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 11namespace v8 { 12namespace 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 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.code_offset += other.code_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.code_offset -= other.code_offset; 46 value.source_position -= other.source_position; 47} 48 49// Helper: Encode an integer. 50template <typename T> 51void EncodeInt(ZoneVector<byte>& bytes, T value) { 52 // Zig-zag encoding. 53 static const int kShift = sizeof(T) * kBitsPerByte - 1; 54 value = ((value << 1) ^ (value >> kShift)); 55 DCHECK_GE(value, 0); 56 auto encoded = static_cast<typename std::make_unsigned<T>::type>(value); 57 bool more; 58 do { 59 more = encoded > ValueBits::kMax; 60 byte current = 61 MoreBit::encode(more) | ValueBits::encode(encoded & ValueBits::kMask); 62 bytes.push_back(current); 63 encoded >>= ValueBits::kSize; 64 } while (more); 65} 66 67// Encode a PositionTableEntry. 68void 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 entry.is_statement ? entry.code_offset : -entry.code_offset - 1); 74 EncodeInt(bytes, entry.source_position); 75} 76 77// Helper: Decode an integer. 78template <typename T> 79T DecodeInt(ByteArray* bytes, int* index) { 80 byte current; 81 int shift = 0; 82 T decoded = 0; 83 bool more; 84 do { 85 current = bytes->get((*index)++); 86 decoded |= static_cast<typename std::make_unsigned<T>::type>( 87 ValueBits::decode(current)) 88 << shift; 89 more = MoreBit::decode(current); 90 shift += ValueBits::kSize; 91 } while (more); 92 DCHECK_GE(decoded, 0); 93 decoded = (decoded >> 1) ^ (-(decoded & 1)); 94 return decoded; 95} 96 97void DecodeEntry(ByteArray* bytes, int* index, PositionTableEntry* entry) { 98 int tmp = DecodeInt<int>(bytes, index); 99 if (tmp >= 0) { 100 entry->is_statement = true; 101 entry->code_offset = tmp; 102 } else { 103 entry->is_statement = false; 104 entry->code_offset = -(tmp + 1); 105 } 106 entry->source_position = DecodeInt<int64_t>(bytes, index); 107} 108 109} // namespace 110 111SourcePositionTableBuilder::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 previous_() { 119} 120 121void SourcePositionTableBuilder::AddPosition(size_t code_offset, 122 SourcePosition source_position, 123 bool is_statement) { 124 if (Omit()) return; 125 DCHECK(source_position.IsKnown()); 126 int offset = static_cast<int>(code_offset); 127 AddEntry({offset, source_position.raw(), is_statement}); 128} 129 130void SourcePositionTableBuilder::AddEntry(const PositionTableEntry& entry) { 131 PositionTableEntry tmp(entry); 132 SubtractFromEntry(tmp, previous_); 133 EncodeEntry(bytes_, tmp); 134 previous_ = entry; 135#ifdef ENABLE_SLOW_DCHECKS 136 raw_entries_.push_back(entry); 137#endif 138} 139 140Handle<ByteArray> SourcePositionTableBuilder::ToSourcePositionTable( 141 Isolate* isolate, Handle<AbstractCode> code) { 142 if (bytes_.empty()) return isolate->factory()->empty_byte_array(); 143 DCHECK(!Omit()); 144 145 Handle<ByteArray> table = isolate->factory()->NewByteArray( 146 static_cast<int>(bytes_.size()), TENURED); 147 148 MemCopy(table->GetDataStartAddress(), &*bytes_.begin(), bytes_.size()); 149 150 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 return table; 168} 169 170SourcePositionTableIterator::SourcePositionTableIterator(ByteArray* byte_array) 171 : table_(byte_array), index_(0), current_() { 172 Advance(); 173} 174 175void SourcePositionTableIterator::Advance() { 176 DCHECK(!done()); 177 DCHECK(index_ >= 0 && index_ <= table_->length()); 178 if (index_ >= table_->length()) { 179 index_ = kDone; 180 } else { 181 PositionTableEntry tmp; 182 DecodeEntry(table_, &index_, &tmp); 183 AddAndSetEntry(current_, tmp); 184 } 185} 186 187} // namespace internal 188} // namespace v8 189