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

1 files changed, 5 insertions, 5 deletions

diff --git a/include/llvm/CodeGen/MachineBranchProbabilityInfo.h b/include/llvm/CodeGen/MachineBranchProbabilityInfo.h
index 994e1eec23..e768874894 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;