diff --git a/runtime/base/mutex.cc b/runtime/base/mutex.cc
index 5d92298..0970abd 100644
--- a/runtime/base/mutex.cc
+++ b/runtime/base/mutex.cc
@@ -48,7 +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::verifier_deps_lock_ = nullptr;
 ReaderWriterMutex* Locks::oat_file_manager_lock_ = nullptr;
 Mutex* Locks::host_dlopen_handles_lock_ = nullptr;
 Mutex* Locks::reference_processor_lock_ = nullptr;
@@ -1039,7 +1039,7 @@
 
     UPDATE_CURRENT_LOCK_LEVEL(kVerifierDepsLock);
     DCHECK(verifier_deps_lock_ == nullptr);
-    verifier_deps_lock_ = new Mutex("verifier deps lock", current_lock_level);
+    verifier_deps_lock_ = new ReaderWriterMutex("verifier deps lock", current_lock_level);
 
     UPDATE_CURRENT_LOCK_LEVEL(kHostDlOpenHandlesLock);
     DCHECK(host_dlopen_handles_lock_ == nullptr);
diff --git a/runtime/base/mutex.h b/runtime/base/mutex.h
index 74b786c..7e73e0d 100644
--- a/runtime/base/mutex.h
+++ b/runtime/base/mutex.h
@@ -658,8 +658,8 @@
   // 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 extra string entries for VerifierDeps.
+  static ReaderWriterMutex* verifier_deps_lock_ ACQUIRED_AFTER(oat_file_manager_lock_);
 
   // Guards dlopen_handles_ in DlOpenOatFile.
   static Mutex* host_dlopen_handles_lock_ ACQUIRED_AFTER(verifier_deps_lock_);
diff --git a/runtime/base/stl_util.h b/runtime/base/stl_util.h
index a53dcea..d5f375a 100644
--- a/runtime/base/stl_util.h
+++ b/runtime/base/stl_util.h
@@ -18,6 +18,7 @@
 #define ART_RUNTIME_BASE_STL_UTIL_H_
 
 #include <algorithm>
+#include <set>
 #include <sstream>
 
 #include "base/logging.h"
@@ -187,6 +188,12 @@
   using type = T;
 };
 
+// Merge `other` entries into `to_update`.
+template <typename T>
+static inline void MergeSets(std::set<T>& to_update, const std::set<T>& other) {
+  to_update.insert(other.begin(), other.end());
+}
+
 }  // namespace art
 
 #endif  // ART_RUNTIME_BASE_STL_UTIL_H_
diff --git a/runtime/entrypoints_order_test.cc b/runtime/entrypoints_order_test.cc
index b0463d7..1283660 100644
--- a/runtime/entrypoints_order_test.cc
+++ b/runtime/entrypoints_order_test.cc
@@ -94,8 +94,8 @@
     EXPECT_OFFSET_DIFFP(Thread, tlsPtr_, opeer, jpeer, sizeof(void*));
     EXPECT_OFFSET_DIFFP(Thread, tlsPtr_, jpeer, stack_begin, sizeof(void*));
     EXPECT_OFFSET_DIFFP(Thread, tlsPtr_, stack_begin, stack_size, sizeof(void*));
-    EXPECT_OFFSET_DIFFP(Thread, tlsPtr_, stack_size, stack_trace_sample, sizeof(void*));
-    EXPECT_OFFSET_DIFFP(Thread, tlsPtr_, stack_trace_sample, wait_next, sizeof(void*));
+    EXPECT_OFFSET_DIFFP(Thread, tlsPtr_, stack_size, deps_or_stack_trace_sample, sizeof(void*));
+    EXPECT_OFFSET_DIFFP(Thread, tlsPtr_, deps_or_stack_trace_sample, wait_next, sizeof(void*));
     EXPECT_OFFSET_DIFFP(Thread, tlsPtr_, wait_next, monitor_enter_object, sizeof(void*));
     EXPECT_OFFSET_DIFFP(Thread, tlsPtr_, monitor_enter_object, top_handle_scope, sizeof(void*));
     EXPECT_OFFSET_DIFFP(Thread, tlsPtr_, top_handle_scope, class_loader_override, sizeof(void*));
