410 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef LLDB_TARGET_TRACE_HTR_H10#define LLDB_TARGET_TRACE_HTR_H11 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 block22/// See lldb/docs/htr.rst for comprehensive HTR documentation23class HTRBlockMetadata {24public:25 /// Constructor for a block's metadata.26 ///27 /// \param[in] first_instruction_load_address28 /// The load address of the block's first instruction.29 ///30 /// \param[in] num_instructions31 /// The total number of instructions in the block.32 ///33 /// \param[in] func_calls34 /// The map of a function name to the number of times it is called from35 /// 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_metadata45 /// Metadata that metadata_to_merge will be merged into.46 ///47 /// \param[in] metadata_to_merge48 /// 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 /// \return54 /// 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 /// \return60 /// The name of the function that is called the most from this block or61 /// 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 /// \return67 /// 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 these73 /// instructions are merged into blocks, we merge these different function74 /// calls into a single map containing the function names to the number of75 /// times it is called from this block.76 ///77 /// \return78 /// The mapping of function name to the number of times it is called from79 /// 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 block90/// See lldb/docs/htr.rst for comprehensive HTR documentation91class HTRBlock {92public:93 /// Constructor for a block of an HTR layer.94 ///95 /// \param[in] offset96 /// The offset of the start of this block in the previous layer.97 ///98 /// \param[in] size99 /// Number of blocks/instructions that make up this block in the previous100 /// layer.101 ///102 /// \param[in] metadata103 /// 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 /// \return110 /// The offset of the block.111 size_t GetOffset() const;112 113 /// Get the number of blocks/instructions that make up this block in the114 /// previous layer.115 ///116 /// \return117 /// The size of the block.118 size_t GetSize() const;119 120 /// Get the metadata for this block.121 ///122 /// \return123 /// The metadata of the block.124 HTRBlockMetadata const &GetMetadata() const;125 126private:127 /// Offset in the previous layer128 size_t m_offset;129 /// Number of blocks/instructions that make up this block in the previous130 /// layer131 size_t m_size;132 /// General metadata for this block133 HTRBlockMetadata m_metadata;134};135 136/// HTR layer interface137/// See lldb/docs/htr.rst for comprehensive HTR documentation138class IHTRLayer {139public:140 /// Construct new HTR layer.141 //142 /// \param[in] id143 /// The layer's id.144 IHTRLayer(size_t id) : m_layer_id(id) {}145 146 /// Get the ID of the layer.147 ///148 /// \return149 /// 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] index155 /// The position of the unit in the layer.156 ///157 /// \return158 /// 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 /// \return164 /// 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 of168 /// "units" (instructions or blocks depending on layer type) in this layer169 /// This allows the implementation class to decide how to store/generate this170 /// metadata. For example, in the case of the instruction layer we want to171 /// lazily generate this metadata instead of storing it for each instruction.172 ///173 /// \param[in] start_unit_index174 /// The index of the first unit to be merged.175 ///176 /// \param[in] num_units177 /// The number of units to be merged. Must be >= 1, since merging 0 blocks178 /// does not make sense.179 ///180 /// \return181 /// 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 documentation193class HTRInstructionLayer : public IHTRLayer {194public:195 /// Construct new instruction layer.196 //197 /// \param[in] id198 /// 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 /// \return208 /// 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_addr214 /// The load address of the 'call' instruction.215 ///216 /// \param[in] func_name217 /// The name of the function the 'call' instruction is calling if it can218 /// 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 instruction223 /// trace.224 ///225 /// \param[in] load_addr226 /// 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 since234 // most instructions don't contain useful metadata235 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 if238 // 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 documentation244class HTRBlockLayer : public IHTRLayer {245public:246 /// Construct new block layer.247 //248 /// \param[in] id249 /// 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_id259 /// The id of the block to retrieve.260 ///261 /// \return262 /// The \a HTRBlock with the specified id, nullptr if no there is no block263 /// 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 the268 /// trace and the block defs map maps block ID to the corresponding \a269 /// HTRBlock.270 ///271 /// \return272 /// 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_id278 /// The block id of the new block.279 ///280 /// \param[in] block281 /// The new \a HTRBlock to be appended to the layer. This block is moved282 /// 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_id288 /// 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 HTRBlock293 std::unordered_map<size_t, HTRBlock> m_block_defs;294 /// Reduce memory footprint by just storing a trace of block IDs and use295 /// m_block_defs to map a block_id to its corresponding HTRBlock296 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 class304/// See lldb/docs/htr.rst for comprehensive HTR documentation305class TraceHTR {306 307public:308 /// Constructor for a trace's HTR.309 ///310 /// \param[in] thread311 /// The thread the trace belongs to.312 ///313 /// \param[in] cursor314 /// 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 further318 /// summarization/compression is achieved319 void ExecutePasses();320 321 /// Export HTR layers to the specified format and outfile.322 ///323 /// \param[in] outfile324 /// The file that the exported HTR data will be written to.325 ///326 /// \return327 /// 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 /// \return333 /// The block layers of this HTR.334 llvm::ArrayRef<HTRBlockLayerUP> GetBlockLayers() const;335 336 /// Get the instruction layer of this HTR.337 ///338 /// \return339 /// 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 HTR350 HTRInstructionLayerUP m_instruction_layer_up;351 // There are one or more block layers per HTR352 std::vector<HTRBlockLayerUP> m_block_layer_ups;353};354 355// Serialization functions for exporting HTR to Chrome Trace Format356llvm::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 layer363///364/// A "basic super block" is the longest sequence of blocks that always occur in365/// 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 and371/// successor blocks.372/// Predecessor - the block that occurs directly before (to the left of)373/// the current block Successor - the block that occurs directly after374/// (to the right of) the current block375/// - A block with more than one distinct successor is always the start of a376/// super block, the super block will continue until the next block with377/// more than one distinct predecessor or successor.378///379/// The implementation makes use of two terms - 'heads' and 'tails' known as380/// the 'endpoints' of a basic super block:381/// A 'head' is defined to be a block in the trace that doesn't have a382/// unique predecessor383/// A 'tail' is defined to be a block in the trace that doesn't have a384/// unique successor385///386/// A basic super block is defined to be a sequence of blocks between two387/// endpoints388///389/// A head represents the start of the next group, so the current group390/// ends at the block preceding the head and the next group begins with391/// this head block392///393/// A tail represents the end of the current group, so the current group394/// ends with the tail block and the next group begins with the395/// following block.396///397/// See lldb/docs/htr.rst for comprehensive HTR documentation398///399/// \param[in] layer400/// The layer to execute the pass on.401///402/// \return403/// A new layer instance representing the merge of blocks in the404/// previous layer405HTRBlockLayerUP BasicSuperBlockMerge(IHTRLayer &layer);406 407} // namespace lldb_private408 409#endif // LLDB_TARGET_TRACE_HTR_H410