Refactor value-is-dead analysis to separate analysis class
Bug: b/267990059
Change-Id: I8b881203ebe21395f48c8eeb6434faa03f7f9d46
diff --git a/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java b/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
index 0a79887..2daa545 100644
--- a/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
+++ b/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
@@ -662,15 +662,6 @@
return !phis.isEmpty();
}
- public boolean hasDeadPhi(AppView<?> appView, IRCode code) {
- for (Phi phi : phis) {
- if (phi.isDead(appView, code)) {
- return true;
- }
- }
- return false;
- }
-
public List<Phi> getPhis() {
return phis;
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/Value.java b/src/main/java/com/android/tools/r8/ir/code/Value.java
index 54710df..b0eb2bd 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Value.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Value.java
@@ -29,7 +29,6 @@
import com.android.tools.r8.ir.analysis.value.AbstractValue;
import com.android.tools.r8.ir.analysis.value.NumberFromIntervalValue;
import com.android.tools.r8.ir.analysis.value.UnknownValue;
-import com.android.tools.r8.ir.optimize.DeadCodeRemover.DeadInstructionResult;
import com.android.tools.r8.ir.regalloc.LiveIntervals;
import com.android.tools.r8.origin.Origin;
import com.android.tools.r8.position.MethodPosition;
@@ -464,6 +463,10 @@
return !users.isEmpty() || !phiUsers.isEmpty() || numberOfDebugUsers() > 0;
}
+ public boolean isUnused() {
+ return !isUsed();
+ }
+
public boolean isAlwaysNull(AppView<?> appView) {
if (hasLocalInfo()) {
// Not always null as the value can be changed via the debugger.
@@ -972,73 +975,6 @@
}
}
- public boolean isDead(AppView<?> appView, IRCode code) {
- // Totally unused values are trivially dead.
- return !isUsed() || isDead(appView, code, Predicates.alwaysFalse());
- }
-
- public boolean isDead(AppView<?> appView, IRCode code, Predicate<Instruction> ignoreUser) {
- // Totally unused values are trivially dead.
- return !isUsed() || isDead(appView, code, ignoreUser, Sets.newIdentityHashSet());
- }
-
- /**
- * Used to determine if a given value is dead.
- *
- * <p>The predicate `ignoreUser` can be used to determine if a given value is dead under the
- * assumption that the instructions for which `ignoreUser` returns true are also dead.
- *
- * <p>One use case of this is when we attempt to determine if a call to {@code <init>()} can be
- * removed: calls to {@code <init>()} can only be removed if the receiver is dead except for the
- * constructor call.
- */
- protected boolean isDead(
- AppView<?> appView, IRCode code, Predicate<Instruction> ignoreUser, Set<Value> active) {
- // Give up when the dependent set of values reach a given threshold (otherwise this fails with
- // a StackOverflowError on Art003_omnibus_opcodesTest).
- if (active.size() > 100) {
- return false;
- }
-
- // 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 (hasDebugUsers()) {
- return false;
- }
- // This is a candidate for a dead value. Guard against looping by adding it to the set of
- // currently active values.
- active.add(this);
- for (Instruction instruction : uniqueUsers()) {
- if (ignoreUser.test(instruction)) {
- continue;
- }
- DeadInstructionResult result = instruction.canBeDeadCode(appView, code);
- if (result.isNotDead()) {
- return false;
- }
- if (result.isMaybeDead()) {
- for (Value valueRequiredToBeDead : result.getValuesRequiredToBeDead()) {
- if (!active.contains(valueRequiredToBeDead)
- && !valueRequiredToBeDead.isDead(appView, code, ignoreUser, active)) {
- return false;
- }
- }
- }
- Value outValue = instruction.outValue();
- if (outValue != null
- && !active.contains(outValue)
- && !outValue.isDead(appView, code, ignoreUser, active)) {
- return false;
- }
- }
- for (Phi phi : uniquePhiUsers()) {
- if (!active.contains(phi) && !phi.isDead(appView, code, ignoreUser, active)) {
- return false;
- }
- }
- return true;
- }
-
public boolean isZero() {
return isConstant()
&& getConstInstruction().isConstNumber()
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
new file mode 100644
index 0000000..f91a569
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/code/ValueIsDeadAnalysis.java
@@ -0,0 +1,74 @@
+// Copyright (c) 2023, 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.ir.code;
+
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.ir.optimize.DeadCodeRemover.DeadInstructionResult;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Sets;
+import java.util.Set;
+
+public class ValueIsDeadAnalysis {
+
+ private final AppView<?> appView;
+ private final IRCode code;
+
+ public ValueIsDeadAnalysis(AppView<?> appView, IRCode code) {
+ this.appView = appView;
+ this.code = code;
+ }
+
+ public boolean isDead(Value value) {
+ // Totally unused values are trivially dead.
+ if (value.isUnused()) {
+ return true;
+ }
+ return isDead(value, Sets.newIdentityHashSet());
+ }
+
+ public boolean hasDeadPhi(BasicBlock block) {
+ return Iterables.any(block.getPhis(), this::isDead);
+ }
+
+ private boolean isDead(Value value, Set<Value> active) {
+ // Give up when the dependent set of values reach a given threshold (otherwise this fails with
+ // a StackOverflowError on Art003_omnibus_opcodesTest).
+ if (active.size() > 100) {
+ return false;
+ }
+
+ // 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()) {
+ return false;
+ }
+ // This is a candidate for a dead value. Guard against looping by adding it to the set of
+ // currently active values.
+ active.add(value);
+ for (Instruction instruction : value.uniqueUsers()) {
+ DeadInstructionResult result = instruction.canBeDeadCode(appView, code);
+ if (result.isNotDead()) {
+ return false;
+ }
+ if (result.isMaybeDead()) {
+ for (Value valueRequiredToBeDead : result.getValuesRequiredToBeDead()) {
+ if (!active.contains(valueRequiredToBeDead) && !isDead(valueRequiredToBeDead, active)) {
+ return false;
+ }
+ }
+ }
+ Value outValue = instruction.outValue();
+ if (outValue != null && !active.contains(outValue) && !isDead(outValue, active)) {
+ return false;
+ }
+ }
+ for (Phi phi : value.uniquePhiUsers()) {
+ if (!active.contains(phi) && !isDead(phi, active)) {
+ return false;
+ }
+ }
+ return true;
+ }
+}
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 92e653d..16cd748 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
@@ -19,6 +19,7 @@
import com.android.tools.r8.ir.code.InstructionListIterator;
import com.android.tools.r8.ir.code.Phi;
import com.android.tools.r8.ir.code.Value;
+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.Timing;
@@ -52,13 +53,14 @@
// 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 {
worklist.addAll(code.topologicallySortedBlocks());
while (!worklist.isEmpty()) {
BasicBlock block = worklist.removeLast();
- removeDeadInstructions(worklist, code, block);
- removeDeadPhis(worklist, code, block);
+ removeDeadInstructions(worklist, code, block, valueIsDeadAnalysis);
+ removeDeadPhis(worklist, block, valueIsDeadAnalysis);
}
} while (codeRewriter.simplifyIf(code).anySimplifications()
|| removeUnneededCatchHandlers(code));
@@ -70,8 +72,9 @@
public boolean verifyNoDeadCode(IRCode code) {
assert !codeRewriter.rewriteMoveResult(code);
assert !removeUnneededCatchHandlers(code);
+ ValueIsDeadAnalysis valueIsDeadAnalysis = new ValueIsDeadAnalysis(appView, code);
for (BasicBlock block : code.blocks) {
- assert !block.hasDeadPhi(appView, code);
+ assert !valueIsDeadAnalysis.hasDeadPhi(block);
for (Instruction instruction : block.getInstructions()) {
// No unused move-result instructions.
assert !instruction.isInvoke()
@@ -79,7 +82,7 @@
|| instruction.outValue().hasAnyUsers();
// No dead instructions.
assert !instruction.canBeDeadCode(appView, code).isDeadIfOutValueIsDead()
- || (instruction.hasOutValue() && !instruction.outValue().isDead(appView, code));
+ || (instruction.hasOutValue() && !valueIsDeadAnalysis.isDead(instruction.outValue()));
}
}
return true;
@@ -108,11 +111,12 @@
}
}
- private void removeDeadPhis(Queue<BasicBlock> worklist, IRCode code, BasicBlock block) {
+ private void removeDeadPhis(
+ Queue<BasicBlock> worklist, BasicBlock block, ValueIsDeadAnalysis valueIsDeadAnalysis) {
Iterator<Phi> phiIt = block.getPhis().iterator();
while (phiIt.hasNext()) {
Phi phi = phiIt.next();
- if (phi.isDead(appView, code)) {
+ if (valueIsDeadAnalysis.isDead(phi)) {
phiIt.remove();
for (Value operand : phi.getOperands()) {
operand.removePhiUser(phi);
@@ -122,7 +126,11 @@
}
}
- private void removeDeadInstructions(Queue<BasicBlock> worklist, IRCode code, BasicBlock block) {
+ private void removeDeadInstructions(
+ Queue<BasicBlock> worklist,
+ IRCode code,
+ BasicBlock block,
+ ValueIsDeadAnalysis valueIsDeadAnalysis) {
InstructionListIterator iterator = block.listIterator(code, block.getInstructions().size());
while (iterator.hasPrevious()) {
Instruction current = iterator.previous();
@@ -165,7 +173,7 @@
if (deadInstructionResult.isMaybeDead()) {
boolean satisfied = true;
for (Value valueRequiredToBeDead : deadInstructionResult.getValuesRequiredToBeDead()) {
- if (!valueRequiredToBeDead.isDead(appView, code)) {
+ if (!valueIsDeadAnalysis.isDead(valueRequiredToBeDead)) {
satisfied = false;
break;
}
@@ -175,7 +183,7 @@
}
}
Value outValue = current.outValue();
- if (outValue != null && !outValue.isDead(appView, code)) {
+ if (outValue != null && !valueIsDeadAnalysis.isDead(outValue)) {
continue;
}
updateWorklist(worklist, current);
