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. Could something like the Uses and Defs constraints apply to whole register classes as well? 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? Thanks, // A
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>
On Sep 22, 2007, at 10:36 AM, Christopher Lamb <christopher.lamb at gmail.com > wrote:> > 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. >>This may work. But the mechanism is designed for load / store folding. What's described here means folding the address computation to a separate instruction. It's not clear how well this fits. I am going to suggest something shocking. :) Since you will end up writing a bunch of target specific code anyway, you might a well write a target specific pass that change generic instructions into data register variant ones when necessary. Evan>> 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 > > > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20070923/77aa0d94/attachment.html>