[LLVMdev] Regalloc Refactoring

[David Greene]

Chris Lattner wrote:
> On Thu, 12 Apr 2007, David Greene wrote:
>> As I work toward improving LLVM register allocation, I've
>> come across the need to do some refactoring.
> 
> cool.  :)  One request: Evan is currently out on vacation until Monday. 
> This is an area that he is very interested in and will want to chime in 
> on.  Please don't start anything drastic until he gets back :).

Will do.  Right now I'm mostly just experimenting.  We keep our
own copy of the repository here so it's easy to back out changes.

> If you're interested in this, I'd suggest taking a look at some of the 
> smart phi elimination algorithms which use dominance properties (i.e., 
> they don't require an interference graph).

I'm definitely interested in improving coalescing and it sounds like
this would fall under that work.  Do you have references to papers
that talk about the various algorithms?

> Beyond that, one of the issues is the "r2rmap" and "rep" function.  As 
> you've noticed, the coallescer basically uses these to avoid rewriting the 
> code after it does coallescing.  For example, if r1024 is coallesced with 
> r1026, it leaves all uses of both registers in the code, instead of 
> rewriting uses of r1026 with r1024 and deleting all memory of r1026. This 
> mades sense long ago, but now it is increasingly clear that this is a bad 
> idea.  I would much rather have the coallescer be responsible for updating 
> the code.  I would suggest doing this as a first step, it is clearly 
> goodness :)

This is what I was trying to get at, but wasn't entirely clear about.
Does the loop nest after the call to joinIntervals  in 
LiveIntervals::runOnMachineFunction do this rewrite?  Specifically:

   // perform a final pass over the instructions and compute spill
   // weights, coalesce virtual registers and remove identity moves.
   const LoopInfo &loopInfo = getAnalysis<LoopInfo>();

   for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
        mbbi != mbbe; ++mbbi) {
     [...]

       for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
         const MachineOperand &mop = mii->getOperand(i);
         if (mop.isRegister() && mop.getReg() &&
             MRegisterInfo::isVirtualRegister(mop.getReg())) {
           // replace register with representative register
           unsigned reg = rep(mop.getReg());
           mii->getOperand(i).setReg(reg);

Doesn't that last statement actually do the rewrite?  And how does
this interact with the spill cost computation?  I'm thinking separating
out the spill cost computation is going to be a bit more work because
right now it does some of its calculations in concert with this
rewriting.  But it seems workable.

>> For the same reasons, I would like to eventually separate
>> the spill cost calculation from the coalescing phase and

> This seems fine in principle, but i'd like Evan to chime in when he's 
> back.

Sure.

> Yes, but try to break this down into small pieces: first step is to 
> eliminate rep/r2rmap.  Second step is to split coallescer off.  PHI elim 
> changes are independent of this, but would also be a separate project.

Good work plan.  That's how I'll submit the patches.

                                -Dave