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