117 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef LLVM_TOOLS_LLVM_PROFGEN_MISSINGFRAMEINFERRER_H10#define LLVM_TOOLS_LLVM_PROFGEN_MISSINGFRAMEINFERRER_H11 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 tail35 // 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 and43 // target frame address. Append the unique path prefix (not including `To`) to44 // `UniquePath` if exists. Return the whether this's a unqiue tail call45 // path. The source/dest frame will typically be a pair of adjacent frame46 // 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 target51 // function. Output the unique path prefix (not including `To`) in52 // `UniquePath` if exists. Return the number of possibly availabe tail call53 // 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 target58 // function. Output the unique path prefix (not including `To`) in59 // `UniquePath` if exists. Return the number of possibly availabe tail call60 // 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 first67 // populated with static call edges but then trimmed down to dynamic call68 // 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 first72 // populated with static call edges but then trimmed down to dynamic call73 // 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_STATS108 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#endif112};113} // end namespace sampleprof114} // end namespace llvm115 116#endif117