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) {
diff --git a/test/411-checker-hdiv-hrem-const/src/DivTest.java b/test/411-checker-hdiv-hrem-const/src/DivTest.java
index ba6ca86..60230c4 100644
--- a/test/411-checker-hdiv-hrem-const/src/DivTest.java
+++ b/test/411-checker-hdiv-hrem-const/src/DivTest.java
@@ -27,6 +27,12 @@
}
}
+ private static void expectEquals(String expected, String result) {
+ if (!expected.equals(result)) {
+ throw new Error("Expected: " + expected + ", found: " + result);
+ }
+ }
+
public static void main() {
divInt();
divLong();
@@ -95,6 +101,25 @@
expectEquals(1, $noinline$IntDivByMinus6(-6));
expectEquals(-3, $noinline$IntDivByMinus6(19));
expectEquals(3, $noinline$IntDivByMinus6(-19));
+
+ expectEquals(2, $noinline$UnsignedIntDiv01(12));
+ expectEquals(2, $noinline$UnsignedIntDiv02(12));
+ expectEquals(2, $noinline$UnsignedIntDiv03(12));
+ expectEquals(2, $noinline$UnsignedIntDiv04(12));
+ expectEquals("01", $noinline$UnsignedIntDiv05(10));
+ expectEquals("321", $noinline$UnsignedIntDiv05(123));
+ expectEquals(1, $noinline$UnsignedIntDiv06(101));
+ expectEquals(1, $noinline$UnsignedIntDiv07(10));
+ expectEquals(1, $noinline$UnsignedIntDiv07(100));
+ expectEquals(10, $noinline$UnsignedIntDiv08(100));
+ expectEquals(11, $noinline$UnsignedIntDiv08(101));
+
+ expectEquals(-2, $noinline$SignedIntDiv01(-12));
+ expectEquals(-2, $noinline$SignedIntDiv02(-12));
+ expectEquals(2, $noinline$SignedIntDiv03(-12));
+ expectEquals(2, $noinline$SignedIntDiv04(-12, true));
+ expectEquals(-2, $noinline$SignedIntDiv05(-12, 0,-13));
+ expectEquals(-2, $noinline$SignedIntDiv06(-12));
}
// A test case to check that 'lsr' and 'asr' are combined into one 'asr'.
@@ -234,6 +259,303 @@
return r;
}
+ private static int $noinline$Negate(int v) {
+ return -v;
+ }
+
+ private static int $noinline$Decrement(int v) {
+ return v - 1;
+ }
+
+ private static int $noinline$Increment(int v) {
+ return v + 1;
+ }
+
+ // 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$UnsignedIntDiv01(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$UnsignedIntDiv01(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$UnsignedIntDiv01(int v) {
+ int c = 0;
+ if (v > 0) {
+ c = v / 6;
+ } else {
+ c = $noinline$Negate(v); // This is to prevent from using Select.
+ }
+ return c;
+ }
+
+ // 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$UnsignedIntDiv02(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$UnsignedIntDiv02(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$UnsignedIntDiv02(int v) {
+ int c = 0;
+ if (0 < v) {
+ c = v / 6;
+ } else {
+ c = $noinline$Negate(v); // This is to prevent from using Select.
+ }
+ return c;
+ }
+
+ // 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$UnsignedIntDiv03(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$UnsignedIntDiv03(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$UnsignedIntDiv03(int v) {
+ int c = 0;
+ if (v >= 0) {
+ c = v / 6;
+ } else {
+ c = $noinline$Negate(v); // This is to prevent from using Select.
+ }
+ return c;
+ }
+
+ // 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$UnsignedIntDiv04(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$UnsignedIntDiv04(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$UnsignedIntDiv04(int v) {
+ int c = 0;
+ if (0 <= v) {
+ c = v / 6;
+ } else {
+ c = $noinline$Negate(v); // This is to prevent from using Select.
+ }
+ return c;
+ }
+
+ // A test case to check that a correcting 'add' is not generated for a non-negative
+ // dividend and a positive divisor.
+ //
+ /// CHECK-START-ARM: java.lang.String DivTest.$noinline$UnsignedIntDiv05(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: java.lang.String DivTest.$noinline$UnsignedIntDiv05(int) disassembly (after)
+ /// CHECK: smull x{{\d+}}, w{{\d+}}, w{{\d+}}
+ /// CHECK: lsr x{{\d+}}, x{{\d+}}, #34
+ /// CHECK-NOT: add w{{\d+}}, w{{\d+}}, w{{\d+}}, lsr #31
+ private static String $noinline$UnsignedIntDiv05(int v) {
+ String r = "";
+ while (v > 0) {
+ int d = v % 10;
+ r += (char)(d + '0');
+ v /= 10;
+ }
+ 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$UnsignedIntDiv06(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$UnsignedIntDiv06(int) disassembly (after)
+ /// CHECK: smull x{{\d+}}, w{{\d+}}, w{{\d+}}
+ /// CHECK: lsr x{{\d+}}, x{{\d+}}, #34
+ /// CHECK-NOT: add w{{\d+}}, w{{\d+}}, w{{\d+}}, lsr #31
+ private static int $noinline$UnsignedIntDiv06(int v) {
+ int c = 0;
+ for(; v > 100; ++c) {
+ v /= 10;
+ }
+ return c;
+ }
+
+ // 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$UnsignedIntDiv07(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$UnsignedIntDiv07(int) disassembly (after)
+ /// CHECK: smull x{{\d+}}, w{{\d+}}, w{{\d+}}
+ /// CHECK: lsr x{{\d+}}, x{{\d+}}, #34
+ /// CHECK-NOT: add w{{\d+}}, w{{\d+}}, w{{\d+}}, lsr #31
+ private static int $noinline$UnsignedIntDiv07(int v) {
+ while (v > 0 && (v % 10) == 0) {
+ v /= 10;
+ }
+ return v;
+ }
+
+ // 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$UnsignedIntDiv08(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$UnsignedIntDiv08(int) disassembly (after)
+ /// CHECK: smull x{{\d+}}, w{{\d+}}, w{{\d+}}
+ /// CHECK: lsr x{{\d+}}, x{{\d+}}, #34
+ /// CHECK-NOT: add w{{\d+}}, w{{\d+}}, w{{\d+}}, lsr #31
+ private static int $noinline$UnsignedIntDiv08(int v) {
+ if (v < 10) {
+ v = $noinline$Negate(v); // This is to prevent from using Select.
+ } else {
+ v = (v % 10) + (v / 10);
+ }
+ return v;
+ }
+
+ // A test case to check that a correcting 'add' is generated for a negative
+ // dividend and a positive divisor.
+ //
+ /// CHECK-START-ARM: int DivTest.$noinline$SignedIntDiv01(int) disassembly (after)
+ /// CHECK: smull r{{\d+}}, r{{\d+}}, r{{\d+}}, r{{\d+}}
+ /// CHECK-NEXT: sub r{{\d+}}, r{{\d+}}, r{{\d+}}, asr #31
+ //
+ /// CHECK-START-ARM64: int DivTest.$noinline$SignedIntDiv01(int) disassembly (after)
+ /// CHECK: asr x{{\d+}}, x{{\d+}}, #32
+ /// CHECK-NEXT: add w{{\d+}}, w{{\d+}}, w{{\d+}}, lsr #31
+ private static int $noinline$SignedIntDiv01(int v) {
+ int c = 0;
+ if (v < 0) {
+ c = v / 6;
+ } else {
+ c = $noinline$Decrement(v); // This is to prevent from using Select.
+ }
+ return c;
+ }
+
+ // A test case to check that a correcting 'add' is generated for a negative
+ // dividend and a positive divisor.
+ //
+ /// CHECK-START-ARM: int DivTest.$noinline$SignedIntDiv02(int) disassembly (after)
+ /// CHECK: smull r{{\d+}}, r{{\d+}}, r{{\d+}}, r{{\d+}}
+ /// CHECK-NEXT: sub r{{\d+}}, r{{\d+}}, r{{\d+}}, asr #31
+ //
+ /// CHECK-START-ARM64: int DivTest.$noinline$SignedIntDiv02(int) disassembly (after)
+ /// CHECK: asr x{{\d+}}, x{{\d+}}, #32
+ /// CHECK-NEXT: add w{{\d+}}, w{{\d+}}, w{{\d+}}, lsr #31
+ private static int $noinline$SignedIntDiv02(int v) {
+ int c = 0;
+ if (v <= 0) {
+ c = v / 6;
+ } else {
+ c = $noinline$Decrement(v); // This is to prevent from using Select.
+ }
+ return c;
+ }
+
+ // A test case to check that a correcting 'add' is generated for signed division.
+ //
+ /// CHECK-START-ARM: int DivTest.$noinline$SignedIntDiv03(int) disassembly (after)
+ /// CHECK: smull r{{\d+}}, r{{\d+}}, r{{\d+}}, r{{\d+}}
+ /// CHECK-NEXT: sub r{{\d+}}, r{{\d+}}, r{{\d+}}, asr #31
+ //
+ /// CHECK-START-ARM64: int DivTest.$noinline$SignedIntDiv03(int) disassembly (after)
+ /// CHECK: asr x{{\d+}}, x{{\d+}}, #32
+ /// CHECK-NEXT: add w{{\d+}}, w{{\d+}}, w{{\d+}}, lsr #31
+ private static int $noinline$SignedIntDiv03(int v) {
+ boolean positive = (v > 0);
+ int c = v / 6;
+ if (!positive) {
+ c = $noinline$Negate(c); // This is to prevent from using Select.
+ }
+ return c;
+ }
+
+ // A test case to check that a correcting 'add' is generated for signed division.
+ //
+ /// CHECK-START-ARM: int DivTest.$noinline$SignedIntDiv04(int, boolean) disassembly (after)
+ /// CHECK: smull r{{\d+}}, r{{\d+}}, r{{\d+}}, r{{\d+}}
+ /// CHECK-NEXT: sub r{{\d+}}, r{{\d+}}, r{{\d+}}, asr #31
+ //
+ /// CHECK-START-ARM64: int DivTest.$noinline$SignedIntDiv04(int, boolean) disassembly (after)
+ /// CHECK: asr x{{\d+}}, x{{\d+}}, #32
+ /// CHECK-NEXT: add w{{\d+}}, w{{\d+}}, w{{\d+}}, lsr #31
+ private static int $noinline$SignedIntDiv04(int v, boolean apply_div) {
+ int c = 0;
+ boolean positive = (v > 0);
+ if (apply_div) {
+ c = v / 6;
+ } else {
+ c = $noinline$Decrement(v); // This is to prevent from using Select.
+ }
+ if (!positive) {
+ c = $noinline$Negate(c); // This is to prevent from using Select.
+ }
+ return c;
+ }
+
+ // A test case to check that a correcting 'add' is generated for signed division.
+ //
+ /// CHECK-START-ARM: int DivTest.$noinline$SignedIntDiv05(int, int, int) disassembly (after)
+ /// CHECK: smull r{{\d+}}, r{{\d+}}, r{{\d+}}, r{{\d+}}
+ /// CHECK-NEXT: sub r{{\d+}}, r{{\d+}}, r{{\d+}}, asr #31
+ //
+ /// CHECK-START-ARM64: int DivTest.$noinline$SignedIntDiv05(int, int, int) disassembly (after)
+ /// CHECK: asr x{{\d+}}, x{{\d+}}, #32
+ /// CHECK-NEXT: add w{{\d+}}, w{{\d+}}, w{{\d+}}, lsr #31
+ private static int $noinline$SignedIntDiv05(int v, int a, int b) {
+ int c = 0;
+
+ if (v < a)
+ c = $noinline$Increment(c); // This is to prevent from using Select.
+
+ if (b < a)
+ c = $noinline$Increment(c); // This is to prevent from using Select.
+
+ if (v > b) {
+ c = v / 6;
+ } else {
+ c = $noinline$Increment(c); // This is to prevent from using Select.
+ }
+
+ return c;
+ }
+
+ // A test case to check that a correcting 'add' is generated for signed division.
+ //
+ /// CHECK-START-ARM: int DivTest.$noinline$SignedIntDiv06(int) disassembly (after)
+ /// CHECK: smull r{{\d+}}, r{{\d+}}, r{{\d+}}, r{{\d+}}
+ /// CHECK-NEXT: sub r{{\d+}}, r{{\d+}}, r{{\d+}}, asr #31
+ //
+ /// CHECK-START-ARM64: int DivTest.$noinline$SignedIntDiv06(int) disassembly (after)
+ /// CHECK: asr x{{\d+}}, x{{\d+}}, #32
+ /// CHECK-NEXT: add w{{\d+}}, w{{\d+}}, w{{\d+}}, lsr #31
+ private static int $noinline$SignedIntDiv06(int v) {
+ int c = v / 6;
+
+ if (v > 0) {
+ c = $noinline$Negate(c); // This is to prevent from using Select.
+ }
+
+ return c;
+ }
+
private static void divLong() {
expectEquals(0L, $noinline$LongDivBy18(0L));
expectEquals(0L, $noinline$LongDivBy18(1L));
@@ -298,6 +620,25 @@
expectEquals(1L, $noinline$LongDivByMinus100(-100L));
expectEquals(-3L, $noinline$LongDivByMinus100(301L));
expectEquals(3L, $noinline$LongDivByMinus100(-301L));
+
+ expectEquals(2L, $noinline$UnsignedLongDiv01(12L));
+ expectEquals(2L, $noinline$UnsignedLongDiv02(12L));
+ expectEquals(2L, $noinline$UnsignedLongDiv03(12L));
+ expectEquals(2L, $noinline$UnsignedLongDiv04(12L));
+ expectEquals("01", $noinline$UnsignedLongDiv05(10L));
+ expectEquals("321", $noinline$UnsignedLongDiv05(123L));
+ expectEquals(1L, $noinline$UnsignedLongDiv06(101L));
+ expectEquals(1L, $noinline$UnsignedLongDiv07(10L));
+ expectEquals(1L, $noinline$UnsignedLongDiv07(100L));
+ expectEquals(10L, $noinline$UnsignedLongDiv08(100L));
+ expectEquals(11L, $noinline$UnsignedLongDiv08(101L));
+
+ expectEquals(-2L, $noinline$SignedLongDiv01(-12L));
+ expectEquals(-2L, $noinline$SignedLongDiv02(-12L));
+ expectEquals(2L, $noinline$SignedLongDiv03(-12L));
+ expectEquals(2L, $noinline$SignedLongDiv04(-12L, true));
+ expectEquals(-2L, $noinline$SignedLongDiv05(-12L, 0L,-13L));
+ expectEquals(-2L, $noinline$SignedLongDiv06(-12L));
}
// Test cases for Int64 HDiv/HRem to check that optimizations implemented for Int32 are not
@@ -376,4 +717,256 @@
long r = v / -100L;
return r;
}
+
+ private static long $noinline$Negate(long v) {
+ return -v;
+ }
+
+ private static long $noinline$Decrement(long v) {
+ return v - 1;
+ }
+
+ private static long $noinline$Increment(long v) {
+ return v + 1;
+ }
+
+ // A test case to check that a correcting 'add' is not generated for a non-negative
+ // dividend and a positive divisor.
+ //
+ /// CHECK-START-ARM64: long DivTest.$noinline$UnsignedLongDiv01(long) disassembly (after)
+ /// CHECK: smulh x{{\d+}}, x{{\d+}}, x{{\d+}}
+ /// CHECK-NOT: add x{{\d+}}, x{{\d+}}, x{{\d+}}, lsr #63
+ private static long $noinline$UnsignedLongDiv01(long v) {
+ long c = 0;
+ if (v > 0) {
+ c = v / 6;
+ } else {
+ c = $noinline$Negate(v); // This is to prevent from using Select.
+ }
+ return c;
+ }
+
+ // A test case to check that a correcting 'add' is not generated for a non-negative
+ // dividend and a positive divisor.
+ //
+ /// CHECK-START-ARM64: long DivTest.$noinline$UnsignedLongDiv02(long) disassembly (after)
+ /// CHECK: smulh x{{\d+}}, x{{\d+}}, x{{\d+}}
+ /// CHECK-NOT: add x{{\d+}}, x{{\d+}}, x{{\d+}}, lsr #63
+ private static long $noinline$UnsignedLongDiv02(long v) {
+ long c = 0;
+ if (0 < v) {
+ c = v / 6;
+ } else {
+ c = $noinline$Negate(v); // This is to prevent from using Select.
+ }
+ return c;
+ }
+
+ // A test case to check that a correcting 'add' is not generated for a non-negative
+ // dividend and a positive divisor.
+ //
+ /// CHECK-START-ARM64: long DivTest.$noinline$UnsignedLongDiv03(long) disassembly (after)
+ /// CHECK: smulh x{{\d+}}, x{{\d+}}, x{{\d+}}
+ /// CHECK-NOT: add x{{\d+}}, x{{\d+}}, x{{\d+}}, lsr #63
+ private static long $noinline$UnsignedLongDiv03(long v) {
+ long c = 0;
+ if (v >= 0) {
+ c = v / 6;
+ } else {
+ c = $noinline$Negate(v); // This is to prevent from using Select.
+ }
+ return c;
+ }
+
+ // A test case to check that a correcting 'add' is not generated for a non-negative
+ // dividend and a positive divisor.
+ //
+ /// CHECK-START-ARM64: long DivTest.$noinline$UnsignedLongDiv04(long) disassembly (after)
+ /// CHECK: smulh x{{\d+}}, x{{\d+}}, x{{\d+}}
+ /// CHECK-NOT: add x{{\d+}}, x{{\d+}}, x{{\d+}}, lsr #63
+ private static long $noinline$UnsignedLongDiv04(long v) {
+ long c = 0;
+ if (0 <= v) {
+ c = v / 6;
+ } else {
+ c = $noinline$Negate(v); // This is to prevent from using Select.
+ }
+ return c;
+ }
+
+ // A test case to check that a correcting 'add' is not generated for a non-negative
+ // dividend and a positive divisor.
+ //
+ /// CHECK-START-ARM64: java.lang.String DivTest.$noinline$UnsignedLongDiv05(long) disassembly (after)
+ /// CHECK: smulh x{{\d+}}, x{{\d+}}, x{{\d+}}
+ /// CHECK-NEXT: lsr x{{\d+}}, x{{\d+}}, #2
+ /// CHECK-NOT: add x{{\d+}}, x{{\d+}}, x{{\d+}}, lsr #63
+ private static String $noinline$UnsignedLongDiv05(long v) {
+ String r = "";
+ while (v > 0) {
+ long d = v % 10;
+ r += (char)(d + '0');
+ v /= 10;
+ }
+ 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-ARM64: void DivTest.$noinline$UnsignedLongDiv05(java.lang.StringBuilder, long, long) disassembly (after)
+ /// CHECK: smulh x{{\d+}}, x{{\d+}}, x{{\d+}}
+ /// CHECK-NEXT: lsr x{{\d+}}, x{{\d+}}, #2
+ /// CHECK-NOT: add x{{\d+}}, x{{\d+}}, x{{\d+}}, lsr #63
+ private static void $noinline$UnsignedLongDiv05(java.lang.StringBuilder sb, long w, long d) {
+ while (w > 0) {
+ sb.append((char)(d/w + '0'));
+ d = d % w;
+ w /= 10;
+ }
+ }
+
+ // A test case to check that a correcting 'add' is not generated for a non-negative
+ // dividend and a positive divisor.
+ //
+ /// CHECK-START-ARM64: long DivTest.$noinline$UnsignedLongDiv06(long) disassembly (after)
+ /// CHECK: smulh x{{\d+}}, x{{\d+}}, x{{\d+}}
+ /// CHECK-NOT: add x{{\d+}}, x{{\d+}}, x{{\d+}}, lsr #63
+ private static long $noinline$UnsignedLongDiv06(long v) {
+ long c = 0;
+ for(; v > 100; ++c) {
+ v /= 10;
+ }
+ return c;
+ }
+
+ // A test case to check that a correcting 'add' is not generated for a non-negative
+ // dividend and a positive divisor.
+ //
+ /// CHECK-START-ARM64: long DivTest.$noinline$UnsignedLongDiv07(long) disassembly (after)
+ /// CHECK: smulh x{{\d+}}, x{{\d+}}, x{{\d+}}
+ /// CHECK-NOT: add x{{\d+}}, x{{\d+}}, x{{\d+}}, lsr #63
+ private static long $noinline$UnsignedLongDiv07(long v) {
+ while (v > 0 && (v % 10) == 0) {
+ v /= 10;
+ }
+ return v;
+ }
+
+ // A test case to check that a correcting 'add' is not generated for a non-negative
+ // dividend and a positive divisor.
+ //
+ /// CHECK-START-ARM64: long DivTest.$noinline$UnsignedLongDiv08(long) disassembly (after)
+ /// CHECK: smulh x{{\d+}}, x{{\d+}}, x{{\d+}}
+ /// CHECK-NOT: add x{{\d+}}, x{{\d+}}, x{{\d+}}, lsr #63
+ private static long $noinline$UnsignedLongDiv08(long v) {
+ if (v < 10) {
+ v = $noinline$Negate(v); // This is to prevent from using Select.
+ } else {
+ v = (v % 10) + (v / 10);
+ }
+ return v;
+ }
+
+ // A test case to check that a correcting 'add' is generated for a negative
+ // dividend and a positive divisor.
+ //
+ /// CHECK-START-ARM64: long DivTest.$noinline$SignedLongDiv01(long) disassembly (after)
+ /// CHECK: smulh x{{\d+}}, x{{\d+}}, x{{\d+}}
+ /// CHECK-NEXT: add x{{\d+}}, x{{\d+}}, x{{\d+}}, lsr #63
+ private static long $noinline$SignedLongDiv01(long v) {
+ long c = 0;
+ if (v < 0) {
+ c = v / 6;
+ } else {
+ c = $noinline$Decrement(v); // This is to prevent from using Select.
+ }
+ return c;
+ }
+
+ // A test case to check that a correcting 'add' is generated for a negative
+ // dividend and a positive divisor.
+ //
+ /// CHECK-START-ARM64: long DivTest.$noinline$SignedLongDiv02(long) disassembly (after)
+ /// CHECK: smulh x{{\d+}}, x{{\d+}}, x{{\d+}}
+ /// CHECK-NEXT: add x{{\d+}}, x{{\d+}}, x{{\d+}}, lsr #63
+ private static long $noinline$SignedLongDiv02(long v) {
+ long c = 0;
+ if (v <= 0) {
+ c = v / 6;
+ } else {
+ c = $noinline$Decrement(v); // This is to prevent from using Select.
+ }
+ return c;
+ }
+
+ // A test case to check that a correcting 'add' is generated for signed division.
+ //
+ /// CHECK-START-ARM64: long DivTest.$noinline$SignedLongDiv03(long) disassembly (after)
+ /// CHECK: smulh x{{\d+}}, x{{\d+}}, x{{\d+}}
+ /// CHECK-NEXT: add x{{\d+}}, x{{\d+}}, x{{\d+}}, lsr #63
+ private static long $noinline$SignedLongDiv03(long v) {
+ boolean positive = (v > 0);
+ long c = v / 6;
+ if (!positive) {
+ c = $noinline$Negate(c); // This is to prevent from using Select.
+ }
+ return c;
+ }
+
+ // A test case to check that a correcting 'add' is generated for signed division.
+ //
+ /// CHECK-START-ARM64: long DivTest.$noinline$SignedLongDiv04(long, boolean) disassembly (after)
+ /// CHECK: smulh x{{\d+}}, x{{\d+}}, x{{\d+}}
+ /// CHECK-NEXT: add x{{\d+}}, x{{\d+}}, x{{\d+}}, lsr #63
+ private static long $noinline$SignedLongDiv04(long v, boolean apply_div) {
+ long c = 0;
+ boolean positive = (v > 0);
+ if (apply_div) {
+ c = v / 6;
+ } else {
+ c = $noinline$Decrement(v); // This is to prevent from using Select.
+ }
+ if (!positive) {
+ c = $noinline$Negate(c); // This is to prevent from using Select.
+ }
+ return c;
+ }
+
+ // A test case to check that a correcting 'add' is generated for signed division.
+ //
+ /// CHECK-START-ARM64: long DivTest.$noinline$SignedLongDiv05(long, long, long) disassembly (after)
+ /// CHECK: smulh x{{\d+}}, x{{\d+}}, x{{\d+}}
+ /// CHECK-NEXT: add x{{\d+}}, x{{\d+}}, x{{\d+}}, lsr #63
+ private static long $noinline$SignedLongDiv05(long v, long a, long b) {
+ long c = 0;
+
+ if (v < a)
+ c = $noinline$Increment(c); // This is to prevent from using Select.
+
+ if (b < a)
+ c = $noinline$Increment(c); // This is to prevent from using Select.
+
+ if (v > b) {
+ c = v / 6;
+ } else {
+ c = $noinline$Increment(c); // This is to prevent from using Select.
+ }
+
+ return c;
+ }
+
+ // A test case to check that a correcting 'add' is generated for signed division.
+ //
+ /// CHECK-START-ARM64: long DivTest.$noinline$SignedLongDiv06(long) disassembly (after)
+ /// CHECK: smulh x{{\d+}}, x{{\d+}}, x{{\d+}}
+ /// CHECK-NEXT: add x{{\d+}}, x{{\d+}}, x{{\d+}}, lsr #63
+ private static long $noinline$SignedLongDiv06(long v) {
+ long c = v / 6;
+
+ if (v > 0) {
+ c = $noinline$Negate(c); // This is to prevent from using Select.
+ }
+
+ return c;
+ }
}
diff --git a/test/411-checker-hdiv-hrem-const/src/RemTest.java b/test/411-checker-hdiv-hrem-const/src/RemTest.java
index 8dbd401..f7117ec 100644
--- a/test/411-checker-hdiv-hrem-const/src/RemTest.java
+++ b/test/411-checker-hdiv-hrem-const/src/RemTest.java
@@ -95,6 +95,20 @@
expectEquals(0, $noinline$IntRemByMinus6(-6));
expectEquals(1, $noinline$IntRemByMinus6(19));
expectEquals(-1, $noinline$IntRemByMinus6(-19));
+
+ expectEquals(1, $noinline$UnsignedIntRem01(13));
+ expectEquals(1, $noinline$UnsignedIntRem02(13));
+ expectEquals(1, $noinline$UnsignedIntRem03(13));
+ expectEquals(1, $noinline$UnsignedIntRem04(13));
+ expectEquals(1, $noinline$UnsignedIntRem05(101));
+ expectEquals(11, $noinline$UnsignedIntRem06(101));
+
+ expectEquals(-1, $noinline$SignedIntRem01(-13));
+ expectEquals(-1, $noinline$SignedIntRem02(-13));
+ expectEquals(1, $noinline$SignedIntRem03(-13));
+ expectEquals(1, $noinline$SignedIntRem04(-13, true));
+ expectEquals(0, $noinline$SignedIntRem05(-12, 0,-13));
+ expectEquals(-1, $noinline$SignedIntRem06(-13));
}
// A test case to check that 'lsr' and 'asr' are combined into one 'asr'.
@@ -251,6 +265,287 @@
return r;
}
+ private static int $noinline$Negate(int v) {
+ return -v;
+ }
+
+ private static int $noinline$Decrement(int v) {
+ return v - 1;
+ }
+
+ private static int $noinline$Increment(int v) {
+ return v + 1;
+ }
+
+ // 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$UnsignedIntRem01(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$UnsignedIntRem01(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$UnsignedIntRem01(int v) {
+ int c = 0;
+ if (v > 0) {
+ c = v % 6;
+ } else {
+ c = $noinline$Negate(v); // This is to prevent from using Select.
+ }
+ return c;
+ }
+
+ // 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$UnsignedIntRem02(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$UnsignedIntRem02(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$UnsignedIntRem02(int v) {
+ int c = 0;
+ if (0 < v) {
+ c = v % 6;
+ } else {
+ c = $noinline$Negate(v); // This is to prevent from using Select.
+ }
+ return c;
+ }
+
+ // 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$UnsignedIntRem03(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$UnsignedIntRem03(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$UnsignedIntRem03(int v) {
+ int c = 0;
+ if (v >= 0) {
+ c = v % 6;
+ } else {
+ c = $noinline$Negate(v); // This is to prevent from using Select.
+ }
+ return c;
+ }
+
+ // 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$UnsignedIntRem04(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$UnsignedIntRem04(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$UnsignedIntRem04(int v) {
+ int c = 0;
+ if (0 <= v) {
+ c = v % 6;
+ } else {
+ c = $noinline$Negate(v); // This is to prevent from using Select.
+ }
+ return c;
+ }
+
+ // 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$UnsignedIntRem05(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+}}, #10
+ /// CHECK-NEXT: mls r{{\d+}}, r{{\d+}}, r{{\d+}}, r{{\d+}}
+ //
+ /// CHECK-START-ARM64: int RemTest.$noinline$UnsignedIntRem05(int) disassembly (after)
+ /// CHECK: lsr x{{\d+}}, x{{\d+}}, #34
+ /// CHECK-NEXT: mov w{{\d+}}, #0xa
+ /// CHECK-NEXT: msub w{{\d+}}, w{{\d+}}, w{{\d+}}, w{{\d+}}
+ private static int $noinline$UnsignedIntRem05(int v) {
+ int c = 0;
+ for(; v > 100; ++c) {
+ v %= 10;
+ }
+ return c;
+ }
+
+ // 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$UnsignedIntRem06(int) disassembly (after)
+ /// CHECK: smull r{{\d+}}, r{{\d+}}, r{{\d+}}, r{{\d+}}
+ /// CHECK-NEXT: lsr{{s?}} r{{\d+}}, r{{\d+}}, #2
+ /// CHECK: mls r{{\d+}}, r{{\d+}}, r{{\d+}}, r{{\d+}}
+ //
+ /// CHECK-START-ARM64: int RemTest.$noinline$UnsignedIntRem06(int) disassembly (after)
+ /// CHECK: smull x{{\d+}}, w{{\d+}}, w{{\d+}}
+ /// CHECK-NEXT: lsr x{{\d+}}, x{{\d+}}, #34
+ /// CHECK: msub w{{\d+}}, w{{\d+}}, w{{\d+}}, w{{\d+}}
+ private static int $noinline$UnsignedIntRem06(int v) {
+ if (v < 10) {
+ v = $noinline$Negate(v); // This is to prevent from using Select.
+ } else {
+ v = (v % 10) + (v / 10);
+ }
+ return v;
+ }
+
+ // A test case to check that a correcting 'add' is generated for a negative
+ // dividend and a positive divisor.
+ //
+ /// CHECK-START-ARM: int RemTest.$noinline$SignedIntRem01(int) disassembly (after)
+ /// CHECK: smull r{{\d+}}, r{{\d+}}, r{{\d+}}, r{{\d+}}
+ /// CHECK-NEXT: sub r{{\d+}}, r{{\d+}}, asr #31
+ /// CHECK-NEXT: mov{{s?}} r{{\d+}}, #6
+ /// CHECK-NEXT: mls r{{\d+}}, r{{\d+}}, r{{\d+}}, r{{\d+}}
+ //
+ /// CHECK-START-ARM64: int RemTest.$noinline$SignedIntRem01(int) disassembly (after)
+ /// CHECK: asr x{{\d+}}, x{{\d+}}, #32
+ /// CHECK-NEXT: add w{{\d+}}, w{{\d+}}, w{{\d+}}, lsr #31
+ private static int $noinline$SignedIntRem01(int v) {
+ int c = 0;
+ if (v < 0) {
+ c = v % 6;
+ } else {
+ c = $noinline$Decrement(v); // This is to prevent from using Select.
+ }
+ return c;
+ }
+
+ // A test case to check that a correcting 'add' is generated for a negative
+ // dividend and a positive divisor.
+ //
+ /// CHECK-START-ARM: int RemTest.$noinline$SignedIntRem02(int) disassembly (after)
+ /// CHECK: smull r{{\d+}}, r{{\d+}}, r{{\d+}}, r{{\d+}}
+ /// CHECK-NEXT: sub r{{\d+}}, r{{\d+}}, asr #31
+ /// CHECK-NEXT: mov{{s?}} r{{\d+}}, #6
+ /// CHECK-NEXT: mls r{{\d+}}, r{{\d+}}, r{{\d+}}, r{{\d+}}
+ //
+ /// CHECK-START-ARM64: int RemTest.$noinline$SignedIntRem02(int) disassembly (after)
+ /// CHECK: asr x{{\d+}}, x{{\d+}}, #32
+ /// CHECK-NEXT: add w{{\d+}}, w{{\d+}}, w{{\d+}}, lsr #31
+ private static int $noinline$SignedIntRem02(int v) {
+ int c = 0;
+ if (v <= 0) {
+ c = v % 6;
+ } else {
+ c = $noinline$Decrement(v); // This is to prevent from using Select.
+ }
+ return c;
+ }
+
+ // A test case to check that a correcting 'add' is generated for signed division.
+ //
+ /// CHECK-START-ARM: int RemTest.$noinline$SignedIntRem03(int) disassembly (after)
+ /// CHECK: smull r{{\d+}}, r{{\d+}}, r{{\d+}}, r{{\d+}}
+ /// CHECK-NEXT: sub r{{\d+}}, r{{\d+}}, asr #31
+ /// CHECK-NEXT: mov{{s?}} r{{\d+}}, #6
+ /// CHECK-NEXT: mls r{{\d+}}, r{{\d+}}, r{{\d+}}, r{{\d+}}
+ //
+ /// CHECK-START-ARM64: int RemTest.$noinline$SignedIntRem03(int) disassembly (after)
+ /// CHECK: asr x{{\d+}}, x{{\d+}}, #32
+ /// CHECK-NEXT: add w{{\d+}}, w{{\d+}}, w{{\d+}}, lsr #31
+ private static int $noinline$SignedIntRem03(int v) {
+ boolean positive = (v > 0);
+ int c = v % 6;
+ if (!positive) {
+ c = $noinline$Negate(c); // This is to prevent from using Select.
+ }
+ return c;
+ }
+
+ // A test case to check that a correcting 'add' is generated for signed division.
+ //
+ /// CHECK-START-ARM: int RemTest.$noinline$SignedIntRem04(int, boolean) disassembly (after)
+ /// CHECK: smull r{{\d+}}, r{{\d+}}, r{{\d+}}, r{{\d+}}
+ /// CHECK-NEXT: sub r{{\d+}}, r{{\d+}}, asr #31
+ /// CHECK-NEXT: mov{{s?}} r{{\d+}}, #6
+ /// CHECK-NEXT: mls r{{\d+}}, r{{\d+}}, r{{\d+}}, r{{\d+}}
+ //
+ /// CHECK-START-ARM64: int RemTest.$noinline$SignedIntRem04(int, boolean) disassembly (after)
+ /// CHECK: asr x{{\d+}}, x{{\d+}}, #32
+ /// CHECK-NEXT: add w{{\d+}}, w{{\d+}}, w{{\d+}}, lsr #31
+ private static int $noinline$SignedIntRem04(int v, boolean apply_rem) {
+ int c = 0;
+ boolean positive = (v > 0);
+ if (apply_rem) {
+ c = v % 6;
+ } else {
+ c = $noinline$Decrement(v); // This is to prevent from using Select.
+ }
+ if (!positive) {
+ c = $noinline$Negate(c); // This is to prevent from using Select.
+ }
+ return c;
+ }
+
+ // A test case to check that a correcting 'add' is generated for signed division.
+ //
+ /// CHECK-START-ARM: int RemTest.$noinline$SignedIntRem05(int, int, int) disassembly (after)
+ /// CHECK: smull r{{\d+}}, r{{\d+}}, r{{\d+}}, r{{\d+}}
+ /// CHECK-NEXT: sub r{{\d+}}, r{{\d+}}, asr #31
+ /// CHECK-NEXT: mov{{s?}} r{{\d+}}, #6
+ /// CHECK-NEXT: mls r{{\d+}}, r{{\d+}}, r{{\d+}}, r{{\d+}}
+ //
+ /// CHECK-START-ARM64: int RemTest.$noinline$SignedIntRem05(int, int, int) disassembly (after)
+ /// CHECK: asr x{{\d+}}, x{{\d+}}, #32
+ /// CHECK-NEXT: add w{{\d+}}, w{{\d+}}, w{{\d+}}, lsr #31
+ private static int $noinline$SignedIntRem05(int v, int a, int b) {
+ int c = 0;
+
+ if (v < a)
+ c = $noinline$Increment(c); // This is to prevent from using Select.
+
+ if (b < a)
+ c = $noinline$Increment(c); // This is to prevent from using Select.
+
+ if (v > b) {
+ c = v % 6;
+ } else {
+ c = $noinline$Increment(c); // This is to prevent from using Select.
+ }
+
+ return c;
+ }
+
+ // A test case to check that a correcting 'add' is generated for signed division.
+ //
+ /// CHECK-START-ARM: int RemTest.$noinline$SignedIntRem06(int) disassembly (after)
+ /// CHECK: smull r{{\d+}}, r{{\d+}}, r{{\d+}}, r{{\d+}}
+ /// CHECK-NEXT: sub r{{\d+}}, r{{\d+}}, asr #31
+ /// CHECK-NEXT: mov{{s?}} r{{\d+}}, #6
+ /// CHECK-NEXT: mls r{{\d+}}, r{{\d+}}, r{{\d+}}, r{{\d+}}
+ //
+ /// CHECK-START-ARM64: int RemTest.$noinline$SignedIntRem06(int) disassembly (after)
+ /// CHECK: asr x{{\d+}}, x{{\d+}}, #32
+ /// CHECK-NEXT: add w{{\d+}}, w{{\d+}}, w{{\d+}}, lsr #31
+ private static int $noinline$SignedIntRem06(int v) {
+ int c = v % 6;
+
+ if (v > 0) {
+ c = $noinline$Negate(c); // This is to prevent from using Select.
+ }
+
+ return c;
+ }
+
private static void remLong() {
expectEquals(0L, $noinline$LongRemBy18(0L));
expectEquals(1L, $noinline$LongRemBy18(1L));
@@ -315,6 +610,20 @@
expectEquals(0L, $noinline$LongRemByMinus100(-100L));
expectEquals(1L, $noinline$LongRemByMinus100(101L));
expectEquals(-1L, $noinline$LongRemByMinus100(-101L));
+
+ expectEquals(1L, $noinline$UnsignedLongRem01(13L));
+ expectEquals(1L, $noinline$UnsignedLongRem02(13L));
+ expectEquals(1L, $noinline$UnsignedLongRem03(13L));
+ expectEquals(1L, $noinline$UnsignedLongRem04(13L));
+ expectEquals(1L, $noinline$UnsignedLongRem05(101L));
+ expectEquals(11L, $noinline$UnsignedLongRem06(101L));
+
+ expectEquals(-1L, $noinline$SignedLongRem01(-13L));
+ expectEquals(-1L, $noinline$SignedLongRem02(-13L));
+ expectEquals(1L, $noinline$SignedLongRem03(-13L));
+ expectEquals(1L, $noinline$SignedLongRem04(-13L, true));
+ expectEquals(0L, $noinline$SignedLongRem05(-12L, 0L,-13L));
+ expectEquals(-1L, $noinline$SignedLongRem06(-13L));
}
// Test cases for Int64 HDiv/HRem to check that optimizations implemented for Int32 are not
@@ -409,4 +718,231 @@
long r = v % -100L;
return r;
}
+
+ private static long $noinline$Negate(long v) {
+ return -v;
+ }
+
+ private static long $noinline$Decrement(long v) {
+ return v - 1;
+ }
+
+ private static long $noinline$Increment(long v) {
+ return v + 1;
+ }
+
+ // A test case to check that a correcting 'add' is not generated for a non-negative
+ // dividend and a positive divisor.
+ //
+ /// CHECK-START-ARM64: long RemTest.$noinline$UnsignedLongRem01(long) disassembly (after)
+ /// CHECK: smulh x{{\d+}}, x{{\d+}}, x{{\d+}}
+ /// CHECK-NEXT: mov x{{\d+}}, #0x6
+ /// CHECK-NEXT: msub x{{\d+}}, x{{\d+}}, x{{\d+}}, x{{\d+}}
+ private static long $noinline$UnsignedLongRem01(long v) {
+ long c = 0;
+ if (v > 0) {
+ c = v % 6;
+ } else {
+ c = $noinline$Negate(v); // This is to prevent from using Select.
+ }
+ return c;
+ }
+
+ // A test case to check that a correcting 'add' is not generated for a non-negative
+ // dividend and a positive divisor.
+ //
+ /// CHECK-START-ARM64: long RemTest.$noinline$UnsignedLongRem02(long) disassembly (after)
+ /// CHECK: smulh x{{\d+}}, x{{\d+}}, x{{\d+}}
+ /// CHECK-NEXT: mov x{{\d+}}, #0x6
+ /// CHECK-NEXT: msub x{{\d+}}, x{{\d+}}, x{{\d+}}, x{{\d+}}
+ private static long $noinline$UnsignedLongRem02(long v) {
+ long c = 0;
+ if (0 < v) {
+ c = v % 6;
+ } else {
+ c = $noinline$Negate(v); // This is to prevent from using Select.
+ }
+ return c;
+ }
+
+ // A test case to check that a correcting 'add' is not generated for a non-negative
+ // dividend and a positive divisor.
+ //
+ /// CHECK-START-ARM64: long RemTest.$noinline$UnsignedLongRem03(long) disassembly (after)
+ /// CHECK: smulh x{{\d+}}, x{{\d+}}, x{{\d+}}
+ /// CHECK-NEXT: mov x{{\d+}}, #0x6
+ /// CHECK-NEXT: msub x{{\d+}}, x{{\d+}}, x{{\d+}}, x{{\d+}}
+ private static long $noinline$UnsignedLongRem03(long v) {
+ long c = 0;
+ if (v >= 0) {
+ c = v % 6;
+ } else {
+ c = $noinline$Negate(v); // This is to prevent from using Select.
+ }
+ return c;
+ }
+
+ // A test case to check that a correcting 'add' is not generated for a non-negative
+ // dividend and a positive divisor.
+ //
+ /// CHECK-START-ARM64: long RemTest.$noinline$UnsignedLongRem04(long) disassembly (after)
+ /// CHECK: smulh x{{\d+}}, x{{\d+}}, x{{\d+}}
+ /// CHECK-NEXT: mov x{{\d+}}, #0x6
+ /// CHECK-NEXT: msub x{{\d+}}, x{{\d+}}, x{{\d+}}, x{{\d+}}
+ private static long $noinline$UnsignedLongRem04(long v) {
+ long c = 0;
+ if (0 <= v) {
+ c = v % 6;
+ } else {
+ c = $noinline$Negate(v); // This is to prevent from using Select.
+ }
+ return c;
+ }
+
+ // A test case to check that a correcting 'add' is not generated for a non-negative
+ // dividend and a positive divisor.
+ //
+ /// CHECK-START-ARM64: long RemTest.$noinline$UnsignedLongRem05(long) disassembly (after)
+ /// CHECK: smulh x{{\d+}}, x{{\d+}}, x{{\d+}}
+ /// CHECK-NEXT: lsr x{{\d+}}, x{{\d+}}, #2
+ /// CHECK-NEXT: mov x{{\d+}}, #0xa
+ /// CHECK-NEXT: msub x{{\d+}}, x{{\d+}}, x{{\d+}}, x{{\d+}}
+ private static long $noinline$UnsignedLongRem05(long v) {
+ long c = 0;
+ for(; v > 100; ++c) {
+ v %= 10;
+ }
+ return c;
+ }
+
+ // A test case to check that a correcting 'add' is not generated for a non-negative
+ // dividend and a positive divisor.
+ //
+ /// CHECK-START-ARM64: long RemTest.$noinline$UnsignedLongRem06(long) disassembly (after)
+ /// CHECK: smulh x{{\d+}}, x{{\d+}}, x{{\d+}}
+ /// CHECK-NEXT: lsr x{{\d+}}, x{{\d+}}, #2
+ /// CHECK: msub x{{\d+}}, x{{\d+}}, x{{\d+}}, x{{\d+}}
+ private static long $noinline$UnsignedLongRem06(long v) {
+ if (v < 10) {
+ v = $noinline$Negate(v); // This is to prevent from using Select.
+ } else {
+ v = (v % 10) + (v / 10);
+ }
+ return v;
+ }
+
+ // A test case to check that a correcting 'add' is generated for a negative
+ // dividend and a positive divisor.
+ //
+ /// CHECK-START-ARM64: long RemTest.$noinline$SignedLongRem01(long) disassembly (after)
+ /// CHECK: smulh x{{\d+}}, x{{\d+}}, x{{\d+}}
+ /// CHECK-NEXT: add x{{\d+}}, x{{\d+}}, x{{\d+}}, lsr #63
+ /// CHECK-NEXT: mov x{{\d+}}, #0x6
+ /// CHECK-NEXT: msub x{{\d+}}, x{{\d+}}, x{{\d+}}, x{{\d+}}
+ private static long $noinline$SignedLongRem01(long v) {
+ long c = 0;
+ if (v < 0) {
+ c = v % 6;
+ } else {
+ c = $noinline$Decrement(v); // This is to prevent from using Select.
+ }
+ return c;
+ }
+
+ // A test case to check that a correcting 'add' is generated for a negative
+ // dividend and a positive divisor.
+ //
+ /// CHECK-START-ARM64: long RemTest.$noinline$SignedLongRem02(long) disassembly (after)
+ /// CHECK: smulh x{{\d+}}, x{{\d+}}, x{{\d+}}
+ /// CHECK-NEXT: add x{{\d+}}, x{{\d+}}, x{{\d+}}, lsr #63
+ /// CHECK-NEXT: mov x{{\d+}}, #0x6
+ /// CHECK-NEXT: msub x{{\d+}}, x{{\d+}}, x{{\d+}}, x{{\d+}}
+ private static long $noinline$SignedLongRem02(long v) {
+ long c = 0;
+ if (v <= 0) {
+ c = v % 6;
+ } else {
+ c = $noinline$Decrement(v); // This is to prevent from using Select.
+ }
+ return c;
+ }
+
+ // A test case to check that a correcting 'add' is generated for signed division.
+ //
+ /// CHECK-START-ARM64: long RemTest.$noinline$SignedLongRem03(long) disassembly (after)
+ /// CHECK: smulh x{{\d+}}, x{{\d+}}, x{{\d+}}
+ /// CHECK-NEXT: add x{{\d+}}, x{{\d+}}, x{{\d+}}, lsr #63
+ /// CHECK-NEXT: mov x{{\d+}}, #0x6
+ /// CHECK-NEXT: msub x{{\d+}}, x{{\d+}}, x{{\d+}}, x{{\d+}}
+ private static long $noinline$SignedLongRem03(long v) {
+ boolean positive = (v > 0);
+ long c = v % 6;
+ if (!positive) {
+ c = $noinline$Negate(c); // This is to prevent from using Select.
+ }
+ return c;
+ }
+
+ // A test case to check that a correcting 'add' is generated for signed division.
+ //
+ /// CHECK-START-ARM64: long RemTest.$noinline$SignedLongRem04(long, boolean) disassembly (after)
+ /// CHECK: smulh x{{\d+}}, x{{\d+}}, x{{\d+}}
+ /// CHECK-NEXT: add x{{\d+}}, x{{\d+}}, x{{\d+}}, lsr #63
+ /// CHECK-NEXT: mov x{{\d+}}, #0x6
+ /// CHECK-NEXT: msub x{{\d+}}, x{{\d+}}, x{{\d+}}, x{{\d+}}
+ private static long $noinline$SignedLongRem04(long v, boolean apply_rem) {
+ long c = 0;
+ boolean positive = (v > 0);
+ if (apply_rem) {
+ c = v % 6;
+ } else {
+ c = $noinline$Decrement(v); // This is to prevent from using Select.
+ }
+ if (!positive) {
+ c = $noinline$Negate(c); // This is to prevent from using Select.
+ }
+ return c;
+ }
+
+ // A test case to check that a correcting 'add' is generated for signed division.
+ //
+ /// CHECK-START-ARM64: long RemTest.$noinline$SignedLongRem05(long, long, long) disassembly (after)
+ /// CHECK: smulh x{{\d+}}, x{{\d+}}, x{{\d+}}
+ /// CHECK-NEXT: add x{{\d+}}, x{{\d+}}, x{{\d+}}, lsr #63
+ /// CHECK-NEXT: mov x{{\d+}}, #0x6
+ /// CHECK-NEXT: msub x{{\d+}}, x{{\d+}}, x{{\d+}}, x{{\d+}}
+ private static long $noinline$SignedLongRem05(long v, long a, long b) {
+ long c = 0;
+
+ if (v < a)
+ c = $noinline$Increment(c); // This is to prevent from using Select.
+
+ if (b < a)
+ c = $noinline$Increment(c); // This is to prevent from using Select.
+
+ if (v > b) {
+ c = v % 6;
+ } else {
+ c = $noinline$Increment(c); // This is to prevent from using Select.
+ }
+
+ return c;
+ }
+
+ // A test case to check that a correcting 'add' is generated for signed division.
+ //
+ /// CHECK-START-ARM64: long RemTest.$noinline$SignedLongRem06(long) disassembly (after)
+ /// CHECK: smulh x{{\d+}}, x{{\d+}}, x{{\d+}}
+ /// CHECK-NEXT: add x{{\d+}}, x{{\d+}}, x{{\d+}}, lsr #63
+ /// CHECK-NEXT: mov x{{\d+}}, #0x6
+ /// CHECK-NEXT: msub x{{\d+}}, x{{\d+}}, x{{\d+}}, x{{\d+}}
+ private static long $noinline$SignedLongRem06(long v) {
+ long c = v % 6;
+
+ if (v > 0) {
+ c = $noinline$Negate(c); // This is to prevent from using Select.
+ }
+
+ return c;
+ }
}
diff --git a/test/411-checker-hdiv-hrem-pow2/src/DivTest.java b/test/411-checker-hdiv-hrem-pow2/src/DivTest.java
index 28dfaf1..0d09f3f 100644
--- a/test/411-checker-hdiv-hrem-pow2/src/DivTest.java
+++ b/test/411-checker-hdiv-hrem-pow2/src/DivTest.java
@@ -383,6 +383,21 @@
return r;
}
+ /// CHECK-START-ARM: java.lang.Integer DivTest.unsignedDiv01(int) disassembly (after)
+ /// CHECK: Div
+ /// CHECK-NEXT: asr{{s?}} r{{\d+}}, #1
+ //
+ /// CHECK-START-ARM64: java.lang.Integer DivTest.unsignedDiv01(int) disassembly (after)
+ /// CHECK: Div
+ /// CHECK-NEXT: asr w{{\d+}}, w{{\d+}}, #1
+ private static Integer unsignedDiv01(int v) {
+ int l = 0;
+ for (int m = v - 1; m >= 0; m = m / 2 - 1) {
+ ++l;
+ }
+ return l;
+ }
+
private static void divLong() {
expectEquals(0L, $noinline$LongDivBy2(0L));
expectEquals(0L, $noinline$LongDivBy2(1L));