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

   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
  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         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
  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       : 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   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
 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   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
 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 (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
 244 class HTRBlockLayer : public IHTRLayer {
 245 public:
 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
 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