[DependenceAnalysis][PR52170] Conservative crash on overflowed loop backedge

[artemrad]

Summary

Fixing [PR52170]

The following commit (https://github.com/llvm/llvm-project/commit/7086025d6567562d31fadbaccf08b4fd72ec2100) enabled delinearization of fixed sized arrays. It is now possible to propagate SIV constraints to coupled subscripts in more cases, resulting in more accurate dependence analysis. When a SIV constraint is propagated we re-classify the other non-SIV subscripts. PR52170 describes a case where we hit buggy, superfluous code when doing this reclassification. This change removes this superfluous code.

The original purpose of the removed code (in checkSubscript()) was to make sure that checkUpperBound() was never called on loops whose index variable may overflow. The removed code was superfluous as checkSubscript() works on perfectly nested AddRecs. If a loop can overflow no AddRec can be created and hence checkSubscript() will return that the subscript in NonLinear, as it should.

Changes:

• Removed superfluous code from checkSubscript()
• Added a new LIT test to test that DA reports conservative dependencies when it cannot be determined if overflow will happen in the AddRec

[bmahjour]

llvm/test/Analysis/DependenceAnalysis/TripCountOverflow.ll

36

Shouldn't %n be changed to i64 (while keeping %i as i32) so this test is more representative of the condition check being removed?

[Meinersbur]

Please mention the bug number in the summary as well.

Do you know what was the purpose of the check was? Usually those are not added without reason. In particular, it seems that it has been added in rGc0661aeaf8daf371023cf5669be4bd9b428882d0. What if the code is called when not reclassfying a SIV reclassification?

SCEVs already do the overflow checks that the code was targeting.

Can you clarify? There is a reason why SCEVs have nsw/nuw flags.

[artemrad]

In D119261#3306107, @Meinersbur wrote:

SCEVs already do the overflow checks that the code was targeting.

Can you clarify? There is a reason why SCEVs have nsw/nuw flags.

If a SCEV detects that an overflow is possible it will not produce an AddRec. For example this is the SCEV produced for the simple example below {(4 + %array)<nuw>,+,4}<nuw><%for.outer>. Notice how the starting address is not a constant or a nested AddRec, but rather an expression.

define void @overflow(i32 %n) {
entry:
  %array = alloca [5 x i32], align 1
  br label %for.outer
for.outer:
  %i = phi i32 [ 0, %entry ], [ %i.add, %for.outer ]
  %i.add = add i32 %i, 1
  %i.ptr = getelementptr inbounds [5 x i32], [5 x i32]* %array, i32 0, i32 %i.add
  store i32 0, i32* %i.ptr, align 1
  %cmp = icmp slt i32 %i.add, %n
  br i1 %cmp, label %for.outer, label %other
other:
  ret void
}

Do you know what was the purpose of the check was? Usually those are not added without reason. In particular, it seems that it has been added in rGc0661aeaf8daf371023cf5669be4bd9b428882d0. What if the code is called when not reclassfying a SIV reclassification?

Purpose was to make sure that collectUpperBound() was never called on overflowing loops. More specifically that DA exited early if a loop that could possibly overflow was detected.
My claim is that the code I deleted was superfluous. CheckSubscript works on perfectly nested AddRecs. From the answer above we can see an AddRec would not be produced for a possibly overflowing index. The isLoopInvariant() checks inside the checkSubscript function would of already returned false for this SCEV (as they now do with my change). The deleted code was superfluous.

What if the code is called when not reclassifying a SIV reclassification?

You are correct my statement in the change description was too conservative. This code does get called when we do initial classification of subscripts. It works as intended providing an accurate classification of the subscript. The subscripts that could overflow get the NonLinear classification, and DA conservatively returns [*] for that subscript as it doesn't know how to deal with it.

[artemrad]

@bmahjour @Meinersbur Did I manage to address your concerns?

[artemrad]

@bmahjour @Meinersbur Any other concerns about the change?

[bmahjour]

I'm generally in favour of this patch, but just not sure if there is (or should be) a guarantee that SCEV will NOT produce an AddRec in overflow situations. For example when a GEP has the inbounds attribute, the produced address after adding the index/offset cannot cause an unsigned overflow, so not sure why SCEV would produce different results depending on whether the index/offset could wrap! SCEV seems to produce an AddRec for the offset/index (eg. %i.add) regardless whether it could wrap or not. It's just the GEP that seems to be behaving the way you described.

[nikic]

In D119261#3345920, @bmahjour wrote:

I'm generally in favour of this patch, but just not sure if there is (or should be) a guarantee that SCEV will NOT produce an AddRec in overflow situations. For example when a GEP has the inbounds attribute, the produced address after adding the index/offset cannot cause an unsigned overflow, so not sure why SCEV would produce different results depending on whether the index/offset could wrap! SCEV seems to produce an AddRec for the offset/index (eg. %i.add) regardless whether it could wrap or not. It's just the GEP that seems to be behaving the way you described.

Unless there is some DA-specific restriction involved here, AddRecs (including pointer AddRecs) in SCEV can definitely wrap.

[Meinersbur]

Trying to understand the patch, I applied it and replaced return false with llvm_unreachable. Neither TripCountOverflow.ll, nor PR21585.ll trigger it. The only one that does is Transforms/LoopUnrollAndJam/dependencies_multidims.ll.

llvm/lib/Analysis/DependenceAnalysis.cpp

 // Collect any loops mentioned in the set of "Loops".
 bool DependenceInfo::checkSubscript(const SCEV *Expr, const Loop *LoopNest,
                                     SmallBitVector &Loops, bool IsSrc) {
   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Expr);
   if (!AddRec)
     return isLoopInvariant(Expr, LoopNest);
   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;
-    }
-  }
+
   if (!isLoopInvariant(Step, LoopNest))
     return false;
   if (IsSrc)
     Loops.set(mapSrcLoop(AddRec->getLoop()));
   else
     Loops.set(mapDstLoop(AddRec->getLoop()));
   return checkSubscript(Start, LoopNest, Loops, IsSrc);
 }
