diff --git a/compiler/driver/compiler_driver.cc b/compiler/driver/compiler_driver.cc
index b3160dd..f3718c4 100644
--- a/compiler/driver/compiler_driver.cc
+++ b/compiler/driver/compiler_driver.cc
@@ -291,7 +291,6 @@
       instruction_set_(instruction_set == kArm ? kThumb2 : instruction_set),
       instruction_set_features_(instruction_set_features),
       requires_constructor_barrier_lock_("constructor barrier lock"),
-      compiled_classes_lock_("compiled classes lock"),
       non_relative_linker_patch_count_(0u),
       image_classes_(image_classes),
       classes_to_compile_(compiled_classes),
@@ -1947,7 +1946,12 @@
         if (compiler_only_verifies) {
           // Just update the compiled_classes_ map. The compiler doesn't need to resolve
           // the type.
-          compiled_classes_.Overwrite(ClassReference(dex_file, i), mirror::Class::kStatusVerified);
+          DexFileReference ref(dex_file, i);
+          mirror::Class::Status existing = mirror::Class::kStatusNotReady;
+          DCHECK(compiled_classes_.Get(ref, &existing)) << ref.dex_file->GetLocation();
+          ClassStateTable::InsertResult result =
+             compiled_classes_.Insert(ref, existing, mirror::Class::kStatusVerified);
+          CHECK_EQ(result, ClassStateTable::kInsertResultSuccess);
         } else {
           // Update the class status, so later compilation stages know they don't need to verify
           // the class.
@@ -1978,6 +1982,13 @@
 void CompilerDriver::Verify(jobject jclass_loader,
                             const std::vector<const DexFile*>& dex_files,
                             TimingLogger* timings) {
+  // Always add the dex files to compiled_classes_. This happens for all compiler filters.
+  for (const DexFile* dex_file : dex_files) {
+    if (!compiled_classes_.HaveDexFile(dex_file)) {
+      compiled_classes_.AddDexFile(dex_file, dex_file->NumClassDefs());
+    }
+  }
+
   if (FastVerify(jclass_loader, dex_files, timings)) {
     return;
   }
@@ -2202,6 +2213,9 @@
                                         size_t thread_count,
                                         TimingLogger* timings) {
   TimingLogger::ScopedTiming t("Verify Dex File", timings);
+  if (!compiled_classes_.HaveDexFile(&dex_file)) {
+    compiled_classes_.AddDexFile(&dex_file, dex_file.NumClassDefs());
+  }
   ClassLinker* class_linker = Runtime::Current()->GetClassLinker();
   ParallelCompilationManager context(class_linker, class_loader, this, &dex_file, dex_files,
                                      thread_pool);
@@ -2248,12 +2262,13 @@
     const bool is_app_image = manager_->GetCompiler()->GetCompilerOptions().IsAppImage();
 
     mirror::Class::Status old_status = klass->GetStatus();
+    // Don't initialize classes in boot space when compiling app image
+    if (is_app_image && klass->IsBootStrapClassLoaded()) {
+      // Also return early and don't store the class status in the recorded class status.
+      return;
+    }
     // Only try to initialize classes that were successfully verified.
     if (klass->IsVerified()) {
-      // Don't initialize classes in boot space when compiling app image
-      if (is_app_image && klass->IsBootStrapClassLoaded()) {
-        return;
-      }
       // Attempt to initialize the class but bail if we either need to initialize the super-class
       // or static fields.
       manager_->GetClassLinker()->EnsureInitialized(soa.Self(), klass, false, false);
@@ -2860,12 +2875,12 @@
 
 bool CompilerDriver::GetCompiledClass(ClassReference ref, mirror::Class::Status* status) const {
   DCHECK(status != nullptr);
-  MutexLock mu(Thread::Current(), compiled_classes_lock_);
-  ClassStateTable::const_iterator it = compiled_classes_.find(ref);
-  if (it == compiled_classes_.end()) {
+  // The table doesn't know if something wasn't inserted. For this case it will return
+  // kStatusNotReady. To handle this, just assume anything not verified is not compiled.
+  if (!compiled_classes_.Get(DexFileReference(ref.first, ref.second), status) ||
+      *status < mirror::Class::kStatusVerified) {
     return false;
   }
-  *status = it->second;
   return true;
 }
 
@@ -2886,15 +2901,20 @@
           << " of " << status;
   }
 
-  MutexLock mu(Thread::Current(), compiled_classes_lock_);
-  auto it = compiled_classes_.find(ref);
-  if (it == compiled_classes_.end()) {
-    compiled_classes_.Overwrite(ref, status);
-  } else if (status > it->second) {
+  ClassStateTable::InsertResult result;
+  do {
+    DexFileReference dex_ref(ref.first, ref.second);
+    mirror::Class::Status existing = mirror::Class::kStatusNotReady;
+    CHECK(compiled_classes_.Get(dex_ref, &existing)) << dex_ref.dex_file->GetLocation();
+    if (existing >= status) {
+      // Existing status is already better than we expect, break.
+      break;
+    }
     // Update the status if we now have a greater one. This happens with vdex,
     // which records a class is verified, but does not resolve it.
-    it->second = status;
-  }
+    result = compiled_classes_.Insert(dex_ref, existing, status);
+    CHECK(result != ClassStateTable::kInsertResultInvalidDexFile);
+  } while (result != ClassStateTable::kInsertResultSuccess);
 }
 
 CompiledMethod* CompilerDriver::GetCompiledMethod(MethodReference ref) const {
diff --git a/compiler/driver/compiler_driver.h b/compiler/driver/compiler_driver.h
index a3272d3..93234cb 100644
--- a/compiler/driver/compiler_driver.h
+++ b/compiler/driver/compiler_driver.h
@@ -117,12 +117,12 @@
   void CompileAll(jobject class_loader,
                   const std::vector<const DexFile*>& dex_files,
                   TimingLogger* timings)
-      REQUIRES(!Locks::mutator_lock_, !compiled_classes_lock_, !dex_to_dex_references_lock_);
+      REQUIRES(!Locks::mutator_lock_, !dex_to_dex_references_lock_);
 
   // Compile a single Method.
   void CompileOne(Thread* self, ArtMethod* method, TimingLogger* timings)
       REQUIRES_SHARED(Locks::mutator_lock_)
-      REQUIRES(!compiled_classes_lock_, !dex_to_dex_references_lock_);
+      REQUIRES(!dex_to_dex_references_lock_);
 
   VerificationResults* GetVerificationResults() const;
 
@@ -153,8 +153,7 @@
   std::unique_ptr<const std::vector<uint8_t>> CreateQuickResolutionTrampoline() const;
   std::unique_ptr<const std::vector<uint8_t>> CreateQuickToInterpreterBridge() const;
 
-  bool GetCompiledClass(ClassReference ref, mirror::Class::Status* status) const
-      REQUIRES(!compiled_classes_lock_);
+  bool GetCompiledClass(ClassReference ref, mirror::Class::Status* status) const;
 
   CompiledMethod* GetCompiledMethod(MethodReference ref) const;
   size_t GetNonRelativeLinkerPatchCount() const;
@@ -337,8 +336,7 @@
   // according to the profile file.
   bool ShouldVerifyClassBasedOnProfile(const DexFile& dex_file, uint16_t class_idx) const;
 
-  void RecordClassStatus(ClassReference ref, mirror::Class::Status status)
-      REQUIRES(!compiled_classes_lock_);
+  void RecordClassStatus(ClassReference ref, mirror::Class::Status status);
 
   // Checks if the specified method has been verified without failures. Returns
   // false if the method is not in the verification results (GetVerificationResults).
@@ -387,7 +385,7 @@
   void PreCompile(jobject class_loader,
                   const std::vector<const DexFile*>& dex_files,
                   TimingLogger* timings)
-      REQUIRES(!Locks::mutator_lock_, !compiled_classes_lock_);
+      REQUIRES(!Locks::mutator_lock_);
 
   void LoadImageClasses(TimingLogger* timings) REQUIRES(!Locks::mutator_lock_);
 
@@ -408,12 +406,9 @@
 
   // Do fast verification through VerifierDeps if possible. Return whether
   // verification was successful.
-  // NO_THREAD_SAFETY_ANALYSIS as the method accesses a guarded value in a
-  // single-threaded way.
   bool FastVerify(jobject class_loader,
                   const std::vector<const DexFile*>& dex_files,
-                  TimingLogger* timings)
-      NO_THREAD_SAFETY_ANALYSIS;
+                  TimingLogger* timings);
 
   void Verify(jobject class_loader,
               const std::vector<const DexFile*>& dex_files,
@@ -441,12 +436,12 @@
   void InitializeClasses(jobject class_loader,
                          const std::vector<const DexFile*>& dex_files,
                          TimingLogger* timings)
-      REQUIRES(!Locks::mutator_lock_, !compiled_classes_lock_);
+      REQUIRES(!Locks::mutator_lock_);
   void InitializeClasses(jobject class_loader,
                          const DexFile& dex_file,
                          const std::vector<const DexFile*>& dex_files,
                          TimingLogger* timings)
-      REQUIRES(!Locks::mutator_lock_, !compiled_classes_lock_);
+      REQUIRES(!Locks::mutator_lock_);
 
   void UpdateImageClasses(TimingLogger* timings) REQUIRES(!Locks::mutator_lock_);
 
@@ -484,10 +479,9 @@
   std::map<ClassReference, bool> requires_constructor_barrier_
       GUARDED_BY(requires_constructor_barrier_lock_);
 
-  using ClassStateTable = SafeMap<const ClassReference, mirror::Class::Status>;
-  // All class references that this compiler has compiled.
-  mutable Mutex compiled_classes_lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
-  ClassStateTable compiled_classes_ GUARDED_BY(compiled_classes_lock_);
+  // All class references that this compiler has compiled. Indexed by class defs.
+  using ClassStateTable = AtomicDexRefMap<mirror::Class::Status>;
+  ClassStateTable compiled_classes_;
 
   typedef AtomicDexRefMap<CompiledMethod*> MethodTable;
 
diff --git a/runtime/atomic.h b/runtime/atomic.h
index 25dd1a3..09eae40 100644
--- a/runtime/atomic.h
+++ b/runtime/atomic.h
@@ -187,7 +187,7 @@
 template<typename T>
 class PACKED(sizeof(T)) Atomic : public std::atomic<T> {
  public:
-  Atomic<T>() : std::atomic<T>(0) { }
+  Atomic<T>() : std::atomic<T>(T()) { }
 
   explicit Atomic<T>(T value) : std::atomic<T>(value) { }