diff --git a/runtime/thread.cc b/runtime/thread.cc
index b99df26..65c8681 100644
--- a/runtime/thread.cc
+++ b/runtime/thread.cc
@@ -1900,7 +1900,7 @@
   }
   delete tlsPtr_.instrumentation_stack;
   delete tlsPtr_.name;
-  delete tlsPtr_.stack_trace_sample;
+  delete tlsPtr_.deps_or_stack_trace_sample.stack_trace_sample;
   free(tlsPtr_.nested_signal_state);
 
   Runtime::Current()->GetHeap()->AssertThreadLocalBuffersAreRevoked(this);
diff --git a/runtime/thread.h b/runtime/thread.h
index b2983cc..3f13db1 100644
--- a/runtime/thread.h
+++ b/runtime/thread.h
@@ -70,7 +70,8 @@
 }  // namespace mirror
 
 namespace verifier {
-class MethodVerifier;
+  class MethodVerifier;
+  class VerifierDeps;
 }  // namespace verifier
 
 class ArtMethod;
@@ -947,11 +948,25 @@
   }
 
   std::vector<ArtMethod*>* GetStackTraceSample() const {
-    return tlsPtr_.stack_trace_sample;
+    return tlsPtr_.deps_or_stack_trace_sample.stack_trace_sample;
   }
 
   void SetStackTraceSample(std::vector<ArtMethod*>* sample) {
-    tlsPtr_.stack_trace_sample = sample;
+    DCHECK(sample == nullptr || tlsPtr_.deps_or_stack_trace_sample.verifier_deps == nullptr);
+    tlsPtr_.deps_or_stack_trace_sample.stack_trace_sample = sample;
+  }
+
+  verifier::VerifierDeps* GetVerifierDeps() const {
+    return tlsPtr_.deps_or_stack_trace_sample.verifier_deps;
+  }
+
+  // It is the responsability of the caller to make sure the verifier_deps
+  // entry in the thread is cleared before destruction of the actual VerifierDeps
+  // object, or the thread.
+  void SetVerifierDeps(verifier::VerifierDeps* verifier_deps) {
+    DCHECK(verifier_deps == nullptr ||
+           tlsPtr_.deps_or_stack_trace_sample.stack_trace_sample == nullptr);
+    tlsPtr_.deps_or_stack_trace_sample.verifier_deps = verifier_deps;
   }
 
   uint64_t GetTraceClockBase() const {
@@ -1378,7 +1393,7 @@
       tls_ptr_sized_values() : card_table(nullptr), exception(nullptr), stack_end(nullptr),
       managed_stack(), suspend_trigger(nullptr), jni_env(nullptr), tmp_jni_env(nullptr),
       self(nullptr), opeer(nullptr), jpeer(nullptr), stack_begin(nullptr), stack_size(0),
-      stack_trace_sample(nullptr), wait_next(nullptr), monitor_enter_object(nullptr),
+      deps_or_stack_trace_sample(), wait_next(nullptr), monitor_enter_object(nullptr),
       top_handle_scope(nullptr), class_loader_override(nullptr), long_jump_context(nullptr),
       instrumentation_stack(nullptr), debug_invoke_req(nullptr), single_step_control(nullptr),
       stacked_shadow_frame_record(nullptr), deoptimization_context_stack(nullptr),
@@ -1432,8 +1447,18 @@
     // Size of the stack.
     size_t stack_size;
 
-    // Pointer to previous stack trace captured by sampling profiler.
-    std::vector<ArtMethod*>* stack_trace_sample;
+    // Sampling profiler and AOT verification cannot happen on the same run, so we share
+    // the same entry for the stack trace and the verifier deps.
+    union DepsOrStackTraceSample {
+      DepsOrStackTraceSample() {
+        verifier_deps = nullptr;
+        stack_trace_sample = nullptr;
+      }
+      // Pointer to previous stack trace captured by sampling profiler.
+      std::vector<ArtMethod*>* stack_trace_sample;
+      // When doing AOT verification, per-thread VerifierDeps.
+      verifier::VerifierDeps* verifier_deps;
+    } deps_or_stack_trace_sample;
 
     // The next thread in the wait set this thread is part of or null if not waiting.
     Thread* wait_next;
diff --git a/runtime/thread_pool.cc b/runtime/thread_pool.cc
index 65fd999..d9d2ea3 100644
--- a/runtime/thread_pool.cc
+++ b/runtime/thread_pool.cc
@@ -85,6 +85,7 @@
   ThreadPoolWorker* worker = reinterpret_cast<ThreadPoolWorker*>(arg);
   Runtime* runtime = Runtime::Current();
   CHECK(runtime->AttachCurrentThread(worker->name_.c_str(), true, nullptr, false));
+  worker->thread_ = Thread::Current();
   // Do work until its time to shut down.
   worker->Run();
   runtime->DetachCurrentThread();
diff --git a/runtime/thread_pool.h b/runtime/thread_pool.h
index 2ff33a6..eaadfe0 100644
--- a/runtime/thread_pool.h
+++ b/runtime/thread_pool.h
@@ -62,6 +62,8 @@
   // Set the "nice" priorty for this worker.
   void SetPthreadPriority(int priority);
 
+  Thread* GetThread() const { return thread_; }
+
  protected:
   ThreadPoolWorker(ThreadPool* thread_pool, const std::string& name, size_t stack_size);
   static void* Callback(void* arg) REQUIRES(!Locks::mutator_lock_);
@@ -71,6 +73,7 @@
   const std::string name_;
   std::unique_ptr<MemMap> stack_;
   pthread_t pthread_;
+  Thread* thread_;
 
  private:
   friend class ThreadPool;
@@ -84,6 +87,10 @@
     return threads_.size();
   }
 
