[LLVMdev] help with pointer-to-array conversion

[Chris Lattner]

On Fri, 29 Jul 2005, Naftali Schwartz wrote:
> OK, thanks Chris,

Hi Naftali, sorry I left you hanging.  This dropped off my radar.

> I've found that running
> 	opt -loopsimplify -instcombine -indvars -stats
>
> gives me the setup I need for this transformation, and a small patch makes it 
> happen in the simple case we discussed.

I have been working on a strength reduction pass for LLVM, which recently 
got the ability to reduce induction variables with variable strides.

Because of this, I took out the limitation of -indvars that prevented it 
from promoting indvars with variable strides (which, without strength 
reduction, would result in it introducing multiplies into the bodies of 
loops in the generated code, very bad).

> However, I'm having some trouble 
> when things get a bit more complicated with 3 nesting levels:
>
> int A[3000000], B[20000], C[100], Z;
> int main()
> {
>        int i, j, k, *a, *b, *c;
>        for ( a = &A[0], i = 0; i != 300; i++ )
>                for ( b = &B[0], j = 0; j != 200; j++ )
>                        for ( c = &C[0], k = 0; k != 100; k++ )
>                                Z += *a++ * *b++ * *c++;
> }
> My main problem is maintaining the loop nesting structure, which some pass in 
> llvm seems to want to collapse, and then scalar evolution can't find all the 
> predictable loop counts.  However, when I insert a volatile memory operation 
> inside of each loop, this preserves the loop structure and scalar evolution 
> finds all the loop counts.  What to do?

With current CVS (including the recent change to indvars), this now 
becomes three seperate loops:

$ llvm-gcc big.c -c -o - | opt -loopsimplify | analyze -loops
Printing analysis 'Natural Loop Construction' for function 'main':
Loop Containing:  %loopentry.1, %loopexit.1, %loopexit.2, %no_exit.2, %no_exit.2.outer
     Loop Containing:  %no_exit.2.outer, %loopexit.2, %no_exit.2
         Loop Containing:  %no_exit.2

Note that loop simplify is needed to put the loops into canonical form 
(unmerge them).  Without it, we only get two natural loops (one has two 
backedges):

$ llvm-gcc big.c -c -o - | analyze -loops
Printing analysis 'Natural Loop Construction' for function 'main':
Loop Containing:  %loopentry.1, %loopexit.1, %loopexit.2, %no_exit.2
     Loop Containing:  %no_exit.2, %loopexit.2

Please give current CVS a try and lemme know if you have any problems. 
I'm going to look at your GEP promotion change next.

Thanks,

-Chris

> On Thu, 28 Jul 2005, Chris Lattner wrote:
>
>> On Thu, 28 Jul 2005, Naftali Schwartz wrote:
>>> I now understand that IndVarSimplify.cpp is capable of reproducing array 
>>> references when the pointer initialization from the array address is found 
>>> inside the immediately enclosing loop, such that in the following code:
>> 
>> Ok.
>> 
>>> int A[20000], B[100], Z;
>>> int main()
>>> {
>>>        int i, j, *a, *b;
>>>        for ( a = &A[0], i = 0; i != 200; i++ )
>>>                for ( b = &B[0], j = 0; j != 100; j++ )
>>>                        Z += *a++ * *b++;
>>> }
>>> 
>>> the pointer b can be transformed into an offset from B[], but a cannot be 
>>> transformed into an offset from A[] because the initialization is two 
>>> levels up.
>> 
>> Hrm, that should work.
>> 
>>> I started poking around in IndVarSimplify.cpp and I have a patch which 
>>> should (at least partially) enable the transformation for a as well, but I 
>>> find that although the code looks OK in debug printouts, the gccas output 
>>> is unchanged.
>> 
>> Ok
>> 
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/