BasicBlockUtils.cpp revision 8019893c3f55a4bfe770888fe285d6dae57cf216
1//===-- BasicBlockUtils.cpp - BasicBlock Utilities -------------------------==// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source 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> 23using 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/// 28void 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/// 47void 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/// 65void 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/// 77void 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. 119BasicBlock *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/// 156BasicBlock *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); 167 168 if (DominatorTree *DT = P->getAnalysisToUpdate<DominatorTree>()) 169 DT->addNewBlock(New, Old); 170 171 if (DominanceFrontier *DF = P->getAnalysisToUpdate<DominanceFrontier>()) 172 DF->splitBlock(Old); 173 174 return New; 175} 176