Bug 150721

Summary:

B3->Air lowering should have a story for compare-branch fusion

Product:

WebKit

Reporter:

Filip Pizlo <fpizlo>

Component:

JavaScriptCore

Assignee:

Filip Pizlo <fpizlo>

Status:

RESOLVED FIXED

Severity:

Normal

CC:

barraclough, benjamin, commit-queue, ggaren, mark.lam, mhahnenb, msaboff, nrotem, oliver, saam, sam

Priority:

Version:

WebKit Nightly Build

Hardware:

All

OS:

All

Bug Depends on:

150720

Bug Blocks:

150279, 150903, 150954, 150958

Attachments:

Description	Flags
work in progress	none
more things	none
at least it compiles	none
more	none
more tests, fixed bugs	none
the patch	ggaren: review+
patch for landing	none

Description Filip Pizlo 2015-10-30 10:43:05 PDT

Thingy.

Comment 1 Filip Pizlo 2015-11-01 11:51:36 PST

One way to do this would be to have a comparison selector that takes as an argument the set of possible comparing Air opcodes.  For example it might be something like:

struct Opcodes {
    Opcode compare8;
    Opcode compare16;
    Opcode compare32;
    Opcode compare64;
    Opcode test8;
    Opcode test16;
    Opcode test32;
    Opcode test64;
    Opcode compareDouble8;
    Opcode compareDouble16;
    Opcode compareDouble32;
    Opcode compareDouble64;
};

The comparison selector could then either produce an Inst or an array of Insts that conduct the comparison using whatever compare operations the caller wanted. It can use isValidForm() to decide which Insts are valid, so we can be sure that it only produces valid ones.

Comment 2 Filip Pizlo 2015-11-04 13:43:29 PST

*** Bug 150726 has been marked as a duplicate of this bug. ***

Comment 3 Filip Pizlo 2015-11-04 13:44:30 PST

Created attachment 264807 [details]
work in progress

OMG

Comment 4 Filip Pizlo 2015-11-04 14:09:57 PST

*** Bug 150727 has been marked as a duplicate of this bug. ***

Comment 5 Filip Pizlo 2015-11-04 15:12:50 PST

Created attachment 264820 [details]
more things

Comment 6 Filip Pizlo 2015-11-04 16:52:39 PST

Created attachment 264827 [details]
at least it compiles

Comment 7 Filip Pizlo 2015-11-04 20:28:09 PST

Created attachment 264842 [details]
more

Added constant folding rules

Comment 8 Filip Pizlo 2015-11-04 21:49:27 PST

Created attachment 264846 [details]
more tests, fixed bugs

I still have a lot more tests to write.

Comment 9 Filip Pizlo 2015-11-05 12:15:26 PST

Created attachment 264877 [details]
the patch

Comment 10 WebKit Commit Bot 2015-11-05 12:18:29 PST

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


ERROR: Source/JavaScriptCore/b3/testb3.cpp:2443:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2444:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2498:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2503:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2514:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2519:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2530:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2535:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2546:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2549:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2564:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2569:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2579:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2582:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2592:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2597:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2605:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2608:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2622:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2627:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:3127:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/B3CheckSpecial.h:69:  The parameter name "inst" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/b3/B3CheckSpecial.h:112:  The parameter name "key" adds no information, so it should be removed.  [readability/parameter_name] [5]
Total errors found: 23 in 29 files


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

Comment 11 Geoffrey Garen 2015-11-05 12:36:10 PST

Comment on attachment 264877 [details]
the patch

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

r=me

> Source/JavaScriptCore/b3/B3LowerToAir.cpp:836
> +                // First handle compare's that involve fewer bits than B3's type system supports.

compares

> Source/JavaScriptCore/b3/B3LowerToAir.cpp:864
> +                // Now handle compare's that involve a load and an immediate.

compares

> Source/JavaScriptCore/b3/B3LowerToAir.cpp:870
> +                // Now handle compare's that involve a load. It's not obvious that it's better to

compares

> Source/JavaScriptCore/b3/B3LowerToAir.cpp:883
> +                // Now handle compare's that involve an immediate and a tmp.

compares

Comment 12 Filip Pizlo 2015-11-05 12:38:15 PST

Created attachment 264879 [details]
patch for landing

Comment 13 WebKit Commit Bot 2015-11-05 12:41:13 PST

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


ERROR: Source/JavaScriptCore/b3/testb3.cpp:2443:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2444:  Consider using CHECK_EQ instead of CHECK(a == b)  [readability/check] [2]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2498:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2503:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2514:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2519:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2530:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2535:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2546:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2549:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2564:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2569:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2579:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2582:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2592:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2597:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2605:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2608:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2622:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:2627:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/b3/testb3.cpp:3127:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
Total errors found: 21 in 29 files


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

Comment 14 WebKit Commit Bot 2015-11-05 13:52:00 PST

Comment on attachment 264879 [details]
patch for landing

Clearing flags on attachment: 264879

Committed r192072: <http://trac.webkit.org/changeset/192072>

Comment 15 WebKit Commit Bot 2015-11-05 13:52:05 PST

All reviewed patches have been landed.  Closing bug.

Comment 16 Benjamin Poulain 2015-11-05 14:47:09 PST

Comment on attachment 264879 [details]
patch for landing

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

Quick read:

> Source/JavaScriptCore/b3/B3CheckSpecial.h:103
> +            // Seriously, we don't need to be smart here. It just doesn't matter.
> +            return m_opcode + m_numArgs;

You can use WTF::PairHash() for a safe hash of two integers.

I don't think the comment is very helpful since it does not say why it does not matter.

