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