diff --git a/src/main/java/com/android/tools/r8/graph/DexMethod.java b/src/main/java/com/android/tools/r8/graph/DexMethod.java
index b15ee67..80605e5 100644
--- a/src/main/java/com/android/tools/r8/graph/DexMethod.java
+++ b/src/main/java/com/android/tools/r8/graph/DexMethod.java
@@ -6,17 +6,12 @@
 import com.android.tools.r8.dex.IndexedItemCollection;
 import com.android.tools.r8.errors.CompilationError;
 import com.android.tools.r8.naming.NamingLens;
-import com.google.common.collect.Maps;
-import java.util.Map;
 
 public class DexMethod extends DexMember<DexEncodedMethod, DexMethod> {
 
   public final DexProto proto;
   public final DexString name;
 
-  // Caches used during processing.
-  private Map<DexType, DexEncodedMethod> singleTargetCache;
-
   DexMethod(DexType holder, DexProto proto, DexString name, boolean skipNameValidationForTesting) {
     super(holder);
     this.proto = proto;
@@ -174,21 +169,4 @@
     return name == dexItemFactory.deserializeLambdaMethodName
         && proto == dexItemFactory.deserializeLambdaMethodProto;
   }
-
-  synchronized public void setSingleVirtualMethodCache(
-      DexType receiverType, DexEncodedMethod method) {
-    if (singleTargetCache == null) {
-      singleTargetCache = Maps.newIdentityHashMap();
-    }
-    singleTargetCache.put(receiverType, method);
-  }
-
-  synchronized public boolean isSingleVirtualMethodCached(DexType receiverType) {
-    return singleTargetCache != null && singleTargetCache.containsKey(receiverType);
-  }
-
-  synchronized public DexEncodedMethod getSingleVirtualMethodCache(DexType receiverType) {
-    assert isSingleVirtualMethodCached(receiverType);
-    return singleTargetCache.get(receiverType);
-  }
 }
diff --git a/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java b/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java
index b319c6d..4816759 100644
--- a/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java
+++ b/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java
@@ -142,9 +142,7 @@
       lenseBuilder.add(encodedMethod.method);
       accessFlags.promoteToFinal();
       accessFlags.promoteToPublic();
-      // Although the current method became public, it surely has the single virtual target.
-      encodedMethod.method.setSingleVirtualMethodCache(
-          encodedMethod.method.holder, encodedMethod);
+      // The method just became public and is therefore not a library override.
       encodedMethod.setLibraryMethodOverride(OptionalBool.FALSE);
       return true;
     }
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 eef80a6..ed4c3e3 100644
--- a/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
+++ b/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
@@ -186,6 +186,9 @@
 
   final Set<DexType> instantiatedLambdas;
 
+  /* A cache to improve the lookup performance of lookupSingleVirtualTarget */
+  private final SingleTargetLookupCache singleTargetLookupCache = new SingleTargetLookupCache();
+
   // TODO(zerny): Clean up the constructors so we have just one.
   AppInfoWithLiveness(
       DirectMappedDexApplication application,
@@ -732,6 +735,10 @@
     return objectAllocationInfoCollection;
   }
 
+  void removeFromSingleTargetLookupCache(DexClass clazz) {
+    singleTargetLookupCache.removeInstantiatedType(clazz.type, this);
+  }
+
   private boolean assertNoItemRemoved(Collection<DexReference> items, Collection<DexType> types) {
     Set<DexType> typeSet = ImmutableSet.copyOf(types);
     for (DexReference item : items) {
@@ -1113,31 +1120,6 @@
     }
   }
 