+  const std::vector<ThreadPoolWorker*>& GetWorkers() const {
+    return threads_;
+  }
+
   // Broadcast to the workers and tell them to empty out the work queue.
   void StartWorkers(Thread* self) REQUIRES(!task_queue_lock_);
 
diff --git a/runtime/verifier/verifier_deps.cc b/runtime/verifier/verifier_deps.cc
index a65e82b..fefe5a3 100644
--- a/runtime/verifier/verifier_deps.cc
+++ b/runtime/verifier/verifier_deps.cc
@@ -18,6 +18,7 @@
 
 #include <cstring>
 
+#include "base/stl_util.h"
 #include "compiler_callbacks.h"
 #include "leb128.h"
 #include "mirror/class-inl.h"
@@ -28,7 +29,6 @@
 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());
@@ -36,6 +36,28 @@
   }
 }
 
+void VerifierDeps::MergeWith(const VerifierDeps& other,
+                             const std::vector<const DexFile*>& dex_files) {
+  DCHECK(dex_deps_.size() == other.dex_deps_.size());
+  for (const DexFile* dex_file : dex_files) {
+    DexFileDeps* my_deps = GetDexFileDeps(*dex_file);
+    const DexFileDeps& other_deps = *other.GetDexFileDeps(*dex_file);
+    // We currently collect extra strings only on the main `VerifierDeps`,
+    // which should be the one passed as `this` in this method.
+    DCHECK(other_deps.strings_.empty());
+    MergeSets(my_deps->assignable_types_, other_deps.assignable_types_);
+    MergeSets(my_deps->unassignable_types_, other_deps.unassignable_types_);
+    MergeSets(my_deps->classes_, other_deps.classes_);
+    MergeSets(my_deps->fields_, other_deps.fields_);
+    MergeSets(my_deps->direct_methods_, other_deps.direct_methods_);
+    MergeSets(my_deps->virtual_methods_, other_deps.virtual_methods_);
+    MergeSets(my_deps->interface_methods_, other_deps.interface_methods_);
+    for (dex::TypeIndex entry : other_deps.unverified_classes_) {
+      my_deps->unverified_classes_.push_back(entry);
+    }
+  }
+}
+
 VerifierDeps::DexFileDeps* VerifierDeps::GetDexFileDeps(const DexFile& dex_file) {
   auto it = dex_deps_.find(&dex_file);
   return (it == dex_deps_.end()) ? nullptr : it->second.get();
@@ -134,6 +156,38 @@
   return GetClassDescriptorStringId(dex_file, field->GetDeclaringClass());
 }
 
