[LLVMdev] Q about instruction pattern matching

[Christopher Lamb]

On Sep 22, 2007, at 4:05 AM, Andreas Fredriksson wrote:

> On 9/21/07, Christopher Lamb <christopher.lamb at gmail.com> wrote:
>
>> ISel patterns are matched against DAGs before register allocation.  
>> So you
>> are correct that ISel patterns can't take into account register  
>> classes. The
>> register classes in the patterns are a selection constraint for  
>> the register
>> allocator if that instruction is chosen, not a constraint on  
>> choosing that
>> pattern.
>>
>> Here's a possible way to proceed for now:
>> Define ADDA_32_dx without a pattern. Then in C++ pattern code for  
>> matching
>> address operands select add operations on addresses to ADDA_32_dx.  
>> This way
>> you know that the add your selecting is going to be used as an  
>> address and
>> you can safely tell the register allocator to put the value in an  
>> address
>> register.
>
> Thanks, I guess that makes sense. I might as well go ahead and create
> a general-purpose register class but then require that some operations
> only target the data registers. For instance, multiplication is going
> to require data registers while indirect addressing requires address
> registers.

I'd start with the most straight forward implementation that  
generates correct code. The register allocator currently doesn't  
handle these sorts of register allocation constraints in a  
sophisticated way, so I'd not worry about generating the most  
efficient code for now.

> Could something like the Uses and Defs constraints apply to whole
> register classes as well?

I don't believe so. It's simply a list of physical registers AFAIK.

> For instance, I assume the register
> allocated is going to guarantee that EAX:EDX is not allocated around
> an x86 integer division, and that the inputs end up in the right
> registers. If those constraints "ripple up" through the function,
> couldn't that be augmented to solve this problem as well so that
> arithmetic would automatically select the data registers?

Protecting EAX:EDX is relatively straight forward, it's having the  
inputs end up in the right registers that's tricky.

I'm not an expert on the x86 back end, but my understanding of the  
register allocator is that it doesn't handle these sorts of cascades  
of constraints. The constraints are completely specified by the  
instruction that's selected, this means that a move instruction might  
need to be inserted to move a value between register classes or to  
specific registers. Though it's less than globally optimal, adding  
this sort of affinity propagation would likely add another complex  
dimension to determining optimal register allocation.

Some options down the line would be to make more sophisticated  
patterns that select to instructions that operate on the right  
register classes from the start, or to have a custom machine  
instruction pass similar to x86's operand folding which could swap  
instructions (say from ADD_32_dx_dx to ADDA_32_dx) and perform the  
kind of "ripple up" that you described, eliminating unnecessary  
register to register copies along the way.

--
Christopher Lamb



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20070922/ec16cda1/attachment.html>