diff --git a/src/main/java/com/android/tools/r8/graph/MethodResolutionResult.java b/src/main/java/com/android/tools/r8/graph/MethodResolutionResult.java
index 6b6991d..c56866e 100644
--- a/src/main/java/com/android/tools/r8/graph/MethodResolutionResult.java
+++ b/src/main/java/com/android/tools/r8/graph/MethodResolutionResult.java
@@ -1127,6 +1127,11 @@
         Consumer<? super FailedResolutionResult> failedResolutionConsumer) {
       failedResolutionConsumer.accept(this);
     }
+
+    public boolean hasTypesOrMethodsCausingError() {
+      return (typesCausingError != null && !typesCausingError.isEmpty())
+          || hasMethodsCausingError();
+    }
   }
 
   public static class ClassNotFoundResult extends FailedResolutionResult {
diff --git a/src/main/java/com/android/tools/r8/tracereferences/Tracer.java b/src/main/java/com/android/tools/r8/tracereferences/Tracer.java
index a17a299..3a25350 100644
--- a/src/main/java/com/android/tools/r8/tracereferences/Tracer.java
+++ b/src/main/java/com/android/tools/r8/tracereferences/Tracer.java
@@ -245,11 +245,12 @@
           }
         }
       }
-
+      MethodResolutionResult methodResolutionResult =
+          method.getHolder().isInterface()
+              ? appInfo().resolveMethodOnInterface(method.getHolder(), method.getReference())
+              : appInfo().resolveMethodOnClass(method.getHolder(), method.getReference());
       DexClassAndMethod superTarget =
