diff --git a/src/main/java/com/android/tools/r8/Version.java b/src/main/java/com/android/tools/r8/Version.java
index 4b67000..f301864 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.5.41";
+  public static final String LABEL = "1.5.42";
 
   private Version() {
   }
diff --git a/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java b/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java
index 9b07115..e5e906b 100644
--- a/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java
@@ -231,14 +231,14 @@
       return;
     }
     DexString newName = state.assignNewNameFor(method, method.name, method.proto);
-    if (newName != method.name) {
-      addRenaming(encodedMethod, state, newName);
-    }
+    addRenaming(encodedMethod, state, newName);
   }
 
   private void addRenaming(
       DexEncodedMethod encodedMethod, MethodNamingState<?> state, DexString renamedName) {
-    renaming.put(encodedMethod.method, renamedName);
+    if (encodedMethod.method.name != renamedName) {
+      renaming.put(encodedMethod.method, renamedName);
+    }
     if (!encodedMethod.accessFlags.isPrivate()) {
       state.addRenaming(encodedMethod.method.name, encodedMethod.method.proto, renamedName);
     }
@@ -314,9 +314,7 @@
             }
             state.reserveName(reservedName, method.method.proto, method.method.name);
             globalState.reserveName(reservedName, method.method.proto, method.method.name);
-            if (reservedName != method.method.name) {
-              addRenaming(method, state, reservedName);
-            }
+            addRenaming(method, state, reservedName);
           }
         }
       }
