lib/Transforms/Utils/BreakCriticalEdges.cpp

   1 //===- BreakCriticalEdges.cpp - Critical Edge Elimination Pass ------------===//
   2 //
   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.
   8 //
   9 //===----------------------------------------------------------------------===//
  10
  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"
  17
  18 static Statistic<> NumBroken("break-crit-edges\t- Number of blocks inserted");
  19
  20 class BreakCriticalEdges : public FunctionPass {
  21 public:
  22   virtual bool runOnFunction(Function &F);
  23
  24   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  25     AU.addPreserved<DominatorSet>();
  26     AU.addPreserved<ImmediateDominators>();
  27     AU.addPreserved<DominatorTree>();
  28   }
  29 };
  30
  31 static RegisterOpt<BreakCriticalEdges> X("break-crit-edges",
  32                                          "Break critical edges in CFG");
  33
  34 Pass *createBreakCriticalEdgesPass() { return new BreakCriticalEdges(); }
  35
  36 // runOnFunction - Loop over all of the edges in the CFG, breaking critical
  37 // edges as they are found.
  38 //
  39 bool BreakCriticalEdges::runOnFunction(Function &F) {
  40   bool Changed = false;
  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);
  46         ++NumBroken;
  47         Changed = true;
  48       }
  49   }
  50
  51   return Changed;
  52 }