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,
+// - negative numbers occur only rarely, so we use a denormalized lead byte
+//   (a lead 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 {
+// We'll use the BitField<..> template to handle the actual encoding.
+// Most bytes will be a MoreBit w/ ValueBits. If we also want to encode
+// the type, we'll have a byte with MoreBit, TypeBit, and TypeValueBits,
+// followed by zero or more 'normal' bytes.
+class MoreBit : public BitField8<bool, 7, 1> {};
+class ValueBits : public BitField8<int, 0, 7> {};
+class TypeBit : public BitField8<bool, 6, 1> {};
+class TypeValueBits : public BitField8<int, 0, 6> {};
+
+// Helper: Number of bytes for given value in 'value' bytes encoding.
+int SizeOfValue(int value) {
+  DCHECK(value >= 0);
+  int size = 1;
+  while (value >= (1 << (size * ValueBits::kSize))) size++;
+  return size;
+}
+
+// Helper: Number of bytes for given value (in 'type + value') bytes encoding.
+int SizeOfTypeValue(int value) {
+  DCHECK(value >= 0);
+  int size = 1;
+  while (value >= (1 << (TypeValueBits::kSize + (size - 1) * ValueBits::kSize)))
+    size++;
+  return size;
+}
+
+// Helper: Encode one 'normal' byte.
+void EncodeByte(ZoneVector<byte>& bytes, bool more, int value) {
+  bytes.push_back(MoreBit::encode(more) |

[rmcilroy, 2016/02/18 14:29:53]

DCHECK value is less than 7 bits?

+                  ValueBits::encode(value & ValueBits::kMax));
+}
+
+// Helper: Encode a byte w/ a type value.
+void EncodeTypeByte(ZoneVector<byte>& bytes, bool more, bool type, int value) {
+  bytes.push_back(MoreBit::encode(more) | TypeBit::encode(type) |

[rmcilroy, 2016/02/18 14:29:53]

Ditto, but 6 bits?

+                  TypeValueBits::encode(value & TypeValueBits::kMax));
+}
+
+// Helper: Encode a positive integer w/ the given size.
+void EncodeBytes(ZoneVector<byte>& bytes, int value, int size) {
+  DCHECK(value >= 0);
+  for (int i = 0; i < size; i++) {
+    int byte_no = size - i - 1;
+    EncodeByte(bytes, byte_no != 0, value >> (ValueBits::kSize * byte_no));
+  }
+}
+
+// Encode an integer.
+void EncodeValue(ZoneVector<byte>& bytes, int value) {
+  if (value < 0) {
+    DCHECK(value != INT_MIN);
+    EncodeByte(bytes, true, 0);
+    value = -value;
+  }
+  EncodeBytes(bytes, value, SizeOfValue(value));
+}
+
+// Encode an integer and a type bit.
+void EncodeTypeValue(ZoneVector<byte>& bytes, bool type, int value) {
+  if (value < 0) {
+    DCHECK(value != INT_MIN);
+    EncodeTypeByte(bytes, true, type, 0);
+    EncodeTypeValue(bytes, false, -value);
+  } else {
+    int size = SizeOfTypeValue(value);
+    EncodeTypeByte(bytes, (size > 1), type,
+                   value >> (size - 1) * ValueBits::kSize);
+    EncodeBytes(bytes, value, size - 1);

[rmcilroy, 2016/02/18 14:29:53]

This is a bit magic, i.e., you are relying on the fact that size is less than
what is required for EncodeBytes of this value and that it will therefore only
encode the bottom bytes of the value. I think this would all be a lot simpler if
you did the seperation between TypeValues and Values at a higher level, and just
feed the encoding helpers raw ints which it encodes uniformly with the variable
byte compression scheme. To do this, you might want to have a typed value have
value first, and be shifted up by one with the type bit in the LSB of the value
(to keep the values small for this compression scheme). WDYT?

[vogelheim, 2016/02/18 17:11:19]

Not sure...

My intent was this:

The methods called Encode*Value (also Decode*Value) have a sane interface and
will safely encode the value you put in. However, if I want to avoid code
duplication, I also need some low level helper functions that aren't safe, and
that will rely on their parameters being just right. Those are the Encode*Byte*
versions. The anonymous namespace provides some degree of protection against
mis-use.

EncodeBytes was originally called EncodeRemainder, which might make its purpose
a bit more clear.


I think I'll just implement an alternative as you suggest, and see if I like it
better...

+  }
+}
+
+// Helper: Decode a series of 'value' bytes. Assume the current byte has
+// been decoded, but use it to decide whether we need more bytes.
+void DecodeBytes(const byte* bytes, int* index, int& value) {
+  byte current = bytes[(*index)++];
+  while (MoreBit::decode(current)) {
+    current = bytes[(*index)++];
+    value = (value << ValueBits::kSize) + ValueBits::decode(current);
+  }
+}
+
+// Decode an integer at bytes.get(index). Inverse of EncodeValue.
+int DecodeValue(const byte* bytes, int* index) {
+  byte current = bytes[*index];
+  int val = ValueBits::decode(current);
+  bool sign = (val == 0);
+  DecodeBytes(bytes, index, val);
+  return sign ? -val : val;
+}
+
+// Decode an integer and a type bit at bytes.get(index). Inverse of
+// EncodeTypeValue.
+int DecodeTypeValue(const byte* bytes, int* index, bool* type) {
+  int old_index = *index;
+  byte current = bytes[*index];
+  *type = TypeBit::decode(current);
+  int val = TypeValueBits::decode(current);
+  DecodeBytes(bytes, index, val);
+  bool sign = (*index - old_index) > SizeOfTypeValue(val);
+  return sign ? -val : val;
+}
+
+// Helper: Scan one value backwards.
+// *index is expected to point behind the current 'complete' value encoding
+// and will be set to point behind he previous one.
+void EncodeScanBackwards(ZoneVector<byte>& bytes, int* index) {
+  DCHECK(bytes.size() > 0);
+  DCHECK(*index > 0);
+
+  // Index is expected to point behind a 'complete' value encoding.
+  (*index)--;
+  DCHECK(!MoreBit::decode(bytes[*index]));
+
+  // Scan back until we either hit the beginning of our bytes, or another byte
+  // without 'more' bit.
+  while (*index > 0 && MoreBit::decode(bytes[(*index) - 1])) {
+    (*index)--;
+  }
+  DCHECK(*index >= 0);
+}
+
+}  // namespace
+
+// SourcePositionTableBuilder
 
 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)) {
+    EncodeTypeValue(bytes_, entry.is_statement,
+                    entry.bytecode_offset - previous_bytecode_offset_);
+    EncodeValue(bytes_, entry.source_position - previous_source_position_);
+
+    previous_bytecode_offset_ = entry.bytecode_offset;
+    previous_source_position_ = entry.source_position;
+
+#ifdef ENABLE_SLOW_DCHECKS
+    raw_entries_.push_back(entry);
+#endif
+  }
 }
 
 void SourcePositionTableBuilder::RevertPosition(size_t bytecode_offset) {
   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)) {
+    // Reverting means we need to discard 2 variable length ints. We also need

[rmcilroy, 2016/02/18 14:29:53]

Hmm, I now like this RevertPosition function even less than when it was
originally added :/. Could we remove it and instead have the
bytecode-array-builder keep track of the last source / expression position and
only add it to the source position table if a bytecode gets emitted (i.e., throw
it away if exit_seen_in_block_ where we currently call RevertPosition)?

+    // to read them, in order to fixup the previous_*_ member variables.
+
+    // Scan backwards for 2 values.
+    int index = static_cast<int>(bytes_.size());
+    EncodeScanBackwards(bytes_, &index);
+    EncodeScanBackwards(bytes_, &index);
+
+    // Read from index to adjust previous_* values, but throw away all other
+    // info.
+    {
+      int tmp_index = index;
+      bool tmp_type;
+      previous_bytecode_offset_ -=
+          DecodeTypeValue(&*bytes_.begin(), &tmp_index, &tmp_type);
+      previous_source_position_ -= DecodeValue(&*bytes_.begin(), &tmp_index);
+    }
+
+    bytes_.resize(index);
+
+#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() {
+  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()),
+// SourcePositionTableIterator
+
+SourcePositionTableIterator::SourcePositionTableIterator(ByteArray* byte_array)
+    : table_(byte_array),
       index_(0),
-      length_(table_->length()) {
-  DCHECK(table_->length() % 2 == 0);
+      previous_bytecode_offset_(0),
+      previous_source_position_(0),
+      current_({0, 0, false}) {
   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 {
+    byte* bytes = table_->GetDataStartAddress();
+
+    previous_bytecode_offset_ +=
+        DecodeTypeValue(bytes, &index_, &(current_.is_statement));
+    previous_source_position_ += DecodeValue(bytes, &index_);
+
+    current_.bytecode_offset = previous_bytecode_offset_;
+    current_.source_position = previous_source_position_;
   }
-  index_ += 2;
 }
 
 }  // namespace interpreter
 }  // namespace internal
 }  // namespace v8