//===- SimplifyCFG.cpp - Code to perform CFG simplification ---------------===//
//
-// 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
-// of the CFG. It returns true if a modification was made, and returns an
-// iterator that designates the first element remaining after the block that
-// was deleted.
-//
-// WARNING: The entry node of a function may not be simplified.
+// Peephole optimize the CFG.
//
//===----------------------------------------------------------------------===//
//
static bool PropogatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) {
assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!");
- assert(isa<PHINode>(Succ->front()) && "Only works on PHId BBs!");
+
+ if (!isa<PHINode>(Succ->front()))
+ return false; // We can make the transformation, no problem.
// If there is more than one predecessor, and there are PHI nodes in
// the successor, then we need to add incoming edges for the PHI nodes
// Succ. If so, we cannot do the transformation!
//
for (pred_iterator PI = pred_begin(Succ), PE = pred_end(Succ);
- PI != PE; ++PI) {
+ PI != PE; ++PI)
if (find(BBPreds.begin(), BBPreds.end(), *PI) != BBPreds.end())
return true;
- }
// Loop over all of the PHI nodes in the successor BB
for (BasicBlock::iterator I = Succ->begin();
- PHINode *PN = dyn_cast<PHINode>(*I); ++I) {
- Value *OldVal = PN->removeIncomingValue(BB);
+ PHINode *PN = dyn_cast<PHINode>(&*I); ++I) {
+ Value *OldVal = PN->removeIncomingValue(BB, false);
assert(OldVal && "No entry in PHI for Pred BB!");
for (std::vector<BasicBlock*>::const_iterator PredI = BBPreds.begin(),
//
// WARNING: The entry node of a function may not be simplified.
//
-bool SimplifyCFG(Function::iterator &BBIt) {
- BasicBlock *BB = *BBIt;
+bool SimplifyCFG(BasicBlock *BB) {
Function *M = BB->getParent();
assert(BB && BB->getParent() && "Block not embedded in function!");
assert(BB->getTerminator() && "Degenerate basic block encountered!");
- assert(BB->getParent()->front() != BB && "Can't Simplify entry block!");
+ assert(&BB->getParent()->front() != BB && "Can't Simplify entry block!");
// Remove basic blocks that have no predecessors... which are unreachable.
std::bind2nd(std::mem_fun(&BasicBlock::removePredecessor), BB));
while (!BB->empty()) {
- Instruction *I = BB->back();
+ Instruction &I = BB->back();
// If this instruction is used, replace uses with an arbitrary
// constant value. Because control flow can't get here, we don't care
// what we replace the value with. Note that since this block is
// unreachable, and all values contained within it must dominate their
// uses, that all uses will eventually be removed.
- if (!I->use_empty())
+ if (!I.use_empty())
// Make all users of this instruction reference the constant instead
- I->replaceAllUsesWith(Constant::getNullValue(I->getType()));
+ I.replaceAllUsesWith(Constant::getNullValue(I.getType()));
// Remove the instruction from the basic block
- delete BB->getInstList().pop_back();
+ BB->getInstList().pop_back();
}
- delete M->getBasicBlocks().remove(BBIt);
+ M->getBasicBlockList().erase(BB);
return true;
}
// successor. If so, replace block references with successor.
succ_iterator SI(succ_begin(BB));
if (SI != succ_end(BB) && ++SI == succ_end(BB)) { // One succ?
- if (BB->front()->isTerminator()) { // Terminator is the only instruction!
+ if (BB->front().isTerminator()) { // Terminator is the only instruction!
BasicBlock *Succ = *succ_begin(BB); // There is exactly one successor
if (Succ != BB) { // Arg, don't hurt infinite loops!
// Be careful though, if this transformation fails (returns true) then
// we cannot do this transformation!
//
- if (!isa<PHINode>(Succ->front()) ||
- !PropogatePredecessorsForPHIs(BB, Succ)) {
-
+ if (!PropogatePredecessorsForPHIs(BB, Succ)) {
//cerr << "Killing Trivial BB: \n" << BB;
-
BB->replaceAllUsesWith(Succ);
- BB = M->getBasicBlocks().remove(BBIt);
+ std::string OldName = BB->getName();
+
+ // Delete the old basic block...
+ M->getBasicBlockList().erase(BB);
- if (BB->hasName() && !Succ->hasName()) // Transfer name if we can
- Succ->setName(BB->getName());
- delete BB; // Delete basic block
+ if (!OldName.empty() && !Succ->hasName()) // Transfer name if we can
+ Succ->setName(OldName);
//cerr << "Function after removal: \n" << M;
return true;
// pred, and if there is only one distinct successor of the predecessor, and
// if there are no PHI nodes.
//
- if (!isa<PHINode>(BB->front()) && !BB->hasConstantReferences()) {
+ if (!BB->hasConstantReferences()) {
pred_iterator PI(pred_begin(BB)), PE(pred_end(BB));
BasicBlock *OnlyPred = *PI++;
for (; PI != PE; ++PI) // Search all predecessors, see if they are all same
//cerr << "Merging: " << BB << "into: " << OnlyPred;
TerminatorInst *Term = OnlyPred->getTerminator();
+ // Resolve any PHI nodes at the start of the block. They are all
+ // guaranteed to have exactly one entry if they exist, unless there are
+ // multiple duplicate (but guaranteed to be equal) entries for the
+ // incoming edges. This occurs when there are multiple edges from
+ // OnlyPred to OnlySucc.
+ //
+ while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) {
+ PN->replaceAllUsesWith(PN->getIncomingValue(0));
+ BB->getInstList().pop_front(); // Delete the phi node...
+ }
+
// Delete the unconditional branch from the predecessor...
- BasicBlock::iterator DI = OnlyPred->end();
- delete OnlyPred->getInstList().remove(--DI); // Destroy branch
+ OnlyPred->getInstList().pop_back();
// Move all definitions in the succecessor to the predecessor...
- std::vector<Instruction*> Insts(BB->begin(), BB->end());
- BB->getInstList().remove(BB->begin(), BB->end());
- OnlyPred->getInstList().insert(OnlyPred->end(),
- Insts.begin(), Insts.end());
-
- // Remove basic block from the function... and advance iterator to the
- // next valid block...
- M->getBasicBlocks().remove(BBIt);
-
+ OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList());
+
// Make all PHI nodes that refered to BB now refer to Pred as their
// source...
BB->replaceAllUsesWith(OnlyPred);
-
+
+ std::string OldName = BB->getName();
+
+ // Erase basic block from the function...
+ M->getBasicBlockList().erase(BB);
+
// Inherit predecessors name if it exists...
- if (BB->hasName() && !OnlyPred->hasName())
- OnlyPred->setName(BB->getName());
+ if (!OldName.empty() && !OnlyPred->hasName())
+ OnlyPred->setName(OldName);
- delete BB; // You ARE the weakest link... goodbye
return true;
}
}
projects / oota-llvm.git / blobdiff