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
169 if (!FuncToTailCallMap.count(x: From))
170 return 0;
171
172 CurSearchingDepth++;
173 Visiting.insert(V: From);
174 uint64_t NumPaths = 0;
175 for (auto TailCall : FuncToTailCallMap[From]) {
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 if (!TailCallEdgesF.count(x: From))
210 return 0;
211 Path.push_back(Elt: From);
212 uint64_t NumPaths = 0;
213 for (auto Target : TailCallEdgesF[From]) {
214 NumPaths += computeUniqueTailCallPath(From: Target, To, Path);
215 // Stop analyzing the remaining if we are already seeing more than one
216 // reachable paths.
217 if (NumPaths > 1)
218 break;
219 }
220
221 // Undo already-computed path if it is not unique.
222 if (NumPaths != 1)
223 Path.pop_back();
224 return NumPaths;
225}
226
227bool MissingFrameInferrer::inferMissingFrames(
228 uint64_t From, uint64_t To, SmallVectorImpl<uint64_t> &UniquePath) {
229 assert(!TailCallEdgesF.count(From) &&
230 "transition between From and To cannot be via a tailcall otherwise "
231 "they would not show up at the same time");
232 UniquePath.push_back(Elt: From);
233 uint64_t Pos = UniquePath.size();
234
235 FuncRange *ToFRange = Binary->findFuncRange(Address: To);
236 if (!ToFRange)
237 return false;
238
239 // Bail out if caller has no known outgoing call edges.
240 if (!CallEdgesF.count(x: From))
241 return false;
242
243 // Done with the inference if the calle is reachable via a single callsite.
244 // This may not be accurate but it improves the search throughput.
245 if (llvm::is_contained(Range&: CallEdgesF[From], Element: ToFRange->Func))
246 return true;
247
248 // Bail out if callee is not tailcall reachable at all.
249 if (!TailCallTargetFuncs.contains(V: ToFRange->Func))
250 return false;
251
252 Visiting.clear();
253 CurSearchingDepth = 0;
254 uint64_t NumPaths = 0;
255 for (auto Target : CallEdgesF[From]) {
256 NumPaths +=
257 computeUniqueTailCallPath(From: Target, To: ToFRange->Func, Path&: UniquePath);
258 // Stop analyzing the remaining if we are already seeing more than one
259 // reachable paths.
260 if (NumPaths > 1)
261 break;
262 }
263
264 // Undo already-computed path if it is not unique.
265 if (NumPaths != 1) {
266 UniquePath.pop_back_n(NumItems: UniquePath.size() - Pos);
267 assert(UniquePath.back() == From && "broken path");
268 }
269
270#if LLVM_ENABLE_STATS
271 if (NumPaths == 1) {
272 if (ReachableViaUniquePaths.insert({From, ToFRange->StartAddress}).second)
273 TailCallUniReachable++;
274 } else if (NumPaths == 0) {
275 if (Unreachables.insert({From, ToFRange->StartAddress}).second) {
276 TailCallUnreachable++;
277 LLVM_DEBUG(dbgs() << "No path found from "
278 << format("%8" PRIx64 ":", From) << " to "
279 << format("%8" PRIx64 ":", ToFRange->StartAddress)
280 << "\n");
281 }
282 } else if (NumPaths > 1) {
283 if (ReachableViaMultiPaths.insert({From, ToFRange->StartAddress})
284 .second) {
285 TailCallMultiReachable++;
286 LLVM_DEBUG(dbgs() << "Multiple paths found from "
287 << format("%8" PRIx64 ":", From) << " to "
288 << format("%8" PRIx64 ":", ToFRange->StartAddress)
289 << "\n");
290 }
291 }
292#endif
293
294 return NumPaths == 1;
295}
296
297void MissingFrameInferrer::inferMissingFrames(
298 const SmallVectorImpl<uint64_t> &Context,
299 SmallVectorImpl<uint64_t> &NewContext) {
300 if (Context.size() == 1) {
301 NewContext = Context;
302 return;
303 }
304
305 NewContext.clear();
306 for (uint64_t I = 1; I < Context.size(); I++) {
307 inferMissingFrames(From: Context[I - 1], To: Context[I], UniquePath&: NewContext);
308 }
309 NewContext.push_back(Elt: Context.back());
310
311 assert((NewContext.size() >= Context.size()) &&
312 "Inferred context should include all frames in the original context");
313 assert((NewContext.size() > Context.size() || NewContext == Context) &&
314 "Inferred context should be exactly the same "
315 "with the original context");
316}
317