Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

VM doesn't optimize division by constant (except powers of 2). #17547

Closed
lrhn opened this issue Mar 18, 2014 · 4 comments
Closed

VM doesn't optimize division by constant (except powers of 2). #17547

lrhn opened this issue Mar 18, 2014 · 4 comments
Labels
area-vm type-bug Incorrect behavior (everything from a crash to more subtle misbehavior)

Comments

@lrhn
Copy link
Member

lrhn commented Mar 18, 2014

Example code:

f(x) => x ~/ 10;

generates optimized code:

0xebadc472    d1f8                   sar eax, 1
0xebadc474    d1fb                   sar ebx, 1
0xebadc476    99                     cdq
0xebadc477    f7fb                   idiv ebx
0xebadc479    3d00000040             cmp eax, 0x40000000
0xebadc47e    0f845c000000           jz 0xebadc4e0
0xebadc484    03c0                   add eax,eax

Two smi untags (one should be enough) and an idiv instead of an imul.
I assume the cmp is for detecting division by zero, which is also not necessary.

Apart from unnecessary overhead, you can also convert division to a multiplication with much better efficiency.

Better code could be (edx still reserved):

mov ebx, 0x66666667
sar eax, 1
imul ebx      ;; result in edx:eax
sar edx, 2
lea eax, edx + edx
@iposva-google
Copy link
Contributor

Below is the relevant comment for the comparison:
      __ SmiUntag(left);
      __ SmiUntag(right);
      __ cdq(); // Sign extend EAX -> EDX:EAX.
      __ idivl(right); // EAX: quotient, EDX: remainder.
      // Check the corner case of dividing the 'MIN_SMI' with -1, in which
      // case we cannot tag the result.
      __ cmpl(result, Immediate(0x40000000));
      __ j(EQUAL, deopt);
      __ SmiTag(result);


cc @fsc8000.
Set owner to @sgmitrovic.
Added Accepted label.

@lrhn lrhn assigned ghost Mar 18, 2014
@kevmoo kevmoo added type-bug Incorrect behavior (everything from a crash to more subtle misbehavior) and removed priority-unassigned labels Feb 29, 2016
@lrhn lrhn unassigned ghost Sep 12, 2016
@lrhn
Copy link
Member Author

lrhn commented Sep 12, 2016

Code is now:

0000000004177CC0    48c7c114000000         movq rcx,0x14
...
0000000004177CFC    48d1f8                 sarq rax,1
0000000004177CFF    48d1f9                 sarq rcx,1
0000000004177D02    4899                   cdqq
0000000004177D04    48f7f9                 idivq rcx
0000000004177D07    4d8b9f17000000         movq r11,[r15+0x17]
0000000004177D0E    493bc3                 cmpq rax,r11
0000000004177D11    0f841f000000           jz 0x4177d36
0000000004177D17    4803c0                 addq rax,rax

It's about the same as when originally filed. This is a division by a constant different from -1, it shouldn't need the compare. It also shouldn't need to smi-untag the constant. Or the operand for that matter, keep it multiplied by two and clear the tag bit afterwards.

movq rcx, 0x0a
cddq
idivq rcx
andq rax, -2

And also, if the modulo isn't needed (I know you do div/mod combining), division by constants can be optimized.

@aam
Copy link
Contributor

aam commented Apr 13, 2017

For negative numbers doesn't the proposed code in original report produces results that are off by 1?
-1 ~/ 10 results in -1, while expected is 0?

@rmacnak-google
Copy link
Contributor

d1c9a2b, 13ba681

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
area-vm type-bug Incorrect behavior (everything from a crash to more subtle misbehavior)
Projects
None yet
Development

No branches or pull requests

5 participants