Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Scalar/LoopFuse.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- LoopFuse.cpp - Loop Fusion 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
/// \file
10
/// This file implements the loop fusion pass.
11
/// The implementation is largely based on the following document:
12
///
13
///       Code Transformations to Augment the Scope of Loop Fusion in a
14
///         Production Compiler
15
///       Christopher Mark Barton
16
///       MSc Thesis
17
///       https://webdocs.cs.ualberta.ca/~amaral/thesis/ChristopherBartonMSc.pdf
18
///
19
/// The general approach taken is to collect sets of control flow equivalent
20
/// loops and test whether they can be fused. The necessary conditions for
21
/// fusion are:
22
///    1. The loops must be adjacent (there cannot be any statements between
23
///       the two loops).
24
///    2. The loops must be conforming (they must execute the same number of
25
///       iterations).
26
///    3. The loops must be control flow equivalent (if one loop executes, the
27
///       other is guaranteed to execute).
28
///    4. There cannot be any negative distance dependencies between the loops.
29
/// If all of these conditions are satisfied, it is safe to fuse the loops.
30
///
31
/// This implementation creates FusionCandidates that represent the loop and the
32
/// necessary information needed by fusion. It then operates on the fusion
33
/// candidates, first confirming that the candidate is eligible for fusion. The
34
/// candidates are then collected into control flow equivalent sets, sorted in
35
/// dominance order. Each set of control flow equivalent candidates is then
36
/// traversed, attempting to fuse pairs of candidates in the set. If all
37
/// requirements for fusion are met, the two candidates are fused, creating a
38
/// new (fused) candidate which is then added back into the set to consider for
39
/// additional fusion.
40
///
41
/// This implementation currently does not make any modifications to remove
42
/// conditions for fusion. Code transformations to make loops conform to each of
43
/// the conditions for fusion are discussed in more detail in the document
44
/// above. These can be added to the current implementation in the future.
45
//===----------------------------------------------------------------------===//
46
47
#include "llvm/Transforms/Scalar/LoopFuse.h"
48
#include "llvm/ADT/Statistic.h"
49
#include "llvm/Analysis/DependenceAnalysis.h"
50
#include "llvm/Analysis/DomTreeUpdater.h"
51
#include "llvm/Analysis/LoopInfo.h"
52
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
53
#include "llvm/Analysis/PostDominators.h"
54
#include "llvm/Analysis/ScalarEvolution.h"
55
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
56
#include "llvm/IR/Function.h"
57
#include "llvm/IR/Verifier.h"
58
#include "llvm/Pass.h"
59
#include "llvm/Support/Debug.h"
60
#include "llvm/Support/raw_ostream.h"
61
#include "llvm/Transforms/Scalar.h"
62
#include "llvm/Transforms/Utils.h"
63
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
64
65
using namespace llvm;
66
67
10
#define DEBUG_TYPE "loop-fusion"
68
69
STATISTIC(FuseCounter, "Count number of loop fusions performed");
70
STATISTIC(NumFusionCandidates, "Number of candidates for loop fusion");
71
STATISTIC(InvalidPreheader, "Loop has invalid preheader");
72
STATISTIC(InvalidHeader, "Loop has invalid header");
73
STATISTIC(InvalidExitingBlock, "Loop has invalid exiting blocks");
74
STATISTIC(InvalidExitBlock, "Loop has invalid exit block");
75
STATISTIC(InvalidLatch, "Loop has invalid latch");
76
STATISTIC(InvalidLoop, "Loop is invalid");
77
STATISTIC(AddressTakenBB, "Basic block has address taken");
78
STATISTIC(MayThrowException, "Loop may throw an exception");
79
STATISTIC(ContainsVolatileAccess, "Loop contains a volatile access");
80
STATISTIC(NotSimplifiedForm, "Loop is not in simplified form");
81
STATISTIC(InvalidDependencies, "Dependencies prevent fusion");
82
STATISTIC(InvalidTripCount,
83
          "Loop does not have invariant backedge taken count");
84
STATISTIC(UncomputableTripCount, "SCEV cannot compute trip count of loop");
85
STATISTIC(NonEqualTripCount, "Candidate trip counts are not the same");
86
STATISTIC(NonAdjacent, "Candidates are not adjacent");
87
STATISTIC(NonEmptyPreheader, "Candidate has a non-empty preheader");
88
89
enum FusionDependenceAnalysisChoice {
90
  FUSION_DEPENDENCE_ANALYSIS_SCEV,
91
  FUSION_DEPENDENCE_ANALYSIS_DA,
92
  FUSION_DEPENDENCE_ANALYSIS_ALL,
93
};
94
95
static cl::opt<FusionDependenceAnalysisChoice> FusionDependenceAnalysis(
96
    "loop-fusion-dependence-analysis",
97
    cl::desc("Which dependence analysis should loop fusion use?"),
98
    cl::values(clEnumValN(FUSION_DEPENDENCE_ANALYSIS_SCEV, "scev",
99
                          "Use the scalar evolution interface"),
100
               clEnumValN(FUSION_DEPENDENCE_ANALYSIS_DA, "da",
101
                          "Use the dependence analysis interface"),
102
               clEnumValN(FUSION_DEPENDENCE_ANALYSIS_ALL, "all",
103
                          "Use all available analyses")),
104
    cl::Hidden, cl::init(FUSION_DEPENDENCE_ANALYSIS_ALL), cl::ZeroOrMore);
105
106
#ifndef NDEBUG
107
static cl::opt<bool>
108
    VerboseFusionDebugging("loop-fusion-verbose-debug",
109
                           cl::desc("Enable verbose debugging for Loop Fusion"),
110
                           cl::Hidden, cl::init(false), cl::ZeroOrMore);
