Revision: 15181
Author: [email protected]
Date: Mon Jun 17 08:06:41 2013
Log: MIPS: Optimise Math.floor(x/y) to use integer division for MIPS.
Use div instruction if some divisors do not have magic number.
Based on commit r11427 (318a9598).
This commit also ports commit r15161 (554d45c1).
BUG=
Review URL: https://codereview.chromium.org/16951016
Patch from Dusan Milosavljevic <[email protected]>.
http://code.google.com/p/v8/source/detail?r=15181
Modified:
/branches/bleeding_edge/src/hydrogen-instructions.cc
/branches/bleeding_edge/src/mips/lithium-codegen-mips.cc
/branches/bleeding_edge/src/mips/lithium-codegen-mips.h
/branches/bleeding_edge/src/mips/lithium-mips.cc
/branches/bleeding_edge/src/mips/lithium-mips.h
/branches/bleeding_edge/test/mjsunit/mjsunit.status
=======================================
--- /branches/bleeding_edge/src/hydrogen-instructions.cc Fri Jun 14
11:15:49 2013
+++ /branches/bleeding_edge/src/hydrogen-instructions.cc Mon Jun 17
08:06:41 2013
@@ -1533,8 +1533,6 @@
// with its input.
if (val->representation().IsInteger32()) return val;
-#if defined(V8_TARGET_ARCH_ARM) || defined(V8_TARGET_ARCH_IA32) || \
- defined(V8_TARGET_ARCH_X64)
if (val->IsDiv() && (val->UseCount() == 1)) {
HDiv* hdiv = HDiv::cast(val);
HValue* left = hdiv->left();
@@ -1585,7 +1583,6 @@
// Return NULL to remove this instruction from the graph.
return NULL;
}
-#endif // V8_TARGET_ARCH_ARM
}
return this;
}
=======================================
--- /branches/bleeding_edge/src/mips/lithium-codegen-mips.cc Fri Jun 14
10:00:24 2013
+++ /branches/bleeding_edge/src/mips/lithium-codegen-mips.cc Mon Jun 17
08:06:41 2013
@@ -1174,6 +1174,109 @@
__ bind(&done);
}
}
+
+
+void LCodeGen::EmitSignedIntegerDivisionByConstant(
+ Register result,
+ Register dividend,
+ int32_t divisor,
+ Register remainder,
+ Register scratch,
+ LEnvironment* environment) {
+ ASSERT(!AreAliased(dividend, scratch, at, no_reg));
+ ASSERT(LChunkBuilder::HasMagicNumberForDivisor(divisor));
+
+ uint32_t divisor_abs = abs(divisor);
+
+ int32_t power_of_2_factor =
+ CompilerIntrinsics::CountTrailingZeros(divisor_abs);
+
+ switch (divisor_abs) {
+ case 0:
+ DeoptimizeIf(al, environment);
+ return;
+
+ case 1:
+ if (divisor > 0) {
+ __ Move(result, dividend);
+ } else {
+ __ SubuAndCheckForOverflow(result, zero_reg, dividend, scratch);
+ DeoptimizeIf(lt, environment, scratch, Operand(zero_reg));
+ }
+ // Compute the remainder.
+ __ Move(remainder, zero_reg);
+ return;
+
+ default:
+ if (IsPowerOf2(divisor_abs)) {
+ // Branch and condition free code for integer division by a power
+ // of two.
+ int32_t power = WhichPowerOf2(divisor_abs);
+ if (power > 1) {
+ __ sra(scratch, dividend, power - 1);
+ }
+ __ srl(scratch, scratch, 32 - power);
+ __ Addu(scratch, dividend, Operand(scratch));
+ __ sra(result, scratch, power);
+ // Negate if necessary.
+ // We don't need to check for overflow because the case '-1' is
+ // handled separately.
+ if (divisor < 0) {
+ ASSERT(divisor != -1);
+ __ Subu(result, zero_reg, Operand(result));
+ }
+ // Compute the remainder.
+ if (divisor > 0) {
+ __ sll(scratch, result, power);
+ __ Subu(remainder, dividend, Operand(scratch));
+ } else {
+ __ sll(scratch, result, power);
+ __ Addu(remainder, dividend, Operand(scratch));
+ }
+ return;
+ } else if (LChunkBuilder::HasMagicNumberForDivisor(divisor)) {
+ // Use magic numbers for a few specific divisors.
+ // Details and proofs can be found in:
+ // - Hacker's Delight, Henry S. Warren, Jr.
+ // - The PowerPC Compiler Writer's Guide
+ // and probably many others.
+ //
+ // We handle
+ // <divisor with magic numbers> * <power of 2>
+ // but not
+ // <divisor with magic numbers> * <other divisor with magic
numbers>
+ DivMagicNumbers magic_numbers =
+ DivMagicNumberFor(divisor_abs >> power_of_2_factor);
+ // Branch and condition free code for integer division by a power
+ // of two.
+ const int32_t M = magic_numbers.M;
+ const int32_t s = magic_numbers.s + power_of_2_factor;
+
+ __ li(scratch, Operand(M));
+ __ mult(dividend, scratch);
+ __ mfhi(scratch);
+ if (M < 0) {
+ __ Addu(scratch, scratch, Operand(dividend));
+ }
+ if (s > 0) {
+ __ sra(scratch, scratch, s);
+ __ mov(scratch, scratch);
+ }
+ __ srl(at, dividend, 31);
+ __ Addu(result, scratch, Operand(at));
+ if (divisor < 0) __ Subu(result, zero_reg, Operand(result));
+ // Compute the remainder.
+ __ li(scratch, Operand(divisor));
+ __ Mul(scratch, result, Operand(scratch));
+ __ Subu(remainder, dividend, Operand(scratch));
+ } else {
+ __ li(scratch, Operand(divisor));
+ __ div(dividend, scratch);
+ __ mfhi(remainder);
+ __ mflo(result);
+ }
+ }
+}
void LCodeGen::DoDivI(LDivI* instr) {
@@ -1224,6 +1327,70 @@
__ madd_d(addend, addend, multiplier, multiplicand);
}
+
+
+void LCodeGen::DoMathFloorOfDiv(LMathFloorOfDiv* instr) {
+ const Register result = ToRegister(instr->result());
+ const Register left = ToRegister(instr->left());
+ const Register remainder = ToRegister(instr->temp());
+ const Register scratch = scratch0();
+
+ if (instr->right()->IsConstantOperand()) {
+ Label done;
+ int32_t divisor = ToInteger32(LConstantOperand::cast(instr->right()));
+ if (divisor < 0) {
+ DeoptimizeIf(eq, instr->environment(), left, Operand(zero_reg));
+ }
+ EmitSignedIntegerDivisionByConstant(result,
+ left,
+ divisor,
+ remainder,
+ scratch,
+ instr->environment());
+ // We performed a truncating division. Correct the result if necessary.
+ __ Branch(&done, eq, remainder, Operand(zero_reg), USE_DELAY_SLOT);
+ __ Xor(scratch , remainder, Operand(divisor));
+ __ Branch(&done, ge, scratch, Operand(zero_reg));
+ __ Subu(result, result, Operand(1));
+ __ bind(&done);
+ } else {
+ Label done;
+ const Register right = ToRegister(instr->right());
+
+ // On MIPS div is asynchronous - it will run in the background while we
+ // check for special cases.
+ __ div(left, right);
+
+ // Check for x / 0.
+ DeoptimizeIf(eq, instr->environment(), right, Operand(zero_reg));
+
+ // Check for (0 / -x) that will produce negative zero.
+ if (instr->hydrogen()->CheckFlag(HValue::kBailoutOnMinusZero)) {
+ Label left_not_zero;
+ __ Branch(&left_not_zero, ne, left, Operand(zero_reg));
+ DeoptimizeIf(lt, instr->environment(), right, Operand(zero_reg));
+ __ bind(&left_not_zero);
+ }
+
+ // Check for (kMinInt / -1).
+ if (instr->hydrogen()->CheckFlag(HValue::kCanOverflow)) {
+ Label left_not_min_int;
+ __ Branch(&left_not_min_int, ne, left, Operand(kMinInt));
+ DeoptimizeIf(eq, instr->environment(), right, Operand(-1));
+ __ bind(&left_not_min_int);
+ }
+
+ __ mfhi(remainder);
+ __ mflo(result);
+
+ // We performed a truncating division. Correct the result if necessary.
+ __ Branch(&done, eq, remainder, Operand(zero_reg), USE_DELAY_SLOT);
+ __ Xor(scratch , remainder, Operand(right));
+ __ Branch(&done, ge, scratch, Operand(zero_reg));
+ __ Subu(result, result, Operand(1));
+ __ bind(&done);
+ }
+}
void LCodeGen::DoMulI(LMulI* instr) {
=======================================
--- /branches/bleeding_edge/src/mips/lithium-codegen-mips.h Wed Jun 12
14:46:53 2013
+++ /branches/bleeding_edge/src/mips/lithium-codegen-mips.h Mon Jun 17
08:06:41 2013
@@ -384,6 +384,17 @@
Register source,
int* offset,
AllocationSiteMode mode);
+ // Emit optimized code for integer division.
+ // Inputs are signed.
+ // All registers are clobbered.
+ // If 'remainder' is no_reg, it is not computed.
+ void EmitSignedIntegerDivisionByConstant(Register result,
+ Register dividend,
+ int32_t divisor,
+ Register remainder,
+ Register scratch,
+ LEnvironment* environment);
+
void EnsureSpaceForLazyDeopt();
void DoLoadKeyedExternalArray(LLoadKeyed* instr);
=======================================
--- /branches/bleeding_edge/src/mips/lithium-mips.cc Mon Jun 17 04:11:41
2013
+++ /branches/bleeding_edge/src/mips/lithium-mips.cc Mon Jun 17 08:06:41
2013
@@ -1369,10 +1369,57 @@
}
-LInstruction* LChunkBuilder::DoMathFloorOfDiv(HMathFloorOfDiv* instr) {
- UNIMPLEMENTED();
+bool LChunkBuilder::HasMagicNumberForDivisor(int32_t divisor) {
+ uint32_t divisor_abs = abs(divisor);
+ // Dividing by 0, 1, and powers of 2 is easy.
+ // Note that IsPowerOf2(0) returns true;
+ ASSERT(IsPowerOf2(0) == true);
+ if (IsPowerOf2(divisor_abs)) return true;
+
+ // We have magic numbers for a few specific divisors.
+ // Details and proofs can be found in:
+ // - Hacker's Delight, Henry S. Warren, Jr.
+ // - The PowerPC Compiler Writer's Guide
+ // and probably many others.
+ //
+ // We handle
+ // <divisor with magic numbers> * <power of 2>
+ // but not
+ // <divisor with magic numbers> * <other divisor with magic numbers>
+ int32_t power_of_2_factor =
+ CompilerIntrinsics::CountTrailingZeros(divisor_abs);
+ DivMagicNumbers magic_numbers =
+ DivMagicNumberFor(divisor_abs >> power_of_2_factor);
+ if (magic_numbers.M != InvalidDivMagicNumber.M) return true;
+
+ return false;
+}
+
+
+HValue* LChunkBuilder::SimplifiedDivisorForMathFloorOfDiv(HValue* divisor)
{
+ // Only optimize when we have magic numbers for the divisor.
+ // The standard integer division routine is usually slower than
transitionning
+ // to FPU.
+ if (divisor->IsConstant() &&
+ HConstant::cast(divisor)->HasInteger32Value()) {
+ HConstant* constant_val = HConstant::cast(divisor);
+ return constant_val->CopyToRepresentation(Representation::Integer32(),
+ divisor->block()->zone());
+ }
return NULL;
}
+
+
+LInstruction* LChunkBuilder::DoMathFloorOfDiv(HMathFloorOfDiv* instr) {
+ HValue* right = instr->right();
+ LOperand* dividend = UseRegister(instr->left());
+ LOperand* divisor = UseRegisterOrConstant(right);
+ LOperand* remainder = TempRegister();
+ ASSERT(right->IsConstant() &&
+ HConstant::cast(right)->HasInteger32Value());
+ return AssignEnvironment(DefineAsRegister(
+ new(zone()) LMathFloorOfDiv(dividend, divisor, remainder)));
+}
LInstruction* LChunkBuilder::DoMod(HMod* instr) {
=======================================
--- /branches/bleeding_edge/src/mips/lithium-mips.h Tue Jun 4 01:28:33 2013
+++ /branches/bleeding_edge/src/mips/lithium-mips.h Mon Jun 17 08:06:41 2013
@@ -137,6 +137,7 @@
V(MathCos) \
V(MathExp) \
V(MathFloor) \
+ V(MathFloorOfDiv) \
V(MathLog) \
V(MathMinMax) \
V(MathPowHalf) \
@@ -623,6 +624,25 @@
};
+class LMathFloorOfDiv: public LTemplateInstruction<1, 2, 1> {
+ public:
+ LMathFloorOfDiv(LOperand* left,
+ LOperand* right,
+ LOperand* temp = NULL) {
+ inputs_[0] = left;
+ inputs_[1] = right;
+ temps_[0] = temp;
+ }
+
+ LOperand* left() { return inputs_[0]; }
+ LOperand* right() { return inputs_[1]; }
+ LOperand* temp() { return temps_[0]; }
+
+ DECLARE_CONCRETE_INSTRUCTION(MathFloorOfDiv, "math-floor-of-div")
+ DECLARE_HYDROGEN_ACCESSOR(MathFloorOfDiv)
+};
+
+
class LMulI: public LTemplateInstruction<1, 2, 1> {
public:
LMulI(LOperand* left, LOperand* right, LOperand* temp) {
@@ -2642,6 +2662,9 @@
LInstruction* DoMultiplyAdd(HMul* mul, HValue* addend);
+ static bool HasMagicNumberForDivisor(int32_t divisor);
+ static HValue* SimplifiedDivisorForMathFloorOfDiv(HValue* val);
+
LInstruction* DoMathFloor(HUnaryMathOperation* instr);
LInstruction* DoMathRound(HUnaryMathOperation* instr);
LInstruction* DoMathAbs(HUnaryMathOperation* instr);
=======================================
--- /branches/bleeding_edge/test/mjsunit/mjsunit.status Wed Jun 12 04:02:51
2013
+++ /branches/bleeding_edge/test/mjsunit/mjsunit.status Mon Jun 17 08:06:41
2013
@@ -204,6 +204,9 @@
debug-liveedit-restart-frame: SKIP
debug-liveedit-double-call: SKIP
+# Currently always deopt on minus zero
+math-floor-of-div-minus-zero: SKIP
+
##############################################################################
# Native Client uses the ARM simulator so will behave similarly to arm
# on mjsunit tests.
--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
