<html><body><p><font size="2">Hi all,</font><br><br><font size="2">I have been looking at the `DependenceAnalysis` pass in `llvm/include/llvm/Analysis/DependenceAnalysis.h`.</font><br><font size="2">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: </font><a href="http://web.cse.ohio-state.edu/~pouchet.2/doc/ics-article.15a.pdf"><font size="2">http://web.cse.ohio-state.edu/~pouchet.2/doc/ics-article.15a.pdf</font></a><font size="2">.</font><br><br><font size="2">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*:</font><br><br><font size="2">```</font><br><font size="2" face="Courier New"> // Statically check that the array bounds are in-range. The first subscript we</font><br><font size="2" face="Courier New"> // don't have a size for and it cannot overflow into another subscript, so is</font><br><font size="2" face="Courier New"> // always safe. The others need to be 0 <= subscript[i] < bound, for both src</font><br><font size="2" face="Courier New"> // and dst.</font><br><font size="2" face="Courier New"> // FIXME: It may be better to record these sizes and add them as constraints</font><br><font size="2" face="Courier New"> // to the dependency checks.</font><br><font size="2" face="Courier New"> for (int i = 1; i < size; ++i) {</font><br><font size="2" face="Courier New"> if (!isKnownNonNegative(SrcSubscripts[i], SrcPtr))</font><br><font size="2" face="Courier New"> return false;</font><br><br><font size="2" face="Courier New"> if (!isKnownLessThan(SrcSubscripts[i], Sizes[i - 1]))</font><br><font size="2" face="Courier New"> return false;</font><br><br><font size="2" face="Courier New"> if (!isKnownNonNegative(DstSubscripts[i], DstPtr))</font><br><font size="2" face="Courier New"> return false;</font><br><br><font size="2" face="Courier New"> if (!isKnownLessThan(DstSubscripts[i], Sizes[i - 1]))</font><br><font size="2" face="Courier New"> return false;</font><br><font size="2" face="Courier New"> }</font><br><font size="2">```</font><br><br><font size="2">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:</font><br><br><font size="2">```</font><br><font size="2" face="Courier New">void foo(int n, int m, int a[][m]) {</font><br><font size="2" face="Courier New"> for (int i = 0; i < n-1; ++i)</font><br><font size="2" face="Courier New"> for (int j = 2; j < m; ++j) {</font><br><font size="2" face="Courier New"> a[i][j] = a[i+1][j-2];</font><br><font size="2" face="Courier New"> }</font><br><font size="2" face="Courier New">}</font><br><br><font size="2" face="Courier New">clang test.c -c -O3 -S -Xclang -disable-llvm-passes -emit-llvm</font><br><font size="2" face="Courier New">opt -mem2reg -instcombine -indvars -loop-simplify -loop-rotate -inline -simplifycfg test.ll -S -o test.simp.ll</font><br><font size="2" face="Courier New">opt test.simp.ll -analyze -da</font><br><font size="2">```</font><br><br><font size="2">will produce:</font><br><br><font size="2">```</font><br><font size="2" face="Courier New">da analyze - none!</font><br><font size="2" face="Courier New">da analyze - anti [* *|<]!</font><br><font size="2" face="Courier New">da analyze - output [* *]!</font><br><font size="2">```</font><br><br><font size="2">If the validity checks were not present, the result would be much more accurate dependence vector with accurate dependence distances:</font><br><br><font size="2">```</font><br><font size="2" face="Courier New">da analyze - none!</font><br><font size="2" face="Courier New">da analyze - consistent anti [1 -2]!</font><br><font size="2" face="Courier New">da analyze - none!</font><br><font size="2">```</font><br><br><font size="2">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.</font><br><br><font size="2">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). </font><br><br><font size="2">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. </font><br><br><font size="2">My questions are:</font><br><font size="2">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? </font><br><font size="2">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.</font><br><br><font size="2">Looking forward to your help on this.</font><br><br><font size="2">Thank you,</font><br><br><font size="2">Bardia Mahjour<br>Compiler Optimizations<br>Hydra Squad Lead<br>IBM Toronto Software Lab<br>bmahjour@ca.ibm.com (905) 413-2336<br><br></font><BR>
</body></html>