Recursive inlining.

Recursive inlining.

Due to large performance regressions on dart2js the default depth is set to 1, i.e., we only inline the first level of calls by default. The depth can be changed with the inlining_depth_threshold flag.

R=kmillikin@google.com

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

[zerny-google, 2012-10-04 16:37:55]

Hi guys,

Despite regressions on dart2js, we might want to land recursive inlining so it
is available for experimentation. We can put the depth-threshold to 0 (as done
in this CL) so as not to disrupt dart2js until we have a solution for the code
growth/deopt issues.

What do you think?

[srdjan, 2012-10-04 17:06:26]

DBC, and if Kevin is OK with it, I think we should land it.

http://codereview.chromium.org/11029027/diff/1002/runtime/vm/flow_graph_inlin...
File runtime/vm/flow_graph_inliner.cc (right):

http://codereview.chromium.org/11029027/diff/1002/runtime/vm/flow_graph_inlin...
runtime/vm/flow_graph_inliner.cc:102: }
Why not adding VisitInstanceCall as well? Then we could use this to check if the
method is leaf method. Maybe have then two methods: HasInlinableCalls and
HasCalls

http://codereview.chromium.org/11029027/diff/1002/runtime/vm/flow_graph_inlin...
runtime/vm/flow_graph_inliner.cc:148: }
Reset collected_call_sites_ and inlining_call_sites_ to NULL.

http://codereview.chromium.org/11029027/diff/1002/runtime/vm/flow_graph_inlin...
runtime/vm/flow_graph_inliner.cc:272: if (inlining_depth_ <=
FLAG_inlining_depth_threshold) {
The inlining depth threshold is not keeping inlining depth from going above it.
Maybe rename the flag to recursive_inlining_depth_threshold.

[zerny-google, 2012-10-08 11:44:28]

Thanks for the review Srdjan,

I have followups to your comments below, but might have misunderstood your
points. Please let me know if that is the case.

http://codereview.chromium.org/11029027/diff/1002/runtime/vm/flow_graph_inlin...
File runtime/vm/flow_graph_inliner.cc (right):

http://codereview.chromium.org/11029027/diff/1002/runtime/vm/flow_graph_inlin...
runtime/vm/flow_graph_inliner.cc:102: }
On 2012/10/04 17:06:26, srdjan wrote:
> Why not adding VisitInstanceCall as well? Then we could use this to check if
the
> method is leaf method. Maybe have then two methods: HasInlinableCalls and
> HasCalls

The collection of call sites happens after we have applied IC data so, if I
understand correctly, all the remaining (non polymorphic) instance calls are
those with no receiver type information and therefore cannot be inlined. The
identification of leaf methods seems more appropriate earlier in the pipeline
since that information would be useful for inlining too if it were already
computed.

http://codereview.chromium.org/11029027/diff/1002/runtime/vm/flow_graph_inlin...
runtime/vm/flow_graph_inliner.cc:148: }
On 2012/10/04 17:06:26, srdjan wrote:
> Reset collected_call_sites_ and inlining_call_sites_ to NULL.

Done.

http://codereview.chromium.org/11029027/diff/1002/runtime/vm/flow_graph_inlin...
runtime/vm/flow_graph_inliner.cc:272: if (inlining_depth_ <=
FLAG_inlining_depth_threshold) {
On 2012/10/04 17:06:26, srdjan wrote:
> The inlining depth threshold is not keeping inlining depth from going above
it.
> Maybe rename the flag to recursive_inlining_depth_threshold.

Implicitly it is. The flag is an upper bound on the iterations performed in
InlineCalls. The loop termination is separated from the loop in order to avoid
adding call sites to the array which we might not consider inlining.

[srdjan, 2012-10-08 15:31:03]

http://codereview.chromium.org/11029027/diff/1002/runtime/vm/flow_graph_inlin...
File runtime/vm/flow_graph_inliner.cc (right):

http://codereview.chromium.org/11029027/diff/1002/runtime/vm/flow_graph_inlin...
runtime/vm/flow_graph_inliner.cc:102: }
On 2012/10/08 11:44:28, zerny wrote:
> On 2012/10/04 17:06:26, srdjan wrote:
> > Why not adding VisitInstanceCall as well? Then we could use this to check if
> the
> > method is leaf method. Maybe have then two methods: HasInlinableCalls and
> > HasCalls
> 
> The collection of call sites happens after we have applied IC data so, if I
> understand correctly, all the remaining (non polymorphic) instance calls are
> those with no receiver type information and therefore cannot be inlined. The
> identification of leaf methods seems more appropriate earlier in the pipeline
> since that information would be useful for inlining too if it were already
> computed.


