Improve code for integral modulus calculation.

Improve code for integral modulus calculation.

Depending on what we know about the right operand, we basically do 3
different things (and the code is actually structured this way):

* If we statically know that the right operand is a power of 2, we do
  some bit fiddling instead of doing a "real" modulus calculation.
  This should actually be done on the Hydrogen level, not on the
  Lithium level, but this will be a separate CL.

* If type feedback tells us that the right operand is a power of 2, we
  do the same as above, but guarded by conditional deoptimization to
  make sure that the assumption is still valid. In the long run, we
  should make this guard visible on the Hydrogen level to make it
  visible for GVN and other optimizations.

* In the general case we only do the minimum steps necessary and don't
  try to be too clever, because cleverness actually slows us down on
  real-world code.

If we look at the code gerators for LModI, we actually see that we
basically have 3 (4 on ARM) fundamentally different translations. I
don't really like lumping them together, they should probably be
different Lithium instructions. For the time being, I restructured the
generators to make this crystal-clear, at the cost of some duplication
regarding the power-of-2 cases. This will go away when we do the
strength reduction on the Hydrogen level, so I'd like to keep it as it
is for now.

Note that the MIPS part was only slightly restructured, there is still
some work to do there.

R=jkummerow@chromium.org

Committed: http://code.google.com/p/v8/source/detail?r=15034

[Sven Panne, 2013-06-05 12:37:19]

ia32 version only, just to get early feedback.

[Jakob Kummerow, 2013-06-05 17:08:41]

Looks good.

Needing that mammoth condition in the lithium translator is unfortunate, but in
the short term I don't see a way around it.

https://codereview.chromium.org/15769010/diff/1/src/ia32/lithium-codegen-ia32.cc
File src/ia32/lithium-codegen-ia32.cc (right):

https://codereview.chromium.org/15769010/diff/1/src/ia32/lithium-codegen-ia32...
src/ia32/lithium-codegen-ia32.cc:1246: int32_t divisor =
HConstant::cast(right)->Integer32Value();
even shorter: right->GetInteger32Constant()

https://codereview.chromium.org/15769010/diff/1/src/ia32/lithium-codegen-ia32...
src/ia32/lithium-codegen-ia32.cc:1321: __ test(left_reg, Operand(left_reg));
Why this test? You already know that left_reg == kMinInt at this point.

[Sven Panne, 2013-06-06 06:50:23]

https://codereview.chromium.org/15769010/diff/1/src/ia32/lithium-codegen-ia32.cc
File src/ia32/lithium-codegen-ia32.cc (right):

https://codereview.chromium.org/15769010/diff/1/src/ia32/lithium-codegen-ia32...
src/ia32/lithium-codegen-ia32.cc:1246: int32_t divisor =
HConstant::cast(right)->Integer32Value();
On 2013/06/05 17:08:41, Jakob wrote:
> even shorter: right->GetInteger32Constant()

Done. Lame excuse: It has been there before. ;-) Furthermore, there are 21 other
places like this, but these should handled in a different cleanup CL.

Added an Abs template on the way.

https://codereview.chromium.org/15769010/diff/1/src/ia32/lithium-codegen-ia32...
src/ia32/lithium-codegen-ia32.cc:1321: __ test(left_reg, Operand(left_reg));
On 2013/06/05 17:08:41, Jakob wrote:
> Why this test? You already know that left_reg == kMinInt at this point.

Ooops, this is a remnant of several iterations of simplifying things here. :-/
Done.

[Sven Panne, 2013-06-07 11:59:50]

ia32/x64/ARM complete, PTAL again. Note that the TODOs should probably be done
by platform experts.

@ARM people: Reviewing my ARM changes might be a good idea. :-)

@MIPS people: I've restructured the code to make it more similar to the other
platforms, but did no real changes.

[Jakob Kummerow, 2013-06-07 16:50:07]

Haven't looked at MIPS.

https://codereview.chromium.org/15769010/diff/11001/src/arm/lithium-codegen-a...
File src/arm/lithium-codegen-arm.cc (right):

https://codereview.chromium.org/15769010/diff/11001/src/arm/lithium-codegen-a...
src/arm/lithium-codegen-arm.cc:1303: // TODO(svenpanne) The last comments seems
to be wrong nowadays.
Delete them, then!
"The divisor value is preloaded before" was true before you changed the code
(divisor was loaded in line 1252, comment was in line 1273).
"Be careful that 'right_reg' is only live on entry." clearly does not match
"UseRegister(right)" in lithium-arm.cc; probably it was meant to indicate that
|right| got clobbered in line 1269. Which is scary because |right| wasn't
allocated as UseTempRegister.

