From bf86e624d45ecab60ed3fc990570405812190e59 Mon Sep 17 00:00:00 2001 From: "bmeurer@chromium.org" Date: Mon, 10 Mar 2014 10:39:17 +0000 Subject: [PATCH] Reland "Handle non-power-of-2 divisors in division-like operations". Fixed the flooring div bug and added a test case. R=svenpanne@chromium.org Review URL: https://codereview.chromium.org/191293012 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@19749 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/a64/lithium-a64.cc | 84 ++++++++++++-- src/a64/lithium-a64.h | 65 +++++++++++ src/a64/lithium-codegen-a64.cc | 91 +++++++++++++++ src/a64/lithium-codegen-a64.h | 1 + src/a64/macro-assembler-a64.cc | 16 +++ src/a64/macro-assembler-a64.h | 4 + src/arm/lithium-arm.cc | 96 +++++++++------- src/arm/lithium-arm.h | 54 ++++++++- src/arm/lithium-codegen-arm.cc | 230 +++++++++++++------------------------- src/arm/lithium-codegen-arm.h | 11 -- src/arm/macro-assembler-arm.cc | 19 ++++ src/arm/macro-assembler-arm.h | 4 + src/assembler.cc | 34 ++++++ src/assembler.h | 15 +++ src/ia32/lithium-codegen-ia32.cc | 115 +++++++++++-------- src/ia32/lithium-ia32.cc | 80 +++++++++++-- src/ia32/lithium-ia32.h | 67 ++++++++++- src/ia32/macro-assembler-ia32.cc | 13 +++ src/ia32/macro-assembler-ia32.h | 4 + src/utils.cc | 14 --- src/utils.h | 26 ----- src/x64/assembler-x64.cc | 8 ++ src/x64/assembler-x64.h | 1 + src/x64/lithium-codegen-x64.cc | 98 +++++++++++----- src/x64/lithium-x64.cc | 75 +++++++++++-- src/x64/lithium-x64.h | 67 ++++++++++- src/x64/macro-assembler-x64.cc | 12 ++ src/x64/macro-assembler-x64.h | 4 + test/mjsunit/math-floor-of-div.js | 11 ++ 29 files changed, 962 insertions(+), 357 deletions(-) diff --git a/src/a64/lithium-a64.cc b/src/a64/lithium-a64.cc index 12812bb..dff7003 100644 --- a/src/a64/lithium-a64.cc +++ b/src/a64/lithium-a64.cc @@ -1369,7 +1369,7 @@ LInstruction* LChunkBuilder::DoDeoptimize(HDeoptimize* instr) { LInstruction* LChunkBuilder::DoDivByPowerOf2I(HDiv* instr) { - ASSERT(instr->representation().IsSmiOrInteger32()); + ASSERT(instr->representation().IsInteger32()); ASSERT(instr->left()->representation().Equals(instr->representation())); ASSERT(instr->right()->representation().Equals(instr->representation())); LOperand* dividend = UseRegister(instr->left()); @@ -1387,6 +1387,25 @@ LInstruction* LChunkBuilder::DoDivByPowerOf2I(HDiv* instr) { } +LInstruction* LChunkBuilder::DoDivByConstI(HDiv* instr) { + ASSERT(instr->representation().IsInteger32()); + ASSERT(instr->left()->representation().Equals(instr->representation())); + ASSERT(instr->right()->representation().Equals(instr->representation())); + LOperand* dividend = UseRegister(instr->left()); + int32_t divisor = instr->right()->GetInteger32Constant(); + bool truncating = instr->CheckFlag(HInstruction::kAllUsesTruncatingToInt32); + LOperand* temp = truncating ? NULL : TempRegister(); + LInstruction* result = + DefineAsRegister(new(zone()) LDivByConstI(dividend, divisor, temp)); + bool can_deopt = + divisor == 0 || + (instr->CheckFlag(HValue::kBailoutOnMinusZero) && + instr->left()->RangeCanInclude(0) && divisor < 0) || + !truncating; + return can_deopt ? AssignEnvironment(result) : result; +} + + LInstruction* LChunkBuilder::DoDivI(HBinaryOperation* instr) { ASSERT(instr->representation().IsSmiOrInteger32()); ASSERT(instr->left()->representation().Equals(instr->representation())); @@ -1402,10 +1421,13 @@ LInstruction* LChunkBuilder::DoDivI(HBinaryOperation* instr) { LInstruction* LChunkBuilder::DoDiv(HDiv* instr) { if (instr->representation().IsSmiOrInteger32()) { - // TODO(all): Add Smi support to DoDivI and turn this into a ternary. - if (instr->RightIsPowerOf2()) return DoDivByPowerOf2I(instr); - if (instr->representation().IsInteger32()) return DoDivI(instr); - return DoArithmeticT(Token::DIV, instr); + if (instr->RightIsPowerOf2()) { + return DoDivByPowerOf2I(instr); + } else if (instr->right()->IsConstant()) { + return DoDivByConstI(instr); + } else { + return DoDivI(instr); + } } else if (instr->representation().IsDouble()) { return DoArithmeticD(Token::DIV, instr); } else { @@ -1714,6 +1736,9 @@ LInstruction* LChunkBuilder::DoMapEnumLength(HMapEnumLength* instr) { LInstruction* LChunkBuilder::DoFlooringDivByPowerOf2I(HMathFloorOfDiv* instr) { + ASSERT(instr->representation().IsInteger32()); + ASSERT(instr->left()->representation().Equals(instr->representation())); + ASSERT(instr->right()->representation().Equals(instr->representation())); LOperand* dividend = UseRegisterAtStart(instr->left()); int32_t divisor = instr->right()->GetInteger32Constant(); LInstruction* result = @@ -1725,6 +1750,22 @@ LInstruction* LChunkBuilder::DoFlooringDivByPowerOf2I(HMathFloorOfDiv* instr) { } +LInstruction* LChunkBuilder::DoFlooringDivByConstI(HMathFloorOfDiv* instr) { + ASSERT(instr->representation().IsInteger32()); + ASSERT(instr->left()->representation().Equals(instr->representation())); + ASSERT(instr->right()->representation().Equals(instr->representation())); + LOperand* dividend = UseRegister(instr->left()); + int32_t divisor = instr->right()->GetInteger32Constant(); + LInstruction* result = + DefineAsRegister(new(zone()) LFlooringDivByConstI(dividend, divisor)); + bool can_deopt = + divisor == 0 || + (instr->CheckFlag(HValue::kBailoutOnMinusZero) && + instr->left()->RangeCanInclude(0) && divisor < 0); + return can_deopt ? AssignEnvironment(result) : result; +} + + LInstruction* LChunkBuilder::DoFlooringDivI(HMathFloorOfDiv* instr) { LOperand* dividend = UseRegister(instr->left()); LOperand* divisor = UseRegister(instr->right()); @@ -1739,8 +1780,7 @@ LInstruction* LChunkBuilder::DoMathFloorOfDiv(HMathFloorOfDiv* instr) { if (instr->RightIsPowerOf2()) { return DoFlooringDivByPowerOf2I(instr); } else if (instr->right()->IsConstant()) { - // TODO(svenpanne) Do something more efficient in this case. - return DoFlooringDivI(instr); + return DoFlooringDivByConstI(instr); } else { return DoFlooringDivI(instr); } @@ -1767,7 +1807,7 @@ LInstruction* LChunkBuilder::DoMathMinMax(HMathMinMax* instr) { LInstruction* LChunkBuilder::DoModByPowerOf2I(HMod* instr) { - ASSERT(instr->representation().IsSmiOrInteger32()); + ASSERT(instr->representation().IsInteger32()); ASSERT(instr->left()->representation().Equals(instr->representation())); ASSERT(instr->right()->representation().Equals(instr->representation())); LOperand* dividend = UseRegisterAtStart(instr->left()); @@ -1781,6 +1821,23 @@ LInstruction* LChunkBuilder::DoModByPowerOf2I(HMod* instr) { } +LInstruction* LChunkBuilder::DoModByConstI(HMod* instr) { + ASSERT(instr->representation().IsInteger32()); + ASSERT(instr->left()->representation().Equals(instr->representation())); + ASSERT(instr->right()->representation().Equals(instr->representation())); + LOperand* dividend = UseRegister(instr->left()); + int32_t divisor = instr->right()->GetInteger32Constant(); + LOperand* temp = TempRegister(); + LInstruction* result = + DefineAsRegister(new(zone()) LModByConstI(dividend, divisor, temp)); + bool can_deopt = + divisor == 0 || + (instr->CheckFlag(HValue::kBailoutOnMinusZero) && + instr->left()->CanBeNegative()); + return can_deopt ? AssignEnvironment(result) : result; +} + + LInstruction* LChunkBuilder::DoModI(HMod* instr) { ASSERT(instr->representation().IsSmiOrInteger32()); ASSERT(instr->left()->representation().Equals(instr->representation())); @@ -1798,10 +1855,13 @@ LInstruction* LChunkBuilder::DoModI(HMod* instr) { LInstruction* LChunkBuilder::DoMod(HMod* instr) { if (instr->representation().IsSmiOrInteger32()) { - // TODO(all): Add Smi support to DoDivI and turn this into a ternary. - if (instr->RightIsPowerOf2()) return DoModByPowerOf2I(instr); - if (instr->representation().IsInteger32()) return DoModI(instr); - return DoArithmeticT(Token::MOD, instr); + if (instr->RightIsPowerOf2()) { + return DoModByPowerOf2I(instr); + } else if (instr->right()->IsConstant()) { + return DoModByConstI(instr); + } else { + return DoModI(instr); + } } else if (instr->representation().IsDouble()) { return DoArithmeticD(Token::MOD, instr); } else { diff --git a/src/a64/lithium-a64.h b/src/a64/lithium-a64.h index aa1c23a..6f718e5 100644 --- a/src/a64/lithium-a64.h +++ b/src/a64/lithium-a64.h @@ -90,6 +90,7 @@ class LCodeGen; V(DebugBreak) \ V(DeclareGlobals) \ V(Deoptimize) \ + V(DivByConstI) \ V(DivByPowerOf2I) \ V(DivI) \ V(DoubleBits) \ @@ -97,6 +98,7 @@ class LCodeGen; V(Drop) \ V(Dummy) \ V(DummyUse) \ + V(FlooringDivByConstI) \ V(FlooringDivByPowerOf2I) \ V(FlooringDivI) \ V(ForInCacheArray) \ @@ -143,6 +145,7 @@ class LCodeGen; V(MathPowHalf) \ V(MathRound) \ V(MathSqrt) \ + V(ModByConstI) \ V(ModByPowerOf2I) \ V(ModI) \ V(MulConstIS) \ @@ -1300,6 +1303,26 @@ class LDivByPowerOf2I V8_FINAL : public LTemplateInstruction<1, 1, 0> { }; +class LDivByConstI V8_FINAL : public LTemplateInstruction<1, 1, 1> { + public: + LDivByConstI(LOperand* dividend, int32_t divisor, LOperand* temp) { + inputs_[0] = dividend; + divisor_ = divisor; + temps_[0] = temp; + } + + LOperand* dividend() { return inputs_[0]; } + int32_t divisor() const { return divisor_; } + LOperand* temp() { return temps_[0]; } + + DECLARE_CONCRETE_INSTRUCTION(DivByConstI, "div-by-const-i") + DECLARE_HYDROGEN_ACCESSOR(Div) + + private: + int32_t divisor_; +}; + + class LDivI V8_FINAL : public LTemplateInstruction<1, 2, 1> { public: LDivI(LOperand* left, LOperand* right, LOperand* temp) { @@ -1949,6 +1972,25 @@ class LFlooringDivByPowerOf2I V8_FINAL : public LTemplateInstruction<1, 1, 0> { }; +class LFlooringDivByConstI V8_FINAL : public LTemplateInstruction<1, 1, 0> { + public: + LFlooringDivByConstI(LOperand* dividend, int32_t divisor) { + inputs_[0] = dividend; + divisor_ = divisor; + } + + LOperand* dividend() { return inputs_[0]; } + int32_t divisor() const { return divisor_; } + LOperand* temp1() { return temps_[0]; } + + DECLARE_CONCRETE_INSTRUCTION(FlooringDivByConstI, "flooring-div-by-const-i") + DECLARE_HYDROGEN_ACCESSOR(MathFloorOfDiv) + + private: + int32_t divisor_; +}; + + class LFlooringDivI V8_FINAL : public LTemplateInstruction<1, 2, 1> { public: LFlooringDivI(LOperand* dividend, LOperand* divisor, LOperand* temp) { @@ -2040,6 +2082,26 @@ class LModByPowerOf2I V8_FINAL : public LTemplateInstruction<1, 1, 0> { }; +class LModByConstI V8_FINAL : public LTemplateInstruction<1, 1, 1> { + public: + LModByConstI(LOperand* dividend, int32_t divisor, LOperand* temp) { + inputs_[0] = dividend; + divisor_ = divisor; + temps_[0] = temp; + } + + LOperand* dividend() { return inputs_[0]; } + int32_t divisor() const { return divisor_; } + LOperand* temp() { return temps_[0]; } + + DECLARE_CONCRETE_INSTRUCTION(ModByConstI, "mod-by-const-i") + DECLARE_HYDROGEN_ACCESSOR(Mod) + + private: + int32_t divisor_; +}; + + class LModI V8_FINAL : public LTemplateInstruction<1, 2, 0> { public: LModI(LOperand* left, LOperand* right) { @@ -2931,10 +2993,13 @@ class LChunkBuilder V8_FINAL : public LChunkBuilderBase { #undef DECLARE_DO LInstruction* DoDivByPowerOf2I(HDiv* instr); + LInstruction* DoDivByConstI(HDiv* instr); LInstruction* DoDivI(HBinaryOperation* instr); LInstruction* DoModByPowerOf2I(HMod* instr); + LInstruction* DoModByConstI(HMod* instr); LInstruction* DoModI(HMod* instr); LInstruction* DoFlooringDivByPowerOf2I(HMathFloorOfDiv* instr); + LInstruction* DoFlooringDivByConstI(HMathFloorOfDiv* instr); LInstruction* DoFlooringDivI(HMathFloorOfDiv* instr); static bool HasMagicNumberForDivision(int32_t divisor); diff --git a/src/a64/lithium-codegen-a64.cc b/src/a64/lithium-codegen-a64.cc index 8e443b9..6236eb9 100644 --- a/src/a64/lithium-codegen-a64.cc +++ b/src/a64/lithium-codegen-a64.cc @@ -1057,6 +1057,11 @@ void LCodeGen::DeoptimizeIfZero(Register rt, LEnvironment* environment) { } +void LCodeGen::DeoptimizeIfNotZero(Register rt, LEnvironment* environment) { + DeoptimizeBranch(environment, reg_not_zero, rt); +} + + void LCodeGen::DeoptimizeIfNegative(Register rt, LEnvironment* environment) { int sign_bit = rt.Is64Bits() ? kXSignBit : kWSignBit; DeoptimizeBranch(environment, reg_bit_set, rt, sign_bit); @@ -2634,6 +2639,39 @@ void LCodeGen::DoDivByPowerOf2I(LDivByPowerOf2I* instr) { } +void LCodeGen::DoDivByConstI(LDivByConstI* instr) { + Register dividend = ToRegister32(instr->dividend()); + int32_t divisor = instr->divisor(); + Register result = ToRegister32(instr->result()); + ASSERT(!AreAliased(dividend, result)); + + if (divisor == 0) { + Deoptimize(instr->environment()); + return; + } + + // Check for (0 / -x) that will produce negative zero. + HDiv* hdiv = instr->hydrogen(); + if (hdiv->CheckFlag(HValue::kBailoutOnMinusZero) && + hdiv->left()->RangeCanInclude(0) && divisor < 0) { + DeoptimizeIfZero(dividend, instr->environment()); + } + + __ FlooringDiv(result, dividend, Abs(divisor)); + __ Add(result, result, Operand(dividend, LSR, 31)); + if (divisor < 0) __ Neg(result, result); + + if (!hdiv->CheckFlag(HInstruction::kAllUsesTruncatingToInt32)) { + Register temp = ToRegister32(instr->temp()); + ASSERT(!AreAliased(dividend, result, temp)); + __ Sxtw(dividend.X(), dividend); + __ Mov(temp, divisor); + __ Smsubl(temp.X(), result, temp, dividend.X()); + DeoptimizeIfNotZero(temp, instr->environment()); + } +} + + void LCodeGen::DoDivI(LDivI* instr) { Register dividend = ToRegister32(instr->left()); Register divisor = ToRegister32(instr->right()); @@ -3839,6 +3877,29 @@ void LCodeGen::DoFlooringDivByPowerOf2I(LFlooringDivByPowerOf2I* instr) { } +void LCodeGen::DoFlooringDivByConstI(LFlooringDivByConstI* instr) { + Register dividend = ToRegister32(instr->dividend()); + int32_t divisor = instr->divisor(); + Register result = ToRegister32(instr->result()); + ASSERT(!AreAliased(dividend, result)); + + if (divisor == 0) { + Deoptimize(instr->environment()); + return; + } + + // Check for (0 / -x) that will produce negative zero. + HMathFloorOfDiv* hdiv = instr->hydrogen(); + if (hdiv->CheckFlag(HValue::kBailoutOnMinusZero) && + hdiv->left()->RangeCanInclude(0) && divisor < 0) { + __ Cmp(dividend, 0); + DeoptimizeIf(eq, instr->environment()); + } + + __ FlooringDiv(result, dividend, divisor); +} + + void LCodeGen::DoFlooringDivI(LFlooringDivI* instr) { Register dividend = ToRegister32(instr->dividend()); Register divisor = ToRegister32(instr->divisor()); @@ -4098,6 +4159,36 @@ void LCodeGen::DoModByPowerOf2I(LModByPowerOf2I* instr) { } +void LCodeGen::DoModByConstI(LModByConstI* instr) { + Register dividend = ToRegister32(instr->dividend()); + int32_t divisor = instr->divisor(); + Register result = ToRegister32(instr->result()); + Register temp = ToRegister32(instr->temp()); + ASSERT(!AreAliased(dividend, result, temp)); + + if (divisor == 0) { + Deoptimize(instr->environment()); + return; + } + + __ FlooringDiv(result, dividend, Abs(divisor)); + __ Add(result, result, Operand(dividend, LSR, 31)); + __ Sxtw(dividend.X(), dividend); + __ Mov(temp, Abs(divisor)); + __ Smsubl(result.X(), result, temp, dividend.X()); + + // Check for negative zero. + HMod* hmod = instr->hydrogen(); + if (hmod->CheckFlag(HValue::kBailoutOnMinusZero) && + hmod->left()->CanBeNegative()) { + Label remainder_not_zero; + __ Cbnz(result, &remainder_not_zero); + DeoptimizeIfNegative(dividend, instr->environment()); + __ bind(&remainder_not_zero); + } +} + + void LCodeGen::DoModI(LModI* instr) { Register dividend = ToRegister32(instr->left()); Register divisor = ToRegister32(instr->right()); diff --git a/src/a64/lithium-codegen-a64.h b/src/a64/lithium-codegen-a64.h index 74dad62..140b1ae 100644 --- a/src/a64/lithium-codegen-a64.h +++ b/src/a64/lithium-codegen-a64.h @@ -226,6 +226,7 @@ class LCodeGen: public LCodeGenBase { Deoptimizer::BailoutType* override_bailout_type = NULL); void DeoptimizeIf(Condition cc, LEnvironment* environment); void DeoptimizeIfZero(Register rt, LEnvironment* environment); + void DeoptimizeIfNotZero(Register rt, LEnvironment* environment); void DeoptimizeIfNegative(Register rt, LEnvironment* environment); void DeoptimizeIfSmi(Register rt, LEnvironment* environment); void DeoptimizeIfNotSmi(Register rt, LEnvironment* environment); diff --git a/src/a64/macro-assembler-a64.cc b/src/a64/macro-assembler-a64.cc index 53c7777..e69597c 100644 --- a/src/a64/macro-assembler-a64.cc +++ b/src/a64/macro-assembler-a64.cc @@ -4932,6 +4932,22 @@ bool MacroAssembler::IsCodeAgeSequence(byte* sequence) { #endif +void MacroAssembler::FlooringDiv(Register result, + Register dividend, + int32_t divisor) { + Register tmp = WTmp0(); + ASSERT(!AreAliased(result, dividend, tmp)); + ASSERT(result.Is32Bits() && dividend.Is32Bits()); + MultiplierAndShift ms(divisor); + Mov(tmp, Operand(ms.multiplier())); + Smull(result.X(), dividend, tmp); + Asr(result.X(), result.X(), 32); + if (divisor > 0 && ms.multiplier() < 0) Add(result, result, dividend); + if (divisor < 0 && ms.multiplier() > 0) Sub(result, result, dividend); + if (ms.shift() > 0) Asr(result, result, ms.shift()); +} + + #undef __ #define __ masm-> diff --git a/src/a64/macro-assembler-a64.h b/src/a64/macro-assembler-a64.h index b11b9b6..81d0df6 100644 --- a/src/a64/macro-assembler-a64.h +++ b/src/a64/macro-assembler-a64.h @@ -1677,6 +1677,10 @@ class MacroAssembler : public Assembler { void LoadContext(Register dst, int context_chain_length); + // Emit code for a flooring division by a constant. The dividend register is + // unchanged and Tmp0() gets clobbered. Dividend and result must be different. + void FlooringDiv(Register result, Register dividend, int32_t divisor); + // --------------------------------------------------------------------------- // StatsCounter support diff --git a/src/arm/lithium-arm.cc b/src/arm/lithium-arm.cc index 63109f5..f12b6ea 100644 --- a/src/arm/lithium-arm.cc +++ b/src/arm/lithium-arm.cc @@ -1257,6 +1257,23 @@ LInstruction* LChunkBuilder::DoDivByPowerOf2I(HDiv* instr) { } +LInstruction* LChunkBuilder::DoDivByConstI(HDiv* instr) { + ASSERT(instr->representation().IsInteger32()); + ASSERT(instr->left()->representation().Equals(instr->representation())); + ASSERT(instr->right()->representation().Equals(instr->representation())); + LOperand* dividend = UseRegister(instr->left()); + int32_t divisor = instr->right()->GetInteger32Constant(); + LInstruction* result = + DefineAsRegister(new(zone()) LDivByConstI(dividend, divisor)); + bool can_deopt = + divisor == 0 || + (instr->CheckFlag(HValue::kBailoutOnMinusZero) && + instr->left()->RangeCanInclude(0) && divisor < 0) || + !instr->CheckFlag(HInstruction::kAllUsesTruncatingToInt32); + return can_deopt ? AssignEnvironment(result) : result; +} + + LInstruction* LChunkBuilder::DoDivI(HBinaryOperation* instr) { ASSERT(instr->representation().IsSmiOrInteger32()); ASSERT(instr->left()->representation().Equals(instr->representation())); @@ -1271,7 +1288,13 @@ LInstruction* LChunkBuilder::DoDivI(HBinaryOperation* instr) { LInstruction* LChunkBuilder::DoDiv(HDiv* instr) { if (instr->representation().IsSmiOrInteger32()) { - return instr->RightIsPowerOf2() ? DoDivByPowerOf2I(instr) : DoDivI(instr); + if (instr->RightIsPowerOf2()) { + return DoDivByPowerOf2I(instr); + } else if (instr->right()->IsConstant()) { + return DoDivByConstI(instr); + } else { + return DoDivI(instr); + } } else if (instr->representation().IsDouble()) { return DoArithmeticD(Token::DIV, instr); } else { @@ -1280,29 +1303,6 @@ LInstruction* LChunkBuilder::DoDiv(HDiv* instr) { } -bool LChunkBuilder::HasMagicNumberForDivisor(int32_t divisor) { - uint32_t divisor_abs = abs(divisor); - // Dividing by 0 or powers of 2 is easy. - if (divisor == 0 || 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 - // * - // but not - // * - int32_t power_of_2_factor = - CompilerIntrinsics::CountTrailingZeros(divisor_abs); - DivMagicNumbers magic_numbers = - DivMagicNumberFor(divisor_abs >> power_of_2_factor); - return magic_numbers.M != InvalidDivMagicNumber.M; -} - - LInstruction* LChunkBuilder::DoFlooringDivByPowerOf2I(HMathFloorOfDiv* instr) { LOperand* dividend = UseRegisterAtStart(instr->left()); int32_t divisor = instr->right()->GetInteger32Constant(); @@ -1317,15 +1317,18 @@ LInstruction* LChunkBuilder::DoFlooringDivByPowerOf2I(HMathFloorOfDiv* instr) { LInstruction* LChunkBuilder::DoFlooringDivByConstI(HMathFloorOfDiv* instr) { + ASSERT(instr->representation().IsInteger32()); + ASSERT(instr->left()->representation().Equals(instr->representation())); + ASSERT(instr->right()->representation().Equals(instr->representation())); LOperand* dividend = UseRegister(instr->left()); - LOperand* divisor = CpuFeatures::IsSupported(SUDIV) - ? UseRegister(instr->right()) - : UseOrConstant(instr->right()); - LOperand* remainder = TempRegister(); + int32_t divisor = instr->right()->GetInteger32Constant(); LInstruction* result = - DefineAsRegister( - new(zone()) LFlooringDivByConstI(dividend, divisor, remainder)); - return AssignEnvironment(result); + DefineAsRegister(new(zone()) LFlooringDivByConstI(dividend, divisor)); + bool can_deopt = + divisor == 0 || + (instr->CheckFlag(HValue::kBailoutOnMinusZero) && + instr->left()->RangeCanInclude(0) && divisor < 0); + return can_deopt ? AssignEnvironment(result) : result; } @@ -1333,12 +1336,7 @@ LInstruction* LChunkBuilder::DoMathFloorOfDiv(HMathFloorOfDiv* instr) { if (instr->RightIsPowerOf2()) { return DoFlooringDivByPowerOf2I(instr); } else if (instr->right()->IsConstant()) { - // LMathFloorOfDiv can currently only handle a subset of divisors, so fall - // back to a flooring division in all other cases. - return (CpuFeatures::IsSupported(SUDIV) || - HasMagicNumberForDivisor(instr->right()->GetInteger32Constant())) - ? DoFlooringDivByConstI(instr) - : DoDivI(instr); + return DoFlooringDivByConstI(instr); } else { return DoDivI(instr); } @@ -1360,6 +1358,22 @@ LInstruction* LChunkBuilder::DoModByPowerOf2I(HMod* instr) { } +LInstruction* LChunkBuilder::DoModByConstI(HMod* instr) { + ASSERT(instr->representation().IsSmiOrInteger32()); + ASSERT(instr->left()->representation().Equals(instr->representation())); + ASSERT(instr->right()->representation().Equals(instr->representation())); + LOperand* dividend = UseRegister(instr->left()); + int32_t divisor = instr->right()->GetInteger32Constant(); + LInstruction* result = + DefineAsRegister(new(zone()) LModByConstI(dividend, divisor)); + bool can_deopt = + divisor == 0 || + (instr->CheckFlag(HValue::kBailoutOnMinusZero) && + instr->left()->CanBeNegative()); + return can_deopt ? AssignEnvironment(result) : result; +} + + LInstruction* LChunkBuilder::DoModI(HMod* instr) { ASSERT(instr->representation().IsSmiOrInteger32()); ASSERT(instr->left()->representation().Equals(instr->representation())); @@ -1395,7 +1409,13 @@ LInstruction* LChunkBuilder::DoModI(HMod* instr) { LInstruction* LChunkBuilder::DoMod(HMod* instr) { if (instr->representation().IsSmiOrInteger32()) { - return instr->RightIsPowerOf2() ? DoModByPowerOf2I(instr) : DoModI(instr); + if (instr->RightIsPowerOf2()) { + return DoModByPowerOf2I(instr); + } else if (instr->right()->IsConstant()) { + return DoModByConstI(instr); + } else { + return DoModI(instr); + } } else if (instr->representation().IsDouble()) { return DoArithmeticD(Token::MOD, instr); } else { diff --git a/src/arm/lithium-arm.h b/src/arm/lithium-arm.h index a304258..86cf2f2 100644 --- a/src/arm/lithium-arm.h +++ b/src/arm/lithium-arm.h @@ -86,6 +86,7 @@ class LCodeGen; V(DebugBreak) \ V(DeclareGlobals) \ V(Deoptimize) \ + V(DivByConstI) \ V(DivByPowerOf2I) \ V(DivI) \ V(DoubleBits) \ @@ -137,6 +138,7 @@ class LCodeGen; V(MathPowHalf) \ V(MathRound) \ V(MathSqrt) \ + V(ModByConstI) \ V(ModByPowerOf2I) \ V(ModI) \ V(MulI) \ @@ -638,6 +640,24 @@ class LModByPowerOf2I V8_FINAL : public LTemplateInstruction<1, 1, 0> { }; +class LModByConstI V8_FINAL : public LTemplateInstruction<1, 1, 0> { + public: + LModByConstI(LOperand* dividend, int32_t divisor) { + inputs_[0] = dividend; + divisor_ = divisor; + } + + LOperand* dividend() { return inputs_[0]; } + int32_t divisor() const { return divisor_; } + + DECLARE_CONCRETE_INSTRUCTION(ModByConstI, "mod-by-const-i") + DECLARE_HYDROGEN_ACCESSOR(Mod) + + private: + int32_t divisor_; +}; + + class LModI V8_FINAL : public LTemplateInstruction<1, 2, 2> { public: LModI(LOperand* left, LOperand* right, LOperand* temp, LOperand* temp2) { @@ -675,6 +695,24 @@ class LDivByPowerOf2I V8_FINAL : public LTemplateInstruction<1, 1, 0> { }; +class LDivByConstI V8_FINAL : public LTemplateInstruction<1, 1, 0> { + public: + LDivByConstI(LOperand* dividend, int32_t divisor) { + inputs_[0] = dividend; + divisor_ = divisor; + } + + LOperand* dividend() { return inputs_[0]; } + int32_t divisor() const { return divisor_; } + + DECLARE_CONCRETE_INSTRUCTION(DivByConstI, "div-by-const-i") + DECLARE_HYDROGEN_ACCESSOR(Div) + + private: + int32_t divisor_; +}; + + class LDivI V8_FINAL : public LTemplateInstruction<1, 2, 1> { public: LDivI(LOperand* left, LOperand* right, LOperand* temp) { @@ -713,20 +751,22 @@ class LFlooringDivByPowerOf2I V8_FINAL : public LTemplateInstruction<1, 1, 0> { }; -class LFlooringDivByConstI V8_FINAL : public LTemplateInstruction<1, 2, 1> { +class LFlooringDivByConstI V8_FINAL : public LTemplateInstruction<1, 1, 0> { public: - LFlooringDivByConstI(LOperand* dividend, LOperand* divisor, LOperand* temp) { + LFlooringDivByConstI(LOperand* dividend, int32_t divisor) { inputs_[0] = dividend; - inputs_[1] = divisor; - temps_[0] = temp; + divisor_ = divisor; } LOperand* dividend() { return inputs_[0]; } - LOperand* divisor() { return inputs_[1]; } - LOperand* temp() { return temps_[0]; } + int32_t divisor() const { return divisor_; } + LOperand* temp1() { return temps_[0]; } DECLARE_CONCRETE_INSTRUCTION(FlooringDivByConstI, "flooring-div-by-const-i") DECLARE_HYDROGEN_ACCESSOR(MathFloorOfDiv) + + private: + int32_t divisor_; }; @@ -2711,8 +2751,10 @@ class LChunkBuilder V8_FINAL : public LChunkBuilderBase { LInstruction* DoMathPowHalf(HUnaryMathOperation* instr); LInstruction* DoMathClz32(HUnaryMathOperation* instr); LInstruction* DoDivByPowerOf2I(HDiv* instr); + LInstruction* DoDivByConstI(HDiv* instr); LInstruction* DoDivI(HBinaryOperation* instr); LInstruction* DoModByPowerOf2I(HMod* instr); + LInstruction* DoModByConstI(HMod* instr); LInstruction* DoModI(HMod* instr); LInstruction* DoFlooringDivByPowerOf2I(HMathFloorOfDiv* instr); LInstruction* DoFlooringDivByConstI(HMathFloorOfDiv* instr); diff --git a/src/arm/lithium-codegen-arm.cc b/src/arm/lithium-codegen-arm.cc index a95bb5e..53d1537 100644 --- a/src/arm/lithium-codegen-arm.cc +++ b/src/arm/lithium-codegen-arm.cc @@ -1144,6 +1144,36 @@ void LCodeGen::DoModByPowerOf2I(LModByPowerOf2I* instr) { } +void LCodeGen::DoModByConstI(LModByConstI* instr) { + Register dividend = ToRegister(instr->dividend()); + int32_t divisor = instr->divisor(); + Register result = ToRegister(instr->result()); + ASSERT(!dividend.is(result)); + + if (divisor == 0) { + DeoptimizeIf(al, instr->environment()); + return; + } + + __ FlooringDiv(result, dividend, Abs(divisor)); + __ add(result, result, Operand(dividend, LSR, 31)); + __ mov(ip, Operand(Abs(divisor))); + __ smull(result, ip, result, ip); + __ sub(result, dividend, result, SetCC); + + // Check for negative zero. + HMod* hmod = instr->hydrogen(); + if (hmod->CheckFlag(HValue::kBailoutOnMinusZero) && + hmod->left()->CanBeNegative()) { + Label remainder_not_zero; + __ b(ne, &remainder_not_zero); + __ cmp(dividend, Operand::Zero()); + DeoptimizeIf(lt, instr->environment()); + __ bind(&remainder_not_zero); + } +} + + void LCodeGen::DoModI(LModI* instr) { HMod* hmod = instr->hydrogen(); HValue* left = hmod->left(); @@ -1258,100 +1288,6 @@ void LCodeGen::DoModI(LModI* instr) { } -void LCodeGen::EmitSignedIntegerDivisionByConstant( - Register result, - Register dividend, - int32_t divisor, - Register remainder, - Register scratch, - LEnvironment* environment) { - ASSERT(!AreAliased(dividend, scratch, ip)); - 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 { - __ rsb(result, dividend, Operand::Zero(), SetCC); - DeoptimizeIf(vs, environment); - } - // Compute the remainder. - __ mov(remainder, Operand::Zero()); - 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) { - __ mov(scratch, Operand(dividend, ASR, power - 1)); - } - __ add(scratch, dividend, Operand(scratch, LSR, 32 - power)); - __ mov(result, Operand(scratch, ASR, 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); - __ rsb(result, result, Operand::Zero()); - } - // Compute the remainder. - if (divisor > 0) { - __ sub(remainder, dividend, Operand(result, LSL, power)); - } else { - __ add(remainder, dividend, Operand(result, LSL, power)); - } - return; - } else { - // 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 - // * - // but not - // * - 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; - - __ mov(ip, Operand(M)); - __ smull(ip, scratch, dividend, ip); - if (M < 0) { - __ add(scratch, scratch, Operand(dividend)); - } - if (s > 0) { - __ mov(scratch, Operand(scratch, ASR, s)); - } - __ add(result, scratch, Operand(dividend, LSR, 31)); - if (divisor < 0) __ rsb(result, result, Operand::Zero()); - // Compute the remainder. - __ mov(ip, Operand(divisor)); - // This sequence could be replaced with 'mls' when - // it gets implemented. - __ mul(scratch, result, ip); - __ sub(remainder, dividend, scratch); - } - } -} - - void LCodeGen::DoDivByPowerOf2I(LDivByPowerOf2I* instr) { Register dividend = ToRegister(instr->dividend()); int32_t divisor = instr->divisor(); @@ -1398,6 +1334,38 @@ void LCodeGen::DoDivByPowerOf2I(LDivByPowerOf2I* instr) { } +void LCodeGen::DoDivByConstI(LDivByConstI* instr) { + Register dividend = ToRegister(instr->dividend()); + int32_t divisor = instr->divisor(); + Register result = ToRegister(instr->result()); + ASSERT(!dividend.is(result)); + + if (divisor == 0) { + DeoptimizeIf(al, instr->environment()); + return; + } + + // Check for (0 / -x) that will produce negative zero. + HDiv* hdiv = instr->hydrogen(); + if (hdiv->CheckFlag(HValue::kBailoutOnMinusZero) && + hdiv->left()->RangeCanInclude(0) && divisor < 0) { + __ cmp(dividend, Operand::Zero()); + DeoptimizeIf(eq, instr->environment()); + } + + __ FlooringDiv(result, dividend, Abs(divisor)); + __ add(result, result, Operand(dividend, LSR, 31)); + if (divisor < 0) __ rsb(result, result, Operand::Zero()); + + if (!hdiv->CheckFlag(HInstruction::kAllUsesTruncatingToInt32)) { + __ mov(ip, Operand(divisor)); + __ smull(scratch0(), ip, result, ip); + __ sub(scratch0(), scratch0(), dividend, SetCC); + DeoptimizeIf(ne, instr->environment()); + } +} + + void LCodeGen::DoDivI(LDivI* instr) { const Register left = ToRegister(instr->left()); const Register right = ToRegister(instr->right()); @@ -1531,71 +1499,25 @@ void LCodeGen::DoFlooringDivByPowerOf2I(LFlooringDivByPowerOf2I* instr) { void LCodeGen::DoFlooringDivByConstI(LFlooringDivByConstI* instr) { - Register left = ToRegister(instr->dividend()); - Register remainder = ToRegister(instr->temp()); - Register scratch = scratch0(); + Register dividend = ToRegister(instr->dividend()); + int32_t divisor = instr->divisor(); Register result = ToRegister(instr->result()); + ASSERT(!dividend.is(result)); - if (!CpuFeatures::IsSupported(SUDIV)) { - // If the CPU doesn't support sdiv instruction, we only optimize when we - // have magic numbers for the divisor. The standard integer division routine - // is usually slower than transitionning to VFP. - ASSERT(instr->divisor()->IsConstantOperand()); - int32_t divisor = ToInteger32(LConstantOperand::cast(instr->divisor())); - ASSERT(LChunkBuilder::HasMagicNumberForDivisor(divisor)); - if (divisor < 0) { - __ cmp(left, Operand::Zero()); - DeoptimizeIf(eq, instr->environment()); - } - EmitSignedIntegerDivisionByConstant(result, - left, - divisor, - remainder, - scratch, - instr->environment()); - // We performed a truncating division. Correct the result if necessary. - __ cmp(remainder, Operand::Zero()); - __ teq(remainder, Operand(divisor), ne); - __ sub(result, result, Operand(1), LeaveCC, mi); - } else { - CpuFeatureScope scope(masm(), SUDIV); - // TODO(svenpanne) We *statically* know the divisor, use that fact! - Register right = ToRegister(instr->divisor()); + if (divisor == 0) { + DeoptimizeIf(al, instr->environment()); + return; + } - // Check for x / 0. - __ cmp(right, Operand::Zero()); + // Check for (0 / -x) that will produce negative zero. + HMathFloorOfDiv* hdiv = instr->hydrogen(); + if (hdiv->CheckFlag(HValue::kBailoutOnMinusZero) && + hdiv->left()->RangeCanInclude(0) && divisor < 0) { + __ cmp(dividend, Operand::Zero()); DeoptimizeIf(eq, instr->environment()); - - // Check for (kMinInt / -1). - if (instr->hydrogen()->CheckFlag(HValue::kCanOverflow)) { - __ cmp(left, Operand(kMinInt)); - __ cmp(right, Operand(-1), eq); - DeoptimizeIf(eq, instr->environment()); - } - - // Check for (0 / -x) that will produce negative zero. - if (instr->hydrogen()->CheckFlag(HValue::kBailoutOnMinusZero)) { - __ cmp(right, Operand::Zero()); - __ cmp(left, Operand::Zero(), mi); - // "right" can't be null because the code would have already been - // deoptimized. The Z flag is set only if (right < 0) and (left == 0). - // In this case we need to deoptimize to produce a -0. - DeoptimizeIf(eq, instr->environment()); - } - - Label done; - __ sdiv(result, left, right); - // If both operands have the same sign then we are done. - __ eor(remainder, left, Operand(right), SetCC); - __ b(pl, &done); - - // Check if the result needs to be corrected. - __ mls(remainder, result, right, left); - __ cmp(remainder, Operand::Zero()); - __ sub(result, result, Operand(1), LeaveCC, ne); - - __ bind(&done); } + + __ FlooringDiv(result, dividend, divisor); } diff --git a/src/arm/lithium-codegen-arm.h b/src/arm/lithium-codegen-arm.h index 1638ee9..e0f5009 100644 --- a/src/arm/lithium-codegen-arm.h +++ b/src/arm/lithium-codegen-arm.h @@ -349,17 +349,6 @@ class LCodeGen: public LCodeGenBase { 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(int space_needed) V8_OVERRIDE; void DoLoadKeyedExternalArray(LLoadKeyed* instr); void DoLoadKeyedFixedDoubleArray(LLoadKeyed* instr); diff --git a/src/arm/macro-assembler-arm.cc b/src/arm/macro-assembler-arm.cc index d705c90..437b731 100644 --- a/src/arm/macro-assembler-arm.cc +++ b/src/arm/macro-assembler-arm.cc @@ -4032,6 +4032,25 @@ void CodePatcher::EmitCondition(Condition cond) { } +void MacroAssembler::FlooringDiv(Register result, + Register dividend, + int32_t divisor) { + ASSERT(!dividend.is(result)); + ASSERT(!dividend.is(ip)); + ASSERT(!result.is(ip)); + MultiplierAndShift ms(divisor); + mov(ip, Operand(ms.multiplier())); + smull(ip, result, dividend, ip); + if (divisor > 0 && ms.multiplier() < 0) { + add(result, result, Operand(dividend)); + } + if (divisor < 0 && ms.multiplier() > 0) { + sub(result, result, Operand(dividend)); + } + if (ms.shift() > 0) mov(result, Operand(result, ASR, ms.shift())); +} + + } } // namespace v8::internal #endif // V8_TARGET_ARCH_ARM diff --git a/src/arm/macro-assembler-arm.h b/src/arm/macro-assembler-arm.h index 0eaf4dc..f98f141 100644 --- a/src/arm/macro-assembler-arm.h +++ b/src/arm/macro-assembler-arm.h @@ -1155,6 +1155,10 @@ class MacroAssembler: public Assembler { } + // Emit code for a flooring division by a constant. The dividend register is + // unchanged and ip gets clobbered. Dividend and result must be different. + void FlooringDiv(Register result, Register dividend, int32_t divisor); + // --------------------------------------------------------------------------- // StatsCounter support diff --git a/src/assembler.cc b/src/assembler.cc index d51264d..0117fc5 100644 --- a/src/assembler.cc +++ b/src/assembler.cc @@ -1593,4 +1593,38 @@ bool PositionsRecorder::WriteRecordedPositions() { return written; } + +MultiplierAndShift::MultiplierAndShift(int32_t d) { + ASSERT(d <= -2 || 2 <= d); + const uint32_t two31 = 0x80000000; + uint32_t ad = Abs(d); + uint32_t t = two31 + (uint32_t(d) >> 31); + uint32_t anc = t - 1 - t % ad; // Absolute value of nc. + int32_t p = 31; // Init. p. + uint32_t q1 = two31 / anc; // Init. q1 = 2**p/|nc|. + uint32_t r1 = two31 - q1 * anc; // Init. r1 = rem(2**p, |nc|). + uint32_t q2 = two31 / ad; // Init. q2 = 2**p/|d|. + uint32_t r2 = two31 - q2 * ad; // Init. r2 = rem(2**p, |d|). + uint32_t delta; + do { + p++; + q1 *= 2; // Update q1 = 2**p/|nc|. + r1 *= 2; // Update r1 = rem(2**p, |nc|). + if (r1 >= anc) { // Must be an unsigned comparison here. + q1++; + r1 = r1 - anc; + } + q2 *= 2; // Update q2 = 2**p/|d|. + r2 *= 2; // Update r2 = rem(2**p, |d|). + if (r2 >= ad) { // Must be an unsigned comparison here. + q2++; + r2 = r2 - ad; + } + delta = ad - r2; + } while (q1 < delta || (q1 == delta && r1 == 0)); + int32_t mul = static_cast(q2 + 1); + multiplier_ = (d < 0) ? -mul : mul; + shift_ = p - 32; +} + } } // namespace v8::internal diff --git a/src/assembler.h b/src/assembler.h index 2506001..c953629 100644 --- a/src/assembler.h +++ b/src/assembler.h @@ -1037,6 +1037,21 @@ class NullCallWrapper : public CallWrapper { virtual void AfterCall() const { } }; + +// The multiplier and shift for signed division via multiplication, see Warren's +// "Hacker's Delight", chapter 10. +class MultiplierAndShift { + public: + explicit MultiplierAndShift(int32_t d); + int32_t multiplier() const { return multiplier_; } + int32_t shift() const { return shift_; } + + private: + int32_t multiplier_; + int32_t shift_; +}; + + } } // namespace v8::internal #endif // V8_ASSEMBLER_H_ diff --git a/src/ia32/lithium-codegen-ia32.cc b/src/ia32/lithium-codegen-ia32.cc index cbad030..56d850b 100644 --- a/src/ia32/lithium-codegen-ia32.cc +++ b/src/ia32/lithium-codegen-ia32.cc @@ -1401,6 +1401,37 @@ void LCodeGen::DoModByPowerOf2I(LModByPowerOf2I* instr) { } +void LCodeGen::DoModByConstI(LModByConstI* instr) { + Register dividend = ToRegister(instr->dividend()); + int32_t divisor = instr->divisor(); + ASSERT(ToRegister(instr->result()).is(eax)); + + if (divisor == 0) { + DeoptimizeIf(no_condition, instr->environment()); + return; + } + + __ FlooringDiv(dividend, Abs(divisor)); + __ mov(eax, dividend); + __ shr(eax, 31); + __ add(edx, eax); + __ imul(edx, edx, Abs(divisor)); + __ mov(eax, dividend); + __ sub(eax, edx); + + // Check for negative zero. + HMod* hmod = instr->hydrogen(); + if (hmod->CheckFlag(HValue::kBailoutOnMinusZero) && + hmod->left()->CanBeNegative()) { + Label remainder_not_zero; + __ j(not_zero, &remainder_not_zero, Label::kNear); + __ cmp(dividend, Immediate(0)); + DeoptimizeIf(less, instr->environment()); + __ bind(&remainder_not_zero); + } +} + + void LCodeGen::DoModI(LModI* instr) { HMod* hmod = instr->hydrogen(); HValue* left = hmod->left(); @@ -1500,6 +1531,39 @@ void LCodeGen::DoDivByPowerOf2I(LDivByPowerOf2I* instr) { } +void LCodeGen::DoDivByConstI(LDivByConstI* instr) { + Register dividend = ToRegister(instr->dividend()); + int32_t divisor = instr->divisor(); + ASSERT(ToRegister(instr->result()).is(edx)); + + if (divisor == 0) { + DeoptimizeIf(no_condition, instr->environment()); + return; + } + + // Check for (0 / -x) that will produce negative zero. + HDiv* hdiv = instr->hydrogen(); + if (hdiv->CheckFlag(HValue::kBailoutOnMinusZero) && + hdiv->left()->RangeCanInclude(0) && divisor < 0) { + __ test(dividend, dividend); + DeoptimizeIf(zero, instr->environment()); + } + + __ FlooringDiv(dividend, Abs(divisor)); + __ mov(eax, dividend); + __ shr(eax, 31); + __ add(edx, eax); + if (divisor < 0) __ neg(edx); + + if (!hdiv->CheckFlag(HInstruction::kAllUsesTruncatingToInt32)) { + __ mov(eax, edx); + __ imul(eax, eax, divisor); + __ sub(eax, dividend); + DeoptimizeIf(not_equal, instr->environment()); + } +} + + void LCodeGen::DoDivI(LDivI* instr) { Register dividend = ToRegister(instr->left()); Register divisor = ToRegister(instr->right()); @@ -1599,8 +1663,6 @@ void LCodeGen::DoFlooringDivByPowerOf2I(LFlooringDivByPowerOf2I* instr) { void LCodeGen::DoFlooringDivByConstI(LFlooringDivByConstI* instr) { Register dividend = ToRegister(instr->dividend()); int32_t divisor = instr->divisor(); - Register scratch = ToRegister(instr->temp()); - ASSERT(ToRegister(instr->dividend()).is(eax)); ASSERT(ToRegister(instr->result()).is(edx)); if (divisor == 0) { @@ -1608,52 +1670,15 @@ void LCodeGen::DoFlooringDivByConstI(LFlooringDivByConstI* instr) { return; } - // Find b which: 2^b < divisor_abs < 2^(b+1). - uint32_t divisor_abs = abs(divisor); - unsigned b = 31 - CompilerIntrinsics::CountLeadingZeros(divisor_abs); - unsigned shift = 32 + b; // Precision +1bit (effectively). - double multiplier_f = - static_cast(static_cast(1) << shift) / divisor_abs; - int64_t multiplier; - if (multiplier_f - std::floor(multiplier_f) < 0.5) { - multiplier = static_cast(std::floor(multiplier_f)); - } else { - multiplier = static_cast(std::floor(multiplier_f)) + 1; - } - // The multiplier is a uint32. - ASSERT(multiplier > 0 && - multiplier < (static_cast(1) << 32)); - __ mov(scratch, dividend); - if (divisor < 0 && - instr->hydrogen()->CheckFlag(HValue::kBailoutOnMinusZero)) { + // Check for (0 / -x) that will produce negative zero. + HMathFloorOfDiv* hdiv = instr->hydrogen(); + if (hdiv->CheckFlag(HValue::kBailoutOnMinusZero) && + hdiv->left()->RangeCanInclude(0) && divisor < 0) { __ test(dividend, dividend); DeoptimizeIf(zero, instr->environment()); } - __ mov(edx, static_cast(multiplier)); - __ imul(edx); - if (static_cast(multiplier) < 0) { - __ add(edx, scratch); - } - Register reg_lo = eax; - Register reg_byte_scratch = scratch; - if (!reg_byte_scratch.is_byte_register()) { - __ xchg(reg_lo, reg_byte_scratch); - reg_lo = scratch; - reg_byte_scratch = eax; - } - if (divisor < 0) { - __ xor_(reg_byte_scratch, reg_byte_scratch); - __ cmp(reg_lo, 0x40000000); - __ setcc(above, reg_byte_scratch); - __ neg(edx); - __ sub(edx, reg_byte_scratch); - } else { - __ xor_(reg_byte_scratch, reg_byte_scratch); - __ cmp(reg_lo, 0xC0000000); - __ setcc(above_equal, reg_byte_scratch); - __ add(edx, reg_byte_scratch); - } - __ sar(edx, shift - 32); + + __ FlooringDiv(dividend, divisor); } diff --git a/src/ia32/lithium-ia32.cc b/src/ia32/lithium-ia32.cc index b513f85..c4ad7e8 100644 --- a/src/ia32/lithium-ia32.cc +++ b/src/ia32/lithium-ia32.cc @@ -1340,6 +1340,26 @@ LInstruction* LChunkBuilder::DoDivByPowerOf2I(HDiv* instr) { } +LInstruction* LChunkBuilder::DoDivByConstI(HDiv* instr) { + ASSERT(instr->representation().IsInteger32()); + ASSERT(instr->left()->representation().Equals(instr->representation())); + ASSERT(instr->right()->representation().Equals(instr->representation())); + LOperand* dividend = UseRegister(instr->left()); + int32_t divisor = instr->right()->GetInteger32Constant(); + LOperand* temp1 = FixedTemp(eax); + LOperand* temp2 = FixedTemp(edx); + LInstruction* result = + DefineFixed( + new(zone()) LDivByConstI(dividend, divisor, temp1, temp2), edx); + bool can_deopt = + divisor == 0 || + (instr->CheckFlag(HValue::kBailoutOnMinusZero) && + instr->left()->RangeCanInclude(0) && divisor < 0) || + !instr->CheckFlag(HInstruction::kAllUsesTruncatingToInt32); + return can_deopt ? AssignEnvironment(result) : result; +} + + LInstruction* LChunkBuilder::DoDivI(HBinaryOperation* instr) { ASSERT(instr->representation().IsSmiOrInteger32()); ASSERT(instr->left()->representation().Equals(instr->representation())); @@ -1347,14 +1367,21 @@ LInstruction* LChunkBuilder::DoDivI(HBinaryOperation* instr) { LOperand* dividend = UseFixed(instr->left(), eax); LOperand* divisor = UseRegister(instr->right()); LOperand* temp = FixedTemp(edx); - LDivI* result = new(zone()) LDivI(dividend, divisor, temp); - return AssignEnvironment(DefineFixed(result, eax)); + LInstruction* result = + DefineFixed(new(zone()) LDivI(dividend, divisor, temp), eax); + return AssignEnvironment(result); } LInstruction* LChunkBuilder::DoDiv(HDiv* instr) { if (instr->representation().IsSmiOrInteger32()) { - return instr->RightIsPowerOf2() ? DoDivByPowerOf2I(instr) : DoDivI(instr); + if (instr->RightIsPowerOf2()) { + return DoDivByPowerOf2I(instr); + } else if (instr->right()->IsConstant()) { + return DoDivByConstI(instr); + } else { + return DoDivI(instr); + } } else if (instr->representation().IsDouble()) { return DoArithmeticD(Token::DIV, instr); } else { @@ -1376,13 +1403,23 @@ LInstruction* LChunkBuilder::DoFlooringDivByPowerOf2I(HMathFloorOfDiv* instr) { LInstruction* LChunkBuilder::DoFlooringDivByConstI(HMathFloorOfDiv* instr) { - LOperand* dividend = UseFixed(instr->left(), eax); + ASSERT(instr->representation().IsInteger32()); + ASSERT(instr->left()->representation().Equals(instr->representation())); + ASSERT(instr->right()->representation().Equals(instr->representation())); + LOperand* dividend = UseRegister(instr->left()); int32_t divisor = instr->right()->GetInteger32Constant(); - LOperand* temp = TempRegister(); + LOperand* temp1 = FixedTemp(eax); + LOperand* temp2 = FixedTemp(edx); LInstruction* result = - DefineFixed( - new(zone()) LFlooringDivByConstI(dividend, divisor, temp), edx); - bool can_deopt = divisor <= 0; + DefineFixed(new(zone()) LFlooringDivByConstI(dividend, + divisor, + temp1, + temp2), + edx); + bool can_deopt = + divisor == 0 || + (instr->CheckFlag(HValue::kBailoutOnMinusZero) && + instr->left()->RangeCanInclude(0) && divisor < 0); return can_deopt ? AssignEnvironment(result) : result; } @@ -1413,6 +1450,25 @@ LInstruction* LChunkBuilder::DoModByPowerOf2I(HMod* instr) { } +LInstruction* LChunkBuilder::DoModByConstI(HMod* instr) { + ASSERT(instr->representation().IsSmiOrInteger32()); + ASSERT(instr->left()->representation().Equals(instr->representation())); + ASSERT(instr->right()->representation().Equals(instr->representation())); + LOperand* dividend = UseRegister(instr->left()); + int32_t divisor = instr->right()->GetInteger32Constant(); + LOperand* temp1 = FixedTemp(eax); + LOperand* temp2 = FixedTemp(edx); + LInstruction* result = + DefineFixed( + new(zone()) LModByConstI(dividend, divisor, temp1, temp2), eax); + bool can_deopt = + divisor == 0 || + (instr->CheckFlag(HValue::kBailoutOnMinusZero) && + instr->left()->CanBeNegative()); + return can_deopt ? AssignEnvironment(result) : result; +} + + LInstruction* LChunkBuilder::DoModI(HMod* instr) { ASSERT(instr->representation().IsSmiOrInteger32()); ASSERT(instr->left()->representation().Equals(instr->representation())); @@ -1435,7 +1491,13 @@ LInstruction* LChunkBuilder::DoModI(HMod* instr) { LInstruction* LChunkBuilder::DoMod(HMod* instr) { if (instr->representation().IsSmiOrInteger32()) { - return instr->RightIsPowerOf2() ? DoModByPowerOf2I(instr) : DoModI(instr); + if (instr->RightIsPowerOf2()) { + return DoModByPowerOf2I(instr); + } else if (instr->right()->IsConstant()) { + return DoModByConstI(instr); + } else { + return DoModI(instr); + } } else if (instr->representation().IsDouble()) { return DoArithmeticD(Token::MOD, instr); } else { diff --git a/src/ia32/lithium-ia32.h b/src/ia32/lithium-ia32.h index 03144b2..ac9cffa 100644 --- a/src/ia32/lithium-ia32.h +++ b/src/ia32/lithium-ia32.h @@ -88,6 +88,7 @@ class LCodeGen; V(DebugBreak) \ V(DeclareGlobals) \ V(Deoptimize) \ + V(DivByConstI) \ V(DivByPowerOf2I) \ V(DivI) \ V(DoubleBits) \ @@ -139,6 +140,7 @@ class LCodeGen; V(MathPowHalf) \ V(MathRound) \ V(MathSqrt) \ + V(ModByConstI) \ V(ModByPowerOf2I) \ V(ModI) \ V(MulI) \ @@ -657,6 +659,31 @@ class LModByPowerOf2I V8_FINAL : public LTemplateInstruction<1, 1, 0> { }; +class LModByConstI V8_FINAL : public LTemplateInstruction<1, 1, 2> { + public: + LModByConstI(LOperand* dividend, + int32_t divisor, + LOperand* temp1, + LOperand* temp2) { + inputs_[0] = dividend; + divisor_ = divisor; + temps_[0] = temp1; + temps_[1] = temp2; + } + + LOperand* dividend() { return inputs_[0]; } + int32_t divisor() const { return divisor_; } + LOperand* temp1() { return temps_[0]; } + LOperand* temp2() { return temps_[1]; } + + DECLARE_CONCRETE_INSTRUCTION(ModByConstI, "mod-by-const-i") + DECLARE_HYDROGEN_ACCESSOR(Mod) + + private: + int32_t divisor_; +}; + + class LModI V8_FINAL : public LTemplateInstruction<1, 2, 1> { public: LModI(LOperand* left, LOperand* right, LOperand* temp) { @@ -692,6 +719,31 @@ class LDivByPowerOf2I V8_FINAL : public LTemplateInstruction<1, 1, 0> { }; +class LDivByConstI V8_FINAL : public LTemplateInstruction<1, 1, 2> { + public: + LDivByConstI(LOperand* dividend, + int32_t divisor, + LOperand* temp1, + LOperand* temp2) { + inputs_[0] = dividend; + divisor_ = divisor; + temps_[0] = temp1; + temps_[1] = temp2; + } + + LOperand* dividend() { return inputs_[0]; } + int32_t divisor() const { return divisor_; } + LOperand* temp1() { return temps_[0]; } + LOperand* temp2() { return temps_[1]; } + + DECLARE_CONCRETE_INSTRUCTION(DivByConstI, "div-by-const-i") + DECLARE_HYDROGEN_ACCESSOR(Div) + + private: + int32_t divisor_; +}; + + class LDivI V8_FINAL : public LTemplateInstruction<1, 2, 1> { public: LDivI(LOperand* left, LOperand* right, LOperand* temp) { @@ -730,17 +782,22 @@ class LFlooringDivByPowerOf2I V8_FINAL : public LTemplateInstruction<1, 1, 0> { }; -class LFlooringDivByConstI V8_FINAL : public LTemplateInstruction<1, 1, 1> { +class LFlooringDivByConstI V8_FINAL : public LTemplateInstruction<1, 1, 2> { public: - LFlooringDivByConstI(LOperand* dividend, int32_t divisor, LOperand* temp) { + LFlooringDivByConstI(LOperand* dividend, + int32_t divisor, + LOperand* temp1, + LOperand* temp2) { inputs_[0] = dividend; divisor_ = divisor; - temps_[0] = temp; + temps_[0] = temp1; + temps_[1] = temp2; } LOperand* dividend() { return inputs_[0]; } int32_t divisor() const { return divisor_; } - LOperand* temp() { return temps_[0]; } + LOperand* temp1() { return temps_[0]; } + LOperand* temp2() { return temps_[1]; } DECLARE_CONCRETE_INSTRUCTION(FlooringDivByConstI, "flooring-div-by-const-i") DECLARE_HYDROGEN_ACCESSOR(MathFloorOfDiv) @@ -2720,8 +2777,10 @@ class LChunkBuilder V8_FINAL : public LChunkBuilderBase { LInstruction* DoMathPowHalf(HUnaryMathOperation* instr); LInstruction* DoMathClz32(HUnaryMathOperation* instr); LInstruction* DoDivByPowerOf2I(HDiv* instr); + LInstruction* DoDivByConstI(HDiv* instr); LInstruction* DoDivI(HBinaryOperation* instr); LInstruction* DoModByPowerOf2I(HMod* instr); + LInstruction* DoModByConstI(HMod* instr); LInstruction* DoModI(HMod* instr); LInstruction* DoFlooringDivByPowerOf2I(HMathFloorOfDiv* instr); LInstruction* DoFlooringDivByConstI(HMathFloorOfDiv* instr); diff --git a/src/ia32/macro-assembler-ia32.cc b/src/ia32/macro-assembler-ia32.cc index cc0f392..2e5b835 100644 --- a/src/ia32/macro-assembler-ia32.cc +++ b/src/ia32/macro-assembler-ia32.cc @@ -3603,6 +3603,19 @@ void MacroAssembler::JumpIfDictionaryInPrototypeChain( j(not_equal, &loop_again); } + +void MacroAssembler::FlooringDiv(Register dividend, int32_t divisor) { + ASSERT(!dividend.is(eax)); + ASSERT(!dividend.is(edx)); + MultiplierAndShift ms(divisor); + mov(eax, Immediate(ms.multiplier())); + imul(dividend); + if (divisor > 0 && ms.multiplier() < 0) add(edx, dividend); + if (divisor < 0 && ms.multiplier() > 0) sub(edx, dividend); + if (ms.shift() > 0) sar(edx, ms.shift()); +} + + } } // namespace v8::internal #endif // V8_TARGET_ARCH_IA32 diff --git a/src/ia32/macro-assembler-ia32.h b/src/ia32/macro-assembler-ia32.h index 6b0573c..dafa65d 100644 --- a/src/ia32/macro-assembler-ia32.h +++ b/src/ia32/macro-assembler-ia32.h @@ -855,6 +855,10 @@ class MacroAssembler: public Assembler { // Insert code to verify that the x87 stack has the specified depth (0-7) void VerifyX87StackDepth(uint32_t depth); + // Emit code for a flooring division by a constant. The dividend register is + // unchanged, the result is in edx, and eax gets clobbered. + void FlooringDiv(Register dividend, int32_t divisor); + // --------------------------------------------------------------------------- // StatsCounter support diff --git a/src/utils.cc b/src/utils.cc index 8462615..6838cb0 100644 --- a/src/utils.cc +++ b/src/utils.cc @@ -97,18 +97,4 @@ char* SimpleStringBuilder::Finalize() { } -const DivMagicNumbers DivMagicNumberFor(int32_t divisor) { - switch (divisor) { - case 3: return DivMagicNumberFor3; - case 5: return DivMagicNumberFor5; - case 7: return DivMagicNumberFor7; - case 9: return DivMagicNumberFor9; - case 11: return DivMagicNumberFor11; - case 25: return DivMagicNumberFor25; - case 125: return DivMagicNumberFor125; - case 625: return DivMagicNumberFor625; - default: return InvalidDivMagicNumber; - } -} - } } // namespace v8::internal diff --git a/src/utils.h b/src/utils.h index a20e209..7538226 100644 --- a/src/utils.h +++ b/src/utils.h @@ -105,32 +105,6 @@ inline int MostSignificantBit(uint32_t x) { } -// Magic numbers for integer division. -// These are kind of 2's complement reciprocal of the 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. -// See details in the implementation of the algorithm in -// lithium-codegen-arm.cc : LCodeGen::TryEmitSignedIntegerDivisionByConstant(). -struct DivMagicNumbers { - unsigned M; - unsigned s; -}; - -const DivMagicNumbers InvalidDivMagicNumber= {0, 0}; -const DivMagicNumbers DivMagicNumberFor3 = {0x55555556, 0}; -const DivMagicNumbers DivMagicNumberFor5 = {0x66666667, 1}; -const DivMagicNumbers DivMagicNumberFor7 = {0x92492493, 2}; -const DivMagicNumbers DivMagicNumberFor9 = {0x38e38e39, 1}; -const DivMagicNumbers DivMagicNumberFor11 = {0x2e8ba2e9, 1}; -const DivMagicNumbers DivMagicNumberFor25 = {0x51eb851f, 3}; -const DivMagicNumbers DivMagicNumberFor125 = {0x10624dd3, 3}; -const DivMagicNumbers DivMagicNumberFor625 = {0x68db8bad, 8}; - -const DivMagicNumbers DivMagicNumberFor(int32_t divisor); - - // The C++ standard leaves the semantics of '>>' undefined for // negative signed operands. Most implementations do the right thing, // though. diff --git a/src/x64/assembler-x64.cc b/src/x64/assembler-x64.cc index 63f0533..8ca37d4 100644 --- a/src/x64/assembler-x64.cc +++ b/src/x64/assembler-x64.cc @@ -1065,6 +1065,14 @@ void Assembler::imul(Register dst, Register src, Immediate imm) { } +void Assembler::imull(Register src) { + EnsureSpace ensure_space(this); + emit_optional_rex_32(src); + emit(0xF7); + emit_modrm(0x5, src); +} + + void Assembler::imull(Register dst, Register src) { EnsureSpace ensure_space(this); emit_optional_rex_32(dst, src); diff --git a/src/x64/assembler-x64.h b/src/x64/assembler-x64.h index b1b50c0..4214249 100644 --- a/src/x64/assembler-x64.h +++ b/src/x64/assembler-x64.h @@ -937,6 +937,7 @@ class Assembler : public AssemblerBase { void imul(Register dst, const Operand& src); // dst = dst * src. void imul(Register dst, Register src, Immediate imm); // dst = src * imm. // Signed 32-bit multiply instructions. + void imull(Register src); // edx:eax = eax * src. void imull(Register dst, Register src); // dst = dst * src. void imull(Register dst, const Operand& src); // dst = dst * src. void imull(Register dst, Register src, Immediate imm); // dst = src * imm. diff --git a/src/x64/lithium-codegen-x64.cc b/src/x64/lithium-codegen-x64.cc index 4dc9d4a..1b6a97b 100644 --- a/src/x64/lithium-codegen-x64.cc +++ b/src/x64/lithium-codegen-x64.cc @@ -1016,6 +1016,37 @@ void LCodeGen::DoModByPowerOf2I(LModByPowerOf2I* instr) { } +void LCodeGen::DoModByConstI(LModByConstI* instr) { + Register dividend = ToRegister(instr->dividend()); + int32_t divisor = instr->divisor(); + ASSERT(ToRegister(instr->result()).is(rax)); + + if (divisor == 0) { + DeoptimizeIf(no_condition, instr->environment()); + return; + } + + __ FlooringDiv(dividend, Abs(divisor)); + __ movl(rax, dividend); + __ shrl(rax, Immediate(31)); + __ addl(rdx, rax); + __ imull(rdx, rdx, Immediate(Abs(divisor))); + __ movl(rax, dividend); + __ subl(rax, rdx); + + // Check for negative zero. + HMod* hmod = instr->hydrogen(); + if (hmod->CheckFlag(HValue::kBailoutOnMinusZero) && + hmod->left()->CanBeNegative()) { + Label remainder_not_zero; + __ j(not_zero, &remainder_not_zero, Label::kNear); + __ cmpl(dividend, Immediate(0)); + DeoptimizeIf(less, instr->environment()); + __ bind(&remainder_not_zero); + } +} + + void LCodeGen::DoModI(LModI* instr) { if (instr->hydrogen()->RightIsPowerOf2()) { return DoModByPowerOf2I(reinterpret_cast(instr)); @@ -1119,42 +1150,22 @@ void LCodeGen::DoFlooringDivByPowerOf2I(LFlooringDivByPowerOf2I* instr) { void LCodeGen::DoFlooringDivByConstI(LFlooringDivByConstI* instr) { Register dividend = ToRegister(instr->dividend()); int32_t divisor = instr->divisor(); - Register temp = ToRegister(instr->temp()); - Register result = ToRegister(instr->result()); + ASSERT(ToRegister(instr->result()).is(rdx)); if (divisor == 0) { DeoptimizeIf(no_condition, instr->environment()); return; } - // Find b which: 2^b < divisor_abs < 2^(b+1). - uint32_t divisor_abs = abs(divisor); - unsigned b = 31 - CompilerIntrinsics::CountLeadingZeros(divisor_abs); - unsigned shift = 32 + b; // Precision +1bit (effectively). - double multiplier_f = - static_cast(static_cast(1) << shift) / divisor_abs; - int64_t multiplier; - if (multiplier_f - std::floor(multiplier_f) < 0.5) { - multiplier = static_cast(std::floor(multiplier_f)); - } else { - multiplier = static_cast(std::floor(multiplier_f)) + 1; - } - // The multiplier is a uint32. - ASSERT(multiplier > 0 && - multiplier < (static_cast(1) << 32)); - // The multiply is int64, so sign-extend to r64. - __ movsxlq(temp, dividend); - if (divisor < 0 && - instr->hydrogen()->CheckFlag(HValue::kBailoutOnMinusZero)) { - __ neg(temp); + // Check for (0 / -x) that will produce negative zero. + HMathFloorOfDiv* hdiv = instr->hydrogen(); + if (hdiv->CheckFlag(HValue::kBailoutOnMinusZero) && + hdiv->left()->RangeCanInclude(0) && divisor < 0) { + __ testl(dividend, dividend); DeoptimizeIf(zero, instr->environment()); } - __ Set(result, multiplier); - // Result just fit in r64, because it's int32 * uint32. - __ imul(result, temp); - __ addq(result, Immediate(1 << 30)); - __ sar(result, Immediate(shift)); + __ FlooringDiv(dividend, divisor); } @@ -1198,6 +1209,39 @@ void LCodeGen::DoDivByPowerOf2I(LDivByPowerOf2I* instr) { } +void LCodeGen::DoDivByConstI(LDivByConstI* instr) { + Register dividend = ToRegister(instr->dividend()); + int32_t divisor = instr->divisor(); + ASSERT(ToRegister(instr->result()).is(rdx)); + + if (divisor == 0) { + DeoptimizeIf(no_condition, instr->environment()); + return; + } + + // Check for (0 / -x) that will produce negative zero. + HDiv* hdiv = instr->hydrogen(); + if (hdiv->CheckFlag(HValue::kBailoutOnMinusZero) && + hdiv->left()->RangeCanInclude(0) && divisor < 0) { + __ testl(dividend, dividend); + DeoptimizeIf(zero, instr->environment()); + } + + __ FlooringDiv(dividend, Abs(divisor)); + __ movl(rax, dividend); + __ shrl(rax, Immediate(31)); + __ addl(rdx, rax); + if (divisor < 0) __ neg(rdx); + + if (!hdiv->CheckFlag(HInstruction::kAllUsesTruncatingToInt32)) { + __ movl(rax, rdx); + __ imull(rax, rax, Immediate(divisor)); + __ subl(rax, dividend); + DeoptimizeIf(not_equal, instr->environment()); + } +} + + void LCodeGen::DoDivI(LDivI* instr) { Register dividend = ToRegister(instr->left()); Register divisor = ToRegister(instr->right()); diff --git a/src/x64/lithium-x64.cc b/src/x64/lithium-x64.cc index 27001ab..74390e6 100644 --- a/src/x64/lithium-x64.cc +++ b/src/x64/lithium-x64.cc @@ -1261,6 +1261,26 @@ LInstruction* LChunkBuilder::DoDivByPowerOf2I(HDiv* instr) { } +LInstruction* LChunkBuilder::DoDivByConstI(HDiv* instr) { + ASSERT(instr->representation().IsInteger32()); + ASSERT(instr->left()->representation().Equals(instr->representation())); + ASSERT(instr->right()->representation().Equals(instr->representation())); + LOperand* dividend = UseRegister(instr->left()); + int32_t divisor = instr->right()->GetInteger32Constant(); + LOperand* temp1 = FixedTemp(rax); + LOperand* temp2 = FixedTemp(rdx); + LInstruction* result = + DefineFixed( + new(zone()) LDivByConstI(dividend, divisor, temp1, temp2), rdx); + bool can_deopt = + divisor == 0 || + (instr->CheckFlag(HValue::kBailoutOnMinusZero) && + instr->left()->RangeCanInclude(0) && divisor < 0) || + !instr->CheckFlag(HInstruction::kAllUsesTruncatingToInt32); + return can_deopt ? AssignEnvironment(result) : result; +} + + LInstruction* LChunkBuilder::DoDivI(HBinaryOperation* instr) { ASSERT(instr->representation().IsSmiOrInteger32()); ASSERT(instr->left()->representation().Equals(instr->representation())); @@ -1276,7 +1296,13 @@ LInstruction* LChunkBuilder::DoDivI(HBinaryOperation* instr) { LInstruction* LChunkBuilder::DoDiv(HDiv* instr) { if (instr->representation().IsSmiOrInteger32()) { - return instr->RightIsPowerOf2() ? DoDivByPowerOf2I(instr) : DoDivI(instr); + if (instr->RightIsPowerOf2()) { + return DoDivByPowerOf2I(instr); + } else if (instr->right()->IsConstant()) { + return DoDivByConstI(instr); + } else { + return DoDivI(instr); + } } else if (instr->representation().IsDouble()) { return DoArithmeticD(Token::DIV, instr); } else { @@ -1298,13 +1324,23 @@ LInstruction* LChunkBuilder::DoFlooringDivByPowerOf2I(HMathFloorOfDiv* instr) { LInstruction* LChunkBuilder::DoFlooringDivByConstI(HMathFloorOfDiv* instr) { - LOperand* dividend = UseRegisterAtStart(instr->left()); + ASSERT(instr->representation().IsInteger32()); + ASSERT(instr->left()->representation().Equals(instr->representation())); + ASSERT(instr->right()->representation().Equals(instr->representation())); + LOperand* dividend = UseRegister(instr->left()); int32_t divisor = instr->right()->GetInteger32Constant(); - LOperand* temp = TempRegister(); + LOperand* temp1 = FixedTemp(rax); + LOperand* temp2 = FixedTemp(rdx); LInstruction* result = - DefineAsRegister( - new(zone()) LFlooringDivByConstI(dividend, divisor, temp)); - bool can_deopt = divisor <= 0; + DefineFixed(new(zone()) LFlooringDivByConstI(dividend, + divisor, + temp1, + temp2), + rdx); + bool can_deopt = + divisor == 0 || + (instr->CheckFlag(HValue::kBailoutOnMinusZero) && + instr->left()->RangeCanInclude(0) && divisor < 0); return can_deopt ? AssignEnvironment(result) : result; } @@ -1335,6 +1371,25 @@ LInstruction* LChunkBuilder::DoModByPowerOf2I(HMod* instr) { } +LInstruction* LChunkBuilder::DoModByConstI(HMod* instr) { + ASSERT(instr->representation().IsSmiOrInteger32()); + ASSERT(instr->left()->representation().Equals(instr->representation())); + ASSERT(instr->right()->representation().Equals(instr->representation())); + LOperand* dividend = UseRegister(instr->left()); + int32_t divisor = instr->right()->GetInteger32Constant(); + LOperand* temp1 = FixedTemp(rax); + LOperand* temp2 = FixedTemp(rdx); + LInstruction* result = + DefineFixed( + new(zone()) LModByConstI(dividend, divisor, temp1, temp2), rax); + bool can_deopt = + divisor == 0 || + (instr->CheckFlag(HValue::kBailoutOnMinusZero) && + instr->left()->CanBeNegative()); + return can_deopt ? AssignEnvironment(result) : result; +} + + LInstruction* LChunkBuilder::DoModI(HMod* instr) { ASSERT(instr->representation().IsSmiOrInteger32()); ASSERT(instr->left()->representation().Equals(instr->representation())); @@ -1357,7 +1412,13 @@ LInstruction* LChunkBuilder::DoModI(HMod* instr) { LInstruction* LChunkBuilder::DoMod(HMod* instr) { if (instr->representation().IsSmiOrInteger32()) { - return instr->RightIsPowerOf2() ? DoModByPowerOf2I(instr) : DoModI(instr); + if (instr->RightIsPowerOf2()) { + return DoModByPowerOf2I(instr); + } else if (instr->right()->IsConstant()) { + return DoModByConstI(instr); + } else { + return DoModI(instr); + } } else if (instr->representation().IsDouble()) { return DoArithmeticD(Token::MOD, instr); } else { diff --git a/src/x64/lithium-x64.h b/src/x64/lithium-x64.h index c6a6850..4df350d 100644 --- a/src/x64/lithium-x64.h +++ b/src/x64/lithium-x64.h @@ -86,6 +86,7 @@ class LCodeGen; V(DebugBreak) \ V(DeclareGlobals) \ V(Deoptimize) \ + V(DivByConstI) \ V(DivByPowerOf2I) \ V(DivI) \ V(DoubleBits) \ @@ -137,6 +138,7 @@ class LCodeGen; V(MathPowHalf) \ V(MathRound) \ V(MathSqrt) \ + V(ModByConstI) \ V(ModByPowerOf2I) \ V(ModI) \ V(MulI) \ @@ -638,6 +640,31 @@ class LModByPowerOf2I V8_FINAL : public LTemplateInstruction<1, 1, 0> { }; +class LModByConstI V8_FINAL : public LTemplateInstruction<1, 1, 2> { + public: + LModByConstI(LOperand* dividend, + int32_t divisor, + LOperand* temp1, + LOperand* temp2) { + inputs_[0] = dividend; + divisor_ = divisor; + temps_[0] = temp1; + temps_[1] = temp2; + } + + LOperand* dividend() { return inputs_[0]; } + int32_t divisor() const { return divisor_; } + LOperand* temp1() { return temps_[0]; } + LOperand* temp2() { return temps_[1]; } + + DECLARE_CONCRETE_INSTRUCTION(ModByConstI, "mod-by-const-i") + DECLARE_HYDROGEN_ACCESSOR(Mod) + + private: + int32_t divisor_; +}; + + class LModI V8_FINAL : public LTemplateInstruction<1, 2, 1> { public: LModI(LOperand* left, LOperand* right, LOperand* temp) { @@ -673,6 +700,31 @@ class LDivByPowerOf2I V8_FINAL : public LTemplateInstruction<1, 1, 0> { }; +class LDivByConstI V8_FINAL : public LTemplateInstruction<1, 1, 2> { + public: + LDivByConstI(LOperand* dividend, + int32_t divisor, + LOperand* temp1, + LOperand* temp2) { + inputs_[0] = dividend; + divisor_ = divisor; + temps_[0] = temp1; + temps_[1] = temp2; + } + + LOperand* dividend() { return inputs_[0]; } + int32_t divisor() const { return divisor_; } + LOperand* temp1() { return temps_[0]; } + LOperand* temp2() { return temps_[1]; } + + DECLARE_CONCRETE_INSTRUCTION(DivByConstI, "div-by-const-i") + DECLARE_HYDROGEN_ACCESSOR(Div) + + private: + int32_t divisor_; +}; + + class LDivI V8_FINAL : public LTemplateInstruction<1, 2, 1> { public: LDivI(LOperand* left, LOperand* right, LOperand* temp) { @@ -711,17 +763,22 @@ class LFlooringDivByPowerOf2I V8_FINAL : public LTemplateInstruction<1, 1, 0> { }; -class LFlooringDivByConstI V8_FINAL : public LTemplateInstruction<1, 1, 1> { +class LFlooringDivByConstI V8_FINAL : public LTemplateInstruction<1, 1, 2> { public: - LFlooringDivByConstI(LOperand* dividend, int32_t divisor, LOperand* temp) { + LFlooringDivByConstI(LOperand* dividend, + int32_t divisor, + LOperand* temp1, + LOperand* temp2) { inputs_[0] = dividend; divisor_ = divisor; - temps_[0] = temp; + temps_[0] = temp1; + temps_[1] = temp2; } LOperand* dividend() { return inputs_[0]; } int32_t divisor() const { return divisor_; } - LOperand* temp() { return temps_[0]; } + LOperand* temp1() { return temps_[0]; } + LOperand* temp2() { return temps_[0]; } DECLARE_CONCRETE_INSTRUCTION(FlooringDivByConstI, "flooring-div-by-const-i") DECLARE_HYDROGEN_ACCESSOR(MathFloorOfDiv) @@ -2634,8 +2691,10 @@ class LChunkBuilder V8_FINAL : public LChunkBuilderBase { LInstruction* DoMathPowHalf(HUnaryMathOperation* instr); LInstruction* DoMathClz32(HUnaryMathOperation* instr); LInstruction* DoDivByPowerOf2I(HDiv* instr); + LInstruction* DoDivByConstI(HDiv* instr); LInstruction* DoDivI(HBinaryOperation* instr); LInstruction* DoModByPowerOf2I(HMod* instr); + LInstruction* DoModByConstI(HMod* instr); LInstruction* DoModI(HMod* instr); LInstruction* DoFlooringDivByPowerOf2I(HMathFloorOfDiv* instr); LInstruction* DoFlooringDivByConstI(HMathFloorOfDiv* instr); diff --git a/src/x64/macro-assembler-x64.cc b/src/x64/macro-assembler-x64.cc index 95f1724..3191199 100644 --- a/src/x64/macro-assembler-x64.cc +++ b/src/x64/macro-assembler-x64.cc @@ -4979,6 +4979,18 @@ void MacroAssembler::JumpIfDictionaryInPrototypeChain( } +void MacroAssembler::FlooringDiv(Register dividend, int32_t divisor) { + ASSERT(!dividend.is(rax)); + ASSERT(!dividend.is(rdx)); + MultiplierAndShift ms(divisor); + movl(rax, Immediate(ms.multiplier())); + imull(dividend); + if (divisor > 0 && ms.multiplier() < 0) addl(rdx, dividend); + if (divisor < 0 && ms.multiplier() > 0) subl(rdx, dividend); + if (ms.shift() > 0) sarl(rdx, Immediate(ms.shift())); +} + + } } // namespace v8::internal #endif // V8_TARGET_ARCH_X64 diff --git a/src/x64/macro-assembler-x64.h b/src/x64/macro-assembler-x64.h index 63cf9c5..c72f0db 100644 --- a/src/x64/macro-assembler-x64.h +++ b/src/x64/macro-assembler-x64.h @@ -1363,6 +1363,10 @@ class MacroAssembler: public Assembler { Register filler); + // Emit code for a flooring division by a constant. The dividend register is + // unchanged, the result is in rdx, and rax gets clobbered. + void FlooringDiv(Register dividend, int32_t divisor); + // --------------------------------------------------------------------------- // StatsCounter support diff --git a/test/mjsunit/math-floor-of-div.js b/test/mjsunit/math-floor-of-div.js index d528b85..707f657 100644 --- a/test/mjsunit/math-floor-of-div.js +++ b/test/mjsunit/math-floor-of-div.js @@ -286,3 +286,14 @@ test_div_deopt_div_by_zero_v(); test_div_deopt_minus_zero_v(); test_div_deopt_overflow_v(); test_div_deopt_div_by_zero_v(); + + +// Test for flooring division with negative dividend. +function flooring_div_by_3(y) { + return Math.floor(y / 3); +} + +assertEquals(-1, flooring_div_by_3(-2)); +assertEquals(-1, flooring_div_by_3(-2)); +%OptimizeFunctionOnNextCall(flooring_div_by_3); +assertEquals(-1, flooring_div_by_3(-2)); -- 2.7.4