LLVM 24.0.0git
SampleProfileMatcher.h
Go to the documentation of this file.
1//===- Transforms/IPO/SampleProfileMatcher.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/// \file
10/// This file provides the interface for SampleProfileMatcher.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_TRANSFORMS_IPO_SAMPLEPROFILEMATCHER_H
15#define LLVM_TRANSFORMS_IPO_SAMPLEPROFILEMATCHER_H
16
17#include "llvm/ADT/DenseMap.h"
18#include "llvm/ADT/DenseSet.h"
19#include "llvm/ADT/MapVector.h"
20#include "llvm/ADT/StringSet.h"
22
23namespace llvm {
24
25struct IPOOptions;
26
27using AnchorList = std::vector<std::pair<LineLocation, FunctionId>>;
28using AnchorMap = std::map<LineLocation, FunctionId>;
29
30// Sample profile matching - fuzzy match.
32 const IPOOptions &Opts;
33 // -salvage-stale-profile and -salvage-unused-profile, resolved by the loader.
34 bool SalvageStaleProfile;
35 bool SalvageUnusedProfile;
36 Module &M;
37 SampleProfileReader &Reader;
38 LazyCallGraph &CG;
39 const PseudoProbeManager *ProbeManager;
40 const ThinOrFullLTOPhase LTOPhase;
41 SampleProfileMap FlattenedProfiles;
42 // For each function, the matcher generates a map, of which each entry is a
43 // mapping from the source location of current build to the source location
44 // in the profile.
45 StringMap<LocToLocMap> FuncMappings;
46 // Hash mapping cache for matched anchor pairs in stale profile matching
48
49 // Match state for an anchor/callsite.
50 enum class MatchState {
51 Unknown = 0,
52 // Initial match between input profile and current IR.
53 InitialMatch = 1,
54 // Initial mismatch between input profile and current IR.
55 InitialMismatch = 2,
56 // InitialMatch stays matched after fuzzy profile matching.
57 UnchangedMatch = 3,
58 // InitialMismatch stays mismatched after fuzzy profile matching.
59 UnchangedMismatch = 4,
60 // InitialMismatch is recovered after fuzzy profile matching.
61 RecoveredMismatch = 5,
62 // InitialMatch is removed and becomes mismatched after fuzzy profile
63 // matching.
64 RemovedMatch = 6,
65 };
66
67 // For each function, store every callsite and its matching state into this
68 // map, of which each entry is a pair of callsite location and MatchState.
69 // This is used for profile staleness computation and report.
70 StringMap<DenseMap<LineLocation, MatchState>> FuncCallsiteMatchStates;
71
72 // A map from a pair of function and profile name to a boolean value
73 // indicating whether they are matched. This is used as a cache for the
74 // matching result.
75 DenseMap<std::pair<const Function *, FunctionId>, bool> FuncProfileMatchCache;
76 // The new functions found by the call graph matching. The map's key is the
77 // the new(renamed) function pointer and the value is old(unused) profile
78 // name.
79 MapVector<Function *, FunctionId> FuncToProfileNameMap;
80
81 // A map pointer to the FuncNameToProfNameMap in SampleProfileLoader,
82 // which maps the function name to the matched profile name. This is used
83 // for sample loader to look up profile using the new name.
85
86 // A map pointer to the SymbolMap in SampleProfileLoader, which stores all
87 // the original matched symbols before the matching. this is to determine if
88 // the profile is unused(to be matched) or not.
90
91 // The new functions from IR.
93
94 // Pointer to the Profile Symbol List in the reader.
95 std::shared_ptr<ProfileSymbolList> PSL;
96
97 // Profile mismatch statstics:
98 uint64_t TotalProfiledFunc = 0;
99 // Num of checksum-mismatched function.
100 uint64_t NumStaleProfileFunc = 0;
101 uint64_t TotalProfiledCallsites = 0;
102 uint64_t NumMismatchedCallsites = 0;
103 uint64_t NumRecoveredCallsites = 0;
104 // Total samples for all profiled functions.
105 uint64_t TotalFunctionSamples = 0;
106 // Total samples for all checksum-mismatched functions.
107 uint64_t MismatchedFunctionSamples = 0;
108 uint64_t MismatchedCallsiteSamples = 0;
109 uint64_t RecoveredCallsiteSamples = 0;
110
111 // Profile call-graph matching statstics:
112 uint64_t NumCallGraphRecoveredProfiledFunc = 0;
113 uint64_t NumCallGraphRecoveredFuncSamples = 0;
114
115 // A dummy name for unknown indirect callee, used to differentiate from a
116 // non-call instruction that also has an empty callee name.
117 static constexpr const char *UnknownIndirectCallee =
118 "unknown.indirect.callee";
119
120public:
122 const IPOOptions &Opts, Module &M, SampleProfileReader &Reader,
123 LazyCallGraph &CG, const PseudoProbeManager *ProbeManager,
124 ThinOrFullLTOPhase LTOPhase,
126 std::shared_ptr<ProfileSymbolList> PSL,
128 bool SalvageStaleProfile, bool SalvageUnusedProfile)
129 : Opts(Opts), SalvageStaleProfile(SalvageStaleProfile),
130 SalvageUnusedProfile(SalvageUnusedProfile), M(M), Reader(Reader),
131 CG(CG), ProbeManager(ProbeManager), LTOPhase(LTOPhase),
132 FuncNameToProfNameMap(&FuncNameToProfNameMap), SymbolMap(&SymMap),
133 PSL(PSL) {};
134 LLVM_ABI void runOnModule();
136 // Do not clear FuncMappings, it stores IRLoc to ProfLoc remappings which
137 // will be used for sample loader.
138 // Do not clear FlattenedProfiles as it contains function names referenced
139 // by FuncNameToProfNameMap. Clearing this memory could lead to a
140 // use-after-free error.
141 freeContainer(FuncCallsiteMatchStates);
142 freeContainer(FunctionsWithoutProfile);
143 freeContainer(FuncToProfileNameMap);
144 }
145
146private:
147 FunctionSamples *getFlattenedSamplesFor(const FunctionId &Fname) {
148 auto It = FlattenedProfiles.find(Fname);
149 if (It != FlattenedProfiles.end())
150 return &It->second;
151 return nullptr;
152 }
153 FunctionSamples *getFlattenedSamplesFor(const Function &F) {
154 StringRef CanonFName = FunctionSamples::getCanonicalFnName(F);
155 return getFlattenedSamplesFor(FunctionId(CanonFName));
156 }
157 template <typename T> inline void freeContainer(T &C) {
158 T Empty;
159 std::swap(C, Empty);
160 }
161 void getFilteredAnchorList(const AnchorMap &IRAnchors,
162 const AnchorMap &ProfileAnchors,
163 AnchorList &FilteredIRAnchorsList,
164 AnchorList &FilteredProfileAnchorList);
165 void runOnFunction(Function &F);
166 void findIRAnchors(const Function &F, AnchorMap &IRAnchors) const;
167 void findProfileAnchors(const FunctionSamples &FS,
168 AnchorMap &ProfileAnchors) const;
169 bool anchorsMatch(const FunctionId &IRAnchor,
170 const FunctionId &ProfileAnchor) const;
171 // Record the callsite match states for profile staleness report, the result
172 // is saved in FuncCallsiteMatchStates.
173 void recordCallsiteMatchStates(const Function &F, const AnchorMap &IRAnchors,
174 const AnchorMap &ProfileAnchors,
175 const LocToLocMap *IRToProfileLocationMap);
176
177 bool isMismatchState(const enum MatchState &State) {
178 return State == MatchState::InitialMismatch ||
179 State == MatchState::UnchangedMismatch ||
180 State == MatchState::RemovedMatch;
181 };
182
183 bool isInitialState(const enum MatchState &State) {
184 return State == MatchState::InitialMatch ||
185 State == MatchState::InitialMismatch;
186 };
187
188 bool isFinalState(const enum MatchState &State) {
189 return State == MatchState::UnchangedMatch ||
190 State == MatchState::UnchangedMismatch ||
191 State == MatchState::RecoveredMismatch ||
192 State == MatchState::RemovedMatch;
193 };
194
195 void
196 countCallGraphRecoveredSamples(const FunctionSamples &FS,
197 DenseSet<FunctionId> &MatchedUnusedProfile);
198 // Count the samples of checksum mismatched function for the top-level
199 // function and all inlinees.
200 void countMismatchedFuncSamples(const FunctionSamples &FS, bool IsTopLevel);
201 // Count the number of mismatched or recovered callsites.
202 void countMismatchCallsites(const FunctionSamples &FS);
203 // Count the samples of mismatched or recovered callsites for top-level
204 // function and all inlinees.
205 void countMismatchedCallsiteSamples(const FunctionSamples &FS);
206 void computeAndReportProfileStaleness();
207 void UpdateWithSalvagedProfiles();
208
209 LocToLocMap &getIRToProfileLocationMap(const FunctionSamples &FS) {
210 return FuncMappings[FS.getFuncName()];
211 }
212 void distributeIRToProfileLocationMap();
213 void distributeIRToProfileLocationMap(FunctionSamples &FS);
214 LocToLocMap longestCommonSequence(const AnchorList &IRCallsiteAnchors,
215 const AnchorList &ProfileCallsiteAnchors,
216 bool MatchUnusedFunction);
217 void matchNonCallsiteLocs(const LocToLocMap &AnchorMatchings,
218 const AnchorMap &IRAnchors,
219 LocToLocMap &IRToProfileLocationMap);
220 void runStaleProfileMatching(const Function &F, const AnchorMap &IRAnchors,
221 const AnchorMap &ProfileAnchors,
222 LocToLocMap &IRToProfileLocationMap,
223 bool RunCFGMatching, bool RunCGMatching);
224 // If the function doesn't have profile, return the pointer to the function.
225 bool functionHasProfile(const FunctionId &IRFuncName,
226 Function *&FuncWithoutProfile);
227 bool isProfileUnused(const FunctionId &ProfileFuncName);
228 bool functionMatchesProfileHelper(const Function &IRFunc,
229 const FunctionId &ProfFunc);
230 // Determine if the function matches profile. If FindMatchedProfileOnly is
231 // set, only search the existing matched function. Otherwise, try matching the
232 // two functions.
233 bool functionMatchesProfile(const FunctionId &IRFuncName,
234 const FunctionId &ProfileFuncName,
235 bool FindMatchedProfileOnly);
236 // Determine if the function matches profile by computing a similarity ratio
237 // between two sequences of callsite anchors extracted from function and
238 // profile. If it's above the threshold, the function matches the profile.
239 bool functionMatchesProfile(Function &IRFunc, const FunctionId &ProfFunc,
240 bool FindMatchedProfileOnly);
241 // Find functions that don't show in the profile or profile symbol list,
242 // which are supposed to be new functions. We use them as the targets for
243 // call graph matching.
244 void findFunctionsWithoutProfile();
245 // Match orphan IR functions to unused top-level profile entries by demangled
246 // basename, without requiring a matched caller in the call graph.
247 void matchFunctionsWithoutProfileByBasename();
248};
249} // end namespace llvm
250#endif // LLVM_TRANSFORMS_IPO_SAMPLEPROFILEMATCHER_H
uint64_t uint64_t
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
#define LLVM_ABI
Definition Compiler.h:211
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
#define F(x, y, z)
Definition MD5.cpp:54
This file implements a map that provides insertion order iteration.
#define T
This file provides the interface for the sampled PGO profile loader base implementation.
StringSet - A set-like wrapper for the StringMap.
LocallyHashedType DenseMapInfo< LocallyHashedType >::Empty
A lazily constructed view of the call graph of a module.
This class implements a map that also provides access to all stored values in a deterministic order.
Definition MapVector.h:39
A Module instance is used to store all the information related to an LLVM module.
Definition Module.h:68
SampleProfileMatcher(const IPOOptions &Opts, Module &M, SampleProfileReader &Reader, LazyCallGraph &CG, const PseudoProbeManager *ProbeManager, ThinOrFullLTOPhase LTOPhase, HashKeyMap< DenseMap, FunctionId, Function * > &SymMap, std::shared_ptr< ProfileSymbolList > PSL, HashKeyMap< DenseMap, FunctionId, FunctionId > &FuncNameToProfNameMap, bool SalvageStaleProfile, bool SalvageUnusedProfile)
StringMap - This is an unconventional map that is specialized for handling keys that are "strings",...
Definition StringMap.h:129
This class represents a function that is read from a sample profile.
Definition FunctionId.h:36
Representation of the samples collected for a function.
Definition SampleProf.h:854
static StringRef getCanonicalFnName(const Function &F)
Return the canonical name for a function, taking into account suffix elision policy attributes.
This class is a wrapper to associative container MapT<KeyT, ValueT> using the hash value of the origi...
Definition HashKeyMap.h:52
This class provides operator overloads to the map container using MD5 as the key type,...
iterator find(const SampleContext &Ctx)
DenseMap< LineLocation, LineLocation > LocToLocMap
Definition SampleProf.h:847
This is an optimization pass for GlobalISel generic memory operations.
std::map< LineLocation, FunctionId > AnchorMap
ThinOrFullLTOPhase
This enumerates the LLVM full LTO or ThinLTO optimization phases.
Definition Pass.h:75
std::vector< std::pair< LineLocation, FunctionId > > AnchorList
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition BitVector.h:881