dart2js: add initial support for lookup-maps

dart2js: add initial support for lookup-maps

R=herhut@google.com, sra@google.com

Committed: https://github.com/dart-lang/sdk/commit/2c660aa2f03e6932a1ab26e9ca69168a2191b2f2

[Siggi Cherem (dart-lang), 2015-08-28 01:08:56]

Patchset #1 (id:1) has been deleted

[Siggi Cherem (dart-lang), 2015-08-28 01:09:54]

sigmund@google.com changed reviewers:
+ sra@google.com

[Siggi Cherem (dart-lang), 2015-08-29 01:39:44]

Patchset #1 (id:20001) has been deleted

[Siggi Cherem (dart-lang), 2015-08-29 01:39:50]

Patchset #1 (id:40001) has been deleted

[Siggi Cherem (dart-lang), 2015-08-29 01:42:41]

sigmund@google.com changed reviewers:
+ johnniwinther@google.com

[Siggi Cherem (dart-lang), 2015-08-29 01:42:41]

Here is an initial implementation of lookup maps. I have implemented the
tree-shaking based on Type keys, but I plan to also add support for other
constant keys, I just feel this is big enough to send on its own and add the
rest later.

For reviewing, I'd recommend looking at lookup_map.dart first.

The lookup_map_test.dart contains unittest, all other tests in dart2js_extra are
just making sure that the output runs correctly, but otherwise are pretty
similar to what is shown in the unittests.

[sra1, 2015-09-02 00:55:25]

