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/AliasAnalysis.h"
  21 #include "llvm/Analysis/LoopInfo.h"
  22 #include "llvm/Analysis/Dominators.h"
  23 #include <algorithm>
  24 using namespace llvm;
  25
  26 /// ReplaceInstWithValue - Replace all uses of an instruction (specified by BI)
  27 /// with a value, then remove and delete the original instruction.
  28 ///
  29 void llvm::ReplaceInstWithValue(BasicBlock::InstListType &BIL,
  30                                 BasicBlock::iterator &BI, Value *V) {
  31   Instruction &I = *BI;
  32   // Replaces all of the uses of the instruction with uses of the value
  33   I.replaceAllUsesWith(V);
  34
  35   // Make sure to propagate a name if there is one already.
  36   if (I.hasName() && !V->hasName())
  37     V->takeName(&I);
  38
  39   // Delete the unnecessary instruction now...
  40   BI = BIL.erase(BI);
  41 }
  42
  43
  44 /// ReplaceInstWithInst - Replace the instruction specified by BI with the
  45 /// instruction specified by I.  The original instruction is deleted and BI is
  46 /// updated to point to the new instruction.
  47 ///
  48 void llvm::ReplaceInstWithInst(BasicBlock::InstListType &BIL,
  49                                BasicBlock::iterator &BI, Instruction *I) {
  50   assert(I->getParent() == 0 &&
  51          "ReplaceInstWithInst: Instruction already inserted into basic block!");
  52
  53   // Insert the new instruction into the basic block...
  54   BasicBlock::iterator New = BIL.insert(BI, I);
  55
  56   // Replace all uses of the old instruction, and delete it.
  57   ReplaceInstWithValue(BIL, BI, I);
  58
  59   // Move BI back to point to the newly inserted instruction
  60   BI = New;
  61 }
  62
  63 /// ReplaceInstWithInst - Replace the instruction specified by From with the
  64 /// instruction specified by To.
  65 ///
  66 void llvm::ReplaceInstWithInst(Instruction *From, Instruction *To) {
  67   BasicBlock::iterator BI(From);
  68   ReplaceInstWithInst(From->getParent()->getInstList(), BI, To);
  69 }
  70
  71 /// RemoveSuccessor - Change the specified terminator instruction such that its
  72 /// successor SuccNum no longer exists.  Because this reduces the outgoing
  73 /// degree of the current basic block, the actual terminator instruction itself
  74 /// may have to be changed.  In the case where the last successor of the block
  75 /// is deleted, a return instruction is inserted in its place which can cause a
  76 /// surprising change in program behavior if it is not expected.
  77 ///
  78 void llvm::RemoveSuccessor(TerminatorInst *TI, unsigned SuccNum) {
  79   assert(SuccNum < TI->getNumSuccessors() &&
  80          "Trying to remove a nonexistant successor!");
  81
  82   // If our old successor block contains any PHI nodes, remove the entry in the
  83   // PHI nodes that comes from this branch...
  84   //
  85   BasicBlock *BB = TI->getParent();
  86   TI->getSuccessor(SuccNum)->removePredecessor(BB);
  87
  88   TerminatorInst *NewTI = 0;
  89   switch (TI->getOpcode()) {
  90   case Instruction::Br:
  91     // If this is a conditional branch... convert to unconditional branch.
  92     if (TI->getNumSuccessors() == 2) {
  93       cast<BranchInst>(TI)->setUnconditionalDest(TI->getSuccessor(1-SuccNum));
  94     } else {                    // Otherwise convert to a return instruction...
  95       Value *RetVal = 0;
  96
  97       // Create a value to return... if the function doesn't return null...
  98       if (BB->getParent()->getReturnType() != Type::VoidTy)
  99         RetVal = Constant::getNullValue(BB->getParent()->getReturnType());
 100
 101       // Create the return...
 102       NewTI = ReturnInst::Create(RetVal);
 103     }
 104     break;
 105
 106   case Instruction::Invoke:    // Should convert to call
 107   case Instruction::Switch:    // Should remove entry
 108   default:
 109   case Instruction::Ret:       // Cannot happen, has no successors!
 110     assert(0 && "Unhandled terminator instruction type in RemoveSuccessor!");
 111     abort();
 112   }
 113
 114   if (NewTI)   // If it's a different instruction, replace.
 115     ReplaceInstWithInst(TI, NewTI);
 116 }
 117
 118 /// SplitEdge -  Split the edge connecting specified block. Pass P must
 119 /// not be NULL.
 120 BasicBlock *llvm::SplitEdge(BasicBlock *BB, BasicBlock *Succ, Pass *P) {
 121   TerminatorInst *LatchTerm = BB->getTerminator();
 122   unsigned SuccNum = 0;
 123   for (unsigned i = 0, e = LatchTerm->getNumSuccessors(); ; ++i) {
 124     assert(i != e && "Didn't find edge?");
 125     if (LatchTerm->getSuccessor(i) == Succ) {
 126       SuccNum = i;
 127       break;
 128     }
 129   }
 130
 131   // If this is a critical edge, let SplitCriticalEdge do it.
 132   if (SplitCriticalEdge(BB->getTerminator(), SuccNum, P))
 133     return LatchTerm->getSuccessor(SuccNum);
 134
 135   // If the edge isn't critical, then BB has a single successor or Succ has a
 136   // single pred.  Split the block.
 137   BasicBlock::iterator SplitPoint;
 138   if (BasicBlock *SP = Succ->getSinglePredecessor()) {
 139     // If the successor only has a single pred, split the top of the successor
 140     // block.
 141     assert(SP == BB && "CFG broken");
 142     return SplitBlock(Succ, Succ->begin(), P);
 143   } else {
 144     // Otherwise, if BB has a single successor, split it at the bottom of the
 145     // block.
 146     assert(BB->getTerminator()->getNumSuccessors() == 1 &&
 147            "Should have a single succ!");
 148     return SplitBlock(BB, BB->getTerminator(), P);
 149   }
 150 }
 151
 152 /// SplitBlock - Split the specified block at the specified instruction - every
 153 /// thing before SplitPt stays in Old and everything starting with SplitPt moves
 154 /// to a new block.  The two blocks are joined by an unconditional branch and
 155 /// the loop info is updated.
 156 ///
 157 BasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt, Pass *P) {
 158
 159   LoopInfo &LI = P->getAnalysis<LoopInfo>();
 160   BasicBlock::iterator SplitIt = SplitPt;
 161   while (isa<PHINode>(SplitIt))
 162     ++SplitIt;
 163   BasicBlock *New = Old->splitBasicBlock(SplitIt, Old->getName()+".split");
 164   New->setUnwindDest(Old->getUnwindDest());
 165
 166   // The new block lives in whichever loop the old one did.
 167   if (Loop *L = LI.getLoopFor(Old))
 168     L->addBasicBlockToLoop(New, LI.getBase());
 169
 170   if (DominatorTree *DT = P->getAnalysisToUpdate<DominatorTree>())
 171     {
 172       // Old dominates New. New node domiantes all other nodes dominated by Old.
 173       DomTreeNode *OldNode = DT->getNode(Old);
 174       std::vector<DomTreeNode *> Children;
 175       for (DomTreeNode::iterator I = OldNode->begin(), E = OldNode->end();
 176            I != E; ++I)
 177         Children.push_back(*I);
 178
 179       DomTreeNode *NewNode =   DT->addNewBlock(New,Old);
 180
 181       for (std::vector<DomTreeNode *>::iterator I = Children.begin(),
 182              E = Children.end(); I != E; ++I)
 183         DT->changeImmediateDominator(*I, NewNode);
 184     }
 185
 186   if (DominanceFrontier *DF = P->getAnalysisToUpdate<DominanceFrontier>())
 187     DF->splitBlock(Old);
 188
 189   return New;
 190 }
 191
 192
 193 /// SplitBlockPredecessors - This method transforms BB by introducing a new
 194 /// basic block into the function, and moving some of the predecessors of BB to
 195 /// be predecessors of the new block.  The new predecessors are indicated by the
 196 /// Preds array, which has NumPreds elements in it.  The new block is given a
 197 /// suffix of 'Suffix'.
 198 ///
 199 /// This currently updates the LLVM IR, AliasAnalysis, DominatorTree and
 200 /// DominanceFrontier, but no other analyses.
 201 BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB,
 202                                          BasicBlock *const *Preds,
 203                                          unsigned NumPreds, const char *Suffix,
 204                                          Pass *P) {
 205   // Create new basic block, insert right before the original block.
 206   BasicBlock *NewBB =
 207     BasicBlock::Create(BB->getName()+Suffix, BB->getParent(), BB);
 208
 209   // The new block unconditionally branches to the old block.
 210   BranchInst *BI = BranchInst::Create(BB, NewBB);
 211
 212   // Move the edges from Preds to point to NewBB instead of BB.
 213   for (unsigned i = 0; i != NumPreds; ++i) {
 214     Preds[i]->getTerminator()->replaceUsesOfWith(BB, NewBB);
 215
 216     if (Preds[i]->getUnwindDest() == BB)
 217       Preds[i]->setUnwindDest(NewBB);
 218   }
 219
 220   // Update dominator tree and dominator frontier if available.
 221   DominatorTree *DT = P ? P->getAnalysisToUpdate<DominatorTree>() : 0;
 222   if (DT)
 223     DT->splitBlock(NewBB);
 224   if (DominanceFrontier *DF = P ? P->getAnalysisToUpdate<DominanceFrontier>():0)
 225     DF->splitBlock(NewBB);
 226   AliasAnalysis *AA = P ? P->getAnalysisToUpdate<AliasAnalysis>() : 0;
 227
 228
 229   // Insert a new PHI node into NewBB for every PHI node in BB and that new PHI
 230   // node becomes an incoming value for BB's phi node.  However, if the Preds
 231   // list is empty, we need to insert dummy entries into the PHI nodes in BB to
 232   // account for the newly created predecessor.
 233   if (NumPreds == 0) {
 234     // Insert dummy values as the incoming value.
 235     for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I)
 236       cast<PHINode>(I)->addIncoming(UndefValue::get(I->getType()), NewBB);
 237     return NewBB;
 238   }
 239
 240   // Otherwise, create a new PHI node in NewBB for each PHI node in BB.
 241   for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ) {
 242     PHINode *PN = cast<PHINode>(I++);
 243
 244     // Check to see if all of the values coming in are the same.  If so, we
 245     // don't need to create a new PHI node.
 246     Value *InVal = PN->getIncomingValueForBlock(Preds[0]);
 247     for (unsigned i = 1; i != NumPreds; ++i)
 248       if (InVal != PN->getIncomingValueForBlock(Preds[i])) {
 249         InVal = 0;
 250         break;
 251       }
 252
 253     if (InVal) {
 254       // If all incoming values for the new PHI would be the same, just don't
 255       // make a new PHI.  Instead, just remove the incoming values from the old
 256       // PHI.
 257       for (unsigned i = 0; i != NumPreds; ++i)
 258         PN->removeIncomingValue(Preds[i], false);
 259     } else {
 260       // If the values coming into the block are not the same, we need a PHI.
 261       // Create the new PHI node, insert it into NewBB at the end of the block
 262       PHINode *NewPHI =
 263         PHINode::Create(PN->getType(), PN->getName()+".ph", BI);
 264       if (AA) AA->copyValue(PN, NewPHI);
 265
 266       // Move all of the PHI values for 'Preds' to the new PHI.
 267       for (unsigned i = 0; i != NumPreds; ++i) {
 268         Value *V = PN->removeIncomingValue(Preds[i], false);
 269         NewPHI->addIncoming(V, Preds[i]);
 270       }
 271       InVal = NewPHI;
 272     }
 273
 274     // Add an incoming value to the PHI node in the loop for the preheader
 275     // edge.
 276     PN->addIncoming(InVal, NewBB);
 277
 278     // Check to see if we can eliminate this phi node.
 279     if (Value *V = PN->hasConstantValue(DT != 0)) {
 280       Instruction *I = dyn_cast<Instruction>(V);
 281       if (!I || DT == 0 || DT->dominates(I, PN)) {
 282         PN->replaceAllUsesWith(V);
 283         if (AA) AA->deleteValue(PN);
 284         PN->eraseFromParent();
 285       }
 286     }
 287   }
 288
 289   return NewBB;
 290 }