[DA] Use SCEV to conclude DVEntry::EQ in some cases.

[fhahn]

Summary

This is a very naive approach to conclude that both accesses to Arr1 in the
loop below access the same memory location.

void foo(unsigned **Arr1) {
  for (int i = 0; i < 1024; ++i)
    for(int j = 0; j < 1024; ++j)
      Arr1[j][i] = Arr1[j][i] 10;
}

By using SCEV, we can conclude that both accesses to Arr1 access the
same location in each loop iteration. I am probably missing something,
but this seems to work for loop variant accesses in the same loop.

It would be great if you could have a look and let me know what I am
missing :)

For SPEC2006 and the test-suite with LTO, this triggers in around 1100
cases. It also helps LoopInterchange to interchange a few more loops.

[tvvikram]

lib/Analysis/DependenceAnalysis.cpp

3654

Even I am facing a similar issue. What happens if the access is something like A[(i + j) * n] = A[(i + j) * n] + 10, where n can be 0. In this case, the dependence would be "*" and not "=" right? Maybe just checking if difference is zero wouldn't be enough but traversing the SCEV to see that it is simple/understandable would be necessary.

[fhahn]

lib/Analysis/DependenceAnalysis.cpp

3654

Right, thanks for having a look! isLoopInvariant is not enough, looks like we need something like "may be loop invariant" :) I'll update the patch.

[fhahn]

Added IsNotLoopInvariant helper to make sure the expressions we are comparing are not loop invariant, to avoid deducing EQ for scalar dependencies.

[philip.pfaffe]

This does not look correct. Consider the AA.ll testcase. Your change makes DA claim there is no output dependency on the load in %for.inner, but there is! Carried over the outer loop. So the result should be input[* =] (don't quote me on the syntax though).

[fhahn]

In D46201#1123382, @philip.pfaffe wrote:

This does not look correct. Consider the AA.ll testcase. Your change makes DA claim there is no output dependency on the load in %for.inner, but there is! Carried over the outer loop. So the result should be input[* =] (don't quote me on the syntax though).

Right, we should only set EQ for levels that with induction variables involved. I will update the patch