Please add something similar to the comment of the class. IMO, 'CallSite' class
name sounds too generic, what it does is not compute call sites but inlineable
call sites.

http://codereview.chromium.org/11029027/diff/1002/runtime/vm/flow_graph_inlin...
runtime/vm/flow_graph_inliner.cc:272: if (inlining_depth_ <=
FLAG_inlining_depth_threshold) {
On 2012/10/08 11:44:28, zerny wrote:
> On 2012/10/04 17:06:26, srdjan wrote:
> > The inlining depth threshold is not keeping inlining depth from going above
> it.
> > Maybe rename the flag to recursive_inlining_depth_threshold.
> 
> Implicitly it is. The flag is an upper bound on the iterations performed in
> InlineCalls. The loop termination is separated from the loop in order to avoid
> adding call sites to the array which we might not consider inlining.

I am looking at it from the point of user running Dart VM. When I run Dart VM
with --inlining_depth_threshold=1, I expect that one level of inlining occurs,
i.e., a value of 0 should disable inlining, then. Maybe rename it some geekier
name, like inlining_iteration_upper_bound?

[zerny-google, 2012-10-09 11:32:50]

Thanks for the feedback.

> > The collection of call sites happens after we have applied IC data so, if I
> > understand correctly, all the remaining (non polymorphic) instance calls are
> > those with no receiver type information and therefore cannot be inlined. The
> > identification of leaf methods seems more appropriate earlier in the
pipeline
> > since that information would be useful for inlining too if it were already
> > computed.
> 
> 
> Please add something similar to the comment of the class. IMO, 'CallSite'
class
> name sounds too generic, what it does is not compute call sites but inlineable
> call sites.

Ok.

> > Implicitly it is. The flag is an upper bound on the iterations performed in
> > InlineCalls. The loop termination is separated from the loop in order to
avoid
> > adding call sites to the array which we might not consider inlining.
> 
> I am looking at it from the point of user running Dart VM. When I run Dart VM
> with --inlining_depth_threshold=1, I expect that one level of inlining occurs,
> i.e., a value of 0 should disable inlining, then. Maybe rename it some geekier
> name, like inlining_iteration_upper_bound?

This CL updates the code to start at 1 instead, thus 0 (or less) will disable
all inlining.

[srdjan, 2012-10-09 16:22:50]

LGTM from me, but please wait for Kevin's LGTM as well.

[Kevin Millikin (Google), 2012-10-10 09:45:25]

LGTM.

http://codereview.chromium.org/11029027/diff/10001/runtime/vm/flow_graph_inli...
File runtime/vm/flow_graph_inliner.cc (right):

http://codereview.chromium.org/11029027/diff/10001/runtime/vm/flow_graph_inli...
runtime/vm/flow_graph_inliner.cc:83: BlockIterator block_it =
graph->postorder_iterator();
I'd rather have this in the for at the cost of an extra line.

[zerny-google, 2012-10-10 13:17:06]

http://codereview.chromium.org/11029027/diff/10001/runtime/vm/flow_graph_inli...
File runtime/vm/flow_graph_inliner.cc (right):

http://codereview.chromium.org/11029027/diff/10001/runtime/vm/flow_graph_inli...
runtime/vm/flow_graph_inliner.cc:83: BlockIterator block_it =
graph->postorder_iterator();
On 2012/10/10 09:45:25, kmillikin wrote:
> I'd rather have this in the for at the cost of an extra line.

Done.