diff --git a/compiler/compiler.h b/compiler/compiler.h
index 2ca0b77..908d366 100644
--- a/compiler/compiler.h
+++ b/compiler/compiler.h
@@ -27,6 +27,7 @@
   class JitCodeCache;
 }
 namespace mirror {
+  class ClassLoader;
   class DexCache;
 }
 
@@ -63,7 +64,7 @@
                                   InvokeType invoke_type,
                                   uint16_t class_def_idx,
                                   uint32_t method_idx,
-                                  jobject class_loader,
+                                  Handle<mirror::ClassLoader> class_loader,
                                   const DexFile& dex_file,
                                   Handle<mirror::DexCache> dex_cache) const = 0;
 
diff --git a/compiler/dex/dex_to_dex_compiler.cc b/compiler/dex/dex_to_dex_compiler.cc
index d4f6545..76aeaa5 100644
--- a/compiler/dex/dex_to_dex_compiler.cc
+++ b/compiler/dex/dex_to_dex_compiler.cc
@@ -284,16 +284,13 @@
   }
   uint32_t method_idx = is_range ? inst->VRegB_3rc() : inst->VRegB_35c();
   ScopedObjectAccess soa(Thread::Current());
-  StackHandleScope<1> hs(soa.Self());
-  Handle<mirror::ClassLoader> class_loader(hs.NewHandle(
-      soa.Decode<mirror::ClassLoader>(unit_.GetClassLoader())));
 
   ClassLinker* class_linker = unit_.GetClassLinker();
   ArtMethod* resolved_method = class_linker->ResolveMethod<ClassLinker::kForceICCECheck>(
       GetDexFile(),
       method_idx,
       unit_.GetDexCache(),
-      class_loader,
+      unit_.GetClassLoader(),
       /* referrer */ nullptr,
       kVirtual);
 
@@ -330,7 +327,7 @@
     InvokeType invoke_type ATTRIBUTE_UNUSED,
     uint16_t class_def_idx,
     uint32_t method_idx,
