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