diff --git a/src/main/java/com/android/tools/r8/utils/DexVersion.java b/src/main/java/com/android/tools/r8/utils/DexVersion.java
index cdac93d..443b9e7 100644
--- a/src/main/java/com/android/tools/r8/utils/DexVersion.java
+++ b/src/main/java/com/android/tools/r8/utils/DexVersion.java
@@ -4,12 +4,11 @@
 package com.android.tools.r8.utils;
 
 import com.android.tools.r8.errors.Unreachable;
+import com.android.tools.r8.utils.structural.Ordered;
 import java.util.Optional;
 
-/**
- * Android dex version
- */
-public enum DexVersion {
+/** Android dex version */
+public enum DexVersion implements Ordered<DexVersion> {
   V35(35, new byte[] {'0', '3', '5'}),
   V37(37, new byte[] {'0', '3', '7'}),
   V38(38, new byte[] {'0', '3', '8'}),
diff --git a/src/test/java/com/android/tools/r8/ToolHelper.java b/src/test/java/com/android/tools/r8/ToolHelper.java
index d84fe19..1577312 100644
--- a/src/test/java/com/android/tools/r8/ToolHelper.java
+++ b/src/test/java/com/android/tools/r8/ToolHelper.java
@@ -23,6 +23,7 @@
 import com.android.tools.r8.graph.DexApplication;
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DirectMappedDexApplication;
+import com.android.tools.r8.keepanno.utils.Unimplemented;
 import com.android.tools.r8.origin.Origin;
 import com.android.tools.r8.position.Position;
 import com.android.tools.r8.shaking.FilteredClassPath;
@@ -32,6 +33,7 @@
 import com.android.tools.r8.utils.AndroidApiLevel;
 import com.android.tools.r8.utils.AndroidApp;
 import com.android.tools.r8.utils.AndroidAppConsumers;
+import com.android.tools.r8.utils.DexVersion;
 import com.android.tools.r8.utils.ExceptionUtils;
 import com.android.tools.r8.utils.FileUtils;
 import com.android.tools.r8.utils.InternalOptions;
@@ -66,6 +68,7 @@
 import java.util.Arrays;
 import java.util.Collection;
 import java.util.Collections;
+import java.util.Comparator;
 import java.util.HashSet;
 import java.util.LinkedHashMap;
 import java.util.List;
@@ -413,9 +416,6 @@
 
     private final Version version;
     private final Kind kind;
-
-    // TODO(b/258170524): Should be a new version that works.
-    public static final DexVm LATEST_DEX2OAT = ART_6_0_1_HOST;
   }
 
 
@@ -715,12 +715,28 @@
   private static final Path DX = getDxExecutablePath();
 
   private static Path getDexVmPath(DexVm vm) {
-    return Paths.get(
-        TOOLS,
-        "linux",
-        vm.getVersion() == DexVm.Version.DEFAULT
-            ? "art"
-            : "art-" + vm.getVersion());
+    DexVm.Version version = vm.getVersion();
+    Path base = Paths.get(TOOLS, "linux");
+    switch (version) {
+      case DEFAULT:
+        return base.resolve("art");
+      case V4_0_4:
+      case V4_4_4:
+      case V5_1_1:
+      case V6_0_1:
+      case V7_0_0:
+      case V8_1_0:
+      case V9_0_0:
+      case V10_0_0:
+        return base.resolve("art-" + version);
+      case V12_0_0:
+        return base.resolve("host").resolve("art-12.0.0-beta4");
+      case V13_0_0:
+      case MASTER:
+        return base.resolve("host").resolve("art-" + version);
+      default:
+        throw new Unreachable();
+    }
   }
 
   private static Path getDexVmLibPath(DexVm vm) {
@@ -736,7 +752,25 @@
   }
 
   private static String getArchString(DexVm vm) {
-    return vm.isOlderThanOrEqual(DexVm.ART_5_1_1_HOST) ? "arm" : "arm64";
+    switch (vm.getVersion()) {
+      case V4_0_4:
+      case V4_4_4:
+      case V5_1_1:
+        return "arm";
+      case V6_0_1:
+      case V7_0_0:
+      case V8_1_0:
+      case DEFAULT:
+      case V9_0_0:
+      case V10_0_0:
+        return "arm64";
+      case V12_0_0:
+      case V13_0_0:
+      case MASTER:
+        return "x86_64";
+      default:
+        throw new Unimplemented();
+    }
   }
 
   private static Path getProductBootImagePath(DexVm vm) {
@@ -1060,6 +1094,10 @@
     }
   }
 
