Node::origin should always be set, and the dead zone due to SSA Phis can just use...
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 27 Aug 2015 07:16:07 +0000 (07:16 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 27 Aug 2015 07:16:07 +0000 (07:16 +0000)
https://bugs.webkit.org/show_bug.cgi?id=148462

Reviewed by Saam Barati.

The need to label nodes that absolutely cannot exit was first observed when we introduced SSA form.
We indicated this by not setting the CodeOrigin.

But just recently (http://trac.webkit.org/changeset/188979), we added a more comprehensive "exitOK"
bit in NodeOrigin. After that change, there were two ways of indicating that you cannot exit:
!exitOK and an unset NodeOrigin. An unset NodeOrigin implied !exitOK.

Now, this change is about removing the old way so that we only use !exitOK. From now on, all nodes
must have their NodeOrigin set, and the IR validation will check this. This means that I could
remove various pieces of cruft for dealing with unset NodeOrigins, but I did have to add some new
cruft to ensure that all nodes we create have a NodeOrigin.

This change simplifies our IR by having a simpler rule about when NodeOrigin is set: it's always
set.

* dfg/DFGBasicBlock.cpp:
(JSC::DFG::BasicBlock::isInBlock):
(JSC::DFG::BasicBlock::removePredecessor):
(JSC::DFG::BasicBlock::firstOriginNode): Deleted.
(JSC::DFG::BasicBlock::firstOrigin): Deleted.
* dfg/DFGBasicBlock.h:
(JSC::DFG::BasicBlock::begin):
(JSC::DFG::BasicBlock::end):
(JSC::DFG::BasicBlock::numSuccessors):
(JSC::DFG::BasicBlock::successor):
* dfg/DFGCombinedLiveness.cpp:
(JSC::DFG::liveNodesAtHead):
* dfg/DFGConstantHoistingPhase.cpp:
* dfg/DFGCriticalEdgeBreakingPhase.cpp:
(JSC::DFG::CriticalEdgeBreakingPhase::breakCriticalEdge):
* dfg/DFGForAllKills.h:
(JSC::DFG::forAllKilledOperands):
* dfg/DFGIntegerRangeOptimizationPhase.cpp:
* dfg/DFGLoopPreHeaderCreationPhase.cpp:
(JSC::DFG::createPreHeader):
(JSC::DFG::LoopPreHeaderCreationPhase::run):
* dfg/DFGOSRAvailabilityAnalysisPhase.cpp:
(JSC::DFG::OSRAvailabilityAnalysisPhase::run):
* dfg/DFGObjectAllocationSinkingPhase.cpp:
* dfg/DFGPutStackSinkingPhase.cpp:
* dfg/DFGSSAConversionPhase.cpp:
(JSC::DFG::SSAConversionPhase::run):
* dfg/DFGValidate.cpp:
(JSC::DFG::Validate::validate):
(JSC::DFG::Validate::validateSSA):

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

14 files changed:
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/dfg/DFGBasicBlock.cpp
Source/JavaScriptCore/dfg/DFGBasicBlock.h
Source/JavaScriptCore/dfg/DFGCombinedLiveness.cpp
Source/JavaScriptCore/dfg/DFGConstantHoistingPhase.cpp
Source/JavaScriptCore/dfg/DFGCriticalEdgeBreakingPhase.cpp
Source/JavaScriptCore/dfg/DFGForAllKills.h
Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp
Source/JavaScriptCore/dfg/DFGLoopPreHeaderCreationPhase.cpp
Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.cpp
Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp
Source/JavaScriptCore/dfg/DFGPutStackSinkingPhase.cpp
Source/JavaScriptCore/dfg/DFGSSAConversionPhase.cpp
Source/JavaScriptCore/dfg/DFGValidate.cpp

index 3340e18..b381937 100644 (file)
@@ -1,3 +1,56 @@
+2015-08-26  Filip Pizlo  <fpizlo@apple.com>
+
+        Node::origin should always be set, and the dead zone due to SSA Phis can just use exitOK=false
+        https://bugs.webkit.org/show_bug.cgi?id=148462
+
+        Reviewed by Saam Barati.
+
+        The need to label nodes that absolutely cannot exit was first observed when we introduced SSA form.
+        We indicated this by not setting the CodeOrigin.
+
+        But just recently (http://trac.webkit.org/changeset/188979), we added a more comprehensive "exitOK"
+        bit in NodeOrigin. After that change, there were two ways of indicating that you cannot exit:
+        !exitOK and an unset NodeOrigin. An unset NodeOrigin implied !exitOK.
+
+        Now, this change is about removing the old way so that we only use !exitOK. From now on, all nodes
+        must have their NodeOrigin set, and the IR validation will check this. This means that I could
+        remove various pieces of cruft for dealing with unset NodeOrigins, but I did have to add some new
+        cruft to ensure that all nodes we create have a NodeOrigin.
+
+        This change simplifies our IR by having a simpler rule about when NodeOrigin is set: it's always
+        set.
+
+        * dfg/DFGBasicBlock.cpp:
+        (JSC::DFG::BasicBlock::isInBlock):
+        (JSC::DFG::BasicBlock::removePredecessor):
+        (JSC::DFG::BasicBlock::firstOriginNode): Deleted.
+        (JSC::DFG::BasicBlock::firstOrigin): Deleted.
+        * dfg/DFGBasicBlock.h:
+        (JSC::DFG::BasicBlock::begin):
+        (JSC::DFG::BasicBlock::end):
+        (JSC::DFG::BasicBlock::numSuccessors):
+        (JSC::DFG::BasicBlock::successor):
+        * dfg/DFGCombinedLiveness.cpp:
+        (JSC::DFG::liveNodesAtHead):
+        * dfg/DFGConstantHoistingPhase.cpp:
+        * dfg/DFGCriticalEdgeBreakingPhase.cpp:
+        (JSC::DFG::CriticalEdgeBreakingPhase::breakCriticalEdge):
+        * dfg/DFGForAllKills.h:
+        (JSC::DFG::forAllKilledOperands):
+        * dfg/DFGIntegerRangeOptimizationPhase.cpp:
+        * dfg/DFGLoopPreHeaderCreationPhase.cpp:
+        (JSC::DFG::createPreHeader):
+        (JSC::DFG::LoopPreHeaderCreationPhase::run):
+        * dfg/DFGOSRAvailabilityAnalysisPhase.cpp:
+        (JSC::DFG::OSRAvailabilityAnalysisPhase::run):
+        * dfg/DFGObjectAllocationSinkingPhase.cpp:
+        * dfg/DFGPutStackSinkingPhase.cpp:
+        * dfg/DFGSSAConversionPhase.cpp:
+        (JSC::DFG::SSAConversionPhase::run):
+        * dfg/DFGValidate.cpp:
+        (JSC::DFG::Validate::validate):
+        (JSC::DFG::Validate::validateSSA):
+
 2015-08-26  Saam barati  <sbarati@apple.com>
 
         MarkedBlock::allocateBlock will have the wrong allocation size when (sizeof(MarkedBlock) + bytes) is divisible by WTF::pageSize()
index f83f50c..383ee4b 100644 (file)
@@ -102,21 +102,6 @@ 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 ef9e6c5..ce7e23d 100644 (file)
@@ -141,10 +141,7 @@ 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 terminal()->numSuccessors(); }
     
     BasicBlock*& successor(unsigned index)
index ccf9433..a0d9327 100644 (file)
@@ -43,7 +43,7 @@ HashSet<Node*> liveNodesAtHead(Graph& graph, BasicBlock* block)
     
     AvailabilityMap& availabilityMap = block->ssa->availabilityAtHead;
     graph.forAllLocalsLiveInBytecode(
-        block->firstOrigin().forExit,
+        block->at(0)->origin.forExit,
         [&] (VirtualRegister reg) {
             availabilityMap.closeStartingWithLocal(
                 reg,
index 68f3651..4a72f95 100644 (file)
@@ -94,7 +94,7 @@ public:
                     HashMap<FrozenValue*, Node*>& values = valuesFor(node->op());
                     auto result = values.add(node->constant(), node);
                     if (result.isNewEntry)
-                        node->origin = NodeOrigin();
+                        node->origin = m_graph.block(0)->at(0)->origin;
                     else {
                         node->setReplacement(result.iterator->value);
                         toFree.append(node);
index 18f6f5e..1656774 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)->firstOrigin(), OpInfo(*successor));
+            m_graph, SpecNone, Jump, (*successor)->at(0)->origin, OpInfo(*successor));
         pad->predecessors.append(predecessor);
         (*successor)->replacePredecessor(predecessor, pad);
         
index bb630cd..51ac55d 100644 (file)
@@ -55,33 +55,18 @@ void forAllKilledOperands(Graph& graph, Node* nodeBefore, Node* nodeAfter, const
     CodeOrigin after = nodeAfter->origin.forExit;
     
     VirtualRegister alreadyNoted;
-    if (!!after) {
-        // If we MovHint something that is live at the time, then we kill the old value.
-        if (nodeAfter->containsMovHint()) {
-            VirtualRegister reg = nodeAfter->unlinkedLocal();
-            if (graph.isLiveInBytecode(reg, after)) {
-                functor(reg);
-                alreadyNoted = reg;
-            }
+    // If we MovHint something that is live at the time, then we kill the old value.
+    if (nodeAfter->containsMovHint()) {
+        VirtualRegister reg = nodeAfter->unlinkedLocal();
+        if (graph.isLiveInBytecode(reg, after)) {
+            functor(reg);
+            alreadyNoted = reg;
         }
     }
     
-    if (!before) {
-        if (!after)
-            return;
-        // The true before-origin is the origin at predecessors that jump to us. But there can be
-        // many such predecessors and they will likely all have a different origin. So, it's better
-        // to do the conservative thing.
-        graph.forAllLocalsLiveInBytecode(after, functor);
-        return;
-    }
-    
     if (before == after)
         return;
     
-    // before could be unset even if after is, but the opposite cannot happen.
-    ASSERT(!!after);
-    
     // It's easier to do this if the inline call frames are the same. This is way faster than the
     // other loop, below.
     if (before.inlineCallFrame == after.inlineCallFrame) {
index e2dca7c..6abd697 100644 (file)
@@ -999,7 +999,7 @@ public:
             }
         }
         if (!m_zero) {
-            m_zero = m_insertionSet.insertConstant(0, NodeOrigin(), jsNumber(0));
+            m_zero = m_insertionSet.insertConstant(0, m_graph.block(0)->at(0)->origin, jsNumber(0));
             m_insertionSet.execute(m_graph.block(0));
         }
         
index a3f8437..e3750c7 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->firstOrigin(), OpInfo(block));
+        graph, SpecNone, Jump, block->at(0)->origin, OpInfo(block));
     
     for (unsigned predecessorIndex = 0; predecessorIndex < block->predecessors.size(); predecessorIndex++) {
         BasicBlock* predecessor = block->predecessors[predecessorIndex];
@@ -108,7 +108,7 @@ public:
             // A pre-header is most useful if it's possible to exit from its terminal. Hence
             // if the terminal of the existing pre-header doesn't allow for exit, but the first
             // origin of the loop header does, then we should create a new pre-header.
-            if (!needsNewPreHeader && loop.header()->firstOrigin().exitOK
+            if (!needsNewPreHeader && loop.header()->at(0)->origin.exitOK
                 && !existingPreHeader->terminal()->origin.exitOK)
                 needsNewPreHeader = true;
             
index 8c8419a..5e7fb3b 100644 (file)
@@ -91,7 +91,7 @@ public:
                     BasicBlock* successor = block->successor(successorIndex);
                     successor->ssa->availabilityAtHead.merge(calculator.m_availability);
                     successor->ssa->availabilityAtHead.pruneByLiveness(
-                        m_graph, successor->firstOrigin().forExit);
+                        m_graph, successor->at(0)->origin.forExit);
                 }
             }
         } while (changed);
index 1eba508..79118db 100644 (file)
@@ -1548,7 +1548,7 @@ private:
         // with useless constants everywhere
         HashMap<FrozenValue*, Node*> lazyMapping;
         if (!m_bottom)
-            m_bottom = m_insertionSet.insertConstant(0, NodeOrigin(), jsNumber(1927));
+            m_bottom = m_insertionSet.insertConstant(0, m_graph.block(0)->at(0)->origin, jsNumber(1927));
         for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
             m_heap = m_heapAtHead[block];
 
@@ -1621,7 +1621,7 @@ private:
                 if (m_heapAtHead[block].follow(location))
                     return nullptr;
 
-                Node* phiNode = m_graph.addNode(SpecHeapTop, Phi, NodeOrigin());
+                Node* phiNode = m_graph.addNode(SpecHeapTop, Phi, block->at(0)->origin.withInvalidExit());
                 phiNode->mergeFlags(NodeResultJS);
                 return phiNode;
             });
