Index: llvm/lib/Analysis/ScalarEvolution.cpp =================================================================== --- llvm/lib/Analysis/ScalarEvolution.cpp +++ llvm/lib/Analysis/ScalarEvolution.cpp @@ -11540,11 +11540,87 @@ return !isa(getBackedgeTakenCount(L)); } +// TODO: factor this out to a common location in Analysis and common with the +// (slightly different) version in Transform/Utils/LoopUtils.hpp. +// TODO: If BPI is available, we should use it; There's lots of heuristics +// there for branches w/o explicit profiles. +Optional getLoopEstimatedExitCount(const Loop *L, + const BasicBlock *ExitBB, + const DominatorTree &DT) { + assert(L->contains(ExitBB) && L->isLoopExiting(ExitBB)); + + auto *Latch = L->getLoopLatch(); + if (!Latch || !DT.dominates(ExitBB, Latch)) + return None; + + auto *BR = dyn_cast(ExitBB->getTerminator()); + if (!BR) + return None; + + // To estimate the number of times the loop body was executed, we want to + // know the number of times the backedge was taken, vs. the number of times + // we exited the loop. + uint64_t ContinueWeight, ExitWeight; + if (!BR->extractProfMetadata(ContinueWeight, ExitWeight)) + return None; + + if (L->contains(BR->getSuccessor(1))) + std::swap(ContinueWeight, ExitWeight); + + // 0, 0 -> must be dead code, so the loop can't reach backedge + // N, 0 -> never taken + // 0, N -> always taken + if (!ContinueWeight && !ExitWeight) + return 0; + else if (!ContinueWeight) + return 0; + else if (!ExitWeight) + return UINT_MAX; + + // Divide the count of the backedge by the count of the edge exiting the loop, + // rounding to nearest. + return llvm::divideNearest(ContinueWeight, ExitWeight); +} + +Optional getLoopEstimatedExitCount(const Loop *L, + const DominatorTree &DT) { + + SmallVector ExitingBlocks; + L->getExitingBlocks(ExitingBlocks); + unsigned Result = UINT_MAX; + for (auto *ExitingBB : ExitingBlocks) { + auto OptTC = getLoopEstimatedExitCount(L, ExitingBB, DT); + if (!OptTC) + return None; + Result = std::min(Result, *OptTC); + } + return Result; +} + +Optional getLoopEstimatedMaxTripCount(const Loop *L, + const DominatorTree &DT) { + + SmallVector ExitingBlocks; + L->getExitingBlocks(ExitingBlocks); + bool SawOne = false; + unsigned Result = UINT_MAX; + for (auto *ExitingBB : ExitingBlocks) { + auto OptTC = getLoopEstimatedExitCount(L, ExitingBB, DT); + if (!OptTC) + continue; + SawOne = true; + Result = std::min(Result, *OptTC); + } + if (!SawOne) + return None; + return Result; +} + static void PrintLoopInfo(raw_ostream &OS, ScalarEvolution *SE, - const Loop *L) { + const Loop *L, const DominatorTree &DT) { // Print all inner loops first for (Loop *I : *L) - PrintLoopInfo(OS, SE, I); + PrintLoopInfo(OS, SE, I, DT); OS << "Loop "; L->getHeader()->printAsOperand(OS, /*PrintType=*/false); @@ -11556,14 +11632,20 @@ OS << " "; if (SE->hasLoopInvariantBackedgeTakenCount(L)) - OS << "backedge-taken count is " << *SE->getBackedgeTakenCount(L) << "\n"; + OS << "backedge-taken count is " << *SE->getBackedgeTakenCount(L); else - OS << "Unpredictable backedge-taken count.\n"; + OS << "Unpredictable backedge-taken count."; + if (auto OptEC = getLoopEstimatedExitCount(L, DT)) + OS << ", estimated: " << *OptEC; + OS << "\n"; if (ExitingBlocks.size() > 1) for (BasicBlock *ExitingBlock : ExitingBlocks) { OS << " exit count for " << ExitingBlock->getName() << ": " - << *SE->getExitCount(L, ExitingBlock) << "\n"; + << *SE->getExitCount(L, ExitingBlock); + if (auto OptEC = getLoopEstimatedExitCount(L, ExitingBlock, DT)) + OS << ", estimated: " << *OptEC; + OS << "\n"; } OS << "Loop "; @@ -11577,6 +11659,8 @@ } else { OS << "Unpredictable max backedge-taken count. "; } + if (auto OptEC = getLoopEstimatedMaxTripCount(L, DT)) + OS << ", estimated: " << *OptEC; OS << "\n" "Loop "; @@ -11701,7 +11785,7 @@ F.printAsOperand(OS, /*PrintType=*/false); OS << "\n"; for (Loop *I : LI) - PrintLoopInfo(OS, &SE, I); + PrintLoopInfo(OS, &SE, I, DT); } ScalarEvolution::LoopDisposition Index: llvm/test/Analysis/ScalarEvolution/trip-count.ll =================================================================== --- llvm/test/Analysis/ScalarEvolution/trip-count.ll +++ llvm/test/Analysis/ScalarEvolution/trip-count.ll @@ -121,3 +121,80 @@ leave: ret void } + + +define void @basic_estimate(i32 %n) { +; CHECK-LABEL: 'basic_estimate' +; CHECK-NEXT: Determining loop execution counts for: @basic_estimate +; CHECK-NEXT: Loop %loop: backedge-taken count is 19, estimated: 19 +; CHECK-NEXT: Loop %loop: max backedge-taken count is 19, estimated: 19 +; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is 19 +; CHECK-NEXT: Predicates: +; CHECK: Loop %loop: Trip multiple is 20 +; +entry: + br label %loop + +loop: + %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ] + %iv.inc = add nsw i32 %iv, 1 + call void @may_exit() + %becond = icmp ne i32 %iv.inc, 20 + br i1 %becond, label %loop, label %leave, !prof !{!"branch_weights", i32 19, i32 1} + +leave: + ret void +} + +define void @basic_estimate_swapped(i32 %n) { +; CHECK-LABEL: 'basic_estimate_swapped' +; CHECK-NEXT: Determining loop execution counts for: @basic_estimate_swapped +; CHECK-NEXT: Loop %loop: backedge-taken count is 19, estimated: 19 +; CHECK-NEXT: Loop %loop: max backedge-taken count is 19, estimated: 19 +; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is 19 +; CHECK-NEXT: Predicates: +; CHECK: Loop %loop: Trip multiple is 20 +; +entry: + br label %loop + +loop: + %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ] + %iv.inc = add nsw i32 %iv, 1 + call void @may_exit() + %becond = icmp eq i32 %iv.inc, 20 + br i1 %becond, label %leave, label %loop, !prof !{!"branch_weights", i32 2, i32 38} + +leave: + ret void +} + +define void @estimate_unknown(i1* %addr) { +; CHECK-LABEL: 'estimate_unknown' +; CHECK-NEXT: Determining loop execution counts for: @estimate_unknown +; CHECK-NEXT: Loop %loop: Unpredictable backedge-taken count., estimated: 19 +; CHECK-NEXT: exit count for loop: 19, estimated: 19 +; CHECK-NEXT: exit count for latch: ***COULDNOTCOMPUTE***, estimated: 4294967295 +; CHECK-NEXT: Loop %loop: max backedge-taken count is 19, estimated: 19 +; CHECK-NEXT: Loop %loop: Unpredictable predicated backedge-taken count. +; +entry: + br label %loop + +loop: + %iv = phi i32 [ 0, %entry ], [ %iv.inc, %latch ] + %iv.inc = add nsw i32 %iv, 1 + call void @may_exit() + %becond = icmp ne i32 %iv.inc, 20 + br i1 %becond, label %latch, label %leave, !prof !{!"branch_weights", i32 19, i32 1} + +latch: + %unknown = load i1, i1* %addr + br i1 %unknown, label %loop, label %leave, !prof !{!"branch_weights", i32 19, i32 0} + +leave: + ret void +} + + +