Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- LoopUnrollAndJam.cpp - Loop unroll and jam 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 pass implements an unroll and jam pass. Most of the work is done by
10
// Utils/UnrollLoopAndJam.cpp.
11
//===----------------------------------------------------------------------===//
12
13
#include "llvm/Transforms/Scalar/LoopUnrollAndJamPass.h"
14
#include "llvm/ADT/None.h"
15
#include "llvm/ADT/STLExtras.h"
16
#include "llvm/ADT/SmallPtrSet.h"
17
#include "llvm/ADT/StringRef.h"
18
#include "llvm/Analysis/AssumptionCache.h"
19
#include "llvm/Analysis/CodeMetrics.h"
20
#include "llvm/Analysis/DependenceAnalysis.h"
21
#include "llvm/Analysis/LoopAnalysisManager.h"
22
#include "llvm/Analysis/LoopInfo.h"
23
#include "llvm/Analysis/LoopPass.h"
24
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
25
#include "llvm/Analysis/ScalarEvolution.h"
26
#include "llvm/Analysis/TargetTransformInfo.h"
27
#include "llvm/IR/BasicBlock.h"
28
#include "llvm/IR/CFG.h"
29
#include "llvm/IR/Constant.h"
30
#include "llvm/IR/Constants.h"
31
#include "llvm/IR/Dominators.h"
32
#include "llvm/IR/Function.h"
33
#include "llvm/IR/Instruction.h"
34
#include "llvm/IR/Instructions.h"
35
#include "llvm/IR/IntrinsicInst.h"
36
#include "llvm/IR/Metadata.h"
37
#include "llvm/IR/PassManager.h"
38
#include "llvm/Pass.h"
39
#include "llvm/Support/Casting.h"
40
#include "llvm/Support/CommandLine.h"
41
#include "llvm/Support/Debug.h"
42
#include "llvm/Support/ErrorHandling.h"
43
#include "llvm/Support/raw_ostream.h"
44
#include "llvm/Transforms/Scalar.h"
45
#include "llvm/Transforms/Scalar/LoopPassManager.h"
46
#include "llvm/Transforms/Utils.h"
47
#include "llvm/Transforms/Utils/LoopUtils.h"
48
#include "llvm/Transforms/Utils/UnrollLoop.h"
49
#include <algorithm>
50
#include <cassert>
51
#include <cstdint>
52
#include <string>
53
54
using namespace llvm;
55
56
#define DEBUG_TYPE "loop-unroll-and-jam"
57
58
/// @{
59
/// Metadata attribute names
60
static const char *const LLVMLoopUnrollAndJamFollowupAll =
61
    "llvm.loop.unroll_and_jam.followup_all";
62
static const char *const LLVMLoopUnrollAndJamFollowupInner =
63
    "llvm.loop.unroll_and_jam.followup_inner";
64
static const char *const LLVMLoopUnrollAndJamFollowupOuter =
65
    "llvm.loop.unroll_and_jam.followup_outer";
66
static const char *const LLVMLoopUnrollAndJamFollowupRemainderInner =
67
    "llvm.loop.unroll_and_jam.followup_remainder_inner";
68
static const char *const LLVMLoopUnrollAndJamFollowupRemainderOuter =
69
    "llvm.loop.unroll_and_jam.followup_remainder_outer";
70
/// @}
71
72
static cl::opt<bool>
73
    AllowUnrollAndJam("allow-unroll-and-jam", cl::Hidden,
74
                      cl::desc("Allows loops to be unroll-and-jammed."));
75
76
static cl::opt<unsigned> UnrollAndJamCount(
77
    "unroll-and-jam-count", cl::Hidden,
78
    cl::desc("Use this unroll count for all loops including those with "
79
             "unroll_and_jam_count pragma values, for testing purposes"));
80
81
static cl::opt<unsigned> UnrollAndJamThreshold(
82
    "unroll-and-jam-threshold", cl::init(60), cl::Hidden,
83
    cl::desc("Threshold to use for inner loop when doing unroll and jam."));
