LLVM  15.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 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.
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.
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;
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,
161  dbgs() << Message << "\n";
162  for (const BasicBlock *BB : S)
163  dbgs() << "\t" << BB->getName() << "\n";
164  };
165  auto PrintOutSet = [&](const char *Message,
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.
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  SE.forgetTopmostLoop(&L);
580  // Dump analysis results.
581  LLVM_DEBUG(dump());
582 
583  LLVM_DEBUG(dbgs() << "Constant-folding " << FoldCandidates.size()
584  << " terminators in loop " << Header->getName() << "\n");
585 
586  // Make the actual transforms.
587  handleDeadExits();
588  foldTerminators();
589 
590  if (!DeadLoopBlocks.empty()) {
591  LLVM_DEBUG(dbgs() << "Deleting " << DeadLoopBlocks.size()
592  << " dead blocks in loop " << Header->getName() << "\n");
593  deleteDeadLoopBlocks();
594  } else {
595  // If we didn't do updates inside deleteDeadLoopBlocks, do them here.
596  DTU.applyUpdates(DTUpdates);
597  DTUpdates.clear();
598  }
599 
600  if (MSSAU && VerifyMemorySSA)
601  MSSAU->getMemorySSA()->verifyMemorySSA();
602 
603 #ifndef NDEBUG
604  // Make sure that we have preserved all data structures after the transform.
605 #if defined(EXPENSIVE_CHECKS)
607  "DT broken after transform!");
608 #else
610  "DT broken after transform!");
611 #endif
612  assert(DT.isReachableFromEntry(Header));
613  LI.verify(DT);
614 #endif
615 
616  return true;
617  }
618 
619  bool foldingBreaksCurrentLoop() const {
620  return DeleteCurrentLoop;
621  }
622 };
623 } // namespace
624 
625 /// Turn branches and switches with known constant conditions into unconditional
626 /// branches.
628  ScalarEvolution &SE,
629  MemorySSAUpdater *MSSAU,
630  bool &IsLoopDeleted) {
631  if (!EnableTermFolding)
632  return false;
633 
634  // To keep things simple, only process loops with single latch. We
635  // canonicalize most loops to this form. We can support multi-latch if needed.
636  if (!L.getLoopLatch())
637  return false;
638 
639  ConstantTerminatorFoldingImpl BranchFolder(L, LI, DT, SE, MSSAU);
640  bool Changed = BranchFolder.run();
641  IsLoopDeleted = Changed && BranchFolder.foldingBreaksCurrentLoop();
642  return Changed;
643 }
644 
646  LoopInfo &LI, MemorySSAUpdater *MSSAU) {
647  bool Changed = false;
649  // Copy blocks into a temporary array to avoid iterator invalidation issues
650  // as we remove them.
652 
653  for (auto &Block : Blocks) {
654  // Attempt to merge blocks in the trivial case. Don't modify blocks which
655  // belong to other loops.
656  BasicBlock *Succ = cast_or_null<BasicBlock>(Block);
657  if (!Succ)
658  continue;
659 
660  BasicBlock *Pred = Succ->getSinglePredecessor();
661  if (!Pred || !Pred->getSingleSuccessor() || LI.getLoopFor(Pred) != &L)
662  continue;
663 
664  // Merge Succ into Pred and delete it.
665  MergeBlockIntoPredecessor(Succ, &DTU, &LI, MSSAU);
666 
667  if (MSSAU && VerifyMemorySSA)
668  MSSAU->getMemorySSA()->verifyMemorySSA();
669 
670  Changed = true;
671  }
672 
673  return Changed;
674 }
675 
676 static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI,
677  ScalarEvolution &SE, MemorySSAUpdater *MSSAU,
678  bool &IsLoopDeleted) {
679  bool Changed = false;
680 
681  // Constant-fold terminators with known constant conditions.
682  Changed |= constantFoldTerminators(L, DT, LI, SE, MSSAU, IsLoopDeleted);
683 
684  if (IsLoopDeleted)
685  return true;
686 
687  // Eliminate unconditional branches by merging blocks into their predecessors.
688  Changed |= mergeBlocksIntoPredecessors(L, DT, LI, MSSAU);
689 
690  if (Changed)
691  SE.forgetTopmostLoop(&L);
692 
693  return Changed;
694 }
695 
698  LPMUpdater &LPMU) {
700  if (AR.MSSA)
701  MSSAU = MemorySSAUpdater(AR.MSSA);
702  bool DeleteCurrentLoop = false;
703  if (!simplifyLoopCFG(L, AR.DT, AR.LI, AR.SE,
704  MSSAU ? MSSAU.getPointer() : nullptr, DeleteCurrentLoop))
705  return PreservedAnalyses::all();
706 
707  if (DeleteCurrentLoop)
708  LPMU.markLoopAsDeleted(L, "loop-simplifycfg");
709 
710  auto PA = getLoopPassPreservedAnalyses();
711  if (AR.MSSA)
712  PA.preserve<MemorySSAAnalysis>();
713  return PA;
714 }
715 
716 namespace {
717 class LoopSimplifyCFGLegacyPass : public LoopPass {
718 public:
719  static char ID; // Pass ID, replacement for typeid
720  LoopSimplifyCFGLegacyPass() : LoopPass(ID) {
722  }
723 
724  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
725  if (skipLoop(L))
726  return false;
727 
728  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
729  LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
730  ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
731  auto *MSSAA = getAnalysisIfAvailable<MemorySSAWrapperPass>();
733  if (MSSAA)
734  MSSAU = MemorySSAUpdater(&MSSAA->getMSSA());
735  if (MSSAA && VerifyMemorySSA)
736  MSSAU->getMemorySSA()->verifyMemorySSA();
737  bool DeleteCurrentLoop = false;
738  bool Changed =
739  simplifyLoopCFG(*L, DT, LI, SE, MSSAU ? MSSAU.getPointer() : nullptr,
740  DeleteCurrentLoop);
741  if (DeleteCurrentLoop)
742  LPM.markLoopAsDeleted(*L);
743  return Changed;
744  }
745 
746  void getAnalysisUsage(AnalysisUsage &AU) const override {
750  }
751 };
752 } // end namespace
753 
755 INITIALIZE_PASS_BEGIN(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
756  "Simplify loop CFG", false, false)
759 INITIALIZE_PASS_END(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
761 
763  return new LoopSimplifyCFGLegacyPass();
764 }
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
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
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:79
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:1906
llvm::DomTreeUpdater::deleteBB
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
Definition: DomTreeUpdater.cpp:178
llvm::LoopBase::getExitBlocks
void getExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all of the successor blocks of this loop.
Definition: LoopInfoImpl.h:61
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:104
Scalar.h
llvm::DomTreeUpdater::applyUpdates
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Definition: DomTreeUpdater.cpp:231
llvm::DependenceAnalysisWrapperPass
Legacy pass manager pass to access dependence information.
Definition: DependenceAnalysis.h:976
MemorySSAUpdater.h
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:546
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:138
llvm::SmallVector< DominatorTree::UpdateType, 16 >
llvm::LoopInfoBase::verify
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
Definition: LoopInfoImpl.h:687
Statistic.h
llvm::createLoopSimplifyCFGPass
Pass * createLoopSimplifyCFGPass()
Definition: LoopSimplifyCFG.cpp:762
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:1993
llvm::LoopInfoBase::changeLoopFor
void changeLoopFor(BlockT *BB, LoopT *L)
Change the top-level loop that contains BB to the specified loop.
Definition: LoopInfo.h:1024
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:144
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:60
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:1051
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:291
llvm::DominatorTreeBase< BasicBlock, false >::Insert
static constexpr UpdateKind Insert
Definition: GenericDomTree.h:242
llvm::Optional
Definition: APInt.h:33
llvm::formLCSSARecursively
bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
Definition: LCSSA.cpp:404
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:261
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:759
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:201
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::Optional::getPointer
constexpr const T * getPointer() const
Definition: Optional.h:303
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
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:113
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:1617
llvm::MemorySSAWrapperPass
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:998
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:31
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:676
llvm::LoopBase::addChildLoop
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
Definition: LoopInfo.h:411
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:1043
llvm::LoopBase::blocks
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:194
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:627
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:101
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:137
llvm::cl::opt< bool >
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:77
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:716
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:986
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:166
llvm::LoopBlocksDFS::perform
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopInfo.cpp:1221
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:215
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:96
llvm::LoopSimplifyCFGPass::run
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Definition: LoopSimplifyCFG.cpp:696
SI
StandardInstrumentations SI(Debug, VerifyEach)
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:875
llvm::ScalarEvolution::forgetTopmostLoop
void forgetTopmostLoop(const Loop *L)
Definition: ScalarEvolution.cpp:8086
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:948
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:760
llvm::LoopInfo
Definition: LoopInfo.h:1102
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:178
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:1624
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:137
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:305
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:52
llvm::LoopInfoBase::isLoopHeader
bool isLoopHeader(const BlockT *BB) const
Definition: LoopInfo.h:999
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:104
llvm::LoopBlocksDFS::beginPostorder
POIterator beginPostorder() const
Iterate over the cached postorder blocks.
Definition: LoopIterator.h:129
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:591
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:91
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
MemorySSA.h
SmallVector.h
mergeBlocksIntoPredecessors
static bool mergeBlocksIntoPredecessors(Loop &L, DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU)
Definition: LoopSimplifyCFG.cpp:645
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:318
llvm::SmallVectorImpl< BasicBlock * >
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:3230
llvm::SwitchInst::addCase
void addCase(ConstantInt *OnVal, BasicBlock *Dest)
Add an entry to the switch instruction.
Definition: Instructions.cpp:4360
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3086
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:837
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:927
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::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38
llvm::PoisonValue::get
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1796