DFG::PutStackSinkingPhase should eliminate GetStacks that have an obviously known...
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 16 Mar 2015 17:39:07 +0000 (17:39 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 16 Mar 2015 17:39:07 +0000 (17:39 +0000)
https://bugs.webkit.org/show_bug.cgi?id=141624

Reviewed by Geoffrey Garen.

Not eliminating GetStacks was an obvious omission from the original PutStackSinkingPhase.
Previously, we would treat GetStacks conservatively and assume that the stack slot
escaped. That's pretty dumb, since a GetStack is a local load of the stack. This change
makes GetStack a no-op from the standpoint of this phase's deferral analysis. At the end
we either keep the GetStack (if there was no concrete deferral) or we replace it with an
identity over the value that would have been stored by the deferred PutStack. Note that
this might be a Phi that the phase creates, so this is strictly stronger than what GCSE
could do.

But this change revealed the fact that this phase never correctly handled side effects in
case that we had done a GetStack, then a side-effect, and then found ourselves wanting the
value on the stack due to (for example) a Phi on a deferred PutStack and that GetStack.
Basically, it's only correct to use the SSA converter's incoming value mapping if we have
a concrete deferral - since anything but a concrete deferral may imply that the value has
been clobbered.

This has no performance change. I believe that the bug was previously benign because we
have so few operations that clobber the stack anymore, and most of those get used in a
very idiomatic way. The GetStack elimination will be very useful for the varargs
simplification that is part of bug 141174.

This includes a test for the case that Speedometer hit, plus tests for the other cases I
thought of once I realized the deeper issue.

* dfg/DFGPutStackSinkingPhase.cpp:
* tests/stress/get-stack-identity-due-to-sinking.js: Added.
(foo):
(bar):
* tests/stress/get-stack-mapping-with-dead-get-stack.js: Added.
(bar):
(foo):
* tests/stress/get-stack-mapping.js: Added.
(bar):
(foo):
* tests/stress/weird-put-stack-varargs.js: Added.
(baz):
(foo):
(fuzz):
(bar):

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

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/dfg/DFGPutStackSinkingPhase.cpp
Source/JavaScriptCore/tests/stress/get-stack-identity-due-to-sinking.js [new file with mode: 0644]
Source/JavaScriptCore/tests/stress/get-stack-mapping-with-dead-get-stack.js [new file with mode: 0644]
Source/JavaScriptCore/tests/stress/get-stack-mapping.js [new file with mode: 0644]
Source/JavaScriptCore/tests/stress/weird-put-stack-varargs.js [new file with mode: 0644]

index a32446a..41016b9 100644 (file)
@@ -1,3 +1,50 @@
+2015-03-15  Filip Pizlo  <fpizlo@apple.com>
+
+        DFG::PutStackSinkingPhase should eliminate GetStacks that have an obviously known source, and emit GetStacks when the stack's value is needed and none is deferred
+        https://bugs.webkit.org/show_bug.cgi?id=141624
+
+        Reviewed by Geoffrey Garen.
+
+        Not eliminating GetStacks was an obvious omission from the original PutStackSinkingPhase.
+        Previously, we would treat GetStacks conservatively and assume that the stack slot
+        escaped. That's pretty dumb, since a GetStack is a local load of the stack. This change
+        makes GetStack a no-op from the standpoint of this phase's deferral analysis. At the end
+        we either keep the GetStack (if there was no concrete deferral) or we replace it with an
+        identity over the value that would have been stored by the deferred PutStack. Note that
+        this might be a Phi that the phase creates, so this is strictly stronger than what GCSE
+        could do.
+        
+        But this change revealed the fact that this phase never correctly handled side effects in
+        case that we had done a GetStack, then a side-effect, and then found ourselves wanting the
+        value on the stack due to (for example) a Phi on a deferred PutStack and that GetStack.
+        Basically, it's only correct to use the SSA converter's incoming value mapping if we have
+        a concrete deferral - since anything but a concrete deferral may imply that the value has
+        been clobbered.
+        
+        This has no performance change. I believe that the bug was previously benign because we
+        have so few operations that clobber the stack anymore, and most of those get used in a
+        very idiomatic way. The GetStack elimination will be very useful for the varargs
+        simplification that is part of bug 141174.
+        
+        This includes a test for the case that Speedometer hit, plus tests for the other cases I
+        thought of once I realized the deeper issue.
+
+        * dfg/DFGPutStackSinkingPhase.cpp:
+        * tests/stress/get-stack-identity-due-to-sinking.js: Added.
+        (foo):
+        (bar):
+        * tests/stress/get-stack-mapping-with-dead-get-stack.js: Added.
+        (bar):
+        (foo):
+        * tests/stress/get-stack-mapping.js: Added.
+        (bar):
+        (foo):
+        * tests/stress/weird-put-stack-varargs.js: Added.
+        (baz):
+        (foo):
+        (fuzz):
+        (bar):
+
 2015-03-16  Joseph Pecoraro  <pecoraro@apple.com>
 
         Update Map/Set to treat -0 and 0 as the same value
index 9c5d7e6..8285674 100644 (file)
@@ -221,6 +221,12 @@ public:
                         continue;
                     }
                     
