[LLVMdev] Spillers

[Fernando Magno Quintao Pereira]

Well, the spiller in VirtRegMap seems to expect that every possible 
virtual register, including those created due to spilling, are mapped to a 
physical register. It is not that some are "precolored" and others are 
not. The spiller will be run after the register allocator has finished his 
job, and so, each virtual will have a physical location. Maybe Evan could 
correct me if it is not like that.
     In my understanding, your graph coloring algorithm would be iterative, 
as normally happens, and, once it finishes the last iteration, each 
virtual would be mapped to a physical register. At this moment the spiller 
would be called. Further spills should not happen during this phase.

best,

Fernando

> 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
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>