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