[Webkit-unassigned] [Bug 80415] Eliminate redundant Phis in DFG

[bugzilla-daemon at webkit.org]

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





--- Comment #4 from Filip Pizlo <fpizlo at apple.com>  2012-03-06 13:55:51 PST ---
(From update of attachment 130384)
View in context: https://bugs.webkit.org/attachment.cgi?id=130384&action=review

I think this is great.  My intuition is that we could simplify this further by doing away with the phi use map.  But maybe I'm wrong?  Have you tried it without the use map?

> Source/JavaScriptCore/dfg/DFGAbstractState.cpp:1006
> -    if (!node.refCount())
> +    // We don't want to ignore the skipped Phi nodes, otherwise we may fail to
> +    // propagate the type predictions to other blocks.
> +    if (!node.refCount() && node.op != Phi)

Why?  The idea here is that if we have a node that claims that it is using a variable from another block, and its uses of that variable are dead, then we have no work to do.

> Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp:594
> +    void addPhiUse(NodeIndex phi, NodeIndex node, unsigned childIndex, NodeIndex replace = NoNode)
> +    {
> +        ASSERT(phi != NoNode && m_graph[phi].op == Phi);
> +
> +        Vector<PhiUse>* phiUse;
> +        PhiUseMap::iterator iter = m_graph.m_phiUses.find(phi);
> +        if (iter != m_graph.m_phiUses.end())
> +            phiUse = &iter->second;
> +        else {
> +            Vector<PhiUse> emptyUse;
> +            pair<PhiUseMap::iterator, bool> result = m_graph.m_phiUses.add(phi, emptyUse);
> +            phiUse = &result.first->second;
> +        }
> +
> +        // If a replacement is needed, we want to remove the old use entry.
> +        // This would find and delete an entry in the middle of a vector,
> +        // but we expect this would be rarely happened in practice - only when
> +        // a Phi node in a joint block needs to handle more than 3 incoming edges.
> +        if (replace != NoNode) {
> +            size_t i = phiUse->find(PhiUse(replace, childIndex));
> +            ASSERT(i != notFound);
> +            phiUse->remove(i);
> +        }
> +
> +        phiUse->append(PhiUse(node, childIndex));
> +    }

Not sure I buy that the phi use map is necessary.  I kind of don't like it because it means we cannot rerun the redundant phi replacement algorithm a second time unless we also maintain the consistency of this map.  In general, in the future I want to be able to have a phase that introduces new nodes or switches the children of nodes, and then rerun the phi simplification if I had also done some control flow simplification.  But playing with the children of nodes seems hard if I have to maintain the phi use map as I do it.

> Source/JavaScriptCore/dfg/DFGRedundantPhiEliminationPhase.cpp:87
> +                    switch (use.childIndex()) {
> +                    case 1:
> +                        ASSERT(useNode.child1().indexUnchecked() == phi);
> +                        useNode.children.child1().setIndex(replacement);
> +                        m_graph[replacement].ref();
> +                        break;
> +                    case 2:
> +                        ASSERT(useNode.child2().indexUnchecked() == phi);
> +                        useNode.children.child2().setIndex(replacement);
> +                        m_graph[replacement].ref();
> +                        break;
> +                    case 3:
> +                        ASSERT(useNode.child3().indexUnchecked() == phi);
> +                        useNode.children.child3().setIndex(replacement);
> +                        m_graph[replacement].ref();
> +                        break;
> +                    default:
> +                        break;
> +                    }

Why not kill the switch statement and say useNode.children.child(use.childIndex() - 1)?

> Source/JavaScriptCore/dfg/DFGRedundantPhiEliminationPhase.cpp:126
> +    NodeIndex getRedundantReplacement(NodeIndex phi)
> +    {
> +        NodeIndex child1 = m_graph[phi].child1().indexUnchecked();
> +        NodeIndex candidate = child1 == phi ? NoNode : child1;
> +
> +        NodeIndex child2 = m_graph[phi].child2().indexUnchecked();
> +        if (candidate != NoNode) {
> +            if (child2 != NoNode && child2 != candidate && child2 != phi)
> +                return NoNode;
> +        } else if (child2 != phi)
> +            candidate = child2;
> +
> +        NodeIndex child3 = m_graph[phi].child3().indexUnchecked();
> +        if (candidate != NoNode) {
> +            if (child3 != NoNode && child3 != candidate && child3 != phi)
> +                return NoNode;
> +        } else if (child3 != phi)
> +            candidate = child3;
> +        
> +        return candidate;
> +    }

Can't we run this algorithm without having a phi use map?  Seems to me that we could:

1) Wrap the algorithm in a fixpoint.  You're using a worklist; maybe we could do that too.

2) Walk over the graph inside the fixpoint.

3) For every child that is a phi and fits the simplification criteria, attempt to simplify.

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