[LLVMdev] Register allocation in two passes

[Andrew Trick]

On Nov 28, 2011, at 3:39 PM, Borja Ferrer wrote:

> Hello, 
> 
> I'm having a curious design conflict related to reserving registers before the register allocator pass is executed with the backend I'm writing. Basically, what I need is to reserve a certain register only if frame space is allocated in the stack, more precisely I'm interested in the case where a register spill occurs.
> In order to know if a register is spilled the register allocator has to be executed so i can reserve this special reg, but since the register reservation occurs before the allocator is executed there's no way to get this info in only a single pass.
> The only solution i can think of is running the regalloc twice, first to see if any regs are spilled without performing any changes and a second one for doing the real allocation. As a test I've managed to do this with the Greedy regalloc by making the first regalloc execution to not perform a virtreg rewrite at the end of the function pass. But i really want to know if this is safe and if there's a better way of doing it.
> 
> Thanks for any suggestions
> 

The best solution is probably to convert your "reserved" register into an "allocatable" register that is forced to allocate to certain operands (presumably involved in spill code) by defining physical register operands. When live ranges for those special operands are created (on-the-fly), they would need to "evict" any other live ranges currently allocated to their special register with overlapping live ranges. The existing eviction mechanism might even be sufficient to handle it.

But if you really want to reserve the register, you could do that as well. You would do an "en masse" eviction of any live ranges allocated to that register at the time of the first spill. Then prevent anyone else from allocating it, for example by creating a fake live range that spans the entire function.

Neither of these solutions is currently implemented, but the new design supports this sort of thing well, and it's not an uncommon problem to face when porting a backend. I think it would be neat to support this, but Jakob may have a better how it should be done.

-Andy