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