Fix repeated analysis of values in dead code removal
Bug: b/267990059
Change-Id: I9deebf700e936ad81a8fb25d067acc04637d980d
diff --git a/src/main/java/com/android/tools/r8/ir/code/ArrayPut.java b/src/main/java/com/android/tools/r8/ir/code/ArrayPut.java
index 13f8213..c521bf5 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ArrayPut.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ArrayPut.java
@@ -23,6 +23,7 @@
import com.android.tools.r8.ir.conversion.DexBuilder;
import com.android.tools.r8.ir.conversion.MethodConversionOptions;
import com.android.tools.r8.ir.conversion.TypeConstraintResolver;
+import com.android.tools.r8.ir.optimize.DeadCodeRemover.DeadInstructionResult;
import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
import com.android.tools.r8.ir.optimize.InliningConstraints;
import com.android.tools.r8.ir.regalloc.RegisterAllocator;
@@ -117,8 +118,7 @@
}
@Override
- public boolean instructionMayHaveSideEffects(
- AppView<?> appView, ProgramMethod context, SideEffectAssumption assumption) {
+ public boolean instructionInstanceCanThrow(AppView<?> appView, ProgramMethod context) {
// In debug mode, ArrayPut has a side-effect on the locals.
if (appView.options().debug) {
return true;
@@ -158,29 +158,24 @@
if (!valueType.lessThanOrEqualUpToNullability(memberType, appView)) {
return true;
}
-
- if (array.hasPhiUsers()) {
- // The array could be used indirectly.
- return true;
- }
-
- // Check that all usages of the array are array stores.
- for (Instruction user : array.aliasedUsers()) {
- if (user.isAssume()) {
- if (user.outValue().hasPhiUsers()) {
- return true;
- }
- continue;
- }
- if (!user.isArrayPut() || user.asArrayPut().array().getAliasedValue() != array) {
- return true;
- }
- }
-
return false;
}
@Override
+ public boolean instructionMayHaveSideEffects(
+ AppView<?> appView, ProgramMethod context, SideEffectAssumption assumption) {
+ // This modifies the array (or throws).
+ return true;
+ }
+
+ @Override
+ public DeadInstructionResult canBeDeadCode(AppView<?> appView, IRCode code) {
+ return instructionInstanceCanThrow(appView, code.context())
+ ? DeadInstructionResult.notDead()
+ : DeadInstructionResult.deadIfInValueIsDead(array());
+ }
+
+ @Override
public boolean identicalAfterRegisterAllocation(
Instruction other, RegisterAllocator allocator, MethodConversionOptions conversionOptions) {
// We cannot share ArrayPut instructions without knowledge of the type of the array input.
diff --git a/src/main/java/com/android/tools/r8/ir/code/ValueIsDeadAnalysis.java b/src/main/java/com/android/tools/r8/ir/code/ValueIsDeadAnalysis.java
index 14124c1..2bcbae6 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ValueIsDeadAnalysis.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ValueIsDeadAnalysis.java
@@ -4,19 +4,41 @@
package com.android.tools.r8.ir.code;
+import static com.android.tools.r8.utils.MapUtils.ignoreKey;
+
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.ir.optimize.DeadCodeRemover.DeadInstructionResult;
+import com.android.tools.r8.utils.MapUtils;
import com.android.tools.r8.utils.WorkList;
import com.google.common.collect.Iterables;
+import com.google.common.collect.Sets;
+import java.util.Collections;
+import java.util.IdentityHashMap;
import java.util.LinkedHashSet;
+import java.util.Map;
import java.util.Objects;
import java.util.Set;
public class ValueIsDeadAnalysis {
+ private enum ValueIsDeadResult {
+ DEAD,
+ NOT_DEAD;
+
+ boolean isDead() {
+ return this == DEAD;
+ }
+
+ boolean isNotDead() {
+ return this == NOT_DEAD;
+ }
+ }
+
private final AppView<?> appView;
private final IRCode code;
+ private final Map<Value, ValueIsDeadResult> analysisCache = new IdentityHashMap<>();
+
public ValueIsDeadAnalysis(AppView<?> appView, IRCode code) {
this.appView = appView;
this.code = code;
@@ -27,9 +49,24 @@
if (value.isUnused()) {
return true;
}
+ // Create an is-dead dependence graph. If the deadness of value v depends on value u being dead,
+ // a directed edge [v -> u] is added to the graph.
+ //
+ // This graph serves two purposes:
+ // 1) If the analysis finds that `u` is *not* dead, then using the graph we can find all the
+ // values whose deadness depend (directly or indirectly) on `u` being dead, and mark them as
+ // being *not* dead in the analysis cache.
+ // 2) If the analysis finds that `u` *is* dead, we can remove the node from the dependence graph
+ // (as it is necessarily a leaf), and repeatedly mark direct and indirect predecessors of `u`
+ // that have now become leaves as being dead in the analysis cache.
WorkList<Value> worklist = WorkList.newIdentityWorkList(value);
Value notDeadWitness = findNotDeadWitness(worklist);
boolean isDead = Objects.isNull(notDeadWitness);
+ if (isDead) {
+ for (Value deadValue : worklist.getSeenSet()) {
+ recordValueIsDead(deadValue);
+ }
+ }
return isDead;
}
@@ -38,20 +75,31 @@
}
private Value findNotDeadWitness(WorkList<Value> worklist) {
+ DependenceGraph dependenceGraph = new DependenceGraph();
while (worklist.hasNext()) {
Value value = worklist.next();
- // Give up when the dependent set of values reach a given threshold (otherwise this fails with
- // a StackOverflowError on Art003_omnibus_opcodesTest).
- // TODO(b/267990059): Remove this bail-out when the analysis is linear in the size of the code
- // object.
- if (worklist.getSeenSet().size() > 100) {
- return value;
+ // The first time we visit a value we have not yet added any outgoing edges to the dependence
+ // graph.
+ assert dependenceGraph.isLeaf(value);
+
+ // Lookup if we have already analyzed the deadness of this value.
+ ValueIsDeadResult cacheResult = analysisCache.get(value);
+ if (cacheResult != null) {
+ // If it is dead, then continue the search for a non-dead dependent. Otherwise this value is
+ // a witness that the analysis failed.
+ if (cacheResult.isDead()) {
+ continue;
+ } else {
+ recordDependentsAreNotDead(value, dependenceGraph);
+ return value;
+ }
}
// If the value has debug users we cannot eliminate it since it represents a value in a local
// variable that should be visible in the debugger.
if (value.hasDebugUsers()) {
+ recordValueAndDependentsAreNotDead(value, dependenceGraph);
return value;
}
@@ -59,6 +107,7 @@
for (Instruction instruction : value.uniqueUsers()) {
DeadInstructionResult result = instruction.canBeDeadCode(appView, code);
if (result.isNotDead()) {
+ recordValueAndDependentsAreNotDead(value, dependenceGraph);
return value;
}
if (result.isMaybeDead()) {
@@ -69,9 +118,123 @@
}
}
- // Continue the analysis of the dependents.
- worklist.addIfNotSeen(valuesRequiredToBeDead);
+ // No need to record that the deadness of a values relies on its own removal, nor known to be
+ // dead values.
+ valuesRequiredToBeDead.remove(value);
+ valuesRequiredToBeDead.removeIf(
+ valueRequiredToBeDead -> analysisCache.get(value) == ValueIsDeadResult.DEAD);
+
+ if (valuesRequiredToBeDead.isEmpty()) {
+ // We have now proven that this value is dead.
+ recordValueIsDeadAndPropagateToDependents(value, dependenceGraph);
+ } else {
+ // Record the current value as a dependent of each value required to be dead.
+ for (Value valueRequiredToBeDead : valuesRequiredToBeDead) {
+ dependenceGraph.addDependenceEdge(value, valueRequiredToBeDead);
+ }
+
+ // Continue the analysis of the dependents.
+ worklist.addIfNotSeen(valuesRequiredToBeDead);
+ }
}
return null;
}
+
+ private void recordValueIsDeadAndPropagateToDependents(
+ Value value, DependenceGraph dependenceGraph) {
+ WorkList<Value> worklist = WorkList.newIdentityWorkList(value);
+ while (worklist.hasNext()) {
+ Value current = worklist.next();
+ recordValueIsDead(current);
+
+ // This value is now proven to be dead, thus there is no need to keep track of its successors.
+ dependenceGraph.unlinkSuccessors(current);
+
+ // Continue processing of new leaves.
+ for (Value dependent : dependenceGraph.removeLeaf(current)) {
+ if (dependenceGraph.isLeaf(dependent)) {
+ worklist.addIfNotSeen(dependent);
+ }
+ }
+ }
+ }
+
+ private void recordValueIsDead(Value value) {
+ ValueIsDeadResult existingResult = analysisCache.put(value, ValueIsDeadResult.DEAD);
+ assert existingResult == null || existingResult == ValueIsDeadResult.DEAD;
+ }
+
+ private void recordValueAndDependentsAreNotDead(Value value, DependenceGraph dependenceGraph) {
+ recordValueIsNotDead(value, dependenceGraph);
+ recordDependentsAreNotDead(value, dependenceGraph);
+ }
+
+ private void recordValueIsNotDead(Value value, DependenceGraph dependenceGraph) {
+ // This value is now proven to be dead, thus there is no need to keep track of its successors.
+ dependenceGraph.unlinkSuccessors(value);
+ ValueIsDeadResult existingResult = analysisCache.put(value, ValueIsDeadResult.NOT_DEAD);
+ assert existingResult == null || existingResult.isNotDead();
+ }
+
+ private void recordDependentsAreNotDead(Value value, DependenceGraph dependenceGraph) {
+ WorkList<Value> worklist = WorkList.newIdentityWorkList(value);
+ while (worklist.hasNext()) {
+ Value current = worklist.next();
+ for (Value dependent : dependenceGraph.removeLeaf(current)) {
+ recordValueIsNotDead(dependent, dependenceGraph);
+ worklist.addIfNotSeen(dependent);
+ }
+ }
+ }
+
+ private static class DependenceGraph {
+
+ private final Map<Value, Set<Value>> successors = new IdentityHashMap<>();
+ private final Map<Value, Set<Value>> predecessors = new IdentityHashMap<>();
+
+ /**
+ * Records that the removal of {@param value} depends on the removal of {@param
+ * valueRequiredToBeDead} by adding an edge from {@param value} to {@param
+ * valueRequiredToBeDead} in this graph.
+ */
+ void addDependenceEdge(Value value, Value valueRequiredToBeDead) {
+ successors
+ .computeIfAbsent(value, ignoreKey(Sets::newIdentityHashSet))
+ .add(valueRequiredToBeDead);
+ predecessors
+ .computeIfAbsent(valueRequiredToBeDead, ignoreKey(Sets::newIdentityHashSet))
+ .add(value);
+ }
+
+ Set<Value> removeLeaf(Value value) {
+ assert isLeaf(value);
+ Set<Value> dependents = MapUtils.removeOrDefault(predecessors, value, Collections.emptySet());
+ for (Value dependent : dependents) {
+ Set<Value> dependentSuccessors = successors.get(dependent);
+ boolean removed = dependentSuccessors.remove(value);
+ assert removed;
+ if (dependentSuccessors.isEmpty()) {
+ successors.remove(dependent);
+ }
+ }
+ return dependents;
+ }
+
+ void unlinkSuccessors(Value value) {
+ Set<Value> valueSuccessors =
+ MapUtils.removeOrDefault(successors, value, Collections.emptySet());
+ for (Value successor : valueSuccessors) {
+ Set<Value> successorPredecessors = predecessors.get(successor);
+ boolean removed = successorPredecessors.remove(value);
+ assert removed;
+ if (successorPredecessors.isEmpty()) {
+ predecessors.remove(successor);
+ }
+ }
+ }
+
+ boolean isLeaf(Value value) {
+ return !successors.containsKey(value);
+ }
+ }
}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/DeadCodeRemover.java b/src/main/java/com/android/tools/r8/ir/optimize/DeadCodeRemover.java
index 16cd748..dce99b1 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/DeadCodeRemover.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/DeadCodeRemover.java
@@ -22,9 +22,9 @@
import com.android.tools.r8.ir.code.ValueIsDeadAnalysis;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
import com.android.tools.r8.utils.Box;
+import com.android.tools.r8.utils.IterableUtils;
import com.android.tools.r8.utils.Timing;
import com.google.common.collect.ImmutableList;
-import com.google.common.collect.Iterators;
import java.util.ArrayDeque;
import java.util.Collection;
import java.util.Deque;
@@ -299,21 +299,12 @@
}
@Override
- public boolean isDeadIfInValueIsDead() {
- return true;
- }
-
- @Override
public Iterable<Value> getValuesRequiredToBeDead() {
- return () -> Iterators.singletonIterator(inValueRequiredToBeDead);
+ return IterableUtils.singleton(inValueRequiredToBeDead);
}
};
}
- public boolean isDeadIfInValueIsDead() {
- return false;
- }
-
public boolean isDeadIfOutValueIsDead() {
return false;
}
diff --git a/src/main/java/com/android/tools/r8/utils/MapUtils.java b/src/main/java/com/android/tools/r8/utils/MapUtils.java
index 94b9bfe..e0a915f 100644
--- a/src/main/java/com/android/tools/r8/utils/MapUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/MapUtils.java
@@ -61,6 +61,11 @@
map.entrySet().removeIf(entry -> predicate.test(entry.getKey(), entry.getValue()));
}
+ public static <K, V> V removeOrDefault(Map<K, V> map, K key, V defaultValue) {
+ V value = map.remove(key);
+ return value != null ? value : defaultValue;
+ }
+
public static String toString(Map<?, ?> map) {
return StringUtils.join(
",", map.entrySet(), entry -> entry.getKey() + ":" + entry.getValue(), BraceType.TUBORG);
