1 | //===- bolt/Profile/YAMLProfileReader.h - YAML profile reader ---*- 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 | #ifndef BOLT_PROFILE_YAML_PROFILE_READER_H |
10 | #define BOLT_PROFILE_YAML_PROFILE_READER_H |
11 | |
12 | #include "bolt/Profile/ProfileReaderBase.h" |
13 | #include "bolt/Profile/ProfileYAMLMapping.h" |
14 | #include <unordered_set> |
15 | |
16 | namespace llvm { |
17 | class MCDecodedPseudoProbeInlineTree; |
18 | |
19 | namespace bolt { |
20 | |
21 | class YAMLProfileReader : public ProfileReaderBase { |
22 | public: |
23 | explicit YAMLProfileReader(StringRef Filename) |
24 | : ProfileReaderBase(Filename) {} |
25 | |
26 | StringRef getReaderName() const override { return "YAML profile reader" ; } |
27 | |
28 | bool isTrustedSource() const override { return false; } |
29 | |
30 | Error readProfilePreCFG(BinaryContext &BC) override { |
31 | return Error::success(); |
32 | } |
33 | |
34 | Error readProfile(BinaryContext &BC) override; |
35 | |
36 | Error preprocessProfile(BinaryContext &BC) override; |
37 | |
38 | bool hasLocalsWithFileName() const override; |
39 | |
40 | bool mayHaveProfileData(const BinaryFunction &BF) override; |
41 | |
42 | /// Check if the file contains YAML. |
43 | static bool isYAML(StringRef Filename); |
44 | |
45 | using ProfileLookupMap = |
46 | DenseMap<uint32_t, yaml::bolt::BinaryFunctionProfile *>; |
47 | |
48 | using GUIDInlineTreeMap = |
49 | std::unordered_map<uint64_t, const MCDecodedPseudoProbeInlineTree *>; |
50 | |
51 | /// A class for matching binary functions in functions in the YAML profile. |
52 | /// First, a call graph is constructed for both profiled and binary functions. |
53 | /// Then functions are hashed based on the names of their callee/caller |
54 | /// functions. Finally, functions are matched based on these neighbor hashes. |
55 | class CallGraphMatcher { |
56 | public: |
57 | /// Constructs the call graphs for binary and profiled functions and |
58 | /// computes neighbor hashes for binary functions. |
59 | CallGraphMatcher(BinaryContext &BC, yaml::bolt::BinaryProfile &YamlBP, |
60 | ProfileLookupMap &IdToYAMLBF); |
61 | |
62 | /// Returns the YamlBFs adjacent to the parameter YamlBF in the call graph. |
63 | std::optional<std::set<yaml::bolt::BinaryFunctionProfile *>> |
64 | getAdjacentYamlBFs(yaml::bolt::BinaryFunctionProfile &YamlBF) { |
65 | auto It = YamlBFAdjacencyMap.find(Val: &YamlBF); |
66 | return It == YamlBFAdjacencyMap.end() ? std::nullopt |
67 | : std::make_optional(t&: It->second); |
68 | } |
69 | |
70 | /// Returns the binary functions with the parameter neighbor hash. |
71 | std::optional<std::vector<BinaryFunction *>> |
72 | getBFsWithNeighborHash(uint64_t NeighborHash) { |
73 | auto It = NeighborHashToBFs.find(Val: NeighborHash); |
74 | return It == NeighborHashToBFs.end() ? std::nullopt |
75 | : std::make_optional(t&: It->second); |
76 | } |
77 | |
78 | private: |
79 | /// Adds edges to the binary function call graph given the callsites of the |
80 | /// parameter function. |
81 | void constructBFCG(BinaryContext &BC, yaml::bolt::BinaryProfile &YamlBP); |
82 | |
83 | /// Using the constructed binary function call graph, computes and creates |
84 | /// mappings from "neighbor hash" (composed of the function names of callee |
85 | /// and caller functions of a function) to binary functions. |
86 | void computeBFNeighborHashes(BinaryContext &BC); |
87 | |
88 | /// Constructs the call graph for profile functions. |
89 | void constructYAMLFCG(yaml::bolt::BinaryProfile &YamlBP, |
90 | ProfileLookupMap &IdToYAMLBF); |
91 | |
92 | /// Adjacency map for binary functions in the call graph. |
93 | DenseMap<BinaryFunction *, std::set<BinaryFunction *>> BFAdjacencyMap; |
94 | |
95 | /// Maps neighbor hashes to binary functions. |
96 | DenseMap<uint64_t, std::vector<BinaryFunction *>> NeighborHashToBFs; |
97 | |
98 | /// Adjacency map for profile functions in the call graph. |
99 | DenseMap<yaml::bolt::BinaryFunctionProfile *, |
100 | std::set<yaml::bolt::BinaryFunctionProfile *>> |
101 | YamlBFAdjacencyMap; |
102 | }; |
103 | |
104 | // A class for matching inline tree nodes between profile and binary. |
105 | // Provides the mapping from profile inline tree node id to a |
106 | // corresponding binary MCDecodedPseudoProbeInlineTree node. |
107 | // |
108 | // The whole mapping process is the following: |
109 | // |
110 | // (profile) (binary) |
111 | // | blocks ^ |
112 | // v | |
113 | // yaml::bolt::BinaryBasicBlockProfile ~= FlowBlock |
114 | // ||| probes ^ (majority vote) |
115 | // v ||| BBPseudoProbeToBlock |
116 | // yaml::bolt::PseudoProbeInfo MCDecodedPseudoProbe |
117 | // | InlineTreeIndex ^ |
118 | // v | probe id |
119 | // [ profile node id (uint32_t) -> MCDecodedPseudoProbeInlineTree *] |
120 | // InlineTreeNodeMapTy |
121 | class InlineTreeNodeMapTy { |
122 | DenseMap<uint32_t, const MCDecodedPseudoProbeInlineTree *> Map; |
123 | |
124 | void mapInlineTreeNode(uint32_t ProfileNodeIdx, |
125 | const MCDecodedPseudoProbeInlineTree *BinaryNode) { |
126 | auto Res = Map.try_emplace(Key: ProfileNodeIdx, Args&: BinaryNode); |
127 | assert(Res.second && |
128 | "Duplicate mapping from profile node index to binary inline tree" ); |
129 | (void)Res; |
130 | } |
131 | |
132 | public: |
133 | /// Returns matched InlineTree * for a given profile inline_tree_id. |
134 | const MCDecodedPseudoProbeInlineTree * |
135 | getInlineTreeNode(uint32_t ProfileInlineTreeNodeId) const { |
136 | auto It = Map.find(Val: ProfileInlineTreeNodeId); |
137 | if (It == Map.end()) |
138 | return nullptr; |
139 | return It->second; |
140 | } |
141 | |
142 | // Match up \p YamlInlineTree with binary inline tree rooted at \p Root. |
143 | // Return the number of matched nodes. |
144 | // |
145 | // This function populates the mapping from profile inline tree node id to a |
146 | // corresponding binary MCDecodedPseudoProbeInlineTree node. |
147 | size_t matchInlineTrees( |
148 | const MCPseudoProbeDecoder &Decoder, |
149 | const std::vector<yaml::bolt::InlineTreeNode> &YamlInlineTree, |
150 | const MCDecodedPseudoProbeInlineTree *Root); |
151 | }; |
152 | |
153 | // Partial probe matching specification: matched inline tree and corresponding |
154 | // BinaryFunctionProfile |
155 | using ProbeMatchSpec = |
156 | std::pair<InlineTreeNodeMapTy, |
157 | std::reference_wrapper<yaml::bolt::BinaryFunctionProfile>>; |
158 | |
159 | private: |
160 | /// Adjustments for basic samples profiles (without LBR). |
161 | bool NormalizeByInsnCount{false}; |
162 | bool NormalizeByCalls{false}; |
163 | |
164 | /// Binary profile in YAML format. |
165 | yaml::bolt::BinaryProfile YamlBP; |
166 | |
167 | /// Map a function ID from a YAML profile to a BinaryFunction object. |
168 | DenseMap<uint32_t, BinaryFunction *> YamlProfileToFunction; |
169 | |
170 | using FunctionSet = std::unordered_set<const BinaryFunction *>; |
171 | /// To keep track of functions that have a matched profile before the profile |
172 | /// is attributed. |
173 | FunctionSet ProfiledFunctions; |
174 | |
175 | /// Maps profiled function id to function, for function matching with calls as |
176 | /// anchors. |
177 | ProfileLookupMap IdToYamLBF; |
178 | |
179 | /// For LTO symbol resolution. |
180 | /// Map a common LTO prefix to a list of YAML profiles matching the prefix. |
181 | StringMap<std::vector<yaml::bolt::BinaryFunctionProfile *>> LTOCommonNameMap; |
182 | |
183 | /// Map a common LTO prefix to a set of binary functions. |
184 | StringMap<std::unordered_set<BinaryFunction *>> LTOCommonNameFunctionMap; |
185 | |
186 | /// Function names in profile. |
187 | StringSet<> ProfileFunctionNames; |
188 | |
189 | /// BinaryFunction pointers indexed by YamlBP functions. |
190 | std::vector<BinaryFunction *> ProfileBFs; |
191 | |
192 | // Pseudo probe function GUID to inline tree node |
193 | GUIDInlineTreeMap TopLevelGUIDToInlineTree; |
194 | |
195 | // Mapping from a binary function to its partial match specification |
196 | // (YAML profile and its inline tree mapping to binary). |
197 | DenseMap<BinaryFunction *, std::vector<ProbeMatchSpec>> BFToProbeMatchSpecs; |
198 | |
199 | /// Populate \p Function profile with the one supplied in YAML format. |
200 | bool parseFunctionProfile(BinaryFunction &Function, |
201 | const yaml::bolt::BinaryFunctionProfile &YamlBF); |
202 | |
203 | /// Checks if a function profile matches a binary function. |
204 | bool profileMatches(const yaml::bolt::BinaryFunctionProfile &Profile, |
205 | const BinaryFunction &BF); |
206 | |
207 | /// Infer function profile from stale data (collected on older binaries). |
208 | bool inferStaleProfile(BinaryFunction &Function, |
209 | const yaml::bolt::BinaryFunctionProfile &YamlBF, |
210 | const ArrayRef<ProbeMatchSpec> ProbeMatchSpecs); |
211 | |
212 | /// Initialize maps for profile matching. |
213 | void buildNameMaps(BinaryContext &BC); |
214 | |
215 | /// Matches functions using exact name. |
216 | size_t matchWithExactName(); |
217 | |
218 | /// Matches function using LTO comomon name. |
219 | size_t matchWithLTOCommonName(); |
220 | |
221 | /// Matches functions using exact hash. |
222 | size_t matchWithHash(BinaryContext &BC); |
223 | |
224 | /// Matches functions using the call graph. |
225 | size_t matchWithCallGraph(BinaryContext &BC); |
226 | |
227 | /// Matches functions using the call graph. |
228 | /// Populates BF->partial probe match spec map. |
229 | size_t matchWithPseudoProbes(BinaryContext &BC); |
230 | |
231 | /// Matches functions with similarly named profiled functions. |
232 | size_t matchWithNameSimilarity(BinaryContext &BC); |
233 | |
234 | /// Update matched YAML -> BinaryFunction pair. |
235 | void matchProfileToFunction(yaml::bolt::BinaryFunctionProfile &YamlBF, |
236 | BinaryFunction &BF) { |
237 | YamlProfileToFunction[YamlBF.Id] = &BF; |
238 | YamlBF.Used = true; |
239 | |
240 | assert(!ProfiledFunctions.count(&BF) && |
241 | "function already has an assigned profile" ); |
242 | ProfiledFunctions.emplace(args: &BF); |
243 | } |
244 | |
245 | /// Check if the profile uses an event with a given \p Name. |
246 | bool usesEvent(StringRef Name) const; |
247 | }; |
248 | |
249 | } // namespace bolt |
250 | } // namespace llvm |
251 | |
252 | #endif |
253 | |