<!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>[173072] 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/173072">173072</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2014-08-28 12:23:02 -0700 (Thu, 28 Aug 2014)</dd>
</dl>
<h3>Log Message</h3>
<pre>DFG should compute immediate dominators using the O(n log n) form of Lengauer and Tarjan's "A Fast Algorithm for Finding Dominators in a Flowgraph"
https://bugs.webkit.org/show_bug.cgi?id=93361
Reviewed by Mark Hahnenberg.
Source/JavaScriptCore:
This patch also adds some new utilities for reasoning about block-keyed maps, block sets,
and block worklists. It changes preexisting code to use these abstractions.
* CMakeLists.txt:
* JavaScriptCore.vcxproj/JavaScriptCore.vcxproj:
* JavaScriptCore.xcodeproj/project.pbxproj:
* dfg/DFGAnalysis.h:
(JSC::DFG::Analysis::computeIfNecessary):
(JSC::DFG::Analysis::computeDependencies):
* dfg/DFGBlockMap.h: Added.
(JSC::DFG::BlockMap::BlockMap):
(JSC::DFG::BlockMap::size):
(JSC::DFG::BlockMap::atIndex):
(JSC::DFG::BlockMap::operator[]):
* dfg/DFGBlockMapInlines.h: Added.
(JSC::DFG::BlockMap<T>::BlockMap):
* dfg/DFGBlockSet.h: Added.
(JSC::DFG::BlockSet::BlockSet):
(JSC::DFG::BlockSet::add):
(JSC::DFG::BlockSet::contains):
* dfg/DFGBlockWorklist.cpp: Added.
(JSC::DFG::BlockWorklist::BlockWorklist):
(JSC::DFG::BlockWorklist::~BlockWorklist):
(JSC::DFG::BlockWorklist::push):
(JSC::DFG::BlockWorklist::pop):
(JSC::DFG::PostOrderBlockWorklist::PostOrderBlockWorklist):
(JSC::DFG::PostOrderBlockWorklist::~PostOrderBlockWorklist):
(JSC::DFG::PostOrderBlockWorklist::pushPre):
(JSC::DFG::PostOrderBlockWorklist::pushPost):
(JSC::DFG::PostOrderBlockWorklist::pop):
* dfg/DFGBlockWorklist.h: Added.
(JSC::DFG::BlockWorklist::notEmpty):
(JSC::DFG::BlockWith::BlockWith):
(JSC::DFG::BlockWith::operator UnspecifiedBoolType*):
(JSC::DFG::ExtendedBlockWorklist::ExtendedBlockWorklist):
(JSC::DFG::ExtendedBlockWorklist::forcePush):
(JSC::DFG::ExtendedBlockWorklist::push):
(JSC::DFG::ExtendedBlockWorklist::notEmpty):
(JSC::DFG::ExtendedBlockWorklist::pop):
(JSC::DFG::BlockWithOrder::BlockWithOrder):
(JSC::DFG::BlockWithOrder::operator UnspecifiedBoolType*):
(JSC::DFG::PostOrderBlockWorklist::push):
(JSC::DFG::PostOrderBlockWorklist::notEmpty):
* dfg/DFGCSEPhase.cpp:
* dfg/DFGDominators.cpp:
(JSC::DFG::Dominators::compute):
(JSC::DFG::Dominators::naiveDominates):
(JSC::DFG::Dominators::dump):
(JSC::DFG::Dominators::pruneDominators): Deleted.
* dfg/DFGDominators.h:
(JSC::DFG::Dominators::strictlyDominates):
(JSC::DFG::Dominators::dominates):
(JSC::DFG::Dominators::BlockData::BlockData):
* dfg/DFGGraph.cpp:
(JSC::DFG::Graph::dumpBlockHeader):
(JSC::DFG::Graph::getBlocksInPreOrder):
(JSC::DFG::Graph::getBlocksInPostOrder):
* dfg/DFGInvalidationPointInjectionPhase.cpp:
(JSC::DFG::InvalidationPointInjectionPhase::run):
* dfg/DFGNaiveDominators.cpp: Added.
(JSC::DFG::NaiveDominators::NaiveDominators):
(JSC::DFG::NaiveDominators::~NaiveDominators):
(JSC::DFG::NaiveDominators::compute):
(JSC::DFG::NaiveDominators::pruneDominators):
(JSC::DFG::NaiveDominators::dump):
* dfg/DFGNaiveDominators.h: Added.
(JSC::DFG::NaiveDominators::dominates):
* dfg/DFGNaturalLoops.cpp:
(JSC::DFG::NaturalLoops::computeDependencies):
(JSC::DFG::NaturalLoops::compute):
* dfg/DFGNaturalLoops.h:
Source/WTF:
Make BitVector operations return the previous value of the bit you're changing. This is
useful for the kinds of set operations that are commonplace in compiler graph searches.
* wtf/BitVector.h:
(WTF::BitVector::quickSet):
(WTF::BitVector::quickClear):
(WTF::BitVector::set):
(WTF::BitVector::ensureSizeAndSet):
(WTF::BitVector::clear):</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="#trunkSourceJavaScriptCoredfgDFGDominatorscpp">trunk/Source/JavaScriptCore/dfg/DFGDominators.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="#trunkSourceJavaScriptCoredfgDFGInvalidationPointInjectionPhasecpp">trunk/Source/JavaScriptCore/dfg/DFGInvalidationPointInjectionPhase.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGNaturalLoopscpp">trunk/Source/JavaScriptCore/dfg/DFGNaturalLoops.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGNaturalLoopsh">trunk/Source/JavaScriptCore/dfg/DFGNaturalLoops.h</a></li>
<li><a href="#trunkSourceWTFChangeLog">trunk/Source/WTF/ChangeLog</a></li>
<li><a href="#trunkSourceWTFwtfBitVectorh">trunk/Source/WTF/wtf/BitVector.h</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoredfgDFGBlockMaph">trunk/Source/JavaScriptCore/dfg/DFGBlockMap.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGBlockMapInlinesh">trunk/Source/JavaScriptCore/dfg/DFGBlockMapInlines.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGBlockSeth">trunk/Source/JavaScriptCore/dfg/DFGBlockSet.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGBlockWorklistcpp">trunk/Source/JavaScriptCore/dfg/DFGBlockWorklist.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGBlockWorklisth">trunk/Source/JavaScriptCore/dfg/DFGBlockWorklist.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGNaiveDominatorscpp">trunk/Source/JavaScriptCore/dfg/DFGNaiveDominators.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGNaiveDominatorsh">trunk/Source/JavaScriptCore/dfg/DFGNaiveDominators.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 (173071 => 173072)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/CMakeLists.txt 2014-08-28 19:21:24 UTC (rev 173071)
+++ trunk/Source/JavaScriptCore/CMakeLists.txt 2014-08-28 19:23:02 UTC (rev 173072)
</span><span class="lines">@@ -126,6 +126,7 @@
</span><span class="cx"> dfg/DFGBasicBlock.cpp
</span><span class="cx"> dfg/DFGBinarySwitch.cpp
</span><span class="cx"> dfg/DFGBlockInsertionSet.cpp
</span><ins>+ dfg/DFGBlockWorklist.cpp
</ins><span class="cx"> dfg/DFGByteCodeParser.cpp
</span><span class="cx"> dfg/DFGCFAPhase.cpp
</span><span class="cx"> dfg/DFGCFGSimplificationPhase.cpp
</span><span class="lines">@@ -175,6 +176,7 @@
</span><span class="cx"> dfg/DFGLoopPreHeaderCreationPhase.cpp
</span><span class="cx"> dfg/DFGMayExit.cpp
</span><span class="cx"> dfg/DFGMinifiedNode.cpp
</span><ins>+ dfg/DFGNaiveDominators.cpp
</ins><span class="cx"> dfg/DFGNaturalLoops.cpp
</span><span class="cx"> dfg/DFGNode.cpp
</span><span class="cx"> dfg/DFGNodeFlags.cpp
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (173071 => 173072)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2014-08-28 19:21:24 UTC (rev 173071)
+++ trunk/Source/JavaScriptCore/ChangeLog 2014-08-28 19:23:02 UTC (rev 173072)
</span><span class="lines">@@ -1,5 +1,88 @@
</span><span class="cx"> 2014-08-27 Filip Pizlo <fpizlo@apple.com>
</span><span class="cx">
</span><ins>+ DFG should compute immediate dominators using the O(n log n) form of Lengauer and Tarjan's "A Fast Algorithm for Finding Dominators in a Flowgraph"
+ https://bugs.webkit.org/show_bug.cgi?id=93361
+
+ Reviewed by Mark Hahnenberg.
+
+ This patch also adds some new utilities for reasoning about block-keyed maps, block sets,
+ and block worklists. It changes preexisting code to use these abstractions.
+
+ The main effect of this code is that all current clients of dominators end up using the
+ results of the new idom calculation. We convert the dom tree to a dominance test using
+ Dietz's pre/post number range check trick.
+
+ * CMakeLists.txt:
+ * JavaScriptCore.vcxproj/JavaScriptCore.vcxproj:
+ * JavaScriptCore.xcodeproj/project.pbxproj:
+ * dfg/DFGAnalysis.h:
+ (JSC::DFG::Analysis::computeIfNecessary):
+ (JSC::DFG::Analysis::computeDependencies):
+ * dfg/DFGBlockMap.h: Added.
+ (JSC::DFG::BlockMap::BlockMap):
+ (JSC::DFG::BlockMap::size):
+ (JSC::DFG::BlockMap::atIndex):
+ (JSC::DFG::BlockMap::operator[]):
+ * dfg/DFGBlockMapInlines.h: Added.
+ (JSC::DFG::BlockMap<T>::BlockMap):
+ * dfg/DFGBlockSet.h: Added.
+ (JSC::DFG::BlockSet::BlockSet):
+ (JSC::DFG::BlockSet::add):
+ (JSC::DFG::BlockSet::contains):
+ * dfg/DFGBlockWorklist.cpp: Added.
+ (JSC::DFG::BlockWorklist::BlockWorklist):
+ (JSC::DFG::BlockWorklist::~BlockWorklist):
+ (JSC::DFG::BlockWorklist::push):
+ (JSC::DFG::BlockWorklist::pop):
+ (JSC::DFG::PostOrderBlockWorklist::PostOrderBlockWorklist):
+ (JSC::DFG::PostOrderBlockWorklist::~PostOrderBlockWorklist):
+ (JSC::DFG::PostOrderBlockWorklist::pushPre):
+ (JSC::DFG::PostOrderBlockWorklist::pushPost):
+ (JSC::DFG::PostOrderBlockWorklist::pop):
+ * dfg/DFGBlockWorklist.h: Added.
+ (JSC::DFG::BlockWorklist::notEmpty):
+ (JSC::DFG::BlockWith::BlockWith):
+ (JSC::DFG::BlockWith::operator UnspecifiedBoolType*):
+ (JSC::DFG::ExtendedBlockWorklist::ExtendedBlockWorklist):
+ (JSC::DFG::ExtendedBlockWorklist::forcePush):
+ (JSC::DFG::ExtendedBlockWorklist::push):
+ (JSC::DFG::ExtendedBlockWorklist::notEmpty):
+ (JSC::DFG::ExtendedBlockWorklist::pop):
+ (JSC::DFG::BlockWithOrder::BlockWithOrder):
+ (JSC::DFG::BlockWithOrder::operator UnspecifiedBoolType*):
+ (JSC::DFG::PostOrderBlockWorklist::push):
+ (JSC::DFG::PostOrderBlockWorklist::notEmpty):
+ * dfg/DFGCSEPhase.cpp:
+ * dfg/DFGDominators.cpp:
+ (JSC::DFG::Dominators::compute):
+ (JSC::DFG::Dominators::naiveDominates):
+ (JSC::DFG::Dominators::dump):
+ (JSC::DFG::Dominators::pruneDominators): Deleted.
+ * dfg/DFGDominators.h:
+ (JSC::DFG::Dominators::strictlyDominates):
+ (JSC::DFG::Dominators::dominates):
+ (JSC::DFG::Dominators::BlockData::BlockData):
+ * dfg/DFGGraph.cpp:
+ (JSC::DFG::Graph::dumpBlockHeader):
+ (JSC::DFG::Graph::getBlocksInPreOrder):
+ (JSC::DFG::Graph::getBlocksInPostOrder):
+ * dfg/DFGInvalidationPointInjectionPhase.cpp:
+ (JSC::DFG::InvalidationPointInjectionPhase::run):
+ * dfg/DFGNaiveDominators.cpp: Added.
+ (JSC::DFG::NaiveDominators::NaiveDominators):
+ (JSC::DFG::NaiveDominators::~NaiveDominators):
+ (JSC::DFG::NaiveDominators::compute):
+ (JSC::DFG::NaiveDominators::pruneDominators):
+ (JSC::DFG::NaiveDominators::dump):
+ * dfg/DFGNaiveDominators.h: Added.
+ (JSC::DFG::NaiveDominators::dominates):
+ * dfg/DFGNaturalLoops.cpp:
+ (JSC::DFG::NaturalLoops::computeDependencies):
+ (JSC::DFG::NaturalLoops::compute):
+ * dfg/DFGNaturalLoops.h:
+
+2014-08-27 Filip Pizlo <fpizlo@apple.com>
+
</ins><span class="cx"> FTL should be able to do polymorphic call inlining
</span><span class="cx"> https://bugs.webkit.org/show_bug.cgi?id=135145
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreJavaScriptCorevcxprojJavaScriptCorevcxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/JavaScriptCore.vcxproj/JavaScriptCore.vcxproj (173071 => 173072)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/JavaScriptCore.vcxproj/JavaScriptCore.vcxproj 2014-08-28 19:21:24 UTC (rev 173071)
+++ trunk/Source/JavaScriptCore/JavaScriptCore.vcxproj/JavaScriptCore.vcxproj 2014-08-28 19:23:02 UTC (rev 173072)
</span><span class="lines">@@ -372,6 +372,7 @@
</span><span class="cx"> <ClCompile Include="..\dfg\DFGBasicBlock.cpp" />
</span><span class="cx"> <ClCompile Include="..\dfg\DFGBinarySwitch.cpp" />
</span><span class="cx"> <ClCompile Include="..\dfg\DFGBlockInsertionSet.cpp" />
</span><ins>+ <ClCompile Include="..\dfg\DFGBlockWorklist.cpp" />
</ins><span class="cx"> <ClCompile Include="..\dfg\DFGByteCodeParser.cpp" />
</span><span class="cx"> <ClCompile Include="..\dfg\DFGCapabilities.cpp" />
</span><span class="cx"> <ClCompile Include="..\dfg\DFGCFAPhase.cpp" />
</span><span class="lines">@@ -421,6 +422,7 @@
</span><span class="cx"> <ClCompile Include="..\dfg\DFGLoopPreHeaderCreationPhase.cpp" />
</span><span class="cx"> <ClCompile Include="..\dfg\DFGMayExit.cpp" />
</span><span class="cx"> <ClCompile Include="..\dfg\DFGMinifiedNode.cpp" />
</span><ins>+ <ClCompile Include="..\dfg\DFGNaiveDominators.cpp" />
</ins><span class="cx"> <ClCompile Include="..\dfg\DFGNaturalLoops.cpp" />
</span><span class="cx"> <ClCompile Include="..\dfg\DFGNode.cpp" />
</span><span class="cx"> <ClCompile Include="..\dfg\DFGNodeFlags.cpp" />
</span><span class="lines">@@ -993,6 +995,10 @@
</span><span class="cx"> <ClInclude Include="..\dfg\DFGBasicBlockInlines.h" />
</span><span class="cx"> <ClInclude Include="..\dfg\DFGBinarySwitch.h" />
</span><span class="cx"> <ClInclude Include="..\dfg\DFGBlockInsertionSet.h" />
</span><ins>+ <ClInclude Include="..\dfg\DFGBlockMap.h" />
+ <ClInclude Include="..\dfg\DFGBlockMapInlines.h" />
+ <ClInclude Include="..\dfg\DFGBlockWorklist.h" />
+ <ClInclude Include="..\dfg\DFGBlockSet.h" />
</ins><span class="cx"> <ClInclude Include="..\dfg\DFGBranchDirection.h" />
</span><span class="cx"> <ClInclude Include="..\dfg\DFGByteCodeParser.h" />
</span><span class="cx"> <ClInclude Include="..\dfg\DFGCallArrayAllocatorSlowPathGenerator.h" />
</span><span class="lines">@@ -1056,6 +1062,7 @@
</span><span class="cx"> <ClInclude Include="..\dfg\DFGMinifiedGraph.h" />
</span><span class="cx"> <ClInclude Include="..\dfg\DFGMinifiedID.h" />
</span><span class="cx"> <ClInclude Include="..\dfg\DFGMinifiedNode.h" />
</span><ins>+ <ClInclude Include="..\dfg\DFGNaiveDominators.h" />
</ins><span class="cx"> <ClInclude Include="..\dfg\DFGNaturalLoops.h" />
</span><span class="cx"> <ClInclude Include="..\dfg\DFGNode.h" />
</span><span class="cx"> <ClInclude Include="..\dfg\DFGNodeAllocator.h" />
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreJavaScriptCorexcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj (173071 => 173072)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj 2014-08-28 19:21:24 UTC (rev 173071)
+++ trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj 2014-08-28 19:23:02 UTC (rev 173072)
</span><span class="lines">@@ -498,6 +498,13 @@
</span><span class="cx"> 0FC314121814559100033232 /* RegisterSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC314101814559100033232 /* RegisterSet.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 0FC314131814559100033232 /* TempRegisterSet.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FC314111814559100033232 /* TempRegisterSet.cpp */; };
</span><span class="cx"> 0FC3141518146D7000033232 /* RegisterSet.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FC3141418146D7000033232 /* RegisterSet.cpp */; };
</span><ins>+ 0FC3CCFC19ADA410006AC72A /* DFGBlockMap.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC3CCF519ADA410006AC72A /* DFGBlockMap.h */; settings = {ATTRIBUTES = (Private, ); }; };
+ 0FC3CCFD19ADA410006AC72A /* DFGBlockMapInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC3CCF619ADA410006AC72A /* DFGBlockMapInlines.h */; settings = {ATTRIBUTES = (Private, ); }; };
+ 0FC3CCFE19ADA410006AC72A /* DFGBlockSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC3CCF719ADA410006AC72A /* DFGBlockSet.h */; settings = {ATTRIBUTES = (Private, ); }; };
+ 0FC3CCFF19ADA410006AC72A /* DFGBlockWorklist.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FC3CCF819ADA410006AC72A /* DFGBlockWorklist.cpp */; };
+ 0FC3CD0019ADA410006AC72A /* DFGBlockWorklist.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC3CCF919ADA410006AC72A /* DFGBlockWorklist.h */; settings = {ATTRIBUTES = (Private, ); }; };
+ 0FC3CD0119ADA411006AC72A /* DFGNaiveDominators.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FC3CCFA19ADA410006AC72A /* DFGNaiveDominators.cpp */; };
+ 0FC3CD0219ADA411006AC72A /* DFGNaiveDominators.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC3CCFB19ADA410006AC72A /* DFGNaiveDominators.h */; settings = {ATTRIBUTES = (Private, ); }; };
</ins><span class="cx"> 0FC712DE17CD8779008CC93C /* DeferredCompilationCallback.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FC712DC17CD8778008CC93C /* DeferredCompilationCallback.cpp */; };
</span><span class="cx"> 0FC712DF17CD877C008CC93C /* DeferredCompilationCallback.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC712DD17CD8778008CC93C /* DeferredCompilationCallback.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 0FC712E217CD8791008CC93C /* JITToDFGDeferredCompilationCallback.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FC712E017CD878F008CC93C /* JITToDFGDeferredCompilationCallback.cpp */; };
</span><span class="lines">@@ -2421,6 +2428,13 @@
</span><span class="cx"> 0FC314101814559100033232 /* RegisterSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = RegisterSet.h; sourceTree = "<group>"; };
</span><span class="cx"> 0FC314111814559100033232 /* TempRegisterSet.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = TempRegisterSet.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 0FC3141418146D7000033232 /* RegisterSet.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = RegisterSet.cpp; sourceTree = "<group>"; };
</span><ins>+ 0FC3CCF519ADA410006AC72A /* DFGBlockMap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBlockMap.h; path = dfg/DFGBlockMap.h; sourceTree = "<group>"; };
+ 0FC3CCF619ADA410006AC72A /* DFGBlockMapInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBlockMapInlines.h; path = dfg/DFGBlockMapInlines.h; sourceTree = "<group>"; };
+ 0FC3CCF719ADA410006AC72A /* DFGBlockSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBlockSet.h; path = dfg/DFGBlockSet.h; sourceTree = "<group>"; };
+ 0FC3CCF819ADA410006AC72A /* DFGBlockWorklist.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGBlockWorklist.cpp; path = dfg/DFGBlockWorklist.cpp; sourceTree = "<group>"; };
+ 0FC3CCF919ADA410006AC72A /* DFGBlockWorklist.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBlockWorklist.h; path = dfg/DFGBlockWorklist.h; sourceTree = "<group>"; };
+ 0FC3CCFA19ADA410006AC72A /* DFGNaiveDominators.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGNaiveDominators.cpp; path = dfg/DFGNaiveDominators.cpp; sourceTree = "<group>"; };
+ 0FC3CCFB19ADA410006AC72A /* DFGNaiveDominators.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGNaiveDominators.h; path = dfg/DFGNaiveDominators.h; sourceTree = "<group>"; };
</ins><span class="cx"> 0FC712DC17CD8778008CC93C /* DeferredCompilationCallback.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; path = DeferredCompilationCallback.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 0FC712DD17CD8778008CC93C /* DeferredCompilationCallback.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = DeferredCompilationCallback.h; sourceTree = "<group>"; };
</span><span class="cx"> 0FC712E017CD878F008CC93C /* JITToDFGDeferredCompilationCallback.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; path = JITToDFGDeferredCompilationCallback.cpp; sourceTree = "<group>"; };
</span><span class="lines">@@ -4819,6 +4833,11 @@
</span><span class="cx"> A70B083117A0B79B00DAF14B /* DFGBinarySwitch.h */,
</span><span class="cx"> A7D89CE417A0B8CC00773AD8 /* DFGBlockInsertionSet.cpp */,
</span><span class="cx"> A7D89CE517A0B8CC00773AD8 /* DFGBlockInsertionSet.h */,
</span><ins>+ 0FC3CCF519ADA410006AC72A /* DFGBlockMap.h */,
+ 0FC3CCF619ADA410006AC72A /* DFGBlockMapInlines.h */,
+ 0FC3CCF719ADA410006AC72A /* DFGBlockSet.h */,
+ 0FC3CCF819ADA410006AC72A /* DFGBlockWorklist.cpp */,
+ 0FC3CCF919ADA410006AC72A /* DFGBlockWorklist.h */,
</ins><span class="cx"> 0F8364B5164B0C0E0053329A /* DFGBranchDirection.h */,
</span><span class="cx"> 86EC9DB41328DF82002B2AD7 /* DFGByteCodeParser.cpp */,
</span><span class="cx"> 86EC9DB51328DF82002B2AD7 /* DFGByteCodeParser.h */,
</span><span class="lines">@@ -4930,6 +4949,8 @@
</span><span class="cx"> 0FB4B51016B3A964003F696B /* DFGMinifiedID.h */,
</span><span class="cx"> 0F2BDC4C1522818300CD8910 /* DFGMinifiedNode.cpp */,
</span><span class="cx"> 0F2BDC3E1522801700CD8910 /* DFGMinifiedNode.h */,
</span><ins>+ 0FC3CCFA19ADA410006AC72A /* DFGNaiveDominators.cpp */,
+ 0FC3CCFB19ADA410006AC72A /* DFGNaiveDominators.h */,
</ins><span class="cx"> A737810A1799EA2E00817533 /* DFGNaturalLoops.cpp */,
</span><span class="cx"> A737810B1799EA2E00817533 /* DFGNaturalLoops.h */,
</span><span class="cx"> 0FB4B51E16B62772003F696B /* DFGNode.cpp */,
</span><span class="lines">@@ -5842,6 +5863,7 @@
</span><span class="cx"> C2FC9BD316644DFB00810D33 /* CopiedBlockInlines.h in Headers */,
</span><span class="cx"> C2EAA3FA149A835E00FCE112 /* CopiedSpace.h in Headers */,
</span><span class="cx"> C2C8D02D14A3C6E000578E65 /* CopiedSpaceInlines.h in Headers */,
</span><ins>+ 0FC3CCFD19ADA410006AC72A /* DFGBlockMapInlines.h in Headers */,
</ins><span class="cx"> 0F5A52D017ADD717008ECB2D /* CopyToken.h in Headers */,
</span><span class="cx"> C2239D1816262BDD005AC5FD /* CopyVisitor.h in Headers */,
</span><span class="cx"> C2239D1916262BDD005AC5FD /* CopyVisitorInlines.h in Headers */,
</span><span class="lines">@@ -5917,6 +5939,7 @@
</span><span class="cx"> A7BFF3C0179868940002F462 /* DFGFiltrationResult.h in Headers */,
</span><span class="cx"> A78A9777179738B8009DF744 /* DFGFinalizer.h in Headers */,
</span><span class="cx"> 0F2BDC16151C5D4F00CD8910 /* DFGFixupPhase.h in Headers */,
</span><ins>+ 0FC3CCFC19ADA410006AC72A /* DFGBlockMap.h in Headers */,
</ins><span class="cx"> 0F9D339717FFC4E60073C2BC /* DFGFlushedAt.h in Headers */,
</span><span class="cx"> A7D89CF817A0B8CC00773AD8 /* DFGFlushFormat.h in Headers */,
</span><span class="cx"> 86EC9DC61328DF82002B2AD7 /* DFGGenerationInfo.h in Headers */,
</span><span class="lines">@@ -6317,6 +6340,7 @@
</span><span class="cx"> 0F431738146BAC69007E3890 /* ListableHandler.h in Headers */,
</span><span class="cx"> A7E2EA6B0FB460CF00601F06 /* LiteralParser.h in Headers */,
</span><span class="cx"> 0F0FC45A14BD15F500B81154 /* LLIntCallLinkInfo.h in Headers */,
</span><ins>+ 0FC3CD0019ADA410006AC72A /* DFGBlockWorklist.h in Headers */,
</ins><span class="cx"> FE20CE9E15F04A9500DF3430 /* LLIntCLoop.h in Headers */,
</span><span class="cx"> 0F4680CA14BBB16C00BFE272 /* LLIntCommon.h in Headers */,
</span><span class="cx"> 0F4680D314BBD16700BFE272 /* LLIntData.h in Headers */,
</span><span class="lines">@@ -6329,6 +6353,7 @@
</span><span class="cx"> 0F0123331944EA1B00843A0C /* DFGValueStrength.h in Headers */,
</span><span class="cx"> 0FCEFACE1805E75500472CE4 /* LLVMAPI.h in Headers */,
</span><span class="cx"> 0FCEFACF1805E75500472CE4 /* LLVMAPIFunctions.h in Headers */,
</span><ins>+ 0FC3CCFE19ADA410006AC72A /* DFGBlockSet.h in Headers */,
</ins><span class="cx"> A7E5AB381799E4B200D2833D /* LLVMDisassembler.h in Headers */,
</span><span class="cx"> 0FCEFAD31805EDCC00472CE4 /* LLVMHeaders.h in Headers */,
</span><span class="cx"> 142E3139134FF0A600AFADB5 /* Local.h in Headers */,
</span><span class="lines">@@ -6374,6 +6399,7 @@
</span><span class="cx"> 7EFF00640EC05A9A00AA7C93 /* NodeInfo.h in Headers */,
</span><span class="cx"> BC18C43F0E16F5CD00B34460 /* Nodes.h in Headers */,
</span><span class="cx"> 99E45A2818A1B2590026D88F /* NondeterministicInput.h in Headers */,
</span><ins>+ 0FC3CD0219ADA411006AC72A /* DFGNaiveDominators.h in Headers */,
</ins><span class="cx"> BC18C4410E16F5CD00B34460 /* NumberConstructor.h in Headers */,
</span><span class="cx"> 0F5780A218FE1E98001E72D9 /* PureNaN.h in Headers */,
</span><span class="cx"> BC18C4420E16F5CD00B34460 /* NumberConstructor.lut.h in Headers */,
</span><span class="lines">@@ -7297,6 +7323,7 @@
</span><span class="cx"> A7D89CFF17A0B8CC00773AD8 /* DFGSSAConversionPhase.cpp in Sources */,
</span><span class="cx"> 2A05ABD51961DF2400341750 /* JSPropertyNameEnumerator.cpp in Sources */,
</span><span class="cx"> 0FC20CB918556A3500C9E954 /* DFGSSALoweringPhase.cpp in Sources */,
</span><ins>+ 0FC3CD0119ADA411006AC72A /* DFGNaiveDominators.cpp in Sources */,
</ins><span class="cx"> 0F9FB4F417FCB91700CB67F8 /* DFGStackLayoutPhase.cpp in Sources */,
</span><span class="cx"> 0F4F29DF18B6AD1C0057BC15 /* DFGStaticExecutionCountEstimationPhase.cpp in Sources */,
</span><span class="cx"> 0FE7211D193B9C590031F6ED /* DFGTransition.cpp in Sources */,
</span><span class="lines">@@ -7357,6 +7384,7 @@
</span><span class="cx"> 0FD8A31917D51F2200CA2C40 /* FTLForOSREntryJITCode.cpp in Sources */,
</span><span class="cx"> 0F25F1AF181635F300522F39 /* FTLInlineCacheSize.cpp in Sources */,
</span><span class="cx"> 0FEA0A281709623B00BB722C /* FTLIntrinsicRepository.cpp in Sources */,
</span><ins>+ 0FC3CCFF19ADA410006AC72A /* DFGBlockWorklist.cpp in Sources */,
</ins><span class="cx"> 0FEA0A0D170513DB00BB722C /* FTLJITCode.cpp in Sources */,
</span><span class="cx"> A78A9780179738D5009DF744 /* FTLJITFinalizer.cpp in Sources */,
</span><span class="cx"> 0F6B1CB5185FC9E900845D97 /* FTLJSCall.cpp in Sources */,
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGAnalysish"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGAnalysis.h (173071 => 173072)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGAnalysis.h 2014-08-28 19:21:24 UTC (rev 173071)
+++ trunk/Source/JavaScriptCore/dfg/DFGAnalysis.h 2014-08-28 19:23:02 UTC (rev 173072)
</span><span class="lines">@@ -53,6 +53,8 @@
</span><span class="cx"> {
</span><span class="cx"> if (m_valid)
</span><span class="cx"> return;
</span><ins>+ // It's best to run dependent analyses from this method.
+ static_cast<T*>(this)->computeDependencies(graph);
</ins><span class="cx"> // Set to true early, since the analysis may choose to call its own methods in
</span><span class="cx"> // compute() and it may want to ASSERT() validity in those methods.
</span><span class="cx"> m_valid = true;
</span><span class="lines">@@ -61,6 +63,12 @@
</span><span class="cx">
</span><span class="cx"> bool isValid() const { return m_valid; }
</span><span class="cx">
</span><ins>+ // Override this to compute any dependent analyses. See
+ // NaturalLoops::computeDependencies(Graph&) for an example. This isn't strictly necessary but
+ // it makes debug dumps in cases of error work a bit better because this analysis wouldn't yet
+ // be pretending to be valid.
+ void computeDependencies(Graph&) { }
+
</ins><span class="cx"> private:
</span><span class="cx"> bool m_valid;
</span><span class="cx"> };
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGBlockMaph"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/dfg/DFGBlockMap.h (0 => 173072)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGBlockMap.h (rev 0)
+++ trunk/Source/JavaScriptCore/dfg/DFGBlockMap.h 2014-08-28 19:23:02 UTC (rev 173072)
</span><span class="lines">@@ -0,0 +1,90 @@
</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 DFGBlockMap_h
+#define DFGBlockMap_h
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGBasicBlock.h"
+
+namespace JSC { namespace DFG {
+
+class Graph;
+
+template<typename T>
+class BlockMap {
+public:
+ BlockMap()
+ {
+ }
+
+ BlockMap(Graph&);
+
+ BlockIndex size() const
+ {
+ return m_vector.size();
+ }
+
+ T& atIndex(BlockIndex blockIndex)
+ {
+ return m_vector[blockIndex];
+ }
+
+ const T& atIndex(BlockIndex blockIndex) const
+ {
+ return m_vector[blockIndex];
+ }
+
+ T& operator[](BlockIndex blockIndex)
+ {
+ return m_vector[blockIndex];
+ }
+
+ const T& operator[](BlockIndex blockIndex) const
+ {
+ return m_vector[blockIndex];
+ }
+
+ T& operator[](BasicBlock* block)
+ {
+ return m_vector[block->index];
+ }
+
+ const T& operator[](BasicBlock* block) const
+ {
+ return m_vector[block->index];
+ }
+
+private:
+ Vector<T> m_vector;
+};
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGBlockMap_h
+
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGBlockMapInlinesh"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/dfg/DFGBlockMapInlines.h (0 => 173072)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGBlockMapInlines.h (rev 0)
+++ trunk/Source/JavaScriptCore/dfg/DFGBlockMapInlines.h 2014-08-28 19:23:02 UTC (rev 173072)
</span><span class="lines">@@ -0,0 +1,46 @@
</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 DFGBlockMapInlines_h
+#define DFGBlockMapInlines_h
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGBlockMap.h"
+#include "DFGGraph.h"
+
+namespace JSC { namespace DFG {
+
+template<typename T>
+BlockMap<T>::BlockMap(Graph& graph)
+{
+ m_vector.resize(graph.numBlocks());
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGBlockMapInlines_h
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGBlockSeth"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/dfg/DFGBlockSet.h (0 => 173072)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGBlockSet.h (rev 0)
+++ trunk/Source/JavaScriptCore/dfg/DFGBlockSet.h 2014-08-28 19:23:02 UTC (rev 173072)
</span><span class="lines">@@ -0,0 +1,61 @@
</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 DFGBlockSet_h
+#define DFGBlockSet_h
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGBasicBlock.h"
+
+namespace JSC { namespace DFG {
+
+class BlockSet {
+public:
+ BlockSet() { }
+
+ // Return true if the block was added, false if it was already present.
+ bool add(BasicBlock* block)
+ {
+ return !m_set.set(block->index);
+ }
+
+ bool contains(BasicBlock* block) const
+ {
+ if (!block)
+ return false;
+ return m_set.get(block->index);
+ }
+
+private:
+ BitVector m_set;
+};
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGBlockSet_h
+
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGBlockWorklistcpp"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/dfg/DFGBlockWorklist.cpp (0 => 173072)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGBlockWorklist.cpp (rev 0)
+++ trunk/Source/JavaScriptCore/dfg/DFGBlockWorklist.cpp 2014-08-28 19:23:02 UTC (rev 173072)
</span><span class="lines">@@ -0,0 +1,86 @@
</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 "DFGBlockWorklist.h"
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGBasicBlock.h"
+
+namespace JSC { namespace DFG {
+
+BlockWorklist::BlockWorklist()
+{
+}
+
+BlockWorklist::~BlockWorklist()
+{
+}
+
+bool BlockWorklist::push(BasicBlock* block)
+{
+ if (!m_seen.add(block))
+ return false;
+
+ m_stack.append(block);
+ return true;
+}
+
+BasicBlock* BlockWorklist::pop()
+{
+ if (m_stack.isEmpty())
+ return nullptr;
+
+ return m_stack.takeLast();
+}
+
+PostOrderBlockWorklist::PostOrderBlockWorklist()
+{
+}
+
+PostOrderBlockWorklist::~PostOrderBlockWorklist()
+{
+}
+
+bool PostOrderBlockWorklist::pushPre(BasicBlock* block)
+{
+ return m_worklist.push(block, PreOrder);
+}
+
+void PostOrderBlockWorklist::pushPost(BasicBlock* block)
+{
+ m_worklist.forcePush(block, PostOrder);
+}
+
+BlockWithOrder PostOrderBlockWorklist::pop()
+{
+ BlockWith<VisitOrder> result = m_worklist.pop();
+ return BlockWithOrder(result.block, result.data);
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGBlockWorklisth"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/dfg/DFGBlockWorklist.h (0 => 173072)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGBlockWorklist.h (rev 0)
+++ trunk/Source/JavaScriptCore/dfg/DFGBlockWorklist.h 2014-08-28 19:23:02 UTC (rev 173072)
</span><span class="lines">@@ -0,0 +1,192 @@
</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 DFGBlockWorklist_h
+#define DFGBlockWorklist_h
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGBasicBlock.h"
+#include "DFGBlockSet.h"
+#include <wtf/Vector.h>
+
+namespace JSC { namespace DFG {
+
+struct BasicBlock;
+
+class BlockWorklist {
+public:
+ BlockWorklist();
+ ~BlockWorklist();
+
+ bool push(BasicBlock*); // Returns true if we didn't know about the block before.
+
+ bool notEmpty() const { return !m_stack.isEmpty(); }
+ BasicBlock* pop();
+
+private:
+ BlockSet m_seen;
+ Vector<BasicBlock*, 16> m_stack;
+};
+
+// When you say BlockWith<int> you should read it as "block with an int".
+template<typename T>
+struct BlockWith {
+ BlockWith()
+ : block(nullptr)
+ {
+ }
+
+ BlockWith(BasicBlock* block, const T& data)
+ : block(block)
+ , data(data)
+ {
+ }
+
+ typedef void* (BlockWith<T>::*UnspecifiedBoolType);
+ operator UnspecifiedBoolType*() const
+ {
+ return block ? reinterpret_cast<UnspecifiedBoolType*>(1) : nullptr;
+ }
+
+ BasicBlock* block;
+ T data;
+};
+
+// Extended block worklist is useful for enqueueing some meta-data along with the block. It also
+// permits forcibly enqueueing things even if the block has already been seen. It's useful for
+// things like building a spanning tree, in which case T (the auxiliary payload) would be the
+// successor index.
+template<typename T>
+class ExtendedBlockWorklist {
+public:
+ ExtendedBlockWorklist() { }
+
+ void forcePush(const BlockWith<T>& entry)
+ {
+ m_stack.append(entry);
+ }
+
+ void forcePush(BasicBlock* block, const T& data)
+ {
+ forcePush(BlockWith<T>(block, data));
+ }
+
+ bool push(const BlockWith<T>& entry)
+ {
+ if (!m_seen.add(entry.block))
+ return false;
+
+ forcePush(entry);
+ return true;
+ }
+
+ bool push(BasicBlock* block, const T& data)
+ {
+ return push(BlockWith<T>(block, data));
+ }
+
+ bool notEmpty() const { return !m_stack.isEmpty(); }
+
+ BlockWith<T> pop()
+ {
+ if (m_stack.isEmpty())
+ return BlockWith<T>();
+
+ return m_stack.takeLast();
+ }
+
+private:
+ BlockSet m_seen;
+ Vector<BlockWith<T>> m_stack;
+};
+
+enum VisitOrder {
+ PreOrder,
+ PostOrder
+};
+
+struct BlockWithOrder {
+ BlockWithOrder()
+ : block(nullptr)
+ , order(PreOrder)
+ {
+ }
+
+ BlockWithOrder(BasicBlock* block, VisitOrder order)
+ : block(block)
+ , order(order)
+ {
+ }
+
+ typedef void* (BlockWithOrder::*UnspecifiedBoolType);
+ operator UnspecifiedBoolType*() const
+ {
+ return block ? reinterpret_cast<UnspecifiedBoolType*>(1) : nullptr;
+ }
+
+ BasicBlock* block;
+ VisitOrder order;
+};
+
+// Block worklist suitable for post-order traversal.
+class PostOrderBlockWorklist {
+public:
+ PostOrderBlockWorklist();
+ ~PostOrderBlockWorklist();
+
+ bool pushPre(BasicBlock*);
+ void pushPost(BasicBlock*);
+
+ bool push(BasicBlock* block, VisitOrder order = PreOrder)
+ {
+ switch (order) {
+ case PreOrder:
+ return pushPre(block);
+ case PostOrder:
+ pushPost(block);
+ return true;
+ }
+ RELEASE_ASSERT_NOT_REACHED();
+ return false;
+ }
+ bool push(const BlockWithOrder& data)
+ {
+ return push(data.block, data.order);
+ }
+
+ bool notEmpty() const { return m_worklist.notEmpty(); }
+ BlockWithOrder pop();
+
+private:
+ ExtendedBlockWorklist<VisitOrder> m_worklist;
+};
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGBlockWorklist_h
+
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGCSEPhasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGCSEPhase.cpp (173071 => 173072)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGCSEPhase.cpp 2014-08-28 19:21:24 UTC (rev 173071)
+++ trunk/Source/JavaScriptCore/dfg/DFGCSEPhase.cpp 2014-08-28 19:23:02 UTC (rev 173072)
</span><span class="lines">@@ -29,6 +29,7 @@
</span><span class="cx"> #if ENABLE(DFG_JIT)
</span><span class="cx">
</span><span class="cx"> #include "DFGAbstractHeap.h"
</span><ins>+#include "DFGBlockMapInlines.h"
</ins><span class="cx"> #include "DFGClobberSet.h"
</span><span class="cx"> #include "DFGClobberize.h"
</span><span class="cx"> #include "DFGEdgeUsesStructure.h"
</span><span class="lines">@@ -364,6 +365,7 @@
</span><span class="cx"> public:
</span><span class="cx"> GlobalCSEPhase(Graph& graph)
</span><span class="cx"> : Phase(graph, "global common subexpression elimination")
</span><ins>+ , m_impureDataMap(graph)
</ins><span class="cx"> {
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -377,13 +379,11 @@
</span><span class="cx">
</span><span class="cx"> m_graph.getBlocksInPreOrder(m_preOrder);
</span><span class="cx">
</span><del>- m_impureDataMap.resize(m_graph.numBlocks());
-
</del><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 class="cx"> for (unsigned i = m_preOrder.size(); i--;) {
</span><span class="cx"> m_block = m_preOrder[i];
</span><del>- m_impureData = &m_impureDataMap[m_block->index];
</del><ins>+ m_impureData = &m_impureDataMap[m_block];
</ins><span class="cx"> for (unsigned nodeIndex = m_block->size(); nodeIndex--;)
</span><span class="cx"> addWrites(m_graph, m_block->at(nodeIndex), m_impureData->writes);
</span><span class="cx"> }
</span><span class="lines">@@ -407,7 +407,7 @@
</span><span class="cx"> {
</span><span class="cx"> m_pureValues.clear();
</span><span class="cx">
</span><del>- for (unsigned i = m_impureDataMap.size(); i--;) {
</del><ins>+ for (BlockIndex i = m_impureDataMap.size(); i--;) {
</ins><span class="cx"> m_impureDataMap[i].availableAtTail.clear();
</span><span class="cx"> m_impureDataMap[i].didVisit = false;
</span><span class="cx"> }
</span><span class="lines">@@ -423,7 +423,7 @@
</span><span class="cx">
</span><span class="cx"> for (unsigned i = 0; i < m_preOrder.size(); ++i) {
</span><span class="cx"> m_block = m_preOrder[i];
</span><del>- m_impureData = &m_impureDataMap[m_block->index];
</del><ins>+ m_impureData = &m_impureDataMap[m_block];
</ins><span class="cx"> m_writesSoFar.clear();
</span><span class="cx">
</span><span class="cx"> if (verbose)
</span><span class="lines">@@ -562,12 +562,12 @@
</span><span class="cx">
</span><span class="cx"> if (verbose)
</span><span class="cx"> dataLog(" Searching in block ", *block, "\n");
</span><del>- ImpureBlockData& data = m_impureDataMap[block->index];
</del><ins>+ ImpureBlockData& data = m_impureDataMap[block];
</ins><span class="cx">
</span><span class="cx"> // We require strict domination because this would only see things in our own block if
</span><span class="cx"> // they came *after* our position in the block. Clearly, while our block dominates
</span><span class="cx"> // itself, the things in the block after us don't dominate us.
</span><del>- if (m_graph.m_dominators.dominates(block, m_block) && block != m_block) {
</del><ins>+ if (m_graph.m_dominators.strictlyDominates(block, m_block)) {
</ins><span class="cx"> if (verbose)
</span><span class="cx"> dataLog(" It strictly dominates.\n");
</span><span class="cx"> DFG_ASSERT(m_graph, m_node, data.didVisit);
</span><span class="lines">@@ -612,7 +612,7 @@
</span><span class="cx"> // the reduction in compile time would warrant the increase in complexity, though.
</span><span class="cx"> // https://bugs.webkit.org/show_bug.cgi?id=134876
</span><span class="cx"> for (BasicBlock* block : seenList)
</span><del>- m_impureDataMap[block->index].availableAtTail.add(location, match);
</del><ins>+ m_impureDataMap[block].availableAtTail.add(location, match);
</ins><span class="cx"> m_impureData->availableAtTail.add(location, match);
</span><span class="cx">
</span><span class="cx"> return match;
</span><span class="lines">@@ -654,7 +654,7 @@
</span><span class="cx"> Vector<BasicBlock*> m_preOrder;
</span><span class="cx">
</span><span class="cx"> PureMultiMap m_pureValues;
</span><del>- Vector<ImpureBlockData> m_impureDataMap;
</del><ins>+ BlockMap<ImpureBlockData> m_impureDataMap;
</ins><span class="cx">
</span><span class="cx"> BasicBlock* m_block;
</span><span class="cx"> Node* m_node;
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGDominatorscpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGDominators.cpp (173071 => 173072)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGDominators.cpp 2014-08-28 19:21:24 UTC (rev 173071)
+++ trunk/Source/JavaScriptCore/dfg/DFGDominators.cpp 2014-08-28 19:23:02 UTC (rev 173072)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2011 Apple Inc. All rights reserved.
</del><ins>+ * Copyright (C) 2011, 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">@@ -28,7 +28,10 @@
</span><span class="cx">
</span><span class="cx"> #if ENABLE(DFG_JIT)
</span><span class="cx">
</span><ins>+#include "DFGBlockMapInlines.h"
+#include "DFGBlockWorklist.h"
</ins><span class="cx"> #include "DFGGraph.h"
</span><ins>+#include "DFGNaiveDominators.h"
</ins><span class="cx"> #include "JSCInlines.h"
</span><span class="cx">
</span><span class="cx"> namespace JSC { namespace DFG {
</span><span class="lines">@@ -41,94 +44,390 @@
</span><span class="cx"> {
</span><span class="cx"> }
</span><span class="cx">
</span><del>-void Dominators::compute(Graph& graph)
-{
- // This implements a naive dominator solver.
</del><ins>+namespace {
+
+// This implements Lengauer and Tarjan's "A Fast Algorithm for Finding Dominators in a Flowgraph"
+// (TOPLAS 1979). It uses the "simple" implementation of LINK and EVAL, which yields an O(n log n)
+// solution. The full paper is linked below; this code attempts to closely follow the algorithm as
+// it is presented in the paper; in particular sections 3 and 4 as well as appendix B.
+// https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/a%20fast%20algorithm%20for%20finding.pdf
+//
+// This code is very subtle. The Lengauer-Tarjan algorithm is incredibly deep to begin with. The
+// goal of this code is to follow the code in the paper, however our implementation must deviate
+// from the paper when it comes to recursion. The authors had used recursion to implement DFS, and
+// also to implement the "simple" EVAL. We convert both of those into worklist-based solutions.
+// Finally, once the algorithm gives us immediate dominators, we implement dominance tests by
+// walking the dominator tree and computing pre and post numbers. We then use the range inclusion
+// check trick that was first discovered by Paul F. Dietz in 1982 in "Maintaining order in a linked
+// list" (see http://dl.acm.org/citation.cfm?id=802184).
+
+class LengauerTarjan {
+public:
+ LengauerTarjan(Graph& graph)
+ : m_graph(graph)
+ , m_data(graph)
+ {
+ for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+ BasicBlock* block = m_graph.block(blockIndex);
+ if (!block)
+ continue;
+ m_data[block].label = block;
+ }
+ }
</ins><span class="cx">
</span><del>- ASSERT(graph.block(0)->predecessors.isEmpty());
</del><ins>+ void compute()
+ {
+ computeDepthFirstPreNumbering(); // Step 1.
+ computeSemiDominatorsAndImplicitImmediateDominators(); // Steps 2 and 3.
+ computeExplicitImmediateDominators(); // Step 4.
+ }
</ins><span class="cx">
</span><del>- unsigned numBlocks = graph.numBlocks();
-
- // Allocate storage for the dense dominance matrix.
- if (numBlocks > m_results.size()) {
- m_results.grow(numBlocks);
- for (unsigned i = numBlocks; i--;)
- m_results[i].resize(numBlocks);
- m_scratch.resize(numBlocks);
</del><ins>+ BasicBlock* immediateDominator(BasicBlock* block)
+ {
+ return m_data[block].dom;
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- // We know that the entry block is only dominated by itself.
- m_results[0].clearAll();
- m_results[0].set(0);
</del><ins>+private:
+ void computeDepthFirstPreNumbering()
+ {
+ // Use a block worklist that also tracks the index inside the successor list. This is
+ // necessary for ensuring that we don't attempt to visit a successor until the previous
+ // successors that we had visited are fully processed. This ends up being revealed in the
+ // output of this method because the first time we see an edge to a block, we set the
+ // block's parent. So, if we have:
+ //
+ // A -> B
+ // A -> C
+ // B -> C
+ //
+ // And we're processing A, then we want to ensure that if we see A->B first (and hence set
+ // B's prenumber before we set C's) then we also end up setting C's parent to B by virtue
+ // of not noticing A->C until we're done processing B.
+
+ ExtendedBlockWorklist<unsigned> worklist;
+ worklist.push(m_graph.block(0), 0);
+
+ while (BlockWith<unsigned> item = worklist.pop()) {
+ BasicBlock* block = item.block;
+ unsigned successorIndex = item.data;
+
+ // We initially push with successorIndex = 0 regardless of whether or not we have any
+ // successors. This is so that we can assign our prenumber. Subsequently we get pushed
+ // with higher successorIndex values, but only if they are in range.
+ ASSERT(!successorIndex || successorIndex < block->numSuccessors());
</ins><span class="cx">
</span><del>- // Find all of the valid blocks.
- m_scratch.clearAll();
- for (unsigned i = numBlocks; i--;) {
- if (!graph.block(i))
- continue;
- m_scratch.set(i);
</del><ins>+ if (!successorIndex) {
+ m_data[block].semiNumber = m_blockByPreNumber.size();
+ m_blockByPreNumber.append(block);
+ }
+
+ if (successorIndex < block->numSuccessors()) {
+ unsigned nextSuccessorIndex = successorIndex + 1;
+ if (nextSuccessorIndex < block->numSuccessors())
+ worklist.forcePush(block, nextSuccessorIndex);
+
+ BasicBlock* successorBlock = block->successor(successorIndex);
+ if (worklist.push(successorBlock, 0))
+ m_data[successorBlock].parent = block;
+ }
+ }
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- // Mark all nodes as dominated by everything.
- for (unsigned i = numBlocks; i-- > 1;) {
- if (!graph.block(i) || graph.block(i)->predecessors.isEmpty())
- m_results[i].clearAll();
- else
- m_results[i].set(m_scratch);
</del><ins>+ void computeSemiDominatorsAndImplicitImmediateDominators()
+ {
+ for (unsigned currentPreNumber = m_blockByPreNumber.size(); currentPreNumber-- > 1;) {
+ BasicBlock* block = m_blockByPreNumber[currentPreNumber];
+ BlockData& blockData = m_data[block];
+
+ // Step 2:
+ for (BasicBlock* predecessorBlock : block->predecessors) {
+ BasicBlock* intermediateBlock = eval(predecessorBlock);
+ blockData.semiNumber = std::min(
+ m_data[intermediateBlock].semiNumber, blockData.semiNumber);
+ }
+ unsigned bucketPreNumber = blockData.semiNumber;
+ ASSERT(bucketPreNumber <= currentPreNumber);
+ m_data[m_blockByPreNumber[bucketPreNumber]].bucket.append(block);
+ link(blockData.parent, block);
+
+ // Step 3:
+ for (BasicBlock* semiDominee : m_data[blockData.parent].bucket) {
+ BasicBlock* possibleDominator = eval(semiDominee);
+ BlockData& semiDomineeData = m_data[semiDominee];
+ ASSERT(m_blockByPreNumber[semiDomineeData.semiNumber] == blockData.parent);
+ BlockData& possibleDominatorData = m_data[possibleDominator];
+ if (possibleDominatorData.semiNumber < semiDomineeData.semiNumber)
+ semiDomineeData.dom = possibleDominator;
+ else
+ semiDomineeData.dom = blockData.parent;
+ }
+ m_data[blockData.parent].bucket.clear();
+ }
</ins><span class="cx"> }
</span><ins>+
+ void computeExplicitImmediateDominators()
+ {
+ for (unsigned currentPreNumber = 1; currentPreNumber < m_blockByPreNumber.size(); ++currentPreNumber) {
+ BasicBlock* block = m_blockByPreNumber[currentPreNumber];
+ BlockData& blockData = m_data[block];
+
+ if (blockData.dom != m_blockByPreNumber[blockData.semiNumber])
+ blockData.dom = m_data[blockData.dom].dom;
+ }
+ }
+
+ void link(BasicBlock* from, BasicBlock* to)
+ {
+ m_data[to].ancestor = from;
+ }
+
+ BasicBlock* eval(BasicBlock* block)
+ {
+ if (!m_data[block].ancestor)
+ return block;
+
+ compress(block);
+ return m_data[block].label;
+ }
+
+ void compress(BasicBlock* initialBlock)
+ {
+ // This was meant to be a recursive function, but we don't like recursion because we don't
+ // want to blow the stack. The original function will call compress() recursively on the
+ // ancestor of anything that has an ancestor. So, we populate our worklist with the
+ // recursive ancestors of initialBlock. Then we process the list starting from the block
+ // that is furthest up the ancestor chain.
+
+ BasicBlock* ancestor = m_data[initialBlock].ancestor;
+ ASSERT(ancestor);
+ if (!m_data[ancestor].ancestor)
+ return;
+
+ Vector<BasicBlock*, 16> stack;
+ for (BasicBlock* block = initialBlock; block; block = m_data[block].ancestor)
+ stack.append(block);
+
+ // We only care about blocks that have an ancestor that has an ancestor. The last two
+ // elements in the stack won't satisfy this property.
+ ASSERT(stack.size() >= 2);
+ ASSERT(!m_data[stack[stack.size() - 1]].ancestor);
+ ASSERT(!m_data[m_data[stack[stack.size() - 2]].ancestor].ancestor);
+
+ for (unsigned i = stack.size() - 2; i--;) {
+ BasicBlock* block = stack[i];
+ BasicBlock*& labelOfBlock = m_data[block].label;
+ BasicBlock*& ancestorOfBlock = m_data[block].ancestor;
+ ASSERT(ancestorOfBlock);
+ ASSERT(m_data[ancestorOfBlock].ancestor);
+
+ BasicBlock* labelOfAncestorOfBlock = m_data[ancestorOfBlock].label;
+
+ if (m_data[labelOfAncestorOfBlock].semiNumber < m_data[labelOfBlock].semiNumber)
+ labelOfBlock = labelOfAncestorOfBlock;
+ ancestorOfBlock = m_data[ancestorOfBlock].ancestor;
+ }
+ }
</ins><span class="cx">
</span><del>- // Iteratively eliminate nodes that are not dominator.
- bool changed;
- do {
- changed = false;
- // Prune dominators in all non entry blocks: forward scan.
- for (unsigned i = 1; i < numBlocks; ++i)
- changed |= pruneDominators(graph, i);
</del><ins>+ struct BlockData {
+ BlockData()
+ : parent(nullptr)
+ , preNumber(UINT_MAX)
+ , semiNumber(UINT_MAX)
+ , ancestor(nullptr)
+ , label(nullptr)
+ , dom(nullptr)
+ {
+ }
+
+ BasicBlock* parent;
+ unsigned preNumber;
+ unsigned semiNumber;
+ BasicBlock* ancestor;
+ BasicBlock* label;
+ Vector<BasicBlock*> bucket;
+ BasicBlock* dom;
+ };
+
+ Graph& m_graph;
+ BlockMap<BlockData> m_data;
+ Vector<BasicBlock*> m_blockByPreNumber;
+};
</ins><span class="cx">
</span><del>- if (!changed)
- break;
</del><ins>+struct ValidationContext {
+ ValidationContext(Graph& graph, Dominators& dominators)
+ : graph(graph)
+ , dominators(dominators)
+ {
+ }
+
+ void reportError(BasicBlock* from, BasicBlock* to, const char* message)
+ {
+ Error error;
+ error.from = from;
+ error.to = to;
+ error.message = message;
+ errors.append(error);
+ }
+
+ void handleErrors()
+ {
+ if (errors.isEmpty())
+ return;
+
+ startCrashing();
+ dataLog("DFG DOMINATOR VALIDATION FAILED:\n");
+ dataLog("\n");
+ dataLog("For block domination relationships:\n");
+ for (unsigned i = 0; i < errors.size(); ++i) {
+ dataLog(
+ " ", pointerDump(errors[i].from), " -> ", pointerDump(errors[i].to),
+ " (", errors[i].message, ")\n");
+ }
+ dataLog("\n");
+ dataLog("Control flow graph:\n");
+ for (BlockIndex blockIndex = 0; blockIndex < graph.numBlocks(); ++blockIndex) {
+ BasicBlock* block = graph.block(blockIndex);
+ if (!block)
+ continue;
+ dataLog(" Block #", blockIndex, ": successors = [");
+ CommaPrinter comma;
+ for (unsigned i = 0; i < block->numSuccessors(); ++i)
+ dataLog(comma, *block->successor(i));
+ dataLog("], predecessors = [");
+ comma = CommaPrinter();
+ for (unsigned i = 0; i < block->predecessors.size(); ++i)
+ dataLog(comma, *block->predecessors[i]);
+ dataLog("]\n");
+ }
+ dataLog("\n");
+ dataLog("Lengauer-Tarjan Dominators:\n");
+ dataLog(dominators);
+ dataLog("\n");
+ dataLog("Naive Dominators:\n");
+ naiveDominators.dump(graph, WTF::dataFile());
+ dataLog("\n");
+ dataLog("Graph at time of failure:\n");
+ graph.dump();
+ dataLog("\n");
+ dataLog("DFG DOMINATOR VALIDATION FAILIED!\n");
+ CRASH();
+ }
+
+ Graph& graph;
+ Dominators& dominators;
+ NaiveDominators naiveDominators;
+
+ struct Error {
+ BasicBlock* from;
+ BasicBlock* to;
+ const char* message;
+ };
+
+ Vector<Error> errors;
+};
</ins><span class="cx">
</span><del>- // Prune dominators in all non entry blocks: backward scan.
- changed = false;
- for (unsigned i = numBlocks; i-- > 1;)
- changed |= pruneDominators(graph, i);
- } while (changed);
-}
</del><ins>+} // anonymous namespace
</ins><span class="cx">
</span><del>-bool Dominators::pruneDominators(Graph& graph, BlockIndex idx)
</del><ins>+void Dominators::compute(Graph& graph)
</ins><span class="cx"> {
</span><del>- BasicBlock* block = graph.block(idx);
</del><ins>+ LengauerTarjan lengauerTarjan(graph);
+ lengauerTarjan.compute();
</ins><span class="cx">
</span><del>- if (!block || block->predecessors.isEmpty())
- return false;
-
- // Find the intersection of dom(preds).
- m_scratch.set(m_results[block->predecessors[0]->index]);
- for (unsigned j = block->predecessors.size(); j-- > 1;)
- m_scratch.filter(m_results[block->predecessors[j]->index]);
-
- // The block is also dominated by itself.
- m_scratch.set(idx);
-
- return m_results[idx].setAndCheck(m_scratch);
-}
-
-void Dominators::dump(Graph& graph, PrintStream& out) const
-{
- for (BlockIndex blockIndex = 0; blockIndex < graph.numBlocks(); ++blockIndex) {
</del><ins>+ m_data = BlockMap<BlockData>(graph);
+
+ // From here we want to build a spanning tree with both upward and downward links and we want
+ // to do a search over this tree to compute pre and post numbers that can be used for dominance
+ // tests.
+
+ for (BlockIndex blockIndex = graph.numBlocks(); blockIndex--;) {
</ins><span class="cx"> BasicBlock* block = graph.block(blockIndex);
</span><span class="cx"> if (!block)
</span><span class="cx"> continue;
</span><del>- out.print(" Block ", *block, ":");
- for (BlockIndex otherIndex = 0; otherIndex < graph.numBlocks(); ++otherIndex) {
- if (!dominates(block->index, otherIndex))
</del><ins>+
+ BasicBlock* idomBlock = lengauerTarjan.immediateDominator(block);
+ m_data[block].idomParent = idomBlock;
+ if (idomBlock)
+ m_data[idomBlock].idomKids.append(block);
+ }
+
+ unsigned nextPreNumber = 0;
+ unsigned nextPostNumber = 0;
+
+ // Plain stack-based worklist because we are guaranteed to see each block exactly once anyway.
+ Vector<BlockWithOrder> worklist;
+ worklist.append(BlockWithOrder(graph.block(0), PreOrder));
+ while (!worklist.isEmpty()) {
+ BlockWithOrder item = worklist.takeLast();
+ switch (item.order) {
+ case PreOrder:
+ m_data[item.block].preNumber = nextPreNumber++;
+ worklist.append(BlockWithOrder(item.block, PostOrder));
+ for (BasicBlock* kid : m_data[item.block].idomKids)
+ worklist.append(BlockWithOrder(kid, PreOrder));
+ break;
+ case PostOrder:
+ m_data[item.block].postNumber = nextPostNumber++;
+ break;
+ }
+ }
+
+ if (validationEnabled()) {
+ // Check our dominator calculation:
+ // 1) Check that our range-based ancestry test is the same as a naive ancestry test.
+ // 2) Check that our notion of who dominates whom is identical to a naive (not
+ // Lengauer-Tarjan) dominator calculation.
+
+ ValidationContext context(graph, *this);
+ context.naiveDominators.compute(graph);
+
+ for (BlockIndex fromBlockIndex = graph.numBlocks(); fromBlockIndex--;) {
+ BasicBlock* fromBlock = graph.block(fromBlockIndex);
+ if (!fromBlock || m_data[fromBlock].preNumber == UINT_MAX)
</ins><span class="cx"> continue;
</span><del>- out.print(" #", otherIndex);
</del><ins>+ for (BlockIndex toBlockIndex = graph.numBlocks(); toBlockIndex--;) {
+ BasicBlock* toBlock = graph.block(toBlockIndex);
+ if (!toBlock || m_data[toBlock].preNumber == UINT_MAX)
+ continue;
+
+ if (dominates(fromBlock, toBlock) != naiveDominates(fromBlock, toBlock))
+ context.reportError(fromBlock, toBlock, "Range-based domination check is broken");
+ if (dominates(fromBlock, toBlock) != context.naiveDominators.dominates(fromBlock, toBlock))
+ context.reportError(fromBlock, toBlock, "Lengauer-Tarjan domination is broken");
+ }
</ins><span class="cx"> }
</span><del>- out.print("\n");
</del><ins>+
+ context.handleErrors();
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+bool Dominators::naiveDominates(BasicBlock* from, BasicBlock* to) const
+{
+ for (BasicBlock* block = to; block; block = m_data[block].idomParent) {
+ if (block == from)
+ return true;
+ }
+ return false;
+}
+
+void Dominators::dump(PrintStream& out) const
+{
+ if (!isValid()) {
+ out.print(" Not Valid.\n");
+ return;
+ }
+
+ for (BlockIndex blockIndex = 0; blockIndex < m_data.size(); ++blockIndex) {
+ if (m_data[blockIndex].preNumber == UINT_MAX)
+ continue;
+
+ out.print(" Block #", blockIndex, ": idom = ", pointerDump(m_data[blockIndex].idomParent), ", idomKids = [");
+ CommaPrinter comma;
+ for (unsigned i = 0; i < m_data[blockIndex].idomKids.size(); ++i)
+ out.print(comma, *m_data[blockIndex].idomKids[i]);
+ out.print("], pre/post = ", m_data[blockIndex].preNumber, "/", m_data[blockIndex].postNumber, "\n");
+ }
+}
+
</ins><span class="cx"> } } // namespace JSC::DFG
</span><span class="cx">
</span><span class="cx"> #endif // ENABLE(DFG_JIT)
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGDominatorsh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGDominators.h (173071 => 173072)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGDominators.h 2014-08-28 19:21:24 UTC (rev 173071)
+++ trunk/Source/JavaScriptCore/dfg/DFGDominators.h 2014-08-28 19:23:02 UTC (rev 173072)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2011 Apple Inc. All rights reserved.
</del><ins>+ * Copyright (C) 2011, 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">@@ -30,6 +30,7 @@
</span><span class="cx">
</span><span class="cx"> #include "DFGAnalysis.h"
</span><span class="cx"> #include "DFGBasicBlock.h"
</span><ins>+#include "DFGBlockMap.h"
</ins><span class="cx"> #include "DFGCommon.h"
</span><span class="cx"> #include <wtf/FastBitVector.h>
</span><span class="cx">
</span><span class="lines">@@ -44,24 +45,39 @@
</span><span class="cx">
</span><span class="cx"> void compute(Graph&);
</span><span class="cx">
</span><del>- bool dominates(BlockIndex from, BlockIndex to) const
</del><ins>+ bool strictlyDominates(BasicBlock* from, BasicBlock* to) const
</ins><span class="cx"> {
</span><span class="cx"> ASSERT(isValid());
</span><del>- return m_results[to].get(from);
</del><ins>+ return m_data[to].preNumber > m_data[from].preNumber
+ && m_data[to].postNumber < m_data[from].postNumber;
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> bool dominates(BasicBlock* from, BasicBlock* to) const
</span><span class="cx"> {
</span><del>- return dominates(from->index, to->index);
</del><ins>+ return from == to || strictlyDominates(from, to);
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- void dump(Graph&, PrintStream&) const;
</del><ins>+ void dump(PrintStream&) const;
</ins><span class="cx">
</span><span class="cx"> private:
</span><del>- bool pruneDominators(Graph&, BlockIndex);
</del><ins>+ bool naiveDominates(BasicBlock* from, BasicBlock* to) const;
</ins><span class="cx">
</span><del>- Vector<FastBitVector> m_results; // For each block, the bitvector of blocks that dominate it.
- FastBitVector m_scratch; // A temporary bitvector with bit for each block. We recycle this to save new/deletes.
</del><ins>+ struct BlockData {
+ BlockData()
+ : idomParent(nullptr)
+ , preNumber(UINT_MAX)
+ , postNumber(UINT_MAX)
+ {
+ }
+
+ Vector<BasicBlock*> idomKids;
+ BasicBlock* idomParent;
+
+ unsigned preNumber;
+ unsigned postNumber;
+ };
+
+ BlockMap<BlockData> m_data;
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> } } // namespace JSC::DFG
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGGraphcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGGraph.cpp (173071 => 173072)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGGraph.cpp 2014-08-28 19:21:24 UTC (rev 173071)
+++ trunk/Source/JavaScriptCore/dfg/DFGGraph.cpp 2014-08-28 19:23:02 UTC (rev 173072)
</span><span class="lines">@@ -31,6 +31,7 @@
</span><span class="cx"> #include "BytecodeLivenessAnalysisInlines.h"
</span><span class="cx"> #include "CodeBlock.h"
</span><span class="cx"> #include "CodeBlockWithJITType.h"
</span><ins>+#include "DFGBlockWorklist.h"
</ins><span class="cx"> #include "DFGClobberSet.h"
</span><span class="cx"> #include "DFGJITCode.h"
</span><span class="cx"> #include "DFGVariableAccessDataDump.h"
</span><span class="lines">@@ -370,15 +371,19 @@
</span><span class="cx"> if (m_dominators.isValid()) {
</span><span class="cx"> out.print(prefix, " Dominated by:");
</span><span class="cx"> for (size_t i = 0; i < m_blocks.size(); ++i) {
</span><del>- if (!m_dominators.dominates(i, block->index))
</del><ins>+ if (!this->block(i))
</ins><span class="cx"> continue;
</span><ins>+ if (!m_dominators.dominates(this->block(i), block))
+ continue;
</ins><span class="cx"> out.print(" #", i);
</span><span class="cx"> }
</span><span class="cx"> out.print("\n");
</span><span class="cx"> out.print(prefix, " Dominates:");
</span><span class="cx"> for (size_t i = 0; i < m_blocks.size(); ++i) {
</span><del>- if (!m_dominators.dominates(block->index, i))
</del><ins>+ if (!this->block(i))
</ins><span class="cx"> continue;
</span><ins>+ if (!m_dominators.dominates(block, this->block(i)))
+ continue;
</ins><span class="cx"> out.print(" #", i);
</span><span class="cx"> }
</span><span class="cx"> out.print("\n");
</span><span class="lines">@@ -635,73 +640,30 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><del>-// Utilities for pre- and post-order traversals.
-namespace {
-
-inline void addForPreOrder(Vector<BasicBlock*>& result, Vector<BasicBlock*, 16>& worklist, BitVector& seen, BasicBlock* block)
-{
- if (seen.get(block->index))
- return;
-
- result.append(block);
- worklist.append(block);
- seen.set(block->index);
-}
-
-enum PostOrderTaskKind {
- PostOrderFirstVisit,
- PostOrderAddToResult
-};
-
-struct PostOrderTask {
- PostOrderTask(BasicBlock* block = nullptr, PostOrderTaskKind kind = PostOrderFirstVisit)
- : m_block(block)
- , m_kind(kind)
- {
- }
-
- BasicBlock* m_block;
- PostOrderTaskKind m_kind;
-};
-
-inline void addForPostOrder(Vector<PostOrderTask, 16>& worklist, BitVector& seen, BasicBlock* block)
-{
- if (seen.get(block->index))
- return;
-
- worklist.append(PostOrderTask(block, PostOrderFirstVisit));
- seen.set(block->index);
-}
-
-} // anonymous namespace
-
</del><span class="cx"> void Graph::getBlocksInPreOrder(Vector<BasicBlock*>& result)
</span><span class="cx"> {
</span><del>- Vector<BasicBlock*, 16> worklist;
- BitVector seen;
- addForPreOrder(result, worklist, seen, block(0));
- while (!worklist.isEmpty()) {
- BasicBlock* block = worklist.takeLast();
</del><ins>+ BlockWorklist worklist;
+ worklist.push(block(0));
+ while (BasicBlock* block = worklist.pop()) {
+ result.append(block);
</ins><span class="cx"> for (unsigned i = block->numSuccessors(); i--;)
</span><del>- addForPreOrder(result, worklist, seen, block->successor(i));
</del><ins>+ worklist.push(block->successor(i));
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void Graph::getBlocksInPostOrder(Vector<BasicBlock*>& result)
</span><span class="cx"> {
</span><del>- Vector<PostOrderTask, 16> worklist;
- BitVector seen;
- addForPostOrder(worklist, seen, block(0));
- while (!worklist.isEmpty()) {
- PostOrderTask task = worklist.takeLast();
- switch (task.m_kind) {
- case PostOrderFirstVisit:
- worklist.append(PostOrderTask(task.m_block, PostOrderAddToResult));
- for (unsigned i = task.m_block->numSuccessors(); i--;)
- addForPostOrder(worklist, seen, task.m_block->successor(i));
</del><ins>+ PostOrderBlockWorklist worklist;
+ worklist.push(block(0));
+ while (BlockWithOrder item = worklist.pop()) {
+ switch (item.order) {
+ case PreOrder:
+ worklist.pushPost(item.block);
+ for (unsigned i = item.block->numSuccessors(); i--;)
+ worklist.push(item.block->successor(i));
</ins><span class="cx"> break;
</span><del>- case PostOrderAddToResult:
- result.append(task.m_block);
</del><ins>+ case PostOrder:
+ result.append(item.block);
</ins><span class="cx"> break;
</span><span class="cx"> }
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGInvalidationPointInjectionPhasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGInvalidationPointInjectionPhase.cpp (173071 => 173072)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGInvalidationPointInjectionPhase.cpp 2014-08-28 19:21:24 UTC (rev 173071)
+++ trunk/Source/JavaScriptCore/dfg/DFGInvalidationPointInjectionPhase.cpp 2014-08-28 19:23:02 UTC (rev 173072)
</span><span class="lines">@@ -28,6 +28,7 @@
</span><span class="cx">
</span><span class="cx"> #if ENABLE(DFG_JIT)
</span><span class="cx">
</span><ins>+#include "DFGBlockSet.h"
</ins><span class="cx"> #include "DFGClobberize.h"
</span><span class="cx"> #include "DFGGraph.h"
</span><span class="cx"> #include "DFGInsertionSet.h"
</span><span class="lines">@@ -50,7 +51,7 @@
</span><span class="cx"> {
</span><span class="cx"> ASSERT(m_graph.m_form != SSA);
</span><span class="cx">
</span><del>- BitVector blocksThatNeedInvalidationPoints;
</del><ins>+ BlockSet blocksThatNeedInvalidationPoints;
</ins><span class="cx">
</span><span class="cx"> for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
</span><span class="cx"> BasicBlock* block = m_graph.block(blockIndex);
</span><span class="lines">@@ -63,17 +64,18 @@
</span><span class="cx"> // Note: this assumes that control flow occurs at bytecode instruction boundaries.
</span><span class="cx"> if (m_originThatHadFire.isSet()) {
</span><span class="cx"> for (unsigned i = block->numSuccessors(); i--;)
</span><del>- blocksThatNeedInvalidationPoints.set(block->successor(i)->index);
</del><ins>+ blocksThatNeedInvalidationPoints.add(block->successor(i));
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> m_insertionSet.execute(block);
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
</span><del>- if (!blocksThatNeedInvalidationPoints.get(blockIndex))
</del><ins>+ BasicBlock* block = m_graph.block(blockIndex);
+
+ if (!blocksThatNeedInvalidationPoints.contains(block))
</ins><span class="cx"> continue;
</span><span class="cx">
</span><del>- BasicBlock* block = m_graph.block(blockIndex);
</del><span class="cx"> insertInvalidationCheck(0, block->at(0));
</span><span class="cx"> m_insertionSet.execute(block);
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGNaiveDominatorscpp"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/dfg/DFGNaiveDominators.cpp (0 => 173072)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGNaiveDominators.cpp (rev 0)
+++ trunk/Source/JavaScriptCore/dfg/DFGNaiveDominators.cpp 2014-08-28 19:23:02 UTC (rev 173072)
</span><span class="lines">@@ -0,0 +1,135 @@
</span><ins>+/*
+ * Copyright (C) 2011, 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 "DFGNaiveDominators.h"
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGGraph.h"
+#include "JSCInlines.h"
+
+namespace JSC { namespace DFG {
+
+NaiveDominators::NaiveDominators()
+{
+}
+
+NaiveDominators::~NaiveDominators()
+{
+}
+
+void NaiveDominators::compute(Graph& graph)
+{
+ // This implements a naive dominator solver.
+
+ ASSERT(graph.block(0)->predecessors.isEmpty());
+
+ unsigned numBlocks = graph.numBlocks();
+
+ // Allocate storage for the dense dominance matrix.
+ if (numBlocks > m_results.size()) {
+ m_results.grow(numBlocks);
+ for (unsigned i = numBlocks; i--;)
+ m_results[i].resize(numBlocks);
+ m_scratch.resize(numBlocks);
+ }
+
+ // We know that the entry block is only dominated by itself.
+ m_results[0].clearAll();
+ m_results[0].set(0);
+
+ // Find all of the valid blocks.
+ m_scratch.clearAll();
+ for (unsigned i = numBlocks; i--;) {
+ if (!graph.block(i))
+ continue;
+ m_scratch.set(i);
+ }
+
+ // Mark all nodes as dominated by everything.
+ for (unsigned i = numBlocks; i-- > 1;) {
+ if (!graph.block(i) || graph.block(i)->predecessors.isEmpty())
+ m_results[i].clearAll();
+ else
+ m_results[i].set(m_scratch);
+ }
+
+ // Iteratively eliminate nodes that are not dominator.
+ bool changed;
+ do {
+ changed = false;
+ // Prune dominators in all non entry blocks: forward scan.
+ for (unsigned i = 1; i < numBlocks; ++i)
+ changed |= pruneDominators(graph, i);
+
+ if (!changed)
+ break;
+
+ // Prune dominators in all non entry blocks: backward scan.
+ changed = false;
+ for (unsigned i = numBlocks; i-- > 1;)
+ changed |= pruneDominators(graph, i);
+ } while (changed);
+}
+
+bool NaiveDominators::pruneDominators(Graph& graph, BlockIndex idx)
+{
+ BasicBlock* block = graph.block(idx);
+
+ if (!block || block->predecessors.isEmpty())
+ return false;
+
+ // Find the intersection of dom(preds).
+ m_scratch.set(m_results[block->predecessors[0]->index]);
+ for (unsigned j = block->predecessors.size(); j-- > 1;)
+ m_scratch.filter(m_results[block->predecessors[j]->index]);
+
+ // The block is also dominated by itself.
+ m_scratch.set(idx);
+
+ return m_results[idx].setAndCheck(m_scratch);
+}
+
+void NaiveDominators::dump(Graph& graph, PrintStream& out) const
+{
+ for (BlockIndex blockIndex = 0; blockIndex < graph.numBlocks(); ++blockIndex) {
+ BasicBlock* block = graph.block(blockIndex);
+ if (!block)
+ continue;
+ out.print(" Block ", *block, ":");
+ for (BlockIndex otherIndex = 0; otherIndex < graph.numBlocks(); ++otherIndex) {
+ if (!dominates(block->index, otherIndex))
+ continue;
+ out.print(" #", otherIndex);
+ }
+ out.print("\n");
+ }
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGNaiveDominatorsh"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/dfg/DFGNaiveDominators.h (0 => 173072)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGNaiveDominators.h (rev 0)
+++ trunk/Source/JavaScriptCore/dfg/DFGNaiveDominators.h 2014-08-28 19:23:02 UTC (rev 173072)
</span><span class="lines">@@ -0,0 +1,71 @@
</span><ins>+/*
+ * Copyright (C) 2011, 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 DFGNaiveDominators_h
+#define DFGNaiveDominators_h
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGBasicBlock.h"
+#include "DFGCommon.h"
+#include <wtf/FastBitVector.h>
+
+namespace JSC { namespace DFG {
+
+class Graph;
+
+// This class is only used for validating the real dominators implementation.
+
+class NaiveDominators {
+public:
+ NaiveDominators();
+ ~NaiveDominators();
+
+ void compute(Graph&);
+
+ bool dominates(BlockIndex from, BlockIndex to) const
+ {
+ return m_results[to].get(from);
+ }
+
+ bool dominates(BasicBlock* from, BasicBlock* to) const
+ {
+ return dominates(from->index, to->index);
+ }
+
+ void dump(Graph&, PrintStream&) const;
+
+private:
+ bool pruneDominators(Graph&, BlockIndex);
+
+ Vector<FastBitVector> m_results; // For each block, the bitvector of blocks that dominate it.
+ FastBitVector m_scratch; // A temporary bitvector with bit for each block. We recycle this to save new/deletes.
+};
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGNaiveDominators_h
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGNaturalLoopscpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGNaturalLoops.cpp (173071 => 173072)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGNaturalLoops.cpp 2014-08-28 19:21:24 UTC (rev 173071)
+++ trunk/Source/JavaScriptCore/dfg/DFGNaturalLoops.cpp 2014-08-28 19:23:02 UTC (rev 173072)
</span><span class="lines">@@ -45,6 +45,11 @@
</span><span class="cx"> NaturalLoops::NaturalLoops() { }
</span><span class="cx"> NaturalLoops::~NaturalLoops() { }
</span><span class="cx">
</span><ins>+void NaturalLoops::computeDependencies(Graph& graph)
+{
+ graph.m_dominators.computeIfNecessary(graph);
+}
+
</ins><span class="cx"> void NaturalLoops::compute(Graph& graph)
</span><span class="cx"> {
</span><span class="cx"> // Implement the classic dominator-based natural loop finder. The first
</span><span class="lines">@@ -57,11 +62,9 @@
</span><span class="cx">
</span><span class="cx"> static const bool verbose = false;
</span><span class="cx">
</span><del>- graph.m_dominators.computeIfNecessary(graph);
-
</del><span class="cx"> if (verbose) {
</span><span class="cx"> dataLog("Dominators:\n");
</span><del>- graph.m_dominators.dump(graph, WTF::dataFile());
</del><ins>+ graph.m_dominators.dump(WTF::dataFile());
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> m_loops.resize(0);
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGNaturalLoopsh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGNaturalLoops.h (173071 => 173072)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGNaturalLoops.h 2014-08-28 19:21:24 UTC (rev 173071)
+++ trunk/Source/JavaScriptCore/dfg/DFGNaturalLoops.h 2014-08-28 19:23:02 UTC (rev 173072)
</span><span class="lines">@@ -93,6 +93,7 @@
</span><span class="cx"> NaturalLoops();
</span><span class="cx"> ~NaturalLoops();
</span><span class="cx">
</span><ins>+ void computeDependencies(Graph&);
</ins><span class="cx"> void compute(Graph&);
</span><span class="cx">
</span><span class="cx"> unsigned numLoops() const
</span></span></pre></div>
<a id="trunkSourceWTFChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/ChangeLog (173071 => 173072)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/ChangeLog 2014-08-28 19:21:24 UTC (rev 173071)
+++ trunk/Source/WTF/ChangeLog 2014-08-28 19:23:02 UTC (rev 173072)
</span><span class="lines">@@ -1,5 +1,22 @@
</span><span class="cx"> 2014-08-27 Filip Pizlo <fpizlo@apple.com>
</span><span class="cx">
</span><ins>+ DFG should compute immediate dominators using the O(n log n) form of Lengauer and Tarjan's "A Fast Algorithm for Finding Dominators in a Flowgraph"
+ https://bugs.webkit.org/show_bug.cgi?id=93361
+
+ Reviewed by Mark Hahnenberg.
+
+ Make BitVector operations return the previous value of the bit you're changing. This is
+ useful for the kinds of set operations that are commonplace in compiler graph searches.
+
+ * wtf/BitVector.h:
+ (WTF::BitVector::quickSet):
+ (WTF::BitVector::quickClear):
+ (WTF::BitVector::set):
+ (WTF::BitVector::ensureSizeAndSet):
+ (WTF::BitVector::clear):
+
+2014-08-27 Filip Pizlo <fpizlo@apple.com>
+
</ins><span class="cx"> FTL should be able to do polymorphic call inlining
</span><span class="cx"> https://bugs.webkit.org/show_bug.cgi?id=135145
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWTFwtfBitVectorh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/BitVector.h (173071 => 173072)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/BitVector.h 2014-08-28 19:21:24 UTC (rev 173071)
+++ trunk/Source/WTF/wtf/BitVector.h 2014-08-28 19:23:02 UTC (rev 173072)
</span><span class="lines">@@ -117,24 +117,31 @@
</span><span class="cx"> return !!(bits()[bit / bitsInPointer()] & (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1))));
</span><span class="cx"> }
</span><span class="cx">
</span><del>- void quickSet(size_t bit)
</del><ins>+ bool quickSet(size_t bit)
</ins><span class="cx"> {
</span><span class="cx"> ASSERT_WITH_SECURITY_IMPLICATION(bit < size());
</span><del>- bits()[bit / bitsInPointer()] |= (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)));
</del><ins>+ uintptr_t& word = bits()[bit / bitsInPointer()];
+ uintptr_t mask = static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1));
+ bool result = !!(word & mask);
+ word |= mask;
+ return result;
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- void quickClear(size_t bit)
</del><ins>+ bool quickClear(size_t bit)
</ins><span class="cx"> {
</span><span class="cx"> ASSERT_WITH_SECURITY_IMPLICATION(bit < size());
</span><del>- bits()[bit / bitsInPointer()] &= ~(static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)));
</del><ins>+ uintptr_t& word = bits()[bit / bitsInPointer()];
+ uintptr_t mask = static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1));
+ bool result = !!(word & mask);
+ word &= ~mask;
+ return result;
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- void quickSet(size_t bit, bool value)
</del><ins>+ bool quickSet(size_t bit, bool value)
</ins><span class="cx"> {
</span><span class="cx"> if (value)
</span><del>- quickSet(bit);
- else
- quickClear(bit);
</del><ins>+ return quickSet(bit);
+ return quickClear(bit);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> bool get(size_t bit) const
</span><span class="lines">@@ -144,31 +151,30 @@
</span><span class="cx"> return quickGet(bit);
</span><span class="cx"> }
</span><span class="cx">
</span><del>- void set(size_t bit)
</del><ins>+ bool set(size_t bit)
</ins><span class="cx"> {
</span><span class="cx"> ensureSize(bit + 1);
</span><del>- quickSet(bit);
</del><ins>+ return quickSet(bit);
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- void ensureSizeAndSet(size_t bit, size_t size)
</del><ins>+ bool ensureSizeAndSet(size_t bit, size_t size)
</ins><span class="cx"> {
</span><span class="cx"> ensureSize(size);
</span><del>- quickSet(bit);
</del><ins>+ return quickSet(bit);
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- void clear(size_t bit)
</del><ins>+ bool clear(size_t bit)
</ins><span class="cx"> {
</span><span class="cx"> if (bit >= size())
</span><del>- return;
- quickClear(bit);
</del><ins>+ return false;
+ return quickClear(bit);
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- void set(size_t bit, bool value)
</del><ins>+ bool set(size_t bit, bool value)
</ins><span class="cx"> {
</span><span class="cx"> if (value)
</span><del>- set(bit);
- else
- clear(bit);
</del><ins>+ return set(bit);
+ return clear(bit);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void merge(const BitVector& other)
</span></span></pre>
</div>
</div>
</body>
</html>