BreakCriticalEdges.cpp revision d76efa018660e806cd87c0a24512e3c532fc1d36
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/Transforms/Utils/Local.h" 13d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner#include "llvm/Analysis/Dominators.h" 14d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner#include "llvm/Function.h" 15d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner#include "llvm/InstrTypes.h" 16d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner#include "Support/StatisticReporter.h" 17d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner 18d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattnerstatic Statistic<> NumBroken("break-crit-edges\t- Number of blocks inserted"); 19d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner 20d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattnerclass BreakCriticalEdges : public FunctionPass { 21d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattnerpublic: 22d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner virtual bool runOnFunction(Function &F); 23d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner 24d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 25d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner AU.addPreserved<DominatorSet>(); 26d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner AU.addPreserved<ImmediateDominators>(); 27d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner AU.addPreserved<DominatorTree>(); 28d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner } 29d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner}; 30d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner 31d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattnerstatic RegisterOpt<BreakCriticalEdges> X("break-crit-edges", 32d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner "Break critical edges in CFG"); 33d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner 34d76efa018660e806cd87c0a24512e3c532fc1d36Chris LattnerPass *createBreakCriticalEdgesPass() { return new BreakCriticalEdges(); } 35d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner 36d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner// runOnFunction - Loop over all of the edges in the CFG, breaking critical 37d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner// edges as they are found. 38d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner// 39d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattnerbool BreakCriticalEdges::runOnFunction(Function &F) { 40d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner bool Changed = false; 41d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) { 42d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner TerminatorInst *TI = I->getTerminator(); 43d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 44d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner if (isCriticalEdge(TI, i)) { 45d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner SplitCriticalEdge(TI, i, this); 46d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner ++NumBroken; 47d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner Changed = true; 48d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner } 49d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner } 50d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner 51d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner return Changed; 52d76efa018660e806cd87c0a24512e3c532fc1d36Chris Lattner} 53