1 //===- StableFunctionMap.h -------------------------------------*- 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 defines the StableFunctionMap class, to track similar functions. 10 // It provides a mechanism to map stable hashes of functions to their 11 // corresponding metadata. It includes structures for storing function details 12 // and methods for managing and querying these mappings. 13 // 14 //===---------------------------------------------------------------------===// 15 16 #ifndef LLVM_CGDATA_STABLEFUNCTIONMAP_H 17 #define LLVM_CGDATA_STABLEFUNCTIONMAP_H 18 19 #include "llvm/ADT/DenseMap.h" 20 #include "llvm/ADT/StringMap.h" 21 #include "llvm/IR/StructuralHash.h" 22 #include "llvm/Support/Compiler.h" 23 24 namespace llvm { 25 26 using IndexPairHash = std::pair<IndexPair, stable_hash>; 27 using IndexOperandHashVecType = SmallVector<IndexPairHash>; 28 29 /// A stable function is a function with a stable hash while tracking the 30 /// locations of ignored operands and their hashes. 31 struct StableFunction { 32 /// The combined stable hash of the function. 33 stable_hash Hash; 34 /// The name of the function. 35 std::string FunctionName; 36 /// The name of the module the function is in. 37 std::string ModuleName; 38 /// The number of instructions. 39 unsigned InstCount; 40 /// A vector of pairs of IndexPair and operand hash which was skipped. 41 IndexOperandHashVecType IndexOperandHashes; 42 StableFunctionStableFunction43 StableFunction(stable_hash Hash, const std::string FunctionName, 44 const std::string ModuleName, unsigned InstCount, 45 IndexOperandHashVecType &&IndexOperandHashes) 46 : Hash(Hash), FunctionName(FunctionName), ModuleName(ModuleName), 47 InstCount(InstCount), 48 IndexOperandHashes(std::move(IndexOperandHashes)) {} 49 StableFunction() = default; 50 }; 51 52 struct StableFunctionMap { 53 /// An efficient form of StableFunction for fast look-up 54 struct StableFunctionEntry { 55 /// The combined stable hash of the function. 56 stable_hash Hash; 57 /// Id of the function name. 58 unsigned FunctionNameId; 59 /// Id of the module name. 60 unsigned ModuleNameId; 61 /// The number of instructions. 62 unsigned InstCount; 63 /// A map from an IndexPair to a stable_hash which was skipped. 64 std::unique_ptr<IndexOperandHashMapType> IndexOperandHashMap; 65 StableFunctionEntryStableFunctionMap::StableFunctionEntry66 StableFunctionEntry( 67 stable_hash Hash, unsigned FunctionNameId, unsigned ModuleNameId, 68 unsigned InstCount, 69 std::unique_ptr<IndexOperandHashMapType> IndexOperandHashMap) 70 : Hash(Hash), FunctionNameId(FunctionNameId), 71 ModuleNameId(ModuleNameId), InstCount(InstCount), 72 IndexOperandHashMap(std::move(IndexOperandHashMap)) {} 73 }; 74 75 using HashFuncsMapType = 76 DenseMap<stable_hash, SmallVector<std::unique_ptr<StableFunctionEntry>>>; 77 78 /// Get the HashToFuncs map for serialization. getFunctionMapStableFunctionMap79 const HashFuncsMapType &getFunctionMap() const { return HashToFuncs; } 80 81 /// Get the NameToId vector for serialization. getNamesStableFunctionMap82 ArrayRef<std::string> getNames() const { return IdToName; } 83 84 /// Get an existing ID associated with the given name or create a new ID if it 85 /// doesn't exist. 86 LLVM_ABI unsigned getIdOrCreateForName(StringRef Name); 87 88 /// Get the name associated with a given ID 89 LLVM_ABI std::optional<std::string> getNameForId(unsigned Id) const; 90 91 /// Insert a `StableFunction` object into the function map. This method 92 /// handles the uniquing of string names and create a `StableFunctionEntry` 93 /// for insertion. 94 LLVM_ABI void insert(const StableFunction &Func); 95 96 /// Merge a \p OtherMap into this function map. 97 LLVM_ABI void merge(const StableFunctionMap &OtherMap); 98 99 /// \returns true if there is no stable function entry. emptyStableFunctionMap100 bool empty() const { return size() == 0; } 101 102 enum SizeType { 103 UniqueHashCount, // The number of unique hashes in HashToFuncs. 104 TotalFunctionCount, // The number of total functions in HashToFuncs. 105 MergeableFunctionCount, // The number of functions that can be merged based 106 // on their hash. 107 }; 108 109 /// \returns the size of StableFunctionMap. 110 /// \p Type is the type of size to return. 111 LLVM_ABI size_t size(SizeType Type = UniqueHashCount) const; 112 113 /// Finalize the stable function map by trimming content. 114 LLVM_ABI void finalize(bool SkipTrim = false); 115 116 private: 117 /// Insert a `StableFunctionEntry` into the function map directly. This 118 /// method assumes that string names have already been uniqued and the 119 /// `StableFunctionEntry` is ready for insertion. insertStableFunctionMap120 void insert(std::unique_ptr<StableFunctionEntry> FuncEntry) { 121 assert(!Finalized && "Cannot insert after finalization"); 122 HashToFuncs[FuncEntry->Hash].emplace_back(std::move(FuncEntry)); 123 } 124 125 /// A map from a stable_hash to a vector of functions with that hash. 126 HashFuncsMapType HashToFuncs; 127 /// A vector of strings to hold names. 128 SmallVector<std::string> IdToName; 129 /// A map from StringRef (name) to an ID. 130 StringMap<unsigned> NameToId; 131 /// True if the function map is finalized with minimal content. 132 bool Finalized = false; 133 134 friend struct StableFunctionMapRecord; 135 }; 136 137 } // namespace llvm 138 139 #endif 140