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/Analysis/AliasAnalysis.h" 17 #include "llvm/Analysis/CFG.h" 18 #include "llvm/Analysis/LoopInfo.h" 19 #include "llvm/Analysis/MemoryDependenceAnalysis.h" 20 #include "llvm/IR/Constant.h" 21 #include "llvm/IR/DataLayout.h" 22 #include "llvm/IR/Dominators.h" 23 #include "llvm/IR/Function.h" 24 #include "llvm/IR/Instructions.h" 25 #include "llvm/IR/IntrinsicInst.h" 26 #include "llvm/IR/Type.h" 27 #include "llvm/IR/ValueHandle.h" 28 #include "llvm/Support/ErrorHandling.h" 29 #include "llvm/Transforms/Scalar.h" 30 #include "llvm/Transforms/Utils/Local.h" 31 #include <algorithm> 32 using namespace llvm; 33 34 /// DeleteDeadBlock - Delete the specified block, which must have no 35 /// predecessors. 36 void llvm::DeleteDeadBlock(BasicBlock *BB) { 37 assert((pred_begin(BB) == pred_end(BB) || 38 // Can delete self loop. 39 BB->getSinglePredecessor() == BB) && "Block is not dead!"); 40 TerminatorInst *BBTerm = BB->getTerminator(); 41 42 // Loop through all of our successors and make sure they know that one 43 // of their predecessors is going away. 44 for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i) 45 BBTerm->getSuccessor(i)->removePredecessor(BB); 46 47 // Zap all the instructions in the block. 48 while (!BB->empty()) { 49 Instruction &I = BB->back(); 50 // If this instruction is used, replace uses with an arbitrary value. 51 // Because control flow can't get here, we don't care what we replace the 52 // value with. Note that since this block is unreachable, and all values 53 // contained within it must dominate their uses, that all uses will 54 // eventually be removed (they are themselves dead). 55 if (!I.use_empty()) 56 I.replaceAllUsesWith(UndefValue::get(I.getType())); 57 BB->getInstList().pop_back(); 58 } 59 60 // Zap the block! 61 BB->eraseFromParent(); 62 } 63 64 /// FoldSingleEntryPHINodes - We know that BB has one predecessor. If there are 65 /// any single-entry PHI nodes in it, fold them away. This handles the case 66 /// when all entries to the PHI nodes in a block are guaranteed equal, such as 67 /// when the block has exactly one predecessor. 68 void llvm::FoldSingleEntryPHINodes(BasicBlock *BB, AliasAnalysis *AA, 69 MemoryDependenceAnalysis *MemDep) { 70 if (!isa<PHINode>(BB->begin())) return; 71 72 while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 73 if (PN->getIncomingValue(0) != PN) 74 PN->replaceAllUsesWith(PN->getIncomingValue(0)); 75 else 76 PN->replaceAllUsesWith(UndefValue::get(PN->getType())); 77 78 if (MemDep) 79 MemDep->removeInstruction(PN); // Memdep updates AA itself. 80 else if (AA && isa<PointerType>(PN->getType())) 81 AA->deleteValue(PN); 82 83 PN->eraseFromParent(); 84 } 85 } 86 87 88 /// DeleteDeadPHIs - Examine each PHI in the given block and delete it if it 89 /// is dead. Also recursively delete any operands that become dead as 90 /// a result. This includes tracing the def-use list from the PHI to see if 91 /// it is ultimately unused or if it reaches an unused cycle. 92 bool llvm::DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI) { 93 // Recursively deleting a PHI may cause multiple PHIs to be deleted 94 // or RAUW'd undef, so use an array of WeakVH for the PHIs to delete. 95 SmallVector<WeakVH, 8> PHIs; 96 for (BasicBlock::iterator I = BB->begin(); 97 PHINode *PN = dyn_cast<PHINode>(I); ++I) 98 PHIs.push_back(PN); 99 100 bool Changed = false; 101 for (unsigned i = 0, e = PHIs.size(); i != e; ++i) 102 if (PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i].operator Value*())) 103 Changed |= RecursivelyDeleteDeadPHINode(PN, TLI); 104 105 return Changed; 106 } 107 108 /// MergeBlockIntoPredecessor - Attempts to merge a block into its predecessor, 109 /// if possible. The return value indicates success or failure. 110 bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT, 111 LoopInfo *LI, AliasAnalysis *AA, 112 MemoryDependenceAnalysis *MemDep) { 113 // Don't merge away blocks who have their address taken. 114 if (BB->hasAddressTaken()) return false; 115 116 // Can't merge if there are multiple predecessors, or no predecessors. 117 BasicBlock *PredBB = BB->getUniquePredecessor(); 118 if (!PredBB) return false; 119 120 // Don't break self-loops. 121 if (PredBB == BB) return false; 122 // Don't break invokes. 123 if (isa<InvokeInst>(PredBB->getTerminator())) return false; 124 125 succ_iterator SI(succ_begin(PredBB)), SE(succ_end(PredBB)); 126 BasicBlock *OnlySucc = BB; 127 for (; SI != SE; ++SI) 128 if (*SI != OnlySucc) { 129 OnlySucc = nullptr; // There are multiple distinct successors! 130 break; 131 } 132 133 // Can't merge if there are multiple successors. 134 if (!OnlySucc) return false; 135 136 // Can't merge if there is PHI loop. 137 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE; ++BI) { 138 if (PHINode *PN = dyn_cast<PHINode>(BI)) { 139 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 140 if (PN->getIncomingValue(i) == PN) 141 return false; 142 } else 143 break; 144 } 145 146 // Begin by getting rid of unneeded PHIs. 147 if (isa<PHINode>(BB->front())) 148 FoldSingleEntryPHINodes(BB, AA, MemDep); 149 150 // Delete the unconditional branch from the predecessor... 151 PredBB->getInstList().pop_back(); 152 153 // Make all PHI nodes that referred to BB now refer to Pred as their 154 // source... 155 BB->replaceAllUsesWith(PredBB); 156 157 // Move all definitions in the successor to the predecessor... 158 PredBB->getInstList().splice(PredBB->end(), BB->getInstList()); 159 160 // Inherit predecessors name if it exists. 161 if (!PredBB->hasName()) 162 PredBB->takeName(BB); 163 164 // Finally, erase the old block and update dominator info. 165 if (DT) 166 if (DomTreeNode *DTN = DT->getNode(BB)) { 167 DomTreeNode *PredDTN = DT->getNode(PredBB); 168 SmallVector<DomTreeNode *, 8> Children(DTN->begin(), DTN->end()); 169 for (SmallVectorImpl<DomTreeNode *>::iterator DI = Children.begin(), 170 DE = Children.end(); 171 DI != DE; ++DI) 172 DT->changeImmediateDominator(*DI, PredDTN); 173 174 DT->eraseNode(BB); 175 } 176 177 if (LI) 178 LI->removeBlock(BB); 179 180 if (MemDep) 181 MemDep->invalidateCachedPredecessors(); 182 183 BB->eraseFromParent(); 184 return true; 185 } 186 187 /// ReplaceInstWithValue - Replace all uses of an instruction (specified by BI) 188 /// with a value, then remove and delete the original instruction. 189 /// 190 void llvm::ReplaceInstWithValue(BasicBlock::InstListType &BIL, 191 BasicBlock::iterator &BI, Value *V) { 192 Instruction &I = *BI; 193 // Replaces all of the uses of the instruction with uses of the value 194 I.replaceAllUsesWith(V); 195 196 // Make sure to propagate a name if there is one already. 197 if (I.hasName() && !V->hasName()) 198 V->takeName(&I); 199 200 // Delete the unnecessary instruction now... 201 BI = BIL.erase(BI); 202 } 203 204 205 /// ReplaceInstWithInst - Replace the instruction specified by BI with the 206 /// instruction specified by I. The original instruction is deleted and BI is 207 /// updated to point to the new instruction. 208 /// 209 void llvm::ReplaceInstWithInst(BasicBlock::InstListType &BIL, 210 BasicBlock::iterator &BI, Instruction *I) { 211 assert(I->getParent() == nullptr && 212 "ReplaceInstWithInst: Instruction already inserted into basic block!"); 213 214 // Insert the new instruction into the basic block... 215 BasicBlock::iterator New = BIL.insert(BI, I); 216 217 // Replace all uses of the old instruction, and delete it. 218 ReplaceInstWithValue(BIL, BI, I); 219 220 // Move BI back to point to the newly inserted instruction 221 BI = New; 222 } 223 224 /// ReplaceInstWithInst - Replace the instruction specified by From with the 225 /// instruction specified by To. 226 /// 227 void llvm::ReplaceInstWithInst(Instruction *From, Instruction *To) { 228 BasicBlock::iterator BI(From); 229 ReplaceInstWithInst(From->getParent()->getInstList(), BI, To); 230 } 231 232 /// SplitEdge - Split the edge connecting specified block. Pass P must 233 /// not be NULL. 234 BasicBlock *llvm::SplitEdge(BasicBlock *BB, BasicBlock *Succ, DominatorTree *DT, 235 LoopInfo *LI) { 236 unsigned SuccNum = GetSuccessorNumber(BB, Succ); 237 238 // If this is a critical edge, let SplitCriticalEdge do it. 239 TerminatorInst *LatchTerm = BB->getTerminator(); 240 if (SplitCriticalEdge(LatchTerm, SuccNum, CriticalEdgeSplittingOptions(DT, LI) 241 .setPreserveLCSSA())) 242 return LatchTerm->getSuccessor(SuccNum); 243 244 // If the edge isn't critical, then BB has a single successor or Succ has a 245 // single pred. Split the block. 246 if (BasicBlock *SP = Succ->getSinglePredecessor()) { 247 // If the successor only has a single pred, split the top of the successor 248 // block. 249 assert(SP == BB && "CFG broken"); 250 SP = nullptr; 251 return SplitBlock(Succ, Succ->begin(), DT, LI); 252 } 253 254 // Otherwise, if BB has a single successor, split it at the bottom of the 255 // block. 256 assert(BB->getTerminator()->getNumSuccessors() == 1 && 257 "Should have a single succ!"); 258 return SplitBlock(BB, BB->getTerminator(), DT, LI); 259 } 260 261 unsigned 262 llvm::SplitAllCriticalEdges(Function &F, 263 const CriticalEdgeSplittingOptions &Options) { 264 unsigned NumBroken = 0; 265 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) { 266 TerminatorInst *TI = I->getTerminator(); 267 if (TI->getNumSuccessors() > 1 && !isa<IndirectBrInst>(TI)) 268 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 269 if (SplitCriticalEdge(TI, i, Options)) 270 ++NumBroken; 271 } 272 return NumBroken; 273 } 274 275 /// SplitBlock - Split the specified block at the specified instruction - every 276 /// thing before SplitPt stays in Old and everything starting with SplitPt moves 277 /// to a new block. The two blocks are joined by an unconditional branch and 278 /// the loop info is updated. 279 /// 280 BasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt, 281 DominatorTree *DT, LoopInfo *LI) { 282 BasicBlock::iterator SplitIt = SplitPt; 283 while (isa<PHINode>(SplitIt) || isa<LandingPadInst>(SplitIt)) 284 ++SplitIt; 285 BasicBlock *New = Old->splitBasicBlock(SplitIt, Old->getName()+".split"); 286 287 // The new block lives in whichever loop the old one did. This preserves 288 // LCSSA as well, because we force the split point to be after any PHI nodes. 289 if (LI) 290 if (Loop *L = LI->getLoopFor(Old)) 291 L->addBasicBlockToLoop(New, *LI); 292 293 if (DT) 294 // Old dominates New. New node dominates all other nodes dominated by Old. 295 if (DomTreeNode *OldNode = DT->getNode(Old)) { 296 std::vector<DomTreeNode *> Children; 297 for (DomTreeNode::iterator I = OldNode->begin(), E = OldNode->end(); 298 I != E; ++I) 299 Children.push_back(*I); 300 301 DomTreeNode *NewNode = DT->addNewBlock(New, Old); 302 for (std::vector<DomTreeNode *>::iterator I = Children.begin(), 303 E = Children.end(); I != E; ++I) 304 DT->changeImmediateDominator(*I, NewNode); 305 } 306 307 return New; 308 } 309 310 /// UpdateAnalysisInformation - Update DominatorTree, LoopInfo, and LCCSA 311 /// analysis information. 312 static void UpdateAnalysisInformation(BasicBlock *OldBB, BasicBlock *NewBB, 313 ArrayRef<BasicBlock *> Preds, 314 DominatorTree *DT, LoopInfo *LI, 315 bool PreserveLCSSA, bool &HasLoopExit) { 316 // Update dominator tree if available. 317 if (DT) 318 DT->splitBlock(NewBB); 319 320 // The rest of the logic is only relevant for updating the loop structures. 321 if (!LI) 322 return; 323 324 Loop *L = LI->getLoopFor(OldBB); 325 326 // If we need to preserve loop analyses, collect some information about how 327 // this split will affect loops. 328 bool IsLoopEntry = !!L; 329 bool SplitMakesNewLoopHeader = false; 330 for (ArrayRef<BasicBlock *>::iterator i = Preds.begin(), e = Preds.end(); 331 i != e; ++i) { 332 BasicBlock *Pred = *i; 333 334 // If we need to preserve LCSSA, determine if any of the preds is a loop 335 // exit. 336 if (PreserveLCSSA) 337 if (Loop *PL = LI->getLoopFor(Pred)) 338 if (!PL->contains(OldBB)) 339 HasLoopExit = true; 340 341 // If we need to preserve LoopInfo, note whether any of the preds crosses 342 // an interesting loop boundary. 343 if (!L) 344 continue; 345 if (L->contains(Pred)) 346 IsLoopEntry = false; 347 else 348 SplitMakesNewLoopHeader = true; 349 } 350 351 // Unless we have a loop for OldBB, nothing else to do here. 352 if (!L) 353 return; 354 355 if (IsLoopEntry) { 356 // Add the new block to the nearest enclosing loop (and not an adjacent 357 // loop). To find this, examine each of the predecessors and determine which 358 // loops enclose them, and select the most-nested loop which contains the 359 // loop containing the block being split. 360 Loop *InnermostPredLoop = nullptr; 361 for (ArrayRef<BasicBlock*>::iterator 362 i = Preds.begin(), e = Preds.end(); i != e; ++i) { 363 BasicBlock *Pred = *i; 364 if (Loop *PredLoop = LI->getLoopFor(Pred)) { 365 // Seek a loop which actually contains the block being split (to avoid 366 // adjacent loops). 367 while (PredLoop && !PredLoop->contains(OldBB)) 368 PredLoop = PredLoop->getParentLoop(); 369 370 // Select the most-nested of these loops which contains the block. 371 if (PredLoop && PredLoop->contains(OldBB) && 372 (!InnermostPredLoop || 373 InnermostPredLoop->getLoopDepth() < PredLoop->getLoopDepth())) 374 InnermostPredLoop = PredLoop; 375 } 376 } 377 378 if (InnermostPredLoop) 379 InnermostPredLoop->addBasicBlockToLoop(NewBB, *LI); 380 } else { 381 L->addBasicBlockToLoop(NewBB, *LI); 382 if (SplitMakesNewLoopHeader) 383 L->moveToHeader(NewBB); 384 } 385 } 386 387 /// UpdatePHINodes - Update the PHI nodes in OrigBB to include the values coming 388 /// from NewBB. This also updates AliasAnalysis, if available. 389 static void UpdatePHINodes(BasicBlock *OrigBB, BasicBlock *NewBB, 390 ArrayRef<BasicBlock *> Preds, BranchInst *BI, 391 AliasAnalysis *AA, bool HasLoopExit) { 392 // Otherwise, create a new PHI node in NewBB for each PHI node in OrigBB. 393 SmallPtrSet<BasicBlock *, 16> PredSet(Preds.begin(), Preds.end()); 394 for (BasicBlock::iterator I = OrigBB->begin(); isa<PHINode>(I); ) { 395 PHINode *PN = cast<PHINode>(I++); 396 397 // Check to see if all of the values coming in are the same. If so, we 398 // don't need to create a new PHI node, unless it's needed for LCSSA. 399 Value *InVal = nullptr; 400 if (!HasLoopExit) { 401 InVal = PN->getIncomingValueForBlock(Preds[0]); 402 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 403 if (!PredSet.count(PN->getIncomingBlock(i))) 404 continue; 405 if (!InVal) 406 InVal = PN->getIncomingValue(i); 407 else if (InVal != PN->getIncomingValue(i)) { 408 InVal = nullptr; 409 break; 410 } 411 } 412 } 413 414 if (InVal) { 415 // If all incoming values for the new PHI would be the same, just don't 416 // make a new PHI. Instead, just remove the incoming values from the old 417 // PHI. 418 419 // NOTE! This loop walks backwards for a reason! First off, this minimizes 420 // the cost of removal if we end up removing a large number of values, and 421 // second off, this ensures that the indices for the incoming values 422 // aren't invalidated when we remove one. 423 for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i) 424 if (PredSet.count(PN->getIncomingBlock(i))) 425 PN->removeIncomingValue(i, false); 426 427 // Add an incoming value to the PHI node in the loop for the preheader 428 // edge. 429 PN->addIncoming(InVal, NewBB); 430 continue; 431 } 432 433 // If the values coming into the block are not the same, we need a new 434 // PHI. 435 // Create the new PHI node, insert it into NewBB at the end of the block 436 PHINode *NewPHI = 437 PHINode::Create(PN->getType(), Preds.size(), PN->getName() + ".ph", BI); 438 if (AA) 439 AA->copyValue(PN, NewPHI); 440 441 // NOTE! This loop walks backwards for a reason! First off, this minimizes 442 // the cost of removal if we end up removing a large number of values, and 443 // second off, this ensures that the indices for the incoming values aren't 444 // invalidated when we remove one. 445 for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i) { 446 BasicBlock *IncomingBB = PN->getIncomingBlock(i); 447 if (PredSet.count(IncomingBB)) { 448 Value *V = PN->removeIncomingValue(i, false); 449 NewPHI->addIncoming(V, IncomingBB); 450 } 451 } 452 453 PN->addIncoming(NewPHI, NewBB); 454 } 455 } 456 457 /// SplitBlockPredecessors - This method introduces at least one new basic block 458 /// into the function and moves some of the predecessors of BB to be 459 /// predecessors of the new block. The new predecessors are indicated by the 460 /// Preds array. The new block is given a suffix of 'Suffix'. Returns new basic 461 /// block to which predecessors from Preds are now pointing. 462 /// 463 /// If BB is a landingpad block then additional basicblock might be introduced. 464 /// It will have suffix of 'Suffix'+".split_lp". 465 /// See SplitLandingPadPredecessors for more details on this case. 466 /// 467 /// This currently updates the LLVM IR, AliasAnalysis, DominatorTree, 468 /// LoopInfo, and LCCSA but no other analyses. In particular, it does not 469 /// preserve LoopSimplify (because it's complicated to handle the case where one 470 /// of the edges being split is an exit of a loop with other exits). 471 /// 472 BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB, 473 ArrayRef<BasicBlock *> Preds, 474 const char *Suffix, AliasAnalysis *AA, 475 DominatorTree *DT, LoopInfo *LI, 476 bool PreserveLCSSA) { 477 // For the landingpads we need to act a bit differently. 478 // Delegate this work to the SplitLandingPadPredecessors. 479 if (BB->isLandingPad()) { 480 SmallVector<BasicBlock*, 2> NewBBs; 481 std::string NewName = std::string(Suffix) + ".split-lp"; 482 483 SplitLandingPadPredecessors(BB, Preds, Suffix, NewName.c_str(), 484 NewBBs, AA, DT, LI, PreserveLCSSA); 485 return NewBBs[0]; 486 } 487 488 // Create new basic block, insert right before the original block. 489 BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), BB->getName()+Suffix, 490 BB->getParent(), BB); 491 492 // The new block unconditionally branches to the old block. 493 BranchInst *BI = BranchInst::Create(BB, NewBB); 494 495 // Move the edges from Preds to point to NewBB instead of BB. 496 for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 497 // This is slightly more strict than necessary; the minimum requirement 498 // is that there be no more than one indirectbr branching to BB. And 499 // all BlockAddress uses would need to be updated. 500 assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) && 501 "Cannot split an edge from an IndirectBrInst"); 502 Preds[i]->getTerminator()->replaceUsesOfWith(BB, NewBB); 503 } 504 505 // Insert a new PHI node into NewBB for every PHI node in BB and that new PHI 506 // node becomes an incoming value for BB's phi node. However, if the Preds 507 // list is empty, we need to insert dummy entries into the PHI nodes in BB to 508 // account for the newly created predecessor. 509 if (Preds.size() == 0) { 510 // Insert dummy values as the incoming value. 511 for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I) 512 cast<PHINode>(I)->addIncoming(UndefValue::get(I->getType()), NewBB); 513 return NewBB; 514 } 515 516 // Update DominatorTree, LoopInfo, and LCCSA analysis information. 517 bool HasLoopExit = false; 518 UpdateAnalysisInformation(BB, NewBB, Preds, DT, LI, PreserveLCSSA, 519 HasLoopExit); 520 521 // Update the PHI nodes in BB with the values coming from NewBB. 522 UpdatePHINodes(BB, NewBB, Preds, BI, AA, HasLoopExit); 523 return NewBB; 524 } 525 526 /// SplitLandingPadPredecessors - This method transforms the landing pad, 527 /// OrigBB, by introducing two new basic blocks into the function. One of those 528 /// new basic blocks gets the predecessors listed in Preds. The other basic 529 /// block gets the remaining predecessors of OrigBB. The landingpad instruction 530 /// OrigBB is clone into both of the new basic blocks. The new blocks are given 531 /// the suffixes 'Suffix1' and 'Suffix2', and are returned in the NewBBs vector. 532 /// 533 /// This currently updates the LLVM IR, AliasAnalysis, DominatorTree, 534 /// DominanceFrontier, LoopInfo, and LCCSA but no other analyses. In particular, 535 /// it does not preserve LoopSimplify (because it's complicated to handle the 536 /// case where one of the edges being split is an exit of a loop with other 537 /// exits). 538 /// 539 void llvm::SplitLandingPadPredecessors(BasicBlock *OrigBB, 540 ArrayRef<BasicBlock *> Preds, 541 const char *Suffix1, const char *Suffix2, 542 SmallVectorImpl<BasicBlock *> &NewBBs, 543 AliasAnalysis *AA, DominatorTree *DT, 544 LoopInfo *LI, bool PreserveLCSSA) { 545 assert(OrigBB->isLandingPad() && "Trying to split a non-landing pad!"); 546 547 // Create a new basic block for OrigBB's predecessors listed in Preds. Insert 548 // it right before the original block. 549 BasicBlock *NewBB1 = BasicBlock::Create(OrigBB->getContext(), 550 OrigBB->getName() + Suffix1, 551 OrigBB->getParent(), OrigBB); 552 NewBBs.push_back(NewBB1); 553 554 // The new block unconditionally branches to the old block. 555 BranchInst *BI1 = BranchInst::Create(OrigBB, NewBB1); 556 557 // Move the edges from Preds to point to NewBB1 instead of OrigBB. 558 for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 559 // This is slightly more strict than necessary; the minimum requirement 560 // is that there be no more than one indirectbr branching to BB. And 561 // all BlockAddress uses would need to be updated. 562 assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) && 563 "Cannot split an edge from an IndirectBrInst"); 564 Preds[i]->getTerminator()->replaceUsesOfWith(OrigBB, NewBB1); 565 } 566 567 bool HasLoopExit = false; 568 UpdateAnalysisInformation(OrigBB, NewBB1, Preds, DT, LI, PreserveLCSSA, 569 HasLoopExit); 570 571 // Update the PHI nodes in OrigBB with the values coming from NewBB1. 572 UpdatePHINodes(OrigBB, NewBB1, Preds, BI1, AA, HasLoopExit); 573 574 // Move the remaining edges from OrigBB to point to NewBB2. 575 SmallVector<BasicBlock*, 8> NewBB2Preds; 576 for (pred_iterator i = pred_begin(OrigBB), e = pred_end(OrigBB); 577 i != e; ) { 578 BasicBlock *Pred = *i++; 579 if (Pred == NewBB1) continue; 580 assert(!isa<IndirectBrInst>(Pred->getTerminator()) && 581 "Cannot split an edge from an IndirectBrInst"); 582 NewBB2Preds.push_back(Pred); 583 e = pred_end(OrigBB); 584 } 585 586 BasicBlock *NewBB2 = nullptr; 587 if (!NewBB2Preds.empty()) { 588 // Create another basic block for the rest of OrigBB's predecessors. 589 NewBB2 = BasicBlock::Create(OrigBB->getContext(), 590 OrigBB->getName() + Suffix2, 591 OrigBB->getParent(), OrigBB); 592 NewBBs.push_back(NewBB2); 593 594 // The new block unconditionally branches to the old block. 595 BranchInst *BI2 = BranchInst::Create(OrigBB, NewBB2); 596 597 // Move the remaining edges from OrigBB to point to NewBB2. 598 for (SmallVectorImpl<BasicBlock*>::iterator 599 i = NewBB2Preds.begin(), e = NewBB2Preds.end(); i != e; ++i) 600 (*i)->getTerminator()->replaceUsesOfWith(OrigBB, NewBB2); 601 602 // Update DominatorTree, LoopInfo, and LCCSA analysis information. 603 HasLoopExit = false; 604 UpdateAnalysisInformation(OrigBB, NewBB2, NewBB2Preds, DT, LI, 605 PreserveLCSSA, HasLoopExit); 606 607 // Update the PHI nodes in OrigBB with the values coming from NewBB2. 608 UpdatePHINodes(OrigBB, NewBB2, NewBB2Preds, BI2, AA, HasLoopExit); 609 } 610 611 LandingPadInst *LPad = OrigBB->getLandingPadInst(); 612 Instruction *Clone1 = LPad->clone(); 613 Clone1->setName(Twine("lpad") + Suffix1); 614 NewBB1->getInstList().insert(NewBB1->getFirstInsertionPt(), Clone1); 615 616 if (NewBB2) { 617 Instruction *Clone2 = LPad->clone(); 618 Clone2->setName(Twine("lpad") + Suffix2); 619 NewBB2->getInstList().insert(NewBB2->getFirstInsertionPt(), Clone2); 620 621 // Create a PHI node for the two cloned landingpad instructions. 622 PHINode *PN = PHINode::Create(LPad->getType(), 2, "lpad.phi", LPad); 623 PN->addIncoming(Clone1, NewBB1); 624 PN->addIncoming(Clone2, NewBB2); 625 LPad->replaceAllUsesWith(PN); 626 LPad->eraseFromParent(); 627 } else { 628 // There is no second clone. Just replace the landing pad with the first 629 // clone. 630 LPad->replaceAllUsesWith(Clone1); 631 LPad->eraseFromParent(); 632 } 633 } 634 635 /// FoldReturnIntoUncondBranch - This method duplicates the specified return 636 /// instruction into a predecessor which ends in an unconditional branch. If 637 /// the return instruction returns a value defined by a PHI, propagate the 638 /// right value into the return. It returns the new return instruction in the 639 /// predecessor. 640 ReturnInst *llvm::FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB, 641 BasicBlock *Pred) { 642 Instruction *UncondBranch = Pred->getTerminator(); 643 // Clone the return and add it to the end of the predecessor. 644 Instruction *NewRet = RI->clone(); 645 Pred->getInstList().push_back(NewRet); 646 647 // If the return instruction returns a value, and if the value was a 648 // PHI node in "BB", propagate the right value into the return. 649 for (User::op_iterator i = NewRet->op_begin(), e = NewRet->op_end(); 650 i != e; ++i) { 651 Value *V = *i; 652 Instruction *NewBC = nullptr; 653 if (BitCastInst *BCI = dyn_cast<BitCastInst>(V)) { 654 // Return value might be bitcasted. Clone and insert it before the 655 // return instruction. 656 V = BCI->getOperand(0); 657 NewBC = BCI->clone(); 658 Pred->getInstList().insert(NewRet, NewBC); 659 *i = NewBC; 660 } 661 if (PHINode *PN = dyn_cast<PHINode>(V)) { 662 if (PN->getParent() == BB) { 663 if (NewBC) 664 NewBC->setOperand(0, PN->getIncomingValueForBlock(Pred)); 665 else 666 *i = PN->getIncomingValueForBlock(Pred); 667 } 668 } 669 } 670 671 // Update any PHI nodes in the returning block to realize that we no 672 // longer branch to them. 673 BB->removePredecessor(Pred); 674 UncondBranch->eraseFromParent(); 675 return cast<ReturnInst>(NewRet); 676 } 677 678 /// SplitBlockAndInsertIfThen - Split the containing block at the 679 /// specified instruction - everything before and including SplitBefore stays 680 /// in the old basic block, and everything after SplitBefore is moved to a 681 /// new block. The two blocks are connected by a conditional branch 682 /// (with value of Cmp being the condition). 683 /// Before: 684 /// Head 685 /// SplitBefore 686 /// Tail 687 /// After: 688 /// Head 689 /// if (Cond) 690 /// ThenBlock 691 /// SplitBefore 692 /// Tail 693 /// 694 /// If Unreachable is true, then ThenBlock ends with 695 /// UnreachableInst, otherwise it branches to Tail. 696 /// Returns the NewBasicBlock's terminator. 697 698 TerminatorInst *llvm::SplitBlockAndInsertIfThen(Value *Cond, 699 Instruction *SplitBefore, 700 bool Unreachable, 701 MDNode *BranchWeights, 702 DominatorTree *DT) { 703 BasicBlock *Head = SplitBefore->getParent(); 704 BasicBlock *Tail = Head->splitBasicBlock(SplitBefore); 705 TerminatorInst *HeadOldTerm = Head->getTerminator(); 706 LLVMContext &C = Head->getContext(); 707 BasicBlock *ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail); 708 TerminatorInst *CheckTerm; 709 if (Unreachable) 710 CheckTerm = new UnreachableInst(C, ThenBlock); 711 else 712 CheckTerm = BranchInst::Create(Tail, ThenBlock); 713 CheckTerm->setDebugLoc(SplitBefore->getDebugLoc()); 714 BranchInst *HeadNewTerm = 715 BranchInst::Create(/*ifTrue*/ThenBlock, /*ifFalse*/Tail, Cond); 716 HeadNewTerm->setDebugLoc(SplitBefore->getDebugLoc()); 717 HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights); 718 ReplaceInstWithInst(HeadOldTerm, HeadNewTerm); 719 720 if (DT) { 721 if (DomTreeNode *OldNode = DT->getNode(Head)) { 722 std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end()); 723 724 DomTreeNode *NewNode = DT->addNewBlock(Tail, Head); 725 for (auto Child : Children) 726 DT->changeImmediateDominator(Child, NewNode); 727 728 // Head dominates ThenBlock. 729 DT->addNewBlock(ThenBlock, Head); 730 } 731 } 732 733 return CheckTerm; 734 } 735 736 /// SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen, 737 /// but also creates the ElseBlock. 738 /// Before: 739 /// Head 740 /// SplitBefore 741 /// Tail 742 /// After: 743 /// Head 744 /// if (Cond) 745 /// ThenBlock 746 /// else 747 /// ElseBlock 748 /// SplitBefore 749 /// Tail 750 void llvm::SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore, 751 TerminatorInst **ThenTerm, 752 TerminatorInst **ElseTerm, 753 MDNode *BranchWeights) { 754 BasicBlock *Head = SplitBefore->getParent(); 755 BasicBlock *Tail = Head->splitBasicBlock(SplitBefore); 756 TerminatorInst *HeadOldTerm = Head->getTerminator(); 757 LLVMContext &C = Head->getContext(); 758 BasicBlock *ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail); 759 BasicBlock *ElseBlock = BasicBlock::Create(C, "", Head->getParent(), Tail); 760 *ThenTerm = BranchInst::Create(Tail, ThenBlock); 761 (*ThenTerm)->setDebugLoc(SplitBefore->getDebugLoc()); 762 *ElseTerm = BranchInst::Create(Tail, ElseBlock); 763 (*ElseTerm)->setDebugLoc(SplitBefore->getDebugLoc()); 764 BranchInst *HeadNewTerm = 765 BranchInst::Create(/*ifTrue*/ThenBlock, /*ifFalse*/ElseBlock, Cond); 766 HeadNewTerm->setDebugLoc(SplitBefore->getDebugLoc()); 767 HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights); 768 ReplaceInstWithInst(HeadOldTerm, HeadNewTerm); 769 } 770 771 772 /// GetIfCondition - Given a basic block (BB) with two predecessors, 773 /// check to see if the merge at this block is due 774 /// to an "if condition". If so, return the boolean condition that determines 775 /// which entry into BB will be taken. Also, return by references the block 776 /// that will be entered from if the condition is true, and the block that will 777 /// be entered if the condition is false. 778 /// 779 /// This does no checking to see if the true/false blocks have large or unsavory 780 /// instructions in them. 781 Value *llvm::GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, 782 BasicBlock *&IfFalse) { 783 PHINode *SomePHI = dyn_cast<PHINode>(BB->begin()); 784 BasicBlock *Pred1 = nullptr; 785 BasicBlock *Pred2 = nullptr; 786 787 if (SomePHI) { 788 if (SomePHI->getNumIncomingValues() != 2) 789 return nullptr; 790 Pred1 = SomePHI->getIncomingBlock(0); 791 Pred2 = SomePHI->getIncomingBlock(1); 792 } else { 793 pred_iterator PI = pred_begin(BB), PE = pred_end(BB); 794 if (PI == PE) // No predecessor 795 return nullptr; 796 Pred1 = *PI++; 797 if (PI == PE) // Only one predecessor 798 return nullptr; 799 Pred2 = *PI++; 800 if (PI != PE) // More than two predecessors 801 return nullptr; 802 } 803 804 // We can only handle branches. Other control flow will be lowered to 805 // branches if possible anyway. 806 BranchInst *Pred1Br = dyn_cast<BranchInst>(Pred1->getTerminator()); 807 BranchInst *Pred2Br = dyn_cast<BranchInst>(Pred2->getTerminator()); 808 if (!Pred1Br || !Pred2Br) 809 return nullptr; 810 811 // Eliminate code duplication by ensuring that Pred1Br is conditional if 812 // either are. 813 if (Pred2Br->isConditional()) { 814 // If both branches are conditional, we don't have an "if statement". In 815 // reality, we could transform this case, but since the condition will be 816 // required anyway, we stand no chance of eliminating it, so the xform is 817 // probably not profitable. 818 if (Pred1Br->isConditional()) 819 return nullptr; 820 821 std::swap(Pred1, Pred2); 822 std::swap(Pred1Br, Pred2Br); 823 } 824 825 if (Pred1Br->isConditional()) { 826 // The only thing we have to watch out for here is to make sure that Pred2 827 // doesn't have incoming edges from other blocks. If it does, the condition 828 // doesn't dominate BB. 829 if (!Pred2->getSinglePredecessor()) 830 return nullptr; 831 832 // If we found a conditional branch predecessor, make sure that it branches 833 // to BB and Pred2Br. If it doesn't, this isn't an "if statement". 834 if (Pred1Br->getSuccessor(0) == BB && 835 Pred1Br->getSuccessor(1) == Pred2) { 836 IfTrue = Pred1; 837 IfFalse = Pred2; 838 } else if (Pred1Br->getSuccessor(0) == Pred2 && 839 Pred1Br->getSuccessor(1) == BB) { 840 IfTrue = Pred2; 841 IfFalse = Pred1; 842 } else { 843 // We know that one arm of the conditional goes to BB, so the other must 844 // go somewhere unrelated, and this must not be an "if statement". 845 return nullptr; 846 } 847 848 return Pred1Br->getCondition(); 849 } 850 851 // Ok, if we got here, both predecessors end with an unconditional branch to 852 // BB. Don't panic! If both blocks only have a single (identical) 853 // predecessor, and THAT is a conditional branch, then we're all ok! 854 BasicBlock *CommonPred = Pred1->getSinglePredecessor(); 855 if (CommonPred == nullptr || CommonPred != Pred2->getSinglePredecessor()) 856 return nullptr; 857 858 // Otherwise, if this is a conditional branch, then we can use it! 859 BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator()); 860 if (!BI) return nullptr; 861 862 assert(BI->isConditional() && "Two successors but not conditional?"); 863 if (BI->getSuccessor(0) == Pred1) { 864 IfTrue = Pred1; 865 IfFalse = Pred2; 866 } else { 867 IfTrue = Pred2; 868 IfFalse = Pred1; 869 } 870 return BI->getCondition(); 871 } 872