Object allocation sinking should have a sound story for picking materialization points
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 2 Oct 2014 19:38:08 +0000 (19:38 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 2 Oct 2014 19:38:08 +0000 (19:38 +0000)
https://bugs.webkit.org/show_bug.cgi?id=137315

Reviewed by Oliver Hunt.

The only missing piece was having the object allocation sinking phase locate materialization
points that were at CFG edges.

The logic for how and why this "just works" relies on some properties of critical edge
breaking, so I was fairly careful in how I did this. Also, this requires inserting things at
the "first origin node" of a block - that is the first node in a block that has a NodeOrigin
and therefore is allowed to exit. We basically had support for such a notion before, but
didn't close the loop on it; this patch does that.

Also I added the ability to provide a BasicBlock* as context for a DFG_ASSERT().

* dfg/DFGBasicBlock.cpp:
(JSC::DFG::BasicBlock::firstOriginNode):
(JSC::DFG::BasicBlock::firstOrigin):
* dfg/DFGBasicBlock.h:
* dfg/DFGCriticalEdgeBreakingPhase.cpp:
(JSC::DFG::CriticalEdgeBreakingPhase::breakCriticalEdge):
* dfg/DFGGraph.cpp:
(JSC::DFG::crash):
(JSC::DFG::Graph::handleAssertionFailure):
* dfg/DFGGraph.h:
* dfg/DFGLoopPreHeaderCreationPhase.cpp:
(JSC::DFG::createPreHeader):
* dfg/DFGNodeOrigin.h:
(JSC::DFG::NodeOrigin::isSet):
* dfg/DFGObjectAllocationSinkingPhase.cpp:
(JSC::DFG::ObjectAllocationSinkingPhase::determineMaterializationPoints):
(JSC::DFG::ObjectAllocationSinkingPhase::placeMaterializationPoints):
(JSC::DFG::ObjectAllocationSinkingPhase::promoteSunkenFields):
(JSC::DFG::ObjectAllocationSinkingPhase::createMaterialize):
* dfg/DFGValidate.cpp:
(JSC::DFG::Validate::validate):
* runtime/Options.h:

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@174224 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/dfg/DFGBasicBlock.cpp
Source/JavaScriptCore/dfg/DFGBasicBlock.h
Source/JavaScriptCore/dfg/DFGCriticalEdgeBreakingPhase.cpp
Source/JavaScriptCore/dfg/DFGGraph.cpp
Source/JavaScriptCore/dfg/DFGGraph.h
Source/JavaScriptCore/dfg/DFGLoopPreHeaderCreationPhase.cpp
Source/JavaScriptCore/dfg/DFGNodeOrigin.h
Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp
Source/JavaScriptCore/dfg/DFGValidate.cpp
Source/JavaScriptCore/runtime/Options.h

index 2f821d4..8940871 100644 (file)
@@ -1,3 +1,44 @@
+2014-10-02  Filip Pizlo  <fpizlo@apple.com>
+
+        Object allocation sinking should have a sound story for picking materialization points
+        https://bugs.webkit.org/show_bug.cgi?id=137315
+
+        Reviewed by Oliver Hunt.
+        
+        The only missing piece was having the object allocation sinking phase locate materialization
+        points that were at CFG edges.
+        
+        The logic for how and why this "just works" relies on some properties of critical edge
+        breaking, so I was fairly careful in how I did this. Also, this requires inserting things at
+        the "first origin node" of a block - that is the first node in a block that has a NodeOrigin
+        and therefore is allowed to exit. We basically had support for such a notion before, but
+        didn't close the loop on it; this patch does that.
+        
+        Also I added the ability to provide a BasicBlock* as context for a DFG_ASSERT().
+
+        * dfg/DFGBasicBlock.cpp:
+        (JSC::DFG::BasicBlock::firstOriginNode):
+        (JSC::DFG::BasicBlock::firstOrigin):
+        * dfg/DFGBasicBlock.h:
+        * dfg/DFGCriticalEdgeBreakingPhase.cpp:
+        (JSC::DFG::CriticalEdgeBreakingPhase::breakCriticalEdge):
+        * dfg/DFGGraph.cpp:
+        (JSC::DFG::crash):
+        (JSC::DFG::Graph::handleAssertionFailure):
+        * dfg/DFGGraph.h:
+        * dfg/DFGLoopPreHeaderCreationPhase.cpp:
+        (JSC::DFG::createPreHeader):
+        * dfg/DFGNodeOrigin.h:
+        (JSC::DFG::NodeOrigin::isSet):
+        * dfg/DFGObjectAllocationSinkingPhase.cpp:
+        (JSC::DFG::ObjectAllocationSinkingPhase::determineMaterializationPoints):
+        (JSC::DFG::ObjectAllocationSinkingPhase::placeMaterializationPoints):
+        (JSC::DFG::ObjectAllocationSinkingPhase::promoteSunkenFields):
+        (JSC::DFG::ObjectAllocationSinkingPhase::createMaterialize):
+        * dfg/DFGValidate.cpp:
+        (JSC::DFG::Validate::validate):
+        * runtime/Options.h:
+
 2014-10-02  Daniel Bates  <dabates@apple.com>
 
         Clean up: Move XPC forward declarations in JavaScriptCore to WTF SPI wrapper header
index 31fbef7..eb1f6a2 100644 (file)
@@ -89,6 +89,21 @@ bool BasicBlock::isInBlock(Node* myNode) const
     return false;
 }
 
