[LLVMdev] Spillers

[Evan Cheng]

Hi,

Sorry for the delay. I was trying to wrap my head around some live  
interval analysis code and have forgotten about emails. :-)


On Aug 6, 2007, at 9:20 AM, David Greene wrote:

> 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

Actually folding decision was made during allocation. When the  
allocator decides to spill, it asks live interval analysis to attempt  
to fold the load / store. The spiller doesn't actually perform the  
"folding". It needs to know that they have happened to keep track of  
reuse information.

>
> - 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).

Right.

>
> 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.

Fernando and Anton have already answered this question. The allocator  
creates new intervals for spill / restore and they are just like  
other intervals (except they are not allowed to spill again).

So to sum up. The code in VirtMap is not really performing the  
spilling. It's mostly just doing the rewrite.

Evan

>
> 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