LLVM  14.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 
40 // Represents the size of a MemoryLocation. Logically, it's an
41 // Optional<uint63_t> that also carries a bit to represent whether the integer
42 // it contains, N, is 'precise'. Precise, in this context, means that we know
43 // 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 // None.
65 class LocationSize {
66  enum : uint64_t {
67  BeforeOrAfterPointer = ~uint64_t(0),
68  AfterPointer = BeforeOrAfterPointer - 1,
69  MapEmpty = BeforeOrAfterPointer - 2,
70  MapTombstone = BeforeOrAfterPointer - 3,
71  ImpreciseBit = uint64_t(1) << 63,
72 
73  // The maximum value we can represent without falling back to 'unknown'.
74  MaxValue = (MapTombstone - 1) & ~ImpreciseBit,
75  };
76 
78 
79  // Hack to support implicit construction. This should disappear when the
80  // public LocationSize ctor goes away.
81  enum DirectConstruction { Direct };
82 
83  constexpr LocationSize(uint64_t Raw, DirectConstruction): Value(Raw) {}
84 
85  static_assert(AfterPointer & ImpreciseBit,
86  "AfterPointer is imprecise by definition.");
87  static_assert(BeforeOrAfterPointer & ImpreciseBit,
88  "BeforeOrAfterPointer is imprecise by definition.");
89 
90 public:
91  // FIXME: Migrate all users to construct via either `precise` or `upperBound`,
92  // to make it more obvious at the callsite the kind of size that they're
93  // providing.
94  //
95  // Since the overwhelming majority of users of this provide precise values,
96  // this assumes the provided value is precise.
97  constexpr LocationSize(uint64_t Raw)
98  : Value(Raw > MaxValue ? AfterPointer : Raw) {}
99 
102  if (Value.isScalable())
103  return afterPointer();
104  return precise(Value.getFixedSize());
105  }
106 
108  // You can't go lower than 0, so give a precise result.
109  if (LLVM_UNLIKELY(Value == 0))
110  return precise(0);
111  if (LLVM_UNLIKELY(Value > MaxValue))
112  return afterPointer();
113  return LocationSize(Value | ImpreciseBit, Direct);
114  }
116  if (Value.isScalable())
117  return afterPointer();
118  return upperBound(Value.getFixedSize());
119  }
120 
121  /// Any location after the base pointer (but still within the underlying
122  /// object).
123  constexpr static LocationSize afterPointer() {
124  return LocationSize(AfterPointer, Direct);
125  }
126 
127  /// Any location before or after the base pointer (but still within the
128  /// underlying object).
129  constexpr static LocationSize beforeOrAfterPointer() {
130  return LocationSize(BeforeOrAfterPointer, Direct);
131  }
132 
133  // Sentinel values, generally used for maps.
134  constexpr static LocationSize mapTombstone() {
135  return LocationSize(MapTombstone, Direct);
136  }
137  constexpr static LocationSize mapEmpty() {
138  return LocationSize(MapEmpty, Direct);
139  }
140 
141  // Returns a LocationSize that can correctly represent either `*this` or
142  // `Other`.
144  if (Other == *this)
145  return *this;
146 
147  if (Value == BeforeOrAfterPointer || Other.Value == BeforeOrAfterPointer)
148  return beforeOrAfterPointer();
149  if (Value == AfterPointer || Other.Value == AfterPointer)
150  return afterPointer();
151 
152  return upperBound(std::max(getValue(), Other.getValue()));
153  }
154 
155  bool hasValue() const {
156  return Value != AfterPointer && Value != BeforeOrAfterPointer;
157  }
158  uint64_t getValue() const {
159  assert(hasValue() && "Getting value from an unknown LocationSize!");
160  return Value & ~ImpreciseBit;
161  }
162 
163  // Returns whether or not this value is precise. Note that if a value is
164  // precise, it's guaranteed to not be unknown.
165  bool isPrecise() const {
166  return (Value & ImpreciseBit) == 0;
167  }
168 
169  // Convenience method to check if this LocationSize's value is 0.
170  bool isZero() const { return hasValue() && getValue() == 0; }
171 
172  /// Whether accesses before the base pointer are possible.
173  bool mayBeBeforePointer() const { return Value == BeforeOrAfterPointer; }
174 
175  bool operator==(const LocationSize &Other) const {
176  return Value == Other.Value;
177  }
178 
179  bool operator!=(const LocationSize &Other) const {
180  return !(*this == Other);
181  }
182 
183  // Ordering operators are not provided, since it's unclear if there's only one
184  // reasonable way to compare:
185  // - values that don't exist against values that do, and
186  // - precise values to imprecise values
187 
188  void print(raw_ostream &OS) const;
189 
190  // Returns an opaque value that represents this LocationSize. Cannot be
191  // reliably converted back into a LocationSize.
192  uint64_t toRaw() const { return Value; }
193 };
194 
196  Size.print(OS);
197  return OS;
198 }
199 
200 /// Representation for a specific memory location.
201 ///
202 /// This abstraction can be used to represent a specific location in memory.
203 /// The goal of the location is to represent enough information to describe
204 /// abstract aliasing, modification, and reference behaviors of whatever
205 /// value(s) are stored in memory at the particular location.
206 ///
207 /// The primary user of this interface is LLVM's Alias Analysis, but other
208 /// memory analyses such as MemoryDependence can use it as well.
210 public:
211  /// UnknownSize - This is a special value which can be used with the
212  /// size arguments in alias queries to indicate that the caller does not
213  /// know the sizes of the potential memory references.
214  enum : uint64_t { UnknownSize = ~UINT64_C(0) };
215 
216  /// The address of the start of the location.
217  const Value *Ptr;
218 
219  /// The maximum size of the location, in address-units, or
220  /// UnknownSize if the size is not known.
221  ///
222  /// Note that an unknown size does not mean the pointer aliases the entire
223  /// virtual address space, because there are restrictions on stepping out of
224  /// one object and into another. See
225  /// http://llvm.org/docs/LangRef.html#pointeraliasing
227 
228  /// The metadata nodes which describes the aliasing of the location (each
229  /// member is null if that kind of information is unavailable).
231 
232  void print(raw_ostream &OS) const { OS << *Ptr << " " << Size << "\n"; }
233 
234  /// Return a location with information about the memory reference by the given
235  /// instruction.
236  static MemoryLocation get(const LoadInst *LI);
237  static MemoryLocation get(const StoreInst *SI);
238  static MemoryLocation get(const VAArgInst *VI);
239  static MemoryLocation get(const AtomicCmpXchgInst *CXI);
240  static MemoryLocation get(const AtomicRMWInst *RMWI);
241  static MemoryLocation get(const Instruction *Inst) {
242  return *MemoryLocation::getOrNone(Inst);
243  }
244  static Optional<MemoryLocation> getOrNone(const Instruction *Inst);
245 
246  /// Return a location representing the source of a memory transfer.
247  static MemoryLocation getForSource(const MemTransferInst *MTI);
250 
251  /// Return a location representing the destination of a memory set or
252  /// transfer.
253  static MemoryLocation getForDest(const MemIntrinsic *MI);
256 
257  /// Return a location representing a particular argument of a call.
258  static MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx,
259  const TargetLibraryInfo *TLI);
260  static MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx,
261  const TargetLibraryInfo &TLI) {
262  return getForArgument(Call, ArgIdx, &TLI);
263  }
264 
265  /// Return a location that may access any location after Ptr, while remaining
266  /// within the underlying object.
268  const AAMDNodes &AATags = AAMDNodes()) {
270  }
271 
272  /// Return a location that may access any location before or after Ptr, while
273  /// remaining within the underlying object.
274  static MemoryLocation
277  }
278 
279  // Return the exact size if the exact size is known at compiletime,
280  // otherwise return MemoryLocation::UnknownSize.
281  static uint64_t getSizeOrUnknown(const TypeSize &T) {
282  return T.isScalable() ? UnknownSize : T.getFixedSize();
283  }
284 
286  : Ptr(nullptr), Size(LocationSize::beforeOrAfterPointer()), AATags() {}
287 
289  const AAMDNodes &AATags = AAMDNodes())
290  : Ptr(Ptr), Size(Size), AATags(AATags) {}
291 
292  MemoryLocation getWithNewPtr(const Value *NewPtr) const {
293  MemoryLocation Copy(*this);
294  Copy.Ptr = NewPtr;
295  return Copy;
296  }
297 
299  MemoryLocation Copy(*this);
300  Copy.Size = NewSize;
301  return Copy;
302  }
303 
305  MemoryLocation Copy(*this);
306  Copy.AATags = AAMDNodes();
307  return Copy;
308  }
309 
310  bool operator==(const MemoryLocation &Other) const {
311  return Ptr == Other.Ptr && Size == Other.Size && AATags == Other.AATags;
312  }
313 };
314 
315 // Specialize DenseMapInfo.
316 template <> struct DenseMapInfo<LocationSize> {
317  static inline LocationSize getEmptyKey() {
318  return LocationSize::mapEmpty();
319  }
320  static inline LocationSize getTombstoneKey() {
322  }
323  static unsigned getHashValue(const LocationSize &Val) {
325  }
326  static bool isEqual(const LocationSize &LHS, const LocationSize &RHS) {
327  return LHS == RHS;
328  }
329 };
330 
331 template <> struct DenseMapInfo<MemoryLocation> {
332  static inline MemoryLocation getEmptyKey() {
335  }
336  static inline MemoryLocation getTombstoneKey() {
339  }
340  static unsigned getHashValue(const MemoryLocation &Val) {
344  }
345  static bool isEqual(const MemoryLocation &LHS, const MemoryLocation &RHS) {
346  return LHS == RHS;
347  }
348 };
349 }
350 
351 #endif
llvm::Check::Size
@ Size
Definition: FileCheck.h:73
llvm::LocationSize::print
void print(raw_ostream &OS) const
Definition: MemoryLocation.cpp:21
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:103
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:37
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::DenseMapInfo< MemoryLocation >::getHashValue
static unsigned getHashValue(const MemoryLocation &Val)
Definition: MemoryLocation.h:340
llvm::VAArgInst
This class represents the va_arg llvm instruction, which returns an argument of the specified type gi...
Definition: Instructions.h:1833
Optional.h
llvm::LocationSize::afterPointer
constexpr static LocationSize afterPointer()
Any location after the base pointer (but still within the underlying object).
Definition: MemoryLocation.h:123
llvm::DenseMapInfo< LocationSize >::getEmptyKey
static LocationSize getEmptyKey()
Definition: MemoryLocation.h:317
Metadata.h
llvm::MemoryLocation::Ptr
const Value * Ptr
The address of the start of the location.
Definition: MemoryLocation.h:217
llvm::MemTransferInst
This class wraps the llvm.memcpy/memmove intrinsics.
Definition: IntrinsicInst.h:917
llvm::LocationSize::upperBound
static LocationSize upperBound(TypeSize Value)
Definition: MemoryLocation.h:115
TypeSize.h
llvm::LocationSize::upperBound
static LocationSize upperBound(uint64_t Value)
Definition: MemoryLocation.h:107
llvm::MemoryLocation::getWithNewSize
MemoryLocation getWithNewSize(LocationSize NewSize) const
Definition: MemoryLocation.h:298
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:226
llvm::LocationSize::operator==
bool operator==(const LocationSize &Other) const
Definition: MemoryLocation.h:175
llvm::MemIntrinsic
This is the common base class for memset/memcpy/memmove.
Definition: IntrinsicInst.h:874
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:345
llvm::LocationSize::isPrecise
bool isPrecise() const
Definition: MemoryLocation.h:165
llvm::MemoryLocation::get
static MemoryLocation get(const Instruction *Inst)
Definition: MemoryLocation.h:241
llvm::MemoryLocation::getSizeOrUnknown
static uint64_t getSizeOrUnknown(const TypeSize &T)
Definition: MemoryLocation.h:281
llvm::LocationSize::toRaw
uint64_t toRaw() const
Definition: MemoryLocation.h:192
llvm::DenseMapInfo< MemoryLocation >::getEmptyKey
static MemoryLocation getEmptyKey()
Definition: MemoryLocation.h:332
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:230
llvm::LocationSize::mayBeBeforePointer
bool mayBeBeforePointer() const
Whether accesses before the base pointer are possible.
Definition: MemoryLocation.h:173
llvm::DenseMapInfo
Definition: APInt.h:34
llvm::LocationSize
Definition: MemoryLocation.h:65
llvm::AtomicMemTransferInst
Definition: IntrinsicInst.h:833
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:158
llvm::LocationSize::mapTombstone
constexpr static LocationSize mapTombstone()
Definition: MemoryLocation.h:134
llvm::Instruction
Definition: Instruction.h:45
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
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:100
llvm::MemoryLocation::UnknownSize
@ UnknownSize
Definition: MemoryLocation.h:214
llvm::MemoryLocation::MemoryLocation
MemoryLocation(const Value *Ptr, LocationSize Size, const AAMDNodes &AATags=AAMDNodes())
Definition: MemoryLocation.h:288
llvm::AnyMemTransferInst
Definition: IntrinsicInst.h:1029
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:304
VI
@ VI
Definition: SIInstrInfo.cpp:7679
llvm::MemoryLocation::getOrNone
static Optional< MemoryLocation > getOrNone(const Instruction *Inst)
Definition: MemoryLocation.cpp:78
uint64_t
llvm::LocationSize::hasValue
bool hasValue() const
Definition: MemoryLocation.h:155
llvm::LocationSize::isZero
bool isZero() const
Definition: MemoryLocation.h:170
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:131
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::LocationSize::unionWith
LocationSize unionWith(LocationSize Other) const
Definition: MemoryLocation.h:143
llvm::DenseMapInfo< LocationSize >::getTombstoneKey
static LocationSize getTombstoneKey()
Definition: MemoryLocation.h:320
llvm::MemoryLocation::getForArgument
static MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx, const TargetLibraryInfo &TLI)
Definition: MemoryLocation.h:260
llvm::DenseMapInfo< MemoryLocation >::getTombstoneKey
static MemoryLocation getTombstoneKey()
Definition: MemoryLocation.h:336
llvm::LocationSize::mapEmpty
constexpr static LocationSize mapEmpty()
Definition: MemoryLocation.h:137
llvm::LocationSize::operator!=
bool operator!=(const LocationSize &Other) const
Definition: MemoryLocation.h:179
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:175
llvm::AtomicRMWInst
an instruction that atomically reads a memory location, combines it with another value,...
Definition: Instructions.h:726
llvm::MemoryLocation::getWithoutAATags
MemoryLocation getWithoutAATags() const
Definition: MemoryLocation.h:304
llvm::MemoryLocation::MemoryLocation
MemoryLocation()
Definition: MemoryLocation.h:285
llvm::LocationSize::beforeOrAfterPointer
constexpr static LocationSize beforeOrAfterPointer()
Any location before or after the base pointer (but still within the underlying object).
Definition: MemoryLocation.h:129
llvm::DenseMapInfo< LocationSize >::getHashValue
static unsigned getHashValue(const LocationSize &Val)
Definition: MemoryLocation.h:323
llvm::TypeSize
Definition: TypeSize.h:417
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:219
llvm::MemoryLocation::getWithNewPtr
MemoryLocation getWithNewPtr(const Value *NewPtr) const
Definition: MemoryLocation.h:292
llvm::AtomicMemIntrinsic
Definition: IntrinsicInst.h:781
llvm::DenseMapInfo< LocationSize >::isEqual
static bool isEqual(const LocationSize &LHS, const LocationSize &RHS)
Definition: MemoryLocation.h:326
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:267
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
llvm::LocationSize::LocationSize
constexpr LocationSize(uint64_t Raw)
Definition: MemoryLocation.h:97
llvm::LocationSize::precise
static LocationSize precise(TypeSize Value)
Definition: MemoryLocation.h:101
DenseMapInfo.h
llvm::MemoryLocation::operator==
bool operator==(const MemoryLocation &Other) const
Definition: MemoryLocation.h:310
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:275
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1161
llvm::MemoryLocation::print
void print(raw_ostream &OS) const
Definition: MemoryLocation.h:232
llvm::MemoryLocation::getForDest
static MemoryLocation getForDest(const MemIntrinsic *MI)
Return a location representing the destination of a memory set or transfer.
Definition: MemoryLocation.cpp:113
LLVM_UNLIKELY
#define LLVM_UNLIKELY(EXPR)
Definition: Compiler.h:220
llvm::AnyMemIntrinsic
Definition: IntrinsicInst.h:979
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::AtomicCmpXchgInst
An instruction that atomically checks whether a specified value is in a memory location,...
Definition: Instructions.h:521
llvm::MemoryLocation
Representation for a specific memory location.
Definition: MemoryLocation.h:209
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1172