DFG combined liveness can be wrong for terminal basic blocks
authorsbarati@apple.com <sbarati@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 12 Jan 2019 00:26:06 +0000 (00:26 +0000)
committersbarati@apple.com <sbarati@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 12 Jan 2019 00:26:06 +0000 (00:26 +0000)
https://bugs.webkit.org/show_bug.cgi?id=193304
<rdar://problem/45268632>

Reviewed by Yusuke Suzuki.

JSTests:

* stress/dfg-combined-liveness-consider-terminal-blocks-bytecode-liveness.js: Added.

Source/JavaScriptCore:

If a block doesn't have any successors, it can't rely on the typical
backwards liveness propagation that CombinedLiveness was doing. The phase
first got what was live in bytecode and IR at the heads of each block. Then
for each block, it made the live at tail the union of the live at head for
each successor. For a terminal block though, this could be wrong. We could
end up saying nothing is live even though many things may be live in bytecode.
We must account for what's bytecode live at the end of the block. Consider a
block that ends with:
```
ForceOSRExit
Unreachable
```

Things may definitely be live in bytecode at the tail. However, we'll
report nothing as being alive. This probably subtly breaks many analyses,
but we have a test case of it breaking the interference analysis that
the ArgumentsEliminationPhase performs.

* dfg/DFGBasicBlock.h:
(JSC::DFG::BasicBlock::last const):
* dfg/DFGCombinedLiveness.cpp:
(JSC::DFG::addBytecodeLiveness):
(JSC::DFG::liveNodesAtHead):
(JSC::DFG::CombinedLiveness::CombinedLiveness):
* dfg/DFGCombinedLiveness.h:

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

