Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Scalar/LoopVersioningLICM.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- LoopVersioningLICM.cpp - LICM Loop Versioning ----------------------===//
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
// When alias analysis is uncertain about the aliasing between any two accesses,
10
// it will return MayAlias. This uncertainty from alias analysis restricts LICM
11
// from proceeding further. In cases where alias analysis is uncertain we might
12
// use loop versioning as an alternative.
13
//
14
// Loop Versioning will create a version of the loop with aggressive aliasing
15
// assumptions in addition to the original with conservative (default) aliasing
16
// assumptions. The version of the loop making aggressive aliasing assumptions
17
// will have all the memory accesses marked as no-alias. These two versions of
18
// loop will be preceded by a memory runtime check. This runtime check consists
19
// of bound checks for all unique memory accessed in loop, and it ensures the
20
// lack of memory aliasing. The result of the runtime check determines which of
21
// the loop versions is executed: If the runtime check detects any memory
22
// aliasing, then the original loop is executed. Otherwise, the version with
23
// aggressive aliasing assumptions is used.
24
//
25
// Following are the top level steps:
26
//
27
// a) Perform LoopVersioningLICM's feasibility check.
28
// b) If loop is a candidate for versioning then create a memory bound check,
29
//    by considering all the memory accesses in loop body.
30
// c) Clone original loop and set all memory accesses as no-alias in new loop.
31
// d) Set original loop & versioned loop as a branch target of the runtime check
32
//    result.
33
//
34
// It transforms loop as shown below:
35
//
36
//                         +----------------+
37
//                         |Runtime Memcheck|
38
//                         +----------------+
39
//                                 |
40
//              +----------+----------------+----------+
41
//              |                                      |
42
//    +---------+----------+               +-----------+----------+
43
//    |Orig Loop Preheader |               |Cloned Loop Preheader |
44
//    +--------------------+               +----------------------+
45
//              |                                      |
46
//    +--------------------+               +----------------------+
47
//    |Orig Loop Body      |               |Cloned Loop Body      |
48
//    +--------------------+               +----------------------+
49
//              |                                      |
50
//    +--------------------+               +----------------------+
51
//    |Orig Loop Exit Block|               |Cloned Loop Exit Block|
52
//    +--------------------+               +-----------+----------+
53
//              |                                      |
54
//              +----------+--------------+-----------+
55
//                                 |
56
//                           +-----+----+
57
//                           |Join Block|
58
//                           +----------+
59
//
60
//===----------------------------------------------------------------------===//
61
62
#include "llvm/ADT/SmallVector.h"
63
#include "llvm/ADT/StringRef.h"
64
#include "llvm/Analysis/AliasAnalysis.h"
65
#include "llvm/Analysis/AliasSetTracker.h"
66
#include "llvm/Analysis/GlobalsModRef.h"
67
#include "llvm/Analysis/LoopAccessAnalysis.h"
68
#include "llvm/Analysis/LoopInfo.h"
69
#include "llvm/Analysis/LoopPass.h"
70
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
71
#include "llvm/Analysis/ScalarEvolution.h"
72
#include "llvm/IR/CallSite.h"
73
#include "llvm/IR/Constants.h"
74
#include "llvm/IR/Dominators.h"
75
#include "llvm/IR/Instruction.h"
76
#include "llvm/IR/Instructions.h"
77
#include "llvm/IR/LLVMContext.h"
78
#include "llvm/IR/MDBuilder.h"
79
#include "llvm/IR/Metadata.h"
80
#include "llvm/IR/Type.h"
81
#include "llvm/IR/Value.h"
82
#include "llvm/Pass.h"
83
#include "llvm/Support/Casting.h"
84
#include "llvm/Support/CommandLine.h"
85
#include "llvm/Support/Debug.h"
86
#include "llvm/Support/raw_ostream.h"
87
#include "llvm/Transforms/Scalar.h"
88
#include "llvm/Transforms/Utils.h"
89
#include "llvm/Transforms/Utils/LoopUtils.h"
90
#include "llvm/Transforms/Utils/LoopVersioning.h"
91
#include <cassert>
92
#include <memory>
93
94
using namespace llvm;
95
96
0
#define DEBUG_TYPE "loop-versioning-licm"
97
98
static const char *LICMVersioningMetaData = "llvm.loop.licm_versioning.disable";
99
100
/// Threshold minimum allowed percentage for possible
101
/// invariant instructions in a loop.
102
static cl::opt<float>
103
    LVInvarThreshold("licm-versioning-invariant-threshold",
104
                     cl::desc("LoopVersioningLICM's minimum allowed percentage"
105
                              "of possible invariant instructions per loop"),
106
                     cl::init(25), cl::Hidden);
