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/DenseMap.h"
14#include "llvm/ADT/DenseSet.h"
15#include "llvm/ADT/SmallPtrSet.h"
16#include "llvm/ADT/SmallVector.h"
17#include "llvm/ADT/Statistic.h"
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 DenseMap<uint64_t, DenseSet<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 DenseMap<uint64_t, DenseSet<uint64_t>> TailCallEdges;
75
76 // Dynamic call targets in terms of BinaryFunction for any calls.
77 DenseMap<uint64_t, SmallPtrSet<BinaryFunction *, 0>> CallEdgesF;
78
79 // Dynamic call targets in terms of BinaryFunction for tail calls.
80 DenseMap<uint64_t, SmallPtrSet<BinaryFunction *, 0>> TailCallEdgesF;
81
82 // Dynamic tail call targets of caller functions.
83 DenseMap<BinaryFunction *, std::vector<uint64_t>> FuncToTailCallMap;
84
85 // Functions that are reachable via tail calls.
86 DenseSet<const BinaryFunction *> TailCallTargetFuncs;
87
88 // Cached results from a CallerCalleePair to a unique call path between them.
89 DenseMap<CallerCalleePair, std::vector<uint64_t>> UniquePaths;
90 // Cached results from CallerCalleePair to the number of available call paths.
91 DenseMap<CallerCalleePair, uint64_t> NonUniquePaths;
92
93 DenseSet<BinaryFunction *> Visiting;
94
95 uint32_t CurSearchingDepth = 0;
96
97#if LLVM_ENABLE_STATS
98 DenseSet<std::pair<uint64_t, uint64_t>> ReachableViaUniquePaths;
99 DenseSet<std::pair<uint64_t, uint64_t>> Unreachables;
100 DenseSet<std::pair<uint64_t, uint64_t>> ReachableViaMultiPaths;
101#endif
102};
103} // end namespace sampleprof
104} // end namespace llvm
105
106#endif
107