1 files changed, 241 insertions, 55 deletions

diff --git a/contrib/llvm-project/llvm/lib/IR/StructuralHash.cpp b/contrib/llvm-project/llvm/lib/IR/StructuralHash.cpp
index b6de1ed725d7..1c617c100c7d 100644
--- a/contrib/llvm-project/llvm/lib/IR/StructuralHash.cpp
+++ b/contrib/llvm-project/llvm/lib/IR/StructuralHash.cpp
@@ -7,7 +7,6 @@
 //===----------------------------------------------------------------------===//
 
 #include "llvm/IR/StructuralHash.h"
-#include "llvm/ADT/Hashing.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/InstrTypes.h"
@@ -24,61 +23,220 @@ namespace {
 // by the MergeFunctions pass.
 
 class StructuralHashImpl {
-  uint64_t Hash;
+  stable_hash Hash = 4;
 
-  void hash(uint64_t V) { Hash = hashing::detail::hash_16_bytes(Hash, V); }
+  bool DetailedHash;
 
-  // This will produce different values on 32-bit and 64-bit systens as
-  // hash_combine returns a size_t. However, this is only used for
-  // detailed hashing which, in-tree, only needs to distinguish between
-  // differences in functions.
-  template <typename T> void hashArbitaryType(const T &V) {
-    hash(hash_combine(V));
-  }
+  // This random value acts as a block header, as otherwise the partition of
+  // opcodes into BBs wouldn't affect the hash, only the order of the opcodes.
+  static constexpr stable_hash BlockHeaderHash = 45798;
+  static constexpr stable_hash FunctionHeaderHash = 0x62642d6b6b2d6b72;
+  static constexpr stable_hash GlobalHeaderHash = 23456;
+
+  /// IgnoreOp is a function that returns true if the operand should be ignored.
+  IgnoreOperandFunc IgnoreOp = nullptr;
+  /// A mapping from instruction indices to instruction pointers.
+  /// The index represents the position of an instruction based on the order in
+  /// which it is first encountered.
+  std::unique_ptr<IndexInstrMap> IndexInstruction = nullptr;
+  /// A mapping from pairs of instruction indices and operand indices
+  /// to the hashes of the operands.
+  std::unique_ptr<IndexOperandHashMapType> IndexOperandHashMap = nullptr;
 
-  void hashType(Type *ValueType) {
-    hash(ValueType->getTypeID());
+  /// Assign a unique ID to each Value in the order they are first seen.
+  DenseMap<const Value *, int> ValueToId;
+
+  static stable_hash hashType(Type *ValueType) {
+    SmallVector<stable_hash> Hashes;
+    Hashes.emplace_back(ValueType->getTypeID());
     if (ValueType->isIntegerTy())
-      hash(ValueType->getIntegerBitWidth());
+      Hashes.emplace_back(ValueType->getIntegerBitWidth());
+    return stable_hash_combine(Hashes);
   }
 
 public:
-  StructuralHashImpl() : Hash(4) {}
+  StructuralHashImpl() = delete;
+  explicit StructuralHashImpl(bool DetailedHash,
+                              IgnoreOperandFunc IgnoreOp = nullptr)
+      : DetailedHash(DetailedHash), IgnoreOp(IgnoreOp) {
+    if (IgnoreOp) {
+      IndexInstruction = std::make_unique<IndexInstrMap>();
+      IndexOperandHashMap = std::make_unique<IndexOperandHashMapType>();
+    }
+  }
+
+  static stable_hash hashAPInt(const APInt &I) {
+    SmallVector<stable_hash> Hashes;
+    Hashes.emplace_back(I.getBitWidth());
+    auto RawVals = ArrayRef<uint64_t>(I.getRawData(), I.getNumWords());
+    Hashes.append(RawVals.begin(), RawVals.end());
+    return stable_hash_combine(Hashes);
+  }
+
+  static stable_hash hashAPFloat(const APFloat &F) {
+    return hashAPInt(F.bitcastToAPInt());
+  }
+
+  static stable_hash hashGlobalVariable(const GlobalVariable &GVar) {
+    if (!GVar.hasInitializer())
+      return hashGlobalValue(&GVar);
+
+    // Hash the contents of a string.
+    if (GVar.getName().starts_with(".str")) {
+      auto *C = GVar.getInitializer();
+      if (const auto *Seq = dyn_cast<ConstantDataSequential>(C))
+        if (Seq->isString())
+          return stable_hash_name(Seq->getAsString());
+    }
+
+    // Hash structural contents of Objective-C metadata in specific sections.
+    // This can be extended to other metadata if needed.
+    static constexpr const char *SectionNames[] = {
+        "__cfstring",      "__cstring",      "__objc_classrefs",
+        "__objc_methname", "__objc_selrefs",
+    };
+    if (GVar.hasSection()) {
+      StringRef SectionName = GVar.getSection();
+      for (const char *Name : SectionNames)
+        if (SectionName.contains(Name))
+          return hashConstant(GVar.getInitializer());
+    }
 
-  void updateOperand(Value *Operand) {
-    hashType(Operand->getType());
+    return hashGlobalValue(&GVar);
+  }
+
+  static stable_hash hashGlobalValue(const GlobalValue *GV) {
+    if (!GV->hasName())
+      return 0;
+    return stable_hash_name(GV->getName());
+  }
+
+  // Compute a hash for a Constant. This function is logically similar to
+  // FunctionComparator::cmpConstants() in FunctionComparator.cpp, but here
+  // we're interested in computing a hash rather than comparing two Constants.
+  // Some of the logic is simplified, e.g, we don't expand GEPOperator.
+  static stable_hash hashConstant(const Constant *C) {
+    SmallVector<stable_hash> Hashes;
+
+    Type *Ty = C->getType();
+    Hashes.emplace_back(hashType(Ty));
+
+    if (C->isNullValue()) {
+      Hashes.emplace_back(static_cast<stable_hash>('N'));
+      return stable_hash_combine(Hashes);
+    }
+
+    if (auto *GVar = dyn_cast<GlobalVariable>(C)) {
+      Hashes.emplace_back(hashGlobalVariable(*GVar));
+      return stable_hash_combine(Hashes);
+    }
+
+    if (auto *G = dyn_cast<GlobalValue>(C)) {
+      Hashes.emplace_back(hashGlobalValue(G));
+      return stable_hash_combine(Hashes);
+    }
+
+    if (const auto *Seq = dyn_cast<ConstantDataSequential>(C)) {
+      if (Seq->isString()) {
+        Hashes.emplace_back(stable_hash_name(Seq->getAsString()));
+        return stable_hash_combine(Hashes);
+      }
+    }
 
-    // The cases enumerated below are not exhaustive and are only aimed to
-    // get decent coverage over the function.
-    if (ConstantInt *ConstInt = dyn_cast<ConstantInt>(Operand)) {
-      hashArbitaryType(ConstInt->getValue());
-    } else if (ConstantFP *ConstFP = dyn_cast<ConstantFP>(Operand)) {
-      hashArbitaryType(ConstFP->getValue());
-    } else if (Argument *Arg = dyn_cast<Argument>(Operand)) {
-      hash(Arg->getArgNo());
-    } else if (Function *Func = dyn_cast<Function>(Operand)) {
-      // Hashing the name will be deterministic as LLVM's hashing infrastructure
-      // has explicit support for hashing strings and will not simply hash
-      // the pointer.
-      hashArbitaryType(Func->getName());
+    switch (C->getValueID()) {
+    case Value::ConstantIntVal: {
+      const APInt &Int = cast<ConstantInt>(C)->getValue();
+      Hashes.emplace_back(hashAPInt(Int));
+      return stable_hash_combine(Hashes);
     }
+    case Value::ConstantFPVal: {
+      const APFloat &APF = cast<ConstantFP>(C)->getValueAPF();
+      Hashes.emplace_back(hashAPFloat(APF));
+      return stable_hash_combine(Hashes);
+    }
+    case Value::ConstantArrayVal:
+    case Value::ConstantStructVal:
+    case Value::ConstantVectorVal:
+    case Value::ConstantExprVal: {
+      for (const auto &Op : C->operands()) {
+        auto H = hashConstant(cast<Constant>(Op));
+        Hashes.emplace_back(H);
+      }
+      return stable_hash_combine(Hashes);
+    }
+    case Value::BlockAddressVal: {
+      const BlockAddress *BA = cast<BlockAddress>(C);
+      auto H = hashGlobalValue(BA->getFunction());
+      Hashes.emplace_back(H);
+      return stable_hash_combine(Hashes);
+    }
+    case Value::DSOLocalEquivalentVal: {
+      const auto *Equiv = cast<DSOLocalEquivalent>(C);
+      auto H = hashGlobalValue(Equiv->getGlobalValue());
+      Hashes.emplace_back(H);
+      return stable_hash_combine(Hashes);
+    }
+    default:
+      // Skip other types of constants for simplicity.
+      return stable_hash_combine(Hashes);
+    }
+  }
+
+  stable_hash hashValue(Value *V) {
+    // Check constant and return its hash.
+    Constant *C = dyn_cast<Constant>(V);
+    if (C)
+      return hashConstant(C);
+
+    // Hash argument number.
+    SmallVector<stable_hash> Hashes;
+    if (Argument *Arg = dyn_cast<Argument>(V))
+      Hashes.emplace_back(Arg->getArgNo());
+
+    // Get an index (an insertion order) for the non-constant value.
+    auto [It, WasInserted] = ValueToId.try_emplace(V, ValueToId.size());
+    Hashes.emplace_back(It->second);
+
+    return stable_hash_combine(Hashes);
   }
 
-  void updateInstruction(const Instruction &Inst, bool DetailedHash) {
-    hash(Inst.getOpcode());
+  stable_hash hashOperand(Value *Operand) {
+    SmallVector<stable_hash> Hashes;
+    Hashes.emplace_back(hashType(Operand->getType()));
+    Hashes.emplace_back(hashValue(Operand));
+    return stable_hash_combine(Hashes);
+  }
+
+  stable_hash hashInstruction(const Instruction &Inst) {
+    SmallVector<stable_hash> Hashes;
+    Hashes.emplace_back(Inst.getOpcode());
 
     if (!DetailedHash)
-      return;
+      return stable_hash_combine(Hashes);
 
-    hashType(Inst.getType());
+    Hashes.emplace_back(hashType(Inst.getType()));
 
     // Handle additional properties of specific instructions that cause
     // semantic differences in the IR.
     if (const auto *ComparisonInstruction = dyn_cast<CmpInst>(&Inst))
-      hash(ComparisonInstruction->getPredicate());
+      Hashes.emplace_back(ComparisonInstruction->getPredicate());
 
-    for (const auto &Op : Inst.operands())
-      updateOperand(Op);
+    unsigned InstIdx = 0;
+    if (IndexInstruction) {
+      InstIdx = IndexInstruction->size();
+      IndexInstruction->try_emplace(InstIdx, const_cast<Instruction *>(&Inst));
+    }
+
+    for (const auto [OpndIdx, Op] : enumerate(Inst.operands())) {
+      auto OpndHash = hashOperand(Op);
+      if (IgnoreOp && IgnoreOp(&Inst, OpndIdx)) {
+        assert(IndexOperandHashMap);
+        IndexOperandHashMap->try_emplace({InstIdx, OpndIdx}, OpndHash);
+      } else
+        Hashes.emplace_back(OpndHash);
+    }
+
+    return stable_hash_combine(Hashes);
   }
 
   // A function hash is calculated by considering only the number of arguments
@@ -97,15 +255,17 @@ public:
   // expensive checks for pass modification status). When modifying this
   // function, most changes should be gated behind an option and enabled
   // selectively.
-  void update(const Function &F, bool DetailedHash) {
+  void update(const Function &F) {
     // Declarations don't affect analyses.
     if (F.isDeclaration())
       return;
 
-    hash(0x62642d6b6b2d6b72); // Function header
+    SmallVector<stable_hash> Hashes;
+    Hashes.emplace_back(Hash);
+    Hashes.emplace_back(FunctionHeaderHash);
 
-    hash(F.isVarArg());
-    hash(F.arg_size());
+    Hashes.emplace_back(F.isVarArg());
+    Hashes.emplace_back(F.arg_size());
 
     SmallVector<const BasicBlock *, 8> BBs;
     SmallPtrSet<const BasicBlock *, 16> VisitedBBs;
@@ -118,17 +278,17 @@ public:
     while (!BBs.empty()) {
       const BasicBlock *BB = BBs.pop_back_val();
 
-      // This random value acts as a block header, as otherwise the partition of
-      // opcodes into BBs wouldn't affect the hash, only the order of the
-      // opcodes
-      hash(45798);
+      Hashes.emplace_back(BlockHeaderHash);
       for (auto &Inst : *BB)
-        updateInstruction(Inst, DetailedHash);
+        Hashes.emplace_back(hashInstruction(Inst));
 
       for (const BasicBlock *Succ : successors(BB))
         if (VisitedBBs.insert(Succ).second)
           BBs.push_back(Succ);
     }
+
+    // Update the combined hash in place.
+    Hash = stable_hash_combine(Hashes);
   }
 
   void update(const GlobalVariable &GV) {
@@ -137,30 +297,56 @@ public:
     // we ignore anything with the `.llvm` prefix
     if (GV.isDeclaration() || GV.getName().starts_with("llvm."))
       return;
-    hash(23456); // Global header
-    hash(GV.getValueType()->getTypeID());
+    SmallVector<stable_hash> Hashes;
+    Hashes.emplace_back(Hash);
+    Hashes.emplace_back(GlobalHeaderHash);
+    Hashes.emplace_back(GV.getValueType()->getTypeID());
+
+    // Update the combined hash in place.
+    Hash = stable_hash_combine(Hashes);
   }
 
-  void update(const Module &M, bool DetailedHash) {
+  void update(const Module &M) {
     for (const GlobalVariable &GV : M.globals())
       update(GV);
     for (const Function &F : M)
-      update(F, DetailedHash);
+      update(F);
   }
 
   uint64_t getHash() const { return Hash; }
+
+  std::unique_ptr<IndexInstrMap> getIndexInstrMap() {
+    return std::move(IndexInstruction);
+  }
+
+  std::unique_ptr<IndexOperandHashMapType> getIndexPairOpndHashMap() {
+    return std::move(IndexOperandHashMap);
+  }
 };
 
 } // namespace
 
-IRHash llvm::StructuralHash(const Function &F, bool DetailedHash) {
-  StructuralHashImpl H;
-  H.update(F, DetailedHash);
+stable_hash llvm::StructuralHash(const Function &F, bool DetailedHash) {
+  StructuralHashImpl H(DetailedHash);
+  H.update(F);
   return H.getHash();
 }
 
-IRHash llvm::StructuralHash(const Module &M, bool DetailedHash) {
-  StructuralHashImpl H;
-  H.update(M, DetailedHash);
+stable_hash llvm::StructuralHash(const GlobalVariable &GVar) {
+  return StructuralHashImpl::hashGlobalVariable(GVar);
+}
+
+stable_hash llvm::StructuralHash(const Module &M, bool DetailedHash) {
+  StructuralHashImpl H(DetailedHash);
+  H.update(M);
   return H.getHash();
 }
+
+FunctionHashInfo
+llvm::StructuralHashWithDifferences(const Function &F,
+                                    IgnoreOperandFunc IgnoreOp) {
+  StructuralHashImpl H(/*DetailedHash=*/true, IgnoreOp);
+  H.update(F);
+  return FunctionHashInfo(H.getHash(), H.getIndexInstrMap(),
+                          H.getIndexPairOpndHashMap());
+}