[IndVars] avoid crash in LFTR when assuming an add recurrence

[spatel]

Summary

The test is a crasher reduced from:
https://llvm.org/PR49993

I don't know IndVars / SCEV well enough to say if this fix is sufficient. Also, I didn't see an obvious recursion limit to explain why we need 10 urem instructions to trigger, but removing any of those avoids the bug.

[lebedev.ri]

Avoiding assert sounds reasonable to me.

[reames]

This patch looks suspiciously like it's fixing a symptom not the cause. The test case in this review does not reproduce for me. However, the original reduced case from the mentioned bug does.

Glancing at the SCEV for the original test before the transform shows that both the phi and the add *are* AddRecExprs. I'd suggest printing the SCEVs at the point of crash to see what might have changed or to better understand how we can match a loop counter - which the example does appear to be - and yet end up with the increment not being an addrec.

Your patch seems like a workaround. I suspect we'll see other problems if the expected pre-conditions to the LFTR method are not met.

To be clear, I'm not opposing a workaround if this is breaking something badly, I just want to make sure we don't stop at the workaround if there's a deeper issue here.

[nikic]

This is what the SCEV looks like: https://gist.github.com/nikic/28415b7c83f1d7599dc6ac1b04da88b3

I believe this is hitting the hasHugeExpression() limit, and thus not folding the +1 into the AddRec. So I think this doesn't indicate a problem from the SCEV side.

However, I think it would be better to bail out in this case in isLoopCounter() already. As written, I think this code is subtly wrong because it will not drop nowrap flags if it's not an AddRec -- we should be dropping them though, as we just don't have any information in this case.

[spatel]

In D101291#2717400, @reames wrote:

This patch looks suspiciously like it's fixing a symptom not the cause. The test case in this review does not reproduce for me. However, the original reduced case from the mentioned bug does.

Note: I don't disagree with any of the comments and/or reworking this patch, but I'd like to make sure we are seeing the same thing. When you tested locally, did you include a data layout? Without that, I suspect we bail out early without trying any transforms.
The regression test file that I am adding to has:
target datalayout = "n8:16:32:64"

We need the n32 at least to get into trouble in my testing.

[spatel]

Patch updated:
Check for an add recurrence sooner, so we bail out faster.
Also added an assert before the plain cast, so we have a slightly better diagnostic if there's still some other way to get into linearFunctionTestReplace() without an add recurrence.

[reames]

LGTM to the new version. Please leave out the assert, I really don't think it adds anything, and it's definitely not idiomatic.

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

linearFunctionTestReplace(Loop *L, BasicBlock *ExitingBB,
   // that SCEV didn't infer for the post-inc addrec (even if we use a pre-inc
   // check), because the pre-inc addrec flags may be adopted from the original
   // instruction, while SCEV has to explicitly prove the post-inc nowrap flags.
   // TODO: This handling is inaccurate for one case: If we switch to a
   // dynamically dead IV that wraps on the first loop iteration only, which is
   // not covered by the post-inc addrec. (If the new IV was not dynamically
   // dead, it could not be poison on the first iteration in the first place.)
   if (auto *BO = dyn_cast<BinaryOperator>(IncVar)) {
-    const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(SE->getSCEV(IncVar));
+    if (auto *AR = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(IncVar))) {
       if (BO->hasNoUnsignedWrap())
         BO->setHasNoUnsignedWrap(AR->hasNoUnsignedWrap());
       if (BO->hasNoSignedWrap())
         BO->setHasNoSignedWrap(AR->hasNoSignedWrap());
     }
+  }
 
   Value *ExitCnt = genLoopLimit(
       IndVar, ExitingBB, ExitCount, UsePostInc, 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.

llvm/test/Transforms/IndVarSimplify/lftr.ll

for.body29:
   %cmp = icmp ne i8* %iv.next, inttoptr (i64 11 to i8*)
   %and = and i1 %cmp, %cmp
   br i1 %and, label %for.body29, label %exit
 
 exit:
   ret void
 }
 
+define void @PR49993() {
+; CHECK-LABEL: @PR49993(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[IF_END:%.*]]
+; CHECK:       d:
+; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ [[ADD:%.*]], [[D:%.*]] ], [ [[REM10:%.*]], [[IF_END]] ]
+; CHECK-NEXT:    [[ADD]] = add nsw i32 [[PHI]], 1
+; CHECK-NEXT:    [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[REM10]], i32 3)
+; CHECK-NEXT:    [[TMP0:%.*]] = sub i32 [[SMAX]], [[TMP4:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[REM10]], [[TMP0]]
+; CHECK-NEXT:    [[TMP2:%.*]] = add i32 [[TMP1]], 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[ADD]], [[TMP2]]
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[D]], label [[IF_END_LOOPEXIT:%.*]]
+; CHECK:       if.end.loopexit:
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[REM1:%.*]] = urem i32 undef, undef
+; CHECK-NEXT:    [[REM2:%.*]] = urem i32 [[REM1]], undef
+; CHECK-NEXT:    [[REM3:%.*]] = urem i32 [[REM2]], undef
+; CHECK-NEXT:    [[REM4:%.*]] = urem i32 [[REM3]], undef
+; CHECK-NEXT:    [[REM5:%.*]] = urem i32 [[REM4]], undef
+; CHECK-NEXT:    [[REM6:%.*]] = urem i32 [[REM5]], undef
+; CHECK-NEXT:    [[REM7:%.*]] = urem i32 [[REM6]], undef
+; CHECK-NEXT:    [[REM8:%.*]] = urem i32 [[REM7]], undef
+; CHECK-NEXT:    [[REM9:%.*]] = urem i32 [[REM8]], undef
+; CHECK-NEXT:    [[REM10]] = urem i32 [[REM9]], undef
+; CHECK-NEXT:    [[TMP3:%.*]] = sub i32 0, [[REM10]]
+; CHECK-NEXT:    [[TMP4]] = mul i32 [[TMP3]], -1
+; CHECK-NEXT:    br label [[D]]
+;
+entry:
+  br label %if.end
+
+d:
+  %phi = phi i32 [ %add, %d ], [ %rem10, %if.end ]
+  %add = add nsw i32 %phi, 1
+  %cmp = icmp slt i32 %phi, 3
+  br i1 %cmp, label %d, label %if.end
+
+if.end:
+  %rem1 = urem i32 undef, undef
+  %rem2 = urem i32 %rem1, undef
+  %rem3 = urem i32 %rem2, undef
+  %rem4 = urem i32 %rem3, undef
+  %rem5 = urem i32 %rem4, undef
+  %rem6 = urem i32 %rem5, undef
+  %rem7 = urem i32 %rem6, undef
+  %rem8 = urem i32 %rem7, undef
+  %rem9 = urem i32 %rem8, undef
+  %rem10 = urem i32 %rem9, undef
+  br label %d
+}
 
 declare i32 @llvm.loop.decrement.reg.i32(i32, i32)