1 //===- BasicBlockUtils.cpp - BasicBlock Utilities --------------------------==// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This family of functions perform manipulations on basic blocks, and 10 // instructions contained within basic blocks. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 15 #include "llvm/ADT/ArrayRef.h" 16 #include "llvm/ADT/SmallPtrSet.h" 17 #include "llvm/ADT/SmallVector.h" 18 #include "llvm/ADT/Twine.h" 19 #include "llvm/Analysis/CFG.h" 20 #include "llvm/Analysis/DomTreeUpdater.h" 21 #include "llvm/Analysis/LoopInfo.h" 22 #include "llvm/Analysis/MemoryDependenceAnalysis.h" 23 #include "llvm/Analysis/MemorySSAUpdater.h" 24 #include "llvm/IR/BasicBlock.h" 25 #include "llvm/IR/CFG.h" 26 #include "llvm/IR/Constants.h" 27 #include "llvm/IR/DebugInfo.h" 28 #include "llvm/IR/DebugInfoMetadata.h" 29 #include "llvm/IR/Dominators.h" 30 #include "llvm/IR/Function.h" 31 #include "llvm/IR/InstrTypes.h" 32 #include "llvm/IR/Instruction.h" 33 #include "llvm/IR/Instructions.h" 34 #include "llvm/IR/IntrinsicInst.h" 35 #include "llvm/IR/LLVMContext.h" 36 #include "llvm/IR/Type.h" 37 #include "llvm/IR/User.h" 38 #include "llvm/IR/Value.h" 39 #include "llvm/IR/ValueHandle.h" 40 #include "llvm/Support/Casting.h" 41 #include "llvm/Support/CommandLine.h" 42 #include "llvm/Support/Debug.h" 43 #include "llvm/Support/raw_ostream.h" 44 #include "llvm/Transforms/Utils/Local.h" 45 #include <cassert> 46 #include <cstdint> 47 #include <string> 48 #include <utility> 49 #include <vector> 50 51 using namespace llvm; 52 53 #define DEBUG_TYPE "basicblock-utils" 54 55 static cl::opt<unsigned> MaxDeoptOrUnreachableSuccessorCheckDepth( 56 "max-deopt-or-unreachable-succ-check-depth", cl::init(8), cl::Hidden, 57 cl::desc("Set the maximum path length when checking whether a basic block " 58 "is followed by a block that either has a terminating " 59 "deoptimizing call or is terminated with an unreachable")); 60 61 void llvm::detachDeadBlocks( 62 ArrayRef<BasicBlock *> BBs, 63 SmallVectorImpl<DominatorTree::UpdateType> *Updates, 64 bool KeepOneInputPHIs) { 65 for (auto *BB : BBs) { 66 // Loop through all of our successors and make sure they know that one 67 // of their predecessors is going away. 68 SmallPtrSet<BasicBlock *, 4> UniqueSuccessors; 69 for (BasicBlock *Succ : successors(BB)) { 70 Succ->removePredecessor(BB, KeepOneInputPHIs); 71 if (Updates && UniqueSuccessors.insert(Succ).second) 72 Updates->push_back({DominatorTree::Delete, BB, Succ}); 73 } 74 75 // Zap all the instructions in the block. 76 while (!BB->empty()) { 77 Instruction &I = BB->back(); 78 // If this instruction is used, replace uses with an arbitrary value. 79 // Because control flow can't get here, we don't care what we replace the 80 // value with. Note that since this block is unreachable, and all values 81 // contained within it must dominate their uses, that all uses will 82 // eventually be removed (they are themselves dead). 83 if (!I.use_empty()) 84 I.replaceAllUsesWith(PoisonValue::get(I.getType())); 85 BB->back().eraseFromParent(); 86 } 87 new UnreachableInst(BB->getContext(), BB); 88 assert(BB->size() == 1 && 89 isa<UnreachableInst>(BB->getTerminator()) && 90 "The successor list of BB isn't empty before " 91 "applying corresponding DTU updates."); 92 } 93 } 94 95 void llvm::DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU, 96 bool KeepOneInputPHIs) { 97 DeleteDeadBlocks({BB}, DTU, KeepOneInputPHIs); 98 } 99 100 void llvm::DeleteDeadBlocks(ArrayRef <BasicBlock *> BBs, DomTreeUpdater *DTU, 101 bool KeepOneInputPHIs) { 102 #ifndef NDEBUG 103 // Make sure that all predecessors of each dead block is also dead. 104 SmallPtrSet<BasicBlock *, 4> Dead(BBs.begin(), BBs.end()); 105 assert(Dead.size() == BBs.size() && "Duplicating blocks?"); 106 for (auto *BB : Dead) 107 for (BasicBlock *Pred : predecessors(BB)) 108 assert(Dead.count(Pred) && "All predecessors must be dead!"); 109 #endif 110 111 SmallVector<DominatorTree::UpdateType, 4> Updates; 112 detachDeadBlocks(BBs, DTU ? &Updates : nullptr, KeepOneInputPHIs); 113 114 if (DTU) 115 DTU->applyUpdates(Updates); 116 117 for (BasicBlock *BB : BBs) 118 if (DTU) 119 DTU->deleteBB(BB); 120 else 121 BB->eraseFromParent(); 122 } 123 124 bool llvm::EliminateUnreachableBlocks(Function &F, DomTreeUpdater *DTU, 125 bool KeepOneInputPHIs) { 126 df_iterator_default_set<BasicBlock*> Reachable; 127 128 // Mark all reachable blocks. 129 for (BasicBlock *BB : depth_first_ext(&F, Reachable)) 130 (void)BB/* Mark all reachable blocks */; 131 132 // Collect all dead blocks. 133 std::vector<BasicBlock*> DeadBlocks; 134 for (BasicBlock &BB : F) 135 if (!Reachable.count(&BB)) 136 DeadBlocks.push_back(&BB); 137 138 // Delete the dead blocks. 139 DeleteDeadBlocks(DeadBlocks, DTU, KeepOneInputPHIs); 140 141 return !DeadBlocks.empty(); 142 } 143 144 bool llvm::FoldSingleEntryPHINodes(BasicBlock *BB, 145 MemoryDependenceResults *MemDep) { 146 if (!isa<PHINode>(BB->begin())) 147 return false; 148 149 while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 150 if (PN->getIncomingValue(0) != PN) 151 PN->replaceAllUsesWith(PN->getIncomingValue(0)); 152 else 153 PN->replaceAllUsesWith(PoisonValue::get(PN->getType())); 154 155 if (MemDep) 156 MemDep->removeInstruction(PN); // Memdep updates AA itself. 157 158 PN->eraseFromParent(); 159 } 160 return true; 161 } 162 163 bool llvm::DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI, 164 MemorySSAUpdater *MSSAU) { 165 // Recursively deleting a PHI may cause multiple PHIs to be deleted 166 // or RAUW'd undef, so use an array of WeakTrackingVH for the PHIs to delete. 167 SmallVector<WeakTrackingVH, 8> PHIs; 168 for (PHINode &PN : BB->phis()) 169 PHIs.push_back(&PN); 170 171 bool Changed = false; 172 for (unsigned i = 0, e = PHIs.size(); i != e; ++i) 173 if (PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i].operator Value*())) 174 Changed |= RecursivelyDeleteDeadPHINode(PN, TLI, MSSAU); 175 176 return Changed; 177 } 178 179 bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU, 180 LoopInfo *LI, MemorySSAUpdater *MSSAU, 181 MemoryDependenceResults *MemDep, 182 bool PredecessorWithTwoSuccessors) { 183 if (BB->hasAddressTaken()) 184 return false; 185 186 // Can't merge if there are multiple predecessors, or no predecessors. 187 BasicBlock *PredBB = BB->getUniquePredecessor(); 188 if (!PredBB) return false; 189 190 // Don't break self-loops. 191 if (PredBB == BB) return false; 192 193 // Don't break unwinding instructions or terminators with other side-effects. 194 Instruction *PTI = PredBB->getTerminator(); 195 if (PTI->isExceptionalTerminator() || PTI->mayHaveSideEffects()) 196 return false; 197 198 // Can't merge if there are multiple distinct successors. 199 if (!PredecessorWithTwoSuccessors && PredBB->getUniqueSuccessor() != BB) 200 return false; 201 202 // Currently only allow PredBB to have two predecessors, one being BB. 203 // Update BI to branch to BB's only successor instead of BB. 204 BranchInst *PredBB_BI; 205 BasicBlock *NewSucc = nullptr; 206 unsigned FallThruPath; 207 if (PredecessorWithTwoSuccessors) { 208 if (!(PredBB_BI = dyn_cast<BranchInst>(PTI))) 209 return false; 210 BranchInst *BB_JmpI = dyn_cast<BranchInst>(BB->getTerminator()); 211 if (!BB_JmpI || !BB_JmpI->isUnconditional()) 212 return false; 213 NewSucc = BB_JmpI->getSuccessor(0); 214 FallThruPath = PredBB_BI->getSuccessor(0) == BB ? 0 : 1; 215 } 216 217 // Can't merge if there is PHI loop. 218 for (PHINode &PN : BB->phis()) 219 if (llvm::is_contained(PN.incoming_values(), &PN)) 220 return false; 221 222 LLVM_DEBUG(dbgs() << "Merging: " << BB->getName() << " into " 223 << PredBB->getName() << "\n"); 224 225 // Begin by getting rid of unneeded PHIs. 226 SmallVector<AssertingVH<Value>, 4> IncomingValues; 227 if (isa<PHINode>(BB->front())) { 228 for (PHINode &PN : BB->phis()) 229 if (!isa<PHINode>(PN.getIncomingValue(0)) || 230 cast<PHINode>(PN.getIncomingValue(0))->getParent() != BB) 231 IncomingValues.push_back(PN.getIncomingValue(0)); 232 FoldSingleEntryPHINodes(BB, MemDep); 233 } 234 235 // DTU update: Collect all the edges that exit BB. 236 // These dominator edges will be redirected from Pred. 237 std::vector<DominatorTree::UpdateType> Updates; 238 if (DTU) { 239 // To avoid processing the same predecessor more than once. 240 SmallPtrSet<BasicBlock *, 8> SeenSuccs; 241 SmallPtrSet<BasicBlock *, 2> SuccsOfPredBB(succ_begin(PredBB), 242 succ_end(PredBB)); 243 Updates.reserve(Updates.size() + 2 * succ_size(BB) + 1); 244 // Add insert edges first. Experimentally, for the particular case of two 245 // blocks that can be merged, with a single successor and single predecessor 246 // respectively, it is beneficial to have all insert updates first. Deleting 247 // edges first may lead to unreachable blocks, followed by inserting edges 248 // making the blocks reachable again. Such DT updates lead to high compile 249 // times. We add inserts before deletes here to reduce compile time. 250 for (BasicBlock *SuccOfBB : successors(BB)) 251 // This successor of BB may already be a PredBB's successor. 252 if (!SuccsOfPredBB.contains(SuccOfBB)) 253 if (SeenSuccs.insert(SuccOfBB).second) 254 Updates.push_back({DominatorTree::Insert, PredBB, SuccOfBB}); 255 SeenSuccs.clear(); 256 for (BasicBlock *SuccOfBB : successors(BB)) 257 if (SeenSuccs.insert(SuccOfBB).second) 258 Updates.push_back({DominatorTree::Delete, BB, SuccOfBB}); 259 Updates.push_back({DominatorTree::Delete, PredBB, BB}); 260 } 261 262 Instruction *STI = BB->getTerminator(); 263 Instruction *Start = &*BB->begin(); 264 // If there's nothing to move, mark the starting instruction as the last 265 // instruction in the block. Terminator instruction is handled separately. 266 if (Start == STI) 267 Start = PTI; 268 269 // Move all definitions in the successor to the predecessor... 270 PredBB->splice(PTI->getIterator(), BB, BB->begin(), STI->getIterator()); 271 272 if (MSSAU) 273 MSSAU->moveAllAfterMergeBlocks(BB, PredBB, Start); 274 275 // Make all PHI nodes that referred to BB now refer to Pred as their 276 // source... 277 BB->replaceAllUsesWith(PredBB); 278 279 if (PredecessorWithTwoSuccessors) { 280 // Delete the unconditional branch from BB. 281 BB->back().eraseFromParent(); 282 283 // Update branch in the predecessor. 284 PredBB_BI->setSuccessor(FallThruPath, NewSucc); 285 } else { 286 // Delete the unconditional branch from the predecessor. 287 PredBB->back().eraseFromParent(); 288 289 // Move terminator instruction. 290 PredBB->splice(PredBB->end(), BB); 291 292 // Terminator may be a memory accessing instruction too. 293 if (MSSAU) 294 if (MemoryUseOrDef *MUD = cast_or_null<MemoryUseOrDef>( 295 MSSAU->getMemorySSA()->getMemoryAccess(PredBB->getTerminator()))) 296 MSSAU->moveToPlace(MUD, PredBB, MemorySSA::End); 297 } 298 // Add unreachable to now empty BB. 299 new UnreachableInst(BB->getContext(), BB); 300 301 // Inherit predecessors name if it exists. 302 if (!PredBB->hasName()) 303 PredBB->takeName(BB); 304 305 if (LI) 306 LI->removeBlock(BB); 307 308 if (MemDep) 309 MemDep->invalidateCachedPredecessors(); 310 311 if (DTU) 312 DTU->applyUpdates(Updates); 313 314 // Finally, erase the old block and update dominator info. 315 DeleteDeadBlock(BB, DTU); 316 317 return true; 318 } 319 320 bool llvm::MergeBlockSuccessorsIntoGivenBlocks( 321 SmallPtrSetImpl<BasicBlock *> &MergeBlocks, Loop *L, DomTreeUpdater *DTU, 322 LoopInfo *LI) { 323 assert(!MergeBlocks.empty() && "MergeBlocks should not be empty"); 324 325 bool BlocksHaveBeenMerged = false; 326 while (!MergeBlocks.empty()) { 327 BasicBlock *BB = *MergeBlocks.begin(); 328 BasicBlock *Dest = BB->getSingleSuccessor(); 329 if (Dest && (!L || L->contains(Dest))) { 330 BasicBlock *Fold = Dest->getUniquePredecessor(); 331 (void)Fold; 332 if (MergeBlockIntoPredecessor(Dest, DTU, LI)) { 333 assert(Fold == BB && 334 "Expecting BB to be unique predecessor of the Dest block"); 335 MergeBlocks.erase(Dest); 336 BlocksHaveBeenMerged = true; 337 } else 338 MergeBlocks.erase(BB); 339 } else 340 MergeBlocks.erase(BB); 341 } 342 return BlocksHaveBeenMerged; 343 } 344 345 /// Remove redundant instructions within sequences of consecutive dbg.value 346 /// instructions. This is done using a backward scan to keep the last dbg.value 347 /// describing a specific variable/fragment. 348 /// 349 /// BackwardScan strategy: 350 /// ---------------------- 351 /// Given a sequence of consecutive DbgValueInst like this 352 /// 353 /// dbg.value ..., "x", FragmentX1 (*) 354 /// dbg.value ..., "y", FragmentY1 355 /// dbg.value ..., "x", FragmentX2 356 /// dbg.value ..., "x", FragmentX1 (**) 357 /// 358 /// then the instruction marked with (*) can be removed (it is guaranteed to be 359 /// obsoleted by the instruction marked with (**) as the latter instruction is 360 /// describing the same variable using the same fragment info). 361 /// 362 /// Possible improvements: 363 /// - Check fully overlapping fragments and not only identical fragments. 364 /// - Support dbg.addr, dbg.declare. dbg.label, and possibly other meta 365 /// instructions being part of the sequence of consecutive instructions. 366 static bool removeRedundantDbgInstrsUsingBackwardScan(BasicBlock *BB) { 367 SmallVector<DbgValueInst *, 8> ToBeRemoved; 368 SmallDenseSet<DebugVariable> VariableSet; 369 for (auto &I : reverse(*BB)) { 370 if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(&I)) { 371 DebugVariable Key(DVI->getVariable(), 372 DVI->getExpression(), 373 DVI->getDebugLoc()->getInlinedAt()); 374 auto R = VariableSet.insert(Key); 375 // If the variable fragment hasn't been seen before then we don't want 376 // to remove this dbg intrinsic. 377 if (R.second) 378 continue; 379 380 if (auto *DAI = dyn_cast<DbgAssignIntrinsic>(DVI)) { 381 // Don't delete dbg.assign intrinsics that are linked to instructions. 382 if (!at::getAssignmentInsts(DAI).empty()) 383 continue; 384 // Unlinked dbg.assign intrinsics can be treated like dbg.values. 385 } 386 387 // If the same variable fragment is described more than once it is enough 388 // to keep the last one (i.e. the first found since we for reverse 389 // iteration). 390 ToBeRemoved.push_back(DVI); 391 continue; 392 } 393 // Sequence with consecutive dbg.value instrs ended. Clear the map to 394 // restart identifying redundant instructions if case we find another 395 // dbg.value sequence. 396 VariableSet.clear(); 397 } 398 399 for (auto &Instr : ToBeRemoved) 400 Instr->eraseFromParent(); 401 402 return !ToBeRemoved.empty(); 403 } 404 405 /// Remove redundant dbg.value instructions using a forward scan. This can 406 /// remove a dbg.value instruction that is redundant due to indicating that a 407 /// variable has the same value as already being indicated by an earlier 408 /// dbg.value. 409 /// 410 /// ForwardScan strategy: 411 /// --------------------- 412 /// Given two identical dbg.value instructions, separated by a block of 413 /// instructions that isn't describing the same variable, like this 414 /// 415 /// dbg.value X1, "x", FragmentX1 (**) 416 /// <block of instructions, none being "dbg.value ..., "x", ..."> 417 /// dbg.value X1, "x", FragmentX1 (*) 418 /// 419 /// then the instruction marked with (*) can be removed. Variable "x" is already 420 /// described as being mapped to the SSA value X1. 421 /// 422 /// Possible improvements: 423 /// - Keep track of non-overlapping fragments. 424 static bool removeRedundantDbgInstrsUsingForwardScan(BasicBlock *BB) { 425 SmallVector<DbgValueInst *, 8> ToBeRemoved; 426 DenseMap<DebugVariable, std::pair<SmallVector<Value *, 4>, DIExpression *>> 427 VariableMap; 428 for (auto &I : *BB) { 429 if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(&I)) { 430 DebugVariable Key(DVI->getVariable(), std::nullopt, 431 DVI->getDebugLoc()->getInlinedAt()); 432 auto VMI = VariableMap.find(Key); 433 auto *DAI = dyn_cast<DbgAssignIntrinsic>(DVI); 434 // A dbg.assign with no linked instructions can be treated like a 435 // dbg.value (i.e. can be deleted). 436 bool IsDbgValueKind = (!DAI || at::getAssignmentInsts(DAI).empty()); 437 438 // Update the map if we found a new value/expression describing the 439 // variable, or if the variable wasn't mapped already. 440 SmallVector<Value *, 4> Values(DVI->getValues()); 441 if (VMI == VariableMap.end() || VMI->second.first != Values || 442 VMI->second.second != DVI->getExpression()) { 443 // Use a sentinal value (nullptr) for the DIExpression when we see a 444 // linked dbg.assign so that the next debug intrinsic will never match 445 // it (i.e. always treat linked dbg.assigns as if they're unique). 446 if (IsDbgValueKind) 447 VariableMap[Key] = {Values, DVI->getExpression()}; 448 else 449 VariableMap[Key] = {Values, nullptr}; 450 continue; 451 } 452 453 // Don't delete dbg.assign intrinsics that are linked to instructions. 454 if (!IsDbgValueKind) 455 continue; 456 ToBeRemoved.push_back(DVI); 457 } 458 } 459 460 for (auto &Instr : ToBeRemoved) 461 Instr->eraseFromParent(); 462 463 return !ToBeRemoved.empty(); 464 } 465 466 /// Remove redundant undef dbg.assign intrinsic from an entry block using a 467 /// forward scan. 468 /// Strategy: 469 /// --------------------- 470 /// Scanning forward, delete dbg.assign intrinsics iff they are undef, not 471 /// linked to an intrinsic, and don't share an aggregate variable with a debug 472 /// intrinsic that didn't meet the criteria. In other words, undef dbg.assigns 473 /// that come before non-undef debug intrinsics for the variable are 474 /// deleted. Given: 475 /// 476 /// dbg.assign undef, "x", FragmentX1 (*) 477 /// <block of instructions, none being "dbg.value ..., "x", ..."> 478 /// dbg.value %V, "x", FragmentX2 479 /// <block of instructions, none being "dbg.value ..., "x", ..."> 480 /// dbg.assign undef, "x", FragmentX1 481 /// 482 /// then (only) the instruction marked with (*) can be removed. 483 /// Possible improvements: 484 /// - Keep track of non-overlapping fragments. 485 static bool remomveUndefDbgAssignsFromEntryBlock(BasicBlock *BB) { 486 assert(BB->isEntryBlock() && "expected entry block"); 487 SmallVector<DbgAssignIntrinsic *, 8> ToBeRemoved; 488 DenseSet<DebugVariable> SeenDefForAggregate; 489 // Returns the DebugVariable for DVI with no fragment info. 490 auto GetAggregateVariable = [](DbgValueInst *DVI) { 491 return DebugVariable(DVI->getVariable(), std::nullopt, 492 DVI->getDebugLoc()->getInlinedAt()); 493 }; 494 495 // Remove undef dbg.assign intrinsics that are encountered before 496 // any non-undef intrinsics from the entry block. 497 for (auto &I : *BB) { 498 DbgValueInst *DVI = dyn_cast<DbgValueInst>(&I); 499 if (!DVI) 500 continue; 501 auto *DAI = dyn_cast<DbgAssignIntrinsic>(DVI); 502 bool IsDbgValueKind = (!DAI || at::getAssignmentInsts(DAI).empty()); 503 DebugVariable Aggregate = GetAggregateVariable(DVI); 504 if (!SeenDefForAggregate.contains(Aggregate)) { 505 bool IsKill = DVI->isKillLocation() && IsDbgValueKind; 506 if (!IsKill) { 507 SeenDefForAggregate.insert(Aggregate); 508 } else if (DAI) { 509 ToBeRemoved.push_back(DAI); 510 } 511 } 512 } 513 514 for (DbgAssignIntrinsic *DAI : ToBeRemoved) 515 DAI->eraseFromParent(); 516 517 return !ToBeRemoved.empty(); 518 } 519 520 bool llvm::RemoveRedundantDbgInstrs(BasicBlock *BB) { 521 bool MadeChanges = false; 522 // By using the "backward scan" strategy before the "forward scan" strategy we 523 // can remove both dbg.value (2) and (3) in a situation like this: 524 // 525 // (1) dbg.value V1, "x", DIExpression() 526 // ... 527 // (2) dbg.value V2, "x", DIExpression() 528 // (3) dbg.value V1, "x", DIExpression() 529 // 530 // The backward scan will remove (2), it is made obsolete by (3). After 531 // getting (2) out of the way, the foward scan will remove (3) since "x" 532 // already is described as having the value V1 at (1). 533 MadeChanges |= removeRedundantDbgInstrsUsingBackwardScan(BB); 534 if (BB->isEntryBlock() && 535 isAssignmentTrackingEnabled(*BB->getParent()->getParent())) 536 MadeChanges |= remomveUndefDbgAssignsFromEntryBlock(BB); 537 MadeChanges |= removeRedundantDbgInstrsUsingForwardScan(BB); 538 539 if (MadeChanges) 540 LLVM_DEBUG(dbgs() << "Removed redundant dbg instrs from: " 541 << BB->getName() << "\n"); 542 return MadeChanges; 543 } 544 545 void llvm::ReplaceInstWithValue(BasicBlock::iterator &BI, Value *V) { 546 Instruction &I = *BI; 547 // Replaces all of the uses of the instruction with uses of the value 548 I.replaceAllUsesWith(V); 549 550 // Make sure to propagate a name if there is one already. 551 if (I.hasName() && !V->hasName()) 552 V->takeName(&I); 553 554 // Delete the unnecessary instruction now... 555 BI = BI->eraseFromParent(); 556 } 557 558 void llvm::ReplaceInstWithInst(BasicBlock *BB, BasicBlock::iterator &BI, 559 Instruction *I) { 560 assert(I->getParent() == nullptr && 561 "ReplaceInstWithInst: Instruction already inserted into basic block!"); 562 563 // Copy debug location to newly added instruction, if it wasn't already set 564 // by the caller. 565 if (!I->getDebugLoc()) 566 I->setDebugLoc(BI->getDebugLoc()); 567 568 // Insert the new instruction into the basic block... 569 BasicBlock::iterator New = I->insertInto(BB, BI); 570 571 // Replace all uses of the old instruction, and delete it. 572 ReplaceInstWithValue(BI, I); 573 574 // Move BI back to point to the newly inserted instruction 575 BI = New; 576 } 577 578 bool llvm::IsBlockFollowedByDeoptOrUnreachable(const BasicBlock *BB) { 579 // Remember visited blocks to avoid infinite loop 580 SmallPtrSet<const BasicBlock *, 8> VisitedBlocks; 581 unsigned Depth = 0; 582 while (BB && Depth++ < MaxDeoptOrUnreachableSuccessorCheckDepth && 583 VisitedBlocks.insert(BB).second) { 584 if (BB->getTerminatingDeoptimizeCall() || 585 isa<UnreachableInst>(BB->getTerminator())) 586 return true; 587 BB = BB->getUniqueSuccessor(); 588 } 589 return false; 590 } 591 592 void llvm::ReplaceInstWithInst(Instruction *From, Instruction *To) { 593 BasicBlock::iterator BI(From); 594 ReplaceInstWithInst(From->getParent(), BI, To); 595 } 596 597 BasicBlock *llvm::SplitEdge(BasicBlock *BB, BasicBlock *Succ, DominatorTree *DT, 598 LoopInfo *LI, MemorySSAUpdater *MSSAU, 599 const Twine &BBName) { 600 unsigned SuccNum = GetSuccessorNumber(BB, Succ); 601 602 Instruction *LatchTerm = BB->getTerminator(); 603 604 CriticalEdgeSplittingOptions Options = 605 CriticalEdgeSplittingOptions(DT, LI, MSSAU).setPreserveLCSSA(); 606 607 if ((isCriticalEdge(LatchTerm, SuccNum, Options.MergeIdenticalEdges))) { 608 // If it is a critical edge, and the succesor is an exception block, handle 609 // the split edge logic in this specific function 610 if (Succ->isEHPad()) 611 return ehAwareSplitEdge(BB, Succ, nullptr, nullptr, Options, BBName); 612 613 // If this is a critical edge, let SplitKnownCriticalEdge do it. 614 return SplitKnownCriticalEdge(LatchTerm, SuccNum, Options, BBName); 615 } 616 617 // If the edge isn't critical, then BB has a single successor or Succ has a 618 // single pred. Split the block. 619 if (BasicBlock *SP = Succ->getSinglePredecessor()) { 620 // If the successor only has a single pred, split the top of the successor 621 // block. 622 assert(SP == BB && "CFG broken"); 623 SP = nullptr; 624 return SplitBlock(Succ, &Succ->front(), DT, LI, MSSAU, BBName, 625 /*Before=*/true); 626 } 627 628 // Otherwise, if BB has a single successor, split it at the bottom of the 629 // block. 630 assert(BB->getTerminator()->getNumSuccessors() == 1 && 631 "Should have a single succ!"); 632 return SplitBlock(BB, BB->getTerminator(), DT, LI, MSSAU, BBName); 633 } 634 635 void llvm::setUnwindEdgeTo(Instruction *TI, BasicBlock *Succ) { 636 if (auto *II = dyn_cast<InvokeInst>(TI)) 637 II->setUnwindDest(Succ); 638 else if (auto *CS = dyn_cast<CatchSwitchInst>(TI)) 639 CS->setUnwindDest(Succ); 640 else if (auto *CR = dyn_cast<CleanupReturnInst>(TI)) 641 CR->setUnwindDest(Succ); 642 else 643 llvm_unreachable("unexpected terminator instruction"); 644 } 645 646 void llvm::updatePhiNodes(BasicBlock *DestBB, BasicBlock *OldPred, 647 BasicBlock *NewPred, PHINode *Until) { 648 int BBIdx = 0; 649 for (PHINode &PN : DestBB->phis()) { 650 // We manually update the LandingPadReplacement PHINode and it is the last 651 // PHI Node. So, if we find it, we are done. 652 if (Until == &PN) 653 break; 654 655 // Reuse the previous value of BBIdx if it lines up. In cases where we 656 // have multiple phi nodes with *lots* of predecessors, this is a speed 657 // win because we don't have to scan the PHI looking for TIBB. This 658 // happens because the BB list of PHI nodes are usually in the same 659 // order. 660 if (PN.getIncomingBlock(BBIdx) != OldPred) 661 BBIdx = PN.getBasicBlockIndex(OldPred); 662 663 assert(BBIdx != -1 && "Invalid PHI Index!"); 664 PN.setIncomingBlock(BBIdx, NewPred); 665 } 666 } 667 668 BasicBlock *llvm::ehAwareSplitEdge(BasicBlock *BB, BasicBlock *Succ, 669 LandingPadInst *OriginalPad, 670 PHINode *LandingPadReplacement, 671 const CriticalEdgeSplittingOptions &Options, 672 const Twine &BBName) { 673 674 auto *PadInst = Succ->getFirstNonPHI(); 675 if (!LandingPadReplacement && !PadInst->isEHPad()) 676 return SplitEdge(BB, Succ, Options.DT, Options.LI, Options.MSSAU, BBName); 677 678 auto *LI = Options.LI; 679 SmallVector<BasicBlock *, 4> LoopPreds; 680 // Check if extra modifications will be required to preserve loop-simplify 681 // form after splitting. If it would require splitting blocks with IndirectBr 682 // terminators, bail out if preserving loop-simplify form is requested. 683 if (Options.PreserveLoopSimplify && LI) { 684 if (Loop *BBLoop = LI->getLoopFor(BB)) { 685 686 // The only way that we can break LoopSimplify form by splitting a 687 // critical edge is when there exists some edge from BBLoop to Succ *and* 688 // the only edge into Succ from outside of BBLoop is that of NewBB after 689 // the split. If the first isn't true, then LoopSimplify still holds, 690 // NewBB is the new exit block and it has no non-loop predecessors. If the 691 // second isn't true, then Succ was not in LoopSimplify form prior to 692 // the split as it had a non-loop predecessor. In both of these cases, 693 // the predecessor must be directly in BBLoop, not in a subloop, or again 694 // LoopSimplify doesn't hold. 695 for (BasicBlock *P : predecessors(Succ)) { 696 if (P == BB) 697 continue; // The new block is known. 698 if (LI->getLoopFor(P) != BBLoop) { 699 // Loop is not in LoopSimplify form, no need to re simplify after 700 // splitting edge. 701 LoopPreds.clear(); 702 break; 703 } 704 LoopPreds.push_back(P); 705 } 706 // Loop-simplify form can be preserved, if we can split all in-loop 707 // predecessors. 708 if (any_of(LoopPreds, [](BasicBlock *Pred) { 709 return isa<IndirectBrInst>(Pred->getTerminator()); 710 })) { 711 return nullptr; 712 } 713 } 714 } 715 716 auto *NewBB = 717 BasicBlock::Create(BB->getContext(), BBName, BB->getParent(), Succ); 718 setUnwindEdgeTo(BB->getTerminator(), NewBB); 719 updatePhiNodes(Succ, BB, NewBB, LandingPadReplacement); 720 721 if (LandingPadReplacement) { 722 auto *NewLP = OriginalPad->clone(); 723 auto *Terminator = BranchInst::Create(Succ, NewBB); 724 NewLP->insertBefore(Terminator); 725 LandingPadReplacement->addIncoming(NewLP, NewBB); 726 } else { 727 Value *ParentPad = nullptr; 728 if (auto *FuncletPad = dyn_cast<FuncletPadInst>(PadInst)) 729 ParentPad = FuncletPad->getParentPad(); 730 else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(PadInst)) 731 ParentPad = CatchSwitch->getParentPad(); 732 else if (auto *CleanupPad = dyn_cast<CleanupPadInst>(PadInst)) 733 ParentPad = CleanupPad->getParentPad(); 734 else if (auto *LandingPad = dyn_cast<LandingPadInst>(PadInst)) 735 ParentPad = LandingPad->getParent(); 736 else 737 llvm_unreachable("handling for other EHPads not implemented yet"); 738 739 auto *NewCleanupPad = CleanupPadInst::Create(ParentPad, {}, BBName, NewBB); 740 CleanupReturnInst::Create(NewCleanupPad, Succ, NewBB); 741 } 742 743 auto *DT = Options.DT; 744 auto *MSSAU = Options.MSSAU; 745 if (!DT && !LI) 746 return NewBB; 747 748 if (DT) { 749 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy); 750 SmallVector<DominatorTree::UpdateType, 3> Updates; 751 752 Updates.push_back({DominatorTree::Insert, BB, NewBB}); 753 Updates.push_back({DominatorTree::Insert, NewBB, Succ}); 754 Updates.push_back({DominatorTree::Delete, BB, Succ}); 755 756 DTU.applyUpdates(Updates); 757 DTU.flush(); 758 759 if (MSSAU) { 760 MSSAU->applyUpdates(Updates, *DT); 761 if (VerifyMemorySSA) 762 MSSAU->getMemorySSA()->verifyMemorySSA(); 763 } 764 } 765 766 if (LI) { 767 if (Loop *BBLoop = LI->getLoopFor(BB)) { 768 // If one or the other blocks were not in a loop, the new block is not 769 // either, and thus LI doesn't need to be updated. 770 if (Loop *SuccLoop = LI->getLoopFor(Succ)) { 771 if (BBLoop == SuccLoop) { 772 // Both in the same loop, the NewBB joins loop. 773 SuccLoop->addBasicBlockToLoop(NewBB, *LI); 774 } else if (BBLoop->contains(SuccLoop)) { 775 // Edge from an outer loop to an inner loop. Add to the outer loop. 776 BBLoop->addBasicBlockToLoop(NewBB, *LI); 777 } else if (SuccLoop->contains(BBLoop)) { 778 // Edge from an inner loop to an outer loop. Add to the outer loop. 779 SuccLoop->addBasicBlockToLoop(NewBB, *LI); 780 } else { 781 // Edge from two loops with no containment relation. Because these 782 // are natural loops, we know that the destination block must be the 783 // header of its loop (adding a branch into a loop elsewhere would 784 // create an irreducible loop). 785 assert(SuccLoop->getHeader() == Succ && 786 "Should not create irreducible loops!"); 787 if (Loop *P = SuccLoop->getParentLoop()) 788 P->addBasicBlockToLoop(NewBB, *LI); 789 } 790 } 791 792 // If BB is in a loop and Succ is outside of that loop, we may need to 793 // update LoopSimplify form and LCSSA form. 794 if (!BBLoop->contains(Succ)) { 795 assert(!BBLoop->contains(NewBB) && 796 "Split point for loop exit is contained in loop!"); 797 798 // Update LCSSA form in the newly created exit block. 799 if (Options.PreserveLCSSA) { 800 createPHIsForSplitLoopExit(BB, NewBB, Succ); 801 } 802 803 if (!LoopPreds.empty()) { 804 BasicBlock *NewExitBB = SplitBlockPredecessors( 805 Succ, LoopPreds, "split", DT, LI, MSSAU, Options.PreserveLCSSA); 806 if (Options.PreserveLCSSA) 807 createPHIsForSplitLoopExit(LoopPreds, NewExitBB, Succ); 808 } 809 } 810 } 811 } 812 813 return NewBB; 814 } 815 816 void llvm::createPHIsForSplitLoopExit(ArrayRef<BasicBlock *> Preds, 817 BasicBlock *SplitBB, BasicBlock *DestBB) { 818 // SplitBB shouldn't have anything non-trivial in it yet. 819 assert((SplitBB->getFirstNonPHI() == SplitBB->getTerminator() || 820 SplitBB->isLandingPad()) && 821 "SplitBB has non-PHI nodes!"); 822 823 // For each PHI in the destination block. 824 for (PHINode &PN : DestBB->phis()) { 825 int Idx = PN.getBasicBlockIndex(SplitBB); 826 assert(Idx >= 0 && "Invalid Block Index"); 827 Value *V = PN.getIncomingValue(Idx); 828 829 // If the input is a PHI which already satisfies LCSSA, don't create 830 // a new one. 831 if (const PHINode *VP = dyn_cast<PHINode>(V)) 832 if (VP->getParent() == SplitBB) 833 continue; 834 835 // Otherwise a new PHI is needed. Create one and populate it. 836 PHINode *NewPN = PHINode::Create( 837 PN.getType(), Preds.size(), "split", 838 SplitBB->isLandingPad() ? &SplitBB->front() : SplitBB->getTerminator()); 839 for (BasicBlock *BB : Preds) 840 NewPN->addIncoming(V, BB); 841 842 // Update the original PHI. 843 PN.setIncomingValue(Idx, NewPN); 844 } 845 } 846 847 unsigned 848 llvm::SplitAllCriticalEdges(Function &F, 849 const CriticalEdgeSplittingOptions &Options) { 850 unsigned NumBroken = 0; 851 for (BasicBlock &BB : F) { 852 Instruction *TI = BB.getTerminator(); 853 if (TI->getNumSuccessors() > 1 && !isa<IndirectBrInst>(TI)) 854 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 855 if (SplitCriticalEdge(TI, i, Options)) 856 ++NumBroken; 857 } 858 return NumBroken; 859 } 860 861 static BasicBlock *SplitBlockImpl(BasicBlock *Old, Instruction *SplitPt, 862 DomTreeUpdater *DTU, DominatorTree *DT, 863 LoopInfo *LI, MemorySSAUpdater *MSSAU, 864 const Twine &BBName, bool Before) { 865 if (Before) { 866 DomTreeUpdater LocalDTU(DT, DomTreeUpdater::UpdateStrategy::Lazy); 867 return splitBlockBefore(Old, SplitPt, 868 DTU ? DTU : (DT ? &LocalDTU : nullptr), LI, MSSAU, 869 BBName); 870 } 871 BasicBlock::iterator SplitIt = SplitPt->getIterator(); 872 while (isa<PHINode>(SplitIt) || SplitIt->isEHPad()) { 873 ++SplitIt; 874 assert(SplitIt != SplitPt->getParent()->end()); 875 } 876 std::string Name = BBName.str(); 877 BasicBlock *New = Old->splitBasicBlock( 878 SplitIt, Name.empty() ? Old->getName() + ".split" : Name); 879 880 // The new block lives in whichever loop the old one did. This preserves 881 // LCSSA as well, because we force the split point to be after any PHI nodes. 882 if (LI) 883 if (Loop *L = LI->getLoopFor(Old)) 884 L->addBasicBlockToLoop(New, *LI); 885 886 if (DTU) { 887 SmallVector<DominatorTree::UpdateType, 8> Updates; 888 // Old dominates New. New node dominates all other nodes dominated by Old. 889 SmallPtrSet<BasicBlock *, 8> UniqueSuccessorsOfOld; 890 Updates.push_back({DominatorTree::Insert, Old, New}); 891 Updates.reserve(Updates.size() + 2 * succ_size(New)); 892 for (BasicBlock *SuccessorOfOld : successors(New)) 893 if (UniqueSuccessorsOfOld.insert(SuccessorOfOld).second) { 894 Updates.push_back({DominatorTree::Insert, New, SuccessorOfOld}); 895 Updates.push_back({DominatorTree::Delete, Old, SuccessorOfOld}); 896 } 897 898 DTU->applyUpdates(Updates); 899 } else if (DT) 900 // Old dominates New. New node dominates all other nodes dominated by Old. 901 if (DomTreeNode *OldNode = DT->getNode(Old)) { 902 std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end()); 903 904 DomTreeNode *NewNode = DT->addNewBlock(New, Old); 905 for (DomTreeNode *I : Children) 906 DT->changeImmediateDominator(I, NewNode); 907 } 908 909 // Move MemoryAccesses still tracked in Old, but part of New now. 910 // Update accesses in successor blocks accordingly. 911 if (MSSAU) 912 MSSAU->moveAllAfterSpliceBlocks(Old, New, &*(New->begin())); 913 914 return New; 915 } 916 917 BasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt, 918 DominatorTree *DT, LoopInfo *LI, 919 MemorySSAUpdater *MSSAU, const Twine &BBName, 920 bool Before) { 921 return SplitBlockImpl(Old, SplitPt, /*DTU=*/nullptr, DT, LI, MSSAU, BBName, 922 Before); 923 } 924 BasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt, 925 DomTreeUpdater *DTU, LoopInfo *LI, 926 MemorySSAUpdater *MSSAU, const Twine &BBName, 927 bool Before) { 928 return SplitBlockImpl(Old, SplitPt, DTU, /*DT=*/nullptr, LI, MSSAU, BBName, 929 Before); 930 } 931 932 BasicBlock *llvm::splitBlockBefore(BasicBlock *Old, Instruction *SplitPt, 933 DomTreeUpdater *DTU, LoopInfo *LI, 934 MemorySSAUpdater *MSSAU, 935 const Twine &BBName) { 936 937 BasicBlock::iterator SplitIt = SplitPt->getIterator(); 938 while (isa<PHINode>(SplitIt) || SplitIt->isEHPad()) 939 ++SplitIt; 940 std::string Name = BBName.str(); 941 BasicBlock *New = Old->splitBasicBlock( 942 SplitIt, Name.empty() ? Old->getName() + ".split" : Name, 943 /* Before=*/true); 944 945 // The new block lives in whichever loop the old one did. This preserves 946 // LCSSA as well, because we force the split point to be after any PHI nodes. 947 if (LI) 948 if (Loop *L = LI->getLoopFor(Old)) 949 L->addBasicBlockToLoop(New, *LI); 950 951 if (DTU) { 952 SmallVector<DominatorTree::UpdateType, 8> DTUpdates; 953 // New dominates Old. The predecessor nodes of the Old node dominate 954 // New node. 955 SmallPtrSet<BasicBlock *, 8> UniquePredecessorsOfOld; 956 DTUpdates.push_back({DominatorTree::Insert, New, Old}); 957 DTUpdates.reserve(DTUpdates.size() + 2 * pred_size(New)); 958 for (BasicBlock *PredecessorOfOld : predecessors(New)) 959 if (UniquePredecessorsOfOld.insert(PredecessorOfOld).second) { 960 DTUpdates.push_back({DominatorTree::Insert, PredecessorOfOld, New}); 961 DTUpdates.push_back({DominatorTree::Delete, PredecessorOfOld, Old}); 962 } 963 964 DTU->applyUpdates(DTUpdates); 965 966 // Move MemoryAccesses still tracked in Old, but part of New now. 967 // Update accesses in successor blocks accordingly. 968 if (MSSAU) { 969 MSSAU->applyUpdates(DTUpdates, DTU->getDomTree()); 970 if (VerifyMemorySSA) 971 MSSAU->getMemorySSA()->verifyMemorySSA(); 972 } 973 } 974 return New; 975 } 976 977 /// Update DominatorTree, LoopInfo, and LCCSA analysis information. 978 static void UpdateAnalysisInformation(BasicBlock *OldBB, BasicBlock *NewBB, 979 ArrayRef<BasicBlock *> Preds, 980 DomTreeUpdater *DTU, DominatorTree *DT, 981 LoopInfo *LI, MemorySSAUpdater *MSSAU, 982 bool PreserveLCSSA, bool &HasLoopExit) { 983 // Update dominator tree if available. 984 if (DTU) { 985 // Recalculation of DomTree is needed when updating a forward DomTree and 986 // the Entry BB is replaced. 987 if (NewBB->isEntryBlock() && DTU->hasDomTree()) { 988 // The entry block was removed and there is no external interface for 989 // the dominator tree to be notified of this change. In this corner-case 990 // we recalculate the entire tree. 991 DTU->recalculate(*NewBB->getParent()); 992 } else { 993 // Split block expects NewBB to have a non-empty set of predecessors. 994 SmallVector<DominatorTree::UpdateType, 8> Updates; 995 SmallPtrSet<BasicBlock *, 8> UniquePreds; 996 Updates.push_back({DominatorTree::Insert, NewBB, OldBB}); 997 Updates.reserve(Updates.size() + 2 * Preds.size()); 998 for (auto *Pred : Preds) 999 if (UniquePreds.insert(Pred).second) { 1000 Updates.push_back({DominatorTree::Insert, Pred, NewBB}); 1001 Updates.push_back({DominatorTree::Delete, Pred, OldBB}); 1002 } 1003 DTU->applyUpdates(Updates); 1004 } 1005 } else if (DT) { 1006 if (OldBB == DT->getRootNode()->getBlock()) { 1007 assert(NewBB->isEntryBlock()); 1008 DT->setNewRoot(NewBB); 1009 } else { 1010 // Split block expects NewBB to have a non-empty set of predecessors. 1011 DT->splitBlock(NewBB); 1012 } 1013 } 1014 1015 // Update MemoryPhis after split if MemorySSA is available 1016 if (MSSAU) 1017 MSSAU->wireOldPredecessorsToNewImmediatePredecessor(OldBB, NewBB, Preds); 1018 1019 // The rest of the logic is only relevant for updating the loop structures. 1020 if (!LI) 1021 return; 1022 1023 if (DTU && DTU->hasDomTree()) 1024 DT = &DTU->getDomTree(); 1025 assert(DT && "DT should be available to update LoopInfo!"); 1026 Loop *L = LI->getLoopFor(OldBB); 1027 1028 // If we need to preserve loop analyses, collect some information about how 1029 // this split will affect loops. 1030 bool IsLoopEntry = !!L; 1031 bool SplitMakesNewLoopHeader = false; 1032 for (BasicBlock *Pred : Preds) { 1033 // Preds that are not reachable from entry should not be used to identify if 1034 // OldBB is a loop entry or if SplitMakesNewLoopHeader. Unreachable blocks 1035 // are not within any loops, so we incorrectly mark SplitMakesNewLoopHeader 1036 // as true and make the NewBB the header of some loop. This breaks LI. 1037 if (!DT->isReachableFromEntry(Pred)) 1038 continue; 1039 // If we need to preserve LCSSA, determine if any of the preds is a loop 1040 // exit. 1041 if (PreserveLCSSA) 1042 if (Loop *PL = LI->getLoopFor(Pred)) 1043 if (!PL->contains(OldBB)) 1044 HasLoopExit = true; 1045 1046 // If we need to preserve LoopInfo, note whether any of the preds crosses 1047 // an interesting loop boundary. 1048 if (!L) 1049 continue; 1050 if (L->contains(Pred)) 1051 IsLoopEntry = false; 1052 else 1053 SplitMakesNewLoopHeader = true; 1054 } 1055 1056 // Unless we have a loop for OldBB, nothing else to do here. 1057 if (!L) 1058 return; 1059 1060 if (IsLoopEntry) { 1061 // Add the new block to the nearest enclosing loop (and not an adjacent 1062 // loop). To find this, examine each of the predecessors and determine which 1063 // loops enclose them, and select the most-nested loop which contains the 1064 // loop containing the block being split. 1065 Loop *InnermostPredLoop = nullptr; 1066 for (BasicBlock *Pred : Preds) { 1067 if (Loop *PredLoop = LI->getLoopFor(Pred)) { 1068 // Seek a loop which actually contains the block being split (to avoid 1069 // adjacent loops). 1070 while (PredLoop && !PredLoop->contains(OldBB)) 1071 PredLoop = PredLoop->getParentLoop(); 1072 1073 // Select the most-nested of these loops which contains the block. 1074 if (PredLoop && PredLoop->contains(OldBB) && 1075 (!InnermostPredLoop || 1076 InnermostPredLoop->getLoopDepth() < PredLoop->getLoopDepth())) 1077 InnermostPredLoop = PredLoop; 1078 } 1079 } 1080 1081 if (InnermostPredLoop) 1082 InnermostPredLoop->addBasicBlockToLoop(NewBB, *LI); 1083 } else { 1084 L->addBasicBlockToLoop(NewBB, *LI); 1085 if (SplitMakesNewLoopHeader) 1086 L->moveToHeader(NewBB); 1087 } 1088 } 1089 1090 /// Update the PHI nodes in OrigBB to include the values coming from NewBB. 1091 /// This also updates AliasAnalysis, if available. 1092 static void UpdatePHINodes(BasicBlock *OrigBB, BasicBlock *NewBB, 1093 ArrayRef<BasicBlock *> Preds, BranchInst *BI, 1094 bool HasLoopExit) { 1095 // Otherwise, create a new PHI node in NewBB for each PHI node in OrigBB. 1096 SmallPtrSet<BasicBlock *, 16> PredSet(Preds.begin(), Preds.end()); 1097 for (BasicBlock::iterator I = OrigBB->begin(); isa<PHINode>(I); ) { 1098 PHINode *PN = cast<PHINode>(I++); 1099 1100 // Check to see if all of the values coming in are the same. If so, we 1101 // don't need to create a new PHI node, unless it's needed for LCSSA. 1102 Value *InVal = nullptr; 1103 if (!HasLoopExit) { 1104 InVal = PN->getIncomingValueForBlock(Preds[0]); 1105 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 1106 if (!PredSet.count(PN->getIncomingBlock(i))) 1107 continue; 1108 if (!InVal) 1109 InVal = PN->getIncomingValue(i); 1110 else if (InVal != PN->getIncomingValue(i)) { 1111 InVal = nullptr; 1112 break; 1113 } 1114 } 1115 } 1116 1117 if (InVal) { 1118 // If all incoming values for the new PHI would be the same, just don't 1119 // make a new PHI. Instead, just remove the incoming values from the old 1120 // PHI. 1121 1122 // NOTE! This loop walks backwards for a reason! First off, this minimizes 1123 // the cost of removal if we end up removing a large number of values, and 1124 // second off, this ensures that the indices for the incoming values 1125 // aren't invalidated when we remove one. 1126 for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i) 1127 if (PredSet.count(PN->getIncomingBlock(i))) 1128 PN->removeIncomingValue(i, false); 1129 1130 // Add an incoming value to the PHI node in the loop for the preheader 1131 // edge. 1132 PN->addIncoming(InVal, NewBB); 1133 continue; 1134 } 1135 1136 // If the values coming into the block are not the same, we need a new 1137 // PHI. 1138 // Create the new PHI node, insert it into NewBB at the end of the block 1139 PHINode *NewPHI = 1140 PHINode::Create(PN->getType(), Preds.size(), PN->getName() + ".ph", BI); 1141 1142 // NOTE! This loop walks backwards for a reason! First off, this minimizes 1143 // the cost of removal if we end up removing a large number of values, and 1144 // second off, this ensures that the indices for the incoming values aren't 1145 // invalidated when we remove one. 1146 for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i) { 1147 BasicBlock *IncomingBB = PN->getIncomingBlock(i); 1148 if (PredSet.count(IncomingBB)) { 1149 Value *V = PN->removeIncomingValue(i, false); 1150 NewPHI->addIncoming(V, IncomingBB); 1151 } 1152 } 1153 1154 PN->addIncoming(NewPHI, NewBB); 1155 } 1156 } 1157 1158 static void SplitLandingPadPredecessorsImpl( 1159 BasicBlock *OrigBB, ArrayRef<BasicBlock *> Preds, const char *Suffix1, 1160 const char *Suffix2, SmallVectorImpl<BasicBlock *> &NewBBs, 1161 DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, 1162 MemorySSAUpdater *MSSAU, bool PreserveLCSSA); 1163 1164 static BasicBlock * 1165 SplitBlockPredecessorsImpl(BasicBlock *BB, ArrayRef<BasicBlock *> Preds, 1166 const char *Suffix, DomTreeUpdater *DTU, 1167 DominatorTree *DT, LoopInfo *LI, 1168 MemorySSAUpdater *MSSAU, bool PreserveLCSSA) { 1169 // Do not attempt to split that which cannot be split. 1170 if (!BB->canSplitPredecessors()) 1171 return nullptr; 1172 1173 // For the landingpads we need to act a bit differently. 1174 // Delegate this work to the SplitLandingPadPredecessors. 1175 if (BB->isLandingPad()) { 1176 SmallVector<BasicBlock*, 2> NewBBs; 1177 std::string NewName = std::string(Suffix) + ".split-lp"; 1178 1179 SplitLandingPadPredecessorsImpl(BB, Preds, Suffix, NewName.c_str(), NewBBs, 1180 DTU, DT, LI, MSSAU, PreserveLCSSA); 1181 return NewBBs[0]; 1182 } 1183 1184 // Create new basic block, insert right before the original block. 1185 BasicBlock *NewBB = BasicBlock::Create( 1186 BB->getContext(), BB->getName() + Suffix, BB->getParent(), BB); 1187 1188 // The new block unconditionally branches to the old block. 1189 BranchInst *BI = BranchInst::Create(BB, NewBB); 1190 1191 Loop *L = nullptr; 1192 BasicBlock *OldLatch = nullptr; 1193 // Splitting the predecessors of a loop header creates a preheader block. 1194 if (LI && LI->isLoopHeader(BB)) { 1195 L = LI->getLoopFor(BB); 1196 // Using the loop start line number prevents debuggers stepping into the 1197 // loop body for this instruction. 1198 BI->setDebugLoc(L->getStartLoc()); 1199 1200 // If BB is the header of the Loop, it is possible that the loop is 1201 // modified, such that the current latch does not remain the latch of the 1202 // loop. If that is the case, the loop metadata from the current latch needs 1203 // to be applied to the new latch. 1204 OldLatch = L->getLoopLatch(); 1205 } else 1206 BI->setDebugLoc(BB->getFirstNonPHIOrDbg()->getDebugLoc()); 1207 1208 // Move the edges from Preds to point to NewBB instead of BB. 1209 for (BasicBlock *Pred : Preds) { 1210 // This is slightly more strict than necessary; the minimum requirement 1211 // is that there be no more than one indirectbr branching to BB. And 1212 // all BlockAddress uses would need to be updated. 1213 assert(!isa<IndirectBrInst>(Pred->getTerminator()) && 1214 "Cannot split an edge from an IndirectBrInst"); 1215 Pred->getTerminator()->replaceSuccessorWith(BB, NewBB); 1216 } 1217 1218 // Insert a new PHI node into NewBB for every PHI node in BB and that new PHI 1219 // node becomes an incoming value for BB's phi node. However, if the Preds 1220 // list is empty, we need to insert dummy entries into the PHI nodes in BB to 1221 // account for the newly created predecessor. 1222 if (Preds.empty()) { 1223 // Insert dummy values as the incoming value. 1224 for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I) 1225 cast<PHINode>(I)->addIncoming(PoisonValue::get(I->getType()), NewBB); 1226 } 1227 1228 // Update DominatorTree, LoopInfo, and LCCSA analysis information. 1229 bool HasLoopExit = false; 1230 UpdateAnalysisInformation(BB, NewBB, Preds, DTU, DT, LI, MSSAU, PreserveLCSSA, 1231 HasLoopExit); 1232 1233 if (!Preds.empty()) { 1234 // Update the PHI nodes in BB with the values coming from NewBB. 1235 UpdatePHINodes(BB, NewBB, Preds, BI, HasLoopExit); 1236 } 1237 1238 if (OldLatch) { 1239 BasicBlock *NewLatch = L->getLoopLatch(); 1240 if (NewLatch != OldLatch) { 1241 MDNode *MD = OldLatch->getTerminator()->getMetadata("llvm.loop"); 1242 NewLatch->getTerminator()->setMetadata("llvm.loop", MD); 1243 // It's still possible that OldLatch is the latch of another inner loop, 1244 // in which case we do not remove the metadata. 1245 Loop *IL = LI->getLoopFor(OldLatch); 1246 if (IL && IL->getLoopLatch() != OldLatch) 1247 OldLatch->getTerminator()->setMetadata("llvm.loop", nullptr); 1248 } 1249 } 1250 1251 return NewBB; 1252 } 1253 1254 BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB, 1255 ArrayRef<BasicBlock *> Preds, 1256 const char *Suffix, DominatorTree *DT, 1257 LoopInfo *LI, MemorySSAUpdater *MSSAU, 1258 bool PreserveLCSSA) { 1259 return SplitBlockPredecessorsImpl(BB, Preds, Suffix, /*DTU=*/nullptr, DT, LI, 1260 MSSAU, PreserveLCSSA); 1261 } 1262 BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB, 1263 ArrayRef<BasicBlock *> Preds, 1264 const char *Suffix, 1265 DomTreeUpdater *DTU, LoopInfo *LI, 1266 MemorySSAUpdater *MSSAU, 1267 bool PreserveLCSSA) { 1268 return SplitBlockPredecessorsImpl(BB, Preds, Suffix, DTU, 1269 /*DT=*/nullptr, LI, MSSAU, PreserveLCSSA); 1270 } 1271 1272 static void SplitLandingPadPredecessorsImpl( 1273 BasicBlock *OrigBB, ArrayRef<BasicBlock *> Preds, const char *Suffix1, 1274 const char *Suffix2, SmallVectorImpl<BasicBlock *> &NewBBs, 1275 DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, 1276 MemorySSAUpdater *MSSAU, bool PreserveLCSSA) { 1277 assert(OrigBB->isLandingPad() && "Trying to split a non-landing pad!"); 1278 1279 // Create a new basic block for OrigBB's predecessors listed in Preds. Insert 1280 // it right before the original block. 1281 BasicBlock *NewBB1 = BasicBlock::Create(OrigBB->getContext(), 1282 OrigBB->getName() + Suffix1, 1283 OrigBB->getParent(), OrigBB); 1284 NewBBs.push_back(NewBB1); 1285 1286 // The new block unconditionally branches to the old block. 1287 BranchInst *BI1 = BranchInst::Create(OrigBB, NewBB1); 1288 BI1->setDebugLoc(OrigBB->getFirstNonPHI()->getDebugLoc()); 1289 1290 // Move the edges from Preds to point to NewBB1 instead of OrigBB. 1291 for (BasicBlock *Pred : Preds) { 1292 // This is slightly more strict than necessary; the minimum requirement 1293 // is that there be no more than one indirectbr branching to BB. And 1294 // all BlockAddress uses would need to be updated. 1295 assert(!isa<IndirectBrInst>(Pred->getTerminator()) && 1296 "Cannot split an edge from an IndirectBrInst"); 1297 Pred->getTerminator()->replaceUsesOfWith(OrigBB, NewBB1); 1298 } 1299 1300 bool HasLoopExit = false; 1301 UpdateAnalysisInformation(OrigBB, NewBB1, Preds, DTU, DT, LI, MSSAU, 1302 PreserveLCSSA, HasLoopExit); 1303 1304 // Update the PHI nodes in OrigBB with the values coming from NewBB1. 1305 UpdatePHINodes(OrigBB, NewBB1, Preds, BI1, HasLoopExit); 1306 1307 // Move the remaining edges from OrigBB to point to NewBB2. 1308 SmallVector<BasicBlock*, 8> NewBB2Preds; 1309 for (pred_iterator i = pred_begin(OrigBB), e = pred_end(OrigBB); 1310 i != e; ) { 1311 BasicBlock *Pred = *i++; 1312 if (Pred == NewBB1) continue; 1313 assert(!isa<IndirectBrInst>(Pred->getTerminator()) && 1314 "Cannot split an edge from an IndirectBrInst"); 1315 NewBB2Preds.push_back(Pred); 1316 e = pred_end(OrigBB); 1317 } 1318 1319 BasicBlock *NewBB2 = nullptr; 1320 if (!NewBB2Preds.empty()) { 1321 // Create another basic block for the rest of OrigBB's predecessors. 1322 NewBB2 = BasicBlock::Create(OrigBB->getContext(), 1323 OrigBB->getName() + Suffix2, 1324 OrigBB->getParent(), OrigBB); 1325 NewBBs.push_back(NewBB2); 1326 1327 // The new block unconditionally branches to the old block. 1328 BranchInst *BI2 = BranchInst::Create(OrigBB, NewBB2); 1329 BI2->setDebugLoc(OrigBB->getFirstNonPHI()->getDebugLoc()); 1330 1331 // Move the remaining edges from OrigBB to point to NewBB2. 1332 for (BasicBlock *NewBB2Pred : NewBB2Preds) 1333 NewBB2Pred->getTerminator()->replaceUsesOfWith(OrigBB, NewBB2); 1334 1335 // Update DominatorTree, LoopInfo, and LCCSA analysis information. 1336 HasLoopExit = false; 1337 UpdateAnalysisInformation(OrigBB, NewBB2, NewBB2Preds, DTU, DT, LI, MSSAU, 1338 PreserveLCSSA, HasLoopExit); 1339 1340 // Update the PHI nodes in OrigBB with the values coming from NewBB2. 1341 UpdatePHINodes(OrigBB, NewBB2, NewBB2Preds, BI2, HasLoopExit); 1342 } 1343 1344 LandingPadInst *LPad = OrigBB->getLandingPadInst(); 1345 Instruction *Clone1 = LPad->clone(); 1346 Clone1->setName(Twine("lpad") + Suffix1); 1347 Clone1->insertInto(NewBB1, NewBB1->getFirstInsertionPt()); 1348 1349 if (NewBB2) { 1350 Instruction *Clone2 = LPad->clone(); 1351 Clone2->setName(Twine("lpad") + Suffix2); 1352 Clone2->insertInto(NewBB2, NewBB2->getFirstInsertionPt()); 1353 1354 // Create a PHI node for the two cloned landingpad instructions only 1355 // if the original landingpad instruction has some uses. 1356 if (!LPad->use_empty()) { 1357 assert(!LPad->getType()->isTokenTy() && 1358 "Split cannot be applied if LPad is token type. Otherwise an " 1359 "invalid PHINode of token type would be created."); 1360 PHINode *PN = PHINode::Create(LPad->getType(), 2, "lpad.phi", LPad); 1361 PN->addIncoming(Clone1, NewBB1); 1362 PN->addIncoming(Clone2, NewBB2); 1363 LPad->replaceAllUsesWith(PN); 1364 } 1365 LPad->eraseFromParent(); 1366 } else { 1367 // There is no second clone. Just replace the landing pad with the first 1368 // clone. 1369 LPad->replaceAllUsesWith(Clone1); 1370 LPad->eraseFromParent(); 1371 } 1372 } 1373 1374 void llvm::SplitLandingPadPredecessors(BasicBlock *OrigBB, 1375 ArrayRef<BasicBlock *> Preds, 1376 const char *Suffix1, const char *Suffix2, 1377 SmallVectorImpl<BasicBlock *> &NewBBs, 1378 DominatorTree *DT, LoopInfo *LI, 1379 MemorySSAUpdater *MSSAU, 1380 bool PreserveLCSSA) { 1381 return SplitLandingPadPredecessorsImpl( 1382 OrigBB, Preds, Suffix1, Suffix2, NewBBs, 1383 /*DTU=*/nullptr, DT, LI, MSSAU, PreserveLCSSA); 1384 } 1385 void llvm::SplitLandingPadPredecessors(BasicBlock *OrigBB, 1386 ArrayRef<BasicBlock *> Preds, 1387 const char *Suffix1, const char *Suffix2, 1388 SmallVectorImpl<BasicBlock *> &NewBBs, 1389 DomTreeUpdater *DTU, LoopInfo *LI, 1390 MemorySSAUpdater *MSSAU, 1391 bool PreserveLCSSA) { 1392 return SplitLandingPadPredecessorsImpl(OrigBB, Preds, Suffix1, Suffix2, 1393 NewBBs, DTU, /*DT=*/nullptr, LI, MSSAU, 1394 PreserveLCSSA); 1395 } 1396 1397 ReturnInst *llvm::FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB, 1398 BasicBlock *Pred, 1399 DomTreeUpdater *DTU) { 1400 Instruction *UncondBranch = Pred->getTerminator(); 1401 // Clone the return and add it to the end of the predecessor. 1402 Instruction *NewRet = RI->clone(); 1403 NewRet->insertInto(Pred, Pred->end()); 1404 1405 // If the return instruction returns a value, and if the value was a 1406 // PHI node in "BB", propagate the right value into the return. 1407 for (Use &Op : NewRet->operands()) { 1408 Value *V = Op; 1409 Instruction *NewBC = nullptr; 1410 if (BitCastInst *BCI = dyn_cast<BitCastInst>(V)) { 1411 // Return value might be bitcasted. Clone and insert it before the 1412 // return instruction. 1413 V = BCI->getOperand(0); 1414 NewBC = BCI->clone(); 1415 NewBC->insertInto(Pred, NewRet->getIterator()); 1416 Op = NewBC; 1417 } 1418 1419 Instruction *NewEV = nullptr; 1420 if (ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(V)) { 1421 V = EVI->getOperand(0); 1422 NewEV = EVI->clone(); 1423 if (NewBC) { 1424 NewBC->setOperand(0, NewEV); 1425 NewEV->insertInto(Pred, NewBC->getIterator()); 1426 } else { 1427 NewEV->insertInto(Pred, NewRet->getIterator()); 1428 Op = NewEV; 1429 } 1430 } 1431 1432 if (PHINode *PN = dyn_cast<PHINode>(V)) { 1433 if (PN->getParent() == BB) { 1434 if (NewEV) { 1435 NewEV->setOperand(0, PN->getIncomingValueForBlock(Pred)); 1436 } else if (NewBC) 1437 NewBC->setOperand(0, PN->getIncomingValueForBlock(Pred)); 1438 else 1439 Op = PN->getIncomingValueForBlock(Pred); 1440 } 1441 } 1442 } 1443 1444 // Update any PHI nodes in the returning block to realize that we no 1445 // longer branch to them. 1446 BB->removePredecessor(Pred); 1447 UncondBranch->eraseFromParent(); 1448 1449 if (DTU) 1450 DTU->applyUpdates({{DominatorTree::Delete, Pred, BB}}); 1451 1452 return cast<ReturnInst>(NewRet); 1453 } 1454 1455 static Instruction * 1456 SplitBlockAndInsertIfThenImpl(Value *Cond, Instruction *SplitBefore, 1457 bool Unreachable, MDNode *BranchWeights, 1458 DomTreeUpdater *DTU, DominatorTree *DT, 1459 LoopInfo *LI, BasicBlock *ThenBlock) { 1460 SmallVector<DominatorTree::UpdateType, 8> Updates; 1461 BasicBlock *Head = SplitBefore->getParent(); 1462 BasicBlock *Tail = Head->splitBasicBlock(SplitBefore->getIterator()); 1463 if (DTU) { 1464 SmallPtrSet<BasicBlock *, 8> UniqueSuccessorsOfHead; 1465 Updates.push_back({DominatorTree::Insert, Head, Tail}); 1466 Updates.reserve(Updates.size() + 2 * succ_size(Tail)); 1467 for (BasicBlock *SuccessorOfHead : successors(Tail)) 1468 if (UniqueSuccessorsOfHead.insert(SuccessorOfHead).second) { 1469 Updates.push_back({DominatorTree::Insert, Tail, SuccessorOfHead}); 1470 Updates.push_back({DominatorTree::Delete, Head, SuccessorOfHead}); 1471 } 1472 } 1473 Instruction *HeadOldTerm = Head->getTerminator(); 1474 LLVMContext &C = Head->getContext(); 1475 Instruction *CheckTerm; 1476 bool CreateThenBlock = (ThenBlock == nullptr); 1477 if (CreateThenBlock) { 1478 ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail); 1479 if (Unreachable) 1480 CheckTerm = new UnreachableInst(C, ThenBlock); 1481 else { 1482 CheckTerm = BranchInst::Create(Tail, ThenBlock); 1483 if (DTU) 1484 Updates.push_back({DominatorTree::Insert, ThenBlock, Tail}); 1485 } 1486 CheckTerm->setDebugLoc(SplitBefore->getDebugLoc()); 1487 } else 1488 CheckTerm = ThenBlock->getTerminator(); 1489 BranchInst *HeadNewTerm = 1490 BranchInst::Create(/*ifTrue*/ ThenBlock, /*ifFalse*/ Tail, Cond); 1491 if (DTU) 1492 Updates.push_back({DominatorTree::Insert, Head, ThenBlock}); 1493 HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights); 1494 ReplaceInstWithInst(HeadOldTerm, HeadNewTerm); 1495 1496 if (DTU) 1497 DTU->applyUpdates(Updates); 1498 else if (DT) { 1499 if (DomTreeNode *OldNode = DT->getNode(Head)) { 1500 std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end()); 1501 1502 DomTreeNode *NewNode = DT->addNewBlock(Tail, Head); 1503 for (DomTreeNode *Child : Children) 1504 DT->changeImmediateDominator(Child, NewNode); 1505 1506 // Head dominates ThenBlock. 1507 if (CreateThenBlock) 1508 DT->addNewBlock(ThenBlock, Head); 1509 else 1510 DT->changeImmediateDominator(ThenBlock, Head); 1511 } 1512 } 1513 1514 if (LI) { 1515 if (Loop *L = LI->getLoopFor(Head)) { 1516 L->addBasicBlockToLoop(ThenBlock, *LI); 1517 L->addBasicBlockToLoop(Tail, *LI); 1518 } 1519 } 1520 1521 return CheckTerm; 1522 } 1523 1524 Instruction *llvm::SplitBlockAndInsertIfThen(Value *Cond, 1525 Instruction *SplitBefore, 1526 bool Unreachable, 1527 MDNode *BranchWeights, 1528 DominatorTree *DT, LoopInfo *LI, 1529 BasicBlock *ThenBlock) { 1530 return SplitBlockAndInsertIfThenImpl(Cond, SplitBefore, Unreachable, 1531 BranchWeights, 1532 /*DTU=*/nullptr, DT, LI, ThenBlock); 1533 } 1534 Instruction *llvm::SplitBlockAndInsertIfThen(Value *Cond, 1535 Instruction *SplitBefore, 1536 bool Unreachable, 1537 MDNode *BranchWeights, 1538 DomTreeUpdater *DTU, LoopInfo *LI, 1539 BasicBlock *ThenBlock) { 1540 return SplitBlockAndInsertIfThenImpl(Cond, SplitBefore, Unreachable, 1541 BranchWeights, DTU, /*DT=*/nullptr, LI, 1542 ThenBlock); 1543 } 1544 1545 void llvm::SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore, 1546 Instruction **ThenTerm, 1547 Instruction **ElseTerm, 1548 MDNode *BranchWeights, 1549 DomTreeUpdater *DTU) { 1550 BasicBlock *Head = SplitBefore->getParent(); 1551 1552 SmallPtrSet<BasicBlock *, 8> UniqueOrigSuccessors; 1553 if (DTU) 1554 UniqueOrigSuccessors.insert(succ_begin(Head), succ_end(Head)); 1555 1556 BasicBlock *Tail = Head->splitBasicBlock(SplitBefore->getIterator()); 1557 Instruction *HeadOldTerm = Head->getTerminator(); 1558 LLVMContext &C = Head->getContext(); 1559 BasicBlock *ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail); 1560 BasicBlock *ElseBlock = BasicBlock::Create(C, "", Head->getParent(), Tail); 1561 *ThenTerm = BranchInst::Create(Tail, ThenBlock); 1562 (*ThenTerm)->setDebugLoc(SplitBefore->getDebugLoc()); 1563 *ElseTerm = BranchInst::Create(Tail, ElseBlock); 1564 (*ElseTerm)->setDebugLoc(SplitBefore->getDebugLoc()); 1565 BranchInst *HeadNewTerm = 1566 BranchInst::Create(/*ifTrue*/ThenBlock, /*ifFalse*/ElseBlock, Cond); 1567 HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights); 1568 ReplaceInstWithInst(HeadOldTerm, HeadNewTerm); 1569 if (DTU) { 1570 SmallVector<DominatorTree::UpdateType, 8> Updates; 1571 Updates.reserve(4 + 2 * UniqueOrigSuccessors.size()); 1572 for (BasicBlock *Succ : successors(Head)) { 1573 Updates.push_back({DominatorTree::Insert, Head, Succ}); 1574 Updates.push_back({DominatorTree::Insert, Succ, Tail}); 1575 } 1576 for (BasicBlock *UniqueOrigSuccessor : UniqueOrigSuccessors) 1577 Updates.push_back({DominatorTree::Insert, Tail, UniqueOrigSuccessor}); 1578 for (BasicBlock *UniqueOrigSuccessor : UniqueOrigSuccessors) 1579 Updates.push_back({DominatorTree::Delete, Head, UniqueOrigSuccessor}); 1580 DTU->applyUpdates(Updates); 1581 } 1582 } 1583 1584 BranchInst *llvm::GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, 1585 BasicBlock *&IfFalse) { 1586 PHINode *SomePHI = dyn_cast<PHINode>(BB->begin()); 1587 BasicBlock *Pred1 = nullptr; 1588 BasicBlock *Pred2 = nullptr; 1589 1590 if (SomePHI) { 1591 if (SomePHI->getNumIncomingValues() != 2) 1592 return nullptr; 1593 Pred1 = SomePHI->getIncomingBlock(0); 1594 Pred2 = SomePHI->getIncomingBlock(1); 1595 } else { 1596 pred_iterator PI = pred_begin(BB), PE = pred_end(BB); 1597 if (PI == PE) // No predecessor 1598 return nullptr; 1599 Pred1 = *PI++; 1600 if (PI == PE) // Only one predecessor 1601 return nullptr; 1602 Pred2 = *PI++; 1603 if (PI != PE) // More than two predecessors 1604 return nullptr; 1605 } 1606 1607 // We can only handle branches. Other control flow will be lowered to 1608 // branches if possible anyway. 1609 BranchInst *Pred1Br = dyn_cast<BranchInst>(Pred1->getTerminator()); 1610 BranchInst *Pred2Br = dyn_cast<BranchInst>(Pred2->getTerminator()); 1611 if (!Pred1Br || !Pred2Br) 1612 return nullptr; 1613 1614 // Eliminate code duplication by ensuring that Pred1Br is conditional if 1615 // either are. 1616 if (Pred2Br->isConditional()) { 1617 // If both branches are conditional, we don't have an "if statement". In 1618 // reality, we could transform this case, but since the condition will be 1619 // required anyway, we stand no chance of eliminating it, so the xform is 1620 // probably not profitable. 1621 if (Pred1Br->isConditional()) 1622 return nullptr; 1623 1624 std::swap(Pred1, Pred2); 1625 std::swap(Pred1Br, Pred2Br); 1626 } 1627 1628 if (Pred1Br->isConditional()) { 1629 // The only thing we have to watch out for here is to make sure that Pred2 1630 // doesn't have incoming edges from other blocks. If it does, the condition 1631 // doesn't dominate BB. 1632 if (!Pred2->getSinglePredecessor()) 1633 return nullptr; 1634 1635 // If we found a conditional branch predecessor, make sure that it branches 1636 // to BB and Pred2Br. If it doesn't, this isn't an "if statement". 1637 if (Pred1Br->getSuccessor(0) == BB && 1638 Pred1Br->getSuccessor(1) == Pred2) { 1639 IfTrue = Pred1; 1640 IfFalse = Pred2; 1641 } else if (Pred1Br->getSuccessor(0) == Pred2 && 1642 Pred1Br->getSuccessor(1) == BB) { 1643 IfTrue = Pred2; 1644 IfFalse = Pred1; 1645 } else { 1646 // We know that one arm of the conditional goes to BB, so the other must 1647 // go somewhere unrelated, and this must not be an "if statement". 1648 return nullptr; 1649 } 1650 1651 return Pred1Br; 1652 } 1653 1654 // Ok, if we got here, both predecessors end with an unconditional branch to 1655 // BB. Don't panic! If both blocks only have a single (identical) 1656 // predecessor, and THAT is a conditional branch, then we're all ok! 1657 BasicBlock *CommonPred = Pred1->getSinglePredecessor(); 1658 if (CommonPred == nullptr || CommonPred != Pred2->getSinglePredecessor()) 1659 return nullptr; 1660 1661 // Otherwise, if this is a conditional branch, then we can use it! 1662 BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator()); 1663 if (!BI) return nullptr; 1664 1665 assert(BI->isConditional() && "Two successors but not conditional?"); 1666 if (BI->getSuccessor(0) == Pred1) { 1667 IfTrue = Pred1; 1668 IfFalse = Pred2; 1669 } else { 1670 IfTrue = Pred2; 1671 IfFalse = Pred1; 1672 } 1673 return BI; 1674 } 1675 1676 // After creating a control flow hub, the operands of PHINodes in an outgoing 1677 // block Out no longer match the predecessors of that block. Predecessors of Out 1678 // that are incoming blocks to the hub are now replaced by just one edge from 1679 // the hub. To match this new control flow, the corresponding values from each 1680 // PHINode must now be moved a new PHINode in the first guard block of the hub. 1681 // 1682 // This operation cannot be performed with SSAUpdater, because it involves one 1683 // new use: If the block Out is in the list of Incoming blocks, then the newly 1684 // created PHI in the Hub will use itself along that edge from Out to Hub. 1685 static void reconnectPhis(BasicBlock *Out, BasicBlock *GuardBlock, 1686 const SetVector<BasicBlock *> &Incoming, 1687 BasicBlock *FirstGuardBlock) { 1688 auto I = Out->begin(); 1689 while (I != Out->end() && isa<PHINode>(I)) { 1690 auto Phi = cast<PHINode>(I); 1691 auto NewPhi = 1692 PHINode::Create(Phi->getType(), Incoming.size(), 1693 Phi->getName() + ".moved", &FirstGuardBlock->front()); 1694 for (auto *In : Incoming) { 1695 Value *V = UndefValue::get(Phi->getType()); 1696 if (In == Out) { 1697 V = NewPhi; 1698 } else if (Phi->getBasicBlockIndex(In) != -1) { 1699 V = Phi->removeIncomingValue(In, false); 1700 } 1701 NewPhi->addIncoming(V, In); 1702 } 1703 assert(NewPhi->getNumIncomingValues() == Incoming.size()); 1704 if (Phi->getNumOperands() == 0) { 1705 Phi->replaceAllUsesWith(NewPhi); 1706 I = Phi->eraseFromParent(); 1707 continue; 1708 } 1709 Phi->addIncoming(NewPhi, GuardBlock); 1710 ++I; 1711 } 1712 } 1713 1714 using BBPredicates = DenseMap<BasicBlock *, Instruction *>; 1715 using BBSetVector = SetVector<BasicBlock *>; 1716 1717 // Redirects the terminator of the incoming block to the first guard 1718 // block in the hub. The condition of the original terminator (if it 1719 // was conditional) and its original successors are returned as a 1720 // tuple <condition, succ0, succ1>. The function additionally filters 1721 // out successors that are not in the set of outgoing blocks. 1722 // 1723 // - condition is non-null iff the branch is conditional. 1724 // - Succ1 is non-null iff the sole/taken target is an outgoing block. 1725 // - Succ2 is non-null iff condition is non-null and the fallthrough 1726 // target is an outgoing block. 1727 static std::tuple<Value *, BasicBlock *, BasicBlock *> 1728 redirectToHub(BasicBlock *BB, BasicBlock *FirstGuardBlock, 1729 const BBSetVector &Outgoing) { 1730 assert(isa<BranchInst>(BB->getTerminator()) && 1731 "Only support branch terminator."); 1732 auto Branch = cast<BranchInst>(BB->getTerminator()); 1733 auto Condition = Branch->isConditional() ? Branch->getCondition() : nullptr; 1734 1735 BasicBlock *Succ0 = Branch->getSuccessor(0); 1736 BasicBlock *Succ1 = nullptr; 1737 Succ0 = Outgoing.count(Succ0) ? Succ0 : nullptr; 1738 1739 if (Branch->isUnconditional()) { 1740 Branch->setSuccessor(0, FirstGuardBlock); 1741 assert(Succ0); 1742 } else { 1743 Succ1 = Branch->getSuccessor(1); 1744 Succ1 = Outgoing.count(Succ1) ? Succ1 : nullptr; 1745 assert(Succ0 || Succ1); 1746 if (Succ0 && !Succ1) { 1747 Branch->setSuccessor(0, FirstGuardBlock); 1748 } else if (Succ1 && !Succ0) { 1749 Branch->setSuccessor(1, FirstGuardBlock); 1750 } else { 1751 Branch->eraseFromParent(); 1752 BranchInst::Create(FirstGuardBlock, BB); 1753 } 1754 } 1755 1756 assert(Succ0 || Succ1); 1757 return std::make_tuple(Condition, Succ0, Succ1); 1758 } 1759 // Setup the branch instructions for guard blocks. 1760 // 1761 // Each guard block terminates in a conditional branch that transfers 1762 // control to the corresponding outgoing block or the next guard 1763 // block. The last guard block has two outgoing blocks as successors 1764 // since the condition for the final outgoing block is trivially 1765 // true. So we create one less block (including the first guard block) 1766 // than the number of outgoing blocks. 1767 static void setupBranchForGuard(SmallVectorImpl<BasicBlock *> &GuardBlocks, 1768 const BBSetVector &Outgoing, 1769 BBPredicates &GuardPredicates) { 1770 // To help keep the loop simple, temporarily append the last 1771 // outgoing block to the list of guard blocks. 1772 GuardBlocks.push_back(Outgoing.back()); 1773 1774 for (int i = 0, e = GuardBlocks.size() - 1; i != e; ++i) { 1775 auto Out = Outgoing[i]; 1776 assert(GuardPredicates.count(Out)); 1777 BranchInst::Create(Out, GuardBlocks[i + 1], GuardPredicates[Out], 1778 GuardBlocks[i]); 1779 } 1780 1781 // Remove the last block from the guard list. 1782 GuardBlocks.pop_back(); 1783 } 1784 1785 /// We are using one integer to represent the block we are branching to. Then at 1786 /// each guard block, the predicate was calcuated using a simple `icmp eq`. 1787 static void calcPredicateUsingInteger( 1788 const BBSetVector &Incoming, const BBSetVector &Outgoing, 1789 SmallVectorImpl<BasicBlock *> &GuardBlocks, BBPredicates &GuardPredicates) { 1790 auto &Context = Incoming.front()->getContext(); 1791 auto FirstGuardBlock = GuardBlocks.front(); 1792 1793 auto Phi = PHINode::Create(Type::getInt32Ty(Context), Incoming.size(), 1794 "merged.bb.idx", FirstGuardBlock); 1795 1796 for (auto In : Incoming) { 1797 Value *Condition; 1798 BasicBlock *Succ0; 1799 BasicBlock *Succ1; 1800 std::tie(Condition, Succ0, Succ1) = 1801 redirectToHub(In, FirstGuardBlock, Outgoing); 1802 Value *IncomingId = nullptr; 1803 if (Succ0 && Succ1) { 1804 // target_bb_index = Condition ? index_of_succ0 : index_of_succ1. 1805 auto Succ0Iter = find(Outgoing, Succ0); 1806 auto Succ1Iter = find(Outgoing, Succ1); 1807 Value *Id0 = ConstantInt::get(Type::getInt32Ty(Context), 1808 std::distance(Outgoing.begin(), Succ0Iter)); 1809 Value *Id1 = ConstantInt::get(Type::getInt32Ty(Context), 1810 std::distance(Outgoing.begin(), Succ1Iter)); 1811 IncomingId = SelectInst::Create(Condition, Id0, Id1, "target.bb.idx", 1812 In->getTerminator()); 1813 } else { 1814 // Get the index of the non-null successor. 1815 auto SuccIter = Succ0 ? find(Outgoing, Succ0) : find(Outgoing, Succ1); 1816 IncomingId = ConstantInt::get(Type::getInt32Ty(Context), 1817 std::distance(Outgoing.begin(), SuccIter)); 1818 } 1819 Phi->addIncoming(IncomingId, In); 1820 } 1821 1822 for (int i = 0, e = Outgoing.size() - 1; i != e; ++i) { 1823 auto Out = Outgoing[i]; 1824 auto Cmp = ICmpInst::Create(Instruction::ICmp, ICmpInst::ICMP_EQ, Phi, 1825 ConstantInt::get(Type::getInt32Ty(Context), i), 1826 Out->getName() + ".predicate", GuardBlocks[i]); 1827 GuardPredicates[Out] = Cmp; 1828 } 1829 } 1830 1831 /// We record the predicate of each outgoing block using a phi of boolean. 1832 static void calcPredicateUsingBooleans( 1833 const BBSetVector &Incoming, const BBSetVector &Outgoing, 1834 SmallVectorImpl<BasicBlock *> &GuardBlocks, BBPredicates &GuardPredicates, 1835 SmallVectorImpl<WeakVH> &DeletionCandidates) { 1836 auto &Context = Incoming.front()->getContext(); 1837 auto BoolTrue = ConstantInt::getTrue(Context); 1838 auto BoolFalse = ConstantInt::getFalse(Context); 1839 auto FirstGuardBlock = GuardBlocks.front(); 1840 1841 // The predicate for the last outgoing is trivially true, and so we 1842 // process only the first N-1 successors. 1843 for (int i = 0, e = Outgoing.size() - 1; i != e; ++i) { 1844 auto Out = Outgoing[i]; 1845 LLVM_DEBUG(dbgs() << "Creating guard for " << Out->getName() << "\n"); 1846 1847 auto Phi = 1848 PHINode::Create(Type::getInt1Ty(Context), Incoming.size(), 1849 StringRef("Guard.") + Out->getName(), FirstGuardBlock); 1850 GuardPredicates[Out] = Phi; 1851 } 1852 1853 for (auto *In : Incoming) { 1854 Value *Condition; 1855 BasicBlock *Succ0; 1856 BasicBlock *Succ1; 1857 std::tie(Condition, Succ0, Succ1) = 1858 redirectToHub(In, FirstGuardBlock, Outgoing); 1859 1860 // Optimization: Consider an incoming block A with both successors 1861 // Succ0 and Succ1 in the set of outgoing blocks. The predicates 1862 // for Succ0 and Succ1 complement each other. If Succ0 is visited 1863 // first in the loop below, control will branch to Succ0 using the 1864 // corresponding predicate. But if that branch is not taken, then 1865 // control must reach Succ1, which means that the incoming value of 1866 // the predicate from `In` is true for Succ1. 1867 bool OneSuccessorDone = false; 1868 for (int i = 0, e = Outgoing.size() - 1; i != e; ++i) { 1869 auto Out = Outgoing[i]; 1870 PHINode *Phi = cast<PHINode>(GuardPredicates[Out]); 1871 if (Out != Succ0 && Out != Succ1) { 1872 Phi->addIncoming(BoolFalse, In); 1873 } else if (!Succ0 || !Succ1 || OneSuccessorDone) { 1874 // Optimization: When only one successor is an outgoing block, 1875 // the incoming predicate from `In` is always true. 1876 Phi->addIncoming(BoolTrue, In); 1877 } else { 1878 assert(Succ0 && Succ1); 1879 if (Out == Succ0) { 1880 Phi->addIncoming(Condition, In); 1881 } else { 1882 auto Inverted = invertCondition(Condition); 1883 DeletionCandidates.push_back(Condition); 1884 Phi->addIncoming(Inverted, In); 1885 } 1886 OneSuccessorDone = true; 1887 } 1888 } 1889 } 1890 } 1891 1892 // Capture the existing control flow as guard predicates, and redirect 1893 // control flow from \p Incoming block through the \p GuardBlocks to the 1894 // \p Outgoing blocks. 1895 // 1896 // There is one guard predicate for each outgoing block OutBB. The 1897 // predicate represents whether the hub should transfer control flow 1898 // to OutBB. These predicates are NOT ORTHOGONAL. The Hub evaluates 1899 // them in the same order as the Outgoing set-vector, and control 1900 // branches to the first outgoing block whose predicate evaluates to true. 1901 static void 1902 convertToGuardPredicates(SmallVectorImpl<BasicBlock *> &GuardBlocks, 1903 SmallVectorImpl<WeakVH> &DeletionCandidates, 1904 const BBSetVector &Incoming, 1905 const BBSetVector &Outgoing, const StringRef Prefix, 1906 std::optional<unsigned> MaxControlFlowBooleans) { 1907 BBPredicates GuardPredicates; 1908 auto F = Incoming.front()->getParent(); 1909 1910 for (int i = 0, e = Outgoing.size() - 1; i != e; ++i) 1911 GuardBlocks.push_back( 1912 BasicBlock::Create(F->getContext(), Prefix + ".guard", F)); 1913 1914 // When we are using an integer to record which target block to jump to, we 1915 // are creating less live values, actually we are using one single integer to 1916 // store the index of the target block. When we are using booleans to store 1917 // the branching information, we need (N-1) boolean values, where N is the 1918 // number of outgoing block. 1919 if (!MaxControlFlowBooleans || Outgoing.size() <= *MaxControlFlowBooleans) 1920 calcPredicateUsingBooleans(Incoming, Outgoing, GuardBlocks, GuardPredicates, 1921 DeletionCandidates); 1922 else 1923 calcPredicateUsingInteger(Incoming, Outgoing, GuardBlocks, GuardPredicates); 1924 1925 setupBranchForGuard(GuardBlocks, Outgoing, GuardPredicates); 1926 } 1927 1928 BasicBlock *llvm::CreateControlFlowHub( 1929 DomTreeUpdater *DTU, SmallVectorImpl<BasicBlock *> &GuardBlocks, 1930 const BBSetVector &Incoming, const BBSetVector &Outgoing, 1931 const StringRef Prefix, std::optional<unsigned> MaxControlFlowBooleans) { 1932 if (Outgoing.size() < 2) 1933 return Outgoing.front(); 1934 1935 SmallVector<DominatorTree::UpdateType, 16> Updates; 1936 if (DTU) { 1937 for (auto *In : Incoming) { 1938 for (auto Succ : successors(In)) 1939 if (Outgoing.count(Succ)) 1940 Updates.push_back({DominatorTree::Delete, In, Succ}); 1941 } 1942 } 1943 1944 SmallVector<WeakVH, 8> DeletionCandidates; 1945 convertToGuardPredicates(GuardBlocks, DeletionCandidates, Incoming, Outgoing, 1946 Prefix, MaxControlFlowBooleans); 1947 auto FirstGuardBlock = GuardBlocks.front(); 1948 1949 // Update the PHINodes in each outgoing block to match the new control flow. 1950 for (int i = 0, e = GuardBlocks.size(); i != e; ++i) 1951 reconnectPhis(Outgoing[i], GuardBlocks[i], Incoming, FirstGuardBlock); 1952 1953 reconnectPhis(Outgoing.back(), GuardBlocks.back(), Incoming, FirstGuardBlock); 1954 1955 if (DTU) { 1956 int NumGuards = GuardBlocks.size(); 1957 assert((int)Outgoing.size() == NumGuards + 1); 1958 1959 for (auto In : Incoming) 1960 Updates.push_back({DominatorTree::Insert, In, FirstGuardBlock}); 1961 1962 for (int i = 0; i != NumGuards - 1; ++i) { 1963 Updates.push_back({DominatorTree::Insert, GuardBlocks[i], Outgoing[i]}); 1964 Updates.push_back( 1965 {DominatorTree::Insert, GuardBlocks[i], GuardBlocks[i + 1]}); 1966 } 1967 Updates.push_back({DominatorTree::Insert, GuardBlocks[NumGuards - 1], 1968 Outgoing[NumGuards - 1]}); 1969 Updates.push_back({DominatorTree::Insert, GuardBlocks[NumGuards - 1], 1970 Outgoing[NumGuards]}); 1971 DTU->applyUpdates(Updates); 1972 } 1973 1974 for (auto I : DeletionCandidates) { 1975 if (I->use_empty()) 1976 if (auto Inst = dyn_cast_or_null<Instruction>(I)) 1977 Inst->eraseFromParent(); 1978 } 1979 1980 return FirstGuardBlock; 1981 } 1982