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