Hi Sanjoy,<div><br></div><div>In LoopDependenceAnalysis::AnalyzePair, what's going to happen if we have something like this</div><div><br></div><div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div><font face="'courier new', monospace">for (i = 0; i < n; i++)</font></div>
<div><font face="'courier new', monospace">  for (j = 0; j < n; j++)</font></div><div><font face="'courier new', monospace">    A[i][j]++;</font></div></blockquote><br></div><div>versus</div><div><br></div>
<div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div><font face="'courier new', monospace">for (i = 0; i < n; i++)</font></div><div><font face="'courier new', monospace">  for (j = 0; j < n; j++)</font></div>
<div><font face="'courier new', monospace">    A[j][i]++;</font></div></blockquote><br></div><div>That is, will the ordering of the Subscripts in Subscript be different?</div><div>I don't think they should be. The ordering should correspond to the loops.</div>
<div>That is, results related to the i loop should appear first, then results related to the j loop.</div><div><br></div><div>And what's going to happen here?</div><div><blockquote style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:40px;border-top-style:none;border-right-style:none;border-bottom-style:none;border-left-style:none;border-width:initial;border-color:initial;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px">
<div><br class="Apple-interchange-newline"><font face="'courier new', monospace">for (i = 0; i < n; i++)</font></div><div><font face="'courier new', monospace">    A[i+1][i+2] = A[i][i];</font></div></blockquote>
<br></div><div>where there's 2 subscripts, but only one loop level?</div><div>We should analyze each pair of subscripts separately</div><div>and merge (intersect) results applying to the same loop level.</div><div>In this case, we should notice that there's no possible dependence.</div>
<div><br></div><div>And here?</div><div><br></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div><div><font face="'courier new', monospace">for (i = 0; i < n; i++)</font></div></div><div><font face="'courier new', monospace">  for (j = 0; j < n; j++)</font></div>
<div><div><font face="'courier new', monospace">    A[i] = A[i] + B[i][j];</font></div></div></blockquote><div><br></div><div>where A subscripts don't mention the j loop at all?</div><div>I would say there are 3 dependences:</div>
<div><ol><li>a loop-independent anti dependence with direction vector [0 S|<]</li><li>a loop-carried flow dependence with direction vector [0 S|0]</li><li>a loop-carried output dependence with direction vector [0 S|0]</li>
</ol></div><div>You don't seem to have any scheme for handling these cases.</div><div>We should come up with something.</div><div><br></div><div>Preston</div><div><br></div><div><br><div class="gmail_quote">On Sun, Mar 25, 2012 at 9:49 PM, Sanjoy Das <span dir="ltr"><<a href="mailto:sanjoy@playingwithpointers.com">sanjoy@playingwithpointers.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi Hal, Preston!<br>
<br>
Sorry for the delay!  Got busy with some offline work.<br>
<br>
I've worked on my previous code to calculate direction and distance<br>
vectors whenever possible (strong SIV, basically).  I think the<br>
current code is much clearer and would like your opinions on it.<br>
<br>
I have attached the patch and also pushed to the github repo I<br>
mentioned [1].<br>
<br>
Thanks!<br>
<br>
[1] <a href="https://github.com/sanjoy/llvm/tree/lda" target="_blank">https://github.com/sanjoy/llvm/tree/lda</a><br>
<div class="HOEnZb"><div class="h5">--<br>
Sanjoy Das.<br>
<a href="http://playingwithpointers.com" target="_blank">http://playingwithpointers.com</a><br>
</div></div></blockquote></div><br></div>