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 410