-    jobject class_loader,
+    Handle<mirror::ClassLoader> class_loader,
     const DexFile& dex_file,
     DexToDexCompilationLevel dex_to_dex_compilation_level) {
   DCHECK(driver != nullptr);
diff --git a/compiler/dex/dex_to_dex_compiler.h b/compiler/dex/dex_to_dex_compiler.h
index 0a00d45..00c596d 100644
--- a/compiler/dex/dex_to_dex_compiler.h
+++ b/compiler/dex/dex_to_dex_compiler.h
@@ -18,6 +18,7 @@
 #define ART_COMPILER_DEX_DEX_TO_DEX_COMPILER_H_
 
 #include "dex_file.h"
+#include "handle.h"
 #include "invoke_type.h"
 
 namespace art {
@@ -25,6 +26,10 @@
 class CompiledMethod;
 class CompilerDriver;
 
+namespace mirror {
+class ClassLoader;
+}  // namespace mirror
+
 namespace optimizer {
 
 enum class DexToDexCompilationLevel {
@@ -40,7 +45,7 @@
                               InvokeType invoke_type,
                               uint16_t class_def_idx,
                               uint32_t method_idx,
-                              jobject class_loader,
+                              Handle<mirror::ClassLoader> class_loader,
                               const DexFile& dex_file,
                               DexToDexCompilationLevel dex_to_dex_compilation_level);
 
diff --git a/compiler/driver/compiler_driver-inl.h b/compiler/driver/compiler_driver-inl.h
index f296851..5823306 100644
--- a/compiler/driver/compiler_driver-inl.h
+++ b/compiler/driver/compiler_driver-inl.h
@@ -31,17 +31,12 @@
 
 namespace art {
 
-inline mirror::ClassLoader* CompilerDriver::GetClassLoader(const ScopedObjectAccess& soa,
-                                                           const DexCompilationUnit* mUnit) {
-  return soa.Decode<mirror::ClassLoader>(mUnit->GetClassLoader()).Ptr();
-}
-
 inline mirror::Class* CompilerDriver::ResolveClass(
     const ScopedObjectAccess& soa, Handle<mirror::DexCache> dex_cache,
     Handle<mirror::ClassLoader> class_loader, dex::TypeIndex cls_index,
     const DexCompilationUnit* mUnit) {
   DCHECK_EQ(dex_cache->GetDexFile(), mUnit->GetDexFile());
-  DCHECK_EQ(class_loader.Get(), GetClassLoader(soa, mUnit));
+  DCHECK_EQ(class_loader.Get(), mUnit->GetClassLoader().Get());
   mirror::Class* cls = mUnit->GetClassLinker()->ResolveType(
       *mUnit->GetDexFile(), cls_index, dex_cache, class_loader);
   DCHECK_EQ(cls == nullptr, soa.Self()->IsExceptionPending());
@@ -56,7 +51,7 @@
     const ScopedObjectAccess& soa, Handle<mirror::DexCache> dex_cache,
     Handle<mirror::ClassLoader> class_loader, const DexCompilationUnit* mUnit) {
   DCHECK_EQ(dex_cache->GetDexFile(), mUnit->GetDexFile());
-  DCHECK_EQ(class_loader.Get(), GetClassLoader(soa, mUnit));
+  DCHECK_EQ(class_loader.Get(), mUnit->GetClassLoader().Get());
   const DexFile::MethodId& referrer_method_id =
       mUnit->GetDexFile()->GetMethodId(mUnit->GetDexMethodIndex());
   return ResolveClass(soa, dex_cache, class_loader, referrer_method_id.class_idx_, mUnit);
@@ -87,7 +82,7 @@
     const ScopedObjectAccess& soa, Handle<mirror::DexCache> dex_cache,
     Handle<mirror::ClassLoader> class_loader, const DexCompilationUnit* mUnit,
     uint32_t field_idx, bool is_static) {
-  DCHECK_EQ(class_loader.Get(), GetClassLoader(soa, mUnit));
+  DCHECK_EQ(class_loader.Get(), mUnit->GetClassLoader().Get());
   return ResolveFieldWithDexFile(soa, dex_cache, class_loader, mUnit->GetDexFile(), field_idx,
                                  is_static);
 }
@@ -139,7 +134,7 @@
     ScopedObjectAccess& soa, Handle<mirror::DexCache> dex_cache,
     Handle<mirror::ClassLoader> class_loader, const DexCompilationUnit* mUnit,
     uint32_t method_idx, InvokeType invoke_type, bool check_incompatible_class_change) {
-  DCHECK_EQ(class_loader.Get(), GetClassLoader(soa, mUnit));
+  DCHECK_EQ(class_loader.Get(), mUnit->GetClassLoader().Get());
   ArtMethod* resolved_method =
       check_incompatible_class_change
           ? mUnit->GetClassLinker()->ResolveMethod<ClassLinker::kForceICCECheck>(
diff --git a/compiler/driver/compiler_driver.cc b/compiler/driver/compiler_driver.cc
index caab5fb..9950987 100644
--- a/compiler/driver/compiler_driver.cc
+++ b/compiler/driver/compiler_driver.cc
@@ -581,7 +581,7 @@
                           InvokeType invoke_type,
                           uint16_t class_def_idx,
                           uint32_t method_idx,
-                          jobject class_loader,
+                          Handle<mirror::ClassLoader> class_loader,
                           const DexFile& dex_file,
                           optimizer::DexToDexCompilationLevel dex_to_dex_compilation_level,
                           bool compilation_enabled,
@@ -622,9 +622,6 @@
       // Look-up the ArtMethod associated with this code_item (if any)
       // -- It is later used to lookup any [optimization] annotations for this method.
       ScopedObjectAccess soa(self);
-      StackHandleScope<1> hs(soa.Self());
-      Handle<mirror::ClassLoader> class_loader_handle(hs.NewHandle(
-          soa.Decode<mirror::ClassLoader>(class_loader)));
 
       // TODO: Lookup annotation from DexFile directly without resolving method.
       ArtMethod* method =
@@ -632,7 +629,7 @@
               dex_file,
               method_idx,
               dex_cache,
-              class_loader_handle,
+              class_loader,
               /* referrer */ nullptr,
               invoke_type);
 
@@ -679,9 +676,14 @@
 
     if (compile) {
       // NOTE: if compiler declines to compile this method, it will return null.
-      compiled_method = driver->GetCompiler()->Compile(code_item, access_flags, invoke_type,
-                                                       class_def_idx, method_idx, class_loader,
-                                                       dex_file, dex_cache);
+      compiled_method = driver->GetCompiler()->Compile(code_item,
+                                                       access_flags,
+                                                       invoke_type,
+                                                       class_def_idx,
+                                                       method_idx,
+                                                       class_loader,
+                                                       dex_file,
+                                                       dex_cache);
     }
     if (compiled_method == nullptr &&
         dex_to_dex_compilation_level != optimizer::DexToDexCompilationLevel::kDontDexToDexCompile) {
@@ -728,12 +730,14 @@
   uint32_t method_idx = method->GetDexMethodIndex();
   uint32_t access_flags = method->GetAccessFlags();
   InvokeType invoke_type = method->GetInvokeType();
-  StackHandleScope<1> hs(self);
+  StackHandleScope<2> hs(self);
   Handle<mirror::DexCache> dex_cache(hs.NewHandle(method->GetDexCache()));
+  Handle<mirror::ClassLoader> class_loader(
+      hs.NewHandle(method->GetDeclaringClass()->GetClassLoader()));
   {
     ScopedObjectAccessUnchecked soa(self);
     ScopedLocalRef<jobject> local_class_loader(
-        soa.Env(), soa.AddLocalReference<jobject>(method->GetDeclaringClass()->GetClassLoader()));
+        soa.Env(), soa.AddLocalReference<jobject>(class_loader.Get()));
     jclass_loader = soa.Env()->NewGlobalRef(local_class_loader.get());
     // Find the dex_file
     dex_file = method->GetDexFile();
@@ -767,7 +771,7 @@
                 invoke_type,
                 class_def_idx,
                 method_idx,
-                jclass_loader,
+                class_loader,
                 *dex_file,
                 dex_to_dex_compilation_level,
                 true,
@@ -793,7 +797,7 @@
                   invoke_type,
                   class_def_idx,
                   method_idx,
-                  jclass_loader,
+                  class_loader,
                   *dex_file,
                   dex_to_dex_compilation_level,
                   true,
@@ -1073,22 +1077,30 @@
 
 class ResolveCatchBlockExceptionsClassVisitor : public ClassVisitor {
  public:
-  explicit ResolveCatchBlockExceptionsClassVisitor(
-      std::set<std::pair<dex::TypeIndex, const DexFile*>>& exceptions_to_resolve)
-     : exceptions_to_resolve_(exceptions_to_resolve) {}
+  ResolveCatchBlockExceptionsClassVisitor() : classes_() {}
 
   virtual bool operator()(ObjPtr<mirror::Class> c) OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_) {
-    const auto pointer_size = Runtime::Current()->GetClassLinker()->GetImagePointerSize();
-    for (auto& m : c->GetMethods(pointer_size)) {
-      ResolveExceptionsForMethod(&m);
-    }
+    classes_.push_back(c);
     return true;
   }
 
- private:
-  void ResolveExceptionsForMethod(ArtMethod* method_handle)
+  void FindExceptionTypesToResolve(
+      std::set<std::pair<dex::TypeIndex, const DexFile*>>* exceptions_to_resolve)
       REQUIRES_SHARED(Locks::mutator_lock_) {
-    const DexFile::CodeItem* code_item = method_handle->GetCodeItem();
+    const auto pointer_size = Runtime::Current()->GetClassLinker()->GetImagePointerSize();
+    for (ObjPtr<mirror::Class> klass : classes_) {
+      for (ArtMethod& method : klass->GetMethods(pointer_size)) {
+        FindExceptionTypesToResolveForMethod(&method, exceptions_to_resolve);
+      }
+    }
+  }
+
+ private:
+  void FindExceptionTypesToResolveForMethod(
+      ArtMethod* method,
+      std::set<std::pair<dex::TypeIndex, const DexFile*>>* exceptions_to_resolve)
+      REQUIRES_SHARED(Locks::mutator_lock_) {
+    const DexFile::CodeItem* code_item = method->GetCodeItem();
     if (code_item == nullptr) {
       return;  // native or abstract method
     }
@@ -1108,9 +1120,9 @@
         dex::TypeIndex encoded_catch_handler_handlers_type_idx =
             dex::TypeIndex(DecodeUnsignedLeb128(&encoded_catch_handler_list));
         // Add to set of types to resolve if not already in the dex cache resolved types
-        if (!method_handle->IsResolvedTypeIdx(encoded_catch_handler_handlers_type_idx)) {
-          exceptions_to_resolve_.emplace(encoded_catch_handler_handlers_type_idx,
-                                         method_handle->GetDexFile());
+        if (!method->IsResolvedTypeIdx(encoded_catch_handler_handlers_type_idx)) {
+          exceptions_to_resolve->emplace(encoded_catch_handler_handlers_type_idx,
+                                         method->GetDexFile());
         }
         // ignore address associated with catch handler
         DecodeUnsignedLeb128(&encoded_catch_handler_list);
@@ -1122,7 +1134,7 @@
     }
   }
 
-  std::set<std::pair<dex::TypeIndex, const DexFile*>>& exceptions_to_resolve_;
+  std::vector<ObjPtr<mirror::Class>> classes_;
 };
 
 class RecordImageClassesVisitor : public ClassVisitor {
@@ -1176,8 +1188,14 @@
       hs.NewHandle(class_linker->FindSystemClass(self, "Ljava/lang/Throwable;")));
   do {
     unresolved_exception_types.clear();
-    ResolveCatchBlockExceptionsClassVisitor visitor(unresolved_exception_types);
-    class_linker->VisitClasses(&visitor);
+    {
+      // Thread suspension is not allowed while ResolveCatchBlockExceptionsClassVisitor
+      // is using a std::vector<ObjPtr<mirror::Class>>.
+      ScopedAssertNoThreadSuspension ants(__FUNCTION__);
+      ResolveCatchBlockExceptionsClassVisitor visitor;
+      class_linker->VisitClasses(&visitor);
+      visitor.FindExceptionTypesToResolve(&unresolved_exception_types);
+    }
     for (const auto& exception_type : unresolved_exception_types) {
       dex::TypeIndex exception_type_idx = exception_type.first;
       const DexFile* dex_file = exception_type.second;
@@ -1428,19 +1446,14 @@
   dex_to_dex_references_.back().GetMethodIndexes().SetBit(method_ref.dex_method_index);
 }
 
-bool CompilerDriver::CanAccessTypeWithoutChecks(uint32_t referrer_idx,
-                                                Handle<mirror::DexCache> dex_cache,
-                                                dex::TypeIndex type_idx) {
-  // Get type from dex cache assuming it was populated by the verifier
-  mirror::Class* resolved_class = dex_cache->GetResolvedType(type_idx);
+bool CompilerDriver::CanAccessTypeWithoutChecks(ObjPtr<mirror::Class> referrer_class,
+                                                ObjPtr<mirror::Class> resolved_class) {
   if (resolved_class == nullptr) {
     stats_->TypeNeedsAccessCheck();
     return false;  // Unknown class needs access checks.
   }
-  const DexFile::MethodId& method_id = dex_cache->GetDexFile()->GetMethodId(referrer_idx);
   bool is_accessible = resolved_class->IsPublic();  // Public classes are always accessible.
   if (!is_accessible) {
-    mirror::Class* referrer_class = dex_cache->GetResolvedType(method_id.class_idx_);
     if (referrer_class == nullptr) {
       stats_->TypeNeedsAccessCheck();
       return false;  // Incomplete referrer knowledge needs access check.
@@ -1457,12 +1470,9 @@
   return is_accessible;
 }
 
-bool CompilerDriver::CanAccessInstantiableTypeWithoutChecks(uint32_t referrer_idx,
-                                                            Handle<mirror::DexCache> dex_cache,
-                                                            dex::TypeIndex type_idx,
+bool CompilerDriver::CanAccessInstantiableTypeWithoutChecks(ObjPtr<mirror::Class> referrer_class,
+                                                            ObjPtr<mirror::Class> resolved_class,
                                                             bool* finalizable) {
-  // Get type from dex cache assuming it was populated by the verifier.
-  mirror::Class* resolved_class = dex_cache->GetResolvedType(type_idx);
   if (resolved_class == nullptr) {
     stats_->TypeNeedsAccessCheck();
     // Be conservative.
@@ -1470,10 +1480,8 @@
     return false;  // Unknown class needs access checks.
   }
   *finalizable = resolved_class->IsFinalizable();
-  const DexFile::MethodId& method_id = dex_cache->GetDexFile()->GetMethodId(referrer_idx);
   bool is_accessible = resolved_class->IsPublic();  // Public classes are always accessible.
   if (!is_accessible) {
-    mirror::Class* referrer_class = dex_cache->GetResolvedType(method_id.class_idx_);
     if (referrer_class == nullptr) {
       stats_->TypeNeedsAccessCheck();
       return false;  // Incomplete referrer knowledge needs access check.
@@ -1517,9 +1525,7 @@
   mirror::Class* referrer_class;
   Handle<mirror::DexCache> dex_cache(mUnit->GetDexCache());
   {
-    StackHandleScope<1> hs(soa.Self());
-    Handle<mirror::ClassLoader> class_loader_handle(
-        hs.NewHandle(soa.Decode<mirror::ClassLoader>(mUnit->GetClassLoader())));
+    Handle<mirror::ClassLoader> class_loader_handle = mUnit->GetClassLoader();
     resolved_field = ResolveField(soa, dex_cache, class_loader_handle, mUnit, field_idx, false);
     referrer_class = resolved_field != nullptr
         ? ResolveCompilingMethodsClass(soa, dex_cache, class_loader_handle, mUnit) : nullptr;
@@ -2666,10 +2672,18 @@
         continue;
       }
       previous_direct_method_idx = method_idx;
-      CompileMethod(soa.Self(), driver, it.GetMethodCodeItem(), it.GetMethodAccessFlags(),
-                    it.GetMethodInvokeType(class_def), class_def_index,
-                    method_idx, jclass_loader, dex_file, dex_to_dex_compilation_level,
-                    compilation_enabled, dex_cache);
+      CompileMethod(soa.Self(),
+                    driver,
+                    it.GetMethodCodeItem(),
+                    it.GetMethodAccessFlags(),
+                    it.GetMethodInvokeType(class_def),
+                    class_def_index,
+                    method_idx,
+                    class_loader,
+                    dex_file,
+                    dex_to_dex_compilation_level,
+                    compilation_enabled,
+                    dex_cache);
       it.Next();
     }
     // Compile virtual methods
@@ -2683,10 +2697,17 @@
         continue;
       }
       previous_virtual_method_idx = method_idx;
-      CompileMethod(soa.Self(), driver, it.GetMethodCodeItem(), it.GetMethodAccessFlags(),
-                    it.GetMethodInvokeType(class_def), class_def_index,
-                    method_idx, jclass_loader, dex_file, dex_to_dex_compilation_level,
-                    compilation_enabled, dex_cache);
+      CompileMethod(soa.Self(),
+                    driver, it.GetMethodCodeItem(),
+                    it.GetMethodAccessFlags(),
+                    it.GetMethodInvokeType(class_def),
+                    class_def_index,
+                    method_idx,
+                    class_loader,
+                    dex_file,
+                    dex_to_dex_compilation_level,
+                    compilation_enabled,
+                    dex_cache);
       it.Next();
     }
     DCHECK(!it.HasNext());
diff --git a/compiler/driver/compiler_driver.h b/compiler/driver/compiler_driver.h
index 6ba1692..cbde587 100644
--- a/compiler/driver/compiler_driver.h
+++ b/compiler/driver/compiler_driver.h
@@ -187,16 +187,14 @@
       REQUIRES(!requires_constructor_barrier_lock_);
 
   // Are runtime access checks necessary in the compiled code?
-  bool CanAccessTypeWithoutChecks(uint32_t referrer_idx,
-                                  Handle<mirror::DexCache> dex_cache,
-                                  dex::TypeIndex type_idx)
+  bool CanAccessTypeWithoutChecks(ObjPtr<mirror::Class> referrer_class,
+                                  ObjPtr<mirror::Class> resolved_class)
       REQUIRES_SHARED(Locks::mutator_lock_);
 
   // Are runtime access and instantiable checks necessary in the code?
   // out_is_finalizable is set to whether the type is finalizable.
-  bool CanAccessInstantiableTypeWithoutChecks(uint32_t referrer_idx,
-                                              Handle<mirror::DexCache> dex_cache,
-                                              dex::TypeIndex type_idx,
+  bool CanAccessInstantiableTypeWithoutChecks(ObjPtr<mirror::Class> referrer_class,
+                                              ObjPtr<mirror::Class> resolved_class,
                                               bool* out_is_finalizable)
       REQUIRES_SHARED(Locks::mutator_lock_);
 
@@ -374,10 +372,6 @@
                                       uint32_t field_idx)
       REQUIRES_SHARED(Locks::mutator_lock_);
 
-  mirror::ClassLoader* GetClassLoader(const ScopedObjectAccess& soa,
-                                      const DexCompilationUnit* mUnit)
-    REQUIRES_SHARED(Locks::mutator_lock_);
-
  private:
   void PreCompile(jobject class_loader,
                   const std::vector<const DexFile*>& dex_files,
diff --git a/compiler/driver/compiler_driver_test.cc b/compiler/driver/compiler_driver_test.cc
index 316117f..562f97b 100644
--- a/compiler/driver/compiler_driver_test.cc
+++ b/compiler/driver/compiler_driver_test.cc
@@ -101,6 +101,7 @@
 };
 
 // Disabled due to 10 second runtime on host
+// TODO: Update the test for hash-based dex cache arrays. Bug: 30627598
 TEST_F(CompilerDriverTest, DISABLED_LARGE_CompileDexLibCore) {
   CompileAll(nullptr);
 
diff --git a/compiler/driver/dex_compilation_unit.cc b/compiler/driver/dex_compilation_unit.cc
index 47b1929..7e8e812 100644
--- a/compiler/driver/dex_compilation_unit.cc
+++ b/compiler/driver/dex_compilation_unit.cc
@@ -21,7 +21,7 @@
 
 namespace art {
 
-DexCompilationUnit::DexCompilationUnit(jobject class_loader,
+DexCompilationUnit::DexCompilationUnit(Handle<mirror::ClassLoader> class_loader,
                                        ClassLinker* class_linker,
                                        const DexFile& dex_file,
                                        const DexFile::CodeItem* code_item,
diff --git a/compiler/driver/dex_compilation_unit.h b/compiler/driver/dex_compilation_unit.h
index 854927d..24a9a5b 100644
--- a/compiler/driver/dex_compilation_unit.h
+++ b/compiler/driver/dex_compilation_unit.h
@@ -34,7 +34,7 @@
 
 class DexCompilationUnit : public DeletableArenaObject<kArenaAllocMisc> {
  public:
-  DexCompilationUnit(jobject class_loader,
+  DexCompilationUnit(Handle<mirror::ClassLoader> class_loader,
                      ClassLinker* class_linker,
                      const DexFile& dex_file,
                      const DexFile::CodeItem* code_item,
@@ -44,7 +44,7 @@
                      const VerifiedMethod* verified_method,
                      Handle<mirror::DexCache> dex_cache);
 
-  jobject GetClassLoader() const {
+  Handle<mirror::ClassLoader> GetClassLoader() const {
     return class_loader_;
   }
 
@@ -113,7 +113,7 @@
   }
 
  private:
-  const jobject class_loader_;
+  const Handle<mirror::ClassLoader> class_loader_;
 
   ClassLinker* const class_linker_;
 
@@ -125,7 +125,7 @@
   const uint32_t access_flags_;
   const VerifiedMethod* verified_method_;
 
-  Handle<mirror::DexCache> dex_cache_;
+  const Handle<mirror::DexCache> dex_cache_;
 
   std::string symbol_;
 };
diff --git a/compiler/image_writer.cc b/compiler/image_writer.cc
index 9312a1c..aa0791f 100644
--- a/compiler/image_writer.cc
+++ b/compiler/image_writer.cc
@@ -941,9 +941,11 @@
     }
     ObjPtr<mirror::DexCache> dex_cache = self->DecodeJObject(data.weak_root)->AsDexCache();
     for (size_t i = 0; i < dex_cache->NumResolvedTypes(); i++) {
-      Class* klass = dex_cache->GetResolvedType(dex::TypeIndex(i));
+      mirror::TypeDexCachePair pair =
+          dex_cache->GetResolvedTypes()[i].load(std::memory_order_relaxed);
+      mirror::Class* klass = pair.object.Read();
       if (klass != nullptr && !KeepClass(klass)) {
-        dex_cache->SetResolvedType(dex::TypeIndex(i), nullptr);
+        dex_cache->ClearResolvedType(dex::TypeIndex(pair.index));
       }
     }
     ArtMethod** resolved_methods = dex_cache->GetResolvedMethods();
@@ -1575,10 +1577,8 @@
     }
     // Calculate the size of the class table.
     ReaderMutexLock mu(self, *Locks::classlinker_classes_lock_);
-    CHECK_EQ(class_loaders_.size(), compile_app_image_ ? 1u : 0u);
-    mirror::ClassLoader* class_loader = compile_app_image_ ? *class_loaders_.begin() : nullptr;
-    DCHECK_EQ(image_info.class_table_->NumZygoteClasses(class_loader), 0u);
-    if (image_info.class_table_->NumNonZygoteClasses(class_loader) != 0u) {
+    DCHECK_EQ(image_info.class_table_->NumReferencedZygoteClasses(), 0u);
+    if (image_info.class_table_->NumReferencedNonZygoteClasses() != 0u) {
       image_info.class_table_bytes_ += image_info.class_table_->WriteToMemory(nullptr);
     }
   }
@@ -1923,10 +1923,8 @@
     // above comment for intern tables.
     ClassTable temp_class_table;
     temp_class_table.ReadFromMemory(class_table_memory_ptr);
-    CHECK_EQ(class_loaders_.size(), compile_app_image_ ? 1u : 0u);
-    mirror::ClassLoader* class_loader = compile_app_image_ ? *class_loaders_.begin() : nullptr;
-    CHECK_EQ(temp_class_table.NumZygoteClasses(class_loader),
-             table->NumNonZygoteClasses(class_loader) + table->NumZygoteClasses(class_loader));
+    CHECK_EQ(temp_class_table.NumReferencedZygoteClasses(),
+             table->NumReferencedNonZygoteClasses() + table->NumReferencedZygoteClasses());
     UnbufferedRootVisitor visitor(&root_visitor, RootInfo(kRootUnknown));
     temp_class_table.VisitRoots(visitor);
   }
@@ -2214,7 +2212,7 @@
     orig_dex_cache->FixupStrings(NativeCopyLocation(orig_strings, orig_dex_cache),
                                  ImageAddressVisitor(this));
   }
-  GcRoot<mirror::Class>* orig_types = orig_dex_cache->GetResolvedTypes();
+  mirror::TypeDexCacheType* orig_types = orig_dex_cache->GetResolvedTypes();
   if (orig_types != nullptr) {
     copy_dex_cache->SetFieldPtrWithSize<false>(mirror::DexCache::ResolvedTypesOffset(),
                                                NativeLocationInImage(orig_types),
diff --git a/compiler/image_writer.h b/compiler/image_writer.h
index cc7df1c..bdc7146 100644
--- a/compiler/image_writer.h
+++ b/compiler/image_writer.h
@@ -51,8 +51,13 @@
 }  // namespace space
 }  // namespace gc
 
+namespace mirror {
+class ClassLoader;
+}  // namespace mirror
+
 class ClassLoaderVisitor;
 class ClassTable;
+class ImtConflictTable;
 
 static constexpr int kInvalidFd = -1;
 
@@ -79,6 +84,11 @@
     return true;
   }
 
+  ObjPtr<mirror::ClassLoader> GetClassLoader() {
+    CHECK_EQ(class_loaders_.size(), compile_app_image_ ? 1u : 0u);
+    return compile_app_image_ ? *class_loaders_.begin() : nullptr;
+  }
+
   template <typename T>
   T* GetImageAddress(T* object) const REQUIRES_SHARED(Locks::mutator_lock_) {
     if (object == nullptr || IsInBootImage(object)) {
diff --git a/compiler/oat_writer.cc b/compiler/oat_writer.cc
index a3f61d6..afcdf5e 100644
--- a/compiler/oat_writer.cc
+++ b/compiler/oat_writer.cc
@@ -1061,6 +1061,7 @@
   WriteCodeMethodVisitor(OatWriter* writer, OutputStream* out, const size_t file_offset,
                          size_t relative_offset) SHARED_LOCK_FUNCTION(Locks::mutator_lock_)
     : OatDexMethodVisitor(writer, relative_offset),
+      class_loader_(writer->HasImage() ? writer->image_writer_->GetClassLoader() : nullptr),
       out_(out),
       file_offset_(file_offset),
       soa_(Thread::Current()),
@@ -1246,6 +1247,7 @@
   }
 
  private:
+  ObjPtr<mirror::ClassLoader> class_loader_;
   OutputStream* const out_;
   const size_t file_offset_;
   const ScopedObjectAccess soa_;
@@ -1304,10 +1306,12 @@
   }
 
   mirror::Class* GetTargetType(const LinkerPatch& patch) REQUIRES_SHARED(Locks::mutator_lock_) {
+    DCHECK(writer_->HasImage());
     ObjPtr<mirror::DexCache> dex_cache = GetDexCache(patch.TargetTypeDexFile());
-    mirror::Class* type = dex_cache->GetResolvedType(patch.TargetTypeIndex());
+    ObjPtr<mirror::Class> type =
+        ClassLinker::LookupResolvedType(patch.TargetTypeIndex(), dex_cache, class_loader_);
     CHECK(type != nullptr);
-    return type;
+    return type.Ptr();
   }
 
   mirror::String* GetTargetString(const LinkerPatch& patch) REQUIRES_SHARED(Locks::mutator_lock_) {
diff --git a/compiler/optimizing/builder.h b/compiler/optimizing/builder.h
index e4ad422..3a4c9db 100644
--- a/compiler/optimizing/builder.h
+++ b/compiler/optimizing/builder.h
@@ -54,7 +54,10 @@
         compiler_driver_(driver),
         compilation_stats_(compiler_stats),
         block_builder_(graph, dex_file, code_item),
-        ssa_builder_(graph, dex_compilation_unit->GetDexCache(), handles),
+        ssa_builder_(graph,
+                     dex_compilation_unit->GetClassLoader(),
+                     dex_compilation_unit->GetDexCache(),
+                     handles),
         instruction_builder_(graph,
                              &block_builder_,
                              &ssa_builder_,
@@ -80,10 +83,12 @@
         code_item_(code_item),
         dex_compilation_unit_(nullptr),
         compiler_driver_(nullptr),
-        null_dex_cache_(),
         compilation_stats_(nullptr),
         block_builder_(graph, nullptr, code_item),
-        ssa_builder_(graph, null_dex_cache_, handles),
+        ssa_builder_(graph,
+                     handles->NewHandle<mirror::ClassLoader>(nullptr),
+                     handles->NewHandle<mirror::DexCache>(nullptr),
+                     handles),
         instruction_builder_(graph,
                              &block_builder_,
                              &ssa_builder_,
@@ -96,7 +101,7 @@
                              /* code_generator */ nullptr,
                              /* interpreter_metadata */ nullptr,
                              /* compiler_stats */ nullptr,
-                             null_dex_cache_,
+                             handles->NewHandle<mirror::DexCache>(nullptr),
                              handles) {}
 
   GraphAnalysisResult BuildGraph();
@@ -117,8 +122,6 @@
 
   CompilerDriver* const compiler_driver_;
 
-  ScopedNullHandle<mirror::DexCache> null_dex_cache_;
-
   OptimizingCompilerStats* compilation_stats_;
 
   HBasicBlockBuilder block_builder_;
diff --git a/compiler/optimizing/inliner.cc b/compiler/optimizing/inliner.cc
index 2e45149..664b95a 100644
--- a/compiler/optimizing/inliner.cc
+++ b/compiler/optimizing/inliner.cc
@@ -192,9 +192,9 @@
 }
 
 static dex::TypeIndex FindClassIndexIn(mirror::Class* cls,
-                                       const DexFile& dex_file,
-                                       Handle<mirror::DexCache> dex_cache)
+                                       const DexCompilationUnit& compilation_unit)
     REQUIRES_SHARED(Locks::mutator_lock_) {
+  const DexFile& dex_file = *compilation_unit.GetDexFile();
   dex::TypeIndex index;
   if (cls->GetDexCache() == nullptr) {
     DCHECK(cls->IsArrayClass()) << cls->PrettyClass();
@@ -203,22 +203,19 @@
     DCHECK(cls->IsProxyClass()) << cls->PrettyClass();
     // TODO: deal with proxy classes.
   } else if (IsSameDexFile(cls->GetDexFile(), dex_file)) {
-    DCHECK_EQ(cls->GetDexCache(), dex_cache.Get());
+    DCHECK_EQ(cls->GetDexCache(), compilation_unit.GetDexCache().Get());
     index = cls->GetDexTypeIndex();
-    // Update the dex cache to ensure the class is in. The generated code will
-    // consider it is. We make it safe by updating the dex cache, as other
-    // dex files might also load the class, and there is no guarantee the dex
-    // cache of the dex file of the class will be updated.
-    if (dex_cache->GetResolvedType(index) == nullptr) {
-      dex_cache->SetResolvedType(index, cls);
-    }
   } else {
     index = cls->FindTypeIndexInOtherDexFile(dex_file);
-    // We cannot guarantee the entry in the dex cache will resolve to the same class,
+    // We cannot guarantee the entry will resolve to the same class,
     // as there may be different class loaders. So only return the index if it's
-    // the right class in the dex cache already.
-    if (index.IsValid() && dex_cache->GetResolvedType(index) != cls) {
-      index = dex::TypeIndex::Invalid();
+    // the right class already resolved with the class loader.
+    if (index.IsValid()) {
+      ObjPtr<mirror::Class> resolved = ClassLinker::LookupResolvedType(
+          index, compilation_unit.GetDexCache().Get(), compilation_unit.GetClassLoader().Get());
+      if (resolved != cls) {
+        index = dex::TypeIndex::Invalid();
+      }
     }
   }
 
@@ -536,7 +533,10 @@
     ObjPtr<mirror::DexCache> dex_cache =
         dex_profile_index_to_dex_cache[class_ref.dex_profile_index];
     DCHECK(dex_cache != nullptr);
-    ObjPtr<mirror::Class> clazz = dex_cache->GetResolvedType(class_ref.type_index);
+    ObjPtr<mirror::Class> clazz = ClassLinker::LookupResolvedType(
+          class_ref.type_index,
+          dex_cache,
+          caller_compilation_unit_.GetClassLoader().Get());
     if (clazz != nullptr) {
       inline_cache->Set(ic_index++, clazz);
     } else {
@@ -577,9 +577,8 @@
   DCHECK(invoke_instruction->IsInvokeVirtual() || invoke_instruction->IsInvokeInterface())
       << invoke_instruction->DebugName();
 
-  const DexFile& caller_dex_file = *caller_compilation_unit_.GetDexFile();
   dex::TypeIndex class_index = FindClassIndexIn(
-      GetMonomorphicType(classes), caller_dex_file, caller_compilation_unit_.GetDexCache());
+      GetMonomorphicType(classes), caller_compilation_unit_);
   if (!class_index.IsValid()) {
     VLOG(compiler) << "Call to " << ArtMethod::PrettyMethod(resolved_method)
                    << " from inline cache is not inlined because its class is not"
@@ -622,6 +621,7 @@
   // Run type propagation to get the guard typed, and eventually propagate the
   // type of the receiver.
   ReferenceTypePropagation rtp_fixup(graph_,
+                                     outer_compilation_unit_.GetClassLoader(),
                                      outer_compilation_unit_.GetDexCache(),
                                      handles_,
                                      /* is_first_run */ false);
@@ -722,7 +722,6 @@
 
   ClassLinker* class_linker = caller_compilation_unit_.GetClassLinker();
   PointerSize pointer_size = class_linker->GetImagePointerSize();
-  const DexFile& caller_dex_file = *caller_compilation_unit_.GetDexFile();
 
   bool all_targets_inlined = true;
   bool one_target_inlined = false;
@@ -744,8 +743,7 @@
     HInstruction* cursor = invoke_instruction->GetPrevious();
     HBasicBlock* bb_cursor = invoke_instruction->GetBlock();
 
-    dex::TypeIndex class_index = FindClassIndexIn(
-        handle.Get(), caller_dex_file, caller_compilation_unit_.GetDexCache());
+    dex::TypeIndex class_index = FindClassIndexIn(handle.Get(), caller_compilation_unit_);
     HInstruction* return_replacement = nullptr;
     if (!class_index.IsValid() ||
         !TryBuildAndInline(invoke_instruction,
@@ -801,6 +799,7 @@
 
   // Run type propagation to get the guards typed.
   ReferenceTypePropagation rtp_fixup(graph_,
+                                     outer_compilation_unit_.GetClassLoader(),
                                      outer_compilation_unit_.GetDexCache(),
                                      handles_,
                                      /* is_first_run */ false);
@@ -997,6 +996,7 @@
 
   // Run type propagation to get the guard typed.
   ReferenceTypePropagation rtp_fixup(graph_,
+                                     outer_compilation_unit_.GetClassLoader(),
                                      outer_compilation_unit_.GetDexCache(),
                                      handles_,
                                      /* is_first_run */ false);
@@ -1065,6 +1065,7 @@
     // Actual return value has a more specific type than the method's declared
     // return type. Run RTP again on the outer graph to propagate it.
     ReferenceTypePropagation(graph_,
+                             outer_compilation_unit_.GetClassLoader(),
                              outer_compilation_unit_.GetDexCache(),
                              handles_,
                              /* is_first_run */ false).Run();
@@ -1317,7 +1318,11 @@
       /* dex_pc */ 0);
   if (iget->GetType() == Primitive::kPrimNot) {
     // Use the same dex_cache that we used for field lookup as the hint_dex_cache.
-    ReferenceTypePropagation rtp(graph_, dex_cache, handles_, /* is_first_run */ false);
+    ReferenceTypePropagation rtp(graph_,
+                                 outer_compilation_unit_.GetClassLoader(),
+                                 dex_cache,
+                                 handles_,
+                                 /* is_first_run */ false);
     rtp.Visit(iget);
   }
   return iget;
@@ -1363,7 +1368,7 @@
       resolved_method->GetDeclaringClass()->GetClassLoader()));
 
   DexCompilationUnit dex_compilation_unit(
-      class_loader.ToJObject(),
+      class_loader,
       class_linker,
       callee_dex_file,
       code_item,
@@ -1487,6 +1492,7 @@
   // are more specific than the declared ones, run RTP again on the inner graph.
   if (run_rtp || ArgumentTypesMoreSpecific(invoke_instruction, resolved_method)) {
     ReferenceTypePropagation(callee_graph,
+                             outer_compilation_unit_.GetClassLoader(),
                              dex_compilation_unit.GetDexCache(),
                              handles_,
                              /* is_first_run */ false).Run();
diff --git a/compiler/optimizing/instruction_builder.cc b/compiler/optimizing/instruction_builder.cc
index 1053da4..88f67fa 100644
--- a/compiler/optimizing/instruction_builder.cc
+++ b/compiler/optimizing/instruction_builder.cc
@@ -677,11 +677,10 @@
 
 ArtMethod* HInstructionBuilder::ResolveMethod(uint16_t method_idx, InvokeType invoke_type) {
   ScopedObjectAccess soa(Thread::Current());
-  StackHandleScope<3> hs(soa.Self());
+  StackHandleScope<2> hs(soa.Self());
 
   ClassLinker* class_linker = dex_compilation_unit_->GetClassLinker();
-  Handle<mirror::ClassLoader> class_loader(hs.NewHandle(
-      soa.Decode<mirror::ClassLoader>(dex_compilation_unit_->GetClassLoader())));
+  Handle<mirror::ClassLoader> class_loader = dex_compilation_unit_->GetClassLoader();
   Handle<mirror::Class> compiling_class(hs.NewHandle(GetCompilingClass()));
   // We fetch the referenced class eagerly (that is, the class pointed by in the MethodId
   // at method_idx), as `CanAccessResolvedMethod` expects it be be in the dex cache.
@@ -1268,9 +1267,7 @@
 static mirror::Class* GetClassFrom(CompilerDriver* driver,
                                    const DexCompilationUnit& compilation_unit) {
   ScopedObjectAccess soa(Thread::Current());
-  StackHandleScope<1> hs(soa.Self());
-  Handle<mirror::ClassLoader> class_loader(hs.NewHandle(
-      soa.Decode<mirror::ClassLoader>(compilation_unit.GetClassLoader())));
+  Handle<mirror::ClassLoader> class_loader = compilation_unit.GetClassLoader();
   Handle<mirror::DexCache> dex_cache = compilation_unit.GetDexCache();
 
   return driver->ResolveCompilingMethodsClass(soa, dex_cache, class_loader, &compilation_unit);
@@ -1286,10 +1283,9 @@
 
 bool HInstructionBuilder::IsOutermostCompilingClass(dex::TypeIndex type_index) const {
   ScopedObjectAccess soa(Thread::Current());
-  StackHandleScope<3> hs(soa.Self());
+  StackHandleScope<2> hs(soa.Self());
   Handle<mirror::DexCache> dex_cache = dex_compilation_unit_->GetDexCache();
-  Handle<mirror::ClassLoader> class_loader(hs.NewHandle(
-      soa.Decode<mirror::ClassLoader>(dex_compilation_unit_->GetClassLoader())));
+  Handle<mirror::ClassLoader> class_loader = dex_compilation_unit_->GetClassLoader();
   Handle<mirror::Class> cls(hs.NewHandle(compiler_driver_->ResolveClass(
       soa, dex_cache, class_loader, type_index, dex_compilation_unit_)));
   Handle<mirror::Class> outer_class(hs.NewHandle(GetOutermostCompilingClass()));
@@ -1325,8 +1321,7 @@
   StackHandleScope<2> hs(soa.Self());
 
   ClassLinker* class_linker = dex_compilation_unit_->GetClassLinker();
-  Handle<mirror::ClassLoader> class_loader(hs.NewHandle(
-      soa.Decode<mirror::ClassLoader>(dex_compilation_unit_->GetClassLoader())));
+  Handle<mirror::ClassLoader> class_loader = dex_compilation_unit_->GetClassLoader();
   Handle<mirror::Class> compiling_class(hs.NewHandle(GetCompilingClass()));
 
   ArtField* resolved_field = class_linker->ResolveField(*dex_compilation_unit_->GetDexFile(),
@@ -1643,10 +1638,8 @@
 
 HLoadClass* HInstructionBuilder::BuildLoadClass(dex::TypeIndex type_index, uint32_t dex_pc) {
   ScopedObjectAccess soa(Thread::Current());
-  StackHandleScope<2> hs(soa.Self());
   const DexFile& dex_file = *dex_compilation_unit_->GetDexFile();
-  Handle<mirror::ClassLoader> class_loader(hs.NewHandle(
-      soa.Decode<mirror::ClassLoader>(dex_compilation_unit_->GetClassLoader())));
+  Handle<mirror::ClassLoader> class_loader = dex_compilation_unit_->GetClassLoader();
   Handle<mirror::Class> klass = handles_->NewHandle(compiler_driver_->ResolveClass(
       soa, dex_compilation_unit_->GetDexCache(), class_loader, type_index, dex_compilation_unit_));
 
@@ -1730,17 +1723,9 @@
   }
 }
 
-bool HInstructionBuilder::NeedsAccessCheck(dex::TypeIndex type_index,
-                                           Handle<mirror::DexCache> dex_cache,
-                                           bool* finalizable) const {
-  return !compiler_driver_->CanAccessInstantiableTypeWithoutChecks(
-      dex_compilation_unit_->GetDexMethodIndex(), dex_cache, type_index, finalizable);
-}
-
 bool HInstructionBuilder::NeedsAccessCheck(dex::TypeIndex type_index, bool* finalizable) const {
-  ScopedObjectAccess soa(Thread::Current());
-  Handle<mirror::DexCache> dex_cache = dex_compilation_unit_->GetDexCache();
-  return NeedsAccessCheck(type_index, dex_cache, finalizable);
+  return !compiler_driver_->CanAccessInstantiableTypeWithoutChecks(
+      LookupReferrerClass(), LookupResolvedType(type_index, *dex_compilation_unit_), finalizable);
 }
 
 bool HInstructionBuilder::CanDecodeQuickenedInfo() const {
@@ -2780,4 +2765,18 @@
   return true;
 }  // NOLINT(readability/fn_size)
 
+ObjPtr<mirror::Class> HInstructionBuilder::LookupResolvedType(
+    dex::TypeIndex type_index,
+    const DexCompilationUnit& compilation_unit) const {
+  return ClassLinker::LookupResolvedType(
+        type_index, compilation_unit.GetDexCache().Get(), compilation_unit.GetClassLoader().Get());
+}
+
+ObjPtr<mirror::Class> HInstructionBuilder::LookupReferrerClass() const {
+  // TODO: Cache the result in a Handle<mirror::Class>.
+  const DexFile::MethodId& method_id =
+      dex_compilation_unit_->GetDexFile()->GetMethodId(dex_compilation_unit_->GetDexMethodIndex());
+  return LookupResolvedType(method_id.class_idx_, *dex_compilation_unit_);
+}
+
 }  // namespace art
diff --git a/compiler/optimizing/instruction_builder.h b/compiler/optimizing/instruction_builder.h
index 6cb6655..7fdc188 100644
--- a/compiler/optimizing/instruction_builder.h
+++ b/compiler/optimizing/instruction_builder.h
@@ -110,11 +110,8 @@
 
   // Returns whether the current method needs access check for the type.
   // Output parameter finalizable is set to whether the type is finalizable.
-  bool NeedsAccessCheck(dex::TypeIndex type_index,
-                        Handle<mirror::DexCache> dex_cache,
-                        /*out*/bool* finalizable) const
+  bool NeedsAccessCheck(dex::TypeIndex type_index, /*out*/bool* finalizable) const
       REQUIRES_SHARED(Locks::mutator_lock_);
-  bool NeedsAccessCheck(dex::TypeIndex type_index, /*out*/bool* finalizable) const;
 
   template<typename T>
   void Unop_12x(const Instruction& instruction, Primitive::Type type, uint32_t dex_pc);
@@ -304,6 +301,12 @@
   // be found.
   ArtField* ResolveField(uint16_t field_idx, bool is_static, bool is_put);
 
+  ObjPtr<mirror::Class> LookupResolvedType(dex::TypeIndex type_index,
+                                           const DexCompilationUnit& compilation_unit) const
+      REQUIRES_SHARED(Locks::mutator_lock_);
+
+  ObjPtr<mirror::Class> LookupReferrerClass() const REQUIRES_SHARED(Locks::mutator_lock_);
+
   ArenaAllocator* const arena_;
   HGraph* const graph_;
   VariableSizedHandleScope* handles_;
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 918a027..d6153b0 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -307,7 +307,7 @@
                           InvokeType invoke_type,
                           uint16_t class_def_idx,
                           uint32_t method_idx,
-                          jobject class_loader,
+                          Handle<mirror::ClassLoader> class_loader,
                           const DexFile& dex_file,
                           Handle<mirror::DexCache> dex_cache) const OVERRIDE;
 
@@ -376,7 +376,7 @@
                             InvokeType invoke_type,
                             uint16_t class_def_idx,
                             uint32_t method_idx,
-                            jobject class_loader,
+                            Handle<mirror::ClassLoader> class_loader,
                             const DexFile& dex_file,
                             Handle<mirror::DexCache> dex_cache,
                             ArtMethod* method,
@@ -884,7 +884,7 @@
                                               InvokeType invoke_type,
                                               uint16_t class_def_idx,
                                               uint32_t method_idx,
-                                              jobject class_loader,
+                                              Handle<mirror::ClassLoader> class_loader,
                                               const DexFile& dex_file,
                                               Handle<mirror::DexCache> dex_cache,
                                               ArtMethod* method,
@@ -955,11 +955,8 @@
   const uint8_t* interpreter_metadata = nullptr;
   if (method == nullptr) {
     ScopedObjectAccess soa(Thread::Current());
-    StackHandleScope<1> hs(soa.Self());
-    Handle<mirror::ClassLoader> loader(hs.NewHandle(
-        soa.Decode<mirror::ClassLoader>(class_loader)));
     method = compiler_driver->ResolveMethod(
-        soa, dex_cache, loader, &dex_compilation_unit, method_idx, invoke_type);
+        soa, dex_cache, class_loader, &dex_compilation_unit, method_idx, invoke_type);
   }
   // For AOT compilation, we may not get a method, for example if its class is erroneous.
   // JIT should always have a method.
@@ -968,16 +965,6 @@
     graph->SetArtMethod(method);
     ScopedObjectAccess soa(Thread::Current());
     interpreter_metadata = method->GetQuickenedInfo(class_linker->GetImagePointerSize());
-    dex::TypeIndex type_index = method->GetDeclaringClass()->GetDexTypeIndex();
-
-    // Update the dex cache if the type is not in it yet. Note that under AOT,
-    // the verifier must have set it, but under JIT, there's no guarantee, as we
-    // don't necessarily run the verifier.
-    // The compiler and the compiler driver assume the compiling class is
-    // in the dex cache.
-    if (dex_cache->GetResolvedType(type_index) == nullptr) {
-      dex_cache->SetResolvedType(type_index, method->GetDeclaringClass());
-    }
   }
 
   std::unique_ptr<CodeGenerator> codegen(
@@ -1058,7 +1045,7 @@
                                             InvokeType invoke_type,
                                             uint16_t class_def_idx,
                                             uint32_t method_idx,
-                                            jobject jclass_loader,
+                                            Handle<mirror::ClassLoader> jclass_loader,
                                             const DexFile& dex_file,
                                             Handle<mirror::DexCache> dex_cache) const {
   CompilerDriver* compiler_driver = GetCompilerDriver();
@@ -1172,7 +1159,6 @@
   Handle<mirror::DexCache> dex_cache(hs.NewHandle(method->GetDexCache()));
   DCHECK(method->IsCompilable());
 
-  jobject jclass_loader = class_loader.ToJObject();
   const DexFile* dex_file = method->GetDexFile();
   const uint16_t class_def_idx = method->GetClassDefIndex();
   const DexFile::CodeItem* code_item = dex_file->GetCodeItem(method->GetCodeItemOffset());
@@ -1196,7 +1182,7 @@
                    invoke_type,
                    class_def_idx,
                    method_idx,
-                   jclass_loader,
+                   class_loader,
                    *dex_file,
                    dex_cache,
                    method,
diff --git a/compiler/optimizing/reference_type_propagation.cc b/compiler/optimizing/reference_type_propagation.cc
index c55fccc..6e332ca 100644
--- a/compiler/optimizing/reference_type_propagation.cc
+++ b/compiler/optimizing/reference_type_propagation.cc
@@ -65,11 +65,13 @@
 class ReferenceTypePropagation::RTPVisitor : public HGraphDelegateVisitor {
  public:
   RTPVisitor(HGraph* graph,
+             Handle<mirror::ClassLoader> class_loader,
              Handle<mirror::DexCache> hint_dex_cache,
              HandleCache* handle_cache,
              ArenaVector<HInstruction*>* worklist,
              bool is_first_run)
     : HGraphDelegateVisitor(graph),
+      class_loader_(class_loader),
       hint_dex_cache_(hint_dex_cache),
       handle_cache_(handle_cache),
       worklist_(worklist),
@@ -101,6 +103,7 @@
                                bool is_exact);
 
  private:
+  Handle<mirror::ClassLoader> class_loader_;
   Handle<mirror::DexCache> hint_dex_cache_;
   HandleCache* handle_cache_;
   ArenaVector<HInstruction*>* worklist_;
@@ -108,11 +111,13 @@
 };
 
 ReferenceTypePropagation::ReferenceTypePropagation(HGraph* graph,
+                                                   Handle<mirror::ClassLoader> class_loader,
                                                    Handle<mirror::DexCache> hint_dex_cache,
                                                    VariableSizedHandleScope* handles,
                                                    bool is_first_run,
                                                    const char* name)
     : HOptimization(graph, name),
+      class_loader_(class_loader),
       hint_dex_cache_(hint_dex_cache),
       handle_cache_(handles),
       worklist_(graph->GetArena()->Adapter(kArenaAllocReferenceTypePropagation)),
@@ -147,7 +152,12 @@
 }
 
 void ReferenceTypePropagation::Visit(HInstruction* instruction) {
-  RTPVisitor visitor(graph_, hint_dex_cache_, &handle_cache_, &worklist_, is_first_run_);
+  RTPVisitor visitor(graph_,
+                     class_loader_,
+                     hint_dex_cache_,
+                     &handle_cache_,
+                     &worklist_,
+                     is_first_run_);
   instruction->Accept(&visitor);
 }
 
@@ -321,7 +331,12 @@
 }
 
 void ReferenceTypePropagation::VisitBasicBlock(HBasicBlock* block) {
-  RTPVisitor visitor(graph_, hint_dex_cache_, &handle_cache_, &worklist_, is_first_run_);
+  RTPVisitor visitor(graph_,
+                     class_loader_,
+                     hint_dex_cache_,
+                     &handle_cache_,
+                     &worklist_,
+                     is_first_run_);
   // Handle Phis first as there might be instructions in the same block who depend on them.
   for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
     VisitPhi(it.Current()->AsPhi());
@@ -542,8 +557,9 @@
 
   ScopedObjectAccess soa(Thread::Current());
   ObjPtr<mirror::DexCache> dex_cache = FindDexCacheWithHint(soa.Self(), dex_file, hint_dex_cache_);
-  // Get type from dex cache assuming it was populated by the verifier.
-  SetClassAsTypeInfo(instr, dex_cache->GetResolvedType(type_idx), is_exact);
+  ObjPtr<mirror::Class> klass =
+      ClassLinker::LookupResolvedType(type_idx, dex_cache, class_loader_.Get());
+  SetClassAsTypeInfo(instr, klass, is_exact);
 }
 
 void ReferenceTypePropagation::RTPVisitor::VisitNewInstance(HNewInstance* instr) {
@@ -556,25 +572,13 @@
   SetClassAsTypeInfo(instr, instr->GetLoadClass()->GetClass().Get(), /* is_exact */ true);
 }
 
-static mirror::Class* GetClassFromDexCache(Thread* self,
-                                           const DexFile& dex_file,
-                                           dex::TypeIndex type_idx,
-                                           Handle<mirror::DexCache> hint_dex_cache)
-    REQUIRES_SHARED(Locks::mutator_lock_) {
-  ObjPtr<mirror::DexCache> dex_cache = FindDexCacheWithHint(self, dex_file, hint_dex_cache);
-  // Get type from dex cache assuming it was populated by the verifier.
-  return dex_cache->GetResolvedType(type_idx);
-}
-
 void ReferenceTypePropagation::RTPVisitor::VisitParameterValue(HParameterValue* instr) {
   // We check if the existing type is valid: the inliner may have set it.
   if (instr->GetType() == Primitive::kPrimNot && !instr->GetReferenceTypeInfo().IsValid()) {
-    ScopedObjectAccess soa(Thread::Current());
-    mirror::Class* resolved_class = GetClassFromDexCache(soa.Self(),
-                                                         instr->GetDexFile(),
-                                                         instr->GetTypeIndex(),
-                                                         hint_dex_cache_);
-    SetClassAsTypeInfo(instr, resolved_class, /* is_exact */ false);
+    UpdateReferenceTypeInfo(instr,
+                            instr->GetTypeIndex(),
+                            instr->GetDexFile(),
+                            /* is_exact */ false);
   }
 }
 
diff --git a/compiler/optimizing/reference_type_propagation.h b/compiler/optimizing/reference_type_propagation.h
index 4663471..215e967 100644
--- a/compiler/optimizing/reference_type_propagation.h
+++ b/compiler/optimizing/reference_type_propagation.h
@@ -33,6 +33,7 @@
 class ReferenceTypePropagation : public HOptimization {
  public:
   ReferenceTypePropagation(HGraph* graph,
+                           Handle<mirror::ClassLoader> class_loader,
                            Handle<mirror::DexCache> hint_dex_cache,
                            VariableSizedHandleScope* handles,
                            bool is_first_run,
@@ -105,6 +106,8 @@
 
   void ValidateTypes();
 
+  Handle<mirror::ClassLoader> class_loader_;
+
   // Note: hint_dex_cache_ is usually, but not necessarily, the dex cache associated with
   // graph_->GetDexFile(). Since we may look up also in other dex files, it's used only
   // as a hint, to reduce the number of calls to the costly ClassLinker::FindDexCache().
diff --git a/compiler/optimizing/reference_type_propagation_test.cc b/compiler/optimizing/reference_type_propagation_test.cc
index b061c87..84a4bab 100644
--- a/compiler/optimizing/reference_type_propagation_test.cc
+++ b/compiler/optimizing/reference_type_propagation_test.cc
@@ -38,6 +38,7 @@
   void SetupPropagation(VariableSizedHandleScope* handles) {
     graph_->InitializeInexactObjectRTI(handles);
     propagation_ = new (&allocator_) ReferenceTypePropagation(graph_,
+                                                              Handle<mirror::ClassLoader>(),
                                                               Handle<mirror::DexCache>(),
                                                               handles,
                                                               true,
diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index 487e4dd..50ab11b 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -499,7 +499,11 @@
 
   // 4) Compute type of reference type instructions. The pass assumes that
   // NullConstant has been fixed up.
-  ReferenceTypePropagation(graph_, dex_cache_, handles_, /* is_first_run */ true).Run();
+  ReferenceTypePropagation(graph_,
+                           class_loader_,
+                           dex_cache_,
+                           handles_,
+                           /* is_first_run */ true).Run();
 
   // 5) HInstructionBuilder duplicated ArrayGet instructions with ambiguous type
   // (int/float or long/double) and marked ArraySets with ambiguous input type.
diff --git a/compiler/optimizing/ssa_builder.h b/compiler/optimizing/ssa_builder.h
index 45dac54..978f113 100644
--- a/compiler/optimizing/ssa_builder.h
+++ b/compiler/optimizing/ssa_builder.h
@@ -48,9 +48,11 @@
 class SsaBuilder : public ValueObject {
  public:
   SsaBuilder(HGraph* graph,
+             Handle<mirror::ClassLoader> class_loader,
              Handle<mirror::DexCache> dex_cache,
              VariableSizedHandleScope* handles)
       : graph_(graph),
+        class_loader_(class_loader),
         dex_cache_(dex_cache),
         handles_(handles),
         agets_fixed_(false),
@@ -115,6 +117,7 @@
   void RemoveRedundantUninitializedStrings();
 
   HGraph* graph_;
+  Handle<mirror::ClassLoader> class_loader_;
   Handle<mirror::DexCache> dex_cache_;
   VariableSizedHandleScope* const handles_;
 
diff --git a/oatdump/oatdump.cc b/oatdump/oatdump.cc
index a0919a1..becb827 100644
--- a/oatdump/oatdump.cc
+++ b/oatdump/oatdump.cc
@@ -2244,9 +2244,14 @@
           ScopedIndentation indent2(&state->vios_);
           auto* resolved_types = dex_cache->GetResolvedTypes();
           for (size_t i = 0; i < num_types; ++i) {
-            auto* elem = resolved_types[i].Read();
+            auto pair = resolved_types[i].load(std::memory_order_relaxed);
             size_t run = 0;
-            for (size_t j = i + 1; j != num_types && elem == resolved_types[j].Read(); ++j) {
+            for (size_t j = i + 1; j != num_types; ++j) {
+              auto other_pair = resolved_types[j].load(std::memory_order_relaxed);
+              if (pair.index != other_pair.index ||
+                  pair.object.Read() != other_pair.object.Read()) {
+                break;
+              }
               ++run;
             }
             if (run == 0) {
@@ -2256,12 +2261,13 @@
               i = i + run;
             }
             std::string msg;
+            auto* elem = pair.object.Read();
             if (elem == nullptr) {
               msg = "null";
             } else {
               msg = elem->PrettyClass();
             }
-            os << StringPrintf("%p   %s\n", elem, msg.c_str());
+            os << StringPrintf("%p   %u %s\n", elem, pair.index, msg.c_str());
           }
         }
       }
diff --git a/patchoat/patchoat.cc b/patchoat/patchoat.cc
index 4426a30..18a6670 100644
--- a/patchoat/patchoat.cc
+++ b/patchoat/patchoat.cc
@@ -512,8 +512,8 @@
     if (orig_strings != nullptr) {
       orig_dex_cache->FixupStrings(RelocatedCopyOf(orig_strings), RelocatedPointerVisitor(this));
     }
-    GcRoot<mirror::Class>* orig_types = orig_dex_cache->GetResolvedTypes();
-    GcRoot<mirror::Class>* relocated_types = RelocatedAddressOfPointer(orig_types);
+    mirror::TypeDexCacheType* orig_types = orig_dex_cache->GetResolvedTypes();
+    mirror::TypeDexCacheType* relocated_types = RelocatedAddressOfPointer(orig_types);
     copy_dex_cache->SetField64<false>(
         mirror::DexCache::ResolvedTypesOffset(),
         static_cast<int64_t>(reinterpret_cast<uintptr_t>(relocated_types)));
diff --git a/runtime/art_field-inl.h b/runtime/art_field-inl.h
index 80af8e7..16b73c6 100644
--- a/runtime/art_field-inl.h
+++ b/runtime/art_field-inl.h
@@ -311,6 +311,8 @@
 
 template <bool kResolve>
 inline ObjPtr<mirror::Class> ArtField::GetType() {
+  // TODO: Refactor this function into two functions, ResolveType() and LookupType()
+  // so that we can properly annotate it with no-suspension possible / suspension possible.
   const uint32_t field_index = GetDexFieldIndex();
   ObjPtr<mirror::Class> declaring_class = GetDeclaringClass();
   if (UNLIKELY(declaring_class->IsProxyClass())) {
@@ -320,9 +322,16 @@
   const DexFile* const dex_file = dex_cache->GetDexFile();
   const DexFile::FieldId& field_id = dex_file->GetFieldId(field_index);
   ObjPtr<mirror::Class> type = dex_cache->GetResolvedType(field_id.type_idx_);
-  if (kResolve && UNLIKELY(type == nullptr)) {
-    type = ResolveGetType(field_id.type_idx_);
-    CHECK(type != nullptr || Thread::Current()->IsExceptionPending());
+  if (UNLIKELY(type == nullptr)) {
+    ClassLinker* class_linker = Runtime::Current()->GetClassLinker();
+    if (kResolve) {
+      type = class_linker->ResolveType(*dex_file, field_id.type_idx_, declaring_class);
+      CHECK(type != nullptr || Thread::Current()->IsExceptionPending());
+    } else {
+      type = class_linker->LookupResolvedType(
+          *dex_file, field_id.type_idx_, dex_cache, declaring_class->GetClassLoader());
+      DCHECK(!Thread::Current()->IsExceptionPending());
+    }
   }
   return type;
 }
diff --git a/runtime/art_field.cc b/runtime/art_field.cc
index a4a6e5a..7e13104 100644
--- a/runtime/art_field.cc
+++ b/runtime/art_field.cc
@@ -48,10 +48,6 @@
   return Runtime::Current()->GetClassLinker()->FindSystemClass(Thread::Current(), descriptor);
 }
 
-ObjPtr<mirror::Class> ArtField::ResolveGetType(dex::TypeIndex type_idx) {
-  return Runtime::Current()->GetClassLinker()->ResolveType(type_idx, this);
-}
-
 ObjPtr<mirror::String> ArtField::ResolveGetStringName(Thread* self,
                                                       const DexFile& dex_file,
                                                       dex::StringIndex string_idx,
diff --git a/runtime/art_field.h b/runtime/art_field.h
index 427e103..75dd981 100644
--- a/runtime/art_field.h
+++ b/runtime/art_field.h
@@ -217,8 +217,6 @@
  private:
   ObjPtr<mirror::Class> ProxyFindSystemClass(const char* descriptor)
       REQUIRES_SHARED(Locks::mutator_lock_);
-  ObjPtr<mirror::Class> ResolveGetType(dex::TypeIndex type_idx)
-      REQUIRES_SHARED(Locks::mutator_lock_);
   ObjPtr<mirror::String> ResolveGetStringName(Thread* self,
                                               const DexFile& dex_file,
                                               dex::StringIndex string_idx,
diff --git a/runtime/art_method-inl.h b/runtime/art_method-inl.h
index f54b5d6..685e26c 100644
--- a/runtime/art_method-inl.h
+++ b/runtime/art_method-inl.h
@@ -179,12 +179,19 @@
 }
 
 inline mirror::Class* ArtMethod::GetClassFromTypeIndex(dex::TypeIndex type_idx, bool resolve) {
+  // TODO: Refactor this function into two functions, Resolve...() and Lookup...()
+  // so that we can properly annotate it with no-suspension possible / suspension possible.
   ObjPtr<mirror::DexCache> dex_cache = GetDexCache();
   ObjPtr<mirror::Class> type = dex_cache->GetResolvedType(type_idx);
-  if (UNLIKELY(type == nullptr) && resolve) {
+  if (UNLIKELY(type == nullptr)) {
     ClassLinker* class_linker = Runtime::Current()->GetClassLinker();
-    type = class_linker->ResolveType(type_idx, this);
-    CHECK(type != nullptr || Thread::Current()->IsExceptionPending());
+    if (resolve) {
+      type = class_linker->ResolveType(type_idx, this);
+      CHECK(type != nullptr || Thread::Current()->IsExceptionPending());
+    } else {
+      type = class_linker->LookupResolvedType(
+          *dex_cache->GetDexFile(), type_idx, dex_cache, GetClassLoader());
+    }
   }
   return type.Ptr();
 }
diff --git a/runtime/class_linker-inl.h b/runtime/class_linker-inl.h
index 3438810..bd510ca 100644
--- a/runtime/class_linker-inl.h
+++ b/runtime/class_linker-inl.h
@@ -78,6 +78,18 @@
   return string.Ptr();
 }
 
+inline ObjPtr<mirror::Class> ClassLinker::LookupResolvedType(
+    dex::TypeIndex type_idx,
+    ObjPtr<mirror::DexCache> dex_cache,
+    ObjPtr<mirror::ClassLoader> class_loader) {
+  ObjPtr<mirror::Class> type = dex_cache->GetResolvedType(type_idx);
+  if (type == nullptr) {
+    type = Runtime::Current()->GetClassLinker()->LookupResolvedType(
+        *dex_cache->GetDexFile(), type_idx, dex_cache, class_loader);
+  }
+  return type;
+}
+
 inline mirror::Class* ClassLinker::ResolveType(dex::TypeIndex type_idx, ArtMethod* referrer) {
   Thread::PoisonObjectPointersIfDebug();
   if (kIsDebugBuild) {
@@ -91,25 +103,6 @@
     Handle<mirror::ClassLoader> class_loader(hs.NewHandle(declaring_class->GetClassLoader()));
     const DexFile& dex_file = *dex_cache->GetDexFile();
     resolved_type = ResolveType(dex_file, type_idx, dex_cache, class_loader);
-    // Note: We cannot check here to see whether we added the type to the cache. The type
-    //       might be an erroneous class, which results in it being hidden from us.
-  }
-  return resolved_type.Ptr();
-}
-
-inline mirror::Class* ClassLinker::ResolveType(dex::TypeIndex type_idx, ArtField* referrer) {
-  Thread::PoisonObjectPointersIfDebug();
-  ObjPtr<mirror::Class> declaring_class = referrer->GetDeclaringClass();
-  ObjPtr<mirror::DexCache> dex_cache_ptr = declaring_class->GetDexCache();
-  ObjPtr<mirror::Class> resolved_type = dex_cache_ptr->GetResolvedType(type_idx);
-  if (UNLIKELY(resolved_type == nullptr)) {
-    StackHandleScope<2> hs(Thread::Current());
-    Handle<mirror::DexCache> dex_cache(hs.NewHandle(dex_cache_ptr));
-    Handle<mirror::ClassLoader> class_loader(hs.NewHandle(declaring_class->GetClassLoader()));
-    const DexFile& dex_file = *dex_cache->GetDexFile();
-    resolved_type = ResolveType(dex_file, type_idx, dex_cache, class_loader);
-    // Note: We cannot check here to see whether we added the type to the cache. The type
-    //       might be an erroneous class, which results in it being hidden from us.
   }
   return resolved_type.Ptr();
 }
diff --git a/runtime/class_linker.cc b/runtime/class_linker.cc
index bbf06e1..5b7d566 100644
--- a/runtime/class_linker.cc
+++ b/runtime/class_linker.cc
@@ -58,6 +58,7 @@
 #include "gc/heap.h"
 #include "gc/scoped_gc_critical_section.h"
 #include "gc/space/image_space.h"
+#include "gc/space/space-inl.h"
 #include "handle_scope-inl.h"
 #include "image-inl.h"
 #include "imt_conflict_table.h"
@@ -1146,6 +1147,33 @@
   ClassTable* const table_;
 };
 
+class VerifyDirectInterfacesInTableClassVisitor {
+ public:
+  explicit VerifyDirectInterfacesInTableClassVisitor(ObjPtr<mirror::ClassLoader> class_loader)
+      : class_loader_(class_loader), self_(Thread::Current()) { }
+
+  bool operator()(ObjPtr<mirror::Class> klass) REQUIRES_SHARED(Locks::mutator_lock_) {
+    if (!klass->IsPrimitive() && klass->GetClassLoader() == class_loader_) {
+      classes_.push_back(klass);
+    }
+    return true;
+  }
+
+  void Check() const REQUIRES_SHARED(Locks::mutator_lock_) {
+    for (ObjPtr<mirror::Class> klass : classes_) {
+      for (uint32_t i = 0, num = klass->NumDirectInterfaces(); i != num; ++i) {
+        CHECK(klass->GetDirectInterface(self_, klass, i) != nullptr)
+            << klass->PrettyDescriptor() << " iface #" << i;
+      }
+    }
+  }
+
+ private:
+  ObjPtr<mirror::ClassLoader> class_loader_;
+  Thread* self_;
+  std::vector<ObjPtr<mirror::Class>> classes_;
+};
+
 class VerifyDeclaringClassVisitor : public ArtMethodVisitor {
  public:
   VerifyDeclaringClassVisitor() REQUIRES_SHARED(Locks::mutator_lock_, Locks::heap_bitmap_lock_)
@@ -1177,6 +1205,23 @@
   }
 }
 
+template <typename T>
+static void CopyDexCachePairs(const std::atomic<mirror::DexCachePair<T>>* src,
+                              size_t count,
+                              std::atomic<mirror::DexCachePair<T>>* dst) {
+  DCHECK_NE(count, 0u);
+  DCHECK(!src[0].load(std::memory_order_relaxed).object.IsNull() ||
+         src[0].load(std::memory_order_relaxed).index != 0u);
+  for (size_t i = 0; i < count; ++i) {
+    DCHECK_EQ(dst[i].load(std::memory_order_relaxed).index, 0u);
+    DCHECK(dst[i].load(std::memory_order_relaxed).object.IsNull());
+    mirror::DexCachePair<T> source = src[i].load(std::memory_order_relaxed);
+    if (source.index != 0u || !source.object.IsNull()) {
+      dst[i].store(source, std::memory_order_relaxed);
+    }
+  }
+}
+
 bool ClassLinker::UpdateAppImageClassLoadersAndDexCaches(
     gc::space::ImageSpace* space,
     Handle<mirror::ClassLoader> class_loader,
@@ -1230,7 +1275,10 @@
         if (dex_file->NumStringIds() < num_strings) {
           num_strings = dex_file->NumStringIds();
         }
-        const size_t num_types = dex_file->NumTypeIds();
+        size_t num_types = mirror::DexCache::kDexCacheTypeCacheSize;
+        if (dex_file->NumTypeIds() < num_types) {
+          num_types = dex_file->NumTypeIds();
+        }
         const size_t num_methods = dex_file->NumMethodIds();
         const size_t num_fields = dex_file->NumFieldIds();
         size_t num_method_types = mirror::DexCache::kDexCacheMethodTypeCacheSize;
@@ -1250,28 +1298,14 @@
           mirror::StringDexCacheType* const image_resolved_strings = dex_cache->GetStrings();
           mirror::StringDexCacheType* const strings =
               reinterpret_cast<mirror::StringDexCacheType*>(raw_arrays + layout.StringsOffset());
-          for (size_t j = 0; j < num_strings; ++j) {
-            DCHECK_EQ(strings[j].load(std::memory_order_relaxed).index, 0u);
-            DCHECK(strings[j].load(std::memory_order_relaxed).object.IsNull());
-            strings[j].store(image_resolved_strings[j].load(std::memory_order_relaxed),
-                             std::memory_order_relaxed);
-          }
-          mirror::StringDexCachePair::Initialize(strings);
+          CopyDexCachePairs(image_resolved_strings, num_strings, strings);
           dex_cache->SetStrings(strings);
         }
         if (num_types != 0u) {
-          GcRoot<mirror::Class>* const image_resolved_types = dex_cache->GetResolvedTypes();
-          GcRoot<mirror::Class>* const types =
-              reinterpret_cast<GcRoot<mirror::Class>*>(raw_arrays + layout.TypesOffset());
-          for (size_t j = 0; kIsDebugBuild && j < num_types; ++j) {
-            DCHECK(types[j].IsNull());
-          }
-          CopyNonNull(image_resolved_types,
-                      num_types,
-                      types,
-                      [](const GcRoot<mirror::Class>& elem) {
-                          return elem.IsNull();
-                      });
+          mirror::TypeDexCacheType* const image_resolved_types = dex_cache->GetResolvedTypes();
+          mirror::TypeDexCacheType* const types =
+              reinterpret_cast<mirror::TypeDexCacheType*>(raw_arrays + layout.TypesOffset());
+          CopyDexCachePairs(image_resolved_types, num_types, types);
           dex_cache->SetResolvedTypes(types);
         }
         if (num_methods != 0u) {
@@ -1312,15 +1346,7 @@
           mirror::MethodTypeDexCacheType* const method_types =
               reinterpret_cast<mirror::MethodTypeDexCacheType*>(
                   raw_arrays + layout.MethodTypesOffset());
-          for (size_t j = 0; j < num_method_types; ++j) {
-            DCHECK_EQ(method_types[j].load(std::memory_order_relaxed).index, 0u);
-            DCHECK(method_types[j].load(std::memory_order_relaxed).object.IsNull());
-            method_types[j].store(
-                image_resolved_method_types[j].load(std::memory_order_relaxed),
-                std::memory_order_relaxed);
-          }
-
-          mirror::MethodTypeDexCachePair::Initialize(method_types);
+          CopyDexCachePairs(image_resolved_method_types, num_method_types, method_types);
           dex_cache->SetResolvedMethodTypes(method_types);
         }
         if (num_call_sites != 0u) {
@@ -1350,11 +1376,11 @@
       }
       if (kIsDebugBuild) {
         CHECK(new_class_set != nullptr);
-        GcRoot<mirror::Class>* const types = dex_cache->GetResolvedTypes();
+        mirror::TypeDexCacheType* const types = dex_cache->GetResolvedTypes();
         const size_t num_types = dex_cache->NumResolvedTypes();
-        for (int32_t j = 0; j < static_cast<int32_t>(num_types); j++) {
+        for (size_t j = 0; j != num_types; ++j) {
           // The image space is not yet added to the heap, avoid read barriers.
-          ObjPtr<mirror::Class> klass = types[j].Read();
+          ObjPtr<mirror::Class> klass = types[j].load(std::memory_order_relaxed).object.Read();
           if (space->HasAddress(klass.Ptr())) {
             DCHECK(!klass->IsErroneous()) << klass->GetStatus();
             auto it = new_class_set->Find(ClassTable::TableSlot(klass));
@@ -1713,9 +1739,9 @@
       // The current dex file field is bogus, overwrite it so that we can get the dex file in the
       // loop below.
       dex_cache->SetDexFile(dex_file.get());
-      GcRoot<mirror::Class>* const types = dex_cache->GetResolvedTypes();
+      mirror::TypeDexCacheType* const types = dex_cache->GetResolvedTypes();
       for (int32_t j = 0, num_types = dex_cache->NumResolvedTypes(); j < num_types; j++) {
-        ObjPtr<mirror::Class> klass = types[j].Read();
+        ObjPtr<mirror::Class> klass = types[j].load(std::memory_order_relaxed).object.Read();
         if (klass != nullptr) {
           DCHECK(!klass->IsErroneous()) << klass->GetStatus();
         }
@@ -1885,6 +1911,22 @@
     // Since it ensures classes are in the class table.
     VerifyClassInTableArtMethodVisitor visitor2(class_table);
     header.VisitPackedArtMethods(&visitor2, space->Begin(), kRuntimePointerSize);
+    // Verify that all direct interfaces of classes in the class table are also resolved.
+    VerifyDirectInterfacesInTableClassVisitor visitor(class_loader.Get());
+    class_table->Visit(visitor);
+    visitor.Check();
+    // Check that all non-primitive classes in dex caches are also in the class table.
+    for (int32_t i = 0; i < dex_caches->GetLength(); i++) {
+      ObjPtr<mirror::DexCache> dex_cache = dex_caches->Get(i);
+      mirror::TypeDexCacheType* const types = dex_cache->GetResolvedTypes();
+      for (int32_t j = 0, num_types = dex_cache->NumResolvedTypes(); j < num_types; j++) {
+        ObjPtr<mirror::Class> klass = types[j].load(std::memory_order_relaxed).object.Read();
+        if (klass != nullptr && !klass->IsPrimitive()) {
+          CHECK(class_table->Contains(klass)) << klass->PrettyDescriptor()
+              << " " << dex_cache->GetDexFile()->GetLocation();
+        }
+      }
+    }
   }
   VLOG(class_linker) << "Adding image space took " << PrettyDuration(NanoTime() - start_time);
   return true;
@@ -4651,7 +4693,7 @@
       MutableHandle<mirror::Class> handle_scope_iface(hs_iface.NewHandle<mirror::Class>(nullptr));
       for (size_t i = 0; i < num_direct_interfaces; i++) {
         handle_scope_iface.Assign(mirror::Class::GetDirectInterface(self, klass.Get(), i));
-        CHECK(handle_scope_iface != nullptr);
+        CHECK(handle_scope_iface != nullptr) << klass->PrettyDescriptor() << " iface #" << i;
         CHECK(handle_scope_iface->IsInterface());
         if (handle_scope_iface->HasBeenRecursivelyInitialized()) {
           // We have already done this for this interface. Skip it.
@@ -4787,7 +4829,7 @@
     // First we initialize all of iface's super-interfaces recursively.
     for (size_t i = 0; i < num_direct_ifaces; i++) {
       ObjPtr<mirror::Class> super_iface = mirror::Class::GetDirectInterface(self, iface.Get(), i);
-      DCHECK(super_iface != nullptr);
+      CHECK(super_iface != nullptr) << iface->PrettyDescriptor() << " iface #" << i;
       if (!super_iface->HasBeenRecursivelyInitialized()) {
         // Recursive step
         handle_super_iface.Assign(super_iface);
@@ -7762,7 +7804,9 @@
   uint32_t utf16_length;
   const char* utf8_data = dex_file.StringDataAndUtf16LengthByIdx(string_idx, &utf16_length);
   ObjPtr<mirror::String> string = intern_table_->InternStrong(utf16_length, utf8_data);
-  dex_cache->SetResolvedString(string_idx, string);
+  if (string != nullptr) {
+    dex_cache->SetResolvedString(string_idx, string);
+  }
   return string.Ptr();
 }
 
@@ -7803,11 +7847,16 @@
       // Find the class in the loaded classes table.
       type = LookupClass(self, descriptor, hash, class_loader.Ptr());
     }
+    if (type != nullptr) {
+      if (type->IsResolved()) {
+        dex_cache->SetResolvedType(type_idx, type);
+      } else {
+        type = nullptr;
+      }
+    }
   }
-  if (type != nullptr && type->IsResolved()) {
-    return type.Ptr();
-  }
-  return nullptr;
+  DCHECK(type == nullptr || type->IsResolved());
+  return type;
 }
 
 mirror::Class* ClassLinker::ResolveType(const DexFile& dex_file,
@@ -7827,6 +7876,12 @@
   Thread::PoisonObjectPointersIfDebug();
   ObjPtr<mirror::Class> resolved = dex_cache->GetResolvedType(type_idx);
   if (resolved == nullptr) {
+    // TODO: Avoid this lookup as it duplicates work done in FindClass(). It is here
+    // as a workaround for FastNative JNI to avoid AssertNoPendingException() when
+    // trying to resolve annotations while an exception may be pending. Bug: 34659969
+    resolved = LookupResolvedType(dex_file, type_idx, dex_cache.Get(), class_loader.Get());
+  }
+  if (resolved == nullptr) {
     Thread* self = Thread::Current();
     const char* descriptor = dex_file.StringByTypeIdx(type_idx);
     resolved = FindClass(self, descriptor, class_loader);
diff --git a/runtime/class_linker.h b/runtime/class_linker.h
index f07156f..a5d26c7 100644
--- a/runtime/class_linker.h
+++ b/runtime/class_linker.h
@@ -266,10 +266,6 @@
       REQUIRES_SHARED(Locks::mutator_lock_)
       REQUIRES(!Locks::dex_lock_, !Roles::uninterruptible_);
 
-  mirror::Class* ResolveType(dex::TypeIndex type_idx, ArtField* referrer)
-      REQUIRES_SHARED(Locks::mutator_lock_)
-      REQUIRES(!Locks::dex_lock_, !Roles::uninterruptible_);
-
   // Look up a resolved type with the given ID from the DexFile. The ClassLoader is used to search
   // for the type, since it may be referenced from but not contained within the given DexFile.
   ObjPtr<mirror::Class> LookupResolvedType(const DexFile& dex_file,
@@ -277,6 +273,10 @@
                                            ObjPtr<mirror::DexCache> dex_cache,
                                            ObjPtr<mirror::ClassLoader> class_loader)
       REQUIRES_SHARED(Locks::mutator_lock_);
+  static ObjPtr<mirror::Class> LookupResolvedType(dex::TypeIndex type_idx,
+                                                  ObjPtr<mirror::DexCache> dex_cache,
+                                                  ObjPtr<mirror::ClassLoader> class_loader)
+      REQUIRES_SHARED(Locks::mutator_lock_);
 
   // Resolve a type with the given ID from the DexFile, storing the
   // result in DexCache. The ClassLoader is used to search for the
diff --git a/runtime/class_linker_test.cc b/runtime/class_linker_test.cc
index 37e01ef..e5722a1 100644
--- a/runtime/class_linker_test.cc
+++ b/runtime/class_linker_test.cc
@@ -935,7 +935,7 @@
       class_linker_->LookupResolvedType(dex_file, type_idx, dex_cache, class_loader.Get()),
       klass);
   // Zero out the resolved type and make sure LookupResolvedType still finds it.
-  dex_cache->SetResolvedType(type_idx, nullptr);
+  dex_cache->ClearResolvedType(type_idx);
   EXPECT_TRUE(dex_cache->GetResolvedType(type_idx) == nullptr);
   EXPECT_OBJ_PTR_EQ(
       class_linker_->LookupResolvedType(dex_file, type_idx, dex_cache, class_loader.Get()),
@@ -970,7 +970,7 @@
       class_linker_->LookupResolvedType(dex_file, array_idx, dex_cache.Get(), class_loader.Get()),
       array_klass);
   // Zero out the resolved type and make sure LookupResolvedType() still finds it.
-  dex_cache->SetResolvedType(array_idx, nullptr);
+  dex_cache->ClearResolvedType(array_idx);
   EXPECT_TRUE(dex_cache->GetResolvedType(array_idx) == nullptr);
   EXPECT_OBJ_PTR_EQ(
       class_linker_->LookupResolvedType(dex_file, array_idx, dex_cache.Get(), class_loader.Get()),
@@ -993,7 +993,7 @@
       class_linker_->LookupResolvedType(dex_file, type_idx, dex_cache.Get(), class_loader.Get()),
       klass.Get());
   // Zero out the resolved type and make sure LookupResolvedType still finds it.
-  dex_cache->SetResolvedType(type_idx, nullptr);
+  dex_cache->ClearResolvedType(type_idx);
   EXPECT_TRUE(dex_cache->GetResolvedType(type_idx) == nullptr);
   EXPECT_OBJ_PTR_EQ(
       class_linker_->LookupResolvedType(dex_file, type_idx, dex_cache.Get(), class_loader.Get()),
@@ -1011,7 +1011,7 @@
       class_linker_->LookupResolvedType(dex_file, type_idx, dex_cache.Get(), class_loader.Get()),
       klass.Get());
   // Zero out the resolved type and make sure LookupResolvedType() still finds it.
-  dex_cache->SetResolvedType(type_idx, nullptr);
+  dex_cache->ClearResolvedType(type_idx);
   EXPECT_TRUE(dex_cache->GetResolvedType(type_idx) == nullptr);
   EXPECT_OBJ_PTR_EQ(
       class_linker_->LookupResolvedType(dex_file, type_idx, dex_cache.Get(), class_loader.Get()),
diff --git a/runtime/class_table.cc b/runtime/class_table.cc
index 7c3ad12..374b711 100644
--- a/runtime/class_table.cc
+++ b/runtime/class_table.cc
@@ -113,6 +113,20 @@
   return CountDefiningLoaderClasses(defining_loader, classes_.back());
 }
 
+size_t ClassTable::NumReferencedZygoteClasses() const {
+  ReaderMutexLock mu(Thread::Current(), lock_);
+  size_t sum = 0;
+  for (size_t i = 0; i < classes_.size() - 1; ++i) {
+    sum += classes_[i].Size();
+  }
+  return sum;
+}
+
+size_t ClassTable::NumReferencedNonZygoteClasses() const {
+  ReaderMutexLock mu(Thread::Current(), lock_);
+  return classes_.back().Size();
+}
+
 mirror::Class* ClassTable::Lookup(const char* descriptor, size_t hash) {
   DescriptorHashPair pair(descriptor, hash);
   ReaderMutexLock mu(Thread::Current(), lock_);
diff --git a/runtime/class_table.h b/runtime/class_table.h
index 711eae4..79f5aea 100644
--- a/runtime/class_table.h
+++ b/runtime/class_table.h
@@ -144,16 +144,26 @@
       REQUIRES(!lock_)
       REQUIRES_SHARED(Locks::mutator_lock_);
 
-  // Returns the number of classes in previous snapshots.
+  // Returns the number of classes in previous snapshots defined by `defining_loader`.
   size_t NumZygoteClasses(ObjPtr<mirror::ClassLoader> defining_loader) const
       REQUIRES(!lock_)
       REQUIRES_SHARED(Locks::mutator_lock_);
 
-  // Returns all off the classes in the lastest snapshot.
+  // Returns all off the classes in the lastest snapshot defined by `defining_loader`.
   size_t NumNonZygoteClasses(ObjPtr<mirror::ClassLoader> defining_loader) const
       REQUIRES(!lock_)
       REQUIRES_SHARED(Locks::mutator_lock_);
 
+  // Returns the number of classes in previous snapshots no matter the defining loader.
+  size_t NumReferencedZygoteClasses() const
+      REQUIRES(!lock_)
+      REQUIRES_SHARED(Locks::mutator_lock_);
+
+  // Returns all off the classes in the lastest snapshot no matter the defining loader.
+  size_t NumReferencedNonZygoteClasses() const
+      REQUIRES(!lock_)
+      REQUIRES_SHARED(Locks::mutator_lock_);
+
   // Update a class in the table with the new class. Returns the existing class which was replaced.
   mirror::Class* UpdateClass(const char* descriptor, mirror::Class* new_klass, size_t hash)
       REQUIRES(!lock_)
diff --git a/runtime/entrypoints/entrypoint_utils-inl.h b/runtime/entrypoints/entrypoint_utils-inl.h
index 28aca6c..3bc49b8 100644
--- a/runtime/entrypoints/entrypoint_utils-inl.h
+++ b/runtime/entrypoints/entrypoint_utils-inl.h
@@ -709,10 +709,10 @@
     return resolved_method;
   } else if (type == kSuper) {
     // TODO This lookup is rather slow.
-    dex::TypeIndex method_type_idx =
-        referrer->GetDexFile()->GetMethodId(method_idx).class_idx_;
-    mirror::Class* method_reference_class =
-        referrer->GetDexCache()->GetResolvedType(method_type_idx);
+    ObjPtr<mirror::DexCache> dex_cache = referrer->GetDexCache();
+    dex::TypeIndex method_type_idx = dex_cache->GetDexFile()->GetMethodId(method_idx).class_idx_;
+    ObjPtr<mirror::Class> method_reference_class = ClassLinker::LookupResolvedType(
+        method_type_idx, dex_cache, referrer->GetClassLoader());
     if (method_reference_class == nullptr) {
       // Need to do full type resolution...
       return nullptr;
diff --git a/runtime/gc/space/image_space.cc b/runtime/gc/space/image_space.cc
index 2163a20..010ef11 100644
--- a/runtime/gc/space/image_space.cc
+++ b/runtime/gc/space/image_space.cc
@@ -1237,9 +1237,9 @@
           }
           dex_cache->FixupStrings<kWithoutReadBarrier>(new_strings, fixup_adapter);
         }
-        GcRoot<mirror::Class>* types = dex_cache->GetResolvedTypes();
+        mirror::TypeDexCacheType* types = dex_cache->GetResolvedTypes();
         if (types != nullptr) {
-          GcRoot<mirror::Class>* new_types = fixup_adapter.ForwardObject(types);
+          mirror::TypeDexCacheType* new_types = fixup_adapter.ForwardObject(types);
           if (types != new_types) {
             dex_cache->SetResolvedTypes(new_types);
           }
diff --git a/runtime/image.cc b/runtime/image.cc
index f545f8d..6dbf20b 100644
--- a/runtime/image.cc
+++ b/runtime/image.cc
@@ -25,7 +25,7 @@
 namespace art {
 
 const uint8_t ImageHeader::kImageMagic[] = { 'a', 'r', 't', '\n' };
-const uint8_t ImageHeader::kImageVersion[] = { '0', '4', '1', '\0' };  // Revert DexCache types.
+const uint8_t ImageHeader::kImageVersion[] = { '0', '4', '2', '\0' };  // hash-based DexCache types
 
 ImageHeader::ImageHeader(uint32_t image_begin,
                          uint32_t image_size,
diff --git a/runtime/mirror/class.cc b/runtime/mirror/class.cc
index 9a9a5d8..eb2ec9b 100644
--- a/runtime/mirror/class.cc
+++ b/runtime/mirror/class.cc
@@ -951,7 +951,8 @@
     return interfaces->Get(idx);
   } else {
     dex::TypeIndex type_idx = klass->GetDirectInterfaceTypeIdx(idx);
-    ObjPtr<Class> interface = klass->GetDexCache()->GetResolvedType(type_idx);
+    ObjPtr<Class> interface = ClassLinker::LookupResolvedType(
+        type_idx, klass->GetDexCache(), klass->GetClassLoader());
     return interface;
   }
 }
diff --git a/runtime/mirror/dex_cache-inl.h b/runtime/mirror/dex_cache-inl.h
index 973c8ed..29bf6a0 100644
--- a/runtime/mirror/dex_cache-inl.h
+++ b/runtime/mirror/dex_cache-inl.h
@@ -41,14 +41,22 @@
   return Class::ComputeClassSize(true, vtable_entries, 0, 0, 0, 0, 0, pointer_size);
 }
 
-inline mirror::String* DexCache::GetResolvedString(dex::StringIndex string_idx) {
+inline uint32_t DexCache::StringSlotIndex(dex::StringIndex string_idx) {
   DCHECK_LT(string_idx.index_, GetDexFile()->NumStringIds());
-  return StringDexCachePair::Lookup(GetStrings(), string_idx.index_, NumStrings()).Read();
+  const uint32_t slot_idx = string_idx.index_ % kDexCacheStringCacheSize;
+  DCHECK_LT(slot_idx, NumStrings());
+  return slot_idx;
 }
 
-inline void DexCache::SetResolvedString(dex::StringIndex string_idx,
-                                        ObjPtr<mirror::String> resolved) {
-  StringDexCachePair::Assign(GetStrings(), string_idx.index_, resolved.Ptr(), NumStrings());
+inline String* DexCache::GetResolvedString(dex::StringIndex string_idx) {
+  return GetStrings()[StringSlotIndex(string_idx)].load(
+      std::memory_order_relaxed).GetObjectForIndex(string_idx.index_);
+}
+
+inline void DexCache::SetResolvedString(dex::StringIndex string_idx, ObjPtr<String> resolved) {
+  DCHECK(resolved != nullptr);
+  GetStrings()[StringSlotIndex(string_idx)].store(
+      StringDexCachePair(resolved, string_idx.index_), std::memory_order_relaxed);
   Runtime* const runtime = Runtime::Current();
   if (UNLIKELY(runtime->IsActiveTransaction())) {
     DCHECK(runtime->IsAotCompiler());
@@ -59,50 +67,70 @@
 }
 
 inline void DexCache::ClearString(dex::StringIndex string_idx) {
-  const uint32_t slot_idx = string_idx.index_ % NumStrings();
   DCHECK(Runtime::Current()->IsAotCompiler());
+  uint32_t slot_idx = StringSlotIndex(string_idx);
   StringDexCacheType* slot = &GetStrings()[slot_idx];
   // This is racy but should only be called from the transactional interpreter.
   if (slot->load(std::memory_order_relaxed).index == string_idx.index_) {
-    StringDexCachePair cleared(
-        nullptr,
-        StringDexCachePair::InvalidIndexForSlot(slot_idx));
+    StringDexCachePair cleared(nullptr, StringDexCachePair::InvalidIndexForSlot(slot_idx));
     slot->store(cleared, std::memory_order_relaxed);
   }
 }
 
+inline uint32_t DexCache::TypeSlotIndex(dex::TypeIndex type_idx) {
+  DCHECK_LT(type_idx.index_, GetDexFile()->NumTypeIds());
+  const uint32_t slot_idx = type_idx.index_ % kDexCacheTypeCacheSize;
+  DCHECK_LT(slot_idx, NumResolvedTypes());
+  return slot_idx;
+}
+
 inline Class* DexCache::GetResolvedType(dex::TypeIndex type_idx) {
   // It is theorized that a load acquire is not required since obtaining the resolved class will
   // always have an address dependency or a lock.
-  DCHECK_LT(type_idx.index_, NumResolvedTypes());
-  return GetResolvedTypes()[type_idx.index_].Read();
+  return GetResolvedTypes()[TypeSlotIndex(type_idx)].load(
+      std::memory_order_relaxed).GetObjectForIndex(type_idx.index_);
 }
 
 inline void DexCache::SetResolvedType(dex::TypeIndex type_idx, ObjPtr<Class> resolved) {
-  DCHECK_LT(type_idx.index_, NumResolvedTypes());  // NOTE: Unchecked, i.e. not throwing AIOOB.
+  DCHECK(resolved != nullptr);
   // TODO default transaction support.
   // Use a release store for SetResolvedType. This is done to prevent other threads from seeing a
   // class but not necessarily seeing the loaded members like the static fields array.
   // See b/32075261.
-  reinterpret_cast<Atomic<GcRoot<mirror::Class>>&>(GetResolvedTypes()[type_idx.index_]).
-      StoreRelease(GcRoot<Class>(resolved));
+  GetResolvedTypes()[TypeSlotIndex(type_idx)].store(
+      TypeDexCachePair(resolved, type_idx.index_), std::memory_order_release);
   // TODO: Fine-grained marking, so that we don't need to go through all arrays in full.
   Runtime::Current()->GetHeap()->WriteBarrierEveryFieldOf(this);
 }
 
-inline MethodType* DexCache::GetResolvedMethodType(uint32_t proto_idx) {
+inline void DexCache::ClearResolvedType(dex::TypeIndex type_idx) {
+  DCHECK(Runtime::Current()->IsAotCompiler());
+  uint32_t slot_idx = TypeSlotIndex(type_idx);
+  TypeDexCacheType* slot = &GetResolvedTypes()[slot_idx];
+  // This is racy but should only be called from the single-threaded ImageWriter and tests.
+  if (slot->load(std::memory_order_relaxed).index == type_idx.index_) {
+    TypeDexCachePair cleared(nullptr, TypeDexCachePair::InvalidIndexForSlot(slot_idx));
+    slot->store(cleared, std::memory_order_relaxed);
+  }
+}
+
+inline uint32_t DexCache::MethodTypeSlotIndex(uint32_t proto_idx) {
   DCHECK(Runtime::Current()->IsMethodHandlesEnabled());
   DCHECK_LT(proto_idx, GetDexFile()->NumProtoIds());
-  return MethodTypeDexCachePair::Lookup(
-      GetResolvedMethodTypes(), proto_idx, NumResolvedMethodTypes()).Read();
+  const uint32_t slot_idx = proto_idx % kDexCacheMethodTypeCacheSize;
+  DCHECK_LT(slot_idx, NumResolvedMethodTypes());
+  return slot_idx;
+}
+
+inline MethodType* DexCache::GetResolvedMethodType(uint32_t proto_idx) {
+  return GetResolvedMethodTypes()[MethodTypeSlotIndex(proto_idx)].load(
+      std::memory_order_relaxed).GetObjectForIndex(proto_idx);
 }
 
 inline void DexCache::SetResolvedMethodType(uint32_t proto_idx, MethodType* resolved) {
-  DCHECK(Runtime::Current()->IsMethodHandlesEnabled());
-  DCHECK_LT(proto_idx, GetDexFile()->NumProtoIds());
-
-  MethodTypeDexCachePair::Assign(GetResolvedMethodTypes(), proto_idx, resolved,
-                                 NumResolvedMethodTypes());
+  DCHECK(resolved != nullptr);
+  GetResolvedMethodTypes()[MethodTypeSlotIndex(proto_idx)].store(
+      MethodTypeDexCachePair(resolved, proto_idx), std::memory_order_relaxed);
   // TODO: Fine-grained marking, so that we don't need to go through all arrays in full.
   Runtime::Current()->GetHeap()->WriteBarrierEveryFieldOf(this);
 }
@@ -228,15 +256,13 @@
   VisitInstanceFieldsReferences<kVerifyFlags, kReadBarrierOption>(klass, visitor);
   // Visit arrays after.
   if (kVisitNativeRoots) {
-    VisitDexCachePairs<mirror::String, kReadBarrierOption, Visitor>(
+    VisitDexCachePairs<String, kReadBarrierOption, Visitor>(
         GetStrings(), NumStrings(), visitor);
 
-    GcRoot<mirror::Class>* resolved_types = GetResolvedTypes();
-    for (size_t i = 0, num_types = NumResolvedTypes(); i != num_types; ++i) {
-      visitor.VisitRootIfNonNull(resolved_types[i].AddressWithoutBarrier());
-    }
+    VisitDexCachePairs<Class, kReadBarrierOption, Visitor>(
+        GetResolvedTypes(), NumResolvedTypes(), visitor);
 
-    VisitDexCachePairs<mirror::MethodType, kReadBarrierOption, Visitor>(
+    VisitDexCachePairs<MethodType, kReadBarrierOption, Visitor>(
         GetResolvedMethodTypes(), NumResolvedMethodTypes(), visitor);
 
     GcRoot<mirror::CallSite>* resolved_call_sites = GetResolvedCallSites();
@@ -247,35 +273,37 @@
 }
 
 template <ReadBarrierOption kReadBarrierOption, typename Visitor>
-inline void DexCache::FixupStrings(mirror::StringDexCacheType* dest, const Visitor& visitor) {
-  mirror::StringDexCacheType* src = GetStrings();
+inline void DexCache::FixupStrings(StringDexCacheType* dest, const Visitor& visitor) {
+  StringDexCacheType* src = GetStrings();
   for (size_t i = 0, count = NumStrings(); i < count; ++i) {
     StringDexCachePair source = src[i].load(std::memory_order_relaxed);
-    mirror::String* ptr = source.object.Read<kReadBarrierOption>();
-    mirror::String* new_source = visitor(ptr);
+    String* ptr = source.object.Read<kReadBarrierOption>();
+    String* new_source = visitor(ptr);
     source.object = GcRoot<String>(new_source);
     dest[i].store(source, std::memory_order_relaxed);
   }
 }
 
 template <ReadBarrierOption kReadBarrierOption, typename Visitor>
-inline void DexCache::FixupResolvedTypes(GcRoot<mirror::Class>* dest, const Visitor& visitor) {
-  GcRoot<mirror::Class>* src = GetResolvedTypes();
+inline void DexCache::FixupResolvedTypes(TypeDexCacheType* dest, const Visitor& visitor) {
+  TypeDexCacheType* src = GetResolvedTypes();
   for (size_t i = 0, count = NumResolvedTypes(); i < count; ++i) {
-    mirror::Class* source = src[i].Read<kReadBarrierOption>();
-    mirror::Class* new_source = visitor(source);
-    dest[i] = GcRoot<mirror::Class>(new_source);
+    TypeDexCachePair source = src[i].load(std::memory_order_relaxed);
+    Class* ptr = source.object.Read<kReadBarrierOption>();
+    Class* new_source = visitor(ptr);
+    source.object = GcRoot<Class>(new_source);
+    dest[i].store(source, std::memory_order_relaxed);
   }
 }
 
 template <ReadBarrierOption kReadBarrierOption, typename Visitor>
-inline void DexCache::FixupResolvedMethodTypes(mirror::MethodTypeDexCacheType* dest,
+inline void DexCache::FixupResolvedMethodTypes(MethodTypeDexCacheType* dest,
                                                const Visitor& visitor) {
-  mirror::MethodTypeDexCacheType* src = GetResolvedMethodTypes();
+  MethodTypeDexCacheType* src = GetResolvedMethodTypes();
   for (size_t i = 0, count = NumResolvedMethodTypes(); i < count; ++i) {
     MethodTypeDexCachePair source = src[i].load(std::memory_order_relaxed);
-    mirror::MethodType* ptr = source.object.Read<kReadBarrierOption>();
-    mirror::MethodType* new_source = visitor(ptr);
+    MethodType* ptr = source.object.Read<kReadBarrierOption>();
+    MethodType* new_source = visitor(ptr);
     source.object = GcRoot<MethodType>(new_source);
     dest[i].store(source, std::memory_order_relaxed);
   }
diff --git a/runtime/mirror/dex_cache.cc b/runtime/mirror/dex_cache.cc
index 0f6acab..1b8b391 100644
--- a/runtime/mirror/dex_cache.cc
+++ b/runtime/mirror/dex_cache.cc
@@ -58,8 +58,8 @@
 
   mirror::StringDexCacheType* strings = (dex_file->NumStringIds() == 0u) ? nullptr :
       reinterpret_cast<mirror::StringDexCacheType*>(raw_arrays + layout.StringsOffset());
-  GcRoot<mirror::Class>* types = (dex_file->NumTypeIds() == 0u) ? nullptr :
-      reinterpret_cast<GcRoot<mirror::Class>*>(raw_arrays + layout.TypesOffset());
+  mirror::TypeDexCacheType* types = (dex_file->NumTypeIds() == 0u) ? nullptr :
+      reinterpret_cast<mirror::TypeDexCacheType*>(raw_arrays + layout.TypesOffset());
   ArtMethod** methods = (dex_file->NumMethodIds() == 0u) ? nullptr :
       reinterpret_cast<ArtMethod**>(raw_arrays + layout.MethodsOffset());
   ArtField** fields = (dex_file->NumFieldIds() == 0u) ? nullptr :
@@ -69,6 +69,10 @@
   if (dex_file->NumStringIds() < num_strings) {
     num_strings = dex_file->NumStringIds();
   }
+  size_t num_types = mirror::DexCache::kDexCacheTypeCacheSize;
+  if (dex_file->NumTypeIds() < num_types) {
+    num_types = dex_file->NumTypeIds();
+  }
 
   // Note that we allocate the method type dex caches regardless of this flag,
   // and we make sure here that they're not used by the runtime. This is in the
@@ -108,8 +112,9 @@
       CHECK_EQ(strings[i].load(std::memory_order_relaxed).index, 0u);
       CHECK(strings[i].load(std::memory_order_relaxed).object.IsNull());
     }
-    for (size_t i = 0; i < dex_file->NumTypeIds(); ++i) {
-      CHECK(types[i].IsNull());
+    for (size_t i = 0; i < num_types; ++i) {
+      CHECK_EQ(types[i].load(std::memory_order_relaxed).index, 0u);
+      CHECK(types[i].load(std::memory_order_relaxed).object.IsNull());
     }
     for (size_t i = 0; i < dex_file->NumMethodIds(); ++i) {
       CHECK(mirror::DexCache::GetElementPtrSize(methods, i, image_pointer_size) == nullptr);
@@ -128,6 +133,9 @@
   if (strings != nullptr) {
     mirror::StringDexCachePair::Initialize(strings);
   }
+  if (types != nullptr) {
+    mirror::TypeDexCachePair::Initialize(types);
+  }
   if (method_types != nullptr) {
     mirror::MethodTypeDexCachePair::Initialize(method_types);
   }
@@ -136,7 +144,7 @@
                   strings,
                   num_strings,
                   types,
-                  dex_file->NumTypeIds(),
+                  num_types,
                   methods,
                   dex_file->NumMethodIds(),
                   fields,
@@ -152,7 +160,7 @@
                     ObjPtr<String> location,
                     StringDexCacheType* strings,
                     uint32_t num_strings,
-                    GcRoot<Class>* resolved_types,
+                    TypeDexCacheType* resolved_types,
                     uint32_t num_resolved_types,
                     ArtMethod** resolved_methods,
                     uint32_t num_resolved_methods,
diff --git a/runtime/mirror/dex_cache.h b/runtime/mirror/dex_cache.h
index 10bb5aa..0579198 100644
--- a/runtime/mirror/dex_cache.h
+++ b/runtime/mirror/dex_cache.h
@@ -18,14 +18,14 @@
 #define ART_RUNTIME_MIRROR_DEX_CACHE_H_
 
 #include "array.h"
-#include "art_field.h"
-#include "class.h"
+#include "base/bit_utils.h"
 #include "dex_file_types.h"
 #include "object.h"
 #include "object_array.h"
 
 namespace art {
 
+class ArtField;
 class ArtMethod;
 struct DexCacheOffsets;
 class DexFile;
@@ -37,6 +37,7 @@
 namespace mirror {
 
 class CallSite;
+class Class;
 class MethodType;
 class String;
 
@@ -61,7 +62,7 @@
   // it's always non-null if the id branch succeeds (except for the 0th id).
   // Set the initial state for the 0th entry to be {0,1} which is guaranteed to fail
   // the lookup id == stored id branch.
-  DexCachePair(T* object, uint32_t index)
+  DexCachePair(ObjPtr<T> object, uint32_t index)
       : object(object),
         index(index) {}
   DexCachePair() = default;
@@ -75,39 +76,28 @@
     dex_cache[0].store(first_elem, std::memory_order_relaxed);
   }
 
-  static GcRoot<T> Lookup(std::atomic<DexCachePair<T>>* dex_cache,
-                          uint32_t idx,
-                          uint32_t cache_size) {
-    DCHECK_NE(cache_size, 0u);
-    DexCachePair<T> element = dex_cache[idx % cache_size].load(std::memory_order_relaxed);
-    if (idx != element.index) {
-      return GcRoot<T>(nullptr);
-    }
-
-    DCHECK(!element.object.IsNull());
-    return element.object;
-  }
-
-  static void Assign(std::atomic<DexCachePair<T>>* dex_cache,
-                     uint32_t idx,
-                     T* object,
-                     uint32_t cache_size) {
-    DCHECK_LT(idx % cache_size, cache_size);
-    dex_cache[idx % cache_size].store(
-        DexCachePair<T>(object, idx), std::memory_order_relaxed);
-  }
-
   static uint32_t InvalidIndexForSlot(uint32_t slot) {
     // Since the cache size is a power of two, 0 will always map to slot 0.
     // Use 1 for slot 0 and 0 for all other slots.
     return (slot == 0) ? 1u : 0u;
   }
+
+  T* GetObjectForIndex(uint32_t idx) REQUIRES_SHARED(Locks::mutator_lock_) {
+    if (idx != index) {
+      return nullptr;
+    }
+    DCHECK(!object.IsNull());
+    return object.Read();
+  }
 };
 
-using StringDexCachePair = DexCachePair<mirror::String>;
+using TypeDexCachePair = DexCachePair<Class>;
+using TypeDexCacheType = std::atomic<TypeDexCachePair>;
+
+using StringDexCachePair = DexCachePair<String>;
 using StringDexCacheType = std::atomic<StringDexCachePair>;
 
-using MethodTypeDexCachePair = DexCachePair<mirror::MethodType>;
+using MethodTypeDexCachePair = DexCachePair<MethodType>;
 using MethodTypeDexCacheType = std::atomic<MethodTypeDexCachePair>;
 
 // C++ mirror of java.lang.DexCache.
@@ -116,6 +106,11 @@
   // Size of java.lang.DexCache.class.
   static uint32_t ClassSize(PointerSize pointer_size);
 
+  // Size of type dex cache. Needs to be a power of 2 for entrypoint assumptions to hold.
+  static constexpr size_t kDexCacheTypeCacheSize = 1024;
+  static_assert(IsPowerOfTwo(kDexCacheTypeCacheSize),
+                "Type dex cache size is not a power of 2.");
+
   // Size of string dex cache. Needs to be a power of 2 for entrypoint assumptions to hold.
   static constexpr size_t kDexCacheStringCacheSize = 1024;
   static_assert(IsPowerOfTwo(kDexCacheStringCacheSize),
@@ -127,6 +122,10 @@
   static_assert(IsPowerOfTwo(kDexCacheMethodTypeCacheSize),
                 "MethodType dex cache size is not a power of 2.");
 
+  static constexpr size_t StaticTypeSize() {
+    return kDexCacheTypeCacheSize;
+  }
+
   static constexpr size_t StaticStringSize() {
     return kDexCacheStringCacheSize;
   }
@@ -157,7 +156,7 @@
       REQUIRES_SHARED(Locks::mutator_lock_);
 
   template <ReadBarrierOption kReadBarrierOption = kWithReadBarrier, typename Visitor>
-  void FixupResolvedTypes(GcRoot<mirror::Class>* dest, const Visitor& visitor)
+  void FixupResolvedTypes(TypeDexCacheType* dest, const Visitor& visitor)
       REQUIRES_SHARED(Locks::mutator_lock_);
 
   template <ReadBarrierOption kReadBarrierOption = kWithReadBarrier, typename Visitor>
@@ -224,7 +223,7 @@
     return OFFSET_OF_OBJECT_MEMBER(DexCache, num_resolved_call_sites_);
   }
 
-  mirror::String* GetResolvedString(dex::StringIndex string_idx) ALWAYS_INLINE
+  String* GetResolvedString(dex::StringIndex string_idx) ALWAYS_INLINE
       REQUIRES_SHARED(Locks::mutator_lock_);
 
   void SetResolvedString(dex::StringIndex string_idx, ObjPtr<mirror::String> resolved) ALWAYS_INLINE
@@ -239,6 +238,8 @@
   void SetResolvedType(dex::TypeIndex type_idx, ObjPtr<Class> resolved)
       REQUIRES_SHARED(Locks::mutator_lock_);
 
+  void ClearResolvedType(dex::TypeIndex type_idx) REQUIRES_SHARED(Locks::mutator_lock_);
+
   ALWAYS_INLINE ArtMethod* GetResolvedMethod(uint32_t method_idx, PointerSize ptr_size)
       REQUIRES_SHARED(Locks::mutator_lock_);
 
@@ -278,11 +279,11 @@
     SetFieldPtr<false>(StringsOffset(), strings);
   }
 
-  GcRoot<Class>* GetResolvedTypes() ALWAYS_INLINE REQUIRES_SHARED(Locks::mutator_lock_) {
-    return GetFieldPtr<GcRoot<Class>*>(ResolvedTypesOffset());
+  TypeDexCacheType* GetResolvedTypes() ALWAYS_INLINE REQUIRES_SHARED(Locks::mutator_lock_) {
+    return GetFieldPtr<TypeDexCacheType*>(ResolvedTypesOffset());
   }
 
-  void SetResolvedTypes(GcRoot<Class>* resolved_types)
+  void SetResolvedTypes(TypeDexCacheType* resolved_types)
       ALWAYS_INLINE
       REQUIRES_SHARED(Locks::mutator_lock_) {
     SetFieldPtr<false>(ResolvedTypesOffset(), resolved_types);
@@ -363,7 +364,7 @@
     SetFieldPtr<false>(OFFSET_OF_OBJECT_MEMBER(DexCache, dex_file_), dex_file);
   }
 
-  void SetLocation(ObjPtr<mirror::String> location) REQUIRES_SHARED(Locks::mutator_lock_);
+  void SetLocation(ObjPtr<String> location) REQUIRES_SHARED(Locks::mutator_lock_);
 
   // NOTE: Get/SetElementPtrSize() are intended for working with ArtMethod** and ArtField**
   // provided by GetResolvedMethods/Fields() and ArtMethod::GetDexCacheResolvedMethods(),
@@ -380,7 +381,7 @@
             ObjPtr<String> location,
             StringDexCacheType* strings,
             uint32_t num_strings,
-            GcRoot<Class>* resolved_types,
+            TypeDexCacheType* resolved_types,
             uint32_t num_resolved_types,
             ArtMethod** resolved_methods,
             uint32_t num_resolved_methods,
@@ -393,12 +394,16 @@
             PointerSize pointer_size)
       REQUIRES_SHARED(Locks::mutator_lock_);
 
+  uint32_t StringSlotIndex(dex::StringIndex string_idx) REQUIRES_SHARED(Locks::mutator_lock_);
+  uint32_t TypeSlotIndex(dex::TypeIndex type_idx) REQUIRES_SHARED(Locks::mutator_lock_);
+  uint32_t MethodTypeSlotIndex(uint32_t proto_idx) REQUIRES_SHARED(Locks::mutator_lock_);
+
   // Visit instance fields of the dex cache as well as its associated arrays.
   template <bool kVisitNativeRoots,
             VerifyObjectFlags kVerifyFlags = kDefaultVerifyFlags,
             ReadBarrierOption kReadBarrierOption = kWithReadBarrier,
             typename Visitor>
-  void VisitReferences(ObjPtr<mirror::Class> klass, const Visitor& visitor)
+  void VisitReferences(ObjPtr<Class> klass, const Visitor& visitor)
       REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::heap_bitmap_lock_);
 
   HeapReference<Object> dex_;
@@ -410,7 +415,7 @@
   uint64_t resolved_method_types_;  // std::atomic<MethodTypeDexCachePair>* array with
                                     // num_resolved_method_types_ elements.
   uint64_t resolved_methods_;       // ArtMethod*, array with num_resolved_methods_ elements.
-  uint64_t resolved_types_;         // GcRoot<Class>*, array with num_resolved_types_ elements.
+  uint64_t resolved_types_;         // TypeDexCacheType*, array with num_resolved_types_ elements.
   uint64_t strings_;                // std::atomic<StringDexCachePair>*, array with num_strings_
                                     // elements.
 
diff --git a/runtime/mirror/dex_cache_test.cc b/runtime/mirror/dex_cache_test.cc
index 5a2ab71..ef0aaaa 100644
--- a/runtime/mirror/dex_cache_test.cc
+++ b/runtime/mirror/dex_cache_test.cc
@@ -51,7 +51,8 @@
 
   EXPECT_TRUE(dex_cache->StaticStringSize() == dex_cache->NumStrings()
       || java_lang_dex_file_->NumStringIds() == dex_cache->NumStrings());
-  EXPECT_EQ(java_lang_dex_file_->NumTypeIds(),   dex_cache->NumResolvedTypes());
+  EXPECT_TRUE(dex_cache->StaticTypeSize() == dex_cache->NumResolvedTypes()
+      || java_lang_dex_file_->NumTypeIds() == dex_cache->NumResolvedTypes());
   EXPECT_EQ(java_lang_dex_file_->NumMethodIds(), dex_cache->NumResolvedMethods());
   EXPECT_EQ(java_lang_dex_file_->NumFieldIds(),  dex_cache->NumResolvedFields());
   EXPECT_TRUE(dex_cache->StaticMethodTypeSize() == dex_cache->NumResolvedMethodTypes()
diff --git a/runtime/native/java_lang_DexCache.cc b/runtime/native/java_lang_DexCache.cc
index ada3a9d..8fda4df 100644
--- a/runtime/native/java_lang_DexCache.cc
+++ b/runtime/native/java_lang_DexCache.cc
@@ -53,7 +53,7 @@
 static jobject DexCache_getResolvedType(JNIEnv* env, jobject javaDexCache, jint type_index) {
   ScopedFastNativeObjectAccess soa(env);
   ObjPtr<mirror::DexCache> dex_cache = soa.Decode<mirror::DexCache>(javaDexCache);
-  CHECK_LT(static_cast<size_t>(type_index), dex_cache->NumResolvedTypes());
+  CHECK_LT(static_cast<size_t>(type_index), dex_cache->GetDexFile()->NumTypeIds());
   return soa.AddLocalReference<jobject>(dex_cache->GetResolvedType(dex::TypeIndex(type_index)));
 }
 
diff --git a/runtime/oat.h b/runtime/oat.h
index 656b868..1544121 100644
--- a/runtime/oat.h
+++ b/runtime/oat.h
@@ -32,7 +32,7 @@
 class PACKED(4) OatHeader {
  public:
   static constexpr uint8_t kOatMagic[] = { 'o', 'a', 't', '\n' };
-  static constexpr uint8_t kOatVersion[] = { '1', '1', '3', '\0' };  // Invoke info change.
+  static constexpr uint8_t kOatVersion[] = { '1', '1', '4', '\0' };  // hash-based DexCache types.
 
   static constexpr const char* kImageLocationKey = "image-location";
   static constexpr const char* kDex2OatCmdLineKey = "dex2oat-cmdline";
diff --git a/runtime/utils/dex_cache_arrays_layout-inl.h b/runtime/utils/dex_cache_arrays_layout-inl.h
index 9865821..f9a1405 100644
--- a/runtime/utils/dex_cache_arrays_layout-inl.h
+++ b/runtime/utils/dex_cache_arrays_layout-inl.h
@@ -51,9 +51,11 @@
     : DexCacheArraysLayout(pointer_size, dex_file->GetHeader(), dex_file->NumCallSiteIds()) {
 }
 
-inline constexpr size_t DexCacheArraysLayout::Alignment() {
-  // GcRoot<> alignment is 4, i.e. lower than or equal to the pointer alignment.
-  static_assert(alignof(GcRoot<mirror::Class>) == 4, "Expecting alignof(GcRoot<>) == 4");
+constexpr size_t DexCacheArraysLayout::Alignment() {
+  // mirror::Type/String/MethodTypeDexCacheType alignment is 8,
+  // i.e. higher than or equal to the pointer alignment.
+  static_assert(alignof(mirror::TypeDexCacheType) == 8,
+                "Expecting alignof(ClassDexCacheType) == 8");
   static_assert(alignof(mirror::StringDexCacheType) == 8,
                 "Expecting alignof(StringDexCacheType) == 8");
   static_assert(alignof(mirror::MethodTypeDexCacheType) == 8,
@@ -63,17 +65,22 @@
 }
 
 template <typename T>
-static constexpr PointerSize GcRootAsPointerSize() {
+constexpr PointerSize GcRootAsPointerSize() {
   static_assert(sizeof(GcRoot<T>) == 4U, "Unexpected GcRoot size");
   return PointerSize::k32;
 }
 
 inline size_t DexCacheArraysLayout::TypeOffset(dex::TypeIndex type_idx) const {
-  return types_offset_ + ElementOffset(GcRootAsPointerSize<mirror::Class>(), type_idx.index_);
+  return types_offset_ + ElementOffset(PointerSize::k64,
+                                       type_idx.index_ % mirror::DexCache::kDexCacheTypeCacheSize);
 }
 
 inline size_t DexCacheArraysLayout::TypesSize(size_t num_elements) const {
-  return ArraySize(GcRootAsPointerSize<mirror::Class>(), num_elements);
+  size_t cache_size = mirror::DexCache::kDexCacheTypeCacheSize;
+  if (num_elements < cache_size) {
+    cache_size = num_elements;
+  }
+  return ArraySize(PointerSize::k64, cache_size);
 }
 
 inline size_t DexCacheArraysLayout::TypesAlignment() const {
diff --git a/runtime/verifier/method_verifier.cc b/runtime/verifier/method_verifier.cc
index 16739fa..38d151b 100644
--- a/runtime/verifier/method_verifier.cc
+++ b/runtime/verifier/method_verifier.cc
@@ -2399,7 +2399,8 @@
       const RegType& res_type = ResolveClassAndCheckAccess(type_idx);
       if (res_type.IsConflict()) {
         // If this is a primitive type, fail HARD.
-        mirror::Class* klass = dex_cache_->GetResolvedType(type_idx);
+        ObjPtr<mirror::Class> klass =
+            ClassLinker::LookupResolvedType(type_idx, dex_cache_.Get(), class_loader_.Get());
         if (klass != nullptr && klass->IsPrimitive()) {
           Fail(VERIFY_ERROR_BAD_CLASS_HARD) << "using primitive type "
               << dex_file_->StringByTypeIdx(type_idx) << " in instanceof in "
@@ -3722,9 +3723,16 @@
 }
 
 const RegType& MethodVerifier::ResolveClassAndCheckAccess(dex::TypeIndex class_idx) {
-  mirror::Class* klass = dex_cache_->GetResolvedType(class_idx);
+  mirror::Class* klass = can_load_classes_
+      ? Runtime::Current()->GetClassLinker()->ResolveType(
+          *dex_file_, class_idx, dex_cache_, class_loader_)
+      : ClassLinker::LookupResolvedType(class_idx, dex_cache_.Get(), class_loader_.Get()).Ptr();
+  if (can_load_classes_ && klass == nullptr) {
+    DCHECK(self_->IsExceptionPending());
+    self_->ClearException();
+  }
   const RegType* result = nullptr;
-  if (klass != nullptr) {
+  if (klass != nullptr && !klass->IsErroneous()) {
     bool precise = klass->CannotBeAssignedFromOtherTypes();
     if (precise && !IsInstantiableOrPrimitive(klass)) {
       const char* descriptor = dex_file_->StringByTypeIdx(class_idx);
@@ -3747,10 +3755,6 @@
         << "' in " << GetDeclaringClass();
     return *result;
   }
-  if (klass == nullptr && !result->IsUnresolvedTypes()) {
-    klass = result->GetClass();
-    dex_cache_->SetResolvedType(class_idx, klass);
-  }
 
   // Record result of class resolution attempt.
   VerifierDeps::MaybeRecordClassResolution(*dex_file_, class_idx, klass);
diff --git a/test/155-java-set-resolved-type/src/Main.java b/test/155-java-set-resolved-type/src/Main.java
index f92363e..8f79bd7 100644
--- a/test/155-java-set-resolved-type/src/Main.java
+++ b/test/155-java-set-resolved-type/src/Main.java
@@ -55,14 +55,10 @@
             Class<?> timpl = Class.forName("TestImplementation", false, mainLoader);
             // Clear the dex cache resolved types to force a proper lookup the next time
             // we need to find TestInterface.
-            // TODO: Enable clearing the dex cache when we switch to the hash-based type array
-            // and do a proper lookup. Currently, ClassLinker fully relies on the DexCache.
-            if (false) {
-                clearResolvedTypes(timpl);
-            }
+            clearResolvedTypes(timpl);
 
-            // Force intialization of TestClass2. This expects the interface type to be
-            // resolved and found through simple lookup.
+            // Force intialization of TestImplementation. This expects the interface type
+            // to be resolved and found through simple lookup.
             timpl.newInstance();
         } catch (Throwable t) {
             t.printStackTrace();
diff --git a/test/157-void-class/src/Main.java b/test/157-void-class/src/Main.java
index 0a052e7..322b705 100644
--- a/test/157-void-class/src/Main.java
+++ b/test/157-void-class/src/Main.java
@@ -35,11 +35,7 @@
         }
         // Clear the resolved types of the ojluni dex file to make sure there is no entry
         // for "V", i.e. void.
-        // TODO: Enable clearing the dex cache when we switch to the hash-based type array
-        // and do a proper lookup. Currently, ClassLinker fully relies on the DexCache.
-        if (false) {
-            clearResolvedTypes(Integer.class);
-        }
+        clearResolvedTypes(Integer.class);
         // With java.lang.Void being compile-time verified but uninitialized, initialize
         // it now. Previously, this would indirectly initialize TYPE with the current,
         // i.e. zero-initialized, value of TYPE. The only thing that could prevent the
diff --git a/test/158-app-image-class-table/expected.txt b/test/158-app-image-class-table/expected.txt
new file mode 100644
index 0000000..6a5618e
--- /dev/null
+++ b/test/158-app-image-class-table/expected.txt
@@ -0,0 +1 @@
+JNI_OnLoad called
diff --git a/test/158-app-image-class-table/info.txt b/test/158-app-image-class-table/info.txt
new file mode 100644
index 0000000..c844c8e
--- /dev/null
+++ b/test/158-app-image-class-table/info.txt
@@ -0,0 +1,3 @@
+Regression test for app image class table being erroneously omitted
+when it contains only boot image class loader classes while dex caches
+were written with references to these classes.
diff --git a/test/158-app-image-class-table/profile b/test/158-app-image-class-table/profile
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/158-app-image-class-table/profile
diff --git a/test/158-app-image-class-table/run b/test/158-app-image-class-table/run
new file mode 100644
index 0000000..146e180
--- /dev/null
+++ b/test/158-app-image-class-table/run
@@ -0,0 +1,17 @@
+#!/bin/bash
+#
+# Copyright (C) 2017 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#     http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+exec ${RUN} $@ --profile -Xcompiler-option --compiler-filter=speed-profile
diff --git a/test/158-app-image-class-table/src/Main.java b/test/158-app-image-class-table/src/Main.java
new file mode 100644
index 0000000..804468f
--- /dev/null
+++ b/test/158-app-image-class-table/src/Main.java
@@ -0,0 +1,55 @@
+/*
+ * Copyright (C) 2017 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+public class Main {
+    public static String TEST_NAME = "158-app-image-class-table";
+
+    public static void main(String[] args) {
+        try {
+            Class<?> class_loader_class = Class.forName("dalvik.system.PathClassLoader");
+            System.loadLibrary(args[0]);
+        } catch (ClassNotFoundException e) {
+            usingRI = true;
+            // Add expected JNI_OnLoad log line to match expected.txt.
+            System.out.println("JNI_OnLoad called");
+        }
+        try {
+            // Resolve but do not initialize TestImplementation. During the resolution,
+            // we see the Cloneable in the dex cache, so we do not try to look it up
+            // or resolve it.
+            Class<?> timpl =
+                Class.forName("TestImplementation", false, Main.class.getClassLoader());
+            // Clear the dex cache resolved types to force a proper lookup the next time
+            // we need to find TestInterface.
+            clearResolvedTypes(timpl);
+            // Force intialization of TestImplementation. This expects the interface type
+            // to be resolved and found through simple lookup.
+            timpl.newInstance();
+        } catch (Throwable t) {
+            t.printStackTrace();
+        }
+    }
+
+    public static void clearResolvedTypes(Class<?> c) {
+        if (!usingRI) {
+            nativeClearResolvedTypes(c);
+        }
+    }
+
+    private static boolean usingRI = false;
+
+    public static native void nativeClearResolvedTypes(Class<?> c);
+}
diff --git a/test/158-app-image-class-table/src/TestImplementation.java b/test/158-app-image-class-table/src/TestImplementation.java
new file mode 100644
index 0000000..558e587
--- /dev/null
+++ b/test/158-app-image-class-table/src/TestImplementation.java
@@ -0,0 +1,21 @@
+/*
+ * Copyright (C) 2017 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+public class TestImplementation implements Cloneable {
+    public Object clone() {
+        return new TestImplementation();
+    }
+}
diff --git a/test/626-const-class-linking/clear_dex_cache_types.cc b/test/626-const-class-linking/clear_dex_cache_types.cc
index b35dff4..e1af02e 100644
--- a/test/626-const-class-linking/clear_dex_cache_types.cc
+++ b/test/626-const-class-linking/clear_dex_cache_types.cc
@@ -27,7 +27,8 @@
   ScopedObjectAccess soa(Thread::Current());
   mirror::DexCache* dex_cache = soa.Decode<mirror::Class>(cls)->GetDexCache();
   for (size_t i = 0, num_types = dex_cache->NumResolvedTypes(); i != num_types; ++i) {
-    dex_cache->SetResolvedType(dex::TypeIndex(i), ObjPtr<mirror::Class>(nullptr));
+    mirror::TypeDexCachePair cleared(nullptr, mirror::TypeDexCachePair::InvalidIndexForSlot(i));
+    dex_cache->GetResolvedTypes()[i].store(cleared, std::memory_order_relaxed);
   }
 }