@@ -1638,7 +1638,7 @@ private:
                 if (!m_heapAtHead[block].getAllocation(identifier).isEscapedAllocation())
                     return nullptr;
 
-                Node* phiNode = m_graph.addNode(SpecHeapTop, Phi, NodeOrigin());
+                Node* phiNode = m_graph.addNode(SpecHeapTop, Phi, block->at(0)->origin.withInvalidExit());
                 phiNode->mergeFlags(NodeResultJS);
                 return phiNode;
             });
@@ -1669,7 +1669,9 @@ private:
 
                 if (m_sinkCandidates.contains(location.base())) {
                     m_insertionSet.insert(
-                        0, location.createHint(m_graph, NodeOrigin(), phiDef->value()));
+                        0,
+                        location.createHint(
+                            m_graph, block->at(0)->origin.withInvalidExit(), phiDef->value()));
                 }
             }
 
@@ -1680,7 +1682,9 @@ private:
                 Node* identifier = indexToNode[variable->index()];
                 m_escapeeToMaterialization.add(identifier, phiDef->value());
                 bool canExit = false;
-                insertOSRHintsForUpdate(0, NodeOrigin(), canExit, availabilityCalculator.m_availability, identifier, phiDef->value());
+                insertOSRHintsForUpdate(
+                    0, block->at(0)->origin, canExit,
+                    availabilityCalculator.m_availability, identifier, phiDef->value());
             }
 
             if (verbose) {
index 4d7ec11..d75cd18 100644 (file)
@@ -358,7 +358,7 @@ public:
                 if (verbose)
                     dataLog("Adding Phi for ", operand, " at ", pointerDump(block), "\n");
                 
-                Node* phiNode = m_graph.addNode(SpecHeapTop, Phi, NodeOrigin());
+                Node* phiNode = m_graph.addNode(SpecHeapTop, Phi, block->at(0)->origin.withInvalidExit());
                 phiNode->mergeFlags(resultFor(format));
                 return phiNode;
             });
