llvm/IR/StructuralHash.h

0001 //===- llvm/IR/StructuralHash.h - IR Hashing --------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // This file provides hashing of the LLVM IR structure to be used to check
0010 // Passes modification status.
0011 //
0012 //===----------------------------------------------------------------------===//
0013
0014 #ifndef LLVM_IR_STRUCTURALHASH_H
0015 #define LLVM_IR_STRUCTURALHASH_H
0016
0017 #include "llvm/ADT/MapVector.h"
0018 #include "llvm/ADT/StableHashing.h"
0019 #include "llvm/IR/Instruction.h"
0020 #include <cstdint>
0021
0022 namespace llvm {
0023
0024 class Function;
0025 class Module;
0026
0027 /// Returns a hash of the function \p F.
0028 /// \param F The function to hash.
0029 /// \param DetailedHash Whether or not to encode additional information in the
0030 /// hash. The additional information added into the hash when this flag is set
0031 /// to true includes instruction and operand type information.
0032 stable_hash StructuralHash(const Function &F, bool DetailedHash = false);
0033
0034 /// Returns a hash of the global variable \p G.
0035 stable_hash StructuralHash(const GlobalVariable &G);
0036
0037 /// Returns a hash of the module \p M by hashing all functions and global
0038 /// variables contained within. \param M The module to hash. \param DetailedHash
0039 /// Whether or not to encode additional information in the function hashes that
0040 /// composed the module hash.
0041 stable_hash StructuralHash(const Module &M, bool DetailedHash = false);
0042
0043 /// The pair of an instruction index and a operand index.
0044 using IndexPair = std::pair<unsigned, unsigned>;
0045
0046 /// A map from an instruction index to an instruction pointer.
0047 using IndexInstrMap = MapVector<unsigned, Instruction *>;
0048
0049 /// A map from an IndexPair to a stable hash.
0050 using IndexOperandHashMapType = DenseMap<IndexPair, stable_hash>;
0051
0052 /// A function that takes an instruction and an operand index and returns true
0053 /// if the operand should be ignored in the function hash computation.
0054 using IgnoreOperandFunc = std::function<bool(const Instruction *, unsigned)>;
0055
0056 struct FunctionHashInfo {
0057   /// A hash value representing the structural content of the function
0058   stable_hash FunctionHash;
0059   /// A mapping from instruction indices to instruction pointers
0060   std::unique_ptr<IndexInstrMap> IndexInstruction;
0061   /// A mapping from pairs of instruction indices and operand indices
0062   /// to the hashes of the operands. This can be used to analyze or
0063   /// reconstruct the differences in ignored operands
0064   std::unique_ptr<IndexOperandHashMapType> IndexOperandHashMap;
0065
0066   FunctionHashInfo(stable_hash FuntionHash,
0067                    std::unique_ptr<IndexInstrMap> IndexInstruction,
0068                    std::unique_ptr<IndexOperandHashMapType> IndexOperandHashMap)
0069       : FunctionHash(FuntionHash),
0070         IndexInstruction(std::move(IndexInstruction)),
0071         IndexOperandHashMap(std::move(IndexOperandHashMap)) {}
0072 };
0073
0074 /// Computes a structural hash of a given function, considering the structure
0075 /// and content of the function's instructions while allowing for selective
0076 /// ignoring of certain operands based on custom criteria. This hash can be used
0077 /// to identify functions that are structurally similar or identical, which is
0078 /// useful in optimizations, deduplication, or analysis tasks.
0079 /// \param F The function to hash.
0080 /// \param IgnoreOp A callable that takes an instruction and an operand index,
0081 /// and returns true if the operand should be ignored in the hash computation.
0082 /// \return A FunctionHashInfo structure
0083 FunctionHashInfo StructuralHashWithDifferences(const Function &F,
0084                                                IgnoreOperandFunc IgnoreOp);
0085
0086 } // end namespace llvm
0087
0088 #endif