111
#endif
112
113
/// This class is used to represent a candidate for loop fusion. When it is
114
/// constructed, it checks the conditions for loop fusion to ensure that it
115
/// represents a valid candidate. It caches several parts of a loop that are
116
/// used throughout loop fusion (e.g., loop preheader, loop header, etc) instead
117
/// of continually querying the underlying Loop to retrieve these values. It is
118
/// assumed these will not change throughout loop fusion.
119
///
120
/// The invalidate method should be used to indicate that the FusionCandidate is
121
/// no longer a valid candidate for fusion. Similarly, the isValid() method can
122
/// be used to ensure that the FusionCandidate is still valid for fusion.
123
struct FusionCandidate {
124
  /// Cache of parts of the loop used throughout loop fusion. These should not
125
  /// need to change throughout the analysis and transformation.
126
  /// These parts are cached to avoid repeatedly looking up in the Loop class.
127
128
  /// Preheader of the loop this candidate represents
129
  BasicBlock *Preheader;
130
  /// Header of the loop this candidate represents
131
  BasicBlock *Header;
132
  /// Blocks in the loop that exit the loop
133
  BasicBlock *ExitingBlock;
134
  /// The successor block of this loop (where the exiting blocks go to)
135
  BasicBlock *ExitBlock;
136
  /// Latch of the loop
137
  BasicBlock *Latch;
138
  /// The loop that this fusion candidate represents
139
  Loop *L;
140
  /// Vector of instructions in this loop that read from memory
141
  SmallVector<Instruction *, 16> MemReads;
142
  /// Vector of instructions in this loop that write to memory
143
  SmallVector<Instruction *, 16> MemWrites;
144
  /// Are all of the members of this fusion candidate still valid
145
  bool Valid;
146
147
  /// Dominator and PostDominator trees are needed for the
148
  /// FusionCandidateCompare function, required by FusionCandidateSet to
149
  /// determine where the FusionCandidate should be inserted into the set. These
150
  /// are used to establish ordering of the FusionCandidates based on dominance.
151
  const DominatorTree *DT;
152
  const PostDominatorTree *PDT;
153
154
  FusionCandidate(Loop *L, const DominatorTree *DT,
155
                  const PostDominatorTree *PDT)
156
      : Preheader(L->getLoopPreheader()), Header(L->getHeader()),
157
        ExitingBlock(L->getExitingBlock()), ExitBlock(L->getExitBlock()),
158
30
        Latch(L->getLoopLatch()), L(L), Valid(true), DT(DT), PDT(PDT) {
159
30
160
30
    // Walk over all blocks in the loop and check for conditions that may
161
30
    // prevent fusion. For each block, walk over all instructions and collect
162
30
    // the memory reads and writes If any instructions that prevent fusion are
163
30
    // found, invalidate this object and return.
164
141
    for (BasicBlock *BB : L->blocks()) {
165
141
      if (BB->hasAddressTaken()) {
166
0
        AddressTakenBB++;
167
0
        invalidate();
168
0
        return;
169
0
      }
170
141
171
666
      
for (Instruction &I : *BB)141
{
172
666
        if (I.mayThrow()) {
173
0
          MayThrowException++;
174
0
          invalidate();
175
0
          return;
176
0
        }
177
666
        if (StoreInst *SI = dyn_cast<StoreInst>(&I)) {
178
43
          if (SI->isVolatile()) {
179
0
            ContainsVolatileAccess++;
180
0
            invalidate();
181
0
            return;
182
0
          }
183
666
        }
184
666
        if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
185
6
          if (LI->isVolatile()) {
186
0
            ContainsVolatileAccess++;
187
0
            invalidate();
188
0
            return;
189
0
          }
190
666
        }
191
666
        if (I.mayWriteToMemory())
192
43
          MemWrites.push_back(&I);
193
666
        if (I.mayReadFromMemory())
194
6
          MemReads.push_back(&I);
195
666
      }
196
141
    }
197
30
  }
198
199
  /// Check if all members of the class are valid.
200
20
  bool isValid() const {
201
20
    return Preheader && Header && ExitingBlock && ExitBlock && Latch && L &&
202
20
           !L->isInvalid() && Valid;
203
20
  }
204
205
  /// Verify that all members are in sync with the Loop object.
206
30
  void verify() const {
207
30
    assert(isValid() && "Candidate is not valid!!");
208
30
    assert(!L->isInvalid() && "Loop is invalid!");
209
30
    assert(Preheader == L->getLoopPreheader() && "Preheader is out of sync");
210
30
    assert(Header == L->getHeader() && "Header is out of sync");
211
30
    assert(ExitingBlock == L->getExitingBlock() &&
212
30
           "Exiting Blocks is out of sync");
213
30
    assert(ExitBlock == L->getExitBlock() && "Exit block is out of sync");
214
30
    assert(Latch == L->getLoopLatch() && "Latch is out of sync");
215
30
  }
216
217
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
218
  LLVM_DUMP_METHOD void dump() const {
219
    dbgs() << "\tPreheader: " << (Preheader ? Preheader->getName() : "nullptr")
220
           << "\n"
221
           << "\tHeader: " << (Header ? Header->getName() : "nullptr") << "\n"
222
           << "\tExitingBB: "
223
           << (ExitingBlock ? ExitingBlock->getName() : "nullptr") << "\n"
224
           << "\tExitBB: " << (ExitBlock ? ExitBlock->getName() : "nullptr")
225
           << "\n"
226
           << "\tLatch: " << (Latch ? Latch->getName() : "nullptr") << "\n";
227
  }
228
#endif
229
230
private:
231
  // This is only used internally for now, to clear the MemWrites and MemReads
232
  // list and setting Valid to false. I can't envision other uses of this right
233
  // now, since once FusionCandidates are put into the FusionCandidateSet they
234
  // are immutable. Thus, any time we need to change/update a FusionCandidate,
235
  // we must create a new one and insert it into the FusionCandidateSet to
236
  // ensure the FusionCandidateSet remains ordered correctly.
237
0
  void invalidate() {
238
0
    MemWrites.clear();
239
0
    MemReads.clear();
240
0
    Valid = false;
241
0
  }
