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 19 namespace llvm { 20 namespace sampleprof { 21 22 class ProfiledBinary; 23 struct BinaryFunction; 24 25 class MissingFrameInferrer { 26 public: MissingFrameInferrer(ProfiledBinary * Binary)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 39 private: 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 { operatorPairHash90 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