index 46a8153..7e4d187 100644 (file)
@@ -149,7 +149,7 @@ public:
                     return nullptr;
                 
                 Node* phiNode = m_graph.addNode(
-                    variable->prediction(), Phi, NodeOrigin());
+                    variable->prediction(), Phi, block->at(0)->origin.withInvalidExit());
                 FlushFormat format = variable->flushFormat();
                 NodeFlags result = resultFor(format);
                 phiNode->mergeFlags(result);
@@ -252,9 +252,12 @@ public:
                 valueForOperand.operand(variable->local()) = phiDef->value();
                 
                 m_insertionSet.insertNode(
-                    phiInsertionPoint, SpecNone, MovHint, NodeOrigin(),
+                    phiInsertionPoint, SpecNone, MovHint, block->at(0)->origin.withInvalidExit(),
                     OpInfo(variable->local().offset()), phiDef->value()->defaultEdge());
             }
+
+            if (block->at(0)->origin.exitOK)
+                m_insertionSet.insertNode(phiInsertionPoint, SpecNone, ExitOK, block->at(0)->origin);
             
             for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
                 Node* node = block->at(nodeIndex);
index 838eecc..352475b 100644 (file)
@@ -187,6 +187,7 @@ public:
             for (size_t i = 0; i < block->size(); ++i) {
                 Node* node = block->at(i);
 
+                VALIDATE((node), node->origin.isSet());
                 VALIDATE((node), node->origin.semantic.isSet() == node->origin.forExit.isSet());
                 VALIDATE((node), !(!node->origin.forExit.isSet() && node->origin.exitOK));
                 VALIDATE((node), !(mayExit(m_graph, node) == Exits && !node->origin.exitOK));
@@ -526,20 +527,21 @@ private:
                 continue;
             
             VALIDATE((block), block->phis.isEmpty());
-            
-            unsigned nodeIndex = 0;
-            for (; nodeIndex < block->size() && !block->at(nodeIndex)->origin.forExit.isSet(); nodeIndex++) { }
-            
-            VALIDATE((block), nodeIndex < block->size());
-            
-            for (; nodeIndex < block->size(); nodeIndex++)
-                VALIDATE((block->at(nodeIndex)), block->at(nodeIndex)->origin.forExit.isSet());
+
+            bool didSeeExitOK = false;
             
             for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
                 Node* node = block->at(nodeIndex);
+                didSeeExitOK |= node->origin.exitOK;
                 switch (node->op()) {
                 case Phi:
-                    VALIDATE((node), !node->origin.forExit.isSet());
+                    // Phi cannot exit, and it would be wrong to hoist anything to the Phi that could
+                    // exit.
+                    VALIDATE((node), !node->origin.exitOK);
+
+                    // It never makes sense to have exitOK anywhere in the block before a Phi. It's only
+                    // OK to exit after all Phis are done.
+                    VALIDATE((node), !didSeeExitOK);
                     break;
                     
                 case GetLocal: