Allow dispatch to use a range of Class-ids in tests

Allow dispatch to use a range of Class-ids in tests

Use polymorphic call for all multi-cid call sites
Remove special hashCode code

R=vegorov@google.com
BUG=

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

[Vyacheslav Egorov (Google), 2017-03-10 10:31:31]

some initial comments

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

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/constants_dbc.h#...
runtime/vm/constants_dbc.h:175: //  - PushPolymorphic3InstanceCall ArgC, D
Better call it 

PushPolymorphicInstanceCallByRange

(I think original instruction should have been called

PushPolymorphicInstanceCallTarget)

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/constants_dbc.h#...
runtime/vm/constants_dbc.h:603: //  - CheckCids2 rA, rB, rC
Better call it CheckCidRanges

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/flow_graph_compi...
File runtime/vm/flow_graph_compiler.cc (left):

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/flow_graph_compi...
runtime/vm/flow_graph_compiler.cc:174: return ratio >
FLAG_inline_smi_string_hashcode_ratio;
if you killed the code, kill the flag.

but also we need to try and find the benchmark this was helping. maybe blame the
code?

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/flow_graph_compi...
File runtime/vm/flow_graph_compiler.h (right):

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/flow_graph_compi...
runtime/vm/flow_graph_compiler.h:649: intptr_t GetGoodBias(const
GrowableArray<CidRangeTarget>& sorted,
ComputeGoodBiasForCidComparison(...)?

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/flow_graph_compi...
File runtime/vm/flow_graph_compiler_arm.cc (right):

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/flow_graph_compi...
runtime/vm/flow_graph_compiler_arm.cc:1573: if (!is_last_check && !complete &&
count < (total_ic_calls >> 5)) {
Magic constants!

This is a suspect optimization because we are ignoring `fail` label - which in
JIT case would be a deopt. 

Going to megamorphic stub violates assumption that PolymorphicInstanceCall would
deoptimize if a mismatched cid is found. So if we propagate types from
PolymorphicInstanceCalls (treating them as ClassCheck-s) then we will break.

(We actually already do that in AOT just not in JIT).

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/flow_graph_compi...
File runtime/vm/flow_graph_compiler_x64.cc (right):

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/flow_graph_compi...
runtime/vm/flow_graph_compiler_x64.cc:1498: int bias = GetGoodBias(sorted, 127);
magic constant?

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/flow_graph_inlin...
File runtime/vm/flow_graph_inliner.cc (right):

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/flow_graph_inlin...
runtime/vm/flow_graph_inliner.cc:477: bool TryInliningPoly(intptr_t cid_start,
Can an argument to this function simply be CidRangeTarget?

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/flow_graph_inlin...
runtime/vm/flow_graph_inliner.cc:1669: intptr_t try_idx =
call_->GetBlock()->try_index();
const intptr_t try_idx

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/flow_graph_inlin...
runtime/vm/flow_graph_inliner.cc:1697: if (is_last_test && (!test_is_range ||
call_->complete()) &&
Comment above does not reflect reality completely. There are more to this
condition than written in the comment.

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/flow_graph_inlin...
runtime/vm/flow_graph_inliner.cc:1702: if (!call_->complete()) {
needs a comment that condition above implies that !test_is_range.

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/flow_graph_inlin...
runtime/vm/flow_graph_inliner.cc:1963: printf("%s cid %" Pd "-%" Pd ": %" Pd
"/%" Pd
Here and below: This should be THR_Print. Also this calls for a helper because
CidRangeTarget formatting it repeated multiple times.

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/intermediate_lan...
File runtime/vm/intermediate_language.h (right):

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/intermediate_lan...
runtime/vm/intermediate_language.h:2808: intptr_t total_ic_count() { return
total_ic_count_; }
This is an extremely confusing name. We need:

(a) a better name
(b) some comments on why this is needed as opposed to CallCount() above.

Please rearrange members in such a way that CallCount() and total_ic_count are
next to each other.

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/intermediate_lan...
File runtime/vm/intermediate_language_arm.cc (right):

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/intermediate_lan...
runtime/vm/intermediate_language_arm.cc:6310: if (sorted_ic_data.length() > 4 &&
IsDenseSwitch()) {
What is this magical 4? Is this the same 4 as FLAG_max_polymorphic_checks

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/intermediate_lan...
File runtime/vm/intermediate_language_dbc.cc (right):

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/intermediate_lan...
runtime/vm/intermediate_language_dbc.cc:1498: bool using_ranges = false;
Actually we could be smarter about using ranges on DBC, e.g. 

[1, 2], [5, 5], [10 , 10]

are better represented as 

1, 2, 5, 10

then range based call.

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/jit_optimizer.cc
File runtime/vm/jit_optimizer.cc (left):

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/jit_optimizer.cc...
runtime/vm/jit_optimizer.cc:1503: ? FLAG_max_equality_polymorphic_checks
If you killed the code, kill the flag FLAG_max_equality_polymorphic_checks.

It might be good to blame the file and see which benchmark did we think this
code helps and remeasure that benchmark. 

Might be some dart2js corner case. (Similar stuff for hashCode).

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

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/jit_optimizer.cc...
runtime/vm/jit_optimizer.cc:1483: Class& clarse = Class::Handle(Z,
I->class_table()->At(class_id));
please use cls

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/jit_optimizer.cc...
runtime/vm/jit_optimizer.cc:1494: bool JitOptimizer::TryAddClass(const ICData&
ic_data,
This function is called TryAddClass but it does not actually trying to add
anything anywere, nor it uses ic_data parameter.

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/jit_optimizer.cc...
runtime/vm/jit_optimizer.cc:1502: RawClass* raw_class =
I->class_table()->At(class_id);
This seems to almost duplicate the code in the LookupMethodFor(...) maybe merge
them together and make LookupMethodFor(...) return false if class does not
exist.

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

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/jit_optimizer.h#...
runtime/vm/jit_optimizer.h:55: void TryExpandClassesInIC(const ICData& ic_data);
InICData

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/jit_optimizer.h#...
runtime/vm/jit_optimizer.h:60: bool TryAddClass(const ICData& ic_data,
TryAddCheck?

[erikcorry, 2017-03-10 13:30:02]

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

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/constants_dbc.h#...
runtime/vm/constants_dbc.h:175: //  - PushPolymorphic3InstanceCall ArgC, D
On 2017/03/10 10:31:30, Vyacheslav Egorov (Google) wrote:
> Better call it 
> 
> PushPolymorphicInstanceCallByRange
> 
> (I think original instruction should have been called
> 
> PushPolymorphicInstanceCallTarget)

Done.

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/constants_dbc.h#...
runtime/vm/constants_dbc.h:603: //  - CheckCids2 rA, rB, rC
On 2017/03/10 10:31:30, Vyacheslav Egorov (Google) wrote:
> Better call it CheckCidRanges

Done.

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/flow_graph_compi...
File runtime/vm/flow_graph_compiler.cc (left):

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/flow_graph_compi...
runtime/vm/flow_graph_compiler.cc:174: return ratio >
FLAG_inline_smi_string_hashcode_ratio;
On 2017/03/10 10:31:30, Vyacheslav Egorov (Google) wrote:
> if you killed the code, kill the flag.
> 
> but also we need to try and find the benchmark this was helping. maybe blame
the
> code?

Flag killed.

It was introduced here with no explanation:
https://codereview.chromium.org/1921893002

I started a Golem run where I switched it off.

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/flow_graph_compi...
File runtime/vm/flow_graph_compiler.h (right):

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/flow_graph_compi...
runtime/vm/flow_graph_compiler.h:649: intptr_t GetGoodBias(const
GrowableArray<CidRangeTarget>& sorted,
On 2017/03/10 10:31:30, Vyacheslav Egorov (Google) wrote:
> ComputeGoodBiasForCidComparison(...)?

Done.

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/flow_graph_compi...
File runtime/vm/flow_graph_compiler_arm.cc (right):

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/flow_graph_compi...
runtime/vm/flow_graph_compiler_arm.cc:1573: if (!is_last_check && !complete &&
count < (total_ic_calls >> 5)) {
On 2017/03/10 10:31:30, Vyacheslav Egorov (Google) wrote:
> Magic constants!
> 
> This is a suspect optimization because we are ignoring `fail` label - which in
> JIT case would be a deopt. 
> 
> Going to megamorphic stub violates assumption that PolymorphicInstanceCall
would
> deoptimize if a mismatched cid is found. So if we propagate types from
> PolymorphicInstanceCalls (treating them as ClassCheck-s) then we will break.
> 
> (We actually already do that in AOT just not in JIT).

Previous behaviour:

* If there are only a few cids we make a PolymorphicInstanceCall and we will
deopt if new cids appear
* If there are too many cids we leave it as an InstanceCall, which generates a
megamorphic call and never deopt

New behaviour:

* Either way we end up here.
* If there are a lot of different cids then we add a fallback megamorphic stub
call and never deopt.

So I think it's pretty much the same.

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/flow_graph_compi...
File runtime/vm/flow_graph_compiler_x64.cc (right):

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/flow_graph_compi...
runtime/vm/flow_graph_compiler_x64.cc:1498: int bias = GetGoodBias(sorted, 127);
On 2017/03/10 10:31:30, Vyacheslav Egorov (Google) wrote:
> magic constant?

I gave it a name, kMaxImmediateInInstruction.  It's the biggest constant you can
put in a short instruction before you have to go tom a 32 bit constant.  On the
RISC chips it's the limit before you have to add an instruction like movw or
even movw/movt to load the constant.

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/flow_graph_inlin...
File runtime/vm/flow_graph_inliner.cc (right):

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/flow_graph_inlin...
runtime/vm/flow_graph_inliner.cc:477: bool TryInliningPoly(intptr_t cid_start,
On 2017/03/10 10:31:30, Vyacheslav Egorov (Google) wrote:
> Can an argument to this function simply be CidRangeTarget?

Done.

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/flow_graph_inlin...
runtime/vm/flow_graph_inliner.cc:1669: intptr_t try_idx =
call_->GetBlock()->try_index();
On 2017/03/10 10:31:30, Vyacheslav Egorov (Google) wrote:
> const intptr_t try_idx

Done.

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/flow_graph_inlin...
runtime/vm/flow_graph_inliner.cc:1697: if (is_last_test && (!test_is_range ||
call_->complete()) &&
On 2017/03/10 10:31:30, Vyacheslav Egorov (Google) wrote:
> Comment above does not reflect reality completely. There are more to this
> condition than written in the comment.

Done.

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/flow_graph_inlin...
runtime/vm/flow_graph_inliner.cc:1702: if (!call_->complete()) {
On 2017/03/10 10:31:30, Vyacheslav Egorov (Google) wrote:
> needs a comment that condition above implies that !test_is_range.

Done.

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/flow_graph_inlin...
runtime/vm/flow_graph_inliner.cc:1963: printf("%s cid %" Pd "-%" Pd ": %" Pd
"/%" Pd
On 2017/03/10 10:31:30, Vyacheslav Egorov (Google) wrote:
> Here and below: This should be THR_Print. Also this calls for a helper because
> CidRangeTarget formatting it repeated multiple times.

Done.

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/intermediate_lan...
File runtime/vm/intermediate_language.h (right):

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/intermediate_lan...
runtime/vm/intermediate_language.h:2808: intptr_t total_ic_count() { return
total_ic_count_; }
On 2017/03/10 10:31:30, Vyacheslav Egorov (Google) wrote:
> This is an extremely confusing name. We need:
> 
> (a) a better name
> (b) some comments on why this is needed as opposed to CallCount() above.
> 
> Please rearrange members in such a way that CallCount() and total_ic_count are
> next to each other.

Done.

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/intermediate_lan...
File runtime/vm/intermediate_language_arm.cc (right):

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/intermediate_lan...
runtime/vm/intermediate_language_arm.cc:6310: if (sorted_ic_data.length() > 4 &&
IsDenseSwitch()) {
On 2017/03/10 10:31:30, Vyacheslav Egorov (Google) wrote:
> What is this magical 4? Is this the same 4 as FLAG_max_polymorphic_checks

Accidental change, reverted.

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/intermediate_lan...
File runtime/vm/intermediate_language_dbc.cc (right):

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/intermediate_lan...
runtime/vm/intermediate_language_dbc.cc:1498: bool using_ranges = false;
On 2017/03/10 10:31:30, Vyacheslav Egorov (Google) wrote:
> Actually we could be smarter about using ranges on DBC, e.g. 
> 
> [1, 2], [5, 5], [10 , 10]
> 
> are better represented as 
> 
> 1, 2, 5, 10
> 
> then range based call. 

It really depends on the frequency with which we have seen 1, 2, 5 and 10.  I
don't have a good idea right now for how to best choose between the two.

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/jit_optimizer.cc
File runtime/vm/jit_optimizer.cc (left):

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/jit_optimizer.cc...
runtime/vm/jit_optimizer.cc:1503: ? FLAG_max_equality_polymorphic_checks
On 2017/03/10 10:31:30, Vyacheslav Egorov (Google) wrote:
> If you killed the code, kill the flag FLAG_max_equality_polymorphic_checks.
> 
> It might be good to blame the file and see which benchmark did we think this
> code helps and remeasure that benchmark. 
> 
> Might be some dart2js corner case. (Similar stuff for hashCode).

Killed the flag.

Original code review has no rationale.  I've kicked off a benchmark run to see. 
dart2js doesn't seem to use strings for hash keys much according to
https://github.com/dart-lang/sdk/issues/26223

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

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/jit_optimizer.cc...
runtime/vm/jit_optimizer.cc:1483: Class& clarse = Class::Handle(Z,
I->class_table()->At(class_id));
On 2017/03/10 10:31:30, Vyacheslav Egorov (Google) wrote:
> please use cls
> 

Done.

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/jit_optimizer.cc...
runtime/vm/jit_optimizer.cc:1494: bool JitOptimizer::TryAddClass(const ICData&
ic_data,
On 2017/03/10 10:31:31, Vyacheslav Egorov (Google) wrote:
> This function is called TryAddClass but it does not actually trying to add
> anything anywere, nor it uses ic_data parameter.

This method was removed.

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/jit_optimizer.cc...
runtime/vm/jit_optimizer.cc:1502: RawClass* raw_class =
I->class_table()->At(class_id);
On 2017/03/10 10:31:30, Vyacheslav Egorov (Google) wrote:
> This seems to almost duplicate the code in the LookupMethodFor(...) maybe
merge
> them together and make LookupMethodFor(...) return false if class does not
> exist.

Done.

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

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/jit_optimizer.h#...
runtime/vm/jit_optimizer.h:55: void TryExpandClassesInIC(const ICData& ic_data);
On 2017/03/10 10:31:31, Vyacheslav Egorov (Google) wrote:
> InICData

Done.

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/jit_optimizer.h#...
runtime/vm/jit_optimizer.h:60: bool TryAddClass(const ICData& ic_data,
On 2017/03/10 10:31:31, Vyacheslav Egorov (Google) wrote:
> TryAddCheck?

Done.

[erikcorry, 2017-03-10 13:36:54]

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/jit_optimizer.cc
File runtime/vm/jit_optimizer.cc (left):

https://codereview.chromium.org/2737303003/diff/1/runtime/vm/jit_optimizer.cc...
runtime/vm/jit_optimizer.cc:1503: ? FLAG_max_equality_polymorphic_checks
On 2017/03/10 13:30:01, erikcorry wrote:
> On 2017/03/10 10:31:30, Vyacheslav Egorov (Google) wrote:
> > If you killed the code, kill the flag FLAG_max_equality_polymorphic_checks.
> > 
> > It might be good to blame the file and see which benchmark did we think this
> > code helps and remeasure that benchmark. 
> > 
> > Might be some dart2js corner case. (Similar stuff for hashCode).
> 
> Killed the flag.
> 
> Original code review has no rationale.  I've kicked off a benchmark run to
see. 
> dart2js doesn't seem to use strings for hash keys much according to
> https://github.com/dart-lang/sdk/issues/26223

I got confused here between the two flags. I'll check this one as well.

[Vyacheslav Egorov (Google), 2017-03-13 11:59:10]

lgtm

https://codereview.chromium.org/2737303003/diff/20001/runtime/vm/flow_graph_c...
File runtime/vm/flow_graph_compiler_x64.cc (right):

https://codereview.chromium.org/2737303003/diff/20001/runtime/vm/flow_graph_c...
runtime/vm/flow_graph_compiler_x64.cc:1440: intptr_t total_ic_calls) {
total_ic_calls -> total_call_count

https://codereview.chromium.org/2737303003/diff/20001/runtime/vm/flow_graph_i...
File runtime/vm/flow_graph_inliner.cc (right):

https://codereview.chromium.org/2737303003/diff/20001/runtime/vm/flow_graph_i...
runtime/vm/flow_graph_inliner.cc:1538: range.cid_start == range.cid_end &&
Maybe CidRangeTarget needs a helper method

range.is_singularity()

or something like that.

https://codereview.chromium.org/2737303003/diff/20001/runtime/vm/flow_graph_i...
runtime/vm/flow_graph_inliner.cc:1691: bool test_is_range = (variant.cid_start
!= variant.cid_end);
try to make more variable cost - this helps readability of such gigantic
functions.

[erikcorry, 2017-03-15 15:08:53]

Description was changed from

==========
Allow dispatch to use a range of Class-ids in tests

Use polymorphic call for all multi-cid call sites
Remove special hashCode code

R=vegorov@google.com
BUG=
==========

to

==========
Allow dispatch to use a range of Class-ids in tests

Use polymorphic call for all multi-cid call sites
Remove special hashCode code

R=vegorov@google.com
BUG=

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

[erikcorry, 2017-03-15 15:08:54]

Committed patchset #2 (id:20001) manually as
ae8e6705c0e1dd624ec45843879294199c11e368 (presubmit successful).

[sra1, 2017-03-15 18:16:36]

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

[sra1, 2017-03-15 18:16:36]

This regresses dart2js compile time by 5%

http://146.148.43.81:8080/Benchmark?benchmark=CompileAngular-BouncyBalls#targ...
Core i5

[Florian Schneider, 2017-03-16 20:31:40]

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

[Florian Schneider, 2017-03-16 20:31:40]

https://codereview.chromium.org/2737303003/diff/20001/runtime/vm/flow_graph_i...
File runtime/vm/flow_graph_inliner.cc (right):

https://codereview.chromium.org/2737303003/diff/20001/runtime/vm/flow_graph_i...
runtime/vm/flow_graph_inliner.cc:1769: RelationalOpInstr* compare_top = new
RelationalOpInstr(
dbc: Have you tried using _classRangeCheck from internal_patch.dart? We use it
for cid-range checks in the AOT compiler.

v <- classRangeCheck(cid, lower, upper)
Branch if StrictCompare (v == true)

And then rely on the next round of inlining to inline the range check.

[rmacnak, 2017-04-06 22:24:52]

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

[rmacnak, 2017-04-06 22:24:52]

https://codereview.chromium.org/2737303003/diff/20001/runtime/vm/jit_optimize...
File runtime/vm/jit_optimizer.cc (right):

https://codereview.chromium.org/2737303003/diff/20001/runtime/vm/jit_optimize...
runtime/vm/jit_optimizer.cc:1494: Z,
Resolver::ResolveDynamicForReceiverClass(cls, name, args_desc));
This lookup introduced a race with the mutator when creating method extractors.
See issue 29230. Proposed fix in https://codereview.chromium.org/2796283006/