diff --git a/dex2oat/dex2oat.cc b/dex2oat/dex2oat.cc
index ec6f96f..0889098 100644
--- a/dex2oat/dex2oat.cc
+++ b/dex2oat/dex2oat.cc
@@ -1030,6 +1030,9 @@
         compiler_options_->GetNativeDebuggable() ? OatHeader::kTrueValue : OatHeader::kFalseValue);
     key_value_store_->Put(OatHeader::kCompilerFilter,
         CompilerFilter::NameOfFilter(compiler_options_->GetCompilerFilter()));
+    key_value_store_->Put(OatHeader::kHasPatchInfoKey,
+        compiler_options_->GetIncludePatchInformation() ? OatHeader::kTrueValue
+                                                        : OatHeader::kFalseValue);
   }
 
   // Parse the arguments from the command line. In case of an unrecognized option or impossible
diff --git a/runtime/oat.cc b/runtime/oat.cc
index d13999a..80231f3 100644
--- a/runtime/oat.cc
+++ b/runtime/oat.cc
@@ -462,6 +462,10 @@
   return IsKeyEnabled(OatHeader::kPicKey);
 }
 
+bool OatHeader::HasPatchInfo() const {
+  return IsKeyEnabled(OatHeader::kHasPatchInfoKey);
+}
+
 bool OatHeader::IsDebuggable() const {
   return IsKeyEnabled(OatHeader::kDebuggableKey);
 }
diff --git a/runtime/oat.h b/runtime/oat.h
index 0dcc52e..68e71c4 100644
--- a/runtime/oat.h
+++ b/runtime/oat.h
@@ -32,12 +32,13 @@
 class PACKED(4) OatHeader {
  public:
   static constexpr uint8_t kOatMagic[] = { 'o', 'a', 't', '\n' };
-  static constexpr uint8_t kOatVersion[] = { '0', '7', '6', '\0' };
+  static constexpr uint8_t kOatVersion[] = { '0', '7', '7', '\0' };
 
   static constexpr const char* kImageLocationKey = "image-location";
   static constexpr const char* kDex2OatCmdLineKey = "dex2oat-cmdline";
   static constexpr const char* kDex2OatHostKey = "dex2oat-host";
   static constexpr const char* kPicKey = "pic";
+  static constexpr const char* kHasPatchInfoKey = "has-patch-info";
   static constexpr const char* kDebuggableKey = "debuggable";
   static constexpr const char* kNativeDebuggableKey = "native-debuggable";
   static constexpr const char* kCompilerFilter = "compiler-filter";
@@ -109,6 +110,7 @@
 
   size_t GetHeaderSize() const;
   bool IsPic() const;
+  bool HasPatchInfo() const;
   bool IsDebuggable() const;
   bool IsNativeDebuggable() const;
   CompilerFilter::Filter GetCompilerFilter() const;
diff --git a/runtime/oat_file.cc b/runtime/oat_file.cc
index 9ae033f..7c83715 100644
--- a/runtime/oat_file.cc
+++ b/runtime/oat_file.cc
@@ -1248,6 +1248,10 @@
   method->SetEntryPointFromQuickCompiledCode(GetQuickCode());
 }
 
+bool OatFile::HasPatchInfo() const {
+  return GetOatHeader().HasPatchInfo();
+}
+
 bool OatFile::IsPic() const {
   return GetOatHeader().IsPic();
   // TODO: Check against oat_patches. b/18144996
diff --git a/runtime/oat_file.h b/runtime/oat_file.h
index 21aeab4..705ba0d 100644
--- a/runtime/oat_file.h
+++ b/runtime/oat_file.h
@@ -87,6 +87,8 @@
     return is_executable_;
   }
 
+  bool HasPatchInfo() const;
+
   bool IsPic() const;
 
   // Indicates whether the oat file was compiled with full debugging capability.
diff --git a/runtime/oat_file_assistant.cc b/runtime/oat_file_assistant.cc
index 096296b..bb90d46 100644
--- a/runtime/oat_file_assistant.cc
+++ b/runtime/oat_file_assistant.cc
@@ -166,15 +166,11 @@
 
   // See if we can get an up-to-date file by running patchoat.
   if (compilation_desired) {
-    if (odex_okay && OdexFileNeedsRelocation()) {
-      // TODO: don't return kPatchOatNeeded if the odex file contains no
-      // patch information.
+    if (odex_okay && OdexFileNeedsRelocation() && OdexFileHasPatchInfo()) {
       return kPatchOatNeeded;
     }
 
-    if (oat_okay && OatFileNeedsRelocation()) {
-      // TODO: don't return kSelfPatchOatNeeded if the oat file contains no
-      // patch information.
+    if (oat_okay && OatFileNeedsRelocation() && OatFileHasPatchInfo()) {
       return kSelfPatchOatNeeded;
     }
   }
@@ -863,6 +859,11 @@
   return (odex_file != nullptr && odex_file->IsExecutable());
 }
 
+bool OatFileAssistant::OdexFileHasPatchInfo() {
+  const OatFile* odex_file = GetOdexFile();
+  return (odex_file != nullptr && odex_file->HasPatchInfo());
+}
+
 void OatFileAssistant::ClearOdexFileCache() {
   odex_file_load_attempted_ = false;
   cached_odex_file_.reset();
@@ -899,6 +900,11 @@
   return (oat_file != nullptr && oat_file->IsExecutable());
 }
 
+bool OatFileAssistant::OatFileHasPatchInfo() {
+  const OatFile* oat_file = GetOatFile();
+  return (oat_file != nullptr && oat_file->HasPatchInfo());
+}
+
 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 452cd84..db754b9 100644
--- a/runtime/oat_file_assistant.h
+++ b/runtime/oat_file_assistant.h
@@ -310,6 +310,9 @@
   // Returns true if the odex file is opened executable.
   bool OdexFileIsExecutable();
 
+  // Returns true if the odex file has patch info required to run patchoat.
+  bool OdexFileHasPatchInfo();
+
   // Clear any cached information about the odex file that depends on the
   // contents of the file.
   void ClearOdexFileCache();
@@ -326,6 +329,9 @@
   // Returns true if the oat file is opened executable.
   bool OatFileIsExecutable();
 
+  // Returns true if the oat file has patch info required to run patchoat.
+  bool OatFileHasPatchInfo();
+
   // 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 634e048..c247812 100644
--- a/runtime/oat_file_assistant_test.cc
+++ b/runtime/oat_file_assistant_test.cc
@@ -230,6 +230,7 @@
                                                      &error_msg));
     ASSERT_TRUE(odex_file.get() != nullptr) << error_msg;
     EXPECT_FALSE(odex_file->IsPic());
