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