1 //===-- StructuralHash.cpp - IR Hash for expensive checks -------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 
10 #ifdef EXPENSIVE_CHECKS
11 
12 #include "llvm/IR/StructuralHash.h"
13 #include "llvm/IR/Function.h"
14 #include "llvm/IR/Module.h"
15 
16 using namespace llvm;
17 
18 namespace {
19 namespace details {
20 
21 // Basic hashing mechanism to detect structural change to the IR, used to verify
22 // pass return status consistency with actual change. Loosely copied from
23 // llvm/lib/Transforms/Utils/FunctionComparator.cpp
24 
25 class StructuralHash {
26   uint64_t Hash = 0x6acaa36bef8325c5ULL;
27 
28   void update(uint64_t V) { Hash = hashing::detail::hash_16_bytes(Hash, V); }
29 
30 public:
31   StructuralHash() = default;
32 
33   void update(const Function &F) {
34     if (F.empty())
35       return;
36 
37     update(F.isVarArg());
38     update(F.arg_size());
39 
40     SmallVector<const BasicBlock *, 8> BBs;
41     SmallPtrSet<const BasicBlock *, 16> VisitedBBs;
42 
43     BBs.push_back(&F.getEntryBlock());
44     VisitedBBs.insert(BBs[0]);
45     while (!BBs.empty()) {
46       const BasicBlock *BB = BBs.pop_back_val();
47       update(45798); // Block header
48       for (auto &Inst : *BB)
49         update(Inst.getOpcode());
50 
51       const Instruction *Term = BB->getTerminator();
52       for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) {
53         if (!VisitedBBs.insert(Term->getSuccessor(i)).second)
54           continue;
55         BBs.push_back(Term->getSuccessor(i));
56       }
57     }
58   }
59 
60   void update(const Module &M) {
61     for (const Function &F : M)
62       update(F);
63   }
64 
65   uint64_t getHash() const { return Hash; }
66 };
67 
68 } // namespace details
69 
70 } // namespace
71 
72 uint64_t llvm::StructuralHash(const Function &F) {
73   details::StructuralHash H;
74   H.update(F);
75   return H.getHash();
76 }
77 
78 uint64_t llvm::StructuralHash(const Module &M) {
79   details::StructuralHash H;
80   H.update(M);
81   return H.getHash();
82 }
83 
84 #endif
85