Bug 152478 – Optimize Air::TmpWidth analysis in IRC

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

[Filip Pizlo]

We can do this if we think that we need to reduce compile times further, but it doesn't currently appear to be a major bottleneck.

[Robin Morisset]

I just measured, and we only spend 0.6ms in TmpWidth::recompute() in all of JetStream2. So this is beyond negligible. Optimizing accesses to the TmpWidth on the other hand may still matter. But the computation itself is basically free.

[Robin Morisset]

I got the computation wrong: it is about 180ms and not 0.6ms (it seemed miraculous). Still a fairly small part of the register allocator (> 3.5s).

[Robin Morisset]

Created attachment 380358 [details]
Patch

Simple patch that optimizes AirTmpWidth, saving 100ms our of 3.4s in register allocation in JetStream2.

[Robin Morisset]

Created attachment 400000 [details]
Patch

simple rebase

[Sam Weinig]

Comment on attachment 400000 [details]
Patch

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

> Source/JavaScriptCore/b3/air/AirTmpWidth.cpp:66
> +    widthsVector.clear();
> +    widthsVector.resize(AbsoluteTmpMapper<bank>::absoluteIndex(code.numTmps(bank)));

I think this clear() may be unnecessary and not ideal as it can destroy the Vectors buffer. Since you are going to write to all values I the vector anyway, just resizing should be fine and could allow reuse of the underlying buffer,

[Mark Lam]

Comment on attachment 400000 [details]
Patch

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

Some comments and questions for now.  Also, the patch seems to need a rebase already.

> Source/JavaScriptCore/b3/air/AirAllocateRegistersByGraphColoring.cpp:2207
> +    if (debug)

Why not use traceDebug instead?

> Source/JavaScriptCore/b3/air/AirTmpWidth.h:57
> -        auto iter = m_width.find(tmp);
> -        if (iter == m_width.end())
> -            return minimumWidth(Arg(tmp).bank());
> -        return std::min(iter->value.use, iter->value.def);
> +        Widths widths = getWidths(tmp);
> +        return std::min(widths.use, widths.def);

Your implementation isn't equivalent.  The old code allows for the tmp to not be found.  In that case, this function returns minimumWidth(Arg(tmp).bank()).  In your case, you would return a result based on an uninitialized Widths in the vectors.  Also, is it possible to ask for a Widths for a tmp whose index is beyond the bounds of the current vector size?  That was not a problem with the old HashMap solution but may be for the vector.

Are you guaranteed that all the slows in the vector has been fully initialized before any of these accessors are called?  If so, can we assert this some how?

Ditto for the next few cases below.

> Source/JavaScriptCore/b3/air/AirTmpWidth.h:98
> +        Widths(Width useArg, Width defArg)
> +        {
> +            use = useArg;
> +            def = defArg;
> +        }

Why to use constructor initialization form?

    Widths(Width useArg, Width defArg)
        : use(useArg)
        , def(defArg)
    { }

> Source/JavaScriptCore/b3/air/AirTmpWidth.h:106
> +    Widths& getWidths(Tmp tmp)

Webkit style is to name this "widths" instead.  We normally don't use "get" for accessors.

> Source/JavaScriptCore/b3/air/AirTmpWidth.h:117
> +    const Widths& getWidths(Tmp tmp) const

Ditto.

> Source/JavaScriptCore/b3/air/AirTmpWidth.h:126
> +        if (tmp.isGP()) {
> +            unsigned index = AbsoluteTmpMapper<GP>::absoluteIndex(tmp);
> +            ASSERT(index < m_widthGP.size());
> +            return m_widthGP[index];
> +        }
> +        unsigned index = AbsoluteTmpMapper<FP>::absoluteIndex(tmp);
> +        ASSERT(index < m_widthFP.size());
> +        return m_widthFP[index];

Just do this instead:
    return const_cast<TmpWidth*>(this)->widths(tmp);

> Source/JavaScriptCore/b3/air/AirTmpWidth.h:142
> +    Vector<Widths>& getWidthsVector(Bank bank)

WebKit style: use widthsVector instead of getWidthsVector.

> Source/JavaScriptCore/b3/air/AirTmpWidth.h:149
> +    Vector<Widths> m_widthGP;

The minimumWidth for GP is Width8, which happens to be of value 0.  So, this might just works.

> Source/JavaScriptCore/b3/air/AirTmpWidth.h:150
> +    Vector<Widths> m_widthFP;

The minimumWidth for FP is WidthFP, which happens to be of value 2.  So, this doesn't just work if not initialized.

[Robin Morisset]

Comment on attachment 400000 [details]
Patch

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

>> Source/JavaScriptCore/b3/air/AirTmpWidth.cpp:66
>> +    widthsVector.resize(AbsoluteTmpMapper<bank>::absoluteIndex(code.numTmps(bank)));
> 
> I think this clear() may be unnecessary and not ideal as it can destroy the Vectors buffer. Since you are going to write to all values I the vector anyway, just resizing should be fine and could allow reuse of the underlying buffer,

Fixed.

>> Source/JavaScriptCore/b3/air/AirTmpWidth.h:57
>> +        return std::min(widths.use, widths.def);
> 
> Your implementation isn't equivalent.  The old code allows for the tmp to not be found.  In that case, this function returns minimumWidth(Arg(tmp).bank()).  In your case, you would return a result based on an uninitialized Widths in the vectors.  Also, is it possible to ask for a Widths for a tmp whose index is beyond the bounds of the current vector size?  That was not a problem with the old HashMap solution but may be for the vector.
> 
> Are you guaranteed that all the slows in the vector has been fully initialized before any of these accessors are called?  If so, can we assert this some how?
> 
> Ditto for the next few cases below.

The case of an index beyond the vector size is already covered by ASSERTs in getWidths.
As for the uninitialized case, it cannot happen as I initialize the vectors at the very beginning of recompute, which in turn is called in the constructor. Not sure how to ASSERT that we will always call recompute before accessing the data?

>> Source/JavaScriptCore/b3/air/AirTmpWidth.h:98
>> +        }
> 
> Why to use constructor initialization form?
> 
>     Widths(Width useArg, Width defArg)
>         : use(useArg)
>         , def(defArg)
>     { }

Fixed.

>> Source/JavaScriptCore/b3/air/AirTmpWidth.h:106
>> +    Widths& getWidths(Tmp tmp)
> 
> Webkit style is to name this "widths" instead.  We normally don't use "get" for accessors.

Fixed.

>> Source/JavaScriptCore/b3/air/AirTmpWidth.h:126
>> +        return m_widthFP[index];
> 
> Just do this instead:
>     return const_cast<TmpWidth*>(this)->widths(tmp);

Thanks!

>> Source/JavaScriptCore/b3/air/AirTmpWidth.h:142
>> +    Vector<Widths>& getWidthsVector(Bank bank)
> 
> WebKit style: use widthsVector instead of getWidthsVector.

Fixed.

>> Source/JavaScriptCore/b3/air/AirTmpWidth.h:149
>> +    Vector<Widths> m_widthGP;
> 
> The minimumWidth for GP is Width8, which happens to be of value 0.  So, this might just works.

Should I add a comment here that they are initialized in recompute, which is called in the constructor?

[Robin Morisset]

Created attachment 401969 [details]
Patch

[EWS]

Committed r263116: <https://trac.webkit.org/changeset/263116>

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

[Radar WebKit Bug Importer]

<rdar://problem/64421515>