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