The CleanUp after LICM is erroneously removing a Check
authorsbarati@apple.com <sbarati@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 15 Dec 2017 06:20:07 +0000 (06:20 +0000)
committersbarati@apple.com <sbarati@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 15 Dec 2017 06:20:07 +0000 (06:20 +0000)
https://bugs.webkit.org/show_bug.cgi?id=180852
<rdar://problem/36063494>

Reviewed by Filip Pizlo.

JSTests:

* stress/dont-run-cleanup-after-licm.js: Added.

Source/JavaScriptCore:

There was a bug where CleanUp phase relied on isProved() bits and LICM
changed them in an invalid way. The bug is as follows:

We have two loops, L1 and L2, and two preheaders, P1 and P2. L2 is nested
inside of L1. We have a Check inside a node inside L1, say in basic block BB,
and that Check dominates all of L2. This is also a hoisting candidate, so we
hoist it outside of L1 and put it inside P1. Then, when we run AI, we look at
the preheader for each loop inside L1, so P1 and P2. When considering P2,
we execute the Check. Inside P2, before any hoisting is done, this Check
is dead code, because BB dominates P2. When we use AI to "execute" the
Check, it'll set its proof status to proved. This is because inside P2,
in the program before LICM runs, the Check is indeed proven at P2. But
it is not proven inside P1. This "execute" call will set our proof status
for the node inside *P1*, hence, we crash.

The fix here is to make LICM precise when updating the ProofStatus of an edge.
It can trust the AI state at the preheader it hoists the node to, but it can't
trust the state when executing effects inside inner loops's preheaders.

* dfg/DFGPlan.cpp:
(JSC::DFG::Plan::compileInThreadImpl):

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

JSTests/ChangeLog
JSTests/stress/dont-run-cleanup-after-licm.js [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/dfg/DFGAbstractInterpreter.h
Source/JavaScriptCore/dfg/DFGAtTailAbstractState.h
Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.h
Source/JavaScriptCore/dfg/DFGLICMPhase.cpp

index 69cdae0f2da5f7fd499a9039079a75f6e7a29947..1b00a9906ba71565a3d0918919cc24f252a2126e 100644 (file)
@@ -1,3 +1,13 @@
+2017-12-14  Saam Barati  <sbarati@apple.com>
+
+        The CleanUp after LICM is erroneously removing a Check
+        https://bugs.webkit.org/show_bug.cgi?id=180852
+        <rdar://problem/36063494>
+
+        Reviewed by Filip Pizlo.
+
+        * stress/dont-run-cleanup-after-licm.js: Added.
+
 2017-12-14  Michael Saboff  <msaboff@apple.com>
 
         REGRESSION (r225695): Repro crash on yahoo login page
diff --git a/JSTests/stress/dont-run-cleanup-after-licm.js b/JSTests/stress/dont-run-cleanup-after-licm.js
new file mode 100644 (file)
index 0000000..d03849e
--- /dev/null
@@ -0,0 +1,14 @@
+function foo(string) {
+    var result1, result2;
+    for (var i = 0; i < 1000; ++i) {
+        result1 = string[0]; 
+        for (var j = 0; j < 10; ++j)
+            result2 = 1;
+    }
+   return [result1, result2];
+}
+noInline(foo);
+
+foo(" ");
+for (var i = 0; i < 1000; i++)
+    foo(new Error());
index 81d730fa73ba48fe9d9e518a82944acecb9fcc41..962b6abf0d0fecc47585961aa608cab4ed90b438 100644 (file)
@@ -1,3 +1,33 @@
+2017-12-14  Saam Barati  <sbarati@apple.com>
+
+        The CleanUp after LICM is erroneously removing a Check
+        https://bugs.webkit.org/show_bug.cgi?id=180852
+        <rdar://problem/36063494>
+
+        Reviewed by Filip Pizlo.
+
+        There was a bug where CleanUp phase relied on isProved() bits and LICM
+        changed them in an invalid way. The bug is as follows:
+        
+        We have two loops, L1 and L2, and two preheaders, P1 and P2. L2 is nested
+        inside of L1. We have a Check inside a node inside L1, say in basic block BB,
+        and that Check dominates all of L2. This is also a hoisting candidate, so we
+        hoist it outside of L1 and put it inside P1. Then, when we run AI, we look at
+        the preheader for each loop inside L1, so P1 and P2. When considering P2,
+        we execute the Check. Inside P2, before any hoisting is done, this Check
+        is dead code, because BB dominates P2. When we use AI to "execute" the
+        Check, it'll set its proof status to proved. This is because inside P2,
+        in the program before LICM runs, the Check is indeed proven at P2. But
+        it is not proven inside P1. This "execute" call will set our proof status
+        for the node inside *P1*, hence, we crash.
+        
+        The fix here is to make LICM precise when updating the ProofStatus of an edge.
+        It can trust the AI state at the preheader it hoists the node to, but it can't
+        trust the state when executing effects inside inner loops's preheaders.
+
+        * dfg/DFGPlan.cpp:
+        (JSC::DFG::Plan::compileInThreadImpl):
+
 2017-12-14  David Kilzer  <ddkilzer@apple.com>
 
         Enable -Wstrict-prototypes for WebKit
index e212ae98188038e6c01925d870753f953c33088c..1411825632a66c26b35f1634c0c48d953304a91a 100644 (file)
@@ -182,11 +182,7 @@ private:
     ALWAYS_INLINE void filterByType(Edge& edge, SpeculatedType type)
     {
         AbstractValue& value = forNode(edge);
-        if (!value.isType(type))
-            edge.setProofStatus(NeedsCheck);
-        else
-            edge.setProofStatus(IsProved);
-        
+        m_state.setProofStatus(edge, value.isType(type) ? IsProved : NeedsCheck);
         filter(value, type);
     }
     
index 8f043b72bd1cdc74819b2e2cae886bc0380435f3..f1bf56899ecfeb4e0ac232dd53c90bc90f0f4db2 100644 (file)
@@ -65,10 +65,19 @@ public:
     void setBranchDirection(BranchDirection) { }
     void setFoundConstants(bool) { }
 
+    void trustEdgeProofs() { m_trustEdgeProofs = true; }
+    void dontTrustEdgeProofs() { m_trustEdgeProofs = false; }
+    void setProofStatus(Edge& edge, ProofStatus status)
+    {
+        if (m_trustEdgeProofs)
+            edge.setProofStatus(status);
+    }
+
 private:
     Graph& m_graph;
     BlockMap<HashMap<NodeFlowProjection, AbstractValue>> m_valuesAtTailMap;
     BasicBlock* m_block { nullptr };
+    bool m_trustEdgeProofs { false };
 };
 
 } } // namespace JSC::DFG
