Recognize and optimize a.runtimeType == b.runtimeType pattern.

Recognize and optimize a.runtimeType == b.runtimeType pattern.

Start by removing all get:runtimeType overrides in the patch files to have a single point computing the runtime type - Object.get:runtimeType. Handle string, double and integer types inside both intrinsic and runtime call to unify their handling and guarantee that code works even with intrinsifier disabled.

With overrides removed we can easily check that get:runtimeType is unique function name within the application that is being precompiled and use that to convert InstanceCall(get:runtimeType, ...) into StaticCall even nothing is known about the receiver.

This enables us to check if both left side and right side of comparison are StaticCall(Object.get:runtimeType, ...) when specializing InstanceCall(==, x, y). If they are we convert InstanceCall(==, StaticCall(get:runtimeType, a), StaticCall(get:runtimeType, b)) into StaticCall(Object._hasSameRuntimeType, a, b). A canonicalization rule will later delete unused get:runtimeType invocations.

Object._hasSameRuntimeType is implemented in C++ and intrinsified. It operates without creating new runtime types (except for Closures - where it does for simplicity). Cases of different class ids (i.e. a.[cid] != b.[cid]) and non-parameterized types are handled completely in the intrinsic. The rest is handled in the runtime code.

Microbenchmarking results:

Same parameterized classes: 15x improvement
Different parameterized classes: 300x improvement
Different/same non-parameterized classes: 2x improvement


BUG=
R=fschneider@google.com, regis@google.com

Committed: https://github.com/dart-lang/sdk/commit/f4ec20abac2286604565e9d5a6d1d744849c964d

[Vyacheslav Egorov (Google), 2016-09-28 20:48:54]

Description was changed from

==========
Recognize and optimize a.runtimeType == b.runtimeType pattern.

BUG=
==========

to

==========
Recognize and optimize a.runtimeType == b.runtimeType pattern.

Start by removing all get:runtimeType overrides in the patch files to have a
single point computing the runtime type - Object.get:runtimeType. Handle string,
double and integer types inside both intrinsic and runtime call to unify their
handling and guarantee that code works even with intrinsifier disabled.

With overrides removed we can easily check that get:runtimeType is unique
function name within the application that is being precompiled and use that to
convert InstanceCall(get:runtimeType, ...) into StaticCall even nothing is known
about the receiver. 

This enables us to check if both left side and right side of comparison are
StaticCall(Object.get:runtimeType, ...) when specializing InstanceCall(==, x,
y). If they are we convert InstanceCall(==, StaticCall(get:runtimeType, a),
StaticCall(get:runtimeType, b)) into StaticCall(Object._hasSameRuntimeType, a,
b). A canonicalization rule will later delete unused get:runtimeType
invocations.

Object._hasSameRuntimeType is implemented in C++ and intrinsified. It operates
without creating new runtime types (except for Closures - where it does for
simplicity). Cases of different class ids (i.e. a.[cid] != b.[cid]) and
non-parameterized types are handled completely in the intrinsic. The rest is
handled in the runtime code.

Microbenchmarking results:

Same parameterized classes: 15x improvement
Different parameterized classes: 300x improvement
Different/same non-parameterized classes: 2x improvement


BUG=
==========

[Vyacheslav Egorov (Google), 2016-09-28 20:48:54]

vegorov@google.com changed reviewers:
+ fschneider@google.com, regis@google.com

[Vyacheslav Egorov (Google), 2016-09-28 20:55:26]

Please take the first look. 

Intrinsic only implemented on x64 for now. I will port to other platforms if
first review reveals no issues with this approach.

[Florian Schneider, 2016-09-28 22:49:24]

First round of comments. I like the overall approach.

https://codereview.chromium.org/2379733002/diff/40001/runtime/lib/object.cc
File runtime/lib/object.cc (right):

