[LLVMdev] "Graphite" for llvm

[Tobias Grosser]

On 01/04/10 20:44, Dan Gohman wrote:
>
> On Dec 28, 2009, at 4:24 PM, Tobias Grosser wrote:
>>
>> Probably. I think for single dimensional arrays it will not be too
>> difficult using scalar evolution to get the access functions. I think
>> multi dimensional arrays will get complicated.
>
> If you want to know how the address is calculated as a function of
> each enclosing loop, ScalarEvolution should be quite usable for
> multiple dimensions. This is represented with an add-recurrence
> with another add-recurrence as its "start" operand. For example:
>
>    for (i=0; i<m; ++i)    // X
>      for (j=0; j<n; ++j)  // Y
>        A[i][j];
>
> The store address has this expression:
>
>    {{A,+,sizeof(double)*n}<X>,+,sizeof(double)}<Y>
>
> This says that the value starts at A, steps by sizeof(double)*n
> (address units) with the iteration of loop X, and steps by
> sizeof(double) with the iteration of loop Y.
>
> However, if you want to recognize this as a high-level array
> reference on A with subscripts "i" and then "j", there are some
> missing pieces.

You are right, starting with the ScalarEvolution is the right approach. 
However I believe the high level array analysis might be useful to get 
simpler expressions. I have to think about this later on.

> On a related note, analyzing getelementptr yourself directly is
> doable, but there are several major complications. Using a helper
> library such as ScalarEvolution can protect you from many
> low-level artifacts (though not all).

Sure, it is a great tool.

Tobias