LLVM  10.0.0svn
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"
25 #include "llvm/Analysis/LoopInfo.h"
26 #include "llvm/Analysis/LoopPass.h"
32 #include "llvm/IR/Dominators.h"
33 #include "llvm/Transforms/Scalar.h"
35 #include "llvm/Transforms/Utils.h"
39 using namespace llvm;
40 
41 #define DEBUG_TYPE "loop-simplifycfg"
42 
43 static cl::opt<bool> EnableTermFolding("enable-loop-simplifycfg-term-folding",
44  cl::init(true));
45 
46 STATISTIC(NumTerminatorsFolded,
47  "Number of terminators folded to unconditional branches");
48 STATISTIC(NumLoopBlocksDeleted,
49  "Number of loop blocks deleted");
50 STATISTIC(NumLoopExitsDeleted,
51  "Number of loop exiting edges deleted");
52 
53 /// If \p BB is a switch or a conditional branch, but only one of its successors
54 /// can be reached from this block in runtime, return this successor. Otherwise,
55 /// return nullptr.
57  Instruction *TI = BB->getTerminator();
58  if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
59  if (BI->isUnconditional())
60  return nullptr;
61  if (BI->getSuccessor(0) == BI->getSuccessor(1))
62  return BI->getSuccessor(0);
63  ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
64  if (!Cond)
65  return nullptr;
66  return Cond->isZero() ? BI->getSuccessor(1) : BI->getSuccessor(0);
67  }
68 
69  if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
70  auto *CI = dyn_cast<ConstantInt>(SI->getCondition());
71  if (!CI)
72  return nullptr;
73  for (auto Case : SI->cases())
74  if (Case.getCaseValue() == CI)
75  return Case.getCaseSuccessor();
76  return SI->getDefaultDest();
77  }
78 
79  return nullptr;
80 }
81 
82 /// Removes \p BB from all loops from [FirstLoop, LastLoop) in parent chain.
83 static void removeBlockFromLoops(BasicBlock *BB, Loop *FirstLoop,
84  Loop *LastLoop = nullptr) {
85  assert((!LastLoop || LastLoop->contains(FirstLoop->getHeader())) &&
86  "First loop is supposed to be inside of last loop!");
87  assert(FirstLoop->contains(BB) && "Must be a loop block!");
88  for (Loop *Current = FirstLoop; Current != LastLoop;
89  Current = Current->getParentLoop())
90  Current->removeBlockFromLoop(BB);
91 }
92 
93 /// Find innermost loop that contains at least one block from \p BBs and
94 /// contains the header of loop \p L.
96  Loop &L, LoopInfo &LI) {
97  Loop *Innermost = nullptr;
98  for (BasicBlock *BB : BBs) {
99  Loop *BBL = LI.getLoopFor(BB);
100  while (BBL && !BBL->contains(L.getHeader()))
101  BBL = BBL->getParentLoop();
102  if (BBL == &L)
103  BBL = BBL->getParentLoop();
104  if (!BBL)
105  continue;
106  if (!Innermost || BBL->getLoopDepth() > Innermost->getLoopDepth())
107  Innermost = BBL;
108  }
109  return Innermost;
110 }
111 
112 namespace {
113 /// Helper class that can turn branches and switches with constant conditions
114 /// into unconditional branches.
115 class ConstantTerminatorFoldingImpl {
116 private:
117  Loop &L;
118  LoopInfo &LI;
119  DominatorTree &DT;
120  ScalarEvolution &SE;
121  MemorySSAUpdater *MSSAU;
123  DomTreeUpdater DTU;
125 
126  // Whether or not the current loop has irreducible CFG.
127  bool HasIrreducibleCFG = false;
128  // Whether or not the current loop will still exist after terminator constant
129  // folding will be done. In theory, there are two ways how it can happen:
130  // 1. Loop's latch(es) become unreachable from loop header;
131  // 2. Loop's header becomes unreachable from method entry.
132  // In practice, the second situation is impossible because we only modify the
133  // current loop and its preheader and do not affect preheader's reachibility
134  // from any other block. So this variable set to true means that loop's latch
135  // has become unreachable from loop header.
136  bool DeleteCurrentLoop = false;
137 
138  // The blocks of the original loop that will still be reachable from entry
139  // after the constant folding.
140  SmallPtrSet<BasicBlock *, 8> LiveLoopBlocks;
141  // The blocks of the original loop that will become unreachable from entry
142  // after the constant folding.
143  SmallVector<BasicBlock *, 8> DeadLoopBlocks;
144  // The exits of the original loop that will still be reachable from entry
145  // after the constant folding.
146  SmallPtrSet<BasicBlock *, 8> LiveExitBlocks;
147  // The exits of the original loop that will become unreachable from entry
148  // after the constant folding.
149  SmallVector<BasicBlock *, 8> DeadExitBlocks;
150  // The blocks that will still be a part of the current loop after folding.
151  SmallPtrSet<BasicBlock *, 8> BlocksInLoopAfterFolding;
152  // The blocks that have terminators with constant condition that can be
153  // folded. Note: fold candidates should be in L but not in any of its
154  // subloops to avoid complex LI updates.
155  SmallVector<BasicBlock *, 8> FoldCandidates;
156 
157  void dump() const {
158  dbgs() << "Constant terminator folding for loop " << L << "\n";
159  dbgs() << "After terminator constant-folding, the loop will";
160  if (!DeleteCurrentLoop)
161  dbgs() << " not";
162  dbgs() << " be destroyed\n";
163  auto PrintOutVector = [&](const char *Message,
165  dbgs() << Message << "\n";
166  for (const BasicBlock *BB : S)
167  dbgs() << "\t" << BB->getName() << "\n";
168  };
169  auto PrintOutSet = [&](const char *Message,
171  dbgs() << Message << "\n";
172  for (const BasicBlock *BB : S)
173  dbgs() << "\t" << BB->getName() << "\n";
174  };
175  PrintOutVector("Blocks in which we can constant-fold terminator:",
176  FoldCandidates);
177  PrintOutSet("Live blocks from the original loop:", LiveLoopBlocks);
178  PrintOutVector("Dead blocks from the original loop:", DeadLoopBlocks);
179  PrintOutSet("Live exit blocks:", LiveExitBlocks);
180  PrintOutVector("Dead exit blocks:", DeadExitBlocks);
181  if (!DeleteCurrentLoop)
182  PrintOutSet("The following blocks will still be part of the loop:",
183  BlocksInLoopAfterFolding);
184  }
185 
186  /// Whether or not the current loop has irreducible CFG.
187  bool hasIrreducibleCFG(LoopBlocksDFS &DFS) {
188  assert(DFS.isComplete() && "DFS is expected to be finished");
189  // Index of a basic block in RPO traversal.
191  unsigned Current = 0;
192  for (auto I = DFS.beginRPO(), E = DFS.endRPO(); I != E; ++I)
193  RPO[*I] = Current++;
194 
195  for (auto I = DFS.beginRPO(), E = DFS.endRPO(); I != E; ++I) {
196  BasicBlock *BB = *I;
197  for (auto *Succ : successors(BB))
198  if (L.contains(Succ) && !LI.isLoopHeader(Succ) && RPO[BB] > RPO[Succ])
199  // If an edge goes from a block with greater order number into a block
200  // with lesses number, and it is not a loop backedge, then it can only
201  // be a part of irreducible non-loop cycle.
202  return true;
203  }
204  return false;
205  }
206 
207  /// Fill all information about status of blocks and exits of the current loop
208  /// if constant folding of all branches will be done.
209  void analyze() {
210  DFS.perform(&LI);
211  assert(DFS.isComplete() && "DFS is expected to be finished");
212 
213  // TODO: The algorithm below relies on both RPO and Postorder traversals.
214  // When the loop has only reducible CFG inside, then the invariant "all
215  // predecessors of X are processed before X in RPO" is preserved. However
216  // an irreducible loop can break this invariant (e.g. latch does not have to
217  // be the last block in the traversal in this case, and the algorithm relies
218  // on this). We can later decide to support such cases by altering the
219  // algorithms, but so far we just give up analyzing them.
220  if (hasIrreducibleCFG(DFS)) {
221  HasIrreducibleCFG = true;
222  return;
223  }
224 
225  // Collect live and dead loop blocks and exits.
226  LiveLoopBlocks.insert(L.getHeader());
227  for (auto I = DFS.beginRPO(), E = DFS.endRPO(); I != E; ++I) {
228  BasicBlock *BB = *I;
229 
230  // If a loop block wasn't marked as live so far, then it's dead.
231  if (!LiveLoopBlocks.count(BB)) {
232  DeadLoopBlocks.push_back(BB);
233  continue;
234  }
235 
236  BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(BB);
237 
238  // If a block has only one live successor, it's a candidate on constant
239  // folding. Only handle blocks from current loop: branches in child loops
240  // are skipped because if they can be folded, they should be folded during
241  // the processing of child loops.
242  bool TakeFoldCandidate = TheOnlySucc && LI.getLoopFor(BB) == &L;
243  if (TakeFoldCandidate)
244  FoldCandidates.push_back(BB);
245 
246  // Handle successors.
247  for (BasicBlock *Succ : successors(BB))
248  if (!TakeFoldCandidate || TheOnlySucc == Succ) {
249  if (L.contains(Succ))
250  LiveLoopBlocks.insert(Succ);
251  else
252  LiveExitBlocks.insert(Succ);
253  }
254  }
255 
256  // Sanity check: amount of dead and live loop blocks should match the total
257  // number of blocks in loop.
258  assert(L.getNumBlocks() == LiveLoopBlocks.size() + DeadLoopBlocks.size() &&
259  "Malformed block sets?");
260 
261  // Now, all exit blocks that are not marked as live are dead.
262  SmallVector<BasicBlock *, 8> ExitBlocks;
263  L.getExitBlocks(ExitBlocks);
264  SmallPtrSet<BasicBlock *, 8> UniqueDeadExits;
265  for (auto *ExitBlock : ExitBlocks)
266  if (!LiveExitBlocks.count(ExitBlock) &&
267  UniqueDeadExits.insert(ExitBlock).second)
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  // Sanity check: header must be in loop.
306  assert(BlocksInLoopAfterFolding.count(L.getHeader()) &&
307  "Header not in loop?");
308  assert(BlocksInLoopAfterFolding.size() <= LiveLoopBlocks.size() &&
309  "All blocks that stay in loop should be live!");
310  }
311 
312  /// We need to preserve static reachibility of all loop exit blocks (this is)
313  /// required by loop pass manager. In order to do it, we make the following
314  /// trick:
315  ///
316  /// preheader:
317  /// <preheader code>
318  /// br label %loop_header
319  ///
320  /// loop_header:
321  /// ...
322  /// br i1 false, label %dead_exit, label %loop_block
323  /// ...
324  ///
325  /// We cannot simply remove edge from the loop to dead exit because in this
326  /// case dead_exit (and its successors) may become unreachable. To avoid that,
327  /// we insert the following fictive preheader:
328  ///
329  /// preheader:
330  /// <preheader code>
331  /// switch i32 0, label %preheader-split,
332  /// [i32 1, label %dead_exit_1],
333  /// [i32 2, label %dead_exit_2],
334  /// ...
335  /// [i32 N, label %dead_exit_N],
336  ///
337  /// preheader-split:
338  /// br label %loop_header
339  ///
340  /// loop_header:
341  /// ...
342  /// br i1 false, label %dead_exit_N, label %loop_block
343  /// ...
344  ///
345  /// Doing so, we preserve static reachibility of all dead exits and can later
346  /// remove edges from the loop to these blocks.
347  void handleDeadExits() {
348  // If no dead exits, nothing to do.
349  if (DeadExitBlocks.empty())
350  return;
351 
352  // Construct split preheader and the dummy switch to thread edges from it to
353  // dead exits.
354  BasicBlock *Preheader = L.getLoopPreheader();
355  BasicBlock *NewPreheader = llvm::SplitBlock(
356  Preheader, Preheader->getTerminator(), &DT, &LI, MSSAU);
357 
358  IRBuilder<> Builder(Preheader->getTerminator());
359  SwitchInst *DummySwitch =
360  Builder.CreateSwitch(Builder.getInt32(0), NewPreheader);
361  Preheader->getTerminator()->eraseFromParent();
362 
363  unsigned DummyIdx = 1;
364  for (BasicBlock *BB : DeadExitBlocks) {
366  for (auto &PN : BB->phis())
367  DeadPhis.push_back(&PN);
368 
369  // Eliminate all Phis from dead exits.
370  for (Instruction *PN : DeadPhis) {
371  PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
372  PN->eraseFromParent();
373  }
374  assert(DummyIdx != 0 && "Too many dead exits!");
375  DummySwitch->addCase(Builder.getInt32(DummyIdx++), BB);
376  DTUpdates.push_back({DominatorTree::Insert, Preheader, BB});
377  ++NumLoopExitsDeleted;
378  }
379 
380  assert(L.getLoopPreheader() == NewPreheader && "Malformed CFG?");
381  if (Loop *OuterLoop = LI.getLoopFor(Preheader)) {
382  // When we break dead edges, the outer loop may become unreachable from
383  // the current loop. We need to fix loop info accordingly. For this, we
384  // find the most nested loop that still contains L and remove L from all
385  // loops that are inside of it.
386  Loop *StillReachable = getInnermostLoopFor(LiveExitBlocks, L, LI);
387 
388  // Okay, our loop is no longer in the outer loop (and maybe not in some of
389  // its parents as well). Make the fixup.
390  if (StillReachable != OuterLoop) {
391  LI.changeLoopFor(NewPreheader, StillReachable);
392  removeBlockFromLoops(NewPreheader, OuterLoop, StillReachable);
393  for (auto *BB : L.blocks())
394  removeBlockFromLoops(BB, OuterLoop, StillReachable);
395  OuterLoop->removeChildLoop(&L);
396  if (StillReachable)
397  StillReachable->addChildLoop(&L);
398  else
399  LI.addTopLevelLoop(&L);
400 
401  // Some values from loops in [OuterLoop, StillReachable) could be used
402  // in the current loop. Now it is not their child anymore, so such uses
403  // require LCSSA Phis.
404  Loop *FixLCSSALoop = OuterLoop;
405  while (FixLCSSALoop->getParentLoop() != StillReachable)
406  FixLCSSALoop = FixLCSSALoop->getParentLoop();
407  assert(FixLCSSALoop && "Should be a loop!");
408  // We need all DT updates to be done before forming LCSSA.
409  DTU.applyUpdates(DTUpdates);
410  if (MSSAU)
411  MSSAU->applyUpdates(DTUpdates, DT);
412  DTUpdates.clear();
413  formLCSSARecursively(*FixLCSSALoop, DT, &LI, &SE);
414  }
415  }
416 
417  if (MSSAU) {
418  // Clear all updates now. Facilitates deletes that follow.
419  DTU.applyUpdates(DTUpdates);
420  MSSAU->applyUpdates(DTUpdates, DT);
421  DTUpdates.clear();
422  if (VerifyMemorySSA)
423  MSSAU->getMemorySSA()->verifyMemorySSA();
424  }
425  }
426 
427  /// Delete loop blocks that have become unreachable after folding. Make all
428  /// relevant updates to DT and LI.
429  void deleteDeadLoopBlocks() {
430  if (MSSAU) {
431  SmallSetVector<BasicBlock *, 8> DeadLoopBlocksSet(DeadLoopBlocks.begin(),
432  DeadLoopBlocks.end());
433  MSSAU->removeBlocks(DeadLoopBlocksSet);
434  }
435 
436  // The function LI.erase has some invariants that need to be preserved when
437  // it tries to remove a loop which is not the top-level loop. In particular,
438  // it requires loop's preheader to be strictly in loop's parent. We cannot
439  // just remove blocks one by one, because after removal of preheader we may
440  // break this invariant for the dead loop. So we detatch and erase all dead
441  // loops beforehand.
442  for (auto *BB : DeadLoopBlocks)
443  if (LI.isLoopHeader(BB)) {
444  assert(LI.getLoopFor(BB) != &L && "Attempt to remove current loop!");
445  Loop *DL = LI.getLoopFor(BB);
446  if (DL->getParentLoop()) {
447  for (auto *PL = DL->getParentLoop(); PL; PL = PL->getParentLoop())
448  for (auto *BB : DL->getBlocks())
449  PL->removeBlockFromLoop(BB);
450  DL->getParentLoop()->removeChildLoop(DL);
451  LI.addTopLevelLoop(DL);
452  }
453  LI.erase(DL);
454  }
455 
456  for (auto *BB : DeadLoopBlocks) {
457  assert(BB != L.getHeader() &&
458  "Header of the current loop cannot be dead!");
459  LLVM_DEBUG(dbgs() << "Deleting dead loop block " << BB->getName()
460  << "\n");
461  LI.removeBlock(BB);
462  }
463 
464  DetatchDeadBlocks(DeadLoopBlocks, &DTUpdates, /*KeepOneInputPHIs*/true);
465  DTU.applyUpdates(DTUpdates);
466  DTUpdates.clear();
467  for (auto *BB : DeadLoopBlocks)
468  DTU.deleteBB(BB);
469 
470  NumLoopBlocksDeleted += DeadLoopBlocks.size();
471  }
472 
473  /// Constant-fold terminators of blocks acculumated in FoldCandidates into the
474  /// unconditional branches.
475  void foldTerminators() {
476  for (BasicBlock *BB : FoldCandidates) {
477  assert(LI.getLoopFor(BB) == &L && "Should be a loop block!");
478  BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(BB);
479  assert(TheOnlySucc && "Should have one live successor!");
480 
481  LLVM_DEBUG(dbgs() << "Replacing terminator of " << BB->getName()
482  << " with an unconditional branch to the block "
483  << TheOnlySucc->getName() << "\n");
484 
485  SmallPtrSet<BasicBlock *, 2> DeadSuccessors;
486  // Remove all BB's successors except for the live one.
487  unsigned TheOnlySuccDuplicates = 0;
488  for (auto *Succ : successors(BB))
489  if (Succ != TheOnlySucc) {
490  DeadSuccessors.insert(Succ);
491  // If our successor lies in a different loop, we don't want to remove
492  // the one-input Phi because it is a LCSSA Phi.
493  bool PreserveLCSSAPhi = !L.contains(Succ);
494  Succ->removePredecessor(BB, PreserveLCSSAPhi);
495  if (MSSAU)
496  MSSAU->removeEdge(BB, Succ);
497  } else
498  ++TheOnlySuccDuplicates;
499 
500  assert(TheOnlySuccDuplicates > 0 && "Should be!");
501  // If TheOnlySucc was BB's successor more than once, after transform it
502  // will be its successor only once. Remove redundant inputs from
503  // TheOnlySucc's Phis.
504  bool PreserveLCSSAPhi = !L.contains(TheOnlySucc);
505  for (unsigned Dup = 1; Dup < TheOnlySuccDuplicates; ++Dup)
506  TheOnlySucc->removePredecessor(BB, PreserveLCSSAPhi);
507  if (MSSAU && TheOnlySuccDuplicates > 1)
508  MSSAU->removeDuplicatePhiEdgesBetween(BB, TheOnlySucc);
509 
510  IRBuilder<> Builder(BB->getContext());
511  Instruction *Term = BB->getTerminator();
512  Builder.SetInsertPoint(Term);
513  Builder.CreateBr(TheOnlySucc);
514  Term->eraseFromParent();
515 
516  for (auto *DeadSucc : DeadSuccessors)
517  DTUpdates.push_back({DominatorTree::Delete, BB, DeadSucc});
518 
519  ++NumTerminatorsFolded;
520  }
521  }
522 
523 public:
524  ConstantTerminatorFoldingImpl(Loop &L, LoopInfo &LI, DominatorTree &DT,
525  ScalarEvolution &SE,
526  MemorySSAUpdater *MSSAU)
527  : L(L), LI(LI), DT(DT), SE(SE), MSSAU(MSSAU), DFS(&L),
529  bool run() {
530  assert(L.getLoopLatch() && "Should be single latch!");
531 
532  // Collect all available information about status of blocks after constant
533  // folding.
534  analyze();
535  BasicBlock *Header = L.getHeader();
536  (void)Header;
537 
538  LLVM_DEBUG(dbgs() << "In function " << Header->getParent()->getName()
539  << ": ");
540 
541  if (HasIrreducibleCFG) {
542  LLVM_DEBUG(dbgs() << "Loops with irreducible CFG are not supported!\n");
543  return false;
544  }
545 
546  // Nothing to constant-fold.
547  if (FoldCandidates.empty()) {
548  LLVM_DEBUG(
549  dbgs() << "No constant terminator folding candidates found in loop "
550  << Header->getName() << "\n");
551  return false;
552  }
553 
554  // TODO: Support deletion of the current loop.
555  if (DeleteCurrentLoop) {
556  LLVM_DEBUG(
557  dbgs()
558  << "Give up constant terminator folding in loop " << Header->getName()
559  << ": we don't currently support deletion of the current loop.\n");
560  return false;
561  }
562 
563  // TODO: Support blocks that are not dead, but also not in loop after the
564  // folding.
565  if (BlocksInLoopAfterFolding.size() + DeadLoopBlocks.size() !=
566  L.getNumBlocks()) {
567  LLVM_DEBUG(
568  dbgs() << "Give up constant terminator folding in loop "
569  << Header->getName() << ": we don't currently"
570  " support blocks that are not dead, but will stop "
571  "being a part of the loop after constant-folding.\n");
572  return false;
573  }
574 
575  SE.forgetTopmostLoop(&L);
576  // Dump analysis results.
577  LLVM_DEBUG(dump());
578 
579  LLVM_DEBUG(dbgs() << "Constant-folding " << FoldCandidates.size()
580  << " terminators in loop " << Header->getName() << "\n");
581 
582  // Make the actual transforms.
583  handleDeadExits();
584  foldTerminators();
585 
586  if (!DeadLoopBlocks.empty()) {
587  LLVM_DEBUG(dbgs() << "Deleting " << DeadLoopBlocks.size()
588  << " dead blocks in loop " << Header->getName() << "\n");
589  deleteDeadLoopBlocks();
590  } else {
591  // If we didn't do updates inside deleteDeadLoopBlocks, do them here.
592  DTU.applyUpdates(DTUpdates);
593  DTUpdates.clear();
594  }
595 
596  if (MSSAU && VerifyMemorySSA)
597  MSSAU->getMemorySSA()->verifyMemorySSA();
598 
599 #ifndef NDEBUG
600  // Make sure that we have preserved all data structures after the transform.
601 #if defined(EXPENSIVE_CHECKS)
603  "DT broken after transform!");
604 #else
606  "DT broken after transform!");
607 #endif
608  assert(DT.isReachableFromEntry(Header));
609  LI.verify(DT);
610 #endif
611 
612  return true;
613  }
614 
615  bool foldingBreaksCurrentLoop() const {
616  return DeleteCurrentLoop;
617  }
618 };
619 } // namespace
620 
621 /// Turn branches and switches with known constant conditions into unconditional
622 /// branches.
624  ScalarEvolution &SE,
625  MemorySSAUpdater *MSSAU,
626  bool &IsLoopDeleted) {
627  if (!EnableTermFolding)
628  return false;
629 
630  // To keep things simple, only process loops with single latch. We
631  // canonicalize most loops to this form. We can support multi-latch if needed.
632  if (!L.getLoopLatch())
633  return false;
634 
635  ConstantTerminatorFoldingImpl BranchFolder(L, LI, DT, SE, MSSAU);
636  bool Changed = BranchFolder.run();
637  IsLoopDeleted = Changed && BranchFolder.foldingBreaksCurrentLoop();
638  return Changed;
639 }
640 
642  LoopInfo &LI, MemorySSAUpdater *MSSAU) {
643  bool Changed = false;
645  // Copy blocks into a temporary array to avoid iterator invalidation issues
646  // as we remove them.
648 
649  for (auto &Block : Blocks) {
650  // Attempt to merge blocks in the trivial case. Don't modify blocks which
651  // belong to other loops.
652  BasicBlock *Succ = cast_or_null<BasicBlock>(Block);
653  if (!Succ)
654  continue;
655 
656  BasicBlock *Pred = Succ->getSinglePredecessor();
657  if (!Pred || !Pred->getSingleSuccessor() || LI.getLoopFor(Pred) != &L)
658  continue;
659 
660  // Merge Succ into Pred and delete it.
661  MergeBlockIntoPredecessor(Succ, &DTU, &LI, MSSAU);
662 
663  Changed = true;
664  }
665 
666  return Changed;
667 }
668 
669 static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI,
670  ScalarEvolution &SE, MemorySSAUpdater *MSSAU,
671  bool &isLoopDeleted) {
672  bool Changed = false;
673 
674  // Constant-fold terminators with known constant conditions.
675  Changed |= constantFoldTerminators(L, DT, LI, SE, MSSAU, isLoopDeleted);
676 
677  if (isLoopDeleted)
678  return true;
679 
680  // Eliminate unconditional branches by merging blocks into their predecessors.
681  Changed |= mergeBlocksIntoPredecessors(L, DT, LI, MSSAU);
682 
683  if (Changed)
684  SE.forgetTopmostLoop(&L);
685 
686  return Changed;
687 }
688 
691  LPMUpdater &LPMU) {
693  if (AR.MSSA)
694  MSSAU = MemorySSAUpdater(AR.MSSA);
695  bool DeleteCurrentLoop = false;
696  if (!simplifyLoopCFG(L, AR.DT, AR.LI, AR.SE,
697  MSSAU.hasValue() ? MSSAU.getPointer() : nullptr,
698  DeleteCurrentLoop))
699  return PreservedAnalyses::all();
700 
701  if (DeleteCurrentLoop)
702  LPMU.markLoopAsDeleted(L, "loop-simplifycfg");
703 
704  auto PA = getLoopPassPreservedAnalyses();
705  if (AR.MSSA)
706  PA.preserve<MemorySSAAnalysis>();
707  return PA;
708 }
709 
710 namespace {
711 class LoopSimplifyCFGLegacyPass : public LoopPass {
712 public:
713  static char ID; // Pass ID, replacement for typeid
714  LoopSimplifyCFGLegacyPass() : LoopPass(ID) {
716  }
717 
718  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
719  if (skipLoop(L))
720  return false;
721 
722  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
723  LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
724  ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
727  MemorySSA *MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
728  MSSAU = MemorySSAUpdater(MSSA);
729  if (VerifyMemorySSA)
730  MSSA->verifyMemorySSA();
731  }
732  bool DeleteCurrentLoop = false;
733  bool Changed = simplifyLoopCFG(
734  *L, DT, LI, SE, MSSAU.hasValue() ? MSSAU.getPointer() : nullptr,
735  DeleteCurrentLoop);
736  if (DeleteCurrentLoop)
737  LPM.markLoopAsDeleted(*L);
738  return Changed;
739  }
740 
741  void getAnalysisUsage(AnalysisUsage &AU) const override {
745  }
748  }
749 };
750 }
751 
753 INITIALIZE_PASS_BEGIN(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
754  "Simplify loop CFG", false, false)
757 INITIALIZE_PASS_END(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
758  "Simplify loop CFG", false, false)
759 
761  return new LoopSimplifyCFGLegacyPass();
762 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:67
static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI, ScalarEvolution &SE, MemorySSAUpdater *MSSAU, bool &isLoopDeleted)
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:209
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition: MemorySSA.cpp:83
This class represents lattice values for constants.
Definition: AllocatorList.h:23
This header provides classes for managing a pipeline of passes over loops in LLVM IR...
This is the interface for a simple mod/ref and alias analysis over globals.
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
static bool mergeBlocksIntoPredecessors(Loop &L, DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU)
Legacy pass manager pass to access dependence information.
unsigned getLoopDepth() const
Return the nesting level of this loop.
Definition: LoopInfo.h:97
The main scalar evolution driver.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:160
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...
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...
STATISTIC(NumFunctions, "Total number of functions")
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
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:144
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the specified block at the specified instruction - everything before SplitPt stays in Old and e...
bool isComplete() const
Return true if postorder numbers are assigned to all loop blocks.
Definition: LoopIterator.h:126
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:299
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
Definition: LoopInfoImpl.h:681
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
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.
bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
Definition: LCSSA.cpp:385
void removeEdge(BasicBlock *From, BasicBlock *To)
Update the MemoryPhi in To following an edge deletion between From and To.
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:965
This is the interface for a SCEV-based alias analysis.
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
POIterator beginPostorder() const
Iterate over the cached postorder blocks.
Definition: LoopIterator.h:129
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
loop simplifycfg
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:928
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:703
void applyUpdates(ArrayRef< CFGUpdate > Updates, DominatorTree &DT)
Apply CFG updates, analogous with the DT edge updates.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:779
void erase(Loop *L)
Update LoopInfo after removing the last backedge from a loop.
Definition: LoopInfo.cpp:857
RPOIterator endRPO() const
Definition: LoopIterator.h:140
BlockT * getHeader() const
Definition: LoopInfo.h:105
void getExitBlocks(SmallVectorImpl< BlockT *> &ExitBlocks) const
Return all of the successor blocks of this loop.
Definition: LoopInfoImpl.h:62
void addTopLevelLoop(LoopT *New)
This adds the specified loop to the collection of top-level loops.
Definition: LoopInfo.h:979
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:275
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopInfo.cpp:1103
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
static cl::opt< bool > EnableTermFolding("enable-loop-simplifycfg-term-folding", cl::init(true))
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:240
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
Conditional or Unconditional Branch instruction.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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...
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:370
Represent the analysis usage information of a pass.
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:1172
Fast - This calling convention attempts to make calls as fast as possible (e.g.
Definition: CallingConv.h:42
const T * getPointer() const
Definition: Optional.h:253
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:381
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1446
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:160
size_t size() const
Definition: SmallVector.h:52
void markLoopAsDeleted(Loop &L, llvm::StringRef Name)
Loop passes should use this method to indicate they have deleted a loop from the nest.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
size_type size() const
Definition: SmallPtrSet.h:92
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:115
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:297
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
BlockVerifier::State From
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.
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
void verifyMemorySSA() const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
Definition: MemorySSA.cpp:1870
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:926
Pass * createLoopSimplifyCFGPass()
void markLoopAsDeleted(Loop &L)
Definition: LoopPass.cpp:143
loop Simplify loop CFG
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Store the result of a depth first search within basic blocks contained by a single loop...
Definition: LoopIterator.h:97
static void DFS(BasicBlock *Root, SetVector< BasicBlock *> &Set)
bool isLoopHeader(const BlockT *BB) const
Definition: LoopInfo.h:941
void initializeLoopSimplifyCFGLegacyPassPass(PassRegistry &)
static void removeBlockFromLoops(BasicBlock *BB, Loop *FirstLoop, Loop *LastLoop=nullptr)
Removes BB from all loops from [FirstLoop, LastLoop) in parent chain.
POIterator endPostorder() const
Definition: LoopIterator.h:133
LoopT * getParentLoop() const
Definition: LoopInfo.h:106
unsigned getNumBlocks() const
Get the number of blocks in this loop in constant time.
Definition: LoopInfo.h:168
bool hasValue() const
Definition: Optional.h:259
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
Definition: LoopInfo.h:375
INITIALIZE_PASS_BEGIN(LoopSimplifyCFGLegacyPass, "loop-simplifycfg", "Simplify loop CFG", false, false) INITIALIZE_PASS_END(LoopSimplifyCFGLegacyPass
cl::opt< bool > EnableMSSALoopDependency
Enables memory ssa as a dependency for loop passes.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:509
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
#define I(x, y, z)
Definition: MD5.cpp:58
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
Definition: Constants.h:192
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass&#39;s AnalysisUsage.
Definition: LoopUtils.cpp:138
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
Multiway switch.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void removeBlocks(const SmallSetVector< BasicBlock *, 8 > &DeadBlocks)
Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.
rpo Deduce function attributes in RPO
succ_range successors(Instruction *I)
Definition: CFG.h:259
RPOIterator beginRPO() const
Reverse iterate over the cached postorder blocks.
Definition: LoopIterator.h:136
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
This is the interface for LLVM&#39;s primary stateless and local alias analysis.
A container for analyses that lazily runs them and caches their results.
This pass exposes codegen information to IR-level passes.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:161
void DetatchDeadBlocks(ArrayRef< BasicBlock *> BBs, SmallVectorImpl< DominatorTree::UpdateType > *Updates, bool KeepOneInputPHIs=false)
Replace contents of every block in BBs with single unreachable instruction.
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:987
void forgetTopmostLoop(const Loop *L)