Attachment 340829 Details for Bug 144525 – WIP

[patch] WIP

b-backup.diff (text/plain), 12.17 KB, created by Saam Barati on 2018-05-20 23:05:06 PDT

(hide)

Description:

Filename:

MIME Type:

Creator: Saam Barati

Created: 2018-05-20 23:05:06 PDT

Size: 12.17 KB

patch

obsolete

>Index: Source/JavaScriptCore/dfg/DFGLICMPhase.cpp
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGLICMPhase.cpp	(revision 232008)
>+++ Source/JavaScriptCore/dfg/DFGLICMPhase.cpp	(working copy)
>@@ -242,38 +242,138 @@ private:
>             return false;
>         }
>         
>+        // FIXME: At this point if the hoisting of the full node fails but the node has type checks,
>+        // we could still hoist just the checks.
>+        // https://bugs.webkit.org/show_bug.cgi?id=144525
>+        
>+        m_state.initializeTo(data.preHeader);
>+        NodeOrigin originalOrigin = node->origin;
>+        bool canSpeculateBlindly = !m_graph.hasGlobalExitSite(originalOrigin.semantic, HoistingFailed);
>+
>+        // NOTE: We could just use BackwardsDominators here directly, since we already know that the
>+        // preHeader dominates fromBlock. But we wouldn't get anything from being so clever, since
>+        // dominance checks are O(1) and only a few integer compares.
>+        bool isControlFlowEquivalent = m_graph.m_controlEquivalenceAnalysis->dominatesEquivalently(data.preHeader, fromBlock);
>+
>+        bool addsBlindSpeculation = !isControlFlowEquivalent;
>+        NodeOrigin terminalOrigin = data.preHeader->terminal()->origin;
>+
>+        auto insertHoistedNode = [&] (Node* node) {
>+            data.preHeader->insertBeforeTerminal(node);
>+            node->owner = data.preHeader;
>+            node->origin = terminalOrigin.withSemantic(node->origin.semantic);
>+            node->origin.wasHoisted |= addsBlindSpeculation;
>+        };
>+
>+        // For abstract interpretation, these are in the reverse order that they appear in this
>+        // vector.
>+        Vector<Node*, 2> hoistedNodesReverse;
>+        hoistedNodesReverse.append(node);
>+
>+        auto updateAbstractState = [&] {
>+            // We can trust what AI proves about edge proof statuses when hoisting to the preheader.
>+            m_state.trustEdgeProofs();
>+            for (unsigned i = hoistedNodesReverse.size(); i--;)
>+                m_interpreter.execute(hoistedNodesReverse[i]);
>+            // However, when walking various inner loops below, the proof status of
>+            // an edge may be trivially true, even if it's not true in the preheader
>+            // we hoist to. We don't allow the below node executions to change the
>+            // state of edge proofs. An example of where a proof is trivially true
>+            // is if we have two loops, L1 and L2, where L2 is nested inside L1. The
>+            // header for L1 dominates L2. We hoist a Check from L1's header into L1's
>+            // preheader. However, inside L2's preheader, we can't trust that AI will
>+            // tell us this edge is proven. It's proven in L2's preheader because L2
>+            // is dominated by L1's header. However, the edge is not guaranteed to be
>+            // proven inside L1's preheader.
>+            m_state.dontTrustEdgeProofs();
>+
>+            // Modify the states at the end of the preHeader of the loop we hoisted to,
>+            // and all pre-headers inside the loop. This isn't a stability bottleneck right now
>+            // because most loops are small and most blocks belong to few loops.
>+            for (unsigned bodyIndex = loop->size(); bodyIndex--;) {
>+                BasicBlock* subBlock = loop->at(bodyIndex);
>+                const NaturalLoop* subLoop = m_graph.m_ssaNaturalLoops->headerOf(subBlock);
>+                if (!subLoop)
>+                    continue;
>+                BasicBlock* subPreHeader = m_data[subLoop->index()].preHeader;
>+                // We may not have given this loop a pre-header because either it didn't have exitOK
>+                // or the header had multiple predecessors that it did not dominate. In that case the
>+                // loop wouldn't be a hoisting candidate anyway, so we don't have to do anything.
>+                if (!subPreHeader)
>+                    continue;
>+                // The pre-header's tail may be unreachable, in which case we have nothing to do.
>+                if (!subPreHeader->cfaDidFinish)
>+                    continue;
>+                // We handled this above.
>+                if (subPreHeader == data.preHeader)
>+                    continue;
>+                m_state.initializeTo(subPreHeader);
>+                for (unsigned i = hoistedNodesReverse.size(); i--;)
>+                    m_interpreter.execute(hoistedNodesReverse[i]);
>+            }
>+        };
>+        
>+        auto tryHoistAnyChecks = [&] {
>+            // OOPS: addsBlindSpeculation may be a bit too conservative since nodes mayExit for reasons
>+            // that aren't edge type checks.
>+            if (addsBlindSpeculation && !canSpeculateBlindly)
>+                return false;
>+
>+            bool hoistedAnyChecks = false;
>+
>+            hoistedNodesReverse.clear(); // We may have preemptively appended nodes to this. Clear those out. This is only called when we do no other hoisting.
>+
>+            m_graph.doToChildren(node, [&] (Edge edge) {
>+                if (!m_graph.m_ssaDominators->dominates(edge.node()->owner, data.preHeader))
>+                    return;
>+
>+                if (!edge.willHaveCheck())
>+                    return;
>+
>+                if (m_state.forNode(edge).m_type & SpecEmpty) {
>+                    // OOPS: make it so that we know what checks may/may not crash on empty and selectively check them.
>+                    return;
>+                }
>+
>+                // OOPS: aggregate all checks into a single Check/CheckVarargs node...
>+                Node* check = m_graph.addNode(Check, originalOrigin, edge);
>+                dataLogLn("Hoisting check on node: ", edge.node()->index(), " to block: ", data.preHeader->index, " result node: ", check->index());
>+                insertHoistedNode(check);
>+                hoistedNodesReverse.insert(0, check);
>+                hoistedAnyChecks = true;
>+            });
>+
>+            if (hoistedAnyChecks) {
>+                updateAbstractState();
>+                //dataLogLn("Hoisted just checks!");
>+            }
>+
>+            return hoistedAnyChecks;
>+        };
>+
>         if (!edgesDominate(m_graph, node, data.preHeader)) {
>             if (verbose) {
>                 dataLog(
>                     "    Not hoisting ", node, " because it isn't loop invariant.\n");
>             }
>-            return false;
>+            return tryHoistAnyChecks();
>         }
>         
>-        // FIXME: At this point if the hoisting of the full node fails but the node has type checks,
>-        // we could still hoist just the checks.
>-        // https://bugs.webkit.org/show_bug.cgi?id=144525
>-        
>+        // It's not safe to consult the AbstractState until we prove dominance of all the
>+        // edges to the preHeader we're hoisting to. Once we prove that, we can try to
>+        // further approximate addsBlindSpeculation. We are more conservative above before
>+        // we prove all edges dominate the preHeader.
>+        addsBlindSpeculation = mayExit(m_graph, node, m_state) && !isControlFlowEquivalent;
>+
>         if (readsOverlap(m_graph, node, data.writes)) {
>             if (verbose) {
>                 dataLog(
>                     "    Not hoisting ", node,
>                     " because it reads things that the loop writes.\n");
>             }
>-            return false;
>+            return tryHoistAnyChecks();
>         }
>         
>-        m_state.initializeTo(data.preHeader);
>-
>-        NodeOrigin originalOrigin = node->origin;
>-        bool canSpeculateBlindly = !m_graph.hasGlobalExitSite(originalOrigin.semantic, HoistingFailed);
>-
>-        // NOTE: We could just use BackwardsDominators here directly, since we already know that the
>-        // preHeader dominates fromBlock. But we wouldn't get anything from being so clever, since
>-        // dominance checks are O(1) and only a few integer compares.
>-        bool addsBlindSpeculation = mayExit(m_graph, node, m_state)
>-            && !m_graph.m_controlEquivalenceAnalysis->dominatesEquivalently(data.preHeader, fromBlock);
>-        
>         if (addsBlindSpeculation && !canSpeculateBlindly) {
>             if (verbose) {
>                 dataLog(
>@@ -281,23 +381,9 @@ private:
>                     *data.preHeader, ") is not control equivalent to the node's original block (",
>                     *fromBlock, ") and hoisting had previously failed.\n");
>             }
>-            return false;
>+            return tryHoistAnyChecks();
>         }
>         
>-        // For abstract interpretation, these are in the reverse order that they appear in this
>-        // vector.
>-        Vector<Node*, 2> hoistedNodesReverse;
>-        hoistedNodesReverse.append(node);
>-
>-        NodeOrigin terminalOrigin = data.preHeader->terminal()->origin;
>-        
>-        auto insertHoistedNode = [&] (Node* node) {
>-            data.preHeader->insertBeforeTerminal(node);
>-            node->owner = data.preHeader;
>-            node->origin = terminalOrigin.withSemantic(node->origin.semantic);
>-            node->origin.wasHoisted |= addsBlindSpeculation;
>-        };
>-        
>         if (!safeToExecute(m_state, m_graph, node)) {
>             // See if we can rescue the situation by inserting blind speculations.
>             bool ignoreEmptyChildren = true;
>@@ -322,7 +408,7 @@ private:
>                     dataLog(
>                         "    Not hoisting ", node, " because it isn't safe to execute.\n");
>                 }
>-                return false;
>+                return tryHoistAnyChecks();
>             }
>         }
>         
>@@ -333,48 +419,7 @@ private:
>         }
> 
>         insertHoistedNode(node);
>-        
>-        // We can trust what AI proves about edge proof statuses when hoisting to the preheader.
>-        m_state.trustEdgeProofs();
>-        m_state.initializeTo(data.preHeader);
>-        for (unsigned i = hoistedNodesReverse.size(); i--;)
>-            m_interpreter.execute(hoistedNodesReverse[i]);
>-        // However, when walking various inner loops below, the proof status of
>-        // an edge may be trivially true, even if it's not true in the preheader
>-        // we hoist to. We don't allow the below node executions to change the
>-        // state of edge proofs. An example of where a proof is trivially true
>-        // is if we have two loops, L1 and L2, where L2 is nested inside L1. The
>-        // header for L1 dominates L2. We hoist a Check from L1's header into L1's
>-        // preheader. However, inside L2's preheader, we can't trust that AI will
>-        // tell us this edge is proven. It's proven in L2's preheader because L2
>-        // is dominated by L1's header. However, the edge is not guaranteed to be
>-        // proven inside L1's preheader.
>-        m_state.dontTrustEdgeProofs();
>-
>-        // Modify the states at the end of the preHeader of the loop we hoisted to,
>-        // and all pre-headers inside the loop. This isn't a stability bottleneck right now
>-        // because most loops are small and most blocks belong to few loops.
>-        for (unsigned bodyIndex = loop->size(); bodyIndex--;) {
>-            BasicBlock* subBlock = loop->at(bodyIndex);
>-            const NaturalLoop* subLoop = m_graph.m_ssaNaturalLoops->headerOf(subBlock);
>-            if (!subLoop)
>-                continue;
>-            BasicBlock* subPreHeader = m_data[subLoop->index()].preHeader;
>-            // We may not have given this loop a pre-header because either it didn't have exitOK
>-            // or the header had multiple predecessors that it did not dominate. In that case the
>-            // loop wouldn't be a hoisting candidate anyway, so we don't have to do anything.
>-            if (!subPreHeader)
>-                continue;
>-            // The pre-header's tail may be unreachable, in which case we have nothing to do.
>-            if (!subPreHeader->cfaDidFinish)
>-                continue;
>-            // We handled this above.
>-            if (subPreHeader == data.preHeader)
>-                continue;
>-            m_state.initializeTo(subPreHeader);
>-            for (unsigned i = hoistedNodesReverse.size(); i--;)
>-                m_interpreter.execute(hoistedNodesReverse[i]);
>-        }
>+        updateAbstractState();
> 
>         if (node->flags() & NodeHasVarArgs)
>             nodeRef = m_graph.addNode(CheckVarargs, originalOrigin, m_graph.copyVarargChildren(node));

Actions: View | Formatted Diff | Diff

Attachments on bug 144525: 340829 | 340832 | 340865 | 340953