-  private DexEncodedMethod validateSingleVirtualTarget(
-      DexEncodedMethod singleTarget, DexEncodedMethod resolutionResult) {
-    assert resolutionResult.isVirtualMethod();
-
-    if (singleTarget == null || singleTarget == DexEncodedMethod.SENTINEL) {
-      return null;
-    }
-
-    // Art978_virtual_interfaceTest correctly expects an IncompatibleClassChangeError exception
-    // at runtime.
-    if (isInvalidSingleVirtualTarget(singleTarget, resolutionResult)) {
-      return null;
-    }
-
-    return singleTarget;
-  }
-
-  private boolean isInvalidSingleVirtualTarget(
-      DexEncodedMethod singleTarget, DexEncodedMethod resolutionResult) {
-    assert resolutionResult.isVirtualMethod();
-    // Art978_virtual_interfaceTest correctly expects an IncompatibleClassChangeError exception
-    // at runtime.
-    return !singleTarget.accessFlags.isAtLeastAsVisibleAs(resolutionResult.accessFlags);
-  }
-
   /** For mapping invoke virtual instruction to single target method. */
   public DexEncodedMethod lookupSingleVirtualTarget(
       DexMethod method, DexType invocationContext, boolean isInterface) {
@@ -1175,25 +1157,87 @@
       // (it is either primitive or array).
       return null;
     }
+    DexClass initialResolutionHolder = definitionFor(method.holder);
+    if (initialResolutionHolder == null || initialResolutionHolder.isInterface() != isInterface) {
+      return null;
+    }
     DexClass refinedReceiverClass = definitionFor(refinedReceiverType);
     if (refinedReceiverClass == null) {
       // The refined receiver is not defined in the program and we cannot determine the target.
       return null;
     }
+    if (receiverLowerBoundType == null
+        && singleTargetLookupCache.hasCachedItem(refinedReceiverType, method)) {
+      DexEncodedMethod cachedItem =
+          singleTargetLookupCache.getCachedItem(refinedReceiverType, method);
+      return cachedItem;
+    }
     SingleResolutionResult resolution =
-        resolveMethod(method.holder, method, isInterface).asSingleResolution();
+        resolveMethod(initialResolutionHolder, method).asSingleResolution();
     if (resolution == null
         || !resolution.isAccessibleForVirtualDispatchFrom(invocationClass, this)) {
       return null;
     }
     // If the method is modeled, return the resolution.
+    DexEncodedMethod resolvedMethod = resolution.getResolvedMethod();
     if (modeledPredicate.isModeled(resolution.getResolvedHolder().type)) {
       if (resolution.getResolvedHolder().isFinal()
-          || (resolution.getResolvedMethod().isFinal()
-              && resolution.getResolvedMethod().accessFlags.isPublic())) {
-        return resolution.getResolvedMethod();
+          || (resolvedMethod.isFinal() && resolvedMethod.accessFlags.isPublic())) {
+        singleTargetLookupCache.addToCache(refinedReceiverType, method, resolvedMethod);
+        return resolvedMethod;
       }
     }
