Don't use flow-sensative assumptions in branch subsumption.
Bug: b/259298098
Change-Id: Iffab3ad73bcd1c6726a756d80c284562cc3935da
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
index e901e23..d274600 100644
--- 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
@@ -4,12 +4,10 @@
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.DexClassAndMethod;
import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.ir.code.Assume;
import com.android.tools.r8.ir.code.BasicBlock;
import com.android.tools.r8.ir.code.ConstClass;
import com.android.tools.r8.ir.code.ConstNumber;
@@ -23,8 +21,10 @@
import com.android.tools.r8.ir.code.Return;
import com.android.tools.r8.ir.code.Value;
import com.android.tools.r8.utils.SetUtils;
+import com.android.tools.r8.utils.WorkList;
import java.util.List;
import java.util.Set;
+import java.util.function.Predicate;
/**
* Analysis that can be used to determine if the behavior of one basic block is subsumed by the
@@ -45,19 +45,59 @@
this.context = code.context();
}
- public boolean isSubsumedBy(BasicBlock block, BasicBlock other) {
- return isSubsumedBy(block.iterator(), other.iterator(), null);
+ public boolean isSubsumedBy(Value conditionValue, BasicBlock block, BasicBlock other) {
+ return isSubsumedBy(conditionValue, block.iterator(), other.iterator(), null);
+ }
+
+ private boolean dependsOnConditionValue(Value conditionValue, Instruction instruction) {
+ if (instruction.isAssume()) {
+ // Assume instructions are just virtual alias instructions so they are not materializing uses.
+ return false;
+ }
+ WorkList<Assume> assumptionUses = null;
+ for (Value value : instruction.inValues()) {
+ Assume assumption = value.isPhi() ? null : value.getDefinition().asAssume();
+ if (assumption != null) {
+ if (assumptionUses == null) {
+ assumptionUses = WorkList.newIdentityWorkList();
+ }
+ assumptionUses.addIfNotSeen(assumption);
+ }
+ }
+ if (assumptionUses != null) {
+ while (assumptionUses.hasNext()) {
+ Assume next = assumptionUses.next();
+ for (Value assumptionArgument : next.inValues()) {
+ if (assumptionArgument == conditionValue) {
+ return true;
+ }
+ Assume indirectAssumption =
+ assumptionArgument.isPhi() ? null : assumptionArgument.getDefinition().asAssume();
+ if (indirectAssumption != null) {
+ assumptionUses.addIfNotSeen(indirectAssumption);
+ }
+ }
+ }
+ }
+ return false;
+ }
+
+ private Instruction skipNonDependentInstructionsUntil(
+ InstructionIterator iterator, Value conditionValue, Predicate<Instruction> predicate) {
+ return iterator.nextUntil(
+ predicate.or(i -> i.isJumpInstruction() || dependsOnConditionValue(conditionValue, i)));
}
private boolean isSubsumedBy(
- InstructionIterator iterator, InstructionIterator otherIterator, Set<BasicBlock> visited) {
+ Value conditionValue,
+ 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));
+ skipNonDependentInstructionsUntil(
+ iterator, conditionValue, this::isNonLocalDefinitionOrSideEffecting);
// 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
@@ -68,8 +108,8 @@
// Skip over non-throwing instructions in the other block.
Instruction otherInstruction =
- otherIterator.nextUntil(
- or(this::instructionMayHaveSideEffects, Instruction::isJumpInstruction));
+ skipNonDependentInstructionsUntil(
+ otherIterator, conditionValue, this::instructionMayHaveSideEffects);
assert otherInstruction != null;
if (instruction.isGoto()) {
@@ -101,7 +141,7 @@
visited = SetUtils.newIdentityHashSet(instruction.getBlock());
}
if (visited.add(targetBlock)) {
- return isSubsumedBy(targetBlock.iterator(), otherIterator, visited);
+ return isSubsumedBy(conditionValue, targetBlock.iterator(), otherIterator, visited);
}
// Guard against cycles in the control flow graph.
return false;
@@ -125,8 +165,8 @@
otherIterator = targetBlock.iterator();
otherInstruction =
- otherIterator.nextUntil(
- or(this::instructionMayHaveSideEffects, Instruction::isJumpInstruction));
+ skipNonDependentInstructionsUntil(
+ otherIterator, conditionValue, this::instructionMayHaveSideEffects);
// If following the first goto instruction leads to another goto instruction, then we need to
// keep track of the set of visited blocks to guard against cycles in the control flow graph.
@@ -150,7 +190,7 @@
|| otherSingleTarget.getDefinition().getOptimizationInfo().mayHaveSideEffects()) {
return false;
}
- return isSubsumedBy(iterator, otherIterator, visited);
+ return isSubsumedBy(conditionValue, iterator, otherIterator, visited);
}
return false;
}
@@ -172,8 +212,8 @@
return false;
}
- private boolean isBlockLocalInstructionWithoutSideEffects(Instruction instruction) {
- return definesBlockLocalValue(instruction) && !instructionMayHaveSideEffects(instruction);
+ private boolean isNonLocalDefinitionOrSideEffecting(Instruction instruction) {
+ return !definesBlockLocalValue(instruction) || instructionMayHaveSideEffects(instruction);
}
private boolean definesBlockLocalValue(Instruction instruction) {
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 1d4e435..f0ca38f 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
@@ -1135,7 +1135,8 @@
// behavior of the default block, or if the switch case is unreachable.
if (switchCaseAnalyzer.switchCaseIsUnreachable(theSwitch, switchAbstractValue, i)) {
eliminator.markSwitchCaseForRemoval(i);
- } else if (behavioralSubsumption.isSubsumedBy(targetBlock, defaultTarget)) {
+ } else if (behavioralSubsumption.isSubsumedBy(
+ theSwitch.value(), targetBlock, defaultTarget)) {
eliminator.markSwitchCaseForRemoval(i);
hasSwitchCaseToDefaultRewrite = true;
}
@@ -2642,7 +2643,8 @@
// Unable to determine which branch will be taken. Check if the true target can safely be
// rewritten to the false target.
- if (behavioralSubsumption.isSubsumedBy(theIf.getTrueTarget(), theIf.fallthroughBlock())) {
+ if (behavioralSubsumption.isSubsumedBy(
+ theIf.inValues().get(0), theIf.getTrueTarget(), theIf.fallthroughBlock())) {
simplifyIfWithKnownCondition(code, block, theIf, theIf.fallthroughBlock());
simplified = true;
}
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 6be9cc3..834a3df 100644
--- a/src/main/java/com/android/tools/r8/utils/SetUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/SetUtils.java
@@ -16,6 +16,9 @@
public class SetUtils {
public static <T> boolean containsAnyOf(Set<T> set, Iterable<T> elements) {
+ if (set.isEmpty()) {
+ return false;
+ }
for (T element : elements) {
if (set.contains(element)) {
return true;
