[LLVMdev] SIV tests in LoopDependence Analysis, Sanjoy's patch

[Preston Briggs]

Hi Sanjoy,

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

Consider this example

   for (i = 0; i < N; i++) {
1)   t = A[0];
2)   A[i] = t;
   }


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.

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

What's cool about this case is that we can peel the first iteration and
remove the loop-carried dependence.

Here's similar case that happens a lot:


   for (i = 0; i < N; i++) {
1)   t = A[N - 1];
2)   A[i] = t;
   }


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.

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

Again, we can do useful things here by peeling off the last iteration.

Make sense?

Thanks,
Preston




On Sun, Mar 25, 2012 at 9:49 PM, Sanjoy Das <sanjoy at playingwithpointers.com>
wrote:
> Hi Hal, Preston!
>
> Sorry for the delay!  Got busy with some offline work.
>
> I've worked on my previous code to calculate direction and distance
> vectors whenever possible (strong SIV, basically).  I think the
> current code is much clearer and would like your opinions on it.
>
> I have attached the patch and also pushed to the github repo I
> mentioned [1].
>
> Thanks!
>
> [1] https://github.com/sanjoy/llvm/tree/lda
> --
> Sanjoy Das.
> http://playingwithpointers.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120404/2667e4d9/attachment.html>