1//===-- MissingFrameInferrer.cpp - Missing frame inferrer --------- 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 "MissingFrameInferrer.h"
10#include "Options.h"
11#include "PerfReader.h"
12#include "ProfiledBinary.h"
13#include "llvm/ADT/SCCIterator.h"
14#include "llvm/ADT/Statistic.h"
15#include <algorithm>
16#include <cstdint>
17#include <queue>
18#include <sys/types.h>
19
20#define DEBUG_TYPE "missing-frame-inferrer"
21
22using namespace llvm;
23using namespace sampleprof;
24
25STATISTIC(TailCallUniReachable,
26 "Number of frame pairs reachable via a unique tail call path");
27STATISTIC(TailCallMultiReachable,
28 "Number of frame pairs reachable via a multiple tail call paths");
29STATISTIC(TailCallUnreachable,
30 "Number of frame pairs unreachable via any tail call path");
31STATISTIC(TailCallFuncSingleTailCalls,
32 "Number of functions with single tail call site");
33STATISTIC(TailCallFuncMultipleTailCalls,
34 "Number of functions with multiple tail call sites");
35STATISTIC(TailCallMaxTailCallPath, "Length of the longest tail call path");
36
37void MissingFrameInferrer::initialize(
38 const ContextSampleCounterMap *SampleCounters) {
39 // Refine call edges based on LBR samples.
40 if (SampleCounters) {
41 DenseMap<uint64_t, DenseSet<uint64_t>> SampledCalls;
42 DenseMap<uint64_t, DenseSet<uint64_t>> SampledTailCalls;
43
44 // Populate SampledCalls based on static call sites. Similarly to
45 // SampledTailCalls.
46 for (const auto &CI : *SampleCounters) {
47 for (auto Item : CI.second.BranchCounter) {
48 auto From = Item.first.first;
49 auto To = Item.first.second;
50 if (CallEdges.count(Val: From)) {
51 assert(CallEdges[From].size() == 1 &&
52 "A callsite should only appear once with either a known or a "
53 "zero (unknown) target value at this point");
54 SampledCalls[From].insert(V: To);
55 }
56 if (TailCallEdges.count(Val: From)) {
57 assert(TailCallEdges[From].size() == 1 &&
58 "A callsite should only appear once with either a known or a "
59 "zero (unknown) target value at this point");
60 FuncRange *FromFRange = Binary->findFuncRange(Address: From);
61 FuncRange *ToFRange = Binary->findFuncRange(Address: To);
62 if (FromFRange != ToFRange)
63 SampledTailCalls[From].insert(V: To);
64 }
65 }
66 }
67
68 // Replace static edges with dynamic edges.
69 CallEdges = std::move(SampledCalls);
70 TailCallEdges = std::move(SampledTailCalls);
71 }
72
73 // Populate function-based edges. This is to speed up address to function
74 // translation.
75 for (auto Call : CallEdges)
76 for (auto Target : Call.second)
77 if (FuncRange *ToFRange = Binary->findFuncRange(Address: Target))
78 CallEdgesF[Call.first].insert(Ptr: ToFRange->Func);
79
80 for (auto Call : TailCallEdges) {
81 for (auto Target : Call.second) {
82 if (FuncRange *ToFRange = Binary->findFuncRange(Address: Target)) {
83 TailCallEdgesF[Call.first].insert(Ptr: ToFRange->Func);
84 TailCallTargetFuncs.insert(V: ToFRange->Func);
85 }
86 }
87 if (FuncRange *FromFRange = Binary->findFuncRange(Address: Call.first))
88 FuncToTailCallMap[FromFRange->Func].push_back(x: Call.first);
89 }
90
91#if LLVM_ENABLE_STATS
92 for (auto F : FuncToTailCallMap) {
93 assert(F.second.size() > 0 && "");
94 if (F.second.size() > 1)
95 TailCallFuncMultipleTailCalls++;
96 else
97 TailCallFuncSingleTailCalls++;
98 }
99#endif
100
101#ifndef NDEBUG
102 auto PrintCallTargets =
103 [&](const DenseMap<uint64_t, DenseSet<uint64_t>> &CallTargets,
104 bool IsTailCall) {
105 for (const auto &Targets : CallTargets) {
106 for (const auto &Target : Targets.second) {
107 dbgs() << (IsTailCall ? "TailCall" : "Call");
108 dbgs() << " From " << format("%8" PRIx64, Targets.first) << " to "
109 << format("%8" PRIx64, Target) << "\n";
110 }
111 }
112 };
113
114 LLVM_DEBUG({
115 dbgs() << "============================\n ";
116 dbgs() << "Call targets:\n";
117 PrintCallTargets(CallEdges, false);
118 dbgs() << "\nTail call targets:\n";
119 PrintCallTargets(TailCallEdges, true);
120 dbgs() << "============================\n";
121 });
122#endif
123}
124
125uint64_t MissingFrameInferrer::computeUniqueTailCallPath(
126 BinaryFunction *From, BinaryFunction *To, SmallVectorImpl<uint64_t> &Path) {
127 // Search for a unique path comprised of only tail call edges for a given
128 // source and target frame address on the a tail call graph that consists of
129 // only tail call edges. Note that only a unique path counts. Multiple paths
130 // are treated unreachable.
131 if (From == To) {
132 ++NumFoundPaths;
133 return 1;
134 }
135
136 // Ignore cyclic paths. Since we are doing a recursive DFS walk, if the source
137 // frame being visited is already in the stack, it means we are seeing a
138 // cycle. Frames stay visited after the walk returns from them, so each frame
139 // is walked once.
140 if (Visiting.contains(V: From))
141 return 0;
142
143 uint64_t Pos = Path.size();
144
145 // DFS walk each outgoing tail call edges.
146 auto It = FuncToTailCallMap.find(Val: From);
147 if (It == FuncToTailCallMap.end())
148 return 0;
149
150 Visiting.insert(V: From);
151 uint64_t NumPaths = 0;
152 for (auto TailCall : It->second) {
153 NumPaths += computeUniqueTailCallPath(From: TailCall, To, UniquePath&: Path);
154 // Stop analyzing the remaining if we are already seeing more than one
155 // reachable paths.
156 if (NumFoundPaths > 1)
157 break;
158 }
159
160 // Undo already-computed path if it is not unique.
161 if (NumPaths != 1) {
162 Path.pop_back_n(NumItems: Path.size() - Pos);
163 }
164
165 return NumPaths;
166}
167
168uint64_t MissingFrameInferrer::searchUniqueTailCallPath(
169 BinaryFunction *From, BinaryFunction *To, SmallVectorImpl<uint64_t> &Path) {
170 // If already computed, return the cached result. The result of a walk
171 // depends on the frames visited before it, so only whole searches are cached.
172 auto I = UniquePaths.find(Val: {From, To});
173 if (I != UniquePaths.end()) {
174 Path.append(in_start: I->second.begin(), in_end: I->second.end());
175 return 1;
176 }
177
178 auto J = NonUniquePaths.find(Val: {From, To});
179 if (J != NonUniquePaths.end()) {
180 return J->second;
181 }
182
183 uint64_t Pos = Path.size();
184 Visiting.clear();
185 NumFoundPaths = 0;
186 uint64_t NumPaths = computeUniqueTailCallPath(From, To, Path);
187 if (NumPaths == 1 &&
188 hasOtherTailCallPath(Path: ArrayRef(Path).drop_front(N: Pos), To)) {
189 NumPaths = 2;
190 Path.pop_back_n(NumItems: Path.size() - Pos);
191 }
192
193 // Cache the result.
194 if (NumPaths == 1) {
195 UniquePaths[{From, To}].assign(first: Path.begin() + Pos, last: Path.end());
196#if LLVM_ENABLE_STATS
197 auto &LocalPath = UniquePaths[{From, To}];
198 TailCallMaxTailCallPath = std::max(uint64_t(LocalPath.size()),
199 TailCallMaxTailCallPath.getValue());
200#endif
201 } else {
202 NonUniquePaths[{From, To}] = NumPaths;
203 }
204
205 return NumPaths;
206}
207
208bool MissingFrameInferrer::hasOtherTailCallPath(ArrayRef<uint64_t> Path,
209 BinaryFunction *To) {
210 // Another simple path leaves this one at a frame through another tail call
211 // and rejoins it at a later frame, from which `To` is reachable. Walk from
212 // the frames of the path in order, keeping frames visited: the frames
213 // visited without reaching `To` reach no later frame of the path.
214 SmallVector<BinaryFunction *, 8> Funcs;
215 for (uint64_t Site : Path)
216 Funcs.push_back(Elt: Binary->findFuncRange(Address: Site)->Func);
217 Funcs.push_back(Elt: To);
218 Visiting.clear();
219 // Count the path itself, so that a walk stops at the first path it finds.
220 NumFoundPaths = 1;
221 SmallVector<uint64_t, 8> OtherPath;
222 for (auto [I, PathSite] : enumerate(First&: Path)) {
223 Visiting.insert(V: Funcs[I]);
224 for (uint64_t Site : FuncToTailCallMap.find(Val: Funcs[I])->second) {
225 auto It = TailCallEdgesF.find(Val: Site);
226 if (It == TailCallEdgesF.end())
227 continue;
228 for (BinaryFunction *Target : It->second)
229 if ((Site != PathSite || Target != Funcs[I + 1]) &&
230 computeUniqueTailCallPath(From: Target, To, Path&: OtherPath))
231 return true;
232 }
233 }
234 return false;
235}
236
237uint64_t MissingFrameInferrer::computeUniqueTailCallPath(
238 uint64_t From, BinaryFunction *To, SmallVectorImpl<uint64_t> &Path) {
239 auto It = TailCallEdgesF.find(Val: From);
240 if (It == TailCallEdgesF.end())
241 return 0;
242 Path.push_back(Elt: From);
243 uint64_t NumPaths = 0;
244 for (auto Target : It->second) {
245 NumPaths += computeUniqueTailCallPath(From: Target, To, Path);
246 // Stop analyzing the remaining if we are already seeing more than one
247 // reachable paths.
248 if (NumFoundPaths > 1)
249 break;
250 }
251
252 // Undo already-computed path if it is not unique.
253 if (NumPaths != 1)
254 Path.pop_back();
255 return NumPaths;
256}
257
258bool MissingFrameInferrer::inferMissingFrames(
259 uint64_t From, uint64_t To, SmallVectorImpl<uint64_t> &UniquePath) {
260 assert(!TailCallEdgesF.count(From) &&
261 "transition between From and To cannot be via a tailcall otherwise "
262 "they would not show up at the same time");
263 UniquePath.push_back(Elt: From);
264 uint64_t Pos = UniquePath.size();
265
266 FuncRange *ToFRange = Binary->findFuncRange(Address: To);
267 if (!ToFRange)
268 return false;
269
270 // Bail out if caller has no known outgoing call edges.
271 auto It = CallEdgesF.find(Val: From);
272 if (It == CallEdgesF.end())
273 return false;
274
275 // Done with the inference if the calle is reachable via a single callsite.
276 // This may not be accurate but it improves the search throughput.
277 if (llvm::is_contained(Range&: It->second, Element: ToFRange->Func))
278 return true;
279
280 // Bail out if callee is not tailcall reachable at all.
281 if (!TailCallTargetFuncs.contains(V: ToFRange->Func))
282 return false;
283
284 uint64_t NumPaths = 0;
285 for (auto Target : It->second) {
286 NumPaths += searchUniqueTailCallPath(From: Target, To: ToFRange->Func, Path&: UniquePath);
287 // Stop analyzing the remaining if we are already seeing more than one
288 // reachable paths.
289 if (NumPaths > 1)
290 break;
291 }
292
293 // Undo already-computed path if it is not unique.
294 if (NumPaths != 1) {
295 UniquePath.pop_back_n(NumItems: UniquePath.size() - Pos);
296 assert(UniquePath.back() == From && "broken path");
297 }
298
299#if LLVM_ENABLE_STATS
300 if (NumPaths == 1) {
301 if (ReachableViaUniquePaths.insert({From, ToFRange->StartAddress}).second)
302 TailCallUniReachable++;
303 } else if (NumPaths == 0) {
304 if (Unreachables.insert({From, ToFRange->StartAddress}).second) {
305 TailCallUnreachable++;
306 LLVM_DEBUG(dbgs() << "No path found from "
307 << format("%8" PRIx64 ":", From) << " to "
308 << format("%8" PRIx64 ":", ToFRange->StartAddress)
309 << "\n");
310 }
311 } else if (NumPaths > 1) {
312 if (ReachableViaMultiPaths.insert({From, ToFRange->StartAddress})
313 .second) {
314 TailCallMultiReachable++;
315 LLVM_DEBUG(dbgs() << "Multiple paths found from "
316 << format("%8" PRIx64 ":", From) << " to "
317 << format("%8" PRIx64 ":", ToFRange->StartAddress)
318 << "\n");
319 }
320 }
321#endif
322
323 return NumPaths == 1;
324}
325
326void MissingFrameInferrer::inferMissingFrames(
327 const SmallVectorImpl<uint64_t> &Context,
328 SmallVectorImpl<uint64_t> &NewContext) {
329 if (Context.size() == 1) {
330 NewContext = Context;
331 return;
332 }
333
334 NewContext.clear();
335 for (uint64_t I = 1; I < Context.size(); I++) {
336 inferMissingFrames(From: Context[I - 1], To: Context[I], UniquePath&: NewContext);
337 }
338 NewContext.push_back(Elt: Context.back());
339
340 assert((NewContext.size() >= Context.size()) &&
341 "Inferred context should include all frames in the original context");
342 assert((NewContext.size() > Context.size() || NewContext == Context) &&
343 "Inferred context should be exactly the same "
344 "with the original context");
345}
346