Changeset 232742 in webkit

Timestamp:

Jun 11, 2018, 10:05:49 PM (8 years ago)

Author:

sbarati@apple.com

Message:

Reduce graph size by replacing terminal nodes in blocks that have a ForceOSRExit with Unreachable
​https://bugs.webkit.org/show_bug.cgi?id=181409
<rdar://problem/36383749>

Reviewed by Keith Miller.

This patch is me redoing r226655. This is a patch I wrote when
profiling Speedometer. Fil rolled this change out in r230928. He
showed this slowed down a sunspider tests by ~2x. This sunspider
regression revealed a real performance bug in the original change:
we would kill blocks that reached OSR entry targets, sometimes leading
us to not do OSR entry into the DFG, since we could end up deleting
entire loops from the CFG. The reason for this is that code that has run
~once and that reaches loops often has ForceOSRExits inside of it. The
solution to this is to not perform this optimization on blocks that can
reach OSR entry targets.

The reason I'm redoing this patch is that it turns out Fil rolling
out the change was a Speedometer 2 regression.

This is a modified version of the original ChangeLog I wrote in r226655:

When I was looking at profiler data for Speedometer, I noticed that one of
the hottest functions in Speedometer is around 1100 bytecode operations long.
Only about 100 of those bytecode ops ever execute. However, we ended up
spending a lot of time compiling basic blocks that never executed. We often
plant ForceOSRExit nodes when we parse bytecodes that have a null value profile.
This is the case when such a node never executes.

This patch makes it so that anytime a block has a ForceOSRExit, and that block
can not reach an OSR entry target, we replace its terminal node with an Unreachable
node, and remove all nodes after the ForceOSRExit. This cuts down the graph
size since it removes control flow edges from the CFG. This allows us to get
rid of huge chunks of the CFG in certain programs. When doing this transformation,
we also insert Flushes/PhantomLocals to ensure we can recover values that are bytecode
live-in to the ForceOSRExit.

Using ForceOSRExit as the signal for this is a bit of a hack. It definitely
does not get rid of all the CFG that it could. If we decide it's worth
it, we could use additional inputs into this mechanism. For example, we could
profile if a basic block ever executes inside the LLInt/Baseline, and
remove parts of the CFG based on that.

When running Speedometer with the concurrent JIT turned off, this patch
improves DFG/FTL compile times by around 5%.

• dfg/DFGByteCodeParser.cpp:

(JSC::DFG::ByteCodeParser::addToGraph):
(JSC::DFG::ByteCodeParser::inlineCall):
(JSC::DFG::ByteCodeParser::parse):

• dfg/DFGGraph.cpp:

(JSC::DFG::Graph::blocksInPostOrder):

Location:

trunk/Source/JavaScriptCore

Files:

• ChangeLog (modified) (1 diff)
• dfg/DFGByteCodeParser.cpp (modified) (3 diffs)
• dfg/DFGGraph.cpp (modified) (2 diffs)
• dfg/DFGGraph.h (modified) (1 diff)

trunk/Source/JavaScriptCore/ChangeLog

