LLVM 17.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.
68 enum : uint64_t {
69 BeforeOrAfterPointer = ~uint64_t(0),
70 AfterPointer = BeforeOrAfterPointer - 1,
71 MapEmpty = BeforeOrAfterPointer - 2,
72 MapTombstone = BeforeOrAfterPointer - 3,
73 ImpreciseBit = uint64_t(1) << 63,
74
75 // The maximum value we can represent without falling back to 'unknown'.
76 MaxValue = (MapTombstone - 1) & ~ImpreciseBit,
77 };
78
80
81 // Hack to support implicit construction. This should disappear when the
82 // public LocationSize ctor goes away.
83 enum DirectConstruction { Direct };
84
85 constexpr LocationSize(uint64_t Raw, DirectConstruction): Value(Raw) {}
86
87 static_assert(AfterPointer & ImpreciseBit,
88 "AfterPointer is imprecise by definition.");
89 static_assert(BeforeOrAfterPointer & ImpreciseBit,
90 "BeforeOrAfterPointer is imprecise by definition.");
91
92public:
93 // FIXME: Migrate all users to construct via either `precise` or `upperBound`,
94 // to make it more obvious at the callsite the kind of size that they're
95 // providing.
96 //
97 // Since the overwhelming majority of users of this provide precise values,
98 // this assumes the provided value is precise.
99 constexpr LocationSize(uint64_t Raw)
100 : Value(Raw > MaxValue ? AfterPointer : Raw) {}
101
104 if (Value.isScalable())
105 return afterPointer();
106 return precise(Value.getFixedValue());
107 }
108
110 // You can't go lower than 0, so give a precise result.
111 if (LLVM_UNLIKELY(Value == 0))
112 return precise(0);
113 if (LLVM_UNLIKELY(Value > MaxValue))
114 return afterPointer();
115 return LocationSize(Value | ImpreciseBit, Direct);
116 }
118 if (Value.isScalable())
119 return afterPointer();
120 return upperBound(Value.getFixedValue());
121 }
122
123 /// Any location after the base pointer (but still within the underlying
124 /// object).
125 constexpr static LocationSize afterPointer() {
126 return LocationSize(AfterPointer, Direct);
127 }
128
129 /// Any location before or after the base pointer (but still within the
130 /// underlying object).
132 return LocationSize(BeforeOrAfterPointer, Direct);
133 }
134
135 // Sentinel values, generally used for maps.
136 constexpr static LocationSize mapTombstone() {
137 return LocationSize(MapTombstone, Direct);
138 }
139 constexpr static LocationSize mapEmpty() {
140 return LocationSize(MapEmpty, Direct);
141 }
142
143 // Returns a LocationSize that can correctly represent either `*this` or
144 // `Other`.
146 if (Other == *this)
147 return *this;
148
149 if (Value == BeforeOrAfterPointer || Other.Value == BeforeOrAfterPointer)
150 return beforeOrAfterPointer();
151 if (Value == AfterPointer || Other.Value == AfterPointer)
152 return afterPointer();
153
154 return upperBound(std::max(getValue(), Other.getValue()));
155 }
156
157 bool hasValue() const {
158 return Value != AfterPointer && Value != BeforeOrAfterPointer;
159 }
161 assert(hasValue() && "Getting value from an unknown LocationSize!");
162 return Value & ~ImpreciseBit;
163 }
164
165 // Returns whether or not this value is precise. Note that if a value is
166 // precise, it's guaranteed to not be unknown.
167 bool isPrecise() const {
168 return (Value & ImpreciseBit) == 0;
169 }
170
171 // Convenience method to check if this LocationSize's value is 0.
172 bool isZero() const { return hasValue() && getValue() == 0; }
173
174 /// Whether accesses before the base pointer are possible.
175 bool mayBeBeforePointer() const { return Value == BeforeOrAfterPointer; }
176
177 bool operator==(const LocationSize &Other) const {
178 return Value == Other.Value;
179 }
180
181 bool operator!=(const LocationSize &Other) const {
182 return !(*this == Other);
183 }
184
185 // Ordering operators are not provided, since it's unclear if there's only one
186 // reasonable way to compare:
187 // - values that don't exist against values that do, and
188 // - precise values to imprecise values
189
190 void print(raw_ostream &OS) const;
191
192 // Returns an opaque value that represents this LocationSize. Cannot be
193 // reliably converted back into a LocationSize.
194 uint64_t toRaw() const { return Value; }
195};
196
198 Size.print(OS);
199 return OS;
200}
201
202/// Representation for a specific memory location.
203///
204/// This abstraction can be used to represent a specific location in memory.
205/// The goal of the location is to represent enough information to describe
206/// abstract aliasing, modification, and reference behaviors of whatever
207/// value(s) are stored in memory at the particular location.
208///
209/// The primary user of this interface is LLVM's Alias Analysis, but other
210/// memory analyses such as MemoryDependence can use it as well.
212public:
213 /// UnknownSize - This is a special value which can be used with the
214 /// size arguments in alias queries to indicate that the caller does not
215 /// know the sizes of the potential memory references.
216 enum : uint64_t { UnknownSize = ~UINT64_C(0) };
217
218 /// The address of the start of the location.
219 const Value *Ptr;
220
221 /// The maximum size of the location, in address-units, or
222 /// UnknownSize if the size is not known.
223 ///
224 /// Note that an unknown size does not mean the pointer aliases the entire
225 /// virtual address space, because there are restrictions on stepping out of
226 /// one object and into another. See
227 /// http://llvm.org/docs/LangRef.html#pointeraliasing
229
230 /// The metadata nodes which describes the aliasing of the location (each
231 /// member is null if that kind of information is unavailable).
233
234 void print(raw_ostream &OS) const { OS << *Ptr << " " << Size << "\n"; }
235
236 /// Return a location with information about the memory reference by the given
237 /// instruction.
238 static MemoryLocation get(const LoadInst *LI);
239 static MemoryLocation get(const StoreInst *SI);
240 static MemoryLocation get(const VAArgInst *VI);
241 static MemoryLocation get(const AtomicCmpXchgInst *CXI);
242 static MemoryLocation get(const AtomicRMWInst *RMWI);
243 static MemoryLocation get(const Instruction *Inst) {
244 return *MemoryLocation::getOrNone(Inst);
245 }
246 static std::optional<MemoryLocation> getOrNone(const Instruction *Inst);
247
248 /// Return a location representing the source of a memory transfer.
252
253 /// Return a location representing the destination of a memory set or
254 /// transfer.
258 static std::optional<MemoryLocation> getForDest(const CallBase *CI,
259 const TargetLibraryInfo &TLI);
260
261 /// Return a location representing a particular argument of a call.
262 static MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx,
263 const TargetLibraryInfo *TLI);
264 static MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx,
265 const TargetLibraryInfo &TLI) {
266 return getForArgument(Call, ArgIdx, &TLI);
267 }
268
269 /// Return a location that may access any location after Ptr, while remaining
270 /// within the underlying object.
272 const AAMDNodes &AATags = AAMDNodes()) {
274 }
275
276 /// Return a location that may access any location before or after Ptr, while
277 /// remaining within the underlying object.
278 static MemoryLocation
281 }
282
283 // Return the exact size if the exact size is known at compiletime,
284 // otherwise return MemoryLocation::UnknownSize.
286 return T.isScalable() ? UnknownSize : T.getFixedValue();
287 }
288
289 MemoryLocation() : Ptr(nullptr), Size(LocationSize::beforeOrAfterPointer()) {}
290
292 const AAMDNodes &AATags = AAMDNodes())
293 : Ptr(Ptr), Size(Size), AATags(AATags) {}
294
295 MemoryLocation getWithNewPtr(const Value *NewPtr) const {
296 MemoryLocation Copy(*this);
297 Copy.Ptr = NewPtr;
298 return Copy;
299 }
300
302 MemoryLocation Copy(*this);
303 Copy.Size = NewSize;
304 return Copy;
305 }
306
308 MemoryLocation Copy(*this);
309 Copy.AATags = AAMDNodes();
310 return Copy;
311 }
312
313 bool operator==(const MemoryLocation &Other) const {
314 return Ptr == Other.Ptr && Size == Other.Size && AATags == Other.AATags;
315 }
316};
317
318// Specialize DenseMapInfo.
319template <> struct DenseMapInfo<LocationSize> {
320 static inline LocationSize getEmptyKey() {
321 return LocationSize::mapEmpty();
322 }
325 }
326 static unsigned getHashValue(const LocationSize &Val) {
328 }
329 static bool isEqual(const LocationSize &LHS, const LocationSize &RHS) {
330 return LHS == RHS;
331 }
332};
333
334template <> struct DenseMapInfo<MemoryLocation> {
335 static inline MemoryLocation getEmptyKey() {
338 }
342 }
343 static unsigned getHashValue(const MemoryLocation &Val) {
347 }
348 static bool isEqual(const MemoryLocation &LHS, const MemoryLocation &RHS) {
349 return LHS == RHS;
350 }
351};
352}
353
354#endif
#define LLVM_UNLIKELY(EXPR)
Definition: Compiler.h:210
This file defines DenseMapInfo traits for DenseMap.
uint64_t Size
IRTranslator LLVM IR MI
This file contains the declarations for metadata subclasses.
@ VI
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:1190
An instruction for reading from memory.
Definition: Instructions.h:177
bool hasValue() const
static LocationSize precise(uint64_t Value)
static constexpr LocationSize mapEmpty()
uint64_t getValue() const
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 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
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
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:651
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:51