ARM: Optimize Div/Rem by positive const for non-negative dividends
When a constant divisor is positive and it can be proved that dividends
are non-negative, there is no need to generate instructions correcting
the result.
The CL implements this optimization for ARM32/ARM64.
Test: 411-checker-hdiv-hrem-const
Test: test.py --host --optimizing --jit --gtest --interpreter
Test: test.py -target --optimizing --jit --interpreter
Test: run-gtests.sh
Change-Id: Idf9aa740f14700000948b5ca58311be403a269ee
diff --git a/compiler/optimizing/code_generator_arm64.cc b/compiler/optimizing/code_generator_arm64.cc
index ba5b1b7..7d1af05 100644
--- a/compiler/optimizing/code_generator_arm64.cc
+++ b/compiler/optimizing/code_generator_arm64.cc
@@ -3242,13 +3242,23 @@
// Extract the result from the high 32 bits and apply the final right shift.
DCHECK_LT(shift, 32);
- __ Asr(temp.X(), temp.X(), 32 + shift);
-
- if (instruction->IsRem()) {
- GenerateIncrementNegativeByOne(temp, temp, use_cond_inc);
- GenerateResultRemWithAnyConstant(out, dividend, temp, imm, &temps);
+ if (imm > 0 && IsGEZero(instruction->GetLeft())) {
+ // No need to adjust the result for a non-negative dividend and a positive divisor.
+ if (instruction->IsDiv()) {
+ __ Lsr(out.X(), temp.X(), 32 + shift);
+ } else {
+ __ Lsr(temp.X(), temp.X(), 32 + shift);
+ GenerateResultRemWithAnyConstant(out, dividend, temp, imm, &temps);
+ }
} else {
- GenerateIncrementNegativeByOne(out, temp, use_cond_inc);
+ __ Asr(temp.X(), temp.X(), 32 + shift);
+
+ if (instruction->IsRem()) {
+ GenerateIncrementNegativeByOne(temp, temp, use_cond_inc);
+ GenerateResultRemWithAnyConstant(out, dividend, temp, imm, &temps);
+ } else {
+ GenerateIncrementNegativeByOne(out, temp, use_cond_inc);
+ }
}
}
diff --git a/compiler/optimizing/code_generator_arm_vixl.cc b/compiler/optimizing/code_generator_arm_vixl.cc
index db9ab3b..55e69d0 100644
--- a/compiler/optimizing/code_generator_arm_vixl.cc
+++ b/compiler/optimizing/code_generator_arm_vixl.cc
@@ -4310,27 +4310,70 @@
int shift;
CalculateMagicAndShiftForDivRem(imm, /* is_long= */ false, &magic, &shift);
- // TODO(VIXL): Change the static cast to Operand::From() after VIXL is fixed.
- __ Mov(temp1, static_cast<int32_t>(magic));
- __ Smull(temp2, temp1, dividend, temp1);
+ auto generate_unsigned_div_code =[this, magic, shift](vixl32::Register out,
+ vixl32::Register dividend,
+ vixl32::Register temp1,
+ vixl32::Register temp2) {
+ // TODO(VIXL): Change the static cast to Operand::From() after VIXL is fixed.
+ __ Mov(temp1, static_cast<int32_t>(magic));
+ if (magic > 0 && shift == 0) {
+ __ Smull(temp2, out, dividend, temp1);
+ } else {
+ __ Smull(temp2, temp1, dividend, temp1);
+ if (magic < 0) {
+ // The negative magic M = static_cast<int>(m) means that the multiplier m is greater
+ // than INT32_MAX. In such a case shift is never 0.
+ // Proof:
+ // m = (2^p + d - 2^p % d) / d, where p = 32 + shift, d > 2
+ //
+ // If shift == 0, m = (2^32 + d - 2^32 % d) / d =
+ // = (2^32 + d - (2^32 - (2^32 / d) * d)) / d =
+ // = (d + (2^32 / d) * d) / d = 1 + (2^32 / d), here '/' is the integer division.
+ //
+ // 1 + (2^32 / d) is decreasing when d is increasing.
+ // The maximum is 1 431 655 766, when d == 3. This value is less than INT32_MAX.
+ // the minimum is 3, when d = 2^31 -1.
+ // So for all values of d in [3, INT32_MAX] m with p == 32 is in [3, INT32_MAX) and
+ // is never less than 0.
+ __ Add(temp1, temp1, dividend);
+ }
+ DCHECK_NE(shift, 0);
+ __ Lsr(out, temp1, shift);
+ }
+ };
- if (imm > 0 && magic < 0) {
- __ Add(temp1, temp1, dividend);
- } else if (imm < 0 && magic > 0) {
- __ Sub(temp1, temp1, dividend);
- }
-
- if (shift != 0) {
- __ Asr(temp1, temp1, shift);
- }
-
- if (instruction->IsDiv()) {
- __ Sub(out, temp1, Operand(temp1, vixl32::Shift(ASR), 31));
+ if (imm > 0 && IsGEZero(instruction->GetLeft())) {
+ // No need to adjust the result for a non-negative dividend and a positive divisor.
+ if (instruction->IsDiv()) {
+ generate_unsigned_div_code(out, dividend, temp1, temp2);
+ } else {
+ generate_unsigned_div_code(temp1, dividend, temp1, temp2);
+ __ Mov(temp2, imm);
+ __ Mls(out, temp1, temp2, dividend);
+ }
} else {
- __ Sub(temp1, temp1, Operand(temp1, vixl32::Shift(ASR), 31));
- // TODO: Strength reduction for mls.
- __ Mov(temp2, imm);
- __ Mls(out, temp1, temp2, dividend);
+ // TODO(VIXL): Change the static cast to Operand::From() after VIXL is fixed.
+ __ Mov(temp1, static_cast<int32_t>(magic));
+ __ Smull(temp2, temp1, dividend, temp1);
+
+ if (imm > 0 && magic < 0) {
+ __ Add(temp1, temp1, dividend);
+ } else if (imm < 0 && magic > 0) {
+ __ Sub(temp1, temp1, dividend);
+ }
+
+ if (shift != 0) {
+ __ Asr(temp1, temp1, shift);
+ }
+
+ if (instruction->IsDiv()) {
+ __ Sub(out, temp1, Operand(temp1, vixl32::Shift(ASR), 31));
+ } else {
+ __ Sub(temp1, temp1, Operand(temp1, vixl32::Shift(ASR), 31));
+ // TODO: Strength reduction for mls.
+ __ Mov(temp2, imm);
+ __ Mls(out, temp1, temp2, dividend);
+ }
}
}
diff --git a/test/411-checker-hdiv-hrem-const/src/DivTest.java b/test/411-checker-hdiv-hrem-const/src/DivTest.java
index ed4eb62..ba6ca86 100644
--- a/test/411-checker-hdiv-hrem-const/src/DivTest.java
+++ b/test/411-checker-hdiv-hrem-const/src/DivTest.java
@@ -41,6 +41,11 @@
expectEquals(3, $noinline$IntDivBy18(65));
expectEquals(-3, $noinline$IntDivBy18(-65));
+ expectEquals(0, $noinline$IntALenDivBy18(new int[0]));
+ expectEquals(0, $noinline$IntALenDivBy18(new int[1]));
+ expectEquals(1, $noinline$IntALenDivBy18(new int[18]));
+ expectEquals(3, $noinline$IntALenDivBy18(new int[65]));
+
expectEquals(0, $noinline$IntDivByMinus18(0));
expectEquals(0, $noinline$IntDivByMinus18(1));
expectEquals(0, $noinline$IntDivByMinus18(-1));
@@ -57,6 +62,11 @@
expectEquals(3, $noinline$IntDivBy7(22));
expectEquals(-3, $noinline$IntDivBy7(-22));
+ expectEquals(0, $noinline$IntALenDivBy7(new int[0]));
+ expectEquals(0, $noinline$IntALenDivBy7(new int[1]));
+ expectEquals(1, $noinline$IntALenDivBy7(new int[7]));
+ expectEquals(3, $noinline$IntALenDivBy7(new int[22]));
+
expectEquals(0, $noinline$IntDivByMinus7(0));
expectEquals(0, $noinline$IntDivByMinus7(1));
expectEquals(0, $noinline$IntDivByMinus7(-1));
@@ -73,6 +83,11 @@
expectEquals(3, $noinline$IntDivBy6(19));
expectEquals(-3, $noinline$IntDivBy6(-19));
+ expectEquals(0, $noinline$IntALenDivBy6(new int[0]));
+ expectEquals(0, $noinline$IntALenDivBy6(new int[1]));
+ expectEquals(1, $noinline$IntALenDivBy6(new int[6]));
+ expectEquals(3, $noinline$IntALenDivBy6(new int[19]));
+
expectEquals(0, $noinline$IntDivByMinus6(0));
expectEquals(0, $noinline$IntDivByMinus6(1));
expectEquals(0, $noinline$IntDivByMinus6(-1));
@@ -96,6 +111,22 @@
return r;
}
+ // A test case to check that a correcting 'add' is not generated for a non-negative
+ // dividend and a positive divisor.
+ //
+ /// CHECK-START-ARM: int DivTest.$noinline$IntALenDivBy18(int[]) disassembly (after)
+ /// CHECK: smull r{{\d+}}, r{{\d+}}, r{{\d+}}, r{{\d+}}
+ /// CHECK-NEXT: lsr{{s?}} r{{\d+}}, r{{\d+}}, #2
+ /// CHECK-NOT: sub r{{\d+}}, r{{\d+}}, r{{\d+}}, asr #31
+ //
+ /// CHECK-START-ARM64: int DivTest.$noinline$IntALenDivBy18(int[]) disassembly (after)
+ /// CHECK: lsr x{{\d+}}, x{{\d+}}, #34
+ /// CHECK-NOT: add w{{\d+}}, w{{\d+}}, w{{\d+}}, lsr #31
+ private static int $noinline$IntALenDivBy18(int[] arr) {
+ int r = arr.length / 18;
+ return r;
+ }
+
// A test case to check that 'lsr' and 'asr' are combined into one 'asr'.
// Divisor -18 has the same property as divisor 18: no need to correct the
// result of get_high(dividend * magic). So there are no
@@ -125,6 +156,24 @@
return r;
}
+ // A test case to check that a correcting 'add' is not generated for a non-negative
+ // dividend and a positive divisor.
+ //
+ /// CHECK-START-ARM: int DivTest.$noinline$IntALenDivBy7(int[]) disassembly (after)
+ /// CHECK: smull r{{\d+}}, r{{\d+}}, r{{\d+}}, r{{\d+}}
+ /// CHECK-NEXT: add{{s?}} r{{\d+}}, r{{\d+}}
+ /// CHECK-NEXT: lsr{{s?}} r{{\d+}}, r{{\d+}}, #2
+ /// CHECK-NOT: sub r{{\d+}}, r{{\d+}}, r{{\d+}}, asr #31
+ //
+ /// CHECK-START-ARM64: int DivTest.$noinline$IntALenDivBy7(int[]) disassembly (after)
+ /// CHECK: adds x{{\d+}}, x{{\d+}}, x{{\d+}}, lsl #32
+ /// CHECK-NEXT: lsr x{{\d+}}, x{{\d+}}, #34
+ /// CHECK-NOT: cinc w{{\d+}}, w{{\d+}}, mi
+ private static int $noinline$IntALenDivBy7(int[] arr) {
+ int r = arr.length / 7;
+ return r;
+ }
+
// A test case to check that 'lsr' and 'add' are combined into one 'adds'.
// Divisor -7 has the same property as divisor 7: the result of get_high(dividend * magic)
// must be corrected. In this case it is a 'sub' instruction.
@@ -155,6 +204,21 @@
return r;
}
+ // A test case to check that a correcting 'add' is not generated for a non-negative
+ // dividend and a positive divisor.
+ //
+ /// CHECK-START-ARM: int DivTest.$noinline$IntALenDivBy6(int[]) disassembly (after)
+ /// CHECK: smull r{{\d+}}, r{{\d+}}, r{{\d+}}, r{{\d+}}
+ /// CHECK-NOT: sub r{{\d+}}, r{{\d+}}, r{{\d+}}, asr #31
+ //
+ /// CHECK-START-ARM64: int DivTest.$noinline$IntALenDivBy6(int[]) disassembly (after)
+ /// CHECK: lsr x{{\d+}}, x{{\d+}}, #32
+ /// CHECK-NOT: add w{{\d+}}, w{{\d+}}, w{{\d+}}, lsr #31
+ private static int $noinline$IntALenDivBy6(int[] arr) {
+ int r = arr.length / 6;
+ return r;
+ }
+
// A test case to check that 'asr' is used to get the high 32 bits of the result of
// 'dividend * magic'.
// Divisor -6 has the same property as divisor 6: no need to correct the result of
diff --git a/test/411-checker-hdiv-hrem-const/src/RemTest.java b/test/411-checker-hdiv-hrem-const/src/RemTest.java
index 2fae275..8dbd401 100644
--- a/test/411-checker-hdiv-hrem-const/src/RemTest.java
+++ b/test/411-checker-hdiv-hrem-const/src/RemTest.java
@@ -41,6 +41,11 @@
expectEquals(11, $noinline$IntRemBy18(65));
expectEquals(-11, $noinline$IntRemBy18(-65));
+ expectEquals(0, $noinline$IntALenRemBy18(new int[0]));
+ expectEquals(1, $noinline$IntALenRemBy18(new int[1]));
+ expectEquals(0, $noinline$IntALenRemBy18(new int[18]));
+ expectEquals(11, $noinline$IntALenRemBy18(new int[65]));
+
expectEquals(0, $noinline$IntRemByMinus18(0));
expectEquals(1, $noinline$IntRemByMinus18(1));
expectEquals(-1, $noinline$IntRemByMinus18(-1));
@@ -57,6 +62,11 @@
expectEquals(1, $noinline$IntRemBy7(22));
expectEquals(-1, $noinline$IntRemBy7(-22));
+ expectEquals(0, $noinline$IntALenRemBy7(new int[0]));
+ expectEquals(1, $noinline$IntALenRemBy7(new int[1]));
+ expectEquals(0, $noinline$IntALenRemBy7(new int[7]));
+ expectEquals(1, $noinline$IntALenRemBy7(new int[22]));
+
expectEquals(0, $noinline$IntRemByMinus7(0));
expectEquals(1, $noinline$IntRemByMinus7(1));
expectEquals(-1, $noinline$IntRemByMinus7(-1));
@@ -73,6 +83,11 @@
expectEquals(1, $noinline$IntRemBy6(19));
expectEquals(-1, $noinline$IntRemBy6(-19));
+ expectEquals(0, $noinline$IntALenRemBy6(new int[0]));
+ expectEquals(1, $noinline$IntALenRemBy6(new int[1]));
+ expectEquals(0, $noinline$IntALenRemBy6(new int[6]));
+ expectEquals(1, $noinline$IntALenRemBy6(new int[19]));
+
expectEquals(0, $noinline$IntRemByMinus6(0));
expectEquals(1, $noinline$IntRemByMinus6(1));
expectEquals(-1, $noinline$IntRemByMinus6(-1));
@@ -98,6 +113,24 @@
return r;
}
+ // A test case to check that a correcting 'add' is not generated for a non-negative
+ // dividend and a positive divisor.
+ //
+ /// CHECK-START-ARM: int RemTest.$noinline$IntALenRemBy18(int[]) disassembly (after)
+ /// CHECK: smull r{{\d+}}, r{{\d+}}, r{{\d+}}, r{{\d+}}
+ /// CHECK-NEXT: lsr{{s?}} r{{\d+}}, #2
+ /// CHECK-NEXT: mov{{s?}} r{{\d+}}, #18
+ /// CHECK-NEXT: mls r{{\d+}}, r{{\d+}}, r{{\d+}}, r{{\d+}}
+ //
+ /// CHECK-START-ARM64: int RemTest.$noinline$IntALenRemBy18(int[]) disassembly (after)
+ /// CHECK: lsr x{{\d+}}, x{{\d+}}, #34
+ /// CHECK-NEXT: mov w{{\d+}}, #0x12
+ /// CHECK-NEXT: msub w{{\d+}}, w{{\d+}}, w{{\d+}}, w{{\d+}}
+ private static int $noinline$IntALenRemBy18(int[] arr) {
+ int r = arr.length % 18;
+ return r;
+ }
+
// A test case to check that 'lsr' and 'asr' are combined into one 'asr'.
// Divisor -18 has the same property as divisor 18: no need to correct the
// result of get_high(dividend * magic). So there are no
@@ -131,6 +164,25 @@
return r;
}
+ // A test case to check that a correcting 'add' is not generated for a non-negative
+ // dividend and a positive divisor.
+ //
+ /// CHECK-START-ARM: int RemTest.$noinline$IntALenRemBy7(int[]) disassembly (after)
+ /// CHECK: smull r{{\d+}}, r{{\d+}}, r{{\d+}}, r{{\d+}}
+ /// CHECK-NEXT: add{{s?}} r{{\d+}}, r{{\d+}}
+ /// CHECK-NEXT: lsr{{s?}} r{{\d+}}, #2
+ /// CHECK-NEXT: mov{{s?}} r{{\d+}}, #7
+ /// CHECK-NEXT: mls r{{\d+}}, r{{\d+}}, r{{\d+}}, r{{\d+}}
+ //
+ /// CHECK-START-ARM64: int RemTest.$noinline$IntALenRemBy7(int[]) disassembly (after)
+ /// CHECK: lsr x{{\d+}}, x{{\d+}}, #34
+ /// CHECK-NEXT: mov w{{\d+}}, #0x7
+ /// CHECK-NEXT: msub w{{\d+}}, w{{\d+}}, w{{\d+}}, w{{\d+}}
+ private static int $noinline$IntALenRemBy7(int[] arr) {
+ int r = arr.length % 7;
+ return r;
+ }
+
// A test case to check that 'lsr' and 'add' are combined into one 'adds'.
// Divisor -7 has the same property as divisor 7: the result of get_high(dividend * magic)
// must be corrected. In this case it is a 'sub' instruction.
@@ -165,6 +217,23 @@
return r;
}
+ // A test case to check that a correcting 'add' is not generated for a non-negative
+ // dividend and a positive divisor.
+ //
+ /// CHECK-START-ARM: int RemTest.$noinline$IntALenRemBy6(int[]) disassembly (after)
+ /// CHECK: smull r{{\d+}}, r{{\d+}}, r{{\d+}}, r{{\d+}}
+ /// CHECK-NEXT: mov{{s?}} r{{\d+}}, #6
+ /// CHECK-NEXT: mls r{{\d+}}, r{{\d+}}, r{{\d+}}, r{{\d+}}
+ //
+ /// CHECK-START-ARM64: int RemTest.$noinline$IntALenRemBy6(int[]) disassembly (after)
+ /// CHECK: lsr x{{\d+}}, x{{\d+}}, #32
+ /// CHECK-NEXT: mov w{{\d+}}, #0x6
+ /// CHECK-NEXT: msub w{{\d+}}, w{{\d+}}, w{{\d+}}, w{{\d+}}
+ private static int $noinline$IntALenRemBy6(int[] arr) {
+ int r = arr.length % 6;
+ return r;
+ }
+
// A test case to check that 'asr' is used to get the high 32 bits of the result of
// 'dividend * magic'.
// Divisor -6 has the same property as divisor 6: no need to correct the result of