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
37static cl::opt<uint32_t>
38 MaximumSearchDepth("max-search-depth", cl::init(UINT32_MAX - 1),
39 cl::desc("The maximum levels the DFS-based missing "
40 "frame search should go with"),
41 cl::cat(ProfGenCategory));
42
43void MissingFrameInferrer::initialize(
44 const ContextSampleCounterMap *SampleCounters) {
45 // Refine call edges based on LBR samples.
46 if (SampleCounters) {
47 DenseMap<uint64_t, DenseSet<uint64_t>> SampledCalls;
48 DenseMap<uint64_t, DenseSet<uint64_t>> SampledTailCalls;
49
50 // Populate SampledCalls based on static call sites. Similarly to
51 // SampledTailCalls.
52 for (const auto &CI : *SampleCounters) {
53 for (auto Item : CI.second.BranchCounter) {
54 auto From = Item.first.first;
55 auto To = Item.first.second;
56 if (CallEdges.count(Val: From)) {
57 assert(CallEdges[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 SampledCalls[From].insert(V: To);
61 }
62 if (TailCallEdges.count(Val: From)) {
63 assert(TailCallEdges[From].size() == 1 &&
64 "A callsite should only appear once with either a known or a "
65 "zero (unknown) target value at this point");
66 FuncRange *FromFRange = Binary->findFuncRange(Address: From);
67 FuncRange *ToFRange = Binary->findFuncRange(Address: To);
68 if (FromFRange != ToFRange)
69 SampledTailCalls[From].insert(V: To);
70 }
71 }
72 }
73
74 // Replace static edges with dynamic edges.
75 CallEdges = std::move(SampledCalls);
76 TailCallEdges = std::move(SampledTailCalls);
77 }
78
79 // Populate function-based edges. This is to speed up address to function
80 // translation.
81 for (auto Call : CallEdges)
82 for (auto Target : Call.second)
83 if (FuncRange *ToFRange = Binary->findFuncRange(Address: Target))
84 CallEdgesF[Call.first].insert(Ptr: ToFRange->Func);
85
86 for (auto Call : TailCallEdges) {
87 for (auto Target : Call.second) {
88 if (FuncRange *ToFRange = Binary->findFuncRange(Address: Target)) {
89 TailCallEdgesF[Call.first].insert(Ptr: ToFRange->Func);
90 TailCallTargetFuncs.insert(V: ToFRange->Func);
91 }
92 }
93 if (FuncRange *FromFRange = Binary->findFuncRange(Address: Call.first))
94 FuncToTailCallMap[FromFRange->Func].push_back(x: Call.first);
95 }
96
97#if LLVM_ENABLE_STATS
98 for (auto F : FuncToTailCallMap) {
99 assert(F.second.size() > 0 && "");
100 if (F.second.size() > 1)
101 TailCallFuncMultipleTailCalls++;
102 else
103 TailCallFuncSingleTailCalls++;
104 }
105#endif
106
107#ifndef NDEBUG
108 auto PrintCallTargets =
109 [&](const DenseMap<uint64_t, DenseSet<uint64_t>> &CallTargets,
110 bool IsTailCall) {
111 for (const auto &Targets : CallTargets) {
112 for (const auto &Target : Targets.second) {
113 dbgs() << (IsTailCall ? "TailCall" : "Call");
114 dbgs() << " From " << format("%8" PRIx64, Targets.first) << " to "
115 << format("%8" PRIx64, Target) << "\n";
116 }
117 }
118 };
119
120 LLVM_DEBUG({
121 dbgs() << "============================\n ";
122 dbgs() << "Call targets:\n";
123 PrintCallTargets(CallEdges, false);
124 dbgs() << "\nTail call targets:\n";
125 PrintCallTargets(TailCallEdges, true);
126 dbgs() << "============================\n";
127 });
128#endif
129}
130
131uint64_t MissingFrameInferrer::computeUniqueTailCallPath(
132 BinaryFunction *From, BinaryFunction *To, SmallVectorImpl<uint64_t> &Path) {
133 // Search for a unique path comprised of only tail call edges for a given
134 // source and target frame address on the a tail call graph that consists of
135 // only tail call edges. Note that only a unique path counts. Multiple paths
136 // are treated unreachable.
137 if (From == To)
138 return 1;
139
140 // Ignore cyclic paths. Since we are doing a recursive DFS walk, if the source
141 // frame being visited is already in the stack, it means we are seeing a
142 // cycle. This is done before querying the cached result because the cached
143 // result may be computed based on the same path. Consider the following case:
144 // A -> B, B -> A, A -> D
145 // When computing unique reachablity from A to D, the cached result for (B,D)
146 // should not be counted since the unique path B->A->D is basically the same
147 // path as A->D. Counting that with invalidate the uniqueness from A to D.
148 if (Visiting.contains(V: From))
149 return 0;
150
151 // If already computed, return the cached result.
152 auto I = UniquePaths.find(Val: {From, To});
153 if (I != UniquePaths.end()) {
154 Path.append(in_start: I->second.begin(), in_end: I->second.end());
155 return 1;
156 }
157
158 auto J = NonUniquePaths.find(Val: {From, To});
159 if (J != NonUniquePaths.end()) {
160 return J->second;
161 }
162
163 uint64_t Pos = Path.size();
164
165 // DFS walk each outgoing tail call edges.
166 // Bail out if we are already at the the maximum searching depth.
167 if (CurSearchingDepth == MaximumSearchDepth)
168 return 0;
169
170 auto It = FuncToTailCallMap.find(Val: From);
171 if (It == FuncToTailCallMap.end())
172 return 0;
173
174 CurSearchingDepth++;
175 Visiting.insert(V: From);
176 uint64_t NumPaths = 0;
177 for (auto TailCall : It->second) {
178 NumPaths += computeUniqueTailCallPath(From: TailCall, To, UniquePath&: Path);
179 // Stop analyzing the remaining if we are already seeing more than one
180 // reachable paths.
181 if (NumPaths > 1)
182 break;
183 }
184 CurSearchingDepth--;
185 Visiting.erase(V: From);
186
187 // Undo already-computed path if it is not unique.
188 if (NumPaths != 1) {
189 Path.pop_back_n(NumItems: Path.size() - Pos);
190 }
191
192 // Cache the result.
193 if (NumPaths == 1) {
194 UniquePaths[{From, To}].assign(first: Path.begin() + Pos, last: Path.end());
195#if LLVM_ENABLE_STATS
196 auto &LocalPath = UniquePaths[{From, To}];
197 assert((LocalPath.size() <= MaximumSearchDepth + 1) &&
198 "Path should not be longer than the maximum searching depth");
199 TailCallMaxTailCallPath = std::max(uint64_t(LocalPath.size()),
200 TailCallMaxTailCallPath.getValue());
201#endif
202 } else {
203 NonUniquePaths[{From, To}] = NumPaths;
204 }
205
206 return NumPaths;
207}
208
209uint64_t MissingFrameInferrer::computeUniqueTailCallPath(
210 uint64_t From, BinaryFunction *To, SmallVectorImpl<uint64_t> &Path) {
211 auto It = TailCallEdgesF.find(Val: From);
212 if (It == TailCallEdgesF.end())
213 return 0;
214 Path.push_back(Elt: From);
215 uint64_t NumPaths = 0;
216 for (auto Target : It->second) {
217 NumPaths += computeUniqueTailCallPath(From: Target, To, Path);
218 // Stop analyzing the remaining if we are already seeing more than one
219 // reachable paths.
220 if (NumPaths > 1)
221 break;
222 }
223
224 // Undo already-computed path if it is not unique.
225 if (NumPaths != 1)
226 Path.pop_back();
227 return NumPaths;
228}
229
230bool MissingFrameInferrer::inferMissingFrames(
231 uint64_t From, uint64_t To, SmallVectorImpl<uint64_t> &UniquePath) {
232 assert(!TailCallEdgesF.count(From) &&
233 "transition between From and To cannot be via a tailcall otherwise "
234 "they would not show up at the same time");
235 UniquePath.push_back(Elt: From);
236 uint64_t Pos = UniquePath.size();
237
238 FuncRange *ToFRange = Binary->findFuncRange(Address: To);
239 if (!ToFRange)
240 return false;
241
242 // Bail out if caller has no known outgoing call edges.
243 auto It = CallEdgesF.find(Val: From);
244 if (It == CallEdgesF.end())
245 return false;
246
247 // Done with the inference if the calle is reachable via a single callsite.
248 // This may not be accurate but it improves the search throughput.
249 if (llvm::is_contained(Range&: It->second, Element: ToFRange->Func))
250 return true;
251
252 // Bail out if callee is not tailcall reachable at all.
253 if (!TailCallTargetFuncs.contains(V: ToFRange->Func))
254 return false;
255
256 Visiting.clear();
257 CurSearchingDepth = 0;
258 uint64_t NumPaths = 0;
259 for (auto Target : It->second) {
260 NumPaths +=
261 computeUniqueTailCallPath(From: Target, To: ToFRange->Func, Path&: UniquePath);
262 // Stop analyzing the remaining if we are already seeing more than one
263 // reachable paths.
264 if (NumPaths > 1)
265 break;
266 }
267
268 // Undo already-computed path if it is not unique.
269 if (NumPaths != 1) {
270 UniquePath.pop_back_n(NumItems: UniquePath.size() - Pos);
271 assert(UniquePath.back() == From && "broken path");
272 }
273
274#if LLVM_ENABLE_STATS
275 if (NumPaths == 1) {
276 if (ReachableViaUniquePaths.insert({From, ToFRange->StartAddress}).second)
277 TailCallUniReachable++;
278 } else if (NumPaths == 0) {
279 if (Unreachables.insert({From, ToFRange->StartAddress}).second) {
280 TailCallUnreachable++;
281 LLVM_DEBUG(dbgs() << "No path found from "
282 << format("%8" PRIx64 ":", From) << " to "
283 << format("%8" PRIx64 ":", ToFRange->StartAddress)
284 << "\n");
285 }
286 } else if (NumPaths > 1) {
287 if (ReachableViaMultiPaths.insert({From, ToFRange->StartAddress})
288 .second) {
289 TailCallMultiReachable++;
290 LLVM_DEBUG(dbgs() << "Multiple paths found from "
291 << format("%8" PRIx64 ":", From) << " to "
292 << format("%8" PRIx64 ":", ToFRange->StartAddress)
293 << "\n");
294 }
295 }
296#endif
297
298 return NumPaths == 1;
299}
300
301void MissingFrameInferrer::inferMissingFrames(
302 const SmallVectorImpl<uint64_t> &Context,
303 SmallVectorImpl<uint64_t> &NewContext) {
304 if (Context.size() == 1) {
305 NewContext = Context;
306 return;
307 }
308
309 NewContext.clear();
310 for (uint64_t I = 1; I < Context.size(); I++) {
311 inferMissingFrames(From: Context[I - 1], To: Context[I], UniquePath&: NewContext);
312 }
313 NewContext.push_back(Elt: Context.back());
314
315 assert((NewContext.size() >= Context.size()) &&
316 "Inferred context should include all frames in the original context");
317 assert((NewContext.size() > Context.size() || NewContext == Context) &&
318 "Inferred context should be exactly the same "
319 "with the original context");
320}
321