diff --git a/runtime/vm/cha.cc b/runtime/vm/cha.cc
index 5c5ccb0..b937357 100644
--- a/runtime/vm/cha.cc
+++ b/runtime/vm/cha.cc
@@ -12,81 +12,84 @@
 
 namespace dart {
 
-bool CHA::HasSubclasses(intptr_t cid) {
-  Isolate* isolate = Isolate::Current();
-  const bool has_subclasses = HasSubclassesSafe(cid);
-  if (!has_subclasses) {
-    isolate->set_cha_used(true);
-  }
-  return has_subclasses;
-}
-
-
-bool CHA::HasSubclassesSafe(intptr_t cid) {
-  ASSERT(cid >= kInstanceCid);
-  Isolate* isolate = Isolate::Current();
-  const ClassTable& class_table = *isolate->class_table();
-  const Class& cls = Class::Handle(isolate, class_table.At(cid));
-  ASSERT(!cls.IsNull());
-  if (cls.IsObjectClass()) {
-    // Class Object has subclasses, although we do not keep track of them.
-    return true;
-  }
-  const GrowableObjectArray& cls_direct_subclasses =
-      GrowableObjectArray::Handle(isolate, cls.direct_subclasses());
-  return
-      !cls_direct_subclasses.IsNull() && (cls_direct_subclasses.Length() > 0);
-}
-
-
-// Returns true if the given array of cids contains the given cid.
-static bool ContainsCid(ZoneGrowableArray<intptr_t>* cids, intptr_t cid) {
-  for (intptr_t i = 0; i < cids->length(); i++) {
-    if ((*cids)[i] == cid) {
-      return true;
-    }
-  }
+// Return true if the class is private to our internal libraries (not extendable
+// or implementable after startup). Therefore, we don't need to register
+// optimized code for invalidation for those classes.
+// TODO(fschneider): Allow more libraries.
+static bool IsKnownPrivateClass(const Class& type_class) {
+  if (!Library::IsPrivate(String::Handle(type_class.Name()))) return false;
+  const Library& library = Library::Handle(type_class.library());
+  if (library.raw() == Library::CoreLibrary()) return true;
+  if (library.raw() == Library::CollectionLibrary()) return true;
+  if (library.raw() == Library::TypedDataLibrary()) return true;
+  if (library.raw() == Library::MathLibrary()) return true;
   return false;
 }
 
 
-// Recursively collect direct and indirect subclass ids of cls.
-static void CollectSubclassIds(ZoneGrowableArray<intptr_t>* cids,
-                               const Class& cls) {
-  const GrowableObjectArray& cls_direct_subclasses =
-      GrowableObjectArray::Handle(cls.direct_subclasses());
-  if (cls_direct_subclasses.IsNull()) {
-    return;
-  }
-  Class& direct_subclass = Class::Handle();
-  for (intptr_t i = 0; i < cls_direct_subclasses.Length(); i++) {
-    direct_subclass ^= cls_direct_subclasses.At(i);
-    intptr_t direct_subclass_id = direct_subclass.id();
-    if (!ContainsCid(cids, direct_subclass_id)) {
-      cids->Add(direct_subclass_id);
-      CollectSubclassIds(cids, direct_subclass);
+void CHA::AddToLeafClasses(const Class& cls) {
+  if (IsKnownPrivateClass(cls)) return;
+
+  for (intptr_t i = 0; i < leaf_classes_.length(); i++) {
+    if (leaf_classes_[i]->raw() == cls.raw()) {
+      return;
     }
   }
+  leaf_classes_.Add(&Class::ZoneHandle(isolate_, cls.raw()));
 }
 
 
-ZoneGrowableArray<intptr_t>* CHA::GetSubclassIdsOf(intptr_t cid) {
-  ASSERT(cid > kInstanceCid);
-  Isolate* isolate = Isolate::Current();
-  const ClassTable& class_table = *isolate->class_table();
-  const Class& cls = Class::Handle(isolate, class_table.At(cid));
+bool CHA::HasSubclasses(const Class& cls) {
   ASSERT(!cls.IsNull());
-  ZoneGrowableArray<intptr_t>* ids = new ZoneGrowableArray<intptr_t>();
-  CollectSubclassIds(ids, cls);
-  isolate->set_cha_used(true);
-  return ids;
+  ASSERT(cls.id() >= kInstanceCid);
+  // Can't track dependencies for classes on the VM heap since those are
+  // read-only.
+  // TODO(fschneider): Enable tracking of CHA dependent code for VM heap
+  // classes.
+  if (cls.InVMHeap()) return true;
+
+  if (cls.IsObjectClass()) {
+    // Class Object has subclasses, although we do not keep track of them.
+    return true;
+  }
+  const GrowableObjectArray& direct_subclasses =
+      GrowableObjectArray::Handle(isolate_, cls.direct_subclasses());
+  bool result =
+      !direct_subclasses.IsNull() && (direct_subclasses.Length() > 0);
+  if (!result) {
+    AddToLeafClasses(cls);
+  }
+  return result;
+}
+
+
+bool CHA::HasSubclasses(intptr_t cid) {
+  const ClassTable& class_table = *isolate_->class_table();
+  Class& cls = Class::Handle(isolate_, class_table.At(cid));
+  return HasSubclasses(cls);
+}
+
+
+bool CHA::IsImplemented(const Class& cls) {
+  // Signature classes have different type checking rules.
+  ASSERT(!cls.IsSignatureClass());
+  // Can't track dependencies for classes on the VM heap since those are
+  // read-only.
+  // TODO(fschneider): Enable tracking of CHA dependent code for VM heap
+  // classes.
+  if (cls.InVMHeap()) return true;
+
+  bool result = cls.is_implemented();
+  if (!result) {
+    AddToLeafClasses(cls);
+  }
+  return result;
 }
 
 
 bool CHA::HasOverride(const Class& cls, const String& function_name) {
-  Isolate* isolate = Isolate::Current();
   const GrowableObjectArray& cls_direct_subclasses =
-      GrowableObjectArray::Handle(isolate, cls.direct_subclasses());
+      GrowableObjectArray::Handle(isolate_, cls.direct_subclasses());
   // Subclasses of Object are not tracked by CHA. Safely assume that overrides
   // exist.
   if (cls.IsObjectClass()) {
@@ -94,10 +97,10 @@
   }
 
   if (cls_direct_subclasses.IsNull()) {
-    isolate->set_cha_used(true);
+    AddToLeafClasses(cls);
     return false;
   }
-  Class& direct_subclass = Class::Handle(isolate);
+  Class& direct_subclass = Class::Handle(isolate_);
   for (intptr_t i = 0; i < cls_direct_subclasses.Length(); i++) {
     direct_subclass ^= cls_direct_subclasses.At(i);
     // Unfinalized classes are treated as non-existent for CHA purposes,
@@ -111,44 +114,8 @@
       return true;
     }
   }
-  isolate->set_cha_used(true);
+  AddToLeafClasses(cls);
   return false;
 }
 
-
-ZoneGrowableArray<Function*>* CHA::GetNamedInstanceFunctionsOf(
-    const ZoneGrowableArray<intptr_t>& cids,
-    const String& function_name) {
-  Isolate* isolate = Isolate::Current();
-  ASSERT(!function_name.IsNull());
-  const ClassTable& class_table = *isolate->class_table();
-  ZoneGrowableArray<Function*>* functions = new ZoneGrowableArray<Function*>();
-  Class& cls = Class::Handle(isolate);
-  Function& cls_function = Function::Handle(isolate);
-  for (intptr_t i = 0; i < cids.length(); i++) {
-    const intptr_t cid = cids[i];
-    ASSERT(cid > kInstanceCid);
-    cls = class_table.At(cid);
-    cls_function = cls.LookupDynamicFunction(function_name);
-    if (!cls_function.IsNull()) {
-      functions->Add(&Function::ZoneHandle(isolate, cls_function.raw()));
-    }
-  }
-  isolate->set_cha_used(true);
-  return functions;
-}
-
-
-ZoneGrowableArray<Function*>* CHA::GetOverridesOf(const Function& function) {
-  ASSERT(!function.IsNull());
-  ASSERT(function.IsDynamicFunction());
-  Isolate* isolate = Isolate::Current();
-  const Class& function_owner = Class::Handle(isolate, function.Owner());
-  const String& function_name = String::Handle(isolate, function.name());
-  ZoneGrowableArray<intptr_t>* cids = new ZoneGrowableArray<intptr_t>();
-  CollectSubclassIds(cids, function_owner);
-  isolate->set_cha_used(true);
-  return GetNamedInstanceFunctionsOf(*cids, function_name);
-}
-
 }  // namespace dart
diff --git a/runtime/vm/cha.h b/runtime/vm/cha.h
index 18a0bcb..2100820 100644
--- a/runtime/vm/cha.h
+++ b/runtime/vm/cha.h
@@ -6,6 +6,7 @@
 #define VM_CHA_H_
 
 #include "vm/allocation.h"
+#include "vm/growable_array.h"
 
 namespace dart {
 
@@ -14,33 +15,47 @@
 template <typename T> class ZoneGrowableArray;
 class String;
 
-class CHA : public AllStatic {
+class CHA : public StackResource {
  public:
-  // Returns true if the class given by its cid has subclasses.
-  static bool HasSubclasses(intptr_t cid);
+  explicit CHA(Isolate* isolate)
+      : StackResource(isolate),
+        isolate_(isolate),
+        leaf_classes_(isolate, 1),
+        previous_(isolate->cha()) {
+    isolate->set_cha(this);
+  }
 
-  // Use only on known private classes that can never be subclassed by lazy
-  // class finalization. Does not affect Isolate::use_cha flag.
-  static bool HasSubclassesSafe(intptr_t cid);
+  ~CHA() {
+    ASSERT(isolate_->cha() == this);
+    isolate_->set_cha(previous_);
+  }
 
-  // Returns an array containing the cids of the direct and indirect subclasses
-  // of the class given by its cid.
-  // Must not be called for kInstanceCid.
-  static ZoneGrowableArray<intptr_t>* GetSubclassIdsOf(intptr_t cid);
+  // Returns true if the class has subclasses.
+  // Updates set of leaf classes that we register optimized code with for lazy
+  // deoptimization.
+  bool HasSubclasses(const Class& cls);
+  bool HasSubclasses(intptr_t cid);
 
-  // Returns an array containing instance functions of the given name and
-  // belonging to the classes given by their cids.
-  // Cids must not contain kInstanceCid.
-  static ZoneGrowableArray<Function*>* GetNamedInstanceFunctionsOf(
-      const ZoneGrowableArray<intptr_t>& cids,
-      const String& function_name);
-
-  // Returns an array of functions overriding the given function.
-  // Must not be called for a function of class Object.
-  static ZoneGrowableArray<Function*>* GetOverridesOf(const Function& function);
+  // Return true if the class is implemented by some other class.
+  // Updates set of leaf classes that we register optimized code with for lazy
+  // deoptimization.
+  bool IsImplemented(const Class& cls);
 
   // Returns true if any subclass of 'cls' contains the function.
-  static bool HasOverride(const Class& cls, const String& function_name);
+  // Updates set of leaf classes that we register optimized code with for lazy
+  // deoptimization.
+  bool HasOverride(const Class& cls, const String& function_name);
+
+  const GrowableArray<Class*>& leaf_classes() const {
+    return leaf_classes_;
+  }
+
+ private:
+  void AddToLeafClasses(const Class& cls);
+
+  Isolate* isolate_;
+  GrowableArray<Class*> leaf_classes_;
+  CHA* previous_;
 };
 
 }  // namespace dart
diff --git a/runtime/vm/cha_test.cc b/runtime/vm/cha_test.cc
index 1ec35c5..a12a3be 100644
--- a/runtime/vm/cha_test.cc
+++ b/runtime/vm/cha_test.cc
@@ -11,6 +11,14 @@
 
 namespace dart {
 
+static bool ContainsCid(const GrowableArray<Class*>& classes, intptr_t cid) {
+  for (intptr_t i = 0; i < classes.length(); ++i) {
+    if (classes[i]->id() == cid) return true;
+  }
+  return false;
+}
+
+
 TEST_CASE(ClassHierarchyAnalysis) {
   const char* kScriptChars =
       "class A {"
@@ -36,22 +44,18 @@
   const Class& class_a = Class::Handle(
       lib.LookupClass(String::Handle(Symbols::New("A"))));
   EXPECT(!class_a.IsNull());
-  const intptr_t class_a_id = class_a.id();
 
   const Class& class_b = Class::Handle(
       lib.LookupClass(String::Handle(Symbols::New("B"))));
   EXPECT(!class_b.IsNull());
-  const intptr_t class_b_id = class_b.id();
 
   const Class& class_c = Class::Handle(
       lib.LookupClass(String::Handle(Symbols::New("C"))));
   EXPECT(!class_c.IsNull());
-  const intptr_t class_c_id = class_c.id();
 
   const Class& class_d = Class::Handle(
       lib.LookupClass(String::Handle(Symbols::New("D"))));
   EXPECT(!class_d.IsNull());
-  const intptr_t class_d_id = class_d.id();
 
   const String& function_foo_name = String::Handle(String::New("foo"));
   const String& function_bar_name = String::Handle(String::New("bar"));
@@ -76,59 +80,26 @@
       Function::Handle(class_d.LookupDynamicFunction(function_bar_name));
   EXPECT(!class_d_bar.IsNull());
 
-  ZoneGrowableArray<intptr_t>* a_subclass_ids =
-      CHA::GetSubclassIdsOf(class_a_id);
-  EXPECT_EQ(3, a_subclass_ids->length());
-  EXPECT_EQ(class_b_id, (*a_subclass_ids)[0]);
-  EXPECT_EQ(class_c_id, (*a_subclass_ids)[1]);
-  EXPECT_EQ(class_d_id, (*a_subclass_ids)[2]);
-  ZoneGrowableArray<intptr_t>* b_subclass_ids =
-      CHA::GetSubclassIdsOf(class_b_id);
-  EXPECT_EQ(1, b_subclass_ids->length());
-  EXPECT_EQ(class_c_id, (*b_subclass_ids)[0]);
-  ZoneGrowableArray<intptr_t>* c_subclass_ids =
-      CHA::GetSubclassIdsOf(class_c_id);
-  EXPECT_EQ(0, c_subclass_ids->length());
-  ZoneGrowableArray<intptr_t>* d_subclass_ids =
-      CHA::GetSubclassIdsOf(class_d_id);
-  EXPECT_EQ(0, d_subclass_ids->length());
+  CHA cha(Isolate::Current());
 
-  ZoneGrowableArray<Function*>* foos =
-      CHA::GetNamedInstanceFunctionsOf(*a_subclass_ids, function_foo_name);
-  EXPECT_EQ(2, foos->length());
-  EXPECT_EQ(class_c_foo.raw(), (*foos)[0]->raw());
-  EXPECT_EQ(class_d_foo.raw(), (*foos)[1]->raw());
+  EXPECT(cha.HasSubclasses(kInstanceCid));
+  EXPECT(!cha.HasSubclasses(kSmiCid));
+  EXPECT(!cha.HasSubclasses(kNullCid));
 
-  ZoneGrowableArray<Function*>* class_a_foo_overrides =
-      CHA::GetOverridesOf(class_a_foo);
-  EXPECT_EQ(2, class_a_foo_overrides->length());
-  EXPECT_EQ(class_c_foo.raw(), (*class_a_foo_overrides)[0]->raw());
-  EXPECT_EQ(class_d_foo.raw(), (*class_a_foo_overrides)[1]->raw());
+  EXPECT(cha.HasSubclasses(class_a));
+  EXPECT(cha.HasSubclasses(class_b));
+  EXPECT(!cha.HasSubclasses(class_c));
+  EXPECT(!cha.HasSubclasses(class_d));
 
-  ZoneGrowableArray<Function*>* bars =
-      CHA::GetNamedInstanceFunctionsOf(*a_subclass_ids, function_bar_name);
-  EXPECT_EQ(1, bars->length());
-  EXPECT_EQ(class_d_bar.raw(), (*bars)[0]->raw());
-
-  ZoneGrowableArray<Function*>* class_a_bar_overrides =
-      CHA::GetOverridesOf(class_a_bar);
-  EXPECT_EQ(1, class_a_bar_overrides->length());
-  EXPECT_EQ(class_d_bar.raw(), (*class_a_bar_overrides)[0]->raw());
-
-  EXPECT(CHA::HasSubclasses(kInstanceCid));
-  EXPECT(!CHA::HasSubclasses(kSmiCid));
-  EXPECT(!CHA::HasSubclasses(kNullCid));
-  EXPECT(!CHA::HasSubclasses(kDynamicCid));
-  EXPECT(!CHA::HasSubclasses(kVoidCid));
-  EXPECT(CHA::HasSubclasses(class_a_id));
-  EXPECT(CHA::HasSubclasses(class_b_id));
-  EXPECT(!CHA::HasSubclasses(class_c_id));
-  EXPECT(!CHA::HasSubclasses(class_d_id));
+  EXPECT(!ContainsCid(cha.leaf_classes(), class_a.id()));
+  EXPECT(!ContainsCid(cha.leaf_classes(), class_b.id()));
+  EXPECT(ContainsCid(cha.leaf_classes(), class_c.id()));
+  EXPECT(ContainsCid(cha.leaf_classes(), class_d.id()));
 
   class Class& function_impl_class =
       Class::Handle(Type::Handle(Isolate::Current()->object_store()->
           function_impl_type()).type_class());
-  EXPECT(CHA::HasSubclasses(function_impl_class.id()));
+  EXPECT(cha.HasSubclasses(function_impl_class.id()));
 }
 
 }  // namespace dart
diff --git a/runtime/vm/class_finalizer.cc b/runtime/vm/class_finalizer.cc
index 1f0c615..2bda885 100644
--- a/runtime/vm/class_finalizer.cc
+++ b/runtime/vm/class_finalizer.cc
@@ -93,6 +93,27 @@
 }
 
 
+static void CollectImmediateSuperInterfaces(
+    const Class& cls, GrowableArray<intptr_t>* cids) {
+  const Array& interfaces = Array::Handle(cls.interfaces());
+  Class& ifc = Class::Handle();
+  AbstractType& type = AbstractType::Handle();
+  for (intptr_t i = 0; i < interfaces.Length(); ++i) {
+    type ^= interfaces.At(i);
+    if (type.IsMalformed()) continue;
+    if (!type.HasResolvedTypeClass()) continue;
+    ifc ^= type.type_class();
+    for (intptr_t j = 0; j < cids->length(); ++j) {
+      if ((*cids)[j] == ifc.id()) {
+        // Already added.
+        return;
+      }
+    }
+    cids->Add(ifc.id());
+  }
+}
+
+
 // Processing ObjectStore::pending_classes_ occurs:
 // a) when bootstrap process completes (VerifyBootstrapClasses).
 // b) after the user classes are loaded (dart_api).
@@ -2287,8 +2308,6 @@
     // the class conflict with inherited methods.
     ApplyMixinMembers(cls);
   }
-  GrowableArray<intptr_t> added_subclass_to_cids;
-  CollectFinalizedSuperClasses(cls, &added_subclass_to_cids);
   // Ensure super class is finalized.
   const Class& super = Class::Handle(cls.SuperClass());
   if (!super.IsNull()) {
@@ -2317,7 +2336,10 @@
     CheckForLegalConstClass(cls);
   }
   if (FLAG_use_cha) {
-    RemoveCHAOptimizedCode(added_subclass_to_cids);
+    GrowableArray<intptr_t> cids;
+    CollectFinalizedSuperClasses(cls, &cids);
+    CollectImmediateSuperInterfaces(cls, &cids);
+    RemoveCHAOptimizedCode(cids);
   }
 }
 
diff --git a/runtime/vm/compiler.cc b/runtime/vm/compiler.cc
index 557d61c..83500cd 100644
--- a/runtime/vm/compiler.cc
+++ b/runtime/vm/compiler.cc
@@ -8,6 +8,7 @@
 
 #include "vm/ast_printer.h"
 #include "vm/block_scheduler.h"
+#include "vm/cha.h"
 #include "vm/code_generator.h"
 #include "vm/code_patcher.h"
 #include "vm/dart_entry.h"
@@ -252,7 +253,6 @@
   bool is_compiled = false;
   Isolate* isolate = Isolate::Current();
   HANDLESCOPE(isolate);
-  isolate->set_cha_used(false);
 
   // We may reattempt compilation if the function needs to be assembled using
   // far branches on ARM and MIPS. In the else branch of the setjmp call,
@@ -269,6 +269,11 @@
     LongJumpScope jump;
     if (setjmp(*jump.Set()) == 0) {
       FlowGraph* flow_graph = NULL;
+
+      // Class hierarchy analysis is registered with the isolate in the
+      // constructor and unregisters itself upon destruction.
+      CHA cha(isolate);
+
       // TimerScope needs an isolate to be properly terminated in case of a
       // LongJump.
       {
@@ -545,12 +550,6 @@
         const Code& code = Code::Handle(
             Code::FinalizeCode(function, &assembler, optimized));
         code.set_is_optimized(optimized);
-        // CHA should not be used for unoptimized code.
-        ASSERT(optimized || !isolate->cha_used());
-        if (isolate->cha_used()) {
-          Class::Handle(function.Owner()).RegisterCHACode(code);
-          isolate->set_cha_used(false);
-        }
         graph_compiler.FinalizePcDescriptors(code);
         graph_compiler.FinalizeDeoptInfo(code);
         graph_compiler.FinalizeStackmaps(code);
@@ -572,6 +571,13 @@
           }
           function.AttachCode(code);
 
+          // Register code with the classes it depends on because of CHA.
+          for (intptr_t i = 0;
+               i < isolate->cha()->leaf_classes().length();
+               ++i) {
+            isolate->cha()->leaf_classes()[i]->RegisterCHACode(code);
+          }
+
           for (intptr_t i = 0;
                i < flow_graph->guarded_fields()->length();
                i++) {
diff --git a/runtime/vm/flow_graph_optimizer.cc b/runtime/vm/flow_graph_optimizer.cc
index e9d9241..fb8a0a6 100644
--- a/runtime/vm/flow_graph_optimizer.cc
+++ b/runtime/vm/flow_graph_optimizer.cc
@@ -2275,8 +2275,8 @@
   if (function.IsDynamicFunction() &&
       callee_receiver->IsParameter() &&
       (callee_receiver->AsParameter()->index() == 0)) {
-    return CHA::HasOverride(Class::Handle(I, function.Owner()),
-                            call->function_name());
+    return isolate()->cha()->HasOverride(Class::Handle(I, function.Owner()),
+                                         call->function_name());
   }
   return true;
 }
@@ -2293,7 +2293,8 @@
       (callee_receiver->AsParameter()->index() == 0)) {
     const String& field_name =
       String::Handle(I, Field::NameFromGetter(call->function_name()));
-    return CHA::HasOverride(Class::Handle(I, function.Owner()), field_name);
+    return isolate()->cha()->HasOverride(
+        Class::Handle(I, function.Owner()), field_name);
   }
   return true;
 }
@@ -3893,7 +3894,7 @@
 
 
 // Returns true if checking against this type is a direct class id comparison.
-static bool TypeCheckAsClassEquality(const AbstractType& type) {
+bool FlowGraphOptimizer::TypeCheckAsClassEquality(const AbstractType& type) {
   ASSERT(type.IsFinalized() && !type.IsMalformedOrMalbounded());
   // Requires CHA.
   if (!FLAG_use_cha) return false;
@@ -3902,9 +3903,9 @@
   // Signature classes have different type checking rules.
   if (type_class.IsSignatureClass()) return false;
   // Could be an interface check?
-  if (type_class.is_implemented()) return false;
-  const intptr_t type_cid = type_class.id();
-  if (CHA::HasSubclasses(type_cid)) return false;
+  if (isolate()->cha()->IsImplemented(type_class)) return false;
+  // Check if there are subclasses.
+  if (isolate()->cha()->HasSubclasses(type_class)) return false;
   const intptr_t num_type_args = type_class.NumTypeArguments();
   if (num_type_args > 0) {
     // Only raw types can be directly compared, thus disregarding type
diff --git a/runtime/vm/flow_graph_optimizer.h b/runtime/vm/flow_graph_optimizer.h
index e9a7482..a4b12c8 100644
--- a/runtime/vm/flow_graph_optimizer.h
+++ b/runtime/vm/flow_graph_optimizer.h
@@ -125,6 +125,7 @@
   bool TryInlineInt32x4Method(InstanceCallInstr* call,
                                MethodRecognizer::Kind recognized_kind);
   void ReplaceWithInstanceOf(InstanceCallInstr* instr);
+  bool TypeCheckAsClassEquality(const AbstractType& type);
   void ReplaceWithTypeCast(InstanceCallInstr* instr);
 
   bool TryReplaceInstanceCallWithInline(InstanceCallInstr* call);
diff --git a/runtime/vm/flow_graph_type_propagator.cc b/runtime/vm/flow_graph_type_propagator.cc
index 9f3e942..d7e6396 100644
--- a/runtime/vm/flow_graph_type_propagator.cc
+++ b/runtime/vm/flow_graph_type_propagator.cc
@@ -498,20 +498,6 @@
 }
 
 
-// Return true if the class is private to our internal libraries (not extendable
-// or implementable by users).
-// (TODO): Allow more libraries.
-static bool IsKnownPrivateClass(const Class& type_class) {
-  if (!Library::IsPrivate(String::Handle(type_class.Name()))) return false;
-  const Library& library = Library::Handle(type_class.library());
-  if (library.raw() == Library::CoreLibrary()) return true;
-  if (library.raw() == Library::CollectionLibrary()) return true;
-  if (library.raw() == Library::TypedDataLibrary()) return true;
-  if (library.raw() == Library::MathLibrary()) return true;
-  return false;
-}
-
-
 intptr_t CompileType::ToNullableCid() {
   if (cid_ == kIllegalCid) {
     if (type_ == NULL) {
@@ -522,11 +508,14 @@
     } else if (type_->IsVoidType()) {
       cid_ = kNullCid;
     } else if (type_->HasResolvedTypeClass()) {
-      const Class& type_class = Class::Handle(type_->type_class());
-      if (FLAG_use_cha || IsKnownPrivateClass(type_class)) {
-        // A known private class cannot be subclassed or implemented.
-        if (!type_class.is_implemented() &&
-            !CHA::HasSubclassesSafe(type_class.id())) {
+      if (FLAG_use_cha) {
+        const Class& type_class = Class::Handle(type_->type_class());
+        CHA* cha = Isolate::Current()->cha();
+        // Don't infer a cid from an abstract type for signature classes since
+        // there can be multiple compatible classes with different cids.
+        if (!type_class.IsSignatureClass() &&
+            !cha->IsImplemented(type_class) &&
+            !cha->HasSubclasses(type_class.id())) {
           cid_ = type_class.id();
         } else {
           cid_ = kDynamicCid;
@@ -743,7 +732,7 @@
     intptr_t cid = kDynamicCid;
     if (FLAG_use_cha && type.HasResolvedTypeClass()) {
       const Class& type_class = Class::Handle(type.type_class());
-      if (!CHA::HasSubclasses(type_class.id())) {
+      if (!Isolate::Current()->cha()->HasSubclasses(type_class.id())) {
         cid = type_class.id();
       }
     }
@@ -788,15 +777,18 @@
     return ZoneCompileType::Wrap(CompileType::Null());
   }
 
-  return ZoneCompileType::Wrap(CompileType::FromAbstractType(dst_type()));
+  return ZoneCompileType::Wrap(
+      CompileType::FromAbstractType(dst_type(), value_type->is_nullable()));
 }
 
 
 bool AssertAssignableInstr::RecomputeType() {
   CompileType* value_type = value()->Type();
-  return UpdateType(value_type->IsMoreSpecificThan(dst_type())
-                      ? *value_type
-                      : CompileType::FromAbstractType(dst_type()));
+  return UpdateType(
+      value_type->IsMoreSpecificThan(dst_type())
+          ? *value_type
+          : CompileType::FromAbstractType(dst_type(),
+                                          value_type->is_nullable()));
 }
 
 
diff --git a/runtime/vm/isolate.cc b/runtime/vm/isolate.cc
index 684ad60..eec4191 100644
--- a/runtime/vm/isolate.cc
+++ b/runtime/vm/isolate.cc
@@ -429,7 +429,7 @@
       stack_frame_index_(-1),
       last_allocationprofile_accumulator_reset_timestamp_(0),
       last_allocationprofile_gc_timestamp_(0),
-      cha_used_(false),
+      cha_(NULL),
       object_id_ring_(NULL),
       trace_buffer_(NULL),
       profiler_data_(NULL),
diff --git a/runtime/vm/isolate.h b/runtime/vm/isolate.h
index 9f5bdae..1f37635 100644
--- a/runtime/vm/isolate.h
+++ b/runtime/vm/isolate.h
@@ -26,6 +26,7 @@
 class ApiState;
 class Array;
 class Capability;
+class CHA;
 class Class;
 class Code;
 class CodeIndexTable;
@@ -143,8 +144,8 @@
     return OFFSET_OF(Isolate, class_table_);
   }
 
-  bool cha_used() const { return cha_used_; }
-  void set_cha_used(bool value) { cha_used_ = value; }
+  CHA* cha() const { return cha_; }
+  void set_cha(CHA* value) { cha_ = value; }
 
   MegamorphicCacheTable* megamorphic_cache_table() {
     return &megamorphic_cache_table_;
@@ -647,7 +648,7 @@
   int64_t last_allocationprofile_accumulator_reset_timestamp_;
   int64_t last_allocationprofile_gc_timestamp_;
 
-  bool cha_used_;
+  CHA* cha_;
 
   // Ring buffer of objects assigned an id.
   ObjectIdRing* object_id_ring_;
diff --git a/runtime/vm/object.cc b/runtime/vm/object.cc
index 82bdd71..09058ab 100644
--- a/runtime/vm/object.cc
+++ b/runtime/vm/object.cc
@@ -1890,62 +1890,18 @@
 }
 
 
-class FunctionName {
- public:
-  FunctionName(const String& name, String* tmp_string)
-      : name_(name), tmp_string_(tmp_string) {}
-  bool Matches(const Function& function) const {
-    if (name_.IsSymbol()) {
-      return name_.raw() == function.name();
-    } else {
-      *tmp_string_ = function.name();
-      return name_.Equals(*tmp_string_);
-    }
-  }
-  intptr_t Hash() const { return name_.Hash(); }
- private:
-  const String& name_;
-  String* tmp_string_;
-};
-
-
-// Traits for looking up Functions by name.
-class ClassFunctionsTraits {
- public:
-  // Called when growing the table.
-  static bool IsMatch(const Object& a, const Object& b) {
-    ASSERT(a.IsFunction() && b.IsFunction());
-    // Function objects are always canonical.
-    return a.raw() == b.raw();
-  }
-  static bool IsMatch(const FunctionName& name, const Object& obj) {
-    return name.Matches(Function::Cast(obj));
-  }
-  static uword Hash(const Object& key) {
-    return String::HashRawSymbol(Function::Cast(key).name());
-  }
-  static uword Hash(const FunctionName& name) {
-    return name.Hash();
-  }
-};
-typedef UnorderedHashSet<ClassFunctionsTraits> ClassFunctionsSet;
-
-
 void Class::SetFunctions(const Array& value) const {
   ASSERT(!value.IsNull());
-  StorePointer(&raw_ptr()->functions_, value.raw());
-  const intptr_t len = value.Length();
-  ClassFunctionsSet set(HashTables::New<ClassFunctionsSet>(len));
-  if (len >= kFunctionLookupHashTreshold) {
-    Function& func = Function::Handle();
-    for (intptr_t i = 0; i < len; ++i) {
-      func ^= value.At(i);
-      // Verify that all the functions in the array have this class as owner.
-      ASSERT(func.Owner() == raw());
-      set.Insert(func);
-    }
+#if defined(DEBUG)
+  // Verify that all the functions in the array have this class as owner.
+  Function& func = Function::Handle();
+  intptr_t len = value.Length();
+  for (intptr_t i = 0; i < len; i++) {
+    func ^= value.At(i);
+    ASSERT(func.Owner() == raw());
   }
-  StorePointer(&raw_ptr()->functions_hash_table_, set.Release().raw());
+#endif
+  StorePointer(&raw_ptr()->functions_, value.raw());
 }
 
 
@@ -1953,17 +1909,7 @@
   const Array& arr = Array::Handle(functions());
   const Array& new_arr = Array::Handle(Array::Grow(arr, arr.Length() + 1));
   new_arr.SetAt(arr.Length(), function);
-  StorePointer(&raw_ptr()->functions_, new_arr.raw());
-  // Add to hash table, if any.
-  const intptr_t new_len = new_arr.Length();
-  if (new_len == kFunctionLookupHashTreshold) {
-    // Transition to using hash table.
-    SetFunctions(new_arr);
-  } else if (new_len > kFunctionLookupHashTreshold) {
-    ClassFunctionsSet set(raw_ptr()->functions_hash_table_);
-    set.Insert(function);
-    StorePointer(&raw_ptr()->functions_hash_table_, set.Release().raw());
-  }
+  SetFunctions(new_arr);
 }
 
 
@@ -2650,6 +2596,7 @@
   }
 
   virtual void UpdateArrayTo(const Array& value) {
+    // TODO(fschneider): Fails for classes in the VM isolate.
     cls_.set_cha_codes(value);
   }
 
@@ -3884,15 +3831,6 @@
   ASSERT(!funcs.IsNull());
   const intptr_t len = funcs.Length();
   Function& function = isolate->FunctionHandle();
-  if (len >= kFunctionLookupHashTreshold) {
-    ClassFunctionsSet set(raw_ptr()->functions_hash_table_);
-    REUSABLE_STRING_HANDLESCOPE(isolate);
-    function ^= set.GetOrNull(FunctionName(name, &(isolate->StringHandle())));
-    // No mutations.
-    ASSERT(set.Release().raw() == raw_ptr()->functions_hash_table_);
-    return function.IsNull() ? Function::null()
-                             : CheckFunctionType(function, kind);
-  }
   if (name.IsSymbol()) {
     // Quick Symbol compare.
     NoGCScope no_gc;
diff --git a/runtime/vm/object.h b/runtime/vm/object.h
index bb4d0ac..892060d 100644
--- a/runtime/vm/object.h
+++ b/runtime/vm/object.h
@@ -949,7 +949,6 @@
   // Returns true if non-static fields are defined.
   bool HasInstanceFields() const;
 
-  // TODO(koda): Avoid VM service indexing into this array; unite w/ hash table.
   RawArray* functions() const { return raw_ptr()->functions_; }
   void SetFunctions(const Array& value) const;
   void AddFunction(const Function& function) const;
@@ -1212,9 +1211,6 @@
 
   void CalculateFieldOffsets() const;
 
-  // functions_hash_table is in use iff there are at least this many functions.
-  static const intptr_t kFunctionLookupHashTreshold = 16;
-
   // Initial value for the cached number of type arguments.
   static const intptr_t kUnknownNumTypeArguments = -1;
 
diff --git a/runtime/vm/raw_object.h b/runtime/vm/raw_object.h
index 86db68a..bff2eff 100644
--- a/runtime/vm/raw_object.h
+++ b/runtime/vm/raw_object.h
@@ -499,7 +499,6 @@
   RawString* name_;
   RawString* user_name_;
   RawArray* functions_;
-  RawArray* functions_hash_table_;
   RawArray* fields_;
   RawArray* offset_in_words_to_field_;
   RawGrowableObjectArray* closure_functions_;  // Local functions and literals.
diff --git a/tests/language/cha_deopt1_deferred_lib.dart b/tests/language/cha_deopt1_deferred_lib.dart
new file mode 100644
index 0000000..fc07315
--- /dev/null
+++ b/tests/language/cha_deopt1_deferred_lib.dart
@@ -0,0 +1,13 @@
+// Copyright (c) 2014, 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 "cha_deopt1_lib.dart";
+
+class U extends T {
+
+  m() => "good horse";
+
+}
+
+make_u() => new U();
diff --git a/tests/language/cha_deopt1_lib.dart b/tests/language/cha_deopt1_lib.dart
new file mode 100644
index 0000000..f49562d
--- /dev/null
+++ b/tests/language/cha_deopt1_lib.dart
@@ -0,0 +1,12 @@
+// Copyright (c) 2014, 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.
+
+library mylib;
+
+class T {
+
+  m() => 42;
+
+}
+
diff --git a/tests/language/cha_deopt1_test.dart b/tests/language/cha_deopt1_test.dart
new file mode 100644
index 0000000..fd860bf
--- /dev/null
+++ b/tests/language/cha_deopt1_test.dart
@@ -0,0 +1,50 @@
+// Copyright (c) 2014, 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.
+// VMOptions=--optimization-counter-threshold=100
+
+// Test lazy deoptimization at field guards with deferred loading.
+
+import "package:expect/expect.dart";
+import "cha_deopt1_lib.dart";
+import "cha_deopt1_deferred_lib.dart" deferred as d;
+
+var loaded = false;
+
+main() {
+  for (var i = 0; i < 2000; i++) bla();
+  Expect.equals(42, bla());
+  d.loadLibrary().then((_) {
+    loaded = true;
+    Expect.equals("good horse", bla());
+  });
+}
+
+make_t() {
+  try {
+    if (loaded) {
+      return d.make_u();
+    } else {
+      return new T();
+    }
+  } catch (e) { }
+}
+
+bla() {
+  var x = new X();
+  x.test(make_t());
+  return x.fld.m();
+}
+
+
+class X {
+  T fld = new T();
+
+  test(T t) {
+    if (t != null) {
+      T tmp = t;
+      fld = tmp;
+    }
+  }
+}
+
diff --git a/tests/language/cha_deopt2_deferred_lib.dart b/tests/language/cha_deopt2_deferred_lib.dart
new file mode 100644
index 0000000..b1ef444
--- /dev/null
+++ b/tests/language/cha_deopt2_deferred_lib.dart
@@ -0,0 +1,9 @@
+// Copyright (c) 2014, 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 "cha_deopt2_lib.dart";
+
+class U extends T { }
+
+make_u() => new U();
diff --git a/tests/language/cha_deopt2_lib.dart b/tests/language/cha_deopt2_lib.dart
new file mode 100644
index 0000000..3af6575
--- /dev/null
+++ b/tests/language/cha_deopt2_lib.dart
@@ -0,0 +1,13 @@
+// Copyright (c) 2014, 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.
+
+library mylib;
+
+class A { }
+class B { }
+class C { }
+class D { }
+class E { }
+class T { }
+
diff --git a/tests/language/cha_deopt2_test.dart b/tests/language/cha_deopt2_test.dart
new file mode 100644
index 0000000..5a4ed04
--- /dev/null
+++ b/tests/language/cha_deopt2_test.dart
@@ -0,0 +1,39 @@
+// Copyright (c) 2014, 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.
+// VMOptions=--optimization-counter-threshold=100
+
+// Test lazy deoptimization at type checks with deferred loading.
+
+import "package:expect/expect.dart";
+import "cha_deopt2_lib.dart";
+import "cha_deopt2_deferred_lib.dart" deferred as d;
+
+var loaded = false;
+
+main() {
+  for (var i = 0; i < 2000; i++) bla();
+  Expect.equals(1, bla());
+  d.loadLibrary().then((_) {
+    loaded = true;
+    Expect.equals(1, bla());
+  });
+}
+
+make_array() {
+  try {
+    if (loaded) {
+      return [new A(), new B(), new C(), new D(), new E(), d.make_u()];
+    } else {
+      return [new A(), new B(), new C(), new D(), new E(), new T()];
+    }
+  } catch (e) { }
+}
+
+bla() {
+  var count = 0;
+  for (var x in make_array()) {
+    if (x is T) count++;
+  }
+  return count;
+}
diff --git a/tests/language/cha_deopt3_deferred_lib.dart b/tests/language/cha_deopt3_deferred_lib.dart
new file mode 100644
index 0000000..f9cffb1
--- /dev/null
+++ b/tests/language/cha_deopt3_deferred_lib.dart
@@ -0,0 +1,9 @@
+// Copyright (c) 2014, 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 "cha_deopt3_lib.dart";
+
+class U implements T { }
+
+make_u() => new U();
diff --git a/tests/language/cha_deopt3_lib.dart b/tests/language/cha_deopt3_lib.dart
new file mode 100644
index 0000000..3af6575
--- /dev/null
+++ b/tests/language/cha_deopt3_lib.dart
@@ -0,0 +1,13 @@
+// Copyright (c) 2014, 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.
+
+library mylib;
+
+class A { }
+class B { }
+class C { }
+class D { }
+class E { }
+class T { }
+
diff --git a/tests/language/cha_deopt3_test.dart b/tests/language/cha_deopt3_test.dart
new file mode 100644
index 0000000..3dc61b9
--- /dev/null
+++ b/tests/language/cha_deopt3_test.dart
@@ -0,0 +1,39 @@
+// Copyright (c) 2014, 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.
+// VMOptions=--optimization-counter-threshold=100
+
+// Test lazy deoptimization at type checks with interface implementation.
+
+import "package:expect/expect.dart";
+import "cha_deopt3_lib.dart";
+import "cha_deopt3_deferred_lib.dart" deferred as d;
+
+var loaded = false;
+
+main() {
+  for (var i = 0; i < 2000; i++) bla();
+  Expect.equals(1, bla());
+  d.loadLibrary().then((_) {
+    loaded = true;
+    Expect.equals(1, bla());
+  });
+}
+
+make_array() {
+  try {
+    if (loaded) {
+      return [new A(), new B(), new C(), new D(), new E(), d.make_u()];
+    } else {
+      return [new A(), new B(), new C(), new D(), new E(), new T()];
+    }
+  } catch (e) { }
+}
+
+bla() {
+  var count = 0;
+  for (var x in make_array()) {
+    if (x is T) count++;
+  }
+  return count;
+}
diff --git a/tests/language/language_dart2js.status b/tests/language/language_dart2js.status
index 7c9aa07..498301e 100644
--- a/tests/language/language_dart2js.status
+++ b/tests/language/language_dart2js.status
@@ -245,6 +245,9 @@
 new_expression_type_args_test/01: Fail # Wrongly reports compile-time error.
 
 deferred*: skip # Issue 17523
+cha_deopt1_test: skip # Issue 17523
+cha_deopt2_test: skip # Issue 17523
+cha_deopt3_test: skip # Issue 17523
 
 [ $compiler == dart2dart && $minified ]
 cyclic_type_test/0*: Fail # Issue 12605.
diff --git a/tests/standalone/issue14236_test.dart b/tests/standalone/issue14236_test.dart
index 7e248f3..f720a65 100644
--- a/tests/standalone/issue14236_test.dart
+++ b/tests/standalone/issue14236_test.dart
Binary files differ
diff --git a/tools/VERSION b/tools/VERSION
index 4d548ae..938a641 100644
--- a/tools/VERSION
+++ b/tools/VERSION
@@ -28,4 +28,4 @@
 MINOR 6
 PATCH 0
 PRERELEASE 9
-PRERELEASE_PATCH 1
+PRERELEASE_PATCH 2