Revert of 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 {
 
-// 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 {
-
-// A zero-value in the most-significant byte is used to mark negative numbers.
-const int kNegativeSignMarker = 0;
-
-// Each byte is encoded as MoreBit | ValueBits.
-class MoreBit : public BitField8<bool, 7, 1> {};
-class ValueBits : public BitField8<int, 0, 7> {};
-
-// 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) {
-  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) |
-                    ValueBits::encode(kNegativeSignMarker));
-  }
-}
-
-// Encode a PositionTableEntry.
-void EncodeEntry(ZoneVector<byte>& bytes, const PositionTableEntry& entry) {
-  // 1 bit for sign + is_statement each, which leaves 30b for the value.
-  DCHECK(abs(entry.bytecode_offset) < (1 << 30));
-  EncodeInt(bytes, (entry.is_statement ? 1 : 0) | (entry.bytecode_offset << 1));
-  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) == kNegativeSignMarker) {
-    value = -value;
-  }
-  *v = value;
-}
-
-void DecodeEntry(ByteArray* bytes, int* index, PositionTableEntry* entry) {
-  int tmp;
-  DecodeInt(bytes, index, &tmp);
-  entry->is_statement = (tmp & 1);
-
-  // Note that '>>' needs to be arithmetic shift in order to handle negative
-  // numbers properly.
-  entry->bytecode_offset = (tmp >> 1);
-
-  DecodeInt(bytes, index, &entry->source_position);
-}
-
-}  // namespace
+class IsStatementField : public BitField<bool, 0, 1> {};
+class SourcePositionField : public BitField<int, 1, 30> {};
 
 void SourcePositionTableBuilder::AddStatementPosition(size_t bytecode_offset,
                                                       int source_position) {
-  AddEntry({static_cast<int>(bytecode_offset), source_position, true});
+  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});
 }
 
 void SourcePositionTableBuilder::AddExpressionPosition(size_t bytecode_offset,
                                                        int source_position) {
-  AddEntry({static_cast<int>(bytecode_offset), source_position, false});
+  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});
 }
 
-void SourcePositionTableBuilder::AddEntry(const PositionTableEntry& entry) {
-  // Don't encode a new entry if this bytecode already has a source position
-  // assigned.
-  if (bytes_.size() > 0 && previous_.bytecode_offset == entry.bytecode_offset) {
-    return;
-  }
-
-  PositionTableEntry tmp(entry);
-  SubtractFromEntry(tmp, previous_);
-  EncodeEntry(bytes_, tmp);
-  previous_ = entry;
-
-#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();
 }
 
-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);
+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));
   }
-  DCHECK(raw == raw_entries_.end());
-#endif
-
   return table;
 }
 
-SourcePositionTableIterator::SourcePositionTableIterator(ByteArray* byte_array)
-    : table_(byte_array), index_(0), current_() {
+SourcePositionTableIterator::SourcePositionTableIterator(
+    BytecodeArray* bytecode_array)
+    : table_(bytecode_array->source_position_table()),
+      index_(0),
+      length_(table_->length()) {
+  DCHECK(table_->length() % 2 == 0);
   Advance();
 }
 
 void SourcePositionTableIterator::Advance() {
-  DCHECK(!done());
-  DCHECK(index_ >= 0 && index_ <= table_->length());
-  if (index_ == table_->length()) {
-    index_ = kDone;
-  } else {
-    PositionTableEntry tmp;
-    DecodeEntry(table_, &index_, &tmp);
-    AddAndSetEntry(current_, tmp);
+  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);
   }
+  index_ += 2;
 }
 
 }  // namespace interpreter
 }  // namespace internal
 }  // namespace v8