Coverage Report

Created: 2019-03-24 22:13

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h
Line
Count
Source (jump to first uncovered line)
1
//===- llvm/Analysis/MemoryDependenceAnalysis.h - Memory Deps ---*- C++ -*-===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
// This file defines the MemoryDependenceAnalysis analysis pass.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#ifndef LLVM_ANALYSIS_MEMORYDEPENDENCEANALYSIS_H
14
#define LLVM_ANALYSIS_MEMORYDEPENDENCEANALYSIS_H
15
16
#include "llvm/ADT/DenseMap.h"
17
#include "llvm/ADT/Optional.h"
18
#include "llvm/ADT/PointerEmbeddedInt.h"
19
#include "llvm/ADT/PointerIntPair.h"
20
#include "llvm/ADT/PointerSumType.h"
21
#include "llvm/ADT/SmallPtrSet.h"
22
#include "llvm/Analysis/AliasAnalysis.h"
23
#include "llvm/Analysis/MemoryLocation.h"
24
#include "llvm/IR/BasicBlock.h"
25
#include "llvm/IR/Metadata.h"
26
#include "llvm/IR/PassManager.h"
27
#include "llvm/IR/PredIteratorCache.h"
28
#include "llvm/IR/ValueHandle.h"
29
#include "llvm/Pass.h"
30
#include "llvm/Support/ErrorHandling.h"
31
#include <cassert>
32
#include <cstdint>
33
#include <utility>
34
#include <vector>
35
36
namespace llvm {
37
38
class AssumptionCache;
39
class DominatorTree;
40
class Function;
41
class Instruction;
42
class LoadInst;
43
class PHITransAddr;
44
class TargetLibraryInfo;
45
class PhiValues;
46
class Value;
47
48
/// A memory dependence query can return one of three different answers.
49
0
class MemDepResult {
50
  enum DepType {
51
    /// Clients of MemDep never see this.
52
    ///
53
    /// Entries with this marker occur in a LocalDeps map or NonLocalDeps map
54
    /// when the instruction they previously referenced was removed from
55
    /// MemDep.  In either case, the entry may include an instruction pointer.
56
    /// If so, the pointer is an instruction in the block where scanning can
57
    /// start from, saving some work.
58
    ///
59
    /// In a default-constructed MemDepResult object, the type will be Invalid
60
    /// and the instruction pointer will be null.
61
    Invalid = 0,
62
63
    /// This is a dependence on the specified instruction which clobbers the
64
    /// desired value.  The pointer member of the MemDepResult pair holds the
65
    /// instruction that clobbers the memory.  For example, this occurs when we
66
    /// see a may-aliased store to the memory location we care about.
67
    ///
68
    /// There are several cases that may be interesting here:
69
    ///   1. Loads are clobbered by may-alias stores.
70
    ///   2. Loads are considered clobbered by partially-aliased loads.  The
71
    ///      client may choose to analyze deeper into these cases.
72
    Clobber,
73
74
    /// This is a dependence on the specified instruction which defines or
75
    /// produces the desired memory location.  The pointer member of the
76
    /// MemDepResult pair holds the instruction that defines the memory.
77
    ///
78
    /// Cases of interest:
79
    ///   1. This could be a load or store for dependence queries on
80
    ///      load/store.  The value loaded or stored is the produced value.
81
    ///      Note that the pointer operand may be different than that of the
82
    ///      queried pointer due to must aliases and phi translation. Note
83
    ///      that the def may not be the same type as the query, the pointers
84
    ///      may just be must aliases.
85
    ///   2. For loads and stores, this could be an allocation instruction. In
86
    ///      this case, the load is loading an undef value or a store is the
87
    ///      first store to (that part of) the allocation.
88
    ///   3. Dependence queries on calls return Def only when they are readonly
89
    ///      calls or memory use intrinsics with identical callees and no
90
    ///      intervening clobbers.  No validation is done that the operands to
91
    ///      the calls are the same.
92
    Def,
93
94
    /// This marker indicates that the query has no known dependency in the
95
    /// specified block.
96
    ///
97
    /// More detailed state info is encoded in the upper part of the pair (i.e.
98
    /// the Instruction*)
99
    Other
100
  };
101
102
  /// If DepType is "Other", the upper part of the sum type is an encoding of
103
  /// the following more detailed type information.
104
  enum OtherType {
105
    /// This marker indicates that the query has no dependency in the specified
106
    /// block.
107
    ///
108
    /// To find out more, the client should query other predecessor blocks.
109
    NonLocal = 1,
110
    /// This marker indicates that the query has no dependency in the specified
111
    /// function.
112
    NonFuncLocal,
113
    /// This marker indicates that the query dependency is unknown.
114
    Unknown
115
  };
116
117
  using ValueTy = PointerSumType<
118
      DepType, PointerSumTypeMember<Invalid, Instruction *>,
119
      PointerSumTypeMember<Clobber, Instruction *>,
120
      PointerSumTypeMember<Def, Instruction *>,
121
      PointerSumTypeMember<Other, PointerEmbeddedInt<OtherType, 3>>>;
122
  ValueTy Value;
123
124
28.7M
  explicit MemDepResult(ValueTy V) : Value(V) {}
125
126
public:
127
17.6M
  MemDepResult() = default;
128
129
  /// get methods: These are static ctor methods for creating various
130
  /// MemDepResult kinds.
131
555k
  static MemDepResult getDef(Instruction *Inst) {
132
555k
    assert(Inst && "Def requires inst");
133
555k
    return MemDepResult(ValueTy::create<Def>(Inst));
134
555k
  }
135
2.23M
  static MemDepResult getClobber(Instruction *Inst) {
136
2.23M
    assert(Inst && "Clobber requires inst");
137
2.23M
    return MemDepResult(ValueTy::create<Clobber>(Inst));
138
2.23M
  }
139
6.23M
  static MemDepResult getNonLocal() {
140
6.23M
    return MemDepResult(ValueTy::create<Other>(NonLocal));
141
6.23M
  }
142
633k
  static MemDepResult getNonFuncLocal() {
143
633k
    return MemDepResult(ValueTy::create<Other>(NonFuncLocal));
144
633k
  }
145
18.7M
  static MemDepResult getUnknown() {
146
18.7M
    return MemDepResult(ValueTy::create<Other>(Unknown));
147
18.7M
  }
148
149
  /// Tests if this MemDepResult represents a query that is an instruction
150
  /// clobber dependency.
151
18.3M
  bool isClobber() const { return Value.is<Clobber>(); }
152
153
  /// Tests if this MemDepResult represents a query that is an instruction
154
  /// definition dependency.
155
32.4M
  bool isDef() const { return Value.is<Def>(); }
156
157
  /// Tests if this MemDepResult represents a query that is transparent to the
158
  /// start of the block, but where a non-local hasn't been done.
159
26.4M
  bool isNonLocal() const {
160
26.4M
    return Value.is<Other>() && 
Value.cast<Other>() == NonLocal21.9M
;
161
26.4M
  }
162
163
  /// Tests if this MemDepResult represents a query that is transparent to the
164
  /// start of the function.
165
0
  bool isNonFuncLocal() const {
166
0
    return Value.is<Other>() && Value.cast<Other>() == NonFuncLocal;
167
0
  }
168
169
  /// Tests if this MemDepResult represents a query which cannot and/or will
170
  /// not be computed.
171
29.4k
  bool isUnknown() const {
172
29.4k
    return Value.is<Other>() && 
Value.cast<Other>() == Unknown29.1k
;
173
29.4k
  }
174
175
  /// If this is a normal dependency, returns the instruction that is depended
176
  /// on.  Otherwise, returns null.
177
21.5M
  Instruction *getInst() const {
178
21.5M
    switch (Value.getTag()) {
179
21.5M
    case Invalid:
180
3.32M
      return Value.cast<Invalid>();
181
21.5M
    case Clobber:
182
14.0M
      return Value.cast<Clobber>();
183
21.5M
    case Def:
184
1.44M
      return Value.cast<Def>();
185
21.5M
    case Other:
186
2.74M
      return nullptr;
187
0
    }
188
0
    llvm_unreachable("Unknown discriminant!");
189
0
  }
190
191
  bool operator==(const MemDepResult &M) const { return Value == M.Value; }
192
  bool operator!=(const MemDepResult &M) const { return Value != M.Value; }
193
  bool operator<(const MemDepResult &M) const { return Value < M.Value; }
194
  bool operator>(const MemDepResult &M) const { return Value > M.Value; }
195
196
private:
197
  friend class MemoryDependenceResults;
198
199
  /// Tests if this is a MemDepResult in its dirty/invalid. state.
200
12.2M
  bool isDirty() const { return Value.is<Invalid>(); }
201
202
362k
  static MemDepResult getDirty(Instruction *Inst) {
203
362k
    return MemDepResult(ValueTy::create<Invalid>(Inst));
204
362k
  }
205
};
206
207
/// This is an entry in the NonLocalDepInfo cache.
208
///
209
/// For each BasicBlock (the BB entry) it keeps a MemDepResult.
210
class NonLocalDepEntry {
211
  BasicBlock *BB;
212
  MemDepResult Result;
213
214
public:
215
  NonLocalDepEntry(BasicBlock *bb, MemDepResult result)
216
11.9M
      : BB(bb), Result(result) {}
217
218
  // This is used for searches.
219
14.0M
  NonLocalDepEntry(BasicBlock *bb) : BB(bb) {}
220
221
  // BB is the sort key, it can't be changed.
222
24.7M
  BasicBlock *getBB() const { return BB; }
223
224
39.1k
  void setResult(const MemDepResult &R) { Result = R; }
225
226
23.5M
  const MemDepResult &getResult() const { return Result; }
227
228
100M
  bool operator<(const NonLocalDepEntry &RHS) const { return BB < RHS.BB; }
229
};
230
231
/// This is a result from a NonLocal dependence query.
232
///
233
/// For each BasicBlock (the BB entry) it keeps a MemDepResult and the
234
/// (potentially phi translated) address that was live in the block.
235
class NonLocalDepResult {
236
  NonLocalDepEntry Entry;
237
  Value *Address;
238
239
public:
240
  NonLocalDepResult(BasicBlock *bb, MemDepResult result, Value *address)
241
5.62M
      : Entry(bb, result), Address(address) {}
242
243
  // BB is the sort key, it can't be changed.
244
4.96M
  BasicBlock *getBB() const { return Entry.getBB(); }
245
246
0
  void setResult(const MemDepResult &R, Value *Addr) {
247
0
    Entry.setResult(R);
248
0
    Address = Addr;
249
0
  }
250
251
6.73M
  const MemDepResult &getResult() const { return Entry.getResult(); }
252
253
  /// Returns the address of this pointer in this block.
254
  ///
255
  /// This can be different than the address queried for the non-local result
256
  /// because of phi translation.  This returns null if the address was not
257
  /// available in a block (i.e. because phi translation failed) or if this is
258
  /// a cached result and that address was deleted.
259
  ///
260
  /// The address is always null for a non-local 'call' dependence.
261
3.62M
  Value *getAddress() const { return Address; }
262
};
263
264
/// Provides a lazy, caching interface for making common memory aliasing
265
/// information queries, backed by LLVM's alias analysis passes.
266
///
267
/// The dependency information returned is somewhat unusual, but is pragmatic.
268
/// If queried about a store or call that might modify memory, the analysis
269
/// will return the instruction[s] that may either load from that memory or
270
/// store to it.  If queried with a load or call that can never modify memory,
271
/// the analysis will return calls and stores that might modify the pointer,
272
/// but generally does not return loads unless a) they are volatile, or
273
/// b) they load from *must-aliased* pointers.  Returning a dependence on
274
/// must-alias'd pointers instead of all pointers interacts well with the
275
/// internal caching mechanism.
276
class MemoryDependenceResults {
277
  // A map from instructions to their dependency.
278
  using LocalDepMapType = DenseMap<Instruction *, MemDepResult>;
279
  LocalDepMapType LocalDeps;
280
281
public:
282
  using NonLocalDepInfo = std::vector<NonLocalDepEntry>;
283
284
private:
285
  /// A pair<Value*, bool> where the bool is true if the dependence is a read
286
  /// only dependence, false if read/write.
287
  using ValueIsLoadPair = PointerIntPair<const Value *, 1, bool>;
288
289
  /// This pair is used when caching information for a block.
290
  ///
291
  /// If the pointer is null, the cache value is not a full query that starts
292
  /// at the specified block.  If non-null, the bool indicates whether or not
293
  /// the contents of the block was skipped.
294
  using BBSkipFirstBlockPair = PointerIntPair<BasicBlock *, 1, bool>;
295
296
  /// This record is the information kept for each (value, is load) pair.
297
  struct NonLocalPointerInfo {
298
    /// The pair of the block and the skip-first-block flag.
299
    BBSkipFirstBlockPair Pair;
300
    /// The results of the query for each relevant block.
301
    NonLocalDepInfo NonLocalDeps;
302
    /// The maximum size of the dereferences of the pointer.
303
    ///
304
    /// May be UnknownSize if the sizes are unknown.
305
    LocationSize Size = LocationSize::unknown();
306
    /// The AA tags associated with dereferences of the pointer.
307
    ///
308
    /// The members may be null if there are no tags or conflicting tags.
309
    AAMDNodes AATags;
310
311
3.66M
    NonLocalPointerInfo() = default;
312
  };
313
314
  /// Cache storing single nonlocal def for the instruction.
315
  /// It is set when nonlocal def would be found in function returning only
316
  /// local dependencies.
317
  DenseMap<AssertingVH<const Value>, NonLocalDepResult> NonLocalDefsCache;
318
  using ReverseNonLocalDefsCacheTy =
319
    DenseMap<Instruction *, SmallPtrSet<const Value*, 4>>;
320
  ReverseNonLocalDefsCacheTy ReverseNonLocalDefsCache;
321
322
  /// This map stores the cached results of doing a pointer lookup at the
323
  /// bottom of a block.
324
  ///
325
  /// The key of this map is the pointer+isload bit, the value is a list of
326
  /// <bb->result> mappings.
327
  using CachedNonLocalPointerInfo =
328
      DenseMap<ValueIsLoadPair, NonLocalPointerInfo>;
329
  CachedNonLocalPointerInfo NonLocalPointerDeps;
330
331
  // A map from instructions to their non-local pointer dependencies.
332
  using ReverseNonLocalPtrDepTy =
333
      DenseMap<Instruction *, SmallPtrSet<ValueIsLoadPair, 4>>;
334
  ReverseNonLocalPtrDepTy ReverseNonLocalPtrDeps;
335
336
  /// This is the instruction we keep for each cached access that we have for
337
  /// an instruction.
338
  ///
339
  /// The pointer is an owning pointer and the bool indicates whether we have
340
  /// any dirty bits in the set.
341
  using PerInstNLInfo = std::pair<NonLocalDepInfo, bool>;
342
343
  // A map from instructions to their non-local dependencies.
344
  using NonLocalDepMapType = DenseMap<Instruction *, PerInstNLInfo>;
345
346
  NonLocalDepMapType NonLocalDeps;
347
348
  // A reverse mapping from dependencies to the dependees.  This is
349
  // used when removing instructions to keep the cache coherent.
350
  using ReverseDepMapType =
351
      DenseMap<Instruction *, SmallPtrSet<Instruction *, 4>>;
352
  ReverseDepMapType ReverseLocalDeps;
353
354
  // A reverse mapping from dependencies to the non-local dependees.
355
  ReverseDepMapType ReverseNonLocalDeps;
356
357
  /// Current AA implementation, just a cache.
358
  AliasAnalysis &AA;
359
  AssumptionCache &AC;
360
  const TargetLibraryInfo &TLI;
361
  DominatorTree &DT;
362
  PhiValues &PV;
363
  PredIteratorCache PredCache;
364
365
public:
366
  MemoryDependenceResults(AliasAnalysis &AA, AssumptionCache &AC,
367
                          const TargetLibraryInfo &TLI,
368
                          DominatorTree &DT, PhiValues &PV)
369
1.39M
      : AA(AA), AC(AC), TLI(TLI), DT(DT), PV(PV) {}
370
371
  /// Handle invalidation in the new PM.
372
  bool invalidate(Function &F, const PreservedAnalyses &PA,
373
                  FunctionAnalysisManager::Invalidator &Inv);
374
375
  /// Some methods limit the number of instructions they will examine.
376
  /// The return value of this method is the default limit that will be
377
  /// used if no limit is explicitly passed in.
378
  unsigned getDefaultBlockScanLimit() const;
379
380
  /// Returns the instruction on which a memory operation depends.
381
  ///
382
  /// See the class comment for more details. It is illegal to call this on
383
  /// non-memory instructions.
384
  MemDepResult getDependency(Instruction *QueryInst);
385
386
  /// Perform a full dependency query for the specified call, returning the set
387
  /// of blocks that the value is potentially live across.
388
  ///
389
  /// The returned set of results will include a "NonLocal" result for all
390
  /// blocks where the value is live across.
391
  ///
392
  /// This method assumes the instruction returns a "NonLocal" dependency
393
  /// within its own block.
394
  ///
395
  /// This returns a reference to an internal data structure that may be
396
  /// invalidated on the next non-local query or when an instruction is
397
  /// removed.  Clients must copy this data if they want it around longer than
398
  /// that.
399
  const NonLocalDepInfo &getNonLocalCallDependency(CallBase *QueryCall);
400
401
  /// Perform a full dependency query for an access to the QueryInst's
402
  /// specified memory location, returning the set of instructions that either
403
  /// define or clobber the value.
404
  ///
405
  /// Warning: For a volatile query instruction, the dependencies will be
406
  /// accurate, and thus usable for reordering, but it is never legal to
407
  /// remove the query instruction.
408
  ///
409
  /// This method assumes the pointer has a "NonLocal" dependency within
410
  /// QueryInst's parent basic block.
411
  void getNonLocalPointerDependency(Instruction *QueryInst,
412
                                    SmallVectorImpl<NonLocalDepResult> &Result);
413
414
  /// Removes an instruction from the dependence analysis, updating the
415
  /// dependence of instructions that previously depended on it.
416
  void removeInstruction(Instruction *InstToRemove);
417
418
  /// Invalidates cached information about the specified pointer, because it
419
  /// may be too conservative in memdep.
420
  ///
421
  /// This is an optional call that can be used when the client detects an
422
  /// equivalence between the pointer and some other value and replaces the
423
  /// other value with ptr. This can make Ptr available in more places that
424
  /// cached info does not necessarily keep.
425
  void invalidateCachedPointerInfo(Value *Ptr);
426
427
  /// Clears the PredIteratorCache info.
428
  ///
429
  /// This needs to be done when the CFG changes, e.g., due to splitting
430
  /// critical edges.
431
  void invalidateCachedPredecessors();
432
433
  /// Returns the instruction on which a memory location depends.
434
  ///
435
  /// If isLoad is true, this routine ignores may-aliases with read-only
436
  /// operations.  If isLoad is false, this routine ignores may-aliases
437
  /// with reads from read-only locations. If possible, pass the query
438
  /// instruction as well; this function may take advantage of the metadata
439
  /// annotated to the query instruction to refine the result. \p Limit
440
  /// can be used to set the maximum number of instructions that will be
441
  /// examined to find the pointer dependency. On return, it will be set to
442
  /// the number of instructions left to examine. If a null pointer is passed
443
  /// in, the limit will default to the value of -memdep-block-scan-limit.
444
  ///
445
  /// Note that this is an uncached query, and thus may be inefficient.
446
  MemDepResult getPointerDependencyFrom(const MemoryLocation &Loc, bool isLoad,
447
                                        BasicBlock::iterator ScanIt,
448
                                        BasicBlock *BB,
449
                                        Instruction *QueryInst = nullptr,
450
                                        unsigned *Limit = nullptr);
451
452
  MemDepResult getSimplePointerDependencyFrom(const MemoryLocation &MemLoc,
453
                                              bool isLoad,
454
                                              BasicBlock::iterator ScanIt,
455
                                              BasicBlock *BB,
456
                                              Instruction *QueryInst,
457
                                              unsigned *Limit = nullptr);
458
459
  /// This analysis looks for other loads and stores with invariant.group
460
  /// metadata and the same pointer operand. Returns Unknown if it does not
461
  /// find anything, and Def if it can be assumed that 2 instructions load or
462
  /// store the same value and NonLocal which indicate that non-local Def was
463
  /// found, which can be retrieved by calling getNonLocalPointerDependency
464
  /// with the same queried instruction.
465
  MemDepResult getInvariantGroupPointerDependency(LoadInst *LI, BasicBlock *BB);
466
467
  /// Looks at a memory location for a load (specified by MemLocBase, Offs, and
468
  /// Size) and compares it against a load.
469
  ///
470
  /// If the specified load could be safely widened to a larger integer load
471
  /// that is 1) still efficient, 2) safe for the target, and 3) would provide
472
  /// the specified memory location value, then this function returns the size
473
  /// in bytes of the load width to use.  If not, this returns zero.
474
  static unsigned getLoadLoadClobberFullWidthSize(const Value *MemLocBase,
475
                                                  int64_t MemLocOffs,
476
                                                  unsigned MemLocSize,
477
                                                  const LoadInst *LI);
478
479
  /// Release memory in caches.
480
  void releaseMemory();
481
482
private:
483
  MemDepResult getCallDependencyFrom(CallBase *Call, bool isReadOnlyCall,
484
                                     BasicBlock::iterator ScanIt,
485
                                     BasicBlock *BB);
486
  bool getNonLocalPointerDepFromBB(Instruction *QueryInst,
487
                                   const PHITransAddr &Pointer,
488
                                   const MemoryLocation &Loc, bool isLoad,
489
                                   BasicBlock *BB,
490
                                   SmallVectorImpl<NonLocalDepResult> &Result,
491
                                   DenseMap<BasicBlock *, Value *> &Visited,
492
                                   bool SkipFirstBlock = false);
493
  MemDepResult GetNonLocalInfoForBlock(Instruction *QueryInst,
494
                                       const MemoryLocation &Loc, bool isLoad,
495
                                       BasicBlock *BB, NonLocalDepInfo *Cache,
496
                                       unsigned NumSortedEntries);
497
498
  void RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair P);
499
500
  void verifyRemoved(Instruction *Inst) const;
501
};
502
503
/// An analysis that produces \c MemoryDependenceResults for a function.
504
///
505
/// This is essentially a no-op because the results are computed entirely
506
/// lazily.
507
class MemoryDependenceAnalysis
508
    : public AnalysisInfoMixin<MemoryDependenceAnalysis> {
509
  friend AnalysisInfoMixin<MemoryDependenceAnalysis>;
510
511
  static AnalysisKey Key;
512
513
public:
514
  using Result = MemoryDependenceResults;
515
516
  MemoryDependenceResults run(Function &F, FunctionAnalysisManager &AM);
517
};
518
519
/// A wrapper analysis pass for the legacy pass manager that exposes a \c
520
/// MemoryDepnedenceResults instance.
521
class MemoryDependenceWrapperPass : public FunctionPass {
522
  Optional<MemoryDependenceResults> MemDep;
523
524
public:
525
  static char ID;
526
527
  MemoryDependenceWrapperPass();
528
  ~MemoryDependenceWrapperPass() override;
529
530
  /// Pass Implementation stuff.  This doesn't do any analysis eagerly.
531
  bool runOnFunction(Function &) override;
532
533
  /// Clean up memory in between runs
534
  void releaseMemory() override;
535
536
  /// Does not modify anything.  It uses Value Numbering and Alias Analysis.
537
  void getAnalysisUsage(AnalysisUsage &AU) const override;
538
539
1.39M
  MemoryDependenceResults &getMemDep() { return *MemDep; }
540
};
541
542
} // end namespace llvm
543
544
#endif // LLVM_ANALYSIS_MEMORYDEPENDENCEANALYSIS_H