diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index b93c1af..db18661 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -65,6 +65,12 @@
 	cp $< $@
 	$(call dexpreopt-remove-classes.dex,$@)
 
+ART_TEST_GTEST_VerifierDeps_SRC := $(abspath $(wildcard $(LOCAL_PATH)/VerifierDeps/*.smali))
+ART_TEST_HOST_GTEST_VerifierDeps_DEX := $(dir $(ART_TEST_HOST_GTEST_Main_DEX))$(subst Main,VerifierDeps,$(basename $(notdir $(ART_TEST_HOST_GTEST_Main_DEX))))$(suffix $(ART_TEST_HOST_GTEST_Main_DEX))
+
+$(ART_TEST_HOST_GTEST_VerifierDeps_DEX): $(ART_TEST_GTEST_VerifierDeps_SRC) $(HOST_OUT_EXECUTABLES)/smali
+	 $(HOST_OUT_EXECUTABLES)/smali --output=$@ $(filter %.smali,$^)
+
 # Dex file dependencies for each gtest.
 ART_GTEST_dex2oat_environment_tests_DEX_DEPS := Main MainStripped MultiDex MultiDexModifiedSecondary Nested
 
@@ -88,6 +94,7 @@
 ART_GTEST_stub_test_DEX_DEPS := AllFields
 ART_GTEST_transaction_test_DEX_DEPS := Transaction
 ART_GTEST_type_lookup_table_test_DEX_DEPS := Lookup
+ART_GTEST_verifier_deps_test_DEX_DEPS := VerifierDeps
 
 # The elf writer test has dependencies on core.oat.
 ART_GTEST_elf_writer_test_HOST_DEPS := $(HOST_CORE_IMAGE_optimizing_no-pic_64) $(HOST_CORE_IMAGE_optimizing_no-pic_32)
@@ -562,11 +569,14 @@
 ART_GTEST_stub_test_DEX_DEPS :=
 ART_GTEST_transaction_test_DEX_DEPS :=
 ART_GTEST_dex2oat_environment_tests_DEX_DEPS :=
+ART_GTEST_verifier_deps_test_DEX_DEPS :=
 ART_VALGRIND_DEPENDENCIES :=
 ART_VALGRIND_TARGET_DEPENDENCIES :=
 $(foreach dir,$(GTEST_DEX_DIRECTORIES), $(eval ART_TEST_TARGET_GTEST_$(dir)_DEX :=))
 $(foreach dir,$(GTEST_DEX_DIRECTORIES), $(eval ART_TEST_HOST_GTEST_$(dir)_DEX :=))
 ART_TEST_HOST_GTEST_MainStripped_DEX :=
 ART_TEST_TARGET_GTEST_MainStripped_DEX :=
+ART_TEST_GTEST_VerifierDeps_SRC :=
+ART_TEST_HOST_GTEST_VerifierDeps_DEX :=
 GTEST_DEX_DIRECTORIES :=
 LOCAL_PATH :=
diff --git a/compiler/dex/quick_compiler_callbacks.h b/compiler/dex/quick_compiler_callbacks.h
index 1f69686..824194c 100644
--- a/compiler/dex/quick_compiler_callbacks.h
+++ b/compiler/dex/quick_compiler_callbacks.h
@@ -29,8 +29,10 @@
     QuickCompilerCallbacks(VerificationResults* verification_results,
                            DexFileToMethodInlinerMap* method_inliner_map,
                            CompilerCallbacks::CallbackMode mode)
-        : CompilerCallbacks(mode), verification_results_(verification_results),
-          method_inliner_map_(method_inliner_map) {
+        : CompilerCallbacks(mode),
+          verification_results_(verification_results),
+          method_inliner_map_(method_inliner_map),
+          verifier_deps_(nullptr) {
       CHECK(verification_results != nullptr);
       CHECK(method_inliner_map != nullptr);
     }
@@ -47,9 +49,18 @@
       return true;
     }
 
+    verifier::VerifierDeps* GetVerifierDeps() const OVERRIDE {
+      return verifier_deps_;
+    }
+
+    void SetVerifierDeps(verifier::VerifierDeps* deps) {
+      verifier_deps_ = deps;
+    }
+
   private:
     VerificationResults* const verification_results_;
     DexFileToMethodInlinerMap* const method_inliner_map_;
+    verifier::VerifierDeps* verifier_deps_;
 };
 
 }  // namespace art
diff --git a/compiler/dex/verified_method.cc b/compiler/dex/verified_method.cc
index 4bcd59a..e19fb7b 100644
--- a/compiler/dex/verified_method.cc
+++ b/compiler/dex/verified_method.cc
@@ -231,7 +231,7 @@
                                                                 inst->VRegA_21c()));
         const verifier::RegType& cast_type =
             method_verifier->ResolveCheckedClass(inst->VRegB_21c());
-        is_safe_cast = cast_type.IsStrictlyAssignableFrom(reg_type);
+        is_safe_cast = cast_type.IsStrictlyAssignableFrom(reg_type, method_verifier);
       } else {
         const verifier::RegType& array_type(line->GetRegisterType(method_verifier,
                                                                   inst->VRegB_23x()));
@@ -243,7 +243,7 @@
                                                                     inst->VRegA_23x()));
           const verifier::RegType& component_type = method_verifier->GetRegTypeCache()
               ->GetComponentType(array_type, method_verifier->GetClassLoader());
-          is_safe_cast = component_type.IsStrictlyAssignableFrom(value_type);
+          is_safe_cast = component_type.IsStrictlyAssignableFrom(value_type, method_verifier);
         }
       }
       if (is_safe_cast) {
diff --git a/dex2oat/dex2oat.cc b/dex2oat/dex2oat.cc
index 1296bcf..63f5e0c 100644
--- a/dex2oat/dex2oat.cc
+++ b/dex2oat/dex2oat.cc
@@ -77,6 +77,7 @@
 #include "ScopedLocalRef.h"
 #include "scoped_thread_state_change.h"
 #include "utils.h"
+#include "verifier/verifier_deps.h"
 #include "well_known_classes.h"
 #include "zip_archive.h"
 
@@ -1472,6 +1473,12 @@
 
     dex_files_ = MakeNonOwningPointerVector(opened_dex_files_);
 
+    if (!IsBootImage()) {
+      // Collect verification dependencies when compiling an app.
+      verifier_deps_.reset(new verifier::VerifierDeps(dex_files_));
+      callbacks_->SetVerifierDeps(verifier_deps_.get());
+    }
+
     // We had to postpone the swap decision till now, as this is the point when we actually
     // know about the dex files we're going to use.
 
@@ -2626,6 +2633,9 @@
   std::vector<std::vector<const DexFile*>> dex_files_per_oat_file_;
   std::unordered_map<const DexFile*, size_t> dex_file_oat_index_map_;
 
+  // Collector of verifier dependencies.
+  std::unique_ptr<verifier::VerifierDeps> verifier_deps_;
+
   // Backing storage.
   std::vector<std::string> char_backing_storage_;
 
diff --git a/runtime/Android.bp b/runtime/Android.bp
index 6acc1d8..c00689b 100644
--- a/runtime/Android.bp
+++ b/runtime/Android.bp
@@ -198,6 +198,7 @@
         "verifier/reg_type.cc",
         "verifier/reg_type_cache.cc",
         "verifier/register_line.cc",
+        "verifier/verifier_deps.cc",
         "well_known_classes.cc",
         "zip_archive.cc",
 
@@ -558,6 +559,7 @@
         "utils_test.cc",
         "verifier/method_verifier_test.cc",
         "verifier/reg_type_test.cc",
+        "verifier/verifier_deps_test.cc",
         "zip_archive_test.cc",
     ],
     shared_libs: [
diff --git a/runtime/base/mutex.cc b/runtime/base/mutex.cc
index fec918b..43c38c4 100644
--- a/runtime/base/mutex.cc
+++ b/runtime/base/mutex.cc
@@ -48,6 +48,7 @@
 Mutex* Locks::modify_ldt_lock_ = nullptr;
 MutatorMutex* Locks::mutator_lock_ = nullptr;
 Mutex* Locks::profiler_lock_ = nullptr;
+Mutex* Locks::verifier_deps_lock_ = nullptr;
 ReaderWriterMutex* Locks::oat_file_manager_lock_ = nullptr;
 Mutex* Locks::host_dlopen_handles_lock_ = nullptr;
 Mutex* Locks::reference_processor_lock_ = nullptr;
@@ -947,6 +948,7 @@
     DCHECK(deoptimization_lock_ != nullptr);
     DCHECK(heap_bitmap_lock_ != nullptr);
     DCHECK(oat_file_manager_lock_ != nullptr);
+    DCHECK(verifier_deps_lock_ != nullptr);
     DCHECK(host_dlopen_handles_lock_ != nullptr);
     DCHECK(intern_table_lock_ != nullptr);
     DCHECK(jni_libraries_lock_ != nullptr);
@@ -1035,6 +1037,10 @@
     DCHECK(oat_file_manager_lock_ == nullptr);
     oat_file_manager_lock_ = new ReaderWriterMutex("OatFile manager lock", current_lock_level);
 
+    UPDATE_CURRENT_LOCK_LEVEL(kVerifierDepsLock);
+    DCHECK(verifier_deps_lock_ == nullptr);
+    verifier_deps_lock_ = new Mutex("verifier deps lock", current_lock_level);
+
     UPDATE_CURRENT_LOCK_LEVEL(kHostDlOpenHandlesLock);
     DCHECK(host_dlopen_handles_lock_ == nullptr);
     host_dlopen_handles_lock_ = new Mutex("host dlopen handles lock", current_lock_level);
diff --git a/runtime/base/mutex.h b/runtime/base/mutex.h
index d0dc886..8af9fa5 100644
--- a/runtime/base/mutex.h
+++ b/runtime/base/mutex.h
@@ -83,6 +83,7 @@
   kInternTableLock,
   kOatFileSecondaryLookupLock,
   kHostDlOpenHandlesLock,
+  kVerifierDepsLock,
   kOatFileManagerLock,
   kTracingUniqueMethodsLock,
   kTracingStreamingLock,
@@ -650,8 +651,11 @@
   // Guards opened oat files in OatFileManager.
   static ReaderWriterMutex* oat_file_manager_lock_ ACQUIRED_AFTER(modify_ldt_lock_);
 
+  // Guards verifier dependency collection in VerifierDeps.
+  static Mutex* verifier_deps_lock_ ACQUIRED_AFTER(oat_file_manager_lock_);
+
   // Guards dlopen_handles_ in DlOpenOatFile.
-  static Mutex* host_dlopen_handles_lock_ ACQUIRED_AFTER(oat_file_manager_lock_);
+  static Mutex* host_dlopen_handles_lock_ ACQUIRED_AFTER(verifier_deps_lock_);
 
   // Guards intern table.
   static Mutex* intern_table_lock_ ACQUIRED_AFTER(host_dlopen_handles_lock_);
diff --git a/runtime/compiler_callbacks.h b/runtime/compiler_callbacks.h
index ee797e0..00dedef 100644
--- a/runtime/compiler_callbacks.h
+++ b/runtime/compiler_callbacks.h
@@ -25,6 +25,7 @@
 namespace verifier {
 
 class MethodVerifier;
+class VerifierDeps;
 
 }  // namespace verifier
 
@@ -45,6 +46,8 @@
   // done so. Return false if relocating in this way would be problematic.
   virtual bool IsRelocationPossible() = 0;
 
+  virtual verifier::VerifierDeps* GetVerifierDeps() const = 0;
+
   bool IsBootImage() {
     return mode_ == CallbackMode::kCompileBootImage;
   }
diff --git a/runtime/noop_compiler_callbacks.h b/runtime/noop_compiler_callbacks.h
index 02081cb..9c777cc 100644
--- a/runtime/noop_compiler_callbacks.h
+++ b/runtime/noop_compiler_callbacks.h
@@ -36,6 +36,8 @@
   // to disable the relocation since both deal with writing out the images directly.
   bool IsRelocationPossible() OVERRIDE { return false; }
 
+  verifier::VerifierDeps* GetVerifierDeps() const OVERRIDE { return nullptr; }
+
  private:
   DISALLOW_COPY_AND_ASSIGN(NoopCompilerCallbacks);
 };
diff --git a/runtime/utils.cc b/runtime/utils.cc
index d48edcf..6f10aaa 100644
--- a/runtime/utils.cc
+++ b/runtime/utils.cc
@@ -442,6 +442,12 @@
   if ((access_flags & kAccStatic) != 0) {
     result += "static ";
   }
+  if ((access_flags & kAccAbstract) != 0) {
+    result += "abstract ";
+  }
+  if ((access_flags & kAccInterface) != 0) {
+    result += "interface ";
+  }
   if ((access_flags & kAccTransient) != 0) {
     result += "transient ";
   }
diff --git a/runtime/verifier/method_resolution_kind.h b/runtime/verifier/method_resolution_kind.h
new file mode 100644
index 0000000..f72eb7a
--- /dev/null
+++ b/runtime/verifier/method_resolution_kind.h
@@ -0,0 +1,33 @@
+/*
+ * Copyright (C) 2016 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.
+ */
+
+#ifndef ART_RUNTIME_VERIFIER_METHOD_RESOLUTION_KIND_H_
+#define ART_RUNTIME_VERIFIER_METHOD_RESOLUTION_KIND_H_
+
+namespace art {
+namespace verifier {
+
+// Values corresponding to the method resolution algorithms defined in mirror::Class.
+enum MethodResolutionKind {
+  kDirectMethodResolution,
+  kVirtualMethodResolution,
+  kInterfaceMethodResolution,
+};
+
+}  // namespace verifier
+}  // namespace art
+
+#endif  // ART_RUNTIME_VERIFIER_METHOD_RESOLUTION_KIND_H_
diff --git a/runtime/verifier/method_verifier.cc b/runtime/verifier/method_verifier.cc
index 6b1170b..f1d3189 100644
--- a/runtime/verifier/method_verifier.cc
+++ b/runtime/verifier/method_verifier.cc
@@ -37,6 +37,7 @@
 #include "indenter.h"
 #include "intern_table.h"
 #include "leb128.h"
+#include "method_resolution_kind.h"
 #include "mirror/class.h"
 #include "mirror/class-inl.h"
 #include "mirror/dex_cache-inl.h"
@@ -47,6 +48,7 @@
 #include "runtime.h"
 #include "scoped_thread_state_change.h"
 #include "utils.h"
+#include "verifier_deps.h"
 #include "handle_scope-inl.h"
 
 namespace art {
@@ -2189,7 +2191,7 @@
             // We really do expect a reference here.
             Fail(VERIFY_ERROR_BAD_CLASS_HARD) << "return-object returns a non-reference type "
                                               << reg_type;
-          } else if (!return_type.IsAssignableFrom(reg_type)) {
+          } else if (!return_type.IsAssignableFrom(reg_type, this)) {
             if (reg_type.IsUnresolvedTypes() || return_type.IsUnresolvedTypes()) {
               Fail(VERIFY_ERROR_NO_CLASS) << " can't resolve returned type '" << return_type
                   << "' or '" << reg_type << "'";
@@ -2198,7 +2200,7 @@
               // Check whether arrays are involved. They will show a valid class status, even
               // if their components are erroneous.
               if (reg_type.IsArrayTypes() && return_type.IsArrayTypes()) {
-                return_type.CanAssignArray(reg_type, reg_types_, class_loader_, &soft_error);
+                return_type.CanAssignArray(reg_type, reg_types_, class_loader_, this, &soft_error);
                 if (soft_error) {
                   Fail(VERIFY_ERROR_BAD_CLASS_SOFT) << "array with erroneous component type: "
                         << reg_type << " vs " << return_type;
@@ -2486,7 +2488,7 @@
       break;
     case Instruction::THROW: {
       const RegType& res_type = work_line_->GetRegisterType(this, inst->VRegA_11x());
-      if (!reg_types_.JavaLangThrowable(false).IsAssignableFrom(res_type)) {
+      if (!reg_types_.JavaLangThrowable(false).IsAssignableFrom(res_type, this)) {
         if (res_type.IsUninitializedTypes()) {
           Fail(VERIFY_ERROR_BAD_CLASS_HARD) << "thrown exception not initialized";
         } else if (!res_type.IsReferenceTypes()) {
@@ -2639,7 +2641,8 @@
             cast_type.HasClass() &&             // Could be conflict type, make sure it has a class.
             !cast_type.GetClass()->IsInterface() &&
             (orig_type.IsZero() ||
-                orig_type.IsStrictlyAssignableFrom(cast_type.Merge(orig_type, &reg_types_)))) {
+                orig_type.IsStrictlyAssignableFrom(
+                    cast_type.Merge(orig_type, &reg_types_, this), this))) {
           RegisterLine* update_line = RegisterLine::Create(code_item_->registers_size_, this);
           if (inst->Opcode() == Instruction::IF_EQZ) {
             fallthrough_line.reset(update_line);
@@ -3636,8 +3639,13 @@
     return *result;
   }
   if (klass == nullptr && !result->IsUnresolvedTypes()) {
-    dex_cache_->SetResolvedType(class_idx, result->GetClass());
+    klass = result->GetClass();
+    dex_cache_->SetResolvedType(class_idx, klass);
   }
+
+  // Record result of class resolution attempt.
+  VerifierDeps::MaybeRecordClassResolution(*dex_file_, class_idx, klass);
+
   // Check if access is allowed. Unresolved types use xxxWithAccessCheck to
   // check at runtime if access is allowed and so pass here. If result is
   // primitive, skip the access check.
@@ -3664,7 +3672,7 @@
             common_super = &reg_types_.JavaLangThrowable(false);
           } else {
             const RegType& exception = ResolveClassAndCheckAccess(iterator.GetHandlerTypeIndex());
-            if (!reg_types_.JavaLangThrowable(false).IsAssignableFrom(exception)) {
+            if (!reg_types_.JavaLangThrowable(false).IsAssignableFrom(exception, this)) {
               DCHECK(!exception.IsUninitializedTypes());  // Comes from dex, shouldn't be uninit.
               if (exception.IsUnresolvedTypes()) {
                 // We don't know enough about the type. Fail here and let runtime handle it.
@@ -3679,9 +3687,10 @@
             } else if (common_super->Equals(exception)) {
               // odd case, but nothing to do
             } else {
-              common_super = &common_super->Merge(exception, &reg_types_);
+              common_super = &common_super->Merge(exception, &reg_types_, this);
               if (FailOrAbort(this,
-                              reg_types_.JavaLangThrowable(false).IsAssignableFrom(*common_super),
+                              reg_types_.JavaLangThrowable(false).IsAssignableFrom(
+                                  *common_super, this),
                               "java.lang.Throwable is not assignable-from common_super at ",
                               work_insn_idx_)) {
                 break;
@@ -3701,6 +3710,20 @@
   return *common_super;
 }
 
+inline static MethodResolutionKind GetMethodResolutionKind(
+    MethodType method_type, bool is_interface) {
+  if (method_type == METHOD_DIRECT || method_type == METHOD_STATIC) {
+    return kDirectMethodResolution;
+  } else if (method_type == METHOD_INTERFACE) {
+    return kInterfaceMethodResolution;
+  } else if (method_type == METHOD_SUPER && is_interface) {
+    return kInterfaceMethodResolution;
+  } else {
+    DCHECK(method_type == METHOD_VIRTUAL || method_type == METHOD_SUPER);
+    return kVirtualMethodResolution;
+  }
+}
+
 ArtMethod* MethodVerifier::ResolveMethodAndCheckAccess(
     uint32_t dex_method_idx, MethodType method_type) {
   const DexFile::MethodId& method_id = dex_file_->GetMethodId(dex_method_idx);
@@ -3718,6 +3741,7 @@
   const RegType& referrer = GetDeclaringClass();
   auto* cl = Runtime::Current()->GetClassLinker();
   auto pointer_size = cl->GetImagePointerSize();
+  MethodResolutionKind res_kind = GetMethodResolutionKind(method_type, klass->IsInterface());
 
   ArtMethod* res_method = dex_cache_->GetResolvedMethod(dex_method_idx, pointer_size);
   bool stash_method = false;
@@ -3725,35 +3749,44 @@
     const char* name = dex_file_->GetMethodName(method_id);
     const Signature signature = dex_file_->GetMethodSignature(method_id);
 
-    if (method_type == METHOD_DIRECT || method_type == METHOD_STATIC) {
+    if (res_kind == kDirectMethodResolution) {
       res_method = klass->FindDirectMethod(name, signature, pointer_size);
-    } else if (method_type == METHOD_INTERFACE) {
-      res_method = klass->FindInterfaceMethod(name, signature, pointer_size);
-    } else if (method_type == METHOD_SUPER && klass->IsInterface()) {
-      res_method = klass->FindInterfaceMethod(name, signature, pointer_size);
-    } else {
-      DCHECK(method_type == METHOD_VIRTUAL || method_type == METHOD_SUPER);
+    } else if (res_kind == kVirtualMethodResolution) {
       res_method = klass->FindVirtualMethod(name, signature, pointer_size);
+    } else {
+      DCHECK_EQ(res_kind, kInterfaceMethodResolution);
+      res_method = klass->FindInterfaceMethod(name, signature, pointer_size);
     }
+
     if (res_method != nullptr) {
       stash_method = true;
     } else {
       // If a virtual or interface method wasn't found with the expected type, look in
       // the direct methods. This can happen when the wrong invoke type is used or when
       // a class has changed, and will be flagged as an error in later checks.
-      if (method_type == METHOD_INTERFACE ||
-          method_type == METHOD_VIRTUAL ||
-          method_type == METHOD_SUPER) {
+      // Note that in this case, we do not put the resolved method in the Dex cache
+      // because it was not discovered using the expected type of method resolution.
+      if (res_kind != kDirectMethodResolution) {
+        // Record result of the initial resolution attempt.
+        VerifierDeps::MaybeRecordMethodResolution(*dex_file_, dex_method_idx, res_kind, nullptr);
+        // Change resolution type to 'direct' and try to resolve again.
+        res_kind = kDirectMethodResolution;
         res_method = klass->FindDirectMethod(name, signature, pointer_size);
       }
-      if (res_method == nullptr) {
-        Fail(VERIFY_ERROR_NO_METHOD) << "couldn't find method "
-                                     << PrettyDescriptor(klass) << "." << name
-                                     << " " << signature;
-        return nullptr;
-      }
     }
   }
+
+  // Record result of method resolution attempt.
+  VerifierDeps::MaybeRecordMethodResolution(*dex_file_, dex_method_idx, res_kind, res_method);
+
+  if (res_method == nullptr) {
+    Fail(VERIFY_ERROR_NO_METHOD) << "couldn't find method "
+                                 << PrettyDescriptor(klass) << "."
+                                 << dex_file_->GetMethodName(method_id) << " "
+                                 << dex_file_->GetMethodSignature(method_id);
+    return nullptr;
+  }
+
   // Make sure calls to constructors are "direct". There are additional restrictions but we don't
   // enforce them here.
   if (res_method->IsConstructor() && method_type != METHOD_DIRECT) {
@@ -3897,7 +3930,7 @@
             dex_file_->StringByTypeIdx(class_idx),
             false);
       }
-      if (!res_method_class->IsAssignableFrom(adjusted_type)) {
+      if (!res_method_class->IsAssignableFrom(adjusted_type, this)) {
         Fail(adjusted_type.IsUnresolvedTypes()
                  ? VERIFY_ERROR_NO_CLASS
                  : VERIFY_ERROR_BAD_CLASS_SOFT)
@@ -4029,12 +4062,15 @@
   // has a vtable entry for the target method. Or the target is on a interface.
   if (method_type == METHOD_SUPER) {
     uint16_t class_idx = dex_file_->GetMethodId(method_idx).class_idx_;
-    mirror::Class* reference_class = dex_cache_->GetResolvedType(class_idx);
-    if (reference_class == nullptr) {
+    const RegType& reference_type = reg_types_.FromDescriptor(
+        GetClassLoader(),
+        dex_file_->StringByTypeIdx(class_idx),
+        false);
+    if (reference_type.IsUnresolvedTypes()) {
       Fail(VERIFY_ERROR_BAD_CLASS_SOFT) << "Unable to find referenced class from invoke-super";
       return nullptr;
     }
-    if (reference_class->IsInterface()) {
+    if (reference_type.GetClass()->IsInterface()) {
       // TODO Can we verify anything else.
       if (class_idx == class_def_.class_idx_) {
         Fail(VERIFY_ERROR_CLASS_CHANGE) << "Cannot invoke-super on self as interface";
@@ -4046,12 +4082,12 @@
         Fail(VERIFY_ERROR_NO_CLASS) << "Unable to resolve the full class of 'this' used in an"
                                     << "interface invoke-super";
         return nullptr;
-      } else if (!reference_class->IsAssignableFrom(GetDeclaringClass().GetClass())) {
+      } else if (!reference_type.IsStrictlyAssignableFrom(GetDeclaringClass(), this)) {
         Fail(VERIFY_ERROR_CLASS_CHANGE)
             << "invoke-super in " << PrettyClass(GetDeclaringClass().GetClass()) << " in method "
             << PrettyMethod(dex_method_idx_, *dex_file_) << " to method "
             << PrettyMethod(method_idx, *dex_file_) << " references "
-            << "non-super-interface type " << PrettyClass(reference_class);
+            << "non-super-interface type " << PrettyClass(reference_type.GetClass());
         return nullptr;
       }
     } else {
@@ -4062,7 +4098,7 @@
                                     << " to super " << PrettyMethod(res_method);
         return nullptr;
       }
-      if (!reference_class->IsAssignableFrom(GetDeclaringClass().GetClass()) ||
+      if (!reference_type.IsStrictlyAssignableFrom(GetDeclaringClass(), this) ||
           (res_method->GetMethodIndex() >= super.GetClass()->GetVTableLength())) {
         Fail(VERIFY_ERROR_NO_METHOD) << "invalid invoke-super from "
                                     << PrettyMethod(dex_method_idx_, *dex_file_)
@@ -4177,7 +4213,7 @@
     std::string temp;
     const RegType& res_method_class =
         FromClass(klass->GetDescriptor(&temp), klass, klass->CannotBeAssignedFromOtherTypes());
-    if (!res_method_class.IsAssignableFrom(actual_arg_type)) {
+    if (!res_method_class.IsAssignableFrom(actual_arg_type, this)) {
       Fail(actual_arg_type.IsUninitializedTypes()    // Just overcautious - should have never
                ? VERIFY_ERROR_BAD_CLASS_HARD         // quickened this.
                : actual_arg_type.IsUnresolvedTypes()
@@ -4466,8 +4502,11 @@
     return nullptr;  // Can't resolve Class so no more to do here, will do checking at runtime.
   }
   ClassLinker* class_linker = Runtime::Current()->GetClassLinker();
-  ArtField* field = class_linker->ResolveFieldJLS(*dex_file_, field_idx, dex_cache_,
-                                                  class_loader_);
+  ArtField* field = class_linker->ResolveFieldJLS(*dex_file_, field_idx, dex_cache_, class_loader_);
+
+  // Record result of the field resolution attempt.
+  VerifierDeps::MaybeRecordFieldResolution(*dex_file_, field_idx, field);
+
   if (field == nullptr) {
     VLOG(verifier) << "Unable to resolve static field " << field_idx << " ("
               << dex_file_->GetFieldName(field_id) << ") in "
@@ -4501,8 +4540,11 @@
     return nullptr;  // Can't resolve Class so no more to do here
   }
   ClassLinker* class_linker = Runtime::Current()->GetClassLinker();
-  ArtField* field = class_linker->ResolveFieldJLS(*dex_file_, field_idx, dex_cache_,
-                                                  class_loader_);
+  ArtField* field = class_linker->ResolveFieldJLS(*dex_file_, field_idx, dex_cache_, class_loader_);
+
+  // Record result of the field resolution attempt.
+  VerifierDeps::MaybeRecordFieldResolution(*dex_file_, field_idx, field);
+
   if (field == nullptr) {
     VLOG(verifier) << "Unable to resolve instance field " << field_idx << " ("
               << dex_file_->GetFieldName(field_id) << ") in "
@@ -4536,7 +4578,7 @@
                                           << " of " << PrettyMethod(dex_method_idx_, *dex_file_);
         return nullptr;
       }
-    } else if (!field_klass.IsAssignableFrom(obj_type)) {
+    } else if (!field_klass.IsAssignableFrom(obj_type, this)) {
       // Trying to access C1.field1 using reference of type C2, which is neither C1 or a sub-class
       // of C1. For resolution to occur the declared class of the field must be compatible with
       // obj_type, we've discovered this wasn't so, so report the field didn't exist.
@@ -4643,7 +4685,7 @@
     if (is_primitive) {
       VerifyPrimitivePut(*field_type, insn_type, vregA);
     } else {
-      if (!insn_type.IsAssignableFrom(*field_type)) {
+      if (!insn_type.IsAssignableFrom(*field_type, this)) {
         // If the field type is not a reference, this is a global failure rather than
         // a class change failure as the instructions and the descriptors for the type
         // should have been consistent within the same file at compile time.
@@ -4675,7 +4717,7 @@
         return;
       }
     } else {
-      if (!insn_type.IsAssignableFrom(*field_type)) {
+      if (!insn_type.IsAssignableFrom(*field_type, this)) {
         // If the field type is not a reference, this is a global failure rather than
         // a class change failure as the instructions and the descriptors for the type
         // should have been consistent within the same file at compile time.
@@ -4806,7 +4848,7 @@
         return;
       }
     } else {
-      if (!insn_type.IsAssignableFrom(*field_type)) {
+      if (!insn_type.IsAssignableFrom(*field_type, this)) {
         Fail(VERIFY_ERROR_BAD_CLASS_SOFT) << "expected field " << PrettyField(field)
                                           << " to be compatible with type '" << insn_type
                                           << "' but found type '" << *field_type
@@ -4832,7 +4874,7 @@
         return;
       }
     } else {
-      if (!insn_type.IsAssignableFrom(*field_type)) {
+      if (!insn_type.IsAssignableFrom(*field_type, this)) {
         Fail(VERIFY_ERROR_BAD_CLASS_SOFT) << "expected field " << PrettyField(field)
                                           << " to be compatible with type '" << insn_type
                                           << "' but found type '" << *field_type
diff --git a/runtime/verifier/method_verifier.h b/runtime/verifier/method_verifier.h
index c4b1c6e..eb8b7a6 100644
--- a/runtime/verifier/method_verifier.h
+++ b/runtime/verifier/method_verifier.h
@@ -180,6 +180,11 @@
 
   uint8_t EncodePcToReferenceMapData() const;
 
+  const DexFile& GetDexFile() const {
+    DCHECK(dex_file_ != nullptr);
+    return *dex_file_;
+  }
+
   uint32_t DexFileVersion() const {
     return dex_file_->GetVersion();
   }
@@ -353,7 +358,8 @@
    *  (3) Iterate through the method, checking type safety and looking
    *      for code flow problems.
    */
-  static FailureData VerifyMethod(Thread* self, uint32_t method_idx,
+  static FailureData VerifyMethod(Thread* self,
+                                  uint32_t method_idx,
                                   const DexFile* dex_file,
                                   Handle<mirror::DexCache> dex_cache,
                                   Handle<mirror::ClassLoader> class_loader,
@@ -842,6 +848,7 @@
   MethodVerifier* link_;
 
   friend class art::Thread;
+  friend class VerifierDepsTest;
 
   DISALLOW_COPY_AND_ASSIGN(MethodVerifier);
 };
diff --git a/runtime/verifier/reg_type-inl.h b/runtime/verifier/reg_type-inl.h
index 861db3c..d93aaa1 100644
--- a/runtime/verifier/reg_type-inl.h
+++ b/runtime/verifier/reg_type-inl.h
@@ -22,6 +22,8 @@
 #include "base/casts.h"
 #include "base/scoped_arena_allocator.h"
 #include "mirror/class.h"
+#include "method_verifier.h"
+#include "verifier_deps.h"
 
 namespace art {
 namespace verifier {
@@ -62,7 +64,10 @@
   }
 }
 
-inline bool RegType::AssignableFrom(const RegType& lhs, const RegType& rhs, bool strict) {
+inline bool RegType::AssignableFrom(const RegType& lhs,
+                                    const RegType& rhs,
+                                    bool strict,
+                                    MethodVerifier* verifier) {
   if (lhs.Equals(rhs)) {
     return true;
   } else {
@@ -104,10 +109,15 @@
         return true;
       } else if (lhs.IsJavaLangObjectArray()) {
         return rhs.IsObjectArrayTypes();  // All reference arrays may be assigned to Object[]
-      } else if (lhs.HasClass() && rhs.HasClass() &&
-                 lhs.GetClass()->IsAssignableFrom(rhs.GetClass())) {
-        // We're assignable from the Class point-of-view.
-        return true;
+      } else if (lhs.HasClass() && rhs.HasClass()) {
+        // Test assignability from the Class point-of-view.
+        bool result = lhs.GetClass()->IsAssignableFrom(rhs.GetClass());
+        // Record assignability dependency. The `verifier` is null during unit tests.
+        if (verifier != nullptr) {
+          VerifierDeps::MaybeRecordAssignability(
+              verifier->GetDexFile(), lhs.GetClass(), rhs.GetClass(), strict, result);
+        }
+        return result;
       } else {
         // Unresolved types are only assignable for null and equality.
         return false;
@@ -116,12 +126,12 @@
   }
 }
 
-inline bool RegType::IsAssignableFrom(const RegType& src) const {
-  return AssignableFrom(*this, src, false);
+inline bool RegType::IsAssignableFrom(const RegType& src, MethodVerifier* verifier) const {
+  return AssignableFrom(*this, src, false, verifier);
 }
 
-inline bool RegType::IsStrictlyAssignableFrom(const RegType& src) const {
-  return AssignableFrom(*this, src, true);
+inline bool RegType::IsStrictlyAssignableFrom(const RegType& src, MethodVerifier* verifier) const {
+  return AssignableFrom(*this, src, true, verifier);
 }
 
 inline const DoubleHiType* DoubleHiType::GetInstance() {
diff --git a/runtime/verifier/reg_type.cc b/runtime/verifier/reg_type.cc
index 5c19969..3bc2acc 100644
--- a/runtime/verifier/reg_type.cc
+++ b/runtime/verifier/reg_type.cc
@@ -21,6 +21,7 @@
 #include "base/casts.h"
 #include "class_linker-inl.h"
 #include "dex_file-inl.h"
+#include "method_verifier.h"
 #include "mirror/class.h"
 #include "mirror/class-inl.h"
 #include "mirror/object-inl.h"
@@ -575,7 +576,9 @@
   return a.IsConstantTypes() ? b : a;
 }
 
-const RegType& RegType::Merge(const RegType& incoming_type, RegTypeCache* reg_types) const {
+const RegType& RegType::Merge(const RegType& incoming_type,
+                              RegTypeCache* reg_types,
+                              MethodVerifier* verifier) const {
   DCHECK(!Equals(incoming_type));  // Trivial equality handled by caller
   // Perform pointer equality tests for undefined and conflict to avoid virtual method dispatch.
   const UndefinedType& undefined = reg_types->Undefined();
@@ -696,13 +699,21 @@
       // have two sub-classes and don't know how to merge. Create a new string-based unresolved
       // type that reflects our lack of knowledge and that allows the rest of the unresolved
       // mechanics to continue.
-      return reg_types->FromUnresolvedMerge(*this, incoming_type);
+      return reg_types->FromUnresolvedMerge(*this, incoming_type, verifier);
     } else {  // Two reference types, compute Join
       mirror::Class* c1 = GetClass();
       mirror::Class* c2 = incoming_type.GetClass();
       DCHECK(c1 != nullptr && !c1->IsPrimitive());
       DCHECK(c2 != nullptr && !c2->IsPrimitive());
       mirror::Class* join_class = ClassJoin(c1, c2);
+      // Record the dependency that both `c1` and `c2` are assignable to `join_class`.
+      // The `verifier` is null during unit tests.
+      if (verifier != nullptr) {
+        VerifierDeps::MaybeRecordAssignability(
+            verifier->GetDexFile(), join_class, c1, true /* strict */, true /* is_assignable */);
+        VerifierDeps::MaybeRecordAssignability(
+            verifier->GetDexFile(), join_class, c2, true /* strict */, true /* is_assignable */);
+      }
       if (c1 == join_class && !IsPreciseReference()) {
         return *this;
       } else if (c2 == join_class && !incoming_type.IsPreciseReference()) {
@@ -873,8 +884,11 @@
   return os;
 }
 
-bool RegType::CanAssignArray(const RegType& src, RegTypeCache& reg_types,
-                             Handle<mirror::ClassLoader> class_loader, bool* soft_error) const {
+bool RegType::CanAssignArray(const RegType& src,
+                             RegTypeCache& reg_types,
+                             Handle<mirror::ClassLoader> class_loader,
+                             MethodVerifier* verifier,
+                             bool* soft_error) const {
   if (!IsArrayTypes() || !src.IsArrayTypes()) {
     *soft_error = false;
     return false;
@@ -891,7 +905,7 @@
   const RegType& cmp1 = reg_types.GetComponentType(*this, class_loader.Get());
   const RegType& cmp2 = reg_types.GetComponentType(src, class_loader.Get());
 
-  if (cmp1.IsAssignableFrom(cmp2)) {
+  if (cmp1.IsAssignableFrom(cmp2, verifier)) {
     return true;
   }
   if (cmp1.IsUnresolvedTypes()) {
@@ -914,7 +928,7 @@
     *soft_error = false;
     return false;
   }
-  return cmp1.CanAssignArray(cmp2, reg_types, class_loader, soft_error);
+  return cmp1.CanAssignArray(cmp2, reg_types, class_loader, verifier, soft_error);
 }
 
 
diff --git a/runtime/verifier/reg_type.h b/runtime/verifier/reg_type.h
index c3ed77a..9170bb1 100644
--- a/runtime/verifier/reg_type.h
+++ b/runtime/verifier/reg_type.h
@@ -43,7 +43,9 @@
 
 namespace verifier {
 
+class MethodVerifier;
 class RegTypeCache;
+
 /*
  * RegType holds information about the "type" of data held in a register.
  */
@@ -210,7 +212,7 @@
   // Note: Object and interface types may always be assigned to one another, see
   // comment on
   // ClassJoin.
-  bool IsAssignableFrom(const RegType& src) const
+  bool IsAssignableFrom(const RegType& src, MethodVerifier* verifier) const
       REQUIRES_SHARED(Locks::mutator_lock_);
 
   // Can this array type potentially be assigned by src.
@@ -220,14 +222,17 @@
   // will be set to true iff the assignment test failure should be treated as a soft-error, i.e.,
   // when both array types have the same 'depth' and the 'final' component types may be assignable
   // (both are reference types).
-  bool CanAssignArray(const RegType& src, RegTypeCache& reg_types,
-                      Handle<mirror::ClassLoader> class_loader, bool* soft_error) const
+  bool CanAssignArray(const RegType& src,
+                      RegTypeCache& reg_types,
+                      Handle<mirror::ClassLoader> class_loader,
+                      MethodVerifier* verifier,
+                      bool* soft_error) const
       REQUIRES_SHARED(Locks::mutator_lock_);
 
   // Can this type be assigned by src? Variant of IsAssignableFrom that doesn't
   // allow assignment to
   // an interface from an Object.
-  bool IsStrictlyAssignableFrom(const RegType& src) const
+  bool IsStrictlyAssignableFrom(const RegType& src, MethodVerifier* verifier) const
       REQUIRES_SHARED(Locks::mutator_lock_);
 
   // Are these RegTypes the same?
@@ -235,36 +240,21 @@
 
   // Compute the merge of this register from one edge (path) with incoming_type
   // from another.
-  const RegType& Merge(const RegType& incoming_type, RegTypeCache* reg_types) const
+  const RegType& Merge(const RegType& incoming_type,
+                       RegTypeCache* reg_types,
+                       MethodVerifier* verifier) const
       REQUIRES_SHARED(Locks::mutator_lock_);
   // Same as above, but also handles the case where incoming_type == this.
-  const RegType& SafeMerge(const RegType& incoming_type, RegTypeCache* reg_types) const
+  const RegType& SafeMerge(const RegType& incoming_type,
+                           RegTypeCache* reg_types,
+                           MethodVerifier* verifier) const
       REQUIRES_SHARED(Locks::mutator_lock_) {
     if (Equals(incoming_type)) {
       return *this;
     }
-    return Merge(incoming_type, reg_types);
+    return Merge(incoming_type, reg_types, verifier);
   }
 
-  /*
-   * A basic Join operation on classes. For a pair of types S and T the Join, written S v T = J, is
-   * S <: J, T <: J and for-all U such that S <: U, T <: U then J <: U. That is J is the parent of
-   * S and T such that there isn't a parent of both S and T that isn't also the parent of J (ie J
-   * is the deepest (lowest upper bound) parent of S and T).
-   *
-   * This operation applies for regular classes and arrays, however, for interface types there
-   * needn't be a partial ordering on the types. We could solve the problem of a lack of a partial
-   * order by introducing sets of types, however, the only operation permissible on an interface is
-   * invoke-interface. In the tradition of Java verifiers [1] we defer the verification of interface
-   * types until an invoke-interface call on the interface typed reference at runtime and allow
-   * the perversion of Object being assignable to an interface type (note, however, that we don't
-   * allow assignment of Object or Interface to any concrete class and are therefore type safe).
-   *
-   * [1] Java bytecode verification: algorithms and formalizations, Xavier Leroy
-   */
-  static mirror::Class* ClassJoin(mirror::Class* s, mirror::Class* t)
-      REQUIRES_SHARED(Locks::mutator_lock_);
-
   virtual ~RegType() {}
 
   void VisitRoots(RootVisitor* visitor, const RootInfo& root_info) const
@@ -298,7 +288,29 @@
   friend class RegTypeCache;
 
  private:
-  static bool AssignableFrom(const RegType& lhs, const RegType& rhs, bool strict)
+  /*
+   * A basic Join operation on classes. For a pair of types S and T the Join, written S v T = J, is
+   * S <: J, T <: J and for-all U such that S <: U, T <: U then J <: U. That is J is the parent of
+   * S and T such that there isn't a parent of both S and T that isn't also the parent of J (ie J
+   * is the deepest (lowest upper bound) parent of S and T).
+   *
+   * This operation applies for regular classes and arrays, however, for interface types there
+   * needn't be a partial ordering on the types. We could solve the problem of a lack of a partial
+   * order by introducing sets of types, however, the only operation permissible on an interface is
+   * invoke-interface. In the tradition of Java verifiers [1] we defer the verification of interface
+   * types until an invoke-interface call on the interface typed reference at runtime and allow
+   * the perversion of Object being assignable to an interface type (note, however, that we don't
+   * allow assignment of Object or Interface to any concrete class and are therefore type safe).
+   *
+   * [1] Java bytecode verification: algorithms and formalizations, Xavier Leroy
+   */
+  static mirror::Class* ClassJoin(mirror::Class* s, mirror::Class* t)
+      REQUIRES_SHARED(Locks::mutator_lock_);
+
+  static bool AssignableFrom(const RegType& lhs,
+                             const RegType& rhs,
+                             bool strict,
+                             MethodVerifier* verifier)
       REQUIRES_SHARED(Locks::mutator_lock_);
 
   DISALLOW_COPY_AND_ASSIGN(RegType);
diff --git a/runtime/verifier/reg_type_cache.cc b/runtime/verifier/reg_type_cache.cc
index 4d4886e..d0493e5 100644
--- a/runtime/verifier/reg_type_cache.cc
+++ b/runtime/verifier/reg_type_cache.cc
@@ -342,7 +342,9 @@
   }
 }
 
-const RegType& RegTypeCache::FromUnresolvedMerge(const RegType& left, const RegType& right) {
+const RegType& RegTypeCache::FromUnresolvedMerge(const RegType& left,
+                                                 const RegType& right,
+                                                 MethodVerifier* verifier) {
   ArenaBitVector types(&arena_,
                        kDefaultArenaBitVectorBytes * kBitsPerByte,  // Allocate at least 8 bytes.
                        true);                                       // Is expandable.
@@ -383,7 +385,7 @@
   }
 
   // Merge the resolved parts. Left and right might be equal, so use SafeMerge.
-  const RegType& resolved_parts_merged = left_resolved->SafeMerge(*right_resolved, this);
+  const RegType& resolved_parts_merged = left_resolved->SafeMerge(*right_resolved, this, verifier);
   // If we get a conflict here, the merge result is a conflict, not an unresolved merge type.
   if (resolved_parts_merged.IsConflict()) {
     return Conflict();
diff --git a/runtime/verifier/reg_type_cache.h b/runtime/verifier/reg_type_cache.h
index 14d9509..df0fe3d 100644
--- a/runtime/verifier/reg_type_cache.h
+++ b/runtime/verifier/reg_type_cache.h
@@ -75,7 +75,9 @@
       REQUIRES_SHARED(Locks::mutator_lock_);
   const RegType& FromDescriptor(mirror::ClassLoader* loader, const char* descriptor, bool precise)
       REQUIRES_SHARED(Locks::mutator_lock_);
-  const RegType& FromUnresolvedMerge(const RegType& left, const RegType& right)
+  const RegType& FromUnresolvedMerge(const RegType& left,
+                                     const RegType& right,
+                                     MethodVerifier* verifier)
       REQUIRES_SHARED(Locks::mutator_lock_);
   const RegType& FromUnresolvedSuperClass(const RegType& child)
       REQUIRES_SHARED(Locks::mutator_lock_);
diff --git a/runtime/verifier/reg_type_test.cc b/runtime/verifier/reg_type_test.cc
index 42a74f8..f2411b5 100644
--- a/runtime/verifier/reg_type_test.cc
+++ b/runtime/verifier/reg_type_test.cc
@@ -79,8 +79,8 @@
   EXPECT_FALSE(precise_lo.CheckWidePair(precise_const));
   EXPECT_TRUE(precise_lo.CheckWidePair(precise_hi));
   // Test Merging.
-  EXPECT_TRUE((long_lo.Merge(precise_lo, &cache)).IsLongTypes());
-  EXPECT_TRUE((long_hi.Merge(precise_hi, &cache)).IsLongHighTypes());
+  EXPECT_TRUE((long_lo.Merge(precise_lo, &cache, /* verifier */ nullptr)).IsLongTypes());
+  EXPECT_TRUE((long_hi.Merge(precise_hi, &cache, /* verifier */ nullptr)).IsLongHighTypes());
 }
 
 TEST_F(RegTypeTest, Primitives) {
@@ -427,7 +427,8 @@
   const RegType& resolved_ref = cache.JavaLangString();
   const RegType& resolved_unintialiesd = cache.Uninitialized(resolved_ref, 10);
   const RegType& unresolved_unintialized = cache.Uninitialized(unresolved_ref, 12);
-  const RegType& unresolved_merged = cache.FromUnresolvedMerge(unresolved_ref, unresolved_ref_another);
+  const RegType& unresolved_merged = cache.FromUnresolvedMerge(
+      unresolved_ref, unresolved_ref_another, /* verifier */ nullptr);
 
   std::string expected = "Unresolved Reference: java.lang.DoesNotExist";
   EXPECT_EQ(expected, unresolved_ref.Dump());
@@ -488,14 +489,14 @@
   RegTypeCache cache_new(true, allocator);
   const RegType& string = cache_new.JavaLangString();
   const RegType& Object = cache_new.JavaLangObject(true);
-  EXPECT_TRUE(string.Merge(Object, &cache_new).IsJavaLangObject());
+  EXPECT_TRUE(string.Merge(Object, &cache_new, /* verifier */ nullptr).IsJavaLangObject());
   // Merge two unresolved types.
   const RegType& ref_type_0 = cache_new.FromDescriptor(nullptr, "Ljava/lang/DoesNotExist;", true);
   EXPECT_TRUE(ref_type_0.IsUnresolvedReference());
   const RegType& ref_type_1 = cache_new.FromDescriptor(nullptr, "Ljava/lang/DoesNotExistToo;", true);
   EXPECT_FALSE(ref_type_0.Equals(ref_type_1));
 
-  const RegType& merged = ref_type_1.Merge(ref_type_0, &cache_new);
+  const RegType& merged = ref_type_1.Merge(ref_type_0, &cache_new, /* verifier */ nullptr);
   EXPECT_TRUE(merged.IsUnresolvedMergedReference());
   RegType& merged_nonconst = const_cast<RegType&>(merged);
 
@@ -518,22 +519,22 @@
   const RegType& imprecise_cst = cache_new.FromCat1Const(kTestConstantValue, false);
   {
     // float MERGE precise cst => float.
-    const RegType& merged = float_type.Merge(precise_cst, &cache_new);
+    const RegType& merged = float_type.Merge(precise_cst, &cache_new, /* verifier */ nullptr);
     EXPECT_TRUE(merged.IsFloat());
   }
   {
     // precise cst MERGE float => float.
-    const RegType& merged = precise_cst.Merge(float_type, &cache_new);
+    const RegType& merged = precise_cst.Merge(float_type, &cache_new, /* verifier */ nullptr);
     EXPECT_TRUE(merged.IsFloat());
   }
   {
     // float MERGE imprecise cst => float.
-    const RegType& merged = float_type.Merge(imprecise_cst, &cache_new);
+    const RegType& merged = float_type.Merge(imprecise_cst, &cache_new, /* verifier */ nullptr);
     EXPECT_TRUE(merged.IsFloat());
   }
   {
     // imprecise cst MERGE float => float.
-    const RegType& merged = imprecise_cst.Merge(float_type, &cache_new);
+    const RegType& merged = imprecise_cst.Merge(float_type, &cache_new, /* verifier */ nullptr);
     EXPECT_TRUE(merged.IsFloat());
   }
 }
@@ -554,42 +555,46 @@
   const RegType& imprecise_cst_hi = cache_new.FromCat2ConstHi(kTestConstantValue, false);
   {
     // lo MERGE precise cst lo => lo.
-    const RegType& merged = long_lo_type.Merge(precise_cst_lo, &cache_new);
+    const RegType& merged = long_lo_type.Merge(precise_cst_lo, &cache_new, /* verifier */ nullptr);
     EXPECT_TRUE(merged.IsLongLo());
   }
   {
     // precise cst lo MERGE lo => lo.
-    const RegType& merged = precise_cst_lo.Merge(long_lo_type, &cache_new);
+    const RegType& merged = precise_cst_lo.Merge(long_lo_type, &cache_new, /* verifier */ nullptr);
     EXPECT_TRUE(merged.IsLongLo());
   }
   {
     // lo MERGE imprecise cst lo => lo.
-    const RegType& merged = long_lo_type.Merge(imprecise_cst_lo, &cache_new);
+    const RegType& merged = long_lo_type.Merge(
+        imprecise_cst_lo, &cache_new, /* verifier */ nullptr);
     EXPECT_TRUE(merged.IsLongLo());
   }
   {
     // imprecise cst lo MERGE lo => lo.
-    const RegType& merged = imprecise_cst_lo.Merge(long_lo_type, &cache_new);
+    const RegType& merged = imprecise_cst_lo.Merge(
+        long_lo_type, &cache_new, /* verifier */ nullptr);
     EXPECT_TRUE(merged.IsLongLo());
   }
   {
     // hi MERGE precise cst hi => hi.
-    const RegType& merged = long_hi_type.Merge(precise_cst_hi, &cache_new);
+    const RegType& merged = long_hi_type.Merge(precise_cst_hi, &cache_new, /* verifier */ nullptr);
     EXPECT_TRUE(merged.IsLongHi());
   }
   {
     // precise cst hi MERGE hi => hi.
-    const RegType& merged = precise_cst_hi.Merge(long_hi_type, &cache_new);
+    const RegType& merged = precise_cst_hi.Merge(long_hi_type, &cache_new, /* verifier */ nullptr);
     EXPECT_TRUE(merged.IsLongHi());
   }
   {
     // hi MERGE imprecise cst hi => hi.
-    const RegType& merged = long_hi_type.Merge(imprecise_cst_hi, &cache_new);
+    const RegType& merged = long_hi_type.Merge(
+        imprecise_cst_hi, &cache_new, /* verifier */ nullptr);
     EXPECT_TRUE(merged.IsLongHi());
   }
   {
     // imprecise cst hi MERGE hi => hi.
-    const RegType& merged = imprecise_cst_hi.Merge(long_hi_type, &cache_new);
+    const RegType& merged = imprecise_cst_hi.Merge(
+        long_hi_type, &cache_new, /* verifier */ nullptr);
     EXPECT_TRUE(merged.IsLongHi());
   }
 }
@@ -610,42 +615,50 @@
   const RegType& imprecise_cst_hi = cache_new.FromCat2ConstHi(kTestConstantValue, false);
   {
     // lo MERGE precise cst lo => lo.
-    const RegType& merged = double_lo_type.Merge(precise_cst_lo, &cache_new);
+    const RegType& merged = double_lo_type.Merge(
+        precise_cst_lo, &cache_new, /* verifier */ nullptr);
     EXPECT_TRUE(merged.IsDoubleLo());
   }
   {
     // precise cst lo MERGE lo => lo.
-    const RegType& merged = precise_cst_lo.Merge(double_lo_type, &cache_new);
+    const RegType& merged = precise_cst_lo.Merge(
+        double_lo_type, &cache_new, /* verifier */ nullptr);
     EXPECT_TRUE(merged.IsDoubleLo());
   }
   {
     // lo MERGE imprecise cst lo => lo.
-    const RegType& merged = double_lo_type.Merge(imprecise_cst_lo, &cache_new);
+    const RegType& merged = double_lo_type.Merge(
+        imprecise_cst_lo, &cache_new, /* verifier */ nullptr);
     EXPECT_TRUE(merged.IsDoubleLo());
   }
   {
     // imprecise cst lo MERGE lo => lo.
-    const RegType& merged = imprecise_cst_lo.Merge(double_lo_type, &cache_new);
+    const RegType& merged = imprecise_cst_lo.Merge(
+        double_lo_type, &cache_new, /* verifier */ nullptr);
     EXPECT_TRUE(merged.IsDoubleLo());
   }
   {
     // hi MERGE precise cst hi => hi.
-    const RegType& merged = double_hi_type.Merge(precise_cst_hi, &cache_new);
+    const RegType& merged = double_hi_type.Merge(
+        precise_cst_hi, &cache_new, /* verifier */ nullptr);
     EXPECT_TRUE(merged.IsDoubleHi());
   }
   {
     // precise cst hi MERGE hi => hi.
-    const RegType& merged = precise_cst_hi.Merge(double_hi_type, &cache_new);
+    const RegType& merged = precise_cst_hi.Merge(
+        double_hi_type, &cache_new, /* verifier */ nullptr);
     EXPECT_TRUE(merged.IsDoubleHi());
   }
   {
     // hi MERGE imprecise cst hi => hi.
-    const RegType& merged = double_hi_type.Merge(imprecise_cst_hi, &cache_new);
+    const RegType& merged = double_hi_type.Merge(
+        imprecise_cst_hi, &cache_new, /* verifier */ nullptr);
     EXPECT_TRUE(merged.IsDoubleHi());
   }
   {
     // imprecise cst hi MERGE hi => hi.
-    const RegType& merged = imprecise_cst_hi.Merge(double_hi_type, &cache_new);
+    const RegType& merged = imprecise_cst_hi.Merge(
+        double_hi_type, &cache_new, /* verifier */ nullptr);
     EXPECT_TRUE(merged.IsDoubleHi());
   }
 }
diff --git a/runtime/verifier/register_line-inl.h b/runtime/verifier/register_line-inl.h
index d2f3485..3823143 100644
--- a/runtime/verifier/register_line-inl.h
+++ b/runtime/verifier/register_line-inl.h
@@ -131,7 +131,7 @@
                                              const RegType& check_type) {
   // Verify the src register type against the check type refining the type of the register
   const RegType& src_type = GetRegisterType(verifier, vsrc);
-  if (UNLIKELY(!check_type.IsAssignableFrom(src_type))) {
+  if (UNLIKELY(!check_type.IsAssignableFrom(src_type, verifier))) {
     enum VerifyError fail_type;
     if (!check_type.IsNonZeroReferenceTypes() || !src_type.IsNonZeroReferenceTypes()) {
       // Hard fail if one of the types is primitive, since they are concretely known.
diff --git a/runtime/verifier/register_line.cc b/runtime/verifier/register_line.cc
index 71aa94e..823336c 100644
--- a/runtime/verifier/register_line.cc
+++ b/runtime/verifier/register_line.cc
@@ -73,7 +73,7 @@
   DCHECK(check_type1.CheckWidePair(check_type2));
   // Verify the src register type against the check type refining the type of the register
   const RegType& src_type = GetRegisterType(verifier, vsrc);
-  if (!check_type1.IsAssignableFrom(src_type)) {
+  if (!check_type1.IsAssignableFrom(src_type, verifier)) {
     verifier->Fail(VERIFY_ERROR_BAD_CLASS_HARD) << "register v" << vsrc << " has type " << src_type
                                << " but expected " << check_type1;
     return false;
@@ -433,7 +433,8 @@
     if (line_[idx] != incoming_line->line_[idx]) {
       const RegType& incoming_reg_type = incoming_line->GetRegisterType(verifier, idx);
       const RegType& cur_type = GetRegisterType(verifier, idx);
-      const RegType& new_type = cur_type.Merge(incoming_reg_type, verifier->GetRegTypeCache());
+      const RegType& new_type = cur_type.Merge(
+          incoming_reg_type, verifier->GetRegTypeCache(), verifier);
       changed = changed || !cur_type.Equals(new_type);
       line_[idx] = new_type.GetId();
     }
diff --git a/runtime/verifier/verifier_deps.cc b/runtime/verifier/verifier_deps.cc
new file mode 100644
index 0000000..4953483
--- /dev/null
+++ b/runtime/verifier/verifier_deps.cc
@@ -0,0 +1,321 @@
+/*
+ * Copyright (C) 2016 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.
+ */
+
+#include "verifier_deps.h"
+
+#include "compiler_callbacks.h"
+#include "mirror/class-inl.h"
+#include "runtime.h"
+
+namespace art {
+namespace verifier {
+
+VerifierDeps::VerifierDeps(const std::vector<const DexFile*>& dex_files) {
+  MutexLock mu(Thread::Current(), *Locks::verifier_deps_lock_);
+  for (const DexFile* dex_file : dex_files) {
+    DCHECK(GetDexFileDeps(*dex_file) == nullptr);
+    std::unique_ptr<DexFileDeps> deps(new DexFileDeps());
+    dex_deps_.emplace(dex_file, std::move(deps));
+  }
+}
+
+VerifierDeps::DexFileDeps* VerifierDeps::GetDexFileDeps(const DexFile& dex_file) {
+  auto it = dex_deps_.find(&dex_file);
+  return (it == dex_deps_.end()) ? nullptr : it->second.get();
+}
+
+template <typename T>
+uint16_t VerifierDeps::GetAccessFlags(T* element) {
+  static_assert(kAccJavaFlagsMask == 0xFFFF, "Unexpected value of a constant");
+  if (element == nullptr) {
+    return VerifierDeps::kUnresolvedMarker;
+  } else {
+    uint16_t access_flags = Low16Bits(element->GetAccessFlags());
+    CHECK_NE(access_flags, VerifierDeps::kUnresolvedMarker);
+    return access_flags;
+  }
+}
+
+template <typename T>
+uint32_t VerifierDeps::GetDeclaringClassStringId(const DexFile& dex_file, T* element) {
+  static_assert(kAccJavaFlagsMask == 0xFFFF, "Unexpected value of a constant");
+  if (element == nullptr) {
+    return VerifierDeps::kUnresolvedMarker;
+  } else {
+    std::string temp;
+    uint32_t string_id = GetIdFromString(
+        dex_file, element->GetDeclaringClass()->GetDescriptor(&temp));
+    return string_id;
+  }
+}
+
+uint32_t VerifierDeps::GetIdFromString(const DexFile& dex_file, const std::string& str) {
+  const DexFile::StringId* string_id = dex_file.FindStringId(str.c_str());
+  if (string_id != nullptr) {
+    // String is in the DEX file. Return its ID.
+    return dex_file.GetIndexForStringId(*string_id);
+  }
+
+  // String is not in the DEX file. Assign a new ID to it which is higher than
+  // the number of strings in the DEX file.
+
+  DexFileDeps* deps = GetDexFileDeps(dex_file);
+  DCHECK(deps != nullptr);
+
+  uint32_t num_ids_in_dex = dex_file.NumStringIds();
+  uint32_t num_extra_ids = deps->strings_.size();
+
+  for (size_t i = 0; i < num_extra_ids; ++i) {
+    if (deps->strings_[i] == str) {
+      return num_ids_in_dex + i;
+    }
+  }
+
+  deps->strings_.push_back(str);
+
+  uint32_t new_id = num_ids_in_dex + num_extra_ids;
+  CHECK_GE(new_id, num_ids_in_dex);  // check for overflows
+  DCHECK_EQ(str, GetStringFromId(dex_file, new_id));
+
+  return new_id;
+}
+
+std::string VerifierDeps::GetStringFromId(const DexFile& dex_file, uint32_t string_id) {
+  uint32_t num_ids_in_dex = dex_file.NumStringIds();
+  if (string_id < num_ids_in_dex) {
+    return std::string(dex_file.StringDataByIdx(string_id));
+  } else {
+    DexFileDeps* deps = GetDexFileDeps(dex_file);
+    DCHECK(deps != nullptr);
+    string_id -= num_ids_in_dex;
+    CHECK_LT(string_id, deps->strings_.size());
+    return deps->strings_[string_id];
+  }
+}
+
+bool VerifierDeps::IsInClassPath(mirror::Class* klass) {
+  DCHECK(klass != nullptr);
+
+  mirror::DexCache* dex_cache = klass->GetDexCache();
+  if (dex_cache == nullptr) {
+    // This is a synthesized class, in this case always an array. They are not
+    // defined in the compiled DEX files and therefore are part of the classpath.
+    // We could avoid recording dependencies on arrays with component types in
+    // the compiled DEX files but we choose to record them anyway so as to
+    // record the access flags VM sets for array classes.
+    DCHECK(klass->IsArrayClass()) << PrettyDescriptor(klass);
+    return true;
+  }
+
+  const DexFile* dex_file = dex_cache->GetDexFile();
+  DCHECK(dex_file != nullptr);
+
+  // Test if the `dex_deps_` contains an entry for `dex_file`. If not, the dex
+  // file was not registered as being compiled and we assume `klass` is in the
+  // classpath.
+  return (GetDexFileDeps(*dex_file) == nullptr);
+}
+
+void VerifierDeps::AddClassResolution(const DexFile& dex_file,
+                                      uint16_t type_idx,
+                                      mirror::Class* klass) {
+  DexFileDeps* dex_deps = GetDexFileDeps(dex_file);
+  if (dex_deps == nullptr) {
+    // This invocation is from verification of a dex file which is not being compiled.
+    return;
+  }
+
+  if (klass != nullptr && !IsInClassPath(klass)) {
+    // Class resolved into one of the DEX files which are being compiled.
+    // This is not a classpath dependency.
+    return;
+  }
+
+  MutexLock mu(Thread::Current(), *Locks::verifier_deps_lock_);
+  dex_deps->classes_.emplace(ClassResolution(type_idx, GetAccessFlags(klass)));
+}
+
+void VerifierDeps::AddFieldResolution(const DexFile& dex_file,
+                                      uint32_t field_idx,
+                                      ArtField* field) {
+  DexFileDeps* dex_deps = GetDexFileDeps(dex_file);
+  if (dex_deps == nullptr) {
+    // This invocation is from verification of a dex file which is not being compiled.
+    return;
+  }
+
+  if (field != nullptr && !IsInClassPath(field->GetDeclaringClass())) {
+    // Field resolved into one of the DEX files which are being compiled.
+    // This is not a classpath dependency.
+    return;
+  }
+
+  MutexLock mu(Thread::Current(), *Locks::verifier_deps_lock_);
+  dex_deps->fields_.emplace(FieldResolution(
+      field_idx, GetAccessFlags(field), GetDeclaringClassStringId(dex_file, field)));
+}
+
+void VerifierDeps::AddMethodResolution(const DexFile& dex_file,
+                                       uint32_t method_idx,
+                                       MethodResolutionKind resolution_kind,
+                                       ArtMethod* method) {
+  DexFileDeps* dex_deps = GetDexFileDeps(dex_file);
+  if (dex_deps == nullptr) {
+    // This invocation is from verification of a dex file which is not being compiled.
+    return;
+  }
+
+  if (method != nullptr && !IsInClassPath(method->GetDeclaringClass())) {
+    // Method resolved into one of the DEX files which are being compiled.
+    // This is not a classpath dependency.
+    return;
+  }
+
+  MutexLock mu(Thread::Current(), *Locks::verifier_deps_lock_);
+  MethodResolution method_tuple(method_idx,
+                                GetAccessFlags(method),
+                                GetDeclaringClassStringId(dex_file, method));
+  if (resolution_kind == kDirectMethodResolution) {
+    dex_deps->direct_methods_.emplace(method_tuple);
+  } else if (resolution_kind == kVirtualMethodResolution) {
+    dex_deps->virtual_methods_.emplace(method_tuple);
+  } else {
+    DCHECK_EQ(resolution_kind, kInterfaceMethodResolution);
+    dex_deps->interface_methods_.emplace(method_tuple);
+  }
+}
+
+void VerifierDeps::AddAssignability(const DexFile& dex_file,
+                                    mirror::Class* destination,
+                                    mirror::Class* source,
+                                    bool is_strict,
+                                    bool is_assignable) {
+  // Test that the method is only called on reference types.
+  // Note that concurrent verification of `destination` and `source` may have
+  // set their status to erroneous. However, the tests performed below rely
+  // merely on no issues with linking (valid access flags, superclass and
+  // implemented interfaces). If the class at any point reached the IsResolved
+  // status, the requirement holds. This is guaranteed by RegTypeCache::ResolveClass.
+  DCHECK(destination != nullptr && !destination->IsPrimitive());
+  DCHECK(source != nullptr && !source->IsPrimitive());
+
+  if (destination == source ||
+      destination->IsObjectClass() ||
+      (!is_strict && destination->IsInterface())) {
+    // Cases when `destination` is trivially assignable from `source`.
+    DCHECK(is_assignable);
+    return;
+  }
+
+  DCHECK_EQ(is_assignable, destination->IsAssignableFrom(source));
+
+  if (destination->IsArrayClass() && source->IsArrayClass()) {
+    // Both types are arrays. Break down to component types and add recursively.
+    // This helps filter out destinations from compiled DEX files (see below)
+    // and deduplicate entries with the same canonical component type.
+    mirror::Class* destination_component = destination->GetComponentType();
+    mirror::Class* source_component = source->GetComponentType();
+
+    // Only perform the optimization if both types are resolved which guarantees
+    // that they linked successfully, as required at the top of this method.
+    if (destination_component->IsResolved() && source_component->IsResolved()) {
+      AddAssignability(dex_file,
+                       destination_component,
+                       source_component,
+                       /* is_strict */ true,
+                       is_assignable);
+      return;
+    }
+  }
+
+  DexFileDeps* dex_deps = GetDexFileDeps(dex_file);
+  if (dex_deps == nullptr) {
+    // This invocation is from verification of a DEX file which is not being compiled.
+    return;
+  }
+
+  if (!IsInClassPath(destination) && !IsInClassPath(source)) {
+    // Both `destination` and `source` are defined in the compiled DEX files.
+    // No need to record a dependency.
+    return;
+  }
+
+  MutexLock mu(Thread::Current(), *Locks::verifier_deps_lock_);
+
+  // Get string IDs for both descriptors and store in the appropriate set.
+
+  std::string temp1, temp2;
+  std::string destination_desc(destination->GetDescriptor(&temp1));
+  std::string source_desc(source->GetDescriptor(&temp2));
+  uint32_t destination_id = GetIdFromString(dex_file, destination_desc);
+  uint32_t source_id = GetIdFromString(dex_file, source_desc);
+
+  if (is_assignable) {
+    dex_deps->assignable_types_.emplace(TypeAssignability(destination_id, source_id));
+  } else {
+    dex_deps->unassignable_types_.emplace(TypeAssignability(destination_id, source_id));
+  }
+}
+
+static inline VerifierDeps* GetVerifierDepsSingleton() {
+  CompilerCallbacks* callbacks = Runtime::Current()->GetCompilerCallbacks();
+  if (callbacks == nullptr) {
+    return nullptr;
+  }
+  return callbacks->GetVerifierDeps();
+}
+
+void VerifierDeps::MaybeRecordClassResolution(const DexFile& dex_file,
+                                              uint16_t type_idx,
+                                              mirror::Class* klass) {
+  VerifierDeps* singleton = GetVerifierDepsSingleton();
+  if (singleton != nullptr) {
+    singleton->AddClassResolution(dex_file, type_idx, klass);
+  }
+}
+
+void VerifierDeps::MaybeRecordFieldResolution(const DexFile& dex_file,
+                                              uint32_t field_idx,
+                                              ArtField* field) {
+  VerifierDeps* singleton = GetVerifierDepsSingleton();
+  if (singleton != nullptr) {
+    singleton->AddFieldResolution(dex_file, field_idx, field);
+  }
+}
+
+void VerifierDeps::MaybeRecordMethodResolution(const DexFile& dex_file,
+                                               uint32_t method_idx,
+                                               MethodResolutionKind resolution_kind,
+                                               ArtMethod* method) {
+  VerifierDeps* singleton = GetVerifierDepsSingleton();
+  if (singleton != nullptr) {
+    singleton->AddMethodResolution(dex_file, method_idx, resolution_kind, method);
+  }
+}
+
+void VerifierDeps::MaybeRecordAssignability(const DexFile& dex_file,
+                                            mirror::Class* destination,
+                                            mirror::Class* source,
+                                            bool is_strict,
+                                            bool is_assignable) {
+  VerifierDeps* singleton = GetVerifierDepsSingleton();
+  if (singleton != nullptr) {
+    singleton->AddAssignability(dex_file, destination, source, is_strict, is_assignable);
+  }
+}
+
+}  // namespace verifier
+}  // namespace art
diff --git a/runtime/verifier/verifier_deps.h b/runtime/verifier/verifier_deps.h
new file mode 100644
index 0000000..da63d67
--- /dev/null
+++ b/runtime/verifier/verifier_deps.h
@@ -0,0 +1,229 @@
+/*
+ * Copyright (C) 2016 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.
+ */
+
+#ifndef ART_RUNTIME_VERIFIER_VERIFIER_DEPS_H_
+#define ART_RUNTIME_VERIFIER_VERIFIER_DEPS_H_
+
+#include <map>
+#include <set>
+#include <vector>
+
+#include "art_field.h"
+#include "art_method.h"
+#include "base/mutex.h"
+#include "method_resolution_kind.h"
+#include "os.h"
+
+namespace art {
+namespace verifier {
+
+// Verification dependencies collector class used by the MethodVerifier to record
+// resolution outcomes and type assignability tests of classes/methods/fields
+// not present in the set of compiled DEX files, that is classes/methods/fields
+// defined in the classpath.
+// The compilation driver initializes the class and registers all DEX files
+// which are being compiled. Classes defined in DEX files outside of this set
+// (or synthesized classes without associated DEX files) are considered being
+// in the classpath.
+// During code-flow verification, the MethodVerifier informs the VerifierDeps
+// singleton about the outcome of every resolution and assignability test, and
+// the singleton records them if their outcome may change with changes in the
+// classpath.
+class VerifierDeps {
+ public:
+  explicit VerifierDeps(const std::vector<const DexFile*>& dex_files)
+      REQUIRES(!Locks::verifier_deps_lock_);
+
+  // Record the outcome `klass` of resolving type `type_idx` from `dex_file`.
+  // If `klass` is null, the class is assumed unresolved.
+  static void MaybeRecordClassResolution(const DexFile& dex_file,
+                                         uint16_t type_idx,
+                                         mirror::Class* klass)
+      REQUIRES_SHARED(Locks::mutator_lock_)
+      REQUIRES(!Locks::verifier_deps_lock_);
+
+  // Record the outcome `field` of resolving field `field_idx` from `dex_file`.
+  // If `field` is null, the field is assumed unresolved.
+  static void MaybeRecordFieldResolution(const DexFile& dex_file,
+                                         uint32_t field_idx,
+                                         ArtField* field)
+      REQUIRES_SHARED(Locks::mutator_lock_)
+      REQUIRES(!Locks::verifier_deps_lock_);
+
+  // Record the outcome `method` of resolving method `method_idx` from `dex_file`
+  // using `res_kind` kind of method resolution algorithm. If `method` is null,
+  // the method is assumed unresolved.
+  static void MaybeRecordMethodResolution(const DexFile& dex_file,
+                                          uint32_t method_idx,
+                                          MethodResolutionKind res_kind,
+                                          ArtMethod* method)
+      REQUIRES_SHARED(Locks::mutator_lock_)
+      REQUIRES(!Locks::verifier_deps_lock_);
+
+  // Record the outcome `is_assignable` of type assignability test from `source`
+  // to `destination` as defined by RegType::AssignableFrom. `dex_file` is the
+  // owner of the method for which MethodVerifier performed the assignability test.
+  static void MaybeRecordAssignability(const DexFile& dex_file,
+                                       mirror::Class* destination,
+                                       mirror::Class* source,
+                                       bool is_strict,
+                                       bool is_assignable)
+      REQUIRES_SHARED(Locks::mutator_lock_)
+      REQUIRES(!Locks::verifier_deps_lock_);
+
+ private:
+  static constexpr uint16_t kUnresolvedMarker = static_cast<uint16_t>(-1);
+
+  using ClassResolutionBase = std::tuple<uint32_t, uint16_t>;
+  struct ClassResolution : public ClassResolutionBase {
+    ClassResolution(uint32_t type_idx, uint16_t access_flags)
+        : ClassResolutionBase(type_idx, access_flags) {}
+    ClassResolution(const ClassResolution&) = default;
+
+    bool IsResolved() const { return GetAccessFlags() != kUnresolvedMarker; }
+    uint32_t GetDexTypeIndex() const { return std::get<0>(*this); }
+    uint16_t GetAccessFlags() const { return std::get<1>(*this); }
+  };
+
+  using FieldResolutionBase = std::tuple<uint32_t, uint16_t, uint32_t>;
+  struct FieldResolution : public FieldResolutionBase {
+    FieldResolution(uint32_t field_idx, uint16_t access_flags, uint32_t declaring_class_idx)
+        : FieldResolutionBase(field_idx, access_flags, declaring_class_idx) {}
+    FieldResolution(const FieldResolution&) = default;
+
+    bool IsResolved() const { return GetAccessFlags() != kUnresolvedMarker; }
+    uint32_t GetDexFieldIndex() const { return std::get<0>(*this); }
+    uint16_t GetAccessFlags() const { return std::get<1>(*this); }
+    uint32_t GetDeclaringClassIndex() const { return std::get<2>(*this); }
+  };
+
+  using MethodResolutionBase = std::tuple<uint32_t, uint16_t, uint32_t>;
+  struct MethodResolution : public MethodResolutionBase {
+    MethodResolution(uint32_t method_idx, uint16_t access_flags, uint32_t declaring_class_idx)
+        : MethodResolutionBase(method_idx, access_flags, declaring_class_idx) {}
+    MethodResolution(const MethodResolution&) = default;
+
+    bool IsResolved() const { return GetAccessFlags() != kUnresolvedMarker; }
+    uint32_t GetDexMethodIndex() const { return std::get<0>(*this); }
+    uint16_t GetAccessFlags() const { return std::get<1>(*this); }
+    uint32_t GetDeclaringClassIndex() const { return std::get<2>(*this); }
+  };
+
+  using TypeAssignabilityBase = std::tuple<uint32_t, uint32_t>;
+  struct TypeAssignability : public std::tuple<uint32_t, uint32_t> {
+    TypeAssignability(uint32_t destination_idx, uint32_t source_idx)
+        : TypeAssignabilityBase(destination_idx, source_idx) {}
+    TypeAssignability(const TypeAssignability&) = default;
+
+    uint32_t GetDestination() const { return std::get<0>(*this); }
+    uint32_t GetSource() const { return std::get<1>(*this); }
+  };
+
+  // Data structure representing dependencies collected during verification of
+  // methods inside one DexFile.
+  struct DexFileDeps {
+    // Vector of strings which are not present in the corresponding DEX file.
+    // These are referred to with ids starting with `NumStringIds()` of that DexFile.
+    std::vector<std::string> strings_;
+
+    // Set of class pairs recording the outcome of assignability test from one
+    // of the two types to the other.
+    std::set<TypeAssignability> assignable_types_;
+    std::set<TypeAssignability> unassignable_types_;
+
+    // Sets of recorded class/field/method resolutions.
+    std::set<ClassResolution> classes_;
+    std::set<FieldResolution> fields_;
+    std::set<MethodResolution> direct_methods_;
+    std::set<MethodResolution> virtual_methods_;
+    std::set<MethodResolution> interface_methods_;
+  };
+
+  // Finds the DexFileDep instance associated with `dex_file`, or nullptr if
+  // `dex_file` is not reported as being compiled.
+  // We disable thread safety analysis. The method only reads the key set of
+  // `dex_deps_` which stays constant after initialization.
+  DexFileDeps* GetDexFileDeps(const DexFile& dex_file)
+      NO_THREAD_SAFETY_ANALYSIS;
+
+  // Returns true if `klass` is null or not defined in any of dex files which
+  // were reported as being compiled.
+  bool IsInClassPath(mirror::Class* klass)
+      REQUIRES_SHARED(Locks::mutator_lock_);
+
+  // Returns the index of `str`. If it is defined in `dex_file_`, this is the dex
+  // string ID. If not, an ID is assigned to the string and cached in `strings_`
+  // of the corresponding DexFileDeps structure (either provided or inferred from
+  // `dex_file`).
+  uint32_t GetIdFromString(const DexFile& dex_file, const std::string& str)
+      REQUIRES(Locks::verifier_deps_lock_);
+
+  // Returns the string represented by `id`.
+  std::string GetStringFromId(const DexFile& dex_file, uint32_t string_id)
+      REQUIRES(Locks::verifier_deps_lock_);
+
+  // Returns the bytecode access flags of `element` (bottom 16 bits), or
+  // `kUnresolvedMarker` if `element` is null.
+  template <typename T>
+  uint16_t GetAccessFlags(T* element)
+      REQUIRES_SHARED(Locks::mutator_lock_);
+
+  // Returns a string ID of the descriptor of the declaring class of `element`,
+  // or `kUnresolvedMarker` if `element` is null.
+  template <typename T>
+  uint32_t GetDeclaringClassStringId(const DexFile& dex_file, T* element)
+      REQUIRES_SHARED(Locks::mutator_lock_)
+      REQUIRES(Locks::verifier_deps_lock_);
+
+  void AddClassResolution(const DexFile& dex_file,
+                          uint16_t type_idx,
+                          mirror::Class* klass)
+      REQUIRES_SHARED(Locks::mutator_lock_)
+      REQUIRES(!Locks::verifier_deps_lock_);
+
+  void AddFieldResolution(const DexFile& dex_file,
+                          uint32_t field_idx,
+                          ArtField* field)
+      REQUIRES_SHARED(Locks::mutator_lock_)
+      REQUIRES(!Locks::verifier_deps_lock_);
+
+  void AddMethodResolution(const DexFile& dex_file,
+                           uint32_t method_idx,
+                           MethodResolutionKind res_kind,
+                           ArtMethod* method)
+      REQUIRES_SHARED(Locks::mutator_lock_)
+      REQUIRES(!Locks::verifier_deps_lock_);
+
+  void AddAssignability(const DexFile& dex_file,
+                        mirror::Class* destination,
+                        mirror::Class* source,
+                        bool is_strict,
+                        bool is_assignable)
+      REQUIRES_SHARED(Locks::mutator_lock_)
+      REQUIRES(!Locks::verifier_deps_lock_);
+
+  // Map from DexFiles into dependencies collected from verification of their methods.
+  std::map<const DexFile*, std::unique_ptr<DexFileDeps>> dex_deps_
+      GUARDED_BY(Locks::verifier_deps_lock_);
+
+  friend class VerifierDepsTest;
+  ART_FRIEND_TEST(VerifierDepsTest, StringToId);
+};
+
+}  // namespace verifier
+}  // namespace art
+
+#endif  // ART_RUNTIME_VERIFIER_VERIFIER_DEPS_H_
diff --git a/runtime/verifier/verifier_deps_test.cc b/runtime/verifier/verifier_deps_test.cc
new file mode 100644
index 0000000..41a9ad3
--- /dev/null
+++ b/runtime/verifier/verifier_deps_test.cc
@@ -0,0 +1,986 @@
+/*
+ * Copyright (C) 2016 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.
+ */
+
+#include "verifier_deps.h"
+
+#include "class_linker.h"
+#include "common_runtime_test.h"
+#include "compiler_callbacks.h"
+#include "dex_file.h"
+#include "handle_scope-inl.h"
+#include "method_verifier-inl.h"
+#include "mirror/class_loader.h"
+#include "runtime.h"
+#include "thread.h"
+#include "scoped_thread_state_change.h"
+
+namespace art {
+namespace verifier {
+
+class VerifierDepsCompilerCallbacks : public CompilerCallbacks {
+ public:
+  explicit VerifierDepsCompilerCallbacks()
+      : CompilerCallbacks(CompilerCallbacks::CallbackMode::kCompileApp),
+        deps_(nullptr) {}
+
+  void MethodVerified(verifier::MethodVerifier* verifier ATTRIBUTE_UNUSED) OVERRIDE {}
+  void ClassRejected(ClassReference ref ATTRIBUTE_UNUSED) OVERRIDE {}
+  bool IsRelocationPossible() OVERRIDE { return false; }
+
+  verifier::VerifierDeps* GetVerifierDeps() const OVERRIDE { return deps_; }
+  void SetVerifierDeps(verifier::VerifierDeps* deps) { deps_ = deps; }
+
+ private:
+  verifier::VerifierDeps* deps_;
+};
+
+class VerifierDepsTest : public CommonRuntimeTest {
+ public:
+  void SetUpRuntimeOptions(RuntimeOptions* options) {
+    CommonRuntimeTest::SetUpRuntimeOptions(options);
+    callbacks_.reset(new VerifierDepsCompilerCallbacks());
+  }
+
+  mirror::Class* FindClassByName(const std::string& name, ScopedObjectAccess* soa)
+      REQUIRES_SHARED(Locks::mutator_lock_) {
+    StackHandleScope<1> hs(Thread::Current());
+    Handle<mirror::ClassLoader> class_loader_handle(
+        hs.NewHandle(soa->Decode<mirror::ClassLoader*>(class_loader_)));
+    mirror::Class* result = class_linker_->FindClass(Thread::Current(),
+                                                     name.c_str(),
+                                                     class_loader_handle);
+    DCHECK(result != nullptr) << name;
+    return result;
+  }
+
+  void LoadDexFile(ScopedObjectAccess* soa) REQUIRES_SHARED(Locks::mutator_lock_) {
+    class_loader_ = LoadDex("VerifierDeps");
+    std::vector<const DexFile*> dex_files = GetDexFiles(class_loader_);
+    CHECK_EQ(dex_files.size(), 1u);
+    dex_file_ = dex_files.front();
+
+    mirror::ClassLoader* loader = soa->Decode<mirror::ClassLoader*>(class_loader_);
+    class_linker_->RegisterDexFile(*dex_file_, loader);
+
+    klass_Main_ = FindClassByName("LMain;", soa);
+    CHECK(klass_Main_ != nullptr);
+
+    verifier_deps_.reset(new verifier::VerifierDeps(dex_files));
+    VerifierDepsCompilerCallbacks* callbacks =
+        reinterpret_cast<VerifierDepsCompilerCallbacks*>(callbacks_.get());
+    callbacks->SetVerifierDeps(verifier_deps_.get());
+  }
+
+  bool VerifyMethod(const std::string& method_name) {
+    ScopedObjectAccess soa(Thread::Current());
+    LoadDexFile(&soa);
+
+    StackHandleScope<2> hs(Thread::Current());
+    Handle<mirror::ClassLoader> class_loader_handle(
+        hs.NewHandle(soa.Decode<mirror::ClassLoader*>(class_loader_)));
+    Handle<mirror::DexCache> dex_cache_handle(hs.NewHandle(klass_Main_->GetDexCache()));
+
+    const DexFile::ClassDef* class_def = klass_Main_->GetClassDef();
+    const uint8_t* class_data = dex_file_->GetClassData(*class_def);
+    CHECK(class_data != nullptr);
+
+    ClassDataItemIterator it(*dex_file_, class_data);
+    while (it.HasNextStaticField() || it.HasNextInstanceField()) {
+      it.Next();
+    }
+
+    ArtMethod* method = nullptr;
+    while (it.HasNextDirectMethod()) {
+      ArtMethod* resolved_method = class_linker_->ResolveMethod<ClassLinker::kNoICCECheckForCache>(
+          *dex_file_,
+          it.GetMemberIndex(),
+          dex_cache_handle,
+          class_loader_handle,
+          nullptr,
+          it.GetMethodInvokeType(*class_def));
+      CHECK(resolved_method != nullptr);
+      if (method_name == resolved_method->GetName()) {
+        method = resolved_method;
+        break;
+      }
+      it.Next();
+    }
+    CHECK(method != nullptr);
+
+    MethodVerifier verifier(Thread::Current(),
+                            dex_file_,
+                            dex_cache_handle,
+                            class_loader_handle,
+                            *class_def,
+                            it.GetMethodCodeItem(),
+                            it.GetMemberIndex(),
+                            method,
+                            it.GetMethodAccessFlags(),
+                            true /* can_load_classes */,
+                            true /* allow_soft_failures */,
+                            true /* need_precise_constants */,
+                            false /* verify to dump */,
+                            true /* allow_thread_suspension */);
+    verifier.Verify();
+    return !verifier.HasFailures();
+  }
+
+  bool TestAssignabilityRecording(const std::string& dst,
+                                  const std::string& src,
+                                  bool is_strict,
+                                  bool is_assignable) {
+    ScopedObjectAccess soa(Thread::Current());
+    LoadDexFile(&soa);
+    verifier_deps_->AddAssignability(*dex_file_,
+                                     FindClassByName(dst, &soa),
+                                     FindClassByName(src, &soa),
+                                     is_strict,
+                                     is_assignable);
+    return true;
+  }
+
+  // Iterates over all assignability records and tries to find an entry which
+  // matches the expected destination/source pair.
+  bool HasAssignable(const std::string& expected_destination,
+                     const std::string& expected_source,
+                     bool expected_is_assignable) {
+    MutexLock mu(Thread::Current(), *Locks::verifier_deps_lock_);
+    for (auto& dex_dep : verifier_deps_->dex_deps_) {
+      const DexFile& dex_file = *dex_dep.first;
+      auto& storage = expected_is_assignable ? dex_dep.second->assignable_types_
+                                             : dex_dep.second->unassignable_types_;
+      for (auto& entry : storage) {
+        std::string actual_destination =
+            verifier_deps_->GetStringFromId(dex_file, entry.GetDestination());
+        std::string actual_source = verifier_deps_->GetStringFromId(dex_file, entry.GetSource());
+        if ((expected_destination == actual_destination) && (expected_source == actual_source)) {
+          return true;
+        }
+      }
+    }
+    return false;
+  }
+
+  // Iterates over all class resolution records, finds an entry which matches
+  // the given class descriptor and tests its properties.
+  bool HasClass(const std::string& expected_klass,
+                bool expected_resolved,
+                const std::string& expected_access_flags = "") {
+    MutexLock mu(Thread::Current(), *Locks::verifier_deps_lock_);
+    for (auto& dex_dep : verifier_deps_->dex_deps_) {
+      for (auto& entry : dex_dep.second->classes_) {
+        if (expected_resolved != entry.IsResolved()) {
+          continue;
+        }
+
+        std::string actual_klass = dex_dep.first->StringByTypeIdx(entry.GetDexTypeIndex());
+        if (expected_klass != actual_klass) {
+          continue;
+        }
+
+        if (expected_resolved) {
+          // Test access flags. Note that PrettyJavaAccessFlags always appends
+          // a space after the modifiers. Add it to the expected access flags.
+          std::string actual_access_flags = PrettyJavaAccessFlags(entry.GetAccessFlags());
+          if (expected_access_flags + " " != actual_access_flags) {
+            continue;
+          }
+        }
+
+        return true;
+      }
+    }
+    return false;
+  }
+
+  // Iterates over all field resolution records, finds an entry which matches
+  // the given field class+name+type and tests its properties.
+  bool HasField(const std::string& expected_klass,
+                const std::string& expected_name,
+                const std::string& expected_type,
+                bool expected_resolved,
+                const std::string& expected_access_flags = "",
+                const std::string& expected_decl_klass = "") {
+    MutexLock mu(Thread::Current(), *Locks::verifier_deps_lock_);
+    for (auto& dex_dep : verifier_deps_->dex_deps_) {
+      for (auto& entry : dex_dep.second->fields_) {
+        if (expected_resolved != entry.IsResolved()) {
+          continue;
+        }
+
+        const DexFile::FieldId& field_id = dex_dep.first->GetFieldId(entry.GetDexFieldIndex());
+
+        std::string actual_klass = dex_dep.first->StringByTypeIdx(field_id.class_idx_);
+        if (expected_klass != actual_klass) {
+          continue;
+        }
+
+        std::string actual_name = dex_dep.first->StringDataByIdx(field_id.name_idx_);
+        if (expected_name != actual_name) {
+          continue;
+        }
+
+        std::string actual_type = dex_dep.first->StringByTypeIdx(field_id.type_idx_);
+        if (expected_type != actual_type) {
+          continue;
+        }
+
+        if (expected_resolved) {
+          // Test access flags. Note that PrettyJavaAccessFlags always appends
+          // a space after the modifiers. Add it to the expected access flags.
+          std::string actual_access_flags = PrettyJavaAccessFlags(entry.GetAccessFlags());
+          if (expected_access_flags + " " != actual_access_flags) {
+            continue;
+          }
+
+          std::string actual_decl_klass = verifier_deps_->GetStringFromId(
+              *dex_dep.first, entry.GetDeclaringClassIndex());
+          if (expected_decl_klass != actual_decl_klass) {
+            continue;
+          }
+        }
+
+        return true;
+      }
+    }
+    return false;
+  }
+
+  // Iterates over all method resolution records, finds an entry which matches
+  // the given field kind+class+name+signature and tests its properties.
+  bool HasMethod(const std::string& expected_kind,
+                 const std::string& expected_klass,
+                 const std::string& expected_name,
+                 const std::string& expected_signature,
+                 bool expected_resolved,
+                 const std::string& expected_access_flags = "",
+                 const std::string& expected_decl_klass = "") {
+    MutexLock mu(Thread::Current(), *Locks::verifier_deps_lock_);
+    for (auto& dex_dep : verifier_deps_->dex_deps_) {
+      auto& storage = (expected_kind == "direct") ? dex_dep.second->direct_methods_
+                          : (expected_kind == "virtual") ? dex_dep.second->virtual_methods_
+                              : dex_dep.second->interface_methods_;
+      for (auto& entry : storage) {
+        if (expected_resolved != entry.IsResolved()) {
+          continue;
+        }
+
+        const DexFile::MethodId& method_id = dex_dep.first->GetMethodId(entry.GetDexMethodIndex());
+
+        std::string actual_klass = dex_dep.first->StringByTypeIdx(method_id.class_idx_);
+        if (expected_klass != actual_klass) {
+          continue;
+        }
+
+        std::string actual_name = dex_dep.first->StringDataByIdx(method_id.name_idx_);
+        if (expected_name != actual_name) {
+          continue;
+        }
+
+        std::string actual_signature = dex_dep.first->GetMethodSignature(method_id).ToString();
+        if (expected_signature != actual_signature) {
+          continue;
+        }
+
+        if (expected_resolved) {
+          // Test access flags. Note that PrettyJavaAccessFlags always appends
+          // a space after the modifiers. Add it to the expected access flags.
+          std::string actual_access_flags = PrettyJavaAccessFlags(entry.GetAccessFlags());
+          if (expected_access_flags + " " != actual_access_flags) {
+            continue;
+          }
+
+          std::string actual_decl_klass = verifier_deps_->GetStringFromId(
+              *dex_dep.first, entry.GetDeclaringClassIndex());
+          if (expected_decl_klass != actual_decl_klass) {
+            continue;
+          }
+        }
+
+        return true;
+      }
+    }
+    return false;
+  }
+
+  std::unique_ptr<verifier::VerifierDeps> verifier_deps_;
+  const DexFile* dex_file_;
+  jobject class_loader_;
+  mirror::Class* klass_Main_;
+};
+
+TEST_F(VerifierDepsTest, StringToId) {
+  ScopedObjectAccess soa(Thread::Current());
+  LoadDexFile(&soa);
+
+  MutexLock mu(Thread::Current(), *Locks::verifier_deps_lock_);
+
+  uint32_t id_Main1 = verifier_deps_->GetIdFromString(*dex_file_, "LMain;");
+  ASSERT_LT(id_Main1, dex_file_->NumStringIds());
+  ASSERT_EQ("LMain;", verifier_deps_->GetStringFromId(*dex_file_, id_Main1));
+
+  uint32_t id_Main2 = verifier_deps_->GetIdFromString(*dex_file_, "LMain;");
+  ASSERT_LT(id_Main2, dex_file_->NumStringIds());
+  ASSERT_EQ("LMain;", verifier_deps_->GetStringFromId(*dex_file_, id_Main2));
+
+  uint32_t id_Lorem1 = verifier_deps_->GetIdFromString(*dex_file_, "Lorem ipsum");
+  ASSERT_GE(id_Lorem1, dex_file_->NumStringIds());
+  ASSERT_EQ("Lorem ipsum", verifier_deps_->GetStringFromId(*dex_file_, id_Lorem1));
+
+  uint32_t id_Lorem2 = verifier_deps_->GetIdFromString(*dex_file_, "Lorem ipsum");
+  ASSERT_GE(id_Lorem2, dex_file_->NumStringIds());
+  ASSERT_EQ("Lorem ipsum", verifier_deps_->GetStringFromId(*dex_file_, id_Lorem2));
+
+  ASSERT_EQ(id_Main1, id_Main2);
+  ASSERT_EQ(id_Lorem1, id_Lorem2);
+  ASSERT_NE(id_Main1, id_Lorem1);
+}
+
+TEST_F(VerifierDepsTest, Assignable_BothInBoot) {
+  ASSERT_TRUE(TestAssignabilityRecording(/* dst */ "Ljava/util/TimeZone;",
+                                         /* src */ "Ljava/util/SimpleTimeZone;",
+                                         /* is_strict */ true,
+                                         /* is_assignable */ true));
+  ASSERT_TRUE(HasAssignable("Ljava/util/TimeZone;", "Ljava/util/SimpleTimeZone;", true));
+}
+
+TEST_F(VerifierDepsTest, Assignable_DestinationInBoot1) {
+  ASSERT_TRUE(TestAssignabilityRecording(/* dst */ "Ljava/net/Socket;",
+                                         /* src */ "LMySSLSocket;",
+                                         /* is_strict */ true,
+                                         /* is_assignable */ true));
+  ASSERT_TRUE(HasAssignable("Ljava/net/Socket;", "LMySSLSocket;", true));
+}
+
+TEST_F(VerifierDepsTest, Assignable_DestinationInBoot2) {
+  ASSERT_TRUE(TestAssignabilityRecording(/* dst */ "Ljava/util/TimeZone;",
+                                         /* src */ "LMySimpleTimeZone;",
+                                         /* is_strict */ true,
+                                         /* is_assignable */ true));
+  ASSERT_TRUE(HasAssignable("Ljava/util/TimeZone;", "LMySimpleTimeZone;", true));
+}
+
+TEST_F(VerifierDepsTest, Assignable_DestinationInBoot3) {
+  ASSERT_TRUE(TestAssignabilityRecording(/* dst */ "Ljava/util/Collection;",
+                                         /* src */ "LMyThreadSet;",
+                                         /* is_strict */ true,
+                                         /* is_assignable */ true));
+  ASSERT_TRUE(HasAssignable("Ljava/util/Collection;", "LMyThreadSet;", true));
+}
+
+TEST_F(VerifierDepsTest, Assignable_BothArrays_Resolved) {
+  ASSERT_TRUE(TestAssignabilityRecording(/* dst */ "[[Ljava/util/TimeZone;",
+                                         /* src */ "[[Ljava/util/SimpleTimeZone;",
+                                         /* is_strict */ true,
+                                         /* is_assignable */ true));
+  // If the component types of both arrays are resolved, we optimize the list of
+  // dependencies by recording a dependency on the component types.
+  ASSERT_FALSE(HasAssignable("[[Ljava/util/TimeZone;", "[[Ljava/util/SimpleTimeZone;", true));
+  ASSERT_FALSE(HasAssignable("[Ljava/util/TimeZone;", "[Ljava/util/SimpleTimeZone;", true));
+  ASSERT_TRUE(HasAssignable("Ljava/util/TimeZone;", "Ljava/util/SimpleTimeZone;", true));
+}
+
+TEST_F(VerifierDepsTest, Assignable_BothArrays_Erroneous) {
+  ASSERT_TRUE(TestAssignabilityRecording(/* dst */ "[[Ljava/util/TimeZone;",
+                                         /* src */ "[[LMyErroneousTimeZone;",
+                                         /* is_strict */ true,
+                                         /* is_assignable */ true));
+  // If the component type of an array is erroneous, we record the dependency on
+  // the array type.
+  ASSERT_FALSE(HasAssignable("[[Ljava/util/TimeZone;", "[[LMyErroneousTimeZone;", true));
+  ASSERT_TRUE(HasAssignable("[Ljava/util/TimeZone;", "[LMyErroneousTimeZone;", true));
+  ASSERT_FALSE(HasAssignable("Ljava/util/TimeZone;", "LMyErroneousTimeZone;", true));
+}
+
+  // We test that VerifierDeps does not try to optimize by storing assignability
+  // of the component types. This is due to the fact that the component type may
+  // be an erroneous class, even though the array type has resolved status.
+
+TEST_F(VerifierDepsTest, Assignable_ArrayToInterface1) {
+  ASSERT_TRUE(TestAssignabilityRecording(/* dst */ "Ljava/io/Serializable;",
+                                         /* src */ "[Ljava/util/TimeZone;",
+                                         /* is_strict */ true,
+                                         /* is_assignable */ true));
+  ASSERT_TRUE(HasAssignable("Ljava/io/Serializable;", "[Ljava/util/TimeZone;", true));
+}
+
+TEST_F(VerifierDepsTest, Assignable_ArrayToInterface2) {
+  ASSERT_TRUE(TestAssignabilityRecording(/* dst */ "Ljava/io/Serializable;",
+                                         /* src */ "[LMyThreadSet;",
+                                         /* is_strict */ true,
+                                         /* is_assignable */ true));
+  ASSERT_TRUE(HasAssignable("Ljava/io/Serializable;", "[LMyThreadSet;", true));
+}
+
+TEST_F(VerifierDepsTest, NotAssignable_BothInBoot) {
+  ASSERT_TRUE(TestAssignabilityRecording(/* dst */ "Ljava/lang/Exception;",
+                                         /* src */ "Ljava/util/SimpleTimeZone;",
+                                         /* is_strict */ true,
+                                         /* is_assignable */ false));
+  ASSERT_TRUE(HasAssignable("Ljava/lang/Exception;", "Ljava/util/SimpleTimeZone;", false));
+}
+
+TEST_F(VerifierDepsTest, NotAssignable_DestinationInBoot1) {
+  ASSERT_TRUE(TestAssignabilityRecording(/* dst */ "Ljava/lang/Exception;",
+                                         /* src */ "LMySSLSocket;",
+                                         /* is_strict */ true,
+                                         /* is_assignable */ false));
+  ASSERT_TRUE(HasAssignable("Ljava/lang/Exception;", "LMySSLSocket;", false));
+}
+
+TEST_F(VerifierDepsTest, NotAssignable_DestinationInBoot2) {
+  ASSERT_TRUE(TestAssignabilityRecording(/* dst */ "Ljava/lang/Exception;",
+                                         /* src */ "LMySimpleTimeZone;",
+                                         /* is_strict */ true,
+                                         /* is_assignable */ false));
+  ASSERT_TRUE(HasAssignable("Ljava/lang/Exception;", "LMySimpleTimeZone;", false));
+}
+
+TEST_F(VerifierDepsTest, NotAssignable_BothArrays) {
+  ASSERT_TRUE(TestAssignabilityRecording(/* dst */ "[Ljava/lang/Exception;",
+                                         /* src */ "[Ljava/util/SimpleTimeZone;",
+                                         /* is_strict */ true,
+                                         /* is_assignable */ false));
+  ASSERT_TRUE(HasAssignable("Ljava/lang/Exception;", "Ljava/util/SimpleTimeZone;", false));
+}
+
+TEST_F(VerifierDepsTest, ArgumentType_ResolvedClass) {
+  ASSERT_TRUE(VerifyMethod("ArgumentType_ResolvedClass"));
+  ASSERT_TRUE(HasClass("Ljava/lang/Thread;", true, "public"));
+}
+
+TEST_F(VerifierDepsTest, ArgumentType_ResolvedReferenceArray) {
+  ASSERT_TRUE(VerifyMethod("ArgumentType_ResolvedReferenceArray"));
+  ASSERT_TRUE(HasClass("[Ljava/lang/Thread;", true, "public final abstract"));
+}
+
+TEST_F(VerifierDepsTest, ArgumentType_ResolvedPrimitiveArray) {
+  ASSERT_TRUE(VerifyMethod("ArgumentType_ResolvedPrimitiveArray"));
+  ASSERT_TRUE(HasClass("[B", true, "public final abstract"));
+}
+
+TEST_F(VerifierDepsTest, ArgumentType_UnresolvedClass) {
+  ASSERT_TRUE(VerifyMethod("ArgumentType_UnresolvedClass"));
+  ASSERT_TRUE(HasClass("LUnresolvedClass;", false));
+}
+
+TEST_F(VerifierDepsTest, ArgumentType_UnresolvedSuper) {
+  ASSERT_TRUE(VerifyMethod("ArgumentType_UnresolvedSuper"));
+  ASSERT_TRUE(HasClass("LMySetWithUnresolvedSuper;", false));
+}
+
+TEST_F(VerifierDepsTest, ReturnType_Reference) {
+  ASSERT_TRUE(VerifyMethod("ReturnType_Reference"));
+  ASSERT_TRUE(HasAssignable("Ljava/lang/Throwable;", "Ljava/lang/IllegalStateException;", true));
+}
+
+TEST_F(VerifierDepsTest, ReturnType_Array) {
+  ASSERT_FALSE(VerifyMethod("ReturnType_Array"));
+  ASSERT_TRUE(HasAssignable("Ljava/lang/Integer;", "Ljava/lang/IllegalStateException;", false));
+}
+
+TEST_F(VerifierDepsTest, InvokeArgumentType) {
+  ASSERT_TRUE(VerifyMethod("InvokeArgumentType"));
+  ASSERT_TRUE(HasClass("Ljava/text/SimpleDateFormat;", true, "public"));
+  ASSERT_TRUE(HasClass("Ljava/util/SimpleTimeZone;", true, "public"));
+  ASSERT_TRUE(HasMethod("virtual",
+                        "Ljava/text/SimpleDateFormat;",
+                        "setTimeZone",
+                        "(Ljava/util/TimeZone;)V",
+                        true,
+                        "public",
+                        "Ljava/text/DateFormat;"));
+  ASSERT_TRUE(HasAssignable("Ljava/util/TimeZone;", "Ljava/util/SimpleTimeZone;", true));
+}
+
+TEST_F(VerifierDepsTest, MergeTypes_RegisterLines) {
+  ASSERT_TRUE(VerifyMethod("MergeTypes_RegisterLines"));
+  ASSERT_TRUE(HasAssignable("Ljava/lang/Exception;", "LMySocketTimeoutException;", true));
+  ASSERT_TRUE(HasAssignable(
+      "Ljava/lang/Exception;", "Ljava/util/concurrent/TimeoutException;", true));
+}
+
+TEST_F(VerifierDepsTest, MergeTypes_IfInstanceOf) {
+  ASSERT_TRUE(VerifyMethod("MergeTypes_IfInstanceOf"));
+  ASSERT_TRUE(HasAssignable("Ljava/lang/Exception;", "Ljava/net/SocketTimeoutException;", true));
+  ASSERT_TRUE(HasAssignable(
+      "Ljava/lang/Exception;", "Ljava/util/concurrent/TimeoutException;", true));
+  ASSERT_TRUE(HasAssignable("Ljava/net/SocketTimeoutException;", "Ljava/lang/Exception;", false));
+}
+
+TEST_F(VerifierDepsTest, MergeTypes_Unresolved) {
+  ASSERT_TRUE(VerifyMethod("MergeTypes_Unresolved"));
+  ASSERT_TRUE(HasAssignable("Ljava/lang/Exception;", "Ljava/net/SocketTimeoutException;", true));
+  ASSERT_TRUE(HasAssignable(
+      "Ljava/lang/Exception;", "Ljava/util/concurrent/TimeoutException;", true));
+}
+
+TEST_F(VerifierDepsTest, ConstClass_Resolved) {
+  ASSERT_TRUE(VerifyMethod("ConstClass_Resolved"));
+  ASSERT_TRUE(HasClass("Ljava/lang/IllegalStateException;", true, "public"));
+}
+
+TEST_F(VerifierDepsTest, ConstClass_Unresolved) {
+  ASSERT_TRUE(VerifyMethod("ConstClass_Unresolved"));
+  ASSERT_TRUE(HasClass("LUnresolvedClass;", false));
+}
+
+TEST_F(VerifierDepsTest, CheckCast_Resolved) {
+  ASSERT_TRUE(VerifyMethod("CheckCast_Resolved"));
+  ASSERT_TRUE(HasClass("Ljava/lang/IllegalStateException;", true, "public"));
+}
+
+TEST_F(VerifierDepsTest, CheckCast_Unresolved) {
+  ASSERT_TRUE(VerifyMethod("CheckCast_Unresolved"));
+  ASSERT_TRUE(HasClass("LUnresolvedClass;", false));
+}
+
+TEST_F(VerifierDepsTest, InstanceOf_Resolved) {
+  ASSERT_TRUE(VerifyMethod("InstanceOf_Resolved"));
+  ASSERT_TRUE(HasClass("Ljava/lang/IllegalStateException;", true, "public"));
+}
+
+TEST_F(VerifierDepsTest, InstanceOf_Unresolved) {
+  ASSERT_TRUE(VerifyMethod("InstanceOf_Unresolved"));
+  ASSERT_TRUE(HasClass("LUnresolvedClass;", false));
+}
+
+TEST_F(VerifierDepsTest, NewInstance_Resolved) {
+  ASSERT_TRUE(VerifyMethod("NewInstance_Resolved"));
+  ASSERT_TRUE(HasClass("Ljava/lang/IllegalStateException;", true, "public"));
+}
+
+TEST_F(VerifierDepsTest, NewInstance_Unresolved) {
+  ASSERT_TRUE(VerifyMethod("NewInstance_Unresolved"));
+  ASSERT_TRUE(HasClass("LUnresolvedClass;", false));
+}
+
+TEST_F(VerifierDepsTest, NewArray_Resolved) {
+  ASSERT_TRUE(VerifyMethod("NewArray_Resolved"));
+  ASSERT_TRUE(HasClass("[Ljava/lang/IllegalStateException;", true, "public final abstract"));
+}
+
+TEST_F(VerifierDepsTest, NewArray_Unresolved) {
+  ASSERT_TRUE(VerifyMethod("NewArray_Unresolved"));
+  ASSERT_TRUE(HasClass("[LUnresolvedClass;", false));
+}
+
+TEST_F(VerifierDepsTest, Throw) {
+  ASSERT_TRUE(VerifyMethod("Throw"));
+  ASSERT_TRUE(HasAssignable("Ljava/lang/Throwable;", "Ljava/lang/IllegalStateException;", true));
+}
+
+TEST_F(VerifierDepsTest, MoveException_Resolved) {
+  ASSERT_TRUE(VerifyMethod("MoveException_Resolved"));
+  ASSERT_TRUE(HasClass("Ljava/io/InterruptedIOException;", true, "public"));
+  ASSERT_TRUE(HasClass("Ljava/net/SocketTimeoutException;", true, "public"));
+  ASSERT_TRUE(HasClass("Ljava/util/zip/ZipException;", true, "public"));
+
+  // Testing that all exception types are assignable to Throwable.
+  ASSERT_TRUE(HasAssignable("Ljava/lang/Throwable;", "Ljava/io/InterruptedIOException;", true));
+  ASSERT_TRUE(HasAssignable("Ljava/lang/Throwable;", "Ljava/net/SocketTimeoutException;", true));
+  ASSERT_TRUE(HasAssignable("Ljava/lang/Throwable;", "Ljava/util/zip/ZipException;", true));
+
+  // Testing that the merge type is assignable to Throwable.
+  ASSERT_TRUE(HasAssignable("Ljava/lang/Throwable;", "Ljava/io/IOException;", true));
+
+  // Merging of exception types.
+  ASSERT_TRUE(HasAssignable("Ljava/io/IOException;", "Ljava/io/InterruptedIOException;", true));
+  ASSERT_TRUE(HasAssignable("Ljava/io/IOException;", "Ljava/util/zip/ZipException;", true));
+  ASSERT_TRUE(HasAssignable(
+      "Ljava/io/InterruptedIOException;", "Ljava/net/SocketTimeoutException;", true));
+}
+
+TEST_F(VerifierDepsTest, MoveException_Unresolved) {
+  ASSERT_FALSE(VerifyMethod("MoveException_Unresolved"));
+  ASSERT_TRUE(HasClass("LUnresolvedException;", false));
+}
+
+TEST_F(VerifierDepsTest, StaticField_Resolved_DeclaredInReferenced) {
+  ASSERT_TRUE(VerifyMethod("StaticField_Resolved_DeclaredInReferenced"));
+  ASSERT_TRUE(HasClass("Ljava/lang/System;", true, "public final"));
+  ASSERT_TRUE(HasField("Ljava/lang/System;",
+                       "out",
+                       "Ljava/io/PrintStream;",
+                       true,
+                       "public final static",
+                       "Ljava/lang/System;"));
+}
+
+TEST_F(VerifierDepsTest, StaticField_Resolved_DeclaredInSuperclass1) {
+  ASSERT_TRUE(VerifyMethod("StaticField_Resolved_DeclaredInSuperclass1"));
+  ASSERT_TRUE(HasClass("Ljava/util/SimpleTimeZone;", true, "public"));
+  ASSERT_TRUE(HasField(
+      "Ljava/util/SimpleTimeZone;", "LONG", "I", true, "public final static", "Ljava/util/TimeZone;"));
+}
+
+TEST_F(VerifierDepsTest, StaticField_Resolved_DeclaredInSuperclass2) {
+  ASSERT_TRUE(VerifyMethod("StaticField_Resolved_DeclaredInSuperclass2"));
+  ASSERT_TRUE(HasField(
+      "LMySimpleTimeZone;", "SHORT", "I", true, "public final static", "Ljava/util/TimeZone;"));
+}
+
+TEST_F(VerifierDepsTest, StaticField_Resolved_DeclaredInInterface1) {
+  ASSERT_TRUE(VerifyMethod("StaticField_Resolved_DeclaredInInterface1"));
+  ASSERT_TRUE(HasClass("Ljavax/xml/transform/dom/DOMResult;", true, "public"));
+  ASSERT_TRUE(HasField("Ljavax/xml/transform/dom/DOMResult;",
+                       "PI_ENABLE_OUTPUT_ESCAPING",
+                       "Ljava/lang/String;",
+                       true,
+                       "public final static",
+                       "Ljavax/xml/transform/Result;"));
+}
+
+TEST_F(VerifierDepsTest, StaticField_Resolved_DeclaredInInterface2) {
+  ASSERT_TRUE(VerifyMethod("StaticField_Resolved_DeclaredInInterface2"));
+  ASSERT_TRUE(HasField("LMyDOMResult;",
+                       "PI_ENABLE_OUTPUT_ESCAPING",
+                       "Ljava/lang/String;",
+                       true,
+                       "public final static",
+                       "Ljavax/xml/transform/Result;"));
+}
+
+TEST_F(VerifierDepsTest, StaticField_Resolved_DeclaredInInterface3) {
+  ASSERT_TRUE(VerifyMethod("StaticField_Resolved_DeclaredInInterface3"));
+  ASSERT_TRUE(HasField("LMyResult;",
+                       "PI_ENABLE_OUTPUT_ESCAPING",
+                       "Ljava/lang/String;",
+                       true,
+                       "public final static",
+                       "Ljavax/xml/transform/Result;"));
+}
+
+TEST_F(VerifierDepsTest, StaticField_Resolved_DeclaredInInterface4) {
+  ASSERT_TRUE(VerifyMethod("StaticField_Resolved_DeclaredInInterface4"));
+  ASSERT_TRUE(HasField("LMyDocument;",
+                       "ELEMENT_NODE",
+                       "S",
+                       true,
+                       "public final static",
+                       "Lorg/w3c/dom/Node;"));
+}
+
+TEST_F(VerifierDepsTest, StaticField_Unresolved_ReferrerInBoot) {
+  ASSERT_TRUE(VerifyMethod("StaticField_Unresolved_ReferrerInBoot"));
+  ASSERT_TRUE(HasClass("Ljava/util/TimeZone;", true, "public abstract"));
+  ASSERT_TRUE(HasField("Ljava/util/TimeZone;", "x", "I", false));
+}
+
+TEST_F(VerifierDepsTest, StaticField_Unresolved_ReferrerInDex) {
+  ASSERT_TRUE(VerifyMethod("StaticField_Unresolved_ReferrerInDex"));
+  ASSERT_TRUE(HasField("LMyThreadSet;", "x", "I", false));
+}
+
+TEST_F(VerifierDepsTest, InstanceField_Resolved_DeclaredInReferenced) {
+  ASSERT_TRUE(VerifyMethod("InstanceField_Resolved_DeclaredInReferenced"));
+  ASSERT_TRUE(HasClass("Ljava/io/InterruptedIOException;", true, "public"));
+  ASSERT_TRUE(HasField("Ljava/io/InterruptedIOException;",
+                       "bytesTransferred",
+                       "I",
+                       true,
+                       "public",
+                       "Ljava/io/InterruptedIOException;"));
+  ASSERT_TRUE(HasAssignable(
+      "Ljava/io/InterruptedIOException;", "LMySocketTimeoutException;", true));
+}
+
+TEST_F(VerifierDepsTest, InstanceField_Resolved_DeclaredInSuperclass1) {
+  ASSERT_TRUE(VerifyMethod("InstanceField_Resolved_DeclaredInSuperclass1"));
+  ASSERT_TRUE(HasClass("Ljava/net/SocketTimeoutException;", true, "public"));
+  ASSERT_TRUE(HasField("Ljava/net/SocketTimeoutException;",
+                       "bytesTransferred",
+                       "I",
+                       true,
+                       "public",
+                       "Ljava/io/InterruptedIOException;"));
+  ASSERT_TRUE(HasAssignable(
+      "Ljava/io/InterruptedIOException;", "LMySocketTimeoutException;", true));
+}
+
+TEST_F(VerifierDepsTest, InstanceField_Resolved_DeclaredInSuperclass2) {
+  ASSERT_TRUE(VerifyMethod("InstanceField_Resolved_DeclaredInSuperclass2"));
+  ASSERT_TRUE(HasField("LMySocketTimeoutException;",
+                       "bytesTransferred",
+                       "I",
+                       true,
+                       "public",
+                       "Ljava/io/InterruptedIOException;"));
+  ASSERT_TRUE(HasAssignable(
+      "Ljava/io/InterruptedIOException;", "LMySocketTimeoutException;", true));
+}
+
+TEST_F(VerifierDepsTest, InstanceField_Unresolved_ReferrerInBoot) {
+  ASSERT_TRUE(VerifyMethod("InstanceField_Unresolved_ReferrerInBoot"));
+  ASSERT_TRUE(HasClass("Ljava/io/InterruptedIOException;", true, "public"));
+  ASSERT_TRUE(HasField("Ljava/io/InterruptedIOException;", "x", "I", false));
+}
+
+TEST_F(VerifierDepsTest, InstanceField_Unresolved_ReferrerInDex) {
+  ASSERT_TRUE(VerifyMethod("InstanceField_Unresolved_ReferrerInDex"));
+  ASSERT_TRUE(HasField("LMyThreadSet;", "x", "I", false));
+}
+
+TEST_F(VerifierDepsTest, InvokeStatic_Resolved_DeclaredInReferenced) {
+  ASSERT_TRUE(VerifyMethod("InvokeStatic_Resolved_DeclaredInReferenced"));
+  ASSERT_TRUE(HasClass("Ljava/net/Socket;", true, "public"));
+  ASSERT_TRUE(HasMethod("direct",
+                        "Ljava/net/Socket;",
+                        "setSocketImplFactory",
+                        "(Ljava/net/SocketImplFactory;)V",
+                        true,
+                        "public static",
+                        "Ljava/net/Socket;"));
+}
+
+TEST_F(VerifierDepsTest, InvokeStatic_Resolved_DeclaredInSuperclass1) {
+  ASSERT_TRUE(VerifyMethod("InvokeStatic_Resolved_DeclaredInSuperclass1"));
+  ASSERT_TRUE(HasClass("Ljavax/net/ssl/SSLSocket;", true, "public abstract"));
+  ASSERT_TRUE(HasMethod("direct",
+                        "Ljavax/net/ssl/SSLSocket;",
+                        "setSocketImplFactory",
+                        "(Ljava/net/SocketImplFactory;)V",
+                        true,
+                        "public static",
+                        "Ljava/net/Socket;"));
+}
+
+TEST_F(VerifierDepsTest, InvokeStatic_Resolved_DeclaredInSuperclass2) {
+  ASSERT_TRUE(VerifyMethod("InvokeStatic_Resolved_DeclaredInSuperclass2"));
+  ASSERT_TRUE(HasMethod("direct",
+                        "LMySSLSocket;",
+                        "setSocketImplFactory",
+                        "(Ljava/net/SocketImplFactory;)V",
+                        true,
+                        "public static",
+                        "Ljava/net/Socket;"));
+}
+
+TEST_F(VerifierDepsTest, InvokeStatic_DeclaredInInterface1) {
+  ASSERT_TRUE(VerifyMethod("InvokeStatic_DeclaredInInterface1"));
+  ASSERT_TRUE(HasClass("Ljava/util/Map$Entry;", true, "public abstract interface"));
+  ASSERT_TRUE(HasMethod("direct",
+                        "Ljava/util/Map$Entry;",
+                        "comparingByKey",
+                        "()Ljava/util/Comparator;",
+                        true,
+                        "public static",
+                        "Ljava/util/Map$Entry;"));
+}
+
+TEST_F(VerifierDepsTest, InvokeStatic_DeclaredInInterface2) {
+  ASSERT_FALSE(VerifyMethod("InvokeStatic_DeclaredInInterface2"));
+  ASSERT_TRUE(HasClass("Ljava/util/AbstractMap$SimpleEntry;", true, "public"));
+  ASSERT_TRUE(HasMethod("direct",
+                        "Ljava/util/AbstractMap$SimpleEntry;",
+                        "comparingByKey",
+                        "()Ljava/util/Comparator;",
+                        false));
+}
+
+TEST_F(VerifierDepsTest, InvokeStatic_Unresolved1) {
+  ASSERT_FALSE(VerifyMethod("InvokeStatic_Unresolved1"));
+  ASSERT_TRUE(HasClass("Ljavax/net/ssl/SSLSocket;", true, "public abstract"));
+  ASSERT_TRUE(HasMethod("direct", "Ljavax/net/ssl/SSLSocket;", "x", "()V", false));
+}
+
+TEST_F(VerifierDepsTest, InvokeStatic_Unresolved2) {
+  ASSERT_FALSE(VerifyMethod("InvokeStatic_Unresolved2"));
+  ASSERT_TRUE(HasMethod("direct", "LMySSLSocket;", "x", "()V", false));
+}
+
+TEST_F(VerifierDepsTest, InvokeDirect_Resolved_DeclaredInReferenced) {
+  ASSERT_TRUE(VerifyMethod("InvokeDirect_Resolved_DeclaredInReferenced"));
+  ASSERT_TRUE(HasClass("Ljava/net/Socket;", true, "public"));
+  ASSERT_TRUE(HasMethod(
+      "direct", "Ljava/net/Socket;", "<init>", "()V", true, "public", "Ljava/net/Socket;"));
+}
+
+TEST_F(VerifierDepsTest, InvokeDirect_Resolved_DeclaredInSuperclass1) {
+  ASSERT_FALSE(VerifyMethod("InvokeDirect_Resolved_DeclaredInSuperclass1"));
+  ASSERT_TRUE(HasClass("Ljavax/net/ssl/SSLSocket;", true, "public abstract"));
+  ASSERT_TRUE(HasMethod("direct",
+                        "Ljavax/net/ssl/SSLSocket;",
+                        "checkOldImpl",
+                        "()V",
+                        true,
+                        "private",
+                        "Ljava/net/Socket;"));
+}
+
+TEST_F(VerifierDepsTest, InvokeDirect_Resolved_DeclaredInSuperclass2) {
+  ASSERT_FALSE(VerifyMethod("InvokeDirect_Resolved_DeclaredInSuperclass2"));
+  ASSERT_TRUE(HasMethod(
+      "direct", "LMySSLSocket;", "checkOldImpl", "()V", true, "private", "Ljava/net/Socket;"));
+}
+
+TEST_F(VerifierDepsTest, InvokeDirect_Unresolved1) {
+  ASSERT_FALSE(VerifyMethod("InvokeDirect_Unresolved1"));
+  ASSERT_TRUE(HasClass("Ljavax/net/ssl/SSLSocket;", true, "public abstract"));
+  ASSERT_TRUE(HasMethod("direct", "Ljavax/net/ssl/SSLSocket;", "x", "()V", false));
+}
+
+TEST_F(VerifierDepsTest, InvokeDirect_Unresolved2) {
+  ASSERT_FALSE(VerifyMethod("InvokeDirect_Unresolved2"));
+  ASSERT_TRUE(HasMethod("direct", "LMySSLSocket;", "x", "()V", false));
+}
+
+TEST_F(VerifierDepsTest, InvokeVirtual_Resolved_DeclaredInReferenced) {
+  ASSERT_TRUE(VerifyMethod("InvokeVirtual_Resolved_DeclaredInReferenced"));
+  ASSERT_TRUE(HasClass("Ljava/lang/Throwable;", true, "public"));
+  ASSERT_TRUE(HasMethod("virtual",
+                        "Ljava/lang/Throwable;",
+                        "getMessage",
+                        "()Ljava/lang/String;",
+                        true,
+                        "public",
+                        "Ljava/lang/Throwable;"));
+  // Type dependency on `this` argument.
+  ASSERT_TRUE(HasAssignable("Ljava/lang/Throwable;", "LMySocketTimeoutException;", true));
+}
+
+TEST_F(VerifierDepsTest, InvokeVirtual_Resolved_DeclaredInSuperclass1) {
+  ASSERT_TRUE(VerifyMethod("InvokeVirtual_Resolved_DeclaredInSuperclass1"));
+  ASSERT_TRUE(HasClass("Ljava/io/InterruptedIOException;", true, "public"));
+  ASSERT_TRUE(HasMethod("virtual",
+                        "Ljava/io/InterruptedIOException;",
+                        "getMessage",
+                        "()Ljava/lang/String;",
+                        true,
+                        "public",
+                        "Ljava/lang/Throwable;"));
+  // Type dependency on `this` argument.
+  ASSERT_TRUE(HasAssignable("Ljava/lang/Throwable;", "LMySocketTimeoutException;", true));
+}
+
+TEST_F(VerifierDepsTest, InvokeVirtual_Resolved_DeclaredInSuperclass2) {
+  ASSERT_TRUE(VerifyMethod("InvokeVirtual_Resolved_DeclaredInSuperclass2"));
+  ASSERT_TRUE(HasMethod("virtual",
+                        "LMySocketTimeoutException;",
+                        "getMessage",
+                        "()Ljava/lang/String;",
+                        true,
+                        "public",
+                        "Ljava/lang/Throwable;"));
+}
+
+TEST_F(VerifierDepsTest, InvokeVirtual_Resolved_DeclaredInSuperinterface) {
+  ASSERT_TRUE(VerifyMethod("InvokeVirtual_Resolved_DeclaredInSuperinterface"));
+  ASSERT_TRUE(HasMethod("virtual",
+                        "LMyThreadSet;",
+                        "size",
+                        "()I",
+                        true,
+                        "public abstract",
+                        "Ljava/util/Set;"));
+}
+
+TEST_F(VerifierDepsTest, InvokeVirtual_Unresolved1) {
+  ASSERT_FALSE(VerifyMethod("InvokeVirtual_Unresolved1"));
+  ASSERT_TRUE(HasClass("Ljava/io/InterruptedIOException;", true, "public"));
+  ASSERT_TRUE(HasMethod("virtual", "Ljava/io/InterruptedIOException;", "x", "()V", false));
+}
+
+TEST_F(VerifierDepsTest, InvokeVirtual_Unresolved2) {
+  ASSERT_FALSE(VerifyMethod("InvokeVirtual_Unresolved2"));
+  ASSERT_TRUE(HasMethod("virtual", "LMySocketTimeoutException;", "x", "()V", false));
+}
+
+TEST_F(VerifierDepsTest, InvokeVirtual_ActuallyDirect) {
+  ASSERT_FALSE(VerifyMethod("InvokeVirtual_ActuallyDirect"));
+  ASSERT_TRUE(HasMethod("virtual", "LMyThread;", "activeCount", "()I", false));
+  ASSERT_TRUE(HasMethod("direct",
+                        "LMyThread;",
+                        "activeCount",
+                        "()I",
+                        true,
+                        "public static",
+                        "Ljava/lang/Thread;"));
+}
+
+TEST_F(VerifierDepsTest, InvokeInterface_Resolved_DeclaredInReferenced) {
+  ASSERT_TRUE(VerifyMethod("InvokeInterface_Resolved_DeclaredInReferenced"));
+  ASSERT_TRUE(HasClass("Ljava/lang/Runnable;", true, "public abstract interface"));
+  ASSERT_TRUE(HasMethod("interface",
+                        "Ljava/lang/Runnable;",
+                        "run",
+                        "()V",
+                        true,
+                        "public abstract",
+                        "Ljava/lang/Runnable;"));
+}
+
+TEST_F(VerifierDepsTest, InvokeInterface_Resolved_DeclaredInSuperclass) {
+  ASSERT_FALSE(VerifyMethod("InvokeInterface_Resolved_DeclaredInSuperclass"));
+  ASSERT_TRUE(HasMethod("interface", "LMyThread;", "join", "()V", false));
+}
+
+TEST_F(VerifierDepsTest, InvokeInterface_Resolved_DeclaredInSuperinterface1) {
+  ASSERT_FALSE(VerifyMethod("InvokeInterface_Resolved_DeclaredInSuperinterface1"));
+  ASSERT_TRUE(HasMethod("interface",
+                        "LMyThreadSet;",
+                        "run",
+                        "()V",
+                        true,
+                        "public abstract",
+                        "Ljava/lang/Runnable;"));
+}
+
+TEST_F(VerifierDepsTest, InvokeInterface_Resolved_DeclaredInSuperinterface2) {
+  ASSERT_FALSE(VerifyMethod("InvokeInterface_Resolved_DeclaredInSuperinterface2"));
+  ASSERT_TRUE(HasMethod("interface",
+                        "LMyThreadSet;",
+                        "isEmpty",
+                        "()Z",
+                        true,
+                        "public abstract",
+                        "Ljava/util/Set;"));
+}
+
+TEST_F(VerifierDepsTest, InvokeInterface_Unresolved1) {
+  ASSERT_FALSE(VerifyMethod("InvokeInterface_Unresolved1"));
+  ASSERT_TRUE(HasClass("Ljava/lang/Runnable;", true, "public abstract interface"));
+  ASSERT_TRUE(HasMethod("interface", "Ljava/lang/Runnable;", "x", "()V", false));
+}
+
+TEST_F(VerifierDepsTest, InvokeInterface_Unresolved2) {
+  ASSERT_FALSE(VerifyMethod("InvokeInterface_Unresolved2"));
+  ASSERT_TRUE(HasMethod("interface", "LMyThreadSet;", "x", "()V", false));
+}
+
+TEST_F(VerifierDepsTest, InvokeSuper_ThisAssignable) {
+  ASSERT_TRUE(VerifyMethod("InvokeSuper_ThisAssignable"));
+  ASSERT_TRUE(HasClass("Ljava/lang/Runnable;", true, "public abstract interface"));
+  ASSERT_TRUE(HasAssignable("Ljava/lang/Runnable;", "LMain;", true));
+  ASSERT_TRUE(HasMethod("interface",
+                        "Ljava/lang/Runnable;",
+                        "run",
+                        "()V",
+                        true,
+                        "public abstract",
+                        "Ljava/lang/Runnable;"));
+}
+
+TEST_F(VerifierDepsTest, InvokeSuper_ThisNotAssignable) {
+  ASSERT_FALSE(VerifyMethod("InvokeSuper_ThisNotAssignable"));
+  ASSERT_TRUE(HasClass("Ljava/lang/Integer;", true, "public final"));
+  ASSERT_TRUE(HasAssignable("Ljava/lang/Integer;", "LMain;", false));
+  ASSERT_TRUE(HasMethod(
+      "virtual", "Ljava/lang/Integer;", "intValue", "()I", true, "public", "Ljava/lang/Integer;"));
+}
+
+}  // namespace verifier
+}  // namespace art
diff --git a/test/VerifierDeps/Main.smali b/test/VerifierDeps/Main.smali
new file mode 100644
index 0000000..74c0d03
--- /dev/null
+++ b/test/VerifierDeps/Main.smali
@@ -0,0 +1,464 @@
+# Copyright (C) 2016 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.
+
+.class public LMain;
+.super LMyThreadSet;
+
+.method public static ArgumentType_ResolvedClass(Ljava/lang/Thread;)V
+  .registers 1
+  return-void
+.end method
+
+.method public static ArgumentType_ResolvedReferenceArray([Ljava/lang/Thread;)V
+  .registers 1
+  return-void
+.end method
+
+.method public static ArgumentType_ResolvedPrimitiveArray([B)V
+  .registers 1
+  return-void
+.end method
+
+.method public static ArgumentType_UnresolvedClass(LUnresolvedClass;)V
+  .registers 1
+  return-void
+.end method
+
+.method public static ArgumentType_UnresolvedSuper(LMySetWithUnresolvedSuper;)V
+  .registers 1
+  return-void
+.end method
+
+.method public static ReturnType_Reference(Ljava/lang/IllegalStateException;)Ljava/lang/Throwable;
+  .registers 1
+  return-object p0
+.end method
+
+.method public static ReturnType_Array([Ljava/lang/IllegalStateException;)[Ljava/lang/Integer;
+  .registers 1
+  return-object p0
+.end method
+
+.method public static InvokeArgumentType(Ljava/text/SimpleDateFormat;Ljava/util/SimpleTimeZone;)V
+  .registers 2
+  invoke-virtual {p0, p1}, Ljava/text/SimpleDateFormat;->setTimeZone(Ljava/util/TimeZone;)V
+  return-void
+.end method
+
+.method public static MergeTypes_RegisterLines(Z)Ljava/lang/Object;
+  .registers 2
+  if-eqz p0, :else
+
+  new-instance v0, LMySocketTimeoutException;
+  invoke-direct {v0}, LMySocketTimeoutException;-><init>()V
+  goto :merge
+
+  :else
+  new-instance v0, Ljava/util/concurrent/TimeoutException;
+  invoke-direct {v0}, Ljava/util/concurrent/TimeoutException;-><init>()V
+  goto :merge
+
+  :merge
+  return-object v0
+.end method
+
+.method public static MergeTypes_IfInstanceOf(Ljava/net/SocketTimeoutException;)V
+  .registers 2
+  instance-of v0, p0, Ljava/util/concurrent/TimeoutException;
+  if-eqz v0, :else
+  return-void
+  :else
+  return-void
+.end method
+
+.method public static MergeTypes_Unresolved(ZZLUnresolvedClassA;)Ljava/lang/Object;
+  .registers 5
+  if-eqz p0, :else1
+
+  move-object v0, p2
+  goto :merge
+
+  :else1
+  if-eqz p1, :else2
+
+  new-instance v0, Ljava/util/concurrent/TimeoutException;
+  invoke-direct {v0}, Ljava/util/concurrent/TimeoutException;-><init>()V
+  goto :merge
+
+  :else2
+  new-instance v0, Ljava/net/SocketTimeoutException;
+  invoke-direct {v0}, Ljava/net/SocketTimeoutException;-><init>()V
+  goto :merge
+
+  :merge
+  return-object v0
+.end method
+
+.method public static ConstClass_Resolved()V
+  .registers 1
+  const-class v0, Ljava/lang/IllegalStateException;
+  return-void
+.end method
+
+.method public static ConstClass_Unresolved()V
+  .registers 1
+  const-class v0, LUnresolvedClass;
+  return-void
+.end method
+
+.method public static CheckCast_Resolved(Ljava/lang/Object;)V
+  .registers 1
+  check-cast p0, Ljava/lang/IllegalStateException;
+  return-void
+.end method
+
+.method public static CheckCast_Unresolved(Ljava/lang/Object;)V
+  .registers 1
+  check-cast p0, LUnresolvedClass;
+  return-void
+.end method
+
+.method public static InstanceOf_Resolved(Ljava/lang/Object;)Z
+  .registers 1
+  instance-of p0, p0, Ljava/lang/IllegalStateException;
+  return p0
+.end method
+
+.method public static InstanceOf_Unresolved(Ljava/lang/Object;)Z
+  .registers 1
+  instance-of p0, p0, LUnresolvedClass;
+  return p0
+.end method
+
+.method public static NewInstance_Resolved()V
+  .registers 1
+  new-instance v0, Ljava/lang/IllegalStateException;
+  return-void
+.end method
+
+.method public static NewInstance_Unresolved()V
+  .registers 1
+  new-instance v0, LUnresolvedClass;
+  return-void
+.end method
+
+.method public static NewArray_Resolved()V
+  .registers 1
+  const/4 v0, 0x1
+  new-array v0, v0, [Ljava/lang/IllegalStateException;
+  return-void
+.end method
+
+.method public static NewArray_Unresolved()V
+  .registers 2
+  const/4 v0, 0x1
+  new-array v0, v0, [LUnresolvedClass;
+  return-void
+.end method
+
+.method public static Throw(Ljava/lang/IllegalStateException;)V
+  .registers 2
+  throw p0
+.end method
+
+.method public static MoveException_Resolved()Ljava/lang/Object;
+  .registers 1
+  :try_start
+  invoke-static {}, Ljava/lang/System;->nanoTime()J
+  :try_end
+  .catch Ljava/net/SocketTimeoutException; {:try_start .. :try_end} :catch_block
+  .catch Ljava/io/InterruptedIOException; {:try_start .. :try_end} :catch_block
+  .catch Ljava/util/zip/ZipException; {:try_start .. :try_end} :catch_block
+  const/4 v0, 0x0
+  return-object v0
+
+  :catch_block
+  move-exception v0
+  return-object v0
+.end method
+
+.method public static MoveException_Unresolved()Ljava/lang/Object;
+  .registers 1
+  :try_start
+  invoke-static {}, Ljava/lang/System;->nanoTime()J
+  :try_end
+  .catch LUnresolvedException; {:try_start .. :try_end} :catch_block
+  const/4 v0, 0x0
+  return-object v0
+
+  :catch_block
+  move-exception v0
+  return-object v0
+.end method
+
+.method public static StaticField_Resolved_DeclaredInReferenced()V
+  .registers 1
+  sget-object v0, Ljava/lang/System;->out:Ljava/io/PrintStream;
+  return-void
+.end method
+
+.method public static StaticField_Resolved_DeclaredInSuperclass1()V
+  .registers 1
+  sget v0, Ljava/util/SimpleTimeZone;->LONG:I
+  return-void
+.end method
+
+.method public static StaticField_Resolved_DeclaredInSuperclass2()V
+  .registers 1
+  sget v0, LMySimpleTimeZone;->SHORT:I
+  return-void
+.end method
+
+.method public static StaticField_Resolved_DeclaredInInterface1()V
+  .registers 1
+  # Case 1: DOMResult implements Result
+  sget-object v0, Ljavax/xml/transform/dom/DOMResult;->PI_ENABLE_OUTPUT_ESCAPING:Ljava/lang/String;
+  return-void
+.end method
+
+.method public static StaticField_Resolved_DeclaredInInterface2()V
+  .registers 1
+  # Case 2: MyDOMResult extends DOMResult, DOMResult implements Result
+  sget-object v0, LMyDOMResult;->PI_ENABLE_OUTPUT_ESCAPING:Ljava/lang/String;
+  return-void
+.end method
+
+.method public static StaticField_Resolved_DeclaredInInterface3()V
+  .registers 1
+  # Case 3: MyResult implements Result
+  sget-object v0, LMyResult;->PI_ENABLE_OUTPUT_ESCAPING:Ljava/lang/String;
+  return-void
+.end method
+
+.method public static StaticField_Resolved_DeclaredInInterface4()V
+  .registers 1
+  # Case 4: MyDocument implements Document, Document extends Node
+  sget-short v0, LMyDocument;->ELEMENT_NODE:S
+  return-void
+.end method
+
+.method public static StaticField_Unresolved_ReferrerInBoot()V
+  .registers 1
+  sget v0, Ljava/util/TimeZone;->x:I
+  return-void
+.end method
+
+.method public static StaticField_Unresolved_ReferrerInDex()V
+  .registers 1
+  sget v0, LMyThreadSet;->x:I
+  return-void
+.end method
+
+.method public static InstanceField_Resolved_DeclaredInReferenced(LMySocketTimeoutException;)V
+  .registers 1
+  iget v0, p0, Ljava/io/InterruptedIOException;->bytesTransferred:I
+  return-void
+.end method
+
+.method public static InstanceField_Resolved_DeclaredInSuperclass1(LMySocketTimeoutException;)V
+  .registers 1
+  iget v0, p0, Ljava/net/SocketTimeoutException;->bytesTransferred:I
+  return-void
+.end method
+
+.method public static InstanceField_Resolved_DeclaredInSuperclass2(LMySocketTimeoutException;)V
+  .registers 1
+  iget v0, p0, LMySocketTimeoutException;->bytesTransferred:I
+  return-void
+.end method
+
+.method public static InstanceField_Unresolved_ReferrerInBoot(LMySocketTimeoutException;)V
+  .registers 1
+  iget v0, p0, Ljava/io/InterruptedIOException;->x:I
+  return-void
+.end method
+
+.method public static InstanceField_Unresolved_ReferrerInDex(LMyThreadSet;)V
+  .registers 1
+  iget v0, p0, LMyThreadSet;->x:I
+  return-void
+.end method
+
+.method public static InvokeStatic_Resolved_DeclaredInReferenced()V
+  .registers 1
+  const v0, 0x0
+  invoke-static {v0}, Ljava/net/Socket;->setSocketImplFactory(Ljava/net/SocketImplFactory;)V
+  return-void
+.end method
+
+.method public static InvokeStatic_Resolved_DeclaredInSuperclass1()V
+  .registers 1
+  const v0, 0x0
+  invoke-static {v0}, Ljavax/net/ssl/SSLSocket;->setSocketImplFactory(Ljava/net/SocketImplFactory;)V
+  return-void
+.end method
+
+.method public static InvokeStatic_Resolved_DeclaredInSuperclass2()V
+  .registers 1
+  const v0, 0x0
+  invoke-static {v0}, LMySSLSocket;->setSocketImplFactory(Ljava/net/SocketImplFactory;)V
+  return-void
+.end method
+
+.method public static InvokeStatic_DeclaredInInterface1()V
+  .registers 1
+  invoke-static {}, Ljava/util/Map$Entry;->comparingByKey()Ljava/util/Comparator;
+  return-void
+.end method
+
+.method public static InvokeStatic_DeclaredInInterface2()V
+  .registers 1
+  # AbstractMap$SimpleEntry implements Map$Entry
+  # INVOKE_STATIC does not resolve to methods in superinterfaces. This will
+  # therefore result in an unresolved method.
+  invoke-static {}, Ljava/util/AbstractMap$SimpleEntry;->comparingByKey()Ljava/util/Comparator;
+  return-void
+.end method
+
+.method public static InvokeStatic_Unresolved1()V
+  .registers 1
+  invoke-static {}, Ljavax/net/ssl/SSLSocket;->x()V
+  return-void
+.end method
+
+.method public static InvokeStatic_Unresolved2()V
+  .registers 1
+  invoke-static {}, LMySSLSocket;->x()V
+  return-void
+.end method
+
+.method public static InvokeDirect_Resolved_DeclaredInReferenced()V
+  .registers 1
+  new-instance v0, Ljava/net/Socket;
+  invoke-direct {v0}, Ljava/net/Socket;-><init>()V
+  return-void
+.end method
+
+.method public static InvokeDirect_Resolved_DeclaredInSuperclass1(LMySSLSocket;)V
+  .registers 1
+  invoke-direct {p0}, Ljavax/net/ssl/SSLSocket;->checkOldImpl()V
+  return-void
+.end method
+
+.method public static InvokeDirect_Resolved_DeclaredInSuperclass2(LMySSLSocket;)V
+  .registers 1
+  invoke-direct {p0}, LMySSLSocket;->checkOldImpl()V
+  return-void
+.end method
+
+.method public static InvokeDirect_Unresolved1(LMySSLSocket;)V
+  .registers 1
+  invoke-direct {p0}, Ljavax/net/ssl/SSLSocket;->x()V
+  return-void
+.end method
+
+.method public static InvokeDirect_Unresolved2(LMySSLSocket;)V
+  .registers 1
+  invoke-direct {p0}, LMySSLSocket;->x()V
+  return-void
+.end method
+
+.method public static InvokeVirtual_Resolved_DeclaredInReferenced(LMySocketTimeoutException;)V
+  .registers 1
+  invoke-virtual {p0}, Ljava/lang/Throwable;->getMessage()Ljava/lang/String;
+  return-void
+.end method
+
+.method public static InvokeVirtual_Resolved_DeclaredInSuperclass1(LMySocketTimeoutException;)V
+  .registers 1
+  invoke-virtual {p0}, Ljava/io/InterruptedIOException;->getMessage()Ljava/lang/String;
+  return-void
+.end method
+
+.method public static InvokeVirtual_Resolved_DeclaredInSuperclass2(LMySocketTimeoutException;)V
+  .registers 1
+  invoke-virtual {p0}, LMySocketTimeoutException;->getMessage()Ljava/lang/String;
+  return-void
+.end method
+
+.method public static InvokeVirtual_Resolved_DeclaredInSuperinterface(LMyThreadSet;)V
+  .registers 1
+  invoke-virtual {p0}, LMyThreadSet;->size()I
+  return-void
+.end method
+
+.method public static InvokeVirtual_Unresolved1(LMySocketTimeoutException;)V
+  .registers 1
+  invoke-virtual {p0}, Ljava/io/InterruptedIOException;->x()V
+  return-void
+.end method
+
+.method public static InvokeVirtual_Unresolved2(LMySocketTimeoutException;)V
+  .registers 1
+  invoke-virtual {p0}, LMySocketTimeoutException;->x()V
+  return-void
+.end method
+
+.method public static InvokeVirtual_ActuallyDirect(LMyThread;)V
+  .registers 1
+  invoke-virtual {p0}, LMyThread;->activeCount()I
+  return-void
+.end method
+
+.method public static InvokeInterface_Resolved_DeclaredInReferenced(LMyThread;)V
+  .registers 1
+  invoke-interface {p0}, Ljava/lang/Runnable;->run()V
+  return-void
+.end method
+
+.method public static InvokeInterface_Resolved_DeclaredInSuperclass(LMyThread;)V
+  .registers 1
+  # Method join() is declared in the superclass of MyThread. As such, it should
+  # be called with invoke-virtual and will not be resolved here.
+  invoke-interface {p0}, LMyThread;->join()V
+  return-void
+.end method
+
+.method public static InvokeInterface_Resolved_DeclaredInSuperinterface1(LMyThreadSet;)V
+  .registers 1
+  # Verification will fail because the referring class is not an interface.
+  invoke-interface {p0}, LMyThreadSet;->run()V
+  return-void
+.end method
+
+.method public static InvokeInterface_Resolved_DeclaredInSuperinterface2(LMyThreadSet;)V
+  .registers 1
+  # Verification will fail because the referring class is not an interface.
+  invoke-interface {p0}, LMyThreadSet;->isEmpty()Z
+  return-void
+.end method
+
+.method public static InvokeInterface_Unresolved1(LMyThread;)V
+  .registers 1
+  invoke-interface {p0}, Ljava/lang/Runnable;->x()V
+  return-void
+.end method
+
+.method public static InvokeInterface_Unresolved2(LMyThread;)V
+  .registers 1
+  invoke-interface {p0}, LMyThreadSet;->x()V
+  return-void
+.end method
+
+.method public static InvokeSuper_ThisAssignable(Ljava/lang/Thread;)V
+  .registers 1
+  invoke-super {p0}, Ljava/lang/Runnable;->run()V
+  return-void
+.end method
+
+.method public static InvokeSuper_ThisNotAssignable(Ljava/lang/Integer;)V
+  .registers 1
+  invoke-super {p0}, Ljava/lang/Integer;->intValue()I
+  return-void
+.end method
diff --git a/test/VerifierDeps/MyDOMResult.smali b/test/VerifierDeps/MyDOMResult.smali
new file mode 100644
index 0000000..12f6243
--- /dev/null
+++ b/test/VerifierDeps/MyDOMResult.smali
@@ -0,0 +1,16 @@
+# Copyright (C) 2016 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.
+
+.class public LMyDOMResult;
+.super Ljavax/xml/transform/dom/DOMResult;
diff --git a/test/VerifierDeps/MyDocument.smali b/test/VerifierDeps/MyDocument.smali
new file mode 100644
index 0000000..3ce042c
--- /dev/null
+++ b/test/VerifierDeps/MyDocument.smali
@@ -0,0 +1,17 @@
+# Copyright (C) 2016 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.
+
+.class public LMyDocument;
+.super Ljava/lang/Object;
+.implements Lorg/w3c/dom/Document;
diff --git a/test/VerifierDeps/MyErroneousTimeZone.smali b/test/VerifierDeps/MyErroneousTimeZone.smali
new file mode 100644
index 0000000..5f23dd9
--- /dev/null
+++ b/test/VerifierDeps/MyErroneousTimeZone.smali
@@ -0,0 +1,22 @@
+# Copyright (C) 2016 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.
+
+.class public LMyErroneousTimeZone;
+.super LMySimpleTimeZone;
+
+# Class is erroneous because foo() is defined final in the superclass.
+.method public foo()V
+  .registers 1
+  return-void
+.end method
diff --git a/test/VerifierDeps/MyResult.smali b/test/VerifierDeps/MyResult.smali
new file mode 100644
index 0000000..e00e750
--- /dev/null
+++ b/test/VerifierDeps/MyResult.smali
@@ -0,0 +1,17 @@
+# Copyright (C) 2016 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.
+
+.class public LMyResult;
+.super Ljava/lang/Object;
+.implements Ljavax/xml/transform/Result;
diff --git a/test/VerifierDeps/MySSLSocket.smali b/test/VerifierDeps/MySSLSocket.smali
new file mode 100644
index 0000000..dd30081
--- /dev/null
+++ b/test/VerifierDeps/MySSLSocket.smali
@@ -0,0 +1,16 @@
+# Copyright (C) 2016 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.
+
+.class public LMySSLSocket;
+.super Ljavax/net/ssl/SSLSocket;
diff --git a/test/VerifierDeps/MySimpleTimeZone.smali b/test/VerifierDeps/MySimpleTimeZone.smali
new file mode 100644
index 0000000..f7a1e05
--- /dev/null
+++ b/test/VerifierDeps/MySimpleTimeZone.smali
@@ -0,0 +1,24 @@
+# Copyright (C) 2016 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.
+
+.class public LMySimpleTimeZone;
+.super Ljava/util/SimpleTimeZone;
+.implements Ljava/io/Serializable;
+
+# Define foo() as a final method. It is used by the MyErroneousTimeZone subclass
+# to generate a linkage error.
+.method public final foo()V
+  .registers 1
+  return-void
+.end method
diff --git a/test/VerifierDeps/MySocketTimeoutException.smali b/test/VerifierDeps/MySocketTimeoutException.smali
new file mode 100644
index 0000000..50e0762
--- /dev/null
+++ b/test/VerifierDeps/MySocketTimeoutException.smali
@@ -0,0 +1,16 @@
+# Copyright (C) 2016 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.
+
+.class public LMySocketTimeoutException;
+.super Ljava/net/SocketTimeoutException;
diff --git a/test/VerifierDeps/MyThread.smali b/test/VerifierDeps/MyThread.smali
new file mode 100644
index 0000000..7fdb254
--- /dev/null
+++ b/test/VerifierDeps/MyThread.smali
@@ -0,0 +1,16 @@
+# Copyright (C) 2016 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.
+
+.class public LMyThread;
+.super Ljava/lang/Thread;
diff --git a/test/VerifierDeps/MyThreadSet.smali b/test/VerifierDeps/MyThreadSet.smali
new file mode 100644
index 0000000..f331fcf
--- /dev/null
+++ b/test/VerifierDeps/MyThreadSet.smali
@@ -0,0 +1,17 @@
+# Copyright (C) 2016 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.
+
+.class public abstract LMyThreadSet;
+.super Ljava/lang/Thread;
+.implements Ljava/util/Set;