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