Fix the API usage in loop probability heuristics. It was incorrectly

classifying many edges as exiting which were in fact not. These mainly
formed edges into sub-loops. It was also not correctly classifying all
returning edges out of loops as leaving the loop. With this match most
of the loop heuristics are more rational.

Several serious regressions on loop-intesive benchmarks like perlbench's
loop tests when built with -enable-block-placement are fixed by these
updated heuristics. Unfortunately they in turn uncover some other
regressions. There are still several improvemenst that should be made to
loop heuristics including trip-count, and early back-edge management.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142917 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 8 insertions, 15 deletions

diff --git a/lib/Analysis/BranchProbabilityInfo.cpp b/lib/Analysis/BranchProbabilityInfo.cpp
index 0396f99f12..258fe54bee 100644
--- a/lib/Analysis/BranchProbabilityInfo.cpp
+++ b/lib/Analysis/BranchProbabilityInfo.cpp
@@ -216,8 +216,6 @@ bool BranchProbabilityInfo::calcPointerHeuristics(BasicBlock *BB) {
 // Calculate Edge Weights using "Loop Branch Heuristics". Predict backedges
 // as taken, exiting edges as not-taken.
 bool BranchProbabilityInfo::calcLoopBranchHeuristics(BasicBlock *BB) {
-  uint32_t numSuccs = BB->getTerminator()->getNumSuccessors();
-
   Loop *L = LI->getLoopFor(BB);
   if (!L)
     return false;
@@ -226,17 +224,13 @@ bool BranchProbabilityInfo::calcLoopBranchHeuristics(BasicBlock *BB) {
   SmallPtrSet<BasicBlock *, 8> ExitingEdges;
   SmallPtrSet<BasicBlock *, 8> InEdges; // Edges from header to the loop.
 
-  bool isHeader = BB == L->getHeader();
-
   for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
-    BasicBlock *Succ = *I;
-    Loop *SuccL = LI->getLoopFor(Succ);
-    if (SuccL != L)
-      ExitingEdges.insert(Succ);
-    else if (Succ == L->getHeader())
-      BackEdges.insert(Succ);
-    else if (isHeader)
-      InEdges.insert(Succ);
+    if (!L->contains(*I))
+      ExitingEdges.insert(*I);
+    else if (L->getHeader() == *I)
+      BackEdges.insert(*I);
+    else
+      InEdges.insert(*I);
   }
 
   if (uint32_t numBackEdges = BackEdges.size()) {
@@ -263,9 +257,8 @@ bool BranchProbabilityInfo::calcLoopBranchHeuristics(BasicBlock *BB) {
     }
   }
 
-  uint32_t numExitingEdges = ExitingEdges.size();
-  if (uint32_t numNonExitingEdges = numSuccs - numExitingEdges) {
-    uint32_t exitWeight = LBH_NONTAKEN_WEIGHT / numNonExitingEdges;
+  if (uint32_t numExitingEdges = ExitingEdges.size()) {
+    uint32_t exitWeight = LBH_NONTAKEN_WEIGHT / numExitingEdges;
     if (exitWeight < MIN_WEIGHT)
       exitWeight = MIN_WEIGHT;