https://codereview.chromium.org/15769010/diff/11001/src/arm/lithium-codegen-a...
src/arm/lithium-codegen-arm.cc:1311: // this correct? If yes, a comment about
this might be appropriate.
IIUC, we don't need special handling for that case because we're being clever
about sign handling. It seems what happens is:
vabs -> divisor = 1
vdiv -> quotient = kMinInt / 1 = kMinInt
vcvt, vcvt -> quotient == kMinInt still
vmul -> double_scratch = 1 * kMinInt = kMinInt
vcvt, vmov -> scratch = kMinInt
sub -> result_reg = kMinInt - kMinInt = 0
So no overflow anywhere along the chain.

https://codereview.chromium.org/15769010/diff/11001/src/arm/lithium-codegen-a...
src/arm/lithium-codegen-arm.cc:1330: // TODO(svenpanne) Why do we need scratch2
in addition to scratch?
I don't think we do.

https://codereview.chromium.org/15769010/diff/11001/src/hydrogen-instructions.h
File src/hydrogen-instructions.h (right):

https://codereview.chromium.org/15769010/diff/11001/src/hydrogen-instructions...
src/hydrogen-instructions.h:1042: // We should really use the null object
pattern here...
nit: I don't think this comment adds value.

https://codereview.chromium.org/15769010/diff/11001/src/ia32/lithium-codegen-...
File src/ia32/lithium-codegen-ia32.cc (right):

https://codereview.chromium.org/15769010/diff/11001/src/ia32/lithium-codegen-...
src/ia32/lithium-codegen-ia32.cc:1241: // TODO(svenpanne) We should really do
the strength reduction on the
I'm not sure this comment adds value either.

https://codereview.chromium.org/15769010/diff/11001/src/ia32/lithium-codegen-...
src/ia32/lithium-codegen-ia32.cc:1246: int32_t divisor =
Abs(right->GetInteger32Constant());
This just works by accident for right->GetInteger32Constant() == kMinInt, eh?
|divisor| will be 0 due to overflow; if left_reg contains anything other than
kMinInt the operation should be a no-op and the sequence "neg, and_(..., -1),
neg" thankfully is, and if left_reg does contain kMinInt, then the first "neg"
turns it to 0 and the other instructions don't modify it further. Phew!

[Rodolph Perfetta, 2013-06-07 19:55:03]

https://codereview.chromium.org/15769010/diff/11001/src/arm/lithium-arm.cc
File src/arm/lithium-arm.cc (right):

https://codereview.chromium.org/15769010/diff/11001/src/arm/lithium-arm.cc#ne...
src/arm/lithium-arm.cc:1502: UseFixedDouble(left, d1),
Technically not part of your patch but why are we using d1 and d2? The hardfp
abi will use d0 and d1 so this will generate some extra moves.

The same happens on ia32 so I presume there is (was?) a reason. Note that on
ia32 right is in d1 and left in d2 so only left will be moved before the call.
We could do the same for ARM.

https://codereview.chromium.org/15769010/diff/11001/src/arm/lithium-codegen-a...
File src/arm/lithium-codegen-arm.cc (right):

https://codereview.chromium.org/15769010/diff/11001/src/arm/lithium-codegen-a...
src/arm/lithium-codegen-arm.cc:1240: // Check for kMinInt % -1, sdiv might
signal an exception. We have to deopt
sdiv kMinInt, -1 will not trigger an exception but will return kMinInt. (still
not what you want)

https://codereview.chromium.org/15769010/diff/11001/src/arm/lithium-codegen-a...
src/arm/lithium-codegen-arm.cc:1330: // TODO(svenpanne) Why do we need scratch2
in addition to scratch?
I don't think we do either.

in fact you should be able to always do the sub first and then if you care about
-0 check if the result is 0 and left is negative (like it is done when using
sdiv)

[Sven Panne, 2013-06-10 11:05:39]

Addressed feedback, PTAL again...

https://codereview.chromium.org/15769010/diff/11001/src/arm/lithium-arm.cc
File src/arm/lithium-arm.cc (right):

https://codereview.chromium.org/15769010/diff/11001/src/arm/lithium-arm.cc#ne...
src/arm/lithium-arm.cc:1502: UseFixedDouble(left, d1),
On 2013/06/07 19:55:03, Rodolph Perfetta wrote:
> Technically not part of your patch but why are we using d1 and d2? The hardfp
> abi will use d0 and d1 so this will generate some extra moves.
> 
> The same happens on ia32 so I presume there is (was?) a reason. Note that on
> ia32 right is in d1 and left in d2 so only left will be moved before the call.
> We could do the same for ARM.

Good questions, but I don't have immediate answers to them. I'd like to
investigate this in a follow-up CL to get this CL into the tree as quick as
possible.

https://codereview.chromium.org/15769010/diff/11001/src/arm/lithium-codegen-a...
File src/arm/lithium-codegen-arm.cc (right):

https://codereview.chromium.org/15769010/diff/11001/src/arm/lithium-codegen-a...
src/arm/lithium-codegen-arm.cc:1240: // Check for kMinInt % -1, sdiv might
signal an exception. We have to deopt
On 2013/06/07 19:55:03, Rodolph Perfetta wrote:
> sdiv kMinInt, -1 will not trigger an exception but will return kMinInt. (still
> not what you want)

