webkitgtk-2.4.11webkitgtk-2.4.11

1 files changed, 172 insertions, 47 deletions

diff --git a/Source/JavaScriptCore/dfg/DFGDCEPhase.cpp b/Source/JavaScriptCore/dfg/DFGDCEPhase.cpp
index 5290f2422..36f7683a8 100644
--- a/Source/JavaScriptCore/dfg/DFGDCEPhase.cpp
+++ b/Source/JavaScriptCore/dfg/DFGDCEPhase.cpp
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2013-2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2013 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -32,7 +32,7 @@
 #include "DFGGraph.h"
 #include "DFGInsertionSet.h"
 #include "DFGPhase.h"
-#include "JSCInlines.h"
+#include "Operations.h"
 
 namespace JSC { namespace DFG {
 
@@ -48,34 +48,77 @@ public:
     {
         ASSERT(m_graph.m_form == ThreadedCPS || m_graph.m_form == SSA);
         
-        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--;) {
+        // 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) {
             BasicBlock* block = m_graph.block(blockIndex);
             if (!block)
                 continue;
-            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())
+            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)
                         continue;
-                    break;
-                default:
-                    break;
+                    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);
+                    }
                 }
-                block->at(targetIndex++) = node;
             }
-            block->resize(targetIndex);
+        }
+        
+        if (m_graph.m_form == SSA) {
+            // Need to process the graph in reverse DFS order, so that we get to the uses
+            // of a node before we get to the node itself.
+            Vector<BasicBlock*> depthFirst;
+            m_graph.getBlocksInDepthFirstOrder(depthFirst);
+            for (unsigned 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);
         }
         
         m_graph.m_refCountState = ExactRefCount;
@@ -84,16 +127,51 @@ public:
     }
 
 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;
-
-        if (m_graph.m_form == ThreadedCPS) {
+        
+        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.
+            
             for (unsigned phiIndex = 0; phiIndex < block->phis.size(); ++phiIndex) {
-                Node* phi = block->phis[phiIndex];
-                if (!phi->shouldGenerate()) {
-                    m_graph.m_allocator.free(phi);
+                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
                     block->phis[phiIndex--] = block->phis.last();
                     block->phis.removeLast();
                 }
@@ -101,37 +179,75 @@ private:
             
             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.
-        for (unsigned indexInBlock = 0; indexInBlock < block->size(); ++indexInBlock) {
+        for (unsigned indexInBlock = block->size(); indexInBlock--;) {
             Node* node = block->at(indexInBlock);
             if (node->shouldGenerate())
                 continue;
                 
-            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);
+            switch (node->op()) {
+            case MovHint: {
+                ASSERT(node->child1().useKind() == UntypedUse);
+                if (!node->child1()->shouldGenerate()) {
+                    node->setOpAndDefaultFlags(ZombieHint);
+                    node->child1() = Edge();
+                    break;
                 }
+                node->setOpAndDefaultFlags(MovHint);
+                break;
+            }
                 
-                node->setOpAndDefaultFlags(Check);
-                node->children.reset();
-                node->setRefCount(1);
-                continue;
+            case ZombieHint: {
+                // Currently we assume that DCE runs only once.
+                RELEASE_ASSERT_NOT_REACHED();
+                break;
             }
             
-            node->remove();
-            node->setRefCount(1);
+            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->codeOrigin, edge);
+                    }
+
+                    node->convertToPhantomUnchecked();
+                    node->children.reset();
+                    node->setRefCount(1);
+                    break;
+                }
+
+                node->convertToPhantom();
+                eliminateIrrelevantPhantomChildren(node);
+                node->setRefCount(1);
+                break;
+            } }
         }
 
         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)
     {
@@ -139,12 +255,21 @@ private:
             Node* node = variables[i];
             if (!node)
                 continue;
-            if (node->op() != Check && node->shouldGenerate())
+            if (node->op() != Phantom && node->shouldGenerate())
                 continue;
-            variables[i] = nullptr;
+            if (node->op() == GetLocal) {
+                node = node->child1().node();
+                ASSERT(node->op() == Phi || node->op() == SetArgument);
+                if (node->shouldGenerate()) {
+                    variables[i] = node;
+                    continue;
+                }
+            }
+            variables[i] = 0;
         }
     }
     
+    Vector<Node*, 128> m_worklist;
     InsertionSet m_insertionSet;
 };