LLVM 18.0.0git
MemoryLocation.h
Go to the documentation of this file.
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
19#include "llvm/IR/Metadata.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
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
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
110 return LocationSize(Value, false /*Scalable*/);
111 }
113 return LocationSize(Value.getKnownMinValue(), Value.isScalable());
114 }
115
117 // You can't go lower than 0, so give a precise result.
118 if (LLVM_UNLIKELY(Value == 0))
119 return precise(0);
120 if (LLVM_UNLIKELY(Value > MaxValue))
121 return afterPointer();
122 return LocationSize(Value | ImpreciseBit, Direct);
123 }
125 if (Value.isScalable())
126 return afterPointer();
127 return upperBound(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).
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`.
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(std::max(getValue(), Other.getValue()));
164 }
165
166 bool hasValue() const {
167 return Value != AfterPointer && Value != BeforeOrAfterPointer;
168 }
169 bool isScalable() const { return (Value & ScalableBit); }
170
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
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.
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
240
241 /// The metadata nodes which describes the aliasing of the location (each
242 /// member is null if that kind of information is unavailable).
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.
263
264 /// Return a location representing the destination of a memory set or
265 /// transfer.
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);
278 }
279
280 /// Return a location that may access any location after Ptr, while remaining
281 /// within the underlying object.
283 const AAMDNodes &AATags = AAMDNodes()) {
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
292 }
293
294 // Return the exact size if the exact size is known at compiletime,
295 // otherwise return MemoryLocation::UnknownSize.
297 return T.isScalable() ? UnknownSize : T.getFixedValue();
298 }
299
300 MemoryLocation() : Ptr(nullptr), Size(LocationSize::beforeOrAfterPointer()) {}
301
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
313 MemoryLocation Copy(*this);
314 Copy.Size = NewSize;
315 return Copy;
316 }
317
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(); }
334 }
335 static unsigned getHashValue(const LocationSize &Val) {
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() {
347 }
351 }
352 static unsigned getHashValue(const MemoryLocation &Val) {
356 }
357 static bool isEqual(const MemoryLocation &LHS, const MemoryLocation &RHS) {
358 return LHS == RHS;
359 }
360};
361} // namespace llvm
362
363#endif
#define LLVM_UNLIKELY(EXPR)
Definition: Compiler.h:222
This file defines DenseMapInfo traits for DenseMap.
uint64_t Size
IRTranslator LLVM IR MI
This file contains the declarations for metadata subclasses.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
Value * RHS
Value * LHS
An instruction that atomically checks whether a specified value is in a memory location,...
Definition: Instructions.h:513
an instruction that atomically reads a memory location, combines it with another value,...
Definition: Instructions.h:718
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1227
An instruction for reading from memory.
Definition: Instructions.h:177
bool hasValue() const
static LocationSize precise(uint64_t Value)
static constexpr LocationSize mapEmpty()
static LocationSize upperBound(TypeSize Value)
bool mayBeBeforePointer() const
Whether accesses before the base pointer are possible.
static constexpr LocationSize beforeOrAfterPointer()
Any location before or after the base pointer (but still within the underlying object).
bool isScalable() const
TypeSize getValue() const
bool isZero() const
void print(raw_ostream &OS) const
bool isPrecise() const
bool operator!=(const LocationSize &Other) const
static constexpr LocationSize afterPointer()
Any location after the base pointer (but still within the underlying object).
uint64_t toRaw() const
LocationSize unionWith(LocationSize Other) const
static LocationSize upperBound(uint64_t Value)
constexpr LocationSize(uint64_t Raw)
static constexpr LocationSize mapTombstone()
bool operator==(const LocationSize &Other) const
static LocationSize precise(TypeSize Value)
This is the common base class for memset/memcpy/memmove.
This class wraps the llvm.memcpy/memmove intrinsics.
Representation for a specific memory location.
MemoryLocation getWithNewSize(LocationSize NewSize) const
MemoryLocation getWithoutAATags() const
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
static MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx, const TargetLibraryInfo &TLI)
static MemoryLocation getForSource(const MemTransferInst *MTI)
Return a location representing the source of a memory transfer.
void print(raw_ostream &OS) const
LocationSize Size
The maximum size of the location, in address-units, or UnknownSize if the size is not known.
static MemoryLocation getBeforeOrAfter(const Value *Ptr, const AAMDNodes &AATags=AAMDNodes())
Return a location that may access any location before or after Ptr, while remaining within the underl...
static MemoryLocation getAfter(const Value *Ptr, const AAMDNodes &AATags=AAMDNodes())
Return a location that may access any location after Ptr, while remaining within the underlying objec...
static MemoryLocation get(const Instruction *Inst)
MemoryLocation getWithNewPtr(const Value *NewPtr) const
AAMDNodes AATags
The metadata nodes which describes the aliasing of the location (each member is null if that kind of ...
const Value * Ptr
The address of the start of the location.
MemoryLocation(const Value *Ptr, LocationSize Size, const AAMDNodes &AATags=AAMDNodes())
static MemoryLocation getForDest(const MemIntrinsic *MI)
Return a location representing the destination of a memory set or transfer.
bool operator==(const MemoryLocation &Other) const
static uint64_t getSizeOrUnknown(const TypeSize &T)
static std::optional< MemoryLocation > getOrNone(const Instruction *Inst)
static MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx, const TargetLibraryInfo *TLI)
Return a location representing a particular argument of a call.
An instruction for storing to memory.
Definition: Instructions.h:301
Provides information about what library functions are available for the current target.
This class represents the va_arg llvm instruction, which returns an argument of the specified type gi...
LLVM Value Representation.
Definition: Value.h:74
constexpr ScalarTy getKnownMinValue() const
Returns the minimum value this quantity can represent.
Definition: TypeSize.h:170
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Other
Any other memory.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:292
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:738
static LocationSize getTombstoneKey()
static bool isEqual(const LocationSize &LHS, const LocationSize &RHS)
static unsigned getHashValue(const LocationSize &Val)
static LocationSize getEmptyKey()
static MemoryLocation getTombstoneKey()
static MemoryLocation getEmptyKey()
static bool isEqual(const MemoryLocation &LHS, const MemoryLocation &RHS)
static unsigned getHashValue(const MemoryLocation &Val)
An information struct used to provide DenseMap with the various necessary components for a given valu...
Definition: DenseMapInfo.h:50