[MemoryLocation] learn about ptr_provenance

[jeroen.dobbelaere]

Summary

Introduce a ptr_provenance member to MemoryLocation.

Note: in the full restrict patches, the ptr_provenance was tracked through the AAMDNodes. For this extraction of the feature, I feel that the MemoryLocation is a more logical place for it. (aka, the provenance is associated to a location, not to the Alias Analysis Metadata).

[jeroen.dobbelaere]

As shown in https://llvm-compile-time-tracker.com/index.php?config=NewPM-O3&stat=instructions&branch=dobbelaj-snps/perf/ptr_provenance-20210803-03, it seems that tracking the ptr_provenance in the MemoryLocation results in a pretty big extra overhead.

Tracking it in the AAMDNodes as we do in the full restrict patches (See https://llvm-compile-time-tracker.com/index.php?config=NewPM-O3&stat=instructions&branch=dobbelaj-snps/perf/full_restrict-20200918 ; change f3d32e5da7 'looking through noalias intrinsics') seems to have a less severe impact..

[jeroen.dobbelaere]

• Rebased
• use llvm::hash_combine instead of xor for combining the different elements. This avoids hash clashes when ptr == ptr_provenance

[jeroen.dobbelaere]

Rebase to 49cb4fef02e635bf304906232214166c7531d753

[jeroen.dobbelaere]

Rebased to ffe262a198a9f9030991df6d3ddd812e74fa3523

[asbirlea]

Could you add updated compile-time impact measurements after the latest rebase?

[jeroen.dobbelaere]

In D107352#3957589, @asbirlea wrote:

Could you add updated compile-time impact measurements after the latest rebase?

I have rebased the patches and let the compile-time tracker look at it. Results can be found here: https://llvm-compile-time-tracker.com/?config=NewPM-O3&stat=instructions%3Au&remote=dobbelaj-snps&branch=dobbelaj-snps/perf/ptr_provenance-20221207-02
Compared to the (old) run with the huge effect on the speed, there is still some effect visible. (1e51b7f42b)

[jeroen.dobbelaere]

In D107352#3986784, @jeroen.dobbelaere wrote:

In D107352#3957589, @asbirlea wrote:

Could you add updated compile-time impact measurements after the latest rebase?

I have rebased the patches and let the compile-time tracker look at it. Results can be found here: https://llvm-compile-time-tracker.com/?config=NewPM-O3&stat=instructions%3Au&remote=dobbelaj-snps&branch=dobbelaj-snps/perf/ptr_provenance-20221207-02
Compared to the (old) run with the huge effect on the speed, there is still some effect visible. (1e51b7f42b)

https://llvm-compile-time-tracker.com/?config=NewPM-O3&stat=instructions%3Au&remote=dobbelaj-snps&branch=dobbelaj-snps/perf/MemoryLocation-hashing-20221211-01 shows that most of the regression originates from using llvm::hash_combine instead of operator^ (fadd01d66c). A smaller part is added because of the memory usage and initialization of the extra pointer member. Including that extra pointer into the hash computation seems to have only minimal effect.

[jeroen.dobbelaere]

@asbirlea do you think this is acceptable ? We can also keep the ugly xor and use that result with llvm::hash_combine to bring in the new Val.ptrProvenance.

[jeroen.dobbelaere]

Rebased to ef545ef62a833152d8975ff16333b57cc41befcc (Jan 9, 2023)

[asbirlea]

In my opinion, this is fine.

[jeroen.dobbelaere]

Rebased to: 8c7cfa357280dd93d33b10bbba0fe33797e27d63 (Feb 14, 2023)

llvm/include/llvm/Analysis/MemoryLocation.h

 /// specialized memory analysis layers.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_MEMORYLOCATION_H
 #define LLVM_ANALYSIS_MEMORYLOCATION_H
 
 #include "llvm/ADT/DenseMapInfo.h"
+#include "llvm/ADT/Hashing.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/Support/TypeSize.h"
-
 #include <optional>
 
 namespace llvm {
 
 class CallBase;
 class Instruction;
 class LoadInst;
 class StoreInst;
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 provenance of the location. A nullptr or a ConstantPointerNull
+  /// indicate that the provenance can be from anywhere.
+  const Value *PtrProvenance = nullptr;
+
   /// 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;
 
-  void print(raw_ostream &OS) const { OS << *Ptr << " " << Size << "\n"; }
+  void print(raw_ostream &OS) const {
+    OS << *Ptr;
+    if (PtrProvenance)
+      OS << "(" << *PtrProvenance << ") ";
+    else
+      OS << "(nullptr) ";
+    OS << Size << "\n";
+  }
 
   /// 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);
public:
   }
 
   // Return the exact size if the exact size is known at compiletime,
   // otherwise return MemoryLocation::UnknownSize.
   static uint64_t getSizeOrUnknown(const TypeSize &T) {
     return T.isScalable() ? UnknownSize : T.getFixedValue();
   }
 
-  MemoryLocation() : Ptr(nullptr), Size(LocationSize::beforeOrAfterPointer()) {}
+  MemoryLocation()
+      : Ptr(nullptr), PtrProvenance(nullptr),
+        Size(LocationSize::beforeOrAfterPointer()) {}
 
   explicit MemoryLocation(const Value *Ptr, LocationSize Size,
                           const AAMDNodes &AATags = AAMDNodes())
-      : Ptr(Ptr), Size(Size), AATags(AATags) {}
+      : Ptr(Ptr), PtrProvenance(Ptr), Size(Size), AATags(AATags) {}
+
+  explicit MemoryLocation(const Value *Ptr, const Value *PtrProvenance,
+                          LocationSize Size,
+                          const AAMDNodes &AATags = AAMDNodes())
+      : Ptr(Ptr), PtrProvenance(PtrProvenance), Size(Size), AATags(AATags) {}
 
   MemoryLocation getWithNewPtr(const Value *NewPtr) const {
     MemoryLocation Copy(*this);
     Copy.Ptr = NewPtr;
     return Copy;
   }
 
+  MemoryLocation getWithNewPtrProvenance(const Value *NewPtrProvenance) const {
+    MemoryLocation Copy(*this);
+    Copy.PtrProvenance = NewPtrProvenance;
+    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;
+    return Ptr == Other.Ptr && PtrProvenance == Other.PtrProvenance &&
+           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<const Value *>::getEmptyKey(),
                           DenseMapInfo<LocationSize>::getEmptyKey());
   }
   static inline MemoryLocation getTombstoneKey() {
     return MemoryLocation(DenseMapInfo<const Value *>::getTombstoneKey(),
+                          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);
+    return DenseMapInfo<size_t>::getHashValue(static_cast<size_t>(
+        llvm::hash_combine(Val.Ptr, Val.PtrProvenance,
+                           DenseMapInfo<LocationSize>::getHashValue(Val.Size),
+                           DenseMapInfo<AAMDNodes>::getHashValue(Val.AATags))));
   }
   static bool isEqual(const MemoryLocation &LHS, const MemoryLocation &RHS) {
     return LHS == RHS;
   }
 };
 }
 
 #endif

llvm/lib/Analysis/MemoryLocation.cpp

void LocationSize::print(raw_ostream &OS) const {
   else
     OS << "upperBound(" << getValue() << ')';
 }
 
 MemoryLocation MemoryLocation::get(const LoadInst *LI) {
   const auto &DL = LI->getModule()->getDataLayout();
 
   return MemoryLocation(
-      LI->getPointerOperand(),
+      LI->getPointerOperand(), LI->getPtrProvenance(),
       LocationSize::precise(DL.getTypeStoreSize(LI->getType())),
       LI->getAAMetadata());
 }
 
 MemoryLocation MemoryLocation::get(const StoreInst *SI) {
   const auto &DL = SI->getModule()->getDataLayout();
 
-  return MemoryLocation(SI->getPointerOperand(),
+  return MemoryLocation(SI->getPointerOperand(), SI->getPtrProvenance(),
                         LocationSize::precise(DL.getTypeStoreSize(
                             SI->getValueOperand()->getType())),
                         SI->getAAMetadata());
 }
 
 MemoryLocation MemoryLocation::get(const VAArgInst *VI) {
   return MemoryLocation(VI->getPointerOperand(),
                         LocationSize::afterPointer(), VI->getAAMetadata());