diff --git a/pkg/compiler/lib/src/deferred_load/algorithm_state.dart b/pkg/compiler/lib/src/deferred_load/algorithm_state.dart
new file mode 100644
index 0000000..3f08d13
--- /dev/null
+++ b/pkg/compiler/lib/src/deferred_load/algorithm_state.dart
@@ -0,0 +1,155 @@
+// Copyright (c) 2021, 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.
+
+import 'entity_data.dart';
+import 'entity_data_info.dart';
+import 'import_set.dart';
+import 'work_queue.dart';
+
+import '../common.dart';
+import '../compiler.dart' show Compiler;
+import '../elements/entities.dart';
+import '../kernel/element_map.dart';
+import '../world.dart' show KClosedWorld;
+
+/// Manages the state of the [EntityData] model. Every class, member, constant,
+/// etc, is wrapped in the deferred loading algorithm by an [EntityData] which
+/// knows how to collect dependencies for a given [Entity].
+class AlgorithmState {
+  final Compiler compiler;
+  final KernelToElementMap elementMap;
+  final KClosedWorld closedWorld;
+  final EntityDataRegistry registry;
+  final Map<EntityData, ImportSet> entityToSet = {};
+  final Map<EntityData, EntityDataInfo> entityDataToInfo = {};
+  final ImportSetLattice importSets;
+  final WorkQueue queue;
+
+  AlgorithmState._(this.closedWorld, this.elementMap, this.compiler,
+      this.importSets, this.registry)
+      : queue = WorkQueue(importSets, registry);
+
+  /// Factory function to create and initialize a [AlgorithmState].
+  factory AlgorithmState.create(
+      FunctionEntity main,
+      Compiler compiler,
+      KernelToElementMap elementMap,
+      KClosedWorld closedWorld,
+      ImportSetLattice importSets) {
+    var entityDataState = AlgorithmState._(
+        closedWorld, elementMap, compiler, importSets, EntityDataRegistry());
+    entityDataState.initialize(main);
+    return entityDataState;
+  }
+
+  /// Given an [EntityData], an [oldSet] and a [newSet], either ignore the
+  /// update, apply the update immediately if we can avoid unions, or apply the
+  /// update later if we cannot. For more detail on [oldSet] and [newSet],
+  /// please see the comment in deferred_load.dart.
+  void update(EntityData entityData, ImportSet oldSet, ImportSet newSet) {
+    ImportSet currentSet = entityToSet[entityData];
+
+    // If [currentSet] == [newSet], then currentSet must include all of newSet.
+    if (currentSet == newSet) return;
+
+    // Elements in the main output unit always remain there.
+    if (currentSet == importSets.mainSet) return;
+
+    // If [currentSet] == [oldSet], then we can safely update the
+    // [entityToSet] map for [entityData] to [newSet] in a single assignment.
+    // If not, then if we are supposed to update [entityData] recursively, we add
+    // it back to the queue so that we can re-enter [update] later after
+    // performing a union. If we aren't supposed to update recursively, we just
+    // perform the union inline.
+    if (currentSet == oldSet) {
+      // Continue recursively updating from [oldSet] to [newSet].
+      entityToSet[entityData] = newSet;
+      updateDependencies(entityData, oldSet, newSet);
+    } else if (entityData.needsRecursiveUpdate) {
+      assert(
+          // Invariant: we must mark main before we mark any deferred import.
+          newSet != importSets.mainSet || oldSet != null,
+          failedAt(
+              NO_LOCATION_SPANNABLE,
+              "Tried to assign to the main output unit, but it was assigned "
+              "to $currentSet."));
+      queue.addEntityData(entityData, newSet);
+    } else {
+      entityToSet[entityData] = importSets.union(currentSet, newSet);
+    }
+  }
+
+  /// Returns the [EntityDataInfo] associated with a given [EntityData].
+  EntityDataInfo getInfo(EntityData data) {
+    // Check for cached [EntityDataInfo], otherwise create a new one and
+    // collect dependencies.
+    var info = entityDataToInfo[data];
+    if (info == null) {
+      var infoBuilder =
+          EntityDataInfoBuilder(closedWorld, elementMap, compiler, registry);
+      var visitor = EntityDataInfoVisitor(infoBuilder);
+      data.accept(visitor);
+      info = infoBuilder.info;
+      entityDataToInfo[data] = info;
+    }
+    return info;
+  }
+
+  /// Whether to enqueue a deferred entityData.
+  ///
+  /// Due to the nature of the algorithm, some dependencies may be visited more
+  /// than once. However, we know that 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.
+  bool _shouldAddDeferredEntity(ImportSet newSet) => newSet.length <= 1;
+
+  /// Updates the dependencies of a given [EntityData] from [oldSet] to
+  /// [newSet].
+  void updateDependencies(
+      EntityData entityData, ImportSet oldSet, ImportSet newSet) {
+    var info = getInfo(entityData);
+
+    // Process all [DeferredEntityDataInfo]s.
+    if (_shouldAddDeferredEntity(newSet)) {
+      info.deferredRoots.forEach((entity, imports) {
+        for (ImportEntity deferredImport in imports) {
+          queue.addEntityData(entity, importSets.singleton(deferredImport));
+        }
+      });
+    }
+
+    // Process all [directEntityData].
+    for (var entity in info.directDependencies) {
+      update(entity, oldSet, newSet);
+    }
+  }
+
+  /// Initializes the [AlgorithmState] assuming that [main] is the main entry
+  /// point of a given program.
+  void initialize(FunctionEntity main) {
+    // 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.addMember(main, importSets.mainSet);
+
+    // Also add "global" dependencies to the main output unit.  These are
+    // things that the backend needs but cannot associate with a particular
+    // element. This set also contains elements for which we lack precise
+    // information.
+    for (MemberEntity element
+        in closedWorld.backendUsage.globalFunctionDependencies) {
+      queue.addMember(element, importSets.mainSet);
+    }
+    for (ClassEntity element
+        in closedWorld.backendUsage.globalClassDependencies) {
+      queue.addClass(element, importSets.mainSet);
+    }
+
+    // Empty queue.
+    while (queue.isNotEmpty) {
+      queue.processNextItem(this);
+    }
+  }
+}
diff --git a/pkg/compiler/lib/src/deferred_load/deferred_load.dart b/pkg/compiler/lib/src/deferred_load/deferred_load.dart
index c531ba2..360d33e 100644
--- a/pkg/compiler/lib/src/deferred_load/deferred_load.dart
+++ b/pkg/compiler/lib/src/deferred_load/deferred_load.dart
@@ -268,39 +268,26 @@
 // contains a bigger delta.)
 library deferred_load;
 
-import 'dart:collection' show Queue;
-
-import 'package:kernel/ast.dart' as ir;
-
-import 'dependencies.dart';
+import 'algorithm_state.dart';
+import 'entity_data.dart';
 import 'import_set.dart';
 import 'output_unit.dart';
 
 import '../../compiler_new.dart' show OutputType;
-import '../common/metrics.dart' show Metric, Metrics, CountMetric, DurationMetric;
+import '../common/metrics.dart'
+    show Metric, Metrics, CountMetric, DurationMetric;
 import '../common/tasks.dart' show CompilerTask;
 import '../common.dart';
-import '../common_elements.dart' show CommonElements, KElementEnvironment;
+import '../common_elements.dart' show KElementEnvironment;
 import '../compiler.dart' show Compiler;
-import '../constants/values.dart'
-    show
-        ConstantValue,
-        ConstructedConstantValue,
-        InstantiationConstantValue;
+import '../constants/values.dart' show ConstantValue;
 import '../elements/types.dart';
 import '../elements/entities.dart';
-import '../kernel/kelements.dart' show KLocalFunction;
 import '../kernel/element_map.dart';
-import '../universe/use.dart';
-import '../universe/world_impact.dart'
-    show ImpactUseCase, WorldImpact, WorldImpactVisitorImpl;
+import '../universe/world_impact.dart' show ImpactUseCase;
 import '../util/util.dart' show makeUnique;
 import '../world.dart' show KClosedWorld;
 
