[LLVMdev] Greedy register allocation

[Chris Lattner]

On May 4, 2011, at 8:23 AM, Evan Cheng wrote:

>> I don't know how realistic it is to model the loop buffer in the register allocator, but this would a very interesting thing to try to optimize for in a later pass.  If an inner loop "almost" fits, then it would probably be worth heroic effort to try to reduce the size of it to shave off a few bytes. 
> 
> Jakob and I have talked about this briefly. The idea is to insert a copy from the larger register to the smaller register in the loop preheader and change the references inside the loop. However, the reality is this is a lot harder than it sounds.
> 
> 1. When is this profitable? We can model size of loop buffer. But this is also dependent on loop alignment. We may have to align small loops on 32 byte boundary to get this right. 
> 
> 2. When should we do this? I was thinking of a late pass. But it's harder to reason about dependencies when register allocation is done. Perhaps it should be done before the virtual registers are rewritten?
> 
> 3. How restrictive is the optimization? What if the register is updated inside the loop? We have to be careful about instructions requiring specific register inputs. What if the register is updated and live out of the loop? We need to copy it back at loop exits?
> 
> We should start tackling the the restrictive forms of the problem. That should fix a number of cases where linear scan got lucky. I am sure there are a lot more interesting cases though. 

Yep, doing this as a late pass, and having it only handle the "easy and obvious" cases would make a lot of sense.  I bet that some non-trivial number of the major speedups that Jakob is seeing are due to "greedy getting lucky".  The bad thing about this is that relying on luck makes performance analysis extremely difficult.  It is much better to actively control these things where possible so that we both get good performance all the time, and have more useful and comparable perf analysis.  I know you already know this :)

-Chris