Movatterモバイル変換

[0]ホーム
URL:

LLVM 20.0.0git
StableFunctionMap.cpp
Go to the documentation of this file.
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 namespacellvm;
24
25staticcl::opt<unsigned>
26GlobalMergingMinMerges("global-merging-min-merges",
27cl::desc("Minimum number of similar functions with "
28"the same hash required for merging."),
29cl::init(2),cl::Hidden);
30staticcl::opt<unsigned>GlobalMergingMinInstrs(
31"global-merging-min-instrs",
32cl::desc("The minimum instruction count required when merging functions."),
33cl::init(1),cl::Hidden);
34staticcl::opt<unsigned>GlobalMergingMaxParams(
35"global-merging-max-params",
36cl::desc(
37"The maximum number of parameters allowed when merging functions."),
38cl::init(std::numeric_limits<unsigned>::max()),cl::Hidden);
39staticcl::opt<bool>GlobalMergingSkipNoParams(
40"global-merging-skip-no-params",
41cl::desc("Skip merging functions with no parameters."),cl::init(true),
42cl::Hidden);
43staticcl::opt<double>GlobalMergingInstOverhead(
44"global-merging-inst-overhead",
45cl::desc("The overhead cost associated with each instruction when lowering "
46"to machine instruction."),
47cl::init(1.2),cl::Hidden);
48staticcl::opt<double>GlobalMergingParamOverhead(
49"global-merging-param-overhead",
50cl::desc("The overhead cost associated with each parameter when merging "
51"functions."),
52cl::init(2.0),cl::Hidden);
53staticcl::opt<double>
54GlobalMergingCallOverhead("global-merging-call-overhead",
55cl::desc("The overhead cost associated with each "
56"function call when merging functions."),
57cl::init(1.0),cl::Hidden);
58staticcl::opt<double>GlobalMergingExtraThreshold(
59"global-merging-extra-threshold",
60cl::desc("An additional cost threshold that must be exceeded for merging "
61"to be considered beneficial."),
62cl::init(0.0),cl::Hidden);
63
64unsignedStableFunctionMap::getIdOrCreateForName(StringRefName) {
65auto It = NameToId.find(Name);
66if (It != NameToId.end())
67return It->second;
68unsigned Id = IdToName.size();
69assert(Id == NameToId.size() &&"ID collision");
70 IdToName.emplace_back(Name.str());
71 NameToId[IdToName.back()] = Id;
72return Id;
73}
74
75std::optional<std::string>StableFunctionMap::getNameForId(unsigned Id) const{
76if (Id >= IdToName.size())
77return std::nullopt;
78return IdToName[Id];
79}
80
81voidStableFunctionMap::insert(constStableFunction &Func) {
82assert(!Finalized &&"Cannot insert after finalization");
83auto FuncNameId =getIdOrCreateForName(Func.FunctionName);
84auto ModuleNameId =getIdOrCreateForName(Func.ModuleName);
85auto IndexOperandHashMap = std::make_unique<IndexOperandHashMapType>();
86for (auto &[Index, Hash] : Func.IndexOperandHashes)
87 (*IndexOperandHashMap)[Index] = Hash;
88auto FuncEntry = std::make_unique<StableFunctionEntry>(
89 Func.Hash, FuncNameId, ModuleNameId, Func.InstCount,
90 std::move(IndexOperandHashMap));
91insert(std::move(FuncEntry));
92}
93
94voidStableFunctionMap::merge(constStableFunctionMap &OtherMap) {
95assert(!Finalized &&"Cannot merge after finalization");
96for (auto &[Hash, Funcs] : OtherMap.HashToFuncs) {
97auto &ThisFuncs = HashToFuncs[Hash];
98for (auto &Func : Funcs) {
99auto FuncNameId =
100getIdOrCreateForName(*OtherMap.getNameForId(Func->FunctionNameId));
101auto ModuleNameId =
102getIdOrCreateForName(*OtherMap.getNameForId(Func->ModuleNameId));
103auto ClonedIndexOperandHashMap =
104 std::make_unique<IndexOperandHashMapType>(*Func->IndexOperandHashMap);
105 ThisFuncs.emplace_back(std::make_unique<StableFunctionEntry>(
106 Func->Hash, FuncNameId, ModuleNameId, Func->InstCount,
107 std::move(ClonedIndexOperandHashMap)));
108 }
109 }
110}
111
112size_tStableFunctionMap::size(SizeTypeType) const{
113switch (Type) {
114caseUniqueHashCount:
115return HashToFuncs.size();
116caseTotalFunctionCount: {
117size_t Count = 0;
118for (auto &Funcs : HashToFuncs)
119 Count += Funcs.second.size();
120return Count;
121 }
122caseMergeableFunctionCount: {
123size_t Count = 0;
124for (auto &[Hash, Funcs] : HashToFuncs)
125if (Funcs.size() >= 2)
126 Count += Funcs.size();
127return Count;
128 }
129 }
130llvm_unreachable("Unhandled size type");
131}
132
133usingParamLocs =SmallVector<IndexPair>;
134staticvoidremoveIdenticalIndexPair(
135SmallVector<std::unique_ptr<StableFunctionMap::StableFunctionEntry>> &SFS) {
136auto &RSF = SFS[0];
137unsigned StableFunctionCount = SFS.size();
138
139SmallVector<IndexPair> ToDelete;
140for (auto &[Pair, Hash] : *(RSF->IndexOperandHashMap)) {
141bool Identical =true;
142for (unsigned J = 1; J < StableFunctionCount; ++J) {
143auto &SF = SFS[J];
144constauto &SHash = SF->IndexOperandHashMap->at(Pair);
145if (Hash != SHash) {
146 Identical =false;
147break;
148 }
149 }
150
151// No need to parameterize them if the hashes are identical across stable
152// functions.
153if (Identical)
154 ToDelete.emplace_back(Pair);
155 }
156
157for (auto &Pair : ToDelete)
158for (auto &SF : SFS)
159 SF->IndexOperandHashMap->erase(Pair);
160}
161
162staticboolisProfitable(
163constSmallVector<std::unique_ptr<StableFunctionMap::StableFunctionEntry>>
164 &SFS) {
165unsigned StableFunctionCount = SFS.size();
166if (StableFunctionCount <GlobalMergingMinMerges)
167returnfalse;
168
169unsigned InstCount = SFS[0]->InstCount;
170if (InstCount <GlobalMergingMinInstrs)
171returnfalse;
172
173doubleCost = 0.0;
174SmallSet<stable_hash, 8> UniqueHashVals;
175for (auto &SF : SFS) {
176 UniqueHashVals.clear();
177for (auto &[IndexPair, Hash] : *SF->IndexOperandHashMap)
178 UniqueHashVals.insert(Hash);
179unsigned ParamCount = UniqueHashVals.size();
180if (ParamCount >GlobalMergingMaxParams)
181returnfalse;
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.
187if (GlobalMergingSkipNoParams && ParamCount == 0)
188returnfalse;
189Cost += ParamCount *GlobalMergingParamOverhead +GlobalMergingCallOverhead;
190 }
191Cost +=GlobalMergingExtraThreshold;
192
193double Benefit =
194 InstCount * (StableFunctionCount - 1) *GlobalMergingInstOverhead;
195bool Result = Benefit >Cost;
196LLVM_DEBUG(dbgs() <<"isProfitable: Hash = " << SFS[0]->Hash <<", "
197 <<"StableFunctionCount = " << StableFunctionCount
198 <<", InstCount = " << InstCount
199 <<", Benefit = " << Benefit <<", Cost = " <<Cost
200 <<", Result = " << (Result ?"true" :"false") <<"\n");
201return Result;
202}
203
204voidStableFunctionMap::finalize(bool SkipTrim) {
205for (auto It = HashToFuncs.begin(); It != HashToFuncs.end(); ++It) {
206auto &[StableHash, SFS] = *It;
207
208// Group stable functions by ModuleIdentifier.
209 std::stable_sort(SFS.begin(), SFS.end(),
210 [&](const std::unique_ptr<StableFunctionEntry> &L,
211const std::unique_ptr<StableFunctionEntry> &R) {
212 return *getNameForId(L->ModuleNameId) <
213 *getNameForId(R->ModuleNameId);
214 });
215
216// Consider the first function as the root function.
217auto &RSF = SFS[0];
218
219boolInvalid =false;
220unsigned StableFunctionCount = SFS.size();
221for (unsignedI = 1;I < StableFunctionCount; ++I) {
222auto &SF = SFS[I];
223assert(RSF->Hash == SF->Hash);
224if (RSF->InstCount != SF->InstCount) {
225Invalid =true;
226break;
227 }
228if (RSF->IndexOperandHashMap->size() != SF->IndexOperandHashMap->size()) {
229Invalid =true;
230break;
231 }
232for (auto &P : *RSF->IndexOperandHashMap) {
233auto &InstOpndIndex =P.first;
234if (!SF->IndexOperandHashMap->count(InstOpndIndex)) {
235Invalid =true;
236break;
237 }
238 }
239 }
240if (Invalid) {
241 HashToFuncs.erase(It);
242continue;
243 }
244
245if (SkipTrim)
246continue;
247
248// Trim the index pair that has the same operand hash across
249// stable functions.
250removeIdenticalIndexPair(SFS);
251
252if (!isProfitable(SFS))
253 HashToFuncs.erase(It);
254 }
255
256 Finalized =true;
257}
CommandLine.h
Debug.h
LLVM_DEBUG
#define LLVM_DEBUG(...)
Definition:Debug.h:106
Name
std::string Name
Definition:ELFObjHandler.cpp:77
I
#define I(x, y, z)
Definition:MD5.cpp:58
P
#define P(N)
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SmallSet.h
This file defines the SmallSet class.
isProfitable
static bool isProfitable(const SmallVector< std::unique_ptr< StableFunctionMap::StableFunctionEntry > > &SFS)
Definition:StableFunctionMap.cpp:162
removeIdenticalIndexPair
static void removeIdenticalIndexPair(SmallVector< std::unique_ptr< StableFunctionMap::StableFunctionEntry > > &SFS)
Definition:StableFunctionMap.cpp:134
GlobalMergingSkipNoParams
static cl::opt< bool > GlobalMergingSkipNoParams("global-merging-skip-no-params", cl::desc("Skip merging functions with no parameters."), cl::init(true), cl::Hidden)
GlobalMergingParamOverhead
static cl::opt< double > GlobalMergingParamOverhead("global-merging-param-overhead", cl::desc("The overhead cost associated with each parameter when merging " "functions."), cl::init(2.0), cl::Hidden)
GlobalMergingMinMerges
static cl::opt< unsigned > GlobalMergingMinMerges("global-merging-min-merges", cl::desc("Minimum number of similar functions with " "the same hash required for merging."), cl::init(2), cl::Hidden)
GlobalMergingInstOverhead
static cl::opt< double > GlobalMergingInstOverhead("global-merging-inst-overhead", cl::desc("The overhead cost associated with each instruction when lowering " "to machine instruction."), cl::init(1.2), cl::Hidden)
GlobalMergingCallOverhead
static cl::opt< double > GlobalMergingCallOverhead("global-merging-call-overhead", cl::desc("The overhead cost associated with each " "function call when merging functions."), cl::init(1.0), cl::Hidden)
GlobalMergingMaxParams
static cl::opt< unsigned > GlobalMergingMaxParams("global-merging-max-params", cl::desc("The maximum number of parameters allowed when merging functions."), cl::init(std::numeric_limits< unsigned >::max()), cl::Hidden)
GlobalMergingMinInstrs
static cl::opt< unsigned > GlobalMergingMinInstrs("global-merging-min-instrs", cl::desc("The minimum instruction count required when merging functions."), cl::init(1), cl::Hidden)
GlobalMergingExtraThreshold
static cl::opt< double > GlobalMergingExtraThreshold("global-merging-extra-threshold", cl::desc("An additional cost threshold that must be exceeded for merging " "to be considered beneficial."), cl::init(0.0), cl::Hidden)
StableFunctionMap.h
llvm::DenseMapBase::erase
bool erase(const KeyT &Val)
Definition:DenseMap.h:321
llvm::DenseMapBase::size
unsigned size() const
Definition:DenseMap.h:99
llvm::DenseMapBase::begin
iterator begin()
Definition:DenseMap.h:75
llvm::DenseMapBase::end
iterator end()
Definition:DenseMap.h:84
llvm::InstructionCost
Definition:InstructionCost.h:29
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition:SmallSet.h:132
llvm::SmallSet::clear
void clear()
Definition:SmallSet.h:204
llvm::SmallSet::insert
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition:SmallSet.h:181
llvm::SmallSet::size
size_type size() const
Definition:SmallSet.h:170
llvm::SmallVectorBase::size
size_t size() const
Definition:SmallVector.h:78
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition:SmallVector.h:937
llvm::SmallVectorTemplateCommon::back
reference back()
Definition:SmallVector.h:308
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition:SmallVector.h:1196
llvm::StringMapImpl::size
unsigned size() const
Definition:StringMap.h:104
llvm::StringMap::end
iterator end()
Definition:StringMap.h:220
llvm::StringMap::find
iterator find(StringRef Key)
Definition:StringMap.h:233
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition:StringRef.h:51
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition:Type.h:45
llvm::cl::opt
Definition:CommandLine.h:1423
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition:ErrorHandling.h:143
llvm::cl::Hidden
@ Hidden
Definition:CommandLine.h:137
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition:CommandLine.h:443
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition:AddressRanges.h:18
llvm::IndexPair
std::pair< unsigned, unsigned > IndexPair
The pair of an instruction index and a operand index.
Definition:StructuralHash.h:44
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition:Debug.cpp:163
llvm::Cost
InstructionCost Cost
Definition:FunctionSpecialization.h:102
llvm::Invalid
@ Invalid
Definition:PGOCtxProfWriter.h:22
llvm::StableFunctionMap
Definition:StableFunctionMap.h:51
llvm::StableFunctionMap::finalize
void finalize(bool SkipTrim=false)
Finalize the stable function map by trimming content.
Definition:StableFunctionMap.cpp:204
llvm::StableFunctionMap::size
size_t size(SizeType Type=UniqueHashCount) const
Definition:StableFunctionMap.cpp:112
llvm::StableFunctionMap::insert
void insert(const StableFunction &Func)
Insert a StableFunction object into the function map.
Definition:StableFunctionMap.cpp:81
llvm::StableFunctionMap::merge
void merge(const StableFunctionMap &OtherMap)
Merge a OtherMap into this function map.
Definition:StableFunctionMap.cpp:94
llvm::StableFunctionMap::getNameForId
std::optional< std::string > getNameForId(unsigned Id) const
Get the name associated with a given ID.
Definition:StableFunctionMap.cpp:75
llvm::StableFunctionMap::getIdOrCreateForName
unsigned getIdOrCreateForName(StringRef Name)
Get an existing ID associated with the given name or create a new ID if it doesn't exist.
Definition:StableFunctionMap.cpp:64
llvm::StableFunctionMap::SizeType
SizeType
Definition:StableFunctionMap.h:101
llvm::StableFunctionMap::MergeableFunctionCount
@ MergeableFunctionCount
Definition:StableFunctionMap.h:104
llvm::StableFunctionMap::UniqueHashCount
@ UniqueHashCount
Definition:StableFunctionMap.h:102
llvm::StableFunctionMap::TotalFunctionCount
@ TotalFunctionCount
Definition:StableFunctionMap.h:103
llvm::StableFunction
A stable function is a function with a stable hash while tracking the locations of ignored operands a...
Definition:StableFunctionMap.h:30
llvm::cl::desc
Definition:CommandLine.h:409
Generated on Fri Jul 18 2025 10:26:11 for LLVM by doxygen 1.9.6
[8]ページ先頭
©2009-2025 Movatter.jp