<!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>[191870] 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/191870">191870</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2015-11-01 16:48:03 -0800 (Sun, 01 Nov 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>Dominators should be factored out of the DFG
https://bugs.webkit.org/show_bug.cgi?id=150764
Reviewed by Geoffrey Garen.
Source/JavaScriptCore:
Factored DFGDominators.h/DFGDominators.cpp into WTF. To do this, I made two changes to the
DFG:
1) DFG now has a CFG abstraction called DFG::CFG. The cool thing about this is that in the
future if we wanted to support inverted dominators, we could do it by just creating a
DFG::BackwardCFG.
2) Got rid of DFG::Analysis. From now on, an Analysis being invalidated is expressed by the
DFG::Graph having a null pointer for that analysis. When we "run" the analysis, we
just instantiate it. This makes it much more natural to integrate WTF::Dominators into
the DFG.
* CMakeLists.txt:
* JavaScriptCore.xcodeproj/project.pbxproj:
* dfg/DFGAnalysis.h: Removed.
* dfg/DFGCFG.h: Added.
(JSC::DFG::CFG::CFG):
(JSC::DFG::CFG::root):
(JSC::DFG::CFG::newMap<T>):
(JSC::DFG::CFG::successors):
(JSC::DFG::CFG::predecessors):
(JSC::DFG::CFG::index):
(JSC::DFG::CFG::node):
(JSC::DFG::CFG::numNodes):
(JSC::DFG::CFG::dump):
* dfg/DFGCSEPhase.cpp:
* dfg/DFGDisassembler.cpp:
(JSC::DFG::Disassembler::createDumpList):
* dfg/DFGDominators.cpp: Removed.
* dfg/DFGDominators.h:
(JSC::DFG::Dominators::Dominators):
(JSC::DFG::Dominators::strictlyDominates): Deleted.
(JSC::DFG::Dominators::dominates): Deleted.
(JSC::DFG::Dominators::immediateDominatorOf): Deleted.
(JSC::DFG::Dominators::forAllStrictDominatorsOf): Deleted.
(JSC::DFG::Dominators::forAllDominatorsOf): Deleted.
(JSC::DFG::Dominators::forAllBlocksStrictlyDominatedBy): Deleted.
(JSC::DFG::Dominators::forAllBlocksDominatedBy): Deleted.
(JSC::DFG::Dominators::forAllBlocksInDominanceFrontierOf): Deleted.
(JSC::DFG::Dominators::forAllBlocksInIteratedDominanceFrontierOf): Deleted.
(JSC::DFG::Dominators::forAllBlocksInPrunedIteratedDominanceFrontierOf): Deleted.
(JSC::DFG::Dominators::forAllBlocksInDominanceFrontierOfImpl): Deleted.
(JSC::DFG::Dominators::forAllBlocksInIteratedDominanceFrontierOfImpl): Deleted.
(JSC::DFG::Dominators::BlockData::BlockData): Deleted.
* dfg/DFGEdgeDominates.h:
(JSC::DFG::EdgeDominates::operator()):
* dfg/DFGGraph.cpp:
(JSC::DFG::Graph::Graph):
(JSC::DFG::Graph::dumpBlockHeader):
(JSC::DFG::Graph::invalidateCFG):
(JSC::DFG::Graph::substituteGetLocal):
(JSC::DFG::Graph::handleAssertionFailure):
(JSC::DFG::Graph::ensureDominators):
(JSC::DFG::Graph::ensurePrePostNumbering):
(JSC::DFG::Graph::ensureNaturalLoops):
(JSC::DFG::Graph::valueProfileFor):
* dfg/DFGGraph.h:
(JSC::DFG::Graph::hasDebuggerEnabled):
* dfg/DFGLICMPhase.cpp:
(JSC::DFG::LICMPhase::run):
(JSC::DFG::LICMPhase::attemptHoist):
* dfg/DFGLoopPreHeaderCreationPhase.cpp:
(JSC::DFG::createPreHeader):
(JSC::DFG::LoopPreHeaderCreationPhase::run):
* dfg/DFGNaturalLoops.cpp:
(JSC::DFG::NaturalLoop::dump):
(JSC::DFG::NaturalLoops::NaturalLoops):
(JSC::DFG::NaturalLoops::~NaturalLoops):
(JSC::DFG::NaturalLoops::loopsOf):
(JSC::DFG::NaturalLoops::computeDependencies): Deleted.
(JSC::DFG::NaturalLoops::compute): Deleted.
* dfg/DFGNaturalLoops.h:
(JSC::DFG::NaturalLoops::numLoops):
* dfg/DFGNode.h:
(JSC::DFG::Node::SuccessorsIterable::end):
(JSC::DFG::Node::SuccessorsIterable::size):
(JSC::DFG::Node::SuccessorsIterable::at):
(JSC::DFG::Node::SuccessorsIterable::operator[]):
* dfg/DFGOSREntrypointCreationPhase.cpp:
(JSC::DFG::OSREntrypointCreationPhase::run):
* dfg/DFGObjectAllocationSinkingPhase.cpp:
* dfg/DFGPlan.cpp:
(JSC::DFG::Plan::compileInThreadImpl):
* dfg/DFGPrePostNumbering.cpp:
(JSC::DFG::PrePostNumbering::PrePostNumbering):
(JSC::DFG::PrePostNumbering::~PrePostNumbering):
(JSC::DFG::PrePostNumbering::compute): Deleted.
* dfg/DFGPrePostNumbering.h:
(JSC::DFG::PrePostNumbering::preNumber):
(JSC::DFG::PrePostNumbering::postNumber):
* dfg/DFGPutStackSinkingPhase.cpp:
* dfg/DFGSSACalculator.cpp:
(JSC::DFG::SSACalculator::nonLocalReachingDef):
(JSC::DFG::SSACalculator::reachingDefAtTail):
* dfg/DFGSSACalculator.h:
(JSC::DFG::SSACalculator::computePhis):
* dfg/DFGSSAConversionPhase.cpp:
(JSC::DFG::SSAConversionPhase::run):
* ftl/FTLLink.cpp:
(JSC::FTL::link):
* ftl/FTLLowerDFGToLLVM.cpp:
(JSC::FTL::DFG::LowerDFGToLLVM::lower):
(JSC::FTL::DFG::LowerDFGToLLVM::safelyInvalidateAfterTermination):
(JSC::FTL::DFG::LowerDFGToLLVM::isValid):
Source/WTF:
This takes what used to be DFGDominators.h/DFGDominators.cpp and turns it into a generic
algorithm that can take any abstract graph. The idea is that you create Dominators<CFG> and
pass it a CFG object, which defines the types of graph nodes and methods for getting
successors, predecessors, etc. The DFG now defines a class called CFG, which is a wrapper for
DFG::Graph that conforms to the thing that wtf/Dominators.h expects.
When doing things to graphs, it's common to refer to the things in the graph as "nodes".
Because I intend to reuse the CFG abstraction with many graph algorithms, that abstraction uses
the term "node" to refer to a DFG basic block. But in Dominators, the method and variable names
still use "block". This is because although Dominators are applicable to any kind of directed
graph, it's super unlikely that we will ever use them for anything but compilers. Indeed, the
only reason why I'm factoring them out of the DFG is so that I can use them with B3 and Air.
This has the nice side effect that a user of WTF::Dominators<JSC::DFG::CFG> will see familiar
terminology like "blocksStrictlyDominatedBy(...)" instead of "nodesStrictlyDominatedBy(...)",
which would be super confusing.
Overall, wtf/Dominators.h is a combination of what used to be in DFGDominators.h,
DFGDominators.cpp, DFGNaiveDominators.h, and DFGNaiveDominators.cpp. I only changed code when I
had to in order to make it generic.
* WTF.xcodeproj/project.pbxproj:
* wtf/CMakeLists.txt:
* wtf/Dominators.h: Added.
(WTF::Dominators::Dominators):
(WTF::Dominators::compute):
(WTF::Dominators::strictlyDominates):
(WTF::Dominators::dominates):
(WTF::Dominators::immediateDominatorOf):
(WTF::Dominators::forAllStrictDominatorsOf):
(WTF::Dominators::forAllDominatorsOf):
(WTF::Dominators::forAllBlocksStrictlyDominatedBy):
(WTF::Dominators::forAllBlocksDominatedBy):
(WTF::Dominators::strictDominatorsOf):
(WTF::Dominators::dominatorsOf):
(WTF::Dominators::blocksStrictlyDominatedBy):
(WTF::Dominators::blocksDominatedBy):
(WTF::Dominators::forAllBlocksInDominanceFrontierOf):
(WTF::Dominators::dominanceFrontierOf):
(WTF::Dominators::forAllBlocksInIteratedDominanceFrontierOf):
(WTF::Dominators::forAllBlocksInPrunedIteratedDominanceFrontierOf):
(WTF::Dominators::iteratedDominanceFrontierOf):
(WTF::Dominators::dump):
(WTF::Dominators::LengauerTarjan::LengauerTarjan):
(WTF::Dominators::LengauerTarjan::compute):
(WTF::Dominators::LengauerTarjan::immediateDominator):
(WTF::Dominators::LengauerTarjan::computeDepthFirstPreNumbering):
(WTF::Dominators::LengauerTarjan::computeSemiDominatorsAndImplicitImmediateDominators):
(WTF::Dominators::LengauerTarjan::computeExplicitImmediateDominators):
(WTF::Dominators::LengauerTarjan::link):
(WTF::Dominators::LengauerTarjan::eval):
(WTF::Dominators::LengauerTarjan::compress):
(WTF::Dominators::LengauerTarjan::BlockData::BlockData):
(WTF::Dominators::NaiveDominators::NaiveDominators):
(WTF::Dominators::NaiveDominators::dominates):
(WTF::Dominators::NaiveDominators::dump):
(WTF::Dominators::NaiveDominators::pruneDominators):
(WTF::Dominators::ValidationContext::ValidationContext):
(WTF::Dominators::ValidationContext::reportError):
(WTF::Dominators::ValidationContext::handleErrors):
(WTF::Dominators::naiveDominates):
(WTF::Dominators::forAllBlocksInDominanceFrontierOfImpl):
(WTF::Dominators::forAllBlocksInIteratedDominanceFrontierOfImpl):
(WTF::Dominators::BlockData::BlockData):</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="#trunkSourceJavaScriptCoreJavaScriptCorexcodeprojprojectpbxproj">trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGCSEPhasecpp">trunk/Source/JavaScriptCore/dfg/DFGCSEPhase.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGDisassemblercpp">trunk/Source/JavaScriptCore/dfg/DFGDisassembler.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGDominatorsh">trunk/Source/JavaScriptCore/dfg/DFGDominators.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGEdgeDominatesh">trunk/Source/JavaScriptCore/dfg/DFGEdgeDominates.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGGraphcpp">trunk/Source/JavaScriptCore/dfg/DFGGraph.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGGraphh">trunk/Source/JavaScriptCore/dfg/DFGGraph.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGIntegerRangeOptimizationPhasecpp">trunk/Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGLICMPhasecpp">trunk/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGLoopPreHeaderCreationPhasecpp">trunk/Source/JavaScriptCore/dfg/DFGLoopPreHeaderCreationPhase.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="#trunkSourceJavaScriptCoredfgDFGNodeh">trunk/Source/JavaScriptCore/dfg/DFGNode.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGOSREntrypointCreationPhasecpp">trunk/Source/JavaScriptCore/dfg/DFGOSREntrypointCreationPhase.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGObjectAllocationSinkingPhasecpp">trunk/Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGPlancpp">trunk/Source/JavaScriptCore/dfg/DFGPlan.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGPrePostNumberingcpp">trunk/Source/JavaScriptCore/dfg/DFGPrePostNumbering.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGPrePostNumberingh">trunk/Source/JavaScriptCore/dfg/DFGPrePostNumbering.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGPutStackSinkingPhasecpp">trunk/Source/JavaScriptCore/dfg/DFGPutStackSinkingPhase.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGSSACalculatorcpp">trunk/Source/JavaScriptCore/dfg/DFGSSACalculator.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGSSACalculatorh">trunk/Source/JavaScriptCore/dfg/DFGSSACalculator.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGSSAConversionPhasecpp">trunk/Source/JavaScriptCore/dfg/DFGSSAConversionPhase.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGStaticExecutionCountEstimationPhasecpp">trunk/Source/JavaScriptCore/dfg/DFGStaticExecutionCountEstimationPhase.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGTierUpCheckInjectionPhasecpp">trunk/Source/JavaScriptCore/dfg/DFGTierUpCheckInjectionPhase.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreftlFTLLinkcpp">trunk/Source/JavaScriptCore/ftl/FTLLink.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreftlFTLLowerDFGToLLVMcpp">trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp</a></li>
<li><a href="#trunkSourceWTFChangeLog">trunk/Source/WTF/ChangeLog</a></li>
<li><a href="#trunkSourceWTFWTFxcodeprojprojectpbxproj">trunk/Source/WTF/WTF.xcodeproj/project.pbxproj</a></li>
<li><a href="#trunkSourceWTFwtfCMakeListstxt">trunk/Source/WTF/wtf/CMakeLists.txt</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoredfgDFGCFGh">trunk/Source/JavaScriptCore/dfg/DFGCFG.h</a></li>
<li><a href="#trunkSourceWTFwtfDominatorsh">trunk/Source/WTF/wtf/Dominators.h</a></li>
</ul>
<h3>Removed Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoredfgDFGAnalysish">trunk/Source/JavaScriptCore/dfg/DFGAnalysis.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGDominatorscpp">trunk/Source/JavaScriptCore/dfg/DFGDominators.cpp</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 (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/CMakeLists.txt 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/JavaScriptCore/CMakeLists.txt 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -233,7 +233,6 @@
</span><span class="cx"> dfg/DFGDesiredWeakReferences.cpp
</span><span class="cx"> dfg/DFGDisassembler.cpp
</span><span class="cx"> dfg/DFGDoesGC.cpp
</span><del>- dfg/DFGDominators.cpp
</del><span class="cx"> dfg/DFGDriver.cpp
</span><span class="cx"> dfg/DFGEdge.cpp
</span><span class="cx"> dfg/DFGEpoch.cpp
</span><span class="lines">@@ -270,7 +269,6 @@
</span><span class="cx"> dfg/DFGMinifiedNode.cpp
</span><span class="cx"> dfg/DFGMovHintRemovalPhase.cpp
</span><span class="cx"> dfg/DFGMultiGetByOffsetData.cpp
</span><del>- dfg/DFGNaiveDominators.cpp
</del><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 (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/JavaScriptCore/ChangeLog 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -1,3 +1,115 @@
</span><ins>+2015-11-01 Filip Pizlo <fpizlo@apple.com>
+
+ Dominators should be factored out of the DFG
+ https://bugs.webkit.org/show_bug.cgi?id=150764
+
+ Reviewed by Geoffrey Garen.
+
+ Factored DFGDominators.h/DFGDominators.cpp into WTF. To do this, I made two changes to the
+ DFG:
+
+ 1) DFG now has a CFG abstraction called DFG::CFG. The cool thing about this is that in the
+ future if we wanted to support inverted dominators, we could do it by just creating a
+ DFG::BackwardCFG.
+
+ 2) Got rid of DFG::Analysis. From now on, an Analysis being invalidated is expressed by the
+ DFG::Graph having a null pointer for that analysis. When we "run" the analysis, we
+ just instantiate it. This makes it much more natural to integrate WTF::Dominators into
+ the DFG.
+
+ * CMakeLists.txt:
+ * JavaScriptCore.xcodeproj/project.pbxproj:
+ * dfg/DFGAnalysis.h: Removed.
+ * dfg/DFGCFG.h: Added.
+ (JSC::DFG::CFG::CFG):
+ (JSC::DFG::CFG::root):
+ (JSC::DFG::CFG::newMap<T>):
+ (JSC::DFG::CFG::successors):
+ (JSC::DFG::CFG::predecessors):
+ (JSC::DFG::CFG::index):
+ (JSC::DFG::CFG::node):
+ (JSC::DFG::CFG::numNodes):
+ (JSC::DFG::CFG::dump):
+ * dfg/DFGCSEPhase.cpp:
+ * dfg/DFGDisassembler.cpp:
+ (JSC::DFG::Disassembler::createDumpList):
+ * dfg/DFGDominators.cpp: Removed.
+ * dfg/DFGDominators.h:
+ (JSC::DFG::Dominators::Dominators):
+ (JSC::DFG::Dominators::strictlyDominates): Deleted.
+ (JSC::DFG::Dominators::dominates): Deleted.
+ (JSC::DFG::Dominators::immediateDominatorOf): Deleted.
+ (JSC::DFG::Dominators::forAllStrictDominatorsOf): Deleted.
+ (JSC::DFG::Dominators::forAllDominatorsOf): Deleted.
+ (JSC::DFG::Dominators::forAllBlocksStrictlyDominatedBy): Deleted.
+ (JSC::DFG::Dominators::forAllBlocksDominatedBy): Deleted.
+ (JSC::DFG::Dominators::forAllBlocksInDominanceFrontierOf): Deleted.
+ (JSC::DFG::Dominators::forAllBlocksInIteratedDominanceFrontierOf): Deleted.
+ (JSC::DFG::Dominators::forAllBlocksInPrunedIteratedDominanceFrontierOf): Deleted.
+ (JSC::DFG::Dominators::forAllBlocksInDominanceFrontierOfImpl): Deleted.
+ (JSC::DFG::Dominators::forAllBlocksInIteratedDominanceFrontierOfImpl): Deleted.
+ (JSC::DFG::Dominators::BlockData::BlockData): Deleted.
+ * dfg/DFGEdgeDominates.h:
+ (JSC::DFG::EdgeDominates::operator()):
+ * dfg/DFGGraph.cpp:
+ (JSC::DFG::Graph::Graph):
+ (JSC::DFG::Graph::dumpBlockHeader):
+ (JSC::DFG::Graph::invalidateCFG):
+ (JSC::DFG::Graph::substituteGetLocal):
+ (JSC::DFG::Graph::handleAssertionFailure):
+ (JSC::DFG::Graph::ensureDominators):
+ (JSC::DFG::Graph::ensurePrePostNumbering):
+ (JSC::DFG::Graph::ensureNaturalLoops):
+ (JSC::DFG::Graph::valueProfileFor):
+ * dfg/DFGGraph.h:
+ (JSC::DFG::Graph::hasDebuggerEnabled):
+ * dfg/DFGLICMPhase.cpp:
+ (JSC::DFG::LICMPhase::run):
+ (JSC::DFG::LICMPhase::attemptHoist):
+ * dfg/DFGLoopPreHeaderCreationPhase.cpp:
+ (JSC::DFG::createPreHeader):
+ (JSC::DFG::LoopPreHeaderCreationPhase::run):
+ * dfg/DFGNaturalLoops.cpp:
+ (JSC::DFG::NaturalLoop::dump):
+ (JSC::DFG::NaturalLoops::NaturalLoops):
+ (JSC::DFG::NaturalLoops::~NaturalLoops):
+ (JSC::DFG::NaturalLoops::loopsOf):
+ (JSC::DFG::NaturalLoops::computeDependencies): Deleted.
+ (JSC::DFG::NaturalLoops::compute): Deleted.
+ * dfg/DFGNaturalLoops.h:
+ (JSC::DFG::NaturalLoops::numLoops):
+ * dfg/DFGNode.h:
+ (JSC::DFG::Node::SuccessorsIterable::end):
+ (JSC::DFG::Node::SuccessorsIterable::size):
+ (JSC::DFG::Node::SuccessorsIterable::at):
+ (JSC::DFG::Node::SuccessorsIterable::operator[]):
+ * dfg/DFGOSREntrypointCreationPhase.cpp:
+ (JSC::DFG::OSREntrypointCreationPhase::run):
+ * dfg/DFGObjectAllocationSinkingPhase.cpp:
+ * dfg/DFGPlan.cpp:
+ (JSC::DFG::Plan::compileInThreadImpl):
+ * dfg/DFGPrePostNumbering.cpp:
+ (JSC::DFG::PrePostNumbering::PrePostNumbering):
+ (JSC::DFG::PrePostNumbering::~PrePostNumbering):
+ (JSC::DFG::PrePostNumbering::compute): Deleted.
+ * dfg/DFGPrePostNumbering.h:
+ (JSC::DFG::PrePostNumbering::preNumber):
+ (JSC::DFG::PrePostNumbering::postNumber):
+ * dfg/DFGPutStackSinkingPhase.cpp:
+ * dfg/DFGSSACalculator.cpp:
+ (JSC::DFG::SSACalculator::nonLocalReachingDef):
+ (JSC::DFG::SSACalculator::reachingDefAtTail):
+ * dfg/DFGSSACalculator.h:
+ (JSC::DFG::SSACalculator::computePhis):
+ * dfg/DFGSSAConversionPhase.cpp:
+ (JSC::DFG::SSAConversionPhase::run):
+ * ftl/FTLLink.cpp:
+ (JSC::FTL::link):
+ * ftl/FTLLowerDFGToLLVM.cpp:
+ (JSC::FTL::DFG::LowerDFGToLLVM::lower):
+ (JSC::FTL::DFG::LowerDFGToLLVM::safelyInvalidateAfterTermination):
+ (JSC::FTL::DFG::LowerDFGToLLVM::isValid):
+
</ins><span class="cx"> 2015-10-31 Filip Pizlo <fpizlo@apple.com>
</span><span class="cx">
</span><span class="cx"> B3::reduceStrength's DCE should be more agro and less wrong
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreJavaScriptCorexcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -553,8 +553,6 @@
</span><span class="cx"> 0FC3CCFD19ADA410006AC72A /* DFGBlockMapInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC3CCF619ADA410006AC72A /* DFGBlockMapInlines.h */; };
</span><span class="cx"> 0FC3CCFE19ADA410006AC72A /* DFGBlockSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC3CCF719ADA410006AC72A /* DFGBlockSet.h */; };
</span><span class="cx"> 0FC3CD0019ADA410006AC72A /* DFGBlockWorklist.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC3CCF919ADA410006AC72A /* DFGBlockWorklist.h */; };
</span><del>- 0FC3CD0119ADA411006AC72A /* DFGNaiveDominators.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FC3CCFA19ADA410006AC72A /* DFGNaiveDominators.cpp */; };
- 0FC3CD0219ADA411006AC72A /* DFGNaiveDominators.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC3CCFB19ADA410006AC72A /* DFGNaiveDominators.h */; };
</del><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">@@ -605,7 +603,6 @@
</span><span class="cx"> 0FD3E40C1B618B6600C80E1E /* ObjectPropertyConditionSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FD3E4061B618B6600C80E1E /* ObjectPropertyConditionSet.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 0FD3E40D1B618B6600C80E1E /* PropertyCondition.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FD3E4071B618B6600C80E1E /* PropertyCondition.cpp */; };
</span><span class="cx"> 0FD3E40E1B618B6600C80E1E /* PropertyCondition.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FD3E4081B618B6600C80E1E /* PropertyCondition.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><del>- 0FD81AD2154FB4EE00983E72 /* DFGDominators.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FD81ACF154FB4EB00983E72 /* DFGDominators.cpp */; };
</del><span class="cx"> 0FD81AD3154FB4F000983E72 /* DFGDominators.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FD81AD0154FB4EB00983E72 /* DFGDominators.h */; };
</span><span class="cx"> 0FD82E2114172CE300179C94 /* DFGCapabilities.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FD82E1E14172C2F00179C94 /* DFGCapabilities.cpp */; };
</span><span class="cx"> 0FD82E39141AB14D00179C94 /* CompactJITCodeMap.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FD82E37141AB14200179C94 /* CompactJITCodeMap.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="lines">@@ -1591,7 +1588,6 @@
</span><span class="cx"> A730B6121250068F009D25B1 /* StrictEvalActivation.h in Headers */ = {isa = PBXBuildFile; fileRef = A730B6101250068F009D25B1 /* StrictEvalActivation.h */; };
</span><span class="cx"> A730B6131250068F009D25B1 /* StrictEvalActivation.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A730B6111250068F009D25B1 /* StrictEvalActivation.cpp */; };
</span><span class="cx"> A731B25A130093880040A7FA /* Foundation.framework in Frameworks */ = {isa = PBXBuildFile; fileRef = 51F0EB6105C86C6B00E6DF1B /* Foundation.framework */; };
</span><del>- A737810C1799EA2E00817533 /* DFGAnalysis.h in Headers */ = {isa = PBXBuildFile; fileRef = A73781091799EA2E00817533 /* DFGAnalysis.h */; };
</del><span class="cx"> A737810D1799EA2E00817533 /* DFGNaturalLoops.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A737810A1799EA2E00817533 /* DFGNaturalLoops.cpp */; };
</span><span class="cx"> A737810E1799EA2E00817533 /* DFGNaturalLoops.h in Headers */ = {isa = PBXBuildFile; fileRef = A737810B1799EA2E00817533 /* DFGNaturalLoops.h */; };
</span><span class="cx"> A7386554118697B400540279 /* SpecializedThunkJIT.h in Headers */ = {isa = PBXBuildFile; fileRef = A7386551118697B400540279 /* SpecializedThunkJIT.h */; };
</span><span class="lines">@@ -2583,8 +2579,6 @@
</span><span class="cx"> 0FC3CCF619ADA410006AC72A /* DFGBlockMapInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBlockMapInlines.h; path = dfg/DFGBlockMapInlines.h; sourceTree = "<group>"; };
</span><span class="cx"> 0FC3CCF719ADA410006AC72A /* DFGBlockSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBlockSet.h; path = dfg/DFGBlockSet.h; sourceTree = "<group>"; };
</span><span class="cx"> 0FC3CCF919ADA410006AC72A /* DFGBlockWorklist.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBlockWorklist.h; path = dfg/DFGBlockWorklist.h; sourceTree = "<group>"; };
</span><del>- 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>"; };
</del><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">@@ -2637,7 +2631,6 @@
</span><span class="cx"> 0FD3E4071B618B6600C80E1E /* PropertyCondition.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = PropertyCondition.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 0FD3E4081B618B6600C80E1E /* PropertyCondition.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = PropertyCondition.h; sourceTree = "<group>"; };
</span><span class="cx"> 0FD5652216AB780A00197653 /* DFGBasicBlockInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBasicBlockInlines.h; path = dfg/DFGBasicBlockInlines.h; sourceTree = "<group>"; };
</span><del>- 0FD81ACF154FB4EB00983E72 /* DFGDominators.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGDominators.cpp; path = dfg/DFGDominators.cpp; sourceTree = "<group>"; };
</del><span class="cx"> 0FD81AD0154FB4EB00983E72 /* DFGDominators.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGDominators.h; path = dfg/DFGDominators.h; sourceTree = "<group>"; };
</span><span class="cx"> 0FD82E1E14172C2F00179C94 /* DFGCapabilities.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGCapabilities.cpp; path = dfg/DFGCapabilities.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 0FD82E1F14172C2F00179C94 /* DFGCapabilities.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGCapabilities.h; path = dfg/DFGCapabilities.h; sourceTree = "<group>"; };
</span><span class="lines">@@ -3651,7 +3644,6 @@
</span><span class="cx"> A7299DA417D12858005F5FF9 /* SetConstructor.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SetConstructor.h; sourceTree = "<group>"; };
</span><span class="cx"> A730B6101250068F009D25B1 /* StrictEvalActivation.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = StrictEvalActivation.h; sourceTree = "<group>"; };
</span><span class="cx"> A730B6111250068F009D25B1 /* StrictEvalActivation.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = StrictEvalActivation.cpp; sourceTree = "<group>"; };
</span><del>- A73781091799EA2E00817533 /* DFGAnalysis.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGAnalysis.h; path = dfg/DFGAnalysis.h; sourceTree = "<group>"; };
</del><span class="cx"> A737810A1799EA2E00817533 /* DFGNaturalLoops.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGNaturalLoops.cpp; path = dfg/DFGNaturalLoops.cpp; sourceTree = "<group>"; };
</span><span class="cx"> A737810B1799EA2E00817533 /* DFGNaturalLoops.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGNaturalLoops.h; path = dfg/DFGNaturalLoops.h; sourceTree = "<group>"; };
</span><span class="cx"> A7386551118697B400540279 /* SpecializedThunkJIT.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SpecializedThunkJIT.h; sourceTree = "<group>"; };
</span><span class="lines">@@ -5683,7 +5675,6 @@
</span><span class="cx"> 0F18D3CE1B55A6E0002C5C9F /* DFGAdaptiveStructureWatchpoint.h */,
</span><span class="cx"> 0F66E16814DF3F1300B7B2E4 /* DFGAdjacencyList.h */,
</span><span class="cx"> 0FB4B51916B62772003F696B /* DFGAllocator.h */,
</span><del>- A73781091799EA2E00817533 /* DFGAnalysis.h */,
</del><span class="cx"> 0F1E3A431534CBAD000F9456 /* DFGArgumentPosition.h */,
</span><span class="cx"> 0F2DD80C1AB3D8BE00BBB8E8 /* DFGArgumentsEliminationPhase.cpp */,
</span><span class="cx"> 0F2DD80D1AB3D8BE00BBB8E8 /* DFGArgumentsEliminationPhase.h */,
</span><span class="lines">@@ -5769,7 +5760,6 @@
</span><span class="cx"> 0FF427621591A1C9004CB9FF /* DFGDisassembler.h */,
</span><span class="cx"> 0F5A1271192D9FDF008764A3 /* DFGDoesGC.cpp */,
</span><span class="cx"> 0F5A1272192D9FDF008764A3 /* DFGDoesGC.h */,
</span><del>- 0FD81ACF154FB4EB00983E72 /* DFGDominators.cpp */,
</del><span class="cx"> 0FD81AD0154FB4EB00983E72 /* DFGDominators.h */,
</span><span class="cx"> 0F1E3A441534CBAD000F9456 /* DFGDoubleFormatState.h */,
</span><span class="cx"> 0FD3C82014115CF800FD81CB /* DFGDriver.cpp */,
</span><span class="lines">@@ -5852,8 +5842,6 @@
</span><span class="cx"> 0F8F14321ADF090100ED792C /* DFGMovHintRemovalPhase.h */,
</span><span class="cx"> 0FF2CD591B61A4F8004955A8 /* DFGMultiGetByOffsetData.cpp */,
</span><span class="cx"> 0FF2CD5A1B61A4F8004955A8 /* DFGMultiGetByOffsetData.h */,
</span><del>- 0FC3CCFA19ADA410006AC72A /* DFGNaiveDominators.cpp */,
- 0FC3CCFB19ADA410006AC72A /* DFGNaiveDominators.h */,
</del><span class="cx"> A737810A1799EA2E00817533 /* DFGNaturalLoops.cpp */,
</span><span class="cx"> A737810B1799EA2E00817533 /* DFGNaturalLoops.h */,
</span><span class="cx"> 0FB4B51E16B62772003F696B /* DFGNode.cpp */,
</span><span class="lines">@@ -6675,7 +6663,6 @@
</span><span class="cx"> 0F18D3D01B55A6E0002C5C9F /* DFGAdaptiveStructureWatchpoint.h in Headers */,
</span><span class="cx"> 0F66E16B14DF3F1600B7B2E4 /* DFGAdjacencyList.h in Headers */,
</span><span class="cx"> 0FFB921816D02EB20055A5DB /* DFGAllocator.h in Headers */,
</span><del>- A737810C1799EA2E00817533 /* DFGAnalysis.h in Headers */,
</del><span class="cx"> 0F1E3A461534CBAF000F9456 /* DFGArgumentPosition.h in Headers */,
</span><span class="cx"> 0F2DD8121AB3D8BE00BBB8E8 /* DFGArgumentsEliminationPhase.h in Headers */,
</span><span class="cx"> 0F2DD8141AB3D8BE00BBB8E8 /* DFGArgumentsUtilities.h in Headers */,
</span><span class="lines">@@ -6778,7 +6765,6 @@
</span><span class="cx"> 0FEC85141BDACDAC0080FF74 /* B3ControlValue.h in Headers */,
</span><span class="cx"> 0F8F14361ADF090100ED792C /* DFGMovHintRemovalPhase.h in Headers */,
</span><span class="cx"> 0FF2CD5C1B61A4F8004955A8 /* DFGMultiGetByOffsetData.h in Headers */,
</span><del>- 0FC3CD0219ADA411006AC72A /* DFGNaiveDominators.h in Headers */,
</del><span class="cx"> A737810E1799EA2E00817533 /* DFGNaturalLoops.h in Headers */,
</span><span class="cx"> 86ECA3EA132DEF1C002B2AD7 /* DFGNode.h in Headers */,
</span><span class="cx"> 0FFB921B16D02F010055A5DB /* DFGNodeAllocator.h in Headers */,
</span><span class="lines">@@ -8241,7 +8227,6 @@
</span><span class="cx"> C2981FD817BAEE4B00A3BC98 /* DFGDesiredWeakReferences.cpp in Sources */,
</span><span class="cx"> 0FF427641591A1CC004CB9FF /* DFGDisassembler.cpp in Sources */,
</span><span class="cx"> 0F5A1273192D9FDF008764A3 /* DFGDoesGC.cpp in Sources */,
</span><del>- 0FD81AD2154FB4EE00983E72 /* DFGDominators.cpp in Sources */,
</del><span class="cx"> 0FD3C82614115D4000FD81CB /* DFGDriver.cpp in Sources */,
</span><span class="cx"> 0FF0F19E16B72A0B005DF95B /* DFGEdge.cpp in Sources */,
</span><span class="cx"> 0F8F14331ADF090100ED792C /* DFGEpoch.cpp in Sources */,
</span><span class="lines">@@ -8280,7 +8265,6 @@
</span><span class="cx"> 0F2BDC4D1522818600CD8910 /* DFGMinifiedNode.cpp in Sources */,
</span><span class="cx"> 0F8F14351ADF090100ED792C /* DFGMovHintRemovalPhase.cpp in Sources */,
</span><span class="cx"> 0FF2CD5B1B61A4F8004955A8 /* DFGMultiGetByOffsetData.cpp in Sources */,
</span><del>- 0FC3CD0119ADA411006AC72A /* DFGNaiveDominators.cpp in Sources */,
</del><span class="cx"> A737810D1799EA2E00817533 /* DFGNaturalLoops.cpp in Sources */,
</span><span class="cx"> 0FF0F19C16B72A03005DF95B /* DFGNode.cpp in Sources */,
</span><span class="cx"> 0FA581BA150E952C00B9A2D9 /* DFGNodeFlags.cpp in Sources */,
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGAnalysish"></a>
<div class="delfile"><h4>Deleted: trunk/Source/JavaScriptCore/dfg/DFGAnalysis.h (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGAnalysis.h 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/JavaScriptCore/dfg/DFGAnalysis.h 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -1,81 +0,0 @@
</span><del>-/*
- * Copyright (C) 2013, 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 DFGAnalysis_h
-#define DFGAnalysis_h
-
-#if ENABLE(DFG_JIT)
-
-namespace JSC { namespace DFG {
-
-class Graph;
-
-// Use this as a mixin for DFG analyses. The analysis itself implements a public
-// compute(Graph&) method. Clients call computeIfNecessary() when they want
-// results.
-
-template<typename T>
-class Analysis {
-public:
- Analysis()
- : m_valid(false)
- {
- }
-
- void invalidate()
- {
- m_valid = false;
- }
-
- void computeIfNecessary(Graph& graph)
- {
- if (m_valid)
- return;
- // It's best to run dependent analyses from this method.
- static_cast<T*>(this)->computeDependencies(graph);
- // Set to true early, since the analysis may choose to call its own methods in
- // compute() and it may want to ASSERT() validity in those methods.
- m_valid = true;
- static_cast<T*>(this)->compute(graph);
- }
-
- bool isValid() const { return m_valid; }
-
- // 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&) { }
-
-private:
- bool m_valid;
-};
-
-} } // namespace JSC::DFG
-
-#endif // ENABLE(DFG_JIT)
-
-#endif // DFGAnalysis_h
-
</del></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGCFGh"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/dfg/DFGCFG.h (0 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGCFG.h (rev 0)
+++ trunk/Source/JavaScriptCore/dfg/DFGCFG.h 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -0,0 +1,78 @@
</span><ins>+/*
+ * Copyright (C) 2015 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 DFGCFG_h
+#define DFGCFG_h
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGBasicBlock.h"
+#include "DFGBlockMapInlines.h"
+#include "DFGBlockSet.h"
+#include "DFGGraph.h"
+
+namespace JSC { namespace DFG {
+
+class CFG {
+public:
+ typedef BasicBlock* Node;
+ typedef BlockSet Set;
+ template<typename T> using Map = BlockMap<T>;
+ typedef BlockList List;
+
+ CFG(Graph& graph)
+ : m_graph(graph)
+ {
+ }
+
+ Node root() { return m_graph.block(0); }
+
+ template<typename T>
+ Map<T> newMap() { return BlockMap<T>(m_graph); }
+
+ DFG::Node::SuccessorsIterable successors(Node node) { return node->successors(); }
+ PredecessorList& predecessors(Node node) { return node->predecessors; }
+
+ unsigned index(Node node) const { return node->index; }
+ Node node(unsigned index) const { return m_graph.block(index); }
+ unsigned numNodes() const { return m_graph.numBlocks(); }
+
+ PointerDump<BasicBlock> dump(Node node) const { return pointerDump(node); }
+
+ void dump(PrintStream& out) const
+ {
+ m_graph.dump(out);
+ }
+
+private:
+ Graph& m_graph;
+};
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGCFG_h
+
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGCSEPhasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGCSEPhase.cpp (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGCSEPhase.cpp 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/JavaScriptCore/dfg/DFGCSEPhase.cpp 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -32,6 +32,7 @@
</span><span class="cx"> #include "DFGBlockMapInlines.h"
</span><span class="cx"> #include "DFGClobberSet.h"
</span><span class="cx"> #include "DFGClobberize.h"
</span><ins>+#include "DFGDominators.h"
</ins><span class="cx"> #include "DFGEdgeUsesStructure.h"
</span><span class="cx"> #include "DFGGraph.h"
</span><span class="cx"> #include "DFGPhase.h"
</span><span class="lines">@@ -390,7 +391,7 @@
</span><span class="cx"> ASSERT(m_graph.m_form == SSA);
</span><span class="cx">
</span><span class="cx"> m_graph.initializeNodeOwners();
</span><del>- m_graph.m_dominators.computeIfNecessary(m_graph);
</del><ins>+ m_graph.ensureDominators();
</ins><span class="cx">
</span><span class="cx"> m_preOrder = m_graph.blocksInPreOrder();
</span><span class="cx">
</span><span class="lines">@@ -484,7 +485,7 @@
</span><span class="cx">
</span><span class="cx"> for (unsigned i = result.iterator->value.size(); i--;) {
</span><span class="cx"> Node* candidate = result.iterator->value[i];
</span><del>- if (m_graph.m_dominators.dominates(candidate->owner, m_block)) {
</del><ins>+ if (m_graph.m_dominators->dominates(candidate->owner, m_block)) {
</ins><span class="cx"> m_node->replaceWith(candidate);
</span><span class="cx"> m_changed = true;
</span><span class="cx"> return;
</span><span class="lines">@@ -573,7 +574,7 @@
</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.strictlyDominates(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">@@ -652,7 +653,7 @@
</span><span class="cx"> if (!result.isNewEntry) {
</span><span class="cx"> for (unsigned i = result.iterator->value.size(); i--;) {
</span><span class="cx"> Node* candidate = result.iterator->value[i];
</span><del>- if (m_graph.m_dominators.dominates(candidate->owner, m_block)) {
</del><ins>+ if (m_graph.m_dominators->dominates(candidate->owner, m_block)) {
</ins><span class="cx"> ASSERT(candidate);
</span><span class="cx"> match->replaceWith(candidate);
</span><span class="cx"> match.setNode(candidate);
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGDisassemblercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGDisassembler.cpp (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGDisassembler.cpp 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/JavaScriptCore/dfg/DFGDisassembler.cpp 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -94,8 +94,8 @@
</span><span class="cx"> dumpHeader(out, linkBuffer);
</span><span class="cx"> append(result, out, previousOrigin);
</span><span class="cx">
</span><del>- m_graph.m_dominators.computeIfNecessary(m_graph);
- m_graph.m_naturalLoops.computeIfNecessary(m_graph);
</del><ins>+ m_graph.ensureDominators();
+ m_graph.ensureNaturalLoops();
</ins><span class="cx">
</span><span class="cx"> const char* prefix = " ";
</span><span class="cx"> const char* disassemblyPrefix = " ";
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGDominatorscpp"></a>
<div class="delfile"><h4>Deleted: trunk/Source/JavaScriptCore/dfg/DFGDominators.cpp (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGDominators.cpp 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/JavaScriptCore/dfg/DFGDominators.cpp 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -1,476 +0,0 @@
</span><del>-/*
- * Copyright (C) 2011, 2014, 2015 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 "DFGDominators.h"
-
-#if ENABLE(DFG_JIT)
-
-#include "DFGBlockMapInlines.h"
-#include "DFGBlockWorklist.h"
-#include "DFGGraph.h"
-#include "DFGNaiveDominators.h"
-#include "JSCInlines.h"
-
-namespace JSC { namespace DFG {
-
-Dominators::Dominators()
-{
-}
-
-Dominators::~Dominators()
-{
-}
-
-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;
- }
- }
-
- void compute()
- {
- computeDepthFirstPreNumbering(); // Step 1.
- computeSemiDominatorsAndImplicitImmediateDominators(); // Steps 2 and 3.
- computeExplicitImmediateDominators(); // Step 4.
- }
-
- BasicBlock* immediateDominator(BasicBlock* block)
- {
- return m_data[block].dom;
- }
-
-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.node;
- 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());
-
- 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;
- }
- }
- }
-
- 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();
- }
- }
-
- 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;
- }
- }
-
- 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;
-};
-
-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;
-};
-
-} // anonymous namespace
-
-void Dominators::compute(Graph& graph)
-{
- LengauerTarjan lengauerTarjan(graph);
- lengauerTarjan.compute();
-
- 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--;) {
- BasicBlock* block = graph.block(blockIndex);
- if (!block)
- continue;
-
- 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), VisitOrder::Pre));
- while (!worklist.isEmpty()) {
- BlockWithOrder item = worklist.takeLast();
- switch (item.order) {
- case VisitOrder::Pre:
- m_data[item.node].preNumber = nextPreNumber++;
- worklist.append(BlockWithOrder(item.node, VisitOrder::Post));
- for (BasicBlock* kid : m_data[item.node].idomKids)
- worklist.append(BlockWithOrder(kid, VisitOrder::Pre));
- break;
- case VisitOrder::Post:
- m_data[item.node].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)
- continue;
- 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");
- }
- }
-
- context.handleErrors();
- }
-}
-
-BlockSet Dominators::strictDominatorsOf(BasicBlock* to) const
-{
- BlockSet result;
- forAllStrictDominatorsOf(to, BlockAdder(result));
- return result;
-}
-
-BlockSet Dominators::dominatorsOf(BasicBlock* to) const
-{
- BlockSet result;
- forAllDominatorsOf(to, BlockAdder(result));
- return result;
-}
-
-BlockSet Dominators::blocksStrictlyDominatedBy(BasicBlock* from) const
-{
- BlockSet result;
- forAllBlocksStrictlyDominatedBy(from, BlockAdder(result));
- return result;
-}
-
-BlockSet Dominators::blocksDominatedBy(BasicBlock* from) const
-{
- BlockSet result;
- forAllBlocksDominatedBy(from, BlockAdder(result));
- return result;
-}
-
-BlockSet Dominators::dominanceFrontierOf(BasicBlock* from) const
-{
- BlockSet result;
- forAllBlocksInDominanceFrontierOfImpl(from, BlockAdder(result));
- return result;
-}
-
-BlockSet Dominators::iteratedDominanceFrontierOf(const BlockList& from) const
-{
- BlockSet result;
- forAllBlocksInIteratedDominanceFrontierOfImpl(from, BlockAdder(result));
- return result;
-}
-
-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");
- }
-}
-
-} } // namespace JSC::DFG
-
-#endif // ENABLE(DFG_JIT)
-
</del></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGDominatorsh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGDominators.h (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGDominators.h 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/JavaScriptCore/dfg/DFGDominators.h 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -28,190 +28,26 @@
</span><span class="cx">
</span><span class="cx"> #if ENABLE(DFG_JIT)
</span><span class="cx">
</span><del>-#include "DFGAnalysis.h"
</del><span class="cx"> #include "DFGBasicBlock.h"
</span><span class="cx"> #include "DFGBlockMap.h"
</span><span class="cx"> #include "DFGBlockSet.h"
</span><ins>+#include "DFGCFG.h"
</ins><span class="cx"> #include "DFGCommon.h"
</span><ins>+#include "DFGGraph.h"
+#include <wtf/Dominators.h>
+#include <wtf/FastMalloc.h>
+#include <wtf/Noncopyable.h>
</ins><span class="cx">
</span><span class="cx"> namespace JSC { namespace DFG {
</span><span class="cx">
</span><del>-class Graph;
-
-class Dominators : public Analysis<Dominators> {
</del><ins>+class Dominators : public WTF::Dominators<CFG> {
+ WTF_MAKE_NONCOPYABLE(Dominators);
+ WTF_MAKE_FAST_ALLOCATED;
</ins><span class="cx"> public:
</span><del>- Dominators();
- ~Dominators();
-
- void compute(Graph&);
-
- bool strictlyDominates(BasicBlock* from, BasicBlock* to) const
</del><ins>+ Dominators(Graph& graph)
+ : WTF::Dominators<CFG>(*graph.m_cfg, validationEnabled())
</ins><span class="cx"> {
</span><del>- ASSERT(isValid());
- return m_data[to].preNumber > m_data[from].preNumber
- && m_data[to].postNumber < m_data[from].postNumber;
</del><span class="cx"> }
</span><del>-
- bool dominates(BasicBlock* from, BasicBlock* to) const
- {
- return from == to || strictlyDominates(from, to);
- }
-
- BasicBlock* immediateDominatorOf(BasicBlock* block) const
- {
- return m_data[block].idomParent;
- }
-
- template<typename Functor>
- void forAllStrictDominatorsOf(BasicBlock* to, const Functor& functor) const
- {
- for (BasicBlock* block = m_data[to].idomParent; block; block = m_data[block].idomParent)
- functor(block);
- }
-
- template<typename Functor>
- void forAllDominatorsOf(BasicBlock* to, const Functor& functor) const
- {
- for (BasicBlock* block = to; block; block = m_data[block].idomParent)
- functor(block);
- }
-
- template<typename Functor>
- void forAllBlocksStrictlyDominatedBy(BasicBlock* from, const Functor& functor) const
- {
- Vector<BasicBlock*, 16> worklist;
- worklist.appendVector(m_data[from].idomKids);
- while (!worklist.isEmpty()) {
- BasicBlock* block = worklist.takeLast();
- functor(block);
- worklist.appendVector(m_data[block].idomKids);
- }
- }
-
- template<typename Functor>
- void forAllBlocksDominatedBy(BasicBlock* from, const Functor& functor) const
- {
- Vector<BasicBlock*, 16> worklist;
- worklist.append(from);
- while (!worklist.isEmpty()) {
- BasicBlock* block = worklist.takeLast();
- functor(block);
- worklist.appendVector(m_data[block].idomKids);
- }
- }
-
- BlockSet strictDominatorsOf(BasicBlock* to) const;
- BlockSet dominatorsOf(BasicBlock* to) const;
- BlockSet blocksStrictlyDominatedBy(BasicBlock* from) const;
- BlockSet blocksDominatedBy(BasicBlock* from) const;
-
- template<typename Functor>
- void forAllBlocksInDominanceFrontierOf(
- BasicBlock* from, const Functor& functor) const
- {
- BlockSet set;
- forAllBlocksInDominanceFrontierOfImpl(
- from,
- [&] (BasicBlock* block) {
- if (set.add(block))
- functor(block);
- });
- }
-
- BlockSet dominanceFrontierOf(BasicBlock* from) const;
-
- template<typename Functor>
- void forAllBlocksInIteratedDominanceFrontierOf(
- const BlockList& from, const Functor& functor)
- {
- forAllBlocksInPrunedIteratedDominanceFrontierOf(
- from,
- [&] (BasicBlock* block) -> bool {
- functor(block);
- return true;
- });
- }
-
- // This is a close relative of forAllBlocksInIteratedDominanceFrontierOf(), which allows the
- // given functor to return false to indicate that we don't wish to consider the given block.
- // Useful for computing pruned SSA form.
- template<typename Functor>
- void forAllBlocksInPrunedIteratedDominanceFrontierOf(
- const BlockList& from, const Functor& functor)
- {
- BlockSet set;
- forAllBlocksInIteratedDominanceFrontierOfImpl(
- from,
- [&] (BasicBlock* block) -> bool {
- if (!set.add(block))
- return false;
- return functor(block);
- });
- }
-
- BlockSet iteratedDominanceFrontierOf(const BlockList& from) const;
-
- void dump(PrintStream&) const;
-
-private:
- bool naiveDominates(BasicBlock* from, BasicBlock* to) const;
-
- template<typename Functor>
- void forAllBlocksInDominanceFrontierOfImpl(
- BasicBlock* from, const Functor& functor) const
- {
- // Paraphrasing from http://en.wikipedia.org/wiki/Dominator_(graph_theory):
- // "The dominance frontier of a block 'from' is the set of all blocks 'to' such that
- // 'from' dominates an immediate predecessor of 'to', but 'from' does not strictly
- // dominate 'to'."
- //
- // A useful corner case to remember: a block may be in its own dominance frontier if it has
- // a loop edge to itself, since it dominates itself and so it dominates its own immediate
- // predecessor, and a block never strictly dominates itself.
-
- forAllBlocksDominatedBy(
- from,
- [&] (BasicBlock* block) {
- for (unsigned successorIndex = block->numSuccessors(); successorIndex--;) {
- BasicBlock* to = block->successor(successorIndex);
- if (!strictlyDominates(from, to))
- functor(to);
- }
- });
- }
-
- template<typename Functor>
- void forAllBlocksInIteratedDominanceFrontierOfImpl(
- const BlockList& from, const Functor& functor) const
- {
- BlockList worklist = from;
- while (!worklist.isEmpty()) {
- BasicBlock* block = worklist.takeLast();
- forAllBlocksInDominanceFrontierOfImpl(
- block,
- [&] (BasicBlock* otherBlock) {
- if (functor(otherBlock))
- worklist.append(otherBlock);
- });
- }
- }
-
- struct BlockData {
- BlockData()
- : idomParent(nullptr)
- , preNumber(UINT_MAX)
- , postNumber(UINT_MAX)
- {
- }
-
- Vector<BasicBlock*> idomKids;
- BasicBlock* idomParent;
-
- unsigned preNumber;
- unsigned postNumber;
- };
-
- BlockMap<BlockData> m_data;
</del><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> } } // namespace JSC::DFG
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGEdgeDominatesh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGEdgeDominates.h (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGEdgeDominates.h 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/JavaScriptCore/dfg/DFGEdgeDominates.h 2015-11-02 00:48:03 UTC (rev 191870)
</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 "DFGDominators.h"
</ins><span class="cx"> #include "DFGGraph.h"
</span><span class="cx">
</span><span class="cx"> namespace JSC { namespace DFG {
</span><span class="lines">@@ -45,7 +46,7 @@
</span><span class="cx">
</span><span class="cx"> void operator()(Node*, Edge edge)
</span><span class="cx"> {
</span><del>- bool result = m_graph.m_dominators.dominates(edge.node()->owner, m_block);
</del><ins>+ bool result = m_graph.m_dominators->dominates(edge.node()->owner, m_block);
</ins><span class="cx"> if (verbose) {
</span><span class="cx"> dataLog(
</span><span class="cx"> "Checking if ", edge, " in ", *edge.node()->owner,
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGGraphcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGGraph.cpp (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGGraph.cpp 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/JavaScriptCore/dfg/DFGGraph.cpp 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -35,8 +35,12 @@
</span><span class="cx"> #include "DFGBlockWorklist.h"
</span><span class="cx"> #include "DFGClobberSet.h"
</span><span class="cx"> #include "DFGClobbersExitState.h"
</span><ins>+#include "DFGCFG.h"
+#include "DFGDominators.h"
</ins><span class="cx"> #include "DFGJITCode.h"
</span><span class="cx"> #include "DFGMayExit.h"
</span><ins>+#include "DFGNaturalLoops.h"
+#include "DFGPrePostNumbering.h"
</ins><span class="cx"> #include "DFGVariableAccessDataDump.h"
</span><span class="cx"> #include "FullBytecodeLiveness.h"
</span><span class="cx"> #include "FunctionExecutableDump.h"
</span><span class="lines">@@ -64,6 +68,7 @@
</span><span class="cx"> , m_codeBlock(m_plan.codeBlock)
</span><span class="cx"> , m_profiledBlock(m_codeBlock->alternative())
</span><span class="cx"> , m_allocator(longLivedState.m_allocator)
</span><ins>+ , m_cfg(std::make_unique<CFG>(*this))
</ins><span class="cx"> , m_nextMachineLocal(0)
</span><span class="cx"> , m_fixpointState(BeforeFixpoint)
</span><span class="cx"> , m_structureRegistrationState(HaveNotStartedRegistering)
</span><span class="lines">@@ -401,22 +406,22 @@
</span><span class="cx"> if (block->terminal()) {
</span><span class="cx"> for (BasicBlock* successor : block->successors()) {
</span><span class="cx"> out.print(" ", *successor);
</span><del>- if (m_prePostNumbering.isValid())
- out.print(" (", m_prePostNumbering.edgeKind(block, successor), ")");
</del><ins>+ if (m_prePostNumbering)
+ out.print(" (", m_prePostNumbering->edgeKind(block, successor), ")");
</ins><span class="cx"> }
</span><span class="cx"> } else
</span><span class="cx"> out.print(" <invalid>");
</span><span class="cx"> out.print("\n");
</span><del>- if (m_dominators.isValid() && terminalsAreValid()) {
- out.print(prefix, " Dominated by: ", m_dominators.dominatorsOf(block), "\n");
- out.print(prefix, " Dominates: ", m_dominators.blocksDominatedBy(block), "\n");
- out.print(prefix, " Dominance Frontier: ", m_dominators.dominanceFrontierOf(block), "\n");
- out.print(prefix, " Iterated Dominance Frontier: ", m_dominators.iteratedDominanceFrontierOf(BlockList(1, block)), "\n");
</del><ins>+ if (m_dominators && terminalsAreValid()) {
+ out.print(prefix, " Dominated by: ", m_dominators->dominatorsOf(block), "\n");
+ out.print(prefix, " Dominates: ", m_dominators->blocksDominatedBy(block), "\n");
+ out.print(prefix, " Dominance Frontier: ", m_dominators->dominanceFrontierOf(block), "\n");
+ out.print(prefix, " Iterated Dominance Frontier: ", m_dominators->iteratedDominanceFrontierOf(BlockList(1, block)), "\n");
</ins><span class="cx"> }
</span><del>- if (m_prePostNumbering.isValid())
- out.print(prefix, " Pre/Post Numbering: ", m_prePostNumbering.preNumber(block), "/", m_prePostNumbering.postNumber(block), "\n");
- if (m_naturalLoops.isValid()) {
- if (const NaturalLoop* loop = m_naturalLoops.headerOf(block)) {
</del><ins>+ if (m_prePostNumbering)
+ out.print(prefix, " Pre/Post Numbering: ", m_prePostNumbering->preNumber(block), "/", m_prePostNumbering->postNumber(block), "\n");
+ if (m_naturalLoops) {
+ if (const NaturalLoop* loop = m_naturalLoops->headerOf(block)) {
</ins><span class="cx"> out.print(prefix, " Loop header, contains:");
</span><span class="cx"> Vector<BlockIndex> sortedBlockList;
</span><span class="cx"> for (unsigned i = 0; i < loop->size(); ++i)
</span><span class="lines">@@ -428,7 +433,7 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> Vector<const NaturalLoop*> containingLoops =
</span><del>- m_naturalLoops.loopsOf(block);
</del><ins>+ m_naturalLoops->loopsOf(block);
</ins><span class="cx"> if (!containingLoops.isEmpty()) {
</span><span class="cx"> out.print(prefix, " Containing loop headers:");
</span><span class="cx"> for (unsigned i = 0; i < containingLoops.size(); ++i)
</span><span class="lines">@@ -746,9 +751,9 @@
</span><span class="cx">
</span><span class="cx"> void Graph::invalidateCFG()
</span><span class="cx"> {
</span><del>- m_dominators.invalidate();
- m_naturalLoops.invalidate();
- m_prePostNumbering.invalidate();
</del><ins>+ m_dominators = nullptr;
+ m_naturalLoops = nullptr;
+ m_prePostNumbering = nullptr;
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void Graph::substituteGetLocal(BasicBlock& block, unsigned startIndexInBlock, VariableAccessData* variableAccessData, Node* newGetLocal)
</span><span class="lines">@@ -1410,6 +1415,25 @@
</span><span class="cx"> crash(*this, toCString("While handling block ", pointerDump(block), "\n\n"), file, line, function, assertion);
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+void Graph::ensureDominators()
+{
+ if (!m_dominators)
+ m_dominators = std::make_unique<Dominators>(*this);
+}
+
+void Graph::ensurePrePostNumbering()
+{
+ if (!m_prePostNumbering)
+ m_prePostNumbering = std::make_unique<PrePostNumbering>(*this);
+}
+
+void Graph::ensureNaturalLoops()
+{
+ ensureDominators();
+ if (!m_naturalLoops)
+ m_naturalLoops = std::make_unique<NaturalLoops>(*this);
+}
+
</ins><span class="cx"> ValueProfile* Graph::valueProfileFor(Node* node)
</span><span class="cx"> {
</span><span class="cx"> if (!node)
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGGraphh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGGraph.h (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGGraph.h 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/JavaScriptCore/dfg/DFGGraph.h 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -33,14 +33,11 @@
</span><span class="cx"> #include "CodeBlock.h"
</span><span class="cx"> #include "DFGArgumentPosition.h"
</span><span class="cx"> #include "DFGBasicBlock.h"
</span><del>-#include "DFGDominators.h"
</del><span class="cx"> #include "DFGFrozenValue.h"
</span><span class="cx"> #include "DFGLongLivedState.h"
</span><del>-#include "DFGNaturalLoops.h"
</del><span class="cx"> #include "DFGNode.h"
</span><span class="cx"> #include "DFGNodeAllocator.h"
</span><span class="cx"> #include "DFGPlan.h"
</span><del>-#include "DFGPrePostNumbering.h"
</del><span class="cx"> #include "DFGPropertyTypeKey.h"
</span><span class="cx"> #include "DFGScannable.h"
</span><span class="cx"> #include "FullBytecodeLiveness.h"
</span><span class="lines">@@ -59,6 +56,11 @@
</span><span class="cx">
</span><span class="cx"> namespace DFG {
</span><span class="cx">
</span><ins>+class CFG;
+class Dominators;
+class NaturalLoops;
+class PrePostNumbering;
+
</ins><span class="cx"> #define DFG_NODE_DO_TO_CHILDREN(graph, node, thingToDo) do { \
</span><span class="cx"> Node* _node = (node); \
</span><span class="cx"> if (_node->flags() & NodeHasVarArgs) { \
</span><span class="lines">@@ -820,6 +822,10 @@
</span><span class="cx">
</span><span class="cx"> bool hasDebuggerEnabled() const { return m_hasDebuggerEnabled; }
</span><span class="cx">
</span><ins>+ void ensureDominators();
+ void ensurePrePostNumbering();
+ void ensureNaturalLoops();
+
</ins><span class="cx"> VM& m_vm;
</span><span class="cx"> Plan& m_plan;
</span><span class="cx"> CodeBlock* m_codeBlock;
</span><span class="lines">@@ -885,9 +891,10 @@
</span><span class="cx"> HashMap<CodeBlock*, std::unique_ptr<BytecodeKills>> m_bytecodeKills;
</span><span class="cx"> HashSet<std::pair<JSObject*, PropertyOffset>> m_safeToLoad;
</span><span class="cx"> HashMap<PropertyTypeKey, InferredType::Descriptor> m_inferredTypes;
</span><del>- Dominators m_dominators;
- PrePostNumbering m_prePostNumbering;
- NaturalLoops m_naturalLoops;
</del><ins>+ std::unique_ptr<Dominators> m_dominators;
+ std::unique_ptr<PrePostNumbering> m_prePostNumbering;
+ std::unique_ptr<NaturalLoops> m_naturalLoops;
+ std::unique_ptr<CFG> m_cfg;
</ins><span class="cx"> unsigned m_localVars;
</span><span class="cx"> unsigned m_nextMachineLocal;
</span><span class="cx"> unsigned m_parameterSlots;
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGIntegerRangeOptimizationPhasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp 2015-11-02 00:48:03 UTC (rev 191870)
</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 "DFGBlockMapInlines.h"
</span><ins>+#include "DFGBlockSet.h"
</ins><span class="cx"> #include "DFGGraph.h"
</span><span class="cx"> #include "DFGInsertionSet.h"
</span><span class="cx"> #include "DFGPhase.h"
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGLICMPhasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -36,6 +36,7 @@
</span><span class="cx"> #include "DFGEdgeDominates.h"
</span><span class="cx"> #include "DFGGraph.h"
</span><span class="cx"> #include "DFGInsertionSet.h"
</span><ins>+#include "DFGNaturalLoops.h"
</ins><span class="cx"> #include "DFGPhase.h"
</span><span class="cx"> #include "DFGSafeToExecute.h"
</span><span class="cx"> #include "JSCInlines.h"
</span><span class="lines">@@ -71,15 +72,15 @@
</span><span class="cx"> {
</span><span class="cx"> DFG_ASSERT(m_graph, nullptr, m_graph.m_form == SSA);
</span><span class="cx">
</span><del>- m_graph.m_dominators.computeIfNecessary(m_graph);
- m_graph.m_naturalLoops.computeIfNecessary(m_graph);
</del><ins>+ m_graph.ensureDominators();
+ m_graph.ensureNaturalLoops();
</ins><span class="cx">
</span><span class="cx"> if (verbose) {
</span><span class="cx"> dataLog("Graph before LICM:\n");
</span><span class="cx"> m_graph.dump();
</span><span class="cx"> }
</span><span class="cx">
</span><del>- m_data.resize(m_graph.m_naturalLoops.numLoops());
</del><ins>+ m_data.resize(m_graph.m_naturalLoops->numLoops());
</ins><span class="cx">
</span><span class="cx"> // Figure out the set of things each loop writes to, not including blocks that
</span><span class="cx"> // belong to inner loops. We fix this later.
</span><span class="lines">@@ -94,7 +95,7 @@
</span><span class="cx"> if (!block->cfaHasVisited)
</span><span class="cx"> continue;
</span><span class="cx">
</span><del>- const NaturalLoop* loop = m_graph.m_naturalLoops.innerMostLoopOf(block);
</del><ins>+ const NaturalLoop* loop = m_graph.m_naturalLoops->innerMostLoopOf(block);
</ins><span class="cx"> if (!loop)
</span><span class="cx"> continue;
</span><span class="cx"> LoopData& data = m_data[loop->index()];
</span><span class="lines">@@ -114,14 +115,14 @@
</span><span class="cx"> // For each loop:
</span><span class="cx"> // - Identify its pre-header.
</span><span class="cx"> // - Make sure its outer loops know what it clobbers.
</span><del>- for (unsigned loopIndex = m_graph.m_naturalLoops.numLoops(); loopIndex--;) {
- const NaturalLoop& loop = m_graph.m_naturalLoops.loop(loopIndex);
</del><ins>+ for (unsigned loopIndex = m_graph.m_naturalLoops->numLoops(); loopIndex--;) {
+ const NaturalLoop& loop = m_graph.m_naturalLoops->loop(loopIndex);
</ins><span class="cx"> LoopData& data = m_data[loop.index()];
</span><span class="cx">
</span><span class="cx"> for (
</span><del>- const NaturalLoop* outerLoop = m_graph.m_naturalLoops.innerMostOuterLoop(loop);
</del><ins>+ const NaturalLoop* outerLoop = m_graph.m_naturalLoops->innerMostOuterLoop(loop);
</ins><span class="cx"> outerLoop;
</span><del>- outerLoop = m_graph.m_naturalLoops.innerMostOuterLoop(*outerLoop))
</del><ins>+ outerLoop = m_graph.m_naturalLoops->innerMostOuterLoop(*outerLoop))
</ins><span class="cx"> m_data[outerLoop->index()].writes.addAll(data.writes);
</span><span class="cx">
</span><span class="cx"> BasicBlock* header = loop.header();
</span><span class="lines">@@ -135,7 +136,7 @@
</span><span class="cx">
</span><span class="cx"> for (unsigned i = header->predecessors.size(); i--;) {
</span><span class="cx"> BasicBlock* predecessor = header->predecessors[i];
</span><del>- if (m_graph.m_dominators.dominates(header, predecessor))
</del><ins>+ if (m_graph.m_dominators->dominates(header, predecessor))
</ins><span class="cx"> continue;
</span><span class="cx">
</span><span class="cx"> preHeader = predecessor;
</span><span class="lines">@@ -189,7 +190,7 @@
</span><span class="cx"> Vector<const NaturalLoop*> loopStack;
</span><span class="cx"> bool changed = false;
</span><span class="cx"> for (BasicBlock* block : m_graph.blocksInPreOrder()) {
</span><del>- const NaturalLoop* loop = m_graph.m_naturalLoops.innerMostLoopOf(block);
</del><ins>+ const NaturalLoop* loop = m_graph.m_naturalLoops->innerMostLoopOf(block);
</ins><span class="cx"> if (!loop)
</span><span class="cx"> continue;
</span><span class="cx">
</span><span class="lines">@@ -197,7 +198,7 @@
</span><span class="cx"> for (
</span><span class="cx"> const NaturalLoop* current = loop;
</span><span class="cx"> current;
</span><del>- current = m_graph.m_naturalLoops.innerMostOuterLoop(*current))
</del><ins>+ current = m_graph.m_naturalLoops->innerMostOuterLoop(*current))
</ins><span class="cx"> loopStack.append(current);
</span><span class="cx">
</span><span class="cx"> // Remember: the loop stack has the inner-most loop at index 0, so if we want
</span><span class="lines">@@ -333,7 +334,7 @@
</span><span class="cx"> // because most loops are small and most blocks belong to few loops.
</span><span class="cx"> for (unsigned bodyIndex = loop->size(); bodyIndex--;) {
</span><span class="cx"> BasicBlock* subBlock = loop->at(bodyIndex);
</span><del>- const NaturalLoop* subLoop = m_graph.m_naturalLoops.headerOf(subBlock);
</del><ins>+ const NaturalLoop* subLoop = m_graph.m_naturalLoops->headerOf(subBlock);
</ins><span class="cx"> if (!subLoop)
</span><span class="cx"> continue;
</span><span class="cx"> BasicBlock* subPreHeader = m_data[subLoop->index()].preHeader;
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGLoopPreHeaderCreationPhasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGLoopPreHeaderCreationPhase.cpp (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGLoopPreHeaderCreationPhase.cpp 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/JavaScriptCore/dfg/DFGLoopPreHeaderCreationPhase.cpp 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -30,7 +30,9 @@
</span><span class="cx">
</span><span class="cx"> #include "DFGBasicBlockInlines.h"
</span><span class="cx"> #include "DFGBlockInsertionSet.h"
</span><ins>+#include "DFGDominators.h"
</ins><span class="cx"> #include "DFGGraph.h"
</span><ins>+#include "DFGNaturalLoops.h"
</ins><span class="cx"> #include "DFGPhase.h"
</span><span class="cx"> #include "JSCInlines.h"
</span><span class="cx"> #include <wtf/HashMap.h>
</span><span class="lines">@@ -94,7 +96,7 @@
</span><span class="cx">
</span><span class="cx"> for (unsigned predecessorIndex = 0; predecessorIndex < block->predecessors.size(); predecessorIndex++) {
</span><span class="cx"> BasicBlock* predecessor = block->predecessors[predecessorIndex];
</span><del>- if (graph.m_dominators.dominates(block, predecessor))
</del><ins>+ if (graph.m_dominators->dominates(block, predecessor))
</ins><span class="cx"> continue;
</span><span class="cx"> block->predecessors[predecessorIndex--] = block->predecessors.last();
</span><span class="cx"> block->predecessors.removeLast();
</span><span class="lines">@@ -121,16 +123,16 @@
</span><span class="cx">
</span><span class="cx"> bool run()
</span><span class="cx"> {
</span><del>- m_graph.m_dominators.computeIfNecessary(m_graph);
- m_graph.m_naturalLoops.computeIfNecessary(m_graph);
</del><ins>+ m_graph.ensureDominators();
+ m_graph.ensureNaturalLoops();
</ins><span class="cx">
</span><del>- for (unsigned loopIndex = m_graph.m_naturalLoops.numLoops(); loopIndex--;) {
- const NaturalLoop& loop = m_graph.m_naturalLoops.loop(loopIndex);
</del><ins>+ for (unsigned loopIndex = m_graph.m_naturalLoops->numLoops(); loopIndex--;) {
+ const NaturalLoop& loop = m_graph.m_naturalLoops->loop(loopIndex);
</ins><span class="cx"> BasicBlock* existingPreHeader = 0;
</span><span class="cx"> bool needsNewPreHeader = false;
</span><span class="cx"> for (unsigned predecessorIndex = loop.header()->predecessors.size(); predecessorIndex--;) {
</span><span class="cx"> BasicBlock* predecessor = loop.header()->predecessors[predecessorIndex];
</span><del>- if (m_graph.m_dominators.dominates(loop.header(), predecessor))
</del><ins>+ if (m_graph.m_dominators->dominates(loop.header(), predecessor))
</ins><span class="cx"> continue;
</span><span class="cx"> if (!existingPreHeader) {
</span><span class="cx"> existingPreHeader = predecessor;
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGNaiveDominatorscpp"></a>
<div class="delfile"><h4>Deleted: trunk/Source/JavaScriptCore/dfg/DFGNaiveDominators.cpp (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGNaiveDominators.cpp 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/JavaScriptCore/dfg/DFGNaiveDominators.cpp 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -1,135 +0,0 @@
</span><del>-/*
- * 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)
-
</del></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGNaiveDominatorsh"></a>
<div class="delfile"><h4>Deleted: trunk/Source/JavaScriptCore/dfg/DFGNaiveDominators.h (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGNaiveDominators.h 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/JavaScriptCore/dfg/DFGNaiveDominators.h 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -1,71 +0,0 @@
</span><del>-/*
- * 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
</del></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGNaturalLoopscpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGNaturalLoops.cpp (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGNaturalLoops.cpp 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/JavaScriptCore/dfg/DFGNaturalLoops.cpp 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -42,16 +42,10 @@
</span><span class="cx"> out.print("]");
</span><span class="cx"> }
</span><span class="cx">
</span><del>-NaturalLoops::NaturalLoops() { }
-NaturalLoops::~NaturalLoops() { }
-
-void NaturalLoops::computeDependencies(Graph& graph)
</del><ins>+NaturalLoops::NaturalLoops(Graph& graph)
</ins><span class="cx"> {
</span><del>- graph.m_dominators.computeIfNecessary(graph);
-}
</del><ins>+ ASSERT(graph.m_dominators);
</ins><span class="cx">
</span><del>-void NaturalLoops::compute(Graph& graph)
-{
</del><span class="cx"> // Implement the classic dominator-based natural loop finder. The first
</span><span class="cx"> // step is to find all control flow edges A -> B where B dominates A.
</span><span class="cx"> // Then B is a loop header and A is a backward branching block. We will
</span><span class="lines">@@ -64,7 +58,7 @@
</span><span class="cx">
</span><span class="cx"> if (verbose) {
</span><span class="cx"> dataLog("Dominators:\n");
</span><del>- graph.m_dominators.dump(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 class="lines">@@ -76,7 +70,7 @@
</span><span class="cx">
</span><span class="cx"> for (unsigned i = block->numSuccessors(); i--;) {
</span><span class="cx"> BasicBlock* successor = block->successor(i);
</span><del>- if (!graph.m_dominators.dominates(successor, block))
</del><ins>+ if (!graph.m_dominators->dominates(successor, block))
</ins><span class="cx"> continue;
</span><span class="cx"> bool found = false;
</span><span class="cx"> for (unsigned j = m_loops.size(); j--;) {
</span><span class="lines">@@ -199,6 +193,8 @@
</span><span class="cx"> dataLog("Results: ", *this, "\n");
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+NaturalLoops::~NaturalLoops() { }
+
</ins><span class="cx"> Vector<const NaturalLoop*> NaturalLoops::loopsOf(BasicBlock* block) const
</span><span class="cx"> {
</span><span class="cx"> Vector<const NaturalLoop*> result;
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGNaturalLoopsh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGNaturalLoops.h (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGNaturalLoops.h 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/JavaScriptCore/dfg/DFGNaturalLoops.h 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -28,9 +28,11 @@
</span><span class="cx">
</span><span class="cx"> #if ENABLE(DFG_JIT)
</span><span class="cx">
</span><del>-#include "DFGAnalysis.h"
</del><span class="cx"> #include "DFGBasicBlock.h"
</span><span class="cx"> #include "DFGCommon.h"
</span><ins>+#include "DFGDominators.h"
+#include <wtf/FastMalloc.h>
+#include <wtf/Noncopyable.h>
</ins><span class="cx">
</span><span class="cx"> namespace JSC { namespace DFG {
</span><span class="cx">
</span><span class="lines">@@ -88,22 +90,19 @@
</span><span class="cx"> unsigned m_index;
</span><span class="cx"> };
</span><span class="cx">
</span><del>-class NaturalLoops : public Analysis<NaturalLoops> {
</del><ins>+class NaturalLoops {
+ WTF_MAKE_NONCOPYABLE(NaturalLoops);
+ WTF_MAKE_FAST_ALLOCATED;
</ins><span class="cx"> public:
</span><del>- NaturalLoops();
</del><ins>+ NaturalLoops(Graph&);
</ins><span class="cx"> ~NaturalLoops();
</span><span class="cx">
</span><del>- void computeDependencies(Graph&);
- void compute(Graph&);
-
</del><span class="cx"> unsigned numLoops() const
</span><span class="cx"> {
</span><del>- ASSERT(isValid());
</del><span class="cx"> return m_loops.size();
</span><span class="cx"> }
</span><span class="cx"> const NaturalLoop& loop(unsigned i) const
</span><span class="cx"> {
</span><del>- ASSERT(isValid());
</del><span class="cx"> return m_loops[i];
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -111,7 +110,6 @@
</span><span class="cx"> // loop it belongs to.
</span><span class="cx"> const NaturalLoop* headerOf(BasicBlock* block) const
</span><span class="cx"> {
</span><del>- ASSERT(isValid());
</del><span class="cx"> const NaturalLoop* loop = innerMostLoopOf(block);
</span><span class="cx"> if (!loop)
</span><span class="cx"> return 0;
</span><span class="lines">@@ -126,7 +124,6 @@
</span><span class="cx">
</span><span class="cx"> const NaturalLoop* innerMostLoopOf(BasicBlock* block) const
</span><span class="cx"> {
</span><del>- ASSERT(isValid());
</del><span class="cx"> unsigned index = block->innerMostLoopIndices[0];
</span><span class="cx"> if (index == UINT_MAX)
</span><span class="cx"> return 0;
</span><span class="lines">@@ -135,7 +132,6 @@
</span><span class="cx">
</span><span class="cx"> const NaturalLoop* innerMostOuterLoop(const NaturalLoop& loop) const
</span><span class="cx"> {
</span><del>- ASSERT(isValid());
</del><span class="cx"> if (loop.m_outerLoopIndex == UINT_MAX)
</span><span class="cx"> return 0;
</span><span class="cx"> return &m_loops[loop.m_outerLoopIndex];
</span><span class="lines">@@ -143,7 +139,6 @@
</span><span class="cx">
</span><span class="cx"> bool belongsTo(BasicBlock* block, const NaturalLoop& candidateLoop) const
</span><span class="cx"> {
</span><del>- ASSERT(isValid());
</del><span class="cx"> // It's faster to do this test using the loop itself, if it's small.
</span><span class="cx"> if (candidateLoop.size() < 4)
</span><span class="cx"> return candidateLoop.contains(block);
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGNodeh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGNode.h (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGNode.h 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/JavaScriptCore/dfg/DFGNode.h 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -1279,6 +1279,10 @@
</span><span class="cx"> {
</span><span class="cx"> return iterator(m_terminal, m_terminal->numSuccessors());
</span><span class="cx"> }
</span><ins>+
+ size_t size() const { return m_terminal->numSuccessors(); }
+ BasicBlock* at(size_t index) const { return m_terminal->successor(index); }
+ BasicBlock* operator[](size_t index) const { return at(index); }
</ins><span class="cx">
</span><span class="cx"> private:
</span><span class="cx"> Node* m_terminal;
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGOSREntrypointCreationPhasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGOSREntrypointCreationPhase.cpp (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGOSREntrypointCreationPhase.cpp 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/JavaScriptCore/dfg/DFGOSREntrypointCreationPhase.cpp 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -54,7 +54,7 @@
</span><span class="cx"> RELEASE_ASSERT(bytecodeIndex != UINT_MAX);
</span><span class="cx">
</span><span class="cx"> // Needed by createPreHeader().
</span><del>- m_graph.m_dominators.computeIfNecessary(m_graph);
</del><ins>+ m_graph.ensureDominators();
</ins><span class="cx">
</span><span class="cx"> CodeBlock* baseline = m_graph.m_profiledBlock;
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGObjectAllocationSinkingPhasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -727,7 +727,7 @@
</span><span class="cx"> {
</span><span class="cx"> m_graph.computeRefCounts();
</span><span class="cx"> m_graph.initializeNodeOwners();
</span><del>- m_graph.m_dominators.computeIfNecessary(m_graph);
</del><ins>+ m_graph.ensureDominators();
</ins><span class="cx"> performLivenessAnalysis(m_graph);
</span><span class="cx"> performOSRAvailabilityAnalysis(m_graph);
</span><span class="cx"> m_combinedLiveness = CombinedLiveness(m_graph);
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGPlancpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGPlan.cpp (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGPlan.cpp 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/JavaScriptCore/dfg/DFGPlan.cpp 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -344,9 +344,9 @@
</span><span class="cx"> // If we're doing validation, then run some analyses, to give them an opportunity
</span><span class="cx"> // to self-validate. Now is as good a time as any to do this.
</span><span class="cx"> if (validationEnabled()) {
</span><del>- dfg.m_dominators.computeIfNecessary(dfg);
- dfg.m_naturalLoops.computeIfNecessary(dfg);
- dfg.m_prePostNumbering.computeIfNecessary(dfg);
</del><ins>+ dfg.ensureDominators();
+ dfg.ensureNaturalLoops();
+ dfg.ensurePrePostNumbering();
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> switch (mode) {
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGPrePostNumberingcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGPrePostNumbering.cpp (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGPrePostNumbering.cpp 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/JavaScriptCore/dfg/DFGPrePostNumbering.cpp 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -34,10 +34,7 @@
</span><span class="cx">
</span><span class="cx"> namespace JSC { namespace DFG {
</span><span class="cx">
</span><del>-PrePostNumbering::PrePostNumbering() { }
-PrePostNumbering::~PrePostNumbering() { }
-
-void PrePostNumbering::compute(Graph& graph)
</del><ins>+PrePostNumbering::PrePostNumbering(Graph& graph)
</ins><span class="cx"> {
</span><span class="cx"> m_map = BlockMap<Numbering>(graph);
</span><span class="cx">
</span><span class="lines">@@ -60,6 +57,8 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+PrePostNumbering::~PrePostNumbering() { }
+
</ins><span class="cx"> } } // namespace JSC::DFG
</span><span class="cx">
</span><span class="cx"> namespace WTF {
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGPrePostNumberingh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGPrePostNumbering.h (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGPrePostNumbering.h 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/JavaScriptCore/dfg/DFGPrePostNumbering.h 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -28,9 +28,10 @@
</span><span class="cx">
</span><span class="cx"> #if ENABLE(DFG_JIT)
</span><span class="cx">
</span><del>-#include "DFGAnalysis.h"
</del><span class="cx"> #include "DFGBasicBlock.h"
</span><span class="cx"> #include "DFGBlockMap.h"
</span><ins>+#include <wtf/FastMalloc.h>
+#include <wtf/Noncopyable.h>
</ins><span class="cx">
</span><span class="cx"> namespace JSC { namespace DFG {
</span><span class="cx">
</span><span class="lines">@@ -40,13 +41,13 @@
</span><span class="cx"> BackEdge
</span><span class="cx"> };
</span><span class="cx">
</span><del>-class PrePostNumbering : public Analysis<PrePostNumbering> {
</del><ins>+class PrePostNumbering {
+ WTF_MAKE_NONCOPYABLE(PrePostNumbering);
+ WTF_MAKE_FAST_ALLOCATED;
</ins><span class="cx"> public:
</span><del>- PrePostNumbering();
</del><ins>+ PrePostNumbering(Graph&);
</ins><span class="cx"> ~PrePostNumbering();
</span><span class="cx">
</span><del>- void compute(Graph&);
-
</del><span class="cx"> unsigned preNumber(BasicBlock* block) const { return m_map[block].m_preNumber; }
</span><span class="cx"> unsigned postNumber(BasicBlock* block) const { return m_map[block].m_postNumber; }
</span><span class="cx">
</span><span class="lines">@@ -90,7 +91,7 @@
</span><span class="cx"> unsigned m_preNumber;
</span><span class="cx"> unsigned m_postNumber;
</span><span class="cx"> };
</span><del>-
</del><ins>+
</ins><span class="cx"> BlockMap<Numbering> m_map;
</span><span class="cx"> };
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGPutStackSinkingPhasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGPutStackSinkingPhase.cpp (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGPutStackSinkingPhase.cpp 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/JavaScriptCore/dfg/DFGPutStackSinkingPhase.cpp 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -76,7 +76,7 @@
</span><span class="cx"> m_graph.dump();
</span><span class="cx"> }
</span><span class="cx">
</span><del>- m_graph.m_dominators.computeIfNecessary(m_graph);
</del><ins>+ m_graph.ensureDominators();
</ins><span class="cx">
</span><span class="cx"> SSACalculator ssaCalculator(m_graph);
</span><span class="cx"> InsertionSet insertionSet(m_graph);
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGSSACalculatorcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGSSACalculator.cpp (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGSSACalculator.cpp 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/JavaScriptCore/dfg/DFGSSACalculator.cpp 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -95,12 +95,12 @@
</span><span class="cx">
</span><span class="cx"> SSACalculator::Def* SSACalculator::nonLocalReachingDef(BasicBlock* block, Variable* variable)
</span><span class="cx"> {
</span><del>- return reachingDefAtTail(m_graph.m_dominators.immediateDominatorOf(block), variable);
</del><ins>+ return reachingDefAtTail(m_graph.m_dominators->immediateDominatorOf(block), variable);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> SSACalculator::Def* SSACalculator::reachingDefAtTail(BasicBlock* block, Variable* variable)
</span><span class="cx"> {
</span><del>- for (; block; block = m_graph.m_dominators.immediateDominatorOf(block)) {
</del><ins>+ for (; block; block = m_graph.m_dominators->immediateDominatorOf(block)) {
</ins><span class="cx"> if (Def* def = m_data[block].m_defs.get(variable))
</span><span class="cx"> return def;
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGSSACalculatorh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGSSACalculator.h (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGSSACalculator.h 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/JavaScriptCore/dfg/DFGSSACalculator.h 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -176,10 +176,10 @@
</span><span class="cx"> template<typename PhiInsertionFunctor>
</span><span class="cx"> void computePhis(const PhiInsertionFunctor& functor)
</span><span class="cx"> {
</span><del>- DFG_ASSERT(m_graph, nullptr, m_graph.m_dominators.isValid());
</del><ins>+ DFG_ASSERT(m_graph, nullptr, m_graph.m_dominators);
</ins><span class="cx">
</span><span class="cx"> for (Variable& variable : m_variables) {
</span><del>- m_graph.m_dominators.forAllBlocksInPrunedIteratedDominanceFrontierOf(
</del><ins>+ m_graph.m_dominators->forAllBlocksInPrunedIteratedDominanceFrontierOf(
</ins><span class="cx"> variable.m_blocksWithDefs,
</span><span class="cx"> [&] (BasicBlock* block) -> bool {
</span><span class="cx"> Node* phiNode = functor(&variable, block);
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGSSAConversionPhasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGSSAConversionPhase.cpp (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGSSAConversionPhase.cpp 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/JavaScriptCore/dfg/DFGSSAConversionPhase.cpp 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -54,7 +54,7 @@
</span><span class="cx"> RELEASE_ASSERT(m_graph.m_form == ThreadedCPS);
</span><span class="cx">
</span><span class="cx"> m_graph.clearReplacements();
</span><del>- m_graph.m_dominators.computeIfNecessary(m_graph);
</del><ins>+ m_graph.ensureDominators();
</ins><span class="cx">
</span><span class="cx"> if (verbose) {
</span><span class="cx"> dataLog("Graph before SSA transformation:\n");
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGStaticExecutionCountEstimationPhasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGStaticExecutionCountEstimationPhase.cpp (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGStaticExecutionCountEstimationPhase.cpp 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/JavaScriptCore/dfg/DFGStaticExecutionCountEstimationPhase.cpp 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -30,6 +30,7 @@
</span><span class="cx">
</span><span class="cx"> #include "DFGBasicBlockInlines.h"
</span><span class="cx"> #include "DFGGraph.h"
</span><ins>+#include "DFGNaturalLoops.h"
</ins><span class="cx"> #include "DFGPhase.h"
</span><span class="cx"> #include "JSCInlines.h"
</span><span class="cx">
</span><span class="lines">@@ -44,7 +45,7 @@
</span><span class="cx">
</span><span class="cx"> bool run()
</span><span class="cx"> {
</span><del>- m_graph.m_naturalLoops.computeIfNecessary(m_graph);
</del><ins>+ m_graph.ensureNaturalLoops();
</ins><span class="cx">
</span><span class="cx"> // Estimate basic block execution counts based on loop depth.
</span><span class="cx"> for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
</span><span class="lines">@@ -52,7 +53,7 @@
</span><span class="cx"> if (!block)
</span><span class="cx"> continue;
</span><span class="cx">
</span><del>- block->executionCount = pow(10, m_graph.m_naturalLoops.loopDepth(block));
</del><ins>+ block->executionCount = pow(10, m_graph.m_naturalLoops->loopDepth(block));
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> // Estimate branch weights based on execution counts. This isn't quite correct. It'll
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGTierUpCheckInjectionPhasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGTierUpCheckInjectionPhase.cpp (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGTierUpCheckInjectionPhase.cpp 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/JavaScriptCore/dfg/DFGTierUpCheckInjectionPhase.cpp 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -30,6 +30,7 @@
</span><span class="cx">
</span><span class="cx"> #include "DFGGraph.h"
</span><span class="cx"> #include "DFGInsertionSet.h"
</span><ins>+#include "DFGNaturalLoops.h"
</ins><span class="cx"> #include "DFGPhase.h"
</span><span class="cx"> #include "FTLCapabilities.h"
</span><span class="cx"> #include "JSCInlines.h"
</span><span class="lines">@@ -66,8 +67,8 @@
</span><span class="cx">
</span><span class="cx"> // First we find all the loops that contain a LoopHint for which we cannot OSR enter.
</span><span class="cx"> // We use that information to decide if we need CheckTierUpAndOSREnter or CheckTierUpWithNestedTriggerAndOSREnter.
</span><del>- NaturalLoops& naturalLoops = m_graph.m_naturalLoops;
- naturalLoops.computeIfNecessary(m_graph);
</del><ins>+ m_graph.ensureNaturalLoops();
+ NaturalLoops& naturalLoops = *m_graph.m_naturalLoops;
</ins><span class="cx">
</span><span class="cx"> HashSet<const NaturalLoop*> loopsContainingLoopHintWithoutOSREnter = findLoopsContainingLoopHintWithoutOSREnter(naturalLoops, level);
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreftlFTLLinkcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ftl/FTLLink.cpp (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ftl/FTLLink.cpp 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/JavaScriptCore/ftl/FTLLink.cpp 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -99,8 +99,8 @@
</span><span class="cx"> Profiler::OriginStack(),
</span><span class="cx"> toCString("Generated FTL JIT code for ", CodeBlockWithJITType(codeBlock, JITCode::FTLJIT), ", instruction count = ", graph.m_codeBlock->instructionCount(), ":\n"));
</span><span class="cx">
</span><del>- graph.m_dominators.computeIfNecessary(graph);
- graph.m_naturalLoops.computeIfNecessary(graph);
</del><ins>+ graph.ensureDominators();
+ graph.ensureNaturalLoops();
</ins><span class="cx">
</span><span class="cx"> const char* prefix = " ";
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreftlFTLLowerDFGToLLVMcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -30,6 +30,7 @@
</span><span class="cx">
</span><span class="cx"> #include "CodeBlockWithJITType.h"
</span><span class="cx"> #include "DFGAbstractInterpreterInlines.h"
</span><ins>+#include "DFGDominators.h"
</ins><span class="cx"> #include "DFGInPlaceAbstractState.h"
</span><span class="cx"> #include "DFGOSRAvailabilityAnalysisPhase.h"
</span><span class="cx"> #include "DFGOSRExitFuzz.h"
</span><span class="lines">@@ -121,7 +122,7 @@
</span><span class="cx"> } else
</span><span class="cx"> name = "jsBody";
</span><span class="cx">
</span><del>- m_graph.m_dominators.computeIfNecessary(m_graph);
</del><ins>+ m_graph.ensureDominators();
</ins><span class="cx">
</span><span class="cx"> m_ftlState.module =
</span><span class="cx"> moduleCreateWithNameInContext(name.data(), m_ftlState.context);
</span><span class="lines">@@ -382,7 +383,7 @@
</span><span class="cx"> BasicBlock* target = m_graph.block(blockIndex);
</span><span class="cx"> if (!target)
</span><span class="cx"> continue;
</span><del>- if (m_graph.m_dominators.dominates(m_highBlock, target)) {
</del><ins>+ if (m_graph.m_dominators->dominates(m_highBlock, target)) {
</ins><span class="cx"> if (verboseCompilationEnabled())
</span><span class="cx"> dataLog("Block ", *target, " will bail also.\n");
</span><span class="cx"> target->cfaHasVisited = false;
</span><span class="lines">@@ -9156,7 +9157,7 @@
</span><span class="cx"> {
</span><span class="cx"> if (!value)
</span><span class="cx"> return false;
</span><del>- if (!m_graph.m_dominators.dominates(value.block(), m_highBlock))
</del><ins>+ if (!m_graph.m_dominators->dominates(value.block(), m_highBlock))
</ins><span class="cx"> return false;
</span><span class="cx"> return true;
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourceWTFChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/ChangeLog (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/ChangeLog 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/WTF/ChangeLog 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -1,3 +1,75 @@
</span><ins>+2015-11-01 Filip Pizlo <fpizlo@apple.com>
+
+ Dominators should be factored out of the DFG
+ https://bugs.webkit.org/show_bug.cgi?id=150764
+
+ Reviewed by Geoffrey Garen.
+
+ This takes what used to be DFGDominators.h/DFGDominators.cpp and turns it into a generic
+ algorithm that can take any abstract graph. The idea is that you create Dominators<CFG> and
+ pass it a CFG object, which defines the types of graph nodes and methods for getting
+ successors, predecessors, etc. The DFG now defines a class called CFG, which is a wrapper for
+ DFG::Graph that conforms to the thing that wtf/Dominators.h expects.
+
+ When doing things to graphs, it's common to refer to the things in the graph as "nodes".
+ Because I intend to reuse the CFG abstraction with many graph algorithms, that abstraction uses
+ the term "node" to refer to a DFG basic block. But in Dominators, the method and variable names
+ still use "block". This is because although Dominators are applicable to any kind of directed
+ graph, it's super unlikely that we will ever use them for anything but compilers. Indeed, the
+ only reason why I'm factoring them out of the DFG is so that I can use them with B3 and Air.
+
+ This has the nice side effect that a user of WTF::Dominators<JSC::DFG::CFG> will see familiar
+ terminology like "blocksStrictlyDominatedBy(...)" instead of "nodesStrictlyDominatedBy(...)",
+ which would be super confusing.
+
+ Overall, wtf/Dominators.h is a combination of what used to be in DFGDominators.h,
+ DFGDominators.cpp, DFGNaiveDominators.h, and DFGNaiveDominators.cpp. I only changed code when I
+ had to in order to make it generic.
+
+ * WTF.xcodeproj/project.pbxproj:
+ * wtf/CMakeLists.txt:
+ * wtf/Dominators.h: Added.
+ (WTF::Dominators::Dominators):
+ (WTF::Dominators::compute):
+ (WTF::Dominators::strictlyDominates):
+ (WTF::Dominators::dominates):
+ (WTF::Dominators::immediateDominatorOf):
+ (WTF::Dominators::forAllStrictDominatorsOf):
+ (WTF::Dominators::forAllDominatorsOf):
+ (WTF::Dominators::forAllBlocksStrictlyDominatedBy):
+ (WTF::Dominators::forAllBlocksDominatedBy):
+ (WTF::Dominators::strictDominatorsOf):
+ (WTF::Dominators::dominatorsOf):
+ (WTF::Dominators::blocksStrictlyDominatedBy):
+ (WTF::Dominators::blocksDominatedBy):
+ (WTF::Dominators::forAllBlocksInDominanceFrontierOf):
+ (WTF::Dominators::dominanceFrontierOf):
+ (WTF::Dominators::forAllBlocksInIteratedDominanceFrontierOf):
+ (WTF::Dominators::forAllBlocksInPrunedIteratedDominanceFrontierOf):
+ (WTF::Dominators::iteratedDominanceFrontierOf):
+ (WTF::Dominators::dump):
+ (WTF::Dominators::LengauerTarjan::LengauerTarjan):
+ (WTF::Dominators::LengauerTarjan::compute):
+ (WTF::Dominators::LengauerTarjan::immediateDominator):
+ (WTF::Dominators::LengauerTarjan::computeDepthFirstPreNumbering):
+ (WTF::Dominators::LengauerTarjan::computeSemiDominatorsAndImplicitImmediateDominators):
+ (WTF::Dominators::LengauerTarjan::computeExplicitImmediateDominators):
+ (WTF::Dominators::LengauerTarjan::link):
+ (WTF::Dominators::LengauerTarjan::eval):
+ (WTF::Dominators::LengauerTarjan::compress):
+ (WTF::Dominators::LengauerTarjan::BlockData::BlockData):
+ (WTF::Dominators::NaiveDominators::NaiveDominators):
+ (WTF::Dominators::NaiveDominators::dominates):
+ (WTF::Dominators::NaiveDominators::dump):
+ (WTF::Dominators::NaiveDominators::pruneDominators):
+ (WTF::Dominators::ValidationContext::ValidationContext):
+ (WTF::Dominators::ValidationContext::reportError):
+ (WTF::Dominators::ValidationContext::handleErrors):
+ (WTF::Dominators::naiveDominates):
+ (WTF::Dominators::forAllBlocksInDominanceFrontierOfImpl):
+ (WTF::Dominators::forAllBlocksInIteratedDominanceFrontierOfImpl):
+ (WTF::Dominators::BlockData::BlockData):
+
</ins><span class="cx"> 2015-11-01 Darin Adler <darin@apple.com>
</span><span class="cx">
</span><span class="cx"> Remove some dead and unneeded code (ScrollbarThemeSafari, RenderThemeSafari, OPENCL, a little color space logic)
</span></span></pre></div>
<a id="trunkSourceWTFWTFxcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/WTF.xcodeproj/project.pbxproj (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -25,6 +25,7 @@
</span><span class="cx"> 0F2B66A617B6B4FB00A7AE3F /* DeferrableRefCounted.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F2B66A417B6B4F700A7AE3F /* DeferrableRefCounted.h */; };
</span><span class="cx"> 0F2B66A717B6B4FD00A7AE3F /* FlipBytes.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F2B66A517B6B4F700A7AE3F /* FlipBytes.h */; };
</span><span class="cx"> 0F3501641BB258D500F0A2A3 /* WeakRandom.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F3501631BB258C800F0A2A3 /* WeakRandom.h */; };
</span><ins>+ 0F4570431BE5B58F0062A629 /* Dominators.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F4570421BE5B58F0062A629 /* Dominators.h */; };
</ins><span class="cx"> 0F824A681B7443A0002E345D /* ParkingLot.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F824A641B7443A0002E345D /* ParkingLot.cpp */; };
</span><span class="cx"> 0F824A691B7443A0002E345D /* ParkingLot.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F824A651B7443A0002E345D /* ParkingLot.h */; };
</span><span class="cx"> 0F87105A16643F190090B0AD /* RawPointer.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F87105916643F190090B0AD /* RawPointer.h */; };
</span><span class="lines">@@ -50,8 +51,8 @@
</span><span class="cx"> 0FE4479D1B7AAA03009498EB /* WordLock.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FE4479B1B7AAA03009498EB /* WordLock.h */; };
</span><span class="cx"> 0FEB3DCF1BB5D684009D7AAD /* SharedTask.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEB3DCE1BB5D684009D7AAD /* SharedTask.h */; };
</span><span class="cx"> 0FEB3DD11BB7366B009D7AAD /* ParallelVectorIterator.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEB3DD01BB7366B009D7AAD /* ParallelVectorIterator.h */; };
</span><ins>+ 0FEC84AF1BD825310080FF74 /* GraphNodeWorklist.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEC84AE1BD825310080FF74 /* GraphNodeWorklist.h */; };
</ins><span class="cx"> 0FEC84B11BDACD390080FF74 /* ScopedLambda.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEC84B01BDACD390080FF74 /* ScopedLambda.h */; };
</span><del>- 0FEC84AF1BD825310080FF74 /* GraphNodeWorklist.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEC84AE1BD825310080FF74 /* GraphNodeWorklist.h */; };
</del><span class="cx"> 0FED67B61B22D4D80066CE15 /* TinyPtrSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FED67B51B22D4D80066CE15 /* TinyPtrSet.h */; };
</span><span class="cx"> 0FF860951BCCBD740045127F /* PointerComparison.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FF860941BCCBD740045127F /* PointerComparison.h */; };
</span><span class="cx"> 0FFF19DC1BB334EB00886D91 /* ParallelHelperPool.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FFF19DA1BB334EB00886D91 /* ParallelHelperPool.cpp */; };
</span><span class="lines">@@ -321,6 +322,7 @@
</span><span class="cx"> 0F2B66A517B6B4F700A7AE3F /* FlipBytes.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = FlipBytes.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F300B7D18AB48B400A6D72E /* HashMethod.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = HashMethod.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F3501631BB258C800F0A2A3 /* WeakRandom.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = WeakRandom.h; sourceTree = "<group>"; };
</span><ins>+ 0F4570421BE5B58F0062A629 /* Dominators.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Dominators.h; sourceTree = "<group>"; };
</ins><span class="cx"> 0F824A641B7443A0002E345D /* ParkingLot.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ParkingLot.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 0F824A651B7443A0002E345D /* ParkingLot.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ParkingLot.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F87105916643F190090B0AD /* RawPointer.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = RawPointer.h; sourceTree = "<group>"; };
</span><span class="lines">@@ -346,8 +348,8 @@
</span><span class="cx"> 0FE4479B1B7AAA03009498EB /* WordLock.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = WordLock.h; sourceTree = "<group>"; };
</span><span class="cx"> 0FEB3DCE1BB5D684009D7AAD /* SharedTask.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SharedTask.h; sourceTree = "<group>"; };
</span><span class="cx"> 0FEB3DD01BB7366B009D7AAD /* ParallelVectorIterator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ParallelVectorIterator.h; sourceTree = "<group>"; };
</span><ins>+ 0FEC84AE1BD825310080FF74 /* GraphNodeWorklist.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = GraphNodeWorklist.h; sourceTree = "<group>"; };
</ins><span class="cx"> 0FEC84B01BDACD390080FF74 /* ScopedLambda.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ScopedLambda.h; sourceTree = "<group>"; };
</span><del>- 0FEC84AE1BD825310080FF74 /* GraphNodeWorklist.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = GraphNodeWorklist.h; sourceTree = "<group>"; };
</del><span class="cx"> 0FED67B51B22D4D80066CE15 /* TinyPtrSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = TinyPtrSet.h; sourceTree = "<group>"; };
</span><span class="cx"> 0FF860941BCCBD740045127F /* PointerComparison.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = PointerComparison.h; sourceTree = "<group>"; };
</span><span class="cx"> 0FFF19DA1BB334EB00886D91 /* ParallelHelperPool.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ParallelHelperPool.cpp; sourceTree = "<group>"; };
</span><span class="lines">@@ -764,6 +766,7 @@
</span><span class="cx"> 0F2B66A417B6B4F700A7AE3F /* DeferrableRefCounted.h */,
</span><span class="cx"> A8A4727E151A825A004123FF /* Deque.h */,
</span><span class="cx"> A8A4727F151A825A004123FF /* DisallowCType.h */,
</span><ins>+ 0F4570421BE5B58F0062A629 /* Dominators.h */,
</ins><span class="cx"> A8A47280151A825A004123FF /* DoublyLinkedList.h */,
</span><span class="cx"> A8A47297151A825A004123FF /* dtoa.cpp */,
</span><span class="cx"> A8A47298151A825A004123FF /* dtoa.h */,
</span><span class="lines">@@ -1185,6 +1188,7 @@
</span><span class="cx"> 1AFDE6531953B23D00C48FFA /* Optional.h in Headers */,
</span><span class="cx"> A8A473F6151A825B004123FF /* OSAllocator.h in Headers */,
</span><span class="cx"> 7CBBA07419BB7FDC00BBF025 /* OSObjectPtr.h in Headers */,
</span><ins>+ 0F4570431BE5B58F0062A629 /* Dominators.h in Headers */,
</ins><span class="cx"> A8A473FA151A825B004123FF /* OSRandomSource.h in Headers */,
</span><span class="cx"> A8A473FE151A825B004123FF /* PackedIntVector.h in Headers */,
</span><span class="cx"> A8A473FF151A825B004123FF /* PageAllocation.h in Headers */,
</span></span></pre></div>
<a id="trunkSourceWTFwtfCMakeListstxt"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/CMakeLists.txt (191869 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/CMakeLists.txt 2015-11-02 00:25:32 UTC (rev 191869)
+++ trunk/Source/WTF/wtf/CMakeLists.txt 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -16,6 +16,7 @@
</span><span class="cx"> CurrentTime.h
</span><span class="cx"> DataLog.h
</span><span class="cx"> DateMath.h
</span><ins>+ Dominators.h
</ins><span class="cx"> DecimalNumber.h
</span><span class="cx"> DeferrableRefCounted.h
</span><span class="cx"> Deque.h
</span></span></pre></div>
<a id="trunkSourceWTFwtfDominatorsh"></a>
<div class="addfile"><h4>Added: trunk/Source/WTF/wtf/Dominators.h (0 => 191870)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/Dominators.h (rev 0)
+++ trunk/Source/WTF/wtf/Dominators.h 2015-11-02 00:48:03 UTC (rev 191870)
</span><span class="lines">@@ -0,0 +1,746 @@
</span><ins>+/*
+ * Copyright (C) 2011, 2014, 2015 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 WTFDominators_h
+#define WTFDominators_h
+
+#include <wtf/GraphNodeWorklist.h>
+
+namespace WTF {
+
+// This is a utility for finding the dominators of a graph. Dominators are almost universally used
+// for control flow graph analysis, so this code will refer to the graph's "nodes" as "blocks". In
+// that regard this code is kind of specialized for the various JSC compilers, but you could use it
+// for non-compiler things if you are OK with referring to your "nodes" as "blocks".
+
+template<typename Graph>
+class Dominators {
+public:
+ Dominators(Graph& graph, bool selfCheck = false)
+ : m_graph(graph)
+ {
+ LengauerTarjan lengauerTarjan(m_graph);
+ lengauerTarjan.compute();
+
+ m_data = m_graph.template newMap<BlockData>();
+
+ // 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 (unsigned blockIndex = m_graph.numNodes(); blockIndex--;) {
+ typename Graph::Node block = m_graph.node(blockIndex);
+ if (!block)
+ continue;
+
+ typename Graph::Node 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<GraphNodeWithOrder<typename Graph::Node>> worklist;
+ worklist.append(GraphNodeWithOrder<typename Graph::Node>(m_graph.node(0), GraphVisitOrder::Pre));
+ while (!worklist.isEmpty()) {
+ GraphNodeWithOrder<typename Graph::Node> item = worklist.takeLast();
+ switch (item.order) {
+ case GraphVisitOrder::Pre:
+ m_data[item.node].preNumber = nextPreNumber++;
+ worklist.append(GraphNodeWithOrder<typename Graph::Node>(item.node, GraphVisitOrder::Post));
+ for (typename Graph::Node kid : m_data[item.node].idomKids)
+ worklist.append(GraphNodeWithOrder<typename Graph::Node>(kid, GraphVisitOrder::Pre));
+ break;
+ case GraphVisitOrder::Post:
+ m_data[item.node].postNumber = nextPostNumber++;
+ break;
+ }
+ }
+
+ if (selfCheck) {
+ // 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(m_graph, *this);
+
+ for (unsigned fromBlockIndex = m_graph.numNodes(); fromBlockIndex--;) {
+ typename Graph::Node fromBlock = m_graph.node(fromBlockIndex);
+ if (!fromBlock || m_data[fromBlock].preNumber == UINT_MAX)
+ continue;
+ for (unsigned toBlockIndex = m_graph.numNodes(); toBlockIndex--;) {
+ typename Graph::Node toBlock = m_graph.node(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");
+ }
+ }
+
+ context.handleErrors();
+ }
+ }
+
+ bool strictlyDominates(typename Graph::Node from, typename Graph::Node to) const
+ {
+ return m_data[to].preNumber > m_data[from].preNumber
+ && m_data[to].postNumber < m_data[from].postNumber;
+ }
+
+ bool dominates(typename Graph::Node from, typename Graph::Node to) const
+ {
+ return from == to || strictlyDominates(from, to);
+ }
+
+ typename Graph::Node immediateDominatorOf(typename Graph::Node block) const
+ {
+ return m_data[block].idomParent;
+ }
+
+ template<typename Functor>
+ void forAllStrictDominatorsOf(typename Graph::Node to, const Functor& functor) const
+ {
+ for (typename Graph::Node block = m_data[to].idomParent; block; block = m_data[block].idomParent)
+ functor(block);
+ }
+
+ template<typename Functor>
+ void forAllDominatorsOf(typename Graph::Node to, const Functor& functor) const
+ {
+ for (typename Graph::Node block = to; block; block = m_data[block].idomParent)
+ functor(block);
+ }
+
+ template<typename Functor>
+ void forAllBlocksStrictlyDominatedBy(typename Graph::Node from, const Functor& functor) const
+ {
+ Vector<typename Graph::Node, 16> worklist;
+ worklist.appendVector(m_data[from].idomKids);
+ while (!worklist.isEmpty()) {
+ typename Graph::Node block = worklist.takeLast();
+ functor(block);
+ worklist.appendVector(m_data[block].idomKids);
+ }
+ }
+
+ template<typename Functor>
+ void forAllBlocksDominatedBy(typename Graph::Node from, const Functor& functor) const
+ {
+ Vector<typename Graph::Node, 16> worklist;
+ worklist.append(from);
+ while (!worklist.isEmpty()) {
+ typename Graph::Node block = worklist.takeLast();
+ functor(block);
+ worklist.appendVector(m_data[block].idomKids);
+ }
+ }
+
+ typename Graph::Set strictDominatorsOf(typename Graph::Node to) const
+ {
+ typename Graph::Set result;
+ forAllStrictDominatorsOf(
+ to,
+ [&] (typename Graph::Node node) {
+ result.add(node);
+ });
+ return result;
+ }
+
+ typename Graph::Set dominatorsOf(typename Graph::Node to) const
+ {
+ typename Graph::Set result;
+ forAllDominatorsOf(
+ to,
+ [&] (typename Graph::Node node) {
+ result.add(node);
+ });
+ return result;
+ }
+
+ typename Graph::Set blocksStrictlyDominatedBy(typename Graph::Node from) const
+ {
+ typename Graph::Set result;
+ forAllBlocksStrictlyDominatedBy(
+ from,
+ [&] (typename Graph::Node node) {
+ result.add(node);
+ });
+ return result;
+ }
+
+ typename Graph::Set blocksDominatedBy(typename Graph::Node from) const
+ {
+ typename Graph::Set result;
+ forAllBlocksDominatedBy(
+ from,
+ [&] (typename Graph::Node node) {
+ result.add(node);
+ });
+ return result;
+ }
+
+ template<typename Functor>
+ void forAllBlocksInDominanceFrontierOf(
+ typename Graph::Node from, const Functor& functor) const
+ {
+ typename Graph::Set set;
+ forAllBlocksInDominanceFrontierOfImpl(
+ from,
+ [&] (typename Graph::Node block) {
+ if (set.add(block))
+ functor(block);
+ });
+ }
+
+ typename Graph::Set dominanceFrontierOf(typename Graph::Node from) const
+ {
+ typename Graph::Set result;
+ forAllBlocksInDominanceFrontierOf(
+ from,
+ [&] (typename Graph::Node node) {
+ result.add(node);
+ });
+ return result;
+ }
+
+ template<typename Functor>
+ void forAllBlocksInIteratedDominanceFrontierOf(const typename Graph::List& from, const Functor& functor)
+ {
+ forAllBlocksInPrunedIteratedDominanceFrontierOf(
+ from,
+ [&] (typename Graph::Node block) -> bool {
+ functor(block);
+ return true;
+ });
+ }
+
+ // This is a close relative of forAllBlocksInIteratedDominanceFrontierOf(), which allows the
+ // given functor to return false to indicate that we don't wish to consider the given block.
+ // Useful for computing pruned SSA form.
+ template<typename Functor>
+ void forAllBlocksInPrunedIteratedDominanceFrontierOf(
+ const typename Graph::List& from, const Functor& functor)
+ {
+ typename Graph::Set set;
+ forAllBlocksInIteratedDominanceFrontierOfImpl(
+ from,
+ [&] (typename Graph::Node block) -> bool {
+ if (!set.add(block))
+ return false;
+ return functor(block);
+ });
+ }
+
+ typename Graph::Set iteratedDominanceFrontierOf(const typename Graph::List& from) const
+ {
+ typename Graph::Set result;
+ forAllBlocksInIteratedDominanceFrontierOfImpl(
+ from,
+ [&] (typename Graph::Node node) -> bool {
+ return result.add(node);
+ });
+ return result;
+ }
+
+ void dump(PrintStream& out) const
+ {
+ for (unsigned 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");
+ }
+ }
+
+private:
+ // 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.template newMap<BlockData>())
+ {
+ for (unsigned blockIndex = m_graph.numNodes(); blockIndex--;) {
+ typename Graph::Node block = m_graph.node(blockIndex);
+ if (!block)
+ continue;
+ m_data[block].label = block;
+ }
+ }
+
+ void compute()
+ {
+ computeDepthFirstPreNumbering(); // Step 1.
+ computeSemiDominatorsAndImplicitImmediateDominators(); // Steps 2 and 3.
+ computeExplicitImmediateDominators(); // Step 4.
+ }
+
+ typename Graph::Node immediateDominator(typename Graph::Node block)
+ {
+ return m_data[block].dom;
+ }
+
+ 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.
+
+ ExtendedGraphNodeWorklist<typename Graph::Node, unsigned, typename Graph::Set> worklist;
+ worklist.push(m_graph.node(0), 0);
+
+ while (GraphNodeWith<typename Graph::Node, unsigned> item = worklist.pop()) {
+ typename Graph::Node block = item.node;
+ 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 < m_graph.successors(block).size());
+
+ if (!successorIndex) {
+ m_data[block].semiNumber = m_blockByPreNumber.size();
+ m_blockByPreNumber.append(block);
+ }
+
+ if (successorIndex < m_graph.successors(block).size()) {
+ unsigned nextSuccessorIndex = successorIndex + 1;
+ if (nextSuccessorIndex < m_graph.successors(block).size())
+ worklist.forcePush(block, nextSuccessorIndex);
+
+ typename Graph::Node successorBlock = m_graph.successors(block)[successorIndex];
+ if (worklist.push(successorBlock, 0))
+ m_data[successorBlock].parent = block;
+ }
+ }
+ }
+
+ void computeSemiDominatorsAndImplicitImmediateDominators()
+ {
+ for (unsigned currentPreNumber = m_blockByPreNumber.size(); currentPreNumber-- > 1;) {
+ typename Graph::Node block = m_blockByPreNumber[currentPreNumber];
+ BlockData& blockData = m_data[block];
+
+ // Step 2:
+ for (typename Graph::Node predecessorBlock : m_graph.predecessors(block)) {
+ typename Graph::Node 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 (typename Graph::Node semiDominee : m_data[blockData.parent].bucket) {
+ typename Graph::Node 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();
+ }
+ }
+
+ void computeExplicitImmediateDominators()
+ {
+ for (unsigned currentPreNumber = 1; currentPreNumber < m_blockByPreNumber.size(); ++currentPreNumber) {
+ typename Graph::Node 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(typename Graph::Node from, typename Graph::Node to)
+ {
+ m_data[to].ancestor = from;
+ }
+
+ typename Graph::Node eval(typename Graph::Node block)
+ {
+ if (!m_data[block].ancestor)
+ return block;
+
+ compress(block);
+ return m_data[block].label;
+ }
+
+ void compress(typename Graph::Node 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.
+
+ typename Graph::Node ancestor = m_data[initialBlock].ancestor;
+ ASSERT(ancestor);
+ if (!m_data[ancestor].ancestor)
+ return;
+
+ Vector<typename Graph::Node, 16> stack;
+ for (typename Graph::Node 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--;) {
+ typename Graph::Node block = stack[i];
+ typename Graph::Node& labelOfBlock = m_data[block].label;
+ typename Graph::Node& ancestorOfBlock = m_data[block].ancestor;
+ ASSERT(ancestorOfBlock);
+ ASSERT(m_data[ancestorOfBlock].ancestor);
+
+ typename Graph::Node labelOfAncestorOfBlock = m_data[ancestorOfBlock].label;
+
+ if (m_data[labelOfAncestorOfBlock].semiNumber < m_data[labelOfBlock].semiNumber)
+ labelOfBlock = labelOfAncestorOfBlock;
+ ancestorOfBlock = m_data[ancestorOfBlock].ancestor;
+ }
+ }
+
+ struct BlockData {
+ BlockData()
+ : parent(nullptr)
+ , preNumber(UINT_MAX)
+ , semiNumber(UINT_MAX)
+ , ancestor(nullptr)
+ , label(nullptr)
+ , dom(nullptr)
+ {
+ }
+
+ typename Graph::Node parent;
+ unsigned preNumber;
+ unsigned semiNumber;
+ typename Graph::Node ancestor;
+ typename Graph::Node label;
+ Vector<typename Graph::Node> bucket;
+ typename Graph::Node dom;
+ };
+
+ Graph& m_graph;
+ typename Graph::template Map<BlockData> m_data;
+ Vector<typename Graph::Node> m_blockByPreNumber;
+ };
+
+ class NaiveDominators {
+ public:
+ NaiveDominators(Graph& graph)
+ : m_graph(graph)
+ {
+ // This implements a naive dominator solver.
+
+ ASSERT(!graph.predecessors(graph.root()).size());
+
+ unsigned numBlocks = graph.numNodes();
+
+ // Allocate storage for the dense dominance matrix.
+ 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.node(i))
+ continue;
+ m_scratch.set(i);
+ }
+
+ // Mark all nodes as dominated by everything.
+ for (unsigned i = numBlocks; i-- > 1;) {
+ if (!graph.node(i) || !graph.predecessors(graph.node(i)).size())
+ 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(i);
+
+ if (!changed)
+ break;
+
+ // Prune dominators in all non entry blocks: backward scan.
+ changed = false;
+ for (unsigned i = numBlocks; i-- > 1;)
+ changed |= pruneDominators(i);
+ } while (changed);
+ }
+
+ bool dominates(unsigned from, unsigned to) const
+ {
+ return m_results[to].get(from);
+ }
+
+ bool dominates(typename Graph::Node from, typename Graph::Node to) const
+ {
+ return dominates(from->index, to->index);
+ }
+
+ void dump(PrintStream& out) const
+ {
+ for (unsigned blockIndex = 0; blockIndex < m_graph.numNodes(); ++blockIndex) {
+ typename Graph::Node block = m_graph.node(blockIndex);
+ if (!block)
+ continue;
+ out.print(" Block ", m_graph.dump(block), ":");
+ for (unsigned otherIndex = 0; otherIndex < m_graph.numNodes(); ++otherIndex) {
+ if (!dominates(m_graph.index(block), otherIndex))
+ continue;
+ out.print(" ", m_graph.dump(m_graph.node(otherIndex)));
+ }
+ out.print("\n");
+ }
+ }
+
+ private:
+ bool pruneDominators(unsigned idx)
+ {
+ typename Graph::Node block = m_graph.node(idx);
+
+ if (!block || !m_graph.predecessors(block).size())
+ return false;
+
+ // Find the intersection of dom(preds).
+ m_scratch.set(m_results[m_graph.index(m_graph.predecessors(block)[0])]);
+ for (unsigned j = m_graph.predecessors(block).size(); j-- > 1;)
+ m_scratch.filter(m_results[m_graph.index(m_graph.predecessors(block)[j])]);
+
+ // The block is also dominated by itself.
+ m_scratch.set(idx);
+
+ return m_results[idx].setAndCheck(m_scratch);
+ }
+
+ Graph m_graph;
+ 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.
+ };
+
+ struct ValidationContext {
+ ValidationContext(Graph& graph, Dominators& dominators)
+ : graph(graph)
+ , dominators(dominators)
+ , naiveDominators(graph)
+ {
+ }
+
+ void reportError(typename Graph::Node from, typename Graph::Node to, const char* message)
+ {
+ Error error;
+ error.from = from;
+ error.to = to;
+ error.message = message;
+ errors.append(error);
+ }
+
+ void handleErrors()
+ {
+ if (errors.isEmpty())
+ return;
+
+ dataLog("DFG DOMINATOR VALIDATION FAILED:\n");
+ dataLog("\n");
+ dataLog("For block domination relationships:\n");
+ for (unsigned i = 0; i < errors.size(); ++i) {
+ dataLog(
+ " ", graph.dump(errors[i].from), " -> ", graph.dump(errors[i].to),
+ " (", errors[i].message, ")\n");
+ }
+ dataLog("\n");
+ dataLog("Control flow graph:\n");
+ for (unsigned blockIndex = 0; blockIndex < graph.numNodes(); ++blockIndex) {
+ typename Graph::Node block = graph.node(blockIndex);
+ if (!block)
+ continue;
+ dataLog(" Block ", graph.dump(graph.node(blockIndex)), ": successors = [");
+ CommaPrinter comma;
+ for (unsigned i = 0; i < block->numSuccessors(); ++i)
+ dataLog(comma, graph.dump(block->successor(i)));
+ dataLog("], predecessors = [");
+ comma = CommaPrinter();
+ for (unsigned i = 0; i < block->predecessors.size(); ++i)
+ dataLog(comma, graph.dump(block->predecessors[i]));
+ dataLog("]\n");
+ }
+ dataLog("\n");
+ dataLog("Lengauer-Tarjan Dominators:\n");
+ dataLog(dominators);
+ dataLog("\n");
+ dataLog("Naive Dominators:\n");
+ naiveDominators.dump(WTF::dataFile());
+ dataLog("\n");
+ dataLog("Graph at time of failure:\n");
+ dataLog(graph);
+ dataLog("\n");
+ dataLog("DFG DOMINATOR VALIDATION FAILIED!\n");
+ CRASH();
+ }
+
+ Graph& graph;
+ Dominators& dominators;
+ NaiveDominators naiveDominators;
+
+ struct Error {
+ typename Graph::Node from;
+ typename Graph::Node to;
+ const char* message;
+ };
+
+ Vector<Error> errors;
+ };
+
+ bool naiveDominates(typename Graph::Node from, typename Graph::Node to) const
+ {
+ for (typename Graph::Node block = to; block; block = m_data[block].idomParent) {
+ if (block == from)
+ return true;
+ }
+ return false;
+ }
+
+ template<typename Functor>
+ void forAllBlocksInDominanceFrontierOfImpl(
+ typename Graph::Node from, const Functor& functor) const
+ {
+ // Paraphrasing from http://en.wikipedia.org/wiki/Dominator_(graph_theory):
+ // "The dominance frontier of a block 'from' is the set of all blocks 'to' such that
+ // 'from' dominates an immediate predecessor of 'to', but 'from' does not strictly
+ // dominate 'to'."
+ //
+ // A useful corner case to remember: a block may be in its own dominance frontier if it has
+ // a loop edge to itself, since it dominates itself and so it dominates its own immediate
+ // predecessor, and a block never strictly dominates itself.
+
+ forAllBlocksDominatedBy(
+ from,
+ [&] (typename Graph::Node block) {
+ for (typename Graph::Node to : m_graph.successors(block)) {
+ if (!strictlyDominates(from, to))
+ functor(to);
+ }
+ });
+ }
+
+ template<typename Functor>
+ void forAllBlocksInIteratedDominanceFrontierOfImpl(
+ const typename Graph::List& from, const Functor& functor) const
+ {
+ typename Graph::List worklist = from;
+ while (!worklist.isEmpty()) {
+ typename Graph::Node block = worklist.takeLast();
+ forAllBlocksInDominanceFrontierOfImpl(
+ block,
+ [&] (typename Graph::Node otherBlock) {
+ if (functor(otherBlock))
+ worklist.append(otherBlock);
+ });
+ }
+ }
+
+ struct BlockData {
+ BlockData()
+ : idomParent(nullptr)
+ , preNumber(UINT_MAX)
+ , postNumber(UINT_MAX)
+ {
+ }
+
+ Vector<typename Graph::Node> idomKids;
+ typename Graph::Node idomParent;
+
+ unsigned preNumber;
+ unsigned postNumber;
+ };
+
+ Graph& m_graph;
+ typename Graph::template Map<BlockData> m_data;
+};
+
+} // namespace WTF
+
+using WTF::Dominators;
+
+#endif // WTFDominators_h
+
</ins></span></pre>
</div>
</div>
</body>
</html>