Use closure tracer to identify closures that are not passed to Function.apply

Extend closure tracer to also trace dynamic tear offs and use the result to identify closures that might be passed to Function.apply

BUG=
R=floitsch@google.com

Committed: https://code.google.com/p/dart/source/detail?r=35057
Reverted: https://code.google.com/p/dart/source/detail?r=35062

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

[herhut, 2014-04-03 08:31:04]

This unfortunately turned into a larger Cl than originally intended. 

Johnni, as we discussed this, could you take a look at the changes to the model?

[karlklose, 2014-04-03 08:37:28]

https://codereview.chromium.org/223403003/diff/1/sdk/lib/_internal/compiler/i...
File sdk/lib/_internal/compiler/implementation/elements/elements.dart (right):

https://codereview.chromium.org/223403003/diff/1/sdk/lib/_internal/compiler/i...
sdk/lib/_internal/compiler/implementation/elements/elements.dart:833: void set
mightBePassedToFunctionApply(bool value);
Please add these to the world: it is a global property of the program and not a
property of the function itself.

[ngeoffray, 2014-04-03 08:49:36]

https://codereview.chromium.org/223403003/diff/1/sdk/lib/_internal/compiler/i...
File sdk/lib/_internal/compiler/implementation/elements/elements.dart (right):

https://codereview.chromium.org/223403003/diff/1/sdk/lib/_internal/compiler/i...
sdk/lib/_internal/compiler/implementation/elements/elements.dart:833: void set
mightBePassedToFunctionApply(bool value);
On 2014/04/03 08:37:28, karlklose wrote:
> Please add these to the world: it is a global property of the program and not
a
> property of the function itself.

Also, as a general principle, you should not touch the element model for backend
purposes. We failed some time at being consistent, but ideally the element model
is something we wanted to be immutable after the resolution phase.

[herhut, 2014-04-03 09:16:01]

On 2014/04/03 08:49:36, ngeoffray wrote:
>
https://codereview.chromium.org/223403003/diff/1/sdk/lib/_internal/compiler/i...
> File sdk/lib/_internal/compiler/implementation/elements/elements.dart (right):
> 
>
https://codereview.chromium.org/223403003/diff/1/sdk/lib/_internal/compiler/i...
> sdk/lib/_internal/compiler/implementation/elements/elements.dart:833: void set
> mightBePassedToFunctionApply(bool value);
> On 2014/04/03 08:37:28, karlklose wrote:
> > Please add these to the world: it is a global property of the program and
not
> a
> > property of the function itself.
> 
> Also, as a general principle, you should not touch the element model for
backend
> purposes. We failed some time at being consistent, but ideally the element
model
> is something we wanted to be immutable after the resolution phase.

This inference touches one of those failures where the backend introduces new
classes for function expressions. Unfortunately (for me), these classes do not
use the element of the original function expression for the call method but
create a new element. This lead to the situation that closures were passed to
apply that the type inference never saw flowing there. I have added the new
[SynthesizedCallMethodElementX] to be able to differentiate real function
elements from these synthesized ones and to also have a reference back to the
original function expression so that I can find the result of type inference. 

I will replace the property on [FunctionElement] by a set in the world.

[herhut, 2014-04-14 08:21:46]

https://codereview.chromium.org/223403003/diff/1/sdk/lib/_internal/compiler/i...
File sdk/lib/_internal/compiler/implementation/elements/elements.dart (right):

https://codereview.chromium.org/223403003/diff/1/sdk/lib/_internal/compiler/i...
sdk/lib/_internal/compiler/implementation/elements/elements.dart:833: void set
mightBePassedToFunctionApply(bool value);
On 2014/04/03 08:37:28, karlklose wrote:
> Please add these to the world: it is a global property of the program and not
a
> property of the function itself.

Done.

https://codereview.chromium.org/223403003/diff/1/sdk/lib/_internal/compiler/i...
sdk/lib/_internal/compiler/implementation/elements/elements.dart:833: void set
mightBePassedToFunctionApply(bool value);
On 2014/04/03 08:37:28, karlklose wrote:
> Please add these to the world: it is a global property of the program and not
a
> property of the function itself.

Done.

[floitsch, 2014-04-14 15:39:37]

LGTM with comments.

https://codereview.chromium.org/223403003/diff/50001/sdk/lib/_internal/compil...
File sdk/lib/_internal/compiler/implementation/inferrer/closure_tracer.dart
(right):

