llvm dev - Jul 2019 - Loop Opt WG - concerning delinearization.

Note the llvm/lib/Analysis/Delinearization.cpp   recommends

SCEVAddRecExpr::delinearize().

See also llvm/lib/Analysis/DependenceAnalysis.cpp w/r the GEP operator.


Also note this 2015 paper:

  *   On recovering multi-dimensional arrays in Polly
Tobias Grosser, Sebastian Pop, J. Ramanujam, P. Sadayappan
Impact2015 at HiPEAC, Amsterdam, The Netherlands
Slides & Paper: Impact 2015<http://impact.gforge.inria.fr/impact2015/>

               http://impact.gforge.inria.fr/impact2015/


Delinearization is useful, particularly when the code has been hand linearized,

as is often the case for C/C++.  Nonetheless, information may be lost by
lowering

multidimenional array references early.  Consider:


   float A[n1][n2], B[n2];

   for (i = 0; i < ni; ++i)

      for (j = 0; j < nj; ++j)

          A[ix[i]][j] += B[j];


Even in C, the compiler may assume 0 <= j < n2.

In Fortran this is beyond dispute.  But after linearization,

even with delinearization, the fact that nj <= n2 is not

known at compile time.  If the subscripts to A where

interchange the situation is even worse, as 0 <= ix[i] < n2

is expensive to verify.


So delinearization provide a benefit w/r hand linearized subscripts,

while analysis of actual multidimensional references is best

done prior to linearization - before information is lost.


Gary Elsesser

  Cray, Inc.

  Bloomington, MN

  gwe at cray.com




-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190703/d43e691c/attachment.html>

Am Mi., 3. Juli 2019 um 18:12 Uhr schrieb Gary Elsesser via llvm-dev
<llvm-dev at lists.llvm.org>:
> Consider:
>
>    float A[n1][n2], B[n2];
>    for (i = 0; i < ni; ++i)
>       for (j = 0; j < nj; ++j)
>           A[ix[i]][j] += B[j];
>
> Even in C, the compiler may assume 0 <= j < n2.
> In Fortran this is beyond dispute.  But after linearization,
> even with delinearization, the fact that nj <= n2 is not
> known at compile time.
Polly also uses the delinearization and does code versioning for this
case: Check that nj<=n2 before executing the code and if not, fall
back to the original code. The cost is small.

> If the subscripts to A where
> interchange the situation is even worse, as 0 <= ix[i] < n2
> is expensive to verify.
This is some indirect access due to the user's data layout or even a
dynamic lookup table.
Research for this problem uses an inspector/executer model, where the
inspector first determines the access indices that the executor can
make use of.
If it is indeed due to a data layout, the compiler could only take
advantage of it it understood the data structure.

Michael