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