1 //===- llvm/IR/StructuralHash.h - 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 // This file provides hashing of the LLVM IR structure to be used to check 10 // Passes modification status. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_IR_STRUCTURALHASH_H 15 #define LLVM_IR_STRUCTURALHASH_H 16 17 #include "llvm/ADT/MapVector.h" 18 #include "llvm/ADT/StableHashing.h" 19 #include "llvm/IR/Instruction.h" 20 #include "llvm/Support/Compiler.h" 21 #include <cstdint> 22 23 namespace llvm { 24 25 class Function; 26 class Module; 27 28 /// Returns a hash of the function \p F. 29 /// \param F The function to hash. 30 /// \param DetailedHash Whether or not to encode additional information in the 31 /// hash. The additional information added into the hash when this flag is set 32 /// to true includes instruction and operand type information. 33 LLVM_ABI stable_hash StructuralHash(const Function &F, 34 bool DetailedHash = false); 35 36 /// Returns a hash of the global variable \p G. 37 LLVM_ABI stable_hash StructuralHash(const GlobalVariable &G); 38 39 /// Returns a hash of the module \p M by hashing all functions and global 40 /// variables contained within. \param M The module to hash. \param DetailedHash 41 /// Whether or not to encode additional information in the function hashes that 42 /// composed the module hash. 43 LLVM_ABI stable_hash StructuralHash(const Module &M, bool DetailedHash = false); 44 45 /// The pair of an instruction index and a operand index. 46 using IndexPair = std::pair<unsigned, unsigned>; 47 48 /// A map from an instruction index to an instruction pointer. 49 using IndexInstrMap = MapVector<unsigned, Instruction *>; 50 51 /// A map from an IndexPair to a stable hash. 52 using IndexOperandHashMapType = DenseMap<IndexPair, stable_hash>; 53 54 /// A function that takes an instruction and an operand index and returns true 55 /// if the operand should be ignored in the function hash computation. 56 using IgnoreOperandFunc = std::function<bool(const Instruction *, unsigned)>; 57 58 struct FunctionHashInfo { 59 /// A hash value representing the structural content of the function 60 stable_hash FunctionHash; 61 /// A mapping from instruction indices to instruction pointers 62 std::unique_ptr<IndexInstrMap> IndexInstruction; 63 /// A mapping from pairs of instruction indices and operand indices 64 /// to the hashes of the operands. This can be used to analyze or 65 /// reconstruct the differences in ignored operands 66 std::unique_ptr<IndexOperandHashMapType> IndexOperandHashMap; 67 FunctionHashInfoFunctionHashInfo68 FunctionHashInfo(stable_hash FuntionHash, 69 std::unique_ptr<IndexInstrMap> IndexInstruction, 70 std::unique_ptr<IndexOperandHashMapType> IndexOperandHashMap) 71 : FunctionHash(FuntionHash), 72 IndexInstruction(std::move(IndexInstruction)), 73 IndexOperandHashMap(std::move(IndexOperandHashMap)) {} 74 }; 75 76 /// Computes a structural hash of a given function, considering the structure 77 /// and content of the function's instructions while allowing for selective 78 /// ignoring of certain operands based on custom criteria. This hash can be used 79 /// to identify functions that are structurally similar or identical, which is 80 /// useful in optimizations, deduplication, or analysis tasks. 81 /// \param F The function to hash. 82 /// \param IgnoreOp A callable that takes an instruction and an operand index, 83 /// and returns true if the operand should be ignored in the hash computation. 84 /// \return A FunctionHashInfo structure 85 LLVM_ABI FunctionHashInfo 86 StructuralHashWithDifferences(const Function &F, IgnoreOperandFunc IgnoreOp); 87 88 } // end namespace llvm 89 90 #endif 91