[LLVMdev] scalar evolution to determine access functions in arays

[Tobias Grosser]

On 07/27/2011 03:11 PM, Jimborean Alexandra wrote:
> Hello,
>
> How can I compute the functions on the loop iterators used as array
> indices?
>
> For example:
>
> for i = 0, N
> for j = 0, M
> A[2*i + j - 10] = ...
>
> Can I obtain that this instruction A[2*i + j - 10]= .. always accesses
> memory using a function f(i,j) = 2*i + j - 10 + base_address_of_A
>
> If I run the scalar evolution pass on this code I obtain:
>
> %arrayidx = getelementptr inbounds [200 x i32]* @main.A, i32 0, i64 %idxprom
>
> --> ((4 * (sext i32 (-10 + (2 * %tmp6) + %tmp7) to i64)) + @main.A)
>
> Could you please offer an insight on how can I obtain the function from
> the internals of the scalar evolution pass?


Hi Alexandra,

sorry for the delay, I was a little bit busy.

In general your approach is correct, but scalar evolution is in your 
case not able to derive an access function that is defined in terms of 
loop iterators. (If it would you would have something like {0, + 
1}<loop_1> in your scev expression).

What I suspect is that you need to run some canonicalization passes 
before you actually run the scalar evolution pass. Most of the time 
these passes should be sufficient:
-correlated-propagation -mem2reg -instcombine -loop-simplify -indvars

But in Polly we use e.g.:
-basicaa -mem2reg -simplify-libcalls -simplifycfg -instcombine 
-tailcallelim -loop-simplify -lcssa -loop-rotate -lcssa -loop-unswitch 
-instcombine -loop-simplify -lcssa -indvars -loop-deletion -instcombine 
-polly-prepare -polly-region-simplify -indvars

If you send me the .ll file you run your tool on, I could take a closer 
look.

Cheers and all the best
Tobi