Cache lookups at megamorphic call sites in optimized code.

Cache lookups at megamorphic call sites in optimized code.

The function name and argument descriptor are mapped to a lookup cache
at compile time.  The cache maps class id to target function.  It is
resizable.

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

[Vyacheslav Egorov (Google), 2012-12-03 14:55:22]

LGTM with comments addressed.

Please ensure that we have full test coverage for both hits and missed through
megamorphic stubs.

Including misses that lead to invocation of noSuchMethod, wrong argument count,
etc.

Please also ensure coverage with different argument descriptors that include
optional and named parameters.

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

https://codereview.chromium.org/11299298/diff/1/runtime/vm/code_generator.cc#...
runtime/vm/code_generator.cc:1029: if (cls.IsNullClass()) {
Please add a comment.

https://codereview.chromium.org/11299298/diff/1/runtime/vm/code_generator.cc#...
runtime/vm/code_generator.cc:1034: Smi::Cast(Object::Handle(isolate,
descriptor.At(0))).Value();
I know that this is not your code but I really don't like that currently we are
spreading magic constants all the way through our code when working with
arguments descriptor. 

descriptor.At(0) does not communicate intent correctly.

I would prefer to have a wrapper similar to Code::Comments that encapsulates
this knowledge.

https://codereview.chromium.org/11299298/diff/1/runtime/vm/megamorphic_cache_...
File runtime/vm/megamorphic_cache_table.cc (right):

https://codereview.chromium.org/11299298/diff/1/runtime/vm/megamorphic_cache_...
runtime/vm/megamorphic_cache_table.cc:16: table_(new Entry[kInitialCapacity]) {
I think you can allocate this on the first use of Lookup.

https://codereview.chromium.org/11299298/diff/1/runtime/vm/megamorphic_cache_...
runtime/vm/megamorphic_cache_table.cc:35: Entry* old_table = table_;
I suggest using realloc/free instead of new[]/delete[] than this loop goes away.

https://codereview.chromium.org/11299298/diff/1/runtime/vm/megamorphic_cache_...
runtime/vm/megamorphic_cache_table.cc:54: const Code& code =
I suggest adding a comment why do we need a fake function for this miss handler.

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

https://codereview.chromium.org/11299298/diff/1/runtime/vm/object.cc#newcode7814
runtime/vm/object.cc:7814: buckets.SetAt(2 * i, illegal);
I don't like magical constant spread around

https://codereview.chromium.org/11299298/diff/1/runtime/vm/object.cc#newcode7869
runtime/vm/object.cc:7869: set_fill_count(fill_count() + 1);
consider renaming fill_count to size

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

https://codereview.chromium.org/11299298/diff/1/runtime/vm/stub_code_ia32.cc#...
runtime/vm/stub_code_ia32.cc:594: __ int3();
What's up with this int3?

If it can not be reached then kill it (or make a purely debug code).

If it can be reached then it means our tests do not cover this case. Please
ensure test coverage for this.

Ditto x64.

[srdjan, 2012-12-03 19:10:46]

Please test NoSuchMethod handling in presence of Megamorphic call.

In addition to Slava's comments:

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

https://codereview.chromium.org/11299298/diff/1/runtime/vm/code_generator.cc#...
runtime/vm/code_generator.cc:1014: //   Arg0: Receiver's class ID.
This seems to be receiver not cid. Arg1 is ICData ... please fix the rest of the
comment.

https://codereview.chromium.org/11299298/diff/1/runtime/vm/code_generator.cc#...
runtime/vm/code_generator.cc:1017: //   Arg3: IC data.
Describe results (target not found vs found).

https://codereview.chromium.org/11299298/diff/1/runtime/vm/code_generator.cc#...
runtime/vm/code_generator.cc:1054: if (instructions.IsNull()) return;
Would the code above be simpler if changed to:

arguments.SetReturn(Instruction::Handle());
if (target.IsNull()) {
  return;
}

if (!target.HasCode()) {
  // compile, throw error and return if necessary
}

const Instructions& instructions = ....

https://codereview.chromium.org/11299298/diff/1/runtime/vm/code_generator.cc#...
runtime/vm/code_generator.cc:1059: return;
I also think that using isolate here explicitly makes the code look clumsier,
without any performance impact.

https://codereview.chromium.org/11299298/diff/1/runtime/vm/code_generator.cc#...
runtime/vm/code_generator.cc:1060: }
Could you also add tracing flag and code to be able to monitor the megamorphic
misses.

https://codereview.chromium.org/11299298/diff/1/runtime/vm/flow_graph_compile...
File runtime/vm/flow_graph_compiler_ia32.cc (right):

https://codereview.chromium.org/11299298/diff/1/runtime/vm/flow_graph_compile...
runtime/vm/flow_graph_compiler_ia32.cc:1140: __ j(ZERO, &found,
Assembler::kNearJump);
Maybe use a different label e.g., megamorphic_miss, since kIllegalCid means that
there is no such cid in the cache.

Please document also how you are calling into the miss handler.

https://codereview.chromium.org/11299298/diff/1/runtime/vm/megamorphic_cache_...
File runtime/vm/megamorphic_cache_table.cc (right):

https://codereview.chromium.org/11299298/diff/1/runtime/vm/megamorphic_cache_...
runtime/vm/megamorphic_cache_table.cc:14: : capacity_(kInitialCapacity),
initialize miss_handler to null.

https://codereview.chromium.org/11299298/diff/1/runtime/vm/megamorphic_cache_...
File runtime/vm/megamorphic_cache_table.h (right):

https://codereview.chromium.org/11299298/diff/1/runtime/vm/megamorphic_cache_...
runtime/vm/megamorphic_cache_table.h:21: class MegamorphicCacheTable : public
ValueObject {
Don't make it a ValueObject as this indicates to me that it can be used anywhere
as regular class. See also definition of classes ClassTable and StoreBuffer

https://codereview.chromium.org/11299298/diff/1/runtime/vm/megamorphic_cache_...
runtime/vm/megamorphic_cache_table.h:48: Entry* table_;
DISALLOW_YADYADA...

https://codereview.chromium.org/11299298/diff/1/runtime/vm/megamorphic_cache_...
runtime/vm/megamorphic_cache_table.h:49: };
You can use RawGrowableObjectArray* table_, then you do not need to implement
another growing algorithm.

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

https://codereview.chromium.org/11299298/diff/1/runtime/vm/stub_code_ia32.cc#...
runtime/vm/stub_code_ia32.cc:573: // descriptor is a smi.
Please document that EDX contains argument descriptor.

https://codereview.chromium.org/11299298/diff/1/runtime/vm/stub_code_ia32.cc#...
runtime/vm/stub_code_ia32.cc:581: __ popl(EDX);  // Arguments descriptor.
You need to preserve/restore argument descriptor and ic data explicitly and must
assume that any of outgoing arguments will be destroyed/changed in C code.

https://codereview.chromium.org/11299298/diff/1/runtime/vm/stub_code_ia32.cc#...
runtime/vm/stub_code_ia32.cc:585: __ LeaveFrame();
null as result should not be possible, should it? Or is it used for noSuchMethod
handling?

[Kevin Millikin (Google), 2012-12-06 14:03:11]

Thanks for the review.  I've added a test for no such method at megamorphic call
sites.

Please take a quick look.

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

https://codereview.chromium.org/11299298/diff/1/runtime/vm/code_generator.cc#...
runtime/vm/code_generator.cc:1014: //   Arg0: Receiver's class ID.
On 2012/12/03 19:10:46, srdjan wrote:
> This seems to be receiver not cid. Arg1 is ICData ... please fix the rest of
the
> comment.

Comment is fixed.

https://codereview.chromium.org/11299298/diff/1/runtime/vm/code_generator.cc#...
runtime/vm/code_generator.cc:1029: if (cls.IsNullClass()) {
On 2012/12/03 14:55:22, Vyacheslav Egorov (Google) wrote:
> Please add a comment.

The comment at the site I took this from said "For lookups treat null as an
instance of class Object."

I have copied it here, but I don't think it's a very good comment.  It just
repeats exactly what the code says, and doesn't have any indication *why* it
should work.  For instance, I'm somewhat surprised that we want to be invoking
Object::hashCode on null.

https://codereview.chromium.org/11299298/diff/1/runtime/vm/code_generator.cc#...
runtime/vm/code_generator.cc:1034: Smi::Cast(Object::Handle(isolate,
descriptor.At(0))).Value();
On 2012/12/03 14:55:22, Vyacheslav Egorov (Google) wrote:
> I know that this is not your code but I really don't like that currently we
are
> spreading magic constants all the way through our code when working with
> arguments descriptor. 
> 
> descriptor.At(0) does not communicate intent correctly.
> 
> I would prefer to have a wrapper similar to Code::Comments that encapsulates
> this knowledge.

I have fixed this in another change.

https://codereview.chromium.org/11299298/diff/1/runtime/vm/code_generator.cc#...
runtime/vm/code_generator.cc:1054: if (instructions.IsNull()) return;
On 2012/12/03 19:10:46, srdjan wrote:
> Would the code above be simpler if changed to:
> 
> arguments.SetReturn(Instruction::Handle());
> if (target.IsNull()) {
>   return;
> }
> 
> if (!target.HasCode()) {
>   // compile, throw error and return if necessary
> }
> 
> const Instructions& instructions = ....

Possibly.  I think we can sort out the code duplication here and in
ResolveCompileInstanceCallTarget (used by the polymorphic ICs), but I want to
leave that for a separate change.

https://codereview.chromium.org/11299298/diff/1/runtime/vm/code_generator.cc#...
runtime/vm/code_generator.cc:1059: return;
On 2012/12/03 19:10:46, srdjan wrote:
> I also think that using isolate here explicitly makes the code look clumsier,
> without any performance impact.

Removed.

https://codereview.chromium.org/11299298/diff/1/runtime/vm/code_generator.cc#...
runtime/vm/code_generator.cc:1060: }
On 2012/12/03 19:10:46, srdjan wrote:
> Could you also add tracing flag and code to be able to monitor the megamorphic
> misses.

I just printed something for --trace-ic and --trace-ic-miss-in-optimized.  Since
I haven't used those flags, I'm not sure if I'm printing the most useful
possible information.

https://codereview.chromium.org/11299298/diff/1/runtime/vm/flow_graph_compile...
File runtime/vm/flow_graph_compiler_ia32.cc (right):

https://codereview.chromium.org/11299298/diff/1/runtime/vm/flow_graph_compile...
runtime/vm/flow_graph_compiler_ia32.cc:1140: __ j(ZERO, &found,
Assembler::kNearJump);
On 2012/12/03 19:10:46, srdjan wrote:
> Maybe use a different label e.g., megamorphic_miss, since kIllegalCid means
that
> there is no such cid in the cache.
> 
> Please document also how you are calling into the miss handler.

Changed to call_target.

https://codereview.chromium.org/11299298/diff/1/runtime/vm/megamorphic_cache_...
File runtime/vm/megamorphic_cache_table.cc (right):

https://codereview.chromium.org/11299298/diff/1/runtime/vm/megamorphic_cache_...
runtime/vm/megamorphic_cache_table.cc:14: : capacity_(kInitialCapacity),
On 2012/12/03 19:10:46, srdjan wrote:
> initialize miss_handler to null.

Done.

https://codereview.chromium.org/11299298/diff/1/runtime/vm/megamorphic_cache_...
runtime/vm/megamorphic_cache_table.cc:16: table_(new Entry[kInitialCapacity]) {
On 2012/12/03 14:55:22, Vyacheslav Egorov (Google) wrote:
> I think you can allocate this on the first use of Lookup.

Done.

https://codereview.chromium.org/11299298/diff/1/runtime/vm/megamorphic_cache_...
runtime/vm/megamorphic_cache_table.cc:35: Entry* old_table = table_;
On 2012/12/03 14:55:22, Vyacheslav Egorov (Google) wrote:
> I suggest using realloc/free instead of new[]/delete[] than this loop goes
away.

OK, but I originally did it this way to avoid unsightly reinterpret_casts of
void* and sizeof arithmetic.

https://codereview.chromium.org/11299298/diff/1/runtime/vm/megamorphic_cache_...
runtime/vm/megamorphic_cache_table.cc:54: const Code& code =
On 2012/12/03 14:55:22, Vyacheslav Egorov (Google) wrote:
> I suggest adding a comment why do we need a fake function for this miss
handler.

OK.

https://codereview.chromium.org/11299298/diff/1/runtime/vm/megamorphic_cache_...
File runtime/vm/megamorphic_cache_table.h (right):

https://codereview.chromium.org/11299298/diff/1/runtime/vm/megamorphic_cache_...
runtime/vm/megamorphic_cache_table.h:21: class MegamorphicCacheTable : public
ValueObject {
On 2012/12/03 19:10:46, srdjan wrote:
> Don't make it a ValueObject as this indicates to me that it can be used
anywhere
> as regular class. See also definition of classes ClassTable and StoreBuffer

Done.

https://codereview.chromium.org/11299298/diff/1/runtime/vm/megamorphic_cache_...
runtime/vm/megamorphic_cache_table.h:48: Entry* table_;
On 2012/12/03 19:10:46, srdjan wrote:
> DISALLOW_YADYADA...

Done.

https://codereview.chromium.org/11299298/diff/1/runtime/vm/megamorphic_cache_...
runtime/vm/megamorphic_cache_table.h:49: };
On 2012/12/03 19:10:46, srdjan wrote:
> You can use RawGrowableObjectArray* table_, then you do not need to implement
> another growing algorithm.

Thanks for the good idea.  I'll hold that off for another change to get this one
landed.

The Entries are not heap objects now.  Making them their own class is a somewhat
painful and representing structured data in an array (e.g., ArgumentsDescriptor)
is also a lot of busy work in C++.

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

https://codereview.chromium.org/11299298/diff/1/runtime/vm/object.cc#newcode7814
runtime/vm/object.cc:7814: buckets.SetAt(2 * i, illegal);
On 2012/12/03 14:55:22, Vyacheslav Egorov (Google) wrote:
> I don't like magical constant spread around

I thought this was already pretty localized, but I named the constants for the
size of the pair and its components anyway.

There is no simple way to use constants in the generated code because it is
encoded in a platform-specific scale factor in a memory operand.

https://codereview.chromium.org/11299298/diff/1/runtime/vm/object.cc#newcode7869
runtime/vm/object.cc:7869: set_fill_count(fill_count() + 1);
On 2012/12/03 14:55:22, Vyacheslav Egorov (Google) wrote:
> consider renaming fill_count to size

Since variables ending in _size are always in bytes, that seems confusing.  I
was trying for something that couldn't be confused with the capacity (length,
entry_count, etc. seem confusing).

Since fill_count is bad, I went with filled_entry_count.

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

https://codereview.chromium.org/11299298/diff/1/runtime/vm/stub_code_ia32.cc#...
runtime/vm/stub_code_ia32.cc:573: // descriptor is a smi.
On 2012/12/03 19:10:46, srdjan wrote:
> Please document that EDX contains argument descriptor.

OK.

https://codereview.chromium.org/11299298/diff/1/runtime/vm/stub_code_ia32.cc#...
runtime/vm/stub_code_ia32.cc:581: __ popl(EDX);  // Arguments descriptor.
On 2012/12/03 19:10:46, srdjan wrote:
> You need to preserve/restore argument descriptor and ic data explicitly and
must
> assume that any of outgoing arguments will be destroyed/changed in C code.

Thank you, good catch.

https://codereview.chromium.org/11299298/diff/1/runtime/vm/stub_code_ia32.cc#...
runtime/vm/stub_code_ia32.cc:585: __ LeaveFrame();
On 2012/12/03 19:10:46, srdjan wrote:
> null as result should not be possible, should it? Or is it used for
noSuchMethod
> handling? 

No such method, implicit closures.

https://codereview.chromium.org/11299298/diff/1/runtime/vm/stub_code_ia32.cc#...
runtime/vm/stub_code_ia32.cc:594: __ int3();
On 2012/12/03 14:55:22, Vyacheslav Egorov (Google) wrote:
> What's up with this int3?
> 
> If it can not be reached then kill it (or make a purely debug code).
> 
> If it can be reached then it means our tests do not cover this case. Please
> ensure test coverage for this.
> 
> Ditto x64.

Thanks for catching it.  It's a reminder to myself to add a test that covers
this case since we don't have any.  I forgot about it when sending this out for
review.

It turns out that the code below didn't quite work because indirect calls break
our pattern matching on instance calls used by the InstanceFunctionLookup stub.

I have already fixed that separately.

[Vyacheslav Egorov (Google), 2012-12-10 09:23:44]

lgtm

https://codereview.chromium.org/11299298/diff/8001/runtime/vm/megamorphic_cac...
File runtime/vm/megamorphic_cache_table.cc (right):

https://codereview.chromium.org/11299298/diff/8001/runtime/vm/megamorphic_cac...
runtime/vm/megamorphic_cache_table.cc:30: table_ =
If you make kInitialCapacity == kCapacityIncrement and capacity_ = 0 initially
then you can remove this and realloc will handle it.

[Kevin Millikin (Google), 2012-12-10 09:30:46]

https://codereview.chromium.org/11299298/diff/8001/runtime/vm/megamorphic_cac...
File runtime/vm/megamorphic_cache_table.cc (right):

https://codereview.chromium.org/11299298/diff/8001/runtime/vm/megamorphic_cac...
runtime/vm/megamorphic_cache_table.cc:30: table_ =
On 2012/12/10 09:23:44, Vyacheslav Egorov (Google) wrote:
> If you make kInitialCapacity == kCapacityIncrement and capacity_ = 0 initially
> then you can remove this and realloc will handle it. 

Thanks.  That's better.