diff --git a/dex2oat/dex2oat.cc b/dex2oat/dex2oat.cc
index c9cd171..c4b099c 100644
--- a/dex2oat/dex2oat.cc
+++ b/dex2oat/dex2oat.cc
@@ -1787,7 +1787,7 @@
         for (const DexFile* dex_file : *dex_file_vector) {
           for (const std::string& filter : no_inline_filters) {
             // Use dex_file->GetLocation() rather than dex_file->GetBaseLocation(). This
-            // allows tests to specify <test-dexfile>:classes2.dex if needed but if the
+            // allows tests to specify <test-dexfile>!classes2.dex if needed but if the
             // base location passes the StartsWith() test, so do all extra locations.
             std::string dex_location = dex_file->GetLocation();
             if (filter.find('/') == std::string::npos) {
diff --git a/runtime/class_loader_context_test.cc b/runtime/class_loader_context_test.cc
index 1b46f67..a87552d 100644
--- a/runtime/class_loader_context_test.cc
+++ b/runtime/class_loader_context_test.cc
@@ -488,4 +488,12 @@
   ASSERT_TRUE(context->VerifyClassLoaderContextMatch(context->EncodeContextForOatFile("")));
 }
 
+TEST_F(ClassLoaderContextTest, VerifyClassLoaderContextMatchAfterEncodingMultidex) {
+  jobject class_loader = LoadDexInPathClassLoader("MultiDex", nullptr);
+
+  std::unique_ptr<ClassLoaderContext> context = CreateContextForClassLoader(class_loader);
+
+  ASSERT_TRUE(context->VerifyClassLoaderContextMatch(context->EncodeContextForOatFile("")));
+}
+
 }  // namespace art
diff --git a/runtime/dex_file.h b/runtime/dex_file.h
index eb3b210..990ab11 100644
--- a/runtime/dex_file.h
+++ b/runtime/dex_file.h
@@ -62,11 +62,11 @@
   static const uint16_t kDexNoIndex16 = 0xFFFF;
 
   // The separator character in MultiDex locations.
-  static constexpr char kMultiDexSeparator = ':';
+  static constexpr char kMultiDexSeparator = '!';
 
   // A string version of the previous. This is a define so that we can merge string literals in the
   // preprocessor.
-  #define kMultiDexSeparatorString ":"
+  #define kMultiDexSeparatorString "!"
 
   // Raw header_item.
   struct Header {
@@ -499,7 +499,7 @@
     return GetBaseLocation(location.c_str());
   }
 
-  // Returns the ':classes*.dex' part of the dex location. Returns an empty
+  // Returns the '!classes*.dex' part of the dex location. Returns an empty
   // string if there is no multidex suffix for the given location.
   // The kMultiDexSeparator is included in the returned suffix.
   static std::string GetMultiDexSuffix(const std::string& location) {
diff --git a/runtime/dex_file_test.cc b/runtime/dex_file_test.cc
index 78d5c5f..1a73062 100644
--- a/runtime/dex_file_test.cc
+++ b/runtime/dex_file_test.cc
@@ -535,9 +535,9 @@
   std::string dex_location_str = "/system/app/framework.jar";
   const char* dex_location = dex_location_str.c_str();
   ASSERT_EQ("/system/app/framework.jar", DexFile::GetMultiDexLocation(0, dex_location));
-  ASSERT_EQ("/system/app/framework.jar:classes2.dex",
+  ASSERT_EQ("/system/app/framework.jar!classes2.dex",
             DexFile::GetMultiDexLocation(1, dex_location));
-  ASSERT_EQ("/system/app/framework.jar:classes101.dex",
+  ASSERT_EQ("/system/app/framework.jar!classes101.dex",
             DexFile::GetMultiDexLocation(100, dex_location));
 }
 
@@ -563,11 +563,11 @@
 
 TEST(DexFileUtilsTest, GetBaseLocationAndMultiDexSuffix) {
   EXPECT_EQ("/foo/bar/baz.jar", DexFile::GetBaseLocation("/foo/bar/baz.jar"));
-  EXPECT_EQ("/foo/bar/baz.jar", DexFile::GetBaseLocation("/foo/bar/baz.jar:classes2.dex"));
-  EXPECT_EQ("/foo/bar/baz.jar", DexFile::GetBaseLocation("/foo/bar/baz.jar:classes8.dex"));
+  EXPECT_EQ("/foo/bar/baz.jar", DexFile::GetBaseLocation("/foo/bar/baz.jar!classes2.dex"));
+  EXPECT_EQ("/foo/bar/baz.jar", DexFile::GetBaseLocation("/foo/bar/baz.jar!classes8.dex"));
   EXPECT_EQ("", DexFile::GetMultiDexSuffix("/foo/bar/baz.jar"));
-  EXPECT_EQ(":classes2.dex", DexFile::GetMultiDexSuffix("/foo/bar/baz.jar:classes2.dex"));
-  EXPECT_EQ(":classes8.dex", DexFile::GetMultiDexSuffix("/foo/bar/baz.jar:classes8.dex"));
+  EXPECT_EQ("!classes2.dex", DexFile::GetMultiDexSuffix("/foo/bar/baz.jar!classes2.dex"));
+  EXPECT_EQ("!classes8.dex", DexFile::GetMultiDexSuffix("/foo/bar/baz.jar!classes8.dex"));
 }
 
 TEST_F(DexFileTest, ZipOpenClassesPresent) {
diff --git a/runtime/jit/profile_compilation_info.cc b/runtime/jit/profile_compilation_info.cc
index a247b56..45c3792 100644
--- a/runtime/jit/profile_compilation_info.cc
+++ b/runtime/jit/profile_compilation_info.cc
@@ -47,9 +47,8 @@
 namespace art {
 
 const uint8_t ProfileCompilationInfo::kProfileMagic[] = { 'p', 'r', 'o', '\0' };
-// Last profile version: Move startup methods to use a bitmap. Also add support for post-startup
-// methods.
-const uint8_t ProfileCompilationInfo::kProfileVersion[] = { '0', '0', '8', '\0' };
+// Last profile version: update the multidex separator.
+const uint8_t ProfileCompilationInfo::kProfileVersion[] = { '0', '0', '9', '\0' };
 
 static constexpr uint16_t kMaxDexFileKeyLength = PATH_MAX;
 
@@ -1341,7 +1340,7 @@
 
   os << "ProfileInfo:";
 
-  const std::string kFirstDexFileKeySubstitute = ":classes.dex";
+  const std::string kFirstDexFileKeySubstitute = "!classes.dex";
 
   for (const DexFileData* dex_data : info_) {
     os << "\n";
diff --git a/runtime/native/java_lang_VMClassLoader.cc b/runtime/native/java_lang_VMClassLoader.cc
index fc50d55..57c313e 100644
--- a/runtime/native/java_lang_VMClassLoader.cc
+++ b/runtime/native/java_lang_VMClassLoader.cc
@@ -135,7 +135,7 @@
   for (size_t i = 0; i < path.size(); ++i) {
     const DexFile* dex_file = path[i];
 
-    // For multidex locations, e.g., x.jar:classes2.dex, we want to look into x.jar.
+    // For multidex locations, e.g., x.jar!classes2.dex, we want to look into x.jar.
     const std::string& location(dex_file->GetBaseLocation());
 
     ScopedLocalRef<jstring> javaPath(env, env->NewStringUTF(location.c_str()));
diff --git a/runtime/oat.h b/runtime/oat.h
index f4edb16..de4b942 100644
--- a/runtime/oat.h
+++ b/runtime/oat.h
@@ -32,8 +32,8 @@
 class PACKED(4) OatHeader {
  public:
   static constexpr uint8_t kOatMagic[] = { 'o', 'a', 't', '\n' };
-  // Last oat version changed reason: add new class status to skip superclass validation.
-  static constexpr uint8_t kOatVersion[] = { '1', '2', '9', '\0' };
+  // Last oat version changed reason: update kMultiDexSeparator from ':' to '!'.
+  static constexpr uint8_t kOatVersion[] = { '1', '3', '0', '\0' };
 
   static constexpr const char* kImageLocationKey = "image-location";
   static constexpr const char* kDex2OatCmdLineKey = "dex2oat-cmdline";
diff --git a/runtime/oat_file.h b/runtime/oat_file.h
index b112b84..be7d495 100644
--- a/runtime/oat_file.h
+++ b/runtime/oat_file.h
@@ -289,8 +289,8 @@
   // If not null, abs_dex_location is used to resolve the absolute dex
   // location of relative dex locations encoded in the oat file.
   // For example, given absolute location "/data/app/foo/base.apk", encoded
-  // dex locations "base.apk", "base.apk:classes2.dex", etc. would be resolved
-  // to "/data/app/foo/base.apk", "/data/app/foo/base.apk:classes2.dex", etc.
+  // dex locations "base.apk", "base.apk!classes2.dex", etc. would be resolved
+  // to "/data/app/foo/base.apk", "/data/app/foo/base.apk!classes2.dex", etc.
   // Relative encoded dex locations that don't match the given abs_dex_location
   // are left unchanged.
   static std::string ResolveRelativeEncodedDexLocation(
diff --git a/runtime/oat_file_test.cc b/runtime/oat_file_test.cc
index d5fe1f3..7bf0f84 100644
--- a/runtime/oat_file_test.cc
+++ b/runtime/oat_file_test.cc
@@ -45,13 +45,13 @@
       OatFile::ResolveRelativeEncodedDexLocation(
         "/data/app/foo/base.apk", "foo/base.apk"));
 
-  EXPECT_EQ(std::string("/data/app/foo/base.apk:classes2.dex"),
+  EXPECT_EQ(std::string("/data/app/foo/base.apk!classes2.dex"),
       OatFile::ResolveRelativeEncodedDexLocation(
-        "/data/app/foo/base.apk", "base.apk:classes2.dex"));
+        "/data/app/foo/base.apk", "base.apk!classes2.dex"));
 
-  EXPECT_EQ(std::string("/data/app/foo/base.apk:classes11.dex"),
+  EXPECT_EQ(std::string("/data/app/foo/base.apk!classes11.dex"),
       OatFile::ResolveRelativeEncodedDexLocation(
-        "/data/app/foo/base.apk", "base.apk:classes11.dex"));
+        "/data/app/foo/base.apk", "base.apk!classes11.dex"));
 
   EXPECT_EQ(std::string("base.apk"),
       OatFile::ResolveRelativeEncodedDexLocation(
diff --git a/test/569-checker-pattern-replacement/run b/test/569-checker-pattern-replacement/run
index f7e9df2..8ab6527 100755
--- a/test/569-checker-pattern-replacement/run
+++ b/test/569-checker-pattern-replacement/run
@@ -15,4 +15,4 @@
 # limitations under the License.
 
 exec ${RUN} "$@" \
-    -Xcompiler-option --no-inline-from=core-oj,569-checker-pattern-replacement.jar:classes2.dex
+    -Xcompiler-option --no-inline-from="core-oj,569-checker-pattern-replacement.jar!classes2.dex"