[LLVMdev] Area for improvement

[Jeff Cohen]

Chris Lattner wrote:

> On Mon, 21 Feb 2005, Jeff Cohen wrote:
>
>> Sorry, I thought I was running selection dag isel but I screwed up 
>> when trying out the really big array.  You're right, it does clean it 
>> up except for the multiplication.
>>
>> So LoopStrengthReduce is not ready for prime time and doesn't 
>> actually get used?
>
>
> I don't know what the status of it is.  You could try it out, and see 
> what it does. :)  I would suggest adding it to gccas immediately after 
> the SCCP pass.

I know it has a lot of FIXMEs in it.

>
>> I might consider whipping it into shape.  Does it still have to 
>> handle getelementptr in its full generality?
>
>
> What do you mean?
>
> -Chris

Consider the bytecode I originally posted for the nested for loop.  If 
the getelementptrs haven't been replaced with something simpler, LSR 
will have to take them apart itself.  The multiplication cannot be 
replaced with addition without the two-dimensional access being replaced 
with one-dimensional access plus some pointer arithmetic.  I would guess 
that they will not have been decomposed before LSR is run, correct?

It also appears the current LSR reduces each GEP in isolation of all the 
others.  That clearly is bad for this example, as all the GEPs in this 
loop do the same thing with the induction variable.  Creating a separate 
pointer for each one only makes things worse.  Ordinarily the addressing 
is explicit so the redundancy would have been removed and the LSR 
algorithm doesn't have to worry about it, but here it does.  Bottom line 
is it has to strength reduce operations that are implicit, so it first 
has to determine what those operations are and detect common 
subexpressions among those operations itself (possibly across multiple 
basic blocks).  It doesn't appear to handle explicit multiplications at 
all (probably doesn't add much value to do so).

It's a challenge :)