242
};
243
244
inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
245
0
                                     const FusionCandidate &FC) {
246
0
  if (FC.isValid())
247
0
    OS << FC.Preheader->getName();
248
0
  else
249
0
    OS << "<Invalid>";
250
0
251
0
  return OS;
252
0
}
253
254
struct FusionCandidateCompare {
255
  /// Comparison functor to sort two Control Flow Equivalent fusion candidates
256
  /// into dominance order.
257
  /// If LHS dominates RHS and RHS post-dominates LHS, return true;
258
  /// IF RHS dominates LHS and LHS post-dominates RHS, return false;
259
  bool operator()(const FusionCandidate &LHS,
260
26
                  const FusionCandidate &RHS) const {
261
26
    const DominatorTree *DT = LHS.DT;
262
26
263
26
    // Do not save PDT to local variable as it is only used in asserts and thus
264
26
    // will trigger an unused variable warning if building without asserts.
265
26
    assert(DT && LHS.PDT && "Expecting valid dominator tree");
266
26
267
26
    // Do this compare first so if LHS == RHS, function returns false.
268
26
    if (DT->dominates(RHS.Preheader, LHS.Preheader)) {
269
12
      // RHS dominates LHS
270
12
      // Verify LHS post-dominates RHS
271
12
      assert(LHS.PDT->dominates(LHS.Preheader, RHS.Preheader));
272
12
      return false;
273
12
    }
274
14
275
14
    if (DT->dominates(LHS.Preheader, RHS.Preheader)) {
276
14
      // Verify RHS Postdominates LHS
277
14
      assert(LHS.PDT->dominates(RHS.Preheader, LHS.Preheader));
278
14
      return true;
279
14
    }
280
0
281
0
    // If LHS does not dominate RHS and RHS does not dominate LHS then there is
282
0
    // no dominance relationship between the two FusionCandidates. Thus, they
283
0
    // should not be in the same set together.
284
0
    llvm_unreachable(
285
0
        "No dominance relationship between these fusion candidates!");
286
0
  }
287
};
288
289
namespace {
290
using LoopVector = SmallVector<Loop *, 4>;
291
292
// Set of Control Flow Equivalent (CFE) Fusion Candidates, sorted in dominance
293
// order. Thus, if FC0 comes *before* FC1 in a FusionCandidateSet, then FC0
294
// dominates FC1 and FC1 post-dominates FC0.
295
// std::set was chosen because we want a sorted data structure with stable
296
// iterators. A subsequent patch to loop fusion will enable fusing non-ajdacent
297
// loops by moving intervening code around. When this intervening code contains
298
// loops, those loops will be moved also. The corresponding FusionCandidates
299
// will also need to be moved accordingly. As this is done, having stable
300
// iterators will simplify the logic. Similarly, having an efficient insert that
301
// keeps the FusionCandidateSet sorted will also simplify the implementation.
302
using FusionCandidateSet = std::set<FusionCandidate, FusionCandidateCompare>;
303
using FusionCandidateCollection = SmallVector<FusionCandidateSet, 4>;
304
} // namespace
305
306
inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
307
0
                                     const FusionCandidateSet &CandSet) {
308
0
  for (auto IT : CandSet)
309
0
    OS << IT << "\n";
310
0
311
0
  return OS;
312
0
}
313
314
#if !defined(NDEBUG)
315
static void
316
printFusionCandidates(const FusionCandidateCollection &FusionCandidates) {
317
  dbgs() << "Fusion Candidates: \n";
318
  for (const auto &CandidateSet : FusionCandidates) {
319
    dbgs() << "*** Fusion Candidate Set ***\n";
320
    dbgs() << CandidateSet;
321
    dbgs() << "****************************\n";
322
  }
323
}
324
#endif
325
326
/// Collect all loops in function at the same nest level, starting at the
327
/// outermost level.
328
///
329
/// This data structure collects all loops at the same nest level for a
330
/// given function (specified by the LoopInfo object). It starts at the
331
/// outermost level.
332
struct LoopDepthTree {
333
  using LoopsOnLevelTy = SmallVector<LoopVector, 4>;
334
  using iterator = LoopsOnLevelTy::iterator;
335
  using const_iterator = LoopsOnLevelTy::const_iterator;
336
337
8
  LoopDepthTree(LoopInfo &LI) : Depth(1) {
338
8
    if (!LI.empty())
339
8
      LoopsOnLevel.emplace_back(LoopVector(LI.rbegin(), LI.rend()));
340
8
  }
341
342
  /// Test whether a given loop has been removed from the function, and thus is
343
  /// no longer valid.
344
21
  bool isRemovedLoop(const Loop *L) const { return RemovedLoops.count(L); }
345
346
  /// Record that a given loop has been removed from the function and is no
347
  /// longer valid.
348
10
  void removeLoop(const Loop *L) { RemovedLoops.insert(L); }
349
350
  /// Descend the tree to the next (inner) nesting level
351
10
  void descend() {
352
10
    LoopsOnLevelTy LoopsOnNextLevel;
353
10
354
10
    for (const LoopVector &LV : *this)
355
10
      for (Loop *L : LV)
356
21
        if (!isRemovedLoop(L) && 
L->begin() != L->end()11
)
357
2
          LoopsOnNextLevel.emplace_back(LoopVector(L->begin(), L->end()));
358
10
359
10
    LoopsOnLevel = LoopsOnNextLevel;
360
10
    RemovedLoops.clear();
361
10
    Depth++;
362
10
  }
363
364
18
  bool empty() const { return size() == 0; }
365
18
  size_t size() const { return LoopsOnLevel.size() - RemovedLoops.size(); }
366
0
  unsigned getDepth() const { return Depth; }
367
368
20
  iterator begin() { return LoopsOnLevel.begin(); }
369
20
  iterator end() { return LoopsOnLevel.end(); }
370
0
  const_iterator begin() const { return LoopsOnLevel.begin(); }
371
0
  const_iterator end() const { return LoopsOnLevel.end(); }
372
373
private:
374
  /// Set of loops that have been removed from the function and are no longer
375
  /// valid.
376
  SmallPtrSet<const Loop *, 8> RemovedLoops;
377
378
  /// Depth of the current level, starting at 1 (outermost loops).
379
  unsigned Depth;
380
381
  /// Vector of loops at the current depth level that have the same parent loop
382
  LoopsOnLevelTy LoopsOnLevel;
383
};
384
385
#ifndef NDEBUG
386
static void printLoopVector(const LoopVector &LV) {
387
  dbgs() << "****************************\n";
388
  for (auto L : LV)
389
    printLoop(*L, dbgs());
390
  dbgs() << "****************************\n";
391
}
392
#endif
393
394
static void reportLoopFusion(const FusionCandidate &FC0,
395
                             const FusionCandidate &FC1,
396
10
                             OptimizationRemarkEmitter &ORE) {
397
10
  using namespace ore;
398
10
  ORE.emit(
399
10
      OptimizationRemark(DEBUG_TYPE, "LoopFusion", FC0.Preheader->getParent())
400
10
      << "Fused " << NV("Cand1", StringRef(FC0.Preheader->getName()))
401
10
      << " with " << NV("Cand2", StringRef(FC1.Preheader->getName())));
402
10
}
403
404
struct LoopFuser {
405
private:
406
  // Sets of control flow equivalent fusion candidates for a given nest level.
407
  FusionCandidateCollection FusionCandidates;
408
409
  LoopDepthTree LDT;
410
  DomTreeUpdater DTU;
411
412
  LoopInfo &LI;
413
  DominatorTree &DT;
414
  DependenceInfo &DI;
415
  ScalarEvolution &SE;
416
  PostDominatorTree &PDT;
417
  OptimizationRemarkEmitter &ORE;
418
419
public:
420
  LoopFuser(LoopInfo &LI, DominatorTree &DT, DependenceInfo &DI,
421
            ScalarEvolution &SE, PostDominatorTree &PDT,
422
            OptimizationRemarkEmitter &ORE, const DataLayout &DL)
423
      : LDT(LI), DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy), LI(LI),
424
8
        DT(DT), DI(DI), SE(SE), PDT(PDT), ORE(ORE) {}
425
426
  /// This is the main entry point for loop fusion. It will traverse the
427
  /// specified function and collect candidate loops to fuse, starting at the
428
  /// outermost nesting level and working inwards.
429
8
  bool fuseLoops(Function &F) {
430
#ifndef NDEBUG
431
    if (VerboseFusionDebugging) {
432
      LI.print(dbgs());
433
    }
434
#endif
435
436
8
    LLVM_DEBUG(dbgs() << "Performing Loop Fusion on function " << F.getName()
437
8
                      << "\n");
438
8
    bool Changed = false;
439
8
440
18
    while (!LDT.empty()) {
441
10
      LLVM_DEBUG(dbgs() << "Got " << LDT.size() << " loop sets for depth "
442
10
                        << LDT.getDepth() << "\n";);
443
10
444
10
      for (const LoopVector &LV : LDT) {
445
10
        assert(LV.size() > 0 && "Empty loop set was build!");
446
10
447
10
        // Skip singleton loop sets as they do not offer fusion opportunities on
448
10
        // this level.
449
10
        if (LV.size() == 1)
450
1
          continue;
451
#ifndef NDEBUG
452
        if (VerboseFusionDebugging) {
453
          LLVM_DEBUG({
454
            dbgs() << "  Visit loop set (#" << LV.size() << "):\n";
455
            printLoopVector(LV);
456
          });
457
        }
458
#endif
459
460
9
        collectFusionCandidates(LV);
461
9
        Changed |= fuseCandidates();
462
9
      }
463
10
464
10
      // Finished analyzing candidates at this level.
465
10
      // Descend to the next level and clear all of the candidates currently
466
10
      // collected. Note that it will not be possible to fuse any of the
467
10
      // existing candidates with new candidates because the new candidates will
468
10
      // be at a different nest level and thus not be control flow equivalent
469
10
      // with all of the candidates collected so far.
470
10
      LLVM_DEBUG(dbgs() << "Descend one level!\n");
471
10
      LDT.descend();
472
10
      FusionCandidates.clear();
473
10
    }
474
8
475
8
    if (Changed)
476
8
      LLVM_DEBUG(dbgs() << "Function after Loop Fusion: \n"; F.dump(););
477
8
478
#ifndef NDEBUG
479
    assert(DT.verify());
480
    assert(PDT.verify());
481
    LI.verify(DT);
482
    SE.verify();
483
#endif
484
485
8
    LLVM_DEBUG(dbgs() << "Loop Fusion complete\n");
486
8
    return Changed;
487
8
  }
488
489
private:
490
  /// Determine if two fusion candidates are control flow equivalent.
491
  ///
492
  /// Two fusion candidates are control flow equivalent if when one executes,
