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