RFC: Switch to ast ids (instead of positions) for type feedback.

src/assembler.cc

 // Copyright (c) 1994-2006 Sun Microsystems Inc.
 // All Rights Reserved.
 //
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 // - Redistributions of source code must retain the above copyright notice,
 // this list of conditions and the following disclaimer.
 //
@@ skipping 71 matching lines @@
 
 // -----------------------------------------------------------------------------
 // Implementation of RelocInfoWriter and RelocIterator
 //
 // Encoding
 //
 // The most common modes are given single-byte encodings.  Also, it is
 // easy to identify the type of reloc info and skip unwanted modes in
 // an iteration.
 //
 // The encoding relies on the fact that there are less than 14

[fschneider, 2011/02/11 11:28:18]

I'm confused by this comment in the existing code since the ASSERT below says <=
14 

 // different relocation modes.
 //
 // embedded_object:    [6 bits pc delta] 00
 //
 // code_taget:         [6 bits pc delta] 01

[fschneider, 2011/02/11 11:28:18]

--> code_target

 //
+// code_taget_with_id: [6 bits pc delta] 10,

[fschneider, 2011/02/11 11:28:18]

--> code_target

+//                     [6 bits signed data delta] 00
+//
 // position:           [6 bits pc delta] 10,
-//                     [7 bits signed data delta] 0
+//                     [6 bits signed data delta] 01
 //
 // statement_position: [6 bits pc delta] 10,
-//                     [7 bits signed data delta] 1
+//                     [6 bits signed data delta] 10
 //
 // any nondata mode:   00 [4 bits rmode] 11,  // rmode: 0..13 only
 //                     00 [6 bits pc delta]
 //
 // pc-jump:            00 1111 11,
 //                     00 [6 bits pc delta]
 //
 // pc-jump:            01 1111 11,
 // (variable length)   7 - 26 bit pc delta, written in chunks of 7
 //                     bits, the lowest 7 bits written first.
 //
-// data-jump + pos:    00 1110 11,
+// data-jump + c.id:   00 1110 11,
 //                     signed intptr_t, lowest byte written first
 //
-// data-jump + st.pos: 01 1110 11,
+// data-jump + pos:    01 1110 11,
 //                     signed intptr_t, lowest byte written first
 //
-// data-jump + comm.:  10 1110 11,
+// data-jump + st.pos: 10 1110 11,
+//                     signed intptr_t, lowest byte written first
+//
+// data-jump + comm.:  11 1110 11,
 //                     signed intptr_t, lowest byte written first
 //
 const int kMaxRelocModes = 14;
 
 const int kTagBits = 2;
 const int kTagMask = (1 << kTagBits) - 1;
 const int kExtraTagBits = 4;
-const int kPositionTypeTagBits = 1;
-const int kSmallDataBits = kBitsPerByte - kPositionTypeTagBits;
+const int kLocatableTypeTagBits = 2;
+const int kSmallDataBits = kBitsPerByte - kLocatableTypeTagBits;
 
 const int kEmbeddedObjectTag = 0;
 const int kCodeTargetTag = 1;
-const int kPositionTag = 2;
+const int kLocatableTag = 2;
 const int kDefaultTag = 3;
 
 const int kPCJumpTag = (1 << kExtraTagBits) - 1;
 
 const int kSmallPCDeltaBits = kBitsPerByte - kTagBits;
 const int kSmallPCDeltaMask = (1 << kSmallPCDeltaBits) - 1;
 
 const int kVariableLengthPCJumpTopTag = 1;
 const int kChunkBits = 7;
 const int kChunkMask = (1 << kChunkBits) - 1;
 const int kLastChunkTagBits = 1;
 const int kLastChunkTagMask = 1;
 const int kLastChunkTag = 1;
 
 
 const int kDataJumpTag = kPCJumpTag - 1;
 
