xref: /freebsd/contrib/llvm-project/llvm/lib/Transforms/Scalar/LoopSimplifyCFG.cpp (revision e6bfd18d21b225af6a0ed67ceeaf1293b7b9eba5)
1 //===--------- LoopSimplifyCFG.cpp - Loop CFG Simplification Pass ---------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements the Loop SimplifyCFG Pass. This pass is responsible for
10 // basic loop CFG cleanup, primarily to assist other loop passes. If you
11 // encounter a noncanonical CFG construct that causes another loop pass to
12 // perform suboptimally, this is the place to fix it up.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "llvm/Transforms/Scalar/LoopSimplifyCFG.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/ADT/Statistic.h"
19 #include "llvm/Analysis/DependenceAnalysis.h"
20 #include "llvm/Analysis/DomTreeUpdater.h"
21 #include "llvm/Analysis/LoopInfo.h"
22 #include "llvm/Analysis/LoopIterator.h"
23 #include "llvm/Analysis/LoopPass.h"
24 #include "llvm/Analysis/MemorySSA.h"
25 #include "llvm/Analysis/MemorySSAUpdater.h"
26 #include "llvm/Analysis/ScalarEvolution.h"
27 #include "llvm/IR/Dominators.h"
28 #include "llvm/IR/IRBuilder.h"
29 #include "llvm/InitializePasses.h"
30 #include "llvm/Support/CommandLine.h"
31 #include "llvm/Transforms/Scalar.h"
32 #include "llvm/Transforms/Scalar/LoopPassManager.h"
33 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
34 #include "llvm/Transforms/Utils/LoopUtils.h"
35 using namespace llvm;
36 
37 #define DEBUG_TYPE "loop-simplifycfg"
38 
39 static cl::opt<bool> EnableTermFolding("enable-loop-simplifycfg-term-folding",
40                                        cl::init(true));
41 
42 STATISTIC(NumTerminatorsFolded,
43           "Number of terminators folded to unconditional branches");
44 STATISTIC(NumLoopBlocksDeleted,
45           "Number of loop blocks deleted");
46 STATISTIC(NumLoopExitsDeleted,
47           "Number of loop exiting edges deleted");
48 
49 /// If \p BB is a switch or a conditional branch, but only one of its successors
50 /// can be reached from this block in runtime, return this successor. Otherwise,
51 /// return nullptr.
52 static BasicBlock *getOnlyLiveSuccessor(BasicBlock *BB) {
53   Instruction *TI = BB->getTerminator();
54   if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
55     if (BI->isUnconditional())
56       return nullptr;
57     if (BI->getSuccessor(0) == BI->getSuccessor(1))
58       return BI->getSuccessor(0);
59     ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
60     if (!Cond)
61       return nullptr;
62     return Cond->isZero() ? BI->getSuccessor(1) : BI->getSuccessor(0);
63   }
64 
65   if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
66     auto *CI = dyn_cast<ConstantInt>(SI->getCondition());
67     if (!CI)
68       return nullptr;
69     for (auto Case : SI->cases())
70       if (Case.getCaseValue() == CI)
71         return Case.getCaseSuccessor();
72     return SI->getDefaultDest();
73   }
74 
75   return nullptr;
76 }
77 
78 /// Removes \p BB from all loops from [FirstLoop, LastLoop) in parent chain.
79 static void removeBlockFromLoops(BasicBlock *BB, Loop *FirstLoop,
80                                  Loop *LastLoop = nullptr) {
81   assert((!LastLoop || LastLoop->contains(FirstLoop->getHeader())) &&
82          "First loop is supposed to be inside of last loop!");
83   assert(FirstLoop->contains(BB) && "Must be a loop block!");
84   for (Loop *Current = FirstLoop; Current != LastLoop;
85        Current = Current->getParentLoop())
86     Current->removeBlockFromLoop(BB);
87 }
88 
89 /// Find innermost loop that contains at least one block from \p BBs and
90 /// contains the header of loop \p L.
91 static Loop *getInnermostLoopFor(SmallPtrSetImpl<BasicBlock *> &BBs,
92                                  Loop &L, LoopInfo &LI) {
93   Loop *Innermost = nullptr;
94   for (BasicBlock *BB : BBs) {
95     Loop *BBL = LI.getLoopFor(BB);
96     while (BBL && !BBL->contains(L.getHeader()))
97       BBL = BBL->getParentLoop();
98     if (BBL == &L)
99       BBL = BBL->getParentLoop();
100     if (!BBL)
101       continue;
102     if (!Innermost || BBL->getLoopDepth() > Innermost->getLoopDepth())
103       Innermost = BBL;
104   }
105   return Innermost;
106 }
107 
108 namespace {
109 /// Helper class that can turn branches and switches with constant conditions
110 /// into unconditional branches.
111 class ConstantTerminatorFoldingImpl {
112 private:
113   Loop &L;
114   LoopInfo &LI;
115   DominatorTree &DT;
116   ScalarEvolution &SE;
117   MemorySSAUpdater *MSSAU;
118   LoopBlocksDFS DFS;
119   DomTreeUpdater DTU;
120   SmallVector<DominatorTree::UpdateType, 16> DTUpdates;
121 
122   // Whether or not the current loop has irreducible CFG.
123   bool HasIrreducibleCFG = false;
124   // Whether or not the current loop will still exist after terminator constant
125   // folding will be done. In theory, there are two ways how it can happen:
126   // 1. Loop's latch(es) become unreachable from loop header;
127   // 2. Loop's header becomes unreachable from method entry.
128   // In practice, the second situation is impossible because we only modify the
129   // current loop and its preheader and do not affect preheader's reachibility
130   // from any other block. So this variable set to true means that loop's latch
131   // has become unreachable from loop header.
132   bool DeleteCurrentLoop = false;
133 
134   // The blocks of the original loop that will still be reachable from entry
135   // after the constant folding.
136   SmallPtrSet<BasicBlock *, 8> LiveLoopBlocks;
137   // The blocks of the original loop that will become unreachable from entry
138   // after the constant folding.
139   SmallVector<BasicBlock *, 8> DeadLoopBlocks;
140   // The exits of the original loop that will still be reachable from entry
141   // after the constant folding.
142   SmallPtrSet<BasicBlock *, 8> LiveExitBlocks;
143   // The exits of the original loop that will become unreachable from entry
144   // after the constant folding.
145   SmallVector<BasicBlock *, 8> DeadExitBlocks;
146   // The blocks that will still be a part of the current loop after folding.
147   SmallPtrSet<BasicBlock *, 8> BlocksInLoopAfterFolding;
148   // The blocks that have terminators with constant condition that can be
149   // folded. Note: fold candidates should be in L but not in any of its
150   // subloops to avoid complex LI updates.
151   SmallVector<BasicBlock *, 8> FoldCandidates;
152 
153   void dump() const {
154     dbgs() << "Constant terminator folding for loop " << L << "\n";
155     dbgs() << "After terminator constant-folding, the loop will";
156     if (!DeleteCurrentLoop)
157       dbgs() << " not";
158     dbgs() << " be destroyed\n";
159     auto PrintOutVector = [&](const char *Message,
160                            const SmallVectorImpl<BasicBlock *> &S) {
161       dbgs() << Message << "\n";
162       for (const BasicBlock *BB : S)
163         dbgs() << "\t" << BB->getName() << "\n";
164     };
165     auto PrintOutSet = [&](const char *Message,
166                            const SmallPtrSetImpl<BasicBlock *> &S) {
167       dbgs() << Message << "\n";
168       for (const BasicBlock *BB : S)
169         dbgs() << "\t" << BB->getName() << "\n";
170     };
171     PrintOutVector("Blocks in which we can constant-fold terminator:",
172                    FoldCandidates);
173     PrintOutSet("Live blocks from the original loop:", LiveLoopBlocks);
174     PrintOutVector("Dead blocks from the original loop:", DeadLoopBlocks);
175     PrintOutSet("Live exit blocks:", LiveExitBlocks);
176     PrintOutVector("Dead exit blocks:", DeadExitBlocks);
177     if (!DeleteCurrentLoop)
178       PrintOutSet("The following blocks will still be part of the loop:",
179                   BlocksInLoopAfterFolding);
180   }
181 
182   /// Whether or not the current loop has irreducible CFG.
183   bool hasIrreducibleCFG(LoopBlocksDFS &DFS) {
184     assert(DFS.isComplete() && "DFS is expected to be finished");
185     // Index of a basic block in RPO traversal.
186     DenseMap<const BasicBlock *, unsigned> RPO;
187     unsigned Current = 0;
188     for (auto I = DFS.beginRPO(), E = DFS.endRPO(); I != E; ++I)
189       RPO[*I] = Current++;
190 
191     for (auto I = DFS.beginRPO(), E = DFS.endRPO(); I != E; ++I) {
192       BasicBlock *BB = *I;
193       for (auto *Succ : successors(BB))
194         if (L.contains(Succ) && !LI.isLoopHeader(Succ) && RPO[BB] > RPO[Succ])
195           // If an edge goes from a block with greater order number into a block
196           // with lesses number, and it is not a loop backedge, then it can only
197           // be a part of irreducible non-loop cycle.
198           return true;
199     }
200     return false;
201   }
202 
203   /// Fill all information about status of blocks and exits of the current loop
204   /// if constant folding of all branches will be done.
205   void analyze() {
206     DFS.perform(&LI);
207     assert(DFS.isComplete() && "DFS is expected to be finished");
208 
209     // TODO: The algorithm below relies on both RPO and Postorder traversals.
210     // When the loop has only reducible CFG inside, then the invariant "all
211     // predecessors of X are processed before X in RPO" is preserved. However
212     // an irreducible loop can break this invariant (e.g. latch does not have to
213     // be the last block in the traversal in this case, and the algorithm relies
214     // on this). We can later decide to support such cases by altering the
215     // algorithms, but so far we just give up analyzing them.
216     if (hasIrreducibleCFG(DFS)) {
217       HasIrreducibleCFG = true;
218       return;
219     }
220 
221     // Collect live and dead loop blocks and exits.
222     LiveLoopBlocks.insert(L.getHeader());
223     for (auto I = DFS.beginRPO(), E = DFS.endRPO(); I != E; ++I) {
224       BasicBlock *BB = *I;
225 
226       // If a loop block wasn't marked as live so far, then it's dead.
227       if (!LiveLoopBlocks.count(BB)) {
228         DeadLoopBlocks.push_back(BB);
229         continue;
230       }
231 
232       BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(BB);
233 
234       // If a block has only one live successor, it's a candidate on constant
235       // folding. Only handle blocks from current loop: branches in child loops
236       // are skipped because if they can be folded, they should be folded during
237       // the processing of child loops.
238       bool TakeFoldCandidate = TheOnlySucc && LI.getLoopFor(BB) == &L;
239       if (TakeFoldCandidate)
240         FoldCandidates.push_back(BB);
241 
242       // Handle successors.
243       for (BasicBlock *Succ : successors(BB))
244         if (!TakeFoldCandidate || TheOnlySucc == Succ) {
245           if (L.contains(Succ))
246             LiveLoopBlocks.insert(Succ);
247           else
248             LiveExitBlocks.insert(Succ);
249         }
250     }
251 
252     // Amount of dead and live loop blocks should match the total number of
253     // blocks in loop.
254     assert(L.getNumBlocks() == LiveLoopBlocks.size() + DeadLoopBlocks.size() &&
255            "Malformed block sets?");
256 
257     // Now, all exit blocks that are not marked as live are dead, if all their
258     // predecessors are in the loop. This may not be the case, as the input loop
259     // may not by in loop-simplify/canonical form.
260     SmallVector<BasicBlock *, 8> ExitBlocks;
261     L.getExitBlocks(ExitBlocks);
262     SmallPtrSet<BasicBlock *, 8> UniqueDeadExits;
263     for (auto *ExitBlock : ExitBlocks)
264       if (!LiveExitBlocks.count(ExitBlock) &&
265           UniqueDeadExits.insert(ExitBlock).second &&
266           all_of(predecessors(ExitBlock),
267                  [this](BasicBlock *Pred) { return L.contains(Pred); }))
268         DeadExitBlocks.push_back(ExitBlock);
269 
270     // Whether or not the edge From->To will still be present in graph after the
271     // folding.
272     auto IsEdgeLive = [&](BasicBlock *From, BasicBlock *To) {
273       if (!LiveLoopBlocks.count(From))
274         return false;
275       BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(From);
276       return !TheOnlySucc || TheOnlySucc == To || LI.getLoopFor(From) != &L;
277     };
278 
279     // The loop will not be destroyed if its latch is live.
280     DeleteCurrentLoop = !IsEdgeLive(L.getLoopLatch(), L.getHeader());
281 
282     // If we are going to delete the current loop completely, no extra analysis
283     // is needed.
284     if (DeleteCurrentLoop)
285       return;
286 
287     // Otherwise, we should check which blocks will still be a part of the
288     // current loop after the transform.
289     BlocksInLoopAfterFolding.insert(L.getLoopLatch());
290     // If the loop is live, then we should compute what blocks are still in
291     // loop after all branch folding has been done. A block is in loop if
292     // it has a live edge to another block that is in the loop; by definition,
293     // latch is in the loop.
294     auto BlockIsInLoop = [&](BasicBlock *BB) {
295       return any_of(successors(BB), [&](BasicBlock *Succ) {
296         return BlocksInLoopAfterFolding.count(Succ) && IsEdgeLive(BB, Succ);
297       });
298     };
299     for (auto I = DFS.beginPostorder(), E = DFS.endPostorder(); I != E; ++I) {
300       BasicBlock *BB = *I;
301       if (BlockIsInLoop(BB))
302         BlocksInLoopAfterFolding.insert(BB);
303     }
304 
305     assert(BlocksInLoopAfterFolding.count(L.getHeader()) &&
306            "Header not in loop?");
307     assert(BlocksInLoopAfterFolding.size() <= LiveLoopBlocks.size() &&
308            "All blocks that stay in loop should be live!");
309   }
310 
311   /// We need to preserve static reachibility of all loop exit blocks (this is)
312   /// required by loop pass manager. In order to do it, we make the following
313   /// trick:
314   ///
315   ///  preheader:
316   ///    <preheader code>
317   ///    br label %loop_header
318   ///
319   ///  loop_header:
320   ///    ...
321   ///    br i1 false, label %dead_exit, label %loop_block
322   ///    ...
323   ///
324   /// We cannot simply remove edge from the loop to dead exit because in this
325   /// case dead_exit (and its successors) may become unreachable. To avoid that,
326   /// we insert the following fictive preheader:
327   ///
328   ///  preheader:
329   ///    <preheader code>
330   ///    switch i32 0, label %preheader-split,
331   ///                  [i32 1, label %dead_exit_1],
332   ///                  [i32 2, label %dead_exit_2],
333   ///                  ...
334   ///                  [i32 N, label %dead_exit_N],
335   ///
336   ///  preheader-split:
337   ///    br label %loop_header
338   ///
339   ///  loop_header:
340   ///    ...
341   ///    br i1 false, label %dead_exit_N, label %loop_block
342   ///    ...
343   ///
344   /// Doing so, we preserve static reachibility of all dead exits and can later
345   /// remove edges from the loop to these blocks.
346   void handleDeadExits() {
347     // If no dead exits, nothing to do.
348     if (DeadExitBlocks.empty())
349       return;
350 
351     // Construct split preheader and the dummy switch to thread edges from it to
352     // dead exits.
353     BasicBlock *Preheader = L.getLoopPreheader();
354     BasicBlock *NewPreheader = llvm::SplitBlock(
355         Preheader, Preheader->getTerminator(), &DT, &LI, MSSAU);
356 
357     IRBuilder<> Builder(Preheader->getTerminator());
358     SwitchInst *DummySwitch =
359         Builder.CreateSwitch(Builder.getInt32(0), NewPreheader);
360     Preheader->getTerminator()->eraseFromParent();
361 
362     unsigned DummyIdx = 1;
363     for (BasicBlock *BB : DeadExitBlocks) {
364       // Eliminate all Phis and LandingPads from dead exits.
365       // TODO: Consider removing all instructions in this dead block.
366       SmallVector<Instruction *, 4> DeadInstructions;
367       for (auto &PN : BB->phis())
368         DeadInstructions.push_back(&PN);
369 
370       if (auto *LandingPad = dyn_cast<LandingPadInst>(BB->getFirstNonPHI()))
371         DeadInstructions.emplace_back(LandingPad);
372 
373       for (Instruction *I : DeadInstructions) {
374         I->replaceAllUsesWith(PoisonValue::get(I->getType()));
375         I->eraseFromParent();
376       }
377 
378       assert(DummyIdx != 0 && "Too many dead exits!");
379       DummySwitch->addCase(Builder.getInt32(DummyIdx++), BB);
380       DTUpdates.push_back({DominatorTree::Insert, Preheader, BB});
381       ++NumLoopExitsDeleted;
382     }
383 
384     assert(L.getLoopPreheader() == NewPreheader && "Malformed CFG?");
385     if (Loop *OuterLoop = LI.getLoopFor(Preheader)) {
386       // When we break dead edges, the outer loop may become unreachable from
387       // the current loop. We need to fix loop info accordingly. For this, we
388       // find the most nested loop that still contains L and remove L from all
389       // loops that are inside of it.
390       Loop *StillReachable = getInnermostLoopFor(LiveExitBlocks, L, LI);
391 
392       // Okay, our loop is no longer in the outer loop (and maybe not in some of
393       // its parents as well). Make the fixup.
394       if (StillReachable != OuterLoop) {
395         LI.changeLoopFor(NewPreheader, StillReachable);
396         removeBlockFromLoops(NewPreheader, OuterLoop, StillReachable);
397         for (auto *BB : L.blocks())
398           removeBlockFromLoops(BB, OuterLoop, StillReachable);
399         OuterLoop->removeChildLoop(&L);
400         if (StillReachable)
401           StillReachable->addChildLoop(&L);
402         else
403           LI.addTopLevelLoop(&L);
404 
405         // Some values from loops in [OuterLoop, StillReachable) could be used
406         // in the current loop. Now it is not their child anymore, so such uses
407         // require LCSSA Phis.
408         Loop *FixLCSSALoop = OuterLoop;
409         while (FixLCSSALoop->getParentLoop() != StillReachable)
410           FixLCSSALoop = FixLCSSALoop->getParentLoop();
411         assert(FixLCSSALoop && "Should be a loop!");
412         // We need all DT updates to be done before forming LCSSA.
413         if (MSSAU)
414           MSSAU->applyUpdates(DTUpdates, DT, /*UpdateDT=*/true);
415         else
416           DTU.applyUpdates(DTUpdates);
417         DTUpdates.clear();
418         formLCSSARecursively(*FixLCSSALoop, DT, &LI, &SE);
419       }
420     }
421 
422     if (MSSAU) {
423       // Clear all updates now. Facilitates deletes that follow.
424       MSSAU->applyUpdates(DTUpdates, DT, /*UpdateDT=*/true);
425       DTUpdates.clear();
426       if (VerifyMemorySSA)
427         MSSAU->getMemorySSA()->verifyMemorySSA();
428     }
429   }
430 
431   /// Delete loop blocks that have become unreachable after folding. Make all
432   /// relevant updates to DT and LI.
433   void deleteDeadLoopBlocks() {
434     if (MSSAU) {
435       SmallSetVector<BasicBlock *, 8> DeadLoopBlocksSet(DeadLoopBlocks.begin(),
436                                                         DeadLoopBlocks.end());
437       MSSAU->removeBlocks(DeadLoopBlocksSet);
438     }
439 
440     // The function LI.erase has some invariants that need to be preserved when
441     // it tries to remove a loop which is not the top-level loop. In particular,
442     // it requires loop's preheader to be strictly in loop's parent. We cannot
443     // just remove blocks one by one, because after removal of preheader we may
444     // break this invariant for the dead loop. So we detatch and erase all dead
445     // loops beforehand.
446     for (auto *BB : DeadLoopBlocks)
447       if (LI.isLoopHeader(BB)) {
448         assert(LI.getLoopFor(BB) != &L && "Attempt to remove current loop!");
449         Loop *DL = LI.getLoopFor(BB);
450         if (!DL->isOutermost()) {
451           for (auto *PL = DL->getParentLoop(); PL; PL = PL->getParentLoop())
452             for (auto *BB : DL->getBlocks())
453               PL->removeBlockFromLoop(BB);
454           DL->getParentLoop()->removeChildLoop(DL);
455           LI.addTopLevelLoop(DL);
456         }
457         LI.erase(DL);
458       }
459 
460     for (auto *BB : DeadLoopBlocks) {
461       assert(BB != L.getHeader() &&
462              "Header of the current loop cannot be dead!");
463       LLVM_DEBUG(dbgs() << "Deleting dead loop block " << BB->getName()
464                         << "\n");
465       LI.removeBlock(BB);
466     }
467 
468     detachDeadBlocks(DeadLoopBlocks, &DTUpdates, /*KeepOneInputPHIs*/true);
469     DTU.applyUpdates(DTUpdates);
470     DTUpdates.clear();
471     for (auto *BB : DeadLoopBlocks)
472       DTU.deleteBB(BB);
473 
474     NumLoopBlocksDeleted += DeadLoopBlocks.size();
475   }
476 
477   /// Constant-fold terminators of blocks acculumated in FoldCandidates into the
478   /// unconditional branches.
479   void foldTerminators() {
480     for (BasicBlock *BB : FoldCandidates) {
481       assert(LI.getLoopFor(BB) == &L && "Should be a loop block!");
482       BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(BB);
483       assert(TheOnlySucc && "Should have one live successor!");
484 
485       LLVM_DEBUG(dbgs() << "Replacing terminator of " << BB->getName()
486                         << " with an unconditional branch to the block "
487                         << TheOnlySucc->getName() << "\n");
488 
489       SmallPtrSet<BasicBlock *, 2> DeadSuccessors;
490       // Remove all BB's successors except for the live one.
491       unsigned TheOnlySuccDuplicates = 0;
492       for (auto *Succ : successors(BB))
493         if (Succ != TheOnlySucc) {
494           DeadSuccessors.insert(Succ);
495           // If our successor lies in a different loop, we don't want to remove
496           // the one-input Phi because it is a LCSSA Phi.
497           bool PreserveLCSSAPhi = !L.contains(Succ);
498           Succ->removePredecessor(BB, PreserveLCSSAPhi);
499           if (MSSAU)
500             MSSAU->removeEdge(BB, Succ);
501         } else
502           ++TheOnlySuccDuplicates;
503 
504       assert(TheOnlySuccDuplicates > 0 && "Should be!");
505       // If TheOnlySucc was BB's successor more than once, after transform it
506       // will be its successor only once. Remove redundant inputs from
507       // TheOnlySucc's Phis.
508       bool PreserveLCSSAPhi = !L.contains(TheOnlySucc);
509       for (unsigned Dup = 1; Dup < TheOnlySuccDuplicates; ++Dup)
510         TheOnlySucc->removePredecessor(BB, PreserveLCSSAPhi);
511       if (MSSAU && TheOnlySuccDuplicates > 1)
512         MSSAU->removeDuplicatePhiEdgesBetween(BB, TheOnlySucc);
513 
514       IRBuilder<> Builder(BB->getContext());
515       Instruction *Term = BB->getTerminator();
516       Builder.SetInsertPoint(Term);
517       Builder.CreateBr(TheOnlySucc);
518       Term->eraseFromParent();
519 
520       for (auto *DeadSucc : DeadSuccessors)
521         DTUpdates.push_back({DominatorTree::Delete, BB, DeadSucc});
522 
523       ++NumTerminatorsFolded;
524     }
525   }
526 
527 public:
528   ConstantTerminatorFoldingImpl(Loop &L, LoopInfo &LI, DominatorTree &DT,
529                                 ScalarEvolution &SE,
530                                 MemorySSAUpdater *MSSAU)
531       : L(L), LI(LI), DT(DT), SE(SE), MSSAU(MSSAU), DFS(&L),
532         DTU(DT, DomTreeUpdater::UpdateStrategy::Eager) {}
533   bool run() {
534     assert(L.getLoopLatch() && "Should be single latch!");
535 
536     // Collect all available information about status of blocks after constant
537     // folding.
538     analyze();
539     BasicBlock *Header = L.getHeader();
540     (void)Header;
541 
542     LLVM_DEBUG(dbgs() << "In function " << Header->getParent()->getName()
543                       << ": ");
544 
545     if (HasIrreducibleCFG) {
546       LLVM_DEBUG(dbgs() << "Loops with irreducible CFG are not supported!\n");
547       return false;
548     }
549 
550     // Nothing to constant-fold.
551     if (FoldCandidates.empty()) {
552       LLVM_DEBUG(
553           dbgs() << "No constant terminator folding candidates found in loop "
554                  << Header->getName() << "\n");
555       return false;
556     }
557 
558     // TODO: Support deletion of the current loop.
559     if (DeleteCurrentLoop) {
560       LLVM_DEBUG(
561           dbgs()
562           << "Give up constant terminator folding in loop " << Header->getName()
563           << ": we don't currently support deletion of the current loop.\n");
564       return false;
565     }
566 
567     // TODO: Support blocks that are not dead, but also not in loop after the
568     // folding.
569     if (BlocksInLoopAfterFolding.size() + DeadLoopBlocks.size() !=
570         L.getNumBlocks()) {
571       LLVM_DEBUG(
572           dbgs() << "Give up constant terminator folding in loop "
573                  << Header->getName() << ": we don't currently"
574                     " support blocks that are not dead, but will stop "
575                     "being a part of the loop after constant-folding.\n");
576       return false;
577     }
578 
579     // TODO: Tokens may breach LCSSA form by default. However, the transform for
580     // dead exit blocks requires LCSSA form to be maintained for all values,
581     // tokens included, otherwise it may break use-def dominance (see PR56243).
582     if (!DeadExitBlocks.empty() && !L.isLCSSAForm(DT, /*IgnoreTokens*/ false)) {
583       assert(L.isLCSSAForm(DT, /*IgnoreTokens*/ true) &&
584              "LCSSA broken not by tokens?");
585       LLVM_DEBUG(dbgs() << "Give up constant terminator folding in loop "
586                         << Header->getName()
587                         << ": tokens uses potentially break LCSSA form.\n");
588       return false;
589     }
590 
591     SE.forgetTopmostLoop(&L);
592     // Dump analysis results.
593     LLVM_DEBUG(dump());
594 
595     LLVM_DEBUG(dbgs() << "Constant-folding " << FoldCandidates.size()
596                       << " terminators in loop " << Header->getName() << "\n");
597 
598     // Make the actual transforms.
599     handleDeadExits();
600     foldTerminators();
601 
602     if (!DeadLoopBlocks.empty()) {
603       LLVM_DEBUG(dbgs() << "Deleting " << DeadLoopBlocks.size()
604                     << " dead blocks in loop " << Header->getName() << "\n");
605       deleteDeadLoopBlocks();
606     } else {
607       // If we didn't do updates inside deleteDeadLoopBlocks, do them here.
608       DTU.applyUpdates(DTUpdates);
609       DTUpdates.clear();
610     }
611 
612     if (MSSAU && VerifyMemorySSA)
613       MSSAU->getMemorySSA()->verifyMemorySSA();
614 
615 #ifndef NDEBUG
616     // Make sure that we have preserved all data structures after the transform.
617 #if defined(EXPENSIVE_CHECKS)
618     assert(DT.verify(DominatorTree::VerificationLevel::Full) &&
619            "DT broken after transform!");
620 #else
621     assert(DT.verify(DominatorTree::VerificationLevel::Fast) &&
622            "DT broken after transform!");
623 #endif
624     assert(DT.isReachableFromEntry(Header));
625     LI.verify(DT);
626 #endif
627 
628     return true;
629   }
630 
631   bool foldingBreaksCurrentLoop() const {
632     return DeleteCurrentLoop;
633   }
634 };
635 } // namespace
636 
637 /// Turn branches and switches with known constant conditions into unconditional
638 /// branches.
639 static bool constantFoldTerminators(Loop &L, DominatorTree &DT, LoopInfo &LI,
640                                     ScalarEvolution &SE,
641                                     MemorySSAUpdater *MSSAU,
642                                     bool &IsLoopDeleted) {
643   if (!EnableTermFolding)
644     return false;
645 
646   // To keep things simple, only process loops with single latch. We
647   // canonicalize most loops to this form. We can support multi-latch if needed.
648   if (!L.getLoopLatch())
649     return false;
650 
651   ConstantTerminatorFoldingImpl BranchFolder(L, LI, DT, SE, MSSAU);
652   bool Changed = BranchFolder.run();
653   IsLoopDeleted = Changed && BranchFolder.foldingBreaksCurrentLoop();
654   return Changed;
655 }
656 
657 static bool mergeBlocksIntoPredecessors(Loop &L, DominatorTree &DT,
658                                         LoopInfo &LI, MemorySSAUpdater *MSSAU) {
659   bool Changed = false;
660   DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
661   // Copy blocks into a temporary array to avoid iterator invalidation issues
662   // as we remove them.
663   SmallVector<WeakTrackingVH, 16> Blocks(L.blocks());
664 
665   for (auto &Block : Blocks) {
666     // Attempt to merge blocks in the trivial case. Don't modify blocks which
667     // belong to other loops.
668     BasicBlock *Succ = cast_or_null<BasicBlock>(Block);
669     if (!Succ)
670       continue;
671 
672     BasicBlock *Pred = Succ->getSinglePredecessor();
673     if (!Pred || !Pred->getSingleSuccessor() || LI.getLoopFor(Pred) != &L)
674       continue;
675 
676     // Merge Succ into Pred and delete it.
677     MergeBlockIntoPredecessor(Succ, &DTU, &LI, MSSAU);
678 
679     if (MSSAU && VerifyMemorySSA)
680       MSSAU->getMemorySSA()->verifyMemorySSA();
681 
682     Changed = true;
683   }
684 
685   return Changed;
686 }
687 
688 static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI,
689                             ScalarEvolution &SE, MemorySSAUpdater *MSSAU,
690                             bool &IsLoopDeleted) {
691   bool Changed = false;
692 
693   // Constant-fold terminators with known constant conditions.
694   Changed |= constantFoldTerminators(L, DT, LI, SE, MSSAU, IsLoopDeleted);
695 
696   if (IsLoopDeleted)
697     return true;
698 
699   // Eliminate unconditional branches by merging blocks into their predecessors.
700   Changed |= mergeBlocksIntoPredecessors(L, DT, LI, MSSAU);
701 
702   if (Changed)
703     SE.forgetTopmostLoop(&L);
704 
705   return Changed;
706 }
707 
708 PreservedAnalyses LoopSimplifyCFGPass::run(Loop &L, LoopAnalysisManager &AM,
709                                            LoopStandardAnalysisResults &AR,
710                                            LPMUpdater &LPMU) {
711   Optional<MemorySSAUpdater> MSSAU;
712   if (AR.MSSA)
713     MSSAU = MemorySSAUpdater(AR.MSSA);
714   bool DeleteCurrentLoop = false;
715   if (!simplifyLoopCFG(L, AR.DT, AR.LI, AR.SE,
716                        MSSAU ? MSSAU.getPointer() : nullptr, DeleteCurrentLoop))
717     return PreservedAnalyses::all();
718 
719   if (DeleteCurrentLoop)
720     LPMU.markLoopAsDeleted(L, "loop-simplifycfg");
721 
722   auto PA = getLoopPassPreservedAnalyses();
723   if (AR.MSSA)
724     PA.preserve<MemorySSAAnalysis>();
725   return PA;
726 }
727 
728 namespace {
729 class LoopSimplifyCFGLegacyPass : public LoopPass {
730 public:
731   static char ID; // Pass ID, replacement for typeid
732   LoopSimplifyCFGLegacyPass() : LoopPass(ID) {
733     initializeLoopSimplifyCFGLegacyPassPass(*PassRegistry::getPassRegistry());
734   }
735 
736   bool runOnLoop(Loop *L, LPPassManager &LPM) override {
737     if (skipLoop(L))
738       return false;
739 
740     DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
741     LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
742     ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
743     auto *MSSAA = getAnalysisIfAvailable<MemorySSAWrapperPass>();
744     Optional<MemorySSAUpdater> MSSAU;
745     if (MSSAA)
746       MSSAU = MemorySSAUpdater(&MSSAA->getMSSA());
747     if (MSSAA && VerifyMemorySSA)
748       MSSAU->getMemorySSA()->verifyMemorySSA();
749     bool DeleteCurrentLoop = false;
750     bool Changed =
751         simplifyLoopCFG(*L, DT, LI, SE, MSSAU ? MSSAU.getPointer() : nullptr,
752                         DeleteCurrentLoop);
753     if (DeleteCurrentLoop)
754       LPM.markLoopAsDeleted(*L);
755     return Changed;
756   }
757 
758   void getAnalysisUsage(AnalysisUsage &AU) const override {
759     AU.addPreserved<MemorySSAWrapperPass>();
760     AU.addPreserved<DependenceAnalysisWrapperPass>();
761     getLoopAnalysisUsage(AU);
762   }
763 };
764 } // end namespace
765 
766 char LoopSimplifyCFGLegacyPass::ID = 0;
767 INITIALIZE_PASS_BEGIN(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
768                       "Simplify loop CFG", false, false)
769 INITIALIZE_PASS_DEPENDENCY(LoopPass)
770 INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
771 INITIALIZE_PASS_END(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
772                     "Simplify loop CFG", false, false)
773 
774 Pass *llvm::createLoopSimplifyCFGPass() {
775   return new LoopSimplifyCFGLegacyPass();
776 }
777