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