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 eb3e3b2ff3a7467aa3932c2800f48ab4ce660027..dac60131c3f16bc5acf32e380158d09676f84d9b 100644 (file)
--- a/lib/Transforms/Utils/BreakCriticalEdges.cpp
+++ b/lib/Transforms/Utils/BreakCriticalEdges.cpp
@@ -179,7 +179,7 @@ BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum,
   // 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 @@ BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum,
   // 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);
   }