107
108
/// Threshold for maximum allowed loop nest/depth
109
static cl::opt<unsigned> LVLoopDepthThreshold(
110
    "licm-versioning-max-depth-threshold",
111
    cl::desc(
112
        "LoopVersioningLICM's threshold for maximum allowed loop nest/depth"),
113
    cl::init(2), cl::Hidden);
114
115
/// Create MDNode for input string.
116
3
static MDNode *createStringMetadata(Loop *TheLoop, StringRef Name, unsigned V) {
117
3
  LLVMContext &Context = TheLoop->getHeader()->getContext();
118
3
  Metadata *MDs[] = {
119
3
      MDString::get(Context, Name),
120
3
      ConstantAsMetadata::get(ConstantInt::get(Type::getInt32Ty(Context), V))};
121
3
  return MDNode::get(Context, MDs);
122
3
}
123
124
/// Set input string into loop metadata by keeping other values intact.
125
void llvm::addStringMetadataToLoop(Loop *TheLoop, const char *MDString,
126
3
                                   unsigned V) {
127
3
  SmallVector<Metadata *, 4> MDs(1);
128
3
  // If the loop already has metadata, retain it.
129
3
  MDNode *LoopID = TheLoop->getLoopID();
130
3
  if (LoopID) {
131
2
    for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; 
++i1
) {
132
1
      MDNode *Node = cast<MDNode>(LoopID->getOperand(i));
133
1
      MDs.push_back(Node);
134
1
    }
135
1
  }
136
3
  // Add new metadata.
137
3
  MDs.push_back(createStringMetadata(TheLoop, MDString, V));
138
3
  // Replace current metadata node with new one.
139
3
  LLVMContext &Context = TheLoop->getHeader()->getContext();
140
3
  MDNode *NewLoopID = MDNode::get(Context, MDs);
141
3
  // Set operand 0 to refer to the loop id itself.
142
3
  NewLoopID->replaceOperandWith(0, NewLoopID);
143
3
  TheLoop->setLoopID(NewLoopID);
