Publicize private instance methods to public instance methods, phase 1.

Collected method signatures in parallel first. Then, visited interfaces
and classes in a hierarchical order, and check if private instance
methods do not have any conflicts. If so, publicize them.
Those with resolution conflicts could be further publicized with
renaming, which will be phase 2.

Bug: 72109068
Change-Id: If580ef136127932e7c831a1442eccd692891e6f9
diff --git a/src/main/java/com/android/tools/r8/R8.java b/src/main/java/com/android/tools/r8/R8.java
index 13f2404..3d2cc25 100644
--- a/src/main/java/com/android/tools/r8/R8.java
+++ b/src/main/java/com/android/tools/r8/R8.java
@@ -320,16 +320,17 @@
         timing.end();
       }
 
+      GraphLense graphLense = GraphLense.getIdentityLense();
+
       if (options.proguardConfiguration.isAccessModificationAllowed()) {
-        ClassAndMemberPublicizer.run(application, appInfo.dexItemFactory);
+        graphLense = ClassAndMemberPublicizer.run(
+            executorService, timing, application, appInfo, rootSet, graphLense);
         // We can now remove visibility bridges. Note that we do not need to update the
         // invoke-targets here, as the existing invokes will simply dispatch to the now
         // visible super-method. MemberRebinding, if run, will then dispatch it correctly.
         application = new VisibilityBridgeRemover(appInfo, application).run();
       }
 
