LICM incorrectly assumes it'll never insert a node which provably OSR exits
authorsbarati@apple.com <sbarati@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 24 Apr 2019 02:14:23 +0000 (02:14 +0000)
committersbarati@apple.com <sbarati@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 24 Apr 2019 02:14:23 +0000 (02:14 +0000)
https://bugs.webkit.org/show_bug.cgi?id=196721
<rdar://problem/49556479>

Reviewed by Filip Pizlo.

JSTests:

* stress/licm-should-handle-if-a-hoist-causes-a-provable-osr-exit.js: Added.
(foo):

Source/JavaScriptCore:

Previously, we assumed LICM could never hoist code that caused us
to provably OSR exit. This is a bad assumption, as we may very well
hoist such code. Obviously hoisting such code is not ideal. We shouldn't
hoist something we provably know will OSR exit. However, this is super rare,
and the phase is written in such a way where it's easier to gracefully
handle this case than to prevent us from hoisting such code.

If we wanted to ensure we never hoisted code that would provably exit, we'd
have to teach the phase to know when it inserted code that provably exits. I
saw two ways to do that:
1: Save and restore the AI state before actually hoisting.
2: Write an analysis that can determine if such a node would exit.

(1) is bad because it costs in memory and compile time. (2) will inevitably
have bugs as running into this condition is rare.

So instead of (1) or (2), I opted to have LICM gracefully handle when
it causes a provable exit. When we encounter this, we mark all blocks
in the loop as !cfaHasVisited and !cfaDidFinish.

* dfg/DFGLICMPhase.cpp:
(JSC::DFG::LICMPhase::attemptHoist):

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

JSTests/ChangeLog
JSTests/stress/licm-should-handle-if-a-hoist-causes-a-provable-osr-exit.js [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/dfg/DFGLICMPhase.cpp

index c3da161..315ecee 100644 (file)
@@ -1,3 +1,14 @@
+2019-04-23  Saam Barati  <sbarati@apple.com>
+
+        LICM incorrectly assumes it'll never insert a node which provably OSR exits
+        https://bugs.webkit.org/show_bug.cgi?id=196721
+        <rdar://problem/49556479> 
+
+        Reviewed by Filip Pizlo.
+
+        * stress/licm-should-handle-if-a-hoist-causes-a-provable-osr-exit.js: Added.
+        (foo):
+
 2019-04-19  Saam Barati  <sbarati@apple.com>
 
         AbstractValue can represent more than int52
diff --git a/JSTests/stress/licm-should-handle-if-a-hoist-causes-a-provable-osr-exit.js b/JSTests/stress/licm-should-handle-if-a-hoist-causes-a-provable-osr-exit.js
new file mode 100644 (file)
index 0000000..f9d89a5
--- /dev/null
@@ -0,0 +1,14 @@
+const a = [0];
+
+function foo() {
+    for (const x1 of a) {
+        for (const x2 of a) {
+            with (0) {
+                Object;
+            }
+        }
+    }
+    for (let i = 0; i < 100; i++) {
+    }
+}
+foo();
index ead5105..e241ed4 100644 (file)
@@ -1,3 +1,34 @@
+2019-04-23  Saam Barati  <sbarati@apple.com>
+
+        LICM incorrectly assumes it'll never insert a node which provably OSR exits
+        https://bugs.webkit.org/show_bug.cgi?id=196721
+        <rdar://problem/49556479> 
+
+        Reviewed by Filip Pizlo.
+
+        Previously, we assumed LICM could never hoist code that caused us
+        to provably OSR exit. This is a bad assumption, as we may very well
+        hoist such code. Obviously hoisting such code is not ideal. We shouldn't
+        hoist something we provably know will OSR exit. However, this is super rare,
+        and the phase is written in such a way where it's easier to gracefully
+        handle this case than to prevent us from hoisting such code.
+        
+        If we wanted to ensure we never hoisted code that would provably exit, we'd
+        have to teach the phase to know when it inserted code that provably exits. I
+        saw two ways to do that:
+        1: Save and restore the AI state before actually hoisting.
+        2: Write an analysis that can determine if such a node would exit.
+        
+        (1) is bad because it costs in memory and compile time. (2) will inevitably
+        have bugs as running into this condition is rare.
+        
+        So instead of (1) or (2), I opted to have LICM gracefully handle when
+        it causes a provable exit. When we encounter this, we mark all blocks
+        in the loop as !cfaHasVisited and !cfaDidFinish.
+
+        * dfg/DFGLICMPhase.cpp:
+        (JSC::DFG::LICMPhase::attemptHoist):
+
 2019-04-23  Yusuke Suzuki  <ysuzuki@apple.com>
 
         [JSC] Use node index as DFG::MinifiedID
index 72b3548..465f472 100644 (file)
@@ -242,6 +242,7 @@ private:
         }
         
         m_state.initializeTo(data.preHeader);
+        ASSERT(m_state.isValid());
         NodeOrigin originalOrigin = node->origin;
         bool canSpeculateBlindly = !m_graph.hasGlobalExitSite(originalOrigin.semantic, HoistingFailed);
 
@@ -263,10 +264,27 @@ private:
         };
 
         auto updateAbstractState = [&] {
+            auto invalidate = [&] (const NaturalLoop* loop) {
+                LoopData& data = m_data[loop->index()];
+                data.preHeader->cfaDidFinish = false;
+
+                for (unsigned bodyIndex = loop->size(); bodyIndex--;) {
+                    BasicBlock* block = loop->at(bodyIndex);
+                    if (block != data.preHeader)
+                        block->cfaHasVisited = false;
+                    block->cfaDidFinish = false;
+                }
+            };
+
             // We can trust what AI proves about edge proof statuses when hoisting to the preheader.
             m_state.trustEdgeProofs();
-            for (unsigned i = 0; i < hoistedNodes.size(); ++i)
-                m_interpreter.execute(hoistedNodes[i]);
+            for (unsigned i = 0; i < hoistedNodes.size(); ++i) {
+                if (!m_interpreter.execute(hoistedNodes[i])) {
+                    invalidate(loop);
+                    return;
+                }
+            }
+
             // 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
@@ -300,8 +318,12 @@ private:
                 if (subPreHeader == data.preHeader)
                     continue;
                 m_state.initializeTo(subPreHeader);
-                for (unsigned i = 0; i < hoistedNodes.size(); ++i)
-                    m_interpreter.execute(hoistedNodes[i]);
+                for (unsigned i = 0; i < hoistedNodes.size(); ++i) {
+                    if (!m_interpreter.execute(hoistedNodes[i])) {
+                        invalidate(subLoop);
+                        break;
+                    }
+                }
             }
         };