1 files changed, 307 insertions, 0 deletions
diff --git a/clang-r353983e/include/llvm/Analysis/MemoryLocation.h b/clang-r353983e/include/llvm/Analysis/MemoryLocation.h
new file mode 100644
index 00000000..7c26353e
--- /dev/null
+++ b/clang-r353983e/include/llvm/Analysis/MemoryLocation.h
@@ -0,0 +1,307 @@
+//===- MemoryLocation.h - Memory location descriptions ----------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+/// \file
+/// This file provides utility analysis objects describing memory locations.
+/// These are used both by the Alias Analysis infrastructure and more
+/// specialized memory analysis layers.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_MEMORYLOCATION_H
+#define LLVM_ANALYSIS_MEMORYLOCATION_H
+
+#include "llvm/ADT/DenseMapInfo.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Metadata.h"
+
+namespace llvm {
+
+class LoadInst;
+class StoreInst;
+class MemTransferInst;
+class MemIntrinsic;
+class AtomicMemTransferInst;
+class AtomicMemIntrinsic;
+class AnyMemTransferInst;
+class AnyMemIntrinsic;
+class TargetLibraryInfo;
+
+// Represents the size of a MemoryLocation. Logically, it's an
+// Optional<uint63_t> that also carries a bit to represent whether the integer
+// it contains, N, is 'precise'. Precise, in this context, means that we know
+// that the area of storage referenced by the given MemoryLocation must be
+// precisely N bytes. An imprecise value is formed as the union of two or more
+// precise values, and can conservatively represent all of the values unioned
+// into it. Importantly, imprecise values are an *upper-bound* on the size of a
+// MemoryLocation.
+//
+// Concretely, a precise MemoryLocation is (%p, 4) in
+// store i32 0, i32* %p
+//
+// Since we know that %p must be at least 4 bytes large at this point.
+// Otherwise, we have UB. An example of an imprecise MemoryLocation is (%p, 4)
+// at the memcpy in
+//
+//   %n = select i1 %foo, i64 1, i64 4
+//   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %p, i8* %baz, i64 %n, i32 1,
+//                                        i1 false)
+//
+// ...Since we'll copy *up to* 4 bytes into %p, but we can't guarantee that
+// we'll ever actually do so.
+//
+// If asked to represent a pathologically large value, this will degrade to
+// None.
+class LocationSize {
+  enum : uint64_t {
+    Unknown = ~uint64_t(0),
+    ImpreciseBit = uint64_t(1) << 63,
+    MapEmpty = Unknown - 1,
+    MapTombstone = Unknown - 2,
+
+    // The maximum value we can represent without falling back to 'unknown'.
+    MaxValue = (MapTombstone - 1) & ~ImpreciseBit,
+  };
+
+  uint64_t Value;
+
+  // Hack to support implicit construction. This should disappear when the
+  // public LocationSize ctor goes away.
+  enum DirectConstruction { Direct };
+
+  constexpr LocationSize(uint64_t Raw, DirectConstruction): Value(Raw) {}
+
+  static_assert(Unknown & ImpreciseBit, "Unknown is imprecise by definition.");
+public:
+  // FIXME: Migrate all users to construct via either `precise` or `upperBound`,
+  // to make it more obvious at the callsite the kind of size that they're
+  // providing.
+  //
+  // Since the overwhelming majority of users of this provide precise values,
+  // this assumes the provided value is precise.
+  constexpr LocationSize(uint64_t Raw)
+      : Value(Raw > MaxValue ? Unknown : Raw) {}
+
+  static LocationSize precise(uint64_t Value) { return LocationSize(Value); }
+
+  static LocationSize upperBound(uint64_t Value) {
+    // You can't go lower than 0, so give a precise result.
+    if (LLVM_UNLIKELY(Value == 0))
+      return precise(0);
+    if (LLVM_UNLIKELY(Value > MaxValue))
+      return unknown();
+    return LocationSize(Value | ImpreciseBit, Direct);
+  }
+
+  constexpr static LocationSize unknown() {
+    return LocationSize(Unknown, Direct);
+  }
+
+  // Sentinel values, generally used for maps.
+  constexpr static LocationSize mapTombstone() {
+    return LocationSize(MapTombstone, Direct);
+  }
+  constexpr static LocationSize mapEmpty() {
+    return LocationSize(MapEmpty, Direct);
+  }
+
+  // Returns a LocationSize that can correctly represent either `*this` or
+  // `Other`.
+  LocationSize unionWith(LocationSize Other) const {
+    if (Other == *this)
+      return *this;
+
+    if (!hasValue() || !Other.hasValue())
+      return unknown();
+
+    return upperBound(std::max(getValue(), Other.getValue()));
+  }
+
+  bool hasValue() const { return Value != Unknown; }
+  uint64_t getValue() const {
+    assert(hasValue() && "Getting value from an unknown LocationSize!");
+    return Value & ~ImpreciseBit;
+  }
+
+  // Returns whether or not this value is precise. Note that if a value is
+  // precise, it's guaranteed to not be `unknown()`.
+  bool isPrecise() const {
+    return (Value & ImpreciseBit) == 0;
+  }
+
+  // Convenience method to check if this LocationSize's value is 0.
+  bool isZero() const { return hasValue() && getValue() == 0; }
+
+  bool operator==(const LocationSize &Other) const {
+    return Value == Other.Value;
+  }
+
+  bool operator!=(const LocationSize &Other) const {
+    return !(*this == Other);
+  }
+
+  // Ordering operators are not provided, since it's unclear if there's only one
+  // reasonable way to compare:
+  // - values that don't exist against values that do, and
+  // - precise values to imprecise values
+
+  void print(raw_ostream &OS) const;
+
+  // Returns an opaque value that represents this LocationSize. Cannot be
+  // reliably converted back into a LocationSize.
+  uint64_t toRaw() const { return Value; }
+};
+
+inline raw_ostream &operator<<(raw_ostream &OS, LocationSize Size) {
+  Size.print(OS);
+  return OS;
+}
+
+/// Representation for a specific memory location.
+///
+/// This abstraction can be used to represent a specific location in memory.
+/// The goal of the location is to represent enough information to describe
+/// abstract aliasing, modification, and reference behaviors of whatever
+/// value(s) are stored in memory at the particular location.
+///
+/// The primary user of this interface is LLVM's Alias Analysis, but other
+/// memory analyses such as MemoryDependence can use it as well.
+class MemoryLocation {
+public:
+  /// UnknownSize - This is a special value which can be used with the
+  /// size arguments in alias queries to indicate that the caller does not
+  /// know the sizes of the potential memory references.
+  enum : uint64_t { UnknownSize = ~UINT64_C(0) };
+
+  /// The address of the start of the location.
+  const Value *Ptr;
+
+  /// The maximum size of the location, in address-units, or
+  /// UnknownSize if the size is not known.
+  ///
+  /// Note that an unknown size does not mean the pointer aliases the entire
+  /// virtual address space, because there are restrictions on stepping out of
+  /// one object and into another. See
+  /// http://llvm.org/docs/LangRef.html#pointeraliasing
+  LocationSize Size;
+
+  /// The metadata nodes which describes the aliasing of the location (each
+  /// member is null if that kind of information is unavailable).
+  AAMDNodes AATags;
+
+  /// Return a location with information about the memory reference by the given
+  /// instruction.
+  static MemoryLocation get(const LoadInst *LI);
+  static MemoryLocation get(const StoreInst *SI);
+  static MemoryLocation get(const VAArgInst *VI);
+  static MemoryLocation get(const AtomicCmpXchgInst *CXI);
+  static MemoryLocation get(const AtomicRMWInst *RMWI);
+  static MemoryLocation get(const Instruction *Inst) {
+    return *MemoryLocation::getOrNone(Inst);
+  }
+  static Optional<MemoryLocation> getOrNone(const Instruction *Inst) {
+    switch (Inst->getOpcode()) {
+    case Instruction::Load:
+      return get(cast<LoadInst>(Inst));
+    case Instruction::Store:
+      return get(cast<StoreInst>(Inst));
+    case Instruction::VAArg:
+      return get(cast<VAArgInst>(Inst));
+    case Instruction::AtomicCmpXchg:
+      return get(cast<AtomicCmpXchgInst>(Inst));
+    case Instruction::AtomicRMW:
+      return get(cast<AtomicRMWInst>(Inst));
+    default:
+      return None;
+    }
+  }
+
+  /// Return a location representing the source of a memory transfer.
+  static MemoryLocation getForSource(const MemTransferInst *MTI);
+  static MemoryLocation getForSource(const AtomicMemTransferInst *MTI);
+  static MemoryLocation getForSource(const AnyMemTransferInst *MTI);
+
+  /// Return a location representing the destination of a memory set or
+  /// transfer.
+  static MemoryLocation getForDest(const MemIntrinsic *MI);
+  static MemoryLocation getForDest(const AtomicMemIntrinsic *MI);
+  static MemoryLocation getForDest(const AnyMemIntrinsic *MI);
+
+  /// Return a location representing a particular argument of a call.
+  static MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx,
+                                       const TargetLibraryInfo *TLI);
+  static MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx,
+                                       const TargetLibraryInfo &TLI) {
+    return getForArgument(Call, ArgIdx, &TLI);
+  }
+
+  explicit MemoryLocation(const Value *Ptr = nullptr,
+                          LocationSize Size = LocationSize::unknown(),
+                          const AAMDNodes &AATags = AAMDNodes())
+      : Ptr(Ptr), Size(Size), AATags(AATags) {}
+
+  MemoryLocation getWithNewPtr(const Value *NewPtr) const {
+    MemoryLocation Copy(*this);
+    Copy.Ptr = NewPtr;
+    return Copy;
+  }
+
+  MemoryLocation getWithNewSize(LocationSize NewSize) const {
+    MemoryLocation Copy(*this);
+    Copy.Size = NewSize;
+    return Copy;
+  }
+
+  MemoryLocation getWithoutAATags() const {
+    MemoryLocation Copy(*this);
+    Copy.AATags = AAMDNodes();
+    return Copy;
+  }
+
+  bool operator==(const MemoryLocation &Other) const {
+    return Ptr == Other.Ptr && Size == Other.Size && AATags == Other.AATags;
+  }
+};
+
+// Specialize DenseMapInfo.
+template <> struct DenseMapInfo<LocationSize> {
+  static inline LocationSize getEmptyKey() {
+    return LocationSize::mapEmpty();
+  }
+  static inline LocationSize getTombstoneKey() {
+    return LocationSize::mapTombstone();
+  }
+  static unsigned getHashValue(const LocationSize &Val) {
+    return DenseMapInfo<uint64_t>::getHashValue(Val.toRaw());
+  }
+  static bool isEqual(const LocationSize &LHS, const LocationSize &RHS) {
+    return LHS == RHS;
+  }
+};
+
+template <> struct DenseMapInfo<MemoryLocation> {
+  static inline MemoryLocation getEmptyKey() {
+    return MemoryLocation(DenseMapInfo<const Value *>::getEmptyKey(),
+                          DenseMapInfo<LocationSize>::getEmptyKey());
+  }
+  static inline MemoryLocation getTombstoneKey() {
+    return MemoryLocation(DenseMapInfo<const Value *>::getTombstoneKey(),
+                          DenseMapInfo<LocationSize>::getTombstoneKey());
+  }
+  static unsigned getHashValue(const MemoryLocation &Val) {
+    return DenseMapInfo<const Value *>::getHashValue(Val.Ptr) ^
+           DenseMapInfo<LocationSize>::getHashValue(Val.Size) ^
+           DenseMapInfo<AAMDNodes>::getHashValue(Val.AATags);
+  }
+  static bool isEqual(const MemoryLocation &LHS, const MemoryLocation &RHS) {
+    return LHS == RHS;
+  }
+};
+}
+
+#endif