Changeset 184776 in webkit for trunk/Source/JavaScriptCore/dfg/DFGCSEPhase.cpp

Timestamp:

May 22, 2015, 10:24:05 AM (10 years ago)

Author:

[email protected]

Message:

Allow DFGClobberize to return non-node constants that must be later created
​https://bugs.webkit.org/show_bug.cgi?id=145272

Reviewed by Filip Pizlo.

Source/JavaScriptCore:

This adds a new LazyNode class in DFG that represents either a Node*,
or a FrozenValue* with a way to convert it to a Node* provided a block
to insert it into. DFGClobberize is converted to use LazyNode instead
of Node* when def()'ing values, which allows to now define the array's
length as well as the value of its various fields in NewArray and
NewArrayBuffer nodes.

We also introduce a Vector<uint32_t> in DFG::Graph to collect all the
values that can be used as index, in order to avoid def()'ing too many
values at once for big NewArrayBuffers.

HeapLocation had to be updated to use a LazyNode as its index to be
able to define array values.

• CMakeLists.txt:
• JavaScriptCore.vcxproj/JavaScriptCore.vcxproj:
• JavaScriptCore.vcxproj/JavaScriptCore.vcxproj.filters:
• JavaScriptCore.xcodeproj/project.pbxproj:
• dfg/DFGCSEPhase.cpp:
• dfg/DFGClobberize.h:

(JSC::DFG::clobberize):
(JSC::DFG::DefMethodClobberize::operator()):

• dfg/DFGGraph.cpp:

(JSC::DFG::Graph::freezeFragile):

• dfg/DFGGraph.h:
• dfg/DFGHeapLocation.h:

(JSC::DFG::HeapLocation::HeapLocation):
(JSC::DFG::HeapLocation::index):
(JSC::DFG::HeapLocation::hash):

• dfg/DFGLazyNode.cpp: Added.

(JSC::DFG::LazyNode::dump):

• dfg/DFGLazyNode.h: Added.

(JSC::DFG::LazyNode::LazyNode):
(JSC::DFG::LazyNode::setNode):
(JSC::DFG::LazyNode::isHashTableDeletedValue):
(JSC::DFG::LazyNode::isNode):
(JSC::DFG::LazyNode::op):
(JSC::DFG::LazyNode::asNode):
(JSC::DFG::LazyNode::asValue):
(JSC::DFG::LazyNode::hash):
(JSC::DFG::LazyNode::operator==):
(JSC::DFG::LazyNode::operator!=):
(JSC::DFG::LazyNode::ensureIsNode):
(JSC::DFG::LazyNode::operator->):
(JSC::DFG::LazyNode::operator*):
(JSC::DFG::LazyNode::operator!):
(JSC::DFG::LazyNode::operator UnspecifiedBoolType*):
(JSC::DFG::LazyNode::setFrozenValue):

• dfg/DFGPreciseLocalClobberize.h:

(JSC::DFG::PreciseLocalClobberizeAdaptor::def):

• dfg/DFGPutStackSinkingPhase.cpp:

LayoutTests:

• js/regress/script-tests/cse-new-array-buffer.js: Added.

(foo):

• js/regress/script-tests/cse-new-array.js: Added.

(foo):

File:

• trunk/Source/JavaScriptCore/dfg/DFGCSEPhase.cpp (modified) (19 diffs)

trunk/Source/JavaScriptCore/dfg/DFGCSEPhase.cpp

@@ -149 +149 @@
         }
         
-        Node* findReplacement(HeapLocation location)
+        LazyNode findReplacement(HeapLocation location)
         {
             for (unsigned i = m_impureLength; i--;) {
@@ -158 +158 @@
         }
     
-        Node* addImpure(HeapLocation location, Node* node)
-        {
-            if (Node* result = findReplacement(location))
+        LazyNode addImpure(HeapLocation location, LazyNode node)
+        {
+            // FIXME: If we are using small maps, we must not def() derived values.
+            // For now the only derived values we def() are constant-based.
+            if (location.index() && !location.index().isNode())
+                return nullptr;
+            if (LazyNode result = findReplacement(location))
                 return result;
             ASSERT(m_impureLength < capacity);
-            m_impureMap[m_impureLength++] = WTF::KeyValuePair<HeapLocation, Node*>(location, node);
+            m_impureMap[m_impureLength++] = WTF::KeyValuePair<HeapLocation, LazyNode>(location, node);
             return nullptr;
         }
@@ -169 +173 @@
     private:
         WTF::KeyValuePair<PureValue, Node*> m_pureMap[capacity];
-        WTF::KeyValuePair<HeapLocation, Node*> m_impureMap[capacity];
+        WTF::KeyValuePair<HeapLocation, LazyNode> m_impureMap[capacity];
         unsigned m_pureLength;
         unsigned m_impureLength;
@@ -199 +203 @@
         }
         
-        Node* findReplacement(HeapLocation location)
+        LazyNode findReplacement(HeapLocation location)
         {
             return m_impureMap.get(location);
         }
     
-        Node* addImpure(HeapLocation location, Node* node)
+        LazyNode addImpure(HeapLocation location, LazyNode node)
         {
             auto result = m_impureMap.add(location, node);
@@ -214 +218 @@
     private:
         HashMap<PureValue, Node*> m_pureMap;
-        HashMap<HeapLocation, Node*> m_impureMap;
+        HashMap<HeapLocation, LazyNode> m_impureMap;
     };
 
@@ -222 +226 @@
         BlockCSE(Graph& graph)
             : m_graph(graph)
+            , m_insertionSet(graph)
         {
         }
@@ -229 +234 @@
             m_maps.clear();
             m_changed = false;
+            m_block = block;
         
             for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
@@ -298 +304 @@
                 }
             }
