diff --git a/src/main/java/com/android/tools/r8/Version.java b/src/main/java/com/android/tools/r8/Version.java
index cbefea3..2fe03c0 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.76";
+  public static final String LABEL = "1.4.77";
 
   private Version() {
   }
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/MethodPoolCollection.java b/src/main/java/com/android/tools/r8/ir/optimize/MethodPoolCollection.java
index ca38f09..26dee92 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/MethodPoolCollection.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/MethodPoolCollection.java
@@ -110,14 +110,13 @@
         }
       }
       if (clazz.isInterface()) {
-        clazz.type.forAllImplementsSubtypes(
-            implementer -> {
-              DexClass subClazz = application.definitionFor(implementer);
-              if (subClazz != null) {
-                MethodPool childPool = methodPools.computeIfAbsent(subClazz, k -> new MethodPool());
-                childPool.linkInterface(methodPool);
-              }
-            });
+        for (DexType subtype : clazz.type.allImmediateSubtypes()) {
+          DexClass subClazz = application.definitionFor(subtype);
+          if (subClazz != null) {
+            MethodPool childPool = methodPools.computeIfAbsent(subClazz, k -> new MethodPool());
+            childPool.linkInterface(methodPool);
+          }
+        }
       }
     };
   }
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/uninstantiatedtypes/NestedInterfaceMethodTest.java b/src/test/java/com/android/tools/r8/ir/optimize/uninstantiatedtypes/NestedInterfaceMethodTest.java
new file mode 100644
index 0000000..9c8666d
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/uninstantiatedtypes/NestedInterfaceMethodTest.java
@@ -0,0 +1,104 @@
+// 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.ir.optimize.uninstantiatedtypes;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.NeverMerge;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import com.android.tools.r8.utils.StringUtils;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+/** Reproduction for b/128917897. */
+@RunWith(Parameterized.class)
+public class NestedInterfaceMethodTest extends TestBase {
+
+  private final Backend backend;
+
+  @Parameters(name = "Backend: {0}")
+  public static Backend[] data() {
+    return Backend.values();
+  }
+
+  public NestedInterfaceMethodTest(Backend backend) {
+    this.backend = backend;
+  }
+
+  @Test
+  public void test() throws Exception {
+    String expectedOutput = StringUtils.lines("In A.m()", "In A.m()");
+
+    if (backend == Backend.CF) {
+      testForJvm().addTestClasspath().run(TestClass.class).assertSuccessWithOutput(expectedOutput);
+    }
+
+    CodeInspector inspector =
+        testForR8(backend)
+            .addInnerClasses(NestedInterfaceMethodTest.class)
+            .addKeepMainRule(TestClass.class)
+            .enableInliningAnnotations()
+            .enableMergeAnnotations()
+            .addOptionsModification(options -> options.enableDevirtualization = false)
+            .run(TestClass.class)
+            .assertSuccessWithOutput(expectedOutput)
+            .inspector();
+
+    ClassSubject interfaceSubject = inspector.clazz(I.class);
+    assertThat(interfaceSubject, isPresent());
+    assertThat(interfaceSubject.method(Uninstantiated.class.getTypeName(), "m"), isPresent());
+
+    ClassSubject classSubject = inspector.clazz(A.class);
+    assertThat(classSubject, isPresent());
+    assertThat(classSubject.method(Uninstantiated.class.getTypeName(), "m"), isPresent());
+  }
+
+  static class TestClass {
+
+    public static void main(String[] args) {
+      test(new B());
+      test(new C());
+    }
+
+    @NeverInline
+    private static void test(I obj) {
+      obj.m();
+    }
+  }
+
+  @NeverMerge
+  interface I {
+
+    Uninstantiated m();
+  }
+
+  @NeverMerge
+  interface J extends I {}
+
+  static class A implements J {
+
+    @Override
+    public Uninstantiated m() {
+      System.out.println("In A.m()");
+      return null;
+    }
+  }
+
+  static class B extends A {}
+
+  // The purpose of this class is merely to avoid that the invoke-interface instruction in
+  // TestClass.test() gets devirtualized to an invoke-virtual instruction. Otherwise the method
+  // I.m() would not be present in the output.
+  static class C extends A {}
+
+  static class Uninstantiated {}
+}