> > Now the problem is obvious. A two dimensional array access is being > performed by a single instruction. The arithmetic needed to address > the element is implicit, and therefore inaccessible to optimizations. > The redundant calculations can not be eliminated, nor can strength > reduction be performed. getelementptr needs to be broken down into > its constituent operations at some point.Jeff, This is exactly right -- any multi-dimensional array indexing operations need to decomposed into a sequence of single index operations so that they can be exposed to GCSE and LICM. This transformation obscures the indexing behavior of the code, so the right place to do this is within each back-end, on LLVM code just before instruction selection. There is a pass called DecomposeMultiDimRefs (which seems to have been incorrectly moved to lib/Target/SparcV9/) which does this transformation. It's used by the SparcV9 back end before instr. selection but is not specific to Sparc. Running this, followed by LICM and GCSE should address this problem. --Vikram
I figured getelementptr exists as it does to facilitate data flow analysis, but it does need to be broken down before instruction selection. It's not just the missed optimization opportunities. It also introduces a huge amount of complexity into instruction selection as they deal with its complexity. It would also take care of many of the FIXMEs in LoopStrengthReduce. Vikram Adve wrote:>> >> Now the problem is obvious. A two dimensional array access is being >> performed by a single instruction. The arithmetic needed to address >> the element is implicit, and therefore inaccessible to >> optimizations. The redundant calculations can not be eliminated, nor >> can strength reduction be performed. getelementptr needs to be >> broken down into its constituent operations at some point. > > > Jeff, > > This is exactly right -- any multi-dimensional array indexing > operations need to decomposed into a sequence of single index > operations so that they can be exposed to GCSE and LICM. This > transformation obscures the indexing behavior of the code, so the > right place to do this is within each back-end, on LLVM code just > before instruction selection. > > There is a pass called DecomposeMultiDimRefs (which seems to have been > incorrectly moved to lib/Target/SparcV9/) which does this > transformation. It's used by the SparcV9 back end before instr. > selection but is not specific to Sparc. Running this, followed by > LICM and GCSE should address this problem. > > --Vikram
On Feb 21, 2005, at 11:12 PM, Jeff Cohen wrote:> I figured getelementptr exists as it does to facilitate data flow > analysis, but it does need to be broken down before instruction > selection. It's not just the missed optimization opportunities. It > also introduces a huge amount of complexity into instruction selection > as they deal with its complexity. It would also take care of many of > the FIXMEs in LoopStrengthReduce.Yes, I agree. Code-generating multi-dim. array index operations becomes significantly simpler after this transformation. One caveat though is that you may want to keep as many successive constant indexes in a GEP together because they can all be folded into a single offset (i.e., a single operand to a load/store), e.g. geteelementptr <Ty*> %p, int 0, int %i, int 3, int 5, int %j, int %k probably should be broken down into: %p1 = gep %p, int 0, int %i %p2 = gep %p1, int 3, int 5, int %j %p3 = gep %p2, int %k or something like that. --Vikram> > Vikram Adve wrote: > >>> >>> Now the problem is obvious. A two dimensional array access is >>> being performed by a single instruction. The arithmetic needed to >>> address the element is implicit, and therefore inaccessible to >>> optimizations. The redundant calculations can not be eliminated, >>> nor can strength reduction be performed. getelementptr needs to be >>> broken down into its constituent operations at some point. >> >> >> Jeff, >> >> This is exactly right -- any multi-dimensional array indexing >> operations need to decomposed into a sequence of single index >> operations so that they can be exposed to GCSE and LICM. This >> transformation obscures the indexing behavior of the code, so the >> right place to do this is within each back-end, on LLVM code just >> before instruction selection. >> >> There is a pass called DecomposeMultiDimRefs (which seems to have >> been incorrectly moved to lib/Target/SparcV9/) which does this >> transformation. It's used by the SparcV9 back end before instr. >> selection but is not specific to Sparc. Running this, followed by >> LICM and GCSE should address this problem. >> >> --Vikram > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://mail.cs.uiuc.edu/mailman/listinfo/llvmdev
On Mon, 21 Feb 2005, Jeff Cohen wrote:> I figured getelementptr exists as it does to facilitate data flow analysis, > but it does need to be broken down before instruction selection. It's not > just the missed optimization opportunities. It also introduces a huge amount > of complexity into instruction selection as they deal with its complexity. > It would also take care of many of the FIXMEs in LoopStrengthReduce.There are two issues here. One is an important one that should be addressed on the LLVM level: we currently do not have a loop strength reduction pass. Loop strength reduction is an important optimization that turns things like this: for (i = ...; ; ++i) A[i] = ... into: for (p = &A[0]; ... ; ++p) *p = ... This transforms multiplies in addressing arithmetic (e.g. &A+i*sizeof(A[0]) into additions (e.g. p = p + sizeof(A[0])). Nate worked on a patch to do this a while back, but I'm not sure where it stands. The second issue is that we need to do redundancy elimination and hoisting on operations that are only exposed once instruction selection is performed. Getelementptr expansion is just ONE particular case of this, but it can happen with any instructions (including the use of large integer (or any FP) constants on RISC machines, addressing globals with PIC code, handling extended/truncated operations (for RISC machines with a single integer size), etc. Note that hacks like "LowerMultiDimRefs" and the sparc Preselection pass sorta-kinda work around SOME of this, but they really are just as bad as the problem: they solve some cases and make other cases worse. The only way to make preselection or lowermultidimrefs work is to duplication all of the knowledge of how the instruction selector will select the code (e.g. the advice about allowing constant indices to be grouped together). This is *exactly* the reason why the new instruction selection framework was introduced. It already handles local CSE trivially, and will be extended to do GCSE, LICM, and eventually PDCE as time permits. Combined with loop strength reduction, these problems should go completely away. Also, with the new instruction selection frameworks, targets don't have to handle GEP instructions at all, so the "complexity" argument above doesn't apply. If you're interested in working on this, I would suggest starting with the loop strength reduction code, as I've heard it's pretty close to working. -Chris> Vikram Adve wrote: > >>> >>> Now the problem is obvious. A two dimensional array access is being >>> performed by a single instruction. The arithmetic needed to address the >>> element is implicit, and therefore inaccessible to optimizations. The >>> redundant calculations can not be eliminated, nor can strength reduction >>> be performed. getelementptr needs to be broken down into its constituent >>> operations at some point. >> >> >> Jeff, >> >> This is exactly right -- any multi-dimensional array indexing operations >> need to decomposed into a sequence of single index operations so that they >> can be exposed to GCSE and LICM. This transformation obscures the indexing >> behavior of the code, so the right place to do this is within each >> back-end, on LLVM code just before instruction selection. >> >> There is a pass called DecomposeMultiDimRefs (which seems to have been >> incorrectly moved to lib/Target/SparcV9/) which does this transformation. >> It's used by the SparcV9 back end before instr. selection but is not >> specific to Sparc. Running this, followed by LICM and GCSE should address >> this problem. >> >> --Vikram > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://mail.cs.uiuc.edu/mailman/listinfo/llvmdev >-Chris -- http://nondot.org/sabre/ http://llvm.cs.uiuc.edu/