Bug 93361 – DFG should compute immediate dominators using the O(n log n) form of Lengauer and Tarjan's "A Fast Algorithm for Finding Dominators in a Flowgraph"

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[nare]

Created attachment 156927 [details]
Add in DFGDominators immediate dominators computing function.

Add immediate dominators information in Dominators class.

[WebKit Review Bot]

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

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/JavaScriptCore/dfg/DFGDominators.cp..." exit_code: 1
Source/JavaScriptCore/dfg/DFGDominators.cpp:55:  Missing space before {  [whitespace/braces] [5]
Source/JavaScriptCore/dfg/DFGDominators.cpp:122:  Missing space before ( in for(  [whitespace/parens] [5]
Source/JavaScriptCore/dfg/DFGDominators.cpp:122:  Missing space before {  [whitespace/braces] [5]
Source/JavaScriptCore/dfg/DFGDominators.cpp:123:  Missing space before ( in if(  [whitespace/parens] [5]
Source/JavaScriptCore/dfg/DFGDominators.cpp:125:  Missing spaces around =  [whitespace/operators] [4]
Source/JavaScriptCore/dfg/DFGDominators.cpp:125:  Missing space before ( in for(  [whitespace/parens] [5]
Source/JavaScriptCore/dfg/DFGDominators.cpp:125:  Missing space before {  [whitespace/braces] [5]
Source/JavaScriptCore/dfg/DFGDominators.cpp:126:  Missing space before ( in if(  [whitespace/parens] [5]
Source/JavaScriptCore/dfg/DFGDominators.cpp:128:  Missing space before ( in if(  [whitespace/parens] [5]
Source/JavaScriptCore/dfg/DFGDominators.h:46:  The parameter name "graph" adds no information, so it should be removed.  [readability/parameter_name] [5]
Source/JavaScriptCore/dfg/DFGGraph.cpp:325:  Missing space after ,  [whitespace/comma] [3]
Total errors found: 11 in 3 files


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

[nare]

Created attachment 157712 [details]
Add in DFGDominators immediate dominators computing function.

with correct style

[Filip Pizlo]

Comment on attachment 157712 [details]
Add in DFGDominators immediate dominators computing function.

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

> Source/JavaScriptCore/dfg/DFGDominators.h:59
> +    bool isIDomChilds(BlockIndex from, BlockIndex to) const    

I would change this to immediatelyDominates(from, to).

> Source/JavaScriptCore/dfg/DFGDominators.cpp:133
> +void Dominators::buildIDomRelation(Graph& graph)
> +{
> +    ASSERT(isValid());
> +    unsigned numBlocks = graph.m_blocks.size();
> +
> +    for (unsigned j = 0; j < numBlocks; ++j)
> +    for (size_t i = 0; i < numBlocks; ++i) {
> +        if (!m_results[i].get(j)) // i(to), j(from) I need finde j->dominates set
> +            continue;
> +        m_resultsIDom[i].set(j);
> +        m_resultsIDom[j].clear(j);
> +    }
> +
> +    for (unsigned i = 0; i < numBlocks; ++i) {
> +        if (!graph.m_blocks[i])
> +            continue;
> +        for (unsigned j = 0; j < numBlocks; ++j) {
> +            if (!graph.m_blocks[j])
> +                continue;
> +            if (!m_resultsIDom[i].get(j))
> +                continue;
> +            m_resultsIDom[i].exclude(m_resultsIDom[j]);
> +        }
> +    }
> +}

This appears to implement the super-slow version of the algorithm.  I would much prefer the Lengauer and Tarjan algorithm.  Having an O(n^3) algorithm is probably not a good thing.

> Source/JavaScriptCore/dfg/DFGGraph.cpp:325
> -        dataLog("%s  Dominates:", prefix);
> +        dataLog("%s  Immediately Dominates:", prefix);
>          for (size_t i = 0; i < m_blocks.size(); ++i) {
> -            if (!m_dominators.dominates(blockIndex, i))
> +            if (!m_dominators.isIDomChilds(blockIndex, i))

I would prefer if we printed both dominators and immediate dominators. Known all of the dominators (not just the immediate ones) is useful when looking at IR.

[Filip Pizlo]

Created attachment 237133 [details]
it begins

[Filip Pizlo]

Created attachment 237181 [details]
getting close

[Filip Pizlo]

Created attachment 237192 [details]
it's getting interesting

[Filip Pizlo]

Created attachment 237203 [details]
it is written

[Filip Pizlo]

Created attachment 237240 [details]
debugging

It still has bugs.

[Filip Pizlo]

Created attachment 237254 [details]
still debugging

[Filip Pizlo]

Created attachment 237268 [details]
more progress

[Filip Pizlo]

Created attachment 237283 [details]
it works?

Seems right.

[Filip Pizlo]

Created attachment 237285 [details]
the patch

[WebKit Commit Bot]

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


ERROR: Source/JavaScriptCore/dfg/DFGDominators.cpp:225:  Multi line control clauses should use braces.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGGraph.cpp:35:  Alphabetical sorting problem.  [build/include_order] [4]
Total errors found: 2 in 21 files


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

[Mark Hahnenberg]

Comment on attachment 237285 [details]
the patch

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

> Source/JavaScriptCore/dfg/DFGBlockWorklist.h:152
> +struct BlockWithOrder {
> +    BlockWithOrder()
> +        : block(nullptr)
> +        , order(PreOrder)
> +    {
> +    }
> +    
> +    BlockWithOrder(BasicBlock* block, VisitOrder order)
> +        : block(block)
> +        , order(order)
> +    {
> +    }
> +    
> +    typedef void* (BlockWithOrder::*UnspecifiedBoolType);
> +    operator UnspecifiedBoolType*() const
> +    {
> +        return block ? reinterpret_cast<UnspecifiedBoolType*>(1) : nullptr;
> +    }
> +
> +    BasicBlock* block;
> +    VisitOrder order;
> +};

Why not just specialize the BlockWith<> template with VisitOrder? You could even typedef it if you liked how BlockWithOrder reads better than BlockWith<VisitOrder>.

[Mark Hahnenberg]

Comment on attachment 237285 [details]
the patch

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

r=me with comments.

> Source/JavaScriptCore/dfg/DFGDominators.cpp:114
> +            // We're initially push with successorIndex = 0 regardless of whether or not we have

s/We're initially/We initially/

[Filip Pizlo]

(In reply to comment #14)
> (From update of attachment 237285 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=237285&action=review
> 
> > Source/JavaScriptCore/dfg/DFGBlockWorklist.h:152
> > +struct BlockWithOrder {
> > +    BlockWithOrder()
> > +        : block(nullptr)
> > +        , order(PreOrder)
> > +    {
> > +    }
> > +    
> > +    BlockWithOrder(BasicBlock* block, VisitOrder order)
> > +        : block(block)
> > +        , order(order)
> > +    {
> > +    }
> > +    
> > +    typedef void* (BlockWithOrder::*UnspecifiedBoolType);
> > +    operator UnspecifiedBoolType*() const
> > +    {
> > +        return block ? reinterpret_cast<UnspecifiedBoolType*>(1) : nullptr;
> > +    }
> > +
> > +    BasicBlock* block;
> > +    VisitOrder order;
> > +};
> 
> Why not just specialize the BlockWith<> template with VisitOrder? You could even typedef it if you liked how BlockWithOrder reads better than BlockWith<VisitOrder>.

I almost did that.  I spent a lot of time optimizing for maximum clarity in loops like:

    while (BlockWithOrder item = worklist.pop()) {
        switch (item.order) {
        case PreOrder:
            worklist.pushPost(item.block);
            for (unsigned i = item.block->numSuccessors(); i--;)
                worklist.push(item.block->successor(i));
            break;
        case PostOrder:
            result.append(item.block);
            break;
        }

If I had done what you say then I'd be switching on item.data, which I felt was less clear.

Note that we already have two loops that use BlockWithOrder.  I suspect there will be more of them because postorder traversals are important in compilers.

[Filip Pizlo]

Landed in http://trac.webkit.org/changeset/173072