Loop Opt WG - concerning delinearization.

Project Infrastructure LLVM Dev List Archives
1

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:

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@cray.com

2

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