diff --git a/src/test/java/com/android/tools/r8/apimodel/ApiModelOutlineConstClassTest.java b/src/test/java/com/android/tools/r8/apimodel/ApiModelOutlineConstClassTest.java
new file mode 100644
index 0000000..adb64ce
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/apimodel/ApiModelOutlineConstClassTest.java
@@ -0,0 +1,138 @@
+// Copyright (c) 2022, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.apimodel;
+
+import static com.android.tools.r8.apimodel.ApiModelingTestHelper.setMockApiLevelForClass;
+import static com.android.tools.r8.apimodel.ApiModelingTestHelper.verifyThat;
+import static org.junit.Assume.assumeTrue;
+
+import com.android.tools.r8.CompilationMode;
+import com.android.tools.r8.SingleTestRunResult;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestCompilerBuilder;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.testing.AndroidBuildVersion;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameter;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class ApiModelOutlineConstClassTest extends TestBase {
+
+  private static final AndroidApiLevel classApiLevel = AndroidApiLevel.M;
+
+  private static final String[] EXPECTED = new String[] {"class " + typeName(LibraryClass.class)};
+
+  @Parameter public TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimes().withAllApiLevelsAlsoForCf().build();
+  }
+
+  private void setupTestBuilder(TestCompilerBuilder<?, ?, ?, ?, ?> testBuilder) {
+    testBuilder
+        .addLibraryClasses(LibraryClass.class)
+        .addDefaultRuntimeLibrary(parameters)
+        .addProgramClasses(Main.class)
+        .setMinApi(parameters.getApiLevel())
+        .addAndroidBuildVersion(getApiLevelForRuntime())
+        .apply(setMockApiLevelForClass(LibraryClass.class, classApiLevel))
+        .apply(ApiModelingTestHelper::enableApiCallerIdentification)
+        .apply(ApiModelingTestHelper::enableOutliningOfMethods)
+        .apply(ApiModelingTestHelper::enableStubbingOfClasses);
+  }
+
+  public AndroidApiLevel getApiLevelForRuntime() {
+    return parameters.isCfRuntime()
+        ? AndroidApiLevel.B
+        : parameters.getRuntime().asDex().maxSupportedApiLevel();
+  }
+
+  public boolean addToBootClasspath() {
+    return getApiLevelForRuntime().isGreaterThanOrEqualTo(classApiLevel);
+  }
+
+  @Test
+  public void testReference() throws Exception {
+    assumeTrue(parameters.isCfRuntime() && parameters.getApiLevel().isEqualTo(AndroidApiLevel.B));
+    testForJvm()
+        .addProgramClasses(Main.class)
+        .addAndroidBuildVersion(parameters.getApiLevel())
+        .run(parameters.getRuntime(), Main.class)
+        .apply(this::checkOutput);
+  }
+
+  @Test
+  public void testD8Debug() throws Exception {
+    assumeTrue(parameters.isDexRuntime());
+    testForD8()
+        .setMode(CompilationMode.DEBUG)
+        .apply(this::setupTestBuilder)
+        .compile()
+        .inspect(this::inspect)
+        .applyIf(addToBootClasspath(), b -> b.addBootClasspathClasses(LibraryClass.class))
+        .run(parameters.getRuntime(), Main.class)
+        .apply(this::checkOutput);
+  }
+
+  @Test
+  public void testD8Release() throws Exception {
+    assumeTrue(parameters.isDexRuntime());
+    testForD8()
+        .setMode(CompilationMode.RELEASE)
+        .apply(this::setupTestBuilder)
+        .compile()
+        .inspect(this::inspect)
+        .applyIf(addToBootClasspath(), b -> b.addBootClasspathClasses(LibraryClass.class))
+        .run(parameters.getRuntime(), Main.class)
+        .apply(this::checkOutput);
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    testForR8(parameters.getBackend())
+        .apply(this::setupTestBuilder)
+        .addKeepMainRule(Main.class)
+        .compile()
+        .inspect(this::inspect)
+        .applyIf(addToBootClasspath(), b -> b.addBootClasspathClasses(LibraryClass.class))
+        .run(parameters.getRuntime(), Main.class)
+        .apply(this::checkOutput);
+  }
+
+  private void inspect(CodeInspector inspector) throws Exception {
+    verifyThat(inspector, parameters, LibraryClass.class)
+        // TODO(b/258270051): We should outline const class references to new api levels.
+        .hasNotConstClassOutlinedFrom(Main.class.getMethod("main", String[].class));
+  }
+
+  private void checkOutput(SingleTestRunResult<?> runResult) {
+    if (addToBootClasspath()) {
+      runResult.assertSuccessWithOutputLines(EXPECTED);
+    } else {
+      runResult.assertSuccessWithOutputLines("Not checking instance of");
+    }
+  }
+
+  // Only present from api 23.
+  public static class LibraryClass {}
+
+  public static class Main {
+
+    public static void main(String[] args) {
+      if (AndroidBuildVersion.VERSION >= 23) {
+        System.out.println(LibraryClass.class);
+      } else {
+        System.out.println("Not checking instance of");
+      }
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/apimodel/ApiModelingTestHelper.java b/src/test/java/com/android/tools/r8/apimodel/ApiModelingTestHelper.java
index 1e45b00..b487caf 100644
--- a/src/test/java/com/android/tools/r8/apimodel/ApiModelingTestHelper.java
+++ b/src/test/java/com/android/tools/r8/apimodel/ApiModelingTestHelper.java
@@ -5,8 +5,6 @@
 package com.android.tools.r8.apimodel;
 
 import static com.android.tools.r8.utils.codeinspector.CodeMatchers.accessesField;
-import static com.android.tools.r8.utils.codeinspector.CodeMatchers.containsCheckCast;
-import static com.android.tools.r8.utils.codeinspector.CodeMatchers.containsInstanceOf;
 import static com.android.tools.r8.utils.codeinspector.CodeMatchers.invokesMethod;
 import static com.android.tools.r8.utils.codeinspector.CodeMatchers.invokesMethodWithHolderAndName;
 import static com.android.tools.r8.utils.codeinspector.CodeMatchers.invokesMethodWithName;
@@ -39,7 +37,9 @@
 import java.util.Collections;
 import java.util.List;
 import java.util.function.BiConsumer;
+import java.util.function.Function;
 import java.util.stream.Collectors;
+import org.hamcrest.Matcher;
 
 public abstract class ApiModelingTestHelper {
 
@@ -272,35 +272,11 @@
     }
 
     public void hasCheckCastOutlinedFrom(Method method) {
-      // Check that we call is in a synthetic class with a check cast
-      ClassReference classOfInterestReference = Reference.classFromClass(classOfInterest);
-      List<FoundMethodSubject> outlinedMethod =
-          inspector.allClasses().stream()
-              .filter(
-                  clazz ->
-                      clazz
-                          .getOriginalName()
-                          .startsWith(
-                              SyntheticItemsTestUtils.syntheticApiOutlineClassPrefix(
-                                  method.getDeclaringClass())))
-              .flatMap(clazz -> clazz.allMethods().stream())
-              .filter(
-                  methodSubject ->
-                      methodSubject.isSynthetic()
-                          && containsCheckCast(classOfInterestReference).matches(methodSubject))
-              .collect(Collectors.toList());
-      assertFalse(outlinedMethod.isEmpty());
-      // Assert that method invokes the outline
-      MethodSubject caller = inspector.method(method);
-      assertThat(caller, isPresent());
-      assertThat(caller, invokesMethod(outlinedMethod.get(0)));
+      hasOutlinedInstructionWithClassReference(method, CodeMatchers::containsCheckCast);
     }
 
     public void hasNotCheckCastOutlinedFrom(Method method) {
-      ClassReference classOfInterestReference = Reference.classFromClass(classOfInterest);
-      MethodSubject caller = inspector.method(method);
-      assertThat(caller, isPresent());
-      assertThat(caller, containsCheckCast(classOfInterestReference));
+      hasNotOulinedInstructionWithClassReference(method, CodeMatchers::containsCheckCast);
     }
 
     void hasInstanceOfOutlinedFromUntil(Method method, AndroidApiLevel apiLevel) {
@@ -312,8 +288,34 @@
     }
 
     public void hasInstanceOfOutlinedFrom(Method method) {
+      hasOutlinedInstructionWithClassReference(method, CodeMatchers::containsInstanceOf);
+    }
+
+    public void hasNotInstanceOfOutlinedFrom(Method method) {
+      hasNotOulinedInstructionWithClassReference(method, CodeMatchers::containsInstanceOf);
+    }
+
+    void hasConstClassOutlinedFromUntil(Method method, AndroidApiLevel apiLevel) {
+      if (parameters.isDexRuntime() && parameters.getApiLevel().isLessThan(apiLevel)) {
+        hasConstClassOutlinedFrom(method);
+      } else {
+        hasNotConstClassOutlinedFrom(method);
+      }
+    }
+
+    public void hasConstClassOutlinedFrom(Method method) {
+      hasOutlinedInstructionWithClassReference(method, CodeMatchers::containsConstClass);
+    }
+
+    public void hasNotConstClassOutlinedFrom(Method method) {
+      hasNotOulinedInstructionWithClassReference(method, CodeMatchers::containsConstClass);
+    }
+
+    private void hasOutlinedInstructionWithClassReference(
+        Method method, Function<ClassReference, Matcher<? super MethodSubject>> matcher) {
       // Check that we call is in a synthetic class with an instance of.
       ClassReference classOfInterestReference = Reference.classFromClass(classOfInterest);
+      Matcher<? super MethodSubject> instructionMatcher = matcher.apply(classOfInterestReference);
       List<FoundMethodSubject> outlinedMethod =
           inspector.allClasses().stream()
               .filter(
@@ -326,8 +328,7 @@
               .flatMap(clazz -> clazz.allMethods().stream())
               .filter(
                   methodSubject ->
-                      methodSubject.isSynthetic()
-                          && containsInstanceOf(classOfInterestReference).matches(methodSubject))
+                      methodSubject.isSynthetic() && instructionMatcher.matches(methodSubject))
               .collect(Collectors.toList());
       assertFalse(outlinedMethod.isEmpty());
       // Assert that method invokes the outline
@@ -336,11 +337,12 @@
       assertThat(caller, invokesMethod(outlinedMethod.get(0)));
     }
 
-    public void hasNotInstanceOfOutlinedFrom(Method method) {
+    private void hasNotOulinedInstructionWithClassReference(
+        Method method, Function<ClassReference, Matcher<? super MethodSubject>> matcher) {
       ClassReference classOfInterestReference = Reference.classFromClass(classOfInterest);
       MethodSubject caller = inspector.method(method);
       assertThat(caller, isPresent());
-      assertThat(caller, containsInstanceOf(classOfInterestReference));
+      assertThat(caller, matcher.apply(classOfInterestReference));
     }
   }
 
diff --git a/src/test/java/com/android/tools/r8/utils/codeinspector/CodeMatchers.java b/src/test/java/com/android/tools/r8/utils/codeinspector/CodeMatchers.java
index 70e7eab..9ec695c 100644
--- a/src/test/java/com/android/tools/r8/utils/codeinspector/CodeMatchers.java
+++ b/src/test/java/com/android/tools/r8/utils/codeinspector/CodeMatchers.java
@@ -122,6 +122,31 @@
     };
   }
 
+  public static Matcher<MethodSubject> containsConstClass(ClassReference classReference) {
+    return new TypeSafeMatcher<MethodSubject>() {
+      @Override
+      protected boolean matchesSafely(MethodSubject subject) {
+        return subject.isPresent()
+            && subject.getMethod().hasCode()
+            && subject
+                .streamInstructions()
+                .anyMatch(
+                    instructionSubject ->
+                        instructionSubject.isConstClass(classReference.getTypeName()));
+      }
+
+      @Override
+      public void describeTo(Description description) {
+        description.appendText("contains constclass");
+      }
+
+      @Override
+      public void describeMismatchSafely(MethodSubject subject, Description description) {
+        description.appendText("method did not");
+      }
+    };
+  }
+
   public static Matcher<MethodSubject> instantiatesClass(Class<?> clazz) {
     return instantiatesClass(clazz.getTypeName());
   }