@@ +1 @@
+2018-06-11  Saam Barati  <sbarati@apple.com>
+
+        Reduce graph size by replacing terminal nodes in blocks that have a ForceOSRExit with Unreachable
+        https://bugs.webkit.org/show_bug.cgi?id=181409
+        <rdar://problem/36383749>
+
+        Reviewed by Keith Miller.
+
+        This patch is me redoing r226655. This is a patch I wrote when
+        profiling Speedometer. Fil rolled this change out in r230928. He
+        showed this slowed down a sunspider tests by ~2x. This sunspider
+        regression revealed a real performance bug in the original change:
+        we would kill blocks that reached OSR entry targets, sometimes leading
+        us to not do OSR entry into the DFG, since we could end up deleting
+        entire loops from the CFG. The reason for this is that code that has run
+        ~once and that reaches loops often has ForceOSRExits inside of it. The
+        solution to this is to not perform this optimization on blocks that can
+        reach OSR entry targets.
+        
+        The reason I'm redoing this patch is that it turns out Fil rolling
+        out the change was a Speedometer 2 regression.
+        
+        This is a modified version of the original ChangeLog I wrote in r226655:
+        
+        When I was looking at profiler data for Speedometer, I noticed that one of
+        the hottest functions in Speedometer is around 1100 bytecode operations long.
+        Only about 100 of those bytecode ops ever execute. However, we ended up
+        spending a lot of time compiling basic blocks that never executed. We often
+        plant ForceOSRExit nodes when we parse bytecodes that have a null value profile.
+        This is the case when such a node never executes.
+        
+        This patch makes it so that anytime a block has a ForceOSRExit, and that block
+        can not reach an OSR entry target, we replace its terminal node with an Unreachable
+        node, and remove all nodes after the ForceOSRExit. This cuts down the graph
+        size since it removes control flow edges from the CFG. This allows us to get
+        rid of huge chunks of the CFG in certain programs. When doing this transformation,
+        we also insert Flushes/PhantomLocals to ensure we can recover values that are bytecode
+        live-in to the ForceOSRExit.
+        
+        Using ForceOSRExit as the signal for this is a bit of a hack. It definitely
+        does not get rid of all the CFG that it could. If we decide it's worth
+        it, we could use additional inputs into this mechanism. For example, we could
+        profile if a basic block ever executes inside the LLInt/Baseline, and
+        remove parts of the CFG based on that.
+        
+        When running Speedometer with the concurrent JIT turned off, this patch
+        improves DFG/FTL compile times by around 5%.
+
+        * dfg/DFGByteCodeParser.cpp:
+        (JSC::DFG::ByteCodeParser::addToGraph):
+        (JSC::DFG::ByteCodeParser::inlineCall):
+        (JSC::DFG::ByteCodeParser::parse):
+        * dfg/DFGGraph.cpp:
+        (JSC::DFG::Graph::blocksInPostOrder):
+
 2018-06-11  Saam Barati  <sbarati@apple.com>
 

trunk/Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp

@@ -698 +698 @@
     {
         VERBOSE_LOG("        appended ", node, " ", Graph::opName(node->op()), "\n");
+
+        m_hasAnyForceOSRExits |= (node->op() == ForceOSRExit);
+
         m_currentBlock->append(node);
         if (clobbersExitState(m_graph, node))
@@ -1151 +1154 @@
     Instruction* m_currentInstruction;
     bool m_hasDebuggerEnabled;
+    bool m_hasAnyForceOSRExits { false };
 };
 
@@ -6833 +6837 @@
     linkBlocks(inlineStackEntry.m_unlinkedBlocks, inlineStackEntry.m_blockLinkingTargets);
 
