In SCEV's printer pass, print an estimate of the exit count for each exit from profiling information

[reames]

Summary

This is geared at being a debugging aid. When analysing IR, it's common to have large complicated loops with multiple exits and profiling data which indicates which exit is actually taken. When looking to see if there's a problem in SCEV's exit count logic, it really helps to be able to quickly see which exits are probably dead in practice. These are frequently - though not always - good places to examine further.

For the moment, the implementation of the estimated exit count stuff is SCEV specific. There's a version of something analogous in getEstimatedTripCount but a) trip count != exit count, and b) this needs to handle multiple exit loops, and c) I want to be able switch consumes over one by one to minimize breakage. My plan is to land this, move the impl into a common analysis header, then visit each one by one.

[nikic]

llvm/test/Analysis/ScalarEvolution/trip-count.ll

143

Why are the branch weights here 20/1 and not 19/1 (and relatedly, why do we need to subtract -1 in the exit count calculation)?

[reames]

llvm/test/Analysis/ScalarEvolution/trip-count.ll

143

Because I made a mental off by one error, and then made everything else consistent with that mistake. Oops. :)

I was thinking in iterations not backedges taken. Despite the comments which say the opposite.

Thanks for catching that!

[reames]

Fix off by one bug pointed out in review.

[nikic]

What you're doing here is right for a single exit, but I don't think it holds up for multiple exits. Talking in terms of probabilities, you are given P(E_i | not E_{i-1}), where E_i is the event that exit i is taken. The non-conditional exit probability is P(E_i) = P(E_i | not E_{i-1}) / P(not E_{i-1}). The predicted exit count is (1 / P(E_i)) - 1.

To get accurate exit counts, you'd have to walk down the chain of (dominating) exits and adjust probabilities/weights as you go along.

Am I overthinking things?

[reames]

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

llvm/lib/Analysis/ScalarEvolution.cpp

ScalarEvolution::~ScalarEvolution() {
   assert(!WalkingBEDominatingConds && "isLoopBackedgeGuardedByCond garbage!");
   assert(!ProvingSplitPredicate && "ProvingSplitPredicate garbage!");
 }
 
 bool ScalarEvolution::hasLoopInvariantBackedgeTakenCount(const Loop *L) {
   return !isa<SCEVCouldNotCompute>(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<unsigned> 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<BranchInst>(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<unsigned> getLoopEstimatedExitCount(const Loop *L,
+                                             const DominatorTree &DT) {
+
+  SmallVector<BasicBlock *, 4> 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<unsigned> getLoopEstimatedMaxTripCount(const Loop *L,
+                                                const DominatorTree &DT) {
+
+  SmallVector<BasicBlock *, 4> 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);
   OS << ": ";
 
   SmallVector<BasicBlock *, 8> ExitingBlocks;
   L->getExitingBlocks(ExitingBlocks);
   if (ExitingBlocks.size() != 1)
     OS << "<multiple exits> ";
 
   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 ";
   L->getHeader()->printAsOperand(OS, /*PrintType=*/false);
   OS << ": ";
 
   if (!isa<SCEVCouldNotCompute>(SE->getConstantMaxBackedgeTakenCount(L))) {
     OS << "max backedge-taken count is " << *SE->getConstantMaxBackedgeTakenCount(L);
     if (SE->isBackedgeTakenCountMaxOrZero(L))
       OS << ", actual taken count either this or zero.";
   } else {
     OS << "Unpredictable max backedge-taken count. ";
   }
+  if (auto OptEC = getLoopEstimatedMaxTripCount(L, DT))
+    OS << ", estimated: " << *OptEC;
 
   OS << "\n"
         "Loop ";
   L->getHeader()->printAsOperand(OS, /*PrintType=*/false);
   OS << ": ";
 
   SCEVUnionPredicate Pred;
   auto PBT = SE->getPredicatedBackedgeTakenCount(L, Pred);
for (Instruction &I : instructions(F))
         OS << "\n";
       }
   }
 
   OS << "Determining loop execution counts for: ";
   F.printAsOperand(OS, /*PrintType=*/false);
   OS << "\n";
   for (Loop *I : LI)
-    PrintLoopInfo(OS, &SE, I);
+    PrintLoopInfo(OS, &SE, I, DT);
 }
 
 ScalarEvolution::LoopDisposition
 ScalarEvolution::getLoopDisposition(const SCEV *S, const Loop *L) {
   auto &Values = LoopDispositions[S];
   for (auto &V : Values) {
     if (V.getPointer() == L)
       return V.getInt();

llvm/test/Analysis/ScalarEvolution/trip-count.ll

loop:
   %iv.inc = add nsw i32 %iv, 3
   call void @may_exit()
   %becond = icmp ne i32 %iv.inc, 46
   br i1 %becond, label %loop, label %leave
 
 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: <multiple exits> 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
+}
+
+
+