493
  /// the other is guaranteed to execute. This is determined using dominators
494
  /// and post-dominators: if A dominates B and B post-dominates A then A and B
495
  /// are control-flow equivalent.
496
  bool isControlFlowEquivalent(const FusionCandidate &FC0,
497
11
                               const FusionCandidate &FC1) const {
498
11
    assert(FC0.Preheader && FC1.Preheader && "Expecting valid preheaders");
499
11
500
11
    if (DT.dominates(FC0.Preheader, FC1.Preheader))
501
10
      return PDT.dominates(FC1.Preheader, FC0.Preheader);
502
1
503
1
    if (DT.dominates(FC1.Preheader, FC0.Preheader))
504
0
      return PDT.dominates(FC0.Preheader, FC1.Preheader);
505
1
506
1
    return false;
507
1
  }
508
509
  /// Determine if a fusion candidate (representing a loop) is eligible for
510
  /// fusion. Note that this only checks whether a single loop can be fused - it
511
  /// does not check whether it is *legal* to fuse two loops together.
512
20
  bool eligibleForFusion(const FusionCandidate &FC) const {
513
20
    if (!FC.isValid()) {
514
0
      LLVM_DEBUG(dbgs() << "FC " << FC << " has invalid CFG requirements!\n");
515
0
      if (!FC.Preheader)
516
0
        InvalidPreheader++;
517
0
      if (!FC.Header)
518
0
        InvalidHeader++;
519
0
      if (!FC.ExitingBlock)
520
0
        InvalidExitingBlock++;
521
0
      if (!FC.ExitBlock)
522
0
        InvalidExitBlock++;
523
0
      if (!FC.Latch)
524
0
        InvalidLatch++;
525
0
      if (FC.L->isInvalid())
526
0
        InvalidLoop++;
527
0
528
0
      return false;
529
0
    }
530
20
531
20
    // Require ScalarEvolution to be able to determine a trip count.
532
20
    if (!SE.hasLoopInvariantBackedgeTakenCount(FC.L)) {
533
0
      LLVM_DEBUG(dbgs() << "Loop " << FC.L->getName()
534
0
                        << " trip count not computable!\n");
535
0
      InvalidTripCount++;
536
0
      return false;
537
0
    }
538
20
539
20
    if (!FC.L->isLoopSimplifyForm()) {
540
0
      LLVM_DEBUG(dbgs() << "Loop " << FC.L->getName()
541
0
                        << " is not in simplified form!\n");
542
0
      NotSimplifiedForm++;
543
0
      return false;
544
0
    }
545
20
546
20
    return true;
547
20
  }
548
549
  /// Iterate over all loops in the given loop set and identify the loops that
550
  /// are eligible for fusion. Place all eligible fusion candidates into Control
551
  /// Flow Equivalent sets, sorted by dominance.
552
9
  void collectFusionCandidates(const LoopVector &LV) {
553
20
    for (Loop *L : LV) {
554
20
      FusionCandidate CurrCand(L, &DT, &PDT);
555
20
      if (!eligibleForFusion(CurrCand))
556
0
        continue;
557
20
558
20
      // Go through each list in FusionCandidates and determine if L is control
559
20
      // flow equivalent with the first loop in that list. If it is, append LV.
560
20
      // If not, go to the next list.
561
20
      // If no suitable list is found, start another list and add it to
562
20
      // FusionCandidates.
563
20
      bool FoundSet = false;
564
20
565
20
      for (auto &CurrCandSet : FusionCandidates) {
566
11
        if (isControlFlowEquivalent(*CurrCandSet.begin(), CurrCand)) {
567
10
          CurrCandSet.insert(CurrCand);
568
10
          FoundSet = true;
569
#ifndef NDEBUG
570
          if (VerboseFusionDebugging)
571
            LLVM_DEBUG(dbgs() << "Adding " << CurrCand
572
                              << " to existing candidate set\n");
573
#endif
574
          break;
575
10
        }
576
11
      }
577
20
      if (!FoundSet) {
578
10
        // No set was found. Create a new set and add to FusionCandidates
579
#ifndef NDEBUG
580
        if (VerboseFusionDebugging)
581
          LLVM_DEBUG(dbgs() << "Adding " << CurrCand << " to new set\n");
582
#endif
583
        FusionCandidateSet NewCandSet;
584
10
        NewCandSet.insert(CurrCand);
585
10
        FusionCandidates.push_back(NewCandSet);
586
10
      }
587
20
      NumFusionCandidates++;
588
20
    }
589
9
  }
590
591
  /// Determine if it is beneficial to fuse two loops.
592
  ///
593
  /// For now, this method simply returns true because we want to fuse as much
594
  /// as possible (primarily to test the pass). This method will evolve, over
595
  /// time, to add heuristics for profitability of fusion.
596
  bool isBeneficialFusion(const FusionCandidate &FC0,
597
10
                          const FusionCandidate &FC1) {
598
10
    return true;
599
10
  }
600
601
  /// Determine if two fusion candidates have the same trip count (i.e., they
602
  /// execute the same number of iterations).
603
  ///
604
  /// Note that for now this method simply returns a boolean value because there
605
  /// are no mechanisms in loop fusion to handle different trip counts. In the
606
  /// future, this behaviour can be extended to adjust one of the loops to make
607
  /// the trip counts equal (e.g., loop peeling). When this is added, this
608
  /// interface may need to change to return more information than just a
609
  /// boolean value.
610
  bool identicalTripCounts(const FusionCandidate &FC0,
611
10
                           const FusionCandidate &FC1) const {
612
10
    const SCEV *TripCount0 = SE.getBackedgeTakenCount(FC0.L);
613
10
    if (isa<SCEVCouldNotCompute>(TripCount0)) {
614
0
      UncomputableTripCount++;
615
0
      LLVM_DEBUG(dbgs() << "Trip count of first loop could not be computed!");
616
0
      return false;
617
0
    }
618
10
619
10
    const SCEV *TripCount1 = SE.getBackedgeTakenCount(FC1.L);
620
10
    if (isa<SCEVCouldNotCompute>(TripCount1)) {
621
0
      UncomputableTripCount++;
622
0
      LLVM_DEBUG(dbgs() << "Trip count of second loop could not be computed!");
623
0
      return false;
624
0
    }
625
10
    LLVM_DEBUG(dbgs() << "\tTrip counts: " << *TripCount0 << " & "
626
10
                      << *TripCount1 << " are "
627
10
                      << (TripCount0 == TripCount1 ? "identical" : "different")
628
10
                      << "\n");
629
10
630
10
    return (TripCount0 == TripCount1);
631
10
  }
632
633
  /// Walk each set of control flow equivalent fusion candidates and attempt to
634
  /// fuse them. This does a single linear traversal of all candidates in the
635
  /// set. The conditions for legal fusion are checked at this point. If a pair
636
  /// of fusion candidates passes all legality checks, they are fused together
637
  /// and a new fusion candidate is created and added to the FusionCandidateSet.
638
  /// The original fusion candidates are then removed, as they are no longer
639
  /// valid.
