src/main/java/com/android/tools/r8/optimize/argumentpropagation/unusedarguments/EffectivelyUnusedArgumentsAnalysis.java

// Copyright (c) 2022, 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.argumentpropagation.unusedarguments;

import static com.android.tools.r8.utils.MapUtils.ignoreKey;

import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.DexMethodSignature;
import com.android.tools.r8.graph.DexProgramClass;
import com.android.tools.r8.graph.ProgramMethod;
import com.android.tools.r8.ir.code.Argument;
import com.android.tools.r8.ir.code.IRCode;
import com.android.tools.r8.ir.code.Instruction;
import com.android.tools.r8.ir.code.InvokeMethod;
import com.android.tools.r8.ir.code.Value;
import com.android.tools.r8.optimize.argumentpropagation.codescanner.MethodParameter;
import com.android.tools.r8.optimize.argumentpropagation.utils.ParameterRemovalUtils;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
import com.android.tools.r8.utils.ListUtils;
import com.android.tools.r8.utils.WorkList;
import com.android.tools.r8.utils.collections.ProgramMethodSet;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;

/**
 * Analysis to find arguments that are effectively unused. The analysis first computes the
 * constraints for a given argument to be effectively unused, and then subsequently solves the
 * computed constraints.
 *
 * <p>Example: Consider the following Companion class.
 *
 * <pre>
 *   static class Companion {
 *     void foo() {
 *       this.bar()
 *     }
 *     void bar() {
 *       doStuff();
 *     }
 *   }
 * </pre>
 *
 * <p>The analysis works as follows.
 *
 * <ol>
 *   <li>When IR processing the Companion.bar() method, the unused argument analysis records that
 *       its receiver is unused.
 *   <li>When IR processing the Companion.foo() method, the effectively unused argument analysis
 *       records that the receiver of Companion.foo() is unused if the receiver of Companion.bar()
 *       is unused.
 *   <li>After IR processing all methods, the effectively unused argument analysis builds a graph
 *       where there is a directed edge p0 -> p1 if the removal of method parameter p0 depends on
 *       the removal of method parameter p1.
 *   <li>The analysis then repeatedly removes method parameters from the graph that have no outgoing
 *       edges and marks such method parameters as being effectively unused.
 * </ol>
 *
 * <p>
 */
public class EffectivelyUnusedArgumentsAnalysis {

  private final AppView<AppInfoWithLiveness> appView;

  // Maps each method parameter p to the method parameters that must be effectively unused in order
  // for the method parameter p to be effectively unused.
  private final Map<MethodParameter, Set<MethodParameter>> constraints = new ConcurrentHashMap<>();

  // Set of virtual methods that can definitely be optimized.
  //
  // We conservatively exclude virtual methods with dynamic dispatch from this set, since the
  // parameters of such methods can only be removed if the same parameter can be removed from all
  // other virtual methods with the same signature in the class hierarchy.
  private final ProgramMethodSet optimizableVirtualMethods = ProgramMethodSet.createConcurrent();

  public EffectivelyUnusedArgumentsAnalysis(AppView<AppInfoWithLiveness> appView) {
    this.appView = appView;
  }

  public void initializeOptimizableVirtualMethods(Set<DexProgramClass> stronglyConnectedComponent) {
    // Group all virtual methods in this strongly connected component by their signature.
    Map<DexMethodSignature, ProgramMethodSet> methodsBySignature = new HashMap<>();
    for (DexProgramClass clazz : stronglyConnectedComponent) {
      clazz.forEachProgramVirtualMethod(
          method -> {
            ProgramMethodSet methodsWithSameSignature =
                methodsBySignature.computeIfAbsent(
                    method.getMethodSignature(), ignoreKey(ProgramMethodSet::create));
            methodsWithSameSignature.add(method);
          });
    }
    // Mark the unique method signatures as being optimizable.
    methodsBySignature.forEach(
        (signature, methodsWithSignature) -> {
          if (methodsWithSignature.size() == 1) {
            ProgramMethod method = methodsWithSignature.getFirst();
            if (ParameterRemovalUtils.canRemoveUnusedParametersFrom(appView, method)) {
              optimizableVirtualMethods.add(method);
            }
          }
        });
  }

