Page MenuHomePhabricator

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

Authored by fhahn on Apr 27 2018, 11:12 AM.

Details

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.

Diff Detail

Event Timeline

fhahn created this revision.Apr 27 2018, 11:12 AM
tvvikram added inline comments.
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 planned changes to this revision.May 4 2018, 10:24 AM
fhahn added inline comments.
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 updated this revision to Diff 149977.Jun 5 2018, 7:22 AM
fhahn added reviewers: philip.pfaffe, sanjoy.

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

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 planned changes to this revision.Jun 7 2018, 8:23 AM

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