[llvm-dev] Reserved/Unallocatable Registers

Matthias Braun via llvm-dev llvm-dev at lists.llvm.org
Fri Feb 26 10:52:40 PST 2016


> On Feb 25, 2016, at 9:24 PM, Andrew Trick <atrick at apple.com> wrote:
> 
> 
>> On Feb 25, 2016, at 6:14 PM, Matthias Braun <mbraun at apple.com> wrote:
>> 
>> Lately I have had a few discussions of what it means for a register to be unallocatable or reserved. As this comes up every now and again and I often struggled answering such questions I decided to write down some definite rules and codify the current usage and assumptions. I plan to put the rules below into the doxygen comments of MachineRegisterInfo etc. And I also hope that people will correct me if I am wrong or miss something here!
> 
> Thanks Matthias, much appreciated.
> 
>> = Reserved Registers =
>> 
>> == Rules ==
>> 1) The value read from a reserved register cannot be predicted. Reading a reserved register twice may each time produce a different result.
>> 2) Writing to a reserved register may affect more than just the register.
>> 3) Nonetheless reading/writing reserved registers imposes no constraints on reordering instructions.
> 
> I never thought of it this way. I think of reserved registers as having unbounded, continual liveness. Consequently, the register allocator can never “reuse” them. More precisely, they are live out of the current frame, so reserved register writes can still be reordered with nearby instructions that *don’t* access that register.
> 
> Dependencies still need to be tracked!
> 
> I think copies could be optimized, but reserved registers are implicitly live out of the frame. Reserved register writes should not move across calls. See http://reviews.llvm.org/D15667.
Indeed the current code respects ordering dependencies for reserved registers, so rule 3) above can just be removed and we treat reserved regsiters like any other for reordering.
We can handle them like any other register for calls as well then I guess? Moving through calls should be legal if the calls regmask shows they are preserved, or do you have an example where this would be bad?

- Matthias

> 
>> == Motivation ==
>> Generic backend code, especially register allocators make assumptions about how registers behave. These include things like the value in a register only changes in instruction with a def or regmask/clobber operand for that register or writing to the register changes its value but has no further effects. There are often cases where we need exceptions to these rules, typical examples of this are:
>>  - zero registers (e.g. SPARC g0): They always stay zero even if we write other values.
>>  - program counters (e.g. ARM PC): Their value changes with every instruction and writing into them cause control flow to change.
>>  - Stack pointer, Frame pointer: They mostly behave like normal registers but we do not want to impose scheduling constraints; Even if the stack pointers value changes because we reordered an instruction we can usually fix this up by adjusting offsets in load/store operations.
> 
> Reserved registers could be for out-of-band argument passing that doesn’t follow platform ABI rules.
> 
> -Andy
> 
>> So obviously we exclude these registers from register allocation and cannot make too many assumptions about them. However regardless of the alien semantic we still want to model them as registers because that is how they are modeled in most instruction encodings.
>> 
>> == Implications ==
>> - Register allocators will never assign reserved registers to a virtual register. A reserved register is always unallocatable, but an unallocatable register is not necessary a reserved one!
>> - Liveness analysis makes no sense for reserved registers.
>> - The rules above do not free us from modeling the instruction effects properly! Instructions writing to PC must be marked as terminators, we need to add barrier flags if we want to restrict the reordering of time stamp counters, ...
>> 
>> == Examples ==
>> Assume r0 is a normal register r1 is a reserved register:
>> 
>> - We cannot remove the 2nd COPY here because we may read a different value from r1:
>>  r0 = COPY r1
>>      ... use v0
>>  r0 = COPY r1
>>      ... use v0
>> 
>> - We can remove this COPY because r0 is unused:
>>   r0 = COPY r1
>>   return
>> 
>> - We cannot remove this COPY even if r1 appears unused afterwards. We also cannot replace r1 with a different register.
>>   r1 = COPY r0
>> 
>> - We can reorder these instructions in any way:
>> 
>>  STORE r0 to r1+12
>>  STORE r0 to r1+8
>>  ... = LOAD from r1 + 20
>> 
>> 
>> 
>> = Unallocatable Registers =
>> 
>> A reserved register is not allocatable, however there are also registers which are unallocatable just because they are explicitely excluded from allocation orders, they are not reserved registers. This can be confusing so I added this section talking about those!
>> 
>> == Rules ==
>> They behave like normal registers, the only difference is that:
>> 1) The register allocator will never assign an unallocatable register to a virtual register.
>> 
>> == Motivation ==
>> Typical examples of unallocatable but no reserved registers are:
>> - A CPUs flag register: The scheduler has to respect the order! We are interested in liveness, but we do not necessarily want to spill/reload them or perform register allocation on a single register.
>> - X87 floating point stack registers need special handling on top of the generic register allocation
>> 
>> == Impliciations ==
>> Except for the register allocator not using them they behave like normal registers:
>> - We track the liveness of unallocatable registers
>> - The scheduler respects data/output dependencies for unallocatable registers
>> 
>> == Examples ==
>> Assume r0 is a normal register, r1 is an unallocatable register (but not a reserved one):
>> 
>> - We can remove the 2nd COPY here:
>>  r0 = COPY r1
>>      ... use v0
>>  r0 = COPY r1
>>      ... use v0
>> 
>> - We can remove remove the following two COPYs because the r0/r1 are not used afterwards:
>>  r0 = COPY r1
>>  r1 = COPY r0
>>  return 
>> 
>> - We can replace r1 with a different (normal register) here (provided we replace all following uses)
>> r1 = ...
>>     // ...
>>     = use r1
> 



More information about the llvm-dev mailing list