84
85
static cl::opt<unsigned> PragmaUnrollAndJamThreshold(
86
    "pragma-unroll-and-jam-threshold", cl::init(1024), cl::Hidden,
87
    cl::desc("Unrolled size limit for loops with an unroll_and_jam(full) or "
88
             "unroll_count pragma."));
89
90
// Returns the loop hint metadata node with the given name (for example,
91
// "llvm.loop.unroll.count").  If no such metadata node exists, then nullptr is
92
// returned.
93
28
static MDNode *GetUnrollMetadataForLoop(const Loop *L, StringRef Name) {
94
28
  if (MDNode *LoopID = L->getLoopID())
95
16
    return GetUnrollMetadata(LoopID, Name);
96
12
  return nullptr;
97
12
}
98
99
// Returns true if the loop has any metadata starting with Prefix. For example a
100
// Prefix of "llvm.loop.unroll." returns true if we have any unroll metadata.
101
63
static bool HasAnyUnrollPragma(const Loop *L, StringRef Prefix) {
102
63
  if (MDNode *LoopID = L->getLoopID()) {
103
21
    // First operand should refer to the loop id itself.
104
21
    assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
105
21
    assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
106
21
107
42
    for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; 
++i21
) {
108
29
      MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
109
29
      if (!MD)
110
0
        continue;
111
29
112
29
      MDString *S = dyn_cast<MDString>(MD->getOperand(0));
113
29
      if (!S)
114
0
        continue;
115
29
116
29
      if (S->getString().startswith(Prefix))
117
8
        return true;
118
29
    }
119
21
  }
120
63
  
return false55
;
121
63
}
122
123
// Returns true if the loop has an unroll_and_jam(enable) pragma.
124
13
static bool HasUnrollAndJamEnablePragma(const Loop *L) {
125
13
  return GetUnrollMetadataForLoop(L, "llvm.loop.unroll_and_jam.enable");
126
13
}
127
128
// If loop has an unroll_and_jam_count pragma return the (necessarily
129
// positive) value from the pragma.  Otherwise return 0.
130
15
static unsigned UnrollAndJamCountPragmaValue(const Loop *L) {
131
15
  MDNode *MD = GetUnrollMetadataForLoop(L, "llvm.loop.unroll_and_jam.count");
132
15
  if (MD) {
133
4
    assert(MD->getNumOperands() == 2 &&
134
4
           "Unroll count hint metadata should have two operands.");
135
4
    unsigned Count =
136
4
        mdconst::extract<ConstantInt>(MD->getOperand(1))->getZExtValue();
137
4
    assert(Count >= 1 && "Unroll count must be positive.");
138
4
    return Count;
139
4
  }
140
11
  return 0;
141
11
}
142
143
// Returns loop size estimation for unrolled loop.
144
static uint64_t
145
getUnrollAndJammedLoopSize(unsigned LoopSize,
146
63
                           TargetTransformInfo::UnrollingPreferences &UP) {
147
63
  assert(LoopSize >= UP.BEInsns && "LoopSize should not be less than BEInsns!");
148
63
  return static_cast<uint64_t>(LoopSize - UP.BEInsns) * UP.Count + UP.BEInsns;
149
63
}
150
151
// Calculates unroll and jam count and writes it to UP.Count. Returns true if
152
// unroll count was set explicitly.
153
static bool computeUnrollAndJamCount(
154
    Loop *L, Loop *SubLoop, const TargetTransformInfo &TTI, DominatorTree &DT,
155
    LoopInfo *LI, ScalarEvolution &SE,
156
    const SmallPtrSetImpl<const Value *> &EphValues,
157
    OptimizationRemarkEmitter *ORE, unsigned OuterTripCount,
158
    unsigned OuterTripMultiple, unsigned OuterLoopSize, unsigned InnerTripCount,
159
34
    unsigned InnerLoopSize, TargetTransformInfo::UnrollingPreferences &UP) {
160
34
  // First up use computeUnrollCount from the loop unroller to get a count
161
34
  // for unrolling the outer loop, plus any loops requiring explicit
162
34
  // unrolling we leave to the unroller. This uses UP.Threshold /
163
34
  // UP.PartialThreshold / UP.MaxCount to come up with sensible loop values.
164
34
  // We have already checked that the loop has no unroll.* pragmas.
165
34
  unsigned MaxTripCount = 0;
166
34
  bool UseUpperBound = false;
167
34
  bool ExplicitUnroll = computeUnrollCount(
168
34
      L, TTI, DT, LI, SE, EphValues, ORE, OuterTripCount, MaxTripCount,
169
34
      OuterTripMultiple, OuterLoopSize, UP, UseUpperBound);
170
34
  if (ExplicitUnroll || UseUpperBound) {
171
0
    // If the user explicitly set the loop as unrolled, dont UnJ it. Leave it
172
0
    // for the unroller instead.
173
0
    LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; explicit count set by "
174
0
                         "computeUnrollCount\n");
175
0
    UP.Count = 0;
176
0
    return false;
177
0
  }
