include/llvm/Analysis/MemoryLocation.h

   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   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       : Value(Raw > MaxValue ? Unknown : Raw) {}
  89
  90   static LocationSize precise(uint64_t Value) { return LocationSize(Value); }
  91
  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
 101   constexpr static LocationSize unknown() {
 102     return LocationSize(Unknown, Direct);
 103   }
 104
 105   // Sentinel values, generally used for maps.
 106   constexpr static LocationSize mapTombstone() {
 107     return LocationSize(MapTombstone, Direct);
 108   }
 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`.
 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
 125   bool hasValue() const { return Value != Unknown; }
 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()`.
 133   bool isPrecise() const {
 134     return (Value & ImpreciseBit) == 0;
 135   }
 136
 137   // Convenience method to check if this LocationSize's value is 0.
 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.
 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);
 204   static MemoryLocation get(const Instruction *Inst) {
 205     return *MemoryLocation::getOrNone(Inst);
 206   }
 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);
 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())
 246       : Ptr(Ptr), Size(Size), AATags(AATags) {}
 247
 248   MemoryLocation getWithNewPtr(const Value *NewPtr) const {
 249     MemoryLocation Copy(*this);
 250     Copy.Ptr = NewPtr;
 251     return Copy;
 252   }
 253
 254   MemoryLocation getWithNewSize(LocationSize NewSize) const {
 255     MemoryLocation Copy(*this);
 256     Copy.Size = NewSize;
 257     return Copy;
 258   }
 259
 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