contrib/llvm/include/llvm/Analysis/MemoryLocation.h

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