+Node* BasicBlock::firstOriginNode()
+{
+    for (Node* node : *this) {
+        if (node->origin.isSet())
+            return node;
+    }
+    RELEASE_ASSERT_NOT_REACHED();
+    return nullptr;
+}
+
+NodeOrigin BasicBlock::firstOrigin()
+{
+    return firstOriginNode()->origin;
+}
+
 void BasicBlock::removePredecessor(BasicBlock* block)
 {
     for (unsigned i = 0; i < predecessors.size(); ++i) {
index 1ba2fd8..e39cac4 100644 (file)
@@ -34,6 +34,7 @@
 #include "DFGBranchDirection.h"
 #include "DFGFlushedAt.h"
 #include "DFGNode.h"
+#include "DFGNodeOrigin.h"
 #include "DFGStructureClobberState.h"
 #include "Operands.h"
 #include <wtf/HashMap.h>
@@ -90,6 +91,9 @@ struct BasicBlock : RefCounted<BasicBlock> {
     BlockNodeList::iterator begin() { return m_nodes.begin(); }
     BlockNodeList::iterator end() { return m_nodes.end(); }
     
+    Node* firstOriginNode();
+    NodeOrigin firstOrigin();
+    
     unsigned numSuccessors() { return last()->numSuccessors(); }
     
     BasicBlock*& successor(unsigned index)
index 1656774..18f6f5e 100644 (file)
@@ -77,7 +77,7 @@ private:
         // don't know its execution frequency.
         BasicBlock* pad = m_insertionSet.insertBefore(*successor, PNaN);
         pad->appendNode(
-            m_graph, SpecNone, Jump, (*successor)->at(0)->origin, OpInfo(*successor));
+            m_graph, SpecNone, Jump, (*successor)->firstOrigin(), OpInfo(*successor));
         pad->predecessors.append(predecessor);
         (*successor)->replacePredecessor(predecessor, pad);
         
index 1cfff8d..e5b5718 100644 (file)
@@ -1212,25 +1212,41 @@ void Graph::assertIsRegistered(Structure* structure)
     DFG_CRASH(*this, nullptr, toCString("Structure ", pointerDump(structure), " is watchable but isn't being watched.").data());
 }
 
-void Graph::handleAssertionFailure(
-    Node* node, const char* file, int line, const char* function, const char* assertion)
+NO_RETURN_DUE_TO_CRASH static void crash(
+    Graph& graph, const CString& whileText, const char* file, int line, const char* function,
+    const char* assertion)
 {
     startCrashing();
     dataLog("DFG ASSERTION FAILED: ", assertion, "\n");
     dataLog(file, "(", line, ") : ", function, "\n");
     dataLog("\n");
-    if (node) {
-        dataLog("While handling node ", node, "\n");
-        dataLog("\n");
-    }
+    dataLog(whileText);
     dataLog("Graph at time of failure:\n");
-    dump();
+    graph.dump();
     dataLog("\n");
     dataLog("DFG ASSERTION FAILED: ", assertion, "\n");
     dataLog(file, "(", line, ") : ", function, "\n");
     CRASH_WITH_SECURITY_IMPLICATION();
 }
 
+void Graph::handleAssertionFailure(
+    std::nullptr_t, const char* file, int line, const char* function, const char* assertion)
+{
+    crash(*this, "", file, line, function, assertion);
+}
+
+void Graph::handleAssertionFailure(
+    Node* node, const char* file, int line, const char* function, const char* assertion)
+{
+    crash(*this, toCString("While handling node ", node, "\n\n"), file, line, function, assertion);
+}
+
+void Graph::handleAssertionFailure(
+    BasicBlock* block, const char* file, int line, const char* function, const char* assertion)
+{
+    crash(*this, toCString("While handling block ", pointerDump(block), "\n\n"), file, line, function, assertion);
+}
+
 } } // namespace JSC::DFG
 
 #endif // ENABLE(DFG_JIT)
