x86/x64 port of Math.floor(x/y) to use integer division for specific divisor

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.

Committed: https://code.google.com/p/v8/source/detail?r=11887

[Zheng Liu, 2012-05-15 04:44:44]

On 2012/05/07 09:56:15, Zheng Liu wrote:

Could you please review this patch? Thanks.

[Zheng Liu, 2012-06-08 04:31:19]

Any update on this? Thanks.

Zheng Liu
zheng.z.liu@intel.com

[Yang, 2012-06-19 15:41:38]

I'm very sorry that this has taken this long. I had a look over it. This looks
good so far, but I have some comments.

Also, please rebase this CL, there has been some changes related to passing the
Zone explicitly.

http://codereview.chromium.org/10382033/diff/7011/src/ia32/lithium-codegen-ia...
File src/ia32/lithium-codegen-ia32.cc (right):

http://codereview.chromium.org/10382033/diff/7011/src/ia32/lithium-codegen-ia...
src/ia32/lithium-codegen-ia32.cc:985: // FIXME: set & check
HValue::kBailoutOnMinusZero
Is this going to be fixed?

http://codereview.chromium.org/10382033/diff/7011/src/ia32/lithium-codegen-ia...
src/ia32/lithium-codegen-ia32.cc:998: // tedious because neg(dividend) might
overflow
Comments should start with capital letter and end with a period.

Wouldn't neg only overflow for -2^31? Can't we simply deoptimize for this case
and do a simple neg for the rest?

http://codereview.chromium.org/10382033/diff/7011/src/ia32/lithium-codegen-ia...
src/ia32/lithium-codegen-ia32.cc:1021: double multiplier_f =
static_cast<double>((uint64_t)1 << shift)
Use static_cast please.

http://codereview.chromium.org/10382033/diff/7011/src/ia32/lithium-codegen-ia...
src/ia32/lithium-codegen-ia32.cc:1030: ASSERT(multiplier > 0 && multiplier <
((int64_t)1<<32));
Use static_cast please.

http://codereview.chromium.org/10382033/diff/7011/src/ia32/lithium-codegen-ia...
src/ia32/lithium-codegen-ia32.cc:1032: // FIXME: set & check
HValue::kBailoutOnMinusZero
Same here.

