llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

   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
 386 DbgVariableRecordsRemoveRedundantDbgInstrsUsingBackwardScan(BasicBlock *BB) {
 387   SmallVector<DbgVariableRecord *, 8> ToBeRemoved;
 388   SmallDenseSet<DebugVariable> VariableSet;
 389   for (auto &I : reverse(*BB)) {
 390     for (DbgRecord &DR : reverse(I.getDbgRecordRange())) {
 391       if (isa<DbgLabelRecord>(DR)) {
 392         // Emulate existing behaviour (see comment below for dbg.declares).
 393         // FIXME: Don't do this.
 394         VariableSet.clear();
 395         continue;
 396       }
 397
 398       DbgVariableRecord &DVR = cast<DbgVariableRecord>(DR);
 399       // Skip declare-type records, as the debug intrinsic method only works
 400       // on dbg.value intrinsics.
 401       if (DVR.getType() == DbgVariableRecord::LocationType::Declare) {
 402         // The debug intrinsic method treats dbg.declares are "non-debug"
 403         // instructions (i.e., a break in a consecutive range of debug
 404         // intrinsics). Emulate that to create identical outputs. See
 405         // "Possible improvements" above.
 406         // FIXME: Delete the line below.
 407         VariableSet.clear();
 408         continue;
 409       }
 410
 411       DebugVariable Key(DVR.getVariable(), DVR.getExpression(),
 412                         DVR.getDebugLoc()->getInlinedAt());
 413       auto R = VariableSet.insert(Key);
 414       // If the same variable fragment is described more than once it is enough
 415       // to keep the last one (i.e. the first found since we for reverse
 416       // iteration).
 417       if (R.second)
 418         continue;
 419
 420       if (DVR.isDbgAssign()) {
 421         // Don't delete dbg.assign intrinsics that are linked to instructions.
 422         if (!at::getAssignmentInsts(&DVR).empty())
 423           continue;
 424         // Unlinked dbg.assign intrinsics can be treated like dbg.values.
 425       }
 426
 427       ToBeRemoved.push_back(&DVR);
 428     }
 429     // Sequence with consecutive dbg.value instrs ended. Clear the map to
 430     // restart identifying redundant instructions if case we find another
 431     // dbg.value sequence.
 432     VariableSet.clear();
 433   }
 434
 435   for (auto &DVR : ToBeRemoved)
 436     DVR->eraseFromParent();
 437
 438   return !ToBeRemoved.empty();
 439 }
 440
 441 static bool removeRedundantDbgInstrsUsingBackwardScan(BasicBlock *BB) {
 442   if (BB->IsNewDbgInfoFormat)
 443     return DbgVariableRecordsRemoveRedundantDbgInstrsUsingBackwardScan(BB);
 444
 445   SmallVector<DbgValueInst *, 8> ToBeRemoved;
 446   SmallDenseSet<DebugVariable> VariableSet;
 447   for (auto &I : reverse(*BB)) {
 448     if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(&I)) {
 449       DebugVariable Key(DVI->getVariable(),
 450                         DVI->getExpression(),
 451                         DVI->getDebugLoc()->getInlinedAt());
 452       auto R = VariableSet.insert(Key);
 453       // If the variable fragment hasn't been seen before then we don't want
 454       // to remove this dbg intrinsic.
 455       if (R.second)
 456         continue;
 457
 458       if (auto *DAI = dyn_cast<DbgAssignIntrinsic>(DVI)) {
 459         // Don't delete dbg.assign intrinsics that are linked to instructions.
 460         if (!at::getAssignmentInsts(DAI).empty())
 461           continue;
 462         // Unlinked dbg.assign intrinsics can be treated like dbg.values.
 463       }
 464
 465       // If the same variable fragment is described more than once it is enough
 466       // to keep the last one (i.e. the first found since we for reverse
 467       // iteration).
 468       ToBeRemoved.push_back(DVI);
 469       continue;
 470     }
 471     // Sequence with consecutive dbg.value instrs ended. Clear the map to
 472     // restart identifying redundant instructions if case we find another
 473     // dbg.value sequence.
 474     VariableSet.clear();
 475   }
 476
 477   for (auto &Instr : ToBeRemoved)
 478     Instr->eraseFromParent();
 479
 480   return !ToBeRemoved.empty();
 481 }
 482
 483 /// Remove redundant dbg.value instructions using a forward scan. This can
 484 /// remove a dbg.value instruction that is redundant due to indicating that a
 485 /// variable has the same value as already being indicated by an earlier
 486 /// dbg.value.
 487 ///
 488 /// ForwardScan strategy:
 489 /// ---------------------
 490 /// Given two identical dbg.value instructions, separated by a block of
 491 /// instructions that isn't describing the same variable, like this
 492 ///
 493 ///   dbg.value X1, "x", FragmentX1  (**)
 494 ///   <block of instructions, none being "dbg.value ..., "x", ...">
 495 ///   dbg.value X1, "x", FragmentX1  (*)
 496 ///
 497 /// then the instruction marked with (*) can be removed. Variable "x" is already
 498 /// described as being mapped to the SSA value X1.
 499 ///
 500 /// Possible improvements:
 501 /// - Keep track of non-overlapping fragments.
 502 static bool
 503 DbgVariableRecordsRemoveRedundantDbgInstrsUsingForwardScan(BasicBlock *BB) {
 504   SmallVector<DbgVariableRecord *, 8> ToBeRemoved;
 505   SmallDenseMap<DebugVariable,
 506                 std::pair<SmallVector<Value *, 4>, DIExpression *>, 4>
 507       VariableMap;
 508   for (auto &I : *BB) {
 509     for (DbgVariableRecord &DVR : filterDbgVars(I.getDbgRecordRange())) {
 510       if (DVR.getType() == DbgVariableRecord::LocationType::Declare)
 511         continue;
 512       DebugVariable Key(DVR.getVariable(), std::nullopt,
 513                         DVR.getDebugLoc()->getInlinedAt());
 514       auto VMI = VariableMap.find(Key);
 515       // A dbg.assign with no linked instructions can be treated like a
 516       // dbg.value (i.e. can be deleted).
 517       bool IsDbgValueKind =
 518           (!DVR.isDbgAssign() || at::getAssignmentInsts(&DVR).empty());
 519
 520       // Update the map if we found a new value/expression describing the
 521       // variable, or if the variable wasn't mapped already.
 522       SmallVector<Value *, 4> Values(DVR.location_ops());
 523       if (VMI == VariableMap.end() || VMI->second.first != Values ||
 524           VMI->second.second != DVR.getExpression()) {
 525         if (IsDbgValueKind)
 526           VariableMap[Key] = {Values, DVR.getExpression()};
 527         else
 528           VariableMap[Key] = {Values, nullptr};
 529         continue;
 530       }
 531       // Don't delete dbg.assign intrinsics that are linked to instructions.
 532       if (!IsDbgValueKind)
 533         continue;
 534       // Found an identical mapping. Remember the instruction for later removal.
 535       ToBeRemoved.push_back(&DVR);
 536     }
 537   }
 538
 539   for (auto *DVR : ToBeRemoved)
 540     DVR->eraseFromParent();
 541
 542   return !ToBeRemoved.empty();
 543 }
 544
 545 static bool
 546 DbgVariableRecordsRemoveUndefDbgAssignsFromEntryBlock(BasicBlock *BB) {
 547   assert(BB->isEntryBlock() && "expected entry block");
 548   SmallVector<DbgVariableRecord *, 8> ToBeRemoved;
 549   DenseSet<DebugVariable> SeenDefForAggregate;
 550   // Returns the DebugVariable for DVI with no fragment info.
 551   auto GetAggregateVariable = [](const DbgVariableRecord &DVR) {
 552     return DebugVariable(DVR.getVariable(), std::nullopt,
 553                          DVR.getDebugLoc().getInlinedAt());
 554   };
 555
 556   // Remove undef dbg.assign intrinsics that are encountered before
 557   // any non-undef intrinsics from the entry block.
 558   for (auto &I : *BB) {
 559     for (DbgVariableRecord &DVR : filterDbgVars(I.getDbgRecordRange())) {
 560       if (!DVR.isDbgValue() && !DVR.isDbgAssign())
 561         continue;
 562       bool IsDbgValueKind =
 563           (DVR.isDbgValue() || at::getAssignmentInsts(&DVR).empty());
 564       DebugVariable Aggregate = GetAggregateVariable(DVR);
 565       if (!SeenDefForAggregate.contains(Aggregate)) {
 566         bool IsKill = DVR.isKillLocation() && IsDbgValueKind;
 567         if (!IsKill) {
 568           SeenDefForAggregate.insert(Aggregate);
 569         } else if (DVR.isDbgAssign()) {
 570           ToBeRemoved.push_back(&DVR);
 571         }
 572       }
 573     }
 574   }
 575
 576   for (DbgVariableRecord *DVR : ToBeRemoved)
 577     DVR->eraseFromParent();
 578
 579   return !ToBeRemoved.empty();
 580 }
 581
 582 static bool removeRedundantDbgInstrsUsingForwardScan(BasicBlock *BB) {
 583   if (BB->IsNewDbgInfoFormat)
 584     return DbgVariableRecordsRemoveRedundantDbgInstrsUsingForwardScan(BB);
 585
 586   SmallVector<DbgValueInst *, 8> ToBeRemoved;
 587   SmallDenseMap<DebugVariable,
 588                 std::pair<SmallVector<Value *, 4>, DIExpression *>, 4>
 589       VariableMap;
 590   for (auto &I : *BB) {
 591     if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(&I)) {
 592       DebugVariable Key(DVI->getVariable(), std::nullopt,
 593                         DVI->getDebugLoc()->getInlinedAt());
 594       auto VMI = VariableMap.find(Key);
 595       auto *DAI = dyn_cast<DbgAssignIntrinsic>(DVI);
 596       // A dbg.assign with no linked instructions can be treated like a
 597       // dbg.value (i.e. can be deleted).
 598       bool IsDbgValueKind = (!DAI || at::getAssignmentInsts(DAI).empty());
 599
 600       // Update the map if we found a new value/expression describing the
 601       // variable, or if the variable wasn't mapped already.
 602       SmallVector<Value *, 4> Values(DVI->getValues());
 603       if (VMI == VariableMap.end() || VMI->second.first != Values ||
 604           VMI->second.second != DVI->getExpression()) {
 605         // Use a sentinel value (nullptr) for the DIExpression when we see a
 606         // linked dbg.assign so that the next debug intrinsic will never match
 607         // it (i.e. always treat linked dbg.assigns as if they're unique).
 608         if (IsDbgValueKind)
 609           VariableMap[Key] = {Values, DVI->getExpression()};
 610         else
 611           VariableMap[Key] = {Values, nullptr};
 612         continue;
 613       }
 614
 615       // Don't delete dbg.assign intrinsics that are linked to instructions.
 616       if (!IsDbgValueKind)
 617         continue;
 618       ToBeRemoved.push_back(DVI);
 619     }
 620   }
 621
 622   for (auto &Instr : ToBeRemoved)
 623     Instr->eraseFromParent();
 624
 625   return !ToBeRemoved.empty();
 626 }
 627
 628 /// Remove redundant undef dbg.assign intrinsic from an entry block using a
 629 /// forward scan.
 630 /// Strategy:
 631 /// ---------------------
 632 /// Scanning forward, delete dbg.assign intrinsics iff they are undef, not
 633 /// linked to an intrinsic, and don't share an aggregate variable with a debug
 634 /// intrinsic that didn't meet the criteria. In other words, undef dbg.assigns
 635 /// that come before non-undef debug intrinsics for the variable are
 636 /// deleted. Given:
 637 ///
 638 ///   dbg.assign undef, "x", FragmentX1 (*)
 639 ///   <block of instructions, none being "dbg.value ..., "x", ...">
 640 ///   dbg.value %V, "x", FragmentX2
 641 ///   <block of instructions, none being "dbg.value ..., "x", ...">
 642 ///   dbg.assign undef, "x", FragmentX1
 643 ///
 644 /// then (only) the instruction marked with (*) can be removed.
 645 /// Possible improvements:
 646 /// - Keep track of non-overlapping fragments.
 647 static bool removeUndefDbgAssignsFromEntryBlock(BasicBlock *BB) {
 648   if (BB->IsNewDbgInfoFormat)
 649     return DbgVariableRecordsRemoveUndefDbgAssignsFromEntryBlock(BB);
 650
 651   assert(BB->isEntryBlock() && "expected entry block");
 652   SmallVector<DbgAssignIntrinsic *, 8> ToBeRemoved;
 653   DenseSet<DebugVariable> SeenDefForAggregate;
 654   // Returns the DebugVariable for DVI with no fragment info.
 655   auto GetAggregateVariable = [](DbgValueInst *DVI) {
 656     return DebugVariable(DVI->getVariable(), std::nullopt,
 657                          DVI->getDebugLoc()->getInlinedAt());
 658   };
 659
 660   // Remove undef dbg.assign intrinsics that are encountered before
 661   // any non-undef intrinsics from the entry block.
 662   for (auto &I : *BB) {
 663     DbgValueInst *DVI = dyn_cast<DbgValueInst>(&I);
 664     if (!DVI)
 665       continue;
 666     auto *DAI = dyn_cast<DbgAssignIntrinsic>(DVI);
 667     bool IsDbgValueKind = (!DAI || at::getAssignmentInsts(DAI).empty());
 668     DebugVariable Aggregate = GetAggregateVariable(DVI);
 669     if (!SeenDefForAggregate.contains(Aggregate)) {
 670       bool IsKill = DVI->isKillLocation() && IsDbgValueKind;
 671       if (!IsKill) {
 672         SeenDefForAggregate.insert(Aggregate);
 673       } else if (DAI) {
 674         ToBeRemoved.push_back(DAI);
 675       }
 676     }
 677   }
 678
 679   for (DbgAssignIntrinsic *DAI : ToBeRemoved)
 680     DAI->eraseFromParent();
 681
 682   return !ToBeRemoved.empty();
 683 }
 684
 685 bool llvm::RemoveRedundantDbgInstrs(BasicBlock *BB) {
 686   bool MadeChanges = false;
 687   // By using the "backward scan" strategy before the "forward scan" strategy we
 688   // can remove both dbg.value (2) and (3) in a situation like this:
 689   //
 690   //   (1) dbg.value V1, "x", DIExpression()
 691   //       ...
 692   //   (2) dbg.value V2, "x", DIExpression()
 693   //   (3) dbg.value V1, "x", DIExpression()
 694   //
 695   // The backward scan will remove (2), it is made obsolete by (3). After
 696   // getting (2) out of the way, the foward scan will remove (3) since "x"
 697   // already is described as having the value V1 at (1).
 698   MadeChanges |= removeRedundantDbgInstrsUsingBackwardScan(BB);
 699   if (BB->isEntryBlock() &&
 700       isAssignmentTrackingEnabled(*BB->getParent()->getParent()))
 701     MadeChanges |= removeUndefDbgAssignsFromEntryBlock(BB);
 702   MadeChanges |= removeRedundantDbgInstrsUsingForwardScan(BB);
 703
 704   if (MadeChanges)
 705     LLVM_DEBUG(dbgs() << "Removed redundant dbg instrs from: "
 706                       << BB->getName() << "\n");
 707   return MadeChanges;
 708 }
 709
 710 void llvm::ReplaceInstWithValue(BasicBlock::iterator &BI, Value *V) {
 711   Instruction &I = *BI;
 712   // Replaces all of the uses of the instruction with uses of the value
 713   I.replaceAllUsesWith(V);
 714
 715   // Make sure to propagate a name if there is one already.
 716   if (I.hasName() && !V->hasName())
 717     V->takeName(&I);
 718
 719   // Delete the unnecessary instruction now...
 720   BI = BI->eraseFromParent();
 721 }
 722
 723 void llvm::ReplaceInstWithInst(BasicBlock *BB, BasicBlock::iterator &BI,
 724                                Instruction *I) {
 725   assert(I->getParent() == nullptr &&
 726          "ReplaceInstWithInst: Instruction already inserted into basic block!");
 727
 728   // Copy debug location to newly added instruction, if it wasn't already set
 729   // by the caller.
 730   if (!I->getDebugLoc())
 731     I->setDebugLoc(BI->getDebugLoc());
 732
 733   // Insert the new instruction into the basic block...
 734   BasicBlock::iterator New = I->insertInto(BB, BI);
 735
 736   // Replace all uses of the old instruction, and delete it.
 737   ReplaceInstWithValue(BI, I);
 738
 739   // Move BI back to point to the newly inserted instruction
 740   BI = New;
 741 }
 742
 743 bool llvm::IsBlockFollowedByDeoptOrUnreachable(const BasicBlock *BB) {
 744   // Remember visited blocks to avoid infinite loop
 745   SmallPtrSet<const BasicBlock *, 8> VisitedBlocks;
 746   unsigned Depth = 0;
 747   while (BB && Depth++ < MaxDeoptOrUnreachableSuccessorCheckDepth &&
 748          VisitedBlocks.insert(BB).second) {
 749     if (isa<UnreachableInst>(BB->getTerminator()) ||
 750         BB->getTerminatingDeoptimizeCall())
 751       return true;
 752     BB = BB->getUniqueSuccessor();
 753   }
 754   return false;
 755 }
 756
 757 void llvm::ReplaceInstWithInst(Instruction *From, Instruction *To) {
 758   BasicBlock::iterator BI(From);
 759   ReplaceInstWithInst(From->getParent(), BI, To);
 760 }
 761
 762 BasicBlock *llvm::SplitEdge(BasicBlock *BB, BasicBlock *Succ, DominatorTree *DT,
 763                             LoopInfo *LI, MemorySSAUpdater *MSSAU,
 764                             const Twine &BBName) {
 765   unsigned SuccNum = GetSuccessorNumber(BB, Succ);
 766
 767   Instruction *LatchTerm = BB->getTerminator();
 768
 769   CriticalEdgeSplittingOptions Options =
 770       CriticalEdgeSplittingOptions(DT, LI, MSSAU).setPreserveLCSSA();
 771
 772   if ((isCriticalEdge(LatchTerm, SuccNum, Options.MergeIdenticalEdges))) {
 773     // If it is a critical edge, and the succesor is an exception block, handle
 774     // the split edge logic in this specific function
 775     if (Succ->isEHPad())
 776       return ehAwareSplitEdge(BB, Succ, nullptr, nullptr, Options, BBName);
 777
 778     // If this is a critical edge, let SplitKnownCriticalEdge do it.
 779     return SplitKnownCriticalEdge(LatchTerm, SuccNum, Options, BBName);
 780   }
 781
 782   // If the edge isn't critical, then BB has a single successor or Succ has a
 783   // single pred.  Split the block.
 784   if (BasicBlock *SP = Succ->getSinglePredecessor()) {
 785     // If the successor only has a single pred, split the top of the successor
 786     // block.
 787     assert(SP == BB && "CFG broken");
 788     (void)SP;
 789     return SplitBlock(Succ, &Succ->front(), DT, LI, MSSAU, BBName,
 790                       /*Before=*/true);
 791   }
 792
 793   // Otherwise, if BB has a single successor, split it at the bottom of the
 794   // block.
 795   assert(BB->getTerminator()->getNumSuccessors() == 1 &&
 796          "Should have a single succ!");
 797   return SplitBlock(BB, BB->getTerminator(), DT, LI, MSSAU, BBName);
 798 }
 799
 800 void llvm::setUnwindEdgeTo(Instruction *TI, BasicBlock *Succ) {
 801   if (auto *II = dyn_cast<InvokeInst>(TI))
 802     II->setUnwindDest(Succ);
 803   else if (auto *CS = dyn_cast<CatchSwitchInst>(TI))
 804     CS->setUnwindDest(Succ);
 805   else if (auto *CR = dyn_cast<CleanupReturnInst>(TI))
 806     CR->setUnwindDest(Succ);
 807   else
 808     llvm_unreachable("unexpected terminator instruction");
 809 }
 810
 811 void llvm::updatePhiNodes(BasicBlock *DestBB, BasicBlock *OldPred,
 812                           BasicBlock *NewPred, PHINode *Until) {
 813   int BBIdx = 0;
 814   for (PHINode &PN : DestBB->phis()) {
 815     // We manually update the LandingPadReplacement PHINode and it is the last
 816     // PHI Node. So, if we find it, we are done.
 817     if (Until == &PN)
 818       break;
 819
 820     // Reuse the previous value of BBIdx if it lines up.  In cases where we
 821     // have multiple phi nodes with *lots* of predecessors, this is a speed
 822     // win because we don't have to scan the PHI looking for TIBB.  This
 823     // happens because the BB list of PHI nodes are usually in the same
 824     // order.
 825     if (PN.getIncomingBlock(BBIdx) != OldPred)
 826       BBIdx = PN.getBasicBlockIndex(OldPred);
 827
 828     assert(BBIdx != -1 && "Invalid PHI Index!");
 829     PN.setIncomingBlock(BBIdx, NewPred);
 830   }
 831 }
 832
 833 BasicBlock *llvm::ehAwareSplitEdge(BasicBlock *BB, BasicBlock *Succ,
 834                                    LandingPadInst *OriginalPad,
 835                                    PHINode *LandingPadReplacement,
 836                                    const CriticalEdgeSplittingOptions &Options,
 837                                    const Twine &BBName) {
 838
 839   auto *PadInst = Succ->getFirstNonPHI();
 840   if (!LandingPadReplacement && !PadInst->isEHPad())
 841     return SplitEdge(BB, Succ, Options.DT, Options.LI, Options.MSSAU, BBName);
 842
 843   auto *LI = Options.LI;
 844   SmallVector<BasicBlock *, 4> LoopPreds;
 845   // Check if extra modifications will be required to preserve loop-simplify
 846   // form after splitting. If it would require splitting blocks with IndirectBr
 847   // terminators, bail out if preserving loop-simplify form is requested.
 848   if (Options.PreserveLoopSimplify && LI) {
 849     if (Loop *BBLoop = LI->getLoopFor(BB)) {
 850
 851       // The only way that we can break LoopSimplify form by splitting a
 852       // critical edge is when there exists some edge from BBLoop to Succ *and*
 853       // the only edge into Succ from outside of BBLoop is that of NewBB after
 854       // the split. If the first isn't true, then LoopSimplify still holds,
 855       // NewBB is the new exit block and it has no non-loop predecessors. If the
 856       // second isn't true, then Succ was not in LoopSimplify form prior to
 857       // the split as it had a non-loop predecessor. In both of these cases,
 858       // the predecessor must be directly in BBLoop, not in a subloop, or again
 859       // LoopSimplify doesn't hold.
 860       for (BasicBlock *P : predecessors(Succ)) {
 861         if (P == BB)
 862           continue; // The new block is known.
 863         if (LI->getLoopFor(P) != BBLoop) {
 864           // Loop is not in LoopSimplify form, no need to re simplify after
 865           // splitting edge.
 866           LoopPreds.clear();
 867           break;
 868         }
 869         LoopPreds.push_back(P);
 870       }
 871       // Loop-simplify form can be preserved, if we can split all in-loop
 872       // predecessors.
 873       if (any_of(LoopPreds, [](BasicBlock *Pred) {
 874             return isa<IndirectBrInst>(Pred->getTerminator());
 875           })) {
 876         return nullptr;
 877       }
 878     }
 879   }
 880
 881   auto *NewBB =
 882       BasicBlock::Create(BB->getContext(), BBName, BB->getParent(), Succ);
 883   setUnwindEdgeTo(BB->getTerminator(), NewBB);
 884   updatePhiNodes(Succ, BB, NewBB, LandingPadReplacement);
 885
 886   if (LandingPadReplacement) {
 887     auto *NewLP = OriginalPad->clone();
 888     auto *Terminator = BranchInst::Create(Succ, NewBB);
 889     NewLP->insertBefore(Terminator);
 890     LandingPadReplacement->addIncoming(NewLP, NewBB);
 891   } else {
 892     Value *ParentPad = nullptr;
 893     if (auto *FuncletPad = dyn_cast<FuncletPadInst>(PadInst))
 894       ParentPad = FuncletPad->getParentPad();
 895     else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(PadInst))
 896       ParentPad = CatchSwitch->getParentPad();
 897     else if (auto *CleanupPad = dyn_cast<CleanupPadInst>(PadInst))
 898       ParentPad = CleanupPad->getParentPad();
 899     else if (auto *LandingPad = dyn_cast<LandingPadInst>(PadInst))
 900       ParentPad = LandingPad->getParent();
 901     else
 902       llvm_unreachable("handling for other EHPads not implemented yet");
 903
 904     auto *NewCleanupPad = CleanupPadInst::Create(ParentPad, {}, BBName, NewBB);
 905     CleanupReturnInst::Create(NewCleanupPad, Succ, NewBB);
 906   }
 907
 908   auto *DT = Options.DT;
 909   auto *MSSAU = Options.MSSAU;
 910   if (!DT && !LI)
 911     return NewBB;
 912
 913   if (DT) {
 914     DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
 915     SmallVector<DominatorTree::UpdateType, 3> Updates;
 916
 917     Updates.push_back({DominatorTree::Insert, BB, NewBB});
 918     Updates.push_back({DominatorTree::Insert, NewBB, Succ});
 919     Updates.push_back({DominatorTree::Delete, BB, Succ});
 920
 921     DTU.applyUpdates(Updates);
 922     DTU.flush();
 923
 924     if (MSSAU) {
 925       MSSAU->applyUpdates(Updates, *DT);
 926       if (VerifyMemorySSA)
 927         MSSAU->getMemorySSA()->verifyMemorySSA();
 928     }
 929   }
 930
 931   if (LI) {
 932     if (Loop *BBLoop = LI->getLoopFor(BB)) {
 933       // If one or the other blocks were not in a loop, the new block is not
 934       // either, and thus LI doesn't need to be updated.
 935       if (Loop *SuccLoop = LI->getLoopFor(Succ)) {
 936         if (BBLoop == SuccLoop) {
 937           // Both in the same loop, the NewBB joins loop.
 938           SuccLoop->addBasicBlockToLoop(NewBB, *LI);
 939         } else if (BBLoop->contains(SuccLoop)) {
 940           // Edge from an outer loop to an inner loop.  Add to the outer loop.
 941           BBLoop->addBasicBlockToLoop(NewBB, *LI);
 942         } else if (SuccLoop->contains(BBLoop)) {
 943           // Edge from an inner loop to an outer loop.  Add to the outer loop.
 944           SuccLoop->addBasicBlockToLoop(NewBB, *LI);
 945         } else {
 946           // Edge from two loops with no containment relation.  Because these
 947           // are natural loops, we know that the destination block must be the
 948           // header of its loop (adding a branch into a loop elsewhere would
 949           // create an irreducible loop).
 950           assert(SuccLoop->getHeader() == Succ &&
 951                  "Should not create irreducible loops!");
 952           if (Loop *P = SuccLoop->getParentLoop())
 953             P->addBasicBlockToLoop(NewBB, *LI);
 954         }
 955       }
 956
 957       // If BB is in a loop and Succ is outside of that loop, we may need to
 958       // update LoopSimplify form and LCSSA form.
 959       if (!BBLoop->contains(Succ)) {
 960         assert(!BBLoop->contains(NewBB) &&
 961                "Split point for loop exit is contained in loop!");
 962
 963         // Update LCSSA form in the newly created exit block.
 964         if (Options.PreserveLCSSA) {
 965           createPHIsForSplitLoopExit(BB, NewBB, Succ);
 966         }
 967
 968         if (!LoopPreds.empty()) {
 969           BasicBlock *NewExitBB = SplitBlockPredecessors(
 970               Succ, LoopPreds, "split", DT, LI, MSSAU, Options.PreserveLCSSA);
 971           if (Options.PreserveLCSSA)
 972             createPHIsForSplitLoopExit(LoopPreds, NewExitBB, Succ);
 973         }
 974       }
 975     }
 976   }
 977
 978   return NewBB;
 979 }
 980
 981 void llvm::createPHIsForSplitLoopExit(ArrayRef<BasicBlock *> Preds,
 982                                       BasicBlock *SplitBB, BasicBlock *DestBB) {
 983   // SplitBB shouldn't have anything non-trivial in it yet.
 984   assert((SplitBB->getFirstNonPHI() == SplitBB->getTerminator() ||
 985           SplitBB->isLandingPad()) &&
 986          "SplitBB has non-PHI nodes!");
 987
 988   // For each PHI in the destination block.
 989   for (PHINode &PN : DestBB->phis()) {
 990     int Idx = PN.getBasicBlockIndex(SplitBB);
 991     assert(Idx >= 0 && "Invalid Block Index");
 992     Value *V = PN.getIncomingValue(Idx);
 993
 994     // If the input is a PHI which already satisfies LCSSA, don't create
 995     // a new one.
 996     if (const PHINode *VP = dyn_cast<PHINode>(V))
 997       if (VP->getParent() == SplitBB)
 998         continue;
 999
1000     // Otherwise a new PHI is needed. Create one and populate it.
1001     PHINode *NewPN = PHINode::Create(PN.getType(), Preds.size(), "split");
1002     BasicBlock::iterator InsertPos =
1003         SplitBB->isLandingPad() ? SplitBB->begin()
1004                                 : SplitBB->getTerminator()->getIterator();
1005     NewPN->insertBefore(InsertPos);
1006     for (BasicBlock *BB : Preds)
1007       NewPN->addIncoming(V, BB);
1008
1009     // Update the original PHI.
1010     PN.setIncomingValue(Idx, NewPN);
1011   }
1012 }
1013
1014 unsigned
1015 llvm::SplitAllCriticalEdges(Function &F,
1016                             const CriticalEdgeSplittingOptions &Options) {
1017   unsigned NumBroken = 0;
1018   for (BasicBlock &BB : F) {
1019     Instruction *TI = BB.getTerminator();
1020     if (TI->getNumSuccessors() > 1 && !isa<IndirectBrInst>(TI))
1021       for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
1022         if (SplitCriticalEdge(TI, i, Options))
1023           ++NumBroken;
1024   }
1025   return NumBroken;
1026 }
1027
1028 static BasicBlock *SplitBlockImpl(BasicBlock *Old, BasicBlock::iterator SplitPt,
1029                                   DomTreeUpdater *DTU, DominatorTree *DT,
1030                                   LoopInfo *LI, MemorySSAUpdater *MSSAU,
1031                                   const Twine &BBName, bool Before) {
1032   if (Before) {
1033     DomTreeUpdater LocalDTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
1034     return splitBlockBefore(Old, SplitPt,
1035                             DTU ? DTU : (DT ? &LocalDTU : nullptr), LI, MSSAU,
1036                             BBName);
1037   }
1038   BasicBlock::iterator SplitIt = SplitPt;
1039   while (isa<PHINode>(SplitIt) || SplitIt->isEHPad()) {
1040     ++SplitIt;
1041     assert(SplitIt != SplitPt->getParent()->end());
1042   }
1043   std::string Name = BBName.str();
1044   BasicBlock *New = Old->splitBasicBlock(
1045       SplitIt, Name.empty() ? Old->getName() + ".split" : Name);
1046
1047   // The new block lives in whichever loop the old one did. This preserves
1048   // LCSSA as well, because we force the split point to be after any PHI nodes.
1049   if (LI)
1050     if (Loop *L = LI->getLoopFor(Old))
1051       L->addBasicBlockToLoop(New, *LI);
1052
1053   if (DTU) {
1054     SmallVector<DominatorTree::UpdateType, 8> Updates;
1055     // Old dominates New. New node dominates all other nodes dominated by Old.
1056     SmallPtrSet<BasicBlock *, 8> UniqueSuccessorsOfOld;
1057     Updates.push_back({DominatorTree::Insert, Old, New});
1058     Updates.reserve(Updates.size() + 2 * succ_size(New));
1059     for (BasicBlock *SuccessorOfOld : successors(New))
1060       if (UniqueSuccessorsOfOld.insert(SuccessorOfOld).second) {
1061         Updates.push_back({DominatorTree::Insert, New, SuccessorOfOld});
1062         Updates.push_back({DominatorTree::Delete, Old, SuccessorOfOld});
1063       }
1064
1065     DTU->applyUpdates(Updates);
1066   } else if (DT)
1067     // Old dominates New. New node dominates all other nodes dominated by Old.
1068     if (DomTreeNode *OldNode = DT->getNode(Old)) {
1069       std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
1070
1071       DomTreeNode *NewNode = DT->addNewBlock(New, Old);
1072       for (DomTreeNode *I : Children)
1073         DT->changeImmediateDominator(I, NewNode);
1074     }
1075
1076   // Move MemoryAccesses still tracked in Old, but part of New now.
1077   // Update accesses in successor blocks accordingly.
1078   if (MSSAU)
1079     MSSAU->moveAllAfterSpliceBlocks(Old, New, &*(New->begin()));
1080
1081   return New;
1082 }
1083
1084 BasicBlock *llvm::SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt,
1085                              DominatorTree *DT, LoopInfo *LI,
1086                              MemorySSAUpdater *MSSAU, const Twine &BBName,
1087                              bool Before) {
1088   return SplitBlockImpl(Old, SplitPt, /*DTU=*/nullptr, DT, LI, MSSAU, BBName,
1089                         Before);
1090 }
1091 BasicBlock *llvm::SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt,
1092                              DomTreeUpdater *DTU, LoopInfo *LI,
1093                              MemorySSAUpdater *MSSAU, const Twine &BBName,
1094                              bool Before) {
1095   return SplitBlockImpl(Old, SplitPt, DTU, /*DT=*/nullptr, LI, MSSAU, BBName,
1096                         Before);
1097 }
1098
1099 BasicBlock *llvm::splitBlockBefore(BasicBlock *Old, BasicBlock::iterator SplitPt,
1100                                    DomTreeUpdater *DTU, LoopInfo *LI,
1101                                    MemorySSAUpdater *MSSAU,
1102                                    const Twine &BBName) {
1103
1104   BasicBlock::iterator SplitIt = SplitPt;
1105   while (isa<PHINode>(SplitIt) || SplitIt->isEHPad())
1106     ++SplitIt;
1107   std::string Name = BBName.str();
1108   BasicBlock *New = Old->splitBasicBlock(
1109       SplitIt, Name.empty() ? Old->getName() + ".split" : Name,
1110       /* Before=*/true);
1111
1112   // The new block lives in whichever loop the old one did. This preserves
1113   // LCSSA as well, because we force the split point to be after any PHI nodes.
1114   if (LI)
1115     if (Loop *L = LI->getLoopFor(Old))
1116       L->addBasicBlockToLoop(New, *LI);
1117
1118   if (DTU) {
1119     SmallVector<DominatorTree::UpdateType, 8> DTUpdates;
1120     // New dominates Old. The predecessor nodes of the Old node dominate
1121     // New node.
1122     SmallPtrSet<BasicBlock *, 8> UniquePredecessorsOfOld;
1123     DTUpdates.push_back({DominatorTree::Insert, New, Old});
1124     DTUpdates.reserve(DTUpdates.size() + 2 * pred_size(New));
1125     for (BasicBlock *PredecessorOfOld : predecessors(New))
1126       if (UniquePredecessorsOfOld.insert(PredecessorOfOld).second) {
1127         DTUpdates.push_back({DominatorTree::Insert, PredecessorOfOld, New});
1128         DTUpdates.push_back({DominatorTree::Delete, PredecessorOfOld, Old});
1129       }
1130
1131     DTU->applyUpdates(DTUpdates);
1132
1133     // Move MemoryAccesses still tracked in Old, but part of New now.
1134     // Update accesses in successor blocks accordingly.
1135     if (MSSAU) {
1136       MSSAU->applyUpdates(DTUpdates, DTU->getDomTree());
1137       if (VerifyMemorySSA)
1138         MSSAU->getMemorySSA()->verifyMemorySSA();
1139     }
1140   }
1141   return New;
1142 }
1143
1144 /// Update DominatorTree, LoopInfo, and LCCSA analysis information.
1145 /// Invalidates DFS Numbering when DTU or DT is provided.
1146 static void UpdateAnalysisInformation(BasicBlock *OldBB, BasicBlock *NewBB,
1147                                       ArrayRef<BasicBlock *> Preds,
1148                                       DomTreeUpdater *DTU, DominatorTree *DT,
1149                                       LoopInfo *LI, MemorySSAUpdater *MSSAU,
1150                                       bool PreserveLCSSA, bool &HasLoopExit) {
1151   // Update dominator tree if available.
1152   if (DTU) {
1153     // Recalculation of DomTree is needed when updating a forward DomTree and
1154     // the Entry BB is replaced.
1155     if (NewBB->isEntryBlock() && DTU->hasDomTree()) {
1156       // The entry block was removed and there is no external interface for
1157       // the dominator tree to be notified of this change. In this corner-case
1158       // we recalculate the entire tree.
1159       DTU->recalculate(*NewBB->getParent());
1160     } else {
1161       // Split block expects NewBB to have a non-empty set of predecessors.
1162       SmallVector<DominatorTree::UpdateType, 8> Updates;
1163       SmallPtrSet<BasicBlock *, 8> UniquePreds;
1164       Updates.push_back({DominatorTree::Insert, NewBB, OldBB});
1165       Updates.reserve(Updates.size() + 2 * Preds.size());
1166       for (auto *Pred : Preds)
1167         if (UniquePreds.insert(Pred).second) {
1168           Updates.push_back({DominatorTree::Insert, Pred, NewBB});
1169           Updates.push_back({DominatorTree::Delete, Pred, OldBB});
1170         }
1171       DTU->applyUpdates(Updates);
1172     }
1173   } else if (DT) {
1174     if (OldBB == DT->getRootNode()->getBlock()) {
1175       assert(NewBB->isEntryBlock());
1176       DT->setNewRoot(NewBB);
1177     } else {
1178       // Split block expects NewBB to have a non-empty set of predecessors.
1179       DT->splitBlock(NewBB);
1180     }
1181   }
1182
1183   // Update MemoryPhis after split if MemorySSA is available
1184   if (MSSAU)
1185     MSSAU->wireOldPredecessorsToNewImmediatePredecessor(OldBB, NewBB, Preds);
1186
1187   // The rest of the logic is only relevant for updating the loop structures.
1188   if (!LI)
1189     return;
1190
1191   if (DTU && DTU->hasDomTree())
1192     DT = &DTU->getDomTree();
1193   assert(DT && "DT should be available to update LoopInfo!");
1194   Loop *L = LI->getLoopFor(OldBB);
1195
1196   // If we need to preserve loop analyses, collect some information about how
1197   // this split will affect loops.
1198   bool IsLoopEntry = !!L;
1199   bool SplitMakesNewLoopHeader = false;
1200   for (BasicBlock *Pred : Preds) {
1201     // Preds that are not reachable from entry should not be used to identify if
1202     // OldBB is a loop entry or if SplitMakesNewLoopHeader. Unreachable blocks
1203     // are not within any loops, so we incorrectly mark SplitMakesNewLoopHeader
1204     // as true and make the NewBB the header of some loop. This breaks LI.
1205     if (!DT->isReachableFromEntry(Pred))
1206       continue;
1207     // If we need to preserve LCSSA, determine if any of the preds is a loop
1208     // exit.
1209     if (PreserveLCSSA)
1210       if (Loop *PL = LI->getLoopFor(Pred))
1211         if (!PL->contains(OldBB))
1212           HasLoopExit = true;
1213
1214     // If we need to preserve LoopInfo, note whether any of the preds crosses
1215     // an interesting loop boundary.
1216     if (!L)
1217       continue;
1218     if (L->contains(Pred))
1219       IsLoopEntry = false;
1220     else
1221       SplitMakesNewLoopHeader = true;
1222   }
1223
1224   // Unless we have a loop for OldBB, nothing else to do here.
1225   if (!L)
1226     return;
1227
1228   if (IsLoopEntry) {
1229     // Add the new block to the nearest enclosing loop (and not an adjacent
1230     // loop). To find this, examine each of the predecessors and determine which
1231     // loops enclose them, and select the most-nested loop which contains the
1232     // loop containing the block being split.
1233     Loop *InnermostPredLoop = nullptr;
1234     for (BasicBlock *Pred : Preds) {
1235       if (Loop *PredLoop = LI->getLoopFor(Pred)) {
1236         // Seek a loop which actually contains the block being split (to avoid
1237         // adjacent loops).
1238         while (PredLoop && !PredLoop->contains(OldBB))
1239           PredLoop = PredLoop->getParentLoop();
1240
1241         // Select the most-nested of these loops which contains the block.
1242         if (PredLoop && PredLoop->contains(OldBB) &&
1243             (!InnermostPredLoop ||
1244              InnermostPredLoop->getLoopDepth() < PredLoop->getLoopDepth()))
1245           InnermostPredLoop = PredLoop;
1246       }
1247     }
1248
1249     if (InnermostPredLoop)
1250       InnermostPredLoop->addBasicBlockToLoop(NewBB, *LI);
1251   } else {
1252     L->addBasicBlockToLoop(NewBB, *LI);
1253     if (SplitMakesNewLoopHeader)
1254       L->moveToHeader(NewBB);
1255   }
1256 }
1257
1258 /// Update the PHI nodes in OrigBB to include the values coming from NewBB.
1259 /// This also updates AliasAnalysis, if available.
1260 static void UpdatePHINodes(BasicBlock *OrigBB, BasicBlock *NewBB,
1261                            ArrayRef<BasicBlock *> Preds, BranchInst *BI,
1262                            bool HasLoopExit) {
1263   // Otherwise, create a new PHI node in NewBB for each PHI node in OrigBB.
1264   SmallPtrSet<BasicBlock *, 16> PredSet(Preds.begin(), Preds.end());
1265   for (BasicBlock::iterator I = OrigBB->begin(); isa<PHINode>(I); ) {
1266     PHINode *PN = cast<PHINode>(I++);
1267
1268     // Check to see if all of the values coming in are the same.  If so, we
1269     // don't need to create a new PHI node, unless it's needed for LCSSA.
1270     Value *InVal = nullptr;
1271     if (!HasLoopExit) {
1272       InVal = PN->getIncomingValueForBlock(Preds[0]);
1273       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1274         if (!PredSet.count(PN->getIncomingBlock(i)))
1275           continue;
1276         if (!InVal)
1277           InVal = PN->getIncomingValue(i);
1278         else if (InVal != PN->getIncomingValue(i)) {
1279           InVal = nullptr;
1280           break;
1281         }
1282       }
1283     }
1284
1285     if (InVal) {
1286       // If all incoming values for the new PHI would be the same, just don't
1287       // make a new PHI.  Instead, just remove the incoming values from the old
1288       // PHI.
1289       PN->removeIncomingValueIf(
1290           [&](unsigned Idx) {
1291             return PredSet.contains(PN->getIncomingBlock(Idx));
1292           },
1293           /* DeletePHIIfEmpty */ false);
1294
1295       // Add an incoming value to the PHI node in the loop for the preheader
1296       // edge.
1297       PN->addIncoming(InVal, NewBB);
1298       continue;
1299     }
1300
1301     // If the values coming into the block are not the same, we need a new
1302     // PHI.
1303     // Create the new PHI node, insert it into NewBB at the end of the block
1304     PHINode *NewPHI =
1305         PHINode::Create(PN->getType(), Preds.size(), PN->getName() + ".ph", BI->getIterator());
1306
1307     // NOTE! This loop walks backwards for a reason! First off, this minimizes
1308     // the cost of removal if we end up removing a large number of values, and
1309     // second off, this ensures that the indices for the incoming values aren't
1310     // invalidated when we remove one.
1311     for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i) {
1312       BasicBlock *IncomingBB = PN->getIncomingBlock(i);
1313       if (PredSet.count(IncomingBB)) {
1314         Value *V = PN->removeIncomingValue(i, false);
1315         NewPHI->addIncoming(V, IncomingBB);
1316       }
1317     }
1318
1319     PN->addIncoming(NewPHI, NewBB);
1320   }
1321 }
1322
1323 static void SplitLandingPadPredecessorsImpl(
1324     BasicBlock *OrigBB, ArrayRef<BasicBlock *> Preds, const char *Suffix1,
1325     const char *Suffix2, SmallVectorImpl<BasicBlock *> &NewBBs,
1326     DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI,
1327     MemorySSAUpdater *MSSAU, bool PreserveLCSSA);
1328
1329 static BasicBlock *
1330 SplitBlockPredecessorsImpl(BasicBlock *BB, ArrayRef<BasicBlock *> Preds,
1331                            const char *Suffix, DomTreeUpdater *DTU,
1332                            DominatorTree *DT, LoopInfo *LI,
1333                            MemorySSAUpdater *MSSAU, bool PreserveLCSSA) {
1334   // Do not attempt to split that which cannot be split.
1335   if (!BB->canSplitPredecessors())
1336     return nullptr;
1337
1338   // For the landingpads we need to act a bit differently.
1339   // Delegate this work to the SplitLandingPadPredecessors.
1340   if (BB->isLandingPad()) {
1341     SmallVector<BasicBlock*, 2> NewBBs;
1342     std::string NewName = std::string(Suffix) + ".split-lp";
1343
1344     SplitLandingPadPredecessorsImpl(BB, Preds, Suffix, NewName.c_str(), NewBBs,
1345                                     DTU, DT, LI, MSSAU, PreserveLCSSA);
1346     return NewBBs[0];
1347   }
1348
1349   // Create new basic block, insert right before the original block.
1350   BasicBlock *NewBB = BasicBlock::Create(
1351       BB->getContext(), BB->getName() + Suffix, BB->getParent(), BB);
1352
1353   // The new block unconditionally branches to the old block.
1354   BranchInst *BI = BranchInst::Create(BB, NewBB);
1355
1356   Loop *L = nullptr;
1357   BasicBlock *OldLatch = nullptr;
1358   // Splitting the predecessors of a loop header creates a preheader block.
1359   if (LI && LI->isLoopHeader(BB)) {
1360     L = LI->getLoopFor(BB);
1361     // Using the loop start line number prevents debuggers stepping into the
1362     // loop body for this instruction.
1363     BI->setDebugLoc(L->getStartLoc());
1364
1365     // If BB is the header of the Loop, it is possible that the loop is
1366     // modified, such that the current latch does not remain the latch of the
1367     // loop. If that is the case, the loop metadata from the current latch needs
1368     // to be applied to the new latch.
1369     OldLatch = L->getLoopLatch();
1370   } else
1371     BI->setDebugLoc(BB->getFirstNonPHIOrDbg()->getDebugLoc());
1372
1373   // Move the edges from Preds to point to NewBB instead of BB.
1374   for (BasicBlock *Pred : Preds) {
1375     // This is slightly more strict than necessary; the minimum requirement
1376     // is that there be no more than one indirectbr branching to BB. And
1377     // all BlockAddress uses would need to be updated.
1378     assert(!isa<IndirectBrInst>(Pred->getTerminator()) &&
1379            "Cannot split an edge from an IndirectBrInst");
1380     Pred->getTerminator()->replaceSuccessorWith(BB, NewBB);
1381   }
1382
1383   // Insert a new PHI node into NewBB for every PHI node in BB and that new PHI
1384   // node becomes an incoming value for BB's phi node.  However, if the Preds
1385   // list is empty, we need to insert dummy entries into the PHI nodes in BB to
1386   // account for the newly created predecessor.
1387   if (Preds.empty()) {
1388     // Insert dummy values as the incoming value.
1389     for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I)
1390       cast<PHINode>(I)->addIncoming(PoisonValue::get(I->getType()), NewBB);
1391   }
1392
1393   // Update DominatorTree, LoopInfo, and LCCSA analysis information.
1394   bool HasLoopExit = false;
1395   UpdateAnalysisInformation(BB, NewBB, Preds, DTU, DT, LI, MSSAU, PreserveLCSSA,
1396                             HasLoopExit);
1397
1398   if (!Preds.empty()) {
1399     // Update the PHI nodes in BB with the values coming from NewBB.
1400     UpdatePHINodes(BB, NewBB, Preds, BI, HasLoopExit);
1401   }
1402
1403   if (OldLatch) {
1404     BasicBlock *NewLatch = L->getLoopLatch();
1405     if (NewLatch != OldLatch) {
1406       MDNode *MD = OldLatch->getTerminator()->getMetadata(LLVMContext::MD_loop);
1407       NewLatch->getTerminator()->setMetadata(LLVMContext::MD_loop, MD);
1408       // It's still possible that OldLatch is the latch of another inner loop,
1409       // in which case we do not remove the metadata.
1410       Loop *IL = LI->getLoopFor(OldLatch);
1411       if (IL && IL->getLoopLatch() != OldLatch)
1412         OldLatch->getTerminator()->setMetadata(LLVMContext::MD_loop, nullptr);
1413     }
1414   }
1415
1416   return NewBB;
1417 }
1418
1419 BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB,
1420                                          ArrayRef<BasicBlock *> Preds,
1421                                          const char *Suffix, DominatorTree *DT,
1422                                          LoopInfo *LI, MemorySSAUpdater *MSSAU,
1423                                          bool PreserveLCSSA) {
1424   return SplitBlockPredecessorsImpl(BB, Preds, Suffix, /*DTU=*/nullptr, DT, LI,
1425                                     MSSAU, PreserveLCSSA);
1426 }
1427 BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB,
1428                                          ArrayRef<BasicBlock *> Preds,
1429                                          const char *Suffix,
1430                                          DomTreeUpdater *DTU, LoopInfo *LI,
1431                                          MemorySSAUpdater *MSSAU,
1432                                          bool PreserveLCSSA) {
1433   return SplitBlockPredecessorsImpl(BB, Preds, Suffix, DTU,
1434                                     /*DT=*/nullptr, LI, MSSAU, PreserveLCSSA);
1435 }
1436
1437 static void SplitLandingPadPredecessorsImpl(
1438     BasicBlock *OrigBB, ArrayRef<BasicBlock *> Preds, const char *Suffix1,
1439     const char *Suffix2, SmallVectorImpl<BasicBlock *> &NewBBs,
1440     DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI,
1441     MemorySSAUpdater *MSSAU, bool PreserveLCSSA) {
1442   assert(OrigBB->isLandingPad() && "Trying to split a non-landing pad!");
1443
1444   // Create a new basic block for OrigBB's predecessors listed in Preds. Insert
1445   // it right before the original block.
1446   BasicBlock *NewBB1 = BasicBlock::Create(OrigBB->getContext(),
1447                                           OrigBB->getName() + Suffix1,
1448                                           OrigBB->getParent(), OrigBB);
1449   NewBBs.push_back(NewBB1);
1450
1451   // The new block unconditionally branches to the old block.
1452   BranchInst *BI1 = BranchInst::Create(OrigBB, NewBB1);
1453   BI1->setDebugLoc(OrigBB->getFirstNonPHI()->getDebugLoc());
1454
1455   // Move the edges from Preds to point to NewBB1 instead of OrigBB.
1456   for (BasicBlock *Pred : Preds) {
1457     // This is slightly more strict than necessary; the minimum requirement
1458     // is that there be no more than one indirectbr branching to BB. And
1459     // all BlockAddress uses would need to be updated.
1460     assert(!isa<IndirectBrInst>(Pred->getTerminator()) &&
1461            "Cannot split an edge from an IndirectBrInst");
1462     Pred->getTerminator()->replaceUsesOfWith(OrigBB, NewBB1);
1463   }
1464
1465   bool HasLoopExit = false;
1466   UpdateAnalysisInformation(OrigBB, NewBB1, Preds, DTU, DT, LI, MSSAU,
1467                             PreserveLCSSA, HasLoopExit);
1468
1469   // Update the PHI nodes in OrigBB with the values coming from NewBB1.
1470   UpdatePHINodes(OrigBB, NewBB1, Preds, BI1, HasLoopExit);
1471
1472   // Move the remaining edges from OrigBB to point to NewBB2.
1473   SmallVector<BasicBlock*, 8> NewBB2Preds;
1474   for (pred_iterator i = pred_begin(OrigBB), e = pred_end(OrigBB);
1475        i != e; ) {
1476     BasicBlock *Pred = *i++;
1477     if (Pred == NewBB1) continue;
1478     assert(!isa<IndirectBrInst>(Pred->getTerminator()) &&
1479            "Cannot split an edge from an IndirectBrInst");
1480     NewBB2Preds.push_back(Pred);
1481     e = pred_end(OrigBB);
1482   }
1483
1484   BasicBlock *NewBB2 = nullptr;
1485   if (!NewBB2Preds.empty()) {
1486     // Create another basic block for the rest of OrigBB's predecessors.
1487     NewBB2 = BasicBlock::Create(OrigBB->getContext(),
1488                                 OrigBB->getName() + Suffix2,
1489                                 OrigBB->getParent(), OrigBB);
1490     NewBBs.push_back(NewBB2);
1491
1492     // The new block unconditionally branches to the old block.
1493     BranchInst *BI2 = BranchInst::Create(OrigBB, NewBB2);
1494     BI2->setDebugLoc(OrigBB->getFirstNonPHI()->getDebugLoc());
1495
1496     // Move the remaining edges from OrigBB to point to NewBB2.
1497     for (BasicBlock *NewBB2Pred : NewBB2Preds)
1498       NewBB2Pred->getTerminator()->replaceUsesOfWith(OrigBB, NewBB2);
1499
1500     // Update DominatorTree, LoopInfo, and LCCSA analysis information.
1501     HasLoopExit = false;
1502     UpdateAnalysisInformation(OrigBB, NewBB2, NewBB2Preds, DTU, DT, LI, MSSAU,
1503                               PreserveLCSSA, HasLoopExit);
1504
1505     // Update the PHI nodes in OrigBB with the values coming from NewBB2.
1506     UpdatePHINodes(OrigBB, NewBB2, NewBB2Preds, BI2, HasLoopExit);
1507   }
1508
1509   LandingPadInst *LPad = OrigBB->getLandingPadInst();
1510   Instruction *Clone1 = LPad->clone();
1511   Clone1->setName(Twine("lpad") + Suffix1);
1512   Clone1->insertInto(NewBB1, NewBB1->getFirstInsertionPt());
1513
1514   if (NewBB2) {
1515     Instruction *Clone2 = LPad->clone();
1516     Clone2->setName(Twine("lpad") + Suffix2);
1517     Clone2->insertInto(NewBB2, NewBB2->getFirstInsertionPt());
1518
1519     // Create a PHI node for the two cloned landingpad instructions only
1520     // if the original landingpad instruction has some uses.
1521     if (!LPad->use_empty()) {
1522       assert(!LPad->getType()->isTokenTy() &&
1523              "Split cannot be applied if LPad is token type. Otherwise an "
1524              "invalid PHINode of token type would be created.");
1525       PHINode *PN = PHINode::Create(LPad->getType(), 2, "lpad.phi", LPad->getIterator());
1526       PN->addIncoming(Clone1, NewBB1);
1527       PN->addIncoming(Clone2, NewBB2);
1528       LPad->replaceAllUsesWith(PN);
1529     }
1530     LPad->eraseFromParent();
1531   } else {
1532     // There is no second clone. Just replace the landing pad with the first
1533     // clone.
1534     LPad->replaceAllUsesWith(Clone1);
1535     LPad->eraseFromParent();
1536   }
1537 }
1538
1539 void llvm::SplitLandingPadPredecessors(BasicBlock *OrigBB,
1540                                        ArrayRef<BasicBlock *> Preds,
1541                                        const char *Suffix1, const char *Suffix2,
1542                                        SmallVectorImpl<BasicBlock *> &NewBBs,
1543                                        DomTreeUpdater *DTU, LoopInfo *LI,
1544                                        MemorySSAUpdater *MSSAU,
1545                                        bool PreserveLCSSA) {
1546   return SplitLandingPadPredecessorsImpl(OrigBB, Preds, Suffix1, Suffix2,
1547                                          NewBBs, DTU, /*DT=*/nullptr, LI, MSSAU,
1548                                          PreserveLCSSA);
1549 }
1550
1551 ReturnInst *llvm::FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB,
1552                                              BasicBlock *Pred,
1553                                              DomTreeUpdater *DTU) {
1554   Instruction *UncondBranch = Pred->getTerminator();
1555   // Clone the return and add it to the end of the predecessor.
1556   Instruction *NewRet = RI->clone();
1557   NewRet->insertInto(Pred, Pred->end());
1558
1559   // If the return instruction returns a value, and if the value was a
1560   // PHI node in "BB", propagate the right value into the return.
1561   for (Use &Op : NewRet->operands()) {
1562     Value *V = Op;
1563     Instruction *NewBC = nullptr;
1564     if (BitCastInst *BCI = dyn_cast<BitCastInst>(V)) {
1565       // Return value might be bitcasted. Clone and insert it before the
1566       // return instruction.
1567       V = BCI->getOperand(0);
1568       NewBC = BCI->clone();
1569       NewBC->insertInto(Pred, NewRet->getIterator());
1570       Op = NewBC;
1571     }
1572
1573     Instruction *NewEV = nullptr;
1574     if (ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(V)) {
1575       V = EVI->getOperand(0);
1576       NewEV = EVI->clone();
1577       if (NewBC) {
1578         NewBC->setOperand(0, NewEV);
1579         NewEV->insertInto(Pred, NewBC->getIterator());
1580       } else {
1581         NewEV->insertInto(Pred, NewRet->getIterator());
1582         Op = NewEV;
1583       }
1584     }
1585
1586     if (PHINode *PN = dyn_cast<PHINode>(V)) {
1587       if (PN->getParent() == BB) {
1588         if (NewEV) {
1589           NewEV->setOperand(0, PN->getIncomingValueForBlock(Pred));
1590         } else if (NewBC)
1591           NewBC->setOperand(0, PN->getIncomingValueForBlock(Pred));
1592         else
1593           Op = PN->getIncomingValueForBlock(Pred);
1594       }
1595     }
1596   }
1597
1598   // Update any PHI nodes in the returning block to realize that we no
1599   // longer branch to them.
1600   BB->removePredecessor(Pred);
1601   UncondBranch->eraseFromParent();
1602
1603   if (DTU)
1604     DTU->applyUpdates({{DominatorTree::Delete, Pred, BB}});
1605
1606   return cast<ReturnInst>(NewRet);
1607 }
1608
1609 Instruction *llvm::SplitBlockAndInsertIfThen(Value *Cond,
1610                                              BasicBlock::iterator SplitBefore,
1611                                              bool Unreachable,
1612                                              MDNode *BranchWeights,
1613                                              DomTreeUpdater *DTU, LoopInfo *LI,
1614                                              BasicBlock *ThenBlock) {
1615   SplitBlockAndInsertIfThenElse(
1616       Cond, SplitBefore, &ThenBlock, /* ElseBlock */ nullptr,
1617       /* UnreachableThen */ Unreachable,
1618       /* UnreachableElse */ false, BranchWeights, DTU, LI);
1619   return ThenBlock->getTerminator();
1620 }
1621
1622 Instruction *llvm::SplitBlockAndInsertIfElse(Value *Cond,
1623                                              BasicBlock::iterator SplitBefore,
1624                                              bool Unreachable,
1625                                              MDNode *BranchWeights,
1626                                              DomTreeUpdater *DTU, LoopInfo *LI,
1627                                              BasicBlock *ElseBlock) {
1628   SplitBlockAndInsertIfThenElse(
1629       Cond, SplitBefore, /* ThenBlock */ nullptr, &ElseBlock,
1630       /* UnreachableThen */ false,
1631       /* UnreachableElse */ Unreachable, BranchWeights, DTU, LI);
1632   return ElseBlock->getTerminator();
1633 }
1634
1635 void llvm::SplitBlockAndInsertIfThenElse(Value *Cond, BasicBlock::iterator SplitBefore,
1636                                          Instruction **ThenTerm,
1637                                          Instruction **ElseTerm,
1638                                          MDNode *BranchWeights,
1639                                          DomTreeUpdater *DTU, LoopInfo *LI) {
1640   BasicBlock *ThenBlock = nullptr;
1641   BasicBlock *ElseBlock = nullptr;
1642   SplitBlockAndInsertIfThenElse(
1643       Cond, SplitBefore, &ThenBlock, &ElseBlock, /* UnreachableThen */ false,
1644       /* UnreachableElse */ false, BranchWeights, DTU, LI);
1645
1646   *ThenTerm = ThenBlock->getTerminator();
1647   *ElseTerm = ElseBlock->getTerminator();
1648 }
1649
1650 void llvm::SplitBlockAndInsertIfThenElse(
1651     Value *Cond, BasicBlock::iterator SplitBefore, BasicBlock **ThenBlock,
1652     BasicBlock **ElseBlock, bool UnreachableThen, bool UnreachableElse,
1653     MDNode *BranchWeights, DomTreeUpdater *DTU, LoopInfo *LI) {
1654   assert((ThenBlock || ElseBlock) &&
1655          "At least one branch block must be created");
1656   assert((!UnreachableThen || !UnreachableElse) &&
1657          "Split block tail must be reachable");
1658
1659   SmallVector<DominatorTree::UpdateType, 8> Updates;
1660   SmallPtrSet<BasicBlock *, 8> UniqueOrigSuccessors;
1661   BasicBlock *Head = SplitBefore->getParent();
1662   if (DTU) {
1663     UniqueOrigSuccessors.insert(succ_begin(Head), succ_end(Head));
1664     Updates.reserve(4 + 2 * UniqueOrigSuccessors.size());
1665   }
1666
1667   LLVMContext &C = Head->getContext();
1668   BasicBlock *Tail = Head->splitBasicBlock(SplitBefore);
1669   BasicBlock *TrueBlock = Tail;
1670   BasicBlock *FalseBlock = Tail;
1671   bool ThenToTailEdge = false;
1672   bool ElseToTailEdge = false;
1673
1674   // Encapsulate the logic around creation/insertion/etc of a new block.
1675   auto handleBlock = [&](BasicBlock **PBB, bool Unreachable, BasicBlock *&BB,
1676                          bool &ToTailEdge) {
1677     if (PBB == nullptr)
1678       return; // Do not create/insert a block.
1679
1680     if (*PBB)
1681       BB = *PBB; // Caller supplied block, use it.
1682     else {
1683       // Create a new block.
1684       BB = BasicBlock::Create(C, "", Head->getParent(), Tail);
1685       if (Unreachable)
1686         (void)new UnreachableInst(C, BB);
1687       else {
1688         (void)BranchInst::Create(Tail, BB);
1689         ToTailEdge = true;
1690       }
1691       BB->getTerminator()->setDebugLoc(SplitBefore->getDebugLoc());
1692       // Pass the new block back to the caller.
1693       *PBB = BB;
1694     }
1695   };
1696
1697   handleBlock(ThenBlock, UnreachableThen, TrueBlock, ThenToTailEdge);
1698   handleBlock(ElseBlock, UnreachableElse, FalseBlock, ElseToTailEdge);
1699
1700   Instruction *HeadOldTerm = Head->getTerminator();
1701   BranchInst *HeadNewTerm =
1702       BranchInst::Create(/*ifTrue*/ TrueBlock, /*ifFalse*/ FalseBlock, Cond);
1703   HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);
1704   ReplaceInstWithInst(HeadOldTerm, HeadNewTerm);
1705
1706   if (DTU) {
1707     Updates.emplace_back(DominatorTree::Insert, Head, TrueBlock);
1708     Updates.emplace_back(DominatorTree::Insert, Head, FalseBlock);
1709     if (ThenToTailEdge)
1710       Updates.emplace_back(DominatorTree::Insert, TrueBlock, Tail);
1711     if (ElseToTailEdge)
1712       Updates.emplace_back(DominatorTree::Insert, FalseBlock, Tail);
1713     for (BasicBlock *UniqueOrigSuccessor : UniqueOrigSuccessors)
1714       Updates.emplace_back(DominatorTree::Insert, Tail, UniqueOrigSuccessor);
1715     for (BasicBlock *UniqueOrigSuccessor : UniqueOrigSuccessors)
1716       Updates.emplace_back(DominatorTree::Delete, Head, UniqueOrigSuccessor);
1717     DTU->applyUpdates(Updates);
1718   }
1719
1720   if (LI) {
1721     if (Loop *L = LI->getLoopFor(Head); L) {
1722       if (ThenToTailEdge)
1723         L->addBasicBlockToLoop(TrueBlock, *LI);
1724       if (ElseToTailEdge)
1725         L->addBasicBlockToLoop(FalseBlock, *LI);
1726       L->addBasicBlockToLoop(Tail, *LI);
1727     }
1728   }
1729 }
1730
1731 std::pair<Instruction*, Value*>
1732 llvm::SplitBlockAndInsertSimpleForLoop(Value *End, Instruction *SplitBefore) {
1733   BasicBlock *LoopPred = SplitBefore->getParent();
1734   BasicBlock *LoopBody = SplitBlock(SplitBefore->getParent(), SplitBefore);
1735   BasicBlock *LoopExit = SplitBlock(SplitBefore->getParent(), SplitBefore);
1736
1737   auto *Ty = End->getType();
1738   auto &DL = SplitBefore->getDataLayout();
1739   const unsigned Bitwidth = DL.getTypeSizeInBits(Ty);
1740
1741   IRBuilder<> Builder(LoopBody->getTerminator());
1742   auto *IV = Builder.CreatePHI(Ty, 2, "iv");
1743   auto *IVNext =
1744     Builder.CreateAdd(IV, ConstantInt::get(Ty, 1), IV->getName() + ".next",
1745                       /*HasNUW=*/true, /*HasNSW=*/Bitwidth != 2);
1746   auto *IVCheck = Builder.CreateICmpEQ(IVNext, End,
1747                                        IV->getName() + ".check");
1748   Builder.CreateCondBr(IVCheck, LoopExit, LoopBody);
1749   LoopBody->getTerminator()->eraseFromParent();
1750
1751   // Populate the IV PHI.
1752   IV->addIncoming(ConstantInt::get(Ty, 0), LoopPred);
1753   IV->addIncoming(IVNext, LoopBody);
1754
1755   return std::make_pair(LoopBody->getFirstNonPHI(), IV);
1756 }
1757
1758 void llvm::SplitBlockAndInsertForEachLane(ElementCount EC,
1759      Type *IndexTy, Instruction *InsertBefore,
1760      std::function<void(IRBuilderBase&, Value*)> Func) {
1761
1762   IRBuilder<> IRB(InsertBefore);
1763
1764   if (EC.isScalable()) {
1765     Value *NumElements = IRB.CreateElementCount(IndexTy, EC);
1766
1767     auto [BodyIP, Index] =
1768       SplitBlockAndInsertSimpleForLoop(NumElements, InsertBefore);
1769
1770     IRB.SetInsertPoint(BodyIP);
1771     Func(IRB, Index);
1772     return;
1773   }
1774
1775   unsigned Num = EC.getFixedValue();
1776   for (unsigned Idx = 0; Idx < Num; ++Idx) {
1777     IRB.SetInsertPoint(InsertBefore);
1778     Func(IRB, ConstantInt::get(IndexTy, Idx));
1779   }
1780 }
1781
1782 void llvm::SplitBlockAndInsertForEachLane(
1783     Value *EVL, Instruction *InsertBefore,
1784     std::function<void(IRBuilderBase &, Value *)> Func) {
1785
1786   IRBuilder<> IRB(InsertBefore);
1787   Type *Ty = EVL->getType();
1788
1789   if (!isa<ConstantInt>(EVL)) {
1790     auto [BodyIP, Index] = SplitBlockAndInsertSimpleForLoop(EVL, InsertBefore);
1791     IRB.SetInsertPoint(BodyIP);
1792     Func(IRB, Index);
1793     return;
1794   }
1795
1796   unsigned Num = cast<ConstantInt>(EVL)->getZExtValue();
1797   for (unsigned Idx = 0; Idx < Num; ++Idx) {
1798     IRB.SetInsertPoint(InsertBefore);
1799     Func(IRB, ConstantInt::get(Ty, Idx));
1800   }
1801 }
1802
1803 BranchInst *llvm::GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue,
1804                                  BasicBlock *&IfFalse) {
1805   PHINode *SomePHI = dyn_cast<PHINode>(BB->begin());
1806   BasicBlock *Pred1 = nullptr;
1807   BasicBlock *Pred2 = nullptr;
1808
1809   if (SomePHI) {
1810     if (SomePHI->getNumIncomingValues() != 2)
1811       return nullptr;
1812     Pred1 = SomePHI->getIncomingBlock(0);
1813     Pred2 = SomePHI->getIncomingBlock(1);
1814   } else {
1815     pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1816     if (PI == PE) // No predecessor
1817       return nullptr;
1818     Pred1 = *PI++;
1819     if (PI == PE) // Only one predecessor
1820       return nullptr;
1821     Pred2 = *PI++;
1822     if (PI != PE) // More than two predecessors
1823       return nullptr;
1824   }
1825
1826   // We can only handle branches.  Other control flow will be lowered to
1827   // branches if possible anyway.
1828   BranchInst *Pred1Br = dyn_cast<BranchInst>(Pred1->getTerminator());
1829   BranchInst *Pred2Br = dyn_cast<BranchInst>(Pred2->getTerminator());
1830   if (!Pred1Br || !Pred2Br)
1831     return nullptr;
1832
1833   // Eliminate code duplication by ensuring that Pred1Br is conditional if
1834   // either are.
1835   if (Pred2Br->isConditional()) {
1836     // If both branches are conditional, we don't have an "if statement".  In
1837     // reality, we could transform this case, but since the condition will be
1838     // required anyway, we stand no chance of eliminating it, so the xform is
1839     // probably not profitable.
1840     if (Pred1Br->isConditional())
1841       return nullptr;
1842
1843     std::swap(Pred1, Pred2);
1844     std::swap(Pred1Br, Pred2Br);
1845   }
1846
1847   if (Pred1Br->isConditional()) {
1848     // The only thing we have to watch out for here is to make sure that Pred2
1849     // doesn't have incoming edges from other blocks.  If it does, the condition
1850     // doesn't dominate BB.
1851     if (!Pred2->getSinglePredecessor())
1852       return nullptr;
1853
1854     // If we found a conditional branch predecessor, make sure that it branches
1855     // to BB and Pred2Br.  If it doesn't, this isn't an "if statement".
1856     if (Pred1Br->getSuccessor(0) == BB &&
1857         Pred1Br->getSuccessor(1) == Pred2) {
1858       IfTrue = Pred1;
1859       IfFalse = Pred2;
1860     } else if (Pred1Br->getSuccessor(0) == Pred2 &&
1861                Pred1Br->getSuccessor(1) == BB) {
1862       IfTrue = Pred2;
1863       IfFalse = Pred1;
1864     } else {
1865       // We know that one arm of the conditional goes to BB, so the other must
1866       // go somewhere unrelated, and this must not be an "if statement".
1867       return nullptr;
1868     }
1869
1870     return Pred1Br;
1871   }
1872
1873   // Ok, if we got here, both predecessors end with an unconditional branch to
1874   // BB.  Don't panic!  If both blocks only have a single (identical)
1875   // predecessor, and THAT is a conditional branch, then we're all ok!
1876   BasicBlock *CommonPred = Pred1->getSinglePredecessor();
1877   if (CommonPred == nullptr || CommonPred != Pred2->getSinglePredecessor())
1878     return nullptr;
1879
1880   // Otherwise, if this is a conditional branch, then we can use it!
1881   BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator());
1882   if (!BI) return nullptr;
1883
1884   assert(BI->isConditional() && "Two successors but not conditional?");
1885   if (BI->getSuccessor(0) == Pred1) {
1886     IfTrue = Pred1;
1887     IfFalse = Pred2;
1888   } else {
1889     IfTrue = Pred2;
1890     IfFalse = Pred1;
1891   }
1892   return BI;
1893 }
1894
1895 void llvm::InvertBranch(BranchInst *PBI, IRBuilderBase &Builder) {
1896   Value *NewCond = PBI->getCondition();
1897   // If this is a "cmp" instruction, only used for branching (and nowhere
1898   // else), then we can simply invert the predicate.
1899   if (NewCond->hasOneUse() && isa<CmpInst>(NewCond)) {
1900     CmpInst *CI = cast<CmpInst>(NewCond);
1901     CI->setPredicate(CI->getInversePredicate());
1902   } else
1903     NewCond = Builder.CreateNot(NewCond, NewCond->getName() + ".not");
1904
1905   PBI->setCondition(NewCond);
1906   PBI->swapSuccessors();
1907 }
1908
1909 bool llvm::hasOnlySimpleTerminator(const Function &F) {
1910   for (auto &BB : F) {
1911     auto *Term = BB.getTerminator();
1912     if (!(isa<ReturnInst>(Term) || isa<UnreachableInst>(Term) ||
1913           isa<BranchInst>(Term)))
1914       return false;
1915   }
1916   return true;
1917 }
1918
1919 bool llvm::isPresplitCoroSuspendExitEdge(const BasicBlock &Src,
1920                                          const BasicBlock &Dest) {
1921   assert(Src.getParent() == Dest.getParent());
1922   if (!Src.getParent()->isPresplitCoroutine())
1923     return false;
1924   if (auto *SW = dyn_cast<SwitchInst>(Src.getTerminator()))
1925     if (auto *Intr = dyn_cast<IntrinsicInst>(SW->getCondition()))
1926       return Intr->getIntrinsicID() == Intrinsic::coro_suspend &&
1927              SW->getDefaultDest() == &Dest;
1928   return false;
1929 }