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