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 std::unordered_map<uint64_t, std::unordered_set<uint64_t>> SampledCalls;
48 std::unordered_map<uint64_t, std::unordered_set<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(x: 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(x: To);
61 }
62 if (TailCallEdges.count(x: 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(x: To);
70 }
71 }
72 }
73
74 // Replace static edges with dynamic edges.
75 CallEdges = SampledCalls;
76 TailCallEdges = 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(x: 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(x: 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 std::unordered_map<uint64_t, std::unordered_set<uint64_t>>
110 &CallTargets,
111 bool IsTailCall) {
112 for (const auto &Targets : CallTargets) {
113 for (const auto &Target : Targets.second) {
114 dbgs() << (IsTailCall ? "TailCall" : "Call");
115 dbgs() << " From " << format("%8" PRIx64, Targets.first) << " to "
116 << format("%8" PRIx64, Target) << "\n";
117 }
118 }
119 };
120
121 LLVM_DEBUG(dbgs() << "============================\n ";
122 dbgs() << "Call targets:\n";
123 PrintCallTargets(CallEdges, false);
124 dbgs() << "\nTail call targets:\n";
125 PrintCallTargets(CallEdges, true);
126 dbgs() << "============================\n";);
127#endif
128}
129
130uint64_t MissingFrameInferrer::computeUniqueTailCallPath(
131 BinaryFunction *From, BinaryFunction *To, SmallVectorImpl<uint64_t> &Path) {
132 // Search for a unique path comprised of only tail call edges for a given
133 // source and target frame address on the a tail call graph that consists of
134 // only tail call edges. Note that only a unique path counts. Multiple paths
135 // are treated unreachable.
136 if (From == To)
137 return 1;
138
139 // Ignore cyclic paths. Since we are doing a recursive DFS walk, if the source
140 // frame being visited is already in the stack, it means we are seeing a
141 // cycle. This is done before querying the cached result because the cached
142 // result may be computed based on the same path. Consider the following case:
143 // A -> B, B -> A, A -> D
144 // When computing unique reachablity from A to D, the cached result for (B,D)
145 // should not be counted since the unique path B->A->D is basically the same
146 // path as A->D. Counting that with invalidate the uniqueness from A to D.
147 if (Visiting.contains(V: From))
148 return 0;
149
150 // If already computed, return the cached result.
151 auto I = UniquePaths.find(x: {From, To});
152 if (I != UniquePaths.end()) {
153 Path.append(in_start: I->second.begin(), in_end: I->second.end());
154 return 1;
155 }
156
157 auto J = NonUniquePaths.find(x: {From, To});
158 if (J != NonUniquePaths.end()) {
159 return J->second;
160 }
161
162 uint64_t Pos = Path.size();
163
164 // DFS walk each outgoing tail call edges.
165 // Bail out if we are already at the the maximum searching depth.
166 if (CurSearchingDepth == MaximumSearchDepth)
167 return 0;
168
169 auto It = FuncToTailCallMap.find(x: From);
170 if (It == FuncToTailCallMap.end())
171 return 0;
172
173 CurSearchingDepth++;
174 Visiting.insert(V: From);
175 uint64_t NumPaths = 0;
176 for (auto TailCall : It->second) {
177 NumPaths += computeUniqueTailCallPath(From: TailCall, To, UniquePath&: Path);
178 // Stop analyzing the remaining if we are already seeing more than one
179 // reachable paths.
180 if (NumPaths > 1)
181 break;
182 }
183 CurSearchingDepth--;
184 Visiting.erase(V: From);
185
186 // Undo already-computed path if it is not unique.
187 if (NumPaths != 1) {
188 Path.pop_back_n(NumItems: Path.size() - Pos);
189 }
190
191 // Cache the result.
192 if (NumPaths == 1) {
193 UniquePaths[{From, To}].assign(first: Path.begin() + Pos, last: Path.end());
194#if LLVM_ENABLE_STATS
195 auto &LocalPath = UniquePaths[{From, To}];
196 assert((LocalPath.size() <= MaximumSearchDepth + 1) &&
197 "Path should not be longer than the maximum searching depth");
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
208uint64_t MissingFrameInferrer::computeUniqueTailCallPath(
209 uint64_t From, BinaryFunction *To, SmallVectorImpl<uint64_t> &Path) {
210 auto It = TailCallEdgesF.find(x: From);
211 if (It == TailCallEdgesF.end())
212 return 0;
213 Path.push_back(Elt: From);
214 uint64_t NumPaths = 0;
215 for (auto Target : It->second) {
216 NumPaths += computeUniqueTailCallPath(From: Target, To, Path);
217 // Stop analyzing the remaining if we are already seeing more than one
218 // reachable paths.
219 if (NumPaths > 1)
220 break;
221 }
222
223 // Undo already-computed path if it is not unique.
224 if (NumPaths != 1)
225 Path.pop_back();
226 return NumPaths;
227}
228
229bool MissingFrameInferrer::inferMissingFrames(
230 uint64_t From, uint64_t To, SmallVectorImpl<uint64_t> &UniquePath) {
231 assert(!TailCallEdgesF.count(From) &&
232 "transition between From and To cannot be via a tailcall otherwise "
233 "they would not show up at the same time");
234 UniquePath.push_back(Elt: From);
235 uint64_t Pos = UniquePath.size();
236
237 FuncRange *ToFRange = Binary->findFuncRange(Address: To);
238 if (!ToFRange)
239 return false;
240
241 // Bail out if caller has no known outgoing call edges.
242 auto It = CallEdgesF.find(x: From);
243 if (It == CallEdgesF.end())
244 return false;
245
246 // Done with the inference if the calle is reachable via a single callsite.
247 // This may not be accurate but it improves the search throughput.
248 if (llvm::is_contained(Range&: It->second, Element: ToFRange->Func))
249 return true;
250
251 // Bail out if callee is not tailcall reachable at all.
252 if (!TailCallTargetFuncs.contains(V: ToFRange->Func))
253 return false;
254
255 Visiting.clear();
256 CurSearchingDepth = 0;
257 uint64_t NumPaths = 0;
258 for (auto Target : It->second) {
259 NumPaths +=
260 computeUniqueTailCallPath(From: Target, To: ToFRange->Func, Path&: UniquePath);
261 // Stop analyzing the remaining if we are already seeing more than one
262 // reachable paths.
263 if (NumPaths > 1)
264 break;
265 }
266
267 // Undo already-computed path if it is not unique.
268 if (NumPaths != 1) {
269 UniquePath.pop_back_n(NumItems: UniquePath.size() - Pos);
270 assert(UniquePath.back() == From && "broken path");
271 }
272
273#if LLVM_ENABLE_STATS
274 if (NumPaths == 1) {
275 if (ReachableViaUniquePaths.insert({From, ToFRange->StartAddress}).second)
276 TailCallUniReachable++;
277 } else if (NumPaths == 0) {
278 if (Unreachables.insert({From, ToFRange->StartAddress}).second) {
279 TailCallUnreachable++;
280 LLVM_DEBUG(dbgs() << "No path found from "
281 << format("%8" PRIx64 ":", From) << " to "
282 << format("%8" PRIx64 ":", ToFRange->StartAddress)
283 << "\n");
284 }
285 } else if (NumPaths > 1) {
286 if (ReachableViaMultiPaths.insert({From, ToFRange->StartAddress})
287 .second) {
288 TailCallMultiReachable++;
289 LLVM_DEBUG(dbgs() << "Multiple paths found from "
290 << format("%8" PRIx64 ":", From) << " to "
291 << format("%8" PRIx64 ":", ToFRange->StartAddress)
292 << "\n");
293 }
294 }
295#endif
296
297 return NumPaths == 1;
298}
299
300void MissingFrameInferrer::inferMissingFrames(
301 const SmallVectorImpl<uint64_t> &Context,
302 SmallVectorImpl<uint64_t> &NewContext) {
303 if (Context.size() == 1) {
304 NewContext = Context;
305 return;
306 }
307
308 NewContext.clear();
309 for (uint64_t I = 1; I < Context.size(); I++) {
310 inferMissingFrames(From: Context[I - 1], To: Context[I], UniquePath&: NewContext);
311 }
312 NewContext.push_back(Elt: Context.back());
313
314 assert((NewContext.size() >= Context.size()) &&
315 "Inferred context should include all frames in the original context");
316 assert((NewContext.size() > Context.size() || NewContext == Context) &&
317 "Inferred context should be exactly the same "
318 "with the original context");
319}
320