[SCEV] Consider guards in exit limit computation

[mkazantsev]

Summary

Current implementation of computeExitLimit only allows to use explicit
branch conditions to evaluate backedge taken count. This patch teaches
it to take guards conditions into account as well.

[mkazantsev]

Internal fuzzing testing found some failures, putting this on hold until they are investigated.

[mkazantsev]

It seems that this patch is OK, it just revealed some existing bug in IndVar simplifier: it fails to forget loops at some point.

[mkazantsev]

(Sorry, wrong patch)

lib/Analysis/ScalarEvolution.cpp

ScalarEvolution::computeBackedgeTakenCount(const Loop *L,
 
   SmallVector<EdgeExitInfo, 4> ExitCounts;
   bool CouldComputeBECount = true;
   BasicBlock *Latch = L->getLoopLatch(); // may be NULL.
   const SCEV *MustExitMaxBECount = nullptr;
   const SCEV *MayExitMaxBECount = nullptr;
   bool MustExitMaxOrZero = false;
 
-  // Compute the ExitLimit for each loop exit. Use this to populate ExitCounts
-  // and compute maxBECount.
-  // Do a union of all the predicates here.
-  for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
-    BasicBlock *ExitBB = ExitingBlocks[i];
-    ExitLimit EL = computeExitLimit(L, ExitBB, AllowPredicates);
-
+  auto ConsiderExitLimit = [&](BasicBlock *Block, ExitLimit &EL) {
     assert((AllowPredicates || EL.Predicates.empty()) &&
            "Predicated exit limit when predicates are not allowed!");
 
     // 1. For each exit that can be computed, add an entry to ExitCounts.
     // CouldComputeBECount is true only if all exits can be computed.
     if (EL.ExactNotTaken == getCouldNotCompute())
       // We couldn't compute an exact value for this exit, so
       // we won't be able to compute an exact value for the loop.
       CouldComputeBECount = false;
     else
-      ExitCounts.emplace_back(ExitBB, EL);
+      ExitCounts.emplace_back(Block, EL);
 
     // 2. Derive the loop's MaxBECount from each exit's max number of
     // non-exiting iterations. Partition the loop exits into two kinds:
     // LoopMustExits and LoopMayExits.
     //
     // If the exit dominates the loop latch, it is a LoopMustExit otherwise it
     // is a LoopMayExit.  If any computable LoopMustExit is found, then
     // MaxBECount is the minimum EL.MaxNotTaken of computable
     // LoopMustExits. Otherwise, MaxBECount is conservatively the maximum
     // EL.MaxNotTaken, where CouldNotCompute is considered greater than any
     // computable EL.MaxNotTaken.
     if (EL.MaxNotTaken != getCouldNotCompute() && Latch &&
-        DT.dominates(ExitBB, Latch)) {
+        DT.dominates(Block, Latch)) {
       if (!MustExitMaxBECount) {
         MustExitMaxBECount = EL.MaxNotTaken;
         MustExitMaxOrZero = EL.MaxOrZero;
       } else {
         MustExitMaxBECount =
             getUMinFromMismatchedTypes(MustExitMaxBECount, EL.MaxNotTaken);
       }
     } else if (MayExitMaxBECount != getCouldNotCompute()) {
       if (!MayExitMaxBECount || EL.MaxNotTaken == getCouldNotCompute())
         MayExitMaxBECount = EL.MaxNotTaken;
       else {
         MayExitMaxBECount =
             getUMaxFromMismatchedTypes(MayExitMaxBECount, EL.MaxNotTaken);
       }
     }
+  };
+
+  // Compute the ExitLimit for each loop exit. Use this to populate ExitCounts
+  // and compute maxBECount.
+  // Do a union of all the predicates here.
+  for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
+    BasicBlock *ExitBB = ExitingBlocks[i];
+    ExitLimit EL = computeExitLimit(L, ExitBB, AllowPredicates);
+    ConsiderExitLimit(ExitBB, EL);
+  }
+
+  if (HasGuards)
+    // If there are guards in the loop, use their conditions to have a more
+    // accurate estimation.
+    for (BasicBlock *BB : L->getBlocks())
+      for (Instruction &It : *BB) {
+        using namespace llvm::PatternMatch;
+        Value *Condition;
+        if (match(&It, m_Intrinsic<Intrinsic::experimental_guard>(
+                           m_Value(Condition)))) {
+          ExitLimit EL =
+              computeExitLimitFromCond(L, Condition, /*ExitByCond=*/false,
+                                       /*ControlsExit=*/false, AllowPredicates);
+          ConsiderExitLimit(BB, EL);
+        }
       }
+
   const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
     (MayExitMaxBECount ? MayExitMaxBECount : getCouldNotCompute());
   // The loop backedge will be taken the maximum or zero times if there's
   // a single exit that must be taken the maximum or zero times.
   bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
   return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
                            MaxBECount, MaxOrZero);
 }

test/Analysis/ScalarEvolution/exit_count_from_guards.ll

+; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+declare void @llvm.experimental.guard(i1, ...)
+
+; Exit by explicit branch when %iv = 91.
+define void @test_explicit_branch() {
+
+; CHECK-LABEL: Determining loop execution counts for: @test_explicit_branch
+; CHECK:       Loop %loop: <multiple exits> Unpredictable backedge-taken count.
+; CHECK:       Loop %loop: max backedge-taken count is 91
+; CHECK:       Loop %loop: Unpredictable predicated backedge-taken count.
+
+entry:
+  %iv.pre.lcmp = icmp sle i8 0, 100
+  br i1 %iv.pre.lcmp, label %loop, label %exit
+
+loop:
+  %iv = phi i8 [ 0, %entry ], [ %iv.inc, %loop.continue ]
+  %iv.gcmp = icmp sle i8 %iv, 90
+  br i1 %iv.gcmp, label %loop.continue, label %exceptional.exit
+
+loop.continue:
+  %iv.inc = add i8 %iv, 1
+  %iv.lcmp = icmp sle i8 %iv.inc, 100
+  br i1 %iv.lcmp, label %loop, label %exit
+
+exceptional.exit:
+  ret void
+
+exit:
+  ret void
+}
+
+; Exit by the only single guard when %iv = 91.
+define void @test_guard_01() {
+
+; CHECK-LABEL: Determining loop execution counts for: @test_guard_01
+; CHECK:       Loop %loop: Unpredictable backedge-taken count.
+; CHECK:       Loop %loop: max backedge-taken count is 91
+; CHECK:       Loop %loop: Unpredictable predicated backedge-taken count.
+
+entry:
+  %iv.pre.lcmp = icmp sle i8 0, 100
+  br i1 %iv.pre.lcmp, label %loop, label %exit
+
+loop:
+  %iv = phi i8 [ 0, %entry ], [ %iv.inc, %loop ]
+  %iv.gcmp = icmp sle i8 %iv, 90
+  call void(i1, ...) @llvm.experimental.guard(i1 %iv.gcmp) [ "deopt"() ]
+
+  %iv.inc = add i8 %iv, 1
+  %iv.lcmp = icmp sle i8 %iv.inc, 100
+  br i1 %iv.lcmp, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; Two guards that fail on %iv = 51 and 31, meaning that we exit when %iv = 31.
+define void @test_guard_02() {
+
+; CHECK-LABEL: Determining loop execution counts for: @test_guard_02
+; CHECK:       Loop %loop: Unpredictable backedge-taken count.
+; CHECK:       Loop %loop: max backedge-taken count is 31
+; CHECK:       Loop %loop: Unpredictable predicated backedge-taken count.
+
+entry:
+  %iv.pre.lcmp = icmp sle i8 0, 100
+  br i1 %iv.pre.lcmp, label %loop, label %exit
+
+loop:
+  %iv = phi i8 [ 0, %entry ], [ %iv.inc, %loop ]
+  %iv.gcmp1 = icmp sle i8 %iv, 50
+  %iv.gcmp2 = icmp sle i8 %iv, 30
+  call void(i1, ...) @llvm.experimental.guard(i1 %iv.gcmp1) [ "deopt"() ]
+  call void(i1, ...) @llvm.experimental.guard(i1 %iv.gcmp2) [ "deopt"() ]
+
+  %iv.inc = add i8 %iv, 1
+  %iv.lcmp = icmp sle i8 %iv.inc, 100
+  br i1 %iv.lcmp, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; Similar to test_guard_02, but now the conditions are joined via AND.
+define void @test_guard_03() {
+
+; CHECK-LABEL: Determining loop execution counts for: @test_guard_03
+; CHECK:       Loop %loop: Unpredictable backedge-taken count.
+; CHECK:       Loop %loop: max backedge-taken count is 31
+; CHECK:       Loop %loop: Unpredictable predicated backedge-taken count.
+
+entry:
+  %iv.pre.lcmp = icmp sle i8 0, 100
+  br i1 %iv.pre.lcmp, label %loop, label %exit
+
+loop:
+  %iv = phi i8 [ 0, %entry ], [ %iv.inc, %loop ]
+  %iv.gcmp1 = icmp sle i8 %iv, 50
+  %iv.gcmp2 = icmp sle i8 %iv, 30
+  %iv.gcmp = and i1 %iv.gcmp1, %iv.gcmp2
+  call void(i1, ...) @llvm.experimental.guard(i1 %iv.gcmp) [ "deopt"() ]
+
+  %iv.inc = add i8 %iv, 1
+  %iv.lcmp = icmp sle i8 %iv.inc, 100
+  br i1 %iv.lcmp, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; Guard fails on the first iteration.
+define void @test_guard_04() {
+
+; CHECK-LABEL: Determining loop execution counts for: @test_guard_04
+; CHECK:       Loop %loop: Unpredictable backedge-taken count.
+; CHECK:       Loop %loop: max backedge-taken count is 0
+; CHECK:       Loop %loop: Unpredictable predicated backedge-taken count.
+
+entry:
+  %iv.pre.lcmp = icmp sle i8 0, 100
+  br i1 %iv.pre.lcmp, label %loop, label %exit
+
+loop:
+  %iv = phi i8 [ 0, %entry ], [ %iv.inc, %loop ]
+  %iv.gcmp = icmp sge i8 %iv, 90
+  call void(i1, ...) @llvm.experimental.guard(i1 %iv.gcmp) [ "deopt"() ]
+
+  %iv.inc = add i8 %iv, 1
+  %iv.lcmp = icmp sle i8 %iv.inc, 100
+  br i1 %iv.lcmp, label %loop, label %exit
+
+exit:
+  ret void
+}

test/Analysis/ScalarEvolution/no-wrap-unknown-becount.ll

 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
   %iv.inc = add i32 %iv, 3
   %iv.zext = zext i32 %iv to i64
 ; CHECK:  %iv.zext = zext i32 %iv to i64
-; CHECK-NEXT:  -->  {0,+,3}<nuw><%loop>
+; CHECK-NEXT:  -->  {0,+,3}<nuw><nsw><%loop>
   %cmp = icmp ult i32 %iv, 10000
   call void(i1, ...) @llvm.experimental.guard(i1 %cmp) [ "deopt"() ]
   %c = load volatile i1, i1* %cond
   br i1 %c, label %loop, label %leave
 
 leave:
   ret void
 }