[LLVMdev] Greedy register allocation

[Evan Cheng]

On May 4, 2011, at 5:17 AM, Chris Lattner <clattner at apple.com> wrote:

> 
> On May 3, 2011, at 4:08 PM, David A. Greene wrote:
> 
>>> 
>>> It's just that an REX prefix is required on some instructions when
>>> %xmm8 is used. Is it worth it to undo LICM just for that? In this
>>> case, probably. In general, no.
>> 
>> Ah, so you're saying the regression is due to the inner loop icache
>> footprint increasing.  Ok, that makes total sense to me.  I agree this
>> is a difficult thing to get right in a general sort of way.  Perhaps the
>> CostPerUse (or whatwever heuristics use it) can factor in the loop body
>> size so that tight loops are favored for smaller encodings.
> 
> It is almost certainly that the inner loop doesn't fit in the processors predecode loop buffer.  Modern intel X86 chips have a buffer that can hold a very small number of instructions and is bound by instruction count, code size, and sometimes # cache lines.  If a loop fits in this it allows the processor to turn off the decoder completely for the loop, a significant power and performance win.
> 
> 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. 

Evan

> 
> -Chris
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev