BreakCriticalEdges.cpp revision eb0456c8fd60e6c2ef844d8696baa39d5d55f082
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>(); 296de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner } 306de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner }; 316de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner 326de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner RegisterOpt<BreakCriticalEdges> X("break-crit-edges", 336de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner "Break critical edges in CFG"); 346de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattner} 35d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner 36eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// Publically exposed interface to pass... 376de302bbdb0ac8a595ca35a06e5bbc1605e1da3eChris Lattnerconst PassInfo *BreakCriticalEdgesID = X.getPassInfo(); 38d76efa018660e806cd87c0a24512e3c532fc1d36Chris LattnerPass *createBreakCriticalEdgesPass() { return new BreakCriticalEdges(); } 39d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner 40eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 41eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// isCriticalEdge - Return true if the specified edge is a critical edge. 42eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// Critical edges are edges from a block with multiple successors to a block 43eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// with multiple predecessors. 44eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// 45eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattnerstatic bool isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum) { 46eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner assert(SuccNum < TI->getNumSuccessors() && "Illegal edge specification!"); 47eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner assert (TI->getNumSuccessors() > 1); 48eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 49eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner const BasicBlock *Dest = TI->getSuccessor(SuccNum); 50eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner pred_const_iterator I = pred_begin(Dest), E = pred_end(Dest); 51eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 52eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // If there is more than one predecessor, this is a critical edge... 53eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner assert(I != E && "No preds, but we have an edge to the block?"); 54eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner ++I; // Skip one edge due to the incoming arc from TI. 55eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner return I != E; 56eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner} 57eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 58eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// SplitCriticalEdge - Insert a new node node to split the critical edge. This 59eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// will update DominatorSet, ImmediateDominator and DominatorTree information if 60eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// it is available, thus calling this pass will not invalidate either of them. 61eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner// 62eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattnerstatic void SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P) { 63eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner assert(isCriticalEdge(TI, SuccNum) && 64eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner "Cannot break a critical edge, if it isn't a critical edge"); 65eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner BasicBlock *TIBB = TI->getParent(); 66eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 67eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // Create a new basic block, linking it into the CFG. 68eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner BasicBlock *NewBB = new BasicBlock(TIBB->getName()+"_crit_edge"); 69eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner BasicBlock *DestBB = TI->getSuccessor(SuccNum); 70eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // Create our unconditional branch... 71eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner BranchInst *BI = new BranchInst(DestBB); 72eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner NewBB->getInstList().push_back(BI); 73eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 74eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // Branch to the new block, breaking the edge... 75eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner TI->setSuccessor(SuccNum, NewBB); 76eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 77eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // Insert the block into the function... right after the block TI lives in. 78eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner Function &F = *TIBB->getParent(); 79eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner F.getBasicBlockList().insert(TIBB->getNext(), NewBB); 80eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 81eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // If there are any PHI nodes in DestBB, we need to update them so that they 82eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // merge incoming values from NewBB instead of from TIBB. 83eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // 84eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner for (BasicBlock::iterator I = DestBB->begin(); 85eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner PHINode *PN = dyn_cast<PHINode>(&*I); ++I) { 86eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // We no longer enter through TIBB, now we come in through NewBB. 87eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner PN->replaceUsesOfWith(TIBB, NewBB); 88eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner } 89eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 90eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // Now if we have a pass object, update analysis information. Currently we 91eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // update DominatorSet and DominatorTree information if it's available. 92eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // 93eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner if (P) { 94eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // Should we update DominatorSet information? 95eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner if (DominatorSet *DS = P->getAnalysisToUpdate<DominatorSet>()) { 96eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // The blocks that dominate the new one are the blocks that dominate TIBB 97eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // plus the new block itself. 98eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner DominatorSet::DomSetType DomSet = DS->getDominators(TIBB); 99eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner DomSet.insert(NewBB); // A block always dominates itself. 100eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner DS->addBasicBlock(NewBB, DomSet); 101eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner } 102eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 103eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // Should we update ImmdediateDominator information? 104eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner if (ImmediateDominators *ID = 105eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner P->getAnalysisToUpdate<ImmediateDominators>()) { 106eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // TIBB is the new immediate dominator for NewBB. NewBB doesn't dominate 107eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // anything. 108eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner ID->addNewBlock(NewBB, TIBB); 109eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner } 110eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 111eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // Should we update DominatorTree information? 112eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner if (DominatorTree *DT = P->getAnalysisToUpdate<DominatorTree>()) { 113eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner DominatorTree::Node *TINode = DT->getNode(TIBB); 114eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 115eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // The new block is not the immediate dominator for any other nodes, but 116eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // TINode is the immediate dominator for the new node. 117eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner // 118eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner DT->createNewNode(NewBB, TINode); 119eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner } 120eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner } 121eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner} 122eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner 123d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner// runOnFunction - Loop over all of the edges in the CFG, breaking critical 124d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner// edges as they are found. 125d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner// 126d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattnerbool BreakCriticalEdges::runOnFunction(Function &F) { 127d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner bool Changed = false; 128d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) { 129d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner TerminatorInst *TI = I->getTerminator(); 130eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner if (TI->getNumSuccessors() > 1) 131eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 132eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner if (isCriticalEdge(TI, i)) { 133eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner SplitCriticalEdge(TI, i, this); 134eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner ++NumBroken; 135eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner Changed = true; 136eb0456c8fd60e6c2ef844d8696baa39d5d55f082Chris Lattner } 137d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner } 138d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner 139d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner return Changed; 140d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner} 141