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/DomTreeUpdater.h"
20#include "llvm/Analysis/LoopInfo.h"
21#include "llvm/Analysis/LoopIterator.h"
22#include "llvm/Analysis/MemorySSA.h"
23#include "llvm/Analysis/MemorySSAUpdater.h"
24#include "llvm/Analysis/ScalarEvolution.h"
25#include "llvm/IR/Dominators.h"
26#include "llvm/IR/IRBuilder.h"
27#include "llvm/Support/CommandLine.h"
28#include "llvm/Transforms/Scalar.h"
29#include "llvm/Transforms/Scalar/LoopPassManager.h"
30#include "llvm/Transforms/Utils/BasicBlockUtils.h"
31#include "llvm/Transforms/Utils/LoopUtils.h"
32#include <optional>
33using namespace llvm;
34
35#define DEBUG_TYPE "loop-simplifycfg"
36
37static cl::opt<bool> EnableTermFolding("enable-loop-simplifycfg-term-folding",
38 cl::init(Val: true));
39
40STATISTIC(NumTerminatorsFolded,
41 "Number of terminators folded to unconditional branches");
42STATISTIC(NumLoopBlocksDeleted,
43 "Number of loop blocks deleted");
44STATISTIC(NumLoopExitsDeleted,
45 "Number of loop exiting edges deleted");
46
47/// If \p BB is a switch or a conditional branch, but only one of its successors
48/// can be reached from this block in runtime, return this successor. Otherwise,
49/// return nullptr.
50static BasicBlock *getOnlyLiveSuccessor(BasicBlock *BB) {
51 Instruction *TI = BB->getTerminator();
52 if (BranchInst *BI = dyn_cast<BranchInst>(Val: TI)) {
53 if (BI->isUnconditional())
54 return nullptr;
55 if (BI->getSuccessor(i: 0) == BI->getSuccessor(i: 1))
56 return BI->getSuccessor(i: 0);
57 ConstantInt *Cond = dyn_cast<ConstantInt>(Val: BI->getCondition());
58 if (!Cond)
59 return nullptr;
60 return Cond->isZero() ? BI->getSuccessor(i: 1) : BI->getSuccessor(i: 0);
61 }
62
63 if (SwitchInst *SI = dyn_cast<SwitchInst>(Val: TI)) {
64 auto *CI = dyn_cast<ConstantInt>(Val: SI->getCondition());
65 if (!CI)
66 return nullptr;
67 for (auto Case : SI->cases())
68 if (Case.getCaseValue() == CI)
69 return Case.getCaseSuccessor();
70 return SI->getDefaultDest();
71 }
72
73 return nullptr;
74}
75
76/// Removes \p BB from all loops from [FirstLoop, LastLoop) in parent chain.
77static void removeBlockFromLoops(BasicBlock *BB, Loop *FirstLoop,
78 Loop *LastLoop = nullptr) {
79 assert((!LastLoop || LastLoop->contains(FirstLoop->getHeader())) &&
80 "First loop is supposed to be inside of last loop!");
81 assert(FirstLoop->contains(BB) && "Must be a loop block!");
82 for (Loop *Current = FirstLoop; Current != LastLoop;
83 Current = Current->getParentLoop())
84 Current->removeBlockFromLoop(BB);
85}
86
87/// Find innermost loop that contains at least one block from \p BBs and
88/// contains the header of loop \p L.
89static Loop *getInnermostLoopFor(SmallPtrSetImpl<BasicBlock *> &BBs,
90 Loop &L, LoopInfo &LI) {
91 Loop *Innermost = nullptr;
92 for (BasicBlock *BB : BBs) {
93 Loop *BBL = LI.getLoopFor(BB);
94 while (BBL && !BBL->contains(BB: L.getHeader()))
95 BBL = BBL->getParentLoop();
96 if (BBL == &L)
97 BBL = BBL->getParentLoop();
98 if (!BBL)
99 continue;
100 if (!Innermost || BBL->getLoopDepth() > Innermost->getLoopDepth())
101 Innermost = BBL;
102 }
103 return Innermost;
104}
105
106namespace {
107/// Helper class that can turn branches and switches with constant conditions
108/// into unconditional branches.
109class ConstantTerminatorFoldingImpl {
110private:
111 Loop &L;
112 LoopInfo &LI;
113 DominatorTree &DT;
114 ScalarEvolution &SE;
115 MemorySSAUpdater *MSSAU;
116 LoopBlocksDFS DFS;
117 DomTreeUpdater DTU;
118 SmallVector<DominatorTree::UpdateType, 16> DTUpdates;
119
120 // Whether or not the current loop has irreducible CFG.
121 bool HasIrreducibleCFG = false;
122 // Whether or not the current loop will still exist after terminator constant
123 // folding will be done. In theory, there are two ways how it can happen:
124 // 1. Loop's latch(es) become unreachable from loop header;
125 // 2. Loop's header becomes unreachable from method entry.
126 // In practice, the second situation is impossible because we only modify the
127 // current loop and its preheader and do not affect preheader's reachibility
128 // from any other block. So this variable set to true means that loop's latch
129 // has become unreachable from loop header.
130 bool DeleteCurrentLoop = false;
131
132 // The blocks of the original loop that will still be reachable from entry
133 // after the constant folding.
134 SmallPtrSet<BasicBlock *, 8> LiveLoopBlocks;
135 // The blocks of the original loop that will become unreachable from entry
136 // after the constant folding.
137 SmallVector<BasicBlock *, 8> DeadLoopBlocks;
138 // The exits of the original loop that will still be reachable from entry
139 // after the constant folding.
140 SmallPtrSet<BasicBlock *, 8> LiveExitBlocks;
141 // The exits of the original loop that will become unreachable from entry
142 // after the constant folding.
143 SmallVector<BasicBlock *, 8> DeadExitBlocks;
144 // The blocks that will still be a part of the current loop after folding.
145 SmallPtrSet<BasicBlock *, 8> BlocksInLoopAfterFolding;
146 // The blocks that have terminators with constant condition that can be
147 // folded. Note: fold candidates should be in L but not in any of its
148 // subloops to avoid complex LI updates.
149 SmallVector<BasicBlock *, 8> FoldCandidates;
150
151 void dump() const {
152 dbgs() << "Constant terminator folding for loop " << L << "\n";
153 dbgs() << "After terminator constant-folding, the loop will";
154 if (!DeleteCurrentLoop)
155 dbgs() << " not";
156 dbgs() << " be destroyed\n";
157 auto PrintOutVector = [&](const char *Message,
158 const SmallVectorImpl<BasicBlock *> &S) {
159 dbgs() << Message << "\n";
160 for (const BasicBlock *BB : S)
161 dbgs() << "\t" << BB->getName() << "\n";
162 };
163 auto PrintOutSet = [&](const char *Message,
164 const SmallPtrSetImpl<BasicBlock *> &S) {
165 dbgs() << Message << "\n";
166 for (const BasicBlock *BB : S)
167 dbgs() << "\t" << BB->getName() << "\n";
168 };
169 PrintOutVector("Blocks in which we can constant-fold terminator:",
170 FoldCandidates);
171 PrintOutSet("Live blocks from the original loop:", LiveLoopBlocks);
172 PrintOutVector("Dead blocks from the original loop:", DeadLoopBlocks);
173 PrintOutSet("Live exit blocks:", LiveExitBlocks);
174 PrintOutVector("Dead exit blocks:", DeadExitBlocks);
175 if (!DeleteCurrentLoop)
176 PrintOutSet("The following blocks will still be part of the loop:",
177 BlocksInLoopAfterFolding);
178 }
179
180 /// Whether or not the current loop has irreducible CFG.
181 bool hasIrreducibleCFG(LoopBlocksDFS &DFS) {
182 assert(DFS.isComplete() && "DFS is expected to be finished");
183 // Index of a basic block in RPO traversal.
184 DenseMap<const BasicBlock *, unsigned> RPO;
185 unsigned Current = 0;
186 for (auto I = DFS.beginRPO(), E = DFS.endRPO(); I != E; ++I)
187 RPO[*I] = Current++;
188
189 for (auto I = DFS.beginRPO(), E = DFS.endRPO(); I != E; ++I) {
190 BasicBlock *BB = *I;
191 for (auto *Succ : successors(BB))
192 if (L.contains(BB: Succ) && !LI.isLoopHeader(BB: Succ) && RPO[BB] > RPO[Succ])
193 // If an edge goes from a block with greater order number into a block
194 // with lesses number, and it is not a loop backedge, then it can only
195 // be a part of irreducible non-loop cycle.
196 return true;
197 }
198 return false;
199 }
200
201 /// Fill all information about status of blocks and exits of the current loop
202 /// if constant folding of all branches will be done.
203 void analyze() {
204 DFS.perform(LI: &LI);
205 assert(DFS.isComplete() && "DFS is expected to be finished");
206
207 // TODO: The algorithm below relies on both RPO and Postorder traversals.
208 // When the loop has only reducible CFG inside, then the invariant "all
209 // predecessors of X are processed before X in RPO" is preserved. However
210 // an irreducible loop can break this invariant (e.g. latch does not have to
211 // be the last block in the traversal in this case, and the algorithm relies
212 // on this). We can later decide to support such cases by altering the
213 // algorithms, but so far we just give up analyzing them.
214 if (hasIrreducibleCFG(DFS)) {
215 HasIrreducibleCFG = true;
216 return;
217 }
218
219 // Collect live and dead loop blocks and exits.
220 LiveLoopBlocks.insert(Ptr: L.getHeader());
221 for (auto I = DFS.beginRPO(), E = DFS.endRPO(); I != E; ++I) {
222 BasicBlock *BB = *I;
223
224 // If a loop block wasn't marked as live so far, then it's dead.
225 if (!LiveLoopBlocks.count(Ptr: BB)) {
226 DeadLoopBlocks.push_back(Elt: BB);
227 continue;
228 }
229
230 BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(BB);
231
232 // If a block has only one live successor, it's a candidate on constant
233 // folding. Only handle blocks from current loop: branches in child loops
234 // are skipped because if they can be folded, they should be folded during
235 // the processing of child loops.
236 bool TakeFoldCandidate = TheOnlySucc && LI.getLoopFor(BB) == &L;
237 if (TakeFoldCandidate)
238 FoldCandidates.push_back(Elt: BB);
239
240 // Handle successors.
241 for (BasicBlock *Succ : successors(BB))
242 if (!TakeFoldCandidate || TheOnlySucc == Succ) {
243 if (L.contains(BB: Succ))
244 LiveLoopBlocks.insert(Ptr: Succ);
245 else
246 LiveExitBlocks.insert(Ptr: Succ);
247 }
248 }
249
250 // Amount of dead and live loop blocks should match the total number of
251 // blocks in loop.
252 assert(L.getNumBlocks() == LiveLoopBlocks.size() + DeadLoopBlocks.size() &&
253 "Malformed block sets?");
254
255 // Now, all exit blocks that are not marked as live are dead, if all their
256 // predecessors are in the loop. This may not be the case, as the input loop
257 // may not by in loop-simplify/canonical form.
258 SmallVector<BasicBlock *, 8> ExitBlocks;
259 L.getExitBlocks(ExitBlocks);
260 SmallPtrSet<BasicBlock *, 8> UniqueDeadExits;
261 for (auto *ExitBlock : ExitBlocks)
262 if (!LiveExitBlocks.count(Ptr: ExitBlock) &&
263 UniqueDeadExits.insert(Ptr: ExitBlock).second &&
264 all_of(Range: predecessors(BB: ExitBlock),
265 P: [this](BasicBlock *Pred) { return L.contains(BB: Pred); }))
266 DeadExitBlocks.push_back(Elt: ExitBlock);
267
268 // Whether or not the edge From->To will still be present in graph after the
269 // folding.
270 auto IsEdgeLive = [&](BasicBlock *From, BasicBlock *To) {
271 if (!LiveLoopBlocks.count(Ptr: From))
272 return false;
273 BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(BB: From);
274 return !TheOnlySucc || TheOnlySucc == To || LI.getLoopFor(BB: From) != &L;
275 };
276
277 // The loop will not be destroyed if its latch is live.
278 DeleteCurrentLoop = !IsEdgeLive(L.getLoopLatch(), L.getHeader());
279
280 // If we are going to delete the current loop completely, no extra analysis
281 // is needed.
282 if (DeleteCurrentLoop)
283 return;
284
285 // Otherwise, we should check which blocks will still be a part of the
286 // current loop after the transform.
287 BlocksInLoopAfterFolding.insert(Ptr: L.getLoopLatch());
288 // If the loop is live, then we should compute what blocks are still in
289 // loop after all branch folding has been done. A block is in loop if
290 // it has a live edge to another block that is in the loop; by definition,
291 // latch is in the loop.
292 auto BlockIsInLoop = [&](BasicBlock *BB) {
293 return any_of(Range: successors(BB), P: [&](BasicBlock *Succ) {
294 return BlocksInLoopAfterFolding.count(Ptr: Succ) && IsEdgeLive(BB, Succ);
295 });
296 };
297 for (auto I = DFS.beginPostorder(), E = DFS.endPostorder(); I != E; ++I) {
298 BasicBlock *BB = *I;
299 if (BlockIsInLoop(BB))
300 BlocksInLoopAfterFolding.insert(Ptr: BB);
301 }
302
303 assert(BlocksInLoopAfterFolding.count(L.getHeader()) &&
304 "Header not in loop?");
305 assert(BlocksInLoopAfterFolding.size() <= LiveLoopBlocks.size() &&
306 "All blocks that stay in loop should be live!");
307 }
308
309 /// We need to preserve static reachibility of all loop exit blocks (this is)
310 /// required by loop pass manager. In order to do it, we make the following
311 /// trick:
312 ///
313 /// preheader:
314 /// <preheader code>
315 /// br label %loop_header
316 ///
317 /// loop_header:
318 /// ...
319 /// br i1 false, label %dead_exit, label %loop_block
320 /// ...
321 ///
322 /// We cannot simply remove edge from the loop to dead exit because in this
323 /// case dead_exit (and its successors) may become unreachable. To avoid that,
324 /// we insert the following fictive preheader:
325 ///
326 /// preheader:
327 /// <preheader code>
328 /// switch i32 0, label %preheader-split,
329 /// [i32 1, label %dead_exit_1],
330 /// [i32 2, label %dead_exit_2],
331 /// ...
332 /// [i32 N, label %dead_exit_N],
333 ///
334 /// preheader-split:
335 /// br label %loop_header
336 ///
337 /// loop_header:
338 /// ...
339 /// br i1 false, label %dead_exit_N, label %loop_block
340 /// ...
341 ///
342 /// Doing so, we preserve static reachibility of all dead exits and can later
343 /// remove edges from the loop to these blocks.
344 void handleDeadExits() {
345 // If no dead exits, nothing to do.
346 if (DeadExitBlocks.empty())
347 return;
348
349 // Construct split preheader and the dummy switch to thread edges from it to
350 // dead exits.
351 BasicBlock *Preheader = L.getLoopPreheader();
352 BasicBlock *NewPreheader = llvm::SplitBlock(
353 Old: Preheader, SplitPt: Preheader->getTerminator(), DT: &DT, LI: &LI, MSSAU);
354
355 IRBuilder<> Builder(Preheader->getTerminator());
356 SwitchInst *DummySwitch =
357 Builder.CreateSwitch(V: Builder.getInt32(C: 0), Dest: NewPreheader);
358 Preheader->getTerminator()->eraseFromParent();
359
360 unsigned DummyIdx = 1;
361 for (BasicBlock *BB : DeadExitBlocks) {
362 // Eliminate all Phis and LandingPads from dead exits.
363 // TODO: Consider removing all instructions in this dead block.
364 SmallVector<Instruction *, 4> DeadInstructions;
365 for (auto &PN : BB->phis())
366 DeadInstructions.push_back(Elt: &PN);
367
368 if (auto *LandingPad = dyn_cast<LandingPadInst>(Val: BB->getFirstNonPHI()))
369 DeadInstructions.emplace_back(Args&: LandingPad);
370
371 for (Instruction *I : DeadInstructions) {
372 SE.forgetBlockAndLoopDispositions(V: I);
373 I->replaceAllUsesWith(V: PoisonValue::get(T: I->getType()));
374 I->eraseFromParent();
375 }
376
377 assert(DummyIdx != 0 && "Too many dead exits!");
378 DummySwitch->addCase(OnVal: Builder.getInt32(C: DummyIdx++), Dest: BB);
379 DTUpdates.push_back(Elt: {DominatorTree::Insert, Preheader, BB});
380 ++NumLoopExitsDeleted;
381 }
382
383 assert(L.getLoopPreheader() == NewPreheader && "Malformed CFG?");
384 if (Loop *OuterLoop = LI.getLoopFor(BB: Preheader)) {
385 // When we break dead edges, the outer loop may become unreachable from
386 // the current loop. We need to fix loop info accordingly. For this, we
387 // find the most nested loop that still contains L and remove L from all
388 // loops that are inside of it.
389 Loop *StillReachable = getInnermostLoopFor(BBs&: LiveExitBlocks, L, LI);
390
391 // Okay, our loop is no longer in the outer loop (and maybe not in some of
392 // its parents as well). Make the fixup.
393 if (StillReachable != OuterLoop) {
394 LI.changeLoopFor(BB: NewPreheader, L: StillReachable);
395 removeBlockFromLoops(BB: NewPreheader, FirstLoop: OuterLoop, LastLoop: StillReachable);
396 for (auto *BB : L.blocks())
397 removeBlockFromLoops(BB, FirstLoop: OuterLoop, LastLoop: StillReachable);
398 OuterLoop->removeChildLoop(Child: &L);
399 if (StillReachable)
400 StillReachable->addChildLoop(NewChild: &L);
401 else
402 LI.addTopLevelLoop(New: &L);
403
404 // Some values from loops in [OuterLoop, StillReachable) could be used
405 // in the current loop. Now it is not their child anymore, so such uses
406 // require LCSSA Phis.
407 Loop *FixLCSSALoop = OuterLoop;
408 while (FixLCSSALoop->getParentLoop() != StillReachable)
409 FixLCSSALoop = FixLCSSALoop->getParentLoop();
410 assert(FixLCSSALoop && "Should be a loop!");
411 // We need all DT updates to be done before forming LCSSA.
412 if (MSSAU)
413 MSSAU->applyUpdates(Updates: DTUpdates, DT, /*UpdateDT=*/UpdateDTFirst: true);
414 else
415 DTU.applyUpdates(Updates: DTUpdates);
416 DTUpdates.clear();
417 formLCSSARecursively(L&: *FixLCSSALoop, DT, LI: &LI, SE: &SE);
418 SE.forgetBlockAndLoopDispositions();
419 }
420 }
421
422 if (MSSAU) {
423 // Clear all updates now. Facilitates deletes that follow.
424 MSSAU->applyUpdates(Updates: DTUpdates, DT, /*UpdateDT=*/UpdateDTFirst: true);
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.
433 void deleteDeadLoopBlocks() {
434 if (MSSAU) {
435 SmallSetVector<BasicBlock *, 8> DeadLoopBlocksSet(DeadLoopBlocks.begin(),
436 DeadLoopBlocks.end());
437 MSSAU->removeBlocks(DeadBlocks: 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->isOutermost()) {
451 for (auto *PL = DL->getParentLoop(); PL; PL = PL->getParentLoop())
452 for (auto *BB : DL->getBlocks())
453 PL->removeBlockFromLoop(BB);
454 DL->getParentLoop()->removeChildLoop(Child: DL);
455 LI.addTopLevelLoop(New: DL);
456 }
457 LI.erase(L: 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 detachDeadBlocks(BBs: DeadLoopBlocks, Updates: &DTUpdates, /*KeepOneInputPHIs*/true);
469 DTU.applyUpdates(Updates: DTUpdates);
470 DTUpdates.clear();
471 for (auto *BB : DeadLoopBlocks)
472 DTU.deleteBB(DelBB: BB);
473
474 NumLoopBlocksDeleted += DeadLoopBlocks.size();
475 }
476
477 /// Constant-fold terminators of blocks accumulated in FoldCandidates into the
478 /// unconditional branches.
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(Ptr: 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(BB: Succ);
498 Succ->removePredecessor(Pred: BB, KeepOneInputPHIs: PreserveLCSSAPhi);
499 if (MSSAU)
500 MSSAU->removeEdge(From: BB, To: 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(BB: TheOnlySucc);
509 for (unsigned Dup = 1; Dup < TheOnlySuccDuplicates; ++Dup)
510 TheOnlySucc->removePredecessor(Pred: BB, KeepOneInputPHIs: PreserveLCSSAPhi);
511 if (MSSAU && TheOnlySuccDuplicates > 1)
512 MSSAU->removeDuplicatePhiEdgesBetween(From: BB, To: TheOnlySucc);
513
514 IRBuilder<> Builder(BB->getContext());
515 Instruction *Term = BB->getTerminator();
516 Builder.SetInsertPoint(Term);
517 Builder.CreateBr(Dest: TheOnlySucc);
518 Term->eraseFromParent();
519
520 for (auto *DeadSucc : DeadSuccessors)
521 DTUpdates.push_back(Elt: {DominatorTree::Delete, BB, DeadSucc});
522
523 ++NumTerminatorsFolded;
524 }
525 }
526
527public:
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) {}
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 // TODO: Tokens may breach LCSSA form by default. However, the transform for
580 // dead exit blocks requires LCSSA form to be maintained for all values,
581 // tokens included, otherwise it may break use-def dominance (see PR56243).
582 if (!DeadExitBlocks.empty() && !L.isLCSSAForm(DT, /*IgnoreTokens*/ false)) {
583 assert(L.isLCSSAForm(DT, /*IgnoreTokens*/ true) &&
584 "LCSSA broken not by tokens?");
585 LLVM_DEBUG(dbgs() << "Give up constant terminator folding in loop "
586 << Header->getName()
587 << ": tokens uses potentially break LCSSA form.\n");
588 return false;
589 }
590
591 SE.forgetTopmostLoop(L: &L);
592 // Dump analysis results.
593 LLVM_DEBUG(dump());
594
595 LLVM_DEBUG(dbgs() << "Constant-folding " << FoldCandidates.size()
596 << " terminators in loop " << Header->getName() << "\n");
597
598 if (!DeadLoopBlocks.empty())
599 SE.forgetBlockAndLoopDispositions();
600
601 // Make the actual transforms.
602 handleDeadExits();
603 foldTerminators();
604
605 if (!DeadLoopBlocks.empty()) {
606 LLVM_DEBUG(dbgs() << "Deleting " << DeadLoopBlocks.size()
607 << " dead blocks in loop " << Header->getName() << "\n");
608 deleteDeadLoopBlocks();
609 } else {
610 // If we didn't do updates inside deleteDeadLoopBlocks, do them here.
611 DTU.applyUpdates(Updates: DTUpdates);
612 DTUpdates.clear();
613 }
614
615 if (MSSAU && VerifyMemorySSA)
616 MSSAU->getMemorySSA()->verifyMemorySSA();
617
618#ifndef NDEBUG
619 // Make sure that we have preserved all data structures after the transform.
620#if defined(EXPENSIVE_CHECKS)
621 assert(DT.verify(DominatorTree::VerificationLevel::Full) &&
622 "DT broken after transform!");
623#else
624 assert(DT.verify(DominatorTree::VerificationLevel::Fast) &&
625 "DT broken after transform!");
626#endif
627 assert(DT.isReachableFromEntry(Header));
628 LI.verify(DT);
629#endif
630
631 return true;
632 }
633
634 bool foldingBreaksCurrentLoop() const {
635 return DeleteCurrentLoop;
636 }
637};
638} // namespace
639
640/// Turn branches and switches with known constant conditions into unconditional
641/// branches.
642static bool constantFoldTerminators(Loop &L, DominatorTree &DT, LoopInfo &LI,
643 ScalarEvolution &SE,
644 MemorySSAUpdater *MSSAU,
645 bool &IsLoopDeleted) {
646 if (!EnableTermFolding)
647 return false;
648
649 // To keep things simple, only process loops with single latch. We
650 // canonicalize most loops to this form. We can support multi-latch if needed.
651 if (!L.getLoopLatch())
652 return false;
653
654 ConstantTerminatorFoldingImpl BranchFolder(L, LI, DT, SE, MSSAU);
655 bool Changed = BranchFolder.run();
656 IsLoopDeleted = Changed && BranchFolder.foldingBreaksCurrentLoop();
657 return Changed;
658}
659
660static bool mergeBlocksIntoPredecessors(Loop &L, DominatorTree &DT,
661 LoopInfo &LI, MemorySSAUpdater *MSSAU,
662 ScalarEvolution &SE) {
663 bool Changed = false;
664 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
665 // Copy blocks into a temporary array to avoid iterator invalidation issues
666 // as we remove them.
667 SmallVector<WeakTrackingVH, 16> Blocks(L.blocks());
668
669 for (auto &Block : Blocks) {
670 // Attempt to merge blocks in the trivial case. Don't modify blocks which
671 // belong to other loops.
672 BasicBlock *Succ = cast_or_null<BasicBlock>(Val&: Block);
673 if (!Succ)
674 continue;
675
676 BasicBlock *Pred = Succ->getSinglePredecessor();
677 if (!Pred || !Pred->getSingleSuccessor() || LI.getLoopFor(BB: Pred) != &L)
678 continue;
679
680 // Merge Succ into Pred and delete it.
681 MergeBlockIntoPredecessor(BB: Succ, DTU: &DTU, LI: &LI, MSSAU);
682
683 if (MSSAU && VerifyMemorySSA)
684 MSSAU->getMemorySSA()->verifyMemorySSA();
685
686 Changed = true;
687 }
688
689 if (Changed)
690 SE.forgetBlockAndLoopDispositions();
691
692 return Changed;
693}
694
695static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI,
696 ScalarEvolution &SE, MemorySSAUpdater *MSSAU,
697 bool &IsLoopDeleted) {
698 bool Changed = false;
699
700 // Constant-fold terminators with known constant conditions.
701 Changed |= constantFoldTerminators(L, DT, LI, SE, MSSAU, IsLoopDeleted);
702
703 if (IsLoopDeleted)
704 return true;
705
706 // Eliminate unconditional branches by merging blocks into their predecessors.
707 Changed |= mergeBlocksIntoPredecessors(L, DT, LI, MSSAU, SE);
708
709 if (Changed)
710 SE.forgetTopmostLoop(L: &L);
711
712 return Changed;
713}
714
715PreservedAnalyses LoopSimplifyCFGPass::run(Loop &L, LoopAnalysisManager &AM,
716 LoopStandardAnalysisResults &AR,
717 LPMUpdater &LPMU) {
718 std::optional<MemorySSAUpdater> MSSAU;
719 if (AR.MSSA)
720 MSSAU = MemorySSAUpdater(AR.MSSA);
721 bool DeleteCurrentLoop = false;
722 if (!simplifyLoopCFG(L, DT&: AR.DT, LI&: AR.LI, SE&: AR.SE, MSSAU: MSSAU ? &*MSSAU : nullptr,
723 IsLoopDeleted&: DeleteCurrentLoop))
724 return PreservedAnalyses::all();
725
726 if (DeleteCurrentLoop)
727 LPMU.markLoopAsDeleted(L, Name: "loop-simplifycfg");
728
729 auto PA = getLoopPassPreservedAnalyses();
730 if (AR.MSSA)
731 PA.preserve<MemorySSAAnalysis>();
732 return PA;
733}
734