<!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>[214410] 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/214410">214410</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2017-03-26 21:17:52 -0700 (Sun, 26 Mar 2017)</dd>
</dl>
<h3>Log Message</h3>
<pre>B3::fixSSA should do liveness pruning
https://bugs.webkit.org/show_bug.cgi?id=170111
Reviewed by Saam Barati.
Source/JavaScriptCore:
This moves all of the logic of Air::Liveness<> to WTF::Liveness<> and then uses that to
create B3::VariableLiveness. Then this uses VariableLiveness::LiveAtHead to prune Phi
construction.
This makes B3::fixSSA run twice as fast. This is a 13% progression on WasmBench compile
times.
* CMakeLists.txt:
* JavaScriptCore.xcodeproj/project.pbxproj:
* b3/B3BasicBlock.h:
(JSC::B3::BasicBlock::get):
* b3/B3FixSSA.cpp:
(JSC::B3::fixSSA):
* b3/B3VariableLiveness.cpp: Added.
(JSC::B3::VariableLiveness::VariableLiveness):
(JSC::B3::VariableLiveness::~VariableLiveness):
* b3/B3VariableLiveness.h: Added.
(JSC::B3::VariableLivenessAdapter::VariableLivenessAdapter):
(JSC::B3::VariableLivenessAdapter::numIndices):
(JSC::B3::VariableLivenessAdapter::valueToIndex):
(JSC::B3::VariableLivenessAdapter::indexToValue):
(JSC::B3::VariableLivenessAdapter::blockSize):
(JSC::B3::VariableLivenessAdapter::forEachEarlyUse):
(JSC::B3::VariableLivenessAdapter::forEachLateUse):
(JSC::B3::VariableLivenessAdapter::forEachEarlyDef):
(JSC::B3::VariableLivenessAdapter::forEachLateDef):
* b3/air/AirCFG.h: Added.
(JSC::B3::Air::CFG::CFG):
(JSC::B3::Air::CFG::root):
(JSC::B3::Air::CFG::newMap):
(JSC::B3::Air::CFG::successors):
(JSC::B3::Air::CFG::predecessors):
(JSC::B3::Air::CFG::index):
(JSC::B3::Air::CFG::node):
(JSC::B3::Air::CFG::numNodes):
(JSC::B3::Air::CFG::dump):
* b3/air/AirCode.cpp:
(JSC::B3::Air::Code::Code):
* b3/air/AirCode.h:
(JSC::B3::Air::Code::cfg):
* b3/air/AirLiveness.h:
(JSC::B3::Air::LivenessAdapter::LivenessAdapter):
(JSC::B3::Air::LivenessAdapter::blockSize):
(JSC::B3::Air::LivenessAdapter::forEachEarlyUse):
(JSC::B3::Air::LivenessAdapter::forEachLateUse):
(JSC::B3::Air::LivenessAdapter::forEachEarlyDef):
(JSC::B3::Air::LivenessAdapter::forEachLateDef):
(JSC::B3::Air::TmpLivenessAdapter::TmpLivenessAdapter):
(JSC::B3::Air::TmpLivenessAdapter::numIndices):
(JSC::B3::Air::StackSlotLivenessAdapter::StackSlotLivenessAdapter):
(JSC::B3::Air::StackSlotLivenessAdapter::numIndices):
(JSC::B3::Air::StackSlotLivenessAdapter::indexToValue):
(JSC::B3::Air::Liveness::Liveness):
(JSC::B3::Air::Liveness::LocalCalc::LocalCalc): Deleted.
(JSC::B3::Air::Liveness::LocalCalc::Iterable::Iterable): Deleted.
(JSC::B3::Air::Liveness::LocalCalc::Iterable::iterator::iterator): Deleted.
(JSC::B3::Air::Liveness::LocalCalc::Iterable::iterator::operator++): Deleted.
(JSC::B3::Air::Liveness::LocalCalc::Iterable::iterator::operator*): Deleted.
(JSC::B3::Air::Liveness::LocalCalc::Iterable::iterator::operator==): Deleted.
(JSC::B3::Air::Liveness::LocalCalc::Iterable::iterator::operator!=): Deleted.
(JSC::B3::Air::Liveness::LocalCalc::Iterable::begin): Deleted.
(JSC::B3::Air::Liveness::LocalCalc::Iterable::end): Deleted.
(JSC::B3::Air::Liveness::LocalCalc::Iterable::contains): Deleted.
(JSC::B3::Air::Liveness::LocalCalc::live): Deleted.
(JSC::B3::Air::Liveness::LocalCalc::isLive): Deleted.
(JSC::B3::Air::Liveness::LocalCalc::execute): Deleted.
(JSC::B3::Air::Liveness::rawLiveAtHead): Deleted.
(JSC::B3::Air::Liveness::Iterable::Iterable): Deleted.
(JSC::B3::Air::Liveness::Iterable::iterator::iterator): Deleted.
(JSC::B3::Air::Liveness::Iterable::iterator::operator*): Deleted.
(JSC::B3::Air::Liveness::Iterable::iterator::operator++): Deleted.
(JSC::B3::Air::Liveness::Iterable::iterator::operator==): Deleted.
(JSC::B3::Air::Liveness::Iterable::iterator::operator!=): Deleted.
(JSC::B3::Air::Liveness::Iterable::begin): Deleted.
(JSC::B3::Air::Liveness::Iterable::end): Deleted.
(JSC::B3::Air::Liveness::Iterable::contains): Deleted.
(JSC::B3::Air::Liveness::liveAtHead): Deleted.
(JSC::B3::Air::Liveness::liveAtTail): Deleted.
(JSC::B3::Air::Liveness::workset): Deleted.
Source/WTF:
Move Air::Liveness<> to WTF::Liveness<>. This is pretty easy since Air::Liveness<> was
already fairly generic. It leverages the CFG concept so that it can understand many
different kinds of basic blocks. It doesn't try to understand the contents of basic
blocks; it just asks the adaptor for the block size and asks for the early/late
uses/defs of each thing in the block.
This makes it easy to create a B3::VariableLiveness, which fixSSA then uses for
pruning. One of the new features is the Liveness::LiveAtHead nested class, which you
instantiate if you want to perform liveAtHead queries, which SSA construction wants to
do.
This also fixes https://bugs.webkit.org/show_bug.cgi?id=170102#c12
* WTF.xcodeproj/project.pbxproj:
* wtf/CMakeLists.txt:
* wtf/Liveness.h: Added.
(WTF::Liveness::Liveness):
(WTF::Liveness::LocalCalc::LocalCalc):
(WTF::Liveness::LocalCalc::Iterable::Iterable):
(WTF::Liveness::LocalCalc::Iterable::iterator::iterator):
(WTF::Liveness::LocalCalc::Iterable::iterator::operator++):
(WTF::Liveness::LocalCalc::Iterable::iterator::operator*):
(WTF::Liveness::LocalCalc::Iterable::iterator::operator==):
(WTF::Liveness::LocalCalc::Iterable::iterator::operator!=):
(WTF::Liveness::LocalCalc::Iterable::begin):
(WTF::Liveness::LocalCalc::Iterable::end):
(WTF::Liveness::LocalCalc::Iterable::contains):
(WTF::Liveness::LocalCalc::live):
(WTF::Liveness::LocalCalc::isLive):
(WTF::Liveness::LocalCalc::execute):
(WTF::Liveness::rawLiveAtHead):
(WTF::Liveness::Iterable::Iterable):
(WTF::Liveness::Iterable::iterator::iterator):
(WTF::Liveness::Iterable::iterator::operator*):
(WTF::Liveness::Iterable::iterator::operator++):
(WTF::Liveness::Iterable::iterator::operator==):
(WTF::Liveness::Iterable::iterator::operator!=):
(WTF::Liveness::Iterable::begin):
(WTF::Liveness::Iterable::end):
(WTF::Liveness::Iterable::contains):
(WTF::Liveness::liveAtHead):
(WTF::Liveness::liveAtTail):
(WTF::Liveness::workset):
(WTF::Liveness::LiveAtHead::LiveAtHead):
(WTF::Liveness::LiveAtHead::isLiveAtHead):</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="#trunkSourceJavaScriptCoreb3B3BasicBlockh">trunk/Source/JavaScriptCore/b3/B3BasicBlock.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3FixSSAcpp">trunk/Source/JavaScriptCore/b3/B3FixSSA.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirCodecpp">trunk/Source/JavaScriptCore/b3/air/AirCode.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirCodeh">trunk/Source/JavaScriptCore/b3/air/AirCode.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirLivenessh">trunk/Source/JavaScriptCore/b3/air/AirLiveness.h</a></li>
<li><a href="#trunkSourceWTFChangeLog">trunk/Source/WTF/ChangeLog</a></li>
<li><a href="#trunkSourceWTFWTFxcodeprojprojectpbxproj">trunk/Source/WTF/WTF.xcodeproj/project.pbxproj</a></li>
<li><a href="#trunkSourceWTFwtfCMakeListstxt">trunk/Source/WTF/wtf/CMakeLists.txt</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreb3B3VariableLivenesscpp">trunk/Source/JavaScriptCore/b3/B3VariableLiveness.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3VariableLivenessh">trunk/Source/JavaScriptCore/b3/B3VariableLiveness.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirCFGh">trunk/Source/JavaScriptCore/b3/air/AirCFG.h</a></li>
<li><a href="#trunkSourceWTFwtfLivenessh">trunk/Source/WTF/wtf/Liveness.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 (214409 => 214410)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/CMakeLists.txt 2017-03-26 22:11:13 UTC (rev 214409)
+++ trunk/Source/JavaScriptCore/CMakeLists.txt 2017-03-27 04:17:52 UTC (rev 214410)
</span><span class="lines">@@ -180,6 +180,7 @@
</span><span class="cx"> b3/B3ValueKey.cpp
</span><span class="cx"> b3/B3ValueRep.cpp
</span><span class="cx"> b3/B3Variable.cpp
</span><ins>+ b3/B3VariableLiveness.cpp
</ins><span class="cx"> b3/B3VariableValue.cpp
</span><span class="cx"> b3/B3WasmAddressValue.cpp
</span><span class="cx"> b3/B3WasmBoundsCheckValue.cpp
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (214409 => 214410)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2017-03-26 22:11:13 UTC (rev 214409)
+++ trunk/Source/JavaScriptCore/ChangeLog 2017-03-27 04:17:52 UTC (rev 214410)
</span><span class="lines">@@ -1,3 +1,90 @@
</span><ins>+2017-03-26 Filip Pizlo <fpizlo@apple.com>
+
+ B3::fixSSA should do liveness pruning
+ https://bugs.webkit.org/show_bug.cgi?id=170111
+
+ Reviewed by Saam Barati.
+
+ This moves all of the logic of Air::Liveness<> to WTF::Liveness<> and then uses that to
+ create B3::VariableLiveness. Then this uses VariableLiveness::LiveAtHead to prune Phi
+ construction.
+
+ This makes B3::fixSSA run twice as fast. This is a 13% progression on WasmBench compile
+ times.
+
+ * CMakeLists.txt:
+ * JavaScriptCore.xcodeproj/project.pbxproj:
+ * b3/B3BasicBlock.h:
+ (JSC::B3::BasicBlock::get):
+ * b3/B3FixSSA.cpp:
+ (JSC::B3::fixSSA):
+ * b3/B3VariableLiveness.cpp: Added.
+ (JSC::B3::VariableLiveness::VariableLiveness):
+ (JSC::B3::VariableLiveness::~VariableLiveness):
+ * b3/B3VariableLiveness.h: Added.
+ (JSC::B3::VariableLivenessAdapter::VariableLivenessAdapter):
+ (JSC::B3::VariableLivenessAdapter::numIndices):
+ (JSC::B3::VariableLivenessAdapter::valueToIndex):
+ (JSC::B3::VariableLivenessAdapter::indexToValue):
+ (JSC::B3::VariableLivenessAdapter::blockSize):
+ (JSC::B3::VariableLivenessAdapter::forEachEarlyUse):
+ (JSC::B3::VariableLivenessAdapter::forEachLateUse):
+ (JSC::B3::VariableLivenessAdapter::forEachEarlyDef):
+ (JSC::B3::VariableLivenessAdapter::forEachLateDef):
+ * b3/air/AirCFG.h: Added.
+ (JSC::B3::Air::CFG::CFG):
+ (JSC::B3::Air::CFG::root):
+ (JSC::B3::Air::CFG::newMap):
+ (JSC::B3::Air::CFG::successors):
+ (JSC::B3::Air::CFG::predecessors):
+ (JSC::B3::Air::CFG::index):
+ (JSC::B3::Air::CFG::node):
+ (JSC::B3::Air::CFG::numNodes):
+ (JSC::B3::Air::CFG::dump):
+ * b3/air/AirCode.cpp:
+ (JSC::B3::Air::Code::Code):
+ * b3/air/AirCode.h:
+ (JSC::B3::Air::Code::cfg):
+ * b3/air/AirLiveness.h:
+ (JSC::B3::Air::LivenessAdapter::LivenessAdapter):
+ (JSC::B3::Air::LivenessAdapter::blockSize):
+ (JSC::B3::Air::LivenessAdapter::forEachEarlyUse):
+ (JSC::B3::Air::LivenessAdapter::forEachLateUse):
+ (JSC::B3::Air::LivenessAdapter::forEachEarlyDef):
+ (JSC::B3::Air::LivenessAdapter::forEachLateDef):
+ (JSC::B3::Air::TmpLivenessAdapter::TmpLivenessAdapter):
+ (JSC::B3::Air::TmpLivenessAdapter::numIndices):
+ (JSC::B3::Air::StackSlotLivenessAdapter::StackSlotLivenessAdapter):
+ (JSC::B3::Air::StackSlotLivenessAdapter::numIndices):
+ (JSC::B3::Air::StackSlotLivenessAdapter::indexToValue):
+ (JSC::B3::Air::Liveness::Liveness):
+ (JSC::B3::Air::Liveness::LocalCalc::LocalCalc): Deleted.
+ (JSC::B3::Air::Liveness::LocalCalc::Iterable::Iterable): Deleted.
+ (JSC::B3::Air::Liveness::LocalCalc::Iterable::iterator::iterator): Deleted.
+ (JSC::B3::Air::Liveness::LocalCalc::Iterable::iterator::operator++): Deleted.
+ (JSC::B3::Air::Liveness::LocalCalc::Iterable::iterator::operator*): Deleted.
+ (JSC::B3::Air::Liveness::LocalCalc::Iterable::iterator::operator==): Deleted.
+ (JSC::B3::Air::Liveness::LocalCalc::Iterable::iterator::operator!=): Deleted.
+ (JSC::B3::Air::Liveness::LocalCalc::Iterable::begin): Deleted.
+ (JSC::B3::Air::Liveness::LocalCalc::Iterable::end): Deleted.
+ (JSC::B3::Air::Liveness::LocalCalc::Iterable::contains): Deleted.
+ (JSC::B3::Air::Liveness::LocalCalc::live): Deleted.
+ (JSC::B3::Air::Liveness::LocalCalc::isLive): Deleted.
+ (JSC::B3::Air::Liveness::LocalCalc::execute): Deleted.
+ (JSC::B3::Air::Liveness::rawLiveAtHead): Deleted.
+ (JSC::B3::Air::Liveness::Iterable::Iterable): Deleted.
+ (JSC::B3::Air::Liveness::Iterable::iterator::iterator): Deleted.
+ (JSC::B3::Air::Liveness::Iterable::iterator::operator*): Deleted.
+ (JSC::B3::Air::Liveness::Iterable::iterator::operator++): Deleted.
+ (JSC::B3::Air::Liveness::Iterable::iterator::operator==): Deleted.
+ (JSC::B3::Air::Liveness::Iterable::iterator::operator!=): Deleted.
+ (JSC::B3::Air::Liveness::Iterable::begin): Deleted.
+ (JSC::B3::Air::Liveness::Iterable::end): Deleted.
+ (JSC::B3::Air::Liveness::Iterable::contains): Deleted.
+ (JSC::B3::Air::Liveness::liveAtHead): Deleted.
+ (JSC::B3::Air::Liveness::liveAtTail): Deleted.
+ (JSC::B3::Air::Liveness::workset): Deleted.
+
</ins><span class="cx"> 2017-03-25 Filip Pizlo <fpizlo@apple.com>
</span><span class="cx">
</span><span class="cx"> Air::Liveness shouldn't need HashSets
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreJavaScriptCorexcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj (214409 => 214410)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj 2017-03-26 22:11:13 UTC (rev 214409)
+++ trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj 2017-03-27 04:17:52 UTC (rev 214410)
</span><span class="lines">@@ -1007,6 +1007,9 @@
</span><span class="cx"> 0FF427651591A1CE004CB9FF /* DFGDisassembler.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FF427621591A1C9004CB9FF /* DFGDisassembler.h */; };
</span><span class="cx"> 0FF4B4BC1E88449700DBBE86 /* AirRegLiveness.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FF4B4BA1E88449500DBBE86 /* AirRegLiveness.cpp */; };
</span><span class="cx"> 0FF4B4BD1E88449A00DBBE86 /* AirRegLiveness.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FF4B4BB1E88449500DBBE86 /* AirRegLiveness.h */; };
</span><ins>+ 0FF4B4C71E8893C500DBBE86 /* AirCFG.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FF4B4C61E8893BF00DBBE86 /* AirCFG.h */; };
+ 0FF4B4CA1E889D7B00DBBE86 /* B3VariableLiveness.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FF4B4C81E889D7800DBBE86 /* B3VariableLiveness.cpp */; };
+ 0FF4B4CB1E889D7E00DBBE86 /* B3VariableLiveness.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FF4B4C91E889D7800DBBE86 /* B3VariableLiveness.h */; };
</ins><span class="cx"> 0FF60AC216740F8300029779 /* ReduceWhitespace.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FF60AC016740F8100029779 /* ReduceWhitespace.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 0FF60AC316740F8800029779 /* ReduceWhitespace.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FF60ABF16740F8100029779 /* ReduceWhitespace.cpp */; };
</span><span class="cx"> 0FF7168C15A3B235008F5DAA /* PropertyOffset.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FF7168A15A3B231008F5DAA /* PropertyOffset.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="lines">@@ -3524,6 +3527,9 @@
</span><span class="cx"> 0FF427621591A1C9004CB9FF /* DFGDisassembler.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGDisassembler.h; path = dfg/DFGDisassembler.h; sourceTree = "<group>"; };
</span><span class="cx"> 0FF4B4BA1E88449500DBBE86 /* AirRegLiveness.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = AirRegLiveness.cpp; path = b3/air/AirRegLiveness.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 0FF4B4BB1E88449500DBBE86 /* AirRegLiveness.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirRegLiveness.h; path = b3/air/AirRegLiveness.h; sourceTree = "<group>"; };
</span><ins>+ 0FF4B4C61E8893BF00DBBE86 /* AirCFG.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirCFG.h; path = b3/air/AirCFG.h; sourceTree = "<group>"; };
+ 0FF4B4C81E889D7800DBBE86 /* B3VariableLiveness.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3VariableLiveness.cpp; path = b3/B3VariableLiveness.cpp; sourceTree = "<group>"; };
+ 0FF4B4C91E889D7800DBBE86 /* B3VariableLiveness.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3VariableLiveness.h; path = b3/B3VariableLiveness.h; sourceTree = "<group>"; };
</ins><span class="cx"> 0FF60ABF16740F8100029779 /* ReduceWhitespace.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ReduceWhitespace.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 0FF60AC016740F8100029779 /* ReduceWhitespace.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ReduceWhitespace.h; sourceTree = "<group>"; };
</span><span class="cx"> 0FF7168A15A3B231008F5DAA /* PropertyOffset.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = PropertyOffset.h; sourceTree = "<group>"; };
</span><span class="lines">@@ -5504,6 +5510,8 @@
</span><span class="cx"> 0FEC84FD1BDACDAC0080FF74 /* B3ValueRep.h */,
</span><span class="cx"> 0F2BBD921C5FF3F50023EF23 /* B3Variable.cpp */,
</span><span class="cx"> 0F2BBD931C5FF3F50023EF23 /* B3Variable.h */,
</span><ins>+ 0FF4B4C81E889D7800DBBE86 /* B3VariableLiveness.cpp */,
+ 0FF4B4C91E889D7800DBBE86 /* B3VariableLiveness.h */,
</ins><span class="cx"> 0F2BBD941C5FF3F50023EF23 /* B3VariableValue.cpp */,
</span><span class="cx"> 0F2BBD951C5FF3F50023EF23 /* B3VariableValue.h */,
</span><span class="cx"> 53D444DD1DAF09A000B92784 /* B3WasmAddressValue.cpp */,
</span><span class="lines">@@ -5538,6 +5546,7 @@
</span><span class="cx"> 0F6183211C45BF070072450B /* AirCCallingConvention.h */,
</span><span class="cx"> 0FEC854E1BDACDC70080FF74 /* AirCCallSpecial.cpp */,
</span><span class="cx"> 0FEC854F1BDACDC70080FF74 /* AirCCallSpecial.h */,
</span><ins>+ 0FF4B4C61E8893BF00DBBE86 /* AirCFG.h */,
</ins><span class="cx"> 0FEC85501BDACDC70080FF74 /* AirCode.cpp */,
</span><span class="cx"> 0FEC85511BDACDC70080FF74 /* AirCode.h */,
</span><span class="cx"> 0F6183221C45BF070072450B /* AirCustom.cpp */,
</span><span class="lines">@@ -8547,6 +8556,7 @@
</span><span class="cx"> BC02E90F0E1839DB000F9297 /* ErrorPrototype.h in Headers */,
</span><span class="cx"> 996B731B1BDA08D100331B84 /* ErrorPrototype.lut.h in Headers */,
</span><span class="cx"> 14AD910C1DCA92940014F9FE /* EvalCodeBlock.h in Headers */,
</span><ins>+ 0FF4B4CB1E889D7E00DBBE86 /* B3VariableLiveness.h in Headers */,
</ins><span class="cx"> 147341D21DC02E2E00AA29BA /* EvalExecutable.h in Headers */,
</span><span class="cx"> A54982041891D0B00081E5B8 /* EventLoop.h in Headers */,
</span><span class="cx"> FE1C0FFD1B193E9800B53FCA /* Exception.h in Headers */,
</span><span class="lines">@@ -8840,6 +8850,7 @@
</span><span class="cx"> BC18C41E0E16F5CD00B34460 /* JSContextRef.h in Headers */,
</span><span class="cx"> A5EA70EE19F5B5C40098F5EC /* JSContextRefInspectorSupport.h in Headers */,
</span><span class="cx"> A5D2E665195E174000A518E7 /* JSContextRefInternal.h in Headers */,
</span><ins>+ 0FF4B4C71E8893C500DBBE86 /* AirCFG.h in Headers */,
</ins><span class="cx"> 148CD1D8108CF902008163C6 /* JSContextRefPrivate.h in Headers */,
</span><span class="cx"> A72028B81797601E0098028C /* JSCTestRunnerUtils.h in Headers */,
</span><span class="cx"> 72AAF7CE1D0D31B3005E60BE /* JSCustomGetterSetterFunction.h in Headers */,
</span><span class="lines">@@ -9964,6 +9975,7 @@
</span><span class="cx"> 795F099D1E03600500BBE37F /* B3Compile.cpp in Sources */,
</span><span class="cx"> 0FEC850D1BDACDAC0080FF74 /* B3Const32Value.cpp in Sources */,
</span><span class="cx"> 0FEC850F1BDACDAC0080FF74 /* B3Const64Value.cpp in Sources */,
</span><ins>+ 0FF4B4CA1E889D7B00DBBE86 /* B3VariableLiveness.cpp in Sources */,
</ins><span class="cx"> 0FEC85111BDACDAC0080FF74 /* B3ConstDoubleValue.cpp in Sources */,
</span><span class="cx"> 43422A621C158E6A00E2EB98 /* B3ConstFloatValue.cpp in Sources */,
</span><span class="cx"> 0F338DF51BE93D550013C88F /* B3ConstrainedValue.cpp in Sources */,
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3BasicBlockh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3BasicBlock.h (214409 => 214410)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3BasicBlock.h 2017-03-26 22:11:13 UTC (rev 214409)
+++ trunk/Source/JavaScriptCore/b3/B3BasicBlock.h 2017-03-27 04:17:52 UTC (rev 214410)
</span><span class="lines">@@ -64,6 +64,13 @@
</span><span class="cx"> size_t size() const { return m_values.size(); }
</span><span class="cx"> Value* at(size_t index) const { return m_values[index]; }
</span><span class="cx"> Value*& at(size_t index) { return m_values[index]; }
</span><ins>+
+ Value* get(size_t index) const
+ {
+ if (index >= size())
+ return nullptr;
+ return at(index);
+ }
</ins><span class="cx">
</span><span class="cx"> Value* last() const { return m_values.last(); }
</span><span class="cx"> Value*& last() { return m_values.last(); }
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3FixSSAcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3FixSSA.cpp (214409 => 214410)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3FixSSA.cpp 2017-03-26 22:11:13 UTC (rev 214409)
+++ trunk/Source/JavaScriptCore/b3/B3FixSSA.cpp 2017-03-27 04:17:52 UTC (rev 214410)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2016 Apple Inc. All rights reserved.
</del><ins>+ * Copyright (C) 2016-2017 Apple Inc. All rights reserved.
</ins><span class="cx"> *
</span><span class="cx"> * Redistribution and use in source and binary forms, with or without
</span><span class="cx"> * modification, are permitted provided that the following conditions
</span><span class="lines">@@ -38,6 +38,7 @@
</span><span class="cx"> #include "B3UpsilonValue.h"
</span><span class="cx"> #include "B3ValueInlines.h"
</span><span class="cx"> #include "B3Variable.h"
</span><ins>+#include "B3VariableLiveness.h"
</ins><span class="cx"> #include "B3VariableValue.h"
</span><span class="cx"> #include <wtf/CommaPrinter.h>
</span><span class="cx"> #include <wtf/IndexSet.h>
</span><span class="lines">@@ -136,7 +137,10 @@
</span><span class="cx">
</span><span class="cx"> // We know that we have variables to optimize, so do that now.
</span><span class="cx"> breakCriticalEdges(proc);
</span><del>-
</del><ins>+
+ VariableLiveness liveness(proc);
+ VariableLiveness::LiveAtHead liveAtHead = liveness.liveAtHead();
+
</ins><span class="cx"> SSACalculator ssa(proc);
</span><span class="cx">
</span><span class="cx"> // Create a SSACalculator::Variable ("calcVar") for every variable.
</span><span class="lines">@@ -167,6 +171,9 @@
</span><span class="cx"> ssa.computePhis(
</span><span class="cx"> [&] (SSACalculator::Variable* calcVar, BasicBlock* block) -> Value* {
</span><span class="cx"> Variable* variable = calcVarToVariable[calcVar->index()];
</span><ins>+ if (!liveAtHead.isLiveAtHead(block, variable))
+ return nullptr;
+
</ins><span class="cx"> Value* phi = proc.add<Value>(Phi, variable->type(), block->at(0)->origin());
</span><span class="cx"> if (verbose) {
</span><span class="cx"> dataLog(
</span><span class="lines">@@ -182,10 +189,8 @@
</span><span class="cx"> for (BasicBlock* block : proc.blocksInPreOrder()) {
</span><span class="cx"> mapping.clear();
</span><span class="cx">
</span><del>- for (unsigned index = calcVarToVariable.size(); index--;) {
- Variable* variable = calcVarToVariable[index];
- SSACalculator::Variable* calcVar = ssa.variable(index);
-
</del><ins>+ for (Variable* variable : liveness.liveAtHead(block)) {
+ SSACalculator::Variable* calcVar = variableToCalcVar[variable];
</ins><span class="cx"> SSACalculator::Def* def = ssa.reachingDefAtHead(block, calcVar);
</span><span class="cx"> if (def)
</span><span class="cx"> mapping[variable] = def->value();
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3VariableLivenesscpp"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/b3/B3VariableLiveness.cpp (0 => 214410)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3VariableLiveness.cpp (rev 0)
+++ trunk/Source/JavaScriptCore/b3/B3VariableLiveness.cpp 2017-03-27 04:17:52 UTC (rev 214410)
</span><span class="lines">@@ -0,0 +1,45 @@
</span><ins>+/*
+ * Copyright (C) 2017 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 "B3VariableLiveness.h"
+
+#if ENABLE(B3_JIT)
+
+namespace JSC { namespace B3 {
+
+VariableLiveness::VariableLiveness(Procedure& proc)
+ : WTF::Liveness<VariableLivenessAdapter>(proc.cfg(), proc)
+{
+}
+
+VariableLiveness::~VariableLiveness()
+{
+}
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3VariableLivenessh"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/b3/B3VariableLiveness.h (0 => 214410)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3VariableLiveness.h (rev 0)
+++ trunk/Source/JavaScriptCore/b3/B3VariableLiveness.h 2017-03-27 04:17:52 UTC (rev 214410)
</span><span class="lines">@@ -0,0 +1,107 @@
</span><ins>+/*
+ * Copyright (C) 2017 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.
+ */
+
+#pragma once
+
+#if ENABLE(B3_JIT)
+
+#include "B3BasicBlock.h"
+#include "B3CFG.h"
+#include "B3Procedure.h"
+#include "B3ValueInlines.h"
+#include "B3Variable.h"
+#include "B3VariableValue.h"
+#include <wtf/Liveness.h>
+
+namespace JSC { namespace B3 {
+
+struct VariableLivenessAdapter {
+ static constexpr const char* name = "VariableLiveness";
+ typedef B3::CFG CFG;
+ typedef Variable* Thing;
+
+ VariableLivenessAdapter(Procedure& proc)
+ : proc(proc)
+ {
+ }
+
+ unsigned numIndices()
+ {
+ return proc.variables().size();
+ }
+
+ static unsigned valueToIndex(Variable* var) { return var->index(); }
+ Variable* indexToValue(unsigned index) { return proc.variables()[index]; }
+
+ unsigned blockSize(BasicBlock* block)
+ {
+ return block->size();
+ }
+
+ template<typename Func>
+ void forEachEarlyUse(BasicBlock* block, unsigned valueIndex, const Func& func)
+ {
+ Value* value = block->get(valueIndex);
+ if (!value)
+ return;
+ if (value->opcode() != Get)
+ return;
+ func(value->as<VariableValue>()->variable()->index());
+ }
+
+ template<typename Func>
+ void forEachLateUse(BasicBlock*, unsigned, const Func&)
+ {
+ }
+
+ template<typename Func>
+ void forEachEarlyDef(BasicBlock*, unsigned, const Func&)
+ {
+ }
+
+ template<typename Func>
+ void forEachLateDef(BasicBlock* block, unsigned valueIndex, const Func& func)
+ {
+ Value* value = block->get(valueIndex);
+ if (!value)
+ return;
+ if (value->opcode() != Set)
+ return;
+ func(value->as<VariableValue>()->variable()->index());
+ }
+
+ Procedure& proc;
+};
+
+class VariableLiveness : public WTF::Liveness<VariableLivenessAdapter> {
+public:
+ VariableLiveness(Procedure&);
+ ~VariableLiveness();
+};
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirCFGh"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/b3/air/AirCFG.h (0 => 214410)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirCFG.h (rev 0)
+++ trunk/Source/JavaScriptCore/b3/air/AirCFG.h 2017-03-27 04:17:52 UTC (rev 214410)
</span><span class="lines">@@ -0,0 +1,76 @@
</span><ins>+/*
+ * Copyright (C) 2017 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.
+ */
+
+#pragma once
+
+#if ENABLE(B3_JIT)
+
+#include "AirBasicBlock.h"
+#include "AirCode.h"
+#include <wtf/IndexMap.h>
+#include <wtf/IndexSet.h>
+
+namespace JSC { namespace B3 { namespace Air {
+
+class CFG {
+ WTF_MAKE_NONCOPYABLE(CFG);
+ WTF_MAKE_FAST_ALLOCATED;
+public:
+ typedef BasicBlock* Node;
+ typedef IndexSet<BasicBlock> Set;
+ template<typename T> using Map = IndexMap<BasicBlock, T>;
+ typedef Vector<BasicBlock*, 4> List;
+
+ CFG(Code& code)
+ : m_code(code)
+ {
+ }
+
+ Node root() { return m_code[0]; }
+
+ template<typename T>
+ Map<T> newMap() { return IndexMap<JSC::B3::Air::BasicBlock, T>(m_code.size()); }
+
+ SuccessorCollection<BasicBlock, BasicBlock::SuccessorList> successors(Node node) { return node->successorBlocks(); }
+ BasicBlock::PredecessorList& predecessors(Node node) { return node->predecessors(); }
+
+ unsigned index(Node node) const { return node->index(); }
+ Node node(unsigned index) const { return m_code[index]; }
+ unsigned numNodes() const { return m_code.size(); }
+
+ PointerDump<BasicBlock> dump(Node node) const { return pointerDump(node); }
+
+ void dump(PrintStream& out) const
+ {
+ m_code.dump(out);
+ }
+
+private:
+ Code& m_code;
+};
+
+} } } // namespace JSC::B3::Air
+
+#endif // ENABLE(B3_JIT)
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirCodecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirCode.cpp (214409 => 214410)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirCode.cpp 2017-03-26 22:11:13 UTC (rev 214409)
+++ trunk/Source/JavaScriptCore/b3/air/AirCode.cpp 2017-03-27 04:17:52 UTC (rev 214410)
</span><span class="lines">@@ -29,6 +29,7 @@
</span><span class="cx"> #if ENABLE(B3_JIT)
</span><span class="cx">
</span><span class="cx"> #include "AirCCallSpecial.h"
</span><ins>+#include "AirCFG.h"
</ins><span class="cx"> #include "B3BasicBlockUtils.h"
</span><span class="cx"> #include "B3Procedure.h"
</span><span class="cx"> #include "B3StackSlot.h"
</span><span class="lines">@@ -38,6 +39,7 @@
</span><span class="cx">
</span><span class="cx"> Code::Code(Procedure& proc)
</span><span class="cx"> : m_proc(proc)
</span><ins>+ , m_cfg(new CFG(*this))
</ins><span class="cx"> , m_lastPhaseName("initial")
</span><span class="cx"> {
</span><span class="cx"> // Come up with initial orderings of registers. The user may replace this with something else.
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirCodeh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirCode.h (214409 => 214410)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirCode.h 2017-03-26 22:11:13 UTC (rev 214409)
+++ trunk/Source/JavaScriptCore/b3/air/AirCode.h 2017-03-27 04:17:52 UTC (rev 214410)
</span><span class="lines">@@ -52,6 +52,7 @@
</span><span class="cx">
</span><span class="cx"> class BlockInsertionSet;
</span><span class="cx"> class CCallSpecial;
</span><ins>+class CFG;
</ins><span class="cx"> class Disassembler;
</span><span class="cx">
</span><span class="cx"> typedef void WasmBoundsCheckGeneratorFunction(CCallHelpers&, GPRReg, unsigned);
</span><span class="lines">@@ -176,7 +177,7 @@
</span><span class="cx">
</span><span class="cx"> // Recomputes predecessors and deletes unreachable blocks.
</span><span class="cx"> void resetReachability();
</span><del>-
</del><ins>+
</ins><span class="cx"> JS_EXPORT_PRIVATE void dump(PrintStream&) const;
</span><span class="cx">
</span><span class="cx"> unsigned size() const { return m_blocks.size(); }
</span><span class="lines">@@ -256,6 +257,8 @@
</span><span class="cx"> void addFastTmp(Tmp);
</span><span class="cx"> bool isFastTmp(Tmp tmp) const { return m_fastTmps.contains(tmp); }
</span><span class="cx">
</span><ins>+ CFG& cfg() const { return *m_cfg; }
+
</ins><span class="cx"> void* addDataSection(size_t);
</span><span class="cx">
</span><span class="cx"> // The name has to be a string literal, since we don't do any memory management for the string.
</span><span class="lines">@@ -304,6 +307,7 @@
</span><span class="cx"> SparseCollection<StackSlot> m_stackSlots;
</span><span class="cx"> Vector<std::unique_ptr<BasicBlock>> m_blocks;
</span><span class="cx"> SparseCollection<Special> m_specials;
</span><ins>+ std::unique_ptr<CFG> m_cfg;
</ins><span class="cx"> HashSet<Tmp> m_fastTmps;
</span><span class="cx"> CCallSpecial* m_cCallSpecial { nullptr };
</span><span class="cx"> unsigned m_numGPTmps { 0 };
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirLivenessh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirLiveness.h (214409 => 214410)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirLiveness.h 2017-03-26 22:11:13 UTC (rev 214409)
+++ trunk/Source/JavaScriptCore/b3/air/AirLiveness.h 2017-03-27 04:17:52 UTC (rev 214410)
</span><span class="lines">@@ -28,27 +28,107 @@
</span><span class="cx"> #if ENABLE(B3_JIT)
</span><span class="cx">
</span><span class="cx"> #include "AirBasicBlock.h"
</span><ins>+#include "AirCFG.h"
</ins><span class="cx"> #include "AirCode.h"
</span><span class="cx"> #include "AirInstInlines.h"
</span><span class="cx"> #include "AirStackSlot.h"
</span><span class="cx"> #include "AirTmpInlines.h"
</span><del>-#include "B3TimingScope.h"
-#include <wtf/IndexMap.h>
-#include <wtf/IndexSparseSet.h>
-#include <wtf/ListDump.h>
</del><ins>+#include <wtf/Liveness.h>
</ins><span class="cx">
</span><span class="cx"> namespace JSC { namespace B3 { namespace Air {
</span><span class="cx">
</span><ins>+template<typename Adapter>
+struct LivenessAdapter {
+ typedef Air::CFG CFG;
+
+ LivenessAdapter(Code& code)
+ : code(code)
+ {
+ }
+
+ unsigned blockSize(BasicBlock* block)
+ {
+ return block->size();
+ }
+
+ template<typename Func>
+ void forEachEarlyUse(BasicBlock* block, unsigned instIndex, const Func& func)
+ {
+ Inst* inst = block->get(instIndex);
+ if (!inst)
+ return;
+ inst->forEach<typename Adapter::Thing>(
+ [&] (typename Adapter::Thing& thing, Arg::Role role, Bank bank, Width) {
+ if (Arg::isEarlyUse(role)
+ && Adapter::acceptsBank(bank)
+ && Adapter::acceptsRole(role))
+ func(Adapter::valueToIndex(thing));
+ });
+ }
+
+ template<typename Func>
+ void forEachLateUse(BasicBlock* block, unsigned instIndex, const Func& func)
+ {
+ Inst* inst = block->get(instIndex);
+ if (!inst)
+ return;
+ inst->forEach<typename Adapter::Thing>(
+ [&] (typename Adapter::Thing& thing, Arg::Role role, Bank bank, Width) {
+ if (Arg::isLateUse(role)
+ && Adapter::acceptsBank(bank)
+ && Adapter::acceptsRole(role))
+ func(Adapter::valueToIndex(thing));
+ });
+ }
+
+ template<typename Func>
+ void forEachEarlyDef(BasicBlock* block, unsigned instIndex, const Func& func)
+ {
+ Inst* inst = block->get(instIndex);
+ if (!inst)
+ return;
+ inst->forEach<typename Adapter::Thing>(
+ [&] (typename Adapter::Thing& thing, Arg::Role role, Bank bank, Width) {
+ if (Arg::isEarlyDef(role)
+ && Adapter::acceptsBank(bank)
+ && Adapter::acceptsRole(role))
+ func(Adapter::valueToIndex(thing));
+ });
+ }
+
+ template<typename Func>
+ void forEachLateDef(BasicBlock* block, unsigned instIndex, const Func& func)
+ {
+ Inst* inst = block->get(instIndex);
+ if (!inst)
+ return;
+ inst->forEach<typename Adapter::Thing>(
+ [&] (typename Adapter::Thing& thing, Arg::Role role, Bank bank, Width) {
+ if (Arg::isLateDef(role)
+ && Adapter::acceptsBank(bank)
+ && Adapter::acceptsRole(role))
+ func(Adapter::valueToIndex(thing));
+ });
+ }
+
+ Code& code;
+};
+
</ins><span class="cx"> template<Bank adapterBank, Arg::Temperature minimumTemperature = Arg::Cold>
</span><del>-struct TmpLivenessAdapter {
</del><ins>+struct TmpLivenessAdapter : LivenessAdapter<TmpLivenessAdapter<adapterBank, minimumTemperature>> {
+ typedef LivenessAdapter<TmpLivenessAdapter<adapterBank, minimumTemperature>> Base;
+
</ins><span class="cx"> static constexpr const char* name = "TmpLiveness";
</span><span class="cx"> typedef Tmp Thing;
</span><span class="cx">
</span><del>- TmpLivenessAdapter(Code&) { }
</del><ins>+ TmpLivenessAdapter(Code& code)
+ : Base(code)
+ {
+ }
</ins><span class="cx">
</span><del>- static unsigned numIndices(Code& code)
</del><ins>+ unsigned numIndices()
</ins><span class="cx"> {
</span><del>- unsigned numTmps = code.numTmps(adapterBank);
</del><ins>+ unsigned numTmps = Base::code.numTmps(adapterBank);
</ins><span class="cx"> return AbsoluteTmpMapper<adapterBank>::absoluteIndex(numTmps);
</span><span class="cx"> }
</span><span class="cx"> static bool acceptsBank(Bank bank) { return bank == adapterBank; }
</span><span class="lines">@@ -57,16 +137,16 @@
</span><span class="cx"> static Tmp indexToValue(unsigned index) { return AbsoluteTmpMapper<adapterBank>::tmpFromAbsoluteIndex(index); }
</span><span class="cx"> };
</span><span class="cx">
</span><del>-struct StackSlotLivenessAdapter {
</del><ins>+struct StackSlotLivenessAdapter : LivenessAdapter<StackSlotLivenessAdapter> {
</ins><span class="cx"> static constexpr const char* name = "StackSlotLiveness";
</span><span class="cx"> typedef StackSlot* Thing;
</span><span class="cx">
</span><span class="cx"> StackSlotLivenessAdapter(Code& code)
</span><del>- : m_code(code)
</del><ins>+ : LivenessAdapter(code)
</ins><span class="cx"> {
</span><span class="cx"> }
</span><span class="cx">
</span><del>- static unsigned numIndices(Code& code)
</del><ins>+ unsigned numIndices()
</ins><span class="cx"> {
</span><span class="cx"> return code.stackSlots().size();
</span><span class="cx"> }
</span><span class="lines">@@ -73,336 +153,16 @@
</span><span class="cx"> static bool acceptsBank(Bank) { return true; }
</span><span class="cx"> static bool acceptsRole(Arg::Role) { return true; }
</span><span class="cx"> static unsigned valueToIndex(StackSlot* stackSlot) { return stackSlot->index(); }
</span><del>- StackSlot* indexToValue(unsigned index) { return m_code.stackSlots()[index]; }
-
-private:
- Code& m_code;
</del><ins>+ StackSlot* indexToValue(unsigned index) { return code.stackSlots()[index]; }
</ins><span class="cx"> };
</span><span class="cx">
</span><del>-// HEADS UP: The algorithm here is duplicated in AirRegLiveness.h.
</del><span class="cx"> template<typename Adapter>
</span><del>-class Liveness : public Adapter {
- struct Workset;
</del><ins>+class Liveness : public WTF::Liveness<Adapter> {
</ins><span class="cx"> public:
</span><del>- typedef typename Adapter::Thing Thing;
- typedef Vector<unsigned, 4, UnsafeVectorOverflow> IndexVector;
-
</del><span class="cx"> Liveness(Code& code)
</span><del>- : Adapter(code)
- , m_workset(Adapter::numIndices(code))
- , m_liveAtHead(code.size())
- , m_liveAtTail(code.size())
</del><ins>+ : WTF::Liveness<Adapter>(code.cfg(), code)
</ins><span class="cx"> {
</span><del>- TimingScope timingScope(Adapter::name);
-
- // The liveAtTail of each block automatically contains the LateUse's of the terminal.
- for (BasicBlock* block : code) {
- IndexVector& liveAtTail = m_liveAtTail[block];
-
- block->last().forEach<typename Adapter::Thing>(
- [&] (typename Adapter::Thing& thing, Arg::Role role, Bank bank, Width) {
- if (Arg::isLateUse(role)
- && Adapter::acceptsBank(bank)
- && Adapter::acceptsRole(role))
- liveAtTail.append(Adapter::valueToIndex(thing));
- });
-
- std::sort(liveAtTail.begin(), liveAtTail.end());
- removeRepeatedElements(liveAtTail);
- }
-
- // Blocks with new live values at tail.
- BitVector dirtyBlocks;
- for (size_t blockIndex = code.size(); blockIndex--;)
- dirtyBlocks.set(blockIndex);
-
- IndexVector mergeBuffer;
-
- bool changed;
- do {
- changed = false;
-
- for (size_t blockIndex = code.size(); blockIndex--;) {
- BasicBlock* block = code[blockIndex];
- if (!block)
- continue;
-
- if (!dirtyBlocks.quickClear(blockIndex))
- continue;
-
- LocalCalc localCalc(*this, block);
- for (size_t instIndex = block->size(); instIndex--;)
- localCalc.execute(instIndex);
-
- // Handle the early def's of the first instruction.
- block->at(0).forEach<typename Adapter::Thing>(
- [&] (typename Adapter::Thing& thing, Arg::Role role, Bank bank, Width) {
- if (Arg::isEarlyDef(role)
- && Adapter::acceptsBank(bank)
- && Adapter::acceptsRole(role))
- m_workset.remove(Adapter::valueToIndex(thing));
- });
-
- IndexVector& liveAtHead = m_liveAtHead[block];
-
- // We only care about Tmps that were discovered in this iteration. It is impossible
- // to remove a live value from the head.
- // We remove all the values we already knew about so that we only have to deal with
- // what is new in LiveAtHead.
- if (m_workset.size() == liveAtHead.size())
- m_workset.clear();
- else {
- for (unsigned liveIndexAtHead : liveAtHead)
- m_workset.remove(liveIndexAtHead);
- }
-
- if (m_workset.isEmpty())
- continue;
-
- liveAtHead.reserveCapacity(liveAtHead.size() + m_workset.size());
- for (unsigned newValue : m_workset)
- liveAtHead.uncheckedAppend(newValue);
-
- m_workset.sort();
-
- for (BasicBlock* predecessor : block->predecessors()) {
- IndexVector& liveAtTail = m_liveAtTail[predecessor];
-
- if (liveAtTail.isEmpty())
- liveAtTail = m_workset.values();
- else {
- mergeBuffer.resize(0);
- mergeBuffer.reserveCapacity(liveAtTail.size() + m_workset.size());
- auto iter = mergeDeduplicatedSorted(
- liveAtTail.begin(), liveAtTail.end(),
- m_workset.begin(), m_workset.end(),
- mergeBuffer.begin());
- mergeBuffer.resize(iter - mergeBuffer.begin());
-
- if (mergeBuffer.size() == liveAtTail.size())
- continue;
-
- RELEASE_ASSERT(mergeBuffer.size() > liveAtTail.size());
- liveAtTail = mergeBuffer;
- }
-
- dirtyBlocks.quickSet(predecessor->index());
- changed = true;
- }
- }
- } while (changed);
</del><span class="cx"> }
</span><del>-
- // This calculator has to be run in reverse.
- class LocalCalc {
- public:
- LocalCalc(Liveness& liveness, BasicBlock* block)
- : m_liveness(liveness)
- , m_block(block)
- {
- auto& workset = liveness.m_workset;
- workset.clear();
- IndexVector& liveAtTail = liveness.m_liveAtTail[block];
- for (unsigned index : liveAtTail)
- workset.add(index);
- }
-
- class Iterable {
- public:
- Iterable(Liveness& liveness)
- : m_liveness(liveness)
- {
- }
-
- class iterator {
- public:
- iterator(Adapter& adapter, IndexSparseSet<UnsafeVectorOverflow>::const_iterator sparceSetIterator)
- : m_adapter(adapter)
- , m_sparceSetIterator(sparceSetIterator)
- {
- }
-
- iterator& operator++()
- {
- ++m_sparceSetIterator;
- return *this;
- }
-
- typename Adapter::Thing operator*() const
- {
- return m_adapter.indexToValue(*m_sparceSetIterator);
- }
-
- bool operator==(const iterator& other) { return m_sparceSetIterator == other.m_sparceSetIterator; }
- bool operator!=(const iterator& other) { return m_sparceSetIterator != other.m_sparceSetIterator; }
-
- private:
- Adapter& m_adapter;
- IndexSparseSet<UnsafeVectorOverflow>::const_iterator m_sparceSetIterator;
- };
-
- iterator begin() const { return iterator(m_liveness, m_liveness.m_workset.begin()); }
- iterator end() const { return iterator(m_liveness, m_liveness.m_workset.end()); }
-
- bool contains(const typename Adapter::Thing& thing) const
- {
- return m_liveness.m_workset.contains(Adapter::valueToIndex(thing));
- }
-
- private:
- Liveness& m_liveness;
- };
-
- Iterable live() const
- {
- return Iterable(m_liveness);
- }
-
- bool isLive(const typename Adapter::Thing& thing) const
- {
- return live().contains(thing);
- }
-
- void execute(unsigned instIndex)
- {
- Inst& inst = m_block->at(instIndex);
- auto& workset = m_liveness.m_workset;
-
- // First handle the early def's of the next instruction.
- if (instIndex + 1 < m_block->size()) {
- Inst& nextInst = m_block->at(instIndex + 1);
- nextInst.forEach<typename Adapter::Thing>(
- [&] (typename Adapter::Thing& thing, Arg::Role role, Bank bank, Width) {
- if (Arg::isEarlyDef(role)
- && Adapter::acceptsBank(bank)
- && Adapter::acceptsRole(role))
- workset.remove(Adapter::valueToIndex(thing));
- });
- }
-
- // Then handle def's.
- inst.forEach<typename Adapter::Thing>(
- [&] (typename Adapter::Thing& thing, Arg::Role role, Bank bank, Width) {
- if (Arg::isLateDef(role)
- && Adapter::acceptsBank(bank)
- && Adapter::acceptsRole(role))
- workset.remove(Adapter::valueToIndex(thing));
- });
-
- // Then handle use's.
- inst.forEach<typename Adapter::Thing>(
- [&] (typename Adapter::Thing& thing, Arg::Role role, Bank bank, Width) {
- if (Arg::isEarlyUse(role)
- && Adapter::acceptsBank(bank)
- && Adapter::acceptsRole(role))
- workset.add(Adapter::valueToIndex(thing));
- });
-
- // And finally, handle the late use's of the previous instruction.
- if (instIndex) {
- Inst& prevInst = m_block->at(instIndex - 1);
- prevInst.forEach<typename Adapter::Thing>(
- [&] (typename Adapter::Thing& thing, Arg::Role role, Bank bank, Width) {
- if (Arg::isLateUse(role)
- && Adapter::acceptsBank(bank)
- && Adapter::acceptsRole(role))
- workset.add(Adapter::valueToIndex(thing));
- });
- }
- }
-
- private:
- Liveness& m_liveness;
- BasicBlock* m_block;
- };
-
- const IndexVector& rawLiveAtHead(BasicBlock* block)
- {
- return m_liveAtHead[block];
- }
-
- template<typename UnderlyingIterable>
- class Iterable {
- public:
- Iterable(Liveness& liveness, const UnderlyingIterable& iterable)
- : m_liveness(liveness)
- , m_iterable(iterable)
- {
- }
-
- class iterator {
- public:
- iterator()
- : m_liveness(nullptr)
- , m_iter()
- {
- }
-
- iterator(Liveness& liveness, typename UnderlyingIterable::const_iterator iter)
- : m_liveness(&liveness)
- , m_iter(iter)
- {
- }
-
- typename Adapter::Thing operator*()
- {
- return m_liveness->indexToValue(*m_iter);
- }
-
- iterator& operator++()
- {
- ++m_iter;
- return *this;
- }
-
- bool operator==(const iterator& other) const
- {
- ASSERT(m_liveness == other.m_liveness);
- return m_iter == other.m_iter;
- }
-
- bool operator!=(const iterator& other) const
- {
- return !(*this == other);
- }
-
- private:
- Liveness* m_liveness;
- typename UnderlyingIterable::const_iterator m_iter;
- };
-
- iterator begin() const { return iterator(m_liveness, m_iterable.begin()); }
- iterator end() const { return iterator(m_liveness, m_iterable.end()); }
-
- bool contains(const typename Adapter::Thing& thing) const
- {
- return m_liveness.m_workset.contains(Adapter::valueToIndex(thing));
- }
-
- private:
- Liveness& m_liveness;
- const UnderlyingIterable& m_iterable;
- };
-
- Iterable<IndexVector> liveAtHead(BasicBlock* block)
- {
- return Iterable<IndexVector>(*this, m_liveAtHead[block]);
- }
-
- Iterable<IndexVector> liveAtTail(BasicBlock* block)
- {
- return Iterable<IndexVector>(*this, m_liveAtTail[block]);
- }
-
- IndexSparseSet<UnsafeVectorOverflow>& workset() { return m_workset; }
-
-private:
- friend class LocalCalc;
- friend class LocalCalc::Iterable;
-
- IndexSparseSet<UnsafeVectorOverflow> m_workset;
- IndexMap<BasicBlock, IndexVector> m_liveAtHead;
- IndexMap<BasicBlock, IndexVector> m_liveAtTail;
</del><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> template<Bank bank, Arg::Temperature minimumTemperature = Arg::Cold>
</span></span></pre></div>
<a id="trunkSourceWTFChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/ChangeLog (214409 => 214410)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/ChangeLog 2017-03-26 22:11:13 UTC (rev 214409)
+++ trunk/Source/WTF/ChangeLog 2017-03-27 04:17:52 UTC (rev 214410)
</span><span class="lines">@@ -1,3 +1,56 @@
</span><ins>+2017-03-26 Filip Pizlo <fpizlo@apple.com>
+
+ B3::fixSSA should do liveness pruning
+ https://bugs.webkit.org/show_bug.cgi?id=170111
+
+ Reviewed by Saam Barati.
+
+ Move Air::Liveness<> to WTF::Liveness<>. This is pretty easy since Air::Liveness<> was
+ already fairly generic. It leverages the CFG concept so that it can understand many
+ different kinds of basic blocks. It doesn't try to understand the contents of basic
+ blocks; it just asks the adaptor for the block size and asks for the early/late
+ uses/defs of each thing in the block.
+
+ This makes it easy to create a B3::VariableLiveness, which fixSSA then uses for
+ pruning. One of the new features is the Liveness::LiveAtHead nested class, which you
+ instantiate if you want to perform liveAtHead queries, which SSA construction wants to
+ do.
+
+ This also fixes https://bugs.webkit.org/show_bug.cgi?id=170102#c12
+
+ * WTF.xcodeproj/project.pbxproj:
+ * wtf/CMakeLists.txt:
+ * wtf/Liveness.h: Added.
+ (WTF::Liveness::Liveness):
+ (WTF::Liveness::LocalCalc::LocalCalc):
+ (WTF::Liveness::LocalCalc::Iterable::Iterable):
+ (WTF::Liveness::LocalCalc::Iterable::iterator::iterator):
+ (WTF::Liveness::LocalCalc::Iterable::iterator::operator++):
+ (WTF::Liveness::LocalCalc::Iterable::iterator::operator*):
+ (WTF::Liveness::LocalCalc::Iterable::iterator::operator==):
+ (WTF::Liveness::LocalCalc::Iterable::iterator::operator!=):
+ (WTF::Liveness::LocalCalc::Iterable::begin):
+ (WTF::Liveness::LocalCalc::Iterable::end):
+ (WTF::Liveness::LocalCalc::Iterable::contains):
+ (WTF::Liveness::LocalCalc::live):
+ (WTF::Liveness::LocalCalc::isLive):
+ (WTF::Liveness::LocalCalc::execute):
+ (WTF::Liveness::rawLiveAtHead):
+ (WTF::Liveness::Iterable::Iterable):
+ (WTF::Liveness::Iterable::iterator::iterator):
+ (WTF::Liveness::Iterable::iterator::operator*):
+ (WTF::Liveness::Iterable::iterator::operator++):
+ (WTF::Liveness::Iterable::iterator::operator==):
+ (WTF::Liveness::Iterable::iterator::operator!=):
+ (WTF::Liveness::Iterable::begin):
+ (WTF::Liveness::Iterable::end):
+ (WTF::Liveness::Iterable::contains):
+ (WTF::Liveness::liveAtHead):
+ (WTF::Liveness::liveAtTail):
+ (WTF::Liveness::workset):
+ (WTF::Liveness::LiveAtHead::LiveAtHead):
+ (WTF::Liveness::LiveAtHead::isLiveAtHead):
+
</ins><span class="cx"> 2017-03-25 Filip Pizlo <fpizlo@apple.com>
</span><span class="cx">
</span><span class="cx"> Air::Liveness shouldn't need HashSets
</span></span></pre></div>
<a id="trunkSourceWTFWTFxcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/WTF.xcodeproj/project.pbxproj (214409 => 214410)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2017-03-26 22:11:13 UTC (rev 214409)
+++ trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2017-03-27 04:17:52 UTC (rev 214410)
</span><span class="lines">@@ -82,6 +82,7 @@
</span><span class="cx"> 0FEC84AF1BD825310080FF74 /* GraphNodeWorklist.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEC84AE1BD825310080FF74 /* GraphNodeWorklist.h */; };
</span><span class="cx"> 0FEC84B11BDACD390080FF74 /* ScopedLambda.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEC84B01BDACD390080FF74 /* ScopedLambda.h */; };
</span><span class="cx"> 0FED67B61B22D4D80066CE15 /* TinyPtrSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FED67B51B22D4D80066CE15 /* TinyPtrSet.h */; };
</span><ins>+ 0FF4B4C51E88939C00DBBE86 /* Liveness.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FF4B4C41E88939C00DBBE86 /* Liveness.h */; };
</ins><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="cx"> 0FFF19DD1BB334EB00886D91 /* ParallelHelperPool.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FFF19DB1BB334EB00886D91 /* ParallelHelperPool.h */; };
</span><span class="lines">@@ -467,6 +468,7 @@
</span><span class="cx"> 0FEC84AE1BD825310080FF74 /* GraphNodeWorklist.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = GraphNodeWorklist.h; sourceTree = "<group>"; };
</span><span class="cx"> 0FEC84B01BDACD390080FF74 /* ScopedLambda.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ScopedLambda.h; sourceTree = "<group>"; };
</span><span class="cx"> 0FED67B51B22D4D80066CE15 /* TinyPtrSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = TinyPtrSet.h; sourceTree = "<group>"; };
</span><ins>+ 0FF4B4C41E88939C00DBBE86 /* Liveness.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Liveness.h; sourceTree = "<group>"; };
</ins><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="cx"> 0FFF19DB1BB334EB00886D91 /* ParallelHelperPool.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ParallelHelperPool.h; sourceTree = "<group>"; };
</span><span class="lines">@@ -1027,6 +1029,7 @@
</span><span class="cx"> 539EB0621D55284200C82EF7 /* LEBDecoder.h */,
</span><span class="cx"> A70DA0831799F04D00529A9B /* ListDump.h */,
</span><span class="cx"> A8A472C1151A825A004123FF /* ListHashSet.h */,
</span><ins>+ 0FF4B4C41E88939C00DBBE86 /* Liveness.h */,
</ins><span class="cx"> 0FE164681B6FFC9600400E7C /* Lock.cpp */,
</span><span class="cx"> 0FE164691B6FFC9600400E7C /* Lock.h */,
</span><span class="cx"> 0F0FCDDD1DD167F900CCAB53 /* LockAlgorithm.h */,
</span><span class="lines">@@ -1390,6 +1393,7 @@
</span><span class="cx"> 9BD8F40B176C2B470002D865 /* AtomicStringTable.h in Headers */,
</span><span class="cx"> 1469419C16EAB10A0024E146 /* AutodrainedPool.h in Headers */,
</span><span class="cx"> 0F43D8F21DB5ADDC00108FB6 /* AutomaticThread.h in Headers */,
</span><ins>+ 0FF4B4C51E88939C00DBBE86 /* Liveness.h in Headers */,
</ins><span class="cx"> DCEE22051CEB9869000C2396 /* BackwardsGraph.h in Headers */,
</span><span class="cx"> 0FB14E19180FA218009B6B4D /* Bag.h in Headers */,
</span><span class="cx"> 0FB14E1B1810E1DC009B6B4D /* BagToHashMap.h in Headers */,
</span></span></pre></div>
<a id="trunkSourceWTFwtfCMakeListstxt"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/CMakeLists.txt (214409 => 214410)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/CMakeLists.txt 2017-03-26 22:11:13 UTC (rev 214409)
+++ trunk/Source/WTF/wtf/CMakeLists.txt 2017-03-27 04:17:52 UTC (rev 214410)
</span><span class="lines">@@ -57,6 +57,7 @@
</span><span class="cx"> IteratorAdaptors.h
</span><span class="cx"> IteratorRange.h
</span><span class="cx"> ListHashSet.h
</span><ins>+ Liveness.h
</ins><span class="cx"> Lock.h
</span><span class="cx"> LockAlgorithm.h
</span><span class="cx"> LockedPrintStream.h
</span></span></pre></div>
<a id="trunkSourceWTFwtfLivenessh"></a>
<div class="addfile"><h4>Added: trunk/Source/WTF/wtf/Liveness.h (0 => 214410)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/Liveness.h (rev 0)
+++ trunk/Source/WTF/wtf/Liveness.h 2017-03-27 04:17:52 UTC (rev 214410)
</span><span class="lines">@@ -0,0 +1,373 @@
</span><ins>+/*
+ * Copyright (C) 2015-2017 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.
+ */
+
+#pragma once
+
+#include <wtf/BitVector.h>
+#include <wtf/IndexSparseSet.h>
+#include <wtf/ListDump.h>
+#include <wtf/StdLibExtras.h>
+
+namespace WTF {
+
+// HEADS UP: The algorithm here is duplicated in AirRegLiveness.h. That one uses sets rather
+// than fancy vectors, because that's better for register liveness analysis.
+template<typename Adapter>
+class Liveness : public Adapter {
+public:
+ typedef typename Adapter::CFG CFG;
+ typedef typename Adapter::Thing Thing;
+ typedef Vector<unsigned, 4, UnsafeVectorOverflow> IndexVector;
+
+ template<typename... Arguments>
+ Liveness(CFG& cfg, Arguments&&... arguments)
+ : Adapter(std::forward<Arguments>(arguments)...)
+ , m_cfg(cfg)
+ , m_workset(Adapter::numIndices())
+ , m_liveAtHead(cfg.template newMap<IndexVector>())
+ , m_liveAtTail(cfg.template newMap<IndexVector>())
+ {
+ // The liveAtTail of each block automatically contains the LateUse's of the terminal.
+ for (unsigned blockIndex = m_cfg.numNodes(); blockIndex--;) {
+ typename CFG::Node block = m_cfg.node(blockIndex);
+ if (!block)
+ continue;
+
+ IndexVector& liveAtTail = m_liveAtTail[block];
+
+ Adapter::forEachLateUse(
+ block, Adapter::blockSize(block) - 1,
+ [&] (unsigned index) {
+ liveAtTail.append(index);
+ });
+
+ std::sort(liveAtTail.begin(), liveAtTail.end());
+ removeRepeatedElements(liveAtTail);
+ }
+
+ // Blocks with new live values at tail.
+ BitVector dirtyBlocks;
+ for (size_t blockIndex = m_cfg.numNodes(); blockIndex--;)
+ dirtyBlocks.set(blockIndex);
+
+ IndexVector mergeBuffer;
+
+ bool changed;
+ do {
+ changed = false;
+
+ for (size_t blockIndex = m_cfg.numNodes(); blockIndex--;) {
+ typename CFG::Node block = m_cfg.node(blockIndex);
+ if (!block)
+ continue;
+
+ if (!dirtyBlocks.quickClear(blockIndex))
+ continue;
+
+ LocalCalc localCalc(*this, block);
+ for (size_t instIndex = Adapter::blockSize(block); instIndex--;)
+ localCalc.execute(instIndex);
+
+ // Handle the early def's of the first instruction.
+ Adapter::forEachEarlyDef(
+ block, 0,
+ [&] (unsigned index) {
+ m_workset.remove(index);
+ });
+
+ IndexVector& liveAtHead = m_liveAtHead[block];
+
+ // We only care about Tmps that were discovered in this iteration. It is impossible
+ // to remove a live value from the head.
+ // We remove all the values we already knew about so that we only have to deal with
+ // what is new in LiveAtHead.
+ if (m_workset.size() == liveAtHead.size())
+ m_workset.clear();
+ else {
+ for (unsigned liveIndexAtHead : liveAtHead)
+ m_workset.remove(liveIndexAtHead);
+ }
+
+ if (m_workset.isEmpty())
+ continue;
+
+ liveAtHead.reserveCapacity(liveAtHead.size() + m_workset.size());
+ for (unsigned newValue : m_workset)
+ liveAtHead.uncheckedAppend(newValue);
+
+ m_workset.sort();
+
+ for (typename CFG::Node predecessor : m_cfg.predecessors(block)) {
+ IndexVector& liveAtTail = m_liveAtTail[predecessor];
+
+ if (liveAtTail.isEmpty())
+ liveAtTail = m_workset.values();
+ else {
+ mergeBuffer.resize(liveAtTail.size() + m_workset.size());
+ auto iter = mergeDeduplicatedSorted(
+ liveAtTail.begin(), liveAtTail.end(),
+ m_workset.begin(), m_workset.end(),
+ mergeBuffer.begin());
+ mergeBuffer.resize(iter - mergeBuffer.begin());
+
+ if (mergeBuffer.size() == liveAtTail.size())
+ continue;
+
+ RELEASE_ASSERT(mergeBuffer.size() > liveAtTail.size());
+ liveAtTail = mergeBuffer;
+ }
+
+ dirtyBlocks.quickSet(predecessor->index());
+ changed = true;
+ }
+ }
+ } while (changed);
+ }
+
+ // This calculator has to be run in reverse.
+ class LocalCalc {
+ public:
+ LocalCalc(Liveness& liveness, typename CFG::Node block)
+ : m_liveness(liveness)
+ , m_block(block)
+ {
+ auto& workset = liveness.m_workset;
+ workset.clear();
+ IndexVector& liveAtTail = liveness.m_liveAtTail[block];
+ for (unsigned index : liveAtTail)
+ workset.add(index);
+ }
+
+ class Iterable {
+ public:
+ Iterable(Liveness& liveness)
+ : m_liveness(liveness)
+ {
+ }
+
+ class iterator {
+ public:
+ iterator(Adapter& adapter, IndexSparseSet<UnsafeVectorOverflow>::const_iterator sparceSetIterator)
+ : m_adapter(adapter)
+ , m_sparceSetIterator(sparceSetIterator)
+ {
+ }
+
+ iterator& operator++()
+ {
+ ++m_sparceSetIterator;
+ return *this;
+ }
+
+ typename Adapter::Thing operator*() const
+ {
+ return m_adapter.indexToValue(*m_sparceSetIterator);
+ }
+
+ bool operator==(const iterator& other) { return m_sparceSetIterator == other.m_sparceSetIterator; }
+ bool operator!=(const iterator& other) { return m_sparceSetIterator != other.m_sparceSetIterator; }
+
+ private:
+ Adapter& m_adapter;
+ IndexSparseSet<UnsafeVectorOverflow>::const_iterator m_sparceSetIterator;
+ };
+
+ iterator begin() const { return iterator(m_liveness, m_liveness.m_workset.begin()); }
+ iterator end() const { return iterator(m_liveness, m_liveness.m_workset.end()); }
+
+ bool contains(const typename Adapter::Thing& thing) const
+ {
+ return m_liveness.m_workset.contains(Adapter::valueToIndex(thing));
+ }
+
+ private:
+ Liveness& m_liveness;
+ };
+
+ Iterable live() const
+ {
+ return Iterable(m_liveness);
+ }
+
+ bool isLive(const typename Adapter::Thing& thing) const
+ {
+ return live().contains(thing);
+ }
+
+ void execute(unsigned instIndex)
+ {
+ auto& workset = m_liveness.m_workset;
+
+ // First handle the early def's of the next instruction.
+ m_liveness.forEachEarlyDef(
+ m_block, instIndex + 1,
+ [&] (unsigned index) {
+ workset.remove(index);
+ });
+
+ // Then handle def's.
+ m_liveness.forEachLateDef(
+ m_block, instIndex,
+ [&] (unsigned index) {
+ workset.remove(index);
+ });
+
+ // Then handle use's.
+ m_liveness.forEachEarlyUse(
+ m_block, instIndex,
+ [&] (unsigned index) {
+ workset.add(index);
+ });
+
+ // And finally, handle the late use's of the previous instruction.
+ m_liveness.forEachLateUse(
+ m_block, instIndex - 1,
+ [&] (unsigned index) {
+ workset.add(index);
+ });
+ }
+
+ private:
+ Liveness& m_liveness;
+ typename CFG::Node m_block;
+ };
+
+ const IndexVector& rawLiveAtHead(typename CFG::Node block)
+ {
+ return m_liveAtHead[block];
+ }
+
+ template<typename UnderlyingIterable>
+ class Iterable {
+ public:
+ Iterable(Liveness& liveness, const UnderlyingIterable& iterable)
+ : m_liveness(liveness)
+ , m_iterable(iterable)
+ {
+ }
+
+ class iterator {
+ public:
+ iterator()
+ : m_liveness(nullptr)
+ , m_iter()
+ {
+ }
+
+ iterator(Liveness& liveness, typename UnderlyingIterable::const_iterator iter)
+ : m_liveness(&liveness)
+ , m_iter(iter)
+ {
+ }
+
+ typename Adapter::Thing operator*()
+ {
+ return m_liveness->indexToValue(*m_iter);
+ }
+
+ iterator& operator++()
+ {
+ ++m_iter;
+ return *this;
+ }
+
+ bool operator==(const iterator& other) const
+ {
+ ASSERT(m_liveness == other.m_liveness);
+ return m_iter == other.m_iter;
+ }
+
+ bool operator!=(const iterator& other) const
+ {
+ return !(*this == other);
+ }
+
+ private:
+ Liveness* m_liveness;
+ typename UnderlyingIterable::const_iterator m_iter;
+ };
+
+ iterator begin() const { return iterator(m_liveness, m_iterable.begin()); }
+ iterator end() const { return iterator(m_liveness, m_iterable.end()); }
+
+ bool contains(const typename Adapter::Thing& thing) const
+ {
+ return m_liveness.m_workset.contains(Adapter::valueToIndex(thing));
+ }
+
+ private:
+ Liveness& m_liveness;
+ const UnderlyingIterable& m_iterable;
+ };
+
+ Iterable<IndexVector> liveAtHead(typename CFG::Node block)
+ {
+ return Iterable<IndexVector>(*this, m_liveAtHead[block]);
+ }
+
+ Iterable<IndexVector> liveAtTail(typename CFG::Node block)
+ {
+ return Iterable<IndexVector>(*this, m_liveAtTail[block]);
+ }
+
+ IndexSparseSet<UnsafeVectorOverflow>& workset() { return m_workset; }
+
+ class LiveAtHead {
+ public:
+ LiveAtHead(Liveness& liveness)
+ : m_liveness(liveness)
+ {
+ for (unsigned blockIndex = m_liveness.m_cfg.numNodes(); blockIndex--;) {
+ typename CFG::Node block = m_liveness.m_cfg.node(blockIndex);
+ if (!block)
+ continue;
+
+ std::sort(m_liveness.m_liveAtHead[block].begin(), m_liveness.m_liveAtHead[block].end());
+ }
+ }
+
+ bool isLiveAtHead(typename CFG::Node block, const typename Adapter::Thing& thing)
+ {
+ return !!tryBinarySearch<unsigned>(m_liveness.m_liveAtHead[block], m_liveness.m_liveAtHead[block].size(), m_liveness.valueToIndex(thing), [] (unsigned* value) { return *value; });
+ }
+
+ private:
+ Liveness& m_liveness;
+ };
+
+ LiveAtHead liveAtHead() { return LiveAtHead(*this); }
+
+private:
+ friend class LocalCalc;
+ friend class LocalCalc::Iterable;
+
+ CFG& m_cfg;
+ IndexSparseSet<UnsafeVectorOverflow> m_workset;
+ typename CFG::template Map<IndexVector> m_liveAtHead;
+ typename CFG::template Map<IndexVector> m_liveAtTail;
+};
+
+} // namespace WTF
+
</ins></span></pre>
</div>
</div>
</body>
</html>