Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

dart2js: goal directed inlining #9757

Open
rakudrama opened this issue Apr 8, 2013 · 23 comments
Open

dart2js: goal directed inlining #9757

rakudrama opened this issue Apr 8, 2013 · 23 comments
Assignees
Labels
area-web Issues related to Dart Web. P2 A bug or feature request we're likely to work on type-enhancement A request for a change that isn't a bug web-dart2js

Comments

@rakudrama
Copy link
Member

dart2js is doing low-impact inlining.

r20909

      this._liblib9$_timer = $.Timer_Timer($.Duration_16000, this._liblib9$_step$0());

r20929

      t1 = this._liblib10$_step$0();
      milliseconds = $.Duration_16000.get$inMilliseconds();
      if (milliseconds < 0)
        milliseconds = 0;
      this._liblib10$_timer = $.TimerImpl$(milliseconds, t1);

There is almost no benefit from this inlining - it avoids one call that wraps two others at considerable increase in code size. dart2js should not have bothered with this inlining - the JavaScript engines should be able to do it.

But this inlining could be a lot better if get$inMilliseconds was also inlined. It happens to be a pure function of a field of a constant. It should be possible to do more inlining and reduce the code to

      this._liblib10$_timer = $.TimerImpl$(16, this._liblib10$_step$0());

dart2js should avoid inlining unless it can prove it leads to subsequent optimizations that can't be expected of a good JavaScript engine.

In summary, dart2js should inline when:

  1. The inlining generates smaller or same sized code as the original call.
  2. All call sites are inlined and in aggregate the code size is smaller (a subcase of this is inlining a function that has one reference).
  3. There is sure to be a benefit of inlining not available from JavaScript inlining.
@kasperl
Copy link

kasperl commented Apr 22, 2013

Added this to the Later milestone.

@kasperl
Copy link

kasperl commented May 23, 2013

Added TriageForM5 label.

@kasperl
Copy link

kasperl commented May 28, 2013

Removed TriageForM5 label.

@blois
Copy link
Contributor

blois commented Jun 4, 2013

This really harms generated code readability, I'm spending a decent amount of time just trying to piece together the generated code.

In debugging some code, I see code such as element.nodes.firstChild getting inlined 50+ times

    instance2.get$nodes;
    result = new $._ChildNodeListLazy(instance2)._this.firstChild;
    if (result == null)
      $.throwExpression(new $.StateError("No elements"));

In general the generated code appears to be ~2x more lines and much of this appears to be unnecessary.

@rakudrama
Copy link
Member Author

I'm suffering in a similar way.
I want to put a breakpoint on a constructor but it has been inlined to 5 lines of code on 30 places.

@kasperl
Copy link

kasperl commented Jun 5, 2013

Okay, you've convinced me that this is something we really need to fix now!


Set owner to @kasperl.
Removed this from the Later milestone.
Added this to the M5 milestone.
Added Accepted label.

@kasperl
Copy link

kasperl commented Jun 18, 2013

Removed this from the M5 milestone.
Added this to the M6 milestone.

@larsbak
Copy link

larsbak commented Aug 28, 2013

Removed this from the M6 milestone.
Added this to the M7 milestone.

@kasperl
Copy link

kasperl commented Oct 2, 2013

Removed this from the M7 milestone.
Added this to the M8 milestone.

@peter-ahe-google
Copy link
Contributor

Issue #15070 has been merged into this issue.

@kasperl
Copy link

kasperl commented Feb 21, 2014

Set owner to @floitschG.

@kasperl
Copy link

kasperl commented Jun 4, 2014

Removed this from the M8 milestone.
Added this to the 1.6 milestone.

@kasperl
Copy link

kasperl commented Jul 10, 2014

Removed this from the 1.6 milestone.
Added Oldschool-Milestone-1.6 label.

@kasperl
Copy link

kasperl commented Aug 4, 2014

Removed Oldschool-Milestone-1.6 label.

@rakudrama
Copy link
Member Author

Another example of the cost of excessive inlining:

Run: tools/test.py -mrelease -cdart2js -rd8 pkg/csslib
The size of
out/ReleaseIA32/generated_compilations/dart2js/pkg_csslib_test_declaration_test/out.js
is 926764

If inlining is disabled, the size is 804803

@rakudrama
Copy link
Member Author