+                    if (node->op() == GetStack) {
+                        // A GetStack doesn't affect anything, since we know which local we are reading
+                        // from.
+                        continue;
+                    }
+                    
                     auto escapeHandler = [&] (VirtualRegister operand) {
                         if (operand.isHeader())
                             return;
@@ -390,6 +396,29 @@ public:
                     deferred.operand(node->unlinkedLocal()) = ConflictingFlush;
                     break;
                 }
+                    
+                case GetStack: {
+                    StackAccessData* data = node->stackAccessData();
+                    FlushFormat format = deferred.operand(data->local);
+                    if (!isConcrete(format)) {
+                        // This means there is no deferral. No deferral means that the most
+                        // authoritative value for this stack slot is what is stored in the stack. So,
+                        // keep the GetStack.
+                        mapping.operand(data->local) = node;
+                        break;
+                    }
+                    
+                    // We have a concrete deferral, which means a PutStack that hasn't executed yet. It
+                    // would have stored a value with a certain format. That format must match our
+                    // format. But more importantly, we can simply use the value that the PutStack would
+                    // have stored and get rid of the GetStack.
+                    DFG_ASSERT(m_graph, node, format == data->format);
+                    
+                    Node* incoming = mapping.operand(data->local);
+                    node->child1() = incoming->defaultEdge();
+                    node->convertToIdentity();
+                    break;
+                }
                 
                 default: {
                     auto escapeHandler = [&] (VirtualRegister operand) {
@@ -418,16 +447,6 @@ public:
                     preciseLocalClobberize(
                         m_graph, node, escapeHandler, escapeHandler,
                         [&] (VirtualRegister, Node*) { });
-                    
-                    // If we're a GetStack, then we also create a mapping.
-                    // FIXME: We should be able to just eliminate such GetLocals, when we know
-                    // what their incoming value will be.
-                    // https://bugs.webkit.org/show_bug.cgi?id=141624
-                    if (node->op() == GetStack) {
-                        StackAccessData* data = node->stackAccessData();
-                        VirtualRegister operand = data->local;
-                        mapping.operand(operand) = node;
-                    }
                     break;
                 } }
             }
@@ -444,34 +463,24 @@ public:
                     FlushFormat format = deferredAtHead[successorBlock].operand(operand);
                     DFG_ASSERT(m_graph, nullptr, isConcrete(format));
                     UseKind useKind = useKindFor(format);
