Bug 152198 - B3->Air compare-branch fusion should fuse even if the result of the comparison is used more than once
Summary: B3->Air compare-branch fusion should fuse even if the result of the compariso...
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: WebKit Nightly Build
Hardware: All All
: P2 Normal
Assignee: Filip Pizlo
URL:
Keywords:
Depends on:
Blocks: 150279
  Show dependency treegraph
 
Reported: 2015-12-11 16:03 PST by Filip Pizlo
Modified: 2015-12-14 11:14 PST (History)
12 users (show)

See Also:


Attachments
work in progress (17.27 KB, patch)
2015-12-12 15:13 PST, Filip Pizlo
no flags Details | Formatted Diff | Diff
the patch (30.62 KB, patch)
2015-12-12 18:46 PST, Filip Pizlo
no flags Details | Formatted Diff | Diff
the patch (31.12 KB, patch)
2015-12-12 18:48 PST, Filip Pizlo
no flags Details | Formatted Diff | Diff
the patch (30.54 KB, patch)
2015-12-12 18:50 PST, Filip Pizlo
no flags Details | Formatted Diff | Diff
the patch (39.10 KB, patch)
2015-12-13 19:22 PST, Filip Pizlo
no flags Details | Formatted Diff | Diff
tests work in progress (47.52 KB, patch)
2015-12-13 19:38 PST, Filip Pizlo
no flags Details | Formatted Diff | Diff
the patch (56.27 KB, patch)
2015-12-13 20:26 PST, Filip Pizlo
benjamin: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Filip Pizlo 2015-12-11 16:03:40 PST
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.
Comment 1 Filip Pizlo 2015-12-12 15:13:33 PST
Created attachment 267245 [details]
work in progress
Comment 2 Filip Pizlo 2015-12-12 18:46:38 PST
Created attachment 267249 [details]
the patch

I'm still writing tests but other than that, it's ready for review.
Comment 3 Filip Pizlo 2015-12-12 18:48:29 PST
Created attachment 267250 [details]
the patch

Rebased.  Still writing tests.
Comment 4 Filip Pizlo 2015-12-12 18:50:41 PST
Created attachment 267251 [details]
the patch

Rebased but without the DFGCommon.h change.  Still writing more tests.
Comment 5 WebKit Commit Bot 2015-12-12 18:53:38 PST
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.
Comment 6 Filip Pizlo 2015-12-13 19:22:47 PST
Created attachment 267277 [details]
the patch

Added more stuff, now I need to add more tests.
Comment 7 WebKit Commit Bot 2015-12-13 19:25:47 PST
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.
Comment 8 Filip Pizlo 2015-12-13 19:38:51 PST
Created attachment 267278 [details]
tests work in progress
Comment 9 Filip Pizlo 2015-12-13 20:26:34 PST
Created attachment 267280 [details]
the patch
Comment 10 WebKit Commit Bot 2015-12-13 20:27:47 PST
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.
Comment 11 Benjamin Poulain 2015-12-14 10:14:44 PST
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.
Comment 12 Filip Pizlo 2015-12-14 11:09:30 PST
(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.
Comment 13 Filip Pizlo 2015-12-14 11:14:18 PST
Landed in http://trac.webkit.org/changeset/194039