178
34
179
34
  // Override with any explicit Count from the "unroll-and-jam-count" option.
180
34
  bool UserUnrollCount = UnrollAndJamCount.getNumOccurrences() > 0;
181
34
  if (UserUnrollCount) {
182
19
    UP.Count = UnrollAndJamCount;
183
19
    UP.Force = true;
184
19
    if (UP.AllowRemainder &&
185
19
        getUnrollAndJammedLoopSize(OuterLoopSize, UP) < UP.Threshold &&
186
19
        getUnrollAndJammedLoopSize(InnerLoopSize, UP) <
187
19
            UP.UnrollAndJamInnerLoopThreshold)
188
19
      return true;
189
15
  }
190
15
191
15
  // Check for unroll_and_jam pragmas
192
15
  unsigned PragmaCount = UnrollAndJamCountPragmaValue(L);
193
15
  if (PragmaCount > 0) {
194
4
    UP.Count = PragmaCount;
195
4
    UP.Runtime = true;
196
4
    UP.Force = true;
197
4
    if ((UP.AllowRemainder || 
(OuterTripMultiple % PragmaCount == 0)0
) &&
198
4
        getUnrollAndJammedLoopSize(OuterLoopSize, UP) < UP.Threshold &&
199
4
        getUnrollAndJammedLoopSize(InnerLoopSize, UP) <
200
4
            UP.UnrollAndJamInnerLoopThreshold)
201
2
      return true;
202
13
  }
203
13
204
13
  bool PragmaEnableUnroll = HasUnrollAndJamEnablePragma(L);
205
13
  bool ExplicitUnrollAndJamCount = PragmaCount > 0 || 
UserUnrollCount11
;
206
13
  bool ExplicitUnrollAndJam = PragmaEnableUnroll || 
ExplicitUnrollAndJamCount8
;
207
13
208
13
  // If the loop has an unrolling pragma, we want to be more aggressive with
209
13
  // unrolling limits.
210
13
  if (ExplicitUnrollAndJam)
211
7
    UP.UnrollAndJamInnerLoopThreshold = PragmaUnrollAndJamThreshold;
212
13
213
13
  if (!UP.AllowRemainder && getUnrollAndJammedLoopSize(InnerLoopSize, UP) >=
214
0
                                UP.UnrollAndJamInnerLoopThreshold) {
215
0
    LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; can't create remainder and "
216
0
                         "inner loop too large\n");
217
0
    UP.Count = 0;
218
0
    return false;
219
0
  }
220
13
221
13
  // We have a sensible limit for the outer loop, now adjust it for the inner
222
13
  // loop and UP.UnrollAndJamInnerLoopThreshold. If the outer limit was set
223
13
  // explicitly, we want to stick to it.
224
13
  if (!ExplicitUnrollAndJamCount && 
UP.AllowRemainder11
) {
225
17
    while (UP.Count != 0 && getUnrollAndJammedLoopSize(InnerLoopSize, UP) >=
226
17
                                UP.UnrollAndJamInnerLoopThreshold)
227
6
      UP.Count--;
228
11
  }
