1010747 - Math.ceil inlining can cause repeated bailouts

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect)

Description

[Jan de Mooij [:jandem]]

See bug 1009829. The shell testcase below keeps bailing because Math.ceil(x) is inlined like this:

-1 * floor(x * -1.0)

The problem is that if x == 0, x * -1.0 is -0 and the floor will bail. Math.ceil(0) is +0 though, so the code will never be invalidated and we risk being stuck in a bailout loop.

function g(x) {
    return Math.ceil(x);
}
function f() {
    var arr = [1.1];
    var res = 0;
    for (var i=0; i<100000; i++) {
	res = g(arr[0]);
	if (i > 100)
	    arr[0] = 0;
    }
}
f();

Comment 1

[Jan de Mooij [:jandem]]

Benjamin, can you investigate this? Thanks!

Comment 2

[Jan de Mooij [:jandem]]

Considering how common Math.ceil(0) is, let's make sure this is fixed for FF 30 (beta) or else we should disable Math.ceil inlining there for now.

Setting tracking flags because this affects a popular benchmark (CanvasMark, bug 1009829) and likely more benchmarks/websites/games.

Comment 3

[Benjamin Bouvier [:bbouvier] (inactive)]

I'll take care of it very soon.

Comment 4

[Sylvestre Ledru [:Sylvestre]]

Tracking (cf comment 2)

Comment 5

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: Remove inlining in (Double) -> Int32 case

I am trying to make out something better, but at least this decreases the run time for this micro-benchmark.

Comment 6

[Benjamin Bouvier [:bbouvier] (inactive)]

Comment on attachment 8424911 [details] [diff] [review]
Remove inlining in (Double) -> Int32 case

Review of attachment 8424911 [details] [diff] [review]:
-----------------------------------------------------------------

Flagging for review after this morning IRC discussion. This patch should be landed separately from the other ones (to be uploaded), and be uplifted in aurora / beta. Nightly will benefit from the next patches.

Comment 7

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: Part 1 - a few cleanups

Comment 8

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: Part 2 - MCeil + all platforms impl

This patch properly implements MCeil. It has to take a path slightly different from MFloor's. Flagging marty for reviewing the ARM specific parts, jandem for the rest.

The hard part is that we need to test values in the range ]-1; -0], as their ceil value is -0 and we need to bail out in this case. However, this works out pretty well. In your micro-benchmark in comment 0, with moar iterations:

- Without any patch: > 2 minutes
- With the first patch applied (don't inline Ceil(double) -> int32): 2881 ms
- With this patch: 28ms

https://tbpl.mozilla.org/?tree=Try&rev=a744318f991e

Comment 9

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: Part 2 - MCeil + all platforms impl + tests

Even better with tests, see previous comment for the entire explanation.

Note: if you replace "var log = ..." by "var log = print", you will see the places where bailouts are supposed to occur. Then you can check with IONFLAGS=bl-bails that the reports are correct.

Comment 10

[Jan de Mooij [:jandem]]

Comment on attachment 8424911 [details] [diff] [review]
Remove inlining in (Double) -> Int32 case

Review of attachment 8424911 [details] [diff] [review]:
-----------------------------------------------------------------

Thanks!

::: js/src/jit/MCallOptimize.cpp
@@ +693,5 @@
>          return InliningStatus_Inlined;
>      }
>  
> +    if (IsFloatingPointType(argType) && returnType == MIRType_Int32)
> +        return InliningStatus_NotInlined;

Nit: you could also remove this "if", we'll fallback to the 

  return InliningStatus_NotInlined;

At the end. It doesn't really matter; either way is fine with me.

Comment 11

[Jan de Mooij [:jandem]]

Comment on attachment 8425539 [details] [diff] [review]
Part 1 - a few cleanups

Review of attachment 8425539 [details] [diff] [review]:
-----------------------------------------------------------------

Nice.

Comment 12

[Jan de Mooij [:jandem]]

Comment on attachment 8425548 [details] [diff] [review]
Part 2 - MCeil + all platforms impl + tests

Review of attachment 8425548 [details] [diff] [review]:
-----------------------------------------------------------------

Sorry I've been really busy today with reviews and tracking down bugs in 29.

Dan, would you mind taking this?

Comment 13

[Marty Rosenberg [:mjrosenb]]

Comment on attachment 8425548 [details] [diff] [review]
Part 2 - MCeil + all platforms impl + tests

