[llvm-dev] Delinearization validity checks in DependenceAnalysis

[Michael Kruse via llvm-dev]

Am Mo., 13. Mai 2019 um 08:49 Uhr schrieb Bardia Mahjour via llvm-dev
<llvm-dev at lists.llvm.org>:
> 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.

> 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?

Think of an array A[2][2] and two accesses:

A[1][0] = value;
use(A[0][2]);

The subscript of the second is out-of-range and will be evaluated to
the same address as A[1][0]. A dependence-analysis that assumes that
different subscripts means different addresses will not catch the
dependence between the two statements.

Polly implements the FIXME: It assumes that all accesses are
in-bounds, but will execute the original code if this is not the case.
A runtime check testing for the condition decides whether the
optimized (whose assumptions turned out to be wrong) or original code
is going to be executed.


> 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.

You can upload a patch for this and I don't see issues as long as by
default the safety checks are enabled. However, if you just want to
evaluate, why not just implement it in your local branch?


Michael