[SCEV] Handle case where MaxBECount is less precise than ExactBECount for OR.

[fhahn]

Summary

In some cases, MaxBECount can be less precise than ExactBECount for AND
and OR (the AND case was PR26207). In the OR test case, both ExactBECounts are
undef, but MaxBECount are different, so we hit the assertion below. This
patch uses the same solution the AND case already uses.

Assertion failed:

((isa<SCEVCouldNotCompute>(ExactNotTaken) || !isa<SCEVCouldNotCompute>(MaxNotTaken))
  && "Exact is not allowed to be less precise than Max"), function ExitLimit

This patch also consolidates test cases for both AND and OR in a single
test case.

Fixes https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=13245

[sanjoy]

lgtm!

[fhahn]

Thanks! While looking at the assertion failure, I also had a look around to see if callers of getBackedgeTakenCount & co check if the returned SCEVExpr is undef, but it seems most users do not do that. I do not have a good concrete example, where using an undef exit count is problematic, but I was wondering if it is safe in general? To me it seems problematic, e.g. if a pass expands an undef SCEVExpr.

One fishy example I could come up with are alias checks in loop-vectorize. If the trip count is undef, we will generate alias checks using undef as upper bound. Those checks could pass (-> say noalias), even though the pointers actually alias in the vector loop ( because we pick a different value for the undef trip count and now the actual trip count is different than the one used for alias checks)

[sanjoy]

In D58853#1415902, @fhahn wrote:

Thanks! While looking at the assertion failure, I also had a look around to see if callers of getBackedgeTakenCount & co check if the returned SCEVExpr is undef, but it seems most users do not do that. I do not have a good concrete example, where using an undef exit count is problematic, but I was wondering if it is safe in general? To me it seems problematic, e.g. if a pass expands an undef SCEVExpr.

One fishy example I could come up with are alias checks in loop-vectorize. If the trip count is undef, we will generate alias checks using undef as upper bound. Those checks could pass (-> say noalias), even though the pointers actually alias in the vector loop ( because we pick a different value for the undef trip count and now the actual trip count is different than the one used for alias checks)

I think you're right -- generating safety checks is unsound if there is an undef in the trip count expression. This will be solved once we use poison as the standard "deferred UB" construct. The software engineering problem here has been that it is very difficult to trigger this sort of corner cases using undef via well defined C/C++ programs, so we as a community haven't had an urgent incentive to fix these corner cases.

For now I think a good workaround would be to:

• Not simplify undef in SCEV expressions
• Avoid doing things that would require us to expand SCEV expressions with undef in them

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

if (BO->getOpcode() == Instruction::Or) {
       } else {
         // Both conditions must be false at the same time for the loop to exit.
         // For now, be conservative.
         if (EL0.MaxNotTaken == EL1.MaxNotTaken)
           MaxBECount = EL0.MaxNotTaken;
         if (EL0.ExactNotTaken == EL1.ExactNotTaken)
           BECount = EL0.ExactNotTaken;
       }
+      // There are cases (e.g. PR26207) where computeExitLimitFromCond is able
+      // to be more aggressive when computing BECount than when computing
+      // MaxBECount.  In these cases it is possible for EL0.ExactNotTaken and
+      // EL1.ExactNotTaken to match, but for EL0.MaxNotTaken and EL1.MaxNotTaken
+      // to not.
+      if (isa<SCEVCouldNotCompute>(MaxBECount) &&
+          !isa<SCEVCouldNotCompute>(BECount))
+        MaxBECount = getConstant(getUnsignedRangeMax(BECount));
 
       return ExitLimit(BECount, MaxBECount, false,
                        {&EL0.Predicates, &EL1.Predicates});
     }
   }
 
   // With an icmp, it may be feasible to compute an exact backedge-taken count.
   // Proceed to the next level to examine the icmp.

llvm/trunk/test/Analysis/ScalarEvolution/exact-exit-count-more-precise.ll

+; RUN: opt -analyze -scalar-evolution %s | FileCheck %s
+
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @test_and(i16 %in) {
+  br label %bb2
+
+bb2:                                              ; preds = %bb1.i, %bb2, %0
+  %_tmp44.i = icmp slt i16 %in, 2
+  br i1 %_tmp44.i, label %bb1.i, label %bb2
+
+bb1.i:                                            ; preds = %bb1.i, %bb2
+  %_tmp25.i = phi i16 [ %in, %bb2 ], [ %_tmp6.i, %bb1.i ]
+  %_tmp6.i = add nsw i16 %_tmp25.i, 1
+  %_tmp10.i = icmp sge i16 %_tmp6.i, 2
+  %exitcond.i = icmp eq i16 %_tmp6.i, 2
+  %or.cond = and i1 %_tmp10.i, %exitcond.i
+  br i1 %or.cond, label %bb2, label %bb1.i
+}
+
+; CHECK-LABEL: Determining loop execution counts for: @test_and
+; CHECK-NEXT: Loop %bb1.i: backedge-taken count is (1 + (-1 * %in))
+; CHECK-NEXT: Loop %bb1.i: max backedge-taken count is -1
+; CHECK-NEXT: Loop %bb1.i: Predicated backedge-taken count is (1 + (-1 * %in))
+
+
+define void @test_or() {
+  %C10 = icmp slt i1 undef, undef
+  br i1 %C10, label %BB, label %exit
+
+BB:                                               ; preds = %BB, %0
+  %indvars.iv = phi i64 [ -1, %BB ], [ -1, %0 ]
+  %sum.01 = phi i32 [ %2, %BB ], [ undef, %0 ]
+  %1 = trunc i64 %indvars.iv to i32
+  %2 = add nsw i32 %1, %sum.01
+  %B3 = add i32 %1, %2
+  %C11 = icmp ult i32 %2, %1
+  %C5 = icmp sle i32 %1, %B3
+  %B = or i1 %C5, %C11
+  br i1 %B, label %BB, label %exit
+
+exit:                                      ; preds = %BB, %0
+  ret void
+}
+
+; CHECK-LABEL: Determining loop execution counts for: @test_or
+; CHECK-NEXT: Loop %BB: backedge-taken count is undef
+; CHECK-NEXT: Loop %BB: max backedge-taken count is -1
+; CHECK-NEXT: Loop %BB: Predicated backedge-taken count is undef

llvm/trunk/test/Transforms/IndVarSimplify/pr26207.ll

-; RUN: opt -S -indvars < %s | FileCheck %s
-
-target triple = "x86_64-unknown-linux-gnu"
-
-define void @main(i16 %in) {
-; CHECK-LABEL: @main(
-  br label %bb2
-
-bb2:                                              ; preds = %bb1.i, %bb2, %0
-  %_tmp44.i = icmp slt i16 %in, 2
-  br i1 %_tmp44.i, label %bb1.i, label %bb2
-
-bb1.i:                                            ; preds = %bb1.i, %bb2
-  %_tmp25.i = phi i16 [ %in, %bb2 ], [ %_tmp6.i, %bb1.i ]
-  %_tmp6.i = add nsw i16 %_tmp25.i, 1
-  %_tmp10.i = icmp sge i16 %_tmp6.i, 2
-  %exitcond.i = icmp eq i16 %_tmp6.i, 2
-  %or.cond = and i1 %_tmp10.i, %exitcond.i
-  br i1 %or.cond, label %bb2, label %bb1.i
-}