llvm dev - Jul 2011 - [LLVMdev] scalar evolution to determine access functions in arays

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? 
Thank you.


Alexandra
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110727/32415f41/attachment.html>

On Jul 27, 2011, at 7:11 AM, 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?
> Thank you.
> 
> Alexandra
Hello Alexandra,

The scalar evolution pass doesn't to anything when it runs except initialize
some empty maps. The important one is the Value->SCEV map. SCEV is the class
that holds an expression tree. Scalar evolution populates this map on-demand
when the client asks for an expression via ScalarEvolution::getSCEV(Value).

IndVarSimplify and LoopStrengthReduce are example SCEV clients.

Just be careful to invalidate SCEV entries when you mutate the IR.

-Andy
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110727/213a8313/attachment.html>

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

Hello Tobi,

You are right, we need to run some other passes before running the scalar
evolution pass. The sequence that I run for this example is -O3 -loop-simplify
-reg2mem.  This is why I did not obtain the expressions depending on the loop
indices. So I removed the reg2mem pass and scalar evolution computes the correct
functions.


However, I need to run the reg2mem pass (or any other that would eliminate the
phi nodes) before calling my own passes. So probably we are going to run the
scalar evolution on the code containing the phi nodes, run reg2mem and try to
identify the original variables in the new code built after reg2mem.

Thanks for your advice,
Alexandra



________________________________
From: Tobias Grosser <tobias at grosser.es>
To: Jimborean Alexandra <xinfinity_a at yahoo.com>
Cc: "llvmdev at cs.uiuc.edu" <llvmdev at cs.uiuc.edu>;
"luismastrangelo at gmail.com" <luismastrangelo at gmail.com>
Sent: Wednesday, August 3, 2011 2:21 AM
Subject: Re: [LLVMdev] scalar evolution to determine access functions in arays

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110803/e3a9aba2/attachment.html>