[LLVMdev] Multi-dimensional array accesses in LLVM-IR | Thoughts

[Armin Größlinger]

Hi,

I had a few thoughts about recovering multi-dimensional accesses in Polly and
maybe it's time to share them.

On 09/12/2012 10:38 AM, Tobias Grosser wrote:
> [...] Even in the last example which contains parameters both for the
> sizes and the offsets, the parameters for the sizes are the only ones that
> appear on the right hand sides ('8 * %m * %o' and '8 * %o'). 

I guess this is the key observation. When we have a multi-dimensional access,
the coefficients of the iterators have to form an increasing chain w.r.t.
divisibility. For the example

> multidim_ivs_and_integer_offsets_3d.ll:
> ; void foo(long n, long m, long o, double A[n][m][o]) {
> ;   for (long i = 0; i < n; i++)
> ;     for (long j = 0; j < m; j++)
> ;       for (long k = 0; k < o;  k++)
> ;         A[i+3][j-4][k+7] = 1.0;
> ; }

with access function

> ;   {{{(56 + (8 * (-4 + (3 * %m)) * %o) + %A),+,(8 * %m * %o)}<%for.i>,+,
> ;      (8 * %o)}<%for.j>,+,8}<%for.k>

we have (writing the SCEV in ordinary notation and in a suggestive order)

   8*%o*%m * i  +  8*%o * j  +  8 * k  +  24*%m*%o - 32*%o + %A + 56

and we see that the coefficients of the iterators are 8, 8*%o, 8*%o*%m and
every coefficient in this chain divides it successor. By factoring these
coefficients out from all the term they divide, we find the subscripts for the
dimensions:

  8*%o*%m * (i+3)  +  8*%o * (j-4)  +  8 * (k+7)  +  %A

So A[i+4][j-4][k-7] is our candidate for a multi-dimensional access. The math
tool we'd need to implement this is (multivariate) polynomial division or
something similar (coefficients could be arbitrary polynomials, e.g., %o+5*%m+7
if somebody declares something like  double A[][o+5*m+7]  or even more complex
expressions).

Note that two iterators can have the same coefficients (e.g., for
A[i+j][.][.]) or one iterator can have two coefficients (e.g., A[k][k][.]). Or
a "coefficient" may actually be a constant (e.g., A[42][.][.]) or missing in
one access (e.g., A[0][.][.]) so determining the coefficients is non-trivial
(but not too difficult I guess).

> I would guess that we could write a SCEVIterator, that analyzes the SCEVs and guesses
> the dimension sizes. 

I'm not sure if this cane be done on the SCEV directly (instead of polynomials)
for cases that are more complex than products of parameters but I haven't
thought about it thoroughly. OTOH, add recursions should be of the right
structure to check divisibility directly; I'm not sure without more thinking...

> After having written that, it should be possible to write
> another SCEVIterator that given the dimension sizes can separate the different
> dimensions of a SCEV.

Here we have to be careful because when there are several accesses to the same
array (base pointer) not only the coefficients (8, 8*%o, 8*%o*%m above) have to
match but also the range of the subscripts must be right (globally over all
arrays). For example with two accesses

  A[i+4][j-4][k-7]
  A[...][i-k][3*j]

we'd need to check that

   max{j-4, i-k}  -  min{j-4, i-k}   <=  %m - 1
   max{k-7, 3*j}  -  min{k-7, 3*j}   <=  %o - 1

so there is no (inconsistent) overrun between the dimensions (%m and %o are the
factors "between" the dimensions). Note that this also ensures that the factors
between the dimensions are positive, i.e., no dimension is collapsed.

This check can, of course, be relaxed to checking

   0 <= j-4 <= %m - 1
   0 <= k-7 <= %o - 1

   0 <= i-k <= %m - 1
   0 <= 3*j <= %o - 1

(allowing for independent checks for each access) in the assumption that
subscripts start from 0 but I'm not sure how often this will hold on the IR
(after loop index and array base pointer shifts during optimization).

The problem here is that the factors between the dimensions (%m and %o here)
could be non-affine.

> I doubt we will always be able to prove that our guess is correct, but we could
> add a run-time check to test the conditions that we can not prove statically. This is
> also the point, where I think the front-end (or the user with attributes) could help.
> Accesses could be annotated with meta-data providing the size of the array dimensions,
> such that our analysis can start from this meta-data. This could allow our analysis
> to take some short cuts and to avoid some run-time checks.

Makes sense. I think that it should not be too difficult to implement the above
approach for affine factors between the dimensions (which should cover the
common cases) and then we should evaluate how often we need run-time checks and
whether we need more information from the front-ends because other cases occur
in practice.

So far my thoughts for now.

Regards,
Armin