Home | History | Annotate | Download | only in Utils
      1 //===- BreakCriticalEdges.cpp - Critical Edge Elimination Pass ------------===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // 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 // dominator trees.
     15 //
     16 //===----------------------------------------------------------------------===//
     17 
     18 #define DEBUG_TYPE "break-crit-edges"
     19 #include "llvm/Transforms/Scalar.h"
     20 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
     21 #include "llvm/Analysis/Dominators.h"
     22 #include "llvm/Analysis/LoopInfo.h"
     23 #include "llvm/Analysis/ProfileInfo.h"
     24 #include "llvm/Function.h"
     25 #include "llvm/Instructions.h"
     26 #include "llvm/Type.h"
     27 #include "llvm/Support/CFG.h"
     28 #include "llvm/Support/ErrorHandling.h"
     29 #include "llvm/ADT/SmallVector.h"
     30 #include "llvm/ADT/Statistic.h"
     31 using namespace llvm;
     32 
     33 STATISTIC(NumBroken, "Number of blocks inserted");
     34 
     35 namespace {
     36   struct BreakCriticalEdges : public FunctionPass {
     37     static char ID; // Pass identification, replacement for typeid
     38     BreakCriticalEdges() : FunctionPass(ID) {
     39       initializeBreakCriticalEdgesPass(*PassRegistry::getPassRegistry());
     40     }
     41 
     42     virtual bool runOnFunction(Function &F);
     43 
     44     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
     45       AU.addPreserved<DominatorTree>();
     46       AU.addPreserved<LoopInfo>();
     47       AU.addPreserved<ProfileInfo>();
     48 
     49       // No loop canonicalization guarantees are broken by this pass.
     50       AU.addPreservedID(LoopSimplifyID);
     51     }
     52   };
     53 }
     54 
     55 char BreakCriticalEdges::ID = 0;
     56 INITIALIZE_PASS(BreakCriticalEdges, "break-crit-edges",
     57                 "Break critical edges in CFG", false, false)
     58 
     59 // Publicly exposed interface to pass...
     60 char &llvm::BreakCriticalEdgesID = BreakCriticalEdges::ID;
     61 FunctionPass *llvm::createBreakCriticalEdgesPass() {
     62   return new BreakCriticalEdges();
     63 }
     64 
     65 // runOnFunction - Loop over all of the edges in the CFG, breaking critical
     66 // edges as they are found.
     67 //
     68 bool BreakCriticalEdges::runOnFunction(Function &F) {
     69   bool Changed = false;
     70   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
     71     TerminatorInst *TI = I->getTerminator();
     72     if (TI->getNumSuccessors() > 1 && !isa<IndirectBrInst>(TI))
     73       for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
     74         if (SplitCriticalEdge(TI, i, this)) {
     75           ++NumBroken;
     76           Changed = true;
     77         }
     78   }
     79 
     80   return Changed;
     81 }
     82 
     83 //===----------------------------------------------------------------------===//
     84 //    Implementation of the external critical edge manipulation functions
     85 //===----------------------------------------------------------------------===//
     86 
     87 // isCriticalEdge - Return true if the specified edge is a critical edge.
     88 // Critical edges are edges from a block with multiple successors to a block
     89 // with multiple predecessors.
     90 //
     91 bool llvm::isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum,
     92                           bool AllowIdenticalEdges) {
     93   assert(SuccNum < TI->getNumSuccessors() && "Illegal edge specification!");
     94   if (TI->getNumSuccessors() == 1) return false;
     95 
     96   const BasicBlock *Dest = TI->getSuccessor(SuccNum);
     97   const_pred_iterator I = pred_begin(Dest), E = pred_end(Dest);
     98 
     99   // If there is more than one predecessor, this is a critical edge...
    100   assert(I != E && "No preds, but we have an edge to the block?");
    101   const BasicBlock *FirstPred = *I;
    102   ++I;        // Skip one edge due to the incoming arc from TI.
    103   if (!AllowIdenticalEdges)
    104     return I != E;
    105 
    106   // If AllowIdenticalEdges is true, then we allow this edge to be considered
    107   // non-critical iff all preds come from TI's block.
    108   while (I != E) {
    109     const BasicBlock *P = *I;
    110     if (P != FirstPred)
    111       return true;
    112     // Note: leave this as is until no one ever compiles with either gcc 4.0.1
    113     // or Xcode 2. This seems to work around the pred_iterator assert in PR 2207
    114     E = pred_end(P);
    115     ++I;
    116   }
    117   return false;
    118 }
    119 
    120 /// CreatePHIsForSplitLoopExit - When a loop exit edge is split, LCSSA form
    121 /// may require new PHIs in the new exit block. This function inserts the
    122 /// new PHIs, as needed.  Preds is a list of preds inside the loop, SplitBB
    123 /// is the new loop exit block, and DestBB is the old loop exit, now the
    124 /// successor of SplitBB.
    125 static void CreatePHIsForSplitLoopExit(SmallVectorImpl<BasicBlock *> &Preds,
    126                                        BasicBlock *SplitBB,
    127                                        BasicBlock *DestBB) {
    128   // SplitBB shouldn't have anything non-trivial in it yet.
    129   assert(SplitBB->getFirstNonPHI() == SplitBB->getTerminator() &&
    130          "SplitBB has non-PHI nodes!");
    131 
    132   // For each PHI in the destination block...
    133   for (BasicBlock::iterator I = DestBB->begin();
    134        PHINode *PN = dyn_cast<PHINode>(I); ++I) {
    135     unsigned Idx = PN->getBasicBlockIndex(SplitBB);
    136     Value *V = PN->getIncomingValue(Idx);
    137     // If the input is a PHI which already satisfies LCSSA, don't create
    138     // a new one.
    139     if (const PHINode *VP = dyn_cast<PHINode>(V))
    140       if (VP->getParent() == SplitBB)
    141         continue;
    142     // Otherwise a new PHI is needed. Create one and populate it.
    143     PHINode *NewPN = PHINode::Create(PN->getType(), Preds.size(), "split",
    144                                      SplitBB->getTerminator());
    145     for (unsigned i = 0, e = Preds.size(); i != e; ++i)
    146       NewPN->addIncoming(V, Preds[i]);
    147     // Update the original PHI.
    148     PN->setIncomingValue(Idx, NewPN);
    149   }
    150 }
    151 
    152 /// SplitCriticalEdge - If this edge is a critical edge, insert a new node to
    153 /// split the critical edge.  This will update DominatorTree information if it
    154 /// is available, thus calling this pass will not invalidate either of them.
    155 /// This returns the new block if the edge was split, null otherwise.
    156 ///
    157 /// If MergeIdenticalEdges is true (not the default), *all* edges from TI to the
    158 /// specified successor will be merged into the same critical edge block.
    159 /// This is most commonly interesting with switch instructions, which may
    160 /// have many edges to any one destination.  This ensures that all edges to that
    161 /// dest go to one block instead of each going to a different block, but isn't
    162 /// the standard definition of a "critical edge".
    163 ///
    164 /// It is invalid to call this function on a critical edge that starts at an
    165 /// IndirectBrInst.  Splitting these edges will almost always create an invalid
    166 /// program because the address of the new block won't be the one that is jumped
    167 /// to.
    168 ///
    169 BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum,
    170                                     Pass *P, bool MergeIdenticalEdges,
    171                                     bool DontDeleteUselessPhis) {
    172   if (!isCriticalEdge(TI, SuccNum, MergeIdenticalEdges)) return 0;
    173 
    174   assert(!isa<IndirectBrInst>(TI) &&
    175          "Cannot split critical edge from IndirectBrInst");
    176 
    177   BasicBlock *TIBB = TI->getParent();
    178   BasicBlock *DestBB = TI->getSuccessor(SuccNum);
    179 
    180   // Splitting the critical edge to a landing pad block is non-trivial. Don't do
    181   // it in this generic function.
    182   if (DestBB->isLandingPad()) return 0;
    183 
    184   // Create a new basic block, linking it into the CFG.
    185   BasicBlock *NewBB = BasicBlock::Create(TI->getContext(),
    186                       TIBB->getName() + "." + DestBB->getName() + "_crit_edge");
    187   // Create our unconditional branch.
    188   BranchInst *NewBI = BranchInst::Create(DestBB, NewBB);
    189   NewBI->setDebugLoc(TI->getDebugLoc());
    190 
    191   // Branch to the new block, breaking the edge.
    192   TI->setSuccessor(SuccNum, NewBB);
    193 
    194   // Insert the block into the function... right after the block TI lives in.
    195   Function &F = *TIBB->getParent();
    196   Function::iterator FBBI = TIBB;
    197   F.getBasicBlockList().insert(++FBBI, NewBB);
    198 
    199   // If there are any PHI nodes in DestBB, we need to update them so that they
    200   // merge incoming values from NewBB instead of from TIBB.
    201   {
    202     unsigned BBIdx = 0;
    203     for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) {
    204       // We no longer enter through TIBB, now we come in through NewBB.
    205       // Revector exactly one entry in the PHI node that used to come from
    206       // TIBB to come from NewBB.
    207       PHINode *PN = cast<PHINode>(I);
    208 
    209       // Reuse the previous value of BBIdx if it lines up.  In cases where we
    210       // have multiple phi nodes with *lots* of predecessors, this is a speed
    211       // win because we don't have to scan the PHI looking for TIBB.  This
    212       // happens because the BB list of PHI nodes are usually in the same
    213       // order.
    214       if (PN->getIncomingBlock(BBIdx) != TIBB)
    215         BBIdx = PN->getBasicBlockIndex(TIBB);
    216       PN->setIncomingBlock(BBIdx, NewBB);
    217     }
    218   }
    219 
    220   // If there are any other edges from TIBB to DestBB, update those to go
    221   // through the split block, making those edges non-critical as well (and
    222   // reducing the number of phi entries in the DestBB if relevant).
    223   if (MergeIdenticalEdges) {
    224     for (unsigned i = SuccNum+1, e = TI->getNumSuccessors(); i != e; ++i) {
    225       if (TI->getSuccessor(i) != DestBB) continue;
    226 
    227       // Remove an entry for TIBB from DestBB phi nodes.
    228       DestBB->removePredecessor(TIBB, DontDeleteUselessPhis);
    229 
    230       // We found another edge to DestBB, go to NewBB instead.
    231       TI->setSuccessor(i, NewBB);
    232     }
    233   }
    234 
    235 
    236 
    237   // If we don't have a pass object, we can't update anything...
    238   if (P == 0) return NewBB;
    239 
    240   DominatorTree *DT = P->getAnalysisIfAvailable<DominatorTree>();
    241   LoopInfo *LI = P->getAnalysisIfAvailable<LoopInfo>();
    242   ProfileInfo *PI = P->getAnalysisIfAvailable<ProfileInfo>();
    243 
    244   // If we have nothing to update, just return.
    245   if (DT == 0 && LI == 0 && PI == 0)
    246     return NewBB;
    247 
    248   // Now update analysis information.  Since the only predecessor of NewBB is
    249   // the TIBB, TIBB clearly dominates NewBB.  TIBB usually doesn't dominate
    250   // anything, as there are other successors of DestBB.  However, if all other
    251   // predecessors of DestBB are already dominated by DestBB (e.g. DestBB is a
    252   // loop header) then NewBB dominates DestBB.
    253   SmallVector<BasicBlock*, 8> OtherPreds;
    254 
    255   // If there is a PHI in the block, loop over predecessors with it, which is
    256   // faster than iterating pred_begin/end.
    257   if (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) {
    258     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
    259       if (PN->getIncomingBlock(i) != NewBB)
    260         OtherPreds.push_back(PN->getIncomingBlock(i));
    261   } else {
    262     for (pred_iterator I = pred_begin(DestBB), E = pred_end(DestBB);
    263          I != E; ++I) {
    264       BasicBlock *P = *I;
    265       if (P != NewBB)
    266         OtherPreds.push_back(P);
    267     }
    268   }
    269 
    270   bool NewBBDominatesDestBB = true;
    271 
    272   // Should we update DominatorTree information?
    273   if (DT) {
    274     DomTreeNode *TINode = DT->getNode(TIBB);
    275 
    276     // The new block is not the immediate dominator for any other nodes, but
    277     // TINode is the immediate dominator for the new node.
    278     //
    279     if (TINode) {       // Don't break unreachable code!
    280       DomTreeNode *NewBBNode = DT->addNewBlock(NewBB, TIBB);
    281       DomTreeNode *DestBBNode = 0;
    282 
    283       // If NewBBDominatesDestBB hasn't been computed yet, do so with DT.
    284       if (!OtherPreds.empty()) {
    285         DestBBNode = DT->getNode(DestBB);
    286         while (!OtherPreds.empty() && NewBBDominatesDestBB) {
    287           if (DomTreeNode *OPNode = DT->getNode(OtherPreds.back()))
    288             NewBBDominatesDestBB = DT->dominates(DestBBNode, OPNode);
    289           OtherPreds.pop_back();
    290         }
    291         OtherPreds.clear();
    292       }
    293 
    294       // If NewBBDominatesDestBB, then NewBB dominates DestBB, otherwise it
    295       // doesn't dominate anything.
    296       if (NewBBDominatesDestBB) {
    297         if (!DestBBNode) DestBBNode = DT->getNode(DestBB);
    298         DT->changeImmediateDominator(DestBBNode, NewBBNode);
    299       }
    300     }
    301   }
    302 
    303   // Update LoopInfo if it is around.
    304   if (LI) {
    305     if (Loop *TIL = LI->getLoopFor(TIBB)) {
    306       // If one or the other blocks were not in a loop, the new block is not
    307       // either, and thus LI doesn't need to be updated.
    308       if (Loop *DestLoop = LI->getLoopFor(DestBB)) {
    309         if (TIL == DestLoop) {
    310           // Both in the same loop, the NewBB joins loop.
    311           DestLoop->addBasicBlockToLoop(NewBB, LI->getBase());
    312         } else if (TIL->contains(DestLoop)) {
    313           // Edge from an outer loop to an inner loop.  Add to the outer loop.
    314           TIL->addBasicBlockToLoop(NewBB, LI->getBase());
    315         } else if (DestLoop->contains(TIL)) {
    316           // Edge from an inner loop to an outer loop.  Add to the outer loop.
    317           DestLoop->addBasicBlockToLoop(NewBB, LI->getBase());
    318         } else {
    319           // Edge from two loops with no containment relation.  Because these
    320           // are natural loops, we know that the destination block must be the
    321           // header of its loop (adding a branch into a loop elsewhere would
    322           // create an irreducible loop).
    323           assert(DestLoop->getHeader() == DestBB &&
    324                  "Should not create irreducible loops!");
    325           if (Loop *P = DestLoop->getParentLoop())
    326             P->addBasicBlockToLoop(NewBB, LI->getBase());
    327         }
    328       }
    329       // If TIBB is in a loop and DestBB is outside of that loop, split the
    330       // other exit blocks of the loop that also have predecessors outside
    331       // the loop, to maintain a LoopSimplify guarantee.
    332       if (!TIL->contains(DestBB) &&
    333           P->mustPreserveAnalysisID(LoopSimplifyID)) {
    334         assert(!TIL->contains(NewBB) &&
    335                "Split point for loop exit is contained in loop!");
    336 
    337         // Update LCSSA form in the newly created exit block.
    338         if (P->mustPreserveAnalysisID(LCSSAID)) {
    339           SmallVector<BasicBlock *, 1> OrigPred;
    340           OrigPred.push_back(TIBB);
    341           CreatePHIsForSplitLoopExit(OrigPred, NewBB, DestBB);
    342         }
    343 
    344         // For each unique exit block...
    345         // FIXME: This code is functionally equivalent to the corresponding
    346         // loop in LoopSimplify.
    347         SmallVector<BasicBlock *, 4> ExitBlocks;
    348         TIL->getExitBlocks(ExitBlocks);
    349         for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
    350           // Collect all the preds that are inside the loop, and note
    351           // whether there are any preds outside the loop.
    352           SmallVector<BasicBlock *, 4> Preds;
    353           bool HasPredOutsideOfLoop = false;
    354           BasicBlock *Exit = ExitBlocks[i];
    355           for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit);
    356                I != E; ++I) {
    357             BasicBlock *P = *I;
    358             if (TIL->contains(P)) {
    359               if (isa<IndirectBrInst>(P->getTerminator())) {
    360                 Preds.clear();
    361                 break;
    362               }
    363               Preds.push_back(P);
    364             } else {
    365               HasPredOutsideOfLoop = true;
    366             }
    367           }
    368           // If there are any preds not in the loop, we'll need to split
    369           // the edges. The Preds.empty() check is needed because a block
    370           // may appear multiple times in the list. We can't use
    371           // getUniqueExitBlocks above because that depends on LoopSimplify
    372           // form, which we're in the process of restoring!
    373           if (!Preds.empty() && HasPredOutsideOfLoop) {
    374             BasicBlock *NewExitBB =
    375               SplitBlockPredecessors(Exit, Preds, "split", P);
    376             if (P->mustPreserveAnalysisID(LCSSAID))
    377               CreatePHIsForSplitLoopExit(Preds, NewExitBB, Exit);
    378           }
    379         }
    380       }
    381       // LCSSA form was updated above for the case where LoopSimplify is
    382       // available, which means that all predecessors of loop exit blocks
    383       // are within the loop. Without LoopSimplify form, it would be
    384       // necessary to insert a new phi.
    385       assert((!P->mustPreserveAnalysisID(LCSSAID) ||
    386               P->mustPreserveAnalysisID(LoopSimplifyID)) &&
    387              "SplitCriticalEdge doesn't know how to update LCCSA form "
    388              "without LoopSimplify!");
    389     }
    390   }
    391 
    392   // Update ProfileInfo if it is around.
    393   if (PI)
    394     PI->splitEdge(TIBB, DestBB, NewBB, MergeIdenticalEdges);
    395 
    396   return NewBB;
    397 }
    398