[v8-dev] Optimise Math.floor(x/y) to use integer division for specific divisor....

Optimise Math.floor(x/y) to use integer division for specific divisor.

BUG=none
TEST=mjsunit/math-floor-of-div.js

Landing for Rodolph Perfetta <rodolph.perfetta@gmail.com>;.
Committed: https://code.google.com/p/v8/source/detail?r=11420

[Rodolph Perfetta, 2012-03-08 16:59:07]

This supercedes our "optimise bitwise operations" patch.

[danno, 2012-03-09 11:39:09]

Adding Florian, who should review this

[fschneider, 2012-03-20 10:27:39]

On 2012/03/09 11:39:09, danno wrote:
> Adding Florian, who should review this

I did not forget about this, but currently have a large backlog of code reviews
and open issues. Will have a look soon.

[fschneider, 2012-03-28 09:59:18]

Sorry for the long delay. Here are my comments: The approach looks good.

http://codereview.chromium.org/9638018/diff/1/src/arm/lithium-codegen-arm.cc
File src/arm/lithium-codegen-arm.cc (right):

http://codereview.chromium.org/9638018/diff/1/src/arm/lithium-codegen-arm.cc#...
src/arm/lithium-codegen-arm.cc:1047: bool compute_remainder =
remainder.is_valid();
Isn't remainder always a temp-register and compute_remainder always true in
here? In this case you could simplify the code a bit.

http://codereview.chromium.org/9638018/diff/1/src/arm/macro-assembler-arm.cc
File src/arm/macro-assembler-arm.cc (right):

http://codereview.chromium.org/9638018/diff/1/src/arm/macro-assembler-arm.cc#...
src/arm/macro-assembler-arm.cc:3712: 
#ifdef DEBUG

http://codereview.chromium.org/9638018/diff/1/src/arm/macro-assembler-arm.cc#...
src/arm/macro-assembler-arm.cc:3733: 
#endif  // DEBUG

http://codereview.chromium.org/9638018/diff/1/src/arm/macro-assembler-arm.h
File src/arm/macro-assembler-arm.h (right):

