LLVM 22.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"
22
23#include <optional>
24
25namespace llvm {
26
27class CallBase;
28class Instruction;
29class LoadInst;
30class StoreInst;
31class MemTransferInst;
32class MemIntrinsic;
33class AtomicCmpXchgInst;
34class AtomicRMWInst;
35class AnyMemTransferInst;
36class AnyMemIntrinsic;
37class TargetLibraryInfo;
38class VAArgInst;
39
40// Represents the size of a MemoryLocation. Logically, it's an
41// std::optional<uint63_t> that also carries a bit to represent whether the
42// integer it contains, N, is 'precise'. Precise, in this context, means that we
43// know 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// std::nullopt.
65// Store Scalable information in bit 62 of Value. Scalable information is
66// required to do Alias Analysis on Scalable quantities
68 enum : uint64_t {
69 BeforeOrAfterPointer = ~uint64_t(0),
70 ScalableBit = uint64_t(1) << 62,
71 AfterPointer = (BeforeOrAfterPointer - 1) & ~ScalableBit,
72 MapEmpty = BeforeOrAfterPointer - 2,
73 MapTombstone = BeforeOrAfterPointer - 3,
74 ImpreciseBit = uint64_t(1) << 63,
75
76 // The maximum value we can represent without falling back to 'unknown'.
77 MaxValue = (MapTombstone - 1) & ~(ImpreciseBit | ScalableBit),
78 };
79
81
82 constexpr LocationSize(uint64_t Raw) : Value(Raw) {}
83 constexpr LocationSize(uint64_t Raw, bool Scalable)
84 : Value(Raw > MaxValue ? AfterPointer
85 : Raw | (Scalable ? ScalableBit : uint64_t(0))) {}
86
87 static_assert(AfterPointer & ImpreciseBit,
88 "AfterPointer is imprecise by definition.");
89 static_assert(BeforeOrAfterPointer & ImpreciseBit,
90 "BeforeOrAfterPointer is imprecise by definition.");
91 static_assert(~(MaxValue & ScalableBit), "Max value don't have bit 62 set");
92
93public:
94 // Create non-scalable LocationSize
96 return LocationSize(Value, false /*Scalable*/);
97 }
99 return LocationSize(Value.getKnownMinValue(), Value.isScalable());
100 }
101
103 // You can't go lower than 0, so give a precise result.
104 if (LLVM_UNLIKELY(Value == 0))
105 return precise(0);
106 if (LLVM_UNLIKELY(Value > MaxValue))
107 return afterPointer();
108 return LocationSize(Value | ImpreciseBit);
109 }
111 if (Value.isScalable())
112 return afterPointer();
113 return upperBound(Value.getFixedValue());
114 }
115
116 /// Any location after the base pointer (but still within the underlying
117 /// object).
118 constexpr static LocationSize afterPointer() {
119 return LocationSize(AfterPointer);
120 }
121
122 /// Any location before or after the base pointer (but still within the
123 /// underlying object).
125 return LocationSize(BeforeOrAfterPointer);
126 }
127
128 // Sentinel values, generally used for maps.
129 constexpr static LocationSize mapTombstone() {
130 return LocationSize(MapTombstone);
131 }
132 constexpr static LocationSize mapEmpty() {
133 return LocationSize(MapEmpty);
134 }
135
136 // Returns a LocationSize that can correctly represent either `*this` or
137 // `Other`.
139 if (Other == *this)
140 return *this;
141
142 if (Value == BeforeOrAfterPointer || Other.Value == BeforeOrAfterPointer)
143 return beforeOrAfterPointer();
144 if (Value == AfterPointer || Other.Value == AfterPointer)
145 return afterPointer();
146 if (isScalable() || Other.isScalable())
147 return afterPointer();
148
149 return upperBound(std::max(getValue(), Other.getValue()));
150 }
151
152 bool hasValue() const {
153 return Value != AfterPointer && Value != BeforeOrAfterPointer;
154 }
155 bool isScalable() const { return (Value & ScalableBit); }
156
158 assert(hasValue() && "Getting value from an unknown LocationSize!");
159 assert((Value & ~(ImpreciseBit | ScalableBit)) < MaxValue &&
160 "Scalable bit of value should be masked");
161 return {Value & ~(ImpreciseBit | ScalableBit), isScalable()};
162 }
163
164 // Returns whether or not this value is precise. Note that if a value is
165 // precise, it's guaranteed to not be unknown.
166 bool isPrecise() const { return (Value & ImpreciseBit) == 0; }
167
168 // Convenience method to check if this LocationSize's value is 0.
169 bool isZero() const {
170 return hasValue() && getValue().getKnownMinValue() == 0;
171 }
172
173 /// Whether accesses before the base pointer are possible.
174 bool mayBeBeforePointer() const { return Value == BeforeOrAfterPointer; }
175
176 bool operator==(const LocationSize &Other) const {
177 return Value == Other.Value;
178 }
179 bool operator==(const TypeSize &Other) const {
180 return (*this == LocationSize::precise(Other));
181 }
183 return (*this == LocationSize::precise(Other));
184 }
185
186 bool operator!=(const LocationSize &Other) const { return !(*this == Other); }
187 bool operator!=(const TypeSize &Other) const { return !(*this == Other); }
188 bool operator!=(uint64_t Other) const { return !(*this == Other); }
189
190 // Ordering operators are not provided, since it's unclear if there's only one
191 // reasonable way to compare:
192 // - values that don't exist against values that do, and
193 // - precise values to imprecise values
194
195 LLVM_ABI void print(raw_ostream &OS) const;
196
197 // Returns an opaque value that represents this LocationSize. Cannot be
198 // reliably converted back into a LocationSize.
199 uint64_t toRaw() const { return Value; }
200};
201
203 Size.print(OS);
204 return OS;
205}
206
207/// Representation for a specific memory location.
208///
209/// This abstraction can be used to represent a specific location in memory.
210/// The goal of the location is to represent enough information to describe
211/// abstract aliasing, modification, and reference behaviors of whatever
212/// value(s) are stored in memory at the particular location.
213///
214/// The primary user of this interface is LLVM's Alias Analysis, but other
215/// memory analyses such as MemoryDependence can use it as well.
217public:
218 /// UnknownSize - This is a special value which can be used with the
219 /// size arguments in alias queries to indicate that the caller does not
220 /// know the sizes of the potential memory references.
221 enum : uint64_t { UnknownSize = ~UINT64_C(0) };
222
223 /// The address of the start of the location.
224 const Value *Ptr;
225
226 /// The maximum size of the location, in address-units, or
227 /// UnknownSize if the size is not known.
228 ///
229 /// Note that an unknown size does not mean the pointer aliases the entire
230 /// virtual address space, because there are restrictions on stepping out of
231 /// one object and into another. See
232 /// http://llvm.org/docs/LangRef.html#pointeraliasing
234
235 /// The metadata nodes which describes the aliasing of the location (each
236 /// member is null if that kind of information is unavailable).
238
239 void print(raw_ostream &OS) const { OS << *Ptr << " " << Size << "\n"; }
240
241 /// Return a location with information about the memory reference by the given
242 /// instruction.
243 LLVM_ABI static MemoryLocation get(const LoadInst *LI);
244 LLVM_ABI static MemoryLocation get(const StoreInst *SI);
245 LLVM_ABI static MemoryLocation get(const VAArgInst *VI);
246 LLVM_ABI static MemoryLocation get(const AtomicCmpXchgInst *CXI);
247 LLVM_ABI static MemoryLocation get(const AtomicRMWInst *RMWI);
248 static MemoryLocation get(const Instruction *Inst) {
249 return *MemoryLocation::getOrNone(Inst);
250 }
251 LLVM_ABI static std::optional<MemoryLocation>
252 getOrNone(const Instruction *Inst);
253
254 /// Return a location representing the source of a memory transfer.
257
258 /// Return a location representing the destination of a memory set or
259 /// transfer.
262 LLVM_ABI static std::optional<MemoryLocation>
263 getForDest(const CallBase *CI, const TargetLibraryInfo &TLI);
264
265 /// Return a location representing a particular argument of a call.
267 unsigned ArgIdx,
268 const TargetLibraryInfo *TLI);
269 static MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx,
270 const TargetLibraryInfo &TLI) {
271 return getForArgument(Call, ArgIdx, &TLI);
272 }
273
274 /// Return a location that may access any location after Ptr, while remaining
275 /// within the underlying object.
277 const AAMDNodes &AATags = AAMDNodes()) {
279 }
280
281 /// Return a location that may access any location before or after Ptr, while
282 /// remaining within the underlying object.
283 static MemoryLocation
286 }
287
288 MemoryLocation() : Ptr(nullptr), Size(LocationSize::beforeOrAfterPointer()) {}
289
291 const AAMDNodes &AATags = AAMDNodes())
292 : Ptr(Ptr), Size(Size), AATags(AATags) {}
294 const AAMDNodes &AATags = AAMDNodes())
295 : Ptr(Ptr), Size(LocationSize::precise(Size)), AATags(AATags) {}
297 const AAMDNodes &AATags = AAMDNodes())
298 : Ptr(Ptr), Size(LocationSize::precise(Size)), AATags(AATags) {}
299
300 MemoryLocation getWithNewPtr(const Value *NewPtr) const {
301 MemoryLocation Copy(*this);
302 Copy.Ptr = NewPtr;
303 return Copy;
304 }
305
307 MemoryLocation Copy(*this);
308 Copy.Size = NewSize;
309 return Copy;
310 }
312 return getWithNewSize(LocationSize::precise(NewSize));
313 }
315 return getWithNewSize(LocationSize::precise(NewSize));
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
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
#define LLVM_UNLIKELY(EXPR)
Definition: Compiler.h:336
#define LLVM_ABI
Definition: Compiler.h:213
This file defines DenseMapInfo traits for DenseMap.
uint64_t Size
IRTranslator LLVM IR MI
This file contains the declarations for metadata subclasses.
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:506
an instruction that atomically reads a memory location, combines it with another value,...
Definition: Instructions.h:709
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1116
An instruction for reading from memory.
Definition: Instructions.h:180
bool hasValue() const
static LocationSize precise(uint64_t Value)
bool operator!=(uint64_t Other) const
static constexpr LocationSize mapEmpty()
static LocationSize upperBound(TypeSize Value)
bool mayBeBeforePointer() const
Whether accesses before the base pointer are possible.
bool operator==(const TypeSize &Other) const
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
LLVM_ABI void print(raw_ostream &OS) const
bool operator!=(const TypeSize &Other) 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
bool operator==(uint64_t Other) const
static LocationSize upperBound(uint64_t Value)
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(const Value *Ptr, TypeSize Size, const AAMDNodes &AATags=AAMDNodes())
MemoryLocation getWithNewSize(LocationSize NewSize) const
MemoryLocation getWithoutAATags() const
static LLVM_ABI 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 LLVM_ABI 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 getWithNewSize(uint64_t NewSize) const
MemoryLocation getWithNewPtr(const Value *NewPtr) const
MemoryLocation getWithNewSize(TypeSize NewSize) 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 LLVM_ABI MemoryLocation getForDest(const MemIntrinsic *MI)
Return a location representing the destination of a memory set or transfer.
bool operator==(const MemoryLocation &Other) const
MemoryLocation(const Value *Ptr, uint64_t Size, const AAMDNodes &AATags=AAMDNodes())
static LLVM_ABI std::optional< MemoryLocation > getOrNone(const Instruction *Inst)
static LLVM_ABI 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:296
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:75
constexpr ScalarTy getKnownMinValue() const
Returns the minimum value this quantity can represent.
Definition: TypeSize.h:169
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
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:312
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:760
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:54