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

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>

On 08/03/2011 08:35 AM, Jimborean Alexandra wrote:
> 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.
Just out of interest. Why do you need to run the reg2mem pass?

Cheers
Tobi

Only because in my next passes I change the CFG significantly and it is very
hard to maintain the values of the Phi nodes.

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 9:36 AM
Subject: Re: [LLVMdev] scalar evolution to determine access functions in arays

On 08/03/2011 08:35 AM, Jimborean Alexandra wrote:
> 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.
Just out of interest. Why do you need to run the reg2mem pass?

Cheers
Tobi
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110803/9e746814/attachment.html>