BasicBlockUtils.cpp revision 2112bbc42d1de50e482f64e1fb0f10de9817fcf8
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/IntrinsicInst.h" 19#include "llvm/Constant.h" 20#include "llvm/Type.h" 21#include "llvm/Analysis/AliasAnalysis.h" 22#include "llvm/Analysis/LoopInfo.h" 23#include "llvm/Analysis/Dominators.h" 24#include "llvm/Target/TargetData.h" 25#include "llvm/Transforms/Utils/Local.h" 26#include "llvm/Transforms/Scalar.h" 27#include "llvm/Support/ErrorHandling.h" 28#include "llvm/Support/ValueHandle.h" 29#include <algorithm> 30using namespace llvm; 31 32/// DeleteDeadBlock - Delete the specified block, which must have no 33/// predecessors. 34void llvm::DeleteDeadBlock(BasicBlock *BB) { 35 assert((pred_begin(BB) == pred_end(BB) || 36 // Can delete self loop. 37 BB->getSinglePredecessor() == BB) && "Block is not dead!"); 38 TerminatorInst *BBTerm = BB->getTerminator(); 39 40 // Loop through all of our successors and make sure they know that one 41 // of their predecessors is going away. 42 for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i) 43 BBTerm->getSuccessor(i)->removePredecessor(BB); 44 45 // Zap all the instructions in the block. 46 while (!BB->empty()) { 47 Instruction &I = BB->back(); 48 // If this instruction is used, replace uses with an arbitrary value. 49 // Because control flow can't get here, we don't care what we replace the 50 // value with. Note that since this block is unreachable, and all values 51 // contained within it must dominate their uses, that all uses will 52 // eventually be removed (they are themselves dead). 53 if (!I.use_empty()) 54 I.replaceAllUsesWith(UndefValue::get(I.getType())); 55 BB->getInstList().pop_back(); 56 } 57 58 // Zap the block! 59 BB->eraseFromParent(); 60} 61 62/// FoldSingleEntryPHINodes - We know that BB has one predecessor. If there are 63/// any single-entry PHI nodes in it, fold them away. This handles the case 64/// when all entries to the PHI nodes in a block are guaranteed equal, such as 65/// when the block has exactly one predecessor. 66void llvm::FoldSingleEntryPHINodes(BasicBlock *BB) { 67 while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 68 if (PN->getIncomingValue(0) != PN) 69 PN->replaceAllUsesWith(PN->getIncomingValue(0)); 70 else 71 PN->replaceAllUsesWith(UndefValue::get(PN->getType())); 72 PN->eraseFromParent(); 73 } 74} 75 76 77/// DeleteDeadPHIs - Examine each PHI in the given block and delete it if it 78/// is dead. Also recursively delete any operands that become dead as 79/// a result. This includes tracing the def-use list from the PHI to see if 80/// it is ultimately unused or if it reaches an unused cycle. 81bool llvm::DeleteDeadPHIs(BasicBlock *BB) { 82 // Recursively deleting a PHI may cause multiple PHIs to be deleted 83 // or RAUW'd undef, so use an array of WeakVH for the PHIs to delete. 84 SmallVector<WeakVH, 8> PHIs; 85 for (BasicBlock::iterator I = BB->begin(); 86 PHINode *PN = dyn_cast<PHINode>(I); ++I) 87 PHIs.push_back(PN); 88 89 bool Changed = false; 90 for (unsigned i = 0, e = PHIs.size(); i != e; ++i) 91 if (PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i].operator Value*())) 92 Changed |= RecursivelyDeleteDeadPHINode(PN); 93 94 return Changed; 95} 96 97/// MergeBlockIntoPredecessor - Attempts to merge a block into its predecessor, 98/// if possible. The return value indicates success or failure. 99bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, Pass *P) { 100 // Don't merge away blocks who have their address taken. 101 if (BB->hasAddressTaken()) return false; 102 103 // Can't merge if there are multiple predecessors, or no predecessors. 104 BasicBlock *PredBB = BB->getUniquePredecessor(); 105 if (!PredBB) return false; 106 107 // Don't break self-loops. 108 if (PredBB == BB) return false; 109 // Don't break invokes. 110 if (isa<InvokeInst>(PredBB->getTerminator())) return false; 111 112 succ_iterator SI(succ_begin(PredBB)), SE(succ_end(PredBB)); 113 BasicBlock* OnlySucc = BB; 114 for (; SI != SE; ++SI) 115 if (*SI != OnlySucc) { 116 OnlySucc = 0; // There are multiple distinct successors! 117 break; 118 } 119 120 // Can't merge if there are multiple successors. 121 if (!OnlySucc) return false; 122 123 // Can't merge if there is PHI loop. 124 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE; ++BI) { 125 if (PHINode *PN = dyn_cast<PHINode>(BI)) { 126 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 127 if (PN->getIncomingValue(i) == PN) 128 return false; 129 } else 130 break; 131 } 132 133 // Begin by getting rid of unneeded PHIs. 134 while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) { 135 PN->replaceAllUsesWith(PN->getIncomingValue(0)); 136 BB->getInstList().pop_front(); // Delete the phi node... 137 } 138 139 // Delete the unconditional branch from the predecessor... 140 PredBB->getInstList().pop_back(); 141 142 // Move all definitions in the successor to the predecessor... 143 PredBB->getInstList().splice(PredBB->end(), BB->getInstList()); 144 145 // Make all PHI nodes that referred to BB now refer to Pred as their 146 // source... 147 BB->replaceAllUsesWith(PredBB); 148 149 // Inherit predecessors name if it exists. 150 if (!PredBB->hasName()) 151 PredBB->takeName(BB); 152 153 // Finally, erase the old block and update dominator info. 154 if (P) { 155 if (DominatorTree* DT = P->getAnalysisIfAvailable<DominatorTree>()) { 156 DomTreeNode* DTN = DT->getNode(BB); 157 DomTreeNode* PredDTN = DT->getNode(PredBB); 158 159 if (DTN) { 160 SmallPtrSet<DomTreeNode*, 8> Children(DTN->begin(), DTN->end()); 161 for (SmallPtrSet<DomTreeNode*, 8>::iterator DI = Children.begin(), 162 DE = Children.end(); DI != DE; ++DI) 163 DT->changeImmediateDominator(*DI, PredDTN); 164 165 DT->eraseNode(BB); 166 } 167 } 168 } 169 170 BB->eraseFromParent(); 171 172 173 return true; 174} 175 176/// ReplaceInstWithValue - Replace all uses of an instruction (specified by BI) 177/// with a value, then remove and delete the original instruction. 178/// 179void llvm::ReplaceInstWithValue(BasicBlock::InstListType &BIL, 180 BasicBlock::iterator &BI, Value *V) { 181 Instruction &I = *BI; 182 // Replaces all of the uses of the instruction with uses of the value 183 I.replaceAllUsesWith(V); 184 185 // Make sure to propagate a name if there is one already. 186 if (I.hasName() && !V->hasName()) 187 V->takeName(&I); 188 189 // Delete the unnecessary instruction now... 190 BI = BIL.erase(BI); 191} 192 193 194/// ReplaceInstWithInst - Replace the instruction specified by BI with the 195/// instruction specified by I. The original instruction is deleted and BI is 196/// updated to point to the new instruction. 197/// 198void llvm::ReplaceInstWithInst(BasicBlock::InstListType &BIL, 199 BasicBlock::iterator &BI, Instruction *I) { 200 assert(I->getParent() == 0 && 201 "ReplaceInstWithInst: Instruction already inserted into basic block!"); 202 203 // Insert the new instruction into the basic block... 204 BasicBlock::iterator New = BIL.insert(BI, I); 205 206 // Replace all uses of the old instruction, and delete it. 207 ReplaceInstWithValue(BIL, BI, I); 208 209 // Move BI back to point to the newly inserted instruction 210 BI = New; 211} 212 213/// ReplaceInstWithInst - Replace the instruction specified by From with the 214/// instruction specified by To. 215/// 216void llvm::ReplaceInstWithInst(Instruction *From, Instruction *To) { 217 BasicBlock::iterator BI(From); 218 ReplaceInstWithInst(From->getParent()->getInstList(), BI, To); 219} 220 221/// GetSuccessorNumber - Search for the specified successor of basic block BB 222/// and return its position in the terminator instruction's list of 223/// successors. It is an error to call this with a block that is not a 224/// successor. 225unsigned llvm::GetSuccessorNumber(BasicBlock *BB, BasicBlock *Succ) { 226 TerminatorInst *Term = BB->getTerminator(); 227#ifndef NDEBUG 228 unsigned e = Term->getNumSuccessors(); 229#endif 230 for (unsigned i = 0; ; ++i) { 231 assert(i != e && "Didn't find edge?"); 232 if (Term->getSuccessor(i) == Succ) 233 return i; 234 } 235 return 0; 236} 237 238/// SplitEdge - Split the edge connecting specified block. Pass P must 239/// not be NULL. 240BasicBlock *llvm::SplitEdge(BasicBlock *BB, BasicBlock *Succ, Pass *P) { 241 unsigned SuccNum = GetSuccessorNumber(BB, Succ); 242 243 // If this is a critical edge, let SplitCriticalEdge do it. 244 TerminatorInst *LatchTerm = BB->getTerminator(); 245 if (SplitCriticalEdge(LatchTerm, SuccNum, P)) 246 return LatchTerm->getSuccessor(SuccNum); 247 248 // If the edge isn't critical, then BB has a single successor or Succ has a 249 // single pred. Split the block. 250 BasicBlock::iterator SplitPoint; 251 if (BasicBlock *SP = Succ->getSinglePredecessor()) { 252 // If the successor only has a single pred, split the top of the successor 253 // block. 254 assert(SP == BB && "CFG broken"); 255 SP = NULL; 256 return SplitBlock(Succ, Succ->begin(), P); 257 } else { 258 // Otherwise, if BB has a single successor, split it at the bottom of the 259 // block. 260 assert(BB->getTerminator()->getNumSuccessors() == 1 && 261 "Should have a single succ!"); 262 return SplitBlock(BB, BB->getTerminator(), P); 263 } 264} 265 266/// SplitBlock - Split the specified block at the specified instruction - every 267/// thing before SplitPt stays in Old and everything starting with SplitPt moves 268/// to a new block. The two blocks are joined by an unconditional branch and 269/// the loop info is updated. 270/// 271BasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt, Pass *P) { 272 BasicBlock::iterator SplitIt = SplitPt; 273 while (isa<PHINode>(SplitIt)) 274 ++SplitIt; 275 BasicBlock *New = Old->splitBasicBlock(SplitIt, Old->getName()+".split"); 276 277 // The new block lives in whichever loop the old one did. This preserves 278 // LCSSA as well, because we force the split point to be after any PHI nodes. 279 if (LoopInfo* LI = P->getAnalysisIfAvailable<LoopInfo>()) 280 if (Loop *L = LI->getLoopFor(Old)) 281 L->addBasicBlockToLoop(New, LI->getBase()); 282 283 if (DominatorTree *DT = P->getAnalysisIfAvailable<DominatorTree>()) { 284 // Old dominates New. New node dominates all other nodes dominated by Old. 285 DomTreeNode *OldNode = DT->getNode(Old); 286 std::vector<DomTreeNode *> Children; 287 for (DomTreeNode::iterator I = OldNode->begin(), E = OldNode->end(); 288 I != E; ++I) 289 Children.push_back(*I); 290 291 DomTreeNode *NewNode = DT->addNewBlock(New,Old); 292 for (std::vector<DomTreeNode *>::iterator I = Children.begin(), 293 E = Children.end(); I != E; ++I) 294 DT->changeImmediateDominator(*I, NewNode); 295 } 296 297 if (DominanceFrontier *DF = P->getAnalysisIfAvailable<DominanceFrontier>()) 298 DF->splitBlock(Old); 299 300 return New; 301} 302 303 304/// SplitBlockPredecessors - This method transforms BB by introducing a new 305/// basic block into the function, and moving some of the predecessors of BB to 306/// be predecessors of the new block. The new predecessors are indicated by the 307/// Preds array, which has NumPreds elements in it. The new block is given a 308/// suffix of 'Suffix'. 309/// 310/// This currently updates the LLVM IR, AliasAnalysis, DominatorTree, 311/// DominanceFrontier, LoopInfo, and LCCSA but no other analyses. 312/// In particular, it does not preserve LoopSimplify (because it's 313/// complicated to handle the case where one of the edges being split 314/// is an exit of a loop with other exits). 315/// 316BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB, 317 BasicBlock *const *Preds, 318 unsigned NumPreds, const char *Suffix, 319 Pass *P) { 320 // Create new basic block, insert right before the original block. 321 BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), BB->getName()+Suffix, 322 BB->getParent(), BB); 323 324 // The new block unconditionally branches to the old block. 325 BranchInst *BI = BranchInst::Create(BB, NewBB); 326 327 LoopInfo *LI = P ? P->getAnalysisIfAvailable<LoopInfo>() : 0; 328 Loop *L = LI ? LI->getLoopFor(BB) : 0; 329 bool PreserveLCSSA = P->mustPreserveAnalysisID(LCSSAID); 330 331 // Move the edges from Preds to point to NewBB instead of BB. 332 // While here, if we need to preserve loop analyses, collect 333 // some information about how this split will affect loops. 334 bool HasLoopExit = false; 335 bool IsLoopEntry = !!L; 336 bool SplitMakesNewLoopHeader = false; 337 for (unsigned i = 0; i != NumPreds; ++i) { 338 // This is slightly more strict than necessary; the minimum requirement 339 // is that there be no more than one indirectbr branching to BB. And 340 // all BlockAddress uses would need to be updated. 341 assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) && 342 "Cannot split an edge from an IndirectBrInst"); 343 344 Preds[i]->getTerminator()->replaceUsesOfWith(BB, NewBB); 345 346 if (LI) { 347 // If we need to preserve LCSSA, determine if any of 348 // the preds is a loop exit. 349 if (PreserveLCSSA) 350 if (Loop *PL = LI->getLoopFor(Preds[i])) 351 if (!PL->contains(BB)) 352 HasLoopExit = true; 353 // If we need to preserve LoopInfo, note whether any of the 354 // preds crosses an interesting loop boundary. 355 if (L) { 356 if (L->contains(Preds[i])) 357 IsLoopEntry = false; 358 else 359 SplitMakesNewLoopHeader = true; 360 } 361 } 362 } 363 364 // Update dominator tree and dominator frontier if available. 365 DominatorTree *DT = P ? P->getAnalysisIfAvailable<DominatorTree>() : 0; 366 if (DT) 367 DT->splitBlock(NewBB); 368 if (DominanceFrontier *DF = 369 P ? P->getAnalysisIfAvailable<DominanceFrontier>() : 0) 370 DF->splitBlock(NewBB); 371 372 // Insert a new PHI node into NewBB for every PHI node in BB and that new PHI 373 // node becomes an incoming value for BB's phi node. However, if the Preds 374 // list is empty, we need to insert dummy entries into the PHI nodes in BB to 375 // account for the newly created predecessor. 376 if (NumPreds == 0) { 377 // Insert dummy values as the incoming value. 378 for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I) 379 cast<PHINode>(I)->addIncoming(UndefValue::get(I->getType()), NewBB); 380 return NewBB; 381 } 382 383 AliasAnalysis *AA = P ? P->getAnalysisIfAvailable<AliasAnalysis>() : 0; 384 385 if (L) { 386 if (IsLoopEntry) { 387 // Add the new block to the nearest enclosing loop (and not an 388 // adjacent loop). To find this, examine each of the predecessors and 389 // determine which loops enclose them, and select the most-nested loop 390 // which contains the loop containing the block being split. 391 Loop *InnermostPredLoop = 0; 392 for (unsigned i = 0; i != NumPreds; ++i) 393 if (Loop *PredLoop = LI->getLoopFor(Preds[i])) { 394 // Seek a loop which actually contains the block being split (to 395 // avoid adjacent loops). 396 while (PredLoop && !PredLoop->contains(BB)) 397 PredLoop = PredLoop->getParentLoop(); 398 // Select the most-nested of these loops which contains the block. 399 if (PredLoop && 400 PredLoop->contains(BB) && 401 (!InnermostPredLoop || 402 InnermostPredLoop->getLoopDepth() < PredLoop->getLoopDepth())) 403 InnermostPredLoop = PredLoop; 404 } 405 if (InnermostPredLoop) 406 InnermostPredLoop->addBasicBlockToLoop(NewBB, LI->getBase()); 407 } else { 408 L->addBasicBlockToLoop(NewBB, LI->getBase()); 409 if (SplitMakesNewLoopHeader) 410 L->moveToHeader(NewBB); 411 } 412 } 413 414 // Otherwise, create a new PHI node in NewBB for each PHI node in BB. 415 for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ) { 416 PHINode *PN = cast<PHINode>(I++); 417 418 // Check to see if all of the values coming in are the same. If so, we 419 // don't need to create a new PHI node, unless it's needed for LCSSA. 420 Value *InVal = 0; 421 if (!HasLoopExit) { 422 InVal = PN->getIncomingValueForBlock(Preds[0]); 423 for (unsigned i = 1; i != NumPreds; ++i) 424 if (InVal != PN->getIncomingValueForBlock(Preds[i])) { 425 InVal = 0; 426 break; 427 } 428 } 429 430 if (InVal) { 431 // If all incoming values for the new PHI would be the same, just don't 432 // make a new PHI. Instead, just remove the incoming values from the old 433 // PHI. 434 for (unsigned i = 0; i != NumPreds; ++i) 435 PN->removeIncomingValue(Preds[i], false); 436 } else { 437 // If the values coming into the block are not the same, we need a PHI. 438 // Create the new PHI node, insert it into NewBB at the end of the block 439 PHINode *NewPHI = 440 PHINode::Create(PN->getType(), PN->getName()+".ph", BI); 441 if (AA) AA->copyValue(PN, NewPHI); 442 443 // Move all of the PHI values for 'Preds' to the new PHI. 444 for (unsigned i = 0; i != NumPreds; ++i) { 445 Value *V = PN->removeIncomingValue(Preds[i], false); 446 NewPHI->addIncoming(V, Preds[i]); 447 } 448 InVal = NewPHI; 449 } 450 451 // Add an incoming value to the PHI node in the loop for the preheader 452 // edge. 453 PN->addIncoming(InVal, NewBB); 454 } 455 456 return NewBB; 457} 458 459/// FindFunctionBackedges - Analyze the specified function to find all of the 460/// loop backedges in the function and return them. This is a relatively cheap 461/// (compared to computing dominators and loop info) analysis. 462/// 463/// The output is added to Result, as pairs of <from,to> edge info. 464void llvm::FindFunctionBackedges(const Function &F, 465 SmallVectorImpl<std::pair<const BasicBlock*,const BasicBlock*> > &Result) { 466 const BasicBlock *BB = &F.getEntryBlock(); 467 if (succ_begin(BB) == succ_end(BB)) 468 return; 469 470 SmallPtrSet<const BasicBlock*, 8> Visited; 471 SmallVector<std::pair<const BasicBlock*, succ_const_iterator>, 8> VisitStack; 472 SmallPtrSet<const BasicBlock*, 8> InStack; 473 474 Visited.insert(BB); 475 VisitStack.push_back(std::make_pair(BB, succ_begin(BB))); 476 InStack.insert(BB); 477 do { 478 std::pair<const BasicBlock*, succ_const_iterator> &Top = VisitStack.back(); 479 const BasicBlock *ParentBB = Top.first; 480 succ_const_iterator &I = Top.second; 481 482 bool FoundNew = false; 483 while (I != succ_end(ParentBB)) { 484 BB = *I++; 485 if (Visited.insert(BB)) { 486 FoundNew = true; 487 break; 488 } 489 // Successor is in VisitStack, it's a back edge. 490 if (InStack.count(BB)) 491 Result.push_back(std::make_pair(ParentBB, BB)); 492 } 493 494 if (FoundNew) { 495 // Go down one level if there is a unvisited successor. 496 InStack.insert(BB); 497 VisitStack.push_back(std::make_pair(BB, succ_begin(BB))); 498 } else { 499 // Go up one level. 500 InStack.erase(VisitStack.pop_back_val().first); 501 } 502 } while (!VisitStack.empty()); 503 504 505} 506