source-position-table.cc 9.78 KB
Newer Older
1 2 3 4
// Copyright 2016 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

5
#include "src/codegen/source-position-table.h"
6

7
#include "src/base/export-template.h"
8 9
#include "src/base/logging.h"
#include "src/common/assert-scope.h"
10
#include "src/heap/local-factory-inl.h"
11 12
#include "src/objects/objects-inl.h"
#include "src/objects/objects.h"
13 14 15 16

namespace v8 {
namespace internal {

17 18
// We'll use a simple encoding scheme to record the source positions.
// Conceptually, each position consists of:
19
// - code_offset: An integer index into the BytecodeArray or code.
20 21 22 23 24 25 26
// - source_position: An integer index into the source string.
// - position type: Each position is either a statement or an expression.
//
// The basic idea for the encoding is to use a variable-length integer coding,
// where each byte contains 7 bits of payload data, and 1 'more' bit that
// determines whether additional bytes follow. Additionally:
// - we record the difference from the previous position,
27
// - we just stuff one bit for the type into the code offset,
28
// - we write least-significant bits first,
29
// - we use zig-zag encoding to encode both positive and negative numbers.
30 31 32 33

namespace {

// Each byte is encoded as MoreBit | ValueBits.
34 35
using MoreBit = base::BitField8<bool, 7, 1>;
using ValueBits = base::BitField8<unsigned, 0, 7>;
36 37

// Helper: Add the offsets from 'other' to 'value'. Also set is_statement.
38
void AddAndSetEntry(PositionTableEntry* value,
39
                    const PositionTableEntry& other) {
40
  value->code_offset += other.code_offset;
41 42
  DCHECK_IMPLIES(value->code_offset != kFunctionEntryBytecodeOffset,
                 value->code_offset >= 0);
43
  value->source_position += other.source_position;
44
  DCHECK_LE(0, value->source_position);
45
  value->is_statement = other.is_statement;
46 47
}

48
// Helper: Subtract the offsets from 'other' from 'value'.
49
void SubtractFromEntry(PositionTableEntry* value,
50
                       const PositionTableEntry& other) {
51 52
  value->code_offset -= other.code_offset;
  value->source_position -= other.source_position;
53 54 55
}

// Helper: Encode an integer.
56
template <typename T>
57
void EncodeInt(ZoneVector<byte>* bytes, T value) {
58
  using unsigned_type = typename std::make_unsigned<T>::type;
59
  // Zig-zag encoding.
60
  static constexpr int kShift = sizeof(T) * kBitsPerByte - 1;
61
  value = ((static_cast<unsigned_type>(value) << 1) ^ (value >> kShift));
62
  DCHECK_GE(value, 0);
63
  unsigned_type encoded = static_cast<unsigned_type>(value);
64 65
  bool more;
  do {
66
    more = encoded > ValueBits::kMax;
67 68
    byte current =
        MoreBit::encode(more) | ValueBits::encode(encoded & ValueBits::kMask);
69
    bytes->push_back(current);
70
    encoded >>= ValueBits::kSize;
71 72 73 74
  } while (more);
}

// Encode a PositionTableEntry.
75
void EncodeEntry(ZoneVector<byte>* bytes, const PositionTableEntry& entry) {
76
  // We only accept ascending code offsets.
77 78 79 80 81
  DCHECK_LE(0, entry.code_offset);
  // All but the first entry must be *strictly* ascending (no two entries for
  // the same position).
  // TODO(11496): This DCHECK fails tests.
  // DCHECK_IMPLIES(!bytes->empty(), entry.code_offset > 0);
82 83 84
  // Since code_offset is not negative, we use sign to encode is_statement.
  EncodeInt(bytes,
            entry.is_statement ? entry.code_offset : -entry.code_offset - 1);
85 86 87 88
  EncodeInt(bytes, entry.source_position);
}

// Helper: Decode an integer.
89
template <typename T>
90
T DecodeInt(Vector<const byte> bytes, int* index) {
91
  byte current;
92
  int shift = 0;
93
  T decoded = 0;
94 95
  bool more;
  do {
96
    current = bytes[(*index)++];
97 98 99
    decoded |= static_cast<typename std::make_unsigned<T>::type>(
                   ValueBits::decode(current))
               << shift;
100
    more = MoreBit::decode(current);
101
    shift += ValueBits::kSize;
102
  } while (more);
103 104
  DCHECK_GE(decoded, 0);
  decoded = (decoded >> 1) ^ (-(decoded & 1));
105
  return decoded;
106 107
}

108 109
void DecodeEntry(Vector<const byte> bytes, int* index,
                 PositionTableEntry* entry) {
110
  int tmp = DecodeInt<int>(bytes, index);
111 112
  if (tmp >= 0) {
    entry->is_statement = true;
113
    entry->code_offset = tmp;
114 115
  } else {
    entry->is_statement = false;
116
    entry->code_offset = -(tmp + 1);
117
  }
118
  entry->source_position = DecodeInt<int64_t>(bytes, index);
119 120
}

121
Vector<const byte> VectorFromByteArray(ByteArray byte_array) {
122 123
  return Vector<const byte>(byte_array.GetDataStartAddress(),
                            byte_array.length());
124 125
}

126
#ifdef ENABLE_SLOW_DCHECKS
127
void CheckTableEquals(const ZoneVector<PositionTableEntry>& raw_entries,
128
                      SourcePositionTableIterator* encoded) {
129 130 131
  // Brute force testing: Record all positions and decode
  // the entire table to verify they are identical.
  auto raw = raw_entries.begin();
132
  for (; !encoded->done(); encoded->Advance(), raw++) {
133
    DCHECK(raw != raw_entries.end());
134 135 136
    DCHECK_EQ(encoded->code_offset(), raw->code_offset);
    DCHECK_EQ(encoded->source_position().raw(), raw->source_position);
    DCHECK_EQ(encoded->is_statement(), raw->is_statement);
137 138 139 140 141
  }
  DCHECK(raw == raw_entries.end());
}
#endif

142
}  // namespace
143

144
SourcePositionTableBuilder::SourcePositionTableBuilder(
145 146 147 148 149 150 151 152
    Zone* zone, SourcePositionTableBuilder::RecordingMode mode)
    : mode_(mode),
      bytes_(zone),
#ifdef ENABLE_SLOW_DCHECKS
      raw_entries_(zone),
#endif
      previous_() {
}
yangguo's avatar
yangguo committed
153

154
void SourcePositionTableBuilder::AddPosition(size_t code_offset,
155
                                             SourcePosition source_position,
156
                                             bool is_statement) {
157
  if (Omit()) return;
158
  DCHECK(source_position.IsKnown());
159
  int offset = static_cast<int>(code_offset);
160
  AddEntry({offset, source_position.raw(), is_statement});
161 162
}

163
void SourcePositionTableBuilder::AddEntry(const PositionTableEntry& entry) {
164
  PositionTableEntry tmp(entry);
165 166
  SubtractFromEntry(&tmp, previous_);
  EncodeEntry(&bytes_, tmp);
167
  previous_ = entry;
168
#ifdef ENABLE_SLOW_DCHECKS
169
  raw_entries_.push_back(entry);
170
#endif
171 172
}

173 174 175
template <typename LocalIsolate>
Handle<ByteArray> SourcePositionTableBuilder::ToSourcePositionTable(
    LocalIsolate* isolate) {
176
  if (bytes_.empty()) return isolate->factory()->empty_byte_array();
177
  DCHECK(!Omit());
178

179
  Handle<ByteArray> table = isolate->factory()->NewByteArray(
180
      static_cast<int>(bytes_.size()), AllocationType::kOld);
181
  MemCopy(table->GetDataStartAddress(), bytes_.data(), bytes_.size());
182

183 184 185
#ifdef ENABLE_SLOW_DCHECKS
  // Brute force testing: Record all positions and decode
  // the entire table to verify they are identical.
186 187 188
  SourcePositionTableIterator it(
      *table, SourcePositionTableIterator::kAll,
      SourcePositionTableIterator::kDontSkipFunctionEntry);
189
  CheckTableEquals(raw_entries_, &it);
190 191 192 193 194 195
  // No additional source positions after creating the table.
  mode_ = OMIT_SOURCE_POSITIONS;
#endif
  return table;
}

196 197 198 199
template EXPORT_TEMPLATE_DEFINE(V8_EXPORT_PRIVATE)
    Handle<ByteArray> SourcePositionTableBuilder::ToSourcePositionTable(
        Isolate* isolate);
template EXPORT_TEMPLATE_DEFINE(V8_EXPORT_PRIVATE)
200
    Handle<ByteArray> SourcePositionTableBuilder::ToSourcePositionTable(
201
        LocalIsolate* isolate);
202

203 204 205 206
OwnedVector<byte> SourcePositionTableBuilder::ToSourcePositionTableVector() {
  if (bytes_.empty()) return OwnedVector<byte>();
  DCHECK(!Omit());

207
  OwnedVector<byte> table = OwnedVector<byte>::Of(bytes_);
208 209 210 211

#ifdef ENABLE_SLOW_DCHECKS
  // Brute force testing: Record all positions and decode
  // the entire table to verify they are identical.
212 213 214
  SourcePositionTableIterator it(
      table.as_vector(), SourcePositionTableIterator::kAll,
      SourcePositionTableIterator::kDontSkipFunctionEntry);
215
  CheckTableEquals(raw_entries_, &it);
216 217
  // No additional source positions after creating the table.
  mode_ = OMIT_SOURCE_POSITIONS;
218
#endif
219 220 221
  return table;
}

222
void SourcePositionTableIterator::Initialize() {
223
  Advance();
224 225 226 227
  if (function_entry_filter_ == kSkipFunctionEntry &&
      current_.code_offset == kFunctionEntryBytecodeOffset && !done()) {
    Advance();
  }
228 229
}

230
SourcePositionTableIterator::SourcePositionTableIterator(
231 232 233 234 235 236 237 238 239 240 241 242 243 244 245
    ByteArray byte_array, IterationFilter iteration_filter,
    FunctionEntryFilter function_entry_filter)
    : raw_table_(VectorFromByteArray(byte_array)),
      iteration_filter_(iteration_filter),
      function_entry_filter_(function_entry_filter) {
  Initialize();
}

SourcePositionTableIterator::SourcePositionTableIterator(
    Handle<ByteArray> byte_array, IterationFilter iteration_filter,
    FunctionEntryFilter function_entry_filter)
    : table_(byte_array),
      iteration_filter_(iteration_filter),
      function_entry_filter_(function_entry_filter) {
  Initialize();
246
#ifdef DEBUG
247 248
  // We can enable allocation because we keep the table in a handle.
  no_gc.Release();
249
#endif  // DEBUG
250 251
}

252
SourcePositionTableIterator::SourcePositionTableIterator(
253 254 255 256 257 258
    Vector<const byte> bytes, IterationFilter iteration_filter,
    FunctionEntryFilter function_entry_filter)
    : raw_table_(bytes),
      iteration_filter_(iteration_filter),
      function_entry_filter_(function_entry_filter) {
  Initialize();
259
#ifdef DEBUG
260 261
  // We can enable allocation because the underlying vector does not move.
  no_gc.Release();
262
#endif  // DEBUG
263 264
}

265
void SourcePositionTableIterator::Advance() {
266 267
  Vector<const byte> bytes =
      table_.is_null() ? raw_table_ : VectorFromByteArray(*table_);
268
  DCHECK(!done());
269
  DCHECK(index_ >= 0 && index_ <= bytes.length());
270 271 272 273 274 275 276
  bool filter_satisfied = false;
  while (!done() && !filter_satisfied) {
    if (index_ >= bytes.length()) {
      index_ = kDone;
    } else {
      PositionTableEntry tmp;
      DecodeEntry(bytes, &index_, &tmp);
277
      AddAndSetEntry(&current_, tmp);
278
      SourcePosition p = source_position();
279 280 281 282
      filter_satisfied =
          (iteration_filter_ == kAll) ||
          (iteration_filter_ == kJavaScriptOnly && p.IsJavaScript()) ||
          (iteration_filter_ == kExternalOnly && p.IsExternal());
283
    }
284 285 286 287 288
  }
}

}  // namespace internal
}  // namespace v8