1109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch// Copyright 2016 the V8 project authors. All rights reserved. 2109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch// Use of this source code is governed by a BSD-style license that can be 3109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch// found in the LICENSE file. 4109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch 5f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch#include "src/source-position-table.h" 6109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch 7f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch#include "src/log.h" 8109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch#include "src/objects-inl.h" 9109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch#include "src/objects.h" 10109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch 11109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdochnamespace v8 { 12109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdochnamespace internal { 13109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch 143b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch// We'll use a simple encoding scheme to record the source positions. 153b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch// Conceptually, each position consists of: 16f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// - code_offset: An integer index into the BytecodeArray or code. 173b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch// - source_position: An integer index into the source string. 183b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch// - position type: Each position is either a statement or an expression. 193b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch// 203b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch// The basic idea for the encoding is to use a variable-length integer coding, 213b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch// where each byte contains 7 bits of payload data, and 1 'more' bit that 223b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch// determines whether additional bytes follow. Additionally: 233b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch// - we record the difference from the previous position, 24f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// - we just stuff one bit for the type into the code offset, 253b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch// - we write least-significant bits first, 2613e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch// - we use zig-zag encoding to encode both positive and negative numbers. 273b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch 283b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdochnamespace { 293b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch 303b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch// Each byte is encoded as MoreBit | ValueBits. 313b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdochclass MoreBit : public BitField8<bool, 7, 1> {}; 3213e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdochclass ValueBits : public BitField8<unsigned, 0, 7> {}; 333b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch 343b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch// Helper: Add the offsets from 'other' to 'value'. Also set is_statement. 353b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdochvoid AddAndSetEntry(PositionTableEntry& value, 363b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch const PositionTableEntry& other) { 37f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch value.code_offset += other.code_offset; 383b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch value.source_position += other.source_position; 393b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch value.is_statement = other.is_statement; 403b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch} 413b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch 423b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch// Helper: Substract the offsets from 'other' from 'value'. 433b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdochvoid SubtractFromEntry(PositionTableEntry& value, 443b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch const PositionTableEntry& other) { 45f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch value.code_offset -= other.code_offset; 463b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch value.source_position -= other.source_position; 473b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch} 483b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch 493b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch// Helper: Encode an integer. 50c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdochtemplate <typename T> 51c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdochvoid EncodeInt(ZoneVector<byte>& bytes, T value) { 5213e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch // Zig-zag encoding. 53c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch static const int kShift = sizeof(T) * kBitsPerByte - 1; 5413e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch value = ((value << 1) ^ (value >> kShift)); 5513e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch DCHECK_GE(value, 0); 56c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch auto encoded = static_cast<typename std::make_unsigned<T>::type>(value); 573b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch bool more; 583b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch do { 5913e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch more = encoded > ValueBits::kMax; 60c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch byte current = 61c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch MoreBit::encode(more) | ValueBits::encode(encoded & ValueBits::kMask); 62c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch bytes.push_back(current); 6313e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch encoded >>= ValueBits::kSize; 643b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch } while (more); 653b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch} 663b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch 673b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch// Encode a PositionTableEntry. 683b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdochvoid EncodeEntry(ZoneVector<byte>& bytes, const PositionTableEntry& entry) { 69f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // We only accept ascending code offsets. 70f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch DCHECK(entry.code_offset >= 0); 71f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // Since code_offset is not negative, we use sign to encode is_statement. 72f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch EncodeInt(bytes, 73f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch entry.is_statement ? entry.code_offset : -entry.code_offset - 1); 743b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch EncodeInt(bytes, entry.source_position); 753b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch} 763b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch 773b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch// Helper: Decode an integer. 78c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdochtemplate <typename T> 79c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen MurdochT DecodeInt(ByteArray* bytes, int* index) { 803b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch byte current; 8113e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch int shift = 0; 82c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch T decoded = 0; 833b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch bool more; 843b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch do { 853b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch current = bytes->get((*index)++); 86c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch decoded |= static_cast<typename std::make_unsigned<T>::type>( 87c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch ValueBits::decode(current)) 88c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch << shift; 893b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch more = MoreBit::decode(current); 9013e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch shift += ValueBits::kSize; 913b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch } while (more); 9213e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch DCHECK_GE(decoded, 0); 9313e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch decoded = (decoded >> 1) ^ (-(decoded & 1)); 94c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch return decoded; 953b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch} 963b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch 973b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdochvoid DecodeEntry(ByteArray* bytes, int* index, PositionTableEntry* entry) { 98c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch int tmp = DecodeInt<int>(bytes, index); 9913e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch if (tmp >= 0) { 10013e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch entry->is_statement = true; 101f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch entry->code_offset = tmp; 10213e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch } else { 10313e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch entry->is_statement = false; 104f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch entry->code_offset = -(tmp + 1); 10513e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch } 106c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch entry->source_position = DecodeInt<int64_t>(bytes, index); 1073b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch} 1083b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch 1093b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch} // namespace 110109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch 111f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen MurdochSourcePositionTableBuilder::SourcePositionTableBuilder( 112f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch Zone* zone, SourcePositionTableBuilder::RecordingMode mode) 113f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch : mode_(mode), 114f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch bytes_(zone), 115f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch#ifdef ENABLE_SLOW_DCHECKS 116f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch raw_entries_(zone), 117f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch#endif 118f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch previous_() { 119f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch} 120f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 121f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdochvoid SourcePositionTableBuilder::AddPosition(size_t code_offset, 122c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch SourcePosition source_position, 123bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch bool is_statement) { 124f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch if (Omit()) return; 125c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch DCHECK(source_position.IsKnown()); 126f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch int offset = static_cast<int>(code_offset); 127c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch AddEntry({offset, source_position.raw(), is_statement}); 128109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch} 129109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch 1303b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdochvoid SourcePositionTableBuilder::AddEntry(const PositionTableEntry& entry) { 131bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch PositionTableEntry tmp(entry); 1323b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch SubtractFromEntry(tmp, previous_); 1333b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch EncodeEntry(bytes_, tmp); 134bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch previous_ = entry; 1353b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch#ifdef ENABLE_SLOW_DCHECKS 136bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch raw_entries_.push_back(entry); 1373b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch#endif 1383b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch} 1393b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch 140f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen MurdochHandle<ByteArray> SourcePositionTableBuilder::ToSourcePositionTable( 141f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch Isolate* isolate, Handle<AbstractCode> code) { 142f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch if (bytes_.empty()) return isolate->factory()->empty_byte_array(); 143f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch DCHECK(!Omit()); 1443b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch 145f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch Handle<ByteArray> table = isolate->factory()->NewByteArray( 1463b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch static_cast<int>(bytes_.size()), TENURED); 1473b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch 1483b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch MemCopy(table->GetDataStartAddress(), &*bytes_.begin(), bytes_.size()); 1493b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch 150f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch LOG_CODE_EVENT(isolate, CodeLinePosInfoRecordEvent(*code, *table)); 151f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 1523b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch#ifdef ENABLE_SLOW_DCHECKS 1533b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch // Brute force testing: Record all positions and decode 1543b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch // the entire table to verify they are identical. 1553b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch auto raw = raw_entries_.begin(); 1563b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch for (SourcePositionTableIterator encoded(*table); !encoded.done(); 1573b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch encoded.Advance(), raw++) { 1583b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch DCHECK(raw != raw_entries_.end()); 159f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch DCHECK_EQ(encoded.code_offset(), raw->code_offset); 160c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch DCHECK_EQ(encoded.source_position().raw(), raw->source_position); 1613b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch DCHECK_EQ(encoded.is_statement(), raw->is_statement); 1623b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch } 1633b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch DCHECK(raw == raw_entries_.end()); 164f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // No additional source positions after creating the table. 165f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch mode_ = OMIT_SOURCE_POSITIONS; 1663b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch#endif 167109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch return table; 168109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch} 169109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch 1703b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben MurdochSourcePositionTableIterator::SourcePositionTableIterator(ByteArray* byte_array) 1713b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch : table_(byte_array), index_(0), current_() { 172109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch Advance(); 173109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch} 174109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch 175109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdochvoid SourcePositionTableIterator::Advance() { 1763b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch DCHECK(!done()); 1773b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch DCHECK(index_ >= 0 && index_ <= table_->length()); 178c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch if (index_ >= table_->length()) { 1793b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch index_ = kDone; 1803b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch } else { 1813b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch PositionTableEntry tmp; 1823b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch DecodeEntry(table_, &index_, &tmp); 1833b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch AddAndSetEntry(current_, tmp); 184109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch } 185109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch} 186109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch 187109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch} // namespace internal 188109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch} // namespace v8 189