[LLVMdev] Regalloc Refactoring

[Evan Cheng]

On Apr 12, 2007, at 2:37 PM, David Greene wrote:

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

Yay!

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

Right. r2rmap is dead after coalescing. Chris' suggestion (colaescer  
owns it) makes sense.

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

While I agree spill cost computation does not belong in coalescer, I  
am not sure if it should go into a separate pass. To me, spill cost  
formulas should be register allocator specific. Perhaps it ought to  
belong to a generic register allocator class. Each derivative  
allocator is responsible for overriding it and calling it if it deems  
necessary.

I am not too concerned about the potential increase in compile time.  
But please measure it nevertheless. :-) One of these days we will  
provide a reg -> uses mapping to help to mitigate the cost.

Evan

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