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

[Michael Kruse via llvm-dev]

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