Bug 154683 - [DFG][FTL][B3] Support floor and ceil
Summary: [DFG][FTL][B3] Support floor and ceil
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: WebKit Nightly Build
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Yusuke Suzuki
URL:
Keywords:
: 154725 (view as bug list)
Depends on:
Blocks: 153738
  Show dependency treegraph
 
Reported: 2016-02-25 10:15 PST by Yusuke Suzuki
Modified: 2016-03-01 00:09 PST (History)
8 users (show)

See Also:


Attachments
Patch (97.10 KB, patch)
2016-02-26 12:31 PST, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Patch (97.29 KB, patch)
2016-02-26 12:43 PST, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Performance results (64.04 KB, text/plain)
2016-02-27 01:14 PST, Yusuke Suzuki
no flags Details
Patch (111.30 KB, patch)
2016-02-29 11:39 PST, Yusuke Suzuki
fpizlo: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Yusuke Suzuki 2016-02-25 10:15:33 PST
Math.floor and Math.ceil are frequently called. builtin's @toInteger always calls @floor with @abs.
And SunSpider and V8 bench also calls the both (especially, Math.floor).
Similarly to the ArithRound, adding ArithFloor and ArithCeil is nice.

If it is added, we can convert DFG ArithFloor and ArithCeil to Identity if the given value is Int32!
Comment 1 Yusuke Suzuki 2016-02-25 10:18:24 PST
In x86 SSE 4.2 enabled environment, we can use x86 round op for ceil and floor.
This is already used for Math.round implementation.
And adding Floor B3 op is also nice. Ceil is already added to support Round operation. https://bugs.webkit.org/show_bug.cgi?id=152231
Comment 2 Yusuke Suzuki 2016-02-26 10:03:43 PST
*** Bug 154725 has been marked as a duplicate of this bug. ***
Comment 3 Yusuke Suzuki 2016-02-26 12:31:15 PST
Created attachment 272355 [details]
Patch
Comment 4 WebKit Commit Bot 2016-02-26 12:34:39 PST
Attachment 272355 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:4422:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
Total errors found: 1 in 54 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 5 Yusuke Suzuki 2016-02-26 12:43:04 PST
Created attachment 272357 [details]
Patch
Comment 6 WebKit Commit Bot 2016-02-26 12:45:46 PST
Attachment 272357 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:4422:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
Total errors found: 1 in 54 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 7 Yusuke Suzuki 2016-02-26 12:45:57 PST
Comment on attachment 272357 [details]
Patch

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

Added comments for the review.

> Source/JavaScriptCore/b3/B3LowerMacrosAfterOptimizations.cpp:115
> +

if rounding instruction is not supported, we change it to calling the function. This is the same strategy to Ceil.

> Source/JavaScriptCore/b3/B3LowerToAir.cpp:1833
> +        }

Lower to FloorDouble, FloorFloat.

> Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1148
> +            }

New strength reduction case for Ceil. Ceil(Floor(value)) => Floor(value).

> Source/JavaScriptCore/b3/testb3.cpp:3371
> +}

Floor(Ceil(value)) => Ceil(value)

> Source/JavaScriptCore/dfg/DFGGraph.cpp:226
> +        out.print(comma, "Rounding:", node->arithRoundingMode());

Add ArithRoundingMode printing support.

> Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:4429
> +            m_jit.branchConvertDoubleToInt32(resultFPR, resultGPR, failureCases, scratchFPR, shouldCheckNegativeZero(node->arithRoundingMode()));

Emit negative zero check operation only when `shouldCheckNegativeZero(node->arithRoundingMode())` == true.

> Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:4442
> +            if (producesInteger(node->arithRoundingMode()) && !shouldCheckNegativeZero(node->arithRoundingMode())) {

If the negative zero is not considered, we can use `floor(value + 0.5)` for `round(value)`.

> Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp:1886
> +        if (producesInteger(m_node->arithRoundingMode()) && !shouldCheckNegativeZero(m_node->arithRoundingMode())) {

Adding `floor(value + 0.5)` case to FTL.

> Websites/webkit.org/docs/b3/intermediate-representation.html:277
> +

Add new B3 IR, Floor!
Comment 8 Geoffrey Garen 2016-02-26 14:12:10 PST
Comment on attachment 272357 [details]
Patch

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

r=me

Probably good to get Ben or Phil to look at this too.

> Source/JavaScriptCore/b3/B3LowerMacrosAfterOptimizations.cpp:117
> +                double (*floorDouble)(double) = floor;

Does this need a local variable?
Comment 9 Yusuke Suzuki 2016-02-27 01:14:34 PST
Created attachment 272412 [details]
Performance results

Performance results. Looks neutral if Math.round, floor, ceil is not related.
Kraken audio oscillator shows better performance because it includes many Math.round, Math.floor.
Comment 10 Yusuke Suzuki 2016-02-27 01:15:52 PST
Comment on attachment 272357 [details]
Patch

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

Thanks!

>> Source/JavaScriptCore/b3/B3LowerMacrosAfterOptimizations.cpp:117
>> +                double (*floorDouble)(double) = floor;
> 
> Does this need a local variable?

Unnecessary. I'll drop this and use floor directly (And I'll apply the same change to Ceil).
Comment 11 Filip Pizlo 2016-02-29 10:54:30 PST
Comment on attachment 272357 [details]
Patch

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

> Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1191
> +            // Turn this: Floor(Ceil(value))
> +            // Into this: Ceil(value)
> +            if (m_value->child(0)->opcode() == Ceil) {
> +                m_value->replaceWithIdentity(m_value->child(0));
> +                break;
> +            }
> +
> +            // Turn this: Floor(IToD(value))
> +            // Into this: IToD(value)
> +            //
> +            // That works for Int64 because both ARM64 and x86_64
> +            // perform rounding when converting a 64bit integer to double.
> +            if (m_value->child(0)->opcode() == IToD) {
> +                m_value->replaceWithIdentity(m_value->child(0));
> +                break;
> +            }

Please restructure this code in terms
Comment 12 Filip Pizlo 2016-02-29 10:56:07 PST
Comment on attachment 272357 [details]
Patch

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

>> Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1191
>> +            }
> 
> Please restructure this code in terms

