[LLVMdev] "Graphite" for llvm

[Dan Gohman]

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.

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).

Dan