640
9
  bool fuseCandidates() {
641
9
    bool Fused = false;
642
9
    LLVM_DEBUG(printFusionCandidates(FusionCandidates));
643
10
    for (auto &CandidateSet : FusionCandidates) {
644
10
      if (CandidateSet.size() < 2)
645
2
        continue;
646
8
647
8
      LLVM_DEBUG(dbgs() << "Attempting fusion on Candidate Set:\n"
648
8
                        << CandidateSet << "\n");
649
8
650
16
      for (auto FC0 = CandidateSet.begin(); FC0 != CandidateSet.end(); 
++FC08
) {
651
8
        assert(!LDT.isRemovedLoop(FC0->L) &&
652
8
               "Should not have removed loops in CandidateSet!");
653
8
        auto FC1 = FC0;
654
18
        for (++FC1; FC1 != CandidateSet.end(); 
++FC110
) {
655
10
          assert(!LDT.isRemovedLoop(FC1->L) &&
656
10
                 "Should not have removed loops in CandidateSet!");
657
10
658
10
          LLVM_DEBUG(dbgs() << "Attempting to fuse candidate \n"; FC0->dump();
659
10
                     dbgs() << " with\n"; FC1->dump(); dbgs() << "\n");
660
10
661
10
          FC0->verify();
662
10
          FC1->verify();
663
10
664
10
          if (!identicalTripCounts(*FC0, *FC1)) {
665
0
            LLVM_DEBUG(dbgs() << "Fusion candidates do not have identical trip "
666
0
                                 "counts. Not fusing.\n");
667
0
            NonEqualTripCount++;
668
0
            continue;
669
0
          }
670
10
671
10
          if (!isAdjacent(*FC0, *FC1)) {
672
0
            LLVM_DEBUG(dbgs()
673
0
                       << "Fusion candidates are not adjacent. Not fusing.\n");
674
0
            NonAdjacent++;
675
0
            continue;
676
0
          }
677
10
678
10
          // For now we skip fusing if the second candidate has any instructions
679
10
          // in the preheader. This is done because we currently do not have the
680
10
          // safety checks to determine if it is save to move the preheader of
681
10
          // the second candidate past the body of the first candidate. Once
682
10
          // these checks are added, this condition can be removed.
683
10
          if (!isEmptyPreheader(*FC1)) {
684
0
            LLVM_DEBUG(dbgs() << "Fusion candidate does not have empty "
685
0
                                 "preheader. Not fusing.\n");
686
0
            NonEmptyPreheader++;
687
0
            continue;
688
0
          }
689
10
690
10
          if (!dependencesAllowFusion(*FC0, *FC1)) {
691
0
            LLVM_DEBUG(dbgs() << "Memory dependencies do not allow fusion!\n");
692
0
            continue;
693
0
          }
694
10
695
10
          bool BeneficialToFuse = isBeneficialFusion(*FC0, *FC1);
696
10
          LLVM_DEBUG(dbgs()
697
10
                     << "\tFusion appears to be "
698
10
                     << (BeneficialToFuse ? "" : "un") << "profitable!\n");
699
10
          if (!BeneficialToFuse)
700
0
            continue;
701
10
702
10
          // All analysis has completed and has determined that fusion is legal
703
10
          // and profitable. At this point, start transforming the code and
704
10
          // perform fusion.
705
10
706
10
          LLVM_DEBUG(dbgs() << "\tFusion is performed: " << *FC0 << " and "
707
10
                            << *FC1 << "\n");
708
10
709
10
          // Report fusion to the Optimization Remarks.
710
10
          // Note this needs to be done *before* performFusion because
711
10
          // performFusion will change the original loops, making it not
712
10
          // possible to identify them after fusion is complete.
713
10
          reportLoopFusion(*FC0, *FC1, ORE);
714
10
715
10
          FusionCandidate FusedCand(performFusion(*FC0, *FC1), &DT, &PDT);
716
10
          FusedCand.verify();
717
10
          assert(eligibleForFusion(FusedCand) &&
718
10
                 "Fused candidate should be eligible for fusion!");
719
10
720
10
          // Notify the loop-depth-tree that these loops are not valid objects
721
10
          // anymore.
722
10
          LDT.removeLoop(FC1->L);
723
10
724
10
          CandidateSet.erase(FC0);
725
10
          CandidateSet.erase(FC1);
726
10
727
10
          auto InsertPos = CandidateSet.insert(FusedCand);
728
10
729
10
          assert(InsertPos.second &&
730
10
                 "Unable to insert TargetCandidate in CandidateSet!");
731
10
732
10
          // Reset FC0 and FC1 the new (fused) candidate. Subsequent iterations
733
10
          // of the FC1 loop will attempt to fuse the new (fused) loop with the
734
10
          // remaining candidates in the current candidate set.
735
10
          FC0 = FC1 = InsertPos.first;
736
10
737
10
          LLVM_DEBUG(dbgs() << "Candidate Set (after fusion): " << CandidateSet
738
10
                            << "\n");
739
10
740
10
          Fused = true;
741
10
        }
742
8
      }
743
8
    }
744
9
    return Fused;
745
9
  }
746
747
  /// Rewrite all additive recurrences in a SCEV to use a new loop.
748
  class AddRecLoopReplacer : public SCEVRewriteVisitor<AddRecLoopReplacer> {
749
  public:
750
    AddRecLoopReplacer(ScalarEvolution &SE, const Loop &OldL, const Loop &NewL,
751
                       bool UseMax = true)
752
        : SCEVRewriteVisitor(SE), Valid(true), UseMax(UseMax), OldL(OldL),
753
29
          NewL(NewL) {}
754
755
23
    const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
756
23
      const Loop *ExprL = Expr->getLoop();
757
23
      SmallVector<const SCEV *, 2> Operands;
758
23
      if (ExprL == &OldL) {
759
23
        Operands.append(Expr->op_begin(), Expr->op_end());
760
23
        return SE.getAddRecExpr(Operands, &NewL, Expr->getNoWrapFlags());
761
23
      }
762
0
763
0
      if (OldL.contains(ExprL)) {
764
0
        bool Pos = SE.isKnownPositive(Expr->getStepRecurrence(SE));
765
0
        if (!UseMax || !Pos || !Expr->isAffine()) {
766
0
          Valid = false;
767
0
          return Expr;
768
0
        }
769
0
        return visit(Expr->getStart());
770
0
      }
771
0
772
0
      for (const SCEV *Op : Expr->operands())
773
0
        Operands.push_back(visit(Op));
774
0
      return SE.getAddRecExpr(Operands, ExprL, Expr->getNoWrapFlags());
775
0
    }
776
777
29
    bool wasValidSCEV() const { return Valid; }
778
779
  private:
780
    bool Valid, UseMax;
781
    const Loop &OldL, &NewL;
782
  };
783
784
  /// Return false if the access functions of \p I0 and \p I1 could cause
785
  /// a negative dependence.
786
  bool accessDiffIsPositive(const Loop &L0, const Loop &L1, Instruction &I0,
787
29
                            Instruction &I1, bool EqualIsInvalid) {
788
29
    Value *Ptr0 = getLoadStorePointerOperand(&I0);
789
29
    Value *Ptr1 = getLoadStorePointerOperand(&I1);
790
29
    if (!Ptr0 || !Ptr1)
791
0
      return false;
792
29
793
29
    const SCEV *SCEVPtr0 = SE.getSCEVAtScope(Ptr0, &L0);
794
29
    const SCEV *SCEVPtr1 = SE.getSCEVAtScope(Ptr1, &L1);
795
#ifndef NDEBUG
796
    if (VerboseFusionDebugging)
797
      LLVM_DEBUG(dbgs() << "    Access function check: " << *SCEVPtr0 << " vs "
798
                        << *SCEVPtr1 << "\n");
799
#endif
800
    AddRecLoopReplacer Rewriter(SE, L0, L1);
801
29
    SCEVPtr0 = Rewriter.visit(SCEVPtr0);
802
#ifndef NDEBUG
803
    if (VerboseFusionDebugging)
804
      LLVM_DEBUG(dbgs() << "    Access function after rewrite: " << *SCEVPtr0
805
                        << " [Valid: " << Rewriter.wasValidSCEV() << "]\n");
806
#endif
807
29
    if (!Rewriter.wasValidSCEV())
808
0
      return false;
809
29
810
29
    // TODO: isKnownPredicate doesnt work well when one SCEV is loop carried (by
811
29
    //       L0) and the other is not. We could check if it is monotone and test
812
29
    //       the beginning and end value instead.
813
29
814
29
    BasicBlock *L0Header = L0.getHeader();
815
97
    auto HasNonLinearDominanceRelation = [&](const SCEV *S) {
816
97
      const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S);
817
97
      if (!AddRec)
818
66
        return false;
819
31
      return !DT.dominates(L0Header, AddRec->getLoop()->getHeader()) &&
820
31
             
!DT.dominates(AddRec->getLoop()->getHeader(), L0Header)2
;
821
31
    };
