LLVM  16.0.0git
LoopSimplifyCFG.cpp
Go to the documentation of this file.
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 
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/ADT/Statistic.h"
21 #include "llvm/Analysis/LoopInfo.h"
23 #include "llvm/Analysis/LoopPass.h"
27 #include "llvm/IR/Dominators.h"
28 #include "llvm/IR/IRBuilder.h"
29 #include "llvm/InitializePasses.h"
31 #include "llvm/Transforms/Scalar.h"
35 #include <optional>
36 using namespace llvm;
37 
38 #define DEBUG_TYPE "loop-simplifycfg"
39 
40 static cl::opt<bool> EnableTermFolding("enable-loop-simplifycfg-term-folding",
41  cl::init(true));
42 
43 STATISTIC(NumTerminatorsFolded,
44  "Number of terminators folded to unconditional branches");
45 STATISTIC(NumLoopBlocksDeleted,
46  "Number of loop blocks deleted");
47 STATISTIC(NumLoopExitsDeleted,
48  "Number of loop exiting edges deleted");
49 
50 /// If \p BB is a switch or a conditional branch, but only one of its successors
51 /// can be reached from this block in runtime, return this successor. Otherwise,
52 /// return nullptr.
54  Instruction *TI = BB->getTerminator();
55  if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
56  if (BI->isUnconditional())
57  return nullptr;
58  if (BI->getSuccessor(0) == BI->getSuccessor(1))
59  return BI->getSuccessor(0);
60  ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
61  if (!Cond)
62  return nullptr;
63  return Cond->isZero() ? BI->getSuccessor(1) : BI->getSuccessor(0);
64  }
65 
66  if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
67  auto *CI = dyn_cast<ConstantInt>(SI->getCondition());
68  if (!CI)
69  return nullptr;
70  for (auto Case : SI->cases())
71  if (Case.getCaseValue() == CI)
72  return Case.getCaseSuccessor();
73  return SI->getDefaultDest();
74  }
75 
76  return nullptr;
77 }
78 
79 /// Removes \p BB from all loops from [FirstLoop, LastLoop) in parent chain.
80 static void removeBlockFromLoops(BasicBlock *BB, Loop *FirstLoop,
81  Loop *LastLoop = nullptr) {
82  assert((!LastLoop || LastLoop->contains(FirstLoop->getHeader())) &&
83  "First loop is supposed to be inside of last loop!");
84  assert(FirstLoop->contains(BB) && "Must be a loop block!");
85  for (Loop *Current = FirstLoop; Current != LastLoop;
86  Current = Current->getParentLoop())
87  Current->removeBlockFromLoop(BB);
88 }
89 
90 /// Find innermost loop that contains at least one block from \p BBs and
91 /// contains the header of loop \p L.
93  Loop &L, LoopInfo &LI) {
94  Loop *Innermost = nullptr;
95  for (BasicBlock *BB : BBs) {
96  Loop *BBL = LI.getLoopFor(BB);
97  while (BBL && !BBL->contains(L.getHeader()))
98  BBL = BBL->getParentLoop();
99  if (BBL == &L)
100  BBL = BBL->getParentLoop();
101  if (!BBL)
102  continue;
103  if (!Innermost || BBL->getLoopDepth() > Innermost->getLoopDepth())
104  Innermost = BBL;
105  }
106  return Innermost;
107 }
108 
109 namespace {
110 /// Helper class that can turn branches and switches with constant conditions
111 /// into unconditional branches.
112 class ConstantTerminatorFoldingImpl {
113 private:
114  Loop &L;
115  LoopInfo &LI;
116  DominatorTree &DT;
117  ScalarEvolution &SE;
118  MemorySSAUpdater *MSSAU;
119  LoopBlocksDFS DFS;
120  DomTreeUpdater DTU;
122 
123  // Whether or not the current loop has irreducible CFG.
124  bool HasIrreducibleCFG = false;
125  // Whether or not the current loop will still exist after terminator constant
126  // folding will be done. In theory, there are two ways how it can happen:
127  // 1. Loop's latch(es) become unreachable from loop header;
128  // 2. Loop's header becomes unreachable from method entry.
129  // In practice, the second situation is impossible because we only modify the
130  // current loop and its preheader and do not affect preheader's reachibility
131  // from any other block. So this variable set to true means that loop's latch
132  // has become unreachable from loop header.
133  bool DeleteCurrentLoop = false;
134 
135  // The blocks of the original loop that will still be reachable from entry
136  // after the constant folding.
137  SmallPtrSet<BasicBlock *, 8> LiveLoopBlocks;
138  // The blocks of the original loop that will become unreachable from entry
139  // after the constant folding.
140  SmallVector<BasicBlock *, 8> DeadLoopBlocks;
141  // The exits of the original loop that will still be reachable from entry
142  // after the constant folding.
143  SmallPtrSet<BasicBlock *, 8> LiveExitBlocks;
144  // The exits of the original loop that will become unreachable from entry
145  // after the constant folding.
146  SmallVector<BasicBlock *, 8> DeadExitBlocks;
147  // The blocks that will still be a part of the current loop after folding.
148  SmallPtrSet<BasicBlock *, 8> BlocksInLoopAfterFolding;
149  // The blocks that have terminators with constant condition that can be
150  // folded. Note: fold candidates should be in L but not in any of its
151  // subloops to avoid complex LI updates.
152  SmallVector<BasicBlock *, 8> FoldCandidates;
153 
154  void dump() const {
155  dbgs() << "Constant terminator folding for loop " << L << "\n";
156  dbgs() << "After terminator constant-folding, the loop will";
157  if (!DeleteCurrentLoop)
158  dbgs() << " not";
159  dbgs() << " be destroyed\n";
160  auto PrintOutVector = [&](const char *Message,
162  dbgs() << Message << "\n";
163  for (const BasicBlock *BB : S)
164  dbgs() << "\t" << BB->getName() << "\n";
165  };
166  auto PrintOutSet = [&](const char *Message,
168  dbgs() << Message << "\n";
169  for (const BasicBlock *BB : S)
170  dbgs() << "\t" << BB->getName() << "\n";
171  };
172  PrintOutVector("Blocks in which we can constant-fold terminator:",
173  FoldCandidates);
174  PrintOutSet("Live blocks from the original loop:", LiveLoopBlocks);
175  PrintOutVector("Dead blocks from the original loop:", DeadLoopBlocks);
176  PrintOutSet("Live exit blocks:", LiveExitBlocks);
177  PrintOutVector("Dead exit blocks:", DeadExitBlocks);
178  if (!DeleteCurrentLoop)
179  PrintOutSet("The following blocks will still be part of the loop:",
180  BlocksInLoopAfterFolding);
181  }
182 
183  /// Whether or not the current loop has irreducible CFG.
184  bool hasIrreducibleCFG(LoopBlocksDFS &DFS) {
185  assert(DFS.isComplete() && "DFS is expected to be finished");
186  // Index of a basic block in RPO traversal.
188  unsigned Current = 0;
189  for (auto I = DFS.beginRPO(), E = DFS.endRPO(); I != E; ++I)
190  RPO[*I] = Current++;
191 
192  for (auto I = DFS.beginRPO(), E = DFS.endRPO(); I != E; ++I) {
193  BasicBlock *BB = *I;
194  for (auto *Succ : successors(BB))
195  if (L.contains(Succ) && !LI.isLoopHeader(Succ) && RPO[BB] > RPO[Succ])
196  // If an edge goes from a block with greater order number into a block
197  // with lesses number, and it is not a loop backedge, then it can only
198  // be a part of irreducible non-loop cycle.
199  return true;
200  }
201  return false;
202  }
203 
204  /// Fill all information about status of blocks and exits of the current loop
205  /// if constant folding of all branches will be done.
206  void analyze() {
207  DFS.perform(&LI);
208  assert(DFS.isComplete() && "DFS is expected to be finished");
209 
210  // TODO: The algorithm below relies on both RPO and Postorder traversals.
211  // When the loop has only reducible CFG inside, then the invariant "all
212  // predecessors of X are processed before X in RPO" is preserved. However
213  // an irreducible loop can break this invariant (e.g. latch does not have to
214  // be the last block in the traversal in this case, and the algorithm relies
215  // on this). We can later decide to support such cases by altering the
216  // algorithms, but so far we just give up analyzing them.
217  if (hasIrreducibleCFG(DFS)) {
218  HasIrreducibleCFG = true;
219  return;
220  }
221 
222  // Collect live and dead loop blocks and exits.
223  LiveLoopBlocks.insert(L.getHeader());
224  for (auto I = DFS.beginRPO(), E = DFS.endRPO(); I != E; ++I) {
225  BasicBlock *BB = *I;
226 
227  // If a loop block wasn't marked as live so far, then it's dead.
228  if (!LiveLoopBlocks.count(BB)) {
229  DeadLoopBlocks.push_back(BB);
230  continue;
231  }
232 
233  BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(BB);
234 
235  // If a block has only one live successor, it's a candidate on constant
236  // folding. Only handle blocks from current loop: branches in child loops
237  // are skipped because if they can be folded, they should be folded during
238  // the processing of child loops.
239  bool TakeFoldCandidate = TheOnlySucc && LI.getLoopFor(BB) == &L;
240  if (TakeFoldCandidate)
241  FoldCandidates.push_back(BB);
242 
243  // Handle successors.
244  for (BasicBlock *Succ : successors(BB))
245  if (!TakeFoldCandidate || TheOnlySucc == Succ) {
246  if (L.contains(Succ))
247  LiveLoopBlocks.insert(Succ);
248  else
249  LiveExitBlocks.insert(Succ);
250  }
251  }
252 
253  // Amount of dead and live loop blocks should match the total number of
254  // blocks in loop.
255  assert(L.getNumBlocks() == LiveLoopBlocks.size() + DeadLoopBlocks.size() &&
256  "Malformed block sets?");
257 
258  // Now, all exit blocks that are not marked as live are dead, if all their
259  // predecessors are in the loop. This may not be the case, as the input loop
260  // may not by in loop-simplify/canonical form.
261  SmallVector<BasicBlock *, 8> ExitBlocks;
262  L.getExitBlocks(ExitBlocks);
263  SmallPtrSet<BasicBlock *, 8> UniqueDeadExits;
264  for (auto *ExitBlock : ExitBlocks)
265  if (!LiveExitBlocks.count(ExitBlock) &&
266  UniqueDeadExits.insert(ExitBlock).second &&
267  all_of(predecessors(ExitBlock),
268  [this](BasicBlock *Pred) { return L.contains(Pred); }))
269  DeadExitBlocks.push_back(ExitBlock);
270 
271  // Whether or not the edge From->To will still be present in graph after the
272  // folding.
273  auto IsEdgeLive = [&](BasicBlock *From, BasicBlock *To) {
274  if (!LiveLoopBlocks.count(From))
275  return false;
276  BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(From);
277  return !TheOnlySucc || TheOnlySucc == To || LI.getLoopFor(From) != &L;
278  };
279 
280  // The loop will not be destroyed if its latch is live.
281  DeleteCurrentLoop = !IsEdgeLive(L.getLoopLatch(), L.getHeader());
282 
283  // If we are going to delete the current loop completely, no extra analysis
284  // is needed.
285  if (DeleteCurrentLoop)
286  return;
287 
288  // Otherwise, we should check which blocks will still be a part of the
289  // current loop after the transform.
290  BlocksInLoopAfterFolding.insert(L.getLoopLatch());
291  // If the loop is live, then we should compute what blocks are still in
292  // loop after all branch folding has been done. A block is in loop if
293  // it has a live edge to another block that is in the loop; by definition,
294  // latch is in the loop.
295  auto BlockIsInLoop = [&](BasicBlock *BB) {
296  return any_of(successors(BB), [&](BasicBlock *Succ) {
297  return BlocksInLoopAfterFolding.count(Succ) && IsEdgeLive(BB, Succ);
298  });
299  };
300  for (auto I = DFS.beginPostorder(), E = DFS.endPostorder(); I != E; ++I) {
301  BasicBlock *BB = *I;
302  if (BlockIsInLoop(BB))
303  BlocksInLoopAfterFolding.insert(BB);
304  }
305 
306  assert(BlocksInLoopAfterFolding.count(L.getHeader()) &&
307  "Header not in loop?");
308  assert(BlocksInLoopAfterFolding.size() <= LiveLoopBlocks.size() &&
309  "All blocks that stay in loop should be live!");
310  }
311 
312  /// We need to preserve static reachibility of all loop exit blocks (this is)
313  /// required by loop pass manager. In order to do it, we make the following
314  /// trick:
315  ///
316  /// preheader:
317  /// <preheader code>
318  /// br label %loop_header
319  ///
320  /// loop_header:
321  /// ...
322  /// br i1 false, label %dead_exit, label %loop_block
323  /// ...
324  ///
325  /// We cannot simply remove edge from the loop to dead exit because in this
326  /// case dead_exit (and its successors) may become unreachable. To avoid that,
327  /// we insert the following fictive preheader:
328  ///
329  /// preheader:
330  /// <preheader code>
331  /// switch i32 0, label %preheader-split,
332  /// [i32 1, label %dead_exit_1],
333  /// [i32 2, label %dead_exit_2],
334  /// ...
335  /// [i32 N, label %dead_exit_N],
336  ///
337  /// preheader-split:
338  /// br label %loop_header
339  ///
340  /// loop_header:
341  /// ...
342  /// br i1 false, label %dead_exit_N, label %loop_block
343  /// ...
344  ///
345  /// Doing so, we preserve static reachibility of all dead exits and can later
346  /// remove edges from the loop to these blocks.
347  void handleDeadExits() {
348  // If no dead exits, nothing to do.
349  if (DeadExitBlocks.empty())
350  return;
351 
352  // Construct split preheader and the dummy switch to thread edges from it to
353  // dead exits.
354  BasicBlock *Preheader = L.getLoopPreheader();
355  BasicBlock *NewPreheader = llvm::SplitBlock(
356  Preheader, Preheader->getTerminator(), &DT, &LI, MSSAU);
357 
358  IRBuilder<> Builder(Preheader->getTerminator());
359  SwitchInst *DummySwitch =
360  Builder.CreateSwitch(Builder.getInt32(0), NewPreheader);
361  Preheader->getTerminator()->eraseFromParent();
362 
363  unsigned DummyIdx = 1;
364  for (BasicBlock *BB : DeadExitBlocks) {
365  // Eliminate all Phis and LandingPads from dead exits.
366  // TODO: Consider removing all instructions in this dead block.
367  SmallVector<Instruction *, 4> DeadInstructions;
368  for (auto &PN : BB->phis())
369  DeadInstructions.push_back(&PN);
370 
371  if (auto *LandingPad = dyn_cast<LandingPadInst>(BB->getFirstNonPHI()))
372  DeadInstructions.emplace_back(LandingPad);
373 
374  for (Instruction *I : DeadInstructions) {
376  I->replaceAllUsesWith(PoisonValue::get(I->getType()));
377  I->eraseFromParent();
378  }
379 
380  assert(DummyIdx != 0 && "Too many dead exits!");
381  DummySwitch->addCase(Builder.getInt32(DummyIdx++), BB);
382  DTUpdates.push_back({DominatorTree::Insert, Preheader, BB});
383  ++NumLoopExitsDeleted;
384  }
385 
386  assert(L.getLoopPreheader() == NewPreheader && "Malformed CFG?");
387  if (Loop *OuterLoop = LI.getLoopFor(Preheader)) {
388  // When we break dead edges, the outer loop may become unreachable from
389  // the current loop. We need to fix loop info accordingly. For this, we
390  // find the most nested loop that still contains L and remove L from all
391  // loops that are inside of it.
392  Loop *StillReachable = getInnermostLoopFor(LiveExitBlocks, L, LI);
393 
394  // Okay, our loop is no longer in the outer loop (and maybe not in some of
395  // its parents as well). Make the fixup.
396  if (StillReachable != OuterLoop) {
397  LI.changeLoopFor(NewPreheader, StillReachable);
398  removeBlockFromLoops(NewPreheader, OuterLoop, StillReachable);
399  for (auto *BB : L.blocks())
400  removeBlockFromLoops(BB, OuterLoop, StillReachable);
401  OuterLoop->removeChildLoop(&L);
402  if (StillReachable)
403  StillReachable->addChildLoop(&L);
404  else
405  LI.addTopLevelLoop(&L);
406 
407  // Some values from loops in [OuterLoop, StillReachable) could be used
408  // in the current loop. Now it is not their child anymore, so such uses
409  // require LCSSA Phis.
410  Loop *FixLCSSALoop = OuterLoop;
411  while (FixLCSSALoop->getParentLoop() != StillReachable)
412  FixLCSSALoop = FixLCSSALoop->getParentLoop();
413  assert(FixLCSSALoop && "Should be a loop!");
414  // We need all DT updates to be done before forming LCSSA.
415  if (MSSAU)
416  MSSAU->applyUpdates(DTUpdates, DT, /*UpdateDT=*/true);
417  else
418  DTU.applyUpdates(DTUpdates);
419  DTUpdates.clear();
420  formLCSSARecursively(*FixLCSSALoop, DT, &LI, &SE);
422  }
423  }
424 
425  if (MSSAU) {
426  // Clear all updates now. Facilitates deletes that follow.
427  MSSAU->applyUpdates(DTUpdates, DT, /*UpdateDT=*/true);
428  DTUpdates.clear();
429  if (VerifyMemorySSA)
430  MSSAU->getMemorySSA()->verifyMemorySSA();
431  }
432  }
433 
434  /// Delete loop blocks that have become unreachable after folding. Make all
435  /// relevant updates to DT and LI.
436  void deleteDeadLoopBlocks() {
437  if (MSSAU) {
438  SmallSetVector<BasicBlock *, 8> DeadLoopBlocksSet(DeadLoopBlocks.begin(),
439  DeadLoopBlocks.end());
440  MSSAU->removeBlocks(DeadLoopBlocksSet);
441  }
442 
443  // The function LI.erase has some invariants that need to be preserved when
444  // it tries to remove a loop which is not the top-level loop. In particular,
445  // it requires loop's preheader to be strictly in loop's parent. We cannot
446  // just remove blocks one by one, because after removal of preheader we may
447  // break this invariant for the dead loop. So we detatch and erase all dead
448  // loops beforehand.
449  for (auto *BB : DeadLoopBlocks)
450  if (LI.isLoopHeader(BB)) {
451  assert(LI.getLoopFor(BB) != &L && "Attempt to remove current loop!");
452  Loop *DL = LI.getLoopFor(BB);
453  if (!DL->isOutermost()) {
454  for (auto *PL = DL->getParentLoop(); PL; PL = PL->getParentLoop())
455  for (auto *BB : DL->getBlocks())
456  PL->removeBlockFromLoop(BB);
457  DL->getParentLoop()->removeChildLoop(DL);
458  LI.addTopLevelLoop(DL);
459  }
460  LI.erase(DL);
461  }
462 
463  for (auto *BB : DeadLoopBlocks) {
464  assert(BB != L.getHeader() &&
465  "Header of the current loop cannot be dead!");
466  LLVM_DEBUG(dbgs() << "Deleting dead loop block " << BB->getName()
467  << "\n");
468  LI.removeBlock(BB);
469  }
470 
471  detachDeadBlocks(DeadLoopBlocks, &DTUpdates, /*KeepOneInputPHIs*/true);
472  DTU.applyUpdates(DTUpdates);
473  DTUpdates.clear();
474  for (auto *BB : DeadLoopBlocks)
475  DTU.deleteBB(BB);
476 
477  NumLoopBlocksDeleted += DeadLoopBlocks.size();
478  }
479 
480  /// Constant-fold terminators of blocks accumulated in FoldCandidates into the
481  /// unconditional branches.
482  void foldTerminators() {
483  for (BasicBlock *BB : FoldCandidates) {
484  assert(LI.getLoopFor(BB) == &L && "Should be a loop block!");
485  BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(BB);
486  assert(TheOnlySucc && "Should have one live successor!");
487 
488  LLVM_DEBUG(dbgs() << "Replacing terminator of " << BB->getName()
489  << " with an unconditional branch to the block "
490  << TheOnlySucc->getName() << "\n");
491 
492  SmallPtrSet<BasicBlock *, 2> DeadSuccessors;
493  // Remove all BB's successors except for the live one.
494  unsigned TheOnlySuccDuplicates = 0;
495  for (auto *Succ : successors(BB))
496  if (Succ != TheOnlySucc) {
497  DeadSuccessors.insert(Succ);
498  // If our successor lies in a different loop, we don't want to remove
499  // the one-input Phi because it is a LCSSA Phi.
500  bool PreserveLCSSAPhi = !L.contains(Succ);
501  Succ->removePredecessor(BB, PreserveLCSSAPhi);
502  if (MSSAU)
503  MSSAU->removeEdge(BB, Succ);
504  } else
505  ++TheOnlySuccDuplicates;
506 
507  assert(TheOnlySuccDuplicates > 0 && "Should be!");
508  // If TheOnlySucc was BB's successor more than once, after transform it
509  // will be its successor only once. Remove redundant inputs from
510  // TheOnlySucc's Phis.
511  bool PreserveLCSSAPhi = !L.contains(TheOnlySucc);
512  for (unsigned Dup = 1; Dup < TheOnlySuccDuplicates; ++Dup)
513  TheOnlySucc->removePredecessor(BB, PreserveLCSSAPhi);
514  if (MSSAU && TheOnlySuccDuplicates > 1)
515  MSSAU->removeDuplicatePhiEdgesBetween(BB, TheOnlySucc);
516 
517  IRBuilder<> Builder(BB->getContext());
518  Instruction *Term = BB->getTerminator();
519  Builder.SetInsertPoint(Term);
520  Builder.CreateBr(TheOnlySucc);
521  Term->eraseFromParent();
522 
523  for (auto *DeadSucc : DeadSuccessors)
524  DTUpdates.push_back({DominatorTree::Delete, BB, DeadSucc});
525 
526  ++NumTerminatorsFolded;
527  }
528  }
529 
530 public:
531  ConstantTerminatorFoldingImpl(Loop &L, LoopInfo &LI, DominatorTree &DT,
532  ScalarEvolution &SE,
533  MemorySSAUpdater *MSSAU)
534  : L(L), LI(LI), DT(DT), SE(SE), MSSAU(MSSAU), DFS(&L),
535  DTU(DT, DomTreeUpdater::UpdateStrategy::Eager) {}
536  bool run() {
537  assert(L.getLoopLatch() && "Should be single latch!");
538 
539  // Collect all available information about status of blocks after constant
540  // folding.
541  analyze();
542  BasicBlock *Header = L.getHeader();
543  (void)Header;
544 
545  LLVM_DEBUG(dbgs() << "In function " << Header->getParent()->getName()
546  << ": ");
547 
548  if (HasIrreducibleCFG) {
549  LLVM_DEBUG(dbgs() << "Loops with irreducible CFG are not supported!\n");
550  return false;
551  }
552 
553  // Nothing to constant-fold.
554  if (FoldCandidates.empty()) {
555  LLVM_DEBUG(
556  dbgs() << "No constant terminator folding candidates found in loop "
557  << Header->getName() << "\n");
558  return false;
559  }
560 
561  // TODO: Support deletion of the current loop.
562  if (DeleteCurrentLoop) {
563  LLVM_DEBUG(
564  dbgs()
565  << "Give up constant terminator folding in loop " << Header->getName()
566  << ": we don't currently support deletion of the current loop.\n");
567  return false;
568  }
569 
570  // TODO: Support blocks that are not dead, but also not in loop after the
571  // folding.
572  if (BlocksInLoopAfterFolding.size() + DeadLoopBlocks.size() !=
573  L.getNumBlocks()) {
574  LLVM_DEBUG(
575  dbgs() << "Give up constant terminator folding in loop "
576  << Header->getName() << ": we don't currently"
577  " support blocks that are not dead, but will stop "
578  "being a part of the loop after constant-folding.\n");
579  return false;
580  }
581 
582  // TODO: Tokens may breach LCSSA form by default. However, the transform for
583  // dead exit blocks requires LCSSA form to be maintained for all values,
584  // tokens included, otherwise it may break use-def dominance (see PR56243).
585  if (!DeadExitBlocks.empty() && !L.isLCSSAForm(DT, /*IgnoreTokens*/ false)) {
586  assert(L.isLCSSAForm(DT, /*IgnoreTokens*/ true) &&
587  "LCSSA broken not by tokens?");
588  LLVM_DEBUG(dbgs() << "Give up constant terminator folding in loop "
589  << Header->getName()
590  << ": tokens uses potentially break LCSSA form.\n");
591  return false;
592  }
593 
594  SE.forgetTopmostLoop(&L);
595  // Dump analysis results.
596  LLVM_DEBUG(dump());
597 
598  LLVM_DEBUG(dbgs() << "Constant-folding " << FoldCandidates.size()
599  << " terminators in loop " << Header->getName() << "\n");
600 
601  if (!DeadLoopBlocks.empty())
603 
604  // Make the actual transforms.
605  handleDeadExits();
606  foldTerminators();
607 
608  if (!DeadLoopBlocks.empty()) {
609  LLVM_DEBUG(dbgs() << "Deleting " << DeadLoopBlocks.size()
610  << " dead blocks in loop " << Header->getName() << "\n");
611  deleteDeadLoopBlocks();
612  } else {
613  // If we didn't do updates inside deleteDeadLoopBlocks, do them here.
614  DTU.applyUpdates(DTUpdates);
615  DTUpdates.clear();
616  }
617 
618  if (MSSAU && VerifyMemorySSA)
619  MSSAU->getMemorySSA()->verifyMemorySSA();
620 
621 #ifndef NDEBUG
622  // Make sure that we have preserved all data structures after the transform.
623 #if defined(EXPENSIVE_CHECKS)
625  "DT broken after transform!");
626 #else
628  "DT broken after transform!");
629 #endif
630  assert(DT.isReachableFromEntry(Header));
631  LI.verify(DT);
632 #endif
633 
634  return true;
635  }
636 
637  bool foldingBreaksCurrentLoop() const {
638  return DeleteCurrentLoop;
639  }
640 };
641 } // namespace
642 
643 /// Turn branches and switches with known constant conditions into unconditional
644 /// branches.
646  ScalarEvolution &SE,
647  MemorySSAUpdater *MSSAU,
648  bool &IsLoopDeleted) {
649  if (!EnableTermFolding)
650  return false;
651 
652  // To keep things simple, only process loops with single latch. We
653  // canonicalize most loops to this form. We can support multi-latch if needed.
654  if (!L.getLoopLatch())
655  return false;
656 
657  ConstantTerminatorFoldingImpl BranchFolder(L, LI, DT, SE, MSSAU);
658  bool Changed = BranchFolder.run();
659  IsLoopDeleted = Changed && BranchFolder.foldingBreaksCurrentLoop();
660  return Changed;
661 }
662 
664  LoopInfo &LI, MemorySSAUpdater *MSSAU,
665  ScalarEvolution &SE) {
666  bool Changed = false;
668  // Copy blocks into a temporary array to avoid iterator invalidation issues
669  // as we remove them.
671 
672  for (auto &Block : Blocks) {
673  // Attempt to merge blocks in the trivial case. Don't modify blocks which
674  // belong to other loops.
675  BasicBlock *Succ = cast_or_null<BasicBlock>(Block);
676  if (!Succ)
677  continue;
678 
679  BasicBlock *Pred = Succ->getSinglePredecessor();
680  if (!Pred || !Pred->getSingleSuccessor() || LI.getLoopFor(Pred) != &L)
681  continue;
682 
683  // Merge Succ into Pred and delete it.
684  MergeBlockIntoPredecessor(Succ, &DTU, &LI, MSSAU);
685 
686  if (MSSAU && VerifyMemorySSA)
687  MSSAU->getMemorySSA()->verifyMemorySSA();
688 
689  Changed = true;
690  }
691 
692  if (Changed)
694 
695  return Changed;
696 }
697 
698 static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI,
699  ScalarEvolution &SE, MemorySSAUpdater *MSSAU,
700  bool &IsLoopDeleted) {
701  bool Changed = false;
702 
703  // Constant-fold terminators with known constant conditions.
704  Changed |= constantFoldTerminators(L, DT, LI, SE, MSSAU, IsLoopDeleted);
705 
706  if (IsLoopDeleted)
707  return true;
708 
709  // Eliminate unconditional branches by merging blocks into their predecessors.
710  Changed |= mergeBlocksIntoPredecessors(L, DT, LI, MSSAU, SE);
711 
712  if (Changed)
713  SE.forgetTopmostLoop(&L);
714 
715  return Changed;
716 }
717 
720  LPMUpdater &LPMU) {
721  std::optional<MemorySSAUpdater> MSSAU;
722  if (AR.MSSA)
723  MSSAU = MemorySSAUpdater(AR.MSSA);
724  bool DeleteCurrentLoop = false;
725  if (!simplifyLoopCFG(L, AR.DT, AR.LI, AR.SE, MSSAU ? &*MSSAU : nullptr,
726  DeleteCurrentLoop))
727  return PreservedAnalyses::all();
728 
729  if (DeleteCurrentLoop)
730  LPMU.markLoopAsDeleted(L, "loop-simplifycfg");
731 
732  auto PA = getLoopPassPreservedAnalyses();
733  if (AR.MSSA)
734  PA.preserve<MemorySSAAnalysis>();
735  return PA;
736 }
737 
738 namespace {
739 class LoopSimplifyCFGLegacyPass : public LoopPass {
740 public:
741  static char ID; // Pass ID, replacement for typeid
742  LoopSimplifyCFGLegacyPass() : LoopPass(ID) {
744  }
745 
746  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
747  if (skipLoop(L))
748  return false;
749 
750  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
751  LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
752  ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
753  auto *MSSAA = getAnalysisIfAvailable<MemorySSAWrapperPass>();
754  std::optional<MemorySSAUpdater> MSSAU;
755  if (MSSAA)
756  MSSAU = MemorySSAUpdater(&MSSAA->getMSSA());
757  if (MSSAA && VerifyMemorySSA)
758  MSSAU->getMemorySSA()->verifyMemorySSA();
759  bool DeleteCurrentLoop = false;
760  bool Changed = simplifyLoopCFG(*L, DT, LI, SE, MSSAU ? &*MSSAU : nullptr,
761  DeleteCurrentLoop);
762  if (DeleteCurrentLoop)
763  LPM.markLoopAsDeleted(*L);
764  return Changed;
765  }
766 
767  void getAnalysisUsage(AnalysisUsage &AU) const override {
771  }
772 };
773 } // end namespace
774 
776 INITIALIZE_PASS_BEGIN(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
777  "Simplify loop CFG", false, false)
780 INITIALIZE_PASS_END(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
782 
784  return new LoopSimplifyCFGLegacyPass();
785 }
llvm::BranchFolder
Definition: BranchFolding.h:31
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
removeBlockFromLoops
static void removeBlockFromLoops(BasicBlock *BB, Loop *FirstLoop, Loop *LastLoop=nullptr)
Removes BB from all loops from [FirstLoop, LastLoop) in parent chain.
Definition: LoopSimplifyCFG.cpp:80
llvm::MemorySSA::verifyMemorySSA
void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
Definition: MemorySSA.cpp:1865
llvm::DomTreeUpdater::deleteBB
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
Definition: DomTreeUpdater.cpp:177
llvm::LoopBase::getExitBlocks
void getExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all of the successor blocks of this loop.
Definition: LoopInfoImpl.h:64
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
Scalar.h
llvm::DomTreeUpdater::applyUpdates
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Definition: DomTreeUpdater.cpp:230
llvm::DependenceAnalysisWrapperPass
Legacy pass manager pass to access dependence information.
Definition: DependenceAnalysis.h:1001
MemorySSAUpdater.h
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:139
llvm::SmallVector< DominatorTree::UpdateType, 16 >
llvm::LoopInfoBase::verify
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
Definition: LoopInfoImpl.h:699
Statistic.h
llvm::createLoopSimplifyCFGPass
Pass * createLoopSimplifyCFGPass()
Definition: LoopSimplifyCFG.cpp:783
llvm::IRBuilder<>
DomTreeUpdater.h
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:449
RPO
rpo function Deduce function attributes in RPO
Definition: FunctionAttrs.cpp:1902
llvm::LoopInfoBase::changeLoopFor
void changeLoopFor(BlockT *BB, LoopT *L)
Change the top-level loop that contains BB to the specified loop.
Definition: LoopInfo.h:1030
llvm::MemorySSAUpdater::removeBlocks
void removeBlocks(const SmallSetVector< BasicBlock *, 8 > &DeadBlocks)
Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.
Definition: MemorySSAUpdater.cpp:1372
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::getLoopAnalysisUsage
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
Definition: LoopUtils.cpp:142
llvm::detachDeadBlocks
void detachDeadBlocks(ArrayRef< BasicBlock * > BBs, SmallVectorImpl< DominatorTree::UpdateType > *Updates, bool KeepOneInputPHIs=false)
Replace contents of every block in BBs with single unreachable instruction.
Definition: BasicBlockUtils.cpp:61
ScalarEvolution.h
llvm::LoopInfoBase::removeBlock
void removeBlock(BlockT *BB)
This method completely removes BB from all data structures, including all of the Loop objects it is n...
Definition: LoopInfo.h:1057
llvm::LoopStandardAnalysisResults
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Definition: LoopAnalysisManager.h:51
llvm::BasicBlock::getSingleSuccessor
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:315
llvm::DominatorTreeBase< BasicBlock, false >::Insert
static constexpr UpdateKind Insert
Definition: GenericDomTree.h:242
llvm::formLCSSARecursively
bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
Definition: LCSSA.cpp:410
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::successors
auto successors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:29
llvm::BasicBlock::getSinglePredecessor
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:285
llvm::dump
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Definition: SparseBitVector.h:877
llvm::LoopStandardAnalysisResults::DT
DominatorTree & DT
Definition: LoopAnalysisManager.h:54
llvm::Sched::Fast
@ Fast
Definition: TargetLowering.h:104
simplifycfg
loop simplifycfg
Definition: LoopSimplifyCFG.cpp:780
llvm::JumpTable::Full
@ Full
Definition: TargetOptions.h:50
llvm::MemorySSAUpdater::applyUpdates
void applyUpdates(ArrayRef< CFGUpdate > Updates, DominatorTree &DT, bool UpdateDTFirst=false)
Apply CFG updates, analogous with the DT edge updates.
Definition: MemorySSAUpdater.cpp:809
llvm::LoopBase::getNumBlocks
unsigned getNumBlocks() const
Get the number of blocks in this loop in constant time.
Definition: LoopInfo.h:202
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::LoopBlocksDFS::beginRPO
RPOIterator beginRPO() const
Reverse iterate over the cached postorder blocks.
Definition: LoopIterator.h:136
loop
Analysis the ScalarEvolution expression for r is< loop > Outside the loop
Definition: README.txt:8
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::LoopBlocksDFS::isComplete
bool isComplete() const
Return true if postorder numbers are assigned to all loop blocks.
Definition: LoopIterator.h:126
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
CommandLine.h
mergeBlocksIntoPredecessors
static bool mergeBlocksIntoPredecessors(Loop &L, DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU, ScalarEvolution &SE)
Definition: LoopSimplifyCFG.cpp:663
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::LoopBase::getParentLoop
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Definition: LoopInfo.h:114
llvm::all_of
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1734
llvm::MemorySSAWrapperPass
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:984
llvm::initializeLoopSimplifyCFGLegacyPassPass
void initializeLoopSimplifyCFGLegacyPassPass(PassRegistry &)
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
simplifyLoopCFG
static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI, ScalarEvolution &SE, MemorySSAUpdater *MSSAU, bool &IsLoopDeleted)
Definition: LoopSimplifyCFG.cpp:698
llvm::LoopBase::addChildLoop
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
Definition: LoopInfo.h:412
SI
@ SI
Definition: SIInstrInfo.cpp:7966
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::LoopInfoBase::addTopLevelLoop
void addTopLevelLoop(LoopT *New)
This adds the specified loop to the collection of top-level loops.
Definition: LoopInfo.h:1049
llvm::LoopBase::blocks
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:195
false
Definition: StackSlotColoring.cpp:141
llvm::Instruction
Definition: Instruction.h:42
llvm::LoopBlocksDFS::endRPO
RPOIterator endRPO() const
Definition: LoopIterator.h:140
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::predecessors
auto predecessors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:30
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
LoopUtils.h
llvm::AArch64CC::PL
@ PL
Definition: AArch64BaseInfo.h:260
llvm::LPPassManager
Definition: LoopPass.h:76
constantFoldTerminators
static bool constantFoldTerminators(Loop &L, DominatorTree &DT, LoopInfo &LI, ScalarEvolution &SE, MemorySSAUpdater *MSSAU, bool &IsLoopDeleted)
Turn branches and switches with known constant conditions into unconditional branches.
Definition: LoopSimplifyCFG.cpp:645
LoopIterator.h
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::MemorySSAUpdater::removeDuplicatePhiEdgesBetween
void removeDuplicatePhiEdgesBetween(const BasicBlock *From, const BasicBlock *To)
Update the MemoryPhi in To to have a single incoming edge from From, following a CFG change that repl...
Definition: MemorySSAUpdater.cpp:538
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::dxil::PointerTypeAnalysis::run
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
Definition: PointerTypeAnalysis.cpp:189
LoopInfo.h
llvm::LoopBlocksDFS
Store the result of a depth first search within basic blocks contained by a single loop.
Definition: LoopIterator.h:97
llvm::getLoopPassPreservedAnalyses
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
Definition: LoopAnalysisManager.cpp:138
llvm::cl::opt< bool >
llvm::ScalarEvolution::forgetBlockAndLoopDispositions
void forgetBlockAndLoopDispositions(Value *V=nullptr)
Called when the client has changed the disposition of values in a loop or block.
Definition: ScalarEvolution.cpp:8461
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:81
llvm::MemorySSAUpdater::removeEdge
void removeEdge(BasicBlock *From, BasicBlock *To)
Update the MemoryPhi in To following an edge deletion between From and To.
Definition: MemorySSAUpdater.cpp:531
llvm::LoopPass
Definition: LoopPass.h:28
llvm::MemorySSAUpdater
Definition: MemorySSAUpdater.h:54
llvm::LPMUpdater
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Definition: LoopPassManager.h:262
llvm::MemorySSAUpdater::getMemorySSA
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
Definition: MemorySSAUpdater.h:242
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::DenseMap
Definition: DenseMap.h:714
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:992
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:447
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:183
llvm::LoopBlocksDFS::perform
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopInfo.cpp:1222
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:232
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::LoopBase::getLoopDepth
unsigned getLoopDepth() const
Return the nesting level of this loop.
Definition: LoopInfo.h:97
llvm::LoopSimplifyCFGPass::run
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Definition: LoopSimplifyCFG.cpp:718
llvm::DominatorTree::isReachableFromEntry
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:335
llvm::LoopInfo::erase
void erase(Loop *L)
Update LoopInfo after removing the last backedge from a loop.
Definition: LoopInfo.cpp:876
llvm::ScalarEvolution::forgetTopmostLoop
void forgetTopmostLoop(const Loop *L)
Definition: ScalarEvolution.cpp:8428
llvm::LPMUpdater::markLoopAsDeleted
void markLoopAsDeleted(Loop &L, llvm::StringRef Name)
Loop passes should use this method to indicate they have deleted a loop from the nest.
Definition: LoopPassManager.h:282
LoopPassManager.h
llvm::MemorySSAAnalysis
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:934
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
CFG
loop Simplify loop CFG
Definition: LoopSimplifyCFG.cpp:781
llvm::LoopInfo
Definition: LoopInfo.h:1108
llvm::MergeBlockIntoPredecessor
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false)
Attempts to merge a block into its predecessor, if possible.
Definition: BasicBlockUtils.cpp:179
llvm::any_of
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1741
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:138
Simplify
assume Assume Simplify
Definition: AssumeBundleBuilder.cpp:604
LoopPass.h
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::LoopStandardAnalysisResults::LI
LoopInfo & LI
Definition: LoopAnalysisManager.h:55
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::DomTreeUpdater::UpdateStrategy::Eager
@ Eager
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
LoopSimplifyCFG.h
llvm::SmallPtrSetImplBase::size
size_type size() const
Definition: SmallPtrSet.h:93
getOnlyLiveSuccessor
static BasicBlock * getOnlyLiveSuccessor(BasicBlock *BB)
If BB is a switch or a conditional branch, but only one of its successors can be reached from this bl...
Definition: LoopSimplifyCFG.cpp:53
llvm::LoopInfoBase::isLoopHeader
bool isLoopHeader(const BlockT *BB) const
Definition: LoopInfo.h:1005
llvm::LPPassManager::markLoopAsDeleted
void markLoopAsDeleted(Loop &L)
Definition: LoopPass.cpp:110
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(LoopSimplifyCFGLegacyPass, "loop-simplifycfg", "Simplify loop CFG", false, false) INITIALIZE_PASS_END(LoopSimplifyCFGLegacyPass
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:105
llvm::LoopBlocksDFS::beginPostorder
POIterator beginPostorder() const
Iterate over the cached postorder blocks.
Definition: LoopIterator.h:129
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:614
llvm::LoopStandardAnalysisResults::SE
ScalarEvolution & SE
Definition: LoopAnalysisManager.h:56
getInnermostLoopFor
static Loop * getInnermostLoopFor(SmallPtrSetImpl< BasicBlock * > &BBs, Loop &L, LoopInfo &LI)
Find innermost loop that contains at least one block from BBs and contains the header of loop L.
Definition: LoopSimplifyCFG.cpp:92
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
MemorySSA.h
SmallVector.h
Dominators.h
llvm::DominatorTreeBase::verify
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
Definition: GenericDomTree.h:802
llvm::LoopStandardAnalysisResults::MSSA
MemorySSA * MSSA
Definition: LoopAnalysisManager.h:61
llvm::BasicBlock::getTerminator
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:119
llvm::BasicBlock::removePredecessor
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:342
llvm::SmallVectorImpl< BasicBlock * >
llvm::Loop::isLCSSAForm
bool isLCSSAForm(const DominatorTree &DT, bool IgnoreTokens=true) const
Return true if the Loop is in LCSSA form.
Definition: LoopInfo.cpp:462
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::VerifyMemorySSA
bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition: MemorySSA.cpp:91
DependenceAnalysis.h
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::SwitchInst
Multiway switch.
Definition: Instructions.h:3278
llvm::SwitchInst::addCase
void addCase(ConstantInt *OnVal, BasicBlock *Dest)
Add an entry to the switch instruction.
Definition: Instructions.cpp:4518
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3134
llvm::LoopBlocksDFS::endPostorder
POIterator endPostorder() const
Definition: LoopIterator.h:133
BasicBlockUtils.h
llvm::SplitBlock
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
Definition: BasicBlockUtils.cpp:918
InitializePasses.h
EnableTermFolding
static cl::opt< bool > EnableTermFolding("enable-loop-simplifycfg-term-folding", cl::init(true))
llvm::DominatorTreeBase< BasicBlock, false >::Delete
static constexpr UpdateKind Delete
Definition: GenericDomTree.h:243
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:941
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
llvm::PoisonValue::get
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1732