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

[Preston Briggs]

Hi Sanjoy & Hal,

Looking at LoopDependenceAnalysis::analyzeZIV ...
I don't understand much about SCEV, but the code seems inadequate.
Consider these three examples:

int a = ...; // we can't be sure of the relationship between a and b
int b = ...; // perhaps they are parameters, or the result of I/O

for (int i = 0; i < n; i++) {
  v[a][i] = ...;
  v[a + 1][i] = ...;
}

for (int i = 0; i < n; i++) {
  v[a][i] = ...;
  v[a][i] = ...;
}

for (int i = 0; i < n; i++) {
  v[a][i] = ...;
  v[b][i] = ...;
}


In the first loop, we can be confident that the two stores are to different
locations and there is no dependence.

In the second loop, we can be sure that the two references are to the same
location and that there's a consistent loop-independent output dependence
between the two stores.

In the third loop, we can't be sure what's going on and must therefore
assume an inconsistent loop-independent output dependence.

The ZIVanalysis code doesn't do the right thing.  I believe, but am not
certain, that it will get the 1st two loops right, but will return
Independent for the 3rd case. Better code might look something like:

SCEV *delta = a - b
if (delta is zero) {
  consistant &= true
  return Dependent
}
else if (delta is a known constant)
  return Independent
}
else { // delta is some symbolic term
  consistent = false
  return Dependent
}


By the way, when I assert all these things about dependence analysis, I'm
not always correct. If you disagree, please let me know and we'll discuss
it.

Thanks,
Preston
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120328/a4bc2d0d/attachment.html>