-      GraphLense graphLense = GraphLense.getIdentityLense();
-
       if (appInfo.hasLiveness()) {
         if (options.proguardConfiguration.hasApplyMappingFile()) {
           SeedMapper seedMapper =
diff --git a/src/main/java/com/android/tools/r8/graph/DexClass.java b/src/main/java/com/android/tools/r8/graph/DexClass.java
index 2c188da..64c85f3 100644
--- a/src/main/java/com/android/tools/r8/graph/DexClass.java
+++ b/src/main/java/com/android/tools/r8/graph/DexClass.java
@@ -13,6 +13,7 @@
 import com.google.common.collect.Iterators;
 import java.util.Arrays;
 import java.util.List;
+import java.util.Set;
 import java.util.function.Consumer;
 
 public abstract class DexClass extends DexItem {
@@ -158,6 +159,32 @@
     return result;
   }
 
+  public void virtualizeMethods(Set<DexEncodedMethod> privateInstanceMethods) {
+    int vLen = virtualMethods.length;
+    int dLen = directMethods.length;
+    int mLen = privateInstanceMethods.size();
+    assert mLen <= dLen;
+
+    DexEncodedMethod[] newDirectMethods = new DexEncodedMethod[dLen - mLen];
+    int index = 0;
+    for (int i = 0; i < dLen; i++) {
+      DexEncodedMethod encodedMethod = directMethods[i];
+      if (!privateInstanceMethods.contains(encodedMethod)) {
+        newDirectMethods[index++] = encodedMethod;
+      }
+    }
+    assert index == dLen - mLen;
+    setDirectMethods(newDirectMethods);
+
+    DexEncodedMethod[] newVirtualMethods = new DexEncodedMethod[vLen + mLen];
+    System.arraycopy(virtualMethods, 0, newVirtualMethods, 0, vLen);
+    index = vLen;
+    for (DexEncodedMethod encodedMethod : privateInstanceMethods) {
+      newVirtualMethods[index++] = encodedMethod;
+    }
+    setVirtualMethods(newVirtualMethods);
+  }
+
   /**
    * For all annotations on the class and all annotations on its methods and fields apply the
    * specified consumer.
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 83cb824..845eecd 100644
--- a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
+++ b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
@@ -160,6 +160,10 @@
     return isVirtualMethod() && !accessFlags.isAbstract();
   }
 
+  public boolean isPublicized() {
+    return optimizationInfo.isPublicized();
+  }
+
   public boolean isPublicMethod() {
     return accessFlags.isPublic();
   }
@@ -669,6 +673,7 @@
     private boolean neverReturnsNormally = false;
     private boolean returnsConstant = false;
     private long returnedConstant = 0;
+    private boolean publicized = false;
     private boolean forceInline = false;
     private boolean useIdentifierNameString = false;
     private boolean checksNullReceiverBeforeAnySideEffect = false;
@@ -689,6 +694,7 @@
       neverReturnsNull = template.neverReturnsNull;
       returnsConstant = template.returnsConstant;
       returnedConstant = template.returnedConstant;
+      publicized = template.publicized;
       forceInline = template.forceInline;
       useIdentifierNameString = template.useIdentifierNameString;
       checksNullReceiverBeforeAnySideEffect = template.checksNullReceiverBeforeAnySideEffect;
@@ -752,6 +758,10 @@
       return returnedConstant;
     }
 
+    public boolean isPublicized() {
+      return publicized;
+    }
+
     public boolean forceInline() {
       return forceInline;
     }
@@ -792,6 +802,10 @@
       forceInline = true;
     }
 
+    private void markPublicized() {
+      publicized = true;
+    }
+
     private void markUseIdentifierNameString() {
       useIdentifierNameString = true;
     }
@@ -865,6 +879,10 @@
     ensureMutableOI().markForceInline();
   }
 
+  synchronized public void markPublicized() {
+    ensureMutableOI().markPublicized();
+  }
+
   synchronized public void markUseIdentifierNameString() {
     ensureMutableOI().markUseIdentifierNameString();
   }
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 297dd57..eaeb1ee 100644
--- a/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java
+++ b/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java
@@ -3,65 +3,179 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.optimize;
 
+import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.DexApplication;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexEncodedMethod;
-import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.GraphLense;
 import com.android.tools.r8.graph.MethodAccessFlags;
+import com.android.tools.r8.optimize.PublicizerLense.PublicizedLenseBuilder;
+import com.android.tools.r8.shaking.RootSetBuilder.RootSet;
+import com.android.tools.r8.utils.MethodSignatureEquivalence;
+import com.android.tools.r8.utils.ThreadUtils;
+import com.android.tools.r8.utils.Timing;
+import com.google.common.base.Equivalence;
+import com.google.common.base.Equivalence.Wrapper;
+import com.google.common.collect.Sets;
+import java.util.ArrayList;
+import java.util.LinkedHashSet;
+import java.util.List;
+import java.util.Set;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.ExecutorService;
+import java.util.concurrent.Future;
 
 public final class ClassAndMemberPublicizer {
-  private final DexItemFactory factory;
   private final DexApplication application;
+  private final AppInfo appInfo;
+  private final RootSet rootSet;
+  private final GraphLense previuosLense;
+  private final PublicizedLenseBuilder lenseBuilder;
 
-  private ClassAndMemberPublicizer(DexApplication application, DexItemFactory factory) {
+  private final Equivalence<DexMethod> equivalence = MethodSignatureEquivalence.get();
+  // TODO(b/72109068): finer-grained naming spaces, e.g., per-tree.
+  private final Set<Wrapper<DexMethod>> methodPool = Sets.newConcurrentHashSet();
+
+  private ClassAndMemberPublicizer(
+      DexApplication application,
+      AppInfo appInfo,
+      RootSet rootSet,
+      GraphLense previousLense) {
     this.application = application;
-    this.factory = factory;
+    this.appInfo = appInfo;
+    this.rootSet = rootSet;
+    this.previuosLense = previousLense;
+    lenseBuilder = PublicizerLense.createBuilder();
   }
 
   /**
-   * Marks all package private and protected methods and fields as public. Also makes
-   * all private static methods public.
+   * Marks all package private and protected methods and fields as public.
+   * Makes all private static methods public.
+   * Makes private instance methods public final instance methods, if possible.
    * <p>
    * This will destructively update the DexApplication passed in as argument.
    */
-  public static DexApplication run(DexApplication application, DexItemFactory factory) {
-    return new ClassAndMemberPublicizer(application, factory).run();
+  public static GraphLense run(
+      ExecutorService executorService,
+      Timing timing,
+      DexApplication application,
+      AppInfo appInfo,
+      RootSet rootSet,
+      GraphLense previousLense) throws ExecutionException {
+    return new ClassAndMemberPublicizer(application, appInfo, rootSet, previousLense)
+        .run(executorService, timing);
   }
 
-  private DexApplication run() {
-    for (DexClass clazz : application.classes()) {
+  private GraphLense run(ExecutorService executorService, Timing timing)
+      throws ExecutionException {
+    // Phase 1: Collect methods to check if private instance methods don't have conflicts.
+    timing.begin("Phase 1: collectMethods");
+    try {
+      List<Future<?>> futures = new ArrayList<>();
+      // TODO(b/72109068): finer-grained naming spaces will need a different class visiting.
+      application.classes().forEach(clazz ->
+          futures.add(executorService.submit(collectMethodPerClass(clazz))));
+      ThreadUtils.awaitFutures(futures);
+    } finally {
+      timing.end();
+    }
+
+    // Phase 2: Visit classes and promote class/member to public if possible.
+    timing.begin("Phase 2: promoteToPublic");
+    DexType.forAllInterfaces(appInfo.dexItemFactory, this::publicizeType);
+    publicizeType(appInfo.dexItemFactory.objectType);
+    timing.end();
+
+    return lenseBuilder.build(appInfo, previuosLense);
+  }
+
+  private Runnable collectMethodPerClass(DexClass clazz) {
+    return () -> {
+      clazz.forEachMethod(encodedMethod -> {
+        // We will add private instance methods when we promote them.
+        if (!encodedMethod.isPrivateMethod() || encodedMethod.isStaticMethod()) {
+          methodPool.add(equivalence.wrap(encodedMethod.method));
+        }
+      });
+    };
+  }
+
+  private void publicizeType(DexType type) {
+    DexClass clazz = application.definitionFor(type);
+    if (clazz != null && clazz.isProgramClass()) {
       clazz.accessFlags.promoteToPublic();
-      clazz.forEachMethod(this::publicizeMethod);
       clazz.forEachField(field -> field.accessFlags.promoteToPublic());
+      Set<DexEncodedMethod> privateInstanceEncodedMethods = new LinkedHashSet<>();
+      clazz.forEachMethod(encodedMethod -> {
+        if (publicizeMethod(clazz, encodedMethod)) {
+          privateInstanceEncodedMethods.add(encodedMethod);
+        }
+      });
+      if (!privateInstanceEncodedMethods.isEmpty()) {
+        clazz.virtualizeMethods(privateInstanceEncodedMethods);
+      }
     }
-    return application;
+
+    // TODO(b/72109068): Can process sub types in parallel.
+    type.forAllExtendsSubtypes(this::publicizeType);
   }
 
-  private void publicizeMethod(DexEncodedMethod method) {
-    MethodAccessFlags accessFlags = method.accessFlags;
+  private boolean publicizeMethod(DexClass holder, DexEncodedMethod encodedMethod) {
+    MethodAccessFlags accessFlags = encodedMethod.accessFlags;
     if (accessFlags.isPublic()) {
-      return;
+      return false;
     }
 
-    if (factory.isClassConstructor(method.method)) {
-      return;
+    if (appInfo.dexItemFactory.isClassConstructor(encodedMethod.method)) {
+      return false;
     }
 
     if (!accessFlags.isPrivate()) {
       accessFlags.unsetProtected();
       accessFlags.setPublic();
-      return;
+      return false;
     }
     assert accessFlags.isPrivate();
 
-    if (factory.isConstructor(method.method)) {
-      // TODO: b/72211928
-      return;
+    if (appInfo.dexItemFactory.isConstructor(encodedMethod.method)) {
+      // TODO(b/72211928)
+      return false;
     }
 
     if (!accessFlags.isStatic()) {
-      // TODO: b/72109068
-      return;
+      // If this method is mentioned in keep rules, do not transform (rule applications changed).
+      if (rootSet.noShrinking.containsKey(encodedMethod)) {
+        return false;
+      }
+
+      // We can't publicize private instance methods in interfaces or methods that are copied from
+      // interfaces to lambda-desugared classes because this will be added as a new default method.
+      // TODO(b/72109068): It might be possible to transform it into static methods, though.
+      if (holder.isInterface() || accessFlags.isSynthetic()) {
+        return false;
+      }
+
+      Wrapper<DexMethod> key = equivalence.wrap(encodedMethod.method);
+      if (methodPool.contains(key)) {
+        // We can't do anything further because even renaming is not allowed due to the keep rule.
+        if (rootSet.noObfuscation.contains(encodedMethod)) {
+          return false;
+        }
+        // TODO(b/72109068): Renaming will enable more private instance methods to be publicized.
+        return false;
+      }
+      methodPool.add(key);
+      lenseBuilder.add(encodedMethod.method);
+      accessFlags.unsetPrivate();
+      accessFlags.setFinal();
+      accessFlags.setPublic();
+      // Although the current method became public, it surely has the single virtual target.
+      encodedMethod.method.setSingleVirtualMethodCache(
+          encodedMethod.method.getHolder(), encodedMethod);
+      encodedMethod.markPublicized();
+      return true;
     }
 
     // For private static methods we can just relax the access to private, since
@@ -70,5 +184,6 @@
     // does not take into account access of the static methods.
     accessFlags.unsetPrivate();
     accessFlags.setPublic();
+    return false;
   }
 }
diff --git a/src/main/java/com/android/tools/r8/optimize/PublicizerLense.java b/src/main/java/com/android/tools/r8/optimize/PublicizerLense.java
new file mode 100644
index 0000000..835135e
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/optimize/PublicizerLense.java
@@ -0,0 +1,68 @@
+// Copyright (c) 2018, 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.optimize;
+
+import com.android.tools.r8.graph.AppInfo;
+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.GraphLense;
+import com.android.tools.r8.graph.GraphLense.NestedGraphLense;
+import com.android.tools.r8.ir.code.Invoke.Type;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSet;
+import java.util.Set;
+
+final class PublicizerLense extends NestedGraphLense {
+  private final AppInfo appInfo;
+  private final Set<DexMethod> publicizedMethods;
+
+  PublicizerLense(
+      AppInfo appInfo, GraphLense previousLense, Set<DexMethod> publicizedMethods) {
+    // This lense does not map any DexItem's at all.
+    // It will just tweak invoke type for publicized methods from invoke-direct to invoke-virtual.
+    super(ImmutableMap.of(), ImmutableMap.of(), ImmutableMap.of(),
+        previousLense, appInfo.dexItemFactory);
+    this.appInfo = appInfo;
+    this.publicizedMethods = publicizedMethods;
+  }
+
+  @Override
+  public GraphLenseLookupResult lookupMethod(
+      DexMethod method, DexEncodedMethod context, Type type) {
+    GraphLenseLookupResult previous = previousLense.lookupMethod(method, context, type);
+    method = previous.getMethod();
+    type = previous.getType();
+    if (type == Type.DIRECT && publicizedMethods.contains(method)) {
+      DexClass holderClass = appInfo.definitionFor(method.holder);
+      if (holderClass != null) {
+        DexEncodedMethod actualEncodedTarget = holderClass.lookupVirtualMethod(method);
+        if (actualEncodedTarget != null
+            && actualEncodedTarget.isPublicized()) {
+          return new GraphLenseLookupResult(method, Type.VIRTUAL);
+        }
+      }
+    }
+    return super.lookupMethod(method, context, type);
+  }
+
+  static PublicizedLenseBuilder createBuilder() {
+    return new PublicizedLenseBuilder();
+  }
+
+  static class PublicizedLenseBuilder {
+    private final ImmutableSet.Builder<DexMethod> methodSetBuilder = ImmutableSet.builder();
+
+    private PublicizedLenseBuilder() {
+    }
+
+    public GraphLense build(AppInfo appInfo, GraphLense previousLense) {
+      return new PublicizerLense(appInfo, previousLense, methodSetBuilder.build());
+    }
+
+    public void add(DexMethod publicizedMethod) {
+      methodSetBuilder.add(publicizedMethod);
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/accessrelaxation/AccessRelaxationTest.java b/src/test/java/com/android/tools/r8/accessrelaxation/AccessRelaxationTest.java
index 34b92b0..027b7e8 100644
--- a/src/test/java/com/android/tools/r8/accessrelaxation/AccessRelaxationTest.java
+++ b/src/test/java/com/android/tools/r8/accessrelaxation/AccessRelaxationTest.java
@@ -4,35 +4,89 @@
 
 package com.android.tools.r8.accessrelaxation;
 
+import static com.android.tools.r8.utils.DexInspectorMatchers.isPresent;
+import static com.android.tools.r8.utils.DexInspectorMatchers.isPublic;
+import static org.hamcrest.CoreMatchers.not;
 import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertThat;
 
 import com.android.tools.r8.DexIndexedConsumer;
 import com.android.tools.r8.R8Command;
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.VmTestRunner;
+import com.android.tools.r8.accessrelaxation.privateinstance.Base;
+import com.android.tools.r8.accessrelaxation.privateinstance.Sub1;
+import com.android.tools.r8.accessrelaxation.privateinstance.Sub2;
+import com.android.tools.r8.accessrelaxation.privateinstance.TestMain;
 import com.android.tools.r8.accessrelaxation.privatestatic.A;
 import com.android.tools.r8.accessrelaxation.privatestatic.B;
 import com.android.tools.r8.accessrelaxation.privatestatic.BB;
 import com.android.tools.r8.accessrelaxation.privatestatic.C;
+import com.android.tools.r8.naming.MemberNaming.MethodSignature;
 import com.android.tools.r8.origin.Origin;
 import com.android.tools.r8.utils.AndroidApp;
+import com.android.tools.r8.utils.DexInspector;
+import com.android.tools.r8.utils.DexInspector.ClassSubject;
+import com.android.tools.r8.utils.DexInspector.MethodSubject;
 import com.google.common.collect.ImmutableList;
 import org.junit.Test;
+import org.junit.runner.RunWith;
 
+@RunWith(VmTestRunner.class)
 public class AccessRelaxationTest extends TestBase {
-  @Test
-  public void testStaticMethodRelaxation() throws Exception {
+  private static final String STRING = "java.lang.String";
+
+  private static R8Command.Builder loadProgramFiles(Package p, Class... classes) throws Exception {
     R8Command.Builder builder = R8Command.builder();
-    builder.addProgramFiles(ToolHelper.getClassFilesForTestPackage(A.class.getPackage()));
+    builder.addProgramFiles(ToolHelper.getClassFilesForTestPackage(p));
+    for (Class clazz : classes) {
+      builder.addProgramFiles(ToolHelper.getClassFileForTestClass(clazz));
+    }
     builder.setProgramConsumer(DexIndexedConsumer.emptyConsumer());
     builder.setMinApiLevel(ToolHelper.getMinApiLevelForDexVm().getLevel());
+    return builder;
+  }
+
+  private void compareJvmAndArt(AndroidApp app, Class mainClass) throws Exception {
+    // Run on Jvm.
+    String jvmOutput = runOnJava(mainClass);
+
+    // Run on Art to check generated code against verifier.
+    String artOutput = runOnArt(app, mainClass);
+
+    String adjustedArtOutput = artOutput.replace(
+        "java.lang.IncompatibleClassChangeError", "java.lang.IllegalAccessError");
+    assertEquals(jvmOutput, adjustedArtOutput);
+  }
+
+  private static void assertPublic(
+      DexInspector dexInspector, Class clazz, MethodSignature signature) {
+    ClassSubject classSubject = dexInspector.clazz(clazz);
+    assertThat(classSubject, isPresent());
+    MethodSubject methodSubject = classSubject.method(signature);
+    assertThat(methodSubject, isPublic());
+  }
+
+  private static void assertNotPublic(
+      DexInspector dexInspector, Class clazz, MethodSignature signature) {
+    ClassSubject classSubject = dexInspector.clazz(clazz);
+    assertThat(classSubject, isPresent());
+    MethodSubject methodSubject = classSubject.method(signature);
+    assertThat(methodSubject, not(isPublic()));
+  }
+
+  @Test
+  public void testStaticMethodRelaxation() throws Exception {
+    Class mainClass = C.class;
+    R8Command.Builder builder = loadProgramFiles(mainClass.getPackage());
 
     // Note: we use '-checkdiscard' to indirectly check that the access relaxation is
     // done which leads to inlining of all pB*** methods so they are removed. Without
     // access relaxation inlining is not performed and method are kept.
     builder.addProguardConfiguration(
         ImmutableList.of(
-            "-keep class " + C.class.getCanonicalName() + "{",
+            "-keep class " + mainClass.getCanonicalName() + "{",
             "  public static void main(java.lang.String[]);",
             "}",
             "",
@@ -57,15 +111,71 @@
         Origin.unknown());
 
     AndroidApp app = ToolHelper.runR8(builder.build());
+    compareJvmAndArt(app, mainClass);
 
-    // Run on Jvm.
-    String jvmOutput = runOnJava(C.class);
+    DexInspector dexInspector = new DexInspector(app);
+    assertPublic(dexInspector, A.class,
+        new MethodSignature("baz", STRING, ImmutableList.of()));
+    assertPublic(dexInspector, A.class,
+        new MethodSignature("bar", STRING, ImmutableList.of()));
+    assertPublic(dexInspector, A.class,
+        new MethodSignature("bar", STRING, ImmutableList.of("int")));
+    assertPublic(dexInspector, A.class,
+        new MethodSignature("blah", STRING, ImmutableList.of("int")));
 
-    // Run on Art to check generated code against verifier.
-    String artOutput = runOnArt(app, C.class);
+    assertPublic(dexInspector, B.class,
+        new MethodSignature("blah", STRING, ImmutableList.of("int")));
 
-    String adjustedArtOutput = artOutput.replace(
-        "java.lang.IncompatibleClassChangeError", "java.lang.IllegalAccessError");
-    assertEquals(jvmOutput, adjustedArtOutput);
+    assertPublic(dexInspector, BB.class,
+        new MethodSignature("blah", STRING, ImmutableList.of("int")));
+  }
+
+  @Test
+  public void testInstanceMethodRelaxation() throws Exception {
+    Class mainClass = TestMain.class;
+    R8Command.Builder builder = loadProgramFiles(mainClass.getPackage());
+
+    builder.addProguardConfiguration(
+        ImmutableList.of(
+            "-keep class " + mainClass.getCanonicalName() + "{",
+            "  public static void main(java.lang.String[]);",
+            "}",
+            "",
+            "-checkdiscard class " + Base.class.getCanonicalName() + "{",
+            "  *** p*();",
+            "}",
+            "",
+            "-checkdiscard class " + Sub1.class.getCanonicalName() + "{",
+            "  *** p*();",
+            "}",
+            "",
+            "-checkdiscard class " + Sub2.class.getCanonicalName() + "{",
+            "  *** p*();",
+            "}",
+            "",
+            "-dontobfuscate",
+            "-allowaccessmodification"
+        ),
+        Origin.unknown());
+
+    AndroidApp app = ToolHelper.runR8(builder.build());
+    compareJvmAndArt(app, mainClass);
+
+    DexInspector dexInspector = new DexInspector(app);
+    assertPublic(dexInspector, Base.class,
+        new MethodSignature("foo", STRING, ImmutableList.of()));
+
+    // Base#foo?() can't be publicized due to Itf<1>#foo<1>().
+    assertNotPublic(dexInspector, Base.class,
+        new MethodSignature("foo1", STRING, ImmutableList.of()));
+    assertNotPublic(dexInspector, Base.class,
+        new MethodSignature("foo2", STRING, ImmutableList.of()));
+
+    // Sub1#bar1(int) can't be publicized due to Base#bar1(int).
+    assertNotPublic(dexInspector, Sub1.class,
+        new MethodSignature("bar1", STRING, ImmutableList.of("int")));
+
+    assertPublic(dexInspector, Sub2.class,
+        new MethodSignature("bar2", STRING, ImmutableList.of("int")));
   }
 }
diff --git a/src/test/java/com/android/tools/r8/accessrelaxation/InvokeTypeConversionTest.java b/src/test/java/com/android/tools/r8/accessrelaxation/InvokeTypeConversionTest.java
new file mode 100644
index 0000000..fce1f4c
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/accessrelaxation/InvokeTypeConversionTest.java
@@ -0,0 +1,143 @@
+// Copyright (c) 2018, 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.accessrelaxation;
+
+import static com.android.tools.r8.utils.DexInspectorMatchers.isPresent;
+import static org.hamcrest.CoreMatchers.containsString;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertThat;
+import static org.junit.Assert.assertTrue;
+
+import com.android.tools.r8.R8Command;
+import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.ToolHelper.ProcessResult;
+import com.android.tools.r8.VmTestRunner;
+import com.android.tools.r8.code.InvokeDirect;
+import com.android.tools.r8.code.InvokeVirtual;
+import com.android.tools.r8.graph.DexCode;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.origin.Origin;
+import com.android.tools.r8.smali.SmaliBuilder;
+import com.android.tools.r8.smali.SmaliBuilder.MethodSignature;
+import com.android.tools.r8.smali.SmaliTestBase;
+import com.android.tools.r8.utils.AndroidApp;
+import com.android.tools.r8.utils.DexInspector;
+import com.android.tools.r8.utils.DexInspector.ClassSubject;
+import com.google.common.collect.ImmutableList;
+import java.util.List;
+import java.util.function.Consumer;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+
+@RunWith(VmTestRunner.class)
+public class InvokeTypeConversionTest extends SmaliTestBase {
+  private final String CLASS_NAME = "Example";
+  private MethodSignature main;
+
+  private SmaliBuilder buildTestClass(String invokeLine) {
+    SmaliBuilder builder = new SmaliBuilder(CLASS_NAME);
+    builder.addDefaultConstructor();
+    builder.addPrivateInstanceMethod("int", "foo", ImmutableList.of(), 1,
+        "  const/4 v0, 0",
+        "  return v0");
+    builder.addPrivateStaticMethod("int", "bar", ImmutableList.of(), 1,
+        "  const/4 v0, 0",
+        "  return v0");
+    main = builder.addMainMethod(2,
+        "new-instance v1, L" + CLASS_NAME + ";",
+        "invoke-direct { v1 }, L" + CLASS_NAME + ";-><init>()V",
+        invokeLine,
+        "move-result v1",
+        "invoke-static { v1 }, Ljava/lang/Integer;->valueOf(I)Ljava/lang/Integer;",
+        "move-result-object v1",
+        "sget-object v0, Ljava/lang/System;->out:Ljava/io/PrintStream;",
+        "invoke-virtual { v0, v1 }, Ljava/io/PrintStream;->print(Ljava/lang/Object;)V",
+        "return-void");
+    return builder;
+  }
+
+  private void run(
+      SmaliBuilder builder,
+      String expectedException,
+      Consumer<DexInspector> inspectorConsumer) throws Exception {
+    AndroidApp app = buildApplication(builder);
+    List<String> pgConfigs = ImmutableList.of(
+        keepMainProguardConfiguration(CLASS_NAME),
+        "-printmapping",
+        "-dontobfuscate",
+        "-allowaccessmodification");
+    R8Command.Builder command = ToolHelper.prepareR8CommandBuilder(app);
+    command.addProguardConfiguration(pgConfigs, Origin.unknown());
+    AndroidApp processedApp = ToolHelper.runR8(command.build(), o -> {
+      o.enableInlining = false;
+    });
+    ProcessResult artResult = runOnArtRaw(processedApp, CLASS_NAME);
+    if (expectedException == null) {
+      assertEquals(0, artResult.exitCode);
+      assertEquals("0", artResult.stdout);
+    } else {
+      assertEquals(1, artResult.exitCode);
+      assertThat(artResult.stderr, containsString(expectedException));
+    }
+    DexInspector inspector = new DexInspector(processedApp);
+    inspectorConsumer.accept(inspector);
+  }
+
+  // The following test checks invoke-direct, which refers to the private static method, is *not*
+  // rewritten by publicizer lense, resulting in IncompatibleClassChangeError, which is expected.
+  //
+  // class Example {
+  //   private int foo() { return 0; }
+  //   private static int bar() { return 0; }
+  //   public static void main(String[] args) {
+  //     Example instance = new Example();
+  //     "invoke-direct instance, Example->bar()"  <- should yield IncompatibleClassChangeError
+  //     ...
+  //   }
+  // }
+  @Test
+  public void invokeDirectToAlreadyStaticMethod() throws Exception {
+    SmaliBuilder builder = buildTestClass(
+        "invoke-direct { v1 }, L" + CLASS_NAME + ";->bar()I");
+    run(builder, "IncompatibleClassChangeError", dexInspector -> {
+      ClassSubject clazz = dexInspector.clazz(CLASS_NAME);
+      assertThat(clazz, isPresent());
+      DexEncodedMethod method = getMethod(dexInspector, main);
+      assertNotNull(method);
+      DexCode code = method.getCode().asDexCode();
+      // The given invoke line is remained as-is.
+      assertTrue(code.instructions[2] instanceof InvokeDirect);
+    });
+  }
+
+  // The following test checks invoke-direct, which refers to the private instance method, *is*
+  // rewritten by publicizer lense, as the target method will be publicized.
+  //
+  // class Example {
+  //   private int foo() { return 0; }
+  //   private static int bar() { return 0; }
+  //   public static void main(String[] args) {
+  //     Example instance = new Example();
+  //     instance.foo();  // which was "invoke-direct instance, Example->foo()"
+  //                      // will be "invoke-virtual instance, Example->foo()"
+  //     ...
+  //   }
+  // }
+  @Test
+  public void invokeDirectToPublicizedMethod() throws Exception {
+    SmaliBuilder builder = buildTestClass(
+        "invoke-direct { v1 }, L" + CLASS_NAME + ";->foo()I");
+    run(builder, null, dexInspector -> {
+      ClassSubject clazz = dexInspector.clazz(CLASS_NAME);
+      assertThat(clazz, isPresent());
+      DexEncodedMethod method = getMethod(dexInspector, main);
+      assertNotNull(method);
+      DexCode code = method.getCode().asDexCode();
+      // The given invoke line is changed to invoke-virtual
+      assertTrue(code.instructions[2] instanceof InvokeVirtual);
+    });
+  }
+
+}
\ No newline at end of file
diff --git a/src/test/java/com/android/tools/r8/accessrelaxation/privateinstance/Base.java b/src/test/java/com/android/tools/r8/accessrelaxation/privateinstance/Base.java
new file mode 100644
index 0000000..fd1fd1c
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/accessrelaxation/privateinstance/Base.java
@@ -0,0 +1,48 @@
+// Copyright (c) 2018, 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.accessrelaxation.privateinstance;
+
+public class Base {
+
+  // NOTE: here and below 'synchronized' is supposed to disable inlining of this method.
+  private synchronized String foo() {
+    return "Base::foo()";
+  }
+
+  public String pFoo() {
+    return foo();
+  }
+
+  private synchronized String foo1() {
+    return "Base::foo1()";
+  }
+
+  public String pFoo1() {
+    return foo1();
+  }
+
+  private synchronized String foo2() {
+    return "Base::foo2()";
+  }
+
+  public String pFoo2() {
+    return foo2();
+  }
+
+  private synchronized String bar1(int i) {
+    throw new AssertionError("Sub1#bar1(int) will not use this signature.");
+  }
+
+  public void dump() {
+    System.out.println(foo());
+    System.out.println(foo1());
+    System.out.println(foo2());
+    try {
+      bar1(0);
+    } catch (AssertionError e) {
+      // expected
+    }
+  }
+
+}
diff --git a/src/test/java/com/android/tools/r8/accessrelaxation/privateinstance/Itf1.java b/src/test/java/com/android/tools/r8/accessrelaxation/privateinstance/Itf1.java
new file mode 100644
index 0000000..bc44973
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/accessrelaxation/privateinstance/Itf1.java
@@ -0,0 +1,12 @@
+// Copyright (c) 2018, 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.accessrelaxation.privateinstance;
+
+public interface Itf1 {
+  String foo1();
+
+  default String foo1(int i) {
+    return "Itf1::foo1(" + i + ") >> " + foo1();
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/accessrelaxation/privateinstance/Itf2.java b/src/test/java/com/android/tools/r8/accessrelaxation/privateinstance/Itf2.java
new file mode 100644
index 0000000..233a327
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/accessrelaxation/privateinstance/Itf2.java
@@ -0,0 +1,12 @@
+// Copyright (c) 2018, 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.accessrelaxation.privateinstance;
+
+public interface Itf2 {
+  String foo2();
+
+  default String foo2(int i) {
+    return "Itf2::foo2(" + i + ") >> " + foo2();
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/accessrelaxation/privateinstance/Sub1.java b/src/test/java/com/android/tools/r8/accessrelaxation/privateinstance/Sub1.java
new file mode 100644
index 0000000..4cbbf11
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/accessrelaxation/privateinstance/Sub1.java
@@ -0,0 +1,32 @@
+// Copyright (c) 2018, 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.accessrelaxation.privateinstance;
+
+public class Sub1 extends Base implements Itf1 {
+
+  @Override
+  public String foo1() {
+    return "Sub1::foo1()";
+  }
+
+  private synchronized String bar1(int i) {
+    return "Sub1::bar1(" + i + ")";
+  }
+
+  public String pBar1() {
+    return bar1(1);
+  }
+
+  @Override
+  public void dump() {
+    System.out.println(foo1());
+    System.out.println(foo1(0));
+    try {
+      System.out.println(bar1(0));
+    } catch (Throwable e) {
+      System.out.println(e.getClass().getName());
+    }
+  }
+
+}
diff --git a/src/test/java/com/android/tools/r8/accessrelaxation/privateinstance/Sub2.java b/src/test/java/com/android/tools/r8/accessrelaxation/privateinstance/Sub2.java
new file mode 100644
index 0000000..8c4e01e
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/accessrelaxation/privateinstance/Sub2.java
@@ -0,0 +1,28 @@
+// Copyright (c) 2018, 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.accessrelaxation.privateinstance;
+
+public class Sub2 extends Base implements Itf2 {
+
+  @Override
+  public String foo2() {
+    return "Sub2::foo2()";
+  }
+
+  private synchronized String bar2(int i) {
+    return "Sub2::bar2(" + i + ")";
+  }
+
+  public String pBar2() {
+    return bar2(2);
+  }
+
+  @Override
+  public void dump() {
+    System.out.println(foo2());
+    System.out.println(foo2(0));
+    System.out.println(bar2(0));
+  }
+
+}
diff --git a/src/test/java/com/android/tools/r8/accessrelaxation/privateinstance/TestMain.java b/src/test/java/com/android/tools/r8/accessrelaxation/privateinstance/TestMain.java
new file mode 100644
index 0000000..bfd322b
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/accessrelaxation/privateinstance/TestMain.java
@@ -0,0 +1,13 @@
+// Copyright (c) 2018, 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.accessrelaxation.privateinstance;
+
+public class TestMain {
+
+  public static void main(String[] args) {
+    new Base().dump();
+    new Sub1().dump();
+    new Sub2().dump();
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/naming/MinifierTest.java b/src/test/java/com/android/tools/r8/naming/MinifierTest.java
index 4b42880..8a5975ea 100644
--- a/src/test/java/com/android/tools/r8/naming/MinifierTest.java
+++ b/src/test/java/com/android/tools/r8/naming/MinifierTest.java
@@ -98,10 +98,10 @@
     // method naming001.A.m should be kept, according to the keep rule.
     assertEquals("m", naming.lookupName(m).toSourceString());
 
+    // method naming001.A.privateFunc is transformed to a public method, and then kept.
     DexMethod p = dexItemFactory.createMethod(
         a, dexItemFactory.createProto(dexItemFactory.voidType), "privateFunc");
-    // method naming001.A.privateFunc would be renamed.
-    assertNotEquals("privateFunc", naming.lookupName(p).toSourceString());
+    assertEquals("privateFunc", naming.lookupName(p).toSourceString());
   }
 
   private static void test001_rule005(DexItemFactory dexItemFactory, NamingLens naming) {
diff --git a/src/test/java/com/android/tools/r8/naming/NamingTestBase.java b/src/test/java/com/android/tools/r8/naming/NamingTestBase.java
index f311c15..6d16184 100644
--- a/src/test/java/com/android/tools/r8/naming/NamingTestBase.java
+++ b/src/test/java/com/android/tools/r8/naming/NamingTestBase.java
@@ -7,6 +7,7 @@
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.DexApplication;
 import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.graph.GraphLense;
 import com.android.tools.r8.optimize.ClassAndMemberPublicizer;
 import com.android.tools.r8.shaking.Enqueuer;
 import com.android.tools.r8.shaking.ProguardConfiguration;
@@ -57,7 +58,7 @@
   }
 
   @Before
-  public void readApp() throws IOException, ExecutionException, ProguardRuleParserException {
+  public void readApp() throws IOException, ExecutionException {
     program = ToolHelper.buildApplication(ImmutableList.of(appFileName));
     dexItemFactory = program.dexItemFactory;
     appInfo = new AppInfoWithSubtyping(program);
@@ -70,13 +71,18 @@
     InternalOptions options = new InternalOptions(configuration,
         new Reporter(new DefaultDiagnosticsHandler()));
 
-    if (options.proguardConfiguration.isAccessModificationAllowed()) {
-      ClassAndMemberPublicizer.run(program, dexItemFactory);
-    }
-
     ExecutorService executor = ThreadUtils.getExecutorService(1);
+
     RootSet rootSet = new RootSetBuilder(appInfo, program, configuration.getRules(), options)
         .run(executor);
+
+    if (options.proguardConfiguration.isAccessModificationAllowed()) {
+      ClassAndMemberPublicizer.run(
+          executor, timing, program, appInfo, rootSet, GraphLense.getIdentityLense());
+      rootSet =
+          new RootSetBuilder(appInfo, program, configuration.getRules(), options).run(executor);
+    }
+
     Enqueuer enqueuer = new Enqueuer(appInfo, options, options.forceProguardCompatibility);
     appInfo = enqueuer.traceApplication(rootSet, executor, timing);
     return new Minifier(appInfo.withLiveness(), rootSet, options).run(timing);
diff --git a/src/test/java/com/android/tools/r8/neverreturnsnormally/NeverReturnsNormallyTest.java b/src/test/java/com/android/tools/r8/neverreturnsnormally/NeverReturnsNormallyTest.java
index 1f9c20f..3e46098 100644
--- a/src/test/java/com/android/tools/r8/neverreturnsnormally/NeverReturnsNormallyTest.java
+++ b/src/test/java/com/android/tools/r8/neverreturnsnormally/NeverReturnsNormallyTest.java
@@ -22,6 +22,7 @@
 import com.google.common.collect.ImmutableList;
 import java.util.Iterator;
 import java.util.function.BiConsumer;
+import org.junit.Ignore;
 import org.junit.Test;
 
 public class NeverReturnsNormallyTest extends TestBase {
@@ -127,6 +128,7 @@
     return instructions.next();
   }
 
+  @Ignore("b/110736241")
   @Test
   public void test() throws Exception {
     runTest(this::validate, CompilationMode.DEBUG);
diff --git a/src/test/java/com/android/tools/r8/smali/SmaliBuilder.java b/src/test/java/com/android/tools/r8/smali/SmaliBuilder.java
index e818801..1dffcee 100644
--- a/src/test/java/com/android/tools/r8/smali/SmaliBuilder.java
+++ b/src/test/java/com/android/tools/r8/smali/SmaliBuilder.java
@@ -257,6 +257,12 @@
     return addStaticMethod(returnType, name, parameters, locals, buildCode(instructions));
   }
 
+  public MethodSignature addPrivateStaticMethod(
+      String returnType, String name, List<String> parameters, int locals, String... instructions) {
+    return addMethod(
+        "private static", returnType, name, parameters, locals, buildCode(instructions));
+  }
+
   public MethodSignature addStaticMethod(
       String returnType, String name, List<String> parameters, int locals, String code) {
     return addStaticMethod("", returnType, name, parameters, locals, code);
@@ -301,6 +307,11 @@
         "public constructor", "void", "<init>", parameters, locals, buildCode(instructions));
   }
 
+  public MethodSignature addPrivateInstanceMethod(
+      String returnType, String name, List<String> parameters, int locals, String... instructions) {
+    return addMethod("private", returnType, name, parameters, locals, buildCode(instructions));
+  }
+
   public MethodSignature addInstanceMethod(
       String returnType, String name, int locals, String... instructions) {
     return addInstanceMethod(returnType, name, ImmutableList.of(), locals, buildCode(instructions));
diff --git a/src/test/java/com/android/tools/r8/utils/DexInspector.java b/src/test/java/com/android/tools/r8/utils/DexInspector.java
index fd32ec7..0b8de12 100644
--- a/src/test/java/com/android/tools/r8/utils/DexInspector.java
+++ b/src/test/java/com/android/tools/r8/utils/DexInspector.java
@@ -715,6 +715,8 @@
 
   public abstract class MemberSubject extends Subject {
 
+    public abstract boolean isPublic();
+
     public abstract boolean isStatic();
 
     public abstract boolean isFinal();
@@ -773,6 +775,11 @@
     }
 
     @Override
+    public boolean isPublic() {
+      return false;
+    }
+
+    @Override
     public boolean isStatic() {
       return false;
     }
@@ -849,6 +856,11 @@
     }
 
     @Override
+    public boolean isPublic() {
+      return dexMethod.accessFlags.isPublic();
+    }
+
+    @Override
     public boolean isStatic() {
       return dexMethod.accessFlags.isStatic();
     }
@@ -966,6 +978,11 @@
   public class AbsentFieldSubject extends FieldSubject {
 
     @Override
+    public boolean isPublic() {
+      return false;
+    }
+
+    @Override
     public boolean isStatic() {
       return false;
     }
@@ -1032,6 +1049,11 @@
     }
 
     @Override
+    public boolean isPublic() {
+      return dexField.accessFlags.isPublic();
+    }
+
+    @Override
     public boolean isStatic() {
       return dexField.accessFlags.isStatic();
     }
diff --git a/src/test/java/com/android/tools/r8/utils/DexInspectorMatchers.java b/src/test/java/com/android/tools/r8/utils/DexInspectorMatchers.java
index 8e21bea..1986bbc 100644
--- a/src/test/java/com/android/tools/r8/utils/DexInspectorMatchers.java
+++ b/src/test/java/com/android/tools/r8/utils/DexInspectorMatchers.java
@@ -138,4 +138,24 @@
       }
     };
   }
+
+  public static Matcher<MethodSubject> isPublic() {
+    return new TypeSafeMatcher<MethodSubject>() {
+      @Override
+      public boolean matchesSafely(final MethodSubject method) {
+        return method.isPresent() && method.isPublic();
+      }
+
+      @Override
+      public void describeTo(final Description description) {
+        description.appendText("method public");
+      }
+
+      @Override
+      public void describeMismatchSafely(final MethodSubject method, Description description) {
+        description
+            .appendText("method ").appendValue(method.getOriginalName()).appendText(" was not");
+      }
+    };
+  }
 }