1//===-- MissingFrameInferrer.h - 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#ifndef LLVM_TOOLS_LLVM_PROFGEN_MISSINGFRAMEINFERRER_H
10#define LLVM_TOOLS_LLVM_PROFGEN_MISSINGFRAMEINFERRER_H
11
12#include "PerfReader.h"
13#include "llvm/ADT/DenseSet.h"
14#include "llvm/ADT/SmallVector.h"
15#include "llvm/ADT/Statistic.h"
16#include <unordered_map>
17#include <unordered_set>
18
19namespace llvm {
20namespace sampleprof {
21
22class ProfiledBinary;
23struct BinaryFunction;
24
25class MissingFrameInferrer {
26public:
27 MissingFrameInferrer(ProfiledBinary *Binary) : Binary(Binary) {}
28
29 // Defininig a frame transition from a caller function to the callee function.
30 using CallerCalleePair = std::pair<BinaryFunction *, BinaryFunction *>;
31
32 void initialize(const ContextSampleCounterMap *SampleCounters);
33
34 // Given an input `Context`, output `NewContext` with inferred missing tail
35 // call frames.
36 void inferMissingFrames(const SmallVectorImpl<uint64_t> &Context,
37 SmallVectorImpl<uint64_t> &NewContext);
38
39private:
40 friend class ProfiledBinary;
41
42 // Compute a unique tail call path for a pair of source frame address and
43 // target frame address. Append the unique path prefix (not including `To`) to
44 // `UniquePath` if exists. Return the whether this's a unqiue tail call
45 // path. The source/dest frame will typically be a pair of adjacent frame
46 // entries of call stack samples.
47 bool inferMissingFrames(uint64_t From, uint64_t To,
48 SmallVectorImpl<uint64_t> &UniquePath);
49
50 // Compute a unique tail call path from the source frame address to the target
51 // function. Output the unique path prefix (not including `To`) in
52 // `UniquePath` if exists. Return the number of possibly availabe tail call
53 // paths.
54 uint64_t computeUniqueTailCallPath(uint64_t From, BinaryFunction *To,
55 SmallVectorImpl<uint64_t> &UniquePath);
56
57 // Compute a unique tail call path from the source function to the target
58 // function. Output the unique path prefix (not including `To`) in
59 // `UniquePath` if exists. Return the number of possibly availabe tail call
60 // paths.
61 uint64_t computeUniqueTailCallPath(BinaryFunction *From, BinaryFunction *To,
62 SmallVectorImpl<uint64_t> &UniquePath);
63
64 ProfiledBinary *Binary;
65
66 // A map of call instructions to their target addresses. This is first
67 // populated with static call edges but then trimmed down to dynamic call
68 // edges based on LBR samples.
69 std::unordered_map<uint64_t, std::unordered_set<uint64_t>> CallEdges;
70
71 // A map of tail call instructions to their target addresses. This is first
72 // populated with static call edges but then trimmed down to dynamic call
73 // edges based on LBR samples.
74 std::unordered_map<uint64_t, std::unordered_set<uint64_t>> TailCallEdges;
75
76 // Dynamic call targets in terms of BinaryFunction for any calls.
77 std::unordered_map<uint64_t, std::unordered_set<BinaryFunction *>> CallEdgesF;
78
79 // Dynamic call targets in terms of BinaryFunction for tail calls.
80 std::unordered_map<uint64_t, std::unordered_set<BinaryFunction *>>
81 TailCallEdgesF;
82
83 // Dynamic tail call targets of caller functions.
84 std::unordered_map<BinaryFunction *, std::vector<uint64_t>> FuncToTailCallMap;
85
86 // Functions that are reachable via tail calls.
87 DenseSet<const BinaryFunction *> TailCallTargetFuncs;
88
89 struct PairHash {
90 std::size_t operator()(
91 const std::pair<BinaryFunction *, BinaryFunction *> &Pair) const {
92 return std::hash<BinaryFunction *>()(Pair.first) ^
93 std::hash<BinaryFunction *>()(Pair.second);
94 }
95 };
96
97 // Cached results from a CallerCalleePair to a unique call path between them.
98 std::unordered_map<CallerCalleePair, std::vector<uint64_t>, PairHash>
99 UniquePaths;
100 // Cached results from CallerCalleePair to the number of available call paths.
101 std::unordered_map<CallerCalleePair, uint64_t, PairHash> NonUniquePaths;
102
103 DenseSet<BinaryFunction *> Visiting;
104
105 uint32_t CurSearchingDepth = 0;
106
107#if LLVM_ENABLE_STATS
108 DenseSet<std::pair<uint64_t, uint64_t>> ReachableViaUniquePaths;
109 DenseSet<std::pair<uint64_t, uint64_t>> Unreachables;
110 DenseSet<std::pair<uint64_t, uint64_t>> ReachableViaMultiPaths;
111#endif
112};
113} // end namespace sampleprof
114} // end namespace llvm
115
116#endif
117