Compress deopt instructions in memory using variable length encoding.

runtime/vm/deopt_instructions.cc

 // Copyright (c) 2013, 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/deopt_instructions.h"
 
 #include "vm/assembler.h"
 #include "vm/code_patcher.h"
 #include "vm/compiler.h"
 #include "vm/intermediate_language.h"
@@ skipping 10 matching lines @@
 DECLARE_FLAG(bool, trace_deoptimization_verbose);
 
 
 DeoptContext::DeoptContext(const StackFrame* frame,
                            const Code& code,
                            DestFrameOptions dest_options,
                            fpu_register_t* fpu_registers,
                            intptr_t* cpu_registers)
     : code_(code.raw()),
       object_table_(code.object_table()),
-      deopt_info_(DeoptInfo::null()),
+      deopt_info_(TypedData::null()),
       dest_frame_is_allocated_(false),
       dest_frame_(NULL),
       dest_frame_size_(0),
       source_frame_is_allocated_(false),
       source_frame_(NULL),
       source_frame_size_(0),
       cpu_registers_(cpu_registers),
       fpu_registers_(fpu_registers),
       num_args_(0),
       deopt_reason_(ICData::kDeoptUnknown),
       deopt_flags_(0),
       thread_(Thread::Current()),
       deferred_slots_(NULL),
       deferred_objects_count_(0),
       deferred_objects_(NULL) {
-  const DeoptInfo& deopt_info = DeoptInfo::Handle(
+  const TypedData& deopt_info = TypedData::Handle(
       code.GetDeoptInfoAtPc(frame->pc(), &deopt_reason_, &deopt_flags_));
   ASSERT(!deopt_info.IsNull());
   deopt_info_ = deopt_info.raw();
 
   const Function& function = Function::Handle(code.function());
 
   // Do not include incoming arguments if there are optional arguments
   // (they are copied into local space at method entry).
   num_args_ =
       function.HasOptionalParameters() ? 0 : function.num_fixed_parameters();
@@ skipping 16 matching lines @@
     intptr_t* original_frame = source_frame_;
     source_frame_ = new intptr_t[source_frame_size_];
     ASSERT(source_frame_ != NULL);
     for (intptr_t i = 0; i < source_frame_size_; i++) {
       source_frame_[i] = original_frame[i];
     }
     source_frame_is_allocated_ = true;
   }
   caller_fp_ = GetSourceFp();
 
-  dest_frame_size_ = deopt_info.FrameSize();
+  dest_frame_size_ = DeoptInfo::FrameSize(deopt_info);
 
   if (dest_options == kDestIsAllocated) {
     dest_frame_ = new intptr_t[dest_frame_size_];
     ASSERT(source_frame_ != NULL);
     for (intptr_t i = 0; i < dest_frame_size_; i++) {
       dest_frame_[i] = 0;
     }
     dest_frame_is_allocated_ = true;
   }
 
@@ skipping 102 matching lines @@
     case DeoptInstr::kInt32:
     case DeoptInstr::kUint32:
       return true;
 
     case DeoptInstr::kRetAddress:
     case DeoptInstr::kPcMarker:
     case DeoptInstr::kCallerFp:
     case DeoptInstr::kCallerPc:
       return false;
 
-    case DeoptInstr::kSuffix:
     case DeoptInstr::kMaterializeObject:
     default:
       // We should not encounter these instructions when filling stack slots.
       UNREACHABLE();
       return false;
   }
   UNREACHABLE();
   return false;
 }
 
 
 void DeoptContext::FillDestFrame() {
   const Code& code = Code::Handle(code_);
-  const DeoptInfo& deopt_info = DeoptInfo::Handle(deopt_info_);
+  const TypedData& deopt_info = TypedData::Handle(deopt_info_);
 
-  const intptr_t len = deopt_info.TranslationLength();
-  GrowableArray<DeoptInstr*> deopt_instructions(len);
+  GrowableArray<DeoptInstr*> deopt_instructions;
   const Array& deopt_table = Array::Handle(code.deopt_info_array());
   ASSERT(!deopt_table.IsNull());
-  deopt_info.ToInstructions(deopt_table, &deopt_instructions);
+  DeoptInfo::Unpack(deopt_table, deopt_info, &deopt_instructions);
 
-  const intptr_t frame_size = deopt_info.FrameSize();
+  const intptr_t len = deopt_instructions.length();
+  const intptr_t frame_size = dest_frame_size_;
 
   // For now, we never place non-objects in the deoptimized frame if
   // the destination frame is a copy.  This allows us to copy the
   // deoptimized frame into an Array.
   const bool objects_only = dest_frame_is_allocated_;
 
   // All kMaterializeObject instructions are emitted before the instructions
   // that describe stack frames. Skip them and defer materialization of
   // objects until the frame is fully reconstructed and it is safe to perform
   // GC.
   // Arguments (class of the instance to allocate and field-value pairs) are
   // described as part of the expression stack for the bottom-most deoptimized
   // frame. They will be used during materialization and removed from the stack
   // right before control switches to the unoptimized code.
-  const intptr_t num_materializations = deopt_info.NumMaterializations();
+  const intptr_t num_materializations =
+      DeoptInfo::NumMaterializations(deopt_instructions);
   PrepareForDeferredMaterialization(num_materializations);
   for (intptr_t from_index = 0, to_index = kDartFrameFixedSize;
        from_index < num_materializations;
        from_index++) {
     const intptr_t field_count =
         DeoptInstr::GetFieldCount(deopt_instructions[from_index]);
     intptr_t* args = GetDestFrameAddressAt(to_index);
     DeferredObject* obj = new DeferredObject(field_count, args);
     SetDeferredObjectAt(from_index, obj);
     to_index += obj->ArgumentCount();
@@ skipping 451 matching lines @@
 
   void Execute(DeoptContext* deopt_context, intptr_t* dest_addr) {
     *dest_addr = deopt_context->GetSourcePc();
   }
 
  private:
   DISALLOW_COPY_AND_ASSIGN(DeoptCallerPcInstr);
 };
 
 
-// Deoptimization instruction that indicates the rest of this DeoptInfo is a
-// suffix of another one.  The suffix contains the info number (0 based
-// index in the deopt table of the DeoptInfo to share) and the length of the
-// suffix.

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

Is this saving unnecessary given the compression? How much did suffix reuse
contribute to savings in the original, non-compressed layout?

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

Suffix compression gives us 30-40% saving on top - according to my measurements.

-class DeoptSuffixInstr : public DeoptInstr {
- public:
-  DeoptSuffixInstr(intptr_t info_number, intptr_t suffix_length)
-      : info_number_(info_number), suffix_length_(suffix_length) {
-    ASSERT(info_number >= 0);
-    ASSERT(suffix_length >= 0);
-  }
-
-  explicit DeoptSuffixInstr(intptr_t source_index)
-      : info_number_(InfoNumber::decode(source_index)),
-        suffix_length_(SuffixLength::decode(source_index)) {
-  }
-
-  virtual intptr_t source_index() const {
-    return InfoNumber::encode(info_number_) |
-        SuffixLength::encode(suffix_length_);
-  }
-  virtual DeoptInstr::Kind kind() const { return kSuffix; }
-
-  virtual const char* ArgumentsToCString() const {
-    return Thread::Current()->zone()->PrintToString(
-        "%" Pd ":%" Pd, info_number_, suffix_length_);
-  }
-
-  void Execute(DeoptContext* deopt_context, intptr_t* dest_addr) {
-    // The deoptimization info is uncompressed by translating away suffixes
-    // before executing the instructions.
-    UNREACHABLE();
-  }
-
- private:
-  // Static decoder functions in DeoptInstr have access to the bitfield
-  // definitions.
-  friend class DeoptInstr;
-
-  static const intptr_t kFieldWidth = kBitsPerWord / 2;
-  class InfoNumber : public BitField<intptr_t, 0, kFieldWidth> { };
-  class SuffixLength : public BitField<intptr_t, kFieldWidth, kFieldWidth> { };
-
-  const intptr_t info_number_;
-  const intptr_t suffix_length_;
-
-  DISALLOW_COPY_AND_ASSIGN(DeoptSuffixInstr);
-};
-
-
 // Write reference to a materialized object with the given index into the
 // stack slot.
 class DeoptMaterializedObjectRefInstr : public DeoptInstr {
  public:
   explicit DeoptMaterializedObjectRefInstr(intptr_t index)
       : index_(index) {
     ASSERT(index >= 0);
   }
 
   virtual intptr_t source_index() const { return index_; }
@@ skipping 40 matching lines @@
     UNREACHABLE();
   }
 
  private:
   intptr_t field_count_;
 
   DISALLOW_COPY_AND_ASSIGN(DeoptMaterializeObjectInstr);
 };
 
 
