ARM: Optimize Div/Rem by 2^n for non-negative dividends
When it can be proved that dividends are non-negative or the min integer
if their type is integral, there is no need to generate instructions
correcting the result.
The CL implements this optimization for ARM32/ARM64.
Test: 411-checker-hdiv-hrem-pow2
Test: test.py --host --optimizing --jit --gtest --interpreter
Test: test.py -target --optimizing --jit --interpreter
Test: run-gtests.sh
Change-Id: I11211a42918b5801fce8e78f305e69549739c23c
diff --git a/compiler/optimizing/code_generator_arm64.cc b/compiler/optimizing/code_generator_arm64.cc
index b7f519b..ba5b1b7 100644
--- a/compiler/optimizing/code_generator_arm64.cc
+++ b/compiler/optimizing/code_generator_arm64.cc
@@ -3060,22 +3060,50 @@
Register out = OutputRegister(instruction);
Register dividend = InputRegisterAt(instruction, 0);
- if (abs_imm == 2) {
- int bits = DataType::Size(instruction->GetResultType()) * kBitsPerByte;
- __ Add(out, dividend, Operand(dividend, LSR, bits - 1));
+ Register final_dividend;
+ if (HasNonNegativeResultOrMinInt(instruction->GetLeft())) {
+ // No need to adjust the result for non-negative dividends or the INT32_MIN/INT64_MIN dividends.
+ // NOTE: The generated code for HDiv correctly works for the INT32_MIN/INT64_MIN dividends:
+ // imm == 2
+ // add out, dividend(0x80000000), dividend(0x80000000), lsr #31 => out = 0x80000001
+ // asr out, out(0x80000001), #1 => out = 0xc0000000
+ // This is the same as 'asr out, 0x80000000, #1'
+ //
+ // imm > 2
+ // add temp, dividend(0x80000000), imm - 1 => temp = 0b10..01..1, where the number
+ // of the rightmost 1s is ctz_imm.
+ // cmp dividend(0x80000000), 0 => N = 1, V = 0 (lt is true)
+ // csel out, temp(0b10..01..1), dividend(0x80000000), lt => out = 0b10..01..1
+ // asr out, out(0b10..01..1), #ctz_imm => out = 0b1..10..0, where the number of the
+ // leftmost 1s is ctz_imm + 1.
+ // This is the same as 'asr out, dividend(0x80000000), #ctz_imm'.
+ //
+ // imm == INT32_MIN
+ // add tmp, dividend(0x80000000), #0x7fffffff => tmp = -1
+ // cmp dividend(0x80000000), 0 => N = 1, V = 0 (lt is true)
+ // csel out, temp(-1), dividend(0x80000000), lt => out = -1
+ // neg out, out(-1), asr #31 => out = 1
+ // This is the same as 'neg out, dividend(0x80000000), asr #31'.
+ final_dividend = dividend;
} else {
- UseScratchRegisterScope temps(GetVIXLAssembler());
- Register temp = temps.AcquireSameSizeAs(out);
- __ Add(temp, dividend, abs_imm - 1);
- __ Cmp(dividend, 0);
- __ Csel(out, temp, dividend, lt);
+ if (abs_imm == 2) {
+ int bits = DataType::Size(instruction->GetResultType()) * kBitsPerByte;
+ __ Add(out, dividend, Operand(dividend, LSR, bits - 1));
+ } else {
+ UseScratchRegisterScope temps(GetVIXLAssembler());
+ Register temp = temps.AcquireSameSizeAs(out);
+ __ Add(temp, dividend, abs_imm - 1);
+ __ Cmp(dividend, 0);
+ __ Csel(out, temp, dividend, lt);
+ }
+ final_dividend = out;
}
int ctz_imm = CTZ(abs_imm);
if (imm > 0) {
- __ Asr(out, out, ctz_imm);
+ __ Asr(out, final_dividend, ctz_imm);
} else {
- __ Neg(out, Operand(out, ASR, ctz_imm));
+ __ Neg(out, Operand(final_dividend, ASR, ctz_imm));
}
}
@@ -5587,18 +5615,27 @@
Register out = OutputRegister(instruction);
Register dividend = InputRegisterAt(instruction, 0);
- if (abs_imm == 2) {
- __ Cmp(dividend, 0);
- __ And(out, dividend, 1);
- __ Csneg(out, out, out, ge);
- } else {
- UseScratchRegisterScope temps(GetVIXLAssembler());
- Register temp = temps.AcquireSameSizeAs(out);
-
- __ Negs(temp, dividend);
+ if (HasNonNegativeResultOrMinInt(instruction->GetLeft())) {
+ // No need to adjust the result for non-negative dividends or the INT32_MIN/INT64_MIN dividends.
+ // NOTE: The generated code for HRem correctly works for the INT32_MIN/INT64_MIN dividends.
+ // INT*_MIN % imm must be 0 for any imm of power 2. 'and' works only with bits
+ // 0..30 (Int32 case)/0..62 (Int64 case) of a dividend. For INT32_MIN/INT64_MIN they are zeros.
+ // So 'and' always produces zero.
__ And(out, dividend, abs_imm - 1);
- __ And(temp, temp, abs_imm - 1);
- __ Csneg(out, out, temp, mi);
+ } else {
+ if (abs_imm == 2) {
+ __ Cmp(dividend, 0);
+ __ And(out, dividend, 1);
+ __ Csneg(out, out, out, ge);
+ } else {
+ UseScratchRegisterScope temps(GetVIXLAssembler());
+ Register temp = temps.AcquireSameSizeAs(out);
+
+ __ Negs(temp, dividend);
+ __ And(out, dividend, abs_imm - 1);
+ __ And(temp, temp, abs_imm - 1);
+ __ Csneg(out, out, temp, mi);
+ }
}
}
diff --git a/compiler/optimizing/code_generator_arm_vixl.cc b/compiler/optimizing/code_generator_arm_vixl.cc
index 551de55..db9ab3b 100644
--- a/compiler/optimizing/code_generator_arm_vixl.cc
+++ b/compiler/optimizing/code_generator_arm_vixl.cc
@@ -4226,21 +4226,69 @@
uint32_t abs_imm = static_cast<uint32_t>(AbsOrMin(imm));
int ctz_imm = CTZ(abs_imm);
- vixl32::Register add_right_input = dividend;
- if (ctz_imm > 1) {
- __ Asr(out, dividend, 31);
- add_right_input = out;
- }
- __ Add(out, dividend, Operand(add_right_input, vixl32::LSR, 32 - ctz_imm));
-
- if (instruction->IsDiv()) {
- __ Asr(out, out, ctz_imm);
+ auto generate_div_code = [this, imm, ctz_imm](vixl32::Register out, vixl32::Register in) {
+ __ Asr(out, in, ctz_imm);
if (imm < 0) {
__ Rsb(out, out, 0);
}
+ };
+
+ if (HasNonNegativeResultOrMinInt(instruction->GetLeft())) {
+ // No need to adjust the result for non-negative dividends or the INT32_MIN dividend.
+ // NOTE: The generated code for HDiv/HRem correctly works for the INT32_MIN dividend:
+ // imm == 2
+ // HDiv
+ // add out, dividend(0x80000000), dividend(0x80000000), lsr #31 => out = 0x80000001
+ // asr out, out(0x80000001), #1 => out = 0xc0000000
+ // This is the same as 'asr out, dividend(0x80000000), #1'
+ //
+ // imm > 2
+ // HDiv
+ // asr out, dividend(0x80000000), #31 => out = -1
+ // add out, dividend(0x80000000), out(-1), lsr #(32 - ctz_imm) => out = 0b10..01..1,
+ // where the number of the rightmost 1s is ctz_imm.
+ // asr out, out(0b10..01..1), #ctz_imm => out = 0b1..10..0, where the number of the
+ // leftmost 1s is ctz_imm + 1.
+ // This is the same as 'asr out, dividend(0x80000000), #ctz_imm'.
+ //
+ // imm == INT32_MIN
+ // HDiv
+ // asr out, dividend(0x80000000), #31 => out = -1
+ // add out, dividend(0x80000000), out(-1), lsr #1 => out = 0xc0000000
+ // asr out, out(0xc0000000), #31 => out = -1
+ // rsb out, out(-1), #0 => out = 1
+ // This is the same as
+ // asr out, dividend(0x80000000), #31
+ // rsb out, out, #0
+ //
+ //
+ // INT_MIN % imm must be 0 for any imm of power 2. 'and' and 'ubfx' work only with bits
+ // 0..30 of a dividend. For INT32_MIN those bits are zeros. So 'and' and 'ubfx' always
+ // produce zero.
+ if (instruction->IsDiv()) {
+ generate_div_code(out, dividend);
+ } else {
+ if (GetVIXLAssembler()->IsModifiedImmediate(abs_imm - 1)) {
+ __ And(out, dividend, abs_imm - 1);
+ } else {
+ __ Ubfx(out, dividend, 0, ctz_imm);
+ }
+ return;
+ }
} else {
- __ Bfc(out, 0, ctz_imm);
- __ Sub(out, dividend, out);
+ vixl32::Register add_right_input = dividend;
+ if (ctz_imm > 1) {
+ __ Asr(out, dividend, 31);
+ add_right_input = out;
+ }
+ __ Add(out, dividend, Operand(add_right_input, vixl32::LSR, 32 - ctz_imm));
+
+ if (instruction->IsDiv()) {
+ generate_div_code(out, out);
+ } else {
+ __ Bfc(out, 0, ctz_imm);
+ __ Sub(out, dividend, out);
+ }
}
}
@@ -4331,7 +4379,10 @@
Location::OutputOverlap out_overlaps = Location::kNoOutputOverlap;
if (value == 1 || value == 0 || value == -1) {
// No temp register required.
- } else if (IsPowerOfTwo(AbsOrMin(value))) {
+ } else if (IsPowerOfTwo(AbsOrMin(value)) &&
+ value != 2 &&
+ value != -2 &&
+ !HasNonNegativeResultOrMinInt(div)) {
// The "out" register is used as a temporary, so it overlaps with the inputs.
out_overlaps = Location::kOutputOverlap;
} else {
@@ -4445,7 +4496,7 @@
Location::OutputOverlap out_overlaps = Location::kNoOutputOverlap;
if (value == 1 || value == 0 || value == -1) {
// No temp register required.
- } else if (IsPowerOfTwo(AbsOrMin(value))) {
+ } else if (IsPowerOfTwo(AbsOrMin(value)) && !HasNonNegativeResultOrMinInt(rem)) {
// The "out" register is used as a temporary, so it overlaps with the inputs.
out_overlaps = Location::kOutputOverlap;
} else {
diff --git a/compiler/optimizing/code_generator_utils.cc b/compiler/optimizing/code_generator_utils.cc
index dd47a1f..9da5201 100644
--- a/compiler/optimizing/code_generator_utils.cc
+++ b/compiler/optimizing/code_generator_utils.cc
@@ -100,4 +100,15 @@
return !cond_input->IsCondition() || !cond_input->IsEmittedAtUseSite();
}
+bool HasNonNegativeResultOrMinInt(HInstruction* instruction) {
+ // 1. The instruction itself has always a non-negative result or the min value of
+ // the integral type if the instruction has the integral type.
+ // 2. TODO: The instruction can be an expression which uses an induction variable.
+ // Induction variable often start from 0 and are only increased. Such an
+ // expression might be always non-negative.
+ return instruction->IsAbs() ||
+ IsInt64Value(instruction, DataType::MinValueOfIntegralType(instruction->GetType())) ||
+ IsGEZero(instruction);
+}
+
} // namespace art
diff --git a/compiler/optimizing/code_generator_utils.h b/compiler/optimizing/code_generator_utils.h
index a6b41c0..711f929 100644
--- a/compiler/optimizing/code_generator_utils.h
+++ b/compiler/optimizing/code_generator_utils.h
@@ -40,6 +40,10 @@
: std::abs(value);
}
+// Return true if the specified instruction produces only non-negative results or the min value of
+// the integral type if the instruction has the integral type.
+bool HasNonNegativeResultOrMinInt(HInstruction* instruction);
+
} // namespace art
#endif // ART_COMPILER_OPTIMIZING_CODE_GENERATOR_UTILS_H_
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
index 4c78fa8..72c2064 100644
--- a/compiler/optimizing/induction_var_range.cc
+++ b/compiler/optimizing/induction_var_range.cc
@@ -70,28 +70,6 @@
return pow;
}
-/**
- * Detects an instruction that is >= 0. As long as the value is carried by
- * a single instruction, arithmetic wrap-around cannot occur.
- */
-static bool IsGEZero(HInstruction* instruction) {
- DCHECK(instruction != nullptr);
- if (instruction->IsArrayLength()) {
- return true;
- } else if (instruction->IsMin()) {
- // Instruction MIN(>=0, >=0) is >= 0.
- return IsGEZero(instruction->InputAt(0)) &&
- IsGEZero(instruction->InputAt(1));
- } else if (instruction->IsAbs()) {
- // Instruction ABS(>=0) is >= 0.
- // NOTE: ABS(minint) = minint prevents assuming
- // >= 0 without looking at the argument.
- return IsGEZero(instruction->InputAt(0));
- }
- int64_t value = -1;
- return IsInt64AndGet(instruction, &value) && value >= 0;
-}
-
/** Hunts "under the hood" for a suitable instruction at the hint. */
static bool IsMaxAtHint(
HInstruction* instruction, HInstruction* hint, /*out*/HInstruction** suitable) {
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index ec4b79e..64e62fd 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -3173,4 +3173,22 @@
resolved_method_ = method;
}
+bool IsGEZero(HInstruction* instruction) {
+ DCHECK(instruction != nullptr);
+ if (instruction->IsArrayLength()) {
+ return true;
+ } else if (instruction->IsMin()) {
+ // Instruction MIN(>=0, >=0) is >= 0.
+ return IsGEZero(instruction->InputAt(0)) &&
+ IsGEZero(instruction->InputAt(1));
+ } else if (instruction->IsAbs()) {
+ // Instruction ABS(>=0) is >= 0.
+ // NOTE: ABS(minint) = minint prevents assuming
+ // >= 0 without looking at the argument.
+ return IsGEZero(instruction->InputAt(0));
+ }
+ int64_t value = -1;
+ return IsInt64AndGet(instruction, &value) && value >= 0;
+}
+
} // namespace art
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 0eece84..214c7ba 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -8209,6 +8209,10 @@
bool HasEnvironmentUsedByOthers(HInstruction* instruction);
void ResetEnvironmentInputRecords(HInstruction* instruction);
+// Detects an instruction that is >= 0. As long as the value is carried by
+// a single instruction, arithmetic wrap-around cannot occur.
+bool IsGEZero(HInstruction* instruction);
+
} // namespace art
#endif // ART_COMPILER_OPTIMIZING_NODES_H_