229
13
230
13
  // If we are explicitly unroll and jamming, we are done. Otherwise there are a
231
13
  // number of extra performance heuristics to check.
232
13
  if (ExplicitUnrollAndJam)
233
7
    return true;
234
6
235
6
  // If the inner loop count is known and small, leave the entire loop nest to
236
6
  // be the unroller
237
6
  if (InnerTripCount && 
InnerLoopSize * InnerTripCount < UP.Threshold1
) {
238
1
    LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; small inner loop count is "
239
1
                         "being left for the unroller\n");
240
1
    UP.Count = 0;
241
1
    return false;
242
1
  }
243
5
244
5
  // Check for situations where UnJ is likely to be unprofitable. Including
245
5
  // subloops with more than 1 block.
246
5
  if (SubLoop->getBlocks().size() != 1) {
247
1
    LLVM_DEBUG(
248
1
        dbgs() << "Won't unroll-and-jam; More than one inner loop block\n");
249
1
    UP.Count = 0;
250
1
    return false;
251
1
  }
252
4
253
4
  // Limit to loops where there is something to gain from unrolling and
254
4
  // jamming the loop. In this case, look for loads that are invariant in the
255
4
  // outer loop and can become shared.
256
4
  unsigned NumInvariant = 0;
257
4
  for (BasicBlock *BB : SubLoop->getBlocks()) {
258
63
    for (Instruction &I : *BB) {
259
63
      if (auto *Ld = dyn_cast<LoadInst>(&I)) {
260
4
        Value *V = Ld->getPointerOperand();
261
4
        const SCEV *LSCEV = SE.getSCEVAtScope(V, L);
262
4
        if (SE.isLoopInvariant(LSCEV, L))
263
3
          NumInvariant++;
264
4
      }
265
63
    }
266
4
  }
267
4
  if (NumInvariant == 0) {
268
1
    LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; No loop invariant loads\n");
269
1
    UP.Count = 0;
270
1
    return false;
271
1
  }
272
3
273
3
  return false;
