Add DupDupDupPeephole for replacing 3 x dup with dup + dup2
Change-Id: I432efe2c293456f279cd1f9d750640bb0e2a26de
diff --git a/src/main/java/com/android/tools/r8/ir/code/Dup2.java b/src/main/java/com/android/tools/r8/ir/code/Dup2.java
new file mode 100644
index 0000000..decbaec
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/code/Dup2.java
@@ -0,0 +1,82 @@
+// Copyright (c) 2018, 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.cf.LoadStoreHelper;
+import com.android.tools.r8.cf.code.CfStackInstruction;
+import com.android.tools.r8.cf.code.CfStackInstruction.Opcode;
+import com.android.tools.r8.errors.Unreachable;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.conversion.CfBuilder;
+import com.android.tools.r8.ir.conversion.DexBuilder;
+import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
+import com.android.tools.r8.ir.optimize.InliningConstraints;
+import com.google.common.collect.ImmutableList;
+
+public class Dup2 extends Instruction {
+
+ public Dup2(StackValues dest, StackValue src1, StackValue src2) {
+ super(dest, ImmutableList.of(src1, src2));
+ assert !src1.getTypeLattice().isWide();
+ assert !src2.getTypeLattice().isWide();
+ assert dest.getStackValues().size() == 4;
+ }
+
+ @Override
+ public void buildDex(DexBuilder builder) {
+ throw new Unreachable("This classfile-specific IR should not be inserted in the Dex backend.");
+ }
+
+ @Override
+ public void buildCf(CfBuilder builder) {
+ builder.add(new CfStackInstruction(Opcode.Dup2));
+ }
+
+ @Override
+ public boolean identicalNonValueNonPositionParts(Instruction other) {
+ throw new Unreachable();
+ }
+
+ @Override
+ public int compareNonValueParts(Instruction other) {
+ throw new Unreachable();
+ }
+
+ @Override
+ public int maxInValueRegister() {
+ return 0;
+ }
+
+ @Override
+ public int maxOutValueRegister() {
+ throw new Unreachable();
+ }
+
+ @Override
+ public ConstraintWithTarget inliningConstraint(
+ InliningConstraints inliningConstraints, DexType invocationContext) {
+ return inliningConstraints.forDup2();
+ }
+
+ @Override
+ public void insertLoadAndStores(InstructionListIterator it, LoadStoreHelper helper) {
+ // Intentionally empty. Dup2 is a stack operation.
+ }
+
+ @Override
+ public boolean hasInvariantOutType() {
+ return false;
+ }
+
+ @Override
+ public boolean isDup2() {
+ return true;
+ }
+
+ @Override
+ public Dup2 asDup2() {
+ return this;
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/code/Instruction.java b/src/main/java/com/android/tools/r8/ir/code/Instruction.java
index 90e8a6a..d4229bd 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Instruction.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Instruction.java
@@ -629,6 +629,14 @@
return null;
}
+ public boolean isDup2() {
+ return false;
+ }
+
+ public Dup2 asDup2() {
+ return null;
+ }
+
public boolean isJumpInstruction() {
return false;
}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/InliningConstraints.java b/src/main/java/com/android/tools/r8/ir/optimize/InliningConstraints.java
index cc85e39..4e3f9be 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/InliningConstraints.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/InliningConstraints.java
@@ -98,6 +98,10 @@
return ConstraintWithTarget.ALWAYS;
}
+ public ConstraintWithTarget forDup2() {
+ return ConstraintWithTarget.ALWAYS;
+ }
+
public ConstraintWithTarget forInstanceGet(DexField field, DexType invocationContext) {
DexField lookup = graphLense.lookupField(field);
return forFieldInstruction(
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/peepholes/BasicBlockMuncher.java b/src/main/java/com/android/tools/r8/ir/optimize/peepholes/BasicBlockMuncher.java
index 6df0447..25c46f8 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/peepholes/BasicBlockMuncher.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/peepholes/BasicBlockMuncher.java
@@ -19,7 +19,10 @@
// other peepholes to allow for more matches.
private final List<BasicBlockPeephole> destructivePeepholes =
ImmutableList.of(
- new StoreSequenceLoadPeephole(), new StoreLoadPeephole(), new LoadLoadDupPeephole());
+ new StoreSequenceLoadPeephole(),
+ new StoreLoadPeephole(),
+ new LoadLoadDupPeephole(),
+ new DupDupDupPeephole());
private final List<List<BasicBlockPeephole>> allPeepholes =
ImmutableList.of(nonDestructivePeepholes, destructivePeepholes);
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/peepholes/DupDupDupPeephole.java b/src/main/java/com/android/tools/r8/ir/optimize/peepholes/DupDupDupPeephole.java
new file mode 100644
index 0000000..9b86873
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/optimize/peepholes/DupDupDupPeephole.java
@@ -0,0 +1,91 @@
+// Copyright (c) 2018, 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.optimize.peepholes;
+
+import com.android.tools.r8.ir.code.Dup;
+import com.android.tools.r8.ir.code.Dup2;
+import com.android.tools.r8.ir.code.InstructionListIterator;
+import com.android.tools.r8.ir.code.StackValue;
+import com.android.tools.r8.ir.code.StackValues;
+import com.google.common.collect.ImmutableList;
+
+/**
+ * Peephole that looks for the following pattern:
+ *
+ * <pre>
+ * Dup
+ * Dup
+ * Dup
+ * </pre>
+ *
+ * and replaces with
+ *
+ * <pre>
+ * Dup
+ * Dup2
+ * </pre>
+ */
+public class DupDupDupPeephole implements BasicBlockPeephole {
+
+ private final Point dup1Exp =
+ new Point((i) -> i.isDup() && !i.inValues().get(0).getTypeLattice().isWide());
+ private final Point dup2Exp =
+ new Point((i) -> i.isDup() && !i.inValues().get(0).getTypeLattice().isWide());
+ private final Point dup3Exp =
+ new Point((i) -> i.isDup() && !i.inValues().get(0).getTypeLattice().isWide());
+
+ private final PeepholeLayout layout = PeepholeLayout.lookBackward(dup1Exp, dup2Exp, dup3Exp);
+
+ @Override
+ public boolean match(InstructionListIterator it) {
+ Match match = layout.test(it);
+ if (match == null) {
+ return false;
+ }
+
+ Dup dupTop = dup3Exp.get(match).asDup();
+ Dup dupMiddle = dup2Exp.get(match).asDup();
+ Dup dupBottom = dup1Exp.get(match).asDup();
+
+ StackValue src = (StackValue) dupTop.inValues().get(0);
+ StackValue srcMiddle = (StackValue) dupMiddle.inValues().get(0);
+ StackValue srcBottom = (StackValue) dupBottom.inValues().get(0);
+
+ StackValues tv = (StackValues) dupTop.outValue();
+ StackValues mv = (StackValues) dupMiddle.outValue();
+ StackValues bv = (StackValues) dupBottom.outValue();
+
+ // The stack looks like:
+ // ..., tv0, mv0, bv0, bv1,.. -->
+ // because tv1 was used by dupMiddle and mv1 was used by dupBottom.
+
+ StackValue tv0Dup2 = tv.getStackValues().get(0).duplicate(src.getHeight());
+ StackValue mv0Dup2 = mv.getStackValues().get(0).duplicate(src.getHeight() + 1);
+ StackValue bv0Dup2 = bv.getStackValues().get(0).duplicate(src.getHeight() + 2);
+ StackValue bv1Dup2 = bv.getStackValues().get(1).duplicate(src.getHeight() + 3);
+
+ // Remove tv1 use.
+ srcMiddle.removeUser(dupMiddle);
+ // Remove mv1 use.
+ srcBottom.removeUser(dupBottom);
+ // Replace other uses.
+ tv.getStackValues().get(0).replaceUsers(tv0Dup2);
+ mv.getStackValues().get(0).replaceUsers(mv0Dup2);
+ bv.getStackValues().get(0).replaceUsers(bv0Dup2);
+ bv.getStackValues().get(1).replaceUsers(bv1Dup2);
+
+ StackValues dest = new StackValues(ImmutableList.of(tv0Dup2, mv0Dup2, bv0Dup2, bv1Dup2));
+
+ Dup2 dup2 = new Dup2(dest, tv.getStackValues().get(0), tv.getStackValues().get(1));
+
+ it.removeOrReplaceByDebugLocalRead();
+ it.previous();
+ it.replaceCurrentInstruction(dup2);
+
+ // Reset the pointer
+ PeepholeHelper.resetPrevious(it, 1);
+ return true;
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/peepholes/LoadLoadDupPeephole.java b/src/main/java/com/android/tools/r8/ir/optimize/peepholes/LoadLoadDupPeephole.java
index 922b56f..eff527c 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/peepholes/LoadLoadDupPeephole.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/peepholes/LoadLoadDupPeephole.java
@@ -31,12 +31,12 @@
*/
public class LoadLoadDupPeephole implements BasicBlockPeephole {
- private final Point bottomLoadExp =
+ private final Point lastLoadExp =
new Point(PeepholeHelper.withoutLocalInfo(Instruction::isLoad));
- private final Point topLoadExp = new Point(PeepholeHelper.withoutLocalInfo(Instruction::isLoad));
+ private final Point firstLoadExp = new Point(PeepholeHelper.withoutLocalInfo(Instruction::isLoad));
// This searches backwards thus the pattern is built from the bottom.
- private final PeepholeLayout layout = PeepholeLayout.lookBackward(bottomLoadExp, topLoadExp);
+ private final PeepholeLayout layout = PeepholeLayout.lookBackward(lastLoadExp, firstLoadExp);
@Override
public boolean match(InstructionListIterator it) {
@@ -44,24 +44,26 @@
if (match == null) {
return false;
}
- Load bottomLoad = bottomLoadExp.get(match).asLoad();
- Load topLoad = topLoadExp.get(match).asLoad();
- if (topLoad.src() != bottomLoad.src()) {
+ Load lastLoad = lastLoadExp.get(match).asLoad();
+ Load firstLoad = firstLoadExp.get(match).asLoad();
+ if (firstLoad.src() != lastLoad.src()) {
return false;
}
- assert !topLoad.src().hasLocalInfo();
- assert !bottomLoad.src().hasLocalInfo();
+ assert !firstLoad.src().hasLocalInfo();
+ assert !lastLoad.src().hasLocalInfo();
- StackValue src = (StackValue) topLoad.outValue();
- src.removeUser(bottomLoad);
+ StackValue src = (StackValue) firstLoad.outValue();
+ src.removeUser(lastLoad);
int height = src.getHeight();
- StackValue newSrc = src.duplicate(height);
- StackValue newTop = src.duplicate(height + 1);
- StackValues dest = new StackValues(ImmutableList.of(newSrc, newTop));
+ StackValue newFirstLoadOut = src.duplicate(height);
+ StackValue newLastLoadOut = src.duplicate(height + 1);
+ StackValues dest = new StackValues(ImmutableList.of(newFirstLoadOut, newLastLoadOut));
- bottomLoad.outValue().replaceUsers(newSrc);
+ firstLoad.outValue().replaceUsers(newFirstLoadOut);
+ lastLoad.outValue().replaceUsers(newLastLoadOut);
+
it.replaceCurrentInstruction(new Dup(dest, src));
return true;
}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/peepholes/PeepholeHelper.java b/src/main/java/com/android/tools/r8/ir/optimize/peepholes/PeepholeHelper.java
index 72b9ee6..255e4bb 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/peepholes/PeepholeHelper.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/peepholes/PeepholeHelper.java
@@ -14,7 +14,10 @@
public class PeepholeHelper {
public static Predicate<Instruction> withoutLocalInfo(Predicate<Instruction> predicate) {
- return t -> !t.hasInValueWithLocalInfo() && predicate.test(t);
+ return t ->
+ predicate.test(t)
+ && !t.hasInValueWithLocalInfo()
+ && (t.outValue() == null || !t.outValue().hasLocalInfo());
}
public static void swapNextTwoInstructions(InstructionListIterator it) {
