Index: lib/Analysis/ScalarEvolution.cpp =================================================================== --- lib/Analysis/ScalarEvolution.cpp +++ lib/Analysis/ScalarEvolution.cpp @@ -7026,9 +7026,27 @@ 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 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 ExitCounts; bool CouldComputeBECount = true; - BasicBlock *Latch = L->getLoopLatch(); // may be NULL. const SCEV *MustExitMaxBECount = nullptr; const SCEV *MayExitMaxBECount = nullptr; bool MustExitMaxOrZero = false; @@ -7038,10 +7056,37 @@ // 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]; - assert((AllowPredicates || EL.Predicates.empty()) && - "Predicated exit limit when predicates are not allowed!"); + // 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(FiniteUpperBound) && + !cast(FiniteUpperBound)->isAllOnesValue()) { + Instruction *Term = ExitBB->getTerminator(); + if (BranchInst *BI = dyn_cast(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); + } + } + } + // 1. For each exit that can be computed, add an entry to ExitCounts. // CouldComputeBECount is true only if all exits can be computed. Index: test/Analysis/ScalarEvolution/finite-exit-count.ll =================================================================== --- test/Analysis/ScalarEvolution/finite-exit-count.ll +++ test/Analysis/ScalarEvolution/finite-exit-count.ll @@ -0,0 +1,164 @@ +; 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: <> LoopDispositions: { %loop: Computable } +; CHECK-NEXT: %iv.next = add i32 %iv, 1 +; CHECK-NEXT: --> {1,+,1}<%loop> U: full-set S: full-set Exits: <> 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: 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))) 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)))) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: Determining loop execution counts for: @test1 +; CHECK-NEXT: Loop %loop: backedge-taken count is (200 umin (201 * (zext i1 %c to i32))) +; CHECK-NEXT: exit count for loop: (201 * (zext i1 %c to i32)) +; 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))) +; 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))) 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)))) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: Determining loop execution counts for: @test2 +; CHECK-NEXT: Loop %loop: backedge-taken count is (200 umin (201 * (zext i1 (true + %c) to i32))) +; CHECK-NEXT: exit count for loop: (201 * (zext i1 (true + %c) to i32)) +; 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))) +; 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: 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: 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 +} +