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

[Hal Finkel]

On Wed, 12 Sep 2012 14:18:43 +0200
Armin Größlinger <armin.groesslinger at uni-passau.de> wrote:

> 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

Agreed. Furthermore, I already have code that does this (I've started
working on a transformation pass which re-factors and optimizes integer
polynomial expressions, so I can repurpose code from there). It sounds
like we just need to extract integer polynomials used by GEPs
containing induction variables, and, order-by-order, factor out the
non-induction variables. That will give us the 'size' of each
dimension. As you've noted below, we need to make sure that no index
exceeds its size, and that all accesses to an array within a given loop
are consistent. Does that sound reasonable?

 -Hal

> (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



-- 
Hal Finkel
Postdoctoral Appointee
Leadership Computing Facility
Argonne National Laboratory