<!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>[187347] 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/187347">187347</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2015-07-24 11:23:13 -0700 (Fri, 24 Jul 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>DFG::safeToExecute() is wrong for MultiGetByOffset, doesn't consider the structures of the prototypes that get loaded from
https://bugs.webkit.org/show_bug.cgi?id=147250
Reviewed by Geoffrey Garen.
This fixes a nasty - but currently benign - bug in DFG::safeToExecute(). That function
will tell you if hoisting a node to some point is safe in the sense that the node will
not crash the VM if it executes at that point. A node may be unsafe to execute if we
cannot prove that at that point, the memory it is loading is not garbage. This is a
necessarily loose notion - for example it's OK to hoist a load if we haven't proved
that the load makes semantic sense at that point, since anyway the place where the node
did get used will still be guarded by any such semantic checks. But because we may also
hoist uses of the load, we need to make sure that it doesn't produce a garbage value.
Also, we need to ensure that the load won't trap. Hence safeToExecute() returns true
anytime we can be sure that a node will not produce a garbage result (i.e. a malformed
JSValue or object pointer) and will not trap when executed at the point in question.
The bug is that this verification isn't performed for the loads from prototypes inside
MultiGetByOffset. DFG::ByteCodeParser will guard MultiGetByOffset with CheckStructure's
on the prototypes. So, hypothetically, you might end up hoisting a MultiGetByOffset
above those structure checks, which would mean that we might load a value from a memory
location without knowing that the location is valid. It might then return the value
loaded.
This never happens in practice. Those structure checks are more hoistable that the
MultiGetByOffset, since they read a strict subset of the MultiGetByOffset's abstract
heap reads. Also, we hoist in program order. So, those CheckStructure's will always be
hoisted before the MultiGetByOffset gets hoisted.
But we should fix this anyway. DFG::safeToExecute() has a clear definition of what a
"true" return means for IR transformations, and it fails in satisfying that definition
for MultiGetByOffset.
There are various approaches we can use for making this safe. I considered two:
1) Have MultiGetByOffset refer to the prototypes it is loading from in IR, so that we
can check if it's safe to load from them.
2) Turn off MultiGetByOffset hoisting when it will emit loads from prototypes, and the
prototype structure isn't being watched.
I ended up using (2), because it will be the most natural solution once I finish
https://bugs.webkit.org/show_bug.cgi?id=146929. Already now, it's somewhat more natural
than (1) since that requires more extensive IR changes. Also, (2) will give us what we
want in *most* cases: we will usually watch the prototype structure, and we will
usually constant-fold loads from prototypes. Both of these usually-true things would
have to become false for MultiGetByOffset hoisting to be disabled by this change.
This change also adds my attempt at a test, though it's not really a test of this bug.
This bug is currently benign. But, the test does at least trigger the logic to run,
which is better than nothing.
* dfg/DFGSafeToExecute.h:
(JSC::DFG::safeToExecute):
* tests/stress/multi-get-by-offset-hoist-around-structure-check.js: Added.
(foo):</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGSafeToExecuteh">trunk/Source/JavaScriptCore/dfg/DFGSafeToExecute.h</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoretestsstressmultigetbyoffsethoistaroundstructurecheckjs">trunk/Source/JavaScriptCore/tests/stress/multi-get-by-offset-hoist-around-structure-check.js</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (187346 => 187347)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2015-07-24 17:59:51 UTC (rev 187346)
+++ trunk/Source/JavaScriptCore/ChangeLog 2015-07-24 18:23:13 UTC (rev 187347)
</span><span class="lines">@@ -1,3 +1,62 @@
</span><ins>+2015-07-23 Filip Pizlo <fpizlo@apple.com>
+
+ DFG::safeToExecute() is wrong for MultiGetByOffset, doesn't consider the structures of the prototypes that get loaded from
+ https://bugs.webkit.org/show_bug.cgi?id=147250
+
+ Reviewed by Geoffrey Garen.
+
+ This fixes a nasty - but currently benign - bug in DFG::safeToExecute(). That function
+ will tell you if hoisting a node to some point is safe in the sense that the node will
+ not crash the VM if it executes at that point. A node may be unsafe to execute if we
+ cannot prove that at that point, the memory it is loading is not garbage. This is a
+ necessarily loose notion - for example it's OK to hoist a load if we haven't proved
+ that the load makes semantic sense at that point, since anyway the place where the node
+ did get used will still be guarded by any such semantic checks. But because we may also
+ hoist uses of the load, we need to make sure that it doesn't produce a garbage value.
+ Also, we need to ensure that the load won't trap. Hence safeToExecute() returns true
+ anytime we can be sure that a node will not produce a garbage result (i.e. a malformed
+ JSValue or object pointer) and will not trap when executed at the point in question.
+
+ The bug is that this verification isn't performed for the loads from prototypes inside
+ MultiGetByOffset. DFG::ByteCodeParser will guard MultiGetByOffset with CheckStructure's
+ on the prototypes. So, hypothetically, you might end up hoisting a MultiGetByOffset
+ above those structure checks, which would mean that we might load a value from a memory
+ location without knowing that the location is valid. It might then return the value
+ loaded.
+
+ This never happens in practice. Those structure checks are more hoistable that the
+ MultiGetByOffset, since they read a strict subset of the MultiGetByOffset's abstract
+ heap reads. Also, we hoist in program order. So, those CheckStructure's will always be
+ hoisted before the MultiGetByOffset gets hoisted.
+
+ But we should fix this anyway. DFG::safeToExecute() has a clear definition of what a
+ "true" return means for IR transformations, and it fails in satisfying that definition
+ for MultiGetByOffset.
+
+ There are various approaches we can use for making this safe. I considered two:
+
+ 1) Have MultiGetByOffset refer to the prototypes it is loading from in IR, so that we
+ can check if it's safe to load from them.
+
+ 2) Turn off MultiGetByOffset hoisting when it will emit loads from prototypes, and the
+ prototype structure isn't being watched.
+
+ I ended up using (2), because it will be the most natural solution once I finish
+ https://bugs.webkit.org/show_bug.cgi?id=146929. Already now, it's somewhat more natural
+ than (1) since that requires more extensive IR changes. Also, (2) will give us what we
+ want in *most* cases: we will usually watch the prototype structure, and we will
+ usually constant-fold loads from prototypes. Both of these usually-true things would
+ have to become false for MultiGetByOffset hoisting to be disabled by this change.
+
+ This change also adds my attempt at a test, though it's not really a test of this bug.
+ This bug is currently benign. But, the test does at least trigger the logic to run,
+ which is better than nothing.
+
+ * dfg/DFGSafeToExecute.h:
+ (JSC::DFG::safeToExecute):
+ * tests/stress/multi-get-by-offset-hoist-around-structure-check.js: Added.
+ (foo):
+
</ins><span class="cx"> 2015-07-23 Sukolsak Sakshuwong <sukolsak@gmail.com>
</span><span class="cx">
</span><span class="cx"> Implement WebAssembly modules
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGSafeToExecuteh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGSafeToExecute.h (187346 => 187347)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGSafeToExecute.h 2015-07-24 17:59:51 UTC (rev 187346)
+++ trunk/Source/JavaScriptCore/dfg/DFGSafeToExecute.h 2015-07-24 18:23:13 UTC (rev 187347)
</span><span class="lines">@@ -99,8 +99,15 @@
</span><span class="cx">
</span><span class="cx"> // Determines if it's safe to execute a node within the given abstract state. This may
</span><span class="cx"> // return false conservatively. If it returns true, then you can hoist the given node
</span><del>-// up to the given point and expect that it will not crash. This doesn't guarantee that
-// the node will produce the result you wanted other than not crashing.
</del><ins>+// up to the given point and expect that it will not crash. It also guarantees that the
+// node will not produce a malformed JSValue or object pointer when executed in the
+// given state. But this doesn't guarantee that the node will produce the result you
+// wanted. For example, you may have a GetByOffset from a prototype that only makes
+// semantic sense if you've also checked that some nearer prototype doesn't also have
+// a property of the same name. This could still return true even if that check hadn't
+// been performed in the given abstract state. That's fine though: the load can still
+// safely execute before that check, so long as that check continues to guard any
+// user-observable things done to the loaded value.
</ins><span class="cx"> template<typename AbstractStateType>
</span><span class="cx"> bool safeToExecute(AbstractStateType& state, Graph& graph, Node* node)
</span><span class="cx"> {
</span><span class="lines">@@ -255,7 +262,6 @@
</span><span class="cx"> case CheckInBounds:
</span><span class="cx"> case ConstantStoragePointer:
</span><span class="cx"> case Check:
</span><del>- case MultiGetByOffset:
</del><span class="cx"> case MultiPutByOffset:
</span><span class="cx"> case ValueRep:
</span><span class="cx"> case DoubleRep:
</span><span class="lines">@@ -333,6 +339,48 @@
</span><span class="cx"> return true;
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ case MultiGetByOffset: {
+ // We can't always guarantee that the MultiGetByOffset is safe to execute if it
+ // contains loads from prototypes. We know that it won't load from those prototypes if
+ // we watch the mutability of the properties being loaded. So, here we try to
+ // constant-fold prototype loads, and if that fails, we claim that we cannot hoist. We
+ // also know that a load is safe to execute if we are watching the prototype's
+ // structure.
+ for (const GetByIdVariant& variant : node->multiGetByOffsetData().variants) {
+ if (!variant.alternateBase()) {
+ // It's not a prototype load.
+ continue;
+ }
+
+ JSValue base = variant.alternateBase();
+ FrozenValue* frozen = graph.freeze(base);
+ if (state.structureClobberState() == StructuresAreWatched
+ && frozen->structure()->dfgShouldWatch()
+ && frozen->structure()->isValidOffset(variant.offset())) {
+ // We're already watching that it's safe to load from this.
+ continue;
+ }
+
+ JSValue constantResult = graph.tryGetConstantProperty(
+ variant.alternateBase(), variant.baseStructure(), variant.offset());
+ if (!constantResult) {
+ // Couldn't constant-fold a prototype load. Therefore, we shouldn't hoist
+ // because the safety of the load depends on structure checks on the prototype,
+ // and we're too cheap to verify that here.
+ return false;
+ }
+
+ // Otherwise, we will either:
+ // - Not load from the prototype because constant folding will succeed in the
+ // backend, or
+ // - Emit invalid code that fails watchpoint checks. This could happen if the
+ // property becomes mutable after this point, since we already set the watchpoint
+ // above. This case is OK since the code will fail watchpoint checks and never
+ // get installed.
+ }
+ return true;
+ }
+
</ins><span class="cx"> case LastNodeType:
</span><span class="cx"> RELEASE_ASSERT_NOT_REACHED();
</span><span class="cx"> return false;
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoretestsstressmultigetbyoffsethoistaroundstructurecheckjs"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/tests/stress/multi-get-by-offset-hoist-around-structure-check.js (0 => 187347)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/tests/stress/multi-get-by-offset-hoist-around-structure-check.js (rev 0)
+++ trunk/Source/JavaScriptCore/tests/stress/multi-get-by-offset-hoist-around-structure-check.js 2015-07-24 18:23:13 UTC (rev 187347)
</span><span class="lines">@@ -0,0 +1,30 @@
</span><ins>+function foo(o, start) {
+ var result = 0;
+ for (var i = 0; i < 100; ++i)
+ result += o.f;
+ return result;
+}
+
+noInline(foo);
+
+var o = {};
+o.f = 42;
+var f = {};
+f.f = 43;
+f.g = 44;
+
+for (var i = 0; i < 10000; ++i)
+ o.f = i;
+o.f = 42;
+
+for (var i = 0; i < 10000; ++i) {
+ var p;
+ if (i & 1)
+ p = o;
+ else
+ p = Object.create(o);
+ var result = foo(p);
+ if (result != 100 * 42)
+ throw "Error: bad result: " + result;
+}
+
</ins></span></pre>
</div>
</div>
</body>
</html>