<!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>[200645] 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/200645">200645</a></dd>
<dt>Author</dt> <dd>commit-queue@webkit.org</dd>
<dt>Date</dt> <dd>2016-05-10 14:35:32 -0700 (Tue, 10 May 2016)</dd>
</dl>
<h3>Log Message</h3>
<pre>[JSC] FTL can produce GetByVal nodes without proper bounds checking
https://bugs.webkit.org/show_bug.cgi?id=157502
rdar://problem/26027027
Patch by Benjamin Poulain <bpoulain@apple.com> on 2016-05-10
Reviewed by Filip Pizlo.
It was possible for FTL to generates GetByVal on arbitrary offsets
without any bounds checking.
The bug is caused by the order of optimization phases:
-First, the Integer Range Optimization proves that a CheckInBounds
test can never fail.
This proof is based on control flow or preceeding instructions
inside a loop.
-The Loop Invariant Code Motion phase finds that the GetByVal does not
depend on anything in the loop and hoist it out of the loop.
-> As a result, the conditions that were necessary to eliminate
the CheckInBounds are no longer met before the GetByVal.
This patch just moves the Integer Range Optimization phase after
Loop Invariant Code Motion to make sure no code is moved after
its integer ranges bounds proofs have been used.
* dfg/DFGPlan.cpp:
(JSC::DFG::Plan::compileInThreadImpl):
* tests/stress/bounds-check-not-eliminated-by-licm.js: Added.
(testInLoopTests):</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGPlancpp">trunk/Source/JavaScriptCore/dfg/DFGPlan.cpp</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoretestsstressboundschecknoteliminatedbylicmjs">trunk/Source/JavaScriptCore/tests/stress/bounds-check-not-eliminated-by-licm.js</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (200644 => 200645)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2016-05-10 21:30:09 UTC (rev 200644)
+++ trunk/Source/JavaScriptCore/ChangeLog 2016-05-10 21:35:32 UTC (rev 200645)
</span><span class="lines">@@ -1,3 +1,33 @@
</span><ins>+2016-05-10 Benjamin Poulain <bpoulain@apple.com>
+
+ [JSC] FTL can produce GetByVal nodes without proper bounds checking
+ https://bugs.webkit.org/show_bug.cgi?id=157502
+ rdar://problem/26027027
+
+ Reviewed by Filip Pizlo.
+
+ It was possible for FTL to generates GetByVal on arbitrary offsets
+ without any bounds checking.
+
+ The bug is caused by the order of optimization phases:
+ -First, the Integer Range Optimization proves that a CheckInBounds
+ test can never fail.
+ This proof is based on control flow or preceeding instructions
+ inside a loop.
+ -The Loop Invariant Code Motion phase finds that the GetByVal does not
+ depend on anything in the loop and hoist it out of the loop.
+ -> As a result, the conditions that were necessary to eliminate
+ the CheckInBounds are no longer met before the GetByVal.
+
+ This patch just moves the Integer Range Optimization phase after
+ Loop Invariant Code Motion to make sure no code is moved after
+ its integer ranges bounds proofs have been used.
+
+ * dfg/DFGPlan.cpp:
+ (JSC::DFG::Plan::compileInThreadImpl):
+ * tests/stress/bounds-check-not-eliminated-by-licm.js: Added.
+ (testInLoopTests):
+
</ins><span class="cx"> 2016-05-10 Joseph Pecoraro <pecoraro@apple.com>
</span><span class="cx">
</span><span class="cx"> Web Inspector: Eliminate the crazy code for evaluateOnCallFrame
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGPlancpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGPlan.cpp (200644 => 200645)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGPlan.cpp 2016-05-10 21:30:09 UTC (rev 200644)
+++ trunk/Source/JavaScriptCore/dfg/DFGPlan.cpp 2016-05-10 21:35:32 UTC (rev 200645)
</span><span class="lines">@@ -399,8 +399,6 @@
</span><span class="cx"> performConstantHoisting(dfg);
</span><span class="cx"> performGlobalCSE(dfg);
</span><span class="cx"> performLivenessAnalysis(dfg);
</span><del>- performIntegerRangeOptimization(dfg);
- performLivenessAnalysis(dfg);
</del><span class="cx"> performCFA(dfg);
</span><span class="cx"> performConstantFolding(dfg);
</span><span class="cx"> performCleanUp(dfg); // Reduce the graph size a lot.
</span><span class="lines">@@ -424,6 +422,16 @@
</span><span class="cx"> // Alternatively, we could run loop pre-header creation after SSA conversion - but if we did that
</span><span class="cx"> // then we'd need to do some simple SSA fix-up.
</span><span class="cx"> performLICM(dfg);
</span><ins>+
+ // FIXME: Currently: IntegerRangeOptimization *must* be run after LICM.
+ //
+ // IntegerRangeOptimization makes changes on nodes based on preceding blocks
+ // and nodes. LICM moves nodes which can invalidates assumptions used
+ // by IntegerRangeOptimization.
+ //
+ // Ideally, the dependencies should be explicit. See https://bugs.webkit.org/show_bug.cgi?id=157534.
+ performLivenessAnalysis(dfg);
+ performIntegerRangeOptimization(dfg);
</ins><span class="cx">
</span><span class="cx"> performCleanUp(dfg);
</span><span class="cx"> performIntegerCheckCombining(dfg);
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoretestsstressboundschecknoteliminatedbylicmjs"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/tests/stress/bounds-check-not-eliminated-by-licm.js (0 => 200645)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/tests/stress/bounds-check-not-eliminated-by-licm.js (rev 0)
+++ trunk/Source/JavaScriptCore/tests/stress/bounds-check-not-eliminated-by-licm.js 2016-05-10 21:35:32 UTC (rev 200645)
</span><span class="lines">@@ -0,0 +1,30 @@
</span><ins>+function testInLoopTests(array, index)
+{
+ let arrayLength = array.length;
+ let sum = 0;
+ for (let i = 0; i < 10; ++i) {
+ if (index >= 0 && index < arrayLength) {
+ sum += array[index];
+ }
+ }
+ return sum;
+}
+noInline(testInLoopTests);
+
+
+let testArray = [1, 2, 3];
+
+// Warmup "in-bounds" up to FTL.
+for (let i = 0; i < 1e5; ++i) {
+ if (testInLoopTests(testArray, 1) !== 20)
+ throw "Failed testInLoopTests(testArray, 1)"
+ if (testInLoopTests(testArray, 2) !== 30)
+ throw "Failed testInLoopTests(testArray, 2)"
+}
+
+let largeIntResult = testInLoopTests(testArray, 2147483647);
+if (largeIntResult !== 0)
+ throw "Failed testInLoopTests(testArray, 2147483647)";
+let smallIntResult = testInLoopTests(testArray, -2147483647);
+if (smallIntResult !== 0)
+ throw "Failed testInLoopTests(testArray, -2147483647)";
</ins></span></pre>
</div>
</div>
</body>
</html>