diff --git a/src/main/java/com/android/tools/r8/Version.java b/src/main/java/com/android/tools/r8/Version.java
index 558540a..6ebdc7c 100644
--- a/src/main/java/com/android/tools/r8/Version.java
+++ b/src/main/java/com/android/tools/r8/Version.java
@@ -11,7 +11,7 @@
 
   // This field is accessed from release scripts using simple pattern matching.
   // Therefore, changing this field could break our release scripts.
-  public static final String LABEL = "1.4.35";
+  public static final String LABEL = "1.4.36";
 
   private Version() {
   }
diff --git a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
index 4db858b..0d05021 100644
--- a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
+++ b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
@@ -640,7 +640,6 @@
 
   public DexEncodedMethod toForwardingMethod(DexClass holder, DexItemFactory itemFactory) {
     checkIfObsolete();
-    assert accessFlags.isPublic();
     // Clear the final flag, as this method is now overwritten. Do this before creating the builder
     // for the forwarding method, as the forwarding method will copy the access flags from this,
     // and if different forwarding methods are created in different subclasses the first could be
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 3c300b6..608f915 100644
--- a/src/main/java/com/android/tools/r8/optimize/MemberRebindingAnalysis.java
+++ b/src/main/java/com/android/tools/r8/optimize/MemberRebindingAnalysis.java
@@ -120,8 +120,10 @@
   }
 
   private void computeMethodRebinding(
-      Set<DexMethod> methods, Function<DexMethod, DexEncodedMethod> lookupTarget, Type invokeType) {
-    for (DexMethod method : methods) {
+      Map<DexMethod, Set<DexEncodedMethod>> methodsWithContexts,
+      Function<DexMethod, DexEncodedMethod> lookupTarget,
+      Type invokeType) {
+    for (DexMethod method : methodsWithContexts.keySet()) {
       // We can safely ignore array types, as the corresponding methods are defined in a library.
       if (!method.getHolder().isClassType()) {
         continue;
@@ -149,7 +151,10 @@
 
         // If the target class is not public but the targeted method is, we might run into
         // visibility problems when rebinding.
-        if (mayNeedBridgeForVisibility(target, targetClass)) {
+        final DexEncodedMethod finalTarget = target;
+        Set<DexEncodedMethod> contexts = methodsWithContexts.get(method);
+        if (contexts.stream().anyMatch(context ->
+            mayNeedBridgeForVisibility(context.method.getHolder(), finalTarget))) {
           target =
               insertBridgeForVisibilityIfNeeded(
                   method, target, originalClass, targetClass, lookupTarget);
@@ -205,8 +210,20 @@
     return findHolderForInterfaceMethodBridge(superClass.asProgramClass(), iface);
   }
 
-  private boolean mayNeedBridgeForVisibility(DexEncodedMethod target, DexClass targetClass) {
-    return !targetClass.accessFlags.isPublic() && target.accessFlags.isPublic();
+  private boolean mayNeedBridgeForVisibility(DexType context, DexEncodedMethod method) {
+    DexType holderType = method.method.getHolder();
+    DexClass holder = appInfo.definitionFor(holderType);
+    if (holder == null) {
+      return false;
+    }
+    ConstraintWithTarget classVisibility =
+        ConstraintWithTarget.deriveConstraint(context, holderType, holder.accessFlags, appInfo);
+    ConstraintWithTarget methodVisibility =
+        ConstraintWithTarget.deriveConstraint(context, holderType, method.accessFlags, appInfo);
+    // We may need bridge for visibility if the target class is not visible while the target method
+    // is visible from the calling context.
+    return classVisibility == ConstraintWithTarget.NEVER
+        && methodVisibility != ConstraintWithTarget.NEVER;
   }
 
   private DexEncodedMethod insertBridgeForVisibilityIfNeeded(
@@ -263,15 +280,15 @@
     return null;
   }
 
-  private void computeFieldRebinding(Map<DexField, Set<DexEncodedMethod>> fields,
+  private void computeFieldRebinding(
+      Map<DexField, Set<DexEncodedMethod>> fieldsWithContexts,
       BiFunction<DexType, DexField, DexEncodedField> lookup,
       BiFunction<DexClass, DexField, DexEncodedField> lookupTargetOnClass) {
-    for (Map.Entry<DexField, Set<DexEncodedMethod>> entry : fields.entrySet()) {
-      DexField field = entry.getKey();
+    for (DexField field : fieldsWithContexts.keySet()) {
       DexEncodedField target = lookup.apply(field.getHolder(), field);
       // Rebind to the lowest library class or program class. Do not rebind accesses to fields that
       // are not visible from the access context.
-      Set<DexEncodedMethod> contexts = entry.getValue();
+      Set<DexEncodedMethod> contexts = fieldsWithContexts.get(field);
       if (target != null && target.field != field
           && contexts.stream().allMatch(context ->
               isVisibleFromOriginalContext(context.method.getHolder(), target))) {
diff --git a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
index 55ceee8..a51ca83 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -88,7 +88,9 @@
 import java.util.Objects;
 import java.util.Queue;
 import java.util.Set;
+import java.util.SortedMap;
 import java.util.SortedSet;
+import java.util.TreeMap;
 import java.util.concurrent.ExecutionException;
 import java.util.concurrent.ExecutorService;
 import java.util.function.BiConsumer;
@@ -116,12 +118,16 @@
   private RootSet rootSet;
   private ProguardClassFilter dontWarnPatterns;
 
-  private final Map<DexType, Set<DexMethod>> virtualInvokes = Maps.newIdentityHashMap();
-  private final Map<DexType, Set<DexMethod>> interfaceInvokes = Maps.newIdentityHashMap();
+  private final Map<DexType, Set<TargetWithContext<DexMethod>>> virtualInvokes =
+      Maps.newIdentityHashMap();
+  private final Map<DexType, Set<TargetWithContext<DexMethod>>> interfaceInvokes =
+      Maps.newIdentityHashMap();
   private final Map<DexType, Set<TargetWithContext<DexMethod>>> superInvokes =
       Maps.newIdentityHashMap();
-  private final Map<DexType, Set<DexMethod>> directInvokes = Maps.newIdentityHashMap();
-  private final Map<DexType, Set<DexMethod>> staticInvokes = Maps.newIdentityHashMap();
+  private final Map<DexType, Set<TargetWithContext<DexMethod>>> directInvokes =
+      Maps.newIdentityHashMap();
+  private final Map<DexType, Set<TargetWithContext<DexMethod>>> staticInvokes =
+      Maps.newIdentityHashMap();
   private final Map<DexType, Set<TargetWithContext<DexField>>> instanceFieldsWritten =
       Maps.newIdentityHashMap();
   private final Map<DexType, Set<TargetWithContext<DexField>>> instanceFieldsRead =
@@ -439,7 +445,7 @@
         // Revisit the current method to implicitly add -keep rule for items with reflective access.
         pendingReflectiveUses.add(currentMethod);
       }
-      if (!registerItemWithTarget(virtualInvokes, method)) {
+      if (!registerItemWithTargetAndContext(virtualInvokes, method, currentMethod)) {
         return false;
       }
       if (Log.ENABLED) {
@@ -455,7 +461,7 @@
     }
 
     boolean registerInvokeDirect(DexMethod method, KeepReason keepReason) {
-      if (!registerItemWithTarget(directInvokes, method)) {
+      if (!registerItemWithTargetAndContext(directInvokes, method, currentMethod)) {
         return false;
       }
       if (Log.ENABLED) {
@@ -482,7 +488,7 @@
       if (method == appInfo.dexItemFactory.enumMethods.valueOf) {
         pendingReflectiveUses.add(currentMethod);
       }
-      if (!registerItemWithTarget(staticInvokes, method)) {
+      if (!registerItemWithTargetAndContext(staticInvokes, method, currentMethod)) {
         return false;
       }
       if (Log.ENABLED) {
@@ -498,7 +504,7 @@
     }
 
     boolean registerInvokeInterface(DexMethod method, KeepReason keepReason) {
-      if (!registerItemWithTarget(interfaceInvokes, method)) {
+      if (!registerItemWithTargetAndContext(interfaceInvokes, method, currentMethod)) {
         return false;
       }
       if (Log.ENABLED) {
@@ -1629,34 +1635,18 @@
     }
   }
 
-  private Map<DexField, Set<DexEncodedMethod>> collectFields(
-      Map<DexType, Set<TargetWithContext<DexField>>> map) {
-    Map<DexField, Set<DexEncodedMethod>> result = new IdentityHashMap<>();
-    for (Entry<DexType, Set<TargetWithContext<DexField>>> entry : map.entrySet()) {
-      for (TargetWithContext<DexField> fieldWithContext : entry.getValue()) {
-        DexField field = fieldWithContext.getTarget();
-        DexEncodedMethod context = fieldWithContext.getContext();
-        result.computeIfAbsent(field, k -> Sets.newIdentityHashSet())
+  <T extends Descriptor<?, T>> SortedMap<T, Set<DexEncodedMethod>> collectDescriptors(
+      Map<DexType, Set<TargetWithContext<T>>> map) {
+    SortedMap<T, Set<DexEncodedMethod>> result = new TreeMap<>(PresortedComparable::slowCompare);
+    for (Entry<DexType, Set<TargetWithContext<T>>> entry : map.entrySet()) {
+      for (TargetWithContext<T> descriptorWithContext : entry.getValue()) {
+        T descriptor = descriptorWithContext.getTarget();
+        DexEncodedMethod context = descriptorWithContext.getContext();
+        result.computeIfAbsent(descriptor, k -> Sets.newIdentityHashSet())
             .add(context);
       }
     }
-    return result;
-  }
-
-  Map<DexField, Set<DexEncodedMethod>> collectInstanceFieldsRead() {
-    return Collections.unmodifiableMap(collectFields(instanceFieldsRead));
-  }
-
-  Map<DexField, Set<DexEncodedMethod>> collectInstanceFieldsWritten() {
-    return Collections.unmodifiableMap(collectFields(instanceFieldsWritten));
-  }
-
-  Map<DexField, Set<DexEncodedMethod>> collectStaticFieldsRead() {
-    return Collections.unmodifiableMap(collectFields(staticFieldsRead));
-  }
-
-  Map<DexField, Set<DexEncodedMethod>> collectStaticFieldsWritten() {
-    return Collections.unmodifiableMap(collectFields(staticFieldsWritten));
+    return Collections.unmodifiableSortedMap(result);
   }
 
   private Set<DexField> collectReachedFields(
@@ -1915,39 +1905,39 @@
     /**
      * Set of all field ids used in instance field reads, along with access context.
      */
-    public final Map<DexField, Set<DexEncodedMethod>> instanceFieldReads;
+    public final SortedMap<DexField, Set<DexEncodedMethod>> instanceFieldReads;
     /**
      * Set of all field ids used in instance field writes, along with access context.
      */
-    public final Map<DexField, Set<DexEncodedMethod>> instanceFieldWrites;
+    public final SortedMap<DexField, Set<DexEncodedMethod>> instanceFieldWrites;
     /**
      * Set of all field ids used in static field reads, along with access context.
      */
-    public final Map<DexField, Set<DexEncodedMethod>> staticFieldReads;
+    public final SortedMap<DexField, Set<DexEncodedMethod>> staticFieldReads;
     /**
      * Set of all field ids used in static field writes, along with access context.
      */
-    public final Map<DexField, Set<DexEncodedMethod>> staticFieldWrites;
+    public final SortedMap<DexField, Set<DexEncodedMethod>> staticFieldWrites;
     /**
-     * Set of all methods referenced in virtual invokes;
+     * Set of all methods referenced in virtual invokes, along with calling context.
      */
-    public final SortedSet<DexMethod> virtualInvokes;
+    public final SortedMap<DexMethod, Set<DexEncodedMethod>> virtualInvokes;
     /**
-     * Set of all methods referenced in interface invokes;
+     * Set of all methods referenced in interface invokes, along with calling context.
      */
-    public final SortedSet<DexMethod> interfaceInvokes;
+    public final SortedMap<DexMethod, Set<DexEncodedMethod>> interfaceInvokes;
     /**
-     * Set of all methods referenced in super invokes;
+     * Set of all methods referenced in super invokes, along with calling context.
      */
-    public final SortedSet<DexMethod> superInvokes;
+    public final SortedMap<DexMethod, Set<DexEncodedMethod>> superInvokes;
     /**
-     * Set of all methods referenced in direct invokes;
+     * Set of all methods referenced in direct invokes, along with calling context.
      */
-    public final SortedSet<DexMethod> directInvokes;
+    public final SortedMap<DexMethod, Set<DexEncodedMethod>> directInvokes;
     /**
-     * Set of all methods referenced in static invokes;
+     * Set of all methods referenced in static invokes, along with calling context.
      */
-    public final SortedSet<DexMethod> staticInvokes;
+    public final SortedMap<DexMethod, Set<DexEncodedMethod>> staticInvokes;
     /**
      * Set of live call sites in the code. Note that if desugaring has taken place call site objects
      * will have been removed from the code.
@@ -2041,20 +2031,20 @@
               DexMethod::slowCompareTo, enqueuer.virtualMethodsTargetedByInvokeDirect);
       this.liveMethods = toSortedDescriptorSet(enqueuer.liveMethods.getItems());
       this.liveFields = toSortedDescriptorSet(enqueuer.liveFields.getItems());
-      this.instanceFieldReads = enqueuer.collectInstanceFieldsRead();
-      this.instanceFieldWrites = enqueuer.collectInstanceFieldsWritten();
-      this.staticFieldReads = enqueuer.collectStaticFieldsRead();
-      this.staticFieldWrites = enqueuer.collectStaticFieldsWritten();
+      this.instanceFieldReads = enqueuer.collectDescriptors(enqueuer.instanceFieldsRead);
+      this.instanceFieldWrites = enqueuer.collectDescriptors(enqueuer.instanceFieldsWritten);
+      this.staticFieldReads = enqueuer.collectDescriptors(enqueuer.staticFieldsRead);
+      this.staticFieldWrites = enqueuer.collectDescriptors(enqueuer.staticFieldsWritten);
       this.fieldsRead = enqueuer.mergeFieldAccesses(
           instanceFieldReads.keySet(), staticFieldReads.keySet());
       this.fieldsWritten = enqueuer.mergeFieldAccesses(
           instanceFieldWrites.keySet(), staticFieldWrites.keySet());
       this.pinnedItems = enqueuer.pinnedItems;
-      this.virtualInvokes = joinInvokedMethods(enqueuer.virtualInvokes);
-      this.interfaceInvokes = joinInvokedMethods(enqueuer.interfaceInvokes);
-      this.superInvokes = joinInvokedMethods(enqueuer.superInvokes, TargetWithContext::getTarget);
-      this.directInvokes = joinInvokedMethods(enqueuer.directInvokes);
-      this.staticInvokes = joinInvokedMethods(enqueuer.staticInvokes);
+      this.virtualInvokes = enqueuer.collectDescriptors(enqueuer.virtualInvokes);
+      this.interfaceInvokes = enqueuer.collectDescriptors(enqueuer.interfaceInvokes);
+      this.superInvokes = enqueuer.collectDescriptors(enqueuer.superInvokes);
+      this.directInvokes = enqueuer.collectDescriptors(enqueuer.directInvokes);
+      this.staticInvokes = enqueuer.collectDescriptors(enqueuer.staticInvokes);
       this.callSites = enqueuer.callSites;
       this.brokenSuperInvokes =
           ImmutableSortedSet.copyOf(DexMethod::slowCompareTo, enqueuer.brokenSuperInvokes);
@@ -2153,11 +2143,16 @@
       this.fieldsRead = rewriteItems(previous.fieldsRead, lense::lookupField);
       this.fieldsWritten = rewriteItems(previous.fieldsWritten, lense::lookupField);
       this.pinnedItems = lense.rewriteReferencesConservatively(previous.pinnedItems);
-      this.virtualInvokes = lense.rewriteMethodsConservatively(previous.virtualInvokes);
-      this.interfaceInvokes = lense.rewriteMethodsConservatively(previous.interfaceInvokes);
-      this.superInvokes = lense.rewriteMethodsConservatively(previous.superInvokes);
-      this.directInvokes = lense.rewriteMethodsConservatively(previous.directInvokes);
-      this.staticInvokes = lense.rewriteMethodsConservatively(previous.staticInvokes);
+      this.virtualInvokes = rewriteKeysConservativelyWhileMergingValues(
+          previous.virtualInvokes, lense::lookupMethodInAllContexts);
+      this.interfaceInvokes = rewriteKeysConservativelyWhileMergingValues(
+          previous.interfaceInvokes, lense::lookupMethodInAllContexts);
+      this.superInvokes = rewriteKeysConservativelyWhileMergingValues(
+          previous.superInvokes, lense::lookupMethodInAllContexts);
+      this.directInvokes = rewriteKeysConservativelyWhileMergingValues(
+          previous.directInvokes, lense::lookupMethodInAllContexts);
+      this.staticInvokes = rewriteKeysConservativelyWhileMergingValues(
+          previous.staticInvokes, lense::lookupMethodInAllContexts);
       // TODO(sgjesse): Rewrite call sites as well? Right now they are only used by minification
       // after second tree shaking.
       this.callSites = previous.callSites;
@@ -2294,16 +2289,6 @@
       return isInstantiatedDirectly(type) || isInstantiatedIndirectly(type);
     }
 
-    private SortedSet<DexMethod> joinInvokedMethods(Map<DexType, Set<DexMethod>> invokes) {
-      return joinInvokedMethods(invokes, Function.identity());
-    }
-
-    private <T> SortedSet<DexMethod> joinInvokedMethods(Map<DexType, Set<T>> invokes,
-        Function<T, DexMethod> getter) {
-      return invokes.values().stream().flatMap(Set::stream).map(getter)
-          .collect(ImmutableSortedSet.toImmutableSortedSet(PresortedComparable::slowCompare));
-    }
-
     private Object2BooleanMap<DexReference> joinIdentifierNameStrings(
         Set<DexReference> explicit, Set<DexReference> implicit) {
       Object2BooleanMap<DexReference> result = new Object2BooleanArrayMap<>();
@@ -2336,17 +2321,30 @@
       return builder.build();
     }
 
-
     private static <T extends PresortedComparable<T>, S>
-        Map<T, Set<S>> rewriteKeysWhileMergingValues(
+        SortedMap<T, Set<S>> rewriteKeysWhileMergingValues(
             Map<T, Set<S>> original, Function<T, T> rewrite) {
-      Map<T, Set<S>> result = new IdentityHashMap<>();
+      SortedMap<T, Set<S>> result = new TreeMap<>(PresortedComparable::slowCompare);
       for (T item : original.keySet()) {
         T rewrittenKey = rewrite.apply(item);
         result.computeIfAbsent(rewrittenKey, k -> Sets.newIdentityHashSet())
             .addAll(original.get(item));
       }
-      return Collections.unmodifiableMap(result);
+      return Collections.unmodifiableSortedMap(result);
+    }
+
+    private static <T extends PresortedComparable<T>, S>
+        SortedMap<T, Set<S>> rewriteKeysConservativelyWhileMergingValues(
+            Map<T, Set<S>> original, Function<T, Set<T>> rewrite) {
+      SortedMap<T, Set<S>> result = new TreeMap<>(PresortedComparable::slowCompare);
+      for (T item : original.keySet()) {
+        Set<T> rewrittenKeys = rewrite.apply(item);
+        for (T rewrittenKey : rewrittenKeys) {
+          result.computeIfAbsent(rewrittenKey, k -> Sets.newIdentityHashSet())
+              .addAll(original.get(item));
+        }
+      }
+      return Collections.unmodifiableSortedMap(result);
     }
 
     @Override
diff --git a/src/test/java/com/android/tools/r8/resolution/b123730538/B123730538.java b/src/test/java/com/android/tools/r8/resolution/b123730538/B123730538.java
new file mode 100644
index 0000000..462d514
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/resolution/b123730538/B123730538.java
@@ -0,0 +1,99 @@
+// Copyright (c) 2019, 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.b123730538;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotEquals;
+import static org.junit.Assert.assertThat;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.resolution.b123730538.runner.PublicClassExtender;
+import com.android.tools.r8.resolution.b123730538.runner.Runner;
+import com.android.tools.r8.resolution.b123730538.sub.PublicClass;
+import com.android.tools.r8.utils.StringUtils;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import com.android.tools.r8.utils.codeinspector.InstructionSubject;
+import com.android.tools.r8.utils.codeinspector.MethodSubject;
+import com.google.common.collect.ImmutableList;
+import java.nio.file.Path;
+import java.util.List;
+import org.junit.BeforeClass;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class B123730538 extends TestBase {
+  private static final Class MAIN = Runner.class;
+  private static List<Path> CLASSES;
+  private static final String EXPECTED_OUTPUT = StringUtils.lines("pkg.AbstractClass::foo");
+
+  private final Backend backend;
+
+  @Parameterized.Parameters(name = "Backend: {0}")
+  public static Object[] data() {
+    return Backend.values();
+  }
+
+  public B123730538(Backend backend) {
+    this.backend = backend;
+  }
+
+  @BeforeClass
+  public static void setUpClass() throws Exception {
+    CLASSES = ImmutableList.<Path>builder()
+        .addAll(ToolHelper.getClassFilesForTestPackage(MAIN.getPackage()))
+        .addAll(ToolHelper.getClassFilesForTestPackage(PublicClass.class.getPackage()))
+        .build();
+  }
+
+  @Test
+  public void testProguard() throws Exception {
+    Path inJar = temp.newFile("input.jar").toPath().toAbsolutePath();
+    writeToJar(inJar, CLASSES);
+    testForProguard()
+        .addProgramFiles(inJar)
+        .addKeepMainRule(MAIN)
+        .addKeepRules("-dontoptimize")
+        .run(MAIN)
+        .assertSuccessWithOutput(EXPECTED_OUTPUT)
+        .inspect(this::inspect);
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    testForR8(backend)
+        .addProgramFiles(CLASSES)
+        .addKeepMainRule(MAIN)
+        .addKeepRules("-dontoptimize")
+        .run(MAIN)
+        .assertSuccessWithOutput(EXPECTED_OUTPUT)
+        .inspect(this::inspect);
+  }
+
+  private void inspect(CodeInspector inspector) {
+    MethodSubject foo = inspector.clazz(
+        PublicClass.class.getTypeName().replace("PublicClass", "AbstractClass"))
+        .uniqueMethodWithName("foo");
+    assertThat(foo, isPresent());
+
+    ClassSubject main = inspector.clazz(PublicClassExtender.class);
+    assertThat(main, isPresent());
+    MethodSubject methodSubject = main.uniqueMethodWithName("delegate");
+    assertThat(methodSubject, isPresent());
+
+    methodSubject
+        .iterateInstructions(InstructionSubject::isInvokeVirtual)
+        .forEachRemaining(instructionSubject -> {
+          String methodName = instructionSubject.getMethod().name.toString();
+          // Method references will be renamed.
+          assertNotEquals("foo", methodName);
+          assertEquals(foo.getFinalName(), methodName);
+        });
+  }
+
+}
diff --git a/src/test/java/com/android/tools/r8/resolution/b123730538/runner/AnotherPublicClassExtender.java b/src/test/java/com/android/tools/r8/resolution/b123730538/runner/AnotherPublicClassExtender.java
new file mode 100644
index 0000000..8377885
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/resolution/b123730538/runner/AnotherPublicClassExtender.java
@@ -0,0 +1,13 @@
+// Copyright (c) 2019, 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.b123730538.runner;
+
+import com.android.tools.r8.resolution.b123730538.sub.AnotherPublicClass;
+
+// To make AbstractPublicClass not mergeable for both R8 and Proguard.
+class AnotherPublicClassExtender extends AnotherPublicClass {
+  void delegate() {
+    foo();
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/resolution/b123730538/runner/PublicClassExtender.java b/src/test/java/com/android/tools/r8/resolution/b123730538/runner/PublicClassExtender.java
new file mode 100644
index 0000000..b866eea
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/resolution/b123730538/runner/PublicClassExtender.java
@@ -0,0 +1,15 @@
+// Copyright (c) 2019, 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.b123730538.runner;
+
+import com.android.tools.r8.resolution.b123730538.sub.PublicClass;
+
+public class PublicClassExtender extends PublicClass {
+  void delegate() {
+    // Method reference should be PublicClassExtender#foo, not the definition AbstractClass#foo
+    // because package-private AbstractClass is not visible from this calling context.
+    // Otherwise, we will see java.lang.IllegalAccessError.
+    foo();
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/resolution/b123730538/runner/Runner.java b/src/test/java/com/android/tools/r8/resolution/b123730538/runner/Runner.java
new file mode 100644
index 0000000..54e0c6e
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/resolution/b123730538/runner/Runner.java
@@ -0,0 +1,26 @@
+// Copyright (c) 2019, 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.b123730538.runner;
+
+public class Runner {
+
+  static int counter = 0;
+
+  static Object create() {
+    if (counter++ % 2 == 0) {
+      return new PublicClassExtender();
+    } else {
+      return new AnotherPublicClassExtender();
+    }
+  }
+
+  public static void main(String[] args) {
+    Object instance = create();
+    if (instance instanceof PublicClassExtender) {
+      ((PublicClassExtender) instance).delegate();
+    } else {
+      ((AnotherPublicClassExtender) instance).delegate();
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/resolution/b123730538/sub/AbstractClass.java b/src/test/java/com/android/tools/r8/resolution/b123730538/sub/AbstractClass.java
new file mode 100644
index 0000000..a99e9c5
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/resolution/b123730538/sub/AbstractClass.java
@@ -0,0 +1,10 @@
+// Copyright (c) 2019, 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.b123730538.sub;
+
+abstract class AbstractClass {
+  protected void foo() {
+    System.out.println("pkg.AbstractClass::foo");
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/resolution/b123730538/sub/AnotherPublicClass.java b/src/test/java/com/android/tools/r8/resolution/b123730538/sub/AnotherPublicClass.java
new file mode 100644
index 0000000..b9433a1
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/resolution/b123730538/sub/AnotherPublicClass.java
@@ -0,0 +1,8 @@
+// Copyright (c) 2019, 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.b123730538.sub;
+
+// To make AbstractClass not mergeable for both R8 and Proguard.
+public class AnotherPublicClass extends AbstractClass {
+}
diff --git a/src/test/java/com/android/tools/r8/resolution/b123730538/sub/PublicClass.java b/src/test/java/com/android/tools/r8/resolution/b123730538/sub/PublicClass.java
new file mode 100644
index 0000000..c3afbfc
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/resolution/b123730538/sub/PublicClass.java
@@ -0,0 +1,7 @@
+// Copyright (c) 2019, 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.b123730538.sub;
+
+public class PublicClass extends AbstractClass {
+}