text: //===-- TraceHTR.cpp ------------------------------------------------------===//
  //
  // 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
  //
  //===----------------------------------------------------------------------===//
  
  #include "TraceHTR.h"
  
  #include "lldb/Symbol/Function.h"
  #include "lldb/Target/Process.h"
  #include "lldb/Target/Target.h"
  #include "llvm/Support/JSON.h"
  #include <sstream>
  #include <string>
  
  using namespace lldb_private;
  using namespace lldb;
  
  size_t HTRBlockMetadata::GetNumInstructions() const {
    return m_num_instructions;
  }
  
  llvm::Optional<llvm::StringRef>
  HTRBlockMetadata::GetMostFrequentlyCalledFunction() const {
    size_t max_ncalls = 0;
    llvm::Optional<llvm::StringRef> max_name = llvm::None;
    for (const auto &it : m_func_calls) {
      ConstString name = it.first;
      size_t ncalls = it.second;
      if (ncalls > max_ncalls) {
        max_ncalls = ncalls;
        max_name = name.GetStringRef();
      }
    }
    return max_name;
  }
  
  llvm::DenseMap<ConstString, size_t> const &
  HTRBlockMetadata::GetFunctionCalls() const {
    return m_func_calls;
  }
  
  lldb::addr_t HTRBlockMetadata::GetFirstInstructionLoadAddress() const {
    return m_first_instruction_load_address;
  }
  
  size_t HTRBlock::GetOffset() const { return m_offset; }
  
  size_t HTRBlock::GetSize() const { return m_size; }
  
  HTRBlockMetadata const &HTRBlock::GetMetadata() const { return m_metadata; }
  
  llvm::ArrayRef<HTRBlockLayerUP> TraceHTR::GetBlockLayers() const {
    return m_block_layer_ups;
  }
  
  HTRInstructionLayer const &TraceHTR::GetInstructionLayer() const {
    return *m_instruction_layer_up;
  }
  
  void TraceHTR::AddNewBlockLayer(HTRBlockLayerUP &&block_layer) {
    m_block_layer_ups.emplace_back(std::move(block_layer));
  }
  
  size_t IHTRLayer::GetLayerId() const { return m_layer_id; }
  
  void HTRBlockLayer::AppendNewBlock(size_t block_id, HTRBlock &&block) {
    m_block_id_trace.emplace_back(block_id);
    m_block_defs.emplace(block_id, block);
  }
  
  void HTRBlockLayer::AppendRepeatedBlock(size_t block_id) {
    m_block_id_trace.emplace_back(block_id);
  }
  
  llvm::ArrayRef<lldb::addr_t> HTRInstructionLayer::GetInstructionTrace() const {
    return m_instruction_trace;
  }
  
  void HTRInstructionLayer::AddCallInstructionMetadata(
      lldb::addr_t load_addr, llvm::Optional<ConstString> func_name) {
    m_call_isns.emplace(load_addr, func_name);
  }
  
  void HTRInstructionLayer::AppendInstruction(lldb::addr_t load_addr) {
    m_instruction_trace.emplace_back(load_addr);
  }
  
  HTRBlock const *HTRBlockLayer::GetBlockById(size_t block_id) const {
    auto block_it = m_block_defs.find(block_id);
    if (block_it == m_block_defs.end())
      return nullptr;
    else
      return &block_it->second;
  }
  
  llvm::ArrayRef<size_t> HTRBlockLayer::GetBlockIdTrace() const {
    return m_block_id_trace;
  }
  
  size_t HTRBlockLayer::GetNumUnits() const { return m_block_id_trace.size(); }
  
  HTRBlockMetadata HTRInstructionLayer::GetMetadataByIndex(size_t index) const {
    lldb::addr_t instruction_load_address = m_instruction_trace[index];
    llvm::DenseMap<ConstString, size_t> func_calls;
  
    auto func_name_it = m_call_isns.find(instruction_load_address);
    if (func_name_it != m_call_isns.end()) {
      if (llvm::Optional<ConstString> func_name = func_name_it->second) {
        func_calls[*func_name] = 1;
      }
    }
    return {instruction_load_address, 1, std::move(func_calls)};
  }
  
  size_t HTRInstructionLayer::GetNumUnits() const {
    return m_instruction_trace.size();
  }
  
  HTRBlockMetadata HTRBlockLayer::GetMetadataByIndex(size_t index) const {
    size_t block_id = m_block_id_trace[index];
    HTRBlock block = m_block_defs.find(block_id)->second;
    return block.GetMetadata();
  }
  
  TraceHTR::TraceHTR(Thread &thread, TraceCursor &cursor)
      : m_instruction_layer_up(std::make_unique<HTRInstructionLayer>(0)) {
  
    // Move cursor to the first instruction in the trace
    cursor.SetForwards(true);
    cursor.Seek(0, TraceCursor::SeekType::Set);
  
    Target &target = thread.GetProcess()->GetTarget();
    auto function_name_from_load_address =
        [&](lldb::addr_t load_address) -> llvm::Optional<ConstString> {
      lldb_private::Address pc_addr;
      SymbolContext sc;
      if (target.ResolveLoadAddress(load_address, pc_addr) &&
          pc_addr.CalculateSymbolContext(&sc))
        return sc.GetFunctionName()
                   ? llvm::Optional<ConstString>(sc.GetFunctionName())
                   : llvm::None;
      else
        return llvm::None;
    };
  
    bool more_data_in_trace = true;
    while (more_data_in_trace) {
      if (cursor.IsError()) {
        // Append a load address of 0 for all instructions that an error occured
        // while decoding.
        // TODO: Make distinction between errors by storing the error messages.
        // Currently, all errors are treated the same.
        m_instruction_layer_up->AppendInstruction(0);
        more_data_in_trace = cursor.Next();
      } else {
        lldb::addr_t current_instruction_load_address = cursor.GetLoadAddress();
        lldb::TraceInstructionControlFlowType current_instruction_type =
            cursor.GetInstructionControlFlowType();
  
        m_instruction_layer_up->AppendInstruction(
            current_instruction_load_address);
        more_data_in_trace = cursor.Next();
        if (current_instruction_type &
            lldb::eTraceInstructionControlFlowTypeCall) {
          if (more_data_in_trace && !cursor.IsError()) {
            m_instruction_layer_up->AddCallInstructionMetadata(
                current_instruction_load_address,
                function_name_from_load_address(cursor.GetLoadAddress()));
          } else {
            // Next instruction is not known - pass None to indicate the name
            // of the function being called is not known
            m_instruction_layer_up->AddCallInstructionMetadata(
                current_instruction_load_address, llvm::None);
          }
        }
      }
    }
  }
  
  void HTRBlockMetadata::MergeMetadata(
      HTRBlockMetadata &merged_metadata,
      HTRBlockMetadata const &metadata_to_merge) {
    merged_metadata.m_num_instructions += metadata_to_merge.m_num_instructions;
    for (const auto &it : metadata_to_merge.m_func_calls) {
      ConstString name = it.first;
      size_t num_calls = it.second;
      merged_metadata.m_func_calls[name] += num_calls;
    }
  }
  
  HTRBlock IHTRLayer::MergeUnits(size_t start_unit_index, size_t num_units) {
    // TODO: make this function take `end_unit_index` as a parameter instead of
    // unit and merge the range [start_unit_indx, end_unit_index] inclusive.
    HTRBlockMetadata merged_metadata = GetMetadataByIndex(start_unit_index);
    for (size_t i = start_unit_index + 1; i < start_unit_index + num_units; i++) {
      // merge the new metadata into merged_metadata
      HTRBlockMetadata::MergeMetadata(merged_metadata, GetMetadataByIndex(i));
    }
    return {start_unit_index, num_units, merged_metadata};
  }
  
  void TraceHTR::ExecutePasses() {
    auto are_passes_done = [](IHTRLayer &l1, IHTRLayer &l2) {
      return l1.GetNumUnits() == l2.GetNumUnits();
    };
    HTRBlockLayerUP current_block_layer_up =
        BasicSuperBlockMerge(*m_instruction_layer_up);
    HTRBlockLayer &current_block_layer = *current_block_layer_up;
    if (are_passes_done(*m_instruction_layer_up, *current_block_layer_up))
      return;
  
    AddNewBlockLayer(std::move(current_block_layer_up));
    while (true) {
      HTRBlockLayerUP new_block_layer_up =
          BasicSuperBlockMerge(current_block_layer);
      if (are_passes_done(current_block_layer, *new_block_layer_up))
        return;
  
      current_block_layer = *new_block_layer_up;
      AddNewBlockLayer(std::move(new_block_layer_up));
    }
  }
  
  llvm::Error TraceHTR::Export(std::string outfile) {
    std::error_code ec;
    llvm::raw_fd_ostream os(outfile, ec, llvm::sys::fs::OF_Text);
    if (ec) {
      return llvm::make_error<llvm::StringError>(
          "unable to open destination file: " + outfile, os.error());
    } else {
      os << toJSON(*this);
      os.close();
      if (os.has_error()) {
        return llvm::make_error<llvm::StringError>(
            "unable to write to destination file: " + outfile, os.error());
      }
    }
    return llvm::Error::success();
  }
  
  HTRBlockLayerUP lldb_private::BasicSuperBlockMerge(IHTRLayer &layer) {
    std::unique_ptr<HTRBlockLayer> new_block_layer =
        std::make_unique<HTRBlockLayer>(layer.GetLayerId() + 1);
  
    if (layer.GetNumUnits()) {
      // Future Improvement: split this into two functions - one for finding heads
      // and tails, one for merging/creating the next layer A 'head' is defined to
      // be a block whose occurrences in the trace do not have a unique preceding
      // block.
      std::unordered_set<size_t> heads;
  
      // The load address of the first instruction of a block is the unique ID for
      // that block (i.e. blocks with the same first instruction load address are
      // the same block)
  
      // Future Improvement: no need to store all its preceding block ids, all we
      // care about is that there is more than one preceding block id, so an enum
      // could be used
      std::unordered_map<lldb::addr_t, std::unordered_set<lldb::addr_t>> head_map;
      lldb::addr_t prev_id =
          layer.GetMetadataByIndex(0).GetFirstInstructionLoadAddress();
      size_t num_units = layer.GetNumUnits();
      // This excludes the first unit since it has no previous unit
      for (size_t i = 1; i < num_units; i++) {
        lldb::addr_t current_id =
            layer.GetMetadataByIndex(i).GetFirstInstructionLoadAddress();
        head_map[current_id].insert(prev_id);
        prev_id = current_id;
      }
      for (const auto &it : head_map) {
        // ID of 0 represents an error - errors can't be heads or tails
        lldb::addr_t id = it.first;
        const std::unordered_set<lldb::addr_t> predecessor_set = it.second;
        if (id && predecessor_set.size() > 1)
          heads.insert(id);
      }
  
      // Future Improvement: identify heads and tails in the same loop
      // A 'tail' is defined to be a block whose occurrences in the trace do
      // not have a unique succeeding block.
      std::unordered_set<lldb::addr_t> tails;
      std::unordered_map<lldb::addr_t, std::unordered_set<lldb::addr_t>> tail_map;
  
      // This excludes the last unit since it has no next unit
      for (size_t i = 0; i < num_units - 1; i++) {
        lldb::addr_t current_id =
            layer.GetMetadataByIndex(i).GetFirstInstructionLoadAddress();
        lldb::addr_t next_id =
            layer.GetMetadataByIndex(i + 1).GetFirstInstructionLoadAddress();
        tail_map[current_id].insert(next_id);
      }
  
      // Mark last block as tail so the algorithm stops gracefully
      lldb::addr_t last_id = layer.GetMetadataByIndex(num_units - 1)
                                 .GetFirstInstructionLoadAddress();
      tails.insert(last_id);
      for (const auto &it : tail_map) {
        lldb::addr_t id = it.first;
        const std::unordered_set<lldb::addr_t> successor_set = it.second;
        // ID of 0 represents an error - errors can't be heads or tails
        if (id && successor_set.size() > 1)
          tails.insert(id);
      }
  
      // Need to keep track of size of string since things we push are variable
      // length
      size_t superblock_size = 0;
      // Each super block always has the same first unit (we call this the
      // super block head) This gurantee allows us to use the super block head as
      // the unique key mapping to the super block it begins
      llvm::Optional<size_t> superblock_head = llvm::None;
      auto construct_next_layer = [&](size_t merge_start, size_t n) -> void {
        if (!superblock_head)
          return;
        if (new_block_layer->GetBlockById(*superblock_head)) {
          new_block_layer->AppendRepeatedBlock(*superblock_head);
        } else {
          HTRBlock new_block = layer.MergeUnits(merge_start, n);
          new_block_layer->AppendNewBlock(*superblock_head, std::move(new_block));
        }
      };
  
      for (size_t i = 0; i < num_units; i++) {
        lldb::addr_t unit_id =
            layer.GetMetadataByIndex(i).GetFirstInstructionLoadAddress();
        auto isHead = heads.count(unit_id) > 0;
        auto isTail = tails.count(unit_id) > 0;
  
        if (isHead && isTail) {
          // Head logic
          if (superblock_size) { // this handles (tail, head) adjacency -
                                 // otherwise an empty
                                 // block is created
            // End previous super block
            construct_next_layer(i - superblock_size, superblock_size);
          }
          // Current id is first in next super block since it's a head
          superblock_head = unit_id;
          superblock_size = 1;
  
          // Tail logic
          construct_next_layer(i - superblock_size + 1, superblock_size);
          // Reset the block_head since the prev super block has come to and end
          superblock_head = llvm::None;
          superblock_size = 0;
        } else if (isHead) {
          if (superblock_size) { // this handles (tail, head) adjacency -
                                 // otherwise an empty
                                 // block is created
            // End previous super block
            construct_next_layer(i - superblock_size, superblock_size);
          }
          // Current id is first in next super block since it's a head
          superblock_head = unit_id;
          superblock_size = 1;
        } else if (isTail) {
          if (!superblock_head)
            superblock_head = unit_id;
          superblock_size++;
  
          // End previous super block
          construct_next_layer(i - superblock_size + 1, superblock_size);
          // Reset the block_head since the prev super block has come to and end
          superblock_head = llvm::None;
          superblock_size = 0;
        } else {
          if (!superblock_head)
            superblock_head = unit_id;
          superblock_size++;
        }
      }
    }
    return new_block_layer;
  }
  
  llvm::json::Value lldb_private::toJSON(const TraceHTR &htr) {
    std::vector<llvm::json::Value> layers_as_json;
    for (size_t i = 0; i < htr.GetInstructionLayer().GetInstructionTrace().size();
         i++) {
      size_t layer_id = htr.GetInstructionLayer().GetLayerId();
      HTRBlockMetadata metadata = htr.GetInstructionLayer().GetMetadataByIndex(i);
      lldb::addr_t load_address = metadata.GetFirstInstructionLoadAddress();
  
      std::string display_name;
  
      std::stringstream stream;
      stream << "0x" << std::hex << load_address;
      std::string load_address_hex_string(stream.str());
      display_name.assign(load_address_hex_string);
  
      // name: load address of the first instruction of the block and the name
      // of the most frequently called function from the block (if applicable)
  
      // ph: the event type - 'X' for Complete events (see link to documentation
      // below)
  
      // Since trace timestamps aren't yet supported in HTR, the ts (timestamp) is
      // based on the instruction's offset in the trace and the dur (duration) is
      // 1 since this layer contains single instructions. Using the instruction
      // offset and a duration of 1 oversimplifies the true timing information of
      // the trace, nonetheless, these approximate timestamps/durations provide an
      // clear visualization of the trace.
  
      // ts: offset from the beginning of the trace for the first instruction in
      // the block
  
      // dur: 1 since this layer contains single instructions.
  
      // pid: the ID of the HTR layer the blocks belong to
  
      // See
      // https://docs.google.com/document/d/1CvAClvFfyA5R-PhYUmn5OOQtYMH4h6I0nSsKchNAySU/preview#heading=h.j75x71ritcoy
      // for documentation on the Trace Event Format
      layers_as_json.emplace_back(llvm::json::Object{
          {"name", display_name},
          {"ph", "X"},
          {"ts", (int64_t)i},
          {"dur", 1},
          {"pid", (int64_t)layer_id},
      });
    }
  
    for (const auto &layer : htr.GetBlockLayers()) {
      size_t start_ts = 0;
      std::vector<size_t> block_id_trace = layer->GetBlockIdTrace();
      for (size_t i = 0; i < block_id_trace.size(); i++) {
        size_t id = block_id_trace[i];
        // Guranteed that this ID is valid, so safe to dereference here.
        HTRBlock block = *layer->GetBlockById(id);
        llvm::json::Value block_json = toJSON(block);
        size_t layer_id = layer->GetLayerId();
  
        HTRBlockMetadata metadata = block.GetMetadata();
  
        llvm::Optional<llvm::StringRef> most_freq_func =
            metadata.GetMostFrequentlyCalledFunction();
        std::stringstream stream;
        stream << "0x" << std::hex << metadata.GetFirstInstructionLoadAddress();
        std::string offset_hex_string(stream.str());
        std::string display_name =
            most_freq_func ? offset_hex_string + ": " + most_freq_func->str()
                           : offset_hex_string;
  
        // Since trace timestamps aren't yet supported in HTR, the ts (timestamp)
        // and dur (duration) are based on the block's offset in the trace and
        // number of instructions in the block, respectively. Using the block
        // offset and the number of instructions oversimplifies the true timing
        // information of the trace, nonetheless, these approximate
        // timestamps/durations provide an understandable visualization of the
        // trace.
        auto duration = metadata.GetNumInstructions();
        layers_as_json.emplace_back(llvm::json::Object{
            {"name", display_name},
            {"ph", "X"},
            {"ts", (int64_t)start_ts},
            {"dur", (int64_t)duration},
            {"pid", (int64_t)layer_id},
            {"args", block_json},
        });
        start_ts += duration;
      }
    }
    return layers_as_json;
  }
  
  llvm::json::Value lldb_private::toJSON(const HTRBlock &block) {
    return llvm::json::Value(
        llvm::json::Object{{"Metadata", block.GetMetadata()}});
  }
  
  llvm::json::Value lldb_private::toJSON(const HTRBlockMetadata &metadata) {
    std::vector<llvm::json::Value> function_calls;
    for (const auto &it : metadata.GetFunctionCalls()) {
      ConstString name = it.first;
      size_t n_calls = it.second;
      function_calls.emplace_back(llvm::formatv("({0}: {1})", name, n_calls));
    }
  
    return llvm::json::Value(llvm::json::Object{
        {"Number of Instructions", (ssize_t)metadata.GetNumInstructions()},
        {"Functions", function_calls}});
  }
  