Backport Math/StrictMath.multiplyHigh
Test: tools/test.py --dex_vm all --no-internal -v *Backport*Test*
Test: tools/test.py --no-internal -v *GenerateBackportMethods*
Change-Id: Icf3d4400ab3e5be6fd6c9ac977ac0f8e840794f5
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/BackportedMethodRewriter.java b/src/main/java/com/android/tools/r8/ir/desugar/BackportedMethodRewriter.java
index 8610eca..8b44470 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/BackportedMethodRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/BackportedMethodRewriter.java
@@ -1214,6 +1214,15 @@
method,
BackportedMethods::MathMethods_multiplyFull));
+ // long {Math,StrictMath}.multiplyHigh(long, long)
+ name = factory.createString("multiplyHigh");
+ proto = factory.createProto(factory.longType, factory.longType, factory.longType);
+ method = factory.createMethod(type, proto, name);
+ addProvider(
+ new MethodGenerator(
+ method,
+ BackportedMethods::MathMethods_multiplyHigh));
+
// long {Math,StrictMath}.floorDiv(long, int)
name = factory.createString("floorDiv");
proto = factory.createProto(factory.longType, factory.longType, factory.intType);
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/backports/BackportedMethods.java b/src/main/java/com/android/tools/r8/ir/desugar/backports/BackportedMethods.java
index 80f34d99..5ca3dbd 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/backports/BackportedMethods.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/backports/BackportedMethods.java
@@ -3175,6 +3175,110 @@
ImmutableList.of());
}
+ public static CfCode MathMethods_multiplyHigh(InternalOptions options, DexMethod method) {
+ CfLabel label0 = new CfLabel();
+ CfLabel label1 = new CfLabel();
+ CfLabel label2 = new CfLabel();
+ CfLabel label3 = new CfLabel();
+ CfLabel label4 = new CfLabel();
+ CfLabel label5 = new CfLabel();
+ CfLabel label6 = new CfLabel();
+ CfLabel label7 = new CfLabel();
+ CfLabel label8 = new CfLabel();
+ CfLabel label9 = new CfLabel();
+ CfLabel label10 = new CfLabel();
+ CfLabel label11 = new CfLabel();
+ CfLabel label12 = new CfLabel();
+ CfLabel label13 = new CfLabel();
+ CfLabel label14 = new CfLabel();
+ CfLabel label15 = new CfLabel();
+ return new CfCode(
+ method.holder,
+ 4,
+ 32,
+ ImmutableList.of(
+ label0,
+ new CfLoad(ValueType.LONG, 0),
+ new CfConstNumber(4294967295L, ValueType.LONG),
+ new CfLogicalBinop(CfLogicalBinop.Opcode.And, NumericType.LONG),
+ new CfStore(ValueType.LONG, 4),
+ label1,
+ new CfLoad(ValueType.LONG, 0),
+ new CfConstNumber(32, ValueType.INT),
+ new CfLogicalBinop(CfLogicalBinop.Opcode.Shr, NumericType.LONG),
+ new CfStore(ValueType.LONG, 6),
+ label2,
+ new CfLoad(ValueType.LONG, 2),
+ new CfConstNumber(4294967295L, ValueType.LONG),
+ new CfLogicalBinop(CfLogicalBinop.Opcode.And, NumericType.LONG),
+ new CfStore(ValueType.LONG, 8),
+ label3,
+ new CfLoad(ValueType.LONG, 2),
+ new CfConstNumber(32, ValueType.INT),
+ new CfLogicalBinop(CfLogicalBinop.Opcode.Shr, NumericType.LONG),
+ new CfStore(ValueType.LONG, 10),
+ label4,
+ new CfLoad(ValueType.LONG, 4),
+ new CfLoad(ValueType.LONG, 8),
+ new CfArithmeticBinop(CfArithmeticBinop.Opcode.Mul, NumericType.LONG),
+ new CfStore(ValueType.LONG, 12),
+ label5,
+ new CfLoad(ValueType.LONG, 12),
+ new CfConstNumber(32, ValueType.INT),
+ new CfLogicalBinop(CfLogicalBinop.Opcode.Ushr, NumericType.LONG),
+ new CfStore(ValueType.LONG, 14),
+ label6,
+ new CfLoad(ValueType.LONG, 6),
+ new CfLoad(ValueType.LONG, 8),
+ new CfArithmeticBinop(CfArithmeticBinop.Opcode.Mul, NumericType.LONG),
+ new CfStore(ValueType.LONG, 16),
+ label7,
+ new CfLoad(ValueType.LONG, 16),
+ new CfLoad(ValueType.LONG, 14),
+ new CfArithmeticBinop(CfArithmeticBinop.Opcode.Add, NumericType.LONG),
+ new CfStore(ValueType.LONG, 18),
+ label8,
+ new CfLoad(ValueType.LONG, 18),
+ new CfConstNumber(4294967295L, ValueType.LONG),
+ new CfLogicalBinop(CfLogicalBinop.Opcode.And, NumericType.LONG),
+ new CfStore(ValueType.LONG, 20),
+ label9,
+ new CfLoad(ValueType.LONG, 18),
+ new CfConstNumber(32, ValueType.INT),
+ new CfLogicalBinop(CfLogicalBinop.Opcode.Shr, NumericType.LONG),
+ new CfStore(ValueType.LONG, 22),
+ label10,
+ new CfLoad(ValueType.LONG, 4),
+ new CfLoad(ValueType.LONG, 10),
+ new CfArithmeticBinop(CfArithmeticBinop.Opcode.Mul, NumericType.LONG),
+ new CfStore(ValueType.LONG, 24),
+ label11,
+ new CfLoad(ValueType.LONG, 24),
+ new CfLoad(ValueType.LONG, 20),
+ new CfArithmeticBinop(CfArithmeticBinop.Opcode.Add, NumericType.LONG),
+ new CfStore(ValueType.LONG, 26),
+ label12,
+ new CfLoad(ValueType.LONG, 26),
+ new CfConstNumber(32, ValueType.INT),
+ new CfLogicalBinop(CfLogicalBinop.Opcode.Shr, NumericType.LONG),
+ new CfStore(ValueType.LONG, 28),
+ label13,
+ new CfLoad(ValueType.LONG, 6),
+ new CfLoad(ValueType.LONG, 10),
+ new CfArithmeticBinop(CfArithmeticBinop.Opcode.Mul, NumericType.LONG),
+ new CfStore(ValueType.LONG, 30),
+ label14,
+ new CfLoad(ValueType.LONG, 30),
+ new CfLoad(ValueType.LONG, 22),
+ new CfArithmeticBinop(CfArithmeticBinop.Opcode.Add, NumericType.LONG),
+ new CfLoad(ValueType.LONG, 28),
+ new CfArithmeticBinop(CfArithmeticBinop.Opcode.Add, NumericType.LONG),
+ new CfReturn(ValueType.LONG),
+ label15),
+ ImmutableList.of(),
+ ImmutableList.of());
+ }
+
public static CfCode MathMethods_negateExactInt(InternalOptions options, DexMethod method) {
CfLabel label0 = new CfLabel();
CfLabel label1 = new CfLabel();
diff --git a/src/test/examplesJava9/backport/MathBackportJava9Main.java b/src/test/examplesJava9/backport/MathBackportJava9Main.java
index c465af1..9030283 100644
--- a/src/test/examplesJava9/backport/MathBackportJava9Main.java
+++ b/src/test/examplesJava9/backport/MathBackportJava9Main.java
@@ -4,11 +4,14 @@
package backport;
+import java.math.BigInteger;
+
public class MathBackportJava9Main {
public static void main(String[] args) {
testMultiplyExactLongInt();
testMultiplyFull();
+ testMultiplyHigh();
testFloorDivLongInt();
testFloorModLongInt();
}
@@ -37,6 +40,27 @@
Math.multiplyFull(Integer.MIN_VALUE, Integer.MIN_VALUE));
}
+ public static void testMultiplyHigh() {
+ long[] interestingValues = {
+ Long.MIN_VALUE, Long.MAX_VALUE,
+ Integer.MIN_VALUE, Integer.MAX_VALUE,
+ Short.MIN_VALUE, Short.MAX_VALUE,
+ Byte.MIN_VALUE, Byte.MAX_VALUE,
+ 0L,
+ -1L, 1L,
+ -42L, 42L
+ };
+ for (long x : interestingValues) {
+ for (long y : interestingValues) {
+ long expected = BigInteger.valueOf(x)
+ .multiply(BigInteger.valueOf(y))
+ .shiftRight(64)
+ .longValue();
+ assertEquals(expected, Math.multiplyHigh(x, y));
+ }
+ }
+ }
+
public static void testFloorDivLongInt() {
assertEquals(1L, Math.floorDiv(4L, 4));
assertEquals(1L, Math.floorDiv(-4L, -4));
diff --git a/src/test/examplesJava9/backport/StrictMathBackportJava9Main.java b/src/test/examplesJava9/backport/StrictMathBackportJava9Main.java
index e0e45fb..e9c33ca 100644
--- a/src/test/examplesJava9/backport/StrictMathBackportJava9Main.java
+++ b/src/test/examplesJava9/backport/StrictMathBackportJava9Main.java
@@ -4,6 +4,8 @@
package backport;
+import java.math.BigInteger;
+
public class StrictMathBackportJava9Main {
public static void main(String[] args) {
@@ -37,6 +39,27 @@
StrictMath.multiplyFull(Integer.MIN_VALUE, Integer.MIN_VALUE));
}
+ public static void testMultiplyHigh() {
+ long[] interestingValues = {
+ Long.MIN_VALUE, Long.MAX_VALUE,
+ Integer.MIN_VALUE, Integer.MAX_VALUE,
+ Short.MIN_VALUE, Short.MAX_VALUE,
+ Byte.MIN_VALUE, Byte.MAX_VALUE,
+ 0L,
+ -1L, 1L,
+ -42L, 42L
+ };
+ for (long x : interestingValues) {
+ for (long y : interestingValues) {
+ long expected = BigInteger.valueOf(x)
+ .multiply(BigInteger.valueOf(y))
+ .shiftRight(64)
+ .longValue();
+ assertEquals(expected, StrictMath.multiplyHigh(x, y));
+ }
+ }
+ }
+
public static void testFloorDivLongInt() {
assertEquals(1L, StrictMath.floorDiv(4L, 4));
assertEquals(1L, StrictMath.floorDiv(-4L, -4));
diff --git a/src/test/java/com/android/tools/r8/ir/desugar/backports/MathMethods.java b/src/test/java/com/android/tools/r8/ir/desugar/backports/MathMethods.java
index d3379c8..a41259d 100644
--- a/src/test/java/com/android/tools/r8/ir/desugar/backports/MathMethods.java
+++ b/src/test/java/com/android/tools/r8/ir/desugar/backports/MathMethods.java
@@ -158,6 +158,29 @@
return (long) x * y;
}
+ public static long multiplyHigh(long x, long y) {
+ // Adapted from Hacker's Delight (2nd ed), 8-2.
+ long xLow = x & 0xFFFFFFFFL;
+ long xHigh = x >> 32;
+ long yLow = y & 0xFFFFFFFFL;
+ long yHigh = y >> 32;
+
+ long lowLow = xLow * yLow;
+ long lowLowCarry = lowLow >>> 32;
+
+ long highLow = xHigh * yLow;
+ long mid1 = highLow + lowLowCarry;
+ long mid1Low = mid1 & 0xFFFFFFFFL;
+ long mid1High = mid1 >> 32;
+
+ long lowHigh = xLow * yHigh;
+ long mid2 = lowHigh + mid1Low;
+ long mid2High = mid2 >> 32;
+
+ long highHigh = xHigh * yHigh;
+ return highHigh + mid1High + mid2High;
+ }
+
public static int negateExactInt(int value) {
if (value == Integer.MIN_VALUE) {
throw new ArithmeticException();