index 00abaec..0cd15de 100644 (file)
@@ -845,7 +845,13 @@ public:
     virtual void visitChildren(SlotVisitor&) override;
     
     NO_RETURN_DUE_TO_CRASH void handleAssertionFailure(
-        Node* node, const char* file, int line, const char* function,
+        std::nullptr_t, const char* file, int line, const char* function,
+        const char* assertion);
+    NO_RETURN_DUE_TO_CRASH void handleAssertionFailure(
+        Node*, const char* file, int line, const char* function,
+        const char* assertion);
+    NO_RETURN_DUE_TO_CRASH void handleAssertionFailure(
+        BasicBlock*, const char* file, int line, const char* function,
         const char* assertion);
     
     VM& m_vm;
index b11b2db..762562d 100644 (file)
@@ -42,7 +42,7 @@ BasicBlock* createPreHeader(Graph& graph, BlockInsertionSet& insertionSet, Basic
     // Don't bother to preserve execution frequencies for now.
     BasicBlock* preHeader = insertionSet.insertBefore(block, PNaN);
     preHeader->appendNode(
-        graph, SpecNone, Jump, block->at(0)->origin, OpInfo(block));
+        graph, SpecNone, Jump, block->firstOrigin(), OpInfo(block));
     
     for (unsigned predecessorIndex = 0; predecessorIndex < block->predecessors.size(); predecessorIndex++) {
         BasicBlock* predecessor = block->predecessors[predecessorIndex];
index 472f134..12cc064 100644 (file)
@@ -49,6 +49,7 @@ struct NodeOrigin {
     
     bool isSet() const
     {
+        ASSERT(semantic.isSet() == forExit.isSet());
         return semantic.isSet();
     }
     
index 13aabac..36be0b5 100644 (file)
@@ -145,7 +145,8 @@ private:
         // materializations.
         
         m_sinkCandidates.clear();
-        m_edgeToMaterializationPoint.clear();
+        m_materializationToEscapee.clear();
+        m_materializationSiteToMaterializations.clear();
         
         BlockMap<HashMap<Node*, bool>> materializedAtHead(m_graph);
         BlockMap<HashMap<Node*, bool>> materializedAtTail(m_graph);
@@ -235,7 +236,14 @@ private:
             return;
         
         // A materialization edge exists at any point where a node escapes but hasn't been
-        // materialized yet.
+        // materialized yet. We do this in two parts. First we find all of the nodes that cause
+        // escaping to happen, where the escapee had not yet been materialized. This catches
+        // everything but loops. We then catch loops - as well as weirder control flow constructs -
+        // in a subsequent pass that looks at places in the CFG where an edge exists from a block
+        // that hasn't materialized to a block that has. We insert the materialization along such an
+        // edge, and we rely on the fact that critical edges were already broken so that we actually
+        // either insert the materialization at the head of the successor or the tail of the
+        // predecessor.
         //
         // FIXME: This can create duplicate allocations when we really only needed to perform one.
         // For example:
@@ -254,6 +262,8 @@ private:
         // materialization point right at the top of the then case of "if (rare)". To do this, we can
         // find the LCA of the various materializations in the dom tree.
         // https://bugs.webkit.org/show_bug.cgi?id=137124
+        
+        // First pass: find intra-block materialization points.
         for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
             HashSet<Node*> materialized;
             for (auto pair : materializedAtHead[block]) {
@@ -274,20 +284,70 @@ private:
                         if (!materialized.add(escapee).isNewEntry)
                             return;
                         
-                        Node* materialize = createMaterialize(escapee, node->origin);
-                        if (verbose)
-                            dataLog("Adding materialization point: ", node, "->", escapee, " = ", materialize, "\n");
-                        m_edgeToMaterializationPoint.add(
-                            std::make_pair(node, escapee), materialize);
+                        createMaterialize(escapee, node);
                     });
             }
         }
