- Revision
- 239882
- Author
- [email protected]
- Date
- 2019-01-11 16:26:06 -0800 (Fri, 11 Jan 2019)
Log Message
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.
JSTests:
* stress/dfg-combined-liveness-consider-terminal-blocks-bytecode-liveness.js: Added.
Source/_javascript_Core:
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:
Modified Paths
Added Paths
Diff
Modified: trunk/JSTests/ChangeLog (239881 => 239882)
--- trunk/JSTests/ChangeLog 2019-01-12 00:21:49 UTC (rev 239881)
+++ trunk/JSTests/ChangeLog 2019-01-12 00:26:06 UTC (rev 239882)
@@ -1,3 +1,13 @@
+2019-01-11 Saam barati <[email protected]>
+
+ 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 <[email protected]>
[JSC] Global lexical bindings can shadow global variables if it is `configurable = true`
Added: trunk/JSTests/stress/dfg-combined-liveness-consider-terminal-blocks-bytecode-liveness.js (0 => 239882)
--- trunk/JSTests/stress/dfg-combined-liveness-consider-terminal-blocks-bytecode-liveness.js (rev 0)
+++ trunk/JSTests/stress/dfg-combined-liveness-consider-terminal-blocks-bytecode-liveness.js 2019-01-12 00:26:06 UTC (rev 239882)
@@ -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();
Modified: trunk/Source/_javascript_Core/ChangeLog (239881 => 239882)
--- trunk/Source/_javascript_Core/ChangeLog 2019-01-12 00:21:49 UTC (rev 239881)
+++ trunk/Source/_javascript_Core/ChangeLog 2019-01-12 00:26:06 UTC (rev 239882)
@@ -1,3 +1,37 @@
+2019-01-11 Saam barati <[email protected]>
+
+ 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 <[email protected]>
[JSC] Global lexical bindings can shadow global variables if it is `configurable = true`
Modified: trunk/Source/_javascript_Core/dfg/DFGBasicBlock.h (239881 => 239882)
--- trunk/Source/_javascript_Core/dfg/DFGBasicBlock.h 2019-01-12 00:21:49 UTC (rev 239881)
+++ trunk/Source/_javascript_Core/dfg/DFGBasicBlock.h 2019-01-12 00:26:06 UTC (rev 239882)
@@ -64,6 +64,11 @@
}
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
Modified: trunk/Source/_javascript_Core/dfg/DFGCombinedLiveness.cpp (239881 => 239882)
--- trunk/Source/_javascript_Core/dfg/DFGCombinedLiveness.cpp 2019-01-12 00:21:49 UTC (rev 239881)
+++ trunk/Source/_javascript_Core/dfg/DFGCombinedLiveness.cpp 2019-01-12 00:26:06 UTC (rev 239882)
@@ -35,17 +35,10 @@
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 @@
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 @@
: 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()) {
Modified: trunk/Source/_javascript_Core/dfg/DFGCombinedLiveness.h (239881 => 239882)
--- trunk/Source/_javascript_Core/dfg/DFGCombinedLiveness.h 2019-01-12 00:21:49 UTC (rev 239881)
+++ trunk/Source/_javascript_Core/dfg/DFGCombinedLiveness.h 2019-01-12 00:26:06 UTC (rev 239882)
@@ -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
