Closed Bug 1017275 Opened 6 years ago Closed 6 years ago

Make Number.isNaN and Number.isFinite inlinable

Categories

(Core :: JavaScript Engine: JIT, enhancement)

enhancement
Not set

Tracking

()

RESOLVED FIXED
mozilla32

People

(Reporter: Waldo, Assigned: nathan)

Details

(Whiteboard: [mentor=nbp][lang=c++])

Attachments

(1 file, 7 obsolete files)

New ES6 methods, both pretty trivial, no reason not to inline them instead of requiring function calls.  Also a good way to ease into JIT code some.  Relevant code to inline should be in jit/MCallOptimize.cpp.  All sorts of MIR instruction information should be in jit/MIR.h.  Ask questions here or in #jsapi/#ionmonkey.  :-)
Whiteboard: [mentor=nbp][lang=c++]
Attached patch Patch for inlining isNaN (obsolete) — Splinter Review
All right, isNaN works! I'll do isFinite in another patch
Attachment #8431246 - Flags: review?(jwalden+bmo)
And here's IsFinite().
Attachment #8431859 - Flags: review?(jwalden+bmo)
Comment on attachment 8431246 [details] [diff] [review]
Patch for inlining isNaN

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

Overall this looks fairly solid and reasonable, except for one thing: MIR instructions are composable.  You don't need to add a MIR instruction, or an underlying LIR instruction, to handle this case, because we already have a comparison op.  Given that, we obviously want to just reuse those without adding a bunch of code for one special case.

In any event it looks like you had opportunity to dive into a bunch of different places in the process, so the patch seems useful even if it's doing rather more work than it needs to.  :-)

::: js/src/jit/MCallOptimize.cpp
@@ +43,5 @@
>      if (native == js::array_concat)
>          return inlineArrayConcat(callInfo);
>      if (native == js::array_splice)
>          return inlineArraySplice(callInfo);
> +    

Style nit: Remove the trailing whitespace.  Also typically we only separate methods, bits of code, etc. by a single blank line.  You've added double blank lines a few places in this patch.

@@ +614,5 @@
> +    if (callInfo.constructing())
> +        return InliningStatus_NotInlined;
> +
> +    if (callInfo.argc() != 1)
> +        return InliningStatus_NotInlined;

isNaN is super-simple, so we can/should handle every case except the constructing case, which truly isn't inlinable.  Zero arguments evaluates to constant false, easily done.  And if non-zero arguments, you can continue through to the rest of the inlining with correct behavior.

@@ +616,5 @@
> +
> +    if (callInfo.argc() != 1)
> +        return InliningStatus_NotInlined;
> +
> +    MIRType argType = callInfo.getArg(0)->type();

Add a local for |callInfo.getArg(0)|, to cut down repetition.

@@ +618,5 @@
> +        return InliningStatus_NotInlined;
> +
> +    MIRType argType = callInfo.getArg(0)->type();
> +    if (!IsNumberType(argType))
> +        return InliningStatus_NotInlined;

IsNumberType admits floats, doubles, and int32_t, but the latter can't be NaN.  IsFloatingPointType is what you really want.  And, you should be able to make the !IsFloatingPointType case fall through into evaluating to a constant false, as well.

@@ +622,5 @@
> +        return InliningStatus_NotInlined;
> +
> +    callInfo.setImplicitlyUsedUnchecked();
> +
> +    MIsNaN *ins = MIsNaN::New(alloc(), callInfo.getArg(0));

MIR instructions are composable, so you shouldn't need a new instruction to do this.  Something like

MDefinition *arg = callInfo.getArg(0);
MCompare *cmp = MCompare::New(alloc(), arg, arg, JSOP_STRICTNE);
current->add(cmp);
current->push(cmp);
return InliningStatus_Inlined;

should do the trick, I think.  As a bonus, I think that also lets you rely on existing code to optimize the comparison away if it's known the operand isn't NaN.  (Although on skimming, we might not have this for doubles.  If I'm not mistaken about that, we should probably file a followup to take advantage of that information.)
Attachment #8431246 - Flags: review?(jwalden+bmo) → review-
Comment on attachment 8431859 [details] [diff] [review]
inlineIsFinite.patch inlines IsFinite

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

Looks pretty decent, but we should implement this differently at the lower levels, and we need to be careful about making float32 stuff work.  Also, this needs some tests.

It'd be good to do some before/after benchmarking of this to see what sort of perf difference it makes on a stupid little microbenchmark.  I'll poke you to discuss the sort of thing you'd want here.

::: js/src/jit/CodeGenerator.cpp
@@ +4437,5 @@
>      return true;
>  }
>  
>  bool
> +CodeGenerator::visitIsFinite(LIsFinite *ins)

