- Revision
- 200096
- Author
- fpi...@apple.com
- Date
- 2016-04-26 10:38:43 -0700 (Tue, 26 Apr 2016)
Log Message
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<AbstractStateType>::executeEdges):
(JSC::DFG::AbstractInterpreter<AbstractStateType>::executeKnownEdgeTypes):
(JSC::DFG::AbstractInterpreter<AbstractStateType>::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):
Modified Paths
Added Paths
Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (200095 => 200096)
--- trunk/Source/_javascript_Core/ChangeLog 2016-04-26 17:28:54 UTC (rev 200095)
+++ trunk/Source/_javascript_Core/ChangeLog 2016-04-26 17:38:43 UTC (rev 200096)
@@ -1,3 +1,60 @@
+2016-04-26 Filip Pizlo <fpi...@apple.com>
+
+ 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<AbstractStateType>::executeEdges):
+ (JSC::DFG::AbstractInterpreter<AbstractStateType>::executeKnownEdgeTypes):
+ (JSC::DFG::AbstractInterpreter<AbstractStateType>::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 <barraclo...@apple.com>
Enable separated heap by default on ios
Modified: trunk/Source/_javascript_Core/dfg/DFGAbstractInterpreter.h (200095 => 200096)
--- trunk/Source/_javascript_Core/dfg/DFGAbstractInterpreter.h 2016-04-26 17:28:54 UTC (rev 200095)
+++ trunk/Source/_javascript_Core/dfg/DFGAbstractInterpreter.h 2016-04-26 17:38:43 UTC (rev 200096)
@@ -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 @@
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.
Modified: trunk/Source/_javascript_Core/dfg/DFGAbstractInterpreterInlines.h (200095 => 200096)
--- trunk/Source/_javascript_Core/dfg/DFGAbstractInterpreterInlines.h 2016-04-26 17:28:54 UTC (rev 200095)
+++ trunk/Source/_javascript_Core/dfg/DFGAbstractInterpreterInlines.h 2016-04-26 17:38:43 UTC (rev 200096)
@@ -97,7 +97,11 @@
template<typename AbstractStateType>
void AbstractInterpreter<AbstractStateType>::executeEdges(Node* node)
{
- DFG_NODE_DO_TO_CHILDREN(m_graph, node, filterEdgeByUse);
+ m_graph.doToChildren(
+ node,
+ [&] (Edge& edge) {
+ filterEdgeByUse(edge);
+ });
}
template<typename AbstractStateType>
@@ -107,14 +111,26 @@
}
template<typename AbstractStateType>
-void AbstractInterpreter<AbstractStateType>::verifyEdge(Node* node, Edge edge)
+void AbstractInterpreter<AbstractStateType>::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<typename AbstractStateType>
+void AbstractInterpreter<AbstractStateType>::verifyEdge(Node* node, Edge edge)
+{
if (!(forNode(edge).m_type & ~typeFilterFor(edge.useKind())))
return;
Modified: trunk/Source/_javascript_Core/dfg/DFGSpeculativeJIT.cpp (200095 => 200096)
--- trunk/Source/_javascript_Core/dfg/DFGSpeculativeJIT.cpp 2016-04-26 17:28:54 UTC (rev 200095)
+++ trunk/Source/_javascript_Core/dfg/DFGSpeculativeJIT.cpp 2016-04-26 17:38:43 UTC (rev 200096)
@@ -1611,6 +1611,7 @@
}
m_interpreter.startExecuting();
+ m_interpreter.executeKnownEdgeTypes(m_currentNode);
m_jit.setForNode(m_currentNode);
m_origin = m_currentNode->origin;
if (validationEnabled())
Modified: trunk/Source/_javascript_Core/dfg/DFGUseKind.h (200095 => 200096)
--- trunk/Source/_javascript_Core/dfg/DFGUseKind.h 2016-04-26 17:28:54 UTC (rev 200095)
+++ trunk/Source/_javascript_Core/dfg/DFGUseKind.h 2016-04-26 17:38:43 UTC (rev 200096)
@@ -87,7 +87,7 @@
{
switch (useKind) {
case UntypedUse:
- return SpecFullTop;
+ return SpecBytecodeTop;
case Int32Use:
case KnownInt32Use:
return SpecInt32Only;
Modified: trunk/Source/_javascript_Core/ftl/FTLLowerDFGToB3.cpp (200095 => 200096)
--- trunk/Source/_javascript_Core/ftl/FTLLowerDFGToB3.cpp 2016-04-26 17:28:54 UTC (rev 200095)
+++ trunk/Source/_javascript_Core/ftl/FTLLowerDFGToB3.cpp 2016-04-26 17:38:43 UTC (rev 200096)
@@ -432,6 +432,7 @@
m_availableRecoveries.resize(0);
m_interpreter.startExecuting();
+ m_interpreter.executeKnownEdgeTypes(m_node);
switch (m_node->op()) {
case DFG::Upsilon:
Added: trunk/Source/_javascript_Core/tests/stress/path-sensitive-known-cell-crash.js (0 => 200096)
--- trunk/Source/_javascript_Core/tests/stress/path-sensitive-known-cell-crash.js (rev 0)
+++ trunk/Source/_javascript_Core/tests/stress/path-sensitive-known-cell-crash.js 2016-04-26 17:38:43 UTC (rev 200096)
@@ -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});
+}
+
