Coverage Report

Created: 2019-07-24 05:18

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