https://codereview.chromium.org/2379733002/diff/40001/runtime/lib/object.cc#n...
runtime/lib/object.cc:155: if (!cls.IsGeneric() || (cls.NumTypeArguments() <=
0)) {
It reads a bit strange. Can <0 ever occur here?

https://codereview.chromium.org/2379733002/diff/40001/runtime/vm/aot_optimize...
File runtime/vm/aot_optimizer.cc (right):

https://codereview.chromium.org/2379733002/diff/40001/runtime/vm/aot_optimize...
runtime/vm/aot_optimizer.cc:150: if (RecognizeRuntimeTypeGetter(call)) {
Any reason why this is here and not in AotOptimizer::VisitInstanceCall?

https://codereview.chromium.org/2379733002/diff/40001/runtime/vm/intrinsifier...
File runtime/vm/intrinsifier_x64.cc (right):

https://codereview.chromium.org/2379733002/diff/40001/runtime/vm/intrinsifier...
runtime/vm/intrinsifier_x64.cc:1717: // different class ids and they are not
strings or integers.
I wonder if there are any other classes that have different implementation cids,
but report the same runtimeType:

e.g. typed lists Uint8List and _ExternalUint8Array should report "Uint8List" as
runtimeType.

Maybe the Class::canonical_type can be compared to handle this?

[Vyacheslav Egorov (Google), 2016-09-29 00:31:22]

https://codereview.chromium.org/2379733002/diff/40001/runtime/lib/object.cc
File runtime/lib/object.cc (right):

https://codereview.chromium.org/2379733002/diff/40001/runtime/lib/object.cc#n...
runtime/lib/object.cc:155: if (!cls.IsGeneric() || (cls.NumTypeArguments() <=
0)) {
On 2016/09/28 22:49:24, Florian Schneider wrote:
> It reads a bit strange. Can <0 ever occur here?

Yeah, it don't think it can... num_type_arguments can be negative, but this
should not... I probably just inverted some condition without thinking. 

Will fix.

https://codereview.chromium.org/2379733002/diff/40001/runtime/vm/aot_optimize...
File runtime/vm/aot_optimizer.cc (right):

https://codereview.chromium.org/2379733002/diff/40001/runtime/vm/aot_optimize...
runtime/vm/aot_optimizer.cc:150: if (RecognizeRuntimeTypeGetter(call)) {
On 2016/09/28 22:49:24, Florian Schneider wrote:
> Any reason why this is here and not in AotOptimizer::VisitInstanceCall?

Because we will never get into VisitInstanceCall if we know nothing about the
receiver - thus we can't create ICData for this call and TryCreateICData will
return false. However this inlining works even if we know nothing about the
receiver.

https://codereview.chromium.org/2379733002/diff/40001/runtime/vm/intrinsifier...
File runtime/vm/intrinsifier_x64.cc (right):

https://codereview.chromium.org/2379733002/diff/40001/runtime/vm/intrinsifier...
runtime/vm/intrinsifier_x64.cc:1717: // different class ids and they are not
strings or integers.
I checked all our sources and I could not see any other class overwriting
get:runtimeType - only _Double, strings and ints do - that's why they are
handled here - to match current a.runtimeType == b.runtimeType behavior. 

e.g. currently if a is Uint8List and b is external Uint8List then their runtime
types are different and this implementation captures this.

as far as I understand from the implementation Class::canonical_type() is a
canonical receiver type so it is different for Uint8List and ExternalUint8List
(and Smi vs Mint vs Bigint) - that is why we have to handle all these cases in a
special way instead of just looking at the canonical type.

[siva, 2016-09-29 02:28:19]

asiva@google.com changed reviewers:
+ asiva@google.com

[siva, 2016-09-29 02:28:20]

https://codereview.chromium.org/2379733002/diff/40001/runtime/lib/object_patc...
File runtime/lib/object_patch.dart (right):

https://codereview.chromium.org/2379733002/diff/40001/runtime/lib/object_patc...
runtime/lib/object_patch.dart:54: @patch Type get runtimeType native
"Object_runtimeType";
One could recover some of the lost effectiveness of the over rides by changing
this to have some dart code for those cases? Something like

Type get _runtimeType native "Object_runtimeType";
@patch Type get runtimeType {
  int cid = ClassId.getId(this);
  if (cid == ClassID.double) return double;
  else if (cid == ClassID.smi || cid .....) return int;
  else if (cid == ClassId.oneByteString....) return String;
  else return _runtimeType;
}

https://codereview.chromium.org/2379733002/diff/40001/runtime/vm/aot_optimize...
File runtime/vm/aot_optimizer.cc (right):

https://codereview.chromium.org/2379733002/diff/40001/runtime/vm/aot_optimize...
runtime/vm/aot_optimizer.cc:103: Class::Handle(Z,
thread()->isolate()->object_store()->object_class());
there seems to be an I in this file so I->object_store() ?

https://codereview.chromium.org/2379733002/diff/40001/runtime/vm/aot_optimize...
runtime/vm/aot_optimizer.cc:674: Class::Handle(Z,
thread()->isolate()->object_store()->object_class());
Ditto comment about I

[Vyacheslav Egorov (Google), 2016-09-29 15:01:44]

PTAL

New patch set adds polymorphic inlining of Object.get:runtimeType to guarantee
good performance in cases like:

f(x) {
  return x.runtimeType;
}

for (...) {
  f(""); f(1);
}

(though I think such cases are rare).

https://codereview.chromium.org/2379733002/diff/40001/runtime/lib/object_patc...
File runtime/lib/object_patch.dart (right):

https://codereview.chromium.org/2379733002/diff/40001/runtime/lib/object_patc...
runtime/lib/object_patch.dart:54: @patch Type get runtimeType native
"Object_runtimeType";
On 2016/09/29 02:28:20, siva wrote:
> One could recover some of the lost effectiveness of the over rides by changing
> this to have some dart code for those cases? Something like
> 
> Type get _runtimeType native "Object_runtimeType";
> @patch Type get runtimeType {
>   int cid = ClassId.getId(this);
>   if (cid == ClassID.double) return double;
>   else if (cid == ClassID.smi || cid .....) return int;
>   else if (cid == ClassId.oneByteString....) return String;
>   else return _runtimeType;
> }

This is precisely what intrinsic is doing. 

However even with intrinsic effectiveness was in monomorphic JIT case - which I
origianlly considered unimportant (it's unlikely that x.runtimeType call site is
monomorphic).

To match previous behavior and performance I added support for polymorphic
inlining of Object.get:runtimeType.

Now performance of monomorphic/polymorphic cases are on par or better in both
AOT and JIT case.

https://codereview.chromium.org/2379733002/diff/40001/runtime/vm/aot_optimize...
File runtime/vm/aot_optimizer.cc (right):

https://codereview.chromium.org/2379733002/diff/40001/runtime/vm/aot_optimize...
runtime/vm/aot_optimizer.cc:103: Class::Handle(Z,
thread()->isolate()->object_store()->object_class());
On 2016/09/29 02:28:20, siva wrote:
> there seems to be an I in this file so I->object_store() ?

Done.

https://codereview.chromium.org/2379733002/diff/40001/runtime/vm/aot_optimize...
runtime/vm/aot_optimizer.cc:674: Class::Handle(Z,
thread()->isolate()->object_store()->object_class());
On 2016/09/29 02:28:20, siva wrote:
> Ditto comment about I

Done.

[Florian Schneider, 2016-09-29 18:03:29]

https://codereview.chromium.org/2379733002/diff/40001/runtime/lib/object_patc...
File runtime/lib/object_patch.dart (right):

https://codereview.chromium.org/2379733002/diff/40001/runtime/lib/object_patc...
runtime/lib/object_patch.dart:54: @patch Type get runtimeType native
"Object_runtimeType";
On 2016/09/29 15:01:43, Vyacheslav Egorov (Google) wrote:
> On 2016/09/29 02:28:20, siva wrote:
> > One could recover some of the lost effectiveness of the over rides by
changing
> > this to have some dart code for those cases? Something like
> > 
> > Type get _runtimeType native "Object_runtimeType";
> > @patch Type get runtimeType {
> >   int cid = ClassId.getId(this);
> >   if (cid == ClassID.double) return double;
> >   else if (cid == ClassID.smi || cid .....) return int;
> >   else if (cid == ClassId.oneByteString....) return String;
> >   else return _runtimeType;
> > }
> 
> This is precisely what intrinsic is doing. 
> 
> However even with intrinsic effectiveness was in monomorphic JIT case - which
I
> origianlly considered unimportant (it's unlikely that x.runtimeType call site
is
> monomorphic).
> 
> To match previous behavior and performance I added support for polymorphic
> inlining of Object.get:runtimeType.
> 
> Now performance of monomorphic/polymorphic cases are on par or better in both
> AOT and JIT case. 
> 

I think Siva's suggestion would simplify the hand-written assembly with being
acceptable fast at the same time.

https://codereview.chromium.org/2379733002/diff/40001/runtime/vm/aot_optimize...
File runtime/vm/aot_optimizer.cc (right):

https://codereview.chromium.org/2379733002/diff/40001/runtime/vm/aot_optimize...
runtime/vm/aot_optimizer.cc:150: if (RecognizeRuntimeTypeGetter(call)) {
On 2016/09/29 00:31:22, Vyacheslav Egorov (Google) wrote:
> On 2016/09/28 22:49:24, Florian Schneider wrote:
> > Any reason why this is here and not in AotOptimizer::VisitInstanceCall?
> 
> Because we will never get into VisitInstanceCall if we know nothing about the
> receiver - thus we can't create ICData for this call and TryCreateICData will
> return false. However this inlining works even if we know nothing about the
> receiver. 

Yes, I meant that the ApplyICData phase always visits all instance calls (and
invokes VisitInstanceCall) I'm not sure why we actually have ApplyClassIds and
ApplyICData separate, but that would be another clean up.

https://codereview.chromium.org/2379733002/diff/40001/runtime/vm/intrinsifier...
File runtime/vm/intrinsifier_x64.cc (right):

https://codereview.chromium.org/2379733002/diff/40001/runtime/vm/intrinsifier...
runtime/vm/intrinsifier_x64.cc:1674: // Check if left hand size is a closure.
Closures are handled in the runtime.
s/size/side/

https://codereview.chromium.org/2379733002/diff/40001/runtime/vm/intrinsifier...
runtime/vm/intrinsifier_x64.cc:1717: // different class ids and they are not
strings or integers.
On 2016/09/29 00:31:22, Vyacheslav Egorov (Google) wrote:
> I checked all our sources and I could not see any other class overwriting
> get:runtimeType - only _Double, strings and ints do - that's why they are
> handled here - to match current a.runtimeType == b.runtimeType behavior. 
> 
> e.g. currently if a is Uint8List and b is external Uint8List then their
runtime
> types are different and this implementation captures this.
> 
> as far as I understand from the implementation Class::canonical_type() is a
> canonical receiver type so it is different for Uint8List and ExternalUint8List
> (and Smi vs Mint vs Bigint) - that is why we have to handle all these cases in
a
> special way instead of just looking at the canonical type. 

You're right. I was confused because toString() returns the same string for
external and internal typed lists. -- But the runtime type is different.

https://codereview.chromium.org/2379733002/diff/40001/runtime/vm/precompiler.cc
File runtime/vm/precompiler.cc (right):

https://codereview.chromium.org/2379733002/diff/40001/runtime/vm/precompiler....
runtime/vm/precompiler.cc:1525: get_runtime_type_is_unique_ = !farray.IsNull()
&& (farray.Length() == 1);
Use CHA? Also can be used in JIT then.

https://codereview.chromium.org/2379733002/diff/60001/runtime/vm/aot_optimize...
File runtime/vm/aot_optimizer.cc (right):

https://codereview.chromium.org/2379733002/diff/60001/runtime/vm/aot_optimize...
runtime/vm/aot_optimizer.cc:92: if ((precompiler_ == NULL) ||
!precompiler_->get_runtime_type_is_unique()) {
Can we use existing CHA to detect overrides? This way the same optimization
would work in the JIT seamlessly.

https://codereview.chromium.org/2379733002/diff/60001/runtime/vm/intrinsifier...
File runtime/vm/intrinsifier_x64.cc (right):

https://codereview.chromium.org/2379733002/diff/60001/runtime/vm/intrinsifier...
runtime/vm/intrinsifier_x64.cc:1693: __ j(NOT_EQUAL, &fall_through,
Assembler::kNearJump);
Idea: To make the comparison with parameterized classes fast, could we stored
the canonical type in the object, instead of the type arguments?

Then we always could do a simple comparison of the canonical type in generated
code.

Have not thought it through... It may be too big of a change though.

[Vyacheslav Egorov (Google), 2016-09-30 09:56:28]

https://codereview.chromium.org/2379733002/diff/40001/runtime/lib/object_patc...
File runtime/lib/object_patch.dart (right):

https://codereview.chromium.org/2379733002/diff/40001/runtime/lib/object_patc...
runtime/lib/object_patch.dart:54: @patch Type get runtimeType native
"Object_runtimeType";
On 2016/09/29 18:03:28, Florian Schneider wrote:
>
> I think Siva's suggestion would simplify the hand-written assembly with being
> acceptable fast at the same time.
>

I did measurements: it's 30-50% slower than the intrinsic on x64. If we consider
such hit acceptable - then we can certainly move to this instead of the
intrinsic. 

But I think 50% faster code is better.

https://codereview.chromium.org/2379733002/diff/40001/runtime/vm/aot_optimize...
File runtime/vm/aot_optimizer.cc (right):

https://codereview.chromium.org/2379733002/diff/40001/runtime/vm/aot_optimize...
runtime/vm/aot_optimizer.cc:150: if (RecognizeRuntimeTypeGetter(call)) {
On 2016/09/29 18:03:28, Florian Schneider wrote:
> On 2016/09/29 00:31:22, Vyacheslav Egorov (Google) wrote:
> > On 2016/09/28 22:49:24, Florian Schneider wrote:
> > > Any reason why this is here and not in AotOptimizer::VisitInstanceCall?
> > 
> > Because we will never get into VisitInstanceCall if we know nothing about
the
> > receiver - thus we can't create ICData for this call and TryCreateICData
will
> > return false. However this inlining works even if we know nothing about the
> > receiver. 
> 
> Yes, I meant that the ApplyICData phase always visits all instance calls (and
> invokes VisitInstanceCall) I'm not sure why we actually have ApplyClassIds and
> ApplyICData separate, but that would be another clean up.

Fair enough. Moved it into VisitInstanceCall.

https://codereview.chromium.org/2379733002/diff/40001/runtime/vm/precompiler.cc
File runtime/vm/precompiler.cc (right):

https://codereview.chromium.org/2379733002/diff/40001/runtime/vm/precompiler....
runtime/vm/precompiler.cc:1525: get_runtime_type_is_unique_ = !farray.IsNull()
&& (farray.Length() == 1);
On 2016/09/29 18:03:29, Florian Schneider wrote:
> Use CHA? Also can be used in JIT then.

CHA does not track subclasses of Object - because everything is a subclass of
Object. So for any method of Object it just says it's overridden. That's why I
had to hand roll my own way to detect this.

https://codereview.chromium.org/2379733002/diff/60001/runtime/vm/aot_optimize...
File runtime/vm/aot_optimizer.cc (right):

https://codereview.chromium.org/2379733002/diff/60001/runtime/vm/aot_optimize...
runtime/vm/aot_optimizer.cc:92: if ((precompiler_ == NULL) ||
!precompiler_->get_runtime_type_is_unique()) {
On 2016/09/29 18:03:29, Florian Schneider wrote:
> Can we use existing CHA to detect overrides? This way the same optimization
> would work in the JIT seamlessly.

See above. CHA does not work with Object.

We could make it work with Object in AOT case though.

https://codereview.chromium.org/2379733002/diff/60001/runtime/vm/intrinsifier...
File runtime/vm/intrinsifier_x64.cc (right):

https://codereview.chromium.org/2379733002/diff/60001/runtime/vm/intrinsifier...
runtime/vm/intrinsifier_x64.cc:1693: __ j(NOT_EQUAL, &fall_through,
Assembler::kNearJump);
On 2016/09/29 18:03:29, Florian Schneider wrote:
> Idea: To make the comparison with parameterized classes fast, could we stored
> the canonical type in the object, instead of the type arguments?
> 
> Then we always could do a simple comparison of the canonical type in generated
> code.
> 
> Have not thought it through... It may be too big of a change though.

Yes, that would be neat, but I think it's not that easy. For example in the code
like:

class Map<K, V> {
  foo() => new Baz<K, V>();
}

we currently don't allocate new type argument vector inside foo() because we can
just reuse existing one. However if we start storing canonical type then we need
to allocate one everytime. A more complicated solution would be to do it lazily
--- store either type arguments or canonical type inside the object (i.e. store
type arguments first - then promote it to become full blown type on the first
access).

However it's a gigantic change that is outside of scope for this change. 

Actually the work Karl & Peter doing regarding desugaring generics in the
front-end might simplify most of this code drastically.

[Vyacheslav Egorov (Google), 2016-09-30 17:03:04]

I ported to ARM and did a quick measurement on Flutter: this CL improves layout
benchmark by 10% as anticipated. 

Stock layout goes from ~540 on my phone to ~480.

I has to massage aot optimizer a bit though. I will upload changes on Monday.

[Florian Schneider, 2016-09-30 17:42:56]

https://codereview.chromium.org/2379733002/diff/40001/runtime/lib/object_patc...
File runtime/lib/object_patch.dart (right):

https://codereview.chromium.org/2379733002/diff/40001/runtime/lib/object_patc...
runtime/lib/object_patch.dart:54: @patch Type get runtimeType native
"Object_runtimeType";
On 2016/09/30 09:56:27, Vyacheslav Egorov (Google) wrote:
> On 2016/09/29 18:03:28, Florian Schneider wrote:
> >
> > I think Siva's suggestion would simplify the hand-written assembly with
being
> > acceptable fast at the same time.
> >
> 
> I did measurements: it's 30-50% slower than the intrinsic on x64. If we
consider
> such hit acceptable - then we can certainly move to this instead of the
> intrinsic. 
> 
> But I think 50% faster code is better.

Sounds good!

https://codereview.chromium.org/2379733002/diff/60001/runtime/vm/aot_optimize...
File runtime/vm/aot_optimizer.cc (right):

https://codereview.chromium.org/2379733002/diff/60001/runtime/vm/aot_optimize...
runtime/vm/aot_optimizer.cc:92: if ((precompiler_ == NULL) ||
!precompiler_->get_runtime_type_is_unique()) {
On 2016/09/30 09:56:28, Vyacheslav Egorov (Google) wrote:
> On 2016/09/29 18:03:29, Florian Schneider wrote:
> > Can we use existing CHA to detect overrides? This way the same optimization
> > would work in the JIT seamlessly.
> 
> See above. CHA does not work with Object.
> 
> We could make it work with Object in AOT case though. 

I think it would be out of scope for this CL.

I was just wondering: It does not seem too difficult to get the same
optimization working for DBC/JIT: Basically, only track the overriding of
runtimeType on class finalization - and register code has
a.runtimeType==b.runtimeType inlined with Object in CHA (since Object is not
otherwise used by CHA)

https://codereview.chromium.org/2379733002/diff/60001/runtime/vm/intrinsifier...
File runtime/vm/intrinsifier_x64.cc (right):

https://codereview.chromium.org/2379733002/diff/60001/runtime/vm/intrinsifier...
runtime/vm/intrinsifier_x64.cc:1693: __ j(NOT_EQUAL, &fall_through,
Assembler::kNearJump);
> 
> However it's a gigantic change that is outside of scope for this change. 

Agreed.

[Vyacheslav Egorov (Google), 2016-10-04 17:59:42]

This is ready for the review.

Main changes in this revision:

(1) AOT optimization is hoisted out of TryReplaceWithEqualityOp into
VisitInstanceCall. The reason for this is that TryReplaceWithEqualityOp is
considered speculative - which means it might get disabled when we fail to
remove all deopts in the function on the first run (which does happen in Flutter
in functions we care about.). Hoisting it out works - because optimization by
itself is not speculative - so it should not be disabled. 

I think we need to review all AOT optimizations that we have and separate out
speculative ones from non-speculative to make sure that we don't disable too
much when we retry, e.g. another example of this is comparisons with null,
something like x == null can always be specialized as a StrictCompare.

(2) I ported code to all arches.

Please take another look.

[Vyacheslav Egorov (Google), 2016-10-06 09:35:23]

friendly ping :)

[Florian Schneider, 2016-10-06 18:03:20]

Lgtm

https://codereview.chromium.org/2379733002/diff/100001/runtime/lib/object.cc
File runtime/lib/object.cc (right):

https://codereview.chromium.org/2379733002/diff/100001/runtime/lib/object.cc#...
runtime/lib/object.cc:155: if (!cls.IsGeneric() || (cls.NumTypeArguments() ==
0)) {
Could this be simplified to this?

if (cls.type_arguments_field_offset() == kNoTypeArguments) {...

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/flow_graph_...
File runtime/vm/flow_graph_inliner.cc (right):

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/flow_graph_...
runtime/vm/flow_graph_inliner.cc:3786: call->deopt_id() != Thread::kNoDeoptId ?
Can call ever have Thread::kNoDeoptId?

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/intermediat...
File runtime/vm/intermediate_language.cc (right):

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/intermediat...
runtime/vm/intermediate_language.cc:3236: for (intptr_t i = 0; i < num_checks;
i++) {
I'd rather use the propagated type of the receiver. If this call does not have
checks, then it should be computed already:

is_string = ArgumentAt(0)->Type()->ToAbstractType()->IsStringType()
is_int = ArgumentAt(0)->Type()->ToAbstractType()->IsIntType()
is_double = ArgumentAt(0)->Type()->ToAbstractType()->IsDoubleType()

For other types, you can check if ToCid() != kDynamicCid, the abstract type
would be the runtimeType.

[regis, 2016-10-08 09:10:37]

lgtm with a few comments

https://codereview.chromium.org/2379733002/diff/100001/runtime/lib/object.cc
File runtime/lib/object.cc (right):

https://codereview.chromium.org/2379733002/diff/100001/runtime/lib/object.cc#...
runtime/lib/object.cc:155: if (!cls.IsGeneric() || (cls.NumTypeArguments() ==
0)) {
If cls is generic, the number of type arguments will always be > 0. So this can
be simplified to
if (!cls.IsGeneric()) {
  ...
}

Florian, checking for kNoTypeArguments would not be correct, because a
non-generic class can still have type arguments, e.g. class C extends B<A>, but
they will be constant and always equal.

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/assembler_a...
File runtime/vm/assembler_arm.cc (right):

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/assembler_a...
runtime/vm/assembler_arm.cc:3021: Condition cond) {
Why do you need this new flavor? Since you are not setting the flags, calling
AddImmediate(rd, rn, -value, cond) should be equivalent.

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/assembler_a...
File runtime/vm/assembler_arm64.cc (right):

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/assembler_a...
runtime/vm/assembler_arm64.cc:685: void Assembler::SubImmediate(Register dest,
Register rn, int64_t imm) {
Same comment as for arm.

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/assembler_a...
File runtime/vm/assembler_arm64.h (right):

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/assembler_a...
runtime/vm/assembler_arm64.h:1249: void SubImmediate(Register dest, Register rn,
int64_t imm);
Not sure you need this.

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/intrinsifie...
File runtime/vm/intrinsifier_arm.cc (right):

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/intrinsifie...
runtime/vm/intrinsifier_arm.cc:1689: __ ldrh(R3, FieldAddress(R3,
Class::num_type_arguments_offset()));
You would cover more cases by checking the number of type parameters, rather
than number of type arguments, because non-generic classes (i.e. no type
parameters) may still have type arguments, but they are guaranteed to be equal.

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/intrinsifie...
File runtime/vm/intrinsifier_arm64.cc (right):

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/intrinsifie...
runtime/vm/intrinsifier_arm64.cc:1775: __ ldr(R3, FieldAddress(R3,
Class::num_type_arguments_offset()), kHalfword);
ditto

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/intrinsifie...
File runtime/vm/intrinsifier_ia32.cc (right):

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/intrinsifie...
runtime/vm/intrinsifier_ia32.cc:1822: __ movzxw(EBX, FieldAddress(EBX,
Class::num_type_arguments_offset()));
ditto

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/intrinsifie...
File runtime/vm/intrinsifier_mips.cc (right):

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/intrinsifie...
runtime/vm/intrinsifier_mips.cc:1806: __ lhu(T1, FieldAddress(T2,
Class::num_type_arguments_offset()));
ditto

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/intrinsifie...
File runtime/vm/intrinsifier_x64.cc (right):

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/intrinsifie...
runtime/vm/intrinsifier_x64.cc:1691: __ movzxw(RCX, FieldAddress(RDI,
Class::num_type_arguments_offset()));
ditto

[Vyacheslav Egorov (Google), 2016-10-24 20:23:03]

Thanks for the reviews.

https://codereview.chromium.org/2379733002/diff/100001/runtime/lib/object.cc
File runtime/lib/object.cc (right):

https://codereview.chromium.org/2379733002/diff/100001/runtime/lib/object.cc#...
runtime/lib/object.cc:155: if (!cls.IsGeneric() || (cls.NumTypeArguments() ==
0)) {
On 2016/10/08 09:10:37, regis wrote:
> If cls is generic, the number of type arguments will always be > 0. So this
can
> be simplified to
> if (!cls.IsGeneric()) {
>   ...
> }
> 
> Florian, checking for kNoTypeArguments would not be correct, because a
> non-generic class can still have type arguments, e.g. class C extends B<A>,
but
> they will be constant and always equal.
> 

Done.

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/assembler_a...
File runtime/vm/assembler_arm.cc (right):

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/assembler_a...
runtime/vm/assembler_arm.cc:3021: Condition cond) {
On 2016/10/08 09:10:37, regis wrote:
> Why do you need this new flavor? Since you are not setting the flags, calling
> AddImmediate(rd, rn, -value, cond) should be equivalent.

Done.

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/assembler_a...
File runtime/vm/assembler_arm64.cc (right):

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/assembler_a...
runtime/vm/assembler_arm64.cc:685: void Assembler::SubImmediate(Register dest,
Register rn, int64_t imm) {
On 2016/10/08 09:10:37, regis wrote:
> Same comment as for arm.

Done.

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/assembler_a...
File runtime/vm/assembler_arm64.h (right):

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/assembler_a...
runtime/vm/assembler_arm64.h:1249: void SubImmediate(Register dest, Register rn,
int64_t imm);
On 2016/10/08 09:10:37, regis wrote:
> Not sure you need this.

Done.

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/flow_graph_...
File runtime/vm/flow_graph_inliner.cc (right):

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/flow_graph_...
runtime/vm/flow_graph_inliner.cc:3786: call->deopt_id() != Thread::kNoDeoptId ?
On 2016/10/06 18:03:19, Florian Schneider wrote:
> Can call ever have Thread::kNoDeoptId?

That's an interesting question. In JIT it should not be possible. In AOT I
suspect that we can be much more liberal with deopt ids. 

 The code above does the same check so I will leave it for now and we will
investigate later.

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/intermediat...
File runtime/vm/intermediate_language.cc (right):

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/intermediat...
runtime/vm/intermediate_language.cc:3236: for (intptr_t i = 0; i < num_checks;
i++) {
On 2016/10/06 18:03:19, Florian Schneider wrote:
> I'd rather use the propagated type of the receiver. If this call does not have
> checks, then it should be computed already:
> 
> is_string = ArgumentAt(0)->Type()->ToAbstractType()->IsStringType()
> is_int = ArgumentAt(0)->Type()->ToAbstractType()->IsIntType()
> is_double = ArgumentAt(0)->Type()->ToAbstractType()->IsDoubleType()
> 
> For other types, you can check if ToCid() != kDynamicCid, the abstract type
> would be the runtimeType.

This is also called from a place where type propagation (might) have not been
run yet. 

I agree that using type propagator data might be better here.

We can look into refactoring it.

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/intrinsifie...
File runtime/vm/intrinsifier_arm.cc (right):

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/intrinsifie...
runtime/vm/intrinsifier_arm.cc:1689: __ ldrh(R3, FieldAddress(R3,
Class::num_type_arguments_offset()));
On 2016/10/08 09:10:37, regis wrote:
> You would cover more cases by checking the number of type parameters, rather
> than number of type arguments, because non-generic classes (i.e. no type
> parameters) may still have type arguments, but they are guaranteed to be
equal.

Nice idea, thanks! This can be a further improvement. The complexity inside
Class::NumTypeParameters put me off originally.

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/intrinsifie...
File runtime/vm/intrinsifier_arm64.cc (right):

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/intrinsifie...
runtime/vm/intrinsifier_arm64.cc:1775: __ ldr(R3, FieldAddress(R3,
Class::num_type_arguments_offset()), kHalfword);
On 2016/10/08 09:10:37, regis wrote:
> ditto

Acknowledged.

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/intrinsifie...
File runtime/vm/intrinsifier_ia32.cc (right):

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/intrinsifie...
runtime/vm/intrinsifier_ia32.cc:1822: __ movzxw(EBX, FieldAddress(EBX,
Class::num_type_arguments_offset()));
On 2016/10/08 09:10:37, regis wrote:
> ditto

Acknowledged.

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/intrinsifie...
File runtime/vm/intrinsifier_mips.cc (right):

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/intrinsifie...
runtime/vm/intrinsifier_mips.cc:1806: __ lhu(T1, FieldAddress(T2,
Class::num_type_arguments_offset()));
On 2016/10/08 09:10:37, regis wrote:
> ditto

Acknowledged.

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/intrinsifie...
File runtime/vm/intrinsifier_x64.cc (right):

https://codereview.chromium.org/2379733002/diff/100001/runtime/vm/intrinsifie...
runtime/vm/intrinsifier_x64.cc:1691: __ movzxw(RCX, FieldAddress(RDI,
Class::num_type_arguments_offset()));
On 2016/10/08 09:10:37, regis wrote:
> ditto

Acknowledged.

[Vyacheslav Egorov (Google), 2016-10-25 08:03:09]

Description was changed from

==========
Recognize and optimize a.runtimeType == b.runtimeType pattern.

Start by removing all get:runtimeType overrides in the patch files to have a
single point computing the runtime type - Object.get:runtimeType. Handle string,
double and integer types inside both intrinsic and runtime call to unify their
handling and guarantee that code works even with intrinsifier disabled.

With overrides removed we can easily check that get:runtimeType is unique
function name within the application that is being precompiled and use that to
convert InstanceCall(get:runtimeType, ...) into StaticCall even nothing is known
about the receiver. 

This enables us to check if both left side and right side of comparison are
StaticCall(Object.get:runtimeType, ...) when specializing InstanceCall(==, x,
y). If they are we convert InstanceCall(==, StaticCall(get:runtimeType, a),
StaticCall(get:runtimeType, b)) into StaticCall(Object._hasSameRuntimeType, a,
b). A canonicalization rule will later delete unused get:runtimeType
invocations.

Object._hasSameRuntimeType is implemented in C++ and intrinsified. It operates
without creating new runtime types (except for Closures - where it does for
simplicity). Cases of different class ids (i.e. a.[cid] != b.[cid]) and
non-parameterized types are handled completely in the intrinsic. The rest is
handled in the runtime code.

Microbenchmarking results:

Same parameterized classes: 15x improvement
Different parameterized classes: 300x improvement
Different/same non-parameterized classes: 2x improvement


BUG=
==========

to

==========
Recognize and optimize a.runtimeType == b.runtimeType pattern.

Start by removing all get:runtimeType overrides in the patch files to have a
single point computing the runtime type - Object.get:runtimeType. Handle string,
double and integer types inside both intrinsic and runtime call to unify their
handling and guarantee that code works even with intrinsifier disabled.

With overrides removed we can easily check that get:runtimeType is unique
function name within the application that is being precompiled and use that to
convert InstanceCall(get:runtimeType, ...) into StaticCall even nothing is known
about the receiver.

This enables us to check if both left side and right side of comparison are
StaticCall(Object.get:runtimeType, ...) when specializing InstanceCall(==, x,
y). If they are we convert InstanceCall(==, StaticCall(get:runtimeType, a),
StaticCall(get:runtimeType, b)) into StaticCall(Object._hasSameRuntimeType, a,
b). A canonicalization rule will later delete unused get:runtimeType
invocations.

Object._hasSameRuntimeType is implemented in C++ and intrinsified. It operates
without creating new runtime types (except for Closures - where it does for
simplicity). Cases of different class ids (i.e. a.[cid] != b.[cid]) and
non-parameterized types are handled completely in the intrinsic. The rest is
handled in the runtime code.

Microbenchmarking results:

Same parameterized classes: 15x improvement
Different parameterized classes: 300x improvement
Different/same non-parameterized classes: 2x improvement


BUG=
R=fschneider@google.com, regis@google.com

Committed:
https://github.com/dart-lang/sdk/commit/f4ec20abac2286604565e9d5a6d1d744849c964d
==========

[Vyacheslav Egorov (Google), 2016-10-25 08:03:11]

Committed patchset #7 (id:120001) manually as
f4ec20abac2286604565e9d5a6d1d744849c964d (presubmit successful).

[zra, 2016-10-25 11:48:06]

On 2016/10/25 08:03:11, Vyacheslav Egorov (Google) wrote:
> Committed patchset #7 (id:120001) manually as
> f4ec20abac2286604565e9d5a6d1d744849c964d (presubmit successful).

It looks like this change causes some problems with DBC:

FAILED: none-vm-checked debug_simdbc64
language/first_class_types_literals_test/01
Expected: Pass 
Actual: RuntimeError
CommandOutput[vm]:

stderr:
Unhandled exception:
Expect.equals(expected: <int>, actual: <int>) fails.
#0      Expect._fail (package:expect/expect.dart:435:5)
#1      Expect.equals (package:expect/expect.dart:102:5)
#2      main
(file:///usr/local/google/home/zra/dart/sdk/out/DebugSIMDBC64/generated_tests/language/first_class_types_literals_test_01.dart:40:10)
#3      _startIsolate.<anonymous closure>
(dart:isolate-patch/isolate_patch.dart:261)
#4      _RawReceivePortImpl._handleMessage
(dart:isolate-patch/isolate_patch.dart:148)


Command[vm]: DART_CONFIGURATION=DebugSIMDBC64 out/DebugSIMDBC64/dart
--enable_asserts --enable_type_checks --ignore-unrecognized-flags
--packages=.packages
out/DebugSIMDBC64/generated_tests/language/first_class_types_literals_test_01.dart

[Vyacheslav Egorov (Google), 2016-10-25 15:09:54]

On 2016/10/25 11:48:06, zra wrote:
> On 2016/10/25 08:03:11, Vyacheslav Egorov (Google) wrote:
> > Committed patchset #7 (id:120001) manually as
> > f4ec20abac2286604565e9d5a6d1d744849c964d (presubmit successful).
> 
> It looks like this change causes some problems with DBC:
> 
> FAILED: none-vm-checked debug_simdbc64
> language/first_class_types_literals_test/01
> Expected: Pass 
> Actual: RuntimeError
> CommandOutput[vm]:
> 
> stderr:
> Unhandled exception:
> Expect.equals(expected: <int>, actual: <int>) fails.
> #0      Expect._fail (package:expect/expect.dart:435:5)
> #1      Expect.equals (package:expect/expect.dart:102:5)
> #2      main
>
(file:///usr/local/google/home/zra/dart/sdk/out/DebugSIMDBC64/generated_tests/language/first_class_types_literals_test_01.dart:40:10)
> #3      _startIsolate.<anonymous closure>
> (dart:isolate-patch/isolate_patch.dart:261)
> #4      _RawReceivePortImpl._handleMessage
> (dart:isolate-patch/isolate_patch.dart:148)
> 
> 
> Command[vm]: DART_CONFIGURATION=DebugSIMDBC64 out/DebugSIMDBC64/dart
> --enable_asserts --enable_type_checks --ignore-unrecognized-flags
> --packages=.packages
>
out/DebugSIMDBC64/generated_tests/language/first_class_types_literals_test_01.dart

Thanks! I will dig into this in the evening. The exception is very confusing
though - looks like some int type is not canonicalized(?).