+    if (m_hasAnyForceOSRExits) {
+        BlockSet blocksToIgnore;
+        for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
+            if (block->isOSRTarget)
+                blocksToIgnore.add(block);
+        }
+
+        {
+            bool isSafeToValidate = false;
+            auto postOrder = m_graph.blocksInPostOrder(isSafeToValidate); // This algorithm doesn't rely on the predecessors list, which is not yet built.
+            bool changed;
+            do {
+                changed = false;
+                for (BasicBlock* block : postOrder) {
+                    for (BasicBlock* successor : block->successors()) {
+                        if (blocksToIgnore.contains(successor)) {
+                            changed |= blocksToIgnore.add(block);
+                            break;
+                        }
+                    }
+                }
+            } while (changed);
+        }
+
+        InsertionSet insertionSet(m_graph);
+        Operands<VariableAccessData*> mapping(OperandsLike, m_graph.block(0)->variablesAtHead);
+
+        for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
+            if (blocksToIgnore.contains(block))
+                continue;
+
+            mapping.fill(nullptr);
+            if (validationEnabled()) {
+                // Verify that it's correct to fill mapping with nullptr.
+                for (unsigned i = 0; i < block->variablesAtHead.size(); ++i) {
+                    Node* node = block->variablesAtHead.at(i);
+                    RELEASE_ASSERT(!node);
+                }
+            }
+
+            for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
+                Node* node = block->at(nodeIndex);
+
+                if (node->hasVariableAccessData(m_graph))
+                    mapping.operand(node->local()) = node->variableAccessData();
+
+                if (node->op() == ForceOSRExit) {
+                    NodeOrigin endOrigin = node->origin.withExitOK(true);
+
+                    if (validationEnabled()) {
+                        // This verifies that we don't need to change any of the successors's predecessor
+                        // list after planting the Unreachable below. At this point in the bytecode
+                        // parser, we haven't linked up the predecessor lists yet.
+                        for (BasicBlock* successor : block->successors())
+                            RELEASE_ASSERT(successor->predecessors.isEmpty());
+                    }
+
+                    block->resize(nodeIndex + 1);
+
+                    insertionSet.insertNode(block->size(), SpecNone, ExitOK, endOrigin);
+
+                    auto insertLivenessPreservingOp = [&] (InlineCallFrame* inlineCallFrame, NodeType op, VirtualRegister operand) {
+                        VariableAccessData* variable = mapping.operand(operand);
+                        if (!variable) {
+                            variable = newVariableAccessData(operand);
+                            mapping.operand(operand) = variable;
+                        }
+
+                        VirtualRegister argument = operand - (inlineCallFrame ? inlineCallFrame->stackOffset : 0);
+                        if (argument.isArgument() && !argument.isHeader()) {
+                            const Vector<ArgumentPosition*>& arguments = m_inlineCallFrameToArgumentPositions.get(inlineCallFrame);
+                            arguments[argument.toArgument()]->addVariable(variable);
+                        }
+
+                        insertionSet.insertNode(block->size(), SpecNone, op, endOrigin, OpInfo(variable));
+                    };
+                    auto addFlushDirect = [&] (InlineCallFrame* inlineCallFrame, VirtualRegister operand) {
+                        insertLivenessPreservingOp(inlineCallFrame, Flush, operand);
+                    };
+                    auto addPhantomLocalDirect = [&] (InlineCallFrame* inlineCallFrame, VirtualRegister operand) {
+                        insertLivenessPreservingOp(inlineCallFrame, PhantomLocal, operand);
+                    };
+                    flushForTerminalImpl(endOrigin.semantic, addFlushDirect, addPhantomLocalDirect);
+
+                    insertionSet.insertNode(block->size(), SpecNone, Unreachable, endOrigin);
+                    insertionSet.execute(block);
+                    break;
+                }
+            }
+        }
+    } else if (validationEnabled()) {
+        // Ensure our bookkeeping for ForceOSRExit nodes is working.
+        for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
+            for (Node* node : *block)
+                RELEASE_ASSERT(node->op() != ForceOSRExit);
+        }
+    }
+    
     m_graph.determineReachability();
     m_graph.killUnreachableBlocks();

trunk/Source/JavaScriptCore/dfg/DFGGraph.cpp

@@ -913 +913 @@
 }
 
-BlockList Graph::blocksInPostOrder()
+BlockList Graph::blocksInPostOrder(bool isSafeToValidate)
 {
     BlockList result;
@@ -932 +932 @@
     }
 
-    if (validationEnabled()) {
+    if (isSafeToValidate && validationEnabled()) { // There are users of this where we haven't yet built of the CFG enough to be able to run dominators.
         auto validateResults = [&] (auto& dominators) {
             // When iterating over reverse post order, we should see dominators

trunk/Source/JavaScriptCore/dfg/DFGGraph.h

@@ -628 +628 @@
     
     BlockList blocksInPreOrder();
-    BlockList blocksInPostOrder();
+    BlockList blocksInPostOrder(bool isSafeToValidate = true);
     
     class NaturalBlockIterable {