From dce94d92df77da125a1c1256a9294db891a9db9c Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Tue, 10 Nov 2009 05:59:26 +0000 Subject: [PATCH] refactor TryToSimplifyUncondBranchFromEmptyBlock out of SimplifyCFG. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@86666 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Transforms/Utils/Local.h | 9 +- lib/Transforms/Utils/Local.cpp | 171 ++++++++++++++++++++++++++ lib/Transforms/Utils/SimplifyCFG.cpp | 166 +------------------------ 3 files changed, 181 insertions(+), 165 deletions(-) diff --git a/include/llvm/Transforms/Utils/Local.h b/include/llvm/Transforms/Utils/Local.h index 419029f10ee..24be83cb3d8 100644 --- a/include/llvm/Transforms/Utils/Local.h +++ b/include/llvm/Transforms/Utils/Local.h @@ -85,7 +85,14 @@ void RecursivelyDeleteDeadPHINode(PHINode *PN); /// void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, Pass *P = 0); - + +/// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an +/// unconditional branch, and contains no instructions other than PHI nodes, +/// potential debug intrinsics and the branch. If possible, eliminate BB by +/// rewriting all the predecessors to branch to the successor block and return +/// true. If we can't transform, return false. +bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB); + /// SimplifyCFG - This function is used to do simplification of a CFG. For /// example, it adjusts branches to branches to eliminate the extra hop, it /// eliminates unreachable basic blocks, and does other "peephole" optimization diff --git a/lib/Transforms/Utils/Local.cpp b/lib/Transforms/Utils/Local.cpp index 543ddf15d10..70afce91ee3 100644 --- a/lib/Transforms/Utils/Local.cpp +++ b/lib/Transforms/Utils/Local.cpp @@ -26,8 +26,11 @@ #include "llvm/Analysis/DebugInfo.h" #include "llvm/Analysis/ProfileInfo.h" #include "llvm/Target/TargetData.h" +#include "llvm/Support/CFG.h" +#include "llvm/Support/Debug.h" #include "llvm/Support/GetElementPtrTypeIterator.h" #include "llvm/Support/MathExtras.h" +#include "llvm/Support/raw_ostream.h" using namespace llvm; //===----------------------------------------------------------------------===// @@ -362,6 +365,174 @@ void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, Pass *P) { PredBB->eraseFromParent(); } +/// CanPropagatePredecessorsForPHIs - Return true if we can fold BB, an +/// almost-empty BB ending in an unconditional branch to Succ, into succ. +/// +/// Assumption: Succ is the single successor for BB. +/// +static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { + assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!"); + + DEBUG(errs() << "Looking to fold " << BB->getName() << " into " + << Succ->getName() << "\n"); + // Shortcut, if there is only a single predecessor it must be BB and merging + // is always safe + if (Succ->getSinglePredecessor()) return true; + + // Make a list of the predecessors of BB + typedef SmallPtrSet BlockSet; + BlockSet BBPreds(pred_begin(BB), pred_end(BB)); + + // Use that list to make another list of common predecessors of BB and Succ + BlockSet CommonPreds; + for (pred_iterator PI = pred_begin(Succ), PE = pred_end(Succ); + PI != PE; ++PI) + if (BBPreds.count(*PI)) + CommonPreds.insert(*PI); + + // Shortcut, if there are no common predecessors, merging is always safe + if (CommonPreds.empty()) + return true; + + // Look at all the phi nodes in Succ, to see if they present a conflict when + // merging these blocks + for (BasicBlock::iterator I = Succ->begin(); isa(I); ++I) { + PHINode *PN = cast(I); + + // If the incoming value from BB is again a PHINode in + // BB which has the same incoming value for *PI as PN does, we can + // merge the phi nodes and then the blocks can still be merged + PHINode *BBPN = dyn_cast(PN->getIncomingValueForBlock(BB)); + if (BBPN && BBPN->getParent() == BB) { + for (BlockSet::iterator PI = CommonPreds.begin(), PE = CommonPreds.end(); + PI != PE; PI++) { + if (BBPN->getIncomingValueForBlock(*PI) + != PN->getIncomingValueForBlock(*PI)) { + DEBUG(errs() << "Can't fold, phi node " << PN->getName() << " in " + << Succ->getName() << " is conflicting with " + << BBPN->getName() << " with regard to common predecessor " + << (*PI)->getName() << "\n"); + return false; + } + } + } else { + Value* Val = PN->getIncomingValueForBlock(BB); + for (BlockSet::iterator PI = CommonPreds.begin(), PE = CommonPreds.end(); + PI != PE; PI++) { + // See if the incoming value for the common predecessor is equal to the + // one for BB, in which case this phi node will not prevent the merging + // of the block. + if (Val != PN->getIncomingValueForBlock(*PI)) { + DEBUG(errs() << "Can't fold, phi node " << PN->getName() << " in " + << Succ->getName() << " is conflicting with regard to common " + << "predecessor " << (*PI)->getName() << "\n"); + return false; + } + } + } + } + + return true; +} + +/// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an +/// unconditional branch, and contains no instructions other than PHI nodes, +/// potential debug intrinsics and the branch. If possible, eliminate BB by +/// rewriting all the predecessors to branch to the successor block and return +/// true. If we can't transform, return false. +bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB) { + // We can't eliminate infinite loops. + BasicBlock *Succ = cast(BB->getTerminator())->getSuccessor(0); + if (BB == Succ) return false; + + // Check to see if merging these blocks would cause conflicts for any of the + // phi nodes in BB or Succ. If not, we can safely merge. + if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false; + + // Check for cases where Succ has multiple predecessors and a PHI node in BB + // has uses which will not disappear when the PHI nodes are merged. It is + // possible to handle such cases, but difficult: it requires checking whether + // BB dominates Succ, which is non-trivial to calculate in the case where + // Succ has multiple predecessors. Also, it requires checking whether + // constructing the necessary self-referential PHI node doesn't intoduce any + // conflicts; this isn't too difficult, but the previous code for doing this + // was incorrect. + // + // Note that if this check finds a live use, BB dominates Succ, so BB is + // something like a loop pre-header (or rarely, a part of an irreducible CFG); + // folding the branch isn't profitable in that case anyway. + if (!Succ->getSinglePredecessor()) { + BasicBlock::iterator BBI = BB->begin(); + while (isa(*BBI)) { + for (Value::use_iterator UI = BBI->use_begin(), E = BBI->use_end(); + UI != E; ++UI) { + if (PHINode* PN = dyn_cast(*UI)) { + if (PN->getIncomingBlock(UI) != BB) + return false; + } else { + return false; + } + } + ++BBI; + } + } + + DEBUG(errs() << "Killing Trivial BB: \n" << *BB); + + if (isa(Succ->begin())) { + // If there is more than one pred of succ, and there are PHI nodes in + // the successor, then we need to add incoming edges for the PHI nodes + // + const SmallVector BBPreds(pred_begin(BB), pred_end(BB)); + + // Loop over all of the PHI nodes in the successor of BB. + for (BasicBlock::iterator I = Succ->begin(); isa(I); ++I) { + PHINode *PN = cast(I); + Value *OldVal = PN->removeIncomingValue(BB, false); + assert(OldVal && "No entry in PHI for Pred BB!"); + + // If this incoming value is one of the PHI nodes in BB, the new entries + // in the PHI node are the entries from the old PHI. + if (isa(OldVal) && cast(OldVal)->getParent() == BB) { + PHINode *OldValPN = cast(OldVal); + for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) + // Note that, since we are merging phi nodes and BB and Succ might + // have common predecessors, we could end up with a phi node with + // identical incoming branches. This will be cleaned up later (and + // will trigger asserts if we try to clean it up now, without also + // simplifying the corresponding conditional branch). + PN->addIncoming(OldValPN->getIncomingValue(i), + OldValPN->getIncomingBlock(i)); + } else { + // Add an incoming value for each of the new incoming values. + for (unsigned i = 0, e = BBPreds.size(); i != e; ++i) + PN->addIncoming(OldVal, BBPreds[i]); + } + } + } + + while (PHINode *PN = dyn_cast(&BB->front())) { + if (Succ->getSinglePredecessor()) { + // BB is the only predecessor of Succ, so Succ will end up with exactly + // the same predecessors BB had. + Succ->getInstList().splice(Succ->begin(), + BB->getInstList(), BB->begin()); + } else { + // We explicitly check for such uses in CanPropagatePredecessorsForPHIs. + assert(PN->use_empty() && "There shouldn't be any uses here!"); + PN->eraseFromParent(); + } + } + + // Everything that jumped to BB now goes to Succ. + BB->replaceAllUsesWith(Succ); + if (!Succ->hasName()) Succ->takeName(BB); + BB->eraseFromParent(); // Delete the old basic block. + return true; +} + + + /// OnlyUsedByDbgIntrinsics - Return true if the instruction I is only used /// by DbgIntrinsics. If DbgInUses is specified then the vector is filled /// with the DbgInfoIntrinsic that use the instruction I. diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp index a8a9e306f37..8dbc8081c5a 100644 --- a/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/lib/Transforms/Utils/SimplifyCFG.cpp @@ -78,166 +78,6 @@ static void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, PN->addIncoming(PN->getIncomingValueForBlock(ExistPred), NewPred); } -/// CanPropagatePredecessorsForPHIs - Return true if we can fold BB, an -/// almost-empty BB ending in an unconditional branch to Succ, into succ. -/// -/// Assumption: Succ is the single successor for BB. -/// -static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { - assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!"); - - DEBUG(errs() << "Looking to fold " << BB->getName() << " into " - << Succ->getName() << "\n"); - // Shortcut, if there is only a single predecessor it must be BB and merging - // is always safe - if (Succ->getSinglePredecessor()) return true; - - // Make a list of the predecessors of BB - typedef SmallPtrSet BlockSet; - BlockSet BBPreds(pred_begin(BB), pred_end(BB)); - - // Use that list to make another list of common predecessors of BB and Succ - BlockSet CommonPreds; - for (pred_iterator PI = pred_begin(Succ), PE = pred_end(Succ); - PI != PE; ++PI) - if (BBPreds.count(*PI)) - CommonPreds.insert(*PI); - - // Shortcut, if there are no common predecessors, merging is always safe - if (CommonPreds.empty()) - return true; - - // Look at all the phi nodes in Succ, to see if they present a conflict when - // merging these blocks - for (BasicBlock::iterator I = Succ->begin(); isa(I); ++I) { - PHINode *PN = cast(I); - - // If the incoming value from BB is again a PHINode in - // BB which has the same incoming value for *PI as PN does, we can - // merge the phi nodes and then the blocks can still be merged - PHINode *BBPN = dyn_cast(PN->getIncomingValueForBlock(BB)); - if (BBPN && BBPN->getParent() == BB) { - for (BlockSet::iterator PI = CommonPreds.begin(), PE = CommonPreds.end(); - PI != PE; PI++) { - if (BBPN->getIncomingValueForBlock(*PI) - != PN->getIncomingValueForBlock(*PI)) { - DEBUG(errs() << "Can't fold, phi node " << PN->getName() << " in " - << Succ->getName() << " is conflicting with " - << BBPN->getName() << " with regard to common predecessor " - << (*PI)->getName() << "\n"); - return false; - } - } - } else { - Value* Val = PN->getIncomingValueForBlock(BB); - for (BlockSet::iterator PI = CommonPreds.begin(), PE = CommonPreds.end(); - PI != PE; PI++) { - // See if the incoming value for the common predecessor is equal to the - // one for BB, in which case this phi node will not prevent the merging - // of the block. - if (Val != PN->getIncomingValueForBlock(*PI)) { - DEBUG(errs() << "Can't fold, phi node " << PN->getName() << " in " - << Succ->getName() << " is conflicting with regard to common " - << "predecessor " << (*PI)->getName() << "\n"); - return false; - } - } - } - } - - return true; -} - -/// TryToSimplifyUncondBranchFromEmptyBlock - BB contains an unconditional -/// branch to Succ, and contains no instructions other than PHI nodes and the -/// branch. If possible, eliminate BB. -static bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, - BasicBlock *Succ) { - // Check to see if merging these blocks would cause conflicts for any of the - // phi nodes in BB or Succ. If not, we can safely merge. - if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false; - - // Check for cases where Succ has multiple predecessors and a PHI node in BB - // has uses which will not disappear when the PHI nodes are merged. It is - // possible to handle such cases, but difficult: it requires checking whether - // BB dominates Succ, which is non-trivial to calculate in the case where - // Succ has multiple predecessors. Also, it requires checking whether - // constructing the necessary self-referential PHI node doesn't intoduce any - // conflicts; this isn't too difficult, but the previous code for doing this - // was incorrect. - // - // Note that if this check finds a live use, BB dominates Succ, so BB is - // something like a loop pre-header (or rarely, a part of an irreducible CFG); - // folding the branch isn't profitable in that case anyway. - if (!Succ->getSinglePredecessor()) { - BasicBlock::iterator BBI = BB->begin(); - while (isa(*BBI)) { - for (Value::use_iterator UI = BBI->use_begin(), E = BBI->use_end(); - UI != E; ++UI) { - if (PHINode* PN = dyn_cast(*UI)) { - if (PN->getIncomingBlock(UI) != BB) - return false; - } else { - return false; - } - } - ++BBI; - } - } - - DEBUG(errs() << "Killing Trivial BB: \n" << *BB); - - if (isa(Succ->begin())) { - // If there is more than one pred of succ, and there are PHI nodes in - // the successor, then we need to add incoming edges for the PHI nodes - // - const SmallVector BBPreds(pred_begin(BB), pred_end(BB)); - - // Loop over all of the PHI nodes in the successor of BB. - for (BasicBlock::iterator I = Succ->begin(); isa(I); ++I) { - PHINode *PN = cast(I); - Value *OldVal = PN->removeIncomingValue(BB, false); - assert(OldVal && "No entry in PHI for Pred BB!"); - - // If this incoming value is one of the PHI nodes in BB, the new entries - // in the PHI node are the entries from the old PHI. - if (isa(OldVal) && cast(OldVal)->getParent() == BB) { - PHINode *OldValPN = cast(OldVal); - for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) - // Note that, since we are merging phi nodes and BB and Succ might - // have common predecessors, we could end up with a phi node with - // identical incoming branches. This will be cleaned up later (and - // will trigger asserts if we try to clean it up now, without also - // simplifying the corresponding conditional branch). - PN->addIncoming(OldValPN->getIncomingValue(i), - OldValPN->getIncomingBlock(i)); - } else { - // Add an incoming value for each of the new incoming values. - for (unsigned i = 0, e = BBPreds.size(); i != e; ++i) - PN->addIncoming(OldVal, BBPreds[i]); - } - } - } - - while (PHINode *PN = dyn_cast(&BB->front())) { - if (Succ->getSinglePredecessor()) { - // BB is the only predecessor of Succ, so Succ will end up with exactly - // the same predecessors BB had. - Succ->getInstList().splice(Succ->begin(), - BB->getInstList(), BB->begin()); - } else { - // We explicitly check for such uses in CanPropagatePredecessorsForPHIs. - assert(PN->use_empty() && "There shouldn't be any uses here!"); - PN->eraseFromParent(); - } - } - - // Everything that jumped to BB now goes to Succ. - BB->replaceAllUsesWith(Succ); - if (!Succ->hasName()) Succ->takeName(BB); - BB->eraseFromParent(); // Delete the old basic block. - return true; -} /// GetIfCondition - Given a basic block (BB) with two predecessors (and /// presumably PHI nodes in it), check to see if the merge at this block is due @@ -1983,13 +1823,11 @@ bool llvm::SimplifyCFG(BasicBlock *BB) { if (BI->isUnconditional()) { BasicBlock::iterator BBI = BB->getFirstNonPHI(); - BasicBlock *Succ = BI->getSuccessor(0); // Ignore dbg intrinsics. while (isa(BBI)) ++BBI; - if (BBI->isTerminator() && // Terminator is the only non-phi instruction! - Succ != BB) // Don't hurt infinite loops! - if (TryToSimplifyUncondBranchFromEmptyBlock(BB, Succ)) + if (BBI->isTerminator()) // Terminator is the only non-phi instruction! + if (TryToSimplifyUncondBranchFromEmptyBlock(BB)) return true; } else { // Conditional branch -- 2.34.1