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