Ugh.  I hate bugzilla sometimes.

> Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1192
> +            // Turn this: Floor(Floor(value))
> +            // Into this: Floor(value)
> +            if (m_value->child(0)->opcode() == Floor) {
> +                m_value->replaceWithIdentity(m_value->child(0));
> +                break;
> +            }
> +
> +            // Turn this: Floor(Ceil(value))
> +            // Into this: Ceil(value)
> +            if (m_value->child(0)->opcode() == Ceil) {
> +                m_value->replaceWithIdentity(m_value->child(0));
> +                break;
> +            }
> +
> +            // Turn this: Floor(IToD(value))
> +            // Into this: IToD(value)
> +            //
> +            // That works for Int64 because both ARM64 and x86_64
> +            // perform rounding when converting a 64bit integer to double.
> +            if (m_value->child(0)->opcode() == IToD) {
> +                m_value->replaceWithIdentity(m_value->child(0));
> +                break;
> +            }
> +            break;

Please restructure this code around a single predicate: "is a floating value already rounded?"

You can add it as a method to B3::Value.  Then you can replace all of these rules with:

if (m_value->child(0)->isRounded()) {
    m_value->replaceWithIdentity(m_value->child(0));
    m_changed = true;
}
Comment 13 Filip Pizlo 2016-02-29 10:58:03 PST
Comment on attachment 272357 [details]
Patch

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

> Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1146
> +                m_value->replaceWithIdentity(m_value->child(0));

This is wrong, it doesn't set m_changed to true.

> Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1172
> +                m_value->replaceWithIdentity(m_value->child(0));

This is wrong - it doesn't set m_changed to true.

> Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1179
> +                m_value->replaceWithIdentity(m_value->child(0));

Ditto.

> Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1189
> +                m_value->replaceWithIdentity(m_value->child(0));

Ditto.
Comment 14 Yusuke Suzuki 2016-02-29 11:39:41 PST
Created attachment 272506 [details]
Patch
Comment 15 WebKit Commit Bot 2016-02-29 11:42:46 PST
Attachment 272506 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:4422:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
Total errors found: 1 in 54 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 16 Yusuke Suzuki 2016-02-29 11:47:41 PST
Comment on attachment 272506 [details]
Patch

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

Thanks for reviews! Updated the patch.

> Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1090
> +                replaceWithIdentity(m_value->child(0));

Hm, this also misses `m_change = true`.
To reduce such mistakes, I introduced `replaceWithIdentity(newNode)` member function for this pass.
It peforms `m_value->replaceWithIdentity(newNode)` and set `m_changed = true`.
This is similar to `replaceWithNewValue(newNode)`.

> Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1122
> +            if (m_value->child(0)->isRounded()) {

Restructure Ceil part.

> Source/JavaScriptCore/b3/B3ReduceStrength.cpp:1138
> +            if (m_value->child(0)->isRounded()) {

Restructure Floor part.
Comment 17 Filip Pizlo 2016-02-29 11:53:03 PST
Comment on attachment 272506 [details]
Patch

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

> Source/JavaScriptCore/b3/B3ReduceStrength.cpp:2096
> +    void replaceWithIdentity(Value* newValue)
> +    {
> +        m_value->replaceWithIdentity(newValue);
> +        m_changed = true;
> +    }

Nice!

> Source/JavaScriptCore/b3/B3Value.cpp:366
> +    switch (opcode()) {

Above here, you should ASSERT that isFloat(type()).

> Source/JavaScriptCore/b3/B3Value.cpp:370
> +        return true;

You should add cases for Const32Float and Const64Float, or add a FIXME about adding them.
Comment 18 Yusuke Suzuki 2016-02-29 12:02:35 PST
Comment on attachment 272506 [details]
Patch

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

Thanks!

>> Source/JavaScriptCore/b3/B3Value.cpp:366
>> +    switch (opcode()) {
> 
> Above here, you should ASSERT that isFloat(type()).

Oh! That's nice. Inserted.

>> Source/JavaScriptCore/b3/B3Value.cpp:370
>> +        return true;
> 
> You should add cases for Const32Float and Const64Float, or add a FIXME about adding them.

That's nice. When ConstFloat / ConstDouble comes, we can check the constant value is rounded or not by `constValue == ceil(constValue)` (double case).
Comment 19 Yusuke Suzuki 2016-02-29 18:30:43 PST
Committed r197380: <http://trac.webkit.org/changeset/197380>
Comment 20 Yusuke Suzuki 2016-03-01 00:09:03 PST
Originally this patch is introduced for @toInteger. But it also optimizes kraken-oscillator! (Since it calls Math.round and Math.floor a lot!)
https://arewefastyet.com/#machine=29&view=single&suite=kraken&subtest=oscillator