Update defer loading algorithm:

pkg/compiler/lib/src/deferred_load.dart

Index: pkg/compiler/lib/src/deferred_load.dart
diff --git a/pkg/compiler/lib/src/deferred_load.dart b/pkg/compiler/lib/src/deferred_load.dart
index 43ad9971fae26dd65f4555cb0f57186685f3d02e..95633ad1b41f004de1470e826b2d7cc055967881 100644
--- a/pkg/compiler/lib/src/deferred_load.dart
+++ b/pkg/compiler/lib/src/deferred_load.dart
@@ -4,6 +4,8 @@
 
 library deferred_load;
 
+import 'dart:collection' show Queue;
+
 import 'common/tasks.dart' show CompilerTask;
 import 'common.dart';
 import 'compiler.dart' show Compiler;
@@ -54,35 +56,43 @@ import 'world.dart' show ClosedWorld;
 /// Whenever a deferred Element is shared between several deferred imports it is
 /// in an output unit with those imports in the [imports] Set.
 ///
-/// OutputUnits are equal if their [imports] are equal.
-class OutputUnit {
-  /// The deferred imports that will load this output unit when one of them is
-  /// loaded.
-  final Setlet<_DeferredImport> imports = new Setlet<_DeferredImport>();
-
+/// We never create two OutputUnits sharing the same set of [imports].
+class OutputUnit implements Comparable<OutputUnit> {
   /// `true` if this output unit is for the main output file.
   final bool isMainOutput;
 
   /// A unique name representing this [OutputUnit].
-  String name;
-
-  OutputUnit({this.isMainOutput: false});
-
-  String toString() => "OutputUnit($name)";
-
-  bool operator ==(other) {
-    return other is OutputUnit &&
-        imports.length == other.imports.length &&
-        imports.containsAll(other.imports);
-  }
-
-  int get hashCode {
-    int sum = 0;
-    for (_DeferredImport import in imports) {
-      sum = (sum + import.hashCode) & 0x3FFFFFFF; // Stay in 30 bit range.
+  final String name;
+
+  /// The deferred imports that use the elements in this output unit.
+  final Set<ImportElement> _imports;
+
+  OutputUnit(this.isMainOutput, this.name, this._imports);
+
+  int compareTo(OutputUnit other) {
+    if (identical(this, other)) return 0;
+    if (isMainOutput && !other.isMainOutput) return -1;
+    if (!isMainOutput && other.isMainOutput) return 1;
+    var size = _imports.length;
+    var otherSize = other._imports.length;
+    if (size != otherSize) return size.compareTo(otherSize);
+    var imports = _imports.toList();
+    var otherImports = other._imports.toList();
+    for (var i = 0; i < size; i++) {
+      if (imports[i] == otherImports[i]) continue;
+      var a = imports[i].uri.path;
+      var b = otherImports[i].uri.path;
+      var cmp = a.compareTo(b);
+      if (cmp != 0) return cmp;
     }
-    return sum;
+    // TODO(sigmund): make compare stable.  If we hit this point, all imported
+    // libraries are the same, however [this] and [other] use different deferred
+    // imports in the program. We can make this stable if we sort based on the
+    // deferred imports themselves (e.g. their declaration location).
+    return name.compareTo(other.name);
   }
+
+  String toString() => "OutputUnit($name, $_imports)";
 }
 
 /// For each deferred import, find elements and constants to be loaded when that
@@ -96,15 +106,12 @@ class DeferredLoadTask extends CompilerTask {
   ClassElement get deferredLibraryClass =>
       compiler.resolution.commonElements.deferredLibraryClass;
 
-  /// A synthetic import representing the loading of the main program.
-  final _DeferredImport _fakeMainImport = const _DeferredImport();
-
   /// The OutputUnit that will be loaded when the program starts.
-  final OutputUnit mainOutputUnit = new OutputUnit(isMainOutput: true);
+  OutputUnit mainOutputUnit;
 
   /// A set containing (eventually) all output units that will result from the
   /// program.
-  final Set<OutputUnit> allOutputUnits = new Set<OutputUnit>();
+  final List<OutputUnit> allOutputUnits = new List<OutputUnit>();
 
   /// Will be `true` if the program contains deferred libraries.
   bool isProgramSplit = false;
@@ -123,42 +130,35 @@ class DeferredLoadTask extends CompilerTask {
 
   /// A cache of the result of calling `computeImportDeferName` on the keys of
   /// this map.
-  final Map<_DeferredImport, String> importDeferName =
-      <_DeferredImport, String>{};
+  final Map<ImportElement, String> _importDeferName = <ImportElement, String>{};
 
   /// A mapping from elements and constants to their output unit. Query this via
   /// [outputUnitForElement]
-  final Map<Element, OutputUnit> _elementToOutputUnit =
-      new Map<Element, OutputUnit>();
+  final Map<Entity, ImportSet> _elementToSet = new Map<Entity, ImportSet>();
 
   /// A mapping from constants to their output unit. Query this via
   /// [outputUnitForConstant]
-  final Map<ConstantValue, OutputUnit> _constantToOutputUnit =
-      new Map<ConstantValue, OutputUnit>();
+  final Map<ConstantValue, ImportSet> _constantToSet =
+      new Map<ConstantValue, ImportSet>();
 
-  /// All the imports with a [DeferredLibrary] annotation, mapped to the
-  /// [LibraryElement] they import.
-  /// The main library is included in this set for convenience.
-  final Map<_DeferredImport, LibraryElement> _allDeferredImports =
-      new Map<_DeferredImport, LibraryElement>();
+  Iterable<ImportElement> get _allDeferredImports =>
+      _deferredImportDescriptions.keys;
 
   /// Because the token-stream is forgotten later in the program, we cache a
   /// description of each deferred import.
-  final Map<_DeferredImport, ImportDescription> _deferredImportDescriptions =
-      <_DeferredImport, ImportDescription>{};
-
-  // For each deferred import we want to know exactly what elements have to
-  // be loaded.
-  Map<_DeferredImport, Set<Element>> _importedDeferredBy = null;
-  Map<_DeferredImport, Set<ConstantValue>> _constantsDeferredBy = null;
+  final Map<ImportElement, ImportDescription> _deferredImportDescriptions =
+      <ImportElement, ImportDescription>{};
 
-  Set<Element> _mainElements = new Set<Element>();
+  /// A lattice to compactly represent multiple subsets of imports.
+  final ImportSetLattice importSets = new ImportSetLattice();
 
   final Compiler compiler;
   DeferredLoadTask(Compiler compiler)
       : compiler = compiler,
         super(compiler.measurer) {
-    mainOutputUnit.imports.add(_fakeMainImport);
+    mainOutputUnit = new OutputUnit(true, 'main', new Set<ImportElement>());
+    importSets.mainSet.unit = mainOutputUnit;
+    allOutputUnits.add(mainOutputUnit);
   }
 
   JavaScriptBackend get backend => compiler.backend;
@@ -171,19 +171,19 @@ class DeferredLoadTask extends CompilerTask {
     if (!isProgramSplit) return mainOutputUnit;
     Element element = entity;
     element = element.implementation;
-    while (!_elementToOutputUnit.containsKey(element)) {
+    while (!_elementToSet.containsKey(element)) {
       // TODO(21051): workaround: it looks like we output annotation constants
       // for classes that we don't include in the output. This seems to happen
       // when we have reflection but can see that some classes are not needed.
       // We still add the annotation but don't run through it below (where we
       // assign every element to its output unit).
       if (element.enclosingElement == null) {
-        _elementToOutputUnit[element] = mainOutputUnit;
+        _elementToSet[element] = importSets.mainSet;
         break;
       }
       element = element.enclosingElement.implementation;
     }
-    return _elementToOutputUnit[element];
+    return _elementToSet[element].unit;
   }
 
   /// Returns the [OutputUnit] where [element] belongs.
@@ -197,20 +197,18 @@ class DeferredLoadTask extends CompilerTask {
   }
 
   /// Direct access to the output-unit to element relation used for testing.
-  OutputUnit getOutputUnitForElementForTesting(Element element) {
-    return _elementToOutputUnit[element];
+  OutputUnit getOutputUnitForElementForTesting(Entity element) {
+    return _elementToSet[element]?.unit;
   }
 
   /// Returns the [OutputUnit] where [constant] belongs.
   OutputUnit outputUnitForConstant(ConstantValue constant) {
     if (!isProgramSplit) return mainOutputUnit;
-    return _constantToOutputUnit[constant];
+    return _constantToSet[constant]?.unit;
   }
 
   /// Direct access to the output-unit to constants map used for testing.
-  Map<ConstantValue, OutputUnit> get outputUnitForConstantsForTesting {
-    return _constantToOutputUnit;
-  }
+  Iterable<ConstantValue> get constantsForTesting => _constantToSet.keys;
 
   bool isDeferred(Entity element) {
     return outputUnitForElement(element) != mainOutputUnit;
@@ -222,43 +220,38 @@ class DeferredLoadTask extends CompilerTask {
 
   /// Returns the unique name for the deferred import of [prefix].
   String getImportDeferName(Spannable node, PrefixElement prefix) {
-    String name =
-        importDeferName[new _DeclaredDeferredImport(prefix.deferredImport)];
+    String name = _importDeferName[prefix.deferredImport];
     if (name == null) {
       reporter.internalError(node, "No deferred name for $prefix.");
     }
     return name;
   }
 
+  /// Returns the names associated with each deferred import in [unit].
+  Iterable<String> getImportNames(OutputUnit unit) {
+    return unit._imports.map((i) => _importDeferName[i]);
+  }
+
   /// Returns `true` if element [to] is reachable from element [from] without
   /// crossing a deferred import.
   ///
   /// For example, if we have two deferred libraries `A` and `B` that both
   /// import a library `C`, then even though elements from `A` and `C` end up in
   /// different output units, there is a non-deferred path between `A` and `C`.
-  bool hasOnlyNonDeferredImportPaths(Element from, Element to) {
+  bool hasOnlyNonDeferredImportPaths(Entity from, Entity to) {
     OutputUnit outputUnitFrom = outputUnitForElement(from);
     OutputUnit outputUnitTo = outputUnitForElement(to);
-    return outputUnitTo.imports.containsAll(outputUnitFrom.imports);
-  }
-
-  // TODO(het): use a union-find to canonicalize output units
-  OutputUnit _getCanonicalUnit(OutputUnit outputUnit) {
-    OutputUnit representative = allOutputUnits.lookup(outputUnit);
-    if (representative == null) {
-      representative = outputUnit;
-      allOutputUnits.add(representative);
-    }
-    return representative;
+    if (outputUnitTo == mainOutputUnit) return true;
+    if (outputUnitFrom == mainOutputUnit) return false;
+    return outputUnitTo._imports.containsAll(outputUnitFrom._imports);
   }
 
   void registerConstantDeferredUse(
       DeferredConstantValue constant, PrefixElement prefix) {
-    OutputUnit outputUnit = new OutputUnit();
-    outputUnit.imports.add(new _DeclaredDeferredImport(prefix.deferredImport));
-
-    // Check to see if there is already a canonical output unit registered.
-    _constantToOutputUnit[constant] = _getCanonicalUnit(outputUnit);
+    var newSet = importSets.singleton(prefix.deferredImport);
+    assert(
+        _constantToSet[constant] == null || _constantToSet[constant] == newSet);
+    _constantToSet[constant] = newSet;
   }
 
   /// Given [imports] that refer to an element from a library, determine whether
@@ -510,82 +503,126 @@ class DeferredLoadTask extends CompilerTask {
     return result;
   }
 
-  /// Add all dependencies of [constant] to the mapping of [import].
-  void _mapConstantDependencies(
-      ConstantValue constant, _DeferredImport import) {
-    Set<ConstantValue> constants = _constantsDeferredBy.putIfAbsent(
-        import, () => new Set<ConstantValue>());
-    if (constants.contains(constant)) return;
-    constants.add(constant);
-    if (constant is ConstructedConstantValue) {
-      ClassElement cls = constant.type.element;
-      _mapDependencies(element: cls, import: import);
+  /// Update the import set of all constants reachable from [constant], as long
+  /// as they had the [oldSet]. As soon as we see a constant with a different
+  /// import set, we stop and enqueue a new recursive update in [queue].
+  ///
+  /// Invariants: oldSet is either null or a subset of newSet.
+  void _updateConstantRecursive(ConstantValue constant, ImportSet oldSet,
+      ImportSet newSet, WorkQueue queue) {
+    if (constant == null) return;
+    var currentSet = _constantToSet[constant];
+
+    // Already visited.
+    if (currentSet == newSet) return;
+
+    // Elements in the main output unit always remain there.
+    if (currentSet == importSets.mainSet) return;
+
+    if (currentSet == oldSet) {
+      _constantToSet[constant] = newSet;
+      if (constant is ConstructedConstantValue) {
+        ClassElement cls = constant.type.element;
+        _updateElementRecursive(cls, oldSet, newSet, queue);
+      }
+      constant.getDependencies().forEach((ConstantValue dependency) {
+        if (dependency is DeferredConstantValue) {
+          /// New deferred-imports are only discovered when we are visiting the
+          /// main output unit (size == 0) or code reachable from a deferred
+          /// import (size == 1). After that, we are rediscovering the
+          /// same nodes we have already seen.
+          if (newSet.length <= 1) {
+            PrefixElement prefix = dependency.prefix;
+            queue.addConstant(
+                dependency, importSets.singleton(prefix.deferredImport));
+          }
+        } else {
+          _updateConstantRecursive(dependency, oldSet, newSet, queue);
+        }
+      });
+    } else {
+      assert(
+          // Invariant: we must mark main before we mark any deferred import.
+          newSet != importSets.mainSet || oldSet != null,
+          failedAt(
+              NO_LOCATION_SPANNABLE,
+              "Tried to assign ${constant.toDartText()} to the main output "
+              "unit, but it was assigned to $currentSet."));
+      queue.addConstant(constant, newSet);
     }
-    constant.getDependencies().forEach((ConstantValue dependency) {
-      _mapConstantDependencies(dependency, import);
-    });
   }
 
-  /// Recursively traverses the graph of dependencies from [element], mapping
-  /// deferred imports to each dependency it needs in the sets
-  /// [_importedDeferredBy] and [_constantsDeferredBy].
-  void _mapDependencies(
-      {Element element, _DeferredImport import, isMirrorUsage: false}) {
-    Set<Element> elements = _importedDeferredBy[import] ??= new Set<Element>();
-
-    Set<Element> dependentElements = new Set<Element>();
-    Set<ConstantValue> dependentConstants = new Set<ConstantValue>();
-
-    LibraryElement library;
-
-    if (element != null) {
-      // Only process elements once, unless we are doing dependencies due to
-      // mirrors, which are added in additional traversals.
-      if (!isMirrorUsage && elements.contains(element)) return;
-      // Anything used directly by main will be loaded from the start
-      // We do not need to traverse it again.
-      if (import != _fakeMainImport && _mainElements.contains(element)) return;
-      // This adds [element] to [_mainElements] because [_mainElements] is
-      // aliased with `_importedDeferredBy[_fakeMainImport]]`.
-      elements.add(element);
+  /// Update the import set of all elements reachable from [element], as long as
+  /// they had the [oldSet]. As soon as we see an element with a different
+  /// import set, we stop and enqueue a new recursive update in [queue].
+  void _updateElementRecursive(
+      Element element, ImportSet oldSet, ImportSet newSet, WorkQueue queue,
+      {bool isMirrorUsage: false}) {
+    if (element == null) return;
+    var currentSet = _elementToSet[element];
+
+    // Already visited. We may visit some root nodes a second time with
+    // [isMirrorUsage] in order to mark static members used reflectively.
+    if (currentSet == newSet && !isMirrorUsage) return;
+
+    // Elements in the main output unit always remain there.
+    if (currentSet == importSets.mainSet) return;
+
+    if (currentSet == oldSet) {
+      // Continue recursively updating from [oldSet] to [newSet].
+      _elementToSet[element] = newSet;
 
-      // This call can modify [dependentElements] and [dependentConstants].
+      Set<Element> dependentElements = new Set<Element>();
+      Set<ConstantValue> dependentConstants = new Set<ConstantValue>();
       _collectAllElementsAndConstantsResolvedFrom(
           element, dependentElements, dependentConstants, isMirrorUsage);
 
-      library = element.library;
-    }
-
-    for (Element dependency in dependentElements) {
-      Iterable<ImportElement> imports = _getImports(dependency, library);
-      if (_isExplicitlyDeferred(imports)) {
-        for (ImportElement deferredImport in imports) {
-          _mapDependencies(
-              element: dependency,
-              import: new _DeclaredDeferredImport(deferredImport));
+      LibraryElement library = element.library;
+      for (Element dependency in dependentElements) {
+        Iterable<ImportElement> imports = _getImports(dependency, library);
+        if (_isExplicitlyDeferred(imports)) {
+          /// New deferred-imports are only discovered when we are visiting the
+          /// main output unit (size == 0) or code reachable from a deferred
+          /// import (size == 1). After that, we are rediscovering the
+          /// same nodes we have already seen.
+          if (newSet.length <= 1) {
+            for (ImportElement deferredImport in imports) {
+              queue.addElement(
+                  dependency, importSets.singleton(deferredImport));
+            }
+          }
+        } else {
+          _updateElementRecursive(dependency, oldSet, newSet, queue);
         }
-      } else {
-        _mapDependencies(element: dependency, import: import);
       }
-    }
 
-    for (ConstantValue dependency in dependentConstants) {
-      if (dependency is DeferredConstantValue) {
-        PrefixElement prefix = dependency.prefix;
-        _mapConstantDependencies(
-            dependency, new _DeclaredDeferredImport(prefix.deferredImport));
-      } else {
-        _mapConstantDependencies(dependency, import);
+      for (ConstantValue dependency in dependentConstants) {
+        if (dependency is DeferredConstantValue) {
+          if (newSet.length <= 1) {
+            PrefixElement prefix = dependency.prefix;
+            queue.addConstant(
+                dependency, importSets.singleton(prefix.deferredImport));
+          }
+        } else {
+          _updateConstantRecursive(dependency, oldSet, newSet, queue);
+        }
       }
+    } else {
+      queue.addElement(element, newSet);
     }
   }
 
   /// Adds extra dependencies coming from mirror usage.
-  ///
-  /// The elements are added with [_mapDependencies].
-  void _addMirrorElements() {
-    void mapDependenciesIfResolved(
-        Element element, _DeferredImport deferredImport) {
+  void _addDeferredMirrorElements(WorkQueue queue) {
+    for (ImportElement deferredImport in _allDeferredImports) {
+      _addMirrorElementsForLibrary(queue, deferredImport.importedLibrary,
+          importSets.singleton(deferredImport));
+    }
+  }
+
+  void _addMirrorElementsForLibrary(
+      WorkQueue queue, LibraryElement root, ImportSet newSet) {
+    void handleElementIfResolved(Element element) {
       // If an element is the target of a MirrorsUsed annotation but never used
       // It will not be resolved, and we should not call isNeededForReflection.
       // TODO(sigurdm): Unresolved elements should just answer false when
@@ -612,16 +649,15 @@ class DeferredLoadTask extends CompilerTask {
       }
 
       if (isAccessibleByReflection(element)) {
-        _mapDependencies(
-            element: element, import: deferredImport, isMirrorUsage: true);
+        queue.addElement(element, newSet, isMirrorUsage: true);
       }
     }
 
     // For each deferred import we analyze all elements reachable from the
     // imported library through non-deferred imports.
-    void handleLibrary(LibraryElement library, _DeferredImport deferredImport) {
+    void handleLibrary(LibraryElement library) {
       library.implementation.forEachLocalMember((Element element) {
-        mapDependenciesIfResolved(element, deferredImport);
+        handleElementIfResolved(element);
       });
 
       void processMetadata(Element element) {
@@ -629,7 +665,7 @@ class DeferredLoadTask extends CompilerTask {
           ConstantValue constant =
               backend.constants.getConstantValueForMetadata(metadata);
           if (constant != null) {
-            _mapConstantDependencies(constant, deferredImport);
+            queue.addConstant(constant, newSet);
           }
         }
       }
@@ -639,43 +675,43 @@ class DeferredLoadTask extends CompilerTask {
       library.exports.forEach(processMetadata);
     }
 
-    for (_DeferredImport deferredImport in _allDeferredImports.keys) {
-      LibraryElement deferredLibrary = _allDeferredImports[deferredImport];
-      for (LibraryElement library
-          in _nonDeferredReachableLibraries(deferredLibrary)) {
-        handleLibrary(library, deferredImport);
-      }
-    }
+    _nonDeferredReachableLibraries(root).forEach(handleLibrary);
   }
 
   /// Computes a unique string for the name field for each outputUnit.
-  ///
-  /// Also sets up the [hunksToLoad] mapping.
-  void _assignNamesToOutputUnits(Set<OutputUnit> allOutputUnits) {
+  void _createOutputUnits() {
+    int counter = 1;
+    void addUnit(ImportSet importSet) {
+      if (importSet.unit != null) return;
+      var unit = new OutputUnit(false, '$counter',
+          importSet._imports.map((i) => i.declaration).toSet());
+      counter++;
+      importSet.unit = unit;
+      allOutputUnits.add(unit);
+    }
+
+    // Generate an output unit for all import sets that are associated with an
+    // element or constant.
+    _elementToSet.values.forEach(addUnit);
+    _constantToSet.values.forEach(addUnit);
+
+    // Sort output units to make the output of the compiler more stable.
+    allOutputUnits.sort();
+  }
+
+  void _setupHunksToLoad() {
     Set<String> usedImportNames = new Set<String>();
 
-    void computeImportDeferName(_DeferredImport import) {
-      String result = import.computeImportDeferName(compiler);
+    void computeImportDeferName(ImportElement import) {
+      String result = _computeImportDeferName(import, compiler);
       assert(result != null);
-      importDeferName[import] = makeUnique(result, usedImportNames);
+      _importDeferName[import] = makeUnique(result, usedImportNames);
     }
 
-    int counter = 1;
-
-    for (_DeferredImport import in _allDeferredImports.keys) {
+    for (ImportElement import in _allDeferredImports) {
       computeImportDeferName(import);
     }
 
-    for (OutputUnit outputUnit in allOutputUnits) {
-      if (outputUnit == mainOutputUnit) {
-        outputUnit.name = "main";
-      } else {
-        outputUnit.name = "$counter";
-        ++counter;
-      }
-    }
-
-    List sortedOutputUnits = new List.from(allOutputUnits);
     // Sort the output units in descending order of the number of imports they
     // include.
 
@@ -688,122 +724,158 @@ class DeferredLoadTask extends CompilerTask {
     // shared by S2 such that S2 not a superset of S1. Let lib_s be a library in
     // S1 not in S2. lib_s must depend on C, and then in turn on D. Therefore D
     // is not in the right output unit.
-    sortedOutputUnits.sort((a, b) => b.imports.length - a.imports.length);
+    List sortedOutputUnits = allOutputUnits.reversed.toList();
 
     // For each deferred import we find out which outputUnits to load.
-    for (_DeferredImport import in _allDeferredImports.keys) {
-      if (import == _fakeMainImport) continue;
-      hunksToLoad[importDeferName[import]] = new List<OutputUnit>();
+    for (ImportElement import in _allDeferredImports) {
+      // We expect to find an entry for any call to `loadLibrary`, even if
+      // there is no code to load. In that case, the entry will be an empty
+      // list.
+      hunksToLoad[_importDeferName[import]] = new List<OutputUnit>();
       for (OutputUnit outputUnit in sortedOutputUnits) {
         if (outputUnit == mainOutputUnit) continue;
-        if (outputUnit.imports.contains(import)) {
-          hunksToLoad[importDeferName[import]].add(outputUnit);
+        if (outputUnit._imports.contains(import)) {
+          hunksToLoad[_importDeferName[import]].add(outputUnit);
         }
       }
     }
   }
 
+  /// Performs the deferred loading algorithm.
+  ///
+  /// The deferred loading algorithm maps elements and constants to an output
+  /// unit. Each output unit is identified by a subset of deferred imports (an
+  /// [ImportSet]), and they will contain the elements that are inheretly used
+  /// by all those deferred imports. An element is used by a deferred import if
+  /// it is either loaded by that import or transitively accessed by an element
+  /// that the import loads.  An empty set represents the main output unit,
+  /// which contains any elements that are accessed directly and are not
+  /// deferred.
+  ///
+  /// The algorithm traverses the element model recursively looking for
+  /// dependencies between elements. These dependencies may be deferred or
+  /// non-deferred. Deferred dependencies are mainly used to discover the root
+  /// elements that are loaded from deferred imports, while non-deferred
+  /// dependencies are used to recursively associate more elements to output
+  /// units.
+  ///
+  /// Naively, the algorithm traverses each root of a deferred import and marks
+  /// everything it can reach as being used by that import. To reduce how many
+  /// times we visit an element, we use an algorithm that works in segments: it
+  /// marks elements with a subset of deferred imports at a time, until it
+  /// detects a merge point where more deferred imports could be considered at
+  /// once.
+  ///
+  /// For example, consider this dependency graph (ignoring elements in the main
+  /// output unit):
+  ///
+  ///   deferred import A: a1 ---> s1 ---> s2  -> s3
+  ///                              ^       ^
+  ///                              |       |
+  ///   deferred import B: b1 -----+       |
+  ///                                      |
+  ///   deferred import C: c1 ---> c2 ---> c3
+  ///
+  /// The algorithm will compute a result with 5 deferred output units:
+  //
+  ///   * unit {A}:        contains a1
+  ///   * unit {B}:        contains b1
+  ///   * unit {C}:        contains c1, c2, and c3
+  ///   * unit {A, B}:     contains s1
+  ///   * unit {A, B, C}:  contains s2, and s3
+  ///
+  /// After marking everything reachable from main as part of the main output
+  /// unit, our algorithm will work as follows:
+  ///
+  ///   * Initially all deferred elements have no mapping.
+  ///   * We make note of work to do, initially to mark the root of each
+  ///     deferred import:
+  ///        * a1 with A, and recurse from there.
+  ///        * b1 with B, and recurse from there.
+  ///        * c1 with C, and recurse from there.
+  ///   * we update a1, s1, s2, s3 from no mapping to {A}
+  ///   * we update b1 from no mapping to {B}, and when we find s1 we notice
+  ///     that s1 is already associated with another import set {A}, so we make
+  ///     note of additional work for later to mark s1 with {A, B}
+  ///   * we update c1, c2, c3 to {C}, and make a note to update s2 with {A, C}
+  ///   * we update s1 to {A, B}, and update the existing note to update s2, now
+  ///     with {A, B, C}
+  ///   * finally we update s2 and s3 with {A, B, C} in one go, without ever
+  ///     updating them to the intermediate state {A, C}.
+  ///
+  /// The implementation below does atomic updates from one import-set to
+  /// another.  At first we add one deferred import at a time, but as the
+  /// algorithm progesses it may update a small import-set with a larger
+  /// import-set in one go. The key of this algorithm is to detect when sharing
+  /// begins, so we can update those elements more efficently.
+  ///
+  /// To detect these merge points where sharing begins, the implementation
+  /// below uses `a swap operation`: we first compare what the old import-set
+  /// is, and if it matches our expectation, the swap is done and we recurse,
+  /// otherwise a merge root was detected and we enqueue a new segment of
+  /// updates for later.
+  ///
+  /// TODO(sigmund): investigate different heuristics for how to select the next
+  /// work item (e.g. we might converge faster if we pick first the update that
+  /// contains a bigger delta.)
   void onResolutionComplete(FunctionEntity main, ClosedWorld closedWorld) {
-    if (!isProgramSplit) {
-      allOutputUnits.add(mainOutputUnit);
-      return;
-    }
+    if (!isProgramSplit) return;
     if (main == null) return;
-    MethodElement mainMethod = main;
-    LibraryElement mainLibrary = mainMethod.library;
-    _importedDeferredBy = new Map<_DeferredImport, Set<Element>>();
-    _constantsDeferredBy = new Map<_DeferredImport, Set<ConstantValue>>();
-    _importedDeferredBy[_fakeMainImport] = _mainElements;
 
     work() {
-      // Starting from main, traverse the program and find all dependencies.
-      _mapDependencies(element: mainMethod, import: _fakeMainImport);
+      var queue = new WorkQueue(this.importSets);
+
+      // Add `main` and their recursive dependencies to the main output unit.
+      // We do this upfront to avoid wasting time visiting these elements when
+      // analyzing deferred imports.
+      queue.addElement(main, importSets.mainSet);
 
-      // Also add "global" dependencies to the main OutputUnit.  These are
+      // Also add "global" dependencies to the main output unit.  These are
       // things that the backend needs but cannot associate with a particular
       // element, for example, startRootIsolate.  This set also contains
       // elements for which we lack precise information.
       for (MethodElement element
           in closedWorld.backendUsage.globalFunctionDependencies) {
-        _mapDependencies(
-            element: element.implementation, import: _fakeMainImport);
+        queue.addElement(element.implementation, importSets.mainSet);
       }
       for (ClassElement element
           in closedWorld.backendUsage.globalClassDependencies) {
-        _mapDependencies(
-            element: element.implementation, import: _fakeMainImport);
+        queue.addElement(element.implementation, importSets.mainSet);
       }
-
-      // Now check to see if we have to add more elements due to mirrors.
       if (closedWorld.backendUsage.isMirrorsUsed) {
-        _addMirrorElements();
+        _addMirrorElementsForLibrary(queue, main.library, importSets.mainSet);
       }
 
-      // Build the OutputUnits using these two maps.
-      Map<Element, OutputUnit> elementToOutputUnitBuilder =
-          new Map<Element, OutputUnit>();
-      Map<ConstantValue, OutputUnit> constantToOutputUnitBuilder =
-          new Map<ConstantValue, OutputUnit>();
-
-      // Add all constants that may have been registered during resolution with
-      // [registerConstantDeferredUse].
-      constantToOutputUnitBuilder.addAll(_constantToOutputUnit);
-      _constantToOutputUnit.clear();
-
-      // Reverse the mappings. For each element record an OutputUnit collecting
-      // all deferred imports mapped to this element. Same for constants.
-      for (_DeferredImport import in _importedDeferredBy.keys) {
-        for (Element element in _importedDeferredBy[import]) {
-          // Only one file should be loaded when the program starts, so make
-          // sure that only one OutputUnit is created for [fakeMainImport].
-          if (import == _fakeMainImport) {
-            elementToOutputUnitBuilder[element] = mainOutputUnit;
-          } else {
-            elementToOutputUnitBuilder
-                .putIfAbsent(element, () => new OutputUnit())
-                .imports
-                .add(import);
-          }
-        }
-      }
-      for (_DeferredImport import in _constantsDeferredBy.keys) {
-        for (ConstantValue constant in _constantsDeferredBy[import]) {
-          // Only one file should be loaded when the program starts, so make
-          // sure that only one OutputUnit is created for [fakeMainImport].
-          if (import == _fakeMainImport) {
-            constantToOutputUnitBuilder[constant] = mainOutputUnit;
-          } else {
-            constantToOutputUnitBuilder
-                .putIfAbsent(constant, () => new OutputUnit())
-                .imports
-                .add(import);
+      void emptyQueue() {
+        while (queue.isNotEmpty) {
+          var item = queue.nextItem();
+          if (item.element != null) {
+            var oldSet = _elementToSet[item.element];
+            var newSet = importSets.union(oldSet, item.newSet);
+            _updateElementRecursive(item.element, oldSet, newSet, queue,
+                isMirrorUsage: item.isMirrorUsage);
+          } else if (item.value != null) {
+            var oldSet = _constantToSet[item.value];
+            var newSet = importSets.union(oldSet, item.newSet);
+            _updateConstantRecursive(item.value, oldSet, newSet, queue);
           }
         }
       }
 
-      // Release maps;
-      _importedDeferredBy = null;
-      _constantsDeferredBy = null;
-
-      // Find all the output units elements/constants have been mapped
-      // to, and canonicalize them.
-      elementToOutputUnitBuilder
-          .forEach((Element element, OutputUnit outputUnit) {
-        _elementToOutputUnit[element] = _getCanonicalUnit(outputUnit);
-      });
-      constantToOutputUnitBuilder
-          .forEach((ConstantValue constant, OutputUnit outputUnit) {
-        _constantToOutputUnit[constant] = _getCanonicalUnit(outputUnit);
-      });
+      emptyQueue();
+      if (closedWorld.backendUsage.isMirrorsUsed) {
+        _addDeferredMirrorElements(queue);
+        emptyQueue();
+      }
 
-      // Generate a unique name for each OutputUnit.
-      _assignNamesToOutputUnits(allOutputUnits);
+      _createOutputUnits();
+      _setupHunksToLoad();
     }
 
-    reporter.withCurrentElement(mainLibrary, () => measure(work));
+    reporter.withCurrentElement(main.library, () => measure(work));
 
-    // Notify the impact strategy impacts are no longer needed for deferred
-    // load.
+    // Notify that we no longer need impacts for deferred load, so they can be
+    // discarded at this time.
     compiler.impactStrategy.onImpactUsed(IMPACT_USE);
   }
 
@@ -811,7 +883,6 @@ class DeferredLoadTask extends CompilerTask {
     if (mainLibrary == null) return;
     // TODO(johnniwinther): Support deferred load for kernel based elements.
     if (compiler.options.useKernel) return;
-    _allDeferredImports[_fakeMainImport] = mainLibrary;
     var lastDeferred;
     // When detecting duplicate prefixes of deferred libraries there are 4
     // cases of duplicate prefixes:
@@ -862,17 +933,13 @@ class DeferredLoadTask extends CompilerTask {
           // The last import we saw with the same prefix.
           ImportElement previousDeferredImport = prefixDeferredImport[prefix];
           if (import.isDeferred) {
-            _DeferredImport key = new _DeclaredDeferredImport(import);
-            LibraryElement importedLibrary = import.importedLibrary;
-            _allDeferredImports[key] = importedLibrary;
-
             if (prefix == null) {
               reporter.reportErrorMessage(
                   import, MessageKind.DEFERRED_LIBRARY_WITHOUT_PREFIX);
             } else {
               prefixDeferredImport[prefix] = import;
               Uri mainLibraryUri = compiler.mainLibraryUri;
-              _deferredImportDescriptions[key] =
+              _deferredImportDescriptions[import] =
                   new ImportDescription(import, library, mainLibraryUri);
             }
             isProgramSplit = true;
@@ -971,8 +1038,8 @@ class DeferredLoadTask extends CompilerTask {
   Map<String, Map<String, dynamic>> computeDeferredMap() {
     Map<String, Map<String, dynamic>> mapping =
         new Map<String, Map<String, dynamic>>();
-    _deferredImportDescriptions.keys.forEach((_DeferredImport import) {
-      List<OutputUnit> outputUnits = hunksToLoad[importDeferName[import]];
+    _deferredImportDescriptions.keys.forEach((ImportElement import) {
+      List<OutputUnit> outputUnits = hunksToLoad[_importDeferName[import]];
       ImportDescription description = _deferredImportDescriptions[import];
       Map<String, dynamic> libraryMap = mapping.putIfAbsent(
           description.importingUri,
@@ -981,7 +1048,7 @@ class DeferredLoadTask extends CompilerTask {
                 "imports": <String, List<String>>{}
               });
 
-      libraryMap["imports"][importDeferName[import]] =
+      libraryMap["imports"][_importDeferName[import]] =
           outputUnits.map((OutputUnit outputUnit) {
         return deferredPartFileName(outputUnit.name);
       }).toList();
@@ -1007,33 +1074,51 @@ class DeferredLoadTask extends CompilerTask {
   String dump() {
     Map<OutputUnit, List<String>> elementMap = <OutputUnit, List<String>>{};
     Map<OutputUnit, List<String>> constantMap = <OutputUnit, List<String>>{};
-    _elementToOutputUnit.forEach((Element element, OutputUnit output) {
-      elementMap.putIfAbsent(output, () => <String>[]).add('$element');
+    _elementToSet.forEach((Entity element, ImportSet importSet) {
+      elementMap.putIfAbsent(importSet.unit, () => <String>[]).add('$element');
     });
-    _constantToOutputUnit.forEach((ConstantValue value, OutputUnit output) {
+    _constantToSet.forEach((ConstantValue value, ImportSet importSet) {
       constantMap
-          .putIfAbsent(output, () => <String>[])
+          .putIfAbsent(importSet.unit, () => <String>[])
           .add(value.toStructuredText());
     });
 
-    StringBuffer sb = new StringBuffer();
+    Map<OutputUnit, String> text = {};
     for (OutputUnit outputUnit in allOutputUnits) {
-      sb.write('\n-------------------------------\n');
-      sb.write('Output unit: ${outputUnit.name}');
+      StringBuffer unitText = new StringBuffer();
+      if (outputUnit.isMainOutput) {
+        unitText.write(' <MAIN UNIT>');
+      } else {
+        unitText.write(' imports:');
+        var imports = outputUnit._imports.map((i) => '${i.uri}').toList()
+          ..sort();
+        for (var i in imports) {
+          unitText.write('\n   $i:');
+        }
+      }
       List<String> elements = elementMap[outputUnit];
       if (elements != null) {
-        sb.write('\n elements:');
+        unitText.write('\n elements:');
         for (String element in elements..sort()) {
-          sb.write('\n  $element');
+          unitText.write('\n  $element');
         }
       }
       List<String> constants = constantMap[outputUnit];
       if (constants != null) {
-        sb.write('\n constants:');
+        unitText.write('\n constants:');
         for (String value in constants..sort()) {
-          sb.write('\n  $value');
+          unitText.write('\n  $value');
         }
       }
+      text[outputUnit] = '$unitText';
+    }
+
+    StringBuffer sb = new StringBuffer();
+    for (OutputUnit outputUnit in allOutputUnits.toList()
+      ..sort((a, b) => text[a].compareTo(text[b]))) {
+      sb.write('\n\n-------------------------------\n');
+      sb.write('Output unit: ${outputUnit.name}');
+      sb.write('\n ${text[outputUnit]}');
     }
     return sb.toString();
   }
@@ -1061,67 +1146,249 @@ class ImportDescription {
   }
 }
 
-/// A node in the deferred import graph.
+/// Indirectly represents a deferred import in an [ImportSet].
 ///
-/// This class serves as the root node; the 'import' of the main library.
+/// We could directly store the [declaration] in [ImportSet], but adding this
+/// class makes some of the import set operations more efficient.
 class _DeferredImport {
-  const _DeferredImport();
-
-  /// Computes a suggestive name for this import.
-  String computeImportDeferName(Compiler compiler) => 'main';
+  final ImportElement declaration;
 
-  ImportElement get declaration => null;
+  /// Canonical index associated with [declaration]. This is used to efficiently
+  /// implement [ImportSetLattice.union].
+  final int index;
 
-  String toString() => 'main';
+  _DeferredImport(this.declaration, this.index);
 }
 
-/// A node in the deferred import graph defined by a deferred import directive.
-class _DeclaredDeferredImport implements _DeferredImport {
-  final ImportElement declaration;
-
-  _DeclaredDeferredImport(this.declaration);
+/// A compact lattice representation of import sets and subsets.
+///
+/// We use a graph of nodes to represent elements of the lattice, but only
+/// create new nodes on-demand as they are needed by the deferred loading
+/// algorithm.
+///
+/// The constructions of nodes is carefully done by storing imports in a
+/// specific order. This ensures that we have a unique and canonical
+/// representation for each subset.
+class ImportSetLattice {
+  /// Index of deferred imports that defines the canonical order used by the
+  /// operations below.
+  Map<ImportElement, _DeferredImport> _importIndex = {};
+
+  /// The canonical instance representing the empty import set.
+  ImportSet _emptySet = new ImportSet();
+
+  /// The import set representing the main output unit, which happens to be
+  /// implemented as an empty set in our algorithm.
+  ImportSet get mainSet => _emptySet;
+
+  /// Get the singleton import set that only contains [import].
+  ImportSet singleton(ImportElement import) {
+    // Ensure we have import in the index.
+    return _emptySet._add(_wrap(import));
+  }
 
-  @override
-  String computeImportDeferName(Compiler compiler) {
-    String result;
-    if (declaration.isDeferred) {
-      if (declaration.prefix != null) {
-        result = declaration.prefix.name;
+  /// Get the import set that includes the union of [a] and [b].
+  ImportSet union(ImportSet a, ImportSet b) {
+    if (a == null || a == _emptySet) return b;
+    if (b == null || b == _emptySet) return a;
+
+    // We create the union by merging the imports in canonical order first, and
+    // then getting (or creating) the canonical sets by adding an import at a
+    // time.
+    List<_DeferredImport> aImports = a._imports;
+    List<_DeferredImport> bImports = b._imports;
+    int i = 0, j = 0, lastAIndex = 0, lastBIndex = 0;
+    var result = _emptySet;
+    while (i < aImports.length && j < bImports.length) {
+      var importA = aImports[i];
+      var importB = bImports[j];
+      assert(lastAIndex <= importA.index);
+      assert(lastBIndex <= importB.index);
+      if (importA.index < importB.index) {
+        result = result._add(importA);
+        i++;
       } else {
-        // This happens when the deferred import isn't declared with a prefix.
-        assert(compiler.compilationFailed);
-        result = '';
-      }
-    } else {
-      // Finds the first argument to the [DeferredLibrary] annotation
-      List<MetadataAnnotation> metadatas = declaration.metadata;
-      assert(metadatas != null);
-      for (MetadataAnnotation metadata in metadatas) {
-        metadata.ensureResolved(compiler.resolution);
-        ConstantValue value =
-            compiler.constants.getConstantValue(metadata.constant);
-        ResolutionDartType type =
-            value.getType(compiler.resolution.commonElements);
-        Element element = type.element;
-        if (element ==
-            compiler.resolution.commonElements.deferredLibraryClass) {
-          ConstructedConstantValue constant = value;
-          StringConstantValue s = constant.fields.values.single;
-          result = s.primitiveValue;
-          break;
-        }
+        result = result._add(importB);
+        j++;
       }
     }
-    assert(result != null);
+    for (; i < aImports.length; i++) {
+      result = result._add(aImports[i]);
+    }
+    for (; j < bImports.length; j++) {
+      result = result._add(bImports[j]);
+    }
+
     return result;
   }
 
-  bool operator ==(other) {
-    if (other is! _DeclaredDeferredImport) return false;
-    return declaration == other.declaration;
+  /// Get the index for an [import] according to the canonical order.
+  _DeferredImport _wrap(ImportElement import) {
+    return _importIndex.putIfAbsent(
+        import, () => new _DeferredImport(import, _importIndex.length));
   }
+}
 
-  int get hashCode => declaration.hashCode * 17;
+/// A canonical set of deferred imports.
+class ImportSet {
+  /// Imports that are part of this set.
+  ///
+  /// Invariant: the order in which elements are added must respect the
+  /// canonical order of all imports in [ImportSetLattice].
+  final List<_DeferredImport> _imports;
+
+  /// Links to other import sets in the lattice by adding one import.
+  final Map<_DeferredImport, ImportSet> _transitions =
+      <_DeferredImport, ImportSet>{};
+
+  ImportSet([this._imports = const <_DeferredImport>[]]);
+
+  /// The output unit corresponding to this set of imports, if any.
+  OutputUnit unit;
+
+  int get length => _imports.length;
+
+  /// Create an import set that adds [import] to all the imports on this set.
+  /// This assumes that import's canonical order comes after all imports in
+  /// this current set. This should only be called from [ImportSetLattice],
+  /// since it is where we preserve this invariant.
+  ImportSet _add(_DeferredImport import) {
+    return _transitions.putIfAbsent(import, () {
+      var result = new ImportSet(new List.from(_imports)..add(import));
+      result._transitions[import] = result;
+      return result;
+    });
+  }
+
+  String toString() {
+    StringBuffer sb = new StringBuffer();
+    sb.write('ImportSet(size: $length, ');
+    for (var import in _imports) {
+      sb.write('${import.declaration.prefix} ');
+    }
+    sb.write(')');
+    return '$sb';
+  }
+}
+
+/// The algorithm work queue.
+class WorkQueue {
+  /// The actual queue of work that needs to be done.
+  final Queue<WorkItem> queue = new Queue<WorkItem>();
+
+  /// An index to find work items in the queue corresponding to an entity.
+  final Map<Entity, WorkItem> pendingElements = <Entity, WorkItem>{};
+
+  /// An index to find work items in the queue corresponding to a constant.
+  final Map<ConstantValue, WorkItem> pendingConstants =
+      <ConstantValue, WorkItem>{};
+
+  /// Lattice used to compute unions of [ImportSet]s.
+  final ImportSetLattice _importSets;
 
-  String toString() => '$declaration';
+  WorkQueue(this._importSets);
+
+  /// Whether there are no more work items in the queue.
+  bool get isNotEmpty => queue.isNotEmpty;
+
+  /// Pop the next element in the queue.
+  WorkItem nextItem() {
+    assert(isNotEmpty);
+    var item = queue.removeFirst();
+    if (item.element != null) pendingElements.remove(item.element);
+    if (item.value != null) pendingConstants.remove(item.value);
+    return item;
+  }
+
+  /// Add to the queue that [element] should be updated to include all imports
+  /// in [importSet]. If there is already a work item in the queue for
+  /// [element], this makes sure that the work item now includes the union of
+  /// [importSet] and the existing work item's import set.
+  void addElement(Entity element, ImportSet importSet, {isMirrorUsage: false}) {
+    var item = pendingElements[element];
+    if (item == null) {
+      item = new WorkItem(element, importSet);
+      pendingElements[element] = item;
+      queue.add(item);
+    } else {
+      item.newSet = _importSets.union(item.newSet, importSet);
+    }
+    if (isMirrorUsage) item.isMirrorUsage = true;
+  }
+
+  /// Add to the queue that [constant] should be updated to include all imports
+  /// in [importSet]. If there is already a work item in the queue for
+  /// [constant], this makes sure that the work item now includes the union of
+  /// [importSet] and the existing work item's import set.
+  void addConstant(ConstantValue constant, ImportSet importSet) {
+    var item = pendingConstants[constant];
+    if (item == null) {
+      item = new WorkItem.constant(constant, importSet);
+      pendingConstants[constant] = item;
+      queue.add(item);
+    } else {
+      item.newSet = _importSets.union(item.newSet, importSet);
+    }
+  }
+}
+
+/// Summary of the work that needs to be done on an entity or constant.
+class WorkItem {
+  /// Entity to be recursively updated.
+  final Entity element;
+
+  /// Constant to be recursively updated.
+  final ConstantValue value;
+
+  /// Additional imports that use [element] or [value] and need to be added by
+  /// the algorithm.
+  ///
+  /// This is non-final in case we add more deferred imports to the set before
+  /// the work item is applied (see [WorkQueue.addElement] and
+  /// [WorkQueue.addConstant]).
+  ImportSet newSet;
+
+  /// Whether [element] is used via mirrors.
+  ///
+  /// This is non-final in case we later discover that the same [element] is
+  /// used via mirrors (but before the work item is applied).
+  bool isMirrorUsage = false;
+
+  WorkItem(this.element, this.newSet) : value = null;
+  WorkItem.constant(this.value, this.newSet) : element = null;
+}
+
+/// Returns a name for a deferred import.
+// TODO(sigmund): delete support for the old annotation-style syntax.
+String _computeImportDeferName(ImportElement declaration, Compiler compiler) {
+  String result;
+  if (declaration.isDeferred) {
+    if (declaration.prefix != null) {
+      result = declaration.prefix.name;
+    } else {
+      // This happens when the deferred import isn't declared with a prefix.
+      assert(compiler.compilationFailed);
+      result = '';
+    }
+  } else {
+    // Finds the first argument to the [DeferredLibrary] annotation
+    List<MetadataAnnotation> metadatas = declaration.metadata;
+    assert(metadatas != null);
+    for (MetadataAnnotation metadata in metadatas) {
+      metadata.ensureResolved(compiler.resolution);
+      ConstantValue value =
+          compiler.constants.getConstantValue(metadata.constant);
+      ResolutionDartType type =
+          value.getType(compiler.resolution.commonElements);
+      Element element = type.element;
+      if (element == compiler.resolution.commonElements.deferredLibraryClass) {
+        ConstructedConstantValue constant = value;
+        StringConstantValue s = constant.fields.values.single;
+        result = s.primitiveValue;
+        break;
+      }
+    }
+  }
+  assert(result != null);
+  return result;
 }