Review of attachment 8425548 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/arm/MacroAssembler-arm.cpp
@@ +4213,5 @@
> +    ma_b(&handlePos, Assembler::NotSigned);
> +
> +    // We are in the ]-Inf; 0[ range
> +    // If we are in the ]-1; 0[ range => bailout
> +    loadConstantDouble(-1.0, ScratchFloatReg);

you should use ma_vimm here, it will generate a single instruction immediate move, rather than a load.

@@ +4243,5 @@
> +    ma_vcvt_U32_F64(ScratchFloatReg, ScratchFloatReg);
> +    compareDouble(ScratchFloatReg, input);
> +    ma_add(output, Imm32(1), output, NoSetCond, NotEqual);
> +    // Bail out if the add overflowed or the result is negative
> +    ma_mov(output, output, SetCond);

You *may* be able to get away with not doing this, by using vrms, moving the condition codes to the scratch register, then adding that (right shifted by 30, to convert the Z flag into either 0 or 1), then doing an unconditional add, but this code is fine, and I'd like to see that bit of craziness tested *thoroughly*

@@ +4264,5 @@
> +    ma_b(&handlePos, Assembler::NotSigned);
> +
> +    // We are in the ]-Inf; 0[ range
> +    // If we are in the ]-1; 0[ range => bailout
> +    loadConstantFloat32(-1.f, ScratchFloatReg);

it looks like this is fine (why do the double and single variants of this function take wildly different code paths?)

Comment 14

[Dan Gohman [:sunfish]]

Comment on attachment 8425548 [details] [diff] [review]
Part 2 - MCeil + all platforms impl + tests

Review of attachment 8425548 [details] [diff] [review]:
-----------------------------------------------------------------

Overall looks very good. I believe this will fix bug 718372 too.

::: js/src/jit-test/tests/ion/ceil.js
@@ +54,5 @@
> +// Values outside the INT32 range, when represented in either double or
> +// single precision
> +testBailout(INT_MAX + .5);
> +testBailout(INT_MIN - 129);
> +// BatNaN

I see.

::: js/src/jit/shared/CodeGenerator-x86-shared.cpp
@@ +1723,5 @@
> +    masm.loadConstantDouble(-1, scratch);
> +    masm.branchDouble(Assembler::DoubleLessThanOrEqual, input, scratch, &lessThanMinusOne);
> +
> +    masm.xorpd(scratch, scratch);
> +    masm.branchDouble(Assembler::DoubleLessThan, input, scratch, &bailout);

I think we can skip this check. After the x <= -1 branch before this, the only values remaining with their sign bit set are (-1,0) and -0; the movmskpd sign bit check below should catch everything in (-1,0) as well as -0. To handle NaN, you could make the check above use DoubleLessThanOrEqualOrUnordered instead of DoubleLessThanOrEqual.

@@ +1738,5 @@
> +        // Round toward +Infinity.
> +        masm.roundsd(input, scratch, JSC::X86Assembler::RoundUp);
> +
> +        masm.cvttsd2si(scratch, output);
> +        masm.cmp32(output, Imm32(INT_MIN));

You can do this cmp with a smaller immediate; see the code in x86's and x64's branchTruncateDouble implementations.

@@ +1746,5 @@
> +    }
> +
> +    Label end;
> +
> +    // x > -0 (i.e. x >= 0), we can truncate (resp. truncate and add 1) for

Technically -0 is equal to 0, so this comment should say x >= 0 and x is not -0.0, or x's signbit is 0.

@@ +1751,5 @@
> +    // integer (resp. non-integer) values.
> +    // Will also work for NaN and values >= INT_MAX + 1, as the truncate
> +    // operation will return INT_MIN and there'll be a bailout.
> +    masm.cvttsd2si(input, output);
> +    masm.cmp32(output, Imm32(INT_MIN));

Another cmp which can use the trick in branchTruncateDouble.

@@ +1760,5 @@
> +
> +    // if input > INT_MAX, output == INT_MAX so adding 1 will overflow.
> +    masm.cmp32(output, Imm32(INT_MAX));
> +    if (!bailoutIf(Assembler::Equal, lir->snapshot()))
> +        return false;

Instead of explicitly testing for INT_MAX, you could just bailout on Assembler::Overflow after doing the add below.

