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

[Preston Briggs]

Hi Sanjoy,

In LoopDependenceAnalysis::AnalyzePair, what's going to happen if we have
something like this

for (i = 0; i < n; i++)
  for (j = 0; j < n; j++)
    A[i][j]++;


versus

for (i = 0; i < n; i++)
  for (j = 0; j < n; j++)
    A[j][i]++;


That is, will the ordering of the Subscripts in Subscript be different?
I don't think they should be. The ordering should correspond to the loops.
That is, results related to the i loop should appear first, then results
related to the j loop.

And what's going to happen here?


for (i = 0; i < n; i++)
    A[i+1][i+2] = A[i][i];


where there's 2 subscripts, but only one loop level?
We should analyze each pair of subscripts separately
and merge (intersect) results applying to the same loop level.
In this case, we should notice that there's no possible dependence.

And here?

for (i = 0; i < n; i++)
  for (j = 0; j < n; j++)
    A[i] = A[i] + B[i][j];


where A subscripts don't mention the j loop at all?
I would say there are 3 dependences:

   1. a loop-independent anti dependence with direction vector [0 S|<]
   2. a loop-carried flow dependence with direction vector [0 S|0]
   3. a loop-carried output dependence with direction vector [0 S|0]

You don't seem to have any scheme for handling these cases.
We should come up with something.

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/20120327/0b26178a/attachment.html>