LLVM  9.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  SmallPtrSet<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  assert(DT.verify() && "DT broken after transform!");
602  assert(DT.isReachableFromEntry(Header));
603  LI.verify(DT);
604 #endif
605 
606  return true;
607  }
608 
609  bool foldingBreaksCurrentLoop() const {
610  return DeleteCurrentLoop;
611  }
612 };
613 } // namespace
614 
615 /// Turn branches and switches with known constant conditions into unconditional
616 /// branches.
618  ScalarEvolution &SE,
619  MemorySSAUpdater *MSSAU,
620  bool &IsLoopDeleted) {
621  if (!EnableTermFolding)
622  return false;
623 
624  // To keep things simple, only process loops with single latch. We
625  // canonicalize most loops to this form. We can support multi-latch if needed.
626  if (!L.getLoopLatch())
627  return false;
628 
629  ConstantTerminatorFoldingImpl BranchFolder(L, LI, DT, SE, MSSAU);
630  bool Changed = BranchFolder.run();
631  IsLoopDeleted = Changed && BranchFolder.foldingBreaksCurrentLoop();
632  return Changed;
633 }
634 
636  LoopInfo &LI, MemorySSAUpdater *MSSAU) {
637  bool Changed = false;
639  // Copy blocks into a temporary array to avoid iterator invalidation issues
640  // as we remove them.
642 
643  for (auto &Block : Blocks) {
644  // Attempt to merge blocks in the trivial case. Don't modify blocks which
645  // belong to other loops.
646  BasicBlock *Succ = cast_or_null<BasicBlock>(Block);
647  if (!Succ)
648  continue;
649 
650  BasicBlock *Pred = Succ->getSinglePredecessor();
651  if (!Pred || !Pred->getSingleSuccessor() || LI.getLoopFor(Pred) != &L)
652  continue;
653 
654  // Merge Succ into Pred and delete it.
655  MergeBlockIntoPredecessor(Succ, &DTU, &LI, MSSAU);
656 
657  Changed = true;
658  }
659 
660  return Changed;
661 }
662 
663 static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI,
664  ScalarEvolution &SE, MemorySSAUpdater *MSSAU,
665  bool &isLoopDeleted) {
666  bool Changed = false;
667 
668  // Constant-fold terminators with known constant conditions.
669  Changed |= constantFoldTerminators(L, DT, LI, SE, MSSAU, isLoopDeleted);
670 
671  if (isLoopDeleted)
672  return true;
673 
674  // Eliminate unconditional branches by merging blocks into their predecessors.
675  Changed |= mergeBlocksIntoPredecessors(L, DT, LI, MSSAU);
676 
677  if (Changed)
678  SE.forgetTopmostLoop(&L);
679 
680  return Changed;
681 }
682 
685  LPMUpdater &LPMU) {
687  if (EnableMSSALoopDependency && AR.MSSA)
688  MSSAU = MemorySSAUpdater(AR.MSSA);
689  bool DeleteCurrentLoop = false;
690  if (!simplifyLoopCFG(L, AR.DT, AR.LI, AR.SE,
691  MSSAU.hasValue() ? MSSAU.getPointer() : nullptr,
692  DeleteCurrentLoop))
693  return PreservedAnalyses::all();
694 
695  if (DeleteCurrentLoop)
696  LPMU.markLoopAsDeleted(L, "loop-simplifycfg");
697 
699 }
700 
701 namespace {
702 class LoopSimplifyCFGLegacyPass : public LoopPass {
703 public:
704  static char ID; // Pass ID, replacement for typeid
705  LoopSimplifyCFGLegacyPass() : LoopPass(ID) {
707  }
708 
709  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
710  if (skipLoop(L))
711  return false;
712 
713  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
714  LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
715  ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
718  MemorySSA *MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
719  MSSAU = MemorySSAUpdater(MSSA);
720  if (VerifyMemorySSA)
721  MSSA->verifyMemorySSA();
722  }
723  bool DeleteCurrentLoop = false;
724  bool Changed = simplifyLoopCFG(
725  *L, DT, LI, SE, MSSAU.hasValue() ? MSSAU.getPointer() : nullptr,
726  DeleteCurrentLoop);
727  if (DeleteCurrentLoop)
728  LPM.markLoopAsDeleted(*L);
729  return Changed;
730  }
731 
732  void getAnalysisUsage(AnalysisUsage &AU) const override {
736  }
739  }
740 };
741 }
742 
744 INITIALIZE_PASS_BEGIN(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
745  "Simplify loop CFG", false, false)
748 INITIALIZE_PASS_END(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
749  "Simplify loop CFG", false, false)
750 
752  return new LoopSimplifyCFGLegacyPass();
753 }
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:224
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:82
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.
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr)
Attempts to merge a block into its predecessor, if possible.
void removeDuplicatePhiEdgesBetween(BasicBlock *From, BasicBlock *To)
Update the MemoryPhi in To to have a single incoming edge from From, following a CFG change that repl...
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:91
The main scalar evolution driver.
void removeBlocks(const SmallPtrSetImpl< BasicBlock *> &DeadBlocks)
Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:173
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:137
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:703
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
Definition: LCSSA.cpp:383
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:957
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:694
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:700
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:742
void erase(Loop *L)
Update LoopInfo after removing the last backedge from a loop.
Definition: LoopInfo.cpp:601
RPOIterator endRPO() const
Definition: LoopIterator.h:140
BlockT * getHeader() const
Definition: LoopInfo.h:99
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:745
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:268
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopInfo.cpp:847
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:427
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:153
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:233
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")
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:1192
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:1424
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
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:109
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:1841
Pass * createLoopSimplifyCFGPass()
void markLoopAsDeleted(Loop &L)
Definition: LoopPass.cpp:142
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:707
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:100
unsigned getNumBlocks() const
Get the number of blocks in this loop in constant time.
Definition: LoopInfo.h:162
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:330
INITIALIZE_PASS_BEGIN(LoopSimplifyCFGLegacyPass, "loop-simplifycfg", "Simplify loop CFG", false, false) INITIALIZE_PASS_END(LoopSimplifyCFGLegacyPass
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:464
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:136
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())
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
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Split the specified block at the specified instruction - everything before SplitPt stays in Old and e...
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:155
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:753
void forgetTopmostLoop(const Loop *L)
cl::opt< bool > EnableMSSALoopDependency
Enables memory ssa as a dependency for loop passes.