JavaScriptCore-7601.1.46.3.tar.gz

[apple/javascriptcore.git] / dfg / DFGDCEPhase.cpp

diff --git a/dfg/DFGDCEPhase.cpp b/dfg/DFGDCEPhase.cpp
index e8cf933cc0be413d6d35025287b8be0c59f388ac..5290f242278b0eeb79203f54a6bea9de62b71197 100644 (file)
--- a/dfg/DFGDCEPhase.cpp
+++ b/dfg/DFGDCEPhase.cpp
@@ -1,5 +1,5 @@
 /*
 /*

- * Copyright (C) 2013, 2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2013-2015 Apple Inc. All rights reserved.

  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions


@@ -48,75 +48,34 @@ public:
     {
         ASSERT(m_graph.m_form == ThreadedCPS || m_graph.m_form == SSA);
         
     {
         ASSERT(m_graph.m_form == ThreadedCPS || m_graph.m_form == SSA);
         

-        // First reset the counts to 0 for all nodes.
-        for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
-            BasicBlock* block = m_graph.block(blockIndex);
-            if (!block)
-                continue;
-            for (unsigned indexInBlock = block->size(); indexInBlock--;)
-                block->at(indexInBlock)->setRefCount(0);
-            for (unsigned phiIndex = block->phis.size(); phiIndex--;)
-                block->phis[phiIndex]->setRefCount(0);
-        }
-    
-        // Now find the roots:
-        // - Nodes that are must-generate.
-        // - Nodes that are reachable from type checks.
-        // Set their ref counts to 1 and put them on the worklist.
-        for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
+        m_graph.computeRefCounts();
+        
+        for (BasicBlock* block : m_graph.blocksInPreOrder())
+            fixupBlock(block);
+        
+        cleanVariables(m_graph.m_arguments);
+
+        // Just do a basic Phantom/Check clean-up.
+        for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {

             BasicBlock* block = m_graph.block(blockIndex);
             if (!block)
                 continue;
             BasicBlock* block = m_graph.block(blockIndex);
             if (!block)
                 continue;

-            for (unsigned indexInBlock = block->size(); indexInBlock--;) {
-                Node* node = block->at(indexInBlock);
-                DFG_NODE_DO_TO_CHILDREN(m_graph, node, findTypeCheckRoot);
-                if (!(node->flags() & NodeMustGenerate))
-                    continue;
-                if (!node->postfixRef())
-                    m_worklist.append(node);
-            }
-        }
-        
-        while (!m_worklist.isEmpty()) {
-            while (!m_worklist.isEmpty()) {
-                Node* node = m_worklist.last();
-                m_worklist.removeLast();
-                ASSERT(node->shouldGenerate()); // It should not be on the worklist unless it's ref'ed.
-                DFG_NODE_DO_TO_CHILDREN(m_graph, node, countEdge);
-            }
-            
-            if (m_graph.m_form == SSA) {
-                // Find Phi->Upsilon edges, which are represented as meta-data in the
-                // Upsilon.
-                for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
-                    BasicBlock* block = m_graph.block(blockIndex);
-                    if (!block)
+            unsigned sourceIndex = 0;
+            unsigned targetIndex = 0;
+            while (sourceIndex < block->size()) {
+                Node* node = block->at(sourceIndex++);
+                switch (node->op()) {
+                case Check:
+                case Phantom:
+                    if (node->children.isEmpty())

                         continue;
                         continue;

-                    for (unsigned nodeIndex = block->size(); nodeIndex--;) {
-                        Node* node = block->at(nodeIndex);
-                        if (node->op() != Upsilon)
-                            continue;
-                        if (node->shouldGenerate())
-                            continue;
-                        if (node->phi()->shouldGenerate())
-                            countNode(node);
-                    }
+                    break;
+                default:
+                    break;

                 }
                 }

+                block->at(targetIndex++) = node;

             }
             }

-        }
-        
-        if (m_graph.m_form == SSA) {
-            Vector<BasicBlock*> depthFirst;
-            m_graph.getBlocksInDepthFirstOrder(depthFirst);
-            for (unsigned i = 0; i < depthFirst.size(); ++i)
-                fixupBlock(depthFirst[i]);
-        } else {
-            RELEASE_ASSERT(m_graph.m_form == ThreadedCPS);
-            
-            for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex)
-                fixupBlock(m_graph.block(blockIndex));
-            
-            cleanVariables(m_graph.m_arguments);
+            block->resize(targetIndex);

         }
         
         m_graph.m_refCountState = ExactRefCount;
         }
         
         m_graph.m_refCountState = ExactRefCount;


@@ -125,51 +84,16 @@ public:
     }
 
 private:
     }
 
 private:

-    void findTypeCheckRoot(Node*, Edge edge)
-    {
-        // We may have an "unproved" untyped use for code that is unreachable. The CFA
-        // will just not have gotten around to it.
-        if (edge.willNotHaveCheck())
-            return;
-        if (!edge->postfixRef())
-            m_worklist.append(edge.node());
-    }
-    
-    void countNode(Node* node)
-    {
-        if (node->postfixRef())
-            return;
-        m_worklist.append(node);
-    }
-    
-    void countEdge(Node*, Edge edge)
-    {
-        // Don't count edges that are already counted for their type checks.
-        if (edge.willHaveCheck())
-            return;
-        countNode(edge.node());
-    }
-    

     void fixupBlock(BasicBlock* block)
     {
         if (!block)
             return;
     void fixupBlock(BasicBlock* block)
     {
         if (!block)
             return;

-        
-        switch (m_graph.m_form) {
-        case SSA:
-            break;
-            
-        case ThreadedCPS: {
-            // Clean up variable links for the block. We need to do this before the actual DCE
-            // because we need to see GetLocals, so we can bypass them in situations where the
-            // vars-at-tail point to a GetLocal, the GetLocal is dead, but the Phi it points
-            // to is alive.
-            
+
+        if (m_graph.m_form == ThreadedCPS) {

             for (unsigned phiIndex = 0; phiIndex < block->phis.size(); ++phiIndex) {
             for (unsigned phiIndex = 0; phiIndex < block->phis.size(); ++phiIndex) {

-                if (!block->phis[phiIndex]->shouldGenerate()) {
-                    // FIXME: We could actually free nodes here. Except that it probably
-                    // doesn't matter, since we don't add any nodes after this phase.
-                    // https://bugs.webkit.org/show_bug.cgi?id=126239
+                Node* phi = block->phis[phiIndex];
+                if (!phi->shouldGenerate()) {
+                    m_graph.m_allocator.free(phi);

                     block->phis[phiIndex--] = block->phis.last();
                     block->phis.removeLast();
                 }
                     block->phis[phiIndex--] = block->phis.last();
                     block->phis.removeLast();
                 }


@@ -177,12 +101,6 @@ private:
             
             cleanVariables(block->variablesAtHead);
             cleanVariables(block->variablesAtTail);
             
             cleanVariables(block->variablesAtHead);
             cleanVariables(block->variablesAtTail);

-            break;
-        }
-            
-        default:
-            RELEASE_ASSERT_NOT_REACHED();
-            return;

         }
 
         // This has to be a forward loop because we are using the insertion set.
         }
 
         // This has to be a forward loop because we are using the insertion set.


@@ -191,62 +109,29 @@ private:
             if (node->shouldGenerate())
                 continue;
                 
             if (node->shouldGenerate())
                 continue;
                 

-            switch (node->op()) {
-            case MovHint: {
-                // Check if the child is dead. MovHint's child would only be a Phantom
-                // if we had just killed it.
-                if (node->child1()->op() == Phantom) {
-                    node->setOpAndDefaultFlags(ZombieHint);
-                    node->child1() = Edge();
-                    break;
+            if (node->flags() & NodeHasVarArgs) {
+                for (unsigned childIdx = node->firstChild(); childIdx < node->firstChild() + node->numChildren(); childIdx++) {
+                    Edge edge = m_graph.m_varArgChildren[childIdx];
+                    
+                    if (!edge || edge.willNotHaveCheck())
+                        continue;
+                    
+                    m_insertionSet.insertNode(indexInBlock, SpecNone, Check, node->origin, edge);

                 }
                 }

-                break;
-            }

                 
                 

-            case ZombieHint: {
-                // Currently we assume that DCE runs only once.
-                RELEASE_ASSERT_NOT_REACHED();
-                break;
+                node->setOpAndDefaultFlags(Check);
+                node->children.reset();
+                node->setRefCount(1);
+                continue;

             }
             
             }
             

-            default: {
-                if (node->flags() & NodeHasVarArgs) {
-                    for (unsigned childIdx = node->firstChild(); childIdx < node->firstChild() + node->numChildren(); childIdx++) {
-                        Edge edge = m_graph.m_varArgChildren[childIdx];
-
-                        if (!edge || edge.willNotHaveCheck())
-                            continue;
-
-                        m_insertionSet.insertNode(indexInBlock, SpecNone, Phantom, node->origin, edge);
-                    }
-
-                    node->convertToPhantomUnchecked();
-                    node->children.reset();
-                    node->setRefCount(1);
-                    break;
-                }
-
-                node->convertToPhantom();
-                eliminateIrrelevantPhantomChildren(node);
-                node->setRefCount(1);
-                break;
-            } }
+            node->remove();
+            node->setRefCount(1);

         }
 
         m_insertionSet.execute(block);
     }
     
         }
 
         m_insertionSet.execute(block);
     }
     

-    void eliminateIrrelevantPhantomChildren(Node* node)
-    {
-        for (unsigned i = 0; i < AdjacencyList::Size; ++i) {
-            Edge edge = node->children.child(i);
-            if (!edge)
-                continue;
-            if (edge.willNotHaveCheck())
-                node->children.removeEdge(i--);
-        }
-    }
-    

     template<typename VariablesVectorType>
     void cleanVariables(VariablesVectorType& variables)
     {
     template<typename VariablesVectorType>
     void cleanVariables(VariablesVectorType& variables)
     {


@@ -254,53 +139,12 @@ private:
             Node* node = variables[i];
             if (!node)
                 continue;
             Node* node = variables[i];
             if (!node)
                 continue;

-            if (node->op() != Phantom && node->shouldGenerate())
+            if (node->op() != Check && node->shouldGenerate())

                 continue;
                 continue;

-            if (node->op() == GetLocal) {
-                node = node->child1().node();
-                
-                // FIXME: In the case that the variable is captured, we really want to be able
-                // to replace the variable-at-tail with the last use of the variable in the same
-                // way that CPS rethreading would do. The child of the GetLocal isn't necessarily
-                // the same as what CPS rethreading would do. For example, we may have:
-                //
-                // a: SetLocal(...) // live
-                // b: GetLocal(@a) // live
-                // c: GetLocal(@a) // dead
-                //
-                // When killing @c, the code below will set the variable-at-tail to @a, while CPS
-                // rethreading would have set @b. This is a benign bug, since all clients of CPS
-                // only use the variable-at-tail of captured variables to get the
-                // VariableAccessData and observe that it is in fact captured. But, this feels
-                // like it could cause bugs in the future.
-                //
-                // It's tempting to just dethread and then invoke CPS rethreading, but CPS
-                // rethreading fails to preserve exact ref-counts. So we would need a fixpoint.
-                // It's probably the case that this fixpoint will be guaranteed to converge after
-                // the second iteration (i.e. the second run of DCE will not kill anything and so
-                // will not need to dethread), but for now the safest approach is probably just to
-                // allow for this tiny bit of sloppiness.
-                //
-                // Another possible solution would be to simply say that DCE dethreads but then
-                // we never rethread before going to the backend. That feels intuitively right
-                // because it's unlikely that any of the phases after DCE in the backend rely on
-                // ThreadedCPS.
-                //
-                // https://bugs.webkit.org/show_bug.cgi?id=130115
-                ASSERT(
-                    node->op() == Phi || node->op() == SetArgument
-                    || node->variableAccessData()->isCaptured());
-                
-                if (node->shouldGenerate()) {
-                    variables[i] = node;
-                    continue;
-                }
-            }
-            variables[i] = 0;
+            variables[i] = nullptr;

         }
     }
     
         }
     }
     

-    Vector<Node*, 128> m_worklist;

     InsertionSet m_insertionSet;
 };
 
     InsertionSet m_insertionSet;
 };