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