diff --git a/compiler/dex/verification_results.cc b/compiler/dex/verification_results.cc
index 669d8cd..9d39bf2 100644
--- a/compiler/dex/verification_results.cc
+++ b/compiler/dex/verification_results.cc
@@ -103,6 +103,17 @@
   return (it != verified_methods_.end()) ? it->second : nullptr;
 }
 
+void VerificationResults::CreateVerifiedMethodFor(MethodReference ref) {
+  // This method should only be called for classes verified at compile time,
+  // which have no verifier error, nor has methods that we know will throw
+  // at runtime.
+  AtomicMap::InsertResult result = atomic_verified_methods_.Insert(
+      ref,
+      /*expected*/ nullptr,
+      new VerifiedMethod(/* encountered_error_types */ 0, /* has_runtime_throw */ false));
+  DCHECK_EQ(result, AtomicMap::kInsertResultSuccess);
+}
+
 void VerificationResults::AddRejectedClass(ClassReference ref) {
   {
     WriterMutexLock mu(Thread::Current(), rejected_classes_lock_);
diff --git a/compiler/dex/verification_results.h b/compiler/dex/verification_results.h
index ea38f4d..ab735c1 100644
--- a/compiler/dex/verification_results.h
+++ b/compiler/dex/verification_results.h
@@ -47,6 +47,9 @@
       REQUIRES_SHARED(Locks::mutator_lock_)
       REQUIRES(!verified_methods_lock_);
 
+  void CreateVerifiedMethodFor(MethodReference ref)
+      REQUIRES(!verified_methods_lock_);
+
   const VerifiedMethod* GetVerifiedMethod(MethodReference ref)
       REQUIRES(!verified_methods_lock_);
 
diff --git a/compiler/dex/verified_method.h b/compiler/dex/verified_method.h
index 04331e5..ce53417 100644
--- a/compiler/dex/verified_method.h
+++ b/compiler/dex/verified_method.h
@@ -32,6 +32,8 @@
 
 class VerifiedMethod {
  public:
+  VerifiedMethod(uint32_t encountered_error_types, bool has_runtime_throw);
+
   // Cast elision set type.
   // Since we're adding the dex PCs to the set in increasing order, a sorted vector
   // is better for performance (not just memory usage), especially for large sets.
@@ -80,8 +82,6 @@
   }
 
  private:
-  VerifiedMethod(uint32_t encountered_error_types, bool has_runtime_throw);
-
   /*
    * Generate the GC map for a method that has just been verified (i.e. we're doing this as part of
    * verification). For type-precise determination we have all the data we need, so we just need to
diff --git a/compiler/driver/compiler_driver.cc b/compiler/driver/compiler_driver.cc
index 6b62110..a2bab80 100644
--- a/compiler/driver/compiler_driver.cc
+++ b/compiler/driver/compiler_driver.cc
@@ -2005,6 +2005,35 @@
   }
 }
 
+static void PopulateVerifiedMethods(const DexFile& dex_file,
+                                    uint32_t class_def_index,
+                                    VerificationResults* verification_results) {
+  const DexFile::ClassDef& class_def = dex_file.GetClassDef(class_def_index);
+  const uint8_t* class_data = dex_file.GetClassData(class_def);
+  if (class_data == nullptr) {
+    return;
+  }
+  ClassDataItemIterator it(dex_file, class_data);
+  // Skip fields
+  while (it.HasNextStaticField()) {
+    it.Next();
+  }
+  while (it.HasNextInstanceField()) {
+    it.Next();
+  }
+
+  while (it.HasNextDirectMethod()) {
+    verification_results->CreateVerifiedMethodFor(MethodReference(&dex_file, it.GetMemberIndex()));
+    it.Next();
+  }
+
+  while (it.HasNextVirtualMethod()) {
+    verification_results->CreateVerifiedMethodFor(MethodReference(&dex_file, it.GetMemberIndex()));
+    it.Next();
+  }
+  DCHECK(!it.HasNext());
+}
+
 void CompilerDriver::Verify(jobject jclass_loader,
                             const std::vector<const DexFile*>& dex_files,
                             TimingLogger* timings) {
@@ -2041,6 +2070,13 @@
           } else if (set.find(class_def.class_idx_) == set.end()) {
             ObjectLock<mirror::Class> lock(soa.Self(), cls);
             mirror::Class::SetStatus(cls, mirror::Class::kStatusVerified, soa.Self());
+            // Create `VerifiedMethod`s for each methods, the compiler expects one for
+            // quickening or compiling.
+            // Note that this means:
+            // - We're only going to compile methods that did verify.
+            // - Quickening will not do checkcast ellision.
+            // TODO(ngeoffray): Reconsider this once we refactor compiler filters.
+            PopulateVerifiedMethods(*dex_file, i, verification_results_);
           }
         }
       }
diff --git a/test/629-vdex-speed/expected.txt b/test/629-vdex-speed/expected.txt
new file mode 100644
index 0000000..6a5618e
--- /dev/null
+++ b/test/629-vdex-speed/expected.txt
@@ -0,0 +1 @@
+JNI_OnLoad called
diff --git a/test/629-vdex-speed/info.txt b/test/629-vdex-speed/info.txt
new file mode 100644
index 0000000..6d84cb5
--- /dev/null
+++ b/test/629-vdex-speed/info.txt
@@ -0,0 +1,2 @@
+Regression test for vdex that used to not AOT compile
+methods when the VerifierDeps were verified.
diff --git a/test/629-vdex-speed/run b/test/629-vdex-speed/run
new file mode 100644
index 0000000..f1b0a95
--- /dev/null
+++ b/test/629-vdex-speed/run
@@ -0,0 +1,17 @@
+#!/bin/bash
+#
+# 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.
+
+exec ${RUN} --vdex "${@}"
diff --git a/test/629-vdex-speed/src/Main.java b/test/629-vdex-speed/src/Main.java
new file mode 100644
index 0000000..470565a
--- /dev/null
+++ b/test/629-vdex-speed/src/Main.java
@@ -0,0 +1,27 @@
+/*
+ * 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.
+ */
+
+public class Main {
+  public static void main(String[] args) {
+    System.loadLibrary(args[0]);
+    if (!isAotCompiled(Main.class, "main")) {
+      throw new Error("Expected Main.main to be AOT compiled");
+    }
+  }
+
+  private native static boolean isAotCompiled(Class<?> cls, String methodName);
+}
+
diff --git a/test/Android.run-test.mk b/test/Android.run-test.mk
index d15d016..d7dfe5a 100644
--- a/test/Android.run-test.mk
+++ b/test/Android.run-test.mk
@@ -360,8 +360,10 @@
 TEST_ART_BROKEN_NO_RELOCATE_TESTS :=
 
 # Temporarily disable some broken tests when forcing access checks in interpreter b/22414682
+# 629 requires compilation.
 TEST_ART_BROKEN_INTERPRETER_ACCESS_CHECK_TESTS := \
-  137-cfi
+  137-cfi \
+  629-vdex-speed
 
 ifneq (,$(filter interp-ac,$(COMPILER_TYPES)))
   ART_TEST_KNOWN_BROKEN += $(call all-run-test-names,$(TARGET_TYPES),$(RUN_TYPES),$(PREBUILD_TYPES), \
@@ -470,12 +472,14 @@
 # This test dynamically enables tracing to force a deoptimization. This makes the test meaningless
 # when already tracing, and writes an error message that we do not want to check for.
 # 130 occasional timeout b/32383962.
+# 629 requires compilation.
 TEST_ART_BROKEN_TRACING_RUN_TESTS := \
   087-gc-after-link \
   130-hprof \
   137-cfi \
   141-class-unload \
   570-checker-osr \
+  629-vdex-speed \
   802-deoptimization
 
 ifneq (,$(filter trace stream,$(TRACE_TYPES)))
@@ -486,9 +490,11 @@
 
 # Known broken tests for the interpreter.
 # CFI unwinding expects managed frames.
+# 629 requires compilation.
 TEST_ART_BROKEN_INTERPRETER_RUN_TESTS := \
   137-cfi \
-  554-jit-profile-file
+  554-jit-profile-file \
+  629-vdex-speed
 
 ifneq (,$(filter interpreter,$(COMPILER_TYPES)))
   ART_TEST_KNOWN_BROKEN += $(call all-run-test-names,$(TARGET_TYPES),$(RUN_TYPES),$(PREBUILD_TYPES), \
@@ -504,8 +510,10 @@
 # Test 906 iterates the heap filtering with different options. No instances should be created
 # between those runs to be able to have precise checks.
 # Test 902 hits races with the JIT compiler. b/32821077
+# Test 629 requires compilation.
 TEST_ART_BROKEN_JIT_RUN_TESTS := \
   137-cfi \
+  629-vdex-speed \
   902-hello-transformation \
   904-object-allocation \
   906-iterate-heap \
diff --git a/test/common/runtime_state.cc b/test/common/runtime_state.cc
index 9cfa324..285f3aa 100644
--- a/test/common/runtime_state.cc
+++ b/test/common/runtime_state.cc
@@ -119,6 +119,24 @@
   return JNI_TRUE;
 }
 
+extern "C" JNIEXPORT jboolean JNICALL Java_Main_isAotCompiled(JNIEnv* env,
+                                                              jclass,
+                                                              jclass cls,
+                                                              jstring method_name) {
+  Thread* self = Thread::Current();
+  ScopedObjectAccess soa(self);
+  ScopedUtfChars chars(env, method_name);
+  CHECK(chars.c_str() != nullptr);
+  ArtMethod* method = soa.Decode<mirror::Class>(cls)->FindDeclaredDirectMethodByName(
+        chars.c_str(), kRuntimePointerSize);
+  const void* code = method->GetOatMethodQuickCode(kRuntimePointerSize);
+  jit::Jit* jit = Runtime::Current()->GetJit();
+  if (jit != nullptr && jit->GetCodeCache()->ContainsPc(code)) {
+    return true;
+  }
+  return code != nullptr;
+}
+
 extern "C" JNIEXPORT void JNICALL Java_Main_ensureJitCompiled(JNIEnv* env,
                                                              jclass,
                                                              jclass cls,