index 9f94cfee81285e08a449f44b53ecb6d79dde1205..a97c3151580ad8ef00778e19f9609a052e5af5d9 100644 (file)
@@ -126,6 +126,11 @@ public:
     // So, we should probably keep this method.
     void setFoundConstants(bool foundConstants) { m_foundConstants = foundConstants; }
 
+    void setProofStatus(Edge& edge, ProofStatus status)
+    {
+        edge.setProofStatus(status);
+    }
+
 private:
     void mergeStateAtTail(AbstractValue& destination, AbstractValue& inVariable, Node*);
 
index a28127fff0ab07e9c31594a442fefc04b1a0feb8..ef7d6475e8d883db1a9bd35ed4f3aedddebf3c96 100644 (file)
@@ -220,7 +220,7 @@ public:
                     changed |= attemptHoist(block, nodeRef, loopStack[stackIndex]);
             }
         }
-        
+
         return changed;
     }
 
@@ -297,15 +297,28 @@ private:
                 "\n");
         }
 
-        // FIXME: We should adjust the Check: flags on the edges of node. There are phases that assume
-        // that those flags are correct even if AI is stale.
-        // https://bugs.webkit.org/show_bug.cgi?id=148544
         data.preHeader->insertBeforeTerminal(node);
         node->owner = data.preHeader;
         NodeOrigin terminalOrigin = data.preHeader->terminal()->origin;
         node->origin = terminalOrigin.withSemantic(node->origin.semantic);
         node->origin.wasHoisted |= addsBlindSpeculation;
         
+        // We can trust what AI proves about edge proof statuses when hoisting to the preheader.
+        m_state.trustEdgeProofs();
+        m_state.initializeTo(data.preHeader);
+        m_interpreter.execute(node);
+        // 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.
@@ -323,10 +336,13 @@ private:
             // 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);
             m_interpreter.execute(node);
         }
-        
+
         // It just so happens that all of the nodes we currently know how to hoist
         // don't have var-arg children. That may change and then we can fix this
         // code. But for now we just assert that's the case.