dart2js: add initial support for lookup-maps

pkg/compiler/lib/src/js_backend/lookup_map_analysis.dart

+// Copyright (c) 2015, the Dart project authors.  Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+/// Analysis to determine how to generate code for `LookupMap`s.
+library compiler.src.js_backend.lookup_map_analysis;
+
+import '../common/registry.dart' show Registry;
+import '../compiler.dart' show Compiler;
+import '../constants/values.dart' show
+     ConstantValue,
+     ConstructedConstantValue,
+     ListConstantValue,
+     NullConstantValue,
+     TypeConstantValue;
+import '../dart_types.dart' show DartType;
+import '../elements/elements.dart' show Elements, Element, ClassElement,
+     FieldElement, FunctionElement, FunctionSignature;
+import '../enqueue.dart' show Enqueuer;
+import 'js_backend.dart' show JavaScriptBackend;
+import '../dart_types.dart' show DynamicType, InterfaceType;
+
+/// An analysis and optimization to remove unused entries from a `LookupMap`.
+///
+/// `LookupMaps` are defined in `package:lookup_map/lookup_map.dart`. They are
+/// simple maps that contain constant expressions as keys, and that only support
+/// the lookup operation.
+///
+/// This analysis and optimization will tree-shake the contents of the maps by
+/// looking at the program and finding which keys are clearly unused. Not all
+/// constants can be approximated statically, so this optimization is limited to
+/// the following keys:
+///
+///   * Const expressions that can only be created via const constructors. This
+///   excludes primitives, strings, and any const type that overrides the ==
+///   operator.
+///
+///   * Type literals.
+///
+/// Type literals are more complex than const expressions because they can be
+/// created in multiple ways. We can approximate the possible set of keys if we
+/// follow these rules:
+///
+///   * Include all type-literals used explicitly in the code (excluding
+///   obviously the uses that can be removed from LookupMaps)
+///
+///   * Include every single type-literal if a mirror API is used to create

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

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...

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

Good point. done