JSTests/ChangeLog
JSTests/stress/dfg-combined-liveness-consider-terminal-blocks-bytecode-liveness.js [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/dfg/DFGBasicBlock.h
Source/JavaScriptCore/dfg/DFGCombinedLiveness.cpp
Source/JavaScriptCore/dfg/DFGCombinedLiveness.h

index 736c243..a915dfe 100644 (file)
@@ -1,3 +1,13 @@
+2019-01-11  Saam barati  <sbarati@apple.com>
+
+        DFG combined liveness can be wrong for terminal basic blocks
+        https://bugs.webkit.org/show_bug.cgi?id=193304
+        <rdar://problem/45268632>
+
+        Reviewed by Yusuke Suzuki.
+
+        * stress/dfg-combined-liveness-consider-terminal-blocks-bytecode-liveness.js: Added.
+
 2019-01-11  Yusuke Suzuki  <yusukesuzuki@slowstart.org>
 
         [JSC] Global lexical bindings can shadow global variables if it is `configurable = true`
diff --git a/JSTests/stress/dfg-combined-liveness-consider-terminal-blocks-bytecode-liveness.js b/JSTests/stress/dfg-combined-liveness-consider-terminal-blocks-bytecode-liveness.js
new file mode 100644 (file)
index 0000000..2360a1e
--- /dev/null
@@ -0,0 +1,19 @@
+//@ runDefault("--useConcurrentJIT=0", "--usePutStackSinking=0")
+
+function foo() {
+    var args1 = function () {
+        return arguments;
+    }();
+    var args2 = function () {
+        var result = arguments;
+        result.length = 1;
+        return result;
+    }(1);
+    for (var i = 0; i < 10000000; ++i) {
+        args1.length;
+        args2.length;
+    }
+}
+foo();
+foo();
+foo();
index 3ebb4df..a9ee558 100644 (file)
@@ -1,3 +1,37 @@
+2019-01-11  Saam barati  <sbarati@apple.com>
+
+        DFG combined liveness can be wrong for terminal basic blocks
+        https://bugs.webkit.org/show_bug.cgi?id=193304
+        <rdar://problem/45268632>
+
+        Reviewed by Yusuke Suzuki.
+
+        If a block doesn't have any successors, it can't rely on the typical
+        backwards liveness propagation that CombinedLiveness was doing. The phase
+        first got what was live in bytecode and IR at the heads of each block. Then
+        for each block, it made the live at tail the union of the live at head for
+        each successor. For a terminal block though, this could be wrong. We could
+        end up saying nothing is live even though many things may be live in bytecode.
+        We must account for what's bytecode live at the end of the block. Consider a
+        block that ends with:
+        ```
+        ForceOSRExit
+        Unreachable
+        ```
+        
+        Things may definitely be live in bytecode at the tail. However, we'll
+        report nothing as being alive. This probably subtly breaks many analyses,
+        but we have a test case of it breaking the interference analysis that
+        the ArgumentsEliminationPhase performs.
+
+        * dfg/DFGBasicBlock.h:
+        (JSC::DFG::BasicBlock::last const):
+        * dfg/DFGCombinedLiveness.cpp:
+        (JSC::DFG::addBytecodeLiveness):
+        (JSC::DFG::liveNodesAtHead):
+        (JSC::DFG::CombinedLiveness::CombinedLiveness):
+        * dfg/DFGCombinedLiveness.h:
+
 2019-01-11  Yusuke Suzuki  <yusukesuzuki@slowstart.org>
 
         [JSC] Global lexical bindings can shadow global variables if it is `configurable = true`
index eb5fc9f..1b93343 100644 (file)
@@ -64,6 +64,11 @@ struct BasicBlock : RefCounted<BasicBlock> {
     }
     Node*& operator[](size_t i) { return at(i); }
     Node* operator[](size_t i) const { return at(i); }
+    Node* last() const
+    {
+        RELEASE_ASSERT(!!size());
+        return at(size() - 1);
+    }
     
     // Use this to find both the index of the terminal and the terminal itself in one go. May
     // return a clear NodeAndIndex if the basic block currently lacks a terminal. That may happen
index 0eb0c60..95866a7 100644 (file)
 
 namespace JSC { namespace DFG {
 
-NodeSet liveNodesAtHead(Graph& graph, BasicBlock* block)
+static void addBytecodeLiveness(Graph& graph, AvailabilityMap& availabilityMap, NodeSet& seen, Node* node)
 {
-    NodeSet seen;
-    for (NodeFlowProjection node : block->ssa->liveAtHead) {
-        if (node.kind() == NodeFlowProjection::Primary)
-            seen.addVoid(node.node());
-    }
-    
-    AvailabilityMap& availabilityMap = block->ssa->availabilityAtHead;
     graph.forAllLiveInBytecode(
-        block->at(0)->origin.forExit,
+        node->origin.forExit,
         [&] (VirtualRegister reg) {
             availabilityMap.closeStartingWithLocal(
                 reg,
@@ -56,7 +49,17 @@ NodeSet liveNodesAtHead(Graph& graph, BasicBlock* block)
                     return seen.add(node).isNewEntry;
                 });
         });
-    
+}
+
+NodeSet liveNodesAtHead(Graph& graph, BasicBlock* block)
+{
+    NodeSet seen;
+    for (NodeFlowProjection node : block->ssa->liveAtHead) {
+        if (node.kind() == NodeFlowProjection::Primary)
+            seen.addVoid(node.node());
+    }
+
+    addBytecodeLiveness(graph, block->ssa->availabilityAtHead, seen, block->at(0));
     return seen;
 }
 
@@ -64,9 +67,27 @@ CombinedLiveness::CombinedLiveness(Graph& graph)
     : liveAtHead(graph)
     , liveAtTail(graph)
 {
-    // First compute the liveAtHead for each block.
-    for (BasicBlock* block : graph.blocksInNaturalOrder())
+    // First compute 
+    // - The liveAtHead for each block.
+    // - The liveAtTail for blocks that won't properly propagate
+    //   the information based on their empty successor list.
+    for (BasicBlock* block : graph.blocksInNaturalOrder()) {
         liveAtHead[block] = liveNodesAtHead(graph, block);
+
+        // If we don't have successors, we can't rely on the propagation below. This doesn't usually
+        // do anything for terminal blocks, since the last node is usually a return, so nothing is live
+        // after it. However, we may also have the end of the basic block be:
+        //
+        // ForceOSRExit
+        // Unreachable
+        //
+        // And things may definitely be live in bytecode at that point in the program.
+        if (!block->numSuccessors()) {
+            NodeSet seen;
+            addBytecodeLiveness(graph, block->ssa->availabilityAtTail, seen, block->last());
+            liveAtTail[block] = seen;
+        }
+    }
     
     // Now compute the liveAtTail by unifying the liveAtHead of the successors.
     for (BasicBlock* block : graph.blocksInNaturalOrder()) {
index e1ac76d..3b21ff9 100644 (file)
@@ -32,7 +32,7 @@
 
 namespace JSC { namespace DFG {
 
-// Returns the set of nodes live at tail, both due to due DFG and due to bytecode (i.e. OSR exit).
+// Returns the set of nodes live at head, both due to DFG and due to bytecode (i.e. OSR exit).
 NodeSet liveNodesAtHead(Graph&, BasicBlock*);
 
 // WARNING: This currently does not reason about the liveness of shadow values. The execution