Fix a quadratic algorithm in MachineBranchProbabilityInfo.

The getSumForBlock function was quadratic in the number of successors
because getSuccWeight would perform a linear search for an already known
iterator.

This patch was originally committed as r161460, but reverted again
because of assertion failures. Now that duplicate Machine CFG edges have
been eliminated, this works properly.

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

1 files changed, 6 insertions, 3 deletions

diff --git a/include/llvm/CodeGen/MachineBranchProbabilityInfo.h b/include/llvm/CodeGen/MachineBranchProbabilityInfo.h
index af4db7d6bd..12189ceb7f 100644
--- a/include/llvm/CodeGen/MachineBranchProbabilityInfo.h
+++ b/include/llvm/CodeGen/MachineBranchProbabilityInfo.h
@@ -16,14 +16,12 @@
 #define LLVM_CODEGEN_MACHINEBRANCHPROBABILITYINFO_H
 
 #include "llvm/Pass.h"
+#include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/Support/BranchProbability.h"
 #include <climits>
 
 namespace llvm {
 
-class raw_ostream;
-class MachineBasicBlock;
-
 class MachineBranchProbabilityInfo : public ImmutablePass {
   virtual void anchor();
 
@@ -52,6 +50,11 @@ public:
   uint32_t getEdgeWeight(const MachineBasicBlock *Src,
                          const MachineBasicBlock *Dst) const;
 
+  // Same thing, but using a const_succ_iterator from Src. This is faster when
+  // the iterator is already available.
+  uint32_t getEdgeWeight(const MachineBasicBlock *Src,
+                         MachineBasicBlock::const_succ_iterator 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.