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);
+ }
}
}