Coverage Report

Created: 2022-01-15 10:30

/Users/buildslave/jenkins/workspace/coverage/llvm-project/lldb/source/Plugins/TraceExporter/common/TraceHTR.h
Line
Count
Source (jump to first uncovered line)
1
//===-- TraceHTR.h --------------------------------------------------------===//
2
//
3
// Part of the LLVM Project, under the Apache
4
// License v2.0 with LLVM Exceptions.// See https://llvm.org/LICENSE.txt for
5
// license information.// SPDX-License-Identifier: Apache-2.0 WITH
6
// LLVM-exception
7
//
8
//===----------------------------------------------------------------------===//
9
10
#ifndef LLDB_TARGET_TRACE_HTR_H
11
#define LLDB_TARGET_TRACE_HTR_H
12
13
#include "lldb/Target/Thread.h"
14
#include "lldb/Target/Trace.h"
15
16
#include <unordered_map>
17
#include <unordered_set>
18
19
namespace lldb_private {
20
21
/// Metadata associated with an HTR block
22
/// See lldb/docs/htr.rst for comprehensive HTR documentation
23
class HTRBlockMetadata {
24
public:
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
0
        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
  ///     None if no function is called from this block.
62
  llvm::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
82
private:
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
91
class HTRBlock {
92
public:
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
0
      : 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
126
private:
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
138
class IHTRLayer {
139
public:
140
  /// Construct new HTR layer.
141
  //
142
  /// \param[in] id
143
  ///     The layer's id.
144
0
  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
0
  virtual ~IHTRLayer() = default;
185
186
protected:
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
193
class HTRInstructionLayer : public IHTRLayer {
194
public:
195
  /// Construct new instruction layer.
196
  //
197
  /// \param[in] id
198
  ///     The layer's id.
199
0
  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, None otherwise.
219
  void AddCallInstructionMetadata(lldb::addr_t load_addr,
220
                                  llvm::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
229
private:
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 (None if function
238
  // name can't be determined)
239
  std::unordered_map<lldb::addr_t, llvm::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
244
class HTRBlockLayer : public IHTRLayer {
245
public:
246
  /// Construct new block layer.
247
  //
248
  /// \param[in] id
249
  ///     The layer's id.
250
0
  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
291
private:
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
299
typedef std::unique_ptr<lldb_private::HTRBlockLayer> HTRBlockLayerUP;
300
typedef std::unique_ptr<lldb_private::HTRInstructionLayer>
301
    HTRInstructionLayerUP;
302
303
/// Top-level HTR class
304
/// See lldb/docs/htr.rst for comprehensive HTR documentation
305
class TraceHTR {
306
307
public:
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
348
private:
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
356
llvm::json::Value toJSON(const TraceHTR &htr);
357
llvm::json::Value toJSON(const HTRBlock &block);
358
llvm::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
405
HTRBlockLayerUP BasicSuperBlockMerge(IHTRLayer &layer);
406
407
} // namespace lldb_private
408
409
#endif // LLDB_TARGET_TRACE_HTR_H