<!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>[200468] 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/200468">200468</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2016-05-05 12:20:23 -0700 (Thu, 05 May 2016)</dd>
</dl>
<h3>Log Message</h3>
<pre>We shouldn't crash if DFG AI proved that something was unreachable on one run but then decided not to prove it on another run
https://bugs.webkit.org/show_bug.cgi?id=157379
Reviewed by Mark Lam.
Any run of DFG AI is a fixpoint that loosens the proof until it can't find any more
counterexamples to the proof. It errs on the side of loosening proofs, i.e., on the side of
proving fewer things.
We run this fixpoint multiple times since there are multiple points in the DFG optimization
pipeline when we run DFG AI. Each of those runs completes a fixpoint and produces the
tightest proof it can that did not result in counterexamples being found.
It's possible that on run K of DFG AI, we prove some property, but on run K+1, we don't prove
that property. The code could have changed between the two runs due to other phases. Other
phases may modify the code in such a way that it's less amenable to AI's analysis. Our design
allows this because DFG AI is not 100% precise. It defends itself from making unsound choices
or running forever by sometimes punting on proving some property. It must be able to do this,
and so therefore, it might sometimes prove fewer things on a later run.
Currently in trunk if the property that AI proves on run K but fails to prove on run K+1 is
the reachability of a piece of code, then run K+1 will crash on an assertion at the
Unreachable node. It will complain that it reached an Unreachable. But it might be reaching
that Unreachable because it failed to prove that something earlier was always exiting. That's
OK, see above.
So, we should remove the assertion that AI doesn't see Unreachable.
No new tests because I don't know how to make this happen. I believe that this happens in the
wild based on crash logs.
* dfg/DFGAbstractInterpreterInlines.h:
(JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGAbstractInterpreterInlinesh">trunk/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (200467 => 200468)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2016-05-05 19:01:40 UTC (rev 200467)
+++ trunk/Source/JavaScriptCore/ChangeLog 2016-05-05 19:20:23 UTC (rev 200468)
</span><span class="lines">@@ -1,3 +1,39 @@
</span><ins>+2016-05-05 Filip Pizlo <fpizlo@apple.com>
+
+ We shouldn't crash if DFG AI proved that something was unreachable on one run but then decided not to prove it on another run
+ https://bugs.webkit.org/show_bug.cgi?id=157379
+
+ Reviewed by Mark Lam.
+
+ Any run of DFG AI is a fixpoint that loosens the proof until it can't find any more
+ counterexamples to the proof. It errs on the side of loosening proofs, i.e., on the side of
+ proving fewer things.
+
+ We run this fixpoint multiple times since there are multiple points in the DFG optimization
+ pipeline when we run DFG AI. Each of those runs completes a fixpoint and produces the
+ tightest proof it can that did not result in counterexamples being found.
+
+ It's possible that on run K of DFG AI, we prove some property, but on run K+1, we don't prove
+ that property. The code could have changed between the two runs due to other phases. Other
+ phases may modify the code in such a way that it's less amenable to AI's analysis. Our design
+ allows this because DFG AI is not 100% precise. It defends itself from making unsound choices
+ or running forever by sometimes punting on proving some property. It must be able to do this,
+ and so therefore, it might sometimes prove fewer things on a later run.
+
+ Currently in trunk if the property that AI proves on run K but fails to prove on run K+1 is
+ the reachability of a piece of code, then run K+1 will crash on an assertion at the
+ Unreachable node. It will complain that it reached an Unreachable. But it might be reaching
+ that Unreachable because it failed to prove that something earlier was always exiting. That's
+ OK, see above.
+
+ So, we should remove the assertion that AI doesn't see Unreachable.
+
+ No new tests because I don't know how to make this happen. I believe that this happens in the
+ wild based on crash logs.
+
+ * dfg/DFGAbstractInterpreterInlines.h:
+ (JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
+
</ins><span class="cx"> 2016-05-05 Joseph Pecoraro <pecoraro@apple.com>
</span><span class="cx">
</span><span class="cx"> Crash if you type "debugger" in the console and continue
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGAbstractInterpreterInlinesh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h (200467 => 200468)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h 2016-05-05 19:01:40 UTC (rev 200467)
+++ trunk/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h 2016-05-05 19:20:23 UTC (rev 200468)
</span><span class="lines">@@ -2878,6 +2878,14 @@
</span><span class="cx"> break;
</span><span class="cx">
</span><span class="cx"> case Unreachable:
</span><ins>+ // It may be that during a previous run of AI we proved that something was unreachable, but
+ // during this run of AI we forget that it's unreachable. AI's proofs don't have to get
+ // monotonically stronger over time. So, we don't assert that AI doesn't reach the
+ // Unreachable. We have no choice but to take our past proof at face value. Otherwise we'll
+ // crash whenever AI fails to be as powerful on run K as it was on run K-1.
+ m_state.setIsValid(false);
+ break;
+
</ins><span class="cx"> case LastNodeType:
</span><span class="cx"> case ArithIMul:
</span><span class="cx"> case FiatInt52:
</span></span></pre>
</div>
</div>
</body>
</html>