822
29
    if (SCEVExprContains(SCEVPtr1, HasNonLinearDominanceRelation))
823
0
      return false;
824
29
825
29
    ICmpInst::Predicate Pred =
826
29
        EqualIsInvalid ? 
ICmpInst::ICMP_SGT0
: ICmpInst::ICMP_SGE;
827
29
    bool IsAlwaysGE = SE.isKnownPredicate(Pred, SCEVPtr0, SCEVPtr1);
828
#ifndef NDEBUG
829
    if (VerboseFusionDebugging)
830
      LLVM_DEBUG(dbgs() << "    Relation: " << *SCEVPtr0
831
                        << (IsAlwaysGE ? "  >=  " : "  may <  ") << *SCEVPtr1
832
                        << "\n");
833
#endif
834
    return IsAlwaysGE;
835
29
  }
836
837
  /// Return true if the dependences between @p I0 (in @p L0) and @p I1 (in
838
  /// @p L1) allow loop fusion of @p L0 and @p L1. The dependence analyses
839
  /// specified by @p DepChoice are used to determine this.
840
  bool dependencesAllowFusion(const FusionCandidate &FC0,
841
                              const FusionCandidate &FC1, Instruction &I0,
842
                              Instruction &I1, bool AnyDep,
843
82
                              FusionDependenceAnalysisChoice DepChoice) {
844
#ifndef NDEBUG
845
    if (VerboseFusionDebugging) {
846
      LLVM_DEBUG(dbgs() << "Check dep: " << I0 << " vs " << I1 << " : "
847
                        << DepChoice << "\n");
848
    }
849
#endif
850
    switch (DepChoice) {
851
82
    case FUSION_DEPENDENCE_ANALYSIS_SCEV:
852
29
      return accessDiffIsPositive(*FC0.L, *FC1.L, I0, I1, AnyDep);
853
82
    case FUSION_DEPENDENCE_ANALYSIS_DA: {
854
24
      auto DepResult = DI.depends(&I0, &I1, true);
855
24
      if (!DepResult)
856
24
        return true;
857
#ifndef NDEBUG
858
      if (VerboseFusionDebugging) {
859
        LLVM_DEBUG(dbgs() << "DA res: "; DepResult->dump(dbgs());
860
                   dbgs() << " [#l: " << DepResult->getLevels() << "][Ordered: "
861
                          << (DepResult->isOrdered() ? "true" : "false")
862
                          << "]\n");
863
        LLVM_DEBUG(dbgs() << "DepResult Levels: " << DepResult->getLevels()
864
                          << "\n");
865
      }
866
#endif
867
868
0
      if (DepResult->getNextPredecessor() || DepResult->getNextSuccessor())
869
0
        LLVM_DEBUG(
870
0
            dbgs() << "TODO: Implement pred/succ dependence handling!\n");
871
0
872
0
      // TODO: Can we actually use the dependence info analysis here?
873
0
      return false;
874
0
    }
875
0
876
29
    case FUSION_DEPENDENCE_ANALYSIS_ALL:
877
29
      return dependencesAllowFusion(FC0, FC1, I0, I1, AnyDep,
878
29
                                    FUSION_DEPENDENCE_ANALYSIS_SCEV) ||
879
29
             dependencesAllowFusion(FC0, FC1, I0, I1, AnyDep,
880
24
                                    FUSION_DEPENDENCE_ANALYSIS_DA);
881
0
    }
882
0
883
0
    llvm_unreachable("Unknown fusion dependence analysis choice!");
884
0
  }
885
886
  /// Perform a dependence check and return if @p FC0 and @p FC1 can be fused.
887
  bool dependencesAllowFusion(const FusionCandidate &FC0,
888
10
                              const FusionCandidate &FC1) {
889
10
    LLVM_DEBUG(dbgs() << "Check if " << FC0 << " can be fused with " << FC1
890
10
                      << "\n");
891
10
    assert(FC0.L->getLoopDepth() == FC1.L->getLoopDepth());
892
10
    assert(DT.dominates(FC0.Preheader, FC1.Preheader));
893
10
894
13
    for (Instruction *WriteL0 : FC0.MemWrites) {
895
13
      for (Instruction *WriteL1 : FC1.MemWrites)
896
13
        if (!dependencesAllowFusion(FC0, FC1, *WriteL0, *WriteL1,
897
13
                                    /* AnyDep */ false,
898
13
                                    FusionDependenceAnalysis)) {
899
0
          InvalidDependencies++;
900
0
          return false;
901
0
        }
902
13
      for (Instruction *ReadL1 : FC1.MemReads)
903
3
        if (!dependencesAllowFusion(FC0, FC1, *WriteL0, *ReadL1,
904
3
                                    /* AnyDep */ false,
905
3
                                    FusionDependenceAnalysis)) {
906
0
          InvalidDependencies++;
907
0
          return false;
908
0
        }
909
13
    }
910
10
911
10
    for (Instruction *WriteL1 : FC1.MemWrites) {
912
10
      for (Instruction *WriteL0 : FC0.MemWrites)
913
13
        if (!dependencesAllowFusion(FC0, FC1, *WriteL0, *WriteL1,
914
13
                                    /* AnyDep */ false,
915
13
                                    FusionDependenceAnalysis)) {
916
0
          InvalidDependencies++;
917
0
          return false;
918
0
        }
919
10
      for (Instruction *ReadL0 : FC0.MemReads)
920
0
        if (!dependencesAllowFusion(FC0, FC1, *ReadL0, *WriteL1,
921
0
                                    /* AnyDep */ false,
922
0
                                    FusionDependenceAnalysis)) {
923
0
          InvalidDependencies++;
924
0
          return false;
925
0
        }
926
10
    }
927
10
928
10
    // Walk through all uses in FC1. For each use, find the reaching def. If the
929
10
    // def is located in FC0 then it is is not safe to fuse.
930
10
    for (BasicBlock *BB : FC1.L->blocks())
931
33
      for (Instruction &I : *BB)
932
148
        for (auto &Op : I.operands())
933
279
          if (Instruction *Def = dyn_cast<Instruction>(Op))
934
152
            if (FC0.L->contains(Def->getParent())) {
935
0
              InvalidDependencies++;
936
0
              return false;
937
0
            }
938
10
939
10
    return true;
940
10
  }
941
942
  /// Determine if the exit block of \p FC0 is the preheader of \p FC1. In this
943
  /// case, there is no code in between the two fusion candidates, thus making
944
  /// them adjacent.
945
  bool isAdjacent(const FusionCandidate &FC0,
946
10
                  const FusionCandidate &FC1) const {
947
10
    return FC0.ExitBlock == FC1.Preheader;
948
10
  }
