lib/Transforms/Utils/BreakCriticalEdges.cpp

   1 //===- BreakCriticalEdges.cpp - Critical Edge Elimination Pass ------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // BreakCriticalEdges pass - Break all of the critical edges in the CFG by
  11 // inserting a dummy basic block.  This pass may be "required" by passes that
  12 // cannot deal with critical edges.  For this usage, the structure type is
  13 // forward declared.  This pass obviously invalidates the CFG, but can update
  14 // forward dominator (set, immediate dominators, and tree) information.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #include "llvm/Transforms/Scalar.h"
  19 #include "llvm/Analysis/Dominators.h"
  20 #include "llvm/Function.h"
  21 #include "llvm/iTerminators.h"
  22 #include "llvm/iPHINode.h"
  23 #include "llvm/Support/CFG.h"
  24 #include "Support/Statistic.h"
  25
  26 namespace {
  27   Statistic<> NumBroken("break-crit-edges", "Number of blocks inserted");
  28
  29   struct BreakCriticalEdges : public FunctionPass {
  30     virtual bool runOnFunction(Function &F);
  31
  32     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  33       AU.addPreserved<DominatorSet>();
  34       AU.addPreserved<ImmediateDominators>();
  35       AU.addPreserved<DominatorTree>();
  36       AU.addPreserved<DominanceFrontier>();
  37
  38       // No loop canonicalization guarantees are broken by this pass.
  39       AU.addPreservedID(LoopSimplifyID);
  40     }
  41   };
  42
  43   RegisterOpt<BreakCriticalEdges> X("break-crit-edges",
  44                                     "Break critical edges in CFG");
  45 }
  46
  47 // Publically exposed interface to pass...
  48 const PassInfo *BreakCriticalEdgesID = X.getPassInfo();
  49 Pass *createBreakCriticalEdgesPass() { return new BreakCriticalEdges(); }
  50
  51
  52 // isCriticalEdge - Return true if the specified edge is a critical edge.
  53 // Critical edges are edges from a block with multiple successors to a block
  54 // with multiple predecessors.
  55 //
  56 bool isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum) {
  57   assert(SuccNum < TI->getNumSuccessors() && "Illegal edge specification!");
  58   if (TI->getNumSuccessors() == 1) return false;
  59
  60   const BasicBlock *Dest = TI->getSuccessor(SuccNum);
  61   pred_const_iterator I = pred_begin(Dest), E = pred_end(Dest);
  62
  63   // If there is more than one predecessor, this is a critical edge...
  64   assert(I != E && "No preds, but we have an edge to the block?");
  65   ++I;        // Skip one edge due to the incoming arc from TI.
  66   return I != E;
  67 }
  68
  69 // SplitCriticalEdge - Insert a new node node to split the critical edge.  This
  70 // will update DominatorSet, ImmediateDominator and DominatorTree information if
  71 // it is available, thus calling this pass will not invalidate either of them.
  72 //
  73 void SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P) {
  74   assert(isCriticalEdge(TI, SuccNum) &&
  75          "Cannot break a critical edge, if it isn't a critical edge");
  76   BasicBlock *TIBB = TI->getParent();
  77   BasicBlock *DestBB = TI->getSuccessor(SuccNum);
  78
  79   // Create a new basic block, linking it into the CFG.
  80   BasicBlock *NewBB = new BasicBlock(TIBB->getName() + "." +
  81                                      DestBB->getName() + "_crit_edge");
  82   // Create our unconditional branch...
  83   BranchInst *BI = new BranchInst(DestBB);
  84   NewBB->getInstList().push_back(BI);
  85
  86   // Branch to the new block, breaking the edge...
  87   TI->setSuccessor(SuccNum, NewBB);
  88
  89   // Insert the block into the function... right after the block TI lives in.
  90   Function &F = *TIBB->getParent();
  91   F.getBasicBlockList().insert(TIBB->getNext(), NewBB);
  92
  93   // If there are any PHI nodes in DestBB, we need to update them so that they
  94   // merge incoming values from NewBB instead of from TIBB.
  95   //
  96   for (BasicBlock::iterator I = DestBB->begin();
  97        PHINode *PN = dyn_cast<PHINode>(I); ++I) {
  98     // We no longer enter through TIBB, now we come in through NewBB.
  99     PN->replaceUsesOfWith(TIBB, NewBB);
 100   }
 101
 102   // If we don't have a pass object, we can't update anything...
 103   if (P == 0) return;
 104
 105   // Now update analysis information.  These are the analyses that we are
 106   // currently capable of updating...
 107   //
 108
 109   // Should we update DominatorSet information?
 110   if (DominatorSet *DS = P->getAnalysisToUpdate<DominatorSet>()) {
 111     // The blocks that dominate the new one are the blocks that dominate TIBB
 112     // plus the new block itself.
 113     DominatorSet::DomSetType DomSet = DS->getDominators(TIBB);
 114     DomSet.insert(NewBB);  // A block always dominates itself.
 115     DS->addBasicBlock(NewBB, DomSet);
 116   }
 117
 118   // Should we update ImmediateDominator information?
 119   if (ImmediateDominators *ID = P->getAnalysisToUpdate<ImmediateDominators>()) {
 120     // TIBB is the new immediate dominator for NewBB.  NewBB doesn't dominate
 121     // anything.
 122     ID->addNewBlock(NewBB, TIBB);
 123   }
 124
 125   // Should we update DominatorTree information?
 126   if (DominatorTree *DT = P->getAnalysisToUpdate<DominatorTree>()) {
 127     DominatorTree::Node *TINode = DT->getNode(TIBB);
 128
 129     // The new block is not the immediate dominator for any other nodes, but
 130     // TINode is the immediate dominator for the new node.
 131     //
 132     if (TINode)        // Don't break unreachable code!
 133       DT->createNewNode(NewBB, TINode);
 134   }
 135
 136   // Should we update DominanceFrontier information?
 137   if (DominanceFrontier *DF = P->getAnalysisToUpdate<DominanceFrontier>()) {
 138     // Since the new block is dominated by its only predecessor TIBB,
 139     // it cannot be in any block's dominance frontier.  Its dominance
 140     // frontier is {DestBB}.
 141     DominanceFrontier::DomSetType NewDFSet;
 142     NewDFSet.insert(DestBB);
 143     DF->addBasicBlock(NewBB, NewDFSet);
 144   }
 145 }
 146
 147 // runOnFunction - Loop over all of the edges in the CFG, breaking critical
 148 // edges as they are found.
 149 //
 150 bool BreakCriticalEdges::runOnFunction(Function &F) {
 151   bool Changed = false;
 152   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
 153     TerminatorInst *TI = I->getTerminator();
 154     if (TI->getNumSuccessors() > 1)
 155       for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
 156         if (isCriticalEdge(TI, i)) {
 157           SplitCriticalEdge(TI, i, this);
 158           ++NumBroken;
 159           Changed = true;
 160         }
 161   }
 162
 163   return Changed;
 164 }