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 // used/compiler.used don't affect analyses. 62 if (GV.getName() == "llvm.compiler.used" || GV.getName() == "llvm.used") 63 return; 64 hash(23456); // Global header 65 hash(GV.getValueType()->getTypeID()); 66 } 67 68 void update(const Module &M) { 69 for (const GlobalVariable &GV : M.globals()) 70 update(GV); 71 for (const Function &F : M) 72 update(F); 73 } 74 75 uint64_t getHash() const { return Hash; } 76 }; 77 78 } // namespace 79 80 uint64_t llvm::StructuralHash(const Function &F) { 81 StructuralHashImpl H; 82 H.update(F); 83 return H.getHash(); 84 } 85 86 uint64_t llvm::StructuralHash(const Module &M) { 87 StructuralHashImpl H; 88 H.update(M); 89 return H.getHash(); 90 } 91