+static inline VerifierDeps* GetMainVerifierDeps() {
+  // The main VerifierDeps is the one set in the compiler callbacks, which at the
+  // end of verification will have all the per-thread VerifierDeps merged into it.
+  CompilerCallbacks* callbacks = Runtime::Current()->GetCompilerCallbacks();
+  if (callbacks == nullptr) {
+    return nullptr;
+  }
+  return callbacks->GetVerifierDeps();
+}
+
+static inline VerifierDeps* GetThreadLocalVerifierDeps() {
+  // During AOT, each thread has its own VerifierDeps, to avoid lock contention. At the end
+  // of full verification, these VerifierDeps will be merged into the main one.
+  if (!Runtime::Current()->IsAotCompiler()) {
+    return nullptr;
+  }
+  return Thread::Current()->GetVerifierDeps();
+}
+
+static bool FindExistingStringId(const std::vector<std::string>& strings,
+                                 const std::string& str,
+                                 uint32_t* found_id) {
+  uint32_t num_extra_ids = strings.size();
+  for (size_t i = 0; i < num_extra_ids; ++i) {
+    if (strings[i] == str) {
+      *found_id = i;
+      return true;
+    }
+  }
+  return false;
+}
+
 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) {
@@ -144,25 +198,32 @@
   // 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);
+  // We use the main `VerifierDeps` for adding new strings to simplify
+  // synchronization/merging of these entries between threads.
+  VerifierDeps* singleton = GetMainVerifierDeps();
+  DexFileDeps* deps = singleton->GetDexFileDeps(dex_file);
   DCHECK(deps != nullptr);
 
   uint32_t num_ids_in_dex = dex_file.NumStringIds();
-  uint32_t num_extra_ids = deps->strings_.size();
+  uint32_t found_id;
 
-  for (size_t i = 0; i < num_extra_ids; ++i) {
-    if (deps->strings_[i] == str) {
-      return num_ids_in_dex + i;
+  {
+    ReaderMutexLock mu(Thread::Current(), *Locks::verifier_deps_lock_);
+    if (FindExistingStringId(deps->strings_, str, &found_id)) {
+      return num_ids_in_dex + found_id;
     }
   }
-
-  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;
+  {
+    WriterMutexLock mu(Thread::Current(), *Locks::verifier_deps_lock_);
+    if (FindExistingStringId(deps->strings_, str, &found_id)) {
+      return num_ids_in_dex + found_id;
+    }
+    deps->strings_.push_back(str);
+    uint32_t new_id = num_ids_in_dex + deps->strings_.size() - 1;
+    CHECK_GE(new_id, num_ids_in_dex);  // check for overflows
+    DCHECK_EQ(str, singleton->GetStringFromId(dex_file, new_id));
+    return new_id;
+  }
 }
 
 std::string VerifierDeps::GetStringFromId(const DexFile& dex_file, uint32_t string_id) const {
@@ -216,7 +277,6 @@
     return;
   }
 
-  MutexLock mu(Thread::Current(), *Locks::verifier_deps_lock_);
   dex_deps->classes_.emplace(ClassResolution(type_idx, GetAccessFlags(klass)));
 }
 
@@ -235,7 +295,6 @@
     return;
   }
 