144
3
}
145
146
namespace {
147
148
struct LoopVersioningLICM : public LoopPass {
149
  static char ID;
150
151
  LoopVersioningLICM()
152
      : LoopPass(ID), LoopDepthThreshold(LVLoopDepthThreshold),
153
2
        InvariantThreshold(LVInvarThreshold) {
154
2
    initializeLoopVersioningLICMPass(*PassRegistry::getPassRegistry());
155
2
  }
156
157
  bool runOnLoop(Loop *L, LPPassManager &LPM) override;
158
159
2
  void getAnalysisUsage(AnalysisUsage &AU) const override {
160
2
    AU.setPreservesCFG();
161
2
    AU.addRequired<AAResultsWrapperPass>();
162
2
    AU.addRequired<DominatorTreeWrapperPass>();
163
2
    AU.addRequiredID(LCSSAID);
164
2
    AU.addRequired<LoopAccessLegacyAnalysis>();
165
2
    AU.addRequired<LoopInfoWrapperPass>();
166
2
    AU.addRequiredID(LoopSimplifyID);
167
2
    AU.addRequired<ScalarEvolutionWrapperPass>();
168
2
    AU.addPreserved<AAResultsWrapperPass>();
169
2
    AU.addPreserved<GlobalsAAWrapperPass>();
170
2
    AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
171
2
  }
172
173
8
  StringRef getPassName() const override { return "Loop Versioning for LICM"; }
174
175
8
  void reset() {
176
8
    AA = nullptr;
177
8
    SE = nullptr;
178
8
    LAA = nullptr;
179
8
    CurLoop = nullptr;
180
8
    LoadAndStoreCounter = 0;
181
8
    InvariantCounter = 0;
182
8
    IsReadOnlyLoop = true;
183
8
    ORE = nullptr;
184
8
    CurAST.reset();
185
8
  }
186
187
  class AutoResetter {
188
  public:
189
8
    AutoResetter(LoopVersioningLICM &LVLICM) : LVLICM(LVLICM) {}
190
8
    ~AutoResetter() { LVLICM.reset(); }
191
192
  private:
193
    LoopVersioningLICM &LVLICM;
194
  };
195
196
private:
197
  // Current AliasAnalysis information
198
  AliasAnalysis *AA = nullptr;
199
200
  // Current ScalarEvolution
201
  ScalarEvolution *SE = nullptr;
202
203
  // Current LoopAccessAnalysis
204
  LoopAccessLegacyAnalysis *LAA = nullptr;
205
206
  // Current Loop's LoopAccessInfo
207
  const LoopAccessInfo *LAI = nullptr;
208
209
  // The current loop we are working on.
210
  Loop *CurLoop = nullptr;
211
212
  // AliasSet information for the current loop.
213
  std::unique_ptr<AliasSetTracker> CurAST;
214
215
  // Maximum loop nest threshold
216
  unsigned LoopDepthThreshold;
217
218
  // Minimum invariant threshold
219
  float InvariantThreshold;
220
221
  // Counter to track num of load & store
222
  unsigned LoadAndStoreCounter = 0;
223
224
  // Counter to track num of invariant
225
  unsigned InvariantCounter = 0;
226
227
  // Read only loop marker.
228
  bool IsReadOnlyLoop = true;
229
230
  // OptimizationRemarkEmitter
231
  OptimizationRemarkEmitter *ORE;
232
233
  bool isLegalForVersioning();
234
  bool legalLoopStructure();
235
  bool legalLoopInstructions();
236
  bool legalLoopMemoryAccesses();
237
  bool isLoopAlreadyVisited();
238
  void setNoAliasToLoop(Loop *VerLoop);
239
  bool instructionSafeForVersioning(Instruction *I);
240
};
241
242
} // end anonymous namespace
243
244
/// Check loop structure and confirms it's good for LoopVersioningLICM.
245
7
bool LoopVersioningLICM::legalLoopStructure() {
246
7
  // Loop must be in loop simplify form.
247
7
  if (!CurLoop->isLoopSimplifyForm()) {
248
0
    LLVM_DEBUG(dbgs() << "    loop is not in loop-simplify form.\n");
249
0
    return false;
250
0
  }
251
7
  // Loop should be innermost loop, if not return false.
252
7
  if (!CurLoop->getSubLoops().empty()) {
253
4
    LLVM_DEBUG(dbgs() << "    loop is not innermost\n");
254
4
    return false;
255
4
  }
256
3
  // Loop should have a single backedge, if not return false.
257
3
  if (CurLoop->getNumBackEdges() != 1) {
258
0
    LLVM_DEBUG(dbgs() << "    loop has multiple backedges\n");
259
0
    return false;
260
0
  }
261
3
  // Loop must have a single exiting block, if not return false.
262
3
  if (!CurLoop->getExitingBlock()) {
263
0
    LLVM_DEBUG(dbgs() << "    loop has multiple exiting block\n");
264
0
    return false;
265
0
  }
266
3
  // We only handle bottom-tested loop, i.e. loop in which the condition is
267
3
  // checked at the end of each iteration. With that we can assume that all
268
3
  // instructions in the loop are executed the same number of times.
269
3
  if (CurLoop->getExitingBlock() != CurLoop->getLoopLatch()) {
270
0
    LLVM_DEBUG(dbgs() << "    loop is not bottom tested\n");
271
0
    return false;
272
0
  }
273
3
  // Parallel loops must not have aliasing loop-invariant memory accesses.
274
3
  // Hence we don't need to version anything in this case.
275
3
  if (CurLoop->isAnnotatedParallel()) {
276
0
    LLVM_DEBUG(dbgs() << "    Parallel loop is not worth versioning\n");
277
0
    return false;
278
0
  }
279
3
  // Loop depth more then LoopDepthThreshold are not allowed
280
3
  if (CurLoop->getLoopDepth() > LoopDepthThreshold) {
281
0
    LLVM_DEBUG(dbgs() << "    loop depth is more then threshold\n");
282
0
    return false;
283
0
  }
284
3
  // We need to be able to compute the loop trip count in order
285
3
  // to generate the bound checks.
286
3
  const SCEV *ExitCount = SE->getBackedgeTakenCount(CurLoop);
287
3
  if (ExitCount == SE->getCouldNotCompute()) {
288
0
    LLVM_DEBUG(dbgs() << "    loop does not has trip count\n");
289
0
    return false;
290
0
  }
291
3
  return true;
292
3
}
293
294
/// Check memory accesses in loop and confirms it's good for
295
/// LoopVersioningLICM.
296
1
bool LoopVersioningLICM::legalLoopMemoryAccesses() {
297
1
  bool HasMayAlias = false;
298
1
  bool TypeSafety = false;
299
1
  bool HasMod = false;
300
1
  // Memory check:
301
1
  // Transform phase will generate a versioned loop and also a runtime check to
302
1
  // ensure the pointers are independent and they don’t alias.
303
1
  // In version variant of loop, alias meta data asserts that all access are
304
1
  // mutually independent.
305
1
  //
306
1
  // Pointers aliasing in alias domain are avoided because with multiple
307
1
  // aliasing domains we may not be able to hoist potential loop invariant
308
1
  // access out of the loop.
309
1
  //
310
1
  // Iterate over alias tracker sets, and confirm AliasSets doesn't have any
311
1
  // must alias set.
312
1
  for (const auto &I : *CurAST) {
313
1
    const AliasSet &AS = I;
314
1
    // Skip Forward Alias Sets, as this should be ignored as part of
315
1
    // the AliasSetTracker object.
316
1
    if (AS.isForwardingAliasSet())
317
0
      continue;
318
1
    // With MustAlias its not worth adding runtime bound check.
319
1
    if (AS.isMustAlias())
320
0
      return false;
321
1
    Value *SomePtr = AS.begin()->getValue();
322
1
    bool TypeCheck = true;
323
1
    // Check for Mod & MayAlias
324
1
    HasMayAlias |= AS.isMayAlias();
325
1
    HasMod |= AS.isMod();
326
2
    for (const auto &A : AS) {
327
2
      Value *Ptr = A.getValue();
328
2
      // Alias tracker should have pointers of same data type.
329
2
      TypeCheck = (TypeCheck && (SomePtr->getType() == Ptr->getType()));
330
2
    }
331
1
    // At least one alias tracker should have pointers of same data type.
332
1
    TypeSafety |= TypeCheck;
333
1
  }
334
1
  // Ensure types should be of same type.
335
1
  if (!TypeSafety) {
336
0
    LLVM_DEBUG(dbgs() << "    Alias tracker type safety failed!\n");
337
0
    return false;
338
0
  }
339
1
  // Ensure loop body shouldn't be read only.
340
1
  if (!HasMod) {
341
0
    LLVM_DEBUG(dbgs() << "    No memory modified in loop body\n");
342
0
    return false;
343
0
  }
344
1
  // Make sure alias set has may alias case.
345
1
  // If there no alias memory ambiguity, return false.
346
1
  if (!HasMayAlias) {
347
0
    LLVM_DEBUG(dbgs() << "    No ambiguity in memory access.\n");
348
0
    return false;
349
0
  }
350
1
  return true;
351
1
}
352
353
/// Check loop instructions safe for Loop versioning.
354
/// It returns true if it's safe else returns false.
355
/// Consider following:
356
/// 1) Check all load store in loop body are non atomic & non volatile.
357
/// 2) Check function call safety, by ensuring its not accessing memory.
358
/// 3) Loop body shouldn't have any may throw instruction.
359
/// 4) Loop body shouldn't have any convergent or noduplicate instructions.
360
22
bool LoopVersioningLICM::instructionSafeForVersioning(Instruction *I) {
361
22
  assert(I != nullptr && "Null instruction found!");
362
22
  // Check function call safety
363
22
  if (auto *Call = dyn_cast<CallBase>(I)) {
364
2
    if (Call->isConvergent() || 
Call->cannotDuplicate()1
) {
365
2
      LLVM_DEBUG(dbgs() << "    Convergent call site found.\n");
366
2
      return false;
367
2
    }
368
0
369
0
    if (!AA->doesNotAccessMemory(Call)) {
370
0
      LLVM_DEBUG(dbgs() << "    Unsafe call site found.\n");
371
0
      return false;
372
0
    }
373
20
  }
374
20
375
20
  // Avoid loops with possiblity of throw
376
20
  if (I->mayThrow()) {
377
0
    LLVM_DEBUG(dbgs() << "    May throw instruction found in loop body\n");
378
0
    return false;
379
0
  }
380
20
  // If current instruction is load instructions
381
20
  // make sure it's a simple load (non atomic & non volatile)
382
20
  if (I->mayReadFromMemory()) {
383
3
    LoadInst *Ld = dyn_cast<LoadInst>(I);
384
3
    if (!Ld || !Ld->isSimple()) {
385
0
      LLVM_DEBUG(dbgs() << "    Found a non-simple load.\n");
386
0
      return false;
387
0
    }
388
3
    LoadAndStoreCounter++;
389
3
    Value *Ptr = Ld->getPointerOperand();
390
3
    // Check loop invariant.
391
3
    if (SE->isLoopInvariant(SE->getSCEV(Ptr), CurLoop))
392
3
      InvariantCounter++;
393
3
  }
394
17
  // If current instruction is store instruction
395
17
  // make sure it's a simple store (non atomic & non volatile)
396
17
  else if (I->mayWriteToMemory()) {
397
4
    StoreInst *St = dyn_cast<StoreInst>(I);
398
4
    if (!St || !St->isSimple()) {
399
0
      LLVM_DEBUG(dbgs() << "    Found a non-simple store.\n");
400
0
      return false;
401
0
    }
402
4
    LoadAndStoreCounter++;
403
4
    Value *Ptr = St->getPointerOperand();
404
4
    // Check loop invariant.
405
4
    if (SE->isLoopInvariant(SE->getSCEV(Ptr), CurLoop))
406
1
      InvariantCounter++;
407
4
408
4
    IsReadOnlyLoop = false;
409
4
  }
410
20
  return true;
411
20
}
412
413
/// Check loop instructions and confirms it's good for
414
/// LoopVersioningLICM.
415
3
bool LoopVersioningLICM::legalLoopInstructions() {
416
3
  // Resetting counters.
417
3
  LoadAndStoreCounter = 0;
418
3
  InvariantCounter = 0;
419
3
  IsReadOnlyLoop = true;
420
3
  using namespace ore;
421
3
  // Iterate over loop blocks and instructions of each block and check
422
3
  // instruction safety.
423
3
  for (auto *Block : CurLoop->getBlocks())
424
22
    
for (auto &Inst : *Block)3
{
425
22
      // If instruction is unsafe just return false.
426
22
      if (!instructionSafeForVersioning(&Inst)) {
427
2
        ORE->emit([&]() {
428
0
          return OptimizationRemarkMissed(DEBUG_TYPE, "IllegalLoopInst", &Inst)
429
0
                 << " Unsafe Loop Instruction";
430
0
        });
431
2
        return false;
432
2
      }
433
22
    }
434
3
  // Get LoopAccessInfo from current loop.
435
3
  LAI = &LAA->getInfo(CurLoop);
436
1
  // Check LoopAccessInfo for need of runtime check.
437
1
  if (LAI->getRuntimePointerChecking()->getChecks().empty()) {
438
0
    LLVM_DEBUG(dbgs() << "    LAA: Runtime check not found !!\n");
439
0
    return false;
440
0
  }
441
1
  // Number of runtime-checks should be less then RuntimeMemoryCheckThreshold
442
1
  if (LAI->getNumRuntimePointerChecks() >
443
1
      VectorizerParams::RuntimeMemoryCheckThreshold) {
444
0
    LLVM_DEBUG(
445
0
        dbgs() << "    LAA: Runtime checks are more than threshold !!\n");
446
0
    ORE->emit([&]() {
447
0
      return OptimizationRemarkMissed(DEBUG_TYPE, "RuntimeCheck",
448
0
                                      CurLoop->getStartLoc(),
449
0
                                      CurLoop->getHeader())
450
0
             << "Number of runtime checks "
451
0
             << NV("RuntimeChecks", LAI->getNumRuntimePointerChecks())
452
0
             << " exceeds threshold "
453
0
             << NV("Threshold", VectorizerParams::RuntimeMemoryCheckThreshold);
454
0
    });
455
0
    return false;
456
0
  }
457
1
  // Loop should have at least one invariant load or store instruction.
458
1
  if (!InvariantCounter) {
459
0
    LLVM_DEBUG(dbgs() << "    Invariant not found !!\n");
460
0
    return false;
461
0
  }
462
1
  // Read only loop not allowed.
463
1
  if (IsReadOnlyLoop) {
464
0
    LLVM_DEBUG(dbgs() << "    Found a read-only loop!\n");
465
0
    return false;
466
0
  }
467
1
  // Profitablity check:
468
1
  // Check invariant threshold, should be in limit.
469
1
  if (InvariantCounter * 100 < InvariantThreshold * LoadAndStoreCounter) {
470
0
    LLVM_DEBUG(
471
0
        dbgs()
472
0
        << "    Invariant load & store are less then defined threshold\n");
473
0
    LLVM_DEBUG(dbgs() << "    Invariant loads & stores: "
474
0
                      << ((InvariantCounter * 100) / LoadAndStoreCounter)
475
0
                      << "%\n");
476
0
    LLVM_DEBUG(dbgs() << "    Invariant loads & store threshold: "
477
0
                      << InvariantThreshold << "%\n");
478
0
    ORE->emit([&]() {
479
0
      return OptimizationRemarkMissed(DEBUG_TYPE, "InvariantThreshold",
480
0
                                      CurLoop->getStartLoc(),
481
0
                                      CurLoop->getHeader())
482
0
             << "Invariant load & store "
483
0
             << NV("LoadAndStoreCounter",
484
0
                   ((InvariantCounter * 100) / LoadAndStoreCounter))
485
0
             << " are less then defined threshold "
486
0
             << NV("Threshold", InvariantThreshold);
487
0
    });
488
0
    return false;
489
0
  }
490
1
  return true;
491
1
}
492
493
/// It checks loop is already visited or not.
494
/// check loop meta data, if loop revisited return true
495
/// else false.
496
7
bool LoopVersioningLICM::isLoopAlreadyVisited() {
497
7
  // Check LoopVersioningLICM metadata into loop
498
7
  if (findStringMetadataForLoop(CurLoop, LICMVersioningMetaData)) {
499
0
    return true;
500
0
  }
501
7
  return false;
502
7
}
503
504
/// Checks legality for LoopVersioningLICM by considering following:
505
/// a) loop structure legality   b) loop instruction legality
506
/// c) loop memory access legality.
507
/// Return true if legal else returns false.
508
7
bool LoopVersioningLICM::isLegalForVersioning() {
509
7
  using namespace ore;
510
7
  LLVM_DEBUG(dbgs() << "Loop: " << *CurLoop);
511
7
  // Make sure not re-visiting same loop again.
512
7
  if (isLoopAlreadyVisited()) {
513
0
    LLVM_DEBUG(
514
0
        dbgs() << "    Revisiting loop in LoopVersioningLICM not allowed.\n\n");
515
0
    return false;
516
0
  }
517
7
  // Check loop structure leagality.
518
7
  if (!legalLoopStructure()) {
519
4
    LLVM_DEBUG(
520
4
        dbgs() << "    Loop structure not suitable for LoopVersioningLICM\n\n");
521
4
    ORE->emit([&]() {
522
0
      return OptimizationRemarkMissed(DEBUG_TYPE, "IllegalLoopStruct",
523
0
                                      CurLoop->getStartLoc(),
524
0
                                      CurLoop->getHeader())
525
0
             << " Unsafe Loop structure";
526
0
    });
527
4
    return false;
528
4
  }
529
3
  // Check loop instruction leagality.
530
3
  if (!legalLoopInstructions()) {
531
2
    LLVM_DEBUG(
532
2
        dbgs()
533
2
        << "    Loop instructions not suitable for LoopVersioningLICM\n\n");
534
2
    return false;
535
2
  }
536
1
  // Check loop memory access leagality.
537
1
  if (!legalLoopMemoryAccesses()) {
538
0
    LLVM_DEBUG(
539
0
        dbgs()
540
0
        << "    Loop memory access not suitable for LoopVersioningLICM\n\n");
541
0
    ORE->emit([&]() {
542
0
      return OptimizationRemarkMissed(DEBUG_TYPE, "IllegalLoopMemoryAccess",
543
0
                                      CurLoop->getStartLoc(),
544
0
                                      CurLoop->getHeader())
545
0
             << " Unsafe Loop memory access";
546
0
    });
547
0
    return false;
548
0
  }
549
1
  // Loop versioning is feasible, return true.
550
1
  LLVM_DEBUG(dbgs() << "    Loop Versioning found to be beneficial\n\n");
551
1
  ORE->emit([&]() {
552
0
    return OptimizationRemark(DEBUG_TYPE, "IsLegalForVersioning",
553
0
                              CurLoop->getStartLoc(), CurLoop->getHeader())
554
0
           << " Versioned loop for LICM."
555
0
           << " Number of runtime checks we had to insert "
556
0
           << NV("RuntimeChecks", LAI->getNumRuntimePointerChecks());
557
0
  });
558
1
  return true;
559
1
}
560
561
/// Update loop with aggressive aliasing assumptions.
562
/// It marks no-alias to any pairs of memory operations by assuming
563
/// loop should not have any must-alias memory accesses pairs.
564
/// During LoopVersioningLICM legality we ignore loops having must
565
/// aliasing memory accesses.
566
1
void LoopVersioningLICM::setNoAliasToLoop(Loop *VerLoop) {
567
1
  // Get latch terminator instruction.
568
1
  Instruction *I = VerLoop->getLoopLatch()->getTerminator();
569
1
  // Create alias scope domain.
570
1
  MDBuilder MDB(I->getContext());
571
1
  MDNode *NewDomain = MDB.createAnonymousAliasScopeDomain("LVDomain");
572
1
  StringRef Name = "LVAliasScope";
573
1
  SmallVector<Metadata *, 4> Scopes, NoAliases;
574
1
  MDNode *NewScope = MDB.createAnonymousAliasScope(NewDomain, Name);
575
1
  // Iterate over each instruction of loop.
576
1
  // set no-alias for all load & store instructions.
577
1
  for (auto *Block : CurLoop->getBlocks()) {
578
10
    for (auto &Inst : *Block) {
579
10
      // Only interested in instruction that may modify or read memory.
580
10
      if (!Inst.mayReadFromMemory() && 
!Inst.mayWriteToMemory()9
)
581
7
        continue;
582
3
      Scopes.push_back(NewScope);
583
3
      NoAliases.push_back(NewScope);
584
3
      // Set no-alias for current instruction.
585
3
      Inst.setMetadata(
586
3
          LLVMContext::MD_noalias,
587
3
          MDNode::concatenate(Inst.getMetadata(LLVMContext::MD_noalias),
588
3
                              MDNode::get(Inst.getContext(), NoAliases)));
589
3
      // set alias-scope for current instruction.
590
3
      Inst.setMetadata(
591
3
          LLVMContext::MD_alias_scope,
592
3
          MDNode::concatenate(Inst.getMetadata(LLVMContext::MD_alias_scope),
593
3
                              MDNode::get(Inst.getContext(), Scopes)));
594
3
    }
595
1
  }
596
1
}
597
598
8
bool LoopVersioningLICM::runOnLoop(Loop *L, LPPassManager &LPM) {
599
8
  // This will automatically release all resources hold by the current
600
8
  // LoopVersioningLICM object.
601
8
  AutoResetter Resetter(*this);
602
8
603
8
  if (skipLoop(L))
604
0
    return false;
605
8
606
8
  // Do not do the transformation if disabled by metadata.
607
8
  if (hasLICMVersioningTransformation(L) & TM_Disable)
608
1
    return false;
609
7
610
7
  // Get Analysis information.
611
7
  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
612
7
  SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
613
7
  LAA = &getAnalysis<LoopAccessLegacyAnalysis>();
614
7
  ORE = &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
615
7
  LAI = nullptr;
616
7
  // Set Current Loop
617
7
  CurLoop = L;
618
7
  CurAST.reset(new AliasSetTracker(*AA));
619
7
620
7
  // Loop over the body of this loop, construct AST.
621
7
  LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
622
26
  for (auto *Block : L->getBlocks()) {
623
26
    if (LI->getLoopFor(Block) == L) // Ignore blocks in subloop.
624
21
      CurAST->add(*Block);          // Incorporate the specified basic block
625
26
  }
626
7
627
7
  bool Changed = false;
628
7
629
7
  // Check feasiblity of LoopVersioningLICM.
630
7
  // If versioning found to be feasible and beneficial then proceed
631
7
  // else simply return, by cleaning up memory.
632
7
  if (isLegalForVersioning()) {
633
1
    // Do loop versioning.
634
1
    // Create memcheck for memory accessed inside loop.
635
1
    // Clone original loop, and set blocks properly.
636
1
    DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
637
1
    LoopVersioning LVer(*LAI, CurLoop, LI, DT, SE, true);
638
1
    LVer.versionLoop();
639
1
    // Set Loop Versioning metaData for original loop.
640
1
    addStringMetadataToLoop(LVer.getNonVersionedLoop(), LICMVersioningMetaData);
641
1
    // Set Loop Versioning metaData for version loop.
642
1
    addStringMetadataToLoop(LVer.getVersionedLoop(), LICMVersioningMetaData);
643
1
    // Set "llvm.mem.parallel_loop_access" metaData to versioned loop.
644
1
    // FIXME: "llvm.mem.parallel_loop_access" annotates memory access
645
1
    // instructions, not loops.
646
1
    addStringMetadataToLoop(LVer.getVersionedLoop(),
647
1
                            "llvm.mem.parallel_loop_access");
648
1
    // Update version loop with aggressive aliasing assumption.
649
1
    setNoAliasToLoop(LVer.getVersionedLoop());
650
1
    Changed = true;
651
1
  }
652
7
  return Changed;
653
7
}
654
655
char LoopVersioningLICM::ID = 0;
656
657
36.0k
INITIALIZE_PASS_BEGIN(LoopVersioningLICM, "loop-versioning-licm",
658
36.0k
                      "Loop Versioning For LICM", false, false)
659
36.0k
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
660
36.0k
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
661
36.0k
INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
662
36.0k
INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
663
36.0k
INITIALIZE_PASS_DEPENDENCY(LoopAccessLegacyAnalysis)
664
36.0k
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
665
36.0k
INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
666
36.0k
INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
667
36.0k
INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)
668
36.0k
INITIALIZE_PASS_END(LoopVersioningLICM, "loop-versioning-licm",
669
                    "Loop Versioning For LICM", false, false)
670
671
0
Pass *llvm::createLoopVersioningLICMPass() { return new LoopVersioningLICM(); }