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