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 116643352 : value.code_offset += other.code_offset;
37 116643352 : value.source_position += other.source_position;
38 116643352 : 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 35579899 : value.code_offset -= other.code_offset;
45 35579899 : value.source_position -= other.source_position;
46 : }
47 :
48 : // Helper: Encode an integer.
49 : template <typename T>
50 71159950 : void EncodeInt(std::vector<byte>& bytes, T value) {
51 : // Zig-zag encoding.
52 : static const int kShift = sizeof(T) * kBitsPerByte - 1;
53 71159950 : value = ((value << 1) ^ (value >> kShift));
54 : DCHECK_GE(value, 0);
55 71159950 : auto encoded = static_cast<typename std::make_unsigned<T>::type>(value);
56 : bool more;
57 76838953 : do {
58 76837376 : more = encoded > ValueBits::kMax;
59 : byte current =
60 153674752 : MoreBit::encode(more) | ValueBits::encode(encoded & ValueBits::kMask);
61 76837376 : bytes.push_back(current);
62 76838953 : encoded >>= ValueBits::kSize;
63 : } while (more);
64 71161527 : }
65 :
66 : // Encode a PositionTableEntry.
67 35584048 : void EncodeEntry(std::vector<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 35584048 : entry.is_statement ? entry.code_offset : -entry.code_offset - 1);
73 35580410 : EncodeInt(bytes, entry.source_position);
74 35580902 : }
75 :
76 : // Helper: Decode an integer.
77 : template <typename T>
78 : T DecodeInt(Vector<const byte> bytes, int* index) {
79 : byte current;
80 : int shift = 0;
81 : T decoded = 0;
82 : bool more;
83 240534211 : do {
84 481068422 : current = bytes[(*index)++];
85 240534211 : decoded |= static_cast<typename std::make_unsigned<T>::type>(
86 : ValueBits::decode(current))
87 : << shift;
88 : more = MoreBit::decode(current);
89 240534211 : shift += ValueBits::kSize;
90 : } while (more);
91 : DCHECK_GE(decoded, 0);
92 233286704 : decoded = (decoded >> 1) ^ (-(decoded & 1));
93 : return decoded;
94 : }
95 :
96 116643352 : void DecodeEntry(Vector<const byte> bytes, int* index,
97 : PositionTableEntry* entry) {
98 : int tmp = DecodeInt<int>(bytes, index);
99 116643352 : if (tmp >= 0) {
100 66995866 : entry->is_statement = true;
101 66995866 : entry->code_offset = tmp;
102 : } else {
103 49647486 : entry->is_statement = false;
104 49647486 : entry->code_offset = -(tmp + 1);
105 : }
106 116643352 : entry->source_position = DecodeInt<int64_t>(bytes, index);
107 116643352 : }
108 :
109 : Vector<const byte> VectorFromByteArray(ByteArray byte_array) {
110 : return Vector<const byte>(byte_array->GetDataStartAddress(),
111 11920516 : byte_array->length());
112 : }
113 :
114 : #ifdef ENABLE_SLOW_DCHECKS
115 : void CheckTableEquals(std::vector<PositionTableEntry>& raw_entries,
116 : SourcePositionTableIterator& encoded) {
117 : // Brute force testing: Record all positions and decode
118 : // the entire table to verify they are identical.
119 : auto raw = raw_entries.begin();
120 : for (; !encoded.done(); encoded.Advance(), raw++) {
121 : DCHECK(raw != raw_entries.end());
122 : DCHECK_EQ(encoded.code_offset(), raw->code_offset);
123 : DCHECK_EQ(encoded.source_position().raw(), raw->source_position);
124 : DCHECK_EQ(encoded.is_statement(), raw->is_statement);
125 : }
126 : DCHECK(raw == raw_entries.end());
127 : }
128 : #endif
129 :
130 : } // namespace
131 :
132 5792431 : SourcePositionTableBuilder::SourcePositionTableBuilder(
133 : SourcePositionTableBuilder::RecordingMode mode)
134 11584862 : : mode_(mode), previous_() {}
135 :
136 35580464 : void SourcePositionTableBuilder::AddPosition(size_t code_offset,
137 : SourcePosition source_position,
138 35580464 : bool is_statement) {
139 71161471 : if (Omit()) return;
140 : DCHECK(source_position.IsKnown());
141 35580691 : int offset = static_cast<int>(code_offset);
142 35580691 : AddEntry({offset, source_position.raw(), is_statement});
143 : }
144 :
145 35579899 : void SourcePositionTableBuilder::AddEntry(const PositionTableEntry& entry) {
146 35579899 : PositionTableEntry tmp(entry);
147 35579899 : SubtractFromEntry(tmp, previous_);
148 35579899 : EncodeEntry(bytes_, tmp);
149 35581052 : previous_ = entry;
150 : #ifdef ENABLE_SLOW_DCHECKS
151 : raw_entries_.push_back(entry);
152 : #endif
153 35581052 : }
154 :
155 3987640 : Handle<ByteArray> SourcePositionTableBuilder::ToSourcePositionTable(
156 : Isolate* isolate) {
157 6531093 : if (bytes_.empty()) return isolate->factory()->empty_byte_array();
158 : DCHECK(!Omit());
159 :
160 : Handle<ByteArray> table = isolate->factory()->NewByteArray(
161 2543435 : static_cast<int>(bytes_.size()), TENURED);
162 : MemCopy(table->GetDataStartAddress(), bytes_.data(), bytes_.size());
163 :
164 : #ifdef ENABLE_SLOW_DCHECKS
165 : // Brute force testing: Record all positions and decode
166 : // the entire table to verify they are identical.
167 : SourcePositionTableIterator it(*table);
168 : CheckTableEquals(raw_entries_, it);
169 : // No additional source positions after creating the table.
170 : mode_ = OMIT_SOURCE_POSITIONS;
171 : #endif
172 2543432 : return table;
173 : }
174 :
175 1755648 : OwnedVector<byte> SourcePositionTableBuilder::ToSourcePositionTableVector() {
176 1755648 : if (bytes_.empty()) return OwnedVector<byte>();
177 : DCHECK(!Omit());
178 :
179 327806 : OwnedVector<byte> table = OwnedVector<byte>::Of(bytes_);
180 :
181 : #ifdef ENABLE_SLOW_DCHECKS
182 : // Brute force testing: Record all positions and decode
183 : // the entire table to verify they are identical.
184 : SourcePositionTableIterator it(table.as_vector());
185 : CheckTableEquals(raw_entries_, it);
186 : // No additional source positions after creating the table.
187 : mode_ = OMIT_SOURCE_POSITIONS;
188 : #endif
189 : return table;
190 : }
191 :
192 4266467 : SourcePositionTableIterator::SourcePositionTableIterator(ByteArray byte_array)
193 8532934 : : raw_table_(VectorFromByteArray(byte_array)) {
194 4266467 : Advance();
195 4266467 : }
196 :
197 523128 : SourcePositionTableIterator::SourcePositionTableIterator(
198 : Handle<ByteArray> byte_array)
199 523128 : : table_(byte_array) {
200 523128 : Advance();
201 : #ifdef DEBUG
202 : // We can enable allocation because we keep the table in a handle.
203 : no_gc.Release();
204 : #endif // DEBUG
205 523130 : }
206 :
207 171787 : SourcePositionTableIterator::SourcePositionTableIterator(
208 : Vector<const byte> bytes)
209 343574 : : raw_table_(bytes) {
210 171787 : Advance();
211 : #ifdef DEBUG
212 : // We can enable allocation because the underlying vector does not move.
213 : no_gc.Release();
214 : #endif // DEBUG
215 171787 : }
216 :
217 119327283 : void SourcePositionTableIterator::Advance() {
218 : Vector<const byte> bytes =
219 119327283 : table_.is_null() ? raw_table_ : VectorFromByteArray(*table_);
220 : DCHECK(!done());
221 : DCHECK(index_ >= 0 && index_ <= bytes.length());
222 238654574 : if (index_ >= bytes.length()) {
223 2683931 : index_ = kDone;
224 : } else {
225 : PositionTableEntry tmp;
226 116643356 : DecodeEntry(bytes, &index_, &tmp);
227 : AddAndSetEntry(current_, tmp);
228 : }
229 119327283 : }
230 :
231 : } // namespace internal
232 183867 : } // namespace v8
|
