diff --git a/compiler/Android.bp b/compiler/Android.bp
index 61f682c..0b14859 100644
--- a/compiler/Android.bp
+++ b/compiler/Android.bp
@@ -342,6 +342,7 @@
         "utils/string_reference_test.cc",
         "utils/swap_space_test.cc",
         "utils/test_dex_file_builder_test.cc",
+        "verifier_deps_test.cc",
 
         "jni/jni_cfi_test.cc",
         "optimizing/codegen_test.cc",
diff --git a/compiler/driver/compiler_driver.cc b/compiler/driver/compiler_driver.cc
index dbde41c..56b4ebd 100644
--- a/compiler/driver/compiler_driver.cc
+++ b/compiler/driver/compiler_driver.cc
@@ -72,6 +72,7 @@
 #include "verifier/method_verifier.h"
 #include "verifier/method_verifier-inl.h"
 #include "verifier/verifier_log_mode.h"
+#include "verifier/verifier_deps.h"
 
 namespace art {
 
@@ -1968,6 +1969,7 @@
         hs.NewHandle(soa.Decode<mirror::ClassLoader>(jclass_loader)));
     Handle<mirror::Class> klass(
         hs.NewHandle(class_linker->FindClass(soa.Self(), descriptor, class_loader)));
+    verifier::MethodVerifier::FailureKind failure_kind;
     if (klass.Get() == nullptr) {
       CHECK(soa.Self()->IsExceptionPending());
       soa.Self()->ClearException();
@@ -1980,7 +1982,8 @@
       Handle<mirror::DexCache> dex_cache(hs.NewHandle(class_linker->FindDexCache(
           soa.Self(), dex_file, false)));
       std::string error_msg;
-      if (verifier::MethodVerifier::VerifyClass(soa.Self(),
+      failure_kind =
+          verifier::MethodVerifier::VerifyClass(soa.Self(),
                                                 &dex_file,
                                                 dex_cache,
                                                 class_loader,
@@ -1988,15 +1991,15 @@
                                                 Runtime::Current()->GetCompilerCallbacks(),
                                                 true /* allow soft failures */,
                                                 log_level_,
-                                                &error_msg) ==
-                                                    verifier::MethodVerifier::kHardFailure) {
+                                                &error_msg);
+      if (failure_kind == verifier::MethodVerifier::kHardFailure) {
         LOG(ERROR) << "Verification failed on class " << PrettyDescriptor(descriptor)
                    << " because: " << error_msg;
         manager_->GetCompiler()->SetHadHardVerifierFailure();
       }
     } else if (!SkipClass(jclass_loader, dex_file, klass.Get())) {
       CHECK(klass->IsResolved()) << klass->PrettyClass();
-      class_linker->VerifyClass(soa.Self(), klass, log_level_);
+      failure_kind = class_linker->VerifyClass(soa.Self(), klass, log_level_);
 
       if (klass->IsErroneous()) {
         // ClassLinker::VerifyClass throws, which isn't useful in the compiler.
@@ -2008,13 +2011,18 @@
       CHECK(klass->IsCompileTimeVerified() || klass->IsErroneous())
           << klass->PrettyDescriptor() << ": state=" << klass->GetStatus();
 
-      // It is *very* problematic if there are verification errors in the boot classpath. For example,
-      // we rely on things working OK without verification when the decryption dialog is brought up.
-      // So abort in a debug build if we find this violated.
+      // It is *very* problematic if there are verification errors in the boot classpath.
+      // For example, we rely on things working OK without verification when the
+      // decryption dialog is brought up. So abort in a debug build if we find this violated.
       DCHECK(!manager_->GetCompiler()->GetCompilerOptions().IsBootImage() || klass->IsVerified())
           << "Boot classpath class " << klass->PrettyClass()
           << " failed to fully verify.";
+    } else {
+      // Make the skip a soft failure, essentially being considered as verify at runtime.
+      failure_kind = verifier::MethodVerifier::kSoftFailure;
     }
+    verifier::VerifierDeps::MaybeRecordVerificationStatus(
+        dex_file, class_def.class_idx_, failure_kind);
     soa.Self()->AssertNoPendingException();
   }
 
diff --git a/compiler/driver/compiler_driver.h b/compiler/driver/compiler_driver.h
index 9a4dd85..4a48f9c 100644
--- a/compiler/driver/compiler_driver.h
+++ b/compiler/driver/compiler_driver.h
@@ -50,6 +50,7 @@
 
 namespace verifier {
 class MethodVerifier;
+class VerifierDepsTest;
 }  // namespace verifier
 
 class BitVector;
@@ -578,6 +579,7 @@
   const BitVector* current_dex_to_dex_methods_;
 
   friend class CompileClassVisitor;
+  friend class verifier::VerifierDepsTest;
   DISALLOW_COPY_AND_ASSIGN(CompilerDriver);
 };
 
