diff --git a/src/main/java/com/android/tools/r8/graph/GraphLense.java b/src/main/java/com/android/tools/r8/graph/GraphLense.java
index 7d2d844..e5de7ff 100644
--- a/src/main/java/com/android/tools/r8/graph/GraphLense.java
+++ b/src/main/java/com/android/tools/r8/graph/GraphLense.java
@@ -15,7 +15,6 @@
 import java.util.ArrayDeque;
 import java.util.Collections;
 import java.util.Deque;
-import java.util.HashSet;
 import java.util.IdentityHashMap;
 import java.util.Map;
 import java.util.Set;
@@ -710,7 +709,7 @@
 
     @Override
     public Set<DexMethod> lookupMethodInAllContexts(DexMethod method) {
-      Set<DexMethod> result = new HashSet<>();
+      Set<DexMethod> result = Sets.newIdentityHashSet();
       for (DexMethod previous : previousLense.lookupMethodInAllContexts(method)) {
         result.add(methodMap.getOrDefault(previous, previous));
       }
diff --git a/src/main/java/com/android/tools/r8/optimize/MemberRebindingAnalysis.java b/src/main/java/com/android/tools/r8/optimize/MemberRebindingAnalysis.java
index beb3727..42e03e0 100644
--- a/src/main/java/com/android/tools/r8/optimize/MemberRebindingAnalysis.java
+++ b/src/main/java/com/android/tools/r8/optimize/MemberRebindingAnalysis.java
@@ -166,7 +166,7 @@
                     method, target, originalClass, targetClass, lookupTarget);
           }
         }
-        builder.map(method, lense.lookupMethod(validTargetFor(target.method, method)));
+        builder.map(method, lense.lookupMethod(validTargetFor(target.method, method)), invokeType);
       }
     }
   }
diff --git a/src/main/java/com/android/tools/r8/optimize/MemberRebindingLense.java b/src/main/java/com/android/tools/r8/optimize/MemberRebindingLense.java
index a845de2..95e2772 100644
--- a/src/main/java/com/android/tools/r8/optimize/MemberRebindingLense.java
+++ b/src/main/java/com/android/tools/r8/optimize/MemberRebindingLense.java
@@ -9,45 +9,72 @@
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.GraphLense;
 import com.android.tools.r8.graph.GraphLense.NestedGraphLense;
+import com.android.tools.r8.ir.code.Invoke;
 import com.android.tools.r8.ir.code.Invoke.Type;
 import com.google.common.collect.ImmutableMap;
+import java.util.Collections;
+import java.util.IdentityHashMap;
 import java.util.Map;
