PHINode::getBasicBlockIndex is O(n) in the number of inputs
to a PHI, avoid it in the common case where the BB occurs
in the same index for multiple phis. This speeds up CGP on
an insane testcase from 8.35 to 3.58s.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@96080 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Transforms/Utils/BreakCriticalEdges.cpp b/lib/Transforms/Utils/BreakCriticalEdges.cpp
index eb3e3b2..dac6013 100644
--- a/lib/Transforms/Utils/BreakCriticalEdges.cpp
+++ b/lib/Transforms/Utils/BreakCriticalEdges.cpp
@@ -179,7 +179,7 @@
// Create a new basic block, linking it into the CFG.
BasicBlock *NewBB = BasicBlock::Create(TI->getContext(),
TIBB->getName() + "." + DestBB->getName() + "_crit_edge");
- // Create our unconditional branch...
+ // Create our unconditional branch.
BranchInst::Create(DestBB, NewBB);
// Branch to the new block, breaking the edge.
@@ -193,12 +193,19 @@
// If there are any PHI nodes in DestBB, we need to update them so that they
// merge incoming values from NewBB instead of from TIBB.
//
+ unsigned BBIdx = 0;
for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) {
- PHINode *PN = cast<PHINode>(I);
// We no longer enter through TIBB, now we come in through NewBB. Revector
// exactly one entry in the PHI node that used to come from TIBB to come
// from NewBB.
- int BBIdx = PN->getBasicBlockIndex(TIBB);
+ PHINode *PN = cast<PHINode>(I);
+
+ // Reuse the previous value of BBIdx if it lines up. In cases where we have
+ // multiple phi nodes with *lots* of predecessors, this is a speed win
+ // because we don't have to scan the PHI looking for TIBB. This happens
+ // because the BB list of PHI nodes are usually in the same order.
+ if (PN->getIncomingBlock(BBIdx) != TIBB)
+ BBIdx = PN->getBasicBlockIndex(TIBB);
PN->setIncomingBlock(BBIdx, NewBB);
}