+        
+        // Second pass: find CFG edge materialization points.
+        for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
+            for (BasicBlock* successorBlock : block->successors()) {
+                for (auto pair : materializedAtHead[successorBlock]) {
+                    Node* allocation = pair.key;
+                    
+                    // We only care if it is materialized in the successor.
+                    if (!pair.value)
+                        continue;
+                    
+                    // We only care about sinking candidates.
+                    if (!m_sinkCandidates.contains(allocation))
+                        continue;
+                    
+                    // We only care if it isn't materialized in the predecessor.
+                    if (materializedAtTail[block].get(allocation))
+                        continue;
+                    
+                    // We need to decide if we put the materialization at the head of the successor,
+                    // or the tail of the predecessor. It needs to be placed so that the allocation
+                    // is never materialized before, and always materialized after.
+                    
+                    // Is it never materialized in any of successor's predecessors? I like to think
+                    // of "successors' predecessors" and "predecessor's successors" as the "shadow",
+                    // because of what it looks like when you draw it.
+                    bool neverMaterializedInShadow = true;
+                    for (BasicBlock* shadowBlock : successorBlock->predecessors) {
+                        if (materializedAtTail[shadowBlock].get(allocation)) {
+                            neverMaterializedInShadow = false;
+                            break;
+                        }
+                    }
+                    
+                    if (neverMaterializedInShadow) {
+                        createMaterialize(allocation, successorBlock->firstOriginNode());
+                        continue;
+                    }
+                    
+                    // Because we had broken critical edges, it must be the case that the
+                    // predecessor's successors all materialize the object. This is because the
+                    // previous case is guaranteed to catch the case where the successor only has
+                    // one predecessor. When critical edges are broken, this is also the only case
+                    // where the predecessor could have had multiple successors. Therefore we have
+                    // already handled the case where the predecessor has multiple successors.
+                    DFG_ASSERT(m_graph, block, block->numSuccessors() == 1);
+                    
+                    createMaterialize(allocation, block->last());
+                }
+            }
+        }
     }
     
     void placeMaterializationPoints()
     {
         m_ssaCalculator.reset();
         
+        // The "variables" are the object allocations that we are sinking. So, nodeToVariable maps
+        // sink candidates (aka escapees) to the SSACalculator's notion of Variable, and indexToNode
+        // maps in the opposite direction using the SSACalculator::Variable::index() as the key.
         HashMap<Node*, SSACalculator::Variable*> nodeToVariable;
         Vector<Node*> indexToNode;
         
@@ -303,17 +363,11 @@ private:
                 if (SSACalculator::Variable* variable = nodeToVariable.get(node))
                     m_ssaCalculator.newDef(variable, block, node);
                 
-                m_graph.doToChildren(
-                    node,
-                    [&] (Edge edge) {
-                        Node* materialize =
-                            m_edgeToMaterializationPoint.get(std::make_pair(node, edge.node()));
-                        if (!materialize)
-                            return;
-                        
-                        m_ssaCalculator.newDef(
-                            nodeToVariable.get(edge.node()), block, materialize);
-                    });
+                for (Node* materialize : m_materializationSiteToMaterializations.get(node)) {
+                    m_ssaCalculator.newDef(
+                        nodeToVariable.get(m_materializationToEscapee.get(materialize)),
+                        block, materialize);
+                }
             }
         }
         
