Our for-in optimization in the bytecode generator does its static analysis incorrectly
https://bugs.webkit.org/show_bug.cgi?id=172532
<rdar://problem/32369452>
Reviewed by Mark Lam.
JSTests:
* stress/for-in-invalidation-for-any-write.js: Added.
(assert):
(test):
(test.i):
Source/JavaScriptCore:
Our static analysis for when a for-in induction variable
is written to tried to its analysis as we generate
bytecode. This has issues, since it does not account for
the dynamic execution path of the program. Let's consider
a program where our old analysis worked:
```
for (let p in o) {
o[p]; // We can transform this into a fast get_direct_pname
p = 20;
o[p]; // We cannot transform this since p has been changed.
}
```
However, our static analysis did not account for loops, which exist
in JavaScript. e.g, it would incorrectly compile this program as:
```
for (let p in o) {
for (let i = 0; i < 20; ++i) {
o[p]; // It transforms this to use get_direct_pname even though p will be over-written if we get here from the inner loop back edge!
p = 20;
o[p]; // We correctly do not transform this.
}
}
```
Because of this flaw, I've made the optimization more conservative.
We now optimistically emit code for the optimized access. However,
if a for-in context is *ever* invalidated, before we pop it off
the stack, we rewrite the program's optimized accesses to no longer
be optimized. To do this, each context keeps track of its optimized
accesses.
This patch also adds a new bytecode, op_nop, which is just a no-op.
It was helpful to add this because reverting get_direct_pname to get_by_val
will leave us with an extra instruction word because get_direct_pname is
has a length of 7 where get_by_val has a length of 6. This leaves us with
an extra slot that we fill with an op_nop.
* bytecode/BytecodeDumper.cpp:
(JSC::BytecodeDumper<Block>::dumpBytecode):
* bytecode/BytecodeList.json:
* bytecode/BytecodeUseDef.h:
(JSC::computeUsesForBytecodeOffset):
(JSC::computeDefsForBytecodeOffset):
* bytecompiler/BytecodeGenerator.cpp:
(JSC::BytecodeGenerator::emitGetByVal):
(JSC::BytecodeGenerator::popIndexedForInScope):
(JSC::BytecodeGenerator::popStructureForInScope):
(JSC::BytecodeGenerator::invalidateForInContextForLocal):
(JSC::StructureForInContext::pop):
(JSC::IndexedForInContext::pop):
* bytecompiler/BytecodeGenerator.h:
(JSC::StructureForInContext::addGetInst):
(JSC::IndexedForInContext::addGetInst):
* dfg/DFGByteCodeParser.cpp:
(JSC::DFG::ByteCodeParser::parseBlock):
* dfg/DFGCapabilities.cpp:
(JSC::DFG::capabilityLevel):
* jit/JIT.cpp:
(JSC::JIT::privateCompileMainPass):
* jit/JIT.h:
* jit/JITOpcodes.cpp:
(JSC::JIT::emit_op_nop):
* llint/LowLevelInterpreter.asm:
git-svn-id: http://svn.webkit.org/repository/webkit/trunk@217438 268f45cc-cd09-0410-ab3c-d52691b4dbfc
diff --git a/JSTests/ChangeLog b/JSTests/ChangeLog
index 3eacf08..2d8d90a 100644
--- a/JSTests/ChangeLog
+++ b/JSTests/ChangeLog
@@ -1,3 +1,16 @@
+2017-05-25 Saam Barati <sbarati@apple.com>
+
+ Our for-in optimization in the bytecode generator does its static analysis incorrectly
+ https://bugs.webkit.org/show_bug.cgi?id=172532
+ <rdar://problem/32369452>
+
+ Reviewed by Mark Lam.
+
+ * stress/for-in-invalidation-for-any-write.js: Added.
+ (assert):
+ (test):
+ (test.i):
+
2017-05-25 Mark Lam <mark.lam@apple.com>
ObjectToStringAdaptiveInferredPropertyValueWatchpoint should not reinstall itself nor handleFire if it's dying shortly.
diff --git a/JSTests/stress/for-in-invalidation-for-any-write.js b/JSTests/stress/for-in-invalidation-for-any-write.js
new file mode 100644
index 0000000..7cbbbf2
--- /dev/null
+++ b/JSTests/stress/for-in-invalidation-for-any-write.js
@@ -0,0 +1,146 @@
+function assert(b) {
+ if (!b)
+ throw new Error("Bad assertion");
+}
+noInline(assert);
+
+function test(f) {
+ noInline(f);
+ for (let i = 0; i < 1000; ++i)
+ f();
+}
+
+test(function() {
+ let o = {xx: 42};
+ for (let i in o) {
+ for (let j = 0; j < 2; j++) {
+ let r = o[i];
+ if (i === "xx")
+ assert(r === 42);
+ i = function() { }
+ }
+ }
+});
+
+test(function() {
+ let o = {xx: 42};
+ for (let i in {xx: 0}) {
+ for (let j = 0; j < 2; j++) {
+ let r = o[i];
+ if (i === "xx")
+ assert(r === 42);
+ i = new Uint32Array([0, 1, 0x777777, 0, 0]);
+ }
+ }
+});
+
+test(function() {
+ let o = {xx: 42};
+ for (let i in {xx: 0}) {
+ for (let j = 0; j < 2; j++) {
+ let r = o[i];
+ if (i === "xx")
+ assert(r === 42);
+ ([i] = [new Uint32Array([0, 1, 0x777777, 0, 0])]);
+ }
+ }
+});
+
+test(function() {
+ let o = {xx: 42};
+ for (let i in {xx: 0}) {
+ for (let j = 0; j < 2; j++) {
+ let r = o[i];
+ if (i === "xx")
+ assert(r === 42);
+ ({xyz: i} = {xyz: new Uint32Array([0, 1, 0x777777, 0, 0])});
+ }
+ }
+});
+
+test(function() {
+ let o = [1,2,3];
+ let toStringCalls = 0;
+ let first;
+ let num = 0;
+ let total = 0;
+ for (let i in o) {
+ first = true;
+ for (let j = 0; j < 3; j++) {
+ let r = o[i];
+ if (first)
+ assert(r === o[num]);
+ else
+ assert(r === undefined);
+ first = false;
+ i = {
+ toString() {
+ ++toStringCalls;
+ return "hello!";
+ }
+ }
+ }
+ ++num;
+ }
+
+ // Should be called twice per outer for-in loop.
+ assert(toStringCalls === o.length * 2);
+});
+
+test(function() {
+ let o = [1,2,3];
+ let toStringCalls = 0;
+ let first;
+ let num = 0;
+ let total = 0;
+ for (let i in o) {
+ first = true;
+ for (let j = 0; j < 3; j++) {
+ let r = o[i];
+ if (first)
+ assert(r === o[num]);
+ else
+ assert(r === undefined);
+ first = false;
+ ([i] = [{
+ toString() {
+ ++toStringCalls;
+ return "hello!";
+ }
+ }]);
+ }
+ ++num;
+ }
+
+ // Should be called twice per outer for-in loop.
+ assert(toStringCalls === o.length * 2);
+});
+
+test(function() {
+ let o = [1,2,3];
+ let toStringCalls = 0;
+ let first;
+ let num = 0;
+ let total = 0;
+ for (let i in o) {
+ first = true;
+ for (let j = 0; j < 3; j++) {
+ let r = o[i];
+ if (first)
+ assert(r === o[num]);
+ else
+ assert(r === undefined);
+ first = false;
+ ({xyz: i} = {xyz: {
+ toString() {
+ ++toStringCalls;
+ return "hello!";
+ }
+ }});
+ }
+ ++num;
+ }
+
+ // Should be called twice per outer for-in loop.
+ assert(toStringCalls === o.length * 2);
+});
diff --git a/Source/JavaScriptCore/ChangeLog b/Source/JavaScriptCore/ChangeLog
index fb8a734..bf0b98c 100644
--- a/Source/JavaScriptCore/ChangeLog
+++ b/Source/JavaScriptCore/ChangeLog
@@ -1,3 +1,77 @@
+2017-05-25 Saam Barati <sbarati@apple.com>
+
+ Our for-in optimization in the bytecode generator does its static analysis incorrectly
+ https://bugs.webkit.org/show_bug.cgi?id=172532
+ <rdar://problem/32369452>
+
+ Reviewed by Mark Lam.
+
+ Our static analysis for when a for-in induction variable
+ is written to tried to its analysis as we generate
+ bytecode. This has issues, since it does not account for
+ the dynamic execution path of the program. Let's consider
+ a program where our old analysis worked:
+
+ ```
+ for (let p in o) {
+ o[p]; // We can transform this into a fast get_direct_pname
+ p = 20;
+ o[p]; // We cannot transform this since p has been changed.
+ }
+ ```
+
+ However, our static analysis did not account for loops, which exist
+ in JavaScript. e.g, it would incorrectly compile this program as:
+ ```
+ for (let p in o) {
+ for (let i = 0; i < 20; ++i) {
+ o[p]; // It transforms this to use get_direct_pname even though p will be over-written if we get here from the inner loop back edge!
+ p = 20;
+ o[p]; // We correctly do not transform this.
+ }
+ }
+ ```
+
+ Because of this flaw, I've made the optimization more conservative.
+ We now optimistically emit code for the optimized access. However,
+ if a for-in context is *ever* invalidated, before we pop it off
+ the stack, we rewrite the program's optimized accesses to no longer
+ be optimized. To do this, each context keeps track of its optimized
+ accesses.
+
+ This patch also adds a new bytecode, op_nop, which is just a no-op.
+ It was helpful to add this because reverting get_direct_pname to get_by_val
+ will leave us with an extra instruction word because get_direct_pname is
+ has a length of 7 where get_by_val has a length of 6. This leaves us with
+ an extra slot that we fill with an op_nop.
+
+ * bytecode/BytecodeDumper.cpp:
+ (JSC::BytecodeDumper<Block>::dumpBytecode):
+ * bytecode/BytecodeList.json:
+ * bytecode/BytecodeUseDef.h:
+ (JSC::computeUsesForBytecodeOffset):
+ (JSC::computeDefsForBytecodeOffset):
+ * bytecompiler/BytecodeGenerator.cpp:
+ (JSC::BytecodeGenerator::emitGetByVal):
+ (JSC::BytecodeGenerator::popIndexedForInScope):
+ (JSC::BytecodeGenerator::popStructureForInScope):
+ (JSC::BytecodeGenerator::invalidateForInContextForLocal):
+ (JSC::StructureForInContext::pop):
+ (JSC::IndexedForInContext::pop):
+ * bytecompiler/BytecodeGenerator.h:
+ (JSC::StructureForInContext::addGetInst):
+ (JSC::IndexedForInContext::addGetInst):
+ * dfg/DFGByteCodeParser.cpp:
+ (JSC::DFG::ByteCodeParser::parseBlock):
+ * dfg/DFGCapabilities.cpp:
+ (JSC::DFG::capabilityLevel):
+ * jit/JIT.cpp:
+ (JSC::JIT::privateCompileMainPass):
+ * jit/JIT.h:
+ * jit/JITOpcodes.cpp:
+ (JSC::JIT::emit_op_nop):
+ * llint/LowLevelInterpreter.asm:
+
2017-05-25 Mark Lam <mark.lam@apple.com>
ObjectToStringAdaptiveInferredPropertyValueWatchpoint should not reinstall itself nor handleFire if it's dying shortly.
diff --git a/Source/JavaScriptCore/bytecode/BytecodeDumper.cpp b/Source/JavaScriptCore/bytecode/BytecodeDumper.cpp
index 75a5420..7697ad12 100644
--- a/Source/JavaScriptCore/bytecode/BytecodeDumper.cpp
+++ b/Source/JavaScriptCore/bytecode/BytecodeDumper.cpp
@@ -1265,6 +1265,10 @@
printLocationAndOp(out, location, it, "check_traps");
break;
}
+ case op_nop: {
+ printLocationAndOp(out, location, it, "nop");
+ break;
+ }
case op_log_shadow_chicken_prologue: {
int r0 = (++it)->u.operand;
printLocationAndOp(out, location, it, "log_shadow_chicken_prologue");
diff --git a/Source/JavaScriptCore/bytecode/BytecodeList.json b/Source/JavaScriptCore/bytecode/BytecodeList.json
index 2b1cae2..11b9a65 100644
--- a/Source/JavaScriptCore/bytecode/BytecodeList.json
+++ b/Source/JavaScriptCore/bytecode/BytecodeList.json
@@ -153,7 +153,8 @@
{ "name" : "op_check_traps", "length" : 1 },
{ "name" : "op_log_shadow_chicken_prologue", "length" : 2},
{ "name" : "op_log_shadow_chicken_tail", "length" : 3},
- { "name" : "op_resolve_scope_for_hoisting_func_decl_in_eval", "length" : 4 }
+ { "name" : "op_resolve_scope_for_hoisting_func_decl_in_eval", "length" : 4 },
+ { "name" : "op_nop", "length" : 1 }
]
},
{
diff --git a/Source/JavaScriptCore/bytecode/BytecodeUseDef.h b/Source/JavaScriptCore/bytecode/BytecodeUseDef.h
index 87a5cbd..12440ef 100644
--- a/Source/JavaScriptCore/bytecode/BytecodeUseDef.h
+++ b/Source/JavaScriptCore/bytecode/BytecodeUseDef.h
@@ -54,6 +54,7 @@
case op_get_rest_length:
case op_check_traps:
case op_get_argument:
+ case op_nop:
return;
case op_assert:
case op_get_scope:
@@ -364,6 +365,7 @@
case op_log_shadow_chicken_prologue:
case op_log_shadow_chicken_tail:
case op_yield:
+ case op_nop:
#define LLINT_HELPER_OPCODES(opcode, length) case opcode:
FOR_EACH_LLINT_OPCODE_EXTENSION(LLINT_HELPER_OPCODES);
#undef LLINT_HELPER_OPCODES
diff --git a/Source/JavaScriptCore/bytecompiler/BytecodeGenerator.cpp b/Source/JavaScriptCore/bytecompiler/BytecodeGenerator.cpp
index 63bfd66..d1fd681 100644
--- a/Source/JavaScriptCore/bytecompiler/BytecodeGenerator.cpp
+++ b/Source/JavaScriptCore/bytecompiler/BytecodeGenerator.cpp
@@ -2843,15 +2843,15 @@
RegisterID* BytecodeGenerator::emitGetByVal(RegisterID* dst, RegisterID* base, RegisterID* property)
{
- for (size_t i = m_forInContextStack.size(); i > 0; i--) {
- ForInContext& context = m_forInContextStack[i - 1].get();
+ for (size_t i = m_forInContextStack.size(); i--; ) {
+ ForInContext& context = m_forInContextStack[i].get();
if (context.local() != property)
continue;
- if (!context.isValid())
- break;
+ unsigned instIndex = instructions().size();
if (context.type() == ForInContext::IndexedForInContextType) {
+ static_cast<IndexedForInContext&>(context).addGetInst(instIndex, property->index());
property = static_cast<IndexedForInContext&>(context).index();
break;
}
@@ -2865,6 +2865,8 @@
instructions().append(structureContext.index()->index());
instructions().append(structureContext.enumerator()->index());
instructions().append(profile);
+
+ structureContext.addGetInst(instIndex, property->index(), profile);
return dst;
}
@@ -4555,6 +4557,9 @@
{
if (!localRegister)
return;
+
+ ASSERT(m_forInContextStack.last()->type() == ForInContext::IndexedForInContextType);
+ static_cast<IndexedForInContext&>(m_forInContextStack.last().get()).finalize(*this);
m_forInContextStack.removeLast();
}
@@ -4663,6 +4668,8 @@
{
if (!localRegister)
return;
+ ASSERT(m_forInContextStack.last()->type() == ForInContext::StructureForInContextType);
+ static_cast<StructureForInContext&>(m_forInContextStack.last().get()).finalize(*this);
m_forInContextStack.removeLast();
}
@@ -4679,8 +4686,8 @@
// to perform some flow-sensitive analysis to see if/when the loop iteration variable was
// reassigned, or we'd have to resort to runtime checks to see if the variable had been
// reassigned from its original value.
- for (size_t i = m_forInContextStack.size(); i > 0; i--) {
- ForInContext& context = m_forInContextStack[i - 1].get();
+ for (size_t i = m_forInContextStack.size(); i--; ) {
+ ForInContext& context = m_forInContextStack[i].get();
if (context.local() != localRegister)
continue;
context.invalidate();
@@ -5034,6 +5041,51 @@
emitJumpIfTrue(equivalenceResult, jumpTarget);
}
+void StructureForInContext::finalize(BytecodeGenerator& generator)
+{
+ if (isValid())
+ return;
+
+ for (const auto& instTuple : m_getInsts) {
+ unsigned instIndex = std::get<0>(instTuple);
+ int propertyRegIndex = std::get<1>(instTuple);
+ UnlinkedValueProfile valueProfile = std::get<2>(instTuple);
+ OpcodeID op = generator.instructions()[instIndex].u.opcode;
+ RELEASE_ASSERT(op == op_get_direct_pname);
+ ASSERT(opcodeLength(op_get_direct_pname) == 7);
+ ASSERT(opcodeLength(op_get_by_val) == 6);
+
+ // 0. Change the opcode to get_by_val.
+ generator.instructions()[instIndex].u.opcode = op_get_by_val;
+ // 1. dst stays the same.
+ // 2. base stays the same.
+ // 3. property gets switched to the original property.
+ generator.instructions()[instIndex + 3].u.operand = propertyRegIndex;
+ // 4. add an array profile.
+ generator.instructions()[instIndex + 4].u.unsignedValue = generator.newArrayProfile();
+ // 5. set the result value profile.
+ generator.instructions()[instIndex + 5].u.unsignedValue = valueProfile;
+ // 6. nop out the last instruction word.
+ generator.instructions()[instIndex + 6].u.opcode = op_nop;
+ }
+}
+
+void IndexedForInContext::finalize(BytecodeGenerator& generator)
+{
+ if (isValid())
+ return;
+
+ for (const auto& instPair : m_getInsts) {
+ unsigned instIndex = instPair.first;
+ int propertyRegIndex = instPair.second;
+ OpcodeID op = generator.instructions()[instIndex].u.opcode;
+ RELEASE_ASSERT(op == op_get_by_val);
+ // We just need to perform the get_by_val with the original property here,
+ // not the indexed one.
+ generator.instructions()[instIndex + 3].u.operand = propertyRegIndex;
+ }
+}
+
} // namespace JSC
namespace WTF {
diff --git a/Source/JavaScriptCore/bytecompiler/BytecodeGenerator.h b/Source/JavaScriptCore/bytecompiler/BytecodeGenerator.h
index c7f47f0..db3197a 100644
--- a/Source/JavaScriptCore/bytecompiler/BytecodeGenerator.h
+++ b/Source/JavaScriptCore/bytecompiler/BytecodeGenerator.h
@@ -221,10 +221,18 @@
RegisterID* property() const { return m_propertyRegister.get(); }
RegisterID* enumerator() const { return m_enumeratorRegister.get(); }
+ void addGetInst(unsigned instIndex, int propertyRegIndex, UnlinkedValueProfile valueProfile)
+ {
+ m_getInsts.append({ instIndex, propertyRegIndex, valueProfile });
+ }
+
+ void finalize(BytecodeGenerator&);
+
private:
RefPtr<RegisterID> m_indexRegister;
RefPtr<RegisterID> m_propertyRegister;
RefPtr<RegisterID> m_enumeratorRegister;
+ Vector<std::tuple<unsigned, int, UnlinkedValueProfile>> m_getInsts;
};
class IndexedForInContext : public ForInContext {
@@ -242,8 +250,12 @@
RegisterID* index() const { return m_indexRegister.get(); }
+ void finalize(BytecodeGenerator&);
+ void addGetInst(unsigned instIndex, int propertyIndex) { m_getInsts.append({ instIndex, propertyIndex }); }
+
private:
RefPtr<RegisterID> m_indexRegister;
+ Vector<std::pair<unsigned, int>> m_getInsts;
};
struct TryData {
@@ -942,6 +954,7 @@
void popLexicalScope(VariableEnvironmentNode*);
void prepareLexicalScopeForNextForLoopIteration(VariableEnvironmentNode*, RegisterID* loopSymbolTable);
int labelScopeDepth() const;
+ UnlinkedArrayProfile newArrayProfile();
private:
ParserError generate();
@@ -951,7 +964,6 @@
void emitOpcode(OpcodeID);
UnlinkedArrayAllocationProfile newArrayAllocationProfile();
UnlinkedObjectAllocationProfile newObjectAllocationProfile();
- UnlinkedArrayProfile newArrayProfile();
UnlinkedValueProfile emitProfiledOpcode(OpcodeID);
int kill(RegisterID* dst)
{
diff --git a/Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp b/Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp
index f0aa6e9..d5d0f82 100644
--- a/Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp
+++ b/Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp
@@ -5550,6 +5550,11 @@
addToGraph(CheckTraps);
NEXT_OPCODE(op_check_traps);
}
+
+ case op_nop: {
+ addToGraph(Check); // We add a nop here so that basic block linking doesn't break.
+ NEXT_OPCODE(op_nop);
+ }
case op_create_lexical_environment: {
VirtualRegister symbolTableRegister(currentInstruction[3].u.operand);
diff --git a/Source/JavaScriptCore/dfg/DFGCapabilities.cpp b/Source/JavaScriptCore/dfg/DFGCapabilities.cpp
index 842889e..27c30f5 100644
--- a/Source/JavaScriptCore/dfg/DFGCapabilities.cpp
+++ b/Source/JavaScriptCore/dfg/DFGCapabilities.cpp
@@ -188,6 +188,7 @@
case op_jngreatereq:
case op_loop_hint:
case op_check_traps:
+ case op_nop:
case op_ret:
case op_end:
case op_new_object:
diff --git a/Source/JavaScriptCore/jit/JIT.cpp b/Source/JavaScriptCore/jit/JIT.cpp
index 9b672fd..a2d1d2d 100644
--- a/Source/JavaScriptCore/jit/JIT.cpp
+++ b/Source/JavaScriptCore/jit/JIT.cpp
@@ -330,6 +330,7 @@
DEFINE_OP(op_jtrue)
DEFINE_OP(op_loop_hint)
DEFINE_OP(op_check_traps)
+ DEFINE_OP(op_nop)
DEFINE_OP(op_lshift)
DEFINE_OP(op_mod)
DEFINE_OP(op_mov)
diff --git a/Source/JavaScriptCore/jit/JIT.h b/Source/JavaScriptCore/jit/JIT.h
index 43685b3..518165f 100644
--- a/Source/JavaScriptCore/jit/JIT.h
+++ b/Source/JavaScriptCore/jit/JIT.h
@@ -531,6 +531,7 @@
void emit_op_jtrue(Instruction*);
void emit_op_loop_hint(Instruction*);
void emit_op_check_traps(Instruction*);
+ void emit_op_nop(Instruction*);
void emit_op_lshift(Instruction*);
void emit_op_mod(Instruction*);
void emit_op_mov(Instruction*);
diff --git a/Source/JavaScriptCore/jit/JITOpcodes.cpp b/Source/JavaScriptCore/jit/JITOpcodes.cpp
index 452be1a..8adccbe 100644
--- a/Source/JavaScriptCore/jit/JITOpcodes.cpp
+++ b/Source/JavaScriptCore/jit/JITOpcodes.cpp
@@ -948,6 +948,10 @@
addSlowCase(branchTest8(NonZero, AbsoluteAddress(m_vm->needTrapHandlingAddress())));
}
+void JIT::emit_op_nop(Instruction*)
+{
+}
+
void JIT::emitSlow_op_check_traps(Instruction*, Vector<SlowCaseEntry>::iterator& iter)
{
linkSlowCase(iter);
diff --git a/Source/JavaScriptCore/llint/LowLevelInterpreter.asm b/Source/JavaScriptCore/llint/LowLevelInterpreter.asm
index da9c24e..2fcb6e6 100644
--- a/Source/JavaScriptCore/llint/LowLevelInterpreter.asm
+++ b/Source/JavaScriptCore/llint/LowLevelInterpreter.asm
@@ -1571,6 +1571,10 @@
end
+_llint_op_nop:
+ dispatch(1)
+
+
_llint_op_switch_string:
traceExecution()
callOpcodeSlowPath(_llint_slow_path_switch_string)
