[llvm-dev] Delinearization validity checks in DependenceAnalysis

[Bardia Mahjour via llvm-dev]

Hi all,

I have been looking at the `DependenceAnalysis` pass in
`llvm/include/llvm/Analysis/DependenceAnalysis.h`.
In order for this analysis to produce accurate dependence vectors for
multi-dimensional arrays in nested loops, it needs to "delinearize" array
element accesses to recover the subscripts in each dimension of the array.
I believe that the current implementation of delinearization is based on
this paper:
http://web.cse.ohio-state.edu/~pouchet.2/doc/ics-article.15a.pdf.

This paper describes how to delinearize the subscripts, and as a last step
it requires certain conditions to be met in order to validate that the
delinearized indexes are correct. The `tryDelinearize` function in
`DependenceAnalysis.cpp` appears to be checking for cases where these
conditions can be validated *at compile time*:

```
  // Statically check that the array bounds are in-range. The first
subscript we
  // don't have a size for and it cannot overflow into another subscript,
so is
  // always safe. The others need to be 0 <= subscript[i] < bound, for both
src
  // and dst.
  // FIXME: It may be better to record these sizes and add them as
constraints
  // to the dependency checks.
  for (int i = 1; i < size; ++i) {
    if (!isKnownNonNegative(SrcSubscripts[i], SrcPtr))
      return false;

    if (!isKnownLessThan(SrcSubscripts[i], Sizes[i - 1]))
      return false;

    if (!isKnownNonNegative(DstSubscripts[i], DstPtr))
      return false;

     if (!isKnownLessThan(DstSubscripts[i], Sizes[i - 1]))
      return false;
    }
```

The problem is that in a lot of cases these conditions cannot be proven
statically, even though the delinearized indexes are in fact correct. For
example consider this simple loop:

```
void foo(int n, int m, int a[][m]) {
  for (int i = 0; i < n-1; ++i)
    for (int j = 2; j < m; ++j) {
      a[i][j] = a[i+1][j-2];
    }
}

clang test.c -c -O3 -S -Xclang -disable-llvm-passes -emit-llvm
opt -mem2reg -instcombine -indvars -loop-simplify -loop-rotate -inline
-simplifycfg test.ll -S -o test.simp.ll
opt test.simp.ll -analyze -da
```

will produce:

```
da analyze - none!
da analyze - anti [* *|<]!
da analyze - output [* *]!
```

If the validity checks were not present, the result would be much more
accurate dependence vector with accurate dependence distances:

```
da analyze - none!
da analyze - consistent anti [1 -2]!
da analyze - none!
```

In my experience the static validity checks tend to fail in many common
cases (involving loops with symbolic bounds). Sometimes this happens
because SCEV is not able to simplify the expressions due to presence of
type casts and sign/zero extensions, but other times the conditions are
just not computable at compile-time.

So far I haven't been able to come up with an example where the validity
checks in the current implementation legitimately catch a case of invalid
delinearization. I've also disabled these checks and run some tests without
finding any failures (other than improvements in the dependence analysis
LIT tests).

I also had a quick look at Polly which benefits from delinearization. From
what I saw, a much more optimistic approach is taken where the validity
checks seem to be avoided.

My questions are:
1. Does anyone have more information about why these validity checks are
necessary in the current implementation, perhaps with some examples showing
an incorrect delinearization that's possible without those checks?
2. Are there any concerns with putting these validity checks under an
option so that we can more easily disable them and experiment? This could
also help us improve LIT tests, since some of them have been pessimised to
compensate for DA's inability to delinearize, and could fail to catch
regressions as a result of bad changes to the data dependence analysis.

Looking forward to your help on this.

Thank you,

Bardia Mahjour
Compiler Optimizations
Hydra Squad Lead
IBM Toronto Software Lab
bmahjour at ca.ibm.com (905) 413-2336

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