← Back to branch summary

~pali/+junk/llvm-toolchain-3.7

« back to all changes in this revision

Viewing changes to include/llvm/Analysis/LoopAccessAnalysis.h

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2015-07-15 17:51:08 UTC
  • Revision ID: package-import@ubuntu.com-20150715175108-l8mynwovkx4zx697
Tags: upstream-3.7~+rc2
Import upstream version 3.7~+rc2

Show diffs side-by-side

added added

removed removed

Lines of Context:
include/llvm/Analysis/LoopAccessAnalysis.h
 
1
//===- llvm/Analysis/LoopAccessAnalysis.h -----------------------*- C++ -*-===//
 
2
//
 
3
//                     The LLVM Compiler Infrastructure
 
4
//
 
5
// This file is distributed under the University of Illinois Open Source
 
6
// License. See LICENSE.TXT for details.
 
7
//
 
8
//===----------------------------------------------------------------------===//
 
9
//
 
10
// This file defines the interface for the loop memory dependence framework that
 
11
// was originally developed for the Loop Vectorizer.
 
12
//
 
13
//===----------------------------------------------------------------------===//
 
14
 
 
15
#ifndef LLVM_ANALYSIS_LOOPACCESSANALYSIS_H
 
16
#define LLVM_ANALYSIS_LOOPACCESSANALYSIS_H
 
17
 
 
18
#include "llvm/ADT/EquivalenceClasses.h"
 
19
#include "llvm/ADT/Optional.h"
 
20
#include "llvm/ADT/SetVector.h"
 
21
#include "llvm/Analysis/AliasAnalysis.h"
 
22
#include "llvm/Analysis/AliasSetTracker.h"
 
23
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
 
24
#include "llvm/IR/ValueHandle.h"
 
25
#include "llvm/Pass.h"
 
26
#include "llvm/Support/raw_ostream.h"
 
