lib/Transforms/Utils/BasicBlockUtils.cpp

   1 //===-- BasicBlockUtils.cpp - BasicBlock Utilities -------------------------==//
   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 // This family of functions perform manipulations on basic blocks, and
  11 // instructions contained within basic blocks.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  16 #include "llvm/Function.h"
  17 #include "llvm/Instructions.h"
  18 #include "llvm/Constant.h"
  19 #include "llvm/Type.h"
  20 #include "llvm/Analysis/LoopInfo.h"
  21 #include "llvm/Analysis/Dominators.h"
  22 #include <algorithm>
  23 using namespace llvm;
  24
  25 /// ReplaceInstWithValue - Replace all uses of an instruction (specified by BI)
  26 /// with a value, then remove and delete the original instruction.
  27 ///
  28 void llvm::ReplaceInstWithValue(BasicBlock::InstListType &BIL,
  29                                 BasicBlock::iterator &BI, Value *V) {
  30   Instruction &I = *BI;
  31   // Replaces all of the uses of the instruction with uses of the value
  32   I.replaceAllUsesWith(V);
  33
  34   // Make sure to propagate a name if there is one already.
  35   if (I.hasName() && !V->hasName())
  36     V->takeName(&I);
  37
  38   // Delete the unnecessary instruction now...
  39   BI = BIL.erase(BI);
  40 }
  41
  42
  43 /// ReplaceInstWithInst - Replace the instruction specified by BI with the
  44 /// instruction specified by I.  The original instruction is deleted and BI is
  45 /// updated to point to the new instruction.
  46 ///
  47 void llvm::ReplaceInstWithInst(BasicBlock::InstListType &BIL,
  48                                BasicBlock::iterator &BI, Instruction *I) {
  49   assert(I->getParent() == 0 &&
  50          "ReplaceInstWithInst: Instruction already inserted into basic block!");
  51
  52   // Insert the new instruction into the basic block...
  53   BasicBlock::iterator New = BIL.insert(BI, I);
  54
  55   // Replace all uses of the old instruction, and delete it.
  56   ReplaceInstWithValue(BIL, BI, I);
  57
  58   // Move BI back to point to the newly inserted instruction
  59   BI = New;
  60 }
  61
  62 /// ReplaceInstWithInst - Replace the instruction specified by From with the
  63 /// instruction specified by To.
  64 ///
  65 void llvm::ReplaceInstWithInst(Instruction *From, Instruction *To) {
  66   BasicBlock::iterator BI(From);
  67   ReplaceInstWithInst(From->getParent()->getInstList(), BI, To);
  68 }
  69
  70 /// RemoveSuccessor - Change the specified terminator instruction such that its
  71 /// successor SuccNum no longer exists.  Because this reduces the outgoing
  72 /// degree of the current basic block, the actual terminator instruction itself
  73 /// may have to be changed.  In the case where the last successor of the block
  74 /// is deleted, a return instruction is inserted in its place which can cause a
  75 /// surprising change in program behavior if it is not expected.
  76 ///
  77 void llvm::RemoveSuccessor(TerminatorInst *TI, unsigned SuccNum) {
  78   assert(SuccNum < TI->getNumSuccessors() &&
  79          "Trying to remove a nonexistant successor!");
  80
  81   // If our old successor block contains any PHI nodes, remove the entry in the
  82   // PHI nodes that comes from this branch...
  83   //
  84   BasicBlock *BB = TI->getParent();
  85   TI->getSuccessor(SuccNum)->removePredecessor(BB);
  86
  87   TerminatorInst *NewTI = 0;
  88   switch (TI->getOpcode()) {
  89   case Instruction::Br:
  90     // If this is a conditional branch... convert to unconditional branch.
  91     if (TI->getNumSuccessors() == 2) {
  92       cast<BranchInst>(TI)->setUnconditionalDest(TI->getSuccessor(1-SuccNum));
  93     } else {                    // Otherwise convert to a return instruction...
  94       Value *RetVal = 0;
  95
  96       // Create a value to return... if the function doesn't return null...
  97       if (BB->getParent()->getReturnType() != Type::VoidTy)
  98         RetVal = Constant::getNullValue(BB->getParent()->getReturnType());
  99
 100       // Create the return...
 101       NewTI = new ReturnInst(RetVal);
 102     }
 103     break;
 104
 105   case Instruction::Invoke:    // Should convert to call
 106   case Instruction::Switch:    // Should remove entry
 107   default:
 108   case Instruction::Ret:       // Cannot happen, has no successors!
 109     assert(0 && "Unhandled terminator instruction type in RemoveSuccessor!");
 110     abort();
 111   }
 112
 113   if (NewTI)   // If it's a different instruction, replace.
 114     ReplaceInstWithInst(TI, NewTI);
 115 }
 116
 117 /// SplitEdge -  Split the edge connecting specified block. Pass P must
 118 /// not be NULL.
 119 BasicBlock *llvm::SplitEdge(BasicBlock *BB, BasicBlock *Succ, Pass *P) {
 120   TerminatorInst *LatchTerm = BB->getTerminator();
 121   unsigned SuccNum = 0;
 122   for (unsigned i = 0, e = LatchTerm->getNumSuccessors(); ; ++i) {
 123     assert(i != e && "Didn't find edge?");
 124     if (LatchTerm->getSuccessor(i) == Succ) {
 125       SuccNum = i;
 126       break;
 127     }
 128   }
 129
 130   // If this is a critical edge, let SplitCriticalEdge do it.
 131   if (SplitCriticalEdge(BB->getTerminator(), SuccNum, P))
 132     return LatchTerm->getSuccessor(SuccNum);
 133
 134   // If the edge isn't critical, then BB has a single successor or Succ has a
 135   // single pred.  Split the block.
 136   BasicBlock::iterator SplitPoint;
 137   if (BasicBlock *SP = Succ->getSinglePredecessor()) {
 138     // If the successor only has a single pred, split the top of the successor
 139     // block.
 140     assert(SP == BB && "CFG broken");
 141     return SplitBlock(Succ, Succ->begin(), P);
 142   } else {
 143     // Otherwise, if BB has a single successor, split it at the bottom of the
 144     // block.
 145     assert(BB->getTerminator()->getNumSuccessors() == 1 &&
 146            "Should have a single succ!");
 147     return SplitBlock(BB, BB->getTerminator(), P);
 148   }
 149 }
 150
 151 /// SplitBlock - Split the specified block at the specified instruction - every
 152 /// thing before SplitPt stays in Old and everything starting with SplitPt moves
 153 /// to a new block.  The two blocks are joined by an unconditional branch and
 154 /// the loop info is updated.
 155 ///
 156 BasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt, Pass *P) {
 157
 158   LoopInfo &LI = P->getAnalysis<LoopInfo>();
 159   BasicBlock::iterator SplitIt = SplitPt;
 160   while (isa<PHINode>(SplitIt))
 161     ++SplitIt;
 162   BasicBlock *New = Old->splitBasicBlock(SplitIt, Old->getName()+".split");
 163
 164   // The new block lives in whichever loop the old one did.
 165   if (Loop *L = LI.getLoopFor(Old))
 166     L->addBasicBlockToLoop(New, LI.getBase());
 167
 168   if (DominatorTree *DT = P->getAnalysisToUpdate<DominatorTree>())
 169     {
 170       // Old dominates New. New node domiantes all other nodes dominated by Old.
 171       DomTreeNode *OldNode = DT->getNode(Old);
 172       std::vector<DomTreeNode *> Children;
 173       for (DomTreeNode::iterator I = OldNode->begin(), E = OldNode->end();
 174            I != E; ++I)
 175         Children.push_back(*I);
 176
 177       DomTreeNode *NewNode =   DT->addNewBlock(New,Old);
 178
 179       for (std::vector<DomTreeNode *>::iterator I = Children.begin(),
 180              E = Children.end(); I != E; ++I)
 181         DT->changeImmediateDominator(*I, NewNode);
 182     }
 183
 184   if (DominanceFrontier *DF = P->getAnalysisToUpdate<DominanceFrontier>())
 185     DF->splitBlock(Old);
 186
 187   return New;
 188 }