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