+///   types (e.g.  ClassMirror.reflectedType).
+///
+///   * Include all allocated types if the program contains `e.runtimeType`
+///   expressions.
+///
+///   * Include all generic-type arguments, if the program uses type
+///   variables in expressions such as `class A<T> { Type get extract => T }`.
+///
+// TODO(sigmund): add support for const expressions, currently this
+// implementation only supports Type literals. To support const expressions we
+// need to change some of the invariants below (e.g. we can no longer use the
+// ClassElement of a type to refer to keys we need to discover).
+// TODO(sigmund): detect uses of mirrors
+class LookupMapAnalysis {
+  /// Reference to [JavaScriptBackend] to be able to enqueue work when we
+  /// discover that a key in a map is potentially used.
+  final JavaScriptBackend backend;
+
+  /// The resolved [ClassElement] associated with `LookupMap`.
+  ClassElement typeLookupMapClass;
+
+  /// The resolved [FieldElement] for `LookupMap._entries`.
+  FieldElement entriesField;
+
+  /// The resolved [FieldElement] for `LookupMap._key`.
+  FieldElement keyField;
+
+  /// The resolved [FieldElement] for `LookupMap._value`.
+  FieldElement valueField;
+
+  /// Constant instances of `LookupMap` and information about them tracked by
+  /// this analysis.
+  final Map<ConstantValue, _LookupMapInfo> _lookupMaps = {};
+
+  /// Types that we have discovered to be in use in the program.
+  final _inUse = new Set<ClassElement>();
+
+  /// Pending work to do if we discover that a new type is in use. For each type
+  /// that we haven't seen, we record the list of lookup-maps that use such type
+  /// as a key.
+  final _pending = <ClassElement, List<_LookupMapInfo>>{};
+
+  /// Whether the backend is currently processing the codegen queue.
+  // TODO(sigmund): is there a better way to do this. Do we need to plumb the
+  // enqueuer on each callback?
+  bool get _inCodegen => backend.compiler.phase == Compiler.PHASE_COMPILING;
+
+  /// Whether to enable some print debugging for this feature.
+  static const _debug = const String.fromEnvironment('lookupMap') == 'debug';

[sra1, 2015/09/02 00:55:24]

maybe _DEBUG ?

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

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.

+
+  /// Whether this analysis and optimization is enabled.
+  bool get _isEnabled {
+    // `tlm==off` kept here to make it easy to test disabling this feature

[sra1, 2015/09/02 00:55:24]

tlm?

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

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

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

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

+    if (const String.fromEnvironment('lookupMap') == 'off') return false;
+    return typeLookupMapClass != null;
+  }
+
+  LookupMapAnalysis(this.backend);

[sra1, 2015/09/02 00:55:24]

Move ctor above _isEnabled

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

Done.

+
+  /// Initializes this analysis by providing the resolver information of
+  /// `LookupMap`.
+  void initRuntimeClass(ClassElement cls) {
+    cls.computeType(backend.compiler);
+    entriesField = cls.lookupMember('_entries');
+    keyField = cls.lookupMember('_key');
+    valueField = cls.lookupMember('_value');
+    // TODO(sigmund): consider inlining nested maps to improve the quality of
+    // the output code.

[sra1, 2015/09/02 00:55:24]

Say what aspect do you think will improve.  Size?  Speed?
Nested maps could be shared, in which case flattening might duplicate info.

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

Done.

+    typeLookupMapClass = cls;
+  }
+
+  /// Whether [constant] is an instance of a `LookupMap`.
+  bool isLookupMap(ConstantValue constant) =>
+      _isEnabled &&
+      constant.isConstructedObject &&
+      (constant as ConstructedConstantValue).type.asRaw().element

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

Maybe use local variable instead of as?

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

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!

+          .isSubclassOf(typeLookupMapClass);
+
+  /// Registers an instance of a lookup-map with the analysis.
+  void registerLookupMapReference(ConstantValue lookupMap) {
+    if (!_isEnabled || !_inCodegen) return;
+    assert(isLookupMap(lookupMap));
+    _lookupMaps.putIfAbsent(lookupMap, () {
+      if (_debug) print('\x1b[32m>>> ${lookupMap.unparse()} \x1b[0m');

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

https://github.com/google/ansicolor-dart :-D

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

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

+      var info = new _LookupMapInfo(
+          lookupMap, entriesField, keyField, valueField);
+      for (ClassElement type in info.unusedEntries.keys.toList()) {

[sra1, 2015/09/02 00:55:24]

Is the toList() copy part of the algorithm?
Yes: say why
No: delete

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

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?

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

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.

+        if (_inUse.contains(type)) {
+          info._markUsed(type, backend);
+        } else {
+          _pending.putIfAbsent(type, () => []).add(info);
+        }
+      }
+      return info;
+    });
+  }
+
+  /// Records that [type] is used in the program, and updates every map that
+  /// has it as a key.
+  void _addUse(ClassElement type, [String debugContext]) {
+    if (_inUse.add(type)) {
+      if (_debug) print('\x1b[33m FYI($debugContext): ${type} \x1b[0m');
+      _pending[type]?.forEach((info) => info._markUsed(type, backend));
+      _pending[type] = [];

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

How about const []?

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

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.

+    }
+  }
+
+  /// Callback from the enqueuer, invoked when [element] is instantiated.
+  void registerInstantiatedClass(ClassElement element) {
+    if (!_isEnabled || !_inCodegen) return;
+    // TODO(sigmund): only add if .runtimeType is ever used
+    _addUse(element, '+class');
+  }
+
+  /// Callback from the enqueuer, invoked when [type] is instantiated.
+  void registerInstantiatedType(InterfaceType type, Registry registry) {
+    if (!_isEnabled || !_inCodegen) return;
+    // TODO(sigmund): only add if .runtimeType is ever used
+    _addUse(type.element, '+type');
+    // TODO(sigmund): only do this when type-argument expressions are used?
+    _addGenerics(type, registry);
+  }
+
+  /// Records generic type arguments in [type], in case they are retrieved and
+  /// returned using a type-argument expression.
+  void _addGenerics(InterfaceType type, Registry registry) {
+    if (!type.isGeneric) return;
+    for (var arg in type.typeArguments) {
+      if (arg is InterfaceType) {
+        _addUse(arg.element, '+generic');
+        // Note: this call was needed to generate correct code for
+        // type_lookup_map/generic_type_test
+        // TODO(sigmund): can we get rid of this?
+        backend.registerInstantiatedConstantType(
+            backend.typeImplementation.rawType, registry);
+        _addGenerics(arg, registry);
+      }
+    }
+  }
+
+  /// Callback from the codegen enqueuer, invoked when a type constant
+  /// corresponding to the [element] is used in the program.
+  void registerTypeConstant(Element element) {
+    if (!_isEnabled || !_inCodegen) return;
+    assert(element.isClass);
+    _addUse(element, '+literal');
+  }
+
+  /// Callback from the backend, invoked when reaching the end of the enqueuing
+  /// process, but before emitting the code. At this moment we have discovered
+  /// all types used in the program and we can tree-shake anything that is
+  /// unused.
+  void onQueueEmpty(Enqueuer enqueuer) {

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

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?

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

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

+    if (!_isEnabled || enqueuer.isResolutionQueue) return;
+    assert(_inCodegen);
+
+    _lookupMaps.values.forEach((info) {
+      // Technically this should be reached only once, but we seem to get a

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

This should be fixed in the calling context...

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

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

+      // second call during `checkQueue`. We set emitted = true to ensure we
+      // only do this once.
+      if (info.emitted) {
+        // TODO(sigmund): check that nothing really changed?
+        return;
+      }
+      info.emitted = true;
+      info._prepareForEmission();
+    });
+
+    if (_debug) {
+      print('done!');
+      _lookupMaps.forEach((original, info) {
+          info.unusedEntries.forEach((k, _) => print('${k.rawType} unused'));
+      });
+    }
+  }
+}
+
+/// Internal information about the entries on a lookup-map.
+class _LookupMapInfo {
+  /// The original reference to the constant value.
+  ///
+  /// This reference will be mutated in place to remove it's entries when the
+  /// map is first seen during codegen, and to restore them (or a subset of
+  /// them) when we have finished discovering which entries are used. This has
+  /// the side-effect that `orignal.getDependencies()` will be empty during
+  /// most of codegen until we are ready to emit the constants. However,
+  /// restoring the entries before emitting code lets us keep the emitter logic
+  /// agnostic of this optimization.
+  final ConstructedConstantValue original;
+
+  /// Resolved field element to lookup the entries list.
+  final FieldElement entriesField;

[sra1, 2015/09/02 00:55:24]

Are these different to the ones in LookupMapAnalysis?
You could pass in LookupMapAnalysis, either to the methods or the constructor.

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

Done.

+
+  /// Resolved field element to lookup the key when the map is built as a
+  /// single-pair.
+  final FieldElement keyField;
+
+  /// Resolved field element to lookup the value whent he map is built as a
+  /// single-pair.
+  final FieldElement valueField;
+
+  /// Whether we have already emitted this constant.
+  bool emitted = false;
+
+  /// Whether the `LookupMap` constant was built using the `LookupMap.pair`
+  /// constructor.
+  bool singlePair;
+
+  /// Entries in the lookup map whose keys have not been seen in the rest of the
+  /// program.
+  Map<ClassElement, ConstantValue> unusedEntries = {};

[sra1, 2015/09/02 00:55:24]

We typically use <ClassElement, ConstantValue>{} to get checking.

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

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

+
+  /// Entries that have been used, and thus will be part of the generated code.
+  Map<ClassElement, ConstantValue> usedEntries = {};
+
+  /// Internal helper to memoize the mapping between map class elements and
+  /// their corresponding type constants.
+  Map<ClassElement, TypeConstantValue> _typeConstants = {};
+
+  _LookupMapInfo(this.original,
+      this.entriesField, this.keyField, this.valueField) {

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

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.

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

Done.

+    ConstantValue key = original.fields[keyField];
+    singlePair = !key.isNull;
+
+    if (singlePair) {
+      ClassElement cls = key.representedType.element;
+      _typeConstants[cls] = key;
+      unusedEntries[cls] = original.fields[valueField];
+
+      // Note: we modify the constant in-place, see comment in [original].
+      original.fields[keyField] = new NullConstantValue();
+      original.fields[valueField] = new NullConstantValue();
+    } else {
+      ListConstantValue list = original.fields[entriesField];
+      List<ConstantValue> keyValuePairs = list.entries;
+      for (int i = 0; i < keyValuePairs.length; i += 2) {
+        TypeConstantValue type = keyValuePairs[i];
+        ClassElement cls = type.representedType.element;
+        if (cls == null || !cls.isClass) {
+          // TODO(sigmund): report an error
+          continue;
+        }
+        _typeConstants[cls] = type;
+        unusedEntries[cls] = keyValuePairs[i + 1];
+      }
+
+      // Note: we modify the constant in-place, see comment in [original].
+      original.fields[entriesField] =
+          new ListConstantValue(list.type, []);
+    }
+  }
+
+  /// Marks that [type] is a key that has been seen, and thus, the corresponding
+  /// entry in this map should be considered reachable.
+  _markUsed(ClassElement type, JavaScriptBackend backend) {
+    assert(!emitted);
+    assert(unusedEntries.containsKey(type));
+    assert(!usedEntries.containsKey(type));
+    ConstantValue constant = unusedEntries.remove(type);
+    usedEntries[type] = constant;
+    backend.registerCompileTimeConstant(constant,
+        backend.compiler.globalDependencies,
+        addForEmission: false);
+  }
+
+  /// Restores [original] to contain all of the entries marked as possibly used.
+  _prepareForEmission() {
+    ListConstantValue originalEntries = original.fields[entriesField];
+    DartType listType = originalEntries.type;
+    List<ConstantValue> keyValuePairs = <ConstantValue>[];
+    usedEntries.forEach((key, value) {
+      keyValuePairs.add(_typeConstants[key]);
+      keyValuePairs.add(value);
+    });
+
+    // Note: we are restoring the entries here, see comment in [original].
+    if (singlePair) {
+      assert (keyValuePairs.length == 0 || keyValuePairs.length == 2);
+      if (keyValuePairs.length == 2) {
+        original.fields[keyField] = keyValuePairs[0];
+        original.fields[valueField] = keyValuePairs[1];
+      }
+    } else {
+      original.fields[entriesField] =
+          new ListConstantValue(listType, keyValuePairs);
+    }
+  }
+}