diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index 4f273e5..c785bef 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -105,7 +105,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
+ART_GTEST_verifier_deps_test_DEX_DEPS := VerifierDeps MultiDex
 
 # 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)
diff --git a/compiler/oat_writer.cc b/compiler/oat_writer.cc
index 6cbca7a..f9173f5 100644
--- a/compiler/oat_writer.cc
+++ b/compiler/oat_writer.cc
@@ -1759,7 +1759,7 @@
   }
 
   std::vector<uint8_t> buffer;
-  verifier_deps->Encode(&buffer);
+  verifier_deps->Encode(*dex_files_, &buffer);
 
   if (!vdex_out->WriteFully(buffer.data(), buffer.size())) {
     PLOG(ERROR) << "Failed to write verifier deps."
diff --git a/compiler/verifier_deps_test.cc b/compiler/verifier_deps_test.cc
index 9664e43..cd6ca4c 100644
--- a/compiler/verifier_deps_test.cc
+++ b/compiler/verifier_deps_test.cc
@@ -79,17 +79,24 @@
     callbacks->SetVerifierDeps(verifier_deps_.get());
   }
 
+  void LoadDexFile(ScopedObjectAccess* soa, const char* name1, const char* name2 = nullptr)
+      REQUIRES_SHARED(Locks::mutator_lock_) {
+    class_loader_ = (name2 == nullptr) ? LoadDex(name1) : LoadMultiDex(name1, name2);
+    dex_files_ = GetDexFiles(class_loader_);
+    primary_dex_file_ = dex_files_.front();
+
+    SetVerifierDeps(dex_files_);
+    StackHandleScope<1> hs(soa->Self());
+    Handle<mirror::ClassLoader> loader =
+        hs.NewHandle(soa->Decode<mirror::ClassLoader>(class_loader_));
+    for (const DexFile* dex_file : dex_files_) {
+      class_linker_->RegisterDexFile(*dex_file, loader.Get());
+    }
+  }
+
   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();
-
-    SetVerifierDeps(dex_files);
-
-    ObjPtr<mirror::ClassLoader> loader = soa->Decode<mirror::ClassLoader>(class_loader_);
-    class_linker_->RegisterDexFile(*dex_file_, loader.Ptr());
-
+    LoadDexFile(soa, "VerifierDeps");
+    CHECK_EQ(dex_files_.size(), 1u);
     klass_Main_ = FindClassByName("LMain;", soa);
     CHECK(klass_Main_ != nullptr);
   }
@@ -98,16 +105,16 @@
     ScopedObjectAccess soa(Thread::Current());
     LoadDexFile(&soa);
 
-    StackHandleScope<2> hs(Thread::Current());
+    StackHandleScope<2> hs(soa.Self());
     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);
+    const uint8_t* class_data = primary_dex_file_->GetClassData(*class_def);
     CHECK(class_data != nullptr);
 
-    ClassDataItemIterator it(*dex_file_, class_data);
+    ClassDataItemIterator it(*primary_dex_file_, class_data);
     while (it.HasNextStaticField() || it.HasNextInstanceField()) {
       it.Next();
     }
