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