-intptr_t DeoptInstr::DecodeSuffix(intptr_t source_index,
-                                  intptr_t* info_number) {
-  *info_number = DeoptSuffixInstr::InfoNumber::decode(source_index);
-  return DeoptSuffixInstr::SuffixLength::decode(source_index);
-}
-
-
 uword DeoptInstr::GetRetAddress(DeoptInstr* instr,
                                 const Array& object_table,
                                 Code* code) {
   ASSERT(instr->kind() == kRetAddress);
   DeoptRetAddressInstr* ret_address_instr =
       static_cast<DeoptRetAddressInstr*>(instr);
   // The following assert may trigger when displaying a backtrace
   // from the simulator.
   ASSERT(Isolate::IsDeoptAfter(ret_address_instr->deopt_id()));
   ASSERT(!object_table.IsNull());
@@ skipping 38 matching lines @@
     case kPcMarker:
       return new DeoptPcMarkerInstr(source_index);
     case kPp:
       return new DeoptPpInstr(source_index);
     case kCallerFp:
       return new DeoptCallerFpInstr();
     case kCallerPp:
       return new DeoptCallerPpInstr();
     case kCallerPc:
       return new DeoptCallerPcInstr();
-    case kSuffix:
-      return new DeoptSuffixInstr(source_index);
     case kMaterializedObjectRef:
       return new DeoptMaterializedObjectRefInstr(source_index);
     case kMaterializeObject:
       return new DeoptMaterializeObjectInstr(source_index);
   }
   UNREACHABLE();
   return NULL;
 }
 
 
