Encode interpreter::SourcePositionTable as variable-length ints.

src/interpreter/source-position-table.cc

 // Copyright 2016 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/interpreter/source-position-table.h"
 
-#include "src/assembler.h"
 #include "src/objects-inl.h"
 #include "src/objects.h"
 
 namespace v8 {
 namespace internal {
 namespace interpreter {
 
-class IsStatementField : public BitField<bool, 0, 1> {};
-class SourcePositionField : public BitField<int, 1, 30> {};
+// We'll use a simple encoding scheme to record the source positions.
+// Conceptually, each position consists of:
+// - bytecode_offset: An integer index into the BytecodeArray
+// - source_position: An integer index into the source string.
+// - position type: Each position is either a statement or an expression.
+//
+// The basic idea for the encoding is to use a variable-length integer coding,
+// where each byte contains 7 bits of payload data, and 1 'more' bit that
+// determines whether additional bytes follow. Additionally:
+// - we record the difference from the previous position,
+// - we just stuff one bit for the type into the bytecode offset,
+// - we write least-significant bits first,
+// - negative numbers occur only rarely, so we use a denormalized
+//   most-significant byte (a byte with all zeros, which normally wouldn't make
+//   any sense)
+//   to encode a negative sign, so that we 'pay' nothing for positive numbers,
+//   but have to pay a full byte for negative integers.
+
+namespace {
+// Each byte is encoded as MoreBit | ValueBits.
+class MoreBit : public BitField8<bool, 7, 1> {};
+class ValueBits : public BitField8<int, 0, 7> {};
+
+// Bytecode offsets also include a bit for the position type in its least
+// significant digit.
+// Beware that the bytecode offset can be negative, and the default BitField
+// implementation might not do the right thing in this case.
+class TypeBit : public BitField<bool, 0, 1> {};
+class BytecodeOffsetBits : public BitField<int, 1, 31> {};
+
+// Helper: Add the offsets from 'other' to 'value'. Also set is_statement.
+void AddAndSetEntry(PositionTableEntry& value,
+                    const PositionTableEntry& other) {
+  value.bytecode_offset += other.bytecode_offset;
+  value.source_position += other.source_position;
+  value.is_statement = other.is_statement;
+}
+
+// Helper: Substract the offsets from 'other' from 'value'.
+void SubtractFromEntry(PositionTableEntry& value,
+                       const PositionTableEntry& other) {
+  value.bytecode_offset -= other.bytecode_offset;
+  value.source_position -= other.source_position;
+}
+
+// Helper: Encode an integer.
+void EncodeInt(ZoneVector<byte>& bytes, int value) {
+  DCHECK(abs(value) < (1 << 30));
+  bool sign = false;
+  if (value < 0) {
+    sign = true;
+    value = -value;
+  }
+
+  bool more;
+  do {
+    more = value > ValueBits::kMax;
+    bytes.push_back(MoreBit::encode(more || sign) |
+                    ValueBits::encode(value & ValueBits::kMax));
+    value >>= ValueBits::kSize;
+  } while (more);
+
+  if (sign) {
+    bytes.push_back(MoreBit::encode(false));
+  }
+}
+
+// Encode a PositionTableEntry.
+void EncodeEntry(ZoneVector<byte>& bytes, const PositionTableEntry& entry) {
+  EncodeInt(bytes, TypeBit::encode(entry.is_statement) |
+                       BytecodeOffsetBits::encode(entry.bytecode_offset &
+                                                  BytecodeOffsetBits::kMax));
+  EncodeInt(bytes, entry.source_position);
+}
+
+// Helper: Decode an integer.
+void DecodeInt(ByteArray* bytes, int* index, int* v) {
+  byte current;
+  int n = 0;
+  int value = 0;
+  bool more;
+  do {
+    current = bytes->get((*index)++);
+    value |= ValueBits::decode(current) << (n * ValueBits::kSize);
+    n++;
+    more = MoreBit::decode(current);
+  } while (more);
+
+  if (ValueBits::decode(current) == 0) {
+    value = -value;
+  }
+  *v = value;
+}
+
+void DecodeEntry(ByteArray* bytes, int* index, PositionTableEntry* entry) {
+  int tmp;
+  DecodeInt(bytes, index, &tmp);
+  entry->is_statement = TypeBit::decode(tmp);
+
+  // Directly shift tmp, because '>>' needs to be arithmetic shift in order to
+  // handle negative numbers properly.
+  entry->bytecode_offset = (tmp >> BytecodeOffsetBits::kShift);
+
+  DecodeInt(bytes, index, &entry->source_position);
+}
+
+}  // namespace
 
 void SourcePositionTableBuilder::AddStatementPosition(size_t bytecode_offset,
                                                       int source_position) {
-  int offset = static_cast<int>(bytecode_offset);
-  // If a position has already been assigned to this bytecode offset,
-  // do not reassign a new statement position.
-  if (CodeOffsetHasPosition(offset)) return;
-  uint32_t encoded = IsStatementField::encode(true) |
-                     SourcePositionField::encode(source_position);
-  entries_.push_back({offset, encoded});
+  AddEntry({static_cast<int>(bytecode_offset), source_position, true});
 }
 
 void SourcePositionTableBuilder::AddExpressionPosition(size_t bytecode_offset,
                                                        int source_position) {
-  int offset = static_cast<int>(bytecode_offset);
-  // If a position has already been assigned to this bytecode offset,
-  // do not reassign a new statement position.
-  if (CodeOffsetHasPosition(offset)) return;
-  uint32_t encoded = IsStatementField::encode(false) |
-                     SourcePositionField::encode(source_position);
-  entries_.push_back({offset, encoded});
+  AddEntry({static_cast<int>(bytecode_offset), source_position, false});
+}
+
+void SourcePositionTableBuilder::AddEntry(const PositionTableEntry& entry) {
+  if (!CodeOffsetHasPosition(entry.bytecode_offset)) {
+    EncodeCurrent();
+    current_ = entry;
+    has_current_ = true;
+
+#ifdef ENABLE_SLOW_DCHECKS
+    raw_entries_.push_back(entry);
+#endif
+  }
+}
+
+void SourcePositionTableBuilder::EncodeCurrent() {
+  if (has_current_) {
+    PositionTableEntry tmp(current_);
+    SubtractFromEntry(tmp, previous_);
+    EncodeEntry(bytes_, tmp);
+    previous_ = current_;
+    has_current_ = false;
+  }
+}
+
+bool SourcePositionTableBuilder::CodeOffsetHasPosition(
+    int bytecode_offset) const {
+  // Return whether bytecode offset already has a position assigned.
+  int most_recent_bytecode_offset =
+      (has_current_ ? current_ : previous_).bytecode_offset;
+  return bytes_.size() > 0 && (most_recent_bytecode_offset == bytecode_offset);
 }
 
 void SourcePositionTableBuilder::RevertPosition(size_t bytecode_offset) {

[rmcilroy, 2016/02/22 12:38:40]

I much prefer what you've done here (in PS 5 and 6) but I still think it would
be much simpler and less confusing to have BytecodeArrayBuilder trigger the
emittion when it emits the bytecode rather than trying to fix it up if it
decides not to emit a bytecode for a source position. 

Actually now I think of it, I think all we need to do is have the
BytecodeArrayBuilder::SetReturn/Statement/ExpressionPosition functions check for
exit_seen_in_block_ and only actually encode source position if this is not true
- this would avoid the whole need for reverting positions entirely. WDYT?

[vogelheim, 2016/02/22 18:33:33]

Done.

   int offset = static_cast<int>(bytecode_offset);
   // If we already added a source position table entry, but the bytecode array
   // builder ended up not outputting a bytecode for the corresponding bytecode
   // offset, we have to remove that entry.
-  if (CodeOffsetHasPosition(offset)) entries_.pop_back();
+  if (CodeOffsetHasPosition(offset)) {
+    DCHECK(has_current_);
+    has_current_ = false;
+
+#ifdef ENABLE_SLOW_DCHECKS
+    raw_entries_.pop_back();
+#endif
+  }
 }
 
-Handle<FixedArray> SourcePositionTableBuilder::ToFixedArray() {
-  int length = static_cast<int>(entries_.size());
-  Handle<FixedArray> table =
-      isolate_->factory()->NewFixedArray(length * 2, TENURED);
-  for (int i = 0; i < length; i++) {
-    table->set(i * 2, Smi::FromInt(entries_[i].bytecode_offset));
-    table->set(i * 2 + 1, Smi::FromInt(entries_[i].source_position_and_type));
+Handle<ByteArray> SourcePositionTableBuilder::ToSourcePositionTable() {
+  EncodeCurrent();
+
+  Handle<ByteArray> table = isolate_->factory()->NewByteArray(
+      static_cast<int>(bytes_.size()), TENURED);
+  if (bytes_.empty()) return table;
+
+  MemCopy(table->GetDataStartAddress(), &*bytes_.begin(), bytes_.size());
+
+#ifdef ENABLE_SLOW_DCHECKS
+  // Brute force testing: Record all positions and decode
+  // the entire table to verify they are identical.
+  auto raw = raw_entries_.begin();
+  for (SourcePositionTableIterator encoded(*table); !encoded.done();
+       encoded.Advance(), raw++) {
+    DCHECK(raw != raw_entries_.end());
+    DCHECK_EQ(encoded.bytecode_offset(), raw->bytecode_offset);
+    DCHECK_EQ(encoded.source_position(), raw->source_position);
+    DCHECK_EQ(encoded.is_statement(), raw->is_statement);
   }
+  DCHECK(raw == raw_entries_.end());
+#endif
+
   return table;
 }
 
-SourcePositionTableIterator::SourcePositionTableIterator(
-    BytecodeArray* bytecode_array)
-    : table_(bytecode_array->source_position_table()),
-      index_(0),
-      length_(table_->length()) {
-  DCHECK(table_->length() % 2 == 0);
+SourcePositionTableIterator::SourcePositionTableIterator(ByteArray* byte_array)
+    : table_(byte_array), index_(0), current_() {
   Advance();
 }
 
 void SourcePositionTableIterator::Advance() {
-  if (index_ < length_) {
-    int new_bytecode_offset = Smi::cast(table_->get(index_))->value();
-    // Bytecode offsets are in ascending order.
-    DCHECK(bytecode_offset_ < new_bytecode_offset || index_ == 0);
-    bytecode_offset_ = new_bytecode_offset;
-    uint32_t source_position_and_type =
-        static_cast<uint32_t>(Smi::cast(table_->get(index_ + 1))->value());
-    is_statement_ = IsStatementField::decode(source_position_and_type);
-    source_position_ = SourcePositionField::decode(source_position_and_type);
+  DCHECK(!done());
+  DCHECK(index_ >= 0 && index_ <= table_->length());
+  if (index_ == table_->length()) {
+    index_ = kDone;
+  } else {
+    PositionTableEntry tmp;
+    DecodeEntry(table_, &index_, &tmp);
+    AddAndSetEntry(current_, tmp);
   }
-  index_ += 2;
 }
 
 }  // namespace interpreter
 }  // namespace internal
 }  // namespace v8