- Revision
- 203356
- Author
- [email protected]
- Date
- 2016-07-18 11:55:31 -0700 (Mon, 18 Jul 2016)
Log Message
OSR entry into DFG has problems with lexical scoping
https://bugs.webkit.org/show_bug.cgi?id=159687
Reviewed by Saam Barati.
Source/_javascript_Core:
What a fun bug! It turns out that uses of lexical scoping, like "let", may sometimes cause us
to not be able to OSR enter into a loop from baseline to DFG. The bug is in a mitigation for
a different bug, which in turn had a mitigation for yet another bug, so the story here is a
long one.
DFG OSR entry has long had a mitigation for the following bug: the DFG bytecode parser may
choose to make us always OSR exit at some instruction if it thinks that it doesn't have
enough profiling for that instruction. We will do this if some kinds of put_by_id only
execute once, for example. This causes problems for loopy benchmarks like this:
put_by_id(something crazy);
for (var i = 0; i < bigNumber; ++i) simpleMath;
In this case, the put_by_id will have only executed once, and since it did something crazy
that one time, the bytecode parser will replace it with ForceOSRExit.
This creates an OSR entry bug: DFG CFA will then prove that the loop is unreachable, and will
tell OSR entry that it's impossible to enter into that loop.
We mitigated this bug a long time ago by recording mustHandleValues for loops at which we
want to enter. We inject these values into DFG CFA and we force CFA to recognize that the
loop is reachable even if CFA wanted to prove that it wasn't.
But this leads to another bug: we need to scrape the values from the stack inside
operationOptimize() and then we need to reason about them in the compiler. Some of those
values may be garbage, which would cause pandemonium inside the compiler. We also mitigated
this bug, by only recording the "vars", since those are guaranteed to be reset by op_enter.
And that's where the lexical scoping bug happens: "let" bound variables aren't part of the
"vars". DFG will see that they are live, but mustHandleValues will not have anything for
those variables, so CFA will prove that the values are Bottom. Then OSR entry will always
fail because no value is ever a subset of Bottom.
The first part of the fix is to ensure that mustHandleValues record all of the values on the
stack (i.e. within m_numCalleeLocals, rather than just m_numVars). But this creates a second
problem: we may record garbage. This patch includes a better fix for the garbage: before
touching mustHandleValues we run the bytecode liveness analysis and clear any values that are
not live. This ensures that we clear the garbage.
This is an enormous speed-up on microbenchmarks that use lexical scoping and have some crazy
put_by_id in the lead-up to the hot loop.
* dfg/DFGCFAPhase.cpp:
(JSC::DFG::CFAPhase::run):
* dfg/DFGOSREntry.cpp:
(JSC::DFG::prepareOSREntry):
* dfg/DFGPlan.cpp:
(JSC::DFG::Plan::compileInThreadImpl):
(JSC::DFG::Plan::checkLivenessAndVisitChildren):
(JSC::DFG::Plan::cancel):
(JSC::DFG::Plan::cleanMustHandleValuesIfNecessary):
* dfg/DFGPlan.h:
(JSC::DFG::Plan::canTierUpAndOSREnter):
* jit/JITOperations.cpp:
LayoutTests:
* js/regress/script-tests/strict-osr-entry.js: Added.
(let.o.apply_):
* js/regress/strict-osr-entry-expected.txt: Added.
* js/regress/strict-osr-entry.html: Added.
Modified Paths
Added Paths
Diff
Modified: trunk/LayoutTests/ChangeLog (203355 => 203356)
--- trunk/LayoutTests/ChangeLog 2016-07-18 18:51:13 UTC (rev 203355)
+++ trunk/LayoutTests/ChangeLog 2016-07-18 18:55:31 UTC (rev 203356)
@@ -1,3 +1,15 @@
+2016-07-12 Filip Pizlo <[email protected]>
+
+ OSR entry into DFG has problems with lexical scoping
+ https://bugs.webkit.org/show_bug.cgi?id=159687
+
+ Reviewed by Saam Barati.
+
+ * js/regress/script-tests/strict-osr-entry.js: Added.
+ (let.o.apply_):
+ * js/regress/strict-osr-entry-expected.txt: Added.
+ * js/regress/strict-osr-entry.html: Added.
+
2016-07-18 Youenn Fablet <[email protected]>
[Streams API] ReadableStream should throw a RangeError in case of NaN highWaterMark
Added: trunk/LayoutTests/js/regress/script-tests/strict-osr-entry.js (0 => 203356)
--- trunk/LayoutTests/js/regress/script-tests/strict-osr-entry.js (rev 0)
+++ trunk/LayoutTests/js/regress/script-tests/strict-osr-entry.js 2016-07-18 18:55:31 UTC (rev 203356)
@@ -0,0 +1,17 @@
+"use strict";
+
+(function() {
+ let o = {
+ apply_(a, b) {
+ return a + b;
+ }
+ };
+
+ let result = 0;
+ for (let i = 0; i < 10000000; ++i)
+ result = o.apply_(result, 1);
+
+ if (result != 10000000)
+ throw new "Bad result: " + result;
+})();
+
Added: trunk/LayoutTests/js/regress/strict-osr-entry-expected.txt (0 => 203356)
--- trunk/LayoutTests/js/regress/strict-osr-entry-expected.txt (rev 0)
+++ trunk/LayoutTests/js/regress/strict-osr-entry-expected.txt 2016-07-18 18:55:31 UTC (rev 203356)
@@ -0,0 +1,10 @@
+JSRegress/strict-osr-entry
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS no exception thrown
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
Added: trunk/LayoutTests/js/regress/strict-osr-entry.html (0 => 203356)
--- trunk/LayoutTests/js/regress/strict-osr-entry.html (rev 0)
+++ trunk/LayoutTests/js/regress/strict-osr-entry.html 2016-07-18 18:55:31 UTC (rev 203356)
@@ -0,0 +1,12 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<script src=""
+</head>
+<body>
+<script src=""
+<script src=""
+<script src=""
+<script src=""
+</body>
+</html>
Modified: trunk/Source/_javascript_Core/ChangeLog (203355 => 203356)
--- trunk/Source/_javascript_Core/ChangeLog 2016-07-18 18:51:13 UTC (rev 203355)
+++ trunk/Source/_javascript_Core/ChangeLog 2016-07-18 18:55:31 UTC (rev 203356)
@@ -1,3 +1,65 @@
+2016-07-12 Filip Pizlo <[email protected]>
+
+ OSR entry into DFG has problems with lexical scoping
+ https://bugs.webkit.org/show_bug.cgi?id=159687
+
+ Reviewed by Saam Barati.
+
+ What a fun bug! It turns out that uses of lexical scoping, like "let", may sometimes cause us
+ to not be able to OSR enter into a loop from baseline to DFG. The bug is in a mitigation for
+ a different bug, which in turn had a mitigation for yet another bug, so the story here is a
+ long one.
+
+ DFG OSR entry has long had a mitigation for the following bug: the DFG bytecode parser may
+ choose to make us always OSR exit at some instruction if it thinks that it doesn't have
+ enough profiling for that instruction. We will do this if some kinds of put_by_id only
+ execute once, for example. This causes problems for loopy benchmarks like this:
+
+ put_by_id(something crazy);
+ for (var i = 0; i < bigNumber; ++i) simpleMath;
+
+ In this case, the put_by_id will have only executed once, and since it did something crazy
+ that one time, the bytecode parser will replace it with ForceOSRExit.
+
+ This creates an OSR entry bug: DFG CFA will then prove that the loop is unreachable, and will
+ tell OSR entry that it's impossible to enter into that loop.
+
+ We mitigated this bug a long time ago by recording mustHandleValues for loops at which we
+ want to enter. We inject these values into DFG CFA and we force CFA to recognize that the
+ loop is reachable even if CFA wanted to prove that it wasn't.
+
+ But this leads to another bug: we need to scrape the values from the stack inside
+ operationOptimize() and then we need to reason about them in the compiler. Some of those
+ values may be garbage, which would cause pandemonium inside the compiler. We also mitigated
+ this bug, by only recording the "vars", since those are guaranteed to be reset by op_enter.
+
+ And that's where the lexical scoping bug happens: "let" bound variables aren't part of the
+ "vars". DFG will see that they are live, but mustHandleValues will not have anything for
+ those variables, so CFA will prove that the values are Bottom. Then OSR entry will always
+ fail because no value is ever a subset of Bottom.
+
+ The first part of the fix is to ensure that mustHandleValues record all of the values on the
+ stack (i.e. within m_numCalleeLocals, rather than just m_numVars). But this creates a second
+ problem: we may record garbage. This patch includes a better fix for the garbage: before
+ touching mustHandleValues we run the bytecode liveness analysis and clear any values that are
+ not live. This ensures that we clear the garbage.
+
+ This is an enormous speed-up on microbenchmarks that use lexical scoping and have some crazy
+ put_by_id in the lead-up to the hot loop.
+
+ * dfg/DFGCFAPhase.cpp:
+ (JSC::DFG::CFAPhase::run):
+ * dfg/DFGOSREntry.cpp:
+ (JSC::DFG::prepareOSREntry):
+ * dfg/DFGPlan.cpp:
+ (JSC::DFG::Plan::compileInThreadImpl):
+ (JSC::DFG::Plan::checkLivenessAndVisitChildren):
+ (JSC::DFG::Plan::cancel):
+ (JSC::DFG::Plan::cleanMustHandleValuesIfNecessary):
+ * dfg/DFGPlan.h:
+ (JSC::DFG::Plan::canTierUpAndOSREnter):
+ * jit/JITOperations.cpp:
+
2016-07-18 Youenn Fablet <[email protected]>
REGRESSION(r202975): --minimal build is broken
Modified: trunk/Source/_javascript_Core/dfg/DFGCFAPhase.cpp (203355 => 203356)
--- trunk/Source/_javascript_Core/dfg/DFGCFAPhase.cpp 2016-07-18 18:51:13 UTC (rev 203355)
+++ trunk/Source/_javascript_Core/dfg/DFGCFAPhase.cpp 2016-07-18 18:55:31 UTC (rev 203356)
@@ -80,6 +80,9 @@
} while (m_changed);
if (m_graph.m_form != SSA) {
+ if (m_verbose)
+ dataLog(" Widening state at OSR entry block.\n");
+
ASSERT(!m_changed);
// Widen the abstract values at the block that serves as the must-handle OSR entry.
@@ -93,14 +96,23 @@
if (block->bytecodeBegin != m_graph.m_plan.osrEntryBytecodeIndex)
continue;
+ if (m_verbose)
+ dataLog(" Found must-handle block: ", *block, "\n");
+
bool changed = false;
for (size_t i = m_graph.m_plan.mustHandleValues.size(); i--;) {
int operand = m_graph.m_plan.mustHandleValues.operandForIndex(i);
JSValue value = m_graph.m_plan.mustHandleValues[i];
Node* node = block->variablesAtHead.operand(operand);
- if (!node)
+ if (!node) {
+ if (m_verbose)
+ dataLog(" Not live: ", VirtualRegister(operand), "\n");
continue;
+ }
+ if (m_verbose)
+ dataLog(" Widening ", VirtualRegister(operand), " with ", value, "\n");
+
AbstractValue& target = block->valuesAtHead.operand(operand);
changed |= target.mergeOSREntryValue(m_graph, value);
target.fixTypeForRepresentation(
Modified: trunk/Source/_javascript_Core/dfg/DFGOSREntry.cpp (203355 => 203356)
--- trunk/Source/_javascript_Core/dfg/DFGOSREntry.cpp 2016-07-18 18:51:13 UTC (rev 203355)
+++ trunk/Source/_javascript_Core/dfg/DFGOSREntry.cpp 2016-07-18 18:55:31 UTC (rev 203356)
@@ -228,7 +228,7 @@
if (!entry->m_expectedValues.local(local).validate(exec->registers()[localOffset].asanUnsafeJSValue())) {
if (Options::verboseOSR()) {
dataLog(
- " OSR failed because variable ", localOffset, " is ",
+ " OSR failed because variable ", VirtualRegister(localOffset), " is ",
exec->registers()[localOffset].asanUnsafeJSValue(), ", expected ",
entry->m_expectedValues.local(local), ".\n");
}
Modified: trunk/Source/_javascript_Core/dfg/DFGPlan.cpp (203355 => 203356)
--- trunk/Source/_javascript_Core/dfg/DFGPlan.cpp 2016-07-18 18:51:13 UTC (rev 203355)
+++ trunk/Source/_javascript_Core/dfg/DFGPlan.cpp 2016-07-18 18:55:31 UTC (rev 203356)
@@ -238,6 +238,8 @@
Plan::CompilationPath Plan::compileInThreadImpl(LongLivedState& longLivedState)
{
+ cleanMustHandleValuesIfNecessary();
+
if (verboseCompilationEnabled(mode) && osrEntryBytecodeIndex != UINT_MAX) {
dataLog("\n");
dataLog("Compiler must handle OSR entry from bc#", osrEntryBytecodeIndex, " with values: ", mustHandleValues, "\n");
@@ -626,7 +628,8 @@
{
if (!isKnownToBeLiveDuringGC())
return;
-
+
+ cleanMustHandleValuesIfNecessary();
for (unsigned i = mustHandleValues.size(); i--;)
visitor.appendUnbarrieredValue(&mustHandleValues[i]);
@@ -675,6 +678,29 @@
stage = Cancelled;
}
+void Plan::cleanMustHandleValuesIfNecessary()
+{
+ LockHolder locker(mustHandleValueCleaningLock);
+
+ if (!mustHandleValuesMayIncludeGarbage)
+ return;
+
+ mustHandleValuesMayIncludeGarbage = false;
+
+ if (!codeBlock)
+ return;
+
+ if (!mustHandleValues.numberOfLocals())
+ return;
+
+ FastBitVector liveness = codeBlock->alternative()->livenessAnalysis().getLivenessInfoAtBytecodeOffset(osrEntryBytecodeIndex);
+
+ for (unsigned local = mustHandleValues.numberOfLocals(); local--;) {
+ if (!liveness.get(local))
+ mustHandleValues.local(local) = jsUndefined();
+ }
+}
+
} } // namespace JSC::DFG
#endif // ENABLE(DFG_JIT)
Modified: trunk/Source/_javascript_Core/dfg/DFGPlan.h (203355 => 203356)
--- trunk/Source/_javascript_Core/dfg/DFGPlan.h 2016-07-18 18:51:13 UTC (rev 203355)
+++ trunk/Source/_javascript_Core/dfg/DFGPlan.h 2016-07-18 18:55:31 UTC (rev 203356)
@@ -78,6 +78,8 @@
bool canTierUpAndOSREnter() const { return !tierUpAndOSREnterBytecodes.isEmpty(); }
+ void cleanMustHandleValuesIfNecessary();
+
// Warning: pretty much all of the pointer fields in this object get nulled by cancel(). So, if
// you're writing code that is callable on the cancel path, be sure to null check everything!
@@ -90,6 +92,8 @@
CompilationMode mode;
const unsigned osrEntryBytecodeIndex;
Operands<JSValue> mustHandleValues;
+ bool mustHandleValuesMayIncludeGarbage { true };
+ Lock mustHandleValueCleaningLock;
ThreadData* threadData;
Modified: trunk/Source/_javascript_Core/jit/JITOperations.cpp (203355 => 203356)
--- trunk/Source/_javascript_Core/jit/JITOperations.cpp 2016-07-18 18:51:13 UTC (rev 203355)
+++ trunk/Source/_javascript_Core/jit/JITOperations.cpp 2016-07-18 18:55:31 UTC (rev 203356)
@@ -1353,7 +1353,7 @@
unsigned numVarsWithValues;
if (bytecodeIndex)
- numVarsWithValues = codeBlock->m_numVars;
+ numVarsWithValues = codeBlock->m_numCalleeLocals;
else
numVarsWithValues = 0;
Operands<JSValue> mustHandleValues(codeBlock->numParameters(), numVarsWithValues);