http://codereview.chromium.org/10382033/diff/7011/src/ia32/lithium-codegen-ia...
src/ia32/lithium-codegen-ia32.cc:1039: if ((int32_t)multiplier < 0) {
Use static_cast please.

http://codereview.chromium.org/10382033/diff/7011/src/x64/lithium-codegen-x64.cc
File src/x64/lithium-codegen-x64.cc (right):

http://codereview.chromium.org/10382033/diff/7011/src/x64/lithium-codegen-x64...
src/x64/lithium-codegen-x64.cc:908: // FIXME: set & check
HValue::kBailoutOnMinusZero
Any changes here?

http://codereview.chromium.org/10382033/diff/7011/src/x64/lithium-codegen-x64...
src/x64/lithium-codegen-x64.cc:922: // FIXME: set & check
HValue::kBailoutOnMinusZero
Ditto.

http://codereview.chromium.org/10382033/diff/7011/src/x64/lithium-codegen-x64...
src/x64/lithium-codegen-x64.cc:938: double multiplier_f =
static_cast<double>((uint64_t)1 << shift)
Use static_cast please.

http://codereview.chromium.org/10382033/diff/7011/src/x64/lithium-codegen-x64...
src/x64/lithium-codegen-x64.cc:947: ASSERT(multiplier > 0 && multiplier <
((int64_t)1<<32));
Use static_cast please.

http://codereview.chromium.org/10382033/diff/7011/src/x64/lithium-codegen-x64...
src/x64/lithium-codegen-x64.cc:952: // FIXME: set & check
HValue::kBailoutOnMinusZero
Ditto.

[Zheng Liu, 2012-06-20 09:14:29]

Rebased and comments addressed.

Also added a simple kBailoutOnMinusZero handling, please check it.
Apparently the "if(false)" in test should be enabled, but that would assert on
arm.

On 2012/06/19 15:41:38, Yang wrote:
> 
>
http://codereview.chromium.org/10382033/diff/7011/src/ia32/lithium-codegen-ia...
> src/ia32/lithium-codegen-ia32.cc:998: // tedious because neg(dividend) might
> overflow
> Comments should start with capital letter and end with a period.
> 
> Wouldn't neg only overflow for -2^31? Can't we simply deoptimize for this case
> and do a simple neg for the rest?
> 
I thought that other Int32 ops don't easily deoptimize on kMinInt, so I'd not
like to make it more fragile.
I'll change it if you do think it's too complex.

Thanks, Zheng Liu
zheng.z.liu@intel.com

[Yang, 2012-06-20 12:19:42]

I have still some comments, but I think after those are addressed, this CL is
good to be landed.

http://codereview.chromium.org/10382033/diff/16002/src/hydrogen-instructions.h
File src/hydrogen-instructions.h (right):

http://codereview.chromium.org/10382033/diff/16002/src/hydrogen-instructions....
src/hydrogen-instructions.h:2780: virtual HValue*
EnsureAndPropagateNotMinusZero(BitVector* visited) {
All implementations of EnsureAndPropagateNotMinusZero can be found in
hydrogen-instructions.cc around like 2200. Please only put the function header
here and move the implementation to hydrogen-instructions.cc like the others.

http://codereview.chromium.org/10382033/diff/16002/src/ia32/lithium-codegen-i...
File src/ia32/lithium-codegen-ia32.cc (right):

http://codereview.chromium.org/10382033/diff/16002/src/ia32/lithium-codegen-i...
src/ia32/lithium-codegen-ia32.cc:1058: // The sequence is tedious because
neg(dividend) might overflow.
I took a second look. Wouldn't we circumvent this problem if we simply divide
first and then negate? We would then observe three distinct cases (if divisor <
0):
- divisor is -1: we can simply do a NEG. Only if divident is kMinInt would NEG
overflow. We guard against this case first and deopt here, since we would
require a double representation for the result anyway (because (-kMinInt) >
kMaxInt). This case has already been dealt with in the switch!
- divisor is -2 or less, and divident is 0: we bail out if kBailoutOnMinusZero
is set, otherwise return 0.
- divisor is -2 or less, and divident is not 0: we calculate
divident/divisor_abs by shifting and set the sign with neg. We don't expect
overflow for neg because divident/divisor_abs cannot be kMinInt.

Did I overlook anything? With this, we don't clobber divident, so it doesn't
have to be reserved with UseTempRegister.

http://codereview.chromium.org/10382033/diff/16002/src/ia32/lithium-codegen-i...
src/ia32/lithium-codegen-ia32.cc:1080: unsigned b = 31 -
CompilerIntrinsics::CountLeadingZeros(divisor_abs);
I assume divisor_abs == divisor here? Maybe use the former here can avoid some
confusions.

http://codereview.chromium.org/10382033/diff/16002/test/mjsunit/math-floor-of...
File test/mjsunit/math-floor-of-div.js (right):

http://codereview.chromium.org/10382033/diff/16002/test/mjsunit/math-floor-of...
test/mjsunit/math-floor-of-div.js:217: 
Please create a new test file called math-floor-of-div-minus-zero.js, and add it
to mjsunit.status so that it is skipped on ARM and MIPS.

[Zheng Liu, 2012-06-20 13:54:15]

http://codereview.chromium.org/10382033/diff/16002/src/hydrogen-instructions.h
File src/hydrogen-instructions.h (right):

http://codereview.chromium.org/10382033/diff/16002/src/hydrogen-instructions....
src/hydrogen-instructions.h:2780: virtual HValue*
EnsureAndPropagateNotMinusZero(BitVector* visited) {
On 2012/06/20 12:19:42, Yang wrote:
> All implementations of EnsureAndPropagateNotMinusZero can be found in
> hydrogen-instructions.cc around like 2200. Please only put the function header
> here and move the implementation to hydrogen-instructions.cc like the others.

Done.

http://codereview.chromium.org/10382033/diff/16002/src/ia32/lithium-codegen-i...
File src/ia32/lithium-codegen-ia32.cc (right):

http://codereview.chromium.org/10382033/diff/16002/src/ia32/lithium-codegen-i...
src/ia32/lithium-codegen-ia32.cc:1058: // The sequence is tedious because
neg(dividend) might overflow.
On 2012/06/20 12:19:42, Yang wrote:
> I took a second look. Wouldn't we circumvent this problem if we simply divide
> first and then negate? We would then observe three distinct cases (if divisor
<
> 0):
> - divisor is -1: we can simply do a NEG. Only if divident is kMinInt would NEG
> overflow. We guard against this case first and deopt here, since we would
> require a double representation for the result anyway (because (-kMinInt) >
> kMaxInt). This case has already been dealt with in the switch!
> - divisor is -2 or less, and divident is 0: we bail out if kBailoutOnMinusZero
> is set, otherwise return 0.
> - divisor is -2 or less, and divident is not 0: we calculate
> divident/divisor_abs by shifting and set the sign with neg. We don't expect
> overflow for neg because divident/divisor_abs cannot be kMinInt.
> 
> Did I overlook anything? With this, we don't clobber divident, so it doesn't
> have to be reserved with UseTempRegister.

As a floor() op, it's not symmetric around zero.
e.g. Math.floor(1/-4) => -1

http://codereview.chromium.org/10382033/diff/16002/src/ia32/lithium-codegen-i...
src/ia32/lithium-codegen-ia32.cc:1080: unsigned b = 31 -
CompilerIntrinsics::CountLeadingZeros(divisor_abs);
On 2012/06/20 12:19:42, Yang wrote:
> I assume divisor_abs == divisor here? Maybe use the former here can avoid some
> confusions.

Here abs(divisor) is not-power-of-two. divisor could be negative.

http://codereview.chromium.org/10382033/diff/16002/test/mjsunit/math-floor-of...
File test/mjsunit/math-floor-of-div.js (right):

http://codereview.chromium.org/10382033/diff/16002/test/mjsunit/math-floor-of...
test/mjsunit/math-floor-of-div.js:217: 
On 2012/06/20 12:19:42, Yang wrote:
> Please create a new test file called math-floor-of-div-minus-zero.js, and add
it
> to mjsunit.status so that it is skipped on ARM and MIPS.

Done.

[Yang, 2012-06-20 13:59:23]

On 2012/06/20 13:54:15, Zheng Liu wrote:
> http://codereview.chromium.org/10382033/diff/16002/src/hydrogen-instructions.h
> File src/hydrogen-instructions.h (right):
> 
>
http://codereview.chromium.org/10382033/diff/16002/src/hydrogen-instructions....
> src/hydrogen-instructions.h:2780: virtual HValue*
> EnsureAndPropagateNotMinusZero(BitVector* visited) {
> On 2012/06/20 12:19:42, Yang wrote:
> > All implementations of EnsureAndPropagateNotMinusZero can be found in
> > hydrogen-instructions.cc around like 2200. Please only put the function
header
> > here and move the implementation to hydrogen-instructions.cc like the
others.
> 
> Done.
> 
>
http://codereview.chromium.org/10382033/diff/16002/src/ia32/lithium-codegen-i...
> File src/ia32/lithium-codegen-ia32.cc (right):
> 
>
http://codereview.chromium.org/10382033/diff/16002/src/ia32/lithium-codegen-i...
> src/ia32/lithium-codegen-ia32.cc:1058: // The sequence is tedious because
> neg(dividend) might overflow.
> On 2012/06/20 12:19:42, Yang wrote:
> > I took a second look. Wouldn't we circumvent this problem if we simply
divide
> > first and then negate? We would then observe three distinct cases (if
divisor
> <
> > 0):
> > - divisor is -1: we can simply do a NEG. Only if divident is kMinInt would
NEG
> > overflow. We guard against this case first and deopt here, since we would
> > require a double representation for the result anyway (because (-kMinInt) >
> > kMaxInt). This case has already been dealt with in the switch!
> > - divisor is -2 or less, and divident is 0: we bail out if
kBailoutOnMinusZero
> > is set, otherwise return 0.
> > - divisor is -2 or less, and divident is not 0: we calculate
> > divident/divisor_abs by shifting and set the sign with neg. We don't expect
> > overflow for neg because divident/divisor_abs cannot be kMinInt.
> > 
> > Did I overlook anything? With this, we don't clobber divident, so it doesn't
> > have to be reserved with UseTempRegister.
> 
> As a floor() op, it's not symmetric around zero.
> e.g. Math.floor(1/-4) => -1
> 
>
http://codereview.chromium.org/10382033/diff/16002/src/ia32/lithium-codegen-i...
> src/ia32/lithium-codegen-ia32.cc:1080: unsigned b = 31 -
> CompilerIntrinsics::CountLeadingZeros(divisor_abs);
> On 2012/06/20 12:19:42, Yang wrote:
> > I assume divisor_abs == divisor here? Maybe use the former here can avoid
some
> > confusions.
> 
> Here abs(divisor) is not-power-of-two. divisor could be negative.
> 
>
http://codereview.chromium.org/10382033/diff/16002/test/mjsunit/math-floor-of...
> File test/mjsunit/math-floor-of-div.js (right):
> 
>
http://codereview.chromium.org/10382033/diff/16002/test/mjsunit/math-floor-of...
> test/mjsunit/math-floor-of-div.js:217: 
> On 2012/06/20 12:19:42, Yang wrote:
> > Please create a new test file called math-floor-of-div-minus-zero.js, and
add
> it
> > to mjsunit.status so that it is skipped on ARM and MIPS.
> 
> Done.

I see. LGTM. I'll land this CL. Thanks for sticking with me.