+    DexEncodedMethod exactTarget =
+        getMethodTargetFromExactRuntimeInformation(
+            refinedReceiverType, receiverLowerBoundType, resolution, refinedReceiverClass);
+    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;
+    }
+    if (refinedReceiverClass.isNotProgramClass()) {
+      // The refined receiver is not defined in the program and we cannot determine the target.
+      singleTargetLookupCache.addToCache(refinedReceiverType, method, null);
+      return null;
+    }
+    DexClass resolvedHolder = resolution.getResolvedHolder();
+    // TODO(b/148769279): Disable lookup single target on lambda's for now.
+    if (resolvedHolder.isInterface()
+        && resolvedHolder.isProgramClass()
+        && hasAnyInstantiatedLambdas(resolvedHolder.asProgramClass())) {
+      singleTargetLookupCache.addToCache(refinedReceiverType, method, null);
+      return null;
+    }
+    DexEncodedMethod singleMethodTarget = null;
+    DexProgramClass refinedLowerBound = null;
+    if (receiverLowerBoundType != null) {
+      DexClass refinedLowerBoundClass = definitionFor(receiverLowerBoundType.getClassType());
+      if (refinedLowerBoundClass != null) {
+        refinedLowerBound = refinedLowerBoundClass.asProgramClass();
+      }
+    }
+    LookupResultSuccess lookupResult =
+        resolution
+            .lookupVirtualDispatchTargets(
+                invocationClass, this, refinedReceiverClass.asProgramClass(), refinedLowerBound)
+            .asLookupResultSuccess();
+    if (lookupResult != null && !lookupResult.isIncomplete()) {
+      LookupTarget singleTarget = lookupResult.getSingleLookupTarget();
+      if (singleTarget != null && singleTarget.isMethodTarget()) {
+        singleMethodTarget = singleTarget.asMethodTarget().getMethod();
+      }
+    }
+    if (receiverLowerBoundType == null) {
+      singleTargetLookupCache.addToCache(refinedReceiverType, method, singleMethodTarget);
+    }
+    return singleMethodTarget;
+  }
+
+  private DexEncodedMethod getMethodTargetFromExactRuntimeInformation(
+      DexType refinedReceiverType,
+      ClassTypeLatticeElement receiverLowerBoundType,
+      SingleResolutionResult resolution,
+      DexClass refinedReceiverClass) {
     // If the lower-bound on the receiver type is the same as the upper-bound, then we have exact
     // runtime type information. In this case, the invoke will dispatch to the resolution result
     // from the runtime type of the receiver.
@@ -1204,7 +1248,7 @@
             resolution.lookupVirtualDispatchTarget(refinedReceiverClass.asProgramClass(), this);
         if (clazzAndMethod == null || isPinned(clazzAndMethod.getMethod().method)) {
           // TODO(b/150640456): We should maybe only consider program methods.
-          return null;
+          return DexEncodedMethod.SENTINEL;
         }
         return clazzAndMethod.getMethod();
       } else {
@@ -1212,56 +1256,16 @@
         // 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 targetOnReceiver = refinedReceiverClass.lookupVirtualMethod(method);
-        if (targetOnReceiver != null
-            && isOverriding(resolution.getResolvedMethod(), targetOnReceiver)) {
+        DexEncodedMethod resolvedMethod = resolution.getResolvedMethod();
+        DexEncodedMethod targetOnReceiver =
+            refinedReceiverClass.lookupVirtualMethod(resolvedMethod.method);
+        if (targetOnReceiver != null && isOverriding(resolvedMethod, targetOnReceiver)) {
           return targetOnReceiver;
         }
-        return null;
+        return DexEncodedMethod.SENTINEL;
       }
     }
-    if (refinedReceiverClass.isNotProgramClass()) {
-      // The refined receiver is not defined in the program and we cannot determine the target.
-      return null;
-    }
-    DexClass resolvedHolder = resolution.getResolvedHolder();
-    // TODO(b/148769279): Disable lookup single target on lambda's for now.
-    if (resolvedHolder.isInterface()
-        && resolvedHolder.isProgramClass()
-        && hasAnyInstantiatedLambdas(resolvedHolder.asProgramClass())) {
-      return null;
-    }
-
-    if (method.isSingleVirtualMethodCached(refinedReceiverType)) {
-      return method.getSingleVirtualMethodCache(refinedReceiverType);
-    }
-
-    DexProgramClass refinedLowerBound = null;
-    if (receiverLowerBoundType != null) {
-      assert receiverLowerBoundType.isClassType();
-      DexClass refinedLowerBoundClass = definitionFor(receiverLowerBoundType.getClassType());
-      if (refinedLowerBoundClass != null) {
-        refinedLowerBound = refinedLowerBoundClass.asProgramClass();
-      }
-    }
-
-    LookupResultSuccess lookupResult =
-        resolution
-            .lookupVirtualDispatchTargets(
-                invocationClass, this, refinedReceiverClass.asProgramClass(), refinedLowerBound)
-            .asLookupResultSuccess();
-
-    if (lookupResult == null || lookupResult.isIncomplete()) {
-      return null;
-    }
-
-    LookupTarget singleTarget = lookupResult.getSingleLookupTarget();
-    DexEncodedMethod singleMethodTarget = null;
-    if (singleTarget != null && singleTarget.isMethodTarget()) {
-      singleMethodTarget = singleTarget.asMethodTarget().getMethod();
-    }
-    method.setSingleVirtualMethodCache(refinedReceiverType, singleMethodTarget);
-    return singleMethodTarget;
+    return null;
   }
 
   public AppInfoWithLiveness withSwitchMaps(Map<DexField, Int2ReferenceMap<DexField>> switchMaps) {
@@ -1276,12 +1280,6 @@
     return new AppInfoWithLiveness(this, switchMaps, enumValueInfoMaps);
   }
 
