Opt compiler: More strength reduction for multiplications.
We transform code looking like
MUL dst, src, (2^n + 1)
into
SHL tmp, src, n
ADD dst, src, tmp
and code looking like
MUL dst, src, (2^n - 1)
into
SHL tmp, src, n
SUB dst, tmp, src
Change-Id: Ia620ab68758caa70a01530b88cd65dd0444376d7
diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc
index b97dc1a..9ad2dd1 100644
--- a/compiler/optimizing/instruction_simplifier.cc
+++ b/compiler/optimizing/instruction_simplifier.cc
@@ -796,6 +796,34 @@
HShl* shl = new(allocator) HShl(type, input_other, shift);
block->ReplaceAndRemoveInstructionWith(instruction, shl);
RecordSimplification();
+ } else if (IsPowerOfTwo(factor - 1)) {
+ // Transform code looking like
+ // MUL dst, src, (2^n + 1)
+ // into
+ // SHL tmp, src, n
+ // ADD dst, src, tmp
+ HShl* shl = new (allocator) HShl(type,
+ input_other,
+ GetGraph()->GetIntConstant(WhichPowerOf2(factor - 1)));
+ HAdd* add = new (allocator) HAdd(type, input_other, shl);
+
+ block->InsertInstructionBefore(shl, instruction);
+ block->ReplaceAndRemoveInstructionWith(instruction, add);
+ RecordSimplification();
+ } else if (IsPowerOfTwo(factor + 1)) {
+ // Transform code looking like
+ // MUL dst, src, (2^n - 1)
+ // into
+ // SHL tmp, src, n
+ // SUB dst, tmp, src
+ HShl* shl = new (allocator) HShl(type,
+ input_other,
+ GetGraph()->GetIntConstant(WhichPowerOf2(factor + 1)));
+ HSub* sub = new (allocator) HSub(type, shl, input_other);
+
+ block->InsertInstructionBefore(shl, instruction);
+ block->ReplaceAndRemoveInstructionWith(instruction, sub);
+ RecordSimplification();
}
}
}
diff --git a/test/458-checker-instruction-simplification/src/Main.java b/test/458-checker-instruction-simplification/src/Main.java
index c32d34a..d5fed2a 100644
--- a/test/458-checker-instruction-simplification/src/Main.java
+++ b/test/458-checker-instruction-simplification/src/Main.java
@@ -1226,6 +1226,46 @@
return arg / -0.25f;
}
+ /**
+ * Test strength reduction of factors of the form (2^n + 1).
+ */
+
+ /// CHECK-START: int Main.mulPow2Plus1(int) instruction_simplifier (before)
+ /// CHECK-DAG: <<Arg:i\d+>> ParameterValue
+ /// CHECK-DAG: <<Const9:i\d+>> IntConstant 9
+ /// CHECK: Mul [<<Arg>>,<<Const9>>]
+
+ /// CHECK-START: int Main.mulPow2Plus1(int) instruction_simplifier (after)
+ /// CHECK-DAG: <<Arg:i\d+>> ParameterValue
+ /// CHECK-DAG: <<Const3:i\d+>> IntConstant 3
+ /// CHECK: <<Shift:i\d+>> Shl [<<Arg>>,<<Const3>>]
+ /// CHECK-NEXT: Add [<<Arg>>,<<Shift>>]
+
+ public static int mulPow2Plus1(int arg) {
+ return arg * 9;
+ }
+
+
+ /**
+ * Test strength reduction of factors of the form (2^n - 1).
+ */
+
+ /// CHECK-START: long Main.mulPow2Minus1(long) instruction_simplifier (before)
+ /// CHECK-DAG: <<Arg:j\d+>> ParameterValue
+ /// CHECK-DAG: <<Const31:j\d+>> LongConstant 31
+ /// CHECK: Mul [<<Arg>>,<<Const31>>]
+
+ /// CHECK-START: long Main.mulPow2Minus1(long) instruction_simplifier (after)
+ /// CHECK-DAG: <<Arg:j\d+>> ParameterValue
+ /// CHECK-DAG: <<Const5:i\d+>> IntConstant 5
+ /// CHECK: <<Shift:j\d+>> Shl [<<Arg>>,<<Const5>>]
+ /// CHECK-NEXT: Sub [<<Shift>>,<<Arg>>]
+
+ public static long mulPow2Minus1(long arg) {
+ return arg * 31;
+ }
+
+
public static void main(String[] args) {
int arg = 123456;
@@ -1283,5 +1323,15 @@
assertLongEquals(Shr56And255(0xc123456787654321L), 0xc1L);
assertIntEquals(Shr24And127(0xc1234567), 0x41);
assertLongEquals(Shr56And127(0xc123456787654321L), 0x41L);
+ assertIntEquals(0, mulPow2Plus1(0));
+ assertIntEquals(9, mulPow2Plus1(1));
+ assertIntEquals(18, mulPow2Plus1(2));
+ assertIntEquals(900, mulPow2Plus1(100));
+ assertIntEquals(111105, mulPow2Plus1(12345));
+ assertLongEquals(0, mulPow2Minus1(0));
+ assertLongEquals(31, mulPow2Minus1(1));
+ assertLongEquals(62, mulPow2Minus1(2));
+ assertLongEquals(3100, mulPow2Minus1(100));
+ assertLongEquals(382695, mulPow2Minus1(12345));
}
}
diff --git a/test/485-checker-dce-loop-update/smali/TestCase.smali b/test/485-checker-dce-loop-update/smali/TestCase.smali
index ab4afdb..1de0bae 100644
--- a/test/485-checker-dce-loop-update/smali/TestCase.smali
+++ b/test/485-checker-dce-loop-update/smali/TestCase.smali
@@ -136,11 +136,11 @@
## CHECK-DAG: <<Cst1:i\d+>> IntConstant 1
## CHECK-DAG: <<Cst5:i\d+>> IntConstant 5
## CHECK-DAG: <<Cst7:i\d+>> IntConstant 7
-## CHECK-DAG: <<Cst9:i\d+>> IntConstant 9
+## CHECK-DAG: <<Cst11:i\d+>> IntConstant 11
## CHECK-DAG: <<PhiX1:i\d+>> Phi [<<ArgX>>,<<Add5:i\d+>>,<<Add7:i\d+>>] loop:<<HeaderY:B\d+>>
## CHECK-DAG: If [<<ArgY>>] loop:<<HeaderY>>
## CHECK-DAG: If [<<ArgZ>>] loop:<<HeaderY>>
-## CHECK-DAG: <<Mul9:i\d+>> Mul [<<PhiX1>>,<<Cst9>>] loop:<<HeaderY>>
+## CHECK-DAG: <<Mul9:i\d+>> Mul [<<PhiX1>>,<<Cst11>>] loop:<<HeaderY>>
## CHECK-DAG: <<PhiX2:i\d+>> Phi [<<PhiX1>>,<<Mul9>>] loop:<<HeaderY>>
## CHECK-DAG: If [<<Cst1>>] loop:<<HeaderY>>
## CHECK-DAG: <<Add5>> Add [<<PhiX2>>,<<Cst5>>] loop:<<HeaderY>>
@@ -152,12 +152,12 @@
## CHECK-DAG: <<ArgY:z\d+>> ParameterValue
## CHECK-DAG: <<ArgZ:z\d+>> ParameterValue
## CHECK-DAG: <<Cst7:i\d+>> IntConstant 7
-## CHECK-DAG: <<Cst9:i\d+>> IntConstant 9
+## CHECK-DAG: <<Cst11:i\d+>> IntConstant 11
## CHECK-DAG: <<PhiX1:i\d+>> Phi [<<ArgX>>,<<Add7:i\d+>>] loop:<<HeaderY:B\d+>>
## CHECK-DAG: If [<<ArgY>>] loop:<<HeaderY>>
## CHECK-DAG: <<Add7>> Add [<<PhiX1>>,<<Cst7>>] loop:<<HeaderY>>
## CHECK-DAG: If [<<ArgZ>>] loop:none
-## CHECK-DAG: <<Mul9:i\d+>> Mul [<<PhiX1>>,<<Cst9>>] loop:none
+## CHECK-DAG: <<Mul9:i\d+>> Mul [<<PhiX1>>,<<Cst11>>] loop:none
## CHECK-DAG: <<PhiX2:i\d+>> Phi [<<PhiX1>>,<<Mul9>>] loop:none
## CHECK-DAG: Return [<<PhiX2>>] loop:none
@@ -177,7 +177,7 @@
# Additional logic which will end up outside the loop
if-eqz p2, :skip_if
- mul-int/lit8 p0, p0, 9
+ mul-int/lit8 p0, p0, 11
:skip_if
if-nez v0, :loop_end # will always take the branch
