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 details {
19 
20 // Basic hashing mechanism to detect structural change to the IR, used to verify
21 // pass return status consistency with actual change. Loosely copied from
22 // llvm/lib/Transforms/Utils/FunctionComparator.cpp
23 
24 class StructuralHash {
25   uint64_t Hash = 0x6acaa36bef8325c5ULL;
26 
27   void update(uint64_t V) { Hash = hashing::detail::hash_16_bytes(Hash, V); }
28 
29 public:
30   StructuralHash() = default;
31 
32   void update(const Function &F) {
33     if (F.empty())
34       return;
35 
36     update(F.isVarArg());
37     update(F.arg_size());
38 
39     SmallVector<const BasicBlock *, 8> BBs;
40     SmallPtrSet<const BasicBlock *, 16> VisitedBBs;
41 
42     BBs.push_back(&F.getEntryBlock());
43     VisitedBBs.insert(BBs[0]);
44     while (!BBs.empty()) {
45       const BasicBlock *BB = BBs.pop_back_val();
46       update(45798); // Block header
47       for (auto &Inst : *BB)
48         update(Inst.getOpcode());
49 
50       const Instruction *Term = BB->getTerminator();
51       for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) {
52         if (!VisitedBBs.insert(Term->getSuccessor(i)).second)
53           continue;
54         BBs.push_back(Term->getSuccessor(i));
55       }
56     }
57   }
58 
59   void update(const Module &M) {
60     for (const Function &F : M)
61       update(F);
62   }
63 
64   uint64_t getHash() const { return Hash; }
65 };
66 
67 } // namespace details
68 
69 uint64_t llvm::StructuralHash(const Function &F) {
70   ::details::StructuralHash H;
71   H.update(F);
72   return H.getHash();
73 }
74 
75 uint64_t llvm::StructuralHash(const Module &M) {
76   ::details::StructuralHash H;
77   H.update(M);
78   return H.getHash();
79 }
80 
81 #endif
82