llvm dev - May 2011 - [LLVMdev] TargetRegisterInfo and "infinite" register files

On May 17, 2011, at 9:18 AM, Andrew Clinton wrote:
> I have faced this same problem in my backend, and I'm working around it
by providing a large physical register set.  There are two problems with this:
> 
> 1. There's a chance that the register allocator will run out of
registers to assign, in which case the allocation will fail - making it
necessary to retry with a larger register set
> 2. The code generator consumes storage proportional to the number of
registers that could be assigned
> 
> I'd be interested in an improvement to the code generator that makes it
possible to specify an infinite register set without the need to store the
registers explicitly.
As I explained to Justin, allocating against an infinite register file
doesn't really do anything. It's a quadratic time no-op.

What you can do instead is:

1) Just use virtual registers and skip register allocation, or

2) Allocate to a small register file, implement memory operand folding, and
pretend that spill slots are registers.

/jakob

On 05/17/2011 12:54 PM, Jakob Stoklund Olesen wrote:
> On May 17, 2011, at 9:18 AM, Andrew Clinton wrote:
>
>> I have faced this same problem in my backend, and I'm working
around it by providing a large physical register set.  There are two problems
with this:
>>
>> 1. There's a chance that the register allocator will run out of
registers to assign, in which case the allocation will fail - making it
necessary to retry with a larger register set
>> 2. The code generator consumes storage proportional to the number of
registers that could be assigned
>>
>> I'd be interested in an improvement to the code generator that
makes it possible to specify an infinite register set without the need to store
the registers explicitly.
> As I explained to Justin, allocating against an infinite register file
doesn't really do anything. It's a quadratic time no-op.
>
> What you can do instead is:
>
> 1) Just use virtual registers and skip register allocation, or
>
> 2) Allocate to a small register file, implement memory operand folding, and
pretend that spill slots are registers.
>
> /jakob
>
Empirically, 1) is not true.  The linear scan register allocator appears 
to do a very good job of reusing registers that have been killed.  It 
also automatically inserts copies for operations that clobber register 
operands, and coalesces identity register moves.  2) is a good idea but 
when I implemented register allocation, I did not find a straightforward 
way to integrate spilled memory operands into my instruction set.

Andrew

On May 17, 2011, at 11:32 AM, Andrew Clinton wrote:
> On 05/17/2011 12:54 PM, Jakob Stoklund Olesen wrote:
>> What you can do instead is:
>> 
>> 1) Just use virtual registers and skip register allocation, or
>> 
>> 2) Allocate to a small register file, implement memory operand folding,
and pretend that spill slots are registers.
>> 
>> /jakob
>> 
> 
> Empirically, 1) is not true.  The linear scan register allocator appears 
> to do a very good job of reusing registers that have been killed.  It 
> also automatically inserts copies for operations that clobber register 
> operands, and coalesces identity register moves.
Good point. The 2-addr, phi-elim, and coalescer passes are definitely helpful.

The final register allocator pass that assigns physical registers probably
doesn't help you much.

/jakob