@@ -361,20 +415,15 @@ private:
             for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
                 Node* node = block->at(nodeIndex);
 
-                m_graph.doToChildren(
-                    node,
-                    [&] (Edge edge) {
-                        Node* materialize = m_edgeToMaterializationPoint.get(
-                            std::make_pair(node, edge.node()));
-                        if (materialize) {
-                            m_insertionSet.insert(nodeIndex, materialize);
-                            insertOSRHintsForUpdate(
-                                m_insertionSet, nodeIndex, node->origin,
-                                availabilityCalculator.m_availability, edge.node(), materialize);
-                            mapping.set(edge.node(), materialize);
-                        }
-                    });
-
+                for (Node* materialize : m_materializationSiteToMaterializations.get(node)) {
+                    Node* escapee = m_materializationToEscapee.get(materialize);
+                    m_insertionSet.insert(nodeIndex, materialize);
+                    insertOSRHintsForUpdate(
+                        m_insertionSet, nodeIndex, node->origin,
+                        availabilityCalculator.m_availability, escapee, materialize);
+                    mapping.set(escapee, materialize);
+                }
+                    
                 availabilityCalculator.executeNode(node);
                 
                 m_graph.doToChildren(
@@ -386,7 +435,8 @@ private:
             }
             
             size_t upsilonInsertionPoint = block->size() - 1;
