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