diff --git a/src/main/java/com/android/tools/r8/graph/AppInfo.java b/src/main/java/com/android/tools/r8/graph/AppInfo.java
index b02bb19..07512e5 100644
--- a/src/main/java/com/android/tools/r8/graph/AppInfo.java
+++ b/src/main/java/com/android/tools/r8/graph/AppInfo.java
@@ -226,14 +226,13 @@
    * @param context the method the invoke is contained in, i.e., the caller.
    * @return The actual target for {@code method} if on the holder, or {@code null}.
    */
-  @SuppressWarnings("ReferenceEquality")
-  public final DexEncodedMethod lookupStaticTargetOnItself(
+  public final DexClassAndMethod lookupStaticTargetOnItself(
       DexMethod method, ProgramMethod context) {
-    if (method.holder != context.getHolderType()) {
+    if (!method.getHolderType().isIdenticalTo(context.getHolderType())) {
       return null;
     }
-    DexEncodedMethod singleTarget = context.getHolder().lookupDirectMethod(method);
-    if (singleTarget != null && singleTarget.isStatic()) {
+    DexClassAndMethod singleTarget = context.getHolder().lookupDirectClassMethod(method);
+    if (singleTarget != null && singleTarget.getAccessFlags().isStatic()) {
       return singleTarget;
     }
     return null;
@@ -246,14 +245,13 @@
    * @param context the method the invoke is contained in, i.e., the caller.
    * @return The actual target for {@code method} if on the holder, or {@code null}.
    */
-  @SuppressWarnings("ReferenceEquality")
-  public final DexEncodedMethod lookupDirectTargetOnItself(
+  public final DexClassAndMethod lookupDirectTargetOnItself(
       DexMethod method, ProgramMethod context) {
-    if (method.holder != context.getHolderType()) {
+    if (!method.getHolderType().isIdenticalTo(context.getHolderType())) {
       return null;
     }
-    DexEncodedMethod singleTarget = context.getHolder().lookupDirectMethod(method);
-    if (singleTarget != null && !singleTarget.isStatic()) {
+    DexClassAndMethod singleTarget = context.getHolder().lookupDirectClassMethod(method);
+    if (singleTarget != null && !singleTarget.getAccessFlags().isStatic()) {
       return singleTarget;
     }
     return null;
diff --git a/src/main/java/com/android/tools/r8/graph/AppInfoWithClassHierarchy.java b/src/main/java/com/android/tools/r8/graph/AppInfoWithClassHierarchy.java
index fcfb3cf..d121559 100644
--- a/src/main/java/com/android/tools/r8/graph/AppInfoWithClassHierarchy.java
+++ b/src/main/java/com/android/tools/r8/graph/AppInfoWithClassHierarchy.java
@@ -627,14 +627,14 @@
    * @return The actual target for {@code method} or {@code null} if none found.
    */
   // TODO(b/155968472): This should take a parameter `boolean isInterface` and use resolveMethod().
-  public DexEncodedMethod lookupStaticTarget(
+  public DexClassAndMethod lookupStaticTarget(
       DexMethod method,
       DexProgramClass context,
       AppView<? extends AppInfoWithClassHierarchy> appView) {
     return lookupStaticTarget(method, context, appView, appView.appInfo());
   }
 
-  public DexEncodedMethod lookupStaticTarget(
+  public DexClassAndMethod lookupStaticTarget(
       DexMethod method,
       DexProgramClass context,
       AppView<?> appView,
@@ -645,14 +645,14 @@
   }
 
   // TODO(b/155968472): This should take a parameter `boolean isInterface` and use resolveMethod().
-  public DexEncodedMethod lookupStaticTarget(
+  public DexClassAndMethod lookupStaticTarget(
       DexMethod method,
       ProgramMethod context,
       AppView<? extends AppInfoWithClassHierarchy> appView) {
     return lookupStaticTarget(method, context.getHolder(), appView);
   }
 
-  public DexEncodedMethod lookupStaticTarget(
+  public DexClassAndMethod lookupStaticTarget(
       DexMethod method,
       ProgramMethod context,
       AppView<?> appView,
@@ -713,14 +713,14 @@
    * @return The actual target for {@code method} or {@code null} if none found.
    */
   // TODO(b/155968472): This should take a parameter `boolean isInterface` and use resolveMethod().
-  public DexEncodedMethod lookupDirectTarget(
+  public DexClassAndMethod lookupDirectTarget(
       DexMethod method,
       DexProgramClass context,
       AppView<? extends AppInfoWithClassHierarchy> appView) {
     return lookupDirectTarget(method, context, appView, appView.appInfo());
   }
 
-  public DexEncodedMethod lookupDirectTarget(
+  public DexClassAndMethod lookupDirectTarget(
       DexMethod method,
       DexProgramClass context,
       AppView<?> appView,
@@ -731,14 +731,14 @@
   }
 
   // TODO(b/155968472): This should take a parameter `boolean isInterface` and use resolveMethod().
-  public DexEncodedMethod lookupDirectTarget(
+  public DexClassAndMethod lookupDirectTarget(
       DexMethod method,
       ProgramMethod context,
       AppView<? extends AppInfoWithClassHierarchy> appView) {
     return lookupDirectTarget(method, context, appView, appView.appInfo());
   }
 
-  public DexEncodedMethod lookupDirectTarget(
+  public DexClassAndMethod lookupDirectTarget(
       DexMethod method,
       ProgramMethod context,
       AppView<?> appView,
diff --git a/src/main/java/com/android/tools/r8/graph/DexClass.java b/src/main/java/com/android/tools/r8/graph/DexClass.java
index 263335f..e8c908a 100644
--- a/src/main/java/com/android/tools/r8/graph/DexClass.java
+++ b/src/main/java/com/android/tools/r8/graph/DexClass.java
@@ -499,6 +499,10 @@
     return field != null ? DexClassAndField.create(this, field) : null;
   }
 
+  public DexClassAndMethod lookupDirectClassMethod(DexMethod method) {
+    return toClassMethodOrNull(lookupDirectMethod(method));
+  }
+
   /** Find direct method in this class matching {@param method}. */
   public DexEncodedMethod lookupDirectMethod(DexMethod method) {
     return methodCollection.getDirectMethod(method);
@@ -509,6 +513,10 @@
     return methodCollection.getDirectMethod(predicate);
   }
 
+  public DexClassAndMethod lookupVirtualClassMethod(DexMethod method) {
+    return toClassMethodOrNull(lookupVirtualMethod(method));
+  }
+
   /** Find virtual method in this class matching {@param method}. */
   public DexEncodedMethod lookupVirtualMethod(DexMethod method) {
     return methodCollection.getVirtualMethod(method);
diff --git a/src/main/java/com/android/tools/r8/graph/DexClassAndMethod.java b/src/main/java/com/android/tools/r8/graph/DexClassAndMethod.java
index 4af04cb..f46fc2b 100644
--- a/src/main/java/com/android/tools/r8/graph/DexClassAndMethod.java
+++ b/src/main/java/com/android/tools/r8/graph/DexClassAndMethod.java
@@ -38,7 +38,9 @@
 
   @SuppressWarnings("ReferenceEquality")
   public boolean isStructurallyEqualTo(DexClassAndMethod other) {
-    return getDefinition() == other.getDefinition() && getHolder() == other.getHolder();
+    return other != null
+        && getDefinition() == other.getDefinition()
+        && getHolder() == other.getHolder();
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/graph/DispatchTargetLookupResult.java b/src/main/java/com/android/tools/r8/graph/DispatchTargetLookupResult.java
new file mode 100644
index 0000000..0190e2c
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/graph/DispatchTargetLookupResult.java
@@ -0,0 +1,41 @@
+// Copyright (c) 2023, 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.graph;
+
+import com.android.tools.r8.graph.MethodResolutionResult.SingleResolutionResult;
+
+public abstract class DispatchTargetLookupResult {
+
+  private final SingleResolutionResult<?> singleResolutionResult;
+
+  DispatchTargetLookupResult(SingleResolutionResult<?> singleResolutionResult) {
+    assert singleResolutionResult != null;
+    this.singleResolutionResult = singleResolutionResult;
+  }
+
+  public static DispatchTargetLookupResult create(
+      DexClassAndMethod singleDispatchTarget, SingleResolutionResult<?> singleResolutionResult) {
+    if (singleDispatchTarget != null) {
+      return new SingleDispatchTargetLookupResult(singleDispatchTarget, singleResolutionResult);
+    } else {
+      return new UnknownDispatchTargetLookupResult(singleResolutionResult);
+    }
+  }
+
+  public SingleResolutionResult<?> getResolutionResult() {
+    return singleResolutionResult;
+  }
+
+  public DexClassAndMethod getSingleDispatchTarget() {
+    return null;
+  }
+
+  public boolean isSingleResult() {
+    return false;
+  }
+
+  public SingleDispatchTargetLookupResult asSingleResult() {
+    return null;
+  }
+}
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 428c57d..e8290ab 100644
--- a/src/main/java/com/android/tools/r8/graph/MethodResolutionResult.java
+++ b/src/main/java/com/android/tools/r8/graph/MethodResolutionResult.java
@@ -8,7 +8,12 @@
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.LookupResult.LookupResultSuccess;
 import com.android.tools.r8.graph.LookupResult.LookupResultSuccess.LookupResultCollectionState;
+import com.android.tools.r8.ir.analysis.type.DynamicType;
+import com.android.tools.r8.ir.code.InvokeDirect;
 import com.android.tools.r8.ir.code.InvokeMethod;
+import com.android.tools.r8.ir.code.InvokeMethodWithReceiver;
+import com.android.tools.r8.ir.code.InvokeStatic;
+import com.android.tools.r8.ir.code.InvokeSuper;
 import com.android.tools.r8.ir.desugar.LambdaDescriptor;
 import com.android.tools.r8.ir.optimize.info.DefaultMethodOptimizationInfo;
 import com.android.tools.r8.ir.optimize.info.MethodOptimizationInfo;
@@ -34,6 +39,10 @@
 public abstract class MethodResolutionResult
     extends MemberResolutionResult<DexEncodedMethod, DexMethod> {
 
+  public static UnknownMethodResolutionResult unknown() {
+    return UnknownMethodResolutionResult.get();
+  }
+
   @Override
   public boolean isMethodResolutionResult() {
     return true;
@@ -136,7 +145,13 @@
     return null;
   }
 
-  /** Short-hand to get the single resolution method if resolution finds it, null otherwise. */
+  /**
+   * Short-hand to get the single resolution method if resolution finds it, null otherwise.
+   *
+   * @deprecated Use {@link #getResolvedMethod()}.
+   */
+  @Deprecated
+  @SuppressWarnings("InlineMeSuggester")
   public final DexEncodedMethod getSingleTarget() {
     return isSingleResolution() ? asSingleResolution().getResolvedMethod() : null;
   }
@@ -173,21 +188,21 @@
       DexProgramClass context, AppView<?> appView, AppInfoWithClassHierarchy appInfo);
 
   /** Lookup the single target of an invoke-direct on this resolution result if possible. */
-  public final DexEncodedMethod lookupInvokeDirectTarget(
+  public final DexClassAndMethod lookupInvokeDirectTarget(
       DexProgramClass context, AppView<? extends AppInfoWithClassHierarchy> appView) {
     return lookupInvokeDirectTarget(context, appView, appView.appInfo());
   }
 
-  public abstract DexEncodedMethod lookupInvokeDirectTarget(
+  public abstract DexClassAndMethod lookupInvokeDirectTarget(
       DexProgramClass context, AppView<?> appView, AppInfoWithClassHierarchy appInfo);
 
   /** Lookup the single target of an invoke-static on this resolution result if possible. */
-  public final DexEncodedMethod lookupInvokeStaticTarget(
+  public final DexClassAndMethod lookupInvokeStaticTarget(
       DexProgramClass context, AppView<? extends AppInfoWithClassHierarchy> appView) {
     return lookupInvokeStaticTarget(context, appView, appView.appInfo());
   }
 
-  public abstract DexEncodedMethod lookupInvokeStaticTarget(
+  public abstract DexClassAndMethod lookupInvokeStaticTarget(
       DexProgramClass context, AppView<?> appView, AppInfoWithClassHierarchy appInfo);
 
   public abstract LookupResult lookupVirtualDispatchTargets(
@@ -300,6 +315,126 @@
       return DefaultMethodOptimizationInfo.getInstance();
     }
 
+    public DispatchTargetLookupResult lookupDispatchTarget(
+        AppView<?> appView, InvokeMethod invoke, ProgramMethod context) {
+      switch (invoke.getType()) {
+        case DIRECT:
+          return lookupDirectDispatchTarget(appView, invoke.asInvokeDirect(), context);
+        case POLYMORPHIC:
+          return new UnknownDispatchTargetLookupResult(this);
+        case STATIC:
+          return lookupStaticDispatchTarget(appView, invoke.asInvokeStatic(), context);
+        case SUPER:
+          return lookupSuperDispatchTarget(appView, invoke.asInvokeSuper(), context);
+        default:
+          break;
+      }
+      assert invoke.isInvokeInterface() || invoke.isInvokeVirtual();
+      InvokeMethodWithReceiver invokeMethodWithReceiver = invoke.asInvokeMethodWithReceiver();
+      DynamicType dynamicReceiverType =
+          appView.hasLiveness()
+              ? invokeMethodWithReceiver.getReceiver().getDynamicType(appView.withLiveness())
+              : DynamicType.unknown();
+      return lookupVirtualDispatchTarget(
+          appView, invokeMethodWithReceiver, dynamicReceiverType, context);
+    }
+
+    private DispatchTargetLookupResult lookupDirectDispatchTarget(
+        AppView<?> appView, InvokeDirect invoke, ProgramMethod context) {
+      DexMethod invokedMethod = invoke.getInvokedMethod();
+      DexClassAndMethod result;
+      if (appView.hasLiveness()) {
+        AppView<AppInfoWithLiveness> appViewWithLiveness = appView.withLiveness();
+        AppInfoWithLiveness appInfo = appViewWithLiveness.appInfo();
+        result = appInfo.lookupDirectTarget(invokedMethod, context, appViewWithLiveness);
+        assert invoke.verifyD8LookupResult(
+            result, appView.appInfo().lookupDirectTargetOnItself(invokedMethod, context));
+      } else {
+        // In D8, we can treat invoke-direct instructions as having a single target if the invoke is
+        // targeting a method in the enclosing class.
+        result = appView.appInfo().lookupDirectTargetOnItself(invokedMethod, context);
+      }
+      return DispatchTargetLookupResult.create(result, this);
+    }
+
+    private DispatchTargetLookupResult lookupStaticDispatchTarget(
+        AppView<?> appView, InvokeStatic invoke, ProgramMethod context) {
+      DexMethod invokedMethod = invoke.getInvokedMethod();
+      DexClassAndMethod result;
+      if (appView.appInfo().hasLiveness()) {
+        AppView<AppInfoWithLiveness> appViewWithLiveness = appView.withLiveness();
+        AppInfoWithLiveness appInfo = appViewWithLiveness.appInfo();
+        result = appInfo.lookupStaticTarget(invokedMethod, context, appViewWithLiveness);
+        assert invoke.verifyD8LookupResult(
+            result, appInfo.lookupStaticTargetOnItself(invokedMethod, context));
+      } else {
+        // Allow optimizing static library invokes in D8.
+        DexClass clazz = appView.definitionForHolder(invokedMethod);
+        if (clazz != null
+            && (clazz.isLibraryClass() || appView.libraryMethodOptimizer().isModeled(clazz.type))) {
+          result = clazz.lookupClassMethod(invokedMethod);
+        } else {
+          // In D8, we can treat invoke-static instructions as having a single target if the invoke
+          // is targeting a method in the enclosing class.
+          result = appView.appInfo().lookupStaticTargetOnItself(invokedMethod, context);
+        }
+      }
+      return DispatchTargetLookupResult.create(result, this);
+    }
+
+    private DispatchTargetLookupResult lookupSuperDispatchTarget(
+        AppView<?> appView, InvokeSuper invoke, ProgramMethod context) {
+      DexClassAndMethod result = null;
+      if (appView.appInfo().hasLiveness() && context != null) {
+        AppView<AppInfoWithLiveness> appViewWithLiveness = appView.withLiveness();
+        AppInfoWithLiveness appInfo = appViewWithLiveness.appInfo();
+        DexMethod invokedMethod = invoke.getInvokedMethod();
+        if (appInfo.isSubtype(context.getHolderType(), invokedMethod.getHolderType())) {
+          result = appInfo.lookupSuperTarget(invokedMethod, context, appViewWithLiveness);
+        }
+      }
+      return DispatchTargetLookupResult.create(result, this);
+    }
+
+    public DispatchTargetLookupResult lookupVirtualDispatchTarget(
+        AppView<?> appView,
+        InvokeMethodWithReceiver invoke,
+        DynamicType dynamicReceiverType,
+        ProgramMethod context) {
+      DexMethod invokedMethod = invoke.getInvokedMethod();
+      DexClassAndMethod result = null;
+      if (appView.appInfo().hasLiveness()) {
+        AppView<AppInfoWithLiveness> appViewWithLiveness = appView.withLiveness();
+        result =
+            appViewWithLiveness
+                .appInfo()
+                .lookupSingleVirtualTarget(
+                    appViewWithLiveness,
+                    invokedMethod,
+                    context,
+                    invoke.getInterfaceBit(),
+                    appView,
+                    dynamicReceiverType);
+      } else {
+        // In D8, allow lookupSingleTarget() to be used for finding final library methods. This is
+        // used for library modeling.
+        DexType holder = invokedMethod.getHolderType();
+        if (holder.isClassType()) {
+          DexClass clazz = appView.definitionFor(holder);
+          if (clazz != null
+              && (clazz.isLibraryClass()
+                  || appView.libraryMethodOptimizer().isModeled(clazz.getType()))) {
+            DexClassAndMethod singleTargetCandidate = clazz.lookupClassMethod(invokedMethod);
+            if (singleTargetCandidate != null
+                && (clazz.isFinal() || singleTargetCandidate.getAccessFlags().isFinal())) {
+              result = singleTargetCandidate;
+            }
+          }
+        }
+      }
+      return DispatchTargetLookupResult.create(result, this);
+    }
+
     @Override
     public DexClass getInitialResolutionHolder() {
       return initialResolutionHolder;
@@ -441,13 +576,13 @@
      * @return The actual target or {@code null} if none found.
      */
     @Override
-    public DexEncodedMethod lookupInvokeStaticTarget(
+    public DexClassAndMethod lookupInvokeStaticTarget(
         DexProgramClass context, AppView<?> appView, AppInfoWithClassHierarchy appInfo) {
       if (isAccessibleFrom(context, appView, appInfo).isFalse()) {
         return null;
       }
       if (resolvedMethod.isStatic()) {
-        return resolvedMethod;
+        return getResolutionPair();
       }
       return null;
     }
@@ -462,13 +597,13 @@
      * @return The actual target or {@code null} if none found.
      */
     @Override
-    public DexEncodedMethod lookupInvokeDirectTarget(
+    public DexClassAndMethod lookupInvokeDirectTarget(
         DexProgramClass context, AppView<?> appView, AppInfoWithClassHierarchy appInfo) {
       if (isAccessibleFrom(context, appView, appInfo).isFalse()) {
         return null;
       }
       if (resolvedMethod.isDirectMethod()) {
-        return resolvedMethod;
+        return getResolutionPair();
       }
       return null;
     }
@@ -882,23 +1017,30 @@
     private static DexClassAndMethod findWideningOverride(
         DexClassAndMethod resolvedMethod, DexClass clazz, AppInfoWithClassHierarchy appInfo) {
       // Otherwise, lookup to first override that is distinct from resolvedMethod.
-      assert resolvedMethod.getDefinition().accessFlags.isPackagePrivate();
-      while (clazz.superType != null) {
-        clazz = definitionForHelper(appInfo, clazz.superType);
+      assert resolvedMethod.getDefinition().getAccessFlags().isPackagePrivate();
+      while (clazz.hasSuperType()) {
+        clazz = definitionForHelper(appInfo, clazz.getSuperType());
         if (clazz == null) {
           return resolvedMethod;
         }
-        DexEncodedMethod otherOverride = clazz.lookupVirtualMethod(resolvedMethod.getReference());
+        DexClassAndMethod otherOverride =
+            clazz.lookupVirtualClassMethod(resolvedMethod.getReference());
         if (otherOverride != null
-            && isOverriding(resolvedMethod.getDefinition(), otherOverride)
-            && (otherOverride.accessFlags.isPublic() || otherOverride.accessFlags.isProtected())) {
-          assert resolvedMethod.getDefinition() != otherOverride;
-          return DexClassAndMethod.create(clazz, otherOverride);
+            && isOverriding(resolvedMethod, otherOverride)
+            && (otherOverride.getAccessFlags().isPublic()
+                || otherOverride.getAccessFlags().isProtected())) {
+          assert resolvedMethod.getDefinition() != otherOverride.getDefinition();
+          return otherOverride;
         }
       }
       return resolvedMethod;
     }
 
+    public static boolean isOverriding(
+        DexClassAndMethod resolvedMethod, DexClassAndMethod candidate) {
+      return isOverriding(resolvedMethod.getDefinition(), candidate.getDefinition());
+    }
+
     /**
      * Implementation of method overriding according to the jvm specification
      * https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-5.html#jvms-5.4.5
@@ -1040,13 +1182,13 @@
     }
 
     @Override
-    public DexEncodedMethod lookupInvokeStaticTarget(
+    public DexClassAndMethod lookupInvokeStaticTarget(
         DexProgramClass context, AppView<?> appView, AppInfoWithClassHierarchy appInfo) {
       return null;
     }
 
     @Override
-    public DexEncodedMethod lookupInvokeDirectTarget(
+    public DexClassAndMethod lookupInvokeDirectTarget(
         DexProgramClass context, AppView<?> appView, AppInfoWithClassHierarchy appInfo) {
       return null;
     }
@@ -1429,13 +1571,13 @@
     }
 
     @Override
-    public DexEncodedMethod lookupInvokeDirectTarget(
+    public DexClassAndMethod lookupInvokeDirectTarget(
         DexProgramClass context, AppView<?> appView, AppInfoWithClassHierarchy appInfo) {
       throw new Unreachable("Should not be called on MultipleFieldResolutionResult");
     }
 
     @Override
-    public DexEncodedMethod lookupInvokeStaticTarget(
+    public DexClassAndMethod lookupInvokeStaticTarget(
         DexProgramClass context, AppView<?> appView, AppInfoWithClassHierarchy appInfo) {
       throw new Unreachable("Should not be called on MultipleFieldResolutionResult");
     }
@@ -1687,4 +1829,106 @@
           : new NoSuchMethodResultDueToMultipleClassDefinitions(typesCausingError);
     }
   }
+
+  public static class UnknownMethodResolutionResult extends MethodResolutionResult {
+
+    private static final UnknownMethodResolutionResult INSTANCE =
+        new UnknownMethodResolutionResult();
+
+    private UnknownMethodResolutionResult() {}
+
+    static UnknownMethodResolutionResult get() {
+      return INSTANCE;
+    }
+
+    @Override
+    public OptionalBool isAccessibleFrom(
+        ProgramDefinition context, AppView<?> appView, AppInfoWithClassHierarchy appInfo) {
+      return OptionalBool.unknown();
+    }
+
+    @Override
+    public OptionalBool isAccessibleForVirtualDispatchFrom(
+        ProgramDefinition context, AppView<? extends AppInfoWithClassHierarchy> appView) {
+      return OptionalBool.unknown();
+    }
+
+    @Override
+    public boolean isVirtualTarget() {
+      throw new Unreachable();
+    }
+
+    @Override
+    public DexClassAndMethod lookupInvokeSpecialTarget(
+        DexProgramClass context, AppView<? extends AppInfoWithClassHierarchy> appView) {
+      throw new Unreachable();
+    }
+
+    @Override
+    public DexClassAndMethod lookupInvokeSuperTarget(
+        DexProgramClass context, AppView<?> appView, AppInfoWithClassHierarchy appInfo) {
+      throw new Unreachable();
+    }
+
+    @Override
+    public DexClassAndMethod lookupInvokeDirectTarget(
+        DexProgramClass context, AppView<?> appView, AppInfoWithClassHierarchy appInfo) {
+      throw new Unreachable();
+    }
+
+    @Override
+    public DexClassAndMethod lookupInvokeStaticTarget(
+        DexProgramClass context, AppView<?> appView, AppInfoWithClassHierarchy appInfo) {
+      throw new Unreachable();
+    }
+
+    @Override
+    public LookupResult lookupVirtualDispatchTargets(
+        DexProgramClass context,
+        AppView<? extends AppInfoWithClassHierarchy> appView,
+        InstantiatedSubTypeInfo instantiatedInfo,
+        PinnedPredicate pinnedPredicate) {
+      throw new Unreachable();
+    }
+
+    @Override
+    public LookupResult lookupVirtualDispatchTargets(
+        DexProgramClass context,
+        AppView<AppInfoWithLiveness> appView,
+        DexProgramClass refinedReceiverUpperBound,
+        DexProgramClass refinedReceiverLowerBound) {
+      throw new Unreachable();
+    }
+
+    @Override
+    public LookupTarget lookupVirtualDispatchTarget(
+        InstantiatedObject instance, AppInfoWithClassHierarchy appInfo) {
+      throw new Unreachable();
+    }
+
+    @Override
+    public LookupMethodTarget lookupVirtualDispatchTarget(
+        DexClass dynamicInstance, AppInfoWithClassHierarchy appInfo) {
+      throw new Unreachable();
+    }
+
+    @Override
+    public LookupTarget lookupVirtualDispatchTarget(
+        LambdaDescriptor lambdaInstance,
+        AppInfoWithClassHierarchy appInfo,
+        Consumer<DexType> typeCausingFailureConsumer,
+        Consumer<? super DexEncodedMethod> methodCausingFailureConsumer) {
+      throw new Unreachable();
+    }
+
+    @Override
+    public void visitMethodResolutionResults(
+        Consumer<? super SingleResolutionResult<? extends ProgramOrClasspathClass>>
+            programOrClasspathConsumer,
+        Consumer<? super SingleLibraryResolutionResult> libraryResultConsumer,
+        Consumer<? super ArrayCloneMethodResult> cloneResultConsumer,
+        Consumer<? super FailedResolutionResult> failedResolutionConsumer) {
+      throw new Unreachable();
+    }
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/graph/SingleDispatchTargetLookupResult.java b/src/main/java/com/android/tools/r8/graph/SingleDispatchTargetLookupResult.java
new file mode 100644
index 0000000..5cd3952
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/graph/SingleDispatchTargetLookupResult.java
@@ -0,0 +1,33 @@
+// Copyright (c) 2023, 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.graph;
+
+import com.android.tools.r8.graph.MethodResolutionResult.SingleResolutionResult;
+
+public class SingleDispatchTargetLookupResult extends DispatchTargetLookupResult {
+
+  private final DexClassAndMethod singleDispatchTarget;
+
+  public SingleDispatchTargetLookupResult(
+      DexClassAndMethod singleDispatchTarget, SingleResolutionResult<?> singleResolutionResult) {
+    super(singleResolutionResult);
+    assert singleDispatchTarget != null;
+    this.singleDispatchTarget = singleDispatchTarget;
+  }
+
+  @Override
+  public DexClassAndMethod getSingleDispatchTarget() {
+    return singleDispatchTarget;
+  }
+
+  @Override
+  public boolean isSingleResult() {
+    return true;
+  }
+
+  @Override
+  public SingleDispatchTargetLookupResult asSingleResult() {
+    return this;
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/graph/UnknownDispatchTargetLookupResult.java b/src/main/java/com/android/tools/r8/graph/UnknownDispatchTargetLookupResult.java
new file mode 100644
index 0000000..0d51cff
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/graph/UnknownDispatchTargetLookupResult.java
@@ -0,0 +1,13 @@
+// Copyright (c) 2023, 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.graph;
+
+import com.android.tools.r8.graph.MethodResolutionResult.SingleResolutionResult;
+
+public class UnknownDispatchTargetLookupResult extends DispatchTargetLookupResult {
+
+  public UnknownDispatchTargetLookupResult(SingleResolutionResult<?> singleResolutionResult) {
+    super(singleResolutionResult);
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeDirect.java b/src/main/java/com/android/tools/r8/ir/code/InvokeDirect.java
index 5bf3bd6..22cc39f 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeDirect.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeDirect.java
@@ -3,8 +3,6 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.code;
 
-import static com.android.tools.r8.graph.DexEncodedMethod.asDexClassAndMethodOrNull;
-
 import com.android.tools.r8.cf.code.CfInvoke;
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.dex.code.DexInstruction;
@@ -12,7 +10,6 @@
 import com.android.tools.r8.dex.code.DexInvokeDirectRange;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexClassAndMethod;
-import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexType;
@@ -23,7 +20,6 @@
 import com.android.tools.r8.ir.analysis.ClassInitializationAnalysis.Query;
 import com.android.tools.r8.ir.analysis.fieldvalueanalysis.AbstractFieldSet;
 import com.android.tools.r8.ir.analysis.modeling.LibraryMethodReadSetModeling;
-import com.android.tools.r8.ir.analysis.type.DynamicType;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.optimize.DeadCodeRemover.DeadInstructionResult;
@@ -137,25 +133,6 @@
   }
 
   @Override
-  public DexClassAndMethod lookupSingleTarget(
-      AppView<?> appView, ProgramMethod context, DynamicType dynamicReceiverType) {
-    DexMethod invokedMethod = getInvokedMethod();
-    DexEncodedMethod result;
-    if (appView.hasLiveness()) {
-      AppView<AppInfoWithLiveness> appViewWithLiveness = appView.withLiveness();
-      AppInfoWithLiveness appInfo = appViewWithLiveness.appInfo();
-      result = appInfo.lookupDirectTarget(invokedMethod, context, appViewWithLiveness);
-      assert verifyD8LookupResult(
-          result, appView.appInfo().lookupDirectTargetOnItself(invokedMethod, context));
-    } else {
-      // In D8, we can treat invoke-direct instructions as having a single target if the invoke is
-      // targeting a method in the enclosing class.
-      result = appView.appInfo().lookupDirectTargetOnItself(invokedMethod, context);
-    }
-    return asDexClassAndMethodOrNull(result, appView);
-  }
-
-  @Override
   public ConstraintWithTarget inliningConstraint(
       InliningConstraints inliningConstraints, ProgramMethod context) {
     return inliningConstraints.forInvokeDirect(getInvokedMethod(), context);
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeInterface.java b/src/main/java/com/android/tools/r8/ir/code/InvokeInterface.java
index 2936292..13f5ade 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeInterface.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeInterface.java
@@ -3,8 +3,6 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.code;
 
-import static com.android.tools.r8.graph.DexEncodedMethod.asDexClassAndMethodOrNull;
-
 import com.android.tools.r8.cf.code.CfInvoke;
 import com.android.tools.r8.dex.code.DexInstruction;
 import com.android.tools.r8.dex.code.DexInvokeDirect;
@@ -13,7 +11,6 @@
 import com.android.tools.r8.dex.code.DexInvokeInterfaceRange;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexClassAndMethod;
-import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.ProgramMethod;
@@ -21,7 +18,6 @@
 import com.android.tools.r8.ir.analysis.ClassInitializationAnalysis;
 import com.android.tools.r8.ir.analysis.ClassInitializationAnalysis.AnalysisAssumption;
 import com.android.tools.r8.ir.analysis.ClassInitializationAnalysis.Query;
-import com.android.tools.r8.ir.analysis.type.DynamicType;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
@@ -120,26 +116,6 @@
   }
 
   @Override
-  public DexClassAndMethod lookupSingleTarget(
-      AppView<?> appView, ProgramMethod context, DynamicType dynamicReceiverType) {
-    if (!appView.appInfo().hasLiveness()) {
-      return null;
-    }
-    AppView<AppInfoWithLiveness> appViewWithLiveness = appView.withLiveness();
-    DexEncodedMethod result =
-        appViewWithLiveness
-            .appInfo()
-            .lookupSingleVirtualTarget(
-                appViewWithLiveness,
-                getInvokedMethod(),
-                context,
-                true,
-                appView,
-                dynamicReceiverType);
-    return asDexClassAndMethodOrNull(result, appView);
-  }
-
-  @Override
   public ConstraintWithTarget inliningConstraint(
       InliningConstraints inliningConstraints, ProgramMethod context) {
     return inliningConstraints.forInvokeInterface(getInvokedMethod(), context);
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java b/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java
index 9799455..434272d 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java
@@ -11,11 +11,13 @@
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
 import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexClassAndMethod;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.DispatchTargetLookupResult;
 import com.android.tools.r8.graph.LookupResult;
 import com.android.tools.r8.graph.MethodResolutionResult;
 import com.android.tools.r8.graph.MethodResolutionResult.SingleResolutionResult;
@@ -121,11 +123,53 @@
     return appView.appInfo().resolveMethod(method, getInterfaceBit());
   }
 
-  // In subclasses, e.g., invoke-virtual or invoke-super, use a narrower receiver type by using
-  // receiver type and calling context---the holder of the method where the current invocation is.
-  // TODO(b/140204899): Refactor lookup methods to be defined in a single place.
-  public abstract DexClassAndMethod lookupSingleTarget(AppView<?> appView, ProgramMethod context);
+  public MethodResolutionResult resolveMethod(AppView<?> appView, ProgramMethod context) {
+    if (appView.hasClassHierarchy()) {
+      return resolveMethod(appView.withClassHierarchy());
+    }
+    if (method.getHolderType().isIdenticalTo(context.getHolderType())) {
+      DexClass resolutionHolder = context.getHolder();
+      DexEncodedMethod lookupResult = resolutionHolder.lookupMethod(method);
+      if (lookupResult != null) {
+        return MethodResolutionResult.createSingleResolutionResult(
+            resolutionHolder, resolutionHolder, lookupResult);
+      }
+    }
+    if (appView.libraryMethodOptimizer().isModeled(method.getHolderType())) {
+      DexClassAndMethod lookupResult = appView.definitionFor(method);
+      if (lookupResult != null) {
+        DexClass resolutionHolder = lookupResult.getHolder();
+        return MethodResolutionResult.createSingleResolutionResult(
+            resolutionHolder, resolutionHolder, lookupResult.getDefinition());
+      }
+    }
+    return MethodResolutionResult.unknown();
+  }
 
+  /**
+   * In subclasses, e.g., invoke-virtual or invoke-super, use a narrower receiver type by using
+   * receiver type and calling context---the resolutionHolder of the method where the current
+   * invocation is.
+   *
+   * @deprecated Use {@link SingleResolutionResult#lookupDispatchTarget}.
+   */
+  @Deprecated
+  public final DexClassAndMethod lookupSingleTarget(AppView<?> appView, ProgramMethod context) {
+    MethodResolutionResult resolutionResult = resolveMethod(appView, context);
+    if (resolutionResult.isSingleResolution()) {
+      DispatchTargetLookupResult lookupResult =
+          resolutionResult.asSingleResolution().lookupDispatchTarget(appView, this, context);
+      if (lookupResult.isSingleResult()) {
+        return lookupResult.asSingleResult().getSingleDispatchTarget();
+      }
+    }
+    return null;
+  }
+
+  /**
+   * @deprecated Use {@link SingleResolutionResult#lookupDispatchTarget}.
+   */
+  @Deprecated
   public final ProgramMethod lookupSingleProgramTarget(AppView<?> appView, ProgramMethod context) {
     return DexClassAndMethod.asProgramMethodOrNull(lookupSingleTarget(appView, context));
   }
@@ -269,12 +313,12 @@
   }
 
   @SuppressWarnings("ReferenceEquality")
-  boolean verifyD8LookupResult(
-      DexEncodedMethod hierarchyResult, DexEncodedMethod lookupDirectTargetOnItself) {
+  public boolean verifyD8LookupResult(
+      DexClassAndMethod hierarchyResult, DexClassAndMethod lookupDirectTargetOnItself) {
     if (lookupDirectTargetOnItself == null) {
       return true;
     }
-    assert lookupDirectTargetOnItself == hierarchyResult;
+    assert lookupDirectTargetOnItself.isStructurallyEqualTo(hierarchyResult);
     return true;
   }
 
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeMethodWithReceiver.java b/src/main/java/com/android/tools/r8/ir/code/InvokeMethodWithReceiver.java
index 2521043..edc96f6 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeMethodWithReceiver.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeMethodWithReceiver.java
@@ -16,7 +16,6 @@
 import com.android.tools.r8.ir.analysis.ClassInitializationAnalysis;
 import com.android.tools.r8.ir.analysis.VerifyTypesHelper;
 import com.android.tools.r8.ir.analysis.type.ClassTypeElement;
-import com.android.tools.r8.ir.analysis.type.DynamicType;
 import com.android.tools.r8.ir.analysis.type.TypeAnalysis;
 import com.android.tools.r8.ir.analysis.type.TypeElement;
 import com.android.tools.r8.ir.conversion.DexBuilder;
@@ -66,24 +65,6 @@
         this, singleTarget, reason, whyAreYouNotInliningReporter);
   }
 
-  @Override
-  public final DexClassAndMethod lookupSingleTarget(AppView<?> appView, ProgramMethod context) {
-    DynamicType dynamicReceiverType =
-        appView.hasLiveness()
-            ? getReceiver().getDynamicType(appView.withLiveness())
-            : DynamicType.unknown();
-    return lookupSingleTarget(appView, context, dynamicReceiverType);
-  }
-
-  public abstract DexClassAndMethod lookupSingleTarget(
-      AppView<?> appView, ProgramMethod context, DynamicType dynamicReceiverType);
-
-  public final ProgramMethod lookupSingleProgramTarget(
-      AppView<?> appView, ProgramMethod context, DynamicType dynamicReceiverType) {
-    return DexClassAndMethod.asProgramMethodOrNull(
-        lookupSingleTarget(appView, context, dynamicReceiverType));
-  }
-
   /**
    * If an invoke-virtual targets a private method in the current class overriding will not apply
    * (see JVM 11 spec on method selection 5.4.6. In previous jvm specs this was not explicitly
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokePolymorphic.java b/src/main/java/com/android/tools/r8/ir/code/InvokePolymorphic.java
index 5e80e07ef..0061bf3 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokePolymorphic.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokePolymorphic.java
@@ -9,7 +9,6 @@
 import com.android.tools.r8.dex.code.DexInvokePolymorphicRange;
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.AppView;
-import com.android.tools.r8.graph.DexClassAndMethod;
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexProto;
@@ -135,12 +134,6 @@
   }
 
   @Override
-  public DexClassAndMethod lookupSingleTarget(AppView<?> appView, ProgramMethod context) {
-    // TODO(herhut): Implement lookup target for invokePolymorphic.
-    return null;
-  }
-
-  @Override
   public ProgramMethodSet lookupProgramDispatchTargets(
       AppView<AppInfoWithLiveness> appView, ProgramMethod context) {
     // TODO(herhut): Implement lookup target for invokePolymorphic.
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeStatic.java b/src/main/java/com/android/tools/r8/ir/code/InvokeStatic.java
index e7043b0..f1d4aea 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeStatic.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeStatic.java
@@ -3,16 +3,13 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.code;
 
-import static com.android.tools.r8.graph.DexEncodedMethod.asDexClassAndMethodOrNull;
 
 import com.android.tools.r8.cf.code.CfInvoke;
 import com.android.tools.r8.dex.code.DexInstruction;
 import com.android.tools.r8.dex.code.DexInvokeStatic;
 import com.android.tools.r8.dex.code.DexInvokeStaticRange;
 import com.android.tools.r8.graph.AppView;
-import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexClassAndMethod;
-import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.MethodResolutionResult.SingleResolutionResult;
@@ -117,31 +114,6 @@
   }
 
   @Override
-  public DexClassAndMethod lookupSingleTarget(AppView<?> appView, ProgramMethod context) {
-    DexMethod invokedMethod = getInvokedMethod();
-    DexEncodedMethod result;
-    if (appView.appInfo().hasLiveness()) {
-      AppView<AppInfoWithLiveness> appViewWithLiveness = appView.withLiveness();
-      AppInfoWithLiveness appInfo = appViewWithLiveness.appInfo();
-      result = appInfo.lookupStaticTarget(invokedMethod, context, appViewWithLiveness);
-      assert verifyD8LookupResult(
-          result, appInfo.lookupStaticTargetOnItself(invokedMethod, context));
-    } else {
-      // Allow optimizing static library invokes in D8.
-      DexClass clazz = appView.definitionForHolder(getInvokedMethod());
-      if (clazz != null
-          && (clazz.isLibraryClass() || appView.libraryMethodOptimizer().isModeled(clazz.type))) {
-        result = clazz.lookupMethod(getInvokedMethod());
-      } else {
-        // In D8, we can treat invoke-static instructions as having a single target if the invoke is
-        // targeting a method in the enclosing class.
-        result = appView.appInfo().lookupStaticTargetOnItself(invokedMethod, context);
-      }
-    }
-    return asDexClassAndMethodOrNull(result, appView);
-  }
-
-  @Override
   public ConstraintWithTarget inliningConstraint(
       InliningConstraints inliningConstraints, ProgramMethod context) {
     return inliningConstraints.forInvokeStatic(getInvokedMethod(), context);
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeSuper.java b/src/main/java/com/android/tools/r8/ir/code/InvokeSuper.java
index b63fc98..6db911d 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeSuper.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeSuper.java
@@ -3,7 +3,6 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.code;
 
-
 import com.android.tools.r8.cf.code.CfInvoke;
 import com.android.tools.r8.dex.code.DexInstruction;
 import com.android.tools.r8.dex.code.DexInvokeSuper;
@@ -17,7 +16,6 @@
 import com.android.tools.r8.ir.analysis.ClassInitializationAnalysis;
 import com.android.tools.r8.ir.analysis.ClassInitializationAnalysis.AnalysisAssumption;
 import com.android.tools.r8.ir.analysis.ClassInitializationAnalysis.Query;
-import com.android.tools.r8.ir.analysis.type.DynamicType;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
@@ -109,19 +107,6 @@
   }
 
   @Override
-  public DexClassAndMethod lookupSingleTarget(
-      AppView<?> appView, ProgramMethod context, DynamicType dynamicReceiverType) {
-    if (appView.appInfo().hasLiveness() && context != null) {
-      AppView<AppInfoWithLiveness> appViewWithLiveness = appView.withLiveness();
-      AppInfoWithLiveness appInfo = appViewWithLiveness.appInfo();
-      if (appInfo.isSubtype(context.getHolderType(), getInvokedMethod().holder)) {
-        return appInfo.lookupSuperTarget(getInvokedMethod(), context, appViewWithLiveness);
-      }
-    }
-    return null;
-  }
-
-  @Override
   public ConstraintWithTarget inliningConstraint(
       InliningConstraints inliningConstraints, ProgramMethod context) {
     return inliningConstraints.forInvokeSuper(getInvokedMethod(), context);
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeVirtual.java b/src/main/java/com/android/tools/r8/ir/code/InvokeVirtual.java
index cf04e98..cde845d 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeVirtual.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeVirtual.java
@@ -3,8 +3,6 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.code;
 
-import static com.android.tools.r8.graph.DexEncodedMethod.asDexClassAndMethodOrNull;
-
 import com.android.tools.r8.cf.code.CfInvoke;
 import com.android.tools.r8.dex.code.DexInstruction;
 import com.android.tools.r8.dex.code.DexInvokeDirect;
@@ -12,9 +10,7 @@
 import com.android.tools.r8.dex.code.DexInvokeVirtual;
 import com.android.tools.r8.dex.code.DexInvokeVirtualRange;
 import com.android.tools.r8.graph.AppView;
-import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexClassAndMethod;
-import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.ProgramMethod;
@@ -22,7 +18,6 @@
 import com.android.tools.r8.ir.analysis.ClassInitializationAnalysis;
 import com.android.tools.r8.ir.analysis.ClassInitializationAnalysis.AnalysisAssumption;
 import com.android.tools.r8.ir.analysis.ClassInitializationAnalysis.Query;
-import com.android.tools.r8.ir.analysis.type.DynamicType;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
@@ -125,44 +120,6 @@
   }
 
   @Override
-  public DexClassAndMethod lookupSingleTarget(
-      AppView<?> appView, ProgramMethod context, DynamicType dynamicReceiverType) {
-    return lookupSingleTarget(appView, context, dynamicReceiverType, getInvokedMethod());
-  }
-
-  public static DexClassAndMethod lookupSingleTarget(
-      AppView<?> appView,
-      ProgramMethod context,
-      DynamicType dynamicReceiverType,
-      DexMethod method) {
-    DexEncodedMethod result = null;
-    if (appView.appInfo().hasLiveness()) {
-      AppView<AppInfoWithLiveness> appViewWithLiveness = appView.withLiveness();
-      result =
-          appViewWithLiveness
-              .appInfo()
-              .lookupSingleVirtualTarget(
-                  appViewWithLiveness, method, context, false, appView, dynamicReceiverType);
-    } else {
-      // In D8, allow lookupSingleTarget() to be used for finding final library methods. This is
-      // used for library modeling.
-      DexType holder = method.holder;
-      if (holder.isClassType()) {
-        DexClass clazz = appView.definitionFor(holder);
-        if (clazz != null
-            && (clazz.isLibraryClass() || appView.libraryMethodOptimizer().isModeled(clazz.type))) {
-          DexEncodedMethod singleTargetCandidate = clazz.lookupMethod(method);
-          if (singleTargetCandidate != null
-              && (clazz.isFinal() || singleTargetCandidate.isFinal())) {
-            result = singleTargetCandidate;
-          }
-        }
-      }
-    }
-    return asDexClassAndMethodOrNull(result, appView);
-  }
-
-  @Override
   public ConstraintWithTarget inliningConstraint(
       InliningConstraints inliningConstraints, ProgramMethod context) {
     return inliningConstraints.forInvokeVirtual(getInvokedMethod(), context);
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/LambdaDescriptor.java b/src/main/java/com/android/tools/r8/ir/desugar/LambdaDescriptor.java
index 9f4c5d0..7e9cc29 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/LambdaDescriptor.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/LambdaDescriptor.java
@@ -8,8 +8,8 @@
 import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexCallSite;
+import com.android.tools.r8.graph.DexClassAndMethod;
 import com.android.tools.r8.graph.DexDefinitionSupplier;
-import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexMethodHandle;
@@ -96,10 +96,10 @@
     this.captures = captures;
 
     this.interfaces.add(mainInterface);
-    DexEncodedMethod targetMethod =
+    DexClassAndMethod targetMethod =
         context == null ? null : lookupTargetMethod(appView, appInfo, context);
     if (targetMethod != null) {
-      targetAccessFlags = targetMethod.accessFlags.copy();
+      targetAccessFlags = targetMethod.getAccessFlags().copy();
       targetHolder = targetMethod.getHolderType();
     } else {
       targetAccessFlags = null;
@@ -116,7 +116,7 @@
     return captures.length > 0 ? captures[0] : params[0];
   }
 
-  private DexEncodedMethod lookupTargetMethod(
+  private DexClassAndMethod lookupTargetMethod(
       AppView<?> appView, AppInfoWithClassHierarchy appInfo, ProgramMethod context) {
     assert context != null;
     // Find the lambda's impl-method target.
@@ -124,10 +124,10 @@
     switch (implHandle.type) {
       case INVOKE_DIRECT:
       case INVOKE_INSTANCE: {
-          DexEncodedMethod target =
+          DexClassAndMethod target =
               appInfo
                   .resolveMethodOnLegacy(getImplReceiverType(), method, implHandle.isInterface)
-                  .getSingleTarget();
+                  .getResolutionPair();
         if (target == null) {
             target = appInfo.lookupDirectTarget(method, context, appView, appInfo);
         }
@@ -139,22 +139,22 @@
       }
 
       case INVOKE_STATIC: {
-          DexEncodedMethod target = appInfo.lookupStaticTarget(method, context, appView, appInfo);
-        assert target == null || target.accessFlags.isStatic();
+          DexClassAndMethod target = appInfo.lookupStaticTarget(method, context, appView, appInfo);
+          assert target == null || target.getAccessFlags().isStatic();
         return target;
       }
 
       case INVOKE_CONSTRUCTOR: {
-          DexEncodedMethod target = appInfo.lookupDirectTarget(method, context, appView, appInfo);
-        assert target == null || target.accessFlags.isConstructor();
+          DexClassAndMethod target = appInfo.lookupDirectTarget(method, context, appView, appInfo);
+          assert target == null || target.getAccessFlags().isConstructor();
         return target;
       }
 
       case INVOKE_INTERFACE: {
-          DexEncodedMethod target =
+          DexClassAndMethod target =
               appInfo
                   .resolveMethodOnInterfaceLegacy(getImplReceiverType(), method)
-                  .getSingleTarget();
+                  .getResolutionPair();
         assert target == null || isInstanceMethod(target);
         return target;
       }
@@ -164,24 +164,23 @@
     }
   }
 
-  private boolean isInstanceMethod(DexEncodedMethod encodedMethod) {
-    assert encodedMethod != null;
-    return !encodedMethod.accessFlags.isConstructor() && !encodedMethod.isStatic();
+  private boolean isInstanceMethod(DexClassAndMethod method) {
+    assert method != null;
+    return !method.getAccessFlags().isConstructor() && !method.getAccessFlags().isStatic();
   }
 
-  private boolean isPrivateInstanceMethod(DexEncodedMethod encodedMethod) {
-    assert encodedMethod != null;
-    return encodedMethod.isPrivateMethod() && isInstanceMethod(encodedMethod);
+  private boolean isPrivateInstanceMethod(DexClassAndMethod method) {
+    assert method != null;
+    return method.getAccessFlags().isPrivate() && isInstanceMethod(method);
   }
 
-  private boolean isPublicizedInstanceMethod(DexEncodedMethod encodedMethod) {
-    assert encodedMethod != null;
-    return encodedMethod.isPublicized() && isInstanceMethod(encodedMethod);
+  private boolean isPublicizedInstanceMethod(DexClassAndMethod method) {
+    assert method != null;
+    return method.getDefinition().isPublicized() && isInstanceMethod(method);
   }
 
-  @SuppressWarnings("ReferenceEquality")
   public final boolean verifyTargetFoundInClass(DexType type) {
-    return targetHolder == type;
+    return targetHolder.isIdenticalTo(type);
   }
 
   /** If the lambda delegates to lambda$ method. */
@@ -196,10 +195,6 @@
     }
   }
 
-  public Iterable<DexType> getReferencedBaseTypes(DexItemFactory dexItemFactory) {
-    return enforcedProto.getBaseTypes(dexItemFactory);
-  }
-
   /** Is a stateless lambda, i.e. lambda does not capture any values */
   final boolean isStateless() {
     return captures.isEmpty();
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/Devirtualizer.java b/src/main/java/com/android/tools/r8/ir/optimize/Devirtualizer.java
index f399865..a0715f7 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/Devirtualizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/Devirtualizer.java
@@ -11,6 +11,7 @@
 import com.android.tools.r8.graph.DexClassAndMethod;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.DispatchTargetLookupResult;
 import com.android.tools.r8.graph.MethodResolutionResult.SingleResolutionResult;
 import com.android.tools.r8.graph.ProgramMethod;
 import com.android.tools.r8.ir.analysis.type.TypeElement;
@@ -127,20 +128,24 @@
           // Check if the instruction can be rewritten to invoke-virtual. This allows inlining of
           // the enclosing method into contexts outside the current class.
           if (options.testing.enableInvokeSuperToInvokeVirtualRewriting) {
-            DexClassAndMethod singleTarget = invoke.lookupSingleTarget(appView, context);
-            if (singleTarget != null) {
-              DexMethod invokedMethod = invoke.getInvokedMethod();
-              DexClassAndMethod newSingleTarget =
-                  InvokeVirtual.lookupSingleTarget(
-                      appView,
-                      context,
-                      invoke.getReceiver().getDynamicType(appView),
-                      invokedMethod);
-              if (newSingleTarget != null
-                  && newSingleTarget.getReference() == singleTarget.getReference()) {
-                it.replaceCurrentInstruction(
-                    new InvokeVirtual(invokedMethod, invoke.outValue(), invoke.arguments()));
-                continue;
+            SingleResolutionResult<?> resolutionResult =
+                invoke.resolveMethod(appView).asSingleResolution();
+            if (resolutionResult != null) {
+              DispatchTargetLookupResult lookupResult =
+                  resolutionResult.lookupDispatchTarget(appView, invoke, context);
+              if (lookupResult.isSingleResult()
+                  && !lookupResult.getSingleDispatchTarget().getHolder().isInterface()) {
+                DexMethod invokedMethod = invoke.getInvokedMethod();
+                DispatchTargetLookupResult newLookupResult =
+                    resolutionResult.lookupVirtualDispatchTarget(
+                        appView, invoke, invoke.getReceiver().getDynamicType(appView), context);
+                if (lookupResult
+                    .getSingleDispatchTarget()
+                    .isStructurallyEqualTo(newLookupResult.getSingleDispatchTarget())) {
+                  it.replaceCurrentInstruction(
+                      new InvokeVirtual(invokedMethod, invoke.outValue(), invoke.arguments()));
+                  continue;
+                }
               }
             }
           }
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/InliningConstraints.java b/src/main/java/com/android/tools/r8/ir/optimize/InliningConstraints.java
index 054a256..46dd4a0 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/InliningConstraints.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/InliningConstraints.java
@@ -9,8 +9,8 @@
 import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexClass;
+import com.android.tools.r8.graph.DexClassAndMethod;
 import com.android.tools.r8.graph.DexEncodedMember;
-import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexField;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexProgramClass;
@@ -177,10 +177,14 @@
     }
     MethodResolutionResult resolutionResult =
         appView.appInfo().unsafeResolveMethodDueToDexFormatLegacy(lookup);
-    DexEncodedMethod target =
+    DexClassAndMethod target =
         singleTargetWhileVerticalClassMerging(
             resolutionResult, context, MethodResolutionResult::lookupInvokeDirectTarget);
-    return forResolvedMember(resolutionResult.getInitialResolutionHolder(), context, target);
+    if (target != null) {
+      return forResolvedMember(
+          resolutionResult.getInitialResolutionHolder(), context, target.getDefinition());
+    }
+    return ConstraintWithTarget.NEVER;
   }
 
   public ConstraintWithTarget forInvokeInterface(DexMethod method, ProgramMethod context) {
@@ -209,36 +213,39 @@
     }
     MethodResolutionResult resolutionResult =
         appView.appInfo().unsafeResolveMethodDueToDexFormatLegacy(lookup);
-    DexEncodedMethod target =
+    DexClassAndMethod target =
         singleTargetWhileVerticalClassMerging(
             resolutionResult, context, MethodResolutionResult::lookupInvokeStaticTarget);
     if (!allowStaticInterfaceMethodCalls && target != null) {
       // See b/120121170.
       DexClass methodClass = appView.definitionFor(graphLens.lookupType(target.getHolderType()));
-      if (methodClass != null && methodClass.isInterface() && target.hasCode()) {
+      if (methodClass != null && methodClass.isInterface() && target.getDefinition().hasCode()) {
         return ConstraintWithTarget.NEVER;
       }
     }
-    return forResolvedMember(resolutionResult.getInitialResolutionHolder(), context, target);
+    if (target != null) {
+      return forResolvedMember(
+          resolutionResult.getInitialResolutionHolder(), context, target.getDefinition());
+    }
+    return ConstraintWithTarget.NEVER;
   }
 
   @SuppressWarnings({"ConstantConditions", "ReferenceEquality"})
-  private DexEncodedMethod singleTargetWhileVerticalClassMerging(
+  private DexClassAndMethod singleTargetWhileVerticalClassMerging(
       MethodResolutionResult resolutionResult,
       ProgramMethod context,
       TriFunction<
               MethodResolutionResult,
               DexProgramClass,
               AppView<? extends AppInfoWithClassHierarchy>,
-              DexEncodedMethod>
+              DexClassAndMethod>
           lookup) {
     if (!resolutionResult.isSingleResolution()) {
       return null;
     }
-    DexEncodedMethod dexEncodedMethod =
-        lookup.apply(resolutionResult, context.getHolder(), appView);
-    if (!isVerticalClassMerging() || dexEncodedMethod != null) {
-      return dexEncodedMethod;
+    DexClassAndMethod lookupResult = lookup.apply(resolutionResult, context.getHolder(), appView);
+    if (!isVerticalClassMerging() || lookupResult != null) {
+      return lookupResult;
     }
     assert isVerticalClassMerging();
     assert graphLens.lookupType(context.getHolder().superType) == context.getHolderType();
@@ -247,7 +254,7 @@
     if (superContext == null) {
       return null;
     }
-    DexEncodedMethod alternativeDexEncodedMethod =
+    DexClassAndMethod alternativeDexEncodedMethod =
         lookup.apply(resolutionResult, superContext, appView);
     if (alternativeDexEncodedMethod != null
         && alternativeDexEncodedMethod.getHolderType() == superContext.type) {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/classinliner/InlineCandidateProcessor.java b/src/main/java/com/android/tools/r8/ir/optimize/classinliner/InlineCandidateProcessor.java
index c0a989b..52b3b8a 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/classinliner/InlineCandidateProcessor.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/classinliner/InlineCandidateProcessor.java
@@ -19,6 +19,7 @@
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.graph.DispatchTargetLookupResult;
 import com.android.tools.r8.graph.FieldResolutionResult;
 import com.android.tools.r8.graph.FieldResolutionResult.SingleProgramFieldResolutionResult;
 import com.android.tools.r8.graph.LibraryMethod;
@@ -491,12 +492,34 @@
             continue;
           }
 
-          DynamicType exactReceiverType =
-              DynamicType.createExact(
-                  ClassTypeElement.create(
-                      eligibleClass.getType(), Nullability.definitelyNotNull(), appView));
+          SingleResolutionResult<?> resolutionResult =
+              invoke.resolveMethod(appView).asSingleResolution();
+          if (resolutionResult == null) {
+            throw new IllegalClassInlinerStateException();
+          }
+
+          DispatchTargetLookupResult dispatchTargetLookupResult;
+          if (invoke.isInvokeDirect() || invoke.isInvokeSuper()) {
+            dispatchTargetLookupResult =
+                resolutionResult.lookupDispatchTarget(appView, invoke, method);
+          } else {
+            DynamicType exactReceiverType =
+                DynamicType.createExact(
+                    ClassTypeElement.create(
+                        eligibleClass.getType(), Nullability.definitelyNotNull(), appView));
+            dispatchTargetLookupResult =
+                resolutionResult.lookupVirtualDispatchTarget(
+                    appView, invoke, exactReceiverType, method);
+          }
+          if (!dispatchTargetLookupResult.isSingleResult()) {
+            throw new IllegalClassInlinerStateException();
+          }
+
           ProgramMethod singleTarget =
-              invoke.lookupSingleProgramTarget(appView, method, exactReceiverType);
+              dispatchTargetLookupResult
+                  .asSingleResult()
+                  .getSingleDispatchTarget()
+                  .asProgramMethod();
           if (singleTarget == null || !indirectMethodCallsOnInstance.contains(singleTarget)) {
             throw new IllegalClassInlinerStateException();
           }
diff --git a/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java b/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
index 927f14b..3bdf1c0 100644
--- a/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
+++ b/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
@@ -3,8 +3,6 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.shaking;
 
-import static com.android.tools.r8.graph.DexEncodedMethod.asProgramMethodOrNull;
-import static com.android.tools.r8.graph.DexEncodedMethod.toMethodDefinitionOrNull;
 import static com.android.tools.r8.graph.DexProgramClass.asProgramClassOrNull;
 import static com.android.tools.r8.graph.MethodResolutionResult.SingleResolutionResult.isOverriding;
 import static com.android.tools.r8.utils.collections.ThrowingSet.isThrowingSet;
@@ -18,6 +16,7 @@
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexClassAndField;
 import com.android.tools.r8.graph.DexClassAndMember;
+import com.android.tools.r8.graph.DexClassAndMethod;
 import com.android.tools.r8.graph.DexClasspathClass;
 import com.android.tools.r8.graph.DexDefinition;
 import com.android.tools.r8.graph.DexDefinitionSupplier;
@@ -30,6 +29,7 @@
 import com.android.tools.r8.graph.DexReference;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.DirectMappedDexApplication;
+import com.android.tools.r8.graph.DispatchTargetLookupResult;
 import com.android.tools.r8.graph.FieldAccessInfo;
 import com.android.tools.r8.graph.FieldAccessInfoCollection;
 import com.android.tools.r8.graph.FieldAccessInfoCollectionImpl;
@@ -46,7 +46,9 @@
 import com.android.tools.r8.graph.ProgramField;
 import com.android.tools.r8.graph.ProgramMethod;
 import com.android.tools.r8.graph.PrunedItems;
+import com.android.tools.r8.graph.SingleDispatchTargetLookupResult;
 import com.android.tools.r8.graph.SubtypingInfo;
+import com.android.tools.r8.graph.UnknownDispatchTargetLookupResult;
 import com.android.tools.r8.graph.lens.GraphLens;
 import com.android.tools.r8.graph.lens.NonIdentityGraphLens;
 import com.android.tools.r8.horizontalclassmerging.HorizontalClassMerger;
@@ -130,12 +132,14 @@
    * kept.
    */
   private Set<DexMethod> liveMethods;
+
   /**
    * Information about all fields that are accessed by the program. The information includes whether
    * a given field is read/written by the program, and it also includes all indirect accesses to
    * each field. The latter is used, for example, during member rebinding.
    */
-  private FieldAccessInfoCollectionImpl fieldAccessInfoCollection;
+  private final FieldAccessInfoCollectionImpl fieldAccessInfoCollection;
+
   /** Set of all methods referenced in invokes along with their calling contexts. */
   private final MethodAccessInfoCollection methodAccessInfoCollection;
   /** Information about instantiated classes and their allocation sites. */
@@ -1281,7 +1285,7 @@
     return prunedTypes;
   }
 
-  public DexEncodedMethod lookupSingleTarget(
+  public DexClassAndMethod lookupSingleTarget(
       AppView<AppInfoWithLiveness> appView,
       InvokeType type,
       DexMethod target,
@@ -1302,7 +1306,7 @@
       case STATIC:
         return lookupStaticTarget(target, context, appView);
       case SUPER:
-        return toMethodDefinitionOrNull(lookupSuperTarget(target, context, appView));
+        return lookupSuperTarget(target, context, appView);
       default:
         return null;
     }
@@ -1314,12 +1318,12 @@
       DexMethod target,
       ProgramMethod context,
       LibraryModeledPredicate modeledPredicate) {
-    return asProgramMethodOrNull(
-        lookupSingleTarget(appView, type, target, context, modeledPredicate), this);
+    return DexClassAndMethod.asProgramMethodOrNull(
+        lookupSingleTarget(appView, type, target, context, modeledPredicate));
   }
 
   /** For mapping invoke virtual instruction to single target method. */
-  public DexEncodedMethod lookupSingleVirtualTarget(
+  public DexClassAndMethod lookupSingleVirtualTarget(
       AppView<AppInfoWithLiveness> appView,
       DexMethod method,
       ProgramMethod context,
@@ -1329,7 +1333,7 @@
   }
 
   /** For mapping invoke virtual instruction to single target method. */
-  public DexEncodedMethod lookupSingleVirtualTarget(
+  public DexClassAndMethod lookupSingleVirtualTarget(
       AppView<AppInfoWithLiveness> appView,
       DexMethod method,
       ProgramMethod context,
@@ -1341,7 +1345,7 @@
   }
 
   @SuppressWarnings("ReferenceEquality")
-  public DexEncodedMethod lookupSingleVirtualTarget(
+  public DexClassAndMethod lookupSingleVirtualTarget(
       AppView<AppInfoWithLiveness> appView,
       DexMethod method,
       ProgramMethod context,
@@ -1370,11 +1374,13 @@
       // The refined receiver is not defined in the program and we cannot determine the target.
       return null;
     }
-    if (!dynamicReceiverType.hasDynamicLowerBoundType()
-        && singleTargetLookupCache.hasCachedItem(refinedReceiverType, method)) {
-      DexEncodedMethod cachedItem =
-          singleTargetLookupCache.getCachedItem(refinedReceiverType, method);
-      return cachedItem;
+    if (!dynamicReceiverType.hasDynamicLowerBoundType()) {
+      if (singleTargetLookupCache.hasPositiveCacheHit(refinedReceiverType, method)) {
+        return singleTargetLookupCache.getPositiveCacheHit(refinedReceiverType, method);
+      }
+      if (singleTargetLookupCache.hasNegativeCacheHit(refinedReceiverType, method)) {
+        return null;
+      }
     }
     SingleResolutionResult<?> resolution =
         resolveMethodOnLegacy(initialResolutionHolder, method).asSingleResolution();
@@ -1383,15 +1389,16 @@
       return null;
     }
     // If the method is modeled, return the resolution.
-    DexEncodedMethod resolvedMethod = resolution.getResolvedMethod();
-    if (modeledPredicate.isModeled(resolution.getResolvedHolder().type)) {
+    DexClassAndMethod resolvedMethod = resolution.getResolutionPair();
+    if (modeledPredicate.isModeled(resolution.getResolvedHolder().getType())) {
       if (resolution.getResolvedHolder().isFinal()
-          || (resolvedMethod.isFinal() && resolvedMethod.accessFlags.isPublic())) {
+          || (resolvedMethod.getAccessFlags().isFinal()
+              && resolvedMethod.getAccessFlags().isPublic())) {
         singleTargetLookupCache.addToCache(refinedReceiverType, method, resolvedMethod);
         return resolvedMethod;
       }
     }
-    DexEncodedMethod exactTarget =
+    DispatchTargetLookupResult exactTarget =
         getMethodTargetFromExactRuntimeInformation(
             refinedReceiverType,
             dynamicReceiverType.getDynamicLowerBoundType(),
@@ -1400,11 +1407,13 @@
     if (exactTarget != null) {
       // We are not caching single targets here because the cache does not include the
       // lower bound dimension.
-      return exactTarget == DexEncodedMethod.SENTINEL ? null : exactTarget;
+      return exactTarget.isSingleResult()
+          ? exactTarget.asSingleResult().getSingleDispatchTarget()
+          : null;
     }
     if (refinedReceiverClass.isNotProgramClass()) {
       // The refined receiver is not defined in the program and we cannot determine the target.
-      singleTargetLookupCache.addToCache(refinedReceiverType, method, null);
+      singleTargetLookupCache.addNoSingleTargetToCache(refinedReceiverType, method);
       return null;
     }
     DexClass resolvedHolder = resolution.getResolvedHolder();
@@ -1413,10 +1422,10 @@
         && resolvedHolder.isProgramClass()
         && objectAllocationInfoCollection.isImmediateInterfaceOfInstantiatedLambda(
             resolvedHolder.asProgramClass())) {
-      singleTargetLookupCache.addToCache(refinedReceiverType, method, null);
+      singleTargetLookupCache.addNoSingleTargetToCache(refinedReceiverType, method);
       return null;
     }
-    DexEncodedMethod singleMethodTarget = null;
+    DexClassAndMethod singleMethodTarget = null;
     DexProgramClass refinedLowerBound = null;
     if (dynamicReceiverType.hasDynamicLowerBoundType()) {
       DexClass refinedLowerBoundClass =
@@ -1440,7 +1449,7 @@
     if (lookupResult != null && !lookupResult.isIncomplete()) {
       LookupTarget singleTarget = lookupResult.getSingleLookupTarget();
       if (singleTarget != null && singleTarget.isMethodTarget()) {
-        singleMethodTarget = singleTarget.asMethodTarget().getDefinition();
+        singleMethodTarget = singleTarget.asMethodTarget().getTarget();
       }
     }
     if (!dynamicReceiverType.hasDynamicLowerBoundType()) {
@@ -1450,7 +1459,7 @@
   }
 
   @SuppressWarnings("ReferenceEquality")
-  private DexEncodedMethod getMethodTargetFromExactRuntimeInformation(
+  private DispatchTargetLookupResult getMethodTargetFromExactRuntimeInformation(
       DexType refinedReceiverType,
       ClassTypeElement receiverLowerBoundType,
       SingleResolutionResult<?> resolution,
@@ -1469,21 +1478,21 @@
                     .getMethodInfo(methodTarget.getTarget().asProgramMethod())
                     .isOptimizationAllowed(options()))) {
           // TODO(b/150640456): We should maybe only consider program methods.
-          return DexEncodedMethod.SENTINEL;
+          return new UnknownDispatchTargetLookupResult(resolution);
         }
-        return methodTarget.getDefinition();
+        return new SingleDispatchTargetLookupResult(methodTarget.getTarget(), resolution);
       } else {
         // TODO(b/150640456): We should maybe only consider program methods.
         // If we resolved to a method on the refined receiver in the library, then we report the
         // method as a single target as well. This is a bit iffy since the library could change
         // implementation, but we use this for library modelling.
-        DexEncodedMethod resolvedMethod = resolution.getResolvedMethod();
-        DexEncodedMethod targetOnReceiver =
-            refinedReceiverClass.lookupVirtualMethod(resolvedMethod.getReference());
+        DexClassAndMethod resolvedMethod = resolution.getResolutionPair();
+        DexClassAndMethod targetOnReceiver =
+            refinedReceiverClass.lookupVirtualClassMethod(resolvedMethod.getReference());
         if (targetOnReceiver != null && isOverriding(resolvedMethod, targetOnReceiver)) {
-          return targetOnReceiver;
+          return new SingleDispatchTargetLookupResult(targetOnReceiver, resolution);
         }
-        return DexEncodedMethod.SENTINEL;
+        return new UnknownDispatchTargetLookupResult(resolution);
       }
     }
     return null;
diff --git a/src/main/java/com/android/tools/r8/shaking/SingleTargetLookupCache.java b/src/main/java/com/android/tools/r8/shaking/SingleTargetLookupCache.java
index 392ae35..0c576e0 100644
--- a/src/main/java/com/android/tools/r8/shaking/SingleTargetLookupCache.java
+++ b/src/main/java/com/android/tools/r8/shaking/SingleTargetLookupCache.java
@@ -4,32 +4,51 @@
 
 package com.android.tools.r8.shaking;
 
+import static com.android.tools.r8.utils.MapUtils.ignoreKey;
+
+import com.android.tools.r8.graph.DexClassAndMethod;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.utils.ObjectUtils;
 import com.android.tools.r8.utils.TraversalContinuation;
 import com.google.common.collect.Sets;
+import java.util.Collections;
 import java.util.Map;
 import java.util.Set;
 import java.util.concurrent.ConcurrentHashMap;
 
 public class SingleTargetLookupCache {
 
-  private Map<DexType, Map<DexMethod, DexEncodedMethod>> cache = new ConcurrentHashMap<>();
+  private final Map<DexType, Map<DexMethod, DexClassAndMethod>> positiveCache =
+      new ConcurrentHashMap<>();
+  private final Map<DexType, Set<DexMethod>> negativeCache = new ConcurrentHashMap<>();
 
-  @SuppressWarnings("ReferenceEquality")
-  public void addToCache(DexType refinedReceiverType, DexMethod method, DexEncodedMethod target) {
-    assert target != DexEncodedMethod.SENTINEL;
-    Map<DexMethod, DexEncodedMethod> methodCache =
-        cache.computeIfAbsent(refinedReceiverType, ignored -> new ConcurrentHashMap<>());
-    target = target == null ? DexEncodedMethod.SENTINEL : target;
-    assert methodCache.getOrDefault(method, target) == target;
-    methodCache.putIfAbsent(method, target);
+  public void addNoSingleTargetToCache(DexType refinedReceiverType, DexMethod method) {
+    assert !hasPositiveCacheHit(refinedReceiverType, method);
+    negativeCache
+        .computeIfAbsent(refinedReceiverType, ignoreKey(ConcurrentHashMap::newKeySet))
+        .add(method);
+  }
+
+  public void addToCache(DexType refinedReceiverType, DexMethod method, DexClassAndMethod target) {
+    if (target == null) {
+      addNoSingleTargetToCache(refinedReceiverType, method);
+      return;
+    }
+    assert !ObjectUtils.identical(target.getDefinition(), DexEncodedMethod.SENTINEL);
+    assert !hasNegativeCacheHit(refinedReceiverType, method);
+    assert !hasPositiveCacheHit(refinedReceiverType, method)
+        || getPositiveCacheHit(refinedReceiverType, method).isStructurallyEqualTo(target);
+    positiveCache
+        .computeIfAbsent(refinedReceiverType, ignoreKey(ConcurrentHashMap::new))
+        .put(method, target);
   }
 
   public void removeInstantiatedType(DexType instantiatedType, AppInfoWithLiveness appInfo) {
     // Remove all types in the instantiated hierarchy related to this type.
-    cache.remove(instantiatedType);
+    positiveCache.remove(instantiatedType);
+    negativeCache.remove(instantiatedType);
     Set<DexType> seen = Sets.newIdentityHashSet();
     appInfo.forEachInstantiatedSubType(
         instantiatedType,
@@ -38,7 +57,8 @@
                 instance,
                 (superType, subclass, ignore) -> {
                   if (seen.add(superType)) {
-                    cache.remove(superType);
+                    positiveCache.remove(superType);
+                    negativeCache.remove(superType);
                     return TraversalContinuation.doContinue();
                   } else {
                     return TraversalContinuation.doBreak();
@@ -49,25 +69,15 @@
         });
   }
 
-  @SuppressWarnings("ReferenceEquality")
-  public DexEncodedMethod getCachedItem(DexType receiverType, DexMethod method) {
-    Map<DexMethod, DexEncodedMethod> cachedMethods = cache.get(receiverType);
-    if (cachedMethods == null) {
-      return null;
-    }
-    DexEncodedMethod target = cachedMethods.get(method);
-    return target == DexEncodedMethod.SENTINEL ? null : target;
+  public boolean hasPositiveCacheHit(DexType receiverType, DexMethod method) {
+    return positiveCache.getOrDefault(receiverType, Collections.emptyMap()).containsKey(method);
   }
 
-  public boolean hasCachedItem(DexType receiverType, DexMethod method) {
-    Map<DexMethod, DexEncodedMethod> cachedMethods = cache.get(receiverType);
-    if (cachedMethods == null) {
-      return false;
-    }
-    return cachedMethods.containsKey(method);
+  public DexClassAndMethod getPositiveCacheHit(DexType receiverType, DexMethod method) {
+    return positiveCache.getOrDefault(receiverType, Collections.emptyMap()).get(method);
   }
 
-  public void clear() {
-    cache = new ConcurrentHashMap<>();
+  public boolean hasNegativeCacheHit(DexType receiverType, DexMethod method) {
+    return negativeCache.getOrDefault(receiverType, Collections.emptySet()).contains(method);
   }
 }
diff --git a/src/main/java/com/android/tools/r8/utils/ObjectUtils.java b/src/main/java/com/android/tools/r8/utils/ObjectUtils.java
index 216f19b..9dfd1e0 100644
--- a/src/main/java/com/android/tools/r8/utils/ObjectUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/ObjectUtils.java
@@ -16,6 +16,11 @@
     return orElse;
   }
 
+  @SuppressWarnings("ReferenceEquality")
+  public static boolean identical(Object a, Object b) {
+    return a == b;
+  }
+
   public static <S, T> T mapNotNull(S object, Function<? super S, ? extends T> fn) {
     if (object != null) {
       return fn.apply(object);
diff --git a/src/test/java/com/android/tools/r8/resolution/SingleTargetLookupTest.java b/src/test/java/com/android/tools/r8/resolution/SingleTargetLookupTest.java
index e010bfe..d32849b 100644
--- a/src/test/java/com/android/tools/r8/resolution/SingleTargetLookupTest.java
+++ b/src/test/java/com/android/tools/r8/resolution/SingleTargetLookupTest.java
@@ -11,7 +11,7 @@
 import com.android.tools.r8.TestAppViewBuilder;
 import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.AppView;
-import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexClassAndMethod;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.LookupResult;
@@ -195,7 +195,7 @@
     ProgramMethod context =
         appInfo.definitionForProgramType(reference.holder).getProgramDefaultInitializer();
     Assert.assertNotNull(appInfo.resolveMethodOnClassHolderLegacy(reference).getSingleTarget());
-    DexEncodedMethod singleVirtualTarget =
+    DexClassAndMethod singleVirtualTarget =
         appInfo.lookupSingleVirtualTarget(appView, reference, context, false);
     if (singleTargetHolderOrNull == null) {
       Assert.assertNull(singleVirtualTarget);
diff --git a/src/test/java/com/android/tools/r8/resolution/VirtualOverrideOfStaticMethodWithVirtualParentInterfaceTest.java b/src/test/java/com/android/tools/r8/resolution/VirtualOverrideOfStaticMethodWithVirtualParentInterfaceTest.java
index 244e9ea..e15e664 100644
--- a/src/test/java/com/android/tools/r8/resolution/VirtualOverrideOfStaticMethodWithVirtualParentInterfaceTest.java
+++ b/src/test/java/com/android/tools/r8/resolution/VirtualOverrideOfStaticMethodWithVirtualParentInterfaceTest.java
@@ -11,6 +11,7 @@
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestParametersCollection;
 import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexClassAndMethod;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexProgramClass;
@@ -132,7 +133,7 @@
     DexEncodedMethod resolved = resolutionResult.getSingleTarget();
     assertEquals(methodOnBReference, resolved.getReference());
     assertFalse(resolutionResult.isVirtualTarget());
-    DexEncodedMethod singleVirtualTarget =
+    DexClassAndMethod singleVirtualTarget =
         appInfo.lookupSingleVirtualTarget(appView, methodOnBReference, methodOnB, false);
     Assert.assertNull(singleVirtualTarget);
   }
diff --git a/src/test/java/com/android/tools/r8/resolution/VirtualOverrideOfStaticMethodWithVirtualParentTest.java b/src/test/java/com/android/tools/r8/resolution/VirtualOverrideOfStaticMethodWithVirtualParentTest.java
index b456774..d166b97 100644
--- a/src/test/java/com/android/tools/r8/resolution/VirtualOverrideOfStaticMethodWithVirtualParentTest.java
+++ b/src/test/java/com/android/tools/r8/resolution/VirtualOverrideOfStaticMethodWithVirtualParentTest.java
@@ -14,6 +14,7 @@
 import com.android.tools.r8.TestRunResult;
 import com.android.tools.r8.ToolHelper.DexVm.Version;
 import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexClassAndMethod;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexProgramClass;
@@ -179,7 +180,7 @@
     DexEncodedMethod resolved = resolutionResult.getSingleTarget();
     assertEquals(methodOnA, resolved.getReference());
     assertFalse(resolutionResult.isVirtualTarget());
-    DexEncodedMethod singleVirtualTarget =
+    DexClassAndMethod singleVirtualTarget =
         appInfo.lookupSingleVirtualTarget(
             appView, methodOnB, bClass.getProgramDefaultInitializer(), false);
     Assert.assertNull(singleVirtualTarget);
diff --git a/src/test/java/com/android/tools/r8/resolution/singletarget/InstantiatedLowerBoundTest.java b/src/test/java/com/android/tools/r8/resolution/singletarget/InstantiatedLowerBoundTest.java
index 788e55b..7b9b80c 100644
--- a/src/test/java/com/android/tools/r8/resolution/singletarget/InstantiatedLowerBoundTest.java
+++ b/src/test/java/com/android/tools/r8/resolution/singletarget/InstantiatedLowerBoundTest.java
@@ -14,7 +14,7 @@
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestParametersCollection;
 import com.android.tools.r8.graph.AppView;
-import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexClassAndMethod;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexType;
@@ -64,7 +64,7 @@
     DexMethod fooA = buildNullaryVoidMethod(A.class, "foo", appInfo.dexItemFactory());
     TypeElement latticeA = typeA.toTypeElement(appView);
     ClassTypeElement latticeB = typeB.toTypeElement(appView).asClassType();
-    DexEncodedMethod singleTarget =
+    DexClassAndMethod singleTarget =
         appInfo.lookupSingleVirtualTarget(
             appView,
             fooA,
@@ -97,7 +97,7 @@
     DexMethod fooA = buildNullaryVoidMethod(A.class, "foo", appInfo.dexItemFactory());
     TypeElement latticeA = typeA.toTypeElement(appView);
     ClassTypeElement latticeB = typeB.toTypeElement(appView).asClassType();
-    DexEncodedMethod singleTarget =
+    DexClassAndMethod singleTarget =
         appInfo.lookupSingleVirtualTarget(
             appView,
             fooA,
@@ -153,7 +153,7 @@
     assertEquals(expected, actual);
     TypeElement latticeA = typeA.toTypeElement(appView);
     ClassTypeElement latticeC = typeC.toTypeElement(appView).asClassType();
-    DexEncodedMethod singleTarget =
+    DexClassAndMethod singleTarget =
         appInfo.lookupSingleVirtualTarget(
             appView,
             fooA,
diff --git a/src/test/java/com/android/tools/r8/resolution/singletarget/SuccessAndInvalidLookupTest.java b/src/test/java/com/android/tools/r8/resolution/singletarget/SuccessAndInvalidLookupTest.java
index ca2dee8..ec3815d 100644
--- a/src/test/java/com/android/tools/r8/resolution/singletarget/SuccessAndInvalidLookupTest.java
+++ b/src/test/java/com/android/tools/r8/resolution/singletarget/SuccessAndInvalidLookupTest.java
@@ -13,7 +13,7 @@
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestParametersCollection;
 import com.android.tools.r8.graph.AppView;
-import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexClassAndMethod;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.ProgramMethod;
@@ -58,12 +58,12 @@
     DynamicType dynamicTypeA =
         DynamicTypeWithUpperBound.create(appView, typeA.toTypeElement(appView));
     DexMethod fooA = buildNullaryVoidMethod(A.class, "foo", appInfo.dexItemFactory());
-    DexEncodedMethod singleTarget =
+    DexClassAndMethod singleTarget =
         appInfo.lookupSingleVirtualTarget(
             appView, fooA, mainMethod, false, t -> false, dynamicTypeA);
     assertNotNull(singleTarget);
     assertEquals(fooA, singleTarget.getReference());
-    DexEncodedMethod invalidSingleTarget =
+    DexClassAndMethod invalidSingleTarget =
         appInfo.lookupSingleVirtualTarget(
             appView, fooA, mainMethod, true, t -> false, dynamicTypeA);
     assertNull(invalidSingleTarget);
@@ -91,12 +91,12 @@
         DynamicTypeWithUpperBound.create(appView, typeA.toTypeElement(appView));
     DexMethod fooI = buildNullaryVoidMethod(I.class, "foo", appInfo.dexItemFactory());
     DexMethod fooA = buildNullaryVoidMethod(A.class, "foo", appInfo.dexItemFactory());
-    DexEncodedMethod singleTarget =
+    DexClassAndMethod singleTarget =
         appInfo.lookupSingleVirtualTarget(
             appView, fooI, mainMethod, true, t -> false, dynamicTypeA);
     assertNotNull(singleTarget);
     assertEquals(fooA, singleTarget.getReference());
-    DexEncodedMethod invalidSingleTarget =
+    DexClassAndMethod invalidSingleTarget =
         appInfo.lookupSingleVirtualTarget(
             appView, fooI, mainMethod, false, t -> false, dynamicTypeA);
     assertNull(invalidSingleTarget);