xref: /llvm-project/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp (revision bf7190a15470adb31f8df08aa9d61bb2861e7d54)
1 //===- SimpleLoopUnswitch.cpp - Hoist loop-invariant control flow ---------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "llvm/Transforms/Scalar/SimpleLoopUnswitch.h"
11 #include "llvm/ADT/DenseMap.h"
12 #include "llvm/ADT/STLExtras.h"
13 #include "llvm/ADT/Sequence.h"
14 #include "llvm/ADT/SetVector.h"
15 #include "llvm/ADT/SmallPtrSet.h"
16 #include "llvm/ADT/SmallVector.h"
17 #include "llvm/ADT/Statistic.h"
18 #include "llvm/ADT/Twine.h"
19 #include "llvm/Analysis/AssumptionCache.h"
20 #include "llvm/Analysis/CFG.h"
21 #include "llvm/Analysis/CodeMetrics.h"
22 #include "llvm/Analysis/LoopAnalysisManager.h"
23 #include "llvm/Analysis/LoopInfo.h"
24 #include "llvm/Analysis/LoopIterator.h"
25 #include "llvm/Analysis/LoopPass.h"
26 #include "llvm/IR/BasicBlock.h"
27 #include "llvm/IR/Constant.h"
28 #include "llvm/IR/Constants.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/Use.h"
36 #include "llvm/IR/Value.h"
37 #include "llvm/Pass.h"
38 #include "llvm/Support/Casting.h"
39 #include "llvm/Support/Debug.h"
40 #include "llvm/Support/ErrorHandling.h"
41 #include "llvm/Support/GenericDomTree.h"
42 #include "llvm/Support/raw_ostream.h"
43 #include "llvm/Transforms/Scalar/SimpleLoopUnswitch.h"
44 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
45 #include "llvm/Transforms/Utils/Cloning.h"
46 #include "llvm/Transforms/Utils/LoopUtils.h"
47 #include "llvm/Transforms/Utils/ValueMapper.h"
48 #include <algorithm>
49 #include <cassert>
50 #include <iterator>
51 #include <numeric>
52 #include <utility>
53 
54 #define DEBUG_TYPE "simple-loop-unswitch"
55 
56 using namespace llvm;
57 
58 STATISTIC(NumBranches, "Number of branches unswitched");
59 STATISTIC(NumSwitches, "Number of switches unswitched");
60 STATISTIC(NumTrivial, "Number of unswitches that are trivial");
61 
62 static cl::opt<bool> EnableNonTrivialUnswitch(
63     "enable-nontrivial-unswitch", cl::init(false), cl::Hidden,
64     cl::desc("Forcibly enables non-trivial loop unswitching rather than "
65              "following the configuration passed into the pass."));
66 
67 static cl::opt<int>
68     UnswitchThreshold("unswitch-threshold", cl::init(50), cl::Hidden,
69                       cl::desc("The cost threshold for unswitching a loop."));
70 
71 static void replaceLoopUsesWithConstant(Loop &L, Value &LIC,
72                                         Constant &Replacement) {
73   assert(!isa<Constant>(LIC) && "Why are we unswitching on a constant?");
74 
75   // Replace uses of LIC in the loop with the given constant.
76   for (auto UI = LIC.use_begin(), UE = LIC.use_end(); UI != UE;) {
77     // Grab the use and walk past it so we can clobber it in the use list.
78     Use *U = &*UI++;
79     Instruction *UserI = dyn_cast<Instruction>(U->getUser());
80     if (!UserI || !L.contains(UserI))
81       continue;
82 
83     // Replace this use within the loop body.
84     *U = &Replacement;
85   }
86 }
87 
88 /// Update the IDom for a basic block whose predecessor set has changed.
89 ///
90 /// This routine is designed to work when the domtree update is relatively
91 /// localized by leveraging a known common dominator, often a loop header.
92 ///
93 /// FIXME: Should consider hand-rolling a slightly more efficient non-DFS
94 /// approach here as we can do that easily by persisting the candidate IDom's
95 /// dominating set between each predecessor.
96 ///
97 /// FIXME: Longer term, many uses of this can be replaced by an incremental
98 /// domtree update strategy that starts from a known dominating block and
99 /// rebuilds that subtree.
100 static bool updateIDomWithKnownCommonDominator(BasicBlock *BB,
101                                                BasicBlock *KnownDominatingBB,
102                                                DominatorTree &DT) {
103   assert(pred_begin(BB) != pred_end(BB) &&
104          "This routine does not handle unreachable blocks!");
105 
106   BasicBlock *OrigIDom = DT[BB]->getIDom()->getBlock();
107 
108   BasicBlock *IDom = *pred_begin(BB);
109   assert(DT.dominates(KnownDominatingBB, IDom) &&
110          "Bad known dominating block!");
111 
112   // Walk all of the other predecessors finding the nearest common dominator
113   // until all predecessors are covered or we reach the loop header. The loop
114   // header necessarily dominates all loop exit blocks in loop simplified form
115   // so we can early-exit the moment we hit that block.
116   for (auto PI = std::next(pred_begin(BB)), PE = pred_end(BB);
117        PI != PE && IDom != KnownDominatingBB; ++PI) {
118     assert(DT.dominates(KnownDominatingBB, *PI) &&
119            "Bad known dominating block!");
120     IDom = DT.findNearestCommonDominator(IDom, *PI);
121   }
122 
123   if (IDom == OrigIDom)
124     return false;
125 
126   DT.changeImmediateDominator(BB, IDom);
127   return true;
128 }
129 
130 // Note that we don't currently use the IDFCalculator here for two reasons:
131 // 1) It computes dominator tree levels for the entire function on each run
132 //    of 'compute'. While this isn't terrible, given that we expect to update
133 //    relatively small subtrees of the domtree, it isn't necessarily the right
134 //    tradeoff.
135 // 2) The interface doesn't fit this usage well. It doesn't operate in
136 //    append-only, and builds several sets that we don't need.
137 //
138 // FIXME: Neither of these issues are a big deal and could be addressed with
139 // some amount of refactoring of IDFCalculator. That would allow us to share
140 // the core logic here (which is solving the same core problem).
141 static void appendDomFrontier(DomTreeNode *Node,
142                               SmallSetVector<BasicBlock *, 4> &Worklist,
143                               SmallVectorImpl<DomTreeNode *> &DomNodes,
144                               SmallPtrSetImpl<BasicBlock *> &DomSet) {
145   assert(DomNodes.empty() && "Must start with no dominator nodes.");
146   assert(DomSet.empty() && "Must start with an empty dominator set.");
147 
148   // First flatten this subtree into sequence of nodes by doing a pre-order
149   // walk.
150   DomNodes.push_back(Node);
151   // We intentionally re-evaluate the size as each node can add new children.
152   // Because this is a tree walk, this cannot add any duplicates.
153   for (int i = 0; i < (int)DomNodes.size(); ++i)
154     DomNodes.insert(DomNodes.end(), DomNodes[i]->begin(), DomNodes[i]->end());
155 
156   // Now create a set of the basic blocks so we can quickly test for
157   // dominated successors. We could in theory use the DFS numbers of the
158   // dominator tree for this, but we want this to remain predictably fast
159   // even while we mutate the dominator tree in ways that would invalidate
160   // the DFS numbering.
161   for (DomTreeNode *InnerN : DomNodes)
162     DomSet.insert(InnerN->getBlock());
163 
164   // Now re-walk the nodes, appending every successor of every node that isn't
165   // in the set. Note that we don't append the node itself, even though if it
166   // is a successor it does not strictly dominate itself and thus it would be
167   // part of the dominance frontier. The reason we don't append it is that
168   // the node passed in came *from* the worklist and so it has already been
169   // processed.
170   for (DomTreeNode *InnerN : DomNodes)
171     for (BasicBlock *SuccBB : successors(InnerN->getBlock()))
172       if (!DomSet.count(SuccBB))
173         Worklist.insert(SuccBB);
174 
175   DomNodes.clear();
176   DomSet.clear();
177 }
178 
179 /// Update the dominator tree after unswitching a particular former exit block.
180 ///
181 /// This handles the full update of the dominator tree after hoisting a block
182 /// that previously was an exit block (or split off of an exit block) up to be
183 /// reached from the new immediate dominator of the preheader.
184 ///
185 /// The common case is simple -- we just move the unswitched block to have an
186 /// immediate dominator of the old preheader. But in complex cases, there may
187 /// be other blocks reachable from the unswitched block that are immediately
188 /// dominated by some node between the unswitched one and the old preheader.
189 /// All of these also need to be hoisted in the dominator tree. We also want to
190 /// minimize queries to the dominator tree because each step of this
191 /// invalidates any DFS numbers that would make queries fast.
192 static void updateDTAfterUnswitch(BasicBlock *UnswitchedBB, BasicBlock *OldPH,
193                                   DominatorTree &DT) {
194   DomTreeNode *OldPHNode = DT[OldPH];
195   DomTreeNode *UnswitchedNode = DT[UnswitchedBB];
196   // If the dominator tree has already been updated for this unswitched node,
197   // we're done. This makes it easier to use this routine if there are multiple
198   // paths to the same unswitched destination.
199   if (UnswitchedNode->getIDom() == OldPHNode)
200     return;
201 
202   // First collect the domtree nodes that we are hoisting over. These are the
203   // set of nodes which may have children that need to be hoisted as well.
204   SmallPtrSet<DomTreeNode *, 4> DomChain;
205   for (auto *IDom = UnswitchedNode->getIDom(); IDom != OldPHNode;
206        IDom = IDom->getIDom())
207     DomChain.insert(IDom);
208 
209   // The unswitched block ends up immediately dominated by the old preheader --
210   // regardless of whether it is the loop exit block or split off of the loop
211   // exit block.
212   DT.changeImmediateDominator(UnswitchedNode, OldPHNode);
213 
214   // For everything that moves up the dominator tree, we need to examine the
215   // dominator frontier to see if it additionally should move up the dominator
216   // tree. This lambda appends the dominator frontier for a node on the
217   // worklist.
218   SmallSetVector<BasicBlock *, 4> Worklist;
219 
220   // Scratch data structures reused by domfrontier finding.
221   SmallVector<DomTreeNode *, 4> DomNodes;
222   SmallPtrSet<BasicBlock *, 4> DomSet;
223 
224   // Append the initial dom frontier nodes.
225   appendDomFrontier(UnswitchedNode, Worklist, DomNodes, DomSet);
226 
227   // Walk the worklist. We grow the list in the loop and so must recompute size.
228   for (int i = 0; i < (int)Worklist.size(); ++i) {
229     auto *BB = Worklist[i];
230 
231     DomTreeNode *Node = DT[BB];
232     assert(!DomChain.count(Node) &&
233            "Cannot be dominated by a block you can reach!");
234 
235     // If this block had an immediate dominator somewhere in the chain
236     // we hoisted over, then its position in the domtree needs to move as it is
237     // reachable from a node hoisted over this chain.
238     if (!DomChain.count(Node->getIDom()))
239       continue;
240 
241     DT.changeImmediateDominator(Node, OldPHNode);
242 
243     // Now add this node's dominator frontier to the worklist as well.
244     appendDomFrontier(Node, Worklist, DomNodes, DomSet);
245   }
246 }
247 
248 /// Check that all the LCSSA PHI nodes in the loop exit block have trivial
249 /// incoming values along this edge.
250 static bool areLoopExitPHIsLoopInvariant(Loop &L, BasicBlock &ExitingBB,
251                                          BasicBlock &ExitBB) {
252   for (Instruction &I : ExitBB) {
253     auto *PN = dyn_cast<PHINode>(&I);
254     if (!PN)
255       // No more PHIs to check.
256       return true;
257 
258     // If the incoming value for this edge isn't loop invariant the unswitch
259     // won't be trivial.
260     if (!L.isLoopInvariant(PN->getIncomingValueForBlock(&ExitingBB)))
261       return false;
262   }
263   llvm_unreachable("Basic blocks should never be empty!");
264 }
265 
266 /// Rewrite the PHI nodes in an unswitched loop exit basic block.
267 ///
268 /// Requires that the loop exit and unswitched basic block are the same, and
269 /// that the exiting block was a unique predecessor of that block. Rewrites the
270 /// PHI nodes in that block such that what were LCSSA PHI nodes become trivial
271 /// PHI nodes from the old preheader that now contains the unswitched
272 /// terminator.
273 static void rewritePHINodesForUnswitchedExitBlock(BasicBlock &UnswitchedBB,
274                                                   BasicBlock &OldExitingBB,
275                                                   BasicBlock &OldPH) {
276   for (PHINode &PN : UnswitchedBB.phis()) {
277     // When the loop exit is directly unswitched we just need to update the
278     // incoming basic block. We loop to handle weird cases with repeated
279     // incoming blocks, but expect to typically only have one operand here.
280     for (auto i : seq<int>(0, PN.getNumOperands())) {
281       assert(PN.getIncomingBlock(i) == &OldExitingBB &&
282              "Found incoming block different from unique predecessor!");
283       PN.setIncomingBlock(i, &OldPH);
284     }
285   }
286 }
287 
288 /// Rewrite the PHI nodes in the loop exit basic block and the split off
289 /// unswitched block.
290 ///
291 /// Because the exit block remains an exit from the loop, this rewrites the
292 /// LCSSA PHI nodes in it to remove the unswitched edge and introduces PHI
293 /// nodes into the unswitched basic block to select between the value in the
294 /// old preheader and the loop exit.
295 static void rewritePHINodesForExitAndUnswitchedBlocks(BasicBlock &ExitBB,
296                                                       BasicBlock &UnswitchedBB,
297                                                       BasicBlock &OldExitingBB,
298                                                       BasicBlock &OldPH) {
299   assert(&ExitBB != &UnswitchedBB &&
300          "Must have different loop exit and unswitched blocks!");
301   Instruction *InsertPt = &*UnswitchedBB.begin();
302   for (PHINode &PN : ExitBB.phis()) {
303     auto *NewPN = PHINode::Create(PN.getType(), /*NumReservedValues*/ 2,
304                                   PN.getName() + ".split", InsertPt);
305 
306     // Walk backwards over the old PHI node's inputs to minimize the cost of
307     // removing each one. We have to do this weird loop manually so that we
308     // create the same number of new incoming edges in the new PHI as we expect
309     // each case-based edge to be included in the unswitched switch in some
310     // cases.
311     // FIXME: This is really, really gross. It would be much cleaner if LLVM
312     // allowed us to create a single entry for a predecessor block without
313     // having separate entries for each "edge" even though these edges are
314     // required to produce identical results.
315     for (int i = PN.getNumIncomingValues() - 1; i >= 0; --i) {
316       if (PN.getIncomingBlock(i) != &OldExitingBB)
317         continue;
318 
319       Value *Incoming = PN.removeIncomingValue(i);
320       NewPN->addIncoming(Incoming, &OldPH);
321     }
322 
323     // Now replace the old PHI with the new one and wire the old one in as an
324     // input to the new one.
325     PN.replaceAllUsesWith(NewPN);
326     NewPN->addIncoming(&PN, &ExitBB);
327   }
328 }
329 
330 /// Unswitch a trivial branch if the condition is loop invariant.
331 ///
332 /// This routine should only be called when loop code leading to the branch has
333 /// been validated as trivial (no side effects). This routine checks if the
334 /// condition is invariant and one of the successors is a loop exit. This
335 /// allows us to unswitch without duplicating the loop, making it trivial.
336 ///
337 /// If this routine fails to unswitch the branch it returns false.
338 ///
339 /// If the branch can be unswitched, this routine splits the preheader and
340 /// hoists the branch above that split. Preserves loop simplified form
341 /// (splitting the exit block as necessary). It simplifies the branch within
342 /// the loop to an unconditional branch but doesn't remove it entirely. Further
343 /// cleanup can be done with some simplify-cfg like pass.
344 static bool unswitchTrivialBranch(Loop &L, BranchInst &BI, DominatorTree &DT,
345                                   LoopInfo &LI) {
346   assert(BI.isConditional() && "Can only unswitch a conditional branch!");
347   DEBUG(dbgs() << "  Trying to unswitch branch: " << BI << "\n");
348 
349   Value *LoopCond = BI.getCondition();
350 
351   // Need a trivial loop condition to unswitch.
352   if (!L.isLoopInvariant(LoopCond))
353     return false;
354 
355   // FIXME: We should compute this once at the start and update it!
356   SmallVector<BasicBlock *, 16> ExitBlocks;
357   L.getExitBlocks(ExitBlocks);
358   SmallPtrSet<BasicBlock *, 16> ExitBlockSet(ExitBlocks.begin(),
359                                              ExitBlocks.end());
360 
361   // Check to see if a successor of the branch is guaranteed to
362   // exit through a unique exit block without having any
363   // side-effects.  If so, determine the value of Cond that causes
364   // it to do this.
365   ConstantInt *CondVal = ConstantInt::getTrue(BI.getContext());
366   ConstantInt *Replacement = ConstantInt::getFalse(BI.getContext());
367   int LoopExitSuccIdx = 0;
368   auto *LoopExitBB = BI.getSuccessor(0);
369   if (!ExitBlockSet.count(LoopExitBB)) {
370     std::swap(CondVal, Replacement);
371     LoopExitSuccIdx = 1;
372     LoopExitBB = BI.getSuccessor(1);
373     if (!ExitBlockSet.count(LoopExitBB))
374       return false;
375   }
376   auto *ContinueBB = BI.getSuccessor(1 - LoopExitSuccIdx);
377   assert(L.contains(ContinueBB) &&
378          "Cannot have both successors exit and still be in the loop!");
379 
380   auto *ParentBB = BI.getParent();
381   if (!areLoopExitPHIsLoopInvariant(L, *ParentBB, *LoopExitBB))
382     return false;
383 
384   DEBUG(dbgs() << "    unswitching trivial branch when: " << CondVal
385                << " == " << LoopCond << "\n");
386 
387   // Split the preheader, so that we know that there is a safe place to insert
388   // the conditional branch. We will change the preheader to have a conditional
389   // branch on LoopCond.
390   BasicBlock *OldPH = L.getLoopPreheader();
391   BasicBlock *NewPH = SplitEdge(OldPH, L.getHeader(), &DT, &LI);
392 
393   // Now that we have a place to insert the conditional branch, create a place
394   // to branch to: this is the exit block out of the loop that we are
395   // unswitching. We need to split this if there are other loop predecessors.
396   // Because the loop is in simplified form, *any* other predecessor is enough.
397   BasicBlock *UnswitchedBB;
398   if (BasicBlock *PredBB = LoopExitBB->getUniquePredecessor()) {
399     (void)PredBB;
400     assert(PredBB == BI.getParent() &&
401            "A branch's parent isn't a predecessor!");
402     UnswitchedBB = LoopExitBB;
403   } else {
404     UnswitchedBB = SplitBlock(LoopExitBB, &LoopExitBB->front(), &DT, &LI);
405   }
406 
407   // Now splice the branch to gate reaching the new preheader and re-point its
408   // successors.
409   OldPH->getInstList().splice(std::prev(OldPH->end()),
410                               BI.getParent()->getInstList(), BI);
411   OldPH->getTerminator()->eraseFromParent();
412   BI.setSuccessor(LoopExitSuccIdx, UnswitchedBB);
413   BI.setSuccessor(1 - LoopExitSuccIdx, NewPH);
414 
415   // Create a new unconditional branch that will continue the loop as a new
416   // terminator.
417   BranchInst::Create(ContinueBB, ParentBB);
418 
419   // Rewrite the relevant PHI nodes.
420   if (UnswitchedBB == LoopExitBB)
421     rewritePHINodesForUnswitchedExitBlock(*UnswitchedBB, *ParentBB, *OldPH);
422   else
423     rewritePHINodesForExitAndUnswitchedBlocks(*LoopExitBB, *UnswitchedBB,
424                                               *ParentBB, *OldPH);
425 
426   // Now we need to update the dominator tree.
427   updateDTAfterUnswitch(UnswitchedBB, OldPH, DT);
428   // But if we split something off of the loop exit block then we also removed
429   // one of the predecessors for the loop exit block and may need to update its
430   // idom.
431   if (UnswitchedBB != LoopExitBB)
432     updateIDomWithKnownCommonDominator(LoopExitBB, L.getHeader(), DT);
433 
434   // Since this is an i1 condition we can also trivially replace uses of it
435   // within the loop with a constant.
436   replaceLoopUsesWithConstant(L, *LoopCond, *Replacement);
437 
438   ++NumTrivial;
439   ++NumBranches;
440   return true;
441 }
442 
443 /// Unswitch a trivial switch if the condition is loop invariant.
444 ///
445 /// This routine should only be called when loop code leading to the switch has
446 /// been validated as trivial (no side effects). This routine checks if the
447 /// condition is invariant and that at least one of the successors is a loop
448 /// exit. This allows us to unswitch without duplicating the loop, making it
449 /// trivial.
450 ///
451 /// If this routine fails to unswitch the switch it returns false.
452 ///
453 /// If the switch can be unswitched, this routine splits the preheader and
454 /// copies the switch above that split. If the default case is one of the
455 /// exiting cases, it copies the non-exiting cases and points them at the new
456 /// preheader. If the default case is not exiting, it copies the exiting cases
457 /// and points the default at the preheader. It preserves loop simplified form
458 /// (splitting the exit blocks as necessary). It simplifies the switch within
459 /// the loop by removing now-dead cases. If the default case is one of those
460 /// unswitched, it replaces its destination with a new basic block containing
461 /// only unreachable. Such basic blocks, while technically loop exits, are not
462 /// considered for unswitching so this is a stable transform and the same
463 /// switch will not be revisited. If after unswitching there is only a single
464 /// in-loop successor, the switch is further simplified to an unconditional
465 /// branch. Still more cleanup can be done with some simplify-cfg like pass.
466 static bool unswitchTrivialSwitch(Loop &L, SwitchInst &SI, DominatorTree &DT,
467                                   LoopInfo &LI) {
468   DEBUG(dbgs() << "  Trying to unswitch switch: " << SI << "\n");
469   Value *LoopCond = SI.getCondition();
470 
471   // If this isn't switching on an invariant condition, we can't unswitch it.
472   if (!L.isLoopInvariant(LoopCond))
473     return false;
474 
475   auto *ParentBB = SI.getParent();
476 
477   // FIXME: We should compute this once at the start and update it!
478   SmallVector<BasicBlock *, 16> ExitBlocks;
479   L.getExitBlocks(ExitBlocks);
480   SmallPtrSet<BasicBlock *, 16> ExitBlockSet(ExitBlocks.begin(),
481                                              ExitBlocks.end());
482 
483   SmallVector<int, 4> ExitCaseIndices;
484   for (auto Case : SI.cases()) {
485     auto *SuccBB = Case.getCaseSuccessor();
486     if (ExitBlockSet.count(SuccBB) &&
487         areLoopExitPHIsLoopInvariant(L, *ParentBB, *SuccBB))
488       ExitCaseIndices.push_back(Case.getCaseIndex());
489   }
490   BasicBlock *DefaultExitBB = nullptr;
491   if (ExitBlockSet.count(SI.getDefaultDest()) &&
492       areLoopExitPHIsLoopInvariant(L, *ParentBB, *SI.getDefaultDest()) &&
493       !isa<UnreachableInst>(SI.getDefaultDest()->getTerminator()))
494     DefaultExitBB = SI.getDefaultDest();
495   else if (ExitCaseIndices.empty())
496     return false;
497 
498   DEBUG(dbgs() << "    unswitching trivial cases...\n");
499 
500   SmallVector<std::pair<ConstantInt *, BasicBlock *>, 4> ExitCases;
501   ExitCases.reserve(ExitCaseIndices.size());
502   // We walk the case indices backwards so that we remove the last case first
503   // and don't disrupt the earlier indices.
504   for (unsigned Index : reverse(ExitCaseIndices)) {
505     auto CaseI = SI.case_begin() + Index;
506     // Save the value of this case.
507     ExitCases.push_back({CaseI->getCaseValue(), CaseI->getCaseSuccessor()});
508     // Delete the unswitched cases.
509     SI.removeCase(CaseI);
510   }
511 
512   // Check if after this all of the remaining cases point at the same
513   // successor.
514   BasicBlock *CommonSuccBB = nullptr;
515   if (SI.getNumCases() > 0 &&
516       std::all_of(std::next(SI.case_begin()), SI.case_end(),
517                   [&SI](const SwitchInst::CaseHandle &Case) {
518                     return Case.getCaseSuccessor() ==
519                            SI.case_begin()->getCaseSuccessor();
520                   }))
521     CommonSuccBB = SI.case_begin()->getCaseSuccessor();
522 
523   if (DefaultExitBB) {
524     // We can't remove the default edge so replace it with an edge to either
525     // the single common remaining successor (if we have one) or an unreachable
526     // block.
527     if (CommonSuccBB) {
528       SI.setDefaultDest(CommonSuccBB);
529     } else {
530       BasicBlock *UnreachableBB = BasicBlock::Create(
531           ParentBB->getContext(),
532           Twine(ParentBB->getName()) + ".unreachable_default",
533           ParentBB->getParent());
534       new UnreachableInst(ParentBB->getContext(), UnreachableBB);
535       SI.setDefaultDest(UnreachableBB);
536       DT.addNewBlock(UnreachableBB, ParentBB);
537     }
538   } else {
539     // If we're not unswitching the default, we need it to match any cases to
540     // have a common successor or if we have no cases it is the common
541     // successor.
542     if (SI.getNumCases() == 0)
543       CommonSuccBB = SI.getDefaultDest();
544     else if (SI.getDefaultDest() != CommonSuccBB)
545       CommonSuccBB = nullptr;
546   }
547 
548   // Split the preheader, so that we know that there is a safe place to insert
549   // the switch.
550   BasicBlock *OldPH = L.getLoopPreheader();
551   BasicBlock *NewPH = SplitEdge(OldPH, L.getHeader(), &DT, &LI);
552   OldPH->getTerminator()->eraseFromParent();
553 
554   // Now add the unswitched switch.
555   auto *NewSI = SwitchInst::Create(LoopCond, NewPH, ExitCases.size(), OldPH);
556 
557   // Rewrite the IR for the unswitched basic blocks. This requires two steps.
558   // First, we split any exit blocks with remaining in-loop predecessors. Then
559   // we update the PHIs in one of two ways depending on if there was a split.
560   // We walk in reverse so that we split in the same order as the cases
561   // appeared. This is purely for convenience of reading the resulting IR, but
562   // it doesn't cost anything really.
563   SmallPtrSet<BasicBlock *, 2> UnswitchedExitBBs;
564   SmallDenseMap<BasicBlock *, BasicBlock *, 2> SplitExitBBMap;
565   // Handle the default exit if necessary.
566   // FIXME: It'd be great if we could merge this with the loop below but LLVM's
567   // ranges aren't quite powerful enough yet.
568   if (DefaultExitBB) {
569     if (pred_empty(DefaultExitBB)) {
570       UnswitchedExitBBs.insert(DefaultExitBB);
571       rewritePHINodesForUnswitchedExitBlock(*DefaultExitBB, *ParentBB, *OldPH);
572     } else {
573       auto *SplitBB =
574           SplitBlock(DefaultExitBB, &DefaultExitBB->front(), &DT, &LI);
575       rewritePHINodesForExitAndUnswitchedBlocks(*DefaultExitBB, *SplitBB,
576                                                 *ParentBB, *OldPH);
577       updateIDomWithKnownCommonDominator(DefaultExitBB, L.getHeader(), DT);
578       DefaultExitBB = SplitExitBBMap[DefaultExitBB] = SplitBB;
579     }
580   }
581   // Note that we must use a reference in the for loop so that we update the
582   // container.
583   for (auto &CasePair : reverse(ExitCases)) {
584     // Grab a reference to the exit block in the pair so that we can update it.
585     BasicBlock *ExitBB = CasePair.second;
586 
587     // If this case is the last edge into the exit block, we can simply reuse it
588     // as it will no longer be a loop exit. No mapping necessary.
589     if (pred_empty(ExitBB)) {
590       // Only rewrite once.
591       if (UnswitchedExitBBs.insert(ExitBB).second)
592         rewritePHINodesForUnswitchedExitBlock(*ExitBB, *ParentBB, *OldPH);
593       continue;
594     }
595 
596     // Otherwise we need to split the exit block so that we retain an exit
597     // block from the loop and a target for the unswitched condition.
598     BasicBlock *&SplitExitBB = SplitExitBBMap[ExitBB];
599     if (!SplitExitBB) {
600       // If this is the first time we see this, do the split and remember it.
601       SplitExitBB = SplitBlock(ExitBB, &ExitBB->front(), &DT, &LI);
602       rewritePHINodesForExitAndUnswitchedBlocks(*ExitBB, *SplitExitBB,
603                                                 *ParentBB, *OldPH);
604       updateIDomWithKnownCommonDominator(ExitBB, L.getHeader(), DT);
605     }
606     // Update the case pair to point to the split block.
607     CasePair.second = SplitExitBB;
608   }
609 
610   // Now add the unswitched cases. We do this in reverse order as we built them
611   // in reverse order.
612   for (auto CasePair : reverse(ExitCases)) {
613     ConstantInt *CaseVal = CasePair.first;
614     BasicBlock *UnswitchedBB = CasePair.second;
615 
616     NewSI->addCase(CaseVal, UnswitchedBB);
617     updateDTAfterUnswitch(UnswitchedBB, OldPH, DT);
618   }
619 
620   // If the default was unswitched, re-point it and add explicit cases for
621   // entering the loop.
622   if (DefaultExitBB) {
623     NewSI->setDefaultDest(DefaultExitBB);
624     updateDTAfterUnswitch(DefaultExitBB, OldPH, DT);
625 
626     // We removed all the exit cases, so we just copy the cases to the
627     // unswitched switch.
628     for (auto Case : SI.cases())
629       NewSI->addCase(Case.getCaseValue(), NewPH);
630   }
631 
632   // If we ended up with a common successor for every path through the switch
633   // after unswitching, rewrite it to an unconditional branch to make it easy
634   // to recognize. Otherwise we potentially have to recognize the default case
635   // pointing at unreachable and other complexity.
636   if (CommonSuccBB) {
637     BasicBlock *BB = SI.getParent();
638     SI.eraseFromParent();
639     BranchInst::Create(CommonSuccBB, BB);
640   }
641 
642   assert(DT.verify(DominatorTree::VerificationLevel::Fast));
643   ++NumTrivial;
644   ++NumSwitches;
645   return true;
646 }
647 
648 /// This routine scans the loop to find a branch or switch which occurs before
649 /// any side effects occur. These can potentially be unswitched without
650 /// duplicating the loop. If a branch or switch is successfully unswitched the
651 /// scanning continues to see if subsequent branches or switches have become
652 /// trivial. Once all trivial candidates have been unswitched, this routine
653 /// returns.
654 ///
655 /// The return value indicates whether anything was unswitched (and therefore
656 /// changed).
657 static bool unswitchAllTrivialConditions(Loop &L, DominatorTree &DT,
658                                          LoopInfo &LI) {
659   bool Changed = false;
660 
661   // If loop header has only one reachable successor we should keep looking for
662   // trivial condition candidates in the successor as well. An alternative is
663   // to constant fold conditions and merge successors into loop header (then we
664   // only need to check header's terminator). The reason for not doing this in
665   // LoopUnswitch pass is that it could potentially break LoopPassManager's
666   // invariants. Folding dead branches could either eliminate the current loop
667   // or make other loops unreachable. LCSSA form might also not be preserved
668   // after deleting branches. The following code keeps traversing loop header's
669   // successors until it finds the trivial condition candidate (condition that
670   // is not a constant). Since unswitching generates branches with constant
671   // conditions, this scenario could be very common in practice.
672   BasicBlock *CurrentBB = L.getHeader();
673   SmallPtrSet<BasicBlock *, 8> Visited;
674   Visited.insert(CurrentBB);
675   do {
676     // Check if there are any side-effecting instructions (e.g. stores, calls,
677     // volatile loads) in the part of the loop that the code *would* execute
678     // without unswitching.
679     if (llvm::any_of(*CurrentBB,
680                      [](Instruction &I) { return I.mayHaveSideEffects(); }))
681       return Changed;
682 
683     TerminatorInst *CurrentTerm = CurrentBB->getTerminator();
684 
685     if (auto *SI = dyn_cast<SwitchInst>(CurrentTerm)) {
686       // Don't bother trying to unswitch past a switch with a constant
687       // condition. This should be removed prior to running this pass by
688       // simplify-cfg.
689       if (isa<Constant>(SI->getCondition()))
690         return Changed;
691 
692       if (!unswitchTrivialSwitch(L, *SI, DT, LI))
693         // Coludn't unswitch this one so we're done.
694         return Changed;
695 
696       // Mark that we managed to unswitch something.
697       Changed = true;
698 
699       // If unswitching turned the terminator into an unconditional branch then
700       // we can continue. The unswitching logic specifically works to fold any
701       // cases it can into an unconditional branch to make it easier to
702       // recognize here.
703       auto *BI = dyn_cast<BranchInst>(CurrentBB->getTerminator());
704       if (!BI || BI->isConditional())
705         return Changed;
706 
707       CurrentBB = BI->getSuccessor(0);
708       continue;
709     }
710 
711     auto *BI = dyn_cast<BranchInst>(CurrentTerm);
712     if (!BI)
713       // We do not understand other terminator instructions.
714       return Changed;
715 
716     // Don't bother trying to unswitch past an unconditional branch or a branch
717     // with a constant value. These should be removed by simplify-cfg prior to
718     // running this pass.
719     if (!BI->isConditional() || isa<Constant>(BI->getCondition()))
720       return Changed;
721 
722     // Found a trivial condition candidate: non-foldable conditional branch. If
723     // we fail to unswitch this, we can't do anything else that is trivial.
724     if (!unswitchTrivialBranch(L, *BI, DT, LI))
725       return Changed;
726 
727     // Mark that we managed to unswitch something.
728     Changed = true;
729 
730     // We unswitched the branch. This should always leave us with an
731     // unconditional branch that we can follow now.
732     BI = cast<BranchInst>(CurrentBB->getTerminator());
733     assert(!BI->isConditional() &&
734            "Cannot form a conditional branch by unswitching1");
735     CurrentBB = BI->getSuccessor(0);
736 
737     // When continuing, if we exit the loop or reach a previous visited block,
738     // then we can not reach any trivial condition candidates (unfoldable
739     // branch instructions or switch instructions) and no unswitch can happen.
740   } while (L.contains(CurrentBB) && Visited.insert(CurrentBB).second);
741 
742   return Changed;
743 }
744 
745 /// Build the cloned blocks for an unswitched copy of the given loop.
746 ///
747 /// The cloned blocks are inserted before the loop preheader (`LoopPH`) and
748 /// after the split block (`SplitBB`) that will be used to select between the
749 /// cloned and original loop.
750 ///
751 /// This routine handles cloning all of the necessary loop blocks and exit
752 /// blocks including rewriting their instructions and the relevant PHI nodes.
753 /// It skips loop and exit blocks that are not necessary based on the provided
754 /// set. It also correctly creates the unconditional branch in the cloned
755 /// unswitched parent block to only point at the unswitched successor.
756 ///
757 /// This does not handle most of the necessary updates to `LoopInfo`. Only exit
758 /// block splitting is correctly reflected in `LoopInfo`, essentially all of
759 /// the cloned blocks (and their loops) are left without full `LoopInfo`
760 /// updates. This also doesn't fully update `DominatorTree`. It adds the cloned
761 /// blocks to them but doesn't create the cloned `DominatorTree` structure and
762 /// instead the caller must recompute an accurate DT. It *does* correctly
763 /// update the `AssumptionCache` provided in `AC`.
764 static BasicBlock *buildClonedLoopBlocks(
765     Loop &L, BasicBlock *LoopPH, BasicBlock *SplitBB,
766     ArrayRef<BasicBlock *> ExitBlocks, BasicBlock *ParentBB,
767     BasicBlock *UnswitchedSuccBB, BasicBlock *ContinueSuccBB,
768     const SmallPtrSetImpl<BasicBlock *> &SkippedLoopAndExitBlocks,
769     ValueToValueMapTy &VMap, AssumptionCache &AC, DominatorTree &DT,
770     LoopInfo &LI) {
771   SmallVector<BasicBlock *, 4> NewBlocks;
772   NewBlocks.reserve(L.getNumBlocks() + ExitBlocks.size());
773 
774   // We will need to clone a bunch of blocks, wrap up the clone operation in
775   // a helper.
776   auto CloneBlock = [&](BasicBlock *OldBB) {
777     // Clone the basic block and insert it before the new preheader.
778     BasicBlock *NewBB = CloneBasicBlock(OldBB, VMap, ".us", OldBB->getParent());
779     NewBB->moveBefore(LoopPH);
780 
781     // Record this block and the mapping.
782     NewBlocks.push_back(NewBB);
783     VMap[OldBB] = NewBB;
784 
785     // Add the block to the domtree. We'll move it to the correct position
786     // below.
787     DT.addNewBlock(NewBB, SplitBB);
788 
789     return NewBB;
790   };
791 
792   // First, clone the preheader.
793   auto *ClonedPH = CloneBlock(LoopPH);
794 
795   // Then clone all the loop blocks, skipping the ones that aren't necessary.
796   for (auto *LoopBB : L.blocks())
797     if (!SkippedLoopAndExitBlocks.count(LoopBB))
798       CloneBlock(LoopBB);
799 
800   // Split all the loop exit edges so that when we clone the exit blocks, if
801   // any of the exit blocks are *also* a preheader for some other loop, we
802   // don't create multiple predecessors entering the loop header.
803   for (auto *ExitBB : ExitBlocks) {
804     if (SkippedLoopAndExitBlocks.count(ExitBB))
805       continue;
806 
807     // When we are going to clone an exit, we don't need to clone all the
808     // instructions in the exit block and we want to ensure we have an easy
809     // place to merge the CFG, so split the exit first. This is always safe to
810     // do because there cannot be any non-loop predecessors of a loop exit in
811     // loop simplified form.
812     auto *MergeBB = SplitBlock(ExitBB, &ExitBB->front(), &DT, &LI);
813 
814     // Rearrange the names to make it easier to write test cases by having the
815     // exit block carry the suffix rather than the merge block carrying the
816     // suffix.
817     MergeBB->takeName(ExitBB);
818     ExitBB->setName(Twine(MergeBB->getName()) + ".split");
819 
820     // Now clone the original exit block.
821     auto *ClonedExitBB = CloneBlock(ExitBB);
822     assert(ClonedExitBB->getTerminator()->getNumSuccessors() == 1 &&
823            "Exit block should have been split to have one successor!");
824     assert(ClonedExitBB->getTerminator()->getSuccessor(0) == MergeBB &&
825            "Cloned exit block has the wrong successor!");
826 
827     // Move the merge block's idom to be the split point as one exit is
828     // dominated by one header, and the other by another, so we know the split
829     // point dominates both. While the dominator tree isn't fully accurate, we
830     // want sub-trees within the original loop to be correctly reflect
831     // dominance within that original loop (at least) and that requires moving
832     // the merge block out of that subtree.
833     // FIXME: This is very brittle as we essentially have a partial contract on
834     // the dominator tree. We really need to instead update it and keep it
835     // valid or stop relying on it.
836     DT.changeImmediateDominator(MergeBB, SplitBB);
837 
838     // Remap any cloned instructions and create a merge phi node for them.
839     for (auto ZippedInsts : llvm::zip_first(
840              llvm::make_range(ExitBB->begin(), std::prev(ExitBB->end())),
841              llvm::make_range(ClonedExitBB->begin(),
842                               std::prev(ClonedExitBB->end())))) {
843       Instruction &I = std::get<0>(ZippedInsts);
844       Instruction &ClonedI = std::get<1>(ZippedInsts);
845 
846       // The only instructions in the exit block should be PHI nodes and
847       // potentially a landing pad.
848       assert(
849           (isa<PHINode>(I) || isa<LandingPadInst>(I) || isa<CatchPadInst>(I)) &&
850           "Bad instruction in exit block!");
851       // We should have a value map between the instruction and its clone.
852       assert(VMap.lookup(&I) == &ClonedI && "Mismatch in the value map!");
853 
854       auto *MergePN =
855           PHINode::Create(I.getType(), /*NumReservedValues*/ 2, ".us-phi",
856                           &*MergeBB->getFirstInsertionPt());
857       I.replaceAllUsesWith(MergePN);
858       MergePN->addIncoming(&I, ExitBB);
859       MergePN->addIncoming(&ClonedI, ClonedExitBB);
860     }
861   }
862 
863   // Rewrite the instructions in the cloned blocks to refer to the instructions
864   // in the cloned blocks. We have to do this as a second pass so that we have
865   // everything available. Also, we have inserted new instructions which may
866   // include assume intrinsics, so we update the assumption cache while
867   // processing this.
868   for (auto *ClonedBB : NewBlocks)
869     for (Instruction &I : *ClonedBB) {
870       RemapInstruction(&I, VMap,
871                        RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
872       if (auto *II = dyn_cast<IntrinsicInst>(&I))
873         if (II->getIntrinsicID() == Intrinsic::assume)
874           AC.registerAssumption(II);
875     }
876 
877   // Remove the cloned parent as a predecessor of the cloned continue successor
878   // if we did in fact clone it.
879   auto *ClonedParentBB = cast<BasicBlock>(VMap.lookup(ParentBB));
880   if (auto *ClonedContinueSuccBB =
881           cast_or_null<BasicBlock>(VMap.lookup(ContinueSuccBB)))
882     ClonedContinueSuccBB->removePredecessor(ClonedParentBB,
883                                             /*DontDeleteUselessPHIs*/ true);
884   // Replace the cloned branch with an unconditional branch to the cloned
885   // unswitched successor.
886   auto *ClonedSuccBB = cast<BasicBlock>(VMap.lookup(UnswitchedSuccBB));
887   ClonedParentBB->getTerminator()->eraseFromParent();
888   BranchInst::Create(ClonedSuccBB, ClonedParentBB);
889 
890   // Update any PHI nodes in the cloned successors of the skipped blocks to not
891   // have spurious incoming values.
892   for (auto *LoopBB : L.blocks())
893     if (SkippedLoopAndExitBlocks.count(LoopBB))
894       for (auto *SuccBB : successors(LoopBB))
895         if (auto *ClonedSuccBB = cast_or_null<BasicBlock>(VMap.lookup(SuccBB)))
896           for (PHINode &PN : ClonedSuccBB->phis())
897             PN.removeIncomingValue(LoopBB, /*DeletePHIIfEmpty*/ false);
898 
899   return ClonedPH;
900 }
901 
902 /// Recursively clone the specified loop and all of its children.
903 ///
904 /// The target parent loop for the clone should be provided, or can be null if
905 /// the clone is a top-level loop. While cloning, all the blocks are mapped
906 /// with the provided value map. The entire original loop must be present in
907 /// the value map. The cloned loop is returned.
908 static Loop *cloneLoopNest(Loop &OrigRootL, Loop *RootParentL,
909                            const ValueToValueMapTy &VMap, LoopInfo &LI) {
910   auto AddClonedBlocksToLoop = [&](Loop &OrigL, Loop &ClonedL) {
911     assert(ClonedL.getBlocks().empty() && "Must start with an empty loop!");
912     ClonedL.reserveBlocks(OrigL.getNumBlocks());
913     for (auto *BB : OrigL.blocks()) {
914       auto *ClonedBB = cast<BasicBlock>(VMap.lookup(BB));
915       ClonedL.addBlockEntry(ClonedBB);
916       if (LI.getLoopFor(BB) == &OrigL) {
917         assert(!LI.getLoopFor(ClonedBB) &&
918                "Should not have an existing loop for this block!");
919         LI.changeLoopFor(ClonedBB, &ClonedL);
920       }
921     }
922   };
923 
924   // We specially handle the first loop because it may get cloned into
925   // a different parent and because we most commonly are cloning leaf loops.
926   Loop *ClonedRootL = LI.AllocateLoop();
927   if (RootParentL)
928     RootParentL->addChildLoop(ClonedRootL);
929   else
930     LI.addTopLevelLoop(ClonedRootL);
931   AddClonedBlocksToLoop(OrigRootL, *ClonedRootL);
932 
933   if (OrigRootL.empty())
934     return ClonedRootL;
935 
936   // If we have a nest, we can quickly clone the entire loop nest using an
937   // iterative approach because it is a tree. We keep the cloned parent in the
938   // data structure to avoid repeatedly querying through a map to find it.
939   SmallVector<std::pair<Loop *, Loop *>, 16> LoopsToClone;
940   // Build up the loops to clone in reverse order as we'll clone them from the
941   // back.
942   for (Loop *ChildL : llvm::reverse(OrigRootL))
943     LoopsToClone.push_back({ClonedRootL, ChildL});
944   do {
945     Loop *ClonedParentL, *L;
946     std::tie(ClonedParentL, L) = LoopsToClone.pop_back_val();
947     Loop *ClonedL = LI.AllocateLoop();
948     ClonedParentL->addChildLoop(ClonedL);
949     AddClonedBlocksToLoop(*L, *ClonedL);
950     for (Loop *ChildL : llvm::reverse(*L))
951       LoopsToClone.push_back({ClonedL, ChildL});
952   } while (!LoopsToClone.empty());
953 
954   return ClonedRootL;
955 }
956 
957 /// Build the cloned loops of an original loop from unswitching.
958 ///
959 /// Because unswitching simplifies the CFG of the loop, this isn't a trivial
960 /// operation. We need to re-verify that there even is a loop (as the backedge
961 /// may not have been cloned), and even if there are remaining backedges the
962 /// backedge set may be different. However, we know that each child loop is
963 /// undisturbed, we only need to find where to place each child loop within
964 /// either any parent loop or within a cloned version of the original loop.
965 ///
966 /// Because child loops may end up cloned outside of any cloned version of the
967 /// original loop, multiple cloned sibling loops may be created. All of them
968 /// are returned so that the newly introduced loop nest roots can be
969 /// identified.
970 static Loop *buildClonedLoops(Loop &OrigL, ArrayRef<BasicBlock *> ExitBlocks,
971                               const ValueToValueMapTy &VMap, LoopInfo &LI,
972                               SmallVectorImpl<Loop *> &NonChildClonedLoops) {
973   Loop *ClonedL = nullptr;
974 
975   auto *OrigPH = OrigL.getLoopPreheader();
976   auto *OrigHeader = OrigL.getHeader();
977 
978   auto *ClonedPH = cast<BasicBlock>(VMap.lookup(OrigPH));
979   auto *ClonedHeader = cast<BasicBlock>(VMap.lookup(OrigHeader));
980 
981   // We need to know the loops of the cloned exit blocks to even compute the
982   // accurate parent loop. If we only clone exits to some parent of the
983   // original parent, we want to clone into that outer loop. We also keep track
984   // of the loops that our cloned exit blocks participate in.
985   Loop *ParentL = nullptr;
986   SmallVector<BasicBlock *, 4> ClonedExitsInLoops;
987   SmallDenseMap<BasicBlock *, Loop *, 16> ExitLoopMap;
988   ClonedExitsInLoops.reserve(ExitBlocks.size());
989   for (auto *ExitBB : ExitBlocks)
990     if (auto *ClonedExitBB = cast_or_null<BasicBlock>(VMap.lookup(ExitBB)))
991       if (Loop *ExitL = LI.getLoopFor(ExitBB)) {
992         ExitLoopMap[ClonedExitBB] = ExitL;
993         ClonedExitsInLoops.push_back(ClonedExitBB);
994         if (!ParentL || (ParentL != ExitL && ParentL->contains(ExitL)))
995           ParentL = ExitL;
996       }
997   assert((!ParentL || ParentL == OrigL.getParentLoop() ||
998           ParentL->contains(OrigL.getParentLoop())) &&
999          "The computed parent loop should always contain (or be) the parent of "
1000          "the original loop.");
1001 
1002   // We build the set of blocks dominated by the cloned header from the set of
1003   // cloned blocks out of the original loop. While not all of these will
1004   // necessarily be in the cloned loop, it is enough to establish that they
1005   // aren't in unreachable cycles, etc.
1006   SmallSetVector<BasicBlock *, 16> ClonedLoopBlocks;
1007   for (auto *BB : OrigL.blocks())
1008     if (auto *ClonedBB = cast_or_null<BasicBlock>(VMap.lookup(BB)))
1009       ClonedLoopBlocks.insert(ClonedBB);
1010 
1011   // Rebuild the set of blocks that will end up in the cloned loop. We may have
1012   // skipped cloning some region of this loop which can in turn skip some of
1013   // the backedges so we have to rebuild the blocks in the loop based on the
1014   // backedges that remain after cloning.
1015   SmallVector<BasicBlock *, 16> Worklist;
1016   SmallPtrSet<BasicBlock *, 16> BlocksInClonedLoop;
1017   for (auto *Pred : predecessors(ClonedHeader)) {
1018     // The only possible non-loop header predecessor is the preheader because
1019     // we know we cloned the loop in simplified form.
1020     if (Pred == ClonedPH)
1021       continue;
1022 
1023     // Because the loop was in simplified form, the only non-loop predecessor
1024     // should be the preheader.
1025     assert(ClonedLoopBlocks.count(Pred) && "Found a predecessor of the loop "
1026                                            "header other than the preheader "
1027                                            "that is not part of the loop!");
1028 
1029     // Insert this block into the loop set and on the first visit (and if it
1030     // isn't the header we're currently walking) put it into the worklist to
1031     // recurse through.
1032     if (BlocksInClonedLoop.insert(Pred).second && Pred != ClonedHeader)
1033       Worklist.push_back(Pred);
1034   }
1035 
1036   // If we had any backedges then there *is* a cloned loop. Put the header into
1037   // the loop set and then walk the worklist backwards to find all the blocks
1038   // that remain within the loop after cloning.
1039   if (!BlocksInClonedLoop.empty()) {
1040     BlocksInClonedLoop.insert(ClonedHeader);
1041 
1042     while (!Worklist.empty()) {
1043       BasicBlock *BB = Worklist.pop_back_val();
1044       assert(BlocksInClonedLoop.count(BB) &&
1045              "Didn't put block into the loop set!");
1046 
1047       // Insert any predecessors that are in the possible set into the cloned
1048       // set, and if the insert is successful, add them to the worklist. Note
1049       // that we filter on the blocks that are definitely reachable via the
1050       // backedge to the loop header so we may prune out dead code within the
1051       // cloned loop.
1052       for (auto *Pred : predecessors(BB))
1053         if (ClonedLoopBlocks.count(Pred) &&
1054             BlocksInClonedLoop.insert(Pred).second)
1055           Worklist.push_back(Pred);
1056     }
1057 
1058     ClonedL = LI.AllocateLoop();
1059     if (ParentL) {
1060       ParentL->addBasicBlockToLoop(ClonedPH, LI);
1061       ParentL->addChildLoop(ClonedL);
1062     } else {
1063       LI.addTopLevelLoop(ClonedL);
1064     }
1065 
1066     ClonedL->reserveBlocks(BlocksInClonedLoop.size());
1067     // We don't want to just add the cloned loop blocks based on how we
1068     // discovered them. The original order of blocks was carefully built in
1069     // a way that doesn't rely on predecessor ordering. Rather than re-invent
1070     // that logic, we just re-walk the original blocks (and those of the child
1071     // loops) and filter them as we add them into the cloned loop.
1072     for (auto *BB : OrigL.blocks()) {
1073       auto *ClonedBB = cast_or_null<BasicBlock>(VMap.lookup(BB));
1074       if (!ClonedBB || !BlocksInClonedLoop.count(ClonedBB))
1075         continue;
1076 
1077       // Directly add the blocks that are only in this loop.
1078       if (LI.getLoopFor(BB) == &OrigL) {
1079         ClonedL->addBasicBlockToLoop(ClonedBB, LI);
1080         continue;
1081       }
1082 
1083       // We want to manually add it to this loop and parents.
1084       // Registering it with LoopInfo will happen when we clone the top
1085       // loop for this block.
1086       for (Loop *PL = ClonedL; PL; PL = PL->getParentLoop())
1087         PL->addBlockEntry(ClonedBB);
1088     }
1089 
1090     // Now add each child loop whose header remains within the cloned loop. All
1091     // of the blocks within the loop must satisfy the same constraints as the
1092     // header so once we pass the header checks we can just clone the entire
1093     // child loop nest.
1094     for (Loop *ChildL : OrigL) {
1095       auto *ClonedChildHeader =
1096           cast_or_null<BasicBlock>(VMap.lookup(ChildL->getHeader()));
1097       if (!ClonedChildHeader || !BlocksInClonedLoop.count(ClonedChildHeader))
1098         continue;
1099 
1100 #ifndef NDEBUG
1101       // We should never have a cloned child loop header but fail to have
1102       // all of the blocks for that child loop.
1103       for (auto *ChildLoopBB : ChildL->blocks())
1104         assert(BlocksInClonedLoop.count(
1105                    cast<BasicBlock>(VMap.lookup(ChildLoopBB))) &&
1106                "Child cloned loop has a header within the cloned outer "
1107                "loop but not all of its blocks!");
1108 #endif
1109 
1110       cloneLoopNest(*ChildL, ClonedL, VMap, LI);
1111     }
1112   }
1113 
1114   // Now that we've handled all the components of the original loop that were
1115   // cloned into a new loop, we still need to handle anything from the original
1116   // loop that wasn't in a cloned loop.
1117 
1118   // Figure out what blocks are left to place within any loop nest containing
1119   // the unswitched loop. If we never formed a loop, the cloned PH is one of
1120   // them.
1121   SmallPtrSet<BasicBlock *, 16> UnloopedBlockSet;
1122   if (BlocksInClonedLoop.empty())
1123     UnloopedBlockSet.insert(ClonedPH);
1124   for (auto *ClonedBB : ClonedLoopBlocks)
1125     if (!BlocksInClonedLoop.count(ClonedBB))
1126       UnloopedBlockSet.insert(ClonedBB);
1127 
1128   // Copy the cloned exits and sort them in ascending loop depth, we'll work
1129   // backwards across these to process them inside out. The order shouldn't
1130   // matter as we're just trying to build up the map from inside-out; we use
1131   // the map in a more stably ordered way below.
1132   auto OrderedClonedExitsInLoops = ClonedExitsInLoops;
1133   llvm::sort(OrderedClonedExitsInLoops.begin(),
1134              OrderedClonedExitsInLoops.end(),
1135              [&](BasicBlock *LHS, BasicBlock *RHS) {
1136                return ExitLoopMap.lookup(LHS)->getLoopDepth() <
1137                       ExitLoopMap.lookup(RHS)->getLoopDepth();
1138              });
1139 
1140   // Populate the existing ExitLoopMap with everything reachable from each
1141   // exit, starting from the inner most exit.
1142   while (!UnloopedBlockSet.empty() && !OrderedClonedExitsInLoops.empty()) {
1143     assert(Worklist.empty() && "Didn't clear worklist!");
1144 
1145     BasicBlock *ExitBB = OrderedClonedExitsInLoops.pop_back_val();
1146     Loop *ExitL = ExitLoopMap.lookup(ExitBB);
1147 
1148     // Walk the CFG back until we hit the cloned PH adding everything reachable
1149     // and in the unlooped set to this exit block's loop.
1150     Worklist.push_back(ExitBB);
1151     do {
1152       BasicBlock *BB = Worklist.pop_back_val();
1153       // We can stop recursing at the cloned preheader (if we get there).
1154       if (BB == ClonedPH)
1155         continue;
1156 
1157       for (BasicBlock *PredBB : predecessors(BB)) {
1158         // If this pred has already been moved to our set or is part of some
1159         // (inner) loop, no update needed.
1160         if (!UnloopedBlockSet.erase(PredBB)) {
1161           assert(
1162               (BlocksInClonedLoop.count(PredBB) || ExitLoopMap.count(PredBB)) &&
1163               "Predecessor not mapped to a loop!");
1164           continue;
1165         }
1166 
1167         // We just insert into the loop set here. We'll add these blocks to the
1168         // exit loop after we build up the set in an order that doesn't rely on
1169         // predecessor order (which in turn relies on use list order).
1170         bool Inserted = ExitLoopMap.insert({PredBB, ExitL}).second;
1171         (void)Inserted;
1172         assert(Inserted && "Should only visit an unlooped block once!");
1173 
1174         // And recurse through to its predecessors.
1175         Worklist.push_back(PredBB);
1176       }
1177     } while (!Worklist.empty());
1178   }
1179 
1180   // Now that the ExitLoopMap gives as  mapping for all the non-looping cloned
1181   // blocks to their outer loops, walk the cloned blocks and the cloned exits
1182   // in their original order adding them to the correct loop.
1183 
1184   // We need a stable insertion order. We use the order of the original loop
1185   // order and map into the correct parent loop.
1186   for (auto *BB : llvm::concat<BasicBlock *const>(
1187            makeArrayRef(ClonedPH), ClonedLoopBlocks, ClonedExitsInLoops))
1188     if (Loop *OuterL = ExitLoopMap.lookup(BB))
1189       OuterL->addBasicBlockToLoop(BB, LI);
1190 
1191 #ifndef NDEBUG
1192   for (auto &BBAndL : ExitLoopMap) {
1193     auto *BB = BBAndL.first;
1194     auto *OuterL = BBAndL.second;
1195     assert(LI.getLoopFor(BB) == OuterL &&
1196            "Failed to put all blocks into outer loops!");
1197   }
1198 #endif
1199 
1200   // Now that all the blocks are placed into the correct containing loop in the
1201   // absence of child loops, find all the potentially cloned child loops and
1202   // clone them into whatever outer loop we placed their header into.
1203   for (Loop *ChildL : OrigL) {
1204     auto *ClonedChildHeader =
1205         cast_or_null<BasicBlock>(VMap.lookup(ChildL->getHeader()));
1206     if (!ClonedChildHeader || BlocksInClonedLoop.count(ClonedChildHeader))
1207       continue;
1208 
1209 #ifndef NDEBUG
1210     for (auto *ChildLoopBB : ChildL->blocks())
1211       assert(VMap.count(ChildLoopBB) &&
1212              "Cloned a child loop header but not all of that loops blocks!");
1213 #endif
1214 
1215     NonChildClonedLoops.push_back(cloneLoopNest(
1216         *ChildL, ExitLoopMap.lookup(ClonedChildHeader), VMap, LI));
1217   }
1218 
1219   // Return the main cloned loop if any.
1220   return ClonedL;
1221 }
1222 
1223 static void deleteDeadBlocksFromLoop(Loop &L, BasicBlock *DeadSubtreeRoot,
1224                                      SmallVectorImpl<BasicBlock *> &ExitBlocks,
1225                                      DominatorTree &DT, LoopInfo &LI) {
1226   // Walk the dominator tree to build up the set of blocks we will delete here.
1227   // The order is designed to allow us to always delete bottom-up and avoid any
1228   // dangling uses.
1229   SmallSetVector<BasicBlock *, 16> DeadBlocks;
1230   DeadBlocks.insert(DeadSubtreeRoot);
1231   for (int i = 0; i < (int)DeadBlocks.size(); ++i)
1232     for (DomTreeNode *ChildN : *DT[DeadBlocks[i]]) {
1233       // FIXME: This assert should pass and that means we don't change nearly
1234       // as much below! Consider rewriting all of this to avoid deleting
1235       // blocks. They are always cloned before being deleted, and so instead
1236       // could just be moved.
1237       // FIXME: This in turn means that we might actually be more able to
1238       // update the domtree.
1239       assert((L.contains(ChildN->getBlock()) ||
1240               llvm::find(ExitBlocks, ChildN->getBlock()) != ExitBlocks.end()) &&
1241              "Should never reach beyond the loop and exits when deleting!");
1242       DeadBlocks.insert(ChildN->getBlock());
1243     }
1244 
1245   // Filter out the dead blocks from the exit blocks list so that it can be
1246   // used in the caller.
1247   llvm::erase_if(ExitBlocks,
1248                  [&](BasicBlock *BB) { return DeadBlocks.count(BB); });
1249 
1250   // Remove these blocks from their successors.
1251   for (auto *BB : DeadBlocks)
1252     for (BasicBlock *SuccBB : successors(BB))
1253       SuccBB->removePredecessor(BB, /*DontDeleteUselessPHIs*/ true);
1254 
1255   // Walk from this loop up through its parents removing all of the dead blocks.
1256   for (Loop *ParentL = &L; ParentL; ParentL = ParentL->getParentLoop()) {
1257     for (auto *BB : DeadBlocks)
1258       ParentL->getBlocksSet().erase(BB);
1259     llvm::erase_if(ParentL->getBlocksVector(),
1260                    [&](BasicBlock *BB) { return DeadBlocks.count(BB); });
1261   }
1262 
1263   // Now delete the dead child loops. This raw delete will clear them
1264   // recursively.
1265   llvm::erase_if(L.getSubLoopsVector(), [&](Loop *ChildL) {
1266     if (!DeadBlocks.count(ChildL->getHeader()))
1267       return false;
1268 
1269     assert(llvm::all_of(ChildL->blocks(),
1270                         [&](BasicBlock *ChildBB) {
1271                           return DeadBlocks.count(ChildBB);
1272                         }) &&
1273            "If the child loop header is dead all blocks in the child loop must "
1274            "be dead as well!");
1275     LI.destroy(ChildL);
1276     return true;
1277   });
1278 
1279   // Remove the mappings for the dead blocks.
1280   for (auto *BB : DeadBlocks)
1281     LI.changeLoopFor(BB, nullptr);
1282 
1283   // Drop all the references from these blocks to others to handle cyclic
1284   // references as we start deleting the blocks themselves.
1285   for (auto *BB : DeadBlocks)
1286     BB->dropAllReferences();
1287 
1288   for (auto *BB : llvm::reverse(DeadBlocks)) {
1289     DT.eraseNode(BB);
1290     BB->eraseFromParent();
1291   }
1292 }
1293 
1294 /// Recompute the set of blocks in a loop after unswitching.
1295 ///
1296 /// This walks from the original headers predecessors to rebuild the loop. We
1297 /// take advantage of the fact that new blocks can't have been added, and so we
1298 /// filter by the original loop's blocks. This also handles potentially
1299 /// unreachable code that we don't want to explore but might be found examining
1300 /// the predecessors of the header.
1301 ///
1302 /// If the original loop is no longer a loop, this will return an empty set. If
1303 /// it remains a loop, all the blocks within it will be added to the set
1304 /// (including those blocks in inner loops).
1305 static SmallPtrSet<const BasicBlock *, 16> recomputeLoopBlockSet(Loop &L,
1306                                                                  LoopInfo &LI) {
1307   SmallPtrSet<const BasicBlock *, 16> LoopBlockSet;
1308 
1309   auto *PH = L.getLoopPreheader();
1310   auto *Header = L.getHeader();
1311 
1312   // A worklist to use while walking backwards from the header.
1313   SmallVector<BasicBlock *, 16> Worklist;
1314 
1315   // First walk the predecessors of the header to find the backedges. This will
1316   // form the basis of our walk.
1317   for (auto *Pred : predecessors(Header)) {
1318     // Skip the preheader.
1319     if (Pred == PH)
1320       continue;
1321 
1322     // Because the loop was in simplified form, the only non-loop predecessor
1323     // is the preheader.
1324     assert(L.contains(Pred) && "Found a predecessor of the loop header other "
1325                                "than the preheader that is not part of the "
1326                                "loop!");
1327 
1328     // Insert this block into the loop set and on the first visit and, if it
1329     // isn't the header we're currently walking, put it into the worklist to
1330     // recurse through.
1331     if (LoopBlockSet.insert(Pred).second && Pred != Header)
1332       Worklist.push_back(Pred);
1333   }
1334 
1335   // If no backedges were found, we're done.
1336   if (LoopBlockSet.empty())
1337     return LoopBlockSet;
1338 
1339   // Add the loop header to the set.
1340   LoopBlockSet.insert(Header);
1341 
1342   // We found backedges, recurse through them to identify the loop blocks.
1343   while (!Worklist.empty()) {
1344     BasicBlock *BB = Worklist.pop_back_val();
1345     assert(LoopBlockSet.count(BB) && "Didn't put block into the loop set!");
1346 
1347     // Because we know the inner loop structure remains valid we can use the
1348     // loop structure to jump immediately across the entire nested loop.
1349     // Further, because it is in loop simplified form, we can directly jump
1350     // to its preheader afterward.
1351     if (Loop *InnerL = LI.getLoopFor(BB))
1352       if (InnerL != &L) {
1353         assert(L.contains(InnerL) &&
1354                "Should not reach a loop *outside* this loop!");
1355         // The preheader is the only possible predecessor of the loop so
1356         // insert it into the set and check whether it was already handled.
1357         auto *InnerPH = InnerL->getLoopPreheader();
1358         assert(L.contains(InnerPH) && "Cannot contain an inner loop block "
1359                                       "but not contain the inner loop "
1360                                       "preheader!");
1361         if (!LoopBlockSet.insert(InnerPH).second)
1362           // The only way to reach the preheader is through the loop body
1363           // itself so if it has been visited the loop is already handled.
1364           continue;
1365 
1366         // Insert all of the blocks (other than those already present) into
1367         // the loop set. We expect at least the block that led us to find the
1368         // inner loop to be in the block set, but we may also have other loop
1369         // blocks if they were already enqueued as predecessors of some other
1370         // outer loop block.
1371         for (auto *InnerBB : InnerL->blocks()) {
1372           if (InnerBB == BB) {
1373             assert(LoopBlockSet.count(InnerBB) &&
1374                    "Block should already be in the set!");
1375             continue;
1376           }
1377 
1378           LoopBlockSet.insert(InnerBB);
1379         }
1380 
1381         // Add the preheader to the worklist so we will continue past the
1382         // loop body.
1383         Worklist.push_back(InnerPH);
1384         continue;
1385       }
1386 
1387     // Insert any predecessors that were in the original loop into the new
1388     // set, and if the insert is successful, add them to the worklist.
1389     for (auto *Pred : predecessors(BB))
1390       if (L.contains(Pred) && LoopBlockSet.insert(Pred).second)
1391         Worklist.push_back(Pred);
1392   }
1393 
1394   // We've found all the blocks participating in the loop, return our completed
1395   // set.
1396   return LoopBlockSet;
1397 }
1398 
1399 /// Rebuild a loop after unswitching removes some subset of blocks and edges.
1400 ///
1401 /// The removal may have removed some child loops entirely but cannot have
1402 /// disturbed any remaining child loops. However, they may need to be hoisted
1403 /// to the parent loop (or to be top-level loops). The original loop may be
1404 /// completely removed.
1405 ///
1406 /// The sibling loops resulting from this update are returned. If the original
1407 /// loop remains a valid loop, it will be the first entry in this list with all
1408 /// of the newly sibling loops following it.
1409 ///
1410 /// Returns true if the loop remains a loop after unswitching, and false if it
1411 /// is no longer a loop after unswitching (and should not continue to be
1412 /// referenced).
1413 static bool rebuildLoopAfterUnswitch(Loop &L, ArrayRef<BasicBlock *> ExitBlocks,
1414                                      LoopInfo &LI,
1415                                      SmallVectorImpl<Loop *> &HoistedLoops) {
1416   auto *PH = L.getLoopPreheader();
1417 
1418   // Compute the actual parent loop from the exit blocks. Because we may have
1419   // pruned some exits the loop may be different from the original parent.
1420   Loop *ParentL = nullptr;
1421   SmallVector<Loop *, 4> ExitLoops;
1422   SmallVector<BasicBlock *, 4> ExitsInLoops;
1423   ExitsInLoops.reserve(ExitBlocks.size());
1424   for (auto *ExitBB : ExitBlocks)
1425     if (Loop *ExitL = LI.getLoopFor(ExitBB)) {
1426       ExitLoops.push_back(ExitL);
1427       ExitsInLoops.push_back(ExitBB);
1428       if (!ParentL || (ParentL != ExitL && ParentL->contains(ExitL)))
1429         ParentL = ExitL;
1430     }
1431 
1432   // Recompute the blocks participating in this loop. This may be empty if it
1433   // is no longer a loop.
1434   auto LoopBlockSet = recomputeLoopBlockSet(L, LI);
1435 
1436   // If we still have a loop, we need to re-set the loop's parent as the exit
1437   // block set changing may have moved it within the loop nest. Note that this
1438   // can only happen when this loop has a parent as it can only hoist the loop
1439   // *up* the nest.
1440   if (!LoopBlockSet.empty() && L.getParentLoop() != ParentL) {
1441     // Remove this loop's (original) blocks from all of the intervening loops.
1442     for (Loop *IL = L.getParentLoop(); IL != ParentL;
1443          IL = IL->getParentLoop()) {
1444       IL->getBlocksSet().erase(PH);
1445       for (auto *BB : L.blocks())
1446         IL->getBlocksSet().erase(BB);
1447       llvm::erase_if(IL->getBlocksVector(), [&](BasicBlock *BB) {
1448         return BB == PH || L.contains(BB);
1449       });
1450     }
1451 
1452     LI.changeLoopFor(PH, ParentL);
1453     L.getParentLoop()->removeChildLoop(&L);
1454     if (ParentL)
1455       ParentL->addChildLoop(&L);
1456     else
1457       LI.addTopLevelLoop(&L);
1458   }
1459 
1460   // Now we update all the blocks which are no longer within the loop.
1461   auto &Blocks = L.getBlocksVector();
1462   auto BlocksSplitI =
1463       LoopBlockSet.empty()
1464           ? Blocks.begin()
1465           : std::stable_partition(
1466                 Blocks.begin(), Blocks.end(),
1467                 [&](BasicBlock *BB) { return LoopBlockSet.count(BB); });
1468 
1469   // Before we erase the list of unlooped blocks, build a set of them.
1470   SmallPtrSet<BasicBlock *, 16> UnloopedBlocks(BlocksSplitI, Blocks.end());
1471   if (LoopBlockSet.empty())
1472     UnloopedBlocks.insert(PH);
1473 
1474   // Now erase these blocks from the loop.
1475   for (auto *BB : make_range(BlocksSplitI, Blocks.end()))
1476     L.getBlocksSet().erase(BB);
1477   Blocks.erase(BlocksSplitI, Blocks.end());
1478 
1479   // Sort the exits in ascending loop depth, we'll work backwards across these
1480   // to process them inside out.
1481   std::stable_sort(ExitsInLoops.begin(), ExitsInLoops.end(),
1482                    [&](BasicBlock *LHS, BasicBlock *RHS) {
1483                      return LI.getLoopDepth(LHS) < LI.getLoopDepth(RHS);
1484                    });
1485 
1486   // We'll build up a set for each exit loop.
1487   SmallPtrSet<BasicBlock *, 16> NewExitLoopBlocks;
1488   Loop *PrevExitL = L.getParentLoop(); // The deepest possible exit loop.
1489 
1490   auto RemoveUnloopedBlocksFromLoop =
1491       [](Loop &L, SmallPtrSetImpl<BasicBlock *> &UnloopedBlocks) {
1492         for (auto *BB : UnloopedBlocks)
1493           L.getBlocksSet().erase(BB);
1494         llvm::erase_if(L.getBlocksVector(), [&](BasicBlock *BB) {
1495           return UnloopedBlocks.count(BB);
1496         });
1497       };
1498 
1499   SmallVector<BasicBlock *, 16> Worklist;
1500   while (!UnloopedBlocks.empty() && !ExitsInLoops.empty()) {
1501     assert(Worklist.empty() && "Didn't clear worklist!");
1502     assert(NewExitLoopBlocks.empty() && "Didn't clear loop set!");
1503 
1504     // Grab the next exit block, in decreasing loop depth order.
1505     BasicBlock *ExitBB = ExitsInLoops.pop_back_val();
1506     Loop &ExitL = *LI.getLoopFor(ExitBB);
1507     assert(ExitL.contains(&L) && "Exit loop must contain the inner loop!");
1508 
1509     // Erase all of the unlooped blocks from the loops between the previous
1510     // exit loop and this exit loop. This works because the ExitInLoops list is
1511     // sorted in increasing order of loop depth and thus we visit loops in
1512     // decreasing order of loop depth.
1513     for (; PrevExitL != &ExitL; PrevExitL = PrevExitL->getParentLoop())
1514       RemoveUnloopedBlocksFromLoop(*PrevExitL, UnloopedBlocks);
1515 
1516     // Walk the CFG back until we hit the cloned PH adding everything reachable
1517     // and in the unlooped set to this exit block's loop.
1518     Worklist.push_back(ExitBB);
1519     do {
1520       BasicBlock *BB = Worklist.pop_back_val();
1521       // We can stop recursing at the cloned preheader (if we get there).
1522       if (BB == PH)
1523         continue;
1524 
1525       for (BasicBlock *PredBB : predecessors(BB)) {
1526         // If this pred has already been moved to our set or is part of some
1527         // (inner) loop, no update needed.
1528         if (!UnloopedBlocks.erase(PredBB)) {
1529           assert((NewExitLoopBlocks.count(PredBB) ||
1530                   ExitL.contains(LI.getLoopFor(PredBB))) &&
1531                  "Predecessor not in a nested loop (or already visited)!");
1532           continue;
1533         }
1534 
1535         // We just insert into the loop set here. We'll add these blocks to the
1536         // exit loop after we build up the set in a deterministic order rather
1537         // than the predecessor-influenced visit order.
1538         bool Inserted = NewExitLoopBlocks.insert(PredBB).second;
1539         (void)Inserted;
1540         assert(Inserted && "Should only visit an unlooped block once!");
1541 
1542         // And recurse through to its predecessors.
1543         Worklist.push_back(PredBB);
1544       }
1545     } while (!Worklist.empty());
1546 
1547     // If blocks in this exit loop were directly part of the original loop (as
1548     // opposed to a child loop) update the map to point to this exit loop. This
1549     // just updates a map and so the fact that the order is unstable is fine.
1550     for (auto *BB : NewExitLoopBlocks)
1551       if (Loop *BBL = LI.getLoopFor(BB))
1552         if (BBL == &L || !L.contains(BBL))
1553           LI.changeLoopFor(BB, &ExitL);
1554 
1555     // We will remove the remaining unlooped blocks from this loop in the next
1556     // iteration or below.
1557     NewExitLoopBlocks.clear();
1558   }
1559 
1560   // Any remaining unlooped blocks are no longer part of any loop unless they
1561   // are part of some child loop.
1562   for (; PrevExitL; PrevExitL = PrevExitL->getParentLoop())
1563     RemoveUnloopedBlocksFromLoop(*PrevExitL, UnloopedBlocks);
1564   for (auto *BB : UnloopedBlocks)
1565     if (Loop *BBL = LI.getLoopFor(BB))
1566       if (BBL == &L || !L.contains(BBL))
1567         LI.changeLoopFor(BB, nullptr);
1568 
1569   // Sink all the child loops whose headers are no longer in the loop set to
1570   // the parent (or to be top level loops). We reach into the loop and directly
1571   // update its subloop vector to make this batch update efficient.
1572   auto &SubLoops = L.getSubLoopsVector();
1573   auto SubLoopsSplitI =
1574       LoopBlockSet.empty()
1575           ? SubLoops.begin()
1576           : std::stable_partition(
1577                 SubLoops.begin(), SubLoops.end(), [&](Loop *SubL) {
1578                   return LoopBlockSet.count(SubL->getHeader());
1579                 });
1580   for (auto *HoistedL : make_range(SubLoopsSplitI, SubLoops.end())) {
1581     HoistedLoops.push_back(HoistedL);
1582     HoistedL->setParentLoop(nullptr);
1583 
1584     // To compute the new parent of this hoisted loop we look at where we
1585     // placed the preheader above. We can't lookup the header itself because we
1586     // retained the mapping from the header to the hoisted loop. But the
1587     // preheader and header should have the exact same new parent computed
1588     // based on the set of exit blocks from the original loop as the preheader
1589     // is a predecessor of the header and so reached in the reverse walk. And
1590     // because the loops were all in simplified form the preheader of the
1591     // hoisted loop can't be part of some *other* loop.
1592     if (auto *NewParentL = LI.getLoopFor(HoistedL->getLoopPreheader()))
1593       NewParentL->addChildLoop(HoistedL);
1594     else
1595       LI.addTopLevelLoop(HoistedL);
1596   }
1597   SubLoops.erase(SubLoopsSplitI, SubLoops.end());
1598 
1599   // Actually delete the loop if nothing remained within it.
1600   if (Blocks.empty()) {
1601     assert(SubLoops.empty() &&
1602            "Failed to remove all subloops from the original loop!");
1603     if (Loop *ParentL = L.getParentLoop())
1604       ParentL->removeChildLoop(llvm::find(*ParentL, &L));
1605     else
1606       LI.removeLoop(llvm::find(LI, &L));
1607     LI.destroy(&L);
1608     return false;
1609   }
1610 
1611   return true;
1612 }
1613 
1614 /// Helper to visit a dominator subtree, invoking a callable on each node.
1615 ///
1616 /// Returning false at any point will stop walking past that node of the tree.
1617 template <typename CallableT>
1618 void visitDomSubTree(DominatorTree &DT, BasicBlock *BB, CallableT Callable) {
1619   SmallVector<DomTreeNode *, 4> DomWorklist;
1620   DomWorklist.push_back(DT[BB]);
1621 #ifndef NDEBUG
1622   SmallPtrSet<DomTreeNode *, 4> Visited;
1623   Visited.insert(DT[BB]);
1624 #endif
1625   do {
1626     DomTreeNode *N = DomWorklist.pop_back_val();
1627 
1628     // Visit this node.
1629     if (!Callable(N->getBlock()))
1630       continue;
1631 
1632     // Accumulate the child nodes.
1633     for (DomTreeNode *ChildN : *N) {
1634       assert(Visited.insert(ChildN).second &&
1635              "Cannot visit a node twice when walking a tree!");
1636       DomWorklist.push_back(ChildN);
1637     }
1638   } while (!DomWorklist.empty());
1639 }
1640 
1641 /// Take an invariant branch that has been determined to be safe and worthwhile
1642 /// to unswitch despite being non-trivial to do so and perform the unswitch.
1643 ///
1644 /// This directly updates the CFG to hoist the predicate out of the loop, and
1645 /// clone the necessary parts of the loop to maintain behavior.
1646 ///
1647 /// It also updates both dominator tree and loopinfo based on the unswitching.
1648 ///
1649 /// Once unswitching has been performed it runs the provided callback to report
1650 /// the new loops and no-longer valid loops to the caller.
1651 static bool unswitchInvariantBranch(
1652     Loop &L, BranchInst &BI, DominatorTree &DT, LoopInfo &LI,
1653     AssumptionCache &AC,
1654     function_ref<void(bool, ArrayRef<Loop *>)> NonTrivialUnswitchCB) {
1655   assert(BI.isConditional() && "Can only unswitch a conditional branch!");
1656   assert(L.isLoopInvariant(BI.getCondition()) &&
1657          "Can only unswitch an invariant branch condition!");
1658 
1659   // Constant and BBs tracking the cloned and continuing successor.
1660   const int ClonedSucc = 0;
1661   auto *ParentBB = BI.getParent();
1662   auto *UnswitchedSuccBB = BI.getSuccessor(ClonedSucc);
1663   auto *ContinueSuccBB = BI.getSuccessor(1 - ClonedSucc);
1664 
1665   assert(UnswitchedSuccBB != ContinueSuccBB &&
1666          "Should not unswitch a branch that always goes to the same place!");
1667 
1668   // The branch should be in this exact loop. Any inner loop's invariant branch
1669   // should be handled by unswitching that inner loop. The caller of this
1670   // routine should filter out any candidates that remain (but were skipped for
1671   // whatever reason).
1672   assert(LI.getLoopFor(ParentBB) == &L && "Branch in an inner loop!");
1673 
1674   SmallVector<BasicBlock *, 4> ExitBlocks;
1675   L.getUniqueExitBlocks(ExitBlocks);
1676 
1677   // We cannot unswitch if exit blocks contain a cleanuppad instruction as we
1678   // don't know how to split those exit blocks.
1679   // FIXME: We should teach SplitBlock to handle this and remove this
1680   // restriction.
1681   for (auto *ExitBB : ExitBlocks)
1682     if (isa<CleanupPadInst>(ExitBB->getFirstNonPHI()))
1683       return false;
1684 
1685   SmallPtrSet<BasicBlock *, 4> ExitBlockSet(ExitBlocks.begin(),
1686                                             ExitBlocks.end());
1687 
1688   // Compute the parent loop now before we start hacking on things.
1689   Loop *ParentL = L.getParentLoop();
1690 
1691   // Compute the outer-most loop containing one of our exit blocks. This is the
1692   // furthest up our loopnest which can be mutated, which we will use below to
1693   // update things.
1694   Loop *OuterExitL = &L;
1695   for (auto *ExitBB : ExitBlocks) {
1696     Loop *NewOuterExitL = LI.getLoopFor(ExitBB);
1697     if (!NewOuterExitL) {
1698       // We exited the entire nest with this block, so we're done.
1699       OuterExitL = nullptr;
1700       break;
1701     }
1702     if (NewOuterExitL != OuterExitL && NewOuterExitL->contains(OuterExitL))
1703       OuterExitL = NewOuterExitL;
1704   }
1705 
1706   // If the edge we *aren't* cloning in the unswitch (the continuing edge)
1707   // dominates its target, we can skip cloning the dominated region of the loop
1708   // and its exits. We compute this as a set of nodes to be skipped.
1709   SmallPtrSet<BasicBlock *, 4> SkippedLoopAndExitBlocks;
1710   if (ContinueSuccBB->getUniquePredecessor() ||
1711       llvm::all_of(predecessors(ContinueSuccBB), [&](BasicBlock *PredBB) {
1712         return PredBB == ParentBB || DT.dominates(ContinueSuccBB, PredBB);
1713       })) {
1714     visitDomSubTree(DT, ContinueSuccBB, [&](BasicBlock *BB) {
1715       SkippedLoopAndExitBlocks.insert(BB);
1716       return true;
1717     });
1718   }
1719   // Similarly, if the edge we *are* cloning in the unswitch (the unswitched
1720   // edge) dominates its target, we will end up with dead nodes in the original
1721   // loop and its exits that will need to be deleted. Here, we just retain that
1722   // the property holds and will compute the deleted set later.
1723   bool DeleteUnswitchedSucc =
1724       UnswitchedSuccBB->getUniquePredecessor() ||
1725       llvm::all_of(predecessors(UnswitchedSuccBB), [&](BasicBlock *PredBB) {
1726         return PredBB == ParentBB || DT.dominates(UnswitchedSuccBB, PredBB);
1727       });
1728 
1729   // Split the preheader, so that we know that there is a safe place to insert
1730   // the conditional branch. We will change the preheader to have a conditional
1731   // branch on LoopCond. The original preheader will become the split point
1732   // between the unswitched versions, and we will have a new preheader for the
1733   // original loop.
1734   BasicBlock *SplitBB = L.getLoopPreheader();
1735   BasicBlock *LoopPH = SplitEdge(SplitBB, L.getHeader(), &DT, &LI);
1736 
1737   // Keep a mapping for the cloned values.
1738   ValueToValueMapTy VMap;
1739 
1740   // Build the cloned blocks from the loop.
1741   auto *ClonedPH = buildClonedLoopBlocks(
1742       L, LoopPH, SplitBB, ExitBlocks, ParentBB, UnswitchedSuccBB,
1743       ContinueSuccBB, SkippedLoopAndExitBlocks, VMap, AC, DT, LI);
1744 
1745   // Build the cloned loop structure itself. This may be substantially
1746   // different from the original structure due to the simplified CFG. This also
1747   // handles inserting all the cloned blocks into the correct loops.
1748   SmallVector<Loop *, 4> NonChildClonedLoops;
1749   Loop *ClonedL =
1750       buildClonedLoops(L, ExitBlocks, VMap, LI, NonChildClonedLoops);
1751 
1752   // Remove the parent as a predecessor of the unswitched successor.
1753   UnswitchedSuccBB->removePredecessor(ParentBB, /*DontDeleteUselessPHIs*/ true);
1754 
1755   // Now splice the branch from the original loop and use it to select between
1756   // the two loops.
1757   SplitBB->getTerminator()->eraseFromParent();
1758   SplitBB->getInstList().splice(SplitBB->end(), ParentBB->getInstList(), BI);
1759   BI.setSuccessor(ClonedSucc, ClonedPH);
1760   BI.setSuccessor(1 - ClonedSucc, LoopPH);
1761 
1762   // Create a new unconditional branch to the continuing block (as opposed to
1763   // the one cloned).
1764   BranchInst::Create(ContinueSuccBB, ParentBB);
1765 
1766   // Delete anything that was made dead in the original loop due to
1767   // unswitching.
1768   if (DeleteUnswitchedSucc)
1769     deleteDeadBlocksFromLoop(L, UnswitchedSuccBB, ExitBlocks, DT, LI);
1770 
1771   SmallVector<Loop *, 4> HoistedLoops;
1772   bool IsStillLoop = rebuildLoopAfterUnswitch(L, ExitBlocks, LI, HoistedLoops);
1773 
1774   // This will have completely invalidated the dominator tree. We can't easily
1775   // bound how much is invalid because in some cases we will refine the
1776   // predecessor set of exit blocks of the loop which can move large unrelated
1777   // regions of code into a new subtree.
1778   //
1779   // FIXME: Eventually, we should use an incremental update utility that
1780   // leverages the existing information in the dominator tree (and potentially
1781   // the nature of the change) to more efficiently update things.
1782   DT.recalculate(*SplitBB->getParent());
1783 
1784   // We can change which blocks are exit blocks of all the cloned sibling
1785   // loops, the current loop, and any parent loops which shared exit blocks
1786   // with the current loop. As a consequence, we need to re-form LCSSA for
1787   // them. But we shouldn't need to re-form LCSSA for any child loops.
1788   // FIXME: This could be made more efficient by tracking which exit blocks are
1789   // new, and focusing on them, but that isn't likely to be necessary.
1790   //
1791   // In order to reasonably rebuild LCSSA we need to walk inside-out across the
1792   // loop nest and update every loop that could have had its exits changed. We
1793   // also need to cover any intervening loops. We add all of these loops to
1794   // a list and sort them by loop depth to achieve this without updating
1795   // unnecessary loops.
1796   auto UpdateLCSSA = [&](Loop &UpdateL) {
1797 #ifndef NDEBUG
1798     for (Loop *ChildL : UpdateL)
1799       assert(ChildL->isRecursivelyLCSSAForm(DT, LI) &&
1800              "Perturbed a child loop's LCSSA form!");
1801 #endif
1802     formLCSSA(UpdateL, DT, &LI, nullptr);
1803   };
1804 
1805   // For non-child cloned loops and hoisted loops, we just need to update LCSSA
1806   // and we can do it in any order as they don't nest relative to each other.
1807   for (Loop *UpdatedL : llvm::concat<Loop *>(NonChildClonedLoops, HoistedLoops))
1808     UpdateLCSSA(*UpdatedL);
1809 
1810   // If the original loop had exit blocks, walk up through the outer most loop
1811   // of those exit blocks to update LCSSA and form updated dedicated exits.
1812   if (OuterExitL != &L) {
1813     SmallVector<Loop *, 4> OuterLoops;
1814     // We start with the cloned loop and the current loop if they are loops and
1815     // move toward OuterExitL. Also, if either the cloned loop or the current
1816     // loop have become top level loops we need to walk all the way out.
1817     if (ClonedL) {
1818       OuterLoops.push_back(ClonedL);
1819       if (!ClonedL->getParentLoop())
1820         OuterExitL = nullptr;
1821     }
1822     if (IsStillLoop) {
1823       OuterLoops.push_back(&L);
1824       if (!L.getParentLoop())
1825         OuterExitL = nullptr;
1826     }
1827     // Grab all of the enclosing loops now.
1828     for (Loop *OuterL = ParentL; OuterL != OuterExitL;
1829          OuterL = OuterL->getParentLoop())
1830       OuterLoops.push_back(OuterL);
1831 
1832     // Finally, update our list of outer loops. This is nicely ordered to work
1833     // inside-out.
1834     for (Loop *OuterL : OuterLoops) {
1835       // First build LCSSA for this loop so that we can preserve it when
1836       // forming dedicated exits. We don't want to perturb some other loop's
1837       // LCSSA while doing that CFG edit.
1838       UpdateLCSSA(*OuterL);
1839 
1840       // For loops reached by this loop's original exit blocks we may
1841       // introduced new, non-dedicated exits. At least try to re-form dedicated
1842       // exits for these loops. This may fail if they couldn't have dedicated
1843       // exits to start with.
1844       formDedicatedExitBlocks(OuterL, &DT, &LI, /*PreserveLCSSA*/ true);
1845     }
1846   }
1847 
1848 #ifndef NDEBUG
1849   // Verify the entire loop structure to catch any incorrect updates before we
1850   // progress in the pass pipeline.
1851   LI.verify(DT);
1852 #endif
1853 
1854   // Now that we've unswitched something, make callbacks to report the changes.
1855   // For that we need to merge together the updated loops and the cloned loops
1856   // and check whether the original loop survived.
1857   SmallVector<Loop *, 4> SibLoops;
1858   for (Loop *UpdatedL : llvm::concat<Loop *>(NonChildClonedLoops, HoistedLoops))
1859     if (UpdatedL->getParentLoop() == ParentL)
1860       SibLoops.push_back(UpdatedL);
1861   NonTrivialUnswitchCB(IsStillLoop, SibLoops);
1862 
1863   ++NumBranches;
1864   return true;
1865 }
1866 
1867 /// Recursively compute the cost of a dominator subtree based on the per-block
1868 /// cost map provided.
1869 ///
1870 /// The recursive computation is memozied into the provided DT-indexed cost map
1871 /// to allow querying it for most nodes in the domtree without it becoming
1872 /// quadratic.
1873 static int
1874 computeDomSubtreeCost(DomTreeNode &N,
1875                       const SmallDenseMap<BasicBlock *, int, 4> &BBCostMap,
1876                       SmallDenseMap<DomTreeNode *, int, 4> &DTCostMap) {
1877   // Don't accumulate cost (or recurse through) blocks not in our block cost
1878   // map and thus not part of the duplication cost being considered.
1879   auto BBCostIt = BBCostMap.find(N.getBlock());
1880   if (BBCostIt == BBCostMap.end())
1881     return 0;
1882 
1883   // Lookup this node to see if we already computed its cost.
1884   auto DTCostIt = DTCostMap.find(&N);
1885   if (DTCostIt != DTCostMap.end())
1886     return DTCostIt->second;
1887 
1888   // If not, we have to compute it. We can't use insert above and update
1889   // because computing the cost may insert more things into the map.
1890   int Cost = std::accumulate(
1891       N.begin(), N.end(), BBCostIt->second, [&](int Sum, DomTreeNode *ChildN) {
1892         return Sum + computeDomSubtreeCost(*ChildN, BBCostMap, DTCostMap);
1893       });
1894   bool Inserted = DTCostMap.insert({&N, Cost}).second;
1895   (void)Inserted;
1896   assert(Inserted && "Should not insert a node while visiting children!");
1897   return Cost;
1898 }
1899 
1900 /// Unswitch control flow predicated on loop invariant conditions.
1901 ///
1902 /// This first hoists all branches or switches which are trivial (IE, do not
1903 /// require duplicating any part of the loop) out of the loop body. It then
1904 /// looks at other loop invariant control flows and tries to unswitch those as
1905 /// well by cloning the loop if the result is small enough.
1906 static bool
1907 unswitchLoop(Loop &L, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC,
1908              TargetTransformInfo &TTI, bool NonTrivial,
1909              function_ref<void(bool, ArrayRef<Loop *>)> NonTrivialUnswitchCB) {
1910   assert(L.isRecursivelyLCSSAForm(DT, LI) &&
1911          "Loops must be in LCSSA form before unswitching.");
1912   bool Changed = false;
1913 
1914   // Must be in loop simplified form: we need a preheader and dedicated exits.
1915   if (!L.isLoopSimplifyForm())
1916     return false;
1917 
1918   // Try trivial unswitch first before loop over other basic blocks in the loop.
1919   Changed |= unswitchAllTrivialConditions(L, DT, LI);
1920 
1921   // If we're not doing non-trivial unswitching, we're done. We both accept
1922   // a parameter but also check a local flag that can be used for testing
1923   // a debugging.
1924   if (!NonTrivial && !EnableNonTrivialUnswitch)
1925     return Changed;
1926 
1927   // Collect all remaining invariant branch conditions within this loop (as
1928   // opposed to an inner loop which would be handled when visiting that inner
1929   // loop).
1930   SmallVector<TerminatorInst *, 4> UnswitchCandidates;
1931   for (auto *BB : L.blocks())
1932     if (LI.getLoopFor(BB) == &L)
1933       if (auto *BI = dyn_cast<BranchInst>(BB->getTerminator()))
1934         if (BI->isConditional() && L.isLoopInvariant(BI->getCondition()) &&
1935             BI->getSuccessor(0) != BI->getSuccessor(1))
1936           UnswitchCandidates.push_back(BI);
1937 
1938   // If we didn't find any candidates, we're done.
1939   if (UnswitchCandidates.empty())
1940     return Changed;
1941 
1942   // Check if there are irreducible CFG cycles in this loop. If so, we cannot
1943   // easily unswitch non-trivial edges out of the loop. Doing so might turn the
1944   // irreducible control flow into reducible control flow and introduce new
1945   // loops "out of thin air". If we ever discover important use cases for doing
1946   // this, we can add support to loop unswitch, but it is a lot of complexity
1947   // for what seems little or no real world benifit.
1948   LoopBlocksRPO RPOT(&L);
1949   RPOT.perform(&LI);
1950   if (containsIrreducibleCFG<const BasicBlock *>(RPOT, LI))
1951     return Changed;
1952 
1953   DEBUG(dbgs() << "Considering " << UnswitchCandidates.size()
1954                << " non-trivial loop invariant conditions for unswitching.\n");
1955 
1956   // Given that unswitching these terminators will require duplicating parts of
1957   // the loop, so we need to be able to model that cost. Compute the ephemeral
1958   // values and set up a data structure to hold per-BB costs. We cache each
1959   // block's cost so that we don't recompute this when considering different
1960   // subsets of the loop for duplication during unswitching.
1961   SmallPtrSet<const Value *, 4> EphValues;
1962   CodeMetrics::collectEphemeralValues(&L, &AC, EphValues);
1963   SmallDenseMap<BasicBlock *, int, 4> BBCostMap;
1964 
1965   // Compute the cost of each block, as well as the total loop cost. Also, bail
1966   // out if we see instructions which are incompatible with loop unswitching
1967   // (convergent, noduplicate, or cross-basic-block tokens).
1968   // FIXME: We might be able to safely handle some of these in non-duplicated
1969   // regions.
1970   int LoopCost = 0;
1971   for (auto *BB : L.blocks()) {
1972     int Cost = 0;
1973     for (auto &I : *BB) {
1974       if (EphValues.count(&I))
1975         continue;
1976 
1977       if (I.getType()->isTokenTy() && I.isUsedOutsideOfBlock(BB))
1978         return Changed;
1979       if (auto CS = CallSite(&I))
1980         if (CS.isConvergent() || CS.cannotDuplicate())
1981           return Changed;
1982 
1983       Cost += TTI.getUserCost(&I);
1984     }
1985     assert(Cost >= 0 && "Must not have negative costs!");
1986     LoopCost += Cost;
1987     assert(LoopCost >= 0 && "Must not have negative loop costs!");
1988     BBCostMap[BB] = Cost;
1989   }
1990   DEBUG(dbgs() << "  Total loop cost: " << LoopCost << "\n");
1991 
1992   // Now we find the best candidate by searching for the one with the following
1993   // properties in order:
1994   //
1995   // 1) An unswitching cost below the threshold
1996   // 2) The smallest number of duplicated unswitch candidates (to avoid
1997   //    creating redundant subsequent unswitching)
1998   // 3) The smallest cost after unswitching.
1999   //
2000   // We prioritize reducing fanout of unswitch candidates provided the cost
2001   // remains below the threshold because this has a multiplicative effect.
2002   //
2003   // This requires memoizing each dominator subtree to avoid redundant work.
2004   //
2005   // FIXME: Need to actually do the number of candidates part above.
2006   SmallDenseMap<DomTreeNode *, int, 4> DTCostMap;
2007   // Given a terminator which might be unswitched, computes the non-duplicated
2008   // cost for that terminator.
2009   auto ComputeUnswitchedCost = [&](TerminatorInst *TI) {
2010     BasicBlock &BB = *TI->getParent();
2011     SmallPtrSet<BasicBlock *, 4> Visited;
2012 
2013     int Cost = LoopCost;
2014     for (BasicBlock *SuccBB : successors(&BB)) {
2015       // Don't count successors more than once.
2016       if (!Visited.insert(SuccBB).second)
2017         continue;
2018 
2019       // This successor's domtree will not need to be duplicated after
2020       // unswitching if the edge to the successor dominates it (and thus the
2021       // entire tree). This essentially means there is no other path into this
2022       // subtree and so it will end up live in only one clone of the loop.
2023       if (SuccBB->getUniquePredecessor() ||
2024           llvm::all_of(predecessors(SuccBB), [&](BasicBlock *PredBB) {
2025             return PredBB == &BB || DT.dominates(SuccBB, PredBB);
2026           })) {
2027         Cost -= computeDomSubtreeCost(*DT[SuccBB], BBCostMap, DTCostMap);
2028         assert(Cost >= 0 &&
2029                "Non-duplicated cost should never exceed total loop cost!");
2030       }
2031     }
2032 
2033     // Now scale the cost by the number of unique successors minus one. We
2034     // subtract one because there is already at least one copy of the entire
2035     // loop. This is computing the new cost of unswitching a condition.
2036     assert(Visited.size() > 1 &&
2037            "Cannot unswitch a condition without multiple distinct successors!");
2038     return Cost * (Visited.size() - 1);
2039   };
2040   TerminatorInst *BestUnswitchTI = nullptr;
2041   int BestUnswitchCost;
2042   for (TerminatorInst *CandidateTI : UnswitchCandidates) {
2043     int CandidateCost = ComputeUnswitchedCost(CandidateTI);
2044     DEBUG(dbgs() << "  Computed cost of " << CandidateCost
2045                  << " for unswitch candidate: " << *CandidateTI << "\n");
2046     if (!BestUnswitchTI || CandidateCost < BestUnswitchCost) {
2047       BestUnswitchTI = CandidateTI;
2048       BestUnswitchCost = CandidateCost;
2049     }
2050   }
2051 
2052   if (BestUnswitchCost < UnswitchThreshold) {
2053     DEBUG(dbgs() << "  Trying to unswitch non-trivial (cost = "
2054                  << BestUnswitchCost << ") branch: " << *BestUnswitchTI
2055                  << "\n");
2056     Changed |= unswitchInvariantBranch(L, cast<BranchInst>(*BestUnswitchTI), DT,
2057                                        LI, AC, NonTrivialUnswitchCB);
2058   } else {
2059     DEBUG(dbgs() << "Cannot unswitch, lowest cost found: " << BestUnswitchCost
2060                  << "\n");
2061   }
2062 
2063   return Changed;
2064 }
2065 
2066 PreservedAnalyses SimpleLoopUnswitchPass::run(Loop &L, LoopAnalysisManager &AM,
2067                                               LoopStandardAnalysisResults &AR,
2068                                               LPMUpdater &U) {
2069   Function &F = *L.getHeader()->getParent();
2070   (void)F;
2071 
2072   DEBUG(dbgs() << "Unswitching loop in " << F.getName() << ": " << L << "\n");
2073 
2074   // Save the current loop name in a variable so that we can report it even
2075   // after it has been deleted.
2076   std::string LoopName = L.getName();
2077 
2078   auto NonTrivialUnswitchCB = [&L, &U, &LoopName](bool CurrentLoopValid,
2079                                                   ArrayRef<Loop *> NewLoops) {
2080     // If we did a non-trivial unswitch, we have added new (cloned) loops.
2081     U.addSiblingLoops(NewLoops);
2082 
2083     // If the current loop remains valid, we should revisit it to catch any
2084     // other unswitch opportunities. Otherwise, we need to mark it as deleted.
2085     if (CurrentLoopValid)
2086       U.revisitCurrentLoop();
2087     else
2088       U.markLoopAsDeleted(L, LoopName);
2089   };
2090 
2091   if (!unswitchLoop(L, AR.DT, AR.LI, AR.AC, AR.TTI, NonTrivial,
2092                     NonTrivialUnswitchCB))
2093     return PreservedAnalyses::all();
2094 
2095   // Historically this pass has had issues with the dominator tree so verify it
2096   // in asserts builds.
2097   assert(AR.DT.verify(DominatorTree::VerificationLevel::Fast));
2098   return getLoopPassPreservedAnalyses();
2099 }
2100 
2101 namespace {
2102 
2103 class SimpleLoopUnswitchLegacyPass : public LoopPass {
2104   bool NonTrivial;
2105 
2106 public:
2107   static char ID; // Pass ID, replacement for typeid
2108 
2109   explicit SimpleLoopUnswitchLegacyPass(bool NonTrivial = false)
2110       : LoopPass(ID), NonTrivial(NonTrivial) {
2111     initializeSimpleLoopUnswitchLegacyPassPass(
2112         *PassRegistry::getPassRegistry());
2113   }
2114 
2115   bool runOnLoop(Loop *L, LPPassManager &LPM) override;
2116 
2117   void getAnalysisUsage(AnalysisUsage &AU) const override {
2118     AU.addRequired<AssumptionCacheTracker>();
2119     AU.addRequired<TargetTransformInfoWrapperPass>();
2120     getLoopAnalysisUsage(AU);
2121   }
2122 };
2123 
2124 } // end anonymous namespace
2125 
2126 bool SimpleLoopUnswitchLegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) {
2127   if (skipLoop(L))
2128     return false;
2129 
2130   Function &F = *L->getHeader()->getParent();
2131 
2132   DEBUG(dbgs() << "Unswitching loop in " << F.getName() << ": " << *L << "\n");
2133 
2134   auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2135   auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
2136   auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
2137   auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
2138 
2139   auto NonTrivialUnswitchCB = [&L, &LPM](bool CurrentLoopValid,
2140                                          ArrayRef<Loop *> NewLoops) {
2141     // If we did a non-trivial unswitch, we have added new (cloned) loops.
2142     for (auto *NewL : NewLoops)
2143       LPM.addLoop(*NewL);
2144 
2145     // If the current loop remains valid, re-add it to the queue. This is
2146     // a little wasteful as we'll finish processing the current loop as well,
2147     // but it is the best we can do in the old PM.
2148     if (CurrentLoopValid)
2149       LPM.addLoop(*L);
2150     else
2151       LPM.markLoopAsDeleted(*L);
2152   };
2153 
2154   bool Changed =
2155       unswitchLoop(*L, DT, LI, AC, TTI, NonTrivial, NonTrivialUnswitchCB);
2156 
2157   // If anything was unswitched, also clear any cached information about this
2158   // loop.
2159   LPM.deleteSimpleAnalysisLoop(L);
2160 
2161   // Historically this pass has had issues with the dominator tree so verify it
2162   // in asserts builds.
2163   assert(DT.verify(DominatorTree::VerificationLevel::Fast));
2164 
2165   return Changed;
2166 }
2167 
2168 char SimpleLoopUnswitchLegacyPass::ID = 0;
2169 INITIALIZE_PASS_BEGIN(SimpleLoopUnswitchLegacyPass, "simple-loop-unswitch",
2170                       "Simple unswitch loops", false, false)
2171 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
2172 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
2173 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
2174 INITIALIZE_PASS_DEPENDENCY(LoopPass)
2175 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
2176 INITIALIZE_PASS_END(SimpleLoopUnswitchLegacyPass, "simple-loop-unswitch",
2177                     "Simple unswitch loops", false, false)
2178 
2179 Pass *llvm::createSimpleLoopUnswitchLegacyPass(bool NonTrivial) {
2180   return new SimpleLoopUnswitchLegacyPass(NonTrivial);
2181 }
2182