diff --git a/compiler/driver/compiler_options.h b/compiler/driver/compiler_options.h
index 4eb6954..56b632d 100644
--- a/compiler/driver/compiler_options.h
+++ b/compiler/driver/compiler_options.h
@@ -29,6 +29,10 @@
 
 namespace art {
 
+namespace verifier {
+  class VerifierDepsTest;
+}
+
 class DexFile;
 
 class CompilerOptions FINAL {
@@ -338,6 +342,7 @@
 
   friend class Dex2Oat;
   friend class CommonCompilerTest;
+  friend class verifier::VerifierDepsTest;
 
   DISALLOW_COPY_AND_ASSIGN(CompilerOptions);
 };
diff --git a/runtime/verifier/verifier_deps_test.cc b/compiler/verifier_deps_test.cc
similarity index 94%
rename from runtime/verifier/verifier_deps_test.cc
rename to compiler/verifier_deps_test.cc
index 71203e6..9664e43 100644
--- a/runtime/verifier/verifier_deps_test.cc
+++ b/compiler/verifier_deps_test.cc
@@ -14,14 +14,17 @@
  * limitations under the License.
  */
 
-#include "verifier_deps.h"
+// Test is in compiler, as it uses compiler related code.
+#include "verifier/verifier_deps.h"
 
 #include "class_linker.h"
-#include "common_runtime_test.h"
+#include "compiler/common_compiler_test.h"
+#include "compiler/driver/compiler_options.h"
+#include "compiler/driver/compiler_driver.h"
 #include "compiler_callbacks.h"
 #include "dex_file.h"
 #include "handle_scope-inl.h"
-#include "method_verifier-inl.h"
+#include "verifier/method_verifier-inl.h"
 #include "mirror/class_loader.h"
 #include "runtime.h"
 #include "thread.h"
@@ -47,10 +50,10 @@
   verifier::VerifierDeps* deps_;
 };
 
