LLVM API Documentation

BreakCriticalEdges.cpp
Go to the documentation of this file.
00001 //===- BreakCriticalEdges.cpp - Critical Edge Elimination Pass ------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // BreakCriticalEdges pass - Break all of the critical edges in the CFG by
00011 // inserting a dummy basic block.  This pass may be "required" by passes that
00012 // cannot deal with critical edges.  For this usage, the structure type is
00013 // forward declared.  This pass obviously invalidates the CFG, but can update
00014 // dominator trees.
00015 //
00016 //===----------------------------------------------------------------------===//
00017 
00018 #include "llvm/Transforms/Scalar.h"
00019 #include "llvm/ADT/SmallVector.h"
00020 #include "llvm/ADT/Statistic.h"
00021 #include "llvm/Analysis/CFG.h"
00022 #include "llvm/Analysis/LoopInfo.h"
00023 #include "llvm/IR/CFG.h"
00024 #include "llvm/IR/Dominators.h"
00025 #include "llvm/IR/Function.h"
00026 #include "llvm/IR/Instructions.h"
00027 #include "llvm/IR/Type.h"
00028 #include "llvm/Support/ErrorHandling.h"
00029 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
00030 using namespace llvm;
00031 
00032 #define DEBUG_TYPE "break-crit-edges"
00033 
00034 STATISTIC(NumBroken, "Number of blocks inserted");
00035 
00036 namespace {
00037   struct BreakCriticalEdges : public FunctionPass {
00038     static char ID; // Pass identification, replacement for typeid
00039     BreakCriticalEdges() : FunctionPass(ID) {
00040       initializeBreakCriticalEdgesPass(*PassRegistry::getPassRegistry());
00041     }
00042 
00043     bool runOnFunction(Function &F) override {
00044       unsigned N = SplitAllCriticalEdges(F, this);
00045       NumBroken += N;
00046       return N > 0;
00047     }
00048 
00049     void getAnalysisUsage(AnalysisUsage &AU) const override {
00050       AU.addPreserved<DominatorTreeWrapperPass>();
00051       AU.addPreserved<LoopInfo>();
00052 
00053       // No loop canonicalization guarantees are broken by this pass.
00054       AU.addPreservedID(LoopSimplifyID);
00055     }
00056   };
00057 }
00058 
00059 char BreakCriticalEdges::ID = 0;
00060 INITIALIZE_PASS(BreakCriticalEdges, "break-crit-edges",
00061                 "Break critical edges in CFG", false, false)
00062 
00063 // Publicly exposed interface to pass...
00064 char &llvm::BreakCriticalEdgesID = BreakCriticalEdges::ID;
00065 FunctionPass *llvm::createBreakCriticalEdgesPass() {
00066   return new BreakCriticalEdges();
00067 }
00068 
00069 //===----------------------------------------------------------------------===//
00070 //    Implementation of the external critical edge manipulation functions
00071 //===----------------------------------------------------------------------===//
00072 
00073 /// createPHIsForSplitLoopExit - When a loop exit edge is split, LCSSA form
00074 /// may require new PHIs in the new exit block. This function inserts the
00075 /// new PHIs, as needed. Preds is a list of preds inside the loop, SplitBB
00076 /// is the new loop exit block, and DestBB is the old loop exit, now the
00077 /// successor of SplitBB.
00078 static void createPHIsForSplitLoopExit(ArrayRef<BasicBlock *> Preds,
00079                                        BasicBlock *SplitBB,
00080                                        BasicBlock *DestBB) {
00081   // SplitBB shouldn't have anything non-trivial in it yet.
00082   assert((SplitBB->getFirstNonPHI() == SplitBB->getTerminator() ||
00083           SplitBB->isLandingPad()) && "SplitBB has non-PHI nodes!");
00084 
00085   // For each PHI in the destination block.
00086   for (BasicBlock::iterator I = DestBB->begin();
00087        PHINode *PN = dyn_cast<PHINode>(I); ++I) {
00088     unsigned Idx = PN->getBasicBlockIndex(SplitBB);
00089     Value *V = PN->getIncomingValue(Idx);
00090 
00091     // If the input is a PHI which already satisfies LCSSA, don't create
00092     // a new one.
00093     if (const PHINode *VP = dyn_cast<PHINode>(V))
00094       if (VP->getParent() == SplitBB)
00095         continue;
00096 
00097     // Otherwise a new PHI is needed. Create one and populate it.
00098     PHINode *NewPN =
00099       PHINode::Create(PN->getType(), Preds.size(), "split",
00100                       SplitBB->isLandingPad() ?
00101                       SplitBB->begin() : SplitBB->getTerminator());
00102     for (unsigned i = 0, e = Preds.size(); i != e; ++i)
00103       NewPN->addIncoming(V, Preds[i]);
00104 
00105     // Update the original PHI.
00106     PN->setIncomingValue(Idx, NewPN);
00107   }
00108 }
00109 
00110 /// SplitCriticalEdge - If this edge is a critical edge, insert a new node to
00111 /// split the critical edge.  This will update DominatorTree information if it
00112 /// is available, thus calling this pass will not invalidate either of them.
00113 /// This returns the new block if the edge was split, null otherwise.
00114 ///
00115 /// If MergeIdenticalEdges is true (not the default), *all* edges from TI to the
00116 /// specified successor will be merged into the same critical edge block.
00117 /// This is most commonly interesting with switch instructions, which may
00118 /// have many edges to any one destination.  This ensures that all edges to that
00119 /// dest go to one block instead of each going to a different block, but isn't
00120 /// the standard definition of a "critical edge".
00121 ///
00122 /// It is invalid to call this function on a critical edge that starts at an
00123 /// IndirectBrInst.  Splitting these edges will almost always create an invalid
00124 /// program because the address of the new block won't be the one that is jumped
00125 /// to.
00126 ///
00127 BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum,
00128                                     Pass *P, bool MergeIdenticalEdges,
00129                                     bool DontDeleteUselessPhis,
00130                                     bool SplitLandingPads) {
00131   if (!isCriticalEdge(TI, SuccNum, MergeIdenticalEdges)) return nullptr;
00132 
00133   assert(!isa<IndirectBrInst>(TI) &&
00134          "Cannot split critical edge from IndirectBrInst");
00135 
00136   BasicBlock *TIBB = TI->getParent();
00137   BasicBlock *DestBB = TI->getSuccessor(SuccNum);
00138 
00139   // Splitting the critical edge to a landing pad block is non-trivial. Don't do
00140   // it in this generic function.
00141   if (DestBB->isLandingPad()) return nullptr;
00142 
00143   // Create a new basic block, linking it into the CFG.
00144   BasicBlock *NewBB = BasicBlock::Create(TI->getContext(),
00145                       TIBB->getName() + "." + DestBB->getName() + "_crit_edge");
00146   // Create our unconditional branch.
00147   BranchInst *NewBI = BranchInst::Create(DestBB, NewBB);
00148   NewBI->setDebugLoc(TI->getDebugLoc());
00149 
00150   // Branch to the new block, breaking the edge.
00151   TI->setSuccessor(SuccNum, NewBB);
00152 
00153   // Insert the block into the function... right after the block TI lives in.
00154   Function &F = *TIBB->getParent();
00155   Function::iterator FBBI = TIBB;
00156   F.getBasicBlockList().insert(++FBBI, NewBB);
00157 
00158   // If there are any PHI nodes in DestBB, we need to update them so that they
00159   // merge incoming values from NewBB instead of from TIBB.
00160   {
00161     unsigned BBIdx = 0;
00162     for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) {
00163       // We no longer enter through TIBB, now we come in through NewBB.
00164       // Revector exactly one entry in the PHI node that used to come from
00165       // TIBB to come from NewBB.
00166       PHINode *PN = cast<PHINode>(I);
00167 
00168       // Reuse the previous value of BBIdx if it lines up.  In cases where we
00169       // have multiple phi nodes with *lots* of predecessors, this is a speed
00170       // win because we don't have to scan the PHI looking for TIBB.  This
00171       // happens because the BB list of PHI nodes are usually in the same
00172       // order.
00173       if (PN->getIncomingBlock(BBIdx) != TIBB)
00174         BBIdx = PN->getBasicBlockIndex(TIBB);
00175       PN->setIncomingBlock(BBIdx, NewBB);
00176     }
00177   }
00178 
00179   // If there are any other edges from TIBB to DestBB, update those to go
00180   // through the split block, making those edges non-critical as well (and
00181   // reducing the number of phi entries in the DestBB if relevant).
00182   if (MergeIdenticalEdges) {
00183     for (unsigned i = SuccNum+1, e = TI->getNumSuccessors(); i != e; ++i) {
00184       if (TI->getSuccessor(i) != DestBB) continue;
00185 
00186       // Remove an entry for TIBB from DestBB phi nodes.
00187       DestBB->removePredecessor(TIBB, DontDeleteUselessPhis);
00188 
00189       // We found another edge to DestBB, go to NewBB instead.
00190       TI->setSuccessor(i, NewBB);
00191     }
00192   }
00193 
00194 
00195 
00196   // If we don't have a pass object, we can't update anything...
00197   if (!P) return NewBB;
00198 
00199   DominatorTreeWrapperPass *DTWP =
00200       P->getAnalysisIfAvailable<DominatorTreeWrapperPass>();
00201   DominatorTree *DT = DTWP ? &DTWP->getDomTree() : nullptr;
00202   LoopInfo *LI = P->getAnalysisIfAvailable<LoopInfo>();
00203 
00204   // If we have nothing to update, just return.
00205   if (!DT && !LI)
00206     return NewBB;
00207 
00208   // Now update analysis information.  Since the only predecessor of NewBB is
00209   // the TIBB, TIBB clearly dominates NewBB.  TIBB usually doesn't dominate
00210   // anything, as there are other successors of DestBB.  However, if all other
00211   // predecessors of DestBB are already dominated by DestBB (e.g. DestBB is a
00212   // loop header) then NewBB dominates DestBB.
00213   SmallVector<BasicBlock*, 8> OtherPreds;
00214 
00215   // If there is a PHI in the block, loop over predecessors with it, which is
00216   // faster than iterating pred_begin/end.
00217   if (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) {
00218     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
00219       if (PN->getIncomingBlock(i) != NewBB)
00220         OtherPreds.push_back(PN->getIncomingBlock(i));
00221   } else {
00222     for (pred_iterator I = pred_begin(DestBB), E = pred_end(DestBB);
00223          I != E; ++I) {
00224       BasicBlock *P = *I;
00225       if (P != NewBB)
00226         OtherPreds.push_back(P);
00227     }
00228   }
00229 
00230   bool NewBBDominatesDestBB = true;
00231 
00232   // Should we update DominatorTree information?
00233   if (DT) {
00234     DomTreeNode *TINode = DT->getNode(TIBB);
00235 
00236     // The new block is not the immediate dominator for any other nodes, but
00237     // TINode is the immediate dominator for the new node.
00238     //
00239     if (TINode) {       // Don't break unreachable code!
00240       DomTreeNode *NewBBNode = DT->addNewBlock(NewBB, TIBB);
00241       DomTreeNode *DestBBNode = nullptr;
00242 
00243       // If NewBBDominatesDestBB hasn't been computed yet, do so with DT.
00244       if (!OtherPreds.empty()) {
00245         DestBBNode = DT->getNode(DestBB);
00246         while (!OtherPreds.empty() && NewBBDominatesDestBB) {
00247           if (DomTreeNode *OPNode = DT->getNode(OtherPreds.back()))
00248             NewBBDominatesDestBB = DT->dominates(DestBBNode, OPNode);
00249           OtherPreds.pop_back();
00250         }
00251         OtherPreds.clear();
00252       }
00253 
00254       // If NewBBDominatesDestBB, then NewBB dominates DestBB, otherwise it
00255       // doesn't dominate anything.
00256       if (NewBBDominatesDestBB) {
00257         if (!DestBBNode) DestBBNode = DT->getNode(DestBB);
00258         DT->changeImmediateDominator(DestBBNode, NewBBNode);
00259       }
00260     }
00261   }
00262 
00263   // Update LoopInfo if it is around.
00264   if (LI) {
00265     if (Loop *TIL = LI->getLoopFor(TIBB)) {
00266       // If one or the other blocks were not in a loop, the new block is not
00267       // either, and thus LI doesn't need to be updated.
00268       if (Loop *DestLoop = LI->getLoopFor(DestBB)) {
00269         if (TIL == DestLoop) {
00270           // Both in the same loop, the NewBB joins loop.
00271           DestLoop->addBasicBlockToLoop(NewBB, LI->getBase());
00272         } else if (TIL->contains(DestLoop)) {
00273           // Edge from an outer loop to an inner loop.  Add to the outer loop.
00274           TIL->addBasicBlockToLoop(NewBB, LI->getBase());
00275         } else if (DestLoop->contains(TIL)) {
00276           // Edge from an inner loop to an outer loop.  Add to the outer loop.
00277           DestLoop->addBasicBlockToLoop(NewBB, LI->getBase());
00278         } else {
00279           // Edge from two loops with no containment relation.  Because these
00280           // are natural loops, we know that the destination block must be the
00281           // header of its loop (adding a branch into a loop elsewhere would
00282           // create an irreducible loop).
00283           assert(DestLoop->getHeader() == DestBB &&
00284                  "Should not create irreducible loops!");
00285           if (Loop *P = DestLoop->getParentLoop())
00286             P->addBasicBlockToLoop(NewBB, LI->getBase());
00287         }
00288       }
00289       // If TIBB is in a loop and DestBB is outside of that loop, we may need
00290       // to update LoopSimplify form and LCSSA form.
00291       if (!TIL->contains(DestBB) &&
00292           P->mustPreserveAnalysisID(LoopSimplifyID)) {
00293         assert(!TIL->contains(NewBB) &&
00294                "Split point for loop exit is contained in loop!");
00295 
00296         // Update LCSSA form in the newly created exit block.
00297         if (P->mustPreserveAnalysisID(LCSSAID))
00298           createPHIsForSplitLoopExit(TIBB, NewBB, DestBB);
00299 
00300         // The only that we can break LoopSimplify form by splitting a critical
00301         // edge is if after the split there exists some edge from TIL to DestBB
00302         // *and* the only edge into DestBB from outside of TIL is that of
00303         // NewBB. If the first isn't true, then LoopSimplify still holds, NewBB
00304         // is the new exit block and it has no non-loop predecessors. If the
00305         // second isn't true, then DestBB was not in LoopSimplify form prior to
00306         // the split as it had a non-loop predecessor. In both of these cases,
00307         // the predecessor must be directly in TIL, not in a subloop, or again
00308         // LoopSimplify doesn't hold.
00309         SmallVector<BasicBlock *, 4> LoopPreds;
00310         for (pred_iterator I = pred_begin(DestBB), E = pred_end(DestBB); I != E;
00311              ++I) {
00312           BasicBlock *P = *I;
00313           if (P == NewBB)
00314             continue; // The new block is known.
00315           if (LI->getLoopFor(P) != TIL) {
00316             // No need to re-simplify, it wasn't to start with.
00317             LoopPreds.clear();
00318             break;
00319           }
00320           LoopPreds.push_back(P);
00321         }
00322         if (!LoopPreds.empty()) {
00323           assert(!DestBB->isLandingPad() &&
00324                  "We don't split edges to landing pads!");
00325           BasicBlock *NewExitBB =
00326               SplitBlockPredecessors(DestBB, LoopPreds, "split", P);
00327           if (P->mustPreserveAnalysisID(LCSSAID))
00328             createPHIsForSplitLoopExit(LoopPreds, NewExitBB, DestBB);
00329         }
00330       }
00331       // LCSSA form was updated above for the case where LoopSimplify is
00332       // available, which means that all predecessors of loop exit blocks
00333       // are within the loop. Without LoopSimplify form, it would be
00334       // necessary to insert a new phi.
00335       assert((!P->mustPreserveAnalysisID(LCSSAID) ||
00336               P->mustPreserveAnalysisID(LoopSimplifyID)) &&
00337              "SplitCriticalEdge doesn't know how to update LCCSA form "
00338              "without LoopSimplify!");
00339     }
00340   }
00341 
00342   return NewBB;
00343 }