Problem of stack slot coloring

Hi,

Can anyone help me with the stack slot coloring optimization?
This corresponding file is /lib/codegen/stackslotcoloring.cpp.

It is said this optimization was for stack slot overlay for frame size reduction, after register allocation phase.
And this transformation pass relies on the LiveStack analysis pass.

How, when checking the source code, it seems the LiveStack analysis has not been implemented, since the code was found in LiveStackAnalysis.cpp:

bool LiveStacks::runOnMachineFunction(MachineFunction &MF) {
TRI = MF.getTarget().getRegisterInfo();
// FIXME: No analysis is being done right now. We are relying on the
// register allocators to provide the information.
return false;
}

And I found the greedy register allocator did nothing to fill the LiveStackAnalysis::S2IMap, which is critical for the stack slot coloring.
Furthermore, the LiveInterval analysis only computes live intervals for virtual registers, but not for stack slots which has frame indexes.
Does it mean this optimization has not been implemented yet ? And any advice for me to do it by myself?
Or am I misunderstanding the implementation?

I really need some advice eagerly!
Any help is greatly appreciated!

From: "Qingan Li" <ww345ww@gmail.com>
To: llvmdev@cs.uiuc.edu
Sent: Monday, October 13, 2014 8:29:38 AM
Subject: [LLVMdev] Problem of stack slot coloring

Hi,

Can anyone help me with the stack slot coloring optimization?
This corresponding file is /lib/codegen/stackslotcoloring.cpp.

It is said this optimization was for stack slot overlay for frame
size reduction, after register allocation phase.
And this transformation pass relies on the LiveStack analysis pass.

How, when checking the source code, it seems the LiveStack analysis
has not been implemented, since the code was found in
LiveStackAnalysis.cpp:

bool LiveStacks::runOnMachineFunction(MachineFunction &MF) {
TRI = MF.getTarget().getRegisterInfo();
// FIXME: No analysis is being done right now. We are relying on the
// register allocators to provide the information.
return false;
}

And I found the greedy register allocator did nothing to fill the
LiveStackAnalysis:: S2IMap, which is critical for the stack slot
coloring.

It seems that the relevant piece of code is in lib/CodeGen/InlineSpiller.cpp:

/// spillAll - Spill all registers remaining after rematerialization.
void InlineSpiller::spillAll() {
  // Update LiveStacks now that we are committed to spilling.
  if (StackSlot == VirtRegMap::NO_STACK_SLOT) {
    StackSlot = VRM.assignVirt2StackSlot(Original);
    StackInt = &LSS.getOrCreateInterval(StackSlot, MRI.getRegClass(Original));
    StackInt->getNextValue(SlotIndex(), LSS.getVNInfoAllocator());
  } else
    StackInt = &LSS.getInterval(StackSlot);

  if (Original != Edit->getReg())
    VRM.assignVirt2StackSlot(Edit->getReg(), StackSlot);

  assert(StackInt->getNumValNums() == 1 && "Bad stack interval values");
  for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i)
    StackInt->MergeSegmentsInAsValue(LIS.getInterval(RegsToSpill[i]),
                                     StackInt->getValNumInfo(0));
  DEBUG(dbgs() << "Merged spilled regs: " << *StackInt << '\n');

And this is called by the register allocator in RAGreedy::selectOrSplitImpl.

When the InlineSpiller calls LSS.getOrCreateInterval, that is a call to LiveStacks::getOrCreateInterval, and that updates the S2IMap inside of LiveStacks.

-Hal

Hal’s advice helps me a lot to understand the implementation much better. Thanks so much!

So, now I am able to state my problem more clearly:

  1. There are two kinds of locals, i.e., the local variables originated from the source code (like C/C++), and the compilation generated temporaries. After instruction selection phase, the former is seen as frame indexes, while the latter is seen as virtual registers.
  2. The LiveInterval analysis computes the live intervals for virtual registers, which are then used for register allocation.
  3. The register allocator spills some virtual registers as stack slot, and provides the information to LiveStack analysis, which is used for stack slot coloring.

So, it seems the stack slot coloring deals with only the compilation generated temporaries, but not the local variables from the source code.
Am I right?
And, why it doesn’t support the overlay of local variables? The reason is, it may do harm to the source code level debug? Or it involves complicated alias analysis?
If I want to do it by myself, any further advice?

2014-10-13 23:32 GMT+08:00 Hal Finkel <hfinkel@anl.gov>:

The mem2reg pass will translate stack based variables into virtual registers & phi nodes, except for cases where the stack address is required.

Got it now. Thanks!