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 namespace {
  19   Statistic<> NumBroken("break-crit-edges\t- Number of blocks inserted");
  20
  21   struct BreakCriticalEdges : public FunctionPass {
  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   RegisterOpt<BreakCriticalEdges> X("break-crit-edges",
  32                                     "Break critical edges in CFG");
  33 }
  34
  35 const PassInfo *BreakCriticalEdgesID = X.getPassInfo();
  36
  37 Pass *createBreakCriticalEdgesPass() { return new BreakCriticalEdges(); }
  38
  39 // runOnFunction - Loop over all of the edges in the CFG, breaking critical
  40 // edges as they are found.
  41 //
  42 bool BreakCriticalEdges::runOnFunction(Function &F) {
  43   bool Changed = false;
  44   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
  45     TerminatorInst *TI = I->getTerminator();
  46     for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
  47       if (isCriticalEdge(TI, i)) {
  48         SplitCriticalEdge(TI, i, this);
  49         ++NumBroken;
  50         Changed = true;
  51       }
  52   }
  53
  54   return Changed;
  55 }