Coverage Report

Created: 2022-01-18 06:27

/Users/buildslave/jenkins/workspace/coverage/llvm-project/lldb/source/Plugins/TraceExporter/common/TraceHTR.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- TraceHTR.cpp ------------------------------------------------------===//
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
#include "TraceHTR.h"
10
11
#include "lldb/Symbol/Function.h"
12
#include "lldb/Target/Process.h"
13
#include "lldb/Target/Target.h"
14
#include "llvm/Support/JSON.h"
15
#include <sstream>
16
#include <string>
17
18
using namespace lldb_private;
19
using namespace lldb;
20
21
0
size_t HTRBlockMetadata::GetNumInstructions() const {
22
0
  return m_num_instructions;
23
0
}
24
25
llvm::Optional<llvm::StringRef>
26
0
HTRBlockMetadata::GetMostFrequentlyCalledFunction() const {
27
0
  size_t max_ncalls = 0;
28
0
  llvm::Optional<llvm::StringRef> max_name = llvm::None;
29
0
  for (const auto &it : m_func_calls) {
30
0
    ConstString name = it.first;
31
0
    size_t ncalls = it.second;
32
0
    if (ncalls > max_ncalls) {
33
0
      max_ncalls = ncalls;
34
0
      max_name = name.GetStringRef();
35
0
    }
36
0
  }
37
0
  return max_name;
38
0
}
39
40
llvm::DenseMap<ConstString, size_t> const &
41
0
HTRBlockMetadata::GetFunctionCalls() const {
42
0
  return m_func_calls;
43
0
}
44
45
0
lldb::addr_t HTRBlockMetadata::GetFirstInstructionLoadAddress() const {
46
0
  return m_first_instruction_load_address;
47
0
}
48
49
0
size_t HTRBlock::GetOffset() const { return m_offset; }
50
51
0
size_t HTRBlock::GetSize() const { return m_size; }
52
53
0
HTRBlockMetadata const &HTRBlock::GetMetadata() const { return m_metadata; }
54
55
0
llvm::ArrayRef<HTRBlockLayerUP> TraceHTR::GetBlockLayers() const {
56
0
  return m_block_layer_ups;
57
0
}
58
59
0
HTRInstructionLayer const &TraceHTR::GetInstructionLayer() const {
60
0
  return *m_instruction_layer_up;
61
0
}
62
63
0
void TraceHTR::AddNewBlockLayer(HTRBlockLayerUP &&block_layer) {
64
0
  m_block_layer_ups.emplace_back(std::move(block_layer));
65
0
}
66
67
0
size_t IHTRLayer::GetLayerId() const { return m_layer_id; }
68
69
0
void HTRBlockLayer::AppendNewBlock(size_t block_id, HTRBlock &&block) {
70
0
  m_block_id_trace.emplace_back(block_id);
71
0
  m_block_defs.emplace(block_id, block);
72
0
}
73
74
0
void HTRBlockLayer::AppendRepeatedBlock(size_t block_id) {
75
0
  m_block_id_trace.emplace_back(block_id);
76
0
}
77
78
0
llvm::ArrayRef<lldb::addr_t> HTRInstructionLayer::GetInstructionTrace() const {
79
0
  return m_instruction_trace;
80
0
}
81
82
void HTRInstructionLayer::AddCallInstructionMetadata(
83
0
    lldb::addr_t load_addr, llvm::Optional<ConstString> func_name) {
84
0
  m_call_isns.emplace(load_addr, func_name);
85
0
}
86
87
0
void HTRInstructionLayer::AppendInstruction(lldb::addr_t load_addr) {
88
0
  m_instruction_trace.emplace_back(load_addr);
89
0
}
90
91
0
HTRBlock const *HTRBlockLayer::GetBlockById(size_t block_id) const {
92
0
  auto block_it = m_block_defs.find(block_id);
93
0
  if (block_it == m_block_defs.end())
94
0
    return nullptr;
95
0
  else
96
0
    return &block_it->second;
97
0
}
98
99
0
llvm::ArrayRef<size_t> HTRBlockLayer::GetBlockIdTrace() const {
100
0
  return m_block_id_trace;
101
0
}
102
103
0
size_t HTRBlockLayer::GetNumUnits() const { return m_block_id_trace.size(); }
104
105
0
HTRBlockMetadata HTRInstructionLayer::GetMetadataByIndex(size_t index) const {
106
0
  lldb::addr_t instruction_load_address = m_instruction_trace[index];
107
0
  llvm::DenseMap<ConstString, size_t> func_calls;
108
109
0
  auto func_name_it = m_call_isns.find(instruction_load_address);
110
0
  if (func_name_it != m_call_isns.end()) {
111
0
    if (llvm::Optional<ConstString> func_name = func_name_it->second) {
112
0
      func_calls[*func_name] = 1;
113
0
    }
114
0
  }
115
0
  return {instruction_load_address, 1, std::move(func_calls)};
116
0
}
117
118
0
size_t HTRInstructionLayer::GetNumUnits() const {
119
0
  return m_instruction_trace.size();
120
0
}
121
122
0
HTRBlockMetadata HTRBlockLayer::GetMetadataByIndex(size_t index) const {
123
0
  size_t block_id = m_block_id_trace[index];
124
0
  HTRBlock block = m_block_defs.find(block_id)->second;
125
0
  return block.GetMetadata();
126
0
}
127
128
TraceHTR::TraceHTR(Thread &thread, TraceCursor &cursor)
129
0
    : m_instruction_layer_up(std::make_unique<HTRInstructionLayer>(0)) {
130
131
  // Move cursor to the first instruction in the trace
132
0
  cursor.SetForwards(true);
133
0
  cursor.Seek(0, TraceCursor::SeekType::Set);
134
135
0
  Target &target = thread.GetProcess()->GetTarget();
136
0
  auto function_name_from_load_address =
137
0
      [&](lldb::addr_t load_address) -> llvm::Optional<ConstString> {
138
0
    lldb_private::Address pc_addr;
139
0
    SymbolContext sc;
140
0
    if (target.ResolveLoadAddress(load_address, pc_addr) &&
141
0
        pc_addr.CalculateSymbolContext(&sc))
142
0
      return sc.GetFunctionName()
143
0
                 ? llvm::Optional<ConstString>(sc.GetFunctionName())
144
0
                 : llvm::None;
145
0
    else
146
0
      return llvm::None;
147
0
  };
148
149
0
  bool more_data_in_trace = true;
150
0
  while (more_data_in_trace) {
151
0
    if (cursor.IsError()) {
152
      // Append a load address of 0 for all instructions that an error occured
153
      // while decoding.
154
      // TODO: Make distinction between errors by storing the error messages.
155
      // Currently, all errors are treated the same.
156
0
      m_instruction_layer_up->AppendInstruction(0);
157
0
      more_data_in_trace = cursor.Next();
158
0
    } else {
159
0
      lldb::addr_t current_instruction_load_address = cursor.GetLoadAddress();
160
0
      lldb::TraceInstructionControlFlowType current_instruction_type =
161
0
          cursor.GetInstructionControlFlowType();
162
163
0
      m_instruction_layer_up->AppendInstruction(
164
0
          current_instruction_load_address);
165
0
      more_data_in_trace = cursor.Next();
166
0
      if (current_instruction_type &
167
0
          lldb::eTraceInstructionControlFlowTypeCall) {
168
0
        if (more_data_in_trace && !cursor.IsError()) {
169
0
          m_instruction_layer_up->AddCallInstructionMetadata(
170
0
              current_instruction_load_address,
171
0
              function_name_from_load_address(cursor.GetLoadAddress()));
172
0
        } else {
173
          // Next instruction is not known - pass None to indicate the name
174
          // of the function being called is not known
175
0
          m_instruction_layer_up->AddCallInstructionMetadata(
176
0
              current_instruction_load_address, llvm::None);
177
0
        }
178
0
      }
179
0
    }
180
0
  }
181
0
}
182
183
void HTRBlockMetadata::MergeMetadata(
184
    HTRBlockMetadata &merged_metadata,
185
0
    HTRBlockMetadata const &metadata_to_merge) {
186
0
  merged_metadata.m_num_instructions += metadata_to_merge.m_num_instructions;
187
0
  for (const auto &it : metadata_to_merge.m_func_calls) {
188
0
    ConstString name = it.first;
189
0
    size_t num_calls = it.second;
190
0
    merged_metadata.m_func_calls[name] += num_calls;
191
0
  }
192
0
}
193
194
0
HTRBlock IHTRLayer::MergeUnits(size_t start_unit_index, size_t num_units) {
195
  // TODO: make this function take `end_unit_index` as a parameter instead of
196
  // unit and merge the range [start_unit_indx, end_unit_index] inclusive.
197
0
  HTRBlockMetadata merged_metadata = GetMetadataByIndex(start_unit_index);
198
0
  for (size_t i = start_unit_index + 1; i < start_unit_index + num_units; i++) {
199
    // merge the new metadata into merged_metadata
200
0
    HTRBlockMetadata::MergeMetadata(merged_metadata, GetMetadataByIndex(i));
201
0
  }
202
0
  return {start_unit_index, num_units, merged_metadata};
203
0
}
204
205
0
void TraceHTR::ExecutePasses() {
206
0
  auto are_passes_done = [](IHTRLayer &l1, IHTRLayer &l2) {
207
0
    return l1.GetNumUnits() == l2.GetNumUnits();
208
0
  };
209
0
  HTRBlockLayerUP current_block_layer_up =
210
0
      BasicSuperBlockMerge(*m_instruction_layer_up);
211
0
  HTRBlockLayer &current_block_layer = *current_block_layer_up;
212
0
  if (are_passes_done(*m_instruction_layer_up, *current_block_layer_up))
213
0
    return;
214
215
0
  AddNewBlockLayer(std::move(current_block_layer_up));
216
0
  while (true) {
217
0
    HTRBlockLayerUP new_block_layer_up =
218
0
        BasicSuperBlockMerge(current_block_layer);
219
0
    if (are_passes_done(current_block_layer, *new_block_layer_up))
220
0
      return;
221
222
0
    current_block_layer = *new_block_layer_up;
223
0
    AddNewBlockLayer(std::move(new_block_layer_up));
224
0
  }
225
0
}
226
227
0
llvm::Error TraceHTR::Export(std::string outfile) {
228
0
  std::error_code ec;
229
0
  llvm::raw_fd_ostream os(outfile, ec, llvm::sys::fs::OF_Text);
230
0
  if (ec) {
231
0
    return llvm::make_error<llvm::StringError>(
232
0
        "unable to open destination file: " + outfile, os.error());
233
0
  } else {
234
0
    os << toJSON(*this);
235
0
    os.close();
236
0
    if (os.has_error()) {
237
0
      return llvm::make_error<llvm::StringError>(
238
0
          "unable to write to destination file: " + outfile, os.error());
239
0
    }
240
0
  }
241
0
  return llvm::Error::success();
242
0
}
243
244
0
HTRBlockLayerUP lldb_private::BasicSuperBlockMerge(IHTRLayer &layer) {
245
0
  std::unique_ptr<HTRBlockLayer> new_block_layer =
246
0
      std::make_unique<HTRBlockLayer>(layer.GetLayerId() + 1);
247
248
0
  if (layer.GetNumUnits()) {
249
    // Future Improvement: split this into two functions - one for finding heads
250
    // and tails, one for merging/creating the next layer A 'head' is defined to
251
    // be a block whose occurrences in the trace do not have a unique preceding
252
    // block.
253
0
    std::unordered_set<size_t> heads;
254
255
    // The load address of the first instruction of a block is the unique ID for
256
    // that block (i.e. blocks with the same first instruction load address are
257
    // the same block)
258
259
    // Future Improvement: no need to store all its preceding block ids, all we
260
    // care about is that there is more than one preceding block id, so an enum
261
    // could be used
262
0
    std::unordered_map<lldb::addr_t, std::unordered_set<lldb::addr_t>> head_map;
263
0
    lldb::addr_t prev_id =
264
0
        layer.GetMetadataByIndex(0).GetFirstInstructionLoadAddress();
265
0
    size_t num_units = layer.GetNumUnits();
266
    // This excludes the first unit since it has no previous unit
267
0
    for (size_t i = 1; i < num_units; i++) {
268
0
      lldb::addr_t current_id =
269
0
          layer.GetMetadataByIndex(i).GetFirstInstructionLoadAddress();
270
0
      head_map[current_id].insert(prev_id);
271
0
      prev_id = current_id;
272
0
    }
273
0
    for (const auto &it : head_map) {
274
      // ID of 0 represents an error - errors can't be heads or tails
275
0
      lldb::addr_t id = it.first;
276
0
      const std::unordered_set<lldb::addr_t> predecessor_set = it.second;
277
0
      if (id && predecessor_set.size() > 1)
278
0
        heads.insert(id);
279
0
    }
280
281
    // Future Improvement: identify heads and tails in the same loop
282
    // A 'tail' is defined to be a block whose occurrences in the trace do
283
    // not have a unique succeeding block.
284
0
    std::unordered_set<lldb::addr_t> tails;
285
0
    std::unordered_map<lldb::addr_t, std::unordered_set<lldb::addr_t>> tail_map;
286
287
    // This excludes the last unit since it has no next unit
288
0
    for (size_t i = 0; i < num_units - 1; i++) {
289
0
      lldb::addr_t current_id =
290
0
          layer.GetMetadataByIndex(i).GetFirstInstructionLoadAddress();
291
0
      lldb::addr_t next_id =
292
0
          layer.GetMetadataByIndex(i + 1).GetFirstInstructionLoadAddress();
293
0
      tail_map[current_id].insert(next_id);
294
0
    }
295
296
    // Mark last block as tail so the algorithm stops gracefully
297
0
    lldb::addr_t last_id = layer.GetMetadataByIndex(num_units - 1)
298
0
                               .GetFirstInstructionLoadAddress();
299
0
    tails.insert(last_id);
300
0
    for (const auto &it : tail_map) {
301
0
      lldb::addr_t id = it.first;
302
0
      const std::unordered_set<lldb::addr_t> successor_set = it.second;
303
      // ID of 0 represents an error - errors can't be heads or tails
304
0
      if (id && successor_set.size() > 1)
305
0
        tails.insert(id);
306
0
    }
307
308
    // Need to keep track of size of string since things we push are variable
309
    // length
310
0
    size_t superblock_size = 0;
311
    // Each super block always has the same first unit (we call this the
312
    // super block head) This gurantee allows us to use the super block head as
313
    // the unique key mapping to the super block it begins
314
0
    llvm::Optional<size_t> superblock_head = llvm::None;
315
0
    auto construct_next_layer = [&](size_t merge_start, size_t n) -> void {
316
0
      if (!superblock_head)
317
0
        return;
318
0
      if (new_block_layer->GetBlockById(*superblock_head)) {
319
0
        new_block_layer->AppendRepeatedBlock(*superblock_head);
320
0
      } else {
321
0
        HTRBlock new_block = layer.MergeUnits(merge_start, n);
322
0
        new_block_layer->AppendNewBlock(*superblock_head, std::move(new_block));
323
0
      }
324
0
    };
325
326
0
    for (size_t i = 0; i < num_units; i++) {
327
0
      lldb::addr_t unit_id =
328
0
          layer.GetMetadataByIndex(i).GetFirstInstructionLoadAddress();
329
0
      auto isHead = heads.count(unit_id) > 0;
330
0
      auto isTail = tails.count(unit_id) > 0;
331
332
0
      if (isHead && isTail) {
333
        // Head logic
334
0
        if (superblock_size) { // this handles (tail, head) adjacency -
335
                               // otherwise an empty
336
                               // block is created
337
          // End previous super block
338
0
          construct_next_layer(i - superblock_size, superblock_size);
339
0
        }
340
        // Current id is first in next super block since it's a head
341
0
        superblock_head = unit_id;
342
0
        superblock_size = 1;
343
344
        // Tail logic
345
0
        construct_next_layer(i - superblock_size + 1, superblock_size);
346
        // Reset the block_head since the prev super block has come to and end
347
0
        superblock_head = llvm::None;
348
0
        superblock_size = 0;
349
0
      } else if (isHead) {
350
0
        if (superblock_size) { // this handles (tail, head) adjacency -
351
                               // otherwise an empty
352
                               // block is created
353
          // End previous super block
354
0
          construct_next_layer(i - superblock_size, superblock_size);
355
0
        }
356
        // Current id is first in next super block since it's a head
357
0
        superblock_head = unit_id;
358
0
        superblock_size = 1;
359
0
      } else if (isTail) {
360
0
        if (!superblock_head)
361
0
          superblock_head = unit_id;
362
0
        superblock_size++;
363
364
        // End previous super block
365
0
        construct_next_layer(i - superblock_size + 1, superblock_size);
366
        // Reset the block_head since the prev super block has come to and end
367
0
        superblock_head = llvm::None;
368
0
        superblock_size = 0;
369
0
      } else {
370
0
        if (!superblock_head)
371
0
          superblock_head = unit_id;
372
0
        superblock_size++;
373
0
      }
374
0
    }
375
0
  }
376
0
  return new_block_layer;
377
0
}
378
379
0
llvm::json::Value lldb_private::toJSON(const TraceHTR &htr) {
380
0
  std::vector<llvm::json::Value> layers_as_json;
381
0
  for (size_t i = 0; i < htr.GetInstructionLayer().GetInstructionTrace().size();
382
0
       i++) {
383
0
    size_t layer_id = htr.GetInstructionLayer().GetLayerId();
384
0
    HTRBlockMetadata metadata = htr.GetInstructionLayer().GetMetadataByIndex(i);
385
0
    lldb::addr_t load_address = metadata.GetFirstInstructionLoadAddress();
386
387
0
    std::string display_name;
388
389
0
    std::stringstream stream;
390
0
    stream << "0x" << std::hex << load_address;
391
0
    std::string load_address_hex_string(stream.str());
392
0
    display_name.assign(load_address_hex_string);
393
394
    // name: load address of the first instruction of the block and the name
395
    // of the most frequently called function from the block (if applicable)
396
397
    // ph: the event type - 'X' for Complete events (see link to documentation
398
    // below)
399
400
    // Since trace timestamps aren't yet supported in HTR, the ts (timestamp) is
401
    // based on the instruction's offset in the trace and the dur (duration) is
402
    // 1 since this layer contains single instructions. Using the instruction
403
    // offset and a duration of 1 oversimplifies the true timing information of
404
    // the trace, nonetheless, these approximate timestamps/durations provide an
405
    // clear visualization of the trace.
406
407
    // ts: offset from the beginning of the trace for the first instruction in
408
    // the block
409
410
    // dur: 1 since this layer contains single instructions.
411
412
    // pid: the ID of the HTR layer the blocks belong to
413
414
    // See
415
    // https://docs.google.com/document/d/1CvAClvFfyA5R-PhYUmn5OOQtYMH4h6I0nSsKchNAySU/preview#heading=h.j75x71ritcoy
416
    // for documentation on the Trace Event Format
417
0
    layers_as_json.emplace_back(llvm::json::Object{
418
0
        {"name", display_name},
419
0
        {"ph", "X"},
420
0
        {"ts", (int64_t)i},
421
0
        {"dur", 1},
422
0
        {"pid", (int64_t)layer_id},
423
0
    });
424
0
  }
425
426
0
  for (const auto &layer : htr.GetBlockLayers()) {
427
0
    size_t start_ts = 0;
428
0
    std::vector<size_t> block_id_trace = layer->GetBlockIdTrace();
429
0
    for (size_t i = 0; i < block_id_trace.size(); i++) {
430
0
      size_t id = block_id_trace[i];
431
      // Guranteed that this ID is valid, so safe to dereference here.
432
0
      HTRBlock block = *layer->GetBlockById(id);
433
0
      llvm::json::Value block_json = toJSON(block);
434
0
      size_t layer_id = layer->GetLayerId();
435
436
0
      HTRBlockMetadata metadata = block.GetMetadata();
437
438
0
      llvm::Optional<llvm::StringRef> most_freq_func =
439
0
          metadata.GetMostFrequentlyCalledFunction();
440
0
      std::stringstream stream;
441
0
      stream << "0x" << std::hex << metadata.GetFirstInstructionLoadAddress();
442
0
      std::string offset_hex_string(stream.str());
443
0
      std::string display_name =
444
0
          most_freq_func ? offset_hex_string + ": " + most_freq_func->str()
445
0
                         : offset_hex_string;
446
447
      // Since trace timestamps aren't yet supported in HTR, the ts (timestamp)
448
      // and dur (duration) are based on the block's offset in the trace and
449
      // number of instructions in the block, respectively. Using the block
450
      // offset and the number of instructions oversimplifies the true timing
451
      // information of the trace, nonetheless, these approximate
452
      // timestamps/durations provide an understandable visualization of the
453
      // trace.
454
0
      auto duration = metadata.GetNumInstructions();
455
0
      layers_as_json.emplace_back(llvm::json::Object{
456
0
          {"name", display_name},
457
0
          {"ph", "X"},
458
0
          {"ts", (int64_t)start_ts},
459
0
          {"dur", (int64_t)duration},
460
0
          {"pid", (int64_t)layer_id},
461
0
          {"args", block_json},
462
0
      });
463
0
      start_ts += duration;
464
0
    }
465
0
  }
466
0
  return layers_as_json;
467
0
}
468
469
0
llvm::json::Value lldb_private::toJSON(const HTRBlock &block) {
470
0
  return llvm::json::Value(
471
0
      llvm::json::Object{{"Metadata", block.GetMetadata()}});
472
0
}
473
474
0
llvm::json::Value lldb_private::toJSON(const HTRBlockMetadata &metadata) {
475
0
  std::vector<llvm::json::Value> function_calls;
476
0
  for (const auto &it : metadata.GetFunctionCalls()) {
477
0
    ConstString name = it.first;
478
0
    size_t n_calls = it.second;
479
0
    function_calls.emplace_back(llvm::formatv("({0}: {1})", name, n_calls));
480
0
  }
481
482
0
  return llvm::json::Value(llvm::json::Object{
483
0
      {"Number of Instructions", (ssize_t)metadata.GetNumInstructions()},
484
0
      {"Functions", function_calls}});
485
0
}