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 7#include "src/objects-inl.h" 8#include "src/objects.h" 9 10namespace v8 { 11namespace internal { 12namespace interpreter { 13 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, 26// - we use zig-zag encoding to encode both positive and negative numbers. 27 28namespace { 29 30// Each byte is encoded as MoreBit | ValueBits. 31class MoreBit : public BitField8<bool, 7, 1> {}; 32class ValueBits : public BitField8<unsigned, 0, 7> {}; 33 34// Helper: Add the offsets from 'other' to 'value'. Also set is_statement. 35void 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'. 43void 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. 50void EncodeInt(ZoneVector<byte>& bytes, int value) { 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); 56 bool more; 57 do { 58 more = encoded > ValueBits::kMax; 59 bytes.push_back(MoreBit::encode(more) | 60 ValueBits::encode(encoded & ValueBits::kMask)); 61 encoded >>= ValueBits::kSize; 62 } while (more); 63} 64 65// Encode a PositionTableEntry. 66void EncodeEntry(ZoneVector<byte>& bytes, const PositionTableEntry& entry) { 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); 72 EncodeInt(bytes, entry.source_position); 73} 74 75// Helper: Decode an integer. 76void DecodeInt(ByteArray* bytes, int* index, int* v) { 77 byte current; 78 int shift = 0; 79 int decoded = 0; 80 bool more; 81 do { 82 current = bytes->get((*index)++); 83 decoded |= ValueBits::decode(current) << shift; 84 more = MoreBit::decode(current); 85 shift += ValueBits::kSize; 86 } while (more); 87 DCHECK_GE(decoded, 0); 88 decoded = (decoded >> 1) ^ (-(decoded & 1)); 89 *v = decoded; 90} 91 92void DecodeEntry(ByteArray* bytes, int* index, PositionTableEntry* entry) { 93 int tmp; 94 DecodeInt(bytes, index, &tmp); 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 } 102 DecodeInt(bytes, index, &entry->source_position); 103} 104 105} // namespace 106 107void SourcePositionTableBuilder::AddPosition(size_t bytecode_offset, 108 int source_position, 109 bool is_statement) { 110 int offset = static_cast<int>(bytecode_offset); 111 AddEntry({offset, source_position, is_statement}); 112} 113 114void SourcePositionTableBuilder::AddEntry(const PositionTableEntry& entry) { 115 PositionTableEntry tmp(entry); 116 SubtractFromEntry(tmp, previous_); 117 EncodeEntry(bytes_, tmp); 118 previous_ = entry; 119 120 if (entry.is_statement) { 121 LOG_CODE_EVENT(isolate_, CodeLinePosInfoAddStatementPositionEvent( 122 jit_handler_data_, entry.bytecode_offset, 123 entry.source_position)); 124 } 125 LOG_CODE_EVENT(isolate_, CodeLinePosInfoAddPositionEvent( 126 jit_handler_data_, entry.bytecode_offset, 127 entry.source_position)); 128 129#ifdef ENABLE_SLOW_DCHECKS 130 raw_entries_.push_back(entry); 131#endif 132} 133 134Handle<ByteArray> SourcePositionTableBuilder::ToSourcePositionTable() { 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 156 return table; 157} 158 159SourcePositionTableIterator::SourcePositionTableIterator(ByteArray* byte_array) 160 : table_(byte_array), index_(0), current_() { 161 Advance(); 162} 163 164void SourcePositionTableIterator::Advance() { 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); 173 } 174} 175 176} // namespace interpreter 177} // namespace internal 178} // namespace v8 179