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 was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source 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 // forward dominator (set, immediate dominators, tree, and frontier)
00015 // information.
00016 //
00017 //===----------------------------------------------------------------------===//
00018 
00019 #include "llvm/Transforms/Scalar.h"
00020 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
00021 #include "llvm/Analysis/Dominators.h"
00022 #include "llvm/Analysis/LoopInfo.h"
00023 #include "llvm/Function.h"
00024 #include "llvm/Instructions.h"
00025 #include "llvm/Type.h"
00026 #include "llvm/Support/CFG.h"
00027 #include "llvm/ADT/Statistic.h"
00028 using namespace llvm;
00029 
00030 namespace {
00031   Statistic<> NumBroken("break-crit-edges", "Number of blocks inserted");
00032 
00033   struct BreakCriticalEdges : public FunctionPass {
00034     virtual bool runOnFunction(Function &F);
00035 
00036     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00037       AU.addPreserved<ETForest>();
00038       AU.addPreserved<DominatorSet>();
00039       AU.addPreserved<ImmediateDominators>();
00040       AU.addPreserved<DominatorTree>();
00041       AU.addPreserved<DominanceFrontier>();
00042       AU.addPreserved<LoopInfo>();
00043 
00044       // No loop canonicalization guarantees are broken by this pass.
00045       AU.addPreservedID(LoopSimplifyID);
00046     }
00047   };
00048 
00049   RegisterOpt<BreakCriticalEdges> X("break-crit-edges",
00050                                     "Break critical edges in CFG");
00051 }
00052 
00053 // Publically exposed interface to pass...
00054 const PassInfo *llvm::BreakCriticalEdgesID = X.getPassInfo();
00055 FunctionPass *llvm::createBreakCriticalEdgesPass() {
00056   return new BreakCriticalEdges();
00057 }
00058 
00059 // runOnFunction - Loop over all of the edges in the CFG, breaking critical
00060 // edges as they are found.
00061 //
00062 bool BreakCriticalEdges::runOnFunction(Function &F) {
00063   bool Changed = false;
00064   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
00065     TerminatorInst *TI = I->getTerminator();
00066     if (TI->getNumSuccessors() > 1)
00067       for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
00068         if (SplitCriticalEdge(TI, i, this)) {
00069           ++NumBroken;
00070           Changed = true;
00071         }
00072   }
00073 
00074   return Changed;
00075 }
00076 
00077 //===----------------------------------------------------------------------===//
00078 //    Implementation of the external critical edge manipulation functions
00079 //===----------------------------------------------------------------------===//
00080 
00081 // isCriticalEdge - Return true if the specified edge is a critical edge.
00082 // Critical edges are edges from a block with multiple successors to a block
00083 // with multiple predecessors.
00084 //
00085 bool llvm::isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum) {
00086   assert(SuccNum < TI->getNumSuccessors() && "Illegal edge specification!");
00087   if (TI->getNumSuccessors() == 1) return false;
00088 
00089   const BasicBlock *Dest = TI->getSuccessor(SuccNum);
00090   pred_const_iterator I = pred_begin(Dest), E = pred_end(Dest);
00091 
00092   // If there is more than one predecessor, this is a critical edge...
00093   assert(I != E && "No preds, but we have an edge to the block?");
00094   ++I;        // Skip one edge due to the incoming arc from TI.
00095   return I != E;
00096 }
00097 
00098 // SplitCriticalEdge - If this edge is a critical edge, insert a new node to
00099 // split the critical edge.  This will update DominatorSet, ImmediateDominator,
00100 // DominatorTree, and DominatorFrontier information if it is available, thus
00101 // calling this pass will not invalidate either of them.  This returns true if
00102 // the edge was split, false otherwise.
00103 //
00104 bool llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P) {
00105   if (!isCriticalEdge(TI, SuccNum)) return false;
00106   BasicBlock *TIBB = TI->getParent();
00107   BasicBlock *DestBB = TI->getSuccessor(SuccNum);
00108 
00109   // Create a new basic block, linking it into the CFG.
00110   BasicBlock *NewBB = new BasicBlock(TIBB->getName() + "." +
00111                                      DestBB->getName() + "_crit_edge");
00112   // Create our unconditional branch...
00113   new BranchInst(DestBB, NewBB);
00114 
00115   // Branch to the new block, breaking the edge...
00116   TI->setSuccessor(SuccNum, NewBB);
00117 
00118   // Insert the block into the function... right after the block TI lives in.
00119   Function &F = *TIBB->getParent();
00120   F.getBasicBlockList().insert(TIBB->getNext(), NewBB);
00121 
00122   // If there are any PHI nodes in DestBB, we need to update them so that they
00123   // merge incoming values from NewBB instead of from TIBB.
00124   //
00125   for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) {
00126     PHINode *PN = cast<PHINode>(I);
00127     // We no longer enter through TIBB, now we come in through NewBB.  Revector
00128     // exactly one entry in the PHI node that used to come from TIBB to come
00129     // from NewBB.
00130     int BBIdx = PN->getBasicBlockIndex(TIBB);
00131     PN->setIncomingBlock(BBIdx, NewBB);
00132   }
00133 
00134   // If we don't have a pass object, we can't update anything...
00135   if (P == 0) return true;
00136 
00137   // Now update analysis information.  These are the analyses that we are
00138   // currently capable of updating...
00139   //
00140 
00141   // Should we update DominatorSet information?
00142   if (DominatorSet *DS = P->getAnalysisToUpdate<DominatorSet>()) {
00143     // The blocks that dominate the new one are the blocks that dominate TIBB
00144     // plus the new block itself.
00145     DominatorSet::DomSetType DomSet = DS->getDominators(TIBB);
00146     DomSet.insert(NewBB);  // A block always dominates itself.
00147     DS->addBasicBlock(NewBB, DomSet);
00148   }
00149 
00150   // Should we update ImmediateDominator information?
00151   if (ImmediateDominators *ID = P->getAnalysisToUpdate<ImmediateDominators>()) {
00152     // TIBB is the new immediate dominator for NewBB.  NewBB doesn't dominate
00153     // anything.
00154     ID->addNewBlock(NewBB, TIBB);
00155   }
00156 
00157   // Update the forest?
00158   if (ETForest *EF = P->getAnalysisToUpdate<ETForest>())
00159     EF->addNewBlock(NewBB, TIBB);
00160 
00161   // Should we update DominatorTree information?
00162   if (DominatorTree *DT = P->getAnalysisToUpdate<DominatorTree>()) {
00163     DominatorTree::Node *TINode = DT->getNode(TIBB);
00164 
00165     // The new block is not the immediate dominator for any other nodes, but
00166     // TINode is the immediate dominator for the new node.
00167     //
00168     if (TINode)        // Don't break unreachable code!
00169       DT->createNewNode(NewBB, TINode);
00170   }
00171 
00172   // Should we update DominanceFrontier information?
00173   if (DominanceFrontier *DF = P->getAnalysisToUpdate<DominanceFrontier>()) {
00174     // Since the new block is dominated by its only predecessor TIBB,
00175     // it cannot be in any block's dominance frontier.  Its dominance
00176     // frontier is {DestBB}.
00177     DominanceFrontier::DomSetType NewDFSet;
00178     NewDFSet.insert(DestBB);
00179     DF->addBasicBlock(NewBB, NewDFSet);
00180   }
00181   
00182   // Update LoopInfo if it is around.
00183   if (LoopInfo *LI = P->getAnalysisToUpdate<LoopInfo>()) {
00184     // If one or the other blocks were not in a loop, the new block is not
00185     // either, and thus LI doesn't need to be updated.
00186     if (Loop *TIL = LI->getLoopFor(TIBB))
00187       if (Loop *DestLoop = LI->getLoopFor(DestBB)) {
00188         if (TIL == DestLoop) {
00189           // Both in the same loop, the NewBB joins loop.
00190           DestLoop->addBasicBlockToLoop(NewBB, *LI);
00191         } else if (TIL->contains(DestLoop->getHeader())) {
00192           // Edge from an outer loop to an inner loop.  Add to the outer lopo.
00193           TIL->addBasicBlockToLoop(NewBB, *LI);
00194         } else if (DestLoop->contains(TIL->getHeader())) {
00195           // Edge from an inner loop to an outer loop.  Add to the outer lopo.
00196           DestLoop->addBasicBlockToLoop(NewBB, *LI);
00197         } else {
00198           // Edge from two loops with no containment relation.  Because these
00199           // are natural loops, we know that the destination block must be the
00200           // header of its loop (adding a branch into a loop elsewhere would
00201           // create an irreducible loop).
00202           assert(DestLoop->getHeader() == DestBB &&
00203                  "Should not create irreducible loops!");
00204           if (Loop *P = DestLoop->getParentLoop())
00205             P->addBasicBlockToLoop(NewBB, *LI);
00206         }
00207       }
00208     
00209   }
00210   return true;
00211 }