[LLVMdev] Spillers

[David Greene]

Can someone explain the theory behind the spillers in VirtRegMap.cpp?

It seems as though the spillers do triple duty:

- Insert load/store operations and/or fold instructions as necessary to carry
  out spills

- Rewrite the spilled virtual registers to use machine registers (mapping 
  given by the caller in the VRM).

- Rewrite machine code to change virtual registers to physical registers
  (mapping given by the caller in the VRM, presumably the caller is regalloc).

My question concerns duty #2.  There is code in the spiller that assumes 
intervals created to spill a virtual register have been mapped to physical 
registers.  Why is this so?  This puts a constraint on register allocation 
that is potentially bad.

For example, the prototype graph coloring allocator posted by Bill W. some 
time ago has this code in it (the **** comments are my own):

/// SpillLiveInterval - Assign a live interval to a stack slot.
/// 
void RegAlloc::SpillLiveInterval(LiveInterval* LI) {
[...]
  int Slot = VRM->assignVirt2StackSlot(LI->reg);
  DEBUG(std::cerr << "Spilling " << *LI << " into slot " << Slot << "\n");
  std::vector<LiveInterval*> Added =
    LIs->addIntervalsForSpills(*LI, *VRM, Slot);

  static unsigned J = 0;

  for (unsigned I = 0; I < Added.size(); ++I, ++J) {
    unsigned VReg = Added[I]->reg;
    const TargetRegisterClass* RC = MF->getSSARegMap()->getRegClass(VReg);
    TargetRegisterClass::const_iterator Iter = 
RC->allocation_order_begin(*MF);
    if (Iter + J >= RC->allocation_order_end(*MF)) J = 0;
    unsigned PReg = *(Iter + J);

    // **** Assign the newly-created live interval to a physical register
    VRM->assignVirt2Phys(VReg, PReg);
    PRT->addRegUse(PReg);

    DEBUG(std::cerr << "\tAdded LI: " << *Added[I]
                    << " assigned Reg " << MRI->getName(PReg)
                    << "\n");

    for (LiveIntervals::const_iterator
           K = LIs->begin(); K != LIs->end(); ++K) {
      const LiveInterval& L = K->second;
      unsigned LIReg = L.reg;

      if (!MRegisterInfo::isVirtualRegister(LIReg) || LIReg == VReg) continue;

      // **** Check to see if the physreg we assigned conflicts with something
      // **** else.  If so, that thing has to live in memory too.
      if (VRM->hasPhys(LIReg) && VRM->getPhys(LIReg) == PReg &&
          !VRM->hasStackSlot(LIReg) && Added[I]->overlaps(L))
        VRM->assignVirt2StackSlot(LIReg);
    }
  }

The two points I want to talk about are noted by the **** comments.  The first
takes a newly-created live interval to represent the lifetime between a reload
and use of the reload (or def and store) and assigns it a physical register
*outside of the coloring algorithm proper.*  This is due to the requirement 
that the spiller see spill intervals mapped to physical registers.

The second is a consequence of the first.  Because of this hackish "coloring"
of the spill interval, we may have to patch up code and move other things
into memory as well.  This is bad.

Traditionally, a graph coloring algorithm spills some number of candidates and
then restarts the algorithm with the graph representing the newly-inserted 
live intervals for the spills.  Those intervals get colored along with 
everything else and therefore the allocator can make a better decision based
on the global information available.

It seems as though the current spillers assume they are the last thing to run.
That's not true in the general case as allocators often want to iterate to get
the best mapping possible.  In fact the priority-based coloring algorithm Bill
posted avoids this iteration precisely because it can't easily happen (as I'm
discovering as I implement my own algorithm).  This leads to poorer register
allocation than is necessary.

Right now, I'm simply trying to understand the logic of the spillers and why 
they expect spill intervals to be pre-colored.  Can someone help?

Thanks.

                                                  -Dave