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