diff --git a/src/test/java/com/android/tools/r8/naming/AbstractMethodRenamingTest.java b/src/test/java/com/android/tools/r8/naming/AbstractMethodRenamingTest.java
new file mode 100644
index 0000000..71b158d
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/naming/AbstractMethodRenamingTest.java
@@ -0,0 +1,106 @@
+// 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.naming;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static com.android.tools.r8.utils.codeinspector.Matchers.isRenamed;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.junit.Assert.assertEquals;
+
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+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.MethodSubject;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class AbstractMethodRenamingTest extends TestBase {
+
+  static abstract class Base implements Runnable {
+    @NeverInline
+    public abstract void foo();
+
+    @NeverInline
+    @Override
+    public void run() {
+      foo();
+    }
+  }
+
+  static final class Sub1 extends Base {
+    public final void foo() {
+      System.out.println("Sub1::foo");
+    }
+  }
+
+  static final class Sub2 extends Base {
+    public final void foo() {
+      System.out.println("Sub2::foo");
+    }
+  }
+
+  static class TestMain {
+    static Runnable createInstance() {
+      return System.currentTimeMillis() > 0 ? new Sub1() : new Sub2();
+    }
+    public static void main(String... args) {
+      Runnable instance = createInstance();
+      instance.run();
+    }
+  }
+
+  private TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimes().build();
+  }
+
+  public AbstractMethodRenamingTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(AbstractMethodRenamingTest.class)
+        .addKeepMainRule(TestMain.class)
+        .enableInliningAnnotations()
+        .setMinApi(parameters.getRuntime())
+        .run(parameters.getRuntime(), TestMain.class)
+        .assertSuccessWithOutput(StringUtils.lines("Sub1::foo"))
+        .inspect(this::inspect);
+  }
+
+  private void inspect(CodeInspector inspector) {
+    ClassSubject base = inspector.clazz(Base.class);
+    assertThat(base, isPresent());
+    assertThat(base, isRenamed());
+    MethodSubject foo = base.uniqueMethodWithName("foo");
+    assertThat(foo, isPresent());
+    assertThat(foo, isRenamed());
+
+    ClassSubject sub1 = inspector.clazz(Sub1.class);
+    assertThat(sub1, isPresent());
+    assertThat(sub1, isRenamed());
+    MethodSubject fooInSub1 = sub1.uniqueMethodWithName("foo");
+    assertThat(fooInSub1, isPresent());
+    assertThat(fooInSub1, isRenamed());
+    assertEquals(foo.getFinalName(), fooInSub1.getFinalName());
+
+    ClassSubject sub2 = inspector.clazz(Sub1.class);
+    assertThat(sub2, isPresent());
+    assertThat(sub2, isRenamed());
+    MethodSubject fooInSub2 = sub2.uniqueMethodWithName("foo");
+    assertThat(fooInSub2, isPresent());
+    assertThat(fooInSub2, isRenamed());
+    assertEquals(foo.getFinalName(), fooInSub2.getFinalName());
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/naming/b133686361/AlreadyRenamedAbstractMethodRenamingTest.java b/src/test/java/com/android/tools/r8/naming/b133686361/AlreadyRenamedAbstractMethodRenamingTest.java
new file mode 100644
index 0000000..d104210
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/naming/b133686361/AlreadyRenamedAbstractMethodRenamingTest.java
@@ -0,0 +1,113 @@
+// 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.naming.b133686361;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static com.android.tools.r8.utils.codeinspector.Matchers.isRenamed;
+import static org.hamcrest.CoreMatchers.not;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.junit.Assert.assertEquals;
+
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+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.MethodSubject;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+// Reproduce b/133686361
+// This test is just same as {@link com.android.tools.r8.naming.AbstractMethodRenamingTest},
+// except for methods `foo` being renamed to `a` (e.g., already processed by other shrinker).
+// In that case, assigning `a` to Base#a seems not a new renaming. But, if we skip marking that
+// name in the corresponding naming state, all subtypes' `a` are renamed to some other names,
+// resulting in AbstractMethodError.
+@RunWith(Parameterized.class)
+public class AlreadyRenamedAbstractMethodRenamingTest extends TestBase {
+
+  static abstract class Base implements Runnable {
+    @NeverInline
+    public abstract void a();
+
+    @NeverInline
+    @Override
+    public void run() {
+      a();
+    }
+  }
+
+  static final class Sub1 extends Base {
+    public final void a() {
+      System.out.println("Sub1::a");
+    }
+  }
+
+  static final class Sub2 extends Base {
+    public final void a() {
+      System.out.println("Sub2::a");
+    }
+  }
+
+  static class TestMain {
+    static Runnable createInstance() {
+      return System.currentTimeMillis() > 0 ? new Sub1() : new Sub2();
+    }
+    public static void main(String... args) {
+      Runnable instance = createInstance();
+      instance.run();
+    }
+  }
+
+  private TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimes().build();
+  }
+
+  public AlreadyRenamedAbstractMethodRenamingTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void b133686361() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(AlreadyRenamedAbstractMethodRenamingTest.class)
+        .addKeepMainRule(TestMain.class)
+        .enableInliningAnnotations()
+        .setMinApi(parameters.getRuntime())
+        .run(parameters.getRuntime(), TestMain.class)
+        .assertSuccessWithOutput(StringUtils.lines("Sub1::a"))
+        .inspect(this::inspect);
+  }
+
+  private void inspect(CodeInspector inspector) {
+    ClassSubject base = inspector.clazz(Base.class);
+    assertThat(base, isPresent());
+    assertThat(base, isRenamed());
+    MethodSubject a = base.uniqueMethodWithName("a");
+    assertThat(a, isPresent());
+    assertThat(a, not(isRenamed()));
+
+    ClassSubject sub1 = inspector.clazz(Sub1.class);
+    assertThat(sub1, isPresent());
+    assertThat(sub1, isRenamed());
+    MethodSubject aInSub1 = sub1.uniqueMethodWithName("a");
+    assertThat(aInSub1, isPresent());
+    assertThat(aInSub1, not(isRenamed()));
+    assertEquals(a.getFinalName(), aInSub1.getFinalName());
+
+    ClassSubject sub2 = inspector.clazz(Sub1.class);
+    assertThat(sub2, isPresent());
+    assertThat(sub2, isRenamed());
+    MethodSubject aInSub2 = sub2.uniqueMethodWithName("a");
+    assertThat(aInSub2, isPresent());
+    assertThat(aInSub2, not(isRenamed()));
+    assertEquals(a.getFinalName(), aInSub2.getFinalName());
+  }
+}