1 //===- BreakCriticalEdges.cpp - Critical Edge Elimination Pass ------------===//
3 // BreakCriticalEdges pass - Break all of the critical edges in the CFG by
4 // inserting a dummy basic block. This pass may be "required" by passes that
5 // cannot deal with critical edges. For this usage, the structure type is
6 // forward declared. This pass obviously invalidates the CFG, but can update
7 // forward dominator (set, immediate dominators, and tree) information.
9 //===----------------------------------------------------------------------===//
11 #include "llvm/Transforms/Scalar.h"
12 #include "llvm/Transforms/Utils/Local.h"
13 #include "llvm/Analysis/Dominators.h"
14 #include "llvm/Function.h"
15 #include "llvm/InstrTypes.h"
16 #include "Support/StatisticReporter.h"
18 static Statistic<> NumBroken("break-crit-edges\t- Number of blocks inserted");
20 class BreakCriticalEdges : public FunctionPass {
22 virtual bool runOnFunction(Function &F);
24 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
25 AU.addPreserved<DominatorSet>();
26 AU.addPreserved<ImmediateDominators>();
27 AU.addPreserved<DominatorTree>();
31 static RegisterOpt<BreakCriticalEdges> X("break-crit-edges",
32 "Break critical edges in CFG");
34 Pass *createBreakCriticalEdgesPass() { return new BreakCriticalEdges(); }
36 // runOnFunction - Loop over all of the edges in the CFG, breaking critical
37 // edges as they are found.
39 bool BreakCriticalEdges::runOnFunction(Function &F) {
41 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
42 TerminatorInst *TI = I->getTerminator();
43 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
44 if (isCriticalEdge(TI, i)) {
45 SplitCriticalEdge(TI, i, this);