From 340d596509129de8c3fa9dbe4184a2b148b78757 Mon Sep 17 00:00:00 2001
From: Chandler Carruth <chandlerc@gmail.com>
Date: Mon, 14 Nov 2011 09:12:57 +0000
Subject: [PATCH] Under the hood, MBPI is doing a linear scan of every
 successor every time it is queried to compute the probability of a single
 successor. This makes computing the probability of every successor of a block
 in sequence... really really slow. ;] This switches to a linear walk of the
 successors rather than a quadratic one. One of several quadratic behaviors
 slowing this pass down.

I'm not really thrilled with moving the sum code into the public
interface of MBPI, but I don't (at the moment) have ideas for a better
interface. My direction I'm thinking in for a better interface is to
have MBPI actually retain much more state and make *all* of these
queries cheap. That's a lot of work, and would require invasive changes.
Until then, this seems like the least bad (ie, least quadratic)
solution. Suggestions welcome.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@144530 91177308-0d34-0410-b5e6-96231b3b80d8
---
 .../llvm/CodeGen/MachineBranchProbabilityInfo.h | 10 +++++-----
 lib/CodeGen/MachineBlockPlacement.cpp           | 17 +++++++++++++----
 2 files changed, 18 insertions(+), 9 deletions(-)

diff --git a/include/llvm/CodeGen/MachineBranchProbabilityInfo.h b/include/llvm/CodeGen/MachineBranchProbabilityInfo.h
index 994e1eec232..e7688748945 100644
--- a/include/llvm/CodeGen/MachineBranchProbabilityInfo.h
+++ b/include/llvm/CodeGen/MachineBranchProbabilityInfo.h
@@ -34,11 +34,6 @@ class MachineBranchProbabilityInfo : public ImmutablePass {
   // weight to just "inherit" the non-zero weight of an adjacent successor.
   static const uint32_t DEFAULT_WEIGHT = 16;
 
-  // Get sum of the block successors' weights, potentially scaling them to fit
-  // within 32-bits. If scaling is required, sets Scale based on the necessary
-  // adjustment. Any edge weights used with the sum should be divided by Scale.
-  uint32_t getSumForBlock(MachineBasicBlock *MBB, uint32_t &Scale) const;
-
 public:
   static char ID;
 
@@ -55,6 +50,11 @@ public:
   // DEFAULT_WEIGHT.
   uint32_t getEdgeWeight(MachineBasicBlock *Src, MachineBasicBlock *Dst) const;
 
+  // Get sum of the block successors' weights, potentially scaling them to fit
+  // within 32-bits. If scaling is required, sets Scale based on the necessary
+  // adjustment. Any edge weights used with the sum should be divided by Scale.
+  uint32_t getSumForBlock(MachineBasicBlock *MBB, uint32_t &Scale) const;
+
   // A 'Hot' edge is an edge which probability is >= 80%.
   bool isEdgeHot(MachineBasicBlock *Src, MachineBasicBlock *Dst) const;
 
diff --git a/lib/CodeGen/MachineBlockPlacement.cpp b/lib/CodeGen/MachineBlockPlacement.cpp
index ca17ad07e44..bd50ac3a4d5 100644
--- a/lib/CodeGen/MachineBlockPlacement.cpp
+++ b/lib/CodeGen/MachineBlockPlacement.cpp
@@ -334,7 +334,15 @@ MachineBasicBlock *MachineBlockPlacement::selectBestSuccessor(
   const BranchProbability HotProb(4, 5); // 80%
 
   MachineBasicBlock *BestSucc = 0;
-  BranchProbability BestProb = BranchProbability::getZero();
+  // FIXME: Due to the performance of the probability and weight routines in
+  // the MBPI analysis, we manually compute probabilities using the edge
+  // weights. This is suboptimal as it means that the somewhat subtle
+  // definition of edge weight semantics is encoded here as well. We should
+  // improve the MBPI interface to effeciently support query patterns such as
+  // this.
+  uint32_t BestWeight = 0;
+  uint32_t WeightScale = 0;
+  uint32_t SumWeight = MBPI->getSumForBlock(BB, WeightScale);
   DEBUG(dbgs() << "Attempting merge from: " << getBlockName(BB) << "\n");
   for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(),
                                         SE = BB->succ_end();
@@ -347,7 +355,8 @@ MachineBasicBlock *MachineBlockPlacement::selectBestSuccessor(
       continue;
     }
 
-    BranchProbability SuccProb = MBPI->getEdgeProbability(BB, *SI);
+    uint32_t SuccWeight = MBPI->getEdgeWeight(BB, *SI);
+    BranchProbability SuccProb(SuccWeight / WeightScale, SumWeight);
 
     // Only consider successors which are either "hot", or wouldn't violate
     // any CFG constraints.
@@ -360,10 +369,10 @@ MachineBasicBlock *MachineBlockPlacement::selectBestSuccessor(
                  << " (prob)"
                  << (SuccChain.LoopPredecessors != 0 ? " (CFG break)" : "")
                  << "\n");
-    if (BestSucc && BestProb >= SuccProb)
+    if (BestSucc && BestWeight >= SuccWeight)
       continue;
     BestSucc = *SI;
-    BestProb = SuccProb;
+    BestWeight = SuccWeight;
   }
   return BestSucc;
 }
-- 
2.34.1