LCOV - code coverage report
Current view: top level - include/llvm/Analysis - MemoryLocation.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 29 41 70.7 %
Date: 2018-10-19 05:06:59 Functions: 3 8 37.5 %
Legend: Lines: hit not hit

          Line data    Source code
       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/Optional.h"
      20             : #include "llvm/ADT/DenseMapInfo.h"
      21             : #include "llvm/IR/CallSite.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     7449028 :       : 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        6641 :     if (LLVM_UNLIKELY(Value == 0))
      96             :       return precise(0);
      97        6641 :     if (LLVM_UNLIKELY(Value > MaxValue))
      98             :       return unknown();
      99        6641 :     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        6864 :   LocationSize unionWith(LocationSize Other) const {
     117        6864 :     if (Other == *this)
     118           0 :       return *this;
     119             : 
     120        6864 :     if (!hasValue() || !Other.hasValue())
     121         223 :       return unknown();
     122             : 
     123       13282 :     return upperBound(std::max(getValue(), Other.getValue()));
     124             :   }
     125             : 
     126           0 :   bool hasValue() const { return Value != Unknown; }
     127           0 :   uint64_t getValue() const {
     128             :     assert(hasValue() && "Getting value from an unknown LocationSize!");
     129    42899452 :     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           0 :   bool isPrecise() const {
     135    33663375 :     return (Value & ImpreciseBit) == 0;
     136             :   }
     137             : 
     138           0 :   bool operator==(const LocationSize &Other) const {
     139           0 :     return Value == Other.Value;
     140             :   }
     141             : 
     142             :   bool operator!=(const LocationSize &Other) const {
     143     1861743 :     return !(*this == Other);
     144             :   }
     145             : 
     146             :   // Ordering operators are not provided, since it's unclear if there's only one
     147             :   // reasonable way to compare:
     148             :   // - values that don't exist against values that do, and
     149             :   // - precise values to imprecise values
     150             : 
     151             :   void print(raw_ostream &OS) const;
     152             : 
     153             :   // Returns an opaque value that represents this LocationSize. Cannot be
     154             :   // reliably converted back into a LocationSize.
     155           0 :   uint64_t toRaw() const { return Value; }
     156             : };
     157             : 
     158             : inline raw_ostream &operator<<(raw_ostream &OS, LocationSize Size) {
     159         368 :   Size.print(OS);
     160             :   return OS;
     161             : }
     162             : 
     163             : /// Representation for a specific memory location.
     164             : ///
     165             : /// This abstraction can be used to represent a specific location in memory.
     166             : /// The goal of the location is to represent enough information to describe
     167             : /// abstract aliasing, modification, and reference behaviors of whatever
     168             : /// value(s) are stored in memory at the particular location.
     169             : ///
     170             : /// The primary user of this interface is LLVM's Alias Analysis, but other
     171             : /// memory analyses such as MemoryDependence can use it as well.
     172             : class MemoryLocation {
     173             : public:
     174             :   /// UnknownSize - This is a special value which can be used with the
     175             :   /// size arguments in alias queries to indicate that the caller does not
     176             :   /// know the sizes of the potential memory references.
     177             :   enum : uint64_t { UnknownSize = ~UINT64_C(0) };
     178             : 
     179             :   /// The address of the start of the location.
     180             :   const Value *Ptr;
     181             : 
     182             :   /// The maximum size of the location, in address-units, or
     183             :   /// UnknownSize if the size is not known.
     184             :   ///
     185             :   /// Note that an unknown size does not mean the pointer aliases the entire
     186             :   /// virtual address space, because there are restrictions on stepping out of
     187             :   /// one object and into another. See
     188             :   /// http://llvm.org/docs/LangRef.html#pointeraliasing
     189             :   LocationSize Size;
     190             : 
     191             :   /// The metadata nodes which describes the aliasing of the location (each
     192             :   /// member is null if that kind of information is unavailable).
     193             :   AAMDNodes AATags;
     194             : 
     195             :   /// Return a location with information about the memory reference by the given
     196             :   /// instruction.
     197             :   static MemoryLocation get(const LoadInst *LI);
     198             :   static MemoryLocation get(const StoreInst *SI);
     199             :   static MemoryLocation get(const VAArgInst *VI);
     200             :   static MemoryLocation get(const AtomicCmpXchgInst *CXI);
     201             :   static MemoryLocation get(const AtomicRMWInst *RMWI);
     202             :   static MemoryLocation get(const Instruction *Inst) {
     203     1652737 :     return *MemoryLocation::getOrNone(Inst);
     204             :   }
     205     1795408 :   static Optional<MemoryLocation> getOrNone(const Instruction *Inst) {
     206     1795408 :     switch (Inst->getOpcode()) {
     207             :     case Instruction::Load:
     208     1781461 :       return get(cast<LoadInst>(Inst));
     209             :     case Instruction::Store:
     210       13922 :       return get(cast<StoreInst>(Inst));
     211             :     case Instruction::VAArg:
     212           0 :       return get(cast<VAArgInst>(Inst));
     213             :     case Instruction::AtomicCmpXchg:
     214           0 :       return get(cast<AtomicCmpXchgInst>(Inst));
     215             :     case Instruction::AtomicRMW:
     216           0 :       return get(cast<AtomicRMWInst>(Inst));
     217             :     default:
     218             :       return None;
     219             :     }
     220             :   }
     221             : 
     222             :   /// Return a location representing the source of a memory transfer.
     223             :   static MemoryLocation getForSource(const MemTransferInst *MTI);
     224             :   static MemoryLocation getForSource(const AtomicMemTransferInst *MTI);
     225             :   static MemoryLocation getForSource(const AnyMemTransferInst *MTI);
     226             : 
     227             :   /// Return a location representing the destination of a memory set or
     228             :   /// transfer.
     229             :   static MemoryLocation getForDest(const MemIntrinsic *MI);
     230             :   static MemoryLocation getForDest(const AtomicMemIntrinsic *MI);
     231             :   static MemoryLocation getForDest(const AnyMemIntrinsic *MI);
     232             : 
     233             :   /// Return a location representing a particular argument of a call.
     234             :   static MemoryLocation getForArgument(ImmutableCallSite CS, unsigned ArgIdx,
     235             :                                        const TargetLibraryInfo *TLI);
     236             :   static MemoryLocation getForArgument(ImmutableCallSite CS, unsigned ArgIdx,
     237             :                                        const TargetLibraryInfo &TLI) {
     238     5310593 :     return getForArgument(CS, ArgIdx, &TLI);
     239             :   }
     240             : 
     241             :   explicit MemoryLocation(const Value *Ptr = nullptr,
     242             :                           LocationSize Size = LocationSize::unknown(),
     243             :                           const AAMDNodes &AATags = AAMDNodes())
     244    40176598 :       : Ptr(Ptr), Size(Size), AATags(AATags) {}
     245             : 
     246             :   MemoryLocation getWithNewPtr(const Value *NewPtr) const {
     247      226003 :     MemoryLocation Copy(*this);
     248      226003 :     Copy.Ptr = NewPtr;
     249             :     return Copy;
     250             :   }
     251             : 
     252             :   MemoryLocation getWithNewSize(LocationSize NewSize) const {
     253           0 :     MemoryLocation Copy(*this);
     254           0 :     Copy.Size = NewSize;
     255             :     return Copy;
     256             :   }
     257             : 
     258             :   MemoryLocation getWithoutAATags() const {
     259       11790 :     MemoryLocation Copy(*this);
     260       11790 :     Copy.AATags = AAMDNodes();
     261             :     return Copy;
     262             :   }
     263             : 
     264             :   bool operator==(const MemoryLocation &Other) const {
     265   267202364 :     return Ptr == Other.Ptr && Size == Other.Size && AATags == Other.AATags;
     266             :   }
     267             : };
     268             : 
     269             : // Specialize DenseMapInfo.
     270             : template <> struct DenseMapInfo<LocationSize> {
     271             :   static inline LocationSize getEmptyKey() {
     272             :     return LocationSize::mapEmpty();
     273             :   }
     274             :   static inline LocationSize getTombstoneKey() {
     275             :     return LocationSize::mapTombstone();
     276             :   }
     277             :   static unsigned getHashValue(const LocationSize &Val) {
     278   155072822 :     return DenseMapInfo<uint64_t>::getHashValue(Val.toRaw());
     279             :   }
     280             :   static bool isEqual(const LocationSize &LHS, const LocationSize &RHS) {
     281             :     return LHS == RHS;
     282             :   }
     283             : };
     284             : 
     285             : template <> struct DenseMapInfo<MemoryLocation> {
     286             :   static inline MemoryLocation getEmptyKey() {
     287             :     return MemoryLocation(DenseMapInfo<const Value *>::getEmptyKey(),
     288             :                           DenseMapInfo<LocationSize>::getEmptyKey());
     289             :   }
     290             :   static inline MemoryLocation getTombstoneKey() {
     291             :     return MemoryLocation(DenseMapInfo<const Value *>::getTombstoneKey(),
     292             :                           DenseMapInfo<LocationSize>::getTombstoneKey());
     293             :   }
     294   155072822 :   static unsigned getHashValue(const MemoryLocation &Val) {
     295   310145644 :     return DenseMapInfo<const Value *>::getHashValue(Val.Ptr) ^
     296             :            DenseMapInfo<LocationSize>::getHashValue(Val.Size) ^
     297   155072822 :            DenseMapInfo<AAMDNodes>::getHashValue(Val.AATags);
     298             :   }
     299             :   static bool isEqual(const MemoryLocation &LHS, const MemoryLocation &RHS) {
     300             :     return LHS == RHS;
     301             :   }
     302             : };
     303             : }
     304             : 
     305             : #endif

Generated by: LCOV version 1.13