766 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the Loop SimplifyCFG Pass. This pass is responsible for10// basic loop CFG cleanup, primarily to assist other loop passes. If you11// encounter a noncanonical CFG construct that causes another loop pass to12// 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(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 successors49/// 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>(TI)) {54 if (BI->isUnconditional())55 return nullptr;56 if (BI->getSuccessor(0) == BI->getSuccessor(1))57 return BI->getSuccessor(0);58 ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());59 if (!Cond)60 return nullptr;61 return Cond->isZero() ? BI->getSuccessor(1) : BI->getSuccessor(0);62 }63 64 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {65 auto *CI = dyn_cast<ConstantInt>(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 and89/// 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(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 conditions109/// 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 constant124 // 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 the128 // current loop and its preheader and do not affect preheader's reachibility129 // from any other block. So this variable set to true means that loop's latch130 // 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 entry136 // after the constant folding.137 SmallPtrSet<BasicBlock *, 8> LiveLoopBlocks;138 // The blocks of the original loop that will become unreachable from entry139 // after the constant folding.140 SmallVector<BasicBlock *, 8> DeadLoopBlocks;141 // The exits of the original loop that will still be reachable from entry142 // after the constant folding.143 SmallPtrSet<BasicBlock *, 8> LiveExitBlocks;144 // The exits of the original loop that will become unreachable from entry145 // 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 be150 // folded. Note: fold candidates should be in L but not in any of its151 // 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(Succ) && !LI.isLoopHeader(Succ) && RPO[BB] > RPO[Succ])196 // If an edge goes from a block with greater order number into a block197 // with lesses number, and it is not a loop backedge, then it can only198 // 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 loop205 /// if constant folding of all branches will be done.206 void analyze() {207 DFS.perform(&LI);208 assert(DFS.isComplete() && "DFS is expected to be finished");209 210 // TODO: The algorithm below relies on both RPO and Postorder traversals.211 // When the loop has only reducible CFG inside, then the invariant "all212 // predecessors of X are processed before X in RPO" is preserved. However213 // an irreducible loop can break this invariant (e.g. latch does not have to214 // be the last block in the traversal in this case, and the algorithm relies215 // on this). We can later decide to support such cases by altering the216 // 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 LoopSimplify223 // wasn't able to form one because the loop can be entered through an224 // 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(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(BB)) {242 DeadLoopBlocks.push_back(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 constant249 // folding. Only handle blocks from current loop: branches in child loops250 // are skipped because if they can be folded, they should be folded during251 // the processing of child loops.252 bool TakeFoldCandidate = TheOnlySucc && LI.getLoopFor(BB) == &L;253 if (TakeFoldCandidate)254 FoldCandidates.push_back(BB);255 256 // Handle successors.257 for (BasicBlock *Succ : successors(BB))258 if (!TakeFoldCandidate || TheOnlySucc == Succ) {259 if (L.contains(Succ))260 LiveLoopBlocks.insert(Succ);261 else262 LiveExitBlocks.insert(Succ);263 }264 }265 266 // Amount of dead and live loop blocks should match the total number of267 // 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 their272 // predecessors are in the loop. This may not be the case, as the input loop273 // 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(ExitBlock) &&279 UniqueDeadExits.insert(ExitBlock).second &&280 all_of(predecessors(ExitBlock),281 [this](BasicBlock *Pred) { return L.contains(Pred); }))282 DeadExitBlocks.push_back(ExitBlock);283 284 // Whether or not the edge From->To will still be present in graph after the285 // folding.286 auto IsEdgeLive = [&](BasicBlock *From, BasicBlock *To) {287 if (!LiveLoopBlocks.count(From))288 return false;289 BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(From);290 return !TheOnlySucc || TheOnlySucc == To || LI.getLoopFor(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 analysis297 // is needed.298 if (DeleteCurrentLoop)299 return;300 301 // Otherwise, we should check which blocks will still be a part of the302 // current loop after the transform.303 BlocksInLoopAfterFolding.insert(L.getLoopLatch());304 // If the loop is live, then we should compute what blocks are still in305 // loop after all branch folding has been done. A block is in loop if306 // 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(successors(BB), [&](BasicBlock *Succ) {310 return BlocksInLoopAfterFolding.count(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(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 following327 /// trick:328 ///329 /// preheader:330 /// <preheader code>331 /// br label %loop_header332 ///333 /// loop_header:334 /// ...335 /// br i1 false, label %dead_exit, label %loop_block336 /// ...337 ///338 /// We cannot simply remove edge from the loop to dead exit because in this339 /// 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_header352 ///353 /// loop_header:354 /// ...355 /// br i1 false, label %dead_exit_N, label %loop_block356 /// ...357 ///358 /// Doing so, we preserve static reachibility of all dead exits and can later359 /// 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 to366 // dead exits.367 BasicBlock *Preheader = L.getLoopPreheader();368 BasicBlock *NewPreheader = llvm::SplitBlock(369 Preheader, Preheader->getTerminator(), &DT, &LI, MSSAU);370 371 IRBuilder<> Builder(Preheader->getTerminator());372 SwitchInst *DummySwitch =373 Builder.CreateSwitch(Builder.getInt32(0), 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(BB->phis()));382 383 if (auto *LandingPad = dyn_cast<LandingPadInst>(BB->getFirstNonPHIIt()))384 DeadInstructions.emplace_back(LandingPad);385 386 for (Instruction *I : DeadInstructions) {387 SE.forgetValue(I);388 I->replaceAllUsesWith(PoisonValue::get(I->getType()));389 I->eraseFromParent();390 }391 392 assert(DummyIdx != 0 && "Too many dead exits!");393 DummySwitch->addCase(Builder.getInt32(DummyIdx++), BB);394 DTUpdates.push_back({DominatorTree::Insert, Preheader, BB});395 ++NumLoopExitsDeleted;396 }397 // We don't really need to add branch weights to DummySwitch, because all398 // but one branches are just a temporary artifact - see the comment on top399 // of this function. But, it's easy to estimate the weights, and it helps400 // maintain a property of the overall compiler - that the branch weights401 // 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(*DummySwitch, DummyBranchWeights, /*IsExpected=*/false);407 }408 409 assert(L.getLoopPreheader() == NewPreheader && "Malformed CFG?");410 if (Loop *OuterLoop = LI.getLoopFor(Preheader)) {411 // When we break dead edges, the outer loop may become unreachable from412 // the current loop. We need to fix loop info accordingly. For this, we413 // find the most nested loop that still contains L and remove L from all414 // loops that are inside of it.415 Loop *StillReachable = getInnermostLoopFor(LiveExitBlocks, L, LI);416 417 // Okay, our loop is no longer in the outer loop (and maybe not in some of418 // its parents as well). Make the fixup.419 if (StillReachable != OuterLoop) {420 LI.changeLoopFor(NewPreheader, StillReachable);421 removeBlockFromLoops(NewPreheader, OuterLoop, StillReachable);422 for (auto *BB : L.blocks())423 removeBlockFromLoops(BB, OuterLoop, StillReachable);424 OuterLoop->removeChildLoop(&L);425 if (StillReachable)426 StillReachable->addChildLoop(&L);427 else428 LI.addTopLevelLoop(&L);429 430 // Some values from loops in [OuterLoop, StillReachable) could be used431 // in the current loop. Now it is not their child anymore, so such uses432 // 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(DTUpdates, DT, /*UpdateDT=*/true);440 else441 DTU.applyUpdates(DTUpdates);442 DTUpdates.clear();443 formLCSSARecursively(*FixLCSSALoop, DT, &LI, &SE);444 SE.forgetBlockAndLoopDispositions();445 }446 }447 448 if (MSSAU) {449 // Clear all updates now. Facilitates deletes that follow.450 MSSAU->applyUpdates(DTUpdates, DT, /*UpdateDT=*/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 all458 /// 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(DeadLoopBlocksSet);464 }465 466 // The function LI.erase has some invariants that need to be preserved when467 // 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 cannot469 // just remove blocks one by one, because after removal of preheader we may470 // break this invariant for the dead loop. So we detatch and erase all dead471 // 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(DL);481 LI.addTopLevelLoop(DL);482 }483 LI.erase(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(DeadLoopBlocks, &DTUpdates, /*KeepOneInputPHIs*/true);495 DTU.applyUpdates(DTUpdates);496 DTUpdates.clear();497 for (auto *BB : DeadLoopBlocks)498 DTU.deleteBB(BB);499 500 NumLoopBlocksDeleted += DeadLoopBlocks.size();501 }502 503 /// Constant-fold terminators of blocks accumulated in FoldCandidates into the504 /// 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(Succ);521 // If our successor lies in a different loop, we don't want to remove522 // the one-input Phi because it is a LCSSA Phi.523 bool PreserveLCSSAPhi = !L.contains(Succ);524 Succ->removePredecessor(BB, PreserveLCSSAPhi);525 if (MSSAU)526 MSSAU->removeEdge(BB, Succ);527 } else528 ++TheOnlySuccDuplicates;529 530 assert(TheOnlySuccDuplicates > 0 && "Should be!");531 // If TheOnlySucc was BB's successor more than once, after transform it532 // will be its successor only once. Remove redundant inputs from533 // TheOnlySucc's Phis.534 bool PreserveLCSSAPhi = !L.contains(TheOnlySucc);535 for (unsigned Dup = 1; Dup < TheOnlySuccDuplicates; ++Dup)536 TheOnlySucc->removePredecessor(BB, PreserveLCSSAPhi);537 if (MSSAU && TheOnlySuccDuplicates > 1)538 MSSAU->removeDuplicatePhiEdgesBetween(BB, TheOnlySucc);539 540 IRBuilder<> Builder(BB->getContext());541 Instruction *Term = BB->getTerminator();542 Builder.SetInsertPoint(Term);543 Builder.CreateBr(TheOnlySucc);544 Term->eraseFromParent();545 546 for (auto *DeadSucc : DeadSuccessors)547 DTUpdates.push_back({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 constant563 // 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 the600 // 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 for612 // 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);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(DTUpdates);644 DTUpdates.clear();645 }646 647 if (MSSAU && VerifyMemorySSA)648 MSSAU->getMemorySSA()->verifyMemorySSA();649 650#ifndef NDEBUG651 // 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#else656 assert(DT.verify(DominatorTree::VerificationLevel::Fast) &&657 "DT broken after transform!");658#endif659 assert(DT.isReachableFromEntry(Header));660 LI.verify(DT);661#endif662 663 return true;664 }665 666 bool foldingBreaksCurrentLoop() const {667 return DeleteCurrentLoop;668 }669};670} // namespace671 672/// Turn branches and switches with known constant conditions into unconditional673/// 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. We682 // 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 issues698 // 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 which703 // belong to other loops.704 BasicBlock *Succ = cast_or_null<BasicBlock>(Block);705 if (!Succ)706 continue;707 708 BasicBlock *Pred = Succ->getSinglePredecessor();709 if (!Pred || !Pred->getSingleSuccessor() || LI.getLoopFor(Pred) != &L)710 continue;711 712 // Merge Succ into Pred and delete it.713 MergeBlockIntoPredecessor(Succ, &DTU, &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);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, AR.DT, AR.LI, AR.SE, MSSAU ? &*MSSAU : nullptr,755 DeleteCurrentLoop))756 return PreservedAnalyses::all();757 758 if (DeleteCurrentLoop)759 LPMU.markLoopAsDeleted(L, "loop-simplifycfg");760 761 auto PA = getLoopPassPreservedAnalyses();762 if (AR.MSSA)763 PA.preserve<MemorySSAAnalysis>();764 return PA;765}766