[LLVMdev] Area for improvement

[Vikram Adve]

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