llvm/tools/llvm-profgen/MissingFrameInferrer.h

   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:
  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 {
  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