[LLVMdev] Physical register reuse during register allocation

[Jakob Stoklund Olesen]

On Jul 16, 2014, at 7:54 AM, shruti padmanabha <shrupad at umich.edu> wrote:

> When the backend selects a physical register to assign to every virtual register, it must pick a physical register from some data structure of free registers. I'm assuming this choosing is done so as to reuse physical registers as soon as possible. 
> I'm working with an architecture model that could benefit from reusing physical registers as late as possible. So, instead of a LIFO kind of data structure for keeping free physical registers, I need a FIFO queue. 

It's a bit more complicated than that ;-)

The register allocator is optimizing along multiple axes in order to:

- Spill as little as possible.
- Use as few callee saved registers as possible.
- Leave as few copy instructions as possible.
- Use as few expensive registers as possible (like r8-r15 on x86-84 which need one more byte to encode).
- Insert new instructions in the least busy locations.

Trying to reuse registers as late as possible would counteract many of these goals by leaving physical registers unused some of the time. Because of this, the design of RegAllocGreedy is not very friendly to what you are trying to achieve.

If avoiding write-after-read anti-dependencies is really important to you compared to the other optimization goals for RA, it would be fairly simple to implement a linear scan register allocator by starting from RegAllocBasic.cpp. That algorithm makes it easy to use a FIFO queue, but you will get more spilling, and you will of course use all your callee-saved registers very quickly.

You may also be able to do something with TRI:: getRegAllocationHints as Tim suggested.

Thanks,
/jakob