-            NodeOrigin upsilonOrigin = block->last()->origin;
+            Node* upsilonWhere = block->last();
+            NodeOrigin upsilonOrigin = upsilonWhere->origin;
             for (BasicBlock* successorBlock : block->successors()) {
                 for (SSACalculator::Def* phiDef : m_ssaCalculator.phisForBlock(successorBlock)) {
                     Node* phiNode = phiDef->value();
@@ -399,7 +449,7 @@ private:
                         // If we have a Phi that combines materializations with the original
                         // phantom object, then the path with the phantom object must materialize.
                         
-                        incoming = createMaterialize(allocation, upsilonOrigin);
+                        incoming = createMaterialize(allocation, upsilonWhere);
                         m_insertionSet.insert(upsilonInsertionPoint, incoming);
                         insertOSRHintsForUpdate(
                             m_insertionSet, upsilonInsertionPoint, upsilonOrigin,
@@ -407,14 +457,9 @@ private:
                     } else
                         incoming = originalIncoming;
                     
-                    Node* upsilon = m_insertionSet.insertNode(
+                    m_insertionSet.insertNode(
                         upsilonInsertionPoint, SpecNone, Upsilon, upsilonOrigin,
                         OpInfo(phiNode), incoming->defaultEdge());
-                    
-                    if (originalIncoming == allocation) {
-                        m_edgeToMaterializationPoint.add(
-                            std::make_pair(upsilon, allocation), incoming);
-                    }
                 }
             }
             
@@ -502,12 +547,6 @@ private:
     
     void promoteSunkenFields()
     {
-        // Henceforth when we encounter a materialization point, we will want to ask *who* it is
-        // a materialization for. Invert the map to be able to answer such questions.
-        m_materializationPointToEscapee.clear();
-        for (auto pair : m_edgeToMaterializationPoint)
-            m_materializationPointToEscapee.add(pair.value, pair.key.second);
-        
         // Collect the set of heap locations that we will be operating over.
         HashSet<PromotedHeapLocation> locations;
         for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
@@ -615,7 +654,7 @@ private:
             for (Node* node : *block) {
                 m_graph.performSubstitution(node);
                 
-                if (Node* escapee = m_materializationPointToEscapee.get(node))
+                if (Node* escapee = m_materializationToEscapee.get(node))
                     populateMaterialize(block, node, escapee);
                 
                 promoteHeapAccess(
@@ -717,26 +756,37 @@ private:
         }
     }
     
-    Node* createMaterialize(Node* escapee, const NodeOrigin whereOrigin)
+    Node* createMaterialize(Node* escapee, Node* where)
     {
+        Node* result = nullptr;
+        
         switch (escapee->op()) {
         case NewObject:
         case MaterializeNewObject: {
             ObjectMaterializationData* data = m_graph.m_objectMaterializationData.add();
             
-            Node* result = m_graph.addNode(
+            result = m_graph.addNode(
                 escapee->prediction(), Node::VarArg, MaterializeNewObject,
                 NodeOrigin(
                     escapee->origin.semantic,
-                    whereOrigin.forExit),
+                    where->origin.forExit),
                 OpInfo(data), OpInfo(), 0, 0);
-            return result;
+            break;
         }
             
         default:
             DFG_CRASH(m_graph, escapee, "Bad escapee op");
-            return nullptr;
+            break;
         }
+        
+        if (verbose)
+            dataLog("Creating materialization point at ", where, " for ", escapee, ": ", result, "\n");
+        
+        m_materializationToEscapee.add(result, escapee);
+        m_materializationSiteToMaterializations.add(
+            where, Vector<Node*>()).iterator->value.append(result);
+        
+        return result;
     }
     
     void populateMaterialize(BasicBlock* block, Node* node, Node* escapee)
@@ -791,8 +841,8 @@ private:
     
     SSACalculator m_ssaCalculator;
     HashSet<Node*> m_sinkCandidates;
-    HashMap<std::pair<Node*, Node*>, Node*> m_edgeToMaterializationPoint;
-    HashMap<Node*, Node*> m_materializationPointToEscapee;
+    HashMap<Node*, Node*> m_materializationToEscapee;
+    HashMap<Node*, Vector<Node*>> m_materializationSiteToMaterializations;
     HashMap<Node*, Vector<PromotedHeapLocation>> m_locationsForAllocation;
     HashMap<PromotedHeapLocation, SSACalculator::Variable*> m_locationToVariable;
     Vector<PromotedHeapLocation> m_indexToLocation;
index b569eab..2f2e00d 100644 (file)
@@ -213,6 +213,23 @@ public:
                 case Identity:
                     VALIDATE((node), canonicalResultRepresentation(node->result()) == canonicalResultRepresentation(node->child1()->result()));
                     break;
+                case SetLocal:
+                case PutLocal:
+                case Upsilon:
+                    VALIDATE((node), !!node->child1());
+                    switch (node->child1().useKind()) {
+                    case UntypedUse:
+                    case CellUse:
+                    case Int32Use:
+                    case Int52RepUse:
+                    case DoubleRepUse:
+                    case BooleanUse:
+                        break;
+                    default:
+                        VALIDATE((node), !"Bad use kind");
+                        break;
+                    }
+                    break;
                 case MakeRope:
                 case ValueAdd:
                 case ArithAdd:
index bc7a34a..9c4d925 100644 (file)
@@ -178,7 +178,7 @@ typedef const char* optionString;
     v(bool, enableCallEdgeProfiling, true) \
     v(unsigned, frequentCallThreshold, 2) \
     v(bool, optimizeNativeCalls, false) \
-    v(bool, enableObjectAllocationSinking, false) \
+    v(bool, enableObjectAllocationSinking, true) \
     \
     v(bool, enableConcurrentJIT, true) \
     v(unsigned, numberOfDFGCompilerThreads, computeNumberOfWorkerThreads(2, 2) - 1) \