[POC][SCEV] Bounds for loop invariant exits

[reames]

Summary

I noticed in one of the test updates for rL368898 that we hadn't been able to compute a backedge taken count for a loop with a constant exit. This seems unfortunate, so I took a stab at a solution.

At the moment, this isn't ready to go in, I'm mostly looking for feedback on the idea and approach. Is this a good idea? Should I restrict it to only constants? Should this be done somewhere else?

One point I'm a bit concerned about is whether setting the exact count to an arbitrary unreachable value breaks some assumption. I can't think of any, but...

If this is the direction we want to take, I'll do the following:

• Autogen a couple of tests which need updated
• Submit an NFC which computes the max BE taken count in a pre-loop to the main one which tracks computable exits.
• Rebase this on top of both of the above for actual review.

[reames]

Abandoning an old review I'm not going to return to any time soon.

lib/Analysis/ScalarEvolution.cpp

 ScalarEvolution::BackedgeTakenInfo
 ScalarEvolution::computeBackedgeTakenCount(const Loop *L,
                                            bool AllowPredicates) {
   SmallVector<BasicBlock *, 8> ExitingBlocks;
   L->getExitingBlocks(ExitingBlocks);
 
   using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
 
+  BasicBlock *Latch = L->getLoopLatch(); // may be NULL.
+
+  // First, gather all of the computable loop exits, and figure out whether the
+  // loop is known to be finite.
+  SmallVector<ExitLimit, 4> ExitLimits;
+  ExitLimits.reserve(ExitingBlocks.size());
+  const SCEV *FiniteUpperBound = nullptr;
+  for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
+    BasicBlock *ExitBB = ExitingBlocks[i];
+    ExitLimit EL = computeExitLimit(L, ExitBB, AllowPredicates);
+    assert((AllowPredicates || EL.Predicates.empty()) &&
+           "Predicated exit limit when predicates are not allowed!");
+    ExitLimits.push_back(EL);
+    if (!FiniteUpperBound && EL.MaxNotTaken != getCouldNotCompute() &&
+        Latch && DT.dominates(ExitBB, Latch))
+      FiniteUpperBound = EL.MaxNotTaken;
+  }
+
+  
   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);
+    ExitLimit EL = ExitLimits[i];
+
+    // If we have a loop invariant exit condition in a finite loop, improve the
+    // exit count using the information that the loop is finite.
+    if (EL.ExactNotTaken == getCouldNotCompute() &&
+        Latch && DT.dominates(ExitBB, Latch) &&
+        FiniteUpperBound && isa<SCEVConstant>(FiniteUpperBound) &&
+        !cast<SCEVConstant>(FiniteUpperBound)->isAllOnesValue()) {
+      Instruction *Term = ExitBB->getTerminator();
+      if (BranchInst *BI = dyn_cast<BranchInst>(Term)) {
+        assert(BI->isConditional() && "If unconditional, it can't be in loop!");
+        bool ExitIfTrue = !L->contains(BI->getSuccessor(0));
+        assert(ExitIfTrue == L->contains(BI->getSuccessor(1)) &&
+               "It should have one successor in loop and one exit block!");
+        const SCEV *Cond = getSCEV(BI->getCondition());
+        if (isLoopInvariant(Cond, L)) {
+          // If we know that this exit is never taken, then the value of the
+          // exit count matters only in that it's greater than the actual exit
+          // count for the loop.  Thus, we generate what is essentially a
+          // loop invariant select between zero, and a value known to be
+          // greater than the actual exit count.
+          const SCEV *ZeroOrOne =
+            getNoopOrZeroExtend(ExitIfTrue ? getNotSCEV(Cond) : Cond,
+                                FiniteUpperBound->getType());
+          const SCEV *AboveBE =
+            getAddExpr(FiniteUpperBound, getOne(FiniteUpperBound->getType()));
+          EL.ExactNotTaken = getMulExpr(ZeroOrOne, AboveBE); 
+        }
+      }
+    }
     
-    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

test/Analysis/ScalarEvolution/finite-exit-count.ll

+; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
+; RUN: opt -analyze -scalar-evolution %s | FileCheck %s
+
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @test_neg1(i1 %c) {
+; CHECK-LABEL: 'test_neg1'
+; CHECK-NEXT:  Classifying expressions for: @test_neg1
+; CHECK-NEXT:    %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
+; CHECK-NEXT:    --> {0,+,1}<%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %iv.next = add i32 %iv, 1
+; CHECK-NEXT:    --> {1,+,1}<%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:  Determining loop execution counts for: @test_neg1
+; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
+; CHECK-NEXT:  Loop %loop: Unpredictable max backedge-taken count.
+; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
+;
+entry:
+  br label %loop
+loop:
+  %iv = phi i32 [0, %entry], [%iv.next, %loop]
+  %iv.next = add i32 %iv, 1
+  br i1 %c, label %loop, label %exit
+exit:
+  ret void
+}
+
+define void @test_neg2(i1 %c, i1 %c2) {
+; CHECK-LABEL: 'test_neg2'
+; CHECK-NEXT:  Classifying expressions for: @test_neg2
+; CHECK-NEXT:  Determining loop execution counts for: @test_neg2
+; CHECK-NEXT:  Loop %loop: <multiple exits> Unpredictable backedge-taken count.
+; CHECK-NEXT:    exit count for loop: ***COULDNOTCOMPUTE***
+; CHECK-NEXT:    exit count for backedge: ***COULDNOTCOMPUTE***
+; CHECK-NEXT:  Loop %loop: Unpredictable max backedge-taken count.
+; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
+;
+entry:
+  br label %loop
+loop:
+  br i1 %c, label %backedge, label %exit
+backedge:
+  br i1 %c2, label %loop, label %exit
+exit:
+  ret void
+}
+
+
+define void @test1(i1 %c) {
+; CHECK-LABEL: 'test1'
+; CHECK-NEXT:  Classifying expressions for: @test1
+; CHECK-NEXT:    %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
+; CHECK-NEXT:    --> {0,+,1}<%loop> U: [0,201) S: [0,201) Exits: (200 umin (201 * (zext i1 %c to i32))<nuw><nsw>) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %iv.next = add i32 %iv, 1
+; CHECK-NEXT:    --> {1,+,1}<%loop> U: [1,202) S: [1,202) Exits: (1 + (200 umin (201 * (zext i1 %c to i32))<nuw><nsw>)) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:  Determining loop execution counts for: @test1
+; CHECK-NEXT:  Loop %loop: <multiple exits> backedge-taken count is (200 umin (201 * (zext i1 %c to i32))<nuw><nsw>)
+; CHECK-NEXT:    exit count for loop: (201 * (zext i1 %c to i32))<nuw><nsw>
+; CHECK-NEXT:    exit count for backedge: 200
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is 200
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (200 umin (201 * (zext i1 %c to i32))<nuw><nsw>)
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %loop: Trip multiple is 0
+;
+entry:
+  br label %loop
+loop:
+  %iv = phi i32 [0, %entry], [%iv.next, %backedge]
+  %iv.next = add i32 %iv, 1
+  br i1 %c, label %backedge, label %exit
+backedge:
+  %cmp = icmp slt i32 %iv, 200
+  br i1 %cmp, label %loop, label %exit
+exit:
+  ret void
+}
+
+define void @test2(i1 %c) {
+; CHECK-LABEL: 'test2'
+; CHECK-NEXT:  Classifying expressions for: @test2
+; CHECK-NEXT:    %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
+; CHECK-NEXT:    --> {0,+,1}<%loop> U: [0,201) S: [0,201) Exits: (200 umin (201 * (zext i1 (true + %c) to i32))<nuw><nsw>) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %iv.next = add i32 %iv, 1
+; CHECK-NEXT:    --> {1,+,1}<%loop> U: [1,202) S: [1,202) Exits: (1 + (200 umin (201 * (zext i1 (true + %c) to i32))<nuw><nsw>)) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:  Determining loop execution counts for: @test2
+; CHECK-NEXT:  Loop %loop: <multiple exits> backedge-taken count is (200 umin (201 * (zext i1 (true + %c) to i32))<nuw><nsw>)
+; CHECK-NEXT:    exit count for loop: (201 * (zext i1 (true + %c) to i32))<nuw><nsw>
+; CHECK-NEXT:    exit count for backedge: 200
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is 200
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (200 umin (201 * (zext i1 (true + %c) to i32))<nuw><nsw>)
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %loop: Trip multiple is 0
+;
+entry:
+  br label %loop
+loop:
+  %iv = phi i32 [0, %entry], [%iv.next, %backedge]
+  %iv.next = add i32 %iv, 1
+  br i1 %c, label %exit, label %backedge
+backedge:
+  %cmp = icmp slt i32 %iv, 200
+  br i1 %cmp, label %loop, label %exit
+exit:
+  ret void
+}
+
+define void @test3() {
+; CHECK-LABEL: 'test3'
+; CHECK-NEXT:  Classifying expressions for: @test3
+; CHECK-NEXT:    %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
+; CHECK-NEXT:    --> {0,+,1}<%loop> U: [0,201) S: [0,201) Exits: 200 LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %iv.next = add i32 %iv, 1
+; CHECK-NEXT:    --> {1,+,1}<%loop> U: [1,202) S: [1,202) Exits: 201 LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:  Determining loop execution counts for: @test3
+; CHECK-NEXT:  Loop %loop: <multiple exits> backedge-taken count is 200
+; CHECK-NEXT:    exit count for loop: 201
+; CHECK-NEXT:    exit count for backedge: 200
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is 200
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 200
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %loop: Trip multiple is 0
+;
+entry:
+  br label %loop
+loop:
+  %iv = phi i32 [0, %entry], [%iv.next, %backedge]
+  %iv.next = add i32 %iv, 1
+  br i1 false, label %exit, label %backedge
+backedge:
+  %cmp = icmp slt i32 %iv, 200
+  br i1 %cmp, label %loop, label %exit
+exit:
+  ret void
+}
+
+define void @test4() {
+; CHECK-LABEL: 'test4'
+; CHECK-NEXT:  Classifying expressions for: @test4
+; CHECK-NEXT:    %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
+; CHECK-NEXT:    --> {0,+,1}<%loop> U: [0,1) S: [0,1) Exits: 0 LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %iv.next = add i32 %iv, 1
+; CHECK-NEXT:    --> {1,+,1}<%loop> U: [1,2) S: [1,2) Exits: 1 LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:  Determining loop execution counts for: @test4
+; CHECK-NEXT:  Loop %loop: <multiple exits> backedge-taken count is 0
+; CHECK-NEXT:    exit count for loop: false
+; CHECK-NEXT:    exit count for backedge: 200
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is 0
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 0
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %loop: Trip multiple is 0
+;
+entry:
+  br label %loop
+loop:
+  %iv = phi i32 [0, %entry], [%iv.next, %backedge]
+  %iv.next = add i32 %iv, 1
+  br i1 true, label %exit, label %backedge
+backedge:
+  %cmp = icmp slt i32 %iv, 200
+  br i1 %cmp, label %loop, label %exit
+exit:
+  ret void
+}
+