[LLVMdev] Register class proliferation

[Andrew Trick]

On Jun 22, 2011, at 5:54 PM, Jakob Stoklund Olesen wrote:

> 
> On Jun 22, 2011, at 5:01 PM, Andrew Trick wrote:
> 
>> On Jun 21, 2011, at 10:39 PM, Jakob Stoklund Olesen wrote:
>>> The register allocators will check interference using atoms instead of aliases. That will be faster since every register has fewer atoms than aliases. It also scales well when adding support for register sequence constraints since new super-registers don't add any atoms.
>>> 
>>> In the greedy and basic allocators, it means that we will have one LiveIntervalUnion per atom instead of one per physical register as we do it today.
>> 
>> That's one way to make an algorithm scale well--just make the best case expensive enough. Actually, I like this approach very much, I just wonder if we need to 8x liveintervals for pure 64-bit code.
> 
> 8x is not necessary, atoms are not bytes or bits.
> 
> The x86 integer registers would each map to two atoms, except for the 8-bit registers which map to a single atom.
> 
> Today, we have live interval unions for %rax, %eax, %ax, %ah, and %al. Using atoms, we would only have live interval unions for %ah and %al. This probably makes interference checking cheaper than it is today.
> 
> When a virtual register is assigned to a physical register, we only need to insert it into one live interval union. With atoms, the virtual register live range would be inserted into multiple live interval unions - one per atom. On x86, that means assignment will be twice as expensive as it is today.
> 
> We perform many more interference checks than we do register assignments, so I think it will be a good tradeoff.
> 
> The x86 reg --> atoms map would look like this:
> 
> %rax --> {1, 2}
> %eax --> {1, 2}
> %ax --> {1, 2}
> %ah --> {1}
> %al --> {2}
> 
> %rbx --> {3, 4}
> ...
> 
> Registers overlap iff they share an atom, that's all you need. X86 would get 60% less live interval unions.

Awesome. It now occurs to me that situations where this would add much overhead in live intervals will probably never be a compile-time concern.

For sane register architectures, it means that the size of the AliasSet would now effectively be 1. And we have several algorithms in codegen where the number of operations performed is multiplied by the size of the AliasSet.

-Andy