Simplify Compose bit patterns
Bug: b/332668257
Change-Id: Id7257a0f1d84b13d4474b3e39f13b1e179a6db43
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/passes/BinopDescriptor.java b/src/main/java/com/android/tools/r8/ir/conversion/passes/BinopDescriptor.java
new file mode 100644
index 0000000..2862449
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/conversion/passes/BinopDescriptor.java
@@ -0,0 +1,328 @@
+// Copyright (c) 2024, 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.conversion.passes;
+
+import static com.android.tools.r8.utils.BitUtils.ALL_BITS_SET_MASK;
+
+import com.android.tools.r8.errors.Unreachable;
+import com.android.tools.r8.ir.code.Add;
+import com.android.tools.r8.ir.code.And;
+import com.android.tools.r8.ir.code.Binop;
+import com.android.tools.r8.ir.code.Mul;
+import com.android.tools.r8.ir.code.NumericType;
+import com.android.tools.r8.ir.code.Or;
+import com.android.tools.r8.ir.code.Shl;
+import com.android.tools.r8.ir.code.Shr;
+import com.android.tools.r8.ir.code.Sub;
+import com.android.tools.r8.ir.code.Ushr;
+import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.ir.code.Xor;
+
+/**
+ * A Binop descriptor describes left and right identity and absorbing element of binop. <code>
+ * In a space K, for a binop *:
+ * - i is left identity if for each x in K, i * x = x.
+ * - i is right identity if for each x in K, x * i = x.
+ * - a is left absorbing if for each x in K, a * x = a.
+ * - a is right absorbing if for each x in K, x * a = a.
+ * In a space K, a binop * is associative if for each x,y,z in K, (x * y) * z = x * (y * z).
+ * </code>
+ */
+enum BinopDescriptor {
+ ADD(true) {
+ @Override
+ Binop instantiate(NumericType numericType, Value dest, Value left, Value right) {
+ return Add.create(numericType, dest, left, right);
+ }
+
+ @Override
+ Integer leftIdentity(boolean isBooleanValue) {
+ return 0;
+ }
+
+ @Override
+ Integer rightIdentity(boolean isBooleanValue) {
+ return 0;
+ }
+
+ @Override
+ int evaluate(int left, int right) {
+ return left + right;
+ }
+
+ @Override
+ long evaluate(long left, long right) {
+ return left + right;
+ }
+ },
+ SUB(false) {
+ @Override
+ Binop instantiate(NumericType numericType, Value dest, Value left, Value right) {
+ return new Sub(numericType, dest, left, right);
+ }
+
+ @Override
+ Integer rightIdentity(boolean isBooleanValue) {
+ return 0;
+ }
+
+ @Override
+ int evaluate(int left, int right) {
+ return left - right;
+ }
+
+ @Override
+ long evaluate(long left, long right) {
+ return left - right;
+ }
+ },
+ MUL(true) {
+ @Override
+ Binop instantiate(NumericType numericType, Value dest, Value left, Value right) {
+ return Mul.create(numericType, dest, left, right);
+ }
+
+ @Override
+ Integer leftIdentity(boolean isBooleanValue) {
+ return 1;
+ }
+
+ @Override
+ Integer rightIdentity(boolean isBooleanValue) {
+ return 1;
+ }
+
+ @Override
+ Integer leftAbsorbing(boolean isBooleanValue) {
+ return 0;
+ }
+
+ @Override
+ Integer rightAbsorbing(boolean isBooleanValue) {
+ return 0;
+ }
+
+ @Override
+ int evaluate(int left, int right) {
+ return left * right;
+ }
+
+ @Override
+ long evaluate(long left, long right) {
+ return left * right;
+ }
+ },
+ // The following two can be improved if we handle ZeroDivide.
+ DIV(false) {
+ @Override
+ Integer rightIdentity(boolean isBooleanValue) {
+ return 1;
+ }
+ },
+ REM(false),
+ AND(true) {
+ @Override
+ Binop instantiate(NumericType numericType, Value dest, Value left, Value right) {
+ return And.create(numericType, dest, left, right);
+ }
+
+ @Override
+ Integer leftIdentity(boolean isBooleanValue) {
+ return allBitsSet(isBooleanValue);
+ }
+
+ @Override
+ Integer rightIdentity(boolean isBooleanValue) {
+ return allBitsSet(isBooleanValue);
+ }
+
+ @Override
+ Integer leftAbsorbing(boolean isBooleanValue) {
+ return 0;
+ }
+
+ @Override
+ Integer rightAbsorbing(boolean isBooleanValue) {
+ return 0;
+ }
+
+ @Override
+ int evaluate(int left, int right) {
+ return left & right;
+ }
+
+ @Override
+ long evaluate(long left, long right) {
+ return left & right;
+ }
+ },
+ OR(true) {
+ @Override
+ Binop instantiate(NumericType numericType, Value dest, Value left, Value right) {
+ return Or.create(numericType, dest, left, right);
+ }
+
+ @Override
+ Integer leftIdentity(boolean isBooleanValue) {
+ return 0;
+ }
+
+ @Override
+ Integer rightIdentity(boolean isBooleanValue) {
+ return 0;
+ }
+
+ @Override
+ Integer leftAbsorbing(boolean isBooleanValue) {
+ return allBitsSet(isBooleanValue);
+ }
+
+ @Override
+ Integer rightAbsorbing(boolean isBooleanValue) {
+ return allBitsSet(isBooleanValue);
+ }
+
+ @Override
+ int evaluate(int left, int right) {
+ return left | right;
+ }
+
+ @Override
+ long evaluate(long left, long right) {
+ return left | right;
+ }
+ },
+ XOR(true) {
+ @Override
+ Binop instantiate(NumericType numericType, Value dest, Value left, Value right) {
+ return Xor.create(numericType, dest, left, right);
+ }
+
+ @Override
+ Integer leftIdentity(boolean isBooleanValue) {
+ return 0;
+ }
+
+ @Override
+ Integer rightIdentity(boolean isBooleanValue) {
+ return 0;
+ }
+
+ @Override
+ int evaluate(int left, int right) {
+ return left ^ right;
+ }
+
+ @Override
+ long evaluate(long left, long right) {
+ return left ^ right;
+ }
+ },
+ SHL(false) {
+ @Override
+ Binop instantiate(NumericType numericType, Value dest, Value left, Value right) {
+ return new Shl(numericType, dest, left, right);
+ }
+
+ @Override
+ Integer rightIdentity(boolean isBooleanValue) {
+ return 0;
+ }
+
+ @Override
+ Integer leftAbsorbing(boolean isBooleanValue) {
+ return 0;
+ }
+
+ @Override
+ boolean isShift() {
+ return true;
+ }
+ },
+ SHR(false) {
+ @Override
+ Binop instantiate(NumericType numericType, Value dest, Value left, Value right) {
+ return new Shr(numericType, dest, left, right);
+ }
+
+ @Override
+ Integer rightIdentity(boolean isBooleanValue) {
+ return 0;
+ }
+
+ @Override
+ Integer leftAbsorbing(boolean isBooleanValue) {
+ return 0;
+ }
+
+ @Override
+ boolean isShift() {
+ return true;
+ }
+ },
+ USHR(false) {
+ @Override
+ Binop instantiate(NumericType numericType, Value dest, Value left, Value right) {
+ return new Ushr(numericType, dest, left, right);
+ }
+
+ @Override
+ Integer rightIdentity(boolean isBooleanValue) {
+ return 0;
+ }
+
+ @Override
+ Integer leftAbsorbing(boolean isBooleanValue) {
+ return 0;
+ }
+
+ @Override
+ boolean isShift() {
+ return true;
+ }
+ };
+
+ final boolean associativeAndCommutative;
+
+ BinopDescriptor(boolean associativeAndCommutative) {
+ this.associativeAndCommutative = associativeAndCommutative;
+ }
+
+ Binop instantiate(NumericType numericType, Value dest, Value left, Value right) {
+ throw new Unreachable();
+ }
+
+ Integer allBitsSet(boolean isBooleanValue) {
+ return isBooleanValue ? 1 : ALL_BITS_SET_MASK;
+ }
+
+ Integer leftIdentity(boolean isBooleanValue) {
+ return null;
+ }
+
+ Integer rightIdentity(boolean isBooleanValue) {
+ return null;
+ }
+
+ Integer leftAbsorbing(boolean isBooleanValue) {
+ return null;
+ }
+
+ Integer rightAbsorbing(boolean isBooleanValue) {
+ return null;
+ }
+
+ int evaluate(int left, int right) {
+ throw new Unreachable();
+ }
+
+ long evaluate(long left, long right) {
+ throw new Unreachable();
+ }
+
+ boolean isShift() {
+ return false;
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/passes/BinopRewriter.java b/src/main/java/com/android/tools/r8/ir/conversion/passes/BinopRewriter.java
index 1f731e4..7a480d6 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/passes/BinopRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/passes/BinopRewriter.java
@@ -4,9 +4,9 @@
package com.android.tools.r8.ir.conversion.passes;
-import static com.android.tools.r8.utils.BitUtils.ALL_BITS_SET_MASK;
+import static com.android.tools.r8.ir.conversion.passes.BinopDescriptor.ADD;
+import static com.android.tools.r8.ir.conversion.passes.BinopDescriptor.SUB;
-import com.android.tools.r8.errors.Unreachable;
import com.android.tools.r8.graph.AppInfo;
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.ir.analysis.type.TypeElement;
@@ -18,10 +18,12 @@
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.LogicalBinop;
import com.android.tools.r8.ir.code.Mul;
import com.android.tools.r8.ir.code.NumericType;
import com.android.tools.r8.ir.code.Or;
import com.android.tools.r8.ir.code.Phi;
+import com.android.tools.r8.ir.code.Position;
import com.android.tools.r8.ir.code.Rem;
import com.android.tools.r8.ir.code.Shl;
import com.android.tools.r8.ir.code.Shr;
@@ -45,8 +47,8 @@
private Map<Class<?>, BinopDescriptor> createBinopDescriptors() {
ImmutableMap.Builder<Class<?>, BinopDescriptor> builder = ImmutableMap.builder();
- builder.put(Add.class, BinopDescriptor.ADD);
- builder.put(Sub.class, BinopDescriptor.SUB);
+ builder.put(Add.class, ADD);
+ builder.put(Sub.class, SUB);
builder.put(Mul.class, BinopDescriptor.MUL);
builder.put(Div.class, BinopDescriptor.DIV);
builder.put(Rem.class, BinopDescriptor.REM);
@@ -59,314 +61,6 @@
return builder.build();
}
- /**
- * A Binop descriptor describes left and right identity and absorbing element of binop. <code>
- * In a space K, for a binop *:
- * - i is left identity if for each x in K, i * x = x.
- * - i is right identity if for each x in K, x * i = x.
- * - a is left absorbing if for each x in K, a * x = a.
- * - a is right absorbing if for each x in K, x * a = a.
- * In a space K, a binop * is associative if for each x,y,z in K, (x * y) * z = x * (y * z).
- * </code>
- */
- private enum BinopDescriptor {
- ADD(true) {
- @Override
- Binop instantiate(NumericType numericType, Value dest, Value left, Value right) {
- return Add.create(numericType, dest, left, right);
- }
-
- @Override
- Integer leftIdentity(boolean isBooleanValue) {
- return 0;
- }
-
- @Override
- Integer rightIdentity(boolean isBooleanValue) {
- return 0;
- }
-
- @Override
- int evaluate(int left, int right) {
- return left + right;
- }
-
- @Override
- long evaluate(long left, long right) {
- return left + right;
- }
- },
- SUB(false) {
- @Override
- Binop instantiate(NumericType numericType, Value dest, Value left, Value right) {
- return new Sub(numericType, dest, left, right);
- }
-
- @Override
- Integer rightIdentity(boolean isBooleanValue) {
- return 0;
- }
-
- @Override
- int evaluate(int left, int right) {
- return left - right;
- }
-
- @Override
- long evaluate(long left, long right) {
- return left - right;
- }
- },
- MUL(true) {
- @Override
- Binop instantiate(NumericType numericType, Value dest, Value left, Value right) {
- return Mul.create(numericType, dest, left, right);
- }
-
- @Override
- Integer leftIdentity(boolean isBooleanValue) {
- return 1;
- }
-
- @Override
- Integer rightIdentity(boolean isBooleanValue) {
- return 1;
- }
-
- @Override
- Integer leftAbsorbing(boolean isBooleanValue) {
- return 0;
- }
-
- @Override
- Integer rightAbsorbing(boolean isBooleanValue) {
- return 0;
- }
-
- @Override
- int evaluate(int left, int right) {
- return left * right;
- }
-
- @Override
- long evaluate(long left, long right) {
- return left * right;
- }
- },
- // The following two can be improved if we handle ZeroDivide.
- DIV(false) {
- @Override
- Integer rightIdentity(boolean isBooleanValue) {
- return 1;
- }
- },
- REM(false),
- AND(true) {
- @Override
- Binop instantiate(NumericType numericType, Value dest, Value left, Value right) {
- return And.create(numericType, dest, left, right);
- }
-
- @Override
- Integer leftIdentity(boolean isBooleanValue) {
- return allBitsSet(isBooleanValue);
- }
-
- @Override
- Integer rightIdentity(boolean isBooleanValue) {
- return allBitsSet(isBooleanValue);
- }
-
- @Override
- Integer leftAbsorbing(boolean isBooleanValue) {
- return 0;
- }
-
- @Override
- Integer rightAbsorbing(boolean isBooleanValue) {
- return 0;
- }
-
- @Override
- int evaluate(int left, int right) {
- return left & right;
- }
-
- @Override
- long evaluate(long left, long right) {
- return left & right;
- }
- },
- OR(true) {
- @Override
- Binop instantiate(NumericType numericType, Value dest, Value left, Value right) {
- return Or.create(numericType, dest, left, right);
- }
-
- @Override
- Integer leftIdentity(boolean isBooleanValue) {
- return 0;
- }
-
- @Override
- Integer rightIdentity(boolean isBooleanValue) {
- return 0;
- }
-
- @Override
- Integer leftAbsorbing(boolean isBooleanValue) {
- return allBitsSet(isBooleanValue);
- }
-
- @Override
- Integer rightAbsorbing(boolean isBooleanValue) {
- return allBitsSet(isBooleanValue);
- }
-
- @Override
- int evaluate(int left, int right) {
- return left | right;
- }
-
- @Override
- long evaluate(long left, long right) {
- return left | right;
- }
- },
- XOR(true) {
- @Override
- Binop instantiate(NumericType numericType, Value dest, Value left, Value right) {
- return Xor.create(numericType, dest, left, right);
- }
-
- @Override
- Integer leftIdentity(boolean isBooleanValue) {
- return 0;
- }
-
- @Override
- Integer rightIdentity(boolean isBooleanValue) {
- return 0;
- }
-
- @Override
- int evaluate(int left, int right) {
- return left ^ right;
- }
-
- @Override
- long evaluate(long left, long right) {
- return left ^ right;
- }
- },
- SHL(false) {
- @Override
- Binop instantiate(NumericType numericType, Value dest, Value left, Value right) {
- return new Shl(numericType, dest, left, right);
- }
-
- @Override
- Integer rightIdentity(boolean isBooleanValue) {
- return 0;
- }
-
- @Override
- Integer leftAbsorbing(boolean isBooleanValue) {
- return 0;
- }
-
- @Override
- boolean isShift() {
- return true;
- }
- },
- SHR(false) {
- @Override
- Binop instantiate(NumericType numericType, Value dest, Value left, Value right) {
- return new Shr(numericType, dest, left, right);
- }
-
- @Override
- Integer rightIdentity(boolean isBooleanValue) {
- return 0;
- }
-
- @Override
- Integer leftAbsorbing(boolean isBooleanValue) {
- return 0;
- }
-
- @Override
- boolean isShift() {
- return true;
- }
- },
- USHR(false) {
- @Override
- Binop instantiate(NumericType numericType, Value dest, Value left, Value right) {
- return new Ushr(numericType, dest, left, right);
- }
-
- @Override
- Integer rightIdentity(boolean isBooleanValue) {
- return 0;
- }
-
- @Override
- Integer leftAbsorbing(boolean isBooleanValue) {
- return 0;
- }
-
- @Override
- boolean isShift() {
- return true;
- }
- };
-
- final boolean associativeAndCommutative;
-
- BinopDescriptor(
- boolean associativeAndCommutative) {
- this.associativeAndCommutative = associativeAndCommutative;
- }
-
- Binop instantiate(NumericType numericType, Value dest, Value left, Value right) {
- throw new Unreachable();
- }
-
- Integer allBitsSet(boolean isBooleanValue) {
- return isBooleanValue ? 1 : ALL_BITS_SET_MASK;
- }
-
- Integer leftIdentity(boolean isBooleanValue) {
- return null;
- }
-
- Integer rightIdentity(boolean isBooleanValue) {
- return null;
- }
-
- Integer leftAbsorbing(boolean isBooleanValue) {
- return null;
- }
-
- Integer rightAbsorbing(boolean isBooleanValue) {
- return null;
- }
-
- int evaluate(int left, int right) {
- throw new Unreachable();
- }
-
- long evaluate(long left, long right) {
- throw new Unreachable();
- }
-
- boolean isShift() {
- return false;
- }
- }
-
@Override
protected String getRewriterId() {
return "BinopRewriter";
@@ -391,7 +85,7 @@
|| binop.getNumericType() == NumericType.LONG) {
BinopDescriptor binopDescriptor = descriptors.get(binop.getClass());
assert binopDescriptor != null;
- if (identityAbsorbingSimplification(iterator, binop, binopDescriptor)) {
+ if (identityAbsorbingSimplification(iterator, binop, binopDescriptor, code)) {
hasChanged = true;
continue;
}
@@ -415,7 +109,7 @@
ConstNumber constBRight = getConstNumber(binop.rightValue());
if ((constBLeft != null && constBRight != null)
|| (constBLeft == null && constBRight == null)) {
- return false;
+ return successiveLogicalSimplificationNoConstant(iterator, binop, binopDescriptor, code);
}
Value otherValue = constBLeft == null ? binop.leftValue() : binop.rightValue();
if (otherValue.isPhi() || !otherValue.getDefinition().isBinop()) {
@@ -436,14 +130,14 @@
if (binopDescriptor.associativeAndCommutative) {
// a * x * b => x * (a * b) where (a * b) is a constant.
assert binop.isCommutative();
- Value newConst = addNewConstNumber(code, iterator, constB, constA, binopDescriptor);
- replaceBinop(iterator, code, input, newConst, binopDescriptor);
+ rewriteIntoConstThenBinop(
+ iterator, binopDescriptor, binopDescriptor, constB, constA, input, true, code);
return true;
} else if (binopDescriptor.isShift()) {
// x shift: a shift: b => x shift: (a + b) where a + b is a constant.
if (constBRight != null && constARight != null) {
- Value newConst = addNewConstNumber(code, iterator, constB, constA, BinopDescriptor.ADD);
- replaceBinop(iterator, code, input, newConst, binopDescriptor);
+ rewriteIntoConstThenBinop(
+ iterator, ADD, binopDescriptor, constB, constA, input, false, code);
return true;
}
} else if (binop.isSub() && constBRight != null) {
@@ -451,12 +145,10 @@
// x - a - b => x - (a + b) where (a + b) is a constant.
// We ignore b - (x - a) and b - (a - x) with constBRight != null.
if (constARight == null) {
- Value newConst = addNewConstNumber(code, iterator, constA, constB, BinopDescriptor.SUB);
- replaceBinop(iterator, code, newConst, input, BinopDescriptor.SUB);
+ rewriteIntoConstThenBinop(iterator, SUB, SUB, constA, constB, input, true, code);
return true;
} else {
- Value newConst = addNewConstNumber(code, iterator, constB, constA, BinopDescriptor.ADD);
- replaceBinop(iterator, code, input, newConst, BinopDescriptor.SUB);
+ rewriteIntoConstThenBinop(iterator, ADD, SUB, constB, constA, input, false, code);
return true;
}
}
@@ -465,19 +157,16 @@
// x + a - b => x + (a - b) where (a - b) is a constant.
// a + x - b => x + (a - b) where (a - b) is a constant.
// We ignore b - (x + a) and b - (a + x) with constBRight != null.
- Value newConst = addNewConstNumber(code, iterator, constA, constB, BinopDescriptor.SUB);
- replaceBinop(iterator, code, newConst, input, BinopDescriptor.ADD);
+ rewriteIntoConstThenBinop(iterator, SUB, ADD, constA, constB, input, true, code);
return true;
} else if (binop.isAdd() && prevBinop.isSub()) {
// x - a + b => x - (a - b) where (a - b) is a constant.
// a - x + b => (a + b) - x where (a + b) is a constant.
if (constALeft == null) {
- Value newConst = addNewConstNumber(code, iterator, constA, constB, BinopDescriptor.SUB);
- replaceBinop(iterator, code, input, newConst, BinopDescriptor.SUB);
+ rewriteIntoConstThenBinop(iterator, SUB, SUB, constA, constB, input, false, code);
return true;
} else {
- Value newConst = addNewConstNumber(code, iterator, constB, constA, BinopDescriptor.ADD);
- replaceBinop(iterator, code, newConst, input, BinopDescriptor.SUB);
+ rewriteIntoConstThenBinop(iterator, ADD, SUB, constB, constA, input, true, code);
return true;
}
}
@@ -485,6 +174,162 @@
return false;
}
+ private boolean successiveLogicalSimplificationNoConstant(
+ InstructionListIterator iterator, Binop binop, BinopDescriptor binopDescriptor, IRCode code) {
+ if (!(binop.isAnd() || binop.isOr())) {
+ return false;
+ }
+ if (binop.leftValue().isPhi() || binop.rightValue().isPhi()) {
+ return false;
+ }
+ LogicalBinop leftDef = binop.leftValue().getDefinition().asLogicalBinop();
+ LogicalBinop rightDef = binop.rightValue().getDefinition().asLogicalBinop();
+ if (leftDef == null
+ || rightDef == null
+ || (leftDef.getClass() != rightDef.getClass())
+ || (leftDef.getNumericType() != rightDef.getNumericType())) {
+ return false;
+ }
+ // These optimizations were implemented mostly to deal with Compose specific bit patterns.
+ if (leftDef.isAnd() || leftDef.isOr()) {
+ return andOrOnCommonInputSimplification(
+ iterator, binop, leftDef, rightDef, binopDescriptor, code);
+ }
+ if (leftDef.isShl() || leftDef.isShr() || leftDef.isUshr()) {
+ return shiftOnCommonValueSharing(iterator, binop, leftDef, rightDef, binopDescriptor, code);
+ }
+ return false;
+ }
+
+ private boolean andOrOnCommonInputSimplification(
+ InstructionListIterator iterator,
+ Instruction binop,
+ LogicalBinop leftDef,
+ LogicalBinop rightDef,
+ BinopDescriptor binopDescriptor,
+ IRCode code) {
+ // For all permutations of & and |, represented by &| and |&.
+ // (x &| a) |& (x &| b) => (a |& b) &| x.
+ // a |& b will be simplified into a new constant if both constant.
+ Value x, a, b;
+ if (leftDef.leftValue() == rightDef.leftValue()) {
+ x = leftDef.leftValue();
+ a = leftDef.rightValue();
+ b = rightDef.rightValue();
+ } else if (leftDef.leftValue() == rightDef.rightValue()) {
+ x = leftDef.leftValue();
+ a = leftDef.rightValue();
+ b = rightDef.leftValue();
+ } else if (leftDef.rightValue() == rightDef.leftValue()) {
+ x = leftDef.rightValue();
+ a = leftDef.leftValue();
+ b = rightDef.rightValue();
+ } else if (leftDef.rightValue() == rightDef.rightValue()) {
+ x = leftDef.rightValue();
+ a = leftDef.leftValue();
+ b = rightDef.leftValue();
+ } else {
+ return false;
+ }
+
+ rewriteIntoTwoSuccessiveBinops(
+ iterator,
+ binop.getPosition(),
+ binopDescriptor,
+ descriptors.get(leftDef.getClass()),
+ a,
+ b,
+ x,
+ code);
+ return true;
+ }
+
+ private boolean shiftOnCommonValueSharing(
+ InstructionListIterator iterator,
+ Instruction binop,
+ LogicalBinop leftDef,
+ LogicalBinop rightDef,
+ BinopDescriptor binopDescriptor,
+ IRCode code) {
+ // For all permutations of & and |, represented by &|, and any shift operation.
+ // (x shift: val) &| (y shift: val) => (x &| y) shift: val.
+ // x |& y will be simplified into a new constant if both constant.
+ ConstNumber constLeft = getConstNumber(leftDef.rightValue());
+ if (constLeft != null) {
+ // val is a constant.
+ ConstNumber constRight = getConstNumber(rightDef.rightValue());
+ if (constRight == null) {
+ return false;
+ }
+ if (constRight.getRawValue() != constLeft.getRawValue()) {
+ return false;
+ }
+ } else {
+ // val is not constant.
+ if (leftDef.rightValue() != rightDef.rightValue()) {
+ return false;
+ }
+ }
+
+ rewriteIntoTwoSuccessiveBinops(
+ iterator,
+ binop.getPosition(),
+ binopDescriptor,
+ descriptors.get(leftDef.getClass()),
+ leftDef.leftValue(),
+ rightDef.leftValue(),
+ leftDef.rightValue(),
+ code);
+ return true;
+ }
+
+ private void rewriteIntoTwoSuccessiveBinops(
+ InstructionListIterator iterator,
+ Position position,
+ BinopDescriptor firstBinop,
+ BinopDescriptor secondBinop,
+ Value firstLeft,
+ Value firstRight,
+ Value secondRight,
+ IRCode code) {
+ // This creates something along the lines of:
+ // `(firstLeft firstBinop: firstRight) secondBinop: secondOther`.
+ ConstNumber constA = getConstNumber(firstLeft);
+ if (constA != null) {
+ ConstNumber constB = getConstNumber(firstRight);
+ if (constB != null) {
+ rewriteIntoConstThenBinop(
+ iterator, firstBinop, secondBinop, constA, constB, secondRight, true, code);
+ return;
+ }
+ }
+ Binop newFirstBinop = instantiateBinop(code, firstLeft, firstRight, firstBinop);
+ newFirstBinop.setPosition(position);
+ iterator.previous();
+ iterator.add(newFirstBinop);
+ iterator.next();
+ replaceBinop(iterator, code, newFirstBinop.outValue(), secondRight, secondBinop);
+ iterator.previous();
+ }
+
+ private void rewriteIntoConstThenBinop(
+ InstructionListIterator iterator,
+ BinopDescriptor firstBinop,
+ BinopDescriptor secondBinop,
+ ConstNumber firstLeft,
+ ConstNumber firstRight,
+ Value secondOther,
+ boolean newConstFlowsIntoLeft,
+ IRCode code) {
+ Value firstOutValue = insertNewConstNumber(code, iterator, firstLeft, firstRight, firstBinop);
+ replaceBinop(
+ iterator,
+ code,
+ newConstFlowsIntoLeft ? firstOutValue : secondOther,
+ newConstFlowsIntoLeft ? secondOther : firstOutValue,
+ secondBinop);
+ }
+
private void replaceBinop(
InstructionListIterator iterator,
IRCode code,
@@ -493,11 +338,8 @@
BinopDescriptor binopDescriptor) {
Binop newBinop = instantiateBinop(code, left, right, binopDescriptor);
iterator.replaceCurrentInstruction(newBinop);
- // We need to reset the iterator state after replaceCurrentInstruction so that Iterator#remove()
- // can work in identityAbsorbingSimplification by calling previous then next.
+ // We need to reset the iterator state to process the new instruction(s).
iterator.previous();
- iterator.next();
- identityAbsorbingSimplification(iterator, newBinop, binopDescriptor);
}
private Binop instantiateBinop(IRCode code, Value left, Value right, BinopDescriptor descriptor) {
@@ -507,7 +349,7 @@
return descriptor.instantiate(numericType, newValue, left, right);
}
- private Value addNewConstNumber(
+ private Value insertNewConstNumber(
IRCode code,
InstructionListIterator iterator,
ConstNumber left,
@@ -528,7 +370,7 @@
}
private boolean identityAbsorbingSimplification(
- InstructionListIterator iterator, Binop binop, BinopDescriptor binopDescriptor) {
+ InstructionListIterator iterator, Binop binop, BinopDescriptor binopDescriptor, IRCode code) {
ConstNumber constNumber = getConstNumber(binop.leftValue());
if (constNumber != null) {
boolean isBooleanValue = binop.outValue().knownToBeBoolean();
@@ -546,14 +388,28 @@
constNumber = getConstNumber(binop.rightValue());
if (constNumber != null) {
boolean isBooleanValue = binop.outValue().knownToBeBoolean();
- return simplify(
+ if (simplify(
binop,
iterator,
constNumber,
binopDescriptor.rightIdentity(isBooleanValue),
binop.leftValue(),
binopDescriptor.rightAbsorbing(isBooleanValue),
- binop.rightValue());
+ binop.rightValue())) {
+ return true;
+ }
+ }
+ if (binop.leftValue() == binop.rightValue()) {
+ if (binop.isXor() || binop.isSub()) {
+ // a ^ a => 0, a - a => 0
+ ConstNumber zero = new ConstNumber(code.createValue(binop.outValue().getType()), 0);
+ iterator.replaceCurrentInstruction(zero);
+ } else if (binop.isAnd() || binop.isOr()) {
+ // a & a => a, a | a => a.
+ binop.outValue().replaceUsers(binop.leftValue());
+ iterator.remove();
+ }
+ return true;
}
return false;
}
diff --git a/src/test/java/com/android/tools/r8/ir/ComposeBinopTest.java b/src/test/java/com/android/tools/r8/ir/ComposeBinopTest.java
new file mode 100644
index 0000000..cd41b8d
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/ComposeBinopTest.java
@@ -0,0 +1,319 @@
+// Copyright (c) 2024, 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;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.utils.StringUtils;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import com.android.tools.r8.utils.codeinspector.InstructionSubject;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class ComposeBinopTest extends TestBase {
+
+ private static final String EXPECTED_RESULT =
+ StringUtils.lines(
+ "12345678",
+ "12345678",
+ "0",
+ "0",
+ "76532",
+ "76532",
+ "0",
+ "0",
+ "-2147483648",
+ "-2147483648",
+ "0",
+ "0",
+ "74",
+ "0",
+ "12345838",
+ "12345854",
+ "240",
+ "160",
+ "76532",
+ "76542",
+ "0",
+ "0",
+ "-2147483488",
+ "-2147483398",
+ "8260",
+ "0",
+ "12345678",
+ "-2135069698",
+ "8260",
+ "0",
+ "76532",
+ "-2135069698",
+ "0",
+ "0",
+ "-2147475388",
+ "-2135069698",
+ "0",
+ "0",
+ "3948544",
+ "1572864",
+ "0",
+ "0",
+ "0",
+ "0",
+ "252706816",
+ "100663296",
+ "0",
+ "0",
+ "255",
+ "80",
+ "241",
+ "96",
+ "243",
+ "96",
+ "1551743",
+ "1032",
+ "99311600",
+ "66080",
+ "1551743",
+ "1032",
+ "-266892247",
+ "0",
+ "98765424",
+ "0",
+ "269978665",
+ "0",
+ "-268425890",
+ "0",
+ "612256",
+ "0",
+ "268445022",
+ "0",
+ "12413950",
+ "8260",
+ "12413950",
+ "8260",
+ "12413950",
+ "8260",
+ "-131068",
+ "0",
+ "1253900288",
+ "0",
+ "131076",
+ "0",
+ "-2037",
+ "0",
+ "350224384",
+ "0",
+ "2059",
+ "0",
+ "41",
+ "350",
+ "0");
+
+ private final TestParameters parameters;
+
+ @Parameterized.Parameters(name = "{0}")
+ public static TestParametersCollection data() {
+ return getTestParameters().withCfRuntimes().withDexRuntimes().withAllApiLevels().build();
+ }
+
+ public ComposeBinopTest(TestParameters parameters) {
+ this.parameters = parameters;
+ }
+
+ @Test
+ public void testD8() throws Exception {
+ testForRuntime(parameters)
+ .addProgramClasses(Main.class)
+ .run(parameters.getRuntime(), Main.class)
+ .assertSuccessWithOutput(EXPECTED_RESULT);
+ }
+
+ @Test
+ public void testR8() throws Exception {
+ testForR8(parameters.getBackend())
+ .addProgramClasses(Main.class)
+ .addKeepMainRule(Main.class)
+ .enableInliningAnnotations()
+ .setMinApi(parameters)
+ .compile()
+ .inspect(this::inspect)
+ .run(parameters.getRuntime(), Main.class)
+ .assertSuccessWithOutput(EXPECTED_RESULT);
+ }
+
+ private void inspect(CodeInspector inspector) {
+ ClassSubject mainClass = inspector.clazz(Main.class);
+ assertTrue(mainClass.isPresent());
+
+ assertTrue(
+ mainClass
+ .uniqueMethodWithOriginalName("bitSameInput")
+ .streamInstructions()
+ .noneMatch(InstructionSubject::isIntLogicalBinop));
+ assertEquals(
+ 6,
+ mainClass
+ .uniqueMethodWithOriginalName("shareShiftCstLeft")
+ .streamInstructions()
+ .filter(InstructionSubject::isIntLogicalBinop)
+ .count());
+ assertEquals(
+ 12,
+ mainClass
+ .uniqueMethodWithOriginalName("shareShiftCstRight")
+ .streamInstructions()
+ .filter(InstructionSubject::isIntLogicalBinop)
+ .count());
+ assertEquals(
+ 12,
+ mainClass
+ .uniqueMethodWithOriginalName("shareShiftVar")
+ .streamInstructions()
+ .filter(InstructionSubject::isIntLogicalBinop)
+ .count());
+ assertEquals(
+ 4,
+ mainClass
+ .uniqueMethodWithOriginalName("andOrCompositionCst")
+ .streamInstructions()
+ .filter(InstructionSubject::isIntLogicalBinop)
+ .count());
+ assertEquals(
+ 8,
+ mainClass
+ .uniqueMethodWithOriginalName("andOrCompositionVar")
+ .streamInstructions()
+ .filter(InstructionSubject::isIntLogicalBinop)
+ .count());
+ assertEquals(
+ 2,
+ mainClass
+ .uniqueMethodWithOriginalName("composeTests")
+ .streamInstructions()
+ .filter(InstructionSubject::isIntLogicalBinop)
+ .count());
+ }
+
+ static class Main {
+
+ public static void main(String[] args) {
+ int i1 = System.currentTimeMillis() > 0 ? 12345678 : 1;
+ int i2 = System.currentTimeMillis() > 0 ? 76532 : 1;
+ int i3 = System.currentTimeMillis() > 0 ? Integer.MIN_VALUE : 1;
+
+ bitSameInput(i1);
+ bitSameInput(i2);
+ bitSameInput(i3);
+
+ andOrCompositionCst(i1);
+ andOrCompositionCst(i2);
+ andOrCompositionCst(i3);
+
+ andOrCompositionVar(i1, i2, i3);
+ andOrCompositionVar(i2, i3, i1);
+ andOrCompositionVar(i3, i1, i2);
+
+ shareShiftCstLeft(i1);
+ shareShiftCstLeft(i2);
+ shareShiftCstLeft(i3);
+
+ shareShiftCstRight(i1, i2);
+ shareShiftCstRight(i1, i3);
+ shareShiftCstRight(i2, i3);
+
+ shareShiftVar(i1, i2, i3);
+ shareShiftVar(i2, i3, i1);
+ shareShiftVar(i3, i1, i2);
+
+ composeTests(i1);
+ composeTests(i2);
+ composeTests(i3);
+ }
+
+ @NeverInline
+ private static void bitSameInput(int a) {
+ // a & a => a, a | a => a.
+ System.out.println(a & a);
+ System.out.println(a | a);
+ // a ^ a => 0, a - a => 0
+ System.out.println(a ^ a);
+ System.out.println(a - a);
+ }
+
+ @NeverInline
+ private static void shareShiftCstRight(int a, int b) {
+ // (x shift: val) | (y shift: val) => (x | y) shift: val.
+ // (x shift: val) & (y shift: val) => (x & y) shift: val.
+ System.out.println((a >> 3) | (b >> 3));
+ System.out.println((a >> 3) & (b >> 3));
+ System.out.println((a << 3) | (b << 3));
+ System.out.println((a << 3) & (b << 3));
+ System.out.println((a >>> 3) | (b >>> 3));
+ System.out.println((a >>> 3) & (b >>> 3));
+ }
+
+ @NeverInline
+ private static void shareShiftCstLeft(int a) {
+ // (x shift: val) | (y shift: val) => (x | y) shift: val.
+ // (x shift: val) & (y shift: val) => (x & y) shift: val.
+ System.out.println((111 >> a) | (222 >> a));
+ System.out.println((112 >> a) & (223 >> a));
+ System.out.println((113 << a) | (224 << a));
+ System.out.println((114 << a) & (225 << a));
+ System.out.println((115 >>> a) | (226 >>> a));
+ System.out.println((116 >>> a) & (227 >>> a));
+ }
+
+ @NeverInline
+ private static void shareShiftVar(int a, int b, int c) {
+ // (x shift: val) | (y shift: val) => (x | y) shift: val.
+ // (x shift: val) & (y shift: val) => (x & y) shift: val.
+ System.out.println((a >> c) | (b >> c));
+ System.out.println((a >> c) & (b >> c));
+ System.out.println((a << c) | (b << c));
+ System.out.println((a << c) & (b << c));
+ System.out.println((a >>> c) | (b >>> c));
+ System.out.println((a >>> c) & (b >>> c));
+ }
+
+ @NeverInline
+ private static void andOrCompositionCst(int a) {
+ // For all permutations of & and |, represented by &| and |&.
+ // (x &| a) |& (x &| b) => x &| (a |& b).
+ // Note that here a and b are constants therefore should be resolved at compile-time.
+ System.out.println((a & 0b10101010) | (a & 0b11110000));
+ System.out.println((a & 0b10101010) & (a & 0b11110000));
+ System.out.println((a | 0b10101010) & (a | 0b11110000));
+ System.out.println((a | 0b10101010) | (a | 0b11110000));
+ }
+
+ @NeverInline
+ private static void andOrCompositionVar(int a, int b, int c) {
+ // For all permutations of & and |.
+ // (x &| a) |& (x &| b) => x &| (a |& b).
+ System.out.println((a & b) | (a & c));
+ System.out.println((a & b) & (a & c));
+ System.out.println((a | b) & (a | c));
+ System.out.println((a | b) | (a | c));
+ }
+
+ @NeverInline
+ private static void composeTests(int dirty) {
+ // This is rewritten to ((0b0001111111111110 & dirty) >> 3).
+ System.out.println(
+ ((0b1110 & dirty) >> 3)
+ | ((0b01110000 & dirty) >> 3)
+ | ((0b001110000000 & dirty) >> 3)
+ | ((0b0001110000000000 & dirty) >> 3));
+ }
+ }
+}
