From b31b06d04b81c5383e2fba0cd44d4ba3f324a794 Mon Sep 17 00:00:00 2001 From: Owen Anderson Date: Thu, 17 Jul 2008 00:01:40 +0000 Subject: [PATCH] Factor MergeBlockIntoPredecessor out into BasicBlockUtils. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53705 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../llvm/Transforms/Utils/BasicBlockUtils.h | 4 ++ lib/Transforms/Scalar/GVN.cpp | 55 ++----------------- lib/Transforms/Utils/BasicBlockUtils.cpp | 52 ++++++++++++++++++ 3 files changed, 60 insertions(+), 51 deletions(-) diff --git a/include/llvm/Transforms/Utils/BasicBlockUtils.h b/include/llvm/Transforms/Utils/BasicBlockUtils.h index a44095f27d1..f1a7a264176 100644 --- a/include/llvm/Transforms/Utils/BasicBlockUtils.h +++ b/include/llvm/Transforms/Utils/BasicBlockUtils.h @@ -25,6 +25,10 @@ namespace llvm { class Instruction; class Pass; +/// MergeBlockIntoPredecessor - Attempts to merge a block into its predecessor, +/// if possible. The return value indicates success or failure. +bool MergeBlockIntoPredecessor(BasicBlock* BB, Pass* P); + // ReplaceInstWithValue - Replace all uses of an instruction (specified by BI) // with a value, then remove and delete the original instruction. // diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp index 986d755bad0..b002380b74b 100644 --- a/lib/Transforms/Scalar/GVN.cpp +++ b/lib/Transforms/Scalar/GVN.cpp @@ -1125,7 +1125,10 @@ bool GVN::runOnFunction(Function& F) { for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ) { BasicBlock* BB = FI; ++FI; - changed |= mergeBlockIntoPredecessor(BB); + bool removedBlock = MergeBlockIntoPredecessor(BB, this); + if (removedBlock) NumGVNBlocks++; + + changed |= removedBlock; } while (shouldContinue) { @@ -1336,56 +1339,6 @@ bool GVN::performPRE(Function& F) { return changed; } -// mergeBlockIntoPredecessor - If this block is the only successor -// of its predecessor, and the edge is non-critical, -// fold it into that predecessor. -bool GVN::mergeBlockIntoPredecessor(BasicBlock* BB) { - // Can't merge the entry block. - if (pred_begin(BB) == pred_end(BB)) return false; - // Can't merge if there are multiple preds. - if (++pred_begin(BB) != pred_end(BB)) return false; - - BasicBlock* PredBB = *pred_begin(BB); - - // Can't merge if the edge is critical. - if (PredBB->getTerminator()->getNumSuccessors() != 1) return false; - - // Begin by getting rid of unneeded PHIs. - while (PHINode *PN = dyn_cast(&BB->front())) { - PN->replaceAllUsesWith(PN->getIncomingValue(0)); - BB->getInstList().pop_front(); // Delete the phi node... - } - - // Delete the unconditional branch from the predecessor... - PredBB->getInstList().pop_back(); - - // Move all definitions in the successor to the predecessor... - PredBB->getInstList().splice(PredBB->end(), BB->getInstList()); - - // Make all PHI nodes that referred to BB now refer to Pred as their - // source... - BB->replaceAllUsesWith(PredBB); - - // Finally, erase the old block and update dominator info. - DominatorTree& DT = getAnalysis(); - DomTreeNode* DTN = DT[BB]; - DomTreeNode* PredDTN = DT[PredBB]; - - if (DTN) { - SmallPtrSet Children(DTN->begin(), DTN->end()); - for (SmallPtrSet::iterator DI = Children.begin(), - DE = Children.end(); DI != DE; ++DI) - DT.changeImmediateDominator(*DI, PredDTN); - - DT.eraseNode(BB); - } - - BB->eraseFromParent(); - - NumGVNBlocks++; - return true; -} - // iterateOnFunction - Executes one iteration of GVN bool GVN::iterateOnFunction(Function &F) { // Clean out global sets from any previous functions diff --git a/lib/Transforms/Utils/BasicBlockUtils.cpp b/lib/Transforms/Utils/BasicBlockUtils.cpp index 93a8c8e5934..02eb4d6f60a 100644 --- a/lib/Transforms/Utils/BasicBlockUtils.cpp +++ b/lib/Transforms/Utils/BasicBlockUtils.cpp @@ -23,6 +23,58 @@ #include using namespace llvm; +/// MergeBlockIntoPredecessor - Attempts to merge a block into its predecessor, +/// if possible. The return value indicates success or failure. +bool llvm::MergeBlockIntoPredecessor(BasicBlock* BB, Pass* P) { + // Can't merge the entry block. + if (pred_begin(BB) == pred_end(BB)) return false; + // Can't merge if there are multiple preds. + if (++pred_begin(BB) != pred_end(BB)) return false; + + BasicBlock* PredBB = *pred_begin(BB); + + // Can't merge if the edge is critical. + if (PredBB->getTerminator()->getNumSuccessors() != 1) return false; + + // Begin by getting rid of unneeded PHIs. + while (PHINode *PN = dyn_cast(&BB->front())) { + PN->replaceAllUsesWith(PN->getIncomingValue(0)); + BB->getInstList().pop_front(); // Delete the phi node... + } + + // Delete the unconditional branch from the predecessor... + PredBB->getInstList().pop_back(); + + // Move all definitions in the successor to the predecessor... + PredBB->getInstList().splice(PredBB->end(), BB->getInstList()); + + // Make all PHI nodes that referred to BB now refer to Pred as their + // source... + BB->replaceAllUsesWith(PredBB); + + // Finally, erase the old block and update dominator info. + if (P) { + if (DominatorTree* DT = P->getAnalysisToUpdate()) { + DomTreeNode* DTN = DT->getNode(BB); + DomTreeNode* PredDTN = DT->getNode(PredBB); + + if (DTN) { + SmallPtrSet Children(DTN->begin(), DTN->end()); + for (SmallPtrSet::iterator DI = Children.begin(), + DE = Children.end(); DI != DE; ++DI) + DT->changeImmediateDominator(*DI, PredDTN); + + DT->eraseNode(BB); + } + } + } + + BB->eraseFromParent(); + + + return true; +} + /// ReplaceInstWithValue - Replace all uses of an instruction (specified by BI) /// with a value, then remove and delete the original instruction. /// -- 2.34.1