  public void scan(ProgramMethod method, IRCode code) {
    // If this method is not subject to optimization, then don't compute effectively unused
    // constraints for the method parameters.
    if (isUnoptimizable(method)) {
      return;
    }
    Iterator<Argument> argumentIterator = code.argumentIterator();
    while (argumentIterator.hasNext()) {
      Argument argument = argumentIterator.next();
      Value argumentValue = argument.outValue();
      Set<MethodParameter> effectivelyUnusedConstraints =
          computeEffectivelyUnusedConstraints(method, argument, argumentValue);
      if (effectivelyUnusedConstraints != null && !effectivelyUnusedConstraints.isEmpty()) {
        MethodParameter methodParameter =
            new MethodParameter(method.getReference(), argument.getIndex());
        assert !constraints.containsKey(methodParameter);
        constraints.put(methodParameter, effectivelyUnusedConstraints);
      }
    }
  }

  private Set<MethodParameter> computeEffectivelyUnusedConstraints(
      ProgramMethod method, Argument argument, Value argumentValue) {
    if (method.getDefinition().isInstanceInitializer() && argumentValue.isThis()) {
      return null;
    }
    if (method.getDefinition().willBeInlinedIntoInstanceInitializer(appView.dexItemFactory())) {
      return null;
    }
    if (!ParameterRemovalUtils.canRemoveUnusedParameter(appView, method, argument.getIndex())) {
      return null;
    }
    if (!argumentValue.getType().isClassType()
        || argumentValue.hasDebugUsers()
        || argumentValue.hasPhiUsers()) {
      return null;
    }
    Set<MethodParameter> effectivelyUnusedConstraints = new HashSet<>();
    for (Instruction user : argumentValue.uniqueUsers()) {
      if (user.isInvokeMethod()) {
        InvokeMethod invoke = user.asInvokeMethod();
        ProgramMethod resolvedMethod =
            appView
                .appInfo()
                .unsafeResolveMethodDueToDexFormat(invoke.getInvokedMethod())
                .getResolvedProgramMethod();
        if (resolvedMethod == null || isUnoptimizable(resolvedMethod)) {
          return null;
        }
        int dependentArgumentIndex =
            ListUtils.uniqueIndexMatching(invoke.arguments(), value -> value == argumentValue);
        if (dependentArgumentIndex < 0
            || !ParameterRemovalUtils.canRemoveUnusedParameter(
                appView, resolvedMethod, dependentArgumentIndex)) {
          return null;
        }
        effectivelyUnusedConstraints.add(
            new MethodParameter(resolvedMethod.getReference(), dependentArgumentIndex));
      } else {
        return null;
      }
    }
    return effectivelyUnusedConstraints;
  }

  public void computeEffectivelyUnusedArguments() {
    // Build a graph where nodes are method parameters and there is an edge from method parameter p0
    // to method parameter p1 if the removal of p0 depends on the removal of p1.
    EffectivelyUnusedArgumentsGraph dependenceGraph =
        EffectivelyUnusedArgumentsGraph.create(appView, constraints);

    // Remove all unoptimizable method parameters from the graph, as well as all nodes that depend
    // on a node that is unoptimable.
    dependenceGraph.removeUnoptimizableNodes();

    // Repeatedly mark method parameters with no outgoing edges (i.e., no dependencies) as being
    // unused.
    WorkList<EffectivelyUnusedArgumentsGraphNode> worklist =
        WorkList.newIdentityWorkList(dependenceGraph.getNodes());
    while (!worklist.isEmpty()) {
      while (!worklist.isEmpty()) {
        EffectivelyUnusedArgumentsGraphNode node = worklist.removeSeen();
        assert dependenceGraph.verifyContains(node);
        node.removeUnusedSuccessors();
        if (node.getSuccessors().isEmpty()) {
          node.setUnused();
          node.getPredecessors().forEach(worklist::addIfNotSeen);
          node.cleanForRemoval();
          dependenceGraph.remove(node);
        }
      }

      // Handle mutually recursive methods. If there is a cycle p0 -> p1 -> ... -> pn -> p0 and each
      // of the method parameters p0 ... pn has a unique successor, then remove the edge pn -> p0
      // from the graph.
      dependenceGraph.removeClosedCycles(worklist::addIfNotSeen);
    }
  }

  private boolean isUnoptimizable(ProgramMethod method) {
    if (method.getDefinition().belongsToDirectPool()) {
      return !ParameterRemovalUtils.canRemoveUnusedParametersFrom(appView, method);
    }
    if (optimizableVirtualMethods.contains(method)) {
      assert ParameterRemovalUtils.canRemoveUnusedParametersFrom(appView, method);
      return false;
    }
    return true;
  }

  public void onMethodPruned(ProgramMethod method) {
    for (int argumentIndex = 0;
        argumentIndex < method.getDefinition().getNumberOfArguments();
        argumentIndex++) {
      constraints.remove(new MethodParameter(method.getReference(), argumentIndex));
    }
  }
}