Uniform and precise source positions for inlining

src/source-position-table.cc

Index: src/source-position-table.cc
diff --git a/src/source-position-table.cc b/src/source-position-table.cc
index ef6d0773f9b640fd35619b2a6cf7bcac3ea5afff..bb1dc14f6184ecaf36fc867c830fe76f5a611c2d 100644
--- a/src/source-position-table.cc
+++ b/src/source-position-table.cc
@@ -47,17 +47,19 @@ void SubtractFromEntry(PositionTableEntry& value,
 }
 

[vogelheim, 2016/11/04 10:57:41]

[whole file comment, really]

I find the chosen encoding rather weird. When I initially built this, I
admittedly didn't try super hard, but I did try several variants and measured
their impact. [1]

I ended up with two length-encoded ints. You've kept that, but now with one
int32 and one int64, where the int64 is really two separately encoded ints. So
now one 'source int' goes through the length encoding and the
two-in-one-source-position-int as a whole. Does that make any sense?


How about just encoding the three ints separately? Then we can drop the template
magic, and would just call EncodeInt/DecodeInt 3 times. Does that make sense to
you? How does it affect the table size?



[1] (use chromium account:)
https://docs.google.com/spreadsheets/d/1fQLVbTF4eW7RoP1u2AUHG8LMLX65uAhAfqrly...

[Yang, 2016/11/04 14:32:59]

Well since this is delta encoded, simply calling EncodeInt 3 times would
certainly be inefficient. The delta would have to refer to the EncodeInt 3 calls
ago.

Which would probably be a lot easier to reason about and also be more efficient.

[Tobias Tebbi, 2016/11/07 15:10:34]

I tried the version with 3 encoded ints now and it leads to a 39% overhead
compared to the earlier solution with a single 64bit int. This is due to the
fact that 88% of the source positions keep the previous inlining_id.

[vogelheim, 2016/11/07 17:53:26]

Thank you! Sounds like your version is indeed better. :-)

 // Helper: Encode an integer.
-void EncodeInt(ZoneVector<byte>& bytes, int value) {
+template <typename T>
+void EncodeInt(ZoneVector<byte>& bytes, T value) {
   // Zig-zag encoding.
-  static const int kShift = kIntSize * kBitsPerByte - 1;
+  static const int kShift = sizeof(T) * kBitsPerByte - 1;
   value = ((value << 1) ^ (value >> kShift));
   DCHECK_GE(value, 0);
-  unsigned int encoded = static_cast<unsigned int>(value);
+  typename std::make_unsigned<T>::type encoded{value};
   bool more;
   do {
     more = encoded > ValueBits::kMax;
-    bytes.push_back(MoreBit::encode(more) |
-                    ValueBits::encode(encoded & ValueBits::kMask));
+    byte current =
+        MoreBit::encode(more) | ValueBits::encode(encoded & ValueBits::kMask);
+    bytes.push_back(current);
     encoded >>= ValueBits::kSize;
   } while (more);
 }
@@ -67,31 +69,33 @@ void EncodeEntry(ZoneVector<byte>& bytes, const PositionTableEntry& entry) {
   // We only accept ascending code offsets.
   DCHECK(entry.code_offset >= 0);
   // Since code_offset is not negative, we use sign to encode is_statement.
-  EncodeInt(bytes,
-            entry.is_statement ? entry.code_offset : -entry.code_offset - 1);
-  EncodeInt(bytes, entry.source_position);
+  EncodeInt<int>(
+      bytes, entry.is_statement ? entry.code_offset : -entry.code_offset - 1);
+  EncodeInt<int64_t>(bytes, entry.source_position);
 }
 
 // Helper: Decode an integer.
-void DecodeInt(ByteArray* bytes, int* index, int* v) {
+template <typename T>
+T DecodeInt(ByteArray* bytes, int* index) {
   byte current;
   int shift = 0;
-  int decoded = 0;
+  T decoded = 0;
   bool more;
   do {
     current = bytes->get((*index)++);
-    decoded |= ValueBits::decode(current) << shift;
+    decoded |= static_cast<typename std::make_unsigned<T>::type>(
+                   ValueBits::decode(current))
+               << shift;
     more = MoreBit::decode(current);
     shift += ValueBits::kSize;
   } while (more);
   DCHECK_GE(decoded, 0);
   decoded = (decoded >> 1) ^ (-(decoded & 1));
-  *v = decoded;
+  return decoded;
 }
 
 void DecodeEntry(ByteArray* bytes, int* index, PositionTableEntry* entry) {
-  int tmp;
-  DecodeInt(bytes, index, &tmp);
+  int tmp = DecodeInt<int>(bytes, index);
   if (tmp >= 0) {
     entry->is_statement = true;
     entry->code_offset = tmp;
@@ -99,7 +103,7 @@ void DecodeEntry(ByteArray* bytes, int* index, PositionTableEntry* entry) {
     entry->is_statement = false;
     entry->code_offset = -(tmp + 1);
   }
-  DecodeInt(bytes, index, &entry->source_position);
+  entry->source_position = DecodeInt<int64_t>(bytes, index);
 }
 
 }  // namespace
@@ -115,11 +119,12 @@ SourcePositionTableBuilder::SourcePositionTableBuilder(
 }
 
 void SourcePositionTableBuilder::AddPosition(size_t code_offset,
-                                             int source_position,
+                                             SourcePosition source_position,
                                              bool is_statement) {
   if (Omit()) return;
+  DCHECK(source_position.IsKnown());
   int offset = static_cast<int>(code_offset);
-  AddEntry({offset, source_position, is_statement});
+  AddEntry({offset, source_position.raw(), is_statement});
 }
 
 void SourcePositionTableBuilder::AddEntry(const PositionTableEntry& entry) {
@@ -152,7 +157,7 @@ Handle<ByteArray> SourcePositionTableBuilder::ToSourcePositionTable(
        encoded.Advance(), raw++) {
     DCHECK(raw != raw_entries_.end());
     DCHECK_EQ(encoded.code_offset(), raw->code_offset);
-    DCHECK_EQ(encoded.source_position(), raw->source_position);
+    DCHECK_EQ(encoded.source_position().raw(), raw->source_position);
     DCHECK_EQ(encoded.is_statement(), raw->is_statement);
   }
   DCHECK(raw == raw_entries_.end());