1 //===--------- LoopSimplifyCFG.cpp - Loop CFG Simplification Pass ---------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the Loop SimplifyCFG Pass. This pass is responsible for
11 // basic loop CFG cleanup, primarily to assist other loop passes. If you
12 // encounter a noncanonical CFG construct that causes another loop pass to
13 // perform suboptimally, this is the place to fix it up.
14 //
15 //===----------------------------------------------------------------------===//
16
17 #include "llvm/Transforms/Scalar/LoopSimplifyCFG.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/ADT/Statistic.h"
20 #include "llvm/Analysis/AliasAnalysis.h"
21 #include "llvm/Analysis/AssumptionCache.h"
22 #include "llvm/Analysis/BasicAliasAnalysis.h"
23 #include "llvm/Analysis/DependenceAnalysis.h"
24 #include "llvm/Analysis/GlobalsModRef.h"
25 #include "llvm/Analysis/LoopInfo.h"
26 #include "llvm/Analysis/LoopPass.h"
27 #include "llvm/Analysis/MemorySSA.h"
28 #include "llvm/Analysis/MemorySSAUpdater.h"
29 #include "llvm/Analysis/ScalarEvolution.h"
30 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
31 #include "llvm/Analysis/TargetTransformInfo.h"
32 #include "llvm/IR/DomTreeUpdater.h"
33 #include "llvm/IR/Dominators.h"
34 #include "llvm/Transforms/Scalar.h"
35 #include "llvm/Transforms/Scalar/LoopPassManager.h"
36 #include "llvm/Transforms/Utils.h"
37 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
38 #include "llvm/Transforms/Utils/Local.h"
39 #include "llvm/Transforms/Utils/LoopUtils.h"
40 using namespace llvm;
41
42 #define DEBUG_TYPE "loop-simplifycfg"
43
44 static cl::opt<bool> EnableTermFolding("enable-loop-simplifycfg-term-folding",
45 cl::init(false));
46
47 STATISTIC(NumTerminatorsFolded,
48 "Number of terminators folded to unconditional branches");
49 STATISTIC(NumLoopBlocksDeleted,
50 "Number of loop blocks deleted");
51 STATISTIC(NumLoopExitsDeleted,
52 "Number of loop exiting edges deleted");
53
54 /// If \p BB is a switch or a conditional branch, but only one of its successors
55 /// can be reached from this block in runtime, return this successor. Otherwise,
56 /// return nullptr.
getOnlyLiveSuccessor(BasicBlock * BB)57 static BasicBlock *getOnlyLiveSuccessor(BasicBlock *BB) {
58 Instruction *TI = BB->getTerminator();
59 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
60 if (BI->isUnconditional())
61 return nullptr;
62 if (BI->getSuccessor(0) == BI->getSuccessor(1))
63 return BI->getSuccessor(0);
64 ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
65 if (!Cond)
66 return nullptr;
67 return Cond->isZero() ? BI->getSuccessor(1) : BI->getSuccessor(0);
68 }
69
70 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
71 auto *CI = dyn_cast<ConstantInt>(SI->getCondition());
72 if (!CI)
73 return nullptr;
74 for (auto Case : SI->cases())
75 if (Case.getCaseValue() == CI)
76 return Case.getCaseSuccessor();
77 return SI->getDefaultDest();
78 }
79
80 return nullptr;
81 }
82
83 namespace {
84 /// Helper class that can turn branches and switches with constant conditions
85 /// into unconditional branches.
86 class ConstantTerminatorFoldingImpl {
87 private:
88 Loop &L;
89 LoopInfo &LI;
90 DominatorTree &DT;
91 ScalarEvolution &SE;
92 MemorySSAUpdater *MSSAU;
93
94 // Whether or not the current loop has irreducible CFG.
95 bool HasIrreducibleCFG = false;
96 // Whether or not the current loop will still exist after terminator constant
97 // folding will be done. In theory, there are two ways how it can happen:
98 // 1. Loop's latch(es) become unreachable from loop header;
99 // 2. Loop's header becomes unreachable from method entry.
100 // In practice, the second situation is impossible because we only modify the
101 // current loop and its preheader and do not affect preheader's reachibility
102 // from any other block. So this variable set to true means that loop's latch
103 // has become unreachable from loop header.
104 bool DeleteCurrentLoop = false;
105
106 // The blocks of the original loop that will still be reachable from entry
107 // after the constant folding.
108 SmallPtrSet<BasicBlock *, 8> LiveLoopBlocks;
109 // The blocks of the original loop that will become unreachable from entry
110 // after the constant folding.
111 SmallVector<BasicBlock *, 8> DeadLoopBlocks;
112 // The exits of the original loop that will still be reachable from entry
113 // after the constant folding.
114 SmallPtrSet<BasicBlock *, 8> LiveExitBlocks;
115 // The exits of the original loop that will become unreachable from entry
116 // after the constant folding.
117 SmallVector<BasicBlock *, 8> DeadExitBlocks;
118 // The blocks that will still be a part of the current loop after folding.
119 SmallPtrSet<BasicBlock *, 8> BlocksInLoopAfterFolding;
120 // The blocks that have terminators with constant condition that can be
121 // folded. Note: fold candidates should be in L but not in any of its
122 // subloops to avoid complex LI updates.
123 SmallVector<BasicBlock *, 8> FoldCandidates;
124
dump() const125 void dump() const {
126 dbgs() << "Constant terminator folding for loop " << L << "\n";
127 dbgs() << "After terminator constant-folding, the loop will";
128 if (!DeleteCurrentLoop)
129 dbgs() << " not";
130 dbgs() << " be destroyed\n";
131 auto PrintOutVector = [&](const char *Message,
132 const SmallVectorImpl<BasicBlock *> &S) {
133 dbgs() << Message << "\n";
134 for (const BasicBlock *BB : S)
135 dbgs() << "\t" << BB->getName() << "\n";
136 };
137 auto PrintOutSet = [&](const char *Message,
138 const SmallPtrSetImpl<BasicBlock *> &S) {
139 dbgs() << Message << "\n";
140 for (const BasicBlock *BB : S)
141 dbgs() << "\t" << BB->getName() << "\n";
142 };
143 PrintOutVector("Blocks in which we can constant-fold terminator:",
144 FoldCandidates);
145 PrintOutSet("Live blocks from the original loop:", LiveLoopBlocks);
146 PrintOutVector("Dead blocks from the original loop:", DeadLoopBlocks);
147 PrintOutSet("Live exit blocks:", LiveExitBlocks);
148 PrintOutVector("Dead exit blocks:", DeadExitBlocks);
149 if (!DeleteCurrentLoop)
150 PrintOutSet("The following blocks will still be part of the loop:",
151 BlocksInLoopAfterFolding);
152 }
153
154 /// Whether or not the current loop has irreducible CFG.
hasIrreducibleCFG(LoopBlocksDFS & DFS)155 bool hasIrreducibleCFG(LoopBlocksDFS &DFS) {
156 assert(DFS.isComplete() && "DFS is expected to be finished");
157 // Index of a basic block in RPO traversal.
158 DenseMap<const BasicBlock *, unsigned> RPO;
159 unsigned Current = 0;
160 for (auto I = DFS.beginRPO(), E = DFS.endRPO(); I != E; ++I)
161 RPO[*I] = Current++;
162
163 for (auto I = DFS.beginRPO(), E = DFS.endRPO(); I != E; ++I) {
164 BasicBlock *BB = *I;
165 for (auto *Succ : successors(BB))
166 if (L.contains(Succ) && !LI.isLoopHeader(Succ) && RPO[BB] > RPO[Succ])
167 // If an edge goes from a block with greater order number into a block
168 // with lesses number, and it is not a loop backedge, then it can only
169 // be a part of irreducible non-loop cycle.
170 return true;
171 }
172 return false;
173 }
174
175 /// Fill all information about status of blocks and exits of the current loop
176 /// if constant folding of all branches will be done.
analyze()177 void analyze() {
178 LoopBlocksDFS DFS(&L);
179 DFS.perform(&LI);
180 assert(DFS.isComplete() && "DFS is expected to be finished");
181
182 // TODO: The algorithm below relies on both RPO and Postorder traversals.
183 // When the loop has only reducible CFG inside, then the invariant "all
184 // predecessors of X are processed before X in RPO" is preserved. However
185 // an irreducible loop can break this invariant (e.g. latch does not have to
186 // be the last block in the traversal in this case, and the algorithm relies
187 // on this). We can later decide to support such cases by altering the
188 // algorithms, but so far we just give up analyzing them.
189 if (hasIrreducibleCFG(DFS)) {
190 HasIrreducibleCFG = true;
191 return;
192 }
193
194 // Collect live and dead loop blocks and exits.
195 LiveLoopBlocks.insert(L.getHeader());
196 for (auto I = DFS.beginRPO(), E = DFS.endRPO(); I != E; ++I) {
197 BasicBlock *BB = *I;
198
199 // If a loop block wasn't marked as live so far, then it's dead.
200 if (!LiveLoopBlocks.count(BB)) {
201 DeadLoopBlocks.push_back(BB);
202 continue;
203 }
204
205 BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(BB);
206
207 // If a block has only one live successor, it's a candidate on constant
208 // folding. Only handle blocks from current loop: branches in child loops
209 // are skipped because if they can be folded, they should be folded during
210 // the processing of child loops.
211 if (TheOnlySucc && LI.getLoopFor(BB) == &L)
212 FoldCandidates.push_back(BB);
213
214 // Handle successors.
215 for (BasicBlock *Succ : successors(BB))
216 if (!TheOnlySucc || TheOnlySucc == Succ) {
217 if (L.contains(Succ))
218 LiveLoopBlocks.insert(Succ);
219 else
220 LiveExitBlocks.insert(Succ);
221 }
222 }
223
224 // Sanity check: amount of dead and live loop blocks should match the total
225 // number of blocks in loop.
226 assert(L.getNumBlocks() == LiveLoopBlocks.size() + DeadLoopBlocks.size() &&
227 "Malformed block sets?");
228
229 // Now, all exit blocks that are not marked as live are dead.
230 SmallVector<BasicBlock *, 8> ExitBlocks;
231 L.getExitBlocks(ExitBlocks);
232 for (auto *ExitBlock : ExitBlocks)
233 if (!LiveExitBlocks.count(ExitBlock))
234 DeadExitBlocks.push_back(ExitBlock);
235
236 // Whether or not the edge From->To will still be present in graph after the
237 // folding.
238 auto IsEdgeLive = [&](BasicBlock *From, BasicBlock *To) {
239 if (!LiveLoopBlocks.count(From))
240 return false;
241 BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(From);
242 return !TheOnlySucc || TheOnlySucc == To;
243 };
244
245 // The loop will not be destroyed if its latch is live.
246 DeleteCurrentLoop = !IsEdgeLive(L.getLoopLatch(), L.getHeader());
247
248 // If we are going to delete the current loop completely, no extra analysis
249 // is needed.
250 if (DeleteCurrentLoop)
251 return;
252
253 // Otherwise, we should check which blocks will still be a part of the
254 // current loop after the transform.
255 BlocksInLoopAfterFolding.insert(L.getLoopLatch());
256 // If the loop is live, then we should compute what blocks are still in
257 // loop after all branch folding has been done. A block is in loop if
258 // it has a live edge to another block that is in the loop; by definition,
259 // latch is in the loop.
260 auto BlockIsInLoop = [&](BasicBlock *BB) {
261 return any_of(successors(BB), [&](BasicBlock *Succ) {
262 return BlocksInLoopAfterFolding.count(Succ) && IsEdgeLive(BB, Succ);
263 });
264 };
265 for (auto I = DFS.beginPostorder(), E = DFS.endPostorder(); I != E; ++I) {
266 BasicBlock *BB = *I;
267 if (BlockIsInLoop(BB))
268 BlocksInLoopAfterFolding.insert(BB);
269 }
270
271 // Sanity check: header must be in loop.
272 assert(BlocksInLoopAfterFolding.count(L.getHeader()) &&
273 "Header not in loop?");
274 assert(BlocksInLoopAfterFolding.size() <= LiveLoopBlocks.size() &&
275 "All blocks that stay in loop should be live!");
276 }
277
278 /// We need to preserve static reachibility of all loop exit blocks (this is)
279 /// required by loop pass manager. In order to do it, we make the following
280 /// trick:
281 ///
282 /// preheader:
283 /// <preheader code>
284 /// br label %loop_header
285 ///
286 /// loop_header:
287 /// ...
288 /// br i1 false, label %dead_exit, label %loop_block
289 /// ...
290 ///
291 /// We cannot simply remove edge from the loop to dead exit because in this
292 /// case dead_exit (and its successors) may become unreachable. To avoid that,
293 /// we insert the following fictive preheader:
294 ///
295 /// preheader:
296 /// <preheader code>
297 /// switch i32 0, label %preheader-split,
298 /// [i32 1, label %dead_exit_1],
299 /// [i32 2, label %dead_exit_2],
300 /// ...
301 /// [i32 N, label %dead_exit_N],
302 ///
303 /// preheader-split:
304 /// br label %loop_header
305 ///
306 /// loop_header:
307 /// ...
308 /// br i1 false, label %dead_exit_N, label %loop_block
309 /// ...
310 ///
311 /// Doing so, we preserve static reachibility of all dead exits and can later
312 /// remove edges from the loop to these blocks.
handleDeadExits()313 void handleDeadExits() {
314 // If no dead exits, nothing to do.
315 if (DeadExitBlocks.empty())
316 return;
317
318 // Construct split preheader and the dummy switch to thread edges from it to
319 // dead exits.
320 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
321 BasicBlock *Preheader = L.getLoopPreheader();
322 BasicBlock *NewPreheader = Preheader->splitBasicBlock(
323 Preheader->getTerminator(),
324 Twine(Preheader->getName()).concat("-split"));
325 DTU.deleteEdge(Preheader, L.getHeader());
326 DTU.insertEdge(NewPreheader, L.getHeader());
327 DTU.insertEdge(Preheader, NewPreheader);
328 IRBuilder<> Builder(Preheader->getTerminator());
329 SwitchInst *DummySwitch =
330 Builder.CreateSwitch(Builder.getInt32(0), NewPreheader);
331 Preheader->getTerminator()->eraseFromParent();
332
333 unsigned DummyIdx = 1;
334 for (BasicBlock *BB : DeadExitBlocks) {
335 SmallVector<Instruction *, 4> DeadPhis;
336 for (auto &PN : BB->phis())
337 DeadPhis.push_back(&PN);
338
339 // Eliminate all Phis from dead exits.
340 for (Instruction *PN : DeadPhis) {
341 PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
342 PN->eraseFromParent();
343 }
344 assert(DummyIdx != 0 && "Too many dead exits!");
345 DummySwitch->addCase(Builder.getInt32(DummyIdx++), BB);
346 DTU.insertEdge(Preheader, BB);
347 ++NumLoopExitsDeleted;
348 }
349
350 assert(L.getLoopPreheader() == NewPreheader && "Malformed CFG?");
351 if (Loop *OuterLoop = LI.getLoopFor(Preheader)) {
352 OuterLoop->addBasicBlockToLoop(NewPreheader, LI);
353
354 // When we break dead edges, the outer loop may become unreachable from
355 // the current loop. We need to fix loop info accordingly. For this, we
356 // find the most nested loop that still contains L and remove L from all
357 // loops that are inside of it.
358 Loop *StillReachable = nullptr;
359 for (BasicBlock *BB : LiveExitBlocks) {
360 Loop *BBL = LI.getLoopFor(BB);
361 if (BBL && BBL->contains(L.getHeader()))
362 if (!StillReachable ||
363 BBL->getLoopDepth() > StillReachable->getLoopDepth())
364 StillReachable = BBL;
365 }
366
367 // Okay, our loop is no longer in the outer loop (and maybe not in some of
368 // its parents as well). Make the fixup.
369 if (StillReachable != OuterLoop) {
370 LI.changeLoopFor(NewPreheader, StillReachable);
371 for (Loop *NotContaining = OuterLoop; NotContaining != StillReachable;
372 NotContaining = NotContaining->getParentLoop()) {
373 NotContaining->removeBlockFromLoop(NewPreheader);
374 for (auto *BB : L.blocks())
375 NotContaining->removeBlockFromLoop(BB);
376 }
377 OuterLoop->removeChildLoop(&L);
378 if (StillReachable)
379 StillReachable->addChildLoop(&L);
380 else
381 LI.addTopLevelLoop(&L);
382 }
383 }
384 }
385
386 /// Delete loop blocks that have become unreachable after folding. Make all
387 /// relevant updates to DT and LI.
deleteDeadLoopBlocks()388 void deleteDeadLoopBlocks() {
389 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
390 if (MSSAU) {
391 SmallPtrSet<BasicBlock *, 8> DeadLoopBlocksSet(DeadLoopBlocks.begin(),
392 DeadLoopBlocks.end());
393 MSSAU->removeBlocks(DeadLoopBlocksSet);
394 }
395 for (auto *BB : DeadLoopBlocks) {
396 assert(BB != L.getHeader() &&
397 "Header of the current loop cannot be dead!");
398 LLVM_DEBUG(dbgs() << "Deleting dead loop block " << BB->getName()
399 << "\n");
400 if (LI.isLoopHeader(BB)) {
401 assert(LI.getLoopFor(BB) != &L && "Attempt to remove current loop!");
402 LI.erase(LI.getLoopFor(BB));
403 }
404 LI.removeBlock(BB);
405 DeleteDeadBlock(BB, &DTU);
406 ++NumLoopBlocksDeleted;
407 }
408 }
409
410 /// Constant-fold terminators of blocks acculumated in FoldCandidates into the
411 /// unconditional branches.
foldTerminators()412 void foldTerminators() {
413 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
414
415 for (BasicBlock *BB : FoldCandidates) {
416 assert(LI.getLoopFor(BB) == &L && "Should be a loop block!");
417 BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(BB);
418 assert(TheOnlySucc && "Should have one live successor!");
419
420 LLVM_DEBUG(dbgs() << "Replacing terminator of " << BB->getName()
421 << " with an unconditional branch to the block "
422 << TheOnlySucc->getName() << "\n");
423
424 SmallPtrSet<BasicBlock *, 2> DeadSuccessors;
425 // Remove all BB's successors except for the live one.
426 unsigned TheOnlySuccDuplicates = 0;
427 for (auto *Succ : successors(BB))
428 if (Succ != TheOnlySucc) {
429 DeadSuccessors.insert(Succ);
430 // If our successor lies in a different loop, we don't want to remove
431 // the one-input Phi because it is a LCSSA Phi.
432 bool PreserveLCSSAPhi = !L.contains(Succ);
433 Succ->removePredecessor(BB, PreserveLCSSAPhi);
434 if (MSSAU)
435 MSSAU->removeEdge(BB, Succ);
436 } else
437 ++TheOnlySuccDuplicates;
438
439 assert(TheOnlySuccDuplicates > 0 && "Should be!");
440 // If TheOnlySucc was BB's successor more than once, after transform it
441 // will be its successor only once. Remove redundant inputs from
442 // TheOnlySucc's Phis.
443 bool PreserveLCSSAPhi = !L.contains(TheOnlySucc);
444 for (unsigned Dup = 1; Dup < TheOnlySuccDuplicates; ++Dup)
445 TheOnlySucc->removePredecessor(BB, PreserveLCSSAPhi);
446 if (MSSAU && TheOnlySuccDuplicates > 1)
447 MSSAU->removeDuplicatePhiEdgesBetween(BB, TheOnlySucc);
448
449 IRBuilder<> Builder(BB->getContext());
450 Instruction *Term = BB->getTerminator();
451 Builder.SetInsertPoint(Term);
452 Builder.CreateBr(TheOnlySucc);
453 Term->eraseFromParent();
454
455 for (auto *DeadSucc : DeadSuccessors)
456 DTU.deleteEdge(BB, DeadSucc);
457
458 ++NumTerminatorsFolded;
459 }
460 }
461
462 public:
ConstantTerminatorFoldingImpl(Loop & L,LoopInfo & LI,DominatorTree & DT,ScalarEvolution & SE,MemorySSAUpdater * MSSAU)463 ConstantTerminatorFoldingImpl(Loop &L, LoopInfo &LI, DominatorTree &DT,
464 ScalarEvolution &SE,
465 MemorySSAUpdater *MSSAU)
466 : L(L), LI(LI), DT(DT), SE(SE), MSSAU(MSSAU) {}
run()467 bool run() {
468 assert(L.getLoopLatch() && "Should be single latch!");
469
470 // Collect all available information about status of blocks after constant
471 // folding.
472 analyze();
473
474 LLVM_DEBUG(dbgs() << "In function " << L.getHeader()->getParent()->getName()
475 << ": ");
476
477 if (HasIrreducibleCFG) {
478 LLVM_DEBUG(dbgs() << "Loops with irreducible CFG are not supported!\n");
479 return false;
480 }
481
482 // Nothing to constant-fold.
483 if (FoldCandidates.empty()) {
484 LLVM_DEBUG(
485 dbgs() << "No constant terminator folding candidates found in loop "
486 << L.getHeader()->getName() << "\n");
487 return false;
488 }
489
490 // TODO: Support deletion of the current loop.
491 if (DeleteCurrentLoop) {
492 LLVM_DEBUG(
493 dbgs()
494 << "Give up constant terminator folding in loop "
495 << L.getHeader()->getName()
496 << ": we don't currently support deletion of the current loop.\n");
497 return false;
498 }
499
500 // TODO: Support blocks that are not dead, but also not in loop after the
501 // folding.
502 if (BlocksInLoopAfterFolding.size() + DeadLoopBlocks.size() !=
503 L.getNumBlocks()) {
504 LLVM_DEBUG(
505 dbgs() << "Give up constant terminator folding in loop "
506 << L.getHeader()->getName()
507 << ": we don't currently"
508 " support blocks that are not dead, but will stop "
509 "being a part of the loop after constant-folding.\n");
510 return false;
511 }
512
513 SE.forgetTopmostLoop(&L);
514 // Dump analysis results.
515 LLVM_DEBUG(dump());
516
517 LLVM_DEBUG(dbgs() << "Constant-folding " << FoldCandidates.size()
518 << " terminators in loop " << L.getHeader()->getName()
519 << "\n");
520
521 // Make the actual transforms.
522 handleDeadExits();
523 foldTerminators();
524
525 if (!DeadLoopBlocks.empty()) {
526 LLVM_DEBUG(dbgs() << "Deleting " << DeadLoopBlocks.size()
527 << " dead blocks in loop " << L.getHeader()->getName()
528 << "\n");
529 deleteDeadLoopBlocks();
530 }
531
532 #ifndef NDEBUG
533 // Make sure that we have preserved all data structures after the transform.
534 DT.verify();
535 assert(DT.isReachableFromEntry(L.getHeader()));
536 LI.verify(DT);
537 #endif
538
539 return true;
540 }
541 };
542 } // namespace
543
544 /// Turn branches and switches with known constant conditions into unconditional
545 /// branches.
constantFoldTerminators(Loop & L,DominatorTree & DT,LoopInfo & LI,ScalarEvolution & SE,MemorySSAUpdater * MSSAU)546 static bool constantFoldTerminators(Loop &L, DominatorTree &DT, LoopInfo &LI,
547 ScalarEvolution &SE,
548 MemorySSAUpdater *MSSAU) {
549 if (!EnableTermFolding)
550 return false;
551
552 // To keep things simple, only process loops with single latch. We
553 // canonicalize most loops to this form. We can support multi-latch if needed.
554 if (!L.getLoopLatch())
555 return false;
556
557 ConstantTerminatorFoldingImpl BranchFolder(L, LI, DT, SE, MSSAU);
558 return BranchFolder.run();
559 }
560
mergeBlocksIntoPredecessors(Loop & L,DominatorTree & DT,LoopInfo & LI,MemorySSAUpdater * MSSAU)561 static bool mergeBlocksIntoPredecessors(Loop &L, DominatorTree &DT,
562 LoopInfo &LI, MemorySSAUpdater *MSSAU) {
563 bool Changed = false;
564 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
565 // Copy blocks into a temporary array to avoid iterator invalidation issues
566 // as we remove them.
567 SmallVector<WeakTrackingVH, 16> Blocks(L.blocks());
568
569 for (auto &Block : Blocks) {
570 // Attempt to merge blocks in the trivial case. Don't modify blocks which
571 // belong to other loops.
572 BasicBlock *Succ = cast_or_null<BasicBlock>(Block);
573 if (!Succ)
574 continue;
575
576 BasicBlock *Pred = Succ->getSinglePredecessor();
577 if (!Pred || !Pred->getSingleSuccessor() || LI.getLoopFor(Pred) != &L)
578 continue;
579
580 // Merge Succ into Pred and delete it.
581 MergeBlockIntoPredecessor(Succ, &DTU, &LI, MSSAU);
582
583 Changed = true;
584 }
585
586 return Changed;
587 }
588
simplifyLoopCFG(Loop & L,DominatorTree & DT,LoopInfo & LI,ScalarEvolution & SE,MemorySSAUpdater * MSSAU)589 static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI,
590 ScalarEvolution &SE, MemorySSAUpdater *MSSAU) {
591 bool Changed = false;
592
593 // Constant-fold terminators with known constant conditions.
594 Changed |= constantFoldTerminators(L, DT, LI, SE, MSSAU);
595
596 // Eliminate unconditional branches by merging blocks into their predecessors.
597 Changed |= mergeBlocksIntoPredecessors(L, DT, LI, MSSAU);
598
599 if (Changed)
600 SE.forgetTopmostLoop(&L);
601
602 return Changed;
603 }
604
run(Loop & L,LoopAnalysisManager & AM,LoopStandardAnalysisResults & AR,LPMUpdater &)605 PreservedAnalyses LoopSimplifyCFGPass::run(Loop &L, LoopAnalysisManager &AM,
606 LoopStandardAnalysisResults &AR,
607 LPMUpdater &) {
608 Optional<MemorySSAUpdater> MSSAU;
609 if (EnableMSSALoopDependency && AR.MSSA)
610 MSSAU = MemorySSAUpdater(AR.MSSA);
611 if (!simplifyLoopCFG(L, AR.DT, AR.LI, AR.SE,
612 MSSAU.hasValue() ? MSSAU.getPointer() : nullptr))
613 return PreservedAnalyses::all();
614
615 return getLoopPassPreservedAnalyses();
616 }
617
618 namespace {
619 class LoopSimplifyCFGLegacyPass : public LoopPass {
620 public:
621 static char ID; // Pass ID, replacement for typeid
LoopSimplifyCFGLegacyPass()622 LoopSimplifyCFGLegacyPass() : LoopPass(ID) {
623 initializeLoopSimplifyCFGLegacyPassPass(*PassRegistry::getPassRegistry());
624 }
625
runOnLoop(Loop * L,LPPassManager &)626 bool runOnLoop(Loop *L, LPPassManager &) override {
627 if (skipLoop(L))
628 return false;
629
630 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
631 LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
632 ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
633 Optional<MemorySSAUpdater> MSSAU;
634 if (EnableMSSALoopDependency) {
635 MemorySSA *MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
636 MSSAU = MemorySSAUpdater(MSSA);
637 if (VerifyMemorySSA)
638 MSSA->verifyMemorySSA();
639 }
640 return simplifyLoopCFG(*L, DT, LI, SE,
641 MSSAU.hasValue() ? MSSAU.getPointer() : nullptr);
642 }
643
getAnalysisUsage(AnalysisUsage & AU) const644 void getAnalysisUsage(AnalysisUsage &AU) const override {
645 if (EnableMSSALoopDependency) {
646 AU.addRequired<MemorySSAWrapperPass>();
647 AU.addPreserved<MemorySSAWrapperPass>();
648 }
649 AU.addPreserved<DependenceAnalysisWrapperPass>();
650 getLoopAnalysisUsage(AU);
651 }
652 };
653 }
654
655 char LoopSimplifyCFGLegacyPass::ID = 0;
656 INITIALIZE_PASS_BEGIN(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
657 "Simplify loop CFG", false, false)
INITIALIZE_PASS_DEPENDENCY(LoopPass)658 INITIALIZE_PASS_DEPENDENCY(LoopPass)
659 INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
660 INITIALIZE_PASS_END(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
661 "Simplify loop CFG", false, false)
662
663 Pass *llvm::createLoopSimplifyCFGPass() {
664 return new LoopSimplifyCFGLegacyPass();
665 }
666