Changeset 189126 in webkit for trunk/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp

Timestamp:

Aug 28, 2015, 3:38:41 PM (10 years ago)

Author:

[email protected]

Message:

LICM should be sound even if the CFG has changed
​https://bugs.webkit.org/show_bug.cgi?id=148259

Reviewed by Benjamin Poulain.

Source/JavaScriptCore:

Prior to this change, LICM expected a certain CFG shape around a loop: broken critical edges,
a pre-header, and the pre-header's terminal has exitOK. LICM would either crash on an
assertion, or generate code that fails validation, if these conditions weren't met.

The broken critical edge assumption is fine; so far we are assuming that SSA means broken
critical edges. We may revisit this, but we don't have to right now.

The other assumptions are not fine, because it's hard to guarantee that every phase will
preserve the presence of pre-headers. Even if we required that pre-headers are regenerated
before LICM, that regeneration wouldn't be guaranteed to create pre-headers that have exitOK at
the terminal. That's because once in SSA, the loop header probably has exitOK=false at the
head because of Phi's. Pre-header creation has no choice but to use the Node::origin from the
loop header, which means creating a pre-header that has exitOK=false. Regardless of whether
that's a fixable problem, it seems that our best short-term approach is just to be defensive
and turn undesirable pathologies into performance bugs and not crashes.

For the foreseeable future, once pre-headers are created they will probably not be removed. Our
current CFG simplification phase doesn't have a rule for removing pre-headers (since it doesn't
have any jump threading). So, it wouldn't be profitable to put effort towards reneration of
pre-headers for LICM's benefit.

Also, we cannot guarantee that some sequence of CFG transformations will not create a loop that
doesn't have a pre-header. This would be super rare. But you could imagine that some program
has control flow encoded using relooping (like
​https://github.com/kripken/Relooper/blob/master/paper.pdf). If that happens, our compiler will
probably incrementally discover the "original" CFG. That may happen only after SSA conversion,
and so after pre-header generation. This is super unlikely for a bunch of reasons, but it
*could* happen.

So, this patch just makes sure that if pre-headers are missing or cannot be exited from, LICM
will simply avoid hoisting out of that block. At some point later, we can worry about a more
comprehensive solution to the pre-header problem. That's covered by this bug:
​https://bugs.webkit.org/show_bug.cgi?id=148586

• dfg/DFGLICMPhase.cpp:

(JSC::DFG::LICMPhase::run):
(JSC::DFG::LICMPhase::attemptHoist):

• dfg/DFGPlan.cpp:

(JSC::DFG::Plan::compileInThreadImpl):

• runtime/Options.h:
• tests/stress/licm-no-pre-header.js: Added.

(foo):

• tests/stress/licm-pre-header-cannot-exit.js: Added.

(foo):

Tools:

Add a utility for creating tests that set some uncommon option.

• Scripts/run-jsc-stress-tests:

File:

• trunk/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp (modified) (5 diffs)

trunk/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp

@@ -47 +47 @@
 struct LoopData {
     LoopData()
-        : preHeader(0)
+        : preHeader(nullptr)
     {
     }
@@ -113 +113 @@
             const NaturalLoop& loop = m_graph.m_naturalLoops.loop(loopIndex);
             LoopData& data = m_data[loop.index()];
+            
             for (
                 const NaturalLoop* outerLoop = m_graph.m_naturalLoops.innerMostOuterLoop(loop);
@@ -120 +121 @@
             
             BasicBlock* header = loop.header();
-            BasicBlock* preHeader = 0;
+            BasicBlock* preHeader = nullptr;
+            unsigned numberOfPreHeaders = 0; // We're cool if this is 1.
+
+            // This is guaranteed because we expect the CFG not to have unreachable code. Therefore, a
+            // loop header must have a predecessor. (Also, we don't allow the root block to be a loop,
+            // which cuts out the one other way of having a loop header with only one predecessor.)
+            DFG_ASSERT(m_graph, header->at(0), header->predecessors.size() > 1);
+            
             for (unsigned i = header->predecessors.size(); i--;) {
                 BasicBlock* predecessor = header->predecessors[i];
                 if (m_graph.m_dominators.dominates(header, predecessor))
                     continue;
-                DFG_ASSERT(m_graph, nullptr, !preHeader || preHeader == predecessor);
+
                 preHeader = predecessor;
-            }
-            
+                ++numberOfPreHeaders;
+            }
+
+            // We need to validate the pre-header. There are a bunch of things that could be wrong
+            // about it:
+            //
+            // - There might be more than one. This means that pre-header creation either did not run,
+            //   or some CFG transformation destroyed the pre-headers.
+            //
+            // - It may not be legal to exit at the pre-header. That would be a real bummer. Currently,
+            //   LICM assumes that it can always hoist checks. See
+            //   https://bugs.webkit.org/show_bug.cgi?id=148545. Though even with that fixed, we anyway
+            //   would need to check if it's OK to exit at the pre-header since if we can't then we
+            //   would have to restrict hoisting to non-exiting nodes.
+
+            if (numberOfPreHeaders != 1)
+                continue;
+
+            // This is guaranteed because the header has multiple predecessors and critical edges are
+            // broken. Therefore the predecessors must all have one successor, which implies that they
+            // must end in a Jump.
             DFG_ASSERT(m_graph, preHeader->terminal(), preHeader->terminal()->op() == Jump);
-            
-            // We should validate the pre-header. This currently assumes that it's valid to OSR exit at
-            // the Jump of the pre-header. That may not always be the case, like if we lowered a Node
-            // that was ExitInvalid to a loop. This phase should somehow defend against this - at the
-            // very least with assertions, if not with something better (like only hoisting things that
-            // cannot exit).
-            // FIXME: https://bugs.webkit.org/show_bug.cgi?id=148259
+
+            if (!preHeader->terminal()->origin.exitOK)
+                continue;
             
             data.preHeader = preHeader;
@@ -147 +170 @@
         // - The node doesn't write anything.
         // - The node doesn't read anything that the loop writes.
+        // - The preHeader is valid (i.e. it passed the validation above).
         // - The preHeader's state at tail makes the node safe to execute.
         // - The loop's children all belong to nodes that strictly dominate the loop header.
@@ -206 +230 @@
         Node* node = nodeRef;
         LoopData& data = m_data[loop->index()];
+
+        if (!data.preHeader) {
+            if (verbose)
+                dataLog("    Not hoisting ", node, " because the pre-header is invalid.\n");
+            return false;
+        }
         
         if (!data.preHeader->cfaDidFinish) {