From 6bae2a57d5b7ef62ca950e62da2eaf01aeebfef9 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Mon, 20 Aug 2012 22:01:38 +0000 Subject: 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. llvm-svn: 162233 --- llvm/lib/CodeGen/MachineBasicBlock.cpp | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-) (limited to 'llvm/lib/CodeGen/MachineBasicBlock.cpp') diff --git a/llvm/lib/CodeGen/MachineBasicBlock.cpp b/llvm/lib/CodeGen/MachineBasicBlock.cpp index fa6b450..cf13dbd 100644 --- a/llvm/lib/CodeGen/MachineBasicBlock.cpp +++ b/llvm/lib/CodeGen/MachineBasicBlock.cpp @@ -942,12 +942,11 @@ MachineBasicBlock::findDebugLoc(instr_iterator MBBI) { /// getSuccWeight - Return weight of the edge from this block to MBB. /// -uint32_t MachineBasicBlock::getSuccWeight(const MachineBasicBlock *succ) const { +uint32_t MachineBasicBlock::getSuccWeight(const_succ_iterator Succ) const { if (Weights.empty()) return 0; - const_succ_iterator I = std::find(Successors.begin(), Successors.end(), succ); - return *getWeightIterator(I); + return *getWeightIterator(Succ); } /// getWeightIterator - Return wight iterator corresonding to the I successor -- cgit v1.1