Polymorphic inlining for some recognized methods in the optimizing compiler.

Polymorphic inlining for some recognized methods in the optimizing compiler.

The optimizing compiler currently recognizes a certain frequent native methods
like array length or string length and provides an inlined implementation.
Inlining does currently not work for polymorphic call sites of these methods.  
This CL enables also polymorphic inlining in the case of .length getters for
arrays and strings.

1. The method is recognized at flow graph build time. The builder creates
 the body of the method for both compilers (non-optimizing and optimizing).
 Native methods that are not recognized, are translated as before using a NativeCall
 IL instruction.

2. The flow graph inliner handles recognized methods in the same manner as normal methods.
Until now intrinsic and recognized method could not be inlined. This CL enables it.

3. There is no need for an intrinsic assembly implementation because recognized methods
have an IL implementation that does not call into the C++ runtime. I left the intrinsics
in for now, but they can be removed if there is not noticable performance benefit anymore.

4. The inlining heuristics are tweaked in a way that enables more aggressive inlining
of recognized methods: +1 level of inlining depths, call sites of recognized methods are
not counted in the inlining heuristic.

R=kmillikin@google.com, srdjan@google.com

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

[Florian Schneider, 2013-08-12 15:48:14]

This CL handles only recognized .length getters to show the approach.

It simplifies handling of recognized methods because there is no need for
special handling in the optimizer and the intrinsifier anymore, and it enables
polymorphic inlining for them.

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

