<!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>[201182] trunk</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/201182">201182</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2016-05-19 14:25:29 -0700 (Thu, 19 May 2016)</dd>
</dl>
<h3>Log Message</h3>
<pre>DFG::LICMPhase shouldn't hoist type checks unless it knows that the check will succeed at the loop pre-header
https://bugs.webkit.org/show_bug.cgi?id=144527
Reviewed by Saam Barati.
Source/JavaScriptCore:
This adds a control flow equivalence analysis (called ControlEquivalenceAnalysis) based on
dominator analysis over the backwards CFG. Two basic blocks are control flow equivalent if
the execution of one implies that the other one must also execute. It means that the two
blocks' forward and backward dominance are reciprocated: (A dom B and B backdom A) or (B dom
A and A backdom B). LICM now uses it to become more conservative about hoisting checks, if
this has caused problems in the past. If we hoist something that may exit from a block that
was not control equivalent to the pre-header then it's possible that the node's speculation
will fail even though it wouldn't have if it wasn't hoisted. So, we flag these nodes'
origins as being "wasHoisted" and we track all of their exits as "HoistingFailed". LICM will
turn off such speculative hoisting if the CodeBlock from which we are hoisting had the
HoistingFailed exit kind.
Note that this deliberately still allows us to hoist things that may exit even if they are
not control equivalent to the pre-header. This is necessary because the profitability of
hoisting is so huge in all of the cases that we're aware of that it's worth giving it a
shot.
This is neutral on macrobenchmarks since none of the benchmarks we track have a hoistable
operation that would exit only if hoisted. I added microbenchmarks to illustrate the problem
and two of them speed up by ~40% while one of them is neutral (Int52 saves us from having
problems on that program even though LICM previously did the wrong thing).
* JavaScriptCore.xcodeproj/project.pbxproj:
* bytecode/ExitKind.cpp:
(JSC::exitKindToString):
* bytecode/ExitKind.h:
* dfg/DFGAtTailAbstractState.h:
(JSC::DFG::AtTailAbstractState::operator bool):
(JSC::DFG::AtTailAbstractState::initializeTo):
* dfg/DFGBackwardsCFG.h: Added.
(JSC::DFG::BackwardsCFG::BackwardsCFG):
* dfg/DFGBackwardsDominators.h: Added.
(JSC::DFG::BackwardsDominators::BackwardsDominators):
* dfg/DFGCommon.h:
(JSC::DFG::checkAndSet): Deleted.
* dfg/DFGControlEquivalenceAnalysis.h: Added.
(JSC::DFG::ControlEquivalenceAnalysis::ControlEquivalenceAnalysis):
(JSC::DFG::ControlEquivalenceAnalysis::dominatesEquivalently):
(JSC::DFG::ControlEquivalenceAnalysis::areEquivalent):
* dfg/DFGGraph.cpp:
(JSC::DFG::Graph::dump):
(JSC::DFG::Graph::dumpBlockHeader):
(JSC::DFG::Graph::invalidateCFG):
(JSC::DFG::Graph::substituteGetLocal):
(JSC::DFG::Graph::handleAssertionFailure):
(JSC::DFG::Graph::ensureDominators):
(JSC::DFG::Graph::ensurePrePostNumbering):
(JSC::DFG::Graph::ensureNaturalLoops):
(JSC::DFG::Graph::ensureBackwardsCFG):
(JSC::DFG::Graph::ensureBackwardsDominators):
(JSC::DFG::Graph::ensureControlEquivalenceAnalysis):
(JSC::DFG::Graph::methodOfGettingAValueProfileFor):
* dfg/DFGGraph.h:
(JSC::DFG::Graph::hasDebuggerEnabled):
* dfg/DFGInPlaceAbstractState.h:
(JSC::DFG::InPlaceAbstractState::operator bool):
(JSC::DFG::InPlaceAbstractState::createValueForNode):
(JSC::DFG::InPlaceAbstractState::forNode):
* dfg/DFGLICMPhase.cpp:
(JSC::DFG::LICMPhase::run):
(JSC::DFG::LICMPhase::attemptHoist):
* dfg/DFGMayExit.cpp:
(JSC::DFG::mayExit):
* dfg/DFGMayExit.h:
* dfg/DFGNode.h:
* dfg/DFGNodeOrigin.cpp:
(JSC::DFG::NodeOrigin::dump):
* dfg/DFGNodeOrigin.h:
(JSC::DFG::NodeOrigin::takeValidExit):
(JSC::DFG::NodeOrigin::withWasHoisted):
(JSC::DFG::NodeOrigin::forInsertingAfter):
* dfg/DFGNullAbstractState.h: Added.
(JSC::DFG::NullAbstractState::NullAbstractState):
(JSC::DFG::NullAbstractState::operator bool):
(JSC::DFG::NullAbstractState::forNode):
* dfg/DFGOSRExit.cpp:
(JSC::DFG::OSRExit::OSRExit):
* dfg/DFGOSRExitBase.cpp:
(JSC::DFG::OSRExitBase::considerAddingAsFrequentExitSiteSlow):
* dfg/DFGOSRExitBase.h:
(JSC::DFG::OSRExitBase::OSRExitBase):
* dfg/DFGTypeCheckHoistingPhase.cpp:
(JSC::DFG::TypeCheckHoistingPhase::run):
* ftl/FTLOSRExit.cpp:
(JSC::FTL::OSRExitDescriptor::prepareOSRExitHandle):
(JSC::FTL::OSRExit::OSRExit):
* ftl/FTLOSRExit.h:
Source/WTF:
This adds an adaptor for graphs called BackwardsGraph. The WTF graph framework is based on
passing around a Graph template argument that follows the protocol shared by DFG::CFG,
B3::CFG, and Air::CFG. These graphs always have a single root node but may have many leaf
nodes. This new BackwardsGraph adaptor reverses the graph by creating a synthetic return
node that it uses as the root in the inverted graph. This currently may resort to some
heuristics in programs that have an infinite loop, but other than that, it'll work well in
the general case.
This allows us to say Dominators<BackwardsGraph<some graph type>> as a way of computing
backwards dominators, which then allows us to easily answer control flow equivalence
queries.
* CMakeLists.txt:
* WTF.xcodeproj/project.pbxproj:
* wtf/BackwardsGraph.h: Added.
(WTF::BackwardsGraph::Node::Node):
(WTF::BackwardsGraph::Node::root):
(WTF::BackwardsGraph::Node::operator==):
(WTF::BackwardsGraph::Node::operator!=):
(WTF::BackwardsGraph::Node::operator bool):
(WTF::BackwardsGraph::Node::isRoot):
(WTF::BackwardsGraph::Node::node):
(WTF::BackwardsGraph::Set::Set):
(WTF::BackwardsGraph::Set::add):
(WTF::BackwardsGraph::Set::remove):
(WTF::BackwardsGraph::Set::contains):
(WTF::BackwardsGraph::Set::dump):
(WTF::BackwardsGraph::Map::Map):
(WTF::BackwardsGraph::Map::clear):
(WTF::BackwardsGraph::Map::size):
(WTF::BackwardsGraph::Map::operator[]):
(WTF::BackwardsGraph::BackwardsGraph):
(WTF::BackwardsGraph::root):
(WTF::BackwardsGraph::newMap):
(WTF::BackwardsGraph::successors):
(WTF::BackwardsGraph::predecessors):
(WTF::BackwardsGraph::index):
(WTF::BackwardsGraph::node):
(WTF::BackwardsGraph::numNodes):
(WTF::BackwardsGraph::dump):
* wtf/Dominators.h:
(WTF::Dominators::Dominators):
(WTF::Dominators::dump):
(WTF::Dominators::LengauerTarjan::computeDepthFirstPreNumbering):
* wtf/GraphNodeWorklist.h:
(WTF::GraphNodeWith::GraphNodeWith):
(WTF::GraphNodeWith::operator bool):
* wtf/StdLibExtras.h:
(WTF::callStatelessLambda):
(WTF::checkAndSet):
LayoutTests:
Add tests for LICM hoisting things that would only exit if hoisted.
* js/regress/licm-dragons-expected.txt: Added.
* js/regress/licm-dragons-out-of-bounds-expected.txt: Added.
* js/regress/licm-dragons-out-of-bounds.html: Added.
* js/regress/licm-dragons-overflow-expected.txt: Added.
* js/regress/licm-dragons-overflow.html: Added.
* js/regress/licm-dragons.html: Added.
* js/regress/script-tests/licm-dragons-out-of-bounds.js: Added.
(foo):
* js/regress/script-tests/licm-dragons-overflow.js: Added.
(foo):
* js/regress/script-tests/licm-dragons.js: Added.
(foo):</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkLayoutTestsChangeLog">trunk/LayoutTests/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoreJavaScriptCorexcodeprojprojectpbxproj">trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj</a></li>
<li><a href="#trunkSourceJavaScriptCorebytecodeExitKindcpp">trunk/Source/JavaScriptCore/bytecode/ExitKind.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCorebytecodeExitKindh">trunk/Source/JavaScriptCore/bytecode/ExitKind.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGAtTailAbstractStateh">trunk/Source/JavaScriptCore/dfg/DFGAtTailAbstractState.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGCommonh">trunk/Source/JavaScriptCore/dfg/DFGCommon.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGGraphcpp">trunk/Source/JavaScriptCore/dfg/DFGGraph.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGGraphh">trunk/Source/JavaScriptCore/dfg/DFGGraph.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGInPlaceAbstractStateh">trunk/Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGLICMPhasecpp">trunk/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGMayExitcpp">trunk/Source/JavaScriptCore/dfg/DFGMayExit.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGMayExith">trunk/Source/JavaScriptCore/dfg/DFGMayExit.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGNodeh">trunk/Source/JavaScriptCore/dfg/DFGNode.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGNodeOrigincpp">trunk/Source/JavaScriptCore/dfg/DFGNodeOrigin.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGNodeOriginh">trunk/Source/JavaScriptCore/dfg/DFGNodeOrigin.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGOSRExitcpp">trunk/Source/JavaScriptCore/dfg/DFGOSRExit.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGOSRExitBasecpp">trunk/Source/JavaScriptCore/dfg/DFGOSRExitBase.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGOSRExitBaseh">trunk/Source/JavaScriptCore/dfg/DFGOSRExitBase.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGTypeCheckHoistingPhasecpp">trunk/Source/JavaScriptCore/dfg/DFGTypeCheckHoistingPhase.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreftlFTLOSRExitcpp">trunk/Source/JavaScriptCore/ftl/FTLOSRExit.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreftlFTLOSRExith">trunk/Source/JavaScriptCore/ftl/FTLOSRExit.h</a></li>
<li><a href="#trunkSourceWTFChangeLog">trunk/Source/WTF/ChangeLog</a></li>
<li><a href="#trunkSourceWTFWTFxcodeprojprojectpbxproj">trunk/Source/WTF/WTF.xcodeproj/project.pbxproj</a></li>
<li><a href="#trunkSourceWTFwtfCMakeListstxt">trunk/Source/WTF/wtf/CMakeLists.txt</a></li>
<li><a href="#trunkSourceWTFwtfDominatorsh">trunk/Source/WTF/wtf/Dominators.h</a></li>
<li><a href="#trunkSourceWTFwtfGraphNodeWorklisth">trunk/Source/WTF/wtf/GraphNodeWorklist.h</a></li>
<li><a href="#trunkSourceWTFwtfStdLibExtrash">trunk/Source/WTF/wtf/StdLibExtras.h</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkLayoutTestsjsregresslicmdragonsexpectedtxt">trunk/LayoutTests/js/regress/licm-dragons-expected.txt</a></li>
<li><a href="#trunkLayoutTestsjsregresslicmdragonsoutofboundsexpectedtxt">trunk/LayoutTests/js/regress/licm-dragons-out-of-bounds-expected.txt</a></li>
<li><a href="#trunkLayoutTestsjsregresslicmdragonsoutofboundshtml">trunk/LayoutTests/js/regress/licm-dragons-out-of-bounds.html</a></li>
<li><a href="#trunkLayoutTestsjsregresslicmdragonsoverflowexpectedtxt">trunk/LayoutTests/js/regress/licm-dragons-overflow-expected.txt</a></li>
<li><a href="#trunkLayoutTestsjsregresslicmdragonsoverflowhtml">trunk/LayoutTests/js/regress/licm-dragons-overflow.html</a></li>
<li><a href="#trunkLayoutTestsjsregresslicmdragonshtml">trunk/LayoutTests/js/regress/licm-dragons.html</a></li>
<li><a href="#trunkLayoutTestsjsregressscripttestslicmdragonsoutofboundsjs">trunk/LayoutTests/js/regress/script-tests/licm-dragons-out-of-bounds.js</a></li>
<li><a href="#trunkLayoutTestsjsregressscripttestslicmdragonsoverflowjs">trunk/LayoutTests/js/regress/script-tests/licm-dragons-overflow.js</a></li>
<li><a href="#trunkLayoutTestsjsregressscripttestslicmdragonsjs">trunk/LayoutTests/js/regress/script-tests/licm-dragons.js</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGBackwardsCFGh">trunk/Source/JavaScriptCore/dfg/DFGBackwardsCFG.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGBackwardsDominatorsh">trunk/Source/JavaScriptCore/dfg/DFGBackwardsDominators.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGControlEquivalenceAnalysish">trunk/Source/JavaScriptCore/dfg/DFGControlEquivalenceAnalysis.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGNullAbstractStateh">trunk/Source/JavaScriptCore/dfg/DFGNullAbstractState.h</a></li>
<li><a href="#trunkSourceWTFwtfBackwardsGraphh">trunk/Source/WTF/wtf/BackwardsGraph.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkLayoutTestsChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/LayoutTests/ChangeLog (201181 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/ChangeLog 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/LayoutTests/ChangeLog 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -1,3 +1,25 @@
</span><ins>+2016-05-18 Filip Pizlo <fpizlo@apple.com>
+
+ DFG::LICMPhase shouldn't hoist type checks unless it knows that the check will succeed at the loop pre-header
+ https://bugs.webkit.org/show_bug.cgi?id=144527
+
+ Reviewed by Saam Barati.
+
+ Add tests for LICM hoisting things that would only exit if hoisted.
+
+ * js/regress/licm-dragons-expected.txt: Added.
+ * js/regress/licm-dragons-out-of-bounds-expected.txt: Added.
+ * js/regress/licm-dragons-out-of-bounds.html: Added.
+ * js/regress/licm-dragons-overflow-expected.txt: Added.
+ * js/regress/licm-dragons-overflow.html: Added.
+ * js/regress/licm-dragons.html: Added.
+ * js/regress/script-tests/licm-dragons-out-of-bounds.js: Added.
+ (foo):
+ * js/regress/script-tests/licm-dragons-overflow.js: Added.
+ (foo):
+ * js/regress/script-tests/licm-dragons.js: Added.
+ (foo):
+
</ins><span class="cx"> 2016-05-19 Brian Burg <bburg@apple.com>
</span><span class="cx">
</span><span class="cx"> Web Inspector: use a consistent prefix for injected scripts
</span></span></pre></div>
<a id="trunkLayoutTestsjsregresslicmdragonsexpectedtxt"></a>
<div class="addfile"><h4>Added: trunk/LayoutTests/js/regress/licm-dragons-expected.txt (0 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/js/regress/licm-dragons-expected.txt (rev 0)
+++ trunk/LayoutTests/js/regress/licm-dragons-expected.txt 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -0,0 +1,10 @@
</span><ins>+JSRegress/licm-dragons
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS no exception thrown
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
</ins></span></pre></div>
<a id="trunkLayoutTestsjsregresslicmdragonsoutofboundsexpectedtxt"></a>
<div class="addfile"><h4>Added: trunk/LayoutTests/js/regress/licm-dragons-out-of-bounds-expected.txt (0 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/js/regress/licm-dragons-out-of-bounds-expected.txt (rev 0)
+++ trunk/LayoutTests/js/regress/licm-dragons-out-of-bounds-expected.txt 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -0,0 +1,10 @@
</span><ins>+JSRegress/licm-dragons-out-of-bounds
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS no exception thrown
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
</ins></span></pre></div>
<a id="trunkLayoutTestsjsregresslicmdragonsoutofboundshtml"></a>
<div class="addfile"><h4>Added: trunk/LayoutTests/js/regress/licm-dragons-out-of-bounds.html (0 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/js/regress/licm-dragons-out-of-bounds.html (rev 0)
+++ trunk/LayoutTests/js/regress/licm-dragons-out-of-bounds.html 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -0,0 +1,12 @@
</span><ins>+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<script src="../../resources/js-test-pre.js"></script>
+</head>
+<body>
+<script src="../../resources/regress-pre.js"></script>
+<script src="script-tests/licm-dragons-out-of-bounds.js"></script>
+<script src="../../resources/regress-post.js"></script>
+<script src="../../resources/js-test-post.js"></script>
+</body>
+</html>
</ins></span></pre></div>
<a id="trunkLayoutTestsjsregresslicmdragonsoverflowexpectedtxt"></a>
<div class="addfile"><h4>Added: trunk/LayoutTests/js/regress/licm-dragons-overflow-expected.txt (0 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/js/regress/licm-dragons-overflow-expected.txt (rev 0)
+++ trunk/LayoutTests/js/regress/licm-dragons-overflow-expected.txt 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -0,0 +1,10 @@
</span><ins>+JSRegress/licm-dragons-overflow
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS no exception thrown
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
</ins></span></pre></div>
<a id="trunkLayoutTestsjsregresslicmdragonsoverflowhtml"></a>
<div class="addfile"><h4>Added: trunk/LayoutTests/js/regress/licm-dragons-overflow.html (0 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/js/regress/licm-dragons-overflow.html (rev 0)
+++ trunk/LayoutTests/js/regress/licm-dragons-overflow.html 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -0,0 +1,12 @@
</span><ins>+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<script src="../../resources/js-test-pre.js"></script>
+</head>
+<body>
+<script src="../../resources/regress-pre.js"></script>
+<script src="script-tests/licm-dragons-overflow.js"></script>
+<script src="../../resources/regress-post.js"></script>
+<script src="../../resources/js-test-post.js"></script>
+</body>
+</html>
</ins></span></pre></div>
<a id="trunkLayoutTestsjsregresslicmdragonshtml"></a>
<div class="addfile"><h4>Added: trunk/LayoutTests/js/regress/licm-dragons.html (0 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/js/regress/licm-dragons.html (rev 0)
+++ trunk/LayoutTests/js/regress/licm-dragons.html 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -0,0 +1,12 @@
</span><ins>+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<script src="../../resources/js-test-pre.js"></script>
+</head>
+<body>
+<script src="../../resources/regress-pre.js"></script>
+<script src="script-tests/licm-dragons.js"></script>
+<script src="../../resources/regress-post.js"></script>
+<script src="../../resources/js-test-post.js"></script>
+</body>
+</html>
</ins></span></pre></div>
<a id="trunkLayoutTestsjsregressscripttestslicmdragonsoutofboundsjs"></a>
<div class="addfile"><h4>Added: trunk/LayoutTests/js/regress/script-tests/licm-dragons-out-of-bounds.js (0 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/js/regress/script-tests/licm-dragons-out-of-bounds.js (rev 0)
+++ trunk/LayoutTests/js/regress/script-tests/licm-dragons-out-of-bounds.js 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -0,0 +1,30 @@
</span><ins>+function foo(p, o, i) {
+ var result = 0;
+ for (var j = 0; j < 1000; ++j) {
+ if (p)
+ result += o[i];
+ else
+ result++;
+ }
+ return result;
+}
+
+noInline(foo);
+
+var o = [42];
+
+var result = 0;
+
+for (var i = 0; i < 1000; ++i) {
+ result += foo(true, o, 0);
+ result += foo(false, o, 1);
+}
+
+for (var i = 0; i < 10000; ++i)
+ result += foo(false, o, 1);
+
+for (var i = 0; i < 20000; ++i)
+ result += foo(true, o, 0);
+
+if (result != 893000000)
+ throw "Error: bad result: " + result;
</ins></span></pre></div>
<a id="trunkLayoutTestsjsregressscripttestslicmdragonsoverflowjs"></a>
<div class="addfile"><h4>Added: trunk/LayoutTests/js/regress/script-tests/licm-dragons-overflow.js (0 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/js/regress/script-tests/licm-dragons-overflow.js (rev 0)
+++ trunk/LayoutTests/js/regress/script-tests/licm-dragons-overflow.js 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -0,0 +1,28 @@
</span><ins>+function foo(p, a, b) {
+ var result = 0;
+ for (var i = 0; i < 1000; ++i) {
+ if (p)
+ result += a + b;
+ else
+ result += a - b;
+ }
+ return result;
+}
+
+noInline(foo);
+
+var result = 0;
+
+for (var i = 0; i < 1000; ++i) {
+ result += foo(true, 1, 2);
+ result += foo(false, 2000000000, 2000000000);
+}
+
+for (var i = 0; i < 10000; ++i)
+ result += foo(false, 2000000000, 2000000000);
+
+for (var i = 0; i < 10000; ++i)
+ result += foo(true, 1, 2);
+
+if (result != 33000000)
+ throw "Error: bad result: " + result;
</ins></span></pre></div>
<a id="trunkLayoutTestsjsregressscripttestslicmdragonsjs"></a>
<div class="addfile"><h4>Added: trunk/LayoutTests/js/regress/script-tests/licm-dragons.js (0 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/js/regress/script-tests/licm-dragons.js (rev 0)
+++ trunk/LayoutTests/js/regress/script-tests/licm-dragons.js 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -0,0 +1,31 @@
</span><ins>+function foo(p, o) {
+ var result = 0;
+ for (var i = 0; i < 1000; ++i) {
+ if (p)
+ result += o.f;
+ else
+ result++;
+ }
+ return result;
+}
+
+noInline(foo);
+
+var o = {f:42};
+var p = {};
+
+var result = 0;
+
+for (var i = 0; i < 1000; ++i) {
+ result += foo(true, o);
+ result += foo(false, p);
+}
+
+for (var i = 0; i < 10000; ++i)
+ result += foo(false, p);
+
+for (var i = 0; i < 30000; ++i)
+ result += foo(true, o);
+
+if (result != 1313000000)
+ throw "Error: bad result: " + result;
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (201181 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/JavaScriptCore/ChangeLog 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -1,3 +1,98 @@
</span><ins>+2016-05-18 Filip Pizlo <fpizlo@apple.com>
+
+ DFG::LICMPhase shouldn't hoist type checks unless it knows that the check will succeed at the loop pre-header
+ https://bugs.webkit.org/show_bug.cgi?id=144527
+
+ Reviewed by Saam Barati.
+
+ This adds a control flow equivalence analysis (called ControlEquivalenceAnalysis) based on
+ dominator analysis over the backwards CFG. Two basic blocks are control flow equivalent if
+ the execution of one implies that the other one must also execute. It means that the two
+ blocks' forward and backward dominance are reciprocated: (A dom B and B backdom A) or (B dom
+ A and A backdom B). LICM now uses it to become more conservative about hoisting checks, if
+ this has caused problems in the past. If we hoist something that may exit from a block that
+ was not control equivalent to the pre-header then it's possible that the node's speculation
+ will fail even though it wouldn't have if it wasn't hoisted. So, we flag these nodes'
+ origins as being "wasHoisted" and we track all of their exits as "HoistingFailed". LICM will
+ turn off such speculative hoisting if the CodeBlock from which we are hoisting had the
+ HoistingFailed exit kind.
+
+ Note that this deliberately still allows us to hoist things that may exit even if they are
+ not control equivalent to the pre-header. This is necessary because the profitability of
+ hoisting is so huge in all of the cases that we're aware of that it's worth giving it a
+ shot.
+
+ This is neutral on macrobenchmarks since none of the benchmarks we track have a hoistable
+ operation that would exit only if hoisted. I added microbenchmarks to illustrate the problem
+ and two of them speed up by ~40% while one of them is neutral (Int52 saves us from having
+ problems on that program even though LICM previously did the wrong thing).
+
+ * JavaScriptCore.xcodeproj/project.pbxproj:
+ * bytecode/ExitKind.cpp:
+ (JSC::exitKindToString):
+ * bytecode/ExitKind.h:
+ * dfg/DFGAtTailAbstractState.h:
+ (JSC::DFG::AtTailAbstractState::operator bool):
+ (JSC::DFG::AtTailAbstractState::initializeTo):
+ * dfg/DFGBackwardsCFG.h: Added.
+ (JSC::DFG::BackwardsCFG::BackwardsCFG):
+ * dfg/DFGBackwardsDominators.h: Added.
+ (JSC::DFG::BackwardsDominators::BackwardsDominators):
+ * dfg/DFGCommon.h:
+ (JSC::DFG::checkAndSet): Deleted.
+ * dfg/DFGControlEquivalenceAnalysis.h: Added.
+ (JSC::DFG::ControlEquivalenceAnalysis::ControlEquivalenceAnalysis):
+ (JSC::DFG::ControlEquivalenceAnalysis::dominatesEquivalently):
+ (JSC::DFG::ControlEquivalenceAnalysis::areEquivalent):
+ * dfg/DFGGraph.cpp:
+ (JSC::DFG::Graph::dump):
+ (JSC::DFG::Graph::dumpBlockHeader):
+ (JSC::DFG::Graph::invalidateCFG):
+ (JSC::DFG::Graph::substituteGetLocal):
+ (JSC::DFG::Graph::handleAssertionFailure):
+ (JSC::DFG::Graph::ensureDominators):
+ (JSC::DFG::Graph::ensurePrePostNumbering):
+ (JSC::DFG::Graph::ensureNaturalLoops):
+ (JSC::DFG::Graph::ensureBackwardsCFG):
+ (JSC::DFG::Graph::ensureBackwardsDominators):
+ (JSC::DFG::Graph::ensureControlEquivalenceAnalysis):
+ (JSC::DFG::Graph::methodOfGettingAValueProfileFor):
+ * dfg/DFGGraph.h:
+ (JSC::DFG::Graph::hasDebuggerEnabled):
+ * dfg/DFGInPlaceAbstractState.h:
+ (JSC::DFG::InPlaceAbstractState::operator bool):
+ (JSC::DFG::InPlaceAbstractState::createValueForNode):
+ (JSC::DFG::InPlaceAbstractState::forNode):
+ * dfg/DFGLICMPhase.cpp:
+ (JSC::DFG::LICMPhase::run):
+ (JSC::DFG::LICMPhase::attemptHoist):
+ * dfg/DFGMayExit.cpp:
+ (JSC::DFG::mayExit):
+ * dfg/DFGMayExit.h:
+ * dfg/DFGNode.h:
+ * dfg/DFGNodeOrigin.cpp:
+ (JSC::DFG::NodeOrigin::dump):
+ * dfg/DFGNodeOrigin.h:
+ (JSC::DFG::NodeOrigin::takeValidExit):
+ (JSC::DFG::NodeOrigin::withWasHoisted):
+ (JSC::DFG::NodeOrigin::forInsertingAfter):
+ * dfg/DFGNullAbstractState.h: Added.
+ (JSC::DFG::NullAbstractState::NullAbstractState):
+ (JSC::DFG::NullAbstractState::operator bool):
+ (JSC::DFG::NullAbstractState::forNode):
+ * dfg/DFGOSRExit.cpp:
+ (JSC::DFG::OSRExit::OSRExit):
+ * dfg/DFGOSRExitBase.cpp:
+ (JSC::DFG::OSRExitBase::considerAddingAsFrequentExitSiteSlow):
+ * dfg/DFGOSRExitBase.h:
+ (JSC::DFG::OSRExitBase::OSRExitBase):
+ * dfg/DFGTypeCheckHoistingPhase.cpp:
+ (JSC::DFG::TypeCheckHoistingPhase::run):
+ * ftl/FTLOSRExit.cpp:
+ (JSC::FTL::OSRExitDescriptor::prepareOSRExitHandle):
+ (JSC::FTL::OSRExit::OSRExit):
+ * ftl/FTLOSRExit.h:
+
</ins><span class="cx"> 2016-05-19 Mark Lam <mark.lam@apple.com>
</span><span class="cx">
</span><span class="cx"> Code that null checks the VM pointer before any use should ref the VM.
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreJavaScriptCorexcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj (201181 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -1998,6 +1998,10 @@
</span><span class="cx"> DC605B601CE26EA700593718 /* ProfilerUID.h in Headers */ = {isa = PBXBuildFile; fileRef = DC605B5C1CE26E9800593718 /* ProfilerUID.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> DC7997831CDE9FA0004D4A09 /* TagRegistersMode.h in Headers */ = {isa = PBXBuildFile; fileRef = DC7997821CDE9F9E004D4A09 /* TagRegistersMode.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> DC7997841CDE9FA2004D4A09 /* TagRegistersMode.cpp in Sources */ = {isa = PBXBuildFile; fileRef = DC7997811CDE9F9E004D4A09 /* TagRegistersMode.cpp */; };
</span><ins>+ DCEE22091CEB9895000C2396 /* DFGBackwardsCFG.h in Headers */ = {isa = PBXBuildFile; fileRef = DCEE22061CEB9890000C2396 /* DFGBackwardsCFG.h */; };
+ DCEE220A1CEB9895000C2396 /* DFGBackwardsDominators.h in Headers */ = {isa = PBXBuildFile; fileRef = DCEE22071CEB9890000C2396 /* DFGBackwardsDominators.h */; };
+ DCEE220B1CEB9895000C2396 /* DFGControlEquivalenceAnalysis.h in Headers */ = {isa = PBXBuildFile; fileRef = DCEE22081CEB9890000C2396 /* DFGControlEquivalenceAnalysis.h */; };
+ DCEE220D1CEBAF75000C2396 /* DFGNullAbstractState.h in Headers */ = {isa = PBXBuildFile; fileRef = DCEE220C1CEBAF73000C2396 /* DFGNullAbstractState.h */; };
</ins><span class="cx"> DCF3D5691CD2946D003D5C65 /* LazyClassStructure.cpp in Sources */ = {isa = PBXBuildFile; fileRef = DCF3D5641CD29468003D5C65 /* LazyClassStructure.cpp */; };
</span><span class="cx"> DCF3D56A1CD29470003D5C65 /* LazyClassStructure.h in Headers */ = {isa = PBXBuildFile; fileRef = DCF3D5651CD29468003D5C65 /* LazyClassStructure.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> DCF3D56B1CD29472003D5C65 /* LazyClassStructureInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = DCF3D5661CD29468003D5C65 /* LazyClassStructureInlines.h */; };
</span><span class="lines">@@ -4216,6 +4220,10 @@
</span><span class="cx"> DC605B5C1CE26E9800593718 /* ProfilerUID.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = ProfilerUID.h; path = profiler/ProfilerUID.h; sourceTree = "<group>"; };
</span><span class="cx"> DC7997811CDE9F9E004D4A09 /* TagRegistersMode.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = TagRegistersMode.cpp; sourceTree = "<group>"; };
</span><span class="cx"> DC7997821CDE9F9E004D4A09 /* TagRegistersMode.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = TagRegistersMode.h; sourceTree = "<group>"; };
</span><ins>+ DCEE22061CEB9890000C2396 /* DFGBackwardsCFG.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBackwardsCFG.h; path = dfg/DFGBackwardsCFG.h; sourceTree = "<group>"; };
+ DCEE22071CEB9890000C2396 /* DFGBackwardsDominators.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBackwardsDominators.h; path = dfg/DFGBackwardsDominators.h; sourceTree = "<group>"; };
+ DCEE22081CEB9890000C2396 /* DFGControlEquivalenceAnalysis.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGControlEquivalenceAnalysis.h; path = dfg/DFGControlEquivalenceAnalysis.h; sourceTree = "<group>"; };
+ DCEE220C1CEBAF73000C2396 /* DFGNullAbstractState.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGNullAbstractState.h; path = dfg/DFGNullAbstractState.h; sourceTree = "<group>"; };
</ins><span class="cx"> DCF3D5641CD29468003D5C65 /* LazyClassStructure.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LazyClassStructure.cpp; sourceTree = "<group>"; };
</span><span class="cx"> DCF3D5651CD29468003D5C65 /* LazyClassStructure.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = LazyClassStructure.h; sourceTree = "<group>"; };
</span><span class="cx"> DCF3D5661CD29468003D5C65 /* LazyClassStructureInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = LazyClassStructureInlines.h; sourceTree = "<group>"; };
</span><span class="lines">@@ -6131,6 +6139,8 @@
</span><span class="cx"> 0F666EC31835672B00D017F1 /* DFGAvailability.h */,
</span><span class="cx"> 0F2B9CD619D0BA7D00B1D1B5 /* DFGAvailabilityMap.cpp */,
</span><span class="cx"> 0F2B9CD719D0BA7D00B1D1B5 /* DFGAvailabilityMap.h */,
</span><ins>+ DCEE22061CEB9890000C2396 /* DFGBackwardsCFG.h */,
+ DCEE22071CEB9890000C2396 /* DFGBackwardsDominators.h */,
</ins><span class="cx"> 0F714CA116EA92ED00F3EBEB /* DFGBackwardsPropagationPhase.cpp */,
</span><span class="cx"> 0F714CA216EA92ED00F3EBEB /* DFGBackwardsPropagationPhase.h */,
</span><span class="cx"> A7D89CE317A0B8CC00773AD8 /* DFGBasicBlock.cpp */,
</span><span class="lines">@@ -6177,6 +6187,7 @@
</span><span class="cx"> 0F3B3A18153E68EF003ED0FF /* DFGConstantFoldingPhase.h */,
</span><span class="cx"> 0FED67B71B26256D0066CE15 /* DFGConstantHoistingPhase.cpp */,
</span><span class="cx"> 0FED67B81B26256D0066CE15 /* DFGConstantHoistingPhase.h */,
</span><ins>+ DCEE22081CEB9890000C2396 /* DFGControlEquivalenceAnalysis.h */,
</ins><span class="cx"> 0FBE0F6B16C1DB010082C5E8 /* DFGCPSRethreadingPhase.cpp */,
</span><span class="cx"> 0FBE0F6C16C1DB010082C5E8 /* DFGCPSRethreadingPhase.h */,
</span><span class="cx"> A7D89CE617A0B8CC00773AD8 /* DFGCriticalEdgeBreakingPhase.cpp */,
</span><span class="lines">@@ -6288,6 +6299,7 @@
</span><span class="cx"> 0F5D085C1B8CF99D001143B4 /* DFGNodeOrigin.cpp */,
</span><span class="cx"> 0F300B7718AB051100A6D72E /* DFGNodeOrigin.h */,
</span><span class="cx"> 0FA581B9150E952A00B9A2D9 /* DFGNodeType.h */,
</span><ins>+ DCEE220C1CEBAF73000C2396 /* DFGNullAbstractState.h */,
</ins><span class="cx"> 0F2B9CDA19D0BA7D00B1D1B5 /* DFGObjectAllocationSinkingPhase.cpp */,
</span><span class="cx"> 0F2B9CDB19D0BA7D00B1D1B5 /* DFGObjectAllocationSinkingPhase.h */,
</span><span class="cx"> 0F2B9CDC19D0BA7D00B1D1B5 /* DFGObjectMaterializationData.cpp */,
</span><span class="lines">@@ -6955,6 +6967,7 @@
</span><span class="cx"> buildActionMask = 2147483647;
</span><span class="cx"> files = (
</span><span class="cx"> 0FFA549816B8835300B3A982 /* A64DOpcode.h in Headers */,
</span><ins>+ DCEE220A1CEB9895000C2396 /* DFGBackwardsDominators.h in Headers */,
</ins><span class="cx"> 0F1FE51C1922A3BC006987C5 /* AbortReason.h in Headers */,
</span><span class="cx"> 860161E30F3A83C100F84710 /* AbstractMacroAssembler.h in Headers */,
</span><span class="cx"> 0F55F0F514D1063C00AC7649 /* AbstractPC.h in Headers */,
</span><span class="lines">@@ -6999,6 +7012,7 @@
</span><span class="cx"> BC18C3E50E16F5CD00B34460 /* APICast.h in Headers */,
</span><span class="cx"> FE3A06BE1C11041200390FDD /* JITLeftShiftGenerator.h in Headers */,
</span><span class="cx"> BCF605140E203EF800B9A64D /* ArgList.h in Headers */,
</span><ins>+ DCEE22091CEB9895000C2396 /* DFGBackwardsCFG.h in Headers */,
</ins><span class="cx"> 0FE050141AA9091100D33B33 /* ArgumentsMode.h in Headers */,
</span><span class="cx"> 0F6B1CB91861244C00845D97 /* ArityCheckMode.h in Headers */,
</span><span class="cx"> A1A009C11831A26E00CF8711 /* ARM64Assembler.h in Headers */,
</span><span class="lines">@@ -7912,6 +7926,7 @@
</span><span class="cx"> 0FF729B9166AD360000F5BA3 /* ProfilerBytecodes.h in Headers */,
</span><span class="cx"> 0F13912A16771C36009CCB07 /* ProfilerBytecodeSequence.h in Headers */,
</span><span class="cx"> 0FB387901BFBC44D00E3AB1E /* AirOptimizeBlockOrder.h in Headers */,
</span><ins>+ DCEE220D1CEBAF75000C2396 /* DFGNullAbstractState.h in Headers */,
</ins><span class="cx"> 0FF729BA166AD360000F5BA3 /* ProfilerCompilation.h in Headers */,
</span><span class="cx"> 0FF729BB166AD360000F5BA3 /* ProfilerCompilationKind.h in Headers */,
</span><span class="cx"> 0F4A38FA1C8E13DF00190318 /* SuperSampler.h in Headers */,
</span><span class="lines">@@ -8056,6 +8071,7 @@
</span><span class="cx"> 141448CD13A1783700F5BA1A /* TinyBloomFilter.h in Headers */,
</span><span class="cx"> 2684D4381C00161C0081D663 /* AirLiveness.h in Headers */,
</span><span class="cx"> 0F55989817C86C5800A1E543 /* ToNativeFromValue.h in Headers */,
</span><ins>+ DCEE220B1CEB9895000C2396 /* DFGControlEquivalenceAnalysis.h in Headers */,
</ins><span class="cx"> 0F2D4DE919832DAC007D4B19 /* ToThisStatus.h in Headers */,
</span><span class="cx"> 0F952ABD1B487A7700C367C5 /* TrackedReferences.h in Headers */,
</span><span class="cx"> 0F2B670617B6B5AB00A7AE3F /* TypedArrayAdaptors.h in Headers */,
</span></span></pre></div>
<a id="trunkSourceJavaScriptCorebytecodeExitKindcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/bytecode/ExitKind.cpp (201181 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/bytecode/ExitKind.cpp 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/JavaScriptCore/bytecode/ExitKind.cpp 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2012-2015 Apple Inc. All rights reserved.
</del><ins>+ * Copyright (C) 2012-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">@@ -76,6 +76,8 @@
</span><span class="cx"> return "VarargsOverflow";
</span><span class="cx"> case TDZFailure:
</span><span class="cx"> return "TDZFailure";
</span><ins>+ case HoistingFailed:
+ return "HoistingFailed";
</ins><span class="cx"> case Uncountable:
</span><span class="cx"> return "Uncountable";
</span><span class="cx"> case UncountableInvalidation:
</span></span></pre></div>
<a id="trunkSourceJavaScriptCorebytecodeExitKindh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/bytecode/ExitKind.h (201181 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/bytecode/ExitKind.h 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/JavaScriptCore/bytecode/ExitKind.h 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2012-2015 Apple Inc. All rights reserved.
</del><ins>+ * Copyright (C) 2012-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">@@ -50,6 +50,7 @@
</span><span class="cx"> NotStringObject, // We exited because we shouldn't have attempted to optimize string object access.
</span><span class="cx"> VarargsOverflow, // We exited because a varargs call passed more arguments than we expected.
</span><span class="cx"> TDZFailure, // We exited because we were in the TDZ and accessed the variable.
</span><ins>+ HoistingFailed, // Something that was hoisted exited. So, assume that hoisting is a bad idea.
</ins><span class="cx"> Uncountable, // We exited for none of the above reasons, and we should not count it. Most uses of this should be viewed as a FIXME.
</span><span class="cx"> UncountableInvalidation, // We exited because the code block was invalidated; this means that we've already counted the reasons why the code block was invalidated.
</span><span class="cx"> WatchdogTimerFired, // We exited because we need to service the watchdog timer.
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGAtTailAbstractStateh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGAtTailAbstractState.h (201181 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGAtTailAbstractState.h 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/JavaScriptCore/dfg/DFGAtTailAbstractState.h 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2013 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">@@ -40,6 +40,8 @@
</span><span class="cx">
</span><span class="cx"> ~AtTailAbstractState();
</span><span class="cx">
</span><ins>+ explicit operator bool() const { return true; }
+
</ins><span class="cx"> void initializeTo(BasicBlock* block)
</span><span class="cx"> {
</span><span class="cx"> m_block = block;
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGBackwardsCFGh"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/dfg/DFGBackwardsCFG.h (0 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGBackwardsCFG.h (rev 0)
+++ trunk/Source/JavaScriptCore/dfg/DFGBackwardsCFG.h 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -0,0 +1,51 @@
</span><ins>+/*
+ * Copyright (C) 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
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef DFGBackwardsCFG_h
+#define DFGBackwardsCFG_h
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGCFG.h"
+#include <wtf/BackwardsGraph.h>
+
+namespace JSC { namespace DFG {
+
+class BackwardsCFG : public BackwardsGraph<CFG> {
+ WTF_MAKE_NONCOPYABLE(BackwardsCFG);
+ WTF_MAKE_FAST_ALLOCATED;
+public:
+ BackwardsCFG(Graph& graph)
+ : BackwardsGraph<CFG>(*graph.m_cfg)
+ {
+ }
+};
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGBackwardsCFG_h
+
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGBackwardsDominatorsh"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/dfg/DFGBackwardsDominators.h (0 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGBackwardsDominators.h (rev 0)
+++ trunk/Source/JavaScriptCore/dfg/DFGBackwardsDominators.h 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -0,0 +1,52 @@
</span><ins>+/*
+ * Copyright (C) 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
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef DFGBackwardsDominators_h
+#define DFGBackwardsDominators_h
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGBackwardsCFG.h"
+#include <wtf/Dominators.h>
+#include <wtf/FastMalloc.h>
+#include <wtf/Noncopyable.h>
+
+namespace JSC { namespace DFG {
+
+class BackwardsDominators : public WTF::Dominators<BackwardsCFG> {
+ WTF_MAKE_NONCOPYABLE(BackwardsDominators);
+ WTF_MAKE_FAST_ALLOCATED;
+public:
+ BackwardsDominators(Graph& graph)
+ : WTF::Dominators<BackwardsCFG>(graph.ensureBackwardsCFG())
+ {
+ }
+};
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGDominators_h
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGCommonh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGCommon.h (201181 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGCommon.h 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/JavaScriptCore/dfg/DFGCommon.h 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -255,15 +255,6 @@
</span><span class="cx"> AfterFixup
</span><span class="cx"> };
</span><span class="cx">
</span><del>-template<typename T, typename U>
-bool checkAndSet(T& left, U right)
-{
- if (left == right)
- return false;
- left = right;
- return true;
-}
-
</del><span class="cx"> // If possible, this will acquire a lock to make sure that if multiple threads
</span><span class="cx"> // start crashing at the same time, you get coherent dump output. Use this only
</span><span class="cx"> // when you're forcing a crash with diagnostics.
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGControlEquivalenceAnalysish"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/dfg/DFGControlEquivalenceAnalysis.h (0 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGControlEquivalenceAnalysis.h (rev 0)
+++ trunk/Source/JavaScriptCore/dfg/DFGControlEquivalenceAnalysis.h 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -0,0 +1,88 @@
</span><ins>+/*
+ * Copyright (C) 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
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef DFGControlEquivalenceAnalysis_h
+#define DFGControlEquivalenceAnalysis_h
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGBackwardsDominators.h"
+#include "DFGDominators.h"
+
+namespace JSC { namespace DFG {
+
+class ControlEquivalenceAnalysis {
+ WTF_MAKE_NONCOPYABLE(ControlEquivalenceAnalysis);
+ WTF_MAKE_FAST_ALLOCATED;
+public:
+ ControlEquivalenceAnalysis(Graph& graph)
+ : m_dominators(graph.ensureDominators())
+ , m_backwardsDominators(graph.ensureBackwardsDominators())
+ {
+ }
+
+ // This returns true iff:
+ //
+ // - If b executes then a must have executed before it (a dominates b).
+ // - If a executes then b will execute after it (b backwards-dominates a).
+ //
+ // Note that like Dominators and BackwardsDominators, this analysis ignores OSR:
+ //
+ // - This may return true even if we OSR enter in beteen a and b. OSR entry would mean that b
+ // could execute even if a had not executed. This is impossible in DFG SSA but it's possible
+ // in DFG CPS.
+ // - This may return true even if we OSR exit in between a and b. OSR exit would mean that a
+ // could execute even though b will not execute. This is possible in all forms of DFG IR.
+ //
+ // In DFG SSA you only have to worry about the definition being weaked by exits. This is usually
+ // OK, since we use this analysis to determine the cost of moving exits from one block to
+ // another. If we move an exit from b to a and a equivalently dominates b then at worst we have
+ // made the exit happen sooner. If we move an exit from b to a and a dominates b but not
+ // equivalently then we've done something much worse: the program may now exit even if it would
+ // not have ever exited before.
+ bool dominatesEquivalently(BasicBlock* a, BasicBlock* b)
+ {
+ return m_dominators.dominates(a, b)
+ && m_backwardsDominators.dominates(b, a);
+ }
+
+ // This returns true iff the execution of a implies that b also executes and vice-versa.
+ bool areEquivalent(BasicBlock* a, BasicBlock* b)
+ {
+ return dominatesEquivalently(a, b)
+ || dominatesEquivalently(b, a);
+ }
+
+private:
+ Dominators& m_dominators;
+ BackwardsDominators& m_backwardsDominators;
+};
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGControlEquivalenceAnalysis_h
+
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGGraphcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGGraph.cpp (201181 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGGraph.cpp 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/JavaScriptCore/dfg/DFGGraph.cpp 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -32,10 +32,13 @@
</span><span class="cx"> #include "BytecodeLivenessAnalysisInlines.h"
</span><span class="cx"> #include "CodeBlock.h"
</span><span class="cx"> #include "CodeBlockWithJITType.h"
</span><ins>+#include "DFGBackwardsCFG.h"
+#include "DFGBackwardsDominators.h"
</ins><span class="cx"> #include "DFGBlockWorklist.h"
</span><ins>+#include "DFGCFG.h"
</ins><span class="cx"> #include "DFGClobberSet.h"
</span><span class="cx"> #include "DFGClobbersExitState.h"
</span><del>-#include "DFGCFG.h"
</del><ins>+#include "DFGControlEquivalenceAnalysis.h"
</ins><span class="cx"> #include "DFGDominators.h"
</span><span class="cx"> #include "DFGJITCode.h"
</span><span class="cx"> #include "DFGMayExit.h"
</span><span class="lines">@@ -375,6 +378,8 @@
</span><span class="cx"> }
</span><span class="cx"> if (!node->origin.exitOK)
</span><span class="cx"> out.print(comma, "ExitInvalid");
</span><ins>+ if (node->origin.wasHoisted)
+ out.print(comma, "WasHoisted");
</ins><span class="cx"> out.print(")");
</span><span class="cx">
</span><span class="cx"> if (node->hasVariableAccessData(*this) && node->tryGetVariableAccessData())
</span><span class="lines">@@ -419,6 +424,18 @@
</span><span class="cx"> out.print(prefix, " Dominance Frontier: ", m_dominators->dominanceFrontierOf(block), "\n");
</span><span class="cx"> out.print(prefix, " Iterated Dominance Frontier: ", m_dominators->iteratedDominanceFrontierOf(BlockList(1, block)), "\n");
</span><span class="cx"> }
</span><ins>+ if (m_backwardsDominators && terminalsAreValid()) {
+ out.print(prefix, " Backwards dominates by: ", m_backwardsDominators->dominatorsOf(block), "\n");
+ out.print(prefix, " Backwards dominates: ", m_backwardsDominators->blocksDominatedBy(block), "\n");
+ }
+ if (m_controlEquivalenceAnalysis && terminalsAreValid()) {
+ out.print(prefix, " Control equivalent to:");
+ for (BasicBlock* otherBlock : blocksInNaturalOrder()) {
+ if (m_controlEquivalenceAnalysis->areEquivalent(block, otherBlock))
+ out.print(" ", *otherBlock);
+ }
+ out.print("\n");
+ }
</ins><span class="cx"> if (m_prePostNumbering)
</span><span class="cx"> out.print(prefix, " Pre/Post Numbering: ", m_prePostNumbering->preNumber(block), "/", m_prePostNumbering->postNumber(block), "\n");
</span><span class="cx"> if (m_naturalLoops) {
</span><span class="lines">@@ -753,6 +770,9 @@
</span><span class="cx"> m_dominators = nullptr;
</span><span class="cx"> m_naturalLoops = nullptr;
</span><span class="cx"> m_prePostNumbering = nullptr;
</span><ins>+ m_controlEquivalenceAnalysis = nullptr;
+ m_backwardsDominators = nullptr;
+ m_backwardsCFG = nullptr;
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void Graph::substituteGetLocal(BasicBlock& block, unsigned startIndexInBlock, VariableAccessData* variableAccessData, Node* newGetLocal)
</span><span class="lines">@@ -1426,25 +1446,49 @@
</span><span class="cx"> crash(*this, toCString("While handling block ", pointerDump(block), "\n\n"), file, line, function, assertion);
</span><span class="cx"> }
</span><span class="cx">
</span><del>-void Graph::ensureDominators()
</del><ins>+Dominators& Graph::ensureDominators()
</ins><span class="cx"> {
</span><span class="cx"> if (!m_dominators)
</span><span class="cx"> m_dominators = std::make_unique<Dominators>(*this);
</span><ins>+ return *m_dominators;
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-void Graph::ensurePrePostNumbering()
</del><ins>+PrePostNumbering& Graph::ensurePrePostNumbering()
</ins><span class="cx"> {
</span><span class="cx"> if (!m_prePostNumbering)
</span><span class="cx"> m_prePostNumbering = std::make_unique<PrePostNumbering>(*this);
</span><ins>+ return *m_prePostNumbering;
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-void Graph::ensureNaturalLoops()
</del><ins>+NaturalLoops& Graph::ensureNaturalLoops()
</ins><span class="cx"> {
</span><span class="cx"> ensureDominators();
</span><span class="cx"> if (!m_naturalLoops)
</span><span class="cx"> m_naturalLoops = std::make_unique<NaturalLoops>(*this);
</span><ins>+ return *m_naturalLoops;
</ins><span class="cx"> }
</span><span class="cx">
</span><ins>+BackwardsCFG& Graph::ensureBackwardsCFG()
+{
+ if (!m_backwardsCFG)
+ m_backwardsCFG = std::make_unique<BackwardsCFG>(*this);
+ return *m_backwardsCFG;
+}
+
+BackwardsDominators& Graph::ensureBackwardsDominators()
+{
+ if (!m_backwardsDominators)
+ m_backwardsDominators = std::make_unique<BackwardsDominators>(*this);
+ return *m_backwardsDominators;
+}
+
+ControlEquivalenceAnalysis& Graph::ensureControlEquivalenceAnalysis()
+{
+ if (!m_controlEquivalenceAnalysis)
+ m_controlEquivalenceAnalysis = std::make_unique<ControlEquivalenceAnalysis>(*this);
+ return *m_controlEquivalenceAnalysis;
+}
+
</ins><span class="cx"> MethodOfGettingAValueProfile Graph::methodOfGettingAValueProfileFor(Node* node)
</span><span class="cx"> {
</span><span class="cx"> while (node) {
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGGraphh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGGraph.h (201181 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGGraph.h 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/JavaScriptCore/dfg/DFGGraph.h 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -56,7 +56,10 @@
</span><span class="cx">
</span><span class="cx"> namespace DFG {
</span><span class="cx">
</span><ins>+class BackwardsCFG;
+class BackwardsDominators;
</ins><span class="cx"> class CFG;
</span><ins>+class ControlEquivalenceAnalysis;
</ins><span class="cx"> class Dominators;
</span><span class="cx"> class NaturalLoops;
</span><span class="cx"> class PrePostNumbering;
</span><span class="lines">@@ -800,9 +803,12 @@
</span><span class="cx">
</span><span class="cx"> bool hasDebuggerEnabled() const { return m_hasDebuggerEnabled; }
</span><span class="cx">
</span><del>- void ensureDominators();
- void ensurePrePostNumbering();
- void ensureNaturalLoops();
</del><ins>+ Dominators& ensureDominators();
+ PrePostNumbering& ensurePrePostNumbering();
+ NaturalLoops& ensureNaturalLoops();
+ BackwardsCFG& ensureBackwardsCFG();
+ BackwardsDominators& ensureBackwardsDominators();
+ ControlEquivalenceAnalysis& ensureControlEquivalenceAnalysis();
</ins><span class="cx">
</span><span class="cx"> // This function only makes sense to call after bytecode parsing
</span><span class="cx"> // because it queries the m_hasExceptionHandlers boolean whose value
</span><span class="lines">@@ -879,6 +885,9 @@
</span><span class="cx"> std::unique_ptr<PrePostNumbering> m_prePostNumbering;
</span><span class="cx"> std::unique_ptr<NaturalLoops> m_naturalLoops;
</span><span class="cx"> std::unique_ptr<CFG> m_cfg;
</span><ins>+ std::unique_ptr<BackwardsCFG> m_backwardsCFG;
+ std::unique_ptr<BackwardsDominators> m_backwardsDominators;
+ std::unique_ptr<ControlEquivalenceAnalysis> m_controlEquivalenceAnalysis;
</ins><span class="cx"> unsigned m_localVars;
</span><span class="cx"> unsigned m_nextMachineLocal;
</span><span class="cx"> unsigned m_parameterSlots;
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGInPlaceAbstractStateh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.h (201181 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.h 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.h 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2013 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">@@ -42,6 +42,8 @@
</span><span class="cx">
</span><span class="cx"> ~InPlaceAbstractState();
</span><span class="cx">
</span><ins>+ explicit operator bool() const { return true; }
+
</ins><span class="cx"> void createValueForNode(Node*) { }
</span><span class="cx">
</span><span class="cx"> AbstractValue& forNode(Node* node)
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGLICMPhasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp (201181 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp 2016-05-19 21:25:29 UTC (rev 201182)
</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">@@ -33,9 +33,11 @@
</span><span class="cx"> #include "DFGBasicBlockInlines.h"
</span><span class="cx"> #include "DFGClobberSet.h"
</span><span class="cx"> #include "DFGClobberize.h"
</span><ins>+#include "DFGControlEquivalenceAnalysis.h"
</ins><span class="cx"> #include "DFGEdgeDominates.h"
</span><span class="cx"> #include "DFGGraph.h"
</span><span class="cx"> #include "DFGInsertionSet.h"
</span><ins>+#include "DFGMayExit.h"
</ins><span class="cx"> #include "DFGNaturalLoops.h"
</span><span class="cx"> #include "DFGPhase.h"
</span><span class="cx"> #include "DFGSafeToExecute.h"
</span><span class="lines">@@ -74,6 +76,7 @@
</span><span class="cx">
</span><span class="cx"> m_graph.ensureDominators();
</span><span class="cx"> m_graph.ensureNaturalLoops();
</span><ins>+ m_graph.ensureControlEquivalenceAnalysis();
</ins><span class="cx">
</span><span class="cx"> if (verbose) {
</span><span class="cx"> dataLog("Graph before LICM:\n");
</span><span class="lines">@@ -260,43 +263,6 @@
</span><span class="cx"> // we could still hoist just the checks.
</span><span class="cx"> // https://bugs.webkit.org/show_bug.cgi?id=144525
</span><span class="cx">
</span><del>- // FIXME: If a node has a type check - even something like a CheckStructure - then we should
- // only hoist the node if we know that it will execute on every loop iteration or if we know
- // that the type check will always succeed at the loop pre-header through some other means
- // (like looking at prediction propagation results). Otherwise, we might make a mistake like
- // this:
- //
- // var o = ...; // sometimes null and sometimes an object with structure S1.
- // for (...) {
- // if (o)
- // ... = o.f; // CheckStructure and GetByOffset, which we will currently hoist.
- // }
- //
- // When we encounter such code, we'll hoist the CheckStructure and GetByOffset and then we
- // will have a recompile. We'll then end up thinking that the get_by_id needs to be
- // polymorphic, which is false.
- //
- // We can counter this by either having a control flow equivalence check, or by consulting
- // prediction propagation to see if the check would always succeed. Prediction propagation
- // would not be enough for things like:
- //
- // var p = ...; // some boolean predicate
- // var o = {};
- // if (p)
- // o.f = 42;
- // for (...) {
- // if (p)
- // ... = o.f;
- // }
- //
- // Prediction propagation can't tell us anything about the structure, and the CheckStructure
- // will appear to be hoistable because the loop doesn't clobber structures. The cell check
- // in the CheckStructure will be hoistable though, since prediction propagation can tell us
- // that o is always SpecFinalObject. In cases like this, control flow equivalence is the
- // only effective guard.
- //
- // https://bugs.webkit.org/show_bug.cgi?id=144527
-
</del><span class="cx"> if (readsOverlap(m_graph, node, data.writes)) {
</span><span class="cx"> if (verbose) {
</span><span class="cx"> dataLog(
</span><span class="lines">@@ -315,6 +281,25 @@
</span><span class="cx"> return false;
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ NodeOrigin originalOrigin = node->origin;
+
+ // NOTE: We could just use BackwardsDominators here directly, since we already know that the
+ // preHeader dominates fromBlock. But we wouldn't get anything from being so clever, since
+ // dominance checks are O(1) and only a few integer compares.
+ bool addsBlindSpeculation = mayExit(m_graph, node, m_state)
+ && !m_graph.m_controlEquivalenceAnalysis->dominatesEquivalently(data.preHeader, fromBlock);
+
+ if (addsBlindSpeculation
+ && m_graph.baselineCodeBlockFor(originalOrigin.semantic)->hasExitSite(FrequentExitSite(HoistingFailed))) {
+ if (verbose) {
+ dataLog(
+ " Not hoisting ", node, " because it may exit and the pre-header (",
+ *data.preHeader, ") is not control equivalent to the node's original block (",
+ *fromBlock, ") and hoisting had previously failed.\n");
+ }
+ return false;
+ }
+
</ins><span class="cx"> if (verbose) {
</span><span class="cx"> dataLog(
</span><span class="cx"> " Hoisting ", node, " from ", *fromBlock, " to ", *data.preHeader,
</span><span class="lines">@@ -326,8 +311,9 @@
</span><span class="cx"> // https://bugs.webkit.org/show_bug.cgi?id=148544
</span><span class="cx"> data.preHeader->insertBeforeTerminal(node);
</span><span class="cx"> node->owner = data.preHeader;
</span><del>- NodeOrigin originalOrigin = node->origin;
- node->origin = data.preHeader->terminal()->origin.withSemantic(node->origin.semantic);
</del><ins>+ NodeOrigin terminalOrigin = data.preHeader->terminal()->origin;
+ node->origin = terminalOrigin.withSemantic(node->origin.semantic);
+ node->origin.wasHoisted |= addsBlindSpeculation;
</ins><span class="cx">
</span><span class="cx"> // Modify the states at the end of the preHeader of the loop we hoisted to,
</span><span class="cx"> // and all pre-headers inside the loop. This isn't a stability bottleneck right now
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGMayExitcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGMayExit.cpp (201181 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGMayExit.cpp 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/JavaScriptCore/dfg/DFGMayExit.cpp 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
</del><ins>+ * Copyright (C) 2014-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">@@ -28,60 +28,18 @@
</span><span class="cx">
</span><span class="cx"> #if ENABLE(DFG_JIT)
</span><span class="cx">
</span><ins>+#include "DFGAtTailAbstractState.h"
</ins><span class="cx"> #include "DFGGraph.h"
</span><span class="cx"> #include "DFGNode.h"
</span><ins>+#include "DFGNullAbstractState.h"
</ins><span class="cx"> #include "Operations.h"
</span><span class="cx">
</span><span class="cx"> namespace JSC { namespace DFG {
</span><span class="cx">
</span><span class="cx"> namespace {
</span><span class="cx">
</span><del>-class EdgeMayExit {
-public:
- EdgeMayExit()
- : m_result(false)
- {
- }
-
- void operator()(Node*, Edge edge)
- {
- // FIXME: Maybe this should call mayHaveTypeCheck(edge.useKind()) instead.
- // https://bugs.webkit.org/show_bug.cgi?id=148545
- if (edge.willHaveCheck()) {
- m_result = true;
- return;
- }
-
- switch (edge.useKind()) {
- // These are shady because nodes that have these use kinds will typically exit for
- // unrelated reasons. For example CompareEq doesn't usually exit, but if it uses ObjectUse
- // then it will.
- case ObjectUse:
- case ObjectOrOtherUse:
- m_result = true;
- break;
-
- // These are shady because they check the structure even if the type of the child node
- // passes the StringObject type filter.
- case StringObjectUse:
- case StringOrStringObjectUse:
- m_result = true;
- break;
-
- default:
- break;
- }
- }
-
- bool result() const { return m_result; }
-
-private:
- bool m_result;
-};
-
-} // anonymous namespace
-
-ExitMode mayExit(Graph& graph, Node* node)
</del><ins>+template<typename StateType>
+ExitMode mayExitImpl(Graph& graph, Node* node, StateType& state)
</ins><span class="cx"> {
</span><span class="cx"> ExitMode result = DoesNotExit;
</span><span class="cx">
</span><span class="lines">@@ -154,15 +112,68 @@
</span><span class="cx"> // If in doubt, return true.
</span><span class="cx"> return Exits;
</span><span class="cx"> }
</span><ins>+
+ graph.doToChildren(
+ node,
+ [&] (Edge& edge) {
+ if (state) {
+ // Ignore the Check flag on the edge. This is important because that flag answers
+ // the question: "would this edge have had a check if it executed wherever it
+ // currently resides in control flow?" But when a state is passed, we want to ask a
+ // different question: "would this edge have a check if it executed wherever this
+ // state is?" Using the Check flag for this purpose wouldn't even be conservatively
+ // correct. It would be wrong in both directions.
+ if (mayHaveTypeCheck(edge.useKind())
+ && (state.forNode(edge).m_type & ~typeFilterFor(edge.useKind()))) {
+ result = Exits;
+ return;
+ }
+ } else {
+ // FIXME: Maybe this should call mayHaveTypeCheck(edge.useKind()) instead.
+ // https://bugs.webkit.org/show_bug.cgi?id=148545
+ if (edge.willHaveCheck()) {
+ result = Exits;
+ return;
+ }
+ }
+
+ switch (edge.useKind()) {
+ // These are shady because nodes that have these use kinds will typically exit for
+ // unrelated reasons. For example CompareEq doesn't usually exit, but if it uses
+ // ObjectUse then it will.
+ case ObjectUse:
+ case ObjectOrOtherUse:
+ result = Exits;
+ break;
+
+ // These are shady because they check the structure even if the type of the child node
+ // passes the StringObject type filter.
+ case StringObjectUse:
+ case StringOrStringObjectUse:
+ result = Exits;
+ break;
+
+ default:
+ break;
+ }
+ });
</ins><span class="cx">
</span><del>- EdgeMayExit functor;
- DFG_NODE_DO_TO_CHILDREN(graph, node, functor);
- if (functor.result())
- result = Exits;
-
</del><span class="cx"> return result;
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+} // anonymous namespace
+
+ExitMode mayExit(Graph& graph, Node* node)
+{
+ NullAbstractState state;
+ return mayExitImpl(graph, node, state);
+}
+
+ExitMode mayExit(Graph& graph, Node* node, AtTailAbstractState& state)
+{
+ return mayExitImpl(graph, node, state);
+}
+
</ins><span class="cx"> } } // namespace JSC::DFG
</span><span class="cx">
</span><span class="cx"> namespace WTF {
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGMayExith"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGMayExit.h (201181 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGMayExit.h 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/JavaScriptCore/dfg/DFGMayExit.h 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
</del><ins>+ * Copyright (C) 2014-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">@@ -30,6 +30,7 @@
</span><span class="cx">
</span><span class="cx"> namespace JSC { namespace DFG {
</span><span class="cx">
</span><ins>+class AtTailAbstractState;
</ins><span class="cx"> class Graph;
</span><span class="cx"> struct Node;
</span><span class="cx">
</span><span class="lines">@@ -74,6 +75,11 @@
</span><span class="cx">
</span><span class="cx"> ExitMode mayExit(Graph&, Node*);
</span><span class="cx">
</span><ins>+// Like mayExit(), but instead of using the Check: flag to determine if something exits, it
+// evaluates whether it will exit based on the tail state. This is useful for LICM. This *may* also
+// use the AtTailAbstractState to return more precise answers for other nodes.
+ExitMode mayExit(Graph&, Node*, AtTailAbstractState&);
+
</ins><span class="cx"> } } // namespace JSC::DFG
</span><span class="cx">
</span><span class="cx"> namespace WTF {
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGNodeh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGNode.h (201181 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGNode.h 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/JavaScriptCore/dfg/DFGNode.h 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -2299,7 +2299,7 @@
</span><span class="cx">
</span><span class="cx"> private:
</span><span class="cx"> unsigned m_op : 10; // real type is NodeType
</span><del>- unsigned m_flags : 22;
</del><ins>+ unsigned m_flags : 20;
</ins><span class="cx"> // The virtual register number (spill location) associated with this .
</span><span class="cx"> VirtualRegister m_virtualRegister;
</span><span class="cx"> // The number of uses of the result of this operation (+1 for 'must generate' nodes, which have side-effects).
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGNodeOrigincpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGNodeOrigin.cpp (201181 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGNodeOrigin.cpp 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/JavaScriptCore/dfg/DFGNodeOrigin.cpp 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2015 Apple Inc. All rights reserved.
</del><ins>+ * Copyright (C) 2015-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">@@ -32,7 +32,7 @@
</span><span class="cx">
</span><span class="cx"> void NodeOrigin::dump(PrintStream& out) const
</span><span class="cx"> {
</span><del>- out.print("{semantic: ", semantic, ", forExit: ", forExit, ", exitOK: ", exitOK, "}");
</del><ins>+ out.print("{semantic: ", semantic, ", forExit: ", forExit, ", exitOK: ", exitOK, ", wasHoisted: ", wasHoisted, "}");
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> } } // namespace JSC::DFG
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGNodeOriginh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGNodeOrigin.h (201181 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGNodeOrigin.h 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/JavaScriptCore/dfg/DFGNodeOrigin.h 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
</del><ins>+ * Copyright (C) 2014-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">@@ -92,6 +92,13 @@
</span><span class="cx"> return withExitOK(exitOK & std::exchange(canExit, false));
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ NodeOrigin withWasHoisted() const
+ {
+ NodeOrigin result = *this;
+ result.wasHoisted = true;
+ return result;
+ }
+
</ins><span class="cx"> NodeOrigin forInsertingAfter(Graph& graph, Node* node) const
</span><span class="cx"> {
</span><span class="cx"> NodeOrigin result = *this;
</span><span class="lines">@@ -121,6 +128,8 @@
</span><span class="cx"> CodeOrigin forExit;
</span><span class="cx"> // Whether or not it is legal to exit here.
</span><span class="cx"> bool exitOK { false };
</span><ins>+ // Whether or not the node has been hoisted.
+ bool wasHoisted { false };
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> } } // namespace JSC::DFG
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGNullAbstractStateh"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/dfg/DFGNullAbstractState.h (0 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGNullAbstractState.h (rev 0)
+++ trunk/Source/JavaScriptCore/dfg/DFGNullAbstractState.h 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -0,0 +1,66 @@
</span><ins>+/*
+ * Copyright (C) 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
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef DFGNullAbstractState_h
+#define DFGNullAbstractState_h
+
+#if ENABLE(DFG_JIT)
+
+namespace JSC { namespace DFG {
+
+class Edge;
+struct AbstractValue;
+struct Node;
+
+// Use this as a stub for things that can optionally take some kind of abstract state but you wish
+// to not pass any abstract state. This works if the templatized code also does a check (using the
+// operator bool) to see if the state is valid.
+class NullAbstractState {
+ WTF_MAKE_FAST_ALLOCATED;
+public:
+ NullAbstractState() { }
+
+ explicit operator bool() const { return false; }
+
+ AbstractValue& forNode(Node*)
+ {
+ RELEASE_ASSERT_NOT_REACHED();
+ return *bitwise_cast<AbstractValue*>(static_cast<intptr_t>(0x1234));
+ }
+
+ AbstractValue& forNode(Edge)
+ {
+ return forNode(nullptr);
+ }
+
+ // It's valid to add more stub methods here as needed.
+};
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGNullAbstractState_h
+
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGOSRExitcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGOSRExit.cpp (201181 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGOSRExit.cpp 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/JavaScriptCore/dfg/DFGOSRExit.cpp 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -37,7 +37,7 @@
</span><span class="cx"> namespace JSC { namespace DFG {
</span><span class="cx">
</span><span class="cx"> OSRExit::OSRExit(ExitKind kind, JSValueSource jsValueSource, MethodOfGettingAValueProfile valueProfile, SpeculativeJIT* jit, unsigned streamIndex, unsigned recoveryIndex)
</span><del>- : OSRExitBase(kind, jit->m_origin.forExit, jit->m_origin.semantic)
</del><ins>+ : OSRExitBase(kind, jit->m_origin.forExit, jit->m_origin.semantic, jit->m_origin.wasHoisted)
</ins><span class="cx"> , m_jsValueSource(jsValueSource)
</span><span class="cx"> , m_valueProfile(valueProfile)
</span><span class="cx"> , m_patchableCodeOffset(0)
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGOSRExitBasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGOSRExitBase.cpp (201181 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGOSRExitBase.cpp 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/JavaScriptCore/dfg/DFGOSRExitBase.cpp 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2013 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">@@ -41,8 +41,14 @@
</span><span class="cx"> CodeBlock* sourceProfiledCodeBlock =
</span><span class="cx"> baselineCodeBlockForOriginAndBaselineCodeBlock(
</span><span class="cx"> m_codeOriginForExitProfile, profiledCodeBlock);
</span><del>- if (sourceProfiledCodeBlock)
- sourceProfiledCodeBlock->addFrequentExitSite(FrequentExitSite(m_codeOriginForExitProfile.bytecodeIndex, m_kind, jitType));
</del><ins>+ if (sourceProfiledCodeBlock) {
+ FrequentExitSite site;
+ if (m_wasHoisted)
+ site = FrequentExitSite(HoistingFailed, jitType);
+ else
+ site = FrequentExitSite(m_codeOriginForExitProfile.bytecodeIndex, m_kind, jitType);
+ sourceProfiledCodeBlock->addFrequentExitSite(site);
+ }
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> } } // namespace JSC::DFG
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGOSRExitBaseh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGOSRExitBase.h (201181 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGOSRExitBase.h 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/JavaScriptCore/dfg/DFGOSRExitBase.h 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -40,9 +40,10 @@
</span><span class="cx"> // and the FTL.
</span><span class="cx">
</span><span class="cx"> struct OSRExitBase {
</span><del>- OSRExitBase(ExitKind kind, CodeOrigin origin, CodeOrigin originForProfile)
</del><ins>+ OSRExitBase(ExitKind kind, CodeOrigin origin, CodeOrigin originForProfile, bool wasHoisted)
</ins><span class="cx"> : m_kind(kind)
</span><span class="cx"> , m_count(0)
</span><ins>+ , m_wasHoisted(wasHoisted)
</ins><span class="cx"> , m_codeOrigin(origin)
</span><span class="cx"> , m_codeOriginForExitProfile(originForProfile)
</span><span class="cx"> {
</span><span class="lines">@@ -52,6 +53,7 @@
</span><span class="cx">
</span><span class="cx"> ExitKind m_kind;
</span><span class="cx"> uint32_t m_count;
</span><ins>+ bool m_wasHoisted;
</ins><span class="cx">
</span><span class="cx"> CodeOrigin m_codeOrigin;
</span><span class="cx"> CodeOrigin m_codeOriginForExitProfile;
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGTypeCheckHoistingPhasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGTypeCheckHoistingPhase.cpp (201181 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGTypeCheckHoistingPhase.cpp 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/JavaScriptCore/dfg/DFGTypeCheckHoistingPhase.cpp 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -88,7 +88,7 @@
</span><span class="cx"> bool run()
</span><span class="cx"> {
</span><span class="cx"> ASSERT(m_graph.m_form == ThreadedCPS);
</span><del>-
</del><ins>+
</ins><span class="cx"> clearVariableVotes();
</span><span class="cx"> identifyRedundantStructureChecks();
</span><span class="cx"> disableHoistingForVariablesWithInsufficientVotes<StructureTypeCheck>();
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreftlFTLOSRExitcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ftl/FTLOSRExit.cpp (201181 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ftl/FTLOSRExit.cpp 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/JavaScriptCore/ftl/FTLOSRExit.cpp 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -92,7 +92,7 @@
</span><span class="cx"> {
</span><span class="cx"> unsigned index = state.jitCode->osrExit.size();
</span><span class="cx"> OSRExit& exit = state.jitCode->osrExit.alloc(
</span><del>- this, exitKind, nodeOrigin.forExit, nodeOrigin.semantic);
</del><ins>+ this, exitKind, nodeOrigin.forExit, nodeOrigin.semantic, nodeOrigin.wasHoisted);
</ins><span class="cx"> RefPtr<OSRExitHandle> handle = adoptRef(new OSRExitHandle(index, exit));
</span><span class="cx"> for (unsigned i = offset; i < params.size(); ++i)
</span><span class="cx"> exit.m_valueReps.append(params[i]);
</span><span class="lines">@@ -101,9 +101,9 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> OSRExit::OSRExit(
</span><del>- OSRExitDescriptor* descriptor,
- ExitKind exitKind, CodeOrigin codeOrigin, CodeOrigin codeOriginForExitProfile)
- : OSRExitBase(exitKind, codeOrigin, codeOriginForExitProfile)
</del><ins>+ OSRExitDescriptor* descriptor, ExitKind exitKind, CodeOrigin codeOrigin,
+ CodeOrigin codeOriginForExitProfile, bool wasHoisted)
+ : OSRExitBase(exitKind, codeOrigin, codeOriginForExitProfile, wasHoisted)
</ins><span class="cx"> , m_descriptor(descriptor)
</span><span class="cx"> {
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreftlFTLOSRExith"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ftl/FTLOSRExit.h (201181 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ftl/FTLOSRExit.h 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/JavaScriptCore/ftl/FTLOSRExit.h 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -117,10 +117,7 @@
</span><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> struct OSRExit : public DFG::OSRExitBase {
</span><del>- OSRExit(
- OSRExitDescriptor*, ExitKind,
- CodeOrigin, CodeOrigin codeOriginForExitProfile
- );
</del><ins>+ OSRExit(OSRExitDescriptor*, ExitKind, CodeOrigin, CodeOrigin codeOriginForExitProfile, bool wasHoisted);
</ins><span class="cx">
</span><span class="cx"> OSRExitDescriptor* m_descriptor;
</span><span class="cx"> MacroAssemblerCodeRef m_code;
</span></span></pre></div>
<a id="trunkSourceWTFChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/ChangeLog (201181 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/ChangeLog 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/WTF/ChangeLog 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -1,3 +1,61 @@
</span><ins>+2016-05-18 Filip Pizlo <fpizlo@apple.com>
+
+ DFG::LICMPhase shouldn't hoist type checks unless it knows that the check will succeed at the loop pre-header
+ https://bugs.webkit.org/show_bug.cgi?id=144527
+
+ Reviewed by Saam Barati.
+
+ This adds an adaptor for graphs called BackwardsGraph. The WTF graph framework is based on
+ passing around a Graph template argument that follows the protocol shared by DFG::CFG,
+ B3::CFG, and Air::CFG. These graphs always have a single root node but may have many leaf
+ nodes. This new BackwardsGraph adaptor reverses the graph by creating a synthetic return
+ node that it uses as the root in the inverted graph. This currently may resort to some
+ heuristics in programs that have an infinite loop, but other than that, it'll work well in
+ the general case.
+
+ This allows us to say Dominators<BackwardsGraph<some graph type>> as a way of computing
+ backwards dominators, which then allows us to easily answer control flow equivalence
+ queries.
+
+ * CMakeLists.txt:
+ * WTF.xcodeproj/project.pbxproj:
+ * wtf/BackwardsGraph.h: Added.
+ (WTF::BackwardsGraph::Node::Node):
+ (WTF::BackwardsGraph::Node::root):
+ (WTF::BackwardsGraph::Node::operator==):
+ (WTF::BackwardsGraph::Node::operator!=):
+ (WTF::BackwardsGraph::Node::operator bool):
+ (WTF::BackwardsGraph::Node::isRoot):
+ (WTF::BackwardsGraph::Node::node):
+ (WTF::BackwardsGraph::Set::Set):
+ (WTF::BackwardsGraph::Set::add):
+ (WTF::BackwardsGraph::Set::remove):
+ (WTF::BackwardsGraph::Set::contains):
+ (WTF::BackwardsGraph::Set::dump):
+ (WTF::BackwardsGraph::Map::Map):
+ (WTF::BackwardsGraph::Map::clear):
+ (WTF::BackwardsGraph::Map::size):
+ (WTF::BackwardsGraph::Map::operator[]):
+ (WTF::BackwardsGraph::BackwardsGraph):
+ (WTF::BackwardsGraph::root):
+ (WTF::BackwardsGraph::newMap):
+ (WTF::BackwardsGraph::successors):
+ (WTF::BackwardsGraph::predecessors):
+ (WTF::BackwardsGraph::index):
+ (WTF::BackwardsGraph::node):
+ (WTF::BackwardsGraph::numNodes):
+ (WTF::BackwardsGraph::dump):
+ * wtf/Dominators.h:
+ (WTF::Dominators::Dominators):
+ (WTF::Dominators::dump):
+ (WTF::Dominators::LengauerTarjan::computeDepthFirstPreNumbering):
+ * wtf/GraphNodeWorklist.h:
+ (WTF::GraphNodeWith::GraphNodeWith):
+ (WTF::GraphNodeWith::operator bool):
+ * wtf/StdLibExtras.h:
+ (WTF::callStatelessLambda):
+ (WTF::checkAndSet):
+
</ins><span class="cx"> 2016-05-18 Saam barati <sbarati@apple.com>
</span><span class="cx">
</span><span class="cx"> StringBuilder::appendQuotedJSONString doesn't properly protect against the math it's doing. Make the math fit the assertion.
</span></span></pre></div>
<a id="trunkSourceWTFWTFxcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/WTF.xcodeproj/project.pbxproj (201181 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -301,6 +301,7 @@
</span><span class="cx"> CD5497AD15857D0300B5BC30 /* MediaTime.h in Headers */ = {isa = PBXBuildFile; fileRef = CD5497AB15857D0300B5BC30 /* MediaTime.h */; };
</span><span class="cx"> CE46516E19DB1FB4003ECA05 /* NSMapTableSPI.h in Headers */ = {isa = PBXBuildFile; fileRef = CE46516D19DB1FB4003ECA05 /* NSMapTableSPI.h */; };
</span><span class="cx"> CE73E02519DCB7AB00580D5C /* XPCSPI.h in Headers */ = {isa = PBXBuildFile; fileRef = CE73E02419DCB7AB00580D5C /* XPCSPI.h */; };
</span><ins>+ DCEE22051CEB9869000C2396 /* BackwardsGraph.h in Headers */ = {isa = PBXBuildFile; fileRef = DCEE22041CEB9869000C2396 /* BackwardsGraph.h */; };
</ins><span class="cx"> DCEE21FB1CEA7538000C2396 /* CFBundleSPI.h in Headers */ = {isa = PBXBuildFile; fileRef = DCEE21FA1CEA7538000C2396 /* CFBundleSPI.h */; };
</span><span class="cx"> DCEE22001CEA7551000C2396 /* BlockObjCExceptions.h in Headers */ = {isa = PBXBuildFile; fileRef = DCEE21FC1CEA7551000C2396 /* BlockObjCExceptions.h */; };
</span><span class="cx"> DCEE22011CEA7551000C2396 /* BlockObjCExceptions.mm in Sources */ = {isa = PBXBuildFile; fileRef = DCEE21FD1CEA7551000C2396 /* BlockObjCExceptions.mm */; };
</span><span class="lines">@@ -627,6 +628,7 @@
</span><span class="cx"> CD5497AB15857D0300B5BC30 /* MediaTime.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = MediaTime.h; sourceTree = "<group>"; };
</span><span class="cx"> CE46516D19DB1FB4003ECA05 /* NSMapTableSPI.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = NSMapTableSPI.h; sourceTree = "<group>"; };
</span><span class="cx"> CE73E02419DCB7AB00580D5C /* XPCSPI.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = XPCSPI.h; sourceTree = "<group>"; };
</span><ins>+ DCEE22041CEB9869000C2396 /* BackwardsGraph.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = BackwardsGraph.h; sourceTree = "<group>"; };
</ins><span class="cx"> DCEE21FA1CEA7538000C2396 /* CFBundleSPI.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = CFBundleSPI.h; path = cf/CFBundleSPI.h; sourceTree = "<group>"; };
</span><span class="cx"> DCEE21FC1CEA7551000C2396 /* BlockObjCExceptions.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = BlockObjCExceptions.h; sourceTree = "<group>"; };
</span><span class="cx"> DCEE21FD1CEA7551000C2396 /* BlockObjCExceptions.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = BlockObjCExceptions.mm; sourceTree = "<group>"; };
</span><span class="lines">@@ -773,6 +775,7 @@
</span><span class="cx"> A8A4725D151A825A004123FF /* Atomics.h */,
</span><span class="cx"> 1469419A16EAB10A0024E146 /* AutodrainedPool.h */,
</span><span class="cx"> 1469419B16EAB10A0024E146 /* AutodrainedPoolMac.mm */,
</span><ins>+ DCEE22041CEB9869000C2396 /* BackwardsGraph.h */,
</ins><span class="cx"> 0FB14E18180FA218009B6B4D /* Bag.h */,
</span><span class="cx"> 0FB14E1A1810E1DA009B6B4D /* BagToHashMap.h */,
</span><span class="cx"> A8A4725F151A825A004123FF /* Bitmap.h */,
</span><span class="lines">@@ -1179,6 +1182,7 @@
</span><span class="cx"> A8A47391151A825B004123FF /* BumpPointerAllocator.h in Headers */,
</span><span class="cx"> EB95E1F0161A72410089A2F5 /* ByteOrder.h in Headers */,
</span><span class="cx"> A8A473AD151A825B004123FF /* cached-powers.h in Headers */,
</span><ins>+ DCEE22051CEB9869000C2396 /* BackwardsGraph.h in Headers */,
</ins><span class="cx"> A8A4745E151A825B004123FF /* CharacterNames.h in Headers */,
</span><span class="cx"> A8A47394151A825B004123FF /* CheckedArithmetic.h in Headers */,
</span><span class="cx"> A8A47395151A825B004123FF /* CheckedBoolean.h in Headers */,
</span></span></pre></div>
<a id="trunkSourceWTFwtfBackwardsGraphh"></a>
<div class="addfile"><h4>Added: trunk/Source/WTF/wtf/BackwardsGraph.h (0 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/BackwardsGraph.h (rev 0)
+++ trunk/Source/WTF/wtf/BackwardsGraph.h 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -0,0 +1,296 @@
</span><ins>+/*
+ * Copyright (C) 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
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef WTF_BackwardsGraph_h
+#define WTF_BackwardsGraph_h
+
+#include <wtf/FastMalloc.h>
+#include <wtf/GraphNodeWorklist.h>
+#include <wtf/Noncopyable.h>
+#include <wtf/Optional.h>
+#include <wtf/StdLibExtras.h>
+
+namespace WTF {
+
+template<typename Graph>
+class BackwardsGraph {
+ WTF_MAKE_NONCOPYABLE(BackwardsGraph);
+ WTF_MAKE_FAST_ALLOCATED;
+public:
+ // We use "#end" to refer to the synthetic root we have created.
+ static const char* rootName = "#end";
+
+ class Node {
+ public:
+ Node(typename Graph::Node node = typename Graph::Node())
+ : m_node(node)
+ {
+ }
+
+ static Node root()
+ {
+ Node result;
+ result.m_node = 0;
+ result.m_isRoot = true;
+ return result;
+ }
+
+ bool operator==(const Node& other) const
+ {
+ return m_node == other.m_node
+ && m_isRoot == other.m_isRoot;
+ }
+
+ bool operator!=(const Node& other) const
+ {
+ return !(*this == other);
+ }
+
+ explicit operator bool() const { return *this != Node(); }
+
+ bool isRoot() const
+ {
+ return m_isRoot;
+ }
+
+ typename Graph::Node node() const { return m_node; }
+
+ private:
+ typename Graph::Node m_node;
+ bool m_isRoot { false };
+ };
+
+ class Set {
+ public:
+ Set()
+ {
+ }
+
+ bool add(const Node& node)
+ {
+ if (node.isRoot())
+ return checkAndSet(m_hasRoot, true);
+ return m_set.add(node.node());
+ }
+
+ bool remove(const Node& node)
+ {
+ if (node.isRoot())
+ return checkAndSet(m_hasRoot, false);
+ return m_set.remove(node.node());
+ }
+
+ bool contains(const Node& node)
+ {
+ if (node.isRoot())
+ return m_hasRoot;
+ return m_set.contains(node.node());
+ }
+
+ void dump(PrintStream& out) const
+ {
+ if (m_hasRoot)
+ out.print(rootName, " ");
+ out.print(m_set);
+ }
+
+ private:
+ typename Graph::Set m_set;
+ bool m_hasRoot { false };
+ };
+
+ template<typename T>
+ class Map {
+ public:
+ Map(Graph& graph)
+ : m_map(graph.template newMap<T>())
+ {
+ }
+
+ void clear()
+ {
+ m_map.clear();
+ m_root = T();
+ }
+
+ size_t size() const { return m_map.size() + 1; }
+
+ T& operator[](size_t index)
+ {
+ if (!index)
+ return m_root;
+ return m_map[index - 1];
+ }
+
+ const T& operator[](size_t index) const
+ {
+ return (*const_cast<Map*>(this))[index];
+ }
+
+ T& operator[](const Node& node)
+ {
+ if (node.isRoot())
+ return m_root;
+ return m_map[node.node()];
+ }
+
+ const T& operator[](const Node& node) const
+ {
+ return (*const_cast<Map*>(this))[node];
+ }
+
+ private:
+ typename Graph::template Map<T> m_map;
+ T m_root;
+ };
+
+ typedef Vector<Node, 4> List;
+
+ BackwardsGraph(Graph& graph)
+ : m_graph(graph)
+ {
+ GraphNodeWorklist<typename Graph::Node, typename Graph::Set> worklist;
+
+ auto addRootSuccessor = [&] (typename Graph::Node node) {
+ if (worklist.push(node)) {
+ m_rootSuccessorList.append(node);
+ m_rootSuccessorSet.add(node);
+ while (typename Graph::Node node = worklist.pop())
+ worklist.pushAll(graph.predecessors(node));
+ }
+ };
+
+ for (unsigned i = 0; i < graph.numNodes(); ++i) {
+ if (typename Graph::Node node = graph.node(i)) {
+ if (!graph.successors(node).size())
+ addRootSuccessor(node);
+ }
+ }
+
+ // At this point there will be some nodes in the graph that aren't known to the worklist. We
+ // could add any or all of them to the root successors list. Adding all of them would be a bad
+ // pessimisation. Ideally we would pick the ones that have backward edges but no forward
+ // edges. That would require thinking, so we just use a rough heuristic: add the highest
+ // numbered nodes first, which is totally fine if the input program is already sorted nicely.
+ for (unsigned i = graph.numNodes(); i--;) {
+ if (typename Graph::Node node = graph.node(i))
+ addRootSuccessor(node);
+ }
+ }
+
+ Node root() { return Node::root(); }
+
+ template<typename T>
+ Map<T> newMap() { return Map<T>(m_graph); }
+
+ List successors(const Node& node) const
+ {
+ if (node.isRoot())
+ return m_rootSuccessorList;
+ List result;
+ for (typename Graph::Node predecessor : m_graph.predecessors(node.node()))
+ result.append(predecessor);
+ return result;
+ }
+
+ List predecessors(const Node& node) const
+ {
+ if (node.isRoot())
+ return { };
+
+ List result;
+
+ if (m_rootSuccessorSet.contains(node.node()))
+ result.append(Node::root());
+
+ for (typename Graph::Node successor : m_graph.successors(node.node()))
+ result.append(successor);
+
+ return result;
+ }
+
+ unsigned index(const Node& node) const
+ {
+ if (node.isRoot())
+ return 0;
+ return m_graph.index(node.node()) + 1;
+ }
+
+ Node node(unsigned index) const
+ {
+ if (!index)
+ return Node::root();
+ return m_graph.node(index - 1);
+ }
+
+ unsigned numNodes() const
+ {
+ return m_graph.numNodes() + 1;
+ }
+
+ CString dump(Node node) const
+ {
+ StringPrintStream out;
+ if (!node)
+ out.print("<null>");
+ else if (node.isRoot())
+ out.print(rootName);
+ else
+ out.print(m_graph.dump(node.node()));
+ return out.toCString();
+ }
+
+ void dump(PrintStream& out) const
+ {
+ for (unsigned i = 0; i < numNodes(); ++i) {
+ Node node = this->node(i);
+ if (!node)
+ continue;
+ out.print(dump(node), ":\n");
+ out.print(" Preds: ");
+ CommaPrinter comma;
+ for (Node predecessor : predecessors(node))
+ out.print(comma, dump(predecessor));
+ out.print("\n");
+ out.print(" Succs: ");
+ comma = CommaPrinter();
+ for (Node successor : successors(node))
+ out.print(comma, dump(successor));
+ out.print("\n");
+ }
+ }
+
+private:
+ Graph& m_graph;
+ List m_rootSuccessorList;
+ typename Graph::Set m_rootSuccessorSet;
+};
+
+} // namespace WTF
+
+using WTF::BackwardsGraph;
+
+#endif // WTF_BackwardsGraph_h
+
</ins></span></pre></div>
<a id="trunkSourceWTFwtfCMakeListstxt"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/CMakeLists.txt (201181 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/CMakeLists.txt 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/WTF/wtf/CMakeLists.txt 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -2,6 +2,7 @@
</span><span class="cx"> ASCIICType.h
</span><span class="cx"> Assertions.h
</span><span class="cx"> Atomics.h
</span><ins>+ BackwardsGraph.h
</ins><span class="cx"> Bag.h
</span><span class="cx"> BagToHashMap.h
</span><span class="cx"> BitVector.h
</span></span></pre></div>
<a id="trunkSourceWTFwtfDominatorsh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/Dominators.h (201181 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/Dominators.h 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/WTF/wtf/Dominators.h 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2011, 2014, 2015 Apple Inc. All rights reserved.
</del><ins>+ * Copyright (C) 2011, 2014-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">@@ -41,6 +41,7 @@
</span><span class="cx"> public:
</span><span class="cx"> Dominators(Graph& graph, bool selfCheck = false)
</span><span class="cx"> : m_graph(graph)
</span><ins>+ , m_data(graph.template newMap<BlockData>())
</ins><span class="cx"> {
</span><span class="cx"> LengauerTarjan lengauerTarjan(m_graph);
</span><span class="cx"> lengauerTarjan.compute();
</span><span class="lines">@@ -67,7 +68,7 @@
</span><span class="cx">
</span><span class="cx"> // Plain stack-based worklist because we are guaranteed to see each block exactly once anyway.
</span><span class="cx"> Vector<GraphNodeWithOrder<typename Graph::Node>> worklist;
</span><del>- worklist.append(GraphNodeWithOrder<typename Graph::Node>(m_graph.node(0), GraphVisitOrder::Pre));
</del><ins>+ worklist.append(GraphNodeWithOrder<typename Graph::Node>(m_graph.root(), GraphVisitOrder::Pre));
</ins><span class="cx"> while (!worklist.isEmpty()) {
</span><span class="cx"> GraphNodeWithOrder<typename Graph::Node> item = worklist.takeLast();
</span><span class="cx"> switch (item.order) {
</span><span class="lines">@@ -279,10 +280,10 @@
</span><span class="cx"> if (m_data[blockIndex].preNumber == UINT_MAX)
</span><span class="cx"> continue;
</span><span class="cx">
</span><del>- out.print(" Block #", blockIndex, ": idom = ", pointerDump(m_data[blockIndex].idomParent), ", idomKids = [");
</del><ins>+ out.print(" Block #", blockIndex, ": idom = ", m_graph.dump(m_data[blockIndex].idomParent), ", idomKids = [");
</ins><span class="cx"> CommaPrinter comma;
</span><span class="cx"> for (unsigned i = 0; i < m_data[blockIndex].idomKids.size(); ++i)
</span><del>- out.print(comma, *m_data[blockIndex].idomKids[i]);
</del><ins>+ out.print(comma, m_graph.dump(m_data[blockIndex].idomKids[i]));
</ins><span class="cx"> out.print("], pre/post = ", m_data[blockIndex].preNumber, "/", m_data[blockIndex].postNumber, "\n");
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="lines">@@ -347,7 +348,7 @@
</span><span class="cx"> // of not noticing A->C until we're done processing B.
</span><span class="cx">
</span><span class="cx"> ExtendedGraphNodeWorklist<typename Graph::Node, unsigned, typename Graph::Set> worklist;
</span><del>- worklist.push(m_graph.node(0), 0);
</del><ins>+ worklist.push(m_graph.root(), 0);
</ins><span class="cx">
</span><span class="cx"> while (GraphNodeWith<typename Graph::Node, unsigned> item = worklist.pop()) {
</span><span class="cx"> typename Graph::Node block = item.node;
</span></span></pre></div>
<a id="trunkSourceWTFwtfGraphNodeWorklisth"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/GraphNodeWorklist.h (201181 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/GraphNodeWorklist.h 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/WTF/wtf/GraphNodeWorklist.h 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -83,7 +83,7 @@
</span><span class="cx"> {
</span><span class="cx"> }
</span><span class="cx">
</span><del>- explicit operator bool() const { return node; }
</del><ins>+ explicit operator bool() const { return !!node; }
</ins><span class="cx">
</span><span class="cx"> Node node;
</span><span class="cx"> T data;
</span></span></pre></div>
<a id="trunkSourceWTFwtfStdLibExtrash"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/StdLibExtras.h (201181 => 201182)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/StdLibExtras.h 2016-05-19 21:11:02 UTC (rev 201181)
+++ trunk/Source/WTF/wtf/StdLibExtras.h 2016-05-19 21:25:29 UTC (rev 201182)
</span><span class="lines">@@ -299,6 +299,15 @@
</span><span class="cx"> return (*bitwise_cast<Func*>(data))(std::forward<ArgumentTypes>(arguments)...);
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+template<typename T, typename U>
+bool checkAndSet(T& left, U right)
+{
+ if (left == right)
+ return false;
+ left = right;
+ return true;
+}
+
</ins><span class="cx"> } // namespace WTF
</span><span class="cx">
</span><span class="cx"> // This version of placement new omits a 0 check.
</span><span class="lines">@@ -409,17 +418,18 @@
</span><span class="cx">
</span><span class="cx"> using WTF::KB;
</span><span class="cx"> using WTF::MB;
</span><ins>+using WTF::approximateBinarySearch;
+using WTF::binarySearch;
+using WTF::bitwise_cast;
+using WTF::callStatelessLambda;
+using WTF::checkAndSet;
+using WTF::insertIntoBoundedVector;
</ins><span class="cx"> using WTF::isCompilationThread;
</span><del>-using WTF::insertIntoBoundedVector;
</del><span class="cx"> using WTF::isPointerAligned;
</span><ins>+using WTF::isStatelessLambda;
</ins><span class="cx"> using WTF::is8ByteAligned;
</span><del>-using WTF::binarySearch;
</del><ins>+using WTF::safeCast;
</ins><span class="cx"> using WTF::tryBinarySearch;
</span><del>-using WTF::approximateBinarySearch;
-using WTF::bitwise_cast;
-using WTF::safeCast;
-using WTF::isStatelessLambda;
-using WTF::callStatelessLambda;
</del><span class="cx">
</span><span class="cx"> #if COMPILER_SUPPORTS(CXX_USER_LITERALS)
</span><span class="cx"> // We normally don't want to bring in entire std namespaces, but literals are an exception.
</span></span></pre>
</div>
</div>
</body>
</html>