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