ART: Add HasNonNegativeInputAt and HasNonNegativeOrMinIntInputAt
When it can be quickly checked that an input operand in non-negative,
additional optimizations can be applied during code generation.
The CL adds HasNonNegativeInputAt and HasNonNegativeOrMinIntInputAt
which can be used to check if the input operand of an instruction at
the index is non-negative. They guarantee that at the time of checks
the instruction can have non-negative inputs. Other optimizations after
that might break the invariant.
Optimizations HRem/HDiv for ARM32/ARM64 are moved to used the new methods.
Test: 411-checker-hdiv-hrem-pow2
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: Icf8574699e003bba194097c4e39660de16aa53d9
diff --git a/compiler/optimizing/code_generator_arm64.cc b/compiler/optimizing/code_generator_arm64.cc
index 8a8530f..edc8321 100644
--- a/compiler/optimizing/code_generator_arm64.cc
+++ b/compiler/optimizing/code_generator_arm64.cc
@@ -3061,7 +3061,7 @@
Register dividend = InputRegisterAt(instruction, 0);
Register final_dividend;
- if (HasNonNegativeResultOrMinInt(instruction->GetLeft())) {
+ if (HasNonNegativeOrMinIntInputAt(instruction, 0)) {
// 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
@@ -3107,12 +3107,14 @@
}
}
-// Return true if the magic number was modified by subtracting 2^32. So dividend needs to be added.
+// Return true if the magic number was modified by subtracting 2^32(Int32 div) or 2^64(Int64 div).
+// So dividend needs to be added.
static inline bool NeedToAddDividend(int64_t magic_number, int64_t divisor) {
return divisor > 0 && magic_number < 0;
}
-// Return true if the magic number was modified by adding 2^32. So dividend needs to be subtracted.
+// Return true if the magic number was modified by adding 2^32(Int32 div) or 2^64(Int64 div).
+// So dividend needs to be subtracted.
static inline bool NeedToSubDividend(int64_t magic_number, int64_t divisor) {
return divisor < 0 && magic_number > 0;
}
@@ -3177,7 +3179,8 @@
// This allows to use CINC MI which has latency 1.
bool use_cond_inc = false;
- // As magic_number can be modified to fit into 32 bits, check whether the correction is needed.
+ // Some combinations of magic_number and the divisor require to correct the result.
+ // Check whether the correction is needed.
if (NeedToAddDividend(magic, imm)) {
__ Adds(temp, temp, dividend);
use_cond_inc = true;
@@ -3242,7 +3245,7 @@
// Extract the result from the high 32 bits and apply the final right shift.
DCHECK_LT(shift, 32);
- if (imm > 0 && IsGEZero(instruction->GetLeft())) {
+ if (imm > 0 && HasNonNegativeInputAt(instruction, 0)) {
// 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);
@@ -5633,7 +5636,7 @@
Register out = OutputRegister(instruction);
Register dividend = InputRegisterAt(instruction, 0);
- if (HasNonNegativeResultOrMinInt(instruction->GetLeft())) {
+ if (HasNonNegativeOrMinIntInputAt(instruction, 0)) {
// 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
diff --git a/compiler/optimizing/code_generator_arm_vixl.cc b/compiler/optimizing/code_generator_arm_vixl.cc
index d9a965c..ccb0609 100644
--- a/compiler/optimizing/code_generator_arm_vixl.cc
+++ b/compiler/optimizing/code_generator_arm_vixl.cc
@@ -4241,7 +4241,7 @@
}
};
- if (HasNonNegativeResultOrMinInt(instruction->GetLeft())) {
+ if (HasNonNegativeOrMinIntInputAt(instruction, 0)) {
// 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
@@ -4350,7 +4350,7 @@
}
};
- if (imm > 0 && IsGEZero(instruction->GetLeft())) {
+ if (imm > 0 && HasNonNegativeInputAt(instruction, 0)) {
// 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);
@@ -4433,7 +4433,7 @@
} else if (IsPowerOfTwo(AbsOrMin(value)) &&
value != 2 &&
value != -2 &&
- !HasNonNegativeResultOrMinInt(div)) {
+ !HasNonNegativeOrMinIntInputAt(div, 0)) {
// The "out" register is used as a temporary, so it overlaps with the inputs.
out_overlaps = Location::kOutputOverlap;
} else {
@@ -4547,7 +4547,7 @@
Location::OutputOverlap out_overlaps = Location::kNoOutputOverlap;
if (value == 1 || value == 0 || value == -1) {
// No temp register required.
- } else if (IsPowerOfTwo(AbsOrMin(value)) && !HasNonNegativeResultOrMinInt(rem)) {
+ } else if (IsPowerOfTwo(AbsOrMin(value)) && !HasNonNegativeOrMinIntInputAt(rem, 0)) {
// 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 9da5201..c19eda4 100644
--- a/compiler/optimizing/code_generator_utils.cc
+++ b/compiler/optimizing/code_generator_utils.cc
@@ -100,15 +100,17 @@
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);
+
+bool HasNonNegativeInputAt(HInstruction* instr, size_t i) {
+ HInstruction* input = instr->InputAt(i);
+ return IsGEZero(input);
+}
+
+bool HasNonNegativeOrMinIntInputAt(HInstruction* instr, size_t i) {
+ HInstruction* input = instr->InputAt(i);
+ return input->IsAbs() ||
+ IsInt64Value(input, DataType::MinValueOfIntegralType(input->GetType())) ||
+ HasNonNegativeInputAt(instr, i);
}
} // namespace art
diff --git a/compiler/optimizing/code_generator_utils.h b/compiler/optimizing/code_generator_utils.h
index 711f929..64665ad 100644
--- a/compiler/optimizing/code_generator_utils.h
+++ b/compiler/optimizing/code_generator_utils.h
@@ -40,9 +40,11 @@
: 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);
+// Check whether the i-th operand of instr is non-negative.
+bool HasNonNegativeInputAt(HInstruction* instr, size_t i);
+
+// Check whether the i-th operand of instr is non-negative or the minimum integer value.
+bool HasNonNegativeOrMinIntInputAt(HInstruction* instr, size_t i);
} // namespace art