1//===-- StableFunctionMap.cpp ---------------------------------------------===//
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 implements the functionality for the StableFunctionMap class, which
10// manages the mapping of stable function hashes to their metadata. It includes
11// methods for inserting, merging, and finalizing function entries, as well as
12// utilities for handling function names and IDs.
13//
14//===----------------------------------------------------------------------===//
15
16#include "llvm/CGData/StableFunctionMap.h"
17#include "CGDataOptions.h"
18#include "llvm/ADT/SmallSet.h"
19#include "llvm/CGData/StableFunctionMapRecord.h"
20#include "llvm/Support/Debug.h"
21
22#define DEBUG_TYPE "stable-function-map"
23
24using namespace llvm;
25
26unsigned StableFunctionMap::getIdOrCreateForName(StringRef Name) {
27 auto It = NameToId.find(Key: Name);
28 if (It != NameToId.end())
29 return It->second;
30 unsigned Id = IdToName.size();
31 assert(Id == NameToId.size() && "ID collision");
32 IdToName.emplace_back(Args: Name.str());
33 NameToId[IdToName.back()] = Id;
34 return Id;
35}
36
37std::optional<std::string> StableFunctionMap::getNameForId(unsigned Id) const {
38 if (Id >= IdToName.size())
39 return std::nullopt;
40 return IdToName[Id];
41}
42
43void StableFunctionMap::insert(const StableFunction &Func) {
44 assert(!Finalized && "Cannot insert after finalization");
45 auto FuncNameId = getIdOrCreateForName(Name: Func.FunctionName);
46 auto ModuleNameId = getIdOrCreateForName(Name: Func.ModuleName);
47 auto IndexOperandHashMap = std::make_unique<IndexOperandHashMapType>();
48 for (auto &[Index, Hash] : Func.IndexOperandHashes)
49 (*IndexOperandHashMap)[Index] = Hash;
50 auto FuncEntry = std::make_unique<StableFunctionEntry>(
51 args: Func.Hash, args&: FuncNameId, args&: ModuleNameId, args: Func.InstCount,
52 args: std::move(IndexOperandHashMap));
53 insert(FuncEntry: std::move(FuncEntry));
54}
55
56void StableFunctionMap::merge(const StableFunctionMap &OtherMap) {
57 assert(!Finalized && "Cannot merge after finalization");
58 deserializeLazyLoadingEntries();
59 for (auto &[Hash, Funcs] : OtherMap.HashToFuncs) {
60 auto &ThisFuncs = HashToFuncs[Hash].Entries;
61 for (auto &Func : Funcs.Entries) {
62 auto FuncNameId =
63 getIdOrCreateForName(Name: *OtherMap.getNameForId(Id: Func->FunctionNameId));
64 auto ModuleNameId =
65 getIdOrCreateForName(Name: *OtherMap.getNameForId(Id: Func->ModuleNameId));
66 auto ClonedIndexOperandHashMap =
67 std::make_unique<IndexOperandHashMapType>(args&: *Func->IndexOperandHashMap);
68 ThisFuncs.emplace_back(Args: std::make_unique<StableFunctionEntry>(
69 args&: Func->Hash, args&: FuncNameId, args&: ModuleNameId, args&: Func->InstCount,
70 args: std::move(ClonedIndexOperandHashMap)));
71 }
72 }
73}
74
75size_t StableFunctionMap::size(SizeType Type) const {
76 switch (Type) {
77 case UniqueHashCount:
78 return HashToFuncs.size();
79 case TotalFunctionCount: {
80 deserializeLazyLoadingEntries();
81 size_t Count = 0;
82 for (auto &Funcs : HashToFuncs)
83 Count += Funcs.second.Entries.size();
84 return Count;
85 }
86 case MergeableFunctionCount: {
87 deserializeLazyLoadingEntries();
88 size_t Count = 0;
89 for (auto &[Hash, Funcs] : HashToFuncs)
90 if (Funcs.Entries.size() >= 2)
91 Count += Funcs.Entries.size();
92 return Count;
93 }
94 }
95 llvm_unreachable("Unhandled size type");
96}
97
98const StableFunctionMap::StableFunctionEntries &
99StableFunctionMap::at(HashFuncsMapType::key_type FunctionHash) const {
100 auto It = HashToFuncs.find(x: FunctionHash);
101 assert(It != HashToFuncs.end() && "FunctionHash not found!");
102 if (isLazilyLoaded())
103 deserializeLazyLoadingEntry(It);
104 return It->second.Entries;
105}
106
107void StableFunctionMap::deserializeLazyLoadingEntry(
108 HashFuncsMapType::iterator It) const {
109 assert(isLazilyLoaded() && "Cannot deserialize non-lazily-loaded map");
110 auto &[Hash, Storage] = *It;
111 std::call_once(once&: Storage.LazyLoadFlag,
112 f: [this, HashArg = Hash, &StorageArg = Storage]() {
113 for (auto Offset : StorageArg.Offsets)
114 StableFunctionMapRecord::deserializeEntry(
115 Ptr: reinterpret_cast<const unsigned char *>(Offset),
116 Hash: HashArg, FunctionMap: const_cast<StableFunctionMap *>(this));
117 });
118}
119
120void StableFunctionMap::deserializeLazyLoadingEntries() const {
121 if (!isLazilyLoaded())
122 return;
123 for (auto It = HashToFuncs.begin(); It != HashToFuncs.end(); ++It)
124 deserializeLazyLoadingEntry(It);
125}
126
127const StableFunctionMap::HashFuncsMapType &
128StableFunctionMap::getFunctionMap() const {
129 // Ensure all entries are deserialized before returning the raw map.
130 if (isLazilyLoaded())
131 deserializeLazyLoadingEntries();
132 return HashToFuncs;
133}
134
135using ParamLocs = SmallVector<IndexPair>;
136static void
137removeIdenticalIndexPair(StableFunctionMap::StableFunctionEntries &SFS) {
138 auto &RSF = SFS[0];
139 unsigned StableFunctionCount = SFS.size();
140
141 SmallVector<IndexPair> ToDelete;
142 for (auto &[Pair, Hash] : *(RSF->IndexOperandHashMap)) {
143 bool Identical = true;
144 for (unsigned J = 1; J < StableFunctionCount; ++J) {
145 auto &SF = SFS[J];
146 const auto &SHash = SF->IndexOperandHashMap->at(Val: Pair);
147 if (Hash != SHash) {
148 Identical = false;
149 break;
150 }
151 }
152
153 // No need to parameterize them if the hashes are identical across stable
154 // functions.
155 if (Identical)
156 ToDelete.emplace_back(Args&: Pair);
157 }
158
159 for (auto &Pair : ToDelete)
160 for (auto &SF : SFS)
161 SF->IndexOperandHashMap->erase(Val: Pair);
162}
163
164static bool isProfitable(const StableFunctionMap::StableFunctionEntries &SFS) {
165 const CGDataOptions &Opts = CGDataOptions::Global;
166 unsigned StableFunctionCount = SFS.size();
167 if (StableFunctionCount < Opts.global_merging_min_merges)
168 return false;
169
170 unsigned InstCount = SFS[0]->InstCount;
171 if (InstCount < Opts.global_merging_min_instrs)
172 return false;
173
174 double Cost = 0.0;
175 SmallSet<stable_hash, 8> UniqueHashVals;
176 for (auto &SF : SFS) {
177 UniqueHashVals.clear();
178 for (auto &[IndexPair, Hash] : *SF->IndexOperandHashMap)
179 UniqueHashVals.insert(V: Hash);
180 unsigned ParamCount = UniqueHashVals.size();
181 if (ParamCount > Opts.global_merging_max_params)
182 return false;
183 // Theoretically, if ParamCount is 0, it results in identical code folding
184 // (ICF), which we can skip merging here since the linker already handles
185 // ICF. This pass would otherwise introduce unnecessary thunks that are
186 // merely direct jumps. However, enabling this could be beneficial depending
187 // on downstream passes, so we provide an option for it.
188 if (Opts.global_merging_skip_no_params && ParamCount == 0)
189 return false;
190 Cost += ParamCount * Opts.global_merging_param_overhead +
191 Opts.global_merging_call_overhead;
192 }
193 Cost += Opts.global_merging_extra_threshold;
194
195 double Benefit =
196 InstCount * (StableFunctionCount - 1) * Opts.global_merging_inst_overhead;
197 bool Result = Benefit > Cost;
198 LLVM_DEBUG(dbgs() << "isProfitable: Hash = " << SFS[0]->Hash << ", "
199 << "StableFunctionCount = " << StableFunctionCount
200 << ", InstCount = " << InstCount
201 << ", Benefit = " << Benefit << ", Cost = " << Cost
202 << ", Result = " << (Result ? "true" : "false") << "\n");
203 return Result;
204}
205
206void StableFunctionMap::finalize(bool SkipTrim) {
207 deserializeLazyLoadingEntries();
208 SmallVector<HashFuncsMapType::iterator> ToDelete;
209 for (auto It = HashToFuncs.begin(); It != HashToFuncs.end(); ++It) {
210 auto &[StableHash, Storage] = *It;
211 auto &SFS = Storage.Entries;
212
213 // Group stable functions by ModuleIdentifier.
214 llvm::stable_sort(Range&: SFS, C: [&](const std::unique_ptr<StableFunctionEntry> &L,
215 const std::unique_ptr<StableFunctionEntry> &R) {
216 return *getNameForId(Id: L->ModuleNameId) < *getNameForId(Id: R->ModuleNameId);
217 });
218
219 // Consider the first function as the root function.
220 auto &RSF = SFS[0];
221
222 bool Invalid = false;
223 unsigned StableFunctionCount = SFS.size();
224 for (unsigned I = 1; I < StableFunctionCount; ++I) {
225 auto &SF = SFS[I];
226 assert(RSF->Hash == SF->Hash);
227 if (RSF->InstCount != SF->InstCount) {
228 Invalid = true;
229 break;
230 }
231 if (RSF->IndexOperandHashMap->size() != SF->IndexOperandHashMap->size()) {
232 Invalid = true;
233 break;
234 }
235 for (auto &P : *RSF->IndexOperandHashMap) {
236 auto &InstOpndIndex = P.first;
237 if (!SF->IndexOperandHashMap->count(Val: InstOpndIndex)) {
238 Invalid = true;
239 break;
240 }
241 }
242 }
243 if (Invalid) {
244 ToDelete.push_back(Elt: It);
245 continue;
246 }
247
248 if (SkipTrim)
249 continue;
250
251 // Trim the index pair that has the same operand hash across
252 // stable functions.
253 removeIdenticalIndexPair(SFS);
254
255 if (!isProfitable(SFS))
256 ToDelete.push_back(Elt: It);
257 }
258 for (auto It : ToDelete)
259 HashToFuncs.erase(position: It);
260
261 Finalized = true;
262}
263