Redundant switch case elimination
Change-Id: I60a1ef2bb7849ef82b7be6dd66b7ccfd239d3aa3
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/equivalence/BasicBlockBehavioralSubsumption.java b/src/main/java/com/android/tools/r8/ir/analysis/equivalence/BasicBlockBehavioralSubsumption.java
new file mode 100644
index 0000000..fce5100
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/equivalence/BasicBlockBehavioralSubsumption.java
@@ -0,0 +1,207 @@
+// Copyright (c) 2019, 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.analysis.equivalence;
+
+import static com.google.common.base.Predicates.not;
+import static com.google.common.base.Predicates.or;
+
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.code.BasicBlock;
+import com.android.tools.r8.ir.code.ConstClass;
+import com.android.tools.r8.ir.code.ConstNumber;
+import com.android.tools.r8.ir.code.ConstString;
+import com.android.tools.r8.ir.code.DexItemBasedConstString;
+import com.android.tools.r8.ir.code.Instruction;
+import com.android.tools.r8.ir.code.InstructionIterator;
+import com.android.tools.r8.ir.code.Return;
+import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.utils.SetUtils;
+import java.util.Set;
+
+/**
+ * Analysis that can be used to determine if the behavior of one basic block is subsumed by the
+ * behavior of another basic block.
+ *
+ * <p>Example: If the behavior of a switch case is subsumed by the behavior of the switch's default
+ * target, then the switch case can simply be removed from the switch instruction.
+ */
+public class BasicBlockBehavioralSubsumption {
+
+ private final AppView<?> appView;
+ private final DexType context;
+
+ public BasicBlockBehavioralSubsumption(AppView<?> appView, DexType context) {
+ this.appView = appView;
+ this.context = context;
+ }
+
+ public boolean isSubsumedBy(BasicBlock block, BasicBlock other) {
+ return isSubsumedBy(block.iterator(), other.iterator(), null);
+ }
+
+ private boolean isSubsumedBy(
+ InstructionIterator iterator, InstructionIterator otherIterator, Set<BasicBlock> visited) {
+ // Skip over block-local instructions (i.e., instructions that define values that are not used
+ // outside the block itself) that do not have side effects.
+ Instruction instruction =
+ iterator.nextUntil(
+ or(
+ not(this::isBlockLocalInstructionWithoutSideEffects),
+ Instruction::isJumpInstruction));
+
+ // If the instruction defines a value with non-local usages, then we would need a dominator
+ // analysis to verify that all these non-local usages can in fact be replaced by a value
+ // defined in `other`. We just give up in this case.
+ if (definesValueWithNonLocalUsages(instruction)) {
+ return false;
+ }
+
+ // Skip over non-throwing instructions in the other block.
+ Instruction otherInstruction =
+ otherIterator.nextUntil(
+ or(this::instructionMayHaveSideEffects, Instruction::isJumpInstruction));
+ assert otherInstruction != null;
+
+ if (instruction.isGoto()) {
+ BasicBlock targetBlock = instruction.asGoto().getTarget();
+ if (otherInstruction.isGoto()) {
+ BasicBlock otherTargetBlock = otherInstruction.asGoto().getTarget();
+ // If the other instruction is also a goto instruction, which targets the same block, then
+ // we are done.
+ if (targetBlock == otherTargetBlock) {
+ return true;
+ }
+ // Otherwise we continue the search from the two successor blocks.
+ otherIterator = otherTargetBlock.iterator();
+ } else {
+ // Move the cursor backwards to ensure that the recursive call will revisit the current
+ // instruction.
+ otherIterator.previous();
+ }
+ if (visited == null) {
+ visited = SetUtils.newIdentityHashSet(instruction.getBlock());
+ }
+ if (visited.add(targetBlock)) {
+ return isSubsumedBy(targetBlock.iterator(), otherIterator, visited);
+ }
+ // Guard against cycles in the control flow graph.
+ return false;
+ }
+
+ // If the current instruction is not a goto instruction, but the other instruction is, then
+ // we continue the search from the target of the other goto instruction.
+ if (otherInstruction.isGoto()) {
+ otherIterator = otherInstruction.asGoto().getTarget().iterator();
+ otherInstruction =
+ otherIterator.nextUntil(
+ or(this::instructionMayHaveSideEffects, Instruction::isJumpInstruction));
+ }
+
+ if (instruction.isReturn()) {
+ Return returnInstruction = instruction.asReturn();
+ if (otherInstruction.isReturn()) {
+ Return otherReturnInstruction = otherInstruction.asReturn();
+ if (returnInstruction.isReturnVoid()) {
+ assert otherReturnInstruction.isReturnVoid();
+ return true;
+ }
+ return valuesAreIdentical(
+ otherReturnInstruction.returnValue(), returnInstruction.returnValue());
+ }
+ return false;
+ }
+
+ return false;
+ }
+
+ private boolean isBlockLocalInstructionWithoutSideEffects(Instruction instruction) {
+ return definesBlockLocalValue(instruction) && !instructionMayHaveSideEffects(instruction);
+ }
+
+ private boolean definesBlockLocalValue(Instruction instruction) {
+ return !definesValueWithNonLocalUsages(instruction);
+ }
+
+ private boolean definesValueWithNonLocalUsages(Instruction instruction) {
+ if (instruction.hasOutValue()) {
+ Value outValue = instruction.outValue();
+ if (outValue.numberOfPhiUsers() > 0) {
+ return true;
+ }
+ for (Instruction user : outValue.uniqueUsers()) {
+ if (user.getBlock() != instruction.getBlock()) {
+ return true;
+ }
+ }
+ }
+ return false;
+ }
+
+ private boolean instructionMayHaveSideEffects(Instruction instruction) {
+ return instruction.instructionMayHaveSideEffects(appView, context);
+ }
+
+ private boolean valuesAreIdentical(Value value, Value other) {
+ value = value.getAliasedValue();
+ other = other.getAliasedValue();
+ if (value == other) {
+ return true;
+ }
+ if (value.isPhi() || other.isPhi()) {
+ return false;
+ }
+ return instructionsDefineIdenticalValues(value.definition, other.definition);
+ }
+
+ private boolean instructionsDefineIdenticalValues(Instruction instruction, Instruction other) {
+ assert instruction.hasOutValue();
+ assert other.hasOutValue();
+
+ Value outValue = instruction.outValue();
+ Value otherOutValue = other.outValue();
+ if (!outValue.getTypeLattice().equals(otherOutValue.getTypeLattice())) {
+ return false;
+ }
+
+ if (instruction.isConstClass()) {
+ if (!other.isConstClass()) {
+ return false;
+ }
+ ConstClass constClassInstruction = instruction.asConstClass();
+ ConstClass otherConstClassInstruction = other.asConstClass();
+ return constClassInstruction.getValue() == otherConstClassInstruction.getValue();
+ }
+
+ if (instruction.isConstNumber()) {
+ if (!other.isConstNumber()) {
+ return false;
+ }
+ ConstNumber constNumberInstruction = instruction.asConstNumber();
+ ConstNumber otherConstNumberInstruction = other.asConstNumber();
+ return constNumberInstruction.getRawValue() == otherConstNumberInstruction.getRawValue();
+ }
+
+ if (instruction.isConstString()) {
+ if (!other.isConstString()) {
+ return false;
+ }
+ ConstString constStringInstruction = instruction.asConstString();
+ ConstString otherConstStringInstruction = other.asConstString();
+ return constStringInstruction.getValue() == otherConstStringInstruction.getValue();
+ }
+
+ if (instruction.isDexItemBasedConstString()) {
+ if (!other.isDexItemBasedConstString()) {
+ return false;
+ }
+ DexItemBasedConstString constStringInstruction = instruction.asDexItemBasedConstString();
+ DexItemBasedConstString otherConstStringInstruction = other.asDexItemBasedConstString();
+ return constStringInstruction.getItem() == otherConstStringInstruction.getItem();
+ }
+
+ return false;
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java b/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
index 8194593..af2aeba 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
@@ -31,6 +31,7 @@
import com.android.tools.r8.graph.ParameterUsagesInfo.ParameterUsage;
import com.android.tools.r8.graph.ParameterUsagesInfo.ParameterUsageBuilder;
import com.android.tools.r8.ir.analysis.ClassInitializationAnalysis.AnalysisAssumption;
+import com.android.tools.r8.ir.analysis.equivalence.BasicBlockBehavioralSubsumption;
import com.android.tools.r8.ir.analysis.type.Nullability;
import com.android.tools.r8.ir.analysis.type.TypeAnalysis;
import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
@@ -940,6 +941,8 @@
IRCode code, Switch theSwitch, InstructionListIterator iterator) {
BasicBlock defaultTarget = theSwitch.fallthroughBlock();
SwitchCaseEliminator eliminator = null;
+ BasicBlockBehavioralSubsumption behavioralSubsumption =
+ new BasicBlockBehavioralSubsumption(appView, code.method.method.holder);
// Compute the set of switch cases that can be removed.
for (int i = 0; i < theSwitch.numberOfKeys(); i++) {
@@ -947,8 +950,8 @@
// This switch case can be removed if the behavior of the target block is equivalent to the
// behavior of the default block, or if the switch case is unreachable.
- if (basicBlockCanBeReplacedBy(code, targetBlock, defaultTarget)
- || switchCaseIsUnreachable(theSwitch, i)) {
+ if (switchCaseIsUnreachable(theSwitch, i)
+ || behavioralSubsumption.isSubsumedBy(targetBlock, defaultTarget)) {
if (eliminator == null) {
eliminator = new SwitchCaseEliminator(theSwitch, iterator);
}
@@ -961,11 +964,6 @@
return eliminator;
}
- private boolean basicBlockCanBeReplacedBy(IRCode code, BasicBlock block, BasicBlock replacement) {
- // TODO(b/132420434): TBD.
- return false;
- }
-
private boolean switchCaseIsUnreachable(Switch theSwitch, int index) {
Value switchValue = theSwitch.value();
return switchValue.hasValueRange()
diff --git a/src/main/java/com/android/tools/r8/utils/SetUtils.java b/src/main/java/com/android/tools/r8/utils/SetUtils.java
index f910740..c6e8bea 100644
--- a/src/main/java/com/android/tools/r8/utils/SetUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/SetUtils.java
@@ -10,6 +10,12 @@
public class SetUtils {
+ public static <T> Set<T> newIdentityHashSet(T element) {
+ Set<T> result = Sets.newIdentityHashSet();
+ result.add(element);
+ return result;
+ }
+
public static <T> Set<T> newIdentityHashSet(Collection<T> c) {
Set<T> result = Sets.newIdentityHashSet();
result.addAll(c);
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/SwitchCaseRemovalTest.java b/src/test/java/com/android/tools/r8/ir/optimize/SwitchCaseRemovalTest.java
index 3dbf05f..74f9f43 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/SwitchCaseRemovalTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/SwitchCaseRemovalTest.java
@@ -71,14 +71,10 @@
MethodSubject methodSubject = classSubject.uniqueMethodWithName("testSwitchCaseRemoval");
assertThat(methodSubject, isPresent());
assertEquals(
- parameters.isCfRuntime() ? 2 : 1,
- methodSubject.streamInstructions().filter(InstructionSubject::isConstNull).count());
+ 1, methodSubject.streamInstructions().filter(InstructionSubject::isConstNull).count());
assertEquals(
- parameters.isCfRuntime() ? 3 : 2,
- methodSubject.streamInstructions().filter(InstructionSubject::isReturnObject).count());
- verifyUniqueSwitchHasExactCases(
- methodSubject.buildIR(),
- parameters.isCfRuntime() ? ImmutableSet.of(0, 1) : ImmutableSet.of(0));
+ 2, methodSubject.streamInstructions().filter(InstructionSubject::isReturnObject).count());
+ verifyUniqueSwitchHasExactCases(methodSubject.buildIR(), ImmutableSet.of(0));
}
{
diff --git a/src/test/java/com/android/tools/r8/rewrite/switches/SwitchRewritingTest.java b/src/test/java/com/android/tools/r8/rewrite/switches/SwitchRewritingTest.java
index 12562ac..37c3bc3 100644
--- a/src/test/java/com/android/tools/r8/rewrite/switches/SwitchRewritingTest.java
+++ b/src/test/java/com/android/tools/r8/rewrite/switches/SwitchRewritingTest.java
@@ -149,10 +149,12 @@
" return-void"
);
- Consumer<InternalOptions> optionsConsumer = options -> {
- options.verbose = true;
- options.printTimes = true;
- };
+ Consumer<InternalOptions> optionsConsumer =
+ options -> {
+ options.testing.enableDeadSwitchCaseElimination = false;
+ options.verbose = true;
+ options.printTimes = true;
+ };
AndroidApp originalApplication = buildApplication(builder);
AndroidApp processedApplication = processApplication(originalApplication, optionsConsumer);
DexEncodedMethod method = getMethod(processedApplication, signature);