+  public static DexVersion getDexFileVersionForVm(DexVm vm) {
+    return DexVersion.getDexVersion(getMinApiLevelForDexVm(vm));
+  }
+
   private static String getPlatform() {
     return System.getProperty("os.name");
   }
@@ -1995,27 +2033,56 @@
     }
   }
 
-  public static ProcessResult runDex2OatRaw(Path file, Path outFile, DexVm vm) throws IOException {
+  // Checked in VMs for which dex2oat should work specified in decreasing order.
+  private static List<DexVm> SUPPORTED_DEX2OAT_VMS =
+      ImmutableList.of(DexVm.ART_12_0_0_HOST, DexVm.ART_6_0_1_HOST);
+
+  public static ProcessResult runDex2OatRaw(Path file, Path outFile, DexVm targetVm)
+      throws IOException {
     Assume.assumeTrue(ToolHelper.isDex2OatSupported());
-    // TODO(b/258170524): Add working dex2oat. For now we just use latest if it is recent enough.
-    Assume.assumeTrue("b/144975341 & b/258170524", DexVm.LATEST_DEX2OAT.isNewerThanOrEqual(vm));
-    vm = DexVm.LATEST_DEX2OAT;
     assert Files.exists(file);
     assert ByteStreams.toByteArray(Files.newInputStream(file)).length > 0;
+    assert SUPPORTED_DEX2OAT_VMS.stream()
+        .sorted(Comparator.comparing(DexVm::getVersion).reversed())
+        .collect(Collectors.toList())
+        .equals(SUPPORTED_DEX2OAT_VMS);
+    DexVersion requiredDexFileVersion = getDexFileVersionForVm(targetVm);
+    DexVm vm = null;
+    for (DexVm supported : SUPPORTED_DEX2OAT_VMS) {
+      DexVersion supportedDexFileVersion = getDexFileVersionForVm(supported);
+      // This and remaining VMs can't compile code at the required DEX version.
+      if (supportedDexFileVersion.isLessThan(requiredDexFileVersion)) {
+        break;
+      }
+      // Find the "oldest" supported VM. Only consider VMs older than targetVm if no VM matched.
+      if (supported.isNewerThanOrEqual(targetVm) || vm == null) {
+        vm = supported;
+      }
+    }
+    if (vm == null) {
+      throw new Unimplemented("Unable to find a supported dex2oat for VM " + vm);
+    }
     List<String> command = new ArrayList<>();
-    command.add(getDex2OatPath(vm).toString());
-    command.add("--android-root=" + getProductPath(vm) + "/system");
+    command.add(getDex2OatPath(vm).toAbsolutePath().toString());
+    command.add("--android-root=" + getProductPath(vm).toAbsolutePath() + "/system");
     command.add("--runtime-arg");
     command.add("-verbose:verifier");
     command.add("--runtime-arg");
     command.add("-Xnorelocate");
     command.add("--dex-file=" + file.toAbsolutePath());
     command.add("--oat-file=" + outFile.toAbsolutePath());
-    // TODO(zerny): Create a proper interface for invoking dex2oat. Hardcoding arch here is a hack!
     command.add("--instruction-set=" + getArchString(vm));
+    if (vm.version.equals(DexVm.Version.V12_0_0)) {
+      command.add(
+          "--boot-image="
+              + getDexVmPath(vm).toAbsolutePath()
+              + "/apex/art_boot_images/javalib/boot.art");
+    }
     ProcessBuilder builder = new ProcessBuilder(command);
+    builder.directory(getDexVmPath(vm).toFile());
     builder.environment().put("LD_LIBRARY_PATH", getDexVmLibPath(vm).toString());
-    return runProcess(builder);
+    ProcessResult processResult = runProcess(builder);
+    return processResult;
   }
 
   public static ProcessResult runProguardRaw(
@@ -2188,6 +2255,7 @@
 
   public static ProcessResult runProcess(ProcessBuilder builder, PrintStream out)
       throws IOException {
+    out.println("In " + builder.directory());
     String command = String.join(" ", builder.command());
     out.println(command);
     return drainProcessOutputStreams(builder.start(), command);
diff --git a/tools/dex2oat.py b/tools/dex2oat.py
index 04422cf..10c4732 100755
--- a/tools/dex2oat.py
+++ b/tools/dex2oat.py
@@ -12,16 +12,21 @@
 
 LINUX_DIR = os.path.join(utils.TOOLS_DIR, 'linux')
 
+LATEST = '12.0.0'
+
 VERSIONS = [
-  'default',
-  '9.0.0',
-  '8.1.0',
-  '7.0.0',
+  '12.0.0',
+  # TODO(b/258170524): Fix the broken dex2oat versions.
+  # 'default',
+  # '9.0.0',
+  # '8.1.0',
+  # '7.0.0',
   '6.0.1',
-  '5.1.1',
+  # '5.1.1',
 ]
 
 DIRS = {
+  '12.0.0': 'host/art-12.0.0-beta4',
   'default': 'art',
   '9.0.0': 'art-9.0.0',
   '8.1.0': 'art-8.1.0',
@@ -31,6 +36,7 @@
 }
 
 PRODUCTS = {
+  '12.0.0': 'redfin',
   'default': 'angler',
   '9.0.0': 'marlin',
   '8.1.0': 'marlin',
@@ -40,6 +46,7 @@
 }
 
 ARCHS = {
+  '12.0.0': 'x86_64',
   'default': 'arm64',
   '9.0.0': 'arm64',
   '8.1.0': 'arm64',
@@ -58,12 +65,16 @@
   'all',
 ]
 
+BOOT_IMAGE = {
+  '12.0.0': 'apex/art_boot_images/javalib/boot.art'
+}
+
 def ParseOptions():
   parser = optparse.OptionParser()
   parser.add_option('--version',
-                    help='Version of dex2oat. (defaults to latest, eg, tools/linux/art).',
+                    help='Version of dex2oat. (defaults to latest: ' + LATEST + ').',
                     choices=VERSIONS,
-                    default='default')
+                    default=LATEST)
   parser.add_option('--all',
                     help='Run dex2oat on all possible versions',
                     default=False,
@@ -96,7 +107,9 @@
     print("")
   return 0
 
-def run(dexfile, oatfile=None, version='default', verbose=[]):
+def run(dexfile, oatfile=None, version=None, verbose=[]):
+  if not version:
+    version = LATEST
   # dex2oat accepts non-existent dex files, check here instead
   if not os.path.exists(dexfile):
     raise Exception('DEX file not found: "{}"'.format(dexfile))
@@ -117,9 +130,12 @@
     ]
     for flag in verbose:
       cmd += ['--runtime-arg', '-verbose:' + flag]
+    if version in BOOT_IMAGE:
+      cmd += ['--boot-image=' + BOOT_IMAGE[version]]
     env = {"LD_LIBRARY_PATH": os.path.join(base, 'lib')}
     utils.PrintCmd(cmd)
-    subprocess.check_call(cmd, env = env)
+    with utils.ChangedWorkingDirectory(base):
+      subprocess.check_call(cmd, env = env)
 
 if __name__ == '__main__':
   sys.exit(Main())
diff --git a/tools/linux/README.art-versions b/tools/linux/README.art-versions
index 5e38ebd..611c06e 100644
--- a/tools/linux/README.art-versions
+++ b/tools/linux/README.art-versions
@@ -115,6 +115,10 @@
      --art-dir host/art-12.0.0-beta4 \
      --android-product redfin
 
+The dex2oat tool expects to find core-oj.dex in out/host/linux-x86 so copy it.
+
+(cd tools/linux/host; cp -r apex out/host/linux-x86/apex)
+
 (cd tools/linux/host; upload_to_google_storage.py -a --bucket r8-deps art-12.0.0-beta4)
 
 art-10.0.0 (Android Q)
diff --git a/tools/linux/host/art-12.0.0-beta4.tar.gz.sha1 b/tools/linux/host/art-12.0.0-beta4.tar.gz.sha1
index b95d909..9f80774 100644
--- a/tools/linux/host/art-12.0.0-beta4.tar.gz.sha1
+++ b/tools/linux/host/art-12.0.0-beta4.tar.gz.sha1
@@ -1 +1 @@
-9b6d0b061669e0fb1b09ba92c3650d5c7bdc9e85
\ No newline at end of file
+df7267e9eff9cc1812b5a7b4111e7175d5e186e9
\ No newline at end of file