@@ +1769,5 @@
> +
> +    // x <= -1, truncation is the way to go.
> +    masm.bind(&lessThanMinusOne);
> +    masm.cvttsd2si(input, output);
> +    masm.cmp32(output, Imm32(INT_MIN));

Another cmp which can use the trick in branchTruncateDouble. It may be worthwhile to factor this into a helper routine.

@@ +1778,5 @@
> +    return true;
> +}
> +
> +bool
> +CodeGeneratorX86Shared::visitCeilF(LCeilF *lir)

Most of the comments in visitCeil apply here as well.

Comment 15

[Marty Rosenberg [:mjrosenb]]

Comment on attachment 8425548 [details] [diff] [review]
Part 2 - MCeil + all platforms impl + tests

I assume that was some sort of a collision.

Comment 16

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: Remove inlining in (Double) -> Int32 case

Thanks for the review! Carrying forward r+ from jandem.

Landing the attached patch separately, for easier uplifting:
https://hg.mozilla.org/integration/mozilla-inbound/rev/2132ca5bd8a7

Comment 18

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: Bonus: factor out cvttsX2si and bailout code

Thanks for the review comments! Glad that we can spare on test.
Also, making a helper routine for the "convert and truncate and bailout if the truncation has failed" code works out pretty well.

Comment 19

[Dan Gohman [:sunfish]]

Comment on attachment 8426172 [details] [diff] [review]
Bonus: factor out cvttsX2si and bailout code

Review of attachment 8426172 [details] [diff] [review]:
-----------------------------------------------------------------

Nice! One nit: the comment about materializing a value in a register only applied to the 64-bit int case. 32-bit 0x80000000 does fit into an immediate, but it requires a full 4 byte field instead of the one-byte field for 1.

Comment 20

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/2132ca5bd8a7

Comment 21

[Benjamin Bouvier [:bbouvier] (inactive)]

Comment on attachment 8426110 [details] [diff] [review]
Remove inlining in (Double) -> Int32 case

[Approval Request Comment]
Bug caused by (feature/regressing bug #): bug 936740
User impact if declined: big slowdowns on tracked benchmarks and potentially on real world code that uses Math.ceil
Testing completed (on m-c, etc.): local, m-i, m-c completed
Risk to taking this patch (and alternatives if risky): no risk, it just disables an optimization.
String or IDL/UUID changes made by this patch: /

Comment 22

[Benjamin Bouvier [:bbouvier] (inactive)]

(In reply to Dan Gohman [:sunfish] from comment #19)
> Comment on attachment 8426172 [details] [diff] [review]
> Bonus: factor out cvttsX2si and bailout code
> 
> Review of attachment 8426172 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> Nice! One nit: the comment about materializing a value in a register only
> applied to the 64-bit int case. 32-bit 0x80000000 does fit into an
> immediate, but it requires a full 4 byte field instead of the one-byte field
> for 1.

Thanks, fixed the comment.

remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/77b49bfe1d90
remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/84e12d8fa8d5
remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/eb28b926dc94

Comment 23

[Ryan VanderMeulen [:RyanVM]]

Looking at inbound, this looks very likely to stick.

https://hg.mozilla.org/releases/mozilla-aurora/rev/d8896351e5f1
https://hg.mozilla.org/releases/mozilla-aurora/rev/70f39dc8a9c4
https://hg.mozilla.org/releases/mozilla-aurora/rev/6ca8f23d819e

https://hg.mozilla.org/releases/mozilla-beta/rev/586ed41fa2d1
https://hg.mozilla.org/releases/mozilla-beta/rev/80950d72bd71
https://hg.mozilla.org/releases/mozilla-beta/rev/0db12290df12

Comment 24

[Ryan VanderMeulen [:RyanVM]]

Fail. Backed out comment 23 and re-landed the proper branch patch. Sorry about that.

https://hg.mozilla.org/releases/mozilla-aurora/rev/d45368733d27
https://hg.mozilla.org/releases/mozilla-beta/rev/d3f2e54cf39c

Comment 25

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/releases/mozilla-b2g30_v1_4/rev/d3f2e54cf39c

Comment 26

[Hannes Verschore [:h4writer]]

Deltablue improvement of 7% \0/

Comment 27

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/77b49bfe1d90
https://hg.mozilla.org/mozilla-central/rev/84e12d8fa8d5
https://hg.mozilla.org/mozilla-central/rev/eb28b926dc94