Index: runtime/vm/deopt_instructions.cc |
diff --git a/runtime/vm/deopt_instructions.cc b/runtime/vm/deopt_instructions.cc |
index 69b9e43f8d3edd53425b1b2dad95dc4382b6d41c..6f06c579b7cd7656e4799e1265eefb7787b05b4c 100644 |
--- a/runtime/vm/deopt_instructions.cc |
+++ b/runtime/vm/deopt_instructions.cc |
@@ -11,6 +11,9 @@ |
namespace dart { |
+DEFINE_FLAG(bool, compress_deopt_info, true, |
+ "Compress the size of the deoptimization info for optimized code."); |
+ |
DeoptimizationContext::DeoptimizationContext(intptr_t* to_frame_start, |
intptr_t to_frame_size, |
const Array& object_table, |
@@ -61,7 +64,7 @@ class DeoptStackSlotInstr : public DeoptInstr { |
} |
virtual intptr_t from_index() const { return stack_slot_index_; } |
- virtual DeoptInstr::Kind kind() const { return kCopyStackSlot; } |
+ virtual DeoptInstr::Kind kind() const { return kStackSlot; } |
virtual const char* ToCString() const { |
const char* format = "s%"Pd""; |
@@ -94,7 +97,7 @@ class DeoptDoubleStackSlotInstr : public DeoptInstr { |
} |
virtual intptr_t from_index() const { return stack_slot_index_; } |
- virtual DeoptInstr::Kind kind() const { return kCopyDoubleStackSlot; } |
+ virtual DeoptInstr::Kind kind() const { return kDoubleStackSlot; } |
virtual const char* ToCString() const { |
const char* format = "ds%"Pd""; |
@@ -130,7 +133,7 @@ class DeoptInt64StackSlotInstr : public DeoptInstr { |
} |
virtual intptr_t from_index() const { return stack_slot_index_; } |
- virtual DeoptInstr::Kind kind() const { return kCopyInt64StackSlot; } |
+ virtual DeoptInstr::Kind kind() const { return kInt64StackSlot; } |
virtual const char* ToCString() const { |
const char* format = "ms%"Pd""; |
@@ -166,15 +169,15 @@ class DeoptInt64StackSlotInstr : public DeoptInstr { |
// Deoptimization instruction creating return address using function and |
// deopt-id stored at 'object_table_index'. Uses the deopt-after |
// continuation point. |
-class DeoptRetAddrAfterInstr : public DeoptInstr { |
+class DeoptRetAfterAddressInstr : public DeoptInstr { |
public: |
- DeoptRetAddrAfterInstr(intptr_t object_table_index, intptr_t deopt_id) |
+ DeoptRetAfterAddressInstr(intptr_t object_table_index, intptr_t deopt_id) |
: object_table_index_(object_table_index), deopt_id_(deopt_id) { |
ASSERT(object_table_index >= 0); |
ASSERT(deopt_id >= 0); |
} |
- explicit DeoptRetAddrAfterInstr(intptr_t from_index) |
+ explicit DeoptRetAfterAddressInstr(intptr_t from_index) |
: object_table_index_(ObjectTableIndex::decode(from_index)), |
deopt_id_(DeoptId::decode(from_index)) { |
} |
@@ -183,7 +186,7 @@ class DeoptRetAddrAfterInstr : public DeoptInstr { |
return ObjectTableIndex::encode(object_table_index_) | |
DeoptId::encode(deopt_id_); |
} |
- virtual DeoptInstr::Kind kind() const { return kSetRetAfterAddress; } |
+ virtual DeoptInstr::Kind kind() const { return kRetAfterAddress; } |
virtual const char* ToCString() const { |
const char* format = "ret aft oti:%"Pd"(%"Pd")"; |
@@ -211,22 +214,22 @@ class DeoptRetAddrAfterInstr : public DeoptInstr { |
const intptr_t object_table_index_; |
const intptr_t deopt_id_; |
- DISALLOW_COPY_AND_ASSIGN(DeoptRetAddrAfterInstr); |
+ DISALLOW_COPY_AND_ASSIGN(DeoptRetAfterAddressInstr); |
}; |
// Deoptimization instruction creating return address using function and |
// deopt-id stored at 'object_table_index'. Uses the deopt-before |
// continuation point. |
-class DeoptRetAddrBeforeInstr : public DeoptInstr { |
+class DeoptRetBeforeAddressInstr : public DeoptInstr { |
public: |
- DeoptRetAddrBeforeInstr(intptr_t object_table_index, intptr_t deopt_id) |
+ DeoptRetBeforeAddressInstr(intptr_t object_table_index, intptr_t deopt_id) |
: object_table_index_(object_table_index), deopt_id_(deopt_id) { |
ASSERT(object_table_index >= 0); |
- ASSERT(deopt_id_ >= 0); |
+ ASSERT(deopt_id >= 0); |
} |
- explicit DeoptRetAddrBeforeInstr(intptr_t from_index) |
+ explicit DeoptRetBeforeAddressInstr(intptr_t from_index) |
: object_table_index_(ObjectTableIndex::decode(from_index)), |
deopt_id_(DeoptId::decode(from_index)) { |
} |
@@ -235,7 +238,7 @@ class DeoptRetAddrBeforeInstr : public DeoptInstr { |
return ObjectTableIndex::encode(object_table_index_) | |
DeoptId::encode(deopt_id_); |
} |
- virtual DeoptInstr::Kind kind() const { return kSetRetBeforeAddress; } |
+ virtual DeoptInstr::Kind kind() const { return kRetBeforeAddress; } |
virtual const char* ToCString() const { |
const char* format = "ret bef oti:%"Pd"(%"Pd")"; |
@@ -263,7 +266,7 @@ class DeoptRetAddrBeforeInstr : public DeoptInstr { |
const intptr_t object_table_index_; |
const intptr_t deopt_id_; |
- DISALLOW_COPY_AND_ASSIGN(DeoptRetAddrBeforeInstr); |
+ DISALLOW_COPY_AND_ASSIGN(DeoptRetBeforeAddressInstr); |
}; |
@@ -276,7 +279,7 @@ class DeoptConstantInstr : public DeoptInstr { |
} |
virtual intptr_t from_index() const { return object_table_index_; } |
- virtual DeoptInstr::Kind kind() const { return kCopyConstant; } |
+ virtual DeoptInstr::Kind kind() const { return kConstant; } |
virtual const char* ToCString() const { |
const char* format = "const oti:%"Pd""; |
@@ -308,7 +311,7 @@ class DeoptRegisterInstr: public DeoptInstr { |
: reg_(static_cast<Register>(reg_as_int)) {} |
virtual intptr_t from_index() const { return static_cast<intptr_t>(reg_); } |
- virtual DeoptInstr::Kind kind() const { return kCopyRegister; } |
+ virtual DeoptInstr::Kind kind() const { return kRegister; } |
virtual const char* ToCString() const { |
return Assembler::RegisterName(reg_); |
@@ -334,7 +337,7 @@ class DeoptXmmRegisterInstr: public DeoptInstr { |
: reg_(static_cast<XmmRegister>(reg_as_int)) {} |
virtual intptr_t from_index() const { return static_cast<intptr_t>(reg_); } |
- virtual DeoptInstr::Kind kind() const { return kCopyXmmRegister; } |
+ virtual DeoptInstr::Kind kind() const { return kXmmRegister; } |
virtual const char* ToCString() const { |
return Assembler::XmmRegisterName(reg_); |
@@ -361,7 +364,7 @@ class DeoptInt64XmmRegisterInstr: public DeoptInstr { |
: reg_(static_cast<XmmRegister>(reg_as_int)) {} |
virtual intptr_t from_index() const { return static_cast<intptr_t>(reg_); } |
- virtual DeoptInstr::Kind kind() const { return kCopyInt64XmmRegister; } |
+ virtual DeoptInstr::Kind kind() const { return kInt64XmmRegister; } |
virtual const char* ToCString() const { |
const char* format = "%s(m)"; |
@@ -402,7 +405,7 @@ class DeoptPcMarkerInstr : public DeoptInstr { |
} |
virtual intptr_t from_index() const { return object_table_index_; } |
- virtual DeoptInstr::Kind kind() const { return kSetPcMarker; } |
+ virtual DeoptInstr::Kind kind() const { return kPcMarker; } |
virtual const char* ToCString() const { |
const char* format = "pcmark oti:%"Pd""; |
@@ -443,7 +446,7 @@ class DeoptCallerFpInstr : public DeoptInstr { |
DeoptCallerFpInstr() {} |
virtual intptr_t from_index() const { return 0; } |
- virtual DeoptInstr::Kind kind() const { return kSetCallerFp; } |
+ virtual DeoptInstr::Kind kind() const { return kCallerFp; } |
virtual const char* ToCString() const { |
return "callerfp"; |
@@ -468,7 +471,7 @@ class DeoptCallerPcInstr : public DeoptInstr { |
DeoptCallerPcInstr() {} |
virtual intptr_t from_index() const { return 0; } |
- virtual DeoptInstr::Kind kind() const { return kSetCallerPc; } |
+ virtual DeoptInstr::Kind kind() const { return kCallerPc; } |
virtual const char* ToCString() const { |
return "callerpc"; |
@@ -485,28 +488,128 @@ class DeoptCallerPcInstr : public DeoptInstr { |
}; |
+// 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. |
+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 from_index) |
+ : info_number_(InfoNumber::decode(from_index)), |
+ suffix_length_(SuffixLength::decode(from_index)) { |
+ } |
+ |
+ virtual intptr_t from_index() const { |
+ return InfoNumber::encode(info_number_) | |
+ SuffixLength::encode(suffix_length_); |
+ } |
+ virtual DeoptInstr::Kind kind() const { return kSuffix; } |
+ |
+ virtual const char* ToCString() const { |
+ const char* format = "suffix %"Pd":%"Pd; |
+ intptr_t len = OS::SNPrint(NULL, 0, format, info_number_, suffix_length_); |
+ char* chars = Isolate::Current()->current_zone()->Alloc<char>(len + 1); |
+ OS::SNPrint(chars, len + 1, format, info_number_, suffix_length_); |
+ return chars; |
+ } |
+ |
+ void Execute(DeoptimizationContext* deopt_context, intptr_t to_index) { |
+ // The deoptimization info is uncompresses 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); |
+}; |
+ |
+ |
+intptr_t DeoptInstr::DecodeSuffix(intptr_t from_index, intptr_t* info_number) { |
+ *info_number = DeoptSuffixInstr::InfoNumber::decode(from_index); |
+ return DeoptSuffixInstr::SuffixLength::decode(from_index); |
+} |
+ |
+ |
DeoptInstr* DeoptInstr::Create(intptr_t kind_as_int, intptr_t from_index) { |
Kind kind = static_cast<Kind>(kind_as_int); |
switch (kind) { |
- case kCopyStackSlot: return new DeoptStackSlotInstr(from_index); |
- case kCopyDoubleStackSlot: return new DeoptDoubleStackSlotInstr(from_index); |
- case kCopyInt64StackSlot: return new DeoptInt64StackSlotInstr(from_index); |
- case kSetRetAfterAddress: return new DeoptRetAddrAfterInstr(from_index); |
- case kSetRetBeforeAddress: return new DeoptRetAddrBeforeInstr(from_index); |
- case kCopyConstant: return new DeoptConstantInstr(from_index); |
- case kCopyRegister: return new DeoptRegisterInstr(from_index); |
- case kCopyXmmRegister: return new DeoptXmmRegisterInstr(from_index); |
- case kCopyInt64XmmRegister: |
- return new DeoptInt64XmmRegisterInstr(from_index); |
- case kSetPcMarker: return new DeoptPcMarkerInstr(from_index); |
- case kSetCallerFp: return new DeoptCallerFpInstr(); |
- case kSetCallerPc: return new DeoptCallerPcInstr(); |
+ case kStackSlot: return new DeoptStackSlotInstr(from_index); |
+ case kDoubleStackSlot: return new DeoptDoubleStackSlotInstr(from_index); |
+ case kInt64StackSlot: return new DeoptInt64StackSlotInstr(from_index); |
+ case kRetAfterAddress: return new DeoptRetAfterAddressInstr(from_index); |
+ case kRetBeforeAddress: return new DeoptRetBeforeAddressInstr(from_index); |
+ case kConstant: return new DeoptConstantInstr(from_index); |
+ case kRegister: return new DeoptRegisterInstr(from_index); |
+ case kXmmRegister: return new DeoptXmmRegisterInstr(from_index); |
+ case kInt64XmmRegister: return new DeoptInt64XmmRegisterInstr(from_index); |
+ case kPcMarker: return new DeoptPcMarkerInstr(from_index); |
+ case kCallerFp: return new DeoptCallerFpInstr(); |
+ case kCallerPc: return new DeoptCallerPcInstr(); |
+ case kSuffix: return new DeoptSuffixInstr(from_index); |
} |
UNREACHABLE(); |
return NULL; |
} |
+class DeoptInfoBuilder::TrieNode : public ZoneAllocated { |
+ public: |
+ // Construct the root node representing the implicit "shared" terminator |
+ // at the end of each deopt info. |
+ TrieNode() : instruction_(NULL), info_number_(-1), children_(16) { } |
+ |
+ // Construct a node representing a written instruction. |
+ TrieNode(DeoptInstr* instruction, intptr_t info_number) |
+ : instruction_(instruction), info_number_(info_number), children_(4) { } |
+ |
+ intptr_t info_number() const { return info_number_; } |
+ |
+ void AddChild(TrieNode* child) { |
+ if (child != NULL) children_.Add(child); |
+ } |
+ |
+ TrieNode* FindChild(const DeoptInstr& instruction) { |
+ for (intptr_t i = 0; i < children_.length(); ++i) { |
+ TrieNode* child = children_[i]; |
+ if (child->instruction_->Equals(instruction)) return child; |
+ } |
+ return NULL; |
+ } |
+ |
+ private: |
+ const DeoptInstr* instruction_; // Instruction that was written. |
+ const intptr_t info_number_; // Index of the deopt info it was written to. |
+ |
+ GrowableArray<TrieNode*> children_; |
+}; |
+ |
+ |
+DeoptInfoBuilder::DeoptInfoBuilder(const intptr_t num_args) |
+ : instructions_(), |
+ object_table_(GrowableObjectArray::Handle(GrowableObjectArray::New())), |
+ num_args_(num_args), |
+ trie_root_(new TrieNode()), |
+ current_info_number_(0) { |
+} |
+ |
+ |
intptr_t DeoptInfoBuilder::FindOrAddObjectInTable(const Object& obj) const { |
for (intptr_t i = 0; i < object_table_.Length(); i++) { |
if (object_table_.At(i) == obj.raw()) { |
@@ -525,7 +628,8 @@ void DeoptInfoBuilder::AddReturnAddressBefore(const Function& function, |
intptr_t to_index) { |
const intptr_t object_table_index = FindOrAddObjectInTable(function); |
ASSERT(to_index == instructions_.length()); |
- instructions_.Add(new DeoptRetAddrBeforeInstr(object_table_index, deopt_id)); |
+ instructions_.Add(new DeoptRetBeforeAddressInstr(object_table_index, |
+ deopt_id)); |
} |
@@ -534,7 +638,8 @@ void DeoptInfoBuilder::AddReturnAddressAfter(const Function& function, |
intptr_t to_index) { |
const intptr_t object_table_index = FindOrAddObjectInTable(function); |
ASSERT(to_index == instructions_.length()); |
- instructions_.Add(new DeoptRetAddrAfterInstr(object_table_index, deopt_id)); |
+ instructions_.Add(new DeoptRetAfterAddressInstr(object_table_index, |
+ deopt_id)); |
} |
@@ -600,13 +705,47 @@ void DeoptInfoBuilder::AddCallerPc(intptr_t to_index) { |
} |
-RawDeoptInfo* DeoptInfoBuilder::CreateDeoptInfo() const { |
- const intptr_t len = instructions_.length(); |
- const DeoptInfo& deopt_info = DeoptInfo::Handle(DeoptInfo::New(len)); |
- for (intptr_t i = 0; i < len; i++) { |
+RawDeoptInfo* DeoptInfoBuilder::CreateDeoptInfo() { |
+ 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) { |
+ 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(DeoptInfo::New(length)); |
+ |
+ // Write the unshared instructions and build their sub-tree. |
+ TrieNode* node = NULL; |
+ intptr_t write_count = (suffix_length > 1) ? length - 1 : length; |
+ for (intptr_t i = 0; i < write_count; ++i) { |
DeoptInstr* instr = instructions_[i]; |
deopt_info.SetAt(i, instr->kind(), instr->from_index()); |
+ TrieNode* child = node; |
+ node = new TrieNode(instr, current_info_number_); |
+ node->AddChild(child); |
} |
+ suffix->AddChild(node); |
+ |
+ if (suffix_length > 1) { |
+ DeoptInstr* instr = |
+ new DeoptSuffixInstr(suffix->info_number(), suffix_length); |
+ deopt_info.SetAt(length - 1, instr->kind(), instr->from_index()); |
+ } |
+ |
+ instructions_.Clear(); |
+ ++current_info_number_; |
return deopt_info.raw(); |
} |