-          appInfo()
-              .resolveMethodOnLegacy(method.getHolder(), method.getReference())
-              .lookupInvokeSpecialTarget(method.getHolder(), appInfo());
+          methodResolutionResult.lookupInvokeSpecialTarget(method.getHolder(), appInfo());
       if (superTarget != null
           && !superTarget.isProgramMethod()
           && isTargetType(superTarget.getHolderType())) {
@@ -269,8 +270,7 @@
           method -> {
             DexClassAndMethod resolvedMethod =
                 appInfo()
-                    .resolveMethodOnLegacy(
-                        superType, method.getReference(), superType != clazz.superType)
+                    .resolveMethodOn(superType, method.getReference(), superType != clazz.superType)
                     .getResolutionPair();
             if (resolvedMethod != null
                 && !resolvedMethod.isProgramMethod()
@@ -314,7 +314,7 @@
         assert lookupResult.getType().isStatic();
         DexMethod rewrittenMethod = lookupResult.getReference();
         handleRewrittenMethodResolution(
-            rewrittenMethod, appInfo().unsafeResolveMethodDueToDexFormatLegacy(rewrittenMethod));
+            rewrittenMethod, appInfo().unsafeResolveMethodDueToDexFormat(rewrittenMethod));
       }
 
       @Override
@@ -323,7 +323,7 @@
         assert lookupResult.getType().isSuper();
         DexMethod rewrittenMethod = lookupResult.getReference();
         MethodResolutionResult resolutionResult =
-            appInfo().unsafeResolveMethodDueToDexFormatLegacy(rewrittenMethod);
+            appInfo().unsafeResolveMethodDueToDexFormat(rewrittenMethod);
         if (resolutionResult.isFailedResolution()
             && resolutionResult.asFailedResolution().hasMethodsCausingError()) {
           handleRewrittenMethodResolution(rewrittenMethod, resolutionResult);
@@ -352,23 +352,26 @@
         handleRewrittenMethodResolution(
             method,
             lookupResult.getType().isInterface()
-                ? appInfo().resolveMethodOnInterfaceHolderLegacy(method)
-                : appInfo().resolveMethodOnClassHolderLegacy(method));
+                ? appInfo().resolveMethodOnInterfaceHolder(method)
+                : appInfo().resolveMethodOnClassHolder(method));
       }
 
       private void handleRewrittenMethodResolution(
           DexMethod method, MethodResolutionResult resolutionResult) {
-        if (resolutionResult.isFailedResolution()
-            && resolutionResult.asFailedResolution().hasMethodsCausingError()) {
-          resolutionResult
-              .asFailedResolution()
-              .forEachFailureDependency(
-                  type -> addType(type, referencedFrom),
-                  methodCausingFailure ->
-                      handleRewrittenMethodReference(method, methodCausingFailure));
-          return;
-        }
-        handleRewrittenMethodReference(method, resolutionResult.getResolutionPair());
+        resolutionResult.forEachMethodResolutionResult(
+            result -> {
+              if (result.isFailedResolution()
+                  && result.asFailedResolution().hasTypesOrMethodsCausingError()) {
+                result
+                    .asFailedResolution()
+                    .forEachFailureDependency(
+                        type -> addType(type, referencedFrom),
+                        methodCausingFailure ->
+                            handleRewrittenMethodReference(method, methodCausingFailure));
+                return;
+              }
+              handleRewrittenMethodReference(method, result.getResolutionPair());
+            });
       }
 
       private void handleRewrittenMethodReference(
diff --git a/src/test/java/com/android/tools/r8/tracereferences/TraceMethodResolutionWithLibraryAndProgramClassTest.java b/src/test/java/com/android/tools/r8/tracereferences/TraceMethodResolutionWithLibraryAndProgramClassTest.java
index 4dcf1cd..0a2809a 100644
--- a/src/test/java/com/android/tools/r8/tracereferences/TraceMethodResolutionWithLibraryAndProgramClassTest.java
+++ b/src/test/java/com/android/tools/r8/tracereferences/TraceMethodResolutionWithLibraryAndProgramClassTest.java
@@ -13,11 +13,10 @@
 import com.android.tools.r8.ToolHelper;
 import com.android.tools.r8.references.MethodReference;
 import com.android.tools.r8.references.Reference;
-import com.android.tools.r8.transformers.ClassFileTransformer.MethodPredicate;
-import com.android.tools.r8.utils.DescriptorUtils;
 import com.android.tools.r8.utils.ZipUtils.ZipBuilder;
 import com.google.common.collect.ImmutableSet;
 import java.nio.file.Path;
+import java.util.Collections;
 import java.util.HashSet;
 import java.util.Set;
 import org.junit.Test;
@@ -26,7 +25,6 @@
 import org.junit.runners.Parameterized.Parameter;
 import org.junit.runners.Parameterized.Parameters;
 
-// This is a regression test for b/226170842.
 @RunWith(Parameterized.class)
 public class TraceMethodResolutionWithLibraryAndProgramClassTest extends TestBase {
 
@@ -59,23 +57,21 @@
   }
 
   @Test
-  public void testInvalidResolution() throws Exception {
+  public void testValidResolution() throws Exception {
     Path dir = temp.newFolder().toPath();
     Path libJar =
         ZipBuilder.builder(dir.resolve("lib.jar"))
             .addFilesRelative(
-                ToolHelper.getClassPathForTests(), ToolHelper.getClassFileForTestClass(A.class))
-            .addBytes(
-                DescriptorUtils.getPathFromJavaType(B.class),
-                transformer(B.class).removeMethods(MethodPredicate.all()).transform())
+                ToolHelper.getClassPathForTests(),
+                ToolHelper.getClassFileForTestClass(A.class),
+                ToolHelper.getClassFileForTestClass(B.class))
             .build();
     Path targetJar =
         ZipBuilder.builder(dir.resolve("target.jar"))
-            .addBytes(
-                DescriptorUtils.getPathFromJavaType(A.class),
-                transformer(A.class).removeMethods(MethodPredicate.all()).transform())
             .addFilesRelative(
-                ToolHelper.getClassPathForTests(), ToolHelper.getClassFileForTestClass(B.class))
+                ToolHelper.getClassPathForTests(),
+                ToolHelper.getClassFileForTestClass(A.class),
+                ToolHelper.getClassFileForTestClass(B.class))
             .build();
     Path sourceJar =
         ZipBuilder.builder(dir.resolve("source.jar"))
@@ -94,14 +90,11 @@
     ImmutableSet<MethodReference> foundSet =
         ImmutableSet.of(
             Reference.methodFromMethod(A.class.getMethod("foo")),
-            Reference.methodFromMethod(A.class.getMethod("bar")));
-    ImmutableSet<MethodReference> missingSet =
-        ImmutableSet.of(
+            Reference.methodFromMethod(A.class.getMethod("bar")),
             Reference.methodFromMethod(B.class.getMethod("baz")),
             Reference.methodFromMethod(B.class.getMethod("qux")));
     assertEquals(foundSet, consumer.seenMethods);
-    // TODO(b/226170842): Methods should not be missing.
-    assertEquals(missingSet, consumer.seenMissingMethods);
+    assertEquals(Collections.emptySet(), consumer.seenMissingMethods);
   }
 
   // A is added to both library and program, but the program one is missing the methods {foo,bar}
