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 LocationSize(uint64_t Raw,DirectConstruction)77 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. LocationSize(uint64_t Raw)87 constexpr LocationSize(uint64_t Raw) 88 : Value(Raw > MaxValue ? Unknown : Raw) {} 89 precise(uint64_t Value)90 static LocationSize precise(uint64_t Value) { return LocationSize(Value); } 91 upperBound(uint64_t Value)92 static LocationSize upperBound(uint64_t Value) { 93 // You can't go lower than 0, so give a precise result. 94 if (LLVM_UNLIKELY(Value == 0)) 95 return precise(0); 96 if (LLVM_UNLIKELY(Value > MaxValue)) 97 return unknown(); 98 return LocationSize(Value | ImpreciseBit, Direct); 99 } 100 unknown()101 constexpr static LocationSize unknown() { 102 return LocationSize(Unknown, Direct); 103 } 104 105 // Sentinel values, generally used for maps. mapTombstone()106 constexpr static LocationSize mapTombstone() { 107 return LocationSize(MapTombstone, Direct); 108 } mapEmpty()109 constexpr static LocationSize mapEmpty() { 110 return LocationSize(MapEmpty, Direct); 111 } 112 113 // Returns a LocationSize that can correctly represent either `*this` or 114 // `Other`. unionWith(LocationSize Other)115 LocationSize unionWith(LocationSize Other) const { 116 if (Other == *this) 117 return *this; 118 119 if (!hasValue() || !Other.hasValue()) 120 return unknown(); 121 122 return upperBound(std::max(getValue(), Other.getValue())); 123 } 124 hasValue()125 bool hasValue() const { return Value != Unknown; } getValue()126 uint64_t getValue() const { 127 assert(hasValue() && "Getting value from an unknown LocationSize!"); 128 return Value & ~ImpreciseBit; 129 } 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()`. isPrecise()133 bool isPrecise() const { 134 return (Value & ImpreciseBit) == 0; 135 } 136 137 // Convenience method to check if this LocationSize's value is 0. isZero()138 bool isZero() const { return hasValue() && getValue() == 0; } 139 140 bool operator==(const LocationSize &Other) const { 141 return Value == Other.Value; 142 } 143 144 bool operator!=(const LocationSize &Other) const { 145 return !(*this == Other); 146 } 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. toRaw()157 uint64_t toRaw() const { return Value; } 158 }; 159 160 inline raw_ostream &operator<<(raw_ostream &OS, LocationSize Size) { 161 Size.print(OS); 162 return OS; 163 } 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); get(const Instruction * Inst)204 static MemoryLocation get(const Instruction *Inst) { 205 return *MemoryLocation::getOrNone(Inst); 206 } getOrNone(const Instruction * Inst)207 static Optional<MemoryLocation> getOrNone(const Instruction *Inst) { 208 switch (Inst->getOpcode()) { 209 case Instruction::Load: 210 return get(cast<LoadInst>(Inst)); 211 case Instruction::Store: 212 return get(cast<StoreInst>(Inst)); 213 case Instruction::VAArg: 214 return get(cast<VAArgInst>(Inst)); 215 case Instruction::AtomicCmpXchg: 216 return get(cast<AtomicCmpXchgInst>(Inst)); 217 case Instruction::AtomicRMW: 218 return get(cast<AtomicRMWInst>(Inst)); 219 default: 220 return None; 221 } 222 } 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); getForArgument(const CallBase * Call,unsigned ArgIdx,const TargetLibraryInfo & TLI)238 static MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx, 239 const TargetLibraryInfo &TLI) { 240 return getForArgument(Call, ArgIdx, &TLI); 241 } 242 243 explicit MemoryLocation(const Value *Ptr = nullptr, 244 LocationSize Size = LocationSize::unknown(), 245 const AAMDNodes &AATags = AAMDNodes()) Ptr(Ptr)246 : Ptr(Ptr), Size(Size), AATags(AATags) {} 247 getWithNewPtr(const Value * NewPtr)248 MemoryLocation getWithNewPtr(const Value *NewPtr) const { 249 MemoryLocation Copy(*this); 250 Copy.Ptr = NewPtr; 251 return Copy; 252 } 253 getWithNewSize(LocationSize NewSize)254 MemoryLocation getWithNewSize(LocationSize NewSize) const { 255 MemoryLocation Copy(*this); 256 Copy.Size = NewSize; 257 return Copy; 258 } 259 getWithoutAATags()260 MemoryLocation getWithoutAATags() const { 261 MemoryLocation Copy(*this); 262 Copy.AATags = AAMDNodes(); 263 return Copy; 264 } 265 266 bool operator==(const MemoryLocation &Other) const { 267 return Ptr == Other.Ptr && Size == Other.Size && AATags == Other.AATags; 268 } 269 }; 270 271 // Specialize DenseMapInfo. 272 template <> struct DenseMapInfo<LocationSize> { 273 static inline LocationSize getEmptyKey() { 274 return LocationSize::mapEmpty(); 275 } 276 static inline LocationSize getTombstoneKey() { 277 return LocationSize::mapTombstone(); 278 } 279 static unsigned getHashValue(const LocationSize &Val) { 280 return DenseMapInfo<uint64_t>::getHashValue(Val.toRaw()); 281 } 282 static bool isEqual(const LocationSize &LHS, const LocationSize &RHS) { 283 return LHS == RHS; 284 } 285 }; 286 287 template <> struct DenseMapInfo<MemoryLocation> { 288 static inline MemoryLocation getEmptyKey() { 289 return MemoryLocation(DenseMapInfo<const Value *>::getEmptyKey(), 290 DenseMapInfo<LocationSize>::getEmptyKey()); 291 } 292 static inline MemoryLocation getTombstoneKey() { 293 return MemoryLocation(DenseMapInfo<const Value *>::getTombstoneKey(), 294 DenseMapInfo<LocationSize>::getTombstoneKey()); 295 } 296 static unsigned getHashValue(const MemoryLocation &Val) { 297 return DenseMapInfo<const Value *>::getHashValue(Val.Ptr) ^ 298 DenseMapInfo<LocationSize>::getHashValue(Val.Size) ^ 299 DenseMapInfo<AAMDNodes>::getHashValue(Val.AATags); 300 } 301 static bool isEqual(const MemoryLocation &LHS, const MemoryLocation &RHS) { 302 return LHS == RHS; 303 } 304 }; 305 } 306 307 #endif 308