RFC: Resolution based tree-shaking.

Resolution based tree-shaking.

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

[ahe, 2012-06-08 12:29:45]

This is preview. It seems to be close to working now.

[ahe, 2012-06-11 14:42:57]

I'm now able to resolve everything in tests/utils/dummy_compiler_test.dart
before compiling.

I decided to load all interceptors and helpers unconditionally. This only gives
an excess of 27 elements that are resolved but not compiled (not counting the
interceptors and helpers themselves).

[ahe, 2012-06-11 23:14:12]

Please review this CL now. All tests are passing.

[sra1, 2012-06-12 02:25:20]

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
File dart/lib/compiler/implementation/compiler.dart (right):

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/compiler.dart:439: resolved.remove(e);
I'm not sure it is safe to remove elements from a set while iterating over the
set.

[kasperl, 2012-06-12 05:50:12]

LGTM if you address Stephen's concern.

https://chromiumcodereview.appspot.com/10542073/diff/1/dart/lib/compiler/impl...
File dart/lib/compiler/implementation/compiler.dart (right):

https://chromiumcodereview.appspot.com/10542073/diff/1/dart/lib/compiler/impl...
dart/lib/compiler/implementation/compiler.dart:19: resolutionTree =
world.getCachedElements(element);
So getCachedElements has the side-effect that this work item might turn
analyzed?

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
File dart/lib/compiler/implementation/compiler.dart (right):

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/compiler.dart:56: for (var lib in
[compiler.jsHelperLibrary, compiler.interceptorsLibrary]) {
Add a comment that explains that this enqueues all functions in the two
libraries -- or add a helper function ala enqueueAllToplevelFunctionsFrom(lib)?

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/compiler.dart:423: checkQueues() {
Add a high level comment that explains the purpose of this method.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/compiler.dart:478: elements =
resolver.resolve(element);
I think I would use two separate variables for this by calling the first one
'cached' and the other one 'elements'. It feels a bit simpler that way.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/compiler.dart:486: TreeElements result =
world.getCachedElements(element);
Consider a cached/result split here too.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/compiler.dart:608: (beginOffset, endOffset) {
Maybe pull out this closure into a named function declaration instead so its
purpose becomes more obvious?

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
File dart/lib/compiler/implementation/enqueue.dart (right):

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/enqueue.dart:25: final Queue<WorkItem> _queue;
Why did you have to turn this private?

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/enqueue.dart:45: // int allowed =
ElementCategory.VARIABLE | ElementCategory.FUNCTION
There's a lot of commented out code in this method, but no TODO. It isn't clear
what you intent with that is.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
File dart/lib/compiler/implementation/resolver.dart (right):

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/resolver.dart:355:
visitor.compiler.enqueuer.resolution.registerStaticUse(element);
Would visitor.world work?

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/resolver.dart:1140: case "===":
Use ' for string literals for consistency?

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/resolver.dart:1149: if (name === null) return;
Check for name === null before switching on name.stringValue.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
File dart/lib/compiler/implementation/tree/nodes.dart (right):

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/tree/nodes.dart:260: if (argumentsNode ===
null) return -1;
return (argumentsNode === null) ? -1 : argumentsNode.length;

Maybe even use =>?

[ahe, 2012-06-12 06:22:48]

Hi Stephen and Kasper,

Thank you for taking a look. I'll let you know when I have addressed your
comments.

I added a bunch of notes to myself as well.

Cheers,
Peter

https://chromiumcodereview.appspot.com/10542073/diff/1/dart/lib/compiler/impl...
File dart/lib/compiler/implementation/compiler.dart (right):

https://chromiumcodereview.appspot.com/10542073/diff/1/dart/lib/compiler/impl...
dart/lib/compiler/implementation/compiler.dart:19: resolutionTree =
world.getCachedElements(element);
On 2012/06/12 05:50:12, kasperl wrote:
> So getCachedElements has the side-effect that this work item might turn
> analyzed?

getCachedElements does not have side-effects. Assigning to treeElements has the
effect that this work item may "become" analyzed.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
File dart/lib/compiler/implementation/compiler.dart (right):

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/compiler.dart:5: final bool
REPORT_EXCESS_RESOLUTION = false;
Document this.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/compiler.dart:30: abstract void
enqueueHelpers(Enqueuer world);
Implement in dart backend.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/compiler.dart:439: resolved.remove(e);
On 2012/06/12 02:25:20, sra1 wrote:
> I'm not sure it is safe to remove elements from a set while iterating over the
> set.

I thought about that when writing the code. Nothing seemed to break, so I
assumed it was safe. The documentation of Set.remove does not mention that it
isn't safe. I'll change the code, assuming that it isn't safe and file a bug to
update the documentation of Set.remove.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/compiler.dart:466: if (element is
AbstractFieldElement) {
Clean up these and the following special cases.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/compiler.dart:606: return
SourceSpan.withOffsets(
This inlines part of spanFromTokens to define the uri. Consider an optional
argument.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
File dart/lib/compiler/implementation/elements/elements.dart (right):

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/elements/elements.dart:206: if (isMember()) {
!isTopLevel()

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
File dart/lib/compiler/implementation/enqueue.dart (right):

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/enqueue.dart:25: final Queue<WorkItem> _queue;
Make public again.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/enqueue.dart:45: // int allowed =
ElementCategory.VARIABLE | ElementCategory.FUNCTION
Remove comments.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/enqueue.dart:60: if (!isFirstQueue && elements
=== null) {
Remove this dead code.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/enqueue.dart:71: if (cls.isInterface()) throw
'$cls is an interface';
Remove this.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
File dart/lib/compiler/implementation/resolver.dart (right):

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/resolver.dart:355:
visitor.compiler.enqueuer.resolution.registerStaticUse(element);
visitor.world.

[ahe, 2012-06-12 10:56:11]

Addressed comments.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
File dart/lib/compiler/implementation/compiler.dart (right):

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/compiler.dart:5: final bool
REPORT_EXCESS_RESOLUTION = false;
On 2012/06/12 06:22:49, ahe wrote:
> Document this.

Done.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/compiler.dart:30: abstract void
enqueueHelpers(Enqueuer world);
On 2012/06/12 06:22:49, ahe wrote:
> Implement in dart backend.

Done.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/compiler.dart:56: for (var lib in
[compiler.jsHelperLibrary, compiler.interceptorsLibrary]) {
On 2012/06/12 05:50:12, kasperl wrote:
> Add a comment that explains that this enqueues all functions in the two
> libraries -- or add a helper function ala
enqueueAllToplevelFunctionsFrom(lib)?

Done.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/compiler.dart:423: checkQueues() {
On 2012/06/12 05:50:12, kasperl wrote:
> Add a high level comment that explains the purpose of this method.

Done.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/compiler.dart:439: resolved.remove(e);
On 2012/06/12 06:22:49, ahe wrote:
> On 2012/06/12 02:25:20, sra1 wrote:
> > I'm not sure it is safe to remove elements from a set while iterating over
the
> > set.
> 
> I thought about that when writing the code. Nothing seemed to break, so I
> assumed it was safe. The documentation of Set.remove does not mention that it
> isn't safe. I'll change the code, assuming that it isn't safe and file a bug
to
> update the documentation of Set.remove. 

Done.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/compiler.dart:466: if (element is
AbstractFieldElement) {
On 2012/06/12 06:22:49, ahe wrote:
> Clean up these and the following special cases.

That doesn't work :-(

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/compiler.dart:478: elements =
resolver.resolve(element);
On 2012/06/12 05:50:12, kasperl wrote:
> I think I would use two separate variables for this by calling the first one
> 'cached' and the other one 'elements'. It feels a bit simpler that way.

I don't see the benefit.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/compiler.dart:486: TreeElements result =
world.getCachedElements(element);
On 2012/06/12 05:50:12, kasperl wrote:
> Consider a cached/result split here too.

Done. Well, I considered it :-)

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/compiler.dart:606: return
SourceSpan.withOffsets(
On 2012/06/12 06:22:49, ahe wrote:
> This inlines part of spanFromTokens to define the uri. Consider an optional
> argument.

Done.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/compiler.dart:608: (beginOffset, endOffset) {
On 2012/06/12 05:50:12, kasperl wrote:
> Maybe pull out this closure into a named function declaration instead so its
> purpose becomes more obvious?

Done.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
File dart/lib/compiler/implementation/elements/elements.dart (right):

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/elements/elements.dart:206: if (isMember()) {
On 2012/06/12 06:22:49, ahe wrote:
> !isTopLevel()

Done.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
File dart/lib/compiler/implementation/enqueue.dart (right):

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/enqueue.dart:25: final Queue<WorkItem> _queue;
On 2012/06/12 05:50:12, kasperl wrote:
> Why did you have to turn this private?

Temporary refactoring aid, reverted.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/enqueue.dart:25: final Queue<WorkItem> _queue;
On 2012/06/12 06:22:49, ahe wrote:
> Make public again.

Done.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/enqueue.dart:45: // int allowed =
ElementCategory.VARIABLE | ElementCategory.FUNCTION
On 2012/06/12 05:50:12, kasperl wrote:
> There's a lot of commented out code in this method, but no TODO. It isn't
clear
> what you intent with that is.

Done.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/enqueue.dart:45: // int allowed =
ElementCategory.VARIABLE | ElementCategory.FUNCTION
On 2012/06/12 06:22:49, ahe wrote:
> Remove comments.

Done.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/enqueue.dart:60: if (!isFirstQueue && elements
=== null) {
On 2012/06/12 06:22:49, ahe wrote:
> Remove this dead code.

Done.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/enqueue.dart:71: if (cls.isInterface()) throw
'$cls is an interface';
On 2012/06/12 06:22:49, ahe wrote:
> Remove this.

Turned into an internal error.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
File dart/lib/compiler/implementation/resolver.dart (right):

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/resolver.dart:355:
visitor.compiler.enqueuer.resolution.registerStaticUse(element);
On 2012/06/12 05:50:12, kasperl wrote:
> Would visitor.world work?

Done.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/resolver.dart:355:
visitor.compiler.enqueuer.resolution.registerStaticUse(element);
On 2012/06/12 06:22:49, ahe wrote:
> visitor.world.

Done.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/resolver.dart:1140: case "===":
On 2012/06/12 05:50:12, kasperl wrote:
> Use ' for string literals for consistency?

Done.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/resolver.dart:1149: if (name === null) return;
On 2012/06/12 05:50:12, kasperl wrote:
> Check for name === null before switching on name.stringValue.

Removed.

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
File dart/lib/compiler/implementation/tree/nodes.dart (right):

https://chromiumcodereview.appspot.com/10542073/diff/8001/dart/lib/compiler/i...
dart/lib/compiler/implementation/tree/nodes.dart:260: if (argumentsNode ===
null) return -1;
On 2012/06/12 05:50:12, kasperl wrote:
> return (argumentsNode === null) ? -1 : argumentsNode.length;
> 
> Maybe even use =>?

Done.

[ahe, 2012-06-12 12:30:21]

I had to make a few tweaks to get the unit tests to pass. I plan to submit the
code shortly, but please do take look at the last patch set.

[ngeoffray, 2012-06-12 12:44:14]

LGTM

https://chromiumcodereview.appspot.com/10542073/diff/8002/dart/lib/compiler/i...
File dart/lib/compiler/implementation/compiler.dart (right):

https://chromiumcodereview.appspot.com/10542073/diff/8002/dart/lib/compiler/i...
dart/lib/compiler/implementation/compiler.dart:435: * processing the quese).
Also compute the number of methods that
quese -> queues

https://chromiumcodereview.appspot.com/10542073/diff/8002/dart/lib/compiler/i...
dart/lib/compiler/implementation/compiler.dart:481: if (element is
AbstractFieldElement) {
Maybe add this check together with the allowed check line 486.

https://chromiumcodereview.appspot.com/10542073/diff/8002/dart/lib/compiler/i...
dart/lib/compiler/implementation/compiler.dart:513: if (world !==
enqueuer.codegen) return null;
Can we actually prevent this situation? Or is that too cumbersome?

https://chromiumcodereview.appspot.com/10542073/diff/8002/dart/lib/compiler/i...
File dart/lib/compiler/implementation/enqueue.dart (right):

https://chromiumcodereview.appspot.com/10542073/diff/8002/dart/lib/compiler/i...
dart/lib/compiler/implementation/enqueue.dart:37: bool get isFirstQueue() =>
compiler.enqueuer.resolution === this;
isResolutionQueue?

https://chromiumcodereview.appspot.com/10542073/diff/8002/dart/lib/compiler/i...
File dart/lib/compiler/implementation/resolver.dart (right):

https://chromiumcodereview.appspot.com/10542073/diff/8002/dart/lib/compiler/i...
dart/lib/compiler/implementation/resolver.dart:1090: if (target === null)
handleDynamicSend(node);
handleDynamicSend -> registerDynamicSend ?

[ahe, 2012-06-12 18:47:13]

Thank you, Nicolas!

Comments addressed in the next CL:
https://chromiumcodereview.appspot.com/10537129/

https://chromiumcodereview.appspot.com/10542073/diff/8002/dart/lib/compiler/i...
File dart/lib/compiler/implementation/compiler.dart (right):

https://chromiumcodereview.appspot.com/10542073/diff/8002/dart/lib/compiler/i...
dart/lib/compiler/implementation/compiler.dart:435: * processing the quese).
Also compute the number of methods that
On 2012/06/12 12:44:14, ngeoffray wrote:
> quese -> queues

Done.

https://chromiumcodereview.appspot.com/10542073/diff/8002/dart/lib/compiler/i...
dart/lib/compiler/implementation/compiler.dart:481: if (element is
AbstractFieldElement) {
On 2012/06/12 12:44:14, ngeoffray wrote:
> Maybe add this check together with the allowed check line 486.

Done.

https://chromiumcodereview.appspot.com/10542073/diff/8002/dart/lib/compiler/i...
dart/lib/compiler/implementation/compiler.dart:513: if (world !==
enqueuer.codegen) return null;
On 2012/06/12 12:44:14, ngeoffray wrote:
> Can we actually prevent this situation? Or is that too cumbersome?

I'm not sure I understand your question.

https://chromiumcodereview.appspot.com/10542073/diff/8002/dart/lib/compiler/i...
File dart/lib/compiler/implementation/enqueue.dart (right):

https://chromiumcodereview.appspot.com/10542073/diff/8002/dart/lib/compiler/i...
dart/lib/compiler/implementation/enqueue.dart:37: bool get isFirstQueue() =>
compiler.enqueuer.resolution === this;
On 2012/06/12 12:44:14, ngeoffray wrote:
> isResolutionQueue?

Done.

https://chromiumcodereview.appspot.com/10542073/diff/8002/dart/lib/compiler/i...
File dart/lib/compiler/implementation/resolver.dart (right):

https://chromiumcodereview.appspot.com/10542073/diff/8002/dart/lib/compiler/i...
dart/lib/compiler/implementation/resolver.dart:1090: if (target === null)
handleDynamicSend(node);
On 2012/06/12 12:44:14, ngeoffray wrote:
> handleDynamicSend -> registerDynamicSend ?

Done.

[ngeoffray, 2012-06-13 07:31:57]

https://chromiumcodereview.appspot.com/10542073/diff/8002/dart/lib/compiler/i...
File dart/lib/compiler/implementation/compiler.dart (right):

https://chromiumcodereview.appspot.com/10542073/diff/8002/dart/lib/compiler/i...
dart/lib/compiler/implementation/compiler.dart:513: if (world !==
enqueuer.codegen) return null;
On 2012/06/12 18:47:13, ahe wrote:
> On 2012/06/12 12:44:14, ngeoffray wrote:
> > Can we actually prevent this situation? Or is that too cumbersome?
> 
> I'm not sure I understand your question.

It does not feel right that the resolver queue ends up being mixed with the
codegen method in compiler. But that's probably because of how the pipeline is
structured.

[ahe, 2012-06-13 08:20:41]

https://chromiumcodereview.appspot.com/10542073/diff/8002/dart/lib/compiler/i...
File dart/lib/compiler/implementation/compiler.dart (right):

https://chromiumcodereview.appspot.com/10542073/diff/8002/dart/lib/compiler/i...
dart/lib/compiler/implementation/compiler.dart:513: if (world !==
enqueuer.codegen) return null;
On 2012/06/13 07:31:57, ngeoffray wrote:
> On 2012/06/12 18:47:13, ahe wrote:
> > On 2012/06/12 12:44:14, ngeoffray wrote:
> > > Can we actually prevent this situation? Or is that too cumbersome?
> > 
> > I'm not sure I understand your question.
> 
> It does not feel right that the resolver queue ends up being mixed with the
> codegen method in compiler. But that's probably because of how the pipeline is
> structured.

I have some ideas for cleaning this up. If enqueuer.codegen and
enqueuer.resolution were slightly different classes (or initialized
differently), then we could probably change WorkItem.run, analyze, and codegen
to be simpler.