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 | |
23 | namespace llvm { |
24 | |
25 | class CallBase; |
26 | class Instruction; |
27 | class LoadInst; |
28 | class StoreInst; |
29 | class MemTransferInst; |
30 | class MemIntrinsic; |
31 | class AtomicCmpXchgInst; |
32 | class AtomicMemTransferInst; |
33 | class AtomicMemIntrinsic; |
34 | class AtomicRMWInst; |
35 | class AnyMemTransferInst; |
36 | class AnyMemIntrinsic; |
37 | class TargetLibraryInfo; |
38 | class 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. |
65 | class 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 | |
90 | public: |
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 | |
195 | inline 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. |
209 | class MemoryLocation { |
210 | public: |
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. |
316 | template <> 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 | |
331 | template <> 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 | |