https://codereview.chromium.org/22839003/diff/1/runtime/vm/flow_graph_builder...
runtime/vm/flow_graph_builder.cc:3238: BuildSaveContext(
Unrelated refactoring.

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

https://codereview.chromium.org/22839003/diff/1/runtime/vm/flow_graph_inliner...
runtime/vm/flow_graph_inliner.cc:398: // max. size observed is 11 (dart2js).
I think this TODO is obsolete.

[srdjan, 2013-08-12 21:49:47]

LGTM with comments.

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

https://codereview.chromium.org/22839003/diff/1/runtime/vm/flow_graph_builder...
runtime/vm/flow_graph_builder.cc:2811: static intptr_t
OffsetForLengthGetter(MethodRecognizer::Kind kind) {
Can we share this with the one in FlowGraphOptimizer?

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

https://codereview.chromium.org/22839003/diff/1/runtime/vm/flow_graph_inliner...
runtime/vm/flow_graph_inliner.cc:304: if (call != NULL &&
call->HasRecognizedTarget()) {
Add ()

https://codereview.chromium.org/22839003/diff/1/runtime/vm/intermediate_langu...
File runtime/vm/intermediate_language.cc (right):

https://codereview.chromium.org/22839003/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.cc:1783: MethodRecognizer::kUnknown);
indent strange, I think it should be:
return ic_data().HasOneTarget() &&
    (MethodRecognizer::RecognizeKind(
        Function::Handle(ic_data().GetTargetAt(0))) !=
            MethodRecognizer::kUnknown);

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

https://codereview.chromium.org/22839003/diff/1/runtime/vm/intrinsifier_arm.c...
runtime/vm/intrinsifier_arm.cc:134: return true;
I would not remove the intrinsics. They make startup quicker (called by
unoptimized code).

[Kevin Millikin (Google), 2013-08-13 11:47:40]

I like the approach.  LGTM with comments addressed.

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

https://codereview.chromium.org/22839003/diff/1/runtime/vm/compiler.cc#newcod...
runtime/vm/compiler.cc:344: propagator.Propagate();
Why?

We compute this five times.  The other four have a comment explaining why they
are called there, this one just has the same comment as the next one.

I'm guessing that it is necessary now for inlining?  If that's the case, can't
it be moved inside if (FLAG_use_inlining)?  (When !FLAG_use_inlining, we
propagate types and apply class ids twice in a row).

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

https://codereview.chromium.org/22839003/diff/1/runtime/vm/flow_graph_builder...
runtime/vm/flow_graph_builder.cc:2834:
MethodRecognizer::RecognizeKind(function);
Fits on the previous line.

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

https://codereview.chromium.org/22839003/diff/1/runtime/vm/flow_graph_inliner...
runtime/vm/flow_graph_inliner.cc:1067: if (!target.is_optimizable()) {
Why remove this check?

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

https://codereview.chromium.org/22839003/diff/1/runtime/vm/flow_graph_inliner...
runtime/vm/flow_graph_inliner.cc:291: void FindRecognizedCallSites(FlowGraph*
graph) {
Instead of a separate function which is a copy of the other one, you could use
the other one and just change the Visit functions to not add at the inlining
depth except the case of recognized calls.

https://codereview.chromium.org/22839003/diff/1/runtime/vm/flow_graph_inliner...
runtime/vm/flow_graph_inliner.cc:659: } else if (inlining_depth_ ==
FLAG_inlining_depth_threshold) {
In any case, even if you keep the separate function, we need a comment that we
inline recognized calls at the inlining limit because they are not 'really'
calls (and don't themselves have calls).

https://codereview.chromium.org/22839003/diff/1/runtime/vm/intermediate_langu...
File runtime/vm/intermediate_language.cc (right):

https://codereview.chromium.org/22839003/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.cc:1783: MethodRecognizer::kUnknown);
On 2013/08/12 21:49:47, srdjan wrote:
> indent strange, I think it should be:
> return ic_data().HasOneTarget() &&
>     (MethodRecognizer::RecognizeKind(
>         Function::Handle(ic_data().GetTargetAt(0))) !=
>             MethodRecognizer::kUnknown);

I think it should be:

if (!ic_data().HasOneTarget()) return false;
const Function& target = Function::Handle(ic_data().GetTargetAt(0));
return
    (MethodRecognizer::RecognizeKind(target) != MethodRecognizer::kUnknown);

;)

[Florian Schneider, 2013-08-14 12:30:24]

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

https://codereview.chromium.org/22839003/diff/1/runtime/vm/compiler.cc#newcod...
runtime/vm/compiler.cc:344: propagator.Propagate();
On 2013/08/13 11:47:40, kmillikin wrote:
> Why?
> 
> We compute this five times.  The other four have a comment explaining why they
> are called there, this one just has the same comment as the next one.
> 
> I'm guessing that it is necessary now for inlining?  If that's the case, can't
> it be moved inside if (FLAG_use_inlining)?  (When !FLAG_use_inlining, we
> propagate types and apply class ids twice in a row).

Without this I get some performance regressions where propagating types before
inlining helps. I'll move it inside the if-statement.

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

https://codereview.chromium.org/22839003/diff/1/runtime/vm/flow_graph_builder...
runtime/vm/flow_graph_builder.cc:2811: static intptr_t
OffsetForLengthGetter(MethodRecognizer::Kind kind) {
On 2013/08/12 21:49:47, srdjan wrote:
> Can we share this with the one in FlowGraphOptimizer?

The one in the FlowGraphOptimizer is gone with this CL.

https://codereview.chromium.org/22839003/diff/1/runtime/vm/flow_graph_builder...
runtime/vm/flow_graph_builder.cc:2834:
MethodRecognizer::RecognizeKind(function);
On 2013/08/13 11:47:40, kmillikin wrote:
> Fits on the previous line.

Done.

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

https://codereview.chromium.org/22839003/diff/1/runtime/vm/flow_graph_inliner...
runtime/vm/flow_graph_inliner.cc:1067: if (!target.is_optimizable()) {
On 2013/08/13 11:47:40, kmillikin wrote:
> Why remove this check?

It's not strictly necessary, but I'll put it back in as an early bailout.

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

https://codereview.chromium.org/22839003/diff/1/runtime/vm/flow_graph_inliner...
runtime/vm/flow_graph_inliner.cc:291: void FindRecognizedCallSites(FlowGraph*
graph) {
On 2013/08/13 11:47:40, kmillikin wrote:
> Instead of a separate function which is a copy of the other one, you could use
> the other one and just change the Visit functions to not add at the inlining
> depth except the case of recognized calls.

Done.

https://codereview.chromium.org/22839003/diff/1/runtime/vm/flow_graph_inliner...
runtime/vm/flow_graph_inliner.cc:304: if (call != NULL &&
call->HasRecognizedTarget()) {
On 2013/08/12 21:49:47, srdjan wrote:
> Add ()

Done.

https://codereview.chromium.org/22839003/diff/1/runtime/vm/flow_graph_inliner...
runtime/vm/flow_graph_inliner.cc:659: } else if (inlining_depth_ ==
FLAG_inlining_depth_threshold) {
On 2013/08/13 11:47:40, kmillikin wrote:
> In any case, even if you keep the separate function, we need a comment that we
> inline recognized calls at the inlining limit because they are not 'really'
> calls (and don't themselves have calls).

Done. I use only one function. Also change CallSites class to not subclass
FlowGraphVisitor.

https://codereview.chromium.org/22839003/diff/1/runtime/vm/intermediate_langu...
File runtime/vm/intermediate_language.cc (right):

https://codereview.chromium.org/22839003/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.cc:1783: MethodRecognizer::kUnknown);
On 2013/08/13 11:47:40, kmillikin wrote:
> On 2013/08/12 21:49:47, srdjan wrote:
> > indent strange, I think it should be:
> > return ic_data().HasOneTarget() &&
> >     (MethodRecognizer::RecognizeKind(
> >         Function::Handle(ic_data().GetTargetAt(0))) !=
> >             MethodRecognizer::kUnknown);
> 
> I think it should be:
> 
> if (!ic_data().HasOneTarget()) return false;
> const Function& target = Function::Handle(ic_data().GetTargetAt(0));
> return
>     (MethodRecognizer::RecognizeKind(target) != MethodRecognizer::kUnknown);
> 
> ;)

Done.

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

https://codereview.chromium.org/22839003/diff/1/runtime/vm/intrinsifier_arm.c...
runtime/vm/intrinsifier_arm.cc:134: return true;
On 2013/08/12 21:49:47, srdjan wrote:
> I would not remove the intrinsics. They make startup quicker (called by
> unoptimized code).

The problem is that we prohibit inlining of intrinsified methods because of
deoptimization. I _think_ we can enable it if we always emit the full
unoptimized body appended to the intrinsic code (make all intrincic-builder
functions return false).

Second, the new unoptimized code for these is only slightly slower: It enters a
stack frame, plus there is some push/pop because of the unoptimized code does
not use registers across instructions. So if the performance benefit is
negligible, I'd rather remove the code. I'll try to get some measurements.

[Florian Schneider, 2013-08-21 11:18:15]

@Kevin: Could you have a quick look at the diff in the intrinsifier* files? I
had to change it to recognize the native method moduloFromInteger instead of
modulo so that after enabling inlining of non-native intrinsics, there is no
performance regression.

[Kevin Millikin (Google), 2013-08-21 12:36:05]

On 2013/08/21 11:18:15, Florian Schneider wrote:
> @Kevin: Could you have a quick look at the diff in the intrinsifier* files? I
> had to change it to recognize the native method moduloFromInteger instead of
> modulo so that after enabling inlining of non-native intrinsics, there is no
> performance regression.

It looks good to me.

[Florian Schneider, 2013-08-21 12:58:30]

Committed patchset #6 manually as r26429 (presubmit successful).