<html><body><p><font size="2">Hi David,</font><br><br><font size="2">Thank you very much for your response. </font><br><br><font size="2">I also get correct results for my example (for a 64-bit target) if the upper bounds are changed to unsigned. The reason is simply because clang zero-extends `m` for address calculations but sign-extends it for the loop upper bound. This prevents SCEV from canceling out the 'm' term from the difference expression that looks like `(-3 + (sext i32 %m to i64) + (-1 * (zext i32 %m to i64))<nsw>)`. While we cannot reduce expressions of this form in general, it does pose a sever limitation for the vast majority of cases where the loop upper bound is non-negative.</font><br><br><font size="2">Regarding your example, I'm not sure I fully understand the concern and I would appreciate it if you could clarify that for me. My understanding is that if the intended shape of 'a' is in fact 'a[n][m]' then the example, as provided, has an out-of-bound access to start with. To avoid this out-bound access one would need to change the upper bound of the j-loop to be 'm-2'. Interestingly, if we do that, the current validity checks start to pass and we get [0 2] as the dependence vector. Here's a slightly modified version of your example that I tried:</font><br><br><font size="2">```</font><br><font size="2">typedef unsigned long long TT;</font><br><font size="2">void foo(TT n, TT m, int *a) {</font><br><font size="2"> for (TT i = 0; i < n; ++i)</font><br><font size="2"> for (TT j = 0; j < m-2; ++j) {</font><br><font size="2"> a[i*m + j] = a[i*m + j+2];</font><br><font size="2"> }</font><br><font size="2">}</font><br><font size="2">```</font><br><br><font size="2">If the concern is that the actual intended shape of the array may have been something other than a[n][m], and that we are indexing it such that the accesses are in-bound with respect to the memory of the whole array but not with respect to individual dimensions, then I'm not sure we can reason about *any* delinearization statically (except for the limited cases where the bounds are compile-time known).</font><br><br><font size="2">Am I misunderstanding the issue?</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><br><img width="16" height="16" src="cid:1__=8FBB0968DFCF1A308f9e8a93df938690918c8FB@" border="0" alt="Inactive hide details for David Green ---2019/05/14 02:50:27 PM---Hello Interestingly, the example you provide works for me so "><font size="2" color="#424282">David Green ---2019/05/14 02:50:27 PM---Hello Interestingly, the example you provide works for me so long as either it's a 32bit target, or</font><br><br><font size="2" color="#5F5F5F">From: </font><font size="2">David Green <David.Green@arm.com></font><br><font size="2" color="#5F5F5F">To: </font><font size="2">"llvm-dev@lists.llvm.org" <llvm-dev@lists.llvm.org>, Bardia Mahjour <bmahjour@ca.ibm.com></font><br><font size="2" color="#5F5F5F">Cc: </font><font size="2">nd <nd@arm.com></font><br><font size="2" color="#5F5F5F">Date: </font><font size="2">2019/05/14 02:50 PM</font><br><font size="2" color="#5F5F5F">Subject: </font><font size="2">[EXTERNAL] Re: [llvm-dev] Delinearization validity checks in DependenceAnalysis</font><br><hr width="100%" size="2" align="left" noshade style="color:#8091A5; "><br><br><br><tt><font size="2">Hello<br><br>Interestingly, the example you provide works for me so long as either it's a 32bit target, or the array bounds (n and m) are changed to unsigned.<br><br>For a bit of history, DA used to have a different delinearisation method based on geps, but it was known to be invalid in same cases and was eventually removed. There was no delinearisation for a while until these checks were fixed, enough to be correct, but not as powerful as they could be. I believe Pollys delinearisation is much more powerful, and can version loops with runtime conditions.<br><br>IIRC, the checks are there for cases like this:<br>void foo(unsigned n, unsigned m, int *a) {<br> for (int i = 0; i < n; ++i)<br> for (int j = 0; j < m; ++j) {<br> a[i*m + j] = a[i*m + j+2];<br> }<br>}<br><br>The "j-2" can underflow into the previous i iterations space. So the distance vector isn't [0 2] (and isn't even [= <]). Unfortunately this is perfectly valid in C (I think for the int a[][m] case too).<br><br>See this comment for why they were needed and perhaps a better way to fix it:<br></font></tt><tt><font size="2"><a href="https://github.com/llvm/llvm-project/commit/d143c65de3c884d09197da279d2f04f094efaf15#diff-57473b376037dd3637516348b9b02556L3274">https://github.com/llvm/llvm-project/commit/d143c65de3c884d09197da279d2f04f094efaf15#diff-57473b376037dd3637516348b9b02556L3274</a></font></tt><tt><font size="2"><br><br>Any improvements to the delinearisation code would be most welcome.<br>Dave<br><br><br><br><br>From: llvm-dev <llvm-dev-bounces@lists.llvm.org> on behalf of Bardia Mahjour via llvm-dev <llvm-dev@lists.llvm.org><br>Sent: 13 May 2019 14:48<br>To: llvm-dev@lists.llvm.org<br>Subject: [llvm-dev] Delinearization validity checks in DependenceAnalysis<br> <br>Hi all,<br><br>I have been looking at the `DependenceAnalysis` pass in `llvm/include/llvm/Analysis/DependenceAnalysis.h`.<br>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></tt><tt><font size="2"><a href="http://web.cse.ohio-state.edu/~pouchet.2/doc/ics-article.15a.pdf">http://web.cse.ohio-state.edu/~pouchet.2/doc/ics-article.15a.pdf</a></font></tt><tt><font size="2">.<br><br>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*:<br><br>```<br>// Statically check that the array bounds are in-range. The first subscript we<br>// don't have a size for and it cannot overflow into another subscript, so is<br>// always safe. The others need to be 0 <= subscript[i] < bound, for both src<br>// and dst.<br>// FIXME: It may be better to record these sizes and add them as constraints<br>// to the dependency checks.<br>for (int i = 1; i < size; ++i) {<br>if (!isKnownNonNegative(SrcSubscripts[i], SrcPtr))<br>return false;<br><br>if (!isKnownLessThan(SrcSubscripts[i], Sizes[i - 1]))<br>return false;<br><br>if (!isKnownNonNegative(DstSubscripts[i], DstPtr))<br>return false;<br><br>if (!isKnownLessThan(DstSubscripts[i], Sizes[i - 1]))<br>return false;<br>}<br>```<br><br>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:<br><br>```<br>void foo(int n, int m, int a[][m]) {<br>for (int i = 0; i < n-1; ++i)<br>for (int j = 2; j < m; ++j) {<br>a[i][j] = a[i+1][j-2];<br>}<br>}<br><br>clang test.c -c -O3 -S -Xclang -disable-llvm-passes -emit-llvm<br>opt -mem2reg -instcombine -indvars -loop-simplify -loop-rotate -inline -simplifycfg test.ll -S -o test.simp.ll<br>opt test.simp.ll -analyze -da<br>```<br><br>will produce:<br><br>```<br>da analyze - none!<br>da analyze - anti [* *|<]!<br>da analyze - output [* *]!<br>```<br><br>If the validity checks were not present, the result would be much more accurate dependence vector with accurate dependence distances:<br><br>```<br>da analyze - none!<br>da analyze - consistent anti [1 -2]!<br>da analyze - none!<br>```<br><br>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.<br><br>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). <br><br>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. <br><br>My questions are:<br>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? <br>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.<br><br>Looking forward to your help on this.<br><br>Thank you,<br><br>Bardia Mahjour<br>Compiler Optimizations<br>Hydra Squad Lead<br>IBM Toronto Software Lab<br>bmahjour@ca.ibm.com (905) 413-2336<br><br><br><br></font></tt><br><br><BR>
</body></html>