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