Revision: 13178
Author: [email protected]
Date: Mon Dec 10 03:02:22 2012
Log: Improve integer division on IA32 and X64
If the divisor is a Power-of-2 constant, we could use shifts instead of the
expensive idiv instructions, which also loose the register constraints.
Review URL: https://chromiumcodereview.appspot.com/11478043
Patch from Yuqiang Xian <[email protected]>.
http://code.google.com/p/v8/source/detail?r=13178
Added:
/branches/bleeding_edge/test/mjsunit/shift-for-integer-div.js
Modified:
/branches/bleeding_edge/src/hydrogen-instructions.h
/branches/bleeding_edge/src/ia32/lithium-codegen-ia32.cc
/branches/bleeding_edge/src/ia32/lithium-ia32.cc
/branches/bleeding_edge/src/x64/lithium-codegen-x64.cc
/branches/bleeding_edge/src/x64/lithium-x64.cc
=======================================
--- /dev/null
+++ /branches/bleeding_edge/test/mjsunit/shift-for-integer-div.js Mon Dec
10 03:02:22 2012
@@ -0,0 +1,59 @@
+// 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.
+
+function divp4(x) {
+ return x / 4;
+}
+
+for (var i = 0; i < 10000; i+=4) {
+ assertEquals(i >> 2, divp4(i));
+}
+
+assertEquals(0.5, divp4(2));
+
+function divn4(x) {
+ return x / (-4);
+}
+
+for (var i = 0; i < 10000; i+=4) {
+ assertEquals(-(i >> 2), divn4(i));
+}
+
+assertEquals(-0, divn4(0));
+
+
+function divn1(x) {
+ return x / (-1);
+}
+
+for (var i = 0; i < 10000; i++) {
+ assertEquals(-i, divn1(i));
+}
+
+var min_int = -(0x7FFFFFFF)-1;
+assertEquals(-min_int, divn1(min_int));
+
=======================================
--- /branches/bleeding_edge/src/hydrogen-instructions.h Mon Dec 10 00:56:24
2012
+++ /branches/bleeding_edge/src/hydrogen-instructions.h Mon Dec 10 03:02:22
2012
@@ -3682,6 +3682,16 @@
SetFlag(kCanBeDivByZero);
SetFlag(kCanOverflow);
}
+
+ bool HasPowerOf2Divisor() {
+ if (right()->IsConstant() &&
+ HConstant::cast(right())->HasInteger32Value()) {
+ int32_t value = HConstant::cast(right())->Integer32Value();
+ return value != 0 && (IsPowerOf2(value) || IsPowerOf2(-value));
+ }
+
+ return false;
+ }
virtual HValue* EnsureAndPropagateNotMinusZero(BitVector* visited);
=======================================
--- /branches/bleeding_edge/src/ia32/lithium-codegen-ia32.cc Wed Dec 5
07:49:22 2012
+++ /branches/bleeding_edge/src/ia32/lithium-codegen-ia32.cc Mon Dec 10
03:02:22 2012
@@ -1201,6 +1201,43 @@
void LCodeGen::DoDivI(LDivI* instr) {
+ if (instr->hydrogen()->HasPowerOf2Divisor()) {
+ Register dividend = ToRegister(instr->left());
+ int32_t divisor =
+ HConstant::cast(instr->hydrogen()->right())->Integer32Value();
+ int32_t test_value = 0;
+ int32_t power = 0;
+
+ if (divisor > 0) {
+ test_value = divisor - 1;
+ power = WhichPowerOf2(divisor);
+ } else {
+ // Check for (0 / -x) that will produce negative zero.
+ if (instr->hydrogen()->CheckFlag(HValue::kBailoutOnMinusZero)) {
+ __ test(dividend, Operand(dividend));
+ DeoptimizeIf(zero, instr->environment());
+ }
+ // Check for (kMinInt / -1).
+ if (divisor == -1 &&
instr->hydrogen()->CheckFlag(HValue::kCanOverflow)) {
+ __ cmp(dividend, kMinInt);
+ DeoptimizeIf(zero, instr->environment());
+ }
+ test_value = - divisor - 1;
+ power = WhichPowerOf2(-divisor);
+ }
+
+ if (test_value != 0) {
+ // Deoptimize if remainder is not 0.
+ __ test(dividend, Immediate(test_value));
+ DeoptimizeIf(not_zero, instr->environment());
+ __ sar(dividend, power);
+ }
+
+ if (divisor < 0) __ neg(dividend);
+
+ return;
+ }
+
LOperand* right = instr->right();
ASSERT(ToRegister(instr->result()).is(eax));
ASSERT(ToRegister(instr->left()).is(eax));
@@ -1226,7 +1263,7 @@
__ bind(&left_not_zero);
}
- // Check for (-kMinInt / -1).
+ // Check for (kMinInt / -1).
if (instr->hydrogen()->CheckFlag(HValue::kCanOverflow)) {
Label left_not_min_int;
__ cmp(left_reg, kMinInt);
=======================================
--- /branches/bleeding_edge/src/ia32/lithium-ia32.cc Wed Dec 5 08:16:32
2012
+++ /branches/bleeding_edge/src/ia32/lithium-ia32.cc Mon Dec 10 03:02:22
2012
@@ -1264,6 +1264,13 @@
if (instr->representation().IsDouble()) {
return DoArithmeticD(Token::DIV, instr);
} else if (instr->representation().IsInteger32()) {
+ if (instr->HasPowerOf2Divisor()) {
+ ASSERT(!instr->CheckFlag(HValue::kCanBeDivByZero));
+ LOperand* value = UseRegisterAtStart(instr->left());
+ LDivI* div =
+ new(zone()) LDivI(value, UseOrConstant(instr->right()), NULL);
+ return AssignEnvironment(DefineSameAsFirst(div));
+ }
// The temporary operand is necessary to ensure that right is not
allocated
// into edx.
LOperand* temp = FixedTemp(edx);
=======================================
--- /branches/bleeding_edge/src/x64/lithium-codegen-x64.cc Wed Dec 5
07:49:22 2012
+++ /branches/bleeding_edge/src/x64/lithium-codegen-x64.cc Mon Dec 10
03:02:22 2012
@@ -1133,6 +1133,43 @@
void LCodeGen::DoDivI(LDivI* instr) {
+ if (instr->hydrogen()->HasPowerOf2Divisor()) {
+ Register dividend = ToRegister(instr->left());
+ int32_t divisor =
+ HConstant::cast(instr->hydrogen()->right())->Integer32Value();
+ int32_t test_value = 0;
+ int32_t power = 0;
+
+ if (divisor > 0) {
+ test_value = divisor - 1;
+ power = WhichPowerOf2(divisor);
+ } else {
+ // Check for (0 / -x) that will produce negative zero.
+ if (instr->hydrogen()->CheckFlag(HValue::kBailoutOnMinusZero)) {
+ __ testl(dividend, dividend);
+ DeoptimizeIf(zero, instr->environment());
+ }
+ // Check for (kMinInt / -1).
+ if (divisor == -1 &&
instr->hydrogen()->CheckFlag(HValue::kCanOverflow)) {
+ __ cmpl(dividend, Immediate(kMinInt));
+ DeoptimizeIf(zero, instr->environment());
+ }
+ test_value = - divisor - 1;
+ power = WhichPowerOf2(-divisor);
+ }
+
+ if (test_value != 0) {
+ // Deoptimize if remainder is not 0.
+ __ testl(dividend, Immediate(test_value));
+ DeoptimizeIf(not_zero, instr->environment());
+ __ sarl(dividend, Immediate(power));
+ }
+
+ if (divisor < 0) __ negl(dividend);
+
+ return;
+ }
+
LOperand* right = instr->right();
ASSERT(ToRegister(instr->result()).is(rax));
ASSERT(ToRegister(instr->left()).is(rax));
@@ -1158,7 +1195,7 @@
__ bind(&left_not_zero);
}
- // Check for (-kMinInt / -1).
+ // Check for (kMinInt / -1).
if (instr->hydrogen()->CheckFlag(HValue::kCanOverflow)) {
Label left_not_min_int;
__ cmpl(left_reg, Immediate(kMinInt));
=======================================
--- /branches/bleeding_edge/src/x64/lithium-x64.cc Wed Dec 5 08:16:32 2012
+++ /branches/bleeding_edge/src/x64/lithium-x64.cc Mon Dec 10 03:02:22 2012
@@ -1187,6 +1187,13 @@
if (instr->representation().IsDouble()) {
return DoArithmeticD(Token::DIV, instr);
} else if (instr->representation().IsInteger32()) {
+ if (instr->HasPowerOf2Divisor()) {
+ ASSERT(!instr->CheckFlag(HValue::kCanBeDivByZero));
+ LOperand* value = UseRegisterAtStart(instr->left());
+ LDivI* div =
+ new(zone()) LDivI(value, UseOrConstant(instr->right()), NULL);
+ return AssignEnvironment(DefineSameAsFirst(div));
+ }
// The temporary operand is necessary to ensure that right is not
allocated
// into rdx.
LOperand* temp = FixedTemp(rdx);
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