-                    Node* incoming = mapping.operand(operand);
-                    if (!incoming) {
-                        // This can totally happen, see tests/stress/put-local-conservative.js.
-                        // This arises because deferral and liveness are both conservative.
-                        // Conservative liveness means that a load from a *different* closure
-                        // variable may lead us to believe that our local is live. Conservative
-                        // deferral may lead us to believe that the local doesn't have a top deferral
-                        // because someone has done something that would have forced it to be
-                        // materialized. The basic pattern is:
-                        //
-                        // GetClosureVar(loc42) // loc42's deferral is now bottom
-                        // if (predicate1)
-                        //     PutClosureVar(loc42) // prevent GCSE of our GetClosureVar's
-                        // if (predicate2)
-                        //     PutStack(loc42) // we now have a concrete deferral
-                        // // we still have the concrete deferral because we merged with bottom
-                        // GetClosureVar(loc42) // force materialization
-                        //
-                        // We will have a Phi with no incoming value form the basic block that
-                        // bypassed the PutStack.
-                        
-                        // Note: we sort of could have used the equivalent of LLVM's undef here. The
-                        // point is that it's OK to just leave random bits in the local if we're
-                        // coming down this path. But, we don't have a way of saying that in our IR
-                        // right now and anyway it probably doesn't matter that much.
-                        
-                        incoming = insertionSet.insertBottomConstantForUse(
-                            upsilonInsertionPoint, upsilonOrigin, useKind).node();
+                    
+                    // We need to get a value for the stack slot. This phase doesn't really have a
+                    // good way of determining if a stack location got clobbered. It just knows if
+                    // there is a deferral. The lack of a deferral might mean that a PutStack or
+                    // GetStack had never happened, or it might mean that the value was read, or
+                    // that it was written. It's OK for us to make some bad decisions here, since
+                    // GCSE will clean it up anyway.
+                    Node* incoming;
+                    if (isConcrete(deferred.operand(operand))) {
+                        incoming = mapping.operand(operand);
+                        DFG_ASSERT(m_graph, phiNode, incoming);
+                    } else {
+                        // Issue a GetStack to get the value. This might introduce some redundancy
+                        // into the code, but if it's bad enough, GCSE will clean it up.
+                        incoming = insertionSet.insertNode(
+                            upsilonInsertionPoint, SpecNone, GetStack, upsilonOrigin,
+                            OpInfo(m_graph.m_stackAccessData.add(operand, format)));
+                        incoming->setResult(resultFor(format));
                     }
                     
                     insertionSet.insertNode(
diff --git a/Source/JavaScriptCore/tests/stress/get-stack-identity-due-to-sinking.js b/Source/JavaScriptCore/tests/stress/get-stack-identity-due-to-sinking.js
new file mode 100644 (file)
index 0000000..7f74135
--- /dev/null
@@ -0,0 +1,18 @@
+function foo(p, a) {
+    if (p) {
+        var tmp = arguments;
+    }
+    return a;
+}
+
+function bar(p, a) {
+    return foo(p, a);
+}
+
+noInline(bar);
+
+for (var i = 0; i < 10000; ++i) {
+    var result = bar(false, 42);
+    if (result != 42)
+        throw "Error: bad result: " + result;
+}
diff --git a/Source/JavaScriptCore/tests/stress/get-stack-mapping-with-dead-get-stack.js b/Source/JavaScriptCore/tests/stress/get-stack-mapping-with-dead-get-stack.js
new file mode 100644 (file)
index 0000000..e158ccb
--- /dev/null
@@ -0,0 +1,27 @@
+function bar() {
+    if (foo.arguments[0] === void 0)
+        throw "Error: foo.arguments[0] should not be undefined but is."
+}
+
+noInline(bar);
+
+function foo(a, p) {
+    var tmp = a;
+    effectful42();
+    for (var i = 0; i < 10; ++i) {
+        bar();
+        a = i;
+    }
+    if (p) {
+        var tmp = arguments;
+    }
+    return a;
+}
+
+noInline(foo);
+
+for (var i = 0; i < 10000; ++i) {
+    var result = foo(0, false);
+    if (result != 9)
+        throw "Error: bad result: " + result;
+}
diff --git a/Source/JavaScriptCore/tests/stress/get-stack-mapping.js b/Source/JavaScriptCore/tests/stress/get-stack-mapping.js
new file mode 100644 (file)
index 0000000..c62f0de
--- /dev/null
@@ -0,0 +1,26 @@
+function bar() {
+    if (foo.arguments[0] === void 0)
+        throw "Error: foo.arguments[0] should not be undefined but is."
+}
+
+noInline(bar);
+
+function foo(a, p) {
+    effectful42();
+    for (var i = 0; i < 10; ++i) {
+        bar();
+        a = i;
+    }
+    if (p) {
+        var tmp = arguments;
+    }
+    return a;
+}
+
+noInline(foo);
+
+for (var i = 0; i < 10000; ++i) {
+    var result = foo(0, false);
+    if (result != 9)
+        throw "Error: bad result: " + result;
+}
diff --git a/Source/JavaScriptCore/tests/stress/weird-put-stack-varargs.js b/Source/JavaScriptCore/tests/stress/weird-put-stack-varargs.js
new file mode 100644 (file)
index 0000000..ffa9ab1
--- /dev/null
@@ -0,0 +1,26 @@
+function baz() {
+    if (!foo.arguments[1])
+        throw "Error: foo.arguments[1] should be truthy but is falsy: " + foo.arguments[1];
+}
+
+noInline(baz);
+
+function foo(a, b) {
+    if (a)
+        b = 42;
+    baz();
+}
+
+function fuzz(a, b) {
+    return a + b;
+}
+
+function bar(array1, array2) {
+    fuzz.apply(this, array1);
+    foo.apply(this, array2);
+}
+
+noInline(bar);
+
+for (var i = 0; i < 100000; ++i)
+    bar([false, false], [false, true]);