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

[philip.pfaffe]

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.

[philip.pfaffe]

Add the testcase from the PR.

[davide]

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?

[philip.pfaffe]

IR testcase instead of using clang.

[philip.pfaffe]

Ping.

[philip.pfaffe]

Realized this is still pending. Added some reviewers.

[dmgreen]

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

lib/Analysis/DependenceAnalysis.cpp

if ((isa<SCEVZeroExtendExpr>(Src) && isa<SCEVZeroExtendExpr>(Dst)) ||
     const SCEV *DstCastOp = DstCast->getOperand();
     if (SrcCastOp->getType() == DstCastOp->getType()) {
       Pair->Src = SrcCastOp;
       Pair->Dst = DstCastOp;
     }
   }
 }
 
+static const Loop *getLowestCommonAncestor(const Loop *A, const Loop *B) {
+  if (!A || !B)
+    return nullptr;
+  if (A == B)
+    return A;
+  if (A->getLoopDepth() > B->getLoopDepth())
+    return getLowestCommonAncestor(A->getParentLoop(), B);
+  return getLowestCommonAncestor(A, B->getParentLoop());
+}
 
 // Examine the scev and return true iff it's linear.
 // Collect any loops mentioned in the set of "Loops".
 bool DependenceInfo::checkSrcSubscript(const SCEV *Src, const Loop *LoopNest,
                                        SmallBitVector &Loops) {
   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Src);
   if (!AddRec)
     return isLoopInvariant(Src, LoopNest);
+  const auto *Loop = AddRec->getLoop();
   const SCEV *Start = AddRec->getStart();
   const SCEV *Step = AddRec->getStepRecurrence(*SE);
   const SCEV *UB = SE->getBackedgeTakenCount(AddRec->getLoop());
   if (!isa<SCEVCouldNotCompute>(UB)) {
     if (SE->getTypeSizeInBits(Start->getType()) <
         SE->getTypeSizeInBits(UB->getType())) {
       if (!AddRec->getNoWrapFlags())
         return false;
     }
   }
+
+  // Test if the Loop this AddRec refers to is an ancestor of LoopNest
+  auto *LCA = getLowestCommonAncestor(Loop, LoopNest);
+  if (LCA && LCA != Loop) // Loop is a sibling or uncle of LoopNest.
+    return false;
+
   if (!isLoopInvariant(Step, LoopNest))
     return false;
   Loops.set(mapSrcLoop(AddRec->getLoop()));
   return checkSrcSubscript(Start, LoopNest, Loops);
 }
 
 
 
 // Examine the scev and return true iff it's linear.
 // Collect any loops mentioned in the set of "Loops".
 bool DependenceInfo::checkDstSubscript(const SCEV *Dst, const Loop *LoopNest,
                                        SmallBitVector &Loops) {
   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Dst);
   if (!AddRec)
     return isLoopInvariant(Dst, LoopNest);
+  const auto *Loop = AddRec->getLoop();
   const SCEV *Start = AddRec->getStart();
   const SCEV *Step = AddRec->getStepRecurrence(*SE);
-  const SCEV *UB = SE->getBackedgeTakenCount(AddRec->getLoop());
+  const SCEV *UB = SE->getBackedgeTakenCount(Loop);
   if (!isa<SCEVCouldNotCompute>(UB)) {
     if (SE->getTypeSizeInBits(Start->getType()) <
         SE->getTypeSizeInBits(UB->getType())) {
       if (!AddRec->getNoWrapFlags())
         return false;
     }
   }
+  // Test if the Loop this AddRec refers to is an ancestor of LoopNest
+  auto *LCA = getLowestCommonAncestor(Loop, LoopNest);
+  if (LCA && LCA != Loop) // Loop is a sibling or uncle of LoopNest.
+    return false;
+
   if (!isLoopInvariant(Step, LoopNest))
     return false;
-  Loops.set(mapDstLoop(AddRec->getLoop()));
+  Loops.set(mapDstLoop(Loop));
   return checkDstSubscript(Start, LoopNest, Loops);
 }
 
 
 // Examines the subscript pair (the Src and Dst SCEVs)
 // and classifies it as either ZIV, SIV, RDIV, MIV, or Nonlinear.
 // Collects the associated loops in a set.
 DependenceInfo::Subscript::ClassificationKind

test/Analysis/DependenceAnalysis/pr31848.ll

+; RUN: opt -da -analyze < %s | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @foo(i32* nocapture %A, i32 %n) {
+entry:
+  %n.cmp = icmp sgt i32 %n, 0
+  br i1 %n.cmp, label %for.j.header, label %exit
+
+for.j.header:
+  %j= phi i32 [ %j.inc, %for.j.latch ], [ 0, %entry ]
+  br label %for.i.header
+
+for.i.header:
+  %i = phi i32 [ %i.inc, %for.i.latch ], [ 0, %for.j.header ]
+  br label %for.di.header
+
+for.di.header:
+  %di = phi i32 [ -1, %for.i.header ], [ %di.inc, %for.di.latch ]
+  %di.add = add nsw i32 %di, %i
+  br label %for.dj.header
+
+for.dj.header:
+  %dj = phi i32 [ -1, %for.di.header ], [ %dj.inc, %body ]
+  %dj.add = add nsw i32 %dj, %j
+  br label %while.x
+
+while.x:
+  %x = phi i32 [ %di.add, %for.dj.header ], [ %x.inc, %while.x ]
+  %x.cmp = icmp slt i32 %x, 0
+  %x.inc = add nsw i32 %x, %n
+  br i1 %x.cmp, label %while.x, label %while.y
+
+while.y:
+  %y = phi i32 [ %y.inc, %while.y ], [ %dj.add, %while.x ]
+  %y.cmp = icmp slt i32 %y, 0
+  %y.inc = add nsw i32 %y, %n
+  br i1 %y.cmp, label %while.y, label %body
+
+body:
+  %mul = mul nsw i32 %y, %n
+  %add = add nsw i32 %mul, %x
+  %idxprom = sext i32 %add to i64
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom
+; CHECK: da analyze - output [* * * *]
+  store i32 7, i32* %arrayidx, align 4
+  %dj.inc = add nsw i32 %dj, 1
+  %dj.exitcond = icmp eq i32 %dj.inc, 2
+  br i1 %dj.exitcond, label %for.di.latch, label %for.dj.header
+
+for.di.latch:
+  %di.inc = add nsw i32 %di, 1
+  %di.exitcond = icmp eq i32 %di.inc, 2
+  br i1 %di.exitcond, label %for.i.latch, label %for.di.header
+
+for.i.latch:
+  %i.inc = add nuw nsw i32 %i, 1
+  %i.exitcond = icmp eq i32 %i.inc, %n
+  br i1 %i.exitcond, label %for.j.latch, label %for.i.header
+
+for.j.latch:
+  %j.inc = add nuw nsw i32 %j, 1
+  %j.exitcond = icmp eq i32 %j.inc, %n
+  br i1 %j.exitcond, label %exit, label %for.j.header
+
+exit:
+  ret void
+}