> Source/JavaScriptCore/b3/B3CheckSpecial.h:153
> +    // I don't want to think about this very hard, it's not worth it. I'm a be conservative.

"I'm a be"

> Source/JavaScriptCore/b3/B3LowerToAir.cpp:180
> +        ArgPromise(const Arg& arg, Value* valueToLock = nullptr)

explicit?

> Source/JavaScriptCore/b3/B3LowerToAir.cpp:223
> +        Value* m_value;

    Value* m_value { nullptr; }
For the ArgPromise() { } constructor.

> Source/JavaScriptCore/b3/B3LowerToAir.cpp:399
>              return Arg();

The return should be ArgPromise() instead of Arg() now.

> Source/JavaScriptCore/b3/B3LowerToAir.cpp:786
> +            if (!canBeInternal(value) && value != currentValue)

When is "value != currentValue" ever false?

A Branch can reference itself?

> Source/JavaScriptCore/b3/B3LowerToAir.cpp:935
> +                Arg rightImm = imm(right);

Not sure you need to bother with this. In other places, you expect the output to be canonicalized by ReduceStrength.

> Source/JavaScriptCore/b3/B3LowerToAir.cpp:938
> +                    Arg::Width width, const ArgPromise& left, const ArgPromise& right) -> Inst {

This would be more readable on the previous line.
Here is looks a bit like the first statement of the lambda.

> Source/JavaScriptCore/b3/B3LowerToAir.cpp:979
> +                // 32-bit test. Note that this spits on the grave of inferior endians, such as the
> +                // big one.

lol

> Source/JavaScriptCore/b3/B3LowerToAir.cpp:1017
> +        if (canBeInternal(value) || value == currentValue) {

When is "value == currentValue" true?

> Source/JavaScriptCore/b3/B3LowerToAir.cpp:1029
> +        // Sometimes this is the only form of test available. We prefer not to use this because
> +        // it's less canonical.
> +        return test(width, resCond, tmpPromise(value), tmpPromise(value));

IMHO, we should CRASH() if we don't get a valid Inst out of this.

> Source/JavaScriptCore/b3/B3ReduceStrength.cpp:430
> +            

spaaaaace.

Comment 17 Filip Pizlo 2015-11-05 14:53:52 PST

(In reply to comment #16)
> Comment on attachment 264879 [details]
> patch for landing
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=264879&action=review
> 
> Quick read:
> 
> > Source/JavaScriptCore/b3/B3CheckSpecial.h:103
> > +            // Seriously, we don't need to be smart here. It just doesn't matter.
> > +            return m_opcode + m_numArgs;
> 
> You can use WTF::PairHash() for a safe hash of two integers.
> 
> I don't think the comment is very helpful since it does not say why it does
> not matter.

Because there will not be enough unique CheckSpecial::Keys.

> 
> > Source/JavaScriptCore/b3/B3CheckSpecial.h:153
> > +    // I don't want to think about this very hard, it's not worth it. I'm a be conservative.
> 
> "I'm a be"
> 
> > Source/JavaScriptCore/b3/B3LowerToAir.cpp:180
> > +        ArgPromise(const Arg& arg, Value* valueToLock = nullptr)
> 
> explicit?

I want to be able to turn an Arg into an ArgPromise.  We use this for passing imm().

> 
> > Source/JavaScriptCore/b3/B3LowerToAir.cpp:223
> > +        Value* m_value;
> 
>     Value* m_value { nullptr; }
> For the ArgPromise() { } constructor.
> 
> > Source/JavaScriptCore/b3/B3LowerToAir.cpp:399
> >              return Arg();
> 
> The return should be ArgPromise() instead of Arg() now.

Oh, true.

> 
> > Source/JavaScriptCore/b3/B3LowerToAir.cpp:786
> > +            if (!canBeInternal(value) && value != currentValue)
> 
> When is "value != currentValue" ever false?

When we fail to fuse the compare/branch.  We go down this path when we're compiling a LessThan directly, for example.

> 
> A Branch can reference itself?
> 
> > Source/JavaScriptCore/b3/B3LowerToAir.cpp:935
> > +                Arg rightImm = imm(right);
> 
> Not sure you need to bother with this. In other places, you expect the
> output to be canonicalized by ReduceStrength.

Oops, good point.  Filed: https://bugs.webkit.org/show_bug.cgi?id=150954

> 
> > Source/JavaScriptCore/b3/B3LowerToAir.cpp:938
> > +                    Arg::Width width, const ArgPromise& left, const ArgPromise& right) -> Inst {
> 
> This would be more readable on the previous line.
> Here is looks a bit like the first statement of the lambda.
> 
> > Source/JavaScriptCore/b3/B3LowerToAir.cpp:979
> > +                // 32-bit test. Note that this spits on the grave of inferior endians, such as the
> > +                // big one.
> 
> lol
> 
> > Source/JavaScriptCore/b3/B3LowerToAir.cpp:1017
> > +        if (canBeInternal(value) || value == currentValue) {
> 
> When is "value == currentValue" true?
> 
> > Source/JavaScriptCore/b3/B3LowerToAir.cpp:1029
> > +        // Sometimes this is the only form of test available. We prefer not to use this because
> > +        // it's less canonical.
> > +        return test(width, resCond, tmpPromise(value), tmpPromise(value));
> 
> IMHO, we should CRASH() if we don't get a valid Inst out of this.

We will, in the validation.  It's true that we could add asserts here.

> 
> > Source/JavaScriptCore/b3/B3ReduceStrength.cpp:430
> > +            
> 
> spaaaaace.