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
16namespace llvm {
17class MCDecodedPseudoProbeInlineTree;
18
19namespace bolt {
20
21class YAMLProfileReader : public ProfileReaderBase {
22public:
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
159private:
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

source code of bolt/include/bolt/Profile/YAMLProfileReader.h