[Webkit-unassigned] [Bug 93361] Immediate dominators in DFG.

[bugzilla-daemon at webkit.org]

https://bugs.webkit.org/show_bug.cgi?id=93361


Filip Pizlo <fpizlo at apple.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
 Attachment #157712|                            |review-
               Flag|                            |




--- Comment #3 from Filip Pizlo <fpizlo at apple.com>  2012-08-13 15:37:07 PST ---
(From update of attachment 157712)
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.

-- 
Configure bugmail: https://bugs.webkit.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the assignee for the bug.