-class VerifierDepsTest : public CommonRuntimeTest {
+class VerifierDepsTest : public CommonCompilerTest {
  public:
   void SetUpRuntimeOptions(RuntimeOptions* options) {
-    CommonRuntimeTest::SetUpRuntimeOptions(options);
+    CommonCompilerTest::SetUpRuntimeOptions(options);
     callbacks_.reset(new VerifierDepsCompilerCallbacks());
   }
 
@@ -147,23 +150,17 @@
 
   void VerifyDexFile() {
     std::string error_msg;
-    ScopedObjectAccess soa(Thread::Current());
-
-    LoadDexFile(&soa);
-    SetVerifierDeps({ dex_file_ });
-
-    for (size_t i = 0; i < dex_file_->NumClassDefs(); i++) {
-      const char* descriptor = dex_file_->GetClassDescriptor(dex_file_->GetClassDef(i));
-      mirror::Class* klass = FindClassByName(descriptor, &soa);
-      if (klass != nullptr) {
-        MethodVerifier::VerifyClass(Thread::Current(),
-                                    klass,
-                                    nullptr,
-                                    true,
-                                    HardFailLogMode::kLogWarning,
-                                    &error_msg);
-      }
+    {
+      ScopedObjectAccess soa(Thread::Current());
+      LoadDexFile(&soa);
     }
+    SetVerifierDeps({ dex_file_ });
+    TimingLogger timings("Verify", false, false);
+    std::vector<const DexFile*> dex_files;
+    dex_files.push_back(dex_file_);
+    compiler_options_->boot_image_ = false;
+    compiler_driver_->InitializeThreadPools();
+    compiler_driver_->Verify(class_loader_, dex_files, &timings);
   }
 
   bool TestAssignabilityRecording(const std::string& dst,
@@ -184,6 +181,21 @@
     return true;
   }
 
+  bool HasUnverifiedClass(const std::string& cls) {
+    const DexFile::TypeId* type_id = dex_file_->FindTypeId(cls.c_str());
+    DCHECK(type_id != nullptr);
+    uint16_t index = dex_file_->GetIndexForTypeId(*type_id);
+    MutexLock mu(Thread::Current(), *Locks::verifier_deps_lock_);
+    for (const auto& dex_dep : verifier_deps_->dex_deps_) {
+      for (uint16_t entry : dex_dep.second->unverified_classes_) {
+        if (index == entry) {
+          return true;
+        }
+      }
+    }
+    return false;
+  }
+
   // 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,
@@ -361,6 +373,7 @@
     bool has_classes = false;
     bool has_fields = false;
     bool has_methods = false;
+    bool has_unverified_classes = false;
 
     for (auto& entry : verifier_deps_->dex_deps_) {
       has_strings |= !entry.second->strings_.empty();
@@ -371,9 +384,15 @@
       has_methods |= !entry.second->direct_methods_.empty();
       has_methods |= !entry.second->virtual_methods_.empty();
       has_methods |= !entry.second->interface_methods_.empty();
+      has_unverified_classes |= !entry.second->unverified_classes_.empty();
     }
 
-    return has_strings && has_assignability && has_classes && has_fields && has_methods;
+    return has_strings &&
+           has_assignability &&
+           has_classes &&
+           has_fields &&
+           has_methods &&
+           has_unverified_classes;
   }
 
   std::unique_ptr<verifier::VerifierDeps> verifier_deps_;
@@ -1056,5 +1075,18 @@
   ASSERT_TRUE(verifier_deps_->Equals(decoded_deps));
 }
 
+TEST_F(VerifierDepsTest, UnverifiedClasses) {
+  VerifyDexFile();
+  ASSERT_FALSE(HasUnverifiedClass("LMyThread;"));
+  // Test that a class with a soft failure is recorded.
+  ASSERT_TRUE(HasUnverifiedClass("LMain;"));
+  // Test that a class with hard failure is recorded.
+  ASSERT_TRUE(HasUnverifiedClass("LMyVerificationFailure;"));
+  // Test that a class with unresolved super is recorded.
+  ASSERT_FALSE(HasUnverifiedClass("LMyClassWithNoSuper;"));
+  // Test that a class with unresolved super and hard failure is recorded.
+  ASSERT_TRUE(HasUnverifiedClass("LMyClassWithNoSuperButFailures;"));
+}
+
 }  // namespace verifier
 }  // namespace art
diff --git a/runtime/Android.bp b/runtime/Android.bp
index 6945eb0..b498573 100644
--- a/runtime/Android.bp
+++ b/runtime/Android.bp
@@ -565,7 +565,6 @@
         "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/class_linker.cc b/runtime/class_linker.cc
index 3ae36de..c23b1b1 100644
--- a/runtime/class_linker.cc
+++ b/runtime/class_linker.cc
@@ -3730,9 +3730,8 @@
   return false;
 }
 