https://codereview.chromium.org/223403003/diff/50001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/inferrer/closure_tracer.dart:14:
tracedElements.forEach((FunctionElement e) {
minor nit: I prefer 
for (FunctionElement e in tracedElements) {
  ...
}

Couldn't you then break out once the inference needs to is abandoned?

https://codereview.chromium.org/223403003/diff/50001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/inferrer/closure_tracer.dart:23:
tracedElements.forEach((FunctionElement e) {
ditto.

https://codereview.chromium.org/223403003/diff/50001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/inferrer/closure_tracer.dart:45:
tracedElements.forEach((FunctionElement e) {
s/e/functionElement/

https://codereview.chromium.org/223403003/diff/50001/sdk/lib/_internal/compil...
File sdk/lib/_internal/compiler/implementation/inferrer/type_graph_inferrer.dart
(right):

https://codereview.chromium.org/223403003/diff/50001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/inferrer/type_graph_inferrer.dart:603:
info.callees.where((e) => e.isFunction() && !e.isSynthesized);
You probably want to cache the computation (unless you think it's efficient to
rerun through all elements). If that's what you want add a comment that this is
intended.

https://codereview.chromium.org/223403003/diff/50001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/inferrer/type_graph_inferrer.dart:604:
trace(elements, new ClosureTracerVisitor(elements, info, this));
Can it happen (frequently) that the elements list is empty? Should we shortcut
here?

https://codereview.chromium.org/223403003/diff/50001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/inferrer/type_graph_inferrer.dart:606:
trace([info.element],
add assert to make sure you have the right type.
Also helps the reader.

https://codereview.chromium.org/223403003/diff/50001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/inferrer/type_graph_inferrer.dart:782:
// We are tearing a function off and thus create a closure.
also add assert for that.
assert(callee.isMethod()) 
or similar.

https://codereview.chromium.org/223403003/diff/50001/sdk/lib/_internal/compil...
File sdk/lib/_internal/compiler/implementation/inferrer/type_graph_nodes.dart
(right):

https://codereview.chromium.org/223403003/diff/50001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/inferrer/type_graph_nodes.dart:76: new
List<TypeInformation>.from([], growable: false);
new List<TypeInformation>(0);

https://codereview.chromium.org/223403003/diff/50001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/inferrer/type_graph_nodes.dart:160:
ApplyableTypeInformation([users, assignments]) : super(users, assignments);
Add types.

https://codereview.chromium.org/223403003/diff/50001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/inferrer/type_graph_nodes.dart:290:
bool get isStable => super.isStable && !isClosurized;
Add comment, why isClosurized has influence on isStable.

https://codereview.chromium.org/223403003/diff/50001/sdk/lib/_internal/compil...
File sdk/lib/_internal/compiler/implementation/world.dart (right):

https://codereview.chromium.org/223403003/diff/50001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/world.dart:291: if (element is
SynthesizedCallMethodElementX) {
What if we have:
===
var f = () => 499;
var f2 = f.call;

Function.apply(f2, [], {})
===

f2 would be a SynthesizedCallMethodElementX, and would be passed to
Function.apply.

Note: it looks like this is currently broken in dart2js.

Add test (unless there is one already).

[herhut, 2014-04-15 10:50:39]

https://codereview.chromium.org/223403003/diff/50001/sdk/lib/_internal/compil...
File sdk/lib/_internal/compiler/implementation/inferrer/closure_tracer.dart
(right):

https://codereview.chromium.org/223403003/diff/50001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/inferrer/closure_tracer.dart:14:
tracedElements.forEach((FunctionElement e) {
On 2014/04/14 15:39:37, floitsch wrote:
> minor nit: I prefer 
> for (FunctionElement e in tracedElements) {
>   ...
> }
> 
> Couldn't you then break out once the inference needs to is abandoned?

Parameters of closurized functions are abandoned during normal inference as we
do not know the context they are used in. This code resumes type inference for
them, as the tracer will compute just that context. For some parameters, e.g.,
those of native functions, we cannot infer types anyway but trust annotations.
Those are marked as non-resumable and thus will remain abandoned.

Even if all parameters of all traced functions do not take part in inference,
tracing is still beneficial to find out whether the closure flows to
Function.apply.

https://codereview.chromium.org/223403003/diff/50001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/inferrer/closure_tracer.dart:23:
tracedElements.forEach((FunctionElement e) {
On 2014/04/14 15:39:37, floitsch wrote:
> ditto.

Done.

https://codereview.chromium.org/223403003/diff/50001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/inferrer/closure_tracer.dart:45:
tracedElements.forEach((FunctionElement e) {
On 2014/04/14 15:39:37, floitsch wrote:
> s/e/functionElement/

Done.

https://codereview.chromium.org/223403003/diff/50001/sdk/lib/_internal/compil...
File sdk/lib/_internal/compiler/implementation/inferrer/type_graph_inferrer.dart
(right):

https://codereview.chromium.org/223403003/diff/50001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/inferrer/type_graph_inferrer.dart:603:
info.callees.where((e) => e.isFunction() && !e.isSynthesized);
On 2014/04/14 15:39:37, floitsch wrote:
> You probably want to cache the computation (unless you think it's efficient to
> rerun through all elements). If that's what you want add a comment that this
is
> intended.

Done.

https://codereview.chromium.org/223403003/diff/50001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/inferrer/type_graph_inferrer.dart:604:
trace(elements, new ClosureTracerVisitor(elements, info, this));
On 2014/04/14 15:39:37, floitsch wrote:
> Can it happen (frequently) that the elements list is empty? Should we shortcut
> here?

The situation where the target is not a function is rather rare. I am only aware
of cases where you do a.foo and foo is a field that holds a closure already. I
have removed the isSynthesized check, as we should rather fail in such cases.
Currently, no synthesized method can become a closure anyway.

https://codereview.chromium.org/223403003/diff/50001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/inferrer/type_graph_inferrer.dart:606:
trace([info.element],
On 2014/04/14 15:39:37, floitsch wrote:
> add assert to make sure you have the right type.
> Also helps the reader.

Done.

https://codereview.chromium.org/223403003/diff/50001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/inferrer/type_graph_inferrer.dart:782:
// We are tearing a function off and thus create a closure.
On 2014/04/14 15:39:37, floitsch wrote:
> also add assert for that.
> assert(callee.isMethod()) 
> or similar.

Done.

https://codereview.chromium.org/223403003/diff/50001/sdk/lib/_internal/compil...
File sdk/lib/_internal/compiler/implementation/inferrer/type_graph_nodes.dart
(right):

https://codereview.chromium.org/223403003/diff/50001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/inferrer/type_graph_nodes.dart:76: new
List<TypeInformation>.from([], growable: false);
On 2014/04/14 15:39:37, floitsch wrote:
> new List<TypeInformation>(0);

Done.

https://codereview.chromium.org/223403003/diff/50001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/inferrer/type_graph_nodes.dart:160:
ApplyableTypeInformation([users, assignments]) : super(users, assignments);
On 2014/04/14 15:39:37, floitsch wrote:
> Add types.

There is no good type for these. They would need to be of type Container but we
do not have that interface. The super class uses

  var /* List|Set */ users;
  var /* List|ParameterAssignments */ assignments;

for the field declarations.

https://codereview.chromium.org/223403003/diff/50001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/inferrer/type_graph_nodes.dart:290:
bool get isStable => super.isStable && !isClosurized;
On 2014/04/14 15:39:37, floitsch wrote:
> Add comment, why isClosurized has influence on isStable.

Done.

https://codereview.chromium.org/223403003/diff/50001/sdk/lib/_internal/compil...
File sdk/lib/_internal/compiler/implementation/world.dart (right):

https://codereview.chromium.org/223403003/diff/50001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/world.dart:291: if (element is
SynthesizedCallMethodElementX) {
On 2014/04/14 15:39:37, floitsch wrote:
> What if we have:
> ===
> var f = () => 499;
> var f2 = f.call;
> 
> Function.apply(f2, [], {})
> ===
> 
> f2 would be a SynthesizedCallMethodElementX, and would be passed to
> Function.apply.

f2 would be a LocalElement, as would be f1. Only the function expression () =>
499 is turned into a new class with a SynthesizedCallMethodElementX that
corresponds to the function expression.

The tracer uses the front-end view. So it will see that the function expression
flows to Function.apply (once the other bug is fixed) and will tag the function
expression accordingly. During code generation, we actually never see that
function expression but only visit the SynthesizedCallMethodElementX. At that
stage, we have to make the link back to the function expression, which is what
this code does.

> Note: it looks like this is currently broken in dart2js.

Filed a bug http://dartbug.com/18238

> Add test (unless there is one already).

I will add a test in the CL for the above bug.

[herhut, 2014-04-15 11:00:47]

Committed patchset #4 manually as r35057 (presubmit successful).

[herhut, 2014-04-22 11:06:17]

Note that the changes to the MapTypeInformation is noise due to a rebase and not
part of the actual change.

Also, to be conservative, I now preserve the use relationship for all nodes
until the inference is completed.

[floitsch, 2014-04-22 12:32:20]

LGTM.
add minimal tests.

https://codereview.chromium.org/223403003/diff/170001/sdk/lib/_internal/compi...
File sdk/lib/_internal/compiler/implementation/inferrer/type_graph_inferrer.dart
(right):

https://codereview.chromium.org/223403003/diff/170001/sdk/lib/_internal/compi...
sdk/lib/_internal/compiler/implementation/inferrer/type_graph_inferrer.dart:687:
type = new NarrowTypeInformation(type,
add test.

[herhut, 2014-04-23 09:32:46]

PTAL. 

Only changes are in patchset 9.

[floitsch, 2014-04-23 17:34:56]

LGTM.
add test for other change.

[herhut, 2014-04-29 09:46:27]

Committed patchset #9 manually as r35518 (presubmit successful).