@@ -115,7 +122,7 @@
     ArtMethod* method = nullptr;
     while (it.HasNextDirectMethod()) {
       ArtMethod* resolved_method = class_linker_->ResolveMethod<ClassLinker::kNoICCECheckForCache>(
-          *dex_file_,
+          *primary_dex_file_,
           it.GetMemberIndex(),
           dex_cache_handle,
           class_loader_handle,
@@ -131,7 +138,7 @@
     CHECK(method != nullptr);
 
     MethodVerifier verifier(Thread::Current(),
-                            dex_file_,
+                            primary_dex_file_,
                             dex_cache_handle,
                             class_loader_handle,
                             *class_def,
@@ -148,19 +155,16 @@
     return !verifier.HasFailures();
   }
 
-  void VerifyDexFile() {
+  void VerifyDexFile(const char* multidex = nullptr) {
     std::string error_msg;
     {
       ScopedObjectAccess soa(Thread::Current());
-      LoadDexFile(&soa);
+      LoadDexFile(&soa, "VerifierDeps", multidex);
     }
-    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);
+    compiler_driver_->Verify(class_loader_, dex_files_, &timings);
   }
 
   bool TestAssignabilityRecording(const std::string& dst,
@@ -173,7 +177,7 @@
     DCHECK(klass_dst != nullptr);
     mirror::Class* klass_src = FindClassByName(src, &soa);
     DCHECK(klass_src != nullptr);
-    verifier_deps_->AddAssignability(*dex_file_,
+    verifier_deps_->AddAssignability(*primary_dex_file_,
                                      klass_dst,
                                      klass_src,
                                      is_strict,
@@ -182,9 +186,9 @@
   }
 
   bool HasUnverifiedClass(const std::string& cls) {
-    const DexFile::TypeId* type_id = dex_file_->FindTypeId(cls.c_str());
+    const DexFile::TypeId* type_id = primary_dex_file_->FindTypeId(cls.c_str());
     DCHECK(type_id != nullptr);
-    uint16_t index = dex_file_->GetIndexForTypeId(*type_id);
+    uint16_t index = primary_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_) {
@@ -396,7 +400,8 @@
   }
 
   std::unique_ptr<verifier::VerifierDeps> verifier_deps_;
-  const DexFile* dex_file_;
+  std::vector<const DexFile*> dex_files_;
+  const DexFile* primary_dex_file_;
   jobject class_loader_;
   mirror::Class* klass_Main_;
 };
@@ -407,21 +412,21 @@
 
   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_Main1 = verifier_deps_->GetIdFromString(*primary_dex_file_, "LMain;");
+  ASSERT_LT(id_Main1, primary_dex_file_->NumStringIds());
+  ASSERT_EQ("LMain;", verifier_deps_->GetStringFromId(*primary_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_Main2 = verifier_deps_->GetIdFromString(*primary_dex_file_, "LMain;");
+  ASSERT_LT(id_Main2, primary_dex_file_->NumStringIds());
+  ASSERT_EQ("LMain;", verifier_deps_->GetStringFromId(*primary_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_Lorem1 = verifier_deps_->GetIdFromString(*primary_dex_file_, "Lorem ipsum");
+  ASSERT_GE(id_Lorem1, primary_dex_file_->NumStringIds());
+  ASSERT_EQ("Lorem ipsum", verifier_deps_->GetStringFromId(*primary_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));
+  uint32_t id_Lorem2 = verifier_deps_->GetIdFromString(*primary_dex_file_, "Lorem ipsum");
+  ASSERT_GE(id_Lorem2, primary_dex_file_->NumStringIds());
+  ASSERT_EQ("Lorem ipsum", verifier_deps_->GetStringFromId(*primary_dex_file_, id_Lorem2));
 
   ASSERT_EQ(id_Main1, id_Main2);
   ASSERT_EQ(id_Lorem1, id_Lorem2);
@@ -1068,13 +1073,41 @@
   ASSERT_TRUE(HasEachKindOfRecord());
 
   std::vector<uint8_t> buffer;
-  verifier_deps_->Encode(&buffer);
+  verifier_deps_->Encode(dex_files_, &buffer);
   ASSERT_FALSE(buffer.empty());
 
-  VerifierDeps decoded_deps({ dex_file_ }, ArrayRef<uint8_t>(buffer));
+  VerifierDeps decoded_deps(dex_files_, ArrayRef<uint8_t>(buffer));
   ASSERT_TRUE(verifier_deps_->Equals(decoded_deps));
 }
 
+TEST_F(VerifierDepsTest, EncodeDecodeMulti) {
+  VerifyDexFile("MultiDex");
+
+  ASSERT_GT(NumberOfCompiledDexFiles(), 1u);
+  std::vector<uint8_t> buffer;
+  verifier_deps_->Encode(dex_files_, &buffer);
+  ASSERT_FALSE(buffer.empty());
+
+  // Create new DexFile, to mess with std::map order: the verifier deps used
+  // to iterate over the map, which doesn't guarantee insertion order. We fixed
+  // this by passing the expected order when encoding/decoding.
+  std::vector<std::unique_ptr<const DexFile>> first_dex_files = OpenTestDexFiles("VerifierDeps");
+  std::vector<std::unique_ptr<const DexFile>> second_dex_files = OpenTestDexFiles("MultiDex");
+  std::vector<const DexFile*> dex_files;
+  for (auto& dex_file : first_dex_files) {
+    dex_files.push_back(dex_file.get());
+  }
+  for (auto& dex_file : second_dex_files) {
+    dex_files.push_back(dex_file.get());
+  }
+
+  // Dump the new verifier deps to ensure it can properly read the data.
+  VerifierDeps decoded_deps(dex_files, ArrayRef<uint8_t>(buffer));
+  std::ostringstream stream;
+  VariableIndentationOutputStream os(&stream);
+  decoded_deps.Dump(&os);
+}
+
 TEST_F(VerifierDepsTest, UnverifiedClasses) {
   VerifyDexFile();
   ASSERT_FALSE(HasUnverifiedClass("LMyThread;"));
diff --git a/runtime/common_runtime_test.cc b/runtime/common_runtime_test.cc
index 5409fcb..d929812 100644
--- a/runtime/common_runtime_test.cc
+++ b/runtime/common_runtime_test.cc
@@ -572,6 +572,29 @@
   return ret;
 }
 
+jobject CommonRuntimeTestImpl::LoadMultiDex(const char* first_dex_name,
+                                            const char* second_dex_name) {
+  std::vector<std::unique_ptr<const DexFile>> first_dex_files = OpenTestDexFiles(first_dex_name);
+  std::vector<std::unique_ptr<const DexFile>> second_dex_files = OpenTestDexFiles(second_dex_name);
+  std::vector<const DexFile*> class_path;
+  CHECK_NE(0U, first_dex_files.size());
+  CHECK_NE(0U, second_dex_files.size());
+  for (auto& dex_file : first_dex_files) {
+    class_path.push_back(dex_file.get());
+    loaded_dex_files_.push_back(std::move(dex_file));
+  }
+  for (auto& dex_file : second_dex_files) {
+    class_path.push_back(dex_file.get());
+    loaded_dex_files_.push_back(std::move(dex_file));
+  }
+
+  Thread* self = Thread::Current();
+  jobject class_loader = Runtime::Current()->GetClassLinker()->CreatePathClassLoader(self,
+                                                                                     class_path);
+  self->SetClassLoaderOverride(class_loader);
+  return class_loader;
+}
+
 jobject CommonRuntimeTestImpl::LoadDex(const char* dex_name) {
   std::vector<std::unique_ptr<const DexFile>> dex_files = OpenTestDexFiles(dex_name);
   std::vector<const DexFile*> class_path;
diff --git a/runtime/common_runtime_test.h b/runtime/common_runtime_test.h
index 92934c6..827e85e 100644
--- a/runtime/common_runtime_test.h
+++ b/runtime/common_runtime_test.h
@@ -133,6 +133,8 @@
       REQUIRES_SHARED(Locks::mutator_lock_);
 
   jobject LoadDex(const char* dex_name) REQUIRES_SHARED(Locks::mutator_lock_);
+  jobject LoadMultiDex(const char* first_dex_name, const char* second_dex_name)
+      REQUIRES_SHARED(Locks::mutator_lock_);
 
   std::string android_data_;
   std::string dalvik_cache_;
diff --git a/runtime/verifier/verifier_deps.cc b/runtime/verifier/verifier_deps.cc
index 4d1e337..6970871 100644
--- a/runtime/verifier/verifier_deps.cc
+++ b/runtime/verifier/verifier_deps.cc
@@ -39,6 +39,11 @@
   return (it == dex_deps_.end()) ? nullptr : it->second.get();
 }
 
+const VerifierDeps::DexFileDeps* VerifierDeps::GetDexFileDeps(const DexFile& dex_file) const {
+  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");
@@ -95,12 +100,12 @@
   return new_id;
 }
 
-std::string VerifierDeps::GetStringFromId(const DexFile& dex_file, uint32_t string_id) {
+std::string VerifierDeps::GetStringFromId(const DexFile& dex_file, uint32_t string_id) const {
   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);
+    const DexFileDeps* deps = GetDexFileDeps(dex_file);
     DCHECK(deps != nullptr);
     string_id -= num_ids_in_dex;
     CHECK_LT(string_id, deps->strings_.size());
@@ -108,7 +113,7 @@
   }
 }
 
-bool VerifierDeps::IsInClassPath(ObjPtr<mirror::Class> klass) {
+bool VerifierDeps::IsInClassPath(ObjPtr<mirror::Class> klass) const {
   DCHECK(klass != nullptr);
 
   ObjPtr<mirror::DexCache> dex_cache = klass->GetDexCache();
@@ -431,18 +436,20 @@
   }
 }
 
-void VerifierDeps::Encode(std::vector<uint8_t>* buffer) const {
+void VerifierDeps::Encode(const std::vector<const DexFile*>& dex_files,
+                          std::vector<uint8_t>* buffer) const {
   MutexLock mu(Thread::Current(), *Locks::verifier_deps_lock_);
-  for (auto& entry : dex_deps_) {
-    EncodeStringVector(buffer, entry.second->strings_);
-    EncodeSet(buffer, entry.second->assignable_types_);
-    EncodeSet(buffer, entry.second->unassignable_types_);
-    EncodeSet(buffer, entry.second->classes_);
-    EncodeSet(buffer, entry.second->fields_);
-    EncodeSet(buffer, entry.second->direct_methods_);
-    EncodeSet(buffer, entry.second->virtual_methods_);
-    EncodeSet(buffer, entry.second->interface_methods_);
-    EncodeUint16Vector(buffer, entry.second->unverified_classes_);
+  for (const DexFile* dex_file : dex_files) {
+    const DexFileDeps& deps = *GetDexFileDeps(*dex_file);
+    EncodeStringVector(buffer, deps.strings_);
+    EncodeSet(buffer, deps.assignable_types_);
+    EncodeSet(buffer, deps.unassignable_types_);
+    EncodeSet(buffer, deps.classes_);
+    EncodeSet(buffer, deps.fields_);
+    EncodeSet(buffer, deps.direct_methods_);
+    EncodeSet(buffer, deps.virtual_methods_);
+    EncodeSet(buffer, deps.interface_methods_);
+    EncodeUint16Vector(buffer, deps.unverified_classes_);
   }
 }
 
@@ -450,16 +457,17 @@
     : VerifierDeps(dex_files) {
   const uint8_t* data_start = data.data();
   const uint8_t* data_end = data_start + data.size();
-  for (auto& entry : dex_deps_) {
-    DecodeStringVector(&data_start, data_end, &entry.second->strings_);
-    DecodeSet(&data_start, data_end, &entry.second->assignable_types_);
-    DecodeSet(&data_start, data_end, &entry.second->unassignable_types_);
-    DecodeSet(&data_start, data_end, &entry.second->classes_);
-    DecodeSet(&data_start, data_end, &entry.second->fields_);
-    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_);
+  for (const DexFile* dex_file : dex_files) {
+    DexFileDeps* deps = GetDexFileDeps(*dex_file);
+    DecodeStringVector(&data_start, data_end, &deps->strings_);
+    DecodeSet(&data_start, data_end, &deps->assignable_types_);
+    DecodeSet(&data_start, data_end, &deps->unassignable_types_);
+    DecodeSet(&data_start, data_end, &deps->classes_);
+    DecodeSet(&data_start, data_end, &deps->fields_);
+    DecodeSet(&data_start, data_end, &deps->direct_methods_);
+    DecodeSet(&data_start, data_end, &deps->virtual_methods_);
+    DecodeSet(&data_start, data_end, &deps->interface_methods_);
+    DecodeUint16Vector(&data_start, data_end, &deps->unverified_classes_);
   }
   CHECK_LE(data_start, data_end);
 }
@@ -504,5 +512,93 @@
          (unverified_classes_ == rhs.unverified_classes_);
 }
 
+void VerifierDeps::Dump(VariableIndentationOutputStream* vios) const {
+  for (const auto& dep : dex_deps_) {
+    const DexFile& dex_file = *dep.first;
+    vios->Stream()
+        << "Dependencies of "
+        << dex_file.GetLocation()
+        << ":\n";
+
+    ScopedIndentation indent(vios);
+
+    for (const std::string& str : dep.second->strings_) {
+      vios->Stream() << "Extra string: " << str << "\n";
+    }
+
+    for (const TypeAssignability& entry : dep.second->assignable_types_) {
+      vios->Stream()
+        << GetStringFromId(dex_file, entry.GetSource())
+        << " must be assignable to "
+        << GetStringFromId(dex_file, entry.GetDestination())
+        << "\n";
+    }
+
+    for (const TypeAssignability& entry : dep.second->unassignable_types_) {
+      vios->Stream()
+        << GetStringFromId(dex_file, entry.GetSource())
+        << " must not be assignable to "
+        << GetStringFromId(dex_file, entry.GetDestination())
+        << "\n";
+    }
+
+    for (const ClassResolution& entry : dep.second->classes_) {
+      vios->Stream()
+          << dex_file.StringByTypeIdx(entry.GetDexTypeIndex())
+          << (entry.IsResolved() ? " must be resolved " : "must not be resolved ")
+          << " with access flags " << std::hex << entry.GetAccessFlags() << std::dec
+          << "\n";
+    }
+
+    for (const FieldResolution& entry : dep.second->fields_) {
+      const DexFile::FieldId& field_id = dex_file.GetFieldId(entry.GetDexFieldIndex());
+      vios->Stream()
+          << dex_file.GetFieldDeclaringClassDescriptor(field_id) << "->"
+          << dex_file.GetFieldName(field_id) << ":"
+          << dex_file.GetFieldTypeDescriptor(field_id)
+          << " is expected to be ";
+      if (!entry.IsResolved()) {
+        vios->Stream() << "unresolved\n";
+      } else {
+        vios->Stream()
+          << "in class "
+          << GetStringFromId(dex_file, entry.GetDeclaringClassIndex())
+          << ", and have the access flags " << std::hex << entry.GetAccessFlags() << std::dec
+          << "\n";
+      }
+    }
+
+    for (const auto& entry :
+            { std::make_pair(kDirectMethodResolution, dep.second->direct_methods_),
+              std::make_pair(kVirtualMethodResolution, dep.second->virtual_methods_),
+              std::make_pair(kInterfaceMethodResolution, dep.second->interface_methods_) }) {
+      for (const MethodResolution& method : entry.second) {
+        const DexFile::MethodId& method_id = dex_file.GetMethodId(method.GetDexMethodIndex());
+        vios->Stream()
+            << dex_file.GetMethodDeclaringClassDescriptor(method_id) << "->"
+            << dex_file.GetMethodName(method_id)
+            << dex_file.GetMethodSignature(method_id).ToString()
+            << " is expected to be ";
+        if (!method.IsResolved()) {
+          vios->Stream() << "unresolved\n";
+        } else {
+          vios->Stream()
+            << "in class "
+            << GetStringFromId(dex_file, method.GetDeclaringClassIndex())
+            << ", have the access flags " << std::hex << method.GetAccessFlags() << std::dec
+            << ", and be of kind " << entry.first
+            << "\n";
+        }
+      }
+    }
+
+    for (uint16_t type_index : dep.second->unverified_classes_) {
+      vios->Stream()
+          << dex_file.StringByTypeIdx(type_index)
+          << " is expected to be verified at runtime\n";
+    }
+  }
+}
+
 }  // namespace verifier
 }  // namespace art
diff --git a/runtime/verifier/verifier_deps.h b/runtime/verifier/verifier_deps.h
index 9d2622d..6b0c959 100644
--- a/runtime/verifier/verifier_deps.h
+++ b/runtime/verifier/verifier_deps.h
@@ -25,6 +25,7 @@
 #include "art_method.h"
 #include "base/array_ref.h"
 #include "base/mutex.h"
+#include "indenter.h"
 #include "method_resolution_kind.h"
 #include "method_verifier.h"  // For MethodVerifier::FailureKind.
 #include "obj_ptr.h"
@@ -94,9 +95,16 @@
       REQUIRES(!Locks::verifier_deps_lock_);
 
   // Serialize the recorded dependencies and store the data into `buffer`.
-  void Encode(std::vector<uint8_t>* buffer) const
+  // `dex_files` provides the order of the dex files in which the dependencies
+  // should be emitted.
+  void Encode(const std::vector<const DexFile*>& dex_files, std::vector<uint8_t>* buffer) const
       REQUIRES(!Locks::verifier_deps_lock_);
 
+  // NO_THREAD_SAFETY_ANALYSIS as Dump iterates over dex_deps_, which is guarded by
+  // verifier_deps_lock_, but we expect Dump to be called once the deps collection is done.
+  void Dump(VariableIndentationOutputStream* vios) const
+      NO_THREAD_SAFETY_ANALYSIS;
+
  private:
   static constexpr uint16_t kUnresolvedMarker = static_cast<uint16_t>(-1);
 
@@ -185,9 +193,12 @@
   DexFileDeps* GetDexFileDeps(const DexFile& dex_file)
       NO_THREAD_SAFETY_ANALYSIS;
 
+  const DexFileDeps* GetDexFileDeps(const DexFile& dex_file) const
+      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(ObjPtr<mirror::Class> klass)
+  bool IsInClassPath(ObjPtr<mirror::Class> klass) const
       REQUIRES_SHARED(Locks::mutator_lock_);
 
   // Returns the index of `str`. If it is defined in `dex_file_`, this is the dex
@@ -198,13 +209,13 @@
       REQUIRES(Locks::verifier_deps_lock_);
 
   // Returns the string represented by `id`.
-  std::string GetStringFromId(const DexFile& dex_file, uint32_t string_id)
+  std::string GetStringFromId(const DexFile& dex_file, uint32_t string_id) const
       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)
+  static uint16_t GetAccessFlags(T* element)
       REQUIRES_SHARED(Locks::mutator_lock_);
 
   // Returns a string ID of the descriptor of the declaring class of `element`,
@@ -251,6 +262,7 @@
   friend class VerifierDepsTest;
   ART_FRIEND_TEST(VerifierDepsTest, StringToId);
   ART_FRIEND_TEST(VerifierDepsTest, EncodeDecode);
+  ART_FRIEND_TEST(VerifierDepsTest, EncodeDecodeMulti);
 };
 
 }  // namespace verifier