ARM: Optimize div/rem when dividend is compared with a non-negative
When a divisor is a positive constant and a dividend is compared with a
non-negative value, the result of the comparison can guarantee that the
dividend is non-negative. In such a case there is no need to generate
instructions correcting the result of div/rem.
The CL implements this optimization for ARM32/ARM64.
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: If1dc1389f6e34d2be3480ef620a626f389ca53a5
diff --git a/compiler/optimizing/code_generator_arm64.cc b/compiler/optimizing/code_generator_arm64.cc
index 95e2eea..46c65af 100644
--- a/compiler/optimizing/code_generator_arm64.cc
+++ b/compiler/optimizing/code_generator_arm64.cc
@@ -3151,6 +3151,59 @@
__ Msub(out, quotient, temp_imm, dividend);
}
+// Helper to generate code for HDiv/HRem instructions when a dividend is non-negative and
+// a divisor is a positive constant, not power of 2.
+void InstructionCodeGeneratorARM64::GenerateInt64UnsignedDivRemWithAnyPositiveConstant(
+ HBinaryOperation* instruction) {
+ DCHECK(instruction->IsDiv() || instruction->IsRem());
+ DCHECK(instruction->GetResultType() == DataType::Type::kInt64);
+
+ LocationSummary* locations = instruction->GetLocations();
+ Location second = locations->InAt(1);
+ DCHECK(second.IsConstant());
+
+ Register out = OutputRegister(instruction);
+ Register dividend = InputRegisterAt(instruction, 0);
+ int64_t imm = Int64FromConstant(second.GetConstant());
+ DCHECK_GT(imm, 0);
+
+ int64_t magic;
+ int shift;
+ CalculateMagicAndShiftForDivRem(imm, /* is_long= */ true, &magic, &shift);
+
+ UseScratchRegisterScope temps(GetVIXLAssembler());
+ Register temp = temps.AcquireSameSizeAs(out);
+
+ auto generate_unsigned_div_code = [this, magic, shift](Register out,
+ Register dividend,
+ Register temp) {
+ // temp = get_high(dividend * magic)
+ __ Mov(temp, magic);
+ if (magic > 0 && shift == 0) {
+ __ Smulh(out, dividend, temp);
+ } else {
+ __ Smulh(temp, dividend, temp);
+ if (magic < 0) {
+ // The negative magic means that the multiplier m is greater than INT64_MAX.
+ // In such a case shift is never 0. See the proof in
+ // InstructionCodeGeneratorARMVIXL::GenerateDivRemWithAnyConstant.
+ __ Add(temp, temp, dividend);
+ }
+ DCHECK_NE(shift, 0);
+ __ Lsr(out, temp, shift);
+ }
+ };
+
+ if (instruction->IsDiv()) {
+ generate_unsigned_div_code(out, dividend, temp);
+ } else {
+ generate_unsigned_div_code(temp, dividend, temp);
+ GenerateResultRemWithAnyConstant(out, dividend, temp, imm, &temps);
+ }
+}
+
+// Helper to generate code for HDiv/HRem instructions for any dividend and a constant divisor
+// (not power of 2).
void InstructionCodeGeneratorARM64::GenerateInt64DivRemWithAnyConstant(
HBinaryOperation* instruction) {
DCHECK(instruction->IsDiv() || instruction->IsRem());
@@ -3270,10 +3323,15 @@
}
}
-void InstructionCodeGeneratorARM64::GenerateDivRemWithAnyConstant(HBinaryOperation* instruction) {
+void InstructionCodeGeneratorARM64::GenerateDivRemWithAnyConstant(HBinaryOperation* instruction,
+ int64_t divisor) {
DCHECK(instruction->IsDiv() || instruction->IsRem());
if (instruction->GetResultType() == DataType::Type::kInt64) {
- GenerateInt64DivRemWithAnyConstant(instruction);
+ if (divisor > 0 && HasNonNegativeInputAt(instruction, 0)) {
+ GenerateInt64UnsignedDivRemWithAnyPositiveConstant(instruction);
+ } else {
+ GenerateInt64DivRemWithAnyConstant(instruction);
+ }
} else {
GenerateInt32DivRemWithAnyConstant(instruction);
}
@@ -3292,7 +3350,7 @@
} else {
// Cases imm == -1 or imm == 1 are handled by InstructionSimplifier.
DCHECK(imm < -2 || imm > 2) << imm;
- GenerateDivRemWithAnyConstant(instruction);
+ GenerateDivRemWithAnyConstant(instruction, imm);
}
}
@@ -5684,7 +5742,7 @@
GenerateIntRemForPower2Denom(instruction);
} else {
DCHECK(imm < -2 || imm > 2) << imm;
- GenerateDivRemWithAnyConstant(instruction);
+ GenerateDivRemWithAnyConstant(instruction, imm);
}
}
diff --git a/compiler/optimizing/code_generator_arm64.h b/compiler/optimizing/code_generator_arm64.h
index 5c62e0a..04b2c54 100644
--- a/compiler/optimizing/code_generator_arm64.h
+++ b/compiler/optimizing/code_generator_arm64.h
@@ -375,9 +375,10 @@
int64_t divisor,
// This function may acquire a scratch register.
vixl::aarch64::UseScratchRegisterScope* temps_scope);
+ void GenerateInt64UnsignedDivRemWithAnyPositiveConstant(HBinaryOperation* instruction);
void GenerateInt64DivRemWithAnyConstant(HBinaryOperation* instruction);
void GenerateInt32DivRemWithAnyConstant(HBinaryOperation* instruction);
- void GenerateDivRemWithAnyConstant(HBinaryOperation* instruction);
+ void GenerateDivRemWithAnyConstant(HBinaryOperation* instruction, int64_t divisor);
void GenerateIntDiv(HDiv* instruction);
void GenerateIntDivForConstDenom(HDiv *instruction);
void GenerateIntDivForPower2Denom(HDiv *instruction);
diff --git a/compiler/optimizing/code_generator_utils.cc b/compiler/optimizing/code_generator_utils.cc
index c19eda4..abec264 100644
--- a/compiler/optimizing/code_generator_utils.cc
+++ b/compiler/optimizing/code_generator_utils.cc
@@ -100,10 +100,149 @@
return !cond_input->IsCondition() || !cond_input->IsEmittedAtUseSite();
}
+// A helper class to group functions analyzing if values are non-negative
+// at the point of use. The class keeps some context used by the functions.
+// The class is not supposed to be used directly or its instances to be kept.
+// The main function using it is HasNonNegativeInputAt.
+// If you want to use the class methods you need to become a friend of the class.
+class UnsignedUseAnalyzer {
+ private:
+ explicit UnsignedUseAnalyzer(ArenaAllocator* allocator)
+ : seen_values_(allocator->Adapter(kArenaAllocCodeGenerator)) {
+ }
+
+ bool IsNonNegativeUse(HInstruction* target_user, HInstruction* value);
+ bool IsComparedValueNonNegativeInBlock(HInstruction* value,
+ HCondition* cond,
+ HBasicBlock* target_block);
+
+ ArenaSet<HInstruction*> seen_values_;
+
+ friend bool HasNonNegativeInputAt(HInstruction* instr, size_t i);
+};
+
+// Check that the value compared with a non-negavite value is
+// non-negative in the specified basic block.
+bool UnsignedUseAnalyzer::IsComparedValueNonNegativeInBlock(HInstruction* value,
+ HCondition* cond,
+ HBasicBlock* target_block) {
+ DCHECK(cond->HasInput(value));
+
+ // To simplify analysis, we require:
+ // 1. The condition basic block and target_block to be different.
+ // 2. The condition basic block to end with HIf.
+ // 3. HIf to use the condition.
+ if (cond->GetBlock() == target_block ||
+ !cond->GetBlock()->EndsWithIf() ||
+ cond->GetBlock()->GetLastInstruction()->InputAt(0) != cond) {
+ return false;
+ }
+
+ // We need to find a successor basic block of HIf for the case when instr is non-negative.
+ // If the successor dominates target_block, instructions in target_block see a non-negative value.
+ HIf* if_instr = cond->GetBlock()->GetLastInstruction()->AsIf();
+ HBasicBlock* successor = nullptr;
+ switch (cond->GetCondition()) {
+ case kCondGT:
+ case kCondGE: {
+ if (cond->GetLeft() == value) {
+ // The expression is v > A or v >= A.
+ // If A is non-negative, we need the true successor.
+ if (IsNonNegativeUse(cond, cond->GetRight())) {
+ successor = if_instr->IfTrueSuccessor();
+ } else {
+ return false;
+ }
+ } else {
+ DCHECK_EQ(cond->GetRight(), value);
+ // The expression is A > v or A >= v.
+ // If A is non-negative, we need the false successor.
+ if (IsNonNegativeUse(cond, cond->GetLeft())) {
+ successor = if_instr->IfFalseSuccessor();
+ } else {
+ return false;
+ }
+ }
+ break;
+ }
+
+ case kCondLT:
+ case kCondLE: {
+ if (cond->GetLeft() == value) {
+ // The expression is v < A or v <= A.
+ // If A is non-negative, we need the false successor.
+ if (IsNonNegativeUse(cond, cond->GetRight())) {
+ successor = if_instr->IfFalseSuccessor();
+ } else {
+ return false;
+ }
+ } else {
+ DCHECK_EQ(cond->GetRight(), value);
+ // The expression is A < v or A <= v.
+ // If A is non-negative, we need the true successor.
+ if (IsNonNegativeUse(cond, cond->GetLeft())) {
+ successor = if_instr->IfTrueSuccessor();
+ } else {
+ return false;
+ }
+ }
+ break;
+ }
+
+ default:
+ return false;
+ }
+ DCHECK_NE(successor, nullptr);
+
+ return successor->Dominates(target_block);
+}
+
+// Check the value used by target_user is non-negative.
+bool UnsignedUseAnalyzer::IsNonNegativeUse(HInstruction* target_user, HInstruction* value) {
+ DCHECK(target_user->HasInput(value));
+
+ // Prevent infinitive recursion which can happen when the value is an induction variable.
+ if (!seen_values_.insert(value).second) {
+ return false;
+ }
+
+ // Check if the value is always non-negative.
+ if (IsGEZero(value)) {
+ return true;
+ }
+
+ for (const HUseListNode<HInstruction*>& use : value->GetUses()) {
+ HInstruction* user = use.GetUser();
+ if (user == target_user) {
+ continue;
+ }
+
+ // If the value is compared with some non-negative value, this can guarantee the value to be
+ // non-negative at its use.
+ // JFYI: We're not using HTypeConversion to bind the new information because it would
+ // increase the complexity of optimizations: HTypeConversion can create a dependency
+ // which does not exist in the input program, for example:
+ // between two uses, 1st - cmp, 2nd - target_user.
+ if (user->IsCondition()) {
+ // The condition must dominate target_user to guarantee that the value is always checked
+ // before it is used by target_user.
+ if (user->GetBlock()->Dominates(target_user->GetBlock()) &&
+ IsComparedValueNonNegativeInBlock(value, user->AsCondition(), target_user->GetBlock())) {
+ return true;
+ }
+ }
+
+ // TODO The value is non-negative if it is used as an array index before.
+ // TODO The value is non-negative if it is initialized by a positive number and all of its
+ // modifications keep the value non-negative, for example the division operation.
+ }
+
+ return false;
+}
bool HasNonNegativeInputAt(HInstruction* instr, size_t i) {
- HInstruction* input = instr->InputAt(i);
- return IsGEZero(input);
+ UnsignedUseAnalyzer analyzer(instr->GetBlock()->GetGraph()->GetAllocator());
+ return analyzer.IsNonNegativeUse(instr, instr->InputAt(i));
}
bool HasNonNegativeOrMinIntInputAt(HInstruction* instr, size_t i) {