1 //===-- StructuralHash.cpp - IR Hashing -------------------------*- 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 #include "llvm/IR/StructuralHash.h"
10 #include "llvm/IR/Function.h"
11 #include "llvm/IR/GlobalVariable.h"
12 #include "llvm/IR/Module.h"
13 
14 using namespace llvm;
15 
16 namespace {
17 
18 // Basic hashing mechanism to detect structural change to the IR, used to verify
19 // pass return status consistency with actual change. Loosely copied from
20 // llvm/lib/Transforms/Utils/FunctionComparator.cpp
21 
22 class StructuralHashImpl {
23   hash_code Hash;
24 
25   template <typename T> void hash(const T &V) { Hash = hash_combine(Hash, V); }
26 
27 public:
28   StructuralHashImpl() : Hash(4) {}
29 
30   void update(const Function &F) {
31     // Declarations don't affect analyses.
32     if (F.isDeclaration())
33       return;
34 
35     hash(12345); // Function header
36 
37     hash(F.isVarArg());
38     hash(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       hash(45798); // Block header
48       for (auto &Inst : *BB)
49         hash(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 GlobalVariable &GV) {
61     // Declarations and used/compiler.used don't affect analyses.
62     // Since there are several `llvm.*` metadata, like `llvm.embedded.object`,
63     // we ignore anything with the `.llvm` prefix
64     if (GV.isDeclaration() || GV.getName().starts_with("llvm."))
65       return;
66     hash(23456); // Global header
67     hash(GV.getValueType()->getTypeID());
68   }
69 
70   void update(const Module &M) {
71     for (const GlobalVariable &GV : M.globals())
72       update(GV);
73     for (const Function &F : M)
74       update(F);
75   }
76 
77   uint64_t getHash() const { return Hash; }
78 };
79 
80 } // namespace
81 
82 uint64_t llvm::StructuralHash(const Function &F) {
83   StructuralHashImpl H;
84   H.update(F);
85   return H.getHash();
86 }
87 
88 uint64_t llvm::StructuralHash(const Module &M) {
89   StructuralHashImpl H;
90   H.update(M);
91   return H.getHash();
92 }
93