BreakCriticalEdges.cpp revision c178d9459a0e659bedbc1b3c79459ee168453376
1d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner//===- BreakCriticalEdges.cpp - Critical Edge Elimination Pass ------------===// 2d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner// 3d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner// BreakCriticalEdges pass - Break all of the critical edges in the CFG by 4d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner// inserting a dummy basic block. This pass may be "required" by passes that 5d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner// cannot deal with critical edges. For this usage, the structure type is 6d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner// forward declared. This pass obviously invalidates the CFG, but can update 7d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner// forward dominator (set, immediate dominators, and tree) information. 8d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner// 9d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner//===----------------------------------------------------------------------===// 10d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner 11d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner#include "llvm/Transforms/Scalar.h" 12d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner#include "llvm/Analysis/Dominators.h" 13d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner#include "llvm/Function.h" 14eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner#include "llvm/iTerminators.h" 15eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner#include "llvm/iPHINode.h" 16eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner#include "llvm/Support/CFG.h" 17d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner#include "Support/StatisticReporter.h" 18d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner 196de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattnernamespace { 206de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner Statistic<> NumBroken("break-crit-edges\t- Number of blocks inserted"); 216de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner 226de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner struct BreakCriticalEdges : public FunctionPass { 236de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner virtual bool runOnFunction(Function &F); 246de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner 256de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 266de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner AU.addPreserved<DominatorSet>(); 276de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner AU.addPreserved<ImmediateDominators>(); 286de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner AU.addPreserved<DominatorTree>(); 29c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner AU.addPreservedID(LoopPreheadersID); // No preheaders deleted. 306de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner } 31c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner private: 32c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner void SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum); 336de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner }; 346de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner 356de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner RegisterOpt<BreakCriticalEdges> X("break-crit-edges", 366de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner "Break critical edges in CFG"); 376de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner} 38d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner 39eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// Publically exposed interface to pass... 406de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattnerconst PassInfo *BreakCriticalEdgesID = X.getPassInfo(); 41d76efa018660e806cd87c0a24512e3c532fc1d36Chris LattnerPass *createBreakCriticalEdgesPass() { return new BreakCriticalEdges(); } 42d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner 43eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 44eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// isCriticalEdge - Return true if the specified edge is a critical edge. 45eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// Critical edges are edges from a block with multiple successors to a block 46eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// with multiple predecessors. 47eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// 48eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattnerstatic bool isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum) { 49eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner assert(SuccNum < TI->getNumSuccessors() && "Illegal edge specification!"); 50eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner assert (TI->getNumSuccessors() > 1); 51eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 52eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner const BasicBlock *Dest = TI->getSuccessor(SuccNum); 53eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner pred_const_iterator I = pred_begin(Dest), E = pred_end(Dest); 54eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 55eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // If there is more than one predecessor, this is a critical edge... 56eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner assert(I != E && "No preds, but we have an edge to the block?"); 57eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner ++I; // Skip one edge due to the incoming arc from TI. 58eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner return I != E; 59eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner} 60eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 61eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// SplitCriticalEdge - Insert a new node node to split the critical edge. This 62eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// will update DominatorSet, ImmediateDominator and DominatorTree information if 63eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// it is available, thus calling this pass will not invalidate either of them. 64eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// 65c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattnervoid BreakCriticalEdges::SplitCriticalEdge(TerminatorInst *TI,unsigned SuccNum){ 66eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner assert(isCriticalEdge(TI, SuccNum) && 67eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner "Cannot break a critical edge, if it isn't a critical edge"); 68eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner BasicBlock *TIBB = TI->getParent(); 69eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 70eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // Create a new basic block, linking it into the CFG. 71eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner BasicBlock *NewBB = new BasicBlock(TIBB->getName()+"_crit_edge"); 72eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner BasicBlock *DestBB = TI->getSuccessor(SuccNum); 73eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // Create our unconditional branch... 74eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner BranchInst *BI = new BranchInst(DestBB); 75eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner NewBB->getInstList().push_back(BI); 76eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 77eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // Branch to the new block, breaking the edge... 78eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner TI->setSuccessor(SuccNum, NewBB); 79eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 80eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // Insert the block into the function... right after the block TI lives in. 81eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner Function &F = *TIBB->getParent(); 82eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner F.getBasicBlockList().insert(TIBB->getNext(), NewBB); 83eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 84eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // If there are any PHI nodes in DestBB, we need to update them so that they 85eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // merge incoming values from NewBB instead of from TIBB. 86eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // 87eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner for (BasicBlock::iterator I = DestBB->begin(); 88eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner PHINode *PN = dyn_cast<PHINode>(&*I); ++I) { 89eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // We no longer enter through TIBB, now we come in through NewBB. 90eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner PN->replaceUsesOfWith(TIBB, NewBB); 91eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner } 92eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 93c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // Now update analysis information. These are the analyses that we are 94c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // currently capable of updating... 95eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // 96eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 97c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // Should we update DominatorSet information? 98c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner if (DominatorSet *DS = getAnalysisToUpdate<DominatorSet>()) { 99c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // The blocks that dominate the new one are the blocks that dominate TIBB 100c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // plus the new block itself. 101c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner DominatorSet::DomSetType DomSet = DS->getDominators(TIBB); 102c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner DomSet.insert(NewBB); // A block always dominates itself. 103c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner DS->addBasicBlock(NewBB, DomSet); 104c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner } 105eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 106c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // Should we update ImmdediateDominator information? 107c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner if (ImmediateDominators *ID = getAnalysisToUpdate<ImmediateDominators>()) { 108c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // TIBB is the new immediate dominator for NewBB. NewBB doesn't dominate 109c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // anything. 110c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner ID->addNewBlock(NewBB, TIBB); 111c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner } 112c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner 113c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // Should we update DominatorTree information? 114c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner if (DominatorTree *DT = getAnalysisToUpdate<DominatorTree>()) { 115c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner DominatorTree::Node *TINode = DT->getNode(TIBB); 116c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner 117c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // The new block is not the immediate dominator for any other nodes, but 118c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // TINode is the immediate dominator for the new node. 119c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner // 120c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner DT->createNewNode(NewBB, TINode); 121eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner } 122eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner} 123eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 124d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner// runOnFunction - Loop over all of the edges in the CFG, breaking critical 125d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner// edges as they are found. 126d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner// 127d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattnerbool BreakCriticalEdges::runOnFunction(Function &F) { 128d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner bool Changed = false; 129d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) { 130d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner TerminatorInst *TI = I->getTerminator(); 131eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner if (TI->getNumSuccessors() > 1) 132eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 133eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner if (isCriticalEdge(TI, i)) { 134c178d9459a0e659bedbc1b3c79459ee168453376Chris Lattner SplitCriticalEdge(TI, i); 135eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner ++NumBroken; 136eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner Changed = true; 137eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner } 138d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner } 139d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner 140d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner return Changed; 141d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner} 142