Line data Source code
1 : //===- MemoryLocation.h - Memory location descriptions ----------*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : /// \file
10 : /// This file provides utility analysis objects describing memory locations.
11 : /// These are used both by the Alias Analysis infrastructure and more
12 : /// specialized memory analysis layers.
13 : ///
14 : //===----------------------------------------------------------------------===//
15 :
16 : #ifndef LLVM_ANALYSIS_MEMORYLOCATION_H
17 : #define LLVM_ANALYSIS_MEMORYLOCATION_H
18 :
19 : #include "llvm/ADT/Optional.h"
20 : #include "llvm/ADT/DenseMapInfo.h"
21 : #include "llvm/IR/CallSite.h"
22 : #include "llvm/IR/Metadata.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 7449125 : : Value(Raw > MaxValue ? Unknown : Raw) {}
90 :
91 : static LocationSize precise(uint64_t Value) { return LocationSize(Value); }
92 :
93 : static LocationSize upperBound(uint64_t Value) {
94 : // You can't go lower than 0, so give a precise result.
95 6641 : if (LLVM_UNLIKELY(Value == 0))
96 : return precise(0);
97 6641 : if (LLVM_UNLIKELY(Value > MaxValue))
98 : return unknown();
99 6641 : return LocationSize(Value | ImpreciseBit, Direct);
100 : }
101 :
102 : constexpr static LocationSize unknown() {
103 : return LocationSize(Unknown, Direct);
104 : }
105 :
106 : // Sentinel values, generally used for maps.
107 : constexpr static LocationSize mapTombstone() {
108 : return LocationSize(MapTombstone, Direct);
109 : }
110 : constexpr static LocationSize mapEmpty() {
111 : return LocationSize(MapEmpty, Direct);
112 : }
113 :
114 : // Returns a LocationSize that can correctly represent either `*this` or
115 : // `Other`.
116 6864 : LocationSize unionWith(LocationSize Other) const {
117 6864 : if (Other == *this)
118 0 : return *this;
119 :
120 6864 : if (!hasValue() || !Other.hasValue())
121 223 : return unknown();
122 :
123 13282 : return upperBound(std::max(getValue(), Other.getValue()));
124 : }
125 :
126 0 : bool hasValue() const { return Value != Unknown; }
127 0 : uint64_t getValue() const {
128 : assert(hasValue() && "Getting value from an unknown LocationSize!");
129 42901618 : return Value & ~ImpreciseBit;
130 : }
131 :
132 : // Returns whether or not this value is precise. Note that if a value is
133 : // precise, it's guaranteed to not be `unknown()`.
134 0 : bool isPrecise() const {
135 33667452 : return (Value & ImpreciseBit) == 0;
136 : }
137 :
138 0 : bool operator==(const LocationSize &Other) const {
139 0 : return Value == Other.Value;
140 : }
141 :
142 : bool operator!=(const LocationSize &Other) const {
143 1861743 : return !(*this == Other);
144 : }
145 :
146 : // Ordering operators are not provided, since it's unclear if there's only one
147 : // reasonable way to compare:
148 : // - values that don't exist against values that do, and
149 : // - precise values to imprecise values
150 :
151 : void print(raw_ostream &OS) const;
152 :
153 : // Returns an opaque value that represents this LocationSize. Cannot be
154 : // reliably converted back into a LocationSize.
155 0 : uint64_t toRaw() const { return Value; }
156 : };
157 :
158 : inline raw_ostream &operator<<(raw_ostream &OS, LocationSize Size) {
159 368 : Size.print(OS);
160 : return OS;
161 : }
162 :
163 : /// Representation for a specific memory location.
164 : ///
165 : /// This abstraction can be used to represent a specific location in memory.
166 : /// The goal of the location is to represent enough information to describe
167 : /// abstract aliasing, modification, and reference behaviors of whatever
168 : /// value(s) are stored in memory at the particular location.
169 : ///
170 : /// The primary user of this interface is LLVM's Alias Analysis, but other
171 : /// memory analyses such as MemoryDependence can use it as well.
172 : class MemoryLocation {
173 : public:
174 : /// UnknownSize - This is a special value which can be used with the
175 : /// size arguments in alias queries to indicate that the caller does not
176 : /// know the sizes of the potential memory references.
177 : enum : uint64_t { UnknownSize = ~UINT64_C(0) };
178 :
179 : /// The address of the start of the location.
180 : const Value *Ptr;
181 :
182 : /// The maximum size of the location, in address-units, or
183 : /// UnknownSize if the size is not known.
184 : ///
185 : /// Note that an unknown size does not mean the pointer aliases the entire
186 : /// virtual address space, because there are restrictions on stepping out of
187 : /// one object and into another. See
188 : /// http://llvm.org/docs/LangRef.html#pointeraliasing
189 : LocationSize Size;
190 :
191 : /// The metadata nodes which describes the aliasing of the location (each
192 : /// member is null if that kind of information is unavailable).
193 : AAMDNodes AATags;
194 :
195 : /// Return a location with information about the memory reference by the given
196 : /// instruction.
197 : static MemoryLocation get(const LoadInst *LI);
198 : static MemoryLocation get(const StoreInst *SI);
199 : static MemoryLocation get(const VAArgInst *VI);
200 : static MemoryLocation get(const AtomicCmpXchgInst *CXI);
201 : static MemoryLocation get(const AtomicRMWInst *RMWI);
202 : static MemoryLocation get(const Instruction *Inst) {
203 1652737 : return *MemoryLocation::getOrNone(Inst);
204 : }
205 1795408 : static Optional<MemoryLocation> getOrNone(const Instruction *Inst) {
206 1795408 : switch (Inst->getOpcode()) {
207 : case Instruction::Load:
208 1781461 : return get(cast<LoadInst>(Inst));
209 : case Instruction::Store:
210 13922 : return get(cast<StoreInst>(Inst));
211 : case Instruction::VAArg:
212 0 : return get(cast<VAArgInst>(Inst));
213 : case Instruction::AtomicCmpXchg:
214 0 : return get(cast<AtomicCmpXchgInst>(Inst));
215 : case Instruction::AtomicRMW:
216 0 : return get(cast<AtomicRMWInst>(Inst));
217 : default:
218 : return None;
219 : }
220 : }
221 :
222 : /// Return a location representing the source of a memory transfer.
223 : static MemoryLocation getForSource(const MemTransferInst *MTI);
224 : static MemoryLocation getForSource(const AtomicMemTransferInst *MTI);
225 : static MemoryLocation getForSource(const AnyMemTransferInst *MTI);
226 :
227 : /// Return a location representing the destination of a memory set or
228 : /// transfer.
229 : static MemoryLocation getForDest(const MemIntrinsic *MI);
230 : static MemoryLocation getForDest(const AtomicMemIntrinsic *MI);
231 : static MemoryLocation getForDest(const AnyMemIntrinsic *MI);
232 :
233 : /// Return a location representing a particular argument of a call.
234 : static MemoryLocation getForArgument(ImmutableCallSite CS, unsigned ArgIdx,
235 : const TargetLibraryInfo *TLI);
236 : static MemoryLocation getForArgument(ImmutableCallSite CS, unsigned ArgIdx,
237 : const TargetLibraryInfo &TLI) {
238 5310593 : return getForArgument(CS, ArgIdx, &TLI);
239 : }
240 :
241 : explicit MemoryLocation(const Value *Ptr = nullptr,
242 : LocationSize Size = LocationSize::unknown(),
243 : const AAMDNodes &AATags = AAMDNodes())
244 40179728 : : Ptr(Ptr), Size(Size), AATags(AATags) {}
245 :
246 : MemoryLocation getWithNewPtr(const Value *NewPtr) const {
247 226003 : MemoryLocation Copy(*this);
248 226003 : Copy.Ptr = NewPtr;
249 : return Copy;
250 : }
251 :
252 : MemoryLocation getWithNewSize(LocationSize NewSize) const {
253 0 : MemoryLocation Copy(*this);
254 0 : Copy.Size = NewSize;
255 : return Copy;
256 : }
257 :
258 : MemoryLocation getWithoutAATags() const {
259 11790 : MemoryLocation Copy(*this);
260 11790 : Copy.AATags = AAMDNodes();
261 : return Copy;
262 : }
263 :
264 : bool operator==(const MemoryLocation &Other) const {
265 267038195 : return Ptr == Other.Ptr && Size == Other.Size && AATags == Other.AATags;
266 : }
267 : };
268 :
269 : // Specialize DenseMapInfo.
270 : template <> struct DenseMapInfo<LocationSize> {
271 : static inline LocationSize getEmptyKey() {
272 : return LocationSize::mapEmpty();
273 : }
274 : static inline LocationSize getTombstoneKey() {
275 : return LocationSize::mapTombstone();
276 : }
277 : static unsigned getHashValue(const LocationSize &Val) {
278 155087706 : return DenseMapInfo<uint64_t>::getHashValue(Val.toRaw());
279 : }
280 : static bool isEqual(const LocationSize &LHS, const LocationSize &RHS) {
281 : return LHS == RHS;
282 : }
283 : };
284 :
285 : template <> struct DenseMapInfo<MemoryLocation> {
286 : static inline MemoryLocation getEmptyKey() {
287 : return MemoryLocation(DenseMapInfo<const Value *>::getEmptyKey(),
288 : DenseMapInfo<LocationSize>::getEmptyKey());
289 : }
290 : static inline MemoryLocation getTombstoneKey() {
291 : return MemoryLocation(DenseMapInfo<const Value *>::getTombstoneKey(),
292 : DenseMapInfo<LocationSize>::getTombstoneKey());
293 : }
294 155087706 : static unsigned getHashValue(const MemoryLocation &Val) {
295 310175412 : return DenseMapInfo<const Value *>::getHashValue(Val.Ptr) ^
296 : DenseMapInfo<LocationSize>::getHashValue(Val.Size) ^
297 155087706 : DenseMapInfo<AAMDNodes>::getHashValue(Val.AATags);
298 : }
299 : static bool isEqual(const MemoryLocation &LHS, const MemoryLocation &RHS) {
300 : return LHS == RHS;
301 : }
302 : };
303 : }
304 :
305 : #endif
|
