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