27
 
 
28
namespace llvm {
 
29
 
 
30
class Value;
 
31
class DataLayout;
 
32
class AliasAnalysis;
 
33
class ScalarEvolution;
 
34
class Loop;
 
35
class SCEV;
 
36
 
 
37
/// Optimization analysis message produced during vectorization. Messages inform
 
38
/// the user why vectorization did not occur.
 
39
class LoopAccessReport {
 
40
  std::string Message;
 
41
  const Instruction *Instr;
 
42
 
 
43
protected:
 
44
  LoopAccessReport(const Twine &Message, const Instruction *I)
 
45
      : Message(Message.str()), Instr(I) {}
 
46
 
 
47
public:
 
48
  LoopAccessReport(const Instruction *I = nullptr) : Instr(I) {}
 
49
 
 
50
  template <typename A> LoopAccessReport &operator<<(const A &Value) {
 
51
    raw_string_ostream Out(Message);
 
52
    Out << Value;
 
53
    return *this;
 
54
  }
 
55
 
 
56
  const Instruction *getInstr() const { return Instr; }
 
57
 
 
58
  std::string &str() { return Message; }
 
59
  const std::string &str() const { return Message; }
 
60
  operator Twine() { return Message; }
 
61
 
 
62
  /// \brief Emit an analysis note for \p PassName with the debug location from
 
63
  /// the instruction in \p Message if available.  Otherwise use the location of
 
64
  /// \p TheLoop.
 
65
  static void emitAnalysis(const LoopAccessReport &Message,
 
66
                           const Function *TheFunction,
 
67
                           const Loop *TheLoop,
 
68
                           const char *PassName);
 
69
};
 
70
 
 
71
/// \brief Collection of parameters shared beetween the Loop Vectorizer and the
 
72
/// Loop Access Analysis.
 
73
struct VectorizerParams {
 
74
  /// \brief Maximum SIMD width.
 
75
  static const unsigned MaxVectorWidth;
 
76
 
 
77
  /// \brief VF as overridden by the user.
 
78
  static unsigned VectorizationFactor;
 
79
  /// \brief Interleave factor as overridden by the user.
 
80
  static unsigned VectorizationInterleave;
 
81
  /// \brief True if force-vector-interleave was specified by the user.
 
82
  static bool isInterleaveForced();
 
83
 
 
84
  /// \\brief When performing memory disambiguation checks at runtime do not
 
85
  /// make more than this number of comparisons.
 
86
  static unsigned RuntimeMemoryCheckThreshold;
 
87
};
 
88
 
 
89
/// \brief Checks memory dependences among accesses to the same underlying
 
90
/// object to determine whether there vectorization is legal or not (and at
 
91
/// which vectorization factor).
 
92
///
 
93
/// Note: This class will compute a conservative dependence for access to
 
94
/// different underlying pointers. Clients, such as the loop vectorizer, will
 
95
/// sometimes deal these potential dependencies by emitting runtime checks.
 
96
///
 
97
/// We use the ScalarEvolution framework to symbolically evalutate access
 
98
/// functions pairs. Since we currently don't restructure the loop we can rely
 
99
/// on the program order of memory accesses to determine their safety.
 
100
/// At the moment we will only deem accesses as safe for:
 
101
///  * A negative constant distance assuming program order.
 
102
///
 
103
///      Safe: tmp = a[i + 1];     OR     a[i + 1] = x;
 
104
///            a[i] = tmp;                y = a[i];
 
105
///
 
106
///   The latter case is safe because later checks guarantuee that there can't
 
107
///   be a cycle through a phi node (that is, we check that "x" and "y" is not
 
108
///   the same variable: a header phi can only be an induction or a reduction, a
 
109
///   reduction can't have a memory sink, an induction can't have a memory
 
110
///   source). This is important and must not be violated (or we have to
 
111
///   resort to checking for cycles through memory).
 
112
///
 
113
///  * A positive constant distance assuming program order that is bigger
 
114
///    than the biggest memory access.
 
115
///
 
116
///     tmp = a[i]        OR              b[i] = x
 
117
///     a[i+2] = tmp                      y = b[i+2];
 
118
///
 
119
///     Safe distance: 2 x sizeof(a[0]), and 2 x sizeof(b[0]), respectively.
 
120
///
 
121
///  * Zero distances and all accesses have the same size.
 
122
///
 
123
class MemoryDepChecker {
 
124
public:
 
125
  typedef PointerIntPair<Value *, 1, bool> MemAccessInfo;
 
126
  typedef SmallPtrSet<MemAccessInfo, 8> MemAccessInfoSet;
 
127
  /// \brief Set of potential dependent memory accesses.
 
128
  typedef EquivalenceClasses<MemAccessInfo> DepCandidates;
 
129
 
 
130
  /// \brief Dependece between memory access instructions.
 
131
  struct Dependence {
 
132
    /// \brief The type of the dependence.
 
133
    enum DepType {
 
134
      // No dependence.
 
135
      NoDep,
 
136
      // We couldn't determine the direction or the distance.
 
137
      Unknown,
 
138
      // Lexically forward.
 
139
      Forward,
 
140
      // Forward, but if vectorized, is likely to prevent store-to-load
 
141
      // forwarding.
 
142
      ForwardButPreventsForwarding,
 
143
      // Lexically backward.
 
144
      Backward,
 
145
      // Backward, but the distance allows a vectorization factor of
 
146
      // MaxSafeDepDistBytes.
 
147
      BackwardVectorizable,
 
148
      // Same, but may prevent store-to-load forwarding.
 
149
      BackwardVectorizableButPreventsForwarding
 
150
    };
 
151
 
 
152
    /// \brief String version of the types.
 
153
    static const char *DepName[];
 
154
 
 
155
    /// \brief Index of the source of the dependence in the InstMap vector.
 
156
    unsigned Source;
 
157
    /// \brief Index of the destination of the dependence in the InstMap vector.
 
158
    unsigned Destination;
 
159
    /// \brief The type of the dependence.
 
160
    DepType Type;
 
161
 
 
162
    Dependence(unsigned Source, unsigned Destination, DepType Type)
 
163
        : Source(Source), Destination(Destination), Type(Type) {}
 
164
 
 
165
    /// \brief Dependence types that don't prevent vectorization.
 
166
    static bool isSafeForVectorization(DepType Type);
 
167
 
 
168
    /// \brief Dependence types that can be queried from the analysis.
 
169
    static bool isInterestingDependence(DepType Type);
 
170
 
 
171
    /// \brief Lexically backward dependence types.
 
172
    bool isPossiblyBackward() const;
 
173
 
 
174
    /// \brief Print the dependence.  \p Instr is used to map the instruction
 
175
    /// indices to instructions.
 
176
    void print(raw_ostream &OS, unsigned Depth,
 
177
               const SmallVectorImpl<Instruction *> &Instrs) const;
 
178
  };
 
179
 
 
180
  MemoryDepChecker(ScalarEvolution *Se, const Loop *L)
 
181
      : SE(Se), InnermostLoop(L), AccessIdx(0),
 
182
        ShouldRetryWithRuntimeCheck(false), SafeForVectorization(true),
 
183
        RecordInterestingDependences(true) {}
 
184
 
 
185
  /// \brief Register the location (instructions are given increasing numbers)
 
186
  /// of a write access.
 
187
  void addAccess(StoreInst *SI) {
 
188
    Value *Ptr = SI->getPointerOperand();
 
189
    Accesses[MemAccessInfo(Ptr, true)].push_back(AccessIdx);
 
190
    InstMap.push_back(SI);
 
191
    ++AccessIdx;
 
192
  }
 
193
 
 
194
  /// \brief Register the location (instructions are given increasing numbers)
 
195
  /// of a write access.
 
196
  void addAccess(LoadInst *LI) {
 
197
    Value *Ptr = LI->getPointerOperand();
 
198
    Accesses[MemAccessInfo(Ptr, false)].push_back(AccessIdx);
 
199
    InstMap.push_back(LI);
 
200
    ++AccessIdx;
 
201
  }
 
202
 
 
203
  /// \brief Check whether the dependencies between the accesses are safe.
 
204
  ///
 
205
  /// Only checks sets with elements in \p CheckDeps.
 
206
  bool areDepsSafe(DepCandidates &AccessSets, MemAccessInfoSet &CheckDeps,
 
207
                   const ValueToValueMap &Strides);
 
208
 
 
209
  /// \brief No memory dependence was encountered that would inhibit
 
210
  /// vectorization.
 
211
  bool isSafeForVectorization() const { return SafeForVectorization; }
 
212
 
 
213
  /// \brief The maximum number of bytes of a vector register we can vectorize
 
214
  /// the accesses safely with.
 
215
  unsigned getMaxSafeDepDistBytes() { return MaxSafeDepDistBytes; }
 
216
 
 
217
  /// \brief In same cases when the dependency check fails we can still
 
218
  /// vectorize the loop with a dynamic array access check.
 
219
  bool shouldRetryWithRuntimeCheck() { return ShouldRetryWithRuntimeCheck; }
 
220
 
 
221
  /// \brief Returns the interesting dependences.  If null is returned we
 
222
  /// exceeded the MaxInterestingDependence threshold and this information is
 
223
  /// not available.
 
224
  const SmallVectorImpl<Dependence> *getInterestingDependences() const {
 
225
    return RecordInterestingDependences ? &InterestingDependences : nullptr;
 
226
  }
 
227
 
 
228
  void clearInterestingDependences() { InterestingDependences.clear(); }
 
229
 
 
230
  /// \brief The vector of memory access instructions.  The indices are used as
 
231
  /// instruction identifiers in the Dependence class.
 
232
  const SmallVectorImpl<Instruction *> &getMemoryInstructions() const {
 
233
    return InstMap;
 
234
  }
 
235
 
 
236
  /// \brief Find the set of instructions that read or write via \p Ptr.
 
237
  SmallVector<Instruction *, 4> getInstructionsForAccess(Value *Ptr,
 
238
                                                         bool isWrite) const;
 
239
 
 
240
private:
 
241
  ScalarEvolution *SE;
 
242
  const Loop *InnermostLoop;
 
243
 
 
244
  /// \brief Maps access locations (ptr, read/write) to program order.
 
245
  DenseMap<MemAccessInfo, std::vector<unsigned> > Accesses;
 
246
 
 
247
  /// \brief Memory access instructions in program order.
 
248
  SmallVector<Instruction *, 16> InstMap;
 
249
 
 
250
  /// \brief The program order index to be used for the next instruction.
 
251
  unsigned AccessIdx;
 
252
 
 
253
  // We can access this many bytes in parallel safely.
 
254
  unsigned MaxSafeDepDistBytes;
 
255
 
 
256
  /// \brief If we see a non-constant dependence distance we can still try to
 
257
  /// vectorize this loop with runtime checks.
 
258
  bool ShouldRetryWithRuntimeCheck;
 
259
 
 
260
  /// \brief No memory dependence was encountered that would inhibit
 
261
  /// vectorization.
 
262
  bool SafeForVectorization;
 
263
 
 
264
  //// \brief True if InterestingDependences reflects the dependences in the
 
265
  //// loop.  If false we exceeded MaxInterestingDependence and
 
266
  //// InterestingDependences is invalid.
 
267
  bool RecordInterestingDependences;
 
268
 
 
269
  /// \brief Interesting memory dependences collected during the analysis as
 
270
  /// defined by isInterestingDependence.  Only valid if
 
271
  /// RecordInterestingDependences is true.
 
272
  SmallVector<Dependence, 8> InterestingDependences;
 
273
 
 
274
  /// \brief Check whether there is a plausible dependence between the two
 
275
  /// accesses.
 
276
  ///
 
277
  /// Access \p A must happen before \p B in program order. The two indices
 
278
  /// identify the index into the program order map.
 
279
  ///
 
280
  /// This function checks  whether there is a plausible dependence (or the
 
281
  /// absence of such can't be proved) between the two accesses. If there is a
 
282
  /// plausible dependence but the dependence distance is bigger than one
 
283
  /// element access it records this distance in \p MaxSafeDepDistBytes (if this
 
284
  /// distance is smaller than any other distance encountered so far).
 
285
  /// Otherwise, this function returns true signaling a possible dependence.
 
286
  Dependence::DepType isDependent(const MemAccessInfo &A, unsigned AIdx,
 
287
                                  const MemAccessInfo &B, unsigned BIdx,
 
288
                                  const ValueToValueMap &Strides);
 
289
 
 
290
  /// \brief Check whether the data dependence could prevent store-load
 
291
  /// forwarding.
 
292
  bool couldPreventStoreLoadForward(unsigned Distance, unsigned TypeByteSize);
 
293
};
 
294
 
 
295
/// \brief Holds information about the memory runtime legality checks to verify
 
296
/// that a group of pointers do not overlap.
 
297
class RuntimePointerChecking {
 
298
public:
 
299
  struct PointerInfo {
 
300
    /// Holds the pointer value that we need to check.
 
301
    TrackingVH<Value> PointerValue;
 
302
    /// Holds the pointer value at the beginning of the loop.
 
303
    const SCEV *Start;
 
304
    /// Holds the pointer value at the end of the loop.
 
305
    const SCEV *End;
 
306
    /// Holds the information if this pointer is used for writing to memory.
 
307
    bool IsWritePtr;
 
308
    /// Holds the id of the set of pointers that could be dependent because of a
 
309
    /// shared underlying object.
 
310
    unsigned DependencySetId;
 
311
    /// Holds the id of the disjoint alias set to which this pointer belongs.
 
312
    unsigned AliasSetId;
 
313
    /// SCEV for the access.
 
314
    const SCEV *Expr;
 
315
 
 
316
    PointerInfo(Value *PointerValue, const SCEV *Start, const SCEV *End,
 
317
                bool IsWritePtr, unsigned DependencySetId, unsigned AliasSetId,
 
318
                const SCEV *Expr)
 
319
        : PointerValue(PointerValue), Start(Start), End(End),
 
320
          IsWritePtr(IsWritePtr), DependencySetId(DependencySetId),
 
321
          AliasSetId(AliasSetId), Expr(Expr) {}
 
322
  };
 
323
 
 
324
  RuntimePointerChecking(ScalarEvolution *SE) : Need(false), SE(SE) {}
 
325
 
 
326
  /// Reset the state of the pointer runtime information.
 
327
  void reset() {
 
328
    Need = false;
 
329
    Pointers.clear();
 
330
  }
 
331
 
 
332
  /// Insert a pointer and calculate the start and end SCEVs.
 
333
  void insert(Loop *Lp, Value *Ptr, bool WritePtr, unsigned DepSetId,
 
334
              unsigned ASId, const ValueToValueMap &Strides);
 
335
 
 
336
  /// \brief No run-time memory checking is necessary.
 
337
  bool empty() const { return Pointers.empty(); }
 
338
 
 
339
  /// A grouping of pointers. A single memcheck is required between
 
340
  /// two groups.
 
341
  struct CheckingPtrGroup {
 
342
    /// \brief Create a new pointer checking group containing a single
 
343
    /// pointer, with index \p Index in RtCheck.
 
344
    CheckingPtrGroup(unsigned Index, RuntimePointerChecking &RtCheck)
 
345
        : RtCheck(RtCheck), High(RtCheck.Pointers[Index].End),
 
346
          Low(RtCheck.Pointers[Index].Start) {
 
347
      Members.push_back(Index);
 
348
    }
 
349
 
 
350
    /// \brief Tries to add the pointer recorded in RtCheck at index
 
351
    /// \p Index to this pointer checking group. We can only add a pointer
 
352
    /// to a checking group if we will still be able to get
 
353
    /// the upper and lower bounds of the check. Returns true in case
 
354
    /// of success, false otherwise.
 
355
    bool addPointer(unsigned Index);
 
356
 
 
357
    /// Constitutes the context of this pointer checking group. For each
 
358
    /// pointer that is a member of this group we will retain the index
 
359
    /// at which it appears in RtCheck.
 
360
    RuntimePointerChecking &RtCheck;
 
361
    /// The SCEV expression which represents the upper bound of all the
 
362
    /// pointers in this group.
 
363
    const SCEV *High;
 
364
    /// The SCEV expression which represents the lower bound of all the
 
365
    /// pointers in this group.
 
366
    const SCEV *Low;
 
367
    /// Indices of all the pointers that constitute this grouping.
 
368
    SmallVector<unsigned, 2> Members;
 
369
  };
 
370
 
 
371
  /// \brief Groups pointers such that a single memcheck is required
 
372
  /// between two different groups. This will clear the CheckingGroups vector
 
373
  /// and re-compute it. We will only group dependecies if \p UseDependencies
 
374
  /// is true, otherwise we will create a separate group for each pointer.
 
375
  void groupChecks(MemoryDepChecker::DepCandidates &DepCands,
 
376
                   bool UseDependencies);
 
377
 
 
378
  /// \brief Decide if we need to add a check between two groups of pointers,
 
379
  /// according to needsChecking.
 
380
  bool needsChecking(const CheckingPtrGroup &M, const CheckingPtrGroup &N,
 
381
                     const SmallVectorImpl<int> *PtrPartition) const;
 
382
 
 
383
  /// \brief Return true if any pointer requires run-time checking according
 
384
  /// to needsChecking.
 
385
  bool needsAnyChecking(const SmallVectorImpl<int> *PtrPartition) const;
 
386
 
 
387
  /// \brief Returns the number of run-time checks required according to
 
388
  /// needsChecking.
 
389
  unsigned getNumberOfChecks(const SmallVectorImpl<int> *PtrPartition) const;
 
390
 
 
391
  /// \brief Print the list run-time memory checks necessary.
 
392
  ///
 
393
  /// If \p PtrPartition is set, it contains the partition number for
 
394
  /// pointers (-1 if the pointer belongs to multiple partitions).  In this
 
395
  /// case omit checks between pointers belonging to the same partition.
 
396
  void print(raw_ostream &OS, unsigned Depth = 0,
 
397
             const SmallVectorImpl<int> *PtrPartition = nullptr) const;
 
398
 
 
399
  /// This flag indicates if we need to add the runtime check.
 
400
  bool Need;
 
401
 
 
402
  /// Information about the pointers that may require checking.
 
403
  SmallVector<PointerInfo, 2> Pointers;
 
404
 
 
405
  /// Holds a partitioning of pointers into "check groups".
 
406
  SmallVector<CheckingPtrGroup, 2> CheckingGroups;
 
407
 
 
408
private:
 
409
  /// \brief Decide whether we need to issue a run-time check for pointer at
 
410
  /// index \p I and \p J to prove their independence.
 
411
  ///
 
412
  /// If \p PtrPartition is set, it contains the partition number for
 
413
  /// pointers (-1 if the pointer belongs to multiple partitions).  In this
 
414
  /// case omit checks between pointers belonging to the same partition.
 
415
  bool needsChecking(unsigned I, unsigned J,
 
416
                     const SmallVectorImpl<int> *PtrPartition) const;
 
417
 
 
418
  /// Holds a pointer to the ScalarEvolution analysis.
 
419
  ScalarEvolution *SE;
 
420
};
 
421
 
 
422
/// \brief Drive the analysis of memory accesses in the loop
 
423
///
 
424
/// This class is responsible for analyzing the memory accesses of a loop.  It
 
425
/// collects the accesses and then its main helper the AccessAnalysis class
 
426
/// finds and categorizes the dependences in buildDependenceSets.
 
427
///
 
428
/// For memory dependences that can be analyzed at compile time, it determines
 
429
/// whether the dependence is part of cycle inhibiting vectorization.  This work
 
430
/// is delegated to the MemoryDepChecker class.
 
431
///
 
432
/// For memory dependences that cannot be determined at compile time, it
 
433
/// generates run-time checks to prove independence.  This is done by
 
434
/// AccessAnalysis::canCheckPtrAtRT and the checks are maintained by the
 
435
/// RuntimePointerCheck class.
 
436
class LoopAccessInfo {
 
437
public:
 
438
  LoopAccessInfo(Loop *L, ScalarEvolution *SE, const DataLayout &DL,
 
439
                 const TargetLibraryInfo *TLI, AliasAnalysis *AA,
 
440
                 DominatorTree *DT, LoopInfo *LI,
 
441
                 const ValueToValueMap &Strides);
 
442
 
 
443
  /// Return true we can analyze the memory accesses in the loop and there are
 
444
  /// no memory dependence cycles.
 
445
  bool canVectorizeMemory() const { return CanVecMem; }
 
446
 
 
447
  const RuntimePointerChecking *getRuntimePointerChecking() const {
 
448
    return &PtrRtChecking;
 
449
  }
 
450
 
 
451
  /// \brief Number of memchecks required to prove independence of otherwise
 
452
  /// may-alias pointers.
 
453
  unsigned getNumRuntimePointerChecks(
 
454
    const SmallVectorImpl<int> *PtrPartition = nullptr) const {
 
455
    return PtrRtChecking.getNumberOfChecks(PtrPartition);
 
456
  }
 
457
 
 
458
  /// Return true if the block BB needs to be predicated in order for the loop
 
459
  /// to be vectorized.
 
460
  static bool blockNeedsPredication(BasicBlock *BB, Loop *TheLoop,
 
461
                                    DominatorTree *DT);
 
462
 
 
463
  /// Returns true if the value V is uniform within the loop.
 
464
  bool isUniform(Value *V) const;
 
465
 
 
466
  unsigned getMaxSafeDepDistBytes() const { return MaxSafeDepDistBytes; }
 
467
  unsigned getNumStores() const { return NumStores; }
 
468
  unsigned getNumLoads() const { return NumLoads;}
 
469
 
 
470
  /// \brief Add code that checks at runtime if the accessed arrays overlap.
 
471
  ///
 
472
  /// Returns a pair of instructions where the first element is the first
 
473
  /// instruction generated in possibly a sequence of instructions and the
 
474
  /// second value is the final comparator value or NULL if no check is needed.
 
475
  ///
 
476
  /// If \p PtrPartition is set, it contains the partition number for pointers
 
477
  /// (-1 if the pointer belongs to multiple partitions).  In this case omit
 
478
  /// checks between pointers belonging to the same partition.
 
479
  std::pair<Instruction *, Instruction *>
 
480
  addRuntimeCheck(Instruction *Loc,
 
481
                  const SmallVectorImpl<int> *PtrPartition = nullptr) const;
 
482
 
 
483
  /// \brief The diagnostics report generated for the analysis.  E.g. why we
 
484
  /// couldn't analyze the loop.
 
485
  const Optional<LoopAccessReport> &getReport() const { return Report; }
 
486
 
 
487
  /// \brief the Memory Dependence Checker which can determine the
 
488
  /// loop-independent and loop-carried dependences between memory accesses.
 
489
  const MemoryDepChecker &getDepChecker() const { return DepChecker; }
 
490
 
 
491
  /// \brief Return the list of instructions that use \p Ptr to read or write
 
492
  /// memory.
 
493
  SmallVector<Instruction *, 4> getInstructionsForAccess(Value *Ptr,
 
494
                                                         bool isWrite) const {
 
495
    return DepChecker.getInstructionsForAccess(Ptr, isWrite);
 
496
  }
 
497
 
 
498
  /// \brief Print the information about the memory accesses in the loop.
 
499
  void print(raw_ostream &OS, unsigned Depth = 0) const;
 
500
 
 
501
  /// \brief Used to ensure that if the analysis was run with speculating the
 
502
  /// value of symbolic strides, the client queries it with the same assumption.
 
503
  /// Only used in DEBUG build but we don't want NDEBUG-dependent ABI.
 
504
  unsigned NumSymbolicStrides;
 
505
 
 
506
  /// \brief Checks existence of store to invariant address inside loop.
 
507
  /// If the loop has any store to invariant address, then it returns true,
 
508
  /// else returns false.
 
509
  bool hasStoreToLoopInvariantAddress() const {
 
510
    return StoreToLoopInvariantAddress;
 
511
  }
 
512
 
 
513
private:
 
514
  /// \brief Analyze the loop.  Substitute symbolic strides using Strides.
 
515
  void analyzeLoop(const ValueToValueMap &Strides);
 
516
 
 
517
  /// \brief Check if the structure of the loop allows it to be analyzed by this
 
518
  /// pass.
 
519
  bool canAnalyzeLoop();
 
520
 
 
521
  void emitAnalysis(LoopAccessReport &Message);
 
522
 
 
523
  /// We need to check that all of the pointers in this list are disjoint
 
524
  /// at runtime.
 
525
  RuntimePointerChecking PtrRtChecking;
 
526
 
 
527
  /// \brief the Memory Dependence Checker which can determine the
 
528
  /// loop-independent and loop-carried dependences between memory accesses.
 
529
  MemoryDepChecker DepChecker;
 
530
 
 
531
  Loop *TheLoop;
 
532
  ScalarEvolution *SE;
 
533
  const DataLayout &DL;
 
534
  const TargetLibraryInfo *TLI;
 
535
  AliasAnalysis *AA;
 
536
  DominatorTree *DT;
 
537
  LoopInfo *LI;
 
538
 
 
539
  unsigned NumLoads;
 
540
  unsigned NumStores;
 
541
 
 
542
  unsigned MaxSafeDepDistBytes;
 
543
 
 
544
  /// \brief Cache the result of analyzeLoop.
 
545
  bool CanVecMem;
 
546
 
 
547
  /// \brief Indicator for storing to uniform addresses.
 
548
  /// If a loop has write to a loop invariant address then it should be true.
 
549
  bool StoreToLoopInvariantAddress;
 
550
 
 
551
  /// \brief The diagnostics report generated for the analysis.  E.g. why we
 
552
  /// couldn't analyze the loop.
 
553
  Optional<LoopAccessReport> Report;
 
554
};
 
555
 
 
556
Value *stripIntegerCast(Value *V);
 
557
 
 
558
///\brief Return the SCEV corresponding to a pointer with the symbolic stride
 
559
///replaced with constant one.
 
560
///
 
561
/// If \p OrigPtr is not null, use it to look up the stride value instead of \p
 
562
/// Ptr.  \p PtrToStride provides the mapping between the pointer value and its
 
563
/// stride as collected by LoopVectorizationLegality::collectStridedAccess.
 
564
const SCEV *replaceSymbolicStrideSCEV(ScalarEvolution *SE,
 
565
                                      const ValueToValueMap &PtrToStride,
 
566
                                      Value *Ptr, Value *OrigPtr = nullptr);
 
567
 
 
568
/// \brief Check the stride of the pointer and ensure that it does not wrap in
 
569
/// the address space.
 
570
int isStridedPtr(ScalarEvolution *SE, Value *Ptr, const Loop *Lp,
 
571
                 const ValueToValueMap &StridesMap);
 
572
 
 
573
/// \brief This analysis provides dependence information for the memory accesses
 
574
/// of a loop.
 
575
///
 
576
/// It runs the analysis for a loop on demand.  This can be initiated by
 
577
/// querying the loop access info via LAA::getInfo.  getInfo return a
 
578
/// LoopAccessInfo object.  See this class for the specifics of what information
 
579
/// is provided.
 
580
class LoopAccessAnalysis : public FunctionPass {
 
581
public:
 
582
  static char ID;
 
583
 
 
584
  LoopAccessAnalysis() : FunctionPass(ID) {
 
585
    initializeLoopAccessAnalysisPass(*PassRegistry::getPassRegistry());
 
586
  }
 
587
 
 
588
  bool runOnFunction(Function &F) override;
 
589
 
 
590
  void getAnalysisUsage(AnalysisUsage &AU) const override;
 
591
 
 
592
  /// \brief Query the result of the loop access information for the loop \p L.
 
593
  ///
 
594
  /// If the client speculates (and then issues run-time checks) for the values
 
595
  /// of symbolic strides, \p Strides provides the mapping (see
 
596
  /// replaceSymbolicStrideSCEV).  If there is no cached result available run
 
597
  /// the analysis.
 
598
  const LoopAccessInfo &getInfo(Loop *L, const ValueToValueMap &Strides);
 
599
 
 
600
  void releaseMemory() override {
 
601
    // Invalidate the cache when the pass is freed.
 
602
    LoopAccessInfoMap.clear();
 
603
  }
 
604
 
 
605
  /// \brief Print the result of the analysis when invoked with -analyze.
 
606
  void print(raw_ostream &OS, const Module *M = nullptr) const override;
 
607
 
 
608
private:
 
609
  /// \brief The cache.
 
610
  DenseMap<Loop *, std::unique_ptr<LoopAccessInfo>> LoopAccessInfoMap;
 
611
 
 
612
  // The used analysis passes.
 
613
  ScalarEvolution *SE;
 
614
  const TargetLibraryInfo *TLI;
 
615
  AliasAnalysis *AA;
 
616
  DominatorTree *DT;
 
617
  LoopInfo *LI;
 
618
};
 
619
} // End llvm namespace
 
620
 
 
621
#endif