diff --git a/runtime/oat_file_assistant.cc b/runtime/oat_file_assistant.cc
index df0cf45..29b879e 100644
--- a/runtime/oat_file_assistant.cc
+++ b/runtime/oat_file_assistant.cc
@@ -165,6 +165,11 @@
 }
 
 std::unique_ptr<OatFile> OatFileAssistant::GetBestOatFile() {
+  // The best oat files are, in descending order of bestness:
+  // 1. Properly relocated files. These may be opened executable.
+  // 2. Not out-of-date files that are already opened non-executable.
+  // 3. Not out-of-date files that we must reopen non-executable.
+
   if (OatFileIsUpToDate()) {
     oat_file_released_ = true;
     return std::move(cached_oat_file_);
@@ -175,26 +180,36 @@
     return std::move(cached_odex_file_);
   }
 
-  if (load_executable_) {
-    VLOG(oat) << "Oat File Assistant: No relocated oat file found,"
-      << " attempting to fall back to interpreting oat file instead.";
+  VLOG(oat) << "Oat File Assistant: No relocated oat file found,"
+    << " attempting to fall back to interpreting oat file instead.";
 
+  if (!OatFileIsOutOfDate() && !OatFileIsExecutable()) {
+    oat_file_released_ = true;
+    return std::move(cached_oat_file_);
+  }
+
+  if (!OdexFileIsOutOfDate() && !OdexFileIsExecutable()) {
+    oat_file_released_ = true;
+    return std::move(cached_odex_file_);
+  }
+
+  if (!OatFileIsOutOfDate()) {
+    load_executable_ = false;
+    ClearOatFileCache();
     if (!OatFileIsOutOfDate()) {
-      load_executable_ = false;
-      ClearOatFileCache();
-      if (!OatFileIsOutOfDate()) {
-        oat_file_released_ = true;
-        return std::move(cached_oat_file_);
-      }
+      CHECK(!OatFileIsExecutable());
+      oat_file_released_ = true;
+      return std::move(cached_oat_file_);
     }
+  }
 
+  if (!OdexFileIsOutOfDate()) {
+    load_executable_ = false;
+    ClearOdexFileCache();
     if (!OdexFileIsOutOfDate()) {
-      load_executable_ = false;
-      ClearOdexFileCache();
-      if (!OdexFileIsOutOfDate()) {
-        oat_file_released_ = true;
-        return std::move(cached_odex_file_);
-      }
+      CHECK(!OdexFileIsExecutable());
+      oat_file_released_ = true;
+      return std::move(cached_odex_file_);
     }
   }
 
@@ -868,6 +883,11 @@
   return cached_odex_file_.get();
 }
 
+bool OatFileAssistant::OdexFileIsExecutable() {
+  const OatFile* odex_file = GetOdexFile();
+  return (odex_file != nullptr && odex_file->IsExecutable());
+}
+
 void OatFileAssistant::ClearOdexFileCache() {
   odex_file_load_attempted_ = false;
   cached_odex_file_.reset();
@@ -894,6 +914,11 @@
   return cached_oat_file_.get();
 }
 
+bool OatFileAssistant::OatFileIsExecutable() {
+  const OatFile* oat_file = GetOatFile();
+  return (oat_file != nullptr && oat_file->IsExecutable());
+}
+
 void OatFileAssistant::ClearOatFileCache() {
   oat_file_load_attempted_ = false;
   cached_oat_file_.reset();
diff --git a/runtime/oat_file_assistant.h b/runtime/oat_file_assistant.h
index 7216fc7..664db98 100644
--- a/runtime/oat_file_assistant.h
+++ b/runtime/oat_file_assistant.h
@@ -327,6 +327,9 @@
   // The caller shouldn't clean up or free the returned pointer.
   const OatFile* GetOdexFile();
 
+  // Returns true if the odex file is opened executable.
+  bool OdexFileIsExecutable();
+
   // Clear any cached information about the odex file that depends on the
   // contents of the file.
   void ClearOdexFileCache();
@@ -336,6 +339,9 @@
   // The caller shouldn't clean up or free the returned pointer.
   const OatFile* GetOatFile();
 
+  // Returns true if the oat file is opened executable.
+  bool OatFileIsExecutable();
+
   // Clear any cached information about the oat file that depends on the
   // contents of the file.
   void ClearOatFileCache();
diff --git a/runtime/oat_file_assistant_test.cc b/runtime/oat_file_assistant_test.cc
index 570c59c..adb6851 100644
--- a/runtime/oat_file_assistant_test.cc
+++ b/runtime/oat_file_assistant_test.cc
@@ -470,6 +470,10 @@
   EXPECT_TRUE(oat_file_assistant.OatFileIsOutOfDate());
   EXPECT_FALSE(oat_file_assistant.OatFileIsUpToDate());
   EXPECT_TRUE(oat_file_assistant.HasOriginalDexFiles());
+
+  // We should still be able to get the non-executable odex file to run from.
+  std::unique_ptr<OatFile> oat_file = oat_file_assistant.GetBestOatFile();
+  ASSERT_TRUE(oat_file.get() != nullptr);
 }
 
 // Case: We have a stripped DEX file and an ODEX file, but no OAT file.