LLVM  14.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"
24 #include "llvm/Analysis/LoopInfo.h"
26 #include "llvm/Analysis/LoopPass.h"
32 #include "llvm/IR/Dominators.h"
33 #include "llvm/IR/IRBuilder.h"
34 #include "llvm/InitializePasses.h"
36 #include "llvm/Transforms/Scalar.h"
38 #include "llvm/Transforms/Utils.h"
42 using namespace llvm;
43 
44 #define DEBUG_TYPE "loop-simplifycfg"
45 
46 static cl::opt<bool> EnableTermFolding("enable-loop-simplifycfg-term-folding",
47  cl::init(true));
48 
49 STATISTIC(NumTerminatorsFolded,
50  "Number of terminators folded to unconditional branches");
51 STATISTIC(NumLoopBlocksDeleted,
52  "Number of loop blocks deleted");
53 STATISTIC(NumLoopExitsDeleted,
54  "Number of loop exiting edges deleted");
55 
56 /// If \p BB is a switch or a conditional branch, but only one of its successors
57 /// can be reached from this block in runtime, return this successor. Otherwise,
58 /// return nullptr.
60  Instruction *TI = BB->getTerminator();
61  if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
62  if (BI->isUnconditional())
63  return nullptr;
64  if (BI->getSuccessor(0) == BI->getSuccessor(1))
65  return BI->getSuccessor(0);
66  ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
67  if (!Cond)
68  return nullptr;
69  return Cond->isZero() ? BI->getSuccessor(1) : BI->getSuccessor(0);
70  }
71 
72  if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
73  auto *CI = dyn_cast<ConstantInt>(SI->getCondition());
74  if (!CI)
75  return nullptr;
76  for (auto Case : SI->cases())
77  if (Case.getCaseValue() == CI)
78  return Case.getCaseSuccessor();
79  return SI->getDefaultDest();
80  }
81 
82  return nullptr;
83 }
84 
85 /// Removes \p BB from all loops from [FirstLoop, LastLoop) in parent chain.
86 static void removeBlockFromLoops(BasicBlock *BB, Loop *FirstLoop,
87  Loop *LastLoop = nullptr) {
88  assert((!LastLoop || LastLoop->contains(FirstLoop->getHeader())) &&
89  "First loop is supposed to be inside of last loop!");
90  assert(FirstLoop->contains(BB) && "Must be a loop block!");
91  for (Loop *Current = FirstLoop; Current != LastLoop;
92  Current = Current->getParentLoop())
93  Current->removeBlockFromLoop(BB);
94 }
95 
96 /// Find innermost loop that contains at least one block from \p BBs and
97 /// contains the header of loop \p L.
99  Loop &L, LoopInfo &LI) {
100  Loop *Innermost = nullptr;
101  for (BasicBlock *BB : BBs) {
102  Loop *BBL = LI.getLoopFor(BB);
103  while (BBL && !BBL->contains(L.getHeader()))
104  BBL = BBL->getParentLoop();
105  if (BBL == &L)
106  BBL = BBL->getParentLoop();
107  if (!BBL)
108  continue;
109  if (!Innermost || BBL->getLoopDepth() > Innermost->getLoopDepth())
110  Innermost = BBL;
111  }
112  return Innermost;
113 }
114 
115 namespace {
116 /// Helper class that can turn branches and switches with constant conditions
117 /// into unconditional branches.
118 class ConstantTerminatorFoldingImpl {
119 private:
120  Loop &L;
121  LoopInfo &LI;
122  DominatorTree &DT;
123  ScalarEvolution &SE;
124  MemorySSAUpdater *MSSAU;
125  LoopBlocksDFS DFS;
126  DomTreeUpdater DTU;
128 
129  // Whether or not the current loop has irreducible CFG.
130  bool HasIrreducibleCFG = false;
131  // Whether or not the current loop will still exist after terminator constant
132  // folding will be done. In theory, there are two ways how it can happen:
133  // 1. Loop's latch(es) become unreachable from loop header;
134  // 2. Loop's header becomes unreachable from method entry.
135  // In practice, the second situation is impossible because we only modify the
136  // current loop and its preheader and do not affect preheader's reachibility
137  // from any other block. So this variable set to true means that loop's latch
138  // has become unreachable from loop header.
139  bool DeleteCurrentLoop = false;
140 
141  // The blocks of the original loop that will still be reachable from entry
142  // after the constant folding.
143  SmallPtrSet<BasicBlock *, 8> LiveLoopBlocks;
144  // The blocks of the original loop that will become unreachable from entry
145  // after the constant folding.
146  SmallVector<BasicBlock *, 8> DeadLoopBlocks;
147  // The exits of the original loop that will still be reachable from entry
148  // after the constant folding.
149  SmallPtrSet<BasicBlock *, 8> LiveExitBlocks;
150  // The exits of the original loop that will become unreachable from entry
151  // after the constant folding.
152  SmallVector<BasicBlock *, 8> DeadExitBlocks;
153  // The blocks that will still be a part of the current loop after folding.
154  SmallPtrSet<BasicBlock *, 8> BlocksInLoopAfterFolding;
155  // The blocks that have terminators with constant condition that can be
156  // folded. Note: fold candidates should be in L but not in any of its
157  // subloops to avoid complex LI updates.
158  SmallVector<BasicBlock *, 8> FoldCandidates;
159 
160  void dump() const {
161  dbgs() << "Constant terminator folding for loop " << L << "\n";
162  dbgs() << "After terminator constant-folding, the loop will";
163  if (!DeleteCurrentLoop)
164  dbgs() << " not";
165  dbgs() << " be destroyed\n";
166  auto PrintOutVector = [&](const char *Message,
168  dbgs() << Message << "\n";
169  for (const BasicBlock *BB : S)
170  dbgs() << "\t" << BB->getName() << "\n";
171  };
172  auto PrintOutSet = [&](const char *Message,
174  dbgs() << Message << "\n";
175  for (const BasicBlock *BB : S)
176  dbgs() << "\t" << BB->getName() << "\n";
177  };
178  PrintOutVector("Blocks in which we can constant-fold terminator:",
179  FoldCandidates);
180  PrintOutSet("Live blocks from the original loop:", LiveLoopBlocks);
181  PrintOutVector("Dead blocks from the original loop:", DeadLoopBlocks);
182  PrintOutSet("Live exit blocks:", LiveExitBlocks);
183  PrintOutVector("Dead exit blocks:", DeadExitBlocks);
184  if (!DeleteCurrentLoop)
185  PrintOutSet("The following blocks will still be part of the loop:",
186  BlocksInLoopAfterFolding);
187  }
188 
189  /// Whether or not the current loop has irreducible CFG.
190  bool hasIrreducibleCFG(LoopBlocksDFS &DFS) {
191  assert(DFS.isComplete() && "DFS is expected to be finished");
192  // Index of a basic block in RPO traversal.
194  unsigned Current = 0;
195  for (auto I = DFS.beginRPO(), E = DFS.endRPO(); I != E; ++I)
196  RPO[*I] = Current++;
197 
198  for (auto I = DFS.beginRPO(), E = DFS.endRPO(); I != E; ++I) {
199  BasicBlock *BB = *I;
200  for (auto *Succ : successors(BB))
201  if (L.contains(Succ) && !LI.isLoopHeader(Succ) && RPO[BB] > RPO[Succ])
202  // If an edge goes from a block with greater order number into a block
203  // with lesses number, and it is not a loop backedge, then it can only
204  // be a part of irreducible non-loop cycle.
205  return true;
206  }
207  return false;
208  }
209 
210  /// Fill all information about status of blocks and exits of the current loop
211  /// if constant folding of all branches will be done.
212  void analyze() {
213  DFS.perform(&LI);
214  assert(DFS.isComplete() && "DFS is expected to be finished");
215 
216  // TODO: The algorithm below relies on both RPO and Postorder traversals.
217  // When the loop has only reducible CFG inside, then the invariant "all
218  // predecessors of X are processed before X in RPO" is preserved. However
219  // an irreducible loop can break this invariant (e.g. latch does not have to
220  // be the last block in the traversal in this case, and the algorithm relies
221  // on this). We can later decide to support such cases by altering the
222  // algorithms, but so far we just give up analyzing them.
223  if (hasIrreducibleCFG(DFS)) {
224  HasIrreducibleCFG = true;
225  return;
226  }
227 
228  // Collect live and dead loop blocks and exits.
229  LiveLoopBlocks.insert(L.getHeader());
230  for (auto I = DFS.beginRPO(), E = DFS.endRPO(); I != E; ++I) {
231  BasicBlock *BB = *I;
232 
233  // If a loop block wasn't marked as live so far, then it's dead.
234  if (!LiveLoopBlocks.count(BB)) {
235  DeadLoopBlocks.push_back(BB);
236  continue;
237  }
238 
239  BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(BB);
240 
241  // If a block has only one live successor, it's a candidate on constant
242  // folding. Only handle blocks from current loop: branches in child loops
243  // are skipped because if they can be folded, they should be folded during
244  // the processing of child loops.
245  bool TakeFoldCandidate = TheOnlySucc && LI.getLoopFor(BB) == &L;
246  if (TakeFoldCandidate)
247  FoldCandidates.push_back(BB);
248 
249  // Handle successors.
250  for (BasicBlock *Succ : successors(BB))
251  if (!TakeFoldCandidate || TheOnlySucc == Succ) {
252  if (L.contains(Succ))
253  LiveLoopBlocks.insert(Succ);
254  else
255  LiveExitBlocks.insert(Succ);
256  }
257  }
258 
259  // Amount of dead and live loop blocks should match the total number of
260  // blocks in loop.
261  assert(L.getNumBlocks() == LiveLoopBlocks.size() + DeadLoopBlocks.size() &&
262  "Malformed block sets?");
263 
264  // Now, all exit blocks that are not marked as live are dead.
265  SmallVector<BasicBlock *, 8> ExitBlocks;
266  L.getExitBlocks(ExitBlocks);
267  SmallPtrSet<BasicBlock *, 8> UniqueDeadExits;
268  for (auto *ExitBlock : ExitBlocks)
269  if (!LiveExitBlocks.count(ExitBlock) &&
270  UniqueDeadExits.insert(ExitBlock).second)
271  DeadExitBlocks.push_back(ExitBlock);
272 
273  // Whether or not the edge From->To will still be present in graph after the
274  // folding.
275  auto IsEdgeLive = [&](BasicBlock *From, BasicBlock *To) {
276  if (!LiveLoopBlocks.count(From))
277  return false;
278  BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(From);
279  return !TheOnlySucc || TheOnlySucc == To || LI.getLoopFor(From) != &L;
280  };
281 
282  // The loop will not be destroyed if its latch is live.
283  DeleteCurrentLoop = !IsEdgeLive(L.getLoopLatch(), L.getHeader());
284 
285  // If we are going to delete the current loop completely, no extra analysis
286  // is needed.
287  if (DeleteCurrentLoop)
288  return;
289 
290  // Otherwise, we should check which blocks will still be a part of the
291  // current loop after the transform.
292  BlocksInLoopAfterFolding.insert(L.getLoopLatch());
293  // If the loop is live, then we should compute what blocks are still in
294  // loop after all branch folding has been done. A block is in loop if
295  // it has a live edge to another block that is in the loop; by definition,
296  // latch is in the loop.
297  auto BlockIsInLoop = [&](BasicBlock *BB) {
298  return any_of(successors(BB), [&](BasicBlock *Succ) {
299  return BlocksInLoopAfterFolding.count(Succ) && IsEdgeLive(BB, Succ);
300  });
301  };
302  for (auto I = DFS.beginPostorder(), E = DFS.endPostorder(); I != E; ++I) {
303  BasicBlock *BB = *I;
304  if (BlockIsInLoop(BB))
305  BlocksInLoopAfterFolding.insert(BB);
306  }
307 
308  assert(BlocksInLoopAfterFolding.count(L.getHeader()) &&
309  "Header not in loop?");
310  assert(BlocksInLoopAfterFolding.size() <= LiveLoopBlocks.size() &&
311  "All blocks that stay in loop should be live!");
312  }
313 
314  /// We need to preserve static reachibility of all loop exit blocks (this is)
315  /// required by loop pass manager. In order to do it, we make the following
316  /// trick:
317  ///
318  /// preheader:
319  /// <preheader code>
320  /// br label %loop_header
321  ///
322  /// loop_header:
323  /// ...
324  /// br i1 false, label %dead_exit, label %loop_block
325  /// ...
326  ///
327  /// We cannot simply remove edge from the loop to dead exit because in this
328  /// case dead_exit (and its successors) may become unreachable. To avoid that,
329  /// we insert the following fictive preheader:
330  ///
331  /// preheader:
332  /// <preheader code>
333  /// switch i32 0, label %preheader-split,
334  /// [i32 1, label %dead_exit_1],
335  /// [i32 2, label %dead_exit_2],
336  /// ...
337  /// [i32 N, label %dead_exit_N],
338  ///
339  /// preheader-split:
340  /// br label %loop_header
341  ///
342  /// loop_header:
343  /// ...
344  /// br i1 false, label %dead_exit_N, label %loop_block
345  /// ...
346  ///
347  /// Doing so, we preserve static reachibility of all dead exits and can later
348  /// remove edges from the loop to these blocks.
349  void handleDeadExits() {
350  // If no dead exits, nothing to do.
351  if (DeadExitBlocks.empty())
352  return;
353 
354  // Construct split preheader and the dummy switch to thread edges from it to
355  // dead exits.
356  BasicBlock *Preheader = L.getLoopPreheader();
357  BasicBlock *NewPreheader = llvm::SplitBlock(
358  Preheader, Preheader->getTerminator(), &DT, &LI, MSSAU);
359 
360  IRBuilder<> Builder(Preheader->getTerminator());
361  SwitchInst *DummySwitch =
362  Builder.CreateSwitch(Builder.getInt32(0), NewPreheader);
363  Preheader->getTerminator()->eraseFromParent();
364 
365  unsigned DummyIdx = 1;
366  for (BasicBlock *BB : DeadExitBlocks) {
367  // Eliminate all Phis and LandingPads from dead exits.
368  // TODO: Consider removing all instructions in this dead block.
369  SmallVector<Instruction *, 4> DeadInstructions;
370  for (auto &PN : BB->phis())
371  DeadInstructions.push_back(&PN);
372 
373  if (auto *LandingPad = dyn_cast<LandingPadInst>(BB->getFirstNonPHI()))
374  DeadInstructions.emplace_back(LandingPad);
375 
376  for (Instruction *I : DeadInstructions) {
377  I->replaceAllUsesWith(UndefValue::get(I->getType()));
378  I->eraseFromParent();
379  }
380 
381  assert(DummyIdx != 0 && "Too many dead exits!");
382  DummySwitch->addCase(Builder.getInt32(DummyIdx++), BB);
383  DTUpdates.push_back({DominatorTree::Insert, Preheader, BB});
384  ++NumLoopExitsDeleted;
385  }
386 
387  assert(L.getLoopPreheader() == NewPreheader && "Malformed CFG?");
388  if (Loop *OuterLoop = LI.getLoopFor(Preheader)) {
389  // When we break dead edges, the outer loop may become unreachable from
390  // the current loop. We need to fix loop info accordingly. For this, we
391  // find the most nested loop that still contains L and remove L from all
392  // loops that are inside of it.
393  Loop *StillReachable = getInnermostLoopFor(LiveExitBlocks, L, LI);
394 
395  // Okay, our loop is no longer in the outer loop (and maybe not in some of
396  // its parents as well). Make the fixup.
397  if (StillReachable != OuterLoop) {
398  LI.changeLoopFor(NewPreheader, StillReachable);
399  removeBlockFromLoops(NewPreheader, OuterLoop, StillReachable);
400  for (auto *BB : L.blocks())
401  removeBlockFromLoops(BB, OuterLoop, StillReachable);
402  OuterLoop->removeChildLoop(&L);
403  if (StillReachable)
404  StillReachable->addChildLoop(&L);
405  else
406  LI.addTopLevelLoop(&L);
407 
408  // Some values from loops in [OuterLoop, StillReachable) could be used
409  // in the current loop. Now it is not their child anymore, so such uses
410  // require LCSSA Phis.
411  Loop *FixLCSSALoop = OuterLoop;
412  while (FixLCSSALoop->getParentLoop() != StillReachable)
413  FixLCSSALoop = FixLCSSALoop->getParentLoop();
414  assert(FixLCSSALoop && "Should be a loop!");
415  // We need all DT updates to be done before forming LCSSA.
416  if (MSSAU)
417  MSSAU->applyUpdates(DTUpdates, DT, /*UpdateDT=*/true);
418  else
419  DTU.applyUpdates(DTUpdates);
420  DTUpdates.clear();
421  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  DetatchDeadBlocks(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 acculumated 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  SE.forgetTopmostLoop(&L);
583  // Dump analysis results.
584  LLVM_DEBUG(dump());
585 
586  LLVM_DEBUG(dbgs() << "Constant-folding " << FoldCandidates.size()
587  << " terminators in loop " << Header->getName() << "\n");
588 
589  // Make the actual transforms.
590  handleDeadExits();
591  foldTerminators();
592 
593  if (!DeadLoopBlocks.empty()) {
594  LLVM_DEBUG(dbgs() << "Deleting " << DeadLoopBlocks.size()
595  << " dead blocks in loop " << Header->getName() << "\n");
596  deleteDeadLoopBlocks();
597  } else {
598  // If we didn't do updates inside deleteDeadLoopBlocks, do them here.
599  DTU.applyUpdates(DTUpdates);
600  DTUpdates.clear();
601  }
602 
603  if (MSSAU && VerifyMemorySSA)
604  MSSAU->getMemorySSA()->verifyMemorySSA();
605 
606 #ifndef NDEBUG
607  // Make sure that we have preserved all data structures after the transform.
608 #if defined(EXPENSIVE_CHECKS)
610  "DT broken after transform!");
611 #else
613  "DT broken after transform!");
614 #endif
615  assert(DT.isReachableFromEntry(Header));
616  LI.verify(DT);
617 #endif
618 
619  return true;
620  }
621 
622  bool foldingBreaksCurrentLoop() const {
623  return DeleteCurrentLoop;
624  }
625 };
626 } // namespace
627 
628 /// Turn branches and switches with known constant conditions into unconditional
629 /// branches.
631  ScalarEvolution &SE,
632  MemorySSAUpdater *MSSAU,
633  bool &IsLoopDeleted) {
634  if (!EnableTermFolding)
635  return false;
636 
637  // To keep things simple, only process loops with single latch. We
638  // canonicalize most loops to this form. We can support multi-latch if needed.
639  if (!L.getLoopLatch())
640  return false;
641 
642  ConstantTerminatorFoldingImpl BranchFolder(L, LI, DT, SE, MSSAU);
643  bool Changed = BranchFolder.run();
644  IsLoopDeleted = Changed && BranchFolder.foldingBreaksCurrentLoop();
645  return Changed;
646 }
647 
649  LoopInfo &LI, MemorySSAUpdater *MSSAU) {
650  bool Changed = false;
652  // Copy blocks into a temporary array to avoid iterator invalidation issues
653  // as we remove them.
655 
656  for (auto &Block : Blocks) {
657  // Attempt to merge blocks in the trivial case. Don't modify blocks which
658  // belong to other loops.
659  BasicBlock *Succ = cast_or_null<BasicBlock>(Block);
660  if (!Succ)
661  continue;
662 
663  BasicBlock *Pred = Succ->getSinglePredecessor();
664  if (!Pred || !Pred->getSingleSuccessor() || LI.getLoopFor(Pred) != &L)
665  continue;
666 
667  // Merge Succ into Pred and delete it.
668  MergeBlockIntoPredecessor(Succ, &DTU, &LI, MSSAU);
669 
670  if (MSSAU && VerifyMemorySSA)
671  MSSAU->getMemorySSA()->verifyMemorySSA();
672 
673  Changed = true;
674  }
675 
676  return Changed;
677 }
678 
679 static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI,
680  ScalarEvolution &SE, MemorySSAUpdater *MSSAU,
681  bool &IsLoopDeleted) {
682  bool Changed = false;
683 
684  // Constant-fold terminators with known constant conditions.
685  Changed |= constantFoldTerminators(L, DT, LI, SE, MSSAU, IsLoopDeleted);
686 
687  if (IsLoopDeleted)
688  return true;
689 
690  // Eliminate unconditional branches by merging blocks into their predecessors.
691  Changed |= mergeBlocksIntoPredecessors(L, DT, LI, MSSAU);
692 
693  if (Changed)
694  SE.forgetTopmostLoop(&L);
695 
696  return Changed;
697 }
698 
701  LPMUpdater &LPMU) {
703  if (AR.MSSA)
704  MSSAU = MemorySSAUpdater(AR.MSSA);
705  bool DeleteCurrentLoop = false;
706  if (!simplifyLoopCFG(L, AR.DT, AR.LI, AR.SE,
707  MSSAU.hasValue() ? MSSAU.getPointer() : nullptr,
708  DeleteCurrentLoop))
709  return PreservedAnalyses::all();
710 
711  if (DeleteCurrentLoop)
712  LPMU.markLoopAsDeleted(L, "loop-simplifycfg");
713 
714  auto PA = getLoopPassPreservedAnalyses();
715  if (AR.MSSA)
716  PA.preserve<MemorySSAAnalysis>();
717  return PA;
718 }
719 
720 namespace {
721 class LoopSimplifyCFGLegacyPass : public LoopPass {
722 public:
723  static char ID; // Pass ID, replacement for typeid
724  LoopSimplifyCFGLegacyPass() : LoopPass(ID) {
726  }
727 
728  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
729  if (skipLoop(L))
730  return false;
731 
732  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
733  LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
734  ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
735  auto *MSSAA = getAnalysisIfAvailable<MemorySSAWrapperPass>();
737  if (MSSAA)
738  MSSAU = MemorySSAUpdater(&MSSAA->getMSSA());
739  if (MSSAA && VerifyMemorySSA)
740  MSSAU->getMemorySSA()->verifyMemorySSA();
741  bool DeleteCurrentLoop = false;
742  bool Changed = simplifyLoopCFG(
743  *L, DT, LI, SE, MSSAU.hasValue() ? MSSAU.getPointer() : nullptr,
744  DeleteCurrentLoop);
745  if (DeleteCurrentLoop)
746  LPM.markLoopAsDeleted(*L);
747  return Changed;
748  }
749 
750  void getAnalysisUsage(AnalysisUsage &AU) const override {
754  }
755 };
756 } // end namespace
757 
759 INITIALIZE_PASS_BEGIN(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
760  "Simplify loop CFG", false, false)
763 INITIALIZE_PASS_END(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
765 
767  return new LoopSimplifyCFGLegacyPass();
768 }
llvm::BranchFolder
Definition: BranchFolding.h:32
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
AssumptionCache.h
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:22
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:86
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:1901
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:62
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
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:976
MemorySSAUpdater.h
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:122
llvm::SmallVector< DominatorTree::UpdateType, 16 >
llvm::LoopInfoBase::verify
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
Definition: LoopInfoImpl.h:690
Statistic.h
llvm::createLoopSimplifyCFGPass
Pass * createLoopSimplifyCFGPass()
Definition: LoopSimplifyCFG.cpp:766
llvm::IRBuilder<>
DomTreeUpdater.h
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:460
RPO
rpo function Deduce function attributes in RPO
Definition: FunctionAttrs.cpp:1953
llvm::LoopInfoBase::changeLoopFor
void changeLoopFor(BlockT *BB, LoopT *L)
Change the top-level loop that contains BB to the specified loop.
Definition: LoopInfo.h:1008
Local.h
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:1371
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::getLoopAnalysisUsage
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
Definition: LoopUtils.cpp:150
GlobalsModRef.h
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:1035
llvm::LoopStandardAnalysisResults
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Definition: LoopAnalysisManager.h:52
llvm::BasicBlock::getSingleSuccessor
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:298
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:405
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::successors
auto successors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:31
llvm::BasicBlock::getSinglePredecessor
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:268
llvm::dump
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Definition: SparseBitVector.h:876
llvm::LoopStandardAnalysisResults::DT
DominatorTree & DT
Definition: LoopAnalysisManager.h:55
llvm::Sched::Fast
@ Fast
Definition: TargetLowering.h:104
simplifycfg
loop simplifycfg
Definition: LoopSimplifyCFG.cpp:763
BasicAliasAnalysis.h
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:808
llvm::LoopBase::getNumBlocks
unsigned getNumBlocks() const
Get the number of blocks in this loop in constant time.
Definition: LoopInfo.h:185
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:58
llvm::Optional::getPointer
constexpr const T * getPointer() const
Definition: Optional.h:280
llvm::LoopBlocksDFS::isComplete
bool isComplete() const
Return true if postorder numbers are assigned to all loop blocks.
Definition: LoopIterator.h:126
llvm::Optional::hasValue
constexpr bool hasValue() const
Definition: Optional.h:288
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::MemorySSAWrapperPass
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:980
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:679
llvm::LoopBase::addChildLoop
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
Definition: LoopInfo.h:395
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:1027
llvm::LoopBase::blocks
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:178
false
Definition: StackSlotColoring.cpp:142
llvm::Instruction
Definition: Instruction.h:45
llvm::LoopBlocksDFS::endRPO
RPOIterator endRPO() const
Definition: LoopIterator.h:140
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1775
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
LoopUtils.h
llvm::AArch64CC::PL
@ PL
Definition: AArch64BaseInfo.h:260
llvm::LPPassManager
Definition: LoopPass.h:75
Utils.h
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:630
LoopIterator.h
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:537
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
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:140
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:78
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:530
llvm::LoopPass
Definition: LoopPass.h:27
llvm::MemorySSAUpdater
Definition: MemorySSAUpdater.h:55
llvm::LPMUpdater
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Definition: LoopPassManager.h:263
llvm::MemorySSAUpdater::getMemorySSA
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
Definition: MemorySSAUpdater.h:243
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:970
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:441
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:167
llvm::LoopBlocksDFS::perform
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopInfo.cpp:1220
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:216
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:699
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::DominatorTree::isReachableFromEntry
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:328
llvm::LoopInfo::erase
void erase(Loop *L)
Update LoopInfo after removing the last backedge from a loop.
Definition: LoopInfo.cpp:878
llvm::ScalarEvolution::forgetTopmostLoop
void forgetTopmostLoop(const Loop *L)
Definition: ScalarEvolution.cpp:7902
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:283
LoopPassManager.h
llvm::MemorySSAAnalysis
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:930
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:382
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:650
CFG
loop Simplify loop CFG
Definition: LoopSimplifyCFG.cpp:764
llvm::LoopInfo
Definition: LoopInfo.h:1086
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:180
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:1599
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:179
Simplify
assume Assume Simplify
Definition: AssumeBundleBuilder.cpp:603
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:56
llvm::DetatchDeadBlocks
void DetatchDeadBlocks(ArrayRef< BasicBlock * > BBs, SmallVectorImpl< DominatorTree::UpdateType > *Updates, bool KeepOneInputPHIs=false)
Replace contents of every block in BBs with single unreachable instruction.
Definition: BasicBlockUtils.cpp:62
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:309
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.cpp:152
LoopSimplifyCFG.h
llvm::SmallPtrSetImplBase::size
size_type size() const
Definition: SmallPtrSet.h:92
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:59
llvm::LoopInfoBase::isLoopHeader
bool isLoopHeader(const BlockT *BB) const
Definition: LoopInfo.h:983
llvm::LPPassManager::markLoopAsDeleted
void markLoopAsDeleted(Loop &L)
Definition: LoopPass.cpp:112
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
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
ScalarEvolutionAliasAnalysis.h
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:580
llvm::LoopStandardAnalysisResults::SE
ScalarEvolution & SE
Definition: LoopAnalysisManager.h:57
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:98
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:648
Dominators.h
llvm::DominatorTreeBase::verify
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
Definition: GenericDomTree.h:802
TargetTransformInfo.h
llvm::LoopStandardAnalysisResults::MSSA
MemorySSA * MSSA
Definition: LoopAnalysisManager.h:62
llvm::BasicBlock::removePredecessor
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:325
llvm::SmallVectorImpl< BasicBlock * >
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:306
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
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:3236
llvm::SwitchInst::addCase
void addCase(ConstantInt *OnVal, BasicBlock *Dest)
Add an entry to the switch instruction.
Definition: Instructions.cpp:4330
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3092
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:839
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
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:916
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:364
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38