-  public void forEachLiveProgramClass(Consumer<DexProgramClass> fn) {
-    for (DexType type : liveTypes) {
-      fn.accept(definitionFor(type).asProgramClass());
-    }
-  }
-
   /**
    * Visit all class definitions of classpath classes that are referenced in the compilation unit.
    *
diff --git a/src/main/java/com/android/tools/r8/shaking/AppInfoWithLivenessModifier.java b/src/main/java/com/android/tools/r8/shaking/AppInfoWithLivenessModifier.java
index 75c27fd..99f2d84 100644
--- a/src/main/java/com/android/tools/r8/shaking/AppInfoWithLivenessModifier.java
+++ b/src/main/java/com/android/tools/r8/shaking/AppInfoWithLivenessModifier.java
@@ -36,8 +36,11 @@
     // Instantiated classes.
     ObjectAllocationInfoCollectionImpl objectAllocationInfoCollection =
         appInfo.getMutableObjectAllocationInfoCollection();
-    noLongerInstantiatedClasses.forEach(objectAllocationInfoCollection::markNoLongerInstantiated);
-
+    noLongerInstantiatedClasses.forEach(
+        clazz -> {
+          objectAllocationInfoCollection.markNoLongerInstantiated(clazz);
+          appInfo.removeFromSingleTargetLookupCache(clazz);
+        });
     // Written fields.
     FieldAccessInfoCollectionImpl fieldAccessInfoCollection =
         appInfo.getMutableFieldAccessInfoCollection();
diff --git a/src/main/java/com/android/tools/r8/shaking/SingleTargetLookupCache.java b/src/main/java/com/android/tools/r8/shaking/SingleTargetLookupCache.java
new file mode 100644
index 0000000..1691758
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/shaking/SingleTargetLookupCache.java
@@ -0,0 +1,58 @@
+// Copyright (c) 2020, 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.shaking;
+
+import com.android.tools.r8.graph.DexClass;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexType;
+import java.util.Map;
+import java.util.concurrent.ConcurrentHashMap;
+
+public class SingleTargetLookupCache {
+
+  private Map<DexType, Map<DexMethod, DexEncodedMethod>> cache = new ConcurrentHashMap<>();
+
+  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 removeInstantiatedType(DexType instantiatedType, AppInfoWithLiveness appInfo) {
+    // Remove all types in the hierarchy related to this type.
+    cache.remove(instantiatedType);
+    DexClass clazz = appInfo.definitionFor(instantiatedType);
+    if (clazz == null) {
+      return;
+    }
+    appInfo.forEachSuperType(clazz, (type, ignore) -> cache.remove(type));
+    appInfo.subtypes(instantiatedType).forEach(cache::remove);
+  }
+
+  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 hasCachedItem(DexType receiverType, DexMethod method) {
+    Map<DexMethod, DexEncodedMethod> cachedMethods = cache.get(receiverType);
+    if (cachedMethods == null) {
+      return false;
+    }
+    return cachedMethods.containsKey(method);
+  }
+
+  public void clear() {
+    cache = new ConcurrentHashMap<>();
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/resolution/virtualtargets/InstantiatedLowerBoundTest.java b/src/test/java/com/android/tools/r8/resolution/singletarget/InstantiatedLowerBoundTest.java
similarity index 98%
rename from src/test/java/com/android/tools/r8/resolution/virtualtargets/InstantiatedLowerBoundTest.java
rename to src/test/java/com/android/tools/r8/resolution/singletarget/InstantiatedLowerBoundTest.java
index 6001370..deec1e3 100644
--- a/src/test/java/com/android/tools/r8/resolution/virtualtargets/InstantiatedLowerBoundTest.java
+++ b/src/test/java/com/android/tools/r8/resolution/singletarget/InstantiatedLowerBoundTest.java
@@ -2,7 +2,7 @@
 // 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.resolution.virtualtargets;
+package com.android.tools.r8.resolution.singletarget;
 
 import static junit.framework.TestCase.assertEquals;
 import static junit.framework.TestCase.assertNotNull;
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
new file mode 100644
index 0000000..870c9cc
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/resolution/singletarget/SuccessAndInvalidLookupTest.java
@@ -0,0 +1,95 @@
+// Copyright (c) 2020, 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.resolution.singletarget;
+
+import static junit.framework.TestCase.assertEquals;
+import static junit.framework.TestCase.assertNotNull;
+import static junit.framework.TestCase.assertNull;
+
+import com.android.tools.r8.TestBase;
+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.DexMethod;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import java.util.ArrayList;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class SuccessAndInvalidLookupTest extends TestBase {
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withNoneRuntime().build();
+  }
+
+  public SuccessAndInvalidLookupTest(TestParameters parameters) {
+    // Empty to satisfy construction of none-runtime.
+  }
+
+  @Test
+  public void testSingleTargetWithInvalidInvokeInterfaceInvoke() throws Exception {
+    AppView<AppInfoWithLiveness> appView =
+        computeAppViewWithLiveness(
+            buildClasses(I.class, A.class, Main.class).build(),
+            factory -> new ArrayList<>(buildKeepRuleForClassAndMethods(Main.class, factory)));
+    AppInfoWithLiveness appInfo = appView.appInfo();
+    DexType typeMain = buildType(Main.class, appInfo.dexItemFactory());
+    DexType typeA = buildType(A.class, appInfo.dexItemFactory());
+    DexMethod fooA = buildNullaryVoidMethod(A.class, "foo", appInfo.dexItemFactory());
+    DexEncodedMethod singleTarget =
+        appInfo.lookupSingleVirtualTarget(fooA, typeMain, false, t -> false, typeA, null);
+    assertNotNull(singleTarget);
+    assertEquals(fooA, singleTarget.method);
+    DexEncodedMethod invalidSingleTarget =
+        appInfo.lookupSingleVirtualTarget(fooA, typeMain, true, t -> false, typeA, null);
+    assertNull(invalidSingleTarget);
+  }
+
+  @Test
+  public void testSingleTargetWithInvalidInvokeVirtualInvoke() throws Exception {
+    AppView<AppInfoWithLiveness> appView =
+        computeAppViewWithLiveness(
+            buildClasses(I.class, A.class, Main.class).build(),
+            factory -> new ArrayList<>(buildKeepRuleForClassAndMethods(Main.class, factory)));
+    AppInfoWithLiveness appInfo = appView.appInfo();
+    DexType typeMain = buildType(Main.class, appInfo.dexItemFactory());
+    DexType typeA = buildType(I.class, appInfo.dexItemFactory());
+    DexMethod fooI = buildNullaryVoidMethod(I.class, "foo", appInfo.dexItemFactory());
+    DexMethod fooA = buildNullaryVoidMethod(A.class, "foo", appInfo.dexItemFactory());
+    DexEncodedMethod singleTarget =
+        appInfo.lookupSingleVirtualTarget(fooI, typeMain, true, t -> false, typeA, null);
+    assertNotNull(singleTarget);
+    assertEquals(fooA, singleTarget.method);
+    DexEncodedMethod invalidSingleTarget =
+        appInfo.lookupSingleVirtualTarget(fooI, typeMain, false, t -> false, typeA, null);
+    assertNull(invalidSingleTarget);
+  }
+
+  public interface I {
+
+    void foo();
+  }
+
+  public static class A implements I {
+
+    @Override
+    public void foo() {
+      System.out.println("A.foo");
+    }
+  }
+
+  public static class Main {
+
+    public static void main(String[] args) {
+      new A();
+    }
+  }
+}