<!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>[173413] trunk/Source</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/173413">173413</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2014-09-08 17:34:40 -0700 (Mon, 08 Sep 2014)</dd>
</dl>
<h3>Log Message</h3>
<pre>DFG should have a reusable SSA builder
https://bugs.webkit.org/show_bug.cgi?id=136331
Reviewed by Oliver Hunt.
Source/JavaScriptCore:
We want to implement sophisticated SSA transformations like object allocation sinking
(https://bugs.webkit.org/show_bug.cgi?id=136330), but to do that, we need to be able to do
updates to SSA that require inserting new Phi's. This requires calculating where Phis go.
Previously, our Phi calculation was based on Aycock and Horspool's algorithm, and our
implementation of this algorithm only worked when doing CPS->SSA conversion. The code
could not be reused for cases where some phase happens to know that it introduced a few
defs in some blocks and it wants to figure out where the Phis should go. Moreover, even
the general algorithm of Aycock and Horspool is not well suited to such targetted SSA
updates, since it requires first inserting maximal Phis. That scales well when the Phis
were already there (like in our CPS form) but otherwise it's quite unnatural and may be
difficult to make efficient.
The usual way of handling both SSA conversion and SSA update is to use Cytron et al's
algorithm based on dominance frontiers. For a while now, I've been working on creating a
Cytron-based SSA calculator that can be used both as a replacement for our current SSA
converter and as a reusable tool for any phase that needs to do SSA update. I previously
optimized our dominator calculation and representation to use dominator trees computed
using Lengauer and Tarjan's algorithm - mainly to make it more scalable to enumerate over
the set of blocks that dominate you or vice-versa, and then I implemented a dominance
frontier calculator. This patch implements the final step towards making SSA update
available to all SSA phases: it implements an SSACalculator that can tell you where Phis
go when given an arbitrary set of Defs. To keep things simple, and to ensure that we have
good test coverage for this SSACalculator, this patch replaces the old Aycock-Horspool
SSA converter with one based on the SSACalculator.
This has no observable impact. It does reduce the amount of code in SSAConversionPhase.
But even better, it makes SSAConversionPhase have significantly less tricky logic. It
mostly just relies on SSACalculator to do the tricky stuff, and SSAConversionPhase mostly
just reasons about the weirdnesses unique to the ThreadedCPS form that it sees as input.
In fact, using the Cytron et al approach means that there isn't really any "smoke and
mirrors" trickyness related to SSA. SSACalculator's only "tricks" are using the pruned
iterated dominance frontier to place Phi's and using the dom tree to find reaching defs.
The complexity is mostly confined to Dominators, which computes various dominator-related
properties over the control flow graph. That class can be difficult to understand, but at
least it follows well-known graph theory wisdom.
* CMakeLists.txt:
* JavaScriptCore.vcxproj/JavaScriptCore.vcxproj:
* JavaScriptCore.xcodeproj/project.pbxproj:
* dfg/DFGAnalysis.h:
* dfg/DFGCSEPhase.cpp:
* dfg/DFGDCEPhase.cpp:
(JSC::DFG::DCEPhase::run):
* dfg/DFGDominators.h:
(JSC::DFG::Dominators::immediateDominatorOf):
(JSC::DFG::Dominators::forAllBlocksInIteratedDominanceFrontierOf):
(JSC::DFG::Dominators::forAllBlocksInPrunedIteratedDominanceFrontierOf):
* dfg/DFGGraph.cpp:
(JSC::DFG::Graph::dump):
(JSC::DFG::Graph::blocksInPreOrder):
(JSC::DFG::Graph::blocksInPostOrder):
(JSC::DFG::Graph::getBlocksInPreOrder): Deleted.
(JSC::DFG::Graph::getBlocksInPostOrder): Deleted.
* dfg/DFGGraph.h:
* dfg/DFGLICMPhase.cpp:
(JSC::DFG::LICMPhase::run):
* dfg/DFGNodeFlags.h:
* dfg/DFGPhase.cpp:
(JSC::DFG::Phase::beginPhase):
(JSC::DFG::Phase::endPhase):
* dfg/DFGPhase.h:
* dfg/DFGSSACalculator.cpp: Added.
(JSC::DFG::SSACalculator::Variable::dump):
(JSC::DFG::SSACalculator::Variable::dumpVerbose):
(JSC::DFG::SSACalculator::Def::dump):
(JSC::DFG::SSACalculator::SSACalculator):
(JSC::DFG::SSACalculator::~SSACalculator):
(JSC::DFG::SSACalculator::newVariable):
(JSC::DFG::SSACalculator::newDef):
(JSC::DFG::SSACalculator::nonLocalReachingDef):
(JSC::DFG::SSACalculator::reachingDefAtTail):
(JSC::DFG::SSACalculator::dump):
* dfg/DFGSSACalculator.h: Added.
(JSC::DFG::SSACalculator::Variable::index):
(JSC::DFG::SSACalculator::Variable::Variable):
(JSC::DFG::SSACalculator::Def::variable):
(JSC::DFG::SSACalculator::Def::block):
(JSC::DFG::SSACalculator::Def::value):
(JSC::DFG::SSACalculator::Def::Def):
(JSC::DFG::SSACalculator::variable):
(JSC::DFG::SSACalculator::computePhis):
(JSC::DFG::SSACalculator::phisForBlock):
(JSC::DFG::SSACalculator::reachingDefAtHead):
* dfg/DFGSSAConversionPhase.cpp:
(JSC::DFG::SSAConversionPhase::SSAConversionPhase):
(JSC::DFG::SSAConversionPhase::run):
(JSC::DFG::SSAConversionPhase::forwardPhiChildren): Deleted.
(JSC::DFG::SSAConversionPhase::forwardPhi): Deleted.
(JSC::DFG::SSAConversionPhase::forwardPhiEdge): Deleted.
(JSC::DFG::SSAConversionPhase::deduplicateChildren): Deleted.
* dfg/DFGSSAConversionPhase.h:
* dfg/DFGValidate.cpp:
(JSC::DFG::Validate::Validate):
(JSC::DFG::Validate::dumpGraphIfAppropriate):
(JSC::DFG::validate):
* dfg/DFGValidate.h:
* ftl/FTLLowerDFGToLLVM.cpp:
(JSC::FTL::LowerDFGToLLVM::lower):
* runtime/Options.h:
Source/WTF:
Update the alloc() method to use variadic templates. This makes it more natural to use.
* wtf/SegmentedVector.h:
(WTF::SegmentedVector::alloc):</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreCMakeListstxt">trunk/Source/JavaScriptCore/CMakeLists.txt</a></li>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoreJavaScriptCorevcxprojJavaScriptCorevcxproj">trunk/Source/JavaScriptCore/JavaScriptCore.vcxproj/JavaScriptCore.vcxproj</a></li>
<li><a href="#trunkSourceJavaScriptCoreJavaScriptCorexcodeprojprojectpbxproj">trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGAnalysish">trunk/Source/JavaScriptCore/dfg/DFGAnalysis.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGCSEPhasecpp">trunk/Source/JavaScriptCore/dfg/DFGCSEPhase.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGDCEPhasecpp">trunk/Source/JavaScriptCore/dfg/DFGDCEPhase.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGDominatorsh">trunk/Source/JavaScriptCore/dfg/DFGDominators.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="#trunkSourceJavaScriptCoredfgDFGLICMPhasecpp">trunk/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGNodeFlagsh">trunk/Source/JavaScriptCore/dfg/DFGNodeFlags.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGPhasecpp">trunk/Source/JavaScriptCore/dfg/DFGPhase.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGPhaseh">trunk/Source/JavaScriptCore/dfg/DFGPhase.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGSSAConversionPhasecpp">trunk/Source/JavaScriptCore/dfg/DFGSSAConversionPhase.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGSSAConversionPhaseh">trunk/Source/JavaScriptCore/dfg/DFGSSAConversionPhase.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGValidatecpp">trunk/Source/JavaScriptCore/dfg/DFGValidate.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGValidateh">trunk/Source/JavaScriptCore/dfg/DFGValidate.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreftlFTLLowerDFGToLLVMcpp">trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreruntimeOptionsh">trunk/Source/JavaScriptCore/runtime/Options.h</a></li>
<li><a href="#trunkSourceWTFChangeLog">trunk/Source/WTF/ChangeLog</a></li>
<li><a href="#trunkSourceWTFwtfSegmentedVectorh">trunk/Source/WTF/wtf/SegmentedVector.h</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoredfgDFGSSACalculatorcpp">trunk/Source/JavaScriptCore/dfg/DFGSSACalculator.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGSSACalculatorh">trunk/Source/JavaScriptCore/dfg/DFGSSACalculator.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreCMakeListstxt"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/CMakeLists.txt (173412 => 173413)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/CMakeLists.txt 2014-09-09 00:33:02 UTC (rev 173412)
+++ trunk/Source/JavaScriptCore/CMakeLists.txt 2014-09-09 00:34:40 UTC (rev 173413)
</span><span class="lines">@@ -201,6 +201,7 @@
</span><span class="cx"> dfg/DFGPredictionPropagationPhase.cpp
</span><span class="cx"> dfg/DFGPureValue.cpp
</span><span class="cx"> dfg/DFGResurrectionForValidationPhase.cpp
</span><ins>+ dfg/DFGSSACalculator.cpp
</ins><span class="cx"> dfg/DFGSSAConversionPhase.cpp
</span><span class="cx"> dfg/DFGSSALoweringPhase.cpp
</span><span class="cx"> dfg/DFGSafepoint.cpp
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (173412 => 173413)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2014-09-09 00:33:02 UTC (rev 173412)
+++ trunk/Source/JavaScriptCore/ChangeLog 2014-09-09 00:34:40 UTC (rev 173413)
</span><span class="lines">@@ -1,3 +1,110 @@
</span><ins>+2014-09-08 Filip Pizlo <fpizlo@apple.com>
+
+ DFG should have a reusable SSA builder
+ https://bugs.webkit.org/show_bug.cgi?id=136331
+
+ Reviewed by Oliver Hunt.
+
+ We want to implement sophisticated SSA transformations like object allocation sinking
+ (https://bugs.webkit.org/show_bug.cgi?id=136330), but to do that, we need to be able to do
+ updates to SSA that require inserting new Phi's. This requires calculating where Phis go.
+ Previously, our Phi calculation was based on Aycock and Horspool's algorithm, and our
+ implementation of this algorithm only worked when doing CPS->SSA conversion. The code
+ could not be reused for cases where some phase happens to know that it introduced a few
+ defs in some blocks and it wants to figure out where the Phis should go. Moreover, even
+ the general algorithm of Aycock and Horspool is not well suited to such targetted SSA
+ updates, since it requires first inserting maximal Phis. That scales well when the Phis
+ were already there (like in our CPS form) but otherwise it's quite unnatural and may be
+ difficult to make efficient.
+
+ The usual way of handling both SSA conversion and SSA update is to use Cytron et al's
+ algorithm based on dominance frontiers. For a while now, I've been working on creating a
+ Cytron-based SSA calculator that can be used both as a replacement for our current SSA
+ converter and as a reusable tool for any phase that needs to do SSA update. I previously
+ optimized our dominator calculation and representation to use dominator trees computed
+ using Lengauer and Tarjan's algorithm - mainly to make it more scalable to enumerate over
+ the set of blocks that dominate you or vice-versa, and then I implemented a dominance
+ frontier calculator. This patch implements the final step towards making SSA update
+ available to all SSA phases: it implements an SSACalculator that can tell you where Phis
+ go when given an arbitrary set of Defs. To keep things simple, and to ensure that we have
+ good test coverage for this SSACalculator, this patch replaces the old Aycock-Horspool
+ SSA converter with one based on the SSACalculator.
+
+ This has no observable impact. It does reduce the amount of code in SSAConversionPhase.
+ But even better, it makes SSAConversionPhase have significantly less tricky logic. It
+ mostly just relies on SSACalculator to do the tricky stuff, and SSAConversionPhase mostly
+ just reasons about the weirdnesses unique to the ThreadedCPS form that it sees as input.
+ In fact, using the Cytron et al approach means that there isn't really any "smoke and
+ mirrors" trickyness related to SSA. SSACalculator's only "tricks" are using the pruned
+ iterated dominance frontier to place Phi's and using the dom tree to find reaching defs.
+ The complexity is mostly confined to Dominators, which computes various dominator-related
+ properties over the control flow graph. That class can be difficult to understand, but at
+ least it follows well-known graph theory wisdom.
+
+ * CMakeLists.txt:
+ * JavaScriptCore.vcxproj/JavaScriptCore.vcxproj:
+ * JavaScriptCore.xcodeproj/project.pbxproj:
+ * dfg/DFGAnalysis.h:
+ * dfg/DFGCSEPhase.cpp:
+ * dfg/DFGDCEPhase.cpp:
+ (JSC::DFG::DCEPhase::run):
+ * dfg/DFGDominators.h:
+ (JSC::DFG::Dominators::immediateDominatorOf):
+ (JSC::DFG::Dominators::forAllBlocksInIteratedDominanceFrontierOf):
+ (JSC::DFG::Dominators::forAllBlocksInPrunedIteratedDominanceFrontierOf):
+ * dfg/DFGGraph.cpp:
+ (JSC::DFG::Graph::dump):
+ (JSC::DFG::Graph::blocksInPreOrder):
+ (JSC::DFG::Graph::blocksInPostOrder):
+ (JSC::DFG::Graph::getBlocksInPreOrder): Deleted.
+ (JSC::DFG::Graph::getBlocksInPostOrder): Deleted.
+ * dfg/DFGGraph.h:
+ * dfg/DFGLICMPhase.cpp:
+ (JSC::DFG::LICMPhase::run):
+ * dfg/DFGNodeFlags.h:
+ * dfg/DFGPhase.cpp:
+ (JSC::DFG::Phase::beginPhase):
+ (JSC::DFG::Phase::endPhase):
+ * dfg/DFGPhase.h:
+ * dfg/DFGSSACalculator.cpp: Added.
+ (JSC::DFG::SSACalculator::Variable::dump):
+ (JSC::DFG::SSACalculator::Variable::dumpVerbose):
+ (JSC::DFG::SSACalculator::Def::dump):
+ (JSC::DFG::SSACalculator::SSACalculator):
+ (JSC::DFG::SSACalculator::~SSACalculator):
+ (JSC::DFG::SSACalculator::newVariable):
+ (JSC::DFG::SSACalculator::newDef):
+ (JSC::DFG::SSACalculator::nonLocalReachingDef):
+ (JSC::DFG::SSACalculator::reachingDefAtTail):
+ (JSC::DFG::SSACalculator::dump):
+ * dfg/DFGSSACalculator.h: Added.
+ (JSC::DFG::SSACalculator::Variable::index):
+ (JSC::DFG::SSACalculator::Variable::Variable):
+ (JSC::DFG::SSACalculator::Def::variable):
+ (JSC::DFG::SSACalculator::Def::block):
+ (JSC::DFG::SSACalculator::Def::value):
+ (JSC::DFG::SSACalculator::Def::Def):
+ (JSC::DFG::SSACalculator::variable):
+ (JSC::DFG::SSACalculator::computePhis):
+ (JSC::DFG::SSACalculator::phisForBlock):
+ (JSC::DFG::SSACalculator::reachingDefAtHead):
+ * dfg/DFGSSAConversionPhase.cpp:
+ (JSC::DFG::SSAConversionPhase::SSAConversionPhase):
+ (JSC::DFG::SSAConversionPhase::run):
+ (JSC::DFG::SSAConversionPhase::forwardPhiChildren): Deleted.
+ (JSC::DFG::SSAConversionPhase::forwardPhi): Deleted.
+ (JSC::DFG::SSAConversionPhase::forwardPhiEdge): Deleted.
+ (JSC::DFG::SSAConversionPhase::deduplicateChildren): Deleted.
+ * dfg/DFGSSAConversionPhase.h:
+ * dfg/DFGValidate.cpp:
+ (JSC::DFG::Validate::Validate):
+ (JSC::DFG::Validate::dumpGraphIfAppropriate):
+ (JSC::DFG::validate):
+ * dfg/DFGValidate.h:
+ * ftl/FTLLowerDFGToLLVM.cpp:
+ (JSC::FTL::LowerDFGToLLVM::lower):
+ * runtime/Options.h:
+
</ins><span class="cx"> 2014-09-08 Commit Queue <commit-queue@webkit.org>
</span><span class="cx">
</span><span class="cx"> Unreviewed, rolling out r173402.
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreJavaScriptCorevcxprojJavaScriptCorevcxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/JavaScriptCore.vcxproj/JavaScriptCore.vcxproj (173412 => 173413)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/JavaScriptCore.vcxproj/JavaScriptCore.vcxproj 2014-09-09 00:33:02 UTC (rev 173412)
+++ trunk/Source/JavaScriptCore/JavaScriptCore.vcxproj/JavaScriptCore.vcxproj 2014-09-09 00:34:40 UTC (rev 173413)
</span><span class="lines">@@ -451,6 +451,7 @@
</span><span class="cx"> <ClCompile Include="..\dfg\DFGSpeculativeJIT.cpp" />
</span><span class="cx"> <ClCompile Include="..\dfg\DFGSpeculativeJIT32_64.cpp" />
</span><span class="cx"> <ClCompile Include="..\dfg\DFGSpeculativeJIT64.cpp" />
</span><ins>+ <ClCompile Include="..\dfg\DFGSSACalculator.cpp" />
</ins><span class="cx"> <ClCompile Include="..\dfg\DFGSSAConversionPhase.cpp" />
</span><span class="cx"> <ClCompile Include="..\dfg\DFGSSALoweringPhase.cpp" />
</span><span class="cx"> <ClCompile Include="..\dfg\DFGStackLayoutPhase.cpp" />
</span><span class="lines">@@ -1101,6 +1102,7 @@
</span><span class="cx"> <ClInclude Include="..\dfg\DFGSilentRegisterSavePlan.h" />
</span><span class="cx"> <ClInclude Include="..\dfg\DFGSlowPathGenerator.h" />
</span><span class="cx"> <ClInclude Include="..\dfg\DFGSpeculativeJIT.h" />
</span><ins>+ <ClInclude Include="..\dfg\DFGSSACalculator.h" />
</ins><span class="cx"> <ClInclude Include="..\dfg\DFGSSAConversionPhase.h" />
</span><span class="cx"> <ClInclude Include="..\dfg\DFGSSALoweringPhase.h" />
</span><span class="cx"> <ClInclude Include="..\dfg\DFGStackLayoutPhase.h" />
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreJavaScriptCorexcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj (173412 => 173413)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj 2014-09-09 00:33:02 UTC (rev 173412)
+++ trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj 2014-09-09 00:34:40 UTC (rev 173413)
</span><span class="lines">@@ -341,6 +341,8 @@
</span><span class="cx"> 0F666ECD1836B37E00D017F1 /* DFGResurrectionForValidationPhase.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F666ECB1836B37E00D017F1 /* DFGResurrectionForValidationPhase.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 0F66E16B14DF3F1600B7B2E4 /* DFGAdjacencyList.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F66E16814DF3F1300B7B2E4 /* DFGAdjacencyList.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 0F66E16C14DF3F1600B7B2E4 /* DFGEdge.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F66E16914DF3F1300B7B2E4 /* DFGEdge.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><ins>+ 0F682FB219BCB36400FA3BAD /* DFGSSACalculator.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F682FB019BCB36400FA3BAD /* DFGSSACalculator.cpp */; };
+ 0F682FB319BCB36400FA3BAD /* DFGSSACalculator.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F682FB119BCB36400FA3BAD /* DFGSSACalculator.h */; settings = {ATTRIBUTES = (Private, ); }; };
</ins><span class="cx"> 0F69CC88193AC60A0045759E /* DFGFrozenValue.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F69CC86193AC60A0045759E /* DFGFrozenValue.cpp */; };
</span><span class="cx"> 0F69CC89193AC60A0045759E /* DFGFrozenValue.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F69CC87193AC60A0045759E /* DFGFrozenValue.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 0F6B1CB5185FC9E900845D97 /* FTLJSCall.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F6B1CB3185FC9E900845D97 /* FTLJSCall.cpp */; };
</span><span class="lines">@@ -2260,6 +2262,8 @@
</span><span class="cx"> 0F666ECB1836B37E00D017F1 /* DFGResurrectionForValidationPhase.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGResurrectionForValidationPhase.h; path = dfg/DFGResurrectionForValidationPhase.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F66E16814DF3F1300B7B2E4 /* DFGAdjacencyList.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGAdjacencyList.h; path = dfg/DFGAdjacencyList.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F66E16914DF3F1300B7B2E4 /* DFGEdge.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGEdge.h; path = dfg/DFGEdge.h; sourceTree = "<group>"; };
</span><ins>+ 0F682FB019BCB36400FA3BAD /* DFGSSACalculator.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGSSACalculator.cpp; path = dfg/DFGSSACalculator.cpp; sourceTree = "<group>"; };
+ 0F682FB119BCB36400FA3BAD /* DFGSSACalculator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGSSACalculator.h; path = dfg/DFGSSACalculator.h; sourceTree = "<group>"; };
</ins><span class="cx"> 0F69CC86193AC60A0045759E /* DFGFrozenValue.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGFrozenValue.cpp; path = dfg/DFGFrozenValue.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 0F69CC87193AC60A0045759E /* DFGFrozenValue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGFrozenValue.h; path = dfg/DFGFrozenValue.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F6B1CB3185FC9E900845D97 /* FTLJSCall.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = FTLJSCall.cpp; path = ftl/FTLJSCall.cpp; sourceTree = "<group>"; };
</span><span class="lines">@@ -5012,6 +5016,8 @@
</span><span class="cx"> 86EC9DC31328DF82002B2AD7 /* DFGSpeculativeJIT.h */,
</span><span class="cx"> 86880F1B14328BB900B08D42 /* DFGSpeculativeJIT32_64.cpp */,
</span><span class="cx"> 86880F4C14353B2100B08D42 /* DFGSpeculativeJIT64.cpp */,
</span><ins>+ 0F682FB019BCB36400FA3BAD /* DFGSSACalculator.cpp */,
+ 0F682FB119BCB36400FA3BAD /* DFGSSACalculator.h */,
</ins><span class="cx"> A7D89CF017A0B8CC00773AD8 /* DFGSSAConversionPhase.cpp */,
</span><span class="cx"> A7D89CF117A0B8CC00773AD8 /* DFGSSAConversionPhase.h */,
</span><span class="cx"> 0FC20CB718556A3500C9E954 /* DFGSSALoweringPhase.cpp */,
</span><span class="lines">@@ -6478,6 +6484,7 @@
</span><span class="cx"> 0FC314121814559100033232 /* RegisterSet.h in Headers */,
</span><span class="cx"> 0F50AF3C193E8B3900674EE8 /* DFGStructureClobberState.h in Headers */,
</span><span class="cx"> A57D23EE1891B5540031C7FA /* RegularExpression.h in Headers */,
</span><ins>+ 0F682FB319BCB36400FA3BAD /* DFGSSACalculator.h in Headers */,
</ins><span class="cx"> 0FB7F39D15ED8E4600F167B2 /* Reject.h in Headers */,
</span><span class="cx"> 0F2D4DEA19832DAC007D4B19 /* TypeLocation.h in Headers */,
</span><span class="cx"> A5BA15E8182340B300A82E69 /* RemoteInspector.h in Headers */,
</span><span class="lines">@@ -7221,6 +7228,7 @@
</span><span class="cx"> 2AACE63C18CA5A0300ED0191 /* GCActivityCallback.cpp in Sources */,
</span><span class="cx"> C2239D1716262BDD005AC5FD /* CopyVisitor.cpp in Sources */,
</span><span class="cx"> 0F2B66DE17B6B5AB00A7AE3F /* DataView.cpp in Sources */,
</span><ins>+ 0F682FB219BCB36400FA3BAD /* DFGSSACalculator.cpp in Sources */,
</ins><span class="cx"> 147F39C3107EC37600427A48 /* DateConstructor.cpp in Sources */,
</span><span class="cx"> 147F39C4107EC37600427A48 /* DateConversion.cpp in Sources */,
</span><span class="cx"> 147F39C5107EC37600427A48 /* DateInstance.cpp in Sources */,
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGAnalysish"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGAnalysis.h (173412 => 173413)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGAnalysis.h 2014-09-09 00:33:02 UTC (rev 173412)
+++ trunk/Source/JavaScriptCore/dfg/DFGAnalysis.h 2014-09-09 00:34:40 UTC (rev 173413)
</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, 2014 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></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGCSEPhasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGCSEPhase.cpp (173412 => 173413)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGCSEPhase.cpp 2014-09-09 00:33:02 UTC (rev 173412)
+++ trunk/Source/JavaScriptCore/dfg/DFGCSEPhase.cpp 2014-09-09 00:34:40 UTC (rev 173413)
</span><span class="lines">@@ -377,7 +377,7 @@
</span><span class="cx"> m_graph.initializeNodeOwners();
</span><span class="cx"> m_graph.m_dominators.computeIfNecessary(m_graph);
</span><span class="cx">
</span><del>- m_graph.getBlocksInPreOrder(m_preOrder);
</del><ins>+ m_preOrder = m_graph.blocksInPreOrder();
</ins><span class="cx">
</span><span class="cx"> // First figure out what gets clobbered by blocks. Node that this uses the preOrder list
</span><span class="cx"> // for convenience only.
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGDCEPhasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGDCEPhase.cpp (173412 => 173413)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGDCEPhase.cpp 2014-09-09 00:33:02 UTC (rev 173412)
+++ trunk/Source/JavaScriptCore/dfg/DFGDCEPhase.cpp 2014-09-09 00:34:40 UTC (rev 173413)
</span><span class="lines">@@ -116,10 +116,8 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> if (m_graph.m_form == SSA) {
</span><del>- Vector<BasicBlock*> depthFirst;
- m_graph.getBlocksInPreOrder(depthFirst);
- for (unsigned i = 0; i < depthFirst.size(); ++i)
- fixupBlock(depthFirst[i]);
</del><ins>+ for (BasicBlock* block : m_graph.blocksInPreOrder())
+ fixupBlock(block);
</ins><span class="cx"> } else {
</span><span class="cx"> RELEASE_ASSERT(m_graph.m_form == ThreadedCPS);
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGDominatorsh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGDominators.h (173412 => 173413)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGDominators.h 2014-09-09 00:33:02 UTC (rev 173412)
+++ trunk/Source/JavaScriptCore/dfg/DFGDominators.h 2014-09-09 00:34:40 UTC (rev 173413)
</span><span class="lines">@@ -57,6 +57,11 @@
</span><span class="cx"> return from == to || strictlyDominates(from, to);
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ BasicBlock* immediateDominatorOf(BasicBlock* block) const
+ {
+ return m_data[block].idomParent;
+ }
+
</ins><span class="cx"> template<typename Functor>
</span><span class="cx"> void forAllStrictDominatorsOf(BasicBlock* to, const Functor& functor) const
</span><span class="cx"> {
</span><span class="lines">@@ -119,14 +124,28 @@
</span><span class="cx"> void forAllBlocksInIteratedDominanceFrontierOf(
</span><span class="cx"> const BlockList& from, const Functor& functor)
</span><span class="cx"> {
</span><ins>+ forAllBlocksInPrunedIteratedDominanceFrontierOf(
+ from,
+ [&] (BasicBlock* block) -> bool {
+ functor(block);
+ return true;
+ });
+ }
+
+ // This is a close relative of forAllBlocksInIteratedDominanceFrontierOf(), which allows the
+ // given functor to return false to indicate that we don't wish to consider the given block.
+ // Useful for computing pruned SSA form.
+ template<typename Functor>
+ void forAllBlocksInPrunedIteratedDominanceFrontierOf(
+ const BlockList& from, const Functor& functor)
+ {
</ins><span class="cx"> BlockSet set;
</span><span class="cx"> forAllBlocksInIteratedDominanceFrontierOfImpl(
</span><span class="cx"> from,
</span><span class="cx"> [&] (BasicBlock* block) -> bool {
</span><span class="cx"> if (!set.add(block))
</span><span class="cx"> return false;
</span><del>- functor(block);
- return true;
</del><ins>+ return functor(block);
</ins><span class="cx"> });
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGGraphcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGGraph.cpp (173412 => 173413)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGGraph.cpp 2014-09-09 00:33:02 UTC (rev 173412)
+++ trunk/Source/JavaScriptCore/dfg/DFGGraph.cpp 2014-09-09 00:34:40 UTC (rev 173413)
</span><span class="lines">@@ -423,10 +423,10 @@
</span><span class="cx"> if (!context)
</span><span class="cx"> context = &myContext;
</span><span class="cx">
</span><del>- dataLog("\n");
- dataLog("DFG for ", CodeBlockWithJITType(m_codeBlock, JITCode::DFGJIT), ":\n");
- dataLog(" Fixpoint state: ", m_fixpointState, "; Form: ", m_form, "; Unification state: ", m_unificationState, "; Ref count state: ", m_refCountState, "\n");
- dataLog("\n");
</del><ins>+ out.print("\n");
+ out.print("DFG for ", CodeBlockWithJITType(m_codeBlock, JITCode::DFGJIT), ":\n");
+ out.print(" Fixpoint state: ", m_fixpointState, "; Form: ", m_form, "; Unification state: ", m_unificationState, "; Ref count state: ", m_refCountState, "\n");
+ out.print("\n");
</ins><span class="cx">
</span><span class="cx"> Node* lastNode = 0;
</span><span class="cx"> for (size_t b = 0; b < m_blocks.size(); ++b) {
</span><span class="lines">@@ -495,12 +495,12 @@
</span><span class="cx"> out.print(" Values: ", nodeMapDump(block->ssa->valuesAtTail, context), "\n");
</span><span class="cx"> break;
</span><span class="cx"> } }
</span><del>- dataLog("\n");
</del><ins>+ out.print("\n");
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> if (!myContext.isEmpty()) {
</span><del>- myContext.dump(WTF::dataFile());
- dataLog("\n");
</del><ins>+ myContext.dump(out);
+ out.print("\n");
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -626,8 +626,9 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><del>-void Graph::getBlocksInPreOrder(Vector<BasicBlock*>& result)
</del><ins>+BlockList Graph::blocksInPreOrder()
</ins><span class="cx"> {
</span><ins>+ BlockList result;
</ins><span class="cx"> BlockWorklist worklist;
</span><span class="cx"> worklist.push(block(0));
</span><span class="cx"> while (BasicBlock* block = worklist.pop()) {
</span><span class="lines">@@ -635,10 +636,12 @@
</span><span class="cx"> for (unsigned i = block->numSuccessors(); i--;)
</span><span class="cx"> worklist.push(block->successor(i));
</span><span class="cx"> }
</span><ins>+ return result;
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-void Graph::getBlocksInPostOrder(Vector<BasicBlock*>& result)
</del><ins>+BlockList Graph::blocksInPostOrder()
</ins><span class="cx"> {
</span><ins>+ BlockList result;
</ins><span class="cx"> PostOrderBlockWorklist worklist;
</span><span class="cx"> worklist.push(block(0));
</span><span class="cx"> while (BlockWithOrder item = worklist.pop()) {
</span><span class="lines">@@ -653,6 +656,7 @@
</span><span class="cx"> break;
</span><span class="cx"> }
</span><span class="cx"> }
</span><ins>+ return result;
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void Graph::clearReplacements()
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGGraphh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGGraph.h (173412 => 173413)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGGraph.h 2014-09-09 00:33:02 UTC (rev 173412)
+++ trunk/Source/JavaScriptCore/dfg/DFGGraph.h 2014-09-09 00:34:40 UTC (rev 173413)
</span><span class="lines">@@ -676,8 +676,8 @@
</span><span class="cx"> void clearReplacements();
</span><span class="cx"> void initializeNodeOwners();
</span><span class="cx">
</span><del>- void getBlocksInPreOrder(Vector<BasicBlock*>& result);
- void getBlocksInPostOrder(Vector<BasicBlock*>& result);
</del><ins>+ BlockList blocksInPreOrder();
+ BlockList blocksInPostOrder();
</ins><span class="cx">
</span><span class="cx"> Profiler::Compilation* compilation() { return m_plan.compilation.get(); }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGLICMPhasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp (173412 => 173413)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp 2014-09-09 00:33:02 UTC (rev 173412)
+++ trunk/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp 2014-09-09 00:34:40 UTC (rev 173413)
</span><span class="lines">@@ -150,16 +150,9 @@
</span><span class="cx"> //
</span><span class="cx"> // For maximum profit, we walk blocks in DFS order to ensure that we generally
</span><span class="cx"> // tend to hoist dominators before dominatees.
</span><del>- Vector<BasicBlock*> depthFirst;
- m_graph.getBlocksInPreOrder(depthFirst);
</del><span class="cx"> Vector<const NaturalLoop*> loopStack;
</span><span class="cx"> bool changed = false;
</span><del>- for (
- unsigned depthFirstIndex = 0;
- depthFirstIndex < depthFirst.size();
- ++depthFirstIndex) {
-
- BasicBlock* block = depthFirst[depthFirstIndex];
</del><ins>+ for (BasicBlock* block : m_graph.blocksInPreOrder()) {
</ins><span class="cx"> const NaturalLoop* loop = m_graph.m_naturalLoops.innerMostLoopOf(block);
</span><span class="cx"> if (!loop)
</span><span class="cx"> continue;
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGNodeFlagsh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGNodeFlags.h (173412 => 173413)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGNodeFlags.h 2014-09-09 00:33:02 UTC (rev 173412)
+++ trunk/Source/JavaScriptCore/dfg/DFGNodeFlags.h 2014-09-09 00:34:40 UTC (rev 173413)
</span><span class="lines">@@ -68,7 +68,7 @@
</span><span class="cx">
</span><span class="cx"> #define NodeRelevantToOSR 0x10000
</span><span class="cx">
</span><del>-#define NodeIsFlushed 0x20000 // Used by Graph::computeIsFlushed(), will tell you which local nodes are backwards-reachable from a Flush.
</del><ins>+#define NodeIsFlushed 0x20000 // Computed by CPSRethreadingPhase, will tell you which local nodes are backwards-reachable from a Flush.
</ins><span class="cx">
</span><span class="cx"> #define NodeMiscFlag1 0x40000
</span><span class="cx"> #define NodeMiscFlag2 0x80000
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGPhasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGPhase.cpp (173412 => 173413)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGPhase.cpp 2014-09-09 00:33:02 UTC (rev 173412)
+++ trunk/Source/JavaScriptCore/dfg/DFGPhase.cpp 2014-09-09 00:34:40 UTC (rev 173413)
</span><span class="lines">@@ -35,8 +35,15 @@
</span><span class="cx">
</span><span class="cx"> void Phase::beginPhase()
</span><span class="cx"> {
</span><ins>+ if (Options::verboseValidationFailure()) {
+ StringPrintStream out;
+ m_graph.dump(out);
+ m_graphDumpBeforePhase = out.toCString();
+ }
+
</ins><span class="cx"> if (!shouldDumpGraphAtEachPhase())
</span><span class="cx"> return;
</span><ins>+
</ins><span class="cx"> dataLog("Beginning DFG phase ", m_name, ".\n");
</span><span class="cx"> dataLog("Before ", m_name, ":\n");
</span><span class="cx"> m_graph.dump();
</span><span class="lines">@@ -46,7 +53,7 @@
</span><span class="cx"> {
</span><span class="cx"> if (!Options::validateGraphAtEachPhase())
</span><span class="cx"> return;
</span><del>- validate(m_graph, DumpGraph);
</del><ins>+ validate(m_graph, DumpGraph, m_graphDumpBeforePhase);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> } } // namespace JSC::DFG
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGPhaseh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGPhase.h (173412 => 173413)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGPhase.h 2014-09-09 00:33:02 UTC (rev 173412)
+++ trunk/Source/JavaScriptCore/dfg/DFGPhase.h 2014-09-09 00:34:40 UTC (rev 173413)
</span><span class="lines">@@ -67,6 +67,8 @@
</span><span class="cx"> // Call these hooks when starting and finishing.
</span><span class="cx"> void beginPhase();
</span><span class="cx"> void endPhase();
</span><ins>+
+ CString m_graphDumpBeforePhase;
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> template<typename PhaseType>
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGSSACalculatorcpp"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/dfg/DFGSSACalculator.cpp (0 => 173413)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGSSACalculator.cpp (rev 0)
+++ trunk/Source/JavaScriptCore/dfg/DFGSSACalculator.cpp 2014-09-09 00:34:40 UTC (rev 173413)
</span><span class="lines">@@ -0,0 +1,139 @@
</span><ins>+/*
+ * Copyright (C) 2014 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.
+ */
+
+#include "config.h"
+#include "DFGSSACalculator.h"
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGBlockMapInlines.h"
+#include <wtf/CommaPrinter.h>
+#include <wtf/ListDump.h>
+
+namespace JSC { namespace DFG {
+
+void SSACalculator::Variable::dump(PrintStream& out) const
+{
+ out.print("var", m_index);
+}
+
+void SSACalculator::Variable::dumpVerbose(PrintStream& out) const
+{
+ dump(out);
+ if (!m_blocksWithDefs.isEmpty()) {
+ out.print("(defs: ");
+ CommaPrinter comma;
+ for (BasicBlock* block : m_blocksWithDefs)
+ out.print(comma, *block);
+ out.print(")");
+ }
+}
+
+void SSACalculator::Def::dump(PrintStream& out) const
+{
+ out.print("def(", *m_variable, ", ", *m_block, ", ", m_value, ")");
+}
+
+SSACalculator::SSACalculator(Graph& graph)
+ : m_data(graph)
+ , m_graph(graph)
+{
+}
+
+SSACalculator::~SSACalculator()
+{
+}
+
+SSACalculator::Variable* SSACalculator::newVariable()
+{
+ return &m_variables.alloc(Variable(m_variables.size()));
+}
+
+SSACalculator::Def* SSACalculator::newDef(Variable* variable, BasicBlock* block, Node* value)
+{
+ Def* def = m_defs.add(Def(variable, block, value));
+ auto result = m_data[block].m_defs.add(variable, def);
+ if (result.isNewEntry)
+ variable->m_blocksWithDefs.append(block);
+ else
+ result.iterator->value = def;
+ return def;
+}
+
+SSACalculator::Def* SSACalculator::nonLocalReachingDef(BasicBlock* block, Variable* variable)
+{
+ return reachingDefAtTail(m_graph.m_dominators.immediateDominatorOf(block), variable);
+}
+
+SSACalculator::Def* SSACalculator::reachingDefAtTail(BasicBlock* block, Variable* variable)
+{
+ for (; block; block = m_graph.m_dominators.immediateDominatorOf(block)) {
+ if (Def* def = m_data[block].m_defs.get(variable))
+ return def;
+ }
+ return nullptr;
+}
+
+void SSACalculator::dump(PrintStream& out) const
+{
+ out.print("<Variables: [");
+ CommaPrinter comma;
+ for (unsigned i = 0; i < m_variables.size(); ++i) {
+ out.print(comma);
+ m_variables[i].dumpVerbose(out);
+ }
+ out.print("], Defs: [");
+ comma = CommaPrinter();
+ for (Def* def : const_cast<SSACalculator*>(this)->m_defs)
+ out.print(comma, *def);
+ out.print("], Phis: [");
+ comma = CommaPrinter();
+ for (Def* def : const_cast<SSACalculator*>(this)->m_phis)
+ out.print(comma, *def);
+ out.print("], Block data: [");
+ comma = CommaPrinter();
+ for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
+ BasicBlock* block = m_graph.block(blockIndex);
+ if (!block)
+ continue;
+
+ out.print(comma, *block, "=>(");
+ out.print("Defs: {");
+ CommaPrinter innerComma;
+ for (auto entry : m_data[block].m_defs)
+ out.print(innerComma, *entry.key, "->", *entry.value);
+ out.print("}, Phis: {");
+ innerComma = CommaPrinter();
+ for (Def* def : m_data[block].m_phis)
+ out.print(innerComma, *def);
+ out.print("})");
+ }
+ out.print("]>");
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGSSACalculatorh"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/dfg/DFGSSACalculator.h (0 => 173413)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGSSACalculator.h (rev 0)
+++ trunk/Source/JavaScriptCore/dfg/DFGSSACalculator.h 2014-09-09 00:34:40 UTC (rev 173413)
</span><span class="lines">@@ -0,0 +1,261 @@
</span><ins>+/*
+ * Copyright (C) 2014 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 DFGSSACalculator_h
+#define DFGSSACalculator_h
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGDominators.h"
+#include "DFGGraph.h"
+
+namespace JSC { namespace DFG {
+
+// SSACalculator provides a reusable tool for using the Cytron, Ferrante, Rosen, Wegman, and
+// Zadeck "Efficiently Computing Static Single Assignment Form and the Control Dependence Graph"
+// (TOPLAS'91) algorithm for computing SSA. SSACalculator doesn't magically do everything for you
+// but it maintains the major data structures and handles most of the non-local reasoning. Here's
+// the workflow of using SSACalculator to execute this algorithm:
+//
+// 0) Create a fresh SSACalculator instance. You will need this instance only for as long as
+// you're not yet done computing SSA.
+//
+// 1) Create an SSACalculator::Variable for every variable that you want to do Phi insertion
+// on. SSACalculator::Variable::index() is a dense indexing of the Variables that you
+// created, so you can easily use a Vector to map the SSACalculator::Variables to your
+// variables.
+//
+// 2) Create a SSACalculator::Def for every assignment to those variables. A Def knows about the
+// variable, the block, and the DFG::Node* that has the value being put into the variable.
+// Note that creating a Def in block B for variable V if block B already has a def for variable
+// V will overwrite the previous Def's DFG::Node* value. This enables you to create Defs by
+// processing basic blocks in forward order. If a block has multiple Defs of a variable, this
+// "just works" because each block will then remember the last Def of each variable.
+//
+// 3) Call SSACalculator::computePhis(). This takes a functor that will create the Phi nodes. The
+// functor returns either the Phi node it created, or nullptr, if it chooses to prune. (As an
+// aside, it's always sound not to prune, and the safest reason for pruning is liveness.) The
+// computePhis() code will record the created Phi nodes as Defs, and it will separately record
+// the list of Phis inserted at each block. It's OK for the functor you pass here to modify the
+// DFG::Graph on the fly, but the easiest way to write this is to just create the Phi nodes by
+// doing Graph::addNode() and return them. It's then best to insert all Phi nodes for a block
+// in bulk as part of the pass you do below, in step (4).
+//
+// 4) Modify the graph to create the SSA data flow. For each block, this should:
+//
+// 4.0) Compute the set of reaching defs (aka available values) for each variable by calling
+// SSACalculator::reachingDefAtHead() for each variable. Record this in a local table that
+// will be incrementally updated as you proceed through the block in forward order in the
+// next steps:
+//
+// FIXME: It might be better to compute reaching defs for all live variables in one go, to
+// avoid doing repeated dom tree traversals.
+// https://bugs.webkit.org/show_bug.cgi?id=136610
+//
+// 4.1) Insert all of the Phi nodes for the block by using SSACalculator::phisForBlock(), and
+// record those Phi nodes as being available values.
+//
+// 4.2) Process the block in forward order. For each load from a variable, replace it with the
+// available SSA value for that variable. For each store, delete it and record the stored
+// value as being available.
+//
+// Note that you have two options of how to replace loads with SSA values. You can replace
+// the load with an Identity node; this will end up working fairly naturally so long as
+// you run GCSE after your phase. Or, you can replace all uses of the load with the SSA
+// value yourself (using the Graph::performSubstitution() idiom), but that requires that
+// your loop over basic blocks proceeds in the appropriate graph order, for example
+// preorder.
+//
+// FIXME: Make it easier to do this, that doesn't involve rerunning GCSE.
+// https://bugs.webkit.org/show_bug.cgi?id=136639
+//
+// 4.3) Insert Upsilons for each Phi in each successor block. Use the available values table to
+// decide the source value for each Phi's variable. Note that you could also use
+// SSACalculator::reachingDefAtTail() instead of the available values table, though your
+// local available values table is likely to be more efficient.
+//
+// The most obvious use of SSACalculator is for the CPS->SSA conversion itself, but it's meant to
+// also be used for SSA update and for things like the promotion of heap fields to local SSA
+// variables.
+
+class SSACalculator {
+public:
+ SSACalculator(Graph&);
+ ~SSACalculator();
+
+ class Variable {
+ public:
+ unsigned index() const { return m_index; }
+
+ void dump(PrintStream&) const;
+ void dumpVerbose(PrintStream&) const;
+
+ private:
+ friend class SSACalculator;
+
+ Variable()
+ : m_index(UINT_MAX)
+ {
+ }
+
+ Variable(unsigned index)
+ : m_index(index)
+ {
+ }
+
+ BlockList m_blocksWithDefs;
+ unsigned m_index;
+ };
+
+ class Def {
+ public:
+ Variable* variable() const { return m_variable; }
+ BasicBlock* block() const { return m_block; }
+
+ Node* value() const { return m_value; }
+
+ void dump(PrintStream&) const;
+
+ private:
+ friend class SSACalculator;
+
+ Def()
+ : m_variable(nullptr)
+ , m_block(nullptr)
+ , m_value(nullptr)
+ {
+ }
+
+ Def(Variable* variable, BasicBlock* block, Node* value)
+ : m_variable(variable)
+ , m_block(block)
+ , m_value(value)
+ {
+ }
+
+ Variable* m_variable;
+ BasicBlock* m_block;
+ Node* m_value;
+ };
+
+ Variable* newVariable();
+ Def* newDef(Variable*, BasicBlock*, Node*);
+
+ Variable* variable(unsigned index) { return &m_variables[index]; }
+
+ // The PhiInsertionFunctor takes a Variable and a BasicBlock and either inserts a Phi and
+ // returns the Node for that Phi, or it decides that it's not worth it to insert a Phi at that
+ // block because of some additional pruning condition (typically liveness) and returns
+ // nullptr. If a non-null Node* is returned, a new Def is created, so that
+ // nonLocalReachingDef() will find it later. Note that it is generally always sound to not
+ // prune any Phis (that is, to always have the functor insert a Phi and never return nullptr).
+ template<typename PhiInsertionFunctor>
+ void computePhis(PhiInsertionFunctor functor)
+ {
+ DFG_ASSERT(m_graph, nullptr, m_graph.m_dominators.isValid());
+
+ for (Variable& variable : m_variables) {
+ m_graph.m_dominators.forAllBlocksInPrunedIteratedDominanceFrontierOf(
+ variable.m_blocksWithDefs,
+ [&] (BasicBlock* block) -> bool {
+ Node* phiNode = functor(&variable, block);
+ if (!phiNode)
+ return false;
+
+ BlockData& data = m_data[block];
+ Def* phiDef = m_phis.add(Def(&variable, block, phiNode));
+ data.m_phis.append(phiDef);
+
+ // Note that it's possible to have a block that looks like this before SSA
+ // conversion:
+ //
+ // label:
+ // print(x);
+ // ...
+ // x = 42;
+ // goto label;
+ //
+ // And it may look like this after SSA conversion:
+ //
+ // label:
+ // x1: Phi()
+ // ...
+ // Upsilon(42, ^x1)
+ // goto label;
+ //
+ // In this case, we will want to insert a Phi in this block, and the block
+ // will already have a Def for the variable. When this happens, we don't want
+ // the Phi to override the original Def, since the Phi is at the top, the
+ // original Def in the m_defs table would have been at the bottom, and we want
+ // m_defs to tell us about defs at tail.
+ //
+ // So, we rely on the fact that HashMap::add() does nothing if the key was
+ // already present.
+ data.m_defs.add(&variable, phiDef);
+ return true;
+ });
+ }
+ }
+
+ const Vector<Def*>& phisForBlock(BasicBlock* block)
+ {
+ return m_data[block].m_phis;
+ }
+
+ // Ignores defs within the given block; it assumes that you've taken care of those
+ // yourself.
+ Def* nonLocalReachingDef(BasicBlock*, Variable*);
+ Def* reachingDefAtHead(BasicBlock* block, Variable* variable)
+ {
+ return nonLocalReachingDef(block, variable);
+ }
+
+ // Considers the def within the given block, but only works at the tail of the block.
+ Def* reachingDefAtTail(BasicBlock*, Variable*);
+
+ void dump(PrintStream&) const;
+
+private:
+ SegmentedVector<Variable> m_variables;
+ Bag<Def> m_defs;
+
+ Bag<Def> m_phis;
+
+ struct BlockData {
+ HashMap<Variable*, Def*> m_defs;
+ Vector<Def*> m_phis;
+ };
+
+ BlockMap<BlockData> m_data;
+
+ Graph& m_graph;
+};
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGSSACalculator_h
+
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGSSAConversionPhasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGSSAConversionPhase.cpp (173412 => 173413)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGSSAConversionPhase.cpp 2014-09-09 00:33:02 UTC (rev 173412)
+++ trunk/Source/JavaScriptCore/dfg/DFGSSAConversionPhase.cpp 2014-09-09 00:34:40 UTC (rev 173413)
</span><span class="lines">@@ -32,19 +32,20 @@
</span><span class="cx"> #include "DFGGraph.h"
</span><span class="cx"> #include "DFGInsertionSet.h"
</span><span class="cx"> #include "DFGPhase.h"
</span><ins>+#include "DFGSSACalculator.h"
+#include "DFGVariableAccessDataDump.h"
</ins><span class="cx"> #include "JSCInlines.h"
</span><span class="cx">
</span><span class="cx"> namespace JSC { namespace DFG {
</span><span class="cx">
</span><span class="cx"> class SSAConversionPhase : public Phase {
</span><span class="cx"> static const bool verbose = false;
</span><del>- static const bool dumpGraph = false;
</del><span class="cx">
</span><span class="cx"> public:
</span><span class="cx"> SSAConversionPhase(Graph& graph)
</span><span class="cx"> : Phase(graph, "SSA conversion")
</span><ins>+ , m_calculator(graph)
</ins><span class="cx"> , m_insertionSet(graph)
</span><del>- , m_changed(false)
</del><span class="cx"> {
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -52,297 +53,283 @@
</span><span class="cx"> {
</span><span class="cx"> RELEASE_ASSERT(m_graph.m_form == ThreadedCPS);
</span><span class="cx">
</span><del>- if (dumpGraph) {
- dataLog("Graph dump at top of SSA conversion:\n");
</del><ins>+ m_graph.clearReplacements();
+ m_graph.m_dominators.computeIfNecessary(m_graph);
+
+ if (verbose) {
+ dataLog("Graph before SSA transformation:\n");
</ins><span class="cx"> m_graph.dump();
</span><span class="cx"> }
</span><ins>+
+ // Create a SSACalculator::Variable for every root VariableAccessData.
+ for (VariableAccessData& variable : m_graph.m_variableAccessData) {
+ if (!variable.isRoot() || variable.isCaptured())
+ continue;
+
+ SSACalculator::Variable* ssaVariable = m_calculator.newVariable();
+ ASSERT(ssaVariable->index() == m_variableForSSAIndex.size());
+ m_variableForSSAIndex.append(&variable);
+ m_ssaVariableForVariable.add(&variable, ssaVariable);
+ }
</ins><span class="cx">
</span><del>- // Eliminate all duplicate or self-pointing Phi edges. This means that
- // we transform:
- //
- // p: Phi(@n1, @n2, @n3)
- //
- // into:
- //
- // p: Phi(@x)
- //
- // if each @ni in {@n1, @n2, @n3} is either equal to @p to is equal
- // to @x, for exactly one other @x. Additionally, trivial Phis (i.e.
- // p: Phi(@x)) are forwarded, so that if have an edge to such @p, we
- // replace it with @x. This loop does this for Phis only; later we do
- // such forwarding for Phi references found in other nodes.
- //
- // See Aycock and Horspool in CC'00 for a better description of what
- // we're doing here.
- do {
- m_changed = false;
- for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
- BasicBlock* block = m_graph.block(blockIndex);
- if (!block)
- continue;
- for (unsigned phiIndex = block->phis.size(); phiIndex--;) {
- Node* phi = block->phis[phiIndex];
- if (phi->variableAccessData()->isCaptured())
- continue;
- forwardPhiChildren(phi);
- deduplicateChildren(phi);
- }
- }
- } while (m_changed);
-
- // For each basic block, for each local live at the head of that block,
- // figure out what node we should be referring to instead of that local.
- // If it turns out to be a non-trivial Phi, make sure that we create an
- // SSA Phi and Upsilons in predecessor blocks. We reuse
- // BasicBlock::variablesAtHead for tracking which nodes to refer to.
- Operands<bool> nonTrivialPhis(OperandsLike, m_graph.block(0)->variablesAtHead);
</del><ins>+ // Find all SetLocals and create Defs for them. We handle SetArgument by creating a
+ // GetArgument.
</ins><span class="cx"> for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
</span><span class="cx"> BasicBlock* block = m_graph.block(blockIndex);
</span><span class="cx"> if (!block)
</span><span class="cx"> continue;
</span><del>-
- nonTrivialPhis.fill(false);
- for (unsigned i = block->phis.size(); i--;) {
- Node* phi = block->phis[i];
- if (!phi->children.justOneChild())
- nonTrivialPhis.operand(phi->local()) = true;
- }
-
- for (unsigned i = block->variablesAtHead.size(); i--;) {
- Node* node = block->variablesAtHead[i];
- if (!node)
</del><ins>+
+ // Must process the block in forward direction because we want to see the last
+ // assignment for every local.
+ for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
+ Node* node = block->at(nodeIndex);
+ if (node->op() != SetLocal && node->op() != SetArgument)
</ins><span class="cx"> continue;
</span><span class="cx">
</span><del>- if (verbose)
- dataLog("At block #", blockIndex, " for operand r", block->variablesAtHead.operandForIndex(i), " have node ", node, "\n");
-
</del><span class="cx"> VariableAccessData* variable = node->variableAccessData();
</span><del>- if (variable->isCaptured()) {
- // Poison this entry in variablesAtHead because we don't
- // want anyone to try to refer to it, if the variable is
- // captured.
- block->variablesAtHead[i] = 0;
</del><ins>+ if (variable->isCaptured())
</ins><span class="cx"> continue;
</span><del>- }
</del><span class="cx">
</span><del>- switch (node->op()) {
- case Phi:
- case SetArgument:
- break;
- case Flush:
- case GetLocal:
- case PhantomLocal:
- node = node->child1().node();
- break;
- default:
- RELEASE_ASSERT_NOT_REACHED();
</del><ins>+ Node* childNode;
+ if (node->op() == SetLocal)
+ childNode = node->child1().node();
+ else {
+ ASSERT(node->op() == SetArgument);
+ childNode = m_insertionSet.insertNode(
+ nodeIndex, node->variableAccessData()->prediction(),
+ GetArgument, node->origin, OpInfo(node->variableAccessData()));
</ins><span class="cx"> }
</span><del>- RELEASE_ASSERT(node->op() == Phi || node->op() == SetArgument);
</del><span class="cx">
</span><del>- bool isFlushed = !!(node->flags() & NodeIsFlushed);
-
- if (node->op() == Phi) {
- if (!nonTrivialPhis.operand(node->local())) {
- Edge edge = node->children.justOneChild();
- ASSERT(edge);
- if (verbose)
- dataLog(" One child: ", edge, ", ", RawPointer(edge.node()), "\n");
- node = edge.node(); // It's something from a different basic block.
- } else {
- if (verbose)
- dataLog(" Non-trivial.\n");
- // It's a non-trivial Phi.
- FlushFormat format = variable->flushFormat();
- NodeFlags result = resultFor(format);
- UseKind useKind = useKindFor(format);
-
- node = m_insertionSet.insertNode(0, SpecNone, Phi, NodeOrigin());
- if (verbose)
- dataLog(" Inserted new node: ", node, "\n");
- node->mergeFlags(result);
- RELEASE_ASSERT((node->flags() & NodeResultMask) == result);
-
- for (unsigned j = block->predecessors.size(); j--;) {
- BasicBlock* predecessor = block->predecessors[j];
- predecessor->appendNonTerminal(
- m_graph, SpecNone, Upsilon, predecessor->last()->origin,
- OpInfo(node), Edge(predecessor->variablesAtTail[i], useKind));
- }
-
- if (isFlushed) {
- // Do nothing. For multiple reasons.
-
- // Reason #1: If the local is flushed then we don't need to bother
- // with a MovHint since every path to this point in the code will
- // have flushed the bytecode variable using a SetLocal and hence
- // the Availability::flushedAt() will agree, and that will be
- // sufficient for figuring out how to recover the variable's value.
-
- // Reason #2: If we had inserted a MovHint and the Phi function had
- // died (because the only user of the value was the "flush" - i.e.
- // some asynchronous runtime thingy) then the MovHint would turn
- // into a ZombieHint, which would fool us into thinking that the
- // variable is dead.
-
- // Reason #3: If we had inserted a MovHint then even if the Phi
- // stayed alive, we would still end up generating inefficient code
- // since we would be telling the OSR exit compiler to use some SSA
- // value for the bytecode variable rather than just telling it that
- // the value was already on the stack.
- } else {
- m_insertionSet.insertNode(
- 0, SpecNone, MovHint, NodeOrigin(),
- OpInfo(variable->local().offset()), node->defaultEdge());
- }
- }
- }
-
- block->variablesAtHead[i] = node;
</del><ins>+ m_calculator.newDef(
+ m_ssaVariableForVariable.get(variable), block, childNode);
</ins><span class="cx"> }
</span><del>-
</del><ins>+
</ins><span class="cx"> m_insertionSet.execute(block);
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ // Decide where Phis are to be inserted. This creates the Phi's but doesn't insert them
+ // yet. We will later know where to insert them because SSACalculator is such a bro.
+ m_calculator.computePhis(
+ [&] (SSACalculator::Variable* ssaVariable, BasicBlock* block) -> Node* {
+ VariableAccessData* variable = m_variableForSSAIndex[ssaVariable->index()];
+
+ // Prune by liveness. This doesn't buy us much other than compile times.
+ Node* headNode = block->variablesAtHead.operand(variable->local());
+ if (!headNode)
+ return nullptr;
+
+ // There is the possibiltiy of "rebirths". The SSA calculator will already prune
+ // rebirths for the same VariableAccessData. But it will not be able to prune
+ // rebirths that arose from the same local variable number but a different
+ // VariableAccessData. We do that pruning here.
+ //
+ // Here's an example of a rebirth that this would catch:
+ //
+ // var x;
+ // if (foo) {
+ // if (bar) {
+ // x = 42;
+ // } else {
+ // x = 43;
+ // }
+ // print(x);
+ // x = 44;
+ // } else {
+ // x = 45;
+ // }
+ // print(x); // Without this check, we'd have a Phi for x = 42|43 here.
+ //
+ // FIXME: Consider feeding local variable numbers, not VariableAccessData*'s, as
+ // the "variables" for SSACalculator. That would allow us to eliminate this
+ // special case.
+ // https://bugs.webkit.org/show_bug.cgi?id=136641
+ if (headNode->variableAccessData() != variable)
+ return nullptr;
+
+ Node* phiNode = m_graph.addNode(
+ variable->prediction(), Phi, NodeOrigin());
+ FlushFormat format = variable->flushFormat();
+ NodeFlags result = resultFor(format);
+ phiNode->mergeFlags(result);
+ return phiNode;
+ });
+
</ins><span class="cx"> if (verbose) {
</span><del>- dataLog("Variables at head after SSA Phi insertion:\n");
- for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
- BasicBlock* block = m_graph.block(blockIndex);
- if (!block)
- continue;
- dataLog(" ", *block, ": ", block->variablesAtHead, "\n");
- }
</del><ins>+ dataLog("Computed Phis, about to transform the graph.\n");
+ dataLog("\n");
+ dataLog("Graph:\n");
+ m_graph.dump();
+ dataLog("\n");
+ dataLog("Mappings:\n");
+ for (unsigned i = 0; i < m_variableForSSAIndex.size(); ++i)
+ dataLog(" ", i, ": ", VariableAccessDataDump(m_graph, m_variableForSSAIndex[i]), "\n");
+ dataLog("\n");
+ dataLog("SSA calculator: ", m_calculator, "\n");
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- // At this point variablesAtHead in each block refers to either:
</del><ins>+ // Do the bulk of the SSA conversion. For each block, this tracks the operand->Node
+ // mapping based on a combination of what the SSACalculator tells us, and us walking over
+ // the block in forward order. We use our own data structure, valueForOperand, for
+ // determining the local mapping, but we rely on SSACalculator for the non-local mapping.
</ins><span class="cx"> //
</span><del>- // 1) A new SSA phi in the current block.
- // 2) A SetArgument, which will soon get converted into a GetArgument.
- // 3) An old CPS phi in a different block.
</del><ins>+ // This does three things at once:
</ins><span class="cx"> //
</span><del>- // We don't have to do anything for (1) and (2), but we do need to
- // do a replacement for (3).
-
- // Clear all replacements, since other phases may have used them.
- m_graph.clearReplacements();
-
- if (dumpGraph) {
- dataLog("Graph just before identifying replacements:\n");
- m_graph.dump();
- }
-
- // For all of the old CPS Phis, figure out what they correspond to in SSA.
- for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
- BasicBlock* block = m_graph.block(blockIndex);
- if (!block)
- continue;
- if (verbose)
- dataLog("Dealing with block #", blockIndex, "\n");
- for (unsigned phiIndex = block->phis.size(); phiIndex--;) {
- Node* phi = block->phis[phiIndex];
- if (verbose) {
- dataLog(
- "Considering ", phi, " (", RawPointer(phi), "), for r",
- phi->local(), ", and its replacement in ", *block, ", ",
- block->variablesAtHead.operand(phi->local()), "\n");
</del><ins>+ // - Inserts the Phis in all of the places where they need to go. We've already created
+ // them and they are accounted for in the SSACalculator's data structures, but we
+ // haven't inserted them yet, mostly because we want to insert all of a block's Phis in
+ // one go to amortize the cost of node insertion.
+ //
+ // - Create and insert Upsilons.
+ //
+ // - Convert all of the preexisting SSA nodes (other than the old CPS Phi nodes) into SSA
+ // form by replacing as follows:
+ //
+ // - GetLocal over captured variables lose their phis.
+ //
+ // - GetLocal over uncaptured variables die and get replaced with references to the node
+ // specified by valueForOperand.
+ //
+ // - SetLocal gets NodeMustGenerate if it's flushed, or turns into a Check otherwise.
+ //
+ // - Flush loses its children and turns into a Phantom.
+ //
+ // - PhantomLocal becomes Phantom, and its child is whatever is specified by
+ // valueForOperand.
+ //
+ // - SetArgument is removed unless it's a captured variable. Note that GetArgument nodes
+ // have already been inserted.
+ Operands<Node*> valueForOperand(OperandsLike, m_graph.block(0)->variablesAtHead);
+ for (BasicBlock* block : m_graph.blocksInPreOrder()) {
+ valueForOperand.clear();
+
+ // CPS will claim that the root block has all arguments live. But we have already done
+ // the first step of SSA conversion: argument locals are no longer live at head;
+ // instead we have GetArgument nodes for extracting the values of arguments. So, we
+ // skip the at-head available value calculation for the root block.
+ if (block != m_graph.block(0)) {
+ for (size_t i = valueForOperand.size(); i--;) {
+ Node* nodeAtHead = block->variablesAtHead[i];
+ if (!nodeAtHead)
+ continue;
+
+ VariableAccessData* variable = nodeAtHead->variableAccessData();
+ if (variable->isCaptured())
+ continue;
+
+ if (verbose)
+ dataLog("Considering live variable ", VariableAccessDataDump(m_graph, variable), " at head of block ", *block, "\n");
+
+ SSACalculator::Variable* ssaVariable = m_ssaVariableForVariable.get(variable);
+ SSACalculator::Def* def = m_calculator.reachingDefAtHead(block, ssaVariable);
+ if (!def) {
+ // If we are required to insert a Phi, then we won't have a reaching def
+ // at head.
+ continue;
+ }
+
+ Node* node = def->value();
+ if (node->replacement) {
+ // This will occur when a SetLocal had a GetLocal as its source. The
+ // GetLocal would get replaced with an actual SSA value by the time we get
+ // here. Note that the SSA value with which the GetLocal got replaced
+ // would not in turn have a replacement.
+ node = node->replacement;
+ ASSERT(!node->replacement);
+ }
+ if (verbose)
+ dataLog("Mapping: r", valueForOperand.operandForIndex(i), " -> ", node, "\n");
+ valueForOperand[i] = node;
</ins><span class="cx"> }
</span><del>- ASSERT(phi != block->variablesAtHead.operand(phi->local()));
- phi->replacement = block->variablesAtHead.operand(phi->local());
</del><span class="cx"> }
</span><del>- }
-
- // Now make sure that all variablesAtHead in each block points to the
- // canonical SSA value. Prior to this, variablesAtHead[local] may point to
- // an old CPS Phi in a different block.
- for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
- BasicBlock* block = m_graph.block(blockIndex);
- if (!block)
- continue;
- for (size_t i = block->variablesAtHead.size(); i--;) {
- Node* node = block->variablesAtHead[i];
- if (!node)
- continue;
- while (node->replacement) {
- ASSERT(node != node->replacement);
- node = node->replacement;
</del><ins>+
+ // Insert Phis by asking the calculator what phis there are in this block. Also update
+ // valueForOperand with those Phis. For Phis associated with variables that are not
+ // flushed, we also insert a MovHint.
+ size_t phiInsertionPoint = 0;
+ for (SSACalculator::Def* phiDef : m_calculator.phisForBlock(block)) {
+ VariableAccessData* variable = m_variableForSSAIndex[phiDef->variable()->index()];
+
+ // Figure out if the local is meant to be flushed here.
+ bool isFlushed = !!(
+ block->variablesAtHead.operand(variable->local())->flags() & NodeIsFlushed);
+
+ m_insertionSet.insert(phiInsertionPoint, phiDef->value());
+ valueForOperand.operand(variable->local()) = phiDef->value();
+
+ if (isFlushed) {
+ // Do nothing. For multiple reasons.
+
+ // Reason #1: If the local is flushed then we don't need to bother with a
+ // MovHint since every path to this point in the code will have flushed the
+ // bytecode variable using a SetLocal and hence the Availability::flushedAt()
+ // will agree, and that will be sufficient for figuring out how to recover the
+ // variable's value.
+
+ // Reason #2: If we had inserted a MovHint and the Phi function had died
+ // (because the only user of the value was the "flush" - i.e. some
+ // asynchronous runtime thingy) then the MovHint would turn into a ZombieHint,
+ // which would fool us into thinking that the variable is dead. Note that this
+ // reason has a lot to do with the fact that Flushes do not turn into
+ // Phantoms, because our handling of Flushes assume that we (1) always leave
+ // the flushed SetLocals alone and (2) OSR availability analysis always sees
+ // the available flush. The presence of a MovHint or ZombieHint would make the
+ // flush seem unavailable.
+
+ // Reason #3: If we had inserted a MovHint then even if the Phi stayed alive,
+ // we would still end up generating inefficient code since we would be telling
+ // the OSR exit compiler to use some SSA value for the bytecode variable
+ // rather than just telling it that the value was already on the stack.
+ } else {
+ m_insertionSet.insertNode(
+ phiInsertionPoint, SpecNone, MovHint, NodeOrigin(),
+ OpInfo(variable->local().offset()), phiDef->value()->defaultEdge());
</ins><span class="cx"> }
</span><del>- block->variablesAtHead[i] = node;
</del><span class="cx"> }
</span><del>- }
-
- if (verbose) {
- dataLog("Variables at head after convergence:\n");
- for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
- BasicBlock* block = m_graph.block(blockIndex);
- if (!block)
- continue;
- dataLog(" ", *block, ": ", block->variablesAtHead, "\n");
- }
- }
-
- // Convert operations over locals into operations over SSA nodes.
- // - GetLocal over captured variables lose their phis.
- // - GetLocal over uncaptured variables die and get replaced with references
- // to the node specified by variablesAtHead.
- // - SetLocal gets NodeMustGenerate if it's flushed, or turns into a
- // Check otherwise.
- // - Flush loses its children and turns into a Phantom.
- // - PhantomLocal becomes Phantom, and its child is whatever is specified
- // by variablesAtHead.
- // - SetArgument turns into GetArgument unless it's a captured variable.
- // - Upsilons get their children fixed to refer to the true value of that local
- // at the end of the block. Prior to this loop, Upsilons will refer to
- // variableAtTail[operand], which may be any of Flush, PhantomLocal, GetLocal,
- // SetLocal, SetArgument, or Phi. We accomplish this by setting the
- // replacement pointers of all of those nodes to refer to either
- // variablesAtHead[operand], or the child of the SetLocal.
- for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
- BasicBlock* block = m_graph.block(blockIndex);
- if (!block)
- continue;
</del><span class="cx">
</span><del>- for (unsigned phiIndex = block->phis.size(); phiIndex--;) {
- block->phis[phiIndex]->replacement =
- block->variablesAtHead.operand(block->phis[phiIndex]->local());
- }
- for (unsigned nodeIndex = block->size(); nodeIndex--;)
- ASSERT(!block->at(nodeIndex)->replacement);
-
</del><span class="cx"> for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
</span><span class="cx"> Node* node = block->at(nodeIndex);
</span><span class="cx">
</span><ins>+ if (verbose) {
+ dataLog("Processing node ", node, ":\n");
+ m_graph.dump(WTF::dataFile(), " ", node);
+ }
+
</ins><span class="cx"> m_graph.performSubstitution(node);
</span><span class="cx">
</span><span class="cx"> switch (node->op()) {
</span><span class="cx"> case SetLocal: {
</span><span class="cx"> VariableAccessData* variable = node->variableAccessData();
</span><ins>+
</ins><span class="cx"> if (variable->isCaptured() || !!(node->flags() & NodeIsFlushed))
</span><span class="cx"> node->mergeFlags(NodeMustGenerate);
</span><span class="cx"> else
</span><span class="cx"> node->setOpAndDefaultFlags(Check);
</span><del>- node->replacement = node->child1().node(); // Only for Upsilons.
</del><ins>+
+ if (!variable->isCaptured()) {
+ if (verbose)
+ dataLog("Mapping: r", variable->local(), " -> ", node->child1().node(), "\n");
+ valueForOperand.operand(variable->local()) = node->child1().node();
+ }
</ins><span class="cx"> break;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> case GetLocal: {
</span><del>- // It seems tempting to just do forwardPhi(GetLocal), except that we
- // could have created a new (SSA) Phi, and the GetLocal could still be
- // referring to an old (CPS) Phi. Uses variablesAtHead to tell us what
- // to refer to.
</del><span class="cx"> node->children.reset();
</span><ins>+
</ins><span class="cx"> VariableAccessData* variable = node->variableAccessData();
</span><span class="cx"> if (variable->isCaptured())
</span><span class="cx"> break;
</span><ins>+
</ins><span class="cx"> node->convertToPhantom();
</span><del>- node->replacement = block->variablesAtHead.operand(variable->local());
</del><ins>+ if (verbose)
+ dataLog("Replacing node ", node, " with ", valueForOperand.operand(variable->local()), "\n");
+ node->replacement = valueForOperand.operand(variable->local());
</ins><span class="cx"> break;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> case Flush: {
</span><span class="cx"> node->children.reset();
</span><span class="cx"> node->convertToPhantom();
</span><del>- // This is only for Upsilons. An Upsilon will only refer to a Flush if
- // there were no SetLocals or GetLocals in the block.
- node->replacement = block->variablesAtHead.operand(node->local());
</del><span class="cx"> break;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -360,14 +347,9 @@
</span><span class="cx"> // local wouldn't have been computed by the Phi reduction algorithm
</span><span class="cx"> // above.
</span><span class="cx"> node->children.reset();
</span><del>- } else {
- node->child1() =
- block->variablesAtHead.operand(variable->local())->defaultEdge();
- }
</del><ins>+ } else
+ node->child1() = valueForOperand.operand(variable->local())->defaultEdge();
</ins><span class="cx"> node->convertToPhantom();
</span><del>- // This is only for Upsilons. An Upsilon will only refer to a
- // PhantomLocal if there were no SetLocals or GetLocals in the block.
- node->replacement = block->variablesAtHead.operand(variable->local());
</del><span class="cx"> break;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -375,15 +357,48 @@
</span><span class="cx"> VariableAccessData* variable = node->variableAccessData();
</span><span class="cx"> if (variable->isCaptured())
</span><span class="cx"> break;
</span><del>- node->setOpAndDefaultFlags(GetArgument);
- node->setResult(resultFor(node->variableAccessData()->flushFormat()));
</del><ins>+ node->convertToPhantom();
</ins><span class="cx"> break;
</span><span class="cx"> }
</span><del>-
</del><ins>+
+ case GetArgument: {
+ VariableAccessData* variable = node->variableAccessData();
+ ASSERT(!variable->isCaptured());
+ if (verbose)
+ dataLog("Mapping: r", variable->local(), " -> ", node, "\n");
+ valueForOperand.operand(variable->local()) = node;
+ break;
+ }
+
</ins><span class="cx"> default:
</span><span class="cx"> break;
</span><span class="cx"> }
</span><span class="cx"> }
</span><ins>+
+ // We want to insert Upsilons just before the end of the block. On the surface this
+ // seems dangerous because the Upsilon will have a checking UseKind. But, we will not
+ // actually be performing the check at the point of the Upsilon; the check will
+ // already have been performed at the point where the original SetLocal was.
+ size_t upsilonInsertionPoint = block->size() - 1;
+ NodeOrigin upsilonOrigin = block->last()->origin;
+ for (unsigned successorIndex = block->numSuccessors(); successorIndex--;) {
+ BasicBlock* successorBlock = block->successor(successorIndex);
+ for (SSACalculator::Def* phiDef : m_calculator.phisForBlock(successorBlock)) {
+ Node* phiNode = phiDef->value();
+ SSACalculator::Variable* ssaVariable = phiDef->variable();
+ VariableAccessData* variable = m_variableForSSAIndex[ssaVariable->index()];
+ FlushFormat format = variable->flushFormat();
+ UseKind useKind = useKindFor(format);
+
+ m_insertionSet.insertNode(
+ upsilonInsertionPoint, SpecNone, Upsilon, upsilonOrigin,
+ OpInfo(phiNode), Edge(
+ valueForOperand.operand(variable->local()),
+ useKind));
+ }
+ }
+
+ m_insertionSet.execute(block);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> // Free all CPS phis and reset variables vectors.
</span><span class="lines">@@ -404,74 +419,20 @@
</span><span class="cx"> m_graph.m_arguments.clear();
</span><span class="cx">
</span><span class="cx"> m_graph.m_form = SSA;
</span><del>- return true;
- }
</del><span class="cx">
</span><del>-private:
- void forwardPhiChildren(Node* node)
- {
- for (unsigned i = 0; i < AdjacencyList::Size; ++i) {
- Edge& edge = node->children.child(i);
- if (!edge)
- break;
- m_changed |= forwardPhiEdge(edge);
</del><ins>+ if (verbose) {
+ dataLog("Graph after SSA transformation:\n");
+ m_graph.dump();
</ins><span class="cx"> }
</span><del>- }
-
- Node* forwardPhi(Node* node)
- {
- for (;;) {
- switch (node->op()) {
- case Phi: {
- Edge edge = node->children.justOneChild();
- if (!edge)
- return node;
- node = edge.node();
- break;
- }
- case GetLocal:
- case SetLocal:
- if (node->variableAccessData()->isCaptured())
- return node;
- node = node->child1().node();
- break;
- default:
- return node;
- }
- }
- }
-
- bool forwardPhiEdge(Edge& edge)
- {
- Node* newNode = forwardPhi(edge.node());
- if (newNode == edge.node())
- return false;
- edge.setNode(newNode);
</del><ins>+
</ins><span class="cx"> return true;
</span><span class="cx"> }
</span><del>-
- void deduplicateChildren(Node* node)
- {
- for (unsigned i = 0; i < AdjacencyList::Size; ++i) {
- Edge edge = node->children.child(i);
- if (!edge)
- break;
- if (edge == node) {
- node->children.removeEdge(i--);
- m_changed = true;
- continue;
- }
- for (unsigned j = i + 1; j < AdjacencyList::Size; ++j) {
- if (node->children.child(j) == edge) {
- node->children.removeEdge(j--);
- m_changed = true;
- }
- }
- }
- }
-
</del><ins>+
+private:
+ SSACalculator m_calculator;
</ins><span class="cx"> InsertionSet m_insertionSet;
</span><del>- bool m_changed;
</del><ins>+ HashMap<VariableAccessData*, SSACalculator::Variable*> m_ssaVariableForVariable;
+ Vector<VariableAccessData*> m_variableForSSAIndex;
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> bool performSSAConversion(Graph& graph)
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGSSAConversionPhaseh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGSSAConversionPhase.h (173412 => 173413)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGSSAConversionPhase.h 2014-09-09 00:33:02 UTC (rev 173412)
+++ trunk/Source/JavaScriptCore/dfg/DFGSSAConversionPhase.h 2014-09-09 00:34:40 UTC (rev 173413)
</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, 2014 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">@@ -34,10 +34,9 @@
</span><span class="cx">
</span><span class="cx"> // Convert ThreadedCPS form into SSA form. This results in a form that has:
</span><span class="cx"> //
</span><del>-// - Roughly minimal Phi's. We use the Aycock & Horspool fixpoint for
-// converting the CPS maximal Phis into SSA minimal Phis, with the caveat
-// that irreducible control flow may result in some missed opportunities
-// for Phi reduction.
</del><ins>+// - Minimal Phi's. We use the the Cytron et al (TOPLAS'91) algorithm for
+// Phi insertion. Most of the algorithm is implemented in SSACalculator
+// and Dominators.
</ins><span class="cx"> //
</span><span class="cx"> // - No uses of GetLocal/SetLocal except for captured variables and flushes.
</span><span class="cx"> // After this, any remaining SetLocal means Flush. PhantomLocals become
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGValidatecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGValidate.cpp (173412 => 173413)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGValidate.cpp 2014-09-09 00:33:02 UTC (rev 173412)
+++ trunk/Source/JavaScriptCore/dfg/DFGValidate.cpp 2014-09-09 00:34:40 UTC (rev 173413)
</span><span class="lines">@@ -38,9 +38,10 @@
</span><span class="cx">
</span><span class="cx"> class Validate {
</span><span class="cx"> public:
</span><del>- Validate(Graph& graph, GraphDumpMode graphDumpMode)
</del><ins>+ Validate(Graph& graph, GraphDumpMode graphDumpMode, CString graphDumpBeforePhase)
</ins><span class="cx"> : m_graph(graph)
</span><span class="cx"> , m_graphDumpMode(graphDumpMode)
</span><ins>+ , m_graphDumpBeforePhase(graphDumpBeforePhase)
</ins><span class="cx"> {
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -266,6 +267,7 @@
</span><span class="cx"> private:
</span><span class="cx"> Graph& m_graph;
</span><span class="cx"> GraphDumpMode m_graphDumpMode;
</span><ins>+ CString m_graphDumpBeforePhase;
</ins><span class="cx">
</span><span class="cx"> HashMap<Node*, unsigned> m_myRefCounts;
</span><span class="cx"> HashSet<Node*> m_acceptableNodes;
</span><span class="lines">@@ -564,14 +566,19 @@
</span><span class="cx"> {
</span><span class="cx"> if (m_graphDumpMode == DontDumpGraph)
</span><span class="cx"> return;
</span><ins>+ dataLog("\n");
+ if (!m_graphDumpBeforePhase.isNull()) {
+ dataLog("Before phase:\n");
+ dataLog(m_graphDumpBeforePhase);
+ }
</ins><span class="cx"> dataLog("At time of failure:\n");
</span><span class="cx"> m_graph.dump();
</span><span class="cx"> }
</span><span class="cx"> };
</span><span class="cx">
</span><del>-void validate(Graph& graph, GraphDumpMode graphDumpMode)
</del><ins>+void validate(Graph& graph, GraphDumpMode graphDumpMode, CString graphDumpBeforePhase)
</ins><span class="cx"> {
</span><del>- Validate validationObject(graph, graphDumpMode);
</del><ins>+ Validate validationObject(graph, graphDumpMode, graphDumpBeforePhase);
</ins><span class="cx"> validationObject.validate();
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGValidateh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGValidate.h (173412 => 173413)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGValidate.h 2014-09-09 00:33:02 UTC (rev 173412)
+++ trunk/Source/JavaScriptCore/dfg/DFGValidate.h 2014-09-09 00:34:40 UTC (rev 173413)
</span><span class="lines">@@ -35,7 +35,7 @@
</span><span class="cx">
</span><span class="cx"> enum GraphDumpMode { DontDumpGraph, DumpGraph };
</span><span class="cx">
</span><del>-void validate(Graph&, GraphDumpMode = DumpGraph);
</del><ins>+void validate(Graph&, GraphDumpMode = DumpGraph, CString graphDumpBeforePhase = CString());
</ins><span class="cx">
</span><span class="cx"> } } // namespace JSC::DFG
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreftlFTLLowerDFGToLLVMcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp (173412 => 173413)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp 2014-09-09 00:33:02 UTC (rev 173412)
+++ trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp 2014-09-09 00:34:40 UTC (rev 173413)
</span><span class="lines">@@ -145,12 +145,10 @@
</span><span class="cx"> m_out.appendTo(m_prologue, stackOverflow);
</span><span class="cx"> createPhiVariables();
</span><span class="cx">
</span><del>- Vector<BasicBlock*> depthFirst;
- m_graph.getBlocksInPreOrder(depthFirst);
</del><ins>+ Vector<BasicBlock*> preOrder = m_graph.blocksInPreOrder();
</ins><span class="cx">
</span><span class="cx"> int maxNumberOfArguments = -1;
</span><del>- for (unsigned blockIndex = depthFirst.size(); blockIndex--; ) {
- BasicBlock* block = depthFirst[blockIndex];
</del><ins>+ for (BasicBlock* block : preOrder) {
</ins><span class="cx"> for (unsigned nodeIndex = block->size(); nodeIndex--; ) {
</span><span class="cx"> Node* node = block->at(nodeIndex);
</span><span class="cx"> switch (node->op()) {
</span><span class="lines">@@ -211,9 +209,8 @@
</span><span class="cx"> m_out.constInt32(MacroAssembler::maxJumpReplacementSize()));
</span><span class="cx"> m_out.unreachable();
</span><span class="cx">
</span><del>-
- for (unsigned i = 0; i < depthFirst.size(); ++i)
- compileBlock(depthFirst[i]);
</del><ins>+ for (BasicBlock* block : preOrder)
+ compileBlock(block);
</ins><span class="cx">
</span><span class="cx"> if (Options::dumpLLVMIR())
</span><span class="cx"> dumpModule(m_ftlState.module);
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreruntimeOptionsh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/runtime/Options.h (173412 => 173413)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/runtime/Options.h 2014-09-09 00:33:02 UTC (rev 173412)
+++ trunk/Source/JavaScriptCore/runtime/Options.h 2014-09-09 00:34:40 UTC (rev 173413)
</span><span class="lines">@@ -128,6 +128,7 @@
</span><span class="cx"> v(bool, printEachOSRExit, false) \
</span><span class="cx"> v(bool, validateGraph, false) \
</span><span class="cx"> v(bool, validateGraphAtEachPhase, false) \
</span><ins>+ v(bool, verboseValidationFailure, false) \
</ins><span class="cx"> v(bool, verboseOSR, false) \
</span><span class="cx"> v(bool, verboseFTLOSRExit, false) \
</span><span class="cx"> v(bool, verboseCallLink, false) \
</span></span></pre></div>
<a id="trunkSourceWTFChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/ChangeLog (173412 => 173413)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/ChangeLog 2014-09-09 00:33:02 UTC (rev 173412)
+++ trunk/Source/WTF/ChangeLog 2014-09-09 00:34:40 UTC (rev 173413)
</span><span class="lines">@@ -1,3 +1,15 @@
</span><ins>+2014-09-07 Filip Pizlo <fpizlo@apple.com>
+
+ DFG should have a reusable SSA builder
+ https://bugs.webkit.org/show_bug.cgi?id=136331
+
+ Reviewed by Oliver Hunt.
+
+ Update the alloc() method to use variadic templates. This makes it more natural to use.
+
+ * wtf/SegmentedVector.h:
+ (WTF::SegmentedVector::alloc):
+
</ins><span class="cx"> 2014-09-08 Eva Balazsfalvi <evab.u-szeged@partner.samsung.com>
</span><span class="cx">
</span><span class="cx"> Remove FILTERS flag
</span></span></pre></div>
<a id="trunkSourceWTFwtfSegmentedVectorh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/SegmentedVector.h (173412 => 173413)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/SegmentedVector.h 2014-09-09 00:33:02 UTC (rev 173412)
+++ trunk/Source/WTF/wtf/SegmentedVector.h 2014-09-09 00:34:40 UTC (rev 173413)
</span><span class="lines">@@ -157,9 +157,10 @@
</span><span class="cx"> segmentFor(m_size - 1)->uncheckedAppend(std::forward<U>(value));
</span><span class="cx"> }
</span><span class="cx">
</span><del>- T& alloc()
</del><ins>+ template<typename... Args>
+ T& alloc(Args... args)
</ins><span class="cx"> {
</span><del>- append<T>(T());
</del><ins>+ append<T>(T(args...));
</ins><span class="cx"> return last();
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre>
</div>
</div>
</body>
</html>