-// TODO(joshualitt): Refactor logic out of DeferredLoadTask so work_queue.dart
-// can be its own independent library.
-part 'work_queue.dart';
-
 class _DeferredLoadTaskMetrics implements Metrics {
   @override
   String get namespace => 'deferred_load';
@@ -338,21 +325,6 @@
   /// this map.
   final Map<ImportEntity, String> importDeferName = {};
 
-  /// A mapping from classes to their import set.
-  Map<ClassEntity, ImportSet> _classToSet = {};
-
-  /// A mapping from interface types (keyed by classes) to their import set.
-  Map<ClassEntity, ImportSet> _classTypeToSet = {};
-
-  /// A mapping from members to their import set.
-  Map<MemberEntity, ImportSet> _memberToSet = {};
-
-  /// A mapping from local functions to their import set.
-  Map<Local, ImportSet> _localFunctionToSet = {};
-
-  /// A mapping from constants to their import set.
-  Map<ConstantValue, ImportSet> _constantToSet = {};
-
   Iterable<ImportEntity> get _allDeferredImports =>
       _deferredImportDescriptions.keys;
 
@@ -372,6 +344,8 @@
 
   bool get disableProgramSplit => compiler.options.disableProgramSplit;
 
+  AlgorithmState algorithmState;
+
   DeferredLoadTask(this.compiler, this._elementMap) : super(compiler.measurer) {
     _mainOutputUnit = OutputUnit(true, 'main', {});
     importSets.mainSet.unit = _mainOutputUnit;
@@ -381,487 +355,10 @@
   KElementEnvironment get elementEnvironment =>
       compiler.frontendStrategy.elementEnvironment;
 
-  CommonElements get commonElements => compiler.frontendStrategy.commonElements;
-  DartTypes get dartTypes => commonElements.dartTypes;
+  DartTypes get dartTypes => compiler.frontendStrategy.commonElements.dartTypes;
 
   DiagnosticReporter get reporter => compiler.reporter;
 
-  /// Collects all direct dependencies of [element].
-  ///
-  /// The collected dependent elements and constants are are added to
-  /// [elements] and [constants] respectively.
-  void _collectDirectMemberDependencies(KClosedWorld closedWorld,
-      MemberEntity element, Dependencies dependencies) {
-    // TODO(sigurdm): We want to be more specific about this - need a better
-    // way to query "liveness".
-    if (!closedWorld.isMemberUsed(element)) {
-      return;
-    }
-    _collectDependenciesFromImpact(closedWorld, element, dependencies);
-    collectConstantsInBody(element, dependencies);
-  }
-
-  /// Finds all elements and constants that [element] depends directly on.
-  /// (not the transitive closure.)
-  ///
-  /// Adds the results to [elements] and [constants].
-  void _collectAllElementsAndConstantsResolvedFromClass(
-      KClosedWorld closedWorld,
-      ClassEntity element,
-      Dependencies dependencies) {
-    // If we see a class, add everything its live instance members refer
-    // to.  Static members are not relevant, unless we are processing
-    // extra dependencies due to mirrors.
-    void addLiveInstanceMember(MemberEntity member) {
-      if (!closedWorld.isMemberUsed(member)) return;
-      if (!member.isInstanceMember) return;
-      dependencies.addMember(member);
-      _collectDirectMemberDependencies(closedWorld, member, dependencies);
-    }
-
-    void addClassAndMaybeAddEffectiveMixinClass(ClassEntity cls) {
-      dependencies.addClass(cls);
-      if (elementEnvironment.isMixinApplication(cls)) {
-        dependencies.addClass(elementEnvironment.getEffectiveMixinClass(cls));
-      }
-    }
-
-    ClassEntity cls = element;
-    elementEnvironment.forEachLocalClassMember(cls, addLiveInstanceMember);
-    elementEnvironment.forEachSupertype(cls, (InterfaceType type) {
-      _collectTypeDependencies(type, dependencies);
-    });
-    elementEnvironment.forEachSuperClass(cls, (superClass) {
-      addClassAndMaybeAddEffectiveMixinClass(superClass);
-      _collectTypeDependencies(
-          elementEnvironment.getThisType(superClass), dependencies);
-    });
-    addClassAndMaybeAddEffectiveMixinClass(cls);
-  }
-
-  /// Finds all elements and constants that [element] depends directly on.
-  /// (not the transitive closure.)
-  ///
-  /// Adds the results to [elements] and [constants].
-  void _collectAllElementsAndConstantsResolvedFromMember(
-      KClosedWorld closedWorld,
-      MemberEntity element,
-      Dependencies dependencies) {
-    if (element is FunctionEntity) {
-      _collectTypeDependencies(
-          elementEnvironment.getFunctionType(element), dependencies);
-    }
-    if (element.isStatic || element.isTopLevel || element.isConstructor) {
-      dependencies.addMember(element);
-      _collectDirectMemberDependencies(closedWorld, element, dependencies);
-    }
-    if (element is ConstructorEntity && element.isGenerativeConstructor) {
-      // When instantiating a class, we record a reference to the
-      // constructor, not the class itself.  We must add all the
-      // instance members of the constructor's class.
-      ClassEntity cls = element.enclosingClass;
-      _collectAllElementsAndConstantsResolvedFromClass(
-          closedWorld, cls, dependencies);
-    }
-
-    // Other elements, in particular instance members, are ignored as
-    // they are processed as part of the class.
-  }
-
-  /// Extract the set of constants that are used in the body of [element].
-  void collectConstantsInBody(MemberEntity element, Dependencies dependencies) {
-    ir.Member node = _elementMap.getMemberNode(element);
-
-    // Fetch the internal node in order to skip annotations on the member.
-    // TODO(sigmund): replace this pattern when the kernel-ast provides a better
-    // way to skip annotations (issue 31565).
-    var visitor = ConstantCollector(
-        _elementMap, _elementMap.getStaticTypeContext(element), dependencies);
-    if (node is ir.Field) {
-      node.initializer?.accept(visitor);
-      return;
-    }
-
-    if (node is ir.Constructor) {
-      node.initializers.forEach((i) => i.accept(visitor));
-    }
-    node.function?.accept(visitor);
-  }
-
-  /// Recursively collects all the dependencies of [type].
-  void _collectTypeDependencies(DartType type, Dependencies dependencies,
-      [ImportEntity import]) {
-    TypeDependencyVisitor(dependencies, import, commonElements).visit(type);
-  }
-
-  void _collectTypeArgumentDependencies(
-      Iterable<DartType> typeArguments, Dependencies dependencies,
-      [ImportEntity import]) {
-    if (typeArguments == null) return;
-    TypeDependencyVisitor(dependencies, import, commonElements)
-        .visitList(typeArguments);
-  }
-
-  /// Extract any dependencies that are known from the impact of [element].
-  void _collectDependenciesFromImpact(KClosedWorld closedWorld,
-      MemberEntity element, Dependencies dependencies) {
-    WorldImpact worldImpact = compiler.impactCache[element];
-    compiler.impactStrategy.visitImpact(
-        element,
-        worldImpact,
-        WorldImpactVisitorImpl(
-            visitStaticUse: (MemberEntity member, StaticUse staticUse) {
-          void processEntity() {
-            Entity usedEntity = staticUse.element;
-            if (usedEntity is MemberEntity) {
-              dependencies.addMember(usedEntity, staticUse.deferredImport);
-            } else {
-              assert(usedEntity is KLocalFunction,
-                  failedAt(usedEntity, "Unexpected static use $staticUse."));
-              KLocalFunction localFunction = usedEntity;
-              // TODO(sra): Consult KClosedWorld to see if signature is needed.
-              _collectTypeDependencies(
-                  localFunction.functionType, dependencies);
-              dependencies.localFunctions.add(localFunction);
-            }
-          }
-
-          switch (staticUse.kind) {
-            case StaticUseKind.CONSTRUCTOR_INVOKE:
-            case StaticUseKind.CONST_CONSTRUCTOR_INVOKE:
-              // The receiver type of generative constructors is a dependency of
-              // the constructor (handled by `addMember` above) and not a
-              // dependency at the call site.
-              // Factory methods, on the other hand, are like static methods so
-              // the target type is not relevant.
-              // TODO(johnniwinther): Use rti need data to skip unneeded type
-              // arguments.
-              _collectTypeArgumentDependencies(
-                  staticUse.type.typeArguments, dependencies);
-              processEntity();
-              break;
-            case StaticUseKind.STATIC_INVOKE:
-            case StaticUseKind.CLOSURE_CALL:
-            case StaticUseKind.DIRECT_INVOKE:
-              // TODO(johnniwinther): Use rti need data to skip unneeded type
-              // arguments.
-              _collectTypeArgumentDependencies(
-                  staticUse.typeArguments, dependencies);
-              processEntity();
-              break;
-            case StaticUseKind.STATIC_TEAR_OFF:
-            case StaticUseKind.CLOSURE:
-            case StaticUseKind.STATIC_GET:
-            case StaticUseKind.STATIC_SET:
-              processEntity();
-              break;
-            case StaticUseKind.SUPER_TEAR_OFF:
-            case StaticUseKind.SUPER_FIELD_SET:
-            case StaticUseKind.SUPER_GET:
-            case StaticUseKind.SUPER_SETTER_SET:
-            case StaticUseKind.SUPER_INVOKE:
-            case StaticUseKind.INSTANCE_FIELD_GET:
-            case StaticUseKind.INSTANCE_FIELD_SET:
-            case StaticUseKind.FIELD_INIT:
-            case StaticUseKind.FIELD_CONSTANT_INIT:
-              // These static uses are not relevant for this algorithm.
-              break;
-            case StaticUseKind.CALL_METHOD:
-            case StaticUseKind.INLINING:
-              failedAt(element, "Unexpected static use: $staticUse.");
-              break;
-          }
-        }, visitTypeUse: (MemberEntity member, TypeUse typeUse) {
-          void addClassIfInterfaceType(DartType t, [ImportEntity import]) {
-            var typeWithoutNullability = t.withoutNullability;
-            if (typeWithoutNullability is InterfaceType) {
-              dependencies.addClass(typeWithoutNullability.element, import);
-            }
-          }
-
-          DartType type = typeUse.type;
-          switch (typeUse.kind) {
-            case TypeUseKind.TYPE_LITERAL:
-              _collectTypeDependencies(
-                  type, dependencies, typeUse.deferredImport);
-              break;
-            case TypeUseKind.CONST_INSTANTIATION:
-              addClassIfInterfaceType(type, typeUse.deferredImport);
-              _collectTypeDependencies(
-                  type, dependencies, typeUse.deferredImport);
-              break;
-            case TypeUseKind.INSTANTIATION:
-            case TypeUseKind.NATIVE_INSTANTIATION:
-              addClassIfInterfaceType(type);
-              _collectTypeDependencies(type, dependencies);
-              break;
-            case TypeUseKind.IS_CHECK:
-            case TypeUseKind.CATCH_TYPE:
-              _collectTypeDependencies(type, dependencies);
-              break;
-            case TypeUseKind.AS_CAST:
-              if (closedWorld.annotationsData
-                  .getExplicitCastCheckPolicy(element)
-                  .isEmitted) {
-                _collectTypeDependencies(type, dependencies);
-              }
-              break;
-            case TypeUseKind.IMPLICIT_CAST:
-              if (closedWorld.annotationsData
-                  .getImplicitDowncastCheckPolicy(element)
-                  .isEmitted) {
-                _collectTypeDependencies(type, dependencies);
-              }
-              break;
-            case TypeUseKind.PARAMETER_CHECK:
-            case TypeUseKind.TYPE_VARIABLE_BOUND_CHECK:
-              if (closedWorld.annotationsData
-                  .getParameterCheckPolicy(element)
-                  .isEmitted) {
-                _collectTypeDependencies(type, dependencies);
-              }
-              break;
-            case TypeUseKind.RTI_VALUE:
-            case TypeUseKind.TYPE_ARGUMENT:
-            case TypeUseKind.NAMED_TYPE_VARIABLE_NEW_RTI:
-            case TypeUseKind.CONSTRUCTOR_REFERENCE:
-              failedAt(element, "Unexpected type use: $typeUse.");
-              break;
-          }
-        }, visitDynamicUse: (MemberEntity member, DynamicUse dynamicUse) {
-          // TODO(johnniwinther): Use rti need data to skip unneeded type
-          // arguments.
-          _collectTypeArgumentDependencies(
-              dynamicUse.typeArguments, dependencies);
-        }),
-        DeferredLoadTask.IMPACT_USE);
-  }
-
-  /// 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(
-      KClosedWorld closedWorld,
-      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) {
-        ClassEntity cls = constant.type.element;
-        _updateClassRecursive(closedWorld, cls, oldSet, newSet, queue);
-      }
-      if (constant is InstantiationConstantValue) {
-        for (DartType type in constant.typeArguments) {
-          type = type.withoutNullability;
-          if (type is InterfaceType) {
-            _updateClassRecursive(
-                closedWorld, type.element, oldSet, newSet, queue);
-          }
-        }
-      }
-      constant.getDependencies().forEach((ConstantValue dependency) {
-        // Constants are not allowed to refer to deferred constants, so
-        // no need to check for a deferred type literal here.
-        _updateConstantRecursive(
-            closedWorld, 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(closedWorld.dartTypes)} "
-              "to the main output unit, but it was assigned to $currentSet."));
-      queue.addConstant(constant, newSet);
-    }
-  }
-
-  void _updateClassRecursive(KClosedWorld closedWorld, ClassEntity element,
-      ImportSet oldSet, ImportSet newSet, WorkQueue queue) {
-    if (element == null) return;
-
-    ImportSet currentSet = _classToSet[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) 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].
-      _classToSet[element] = newSet;
-
-      Dependencies dependencies = Dependencies();
-      _collectAllElementsAndConstantsResolvedFromClass(
-          closedWorld, element, dependencies);
-      LibraryEntity library = element.library;
-      _processDependencies(
-          closedWorld, library, dependencies, oldSet, newSet, queue, element);
-    } else {
-      queue.addClass(element, newSet);
-    }
-  }
-
-  void _updateClassTypeRecursive(KClosedWorld closedWorld, ClassEntity element,
-      ImportSet oldSet, ImportSet newSet, WorkQueue queue) {
-    if (element == null) return;
-
-    ImportSet currentSet = _classTypeToSet[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) 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].
-      _classTypeToSet[element] = newSet;
-
-      Dependencies dependencies = Dependencies();
-      dependencies.addClassType(element);
-      LibraryEntity library = element.library;
-      _processDependencies(
-          closedWorld, library, dependencies, oldSet, newSet, queue, element);
-    } else {
-      queue.addClassType(element, newSet);
-    }
-  }
-
-  void _updateMemberRecursive(KClosedWorld closedWorld, MemberEntity element,
-      ImportSet oldSet, ImportSet newSet, WorkQueue queue) {
-    if (element == null) return;
-
-    ImportSet currentSet = _memberToSet[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) 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].
-      _memberToSet[element] = newSet;
-
-      Dependencies dependencies = Dependencies();
-      _collectAllElementsAndConstantsResolvedFromMember(
-          closedWorld, element, dependencies);
-
-      LibraryEntity library = element.library;
-      _processDependencies(
-          closedWorld, library, dependencies, oldSet, newSet, queue, element);
-    } else {
-      queue.addMember(element, newSet);
-    }
-  }
-
-  void _updateLocalFunction(
-      Local localFunction, ImportSet oldSet, ImportSet newSet) {
-    ImportSet currentSet = _localFunctionToSet[localFunction];
-    if (currentSet == newSet) return;
-
-    // Elements in the main output unit always remain there.
-    if (currentSet == importSets.mainSet) return;
-
-    if (currentSet == oldSet) {
-      _localFunctionToSet[localFunction] = newSet;
-    } else {
-      _localFunctionToSet[localFunction] = importSets.union(currentSet, newSet);
-    }
-    // Note: local functions are not updated recursively because the
-    // dependencies are already visited as dependencies of the enclosing member.
-  }
-
-  /// Whether to enqueue a deferred dependency.
-  ///
-  /// Due to the nature of the algorithm, some dependencies may be visited more
-  /// than once. However, we know that 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.
-  _shouldAddDeferredDependency(ImportSet newSet) => newSet.length <= 1;
-
-  void _processDependencies(
-      KClosedWorld closedWorld,
-      LibraryEntity library,
-      Dependencies dependencies,
-      ImportSet oldSet,
-      ImportSet newSet,
-      WorkQueue queue,
-      Spannable context) {
-    dependencies.classes.forEach((ClassEntity cls, DependencyInfo info) {
-      if (info.isDeferred) {
-        if (_shouldAddDeferredDependency(newSet)) {
-          for (ImportEntity deferredImport in info.imports) {
-            queue.addClass(cls, importSets.singleton(deferredImport));
-          }
-        }
-      } else {
-        _updateClassRecursive(closedWorld, cls, oldSet, newSet, queue);
-      }
-    });
-
-    dependencies.classType.forEach((ClassEntity cls, DependencyInfo info) {
-      if (info.isDeferred) {
-        if (_shouldAddDeferredDependency(newSet)) {
-          for (ImportEntity deferredImport in info.imports) {
-            queue.addClassType(cls, importSets.singleton(deferredImport));
-          }
-        }
-      } else {
-        _updateClassTypeRecursive(closedWorld, cls, oldSet, newSet, queue);
-      }
-    });
-
-    dependencies.members.forEach((MemberEntity member, DependencyInfo info) {
-      if (info.isDeferred) {
-        if (_shouldAddDeferredDependency(newSet)) {
-          for (ImportEntity deferredImport in info.imports) {
-            queue.addMember(member, importSets.singleton(deferredImport));
-          }
-        }
-      } else {
-        _updateMemberRecursive(closedWorld, member, oldSet, newSet, queue);
-      }
-    });
-
-    for (Local localFunction in dependencies.localFunctions) {
-      _updateLocalFunction(localFunction, oldSet, newSet);
-    }
-
-    dependencies.constants
-        .forEach((ConstantValue constant, DependencyInfo info) {
-      if (info.isDeferred) {
-        if (_shouldAddDeferredDependency(newSet)) {
-          for (ImportEntity deferredImport in info.imports) {
-            queue.addConstant(constant, importSets.singleton(deferredImport));
-          }
-        }
-      } else {
-        _updateConstantRecursive(closedWorld, constant, oldSet, newSet, queue);
-      }
-    });
-  }
-
   /// Computes a unique string for the name field for each outputUnit.
   void _createOutputUnits() {
     int counter = 1;
@@ -877,11 +374,7 @@
 
     // Generate an output unit for all import sets that are associated with an
     // element or constant.
-    _classToSet.values.forEach(addUnit);
-    _classTypeToSet.values.forEach(addUnit);
-    _memberToSet.values.forEach(addUnit);
-    _localFunctionToSet.values.forEach(addUnit);
-    _constantToSet.values.forEach(addUnit);
+    algorithmState?.entityToSet?.values?.forEach(addUnit);
 
     // Sort output units to make the output of the compiler more stable.
     _allOutputUnits.sort();
@@ -937,34 +430,8 @@
     }
 
     work() {
-      var queue = 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.addMember(main, importSets.mainSet);
-
-      // Also add "global" dependencies to the main output unit.  These are
-      // things that the backend needs but cannot associate with a particular
-      // element. This set also contains elements for which we lack precise
-      // information.
-      for (MemberEntity element
-          in closedWorld.backendUsage.globalFunctionDependencies) {
-        queue.addMember(element, importSets.mainSet);
-      }
-      for (ClassEntity element
-          in closedWorld.backendUsage.globalClassDependencies) {
-        queue.addClass(element, importSets.mainSet);
-      }
-
-      void emptyQueue() {
-        while (queue.isNotEmpty) {
-          WorkItem item = queue.nextItem();
-          item.update(this, closedWorld, queue);
-        }
-      }
-
-      emptyQueue();
+      algorithmState = AlgorithmState.create(
+          main, compiler, _elementMap, closedWorld, importSets);
     }
 
     reporter.withCurrentElement(main.library, () => measure(work));
@@ -1014,18 +481,22 @@
     Map<MemberEntity, OutputUnit> memberMap = {};
     Map<Local, OutputUnit> localFunctionMap = {};
     Map<ConstantValue, OutputUnit> constantMap = {};
-    _classToSet.forEach((cls, s) => classMap[cls] = s.unit);
-    _classTypeToSet.forEach((cls, s) => classTypeMap[cls] = s.unit);
-    _memberToSet.forEach((member, s) => memberMap[member] = s.unit);
-    _localFunctionToSet.forEach(
-        (localFunction, s) => localFunctionMap[localFunction] = s.unit);
-    _constantToSet.forEach((constant, s) => constantMap[constant] = s.unit);
-
-    _classToSet = null;
-    _classTypeToSet = null;
-    _memberToSet = null;
-    _localFunctionToSet = null;
-    _constantToSet = null;
+    algorithmState?.entityToSet?.forEach((d, s) {
+      if (d is ClassEntityData) {
+        classMap[d.entity] = s.unit;
+      } else if (d is ClassTypeEntityData) {
+        classTypeMap[d.entity] = s.unit;
+      } else if (d is MemberEntityData) {
+        memberMap[d.entity] = s.unit;
+      } else if (d is LocalFunctionEntityData) {
+        localFunctionMap[d.entity] = s.unit;
+      } else if (d is ConstantEntityData) {
+        constantMap[d.entity] = s.unit;
+      } else {
+        throw 'Unrecognized EntityData $d';
+      }
+    });
+    algorithmState = null;
     importSets = null;
     return OutputUnitData(
         this.isProgramSplit && !disableProgramSplit,
@@ -1057,53 +528,52 @@
     });
   }
 