http://codereview.chromium.org/9638018/diff/1/src/arm/macro-assembler-arm.h#n...
src/arm/macro-assembler-arm.h:88: bool AreAliased(Register reg1,
If this is only used in ASSERTs you can put it inside a

#ifdef DEBUG

http://codereview.chromium.org/9638018/diff/1/src/hydrogen-instructions.cc
File src/hydrogen-instructions.cc (right):

http://codereview.chromium.org/9638018/diff/1/src/hydrogen-instructions.cc#ne...
src/hydrogen-instructions.cc:917: if (value()->IsDiv() &&
LChunkBuilder::SupportsMathFloorOfDiv()) {
The function SupportsMathFloorDiv is essentially like writing

#ifdef V8_TARGET_ARCH_ARM

Maybe just put this part under the #ifdef and add a TODO(issue#) to add this for
other platforms.

e.g. Math.floor(x/4) can also be optimized for ia32.

http://codereview.chromium.org/9638018/diff/1/src/hydrogen-instructions.cc#ne...
src/hydrogen-instructions.cc:946: // If the division had no other uses than this
HMathFloor, delete it.
Not sure how often the division acutally has other uses, but I'd prefer to
simplify the code here to restrict the optimization to the pattern
Math.floor(a/b) where the division has exactly one use.

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

http://codereview.chromium.org/9638018/diff/1/src/hydrogen-instructions.h#new...
src/hydrogen-instructions.h:2654:
set_representation(Representation::Integer32());
I think you can make GVN handle this instruction by setting the flag

SetFlag(kUseGVN)

and implementing the DataEquals-function like for other arithmetic operations.
In this case DataEquals would just return true.

http://codereview.chromium.org/9638018/diff/1/src/ia32/lithium-ia32.h
File src/ia32/lithium-ia32.h (right):

http://codereview.chromium.org/9638018/diff/1/src/ia32/lithium-ia32.h#newcode...
src/ia32/lithium-ia32.h:2344: static bool SupportsMathFloorOfDiv() { return
false; }
I'd add those function only when we add this optimization to ia32. By using a
#ifdef in hydrogen-instructions.cc for the time being we can avoid adding unused
code to the other platforms.

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

http://codereview.chromium.org/9638018/diff/1/test/mjsunit/math-floor-of-div....
test/mjsunit/math-floor-of-div.js:52: for (var l = 0; l <= limit; l++) {
Maybe use a different letter (j, k?), since 1 and l look to similar.

http://codereview.chromium.org/9638018/diff/1/test/mjsunit/math-floor-of-div....
test/mjsunit/math-floor-of-div.js:54: assertEquals(Math.floor(div(l,   1)),
Math.floor(l /   1)); assertEquals(Math.floor(div(l,   -1)), Math.floor(l /  
-1));

Please break the line at 80 chars.

[Alexandre, 2012-03-28 16:27:38]

Thanks for the review.
I addressed your comments and created an issue (2038) for the implementation for
other archs.
http://code.google.com/p/v8/issues/detail?id=2038

The updated patch should be uploaded soon.

Alexandre

http://codereview.chromium.org/9638018/diff/1/src/arm/lithium-codegen-arm.cc
File src/arm/lithium-codegen-arm.cc (right):

http://codereview.chromium.org/9638018/diff/1/src/arm/lithium-codegen-arm.cc#...
src/arm/lithium-codegen-arm.cc:1047: bool compute_remainder =
remainder.is_valid();
Done.

This mechanism can be reintroduced if  further optimizations do not require to
compute the remainder.

On 2012/03/28 09:59:18, fschneider wrote:
> Isn't remainder always a temp-register and compute_remainder always true in
> here? In this case you could simplify the code a bit.

http://codereview.chromium.org/9638018/diff/1/src/arm/macro-assembler-arm.cc
File src/arm/macro-assembler-arm.cc (right):

http://codereview.chromium.org/9638018/diff/1/src/arm/macro-assembler-arm.cc#...
src/arm/macro-assembler-arm.cc:3712: 
On 2012/03/28 09:59:18, fschneider wrote:
> #ifdef DEBUG

Done.

http://codereview.chromium.org/9638018/diff/1/src/arm/macro-assembler-arm.cc#...
src/arm/macro-assembler-arm.cc:3733: 
On 2012/03/28 09:59:18, fschneider wrote:
> #endif  // DEBUG

Done.

http://codereview.chromium.org/9638018/diff/1/src/arm/macro-assembler-arm.h
File src/arm/macro-assembler-arm.h (right):

http://codereview.chromium.org/9638018/diff/1/src/arm/macro-assembler-arm.h#n...
src/arm/macro-assembler-arm.h:88: bool AreAliased(Register reg1,
On 2012/03/28 09:59:18, fschneider wrote:
> If this is only used in ASSERTs you can put it inside a
> 
> #ifdef DEBUG

Done.

http://codereview.chromium.org/9638018/diff/1/src/hydrogen-instructions.cc
File src/hydrogen-instructions.cc (right):

http://codereview.chromium.org/9638018/diff/1/src/hydrogen-instructions.cc#ne...
src/hydrogen-instructions.cc:917: if (value()->IsDiv() &&
LChunkBuilder::SupportsMathFloorOfDiv()) {
On 2012/03/28 09:59:18, fschneider wrote:
> The function SupportsMathFloorDiv is essentially like writing
> 
> #ifdef V8_TARGET_ARCH_ARM
> 
> Maybe just put this part under the #ifdef and add a TODO(issue#) to add this
for
> other platforms.
> 
> e.g. Math.floor(x/4) can also be optimized for ia32.

Done.

http://codereview.chromium.org/9638018/diff/1/src/hydrogen-instructions.cc#ne...
src/hydrogen-instructions.cc:946: // If the division had no other uses than this
HMathFloor, delete it.
On 2012/03/28 09:59:18, fschneider wrote:
> Not sure how often the division acutally has other uses, but I'd prefer to
> simplify the code here to restrict the optimization to the pattern
> Math.floor(a/b) where the division has exactly one use.

Done.

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

http://codereview.chromium.org/9638018/diff/1/src/hydrogen-instructions.h#new...
src/hydrogen-instructions.h:2654:
set_representation(Representation::Integer32());
On 2012/03/28 09:59:18, fschneider wrote:
> I think you can make GVN handle this instruction by setting the flag
> 
> SetFlag(kUseGVN)
> 
> and implementing the DataEquals-function like for other arithmetic operations.
> In this case DataEquals would just return true.

Done.

http://codereview.chromium.org/9638018/diff/1/src/ia32/lithium-ia32.h
File src/ia32/lithium-ia32.h (right):

http://codereview.chromium.org/9638018/diff/1/src/ia32/lithium-ia32.h#newcode...
src/ia32/lithium-ia32.h:2344: static bool SupportsMathFloorOfDiv() { return
false; }
On 2012/03/28 09:59:18, fschneider wrote:
> I'd add those function only when we add this optimization to ia32. By using a
> #ifdef in hydrogen-instructions.cc for the time being we can avoid adding
unused
> code to the other platforms.

Done.

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

http://codereview.chromium.org/9638018/diff/1/test/mjsunit/math-floor-of-div....
test/mjsunit/math-floor-of-div.js:52: for (var l = 0; l <= limit; l++) {
On 2012/03/28 09:59:18, fschneider wrote:
> Maybe use a different letter (j, k?), since 1 and l look to similar.

Done.

http://codereview.chromium.org/9638018/diff/1/test/mjsunit/math-floor-of-div....
test/mjsunit/math-floor-of-div.js:54: assertEquals(Math.floor(div(l,   1)),
Math.floor(l /   1)); assertEquals(Math.floor(div(l,   -1)), Math.floor(l /  
-1));
On 2012/03/28 09:59:18, fschneider wrote:
> 
> Please break the line at 80 chars.

Done.

[Rodolph Perfetta, 2012-03-30 12:14:34]

new patch with comments addressed

[Alexandre, 2012-04-16 10:33:05]

Hello,

Any news on this?

Thanks,

Alexandre

[fschneider, 2012-04-17 07:41:10]

LGTM.

Two small comments. I can fix them before landing if it makes sense. What do you
think?

http://codereview.chromium.org/9638018/diff/13001/src/arm/lithium-arm.cc
File src/arm/lithium-arm.cc (right):

http://codereview.chromium.org/9638018/diff/13001/src/arm/lithium-arm.cc#newc...
src/arm/lithium-arm.cc:1358: HConstant::cast(dividend)->HasInteger32Value()) {
This would only occur is in Math.floor(a/b) both a and b are constants. In this
case the division would be folded already, right? So you can probably leave out
this case here.

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

http://codereview.chromium.org/9638018/diff/13001/test/mjsunit/math-floor-of-...
test/mjsunit/math-floor-of-div.js:169: // (values[key] | 0) does not work
anymore as it is optimized by hydrogen.)
I don't understand why +0 is necessary. It's fine, but maybe also optimized away
in the future. 

x|0 is optimized into x, but x is still forced to be integer32  because of the
bitwise semantics. Maybe you can still use |0 here?

[Alexandre, 2012-04-17 10:01:50]

I agree with your comments. It is great if you can fix them and land.

Thanks,

Alexandre

http://codereview.chromium.org/9638018/diff/13001/src/arm/lithium-arm.cc
File src/arm/lithium-arm.cc (right):

http://codereview.chromium.org/9638018/diff/13001/src/arm/lithium-arm.cc#newc...
src/arm/lithium-arm.cc:1358: HConstant::cast(dividend)->HasInteger32Value()) {
In short: yes we should remove it.

Long:
Divisions are folded at hydrogen generation time.
From what I remember I found out when testing that in rare cases later
optimizations stages could yield this case again. 
In a previous patch not handling this case would raised an error. Now we would
just miss an optimization if we don't handle it.
I ran the tests quickly and did not see this situation occuring any more. So it
seems we should really remove it.


On 2012/04/17 07:41:10, fschneider wrote:
> This would only occur is in Math.floor(a/b) both a and b are constants. In
this
> case the division would be folded already, right? So you can probably leave
out
> this case here.

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

http://codereview.chromium.org/9638018/diff/13001/test/mjsunit/math-floor-of-...
test/mjsunit/math-floor-of-div.js:169: // (values[key] | 0) does not work
anymore as it is optimized by hydrogen.)
I remember changing to '+0' instead of '|0' when the latter was optimized in
hydrogen.
From what I remember the representation for the value loaded from the array was
not forced to int32 and could stay tagged as a smi, preventing the opt for
Math.floor(int32/int32).

Maybe I mis-tested, anyway I re-tested and '|0'works fine.

On 2012/04/17 07:41:10, fschneider wrote:
> I don't understand why +0 is necessary. It's fine, but maybe also optimized
away
> in the future. 
> 
> x|0 is optimized into x, but x is still forced to be integer32  because of the
> bitwise semantics. Maybe you can still use |0 here?

[alexeif, 2012-04-17 16:59:28]

https://chromiumcodereview.appspot.com/9638018/diff/13001/src/utils.h
File src/utils.h (right):

https://chromiumcodereview.appspot.com/9638018/diff/13001/src/utils.h#newcode112
src/utils.h:112: const DivMagicNumbers DivMagicNumberFor625 = {0x68db8bad, 8};
How about adding 60, 100 and 1000? They seem to have even higher rate than 625.

[Alexandre, 2012-04-17 17:12:22]

https://chromiumcodereview.appspot.com/9638018/diff/13001/src/utils.h
File src/utils.h (right):

https://chromiumcodereview.appspot.com/9638018/diff/13001/src/utils.h#newcode112
src/utils.h:112: const DivMagicNumbers DivMagicNumberFor625 = {0x68db8bad, 8};
We can generate optimized code for numbers with an absolute value equals that is
representable by
 <1, or k for which we have a magic number> * 2^n
So optimized code can be generated for these:
60 = 15 * 2^2
100 = 25 * 2^2
1000 = 125 * 2^3

This is detailed in the arm files.

On 2012/04/17 16:59:28, alexeif wrote:
> How about adding 60, 100 and 1000? They seem to have even higher rate than
625.

[alexeif, 2012-04-17 18:30:25]

https://chromiumcodereview.appspot.com/9638018/diff/13001/src/utils.h
File src/utils.h (right):

https://chromiumcodereview.appspot.com/9638018/diff/13001/src/utils.h#newcode112
src/utils.h:112: const DivMagicNumbers DivMagicNumberFor625 = {0x68db8bad, 8};
On 2012/04/17 17:12:22, Alexandre wrote:
> We can generate optimized code for numbers with an absolute value equals that
is
> representable by
>  <1, or k for which we have a magic number> * 2^n
> So optimized code can be generated for these:
> 60 = 15 * 2^2
> 100 = 25 * 2^2
> 1000 = 125 * 2^3
> 
> This is detailed in the arm files.
> 
> On 2012/04/17 16:59:28, alexeif wrote:
> > How about adding 60, 100 and 1000? They seem to have even higher rate than
> 625.
> 
Oh, I see, it has a shift anyway. Btw, why do you need constants for evens 6 and
10?

[Alexandre, 2012-04-18 09:03:58]

https://chromiumcodereview.appspot.com/9638018/diff/13001/src/utils.h
File src/utils.h (right):

https://chromiumcodereview.appspot.com/9638018/diff/13001/src/utils.h#newcode112
src/utils.h:112: const DivMagicNumbers DivMagicNumberFor625 = {0x68db8bad, 8};
Fair question! I actually noticed a non-optimal pattern in the patch (1
instruction difference). Details below.
Since there were a couple of other comments I'll fix that and upload a new
patch.

Optimized code for the pattern
  <k  for which we have a magic number> * 2^n
can require a bit more code (1 instr on ARM) than for
  <k for which we have a magic number>

Using magic numbers for 6 spares one instruction compare to using those for 3
plus the code for the factor 2.
For 10 it does not make a difference here.

And actually, my implementation is non-optimal if divisor == 6...
I first search for the greatest power of 2 dividing the divisor, and check if we
have magic numbers for the odd part.
That means the pattern '3 * 2' is used. One instruction less efficient :(

On 2012/04/17 18:30:26, alexeif wrote:
> On 2012/04/17 17:12:22, Alexandre wrote:
> > We can generate optimized code for numbers with an absolute value equals
that
> is
> > representable by
> >  <1, or k for which we have a magic number> * 2^n
> > So optimized code can be generated for these:
> > 60 = 15 * 2^2
> > 100 = 25 * 2^2
> > 1000 = 125 * 2^3
> > 
> > This is detailed in the arm files.
> > 
> > On 2012/04/17 16:59:28, alexeif wrote:
> > > How about adding 60, 100 and 1000? They seem to have even higher rate than
> > 625.
> > 
> Oh, I see, it has a shift anyway. Btw, why do you need constants for evens 6
and
> 10?

[Zheng Liu, 2012-04-18 10:28:56]

Hi. I proposed a x86/x64 implementation in issue 2038:
http://code.google.com/p/v8/issues/detail?id=2038
which depends on this patch.

I thought that there are some potential deopt unhandled?
Math.floor(0x80000000/-1) = overflow
Math.floor(0/-N) = -0

[Rodolph Perfetta, 2012-04-20 18:14:17]

comments addressed.

[fschneider, 2012-04-23 17:29:58]

LGTM.

We'll land it.

[Rodolph Perfetta, 2012-04-24 15:25:14]

Comments addressed.

[fschneider, 2012-04-24 15:36:54]

Thanks. Still LGTM.

I'll re-land it