-  MutexLock mu(Thread::Current(), *Locks::verifier_deps_lock_);
   dex_deps->fields_.emplace(FieldResolution(field_idx,
                                             GetAccessFlags(field),
                                             GetFieldDeclaringClassStringId(dex_file,
@@ -259,7 +318,6 @@
     return;
   }
 
-  MutexLock mu(Thread::Current(), *Locks::verifier_deps_lock_);
   MethodResolution method_tuple(method_idx,
                                 GetAccessFlags(method),
                                 GetMethodDeclaringClassStringId(dex_file, method_idx, method));
@@ -328,8 +386,6 @@
     return;
   }
 
-  MutexLock mu(Thread::Current(), *Locks::verifier_deps_lock_);
-
   // Get string IDs for both descriptors and store in the appropriate set.
   uint32_t destination_id = GetClassDescriptorStringId(dex_file, destination);
   uint32_t source_id = GetClassDescriptorStringId(dex_file, source);
@@ -341,14 +397,6 @@
   }
 }
 
-static inline VerifierDeps* GetVerifierDepsSingleton() {
-  CompilerCallbacks* callbacks = Runtime::Current()->GetCompilerCallbacks();
-  if (callbacks == nullptr) {
-    return nullptr;
-  }
-  return callbacks->GetVerifierDeps();
-}
-
 void VerifierDeps::MaybeRecordVerificationStatus(const DexFile& dex_file,
                                                  dex::TypeIndex type_idx,
                                                  MethodVerifier::FailureKind failure_kind) {
@@ -357,10 +405,9 @@
     return;
   }
 
-  VerifierDeps* singleton = GetVerifierDepsSingleton();
-  if (singleton != nullptr) {
-    DexFileDeps* dex_deps = singleton->GetDexFileDeps(dex_file);
-    MutexLock mu(Thread::Current(), *Locks::verifier_deps_lock_);
+  VerifierDeps* thread_deps = GetThreadLocalVerifierDeps();
+  if (thread_deps != nullptr) {
+    DexFileDeps* dex_deps = thread_deps->GetDexFileDeps(dex_file);
     dex_deps->unverified_classes_.push_back(type_idx);
   }
 }
@@ -368,18 +415,18 @@
 void VerifierDeps::MaybeRecordClassResolution(const DexFile& dex_file,
                                               dex::TypeIndex type_idx,
                                               mirror::Class* klass) {
-  VerifierDeps* singleton = GetVerifierDepsSingleton();
-  if (singleton != nullptr) {
-    singleton->AddClassResolution(dex_file, type_idx, klass);
+  VerifierDeps* thread_deps = GetThreadLocalVerifierDeps();
+  if (thread_deps != nullptr) {
+    thread_deps->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);
+  VerifierDeps* thread_deps = GetThreadLocalVerifierDeps();
+  if (thread_deps != nullptr) {
+    thread_deps->AddFieldResolution(dex_file, field_idx, field);
   }
 }
 
@@ -387,9 +434,9 @@
                                                uint32_t method_idx,
                                                MethodResolutionKind resolution_kind,
                                                ArtMethod* method) {
-  VerifierDeps* singleton = GetVerifierDepsSingleton();
-  if (singleton != nullptr) {
-    singleton->AddMethodResolution(dex_file, method_idx, resolution_kind, method);
+  VerifierDeps* thread_deps = GetThreadLocalVerifierDeps();
+  if (thread_deps != nullptr) {
+    thread_deps->AddMethodResolution(dex_file, method_idx, resolution_kind, method);
   }
 }
 
@@ -398,9 +445,9 @@
                                             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);
+  VerifierDeps* thread_deps = GetThreadLocalVerifierDeps();
+  if (thread_deps != nullptr) {
+    thread_deps->AddAssignability(dex_file, destination, source, is_strict, is_assignable);
   }
 }
 
