[IR] Add more details to StructuralHash

[aidengrossman]

Summary

This pass extends StructuralHash to include much more information about
the IR under analysis. This is done with a flag (Detailed) to configure
the behavior. The detailed behavior is intended for use in expensive
checks and downstream.

[nikic]

llvm/lib/IR/StructuralHash.cpp

129–137

This seems like a very random collection of things to add to the hash. Why isn't this just hashing all the operands? That should cover the operand types, the called function and the intrinsic ID.

[aidengrossman]

llvm/lib/IR/StructuralHash.cpp

129–137

I was under the impression that it wasn't possible to just hash a value. I can hash the pointer, but I'm not sure that would be correct in all cases (unless everything is uniqued appropriately).

https://github.com/llvm/llvm-project/blob/d9cb76bc4d5e903fe045c58a42fc791d0c70172b/llvm/include/llvm/Analysis/IRSimilarityIdentifier.h#L261 implements logic that seems to follow those assumptions (and is a similar implementation to what is here).

Definitely could be that my assumptions are incorrect here though.

[nikic]

llvm/lib/IR/StructuralHash.cpp

129–137

You are right that we can't "just" hash the operand pointers, but I'd still use that as the general approach. If the operand is a Constant you should be able to hash the pointer as those are uniqued, for Arguments you can take the argument number, and for Instructions you could use only the type for now (to handle those we'd have to number instructions).

[aidengrossman]

llvm/lib/IR/StructuralHash.cpp

129–137

Also, re: pointers, my intention with this is to have a hash that is stable across different modules (interested in looking at function deduplication across modules) given the same function which makes just hashing pointers provide incorrect results.

I'm planning on writing in support for other constant types in the future and instruction operands through numbering (in follow-up patches). My intention with the Detailed flag currently isn't to be make every semantically-meaningful difference produce a different hash but to capture most of the common cases and be "good enough" at most cases.

[aeubanks]

llvm/lib/IR/StructuralHash.cpp

129–137

we should split out a update(Value*) (which doesn't recursively look at operands) and hash the operands of the current instruction as well as the current instruction itself

144

is there anywhere we don't want this new functionality?

[jdoerfert]

FWIW, I think more details, even if not perfect, seems reasonable. We will experiment with this and come back to it as needed.

llvm/lib/IR/StructuralHash.cpp

122

early exit, plz.

[aidengrossman]

Address reviewer feedback

• Early exit where pointed out.
• Switch to hashing operands for the most part (except for in the case of cmp)
• Add a couple additional operands to hash, particularly integer constants and arguments.
• Rebase against upstream to include changes to prevent test regressions on 32-bit arches.

[aidengrossman]

Fix minor formatting issue

llvm/lib/IR/StructuralHash.cpp

129–137

I've split this out into an updateInstruction and an updateValue function. updateInstruction handles everything related to instructions and then calls updateValue when handling operands. I think it makes things a little bit clearer as it avoids any reasoning about recursion depending upon if the value is an instruction or not.

I've added a couple additional cases when handling operands (rather than just hashing the type) that aren't meant to be exhaustive.

144

Yes. The MergeFunctions pass is now using this hash after https://reviews.llvm.org/D158217 and the original hashing implementation did not include additional details (as I believe the intention was to not hash all details) and then use the FunctionComparator class where necessary.

[aeubanks]

this on its own lg, but I have inline comments

llvm/lib/IR/StructuralHash.cpp

48

we really shouldn't have to re-implement llvm::hash_value. IIUC the reason we're not is because 32-bit vs 64-bit hashes are different which causes MergeFunctions to act differently because it sorts hashes. but IMO MergeFunctions shouldn't be sorting by hash, that's kinda bad. I think we should go back to the original version of https://reviews.llvm.org/D158217 and fix MergeFunctions to be more deterministic and not rely on hash values. It seems like we're just currently lucky in that the hashes for test cases in MergeFunctions are ordered consistently between 32/64 bit.

[aidengrossman]

llvm/lib/IR/StructuralHash.cpp

48

I agree that it shouldn't be sorting by hash, but I'd rather not touch that if I don't have to. When I relanded that differential in 64da0be1fc06ee2199bd27c980736986e0eccd9d I updated it to use what MergeFunctions did originally and use hash_16_bytes along with a uint64_t rather than size_t (forgot to update the differential with the changes). The MergeFunction test was consistent before https://reviews.llvm.org/D158217 as they just directly called hash_16_bytes and stored everything as a uint64_t.

[aidengrossman]

Update patch

• Switch to native hashing implementations for APInt/APFloat
• Switch from hashing type pointers to hashing some details about the type as the former is non-deterministic (which of course is frustratingly masked by my system having ASLR disabled). Left a TODO to refactor the type hashing into a more formal hash_value implementation within the class.
• Formatting changes.

[aidengrossman]

llvm/lib/IR/StructuralHash.cpp

48

Sorry for not reading your message close enough initially. I missed basically the entire point. I've switched over to using the native hash_value implementations for APInt and APFloat to avoid the reimplementation. I think within StructuralHash we can guarantee the same hash between 32 bit and 64 bit platforms outside of the detailed hash case, but inside of the detailed hash case we don't make that guarantee. It would be good to order by something other than hash within MergeFunctions, but the ordering needs to be deterministic and ideally fast and hashes make quite a bit of sense for that (other than the significant churn when they change).

I'm thinking keeping the determinism between 64-bit/32-bit makes sense to preserve the MergeFunctions semantics (at least for now) for the non-detailed case and the detailed case can take advantage of hash_value implementations where appropriate. What do you think?

[nikic]

llvm/lib/IR/StructuralHash.cpp

37

Call hash(ToAdd) instead?

51

Aren't these cases covered by the type ID hash?

72

Use auto with dyn_cast.

73

Hrm, apparently we don't have a public API to get subclass data in a generic way :/

76

Loop over operands().

[aidengrossman]

Address reviewer feedback

llvm/lib/IR/StructuralHash.cpp

51

Yes. For some reason I was thinking that there was.a generic floating point type in the enum so did them separately. Thanks for the catch!

[nikic]

Looks fine. Please test EXPENSIVE_ CHECKS to make sure this doesn't find new missing invalidations.

llvm/lib/IR/StructuralHash.cpp

40

I don't think we should add hash_value implementations to uniqued types. It encourages misuse.

[aidengrossman]

Address reviewer feedback

• Remove TODO comment

[aidengrossman]

Looks like the changes caught a regression:

-- Testing: 1 tests, 1 workers --
FAIL: LLVM :: CodeGen/X86/statepoint-stack-usage.ll (1 of 1)
******************** TEST 'LLVM :: CodeGen/X86/statepoint-stack-usage.ll' FAILED ********************
Script:
--
: 'RUN: at line 1';   /tmp/llvm-expensive-checks/bin/llc -verify-machineinstrs -stack-symbol-ordering=0 < /tmp/llvm-project/llvm/test/CodeGen/X86/statepoint-stack-usage.ll | /tmp/llvm-expensive-checks/bin/FileCheck /tmp/llvm-project/llvm/test/CodeGen/X86/statepoint-stack-usage.ll
--
Exit Code: 2
Command Output (stderr):
--
+ : 'RUN: at line 1'
+ /tmp/llvm-expensive-checks/bin/llc -verify-machineinstrs -stack-symbol-ordering=0
+ /tmp/llvm-expensive-checks/bin/FileCheck /tmp/llvm-project/llvm/test/CodeGen/X86/statepoint-stack-usage.ll
Pass modifies its input and doesn't report it: CodeGen Prepare
Pass modifies its input and doesn't report it
UNREACHABLE executed at /tmp/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1441!
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.      Program arguments: /tmp/llvm-expensive-checks/bin/llc -verify-machineinstrs -stack-symbol-ordering=0
1.      Running pass 'Function Pass Manager' on module '<stdin>'.
2.      Running pass 'CodeGen Prepare' on function '@back_to_back_calls'
 #0 0x00005555580db4c8 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/tmp/llvm-expensive-checks/bin/llc+0x2b874c8)
 #1 0x00005555580d8f7e llvm::sys::RunSignalHandlers() (/tmp/llvm-expensive-checks/bin/llc+0x2b84f7e)
 #2 0x00005555580dbca8 SignalHandler(int) Signals.cpp:0:0
 #3 0x0000155554fd9520 (/lib/x86_64-linux-gnu/libc.so.6+0x42520)
 #4 0x000015555502da7c pthread_kill (/lib/x86_64-linux-gnu/libc.so.6+0x96a7c)
 #5 0x0000155554fd9476 gsignal (/lib/x86_64-linux-gnu/libc.so.6+0x42476)
 #6 0x0000155554fbf7f3 abort (/lib/x86_64-linux-gnu/libc.so.6+0x287f3)
 #7 0x0000555558038700 llvm::install_out_of_memory_new_handler() (/tmp/llvm-expensive-checks/bin/llc+0x2ae4700)
 #8 0x0000555557922b42 (/tmp/llvm-expensive-checks/bin/llc+0x23ceb42)
 #9 0x000055555792b232 llvm::FPPassManager::runOnModule(llvm::Module&) (/tmp/llvm-expensive-checks/bin/llc+0x23d7232)
#10 0x00005555579233fa llvm::legacy::PassManagerImpl::run(llvm::Module&) (/tmp/llvm-expensive-checks/bin/llc+0x23cf3fa)
#11 0x0000555556a5e757 main (/tmp/llvm-expensive-checks/bin/llc+0x150a757)
#12 0x0000155554fc0d90 (/lib/x86_64-linux-gnu/libc.so.6+0x29d90)
#13 0x0000155554fc0e40 __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x29e40)
#14 0x0000555556a58c65 _start (/tmp/llvm-expensive-checks/bin/llc+0x1504c65)
FileCheck error: '<stdin>' is empty.
FileCheck command line:  /tmp/llvm-expensive-checks/bin/FileCheck /tmp/llvm-project/llvm/test/CodeGen/X86/statepoint-stack-usage.ll
--
********************
********************
Failed Tests (1):
  LLVM :: CodeGen/X86/statepoint-stack-usage.ll

I'll file an issue and take a look and land this change after this gets fixed (or I find a bug in my code here).

[aidengrossman]

Any opposition to landing this with the detailed parameter set to false in the PM changed checks temporarily while https://github.com/llvm/llvm-project/issues/64938 is fixed (and then enable detailed structural hashing for change status expensive checks once that is fixed)?

[aeubanks]

In D158250#4616110, @aidengrossman wrote:

Any opposition to landing this with the detailed parameter set to false in the PM changed checks temporarily while https://github.com/llvm/llvm-project/issues/64938 is fixed (and then enable detailed structural hashing for change status expensive checks once that is fixed)?

that sounds fine with a TODO

llvm/include/llvm/IR/StructuralHash.h

 //===- llvm/IR/StructuralHash.h - IR Hashing --------------------*- 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
 //
 //===----------------------------------------------------------------------===//
 //

 
 namespace llvm {
 
 class Function;
 class Module;
 
 using IRHash = uint64_t;
 
-IRHash StructuralHash(const Function &F);
-IRHash StructuralHash(const Module &M);
+/// Returns a hash of the function \p F.
+/// \param F The function to hash.
+/// \param DetailedHash Whether or not to encode additional information in the
+/// hash. The additional information added into the hash when this flag is set
+/// to true includes instruction and operand type information.
+IRHash StructuralHash(const Function &F, bool DetailedHash = false);
+
+/// Returns a hash of the module \p M by hashing all functions and global
+/// variables contained within. \param M The module to hash. \param DetailedHash
+/// Whether or not to encode additional information in the function hashes that
+/// composed the module hash.
+IRHash StructuralHash(const Module &M, bool DetailedHash = false);
 
 } // end namespace llvm
 
 #endif

llvm/lib/IR/Pass.cpp

 //===- Pass.cpp - LLVM Pass Infrastructure Implementation -----------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //

 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 // dump - call print(cerr);
 LLVM_DUMP_METHOD void Pass::dump() const {
   print(dbgs(), nullptr);
 }
 #endif
 
 #ifdef EXPENSIVE_CHECKS
-uint64_t Pass::structuralHash(Module &M) const { return StructuralHash(M); }
+uint64_t Pass::structuralHash(Module &M) const {
+  return StructuralHash(M, true);
+}
 
-uint64_t Pass::structuralHash(Function &F) const { return StructuralHash(F); }
+uint64_t Pass::structuralHash(Function &F) const {
+  return StructuralHash(F, true);
+}
 #endif
 
 //===----------------------------------------------------------------------===//
 // ImmutablePass Implementation
 //
 // Force out-of-line virtual method.
 ImmutablePass::~ImmutablePass() = default;
 

llvm/lib/IR/StructuralHash.cpp

 //===-- StructuralHash.cpp - IR Hashing -------------------------*- 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
 //
 //===----------------------------------------------------------------------===//
 
 #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"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
 
 using namespace llvm;
 
 namespace {
 
 // Basic hashing mechanism to detect structural change to the IR, used to verify
 // pass return status consistency with actual change. Loosely copied from
 // llvm/lib/Transforms/Utils/FunctionComparator.cpp
 
 class StructuralHashImpl {
   uint64_t Hash;
 
   void hash(uint64_t V) { Hash = hashing::detail::hash_16_bytes(Hash, V); }
 
+  // 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) {
+    uint64_t ToAdd = hash_combine(V);
+    Hash = hashing::detail::hash_16_bytes(Hash, ToAdd);
+  }
+
 public:
   StructuralHashImpl() : Hash(4) {}
 
+  void updateOperand(Value *Operand) {
+    hashArbitaryType(Operand->getType());
+
+    // 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)) {
+      if (ConstInt->getBitWidth() <= 64) {
+        hash(ConstInt->getValue().getLimitedValue());
+      } else if (ConstInt->getBitWidth() <= 256) {
+        Hash = hashing::detail::hash_17to32_bytes(
+            (const char *)ConstInt->getValue().getRawData(),
+            ConstInt->getBitWidth() / 8, Hash);
+      }
+    } else if (Argument *Arg = dyn_cast<Argument>(Operand)) {
+      hash(Arg->getArgNo());
+    } else if(Function *Func = dyn_cast<Function>(Operand)) {
+      hashArbitaryType(Func->getName());
+    }
+  }
+
+  void updateInstruction(const Instruction &Inst, bool DetailedHash) {
+    hash(Inst.getOpcode());
+
+    if (!DetailedHash)
+      return;
+
+    hashArbitaryType(Inst.getType());
+
+    // Handle additional properties of specific instructions that cause
+    // semantic differences in the IR.
+    if (const CmpInst *ComparisonInstruction = dyn_cast<CmpInst>(&Inst))
+      hash(ComparisonInstruction->getPredicate());
+
+    for (unsigned I = 0; I < Inst.getNumOperands(); ++I)
+      updateOperand(Inst.getOperand(I));
+  }
+
   // A function hash is calculated by considering only the number of arguments
   // and whether a function is varargs, the order of basic blocks (given by the
   // successors of each basic block in depth first order), and the order of
   // opcodes of each instruction within each of these basic blocks. This mirrors
   // the strategy FunctionComparator::compare() uses to compare functions by
   // walking the BBs in depth first order and comparing each instruction in
   // sequence. Because this hash currently does not look at the operands, it is
   // insensitive to things such as the target of calls and the constants used in
   // the function, which makes it useful when possibly merging functions which
   // are the same modulo constants and call targets.
   //
   // Note that different users of StructuralHash will want different behavior
   // out of it (i.e., MergeFunctions will want something different from PM
   // 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) {
+  void update(const Function &F, bool DetailedHash) {
     // Declarations don't affect analyses.
     if (F.isDeclaration())
       return;
 
     hash(0x62642d6b6b2d6b72); // Function header
 
     hash(F.isVarArg());
     hash(F.arg_size());
 
     SmallVector<const BasicBlock *, 8> BBs;
     SmallPtrSet<const BasicBlock *, 16> VisitedBBs;
 
     // Walk the blocks in the same order as
     // FunctionComparator::cmpBasicBlocks(), accumulating the hash of the
     // function "structure." (BB and opcode sequence)
     BBs.push_back(&F.getEntryBlock());
     VisitedBBs.insert(BBs[0]);
     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);
-      for (auto &Inst : *BB)
-        hash(Inst.getOpcode());
+      for (auto &Inst : *BB) {
+                                updateInstruction(Inst, DetailedHash);
+      }
 
       const Instruction *Term = BB->getTerminator();
       for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) {
         if (!VisitedBBs.insert(Term->getSuccessor(i)).second)
           continue;
         BBs.push_back(Term->getSuccessor(i));
       }
     }
   }
 
   void update(const GlobalVariable &GV) {
     // Declarations and used/compiler.used don't affect analyses.
     // Since there are several `llvm.*` metadata, like `llvm.embedded.object`,
     // we ignore anything with the `.llvm` prefix
     if (GV.isDeclaration() || GV.getName().starts_with("llvm."))
       return;
     hash(23456); // Global header
     hash(GV.getValueType()->getTypeID());
   }
 
