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 // Compute a unique tail call path from the source function to the target
65 // function as above, with no functions visited before, and cache the result.
66 // A single path found is checked to be the only one.
67 uint64_t searchUniqueTailCallPath(BinaryFunction *From, BinaryFunction *To,
68 SmallVectorImpl<uint64_t> &UniquePath);
69
70 // Return whether there is a tail call path to the target function other than
71 // the one through the tail calls in `Path`, from the function of its first.
72 bool hasOtherTailCallPath(ArrayRef<uint64_t> Path, BinaryFunction *To);
73
74 ProfiledBinary *Binary;
75
76 // A map of call instructions to their target addresses. This is first
77 // populated with static call edges but then trimmed down to dynamic call
78 // edges based on LBR samples.
79 DenseMap<uint64_t, DenseSet<uint64_t>> CallEdges;
80
81 // A map of tail call instructions to their target addresses. This is first
82 // populated with static call edges but then trimmed down to dynamic call
83 // edges based on LBR samples.
84 DenseMap<uint64_t, DenseSet<uint64_t>> TailCallEdges;
85
86 // Dynamic call targets in terms of BinaryFunction for any calls.
87 DenseMap<uint64_t, SmallPtrSet<BinaryFunction *, 0>> CallEdgesF;
88
89 // Dynamic call targets in terms of BinaryFunction for tail calls.
90 DenseMap<uint64_t, SmallPtrSet<BinaryFunction *, 0>> TailCallEdgesF;
91
92 // Dynamic tail call targets of caller functions.
93 DenseMap<BinaryFunction *, std::vector<uint64_t>> FuncToTailCallMap;
94
95 // Functions that are reachable via tail calls.
96 DenseSet<const BinaryFunction *> TailCallTargetFuncs;
97
98 // Cached results from a CallerCalleePair to a unique call path between them.
99 DenseMap<CallerCalleePair, std::vector<uint64_t>> UniquePaths;
100 // Cached results from CallerCalleePair to the number of available call paths.
101 DenseMap<CallerCalleePair, uint64_t> NonUniquePaths;
102
103 DenseSet<BinaryFunction *> Visiting;
104
105 // Number of tail call paths to the target found by the current search, which
106 // stops once it finds more than one.
107 uint64_t NumFoundPaths = 0;
108
109#if LLVM_ENABLE_STATS
110 DenseSet<std::pair<uint64_t, uint64_t>> ReachableViaUniquePaths;
111 DenseSet<std::pair<uint64_t, uint64_t>> Unreachables;
112 DenseSet<std::pair<uint64_t, uint64_t>> ReachableViaMultiPaths;
113#endif
114};
115} // end namespace sampleprof
116} // end namespace llvm
117
118#endif
119