Coverage Report

Created: 2018-11-16 02:38

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Analysis/MemoryLocation.h
Line
Count
Source (jump to first uncovered line)
1
//===- MemoryLocation.h - Memory location descriptions ----------*- 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
/// \file
10
/// This file provides utility analysis objects describing memory locations.
11
/// These are used both by the Alias Analysis infrastructure and more
12
/// specialized memory analysis layers.
13
///
14
//===----------------------------------------------------------------------===//
15
16
#ifndef LLVM_ANALYSIS_MEMORYLOCATION_H
17
#define LLVM_ANALYSIS_MEMORYLOCATION_H
18
19
#include "llvm/ADT/Optional.h"
20
#include "llvm/ADT/DenseMapInfo.h"
21
#include "llvm/IR/CallSite.h"
22
#include "llvm/IR/Metadata.h"
23
24
namespace llvm {
25
26
class LoadInst;
27
class StoreInst;
28
class MemTransferInst;
29
class MemIntrinsic;
30
class AtomicMemTransferInst;
31
class AtomicMemIntrinsic;
32
class AnyMemTransferInst;
33
class AnyMemIntrinsic;
34
class TargetLibraryInfo;
35
36
// Represents the size of a MemoryLocation. Logically, it's an
37
// Optional<uint63_t> that also carries a bit to represent whether the integer
38
// it contains, N, is 'precise'. Precise, in this context, means that we know
39
// that the area of storage referenced by the given MemoryLocation must be
40
// precisely N bytes. An imprecise value is formed as the union of two or more
41
// precise values, and can conservatively represent all of the values unioned
42
// into it. Importantly, imprecise values are an *upper-bound* on the size of a
43
// MemoryLocation.
44
//
45
// Concretely, a precise MemoryLocation is (%p, 4) in
46
// store i32 0, i32* %p
47
//
48
// Since we know that %p must be at least 4 bytes large at this point.
49
// Otherwise, we have UB. An example of an imprecise MemoryLocation is (%p, 4)
50
// at the memcpy in
51
//
52
//   %n = select i1 %foo, i64 1, i64 4
53
//   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %p, i8* %baz, i64 %n, i32 1,
54
//                                        i1 false)
55
//
56
// ...Since we'll copy *up to* 4 bytes into %p, but we can't guarantee that
57
// we'll ever actually do so.
58
//
59
// If asked to represent a pathologically large value, this will degrade to
60
// None.
61
0
class LocationSize {
Unexecuted instantiation: llvm::LocationSize::operator=(llvm::LocationSize const&)
Unexecuted instantiation: llvm::LocationSize::operator=(llvm::LocationSize&&)
62
  enum : uint64_t {
63
    Unknown = ~uint64_t(0),
64
    ImpreciseBit = uint64_t(1) << 63,
65
    MapEmpty = Unknown - 1,
66
    MapTombstone = Unknown - 2,
67
68
    // The maximum value we can represent without falling back to 'unknown'.
69
    MaxValue = (MapTombstone - 1) & ~ImpreciseBit,
70
  };
71
72
  uint64_t Value;
73
74
  // Hack to support implicit construction. This should disappear when the
75
  // public LocationSize ctor goes away.
76
  enum DirectConstruction { Direct };
77
78
1.50G
  constexpr LocationSize(uint64_t Raw, DirectConstruction): Value(Raw) {}
79
80
  static_assert(Unknown & ImpreciseBit, "Unknown is imprecise by definition.");
81
public:
82
  // FIXME: Migrate all users to construct via either `precise` or `upperBound`,
83
  // to make it more obvious at the callsite the kind of size that they're
84
  // providing.
85
  //
86
  // Since the overwhelming majority of users of this provide precise values,
87
  // this assumes the provided value is precise.
88
  constexpr LocationSize(uint64_t Raw)
89
222M
      : Value(Raw > MaxValue ? Unknown : Raw) {}
90
91
6
  static LocationSize precise(uint64_t Value) { return LocationSize(Value); }
92
93
12.2k
  static LocationSize upperBound(uint64_t Value) {
94
12.2k
    // You can't go lower than 0, so give a precise result.
95
12.2k
    if (LLVM_UNLIKELY(Value == 0))
96
12.2k
      
return precise(0)0
;
97
12.2k
    if (LLVM_UNLIKELY(Value > MaxValue))
98
12.2k
      
return unknown()0
;
99
12.2k
    return LocationSize(Value | ImpreciseBit, Direct);
100
12.2k
  }
101
102
246M
  constexpr static LocationSize unknown() {
103
246M
    return LocationSize(Unknown, Direct);
104
246M
  }
105
106
  // Sentinel values, generally used for maps.
107
514M
  constexpr static LocationSize mapTombstone() {
108
514M
    return LocationSize(MapTombstone, Direct);
109
514M
  }
110
746M
  constexpr static LocationSize mapEmpty() {
111
746M
    return LocationSize(MapEmpty, Direct);
112
746M
  }
113
114
  // Returns a LocationSize that can correctly represent either `*this` or
115
  // `Other`.
116
13.1k
  LocationSize unionWith(LocationSize Other) const {
117
13.1k
    if (Other == *this)
118
0
      return *this;
119
13.1k
120
13.1k
    if (!hasValue() || 
!Other.hasValue()12.5k
)
121
865
      return unknown();
122
12.2k
123
12.2k
    return upperBound(std::max(getValue(), Other.getValue()));
124
12.2k
  }
125
126
25.8k
  bool hasValue() const { return Value != Unknown; }
127
164M
  uint64_t getValue() const {
128
164M
    assert(hasValue() && "Getting value from an unknown LocationSize!");
129
164M
    return Value & ~ImpreciseBit;
130
164M
  }
131
132
  // Returns whether or not this value is precise. Note that if a value is
133
  // precise, it's guaranteed to not be `unknown()`.
134
120M
  bool isPrecise() const {
135
120M
    return (Value & ImpreciseBit) == 0;
136
120M
  }
137
138
1.82G
  bool operator==(const LocationSize &Other) const {
139
1.82G
    return Value == Other.Value;
140
1.82G
  }
141
142
36.3M
  bool operator!=(const LocationSize &Other) const {
143
36.3M
    return !(*this == Other);
144
36.3M
  }
145
146
  // Ordering operators are not provided, since it's unclear if there's only one
147
  // reasonable way to compare:
148
  // - values that don't exist against values that do, and
149
  // - precise values to imprecise values
150
151
  void print(raw_ostream &OS) const;
152
153
  // Returns an opaque value that represents this LocationSize. Cannot be
154
  // reliably converted back into a LocationSize.
155
403M
  uint64_t toRaw() const { return Value; }
156
};
157
158
368
inline raw_ostream &operator<<(raw_ostream &OS, LocationSize Size) {
159
368
  Size.print(OS);
160
368
  return OS;
161
368
}
162
163
/// Representation for a specific memory location.
164
///
165
/// This abstraction can be used to represent a specific location in memory.
166
/// The goal of the location is to represent enough information to describe
167
/// abstract aliasing, modification, and reference behaviors of whatever
168
/// value(s) are stored in memory at the particular location.
169
///
170
/// The primary user of this interface is LLVM's Alias Analysis, but other
171
/// memory analyses such as MemoryDependence can use it as well.
172
0
class MemoryLocation {
Unexecuted instantiation: llvm::MemoryLocation::operator=(llvm::MemoryLocation const&)
Unexecuted instantiation: llvm::MemoryLocation::operator=(llvm::MemoryLocation&&)
173
public:
174
  /// UnknownSize - This is a special value which can be used with the
175
  /// size arguments in alias queries to indicate that the caller does not
176
  /// know the sizes of the potential memory references.
177
  enum : uint64_t { UnknownSize = ~UINT64_C(0) };
178
179
  /// The address of the start of the location.
180
  const Value *Ptr;
181
182
  /// The maximum size of the location, in address-units, or
183
  /// UnknownSize if the size is not known.
184
  ///
185
  /// Note that an unknown size does not mean the pointer aliases the entire
186
  /// virtual address space, because there are restrictions on stepping out of
187
  /// one object and into another. See
188
  /// http://llvm.org/docs/LangRef.html#pointeraliasing
189
  LocationSize Size;
190
191
  /// The metadata nodes which describes the aliasing of the location (each
192
  /// member is null if that kind of information is unavailable).
193
  AAMDNodes AATags;
194
195
  /// Return a location with information about the memory reference by the given
196
  /// instruction.
197
  static MemoryLocation get(const LoadInst *LI);
198
  static MemoryLocation get(const StoreInst *SI);
199
  static MemoryLocation get(const VAArgInst *VI);
200
  static MemoryLocation get(const AtomicCmpXchgInst *CXI);
201
  static MemoryLocation get(const AtomicRMWInst *RMWI);
202
4.46M
  static MemoryLocation get(const Instruction *Inst) {
203
4.46M
    return *MemoryLocation::getOrNone(Inst);
204
4.46M
  }
205
5.11M
  static Optional<MemoryLocation> getOrNone(const Instruction *Inst) {
206
5.11M
    switch (Inst->getOpcode()) {
207
5.11M
    case Instruction::Load:
208
5.08M
      return get(cast<LoadInst>(Inst));
209
5.11M
    case Instruction::Store:
210
28.2k
      return get(cast<StoreInst>(Inst));
211
5.11M
    case Instruction::VAArg:
212
9
      return get(cast<VAArgInst>(Inst));
213
5.11M
    case Instruction::AtomicCmpXchg:
214
0
      return get(cast<AtomicCmpXchgInst>(Inst));
215
5.11M
    case Instruction::AtomicRMW:
216
4.17k
      return get(cast<AtomicRMWInst>(Inst));
217
5.11M
    default:
218
86
      return None;
219
5.11M
    }
220
5.11M
  }
221
222
  /// Return a location representing the source of a memory transfer.
223
  static MemoryLocation getForSource(const MemTransferInst *MTI);
224
  static MemoryLocation getForSource(const AtomicMemTransferInst *MTI);
225
  static MemoryLocation getForSource(const AnyMemTransferInst *MTI);
226
227
  /// Return a location representing the destination of a memory set or
228
  /// transfer.
229
  static MemoryLocation getForDest(const MemIntrinsic *MI);
230
  static MemoryLocation getForDest(const AtomicMemIntrinsic *MI);
231
  static MemoryLocation getForDest(const AnyMemIntrinsic *MI);
232
233
  /// Return a location representing a particular argument of a call.
234
  static MemoryLocation getForArgument(ImmutableCallSite CS, unsigned ArgIdx,
235
                                       const TargetLibraryInfo *TLI);
236
  static MemoryLocation getForArgument(ImmutableCallSite CS, unsigned ArgIdx,
237
1.42M
                                       const TargetLibraryInfo &TLI) {
238
1.42M
    return getForArgument(CS, ArgIdx, &TLI);
239
1.42M
  }
240
241
  explicit MemoryLocation(const Value *Ptr = nullptr,
242
                          LocationSize Size = LocationSize::unknown(),
243
                          const AAMDNodes &AATags = AAMDNodes())
244
1.53G
      : Ptr(Ptr), Size(Size), AATags(AATags) {}
245
246
1.62M
  MemoryLocation getWithNewPtr(const Value *NewPtr) const {
247
1.62M
    MemoryLocation Copy(*this);
248
1.62M
    Copy.Ptr = NewPtr;
249
1.62M
    return Copy;
250
1.62M
  }
251
252
0
  MemoryLocation getWithNewSize(LocationSize NewSize) const {
253
0
    MemoryLocation Copy(*this);
254
0
    Copy.Size = NewSize;
255
0
    return Copy;
256
0
  }
257
258
11.5k
  MemoryLocation getWithoutAATags() const {
259
11.5k
    MemoryLocation Copy(*this);
260
11.5k
    Copy.AATags = AAMDNodes();
261
11.5k
    return Copy;
262
11.5k
  }
263
264
1.80G
  bool operator==(const MemoryLocation &Other) const {
265
1.80G
    return Ptr == Other.Ptr && 
Size == Other.Size1.52G
&&
AATags == Other.AATags1.52G
;
266
1.80G
  }
267
};
268
269
// Specialize DenseMapInfo.
270
template <> struct DenseMapInfo<LocationSize> {
271
741M
  static inline LocationSize getEmptyKey() {
272
741M
    return LocationSize::mapEmpty();
273
741M
  }
274
514M
  static inline LocationSize getTombstoneKey() {
275
514M
    return LocationSize::mapTombstone();
276
514M
  }
277
403M
  static unsigned getHashValue(const LocationSize &Val) {
278
403M
    return DenseMapInfo<uint64_t>::getHashValue(Val.toRaw());
279
403M
  }
280
  static bool isEqual(const LocationSize &LHS, const LocationSize &RHS) {
281
    return LHS == RHS;
282
  }
283
};
284
285
template <> struct DenseMapInfo<MemoryLocation> {
286
741M
  static inline MemoryLocation getEmptyKey() {
287
741M
    return MemoryLocation(DenseMapInfo<const Value *>::getEmptyKey(),
288
741M
                          DenseMapInfo<LocationSize>::getEmptyKey());
289
741M
  }
290
514M
  static inline MemoryLocation getTombstoneKey() {
291
514M
    return MemoryLocation(DenseMapInfo<const Value *>::getTombstoneKey(),
292
514M
                          DenseMapInfo<LocationSize>::getTombstoneKey());
293
514M
  }
294
403M
  static unsigned getHashValue(const MemoryLocation &Val) {
295
403M
    return DenseMapInfo<const Value *>::getHashValue(Val.Ptr) ^
296
403M
           DenseMapInfo<LocationSize>::getHashValue(Val.Size) ^
297
403M
           DenseMapInfo<AAMDNodes>::getHashValue(Val.AATags);
298
403M
  }
299
1.78G
  static bool isEqual(const MemoryLocation &LHS, const MemoryLocation &RHS) {
300
1.78G
    return LHS == RHS;
301
1.78G
  }
302
};
303
}
304
305
#endif