LGTM.  Please scrub debug prints and parameters.

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
File pkg/compiler/lib/src/js_backend/lookup_map_analysis.dart (right):

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
pkg/compiler/lib/src/js_backend/lookup_map_analysis.dart:96: static const _debug
= const String.fromEnvironment('lookupMap') == 'debug';
maybe _DEBUG ?

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
pkg/compiler/lib/src/js_backend/lookup_map_analysis.dart:100: // `tlm==off` kept
here to make it easy to test disabling this feature
tlm?

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
pkg/compiler/lib/src/js_backend/lookup_map_analysis.dart:105:
LookupMapAnalysis(this.backend);
Move ctor above _isEnabled

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
pkg/compiler/lib/src/js_backend/lookup_map_analysis.dart:115: // the output
code.
Say what aspect do you think will improve.  Size?  Speed?
Nested maps could be shared, in which case flattening might duplicate info.

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
pkg/compiler/lib/src/js_backend/lookup_map_analysis.dart:134: for (ClassElement
type in info.unusedEntries.keys.toList()) {
Is the toList() copy part of the algorithm?
Yes: say why
No: delete

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
pkg/compiler/lib/src/js_backend/lookup_map_analysis.dart:239: final FieldElement
entriesField;
Are these different to the ones in LookupMapAnalysis?
You could pass in LookupMapAnalysis, either to the methods or the constructor.

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
pkg/compiler/lib/src/js_backend/lookup_map_analysis.dart:258: Map<ClassElement,
ConstantValue> unusedEntries = {};
We typically use <ClassElement, ConstantValue>{} to get checking.

https://codereview.chromium.org/1320503003/diff/60001/pkg/lookup_map/README.md
File pkg/lookup_map/README.md (right):

https://codereview.chromium.org/1320503003/diff/60001/pkg/lookup_map/README.m...
pkg/lookup_map/README.md:10: internaly: if a key is not used elsewhere in the
program, its entry can be
internally

https://codereview.chromium.org/1320503003/diff/60001/pkg/lookup_map/lib/look...
File pkg/lookup_map/lib/lookup_map.dart (right):

https://codereview.chromium.org/1320503003/diff/60001/pkg/lookup_map/lib/look...
pkg/lookup_map/lib/lookup_map.dart:6: library type_lookup_map;
Do we want 'type' in the library name?

https://codereview.chromium.org/1320503003/diff/60001/pkg/lookup_map/lib/look...
pkg/lookup_map/lib/lookup_map.dart:14: /// internaly: if a key is not used
elsewhere in the program, its entry can be
internally

https://codereview.chromium.org/1320503003/diff/60001/pkg/lookup_map/lib/look...
pkg/lookup_map/lib/lookup_map.dart:16: /// semantics in any visible way.
Currently dart2js supports tree-shaking keys
changing the program semantics in any visible way

-?->

changing the program's behaviour.

[herhut, 2015-09-02 12:59:56]

herhut@google.com changed reviewers:
+ herhut@google.com

[herhut, 2015-09-02 12:59:57]

Nice!

lgtm w/ comments

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
File pkg/compiler/lib/src/js_backend/backend.dart (right):

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
pkg/compiler/lib/src/js_backend/backend.dart:997: (constant as
TypeConstantValue).representedType;
Why use as here? I think the usual style is to cast by assignment to a local.

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
File pkg/compiler/lib/src/js_backend/lookup_map_analysis.dart (right):

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
pkg/compiler/lib/src/js_backend/lookup_map_analysis.dart:47: ///   * Include
every single type-literal if a mirror API is used to create
These should be only those classes that are reflectable. This would allow
tree-shaking in lookup maps when MirrorsUsed is used. Just as a remark for a
future implementation...

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
pkg/compiler/lib/src/js_backend/lookup_map_analysis.dart:100: // `tlm==off` kept
here to make it easy to test disabling this feature
On 2015/09/02 00:55:24, sra1 wrote:
> tlm?

I guess this is a left over from type lookup map :)

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
pkg/compiler/lib/src/js_backend/lookup_map_analysis.dart:123: (constant as
ConstructedConstantValue).type.asRaw().element
Maybe use local variable instead of as?

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
pkg/compiler/lib/src/js_backend/lookup_map_analysis.dart:131: if (_debug)
print('\x1b[32m>>> ${lookupMap.unparse()} \x1b[0m');
https://github.com/google/ansicolor-dart :-D

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
pkg/compiler/lib/src/js_backend/lookup_map_analysis.dart:134: for (ClassElement
type in info.unusedEntries.keys.toList()) {
On 2015/09/02 00:55:24, sra1 wrote:
> Is the toList() copy part of the algorithm?
> Yes: say why
> No: delete

I guess this is because _markUsed will update the unusedEntries under the hood.
I don't like this pattern in general. Either the info handles its state or the
outside does but this is mixed. How about passing in a closure to the
constructor which it can then use to create the appropriate state to begin with?

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
pkg/compiler/lib/src/js_backend/lookup_map_analysis.dart:151: _pending[type] =
[];
How about const []?

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
pkg/compiler/lib/src/js_backend/lookup_map_analysis.dart:200: void
onQueueEmpty(Enqueuer enqueuer) {
This is a bad name. In the enqueuer this might be called multiple times, if the
onQueueEmpty call adds new stuff to the queue. At least the resolution enqueuer
iterates that way. However, this should be called once enqueuing is complete, so
maybe name it such?

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
pkg/compiler/lib/src/js_backend/lookup_map_analysis.dart:205: // Technically
this should be reached only once, but we seem to get a
This should be fixed in the calling context...

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
pkg/compiler/lib/src/js_backend/lookup_map_analysis.dart:268: this.entriesField,
this.keyField, this.valueField) {
Nit: I think it would be easier to read if these would not be passed in
separately but as a reference to the backend or analysis. That way it is clearer
that these are not a specific property of this info but just some shared state.

https://codereview.chromium.org/1320503003/diff/60001/pkg/lookup_map/README.md
File pkg/lookup_map/README.md (right):

https://codereview.chromium.org/1320503003/diff/60001/pkg/lookup_map/README.m...
pkg/lookup_map/README.md:12: in any visible way. Currently dart2js supports
tree-shaking keys that are Type
I prefer observable

https://codereview.chromium.org/1320503003/diff/60001/pkg/lookup_map/lib/look...
File pkg/lookup_map/lib/lookup_map.dart (right):

https://codereview.chromium.org/1320503003/diff/60001/pkg/lookup_map/lib/look...
pkg/lookup_map/lib/lookup_map.dart:16: /// semantics in any visible way.
Currently dart2js supports tree-shaking keys
On 2015/09/02 00:55:25, sra1 wrote:
> changing the program semantics in any visible way
> 
> -?->
> 
> changing the program's behaviour.

That is even nicer...

[Siggi Cherem (dart-lang), 2015-09-03 00:44:30]

Thanks for all the comments!

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
File pkg/compiler/lib/src/js_backend/backend.dart (right):

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
pkg/compiler/lib/src/js_backend/backend.dart:997: (constant as
TypeConstantValue).representedType;
On 2015/09/02 12:59:57, herhut wrote:
> Why use as here? I think the usual style is to cast by assignment to a local.

Done.

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
File pkg/compiler/lib/src/js_backend/lookup_map_analysis.dart (right):

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
pkg/compiler/lib/src/js_backend/lookup_map_analysis.dart:47: ///   * Include
every single type-literal if a mirror API is used to create
On 2015/09/02 12:59:57, herhut wrote:
> These should be only those classes that are reflectable. This would allow
> tree-shaking in lookup maps when MirrorsUsed is used. Just as a remark for a
> future implementation...

Good point. done

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
pkg/compiler/lib/src/js_backend/lookup_map_analysis.dart:96: static const _debug
= const String.fromEnvironment('lookupMap') == 'debug';
On 2015/09/02 00:55:24, sra1 wrote:
> maybe _DEBUG ?

I went ahead and removed the debug code. The only think I kept is the summary
printing, but only if the compiler is running in verbose mode.

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
pkg/compiler/lib/src/js_backend/lookup_map_analysis.dart:100: // `tlm==off` kept
here to make it easy to test disabling this feature
On 2015/09/02 12:59:57, herhut wrote:
> On 2015/09/02 00:55:24, sra1 wrote:
> > tlm?
> 
> I guess this is a left over from type lookup map :)

exactly :) - old name. fixed the comment now "lookupMap"

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
pkg/compiler/lib/src/js_backend/lookup_map_analysis.dart:105:
LookupMapAnalysis(this.backend);
On 2015/09/02 00:55:24, sra1 wrote:
> Move ctor above _isEnabled

