This is an archive of the discontinued LLVM Phabricator instance.

[DA] Fix for PR31848: Treat AddRec subscripts containing extra loops as NonLinear
Needs ReviewPublic

Authored by philip.pfaffe on Feb 3 2017, 5:06 AM.

Details

Summary

The SCEVAddRecExpr nest describing a Subscript may contain loops in which the corresponding memory access is not contained in. This causes errors in DependenceAnalysis. An example is this (see PR31848 for details):

void foo(int *A, int n) {

for (int j = 0; j < n; ++j) {
  for (int i = 0; i < n; ++i) {
    for (int di = -1; di <= 1; ++di) {
      for (int dj = -1; dj <= 1; ++dj) {
        int x = i + di;
        int y = j + dj;
        while (x < 0)
          x += n;
        while (y < 0)
          y += n;

        A[y * n + x] = 7;
      }
    }
  }
}

}

This patch detects that, and classifies the subscripts as NonLinear. This solution is possibly a bit over-pessimistic. For instance, subscripts might well be legal, if its extraneous loops are loop invariant wrt. the lowest common ancestor in the loop nest. I haven't been able to produce this situation however, so I'm not sure whether that can actually happen, or whether it triggers entirely different paths of DA.

Diff Detail

Event Timeline

philip.pfaffe created this revision.Feb 3 2017, 5:06 AM
philip.pfaffe added reviewers: chandlerc, mkuper.

Add the testcase from the PR.

philip.pfaffe edited the summary of this revision. (Show Details)Feb 7 2017, 4:13 AM
davide requested changes to this revision.Feb 7 2017, 7:32 AM
davide added a subscriber: davide.
davide added inline comments.
test/Analysis/DependenceAnalysis/pr31848.c
1–2 ↗(On Diff #87390)

LLVM tests shouldn't use clang, but opt directly. Can you rewrite this as an IR test?

This revision now requires changes to proceed.Feb 7 2017, 7:32 AM
philip.pfaffe edited edge metadata.

IR testcase instead of using clang.

davide removed a reviewer: davide.Feb 12 2017, 12:31 PM

Realized this is still pending. Added some reviewers.

Hello. This looks familiar :)

There is a testcase in D46197 (which this is probably a better fix for), with a store outside any loop, but with this same case of the location being an addrec from the preceeding loop. It's not a big problem in that case as the store is not in a loop, making it mostly uninteresting to DA. But the -analyze option will try to look at it, triggering an assert. I think it's not currently handled by this patch because of the if (LCA && ...) check.

Worth fixing here or should we just ignore that case? Perhaps just not analyse loads/stores outside of loops in -analyze?

lib/Analysis/DependenceAnalysis.cpp
871

Nit: Loop instead of AddRec->getLoop(), same as Dst

887

Same again