- Revision
- 189126
- Author
- [email protected]
- Date
- 2015-08-28 15:38:41 -0700 (Fri, 28 Aug 2015)
Log 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/_javascript_Core:
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:
Modified Paths
Added Paths
Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (189125 => 189126)
--- trunk/Source/_javascript_Core/ChangeLog 2015-08-28 21:54:34 UTC (rev 189125)
+++ trunk/Source/_javascript_Core/ChangeLog 2015-08-28 22:38:41 UTC (rev 189126)
@@ -1,3 +1,55 @@
+2015-08-28 Filip Pizlo <[email protected]>
+
+ LICM should be sound even if the CFG has changed
+ https://bugs.webkit.org/show_bug.cgi?id=148259
+
+ Reviewed by Benjamin Poulain.
+
+ 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):
+
2015-08-28 Yusuke Suzuki <[email protected]>
Move std::function from JSFunction into NativeStdFunctionCell to correctly destroy the heap allocated std::function
Modified: trunk/Source/_javascript_Core/dfg/DFGCFGSimplificationPhase.cpp (189125 => 189126)
--- trunk/Source/_javascript_Core/dfg/DFGCFGSimplificationPhase.cpp 2015-08-28 21:54:34 UTC (rev 189125)
+++ trunk/Source/_javascript_Core/dfg/DFGCFGSimplificationPhase.cpp 2015-08-28 22:38:41 UTC (rev 189126)
@@ -46,6 +46,9 @@
bool run()
{
+ // FIXME: We should make this work in SSA. https://bugs.webkit.org/show_bug.cgi?id=148260
+ DFG_ASSERT(m_graph, nullptr, m_graph.m_form != SSA);
+
const bool extremeLogging = false;
bool outerChanged = false;
Modified: trunk/Source/_javascript_Core/dfg/DFGLICMPhase.cpp (189125 => 189126)
--- trunk/Source/_javascript_Core/dfg/DFGLICMPhase.cpp 2015-08-28 21:54:34 UTC (rev 189125)
+++ trunk/Source/_javascript_Core/dfg/DFGLICMPhase.cpp 2015-08-28 22:38:41 UTC (rev 189126)
@@ -46,7 +46,7 @@
struct LoopData {
LoopData()
- : preHeader(0)
+ : preHeader(nullptr)
{
}
@@ -112,6 +112,7 @@
for (unsigned loopIndex = m_graph.m_naturalLoops.numLoops(); loopIndex--;) {
const NaturalLoop& loop = m_graph.m_naturalLoops.loop(loopIndex);
LoopData& data = ""
+
for (
const NaturalLoop* outerLoop = m_graph.m_naturalLoops.innerMostOuterLoop(loop);
outerLoop;
@@ -119,24 +120,46 @@
m_data[outerLoop->index()].writes.addAll(data.writes);
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);
+
+ if (!preHeader->terminal()->origin.exitOK)
+ continue;
- // 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
-
data.preHeader = preHeader;
}
@@ -146,6 +169,7 @@
// We try to hoist to the outer-most loop that permits it. Hoisting is valid if:
// - 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.
// - The preHeader's state at tail is still valid. This is mostly to save compile
@@ -205,6 +229,12 @@
{
Node* node = nodeRef;
LoopData& data = ""
+
+ if (!data.preHeader) {
+ if (verbose)
+ dataLog(" Not hoisting ", node, " because the pre-header is invalid.\n");
+ return false;
+ }
if (!data.preHeader->cfaDidFinish) {
if (verbose)
Modified: trunk/Source/_javascript_Core/dfg/DFGLoopPreHeaderCreationPhase.cpp (189125 => 189126)
--- trunk/Source/_javascript_Core/dfg/DFGLoopPreHeaderCreationPhase.cpp 2015-08-28 21:54:34 UTC (rev 189125)
+++ trunk/Source/_javascript_Core/dfg/DFGLoopPreHeaderCreationPhase.cpp 2015-08-28 22:38:41 UTC (rev 189126)
@@ -39,8 +39,56 @@
BasicBlock* createPreHeader(Graph& graph, BlockInsertionSet& insertionSet, BasicBlock* block)
{
+ // FIXME: If we run this utility on SSA IR, then we may end up with a bizarre arrangement of
+ // Upsilons and Phis, like:
+ //
+ // BB#1:
+ // Upsilon(@a, ^p)
+ // Jump(#3)
+ //
+ // BB#2:
+ // Upsilon(@b, ^p)
+ // Jump(#3)
+ //
+ // BB#3:
+ // Jump(#4)
+ //
+ // BB#4:
+ // p: Phi()
+ //
+ // Notice how the Upsilons are not in the predecessor of the Phi anymore. It's not clear if this
+ // would be bad. Probably not, but it's weird anyway. We should add a validation rule, and we
+ // should implement a Upsilon/Phi canonicalization that handles this by calling into the
+ // SSACalculator and treating the Upsilons as Defs and rebuilding the Phis from scratch.
+ //
+ // https://bugs.webkit.org/show_bug.cgi?id=148587
+
// Don't bother to preserve execution frequencies for now.
BasicBlock* preHeader = insertionSet.insertBefore(block, PNaN);
+
+ // FIXME: It would be great if we put some effort into enabling exitOK at this origin, if it
+ // happens to be unset. It might not be set because the loop header (i.e. "block") has Phis in it.
+ // Phis have to have exitOK=false. There are a few ways to try to set exitOK:
+ //
+ // - Regenerate an exit origin by proving that we are at an exit origin boundary. If all of the
+ // predecessors' terminals have different exit origins than the exit origin of head of block,
+ // then we can leverage the assumption that exit origin boundaries can always exit. We could
+ // extend this further, and say that we will set exitOK even if a predecessor's terminal has the
+ // same exit origin, but so long it hadn't done anything that clobbers exit since the start of
+ // the origin.
+ //
+ // - Analyze the Phi's and MovHint's at the head of block. If prior to the ExitOK there are only
+ // Phi's and MovHint's, we could "roll them back" by proving that for each of the MovHints, the
+ // referenced Phi has a child that dominates the pre-header, and that child is the node that is
+ // OSR-available at the local being MovHinted.
+ //
+ // Note that there are some obviously wrong ways to try to set exitOK. For example, we cannot
+ // simply use the origin of our predecessors, since in bytecode that could be *any* kind of
+ // instruction. It may not even be a control flow construct, if we had lowered some non-control
+ // bytecode operation into DFG IR that has control flow. Hence, we really do need to try to use the
+ // origin of the head of the loop header.
+ //
+ // https://bugs.webkit.org/show_bug.cgi?id=148586
preHeader->appendNode(
graph, SpecNone, Jump, block->at(0)->origin, OpInfo(block));
Modified: trunk/Source/_javascript_Core/dfg/DFGPlan.cpp (189125 => 189126)
--- trunk/Source/_javascript_Core/dfg/DFGPlan.cpp 2015-08-28 21:54:34 UTC (rev 189125)
+++ trunk/Source/_javascript_Core/dfg/DFGPlan.cpp 2015-08-28 22:38:41 UTC (rev 189126)
@@ -374,7 +374,8 @@
performCleanUp(dfg); // Reduce the graph size a bit.
performCriticalEdgeBreaking(dfg);
- performLoopPreHeaderCreation(dfg);
+ if (Options::createPreHeaders())
+ performLoopPreHeaderCreation(dfg);
performCPSRethreading(dfg);
performSSAConversion(dfg);
performSSALowering(dfg);
Modified: trunk/Source/_javascript_Core/runtime/Options.h (189125 => 189126)
--- trunk/Source/_javascript_Core/runtime/Options.h 2015-08-28 21:54:34 UTC (rev 189125)
+++ trunk/Source/_javascript_Core/runtime/Options.h 2015-08-28 22:38:41 UTC (rev 189126)
@@ -195,6 +195,7 @@
v(unsigned, maxPolymorphicCallVariantsForInlining, 5, nullptr) \
v(unsigned, frequentCallThreshold, 2, nullptr) \
v(double, minimumCallToKnownRate, 0.51, nullptr) \
+ v(bool, createPreHeaders, true, nullptr) \
v(bool, enableMovHintRemoval, true, nullptr) \
v(bool, enableObjectAllocationSinking, true, nullptr) \
\
Added: trunk/Source/_javascript_Core/tests/stress/licm-no-pre-header.js (0 => 189126)
--- trunk/Source/_javascript_Core/tests/stress/licm-no-pre-header.js (rev 0)
+++ trunk/Source/_javascript_Core/tests/stress/licm-no-pre-header.js 2015-08-28 22:38:41 UTC (rev 189126)
@@ -0,0 +1,17 @@
+//@ runMiscFTLNoCJITTest("--createPreHeaders=false")
+
+function foo(array) {
+ var result = 0;
+ var i = 0;
+ if (!array.length)
+ array = [1];
+ do {
+ result += array[i++];
+ } while (i < array.length)
+ return result;
+}
+
+noInline(foo);
+
+for (var i = 0; i < 10000; ++i)
+ foo([1, 2, 3]);
Added: trunk/Source/_javascript_Core/tests/stress/licm-pre-header-cannot-exit.js (0 => 189126)
--- trunk/Source/_javascript_Core/tests/stress/licm-pre-header-cannot-exit.js (rev 0)
+++ trunk/Source/_javascript_Core/tests/stress/licm-pre-header-cannot-exit.js 2015-08-28 22:38:41 UTC (rev 189126)
@@ -0,0 +1,19 @@
+//@ runMiscFTLNoCJITTest("--createPreHeaders=false")
+
+function foo(object, predicate) {
+ var result = 0;
+ var i = 0;
+ if (DFGTrue())
+ predicate = 42;
+ while (predicate >= 42) {
+ result += object.array[i++];
+ if (i >= object.array.length)
+ break;
+ }
+ return result;
+}
+
+noInline(foo);
+
+for (var i = 0; i < 10000; ++i)
+ foo({array: [1, 2, 3]}, {valueOf: function() { return 42; }});
Modified: trunk/Tools/ChangeLog (189125 => 189126)
--- trunk/Tools/ChangeLog 2015-08-28 21:54:34 UTC (rev 189125)
+++ trunk/Tools/ChangeLog 2015-08-28 22:38:41 UTC (rev 189126)
@@ -1,3 +1,14 @@
+2015-08-28 Filip Pizlo <[email protected]>
+
+ LICM should be sound even if the CFG has changed
+ https://bugs.webkit.org/show_bug.cgi?id=148259
+
+ Reviewed by Benjamin Poulain.
+
+ Add a utility for creating tests that set some uncommon option.
+
+ * Scripts/run-jsc-stress-tests:
+
2015-08-28 Brent Fulgham <[email protected]>
[Win] Unreviewed EWS correction.
Modified: trunk/Tools/Scripts/run-jsc-stress-tests (189125 => 189126)
--- trunk/Tools/Scripts/run-jsc-stress-tests 2015-08-28 21:54:34 UTC (rev 189125)
+++ trunk/Tools/Scripts/run-jsc-stress-tests 2015-08-28 22:38:41 UTC (rev 189126)
@@ -762,6 +762,14 @@
run("ftl-no-cjit-small-pool", "--jitMemoryReservationSize=50000", *(FTL_OPTIONS + NO_CJIT_OPTIONS)) if $enableFTL
end
+def runMiscNoCJITTest(*options)
+ run("misc-no-cjit", *(NO_CJIT_OPTIONS + options))
+end
+
+def runMiscFTLNoCJITTest(*options)
+ run("misc-ftl-no-cjit", *(FTL_OPTIONS + NO_CJIT_OPTIONS + options))
+end
+
def defaultRun
runDefault
runAlwaysTriggerCopyPhase
