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 69cdae0..1b00a99 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 81d730f..962b6ab 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 e212ae9..1411825 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 8f043b7..f1bf568 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 9f94cfe..a97c315 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 a28127f..ef7d647 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.