Compress deoptimization information by sharing common suffixes.

Compress deoptimization information by sharing common suffixes.

For all the deoptimization entries in a function, build a suffix trie.  Add
a new deoptimization instruction that indicates the rest of the translation
is a fixed-length suffix of another entry.

BUG=

Committed: https://code.google.com/p/dart/source/detail?r=14252

[Kevin Millikin (Google), 2012-10-05 14:31:55]

http://codereview.chromium.org/11040058/diff/1/runtime/vm/compiler.cc
File runtime/vm/compiler.cc (right):

http://codereview.chromium.org/11040058/diff/1/runtime/vm/compiler.cc#newcode351
runtime/vm/compiler.cc:351: OS::Print("%4"Pd": 0x%"Px"  %s  (%s)\n",
Here we print 'compressed' entries, sometimes terminated by a suffix.  I think
that's fine, but we could also choose to decompress them before printing.

http://codereview.chromium.org/11040058/diff/1/runtime/vm/deopt_instructions.cc
File runtime/vm/deopt_instructions.cc (right):

http://codereview.chromium.org/11040058/diff/1/runtime/vm/deopt_instructions....
runtime/vm/deopt_instructions.cc:516: UNREACHABLE();
Notice.  The strategy is to 'uncompress' the entry before the translation, so
these don't ever get executed.

http://codereview.chromium.org/11040058/diff/1/runtime/vm/deopt_instructions.h
File runtime/vm/deopt_instructions.h (right):

http://codereview.chromium.org/11040058/diff/1/runtime/vm/deopt_instructions....
runtime/vm/deopt_instructions.h:88: kRetAfterAddress,
I renamed these and some of the class names so the naming convention was more
consistent.

kInstructionName correspondes to class DeoptInstructionNameInstr.

http://codereview.chromium.org/11040058/diff/1/runtime/vm/deopt_instructions....
runtime/vm/deopt_instructions.h:137: class DeoptInfoBuilder : public ValueObject
{
This class had to be refactored to build all the DeoptInfos for a function, to
avoid having to thread the trie around.  It also enables moving the object table
into this class.

http://codereview.chromium.org/11040058/diff/1/runtime/vm/object.h
File runtime/vm/object.h (right):

http://codereview.chromium.org/11040058/diff/1/runtime/vm/object.h#newcode2324
runtime/vm/object.h:2324: intptr_t GetLength() const;
Accidental rename.  I'll rename it back to Length().

[srdjan, 2012-10-08 16:37:58]

- Add a flag to disable using tries for compressing suffixes
- Check for regressions in compilation speed, e.g:
dart --compiler_stats lib/compiler/implementation/dart2js.dart
tests/utils/dummy_compiler_test.dart
- Run tests with optimization-counter-threshold=5
- How much space do we save (--trace-isolates)?

https://codereview.chromium.org/11040058/diff/1/runtime/vm/compiler.cc
File runtime/vm/compiler.cc (right):

https://codereview.chromium.org/11040058/diff/1/runtime/vm/compiler.cc#newcod...
runtime/vm/compiler.cc:351: OS::Print("%4"Pd": 0x%"Px"  %s  (%s)\n",
On 2012/10/05 14:31:55, kmillikin wrote:
> Here we print 'compressed' entries, sometimes terminated by a suffix.  I think
> that's fine, but we could also choose to decompress them before printing.

I think we need to do both, i.e., have a flag that decompresses deopt info.

https://codereview.chromium.org/11040058/diff/1/runtime/vm/deopt_instructions.cc
File runtime/vm/deopt_instructions.cc (right):

https://codereview.chromium.org/11040058/diff/1/runtime/vm/deopt_instructions...
runtime/vm/deopt_instructions.cc:488: class DeoptSuffixInstr : public DeoptInstr
{
Add brief comment about the class.

https://codereview.chromium.org/11040058/diff/1/runtime/vm/deopt_instructions...
runtime/vm/deopt_instructions.cc:574: if (child != NULL) children_.Add(child);
When can you call this with child==NULL ?

https://codereview.chromium.org/11040058/diff/1/runtime/vm/deopt_instructions...
runtime/vm/deopt_instructions.cc:586: const DeoptInstr* instruction_;  //
Istruction that was written.
s/Istruction/Instruction/

https://codereview.chromium.org/11040058/diff/1/runtime/vm/deopt_instructions.h
File runtime/vm/deopt_instructions.h (right):

https://codereview.chromium.org/11040058/diff/1/runtime/vm/deopt_instructions...
runtime/vm/deopt_instructions.h:173: TrieNode* trie_root_;
Add comment: used to compress by sharing suffixes ?

https://codereview.chromium.org/11040058/diff/1/runtime/vm/object.h
File runtime/vm/object.h (right):

https://codereview.chromium.org/11040058/diff/1/runtime/vm/object.h#newcode2324
runtime/vm/object.h:2324: intptr_t GetLength() const;
On 2012/10/05 14:31:55, kmillikin wrote:
> Accidental rename.  I'll rename it back to Length().

 Please upload the most recent version.

[Kevin Millikin (Google), 2012-10-10 13:19:59]

On 2012/10/08 16:37:58, srdjan wrote:
> - Add a flag to disable using tries for compressing suffixes
> - Check for regressions in compilation speed, e.g:
> dart --compiler_stats lib/compiler/implementation/dart2js.dart
> tests/utils/dummy_compiler_test.dart
> - Run tests with optimization-counter-threshold=5
> - How much space do we save (--trace-isolates)?

Take another look.  When compression is disabled, I still build a partial trie. 
It's kind of complicated to otherwise support code for two different
deoptimization info formats, so I hope that's good enough.

Any regression in compilation time is lost in the noise.  The suffix trees don't
have a high branching factor, so the linear search for children doesn't make
difference in practice.

--trace-isolates just tells us the old space capacity and size of the space at
exit, so it's hard to compare.  I instrumented to count all bytes allocated for
deopt info (just the translation commands, not the table).  On
dummy_compiler_test.dart:

Before: 14151928 (13.5 MB)  After: 7791760 (7.5 MB)  --> Reduction of 45%.

The child passed to AddChild can be NULL at both call sites.  When building a
new sub-trie for an unshared part of a translation from the bottom up, we start
with a NULL trie and cons its parents onto it.  When grafting a sub-trie onto
the global one, we can have an empty sub-trie if the entire translation is
shared (a copy of some other one).  We could always check before calling
AddChild but I thought this was a simpler implementation and didn't really
thingk AddChildIfNonNull was necessary as a name....

[srdjan, 2012-10-11 15:36:57]

lgtm

[srdjan, 2012-10-11 15:36:59]

lgtm