diff --git a/src/main/java/com/android/tools/r8/Version.java b/src/main/java/com/android/tools/r8/Version.java
index ad42fab..6d50dfe 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.66";
+  public static final String LABEL = "1.5.67";
 
   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 92e16c3..46e0256 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
@@ -7,9 +7,12 @@
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexClass;
+import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.utils.MethodSignatureEquivalence;
+import com.google.common.base.Predicates;
+import java.util.function.Predicate;
 
 // Per-class collection of method signatures.
 //
@@ -28,8 +31,21 @@
 // TODO(b/66369976): to determine if a certain method can be made `final`.
 public class MethodPoolCollection extends MemberPoolCollection<DexMethod> {
 
+  private final Predicate<DexEncodedMethod> methodTester;
+
   public MethodPoolCollection(AppView<? extends AppInfoWithSubtyping> appView) {
     super(appView, MethodSignatureEquivalence.get());
+    this.methodTester = Predicates.alwaysTrue();
+  }
+
+  public MethodPoolCollection(
+      AppView<? extends  AppInfoWithSubtyping> appView, Predicate<DexEncodedMethod> methodTester) {
+    super(appView, MethodSignatureEquivalence.get());
+    this.methodTester = methodTester;
+  }
+
+  public static boolean excludesPrivateInstanceMethod(DexEncodedMethod method) {
+    return !method.isPrivateMethod() || method.isStatic();
   }
 
   @Override
@@ -39,8 +55,7 @@
           memberPools.computeIfAbsent(clazz, k -> new MemberPool<>(equivalence));
       clazz.forEachMethod(
           encodedMethod -> {
-            // We will add private instance methods when we promote them.
-            if (!encodedMethod.isPrivateMethod() || encodedMethod.isStatic()) {
+            if (methodTester.test(encodedMethod)) {
               methodPool.seen(equivalence.wrap(encodedMethod.method));
             }
           });
diff --git a/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java b/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java
index a1006fe..329a051 100644
--- a/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java
+++ b/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java
@@ -37,7 +37,9 @@
       DexApplication application, AppView<AppInfoWithLiveness> appView) {
     this.application = application;
     this.appView = appView;
-    this.methodPoolCollection = new MethodPoolCollection(appView);
+    this.methodPoolCollection =
+        // We will add private instance methods when we promote them.
+        new MethodPoolCollection(appView, MethodPoolCollection::excludesPrivateInstanceMethod);
   }
 
   /**
diff --git a/src/test/java/com/android/tools/r8/TestShrinkerBuilder.java b/src/test/java/com/android/tools/r8/TestShrinkerBuilder.java
index 3dd711d..8db2c33 100644
--- a/src/test/java/com/android/tools/r8/TestShrinkerBuilder.java
+++ b/src/test/java/com/android/tools/r8/TestShrinkerBuilder.java
@@ -132,6 +132,17 @@
     return self();
   }
 
+  public T allowAccessModification() {
+    return allowAccessModification(true);
+  }
+
+  public T allowAccessModification(boolean allowAccessModification) {
+    if (allowAccessModification) {
+      return addKeepRules("-allowaccessmodification");
+    }
+    return self();
+  }
+
   public T addKeepAttributes(String... attributes) {
     return addKeepRules("-keepattributes " + String.join(",", attributes));
   }
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/uninstantiatedtypes/PrivateInstanceMethodCollisionTest.java b/src/test/java/com/android/tools/r8/ir/optimize/uninstantiatedtypes/PrivateInstanceMethodCollisionTest.java
new file mode 100644
index 0000000..c790d0a
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/uninstantiatedtypes/PrivateInstanceMethodCollisionTest.java
@@ -0,0 +1,132 @@
+// 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 static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotEquals;
+
+import com.android.tools.r8.NeverClassInline;
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.utils.BooleanUtils;
+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.FoundMethodSubject;
+import com.android.tools.r8.utils.codeinspector.MethodSubject;
+import java.util.List;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class PrivateInstanceMethodCollisionTest extends TestBase {
+
+  private final TestParameters parameters;
+  private final boolean minification;
+  private final boolean allowAccessModification;
+
+  @Parameters(name = "{0}, minification: {1}, allowaccessmodification: {2}")
+  public static List<Object[]> data() {
+    return buildParameters(
+        getTestParameters().withAllRuntimes().build(),
+        BooleanUtils.values(),
+        BooleanUtils.values());
+  }
+
+  public PrivateInstanceMethodCollisionTest(
+      TestParameters parameters, boolean minification, boolean allowAccessModification) {
+    this.parameters = parameters;
+    this.minification = minification;
+    this.allowAccessModification = allowAccessModification;
+  }
+
+  @Test
+  public void b139769782() throws Exception {
+    String expectedOutput = StringUtils.lines("A#foo(B)", "A#foo(B, Object)");
+
+    if (parameters.isCfRuntime() && !minification && !allowAccessModification) {
+      testForJvm()
+          .addTestClasspath()
+          .run(parameters.getRuntime(), TestClass.class)
+          .assertSuccessWithOutput(expectedOutput);
+    }
+
+    testForR8(parameters.getBackend())
+        .addInnerClasses(PrivateInstanceMethodCollisionTest.class)
+        .addKeepMainRule(TestClass.class)
+        .enableInliningAnnotations()
+        .enableClassInliningAnnotations()
+        .minification(minification)
+        .allowAccessModification(allowAccessModification)
+        .setMinApi(parameters.getRuntime())
+        .compile()
+        .inspect(this::verifyUninstantiatedArgumentsRemovedAndNoCollisions)
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutput(expectedOutput);
+  }
+
+  private void verifyUninstantiatedArgumentsRemovedAndNoCollisions(CodeInspector inspector) {
+    ClassSubject aClassSubject = inspector.clazz(A.class);
+    assertThat(aClassSubject, isPresent());
+
+    if (allowAccessModification) {
+      assertEquals(2, aClassSubject.allMethods(FoundMethodSubject::isVirtual).size());
+      String name = null;
+      for (FoundMethodSubject m : aClassSubject.allMethods(FoundMethodSubject::isVirtual)) {
+        assertEquals(1, m.getMethod().method.proto.parameters.size());
+        if (name == null) {
+          name = m.getFinalName();
+        } else {
+          assertNotEquals(name, m.getFinalName());
+        }
+      }
+    } else {
+      assertEquals(1, aClassSubject.allMethods(FoundMethodSubject::isPrivate).size());
+      MethodSubject privateFoo = aClassSubject.allMethods(FoundMethodSubject::isPrivate).get(0);
+      assertThat(privateFoo, isPresent());
+
+      assertEquals(1, aClassSubject.allMethods(FoundMethodSubject::isVirtual).size());
+      MethodSubject virtualFoo = aClassSubject.allMethods(FoundMethodSubject::isVirtual).get(0);
+      assertThat(virtualFoo, isPresent());
+
+      assertNotEquals(privateFoo.getFinalName(), virtualFoo.getFinalName());
+    }
+  }
+
+  static class TestClass {
+    public static void main(String... args) {
+      A obj = new A();
+      B b = new B();
+      obj.foo(b);
+      obj.foo(b, null);
+    }
+  }
+
+  @NeverClassInline
+  static class A {
+    @NeverInline
+    private void foo(B instantiated) {
+      System.out.println("A#foo(" + instantiated + ")");
+    }
+
+    @NeverInline
+    void foo(B instantiated, C uninstantiated) {
+      System.out.println("A#foo(" + instantiated + ", Object)");
+    }
+  }
+
+  static class B {
+    @Override
+    public String toString() {
+      return "B";
+    }
+  }
+
+  static class C {}
+}
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/unusedarguments/PrivateInstanceMethodCollisionTest.java b/src/test/java/com/android/tools/r8/ir/optimize/unusedarguments/PrivateInstanceMethodCollisionTest.java
new file mode 100644
index 0000000..25797a1
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/unusedarguments/PrivateInstanceMethodCollisionTest.java
@@ -0,0 +1,122 @@
+// 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 static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotEquals;
+
+import com.android.tools.r8.NeverClassInline;
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.utils.BooleanUtils;
+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.FoundMethodSubject;
+import com.android.tools.r8.utils.codeinspector.MethodSubject;
+import java.util.List;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class PrivateInstanceMethodCollisionTest extends TestBase {
+
+  private final TestParameters parameters;
+  private final boolean minification;
+  private final boolean allowAccessModification;
+
+  @Parameters(name = "{0}, minification: {1}, allowaccessmodification: {2}")
+  public static List<Object[]> data() {
+    return buildParameters(
+        getTestParameters().withAllRuntimes().build(),
+        BooleanUtils.values(),
+        BooleanUtils.values());
+  }
+
+  public PrivateInstanceMethodCollisionTest(
+      TestParameters parameters, boolean minification, boolean allowAccessModification) {
+    this.parameters = parameters;
+    this.minification = minification;
+    this.allowAccessModification = allowAccessModification;
+  }
+
+  @Test
+  public void b139769782() throws Exception {
+    String expectedOutput = StringUtils.lines("A#foo(used)", "A#foo(used, Object)");
+
+    if (parameters.isCfRuntime() && !minification && !allowAccessModification) {
+      testForJvm()
+          .addTestClasspath()
+          .run(parameters.getRuntime(), TestClass.class)
+          .assertSuccessWithOutput(expectedOutput);
+    }
+
+    testForR8(parameters.getBackend())
+        .addInnerClasses(PrivateInstanceMethodCollisionTest.class)
+        .addKeepMainRule(TestClass.class)
+        .enableInliningAnnotations()
+        .enableClassInliningAnnotations()
+        .minification(minification)
+        .allowAccessModification(allowAccessModification)
+        .setMinApi(parameters.getRuntime())
+        .compile()
+        .inspect(this::verifyUnusedArgumentsRemovedAndNoCollisions)
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutput(expectedOutput);
+  }
+
+  private void verifyUnusedArgumentsRemovedAndNoCollisions(CodeInspector inspector) {
+    ClassSubject aClassSubject = inspector.clazz(A.class);
+    assertThat(aClassSubject, isPresent());
+
+    if (allowAccessModification) {
+      assertEquals(2, aClassSubject.allMethods(FoundMethodSubject::isVirtual).size());
+      String name = null;
+      for (FoundMethodSubject m : aClassSubject.allMethods(FoundMethodSubject::isVirtual)) {
+        assertEquals(1, m.getMethod().method.proto.parameters.size());
+        if (name == null) {
+          name = m.getFinalName();
+        } else {
+          assertNotEquals(name, m.getFinalName());
+        }
+      }
+    } else {
+      assertEquals(1, aClassSubject.allMethods(FoundMethodSubject::isPrivate).size());
+      MethodSubject privateFoo = aClassSubject.allMethods(FoundMethodSubject::isPrivate).get(0);
+      assertThat(privateFoo, isPresent());
+
+      assertEquals(1, aClassSubject.allMethods(FoundMethodSubject::isVirtual).size());
+      MethodSubject virtualFoo = aClassSubject.allMethods(FoundMethodSubject::isVirtual).get(0);
+      assertThat(virtualFoo, isPresent());
+
+      assertNotEquals(privateFoo.getFinalName(), virtualFoo.getFinalName());
+    }
+  }
+
+  static class TestClass {
+    public static void main(String... args) {
+      A obj = new A();
+      obj.foo("used");
+      obj.foo("used", null);
+    }
+  }
+
+  @NeverClassInline
+  static class A {
+    @NeverInline
+    private void foo(String used) {
+      System.out.println("A#foo(" + used + ")");
+    }
+
+    @NeverInline
+    void foo(String used, Object unused) {
+      System.out.println("A#foo(" + used + ", Object)");
+    }
+  }
+}