Bug 228052 – AirFixObviousSpills should be optimized

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

[Robin Morisset]

It has two problems:
- It visit blocks even when their state at head has not changed
- Worse, the "merge()" function on its State has quadratic time complexity
The result of these is that it is the 5th slowest phase on average in JetStream2, at 390ms on an M1 MBP (for comparison, all of Air is 2.2s and all of B3+Air is 3.3s), and we spend 105ms in it for a single function as a result of the quadratic blow-up in merge().
Both problems are fairly easy to fix.

[Robin Morisset]

Created attachment 433739 [details]
Patch

[Robin Morisset]

Created attachment 433744 [details]
Patch

Fix style nitpicks

[Radar WebKit Bug Importer]

<rdar://problem/81064637>

[Robin Morisset]

Created attachment 434786 [details]
Patch

[Robin Morisset]

Created attachment 442200 [details]
Patch

just rebased.

[Yusuke Suzuki]

Comment on attachment 442200 [details]
Patch

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

r=me

> Source/JavaScriptCore/b3/air/AirFixObviousSpills.cpp:92
> +                    // Before we call merge we must make sure that the two states are sorted.
> +                    m_state.sort();

Do we need to call `sort()` inside this loop? Can we sort() before starting this loop?

> Source/JavaScriptCore/b3/air/AirFixObviousSpills.cpp:-568
> +                    it = std::find_if_not(it, end, [&] (const T& otherAlias) {
> +                        return otherAlias < alias;
> +                    });
> +                    if (it == end)
>                          return true;
> -                    return false;

How about using std::lower_bound or the other binary-searching since other is also sorted?

[Robin Morisset]

Thanks for the review.

> > Source/JavaScriptCore/b3/air/AirFixObviousSpills.cpp:92
> > +                    // Before we call merge we must make sure that the two states are sorted.
> > +                    m_state.sort();
> 
> Do we need to call `sort()` inside this loop? Can we sort() before starting
> this loop?

Good idea, it is a small improvement (total time 139-146ms before, 133-136ms after)

> > Source/JavaScriptCore/b3/air/AirFixObviousSpills.cpp:-568
> > +                    it = std::find_if_not(it, end, [&] (const T& otherAlias) {
> > +                        return otherAlias < alias;
> > +                    });
> > +                    if (it == end)
> >                          return true;
> > -                    return false;
> 
> How about using std::lower_bound or the other binary-searching since other
> is also sorted?

I tried this, and it turned out to be measurably slower, probably we rarely skip over enough elements of the vector to be worth the branch mispredictions.

[Robin Morisset]

Created attachment 444781 [details]
Patch

[EWS]

Committed r286053 (244440@main): <https://commits.webkit.org/244440@main>

All reviewed patches have been landed. Closing bug and clearing flags on attachment 444781 [details].