Bug 154683 – [DFG][FTL][B3] Support floor and ceil

• Status: RESOLVED
• Resolution: FIXED
• Component: JavaScriptCore

[Yusuke Suzuki]

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!

[Yusuke Suzuki]

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

[Yusuke Suzuki]

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

[Yusuke Suzuki]

Created attachment 272355 [details]
Patch

[WebKit Commit Bot]

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.

[Yusuke Suzuki]

Created attachment 272357 [details]
Patch

[WebKit Commit Bot]

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.

[Yusuke Suzuki]

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!

[Geoffrey Garen]

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?

[Yusuke Suzuki]

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.

[Yusuke Suzuki]

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).

[Filip Pizlo]

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

[Filip Pizlo]

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;
}

[Filip Pizlo]

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.

[Yusuke Suzuki]

Created attachment 272506 [details]
Patch

[WebKit Commit Bot]

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.

[Yusuke Suzuki]

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.

[Filip Pizlo]

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.

[Yusuke Suzuki]

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).

[Yusuke Suzuki]

Committed r197380: <http://trac.webkit.org/changeset/197380>

[Yusuke Suzuki]

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