From e4f4aad2d13f87278b770674600d64612a51169a Mon Sep 17 00:00:00 2001 From: "yangguo@chromium.org" Date: Wed, 20 Jun 2012 14:08:03 +0000 Subject: [PATCH] x86/x64 port of Math.floor(x/y) to use integer division for specific divisor. Only handles when x is int32 and y is int32 constant. BUG=v8:2038 Currently implemented by imul (not fpmul). x86 and x64 algorithm differs a bit. x86 implementation is kind of cumbersome, but I couldn't think of better ways. Review URL: https://chromiumcodereview.appspot.com/10382033 Patch from Zheng Liu . git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@11887 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/hydrogen-instructions.cc | 10 ++- src/hydrogen-instructions.h | 3 + src/ia32/disasm-ia32.cc | 1 + src/ia32/lithium-codegen-ia32.cc | 103 +++++++++++++++++++++++++++ src/ia32/lithium-ia32.cc | 49 ++++++++++++- src/ia32/lithium-ia32.h | 19 +++++ src/x64/disasm-x64.cc | 3 + src/x64/lithium-codegen-x64.cc | 83 +++++++++++++++++++++ src/x64/lithium-x64.cc | 47 +++++++++++- src/x64/lithium-x64.h | 19 +++++ test/mjsunit/math-floor-of-div-minus-zero.js | 40 +++++++++++ test/mjsunit/mjsunit.status | 3 + 12 files changed, 375 insertions(+), 5 deletions(-) create mode 100644 test/mjsunit/math-floor-of-div-minus-zero.js diff --git a/src/hydrogen-instructions.cc b/src/hydrogen-instructions.cc index 4bb2509..d44e90a 100644 --- a/src/hydrogen-instructions.cc +++ b/src/hydrogen-instructions.cc @@ -941,7 +941,8 @@ HValue* HUnaryMathOperation::Canonicalize() { // introduced. if (value()->representation().IsInteger32()) return value(); -#ifdef V8_TARGET_ARCH_ARM +#if defined(V8_TARGET_ARCH_ARM) || defined(V8_TARGET_ARCH_IA32) || \ + defined(V8_TARGET_ARCH_X64) if (value()->IsDiv() && (value()->UseCount() == 1)) { // TODO(2038): Implement this optimization for non ARM architectures. HDiv* hdiv = HDiv::cast(value()); @@ -2223,6 +2224,13 @@ HValue* HDiv::EnsureAndPropagateNotMinusZero(BitVector* visited) { } +HValue* HMathFloorOfDiv::EnsureAndPropagateNotMinusZero(BitVector* visited) { + visited->Add(id()); + SetFlag(kBailoutOnMinusZero); + return NULL; +} + + HValue* HMul::EnsureAndPropagateNotMinusZero(BitVector* visited) { visited->Add(id()); if (range() == NULL || range()->CanBeMinusZero()) { diff --git a/src/hydrogen-instructions.h b/src/hydrogen-instructions.h index 0920024..e0c443a 100644 --- a/src/hydrogen-instructions.h +++ b/src/hydrogen-instructions.h @@ -2774,8 +2774,11 @@ class HMathFloorOfDiv: public HBinaryOperation { : HBinaryOperation(context, left, right) { set_representation(Representation::Integer32()); SetFlag(kUseGVN); + SetFlag(kCanOverflow); } + virtual HValue* EnsureAndPropagateNotMinusZero(BitVector* visited); + virtual Representation RequiredInputRepresentation(int index) { return Representation::Integer32(); } diff --git a/src/ia32/disasm-ia32.cc b/src/ia32/disasm-ia32.cc index b5ddcca..412bdaf 100644 --- a/src/ia32/disasm-ia32.cc +++ b/src/ia32/disasm-ia32.cc @@ -553,6 +553,7 @@ int DisassemblerIA32::F7Instruction(byte* data) { case 2: mnem = "not"; break; case 3: mnem = "neg"; break; case 4: mnem = "mul"; break; + case 5: mnem = "imul"; break; case 7: mnem = "idiv"; break; default: UnimplementedInstruction(); } diff --git a/src/ia32/lithium-codegen-ia32.cc b/src/ia32/lithium-codegen-ia32.cc index a1a5482..abac964 100644 --- a/src/ia32/lithium-codegen-ia32.cc +++ b/src/ia32/lithium-codegen-ia32.cc @@ -1022,6 +1022,109 @@ void LCodeGen::DoDivI(LDivI* instr) { } +void LCodeGen::DoMathFloorOfDiv(LMathFloorOfDiv* instr) { + ASSERT(instr->InputAt(1)->IsConstantOperand()); + + Register dividend = ToRegister(instr->InputAt(0)); + int32_t divisor = ToInteger32(LConstantOperand::cast(instr->InputAt(1))); + Register result = ToRegister(instr->result()); + + switch (divisor) { + case 0: + DeoptimizeIf(no_condition, instr->environment()); + return; + + case 1: + __ Move(result, dividend); + return; + + case -1: + __ Move(result, dividend); + __ neg(result); + if (instr->hydrogen()->CheckFlag(HValue::kBailoutOnMinusZero)) { + DeoptimizeIf(zero, instr->environment()); + } + if (instr->hydrogen()->CheckFlag(HValue::kCanOverflow)) { + DeoptimizeIf(overflow, instr->environment()); + } + return; + } + + uint32_t divisor_abs = abs(divisor); + if (IsPowerOf2(divisor_abs)) { + int32_t power = WhichPowerOf2(divisor_abs); + if (divisor < 0) { + // Input[dividend] is clobbered. + // The sequence is tedious because neg(dividend) might overflow. + __ mov(result, dividend); + __ sar(dividend, 31); + __ neg(result); + if (instr->hydrogen()->CheckFlag(HValue::kBailoutOnMinusZero)) { + DeoptimizeIf(zero, instr->environment()); + } + __ shl(dividend, 32 - power); + __ sar(result, power); + __ not_(dividend); + // Clear result.sign if dividend.sign is set. + __ and_(result, dividend); + } else { + __ Move(result, dividend); + __ sar(result, power); + } + } else { + ASSERT(ToRegister(instr->InputAt(0)).is(eax)); + ASSERT(ToRegister(instr->result()).is(edx)); + Register scratch = ToRegister(instr->TempAt(0)); + + // Find b which: 2^b < divisor_abs < 2^(b+1). + 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 - floor(multiplier_f) < 0.5) { + multiplier = floor(multiplier_f); + } else { + multiplier = 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)) { + __ test(dividend, dividend); + DeoptimizeIf(zero, instr->environment()); + } + __ mov(edx, 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); + } +} + + void LCodeGen::DoMulI(LMulI* instr) { Register left = ToRegister(instr->InputAt(0)); LOperand* right = instr->InputAt(1); diff --git a/src/ia32/lithium-ia32.cc b/src/ia32/lithium-ia32.cc index 60366f7..c671e6d 100644 --- a/src/ia32/lithium-ia32.cc +++ b/src/ia32/lithium-ia32.cc @@ -1347,12 +1347,57 @@ LInstruction* LChunkBuilder::DoDiv(HDiv* instr) { } -LInstruction* LChunkBuilder::DoMathFloorOfDiv(HMathFloorOfDiv* instr) { - UNIMPLEMENTED(); +HValue* LChunkBuilder::SimplifiedDividendForMathFloorOfDiv(HValue* dividend) { + // A value with an integer representation does not need to be transformed. + if (dividend->representation().IsInteger32()) { + return dividend; + // A change from an integer32 can be replaced by the integer32 value. + } else if (dividend->IsChange() && + HChange::cast(dividend)->from().IsInteger32()) { + return HChange::cast(dividend)->value(); + } + return NULL; +} + + +HValue* LChunkBuilder::SimplifiedDivisorForMathFloorOfDiv(HValue* divisor) { + 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(); + ASSERT(right->IsConstant() && HConstant::cast(right)->HasInteger32Value()); + LOperand* divisor = chunk_->DefineConstantOperand(HConstant::cast(right)); + int32_t divisor_si = HConstant::cast(right)->Integer32Value(); + if (divisor_si == 0) { + LOperand* dividend = UseRegister(instr->left()); + return AssignEnvironment(DefineAsRegister( + new(zone()) LMathFloorOfDiv(dividend, divisor, NULL))); + } else if (IsPowerOf2(abs(divisor_si))) { + // use dividend as temp if divisor < 0 && divisor != -1 + LOperand* dividend = divisor_si < -1 ? UseTempRegister(instr->left()) : + UseRegisterAtStart(instr->left()); + LInstruction* result = DefineAsRegister( + new(zone()) LMathFloorOfDiv(dividend, divisor, NULL)); + return divisor_si < 0 ? AssignEnvironment(result) : result; + } else { + // needs edx:eax, plus a temp + LOperand* dividend = UseFixed(instr->left(), eax); + LOperand* temp = TempRegister(); + LInstruction* result = DefineFixed( + new(zone()) LMathFloorOfDiv(dividend, divisor, temp), edx); + return divisor_si < 0 ? AssignEnvironment(result) : result; + } +} + + LInstruction* LChunkBuilder::DoMod(HMod* instr) { if (instr->representation().IsInteger32()) { ASSERT(instr->left()->representation().IsInteger32()); diff --git a/src/ia32/lithium-ia32.h b/src/ia32/lithium-ia32.h index cd20631..bc7ef58 100644 --- a/src/ia32/lithium-ia32.h +++ b/src/ia32/lithium-ia32.h @@ -126,6 +126,7 @@ class LCodeGen; V(LoadNamedField) \ V(LoadNamedFieldPolymorphic) \ V(LoadNamedGeneric) \ + V(MathFloorOfDiv) \ V(MathPowHalf) \ V(ModI) \ V(MulI) \ @@ -546,6 +547,21 @@ class LDivI: public LTemplateInstruction<1, 2, 1> { }; +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; + } + + 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) { @@ -2399,6 +2415,9 @@ class LChunkBuilder BASE_EMBEDDED { HYDROGEN_CONCRETE_INSTRUCTION_LIST(DECLARE_DO) #undef DECLARE_DO + static HValue* SimplifiedDividendForMathFloorOfDiv(HValue* val); + static HValue* SimplifiedDivisorForMathFloorOfDiv(HValue* val); + private: enum Status { UNUSED, diff --git a/src/x64/disasm-x64.cc b/src/x64/disasm-x64.cc index 0738153..c8606c4 100644 --- a/src/x64/disasm-x64.cc +++ b/src/x64/disasm-x64.cc @@ -703,6 +703,9 @@ int DisassemblerX64::F6F7Instruction(byte* data) { case 4: mnem = "mul"; break; + case 5: + mnem = "imul"; + break; case 7: mnem = "idiv"; break; diff --git a/src/x64/lithium-codegen-x64.cc b/src/x64/lithium-codegen-x64.cc index 12d38fc..4f71f83 100644 --- a/src/x64/lithium-codegen-x64.cc +++ b/src/x64/lithium-codegen-x64.cc @@ -886,6 +886,89 @@ void LCodeGen::DoModI(LModI* instr) { } +void LCodeGen::DoMathFloorOfDiv(LMathFloorOfDiv* instr) { + ASSERT(instr->InputAt(1)->IsConstantOperand()); + + const Register dividend = ToRegister(instr->InputAt(0)); + int32_t divisor = ToInteger32(LConstantOperand::cast(instr->InputAt(1))); + const Register result = ToRegister(instr->result()); + + switch (divisor) { + case 0: + DeoptimizeIf(no_condition, instr->environment()); + return; + + case 1: + if (!result.is(dividend)) { + __ movl(result, dividend); + } + return; + + case -1: + if (!result.is(dividend)) { + __ movl(result, dividend); + } + __ negl(result); + if (instr->hydrogen()->CheckFlag(HValue::kBailoutOnMinusZero)) { + DeoptimizeIf(zero, instr->environment()); + } + if (instr->hydrogen()->CheckFlag(HValue::kCanOverflow)) { + DeoptimizeIf(overflow, instr->environment()); + } + return; + } + + uint32_t divisor_abs = abs(divisor); + if (IsPowerOf2(divisor_abs)) { + int32_t power = WhichPowerOf2(divisor_abs); + if (divisor < 0) { + __ movsxlq(result, dividend); + __ neg(result); + if (instr->hydrogen()->CheckFlag(HValue::kBailoutOnMinusZero)) { + DeoptimizeIf(zero, instr->environment()); + } + __ sar(result, Immediate(power)); + } else { + if (!result.is(dividend)) { + __ movl(result, dividend); + } + __ sarl(result, Immediate(power)); + } + } else { + Register reg1 = ToRegister(instr->TempAt(0)); + Register reg2 = ToRegister(instr->result()); + + // Find b which: 2^b < divisor_abs < 2^(b+1). + 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 - floor(multiplier_f) < 0.5) { + multiplier = floor(multiplier_f); + } else { + multiplier = 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(reg1, dividend); + if (divisor < 0 && + instr->hydrogen()->CheckFlag(HValue::kBailoutOnMinusZero)) { + __ neg(reg1); + DeoptimizeIf(zero, instr->environment()); + } + __ movq(reg2, multiplier, RelocInfo::NONE); + // Result just fit in r64, because it's int32 * uint32. + __ imul(reg2, reg1); + + __ addq(reg2, Immediate(1 << 30)); + __ sar(reg2, Immediate(shift)); + } +} + + void LCodeGen::DoDivI(LDivI* instr) { LOperand* right = instr->InputAt(1); ASSERT(ToRegister(instr->result()).is(rax)); diff --git a/src/x64/lithium-x64.cc b/src/x64/lithium-x64.cc index d06a6a4..642e951 100644 --- a/src/x64/lithium-x64.cc +++ b/src/x64/lithium-x64.cc @@ -1287,12 +1287,55 @@ LInstruction* LChunkBuilder::DoDiv(HDiv* instr) { } -LInstruction* LChunkBuilder::DoMathFloorOfDiv(HMathFloorOfDiv* instr) { - UNIMPLEMENTED(); +HValue* LChunkBuilder::SimplifiedDividendForMathFloorOfDiv(HValue* dividend) { + // A value with an integer representation does not need to be transformed. + if (dividend->representation().IsInteger32()) { + return dividend; + // A change from an integer32 can be replaced by the integer32 value. + } else if (dividend->IsChange() && + HChange::cast(dividend)->from().IsInteger32()) { + return HChange::cast(dividend)->value(); + } + return NULL; +} + + +HValue* LChunkBuilder::SimplifiedDivisorForMathFloorOfDiv(HValue* divisor) { + 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(); + ASSERT(right->IsConstant() && HConstant::cast(right)->HasInteger32Value()); + LOperand* divisor = chunk_->DefineConstantOperand(HConstant::cast(right)); + int32_t divisor_si = HConstant::cast(right)->Integer32Value(); + if (divisor_si == 0) { + LOperand* dividend = UseRegister(instr->left()); + return AssignEnvironment(DefineAsRegister( + new(zone()) LMathFloorOfDiv(dividend, divisor, NULL))); + } else if (IsPowerOf2(abs(divisor_si))) { + LOperand* dividend = UseRegisterAtStart(instr->left()); + LInstruction* result = DefineAsRegister( + new(zone()) LMathFloorOfDiv(dividend, divisor, NULL)); + return divisor_si < 0 ? AssignEnvironment(result) : result; + } else { + // use two r64 + LOperand* dividend = UseRegisterAtStart(instr->left()); + LOperand* temp = TempRegister(); + LInstruction* result = DefineAsRegister( + new(zone()) LMathFloorOfDiv(dividend, divisor, temp)); + return divisor_si < 0 ? AssignEnvironment(result) : result; + } +} + + LInstruction* LChunkBuilder::DoMod(HMod* instr) { if (instr->representation().IsInteger32()) { ASSERT(instr->left()->representation().IsInteger32()); diff --git a/src/x64/lithium-x64.h b/src/x64/lithium-x64.h index d038dda..a00867d 100644 --- a/src/x64/lithium-x64.h +++ b/src/x64/lithium-x64.h @@ -132,6 +132,7 @@ class LCodeGen; V(LoadNamedField) \ V(LoadNamedFieldPolymorphic) \ V(LoadNamedGeneric) \ + V(MathFloorOfDiv) \ V(ModI) \ V(MulI) \ V(NumberTagD) \ @@ -554,6 +555,21 @@ class LDivI: public LTemplateInstruction<1, 2, 1> { }; +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; + } + + DECLARE_CONCRETE_INSTRUCTION(MathFloorOfDiv, "math-floor-of-div") + DECLARE_HYDROGEN_ACCESSOR(MathFloorOfDiv) +}; + + class LMulI: public LTemplateInstruction<1, 2, 0> { public: LMulI(LOperand* left, LOperand* right) { @@ -2255,6 +2271,9 @@ class LChunkBuilder BASE_EMBEDDED { HYDROGEN_CONCRETE_INSTRUCTION_LIST(DECLARE_DO) #undef DECLARE_DO + static HValue* SimplifiedDividendForMathFloorOfDiv(HValue* val); + static HValue* SimplifiedDivisorForMathFloorOfDiv(HValue* val); + private: enum Status { UNUSED, diff --git a/test/mjsunit/math-floor-of-div-minus-zero.js b/test/mjsunit/math-floor-of-div-minus-zero.js new file mode 100644 index 0000000..9fbe9a9 --- /dev/null +++ b/test/mjsunit/math-floor-of-div-minus-zero.js @@ -0,0 +1,40 @@ +// Copyright 2012 the V8 project authors. All rights reserved. +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following +// disclaimer in the documentation and/or other materials provided +// with the distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived +// from this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +// Flags: --allow-natives-syntax --nouse_inlining + +// Test for negative zero that doesn't need bail out + +function test_div_no_deopt_minus_zero() { + var zero_in_array = [0]; + assertTrue(0 === (Math.floor((zero_in_array[0] | 0) / -1) | 0)); +} + +test_div_no_deopt_minus_zero(); +%OptimizeFunctionOnNextCall(test_div_no_deopt_minus_zero); +test_div_no_deopt_minus_zero(); +assertTrue(2 != %GetOptimizationStatus(test_div_no_deopt_minus_zero)); diff --git a/test/mjsunit/mjsunit.status b/test/mjsunit/mjsunit.status index b526d7f..03ed60f 100644 --- a/test/mjsunit/mjsunit.status +++ b/test/mjsunit/mjsunit.status @@ -126,6 +126,9 @@ debug-liveedit-check-stack: SKIP debug-liveedit-stack-padding: SKIP debug-liveedit-restart-frame: SKIP +# Currently always deopt on minus zero +math-floor-of-div-minus-zero: SKIP + ############################################################################## [ $arch == mips ] -- 2.7.4