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

[Preston Briggs]

I'm travelling right now, so can't fully participate.
But I'd encourage people to read Maslov's paper

Delinearization: an Efficient Way to Break Multiloop Dependence Equations
Vadim Maslov
PLDI '92


Wolfe's book shows the same approach.
My impression was that he can do most, but not all,
of the delinearization we want. At one point, I though that
he couldn't handle coupled subscripts that had been linearized,
but I'll have to re-create my examples.

To get the best results, I thought we should change the GEP
(or have a fancy version in addition to the current one).

Preston


On Wed, Sep 12, 2012 at 9:27 AM, Hal Finkel <hfinkel at anl.gov> wrote:

> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120912/53dfb521/attachment.html>