bool DependenceInfo::tryDelinearize(Instruction *Src, Instruction *Dst,
   if (!tryDelinearizeFixedSize(Src, Dst, SrcAccessFn, DstAccessFn,
                                SrcSubscripts, DstSubscripts) &&
       !tryDelinearizeParametricSize(Src, Dst, SrcAccessFn, DstAccessFn,
                                     SrcSubscripts, DstSubscripts))
     return false;
 
   int Size = SrcSubscripts.size();
   LLVM_DEBUG({
-    dbgs() << "\nSrcSubscripts: ";
+    dbgs() << "SrcSubscripts:\n";
     for (int I = 0; I < Size; I++)
-      dbgs() << *SrcSubscripts[I];
-    dbgs() << "\nDstSubscripts: ";
+      dbgs() << "\t" << *SrcSubscripts[I] << "\n";
+    dbgs() << "DstSubscripts:\n";
     for (int I = 0; I < Size; I++)
-      dbgs() << *DstSubscripts[I];
+      dbgs() << "\t" << *DstSubscripts[I] << "\n";
   });
 
   // The delinearization transforms a single-subscript MIV dependence test into
   // a multi-subscript SIV dependence test that is easier to compute. So we
   // resize Pair to contain as many pairs of subscripts as the delinearization
   // has found, and then initialize the pairs following the delinearization.
   Pair.resize(Size);
   for (int I = 0; I < Size; ++I) {

llvm/test/Analysis/DependenceAnalysis/TripCountOverflow.ll

+; RUN: opt %s -disable-output "-passes=print<da>" 2>&1 | FileCheck %s
+
+; [PR52170]
+; Test that in cases where SIV propagation does not produce a linear equation
+; (e.g. the trip count of the post propagation SCEV can overflow) produce a
+; conservative answer - don't crash.
+; CHECK-LABEL: dynamic_trip_count
+; CHECK: da analyze - output [* S]!
+; CHECK: da analyze - output [* *|<]!
+; CHECK: da analyze - output [* *]!
+
+define void @dynamic_trip_count(i64 %n) {
+entry:
+  %array = alloca [2 x [5 x i32]], align 1
+  br label %for.outer
+
+for.outer:
+  %i = phi i32 [ 0, %entry ], [ %i.add, %cleanup ]
+  %i.trunc = trunc i32 %i to i16
+  %i.trunc.3 = add i16 %i.trunc, 3
+  %i.ptr = getelementptr inbounds [2 x [5 x i32]], [2 x [5 x i32]]* %array, i16 0, i16 %i.trunc, i16 %i.trunc.3
+  br label %for.inner
+
+for.inner:
+  %j = phi i32 [ 0, %for.outer ], [ %j.1, %for.inner ]
+  store i32 undef, i32* %i.ptr, align 1
+  %j.trunc = trunc i32 %j to i16
+  %j.ptr = getelementptr inbounds [2 x [5 x i32]], [2 x [5 x i32]]* %array, i16 0, i16 %j.trunc, i16 %i.trunc.3
+  store i32 0, i32* %j.ptr, align 1
+  %j.1 = add nuw nsw i32 %j, 1
+  br i1 false, label %for.inner, label %cleanup
+
+cleanup:
+  %i.add = add nuw nsw i32 %i, 1
+  %i.add.extend = sext i32 %i.add to i64
+  %cmp = icmp slt i64 %i.add.extend, %n
+  br i1 %cmp, label %for.outer, label %other
+
+other:
+  ret void
+}