Incorrect loop limit computation in LFTR

[sanjoy]

Summary

In LinearFunctionTestReplace, it seems like if we conclude that it is unsafe to insert a comparison because the induction variable is poison, we don't emit the overflowing addition, but emit the LFTR with an incorrect IVCount anyway. I've added a test case lftr-bad-ivcount.ll that demonstrates the bug.

There are a handful of unit tests that need to be fixed with this change (so if you just apply this patch, make check will fail), but first I'd like to get a sanity check on whether this is a bug or if I've misunderstood something.

[sanjoy]

I misread the code -- sorry for the noise.

[majnemer]

Here was my thinking when I wrote the check you are modifying:

1. If we are going to compare against the post-incremented induction variable, the IndVar had better not have a wrapping flag.
2. Otherwise, we should compare against the pre-incremented induction variable.

Is there a reason why option number two isn't viable? I assumed that IndVar and BackedgeTakenCount would contain the correct values to compare.

[sanjoy]

The code is perfectly fine; I just misread it, as I said. :)

I've abandoned the revision on phabricator.

Sent from a mobile device, please excuse typos.

lib/Transforms/Scalar/IndVarSimplify.cpp

else {
     return Rewriter.expandCodeFor(IVLimit, LimitTy, BI);
   }
 }
 
 /// LinearFunctionTestReplace - This method rewrites the exit condition of the
 /// loop to be a canonical != comparison against the incremented loop induction
 /// variable.  This pass is able to rewrite the exit tests of any loop where the
 /// SCEV analysis can determine a loop-invariant trip count of the loop, which
-/// is actually a much broader range than just linear tests.
+/// is actually a much broader range than just linear tests.  Returns nullptr on
+/// failure.
 Value *IndVarSimplify::
 LinearFunctionTestReplace(Loop *L,
                           const SCEV *BackedgeTakenCount,
                           PHINode *IndVar,
                           SCEVExpander &Rewriter) {
   assert(canExpandBackedgeTakenCount(L, SE) && "precondition");
 
   // Initialize CmpIndVar and IVCount to their preincremented values.
if (SE->getSignExtendExpr(SE->getAddExpr(IVInit, BackedgeTakenCount),
         SE->getAddExpr(SE->getSignExtendExpr(IVInit, WideTy),
                        SE->getSignExtendExpr(BackedgeTakenCount, WideTy)))
       WrappingFlags = ScalarEvolution::clearFlags(WrappingFlags, SCEV::FlagNSW);
     if (SE->getZeroExtendExpr(SE->getAddExpr(IVInit, BackedgeTakenCount),
                               WideTy) ==
         SE->getAddExpr(SE->getZeroExtendExpr(IVInit, WideTy),
                        SE->getZeroExtendExpr(BackedgeTakenCount, WideTy)))
       WrappingFlags = ScalarEvolution::clearFlags(WrappingFlags, SCEV::FlagNUW);
-    if (!ScalarEvolution::maskFlags(IncrementedIndvarSCEV->getNoWrapFlags(),
-                                    WrappingFlags)) {
-      // Add one to the "backedge-taken" count to get the trip count.
-      // This addition may overflow, which is valid as long as the comparison is
-      // truncated to BackedgeTakenCount->getType().
-      IVCount =
-          SE->getAddExpr(BackedgeTakenCount,
-                         SE->getConstant(BackedgeTakenCount->getType(), 1));
-      CmpIndVar = IncrementedIndvar;
-    }
-  }
+    if (ScalarEvolution::maskFlags(IncrementedIndvarSCEV->getNoWrapFlags(),
+                                   WrappingFlags))
+      return nullptr;
+
+    // Add one to the "backedge-taken" count to get the trip count.  This
+    // addition may overflow, which is valid as long as the comparison is
 
   Value *ExitCnt = genLoopLimit(IndVar, IVCount, L, Rewriter, SE);
   assert(ExitCnt->getType()->isPointerTy() == IndVar->getType()->isPointerTy()
          && "genLoopLimit missed a cast");
 
   // Insert a new icmp_ne or icmp_eq instruction before the branch.
   BranchInst *BI = cast<BranchInst>(L->getExitingBlock()->getTerminator());
   ICmpInst::Predicate P;

test/Transforms/IndVarSimplify/lftr-bad-ivcount.ll

+; RUN: opt -S -indvars < %s | FileCheck %s
+
+define void @test1(i32 %data_len, i32 %sample) {
+; CHECK-LABEL: @test1(
+entry:
+; CHECK: [[IVCount:[^ ]+]] = sub i32 %data_len, %sample
+  %sub = sub i32 %data_len, %sample
+  %cmp4 = icmp eq i32 %data_len, %sample
+  br i1 %cmp4, label %for.end, label %for.body
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %entry ]
+  %indvars.iv.next = add nuw i64 %indvars.iv, 1
+  %tr = trunc i64 %indvars.iv.next to i32
+  %cmp = icmp ult i32 %tr, %sub
+; CHECK: %cmp = icmp ult i32 %tr, [[IVCount]]
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body, %entry
+  ret void
+}