llvm dev - Nov 2011 - [LLVMdev] Register allocation in two passes

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20111129/fcddc401/attachment.html>

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

Yes, I want the register to be allocatable when there are no stack frames
used in the function so it can be used for other purposes. In fact, I
looked at how other backends solve this problem, but they are all too
conservative by always reserving the register which in my case it is not a
good solution because of the performance impact of not having this register
available.

I find very interesting what you mentioned of tying the physical reg to
spill code. I've created a pseudo instruction for spill code and i've
tied
this physical reg as one of its operands (this register is sort of a shadow
reg of the stack pointer where it can be used as a normal reg when there's
no stack manipulation in the function or as the SP when regs are spilled).
Then if I understood correctly the second part is making the regalloc aware
of this so it can evict other live ranges using this register to avoid the
conflict of both using this register freely and in the spill code which is
what is happening to me, however I'm not very confident with myself on
touching the regalloc.

I've also added Jakob (i hope he doesn't mind :) ) to this thread so he
can
give his point of view.

Thanks for the reply Andy.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20111129/a605c286/attachment.html>