/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Analysis/MemoryLocation.h
Line | Count | Source (jump to first uncovered line) |
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 | 2.18G | 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 | 73.5M | : Value(Raw > MaxValue ? Unknown : Raw) {} |
89 | | |
90 | 64.4M | static LocationSize precise(uint64_t Value) { return LocationSize(Value); } |
91 | | |
92 | 13.5k | static LocationSize upperBound(uint64_t Value) { |
93 | 13.5k | // You can't go lower than 0, so give a precise result. |
94 | 13.5k | if (LLVM_UNLIKELY(Value == 0)) |
95 | 13.5k | return precise(0)0 ; |
96 | 13.5k | if (LLVM_UNLIKELY(Value > MaxValue)) |
97 | 13.5k | return unknown()0 ; |
98 | 13.5k | return LocationSize(Value | ImpreciseBit, Direct); |
99 | 13.5k | } |
100 | | |
101 | 283M | constexpr static LocationSize unknown() { |
102 | 283M | return LocationSize(Unknown, Direct); |
103 | 283M | } |
104 | | |
105 | | // Sentinel values, generally used for maps. |
106 | 766M | constexpr static LocationSize mapTombstone() { |
107 | 766M | return LocationSize(MapTombstone, Direct); |
108 | 766M | } |
109 | 1.13G | constexpr static LocationSize mapEmpty() { |
110 | 1.13G | return LocationSize(MapEmpty, Direct); |
111 | 1.13G | } |
112 | | |
113 | | // Returns a LocationSize that can correctly represent either `*this` or |
114 | | // `Other`. |
115 | 14.4k | LocationSize unionWith(LocationSize Other) const { |
116 | 14.4k | if (Other == *this) |
117 | 0 | return *this; |
118 | 14.4k | |
119 | 14.4k | if (!hasValue() || !Other.hasValue()13.8k ) |
120 | 896 | return unknown(); |
121 | 13.5k | |
122 | 13.5k | return upperBound(std::max(getValue(), Other.getValue())); |
123 | 13.5k | } |
124 | | |
125 | 174M | bool hasValue() const { return Value != Unknown; } |
126 | 274M | uint64_t getValue() const { |
127 | 274M | assert(hasValue() && "Getting value from an unknown LocationSize!"); |
128 | 274M | return Value & ~ImpreciseBit; |
129 | 274M | } |
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 | 125M | bool isPrecise() const { |
134 | 125M | return (Value & ImpreciseBit) == 0; |
135 | 125M | } |
136 | | |
137 | | // Convenience method to check if this LocationSize's value is 0. |
138 | 174M | bool isZero() const { return hasValue() && getValue() == 0104M ; } |
139 | | |
140 | 2.80G | bool operator==(const LocationSize &Other) const { |
141 | 2.80G | return Value == Other.Value; |
142 | 2.80G | } |
143 | | |
144 | 36.5M | bool operator!=(const LocationSize &Other) const { |
145 | 36.5M | return !(*this == Other); |
146 | 36.5M | } |
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 | 524M | uint64_t toRaw() const { return Value; } |
158 | | }; |
159 | | |
160 | 368 | inline raw_ostream &operator<<(raw_ostream &OS, LocationSize Size) { |
161 | 368 | Size.print(OS); |
162 | 368 | return OS; |
163 | 368 | } |
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. |
174 | | class MemoryLocation { |
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 |
191 | | LocationSize Size; |
192 | | |
193 | | /// The metadata nodes which describes the aliasing of the location (each |
194 | | /// member is null if that kind of information is unavailable). |
195 | | AAMDNodes AATags; |
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 | 6.22M | static MemoryLocation get(const Instruction *Inst) { |
205 | 6.22M | return *MemoryLocation::getOrNone(Inst); |
206 | 6.22M | } |
207 | 6.87M | static Optional<MemoryLocation> getOrNone(const Instruction *Inst) { |
208 | 6.87M | switch (Inst->getOpcode()) { |
209 | 6.87M | case Instruction::Load: |
210 | 6.82M | return get(cast<LoadInst>(Inst)); |
211 | 6.87M | case Instruction::Store: |
212 | 43.8k | return get(cast<StoreInst>(Inst)); |
213 | 6.87M | case Instruction::VAArg: |
214 | 18 | return get(cast<VAArgInst>(Inst)); |
215 | 6.87M | case Instruction::AtomicCmpXchg: |
216 | 0 | return get(cast<AtomicCmpXchgInst>(Inst)); |
217 | 6.87M | case Instruction::AtomicRMW: |
218 | 4.17k | return get(cast<AtomicRMWInst>(Inst)); |
219 | 6.87M | default: |
220 | 89 | return None; |
221 | 6.87M | } |
222 | 6.87M | } |
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 | 1.47M | const TargetLibraryInfo &TLI) { |
240 | 1.47M | return getForArgument(Call, ArgIdx, &TLI); |
241 | 1.47M | } |
242 | | |
243 | | explicit MemoryLocation(const Value *Ptr = nullptr, |
244 | | LocationSize Size = LocationSize::unknown(), |
245 | | const AAMDNodes &AATags = AAMDNodes()) |
246 | 2.22G | : Ptr(Ptr), Size(Size), AATags(AATags) {} |
247 | | |
248 | 1.62M | MemoryLocation getWithNewPtr(const Value *NewPtr) const { |
249 | 1.62M | MemoryLocation Copy(*this); |
250 | 1.62M | Copy.Ptr = NewPtr; |
251 | 1.62M | return Copy; |
252 | 1.62M | } |
253 | | |
254 | 0 | MemoryLocation getWithNewSize(LocationSize NewSize) const { |
255 | 0 | MemoryLocation Copy(*this); |
256 | 0 | Copy.Size = NewSize; |
257 | 0 | return Copy; |
258 | 0 | } |
259 | | |
260 | 12.4k | MemoryLocation getWithoutAATags() const { |
261 | 12.4k | MemoryLocation Copy(*this); |
262 | 12.4k | Copy.AATags = AAMDNodes(); |
263 | 12.4k | return Copy; |
264 | 12.4k | } |
265 | | |
266 | 3.10G | bool operator==(const MemoryLocation &Other) const { |
267 | 3.10G | return Ptr == Other.Ptr && Size == Other.Size2.67G && AATags == Other.AATags2.66G ; |
268 | 3.10G | } |
269 | | }; |
270 | | |
271 | | // Specialize DenseMapInfo. |
272 | | template <> struct DenseMapInfo<LocationSize> { |
273 | 1.12G | static inline LocationSize getEmptyKey() { |
274 | 1.12G | return LocationSize::mapEmpty(); |
275 | 1.12G | } |
276 | 766M | static inline LocationSize getTombstoneKey() { |
277 | 766M | return LocationSize::mapTombstone(); |
278 | 766M | } |
279 | 524M | static unsigned getHashValue(const LocationSize &Val) { |
280 | 524M | return DenseMapInfo<uint64_t>::getHashValue(Val.toRaw()); |
281 | 524M | } |
282 | 0 | static bool isEqual(const LocationSize &LHS, const LocationSize &RHS) { |
283 | 0 | return LHS == RHS; |
284 | 0 | } |
285 | | }; |
286 | | |
287 | | template <> struct DenseMapInfo<MemoryLocation> { |
288 | 1.12G | static inline MemoryLocation getEmptyKey() { |
289 | 1.12G | return MemoryLocation(DenseMapInfo<const Value *>::getEmptyKey(), |
290 | 1.12G | DenseMapInfo<LocationSize>::getEmptyKey()); |
291 | 1.12G | } |
292 | 766M | static inline MemoryLocation getTombstoneKey() { |
293 | 766M | return MemoryLocation(DenseMapInfo<const Value *>::getTombstoneKey(), |
294 | 766M | DenseMapInfo<LocationSize>::getTombstoneKey()); |
295 | 766M | } |
296 | 524M | static unsigned getHashValue(const MemoryLocation &Val) { |
297 | 524M | return DenseMapInfo<const Value *>::getHashValue(Val.Ptr) ^ |
298 | 524M | DenseMapInfo<LocationSize>::getHashValue(Val.Size) ^ |
299 | 524M | DenseMapInfo<AAMDNodes>::getHashValue(Val.AATags); |
300 | 524M | } |
301 | 3.05G | static bool isEqual(const MemoryLocation &LHS, const MemoryLocation &RHS) { |
302 | 3.05G | return LHS == RHS; |
303 | 3.05G | } |
304 | | }; |
305 | | } |
306 | | |
307 | | #endif |