Adapted comment.

https://codereview.chromium.org/15769010/diff/11001/src/arm/lithium-codegen-a...
src/arm/lithium-codegen-arm.cc:1303: // TODO(svenpanne) The last comments seems
to be wrong nowadays.
On 2013/06/07 16:50:07, Jakob wrote:
> Delete them, then!
> "The divisor value is preloaded before" was true before you changed the code
> (divisor was loaded in line 1252, comment was in line 1273).
> "Be careful that 'right_reg' is only live on entry." clearly does not match
> "UseRegister(right)" in lithium-arm.cc; probably it was meant to indicate that
> |right| got clobbered in line 1269. Which is scary because |right| wasn't
> allocated as UseTempRegister.

Removed the comment. "scary" = "it was a bug" ;-)

https://codereview.chromium.org/15769010/diff/11001/src/arm/lithium-codegen-a...
src/arm/lithium-codegen-arm.cc:1311: // this correct? If yes, a comment about
this might be appropriate.
On 2013/06/07 16:50:07, Jakob wrote:
> IIUC, we don't need special handling for that case because we're being clever
> about sign handling. [...]

I added a comment about this.

https://codereview.chromium.org/15769010/diff/11001/src/arm/lithium-codegen-a...
src/arm/lithium-codegen-arm.cc:1330: // TODO(svenpanne) Why do we need scratch2
in addition to scratch?
On 2013/06/07 19:55:03, Rodolph Perfetta wrote:
> I don't think we do either.
> 
> in fact you should be able to always do the sub first and then if you care
about
> -0 check if the result is 0 and left is negative (like it is done when using
> sdiv)

Good idea, I did that and simplified LModI accordingly.

https://codereview.chromium.org/15769010/diff/11001/src/hydrogen-instructions.h
File src/hydrogen-instructions.h (right):

https://codereview.chromium.org/15769010/diff/11001/src/hydrogen-instructions...
src/hydrogen-instructions.h:1042: // We should really use the null object
pattern here...
On 2013/06/07 16:50:07, Jakob wrote:
> nit: I don't think this comment adds value.

I'll change this into a real TODO then, code like this is fundamentally
embarrassing and I really like to to this in cleaner way, but not in this CL.

https://codereview.chromium.org/15769010/diff/11001/src/ia32/lithium-codegen-...
File src/ia32/lithium-codegen-ia32.cc (right):

https://codereview.chromium.org/15769010/diff/11001/src/ia32/lithium-codegen-...
src/ia32/lithium-codegen-ia32.cc:1241: // TODO(svenpanne) We should really do
the strength reduction on the
On 2013/06/07 16:50:07, Jakob wrote:
> I'm not sure this comment adds value either.

Actually it does: This part of DoModI is basically a copy of the
has_fixed_right_arg() part, and this part will go away very soon, so I wanted to
make it clear that it doesn't make sense to unify things somehow, this would
even be counter-productive.

https://codereview.chromium.org/15769010/diff/11001/src/ia32/lithium-codegen-...
src/ia32/lithium-codegen-ia32.cc:1246: int32_t divisor =
Abs(right->GetInteger32Constant());
On 2013/06/07 16:50:07, Jakob wrote:
> This just works by accident for right->GetInteger32Constant() == kMinInt, eh?
> |divisor| will be 0 due to overflow; if left_reg contains anything other than
> kMinInt the operation should be a no-op and the sequence "neg, and_(..., -1),
> neg" thankfully is, and if left_reg does contain kMinInt, then the first "neg"
> turns it to 0 and the other instructions don't modify it further. Phew!

Yep, this clever handling has been there before, but most probably it was pure
luck. ;-) I'll add a comment as a reminder when we convert this to
Hydrogen-level strength reduction.

[Jakob Kummerow, 2013-06-10 11:50:01]

lgtm

[Sven Panne, 2013-06-10 12:06:05]

Committed patchset #6 manually as r15034 (presubmit successful).

[Sven Panne, 2013-06-11 06:49:52]

Just a small note regarding the MIPS part: It works as it is, but not in an
optimal way: LChunkBuilder::DoMod seems to allocate temp registers for LModI for
no good reason, and LCodeGen::DoModI doesn't handle the has_fixed_right_arg()
case specially. Fixing both issues should yield a very visible performance
improvement in e.g. Kraken and other benchmarks.

[kisg, 2013-06-11 07:47:29]

On 2013/06/11 06:49:52, Sven Panne wrote:
> Just a small note regarding the MIPS part: It works as it is, but not in an
> optimal way: LChunkBuilder::DoMod seems to allocate temp registers for LModI
for
> no good reason, and LCodeGen::DoModI doesn't handle the has_fixed_right_arg()
> case specially. Fixing both issues should yield a very visible performance
> improvement in e.g. Kraken and other benchmarks.

Hi Sven,

Thanks for the note, we are looking into it.

Best Regards,
Gergely