274
3
}
275
276
static LoopUnrollResult
277
tryToUnrollAndJamLoop(Loop *L, DominatorTree &DT, LoopInfo *LI,
278
                      ScalarEvolution &SE, const TargetTransformInfo &TTI,
279
                      AssumptionCache &AC, DependenceInfo &DI,
280
127
                      OptimizationRemarkEmitter &ORE, int OptLevel) {
281
127
  // Quick checks of the correct loop form
282
127
  if (!L->isLoopSimplifyForm() || L->getSubLoops().size() != 1)
283
65
    return LoopUnrollResult::Unmodified;
284
62
  Loop *SubLoop = L->getSubLoops()[0];
285
62
  if (!SubLoop->isLoopSimplifyForm())
286
0
    return LoopUnrollResult::Unmodified;
287
62
288
62
  BasicBlock *Latch = L->getLoopLatch();
289
62
  BasicBlock *Exit = L->getExitingBlock();
290
62
  BasicBlock *SubLoopLatch = SubLoop->getLoopLatch();
291
62
  BasicBlock *SubLoopExit = SubLoop->getExitingBlock();
292
62
293
62
  if (Latch != Exit || 
SubLoopLatch != SubLoopExit60
)
294
2
    return LoopUnrollResult::Unmodified;
295
60
296
60
  TargetTransformInfo::UnrollingPreferences UP = gatherUnrollingPreferences(
297
60
      L, SE, TTI, nullptr, nullptr, OptLevel,
298
60
      None, None, None, None, None, None);
299
60
  if (AllowUnrollAndJam.getNumOccurrences() > 0)
300
60
    UP.UnrollAndJam = AllowUnrollAndJam;
301
60
  if (UnrollAndJamThreshold.getNumOccurrences() > 0)
302
7
    UP.UnrollAndJamInnerLoopThreshold = UnrollAndJamThreshold;
303
60
  // Exit early if unrolling is disabled.
304
60
  if (!UP.UnrollAndJam || UP.UnrollAndJamInnerLoopThreshold == 0)
305
0
    return LoopUnrollResult::Unmodified;
306
60
307
60
  LLVM_DEBUG(dbgs() << "Loop Unroll and Jam: F["
308
60
                    << L->getHeader()->getParent()->getName() << "] Loop %"
309
60
                    << L->getHeader()->getName() << "\n");
310
60
311
60
  TransformationMode EnableMode = hasUnrollAndJamTransformation(L);
312
60
  if (EnableMode & TM_Disable)
313
3
    return LoopUnrollResult::Unmodified;
314
57
315
57
  // A loop with any unroll pragma (enabling/disabling/count/etc) is left for
316
57
  // the unroller, so long as it does not explicitly have unroll_and_jam
317
57
  // metadata. This means #pragma nounroll will disable unroll and jam as well
318
57
  // as unrolling
319
57
  if (HasAnyUnrollPragma(L, "llvm.loop.unroll.") &&
320
57
      
!HasAnyUnrollPragma(L, "llvm.loop.unroll_and_jam.")6
) {
321
4
    LLVM_DEBUG(dbgs() << "  Disabled due to pragma.\n");
322
4
    return LoopUnrollResult::Unmodified;
323
4
  }
324
53
325
53
  if (!isSafeToUnrollAndJam(L, SE, DT, DI)) {
326
19
    LLVM_DEBUG(dbgs() << "  Disabled due to not being safe.\n");
327
19
    return LoopUnrollResult::Unmodified;
328
19
  }
329
34
330
34
  // Approximate the loop size and collect useful info
331
34
  unsigned NumInlineCandidates;
332
34
  bool NotDuplicatable;
333
34
  bool Convergent;
334
34
  SmallPtrSet<const Value *, 32> EphValues;
335
34
  CodeMetrics::collectEphemeralValues(L, &AC, EphValues);
336
34
  unsigned InnerLoopSize =
337
34
      ApproximateLoopSize(SubLoop, NumInlineCandidates, NotDuplicatable,
338
34
                          Convergent, TTI, EphValues, UP.BEInsns);
339
34
  unsigned OuterLoopSize =
340
34
      ApproximateLoopSize(L, NumInlineCandidates, NotDuplicatable, Convergent,
341
34
                          TTI, EphValues, UP.BEInsns);
342
34
  LLVM_DEBUG(dbgs() << "  Outer Loop Size: " << OuterLoopSize << "\n");
343
34
  LLVM_DEBUG(dbgs() << "  Inner Loop Size: " << InnerLoopSize << "\n");
344
34
  if (NotDuplicatable) {
345
0
    LLVM_DEBUG(dbgs() << "  Not unrolling loop which contains non-duplicatable "
346
0
                         "instructions.\n");
347
0
    return LoopUnrollResult::Unmodified;
348
0
  }
349
34
  if (NumInlineCandidates != 0) {
350
0
    LLVM_DEBUG(dbgs() << "  Not unrolling loop with inlinable calls.\n");
351
0
    return LoopUnrollResult::Unmodified;
352
0
  }
353
34
  if (Convergent) {
354
0
    LLVM_DEBUG(
355
0
        dbgs() << "  Not unrolling loop with convergent instructions.\n");
356
0
    return LoopUnrollResult::Unmodified;
357
0
  }
358
34
359
34
  // Save original loop IDs for after the transformation.
360
34
  MDNode *OrigOuterLoopID = L->getLoopID();
361
34
  MDNode *OrigSubLoopID = SubLoop->getLoopID();
362
34
363
34
  // To assign the loop id of the epilogue, assign it before unrolling it so it
364
34
  // is applied to every inner loop of the epilogue. We later apply the loop ID
365
34
  // for the jammed inner loop.
366
34
  Optional<MDNode *> NewInnerEpilogueLoopID = makeFollowupLoopID(
367
34
      OrigOuterLoopID, {LLVMLoopUnrollAndJamFollowupAll,
368
34
                        LLVMLoopUnrollAndJamFollowupRemainderInner});
369
34
  if (NewInnerEpilogueLoopID.hasValue())
370
1
    SubLoop->setLoopID(NewInnerEpilogueLoopID.getValue());
371
34
372
34
  // Find trip count and trip multiple
373
34
  unsigned OuterTripCount = SE.getSmallConstantTripCount(L, Latch);
374
34
  unsigned OuterTripMultiple = SE.getSmallConstantTripMultiple(L, Latch);
375
34
  unsigned InnerTripCount = SE.getSmallConstantTripCount(SubLoop, SubLoopLatch);
376
34
377
34
  // Decide if, and by how much, to unroll
378
34
  bool IsCountSetExplicitly = computeUnrollAndJamCount(
379
34
      L, SubLoop, TTI, DT, LI, SE, EphValues, &ORE, OuterTripCount,
380
34
      OuterTripMultiple, OuterLoopSize, InnerTripCount, InnerLoopSize, UP);
381
34
  if (UP.Count <= 1)
382
4
    return LoopUnrollResult::Unmodified;
383
30
  // Unroll factor (Count) must be less or equal to TripCount.
384
30
  if (OuterTripCount && 
UP.Count > OuterTripCount5
)
385
2
    UP.Count = OuterTripCount;
386
30
387
30
  Loop *EpilogueOuterLoop = nullptr;
388
30
  LoopUnrollResult UnrollResult = UnrollAndJamLoop(
389
30
      L, UP.Count, OuterTripCount, OuterTripMultiple, UP.UnrollRemainder, LI,
390
30
      &SE, &DT, &AC, &ORE, &EpilogueOuterLoop);
391
30
392
30
  // Assign new loop attributes.
393
30
  if (EpilogueOuterLoop) {
394
17
    Optional<MDNode *> NewOuterEpilogueLoopID = makeFollowupLoopID(
395
17
        OrigOuterLoopID, {LLVMLoopUnrollAndJamFollowupAll,
396
17
                          LLVMLoopUnrollAndJamFollowupRemainderOuter});
397
17
    if (NewOuterEpilogueLoopID.hasValue())
398
0
      EpilogueOuterLoop->setLoopID(NewOuterEpilogueLoopID.getValue());
399
17
  }
400
30
401
30
  Optional<MDNode *> NewInnerLoopID =
402
30
      makeFollowupLoopID(OrigOuterLoopID, {LLVMLoopUnrollAndJamFollowupAll,
403
30
                                           LLVMLoopUnrollAndJamFollowupInner});
404
30
  if (NewInnerLoopID.hasValue())
405
1
    SubLoop->setLoopID(NewInnerLoopID.getValue());
406
29
  else
407
29
    SubLoop->setLoopID(OrigSubLoopID);
408
30
409
30
  if (UnrollResult == LoopUnrollResult::PartiallyUnrolled) {
410
27
    Optional<MDNode *> NewOuterLoopID = makeFollowupLoopID(
411
27
        OrigOuterLoopID,
412
27
        {LLVMLoopUnrollAndJamFollowupAll, LLVMLoopUnrollAndJamFollowupOuter});
413
27
    if (NewOuterLoopID.hasValue()) {
414
1
      L->setLoopID(NewOuterLoopID.getValue());
415
1
416
1
      // Do not setLoopAlreadyUnrolled if a followup was given.
417
1
      return UnrollResult;
418
1
    }
419
29
  }
420
29
421
29
  // If loop has an unroll count pragma or unrolled by explicitly set count
422
29
  // mark loop as unrolled to prevent unrolling beyond that requested.
423
29
  if (UnrollResult != LoopUnrollResult::FullyUnrolled && 
IsCountSetExplicitly26
)
424
24
    L->setLoopAlreadyUnrolled();
425
29
426
29
  return UnrollResult;
427
29
}
428
429
namespace {
430
431
class LoopUnrollAndJam : public LoopPass {
432
public:
433
  static char ID; // Pass ID, replacement for typeid
434
  unsigned OptLevel;
435
436
11
  LoopUnrollAndJam(int OptLevel = 2) : LoopPass(ID), OptLevel(OptLevel) {
437
11
    initializeLoopUnrollAndJamPass(*PassRegistry::getPassRegistry());
438
11
  }
439
440
127
  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
441
127
    if (skipLoop(L))
442
0
      return false;
443
127
444
127
    Function &F = *L->getHeader()->getParent();
445
127
446
127
    auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
447
127
    LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
448
127
    ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
449
127
    const TargetTransformInfo &TTI =
450
127
        getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
451
127
    auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
452
127
    auto &DI = getAnalysis<DependenceAnalysisWrapperPass>().getDI();
453
127
    // For the old PM, we can't use OptimizationRemarkEmitter as an analysis
454
127
    // pass.  Function analyses need to be preserved across loop transformations
455
127
    // but ORE cannot be preserved (see comment before the pass definition).
456
127
    OptimizationRemarkEmitter ORE(&F);
457
127
458
127
    LoopUnrollResult Result =
459
127
        tryToUnrollAndJamLoop(L, DT, LI, SE, TTI, AC, DI, ORE, OptLevel);
460
127
461
127
    if (Result == LoopUnrollResult::FullyUnrolled)
462
3
      LPM.markLoopAsDeleted(*L);
463
127
464
127
    return Result != LoopUnrollResult::Unmodified;
465
127
  }
466
467
  /// This transformation requires natural loop information & requires that
468
  /// loop preheaders be inserted into the CFG...
469
11
  void getAnalysisUsage(AnalysisUsage &AU) const override {
470
11
    AU.addRequired<AssumptionCacheTracker>();
471
11
    AU.addRequired<TargetTransformInfoWrapperPass>();
472
11
    AU.addRequired<DependenceAnalysisWrapperPass>();
473
11
    getLoopAnalysisUsage(AU);
474
11
  }
475
};
476
477
} // end anonymous namespace
478
479
char LoopUnrollAndJam::ID = 0;
480
481
36.0k
INITIALIZE_PASS_BEGIN(LoopUnrollAndJam, "loop-unroll-and-jam",
482
36.0k
                      "Unroll and Jam loops", false, false)
