LLVM  13.0.0git
StructuralHash.cpp
Go to the documentation of this file.
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 
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
i
i
Definition: README.txt:29
llvm
Definition: AllocatorList.h:23
llvm::Function
Definition: Function.h:61
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1167
Module.h
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:634
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::Instruction
Definition: Instruction.h:45
llvm::hashing::detail::hash_16_bytes
uint64_t hash_16_bytes(uint64_t low, uint64_t high)
Definition: Hashing.h:182
StructuralHash.h
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
H
#define H(x, y, z)
Definition: MD5.cpp:58
Function.h
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:364