1// Copyright 2016 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "src/interpreter/source-position-table.h"
6
7#include "src/objects-inl.h"
8#include "src/objects.h"
9
10namespace v8 {
11namespace internal {
12namespace interpreter {
13
14// We'll use a simple encoding scheme to record the source positions.
15// Conceptually, each position consists of:
16// - bytecode_offset: An integer index into the BytecodeArray
17// - source_position: An integer index into the source string.
18// - position type: Each position is either a statement or an expression.
19//
20// The basic idea for the encoding is to use a variable-length integer coding,
21// where each byte contains 7 bits of payload data, and 1 'more' bit that
22// determines whether additional bytes follow. Additionally:
23// - we record the difference from the previous position,
24// - we just stuff one bit for the type into the bytecode offset,
25// - we write least-significant bits first,
26// - we use zig-zag encoding to encode both positive and negative numbers.
27
28namespace {
29
30// Each byte is encoded as MoreBit | ValueBits.
31class MoreBit : public BitField8<bool, 7, 1> {};
32class ValueBits : public BitField8<unsigned, 0, 7> {};
33
34// Helper: Add the offsets from 'other' to 'value'. Also set is_statement.
35void AddAndSetEntry(PositionTableEntry& value,
36                    const PositionTableEntry& other) {
37  value.bytecode_offset += other.bytecode_offset;
38  value.source_position += other.source_position;
39  value.is_statement = other.is_statement;
40}
41
42// Helper: Substract the offsets from 'other' from 'value'.
43void SubtractFromEntry(PositionTableEntry& value,
44                       const PositionTableEntry& other) {
45  value.bytecode_offset -= other.bytecode_offset;
46  value.source_position -= other.source_position;
47}
48
49// Helper: Encode an integer.
50void EncodeInt(ZoneVector<byte>& bytes, int value) {
51  // Zig-zag encoding.
52  static const int kShift = kIntSize * kBitsPerByte - 1;
53  value = ((value << 1) ^ (value >> kShift));
54  DCHECK_GE(value, 0);
55  unsigned int encoded = static_cast<unsigned int>(value);
56  bool more;
57  do {
58    more = encoded > ValueBits::kMax;
59    bytes.push_back(MoreBit::encode(more) |
60                    ValueBits::encode(encoded & ValueBits::kMask));
61    encoded >>= ValueBits::kSize;
62  } while (more);
63}
64
65// Encode a PositionTableEntry.
66void EncodeEntry(ZoneVector<byte>& bytes, const PositionTableEntry& entry) {
67  // We only accept ascending bytecode offsets.
68  DCHECK(entry.bytecode_offset >= 0);
69  // Since bytecode_offset is not negative, we use sign to encode is_statement.
70  EncodeInt(bytes, entry.is_statement ? entry.bytecode_offset
71                                      : -entry.bytecode_offset - 1);
72  EncodeInt(bytes, entry.source_position);
73}
74
75// Helper: Decode an integer.
76void DecodeInt(ByteArray* bytes, int* index, int* v) {
77  byte current;
78  int shift = 0;
79  int decoded = 0;
80  bool more;
81  do {
82    current = bytes->get((*index)++);
83    decoded |= ValueBits::decode(current) << shift;
84    more = MoreBit::decode(current);
85    shift += ValueBits::kSize;
86  } while (more);
87  DCHECK_GE(decoded, 0);
88  decoded = (decoded >> 1) ^ (-(decoded & 1));
89  *v = decoded;
90}
91
92void DecodeEntry(ByteArray* bytes, int* index, PositionTableEntry* entry) {
93  int tmp;
94  DecodeInt(bytes, index, &tmp);
95  if (tmp >= 0) {
96    entry->is_statement = true;
97    entry->bytecode_offset = tmp;
98  } else {
99    entry->is_statement = false;
100    entry->bytecode_offset = -(tmp + 1);
101  }
102  DecodeInt(bytes, index, &entry->source_position);
103}
104
105}  // namespace
106
107void SourcePositionTableBuilder::AddPosition(size_t bytecode_offset,
108                                             int source_position,
109                                             bool is_statement) {
110  int offset = static_cast<int>(bytecode_offset);
111  AddEntry({offset, source_position, is_statement});
112}
113
114void SourcePositionTableBuilder::AddEntry(const PositionTableEntry& entry) {
115  PositionTableEntry tmp(entry);
116  SubtractFromEntry(tmp, previous_);
117  EncodeEntry(bytes_, tmp);
118  previous_ = entry;
119
120  if (entry.is_statement) {
121    LOG_CODE_EVENT(isolate_, CodeLinePosInfoAddStatementPositionEvent(
122                                 jit_handler_data_, entry.bytecode_offset,
123                                 entry.source_position));
124  }
125  LOG_CODE_EVENT(isolate_, CodeLinePosInfoAddPositionEvent(
126                               jit_handler_data_, entry.bytecode_offset,
127                               entry.source_position));
128
129#ifdef ENABLE_SLOW_DCHECKS
130  raw_entries_.push_back(entry);
131#endif
132}
133
134Handle<ByteArray> SourcePositionTableBuilder::ToSourcePositionTable() {
135  if (bytes_.empty()) return isolate_->factory()->empty_byte_array();
136
137  Handle<ByteArray> table = isolate_->factory()->NewByteArray(
138      static_cast<int>(bytes_.size()), TENURED);
139
140  MemCopy(table->GetDataStartAddress(), &*bytes_.begin(), bytes_.size());
141
142#ifdef ENABLE_SLOW_DCHECKS
143  // Brute force testing: Record all positions and decode
144  // the entire table to verify they are identical.
145  auto raw = raw_entries_.begin();
146  for (SourcePositionTableIterator encoded(*table); !encoded.done();
147       encoded.Advance(), raw++) {
148    DCHECK(raw != raw_entries_.end());
149    DCHECK_EQ(encoded.bytecode_offset(), raw->bytecode_offset);
150    DCHECK_EQ(encoded.source_position(), raw->source_position);
151    DCHECK_EQ(encoded.is_statement(), raw->is_statement);
152  }
153  DCHECK(raw == raw_entries_.end());
154#endif
155
156  return table;
157}
158
159SourcePositionTableIterator::SourcePositionTableIterator(ByteArray* byte_array)
160    : table_(byte_array), index_(0), current_() {
161  Advance();
162}
163
164void SourcePositionTableIterator::Advance() {
165  DCHECK(!done());
166  DCHECK(index_ >= 0 && index_ <= table_->length());
167  if (index_ == table_->length()) {
168    index_ = kDone;
169  } else {
170    PositionTableEntry tmp;
171    DecodeEntry(table_, &index_, &tmp);
172    AddAndSetEntry(current_, tmp);
173  }
174}
175
176}  // namespace interpreter
177}  // namespace internal
178}  // namespace v8
179