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  // Sanity check: amount of dead and live loop blocks should match the total
260  // number of blocks in loop.
261  assert(L.getNumBlocks() == LiveLoopBlocks.size() + DeadLoopBlocks.size() &&
262  "Malformed block sets?");
263 
264  // Now, all exit blocks that are not marked as live are dead.
265  SmallVector<BasicBlock *, 8> ExitBlocks;
266  L.getExitBlocks(ExitBlocks);
267  SmallPtrSet<BasicBlock *, 8> UniqueDeadExits;
268  for (auto *ExitBlock : ExitBlocks)
269  if (!LiveExitBlocks.count(ExitBlock) &&
270  UniqueDeadExits.insert(ExitBlock).second)
271  DeadExitBlocks.push_back(ExitBlock);
272 
273  // Whether or not the edge From->To will still be present in graph after the
274  // folding.
275  auto IsEdgeLive = [&](BasicBlock *From, BasicBlock *To) {
276  if (!LiveLoopBlocks.count(From))
277  return false;
278  BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(From);
279  return !TheOnlySucc || TheOnlySucc == To || LI.getLoopFor(From) != &L;
280  };
281 
282  // The loop will not be destroyed if its latch is live.
283  DeleteCurrentLoop = !IsEdgeLive(L.getLoopLatch(), L.getHeader());
284 
285  // If we are going to delete the current loop completely, no extra analysis
286  // is needed.
287  if (DeleteCurrentLoop)
288  return;
289 
290  // Otherwise, we should check which blocks will still be a part of the
291  // current loop after the transform.
292  BlocksInLoopAfterFolding.insert(L.getLoopLatch());
293  // If the loop is live, then we should compute what blocks are still in
294  // loop after all branch folding has been done. A block is in loop if
295  // it has a live edge to another block that is in the loop; by definition,
296  // latch is in the loop.
297  auto BlockIsInLoop = [&](BasicBlock *BB) {
298  return any_of(successors(BB), [&](BasicBlock *Succ) {
299  return BlocksInLoopAfterFolding.count(Succ) && IsEdgeLive(BB, Succ);
300  });
301  };
302  for (auto I = DFS.beginPostorder(), E = DFS.endPostorder(); I != E; ++I) {
303  BasicBlock *BB = *I;
304  if (BlockIsInLoop(BB))
305  BlocksInLoopAfterFolding.insert(BB);
306  }
307 
308  // Sanity check: header must be in loop.
309  assert(BlocksInLoopAfterFolding.count(L.getHeader()) &&
310  "Header not in loop?");
311  assert(BlocksInLoopAfterFolding.size() <= LiveLoopBlocks.size() &&
312  "All blocks that stay in loop should be live!");
313  }
314 
315  /// We need to preserve static reachibility of all loop exit blocks (this is)
316  /// required by loop pass manager. In order to do it, we make the following
317  /// trick:
318  ///
319  /// preheader:
320  /// <preheader code>
321  /// br label %loop_header
322  ///
323  /// loop_header:
324  /// ...
325  /// br i1 false, label %dead_exit, label %loop_block
326  /// ...
327  ///
328  /// We cannot simply remove edge from the loop to dead exit because in this
329  /// case dead_exit (and its successors) may become unreachable. To avoid that,
330  /// we insert the following fictive preheader:
331  ///
332  /// preheader:
333  /// <preheader code>
334  /// switch i32 0, label %preheader-split,
335  /// [i32 1, label %dead_exit_1],
336  /// [i32 2, label %dead_exit_2],
337  /// ...
338  /// [i32 N, label %dead_exit_N],
339  ///
340  /// preheader-split:
341  /// br label %loop_header
342  ///
343  /// loop_header:
344  /// ...
345  /// br i1 false, label %dead_exit_N, label %loop_block
346  /// ...
347  ///
348  /// Doing so, we preserve static reachibility of all dead exits and can later
349  /// remove edges from the loop to these blocks.
350  void handleDeadExits() {
351  // If no dead exits, nothing to do.
352  if (DeadExitBlocks.empty())
353  return;
354 
355  // Construct split preheader and the dummy switch to thread edges from it to
356  // dead exits.
357  BasicBlock *Preheader = L.getLoopPreheader();
358  BasicBlock *NewPreheader = llvm::SplitBlock(
359  Preheader, Preheader->getTerminator(), &DT, &LI, MSSAU);
360 
361  IRBuilder<> Builder(Preheader->getTerminator());
362  SwitchInst *DummySwitch =
363  Builder.CreateSwitch(Builder.getInt32(0), NewPreheader);
364  Preheader->getTerminator()->eraseFromParent();
365 
366  unsigned DummyIdx = 1;
367  for (BasicBlock *BB : DeadExitBlocks) {
368  // Eliminate all Phis and LandingPads from dead exits.
369  // TODO: Consider removing all instructions in this dead block.
370  SmallVector<Instruction *, 4> DeadInstructions;
371  for (auto &PN : BB->phis())
372  DeadInstructions.push_back(&PN);
373 
374  if (auto *LandingPad = dyn_cast<LandingPadInst>(BB->getFirstNonPHI()))
375  DeadInstructions.emplace_back(LandingPad);
376 
377  for (Instruction *I : DeadInstructions) {
378  I->replaceAllUsesWith(UndefValue::get(I->getType()));
379  I->eraseFromParent();
380  }
381 
382  assert(DummyIdx != 0 && "Too many dead exits!");
383  DummySwitch->addCase(Builder.getInt32(DummyIdx++), BB);
384  DTUpdates.push_back({DominatorTree::Insert, Preheader, BB});
385  ++NumLoopExitsDeleted;
386  }
387 
388  assert(L.getLoopPreheader() == NewPreheader && "Malformed CFG?");
389  if (Loop *OuterLoop = LI.getLoopFor(Preheader)) {
390  // When we break dead edges, the outer loop may become unreachable from
391  // the current loop. We need to fix loop info accordingly. For this, we
392  // find the most nested loop that still contains L and remove L from all
393  // loops that are inside of it.
394  Loop *StillReachable = getInnermostLoopFor(LiveExitBlocks, L, LI);
395 
396  // Okay, our loop is no longer in the outer loop (and maybe not in some of
397  // its parents as well). Make the fixup.
398  if (StillReachable != OuterLoop) {
399  LI.changeLoopFor(NewPreheader, StillReachable);
400  removeBlockFromLoops(NewPreheader, OuterLoop, StillReachable);
401  for (auto *BB : L.blocks())
402  removeBlockFromLoops(BB, OuterLoop, StillReachable);
403  OuterLoop->removeChildLoop(&L);
404  if (StillReachable)
405  StillReachable->addChildLoop(&L);
406  else
407  LI.addTopLevelLoop(&L);
408 
409  // Some values from loops in [OuterLoop, StillReachable) could be used
410  // in the current loop. Now it is not their child anymore, so such uses
411  // require LCSSA Phis.
412  Loop *FixLCSSALoop = OuterLoop;
413  while (FixLCSSALoop->getParentLoop() != StillReachable)
414  FixLCSSALoop = FixLCSSALoop->getParentLoop();
415  assert(FixLCSSALoop && "Should be a loop!");
416  // We need all DT updates to be done before forming LCSSA.
417  if (MSSAU)
418  MSSAU->applyUpdates(DTUpdates, DT, /*UpdateDT=*/true);
419  else
420  DTU.applyUpdates(DTUpdates);
421  DTUpdates.clear();
422  formLCSSARecursively(*FixLCSSALoop, DT, &LI, &SE);
423  }
424  }
425 
426  if (MSSAU) {
427  // Clear all updates now. Facilitates deletes that follow.
428  MSSAU->applyUpdates(DTUpdates, DT, /*UpdateDT=*/true);
429  DTUpdates.clear();
430  if (VerifyMemorySSA)
431  MSSAU->getMemorySSA()->verifyMemorySSA();
432  }
433  }
434 
435  /// Delete loop blocks that have become unreachable after folding. Make all
436  /// relevant updates to DT and LI.
437  void deleteDeadLoopBlocks() {
438  if (MSSAU) {
439  SmallSetVector<BasicBlock *, 8> DeadLoopBlocksSet(DeadLoopBlocks.begin(),
440  DeadLoopBlocks.end());
441  MSSAU->removeBlocks(DeadLoopBlocksSet);
442  }
443 
444  // The function LI.erase has some invariants that need to be preserved when
445  // it tries to remove a loop which is not the top-level loop. In particular,
446  // it requires loop's preheader to be strictly in loop's parent. We cannot
447  // just remove blocks one by one, because after removal of preheader we may
448  // break this invariant for the dead loop. So we detatch and erase all dead
449  // loops beforehand.
450  for (auto *BB : DeadLoopBlocks)
451  if (LI.isLoopHeader(BB)) {
452  assert(LI.getLoopFor(BB) != &L && "Attempt to remove current loop!");
453  Loop *DL = LI.getLoopFor(BB);
454  if (!DL->isOutermost()) {
455  for (auto *PL = DL->getParentLoop(); PL; PL = PL->getParentLoop())
456  for (auto *BB : DL->getBlocks())
457  PL->removeBlockFromLoop(BB);
458  DL->getParentLoop()->removeChildLoop(DL);
459  LI.addTopLevelLoop(DL);
460  }
461  LI.erase(DL);
462  }
463 
464  for (auto *BB : DeadLoopBlocks) {
465  assert(BB != L.getHeader() &&
466  "Header of the current loop cannot be dead!");
467  LLVM_DEBUG(dbgs() << "Deleting dead loop block " << BB->getName()
468  << "\n");
469  LI.removeBlock(BB);
470  }
471 
472  DetatchDeadBlocks(DeadLoopBlocks, &DTUpdates, /*KeepOneInputPHIs*/true);
473  DTU.applyUpdates(DTUpdates);
474  DTUpdates.clear();
475  for (auto *BB : DeadLoopBlocks)
476  DTU.deleteBB(BB);
477 
478  NumLoopBlocksDeleted += DeadLoopBlocks.size();
479  }
480 
481  /// Constant-fold terminators of blocks acculumated in FoldCandidates into the
482  /// unconditional branches.
483  void foldTerminators() {
484  for (BasicBlock *BB : FoldCandidates) {
485  assert(LI.getLoopFor(BB) == &L && "Should be a loop block!");
486  BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(BB);
487  assert(TheOnlySucc && "Should have one live successor!");
488 
489  LLVM_DEBUG(dbgs() << "Replacing terminator of " << BB->getName()
490  << " with an unconditional branch to the block "
491  << TheOnlySucc->getName() << "\n");
492 
493  SmallPtrSet<BasicBlock *, 2> DeadSuccessors;
494  // Remove all BB's successors except for the live one.
495  unsigned TheOnlySuccDuplicates = 0;
496  for (auto *Succ : successors(BB))
497  if (Succ != TheOnlySucc) {
498  DeadSuccessors.insert(Succ);
499  // If our successor lies in a different loop, we don't want to remove
500  // the one-input Phi because it is a LCSSA Phi.
501  bool PreserveLCSSAPhi = !L.contains(Succ);
502  Succ->removePredecessor(BB, PreserveLCSSAPhi);
503  if (MSSAU)
504  MSSAU->removeEdge(BB, Succ);
505  } else
506  ++TheOnlySuccDuplicates;
507 
508  assert(TheOnlySuccDuplicates > 0 && "Should be!");
509  // If TheOnlySucc was BB's successor more than once, after transform it
510  // will be its successor only once. Remove redundant inputs from
511  // TheOnlySucc's Phis.
512  bool PreserveLCSSAPhi = !L.contains(TheOnlySucc);
513  for (unsigned Dup = 1; Dup < TheOnlySuccDuplicates; ++Dup)
514  TheOnlySucc->removePredecessor(BB, PreserveLCSSAPhi);
515  if (MSSAU && TheOnlySuccDuplicates > 1)
516  MSSAU->removeDuplicatePhiEdgesBetween(BB, TheOnlySucc);
517 
518  IRBuilder<> Builder(BB->getContext());
519  Instruction *Term = BB->getTerminator();
520  Builder.SetInsertPoint(Term);
521  Builder.CreateBr(TheOnlySucc);
522  Term->eraseFromParent();
523 
524  for (auto *DeadSucc : DeadSuccessors)
525  DTUpdates.push_back({DominatorTree::Delete, BB, DeadSucc});
526 
527  ++NumTerminatorsFolded;
528  }
529  }
530 
531 public:
532  ConstantTerminatorFoldingImpl(Loop &L, LoopInfo &LI, DominatorTree &DT,
533  ScalarEvolution &SE,
534  MemorySSAUpdater *MSSAU)
535  : L(L), LI(LI), DT(DT), SE(SE), MSSAU(MSSAU), DFS(&L),
536  DTU(DT, DomTreeUpdater::UpdateStrategy::Eager) {}
537  bool run() {
538  assert(L.getLoopLatch() && "Should be single latch!");
539 
540  // Collect all available information about status of blocks after constant
541  // folding.
542  analyze();
543  BasicBlock *Header = L.getHeader();
544  (void)Header;
545 
546  LLVM_DEBUG(dbgs() << "In function " << Header->getParent()->getName()
547  << ": ");
548 
549  if (HasIrreducibleCFG) {
550  LLVM_DEBUG(dbgs() << "Loops with irreducible CFG are not supported!\n");
551  return false;
552  }
553 
554  // Nothing to constant-fold.
555  if (FoldCandidates.empty()) {
556  LLVM_DEBUG(
557  dbgs() << "No constant terminator folding candidates found in loop "
558  << Header->getName() << "\n");
559  return false;
560  }
561 
562  // TODO: Support deletion of the current loop.
563  if (DeleteCurrentLoop) {
564  LLVM_DEBUG(
565  dbgs()
566  << "Give up constant terminator folding in loop " << Header->getName()
567  << ": we don't currently support deletion of the current loop.\n");
568  return false;
569  }
570 
571  // TODO: Support blocks that are not dead, but also not in loop after the
572  // folding.
573  if (BlocksInLoopAfterFolding.size() + DeadLoopBlocks.size() !=
574  L.getNumBlocks()) {
575  LLVM_DEBUG(
576  dbgs() << "Give up constant terminator folding in loop "
577  << Header->getName() << ": we don't currently"
578  " support blocks that are not dead, but will stop "
579  "being a part of the loop after constant-folding.\n");
580  return false;
581  }
582 
583  SE.forgetTopmostLoop(&L);
584  // Dump analysis results.
585  LLVM_DEBUG(dump());
586 
587  LLVM_DEBUG(dbgs() << "Constant-folding " << FoldCandidates.size()
588  << " terminators in loop " << Header->getName() << "\n");
589 
590  // Make the actual transforms.
591  handleDeadExits();
592  foldTerminators();
593 
594  if (!DeadLoopBlocks.empty()) {
595  LLVM_DEBUG(dbgs() << "Deleting " << DeadLoopBlocks.size()
596  << " dead blocks in loop " << Header->getName() << "\n");
597  deleteDeadLoopBlocks();
598  } else {
599  // If we didn't do updates inside deleteDeadLoopBlocks, do them here.
600  DTU.applyUpdates(DTUpdates);
601  DTUpdates.clear();
602  }
603 
604  if (MSSAU && VerifyMemorySSA)
605  MSSAU->getMemorySSA()->verifyMemorySSA();
606 
607 #ifndef NDEBUG
608  // Make sure that we have preserved all data structures after the transform.
609 #if defined(EXPENSIVE_CHECKS)
611  "DT broken after transform!");
612 #else
614  "DT broken after transform!");
615 #endif
616  assert(DT.isReachableFromEntry(Header));
617  LI.verify(DT);
618 #endif
619 
620  return true;
621  }
622 
623  bool foldingBreaksCurrentLoop() const {
624  return DeleteCurrentLoop;
625  }
626 };
627 } // namespace
628 
629 /// Turn branches and switches with known constant conditions into unconditional
630 /// branches.
632  ScalarEvolution &SE,
633  MemorySSAUpdater *MSSAU,
634  bool &IsLoopDeleted) {
635  if (!EnableTermFolding)
636  return false;
637 
638  // To keep things simple, only process loops with single latch. We
639  // canonicalize most loops to this form. We can support multi-latch if needed.
640  if (!L.getLoopLatch())
641  return false;
642 
643  ConstantTerminatorFoldingImpl BranchFolder(L, LI, DT, SE, MSSAU);
644  bool Changed = BranchFolder.run();
645  IsLoopDeleted = Changed && BranchFolder.foldingBreaksCurrentLoop();
646  return Changed;
647 }
648 
650  LoopInfo &LI, MemorySSAUpdater *MSSAU) {
651  bool Changed = false;
653  // Copy blocks into a temporary array to avoid iterator invalidation issues
654  // as we remove them.
656 
657  for (auto &Block : Blocks) {
658  // Attempt to merge blocks in the trivial case. Don't modify blocks which
659  // belong to other loops.
660  BasicBlock *Succ = cast_or_null<BasicBlock>(Block);
661  if (!Succ)
662  continue;
663 
664  BasicBlock *Pred = Succ->getSinglePredecessor();
665  if (!Pred || !Pred->getSingleSuccessor() || LI.getLoopFor(Pred) != &L)
666  continue;
667 
668  // Merge Succ into Pred and delete it.
669  MergeBlockIntoPredecessor(Succ, &DTU, &LI, MSSAU);
670 
671  if (MSSAU && VerifyMemorySSA)
672  MSSAU->getMemorySSA()->verifyMemorySSA();
673 
674  Changed = true;
675  }
676 
677  return Changed;
678 }
679 
680 static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI,
681  ScalarEvolution &SE, MemorySSAUpdater *MSSAU,
682  bool &IsLoopDeleted) {
683  bool Changed = false;
684 
685  // Constant-fold terminators with known constant conditions.
686  Changed |= constantFoldTerminators(L, DT, LI, SE, MSSAU, IsLoopDeleted);
687 
688  if (IsLoopDeleted)
689  return true;
690 
691  // Eliminate unconditional branches by merging blocks into their predecessors.
692  Changed |= mergeBlocksIntoPredecessors(L, DT, LI, MSSAU);
693 
694  if (Changed)
695  SE.forgetTopmostLoop(&L);
696 
697  return Changed;
698 }
699 
702  LPMUpdater &LPMU) {
704  if (AR.MSSA)
705  MSSAU = MemorySSAUpdater(AR.MSSA);
706  bool DeleteCurrentLoop = false;
707  if (!simplifyLoopCFG(L, AR.DT, AR.LI, AR.SE,
708  MSSAU.hasValue() ? MSSAU.getPointer() : nullptr,
709  DeleteCurrentLoop))
710  return PreservedAnalyses::all();
711 
712  if (DeleteCurrentLoop)
713  LPMU.markLoopAsDeleted(L, "loop-simplifycfg");
714 
715  auto PA = getLoopPassPreservedAnalyses();
716  if (AR.MSSA)
717  PA.preserve<MemorySSAAnalysis>();
718  return PA;
719 }
720 
721 namespace {
722 class LoopSimplifyCFGLegacyPass : public LoopPass {
723 public:
724  static char ID; // Pass ID, replacement for typeid
725  LoopSimplifyCFGLegacyPass() : LoopPass(ID) {
727  }
728 
729  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
730  if (skipLoop(L))
731  return false;
732 
733  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
734  LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
735  ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
736  MemorySSA *MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
737  MemorySSAUpdater MSSAU(MSSA);
738  if (VerifyMemorySSA)
739  MSSA->verifyMemorySSA();
740  bool DeleteCurrentLoop = false;
741  bool Changed = simplifyLoopCFG(*L, DT, LI, SE, &MSSAU, DeleteCurrentLoop);
742  if (DeleteCurrentLoop)
743  LPM.markLoopAsDeleted(*L);
744  return Changed;
745  }
746 
747  void getAnalysisUsage(AnalysisUsage &AU) const override {
752  }
753 };
754 } // end namespace
755 
757 INITIALIZE_PASS_BEGIN(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
758  "Simplify loop CFG", false, false)
761 INITIALIZE_PASS_END(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
763 
765  return new LoopSimplifyCFGLegacyPass();
766 }
llvm::BranchFolder
Definition: BranchFolding.h:33
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
AssumptionCache.h
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
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:1899
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:979
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:689
Statistic.h
llvm::createLoopSimplifyCFGPass
Pass * createLoopSimplifyCFGPass()
Definition: LoopSimplifyCFG.cpp:764
llvm::IRBuilder<>
DomTreeUpdater.h
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:461
RPO
rpo function Deduce function attributes in RPO
Definition: FunctionAttrs.cpp:1728
llvm::LoopInfoBase::changeLoopFor
void changeLoopFor(BlockT *BB, LoopT *L)
Change the top-level loop that contains BB to the specified loop.
Definition: LoopInfo.h:1005
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:1376
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:149
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:1032
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:294
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:403
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::BasicBlock::getSinglePredecessor
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:264
llvm::dump
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Definition: SparseBitVector.h:876
llvm::successors
succ_range successors(Instruction *I)
Definition: CFG.h:262
llvm::LoopStandardAnalysisResults::DT
DominatorTree & DT
Definition: LoopAnalysisManager.h:55
llvm::Sched::Fast
@ Fast
Definition: TargetLowering.h:105
simplifycfg
loop simplifycfg
Definition: LoopSimplifyCFG.cpp:761
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:809
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:981
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:680
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:1024
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:1771
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:631
LoopIterator.h
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
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
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:531
llvm::LoopPass
Definition: LoopPass.h:27
llvm::MemorySSAUpdater
Definition: MemorySSAUpdater.h:56
llvm::LPMUpdater
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Definition: LoopPassManager.h:249
llvm::MemorySSAUpdater::getMemorySSA
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
Definition: MemorySSAUpdater.h:244
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::DenseMap
Definition: DenseMap.h:714
llvm::MemorySSA
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:705
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:967
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
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:700
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:7509
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:269
LoopPassManager.h
llvm::MemorySSAAnalysis
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:931
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:762
llvm::LoopInfo
Definition: LoopInfo.h:1083
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:173
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:1554
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: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:297
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:148
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:980
llvm::LPPassManager::markLoopAsDeleted
void markLoopAsDeleted(Loop &L)
Definition: LoopPass.cpp:113
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:585
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:649
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:61
llvm::BasicBlock::removePredecessor
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:321
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:307
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::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
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:3204
llvm::SwitchInst::addCase
void addCase(ConstantInt *OnVal, BasicBlock *Dest)
Add an entry to the switch instruction.
Definition: Instructions.cpp:4146
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3060
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:814
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:908
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:37