[llvm-dev] Loop Opt WG - concerning delinearization.

[Gary Elsesser via llvm-dev]

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>