949
950
10
  bool isEmptyPreheader(const FusionCandidate &FC) const {
951
10
    return FC.Preheader->size() == 1;
952
10
  }
953
954
  /// Fuse two fusion candidates, creating a new fused loop.
955
  ///
956
  /// This method contains the mechanics of fusing two loops, represented by \p
957
  /// FC0 and \p FC1. It is assumed that \p FC0 dominates \p FC1 and \p FC1
958
  /// postdominates \p FC0 (making them control flow equivalent). It also
959
  /// assumes that the other conditions for fusion have been met: adjacent,
960
  /// identical trip counts, and no negative distance dependencies exist that
961
  /// would prevent fusion. Thus, there is no checking for these conditions in
962
  /// this method.
963
  ///
964
  /// Fusion is performed by rewiring the CFG to update successor blocks of the
965
  /// components of tho loop. Specifically, the following changes are done:
966
  ///
967
  ///   1. The preheader of \p FC1 is removed as it is no longer necessary
968
  ///   (because it is currently only a single statement block).
969
  ///   2. The latch of \p FC0 is modified to jump to the header of \p FC1.
970
  ///   3. The latch of \p FC1 i modified to jump to the header of \p FC0.
971
  ///   4. All blocks from \p FC1 are removed from FC1 and added to FC0.
972
  ///
973
  /// All of these modifications are done with dominator tree updates, thus
974
  /// keeping the dominator (and post dominator) information up-to-date.
975
  ///
976
  /// This can be improved in the future by actually merging blocks during
977
  /// fusion. For example, the preheader of \p FC1 can be merged with the
978
  /// preheader of \p FC0. This would allow loops with more than a single
979
  /// statement in the preheader to be fused. Similarly, the latch blocks of the
980
  /// two loops could also be fused into a single block. This will require
981
  /// analysis to prove it is safe to move the contents of the block past
982
  /// existing code, which currently has not been implemented.
983
10
  Loop *performFusion(const FusionCandidate &FC0, const FusionCandidate &FC1) {
984
10
    assert(FC0.isValid() && FC1.isValid() &&
985
10
           "Expecting valid fusion candidates");
986
10
987
10
    LLVM_DEBUG(dbgs() << "Fusion Candidate 0: \n"; FC0.dump();
988
10
               dbgs() << "Fusion Candidate 1: \n"; FC1.dump(););
989
10
990
10
    assert(FC1.Preheader == FC0.ExitBlock);
991
10
    assert(FC1.Preheader->size() == 1 &&
992
10
           FC1.Preheader->getSingleSuccessor() == FC1.Header);
993
10
994
10
    // Remember the phi nodes originally in the header of FC0 in order to rewire
995
10
    // them later. However, this is only necessary if the new loop carried
996
10
    // values might not dominate the exiting branch. While we do not generally
997
10
    // test if this is the case but simply insert intermediate phi nodes, we
998
10
    // need to make sure these intermediate phi nodes have different
999
10
    // predecessors. To this end, we filter the special case where the exiting
1000
10
    // block is the latch block of the first loop. Nothing needs to be done
1001
10
    // anyway as all loop carried values dominate the latch and thereby also the
1002
10
    // exiting branch.
1003
10
    SmallVector<PHINode *, 8> OriginalFC0PHIs;
1004
10
    if (FC0.ExitingBlock != FC0.Latch)
1005
10
      for (PHINode &PHI : FC0.Header->phis())
1006
22
        OriginalFC0PHIs.push_back(&PHI);
1007
10
1008
10
    // Replace incoming blocks for header PHIs first.
1009
10
    FC1.Preheader->replaceSuccessorsPhiUsesWith(FC0.Preheader);
1010
10
    FC0.Latch->replaceSuccessorsPhiUsesWith(FC1.Latch);
1011
10
1012
10
    // Then modify the control flow and update DT and PDT.
1013
10
    SmallVector<DominatorTree::UpdateType, 8> TreeUpdates;
1014
10
1015
10
    // The old exiting block of the first loop (FC0) has to jump to the header
1016
10
    // of the second as we need to execute the code in the second header block
1017
10
    // regardless of the trip count. That is, if the trip count is 0, so the
1018
10
    // back edge is never taken, we still have to execute both loop headers,
1019
10
    // especially (but not only!) if the second is a do-while style loop.
1020
10
    // However, doing so might invalidate the phi nodes of the first loop as
1021
10
    // the new values do only need to dominate their latch and not the exiting
1022
10
    // predicate. To remedy this potential problem we always introduce phi
1023
10
    // nodes in the header of the second loop later that select the loop carried
1024
10
    // value, if the second header was reached through an old latch of the
1025
10
    // first, or undef otherwise. This is sound as exiting the first implies the
1026
10
    // second will exit too, __without__ taking the back-edge. [Their
1027
10
    // trip-counts are equal after all.
1028
10
    // KB: Would this sequence be simpler to just just make FC0.ExitingBlock go
1029
10
    // to FC1.Header? I think this is basically what the three sequences are
1030
10
    // trying to accomplish; however, doing this directly in the CFG may mean
1031
10
    // the DT/PDT becomes invalid
1032
10
    FC0.ExitingBlock->getTerminator()->replaceUsesOfWith(FC1.Preheader,
1033
10
                                                         FC1.Header);
1034
10
    TreeUpdates.emplace_back(DominatorTree::UpdateType(
1035
10
        DominatorTree::Delete, FC0.ExitingBlock, FC1.Preheader));
1036
10
    TreeUpdates.emplace_back(DominatorTree::UpdateType(
1037
10
        DominatorTree::Insert, FC0.ExitingBlock, FC1.Header));
1038
10
1039
10
    // The pre-header of L1 is not necessary anymore.
1040
10
    assert(pred_begin(FC1.Preheader) == pred_end(FC1.Preheader));
1041
10
    FC1.Preheader->getTerminator()->eraseFromParent();
1042
10
    new UnreachableInst(FC1.Preheader->getContext(), FC1.Preheader);
1043
10
    TreeUpdates.emplace_back(DominatorTree::UpdateType(
1044
10
        DominatorTree::Delete, FC1.Preheader, FC1.Header));
1045
10
1046
10
    // Moves the phi nodes from the second to the first loops header block.
1047
25
    while (PHINode *PHI = dyn_cast<PHINode>(&FC1.Header->front())) {
1048
15
      if (SE.isSCEVable(PHI->getType()))
1049
15
        SE.forgetValue(PHI);
1050
15
      if (PHI->hasNUsesOrMore(1))
1051
15
        PHI->moveBefore(&*FC0.Header->getFirstInsertionPt());
1052
0
      else
1053
0
        PHI->eraseFromParent();
1054
15
    }
1055
10
1056
10
    // Introduce new phi nodes in the second loop header to ensure
1057
10
    // exiting the first and jumping to the header of the second does not break
1058
10
    // the SSA property of the phis originally in the first loop. See also the
1059
10
    // comment above.
1060
10
    Instruction *L1HeaderIP = &FC1.Header->front();
1061
22
    for (PHINode *LCPHI : OriginalFC0PHIs) {
1062
22
      int L1LatchBBIdx = LCPHI->getBasicBlockIndex(FC1.Latch);
1063
22
      assert(L1LatchBBIdx >= 0 &&
1064
22
             "Expected loop carried value to be rewired at this point!");
1065
22
1066
22
      Value *LCV = LCPHI->getIncomingValue(L1LatchBBIdx);
1067
22
1068
22
      PHINode *L1HeaderPHI = PHINode::Create(
1069
22
          LCV->getType(), 2, LCPHI->getName() + ".afterFC0", L1HeaderIP);
1070
22
      L1HeaderPHI->addIncoming(LCV, FC0.Latch);
1071
22
      L1HeaderPHI->addIncoming(UndefValue::get(LCV->getType()),
1072
22
                               FC0.ExitingBlock);
1073
22
1074
22
      LCPHI->setIncomingValue(L1LatchBBIdx, L1HeaderPHI);
1075
22
    }
1076
10
1077
10
    // Replace latch terminator destinations.
1078
10
    FC0.Latch->getTerminator()->replaceUsesOfWith(FC0.Header, FC1.Header);
1079
10
    FC1.Latch->getTerminator()->replaceUsesOfWith(FC1.Header, FC0.Header);
1080
10
1081
10
    // If FC0.Latch and FC0.ExitingBlock are the same then we have already
1082
10
    // performed the updates above.
1083
10
    if (FC0.Latch != FC0.ExitingBlock)
1084
10
      TreeUpdates.emplace_back(DominatorTree::UpdateType(
1085
10
          DominatorTree::Insert, FC0.Latch, FC1.Header));
1086
10
1087
10
    TreeUpdates.emplace_back(DominatorTree::UpdateType(DominatorTree::Delete,
1088
10
                                                       FC0.Latch, FC0.Header));
1089
10
    TreeUpdates.emplace_back(DominatorTree::UpdateType(DominatorTree::Insert,
1090
10
                                                       FC1.Latch, FC0.Header));
1091
10
    TreeUpdates.emplace_back(DominatorTree::UpdateType(DominatorTree::Delete,
1092
10
                                                       FC1.Latch, FC1.Header));
1093
10
1094
10
    // Update DT/PDT
1095
10
    DTU.applyUpdates(TreeUpdates);
1096
10
1097
10
    LI.removeBlock(FC1.Preheader);
1098
10
    DTU.deleteBB(FC1.Preheader);
1099
10
    DTU.flush();
1100
10
1101
10
    // Is there a way to keep SE up-to-date so we don't need to forget the loops
1102
10
    // and rebuild the information in subsequent passes of fusion?
1103
10
    SE.forgetLoop(FC1.L);
1104
10
    SE.forgetLoop(FC0.L);
1105
10
1106
10
    // Merge the loops.
1107
10
    SmallVector<BasicBlock *, 8> Blocks(FC1.L->block_begin(),
1108
10
                                        FC1.L->block_end());
1109
33
    for (BasicBlock *BB : Blocks) {
1110
33
      FC0.L->addBlockEntry(BB);
1111
33
      FC1.L->removeBlockFromLoop(BB);
1112
33
      if (LI.getLoopFor(BB) != FC1.L)
1113
3
        continue;
1114
30
      LI.changeLoopFor(BB, FC0.L);
1115
30
    }
1116
11
    while (!FC1.L->empty()) {
1117
1
      const auto &ChildLoopIt = FC1.L->begin();
1118
1
      Loop *ChildLoop = *ChildLoopIt;
1119
1
      FC1.L->removeChildLoop(ChildLoopIt);
1120
1
      FC0.L->addChildLoop(ChildLoop);
1121
1
    }
1122
10
1123
10
    // Delete the now empty loop L1.
1124
10
    LI.erase(FC1.L);
1125
10
1126
#ifndef NDEBUG
1127
    assert(!verifyFunction(*FC0.Header->getParent(), &errs()));
1128
    assert(DT.verify(DominatorTree::VerificationLevel::Fast));
1129
    assert(PDT.verify());
1130
    LI.verify(DT);
1131
    SE.verify();
1132
#endif
1133
1134
10
    FuseCounter++;
1135
10
1136
10
    LLVM_DEBUG(dbgs() << "Fusion done:\n");
1137
10
1138
10
    return FC0.L;
1139
10
  }
