<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[200096] trunk/Source/JavaScriptCore</title>
</head>
<body>
<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; }
#msg dl a { font-weight: bold}
#msg dl a:link { color:#fc3; }
#msg dl a:active { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/200096">200096</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2016-04-26 10:38:43 -0700 (Tue, 26 Apr 2016)</dd>
</dl>
<h3>Log Message</h3>
<pre>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):</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGAbstractInterpreterh">trunk/Source/JavaScriptCore/dfg/DFGAbstractInterpreter.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGAbstractInterpreterInlinesh">trunk/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGSpeculativeJITcpp">trunk/Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGUseKindh">trunk/Source/JavaScriptCore/dfg/DFGUseKind.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreftlFTLLowerDFGToB3cpp">trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoretestsstresspathsensitiveknowncellcrashjs">trunk/Source/JavaScriptCore/tests/stress/path-sensitive-known-cell-crash.js</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (200095 => 200096)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2016-04-26 17:28:54 UTC (rev 200095)
+++ trunk/Source/JavaScriptCore/ChangeLog 2016-04-26 17:38:43 UTC (rev 200096)
</span><span class="lines">@@ -1,3 +1,60 @@
</span><ins>+2016-04-26 Filip Pizlo <fpizlo@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):
+
</ins><span class="cx"> 2016-04-26 Gavin Barraclough <barraclough@apple.com>
</span><span class="cx">
</span><span class="cx"> Enable separated heap by default on ios
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGAbstractInterpreterh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGAbstractInterpreter.h (200095 => 200096)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGAbstractInterpreter.h 2016-04-26 17:28:54 UTC (rev 200095)
+++ trunk/Source/JavaScriptCore/dfg/DFGAbstractInterpreter.h 2016-04-26 17:38:43 UTC (rev 200096)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2013-2015 Apple Inc. All rights reserved.
</del><ins>+ * Copyright (C) 2013-2016 Apple Inc. All rights reserved.
</ins><span class="cx"> *
</span><span class="cx"> * Redistribution and use in source and binary forms, with or without
</span><span class="cx"> * modification, are permitted provided that the following conditions
</span><span class="lines">@@ -97,15 +97,12 @@
</span><span class="cx"> void executeEdges(Node*);
</span><span class="cx"> void executeEdges(unsigned indexInBlock);
</span><span class="cx">
</span><ins>+ void executeKnownEdgeTypes(Node*);
+
</ins><span class="cx"> ALWAYS_INLINE void filterEdgeByUse(Edge& edge)
</span><span class="cx"> {
</span><del>- ASSERT(mayHaveTypeCheck(edge.useKind()) || !needsTypeCheck(edge));
</del><span class="cx"> filterByType(edge, typeFilterFor(edge.useKind()));
</span><span class="cx"> }
</span><del>- ALWAYS_INLINE void filterEdgeByUse(Node*, Edge& edge)
- {
- filterEdgeByUse(edge);
- }
</del><span class="cx">
</span><span class="cx"> // Abstractly execute the effects of the given node. This changes the abstract
</span><span class="cx"> // state assuming that edges have already been filtered.
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGAbstractInterpreterInlinesh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h (200095 => 200096)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h 2016-04-26 17:28:54 UTC (rev 200095)
+++ trunk/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h 2016-04-26 17:38:43 UTC (rev 200096)
</span><span class="lines">@@ -97,7 +97,11 @@
</span><span class="cx"> template<typename AbstractStateType>
</span><span class="cx"> void AbstractInterpreter<AbstractStateType>::executeEdges(Node* node)
</span><span class="cx"> {
</span><del>- DFG_NODE_DO_TO_CHILDREN(m_graph, node, filterEdgeByUse);
</del><ins>+ m_graph.doToChildren(
+ node,
+ [&] (Edge& edge) {
+ filterEdgeByUse(edge);
+ });
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> template<typename AbstractStateType>
</span><span class="lines">@@ -107,14 +111,26 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> template<typename AbstractStateType>
</span><del>-void AbstractInterpreter<AbstractStateType>::verifyEdge(Node* node, Edge edge)
</del><ins>+void AbstractInterpreter<AbstractStateType>::executeKnownEdgeTypes(Node* node)
</ins><span class="cx"> {
</span><span class="cx"> // Some use kinds are required to not have checks, because we know somehow that the incoming
</span><span class="cx"> // value will already have the type we want. In those cases, AI may not be smart enough to
</span><del>- // prove that this is indeed the case.
- if (shouldNotHaveTypeCheck(edge.useKind()))
- return;
-
</del><ins>+ // 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)
+{
</ins><span class="cx"> if (!(forNode(edge).m_type & ~typeFilterFor(edge.useKind())))
</span><span class="cx"> return;
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGSpeculativeJITcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp (200095 => 200096)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp 2016-04-26 17:28:54 UTC (rev 200095)
+++ trunk/Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp 2016-04-26 17:38:43 UTC (rev 200096)
</span><span class="lines">@@ -1611,6 +1611,7 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> m_interpreter.startExecuting();
</span><ins>+ m_interpreter.executeKnownEdgeTypes(m_currentNode);
</ins><span class="cx"> m_jit.setForNode(m_currentNode);
</span><span class="cx"> m_origin = m_currentNode->origin;
</span><span class="cx"> if (validationEnabled())
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGUseKindh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGUseKind.h (200095 => 200096)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGUseKind.h 2016-04-26 17:28:54 UTC (rev 200095)
+++ trunk/Source/JavaScriptCore/dfg/DFGUseKind.h 2016-04-26 17:38:43 UTC (rev 200096)
</span><span class="lines">@@ -87,7 +87,7 @@
</span><span class="cx"> {
</span><span class="cx"> switch (useKind) {
</span><span class="cx"> case UntypedUse:
</span><del>- return SpecFullTop;
</del><ins>+ return SpecBytecodeTop;
</ins><span class="cx"> case Int32Use:
</span><span class="cx"> case KnownInt32Use:
</span><span class="cx"> return SpecInt32Only;
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreftlFTLLowerDFGToB3cpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp (200095 => 200096)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp 2016-04-26 17:28:54 UTC (rev 200095)
+++ trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp 2016-04-26 17:38:43 UTC (rev 200096)
</span><span class="lines">@@ -432,6 +432,7 @@
</span><span class="cx"> m_availableRecoveries.resize(0);
</span><span class="cx">
</span><span class="cx"> m_interpreter.startExecuting();
</span><ins>+ m_interpreter.executeKnownEdgeTypes(m_node);
</ins><span class="cx">
</span><span class="cx"> switch (m_node->op()) {
</span><span class="cx"> case DFG::Upsilon:
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoretestsstresspathsensitiveknowncellcrashjs"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/tests/stress/path-sensitive-known-cell-crash.js (0 => 200096)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/tests/stress/path-sensitive-known-cell-crash.js (rev 0)
+++ trunk/Source/JavaScriptCore/tests/stress/path-sensitive-known-cell-crash.js 2016-04-26 17:38:43 UTC (rev 200096)
</span><span class="lines">@@ -0,0 +1,21 @@
</span><ins>+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});
+}
+
</ins></span></pre>
</div>
</div>
</body>
</html>