diff --git a/pkg/compiler/lib/src/compiler.dart b/pkg/compiler/lib/src/compiler.dart
index 1e2a298..be24ef3 100644
--- a/pkg/compiler/lib/src/compiler.dart
+++ b/pkg/compiler/lib/src/compiler.dart
@@ -290,6 +290,15 @@
 
   JClosedWorld computeClosedWorld(LoadedLibraries loadedLibraries) {
     ResolutionEnqueuer resolutionEnqueuer = startResolution();
+    for (LibraryEntity library
+        in frontendStrategy.elementEnvironment.libraries) {
+      frontendStrategy.elementEnvironment.forEachClass(library,
+          (ClassEntity cls) {
+        // Register all classes eagerly to optimize closed world computation in
+        // `ClassWorldBuilder.isInheritedInSubtypeOf`.
+        resolutionEnqueuer.worldBuilder.registerClass(cls);
+      });
+    }
     WorldImpactBuilderImpl mainImpact = new WorldImpactBuilderImpl();
     FunctionEntity mainFunction = frontendStrategy.computeMain(mainImpact);
 
diff --git a/pkg/compiler/lib/src/js_emitter/program_builder/program_builder.dart b/pkg/compiler/lib/src/js_emitter/program_builder/program_builder.dart
index 00cdf32..de9d367 100644
--- a/pkg/compiler/lib/src/js_emitter/program_builder/program_builder.dart
+++ b/pkg/compiler/lib/src/js_emitter/program_builder/program_builder.dart
@@ -690,7 +690,7 @@
       callStubs.add(_buildStubMethod(name, function));
     }
 
