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/log.h"
8 : #include "src/objects-inl.h"
9 : #include "src/objects.h"
10 :
11 : namespace v8 {
12 : namespace internal {
13 :
14 : // We'll use a simple encoding scheme to record the source positions.
15 : // Conceptually, each position consists of:
16 : // - code_offset: An integer index into the BytecodeArray or code.
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 code offset,
25 : // - we write least-significant bits first,
26 : // - we use zig-zag encoding to encode both positive and negative numbers.
27 :
28 : namespace {
29 :
30 : // Each byte is encoded as MoreBit | ValueBits.
31 : class MoreBit : public BitField8<bool, 7, 1> {};
32 : class ValueBits : public BitField8<unsigned, 0, 7> {};
33 :
34 : // Helper: Add the offsets from 'other' to 'value'. Also set is_statement.
35 : void AddAndSetEntry(PositionTableEntry& value,
36 : const PositionTableEntry& other) {
37 219647933 : value.code_offset += other.code_offset;
38 219647933 : value.source_position += other.source_position;
39 219647933 : value.is_statement = other.is_statement;
40 : }
41 :
42 : // Helper: Substract the offsets from 'other' from 'value'.
43 : void SubtractFromEntry(PositionTableEntry& value,
44 : const PositionTableEntry& other) {
45 53078664 : value.code_offset -= other.code_offset;
46 53078664 : value.source_position -= other.source_position;
47 : }
48 :
49 : // Helper: Encode an integer.
50 : template <typename T>
51 106157300 : void EncodeInt(ZoneVector<byte>& bytes, T value) {
52 : // Zig-zag encoding.
53 : static const int kShift = sizeof(T) * kBitsPerByte - 1;
54 106157300 : value = ((value << 1) ^ (value >> kShift));
55 : DCHECK_GE(value, 0);
56 106157300 : auto encoded = static_cast<typename std::make_unsigned<T>::type>(value);
57 : bool more;
58 115286248 : do {
59 115286251 : more = encoded > ValueBits::kMax;
60 : byte current =
61 230572502 : MoreBit::encode(more) | ValueBits::encode(encoded & ValueBits::kMask);
62 115286251 : bytes.push_back(current);
63 115286248 : encoded >>= ValueBits::kSize;
64 : } while (more);
65 106157297 : }
66 :
67 : // Encode a PositionTableEntry.
68 53078687 : void EncodeEntry(ZoneVector<byte>& bytes, const PositionTableEntry& entry) {
69 : // We only accept ascending code offsets.
70 : DCHECK(entry.code_offset >= 0);
71 : // Since code_offset is not negative, we use sign to encode is_statement.
72 : EncodeInt(bytes,
73 53078687 : entry.is_statement ? entry.code_offset : -entry.code_offset - 1);
74 53078650 : EncodeInt(bytes, entry.source_position);
75 53078632 : }
76 :
77 : // Helper: Decode an integer.
78 : template <typename T>
79 : T DecodeInt(ByteArray* bytes, int* index) {
80 : byte current;
81 : int shift = 0;
82 : T decoded = 0;
83 : bool more;
84 449048048 : do {
85 449048048 : current = bytes->get((*index)++);
86 449048048 : decoded |= static_cast<typename std::make_unsigned<T>::type>(
87 : ValueBits::decode(current))
88 : << shift;
89 : more = MoreBit::decode(current);
90 449048048 : shift += ValueBits::kSize;
91 : } while (more);
92 : DCHECK_GE(decoded, 0);
93 439295870 : decoded = (decoded >> 1) ^ (-(decoded & 1));
94 : return decoded;
95 : }
96 :
97 219647935 : void DecodeEntry(ByteArray* bytes, int* index, PositionTableEntry* entry) {
98 : int tmp = DecodeInt<int>(bytes, index);
99 219647935 : if (tmp >= 0) {
100 92515641 : entry->is_statement = true;
101 92515641 : entry->code_offset = tmp;
102 : } else {
103 127132294 : entry->is_statement = false;
104 127132294 : entry->code_offset = -(tmp + 1);
105 : }
106 219647935 : entry->source_position = DecodeInt<int64_t>(bytes, index);
107 219647935 : }
108 :
109 : } // namespace
110 :
111 4375576 : SourcePositionTableBuilder::SourcePositionTableBuilder(
112 : Zone* zone, SourcePositionTableBuilder::RecordingMode mode)
113 : : mode_(mode),
114 : bytes_(zone),
115 : #ifdef ENABLE_SLOW_DCHECKS
116 : raw_entries_(zone),
117 : #endif
118 4375576 : previous_() {
119 4375576 : }
120 :
121 71083546 : void SourcePositionTableBuilder::AddPosition(size_t code_offset,
122 : SourcePosition source_position,
123 71083546 : bool is_statement) {
124 142167068 : if (Omit()) return;
125 : DCHECK(source_position.IsKnown());
126 53078678 : int offset = static_cast<int>(code_offset);
127 53078678 : AddEntry({offset, source_position.raw(), is_statement});
128 : }
129 :
130 53078664 : void SourcePositionTableBuilder::AddEntry(const PositionTableEntry& entry) {
131 53078664 : PositionTableEntry tmp(entry);
132 53078664 : SubtractFromEntry(tmp, previous_);
133 53078664 : EncodeEntry(bytes_, tmp);
134 53078655 : previous_ = entry;
135 : #ifdef ENABLE_SLOW_DCHECKS
136 : raw_entries_.push_back(entry);
137 : #endif
138 53078655 : }
139 :
140 4374457 : Handle<ByteArray> SourcePositionTableBuilder::ToSourcePositionTable(
141 3260002 : Isolate* isolate, Handle<AbstractCode> code) {
142 7634459 : if (bytes_.empty()) return isolate->factory()->empty_byte_array();
143 : DCHECK(!Omit());
144 :
145 : Handle<ByteArray> table = isolate->factory()->NewByteArray(
146 3259999 : static_cast<int>(bytes_.size()), TENURED);
147 :
148 3260002 : MemCopy(table->GetDataStartAddress(), &*bytes_.begin(), bytes_.size());
149 :
150 3260351 : LOG_CODE_EVENT(isolate, CodeLinePosInfoRecordEvent(*code, *table));
151 :
152 : #ifdef ENABLE_SLOW_DCHECKS
153 : // Brute force testing: Record all positions and decode
154 : // the entire table to verify they are identical.
155 : auto raw = raw_entries_.begin();
156 : for (SourcePositionTableIterator encoded(*table); !encoded.done();
157 : encoded.Advance(), raw++) {
158 : DCHECK(raw != raw_entries_.end());
159 : DCHECK_EQ(encoded.code_offset(), raw->code_offset);
160 : DCHECK_EQ(encoded.source_position().raw(), raw->source_position);
161 : DCHECK_EQ(encoded.is_statement(), raw->is_statement);
162 : }
163 : DCHECK(raw == raw_entries_.end());
164 : // No additional source positions after creating the table.
165 : mode_ = OMIT_SOURCE_POSITIONS;
166 : #endif
167 3260001 : return table;
168 : }
169 :
170 5212370 : SourcePositionTableIterator::SourcePositionTableIterator(ByteArray* byte_array)
171 5212370 : : table_(byte_array), index_(0), current_() {
172 5212370 : Advance();
173 5212369 : }
174 :
175 221973142 : void SourcePositionTableIterator::Advance() {
176 : DCHECK(!done());
177 : DCHECK(index_ >= 0 && index_ <= table_->length());
178 443946284 : if (index_ >= table_->length()) {
179 2325201 : index_ = kDone;
180 : } else {
181 : PositionTableEntry tmp;
182 219647941 : DecodeEntry(table_, &index_, &tmp);
183 : AddAndSetEntry(current_, tmp);
184 : }
185 221973134 : }
186 :
187 : } // namespace internal
188 : } // namespace v8
|
