Bug 170111 – B3::fixSSA should do liveness pruning

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Filip Pizlo]

Patch forthcoming.

[Filip Pizlo]

Created attachment 305440 [details]
it begins

First step: make AirLiveness available to B3.

[Filip Pizlo]

The fact that we don't do this is probably a big source of perf issues right now.

[Filip Pizlo]

Created attachment 305441 [details]
the patch

[Filip Pizlo]

Created attachment 305443 [details]
the patch

[Oliver Hunt]

Comment on attachment 305443 [details]
the patch

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

> Source/JavaScriptCore/b3/B3VariableLiveness.h:85
> +    template<typename Func>
> +    void forEachLateDef(BasicBlock* block, unsigned valueIndex, const Func& func)

Have you ever checked to make sure that the optimizer is inlining func? (when function is a constant i mean)

(this is also more out of curiosity that anything else)

> Source/WTF/wtf/Liveness.h:194
> +                IndexSparseSet<UnsafeVectorOverflow>::const_iterator m_sparceSetIterator;

Does this really need to be Unsafe.. ?

[Saam Barati]

Comment on attachment 305443 [details]
the patch

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

r=me. I mostly have some style comments/suggestions.

> Source/JavaScriptCore/ChangeLog:13
> +        This makes B3::fixSSA run twice as fast. This is a 13% progression on WasmBench compile
> +        times.

Awesome!

> Source/JavaScriptCore/b3/air/AirCFG.h:44
> +    typedef BasicBlock* Node;
> +    typedef IndexSet<BasicBlock> Set;
> +    template<typename T> using Map = IndexMap<BasicBlock, T>;
> +    typedef Vector<BasicBlock*, 4> List;

Style: The typedef's here can all be "using"s. I feel like I've been seeing this more in JSC/WebKit, and have been using it more myself.
(Same for typedefs elsewhere in this patch.)

> Source/JavaScriptCore/b3/air/AirCFG.h:61
> +    Node node(unsigned index) const { return m_code[index]; }
> +    unsigned numNodes() const { return m_code.size(); }

Style: Maybe call this block() and numBlocks()? (And make the interface changes in WTF).

> Source/WTF/wtf/Liveness.h:36
> +// HEADS UP: The algorithm here is duplicated in AirRegLiveness.h. That one uses sets rather
> +// than fancy vectors, because that's better for register liveness analysis.

Style: It feels weird to have a comment like this in WTF. Maybe we should have the "heads up" inside AirRegLiveness?

> Source/WTF/wtf/Liveness.h:54
> +            typename CFG::Node block = m_cfg.node(blockIndex);

Style: You use `typename CFG::Node` many times in this file, perhaps it's worth adding something like `using Node = typename CFG::Node` at the top of this class?

> Source/WTF/wtf/Liveness.h:246
> +                m_block, instIndex - 1,

Don't you need to make sure instIndex is > 0? (Perhaps the code gracefully handles the wrap around, but it feels more sane to make sure it's not zero.)

[Filip Pizlo]

(In reply to Saam Barati from comment #6)
> Comment on attachment 305443 [details]
> the patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=305443&action=review
> 
> r=me. I mostly have some style comments/suggestions.
> 
> > Source/JavaScriptCore/ChangeLog:13
> > +        This makes B3::fixSSA run twice as fast. This is a 13% progression on WasmBench compile
> > +        times.
> 
> Awesome!
> 
> > Source/JavaScriptCore/b3/air/AirCFG.h:44
> > +    typedef BasicBlock* Node;
> > +    typedef IndexSet<BasicBlock> Set;
> > +    template<typename T> using Map = IndexMap<BasicBlock, T>;
> > +    typedef Vector<BasicBlock*, 4> List;
> 
> Style: The typedef's here can all be "using"s. I feel like I've been seeing
> this more in JSC/WebKit, and have been using it more myself.
> (Same for typedefs elsewhere in this patch.)
> 
> > Source/JavaScriptCore/b3/air/AirCFG.h:61
> > +    Node node(unsigned index) const { return m_code[index]; }
> > +    unsigned numNodes() const { return m_code.size(); }
> 
> Style: Maybe call this block() and numBlocks()? (And make the interface
> changes in WTF).

This would be an enormous change since there's also a B3CFG, DFGCFG, BackwardsGraph, and lots of other things that define this same API so that they can all be used for Dominators and other graph utilities.

That's why it's "nodes" not "blocks". Dominators takes a Graph type argument. Graphs have nodes, not blocks. Air::CFG, B3::CFG, and DFG::CFG are just three kinds of graphs, whose nodes are blocks. Hence the method names are "node" and "numNodes" and they return information about blocks.

> 
> > Source/WTF/wtf/Liveness.h:36
> > +// HEADS UP: The algorithm here is duplicated in AirRegLiveness.h. That one uses sets rather
> > +// than fancy vectors, because that's better for register liveness analysis.
> 
> Style: It feels weird to have a comment like this in WTF. Maybe we should
> have the "heads up" inside AirRegLiveness?

I bet that most people changing the liveness analysis will find Liveness.h and hack that.

> 
> > Source/WTF/wtf/Liveness.h:54
> > +            typename CFG::Node block = m_cfg.node(blockIndex);
> 
> Style: You use `typename CFG::Node` many times in this file, perhaps it's
> worth adding something like `using Node = typename CFG::Node` at the top of
> this class?
> 
> > Source/WTF/wtf/Liveness.h:246
> > +                m_block, instIndex - 1,
> 
> Don't you need to make sure instIndex is > 0? (Perhaps the code gracefully
> handles the wrap around, but it feels more sane to make sure it's not zero.)

The implementation of this function uses BasicBlock::get() rather than BasicBlock::at().  get() does a bounds check and returns null if the check fails.  If instIndex is 0, this produces -1, which is unsigned-greater-than the BasicBlock vector bounds.

[Filip Pizlo]

Landed in r214410.