Compress deoptimization information by sharing common suffixes.

runtime/vm/deopt_instructions.h

 // 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.
 
 #ifndef VM_DEOPT_INSTRUCTIONS_H_
 #define VM_DEOPT_INSTRUCTIONS_H_
 
 #include "vm/allocation.h"
 #include "vm/assembler.h"
 #include "vm/growable_array.h"
@@ skipping 66 matching lines @@
   DISALLOW_COPY_AND_ASSIGN(DeoptimizationContext);
 };
 
 
 
 // Represents one deopt instruction, e.g, setup return address, store object,
 // store register, etc. The target is defined by instruction's position in
 // the deopt-info array.
 class DeoptInstr : public ZoneAllocated {
  public:
+  enum Kind {
+    kRetAfterAddress,
+    kRetBeforeAddress,
+    kConstant,
+    kRegister,
+    kXmmRegister,
+    kInt64XmmRegister,
+    kStackSlot,
+    kDoubleStackSlot,
+    kInt64StackSlot,
+    kPcMarker,
+    kCallerFp,
+    kCallerPc,
+    kSuffix,
+  };
+
   static DeoptInstr* Create(intptr_t kind_as_int, intptr_t from_index);
 
   DeoptInstr() {}
   virtual ~DeoptInstr() {}
 
   virtual const char* ToCString() const = 0;
 
   virtual void Execute(DeoptimizationContext* deopt_context,
                        intptr_t to_index) = 0;
 
+  bool Equals(const DeoptInstr& other) const {
+    return (kind() == other.kind()) && (from_index() == other.from_index());
+  }
+
+  // Decode the payload of a suffix command.  Return the suffix length and
+  // set the output parameter info_number to the index of the shared suffix.
+  static intptr_t DecodeSuffix(intptr_t from_index, intptr_t* info_number);
+
  protected:
-  enum Kind {
-    kSetRetAfterAddress,
-    kSetRetBeforeAddress,
-    kCopyConstant,
-    kCopyRegister,
-    kCopyXmmRegister,
-    kCopyInt64XmmRegister,
-    kCopyStackSlot,
-    kCopyDoubleStackSlot,
-    kCopyInt64StackSlot,
-    kSetPcMarker,
-    kSetCallerFp,
-    kSetCallerPc,
-  };
-
   virtual DeoptInstr::Kind kind() const = 0;
   virtual intptr_t from_index() const = 0;
 
   friend class DeoptInfoBuilder;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(DeoptInstr);
 };
 
 
-// Builds one instance of DeoptInfo. Call AddXXX methods in the order of
-// their target, starting wih deoptimized code continuation pc and ending with
-// the first argument of the deoptimized code.
+// Builds a deoptimization info table, one DeoptInfo at a time.  Call AddXXX
+// methods in the order of their target, starting wih deoptimized code
+// continuation pc and ending with the first argument of the deoptimized
+// code.  Call CreateDeoptInfo to write the accumulated instructions into
+// the heap and reset the builder's internal state for the next DeoptInfo.
 class DeoptInfoBuilder : public ValueObject {
  public:
+  explicit DeoptInfoBuilder(const intptr_t num_args);
+
   // 'object_table' holds all objects referred to by DeoptInstr in
   // all DeoptInfo instances for a single Code object.
-  DeoptInfoBuilder(const GrowableObjectArray& object_table,
-                   const intptr_t num_args)
-      : instructions_(),
-        object_table_(object_table),
-        num_args_(num_args) {}
+  const GrowableObjectArray& object_table() { return object_table_; }
 
   // Return address before instruction.
   void AddReturnAddressBefore(const Function& function,
                               intptr_t deopt_id,
                               intptr_t to_index);
 
   // Return address after instruction.
   void AddReturnAddressAfter(const Function& function,
                              intptr_t deopt_id,
                              intptr_t to_index);
 
   // Copy from optimized frame to unoptimized.
   void AddCopy(const Location& from_loc,
                const Value& from_value,
                intptr_t to_index);
   void AddPcMarker(const Function& function, intptr_t to_index);
   void AddCallerFp(intptr_t to_index);
   void AddCallerPc(intptr_t to_index);
 
-  RawDeoptInfo* CreateDeoptInfo() const;
+  RawDeoptInfo* CreateDeoptInfo();
 
  private:
+  class TrieNode;
+
   intptr_t FindOrAddObjectInTable(const Object& obj) const;
 
   GrowableArray<DeoptInstr*> instructions_;
   const GrowableObjectArray& object_table_;
   const intptr_t num_args_;
 
+  // Used to compress entries by sharing suffixes.
+  TrieNode* trie_root_;
+  intptr_t current_info_number_;
+
   DISALLOW_COPY_AND_ASSIGN(DeoptInfoBuilder);
 };
 
 
 // Utilities for managing the deopt table and its entries.  The table is
 // stored in an Array in the heap.  It consists of triples of (PC offset,
 // info, reason).  Elements of each entry are stored consecutively in the
 // array.
 class DeoptTable : public AllStatic {
  public:
@@ skipping 18 matching lines @@
                        DeoptInfo* info,
                        Smi* reason);
 
  private:
   static const intptr_t kEntrySize = 3;
 };
 
 }  // namespace dart
 
 #endif  // VM_DEOPT_INSTRUCTIONS_H_