+    EXPECT_TRUE(odex_file->HasPatchInfo());
     EXPECT_EQ(filter, odex_file->GetCompilerFilter());
 
     if (CompilerFilter::IsCompilationEnabled(filter)) {
@@ -277,6 +278,44 @@
     EXPECT_EQ(filter, odex_file->GetCompilerFilter());
   }
 
+  // Generate a non-PIC odex file without patch information for the purposes
+  // of test.  The generated odex file will be un-relocated.
+  // TODO: This won't work correctly if we depend on the boot image being
+  // randomly relocated by a non-zero amount. We should have a better solution
+  // for avoiding that flakiness and duplicating code to generate odex and oat
+  // files for test.
+  void GenerateNoPatchOdexForTest(const std::string& dex_location,
+                                  const std::string& odex_location,
+                                  CompilerFilter::Filter filter) {
+    // Temporarily redirect the dalvik cache so dex2oat doesn't find the
+    // relocated image file.
+    std::string android_data_tmp = GetScratchDir() + "AndroidDataTmp";
+    setenv("ANDROID_DATA", android_data_tmp.c_str(), 1);
+    std::vector<std::string> args;
+    args.push_back("--dex-file=" + dex_location);
+    args.push_back("--oat-file=" + odex_location);
+    args.push_back("--compiler-filter=" + CompilerFilter::NameOfFilter(filter));
+    args.push_back("--runtime-arg");
+    args.push_back("-Xnorelocate");
+    std::string error_msg;
+    ASSERT_TRUE(OatFileAssistant::Dex2Oat(args, &error_msg)) << error_msg;
+    setenv("ANDROID_DATA", android_data_.c_str(), 1);
+
+    // Verify the odex file was generated as expected.
+    std::unique_ptr<OatFile> odex_file(OatFile::Open(odex_location.c_str(),
+                                                     odex_location.c_str(),
+                                                     nullptr,
+                                                     nullptr,
+                                                     false,
+                                                     /*low_4gb*/false,
+                                                     dex_location.c_str(),
+                                                     &error_msg));
+    ASSERT_TRUE(odex_file.get() != nullptr) << error_msg;
+    EXPECT_FALSE(odex_file->IsPic());
+    EXPECT_FALSE(odex_file->HasPatchInfo());
+    EXPECT_EQ(filter, odex_file->GetCompilerFilter());
+  }
+
  private:
   // Reserve memory around where the image will be loaded so other memory
   // won't conflict when it comes time to load the image.
@@ -856,6 +895,37 @@
   EXPECT_EQ(1u, dex_files.size());
 }
 
+// Case: We have a DEX file, no ODEX file and an OAT file that needs
+// relocation but doesn't have patch info.
+// Expect: The status is kDex2OatNeeded, because we can't run patchoat.
+TEST_F(OatFileAssistantTest, NoSelfRelocation) {
+  std::string dex_location = GetScratchDir() + "/NoSelfRelocation.jar";
+  std::string oat_location = GetOdexDir() + "/NoSelfRelocation.oat";
+
+  // Create the dex and odex files
+  Copy(GetDexSrc1(), dex_location);
+  GenerateNoPatchOdexForTest(dex_location, oat_location, CompilerFilter::kSpeed);
+
+  OatFileAssistant oat_file_assistant(dex_location.c_str(),
+      oat_location.c_str(), kRuntimeISA, false, true);
+
+  EXPECT_EQ(OatFileAssistant::kDex2OatNeeded,
+      oat_file_assistant.GetDexOptNeeded(CompilerFilter::kSpeed));
+
+  // Make the oat file up to date.
+  std::string error_msg;
+  ASSERT_TRUE(oat_file_assistant.MakeUpToDate(CompilerFilter::kSpeed, &error_msg)) << error_msg;
+  EXPECT_EQ(OatFileAssistant::kNoDexOptNeeded,
+      oat_file_assistant.GetDexOptNeeded(CompilerFilter::kSpeed));
+
+  std::unique_ptr<OatFile> oat_file = oat_file_assistant.GetBestOatFile();
+  ASSERT_TRUE(oat_file.get() != nullptr);
+  EXPECT_TRUE(oat_file->IsExecutable());
+  std::vector<std::unique_ptr<const DexFile>> dex_files;
+  dex_files = oat_file_assistant.LoadDexFiles(*oat_file, dex_location.c_str());
+  EXPECT_EQ(1u, dex_files.size());
+}
+
 // Case: We have a DEX file, an ODEX file and an OAT file, where the ODEX and
 // OAT files both have patch delta of 0.
 // Expect: It shouldn't crash, and status is kPatchOatNeeded.