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