Refinements to value-is-dead analysis
Bug: b/267990059
Fixes: b/268335684
Change-Id: I8007b13e2a4e0c32dffc181a827867ff4ab0373e
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 2bcbae6..73d0a99 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
@@ -8,12 +8,14 @@
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.ir.optimize.DeadCodeRemover.DeadInstructionResult;
+import com.android.tools.r8.utils.BooleanBox;
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.Iterator;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Objects;
@@ -60,11 +62,17 @@
// (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);
+ BooleanBox foundCycle = new BooleanBox();
+ Value notDeadWitness = findNotDeadWitness(worklist, foundCycle);
boolean isDead = Objects.isNull(notDeadWitness);
if (isDead) {
- for (Value deadValue : worklist.getSeenSet()) {
- recordValueIsDead(deadValue);
+ if (foundCycle.isTrue()) {
+ for (Value deadValue : worklist.getSeenSet()) {
+ recordValueIsDead(deadValue);
+ }
+ } else {
+ assert worklist.getSeenSet().stream()
+ .allMatch(deadValue -> analysisCache.get(deadValue) == ValueIsDeadResult.DEAD);
}
}
return isDead;
@@ -74,7 +82,7 @@
return Iterables.any(block.getPhis(), this::isDead);
}
- private Value findNotDeadWitness(WorkList<Value> worklist) {
+ private Value findNotDeadWitness(WorkList<Value> worklist, BooleanBox foundCycle) {
DependenceGraph dependenceGraph = new DependenceGraph();
while (worklist.hasNext()) {
Value value = worklist.next();
@@ -118,11 +126,17 @@
}
}
- // 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);
+ Iterator<Value> valuesRequiredToBeDeadIterator = valuesRequiredToBeDead.iterator();
+ while (valuesRequiredToBeDeadIterator.hasNext()) {
+ Value valueRequiredToBeDead = valuesRequiredToBeDeadIterator.next();
+ if (hasProvenThatValueIsNotDead(valueRequiredToBeDead)) {
+ recordValueAndDependentsAreNotDead(value, dependenceGraph);
+ return value;
+ }
+ if (!needsToProveThatValueIsDead(value, valueRequiredToBeDead)) {
+ valuesRequiredToBeDeadIterator.remove();
+ }
+ }
if (valuesRequiredToBeDead.isEmpty()) {
// We have now proven that this value is dead.
@@ -131,6 +145,7 @@
// Record the current value as a dependent of each value required to be dead.
for (Value valueRequiredToBeDead : valuesRequiredToBeDead) {
dependenceGraph.addDependenceEdge(value, valueRequiredToBeDead);
+ foundCycle.or(worklist.isSeen(valueRequiredToBeDead));
}
// Continue the analysis of the dependents.
@@ -140,6 +155,16 @@
return null;
}
+ private boolean hasProvenThatValueIsNotDead(Value valueRequiredToBeDead) {
+ return analysisCache.get(valueRequiredToBeDead) == ValueIsDeadResult.NOT_DEAD;
+ }
+
+ private boolean needsToProveThatValueIsDead(Value value, Value valueRequiredToBeDead) {
+ // No need to record that the deadness of a values relies on its own removal.
+ assert !hasProvenThatValueIsNotDead(valueRequiredToBeDead);
+ return valueRequiredToBeDead != value && !analysisCache.containsKey(valueRequiredToBeDead);
+ }
+
private void recordValueIsDeadAndPropagateToDependents(
Value value, DependenceGraph dependenceGraph) {
WorkList<Value> worklist = WorkList.newIdentityWorkList(value);
@@ -161,7 +186,7 @@
private void recordValueIsDead(Value value) {
ValueIsDeadResult existingResult = analysisCache.put(value, ValueIsDeadResult.DEAD);
- assert existingResult == null || existingResult == ValueIsDeadResult.DEAD;
+ assert existingResult == null || existingResult.isDead();
}
private void recordValueAndDependentsAreNotDead(Value value, DependenceGraph dependenceGraph) {
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 dce99b1..b7d7b10 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
@@ -53,9 +53,9 @@
// We may encounter unneeded catch handlers after each iteration, e.g., if a dead instruction
// is the only throwing instruction in a block. Removing unneeded catch handlers can lead to
// more dead instructions.
- ValueIsDeadAnalysis valueIsDeadAnalysis = new ValueIsDeadAnalysis(appView, code);
Deque<BasicBlock> worklist = new ArrayDeque<>();
do {
+ ValueIsDeadAnalysis valueIsDeadAnalysis = new ValueIsDeadAnalysis(appView, code);
worklist.addAll(code.topologicallySortedBlocks());
while (!worklist.isEmpty()) {
BasicBlock block = worklist.removeLast();
