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

source code of llvm/include/llvm/Analysis/MemoryLocation.h