-    if (_commonElements.isInstantiationClass(cls)) {
+    if (_commonElements.isInstantiationClass(cls) && !onlyForRti) {
       callStubs.addAll(_generateInstantiationStubs(cls));
     }
 
diff --git a/pkg/compiler/lib/src/library_loader.dart b/pkg/compiler/lib/src/library_loader.dart
index a941245..b4832ee 100644
--- a/pkg/compiler/lib/src/library_loader.dart
+++ b/pkg/compiler/lib/src/library_loader.dart
@@ -41,6 +41,8 @@
       : initializedCompilerState = _options.kernelInitializedCompilerState,
         super(measurer);
 
+  String get name => 'Library loader';
+
   /// Loads an entire Kernel [Component] from a file on disk.
   Future<LoadedLibraries> loadLibraries(Uri resolvedUri) {
     return measure(() async {
diff --git a/pkg/compiler/lib/src/universe/class_hierarchy.dart b/pkg/compiler/lib/src/universe/class_hierarchy.dart
index cc91490..c351f1e 100644
--- a/pkg/compiler/lib/src/universe/class_hierarchy.dart
+++ b/pkg/compiler/lib/src/universe/class_hierarchy.dart
@@ -625,32 +625,112 @@
     return classSet.hasSubtype(classHierarchyNode);
   }
 
+  Map<ClassEntity, _InheritedCache> _inheritedCacheMap = {};
+
   bool isInheritedInSubtypeOf(ClassEntity x, ClassEntity y) {
-    ClassSet classSet = classSets[x];
-    assert(classSet != null,
-        failedAt(x, "No ClassSet for $x (${x.runtimeType}): ${classSets}"));
+    _InheritedCache cache = _inheritedCacheMap[x] ??= new _InheritedCache();
+    return cache.isInheritedInSubtypeOf(this, x, y);
+  }
+}
 
-    if (_isSubtypeOf(x, y)) {
+/// A cache object used for [ClassHierarchyBuilder.isInheritedInSubtypeOf].
+class _InheritedCache {
+  Map<ClassEntity, _InheritingSet> _map;
+
+  /// Returns whether a live class currently known to inherit from [x] and
+  /// implement [y].
+  bool isInheritedInSubtypeOf(
+      ClassHierarchyBuilder builder, ClassEntity x, ClassEntity y) {
+    _InheritingSet set;
+    if (_map == null) {
+      _map = {};
+    } else {
+      set = _map[y];
+    }
+    if (set == null) {
+      set = _map[y] = _computeInheritingSet(builder, x, y);
+    }
+    return set.hasLiveClass(builder);
+  }
+
+  /// Creates an [_InheritingSet] of classes that inherit members of a class [x]
+  /// while implementing class [y].
+  _InheritingSet _computeInheritingSet(
+      ClassHierarchyBuilder builder, ClassEntity x, ClassEntity y) {
+    ClassSet classSet = builder.classSets[x];
+
+    assert(
+        classSet != null,
+        failedAt(
+            x, "No ClassSet for $x (${x.runtimeType}): ${builder.classSets}"));
+
+    Set<ClassEntity> classes = new Set<ClassEntity>();
+
+    if (builder._isSubtypeOf(x, y)) {
       // [x] implements [y] itself, possible through supertypes.
-      return true;
+      classes.add(x);
     }
 
-    /// Returns `true` if any live subclass of [node] implements [y].
-    bool subclassImplements(ClassHierarchyNode node, {bool strict}) {
-      return node.anySubclass((ClassEntity z) => _isSubtypeOf(z, y),
-          ClassHierarchyNode.INSTANTIATED,
-          strict: strict);
+    /// Add subclasses of [node] that implement [y].
+    void subclassImplements(ClassHierarchyNode node, {bool strict}) {
+      node.forEachSubclass((ClassEntity z) {
+        if (builder._isSubtypeOf(z, y)) {
+          classes.add(z);
+        }
+      }, ClassHierarchyNode.ALL, strict: strict);
     }
 
-    if (subclassImplements(classSet.node, strict: true)) {
-      // A subclass of [x] implements [y].
-      return true;
-    }
+    // A subclasses of [x] that implement [y].
+    subclassImplements(classSet.node, strict: true);
 
     for (ClassHierarchyNode mixinApplication
         in classSet.mixinApplicationNodes) {
-      if (subclassImplements(mixinApplication, strict: false)) {
-        // A subclass of [mixinApplication] implements [y].
+      // A subclass of [mixinApplication] implements [y].
+      subclassImplements(mixinApplication, strict: false);
+    }
+
+    return new _InheritingSet(classes);
+  }
+}
+
+/// A set of classes that inherit members of a class 'x' while implementing
+/// class 'y'.
+///
+/// The set is used [ClassHierarchyBuilder.isInheritedInSubtypeOf] to determine
+/// when members of a class is live.
+class _InheritingSet {
+  /// If `true` the set of classes is known to contain a live class. In this
+  /// case [_classes] is `null`. If `false` the set of classes is empty and
+  /// therefore known never to contain live classes. In this case [_classes]
+  /// is `null`. If `null` [_classes] is a non-empty set containing classes
+  /// that are not yet known to be live.
+  bool _result;
+  Set<ClassEntity> _classes;
+
+  _InheritingSet(Set<ClassEntity> classes)
+      : _result = classes.isEmpty ? false : null,
+        _classes = classes.isNotEmpty ? classes : null;
+
+  /// Returns whether the set of classes is currently known to contain a live
+  /// classes.
+  ///
+  /// The result of this method changes during the closed world computation.
+  /// Initially, we haven't seen any live classes so we will return `false` even
+  /// for a non-empty set of classes. As more classes are marked as
+  /// instantiated, during tree-shaking, the result might change to `true` if
+  /// one of the [_classes] has been marked as live.
+  ///
+  /// The result of this method _is_ monotone, though; when we have returned
+  /// `true` (because at least one class is known to be live) we will continue
+  /// to return `true`.
+  bool hasLiveClass(ClassHierarchyBuilder builder) {
+    if (_result != null) return _result;
+    for (ClassEntity cls in _classes) {
+      if (builder.classHierarchyNodes[cls].isInstantiated) {
+        // We now know this set contains a live class and done need to remember
+        // that set of classes anymore.
+        _result = true;
+        _classes = null;
         return true;
       }
     }
diff --git a/pkg/compiler/lib/src/universe/resolution_world_builder.dart b/pkg/compiler/lib/src/universe/resolution_world_builder.dart
index 6f7d4bd..b203dc9 100644
--- a/pkg/compiler/lib/src/universe/resolution_world_builder.dart
+++ b/pkg/compiler/lib/src/universe/resolution_world_builder.dart
@@ -851,7 +851,7 @@
       memberUsed(usage.entity, useSet);
       return usage;
     });
-    if (!newUsage) {
+    if (!usage.fullyUsed && !newUsage) {
       EnumSet<MemberUse> useSet = new EnumSet<MemberUse>();
       if (!usage.hasRead && _hasInvokedGetter(member)) {
         useSet.addAll(usage.read());
@@ -945,8 +945,6 @@
   bool isInheritedInSubtypeOf(MemberEntity member, ClassEntity type) {
     // TODO(johnniwinther): Use the [member] itself to avoid enqueueing members
     // that are overridden.
-    _classHierarchyBuilder.registerClass(member.enclosingClass);
-    _classHierarchyBuilder.registerClass(type);
     return _classHierarchyBuilder.isInheritedInSubtypeOf(
         member.enclosingClass, type);
   }
@@ -972,12 +970,7 @@
     Map<ClassEntity, Set<ClassEntity>> typesImplementedBySubclasses =
         populateHierarchyNodes();
 
-    var backendUsage = _backendUsageBuilder.close();
-    backendUsage.helperClassesUsed
-        .forEach(_classHierarchyBuilder.registerClass);
-    _nativeResolutionEnqueuer.liveNativeClasses
-        .forEach(_classHierarchyBuilder.registerClass);
-
+    BackendUsage backendUsage = _backendUsageBuilder.close();
     _closed = true;
     assert(
         _classHierarchyBuilder.classHierarchyNodes.length ==
@@ -996,7 +989,7 @@
         commonElements: _commonElements,
         nativeData: _nativeDataBuilder.close(),
         interceptorData: _interceptorDataBuilder.close(),
-        backendUsage: _backendUsageBuilder.close(),
+        backendUsage: backendUsage,
         noSuchMethodData: _noSuchMethodRegistry.close(),
         resolutionWorldBuilder: this,
         rtiNeedBuilder: _rtiNeedBuilder,
diff --git a/pkg/compiler/lib/src/universe/world_builder.dart b/pkg/compiler/lib/src/universe/world_builder.dart
index 5107b28..84aa6d3 100644
--- a/pkg/compiler/lib/src/universe/world_builder.dart
+++ b/pkg/compiler/lib/src/universe/world_builder.dart
@@ -14,7 +14,8 @@
 import '../elements/types.dart';
 import '../js_backend/annotations.dart';
 import '../js_backend/allocator_analysis.dart' show KAllocatorAnalysis;
-import '../js_backend/backend_usage.dart' show BackendUsageBuilder;
+import '../js_backend/backend_usage.dart'
+    show BackendUsage, BackendUsageBuilder;
 import '../js_backend/interceptor_data.dart' show InterceptorDataBuilder;
 import '../js_backend/native_data.dart' show NativeBasicData, NativeDataBuilder;
 import '../js_backend/no_such_method_registry.dart';
diff --git a/tests/compiler/dart2js/model/class_set_test.dart b/tests/compiler/dart2js/model/class_set_test.dart
index ada6c0c..790a8a5 100644
--- a/tests/compiler/dart2js/model/class_set_test.dart
+++ b/tests/compiler/dart2js/model/class_set_test.dart
@@ -36,8 +36,8 @@
       ///    D   E F G
       ///
       class A {}
-      class B extends A {}
       class C extends A {}
+      class B extends A {}
       class D extends B {}
       class E extends C {}
       class F extends C {}
@@ -361,8 +361,8 @@
       ///         H I
       ///
       class A implements X {}
-      class B extends A {}
       class C extends A {}
+      class B extends A {}
       class D extends B {}
       class E extends C {}
       class F extends C implements B {}