Bug 170110 – DFG and B3 SSA conversion should use a faster dominance frontier calculator

• Status: RESOLVED
• Resolution: WONTFIX
• Component: JavaScriptCore

[Filip Pizlo]

Patch forthcoming.

[Filip Pizlo]

Created attachment 305436 [details]
work in progress

[Filip Pizlo]

Created attachment 305439 [details]
it compiles!

[Filip Pizlo]

Created attachment 305442 [details]
the patch

[Build Bot]

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


ERROR: Source/JavaScriptCore/dfg/DFGDominanceFrontiers.h:47:  Comma should be at the beginning of the line in a member initialization list.  [whitespace/init] [4]
ERROR: Source/JavaScriptCore/b3/B3DominanceFrontiers.h:42:  Comma should be at the beginning of the line in a member initialization list.  [whitespace/init] [4]
ERROR: Source/JavaScriptCore/b3/B3DominanceFrontiers.h:43:  Comma should be at the beginning of the line in a member initialization list.  [whitespace/init] [4]
Total errors found: 3 in 19 files


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

[Saam Barati]

Comment on attachment 305442 [details]
the patch

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

r=me. Just style comments below.

> Source/JavaScriptCore/ChangeLog:9
> +        precomputes all dominance frontiers to make them much faster to query. This is a 2.5% overall

Awesome!

> Source/JavaScriptCore/b3/B3SSACalculator.h:113
> +        m_dominanceFrontiers = &m_proc.dominanceFrontiers();

Style: Why does this need to be a member variable?

> Source/WTF/wtf/DominanceFrontiers.h:46
> +        for (unsigned blockIndex = m_graph.numNodes(); blockIndex--;) {

Maybe it's worth a link to where this algorithm is described, something like: http://www.hipersoft.rice.edu/grads/publications/dom14.pdf ?

> Source/WTF/wtf/DominanceFrontiers.h:51
> +            m_iterationSet.clear();

Maybe it's also worth clearing this at after the last iteration of the loop?

> Source/WTF/wtf/DominanceFrontiers.h:58
> +                    [&] (typename Graph::Node dominatorBlock) {
> +                        if (!m_iterationSet.add(m_graph.index(dominatorBlock)))
> +                            return;

If we have already seen this, we've already seen all its dominators too. Maybe it's worth having forAllDominatorsOf take an IterationStatus so we can return early here and cut off the entire iteration to prevent repeated hash set accesses?

> Source/WTF/wtf/Vector.h:965
> +template<typename Func>
> +void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::forEach(const Func& func) const
> +{
> +    size_t size = this->size();
> +    for (size_t i = 0; i < size; ++i)
> +        func(Base::buffer()[i]);
> +}
> +
> +template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
> +template<typename Func>
> +void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::forEach(const Func& func)
> +{
> +    size_t size = this->size();
> +    for (size_t i = 0; i < size; ++i)
> +        func(Base::buffer()[i]);
> +}

Style: Maybe this should be a free function?

[Filip Pizlo]

(In reply to Saam Barati from comment #5)
> Comment on attachment 305442 [details]
> the patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=305442&action=review
> 
> r=me. Just style comments below.
> 
> > Source/JavaScriptCore/ChangeLog:9
> > +        precomputes all dominance frontiers to make them much faster to query. This is a 2.5% overall
> 
> Awesome!
> 
> > Source/JavaScriptCore/b3/B3SSACalculator.h:113
> > +        m_dominanceFrontiers = &m_proc.dominanceFrontiers();
> 
> Style: Why does this need to be a member variable?

Fixed.

> 
> > Source/WTF/wtf/DominanceFrontiers.h:46
> > +        for (unsigned blockIndex = m_graph.numNodes(); blockIndex--;) {
> 
> Maybe it's worth a link to where this algorithm is described, something
> like: http://www.hipersoft.rice.edu/grads/publications/dom14.pdf ?

I'm not using that algorithm.  I don't know what link to use for this algorithm, because I just came up with it on my own.

> 
> > Source/WTF/wtf/DominanceFrontiers.h:51
> > +            m_iterationSet.clear();
> 
> Maybe it's also worth clearing this at after the last iteration of the loop?

Clearing does not release any memory, so it's not profitable to do that.

> 
> > Source/WTF/wtf/DominanceFrontiers.h:58
> > +                    [&] (typename Graph::Node dominatorBlock) {
> > +                        if (!m_iterationSet.add(m_graph.index(dominatorBlock)))
> > +                            return;
> 
> If we have already seen this, we've already seen all its dominators too.
> Maybe it's worth having forAllDominatorsOf take an IterationStatus so we can
> return early here and cut off the entire iteration to prevent repeated hash
> set accesses?

It's easier to use Dominators<>::idom directly and write a for loop.  Ima try that.

> 
> > Source/WTF/wtf/Vector.h:965
> > +template<typename Func>
> > +void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::forEach(const Func& func) const
> > +{
> > +    size_t size = this->size();
> > +    for (size_t i = 0; i < size; ++i)
> > +        func(Base::buffer()[i]);
> > +}
> > +
> > +template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity>
> > +template<typename Func>
> > +void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::forEach(const Func& func)
> > +{
> > +    size_t size = this->size();
> > +    for (size_t i = 0; i < size; ++i)
> > +        func(Base::buffer()[i]);
> > +}
> 
> Style: Maybe this should be a free function?

Could be.  It made sense to me to do it as a member because it uses Vector guts.

[Filip Pizlo]

Holy cow, after I landed the liveness pruning change, this stopped being a speed-up!

I think that our use of liveness pruning in all of our SSA calculators means that we probably don't want this change.

[Filip Pizlo]

Created attachment 305445 [details]
patch I would have landed

[Filip Pizlo]

This isn't profitable because liveness pruning is awesome.