diff --git a/src/test/java/com/android/tools/r8/tracereferences/TraceMethodResolutionWithMissingLibraryAndProgramClassTest.java b/src/test/java/com/android/tools/r8/tracereferences/TraceMethodResolutionWithMissingLibraryAndProgramClassTest.java
new file mode 100644
index 0000000..18ece27
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/tracereferences/TraceMethodResolutionWithMissingLibraryAndProgramClassTest.java
@@ -0,0 +1,144 @@
+// 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.tracereferences;
+
+import static org.junit.Assert.assertEquals;
+
+import com.android.tools.r8.DiagnosticsHandler;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.references.MethodReference;
+import com.android.tools.r8.references.Reference;
+import com.android.tools.r8.transformers.ClassFileTransformer.MethodPredicate;
+import com.android.tools.r8.utils.DescriptorUtils;
+import com.android.tools.r8.utils.ZipUtils.ZipBuilder;
+import com.google.common.collect.ImmutableSet;
+import java.nio.file.Path;
+import java.util.HashSet;
+import java.util.Set;
+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;
+
+// This is a regression test for b/226170842.
+@RunWith(Parameterized.class)
+public class TraceMethodResolutionWithMissingLibraryAndProgramClassTest extends TestBase {
+
+  @Parameter() public TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withNoneRuntime().build();
+  }
+
+  static class SeenReferencesConsumer implements TraceReferencesConsumer {
+
+    private final Set<MethodReference> seenMethods = new HashSet<>();
+    private final Set<MethodReference> seenMissingMethods = new HashSet<>();
+
+    @Override
+    public void acceptType(TracedClass tracedClass, DiagnosticsHandler handler) {}
+
+    @Override
+    public void acceptField(TracedField tracedField, DiagnosticsHandler handler) {}
+
+    @Override
+    public void acceptMethod(TracedMethod tracedMethod, DiagnosticsHandler handler) {
+      if (tracedMethod.isMissingDefinition()) {
+        seenMissingMethods.add(tracedMethod.getReference());
+      } else {
+        seenMethods.add(tracedMethod.getReference());
+      }
+    }
+  }
+
+  @Test
+  public void testInvalidResolution() throws Exception {
+    Path dir = temp.newFolder().toPath();
+    Path libJar =
+        ZipBuilder.builder(dir.resolve("lib.jar"))
+            .addFilesRelative(
+                ToolHelper.getClassPathForTests(), ToolHelper.getClassFileForTestClass(A.class))
+            .addBytes(
+                DescriptorUtils.getPathFromJavaType(B.class),
+                transformer(B.class).removeMethods(MethodPredicate.all()).transform())
+            .build();
+    Path targetJar =
+        ZipBuilder.builder(dir.resolve("target.jar"))
+            .addBytes(
+                DescriptorUtils.getPathFromJavaType(A.class),
+                transformer(A.class).removeMethods(MethodPredicate.all()).transform())
+            .addFilesRelative(
+                ToolHelper.getClassPathForTests(), ToolHelper.getClassFileForTestClass(B.class))
+            .build();
+    Path sourceJar =
+        ZipBuilder.builder(dir.resolve("source.jar"))
+            .addFilesRelative(
+                ToolHelper.getClassPathForTests(), ToolHelper.getClassFileForTestClass(Main.class))
+            .build();
+    SeenReferencesConsumer consumer = new SeenReferencesConsumer();
+    TraceReferences.run(
+        TraceReferencesCommand.builder()
+            .addLibraryFiles(ToolHelper.getMostRecentAndroidJar())
+            .addLibraryFiles(libJar)
+            .addTargetFiles(targetJar)
+            .addSourceFiles(sourceJar)
+            .setConsumer(consumer)
+            .build());
+    ImmutableSet<MethodReference> foundSet =
+        ImmutableSet.of(
+            Reference.methodFromMethod(A.class.getMethod("foo")),
+            Reference.methodFromMethod(A.class.getMethod("bar")),
+            Reference.methodFromMethod(B.class.getMethod("baz")),
+            Reference.methodFromMethod(B.class.getMethod("qux")));
+    assertEquals(foundSet, consumer.seenMethods);
+    assertEquals(foundSet, consumer.seenMissingMethods);
+  }
+
+  // A is added to both library and program, but the program one is missing the methods {foo,bar}
+  public static class A {
+
+    public static boolean foo() {
+      return true;
+    }
+
+    public int bar() {
+      return 42;
+    }
+  }
+
+  // B is added to both library and program, but the library one is missing the methods {baz,qux}
+  public static class B {
+
+    public static boolean baz() {
+      return false;
+    }
+
+    public int qux() {
+      return 42;
+    }
+  }
+
+  public static class Main {
+
+    public static void main(String[] args) {
+      A a = getAInstance(null);
+      B b = getBInstance(null);
+      int value = (A.foo() && B.baz()) ? a.bar() : b.qux();
+    }
+
+    private static A getAInstance(Object o) {
+      return (A) o;
+    }
+
+    private static B getBInstance(Object o) {
+      return (B) o;
+    }
+  }
+}