Line data Source code
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/source-position-table.h"
6 :
7 : #include "src/objects-inl.h"
8 : #include "src/objects.h"
9 :
10 : namespace v8 {
11 : namespace internal {
12 :
13 : // We'll use a simple encoding scheme to record the source positions.
14 : // Conceptually, each position consists of:
15 : // - code_offset: An integer index into the BytecodeArray or code.
16 : // - source_position: An integer index into the source string.
17 : // - position type: Each position is either a statement or an expression.
18 : //
19 : // The basic idea for the encoding is to use a variable-length integer coding,
20 : // where each byte contains 7 bits of payload data, and 1 'more' bit that
21 : // determines whether additional bytes follow. Additionally:
22 : // - we record the difference from the previous position,
23 : // - we just stuff one bit for the type into the code offset,
24 : // - we write least-significant bits first,
25 : // - we use zig-zag encoding to encode both positive and negative numbers.
26 :
27 : namespace {
28 :
29 : // Each byte is encoded as MoreBit | ValueBits.
30 : class MoreBit : public BitField8<bool, 7, 1> {};
31 : class ValueBits : public BitField8<unsigned, 0, 7> {};
32 :
33 : // Helper: Add the offsets from 'other' to 'value'. Also set is_statement.
34 : void AddAndSetEntry(PositionTableEntry& value,
35 : const PositionTableEntry& other) {
36 97630228 : value.code_offset += other.code_offset;
37 97630228 : value.source_position += other.source_position;
38 97630228 : value.is_statement = other.is_statement;
39 : }
40 :
41 : // Helper: Subtract the offsets from 'other' from 'value'.
42 : void SubtractFromEntry(PositionTableEntry& value,
43 : const PositionTableEntry& other) {
44 23946159 : value.code_offset -= other.code_offset;
45 23946159 : value.source_position -= other.source_position;
46 : }
47 :
48 : // Helper: Encode an integer.
49 : template <typename T>
50 47892371 : void EncodeInt(ZoneVector<byte>& bytes, T value) {
51 : // Zig-zag encoding.
52 : static const int kShift = sizeof(T) * kBitsPerByte - 1;
53 47892371 : value = ((value << 1) ^ (value >> kShift));
54 : DCHECK_GE(value, 0);
55 47892371 : auto encoded = static_cast<typename std::make_unsigned<T>::type>(value);
56 : bool more;
57 52427440 : do {
58 52427336 : more = encoded > ValueBits::kMax;
59 : byte current =
60 104854672 : MoreBit::encode(more) | ValueBits::encode(encoded & ValueBits::kMask);
61 52427336 : bytes.push_back(current);
62 52427440 : encoded >>= ValueBits::kSize;
63 : } while (more);
64 47892475 : }
65 :
66 : // Encode a PositionTableEntry.
67 23946166 : void EncodeEntry(ZoneVector<byte>& bytes, const PositionTableEntry& entry) {
68 : // We only accept ascending code offsets.
69 : DCHECK_GE(entry.code_offset, 0);
70 : // Since code_offset is not negative, we use sign to encode is_statement.
71 : EncodeInt(bytes,
72 23946166 : entry.is_statement ? entry.code_offset : -entry.code_offset - 1);
73 23946207 : EncodeInt(bytes, entry.source_position);
74 23946249 : }
75 :
76 : // Helper: Decode an integer.
77 : template <typename T>
78 : T DecodeInt(ByteArray* bytes, int* index) {
79 : byte current;
80 : int shift = 0;
81 : T decoded = 0;
82 : bool more;
83 200688864 : do {
84 200688864 : current = bytes->get((*index)++);
85 200688864 : decoded |= static_cast<typename std::make_unsigned<T>::type>(
86 : ValueBits::decode(current))
87 : << shift;
88 : more = MoreBit::decode(current);
89 200688864 : shift += ValueBits::kSize;
90 : } while (more);
91 : DCHECK_GE(decoded, 0);
92 195260458 : decoded = (decoded >> 1) ^ (-(decoded & 1));
93 : return decoded;
94 : }
95 :
96 97630229 : void DecodeEntry(ByteArray* bytes, int* index, PositionTableEntry* entry) {
97 : int tmp = DecodeInt<int>(bytes, index);
98 97630229 : if (tmp >= 0) {
99 55252458 : entry->is_statement = true;
100 55252458 : entry->code_offset = tmp;
101 : } else {
102 42377771 : entry->is_statement = false;
103 42377771 : entry->code_offset = -(tmp + 1);
104 : }
105 97630229 : entry->source_position = DecodeInt<int64_t>(bytes, index);
106 97630229 : }
107 :
108 : } // namespace
109 :
110 3457308 : SourcePositionTableBuilder::SourcePositionTableBuilder(
111 : Zone* zone, SourcePositionTableBuilder::RecordingMode mode)
112 : : mode_(mode),
113 : bytes_(zone),
114 : #ifdef ENABLE_SLOW_DCHECKS
115 : raw_entries_(zone),
116 : #endif
117 3457308 : previous_() {
118 3457308 : }
119 :
120 30046578 : void SourcePositionTableBuilder::AddPosition(size_t code_offset,
121 : SourcePosition source_position,
122 30046578 : bool is_statement) {
123 60093218 : if (Omit()) return;
124 : DCHECK(source_position.IsKnown());
125 23946214 : int offset = static_cast<int>(code_offset);
126 23946214 : AddEntry({offset, source_position.raw(), is_statement});
127 : }
128 :
129 23946159 : void SourcePositionTableBuilder::AddEntry(const PositionTableEntry& entry) {
130 23946159 : PositionTableEntry tmp(entry);
131 23946159 : SubtractFromEntry(tmp, previous_);
132 23946159 : EncodeEntry(bytes_, tmp);
133 23946280 : previous_ = entry;
134 : #ifdef ENABLE_SLOW_DCHECKS
135 : raw_entries_.push_back(entry);
136 : #endif
137 23946280 : }
138 :
139 3455394 : Handle<ByteArray> SourcePositionTableBuilder::ToSourcePositionTable(
140 : Isolate* isolate) {
141 6076829 : if (bytes_.empty()) return isolate->factory()->empty_byte_array();
142 : DCHECK(!Omit());
143 :
144 : Handle<ByteArray> table = isolate->factory()->NewByteArray(
145 2621434 : static_cast<int>(bytes_.size()), TENURED);
146 :
147 2621435 : MemCopy(table->GetDataStartAddress(), &*bytes_.begin(), bytes_.size());
148 :
149 : #ifdef ENABLE_SLOW_DCHECKS
150 : // Brute force testing: Record all positions and decode
151 : // the entire table to verify they are identical.
152 : auto raw = raw_entries_.begin();
153 : for (SourcePositionTableIterator encoded(*table); !encoded.done();
154 : encoded.Advance(), raw++) {
155 : DCHECK(raw != raw_entries_.end());
156 : DCHECK_EQ(encoded.code_offset(), raw->code_offset);
157 : DCHECK_EQ(encoded.source_position().raw(), raw->source_position);
158 : DCHECK_EQ(encoded.is_statement(), raw->is_statement);
159 : }
160 : DCHECK(raw == raw_entries_.end());
161 : // No additional source positions after creating the table.
162 : mode_ = OMIT_SOURCE_POSITIONS;
163 : #endif
164 2621435 : return table;
165 : }
166 :
167 3295463 : SourcePositionTableIterator::SourcePositionTableIterator(ByteArray* byte_array)
168 6590926 : : raw_table_(byte_array) {
169 3295463 : Advance();
170 3295463 : }
171 :
172 504910 : SourcePositionTableIterator::SourcePositionTableIterator(
173 : Handle<ByteArray> byte_array)
174 504910 : : table_(byte_array) {
175 504910 : Advance();
176 : // We can enable allocation because we keep the table in a handle.
177 : no_gc.Release();
178 504909 : }
179 :
180 99325325 : void SourcePositionTableIterator::Advance() {
181 99325325 : ByteArray* table = raw_table_ ? raw_table_ : *table_;
182 : DCHECK(!done());
183 : DCHECK(index_ >= 0 && index_ <= table->length());
184 198650650 : if (index_ >= table->length()) {
185 1695096 : index_ = kDone;
186 : } else {
187 : PositionTableEntry tmp;
188 97630229 : DecodeEntry(table, &index_, &tmp);
189 : AddAndSetEntry(current_, tmp);
190 : }
191 99325324 : }
192 :
193 : } // namespace internal
194 : } // namespace v8
|
