Revision: 11887
Author: [email protected]
Date: Wed Jun 20 07:08:03 2012
Log: 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 <[email protected]>.
http://code.google.com/p/v8/source/detail?r=11887
Added:
/branches/bleeding_edge/test/mjsunit/math-floor-of-div-minus-zero.js
Modified:
/branches/bleeding_edge/src/hydrogen-instructions.cc
/branches/bleeding_edge/src/hydrogen-instructions.h
/branches/bleeding_edge/src/ia32/disasm-ia32.cc
/branches/bleeding_edge/src/ia32/lithium-codegen-ia32.cc
/branches/bleeding_edge/src/ia32/lithium-ia32.cc
/branches/bleeding_edge/src/ia32/lithium-ia32.h
/branches/bleeding_edge/src/x64/disasm-x64.cc
/branches/bleeding_edge/src/x64/lithium-codegen-x64.cc
/branches/bleeding_edge/src/x64/lithium-x64.cc
/branches/bleeding_edge/src/x64/lithium-x64.h
/branches/bleeding_edge/test/mjsunit/mjsunit.status
=======================================
--- /dev/null
+++ /branches/bleeding_edge/test/mjsunit/math-floor-of-div-minus-zero.js
Wed Jun 20 07:08:03 2012
@@ -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));
=======================================
--- /branches/bleeding_edge/src/hydrogen-instructions.cc Tue Jun 12
08:44:12 2012
+++ /branches/bleeding_edge/src/hydrogen-instructions.cc Wed Jun 20
07:08:03 2012
@@ -941,7 +941,8 @@
// 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());
@@ -2221,6 +2222,13 @@
}
return NULL;
}
+
+
+HValue* HMathFloorOfDiv::EnsureAndPropagateNotMinusZero(BitVector*
visited) {
+ visited->Add(id());
+ SetFlag(kBailoutOnMinusZero);
+ return NULL;
+}
HValue* HMul::EnsureAndPropagateNotMinusZero(BitVector* visited) {
=======================================
--- /branches/bleeding_edge/src/hydrogen-instructions.h Thu Jun 14 07:06:22
2012
+++ /branches/bleeding_edge/src/hydrogen-instructions.h Wed Jun 20 07:08:03
2012
@@ -2774,7 +2774,10 @@
: 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();
=======================================
--- /branches/bleeding_edge/src/ia32/disasm-ia32.cc Fri Dec 2 02:05:20 2011
+++ /branches/bleeding_edge/src/ia32/disasm-ia32.cc Wed Jun 20 07:08:03 2012
@@ -553,6 +553,7 @@
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();
}
=======================================
--- /branches/bleeding_edge/src/ia32/lithium-codegen-ia32.cc Wed Jun 20
06:40:10 2012
+++ /branches/bleeding_edge/src/ia32/lithium-codegen-ia32.cc Wed Jun 20
07:08:03 2012
@@ -1020,6 +1020,109 @@
__ test(edx, Operand(edx));
DeoptimizeIf(not_zero, instr->environment());
}
+
+
+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<double>(static_cast<uint64_t>(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<int64_t>(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<int32_t>(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) {
=======================================
--- /branches/bleeding_edge/src/ia32/lithium-ia32.cc Tue Jun 12 05:16:19
2012
+++ /branches/bleeding_edge/src/ia32/lithium-ia32.cc Wed Jun 20 07:08:03
2012
@@ -1347,10 +1347,55 @@
}
-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) {
=======================================
--- /branches/bleeding_edge/src/ia32/lithium-ia32.h Tue Jun 12 03:22:33 2012
+++ /branches/bleeding_edge/src/ia32/lithium-ia32.h Wed Jun 20 07:08:03 2012
@@ -126,6 +126,7 @@
V(LoadNamedField) \
V(LoadNamedFieldPolymorphic) \
V(LoadNamedGeneric) \
+ V(MathFloorOfDiv) \
V(MathPowHalf) \
V(ModI) \
V(MulI) \
@@ -546,6 +547,21 @@
};
+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 @@
HYDROGEN_CONCRETE_INSTRUCTION_LIST(DECLARE_DO)
#undef DECLARE_DO
+ static HValue* SimplifiedDividendForMathFloorOfDiv(HValue* val);
+ static HValue* SimplifiedDivisorForMathFloorOfDiv(HValue* val);
+
private:
enum Status {
UNUSED,
=======================================
--- /branches/bleeding_edge/src/x64/disasm-x64.cc Mon May 21 02:59:28 2012
+++ /branches/bleeding_edge/src/x64/disasm-x64.cc Wed Jun 20 07:08:03 2012
@@ -703,6 +703,9 @@
case 4:
mnem = "mul";
break;
+ case 5:
+ mnem = "imul";
+ break;
case 7:
mnem = "idiv";
break;
=======================================
--- /branches/bleeding_edge/src/x64/lithium-codegen-x64.cc Wed Jun 20
06:40:10 2012
+++ /branches/bleeding_edge/src/x64/lithium-codegen-x64.cc Wed Jun 20
07:08:03 2012
@@ -884,6 +884,89 @@
__ bind(&done);
}
}
+
+
+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<double>(static_cast<uint64_t>(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<int64_t>(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) {
=======================================
--- /branches/bleeding_edge/src/x64/lithium-x64.cc Tue Jun 12 05:16:19 2012
+++ /branches/bleeding_edge/src/x64/lithium-x64.cc Wed Jun 20 07:08:03 2012
@@ -1287,10 +1287,53 @@
}
-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) {
=======================================
--- /branches/bleeding_edge/src/x64/lithium-x64.h Mon Jun 11 05:42:31 2012
+++ /branches/bleeding_edge/src/x64/lithium-x64.h Wed Jun 20 07:08:03 2012
@@ -132,6 +132,7 @@
V(LoadNamedField) \
V(LoadNamedFieldPolymorphic) \
V(LoadNamedGeneric) \
+ V(MathFloorOfDiv) \
V(ModI) \
V(MulI) \
V(NumberTagD) \
@@ -554,6 +555,21 @@
};
+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 @@
HYDROGEN_CONCRETE_INSTRUCTION_LIST(DECLARE_DO)
#undef DECLARE_DO
+ static HValue* SimplifiedDividendForMathFloorOfDiv(HValue* val);
+ static HValue* SimplifiedDivisorForMathFloorOfDiv(HValue* val);
+
private:
enum Status {
UNUSED,
=======================================
--- /branches/bleeding_edge/test/mjsunit/mjsunit.status Sat Jun 16 14:40:35
2012
+++ /branches/bleeding_edge/test/mjsunit/mjsunit.status Wed Jun 20 07:08:03
2012
@@ -126,6 +126,9 @@
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 ]
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