+import java.util.Set;
 
 public class MemberRebindingLense extends NestedGraphLense {
 
-  public static class Builder extends NestedGraphLense.Builder {
+  public static class Builder {
 
     private final AppView<?> appView;
 
+    private final Map<DexField, DexField> fieldMap = new IdentityHashMap<>();
+    private final Map<Invoke.Type, Map<DexMethod, DexMethod>> methodMaps = new IdentityHashMap<>();
+
     protected Builder(AppView<?> appView) {
       this.appView = appView;
     }
 
+    public void map(DexField from, DexField to) {
+      if (from == to) {
+        assert !fieldMap.containsKey(from);
+        return;
+      }
+      fieldMap.put(from, to);
+    }
+
+    public void map(DexMethod from, DexMethod to, Invoke.Type type) {
+      if (from == to) {
+        assert !methodMaps.containsKey(type) || methodMaps.get(type).getOrDefault(from, to) == to;
+        return;
+      }
+      Map<DexMethod, DexMethod> methodMap =
+          methodMaps.computeIfAbsent(type, ignore -> new IdentityHashMap<>());
+      assert methodMap.getOrDefault(from, to) == to;
+      methodMap.put(from, to);
+    }
+
     public GraphLense build(GraphLense previousLense) {
-      assert typeMap.isEmpty();
-      if (methodMap.isEmpty() && fieldMap.isEmpty()) {
+      if (fieldMap.isEmpty() && methodMaps.isEmpty()) {
         return previousLense;
       }
-      return new MemberRebindingLense(appView, methodMap, fieldMap, previousLense);
+      return new MemberRebindingLense(appView, methodMaps, fieldMap, previousLense);
     }
   }
 
   private final AppView<?> appView;
+  private final Map<Invoke.Type, Map<DexMethod, DexMethod>> methodMaps;
 
   public MemberRebindingLense(
       AppView<?> appView,
-      Map<DexMethod, DexMethod> methodMap,
+      Map<Invoke.Type, Map<DexMethod, DexMethod>> methodMaps,
       Map<DexField, DexField> fieldMap,
       GraphLense previousLense) {
     super(
         ImmutableMap.of(),
-        methodMap,
+        ImmutableMap.of(),
         fieldMap,
         null,
         null,
         previousLense,
         appView.dexItemFactory());
     this.appView = appView;
+    this.methodMaps = methodMaps;
   }
 
   public static Builder builder(AppView<?> appView) {
@@ -55,6 +82,28 @@
   }
 
   @Override
+  public boolean isLegitimateToHaveEmptyMappings() {
+    return true;
+  }
+
+  @Override
+  public GraphLenseLookupResult lookupMethod(DexMethod method, DexMethod context, Type type) {
+    GraphLenseLookupResult previous = previousLense.lookupMethod(method, context, type);
+    Map<DexMethod, DexMethod> methodMap = methodMaps.getOrDefault(type, Collections.emptyMap());
+    DexMethod newMethod = methodMap.get(previous.getMethod());
+    if (newMethod != null) {
+      return new GraphLenseLookupResult(
+          newMethod, mapInvocationType(newMethod, method, previous.getType()));
+    }
+    return previous;
+  }
+
+  @Override
+  public Set<DexMethod> lookupMethodInAllContexts(DexMethod method) {
+    return previousLense.lookupMethodInAllContexts(method);
+  }
+
+  @Override
   protected Type mapInvocationType(DexMethod newMethod, DexMethod originalMethod, Type type) {
     return super.mapVirtualInterfaceInvocationTypes(appView, newMethod, originalMethod, type);
   }
diff --git a/src/test/java/com/android/tools/r8/memberrebinding/MemberRebindingConflictTest.java b/src/test/java/com/android/tools/r8/memberrebinding/MemberRebindingConflictTest.java
index e081a44..b1ae543 100644
--- a/src/test/java/com/android/tools/r8/memberrebinding/MemberRebindingConflictTest.java
+++ b/src/test/java/com/android/tools/r8/memberrebinding/MemberRebindingConflictTest.java
@@ -4,11 +4,8 @@
 
 package com.android.tools.r8.memberrebinding;
 
-import static org.hamcrest.core.StringContains.containsString;
-
 import com.android.tools.r8.NeverInline;
 import com.android.tools.r8.NeverMerge;
-import com.android.tools.r8.R8TestRunResult;
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestParametersCollection;
@@ -35,36 +32,28 @@
 
   @Test
   public void test() throws Exception {
-    R8TestRunResult result =
-        testForR8(parameters.getBackend())
-            .addProgramClasses(A.class, TestClass.class)
-            .addProgramClassFileData(
-                transformer(B.class)
-                    .removeMethods(
-                        (access, name, descriptor, signature, exceptions) -> {
-                          if (name.equals("foo")) {
-                            assert MethodAccessFlags.fromCfAccessFlags(access, false).isSynthetic();
-                            return true;
-                          }
-                          return false;
-                        })
-                    .transform())
-            .addInnerClasses(MemberRebindingConflictTestClasses.class)
-            .addKeepMainRule(TestClass.class)
-            .enableInliningAnnotations()
-            .enableMergeAnnotations()
-            .enableNeverClassInliningAnnotations()
-            .setMinApi(parameters.getApiLevel())
-            .compile()
-            .run(parameters.getRuntime(), TestClass.class);
-
-    if (parameters.isDexRuntime()
-        && parameters.getRuntime().asDex().getVm().getVersion().isDalvik()) {
-      result.assertSuccessWithOutputLines("foo", "bar", "foo", "baz");
-    } else {
-      result.assertFailureWithErrorThatMatches(
-          containsString(IllegalAccessError.class.getTypeName()));
-    }
+    testForR8(parameters.getBackend())
+        .addProgramClasses(A.class, TestClass.class)
+        .addProgramClassFileData(
+            transformer(B.class)
+                .removeMethods(
+                    (access, name, descriptor, signature, exceptions) -> {
+                      if (name.equals("foo")) {
+                        assert MethodAccessFlags.fromCfAccessFlags(access, false).isSynthetic();
+                        return true;
+                      }
+                      return false;
+                    })
+                .transform())
+        .addInnerClasses(MemberRebindingConflictTestClasses.class)
+        .addKeepMainRule(TestClass.class)
+        .enableInliningAnnotations()
+        .enableMergeAnnotations()
+        .enableNeverClassInliningAnnotations()
+        .setMinApi(parameters.getApiLevel())
+        .compile()
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutputLines("foo", "bar", "foo", "baz");
   }
 
   static class TestClass {