1//===-- TraceHTR.h --------------------------------------------------------===//
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 LLDB_TARGET_TRACE_HTR_H
10#define LLDB_TARGET_TRACE_HTR_H
11
12#include "lldb/Target/Thread.h"
13#include "lldb/Target/Trace.h"
14
15#include <optional>
16#include <unordered_map>
17#include <unordered_set>
18
19namespace lldb_private {
20
21/// Metadata associated with an HTR block
22/// See lldb/docs/htr.rst for comprehensive HTR documentation
23class HTRBlockMetadata {
24public:
25 /// Constructor for a block's metadata.
26 ///
27 /// \param[in] first_instruction_load_address
28 /// The load address of the block's first instruction.
29 ///
30 /// \param[in] num_instructions
31 /// The total number of instructions in the block.
32 ///
33 /// \param[in] func_calls
34 /// The map of a function name to the number of times it is called from
35 /// the block.
36 HTRBlockMetadata(lldb::addr_t first_instruction_load_address,
37 size_t num_instructions,
38 llvm::DenseMap<ConstString, size_t> &&func_calls)
39 : m_first_instruction_load_address(first_instruction_load_address),
40 m_num_instructions(num_instructions), m_func_calls(func_calls) {}
41
42 /// Merge two \a HTRBlockMetadata in place.
43 ///
44 /// \param[in][out] merged_metadata
45 /// Metadata that metadata_to_merge will be merged into.
46 ///
47 /// \param[in] metadata_to_merge
48 /// Metadata to merge into merged_metadata.
49 static void MergeMetadata(HTRBlockMetadata &merged_metadata,
50 HTRBlockMetadata const &metadata_to_merge);
51 /// Get the number of instructions in the block.
52 ///
53 /// \return
54 /// The number of instructions in the block.
55 size_t GetNumInstructions() const;
56
57 /// Get the name of the most frequently called function from the block.
58 ///
59 /// \return
60 /// The name of the function that is called the most from this block or
61 /// std::nullopt if no function is called from this block.
62 std::optional<llvm::StringRef> GetMostFrequentlyCalledFunction() const;
63
64 /// Get the load address of the first instruction in the block.
65 ///
66 /// \return
67 /// The load address of the first instruction in the block.
68 lldb::addr_t GetFirstInstructionLoadAddress() const;
69
70 /// Get the function calls map for the block.
71 /// Function calls are identified in the instruction layer by finding 'call'
72 /// instructions and determining the function they are calling. As these
73 /// instructions are merged into blocks, we merge these different function
74 /// calls into a single map containing the function names to the number of
75 /// times it is called from this block.
76 ///
77 /// \return
78 /// The mapping of function name to the number of times it is called from
79 /// this block.
80 llvm::DenseMap<ConstString, size_t> const &GetFunctionCalls() const;
81
82private:
83 lldb::addr_t m_first_instruction_load_address;
84 size_t m_num_instructions;
85 llvm::DenseMap<ConstString, size_t> m_func_calls;
86};
87
88/// Block structure representing a sequence of trace "units" (ie instructions).
89/// Sequences of blocks are merged to create a new, single block
90/// See lldb/docs/htr.rst for comprehensive HTR documentation
91class HTRBlock {
92public:
93 /// Constructor for a block of an HTR layer.
94 ///
95 /// \param[in] offset
96 /// The offset of the start of this block in the previous layer.
97 ///
98 /// \param[in] size
99 /// Number of blocks/instructions that make up this block in the previous
100 /// layer.
101 ///
102 /// \param[in] metadata
103 /// General metadata for this block.
104 HTRBlock(size_t offset, size_t size, HTRBlockMetadata metadata)
105 : m_offset(offset), m_size(size), m_metadata(metadata) {}
106
107 /// Get the offset of the start of this block in the previous layer.
108 ///
109 /// \return
110 /// The offset of the block.
111 size_t GetOffset() const;
112
113 /// Get the number of blocks/instructions that make up this block in the
114 /// previous layer.
115 ///
116 /// \return
117 /// The size of the block.
118 size_t GetSize() const;
119
120 /// Get the metadata for this block.
121 ///
122 /// \return
123 /// The metadata of the block.
124 HTRBlockMetadata const &GetMetadata() const;
125
126private:
127 /// Offset in the previous layer
128 size_t m_offset;
129 /// Number of blocks/instructions that make up this block in the previous
130 /// layer
131 size_t m_size;
132 /// General metadata for this block
133 HTRBlockMetadata m_metadata;
134};
135
136/// HTR layer interface
137/// See lldb/docs/htr.rst for comprehensive HTR documentation
138class IHTRLayer {
139public:
140 /// Construct new HTR layer.
141 //
142 /// \param[in] id
143 /// The layer's id.
144 IHTRLayer(size_t id) : m_layer_id(id) {}
145
146 /// Get the ID of the layer.
147 ///
148 /// \return
149 /// The layer ID of this layer.
150 size_t GetLayerId() const;
151
152 /// Get the metadata of a unit (instruction or block) in the layer.
153 ///
154 /// \param[in] index
155 /// The position of the unit in the layer.
156 ///
157 /// \return
158 /// The metadata of the unit in the layer.
159 virtual HTRBlockMetadata GetMetadataByIndex(size_t index) const = 0;
160
161 /// Get the total number of units (instruction or block) in this layer.
162 ///
163 /// \return
164 /// The total number of units in the layer.
165 virtual size_t GetNumUnits() const = 0;
166
167 /// Creates a new block from the result of merging a contiguous sequence of
168 /// "units" (instructions or blocks depending on layer type) in this layer
169 /// This allows the implementation class to decide how to store/generate this
170 /// metadata. For example, in the case of the instruction layer we want to
171 /// lazily generate this metadata instead of storing it for each instruction.
172 ///
173 /// \param[in] start_unit_index
174 /// The index of the first unit to be merged.
175 ///
176 /// \param[in] num_units
177 /// The number of units to be merged. Must be >= 1, since merging 0 blocks
178 /// does not make sense.
179 ///
180 /// \return
181 /// A new block instance representing the merge of the specified units.
182 HTRBlock MergeUnits(size_t start_unit_index, size_t num_units);
183
184 virtual ~IHTRLayer() = default;
185
186protected:
187 /// ID of the layer.
188 size_t m_layer_id;
189};
190
191/// "Base" layer of HTR representing the dynamic instructions of the trace.
192/// See lldb/docs/htr.rst for comprehensive HTR documentation
193class HTRInstructionLayer : public IHTRLayer {
194public:
195 /// Construct new instruction layer.
196 //
197 /// \param[in] id
198 /// The layer's id.
199 HTRInstructionLayer(size_t id) : IHTRLayer(id) {}
200
201 size_t GetNumUnits() const override;
202
203 HTRBlockMetadata GetMetadataByIndex(size_t index) const override;
204
205 /// Get the dynamic instruction trace.
206 ///
207 /// \return
208 /// The dynamic instruction trace.
209 llvm::ArrayRef<lldb::addr_t> GetInstructionTrace() const;
210
211 /// Add metadata for a 'call' instruction of the trace.
212 ///
213 /// \param[in] load_addr
214 /// The load address of the 'call' instruction.
215 ///
216 /// \param[in] func_name
217 /// The name of the function the 'call' instruction is calling if it can
218 /// be determined, std::nullopt otherwise.
219 void AddCallInstructionMetadata(lldb::addr_t load_addr,
220 std::optional<ConstString> func_name);
221
222 /// Append the load address of an instruction to the dynamic instruction
223 /// trace.
224 ///
225 /// \param[in] load_addr
226 /// The load address of the instruction.
227 void AppendInstruction(lldb::addr_t load_addr);
228
229private:
230 // Dynamic instructions of trace are stored in chronological order.
231 std::vector<lldb::addr_t> m_instruction_trace;
232 // Only store metadata for instructions of interest (call instructions)
233 // If we stored metadata for each instruction this would be wasteful since
234 // most instructions don't contain useful metadata
235
236 // This map contains the load address of all the call instructions.
237 // load address maps to the name of the function it calls (std::nullopt if
238 // function name can't be determined)
239 std::unordered_map<lldb::addr_t, std::optional<ConstString>> m_call_isns;
240};
241
242/// HTR layer composed of blocks of the trace.
243/// See lldb/docs/htr.rst for comprehensive HTR documentation
244class HTRBlockLayer : public IHTRLayer {
245public:
246 /// Construct new block layer.
247 //
248 /// \param[in] id
249 /// The layer's id.
250 HTRBlockLayer(size_t id) : IHTRLayer(id) {}
251
252 size_t GetNumUnits() const override;
253
254 HTRBlockMetadata GetMetadataByIndex(size_t index) const override;
255
256 /// Get an \a HTRBlock from its block id.
257 ///
258 /// \param[in] block_id
259 /// The id of the block to retrieve.
260 ///
261 /// \return
262 /// The \a HTRBlock with the specified id, nullptr if no there is no block
263 /// in the layer with the specified block id.
264 HTRBlock const *GetBlockById(size_t block_id) const;
265
266 /// Get the block ID trace for this layer.
267 /// This block ID trace stores the block ID of each block that occured in the
268 /// trace and the block defs map maps block ID to the corresponding \a
269 /// HTRBlock.
270 ///
271 /// \return
272 /// The block ID trace for this layer.
273 llvm::ArrayRef<size_t> GetBlockIdTrace() const;
274
275 /// Appends a new block to the layer.
276 ///
277 /// \param[in] block_id
278 /// The block id of the new block.
279 ///
280 /// \param[in] block
281 /// The new \a HTRBlock to be appended to the layer. This block is moved
282 /// into the layer.
283 void AppendNewBlock(size_t block_id, HTRBlock &&block);
284
285 /// Appends a repeated block to the layer.
286 ///
287 /// \param[in] block_id
288 /// The block id of the repeated block.
289 void AppendRepeatedBlock(size_t block_id);
290
291private:
292 /// Maps a unique Block ID to the corresponding HTRBlock
293 std::unordered_map<size_t, HTRBlock> m_block_defs;
294 /// Reduce memory footprint by just storing a trace of block IDs and use
295 /// m_block_defs to map a block_id to its corresponding HTRBlock
296 std::vector<size_t> m_block_id_trace;
297};
298
299typedef std::unique_ptr<lldb_private::HTRBlockLayer> HTRBlockLayerUP;
300typedef std::unique_ptr<lldb_private::HTRInstructionLayer>
301 HTRInstructionLayerUP;
302
303/// Top-level HTR class
304/// See lldb/docs/htr.rst for comprehensive HTR documentation
305class TraceHTR {
306
307public:
308 /// Constructor for a trace's HTR.
309 ///
310 /// \param[in] thread
311 /// The thread the trace belongs to.
312 ///
313 /// \param[in] cursor
314 /// The trace cursor that gives access to the trace's contents.
315 TraceHTR(Thread &thread, TraceCursor &cursor);
316
317 /// Executes passes on the HTR layers until no further
318 /// summarization/compression is achieved
319 void ExecutePasses();
320
321 /// Export HTR layers to the specified format and outfile.
322 ///
323 /// \param[in] outfile
324 /// The file that the exported HTR data will be written to.
325 ///
326 /// \return
327 /// Success if the export is successful, Error otherwise.
328 llvm::Error Export(std::string outfile);
329
330 /// Get the block layers of this HTR.
331 ///
332 /// \return
333 /// The block layers of this HTR.
334 llvm::ArrayRef<HTRBlockLayerUP> GetBlockLayers() const;
335
336 /// Get the instruction layer of this HTR.
337 ///
338 /// \return
339 /// The instruction layer of this HTR.
340 HTRInstructionLayer const &GetInstructionLayer() const;
341
342 /// Add a new block layer to this HTR.
343 ///
344 /// \param[in]
345 /// The new block layer to be added.
346 void AddNewBlockLayer(HTRBlockLayerUP &&block_layer);
347
348private:
349 // There is a single instruction layer per HTR
350 HTRInstructionLayerUP m_instruction_layer_up;
351 // There are one or more block layers per HTR
352 std::vector<HTRBlockLayerUP> m_block_layer_ups;
353};
354
355// Serialization functions for exporting HTR to Chrome Trace Format
356llvm::json::Value toJSON(const TraceHTR &htr);
357llvm::json::Value toJSON(const HTRBlock &block);
358llvm::json::Value toJSON(const HTRBlockMetadata &metadata);
359
360/// The HTR passes are defined below:
361
362/// Creates a new layer by merging the "basic super blocks" in the current layer
363///
364/// A "basic super block" is the longest sequence of blocks that always occur in
365/// the same order. (The concept is akin to “Basic Block" in compiler theory,
366/// but refers to dynamic occurrences rather than CFG nodes)
367///
368/// Procedure to find all basic super blocks:
369//
370/// - For each block, compute the number of distinct predecessor and
371/// successor blocks.
372/// Predecessor - the block that occurs directly before (to the left of)
373/// the current block Successor - the block that occurs directly after
374/// (to the right of) the current block
375/// - A block with more than one distinct successor is always the start of a
376/// super block, the super block will continue until the next block with
377/// more than one distinct predecessor or successor.
378///
379/// The implementation makes use of two terms - 'heads' and 'tails' known as
380/// the 'endpoints' of a basic super block:
381/// A 'head' is defined to be a block in the trace that doesn't have a
382/// unique predecessor
383/// A 'tail' is defined to be a block in the trace that doesn't have a
384/// unique successor
385///
386/// A basic super block is defined to be a sequence of blocks between two
387/// endpoints
388///
389/// A head represents the start of the next group, so the current group
390/// ends at the block preceding the head and the next group begins with
391/// this head block
392///
393/// A tail represents the end of the current group, so the current group
394/// ends with the tail block and the next group begins with the
395/// following block.
396///
397/// See lldb/docs/htr.rst for comprehensive HTR documentation
398///
399/// \param[in] layer
400/// The layer to execute the pass on.
401///
402/// \return
403/// A new layer instance representing the merge of blocks in the
404/// previous layer
405HTRBlockLayerUP BasicSuperBlockMerge(IHTRLayer &layer);
406
407} // namespace lldb_private
408
409#endif // LLDB_TARGET_TRACE_HTR_H
410

source code of lldb/source/Plugins/TraceExporter/common/TraceHTR.h