1 //===--- PseudoProbe.h - Pseudo probe decoding utilities ---------*- 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 #ifndef LLVM_TOOLS_LLVM_PROFGEN_PSEUDOPROBE_H
9 #define LLVM_TOOLS_LLVM_PROFGEN_PSEUDOPROBE_H
10 
11 #include "llvm/ADT/StringRef.h"
12 #include "llvm/ADT/Twine.h"
13 #include "llvm/IR/PseudoProbe.h"
14 #include "llvm/Support/raw_ostream.h"
15 #include "llvm/Transforms/IPO/SampleProfileProbe.h"
16 #include <algorithm>
17 #include <set>
18 #include <sstream>
19 #include <string>
20 #include <unordered_map>
21 #include <unordered_set>
22 #include <vector>
23 
24 namespace llvm {
25 namespace sampleprof {
26 
27 enum PseudoProbeAttributes { TAILCALL = 1, DANGLING = 2 };
28 
29 // Use func GUID and index as the location info of the inline site
30 using InlineSite = std::tuple<uint64_t, uint32_t>;
31 
32 struct PseudoProbe;
33 
34 // Tree node to represent the inline relation and its inline site, we use a
35 // dummy root in the PseudoProbeDecoder to lead the tree, the outlined
36 // function will directly be the children of the dummy root. For the inlined
37 // function, all the inlinee will be connected to its inlineer, then further to
38 // its outlined function. Pseudo probes originating from the function stores the
39 // tree's leaf node which we can process backwards to get its inline context
40 class PseudoProbeInlineTree {
41   std::vector<PseudoProbe *> ProbeVector;
42 
43   struct InlineSiteHash {
operatorInlineSiteHash44     uint64_t operator()(const InlineSite &Site) const {
45       return std::get<0>(Site) ^ std::get<1>(Site);
46     }
47   };
48   using InlinedProbeTreeMap =
49       std::unordered_map<InlineSite, std::unique_ptr<PseudoProbeInlineTree>,
50                          InlineSiteHash>;
51   InlinedProbeTreeMap Children;
52 
53 public:
54   // Inlinee function GUID
55   uint64_t GUID = 0;
56   // Inline site to indicate the location in its inliner. As the node could also
57   // be an outlined function, it will use a dummy InlineSite whose GUID and
58   // Index is 0 connected to the dummy root
59   InlineSite ISite;
60   // Used for decoding
61   uint32_t ChildrenToProcess = 0;
62   // Caller node of the inline site
63   PseudoProbeInlineTree *Parent;
64 
PseudoProbeInlineTree()65   PseudoProbeInlineTree(){};
PseudoProbeInlineTree(const InlineSite & Site)66   PseudoProbeInlineTree(const InlineSite &Site) : ISite(Site){};
67 
getOrAddNode(const InlineSite & Site)68   PseudoProbeInlineTree *getOrAddNode(const InlineSite &Site) {
69     auto Ret =
70         Children.emplace(Site, std::make_unique<PseudoProbeInlineTree>(Site));
71     Ret.first->second->Parent = this;
72     return Ret.first->second.get();
73   }
74 
getChildren()75   InlinedProbeTreeMap &getChildren() { return Children; }
getProbes()76   std::vector<PseudoProbe *> &getProbes() { return ProbeVector; }
addProbes(PseudoProbe * Probe)77   void addProbes(PseudoProbe *Probe) { ProbeVector.push_back(Probe); }
78   // Return false if it's a dummy inline site
hasInlineSite()79   bool hasInlineSite() const { return std::get<0>(ISite) != 0; }
80 };
81 
82 // Function descriptor decoded from .pseudo_probe_desc section
83 struct PseudoProbeFuncDesc {
84   uint64_t FuncGUID = 0;
85   uint64_t FuncHash = 0;
86   std::string FuncName;
87 
PseudoProbeFuncDescPseudoProbeFuncDesc88   PseudoProbeFuncDesc(uint64_t GUID, uint64_t Hash, StringRef Name)
89       : FuncGUID(GUID), FuncHash(Hash), FuncName(Name){};
90 
91   void print(raw_ostream &OS);
92 };
93 
94 // GUID to PseudoProbeFuncDesc map
95 using GUIDProbeFunctionMap = std::unordered_map<uint64_t, PseudoProbeFuncDesc>;
96 // Address to pseudo probes map.
97 using AddressProbesMap = std::unordered_map<uint64_t, std::list<PseudoProbe>>;
98 
99 /*
100 A pseudo probe has the format like below:
101   INDEX (ULEB128)
102   TYPE (uint4)
103     0 - block probe, 1 - indirect call, 2 - direct call
104   ATTRIBUTE (uint3)
105     1 - tail call, 2 - dangling
106   ADDRESS_TYPE (uint1)
107     0 - code address, 1 - address delta
108   CODE_ADDRESS (uint64 or ULEB128)
109   code address or address delta, depending on Flag
110 */
111 struct PseudoProbe {
112   uint64_t Address;
113   uint64_t GUID;
114   uint32_t Index;
115   PseudoProbeType Type;
116   uint8_t Attribute;
117   PseudoProbeInlineTree *InlineTree;
118   const static uint32_t PseudoProbeFirstId =
119       static_cast<uint32_t>(PseudoProbeReservedId::Last) + 1;
120 
PseudoProbePseudoProbe121   PseudoProbe(uint64_t Ad, uint64_t G, uint32_t I, PseudoProbeType K,
122               uint8_t At, PseudoProbeInlineTree *Tree)
123       : Address(Ad), GUID(G), Index(I), Type(K), Attribute(At),
124         InlineTree(Tree){};
125 
isEntryPseudoProbe126   bool isEntry() const { return Index == PseudoProbeFirstId; }
127 
isDanglingPseudoProbe128   bool isDangling() const {
129     return Attribute & static_cast<uint8_t>(PseudoProbeAttributes::DANGLING);
130   }
131 
isTailCallPseudoProbe132   bool isTailCall() const {
133     return Attribute & static_cast<uint8_t>(PseudoProbeAttributes::TAILCALL);
134   }
135 
isBlockPseudoProbe136   bool isBlock() const { return Type == PseudoProbeType::Block; }
isIndirectCallPseudoProbe137   bool isIndirectCall() const { return Type == PseudoProbeType::IndirectCall; }
isDirectCallPseudoProbe138   bool isDirectCall() const { return Type == PseudoProbeType::DirectCall; }
isCallPseudoProbe139   bool isCall() const { return isIndirectCall() || isDirectCall(); }
140 
getInlineTreeNodePseudoProbe141   PseudoProbeInlineTree *getInlineTreeNode() const { return InlineTree; }
142 
143   // Get the inlined context by traversing current inline tree backwards,
144   // each tree node has its InlineSite which is taken as the context.
145   // \p ContextStack is populated in root to leaf order
146   void getInlineContext(SmallVectorImpl<std::string> &ContextStack,
147                         const GUIDProbeFunctionMap &GUID2FuncMAP,
148                         bool ShowName) const;
149   // Helper function to get the string from context stack
150   std::string getInlineContextStr(const GUIDProbeFunctionMap &GUID2FuncMAP,
151                                   bool ShowName) const;
152   // Print pseudo probe while disassembling
153   void print(raw_ostream &OS, const GUIDProbeFunctionMap &GUID2FuncMAP,
154              bool ShowName);
155 };
156 
157 /*
158 Decode pseudo probe info from ELF section, used along with ELF reader
159 Two sections are decoded here:
160   1) \fn buildGUID2FunctionMap is responsible for .pseudo_probe_desc
161   section which encodes all function descriptors.
162   2) \fn buildAddress2ProbeMap is responsible for .pseudoprobe section
163     which encodes an inline function forest and each tree includes its
164     inlined function and all pseudo probes inside the function.
165 see \file MCPseudoProbe.h for the details of the section encoding format.
166 */
167 class PseudoProbeDecoder {
168   // GUID to PseudoProbeFuncDesc map.
169   GUIDProbeFunctionMap GUID2FuncDescMap;
170 
171   // Address to probes map.
172   AddressProbesMap Address2ProbesMap;
173 
174   // The dummy root of the inline trie, all the outlined function will directly
175   // be the children of the dummy root, all the inlined function will be the
176   // children of its inlineer. So the relation would be like:
177   // DummyRoot --> OutlinedFunc --> InlinedFunc1 --> InlinedFunc2
178   PseudoProbeInlineTree DummyInlineRoot;
179 
180   /// Points to the current location in the buffer.
181   const uint8_t *Data = nullptr;
182 
183   /// Points to the end of the buffer.
184   const uint8_t *End = nullptr;
185 
186   /// SectionName used for debug
187   std::string SectionName;
188 
189   // Decoding helper function
190   template <typename T> T readUnencodedNumber();
191   template <typename T> T readUnsignedNumber();
192   template <typename T> T readSignedNumber();
193   StringRef readString(uint32_t Size);
194 
195 public:
196   // Decode pseudo_probe_desc section to build GUID to PseudoProbeFuncDesc map.
197   void buildGUID2FuncDescMap(const uint8_t *Start, std::size_t Size);
198 
199   // Decode pseudo_probe section to build address to probes map.
200   void buildAddress2ProbeMap(const uint8_t *Start, std::size_t Size);
201 
202   // Print pseudo_probe_desc section info
203   void printGUID2FuncDescMap(raw_ostream &OS);
204 
205   // Print pseudo_probe section info, used along with show-disassembly
206   void printProbeForAddress(raw_ostream &OS, uint64_t Address);
207 
208   // Look up the probe of a call for the input address
209   const PseudoProbe *getCallProbeForAddr(uint64_t Address) const;
210 
211   const PseudoProbeFuncDesc *getFuncDescForGUID(uint64_t GUID) const;
212 
213   // Helper function to populate one probe's inline stack into
214   // \p InlineContextStack.
215   // Current leaf location info will be added if IncludeLeaf is true
216   // Example:
217   //  Current probe(bar:3) inlined at foo:2 then inlined at main:1
218   //  IncludeLeaf = true,  Output: [main:1, foo:2, bar:3]
219   //  IncludeLeaf = false, Output: [main:1, foo:2]
220   void
221   getInlineContextForProbe(const PseudoProbe *Probe,
222                            SmallVectorImpl<std::string> &InlineContextStack,
223                            bool IncludeLeaf) const;
224 
getAddress2ProbesMap()225   const AddressProbesMap &getAddress2ProbesMap() const {
226     return Address2ProbesMap;
227   }
228 
229   const PseudoProbeFuncDesc *
230   getInlinerDescForProbe(const PseudoProbe *Probe) const;
231 };
232 
233 } // end namespace sampleprof
234 } // end namespace llvm
235 
236 #endif
237