Another example:

  final int _duration;

  const Duration({int days: 0,
                  int hours: 0,
                  int minutes: 0,
                  int seconds: 0,
                  int milliseconds: 0,
                  int microseconds: 0})
      : _duration = days * MICROSECONDS_PER_DAY +
                    hours * MICROSECONDS_PER_HOUR +
                    minutes * MICROSECONDS_PER_MINUTE +
                    seconds * MICROSECONDS_PER_SECOND +
                    milliseconds * MICROSECONDS_PER_MILLISECOND +
                    microseconds;

  /**
   * Adds this Duration and [other] and
   * returns the sum as a new Duration object.
   */
  Duration operator +(Duration other) {
    return new Duration(microseconds: _duration + other._duration);
  }

Most call sites use one named argument, like the one inside Duration.+
dart2js is too chicken to inline the constructor as it stands because it looks like the inlined code could be large.

This is an example where it would be worth generating specializations, doing reducing optimizations on the specializations, and then inlining the specializations when it becomes clear that most of the code is optimized away.

It would be pretty challenging to come up with simple heuristics for this without the help of a specializer.

Manually forcing inlining gives much better code for Duration arithmetic.

@floitschG
Copy link
Contributor

cc @kmillikin.

@floitschG
Copy link
Contributor

Set owner to @kmillikin.
Added Triaged label.

@rakudrama
Copy link
Member Author

Here is another example of low-impact inlining of the JSSyntaxRegExp, in combination with non-sharing of string literals, is quite large

        t1 = new H.JSSyntaxRegExp("rgb((\d{1,3}),\s*(\d{1,3}),\s*(\d{1,3}))", H.JSSyntaxRegExp_makeNative("rgb((\d{1,3}),\s*(\d{1,3}),\s*(\d{1,3}))", false, true, false), null, null).firstMatch$1(color)._match;

Simply not inlining would be better:

        t1 = H.JSSyntaxRegExp$("rgb((\d{1,3}),\s*(\d{1,3}),\s*(\d{1,3}))", false, true).firstMatch$1(color)._match;

@kevmoo kevmoo added P2 A bug or feature request we're likely to work on and removed triaged labels Feb 29, 2016
@kevmoo kevmoo added type-enhancement A request for a change that isn't a bug and removed Priority-Medium labels Mar 1, 2016
@rakudrama
Copy link
Member Author

A heuristic that would work in a subset of the Duration cases is the following:

  • inline calls to const constructors from the new keyword all the inputs happen to be constants. We are pretty much guaranteed to constant-fold down the the allocation.

@matanlurey
Copy link
Contributor

This is probably one of AngularDart's top 3 concerns today.

@MichaelRFairhurst
Copy link
Contributor

Looked at the inlining logic a bit, and it seems like this could be broken down into a few sub-issues:

  • add a true inlining heuristic (it currently only considers "max size"): estimate code size of call site and inline if larger than the call body
  • always inline const since const is always foldable
  • add speculative inlining: expand what is inlined and measure the result, throw away if code size is increased

I'd perhaps be able to take a look at the first two. The third is obviously a bit trickier

@rakudrama
Copy link
Member Author

We have stopped development on the Ast based pipeline and are working on the Kernel based pipeline. You are welcome to play with the Ast based pipeline, but be aware that this is now in maintenance mode until we delete it. It is also difficult to work with the Ast for inlining heuristics (a.b could be a library prefix, getter call, or field access - what you call a 'true' heuristic might be infeasible).

For the Kernel inlining - once everything is working with no inlining we will re-implement inlining. Initially we will implement inlining that is similar to the current inlining (i.e. during SSA construction, but with slightly better heuristics since the inlining candidate is available in a more useful form). We will do it this way because we believe we can get inlining to parity with the Ast pipeline quickly (so we can switch over and delete code). Then we will consider how to reimplement inlining. Deferred inlining will require substantial work on the SSA representation.

My experience is that nothing turns out exactly as expected, so please report back any experiments you try.

One example is that it appears that one should inline new calls to const constructors with constant arguments, but this is not always true. For example, a super- constructor might fill in many fields that are not parameters of the constructor, leading to many copies of the default values at the call sites that would not have occurred without inlining. This was not obvious to me until I tried it :-)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
area-web Issues related to Dart Web. P2 A bug or feature request we're likely to work on type-enhancement A request for a change that isn't a bug web-dart2js
Projects
None yet
Development

No branches or pull requests