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