@@ -533,7 +580,6 @@
 
 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 (const DexFile* dex_file : dex_files) {
     const DexFileDeps& deps = *GetDexFileDeps(*dex_file);
     EncodeStringVector(buffer, deps.strings_);
@@ -575,8 +621,6 @@
 }
 
 bool VerifierDeps::Equals(const VerifierDeps& rhs) const {
-  MutexLock mu(Thread::Current(), *Locks::verifier_deps_lock_);
-
   if (dex_deps_.size() != rhs.dex_deps_.size()) {
     return false;
   }
diff --git a/runtime/verifier/verifier_deps.h b/runtime/verifier/verifier_deps.h
index e35af41..a12071b 100644
--- a/runtime/verifier/verifier_deps.h
+++ b/runtime/verifier/verifier_deps.h
@@ -42,18 +42,19 @@
 // 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.
+// During code-flow verification, the MethodVerifier informs VerifierDeps
+// about the outcome of every resolution and assignability test, and
+// the VerifierDeps object 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_);
+  explicit VerifierDeps(const std::vector<const DexFile*>& dex_files);
 
-  VerifierDeps(const std::vector<const DexFile*>& dex_files,
-               ArrayRef<const uint8_t> data)
-      REQUIRES(!Locks::verifier_deps_lock_);
+  VerifierDeps(const std::vector<const DexFile*>& dex_files, ArrayRef<const uint8_t> data);
+
+  // Merge `other` into this `VerifierDeps`'. `other` and `this` must be for the
+  // same set of dex files.
+  void MergeWith(const VerifierDeps& other, const std::vector<const DexFile*>& dex_files);
 
   // Record the verification status of the class at `type_idx`.
   static void MaybeRecordVerificationStatus(const DexFile& dex_file,
@@ -101,23 +102,15 @@
   // Serialize the recorded dependencies and store the data into `buffer`.
   // `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_);
+  void Encode(const std::vector<const DexFile*>& dex_files, std::vector<uint8_t>* buffer) const;
 
-  // 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;
+  void Dump(VariableIndentationOutputStream* vios) const;
 
   // Verify the encoded dependencies of this `VerifierDeps` are still valid.
-  // NO_THREAD_SAFETY_ANALYSIS, as this must be called on a read-only `VerifierDeps`.
   bool ValidateDependencies(Handle<mirror::ClassLoader> class_loader, Thread* self) const
-      NO_THREAD_SAFETY_ANALYSIS;
+      REQUIRES_SHARED(Locks::mutator_lock_);
 
-  // NO_THREAD_SAFETY_ANALSYS, as this is queried when the VerifierDeps are
-  // fully created.
-  const std::vector<dex::TypeIndex>& GetUnverifiedClasses(const DexFile& dex_file) const
-      NO_THREAD_SAFETY_ANALYSIS {
+  const std::vector<dex::TypeIndex>& GetUnverifiedClasses(const DexFile& dex_file) const {
     return GetDexFileDeps(dex_file)->unverified_classes_;
   }
 
@@ -200,13 +193,9 @@
 
   // 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;
+  DexFileDeps* GetDexFileDeps(const DexFile& dex_file);
 
-  const DexFileDeps* GetDexFileDeps(const DexFile& dex_file) const
-      NO_THREAD_SAFETY_ANALYSIS;
+  const DexFileDeps* GetDexFileDeps(const DexFile& dex_file) const;
 
   // Returns true if `klass` is null or not defined in any of dex files which
   // were reported as being compiled.
@@ -218,11 +207,10 @@
   // 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_);
+      REQUIRES(!Locks::verifier_deps_lock_);
 
   // Returns the string represented by `id`.
-  std::string GetStringFromId(const DexFile& dex_file, uint32_t string_id) const
-      REQUIRES(Locks::verifier_deps_lock_);
+  std::string GetStringFromId(const DexFile& dex_file, uint32_t string_id) const;
 
   // Returns the bytecode access flags of `element` (bottom 16 bits), or
   // `kUnresolvedMarker` if `element` is null.
@@ -235,18 +223,16 @@
   uint32_t GetMethodDeclaringClassStringId(const DexFile& dex_file,
                                            uint32_t dex_method_idx,
                                            ArtMethod* method)
-      REQUIRES_SHARED(Locks::mutator_lock_)
-      REQUIRES(Locks::verifier_deps_lock_);
+      REQUIRES_SHARED(Locks::mutator_lock_);
   uint32_t GetFieldDeclaringClassStringId(const DexFile& dex_file,
                                           uint32_t dex_field_idx,
                                           ArtField* field)
-      REQUIRES_SHARED(Locks::mutator_lock_)
-      REQUIRES(Locks::verifier_deps_lock_);
+      REQUIRES_SHARED(Locks::mutator_lock_);
 
   // Returns a string ID of the descriptor of the class.
   uint32_t GetClassDescriptorStringId(const DexFile& dex_file, ObjPtr<mirror::Class> klass)
       REQUIRES_SHARED(Locks::mutator_lock_)
-      REQUIRES(Locks::verifier_deps_lock_);
+      REQUIRES(!Locks::verifier_deps_lock_);
 
   void AddClassResolution(const DexFile& dex_file,
                           dex::TypeIndex type_idx,
@@ -272,11 +258,9 @@
                         mirror::Class* source,
                         bool is_strict,
                         bool is_assignable)
-      REQUIRES_SHARED(Locks::mutator_lock_)
-      REQUIRES(!Locks::verifier_deps_lock_);
+      REQUIRES_SHARED(Locks::mutator_lock_);
 
-  bool Equals(const VerifierDeps& rhs) const
-      REQUIRES(!Locks::verifier_deps_lock_);
+  bool Equals(const VerifierDeps& rhs) const;
 
   // Verify `dex_file` according to the `deps`, that is going over each
   // `DexFileDeps` field, and checking that the recorded information still
@@ -285,16 +269,14 @@
                      const DexFile& dex_file,
                      const DexFileDeps& deps,
                      Thread* self) const
-      REQUIRES_SHARED(Locks::mutator_lock_)
-      REQUIRES(Locks::verifier_deps_lock_);
+      REQUIRES_SHARED(Locks::mutator_lock_);
 
   bool VerifyAssignability(Handle<mirror::ClassLoader> class_loader,
                            const DexFile& dex_file,
                            const std::set<TypeAssignability>& assignables,
                            bool expected_assignability,
                            Thread* self) const
-      REQUIRES_SHARED(Locks::mutator_lock_)
-      REQUIRES(Locks::verifier_deps_lock_);
+      REQUIRES_SHARED(Locks::mutator_lock_);
 
   // Verify that the set of resolved classes at the point of creation
   // of this `VerifierDeps` is still the same.
@@ -302,8 +284,7 @@
                      const DexFile& dex_file,
                      const std::set<ClassResolution>& classes,
                      Thread* self) const
-      REQUIRES_SHARED(Locks::mutator_lock_)
-      REQUIRES(Locks::verifier_deps_lock_);
+      REQUIRES_SHARED(Locks::mutator_lock_);
 
   // Verify that the set of resolved fields at the point of creation
   // of this `VerifierDeps` is still the same, and each field resolves to the
@@ -313,7 +294,7 @@
                     const std::set<FieldResolution>& classes,
                     Thread* self) const
       REQUIRES_SHARED(Locks::mutator_lock_)
-      REQUIRES(Locks::verifier_deps_lock_);
+      REQUIRES(!Locks::verifier_deps_lock_);
 
   // Verify that the set of resolved methods at the point of creation
   // of this `VerifierDeps` is still the same, and each method resolves to the
@@ -323,12 +304,10 @@
                      const std::set<MethodResolution>& methods,
                      MethodResolutionKind kind,
                      Thread* self) const
-      REQUIRES_SHARED(Locks::mutator_lock_)
-      REQUIRES(Locks::verifier_deps_lock_);
+      REQUIRES_SHARED(Locks::mutator_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_);
+  std::map<const DexFile*, std::unique_ptr<DexFileDeps>> dex_deps_;
 
   friend class VerifierDepsTest;
   ART_FRIEND_TEST(VerifierDepsTest, StringToId);