-void ClassLinker::VerifyClass(Thread* self,
-                              Handle<mirror::Class> klass,
-                              verifier::HardFailLogMode log_level) {
+verifier::MethodVerifier::FailureKind ClassLinker::VerifyClass(
+    Thread* self, Handle<mirror::Class> klass, verifier::HardFailLogMode log_level) {
   {
     // TODO: assert that the monitor on the Class is held
     ObjectLock<mirror::Class> lock(self, klass);
@@ -3753,16 +3752,16 @@
     // this class as a parent to another.
     if (klass->IsErroneous()) {
       ThrowEarlierClassFailure(klass.Get());
-      return;
+      return verifier::MethodVerifier::kHardFailure;
     }
 
     // Don't attempt to re-verify if already sufficiently verified.
     if (klass->IsVerified()) {
       EnsureSkipAccessChecksMethods(klass);
-      return;
+      return verifier::MethodVerifier::kNoFailure;
     }
     if (klass->IsCompileTimeVerified() && Runtime::Current()->IsAotCompiler()) {
-      return;
+      return verifier::MethodVerifier::kNoFailure;
     }
 
     if (klass->GetStatus() == mirror::Class::kStatusResolved) {
@@ -3778,7 +3777,7 @@
     if (!Runtime::Current()->IsVerificationEnabled()) {
       mirror::Class::SetStatus(klass, mirror::Class::kStatusVerified, self);
       EnsureSkipAccessChecksMethods(klass);
-      return;
+      return verifier::MethodVerifier::kNoFailure;
     }
   }
 
@@ -3788,7 +3787,7 @@
   // If we have a superclass and we get a hard verification failure we can return immediately.
   if (supertype.Get() != nullptr && !AttemptSupertypeVerification(self, klass, supertype)) {
     CHECK(self->IsExceptionPending()) << "Verification error should be pending.";
-    return;
+    return verifier::MethodVerifier::kHardFailure;
   }
 
   // Verify all default super-interfaces.
@@ -3815,7 +3814,7 @@
       } else if (UNLIKELY(!AttemptSupertypeVerification(self, klass, iface))) {
         // We had a hard failure while verifying this interface. Just return immediately.
         CHECK(self->IsExceptionPending()) << "Verification error should be pending.";
-        return;
+        return verifier::MethodVerifier::kHardFailure;
       } else if (UNLIKELY(!iface->IsVerified())) {
         // We softly failed to verify the iface. Stop checking and clean up.
         // Put the iface into the supertype handle so we know what caused us to fail.
@@ -3841,8 +3840,8 @@
   //     oat_file_class_status == mirror::Class::kStatusError => !preverified
   DCHECK(!(oat_file_class_status == mirror::Class::kStatusError) || !preverified);
 
-  verifier::MethodVerifier::FailureKind verifier_failure = verifier::MethodVerifier::kNoFailure;
   std::string error_msg;
+  verifier::MethodVerifier::FailureKind verifier_failure = verifier::MethodVerifier::kNoFailure;
   if (!preverified) {
     Runtime* runtime = Runtime::Current();
     verifier_failure = verifier::MethodVerifier::VerifyClass(self,
@@ -3915,6 +3914,7 @@
       EnsureSkipAccessChecksMethods(klass);
     }
   }
+  return verifier_failure;
 }
 
 void ClassLinker::EnsureSkipAccessChecksMethods(Handle<mirror::Class> klass) {
diff --git a/runtime/class_linker.h b/runtime/class_linker.h
index f2bf581..e99dfe3 100644
--- a/runtime/class_linker.h
+++ b/runtime/class_linker.h
@@ -36,6 +36,7 @@
 #include "jni.h"
 #include "mirror/class.h"
 #include "object_callbacks.h"
+#include "verifier/method_verifier.h"
 #include "verifier/verifier_log_mode.h"
 
 namespace art {
@@ -470,9 +471,10 @@
       REQUIRES_SHARED(Locks::mutator_lock_)
       REQUIRES(!Roles::uninterruptible_);
 
-  void VerifyClass(Thread* self,
-                   Handle<mirror::Class> klass,
-                   verifier::HardFailLogMode log_level = verifier::HardFailLogMode::kLogNone)
+  verifier::MethodVerifier::FailureKind VerifyClass(
+      Thread* self,
+      Handle<mirror::Class> klass,
+      verifier::HardFailLogMode log_level = verifier::HardFailLogMode::kLogNone)
       REQUIRES_SHARED(Locks::mutator_lock_)
       REQUIRES(!dex_lock_);
   bool VerifyClassUsingOatFile(const DexFile& dex_file,
diff --git a/runtime/verifier/verifier_deps.cc b/runtime/verifier/verifier_deps.cc
index 3c7fb7a..4d1e337 100644
--- a/runtime/verifier/verifier_deps.cc
+++ b/runtime/verifier/verifier_deps.cc
@@ -280,6 +280,22 @@
   return callbacks->GetVerifierDeps();
 }
 
+void VerifierDeps::MaybeRecordVerificationStatus(const DexFile& dex_file,
+                                                 uint16_t type_idx,
+                                                 MethodVerifier::FailureKind failure_kind) {
+  if (failure_kind == MethodVerifier::kNoFailure) {
+    // We only record classes that did not fully verify at compile time.
+    return;
+  }
+
+  VerifierDeps* singleton = GetVerifierDepsSingleton();
+  if (singleton != nullptr) {
+    DexFileDeps* dex_deps = singleton->GetDexFileDeps(dex_file);
+    MutexLock mu(Thread::Current(), *Locks::verifier_deps_lock_);
+    dex_deps->unverified_classes_.push_back(type_idx);
+  }
+}
+
 void VerifierDeps::MaybeRecordClassResolution(const DexFile& dex_file,
                                               uint16_t type_idx,
                                               mirror::Class* klass) {
@@ -360,6 +376,14 @@
   }
 }
 
+static inline void EncodeUint16Vector(std::vector<uint8_t>* out,
+                                      const std::vector<uint16_t>& vector) {
+  EncodeUnsignedLeb128(out, vector.size());
+  for (uint16_t entry : vector) {
+    EncodeUnsignedLeb128(out, entry);
+  }
+}
+
 template<typename T>
 static inline void DecodeSet(const uint8_t** in, const uint8_t* end, std::set<T>* set) {
   DCHECK(set->empty());
@@ -371,6 +395,17 @@
   }
 }
 
+static inline void DecodeUint16Vector(const uint8_t** in,
+                                      const uint8_t* end,
+                                      std::vector<uint16_t>* vector) {
+  DCHECK(vector->empty());
+  size_t num_entries = DecodeUint32WithOverflowCheck(in, end);
+  vector->reserve(num_entries);
+  for (size_t i = 0; i < num_entries; ++i) {
+    vector->push_back(dchecked_integral_cast<uint16_t>(DecodeUint32WithOverflowCheck(in, end)));
+  }
+}
+
 static inline void EncodeStringVector(std::vector<uint8_t>* out,
                                       const std::vector<std::string>& strings) {
   EncodeUnsignedLeb128(out, strings.size());
@@ -407,6 +442,7 @@
     EncodeSet(buffer, entry.second->direct_methods_);
     EncodeSet(buffer, entry.second->virtual_methods_);
     EncodeSet(buffer, entry.second->interface_methods_);
+    EncodeUint16Vector(buffer, entry.second->unverified_classes_);
   }
 }
 
@@ -423,6 +459,7 @@
     DecodeSet(&data_start, data_end, &entry.second->direct_methods_);
     DecodeSet(&data_start, data_end, &entry.second->virtual_methods_);
     DecodeSet(&data_start, data_end, &entry.second->interface_methods_);
+    DecodeUint16Vector(&data_start, data_end, &entry.second->unverified_classes_);
   }
   CHECK_LE(data_start, data_end);
 }
