[LLVMdev] scalar evolution to determine access functions in arays

[Jimborean Alexandra]

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>