SimplifyCFG.cpp revision bb190ac8dafdcc5e604da3695987d69ee8632195
101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner//===- SimplifyCFG.cpp - Code to perform CFG simplification ---------------===// 201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 3bb190ac8dafdcc5e604da3695987d69ee8632195Chris Lattner// Peephole optimize the CFG. 401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner//===----------------------------------------------------------------------===// 601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner#include "llvm/Transforms/Utils/Local.h" 801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner#include "llvm/Constant.h" 901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner#include "llvm/iPHINode.h" 1001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner#include "llvm/Support/CFG.h" 1101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner#include <algorithm> 1201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner#include <functional> 1301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 1401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// PropogatePredecessors - This gets "Succ" ready to have the predecessors from 1501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// "BB". This is a little tricky because "Succ" has PHI nodes, which need to 1601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// have extra slots added to them to hold the merge edges from BB's 1701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// predecessors. This function returns true (failure) if the Succ BB already 1801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// has a predecessor that is a predecessor of BB. 1901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 2001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// Assumption: Succ is the single successor for BB. 2101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 2201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattnerstatic bool PropogatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { 2301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!"); 243abb95df01ff2ea5a6a35a1b47351072d4cb4c73Chris Lattner 253abb95df01ff2ea5a6a35a1b47351072d4cb4c73Chris Lattner if (!isa<PHINode>(Succ->front())) 263abb95df01ff2ea5a6a35a1b47351072d4cb4c73Chris Lattner return false; // We can make the transformation, no problem. 2701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 2801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // If there is more than one predecessor, and there are PHI nodes in 2901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // the successor, then we need to add incoming edges for the PHI nodes 3001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // 3101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner const std::vector<BasicBlock*> BBPreds(pred_begin(BB), pred_end(BB)); 3201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 3301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Check to see if one of the predecessors of BB is already a predecessor of 3401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Succ. If so, we cannot do the transformation! 3501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // 3601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner for (pred_iterator PI = pred_begin(Succ), PE = pred_end(Succ); 373abb95df01ff2ea5a6a35a1b47351072d4cb4c73Chris Lattner PI != PE; ++PI) 3801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner if (find(BBPreds.begin(), BBPreds.end(), *PI) != BBPreds.end()) 3901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner return true; 4001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 4101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Loop over all of the PHI nodes in the successor BB 4201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner for (BasicBlock::iterator I = Succ->begin(); 4318961504fc2b299578dba817900a0696cf3ccc4dChris Lattner PHINode *PN = dyn_cast<PHINode>(&*I); ++I) { 44bb190ac8dafdcc5e604da3695987d69ee8632195Chris Lattner Value *OldVal = PN->removeIncomingValue(BB, false); 4501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner assert(OldVal && "No entry in PHI for Pred BB!"); 4601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 4701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner for (std::vector<BasicBlock*>::const_iterator PredI = BBPreds.begin(), 4801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner End = BBPreds.end(); PredI != End; ++PredI) { 4901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Add an incoming value for each of the new incoming values... 5001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner PN->addIncoming(OldVal, *PredI); 5101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 5201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 5301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner return false; 5401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner} 5501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 5601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 5701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// SimplifyCFG - This function is used to do simplification of a CFG. For 5801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// example, it adjusts branches to branches to eliminate the extra hop, it 5901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// eliminates unreachable basic blocks, and does other "peephole" optimization 6001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// of the CFG. It returns true if a modification was made, and returns an 6101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// iterator that designates the first element remaining after the block that 6201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// was deleted. 6301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 6401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// WARNING: The entry node of a function may not be simplified. 6501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 6618961504fc2b299578dba817900a0696cf3ccc4dChris Lattnerbool SimplifyCFG(BasicBlock *BB) { 6701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner Function *M = BB->getParent(); 6801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 6901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner assert(BB && BB->getParent() && "Block not embedded in function!"); 7001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner assert(BB->getTerminator() && "Degenerate basic block encountered!"); 7118961504fc2b299578dba817900a0696cf3ccc4dChris Lattner assert(&BB->getParent()->front() != BB && "Can't Simplify entry block!"); 7201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 7301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 7401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Remove basic blocks that have no predecessors... which are unreachable. 7501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner if (pred_begin(BB) == pred_end(BB) && 7601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner !BB->hasConstantReferences()) { 7701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner //cerr << "Removing BB: \n" << BB; 7801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 7901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Loop through all of our successors and make sure they know that one 8001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // of their predecessors is going away. 8101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner for_each(succ_begin(BB), succ_end(BB), 8201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner std::bind2nd(std::mem_fun(&BasicBlock::removePredecessor), BB)); 8301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 8401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner while (!BB->empty()) { 8518961504fc2b299578dba817900a0696cf3ccc4dChris Lattner Instruction &I = BB->back(); 8601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // If this instruction is used, replace uses with an arbitrary 8701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // constant value. Because control flow can't get here, we don't care 8801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // what we replace the value with. Note that since this block is 8901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // unreachable, and all values contained within it must dominate their 9001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // uses, that all uses will eventually be removed. 9118961504fc2b299578dba817900a0696cf3ccc4dChris Lattner if (!I.use_empty()) 9201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Make all users of this instruction reference the constant instead 9318961504fc2b299578dba817900a0696cf3ccc4dChris Lattner I.replaceAllUsesWith(Constant::getNullValue(I.getType())); 9401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 9501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Remove the instruction from the basic block 9618961504fc2b299578dba817900a0696cf3ccc4dChris Lattner BB->getInstList().pop_back(); 9701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 9818961504fc2b299578dba817900a0696cf3ccc4dChris Lattner M->getBasicBlockList().erase(BB); 9901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner return true; 10001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 10101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 10201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Check to see if this block has no instructions and only a single 10301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // successor. If so, replace block references with successor. 10401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner succ_iterator SI(succ_begin(BB)); 10501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner if (SI != succ_end(BB) && ++SI == succ_end(BB)) { // One succ? 10618961504fc2b299578dba817900a0696cf3ccc4dChris Lattner if (BB->front().isTerminator()) { // Terminator is the only instruction! 10701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner BasicBlock *Succ = *succ_begin(BB); // There is exactly one successor 10801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 10901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner if (Succ != BB) { // Arg, don't hurt infinite loops! 11001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // If our successor has PHI nodes, then we need to update them to 11101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // include entries for BB's predecessors, not for BB itself. 11201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Be careful though, if this transformation fails (returns true) then 11301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // we cannot do this transformation! 11401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // 1153abb95df01ff2ea5a6a35a1b47351072d4cb4c73Chris Lattner if (!PropogatePredecessorsForPHIs(BB, Succ)) { 11601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner //cerr << "Killing Trivial BB: \n" << BB; 11701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner BB->replaceAllUsesWith(Succ); 11818961504fc2b299578dba817900a0696cf3ccc4dChris Lattner std::string OldName = BB->getName(); 11918961504fc2b299578dba817900a0696cf3ccc4dChris Lattner 12018961504fc2b299578dba817900a0696cf3ccc4dChris Lattner // Delete the old basic block... 12118961504fc2b299578dba817900a0696cf3ccc4dChris Lattner M->getBasicBlockList().erase(BB); 12201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 12318961504fc2b299578dba817900a0696cf3ccc4dChris Lattner if (!OldName.empty() && !Succ->hasName()) // Transfer name if we can 12418961504fc2b299578dba817900a0696cf3ccc4dChris Lattner Succ->setName(OldName); 12501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 12601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner //cerr << "Function after removal: \n" << M; 12701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner return true; 12801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 12901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 13001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 13101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 13201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 13301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Merge basic blocks into their predecessor if there is only one distinct 13401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // pred, and if there is only one distinct successor of the predecessor, and 13501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // if there are no PHI nodes. 13601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // 13791b65c0b42b3d5dece246bdb366441d6f5593396Chris Lattner if (!BB->hasConstantReferences()) { 13801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner pred_iterator PI(pred_begin(BB)), PE(pred_end(BB)); 13901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner BasicBlock *OnlyPred = *PI++; 14001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner for (; PI != PE; ++PI) // Search all predecessors, see if they are all same 14101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner if (*PI != OnlyPred) { 14201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner OnlyPred = 0; // There are multiple different predecessors... 14301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner break; 14401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 14501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 14601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner BasicBlock *OnlySucc = 0; 14701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner if (OnlyPred && OnlyPred != BB) { // Don't break self loops 14801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Check to see if there is only one distinct successor... 14901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner succ_iterator SI(succ_begin(OnlyPred)), SE(succ_end(OnlyPred)); 15001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner OnlySucc = BB; 15101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner for (; SI != SE; ++SI) 15201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner if (*SI != OnlySucc) { 15301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner OnlySucc = 0; // There are multiple distinct successors! 15401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner break; 15501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 15601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 15701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 15801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner if (OnlySucc) { 15901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner //cerr << "Merging: " << BB << "into: " << OnlyPred; 16001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner TerminatorInst *Term = OnlyPred->getTerminator(); 16101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 16291b65c0b42b3d5dece246bdb366441d6f5593396Chris Lattner // Resolve any PHI nodes at the start of the block. They are all 163929b2c6900e20859f338d808a1a89ffc5b3563bbChris Lattner // guaranteed to have exactly one entry if they exist, unless there are 164929b2c6900e20859f338d808a1a89ffc5b3563bbChris Lattner // multiple duplicate (but guaranteed to be equal) entries for the 165929b2c6900e20859f338d808a1a89ffc5b3563bbChris Lattner // incoming edges. This occurs when there are multiple edges from 166929b2c6900e20859f338d808a1a89ffc5b3563bbChris Lattner // OnlyPred to OnlySucc. 16791b65c0b42b3d5dece246bdb366441d6f5593396Chris Lattner // 16891b65c0b42b3d5dece246bdb366441d6f5593396Chris Lattner while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) { 16991b65c0b42b3d5dece246bdb366441d6f5593396Chris Lattner PN->replaceAllUsesWith(PN->getIncomingValue(0)); 17091b65c0b42b3d5dece246bdb366441d6f5593396Chris Lattner BB->getInstList().pop_front(); // Delete the phi node... 17191b65c0b42b3d5dece246bdb366441d6f5593396Chris Lattner } 17291b65c0b42b3d5dece246bdb366441d6f5593396Chris Lattner 17301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Delete the unconditional branch from the predecessor... 17418961504fc2b299578dba817900a0696cf3ccc4dChris Lattner OnlyPred->getInstList().pop_back(); 17501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 17601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Move all definitions in the succecessor to the predecessor... 17718961504fc2b299578dba817900a0696cf3ccc4dChris Lattner OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList()); 17818961504fc2b299578dba817900a0696cf3ccc4dChris Lattner 17901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Make all PHI nodes that refered to BB now refer to Pred as their 18001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // source... 18101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner BB->replaceAllUsesWith(OnlyPred); 18218961504fc2b299578dba817900a0696cf3ccc4dChris Lattner 18318961504fc2b299578dba817900a0696cf3ccc4dChris Lattner std::string OldName = BB->getName(); 18418961504fc2b299578dba817900a0696cf3ccc4dChris Lattner 18518961504fc2b299578dba817900a0696cf3ccc4dChris Lattner // Erase basic block from the function... 18618961504fc2b299578dba817900a0696cf3ccc4dChris Lattner M->getBasicBlockList().erase(BB); 18718961504fc2b299578dba817900a0696cf3ccc4dChris Lattner 18801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Inherit predecessors name if it exists... 18918961504fc2b299578dba817900a0696cf3ccc4dChris Lattner if (!OldName.empty() && !OnlyPred->hasName()) 19018961504fc2b299578dba817900a0696cf3ccc4dChris Lattner OnlyPred->setName(OldName); 19101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 19201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner return true; 19301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 19401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 19501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 19601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner return false; 19701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner} 198