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