Bug 152198 – B3->Air compare-branch fusion should fuse even if the result of the comparison is used more than once

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Filip Pizlo]

This code:

    cmp
    setXX
    movzx -> put result in %res
    test %res, %res
    jnz
    ...
    test %res, %res
    jnz

is always worse than this code:

    cmp
    jXX
    ...
    cmp
    jXX

But our instruction selector emits the worse code because it's afraid of emitting the compare instruction more than once.  It's also afraid of duplicating loads.  The solution is:

- Don't be afraid of duplicating comparisons if you're emitting a branch, since for a shared comparison result, the branch will have to do a second comparison anyway.
- When we decide to match a shared comparison we could simply disable load fusion.

[Filip Pizlo]

Created attachment 267245 [details]
work in progress

[Filip Pizlo]

Created attachment 267249 [details]
the patch

I'm still writing tests but other than that, it's ready for review.

[Filip Pizlo]

Created attachment 267250 [details]
the patch

Rebased.  Still writing tests.

[Filip Pizlo]

Created attachment 267251 [details]
the patch

Rebased but without the DFGCommon.h change.  Still writing more tests.

[WebKit Commit Bot]

Attachment 267251 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/b3/testb3.cpp:5720:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5722:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5732:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5734:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5749:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5749:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5751:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5751:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5753:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5755:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5757:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5798:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5800:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5813:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5815:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5831:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5833:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5835:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5837:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5839:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5842:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5844:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5846:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5848:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5850:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
Total errors found: 25 in 6 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Filip Pizlo]

Created attachment 267277 [details]
the patch

Added more stuff, now I need to add more tests.

[WebKit Commit Bot]

Attachment 267277 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/b3/B3LowerToAir.cpp:993:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5724:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5726:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5736:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5738:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5753:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5753:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5755:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5755:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5757:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5759:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5761:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5802:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5804:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5817:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5819:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5835:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5837:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5839:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5841:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5843:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5846:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5848:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5850:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5852:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5854:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
Total errors found: 26 in 8 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Filip Pizlo]

Created attachment 267278 [details]
tests work in progress

[Filip Pizlo]

Created attachment 267280 [details]
the patch

[WebKit Commit Bot]

Attachment 267280 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/b3/B3LowerToAir.cpp:993:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5728:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5730:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5740:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5742:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5757:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5757:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5759:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5759:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5761:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5763:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5765:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5806:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5808:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5821:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5823:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5839:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5841:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5843:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5845:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5847:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5850:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5852:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5854:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5856:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:5858:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
Total errors found: 26 in 7 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Benjamin Poulain]

Comment on attachment 267280 [details]
the patch

View in context: https://bugs.webkit.org/attachment.cgi?id=267280&action=review

Quick review, some comments:

> Source/JavaScriptCore/b3/B3LowerToAir.cpp:917
> +        // FusionResult prepareToFuse(value): Call this when you thing that you would like to fuse

typo: thing

> Source/JavaScriptCore/b3/B3LowerToAir.cpp:1000
>          // Chew through any negations. It's not strictly necessary for this to be a loop, but we like
>          // to follow the rule that the instruction selector reduces strength whenever it doesn't
>          // require making things more complicated.

Need update, the loop is no longer only about negation.

> Source/JavaScriptCore/b3/B3LowerToAir.cpp:1598
> +                appendUnOp<ZeroExtend8To32, ZeroExtend8To32>(m_value->child(0));

Shouldn't the second be ZeroExtend8To64?

The Intel doc is not super clear about what happens without the Rex byte here.

> Source/JavaScriptCore/b3/B3LowerToAir.cpp:1603
> +                appendUnOp<ZeroExtend16To32, ZeroExtend16To32>(m_value->child(0));

Ditto.

> Source/JavaScriptCore/b3/B3LowerToAir.cpp:1607
> +            if (m_value->child(1)->isInt(0xffffffff)) {

This is fishy, strength reduction should have simplified this case.

We don't want to repeat every case we have in ReduceStrength.

[Filip Pizlo]

(In reply to comment #11)
> Comment on attachment 267280 [details]
> the patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=267280&action=review
> 
> Quick review, some comments:
> 
> > Source/JavaScriptCore/b3/B3LowerToAir.cpp:917
> > +        // FusionResult prepareToFuse(value): Call this when you thing that you would like to fuse
> 
> typo: thing

Fixed.

> 
> > Source/JavaScriptCore/b3/B3LowerToAir.cpp:1000
> >          // Chew through any negations. It's not strictly necessary for this to be a loop, but we like
> >          // to follow the rule that the instruction selector reduces strength whenever it doesn't
> >          // require making things more complicated.
> 
> Need update, the loop is no longer only about negation.

It never was about negations, I meant "inversions" - both BitXor and Equal(_, 0) are inversions.  I'll change the comment.

> 
> > Source/JavaScriptCore/b3/B3LowerToAir.cpp:1598
> > +                appendUnOp<ZeroExtend8To32, ZeroExtend8To32>(m_value->child(0));
> 
> Shouldn't the second be ZeroExtend8To64?

No, that would be a waste of a REX byte.

> 
> The Intel doc is not super clear about what happens without the Rex byte
> here.

32-bit operations zero-extend any registers that they def.

> 
> > Source/JavaScriptCore/b3/B3LowerToAir.cpp:1603
> > +                appendUnOp<ZeroExtend16To32, ZeroExtend16To32>(m_value->child(0));
> 
> Ditto.
> 
> > Source/JavaScriptCore/b3/B3LowerToAir.cpp:1607
> > +            if (m_value->child(1)->isInt(0xffffffff)) {
> 
> This is fishy, strength reduction should have simplified this case.
> 
> We don't want to repeat every case we have in ReduceStrength.

I'll remove it.

[Filip Pizlo]

Landed in http://trac.webkit.org/changeset/194039