Improve the switch rewriting
- Split switch into ifs and/or switches (not just ifs and one switch)
- Ensure debug information is kept during rewriting
Saves ~7 KB on framework and ~64 KB on GMS Core V10.
Change-Id: I7d4f94ead500ee69ee3cd3d1a667804e9791f670
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 6def63a..08ab002 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
@@ -13,6 +13,8 @@
import com.android.tools.r8.ir.conversion.DexBuilder;
import com.android.tools.r8.utils.CfgPrinter;
import com.google.common.primitives.Ints;
+import it.unimi.dsi.fastutil.ints.Int2ReferenceAVLTreeMap;
+import it.unimi.dsi.fastutil.ints.Int2ReferenceSortedMap;
import java.util.List;
public class Switch extends JumpInstruction {
@@ -159,6 +161,11 @@
}
}
+ // Estimated size of the resulting dex instruction in code units (excluding the payload).
+ public static int estimatedDexSize() {
+ return 3;
+ }
+
public int numberOfKeys() {
return keys.length;
}
@@ -175,6 +182,14 @@
return targetBlockIndices;
}
+ public Int2ReferenceSortedMap<BasicBlock> getKeyToTargetMap() {
+ Int2ReferenceSortedMap<BasicBlock> result = new Int2ReferenceAVLTreeMap<>();
+ for (int i = 0; i < keys.length; i++) {
+ result.put(getKey(i), targetBlock(i));
+ }
+ return result;
+ }
+
@Override
public BasicBlock fallthroughBlock() {
return getBlock().getSuccessors().get(fallthroughBlockIndex);
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 a758223..7741fda 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
@@ -64,21 +64,23 @@
import com.android.tools.r8.ir.conversion.OptimizationFeedback;
import com.android.tools.r8.ir.optimize.SwitchUtils.EnumSwitchInfo;
import com.android.tools.r8.utils.InternalOptions;
-import com.android.tools.r8.utils.IteratorUtils;
import com.android.tools.r8.utils.LongInterval;
import com.google.common.base.Equivalence;
import com.google.common.base.Equivalence.Wrapper;
import com.google.common.collect.ArrayListMultimap;
import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
import com.google.common.collect.ListMultimap;
import com.google.common.collect.Maps;
import it.unimi.dsi.fastutil.ints.Int2IntArrayMap;
import it.unimi.dsi.fastutil.ints.Int2IntMap;
import it.unimi.dsi.fastutil.ints.Int2ObjectAVLTreeMap;
import it.unimi.dsi.fastutil.ints.Int2ObjectSortedMap;
+import it.unimi.dsi.fastutil.ints.Int2ReferenceSortedMap;
import it.unimi.dsi.fastutil.ints.IntArrayList;
import it.unimi.dsi.fastutil.ints.IntIterator;
import it.unimi.dsi.fastutil.ints.IntList;
+import it.unimi.dsi.fastutil.ints.IntLists;
import it.unimi.dsi.fastutil.objects.Object2IntLinkedOpenHashMap;
import it.unimi.dsi.fastutil.objects.Object2IntMap;
import java.util.ArrayList;
@@ -344,11 +346,25 @@
}
// TODO(sgjesse); Move this somewhere else, and reuse it for some of the other switch rewritings.
- public static class SwitchBuilder {
+ public abstract static class InstructionBuilder<T> {
+ protected int blockNumber;
+
+ public abstract T self();
+
+ public T setBlockNumber(int blockNumber) {
+ this.blockNumber = blockNumber;
+ return self();
+ }
+ }
+
+ public static class SwitchBuilder extends InstructionBuilder<SwitchBuilder> {
private Value value;
private Int2ObjectSortedMap<BasicBlock> keyToTarget = new Int2ObjectAVLTreeMap<>();
private BasicBlock fallthrough;
- private int blockNumber;
+
+ public SwitchBuilder self() {
+ return this;
+ }
public SwitchBuilder setValue(Value value) {
this.value = value;
@@ -365,11 +381,6 @@
return this;
}
- public SwitchBuilder setBlockNumber(int blockNumber) {
- this.blockNumber = blockNumber;
- return this;
- }
-
public BasicBlock build() {
final int NOT_FOUND = -1;
Object2IntMap<BasicBlock> targetToSuccessorIndex = new Object2IntLinkedOpenHashMap<>();
@@ -400,65 +411,134 @@
}
}
+ public static class IfBuilder extends InstructionBuilder<IfBuilder> {
+ private final IRCode code;
+ private Value left;
+ private int right;
+ private BasicBlock target;
+ private BasicBlock fallthrough;
+ private int blockNumber;
+
+ public IfBuilder(IRCode code) {
+ this.code = code;
+ }
+
+ public IfBuilder self() {
+ return this;
+ }
+
+ public IfBuilder setLeft(Value left) {
+ this.left = left;
+ return this;
+ }
+
+ public IfBuilder setRight(int right) {
+ this.right = right;
+ return this;
+ }
+
+ public IfBuilder setTarget(BasicBlock target) {
+ this.target = target;
+ return this;
+ }
+
+ public IfBuilder setFallthrough(BasicBlock fallthrough) {
+ this.fallthrough = fallthrough;
+ return this;
+ }
+
+ public BasicBlock build() {
+ assert target != null;
+ assert fallthrough != null;
+ If newIf;
+ BasicBlock ifBlock;
+ if (right != 0) {
+ ConstNumber rightConst = code.createIntConstant(right);
+ newIf = new If(Type.EQ, ImmutableList.of(left, rightConst.dest()));
+ ifBlock = BasicBlock.createIfBlock(blockNumber, newIf, rightConst);
+ } else {
+ newIf = new If(Type.EQ, left);
+ ifBlock = BasicBlock.createIfBlock(blockNumber, newIf);
+ }
+ ifBlock.link(target);
+ ifBlock.link(fallthrough);
+ return ifBlock;
+ }
+ }
+
/**
* Covert the switch instruction to a sequence of if instructions checking for a specified
* set of keys, followed by a new switch with the remaining keys.
*/
private void convertSwitchToSwitchAndIfs(
IRCode code, ListIterator<BasicBlock> blocksIterator, BasicBlock originalBlock,
- InstructionListIterator iterator, Switch theSwitch, List<Integer> keysToRemove) {
+ InstructionListIterator iterator, Switch theSwitch,
+ List<IntList> switches, IntList keysToRemove) {
+
+ // Extract the information from the switch before removing it.
+ Int2ReferenceSortedMap<BasicBlock> keyToTarget = theSwitch.getKeyToTargetMap();
+ Set<Value> originalDebugValues = ImmutableSet.copyOf(theSwitch.getDebugValues());
+
// Split the switch instruction into its own block and remove it.
iterator.previous();
BasicBlock originalSwitchBlock = iterator.split(code, blocksIterator);
assert !originalSwitchBlock.hasCatchHandlers();
assert originalSwitchBlock.getInstructions().size() == 1;
blocksIterator.remove();
-
- int nextBlockNumber = code.getHighestBlockNumber() + 1;
-
- // Collect targets for the keys to peel off, and create a new switch instruction without
- // these keys.
- SwitchBuilder switchBuilder = new SwitchBuilder();
- List<BasicBlock> peeledOffTargets = new ArrayList<>();
- for (int i = 0; i < theSwitch.numberOfKeys(); i++) {
- BasicBlock target = theSwitch.targetBlock(i);
- if (!keysToRemove.contains(theSwitch.getKey(i))) {
- switchBuilder.addKeyAndTarget(theSwitch.getKey(i), theSwitch.targetBlock(i));
- } else {
- peeledOffTargets.add(target);
- }
- }
- assert peeledOffTargets.size() == keysToRemove.size();
- switchBuilder.setValue(theSwitch.value());
- switchBuilder.setFallthrough(theSwitch.fallthroughBlock());
- switchBuilder.setBlockNumber(nextBlockNumber++);
theSwitch.getBlock().detachAllSuccessors();
BasicBlock block = theSwitch.getBlock().unlinkSinglePredecessor();
assert theSwitch.getBlock().getPredecessors().size() == 0;
assert theSwitch.getBlock().getSuccessors().size() == 0;
assert block == originalBlock;
- BasicBlock newSwitchBlock = switchBuilder.build();
+ // Collect the new blocks for adding to the block list.
+ int nextBlockNumber = code.getHighestBlockNumber() + 1;
+ LinkedList<BasicBlock> newBlocks = new LinkedList<>();
- // Create if blocks for each of the peeled off keys, and link them into the graph.
- BasicBlock predecessor = originalBlock;
- for (int i = 0; i < keysToRemove.size(); i++) {
- int key = keysToRemove.get(i);
- BasicBlock peeledOffTarget = peeledOffTargets.get(i);
- ConstNumber keyConst = code.createIntConstant(key);
- If theIf = new If(Type.EQ, ImmutableList.of(keyConst.dest(), theSwitch.value()));
- BasicBlock ifBlock = BasicBlock.createIfBlock(nextBlockNumber++, theIf, keyConst);
- predecessor.link(ifBlock);
- ifBlock.link(peeledOffTarget);
- predecessor = ifBlock;
- blocksIterator.add(ifBlock);
- assert !peeledOffTarget.getPredecessors().contains(theSwitch.getBlock());
+ // Keep track of the current fallthrough, starting with the original.
+ BasicBlock fallthroughBlock = theSwitch.fallthroughBlock();
+
+ // Build the switch-blocks backwards, to always have the fallthrough block in hand.
+ for (int i = switches.size() - 1; i >= 0; i--) {
+ SwitchBuilder switchBuilder = new SwitchBuilder();
+ switchBuilder.setValue(theSwitch.value());
+ IntList keys = switches.get(i);
+ for (int j = 0; j < keys.size(); j++) {
+ int key = keys.getInt(j);
+ switchBuilder.addKeyAndTarget(key, keyToTarget.get(key));
+ }
+ switchBuilder
+ .setFallthrough(fallthroughBlock)
+ .setBlockNumber(nextBlockNumber++);
+ BasicBlock newSwitchBlock = switchBuilder.build();
+ newBlocks.addFirst(newSwitchBlock);
+ fallthroughBlock = newSwitchBlock;
}
- predecessor.link(newSwitchBlock);
- blocksIterator.add(newSwitchBlock);
- // The switch fallthrough block is still the same, and it is right after the new switch block.
- assert newSwitchBlock.exit().fallthroughBlock() == IteratorUtils.peekNext(blocksIterator);
+ // Build the if-blocks backwards, to always have the fallthrough block in hand.
+ for (int i = keysToRemove.size() - 1; i >= 0; i--) {
+ int key = keysToRemove.getInt(i);
+ BasicBlock peeledOffTarget = keyToTarget.get(key);
+ IfBuilder ifBuilder = new IfBuilder(code);
+ ifBuilder
+ .setLeft(theSwitch.value())
+ .setRight(key)
+ .setTarget(peeledOffTarget)
+ .setFallthrough(fallthroughBlock)
+ .setBlockNumber(nextBlockNumber++);
+ BasicBlock ifBlock = ifBuilder.build();
+ newBlocks.addFirst(ifBlock);
+ fallthroughBlock = ifBlock;
+ }
+
+ // Attach the debug values from the original switch to the first of the new instructions,
+ originalDebugValues.forEach(fallthroughBlock.exit()::addDebugValue);
+
+ // Finally link the block before the original switch to the new block sequence.
+ originalBlock.link(fallthroughBlock);
+
+ // Finally add the blocks.
+ newBlocks.forEach(blocksIterator::add);
}
public void rewriteSwitch(IRCode code) {
@@ -490,16 +570,16 @@
}
} else {
// Split keys into outliers and sequences.
- List<List<Integer>> sequences = new ArrayList<>();
- List<Integer> outliers = new ArrayList<>();
+ List<IntList> sequences = new ArrayList<>();
+ IntList outliers = new IntArrayList();
- List<Integer> current = new ArrayList<>();
+ IntList current = new IntArrayList();
int[] keys = theSwitch.getKeys();
int previousKey = keys[0];
current.add(previousKey);
for (int i = 1; i < keys.length; i++) {
assert current.size() > 0;
- assert current.get(current.size() - 1) == previousKey;
+ assert current.getInt(current.size() - 1) == previousKey;
int key = keys[i];
if (((long) key - (long) previousKey) > 1) {
if (current.size() == 1) {
@@ -507,7 +587,7 @@
} else {
sequences.add(current);;
}
- current = new ArrayList<>();
+ current = new IntArrayList();
}
current.add(key);
previousKey = key;
@@ -518,22 +598,45 @@
sequences.add(current);
}
- // Only check for rewrite if there is one sequence and one or two outliers.
- if (sequences.size() == 1 && outliers.size() <= 2) {
- // Get the existing dex size for the payload (excluding the switch itself).
- long currentSize = Switch.payloadSize(keys);
- // Estimate the dex size of the rewritten payload and the additional if instructions.
- long rewrittenSize = Switch.payloadSize(sequences.get(0));
+ // Get the existing dex size for the payload and switch.
+ long currentSize = Switch.payloadSize(keys) + Switch.estimatedDexSize();
+
+ // Never replace with more than 10 if/switch instructions.
+ if (outliers.size() + sequences.size() <= 10) {
+ // Calculate estimated size for splitting into ifs and switches.
+ long rewrittenSize = 0;
for (Integer outlier : outliers) {
- rewrittenSize += ConstNumber.estimatedDexSize(
- ConstType.fromMoveType(theSwitch.value().outType()), outlier);
+ if (outlier != 0) {
+ rewrittenSize += ConstNumber.estimatedDexSize(
+ ConstType.fromMoveType(theSwitch.value().outType()), outlier);
+ }
rewrittenSize += If.estimatedDexSize();
}
- // Rewrite if smaller.
+ for (List<Integer> sequence : sequences) {
+ rewrittenSize += Switch.payloadSize(sequence);
+ }
+ rewrittenSize += Switch.estimatedDexSize() * sequences.size();
+
if (rewrittenSize < currentSize) {
convertSwitchToSwitchAndIfs(
- code, blocksIterator, block, iterator, theSwitch, outliers);
- assert code.isConsistentSSA();
+ code, blocksIterator, block, iterator, theSwitch, sequences, outliers);
+ }
+ } else if (outliers.size() > 1) {
+ // Calculate estimated size for splitting into switches (packed for the sequences
+ // and sparse for the outliers).
+ long rewrittenSize = 0;
+ for (List<Integer> sequence : sequences) {
+ rewrittenSize += Switch.payloadSize(sequence);
+ }
+ rewrittenSize += Switch.payloadSize(outliers);
+ rewrittenSize += Switch.estimatedDexSize() * (sequences.size() + 1);
+
+ if (rewrittenSize < currentSize) {
+ // Create a copy to not modify sequences.
+ List<IntList> seqs = new ArrayList<>(sequences);
+ seqs.add(outliers);
+ convertSwitchToSwitchAndIfs(
+ code, blocksIterator, block, iterator, theSwitch, seqs, IntLists.EMPTY_LIST);
}
}
}
diff --git a/src/test/debugTestResources/Locals.java b/src/test/debugTestResources/Locals.java
index 890cb85..109c43e 100644
--- a/src/test/debugTestResources/Locals.java
+++ b/src/test/debugTestResources/Locals.java
@@ -262,6 +262,44 @@
return -1;
}
+ public static int switchRewriteToIfs(int x) {
+ {
+ int t = x + 1;
+ x = t;
+ x = x + x;
+ }
+ switch (x) {
+ case 0:
+ return 0;
+ case 100:
+ return 1;
+ }
+ return -1;
+ }
+
+ public static int switchRewriteToSwitches(int x) {
+ {
+ int t = x + 1;
+ x = t;
+ x = x + x;
+ }
+ switch (x) {
+ case 0:
+ return 0;
+ case 1:
+ return 0;
+ case 2:
+ return 0;
+ case 100:
+ return 1;
+ case 101:
+ return 1;
+ case 102:
+ return 1;
+ }
+ return -1;
+ }
+
public static void main(String[] args) {
noLocals();
unusedLocals();
@@ -278,5 +316,7 @@
tempInCase(42);
localSwap(1, 2);
argumentLiveAtReturn(-1);
+ switchRewriteToIfs(1);
+ switchRewriteToSwitches(1);
}
}
diff --git a/src/test/java/com/android/tools/r8/debug/LocalsTest.java b/src/test/java/com/android/tools/r8/debug/LocalsTest.java
index 6f73f02c..60db262 100644
--- a/src/test/java/com/android/tools/r8/debug/LocalsTest.java
+++ b/src/test/java/com/android/tools/r8/debug/LocalsTest.java
@@ -484,4 +484,48 @@
checkNoLocal("t"),
run());
}
+
+ @Test
+ public void switchRewriteToIfs() throws Throwable {
+ runDebugTest(
+ "Locals",
+ breakpoint("Locals", "switchRewriteToIfs"),
+ run(),
+ checkLine(SOURCE_FILE, 267),
+ stepOver(),
+ checkLine(SOURCE_FILE, 268),
+ checkLocal("x", Value.createInt(1)),
+ checkLocal("t", Value.createInt(2)),
+ stepOver(),
+ checkLine(SOURCE_FILE, 269),
+ checkLocal("x", Value.createInt(2)),
+ checkLocal("t", Value.createInt(2)),
+ stepOver(),
+ checkLine(SOURCE_FILE, 271),
+ checkLocal("x", Value.createInt(4)),
+ checkNoLocal("t"),
+ run());
+ }
+
+ @Test
+ public void switchRewriteToSwitches() throws Throwable {
+ runDebugTest(
+ "Locals",
+ breakpoint("Locals", "switchRewriteToSwitches"),
+ run(),
+ checkLine(SOURCE_FILE, 282),
+ stepOver(),
+ checkLine(SOURCE_FILE, 283),
+ checkLocal("x", Value.createInt(1)),
+ checkLocal("t", Value.createInt(2)),
+ stepOver(),
+ checkLine(SOURCE_FILE, 284),
+ checkLocal("x", Value.createInt(2)),
+ checkLocal("t", Value.createInt(2)),
+ stepOver(),
+ checkLine(SOURCE_FILE, 286),
+ checkLocal("x", Value.createInt(4)),
+ checkNoLocal("t"),
+ run());
+ }
}
diff --git a/src/test/java/com/android/tools/r8/jasmin/DebugLocalTests.java b/src/test/java/com/android/tools/r8/jasmin/DebugLocalTests.java
index 5ffd815..531831b 100644
--- a/src/test/java/com/android/tools/r8/jasmin/DebugLocalTests.java
+++ b/src/test/java/com/android/tools/r8/jasmin/DebugLocalTests.java
@@ -437,4 +437,228 @@
info.checkLineHasExactLocals(14, "x", "int");
info.checkLineHasExactLocals(16, "x", "int");
}
+
+ @Test
+ public void testLocalSwitchRewriteToIfs() throws Exception {
+ JasminBuilder builder = new JasminBuilder();
+ JasminBuilder.ClassBuilder clazz = builder.addClass("Test");
+
+ /*
+ This is the original Java source code. The code generated by javac have been
+ slightly modified below to end local t on the lookupswitch instruction.
+
+ public static int switchRewrite(int x) { // Line 1
+ {
+ int t = x + 1;
+ x = t;
+ x = x + x;
+ }
+ switch (x) {
+ case 1:
+ return 7;
+ case 100:
+ return 8;
+ }
+ return -1;
+ }
+ */
+ MethodSignature foo = clazz.addStaticMethod("switchRewrite", ImmutableList.of("I"), "I",
+ ".limit stack 2",
+ ".limit locals 2",
+ ".var 0 is x I from L0 to L7",
+ ".var 1 is t I from L1 to L3",
+
+ "L0:",
+ ".line 3",
+ " iload 0",
+ " iconst_1",
+ " iadd",
+ " istore 1",
+ "L1:",
+ ".line 4",
+ " iload 1",
+ " istore 0",
+ "L2:",
+ ".line 5",
+ " iload 0",
+ " iload 0",
+ " iadd",
+ " istore 0",
+ "L3_ORIGINAL:", // This is where javac normally ends t.
+ ".line 7",
+ " iload 0",
+ "L3:", // Moved L3 here to end t on the switch instruction.
+ "lookupswitch",
+ " 0: L4",
+ " 100: L5",
+ " default: L6",
+ "L4:",
+ ".line 9",
+ " iconst_0",
+ " ireturn",
+ "L5:",
+ ".line 11",
+ " iconst_1",
+ " ireturn",
+ "L6:",
+ ".line 13",
+ " iconst_m1",
+ " ireturn",
+ "L7:"
+ );
+
+ clazz.addMainMethod(
+ ".limit stack 2",
+ ".limit locals 1",
+ " getstatic java/lang/System/out Ljava/io/PrintStream;",
+ " ldc 1",
+ " invokestatic Test/switchRewrite(I)I",
+ " invokevirtual java/io/PrintStream/print(I)V",
+ " return");
+
+ String expected = "-1";
+ String javaResult = runOnJava(builder, clazz.name);
+ assertEquals(expected, javaResult);
+
+ AndroidApp jasminApp = builder.build();
+ AndroidApp d8App = ToolHelper.runD8(jasminApp);
+ String artResult = runOnArt(d8App, clazz.name);
+ assertEquals(expected, artResult);
+
+ DebugInfoInspector info = new DebugInfoInspector(d8App, clazz.name, foo);
+ info.checkStartLine(3);
+ info.checkLineHasExactLocals(3, "x", "int");
+ info.checkLineHasExactLocals(4, "x", "int", "t", "int");
+ info.checkLineHasExactLocals(5, "x", "int", "t", "int");
+ info.checkLineHasExactLocals(7, "x", "int", "t", "int");
+ info.checkLineHasExactLocals(9, "x", "int");
+ info.checkLineHasExactLocals(11, "x", "int");
+ info.checkLineHasExactLocals(13, "x", "int");
+ }
+
+ @Test
+ public void testLocalSwitchRewriteToSwitches() throws Exception {
+ JasminBuilder builder = new JasminBuilder();
+ JasminBuilder.ClassBuilder clazz = builder.addClass("Test");
+
+ /*
+ This is the original Java source code. The code generated by javac have been
+ slightly modified below to end local t on the lookupswitch instruction.
+
+ public static int switchRewrite(int x) { // Line 1
+ {
+ int t = x + 1;
+ x = t;
+ x = x + x;
+ }
+ switch (x) {
+ case 0:
+ return 0;
+ case 1:
+ return 0;
+ case 2:
+ return 0;
+ case 100:
+ return 1;
+ case 101:
+ return 1;
+ case 102:
+ return 1;
+ }
+ return -1;
+ }
+ */
+ MethodSignature foo = clazz.addStaticMethod("switchRewrite", ImmutableList.of("I"), "I",
+ ".limit stack 2",
+ ".limit locals 2",
+ ".var 0 is x I from L0 to L11",
+ ".var 1 is t I from L1 to L3",
+
+ "L0:",
+ ".line 3",
+ " iload 0",
+ " iconst_1",
+ " iadd",
+ " istore 1",
+ "L1:",
+ ".line 4",
+ " iload 1",
+ " istore 0",
+ "L2:",
+ ".line 5",
+ " iload 0",
+ " iload 0",
+ " iadd",
+ " istore 0",
+ "L3_ORIGINAL:", // This is where javac normally ends t.
+ ".line 7",
+ " iload 0",
+ "L3:", // Moved L3 here to end t on the switch instruction.
+ "lookupswitch",
+ " 0: L4",
+ " 1: L5",
+ " 2: L6",
+ " 100: L7",
+ " 101: L8",
+ " 102: L9",
+ " default: L10",
+ "L4:",
+ ".line 9",
+ " iconst_0",
+ " ireturn",
+ "L5:",
+ ".line 11",
+ " iconst_0",
+ " ireturn",
+ "L6:",
+ ".line 13",
+ " iconst_0",
+ " ireturn",
+ "L7:",
+ ".line 15",
+ " iconst_1",
+ " ireturn",
+ "L8:",
+ ".line 17",
+ " iconst_1",
+ " ireturn",
+ "L9:",
+ ".line 19",
+ " iconst_1",
+ " ireturn",
+ "L10:",
+ ".line 21",
+ " iconst_m1",
+ " ireturn",
+ "L11:"
+ );
+
+ clazz.addMainMethod(
+ ".limit stack 2",
+ ".limit locals 1",
+ " getstatic java/lang/System/out Ljava/io/PrintStream;",
+ " ldc 1",
+ " invokestatic Test/switchRewrite(I)I",
+ " invokevirtual java/io/PrintStream/print(I)V",
+ " return");
+
+ String expected = "-1";
+ String javaResult = runOnJava(builder, clazz.name);
+ assertEquals(expected, javaResult);
+
+ AndroidApp jasminApp = builder.build();
+ AndroidApp d8App = ToolHelper.runD8(jasminApp);
+ String artResult = runOnArt(d8App, clazz.name);
+ assertEquals(expected, artResult);
+
+ DebugInfoInspector info = new DebugInfoInspector(d8App, clazz.name, foo);
+ info.checkStartLine(3);
+ info.checkLineHasExactLocals(3, "x", "int");
+ info.checkLineHasExactLocals(4, "x", "int", "t", "int");
+ info.checkLineHasExactLocals(5, "x", "int", "t", "int");
+ info.checkLineHasExactLocals(7, "x", "int", "t", "int");
+ info.checkLineHasExactLocals(9, "x", "int");
+ info.checkLineHasExactLocals(11, "x", "int");
+ info.checkLineHasExactLocals(13, "x", "int");
+ }
}
diff --git a/src/test/java/com/android/tools/r8/smali/SwitchRewritingTest.java b/src/test/java/com/android/tools/r8/smali/SwitchRewritingTest.java
index c256920..3750a86 100644
--- a/src/test/java/com/android/tools/r8/smali/SwitchRewritingTest.java
+++ b/src/test/java/com/android/tools/r8/smali/SwitchRewritingTest.java
@@ -34,7 +34,8 @@
public class SwitchRewritingTest extends SmaliTestBase {
private boolean twoCaseWillUsePackedSwitch(int key1, int key2) {
- return Math.abs((long) key1 - (long) key2) <= 2;
+ assert key1 != key2;
+ return Math.abs((long) key1 - (long) key2) == 1;
}
private boolean some16BitConst(Instruction instruction) {
@@ -114,7 +115,7 @@
}
}
- private void runTwoCaseSparseToPackedDexTest(int key1, int key2) {
+ private void runTwoCaseSparseToPackedOrIfsDexTest(int key1, int key2) {
SmaliBuilder builder = new SmaliBuilder(DEFAULT_CLASS_NAME);
MethodSignature signature = builder.addStaticMethod(
@@ -156,24 +157,29 @@
if (twoCaseWillUsePackedSwitch(key1, key2)) {
assertTrue(code.instructions[0] instanceof PackedSwitch);
} else {
- assertTrue(code.instructions[0] instanceof SparseSwitch);
+ if (key1 == 0) {
+ assertTrue(code.instructions[0] instanceof IfEqz);
+ } else {
+ // Const instruction before if.
+ assertTrue(code.instructions[1] instanceof IfEq);
+ }
}
}
@Test
- public void twoCaseSparseToPackedDex() {
+ public void twoCaseSparseToPackedOrIfsDex() {
for (int delta = 1; delta <= 3; delta++) {
- runTwoCaseSparseToPackedDexTest(0, delta);
- runTwoCaseSparseToPackedDexTest(-delta, 0);
- runTwoCaseSparseToPackedDexTest(Integer.MIN_VALUE, Integer.MIN_VALUE + delta);
- runTwoCaseSparseToPackedDexTest(Integer.MAX_VALUE - delta, Integer.MAX_VALUE);
+ runTwoCaseSparseToPackedOrIfsDexTest(0, delta);
+ runTwoCaseSparseToPackedOrIfsDexTest(-delta, 0);
+ runTwoCaseSparseToPackedOrIfsDexTest(Integer.MIN_VALUE, Integer.MIN_VALUE + delta);
+ runTwoCaseSparseToPackedOrIfsDexTest(Integer.MAX_VALUE - delta, Integer.MAX_VALUE);
}
- runTwoCaseSparseToPackedDexTest(-1, 1);
- runTwoCaseSparseToPackedDexTest(-2, 1);
- runTwoCaseSparseToPackedDexTest(-1, 2);
- runTwoCaseSparseToPackedDexTest(Integer.MIN_VALUE, Integer.MAX_VALUE);
- runTwoCaseSparseToPackedDexTest(Integer.MIN_VALUE + 1, Integer.MAX_VALUE);
- runTwoCaseSparseToPackedDexTest(Integer.MIN_VALUE, Integer.MAX_VALUE - 1);
+ runTwoCaseSparseToPackedOrIfsDexTest(-1, 1);
+ runTwoCaseSparseToPackedOrIfsDexTest(-2, 1);
+ runTwoCaseSparseToPackedOrIfsDexTest(-1, 2);
+ runTwoCaseSparseToPackedOrIfsDexTest(Integer.MIN_VALUE, Integer.MAX_VALUE);
+ runTwoCaseSparseToPackedOrIfsDexTest(Integer.MIN_VALUE + 1, Integer.MAX_VALUE);
+ runTwoCaseSparseToPackedOrIfsDexTest(Integer.MIN_VALUE, Integer.MAX_VALUE - 1);
}
private void runLargerSwitchDexTest(int firstKey, int keyStep, int totalKeys,
@@ -356,7 +362,12 @@
if (twoCaseWillUsePackedSwitch(key1, key2)) {
assertTrue(code.instructions[3] instanceof PackedSwitch);
} else {
- assertTrue(code.instructions[3] instanceof SparseSwitch);
+ if (key1 == 0) {
+ assertTrue(code.instructions[3] instanceof IfEqz);
+ } else {
+ // Const instruction before if.
+ assertTrue(code.instructions[4] instanceof IfEq);
+ }
}
}
@@ -462,8 +473,8 @@
runLargerSwitchJarTest(0, 1, 5503, null);
}
- private void runConvertCasesToIf(List<Integer> keys, int defaultValue, int expectedIfs)
- throws Exception {
+ private void runConvertCasesToIf(List<Integer> keys, int defaultValue, int expectedIfs,
+ int expectedPackedSwitches, int expectedSparceSwitches) throws Exception {
JasminBuilder builder = new JasminBuilder();
JasminBuilder.ClassBuilder clazz = builder.addClass("Test");
@@ -514,8 +525,8 @@
}
}
- assertEquals(1, packedSwitches);
- assertEquals(0, sparseSwitches);
+ assertEquals(expectedPackedSwitches, packedSwitches);
+ assertEquals(expectedSparceSwitches, sparseSwitches);
assertEquals(expectedIfs, ifs);
// Run the code
@@ -526,12 +537,34 @@
@Test
public void convertCasesToIf() throws Exception {
- runConvertCasesToIf(ImmutableList.of(0, 1000, 1001, 1002, 1003, 1004), -100, 1);
- runConvertCasesToIf(ImmutableList.of(1000, 1001, 1002, 1003, 1004, 2000), -100, 1);
- runConvertCasesToIf(ImmutableList.of(Integer.MIN_VALUE, 1000, 1001, 1002, 1003, 1004), -100, 1);
- runConvertCasesToIf(ImmutableList.of(1000, 1001, 1002, 1003, 1004, Integer.MAX_VALUE), -100, 1);
- runConvertCasesToIf(ImmutableList.of(0, 1000, 1001, 1002, 1003, 1004, 2000), -100, 2);
+ // Switches that are completely converted to ifs.
+ runConvertCasesToIf(ImmutableList.of(0, 1000), -100, 2, 0, 0);
+ runConvertCasesToIf(ImmutableList.of(0, 1000, 2000), -100, 3, 0, 0);
+ runConvertCasesToIf(ImmutableList.of(0, 1000, 2000, 3000), -100, 4, 0, 0);
+
+ // Switches that are completely converted to ifs and one switch.
+ runConvertCasesToIf(ImmutableList.of(0, 1000, 1001, 1002, 1003, 1004), -100, 1, 1, 0);
+ runConvertCasesToIf(ImmutableList.of(1000, 1001, 1002, 1003, 1004, 2000), -100, 1, 1, 0);
runConvertCasesToIf(ImmutableList.of(
- Integer.MIN_VALUE, 1000, 1001, 1002, 1003, 1004, Integer.MAX_VALUE), -100, 2);
+ Integer.MIN_VALUE, 1000, 1001, 1002, 1003, 1004), -100, 1, 1, 0);
+ runConvertCasesToIf(ImmutableList.of(
+ 1000, 1001, 1002, 1003, 1004, Integer.MAX_VALUE), -100, 1, 1, 0);
+ runConvertCasesToIf(ImmutableList.of(0, 1000, 1001, 1002, 1003, 1004, 2000), -100, 2, 1, 0);
+ runConvertCasesToIf(ImmutableList.of(
+ Integer.MIN_VALUE, 1000, 1001, 1002, 1003, 1004, Integer.MAX_VALUE), -100, 2, 1, 0);
+
+ // Switches that are completely converted to ifs and two switches.
+ runConvertCasesToIf(ImmutableList.of(
+ 0, 1, 2, 3, 4, 1000, 1001, 1002, 1003, 1004), -100, 0, 2, 0);
+ runConvertCasesToIf(ImmutableList.of(
+ -1000, 0, 1, 2, 3, 4, 1000, 1001, 1002, 1003, 1004), -100, 1, 2, 0);
+ runConvertCasesToIf(ImmutableList.of(
+ -1000, 0, 1, 2, 3, 4, 1000, 1001, 1002, 1003, 1004, 2000), -100, 2, 2, 0);
+
+ // Switches that are completely converted two switches (one sparse and one packed).
+ runConvertCasesToIf(ImmutableList.of(
+ -1000, -900, -800, -700, -600, -500, -400, -300,
+ 1000, 1001, 1002, 1003, 1004,
+ 2000, 2100, 2200, 2300, 2400, 2500), -100, 0, 1, 1);
}
}
\ No newline at end of file
