LLVM  9.0.0svn
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/Instructions.h"
21 #include "llvm/IR/Metadata.h"
22 
23 namespace llvm {
24 
25 class LoadInst;
26 class StoreInst;
27 class MemTransferInst;
28 class MemIntrinsic;
29 class AtomicMemTransferInst;
30 class AtomicMemIntrinsic;
31 class AnyMemTransferInst;
32 class AnyMemIntrinsic;
33 class TargetLibraryInfo;
34 
35 // Represents the size of a MemoryLocation. Logically, it's an
36 // Optional<uint63_t> that also carries a bit to represent whether the integer
37 // it contains, N, is 'precise'. Precise, in this context, means that we know
38 // that the area of storage referenced by the given MemoryLocation must be
39 // precisely N bytes. An imprecise value is formed as the union of two or more
40 // precise values, and can conservatively represent all of the values unioned
41 // into it. Importantly, imprecise values are an *upper-bound* on the size of a
42 // MemoryLocation.
43 //
44 // Concretely, a precise MemoryLocation is (%p, 4) in
45 // store i32 0, i32* %p
46 //
47 // Since we know that %p must be at least 4 bytes large at this point.
48 // Otherwise, we have UB. An example of an imprecise MemoryLocation is (%p, 4)
49 // at the memcpy in
50 //
51 // %n = select i1 %foo, i64 1, i64 4
52 // call void @llvm.memcpy.p0i8.p0i8.i64(i8* %p, i8* %baz, i64 %n, i32 1,
53 // i1 false)
54 //
55 // ...Since we'll copy *up to* 4 bytes into %p, but we can't guarantee that
56 // we'll ever actually do so.
57 //
58 // If asked to represent a pathologically large value, this will degrade to
59 // None.
60 class LocationSize {
61  enum : uint64_t {
62  Unknown = ~uint64_t(0),
63  ImpreciseBit = uint64_t(1) << 63,
64  MapEmpty = Unknown - 1,
65  MapTombstone = Unknown - 2,
66 
67  // The maximum value we can represent without falling back to 'unknown'.
68  MaxValue = (MapTombstone - 1) & ~ImpreciseBit,
69  };
70 
71  uint64_t Value;
72 
73  // Hack to support implicit construction. This should disappear when the
74  // public LocationSize ctor goes away.
75  enum DirectConstruction { Direct };
76 
77  constexpr LocationSize(uint64_t Raw, DirectConstruction): Value(Raw) {}
78 
79  static_assert(Unknown & ImpreciseBit, "Unknown is imprecise by definition.");
80 public:
81  // FIXME: Migrate all users to construct via either `precise` or `upperBound`,
82  // to make it more obvious at the callsite the kind of size that they're
83  // providing.
84  //
85  // Since the overwhelming majority of users of this provide precise values,
86  // this assumes the provided value is precise.
87  constexpr LocationSize(uint64_t Raw)
88  : Value(Raw > MaxValue ? Unknown : Raw) {}
89 
90  static LocationSize precise(uint64_t Value) { return LocationSize(Value); }
91 
92  static LocationSize upperBound(uint64_t Value) {
93  // You can't go lower than 0, so give a precise result.
94  if (LLVM_UNLIKELY(Value == 0))
95  return precise(0);
96  if (LLVM_UNLIKELY(Value > MaxValue))
97  return unknown();
98  return LocationSize(Value | ImpreciseBit, Direct);
99  }
100 
101  constexpr static LocationSize unknown() {
102  return LocationSize(Unknown, Direct);
103  }
104 
105  // Sentinel values, generally used for maps.
106  constexpr static LocationSize mapTombstone() {
107  return LocationSize(MapTombstone, Direct);
108  }
109  constexpr static LocationSize mapEmpty() {
110  return LocationSize(MapEmpty, Direct);
111  }
112 
113  // Returns a LocationSize that can correctly represent either `*this` or
114  // `Other`.
115  LocationSize unionWith(LocationSize Other) const {
116  if (Other == *this)
117  return *this;
118 
119  if (!hasValue() || !Other.hasValue())
120  return unknown();
121 
122  return upperBound(std::max(getValue(), Other.getValue()));
123  }
124 
125  bool hasValue() const { return Value != Unknown; }
126  uint64_t getValue() const {
127  assert(hasValue() && "Getting value from an unknown LocationSize!");
128  return Value & ~ImpreciseBit;
129  }
130 
131  // Returns whether or not this value is precise. Note that if a value is
132  // precise, it's guaranteed to not be `unknown()`.
133  bool isPrecise() const {
134  return (Value & ImpreciseBit) == 0;
135  }
136 
137  // Convenience method to check if this LocationSize's value is 0.
138  bool isZero() const { return hasValue() && getValue() == 0; }
139 
140  bool operator==(const LocationSize &Other) const {
141  return Value == Other.Value;
142  }
143 
144  bool operator!=(const LocationSize &Other) const {
145  return !(*this == Other);
146  }
147 
148  // Ordering operators are not provided, since it's unclear if there's only one
149  // reasonable way to compare:
150  // - values that don't exist against values that do, and
151  // - precise values to imprecise values
152 
153  void print(raw_ostream &OS) const;
154 
155  // Returns an opaque value that represents this LocationSize. Cannot be
156  // reliably converted back into a LocationSize.
157  uint64_t toRaw() const { return Value; }
158 };
159 
161  Size.print(OS);
162  return OS;
163 }
164 
165 /// Representation for a specific memory location.
166 ///
167 /// This abstraction can be used to represent a specific location in memory.
168 /// The goal of the location is to represent enough information to describe
169 /// abstract aliasing, modification, and reference behaviors of whatever
170 /// value(s) are stored in memory at the particular location.
171 ///
172 /// The primary user of this interface is LLVM's Alias Analysis, but other
173 /// memory analyses such as MemoryDependence can use it as well.
175 public:
176  /// UnknownSize - This is a special value which can be used with the
177  /// size arguments in alias queries to indicate that the caller does not
178  /// know the sizes of the potential memory references.
179  enum : uint64_t { UnknownSize = ~UINT64_C(0) };
180 
181  /// The address of the start of the location.
182  const Value *Ptr;
183 
184  /// The maximum size of the location, in address-units, or
185  /// UnknownSize if the size is not known.
186  ///
187  /// Note that an unknown size does not mean the pointer aliases the entire
188  /// virtual address space, because there are restrictions on stepping out of
189  /// one object and into another. See
190  /// http://llvm.org/docs/LangRef.html#pointeraliasing
192 
193  /// The metadata nodes which describes the aliasing of the location (each
194  /// member is null if that kind of information is unavailable).
196 
197  /// Return a location with information about the memory reference by the given
198  /// instruction.
199  static MemoryLocation get(const LoadInst *LI);
200  static MemoryLocation get(const StoreInst *SI);
201  static MemoryLocation get(const VAArgInst *VI);
202  static MemoryLocation get(const AtomicCmpXchgInst *CXI);
203  static MemoryLocation get(const AtomicRMWInst *RMWI);
204  static MemoryLocation get(const Instruction *Inst) {
205  return *MemoryLocation::getOrNone(Inst);
206  }
208  switch (Inst->getOpcode()) {
209  case Instruction::Load:
210  return get(cast<LoadInst>(Inst));
211  case Instruction::Store:
212  return get(cast<StoreInst>(Inst));
213  case Instruction::VAArg:
214  return get(cast<VAArgInst>(Inst));
215  case Instruction::AtomicCmpXchg:
216  return get(cast<AtomicCmpXchgInst>(Inst));
217  case Instruction::AtomicRMW:
218  return get(cast<AtomicRMWInst>(Inst));
219  default:
220  return None;
221  }
222  }
223 
224  /// Return a location representing the source of a memory transfer.
225  static MemoryLocation getForSource(const MemTransferInst *MTI);
226  static MemoryLocation getForSource(const AtomicMemTransferInst *MTI);
227  static MemoryLocation getForSource(const AnyMemTransferInst *MTI);
228 
229  /// Return a location representing the destination of a memory set or
230  /// transfer.
231  static MemoryLocation getForDest(const MemIntrinsic *MI);
232  static MemoryLocation getForDest(const AtomicMemIntrinsic *MI);
233  static MemoryLocation getForDest(const AnyMemIntrinsic *MI);
234 
235  /// Return a location representing a particular argument of a call.
236  static MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx,
237  const TargetLibraryInfo *TLI);
238  static MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx,
239  const TargetLibraryInfo &TLI) {
240  return getForArgument(Call, ArgIdx, &TLI);
241  }
242 
243  explicit MemoryLocation(const Value *Ptr = nullptr,
245  const AAMDNodes &AATags = AAMDNodes())
246  : Ptr(Ptr), Size(Size), AATags(AATags) {}
247 
248  MemoryLocation getWithNewPtr(const Value *NewPtr) const {
249  MemoryLocation Copy(*this);
250  Copy.Ptr = NewPtr;
251  return Copy;
252  }
253 
255  MemoryLocation Copy(*this);
256  Copy.Size = NewSize;
257  return Copy;
258  }
259 
261  MemoryLocation Copy(*this);
262  Copy.AATags = AAMDNodes();
263  return Copy;
264  }
265 
266  bool operator==(const MemoryLocation &Other) const {
267  return Ptr == Other.Ptr && Size == Other.Size && AATags == Other.AATags;
268  }
269 };
270 
271 // Specialize DenseMapInfo.
272 template <> struct DenseMapInfo<LocationSize> {
273  static inline LocationSize getEmptyKey() {
274  return LocationSize::mapEmpty();
275  }
276  static inline LocationSize getTombstoneKey() {
278  }
279  static unsigned getHashValue(const LocationSize &Val) {
281  }
282  static bool isEqual(const LocationSize &LHS, const LocationSize &RHS) {
283  return LHS == RHS;
284  }
285 };
286 
287 template <> struct DenseMapInfo<MemoryLocation> {
288  static inline MemoryLocation getEmptyKey() {
291  }
292  static inline MemoryLocation getTombstoneKey() {
295  }
296  static unsigned getHashValue(const MemoryLocation &Val) {
300  }
301  static bool isEqual(const MemoryLocation &LHS, const MemoryLocation &RHS) {
302  return LHS == RHS;
303  }
304 };
305 }
306 
307 #endif
bool operator==(const LocationSize &Other) const
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
static bool isEqual(const LocationSize &LHS, const LocationSize &RHS)
#define LLVM_UNLIKELY(EXPR)
Definition: Compiler.h:191
an instruction that atomically checks whether a specified value is in a memory location, and, if it is, stores a new value there.
Definition: Instructions.h:528
MemoryLocation getWithNewPtr(const Value *NewPtr) const
static constexpr LocationSize unknown()
bool isPrecise() const
This file contains the declarations for metadata subclasses.
static LocationSize precise(uint64_t Value)
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1013
An instruction for reading from memory.
Definition: Instructions.h:167
an instruction that atomically reads a memory location, combines it with another value, and then stores the result back.
Definition: Instructions.h:691
static Optional< MemoryLocation > getOrNone(const Instruction *Inst)
static LocationSize getEmptyKey()
static constexpr LocationSize mapTombstone()
bool operator!=(const LocationSize &Other) const
static LocationSize getTombstoneKey()
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:125
An instruction for storing to memory.
Definition: Instructions.h:320
uint64_t getValue() const
MemoryLocation getWithoutAATags() const
MemoryLocation getWithNewSize(LocationSize NewSize) const
LocationSize unionWith(LocationSize Other) const
static constexpr LocationSize mapEmpty()
LocationSize Size
The maximum size of the location, in address-units, or UnknownSize if the size is not known...
bool operator==(const MemoryLocation &Other) const
MemoryLocation(const Value *Ptr=nullptr, LocationSize Size=LocationSize::unknown(), const AAMDNodes &AATags=AAMDNodes())
This class represents the va_arg llvm instruction, which returns an argument of the specified type gi...
constexpr LocationSize(uint64_t Raw)
const Value * Ptr
The address of the start of the location.
Representation for a specific memory location.
This is the common base class for memset/memcpy/memmove.
static unsigned getHashValue(const LocationSize &Val)
Provides information about what library functions are available for the current target.
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:643
static bool isEqual(const MemoryLocation &LHS, const MemoryLocation &RHS)
void print(raw_ostream &OS) const
This class wraps the llvm.memcpy/memmove intrinsics.
AAMDNodes AATags
The metadata nodes which describes the aliasing of the location (each member is null if that kind of ...
static LocationSize upperBound(uint64_t Value)
bool isZero() const
uint32_t Size
Definition: Profile.cpp:46
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2038
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:72
bool hasValue() const
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
static MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx, const TargetLibraryInfo &TLI)
IRTranslator LLVM IR MI
uint64_t toRaw() const
static MemoryLocation getTombstoneKey()
static MemoryLocation getEmptyKey()
static unsigned getHashValue(const MemoryLocation &Val)