Coverage Report

Created: 2019-07-24 05:18

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