+
+            m_insertionSet.execute(block);
         
             return m_changed;
@@ -319 +327 @@
         }
     
-        void def(HeapLocation location, Node* value)
-        {
-            Node* match = m_maps.addImpure(location, value);
+        void def(HeapLocation location, LazyNode value)
+        {
+            LazyNode match = m_maps.addImpure(location, value);
             if (!match)
                 return;
@@ -344 +352 @@
             }
         
-            m_node->replaceWith(match);
-            m_changed = true;
+            if (value.isNode() && value.asNode() == m_node) {
+                match.ensureIsNode(m_insertionSet, m_block, 0)->owner = m_block;
+                ASSERT(match.isNode());
+                m_node->replaceWith(match.asNode());
+                m_changed = true;
+            }
         }
     
@@ -353 +365 @@
         bool m_changed;
         Node* m_node;
+        BasicBlock* m_block;
     
         Maps m_maps;
+
+        InsertionSet m_insertionSet;
     };
 
@@ -366 +381 @@
         : Phase(graph, "global common subexpression elimination")
         , m_impureDataMap(graph)
+        , m_insertionSet(graph)
     {
     }
@@ -430 +446 @@
 
             for (unsigned nodeIndex = 0; nodeIndex < m_block->size(); ++nodeIndex) {
+                m_nodeIndex = nodeIndex;
                 m_node = m_block->at(nodeIndex);
                 if (verbose)
@@ -442 +459 @@
                     clobberize(m_graph, m_node, *this);
             }
+
+            m_insertionSet.execute(m_block);
             
             m_impureData->didVisit = true;
@@ -487 +506 @@
     }
     
-    Node* findReplacement(HeapLocation location)
+    LazyNode findReplacement(HeapLocation location)
     {
         // At this instant, our "availableAtTail" reflects the set of things that are available in
         // this block so far. We check this map to find block-local CSE opportunities before doing
         // a global search.
-        Node* match = m_impureData->availableAtTail.get(location);
-        if (match) {
+        LazyNode match = m_impureData->availableAtTail.get(location);
+        if (!!match) {
             if (verbose)
                 dataLog("      Found local match: ", match, "\n");
@@ -576 +595 @@
                 if (verbose)
                     dataLog("        Availability: ", match, "\n");
-                if (match) {
+                if (!!match) {
                     // Don't examine the predecessors of a match. At this point we just want to
                     // establish that other blocks on the path from here to there don't clobber
@@ -617 +636 @@
     }
     
-    void def(HeapLocation location, Node* value)
+    void def(HeapLocation location, LazyNode value)
     {
         if (verbose)
             dataLog("    Got heap location def: ", location, " -> ", value, "\n");
         
-        Node* match = findReplacement(location);
+        LazyNode match = findReplacement(location);
         
         if (verbose)
@@ -634 +653 @@
             return;
         }
-        
-        m_node->replaceWith(match);
-        m_changed = true;
+
+        if (value.isNode() && value.asNode() == m_node) {
+            if (!match.isNode()) {
+                // We need to properly record the constant in order to use an existing one if applicable.
+                // This ensures that re-running GCSE will not find new optimizations.
+                match.ensureIsNode(m_insertionSet, m_block, m_nodeIndex)->owner = m_block;
+                auto result = m_pureValues.add(PureValue(match.asNode(), match->constant()), Vector<Node*>());
+                bool replaced = false;
+                if (!result.isNewEntry) {
+                    for (unsigned i = result.iterator->value.size(); i--;) {
+                        Node* candidate = result.iterator->value[i];
+                        if (m_graph.m_dominators.dominates(candidate->owner, m_block)) {
+                            ASSERT(candidate);
+                            match->replaceWith(candidate);
+                            match.setNode(candidate);
+                            replaced = true;
+                            break;
+                        }
+                    }
+                }
+                if (!replaced)
+                    result.iterator->value.append(match.asNode());
+            }
+            ASSERT(match.asNode());
+            m_node->replaceWith(match.asNode());
+            m_changed = true;
+        }
     }
     
@@ -657 +700 @@
     BasicBlock* m_block;
     Node* m_node;
+    unsigned m_nodeIndex;
     ImpureBlockData* m_impureData;
     ClobberSet m_writesSoFar;
+    InsertionSet m_insertionSet;
     
     bool m_changed;