Done.

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
pkg/compiler/lib/src/js_backend/lookup_map_analysis.dart:115: // the output
code.
On 2015/09/02 00:55:24, sra1 wrote:
> Say what aspect do you think will improve.  Size?  Speed?
> Nested maps could be shared, in which case flattening might duplicate info.

Done.

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
pkg/compiler/lib/src/js_backend/lookup_map_analysis.dart:123: (constant as
ConstructedConstantValue).type.asRaw().element
On 2015/09/02 12:59:57, herhut wrote:
> Maybe use local variable instead of as?

Done - in this case, I realize I can switch the check
`constant.isConstructedObject` into `constnat is ConstructedConstantValue)` and
type propagation handles the code correctly without the cast. Yay!

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
pkg/compiler/lib/src/js_backend/lookup_map_analysis.dart:131: if (_debug)
print('\x1b[32m>>> ${lookupMap.unparse()} \x1b[0m');
On 2015/09/02 12:59:57, herhut wrote:
> https://github.com/google/ansicolor-dart :-D

nice :) - I normally define constnats for it, but I'll delete this debug code
for now.

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
pkg/compiler/lib/src/js_backend/lookup_map_analysis.dart:134: for (ClassElement
type in info.unusedEntries.keys.toList()) {
On 2015/09/02 12:59:57, herhut wrote:
> On 2015/09/02 00:55:24, sra1 wrote:
> > Is the toList() copy part of the algorithm?
> > Yes: say why
> > No: delete
> 
> I guess this is because _markUsed will update the unusedEntries under the
hood.
> I don't like this pattern in general. Either the info handles its state or the
> outside does but this is mixed. How about passing in a closure to the
> constructor which it can then use to create the appropriate state to begin
with?

Correct, it's to avoid the concurrent modification errors. I've added a comment
and refactored it following Stephan's suggestions. This code is now in the info
class below.

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
pkg/compiler/lib/src/js_backend/lookup_map_analysis.dart:151: _pending[type] =
[];
On 2015/09/02 12:59:57, herhut wrote:
> How about const []?

Oh - good point, later on when we discover a new LookupMap we wont even have to
use the pending map. I'll just remove the key entirely instead.

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
pkg/compiler/lib/src/js_backend/lookup_map_analysis.dart:200: void
onQueueEmpty(Enqueuer enqueuer) {
On 2015/09/02 12:59:57, herhut wrote:
> This is a bad name. In the enqueuer this might be called multiple times, if
the
> onQueueEmpty call adds new stuff to the queue. At least the resolution
enqueuer
> iterates that way. However, this should be called once enqueuing is complete,
so
> maybe name it such?

Done - I had copied the name from custom_elements_analysis, which does something
similar :)

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
pkg/compiler/lib/src/js_backend/lookup_map_analysis.dart:205: // Technically
this should be reached only once, but we seem to get a
On 2015/09/02 12:59:57, herhut wrote:
> This should be fixed in the calling context...

Done. I think it's cleaner now. I added an API in backend_api for it

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
pkg/compiler/lib/src/js_backend/lookup_map_analysis.dart:239: final FieldElement
entriesField;
On 2015/09/02 00:55:24, sra1 wrote:
> Are these different to the ones in LookupMapAnalysis?
> You could pass in LookupMapAnalysis, either to the methods or the constructor.

Done.

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
pkg/compiler/lib/src/js_backend/lookup_map_analysis.dart:258: Map<ClassElement,
ConstantValue> unusedEntries = {};
On 2015/09/02 00:55:24, sra1 wrote:
> We typically use <ClassElement, ConstantValue>{} to get checking.

Done, but we should chat more about it, we have a lot of redundancy in our type
annotations.

https://codereview.chromium.org/1320503003/diff/60001/pkg/compiler/lib/src/js...
pkg/compiler/lib/src/js_backend/lookup_map_analysis.dart:268: this.entriesField,
this.keyField, this.valueField) {
On 2015/09/02 12:59:57, herhut wrote:
> Nit: I think it would be easier to read if these would not be passed in
> separately but as a reference to the backend or analysis. That way it is
clearer
> that these are not a specific property of this info but just some shared
state.

Done.

https://codereview.chromium.org/1320503003/diff/60001/pkg/lookup_map/README.md
File pkg/lookup_map/README.md (right):

https://codereview.chromium.org/1320503003/diff/60001/pkg/lookup_map/README.m...
pkg/lookup_map/README.md:10: internaly: if a key is not used elsewhere in the
program, its entry can be
On 2015/09/02 00:55:25, sra1 wrote:
> internally

Done.

https://codereview.chromium.org/1320503003/diff/60001/pkg/lookup_map/README.m...
pkg/lookup_map/README.md:12: in any visible way. Currently dart2js supports
tree-shaking keys that are Type
On 2015/09/02 12:59:57, herhut wrote:
> I prefer observable

Done (w/the latter suggestion)

https://codereview.chromium.org/1320503003/diff/60001/pkg/lookup_map/lib/look...
File pkg/lookup_map/lib/lookup_map.dart (right):

https://codereview.chromium.org/1320503003/diff/60001/pkg/lookup_map/lib/look...
pkg/lookup_map/lib/lookup_map.dart:6: library type_lookup_map;
On 2015/09/02 00:55:25, sra1 wrote:
> Do we want 'type' in the library name?

oops - removed. this was the old name before I decided to generalize this to
other const keys.

https://codereview.chromium.org/1320503003/diff/60001/pkg/lookup_map/lib/look...
pkg/lookup_map/lib/lookup_map.dart:14: /// internaly: if a key is not used
elsewhere in the program, its entry can be
On 2015/09/02 00:55:25, sra1 wrote:
> internally

Done.

https://codereview.chromium.org/1320503003/diff/60001/pkg/lookup_map/lib/look...
pkg/lookup_map/lib/lookup_map.dart:16: /// semantics in any visible way.
Currently dart2js supports tree-shaking keys
On 2015/09/02 12:59:57, herhut wrote:
> On 2015/09/02 00:55:25, sra1 wrote:
> > changing the program semantics in any visible way
> > 
> > -?->
> > 
> > changing the program's behaviour.
> 
> That is even nicer...

Done.

[Siggi Cherem (dart-lang), 2015-09-03 00:49:56]

Patchset #2 (id:80001) has been deleted

[Siggi Cherem (dart-lang), 2015-09-03 00:52:04]

Committed patchset #2 (id:100001) manually as
2c660aa2f03e6932a1ab26e9ca69168a2191b2f2 (presubmit successful).

[Ivan Posva, 2015-09-08 15:52:09]

iposva@google.com changed reviewers:
+ iposva@google.com

[Ivan Posva, 2015-09-08 15:52:10]

DBC -ip

https://codereview.chromium.org/1320503003/diff/100001/pkg/lookup_map/README.md
File pkg/lookup_map/README.md (right):

https://codereview.chromium.org/1320503003/diff/100001/pkg/lookup_map/README....
pkg/lookup_map/README.md:5: map is to retrieve values with a key you already
have.  Expect for lookup, any
Expect or except?

[Siggi Cherem (dart-lang), 2015-09-08 16:00:01]

https://codereview.chromium.org/1320503003/diff/100001/pkg/lookup_map/README.md
File pkg/lookup_map/README.md (right):

https://codereview.chromium.org/1320503003/diff/100001/pkg/lookup_map/README....
pkg/lookup_map/README.md:5: map is to retrieve values with a key you already
have.  Expect for lookup, any
On 2015/09/08 15:52:10, Ivan Posva wrote:
> Expect or except?

good catch, thanks!