-const int kNonstatementPositionTag = 0;
-const int kStatementPositionTag = 1;
-const int kCommentTag = 2;
+const int kCodeWithIdTag = 0;
+const int kNonstatementPositionTag = 1;
+const int kStatementPositionTag = 2;
+const int kCommentTag = 3;
 
 
 uint32_t RelocInfoWriter::WriteVariableLengthPCJump(uint32_t pc_delta) {
   // Return if the pc_delta can fit in kSmallPCDeltaBits bits.
   // Otherwise write a variable length PC jump for the bits that do
   // not fit in the kSmallPCDeltaBits bits.
   if (is_uintn(pc_delta, kSmallPCDeltaBits)) return pc_delta;
   WriteExtraTag(kPCJumpTag, kVariableLengthPCJumpTopTag);
   uint32_t pc_jump = pc_delta >> kSmallPCDeltaBits;
   ASSERT(pc_jump > 0);
@@ skipping 10 matching lines @@
 
 
 void RelocInfoWriter::WriteTaggedPC(uint32_t pc_delta, int tag) {
   // Write a byte of tagged pc-delta, possibly preceded by var. length pc-jump.
   pc_delta = WriteVariableLengthPCJump(pc_delta);
   *--pos_ = pc_delta << kTagBits | tag;
 }
 
 
 void RelocInfoWriter::WriteTaggedData(intptr_t data_delta, int tag) {
-  *--pos_ = static_cast<byte>(data_delta << kPositionTypeTagBits | tag);
+  *--pos_ = static_cast<byte>(data_delta << kLocatableTypeTagBits | tag);
 }
 
 
 void RelocInfoWriter::WriteExtraTag(int extra_tag, int top_tag) {
   *--pos_ = static_cast<int>(top_tag << (kTagBits + kExtraTagBits) |
                              extra_tag << kTagBits |
                              kDefaultTag);
 }
 
 
 void RelocInfoWriter::WriteExtraTaggedPC(uint32_t pc_delta, int extra_tag) {
   // Write two-byte tagged pc-delta, possibly preceded by var. length pc-jump.
   pc_delta = WriteVariableLengthPCJump(pc_delta);
   WriteExtraTag(extra_tag, 0);
   *--pos_ = pc_delta;
 }
 
 
+void RelocInfoWriter::WriteExtraTaggedIntData(int data_delta, int top_tag) {
+  WriteExtraTag(kDataJumpTag, top_tag);
+  for (int i = 0; i < kIntSize; i++) {
+    *--pos_ = static_cast<byte>(data_delta);
+    // Signed right shift is arithmetic shift.  Tested in test-utils.cc.
+    data_delta = data_delta >> kBitsPerByte;
+  }
+}
+
+
 void RelocInfoWriter::WriteExtraTaggedData(intptr_t data_delta, int top_tag) {
   WriteExtraTag(kDataJumpTag, top_tag);
   for (int i = 0; i < kIntptrSize; i++) {
     *--pos_ = static_cast<byte>(data_delta);
-  // Signed right shift is arithmetic shift.  Tested in test-utils.cc.
+    // Signed right shift is arithmetic shift.  Tested in test-utils.cc.
     data_delta = data_delta >> kBitsPerByte;
   }
 }
 
 
 void RelocInfoWriter::Write(const RelocInfo* rinfo) {
 #ifdef DEBUG
   byte* begin_pos = pos_;
 #endif
   Counters::reloc_info_count.Increment();
   ASSERT(rinfo->pc() - last_pc_ >= 0);
-  ASSERT(RelocInfo::NUMBER_OF_MODES <= kMaxRelocModes);
+  ASSERT(RelocInfo::NUMBER_OF_MODES - RelocInfo::LAST_CODE_ENUM <=
+         kMaxRelocModes);
   // Use unsigned delta-encoding for pc.
   uint32_t pc_delta = static_cast<uint32_t>(rinfo->pc() - last_pc_);
   RelocInfo::Mode rmode = rinfo->rmode();
 
   // The two most common modes are given small tags, and usually fit in a byte.
   if (rmode == RelocInfo::EMBEDDED_OBJECT) {
     WriteTaggedPC(pc_delta, kEmbeddedObjectTag);
   } else if (rmode == RelocInfo::CODE_TARGET) {
     WriteTaggedPC(pc_delta, kCodeTargetTag);
-  } else if (RelocInfo::IsPosition(rmode)) {
-    // Use signed delta-encoding for data.
-    intptr_t data_delta = rinfo->data() - last_data_;
-    int pos_type_tag = rmode == RelocInfo::POSITION ? kNonstatementPositionTag
-                                                    : kStatementPositionTag;
-    // Check if data is small enough to fit in a tagged byte.
-    // We cannot use is_intn because data_delta is not an int32_t.
-    if (data_delta >= -(1 << (kSmallDataBits-1)) &&
-        data_delta < 1 << (kSmallDataBits-1)) {
-      WriteTaggedPC(pc_delta, kPositionTag);
-      WriteTaggedData(data_delta, pos_type_tag);
-      last_data_ = rinfo->data();
+  } else if (rmode == RelocInfo::CODE_TARGET_WITH_ID) {
+    // Use signed delta-encoding for id.
+    ASSERT(static_cast<int>(rinfo->data()) == rinfo->data());
+    int id_delta = static_cast<int>(rinfo->data()) - last_id_;
+    // Check if delta is small enough to fit in a tagged byte.
+    if (is_intn(id_delta, kSmallDataBits)) {
+      WriteTaggedPC(pc_delta, kLocatableTag);
+      WriteTaggedData(id_delta, kCodeWithIdTag);
     } else {
       // Otherwise, use costly encoding.
       WriteExtraTaggedPC(pc_delta, kPCJumpTag);
-      WriteExtraTaggedData(data_delta, pos_type_tag);
-      last_data_ = rinfo->data();
+      WriteExtraTaggedIntData(id_delta, kCodeWithIdTag);
     }
+    last_id_ = static_cast<int>(rinfo->data());
+  } else if (RelocInfo::IsPosition(rmode)) {
+    // Use signed delta-encoding for position.
+    ASSERT(static_cast<int>(rinfo->data()) == rinfo->data());
+    int pos_delta = static_cast<int>(rinfo->data()) - last_position_;
+    int pos_type_tag = (rmode == RelocInfo::POSITION) ? kNonstatementPositionTag
+                                                      : kStatementPositionTag;
+    // Check if delta is small enough to fit in a tagged byte.
+    if (is_intn(pos_delta, kSmallDataBits)) {
+      WriteTaggedPC(pc_delta, kLocatableTag);
+      WriteTaggedData(pos_delta, pos_type_tag);
+    } else {
+      // Otherwise, use costly encoding.
+      WriteExtraTaggedPC(pc_delta, kPCJumpTag);
+      WriteExtraTaggedIntData(pos_delta, pos_type_tag);
+    }
+    last_position_ = static_cast<int>(rinfo->data());
   } else if (RelocInfo::IsComment(rmode)) {
     // Comments are normally not generated, so we use the costly encoding.
     WriteExtraTaggedPC(pc_delta, kPCJumpTag);
-    WriteExtraTaggedData(rinfo->data() - last_data_, kCommentTag);
-    last_data_ = rinfo->data();
+    WriteExtraTaggedData(rinfo->data(), kCommentTag);
   } else {
+    ASSERT(rmode > RelocInfo::LAST_COMPACT_ENUM);
+    int saved_mode = rmode - RelocInfo::LAST_COMPACT_ENUM;
     // For all other modes we simply use the mode as the extra tag.
     // None of these modes need a data component.
-    ASSERT(rmode < kPCJumpTag && rmode < kDataJumpTag);
-    WriteExtraTaggedPC(pc_delta, rmode);
+    ASSERT(saved_mode < kPCJumpTag && saved_mode < kDataJumpTag);
+    WriteExtraTaggedPC(pc_delta, saved_mode);
   }
   last_pc_ = rinfo->pc();
 #ifdef DEBUG
   ASSERT(begin_pos - pos_ <= kMaxSize);
 #endif
 }
 
 
 inline int RelocIterator::AdvanceGetTag() {
   return *--pos_ & kTagMask;
@@ skipping 13 matching lines @@
 inline void RelocIterator::ReadTaggedPC() {
   rinfo_.pc_ += *pos_ >> kTagBits;
 }
 
 
 inline void RelocIterator::AdvanceReadPC() {
   rinfo_.pc_ += *--pos_;
 }
 
 
+void RelocIterator::AdvanceReadId() {
+  int x = 0;
+  for (int i = 0; i < kIntSize; i++) {
+    x |= static_cast<int>(*--pos_) << i * kBitsPerByte;
+  }
+  last_id_ += x;
+  rinfo_.data_ = last_id_;
+}
+
+
+void RelocIterator::AdvanceReadPosition() {
+  int x = 0;
+  for (int i = 0; i < kIntSize; i++) {
+    x |= static_cast<int>(*--pos_) << i * kBitsPerByte;
+  }
+  last_position_ += x;
+  rinfo_.data_ = last_position_;
+}
+
+
 void RelocIterator::AdvanceReadData() {
   intptr_t x = 0;
   for (int i = 0; i < kIntptrSize; i++) {
     x |= static_cast<intptr_t>(*--pos_) << i * kBitsPerByte;
   }
-  rinfo_.data_ += x;
+  rinfo_.data_ = x;
 }
 
 
 void RelocIterator::AdvanceReadVariableLengthPCJump() {
   // Read the 32-kSmallPCDeltaBits most significant bits of the
   // pc jump in kChunkBits bit chunks and shift them into place.
   // Stop when the last chunk is encountered.
   uint32_t pc_jump = 0;
   for (int i = 0; i < kIntSize; i++) {
     byte pc_jump_part = *--pos_;
     pc_jump |= (pc_jump_part >> kLastChunkTagBits) << i * kChunkBits;
     if ((pc_jump_part & kLastChunkTagMask) == 1) break;
   }
   // The least significant kSmallPCDeltaBits bits will be added
   // later.
   rinfo_.pc_ += pc_jump << kSmallPCDeltaBits;
 }
 
 
-inline int RelocIterator::GetPositionTypeTag() {
-  return *pos_ & ((1 << kPositionTypeTagBits) - 1);
+inline int RelocIterator::GetLocatableTypeTag() {
+  return *pos_ & ((1 << kLocatableTypeTagBits) - 1);
 }
 
 
-inline void RelocIterator::ReadTaggedData() {
+inline void RelocIterator::ReadTaggedId() {
   int8_t signed_b = *pos_;
   // Signed right shift is arithmetic shift.  Tested in test-utils.cc.
-  rinfo_.data_ += signed_b >> kPositionTypeTagBits;
+  last_id_ += signed_b >> kLocatableTypeTagBits;
+  rinfo_.data_ = last_id_;
 }
 
 
-inline RelocInfo::Mode RelocIterator::DebugInfoModeFromTag(int tag) {
-  if (tag == kStatementPositionTag) {
-    return RelocInfo::STATEMENT_POSITION;
-  } else if (tag == kNonstatementPositionTag) {
-    return RelocInfo::POSITION;
-  } else {
-    ASSERT(tag == kCommentTag);
-    return RelocInfo::COMMENT;
-  }
+inline void RelocIterator::ReadTaggedPosition() {
+  int8_t signed_b = *pos_;
+  // Signed right shift is arithmetic shift.  Tested in test-utils.cc.
+  last_position_ += signed_b >> kLocatableTypeTagBits;
+  rinfo_.data_ = last_position_;
 }
 
 
+static inline RelocInfo::Mode GetPositionModeFromTag(int tag) {
+  ASSERT(tag == kNonstatementPositionTag ||
+         tag == kStatementPositionTag);
+  return (tag == kNonstatementPositionTag)
+      ? RelocInfo::POSITION : RelocInfo::STATEMENT_POSITION;
+}
+
+
 void RelocIterator::next() {
   ASSERT(!done());
   // Basically, do the opposite of RelocInfoWriter::Write.
   // Reading of data is as far as possible avoided for unwanted modes,
   // but we must always update the pc.
   //
   // We exit this loop by returning when we find a mode we want.
   while (pos_ > end_) {
     int tag = AdvanceGetTag();
     if (tag == kEmbeddedObjectTag) {
       ReadTaggedPC();
       if (SetMode(RelocInfo::EMBEDDED_OBJECT)) return;
     } else if (tag == kCodeTargetTag) {
       ReadTaggedPC();
       if (SetMode(RelocInfo::CODE_TARGET)) return;
-    } else if (tag == kPositionTag) {
+    } else if (tag == kLocatableTag) {
       ReadTaggedPC();
       Advance();
-      // Check if we want source positions.
-      if (mode_mask_ & RelocInfo::kPositionMask) {
-        ReadTaggedData();
-        if (SetMode(DebugInfoModeFromTag(GetPositionTypeTag()))) return;
+      int locatable_tag = GetLocatableTypeTag();
+      if (locatable_tag == kCodeWithIdTag) {
+        if (SetMode(RelocInfo::CODE_TARGET_WITH_ID)) {
+          ReadTaggedId();
+          return;
+        }
+      } else {
+        // Compact encoding is never used for comments,
+        // so it must be a position.
+        ASSERT(locatable_tag == kNonstatementPositionTag ||
+               locatable_tag == kStatementPositionTag);
+        if (mode_mask_ & RelocInfo::kPositionMask) {
+          ReadTaggedPosition();
+          if (SetMode(GetPositionModeFromTag(locatable_tag))) return;
+        }
       }
     } else {
       ASSERT(tag == kDefaultTag);
       int extra_tag = GetExtraTag();
       if (extra_tag == kPCJumpTag) {
         int top_tag = GetTopTag();
         if (top_tag == kVariableLengthPCJumpTopTag) {
           AdvanceReadVariableLengthPCJump();
         } else {
           AdvanceReadPC();
         }
       } else if (extra_tag == kDataJumpTag) {
-        // Check if we want debug modes (the only ones with data).
-        if (mode_mask_ & RelocInfo::kDebugMask) {
-          int top_tag = GetTopTag();
-          AdvanceReadData();
-          if (SetMode(DebugInfoModeFromTag(top_tag))) return;
+        int locatable_tag = GetTopTag();
+        if (locatable_tag == kCodeWithIdTag) {
+          if (SetMode(RelocInfo::CODE_TARGET_WITH_ID)) {
+            AdvanceReadId();
+            return;
+          }
+          Advance(kIntSize);
+        } else if (locatable_tag != kCommentTag) {
+          ASSERT(locatable_tag == kNonstatementPositionTag ||
+                 locatable_tag == kStatementPositionTag);
+          if (mode_mask_ & RelocInfo::kPositionMask) {
+            AdvanceReadPosition();
+            if (SetMode(GetPositionModeFromTag(locatable_tag))) return;
+          } else {
+            Advance(kIntSize);
+          }
         } else {
-          // Otherwise, just skip over the data.
+          ASSERT(locatable_tag == kCommentTag);
+          if (SetMode(RelocInfo::COMMENT)) {
+            AdvanceReadData();
+            return;
+          }
           Advance(kIntptrSize);
         }
       } else {
         AdvanceReadPC();
-        if (SetMode(static_cast<RelocInfo::Mode>(extra_tag))) return;
+        int rmode = extra_tag + RelocInfo::LAST_COMPACT_ENUM;
+        if (SetMode(static_cast<RelocInfo::Mode>(rmode))) return;
       }
     }
   }
   done_ = true;
 }
 
 
 RelocIterator::RelocIterator(Code* code, int mode_mask) {
   rinfo_.pc_ = code->instruction_start();
   rinfo_.data_ = 0;
   // Relocation info is read backwards.
   pos_ = code->relocation_start() + code->relocation_size();
   end_ = code->relocation_start();
   done_ = false;
   mode_mask_ = mode_mask;
+  last_id_ = 0;
+  last_position_ = 0;
   if (mode_mask_ == 0) pos_ = end_;
   next();
 }
 
 
 RelocIterator::RelocIterator(const CodeDesc& desc, int mode_mask) {
   rinfo_.pc_ = desc.buffer;
   rinfo_.data_ = 0;
   // Relocation info is read backwards.
   pos_ = desc.buffer + desc.buffer_size;
   end_ = pos_ - desc.reloc_size;
   done_ = false;
   mode_mask_ = mode_mask;
+  last_id_ = 0;
+  last_position_ = 0;
   if (mode_mask_ == 0) pos_ = end_;
   next();
 }
 
 
 // -----------------------------------------------------------------------------
 // Implementation of RelocInfo
 
 
 #ifdef ENABLE_DISASSEMBLER
 const char* RelocInfo::RelocModeName(RelocInfo::Mode rmode) {
   switch (rmode) {
     case RelocInfo::NONE:
       return "no reloc";
     case RelocInfo::EMBEDDED_OBJECT:
       return "embedded object";
     case RelocInfo::CONSTRUCT_CALL:
       return "code target (js construct call)";
     case RelocInfo::CODE_TARGET_CONTEXT:
       return "code target (context)";
     case RelocInfo::DEBUG_BREAK:
 #ifndef ENABLE_DEBUGGER_SUPPORT
       UNREACHABLE();
 #endif
       return "debug break";
     case RelocInfo::CODE_TARGET:
       return "code target";
+    case RelocInfo::CODE_TARGET_WITH_ID:
+      return "code target with id";
     case RelocInfo::GLOBAL_PROPERTY_CELL:
       return "global property cell";
     case RelocInfo::RUNTIME_ENTRY:
       return "runtime entry";
     case RelocInfo::JS_RETURN:
       return "js return";
     case RelocInfo::COMMENT:
       return "comment";
     case RelocInfo::POSITION:
       return "position";
@@ skipping 25 matching lines @@
     target_object()->ShortPrint();
     PrintF(")");
   } else if (rmode_ == EXTERNAL_REFERENCE) {
     ExternalReferenceEncoder ref_encoder;
     PrintF(" (%s)  (%p)",
            ref_encoder.NameOfAddress(*target_reference_address()),
            *target_reference_address());
   } else if (IsCodeTarget(rmode_)) {
     Code* code = Code::GetCodeFromTargetAddress(target_address());
     PrintF(" (%s)  (%p)", Code::Kind2String(code->kind()), target_address());
+    if (rmode_ == CODE_TARGET_WITH_ID) {
+      PrintF(" (id=%d)", static_cast<int>(data_));
+    }
   } else if (IsPosition(rmode_)) {
     PrintF("  (%" V8_PTR_PREFIX "d)", data());
   } else if (rmode_ == RelocInfo::RUNTIME_ENTRY) {
     // Depotimization bailouts are stored as runtime entries.
     int id = Deoptimizer::GetDeoptimizationId(
         target_address(), Deoptimizer::EAGER);
     if (id != Deoptimizer::kNotDeoptimizationEntry) {
       PrintF("  (deoptimization bailout %d)", id);
     }
   }
@@ skipping 12 matching lines @@
     case GLOBAL_PROPERTY_CELL:
       Object::VerifyPointer(target_cell());
       break;
     case DEBUG_BREAK:
 #ifndef ENABLE_DEBUGGER_SUPPORT
       UNREACHABLE();
       break;
 #endif
     case CONSTRUCT_CALL:
     case CODE_TARGET_CONTEXT:
+    case CODE_TARGET_WITH_ID:
     case CODE_TARGET: {
       // convert inline target address to code object
       Address addr = target_address();
       ASSERT(addr != NULL);
       // Check that we can find the right code object.
       Code* code = Code::GetCodeFromTargetAddress(addr);
       Object* found = Heap::FindCodeObject(addr);
       ASSERT(found->IsCode());
       ASSERT(code->address() == HeapObject::cast(found)->address());
       break;
@@ skipping 407 matching lines @@
     assembler_->RecordRelocInfo(RelocInfo::POSITION, state_.current_position);
     state_.written_position = state_.current_position;
     written = true;
   }
 
   // Return whether something was written.
   return written;
 }
 
 } }  // namespace v8::internal