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 namespace {
94 /// Helper class that can turn branches and switches with constant conditions
95 /// into unconditional branches.
96 class ConstantTerminatorFoldingImpl {
97 private:
98  Loop &L;
99  LoopInfo &LI;
100  DominatorTree &DT;
101  ScalarEvolution &SE;
102  MemorySSAUpdater *MSSAU;
104  DomTreeUpdater DTU;
106 
107  // Whether or not the current loop has irreducible CFG.
108  bool HasIrreducibleCFG = false;
109  // Whether or not the current loop will still exist after terminator constant
110  // folding will be done. In theory, there are two ways how it can happen:
111  // 1. Loop's latch(es) become unreachable from loop header;
112  // 2. Loop's header becomes unreachable from method entry.
113  // In practice, the second situation is impossible because we only modify the
114  // current loop and its preheader and do not affect preheader's reachibility
115  // from any other block. So this variable set to true means that loop's latch
116  // has become unreachable from loop header.
117  bool DeleteCurrentLoop = false;
118 
119  // The blocks of the original loop that will still be reachable from entry
120  // after the constant folding.
121  SmallPtrSet<BasicBlock *, 8> LiveLoopBlocks;
122  // The blocks of the original loop that will become unreachable from entry
123  // after the constant folding.
124  SmallVector<BasicBlock *, 8> DeadLoopBlocks;
125  // The exits of the original loop that will still be reachable from entry
126  // after the constant folding.
127  SmallPtrSet<BasicBlock *, 8> LiveExitBlocks;
128  // The exits of the original loop that will become unreachable from entry
129  // after the constant folding.
130  SmallVector<BasicBlock *, 8> DeadExitBlocks;
131  // The blocks that will still be a part of the current loop after folding.
132  SmallPtrSet<BasicBlock *, 8> BlocksInLoopAfterFolding;
133  // The blocks that have terminators with constant condition that can be
134  // folded. Note: fold candidates should be in L but not in any of its
135  // subloops to avoid complex LI updates.
136  SmallVector<BasicBlock *, 8> FoldCandidates;
137 
138  void dump() const {
139  dbgs() << "Constant terminator folding for loop " << L << "\n";
140  dbgs() << "After terminator constant-folding, the loop will";
141  if (!DeleteCurrentLoop)
142  dbgs() << " not";
143  dbgs() << " be destroyed\n";
144  auto PrintOutVector = [&](const char *Message,
146  dbgs() << Message << "\n";
147  for (const BasicBlock *BB : S)
148  dbgs() << "\t" << BB->getName() << "\n";
149  };
150  auto PrintOutSet = [&](const char *Message,
152  dbgs() << Message << "\n";
153  for (const BasicBlock *BB : S)
154  dbgs() << "\t" << BB->getName() << "\n";
155  };
156  PrintOutVector("Blocks in which we can constant-fold terminator:",
157  FoldCandidates);
158  PrintOutSet("Live blocks from the original loop:", LiveLoopBlocks);
159  PrintOutVector("Dead blocks from the original loop:", DeadLoopBlocks);
160  PrintOutSet("Live exit blocks:", LiveExitBlocks);
161  PrintOutVector("Dead exit blocks:", DeadExitBlocks);
162  if (!DeleteCurrentLoop)
163  PrintOutSet("The following blocks will still be part of the loop:",
164  BlocksInLoopAfterFolding);
165  }
166 
167  /// Whether or not the current loop has irreducible CFG.
168  bool hasIrreducibleCFG(LoopBlocksDFS &DFS) {
169  assert(DFS.isComplete() && "DFS is expected to be finished");
170  // Index of a basic block in RPO traversal.
172  unsigned Current = 0;
173  for (auto I = DFS.beginRPO(), E = DFS.endRPO(); I != E; ++I)
174  RPO[*I] = Current++;
175 
176  for (auto I = DFS.beginRPO(), E = DFS.endRPO(); I != E; ++I) {
177  BasicBlock *BB = *I;
178  for (auto *Succ : successors(BB))
179  if (L.contains(Succ) && !LI.isLoopHeader(Succ) && RPO[BB] > RPO[Succ])
180  // If an edge goes from a block with greater order number into a block
181  // with lesses number, and it is not a loop backedge, then it can only
182  // be a part of irreducible non-loop cycle.
183  return true;
184  }
185  return false;
186  }
187 
188  /// Fill all information about status of blocks and exits of the current loop
189  /// if constant folding of all branches will be done.
190  void analyze() {
191  DFS.perform(&LI);
192  assert(DFS.isComplete() && "DFS is expected to be finished");
193 
194  // TODO: The algorithm below relies on both RPO and Postorder traversals.
195  // When the loop has only reducible CFG inside, then the invariant "all
196  // predecessors of X are processed before X in RPO" is preserved. However
197  // an irreducible loop can break this invariant (e.g. latch does not have to
198  // be the last block in the traversal in this case, and the algorithm relies
199  // on this). We can later decide to support such cases by altering the
200  // algorithms, but so far we just give up analyzing them.
201  if (hasIrreducibleCFG(DFS)) {
202  HasIrreducibleCFG = true;
203  return;
204  }
205 
206  // Collect live and dead loop blocks and exits.
207  LiveLoopBlocks.insert(L.getHeader());
208  for (auto I = DFS.beginRPO(), E = DFS.endRPO(); I != E; ++I) {
209  BasicBlock *BB = *I;
210 
211  // If a loop block wasn't marked as live so far, then it's dead.
212  if (!LiveLoopBlocks.count(BB)) {
213  DeadLoopBlocks.push_back(BB);
214  continue;
215  }
216 
217  BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(BB);
218 
219  // If a block has only one live successor, it's a candidate on constant
220  // folding. Only handle blocks from current loop: branches in child loops
221  // are skipped because if they can be folded, they should be folded during
222  // the processing of child loops.
223  bool TakeFoldCandidate = TheOnlySucc && LI.getLoopFor(BB) == &L;
224  if (TakeFoldCandidate)
225  FoldCandidates.push_back(BB);
226 
227  // Handle successors.
228  for (BasicBlock *Succ : successors(BB))
229  if (!TakeFoldCandidate || TheOnlySucc == Succ) {
230  if (L.contains(Succ))
231  LiveLoopBlocks.insert(Succ);
232  else
233  LiveExitBlocks.insert(Succ);
234  }
235  }
236 
237  // Sanity check: amount of dead and live loop blocks should match the total
238  // number of blocks in loop.
239  assert(L.getNumBlocks() == LiveLoopBlocks.size() + DeadLoopBlocks.size() &&
240  "Malformed block sets?");
241 
242  // Now, all exit blocks that are not marked as live are dead.
243  SmallVector<BasicBlock *, 8> ExitBlocks;
244  L.getExitBlocks(ExitBlocks);
245  SmallPtrSet<BasicBlock *, 8> UniqueDeadExits;
246  for (auto *ExitBlock : ExitBlocks)
247  if (!LiveExitBlocks.count(ExitBlock) &&
248  UniqueDeadExits.insert(ExitBlock).second)
249  DeadExitBlocks.push_back(ExitBlock);
250 
251  // Whether or not the edge From->To will still be present in graph after the
252  // folding.
253  auto IsEdgeLive = [&](BasicBlock *From, BasicBlock *To) {
254  if (!LiveLoopBlocks.count(From))
255  return false;
256  BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(From);
257  return !TheOnlySucc || TheOnlySucc == To || LI.getLoopFor(From) != &L;
258  };
259 
260  // The loop will not be destroyed if its latch is live.
261  DeleteCurrentLoop = !IsEdgeLive(L.getLoopLatch(), L.getHeader());
262 
263  // If we are going to delete the current loop completely, no extra analysis
264  // is needed.
265  if (DeleteCurrentLoop)
266  return;
267 
268  // Otherwise, we should check which blocks will still be a part of the
269  // current loop after the transform.
270  BlocksInLoopAfterFolding.insert(L.getLoopLatch());
271  // If the loop is live, then we should compute what blocks are still in
272  // loop after all branch folding has been done. A block is in loop if
273  // it has a live edge to another block that is in the loop; by definition,
274  // latch is in the loop.
275  auto BlockIsInLoop = [&](BasicBlock *BB) {
276  return any_of(successors(BB), [&](BasicBlock *Succ) {
277  return BlocksInLoopAfterFolding.count(Succ) && IsEdgeLive(BB, Succ);
278  });
279  };
280  for (auto I = DFS.beginPostorder(), E = DFS.endPostorder(); I != E; ++I) {
281  BasicBlock *BB = *I;
282  if (BlockIsInLoop(BB))
283  BlocksInLoopAfterFolding.insert(BB);
284  }
285 
286  // Sanity check: header must be in loop.
287  assert(BlocksInLoopAfterFolding.count(L.getHeader()) &&
288  "Header not in loop?");
289  assert(BlocksInLoopAfterFolding.size() <= LiveLoopBlocks.size() &&
290  "All blocks that stay in loop should be live!");
291  }
292 
293  /// We need to preserve static reachibility of all loop exit blocks (this is)
294  /// required by loop pass manager. In order to do it, we make the following
295  /// trick:
296  ///
297  /// preheader:
298  /// <preheader code>
299  /// br label %loop_header
300  ///
301  /// loop_header:
302  /// ...
303  /// br i1 false, label %dead_exit, label %loop_block
304  /// ...
305  ///
306  /// We cannot simply remove edge from the loop to dead exit because in this
307  /// case dead_exit (and its successors) may become unreachable. To avoid that,
308  /// we insert the following fictive preheader:
309  ///
310  /// preheader:
311  /// <preheader code>
312  /// switch i32 0, label %preheader-split,
313  /// [i32 1, label %dead_exit_1],
314  /// [i32 2, label %dead_exit_2],
315  /// ...
316  /// [i32 N, label %dead_exit_N],
317  ///
318  /// preheader-split:
319  /// br label %loop_header
320  ///
321  /// loop_header:
322  /// ...
323  /// br i1 false, label %dead_exit_N, label %loop_block
324  /// ...
325  ///
326  /// Doing so, we preserve static reachibility of all dead exits and can later
327  /// remove edges from the loop to these blocks.
328  void handleDeadExits() {
329  // If no dead exits, nothing to do.
330  if (DeadExitBlocks.empty())
331  return;
332 
333  // Construct split preheader and the dummy switch to thread edges from it to
334  // dead exits.
335  BasicBlock *Preheader = L.getLoopPreheader();
336  BasicBlock *NewPreheader = Preheader->splitBasicBlock(
337  Preheader->getTerminator(),
338  Twine(Preheader->getName()).concat("-split"));
339  DTUpdates.push_back({DominatorTree::Delete, Preheader, L.getHeader()});
340  DTUpdates.push_back({DominatorTree::Insert, NewPreheader, L.getHeader()});
341  DTUpdates.push_back({DominatorTree::Insert, Preheader, NewPreheader});
342  IRBuilder<> Builder(Preheader->getTerminator());
343  SwitchInst *DummySwitch =
344  Builder.CreateSwitch(Builder.getInt32(0), NewPreheader);
345  Preheader->getTerminator()->eraseFromParent();
346 
347  unsigned DummyIdx = 1;
348  for (BasicBlock *BB : DeadExitBlocks) {
350  for (auto &PN : BB->phis())
351  DeadPhis.push_back(&PN);
352 
353  // Eliminate all Phis from dead exits.
354  for (Instruction *PN : DeadPhis) {
355  PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
356  PN->eraseFromParent();
357  }
358  assert(DummyIdx != 0 && "Too many dead exits!");
359  DummySwitch->addCase(Builder.getInt32(DummyIdx++), BB);
360  DTUpdates.push_back({DominatorTree::Insert, Preheader, BB});
361  ++NumLoopExitsDeleted;
362  }
363 
364  assert(L.getLoopPreheader() == NewPreheader && "Malformed CFG?");
365  if (Loop *OuterLoop = LI.getLoopFor(Preheader)) {
366  OuterLoop->addBasicBlockToLoop(NewPreheader, LI);
367 
368  // When we break dead edges, the outer loop may become unreachable from
369  // the current loop. We need to fix loop info accordingly. For this, we
370  // find the most nested loop that still contains L and remove L from all
371  // loops that are inside of it.
372  Loop *StillReachable = nullptr;
373  for (BasicBlock *BB : LiveExitBlocks) {
374  Loop *BBL = LI.getLoopFor(BB);
375  if (BBL && BBL->contains(L.getHeader()))
376  if (!StillReachable ||
377  BBL->getLoopDepth() > StillReachable->getLoopDepth())
378  StillReachable = BBL;
379  }
380 
381  // Okay, our loop is no longer in the outer loop (and maybe not in some of
382  // its parents as well). Make the fixup.
383  if (StillReachable != OuterLoop) {
384  LI.changeLoopFor(NewPreheader, StillReachable);
385  removeBlockFromLoops(NewPreheader, OuterLoop, StillReachable);
386  for (auto *BB : L.blocks())
387  removeBlockFromLoops(BB, OuterLoop, StillReachable);
388  OuterLoop->removeChildLoop(&L);
389  if (StillReachable)
390  StillReachable->addChildLoop(&L);
391  else
392  LI.addTopLevelLoop(&L);
393 
394  // Some values from loops in [OuterLoop, StillReachable) could be used
395  // in the current loop. Now it is not their child anymore, so such uses
396  // require LCSSA Phis.
397  Loop *FixLCSSALoop = OuterLoop;
398  while (FixLCSSALoop->getParentLoop() != StillReachable)
399  FixLCSSALoop = FixLCSSALoop->getParentLoop();
400  assert(FixLCSSALoop && "Should be a loop!");
401  // We need all DT updates to be done before forming LCSSA.
402  DTU.applyUpdates(DTUpdates);
403  DTUpdates.clear();
404  formLCSSARecursively(*FixLCSSALoop, DT, &LI, &SE);
405  }
406  }
407  }
408 
409  /// Delete loop blocks that have become unreachable after folding. Make all
410  /// relevant updates to DT and LI.
411  void deleteDeadLoopBlocks() {
412  if (MSSAU) {
413  SmallPtrSet<BasicBlock *, 8> DeadLoopBlocksSet(DeadLoopBlocks.begin(),
414  DeadLoopBlocks.end());
415  MSSAU->removeBlocks(DeadLoopBlocksSet);
416  }
417 
418  // The function LI.erase has some invariants that need to be preserved when
419  // it tries to remove a loop which is not the top-level loop. In particular,
420  // it requires loop's preheader to be strictly in loop's parent. We cannot
421  // just remove blocks one by one, because after removal of preheader we may
422  // break this invariant for the dead loop. So we detatch and erase all dead
423  // loops beforehand.
424  for (auto *BB : DeadLoopBlocks)
425  if (LI.isLoopHeader(BB)) {
426  assert(LI.getLoopFor(BB) != &L && "Attempt to remove current loop!");
427  Loop *DL = LI.getLoopFor(BB);
428  if (DL->getParentLoop()) {
429  for (auto *PL = DL->getParentLoop(); PL; PL = PL->getParentLoop())
430  for (auto *BB : DL->getBlocks())
431  PL->removeBlockFromLoop(BB);
432  DL->getParentLoop()->removeChildLoop(DL);
433  LI.addTopLevelLoop(DL);
434  }
435  LI.erase(DL);
436  }
437 
438  for (auto *BB : DeadLoopBlocks) {
439  assert(BB != L.getHeader() &&
440  "Header of the current loop cannot be dead!");
441  LLVM_DEBUG(dbgs() << "Deleting dead loop block " << BB->getName()
442  << "\n");
443  LI.removeBlock(BB);
444  }
445 
446  DetatchDeadBlocks(DeadLoopBlocks, &DTUpdates, /*KeepOneInputPHIs*/true);
447  DTU.applyUpdates(DTUpdates);
448  DTUpdates.clear();
449  for (auto *BB : DeadLoopBlocks)
450  DTU.deleteBB(BB);
451 
452  NumLoopBlocksDeleted += DeadLoopBlocks.size();
453  }
454 
455  /// Constant-fold terminators of blocks acculumated in FoldCandidates into the
456  /// unconditional branches.
457  void foldTerminators() {
458  for (BasicBlock *BB : FoldCandidates) {
459  assert(LI.getLoopFor(BB) == &L && "Should be a loop block!");
460  BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(BB);
461  assert(TheOnlySucc && "Should have one live successor!");
462 
463  LLVM_DEBUG(dbgs() << "Replacing terminator of " << BB->getName()
464  << " with an unconditional branch to the block "
465  << TheOnlySucc->getName() << "\n");
466 
467  SmallPtrSet<BasicBlock *, 2> DeadSuccessors;
468  // Remove all BB's successors except for the live one.
469  unsigned TheOnlySuccDuplicates = 0;
470  for (auto *Succ : successors(BB))
471  if (Succ != TheOnlySucc) {
472  DeadSuccessors.insert(Succ);
473  // If our successor lies in a different loop, we don't want to remove
474  // the one-input Phi because it is a LCSSA Phi.
475  bool PreserveLCSSAPhi = !L.contains(Succ);
476  Succ->removePredecessor(BB, PreserveLCSSAPhi);
477  if (MSSAU)
478  MSSAU->removeEdge(BB, Succ);
479  } else
480  ++TheOnlySuccDuplicates;
481 
482  assert(TheOnlySuccDuplicates > 0 && "Should be!");
483  // If TheOnlySucc was BB's successor more than once, after transform it
484  // will be its successor only once. Remove redundant inputs from
485  // TheOnlySucc's Phis.
486  bool PreserveLCSSAPhi = !L.contains(TheOnlySucc);
487  for (unsigned Dup = 1; Dup < TheOnlySuccDuplicates; ++Dup)
488  TheOnlySucc->removePredecessor(BB, PreserveLCSSAPhi);
489  if (MSSAU && TheOnlySuccDuplicates > 1)
490  MSSAU->removeDuplicatePhiEdgesBetween(BB, TheOnlySucc);
491 
492  IRBuilder<> Builder(BB->getContext());
493  Instruction *Term = BB->getTerminator();
494  Builder.SetInsertPoint(Term);
495  Builder.CreateBr(TheOnlySucc);
496  Term->eraseFromParent();
497 
498  for (auto *DeadSucc : DeadSuccessors)
499  DTUpdates.push_back({DominatorTree::Delete, BB, DeadSucc});
500 
501  ++NumTerminatorsFolded;
502  }
503  }
504 
505 public:
506  ConstantTerminatorFoldingImpl(Loop &L, LoopInfo &LI, DominatorTree &DT,
507  ScalarEvolution &SE,
508  MemorySSAUpdater *MSSAU)
509  : L(L), LI(LI), DT(DT), SE(SE), MSSAU(MSSAU), DFS(&L),
511  bool run() {
512  assert(L.getLoopLatch() && "Should be single latch!");
513 
514  // Collect all available information about status of blocks after constant
515  // folding.
516  analyze();
517 
518  LLVM_DEBUG(dbgs() << "In function " << L.getHeader()->getParent()->getName()
519  << ": ");
520 
521  if (HasIrreducibleCFG) {
522  LLVM_DEBUG(dbgs() << "Loops with irreducible CFG are not supported!\n");
523  return false;
524  }
525 
526  // Nothing to constant-fold.
527  if (FoldCandidates.empty()) {
528  LLVM_DEBUG(
529  dbgs() << "No constant terminator folding candidates found in loop "
530  << L.getHeader()->getName() << "\n");
531  return false;
532  }
533 
534  // TODO: Support deletion of the current loop.
535  if (DeleteCurrentLoop) {
536  LLVM_DEBUG(
537  dbgs()
538  << "Give up constant terminator folding in loop "
539  << L.getHeader()->getName()
540  << ": we don't currently support deletion of the current loop.\n");
541  return false;
542  }
543 
544  // TODO: Support blocks that are not dead, but also not in loop after the
545  // folding.
546  if (BlocksInLoopAfterFolding.size() + DeadLoopBlocks.size() !=
547  L.getNumBlocks()) {
548  LLVM_DEBUG(
549  dbgs() << "Give up constant terminator folding in loop "
550  << L.getHeader()->getName()
551  << ": we don't currently"
552  " support blocks that are not dead, but will stop "
553  "being a part of the loop after constant-folding.\n");
554  return false;
555  }
556 
557  SE.forgetTopmostLoop(&L);
558  // Dump analysis results.
559  LLVM_DEBUG(dump());
560 
561  LLVM_DEBUG(dbgs() << "Constant-folding " << FoldCandidates.size()
562  << " terminators in loop " << L.getHeader()->getName()
563  << "\n");
564 
565  // Make the actual transforms.
566  handleDeadExits();
567  foldTerminators();
568 
569  if (!DeadLoopBlocks.empty()) {
570  LLVM_DEBUG(dbgs() << "Deleting " << DeadLoopBlocks.size()
571  << " dead blocks in loop " << L.getHeader()->getName()
572  << "\n");
573  deleteDeadLoopBlocks();
574  } else {
575  // If we didn't do updates inside deleteDeadLoopBlocks, do them here.
576  DTU.applyUpdates(DTUpdates);
577  DTUpdates.clear();
578  }
579 
580 #ifndef NDEBUG
581  // Make sure that we have preserved all data structures after the transform.
582  assert(DT.verify() && "DT broken after transform!");
584  LI.verify(DT);
585 #endif
586 
587  return true;
588  }
589 };
590 } // namespace
591 
592 /// Turn branches and switches with known constant conditions into unconditional
593 /// branches.
595  ScalarEvolution &SE,
596  MemorySSAUpdater *MSSAU) {
597  if (!EnableTermFolding)
598  return false;
599 
600  // To keep things simple, only process loops with single latch. We
601  // canonicalize most loops to this form. We can support multi-latch if needed.
602  if (!L.getLoopLatch())
603  return false;
604 
605  ConstantTerminatorFoldingImpl BranchFolder(L, LI, DT, SE, MSSAU);
606  return BranchFolder.run();
607 }
608 
610  LoopInfo &LI, MemorySSAUpdater *MSSAU) {
611  bool Changed = false;
613  // Copy blocks into a temporary array to avoid iterator invalidation issues
614  // as we remove them.
616 
617  for (auto &Block : Blocks) {
618  // Attempt to merge blocks in the trivial case. Don't modify blocks which
619  // belong to other loops.
620  BasicBlock *Succ = cast_or_null<BasicBlock>(Block);
621  if (!Succ)
622  continue;
623 
624  BasicBlock *Pred = Succ->getSinglePredecessor();
625  if (!Pred || !Pred->getSingleSuccessor() || LI.getLoopFor(Pred) != &L)
626  continue;
627 
628  // Merge Succ into Pred and delete it.
629  MergeBlockIntoPredecessor(Succ, &DTU, &LI, MSSAU);
630 
631  Changed = true;
632  }
633 
634  return Changed;
635 }
636 
637 static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI,
638  ScalarEvolution &SE, MemorySSAUpdater *MSSAU) {
639  bool Changed = false;
640 
641  // Constant-fold terminators with known constant conditions.
642  Changed |= constantFoldTerminators(L, DT, LI, SE, MSSAU);
643 
644  // Eliminate unconditional branches by merging blocks into their predecessors.
645  Changed |= mergeBlocksIntoPredecessors(L, DT, LI, MSSAU);
646 
647  if (Changed)
648  SE.forgetTopmostLoop(&L);
649 
650  return Changed;
651 }
652 
655  LPMUpdater &) {
657  if (EnableMSSALoopDependency && AR.MSSA)
658  MSSAU = MemorySSAUpdater(AR.MSSA);
659  if (!simplifyLoopCFG(L, AR.DT, AR.LI, AR.SE,
660  MSSAU.hasValue() ? MSSAU.getPointer() : nullptr))
661  return PreservedAnalyses::all();
662 
664 }
665 
666 namespace {
667 class LoopSimplifyCFGLegacyPass : public LoopPass {
668 public:
669  static char ID; // Pass ID, replacement for typeid
670  LoopSimplifyCFGLegacyPass() : LoopPass(ID) {
672  }
673 
674  bool runOnLoop(Loop *L, LPPassManager &) override {
675  if (skipLoop(L))
676  return false;
677 
678  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
679  LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
680  ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
683  MemorySSA *MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
684  MSSAU = MemorySSAUpdater(MSSA);
685  if (VerifyMemorySSA)
686  MSSA->verifyMemorySSA();
687  }
688  return simplifyLoopCFG(*L, DT, LI, SE,
689  MSSAU.hasValue() ? MSSAU.getPointer() : nullptr);
690  }
691 
692  void getAnalysisUsage(AnalysisUsage &AU) const override {
696  }
699  }
700 };
701 }
702 
704 INITIALIZE_PASS_BEGIN(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
705  "Simplify loop CFG", false, false)
708 INITIALIZE_PASS_END(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
709  "Simplify loop CFG", false, false)
710 
712  return new LoopSimplifyCFGLegacyPass();
713 }
detail::concat_range< ValueT, RangeTs... > concat(RangeTs &&... Ranges)
Concatenated range across two or more ranges.
Definition: STLExtras.h:946
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI, ScalarEvolution &SE, MemorySSAUpdater *MSSAU)
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:67
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 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:951
This is the interface for a SCEV-based alias analysis.
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
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:80
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:689
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:700
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:588
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:740
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:268
static bool constantFoldTerminators(Loop &L, DominatorTree &DT, LoopInfo &LI, ScalarEvolution &SE, MemorySSAUpdater *MSSAU)
Turn branches and switches with known constant conditions into unconditional branches.
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopInfo.cpp:834
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:422
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:154
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:1414
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
size_t size() const
Definition: SmallVector.h:52
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
void verifyMemorySSA() const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
Definition: MemorySSA.cpp:1775
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates, bool ForceRemoveDuplicates=false)
Apply updates on all available trees.
Pass * createLoopSimplifyCFGPass()
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:702
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:166
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:134
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:322
void changeLoopFor(BlockT *BB, LoopT *L)
Change the top-level loop that contains BB to the specified loop.
Definition: LoopInfo.h:721
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="")
Split the basic block into two basic blocks at the specified instruction.
Definition: BasicBlock.cpp:407
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
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:748
void forgetTopmostLoop(const Loop *L)
cl::opt< bool > EnableMSSALoopDependency
Enables memory ssa as a dependency for loop passes.