@@ skipping 23 matching lines @@
     case kPcMarker:
       return "pc";
     case kPp:
       return "pp";
     case kCallerFp:
       return "callerfp";
     case kCallerPp:
       return "callerpp";
     case kCallerPc:
       return "callerpc";
-    case kSuffix:
-      return "suffix";
     case kMaterializedObjectRef:
       return "ref";
     case kMaterializeObject:
       return "mat";
   }
   UNREACHABLE();
   return NULL;
 }
 
 
@@ skipping 261 matching lines @@
     MaterializeObjectInstr* mat) const {
   for (intptr_t i = 0; i < materializations_.length(); i++) {
     if (materializations_[i] == mat) {
       return i;
     }
   }
   return -1;
 }
 
 
-RawDeoptInfo* DeoptInfoBuilder::CreateDeoptInfo(const Array& deopt_table) {
+static uint8_t* ZoneReAlloc(uint8_t* ptr,
+                            intptr_t old_size,
+                            intptr_t new_size) {
+  return Isolate::Current()->current_zone()->Realloc<uint8_t>(
+      ptr, old_size, new_size);
+}
+
+
+RawTypedData* DeoptInfoBuilder::CreateDeoptInfo(const Array& deopt_table) {
   // TODO(vegorov): enable compression of deoptimization info containing object
   // materialization instructions.
   const bool disable_compression =
       (instructions_[0]->kind() == DeoptInstr::kMaterializeObject);
 
   intptr_t length = instructions_.length();
 
   // Count the number of instructions that are a shared suffix of some deopt
   // info already written.
   TrieNode* suffix = trie_root_;
   intptr_t suffix_length = 0;
   if (FLAG_compress_deopt_info && !disable_compression) {
     for (intptr_t i = length - 1; i >= 0; --i) {
       TrieNode* node = suffix->FindChild(*instructions_[i]);
       if (node == NULL) break;
       suffix = node;
       ++suffix_length;
     }
   }
 
   // Allocate space for the translation.  If the shared suffix is longer
   // than one instruction, we replace it with a single suffix instruction.
   if (suffix_length > 1) length -= (suffix_length - 1);
-  const DeoptInfo& deopt_info =
-      DeoptInfo::Handle(zone(), DeoptInfo::New(length));
+
+  uint8_t* buffer;
+  typedef WriteStream::Raw<sizeof(intptr_t), intptr_t> Writer;
+  WriteStream stream(&buffer, ZoneReAlloc, 2 * length * kWordSize);
+
+  Writer::Write(&stream, FrameSize());
+
+  if (suffix_length > 1) {

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

bool use_suffix = suffix_length > 1;

and use this instead of (suffix_length > 1) at multiple places.

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

Done.

+    Writer::Write(&stream, suffix_length);
+    Writer::Write(&stream, suffix->info_number());
+  } else {
+    Writer::Write(&stream, 0);
+  }
 
   // Write the unshared instructions and build their sub-tree.
-  TrieNode* node = NULL;
+  TrieNode* node = (suffix_length > 1) ? suffix : trie_root_;
   intptr_t write_count = (suffix_length > 1) ? length - 1 : length;
-  for (intptr_t i = 0; i < write_count; ++i) {
+  for (intptr_t i = write_count - 1; i >= 0; --i) {
     DeoptInstr* instr = instructions_[i];
-    deopt_info.SetAt(i, instr->kind(), instr->source_index());
-    TrieNode* child = node;
-    node = new(zone()) TrieNode(instr, current_info_number_);
+    Writer::Write(&stream, instr->kind());
+    Writer::Write(&stream, instr->source_index());
+
+    TrieNode* child = new(zone()) TrieNode(instr, current_info_number_);
     node->AddChild(child);
+    node = child;
   }
 
-  if (suffix_length > 1) {
-    suffix->AddChild(node);
-    DeoptInstr* instr =
-        new(zone()) DeoptSuffixInstr(suffix->info_number(), suffix_length);
-    deopt_info.SetAt(length - 1, instr->kind(), instr->source_index());
-  } else {
-    trie_root_->AddChild(node);
+  const TypedData& deopt_info = TypedData::Handle(zone(), TypedData::New(
+      kTypedDataUint8ArrayCid, stream.bytes_written(), Heap::kOld));
+  {
+    NoSafepointScope no_safepoint;
+    memmove(deopt_info.DataAddr(0),
+            stream.buffer(),
+            stream.bytes_written());
   }
 
-  ASSERT(deopt_info.VerifyDecompression(instructions_, deopt_table));
+  ASSERT(DeoptInfo::VerifyDecompression(
+      instructions_, deopt_table, deopt_info));
   instructions_.Clear();
   materializations_.Clear();
   frame_start_ = -1;
 
   ++current_info_number_;
   return deopt_info.raw();
 }
 
 
 intptr_t DeoptTable::SizeFor(intptr_t length) {
   return length * kEntrySize;
 }
 
 void DeoptTable::SetEntry(const Array& table,
                           intptr_t index,
                           const Smi& offset,
-                          const DeoptInfo& info,
+                          const TypedData& info,
                           const Smi& reason) {
   ASSERT((table.Length() % kEntrySize) == 0);
   intptr_t i = index * kEntrySize;
   table.SetAt(i, offset);
   table.SetAt(i + 1, info);
   table.SetAt(i + 2, reason);
 }
 
 
 intptr_t DeoptTable::GetLength(const Array& table) {
   ASSERT((table.Length() % kEntrySize) == 0);
   return table.Length() / kEntrySize;
 }
 
 
 void DeoptTable::GetEntry(const Array& table,
                           intptr_t index,
                           Smi* offset,
-                          DeoptInfo* info,
+                          TypedData* info,
                           Smi* reason) {
   intptr_t i = index * kEntrySize;
   *offset ^= table.At(i);
   *info ^= table.At(i + 1);
   *reason ^= table.At(i + 2);
 }
 
 }  // namespace dart