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
16 #include "llvm/Transforms/Scalar/LoopSimplifyCFG.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/ADT/Statistic.h"
19 #include "llvm/Analysis/AliasAnalysis.h"
20 #include "llvm/Analysis/AssumptionCache.h"
21 #include "llvm/Analysis/BasicAliasAnalysis.h"
22 #include "llvm/Analysis/DependenceAnalysis.h"
23 #include "llvm/Analysis/DomTreeUpdater.h"
24 #include "llvm/Analysis/GlobalsModRef.h"
25 #include "llvm/Analysis/LoopInfo.h"
26 #include "llvm/Analysis/LoopIterator.h"
27 #include "llvm/Analysis/LoopPass.h"
28 #include "llvm/Analysis/MemorySSA.h"
29 #include "llvm/Analysis/MemorySSAUpdater.h"
30 #include "llvm/Analysis/ScalarEvolution.h"
31 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
32 #include "llvm/Analysis/TargetTransformInfo.h"
33 #include "llvm/IR/Dominators.h"
34 #include "llvm/IR/IRBuilder.h"
35 #include "llvm/InitializePasses.h"
36 #include "llvm/Support/CommandLine.h"
37 #include "llvm/Transforms/Scalar.h"
38 #include "llvm/Transforms/Scalar/LoopPassManager.h"
39 #include "llvm/Transforms/Utils.h"
40 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
41 #include "llvm/Transforms/Utils/Local.h"
42 #include "llvm/Transforms/Utils/LoopUtils.h"
43 using namespace llvm;
44
45 #define DEBUG_TYPE "loop-simplifycfg"
46
47 static cl::opt<bool> EnableTermFolding("enable-loop-simplifycfg-term-folding",
48 cl::init(true));
49
50 STATISTIC(NumTerminatorsFolded,
51 "Number of terminators folded to unconditional branches");
52 STATISTIC(NumLoopBlocksDeleted,
53 "Number of loop blocks deleted");
54 STATISTIC(NumLoopExitsDeleted,
55 "Number of loop exiting edges deleted");
56
57 /// If \p BB is a switch or a conditional branch, but only one of its successors
58 /// can be reached from this block in runtime, return this successor. Otherwise,
59 /// return nullptr.
getOnlyLiveSuccessor(BasicBlock * BB)60 static BasicBlock *getOnlyLiveSuccessor(BasicBlock *BB) {
61 Instruction *TI = BB->getTerminator();
62 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
63 if (BI->isUnconditional())
64 return nullptr;
65 if (BI->getSuccessor(0) == BI->getSuccessor(1))
66 return BI->getSuccessor(0);
67 ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
68 if (!Cond)
69 return nullptr;
70 return Cond->isZero() ? BI->getSuccessor(1) : BI->getSuccessor(0);
71 }
72
73 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
74 auto *CI = dyn_cast<ConstantInt>(SI->getCondition());
75 if (!CI)
76 return nullptr;
77 for (auto Case : SI->cases())
78 if (Case.getCaseValue() == CI)
79 return Case.getCaseSuccessor();
80 return SI->getDefaultDest();
81 }
82
83 return nullptr;
84 }
85
86 /// Removes \p BB from all loops from [FirstLoop, LastLoop) in parent chain.
removeBlockFromLoops(BasicBlock * BB,Loop * FirstLoop,Loop * LastLoop=nullptr)87 static void removeBlockFromLoops(BasicBlock *BB, Loop *FirstLoop,
88 Loop *LastLoop = nullptr) {
89 assert((!LastLoop || LastLoop->contains(FirstLoop->getHeader())) &&
90 "First loop is supposed to be inside of last loop!");
91 assert(FirstLoop->contains(BB) && "Must be a loop block!");
92 for (Loop *Current = FirstLoop; Current != LastLoop;
93 Current = Current->getParentLoop())
94 Current->removeBlockFromLoop(BB);
95 }
96
97 /// Find innermost loop that contains at least one block from \p BBs and
98 /// contains the header of loop \p L.
getInnermostLoopFor(SmallPtrSetImpl<BasicBlock * > & BBs,Loop & L,LoopInfo & LI)99 static Loop *getInnermostLoopFor(SmallPtrSetImpl<BasicBlock *> &BBs,
100 Loop &L, LoopInfo &LI) {
101 Loop *Innermost = nullptr;
102 for (BasicBlock *BB : BBs) {
103 Loop *BBL = LI.getLoopFor(BB);
104 while (BBL && !BBL->contains(L.getHeader()))
105 BBL = BBL->getParentLoop();
106 if (BBL == &L)
107 BBL = BBL->getParentLoop();
108 if (!BBL)
109 continue;
110 if (!Innermost || BBL->getLoopDepth() > Innermost->getLoopDepth())
111 Innermost = BBL;
112 }
113 return Innermost;
114 }
115
116 namespace {
117 /// Helper class that can turn branches and switches with constant conditions
118 /// into unconditional branches.
119 class ConstantTerminatorFoldingImpl {
120 private:
121 Loop &L;
122 LoopInfo &LI;
123 DominatorTree &DT;
124 ScalarEvolution &SE;
125 MemorySSAUpdater *MSSAU;
126 LoopBlocksDFS DFS;
127 DomTreeUpdater DTU;
128 SmallVector<DominatorTree::UpdateType, 16> DTUpdates;
129
130 // Whether or not the current loop has irreducible CFG.
131 bool HasIrreducibleCFG = false;
132 // Whether or not the current loop will still exist after terminator constant
133 // folding will be done. In theory, there are two ways how it can happen:
134 // 1. Loop's latch(es) become unreachable from loop header;
135 // 2. Loop's header becomes unreachable from method entry.
136 // In practice, the second situation is impossible because we only modify the
137 // current loop and its preheader and do not affect preheader's reachibility
138 // from any other block. So this variable set to true means that loop's latch
139 // has become unreachable from loop header.
140 bool DeleteCurrentLoop = false;
141
142 // The blocks of the original loop that will still be reachable from entry
143 // after the constant folding.
144 SmallPtrSet<BasicBlock *, 8> LiveLoopBlocks;
145 // The blocks of the original loop that will become unreachable from entry
146 // after the constant folding.
147 SmallVector<BasicBlock *, 8> DeadLoopBlocks;
148 // The exits of the original loop that will still be reachable from entry
149 // after the constant folding.
150 SmallPtrSet<BasicBlock *, 8> LiveExitBlocks;
151 // The exits of the original loop that will become unreachable from entry
152 // after the constant folding.
153 SmallVector<BasicBlock *, 8> DeadExitBlocks;
154 // The blocks that will still be a part of the current loop after folding.
155 SmallPtrSet<BasicBlock *, 8> BlocksInLoopAfterFolding;
156 // The blocks that have terminators with constant condition that can be
157 // folded. Note: fold candidates should be in L but not in any of its
158 // subloops to avoid complex LI updates.
159 SmallVector<BasicBlock *, 8> FoldCandidates;
160
dump() const161 void dump() const {
162 dbgs() << "Constant terminator folding for loop " << L << "\n";
163 dbgs() << "After terminator constant-folding, the loop will";
164 if (!DeleteCurrentLoop)
165 dbgs() << " not";
166 dbgs() << " be destroyed\n";
167 auto PrintOutVector = [&](const char *Message,
168 const SmallVectorImpl<BasicBlock *> &S) {
169 dbgs() << Message << "\n";
170 for (const BasicBlock *BB : S)
171 dbgs() << "\t" << BB->getName() << "\n";
172 };
173 auto PrintOutSet = [&](const char *Message,
174 const SmallPtrSetImpl<BasicBlock *> &S) {
175 dbgs() << Message << "\n";
176 for (const BasicBlock *BB : S)
177 dbgs() << "\t" << BB->getName() << "\n";
178 };
179 PrintOutVector("Blocks in which we can constant-fold terminator:",
180 FoldCandidates);
181 PrintOutSet("Live blocks from the original loop:", LiveLoopBlocks);
182 PrintOutVector("Dead blocks from the original loop:", DeadLoopBlocks);
183 PrintOutSet("Live exit blocks:", LiveExitBlocks);
184 PrintOutVector("Dead exit blocks:", DeadExitBlocks);
185 if (!DeleteCurrentLoop)
186 PrintOutSet("The following blocks will still be part of the loop:",
187 BlocksInLoopAfterFolding);
188 }
189
190 /// Whether or not the current loop has irreducible CFG.
hasIrreducibleCFG(LoopBlocksDFS & DFS)191 bool hasIrreducibleCFG(LoopBlocksDFS &DFS) {
192 assert(DFS.isComplete() && "DFS is expected to be finished");
193 // Index of a basic block in RPO traversal.
194 DenseMap<const BasicBlock *, unsigned> RPO;
195 unsigned Current = 0;
196 for (auto I = DFS.beginRPO(), E = DFS.endRPO(); I != E; ++I)
197 RPO[*I] = Current++;
198
199 for (auto I = DFS.beginRPO(), E = DFS.endRPO(); I != E; ++I) {
200 BasicBlock *BB = *I;
201 for (auto *Succ : successors(BB))
202 if (L.contains(Succ) && !LI.isLoopHeader(Succ) && RPO[BB] > RPO[Succ])
203 // If an edge goes from a block with greater order number into a block
204 // with lesses number, and it is not a loop backedge, then it can only
205 // be a part of irreducible non-loop cycle.
206 return true;
207 }
208 return false;
209 }
210
211 /// Fill all information about status of blocks and exits of the current loop
212 /// if constant folding of all branches will be done.
analyze()213 void analyze() {
214 DFS.perform(&LI);
215 assert(DFS.isComplete() && "DFS is expected to be finished");
216
217 // TODO: The algorithm below relies on both RPO and Postorder traversals.
218 // When the loop has only reducible CFG inside, then the invariant "all
219 // predecessors of X are processed before X in RPO" is preserved. However
220 // an irreducible loop can break this invariant (e.g. latch does not have to
221 // be the last block in the traversal in this case, and the algorithm relies
222 // on this). We can later decide to support such cases by altering the
223 // algorithms, but so far we just give up analyzing them.
224 if (hasIrreducibleCFG(DFS)) {
225 HasIrreducibleCFG = true;
226 return;
227 }
228
229 // Collect live and dead loop blocks and exits.
230 LiveLoopBlocks.insert(L.getHeader());
231 for (auto I = DFS.beginRPO(), E = DFS.endRPO(); I != E; ++I) {
232 BasicBlock *BB = *I;
233
234 // If a loop block wasn't marked as live so far, then it's dead.
235 if (!LiveLoopBlocks.count(BB)) {
236 DeadLoopBlocks.push_back(BB);
237 continue;
238 }
239
240 BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(BB);
241
242 // If a block has only one live successor, it's a candidate on constant
243 // folding. Only handle blocks from current loop: branches in child loops
244 // are skipped because if they can be folded, they should be folded during
245 // the processing of child loops.
246 bool TakeFoldCandidate = TheOnlySucc && LI.getLoopFor(BB) == &L;
247 if (TakeFoldCandidate)
248 FoldCandidates.push_back(BB);
249
250 // Handle successors.
251 for (BasicBlock *Succ : successors(BB))
252 if (!TakeFoldCandidate || TheOnlySucc == Succ) {
253 if (L.contains(Succ))
254 LiveLoopBlocks.insert(Succ);
255 else
256 LiveExitBlocks.insert(Succ);
257 }
258 }
259
260 // Sanity check: amount of dead and live loop blocks should match the total
261 // number of blocks in loop.
262 assert(L.getNumBlocks() == LiveLoopBlocks.size() + DeadLoopBlocks.size() &&
263 "Malformed block sets?");
264
265 // Now, all exit blocks that are not marked as live are dead.
266 SmallVector<BasicBlock *, 8> ExitBlocks;
267 L.getExitBlocks(ExitBlocks);
268 SmallPtrSet<BasicBlock *, 8> UniqueDeadExits;
269 for (auto *ExitBlock : ExitBlocks)
270 if (!LiveExitBlocks.count(ExitBlock) &&
271 UniqueDeadExits.insert(ExitBlock).second)
272 DeadExitBlocks.push_back(ExitBlock);
273
274 // Whether or not the edge From->To will still be present in graph after the
275 // folding.
276 auto IsEdgeLive = [&](BasicBlock *From, BasicBlock *To) {
277 if (!LiveLoopBlocks.count(From))
278 return false;
279 BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(From);
280 return !TheOnlySucc || TheOnlySucc == To || LI.getLoopFor(From) != &L;
281 };
282
283 // The loop will not be destroyed if its latch is live.
284 DeleteCurrentLoop = !IsEdgeLive(L.getLoopLatch(), L.getHeader());
285
286 // If we are going to delete the current loop completely, no extra analysis
287 // is needed.
288 if (DeleteCurrentLoop)
289 return;
290
291 // Otherwise, we should check which blocks will still be a part of the
292 // current loop after the transform.
293 BlocksInLoopAfterFolding.insert(L.getLoopLatch());
294 // If the loop is live, then we should compute what blocks are still in
295 // loop after all branch folding has been done. A block is in loop if
296 // it has a live edge to another block that is in the loop; by definition,
297 // latch is in the loop.
298 auto BlockIsInLoop = [&](BasicBlock *BB) {
299 return any_of(successors(BB), [&](BasicBlock *Succ) {
300 return BlocksInLoopAfterFolding.count(Succ) && IsEdgeLive(BB, Succ);
301 });
302 };
303 for (auto I = DFS.beginPostorder(), E = DFS.endPostorder(); I != E; ++I) {
304 BasicBlock *BB = *I;
305 if (BlockIsInLoop(BB))
306 BlocksInLoopAfterFolding.insert(BB);
307 }
308
309 // Sanity check: header must be in loop.
310 assert(BlocksInLoopAfterFolding.count(L.getHeader()) &&
311 "Header not in loop?");
312 assert(BlocksInLoopAfterFolding.size() <= LiveLoopBlocks.size() &&
313 "All blocks that stay in loop should be live!");
314 }
315
316 /// We need to preserve static reachibility of all loop exit blocks (this is)
317 /// required by loop pass manager. In order to do it, we make the following
318 /// trick:
319 ///
320 /// preheader:
321 /// <preheader code>
322 /// br label %loop_header
323 ///
324 /// loop_header:
325 /// ...
326 /// br i1 false, label %dead_exit, label %loop_block
327 /// ...
328 ///
329 /// We cannot simply remove edge from the loop to dead exit because in this
330 /// case dead_exit (and its successors) may become unreachable. To avoid that,
331 /// we insert the following fictive preheader:
332 ///
333 /// preheader:
334 /// <preheader code>
335 /// switch i32 0, label %preheader-split,
336 /// [i32 1, label %dead_exit_1],
337 /// [i32 2, label %dead_exit_2],
338 /// ...
339 /// [i32 N, label %dead_exit_N],
340 ///
341 /// preheader-split:
342 /// br label %loop_header
343 ///
344 /// loop_header:
345 /// ...
346 /// br i1 false, label %dead_exit_N, label %loop_block
347 /// ...
348 ///
349 /// Doing so, we preserve static reachibility of all dead exits and can later
350 /// remove edges from the loop to these blocks.
handleDeadExits()351 void handleDeadExits() {
352 // If no dead exits, nothing to do.
353 if (DeadExitBlocks.empty())
354 return;
355
356 // Construct split preheader and the dummy switch to thread edges from it to
357 // dead exits.
358 BasicBlock *Preheader = L.getLoopPreheader();
359 BasicBlock *NewPreheader = llvm::SplitBlock(
360 Preheader, Preheader->getTerminator(), &DT, &LI, MSSAU);
361
362 IRBuilder<> Builder(Preheader->getTerminator());
363 SwitchInst *DummySwitch =
364 Builder.CreateSwitch(Builder.getInt32(0), NewPreheader);
365 Preheader->getTerminator()->eraseFromParent();
366
367 unsigned DummyIdx = 1;
368 for (BasicBlock *BB : DeadExitBlocks) {
369 SmallVector<Instruction *, 4> DeadPhis;
370 for (auto &PN : BB->phis())
371 DeadPhis.push_back(&PN);
372
373 // Eliminate all Phis from dead exits.
374 for (Instruction *PN : DeadPhis) {
375 PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
376 PN->eraseFromParent();
377 }
378 assert(DummyIdx != 0 && "Too many dead exits!");
379 DummySwitch->addCase(Builder.getInt32(DummyIdx++), BB);
380 DTUpdates.push_back({DominatorTree::Insert, Preheader, BB});
381 ++NumLoopExitsDeleted;
382 }
383
384 assert(L.getLoopPreheader() == NewPreheader && "Malformed CFG?");
385 if (Loop *OuterLoop = LI.getLoopFor(Preheader)) {
386 // When we break dead edges, the outer loop may become unreachable from
387 // the current loop. We need to fix loop info accordingly. For this, we
388 // find the most nested loop that still contains L and remove L from all
389 // loops that are inside of it.
390 Loop *StillReachable = getInnermostLoopFor(LiveExitBlocks, L, LI);
391
392 // Okay, our loop is no longer in the outer loop (and maybe not in some of
393 // its parents as well). Make the fixup.
394 if (StillReachable != OuterLoop) {
395 LI.changeLoopFor(NewPreheader, StillReachable);
396 removeBlockFromLoops(NewPreheader, OuterLoop, StillReachable);
397 for (auto *BB : L.blocks())
398 removeBlockFromLoops(BB, OuterLoop, StillReachable);
399 OuterLoop->removeChildLoop(&L);
400 if (StillReachable)
401 StillReachable->addChildLoop(&L);
402 else
403 LI.addTopLevelLoop(&L);
404
405 // Some values from loops in [OuterLoop, StillReachable) could be used
406 // in the current loop. Now it is not their child anymore, so such uses
407 // require LCSSA Phis.
408 Loop *FixLCSSALoop = OuterLoop;
409 while (FixLCSSALoop->getParentLoop() != StillReachable)
410 FixLCSSALoop = FixLCSSALoop->getParentLoop();
411 assert(FixLCSSALoop && "Should be a loop!");
412 // We need all DT updates to be done before forming LCSSA.
413 DTU.applyUpdates(DTUpdates);
414 if (MSSAU)
415 MSSAU->applyUpdates(DTUpdates, DT);
416 DTUpdates.clear();
417 formLCSSARecursively(*FixLCSSALoop, DT, &LI, &SE);
418 }
419 }
420
421 if (MSSAU) {
422 // Clear all updates now. Facilitates deletes that follow.
423 DTU.applyUpdates(DTUpdates);
424 MSSAU->applyUpdates(DTUpdates, DT);
425 DTUpdates.clear();
426 if (VerifyMemorySSA)
427 MSSAU->getMemorySSA()->verifyMemorySSA();
428 }
429 }
430
431 /// Delete loop blocks that have become unreachable after folding. Make all
432 /// relevant updates to DT and LI.
deleteDeadLoopBlocks()433 void deleteDeadLoopBlocks() {
434 if (MSSAU) {
435 SmallSetVector<BasicBlock *, 8> DeadLoopBlocksSet(DeadLoopBlocks.begin(),
436 DeadLoopBlocks.end());
437 MSSAU->removeBlocks(DeadLoopBlocksSet);
438 }
439
440 // The function LI.erase has some invariants that need to be preserved when
441 // it tries to remove a loop which is not the top-level loop. In particular,
442 // it requires loop's preheader to be strictly in loop's parent. We cannot
443 // just remove blocks one by one, because after removal of preheader we may
444 // break this invariant for the dead loop. So we detatch and erase all dead
445 // loops beforehand.
446 for (auto *BB : DeadLoopBlocks)
447 if (LI.isLoopHeader(BB)) {
448 assert(LI.getLoopFor(BB) != &L && "Attempt to remove current loop!");
449 Loop *DL = LI.getLoopFor(BB);
450 if (DL->getParentLoop()) {
451 for (auto *PL = DL->getParentLoop(); PL; PL = PL->getParentLoop())
452 for (auto *BB : DL->getBlocks())
453 PL->removeBlockFromLoop(BB);
454 DL->getParentLoop()->removeChildLoop(DL);
455 LI.addTopLevelLoop(DL);
456 }
457 LI.erase(DL);
458 }
459
460 for (auto *BB : DeadLoopBlocks) {
461 assert(BB != L.getHeader() &&
462 "Header of the current loop cannot be dead!");
463 LLVM_DEBUG(dbgs() << "Deleting dead loop block " << BB->getName()
464 << "\n");
465 LI.removeBlock(BB);
466 }
467
468 DetatchDeadBlocks(DeadLoopBlocks, &DTUpdates, /*KeepOneInputPHIs*/true);
469 DTU.applyUpdates(DTUpdates);
470 DTUpdates.clear();
471 for (auto *BB : DeadLoopBlocks)
472 DTU.deleteBB(BB);
473
474 NumLoopBlocksDeleted += DeadLoopBlocks.size();
475 }
476
477 /// Constant-fold terminators of blocks acculumated in FoldCandidates into the
478 /// unconditional branches.
foldTerminators()479 void foldTerminators() {
480 for (BasicBlock *BB : FoldCandidates) {
481 assert(LI.getLoopFor(BB) == &L && "Should be a loop block!");
482 BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(BB);
483 assert(TheOnlySucc && "Should have one live successor!");
484
485 LLVM_DEBUG(dbgs() << "Replacing terminator of " << BB->getName()
486 << " with an unconditional branch to the block "
487 << TheOnlySucc->getName() << "\n");
488
489 SmallPtrSet<BasicBlock *, 2> DeadSuccessors;
490 // Remove all BB's successors except for the live one.
491 unsigned TheOnlySuccDuplicates = 0;
492 for (auto *Succ : successors(BB))
493 if (Succ != TheOnlySucc) {
494 DeadSuccessors.insert(Succ);
495 // If our successor lies in a different loop, we don't want to remove
496 // the one-input Phi because it is a LCSSA Phi.
497 bool PreserveLCSSAPhi = !L.contains(Succ);
498 Succ->removePredecessor(BB, PreserveLCSSAPhi);
499 if (MSSAU)
500 MSSAU->removeEdge(BB, Succ);
501 } else
502 ++TheOnlySuccDuplicates;
503
504 assert(TheOnlySuccDuplicates > 0 && "Should be!");
505 // If TheOnlySucc was BB's successor more than once, after transform it
506 // will be its successor only once. Remove redundant inputs from
507 // TheOnlySucc's Phis.
508 bool PreserveLCSSAPhi = !L.contains(TheOnlySucc);
509 for (unsigned Dup = 1; Dup < TheOnlySuccDuplicates; ++Dup)
510 TheOnlySucc->removePredecessor(BB, PreserveLCSSAPhi);
511 if (MSSAU && TheOnlySuccDuplicates > 1)
512 MSSAU->removeDuplicatePhiEdgesBetween(BB, TheOnlySucc);
513
514 IRBuilder<> Builder(BB->getContext());
515 Instruction *Term = BB->getTerminator();
516 Builder.SetInsertPoint(Term);
517 Builder.CreateBr(TheOnlySucc);
518 Term->eraseFromParent();
519
520 for (auto *DeadSucc : DeadSuccessors)
521 DTUpdates.push_back({DominatorTree::Delete, BB, DeadSucc});
522
523 ++NumTerminatorsFolded;
524 }
525 }
526
527 public:
ConstantTerminatorFoldingImpl(Loop & L,LoopInfo & LI,DominatorTree & DT,ScalarEvolution & SE,MemorySSAUpdater * MSSAU)528 ConstantTerminatorFoldingImpl(Loop &L, LoopInfo &LI, DominatorTree &DT,
529 ScalarEvolution &SE,
530 MemorySSAUpdater *MSSAU)
531 : L(L), LI(LI), DT(DT), SE(SE), MSSAU(MSSAU), DFS(&L),
532 DTU(DT, DomTreeUpdater::UpdateStrategy::Eager) {}
run()533 bool run() {
534 assert(L.getLoopLatch() && "Should be single latch!");
535
536 // Collect all available information about status of blocks after constant
537 // folding.
538 analyze();
539 BasicBlock *Header = L.getHeader();
540 (void)Header;
541
542 LLVM_DEBUG(dbgs() << "In function " << Header->getParent()->getName()
543 << ": ");
544
545 if (HasIrreducibleCFG) {
546 LLVM_DEBUG(dbgs() << "Loops with irreducible CFG are not supported!\n");
547 return false;
548 }
549
550 // Nothing to constant-fold.
551 if (FoldCandidates.empty()) {
552 LLVM_DEBUG(
553 dbgs() << "No constant terminator folding candidates found in loop "
554 << Header->getName() << "\n");
555 return false;
556 }
557
558 // TODO: Support deletion of the current loop.
559 if (DeleteCurrentLoop) {
560 LLVM_DEBUG(
561 dbgs()
562 << "Give up constant terminator folding in loop " << Header->getName()
563 << ": we don't currently support deletion of the current loop.\n");
564 return false;
565 }
566
567 // TODO: Support blocks that are not dead, but also not in loop after the
568 // folding.
569 if (BlocksInLoopAfterFolding.size() + DeadLoopBlocks.size() !=
570 L.getNumBlocks()) {
571 LLVM_DEBUG(
572 dbgs() << "Give up constant terminator folding in loop "
573 << Header->getName() << ": we don't currently"
574 " support blocks that are not dead, but will stop "
575 "being a part of the loop after constant-folding.\n");
576 return false;
577 }
578
579 SE.forgetTopmostLoop(&L);
580 // Dump analysis results.
581 LLVM_DEBUG(dump());
582
583 LLVM_DEBUG(dbgs() << "Constant-folding " << FoldCandidates.size()
584 << " terminators in loop " << Header->getName() << "\n");
585
586 // Make the actual transforms.
587 handleDeadExits();
588 foldTerminators();
589
590 if (!DeadLoopBlocks.empty()) {
591 LLVM_DEBUG(dbgs() << "Deleting " << DeadLoopBlocks.size()
592 << " dead blocks in loop " << Header->getName() << "\n");
593 deleteDeadLoopBlocks();
594 } else {
595 // If we didn't do updates inside deleteDeadLoopBlocks, do them here.
596 DTU.applyUpdates(DTUpdates);
597 DTUpdates.clear();
598 }
599
600 if (MSSAU && VerifyMemorySSA)
601 MSSAU->getMemorySSA()->verifyMemorySSA();
602
603 #ifndef NDEBUG
604 // Make sure that we have preserved all data structures after the transform.
605 #if defined(EXPENSIVE_CHECKS)
606 assert(DT.verify(DominatorTree::VerificationLevel::Full) &&
607 "DT broken after transform!");
608 #else
609 assert(DT.verify(DominatorTree::VerificationLevel::Fast) &&
610 "DT broken after transform!");
611 #endif
612 assert(DT.isReachableFromEntry(Header));
613 LI.verify(DT);
614 #endif
615
616 return true;
617 }
618
foldingBreaksCurrentLoop() const619 bool foldingBreaksCurrentLoop() const {
620 return DeleteCurrentLoop;
621 }
622 };
623 } // namespace
624
625 /// Turn branches and switches with known constant conditions into unconditional
626 /// branches.
constantFoldTerminators(Loop & L,DominatorTree & DT,LoopInfo & LI,ScalarEvolution & SE,MemorySSAUpdater * MSSAU,bool & IsLoopDeleted)627 static bool constantFoldTerminators(Loop &L, DominatorTree &DT, LoopInfo &LI,
628 ScalarEvolution &SE,
629 MemorySSAUpdater *MSSAU,
630 bool &IsLoopDeleted) {
631 if (!EnableTermFolding)
632 return false;
633
634 // To keep things simple, only process loops with single latch. We
635 // canonicalize most loops to this form. We can support multi-latch if needed.
636 if (!L.getLoopLatch())
637 return false;
638
639 ConstantTerminatorFoldingImpl BranchFolder(L, LI, DT, SE, MSSAU);
640 bool Changed = BranchFolder.run();
641 IsLoopDeleted = Changed && BranchFolder.foldingBreaksCurrentLoop();
642 return Changed;
643 }
644
mergeBlocksIntoPredecessors(Loop & L,DominatorTree & DT,LoopInfo & LI,MemorySSAUpdater * MSSAU)645 static bool mergeBlocksIntoPredecessors(Loop &L, DominatorTree &DT,
646 LoopInfo &LI, MemorySSAUpdater *MSSAU) {
647 bool Changed = false;
648 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
649 // Copy blocks into a temporary array to avoid iterator invalidation issues
650 // as we remove them.
651 SmallVector<WeakTrackingVH, 16> Blocks(L.blocks());
652
653 for (auto &Block : Blocks) {
654 // Attempt to merge blocks in the trivial case. Don't modify blocks which
655 // belong to other loops.
656 BasicBlock *Succ = cast_or_null<BasicBlock>(Block);
657 if (!Succ)
658 continue;
659
660 BasicBlock *Pred = Succ->getSinglePredecessor();
661 if (!Pred || !Pred->getSingleSuccessor() || LI.getLoopFor(Pred) != &L)
662 continue;
663
664 // Merge Succ into Pred and delete it.
665 MergeBlockIntoPredecessor(Succ, &DTU, &LI, MSSAU);
666
667 if (MSSAU && VerifyMemorySSA)
668 MSSAU->getMemorySSA()->verifyMemorySSA();
669
670 Changed = true;
671 }
672
673 return Changed;
674 }
675
simplifyLoopCFG(Loop & L,DominatorTree & DT,LoopInfo & LI,ScalarEvolution & SE,MemorySSAUpdater * MSSAU,bool & IsLoopDeleted)676 static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI,
677 ScalarEvolution &SE, MemorySSAUpdater *MSSAU,
678 bool &IsLoopDeleted) {
679 bool Changed = false;
680
681 // Constant-fold terminators with known constant conditions.
682 Changed |= constantFoldTerminators(L, DT, LI, SE, MSSAU, IsLoopDeleted);
683
684 if (IsLoopDeleted)
685 return true;
686
687 // Eliminate unconditional branches by merging blocks into their predecessors.
688 Changed |= mergeBlocksIntoPredecessors(L, DT, LI, MSSAU);
689
690 if (Changed)
691 SE.forgetTopmostLoop(&L);
692
693 return Changed;
694 }
695
run(Loop & L,LoopAnalysisManager & AM,LoopStandardAnalysisResults & AR,LPMUpdater & LPMU)696 PreservedAnalyses LoopSimplifyCFGPass::run(Loop &L, LoopAnalysisManager &AM,
697 LoopStandardAnalysisResults &AR,
698 LPMUpdater &LPMU) {
699 Optional<MemorySSAUpdater> MSSAU;
700 if (AR.MSSA)
701 MSSAU = MemorySSAUpdater(AR.MSSA);
702 bool DeleteCurrentLoop = false;
703 if (!simplifyLoopCFG(L, AR.DT, AR.LI, AR.SE,
704 MSSAU.hasValue() ? MSSAU.getPointer() : nullptr,
705 DeleteCurrentLoop))
706 return PreservedAnalyses::all();
707
708 if (DeleteCurrentLoop)
709 LPMU.markLoopAsDeleted(L, "loop-simplifycfg");
710
711 auto PA = getLoopPassPreservedAnalyses();
712 if (AR.MSSA)
713 PA.preserve<MemorySSAAnalysis>();
714 return PA;
715 }
716
717 namespace {
718 class LoopSimplifyCFGLegacyPass : public LoopPass {
719 public:
720 static char ID; // Pass ID, replacement for typeid
LoopSimplifyCFGLegacyPass()721 LoopSimplifyCFGLegacyPass() : LoopPass(ID) {
722 initializeLoopSimplifyCFGLegacyPassPass(*PassRegistry::getPassRegistry());
723 }
724
runOnLoop(Loop * L,LPPassManager & LPM)725 bool runOnLoop(Loop *L, LPPassManager &LPM) override {
726 if (skipLoop(L))
727 return false;
728
729 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
730 LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
731 ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
732 Optional<MemorySSAUpdater> MSSAU;
733 if (EnableMSSALoopDependency) {
734 MemorySSA *MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
735 MSSAU = MemorySSAUpdater(MSSA);
736 if (VerifyMemorySSA)
737 MSSA->verifyMemorySSA();
738 }
739 bool DeleteCurrentLoop = false;
740 bool Changed = simplifyLoopCFG(
741 *L, DT, LI, SE, MSSAU.hasValue() ? MSSAU.getPointer() : nullptr,
742 DeleteCurrentLoop);
743 if (DeleteCurrentLoop)
744 LPM.markLoopAsDeleted(*L);
745 return Changed;
746 }
747
getAnalysisUsage(AnalysisUsage & AU) const748 void getAnalysisUsage(AnalysisUsage &AU) const override {
749 if (EnableMSSALoopDependency) {
750 AU.addRequired<MemorySSAWrapperPass>();
751 AU.addPreserved<MemorySSAWrapperPass>();
752 }
753 AU.addPreserved<DependenceAnalysisWrapperPass>();
754 getLoopAnalysisUsage(AU);
755 }
756 };
757 } // end namespace
758
759 char LoopSimplifyCFGLegacyPass::ID = 0;
760 INITIALIZE_PASS_BEGIN(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
761 "Simplify loop CFG", false, false)
INITIALIZE_PASS_DEPENDENCY(LoopPass)762 INITIALIZE_PASS_DEPENDENCY(LoopPass)
763 INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
764 INITIALIZE_PASS_END(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
765 "Simplify loop CFG", false, false)
766
767 Pass *llvm::createLoopSimplifyCFGPass() {
768 return new LoopSimplifyCFGLegacyPass();
769 }
770