901274 - Reduce branching in testObjectTruthy and testValueTruthy

Status: RESOLVED FIXED

(Core :: JavaScript Engine, enhancement)

Description

[Dan Gohman [:sunfish]]

Attachment: more-fallthroughs.patch

testObjectTruthy and testValueTruthy both contain code sequences like this:

    masm.j(cond, ifTruthy);
    masm.jump(ifFalsy);

This always emits two branches. However, if either of ifTruthy or ifFalsy could be reached by fallthrough, one of the branches is unnecessary.

This patch factors out the code from the code generator for optimizing two-way branch sequences into utility functions, and replaces manual branching sequences with calls to the utility functions, so that they benefit from the same optimization.

Comment 1

[Jeff Walden [:Waldo]]

Comment on attachment 785436 [details] [diff] [review]
more-fallthroughs.patch

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

Sorry for being slow about getting to this...

I did a bit of work initially when landing this, to do something similar to this -- have branchTestFoo(ifFoo) in addition to testFoo(ifTrue, ifFalse), using the former when fallthrough was possible -- that appeared to make no difference to perf numbers, so I dropped it for other work.  See attachment 693591 [details] [diff] [review].  I think that pattern is clearer than having a bunch of places randomly pass in |nextBlockLabel()|.  What do you think?

The masm.j changes should probably be in a separate patch.  They don't look unreasonable, to consolidate those ideas in a single place, but I'd be happier not having to think about that change so deeply, while also considering the actual desired change being made here.

Comment 2

[Jeff Walden [:Waldo]]

Comment on attachment 785436 [details] [diff] [review]
more-fallthroughs.patch

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

See comment 1.

Comment 3

[Dan Gohman [:sunfish]]

Attachment: test-object.patch

This is just a refresh/forward-port of attachment 693591 [details] [diff] [review].

Comment 4

[Dan Gohman [:sunfish]]

Attachment: test-object.patch

Attached is an updated and tested version of the patch.

I am seeing some cases where performance is behaving erratically, and I think it might be because of the micro-architectural effects of having so many branches so close together. This patch doesn't fix everything, but I'd like to get some branches out of the way before I start experimenting with alignment padding.

Comment 5

[Dan Gohman [:sunfish]]

Attachment: test-notv-branch.patch

This patch applies a similar change to testValueTruthy, to allow NotV to avoid a trailing nop branch.

Comment 6

[Jeff Walden [:Waldo]]

Comment on attachment 822918 [details] [diff] [review]
test-object.patch

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

Been awhile, but I think this makes sense.

Comment 7

[Jeff Walden [:Waldo]]

Comment on attachment 822920 [details] [diff] [review]
test-notv-branch.patch

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

::: js/src/jit/CodeGenerator.cpp
@@ +4697,5 @@
>      Label join;
>      Register output = ToRegister(lir->output());
>  
> +    // Note that the testValueTruthyKernel call above may choose to fall through
> +    // to ifFalsy instead of branching there.

Uh.  Doesn't this actually fall through to ifTruthy?  In which case, isn't this exactly backwards?  (And the comment in CodeGenerator.h would be wrong, then, too.)

::: js/src/jit/CodeGenerator.h
@@ +361,5 @@
>      IonScriptCounts *maybeCreateScriptCounts();
>  
> +    // This function behaves like testValueTruthy with the exception that it can
> +    // choose to let control flow fall through when the object isn't truthy, as
> +    // an optimization. Use testValueTruthhy when it's required to branch to one

testValueTruthhy

Comment 8

[Dan Gohman [:sunfish]]

Attachment: test-notv-branch.patch

(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #7)
> Comment on attachment 822920 [details] [diff] [review]
> test-notv-branch.patch
> 
> Review of attachment 822920 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jit/CodeGenerator.cpp
> @@ +4697,5 @@
> >      Label join;
> >      Register output = ToRegister(lir->output());
> >  
> > +    // Note that the testValueTruthyKernel call above may choose to fall through
> > +    // to ifFalsy instead of branching there.
> 
> Uh.  Doesn't this actually fall through to ifTruthy?  In which case, isn't
> this exactly backwards?  (And the comment in CodeGenerator.h would be wrong,
> then, too.)

Yikes, you're right. Attached is a new patch which fixes this. And I added a test which fails under the old patch and passes under the new one.

> ::: js/src/jit/CodeGenerator.h
> @@ +361,5 @@
> >      IonScriptCounts *maybeCreateScriptCounts();
> >  
> > +    // This function behaves like testValueTruthy with the exception that it can
> > +    // choose to let control flow fall through when the object isn't truthy, as
> > +    // an optimization. Use testValueTruthhy when it's required to branch to one
> 
> testValueTruthhy

Fixed.

Comment 9

[Jeff Walden [:Waldo]]

Comment on attachment 830315 [details] [diff] [review]
test-notv-branch.patch

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

::: js/src/jit-test/tests/ion/notV.js
@@ +16,5 @@
> +assertEq(foo([]), false);
> +assertEq(foo(''), true);
> +assertEq(foo(''), true);
> +assertEq(foo('x'), false);
> +assertEq(foo('x'), false);

I'd probably add -0.0, true twice, then -- at the far end -- objectEmulatingUndefined(), true twice as well.  Just for completeness.

::: js/src/jit/CodeGenerator.h
@@ +364,5 @@
>  
>      IonScriptCounts *maybeCreateScriptCounts();
>  
> +    // This function behaves like testValueTruthy with the exception that it can
> +    // choose to let control flow fall through when the object isn't truthy, as

"when the object is truthy"

Comment 10

[Dan Gohman [:sunfish]]

(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #9)
> Comment on attachment 830315 [details] [diff] [review]
> test-notv-branch.patch
> 
> Review of attachment 830315 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jit-test/tests/ion/notV.js
> @@ +16,5 @@
> > +assertEq(foo([]), false);
> > +assertEq(foo(''), true);
> > +assertEq(foo(''), true);
> > +assertEq(foo('x'), false);
> > +assertEq(foo('x'), false);
> 
> I'd probably add -0.0, true twice, then -- at the far end --
> objectEmulatingUndefined(), true twice as well.  Just for completeness.

Done. I also added NaN and a few other things.

> ::: js/src/jit/CodeGenerator.h
> @@ +364,5 @@
> >  
> >      IonScriptCounts *maybeCreateScriptCounts();
> >  
> > +    // This function behaves like testValueTruthy with the exception that it can
> > +    // choose to let control flow fall through when the object isn't truthy, as
> 
> "when the object is truthy"

Fixed.

https://hg.mozilla.org/integration/mozilla-inbound/rev/4fc6f8d8efb4
https://hg.mozilla.org/integration/mozilla-inbound/rev/391a82010f2f

Comment 11

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/4fc6f8d8efb4
https://hg.mozilla.org/mozilla-central/rev/391a82010f2f