1 //===-- ProfileGenerator.cpp - Profile Generator ---------------*- 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 #include "ProfileGenerator.h"
10
11 static cl::opt<std::string> OutputFilename("output", cl::value_desc("output"),
12 cl::Required,
13 cl::desc("Output profile file"));
14
15 static cl::opt<SampleProfileFormat> OutputFormat(
16 "format", cl::desc("Format of output profile"), cl::init(SPF_Text),
17 cl::values(
18 clEnumValN(SPF_Binary, "binary", "Binary encoding (default)"),
19 clEnumValN(SPF_Compact_Binary, "compbinary", "Compact binary encoding"),
20 clEnumValN(SPF_Ext_Binary, "extbinary", "Extensible binary encoding"),
21 clEnumValN(SPF_Text, "text", "Text encoding"),
22 clEnumValN(SPF_GCC, "gcc",
23 "GCC encoding (only meaningful for -sample)")));
24
25 using namespace llvm;
26 using namespace sampleprof;
27
28 namespace llvm {
29 namespace sampleprof {
30
31 std::unique_ptr<ProfileGenerator>
create(const BinarySampleCounterMap & BinarySampleCounters,enum PerfScriptType SampleType)32 ProfileGenerator::create(const BinarySampleCounterMap &BinarySampleCounters,
33 enum PerfScriptType SampleType) {
34 std::unique_ptr<ProfileGenerator> ProfileGenerator;
35
36 if (SampleType == PERF_LBR_STACK) {
37 ProfileGenerator.reset(new CSProfileGenerator(BinarySampleCounters));
38 } else {
39 // TODO:
40 llvm_unreachable("Unsupported perfscript!");
41 }
42
43 return ProfileGenerator;
44 }
45
write()46 void ProfileGenerator::write() {
47 auto WriterOrErr = SampleProfileWriter::create(OutputFilename, OutputFormat);
48 if (std::error_code EC = WriterOrErr.getError())
49 exitWithError(EC, OutputFilename);
50 auto Writer = std::move(WriterOrErr.get());
51 Writer->write(ProfileMap);
52 }
53
findDisjointRanges(RangeSample & DisjointRanges,const RangeSample & Ranges)54 void ProfileGenerator::findDisjointRanges(RangeSample &DisjointRanges,
55 const RangeSample &Ranges) {
56
57 /*
58 Regions may overlap with each other. Using the boundary info, find all
59 disjoint ranges and their sample count. BoundaryPoint contains the count
60 mutiple samples begin/end at this points.
61
62 |<--100-->| Sample1
63 |<------200------>| Sample2
64 A B C
65
66 In the example above,
67 Sample1 begins at A, ends at B, its value is 100.
68 Sample2 beings at A, ends at C, its value is 200.
69 For A, BeginCount is the sum of sample begins at A, which is 300 and no
70 samples ends at A, so EndCount is 0.
71 Then boundary points A, B, and C with begin/end counts are:
72 A: (300, 0)
73 B: (0, 100)
74 C: (0, 200)
75 */
76 struct BoundaryPoint {
77 // Sum of sample counts beginning at this point
78 uint64_t BeginCount;
79 // Sum of sample counts ending at this point
80 uint64_t EndCount;
81
82 BoundaryPoint() : BeginCount(0), EndCount(0){};
83
84 void addBeginCount(uint64_t Count) { BeginCount += Count; }
85
86 void addEndCount(uint64_t Count) { EndCount += Count; }
87 };
88
89 /*
90 For the above example. With boundary points, follwing logic finds two
91 disjoint region of
92
93 [A,B]: 300
94 [B+1,C]: 200
95
96 If there is a boundary point that both begin and end, the point itself
97 becomes a separate disjoint region. For example, if we have original
98 ranges of
99
100 |<--- 100 --->|
101 |<--- 200 --->|
102 A B C
103
104 there are three boundary points with their begin/end counts of
105
106 A: (100, 0)
107 B: (200, 100)
108 C: (0, 200)
109
110 the disjoint ranges would be
111
112 [A, B-1]: 100
113 [B, B]: 300
114 [B+1, C]: 200.
115 */
116 std::map<uint64_t, BoundaryPoint> Boundaries;
117
118 for (auto Item : Ranges) {
119 uint64_t Begin = Item.first.first;
120 uint64_t End = Item.first.second;
121 uint64_t Count = Item.second;
122 if (Boundaries.find(Begin) == Boundaries.end())
123 Boundaries[Begin] = BoundaryPoint();
124 Boundaries[Begin].addBeginCount(Count);
125
126 if (Boundaries.find(End) == Boundaries.end())
127 Boundaries[End] = BoundaryPoint();
128 Boundaries[End].addEndCount(Count);
129 }
130
131 uint64_t BeginAddress = 0;
132 int Count = 0;
133 for (auto Item : Boundaries) {
134 uint64_t Address = Item.first;
135 BoundaryPoint &Point = Item.second;
136 if (Point.BeginCount) {
137 if (BeginAddress)
138 DisjointRanges[{BeginAddress, Address - 1}] = Count;
139 Count += Point.BeginCount;
140 BeginAddress = Address;
141 }
142 if (Point.EndCount) {
143 assert(BeginAddress && "First boundary point cannot be 'end' point");
144 DisjointRanges[{BeginAddress, Address}] = Count;
145 Count -= Point.EndCount;
146 BeginAddress = Address + 1;
147 }
148 }
149 }
150
151 FunctionSamples &
getFunctionProfileForContext(StringRef ContextStr)152 CSProfileGenerator::getFunctionProfileForContext(StringRef ContextStr) {
153 auto Ret = ProfileMap.try_emplace(ContextStr, FunctionSamples());
154 if (Ret.second) {
155 SampleContext FContext(Ret.first->first(), RawContext);
156 FunctionSamples &FProfile = Ret.first->second;
157 FProfile.setName(FContext.getName());
158 FProfile.setContext(FContext);
159 }
160 return Ret.first->second;
161 }
162
updateBodySamplesforFunctionProfile(FunctionSamples & FunctionProfile,const FrameLocation & LeafLoc,uint64_t Count)163 void CSProfileGenerator::updateBodySamplesforFunctionProfile(
164 FunctionSamples &FunctionProfile, const FrameLocation &LeafLoc,
165 uint64_t Count) {
166 // Filter out invalid negative(int type) lineOffset
167 if (LeafLoc.second.LineOffset & 0x80000000)
168 return;
169 // Use the maximum count of samples with same line location
170 ErrorOr<uint64_t> R = FunctionProfile.findSamplesAt(
171 LeafLoc.second.LineOffset, LeafLoc.second.Discriminator);
172 uint64_t PreviousCount = R ? R.get() : 0;
173 if (PreviousCount < Count) {
174 FunctionProfile.addBodySamples(LeafLoc.second.LineOffset,
175 LeafLoc.second.Discriminator,
176 Count - PreviousCount);
177 FunctionProfile.addTotalSamples(Count - PreviousCount);
178 }
179 }
180
populateFunctionBodySamples()181 void CSProfileGenerator::populateFunctionBodySamples() {
182 for (const auto &BI : BinarySampleCounters) {
183 ProfiledBinary *Binary = BI.first;
184 for (const auto &CI : BI.second.RangeCounter) {
185 StringRef ContextId(CI.first);
186 // Get or create function profile for the range
187 FunctionSamples &FunctionProfile =
188 getFunctionProfileForContext(ContextId);
189 // Compute disjoint ranges first, so we can use MAX
190 // for calculating count for each location.
191 RangeSample Ranges;
192 findDisjointRanges(Ranges, CI.second);
193
194 for (auto Range : Ranges) {
195 uint64_t RangeBegin = Binary->offsetToVirtualAddr(Range.first.first);
196 uint64_t RangeEnd = Binary->offsetToVirtualAddr(Range.first.second);
197 uint64_t Count = Range.second;
198 // Disjoint ranges have introduce zero-filled gap that
199 // doesn't belong to current context, filter them out.
200 if (Count == 0)
201 continue;
202
203 InstructionPointer IP(Binary, RangeBegin, true);
204
205 // Disjoint ranges may have range in the middle of two instr,
206 // e.g. If Instr1 at Addr1, and Instr2 at Addr2, disjoint range
207 // can be Addr1+1 to Addr2-1. We should ignore such range.
208 if (IP.Address > RangeEnd)
209 continue;
210
211 while (IP.Address <= RangeEnd) {
212 uint64_t Offset = Binary->virtualAddrToOffset(IP.Address);
213 const FrameLocation &LeafLoc = Binary->getInlineLeafFrameLoc(Offset);
214 // Recording body sample for this specific context
215 updateBodySamplesforFunctionProfile(FunctionProfile, LeafLoc, Count);
216 // Move to next IP within the range
217 IP.advance();
218 }
219 }
220 }
221 }
222 }
223
populateFunctionBoundarySamples()224 void CSProfileGenerator::populateFunctionBoundarySamples() {
225 for (const auto &BI : BinarySampleCounters) {
226 ProfiledBinary *Binary = BI.first;
227 for (const auto &CI : BI.second.BranchCounter) {
228 StringRef ContextId(CI.first);
229 // Get or create function profile for branch Source
230 FunctionSamples &FunctionProfile =
231 getFunctionProfileForContext(ContextId);
232
233 for (auto Entry : CI.second) {
234 uint64_t SourceOffset = Entry.first.first;
235 uint64_t TargetOffset = Entry.first.second;
236 uint64_t Count = Entry.second;
237 // Get the callee name by branch target if it's a call branch
238 StringRef CalleeName = FunctionSamples::getCanonicalFnName(
239 Binary->getFuncFromStartOffset(TargetOffset));
240 if (CalleeName.size() == 0)
241 continue;
242
243 // Record called target sample and its count
244 const FrameLocation &LeafLoc =
245 Binary->getInlineLeafFrameLoc(SourceOffset);
246
247 FunctionProfile.addCalledTargetSamples(LeafLoc.second.LineOffset,
248 LeafLoc.second.Discriminator,
249 CalleeName, Count);
250 FunctionProfile.addTotalSamples(Count);
251
252 // Record head sample for called target(callee)
253 // TODO: Cleanup ' @ '
254 std::string CalleeContextId =
255 getCallSite(LeafLoc) + " @ " + CalleeName.str();
256 if (ContextId.find(" @ ") != StringRef::npos) {
257 CalleeContextId =
258 ContextId.rsplit(" @ ").first.str() + " @ " + CalleeContextId;
259 }
260
261 if (ProfileMap.find(CalleeContextId) != ProfileMap.end()) {
262 FunctionSamples &CalleeProfile = ProfileMap[CalleeContextId];
263 assert(Count != 0 && "Unexpected zero weight branch");
264 if (CalleeProfile.getName().size()) {
265 CalleeProfile.addHeadSamples(Count);
266 }
267 }
268 }
269 }
270 }
271 }
272
getCallerContext(StringRef CalleeContext,StringRef & CallerNameWithContext)273 static FrameLocation getCallerContext(StringRef CalleeContext,
274 StringRef &CallerNameWithContext) {
275 StringRef CallerContext = CalleeContext.rsplit(" @ ").first;
276 CallerNameWithContext = CallerContext.rsplit(':').first;
277 auto ContextSplit = CallerContext.rsplit(" @ ");
278 FrameLocation LeafFrameLoc = {"", {0, 0}};
279 StringRef Funcname;
280 SampleContext::decodeContextString(ContextSplit.second, Funcname,
281 LeafFrameLoc.second);
282 LeafFrameLoc.first = Funcname.str();
283 return LeafFrameLoc;
284 }
285
populateInferredFunctionSamples()286 void CSProfileGenerator::populateInferredFunctionSamples() {
287 for (const auto &Item : ProfileMap) {
288 const StringRef CalleeContext = Item.first();
289 const FunctionSamples &CalleeProfile = Item.second;
290
291 // If we already have head sample counts, we must have value profile
292 // for call sites added already. Skip to avoid double counting.
293 if (CalleeProfile.getHeadSamples())
294 continue;
295 // If we don't have context, nothing to do for caller's call site.
296 // This could happen for entry point function.
297 if (CalleeContext.find(" @ ") == StringRef::npos)
298 continue;
299
300 // Infer Caller's frame loc and context ID through string splitting
301 StringRef CallerContextId;
302 FrameLocation &&CallerLeafFrameLoc =
303 getCallerContext(CalleeContext, CallerContextId);
304
305 // It's possible that we haven't seen any sample directly in the caller,
306 // in which case CallerProfile will not exist. But we can't modify
307 // ProfileMap while iterating it.
308 // TODO: created function profile for those callers too
309 if (ProfileMap.find(CallerContextId) == ProfileMap.end())
310 continue;
311 FunctionSamples &CallerProfile = ProfileMap[CallerContextId];
312
313 // Since we don't have call count for inlined functions, we
314 // estimate it from inlinee's profile using entry body sample.
315 uint64_t EstimatedCallCount = CalleeProfile.getEntrySamples();
316 // If we don't have samples with location, use 1 to indicate live.
317 if (!EstimatedCallCount && !CalleeProfile.getBodySamples().size())
318 EstimatedCallCount = 1;
319 CallerProfile.addCalledTargetSamples(
320 CallerLeafFrameLoc.second.LineOffset,
321 CallerLeafFrameLoc.second.Discriminator, CalleeProfile.getName(),
322 EstimatedCallCount);
323 updateBodySamplesforFunctionProfile(CallerProfile, CallerLeafFrameLoc,
324 EstimatedCallCount);
325 }
326 }
327
328 } // end namespace sampleprof
329 } // end namespace llvm
330