Changeset 204130 in webkit for trunk/Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.cpp

Timestamp:

Aug 4, 2016, 12:33:21 PM (9 years ago)

Author:

[email protected]

Message:

[JSC] Speed up InPlaceAbstractState::endBasicBlock()
​https://bugs.webkit.org/show_bug.cgi?id=160539

Patch by Benjamin Poulain <​[email protected]> on 2016-08-04
Reviewed by Mark Lam.

This patch does small improvements to our handling
of value propagation to the successors.

One key insight is that using HashMap to map Nodes
to Value in valuesAtTail is too inefficient at the scale
we use it. Instead, I reuse our existing mapping
from every Node to its value, abstracted by forNode().

Since we are not going to use the mapping after endBasicBlock()
I can replace whatever we had there. The next beginBasicBlock()
will setup the new value as needed.

In endBasicBlock(), valuesAtTail is now a vector of all values live
at tail. For each node, I merge the previous live at tail with
the new value, then replace the value in the mapping.
Liveness Analysis guarantees we won't have duplicates there which
make the replacement sound.

Next, when propagating, I take the vector of values lives at head
and use the global node->value mapping to find its new abstract value.
Again, Liveness Analysis guarantees I won't find a value live at head
that was not replaced by the merging at tail of the predecessor.

All our live lists have become vectors instead of HashTable.
The mapping from Node to Value is always done by array indexing.
Same big-O, much smaller constant.

• dfg/DFGAtTailAbstractState.cpp:

(JSC::DFG::AtTailAbstractState::AtTailAbstractState):
(JSC::DFG::AtTailAbstractState::createValueForNode):
(JSC::DFG::AtTailAbstractState::forNode):

• dfg/DFGAtTailAbstractState.h:

I did not look much into this state, I just made it equivalent
to the previous mapping.

• dfg/DFGBasicBlock.h:
• dfg/DFGCFAPhase.cpp:

(JSC::DFG::CFAPhase::performBlockCFA):

• dfg/DFGGraph.cpp:

(JSC::DFG::Graph::dump):

• dfg/DFGInPlaceAbstractState.cpp:

(JSC::DFG::InPlaceAbstractState::endBasicBlock):

(JSC::DFG::InPlaceAbstractState::mergeStateAtTail):
AbstractValue is big enough that we really don't want to copy it twice.

(JSC::DFG::InPlaceAbstractState::merge):
(JSC::DFG::setLiveValues): Deleted.

• dfg/DFGInPlaceAbstractState.h:

• dfg/DFGPhiChildren.h:

This is heap allocated by AbstractInterpreter. It should use fastMalloc().

File:

• trunk/Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.cpp (modified) (9 diffs)

trunk/Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.cpp

@@ -1 +1 @@
 /*
- * Copyright (C) 2013-2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2013-2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -81 +81 @@
 }
 
-static void setLiveValues(HashMap<Node*, AbstractValue>& values, const Vector<Node*>& liveNodes)
-{
-    values.clear();
-    for (Node* node : liveNodes)
-        values.add(node, AbstractValue());
-}
-
 static void setLiveValues(Vector<BasicBlock::SSAData::NodeAbstractValuePair>& values, const Vector<Node*>& live)
 {
@@ -186 +179 @@
         return false;
     }
-    
-    bool changed = checkAndSet(block->cfaStructureClobberStateAtTail, m_structureClobberState);
-    
+
+    block->cfaStructureClobberStateAtTail = m_structureClobberState;
+
     switch (m_graph.m_form) {
     case ThreadedCPS: {
         for (size_t argument = 0; argument < block->variablesAtTail.numberOfArguments(); ++argument) {
             AbstractValue& destination = block->valuesAtTail.argument(argument);
-            changed |= mergeStateAtTail(destination, m_variables.argument(argument), block->variablesAtTail.argument(argument));
+            mergeStateAtTail(destination, m_variables.argument(argument), block->variablesAtTail.argument(argument));
         }
 
         for (size_t local = 0; local < block->variablesAtTail.numberOfLocals(); ++local) {
             AbstractValue& destination = block->valuesAtTail.local(local);
-            changed |= mergeStateAtTail(destination, m_variables.local(local), block->variablesAtTail.local(local));
+            mergeStateAtTail(destination, m_variables.local(local), block->variablesAtTail.local(local));
         }
         break;
@@ -205 +198 @@
     case SSA: {
         for (size_t i = 0; i < block->valuesAtTail.size(); ++i)
-            changed |= block->valuesAtTail[i].merge(m_variables[i]);
-
-        for (Node* node : block->ssa->liveAtTail) {
-            changed |= block->ssa->valuesAtTail.find(node)->value.merge(forNode(node));
+            block->valuesAtTail[i].merge(m_variables[i]);
+
+        for (auto& valueAtTail : block->ssa->valuesAtTail) {
+            AbstractValue& valueAtNode = forNode(valueAtTail.node);
+            valueAtTail.value.merge(valueAtNode);
+            valueAtNode = valueAtTail.value;
         }
         break;
@@ -230 +225 @@
 }
 
-bool InPlaceAbstractState::mergeStateAtTail(AbstractValue& destination, AbstractValue& inVariable, Node* node)
+void InPlaceAbstractState::mergeStateAtTail(AbstractValue& destination, AbstractValue& inVariable, Node* node)
 {
     if (!node)
-        return false;
-        
-    AbstractValue source;
+        return;
+
+    const AbstractValue* source = nullptr;
     
     switch (node->op()) {
@@ -243 +238 @@
     case Flush:
         // The block transfers the value from head to tail.
-        source = inVariable;
+        source = &inVariable;
         break;
             
     case GetLocal:
         // The block refines the value with additional speculations.
-        source = forNode(node);
+        source = &forNode(node);
         break;
             
@@ -254 +249 @@
         // The block sets the variable, and potentially refines it, both
         // before and after setting it.
-        source = forNode(node->child1());
+        source = &forNode(node->child1());
         if (node->variableAccessData()->flushFormat() == FlushedDouble)
-            RELEASE_ASSERT(!(source.m_type & ~SpecFullDouble));
+            RELEASE_ASSERT(!(source->m_type & ~SpecFullDouble));
         break;
         
@@ -263 +258 @@
         break;
     }
-    
-    if (destination == source) {
-        // Abstract execution did not change the output value of the variable, for this
-        // basic block, on this iteration.
-        return false;
-    }
-    
-    // Abstract execution reached a new conclusion about the speculations reached about
-    // this variable after execution of this basic block. Update the state, and return
-    // true to indicate that the fixpoint must go on!
-    destination = source;
-    return true;
+    destination = *source;
 }
 
@@ -311 +295 @@
             Node* node = entry.node;
             if (verbose)
-                dataLog("      Merging for ", node, ": from ", from->ssa->valuesAtTail.find(node)->value, " to ", entry.value, "\n");
-            changed |= entry.value.merge(
-                from->ssa->valuesAtTail.find(node)->value);
+                dataLog("      Merging for ", node, ": from ", forNode(node), " to ", entry.value, "\n");
+#ifndef NDEBUG
+            unsigned valueCountInFromBlock = 0;
+            for (auto& fromBlockValueAtTail : from->ssa->valuesAtTail) {
+                if (fromBlockValueAtTail.node == node) {
+                    ASSERT(fromBlockValueAtTail.value == forNode(node));
+                    ++valueCountInFromBlock;
+                }
+            }
+            ASSERT(valueCountInFromBlock == 1);
+#endif
+
+            changed |= entry.value.merge(forNode(node));
 
             if (verbose)