-  void update(const Module &M) {
+  void update(const Module &M, bool DetailedHash) {
     for (const GlobalVariable &GV : M.globals())
       update(GV);
     for (const Function &F : M)
-      update(F);
+      update(F, DetailedHash);
   }
 
   uint64_t getHash() const { return Hash; }
 };
 
 } // namespace
 
-IRHash llvm::StructuralHash(const Function &F) {
+IRHash llvm::StructuralHash(const Function &F, bool DetailedHash) {
   StructuralHashImpl H;
-  H.update(F);
+  H.update(F, DetailedHash);
   return H.getHash();
 }
 
-IRHash llvm::StructuralHash(const Module &M) {
+IRHash llvm::StructuralHash(const Module &M, bool DetailedHash) {
   StructuralHashImpl H;
-  H.update(M);
+  H.update(M, DetailedHash);
   return H.getHash();
 }

llvm/unittests/IR/StructuralHashTest.cpp

 //===- llvm/unittest/IR/StructuralHashTest.cpp ----------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
TEST(StructuralHashTest, Function) {
   std::unique_ptr<Module> M2 = parseIR(Ctx, "define void @f(i32) { ret void }");
   EXPECT_NE(StructuralHash(*M1), StructuralHash(*M2));
 }
 
 TEST(StructuralHashTest, FunctionRetType) {
   LLVMContext Ctx;
   std::unique_ptr<Module> M1 = parseIR(Ctx, "define void @f() { ret void }");
   std::unique_ptr<Module> M2 = parseIR(Ctx, "define i32 @f() { ret i32 0 }");
-  // FIXME: should be different
   EXPECT_EQ(StructuralHash(*M1), StructuralHash(*M2));
+  EXPECT_NE(StructuralHash(*M1, true), StructuralHash(*M2, true));
 }
 
 TEST(StructuralHashTest, InstructionOpCode) {
   LLVMContext Ctx;
   std::unique_ptr<Module> M1 = parseIR(Ctx, "define void @f(ptr %p) {\n"
                                             "  %a = load i32, ptr %p\n"
                                             "  ret void\n"
                                             "}\n");
   std::unique_ptr<Module> M2 =
       parseIR(Ctx, "define void @f(ptr %p) {\n"
                    "  %a = getelementptr i8, ptr %p, i32 1\n"
                    "  ret void\n"
                    "}\n");
   EXPECT_NE(StructuralHash(*M1), StructuralHash(*M2));
 }
 
-TEST(StructuralHashTest, InstructionType) {
+TEST(StructuralHashTest, InstructionSubType) {
   LLVMContext Ctx;
   std::unique_ptr<Module> M1 = parseIR(Ctx, "define void @f(ptr %p) {\n"
                                             "  %a = load i32, ptr %p\n"
                                             "  ret void\n"
                                             "}\n");
   std::unique_ptr<Module> M2 = parseIR(Ctx, "define void @f(ptr %p) {\n"
                                             "  %a = load i64, ptr %p\n"
                                             "  ret void\n"
                                             "}\n");
-  // FIXME: should be different
   EXPECT_EQ(StructuralHash(*M1), StructuralHash(*M2));
+  EXPECT_NE(StructuralHash(*M1, true), StructuralHash(*M2, true));
+}
+
+TEST(StructuralHashTest, InstructionType) {
+  LLVMContext Ctx;
+  std::unique_ptr<Module> M1 = parseIR(Ctx, "define void @f(ptr %p) {\n"
+                                            "  %1 = load i32, ptr %p\n"
+                                            "  ret void\n"
+                                            "}\n");
+  std::unique_ptr<Module> M2 = parseIR(Ctx, "define void @f(ptr %p) {\n"
+                                            "  %1 = load float, ptr %p\n"
+                                            "  ret void\n"
+                                            "}\n");
+  EXPECT_EQ(StructuralHash(*M1), StructuralHash(*M2));
+  EXPECT_NE(StructuralHash(*M1, true), StructuralHash(*M2, true));
 }
 
 TEST(StructuralHashTest, IgnoredMetadata) {
   LLVMContext Ctx;
   std::unique_ptr<Module> M1 = parseIR(Ctx, "@a = global i32 1\n");
   // clang-format off
   std::unique_ptr<Module> M2 = parseIR(
       Ctx, R"(
         @a = global i32 1
         @llvm.embedded.object = private constant [4 x i8] c"BC\C0\00", section ".llvm.lto", align 1, !exclude !0
         @llvm.compiler.used = appending global [1 x ptr] [ptr @llvm.embedded.object], section "llvm.metadata"
 
         !llvm.embedded.objects = !{!1}
 
         !0 = !{}
         !1 = !{ptr @llvm.embedded.object, !".llvm.lto"}
         )");
+  // clang-format on
+  EXPECT_EQ(StructuralHash(*M1), StructuralHash(*M2));
+}
+
+TEST(StructuralHashTest, ComparisonInstructionPredicate) {
+  LLVMContext Ctx;
+  std::unique_ptr<Module> M1 = parseIR(Ctx, "define i1 @f(i64 %a, i64 %b) {\n"
+                                            "  %1 = icmp eq i64 %a, %b\n"
+                                            "  ret i1 %1\n"
+                                            "}\n");
+  std::unique_ptr<Module> M2 = parseIR(Ctx, "define i1 @f(i64 %a, i64 %b) {\n"
+                                            "  %1 = icmp ne i64 %a, %b\n"
+                                            " ret i1 %1\n"
+                                            "}\n");
+  EXPECT_EQ(StructuralHash(*M1), StructuralHash(*M2));
+  EXPECT_NE(StructuralHash(*M1, true), StructuralHash(*M2, true));
+}
+
+TEST(StructuralHashTest, IntrinsicInstruction) {
+  LLVMContext Ctx;
+  std::unique_ptr<Module> M1 = parseIR(Ctx, "define float @f(float %a) {\n"
+                                            "  %b = call float @llvm.sin.f32(float %a)\n"
+                                            "  ret float %b\n"
+                                            "}\n"
+                                            "declare float @llvm.sin.f32(float)\n");
+  std::unique_ptr<Module> M2 = parseIR(Ctx, "define float @f(float %a) {\n"
+                                            "  %b = call float @llvm.cos.f32(float %a)\n"
+                                            "  ret float %b\n"
+                                            "}\n"
+                                            "declare float @llvm.cos.f32(float)\n");
+  EXPECT_EQ(StructuralHash(*M1), StructuralHash(*M2));
+  EXPECT_NE(StructuralHash(*M1, true), StructuralHash(*M2, true));
+}
+
+TEST(StructuralHashTest, CallInstruction) {
+  LLVMContext Ctx;
+  std::unique_ptr<Module> M1 = parseIR(Ctx, "define i64 @f(i64 %a) {\n"
+                                            "  %b = call i64 @f1(i64 %a)\n"
+                                            "  ret i64 %b\n"
+                                            "}\n"
+                                            "declare i64 @f1(i64)");
+  std::unique_ptr<Module> M2 = parseIR(Ctx, "define i64 @f(i64 %a) {\n"
+                                            "  %b = call i64 @f2(i64 %a)\n"
+                                            "  ret i64 %b\n"
+                                            "}\n"
+                                            "declare i64 @f2(i64)");
+  EXPECT_EQ(StructuralHash(*M1), StructuralHash(*M2));
+  EXPECT_NE(StructuralHash(*M1, true), StructuralHash(*M2, true));
+}
+
+TEST(StructuralHashTest, ConstantInteger) {
+        LLVMContext Ctx;
+        std::unique_ptr<Module> M1 = parseIR(Ctx, "define i64 @f1() {\n"
+                                                  "  ret i64 1\n"
+                                                  "}\n");
+        std::unique_ptr<Module> M2 = parseIR(Ctx, "define i64 @f2() {\n"
+                                                  "  ret i64 2\n"
+                                                  "}\n");
+        EXPECT_EQ(StructuralHash(*M1), StructuralHash(*M2));
+        EXPECT_NE(StructuralHash(*M1, true), StructuralHash(*M2, true));
+}
+
+TEST(StructuralHashTest, BigConstantInteger) {
+        LLVMContext Ctx;
+        std::unique_ptr<Module> M1 =
+            parseIR(Ctx, "define i128 @f1() {\n"
+                         "  ret i128 18446744073709551616\n"
+                         "}\n");
+        std::unique_ptr<Module> M2 =
+            parseIR(Ctx, "define i128 @f2() {\n"
+                         "  ret i128 18446744073709551617\n"
+                         "}\n");
+        EXPECT_EQ(StructuralHash(*M1), StructuralHash(*M2));
+        EXPECT_NE(StructuralHash(*M1, true), StructuralHash(*M2, true));
+}
+
+TEST(StructuralHashTest, ArgumentNumber) {
+        LLVMContext Ctx;
+        std::unique_ptr<Module> M1 =
+            parseIR(Ctx, "define i64 @f1(i64 %a, i64 %b) {\n"
+                         "  ret i64 %a\n"
+                         "}\n");
+        std::unique_ptr<Module> M2 =
+            parseIR(Ctx, "define i64 @f2(i64 %a, i64 %b) {\n"
+                         "  ret i64 %b\n"
+                         "}\n");
         EXPECT_EQ(StructuralHash(*M1), StructuralHash(*M2));
+        EXPECT_NE(StructuralHash(*M1, true), StructuralHash(*M2, true));
 }
 } // end anonymous namespace