Compress deopt instructions in memory using variable length encoding.

runtime/vm/object.cc

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/object.h"
 
 #include "include/dart_api.h"
 #include "platform/assert.h"
 #include "vm/assembler.h"
 #include "vm/cpu.h"
@@ skipping 124 matching lines @@
 RawClass* Object::library_class_ = reinterpret_cast<RawClass*>(RAW_NULL);
 RawClass* Object::namespace_class_ = reinterpret_cast<RawClass*>(RAW_NULL);
 RawClass* Object::code_class_ = reinterpret_cast<RawClass*>(RAW_NULL);
 RawClass* Object::instructions_class_ = reinterpret_cast<RawClass*>(RAW_NULL);
 RawClass* Object::pc_descriptors_class_ = reinterpret_cast<RawClass*>(RAW_NULL);
 RawClass* Object::stackmap_class_ = reinterpret_cast<RawClass*>(RAW_NULL);
 RawClass* Object::var_descriptors_class_ =
     reinterpret_cast<RawClass*>(RAW_NULL);
 RawClass* Object::exception_handlers_class_ =
     reinterpret_cast<RawClass*>(RAW_NULL);
-RawClass* Object::deopt_info_class_ = reinterpret_cast<RawClass*>(RAW_NULL);
 RawClass* Object::context_class_ = reinterpret_cast<RawClass*>(RAW_NULL);
 RawClass* Object::context_scope_class_ = reinterpret_cast<RawClass*>(RAW_NULL);
 RawClass* Object::icdata_class_ = reinterpret_cast<RawClass*>(RAW_NULL);
 RawClass* Object::megamorphic_cache_class_ =
     reinterpret_cast<RawClass*>(RAW_NULL);
 RawClass* Object::subtypetestcache_class_ =
     reinterpret_cast<RawClass*>(RAW_NULL);
 RawClass* Object::api_error_class_ = reinterpret_cast<RawClass*>(RAW_NULL);
 RawClass* Object::language_error_class_ = reinterpret_cast<RawClass*>(RAW_NULL);
 RawClass* Object::unhandled_exception_class_ =
@@ skipping 396 matching lines @@
 
   cls = Class::New<Stackmap>();
   stackmap_class_ = cls.raw();
 
   cls = Class::New<LocalVarDescriptors>();
   var_descriptors_class_ = cls.raw();
 
   cls = Class::New<ExceptionHandlers>();
   exception_handlers_class_ = cls.raw();
 
-  cls = Class::New<DeoptInfo>();
-  deopt_info_class_ = cls.raw();
-
   cls = Class::New<Context>();
   context_class_ = cls.raw();
 
   cls = Class::New<ContextScope>();
   context_scope_class_ = cls.raw();
 
   cls = Class::New<ICData>();
   icdata_class_ = cls.raw();
 
   cls = Class::New<MegamorphicCache>();
@@ skipping 234 matching lines @@
   SET_CLASS_NAME(token_stream, TokenStream);
   SET_CLASS_NAME(script, Script);
   SET_CLASS_NAME(library, LibraryClass);
   SET_CLASS_NAME(namespace, Namespace);
   SET_CLASS_NAME(code, Code);
   SET_CLASS_NAME(instructions, Instructions);
   SET_CLASS_NAME(pc_descriptors, PcDescriptors);
   SET_CLASS_NAME(stackmap, Stackmap);
   SET_CLASS_NAME(var_descriptors, LocalVarDescriptors);
   SET_CLASS_NAME(exception_handlers, ExceptionHandlers);
-  SET_CLASS_NAME(deopt_info, DeoptInfo);
   SET_CLASS_NAME(context, Context);
   SET_CLASS_NAME(context_scope, ContextScope);
   SET_CLASS_NAME(icdata, ICData);
   SET_CLASS_NAME(megamorphic_cache, MegamorphicCache);
   SET_CLASS_NAME(subtypetestcache, SubtypeTestCache);
   SET_CLASS_NAME(api_error, ApiError);
   SET_CLASS_NAME(language_error, LanguageError);
   SET_CLASS_NAME(unhandled_exception, UnhandledException);
   SET_CLASS_NAME(unwind_error, UnwindError);
 
@@ skipping 2372 matching lines @@
     case kInstructionsCid:
       return Symbols::Instructions().raw();
     case kPcDescriptorsCid:
       return Symbols::PcDescriptors().raw();
     case kStackmapCid:
       return Symbols::Stackmap().raw();
     case kLocalVarDescriptorsCid:
       return Symbols::LocalVarDescriptors().raw();
     case kExceptionHandlersCid:
       return Symbols::ExceptionHandlers().raw();
