Hi Sanjoy,<br><br>Reading through LoopDependenceAnalysis::analyseWeakZeroSIV(), it appears you give up some information. Sometimes it's possible to prove that certain directions aren't possible.<br>


<br>Consider this example<div><br><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><font face="'courier new', monospace">   for (i = 0; i < N; i++) {</font><div><font face="'courier new', monospace">1)   t = A[0];</font></div>



<div><font face="'courier new', monospace">2)   A[i] = t;</font></div><div><font face="'courier new', monospace">   }</font></div></blockquote><div><br></div><div>There's a loop-carried flow dependence from (2) to (1) with distance vector [<=|0] and a loop-independent anti dependence from (1) to (2) with distance vector [=|<]. We should be able to find these using the Weak-Zero SIV test.</div>

<div><br></div><div>If the distance (difference of the two constant parts) is 0, as it is in this case, the direction vector is either <= (if the bCoefficent is 0) or = (if the aCoefficient is 0).</div><div><br></div>
<div>What's cool about this case is that we can peel the first iteration and remove the loop-carried dependence.</div><div><br></div><div>Here's similar case that happens a lot:</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">
<font face="'courier new', monospace"><br class="Apple-interchange-newline">   for (i = 0; i < N; i++) {</font><div><font face="'courier new', monospace">1)   t = A[N - 1];</font></div><div><font face="'courier new', monospace">2)   A[i] = t;</font></div>
<div><font face="'courier new', monospace">   }</font></div></blockquote><div><br></div></div><div>This time there's a loop-carried anti dependence from (1) to (2), with distance vector [<=|<]. Again, we should be able to find this with the Weak-Zero SIV test.</div>
<div><br></div><div>If the distance equals iterationCount - 1, as it does in this case, the direction vector is either <= (if the aCoefficient is 0) or = (if the bCoefficient is 0).</div><div><br></div><div>Again, we can do useful things here by peeling off the last iteration.</div>
<div><br></div><div>Make sense?</div><div><br></div><div>Thanks,</div><div>Preston</div><div><br></div><div><br></div>
<div><br><br>On Sun, Mar 25, 2012 at 9:49 PM, Sanjoy Das <<a href="mailto:sanjoy@playingwithpointers.com" target="_blank">sanjoy@playingwithpointers.com</a>> wrote:<br>
> 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>



> --<br>> Sanjoy Das.<br>> <a href="http://playingwithpointers.com" target="_blank">http://playingwithpointers.com</a><br></div></div>