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