llvm dev - Jul 2014 - [LLVMdev] Physical register reuse during register allocation

Hi,

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.
Can you point me to the code where I can access this data structure and
modify it accordingly? Basically, when does the backend pick a specific
physical register as an instruction's destination.

Thanks in advance,
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140716/9be8655d/attachment.html>

> Can you point me to the code where I can access this data structure and
> modify it accordingly? Basically, when does the backend pick a specific
> physical register as an instruction's destination.
LLVM has multiple register allocators, living in
lib/CodeGen/RegAlloc*.cpp. 2 out of the 4 seem to use the
"AllocationOrder" class which you might be able to fiddle for your
purposes (possibly via the TargetRegisterInfo::getRegAllocationHints
function).

But at a glance, it looks like we don't have *any* policy on recently
used registers at the moment. So support for tuning based on recent
use may be lacking in either direction.

Cheers.

Tim.

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