-    case kDeoptInfoCid:
-      return Symbols::DeoptInfo().raw();
     case kContextCid:
       return Symbols::Context().raw();
     case kContextScopeCid:
       return Symbols::ContextScope().raw();
     case kICDataCid:
       return Symbols::ICData().raw();
     case kMegamorphicCacheCid:
       return Symbols::MegamorphicCache().raw();
     case kSubtypeTestCacheCid:
       return Symbols::SubtypeTestCache().raw();
@@ skipping 7909 matching lines @@
   return buffer;
 }
 
 
 void ExceptionHandlers::PrintJSONImpl(JSONStream* stream,
                                       bool ref) const {
   Object::PrintJSONImpl(stream, ref);
 }
 
 
-intptr_t DeoptInfo::Length() const {
-  return Smi::Value(raw_ptr()->length_);
+intptr_t DeoptInfo::FrameSize(const TypedData& packed) {
+  NoSafepointScope no_safepoint;
+  typedef ReadStream::Raw<sizeof(intptr_t), intptr_t> Reader;
+  ReadStream read_stream(reinterpret_cast<uint8_t*>(packed.DataAddr(0)),
+                         packed.LengthInBytes());
+  return Reader::Read(&read_stream);
 }
 
 
-intptr_t DeoptInfo::FromIndex(intptr_t index) const {
-  NoSafepointScope no_safepoint;
-  return *(EntryAddr(index, kFromIndex));
+intptr_t DeoptInfo::NumMaterializations(
+    const GrowableArray<DeoptInstr*>& unpacked) {
+  intptr_t num = 0;
+  while (unpacked[num]->kind() == DeoptInstr::kMaterializeObject) {
+    num++;
+  }
+  return num;
 }
 
 
-intptr_t DeoptInfo::Instruction(intptr_t index) const {
+void DeoptInfo::UnpackInto(const Array& table,
+                           const TypedData& packed,
+                           GrowableArray<DeoptInstr*>* unpacked,
+                           intptr_t length) {
   NoSafepointScope no_safepoint;
-  return *(EntryAddr(index, kInstruction));
-}
+  typedef ReadStream::Raw<sizeof(intptr_t), intptr_t> Reader;
+  ReadStream read_stream(reinterpret_cast<uint8_t*>(packed.DataAddr(0)),
+                         packed.LengthInBytes());
+  const intptr_t frame_size = Reader::Read(&read_stream);  // Skip frame size.
+  USE(frame_size);
 
+  const intptr_t suffix_length = Reader::Read(&read_stream);
+  if (suffix_length != 0) {
+    ASSERT(suffix_length > 1);
+    const intptr_t info_number = Reader::Read(&read_stream);
 
-intptr_t DeoptInfo::FrameSize() const {
-  return TranslationLength() - NumMaterializations();
-}
+    TypedData& suffix = TypedData::Handle();
+    Smi& offset = Smi::Handle();
+    Smi& reason_and_flags = Smi::Handle();
+    DeoptTable::GetEntry(
+      table, info_number, &offset, &suffix, &reason_and_flags);
+    UnpackInto(table, suffix, unpacked, suffix_length);
+  }
 
-
-intptr_t DeoptInfo::TranslationLength() const {
-  intptr_t length = Length();
-  if (Instruction(length - 1) != DeoptInstr::kSuffix) return length;
-
-  // If the last command is a suffix, add in the length of the suffix and
-  // do not count the suffix command as a translation command.
-  intptr_t ignored = 0;
-  intptr_t suffix_length =
-      DeoptInstr::DecodeSuffix(FromIndex(length - 1), &ignored);
-  return length + suffix_length - 1;
-}
-
-
-intptr_t DeoptInfo::NumMaterializations() const {
-  intptr_t pos = 0;
-  while (Instruction(pos) == DeoptInstr::kMaterializeObject) {
-    pos++;
-  }
-  return pos;
-}
-
-
-void DeoptInfo::ToInstructions(const Array& table,
-                               GrowableArray<DeoptInstr*>* instructions) const {
-  ASSERT(instructions->is_empty());
-  Smi& offset = Smi::Handle();
-  DeoptInfo& info = DeoptInfo::Handle(raw());
-  Smi& reason_and_flags = Smi::Handle();
-  intptr_t index = 0;
-  intptr_t length = TranslationLength();
-  while (index < length) {
-    intptr_t instruction = info.Instruction(index);
-    intptr_t from_index = info.FromIndex(index);
-    if (instruction == DeoptInstr::kSuffix) {
-      // Suffix instructions cause us to 'jump' to another translation,
-      // changing info, length and index.
-      intptr_t info_number = 0;
-      intptr_t suffix_length =
-          DeoptInstr::DecodeSuffix(from_index, &info_number);
-      DeoptTable::GetEntry(
-          table, info_number, &offset, &info, &reason_and_flags);
-      length = info.TranslationLength();
-      index = length - suffix_length;
-    } else {
-      instructions->Add(DeoptInstr::Create(instruction, from_index));
-      ++index;
-    }
+  while ((read_stream.PendingBytes() > 0) &&
+         (unpacked->length() < length)) {
+    const intptr_t instruction = Reader::Read(&read_stream);
+    const intptr_t from_index = Reader::Read(&read_stream);
+    unpacked->Add(DeoptInstr::Create(instruction, from_index));
   }
 }
 
 
-const char* DeoptInfo::ToCString() const {
-  if (Length() == 0) {
-    return "No DeoptInfo";
+void DeoptInfo::Unpack(const Array& table,
+                       const TypedData& packed,
+                       GrowableArray<DeoptInstr*>* unpacked) {
+  ASSERT(unpacked->is_empty());
+  UnpackInto(table, packed, unpacked, kMaxInt32);

[Ivan Posva, 2015/04/08 07:12:13]

It is not really obvious why kMaxInt32 is being passed here. Please add a
comment that we don't need a limit here as we want to get the whole stream and
not just a suffix.

[Vyacheslav Egorov (Google), 2015/04/08 13:07:39]

Done.

+
+  const intptr_t length = unpacked->length();

[Florian Schneider, 2015/04/08 08:50:04]

Add a reverse method to GrowableArray?

[Vyacheslav Egorov (Google), 2015/04/08 13:07:39]

Done.

+  for (intptr_t i = 0; i < length / 2; i++) {
+    intptr_t j = length - 1 - i;
+    DeoptInstr* temp = (*unpacked)[i];
+    (*unpacked)[i] = (*unpacked)[j];
+    (*unpacked)[j] = temp;
   }
-  // Convert to DeoptInstr.
-  GrowableArray<DeoptInstr*> deopt_instrs(Length());
-  for (intptr_t i = 0; i < Length(); i++) {
-    deopt_instrs.Add(DeoptInstr::Create(Instruction(i), FromIndex(i)));
-  }
+}
+
+
+const char* DeoptInfo::ToCString(const Array& deopt_table,
+                                 const TypedData& packed) {
+  GrowableArray<DeoptInstr*> deopt_instrs;
+  Unpack(deopt_table, packed, &deopt_instrs);
+
   // Compute the buffer size required.
   intptr_t len = 1;  // Trailing '\0'.
-  for (intptr_t i = 0; i < Length(); i++) {
+  for (intptr_t i = 0; i < deopt_instrs.length(); i++) {
     len += OS::SNPrint(NULL, 0, "[%s]", deopt_instrs[i]->ToCString());
   }
+
   // Allocate the buffer.
   char* buffer = Isolate::Current()->current_zone()->Alloc<char>(len);
+
   // Layout the fields in the buffer.
   intptr_t index = 0;
-  for (intptr_t i = 0; i < Length(); i++) {
+  for (intptr_t i = 0; i < deopt_instrs.length(); i++) {
     index += OS::SNPrint((buffer + index),
                          (len - index),
                          "[%s]",
                          deopt_instrs[i]->ToCString());
   }
+
   return buffer;
 }
 
 
 // Returns a bool so it can be asserted.
 bool DeoptInfo::VerifyDecompression(const GrowableArray<DeoptInstr*>& original,
-                                    const Array& deopt_table) const {
-  intptr_t length = TranslationLength();
-  GrowableArray<DeoptInstr*> unpacked(length);
-  ToInstructions(deopt_table, &unpacked);
+                                    const Array& deopt_table,
+                                    const TypedData& packed) {
+  GrowableArray<DeoptInstr*> unpacked;
+  Unpack(deopt_table, packed, &unpacked);
   ASSERT(unpacked.length() == original.length());
   for (intptr_t i = 0; i < unpacked.length(); ++i) {
     ASSERT(unpacked[i]->Equals(*original[i]));
   }
   return true;
 }
 
 
-void DeoptInfo::PrintJSONImpl(JSONStream* stream, bool ref) const {
-  Object::PrintJSONImpl(stream, ref);
-}
-
-
-RawDeoptInfo* DeoptInfo::New(intptr_t num_commands) {
-  ASSERT(Object::deopt_info_class() != Class::null());
-  if ((num_commands < 0) || (num_commands > kMaxElements)) {
-    FATAL1("Fatal error in DeoptInfo::New(): invalid num_commands %" Pd "\n",
-           num_commands);
-  }
-  DeoptInfo& result = DeoptInfo::Handle();
-  {
-    uword size = DeoptInfo::InstanceSize(num_commands);
-    RawObject* raw = Object::Allocate(DeoptInfo::kClassId,
-                                      size,
-                                      Heap::kOld);
-    NoSafepointScope no_safepoint;
-    result ^= raw;
-    result.SetLength(num_commands);
-  }
-  return result.raw();
-}
-
-
-void DeoptInfo::SetLength(intptr_t value) const {
-  // This is only safe because we create a new Smi, which does not cause
-  // heap allocation.
-  StoreSmi(&raw_ptr()->length_, Smi::New(value));
-}
-
-
-void DeoptInfo::SetAt(intptr_t index,
-                      intptr_t instr_kind,
-                      intptr_t from_index) const {
-  NoSafepointScope no_safepoint;
-  *(EntryAddr(index, kInstruction)) = instr_kind;
-  *(EntryAddr(index, kFromIndex)) = from_index;
-}
-
-
 const char* ICData::ToCString() const {
   const char* kFormat = "ICData target:'%s' num-args: %" Pd
                         " num-checks: %" Pd "";
   const String& name = String::Handle(target_name());
   const intptr_t num_args = NumArgsTested();
   const intptr_t num_checks = NumberOfChecks();
   intptr_t len = OS::SNPrint(NULL, 0, kFormat, name.ToCString(),
       num_args, num_checks) + 1;
   char* chars = Isolate::Current()->current_zone()->Alloc<char>(len);
   OS::SNPrint(chars, len, kFormat, name.ToCString(), num_args, num_checks);
@@ skipping 792 matching lines @@
   }
 #endif  // DEBUG
 }
 
 
 bool Code::HasBreakpoint() const {
   return Isolate::Current()->debugger()->HasBreakpoint(*this);
 }
 
 
-RawDeoptInfo* Code::GetDeoptInfoAtPc(uword pc,
+RawTypedData* Code::GetDeoptInfoAtPc(uword pc,
                                      ICData::DeoptReasonId* deopt_reason,
                                      uint32_t* deopt_flags) const {
   ASSERT(is_optimized());
   const Instructions& instrs = Instructions::Handle(instructions());
   uword code_entry = instrs.EntryPoint();
   const Array& table = Array::Handle(deopt_info_array());

[Ivan Posva, 2015/04/08 07:12:13]

Please add a TODO here to consider removing the table of triplets, where one of
the entries is another table (the TypeData containing the deopt info) with a
single consolidated TypedData object.

[Vyacheslav Egorov (Google), 2015/04/08 13:07:39]

Done.

Though this structure needs random access, so I doubt it will be considerably
more compact than the current structure (though we would save some small
percent).

I realized that on the architectures with constant pool we can get rid of this
table entirely by doing the following:

1. deopt info for eager deopts shoudld be inlined into the call site for the
deopt stub (it will be just passed as a parameter to it).

2. deopt info for lazy deopts should be placed into the constant pool right
after the constant pool entry that corresponds to the call target.

Whether this will give any savings or not is a question though.

   ASSERT(!table.IsNull());
   // Linear search for the PC offset matching the target PC.
   intptr_t length = DeoptTable::GetLength(table);
   Smi& offset = Smi::Handle();
   Smi& reason_and_flags = Smi::Handle();
-  DeoptInfo& info = DeoptInfo::Handle();
+  TypedData& info = TypedData::Handle();
   for (intptr_t i = 0; i < length; ++i) {
     DeoptTable::GetEntry(table, i, &offset, &info, &reason_and_flags);
     if (pc == (code_entry + offset.Value())) {
       ASSERT(!info.IsNull());
       *deopt_reason = DeoptTable::ReasonField::decode(reason_and_flags.Value());
       *deopt_flags = DeoptTable::FlagsField::decode(reason_and_flags.Value());
       return info.raw();
     }
   }
   *deopt_reason = ICData::kDeoptUnknown;
-  return DeoptInfo::null();
+  return TypedData::null();
 }
 
 
 intptr_t Code::BinarySearchInSCallTable(uword pc) const {
   NoSafepointScope no_safepoint;
   const Array& table = Array::Handle(raw_ptr()->static_calls_target_table_);
   RawObject* key = reinterpret_cast<RawObject*>(Smi::New(pc - EntryPoint()));
   intptr_t imin = 0;
   intptr_t imax = table.Length() / kSCallTableEntryLength;
   while (imax >= imin) {
@@ skipping 8580 matching lines @@
   return tag_label.ToCString();
 }
 
 
 void UserTag::PrintJSONImpl(JSONStream* stream, bool ref) const {
   Instance::PrintJSONImpl(stream, ref);
 }
 
 
 }  // namespace dart