Generalize switch rewriting to string switches
This also extends the switch rewriting to optimize switches where a single case is guaranteed to be hit into a goto instruction.
Change-Id: I5b0cc53425a63a75f59e368929997f79dfc33695
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedMessageLiteBuilderShrinker.java b/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedMessageLiteBuilderShrinker.java
index 0801f16..0d2362b 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedMessageLiteBuilderShrinker.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/proto/GeneratedMessageLiteBuilderShrinker.java
@@ -20,8 +20,8 @@
import com.android.tools.r8.ir.code.IRCode;
import com.android.tools.r8.ir.code.Instruction;
import com.android.tools.r8.ir.code.InstructionListIterator;
-import com.android.tools.r8.ir.code.IntSwitch;
import com.android.tools.r8.ir.code.InvokeVirtual;
+import com.android.tools.r8.ir.code.Switch;
import com.android.tools.r8.ir.code.Value;
import com.android.tools.r8.ir.conversion.CallGraph.Node;
import com.android.tools.r8.ir.conversion.IRConverter;
@@ -263,7 +263,11 @@
}
@Override
- public boolean switchCaseIsUnreachable(IntSwitch theSwitch, int index) {
+ public boolean switchCaseIsUnreachable(Switch theSwitch, int index) {
+ if (theSwitch.isStringSwitch()) {
+ assert false : "Unexpected string-switch instruction in dynamicMethod()";
+ return false;
+ }
if (index != newBuilderOrdinal) {
return false;
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/IRCode.java b/src/main/java/com/android/tools/r8/ir/code/IRCode.java
index 268c065..c9d0d84 100644
--- a/src/main/java/com/android/tools/r8/ir/code/IRCode.java
+++ b/src/main/java/com/android/tools/r8/ir/code/IRCode.java
@@ -3,11 +3,14 @@
// BSD-style license that can be found in the LICENSE file.
package com.android.tools.r8.ir.code;
+import static com.android.tools.r8.ir.analysis.type.Nullability.definitelyNotNull;
+
import com.android.tools.r8.errors.Unreachable;
import com.android.tools.r8.graph.AppInfoWithSubtyping;
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.DebugLocalInfo;
import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexString;
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.graph.classmerging.VerticallyMergedClasses;
import com.android.tools.r8.ir.analysis.TypeChecker;
@@ -15,6 +18,7 @@
import com.android.tools.r8.ir.analysis.type.ClassTypeElement;
import com.android.tools.r8.ir.analysis.type.Nullability;
import com.android.tools.r8.ir.analysis.type.TypeElement;
+import com.android.tools.r8.ir.code.BasicBlock.ThrowingInfo;
import com.android.tools.r8.ir.code.Phi.RegisterReadType;
import com.android.tools.r8.ir.conversion.IRBuilder;
import com.android.tools.r8.origin.Origin;
@@ -1098,6 +1102,16 @@
return new ConstNumber(out, value);
}
+ public ConstString createStringConstant(AppView<?> appView, DexString value) {
+ return createStringConstant(appView, value, null);
+ }
+
+ public ConstString createStringConstant(
+ AppView<?> appView, DexString value, DebugLocalInfo local) {
+ Value out = createValue(TypeElement.stringClassType(appView, definitelyNotNull()), local);
+ return new ConstString(out, value, ThrowingInfo.defaultForConstString(appView.options()));
+ }
+
public Phi createPhi(BasicBlock block, TypeElement type) {
return new Phi(valueNumberGenerator.next(), block, type, null, RegisterReadType.NORMAL);
}
@@ -1107,8 +1121,7 @@
}
public ConstClass createConstClass(AppView<?> appView, DexType type) {
- Value out =
- createValue(TypeElement.fromDexType(type, Nullability.definitelyNotNull(), appView));
+ Value out = createValue(TypeElement.fromDexType(type, definitelyNotNull(), appView));
return new ConstClass(out, type);
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/IRMetadata.java b/src/main/java/com/android/tools/r8/ir/code/IRMetadata.java
index e46af2c..c562fe7 100644
--- a/src/main/java/com/android/tools/r8/ir/code/IRMetadata.java
+++ b/src/main/java/com/android/tools/r8/ir/code/IRMetadata.java
@@ -250,6 +250,16 @@
return get(Opcodes.SUB);
}
+ @SuppressWarnings("ConstantConditions")
+ public boolean mayHaveSwitch() {
+ assert Opcodes.INT_SWITCH < 64;
+ assert Opcodes.STRING_SWITCH < 64;
+ long mask = (1L << Opcodes.INT_SWITCH) | (1L << Opcodes.STRING_SWITCH);
+ boolean result = isAnySetInFirst(mask);
+ assert result == (mayHaveIntSwitch() || mayHaveStringSwitch());
+ return result;
+ }
+
public boolean mayHaveUshr() {
return get(Opcodes.USHR);
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/IntSwitch.java b/src/main/java/com/android/tools/r8/ir/code/IntSwitch.java
index f22ef1c..d5a83f5 100644
--- a/src/main/java/com/android/tools/r8/ir/code/IntSwitch.java
+++ b/src/main/java/com/android/tools/r8/ir/code/IntSwitch.java
@@ -14,6 +14,7 @@
import com.android.tools.r8.code.SparseSwitch;
import com.android.tools.r8.code.SparseSwitchPayload;
import com.android.tools.r8.dex.Constants;
+import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.ir.conversion.CfBuilder;
import com.android.tools.r8.ir.conversion.DexBuilder;
import com.android.tools.r8.utils.CfgPrinter;
@@ -51,6 +52,11 @@
}
@Override
+ public Instruction materializeFirstKey(AppView<?> appView, IRCode code) {
+ return code.createIntConstant(getFirstKey());
+ }
+
+ @Override
public boolean valid() {
assert super.valid();
assert keys.length >= 1;
diff --git a/src/main/java/com/android/tools/r8/ir/code/StringSwitch.java b/src/main/java/com/android/tools/r8/ir/code/StringSwitch.java
index 1b3d673..05acba1 100644
--- a/src/main/java/com/android/tools/r8/ir/code/StringSwitch.java
+++ b/src/main/java/com/android/tools/r8/ir/code/StringSwitch.java
@@ -7,6 +7,7 @@
import com.android.tools.r8.cf.LoadStoreHelper;
import com.android.tools.r8.dex.Constants;
import com.android.tools.r8.errors.Unreachable;
+import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.DexString;
import com.android.tools.r8.ir.conversion.CfBuilder;
import com.android.tools.r8.ir.conversion.DexBuilder;
@@ -23,6 +24,10 @@
assert valid();
}
+ public DexString getFirstKey() {
+ return keys[0];
+ }
+
@Override
public int opcode() {
return Opcodes.STRING_SWITCH;
@@ -40,6 +45,11 @@
}
@Override
+ public Instruction materializeFirstKey(AppView<?> appView, IRCode code) {
+ return code.createStringConstant(appView, getFirstKey());
+ }
+
+ @Override
public boolean valid() {
assert super.valid();
assert keys.length >= 1;
diff --git a/src/main/java/com/android/tools/r8/ir/code/Switch.java b/src/main/java/com/android/tools/r8/ir/code/Switch.java
index 8dcb6a4..4e129aa 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Switch.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Switch.java
@@ -4,6 +4,7 @@
package com.android.tools.r8.ir.code;
+import com.android.tools.r8.graph.AppView;
import java.util.function.Consumer;
public abstract class Switch extends JumpInstruction {
@@ -17,6 +18,8 @@
this.fallthroughBlockIndex = fallthroughBlockIndex;
}
+ public abstract Instruction materializeFirstKey(AppView<?> appView, IRCode code);
+
public Value value() {
return inValues.get(0);
}
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 9f34126..eb36e39 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
@@ -948,7 +948,7 @@
}
public boolean rewriteSwitch(IRCode code, SwitchCaseAnalyzer switchCaseAnalyzer) {
- if (!code.metadata().mayHaveIntSwitch()) {
+ if (!code.metadata().mayHaveSwitch()) {
return false;
}
@@ -959,8 +959,8 @@
InstructionListIterator iterator = block.listIterator(code);
while (iterator.hasNext()) {
Instruction instruction = iterator.next();
- if (instruction.isIntSwitch()) {
- IntSwitch theSwitch = instruction.asIntSwitch();
+ if (instruction.isSwitch()) {
+ Switch theSwitch = instruction.asSwitch();
if (options.testing.enableDeadSwitchCaseElimination) {
SwitchCaseEliminator eliminator =
removeUnnecessarySwitchCases(code, theSwitch, iterator, switchCaseAnalyzer);
@@ -975,119 +975,12 @@
continue;
}
- assert instruction.isIntSwitch();
- theSwitch = instruction.asIntSwitch();
+ assert instruction.isSwitch();
+ theSwitch = instruction.asSwitch();
}
}
- if (theSwitch.numberOfKeys() == 1) {
- // Rewrite the switch to an if.
- int fallthroughBlockIndex = theSwitch.getFallthroughBlockIndex();
- int caseBlockIndex = theSwitch.targetBlockIndices()[0];
- if (fallthroughBlockIndex < caseBlockIndex) {
- block.swapSuccessorsByIndex(fallthroughBlockIndex, caseBlockIndex);
- }
- if (theSwitch.getFirstKey() == 0) {
- iterator.replaceCurrentInstruction(new If(Type.EQ, theSwitch.value()));
- } else {
- ConstNumber labelConst = code.createIntConstant(theSwitch.getFirstKey());
- labelConst.setPosition(theSwitch.getPosition());
- iterator.previous();
- iterator.add(labelConst);
- Instruction dummy = iterator.next();
- assert dummy == theSwitch;
- If theIf = new If(Type.EQ, ImmutableList.of(theSwitch.value(), labelConst.dest()));
- iterator.replaceCurrentInstruction(theIf);
- }
- } else {
- // If there are more than 1 key, we use the following algorithm to find keys to combine.
- // First, scan through the keys forward and combine each packed interval with the
- // previous interval if it gives a net saving.
- // Secondly, go through all created intervals and combine the ones without a saving into
- // a single interval and keep a max number of packed switches.
- // Finally, go through all intervals and check if the switch or part of the switch
- // should be transformed to ifs.
-
- // Phase 1: Combine packed intervals.
- InternalOutputMode mode = options.getInternalOutputMode();
- int[] keys = theSwitch.getKeys();
- int maxNumberOfIfsOrSwitches = 10;
- PriorityQueue<Interval> biggestPackedSavings =
- new PriorityQueue<>(
- (x, y) -> Long.compare(y.packedSavings(mode), x.packedSavings(mode)));
- Set<Interval> biggestPackedSet = new HashSet<>();
- List<Interval> intervals = new ArrayList<>();
- int previousKey = keys[0];
- IntList currentKeys = new IntArrayList();
- currentKeys.add(previousKey);
- Interval previousInterval = null;
- for (int i = 1; i < keys.length; i++) {
- int key = keys[i];
- if (((long) key - (long) previousKey) > 1) {
- Interval current = new Interval(currentKeys);
- Interval added = combineOrAddInterval(intervals, previousInterval, current);
- if (added != current && biggestPackedSet.contains(previousInterval)) {
- biggestPackedSet.remove(previousInterval);
- biggestPackedSavings.remove(previousInterval);
- }
- tryAddToBiggestSavings(
- biggestPackedSet, biggestPackedSavings, added, maxNumberOfIfsOrSwitches);
- previousInterval = added;
- currentKeys = new IntArrayList();
- }
- currentKeys.add(key);
- previousKey = key;
- }
- Interval current = new Interval(currentKeys);
- Interval added = combineOrAddInterval(intervals, previousInterval, current);
- if (added != current && biggestPackedSet.contains(previousInterval)) {
- biggestPackedSet.remove(previousInterval);
- biggestPackedSavings.remove(previousInterval);
- }
- tryAddToBiggestSavings(
- biggestPackedSet, biggestPackedSavings, added, maxNumberOfIfsOrSwitches);
-
- // Phase 2: combine sparse intervals into a single bin.
- // Check if we should save a space for a sparse switch, if so, remove the switch with
- // the smallest savings.
- if (biggestPackedSet.size() == maxNumberOfIfsOrSwitches
- && maxNumberOfIfsOrSwitches < intervals.size()) {
- biggestPackedSet.remove(biggestPackedSavings.poll());
- }
- Interval sparse = null;
- List<Interval> newSwitches = new ArrayList<>(maxNumberOfIfsOrSwitches);
- for (int i = 0; i < intervals.size(); i++) {
- Interval interval = intervals.get(i);
- if (biggestPackedSet.contains(interval)) {
- newSwitches.add(interval);
- } else if (sparse == null) {
- sparse = interval;
- newSwitches.add(sparse);
- } else {
- sparse.addInterval(interval);
- }
- }
-
- // Phase 3: at this point we are guaranteed to have the biggest saving switches
- // in newIntervals, potentially with a switch combining the remaining intervals.
- // Now we check to see if we can create any if's to reduce size.
- IntList outliers = new IntArrayList();
- int outliersAsIfSize =
- appView.options().testing.enableSwitchToIfRewriting
- ? findIfsForCandidates(newSwitches, theSwitch, outliers)
- : 0;
-
- long newSwitchesSize = 0;
- List<IntList> newSwitchSequences = new ArrayList<>(newSwitches.size());
- for (Interval interval : newSwitches) {
- newSwitchesSize += interval.estimatedSize(mode);
- newSwitchSequences.add(interval.keys);
- }
-
- long currentSize = IntSwitch.estimatedSize(mode, theSwitch.getKeys());
- if (newSwitchesSize + outliersAsIfSize + codeUnitMargin() < currentSize) {
- convertSwitchToSwitchAndIfs(
- code, blocksIterator, block, iterator, theSwitch, newSwitchSequences, outliers);
- }
+ if (theSwitch.isIntSwitch()) {
+ rewriteIntSwitch(code, blocksIterator, block, iterator, theSwitch.asIntSwitch());
}
}
}
@@ -1107,9 +1000,127 @@
return !affectedValues.isEmpty();
}
+ private void rewriteIntSwitch(
+ IRCode code,
+ ListIterator<BasicBlock> blockIterator,
+ BasicBlock block,
+ InstructionListIterator iterator,
+ IntSwitch theSwitch) {
+ if (theSwitch.numberOfKeys() == 1) {
+ // Rewrite the switch to an if.
+ int fallthroughBlockIndex = theSwitch.getFallthroughBlockIndex();
+ int caseBlockIndex = theSwitch.targetBlockIndices()[0];
+ if (fallthroughBlockIndex < caseBlockIndex) {
+ block.swapSuccessorsByIndex(fallthroughBlockIndex, caseBlockIndex);
+ }
+ If replacement;
+ if (theSwitch.isIntSwitch() && theSwitch.asIntSwitch().getFirstKey() == 0) {
+ replacement = new If(Type.EQ, theSwitch.value());
+ } else {
+ Instruction labelConst = theSwitch.materializeFirstKey(appView, code);
+ labelConst.setPosition(theSwitch.getPosition());
+ iterator.previous();
+ iterator.add(labelConst);
+ Instruction dummy = iterator.next();
+ assert dummy == theSwitch;
+ replacement = new If(Type.EQ, ImmutableList.of(theSwitch.value(), labelConst.outValue()));
+ }
+ iterator.replaceCurrentInstruction(replacement);
+ return;
+ }
+
+ // If there are more than 1 key, we use the following algorithm to find keys to combine.
+ // First, scan through the keys forward and combine each packed interval with the
+ // previous interval if it gives a net saving.
+ // Secondly, go through all created intervals and combine the ones without a saving into
+ // a single interval and keep a max number of packed switches.
+ // Finally, go through all intervals and check if the switch or part of the switch
+ // should be transformed to ifs.
+
+ // Phase 1: Combine packed intervals.
+ InternalOutputMode mode = options.getInternalOutputMode();
+ int[] keys = theSwitch.getKeys();
+ int maxNumberOfIfsOrSwitches = 10;
+ PriorityQueue<Interval> biggestPackedSavings =
+ new PriorityQueue<>((x, y) -> Long.compare(y.packedSavings(mode), x.packedSavings(mode)));
+ Set<Interval> biggestPackedSet = new HashSet<>();
+ List<Interval> intervals = new ArrayList<>();
+ int previousKey = keys[0];
+ IntList currentKeys = new IntArrayList();
+ currentKeys.add(previousKey);
+ Interval previousInterval = null;
+ for (int i = 1; i < keys.length; i++) {
+ int key = keys[i];
+ if (((long) key - (long) previousKey) > 1) {
+ Interval current = new Interval(currentKeys);
+ Interval added = combineOrAddInterval(intervals, previousInterval, current);
+ if (added != current && biggestPackedSet.contains(previousInterval)) {
+ biggestPackedSet.remove(previousInterval);
+ biggestPackedSavings.remove(previousInterval);
+ }
+ tryAddToBiggestSavings(
+ biggestPackedSet, biggestPackedSavings, added, maxNumberOfIfsOrSwitches);
+ previousInterval = added;
+ currentKeys = new IntArrayList();
+ }
+ currentKeys.add(key);
+ previousKey = key;
+ }
+ Interval current = new Interval(currentKeys);
+ Interval added = combineOrAddInterval(intervals, previousInterval, current);
+ if (added != current && biggestPackedSet.contains(previousInterval)) {
+ biggestPackedSet.remove(previousInterval);
+ biggestPackedSavings.remove(previousInterval);
+ }
+ tryAddToBiggestSavings(biggestPackedSet, biggestPackedSavings, added, maxNumberOfIfsOrSwitches);
+
+ // Phase 2: combine sparse intervals into a single bin.
+ // Check if we should save a space for a sparse switch, if so, remove the switch with
+ // the smallest savings.
+ if (biggestPackedSet.size() == maxNumberOfIfsOrSwitches
+ && maxNumberOfIfsOrSwitches < intervals.size()) {
+ biggestPackedSet.remove(biggestPackedSavings.poll());
+ }
+ Interval sparse = null;
+ List<Interval> newSwitches = new ArrayList<>(maxNumberOfIfsOrSwitches);
+ for (int i = 0; i < intervals.size(); i++) {
+ Interval interval = intervals.get(i);
+ if (biggestPackedSet.contains(interval)) {
+ newSwitches.add(interval);
+ } else if (sparse == null) {
+ sparse = interval;
+ newSwitches.add(sparse);
+ } else {
+ sparse.addInterval(interval);
+ }
+ }
+
+ // Phase 3: at this point we are guaranteed to have the biggest saving switches
+ // in newIntervals, potentially with a switch combining the remaining intervals.
+ // Now we check to see if we can create any if's to reduce size.
+ IntList outliers = new IntArrayList();
+ int outliersAsIfSize =
+ appView.options().testing.enableSwitchToIfRewriting
+ ? findIfsForCandidates(newSwitches, theSwitch, outliers)
+ : 0;
+
+ long newSwitchesSize = 0;
+ List<IntList> newSwitchSequences = new ArrayList<>(newSwitches.size());
+ for (Interval interval : newSwitches) {
+ newSwitchesSize += interval.estimatedSize(mode);
+ newSwitchSequences.add(interval.keys);
+ }
+
+ long currentSize = IntSwitch.estimatedSize(mode, theSwitch.getKeys());
+ if (newSwitchesSize + outliersAsIfSize + codeUnitMargin() < currentSize) {
+ convertSwitchToSwitchAndIfs(
+ code, blockIterator, block, iterator, theSwitch, newSwitchSequences, outliers);
+ }
+ }
+
private SwitchCaseEliminator removeUnnecessarySwitchCases(
IRCode code,
- IntSwitch theSwitch,
+ Switch theSwitch,
InstructionListIterator iterator,
SwitchCaseAnalyzer switchCaseAnalyzer) {
BasicBlock defaultTarget = theSwitch.fallthroughBlock();
@@ -1118,9 +1129,18 @@
new BasicBlockBehavioralSubsumption(appView, code.method.holder());
// Compute the set of switch cases that can be removed.
+ int alwaysHitCase = -1;
for (int i = 0; i < theSwitch.numberOfKeys(); i++) {
BasicBlock targetBlock = theSwitch.targetBlock(i);
+ if (switchCaseAnalyzer.switchCaseIsAlwaysHit(theSwitch, i)) {
+ if (eliminator == null) {
+ eliminator = new SwitchCaseEliminator(theSwitch, iterator);
+ }
+ eliminator.markSwitchCaseAsAlwaysHit(i);
+ break;
+ }
+
// 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 (switchCaseAnalyzer.switchCaseIsUnreachable(theSwitch, i)
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/SwitchCaseEliminator.java b/src/main/java/com/android/tools/r8/ir/optimize/SwitchCaseEliminator.java
index 0aabe6e..733db77 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/SwitchCaseEliminator.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/SwitchCaseEliminator.java
@@ -4,10 +4,13 @@
package com.android.tools.r8.ir.optimize;
+import com.android.tools.r8.graph.DexString;
import com.android.tools.r8.ir.code.BasicBlock;
import com.android.tools.r8.ir.code.Goto;
import com.android.tools.r8.ir.code.InstructionListIterator;
import com.android.tools.r8.ir.code.IntSwitch;
+import com.android.tools.r8.ir.code.StringSwitch;
+import com.android.tools.r8.ir.code.Switch;
import it.unimi.dsi.fastutil.ints.IntArrayList;
import it.unimi.dsi.fastutil.ints.IntList;
import it.unimi.dsi.fastutil.ints.IntOpenHashSet;
@@ -21,12 +24,14 @@
private final BasicBlock block;
private final BasicBlock defaultTarget;
private final InstructionListIterator iterator;
- private final IntSwitch theSwitch;
+ private final Switch theSwitch;
+ private int alwaysHitCase = -1;
+ private BasicBlock alwaysHitTarget;
private boolean mayHaveIntroducedUnreachableBlocks = false;
private IntSet switchCasesToBeRemoved;
- SwitchCaseEliminator(IntSwitch theSwitch, InstructionListIterator iterator) {
+ SwitchCaseEliminator(Switch theSwitch, InstructionListIterator iterator) {
this.block = theSwitch.getBlock();
this.defaultTarget = theSwitch.fallthroughBlock();
this.iterator = iterator;
@@ -40,13 +45,34 @@
private boolean canBeOptimized() {
assert switchCasesToBeRemoved == null || !switchCasesToBeRemoved.isEmpty();
- return switchCasesToBeRemoved != null;
+ return switchCasesToBeRemoved != null || hasAlwaysHitCase();
}
boolean mayHaveIntroducedUnreachableBlocks() {
return mayHaveIntroducedUnreachableBlocks;
}
+ public boolean isSwitchCaseLive(int index) {
+ if (hasAlwaysHitCase()) {
+ return index == alwaysHitCase;
+ }
+ return !switchCasesToBeRemoved.contains(index);
+ }
+
+ public boolean isFallthroughLive() {
+ return !hasAlwaysHitCase();
+ }
+
+ public boolean hasAlwaysHitCase() {
+ return alwaysHitCase >= 0;
+ }
+
+ void markSwitchCaseAsAlwaysHit(int i) {
+ assert alwaysHitCase < 0;
+ alwaysHitCase = i;
+ alwaysHitTarget = theSwitch.targetBlock(i);
+ }
+
void markSwitchCaseForRemoval(int i) {
if (switchCasesToBeRemoved == null) {
switchCasesToBeRemoved = new IntOpenHashSet();
@@ -58,8 +84,8 @@
if (canBeOptimized()) {
int originalNumberOfSuccessors = block.getSuccessors().size();
unlinkDeadSuccessors();
- if (allSwitchCasesMarkedForRemoval()) {
- // Replace switch with a simple goto since only the fall through is left.
+ if (hasAlwaysHitCase() || allSwitchCasesMarkedForRemoval()) {
+ // Replace switch with a simple goto.
replaceSwitchByGoto();
} else {
// Replace switch by a new switch where the dead switch cases have been removed.
@@ -90,12 +116,14 @@
private IntPredicate computeSuccessorHasBecomeDeadPredicate() {
int[] numberOfControlFlowEdgesToBlockWithIndex = new int[block.getSuccessors().size()];
for (int i = 0; i < theSwitch.numberOfKeys(); i++) {
- if (!switchCasesToBeRemoved.contains(i)) {
+ if (isSwitchCaseLive(i)) {
int targetBlockIndex = theSwitch.getTargetBlockIndex(i);
numberOfControlFlowEdgesToBlockWithIndex[targetBlockIndex] += 1;
}
}
- numberOfControlFlowEdgesToBlockWithIndex[theSwitch.getFallthroughBlockIndex()] += 1;
+ if (isFallthroughLive()) {
+ numberOfControlFlowEdgesToBlockWithIndex[theSwitch.getFallthroughBlockIndex()] += 1;
+ }
for (int i : block.getCatchHandlersWithSuccessorIndexes().getUniqueTargets()) {
numberOfControlFlowEdgesToBlockWithIndex[i] += 1;
}
@@ -103,7 +131,9 @@
}
private void replaceSwitchByGoto() {
- iterator.replaceCurrentInstruction(new Goto(defaultTarget));
+ assert !hasAlwaysHitCase() || alwaysHitTarget != null;
+ BasicBlock target = hasAlwaysHitCase() ? alwaysHitTarget : defaultTarget;
+ iterator.replaceCurrentInstruction(new Goto(target));
}
private void replaceSwitchByOptimizedSwitch(int originalNumberOfSuccessors) {
@@ -121,11 +151,9 @@
}
int newNumberOfKeys = theSwitch.numberOfKeys() - switchCasesToBeRemoved.size();
- int[] newKeys = new int[newNumberOfKeys];
int[] newTargetBlockIndices = new int[newNumberOfKeys];
for (int i = 0, j = 0; i < theSwitch.numberOfKeys(); i++) {
if (!switchCasesToBeRemoved.contains(i)) {
- newKeys[j] = theSwitch.getKey(i);
newTargetBlockIndices[j] =
theSwitch.getTargetBlockIndex(i)
- targetBlockIndexOffset[theSwitch.getTargetBlockIndex(i)];
@@ -135,12 +163,41 @@
}
}
- iterator.replaceCurrentInstruction(
- new IntSwitch(
- theSwitch.value(),
- newKeys,
- newTargetBlockIndices,
- theSwitch.getFallthroughBlockIndex()
- - targetBlockIndexOffset[theSwitch.getFallthroughBlockIndex()]));
+ Switch replacement;
+ if (theSwitch.isIntSwitch()) {
+ IntSwitch intSwitch = theSwitch.asIntSwitch();
+ int[] newKeys = new int[newNumberOfKeys];
+ for (int i = 0, j = 0; i < theSwitch.numberOfKeys(); i++) {
+ if (!switchCasesToBeRemoved.contains(i)) {
+ newKeys[j] = intSwitch.getKey(i);
+ j++;
+ }
+ }
+ replacement =
+ new IntSwitch(
+ theSwitch.value(),
+ newKeys,
+ newTargetBlockIndices,
+ theSwitch.getFallthroughBlockIndex()
+ - targetBlockIndexOffset[theSwitch.getFallthroughBlockIndex()]);
+ } else {
+ assert theSwitch.isStringSwitch();
+ StringSwitch stringSwitch = theSwitch.asStringSwitch();
+ DexString[] newKeys = new DexString[newNumberOfKeys];
+ for (int i = 0, j = 0; i < theSwitch.numberOfKeys(); i++) {
+ if (!switchCasesToBeRemoved.contains(i)) {
+ newKeys[j] = stringSwitch.getKey(i);
+ j++;
+ }
+ }
+ replacement =
+ new StringSwitch(
+ theSwitch.value(),
+ newKeys,
+ newTargetBlockIndices,
+ theSwitch.getFallthroughBlockIndex()
+ - targetBlockIndexOffset[theSwitch.getFallthroughBlockIndex()]);
+ }
+ iterator.replaceCurrentInstruction(replacement);
}
}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/controlflow/SwitchCaseAnalyzer.java b/src/main/java/com/android/tools/r8/ir/optimize/controlflow/SwitchCaseAnalyzer.java
index 6c22a72..76f63ac 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/controlflow/SwitchCaseAnalyzer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/controlflow/SwitchCaseAnalyzer.java
@@ -4,8 +4,11 @@
package com.android.tools.r8.ir.optimize.controlflow;
-import com.android.tools.r8.ir.code.IntSwitch;
+import com.android.tools.r8.graph.DexString;
+import com.android.tools.r8.ir.code.Instruction;
+import com.android.tools.r8.ir.code.Switch;
import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.utils.LongInterval;
public class SwitchCaseAnalyzer {
@@ -17,9 +20,35 @@
return INSTANCE;
}
- public boolean switchCaseIsUnreachable(IntSwitch theSwitch, int index) {
+ public boolean switchCaseIsAlwaysHit(Switch theSwitch, int index) {
Value switchValue = theSwitch.value();
- return switchValue.hasValueRange()
- && !switchValue.getValueRange().containsValue(theSwitch.getKey(index));
+ if (theSwitch.isIntSwitch()) {
+ LongInterval valueRange = switchValue.getValueRange();
+ return valueRange != null
+ && valueRange.isSingleValue()
+ && valueRange.containsValue(theSwitch.asIntSwitch().getKey(index));
+ }
+
+ assert theSwitch.isStringSwitch();
+
+ Value rootSwitchValue = switchValue.getAliasedValue();
+ DexString key = theSwitch.asStringSwitch().getKey(index);
+ return rootSwitchValue.isDefinedByInstructionSatisfying(Instruction::isConstString)
+ && key == rootSwitchValue.definition.asConstString().getValue();
+ }
+
+ public boolean switchCaseIsUnreachable(Switch theSwitch, int index) {
+ Value switchValue = theSwitch.value();
+ if (theSwitch.isIntSwitch()) {
+ return switchValue.hasValueRange()
+ && !switchValue.getValueRange().containsValue(theSwitch.asIntSwitch().getKey(index));
+ }
+
+ assert theSwitch.isStringSwitch();
+
+ Value rootSwitchValue = switchValue.getAliasedValue();
+ DexString key = theSwitch.asStringSwitch().getKey(index);
+ return rootSwitchValue.isDefinedByInstructionSatisfying(Instruction::isConstString)
+ && key != rootSwitchValue.definition.asConstString().getValue();
}
}
