diff options
author | Chris Lattner <sabre@nondot.org> | 2010-02-13 05:35:08 +0000 |
---|---|---|
committer | Chris Lattner <sabre@nondot.org> | 2010-02-13 05:35:08 +0000 |
commit | 98d5c3141eddc84a8bcf7db57332967695585e42 (patch) | |
tree | d62f4cb77ec83676ced166081a11e82dc401c1fb | |
parent | 6686c6bf68148190309451aa9a79d2efd38ce698 (diff) | |
download | external_llvm-98d5c3141eddc84a8bcf7db57332967695585e42.zip external_llvm-98d5c3141eddc84a8bcf7db57332967695585e42.tar.gz external_llvm-98d5c3141eddc84a8bcf7db57332967695585e42.tar.bz2 |
Split some code out to a helper function (FindReusablePredBB)
and add a doxygen comment.
Cache the phi entry to avoid doing tons of
PHINode::getBasicBlockIndex calls in the common case.
On my insane testcase from re2c, this speeds up CGP from
617.4s to 7.9s (78x).
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@96083 91177308-0d34-0410-b5e6-96231b3b80d8
-rw-r--r-- | lib/Transforms/Scalar/CodeGenPrepare.cpp | 122 |
1 files changed, 72 insertions, 50 deletions
diff --git a/lib/Transforms/Scalar/CodeGenPrepare.cpp b/lib/Transforms/Scalar/CodeGenPrepare.cpp index fedd0ba..6e01ed4 100644 --- a/lib/Transforms/Scalar/CodeGenPrepare.cpp +++ b/lib/Transforms/Scalar/CodeGenPrepare.cpp @@ -301,6 +301,70 @@ void CodeGenPrepare::EliminateMostlyEmptyBlock(BasicBlock *BB) { DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n"); } +/// FindReusablePredBB - Check all of the predecessors of the block DestPHI +/// lives in to see if there is a block that we can reuse as a critical edge +/// from TIBB. +static BasicBlock *FindReusablePredBB(PHINode *DestPHI, BasicBlock *TIBB) { + BasicBlock *Dest = DestPHI->getParent(); + + /// TIPHIValues - This array is lazily computed to determine the values of + /// PHIs in Dest that TI would provide. + SmallVector<Value*, 32> TIPHIValues; + + /// TIBBEntryNo - This is a cache to speed up pred queries for TIBB. + unsigned TIBBEntryNo = 0; + + // Check to see if Dest has any blocks that can be used as a split edge for + // this terminator. + for (unsigned pi = 0, e = DestPHI->getNumIncomingValues(); pi != e; ++pi) { + BasicBlock *Pred = DestPHI->getIncomingBlock(pi); + // To be usable, the pred has to end with an uncond branch to the dest. + BranchInst *PredBr = dyn_cast<BranchInst>(Pred->getTerminator()); + if (!PredBr || !PredBr->isUnconditional()) + continue; + // Must be empty other than the branch and debug info. + BasicBlock::iterator I = Pred->begin(); + while (isa<DbgInfoIntrinsic>(I)) + I++; + if (&*I != PredBr) + continue; + // Cannot be the entry block; its label does not get emitted. + if (Pred == &Dest->getParent()->getEntryBlock()) + continue; + + // Finally, since we know that Dest has phi nodes in it, we have to make + // sure that jumping to Pred will have the same effect as going to Dest in + // terms of PHI values. + PHINode *PN; + unsigned PHINo = 0; + unsigned PredEntryNo = pi; + + bool FoundMatch = true; + for (BasicBlock::iterator I = Dest->begin(); + (PN = dyn_cast<PHINode>(I)); ++I, ++PHINo) { + if (PHINo == TIPHIValues.size()) { + if (PN->getIncomingBlock(TIBBEntryNo) != TIBB) + TIBBEntryNo = PN->getBasicBlockIndex(TIBB); + TIPHIValues.push_back(PN->getIncomingValue(TIBBEntryNo)); + } + + // If the PHI entry doesn't work, we can't use this pred. + if (PN->getIncomingBlock(PredEntryNo) != Pred) + PredEntryNo = PN->getBasicBlockIndex(Pred); + + if (TIPHIValues[PHINo] != PN->getIncomingValue(PredEntryNo)) { + FoundMatch = false; + break; + } + } + + // If we found a workable predecessor, change TI to branch to Succ. + if (FoundMatch) + return Pred; + } + return 0; +} + /// SplitEdgeNicely - Split the critical edge from TI to its specified /// successor if it will improve codegen. We only do this if the successor has @@ -329,57 +393,15 @@ static void SplitEdgeNicely(TerminatorInst *TI, unsigned SuccNum, return; if (!FactorCommonPreds) { - /// TIPHIValues - This array is lazily computed to determine the values of - /// PHIs in Dest that TI would provide. - SmallVector<Value*, 32> TIPHIValues; - - // Check to see if Dest has any blocks that can be used as a split edge for - // this terminator. - for (unsigned pi = 0, e = DestPHI->getNumIncomingValues(); pi != e; ++pi) { - BasicBlock *Pred = DestPHI->getIncomingBlock(pi); - // To be usable, the pred has to end with an uncond branch to the dest. - BranchInst *PredBr = dyn_cast<BranchInst>(Pred->getTerminator()); - if (!PredBr || !PredBr->isUnconditional()) - continue; - // Must be empty other than the branch and debug info. - BasicBlock::iterator I = Pred->begin(); - while (isa<DbgInfoIntrinsic>(I)) - I++; - if (&*I != PredBr) - continue; - // Cannot be the entry block; its label does not get emitted. - if (Pred == &Dest->getParent()->getEntryBlock()) - continue; - - // Finally, since we know that Dest has phi nodes in it, we have to make - // sure that jumping to Pred will have the same effect as going to Dest in - // terms of PHI values. - PHINode *PN; - unsigned PHINo = 0; - bool FoundMatch = true; - for (BasicBlock::iterator I = Dest->begin(); - (PN = dyn_cast<PHINode>(I)); ++I, ++PHINo) { - if (PHINo == TIPHIValues.size()) - TIPHIValues.push_back(PN->getIncomingValueForBlock(TIBB)); - - // If the PHI entry doesn't work, we can't use this pred. - if (TIPHIValues[PHINo] != PN->getIncomingValueForBlock(Pred)) { - FoundMatch = false; - break; - } - } - - // If we found a workable predecessor, change TI to branch to Succ. - if (FoundMatch) { - ProfileInfo *PFI = P->getAnalysisIfAvailable<ProfileInfo>(); - if (PFI) - PFI->splitEdge(TIBB, Dest, Pred); - Dest->removePredecessor(TIBB); - TI->setSuccessor(SuccNum, Pred); - return; - } + if (BasicBlock *ReuseBB = FindReusablePredBB(DestPHI, TIBB)) { + ProfileInfo *PFI = P->getAnalysisIfAvailable<ProfileInfo>(); + if (PFI) + PFI->splitEdge(TIBB, Dest, ReuseBB); + Dest->removePredecessor(TIBB); + TI->setSuccessor(SuccNum, ReuseBB); + return; } - + SplitCriticalEdge(TI, SuccNum, P, true); return; } |