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

//===-- TraceHTR.h --------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#ifndef LLDB_TARGET_TRACE_HTR_H
#define LLDB_TARGET_TRACE_HTR_H

#include "lldb/Target/Thread.h"
#include "lldb/Target/Trace.h"

#include <optional>
#include <unordered_map>
#include <unordered_set>

namespace lldb_private {

/// Metadata associated with an HTR block
/// See lldb/docs/htr.rst for comprehensive HTR documentation
class HTRBlockMetadata { … };

/// Block structure representing a sequence of trace "units" (ie instructions).
/// Sequences of blocks are merged to create a new, single block
/// See lldb/docs/htr.rst for comprehensive HTR documentation
class HTRBlock { … };

/// HTR layer interface
/// See lldb/docs/htr.rst for comprehensive HTR documentation
class IHTRLayer { … };

/// "Base" layer of HTR representing the dynamic instructions of the trace.
/// See lldb/docs/htr.rst for comprehensive HTR documentation
class HTRInstructionLayer : public IHTRLayer { … };

/// HTR layer composed of blocks of the trace.
/// See lldb/docs/htr.rst for comprehensive HTR documentation
class HTRBlockLayer : public IHTRLayer { … };

HTRBlockLayerUP;
HTRInstructionLayerUP;

/// Top-level HTR class
/// See lldb/docs/htr.rst for comprehensive HTR documentation
class TraceHTR { … };

// Serialization functions for exporting HTR to Chrome Trace Format
llvm::json::Value toJSON(const TraceHTR &htr);
llvm::json::Value toJSON(const HTRBlock &block);
llvm::json::Value toJSON(const HTRBlockMetadata &metadata);

/// The HTR passes are defined below:

/// Creates a new layer by merging the "basic super blocks" in the current layer
///
/// A "basic super block" is the longest sequence of blocks that always occur in
/// the same order. (The concept is akin to “Basic Block" in compiler theory,
/// but refers to dynamic occurrences rather than CFG nodes)
///
/// Procedure to find all basic super blocks:
//
///   - For each block, compute the number of distinct predecessor and
///   successor blocks.
///       Predecessor - the block that occurs directly before (to the left of)
///       the current block Successor  - the block that occurs directly after
///       (to the right of) the current block
///   - A block with more than one distinct successor is always the start of a
///   super block, the super block will continue until the next block with
///   more than one distinct predecessor or successor.
///
/// The implementation makes use of two terms - 'heads' and 'tails' known as
/// the 'endpoints' of a basic super block:
///   A 'head' is defined to be a block in the trace that doesn't have a
///   unique predecessor
///   A 'tail' is defined to be a block in the trace that doesn't have a
///   unique successor
///
/// A basic super block is defined to be a sequence of blocks between two
/// endpoints
///
/// A head represents the start of the next group, so the current group
/// ends at the block preceding the head and the next group begins with
/// this head block
///
/// A tail represents the end of the current group, so the current group
/// ends with the tail block and the next group begins with the
/// following block.
///
/// See lldb/docs/htr.rst for comprehensive HTR documentation
///
/// \param[in] layer
///     The layer to execute the pass on.
///
/// \return
///     A new layer instance representing the merge of blocks in the
///     previous layer
HTRBlockLayerUP BasicSuperBlockMerge(IHTRLayer &layer);

} // namespace lldb_private

#endif // LLDB_TARGET_TRACE_HTR_H