[LLVMdev] Area for improvement

[Chris Lattner]

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/