From 50d48a45bb88ae716ccb9320c535aa44af16b687 Mon Sep 17 00:00:00 2001 From: "fpizlo@apple.com" Date: Tue, 26 Apr 2016 17:38:43 +0000 Subject: [PATCH] DFG backends shouldn't emit type checks at KnownBlah edges https://bugs.webkit.org/show_bug.cgi?id=157025 Reviewed by Michael Saboff. This fixes a crash I found when browsing Bing maps with forceEagerCompilation. I include a 100% repro test case. The issue is that our code still doesn't fully appreciate the devious implications of KnownBlah use kinds. Consider KnownCell for example. It means: "trust me, I know that this value will be a cell". You aren't required to provide a proof when you use KnownCell. Often, we use it as a result of a path-sensitive proof. The abstract interpreter is not path-sensitive, so AI will be absolutely sure that the KnownCell use might see a non-cell. This can lead to debug assertions (which this change removes) and it can lead to the backends emitting a type check. That type check can be pure evil if the node that has this edge does not have an exit origin. Such a node would have passed validation because the validater would have thought that the node cannot exit (after all, according to the IR semantics, there is no speculation at KnownCell). This comprehensively fixes the issue by recognizing that Foo(KnownCell:@x) means: I have already proved that by the time you start executing Foo, @x will already be a cell. I cannot tell you how I proved this but you can rely on it anyway. AI now takes advantage of this meaning and will always do filtering of KnownBlah edges regardless of whether the backend actually emits any type checks for those edges. Since the filtering runs before the backend, the backend will not emit any checks because it will know that the edge was already checked (by whatever mechanism we used when we made the edge KnownBlah). Note that it's good that we found this bug now. The DFG currently does very few sparse-conditional or path-sensitive optimizations, but it will probably do more in the future. The bug happens because GetByOffset and friends can achieve path-sensitive proofs via watchpoints on the inferred type. Normally, AI can follow along with this proof. But in the example program, and on Bing maps, we would GCSE one GetByOffset with another that had a weaker proven type. That turned out to be completely sound - between the two GetByOffset's there was a Branch to null check it. The inferred type of the second GetByOffset ended up knowing that it cannot be null because null only occurred in some structures but not others. If we added more sparse-conditional stuff to Branch, then AI would know how to follow along with the proof but it would also create more situations where we'd have a path-sensitive proof. So, it's good that we're now getting this right. * dfg/DFGAbstractInterpreter.h: (JSC::DFG::AbstractInterpreter::filterEdgeByUse): * dfg/DFGAbstractInterpreterInlines.h: (JSC::DFG::AbstractInterpreter::executeEdges): (JSC::DFG::AbstractInterpreter::executeKnownEdgeTypes): (JSC::DFG::AbstractInterpreter::verifyEdge): * dfg/DFGSpeculativeJIT.cpp: (JSC::DFG::SpeculativeJIT::compileCurrentBlock): * dfg/DFGUseKind.h: (JSC::DFG::typeFilterFor): * ftl/FTLLowerDFGToB3.cpp: (JSC::FTL::DFG::LowerDFGToB3::compileNode): * tests/stress/path-sensitive-known-cell-crash.js: Added. (bar): (foo): git-svn-id: https://svn.webkit.org/repository/webkit/trunk@200096 268f45cc-cd09-0410-ab3c-d52691b4dbfc --- Source/JavaScriptCore/ChangeLog | 57 ++++++++++++++++++++++ Source/JavaScriptCore/dfg/DFGAbstractInterpreter.h | 9 ++-- .../dfg/DFGAbstractInterpreterInlines.h | 28 ++++++++--- Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp | 1 + Source/JavaScriptCore/dfg/DFGUseKind.h | 2 +- Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp | 1 + .../stress/path-sensitive-known-cell-crash.js | 21 ++++++++ 7 files changed, 106 insertions(+), 13 deletions(-) create mode 100644 Source/JavaScriptCore/tests/stress/path-sensitive-known-cell-crash.js diff --git a/Source/JavaScriptCore/ChangeLog b/Source/JavaScriptCore/ChangeLog index bcd8e11..0ac4e3d3 100644 --- a/Source/JavaScriptCore/ChangeLog +++ b/Source/JavaScriptCore/ChangeLog @@ -1,3 +1,60 @@ +2016-04-26 Filip Pizlo + + DFG backends shouldn't emit type checks at KnownBlah edges + https://bugs.webkit.org/show_bug.cgi?id=157025 + + Reviewed by Michael Saboff. + + This fixes a crash I found when browsing Bing maps with forceEagerCompilation. I include a + 100% repro test case. + + The issue is that our code still doesn't fully appreciate the devious implications of + KnownBlah use kinds. Consider KnownCell for example. It means: "trust me, I know that this + value will be a cell". You aren't required to provide a proof when you use KnownCell. Often, + we use it as a result of a path-sensitive proof. The abstract interpreter is not + path-sensitive, so AI will be absolutely sure that the KnownCell use might see a non-cell. + This can lead to debug assertions (which this change removes) and it can lead to the backends + emitting a type check. That type check can be pure evil if the node that has this edge does + not have an exit origin. Such a node would have passed validation because the validater would + have thought that the node cannot exit (after all, according to the IR semantics, there is no + speculation at KnownCell). + + This comprehensively fixes the issue by recognizing that Foo(KnownCell:@x) means: I have + already proved that by the time you start executing Foo, @x will already be a cell. I cannot + tell you how I proved this but you can rely on it anyway. AI now takes advantage of this + meaning and will always do filtering of KnownBlah edges regardless of whether the backend + actually emits any type checks for those edges. Since the filtering runs before the backend, + the backend will not emit any checks because it will know that the edge was already checked + (by whatever mechanism we used when we made the edge KnownBlah). + + Note that it's good that we found this bug now. The DFG currently does very few + sparse-conditional or path-sensitive optimizations, but it will probably do more in the + future. The bug happens because GetByOffset and friends can achieve path-sensitive proofs via + watchpoints on the inferred type. Normally, AI can follow along with this proof. But in the + example program, and on Bing maps, we would GCSE one GetByOffset with another that had a + weaker proven type. That turned out to be completely sound - between the two GetByOffset's + there was a Branch to null check it. The inferred type of the second GetByOffset ended up + knowing that it cannot be null because null only occurred in some structures but not others. + If we added more sparse-conditional stuff to Branch, then AI would know how to follow along + with the proof but it would also create more situations where we'd have a path-sensitive + proof. So, it's good that we're now getting this right. + + * dfg/DFGAbstractInterpreter.h: + (JSC::DFG::AbstractInterpreter::filterEdgeByUse): + * dfg/DFGAbstractInterpreterInlines.h: + (JSC::DFG::AbstractInterpreter::executeEdges): + (JSC::DFG::AbstractInterpreter::executeKnownEdgeTypes): + (JSC::DFG::AbstractInterpreter::verifyEdge): + * dfg/DFGSpeculativeJIT.cpp: + (JSC::DFG::SpeculativeJIT::compileCurrentBlock): + * dfg/DFGUseKind.h: + (JSC::DFG::typeFilterFor): + * ftl/FTLLowerDFGToB3.cpp: + (JSC::FTL::DFG::LowerDFGToB3::compileNode): + * tests/stress/path-sensitive-known-cell-crash.js: Added. + (bar): + (foo): + 2016-04-26 Gavin Barraclough Enable separated heap by default on ios diff --git a/Source/JavaScriptCore/dfg/DFGAbstractInterpreter.h b/Source/JavaScriptCore/dfg/DFGAbstractInterpreter.h index e196917..f19bd24 100644 --- a/Source/JavaScriptCore/dfg/DFGAbstractInterpreter.h +++ b/Source/JavaScriptCore/dfg/DFGAbstractInterpreter.h @@ -1,5 +1,5 @@ /* - * Copyright (C) 2013-2015 Apple Inc. All rights reserved. + * Copyright (C) 2013-2016 Apple Inc. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions @@ -97,15 +97,12 @@ public: void executeEdges(Node*); void executeEdges(unsigned indexInBlock); + void executeKnownEdgeTypes(Node*); + ALWAYS_INLINE void filterEdgeByUse(Edge& edge) { - ASSERT(mayHaveTypeCheck(edge.useKind()) || !needsTypeCheck(edge)); filterByType(edge, typeFilterFor(edge.useKind())); } - ALWAYS_INLINE void filterEdgeByUse(Node*, Edge& edge) - { - filterEdgeByUse(edge); - } // Abstractly execute the effects of the given node. This changes the abstract // state assuming that edges have already been filtered. diff --git a/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h b/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h index 2982c47..53081b2 100644 --- a/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h +++ b/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h @@ -97,7 +97,11 @@ void AbstractInterpreter::startExecuting() template void AbstractInterpreter::executeEdges(Node* node) { - DFG_NODE_DO_TO_CHILDREN(m_graph, node, filterEdgeByUse); + m_graph.doToChildren( + node, + [&] (Edge& edge) { + filterEdgeByUse(edge); + }); } template @@ -107,14 +111,26 @@ void AbstractInterpreter::executeEdges(unsigned indexInBlock) } template -void AbstractInterpreter::verifyEdge(Node* node, Edge edge) +void AbstractInterpreter::executeKnownEdgeTypes(Node* node) { // Some use kinds are required to not have checks, because we know somehow that the incoming // value will already have the type we want. In those cases, AI may not be smart enough to - // prove that this is indeed the case. - if (shouldNotHaveTypeCheck(edge.useKind())) - return; - + // prove that this is indeed the case. But the existance of the edge is enough to prove that + // it is indeed the case. Taking advantage of this is not optional, since otherwise the DFG + // and FTL backends may emit checks in a node that lacks a valid exit origin. + m_graph.doToChildren( + node, + [&] (Edge& edge) { + if (mayHaveTypeCheck(edge.useKind())) + return; + + filterEdgeByUse(edge); + }); +} + +template +void AbstractInterpreter::verifyEdge(Node* node, Edge edge) +{ if (!(forNode(edge).m_type & ~typeFilterFor(edge.useKind()))) return; diff --git a/Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp b/Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp index 313e91a..f2f1c78 100644 --- a/Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp +++ b/Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp @@ -1611,6 +1611,7 @@ void SpeculativeJIT::compileCurrentBlock() } m_interpreter.startExecuting(); + m_interpreter.executeKnownEdgeTypes(m_currentNode); m_jit.setForNode(m_currentNode); m_origin = m_currentNode->origin; if (validationEnabled()) diff --git a/Source/JavaScriptCore/dfg/DFGUseKind.h b/Source/JavaScriptCore/dfg/DFGUseKind.h index b2c62c5..d2ef933 100644 --- a/Source/JavaScriptCore/dfg/DFGUseKind.h +++ b/Source/JavaScriptCore/dfg/DFGUseKind.h @@ -87,7 +87,7 @@ inline SpeculatedType typeFilterFor(UseKind useKind) { switch (useKind) { case UntypedUse: - return SpecFullTop; + return SpecBytecodeTop; case Int32Use: case KnownInt32Use: return SpecInt32Only; diff --git a/Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp b/Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp index 3f4d902..e320836 100644 --- a/Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp +++ b/Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp @@ -432,6 +432,7 @@ private: m_availableRecoveries.resize(0); m_interpreter.startExecuting(); + m_interpreter.executeKnownEdgeTypes(m_node); switch (m_node->op()) { case DFG::Upsilon: diff --git a/Source/JavaScriptCore/tests/stress/path-sensitive-known-cell-crash.js b/Source/JavaScriptCore/tests/stress/path-sensitive-known-cell-crash.js new file mode 100644 index 0000000..cc655f4 --- /dev/null +++ b/Source/JavaScriptCore/tests/stress/path-sensitive-known-cell-crash.js @@ -0,0 +1,21 @@ +function bar(o) { + if (o.f) + return o.f; + else + return {e:41, f:42}; +} + +function foo(o) { + var c = bar(o); + return c.f; +} + +noInline(foo); + +// Warm up foo with some different object types. +for (var i = 0; i < 10000; ++i) { + foo({f:{k:0, f:1}}); + foo({g:1, f:{l: -1, f:2, g:3}}); + foo({h:2, f:null}); +} + -- 1.8.3.1