diff --git a/src/main/java/com/android/tools/r8/Version.java b/src/main/java/com/android/tools/r8/Version.java
index 5d31bab..b6d1984 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.66";
+  public static final String LABEL = "1.4.67";
 
   private Version() {
   }
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/UnusedArgumentsCollector.java b/src/main/java/com/android/tools/r8/ir/optimize/UnusedArgumentsCollector.java
index 7056d32..fe2c067 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/UnusedArgumentsCollector.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/UnusedArgumentsCollector.java
@@ -145,13 +145,15 @@
       usedSignatures.add(equivalence.wrap(method));
     }
 
+    private void markSignatureAsNoLongerUsed(DexMethod method) {
+      boolean removed = usedSignatures.remove(equivalence.wrap(method));
+      assert removed;
+    }
+
     DexEncodedMethod removeArguments(DexEncodedMethod method, RemovedArgumentsInfo unused) {
       if (unused == null) {
         return null;
       }
-
-      boolean removed = usedSignatures.remove(equivalence.wrap(method.method));
-      assert removed;
       DexProto newProto = protoWithRemovedArguments(method, unused);
       DexMethod newSignature;
       int count = 0;
@@ -170,6 +172,7 @@
             appView.dexItemFactory().createMethod(method.method.holder, newProto, newName);
         count++;
       } while (!isMethodSignatureAvailable(newSignature));
+      markSignatureAsNoLongerUsed(method.method);
       markSignatureAsUsed(newSignature);
       return method.toTypeSubstitutedMethod(newSignature);
     }
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/unusedarguments/UnusedArgumentsInstanceConstructorCollisionTest.java b/src/test/java/com/android/tools/r8/ir/optimize/unusedarguments/UnusedArgumentsInstanceConstructorCollisionTest.java
new file mode 100644
index 0000000..3b0603c
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/unusedarguments/UnusedArgumentsInstanceConstructorCollisionTest.java
@@ -0,0 +1,67 @@
+// 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.unusedarguments;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.utils.StringUtils;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+/** Regression test for b/127691114. */
+@RunWith(Parameterized.class)
+public class UnusedArgumentsInstanceConstructorCollisionTest extends TestBase {
+
+  private final Backend backend;
+
+  @Parameters(name = "Backend: {0}")
+  public static Backend[] parameters() {
+    return Backend.values();
+  }
+
+  public UnusedArgumentsInstanceConstructorCollisionTest(Backend backend) {
+    this.backend = backend;
+  }
+
+  @Test
+  public void test() throws Exception {
+    String expectedOutput = StringUtils.lines("C");
+    testForR8(backend)
+        .addInnerClasses(UnusedArgumentsInstanceConstructorCollisionTest.class)
+        .addKeepMainRule(TestClass.class)
+        .run(TestClass.class)
+        .assertSuccessWithOutput(expectedOutput);
+  }
+
+  static class TestClass {
+
+    public static void main(String[] args) {
+      new C();
+      new C(new Message("A"));
+      new C(new Message("B"), new Message("C"));
+    }
+  }
+
+  static class C {
+
+    public C() {}
+
+    public C(Message message) {}
+
+    public C(Message message, Message other) {
+      System.out.println(other.value);
+    }
+  }
+
+  static class Message {
+
+    public final String value;
+
+    public Message(String value) {
+      this.value = value;
+    }
+  }
+}