483
36.0k
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
484
36.0k
INITIALIZE_PASS_DEPENDENCY(LoopPass)
485
36.0k
INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
486
36.0k
INITIALIZE_PASS_DEPENDENCY(DependenceAnalysisWrapperPass)
487
36.0k
INITIALIZE_PASS_END(LoopUnrollAndJam, "loop-unroll-and-jam",
488
                    "Unroll and Jam loops", false, false)
489
490
0
Pass *llvm::createLoopUnrollAndJamPass(int OptLevel) {
491
0
  return new LoopUnrollAndJam(OptLevel);
492
0
}
493
494
PreservedAnalyses LoopUnrollAndJamPass::run(Loop &L, LoopAnalysisManager &AM,
495
                                            LoopStandardAnalysisResults &AR,
496
0
                                            LPMUpdater &) {
497
0
  const auto &FAM =
498
0
      AM.getResult<FunctionAnalysisManagerLoopProxy>(L, AR).getManager();
499
0
  Function *F = L.getHeader()->getParent();
500
0
501
0
  auto *ORE = FAM.getCachedResult<OptimizationRemarkEmitterAnalysis>(*F);
502
0
  // FIXME: This should probably be optional rather than required.
503
0
  if (!ORE)
504
0
    report_fatal_error(
505
0
        "LoopUnrollAndJamPass: OptimizationRemarkEmitterAnalysis not cached at "
506
0
        "a higher level");
507
0
508
0
  DependenceInfo DI(F, &AR.AA, &AR.SE, &AR.LI);
509
0
510
0
  LoopUnrollResult Result = tryToUnrollAndJamLoop(
511
0
      &L, AR.DT, &AR.LI, AR.SE, AR.TTI, AR.AC, DI, *ORE, OptLevel);
512
0
513
0
  if (Result == LoopUnrollResult::Unmodified)
514
0
    return PreservedAnalyses::all();
515
0
516
0
  return getLoopPassPreservedAnalyses();
517
0
}