1140
};
1141
1142
struct LoopFuseLegacy : public FunctionPass {
1143
1144
  static char ID;
1145
1146
4
  LoopFuseLegacy() : FunctionPass(ID) {
1147
4
    initializeLoopFuseLegacyPass(*PassRegistry::getPassRegistry());
1148
4
  }
1149
1150
4
  void getAnalysisUsage(AnalysisUsage &AU) const override {
1151
4
    AU.addRequiredID(LoopSimplifyID);
1152
4
    AU.addRequired<ScalarEvolutionWrapperPass>();
1153
4
    AU.addRequired<LoopInfoWrapperPass>();
1154
4
    AU.addRequired<DominatorTreeWrapperPass>();
1155
4
    AU.addRequired<PostDominatorTreeWrapperPass>();
1156
4
    AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
1157
4
    AU.addRequired<DependenceAnalysisWrapperPass>();
1158
4
1159
4
    AU.addPreserved<ScalarEvolutionWrapperPass>();
1160
4
    AU.addPreserved<LoopInfoWrapperPass>();
1161
4
    AU.addPreserved<DominatorTreeWrapperPass>();
1162
4
    AU.addPreserved<PostDominatorTreeWrapperPass>();
1163
4
  }
1164
1165
8
  bool runOnFunction(Function &F) override {
1166
8
    if (skipFunction(F))
1167
0
      return false;
1168
8
    auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1169
8
    auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1170
8
    auto &DI = getAnalysis<DependenceAnalysisWrapperPass>().getDI();
1171
8
    auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
1172
8
    auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
1173
8
    auto &ORE = getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
1174
8
1175
8
    const DataLayout &DL = F.getParent()->getDataLayout();
1176
8
    LoopFuser LF(LI, DT, DI, SE, PDT, ORE, DL);
1177
8
    return LF.fuseLoops(F);
1178
8
  }
1179
};
1180
1181
0
PreservedAnalyses LoopFusePass::run(Function &F, FunctionAnalysisManager &AM) {
1182
0
  auto &LI = AM.getResult<LoopAnalysis>(F);
1183
0
  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1184
0
  auto &DI = AM.getResult<DependenceAnalysis>(F);
1185
0
  auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
1186
0
  auto &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
1187
0
  auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);
1188
0
1189
0
  const DataLayout &DL = F.getParent()->getDataLayout();
1190
0
  LoopFuser LF(LI, DT, DI, SE, PDT, ORE, DL);
1191
0
  bool Changed = LF.fuseLoops(F);
1192
0
  if (!Changed)
1193
0
    return PreservedAnalyses::all();
1194
0
1195
0
  PreservedAnalyses PA;
1196
0
  PA.preserve<DominatorTreeAnalysis>();
1197
0
  PA.preserve<PostDominatorTreeAnalysis>();
1198
0
  PA.preserve<ScalarEvolutionAnalysis>();
1199
0
  PA.preserve<LoopAnalysis>();
1200
0
  return PA;
1201
0
}
1202
1203
char LoopFuseLegacy::ID = 0;
1204
1205
36.0k
INITIALIZE_PASS_BEGIN(LoopFuseLegacy, "loop-fusion", "Loop Fusion", false,
1206
36.0k
                      false)
1207
36.0k
INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
1208
36.0k
INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
1209
36.0k
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1210
36.0k
INITIALIZE_PASS_DEPENDENCY(DependenceAnalysisWrapperPass)
1211
36.0k
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
1212
36.0k
INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)
1213
36.0k
INITIALIZE_PASS_END(LoopFuseLegacy, "loop-fusion", "Loop Fusion", false, false)
1214
1215
0
FunctionPass *llvm::createLoopFusePass() { return new LoopFuseLegacy(); }