src/main/java/com/android/tools/r8/optimize/argumentpropagation/unusedarguments/EffectivelyUnusedArgumentsGraph.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.graph.DexClassAndMethod.asProgramMethodOrNull;

import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.ProgramMethod;
import com.android.tools.r8.ir.optimize.info.MethodOptimizationInfo;
import com.android.tools.r8.optimize.argumentpropagation.codescanner.MethodParameter;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
import com.android.tools.r8.utils.WorkList;
import com.android.tools.r8.utils.dfs.DFSStack;
import com.android.tools.r8.utils.dfs.DFSWorklistItem;
import com.android.tools.r8.utils.dfs.DFSWorklistItem.NewlyVisitedDFSWorklistItem;
import com.google.common.collect.Iterables;
import com.google.common.collect.Sets;
import java.util.ArrayDeque;
import java.util.Collection;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.function.Consumer;

class EffectivelyUnusedArgumentsGraph {

  private final AppView<AppInfoWithLiveness> appView;

  private final Map<MethodParameter, EffectivelyUnusedArgumentsGraphNode> nodes = new HashMap<>();

  private EffectivelyUnusedArgumentsGraph(AppView<AppInfoWithLiveness> appView) {
    this.appView = appView;
  }

  public static EffectivelyUnusedArgumentsGraph create(
      AppView<AppInfoWithLiveness> appView,
      Map<MethodParameter, Set<MethodParameter>> constraints) {
    EffectivelyUnusedArgumentsGraph graph = new EffectivelyUnusedArgumentsGraph(appView);
    constraints.forEach(
        (methodParameter, constraintsForMethodParameter) -> {
          EffectivelyUnusedArgumentsGraphNode node = graph.getOrCreateNode(methodParameter);
          for (MethodParameter constraint : constraintsForMethodParameter) {
            graph.addConstraintEdge(node, constraint, constraints);
          }
        });
    return graph;
  }

  void addConstraintEdge(
      EffectivelyUnusedArgumentsGraphNode node,
      MethodParameter constraint,
      Map<MethodParameter, Set<MethodParameter>> constraints) {
    ProgramMethod dependencyMethod =
        asProgramMethodOrNull(appView.definitionFor(constraint.getMethod()));
    if (dependencyMethod == null) {
      assert false;
      node.setUnoptimizable();
      return;
    }

    // A nullable method parameter cannot be effectively unused if it is used as the receiver in an
    // invoke (or we cannot preserve NPE semantics).
    if (dependencyMethod.getDefinition().isInstance()
        && constraint.getIndex() == 0
        && node.isNullable()) {
      node.setUnoptimizable();
      return;
    }

    // If the successor parameter does not have any constraints, then the successor is not subject
    // to effectively unused argument removal. In this case, the successor can only be removed if it
    // is truly unused.
    if (!constraints.containsKey(constraint)) {
      MethodOptimizationInfo optimizationInfo = dependencyMethod.getOptimizationInfo();
      if (!optimizationInfo.hasUnusedArguments()
          || !optimizationInfo.getUnusedArguments().get(constraint.getIndex())) {
        node.setUnoptimizable();
      }
      return;
    }

    EffectivelyUnusedArgumentsGraphNode successor = getOrCreateNode(constraint, dependencyMethod);
    if (node != successor) {
      node.addSuccessor(successor);
    }
  }

  Collection<EffectivelyUnusedArgumentsGraphNode> getNodes() {
    return nodes.values();
  }

  EffectivelyUnusedArgumentsGraphNode getOrCreateNode(MethodParameter parameter) {
    ProgramMethod method = asProgramMethodOrNull(appView.definitionFor(parameter.getMethod()));
    return method != null ? getOrCreateNode(parameter, method) : null;
  }

  EffectivelyUnusedArgumentsGraphNode getOrCreateNode(
      MethodParameter parameter, ProgramMethod method) {
    return nodes.computeIfAbsent(
        parameter, p -> new EffectivelyUnusedArgumentsGraphNode(method, p.getIndex()));
  }

  void remove(EffectivelyUnusedArgumentsGraphNode node) {
    assert node.getSuccessors().isEmpty();
    assert node.getPredecessors().isEmpty();
    MethodParameter methodParameter =
        new MethodParameter(node.getMethod().getReference(), node.getArgumentIndex());
    EffectivelyUnusedArgumentsGraphNode removed = nodes.remove(methodParameter);
    assert removed == node;
  }

  void removeClosedCycles(Consumer<EffectivelyUnusedArgumentsGraphNode> reprocess) {
    Set<EffectivelyUnusedArgumentsGraphNode> seen = Sets.newIdentityHashSet();
    for (EffectivelyUnusedArgumentsGraphNode root : getNodes()) {
      if (seen.contains(root)) {
        continue;
      }
      DFSStack<EffectivelyUnusedArgumentsGraphNode> stack = DFSStack.createIdentityStack();
      Deque<DFSWorklistItem<EffectivelyUnusedArgumentsGraphNode>> worklist = new ArrayDeque<>();
      worklist.add(new NewlyVisitedDFSWorklistItem<>(root));
      while (!worklist.isEmpty()) {
        DFSWorklistItem<EffectivelyUnusedArgumentsGraphNode> item = worklist.removeLast();
        stack.handle(item);
        if (item.isFullyVisited()) {
          continue;
        }
        EffectivelyUnusedArgumentsGraphNode node = item.getValue();
        seen.add(node);
        worklist.add(item.asNewlyVisited().toFullyVisited());
        node.getSuccessors()
            .removeIf(
                successor -> {
                  if (stack.contains(successor)) {
                    Deque<EffectivelyUnusedArgumentsGraphNode> cycle =
                        stack.getCycleStartingAt(successor);
                    boolean isClosedCycle =
                        Iterables.all(cycle, member -> member.getSuccessors().size() == 1);
                    if (isClosedCycle) {
                      // Remove edge and reprocess this node, since it is now eligible for unused
                      // argument removal.
                      boolean removed = successor.getPredecessors().remove(node);
                      assert removed;
                      reprocess.accept(node);
                      // Return true to remove the successor from the successors of the current
                      // node (to prevent ConcurrentModificationException).
                      return true;
                    }
                  } else {
                    worklist.add(new NewlyVisitedDFSWorklistItem<>(successor));
                  }
                  return false;
                });
      }
    }
  }

  boolean verifyContains(EffectivelyUnusedArgumentsGraphNode node) {
    MethodParameter methodParameter =
        new MethodParameter(node.getMethod().getReference(), node.getArgumentIndex());
    return nodes.containsKey(methodParameter);
  }

  void removeUnoptimizableNodes() {
    WorkList<EffectivelyUnusedArgumentsGraphNode> worklist = WorkList.newIdentityWorkList();
    for (EffectivelyUnusedArgumentsGraphNode node : getNodes()) {
      if (node.isUnoptimizable()) {
        worklist.addIfNotSeen(node);
      }
    }
    while (worklist.hasNext()) {
      EffectivelyUnusedArgumentsGraphNode node = worklist.next();
      worklist.addIfNotSeen(node.getPredecessors());
      node.cleanForRemoval();
      remove(node);
    }
  }
}