-  bool ignoreEntityInDump(Entity element) => false;
-
   /// Creates a textual representation of the output unit content.
   String dump() {
     Map<OutputUnit, List<String>> elementMap = {};
     Map<OutputUnit, List<String>> constantMap = {};
-    _classToSet.forEach((ClassEntity element, ImportSet importSet) {
-      if (ignoreEntityInDump(element)) return;
-      var elements = elementMap.putIfAbsent(importSet.unit, () => <String>[]);
-      var id = element.name ?? '$element';
-      id = '$id cls';
-      elements.add(id);
-    });
-    _classTypeToSet.forEach((ClassEntity element, ImportSet importSet) {
-      if (ignoreEntityInDump(element)) return;
-      var elements = elementMap.putIfAbsent(importSet.unit, () => <String>[]);
-      var id = element.name ?? '$element';
-      id = '$id type';
-      elements.add(id);
-    });
-    _memberToSet.forEach((MemberEntity element, ImportSet importSet) {
-      if (ignoreEntityInDump(element)) return;
-      var elements = elementMap.putIfAbsent(importSet.unit, () => []);
-      var id = element.name ?? '$element';
-      var cls = element.enclosingClass?.name;
-      if (cls != null) id = '$cls.$id';
-      if (element.isSetter) id = '$id=';
-      id = '$id member';
-      elements.add(id);
-    });
-    _localFunctionToSet.forEach((Local element, ImportSet importSet) {
-      if (ignoreEntityInDump(element)) return;
-      var elements = elementMap.putIfAbsent(importSet.unit, () => []);
-      var id = element.name ?? '$element';
-      var context = (element as dynamic).memberContext.name;
-      id = element.name == null || element.name == '' ? '<anonymous>' : id;
-      id = '$context.$id';
-      id = '$id local';
-      elements.add(id);
-    });
-    _constantToSet.forEach((ConstantValue value, ImportSet importSet) {
-      // Skip primitive values: they are not stored in the constant tables and
-      // if they are shared, they end up duplicated anyways across output units.
-      if (value.isPrimitive) return;
-      constantMap
-          .putIfAbsent(importSet.unit, () => [])
-          .add(value.toStructuredText(dartTypes));
+    algorithmState?.entityToSet?.forEach((d, importSet) {
+      if (d is ClassEntityData) {
+        var element = d.entity;
+        var elements = elementMap.putIfAbsent(importSet.unit, () => <String>[]);
+        var id = element.name ?? '$element';
+        id = '$id cls';
+        elements.add(id);
+      } else if (d is ClassTypeEntityData) {
+        var element = d.entity;
+        var elements = elementMap.putIfAbsent(importSet.unit, () => <String>[]);
+        var id = element.name ?? '$element';
+        id = '$id type';
+        elements.add(id);
+      } else if (d is MemberEntityData) {
+        var element = d.entity;
+        var elements = elementMap.putIfAbsent(importSet.unit, () => []);
+        var id = element.name ?? '$element';
+        var cls = element.enclosingClass?.name;
+        if (cls != null) id = '$cls.$id';
+        if (element.isSetter) id = '$id=';
+        id = '$id member';
+        elements.add(id);
+      } else if (d is LocalFunctionEntityData) {
+        var element = d.entity;
+        var elements = elementMap.putIfAbsent(importSet.unit, () => []);
+        var id = element.name ?? '$element';
+        var context = (element as dynamic).memberContext.name;
+        id = element.name == null || element.name == '' ? '<anonymous>' : id;
+        id = '$context.$id';
+        id = '$id local';
+        elements.add(id);
+      } else if (d is ConstantEntityData) {
+        var value = d.entity;
+        // Skip primitive values: they are not stored in the constant tables and
+        // if they are shared, they end up duplicated anyways across output units.
+        if (value.isPrimitive) return;
+        constantMap
+            .putIfAbsent(importSet.unit, () => [])
+            .add(value.toStructuredText(dartTypes));
+      } else {
+        throw 'Unrecognized EntityData $d';
+      }
     });
 
     Map<OutputUnit, String> text = {};
diff --git a/pkg/compiler/lib/src/deferred_load/dependencies.dart b/pkg/compiler/lib/src/deferred_load/dependencies.dart
deleted file mode 100644
index c4579a5..0000000
--- a/pkg/compiler/lib/src/deferred_load/dependencies.dart
+++ /dev/null
@@ -1,250 +0,0 @@
-// Copyright (c) 2021, 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.
-
-import 'package:kernel/ast.dart' as ir;
-import 'package:kernel/type_environment.dart' as ir;
-
-import '../common_elements.dart' show CommonElements;
-import '../constants/values.dart'
-    show
-        ConstantValue;
-import '../elements/types.dart';
-import '../elements/entities.dart';
-import '../ir/util.dart';
-import '../kernel/element_map.dart';
-
-/// [Dependencies] is a helper for collecting per [Entity] [DependencyInfo].
-class Dependencies {
-  final Map<ClassEntity, DependencyInfo> classes = {};
-  final Map<ClassEntity, DependencyInfo> classType = {};
-  final Map<MemberEntity, DependencyInfo> members = {};
-  final Set<Local> localFunctions = {};
-  final Map<ConstantValue, DependencyInfo> constants = {};
-
-  void addClass(ClassEntity cls, [ImportEntity import]) {
-    (classes[cls] ??= DependencyInfo()).registerImport(import);
-
-    // Add a classType dependency as well just in case we optimize out
-    // the class later.
-    addClassType(cls, import);
-  }
-
-  void addClassType(ClassEntity cls, [ImportEntity import]) {
-    (classType[cls] ??= DependencyInfo()).registerImport(import);
-  }
-
-  void addMember(MemberEntity m, [ImportEntity import]) {
-    (members[m] ??= DependencyInfo()).registerImport(import);
-  }
-
-  void addConstant(ConstantValue c, [ImportEntity import]) {
-    (constants[c] ??= DependencyInfo()).registerImport(import);
-  }
-}
-
-class DependencyInfo {
-  bool isDeferred = true;
-  List<ImportEntity> imports;
-
-  registerImport(ImportEntity import) {
-    if (!isDeferred) return;
-    // A null import represents a direct non-deferred dependency.
-    if (import != null) {
-      (imports ??= []).add(import);
-    } else {
-      imports = null;
-      isDeferred = false;
-    }
-  }
-}
-
-class TypeDependencyVisitor implements DartTypeVisitor<void, Null> {
-  final Dependencies _dependencies;
-  final ImportEntity _import;
-  final CommonElements _commonElements;
-
-  TypeDependencyVisitor(this._dependencies, this._import, this._commonElements);
-
-  @override
-  void visit(DartType type, [_]) {
-    type.accept(this, null);
-  }
-
-  void visitList(List<DartType> types) {
-    types.forEach(visit);
-  }
-
-  @override
-  void visitLegacyType(LegacyType type, Null argument) {
-    visit(type.baseType);
-  }
-
-  @override
-  void visitNullableType(NullableType type, Null argument) {
-    visit(type.baseType);
-  }
-
-  @override
-  void visitFutureOrType(FutureOrType type, Null argument) {
-    _dependencies.addClassType(_commonElements.futureClass);
-    visit(type.typeArgument);
-  }
-
-  @override
-  void visitNeverType(NeverType type, Null argument) {
-    // Nothing to add.
-  }
-
-  @override
-  void visitDynamicType(DynamicType type, Null argument) {
-    // Nothing to add.
-  }
-
-  @override
-  void visitErasedType(ErasedType type, Null argument) {
-    // Nothing to add.
-  }
-
-  @override
-  void visitAnyType(AnyType type, Null argument) {
-    // Nothing to add.
-  }
-
-  @override
-  void visitInterfaceType(InterfaceType type, Null argument) {
-    visitList(type.typeArguments);
-    _dependencies.addClassType(type.element, _import);
-  }
-
-  @override
-  void visitFunctionType(FunctionType type, Null argument) {
-    for (FunctionTypeVariable typeVariable in type.typeVariables) {
-      visit(typeVariable.bound);
-    }
-    visitList(type.parameterTypes);
-    visitList(type.optionalParameterTypes);
-    visitList(type.namedParameterTypes);
-    visit(type.returnType);
-  }
-
-  @override
-  void visitFunctionTypeVariable(FunctionTypeVariable type, Null argument) {
-    // Nothing to add. Handled in [visitFunctionType].
-  }
-
-  @override
-  void visitTypeVariableType(TypeVariableType type, Null argument) {
-    // TODO(johnniwinther): Do we need to collect the bound?
-  }
-
-  @override
-  void visitVoidType(VoidType type, Null argument) {
-    // Nothing to add.
-  }
-}
-
-class ConstantCollector extends ir.RecursiveVisitor {
-  final KernelToElementMap elementMap;
-  final Dependencies dependencies;
-  final ir.StaticTypeContext staticTypeContext;
-
-  ConstantCollector(this.elementMap, this.staticTypeContext, this.dependencies);
-
-  CommonElements get commonElements => elementMap.commonElements;
-
-  void add(ir.Expression node, {bool required = true}) {
-    ConstantValue constant = elementMap
-        .getConstantValue(staticTypeContext, node, requireConstant: required);
-    if (constant != null) {
-      dependencies.addConstant(
-          constant, elementMap.getImport(getDeferredImport(node)));
-    }
-  }
-
-  @override
-  void visitIntLiteral(ir.IntLiteral literal) {}
-
-  @override
-  void visitDoubleLiteral(ir.DoubleLiteral literal) {}
-
-  @override
-  void visitBoolLiteral(ir.BoolLiteral literal) {}
-
-  @override
-  void visitStringLiteral(ir.StringLiteral literal) {}
-
-  @override
-  void visitSymbolLiteral(ir.SymbolLiteral literal) => add(literal);
-
-  @override
-  void visitNullLiteral(ir.NullLiteral literal) {}
-
-  @override
-  void visitListLiteral(ir.ListLiteral literal) {
-    if (literal.isConst) {
-      add(literal);
-    } else {
-      super.visitListLiteral(literal);
-    }
-  }
-
-  @override
-  void visitSetLiteral(ir.SetLiteral literal) {
-    if (literal.isConst) {
-      add(literal);
-    } else {
-      super.visitSetLiteral(literal);
-    }
-  }
-
-  @override
-  void visitMapLiteral(ir.MapLiteral literal) {
-    if (literal.isConst) {
-      add(literal);
-    } else {
-      super.visitMapLiteral(literal);
-    }
-  }
-
-  @override
-  void visitConstructorInvocation(ir.ConstructorInvocation node) {
-    if (node.isConst) {
-      add(node);
-    } else {
-      super.visitConstructorInvocation(node);
-    }
-  }
-
-  @override
-  void visitTypeParameter(ir.TypeParameter node) {
-    // We avoid visiting metadata on the type parameter declaration. The bound
-    // cannot hold constants so we skip that as well.
-  }
-
-  @override
-  void visitVariableDeclaration(ir.VariableDeclaration node) {
-    // We avoid visiting metadata on the parameter declaration by only visiting
-    // the initializer. The type cannot hold constants so can kan skip that
-    // as well.
-    node.initializer?.accept(this);
-  }
-
-  @override
-  void visitTypeLiteral(ir.TypeLiteral node) {
-    if (node.type is! ir.TypeParameterType) add(node);
-  }
-
-  @override
-  void visitInstantiation(ir.Instantiation node) {
-    // TODO(johnniwinther): The CFE should mark constant instantiations as
-    // constant.
-    add(node, required: false);
-    super.visitInstantiation(node);
-  }
-
-  @override
-  void visitConstantExpression(ir.ConstantExpression node) {
-    add(node);
-  }
-}
diff --git a/pkg/compiler/lib/src/deferred_load/entity_data.dart b/pkg/compiler/lib/src/deferred_load/entity_data.dart
new file mode 100644
index 0000000..bfb81f2
--- /dev/null
+++ b/pkg/compiler/lib/src/deferred_load/entity_data.dart
@@ -0,0 +1,108 @@
+// Copyright (c) 2021, 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.
+
+import '../constants/values.dart' show ConstantValue;
+import '../elements/entities.dart';
+
+/// [EntityData] is the base class of wrapped [Entity] objects. Each
+/// [EntityData] child knows how to use an [EntityDataCollector] to collect
+/// [EntityDataInfo]. [EntityData] objects are canonicalized and must be created
+/// by an [EntityDataRegistry].
+abstract class EntityData<T> {
+  final T entity;
+
+  EntityData(this.entity);
+
+  void accept(EntityDataVisitor visitor);
+
+  /// Whether or not the [EntityData] needs to be updated recursively.
+  bool get needsRecursiveUpdate => true;
+}
+
+class ClassEntityData extends EntityData<ClassEntity> {
+  @override
+  void accept(EntityDataVisitor visitor) {
+    visitor.visitClassEntityData(entity);
+  }
+
+  ClassEntityData(ClassEntity entity) : super(entity);
+}
+
+class ClassTypeEntityData extends EntityData<ClassEntity> {
+  @override
+  void accept(EntityDataVisitor visitor) {
+    visitor.visitClassTypeEntityData(entity);
+  }
+
+  ClassTypeEntityData(ClassEntity entity) : super(entity);
+}
+
+class MemberEntityData extends EntityData<MemberEntity> {
+  @override
+  void accept(EntityDataVisitor visitor) {
+    visitor.visitMemberEntityData(entity);
+  }
+
+  MemberEntityData(MemberEntity entity) : super(entity);
+}
+
+class LocalFunctionEntityData extends EntityData<Local> {
+  @override
+  void accept(EntityDataVisitor) {}
+
+  // Note: local functions are not updated recursively because the
+  // dependencies are already visited as dependencies of the enclosing member.
+  @override
+  bool get needsRecursiveUpdate => false;
+
+  LocalFunctionEntityData(Local entity) : super(entity);
+}
+
+class ConstantEntityData extends EntityData<ConstantValue> {
+  @override
+  void accept(EntityDataVisitor visitor) {
+    visitor.visitConstantEntityData(entity);
+  }
+
+  ConstantEntityData(ConstantValue entity) : super(entity);
+}
+
+/// A registry used to canonicalize [EntityData].
+class EntityDataRegistry {
+  /// Map of [Entity] / [ConstantValue] to [EntityData], used by all non
+  /// [ClassTypeEntityData].
+  final Map<Object, EntityData> _nonClassTypeData = {};
+
+  /// Map of [ClassEntity] to [EntityData], used by [ClassTypeEntityData].
+  final Map<ClassEntity, ClassTypeEntityData> _classTypeData = {};
+
+  EntityData createClassEntityData(ClassEntity cls) {
+    return _nonClassTypeData[cls] ??= ClassEntityData(cls);
+  }
+
+  EntityData createClassTypeEntityData(ClassEntity cls) {
+    return _classTypeData[cls] ??= ClassTypeEntityData(cls);
+  }
+
+  EntityData createConstantEntityData(ConstantValue constant) {
+    return _nonClassTypeData[constant] ??= ConstantEntityData(constant);
+  }
+
+  EntityData createLocalFunctionEntityData(Local localFunction) {
+    return _nonClassTypeData[localFunction] ??=
+        LocalFunctionEntityData(localFunction);
+  }
+
+  EntityData createMemberEntityData(MemberEntity member) {
+    return _nonClassTypeData[member] ??= MemberEntityData(member);
+  }
+}
+
+/// A trivial visitor to facilate interacting with [EntityData].
+abstract class EntityDataVisitor {
+  void visitClassEntityData(ClassEntity element);
+  void visitClassTypeEntityData(ClassEntity element);
+  void visitConstantEntityData(ConstantValue constant);
+  void visitMemberEntityData(MemberEntity member);
+}
diff --git a/pkg/compiler/lib/src/deferred_load/entity_data_info.dart b/pkg/compiler/lib/src/deferred_load/entity_data_info.dart
new file mode 100644
index 0000000..f3d9ecc
--- /dev/null
+++ b/pkg/compiler/lib/src/deferred_load/entity_data_info.dart
@@ -0,0 +1,568 @@
+// Copyright (c) 2021, 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.
+
+import 'package:kernel/ast.dart' as ir;
+import 'package:kernel/type_environment.dart' as ir;
+
+import 'deferred_load.dart';
+import 'entity_data.dart';
+
+import '../common.dart';
+import '../common_elements.dart' show CommonElements, KElementEnvironment;
+import '../compiler.dart' show Compiler;
+import '../constants/values.dart'
+    show ConstantValue, ConstructedConstantValue, InstantiationConstantValue;
+import '../elements/types.dart';
+import '../elements/entities.dart';
+import '../ir/util.dart';
+import '../kernel/kelements.dart' show KLocalFunction;
+import '../kernel/element_map.dart';
+import '../universe/use.dart';
+import '../universe/world_impact.dart'
+    show ImpactStrategy, WorldImpact, WorldImpactVisitorImpl;
+import '../world.dart' show KClosedWorld;
+
+/// [EntityDataInfo] is meta data about [EntityData] for a given compilation
+/// [Entity].
+class EntityDataInfo {
+  /// The deferred [EntityData] roots collected by the collector.
+  final Map<EntityData, List<ImportEntity>> deferredRoots = {};
+
+  /// The direct [EntityData] collected by the collector.
+  final Set<EntityData> directDependencies = {};
+
+  /// Various [add] methods for various types of direct dependencies.
+  void add(EntityData entityData, {ImportEntity import}) {
+    // If we already have a direct dependency on [entityData] then we have
+    // nothing left to do.
+    if (directDependencies.contains(entityData)) return;
+
+    // If [import] is null, then create a direct dependency on [entityData] and
+    // remove any deferred roots. Otherwise, add [import] to [deferredRoots] for
+    // [entityData].
+    if (import == null) {
+      deferredRoots.remove(entityData);
+      directDependencies.add(entityData);
+    } else {
+      (deferredRoots[entityData] ??= []).add(import);
+    }
+  }
+}
+
+/// Builds [EntityDataInfo] to help update dependencies of [EntityData] in the
+/// deferred_load algorithm.
+class EntityDataInfoBuilder {
+  final EntityDataInfo info = EntityDataInfo();
+  final KClosedWorld closedWorld;
+  final KernelToElementMap elementMap;
+  final Compiler compiler;
+  final EntityDataRegistry registry;
+
+  EntityDataInfoBuilder(
+      this.closedWorld, this.elementMap, this.compiler, this.registry);
+
+  Map<Entity, WorldImpact> get impactCache => compiler.impactCache;
+  ImpactStrategy get impactStrategy => compiler.impactStrategy;
+  KElementEnvironment get elementEnvironment =>
+      compiler.frontendStrategy.elementEnvironment;
+  CommonElements get commonElements => compiler.frontendStrategy.commonElements;
+
+  void add(EntityData data, {ImportEntity import}) {
+    info.add(data, import: import);
+  }
+
+  void addClass(ClassEntity cls, {ImportEntity import}) {
+    add(registry.createClassEntityData(cls), import: import);
+
+    // Add a classType entityData as well just in case we optimize out
+    // the class later.
+    addClassType(cls, import: import);
+  }
+
+  void addClassType(ClassEntity cls, {ImportEntity import}) {
+    add(registry.createClassTypeEntityData(cls), import: import);
+  }
+
+  void addMember(MemberEntity m, {ImportEntity import}) {
+    add(registry.createMemberEntityData(m), import: import);
+  }
+
+  void addConstant(ConstantValue c, {ImportEntity import}) {
+    add(registry.createConstantEntityData(c), import: import);
+  }
+
+  void addLocalFunction(Local localFunction) {
+    add(registry.createLocalFunctionEntityData(localFunction));
+  }
+
+  /// Recursively collects all the dependencies of [type].
+  void addTypeDependencies(DartType type, [ImportEntity import]) {
+    TypeEntityDataVisitor(this, import, commonElements).visit(type);
+  }
+
+  /// Recursively collects all the dependencies of [types].
+  void addTypeListDependencies(Iterable<DartType> types,
+      [ImportEntity import]) {
+    if (types == null) return;
+    TypeEntityDataVisitor(this, import, commonElements).visitList(types);
+  }
+
+  /// Collects all direct dependencies of [element].
+  ///
+  /// The collected dependent elements and constants are are added to
+  /// [elements] and [constants] respectively.
+  void addDirectMemberDependencies(MemberEntity element) {
+    // TODO(sigurdm): We want to be more specific about this - need a better
+    // way to query "liveness".
+    if (!closedWorld.isMemberUsed(element)) {
+      return;
+    }
+    _addDependenciesFromImpact(element);
+    ConstantCollector.collect(elementMap, element, this);
+  }
+
+  void _addFromStaticUse(MemberEntity parent, StaticUse staticUse) {
+    void processEntity() {
+      Entity usedEntity = staticUse.element;
+      if (usedEntity is MemberEntity) {
+        addMember(usedEntity, import: staticUse.deferredImport);
+      } else {
+        assert(usedEntity is KLocalFunction,
+            failedAt(usedEntity, "Unexpected static use $staticUse."));
+        KLocalFunction localFunction = usedEntity;
+        // TODO(sra): Consult KClosedWorld to see if signature is needed.
+        addTypeDependencies(localFunction.functionType);
+        addLocalFunction(localFunction);
+      }
+    }
+
+    switch (staticUse.kind) {
+      case StaticUseKind.CONSTRUCTOR_INVOKE:
+      case StaticUseKind.CONST_CONSTRUCTOR_INVOKE:
+        // The receiver type of generative constructors is a entityData of
+        // the constructor (handled by `addMember` above) and not a
+        // entityData at the call site.
+        // Factory methods, on the other hand, are like static methods so
+        // the target type is not relevant.
+        // TODO(johnniwinther): Use rti need data to skip unneeded type
+        // arguments.
+        addTypeListDependencies(staticUse.type.typeArguments);
+        processEntity();
+        break;
+      case StaticUseKind.STATIC_INVOKE:
+      case StaticUseKind.CLOSURE_CALL:
+      case StaticUseKind.DIRECT_INVOKE:
+        // TODO(johnniwinther): Use rti need data to skip unneeded type
+        // arguments.
+        addTypeListDependencies(staticUse.typeArguments);
+        processEntity();
+        break;
+      case StaticUseKind.STATIC_TEAR_OFF:
+      case StaticUseKind.CLOSURE:
+      case StaticUseKind.STATIC_GET:
+      case StaticUseKind.STATIC_SET:
+        processEntity();
+        break;
+      case StaticUseKind.SUPER_TEAR_OFF:
+      case StaticUseKind.SUPER_FIELD_SET:
+      case StaticUseKind.SUPER_GET:
+      case StaticUseKind.SUPER_SETTER_SET:
+      case StaticUseKind.SUPER_INVOKE:
+      case StaticUseKind.INSTANCE_FIELD_GET:
+      case StaticUseKind.INSTANCE_FIELD_SET:
+      case StaticUseKind.FIELD_INIT:
+      case StaticUseKind.FIELD_CONSTANT_INIT:
+        // These static uses are not relevant for this algorithm.
+        break;
+      case StaticUseKind.CALL_METHOD:
+      case StaticUseKind.INLINING:
+        failedAt(parent, "Unexpected static use: $staticUse.");
+        break;
+    }
+  }
+
+  void _addFromTypeUse(MemberEntity parent, TypeUse typeUse) {
+    void addClassIfInterfaceType(DartType t, [ImportEntity import]) {
+      var typeWithoutNullability = t.withoutNullability;
+      if (typeWithoutNullability is InterfaceType) {
+        addClass(typeWithoutNullability.element, import: import);
+      }
+    }
+
+    DartType type = typeUse.type;
+    switch (typeUse.kind) {
+      case TypeUseKind.TYPE_LITERAL:
+        addTypeDependencies(type, typeUse.deferredImport);
+        break;
+      case TypeUseKind.CONST_INSTANTIATION:
+        addClassIfInterfaceType(type, typeUse.deferredImport);
+        addTypeDependencies(type, typeUse.deferredImport);
+        break;
+      case TypeUseKind.INSTANTIATION:
+      case TypeUseKind.NATIVE_INSTANTIATION:
+        addClassIfInterfaceType(type);
+        addTypeDependencies(type);
+        break;
+      case TypeUseKind.IS_CHECK:
+      case TypeUseKind.CATCH_TYPE:
+        addTypeDependencies(type);
+        break;
+      case TypeUseKind.AS_CAST:
+        if (closedWorld.annotationsData
+            .getExplicitCastCheckPolicy(parent)
+            .isEmitted) {
+          addTypeDependencies(type);
+        }
+        break;
+      case TypeUseKind.IMPLICIT_CAST:
+        if (closedWorld.annotationsData
+            .getImplicitDowncastCheckPolicy(parent)
+            .isEmitted) {
+          addTypeDependencies(type);
+        }
+        break;
+      case TypeUseKind.PARAMETER_CHECK:
+      case TypeUseKind.TYPE_VARIABLE_BOUND_CHECK:
+        if (closedWorld.annotationsData
+            .getParameterCheckPolicy(parent)
+            .isEmitted) {
+          addTypeDependencies(type);
+        }
+        break;
+      case TypeUseKind.RTI_VALUE:
+      case TypeUseKind.TYPE_ARGUMENT:
+      case TypeUseKind.NAMED_TYPE_VARIABLE_NEW_RTI:
+      case TypeUseKind.CONSTRUCTOR_REFERENCE:
+        failedAt(parent, "Unexpected type use: $typeUse.");
+        break;
+    }
+  }
+
+  /// Extract any dependencies that are known from the impact of [element].
+  void _addDependenciesFromImpact(MemberEntity element) {
+    WorldImpact worldImpact = impactCache[element];
+    impactStrategy.visitImpact(
+        element,
+        worldImpact,
+        WorldImpactVisitorImpl(
+            visitStaticUse: (MemberEntity member, StaticUse staticUse) {
+          _addFromStaticUse(element, staticUse);
+        }, visitTypeUse: (MemberEntity member, TypeUse typeUse) {
+          _addFromTypeUse(element, typeUse);
+        }, visitDynamicUse: (MemberEntity member, DynamicUse dynamicUse) {
+          // TODO(johnniwinther): Use rti need data to skip unneeded type
+          // arguments.
+          addTypeListDependencies(dynamicUse.typeArguments);
+        }),
+        DeferredLoadTask.IMPACT_USE);
+  }
+}
+
+/// Collects the necessary [EntityDataInfo] for a given [EntityData].
+class EntityDataInfoVisitor extends EntityDataVisitor {
+  final EntityDataInfoBuilder infoBuilder;
+
+  EntityDataInfoVisitor(this.infoBuilder);
+
+  KClosedWorld get closedWorld => infoBuilder.closedWorld;
+  KElementEnvironment get elementEnvironment =>
+      infoBuilder.compiler.frontendStrategy.elementEnvironment;
+
+  /// Finds all elements and constants that [element] depends directly on.
+  /// (not the transitive closure.)
+  ///
+  /// Adds the results to [elements] and [constants].
+  @override
+  void visitClassEntityData(ClassEntity element) {
+    // If we see a class, add everything its live instance members refer
+    // to.  Static members are not relevant, unless we are processing
+    // extra dependencies due to mirrors.
+    void addLiveInstanceMember(MemberEntity member) {
+      if (!closedWorld.isMemberUsed(member)) return;
+      if (!member.isInstanceMember) return;
+      infoBuilder.addMember(member);
+      infoBuilder.addDirectMemberDependencies(member);
+    }
+
+    void addClassAndMaybeAddEffectiveMixinClass(ClassEntity cls) {
+      infoBuilder.addClass(cls);
+      if (elementEnvironment.isMixinApplication(cls)) {
+        infoBuilder.addClass(elementEnvironment.getEffectiveMixinClass(cls));
+      }
+    }
+
+    ClassEntity cls = element;
+    elementEnvironment.forEachLocalClassMember(cls, addLiveInstanceMember);
+    elementEnvironment.forEachSupertype(cls, (InterfaceType type) {
+      infoBuilder.addTypeDependencies(type);
+    });
+    elementEnvironment.forEachSuperClass(cls, (superClass) {
+      addClassAndMaybeAddEffectiveMixinClass(superClass);
+      infoBuilder
+          .addTypeDependencies(elementEnvironment.getThisType(superClass));
+    });
+    addClassAndMaybeAddEffectiveMixinClass(cls);
+  }
+
+  @override
+  void visitClassTypeEntityData(ClassEntity element) {
+    infoBuilder.addClassType(element);
+  }
+
+  /// Finds all elements and constants that [element] depends directly on.
+  /// (not the transitive closure.)
+  ///
+  /// Adds the results to [elements] and [constants].
+  @override
+  void visitMemberEntityData(MemberEntity element) {
+    if (element is FunctionEntity) {
+      infoBuilder
+          .addTypeDependencies(elementEnvironment.getFunctionType(element));
+    }
+    if (element.isStatic || element.isTopLevel || element.isConstructor) {
+      infoBuilder.addMember(element);
+      infoBuilder.addDirectMemberDependencies(element);
+    }
+    if (element is ConstructorEntity && element.isGenerativeConstructor) {
+      // When instantiating a class, we record a reference to the
+      // constructor, not the class itself.  We must add all the
+      // instance members of the constructor's class.
+      ClassEntity cls = element.enclosingClass;
+      visitClassEntityData(cls);
+    }
+
+    // Other elements, in particular instance members, are ignored as
+    // they are processed as part of the class.
+  }
+
+  @override
+  void visitConstantEntityData(ConstantValue constant) {
+    if (constant is ConstructedConstantValue) {
+      infoBuilder.addClass(constant.type.element);
+    }
+    if (constant is InstantiationConstantValue) {
+      for (DartType type in constant.typeArguments) {
+        type = type.withoutNullability;
+        if (type is InterfaceType) {
+          infoBuilder.addClass(type.element);
+        }
+      }
+    }
+
+    // Constants are not allowed to refer to deferred constants, so
+    // no need to check for a deferred type literal here.
+    constant.getDependencies().forEach(infoBuilder.addConstant);
+  }
+}
+
+class TypeEntityDataVisitor implements DartTypeVisitor<void, Null> {
+  final EntityDataInfoBuilder _infoBuilder;
+  final ImportEntity _import;
+  final CommonElements _commonElements;
+
+  TypeEntityDataVisitor(this._infoBuilder, this._import, this._commonElements);
+
+  @override
+  void visit(DartType type, [_]) {
+    type.accept(this, null);
+  }
+
+  void visitList(List<DartType> types) {
+    types.forEach(visit);
+  }
+
+  @override
+  void visitLegacyType(LegacyType type, Null argument) {
+    visit(type.baseType);
+  }
+
+  @override
+  void visitNullableType(NullableType type, Null argument) {
+    visit(type.baseType);
+  }
+
+  @override
+  void visitFutureOrType(FutureOrType type, Null argument) {
+    _infoBuilder.addClassType(_commonElements.futureClass);
+    visit(type.typeArgument);
+  }
+
+  @override
+  void visitNeverType(NeverType type, Null argument) {
+    // Nothing to add.
+  }
+
+  @override
+  void visitDynamicType(DynamicType type, Null argument) {
+    // Nothing to add.
+  }
+
+  @override
+  void visitErasedType(ErasedType type, Null argument) {
+    // Nothing to add.
+  }
+
+  @override
+  void visitAnyType(AnyType type, Null argument) {
+    // Nothing to add.
+  }
+
+  @override
+  void visitInterfaceType(InterfaceType type, Null argument) {
+    visitList(type.typeArguments);
+    _infoBuilder.addClassType(type.element, import: _import);
+  }
+
+  @override
+  void visitFunctionType(FunctionType type, Null argument) {
+    for (FunctionTypeVariable typeVariable in type.typeVariables) {
+      visit(typeVariable.bound);
+    }
+    visitList(type.parameterTypes);
+    visitList(type.optionalParameterTypes);
+    visitList(type.namedParameterTypes);
+    visit(type.returnType);
+  }
+
+  @override
+  void visitFunctionTypeVariable(FunctionTypeVariable type, Null argument) {
+    // Nothing to add. Handled in [visitFunctionType].
+  }
+
+  @override
+  void visitTypeVariableType(TypeVariableType type, Null argument) {
+    // TODO(johnniwinther): Do we need to collect the bound?
+  }
+
+  @override
+  void visitVoidType(VoidType type, Null argument) {
+    // Nothing to add.
+  }
+}
+
+class ConstantCollector extends ir.RecursiveVisitor {
+  final KernelToElementMap elementMap;
+  final EntityDataInfoBuilder infoBuilder;
+  final ir.StaticTypeContext staticTypeContext;
+
+  ConstantCollector(this.elementMap, this.staticTypeContext, this.infoBuilder);
+
+  CommonElements get commonElements => elementMap.commonElements;
+
+  /// Extract the set of constants that are used in the body of [member].
+  static void collect(KernelToElementMap elementMap, MemberEntity member,
+      EntityDataInfoBuilder infoBuilder) {
+    ir.Member node = elementMap.getMemberNode(member);
+
+    // Fetch the internal node in order to skip annotations on the member.
+    // TODO(sigmund): replace this pattern when the kernel-ast provides a better
+    // way to skip annotations (issue 31565).
+    var visitor = ConstantCollector(
+        elementMap, elementMap.getStaticTypeContext(member), infoBuilder);
+    if (node is ir.Field) {
+      node.initializer?.accept(visitor);
+      return;
+    }
+
+    if (node is ir.Constructor) {
+      node.initializers.forEach((i) => i.accept(visitor));
+    }
+    node.function?.accept(visitor);
+  }
+
+  void add(ir.Expression node, {bool required = true}) {
+    ConstantValue constant = elementMap
+        .getConstantValue(staticTypeContext, node, requireConstant: required);
+    if (constant != null) {
+      infoBuilder.addConstant(constant,
+          import: elementMap.getImport(getDeferredImport(node)));
+    }
+  }
+
+  @override
+  void visitIntLiteral(ir.IntLiteral literal) {}
+
+  @override
+  void visitDoubleLiteral(ir.DoubleLiteral literal) {}
+
+  @override
+  void visitBoolLiteral(ir.BoolLiteral literal) {}
+
+  @override
+  void visitStringLiteral(ir.StringLiteral literal) {}
+
+  @override
+  void visitSymbolLiteral(ir.SymbolLiteral literal) => add(literal);
+
+  @override
+  void visitNullLiteral(ir.NullLiteral literal) {}
+
+  @override
+  void visitListLiteral(ir.ListLiteral literal) {
+    if (literal.isConst) {
+      add(literal);
+    } else {
+      super.visitListLiteral(literal);
+    }
+  }
+
+  @override
+  void visitSetLiteral(ir.SetLiteral literal) {
+    if (literal.isConst) {
+      add(literal);
+    } else {
+      super.visitSetLiteral(literal);
+    }
+  }
+
+  @override
+  void visitMapLiteral(ir.MapLiteral literal) {
+    if (literal.isConst) {
+      add(literal);
+    } else {
+      super.visitMapLiteral(literal);
+    }
+  }
+
+  @override
+  void visitConstructorInvocation(ir.ConstructorInvocation node) {
+    if (node.isConst) {
+      add(node);
+    } else {
+      super.visitConstructorInvocation(node);
+    }
+  }
+
+  @override
+  void visitTypeParameter(ir.TypeParameter node) {
+    // We avoid visiting metadata on the type parameter declaration. The bound
+    // cannot hold constants so we skip that as well.
+  }
+
+  @override
+  void visitVariableDeclaration(ir.VariableDeclaration node) {
+    // We avoid visiting metadata on the parameter declaration by only visiting
+    // the initializer. The type cannot hold constants so can kan skip that
+    // as well.
+    node.initializer?.accept(this);
+  }
+
+  @override
+  void visitTypeLiteral(ir.TypeLiteral node) {
+    if (node.type is! ir.TypeParameterType) add(node);
+  }
+
+  @override
+  void visitInstantiation(ir.Instantiation node) {
+    // TODO(johnniwinther): The CFE should mark constant instantiations as
+    // constant.
+    add(node, required: false);
+    super.visitInstantiation(node);
+  }
+
+  @override
+  void visitConstantExpression(ir.ConstantExpression node) {
+    add(node);
+  }
+}
diff --git a/pkg/compiler/lib/src/deferred_load/output_unit.dart b/pkg/compiler/lib/src/deferred_load/output_unit.dart
index 1b9f93a..17daef0 100644
--- a/pkg/compiler/lib/src/deferred_load/output_unit.dart
+++ b/pkg/compiler/lib/src/deferred_load/output_unit.dart
@@ -6,9 +6,7 @@
 
 import '../common.dart';
 import '../constants/values.dart'
-    show
-        ConstantValue,
-        DeferredGlobalConstantValue;
+    show ConstantValue, DeferredGlobalConstantValue;
 import '../elements/entities.dart';
 import '../serialization/serialization.dart';
 import '../options.dart';
diff --git a/pkg/compiler/lib/src/deferred_load/work_queue.dart b/pkg/compiler/lib/src/deferred_load/work_queue.dart
index 42adfbc..90bf329 100644
--- a/pkg/compiler/lib/src/deferred_load/work_queue.dart
+++ b/pkg/compiler/lib/src/deferred_load/work_queue.dart
@@ -2,30 +2,30 @@
 // 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.
 
-part of deferred_load;
+import 'dart:collection' show Queue;
 
-/// The deferred_load algorithm work queue.
+import 'algorithm_state.dart';
+import 'entity_data.dart';
+import 'import_set.dart';
+
+import '../elements/entities.dart';
+
+/// The entity_data_state work queue.
 class WorkQueue {
   /// The actual queue of work that needs to be done.
   final Queue<WorkItem> queue = Queue();
 
-  /// An index to find work items in the queue corresponding to a class.
-  final Map<ClassEntity, WorkItem> pendingClasses = {};
-
-  /// An index to find work items in the queue corresponding to an
-  /// [InterfaceType] represented here by its [ClassEntitiy].
-  final Map<ClassEntity, WorkItem> pendingClassType = {};
-
-  /// An index to find work items in the queue corresponding to a member.
-  final Map<MemberEntity, WorkItem> pendingMembers = {};
-
-  /// An index to find work items in the queue corresponding to a constant.
-  final Map<ConstantValue, WorkItem> pendingConstants = {};
+  /// An index to find work items in the queue corresponding to a given
+  /// [EntityData].
+  final Map<EntityData, WorkItem> pendingWorkItems = {};
 
   /// Lattice used to compute unions of [ImportSet]s.
   final ImportSetLattice _importSets;
 
-  WorkQueue(this._importSets);
+  /// Registry used to create [EntityData].
+  final EntityDataRegistry _registry;
+
+  WorkQueue(this._importSets, this._registry);
 
   /// Whether there are no more work items in the queue.
   bool get isNotEmpty => queue.isNotEmpty;
@@ -40,66 +40,40 @@
   /// 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 addClass(ClassEntity element, ImportSet importSet) {
-    var item = pendingClasses[element];
+  void addEntityData(EntityData entityData, ImportSet importSet) {
+    var item = pendingWorkItems[entityData];
     if (item == null) {
-      item = ClassWorkItem(element, importSet);
-      pendingClasses[element] = item;
+      item = WorkItem(entityData, importSet);
+      pendingWorkItems[entityData] = item;
       queue.add(item);
     } else {
       item.importsToAdd = _importSets.union(item.importsToAdd, importSet);
     }
   }
 
-  /// Add to the queue that class type (represented by [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 addClassType(ClassEntity element, ImportSet importSet) {
-    var item = pendingClassType[element];
-    if (item == null) {
-      item = ClassTypeWorkItem(element, importSet);
-      pendingClassType[element] = item;
-      queue.add(item);
-    } else {
-      item.importsToAdd = _importSets.union(item.importsToAdd, importSet);
-    }
+  void addMember(MemberEntity member, ImportSet importSet) {
+    addEntityData(_registry.createMemberEntityData(member), importSet);
   }
 
-  /// 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 addMember(MemberEntity element, ImportSet importSet) {
-    var item = pendingMembers[element];
-    if (item == null) {
-      item = MemberWorkItem(element, importSet);
-      pendingMembers[element] = item;
-      queue.add(item);
-    } else {
-      item.importsToAdd = _importSets.union(item.importsToAdd, importSet);
-    }
+  void addClass(ClassEntity cls, ImportSet importSet) {
+    addEntityData(_registry.createClassEntityData(cls), importSet);
   }
 
-  /// 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 = ConstantWorkItem(constant, importSet);
-      pendingConstants[constant] = item;
-      queue.add(item);
-    } else {
-      item.importsToAdd = _importSets.union(item.importsToAdd, importSet);
-    }
+  /// Processes the next item in the queue.
+  void processNextItem(AlgorithmState state) {
+    var item = nextItem();
+    var entityData = item.entityData;
+    pendingWorkItems.remove(entityData);
+    ImportSet oldSet = state.entityToSet[entityData];
+    ImportSet newSet = _importSets.union(oldSet, item.importsToAdd);
+    state.update(entityData, oldSet, newSet);
   }
 }
 
 /// Summary of the work that needs to be done on a class, member, or constant.
-abstract class WorkItem {
+class WorkItem {
+  final EntityData entityData;
+
   /// Additional imports that use [element] or [value] and need to be added by
   /// the algorithm.
   ///
@@ -108,75 +82,5 @@
   /// [WorkQueue.addConstant]).
   ImportSet importsToAdd;
 
-  WorkItem(this.importsToAdd);
-
-  void update(DeferredLoadTask task, KClosedWorld closedWorld, WorkQueue queue);
-}
-
-/// Summary of the work that needs to be done on a class.
-class ClassWorkItem extends WorkItem {
-  /// Class to be recursively updated.
-  final ClassEntity cls;
-
-  ClassWorkItem(this.cls, ImportSet newSet) : super(newSet);
-
-  @override
-  void update(
-      DeferredLoadTask task, KClosedWorld closedWorld, WorkQueue queue) {
-    queue.pendingClasses.remove(cls);
-    ImportSet oldSet = task._classToSet[cls];
-    ImportSet newSet = task.importSets.union(oldSet, importsToAdd);
-    task._updateClassRecursive(closedWorld, cls, oldSet, newSet, queue);
-  }
-}
-
-/// Summary of the work that needs to be done on a class.
-class ClassTypeWorkItem extends WorkItem {
-  /// Class to be recursively updated.
-  final ClassEntity cls;
-
-  ClassTypeWorkItem(this.cls, ImportSet newSet) : super(newSet);
-
-  @override
-  void update(
-      DeferredLoadTask task, KClosedWorld closedWorld, WorkQueue queue) {
-    queue.pendingClassType.remove(cls);
-    ImportSet oldSet = task._classTypeToSet[cls];
-    ImportSet newSet = task.importSets.union(oldSet, importsToAdd);
-    task._updateClassTypeRecursive(closedWorld, cls, oldSet, newSet, queue);
-  }
-}
-
-/// Summary of the work that needs to be done on a member.
-class MemberWorkItem extends WorkItem {
-  /// Member to be recursively updated.
-  final MemberEntity member;
-
-  MemberWorkItem(this.member, ImportSet newSet) : super(newSet);
-
-  @override
-  void update(
-      DeferredLoadTask task, KClosedWorld closedWorld, WorkQueue queue) {
-    queue.pendingMembers.remove(member);
-    ImportSet oldSet = task._memberToSet[member];
-    ImportSet newSet = task.importSets.union(oldSet, importsToAdd);
-    task._updateMemberRecursive(closedWorld, member, oldSet, newSet, queue);
-  }
-}
-
-/// Summary of the work that needs to be done on a constant.
-class ConstantWorkItem extends WorkItem {
-  /// Constant to be recursively updated.
-  final ConstantValue constant;
-
-  ConstantWorkItem(this.constant, ImportSet newSet) : super(newSet);
-
-  @override
-  void update(
-      DeferredLoadTask task, KClosedWorld closedWorld, WorkQueue queue) {
-    queue.pendingConstants.remove(constant);
-    ImportSet oldSet = task._constantToSet[constant];
-    ImportSet newSet = task.importSets.union(oldSet, importsToAdd);
-    task._updateConstantRecursive(closedWorld, constant, oldSet, newSet, queue);
-  }
+  WorkItem(this.entityData, this.importsToAdd);
 }
diff --git a/pkg/compiler/test/deferred/not_in_main_test.dart b/pkg/compiler/test/deferred/not_in_main_test.dart
index 11e92a3..d3e13bd 100644
--- a/pkg/compiler/test/deferred/not_in_main_test.dart
+++ b/pkg/compiler/test/deferred/not_in_main_test.dart
@@ -110,7 +110,7 @@
   dynamic shared = lookupLibrary("memory:shared.dart");
   var a = env.lookupClass(shared, "A");
   Expect.equals(
-      "OutputUnit(1, {import(def2: deferred), import(def3: deferred)})",
+      "OutputUnit(4, {import(def2: deferred), import(def3: deferred)})",
       outputUnitForClass(a).toString());
   Expect.equals(
       "OutputUnit(2, {import(def1: deferred), "
diff --git a/pkg/compiler/test/deferred_loading/data/deferred_overlapping/deferred_overlapping_lib3.dart b/pkg/compiler/test/deferred_loading/data/deferred_overlapping/deferred_overlapping_lib3.dart
index 55ced68..34b9387 100644
--- a/pkg/compiler/test/deferred_loading/data/deferred_overlapping/deferred_overlapping_lib3.dart
+++ b/pkg/compiler/test/deferred_loading/data/deferred_overlapping/deferred_overlapping_lib3.dart
@@ -5,8 +5,8 @@
 // @dart = 2.7
 
 /*class: C3:
- class_unit=1{lib1, lib2},
- type_unit=1{lib1, lib2}
+ class_unit=2{lib1, lib2},
+ type_unit=2{lib1, lib2}
 */
-/*member: C3.:member_unit=1{lib1, lib2}*/
+/*member: C3.:member_unit=2{lib1, lib2}*/
 class C3 {}
diff --git a/pkg/compiler/test/deferred_loading/data/deferred_overlapping/lib1.dart b/pkg/compiler/test/deferred_loading/data/deferred_overlapping/lib1.dart
index ca698b0..39babb0 100644
--- a/pkg/compiler/test/deferred_loading/data/deferred_overlapping/lib1.dart
+++ b/pkg/compiler/test/deferred_loading/data/deferred_overlapping/lib1.dart
@@ -7,8 +7,8 @@
 import "deferred_overlapping_lib3.dart";
 
 /*class: C1:
- class_unit=2{lib1},
- type_unit=2{lib1}
+ class_unit=1{lib1},
+ type_unit=1{lib1}
 */
-/*member: C1.:member_unit=2{lib1}*/
+/*member: C1.:member_unit=1{lib1}*/
 class C1 extends C3 {}
diff --git a/pkg/compiler/test/deferred_loading/data/deferred_overlapping/main.dart b/pkg/compiler/test/deferred_loading/data/deferred_overlapping/main.dart
index 11062ba..acd021d 100644
--- a/pkg/compiler/test/deferred_loading/data/deferred_overlapping/main.dart
+++ b/pkg/compiler/test/deferred_loading/data/deferred_overlapping/main.dart
@@ -4,13 +4,13 @@
 
 /*spec.library: 
  a_pre_fragments=[
-  p1: {units: [2{lib1}], usedBy: [], needs: []},
+  p1: {units: [1{lib1}], usedBy: [], needs: []},
   p2: {units: [3{lib2}], usedBy: [], needs: []},
-  p3: {units: [1{lib1, lib2}], usedBy: [], needs: []}],
+  p3: {units: [2{lib1, lib2}], usedBy: [], needs: []}],
  b_finalized_fragments=[
-  f1: [2{lib1}],
+  f1: [1{lib1}],
   f2: [3{lib2}],
-  f3: [1{lib1, lib2}]],
+  f3: [2{lib1, lib2}]],
  c_steps=[
   lib1=(f3, f1),
   lib2=(f3, f2)]
@@ -18,13 +18,13 @@
 
 /*two-frag|three-frag.library: 
  a_pre_fragments=[
-  p1: {units: [2{lib1}], usedBy: [p3], needs: []},
+  p1: {units: [1{lib1}], usedBy: [p3], needs: []},
   p2: {units: [3{lib2}], usedBy: [p3], needs: []},
-  p3: {units: [1{lib1, lib2}], usedBy: [], needs: [p1, p2]}],
+  p3: {units: [2{lib1, lib2}], usedBy: [], needs: [p1, p2]}],
  b_finalized_fragments=[
-  f1: [2{lib1}],
+  f1: [1{lib1}],
   f2: [3{lib2}],
-  f3: [1{lib1, lib2}]],
+  f3: [2{lib1, lib2}]],
  c_steps=[
   lib1=(f3, f1),
   lib2=(f3, f2)]
diff --git a/pkg/compiler/test/deferred_loading/data/instantiation2/lib1.dart b/pkg/compiler/test/deferred_loading/data/instantiation2/lib1.dart
index 50dde94..59fba08 100644
--- a/pkg/compiler/test/deferred_loading/data/instantiation2/lib1.dart
+++ b/pkg/compiler/test/deferred_loading/data/instantiation2/lib1.dart
@@ -4,14 +4,14 @@
 
 // @dart = 2.7
 
-/*member: getFoo:member_unit=2{b}*/
+/*member: getFoo:member_unit=1{b}*/
 T getFoo<T>(T v) => v;
 
 typedef dynamic G<T>(T v);
 
 /*member: m:
- constants=[InstantiationConstant([int*],FunctionConstant(getFoo))=2{b}],
- member_unit=2{b}
+ constants=[InstantiationConstant([int*],FunctionConstant(getFoo))=1{b}],
+ member_unit=1{b}
 */
 m(int x, {G<int> f: getFoo}) {
   print(f(x));
diff --git a/pkg/compiler/test/deferred_loading/data/instantiation2/main.dart b/pkg/compiler/test/deferred_loading/data/instantiation2/main.dart
index 66b862e..bf10d09 100644
--- a/pkg/compiler/test/deferred_loading/data/instantiation2/main.dart
+++ b/pkg/compiler/test/deferred_loading/data/instantiation2/main.dart
@@ -4,13 +4,13 @@
 
 /*spec.library: 
  a_pre_fragments=[
-  p1: {units: [2{b}], usedBy: [], needs: []},
+  p1: {units: [1{b}], usedBy: [], needs: []},
   p2: {units: [3{c}], usedBy: [], needs: []},
-  p3: {units: [1{b, c}], usedBy: [], needs: []}],
+  p3: {units: [2{b, c}], usedBy: [], needs: []}],
  b_finalized_fragments=[
-  f1: [2{b}],
+  f1: [1{b}],
   f2: [3{c}],
-  f3: [1{b, c}]],
+  f3: [2{b, c}]],
  c_steps=[
   b=(f3, f1),
   c=(f3, f2)]
@@ -18,13 +18,13 @@
 
 /*two-frag|three-frag.library: 
  a_pre_fragments=[
-  p1: {units: [2{b}], usedBy: [p3], needs: []},
+  p1: {units: [1{b}], usedBy: [p3], needs: []},
   p2: {units: [3{c}], usedBy: [p3], needs: []},
-  p3: {units: [1{b, c}], usedBy: [], needs: [p1, p2]}],
+  p3: {units: [2{b, c}], usedBy: [], needs: [p1, p2]}],
  b_finalized_fragments=[
-  f1: [2{b}],
+  f1: [1{b}],
   f2: [3{c}],
-  f3: [1{b, c}]],
+  f3: [2{b, c}]],
  c_steps=[
   b=(f3, f1),
   c=(f3, f2)]
@@ -35,8 +35,14 @@
 // Test instantiations with the same type argument count used only in two
 // deferred libraries.
 
-/*class: global#Instantiation:class_unit=1{b, c},type_unit=1{b, c}*/
-/*class: global#Instantiation1:class_unit=1{b, c},type_unit=1{b, c}*/
+/*class: global#Instantiation:
+ class_unit=2{b, c},
+ type_unit=2{b, c}
+*/
+/*class: global#Instantiation1:
+ class_unit=2{b, c},
+ type_unit=2{b, c}
+*/
 
 import 'lib1.dart' deferred as b;
 import 'lib2.dart' deferred as c;
diff --git a/pkg/compiler/test/deferred_loading/data/instantiation5/lib1.dart b/pkg/compiler/test/deferred_loading/data/instantiation5/lib1.dart
index 506a6b3..a211ccb 100644
--- a/pkg/compiler/test/deferred_loading/data/instantiation5/lib1.dart
+++ b/pkg/compiler/test/deferred_loading/data/instantiation5/lib1.dart
@@ -4,14 +4,14 @@
 
 // @dart = 2.7
 
-/*member: getFoo:member_unit=2{b}*/
+/*member: getFoo:member_unit=1{b}*/
 T getFoo<T>(T v) => v;
 
 typedef dynamic G<T>(T v);
 
 /*member: m:
- constants=[InstantiationConstant([int*],FunctionConstant(getFoo))=2{b}],
- member_unit=2{b}
+ constants=[InstantiationConstant([int*],FunctionConstant(getFoo))=1{b}],
+ member_unit=1{b}
 */
 m(int x, {G<int> f}) {
   f ??= getFoo;
diff --git a/pkg/compiler/test/deferred_loading/data/instantiation5/main.dart b/pkg/compiler/test/deferred_loading/data/instantiation5/main.dart
index 2150985..0ba4442 100644
--- a/pkg/compiler/test/deferred_loading/data/instantiation5/main.dart
+++ b/pkg/compiler/test/deferred_loading/data/instantiation5/main.dart
@@ -4,13 +4,13 @@
 
 /*spec.library: 
  a_pre_fragments=[
-  p1: {units: [2{b}], usedBy: [], needs: []},
+  p1: {units: [1{b}], usedBy: [], needs: []},
   p2: {units: [3{c}], usedBy: [], needs: []},
-  p3: {units: [1{b, c}], usedBy: [], needs: []}],
+  p3: {units: [2{b, c}], usedBy: [], needs: []}],
  b_finalized_fragments=[
-  f1: [2{b}],
+  f1: [1{b}],
   f2: [3{c}],
-  f3: [1{b, c}]],
+  f3: [2{b, c}]],
  c_steps=[
   b=(f3, f1),
   c=(f3, f2)]
@@ -18,13 +18,13 @@
 
 /*two-frag|three-frag.library: 
  a_pre_fragments=[
-  p1: {units: [2{b}], usedBy: [p3], needs: []},
+  p1: {units: [1{b}], usedBy: [p3], needs: []},
   p2: {units: [3{c}], usedBy: [p3], needs: []},
-  p3: {units: [1{b, c}], usedBy: [], needs: [p1, p2]}],
+  p3: {units: [2{b, c}], usedBy: [], needs: [p1, p2]}],
  b_finalized_fragments=[
-  f1: [2{b}],
+  f1: [1{b}],
   f2: [3{c}],
-  f3: [1{b, c}]],
+  f3: [2{b, c}]],
  c_steps=[
   b=(f3, f1),
   c=(f3, f2)]
@@ -35,10 +35,16 @@
 // Test instantiations with the same type argument count used only in two
 // deferred libraries.
 
-/*class: global#Instantiation:class_unit=1{b, c},type_unit=1{b, c}*/
-/*class: global#Instantiation1:class_unit=1{b, c},type_unit=1{b, c}*/
+/*class: global#Instantiation:
+ class_unit=2{b, c},
+ type_unit=2{b, c}
+*/
+/*class: global#Instantiation1:
+ class_unit=2{b, c},
+ type_unit=2{b, c}
+*/
 
-/*member: global#instantiate1:member_unit=1{b, c}*/
+/*member: global#instantiate1:member_unit=2{b, c}*/
 
 import 'lib1.dart' deferred as b;
 import 'lib2.dart' deferred as c;
diff --git a/pkg/compiler/test/deferred_loading/data/lazy_types/lib.dart b/pkg/compiler/test/deferred_loading/data/lazy_types/lib.dart
index 22064c8..d797b5b 100644
--- a/pkg/compiler/test/deferred_loading/data/lazy_types/lib.dart
+++ b/pkg/compiler/test/deferred_loading/data/lazy_types/lib.dart
@@ -5,28 +5,28 @@
 // @dart = 2.7
 
 /*class: Foo:
- class_unit=1{libB},
- type_unit=3{libA, libB, libC}
+ class_unit=4{libB},
+ type_unit=2{libA, libB, libC}
 */
 class Foo {
-  /*member: Foo.x:member_unit=1{libB}*/
+  /*member: Foo.x:member_unit=4{libB}*/
   int x;
-  /*member: Foo.:member_unit=1{libB}*/
+  /*member: Foo.:member_unit=4{libB}*/
   Foo() {
     x = DateTime.now().millisecond;
   }
-  /*member: Foo.method:member_unit=1{libB}*/
+  /*member: Foo.method:member_unit=4{libB}*/
   @pragma('dart2js:noInline')
   int method() => x;
 }
 
-/*member: isFoo:member_unit=3{libA, libB, libC}*/
+/*member: isFoo:member_unit=2{libA, libB, libC}*/
 @pragma('dart2js:noInline')
 bool isFoo(o) {
   return o is Foo;
 }
 
-/*member: callFooMethod:member_unit=1{libB}*/
+/*member: callFooMethod:member_unit=4{libB}*/
 @pragma('dart2js:noInline')
 int callFooMethod() {
   return Foo().method();
@@ -35,7 +35,7 @@
 typedef int FunFoo(Foo a);
 typedef int FunFunFoo(FunFoo b, int c);
 
-/*member: isFunFunFoo:member_unit=3{libA, libB, libC}*/
+/*member: isFunFunFoo:member_unit=2{libA, libB, libC}*/
 @pragma('dart2js:noInline')
 bool isFunFunFoo(o) {
   return o is FunFunFoo;
@@ -43,88 +43,88 @@
 
 /*class: Aoo:
  class_unit=none,
- type_unit=2{libC}
+ type_unit=6{libC}
 */
 class Aoo<T> {}
 
 /*class: Boo:
- class_unit=2{libC},
- type_unit=2{libC}
+ class_unit=6{libC},
+ type_unit=6{libC}
 */
 class Boo<T> implements Aoo<T> {}
 
 /*class: Coo:
- class_unit=2{libC},
- type_unit=2{libC}
+ class_unit=6{libC},
+ type_unit=6{libC}
 */
-/*member: Coo.:member_unit=2{libC}*/
+/*member: Coo.:member_unit=6{libC}*/
 class Coo<T> {}
 
 /*class: Doo:
- class_unit=2{libC},
+ class_unit=6{libC},
  type_unit=5{libB, libC}
 */
-/*member: Doo.:member_unit=2{libC}*/
+/*member: Doo.:member_unit=6{libC}*/
 class Doo<T> extends Coo<T> with Boo<T> {}
 
-/*member: createDooFunFunFoo:member_unit=2{libC}*/
+/*member: createDooFunFunFoo:member_unit=6{libC}*/
 @pragma('dart2js:noInline')
 createDooFunFunFoo() => Doo<FunFunFoo>();
 
 /*class: B:
- class_unit=2{libC},
- type_unit=2{libC}
+ class_unit=6{libC},
+ type_unit=6{libC}
 */
-/*member: B.:member_unit=2{libC}*/
+/*member: B.:member_unit=6{libC}*/
 class B {}
 
 /*class: B2:
- class_unit=2{libC},
- type_unit=4{libA, libC}
+ class_unit=6{libC},
+ type_unit=3{libA, libC}
 */
-/*member: B2.:member_unit=2{libC}*/
+/*member: B2.:member_unit=6{libC}*/
 class B2 extends B {}
 
 /*class: C1:
- class_unit=2{libC},
- type_unit=2{libC}
+ class_unit=6{libC},
+ type_unit=6{libC}
 */
 class C1 {}
 
 /*class: C2:
- class_unit=2{libC},
- type_unit=2{libC}
+ class_unit=6{libC},
+ type_unit=6{libC}
 */
-/*member: C2.:member_unit=2{libC}*/
+/*member: C2.:member_unit=6{libC}*/
 class C2 {}
 
 /*class: C3:
- class_unit=2{libC},
- type_unit=4{libA, libC}
+ class_unit=6{libC},
+ type_unit=3{libA, libC}
 */
-/*member: C3.:member_unit=2{libC}*/
+/*member: C3.:member_unit=6{libC}*/
 class C3 extends C2 with C1 {}
 
 /*class: D1:
- class_unit=2{libC},
- type_unit=2{libC}
+ class_unit=6{libC},
+ type_unit=6{libC}
 */
 class D1 {}
 
 /*class: D2:
- class_unit=2{libC},
- type_unit=2{libC}
+ class_unit=6{libC},
+ type_unit=6{libC}
 */
-/*member: D2.:member_unit=2{libC}*/
+/*member: D2.:member_unit=6{libC}*/
 class D2 {}
 
 /*class: D3:
- class_unit=2{libC},
- type_unit=4{libA, libC}
+ class_unit=6{libC},
+ type_unit=3{libA, libC}
 */
 class D3 = D2 with D1;
 
-/*member: isMega:member_unit=6{libA}*/
+/*member: isMega:member_unit=1{libA}*/
 @pragma('dart2js:noInline')
 bool isMega(o) {
   return o is B2 || o is C3 || o is D3;
diff --git a/pkg/compiler/test/deferred_loading/data/lazy_types/liba.dart b/pkg/compiler/test/deferred_loading/data/lazy_types/liba.dart
index 447ec58..072f8fc 100644
--- a/pkg/compiler/test/deferred_loading/data/lazy_types/liba.dart
+++ b/pkg/compiler/test/deferred_loading/data/lazy_types/liba.dart
@@ -6,11 +6,11 @@
 
 import 'lib.dart' as lib;
 
-/*member: isFoo:member_unit=6{libA}*/
+/*member: isFoo:member_unit=1{libA}*/
 bool isFoo(o) => lib.isFoo(o);
 
-/*member: isFunFunFoo:member_unit=6{libA}*/
+/*member: isFunFunFoo:member_unit=1{libA}*/
 bool isFunFunFoo(o) => lib.isFunFunFoo(o);
 
-/*member: isMega:member_unit=6{libA}*/
+/*member: isMega:member_unit=1{libA}*/
 bool isMega(o) => lib.isMega(o);
diff --git a/pkg/compiler/test/deferred_loading/data/lazy_types/libb.dart b/pkg/compiler/test/deferred_loading/data/lazy_types/libb.dart
index 20c2423..fffb803 100644
--- a/pkg/compiler/test/deferred_loading/data/lazy_types/libb.dart
+++ b/pkg/compiler/test/deferred_loading/data/lazy_types/libb.dart
@@ -6,14 +6,14 @@
 
 import 'lib.dart' as lib;
 
-/*member: callFooMethod:member_unit=1{libB}*/
+/*member: callFooMethod:member_unit=4{libB}*/
 int callFooMethod() => lib.callFooMethod();
 
-/*member: isFoo:member_unit=1{libB}*/
+/*member: isFoo:member_unit=4{libB}*/
 bool isFoo(o) => lib.isFoo(o);
 
-/*member: isFunFunFoo:member_unit=1{libB}*/
+/*member: isFunFunFoo:member_unit=4{libB}*/
 bool isFunFunFoo(o) => lib.isFunFunFoo(o);
 
-/*member: isDooFunFunFoo:member_unit=1{libB}*/
+/*member: isDooFunFunFoo:member_unit=4{libB}*/
 bool isDooFunFunFoo(o) => o is lib.Doo<lib.FunFunFoo>;
diff --git a/pkg/compiler/test/deferred_loading/data/lazy_types/libc.dart b/pkg/compiler/test/deferred_loading/data/lazy_types/libc.dart
index ddc592e..a9a20f2 100644
--- a/pkg/compiler/test/deferred_loading/data/lazy_types/libc.dart
+++ b/pkg/compiler/test/deferred_loading/data/lazy_types/libc.dart
@@ -6,20 +6,20 @@
 
 import 'lib.dart' as lib;
 
-/*member: isFoo:member_unit=2{libC}*/
+/*member: isFoo:member_unit=6{libC}*/
 bool isFoo(o) => lib.isFoo(o);
 
-/*member: isFunFunFoo:member_unit=2{libC}*/
+/*member: isFunFunFoo:member_unit=6{libC}*/
 bool isFunFunFoo(o) => lib.isFunFunFoo(o);
 
-/*member: createB2:member_unit=2{libC}*/
+/*member: createB2:member_unit=6{libC}*/
 createB2() => new lib.B2();
 
-/*member: createC3:member_unit=2{libC}*/
+/*member: createC3:member_unit=6{libC}*/
 createC3() => new lib.C3();
 
-/*member: createD3:member_unit=2{libC}*/
+/*member: createD3:member_unit=6{libC}*/
 createD3() => new lib.D3();
 
-/*member: createDooFunFunFoo:member_unit=2{libC}*/
+/*member: createDooFunFunFoo:member_unit=6{libC}*/
 createDooFunFunFoo() => lib.createDooFunFunFoo();
diff --git a/pkg/compiler/test/deferred_loading/data/lazy_types/main.dart b/pkg/compiler/test/deferred_loading/data/lazy_types/main.dart
index 0c00e5e..8ed7162 100644
--- a/pkg/compiler/test/deferred_loading/data/lazy_types/main.dart
+++ b/pkg/compiler/test/deferred_loading/data/lazy_types/main.dart
@@ -4,17 +4,17 @@
 
 /*spec.library: 
  a_pre_fragments=[
-  p1: {units: [6{libA}], usedBy: [], needs: []},
-  p2: {units: [1{libB}], usedBy: [], needs: []},
-  p3: {units: [2{libC}], usedBy: [], needs: []},
-  p4: {units: [4{libA, libC}], usedBy: [], needs: []},
+  p1: {units: [1{libA}], usedBy: [], needs: []},
+  p2: {units: [4{libB}], usedBy: [], needs: []},
+  p3: {units: [6{libC}], usedBy: [], needs: []},
+  p4: {units: [3{libA, libC}], usedBy: [], needs: []},
   p5: {units: [5{libB, libC}], usedBy: [], needs: []},
-  p6: {units: [3{libA, libB, libC}], usedBy: [], needs: []}],
+  p6: {units: [2{libA, libB, libC}], usedBy: [], needs: []}],
  b_finalized_fragments=[
-  f1: [6{libA}],
-  f2: [1{libB}],
-  f3: [2{libC}],
-  f6: [3{libA, libB, libC}]],
+  f1: [1{libA}],
+  f2: [4{libB}],
+  f3: [6{libC}],
+  f6: [2{libA, libB, libC}]],
  c_steps=[
   libA=(f6, f1),
   libB=(f6, f2),
@@ -23,13 +23,13 @@
 
 /*two-frag.library: 
  a_pre_fragments=[
-  p1: {units: [1{libB}, 6{libA}], usedBy: [p2, p3], needs: []},
-  p2: {units: [4{libA, libC}, 2{libC}], usedBy: [p3], needs: [p1]},
-  p3: {units: [3{libA, libB, libC}, 5{libB, libC}], usedBy: [], needs: [p2, p1]}],
+  p1: {units: [4{libB}, 1{libA}], usedBy: [p2, p3], needs: []},
+  p2: {units: [3{libA, libC}, 6{libC}], usedBy: [p3], needs: [p1]},
+  p3: {units: [2{libA, libB, libC}, 5{libB, libC}], usedBy: [], needs: [p2, p1]}],
  b_finalized_fragments=[
-  f1: [1{libB}, 6{libA}],
-  f2: [2{libC}],
-  f3: [3{libA, libB, libC}]],
+  f1: [4{libB}, 1{libA}],
+  f2: [6{libC}],
+  f3: [2{libA, libB, libC}]],
  c_steps=[
   libA=(f3, f1),
   libB=(f3, f1),
@@ -38,15 +38,15 @@
 
 /*three-frag.library: 
  a_pre_fragments=[
-  p1: {units: [6{libA}], usedBy: [p4], needs: []},
-  p2: {units: [1{libB}], usedBy: [p4], needs: []},
-  p3: {units: [2{libC}], usedBy: [p4], needs: []},
-  p4: {units: [3{libA, libB, libC}, 5{libB, libC}, 4{libA, libC}], usedBy: [], needs: [p3, p2, p1]}],
+  p1: {units: [1{libA}], usedBy: [p4], needs: []},
+  p2: {units: [4{libB}], usedBy: [p4], needs: []},
+  p3: {units: [6{libC}], usedBy: [p4], needs: []},
+  p4: {units: [2{libA, libB, libC}, 5{libB, libC}, 3{libA, libC}], usedBy: [], needs: [p3, p2, p1]}],
  b_finalized_fragments=[
-  f1: [6{libA}],
-  f2: [1{libB}],
-  f3: [2{libC}],
-  f4: [3{libA, libB, libC}]],
+  f1: [1{libA}],
+  f2: [4{libB}],
+  f3: [6{libC}],
+  f4: [2{libA, libB, libC}]],
  c_steps=[
   libA=(f4, f1),
   libB=(f4, f2),
@@ -61,19 +61,19 @@
 
 /*member: foo:
  constants=[
-  FunctionConstant(callFooMethod)=1{libB},
-  FunctionConstant(createB2)=2{libC},
-  FunctionConstant(createC3)=2{libC},
-  FunctionConstant(createD3)=2{libC},
-  FunctionConstant(createDooFunFunFoo)=2{libC},
-  FunctionConstant(isDooFunFunFoo)=1{libB},
-  FunctionConstant(isFoo)=1{libB},
-  FunctionConstant(isFoo)=2{libC},
-  FunctionConstant(isFoo)=6{libA},
-  FunctionConstant(isFunFunFoo)=1{libB},
-  FunctionConstant(isFunFunFoo)=2{libC},
-  FunctionConstant(isFunFunFoo)=6{libA},
-  FunctionConstant(isMega)=6{libA}],
+  FunctionConstant(callFooMethod)=4{libB},
+  FunctionConstant(createB2)=6{libC},
+  FunctionConstant(createC3)=6{libC},
+  FunctionConstant(createD3)=6{libC},
+  FunctionConstant(createDooFunFunFoo)=6{libC},
+  FunctionConstant(isDooFunFunFoo)=4{libB},
+  FunctionConstant(isFoo)=1{libA},
+  FunctionConstant(isFoo)=4{libB},
+  FunctionConstant(isFoo)=6{libC},
+  FunctionConstant(isFunFunFoo)=1{libA},
+  FunctionConstant(isFunFunFoo)=4{libB},
+  FunctionConstant(isFunFunFoo)=6{libC},
+  FunctionConstant(isMega)=1{libA}],
  member_unit=main{}
 */
 void foo() async {
diff --git a/pkg/compiler/test/deferred_loading/data/many_parts/libB.dart b/pkg/compiler/test/deferred_loading/data/many_parts/libB.dart
index 7f86fc1..8fa7f8e 100644
--- a/pkg/compiler/test/deferred_loading/data/many_parts/libB.dart
+++ b/pkg/compiler/test/deferred_loading/data/many_parts/libB.dart
@@ -4,14 +4,14 @@
 
 import "package:expect/expect.dart";
 
-/*member: v:member_unit=1{b1, b2, b3, b4, b5}*/
+/*member: v:member_unit=2{b1, b2, b3, b4, b5}*/
 void v(Set<String> u, String name, int bit) {
   Expect.isTrue(u.add(name));
   Expect.equals(name[bit], '1');
 }
 
 @pragma('dart2js:noInline')
-/*member: f_000_01:member_unit=2{b1}*/
+/*member: f_000_01:member_unit=1{b1}*/
 f_000_01(Set<String> u, int b) => v(u, '00001', b);
 
 @pragma('dart2js:noInline')
@@ -71,7 +71,7 @@
 f_111_01(Set<String> u, int b) => v(u, '11101', b);
 
 @pragma('dart2js:noInline')
-/*member: f_111_11:member_unit=1{b1, b2, b3, b4, b5}*/
+/*member: f_111_11:member_unit=2{b1, b2, b3, b4, b5}*/
 f_111_11(Set<String> u, int b) => v(u, '11111', b);
 
 @pragma('dart2js:noInline')
diff --git a/pkg/compiler/test/deferred_loading/data/many_parts/lib_000_01.dart b/pkg/compiler/test/deferred_loading/data/many_parts/lib_000_01.dart
index 94e3cf7..bb1e6d9 100644
--- a/pkg/compiler/test/deferred_loading/data/many_parts/lib_000_01.dart
+++ b/pkg/compiler/test/deferred_loading/data/many_parts/lib_000_01.dart
@@ -7,7 +7,7 @@
 import 'libB.dart';
 
 @pragma('dart2js:noInline')
-/*member: g_000_01:member_unit=2{b1}*/
+/*member: g_000_01:member_unit=1{b1}*/
 g_000_01() {
   Set<String> uniques = {};
 
diff --git a/pkg/compiler/test/deferred_loading/data/many_parts/main.dart b/pkg/compiler/test/deferred_loading/data/many_parts/main.dart
index cbb56aa..ab6a217 100644
--- a/pkg/compiler/test/deferred_loading/data/many_parts/main.dart
+++ b/pkg/compiler/test/deferred_loading/data/many_parts/main.dart
@@ -14,7 +14,7 @@
   p17: {units: [7{b1, b2, b4}], usedBy: [], needs: []},
   p18: {units: [11{b1, b2, b5}], usedBy: [], needs: []},
   p19: {units: [8{b1, b3, b4}], usedBy: [], needs: []},
-  p1: {units: [2{b1}], usedBy: [], needs: []},
+  p1: {units: [1{b1}], usedBy: [], needs: []},
   p20: {units: [12{b1, b3, b5}], usedBy: [], needs: []},
   p21: {units: [14{b1, b4, b5}], usedBy: [], needs: []},
   p22: {units: [20{b2, b3, b4}], usedBy: [], needs: []},
@@ -27,7 +27,7 @@
   p29: {units: [16{b1, b3, b4, b5}], usedBy: [], needs: []},
   p2: {units: [17{b2}], usedBy: [], needs: []},
   p30: {units: [24{b2, b3, b4, b5}], usedBy: [], needs: []},
-  p31: {units: [1{b1, b2, b3, b4, b5}], usedBy: [], needs: []},
+  p31: {units: [2{b1, b2, b3, b4, b5}], usedBy: [], needs: []},
   p3: {units: [25{b3}], usedBy: [], needs: []},
   p4: {units: [29{b4}], usedBy: [], needs: []},
   p5: {units: [31{b5}], usedBy: [], needs: []},
@@ -46,7 +46,7 @@
   f17: [7{b1, b2, b4}],
   f18: [11{b1, b2, b5}],
   f19: [8{b1, b3, b4}],
-  f1: [2{b1}],
+  f1: [1{b1}],
   f20: [12{b1, b3, b5}],
   f21: [14{b1, b4, b5}],
   f22: [20{b2, b3, b4}],
@@ -59,7 +59,7 @@
   f29: [16{b1, b3, b4, b5}],
   f2: [17{b2}],
   f30: [24{b2, b3, b4, b5}],
-  f31: [1{b1, b2, b3, b4, b5}],
+  f31: [2{b1, b2, b3, b4, b5}],
   f3: [25{b3}],
   f4: [29{b4}],
   f5: [31{b5}],
@@ -77,15 +77,15 @@
 
 /*three-frag.library: 
  a_pre_fragments=[
-  p1: {units: [26{b3, b4}, 21{b2, b5}, 19{b2, b4}, 18{b2, b3}, 10{b1, b5}, 6{b1, b4}, 4{b1, b3}, 3{b1, b2}, 31{b5}, 29{b4}, 25{b3}, 17{b2}, 2{b1}], usedBy: [p2], needs: []},
+  p1: {units: [26{b3, b4}, 21{b2, b5}, 19{b2, b4}, 18{b2, b3}, 10{b1, b5}, 6{b1, b4}, 4{b1, b3}, 3{b1, b2}, 31{b5}, 29{b4}, 25{b3}, 17{b2}, 1{b1}], usedBy: [p2], needs: []},
   p2: {units: [9{b1, b2, b3, b4}, 28{b3, b4, b5}, 23{b2, b4, b5}, 22{b2, b3, b5}, 20{b2, b3, b4}, 14{b1, b4, b5}, 12{b1, b3, b5}, 8{b1, b3, b4}, 11{b1, b2, b5}, 7{b1, b2, b4}, 5{b1, b2, b3}, 30{b4, b5}, 27{b3, b5}], usedBy: [p4, p3], needs: [p1]},
   p3: {units: [24{b2, b3, b4, b5}, 16{b1, b3, b4, b5}, 15{b1, b2, b4, b5}, 13{b1, b2, b3, b5}], usedBy: [p4], needs: [p2]},
-  p4: {units: [1{b1, b2, b3, b4, b5}], usedBy: [], needs: [p2, p3]}],
+  p4: {units: [2{b1, b2, b3, b4, b5}], usedBy: [], needs: [p2, p3]}],
  b_finalized_fragments=[
-  f1: [26{b3, b4}, 21{b2, b5}, 19{b2, b4}, 18{b2, b3}, 10{b1, b5}, 6{b1, b4}, 4{b1, b3}, 3{b1, b2}, 31{b5}, 29{b4}, 25{b3}, 17{b2}, 2{b1}],
+  f1: [26{b3, b4}, 21{b2, b5}, 19{b2, b4}, 18{b2, b3}, 10{b1, b5}, 6{b1, b4}, 4{b1, b3}, 3{b1, b2}, 31{b5}, 29{b4}, 25{b3}, 17{b2}, 1{b1}],
   f2: [9{b1, b2, b3, b4}, 28{b3, b4, b5}, 23{b2, b4, b5}, 22{b2, b3, b5}, 20{b2, b3, b4}, 14{b1, b4, b5}, 12{b1, b3, b5}, 8{b1, b3, b4}, 11{b1, b2, b5}, 7{b1, b2, b4}, 5{b1, b2, b3}, 30{b4, b5}, 27{b3, b5}],
   f3: [24{b2, b3, b4, b5}, 16{b1, b3, b4, b5}, 15{b1, b2, b4, b5}, 13{b1, b2, b3, b5}],
-  f4: [1{b1, b2, b3, b4, b5}]],
+  f4: [2{b1, b2, b3, b4, b5}]],
  c_steps=[
   b1=(f4, f3, f2, f1),
   b2=(f4, f3, f2, f1),
@@ -96,13 +96,13 @@
 
 /*two-frag.library: 
  a_pre_fragments=[
-  p1: {units: [12{b1, b3, b5}, 8{b1, b3, b4}, 11{b1, b2, b5}, 7{b1, b2, b4}, 5{b1, b2, b3}, 30{b4, b5}, 27{b3, b5}, 26{b3, b4}, 21{b2, b5}, 19{b2, b4}, 18{b2, b3}, 10{b1, b5}, 6{b1, b4}, 4{b1, b3}, 3{b1, b2}, 31{b5}, 29{b4}, 25{b3}, 17{b2}, 2{b1}], usedBy: [p2], needs: []},
+  p1: {units: [12{b1, b3, b5}, 8{b1, b3, b4}, 11{b1, b2, b5}, 7{b1, b2, b4}, 5{b1, b2, b3}, 30{b4, b5}, 27{b3, b5}, 26{b3, b4}, 21{b2, b5}, 19{b2, b4}, 18{b2, b3}, 10{b1, b5}, 6{b1, b4}, 4{b1, b3}, 3{b1, b2}, 31{b5}, 29{b4}, 25{b3}, 17{b2}, 1{b1}], usedBy: [p2], needs: []},
   p2: {units: [24{b2, b3, b4, b5}, 16{b1, b3, b4, b5}, 15{b1, b2, b4, b5}, 13{b1, b2, b3, b5}, 9{b1, b2, b3, b4}, 28{b3, b4, b5}, 23{b2, b4, b5}, 22{b2, b3, b5}, 20{b2, b3, b4}, 14{b1, b4, b5}], usedBy: [p3], needs: [p1]},
-  p3: {units: [1{b1, b2, b3, b4, b5}], usedBy: [], needs: [p2]}],
+  p3: {units: [2{b1, b2, b3, b4, b5}], usedBy: [], needs: [p2]}],
  b_finalized_fragments=[
-  f1: [12{b1, b3, b5}, 8{b1, b3, b4}, 11{b1, b2, b5}, 7{b1, b2, b4}, 5{b1, b2, b3}, 30{b4, b5}, 27{b3, b5}, 26{b3, b4}, 21{b2, b5}, 19{b2, b4}, 18{b2, b3}, 10{b1, b5}, 6{b1, b4}, 4{b1, b3}, 3{b1, b2}, 31{b5}, 29{b4}, 25{b3}, 17{b2}, 2{b1}],
+  f1: [12{b1, b3, b5}, 8{b1, b3, b4}, 11{b1, b2, b5}, 7{b1, b2, b4}, 5{b1, b2, b3}, 30{b4, b5}, 27{b3, b5}, 26{b3, b4}, 21{b2, b5}, 19{b2, b4}, 18{b2, b3}, 10{b1, b5}, 6{b1, b4}, 4{b1, b3}, 3{b1, b2}, 31{b5}, 29{b4}, 25{b3}, 17{b2}, 1{b1}],
   f2: [24{b2, b3, b4, b5}, 16{b1, b3, b4, b5}, 15{b1, b2, b4, b5}, 13{b1, b2, b3, b5}, 9{b1, b2, b3, b4}, 28{b3, b4, b5}, 23{b2, b4, b5}, 22{b2, b3, b5}, 20{b2, b3, b4}, 14{b1, b4, b5}],
-  f3: [1{b1, b2, b3, b4, b5}]],
+  f3: [2{b1, b2, b3, b4, b5}]],
  c_steps=[
   b1=(f3, f2, f1),
   b2=(f3, f2, f1),
diff --git a/pkg/compiler/test/deferred_loading/data/type_arguments/lib3.dart b/pkg/compiler/test/deferred_loading/data/type_arguments/lib3.dart
index 9b56057..3147280 100644
--- a/pkg/compiler/test/deferred_loading/data/type_arguments/lib3.dart
+++ b/pkg/compiler/test/deferred_loading/data/type_arguments/lib3.dart
@@ -5,8 +5,8 @@
 // @dart = 2.7
 
 /*class: E:
- class_unit=2{lib3},
- type_unit=2{lib3}
+ class_unit=3{lib3},
+ type_unit=3{lib3}
 */
 class E<T> {
   const E();
@@ -14,7 +14,7 @@
 
 /*class: F:
  class_unit=none,
- type_unit=3{lib1, lib3}
+ type_unit=2{lib1, lib3}
 */
 class F {}
 
diff --git a/pkg/compiler/test/deferred_loading/data/type_arguments/main.dart b/pkg/compiler/test/deferred_loading/data/type_arguments/main.dart
index 6703cb1..86f5ed6 100644
--- a/pkg/compiler/test/deferred_loading/data/type_arguments/main.dart
+++ b/pkg/compiler/test/deferred_loading/data/type_arguments/main.dart
@@ -5,11 +5,11 @@
 /*spec.library: 
  a_pre_fragments=[
   p1: {units: [1{lib1}], usedBy: [], needs: []},
-  p2: {units: [2{lib3}], usedBy: [], needs: []},
-  p3: {units: [3{lib1, lib3}], usedBy: [], needs: []}],
+  p2: {units: [3{lib3}], usedBy: [], needs: []},
+  p3: {units: [2{lib1, lib3}], usedBy: [], needs: []}],
  b_finalized_fragments=[
   f1: [1{lib1}],
-  f2: [2{lib3}]],
+  f2: [3{lib3}]],
  c_steps=[
   lib1=(f1),
   lib3=(f2)]
@@ -18,11 +18,11 @@
 /*two-frag|three-frag.library: 
  a_pre_fragments=[
   p1: {units: [1{lib1}], usedBy: [p3], needs: []},
-  p2: {units: [2{lib3}], usedBy: [p3], needs: []},
-  p3: {units: [3{lib1, lib3}], usedBy: [], needs: [p1, p2]}],
+  p2: {units: [3{lib3}], usedBy: [p3], needs: []},
+  p3: {units: [2{lib1, lib3}], usedBy: [], needs: [p1, p2]}],
  b_finalized_fragments=[
   f1: [1{lib1}],
-  f2: [2{lib3}]],
+  f2: [3{lib3}]],
  c_steps=[
   lib1=(f1),
   lib3=(f2)]
@@ -39,7 +39,7 @@
   ConstructedConstant(A<B*>())=1{lib1},
   ConstructedConstant(A<F*>())=1{lib1},
   ConstructedConstant(C<D*>())=main{},
-  ConstructedConstant(E<F*>())=2{lib3}],
+  ConstructedConstant(E<F*>())=3{lib3}],
  member_unit=main{}
 */
 main() async {
diff --git a/runtime/vm/dart_api_impl.cc b/runtime/vm/dart_api_impl.cc
index 00061db..5d21abf 100644
--- a/runtime/vm/dart_api_impl.cc
+++ b/runtime/vm/dart_api_impl.cc
@@ -1972,6 +1972,7 @@
 
 DART_EXPORT Dart_Handle Dart_RunLoop() {
   Isolate* I;
+  bool result;
   {
     Thread* T = Thread::Current();
     I = T->isolate();
@@ -1988,14 +1989,21 @@
     RunLoopData data;
     data.monitor = &monitor;
     data.done = false;
-    I->message_handler()->Run(I->group()->thread_pool(), NULL, RunLoopDone,
-                              reinterpret_cast<uword>(&data));
-    while (!data.done) {
-      ml.Wait();
+    result =
+        I->message_handler()->Run(I->group()->thread_pool(), NULL, RunLoopDone,
+                                  reinterpret_cast<uword>(&data));
+    if (result) {
+      while (!data.done) {
+        ml.Wait();
+      }
     }
   }
   ::Dart_EnterIsolate(Api::CastIsolate(I));
-  if (I->sticky_error() != Object::null()) {
+  if (!result) {
+    Thread* T = Thread::Current();
+    TransitionNativeToVM transition(T);
+    return Api::NewError("Run method in isolate message handler failed");
+  } else if (I->sticky_error() != Object::null()) {
     Thread* T = Thread::Current();
     TransitionNativeToVM transition(T);
     return Api::NewHandle(T, I->StealStickyError());
diff --git a/runtime/vm/dart_api_impl_test.cc b/runtime/vm/dart_api_impl_test.cc
index 5b0bc2b..fc1877f 100644
--- a/runtime/vm/dart_api_impl_test.cc
+++ b/runtime/vm/dart_api_impl_test.cc
@@ -9396,9 +9396,10 @@
         ml.Notify();
       }
       count++;
+    } else {
+      free(error);
     }
   } while (count < 100);
-  free(error);
 }
 
 TEST_CASE(DartAPI_InvokeVMServiceMethod_Loop) {
diff --git a/runtime/vm/kernel_isolate.cc b/runtime/vm/kernel_isolate.cc
index 066c7d4..5d41659 100644
--- a/runtime/vm/kernel_isolate.cc
+++ b/runtime/vm/kernel_isolate.cc
@@ -436,7 +436,6 @@
                                  false)),
         next_(NULL),
         prev_(NULL) {
-    ASSERT(port_ != ILLEGAL_PORT);
     RegisterRequest(this);
     result_.status = Dart_KernelCompilationStatus_Unknown;
     result_.error = NULL;
@@ -446,7 +445,9 @@
 
   ~KernelCompilationRequest() {
     UnregisterRequest(this);
-    Dart_CloseNativePort(port_);
+    if (port_ != ILLEGAL_PORT) {
+      Dart_CloseNativePort(port_);
+    }
   }
 
   intptr_t setDillData(Dart_CObject** dills_array,
@@ -481,6 +482,13 @@
       char const* klass,
       bool is_static,
       const MallocGrowableArray<char*>* experimental_flags) {
+    if (port_ == ILLEGAL_PORT) {
+      Dart_KernelCompilationResult result = {};
+      result.status = Dart_KernelCompilationStatus_Unknown;
+      result.error =
+          Utils::StrDup("Error Kernel Isolate : unable to create reply port");
+      return result;
+    }
     Thread* thread = Thread::Current();
     TransitionNativeToVM transition(thread);
     Dart_CObject tag;
diff --git a/runtime/vm/message_handler.cc b/runtime/vm/message_handler.cc
index 28a89a2..bbb8211 100644
--- a/runtime/vm/message_handler.cc
+++ b/runtime/vm/message_handler.cc
@@ -100,7 +100,7 @@
   // By default, there is no custom message notification.
 }
 
-void MessageHandler::Run(ThreadPool* pool,
+bool MessageHandler::Run(ThreadPool* pool,
                          StartCallback start_callback,
                          EndCallback end_callback,
                          CallbackData data) {
@@ -118,8 +118,15 @@
   end_callback_ = end_callback;
   callback_data_ = data;
   task_running_ = true;
-  const bool launched_successfully = pool_->Run<MessageHandlerTask>(this);
-  ASSERT(launched_successfully);
+  bool result = pool_->Run<MessageHandlerTask>(this);
+  if (!result) {
+    pool_ = nullptr;
+    start_callback_ = nullptr;
+    end_callback_ = nullptr;
+    callback_data_ = 0;
+    task_running_ = false;
+  }
+  return result;
 }
 
 void MessageHandler::PostMessage(std::unique_ptr<Message> message,
diff --git a/runtime/vm/message_handler.h b/runtime/vm/message_handler.h
index 19b5101..715641b 100644
--- a/runtime/vm/message_handler.h
+++ b/runtime/vm/message_handler.h
@@ -48,7 +48,10 @@
   // no longer has any live ports.  Abnormal termination occurs when
   // HandleMessage() indicates that an error has occurred during
   // message processing.
-  void Run(ThreadPool* pool,
+
+  // Returns false if the handler terminated abnormally, otherwise it
+  // returns true.
+  bool Run(ThreadPool* pool,
            StartCallback start_callback,
            EndCallback end_callback,
            CallbackData data);
diff --git a/runtime/vm/native_api_impl.cc b/runtime/vm/native_api_impl.cc
index 07a2fec..793accb 100644
--- a/runtime/vm/native_api_impl.cc
+++ b/runtime/vm/native_api_impl.cc
@@ -90,8 +90,13 @@
 
   NativeMessageHandler* nmh = new NativeMessageHandler(name, handler);
   Dart_Port port_id = PortMap::CreatePort(nmh);
-  PortMap::SetPortState(port_id, PortMap::kLivePort);
-  nmh->Run(Dart::thread_pool(), NULL, NULL, 0);
+  if (port_id != ILLEGAL_PORT) {
+    PortMap::SetPortState(port_id, PortMap::kLivePort);
+    if (!nmh->Run(Dart::thread_pool(), NULL, NULL, 0)) {
+      PortMap::ClosePort(port_id);
+      port_id = ILLEGAL_PORT;
+    }
+  }
   Dart::ResetActiveApiCall();
   return port_id;
 }
diff --git a/tools/VERSION b/tools/VERSION
index 79b34c1..2fc2c05 100644
--- a/tools/VERSION
+++ b/tools/VERSION
@@ -27,5 +27,5 @@
 MAJOR 2
 MINOR 15
 PATCH 0
-PRERELEASE 28
+PRERELEASE 29
 PRERELEASE_PATCH 0
\ No newline at end of file