@@ -463,7 +500,8 @@
          (fields_ == rhs.fields_) &&
          (direct_methods_ == rhs.direct_methods_) &&
          (virtual_methods_ == rhs.virtual_methods_) &&
-         (interface_methods_ == rhs.interface_methods_);
+         (interface_methods_ == rhs.interface_methods_) &&
+         (unverified_classes_ == rhs.unverified_classes_);
 }
 
 }  // namespace verifier
diff --git a/runtime/verifier/verifier_deps.h b/runtime/verifier/verifier_deps.h
index 3223f6f..9d2622d 100644
--- a/runtime/verifier/verifier_deps.h
+++ b/runtime/verifier/verifier_deps.h
@@ -26,6 +26,7 @@
 #include "base/array_ref.h"
 #include "base/mutex.h"
 #include "method_resolution_kind.h"
+#include "method_verifier.h"  // For MethodVerifier::FailureKind.
 #include "obj_ptr.h"
 #include "os.h"
 
@@ -49,6 +50,12 @@
   explicit VerifierDeps(const std::vector<const DexFile*>& dex_files)
       REQUIRES(!Locks::verifier_deps_lock_);
 
+  // Record the verification status of the class at `type_idx`.
+  static void MaybeRecordVerificationStatus(const DexFile& dex_file,
+                                            uint16_t type_idx,
+                                            MethodVerifier::FailureKind failure_kind)
+      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,
@@ -136,7 +143,7 @@
   };
 
   using TypeAssignabilityBase = std::tuple<uint32_t, uint32_t>;
-  struct TypeAssignability : public std::tuple<uint32_t, uint32_t> {
+  struct TypeAssignability : public TypeAssignabilityBase {
     TypeAssignability() = default;
     TypeAssignability(const TypeAssignability&) = default;
     TypeAssignability(uint32_t destination_idx, uint32_t source_idx)
@@ -165,6 +172,9 @@
     std::set<MethodResolution> virtual_methods_;
     std::set<MethodResolution> interface_methods_;
 
+    // List of classes that were not fully verified in that dex file.
+    std::vector<uint16_t> unverified_classes_;
+
     bool Equals(const DexFileDeps& rhs) const;
   };