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