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 
18 #include "llvm/ADT/DenseMapInfo.h"
19 #include "llvm/IR/Metadata.h"
20 #include "llvm/Support/TypeSize.h"
21 
22 #include <optional>
23 
24 namespace llvm {
25 
26 class CallBase;
27 class Instruction;
28 class LoadInst;
29 class StoreInst;
30 class MemTransferInst;
31 class MemIntrinsic;
32 class AtomicCmpXchgInst;
33 class AtomicMemTransferInst;
34 class AtomicMemIntrinsic;
35 class AtomicRMWInst;
36 class AnyMemTransferInst;
37 class AnyMemIntrinsic;
38 class TargetLibraryInfo;
39 class VAArgInst;
40 class 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 class LocationSize {
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 
92 public:
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).
131  constexpr static LocationSize beforeOrAfterPointer() {
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  }
160  uint64_t getValue() const {
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.
212 public:
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.
249  static MemoryLocation getForSource(const MemTransferInst *MTI);
252 
253  /// Return a location representing the destination of a memory set or
254  /// transfer.
255  static MemoryLocation getForDest(const MemIntrinsic *MI);
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.
285  static uint64_t getSizeOrUnknown(const TypeSize &T) {
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.
319 template <> struct DenseMapInfo<LocationSize> {
320  static inline LocationSize getEmptyKey() {
321  return LocationSize::mapEmpty();
322  }
323  static inline LocationSize getTombstoneKey() {
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 
334 template <> struct DenseMapInfo<MemoryLocation> {
335  static inline MemoryLocation getEmptyKey() {
338  }
339  static inline MemoryLocation getTombstoneKey() {
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
llvm::LocationSize::print
void print(raw_ostream &OS) const
Definition: MemoryLocation.cpp:20
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:109
llvm::MemoryLocation::get
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
Definition: MemoryLocation.cpp:36
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::DenseMapInfo< MemoryLocation >::getHashValue
static unsigned getHashValue(const MemoryLocation &Val)
Definition: MemoryLocation.h:343
llvm::VAArgInst
This class represents the va_arg llvm instruction, which returns an argument of the specified type gi...
Definition: Instructions.h:1841
llvm::LocationSize::afterPointer
constexpr static LocationSize afterPointer()
Any location after the base pointer (but still within the underlying object).
Definition: MemoryLocation.h:125
llvm::DenseMapInfo< LocationSize >::getEmptyKey
static LocationSize getEmptyKey()
Definition: MemoryLocation.h:320
Metadata.h
llvm::MemoryLocation::Ptr
const Value * Ptr
The address of the start of the location.
Definition: MemoryLocation.h:219
llvm::MemTransferInst
This class wraps the llvm.memcpy/memmove intrinsics.
Definition: IntrinsicInst.h:1113
llvm::LocationSize::upperBound
static LocationSize upperBound(TypeSize Value)
Definition: MemoryLocation.h:117
llvm::MemoryLocation::getOrNone
static std::optional< MemoryLocation > getOrNone(const Instruction *Inst)
Definition: MemoryLocation.cpp:78
TypeSize.h
llvm::LocationSize::upperBound
static LocationSize upperBound(uint64_t Value)
Definition: MemoryLocation.h:109
llvm::MemoryLocation::getWithNewSize
MemoryLocation getWithNewSize(LocationSize NewSize) const
Definition: MemoryLocation.h:301
llvm::AAMDNodes
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:651
llvm::MemoryLocation::Size
LocationSize Size
The maximum size of the location, in address-units, or UnknownSize if the size is not known.
Definition: MemoryLocation.h:228
llvm::LocationSize::operator==
bool operator==(const LocationSize &Other) const
Definition: MemoryLocation.h:177
llvm::MemIntrinsic
This is the common base class for memset/memcpy/memmove.
Definition: IntrinsicInst.h:1048
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::DenseMapInfo< MemoryLocation >::isEqual
static bool isEqual(const MemoryLocation &LHS, const MemoryLocation &RHS)
Definition: MemoryLocation.h:348
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::LocationSize::isPrecise
bool isPrecise() const
Definition: MemoryLocation.h:167
llvm::MemoryLocation::get
static MemoryLocation get(const Instruction *Inst)
Definition: MemoryLocation.h:243
llvm::MemoryLocation::getSizeOrUnknown
static uint64_t getSizeOrUnknown(const TypeSize &T)
Definition: MemoryLocation.h:285
llvm::LocationSize::toRaw
uint64_t toRaw() const
Definition: MemoryLocation.h:194
llvm::DenseMapInfo< MemoryLocation >::getEmptyKey
static MemoryLocation getEmptyKey()
Definition: MemoryLocation.h:335
llvm::MemoryLocation::AATags
AAMDNodes AATags
The metadata nodes which describes the aliasing of the location (each member is null if that kind of ...
Definition: MemoryLocation.h:232
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
llvm::LocationSize::mayBeBeforePointer
bool mayBeBeforePointer() const
Whether accesses before the base pointer are possible.
Definition: MemoryLocation.h:175
llvm::DenseMapInfo
An information struct used to provide DenseMap with the various necessary components for a given valu...
Definition: APInt.h:34
llvm::LocationSize
Definition: MemoryLocation.h:67
llvm::AtomicMemTransferInst
Definition: IntrinsicInst.h:1007
SI
@ SI
Definition: SIInstrInfo.cpp:7993
llvm::MemoryLocation::getForSource
static MemoryLocation getForSource(const MemTransferInst *MTI)
Return a location representing the source of a memory transfer.
Definition: MemoryLocation.cpp:95
llvm::LocationSize::getValue
uint64_t getValue() const
Definition: MemoryLocation.h:160
llvm::LocationSize::mapTombstone
constexpr static LocationSize mapTombstone()
Definition: MemoryLocation.h:136
llvm::Instruction
Definition: Instruction.h:41
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:292
llvm::LocationSize::precise
static LocationSize precise(uint64_t Value)
Definition: MemoryLocation.h:102
llvm::MemoryLocation::MemoryLocation
MemoryLocation(const Value *Ptr, LocationSize Size, const AAMDNodes &AATags=AAMDNodes())
Definition: MemoryLocation.h:291
llvm::AnyMemTransferInst
Definition: IntrinsicInst.h:1227
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:301
VI
@ VI
Definition: SIInstrInfo.cpp:7994
uint64_t
llvm::LocationSize::hasValue
bool hasValue() const
Definition: MemoryLocation.h:157
llvm::LocationSize::isZero
bool isZero() const
Definition: MemoryLocation.h:172
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MemoryLocation::getForArgument
static MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx, const TargetLibraryInfo *TLI)
Return a location representing a particular argument of a call.
Definition: MemoryLocation.cpp:160
llvm::LocationSize::unionWith
LocationSize unionWith(LocationSize Other) const
Definition: MemoryLocation.h:145
llvm::DenseMapInfo< LocationSize >::getTombstoneKey
static LocationSize getTombstoneKey()
Definition: MemoryLocation.h:323
llvm::MemoryLocation::getForArgument
static MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx, const TargetLibraryInfo &TLI)
Definition: MemoryLocation.h:264
llvm::DenseMapInfo< MemoryLocation >::getTombstoneKey
static MemoryLocation getTombstoneKey()
Definition: MemoryLocation.h:339
llvm::LocationSize::mapEmpty
constexpr static LocationSize mapEmpty()
Definition: MemoryLocation.h:139
llvm::LocationSize::operator!=
bool operator!=(const LocationSize &Other) const
Definition: MemoryLocation.h:181
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:177
llvm::AtomicRMWInst
an instruction that atomically reads a memory location, combines it with another value,...
Definition: Instructions.h:718
llvm::MemoryLocation::getWithoutAATags
MemoryLocation getWithoutAATags() const
Definition: MemoryLocation.h:307
llvm::MemoryLocation::MemoryLocation
MemoryLocation()
Definition: MemoryLocation.h:289
llvm::LocationSize::beforeOrAfterPointer
constexpr static LocationSize beforeOrAfterPointer()
Any location before or after the base pointer (but still within the underlying object).
Definition: MemoryLocation.h:131
llvm::DenseMapInfo< LocationSize >::getHashValue
static unsigned getHashValue(const LocationSize &Val)
Definition: MemoryLocation.h:326
llvm::TypeSize
Definition: TypeSize.h:314
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:234
llvm::MemoryLocation::getWithNewPtr
MemoryLocation getWithNewPtr(const Value *NewPtr) const
Definition: MemoryLocation.h:295
llvm::AtomicMemIntrinsic
Definition: IntrinsicInst.h:955
Other
std::optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1260
llvm::DenseMapInfo< LocationSize >::isEqual
static bool isEqual(const LocationSize &LHS, const LocationSize &RHS)
Definition: MemoryLocation.h:329
llvm::MemoryLocation::getAfter
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...
Definition: MemoryLocation.h:271
llvm::LocationSize::LocationSize
constexpr LocationSize(uint64_t Raw)
Definition: MemoryLocation.h:99
llvm::LocationSize::precise
static LocationSize precise(TypeSize Value)
Definition: MemoryLocation.h:103
DenseMapInfo.h
llvm::MemoryLocation::operator==
bool operator==(const MemoryLocation &Other) const
Definition: MemoryLocation.h:313
llvm::MemoryLocation::getBeforeOrAfter
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...
Definition: MemoryLocation.h:279
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1184
llvm::MemoryLocation::print
void print(raw_ostream &OS) const
Definition: MemoryLocation.h:234
llvm::MemoryLocation::getForDest
static MemoryLocation getForDest(const MemIntrinsic *MI)
Return a location representing the destination of a memory set or transfer.
Definition: MemoryLocation.cpp:108
LLVM_UNLIKELY
#define LLVM_UNLIKELY(EXPR)
Definition: Compiler.h:210
llvm::MemoryLocation::UnknownSize
@ UnknownSize
Definition: MemoryLocation.h:216
llvm::AnyMemIntrinsic
Definition: IntrinsicInst.h:1175
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::AtomicCmpXchgInst
An instruction that atomically checks whether a specified value is in a memory location,...
Definition: Instructions.h:513
llvm::MemoryLocation
Representation for a specific memory location.
Definition: MemoryLocation.h:211