Changeset 244579 in webkit

Timestamp:

Apr 23, 2019, 7:14:23 PM (7 years ago)

Author:

sbarati@apple.com

Message:

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.

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):

Location:

trunk

Files:

• JSTests/ChangeLog (modified) (1 diff)
• JSTests/stress/licm-should-handle-if-a-hoist-causes-a-provable-osr-exit.js (added)
• Source/JavaScriptCore/ChangeLog (modified) (1 diff)
• Source/JavaScriptCore/dfg/DFGLICMPhase.cpp (modified) (3 diffs)

trunk/JSTests/ChangeLog

@@ +1 @@
+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>
 

trunk/Source/JavaScriptCore/ChangeLog

@@ +1 @@
+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>
 

trunk/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp

@@ -243 +243 @@
         
         m_state.initializeTo(data.preHeader);
+        ASSERT(m_state.isValid());
         NodeOrigin originalOrigin = node->origin;
         bool canSpeculateBlindly = !m_graph.hasGlobalExitSite(originalOrigin.semantic, HoistingFailed);
@@ -264 +265 @@
 
         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
@@ -301 +319 @@
                     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;
+                    }
+                }
             }
         };