This only handles doubles.  We probably should make a version of this that handles floats as well (so we'd have MIsFinite, and then lowering would convert that to LIsFiniteF and LIsFiniteD), when it happens that isFinite is called on a known float32.  I think something like this will exercise that code path, with --ion-eager --ion-parallel-compile=off:

  var farray = new Float32Array([NaN, NaN, NaN, NaN, NaN, NaN, NaN, NaN]);
  for (var i = 0; i < farray.length; i++)
    assertEq(Number.isFinite(farray[i]), false);

@@ +4441,5 @@
> +CodeGenerator::visitIsFinite(LIsFinite *ins)
> +{
> +    Register output = ToRegister(ins->output());
> +    FloatRegister input = ToFloatRegister(ins->number());
> +    FloatRegister temp = ToFloatRegister(ins->temp());

I checked what glibc does for isfinite at least on x86-64.  The approach there is like so:

int
__finite(double x)
{
  int64_t lx;
  EXTRACT_WORDS64(lx,x);
  return (int)((uint64_t)((lx&INT64_C(0x7fffffffffffffff))-INT64_C(0x7ff0000000000000))>>63);
}

which boils down to

   0x00007ffff77f96b0 <__GI___finite+0>:	movabs $0x7fffffffffffffff,%rdx
=> 0x00007ffff77f96ba <__GI___finite+10>:	movq   %xmm0,%rax
   0x00007ffff77f96bf <__GI___finite+15>:	and    %rdx,%rax
   0x00007ffff77f96c2 <__GI___finite+18>:	movabs $0x8010000000000000,%rdx
   0x00007ffff77f96cc <__GI___finite+28>:	add    %rdx,%rax
   0x00007ffff77f96cf <__GI___finite+31>:	shr    $0x3f,%rax
   0x00007ffff77f96d3 <__GI___finite+35>:	retq   

I don't know for sure, but I suspect this sort of bitwise math will be much faster than several floating-point comparisons.  Certainly it's suggestive that glibc, which presumably cares about optimizations, does this.  (We often will compile code with gcc or so and look at the assembly as a hint to suggest what instructions in optimization.  :-) )  Perhaps sunfish can say for sure that bitwise math is definitely fastest way to do it, maybe.

(Note that algorithm doesn't care about returning exactly 0/1 -- that may or may not matter for our purposes here, I'm not sure offhand.  Something to be careful about.)

This may require writing architecture-specific CodeGenerator methods for visiting LIsFinite*.  Not totally sure about that.

::: js/src/jit/Lowering.cpp
@@ +1177,5 @@
>  
>  bool
> +LIRGenerator::visitIsFinite(MIsFinite *ins) {
> +    JS_ASSERT(ins->type() == MIRType_Boolean);
> +    return define(new(alloc()) LIsFinite(useRegister(ins->input()), tempDouble()), ins);

I believe this is where the float32/float64 type mismatch would arise.

::: js/src/jit/MCallOptimize.cpp
@@ +645,5 @@
> +        return InliningStatus_NotInlined;
> +
> +    callInfo.setImplicitlyUsedUnchecked();
> +
> +    MIsFinite *ins = MIsFinite::New(alloc(), callInfo.getArg(0));

I...think this will produce both float32 and float64 argument types, per the FloatingPointPolicy in MIsFinite.  So the Float32Array demo I put in one of the other comments would trigger a MIR type mismatch assertion.  I think.
Attachment #8431859 - Flags: review?(jwalden+bmo) → review-
Comments on the optimization bits of comment 4?  And conceivably on comment 3, if for some reason x != x is that poorly optimized at the microcode level, I guess.  (Although I'm not sure we should care, if it's poorly optimized.  But we should at least know.)
Flags: needinfo?(sunfish)
(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #5)
> Comments on the optimization bits of comment 4?  And conceivably on comment
> 3, if for some reason x != x is that poorly optimized at the microcode
> level, I guess.  (Although I'm not sure we should care, if it's poorly
> optimized.  But we should at least know.)

For isFinite, I theorize (but have not tested) that fabs(x) == PositiveInfinity() is faster yet. It looks like you can do it with the existing MAbs and MCompare nodes also.

With both isFinite and isNaN, using MCompare as suggested in comment 3 is also nice because it should fold into conditional branches (avoiding the need to set an integer register to 0 or 1 when you just want to branch on it) :).
Flags: needinfo?(sunfish)
Ok, isNaN and isFinite have been fixed and combined into one patch because their location worked out so that it's more convenient to put them together.

I'll add tests in another patch, but preliminary tests show quite a speedup for both functions.
Attachment #8431246 - Attachment is obsolete: true
Attachment #8431859 - Attachment is obsolete: true
Attachment #8432781 - Flags: review?(jwalden+bmo)
(In reply to Dan Gohman [:sunfish] from comment #6)
> (In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #5)
> > Comments on the optimization bits of comment 4?  And conceivably on comment
> > 3, if for some reason x != x is that poorly optimized at the microcode
> > level, I guess.  (Although I'm not sure we should care, if it's poorly
> > optimized.  But we should at least know.)
> 
> For isFinite, I theorize (but have not tested) that fabs(x) ==
> PositiveInfinity() is faster yet. It looks like you can do it with the
> existing MAbs and MCompare nodes also.

Oh, oops. Of course, fabs(x) == PositiveInfinity() would be isInfinite, not isFinite.

For isFinite, I suggest (x - x) == 0.0. That should be fast, and it also ends in an MCompare.
Added jit-tests. Revealed that our method doesn't work for NaN, but sunfish beat me to it and already commented a fixed method. Will get that in a sec.
Attachment #8432810 - Flags: review?(jwalden+bmo)
Attached patch Version two that fixes isFinite (obsolete) — Splinter Review
Ok, implemented the subtraction method. Tests pass now!
Attachment #8432781 - Attachment is obsolete: true
Attachment #8432781 - Flags: review?(jwalden+bmo)
Attachment #8432871 - Flags: review?(jwalden+bmo)
Modified the tests slightly so they don't take as long.
Attachment #8432810 - Attachment is obsolete: true
Attachment #8432810 - Flags: review?(jwalden+bmo)
Attachment #8432872 - Flags: review?(jwalden+bmo)
Comment on attachment 8432871 [details] [diff] [review]
Version two that fixes isFinite

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

This is kind of sadfaces, but super-belatedly occurs to me that if we're going to do both of these using what would, effectively, be just as easily written in pure JS, we should just self-host both of these.  :-\  Sorry for the massive head-fake here, but at least it was a solid introduction to MIR, LIR, and the JITs.
Attachment #8432871 - Flags: review?(jwalden+bmo)
Comment on attachment 8432872 [details] [diff] [review]
Tests modifed to do less iterations while still using the inliner.

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

::: js/src/jit-test/tests/basic/isFiniteInline.js
@@ +15,5 @@
> +		rPInfi = Number.isFinite(+Infinity)
> +	}else{
> +		rNInfi = Number.isFinite(-Infinity)
> +		rThreei = Number.isFinite(3)
> +		rPIi = Number.isFinite(3.141592654)

Same basic considerations as on the other test: semicolons, use assertEq(..., true or false), test +0, -0, and -NaN too, move the test to a better location.

::: js/src/jit-test/tests/basic/isNaNInline.js
@@ +1,1 @@
> +/* Test inlining of Number.isNaN() */

I'd put this into ion/inlining/, I think.  Same for the other test.  (We have really poor organization for JIT tests as far as grouping related subjects together.  No need to make it worse, tho.)

@@ +1,4 @@
> +/* Test inlining of Number.isNaN() */
> +
> +var Nann, Pin, PInfn, NInfn
> +var Nani, Pii, PInfi, NInfi

Semicolons at the end of statements, please.  (Other than block statements and function declarations, at least.  Relying on automatic semicolon insertion in JS can be quite fragile.)

@@ +9,5 @@
> +NInfn = Number.isNaN(-Infinity)
> +
> +for (var i = 0; i < 200000; i++) {
> +	if (i % 2 === 1) {
> +		Nani = Number.isNaN(NaN)

Better to make this assertEq(Number.isNaN(NaN), true);

@@ +10,5 @@
> +
> +for (var i = 0; i < 200000; i++) {
> +	if (i % 2 === 1) {
> +		Nani = Number.isNaN(NaN)
> +		PInfi = Number.isNaN(+Infinity)

And this assertEq(Number.isNaN(+Infinity), false);

@@ +13,5 @@
> +		Nani = Number.isNaN(NaN)
> +		PInfi = Number.isNaN(+Infinity)
> +	} else {
> +		Pii = Number.isNaN(3.14159)
> +		NInfi = Number.isNaN(-Infinity)

And assertEq(Number.isNaN(3.14159), false); and assertEq(Number.isNaN(-Infinity), false);

Probably worth throwing in tests for -NaN (in some configurations negation flips the sign bit, meaningless in NaN but a different bit pattern), +0, and -0, too.
Attachment #8432872 - Flags: review?(jwalden+bmo)
Changed to a much much simpler and equally as fast self-hosted implementation and put updated tests in the same patch.
Attachment #8432871 - Attachment is obsolete: true
Attachment #8432872 - Attachment is obsolete: true
Attachment #8435117 - Flags: review?(jwalden+bmo)
Comment on attachment 8435117 [details] [diff] [review]
selfHost.patch - Changed to a very simple self-hosted implementation, combined with fixed tests

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

Modulo nitpicks, looks fine.  Throwing over to sunfish, tho, to answer a question: what tricks do we play in tests these days, to avoid aggressive constant-folding causing the algorithm in question to not be exercised?  Looking at these, I'm somewhat worried that we could easily end up constant-folding away the entire algorithm in all of these cases, then never actually really test the algorithms we want to test.

My guess is we want the loops as they are, but we want additional loops that load these values out of an array or so, so that the exact values aren't *known* when JITting.  But throwing to sunfish to say for sure.

::: js/src/builtin/Number.js
@@ +42,5 @@
> +// ES6 draft ES6 20.1.2.4
> +function Number_isFinite(num) {
> +    if (typeof num == "number")
> +        return num-num == 0;
> +    return false;

=== for both of these, and spaces around the -.  Also, let's structure the way the spec does it, to invert the condition:

    if (typeof num !== "number")
        return false;
    return num - num === 0;

@@ +49,5 @@
> +// ES6 draft ES6 20.1.2.2
> +function Number_isNaN(num) {
> +    if (typeof num == "number")
> +        return num != num;
> +    return false;

Same sorts of comments here:

    if (typeof num !== "number")
        return false;
    return num !== num;

::: js/src/jit-test/tests/ion/inlining/isNaNInline.js
@@ +1,4 @@
> +/* Test inlining of Number.isNaN() */
> +
> +for (var i = 0; i < 200000; i++) {
> +	assertEq(Number.isNaN(NaN), true);

Noooo don't put tabs in files.  :-)
Attachment #8435117 - Flags: review?(sunfish)
Attachment #8435117 - Flags: review?(jwalden+bmo)
Attachment #8435117 - Flags: review+
Comment on attachment 8435117 [details] [diff] [review]
selfHost.patch - Changed to a very simple self-hosted implementation, combined with fixed tests

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

The test already does execute the function bodies; it just isn't as robust against future optimizer cleverness as it could be. I filed bug 1021310 for a possible way to improve these tests. So, this patch looks good to me.
Attachment #8435117 - Flags: review?(sunfish) → review+
Should be good to go!
Attachment #8435117 - Attachment is obsolete: true
Not quite good to go -- had some merge conflicts on CLOBBER hits (guess we're going to be contending on that pretty hard til bug 1019955 is fixed), rejects changing the number_static_methods array for reasons I didn't bother to figure out, and you had ==/!= instead of === and !== (strict equality checks preferred to loose, that is).  But those were easy enough to fix locally.

https://hg.mozilla.org/integration/mozilla-inbound/rev/e6905f611ad6
Target Milestone: --- → mozilla32
https://hg.mozilla.org/mozilla-central/rev/e6905f611ad6
Status: ASSIGNED → RESOLVED
Closed: 6 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.