<!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>[214409] 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/214409">214409</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2017-03-26 15:11:13 -0700 (Sun, 26 Mar 2017)</dd>
</dl>
<h3>Log Message</h3>
<pre>Air::Liveness shouldn't need HashSets
https://bugs.webkit.org/show_bug.cgi?id=170102
Reviewed by Yusuke Suzuki.
Source/JavaScriptCore:
This converts Air::Liveness<> to no longer use HashSets or BitVectors. This turns out to be
easy because it's cheap enough to do a sorted merge of the things being added to liveAtHead and
the things in the predecessors' liveAtTail. This turns out to be faster - it's a 2% overall
compile time progression on WasmBench.
* b3/B3LowerToAir.cpp:
(JSC::B3::Air::LowerToAir::lower): Add a FIXME unrelated to this patch.
* b3/air/AirLiveness.h:
(JSC::B3::Air::AbstractLiveness::AbstractLiveness):
(JSC::B3::Air::AbstractLiveness::LocalCalc::LocalCalc):
(JSC::B3::Air::AbstractLiveness::rawLiveAtHead):
(JSC::B3::Air::AbstractLiveness::liveAtHead):
(JSC::B3::Air::AbstractLiveness::liveAtTail):
* b3/air/AirTmp.h:
(JSC::B3::Air::Tmp::bank):
(JSC::B3::Air::Tmp::tmpIndex):
* dfg/DFGStoreBarrierClusteringPhase.cpp:
Source/WTF:
* wtf/IndexSparseSet.h: Add some helpers for a HashSet-free liveness analysis.
(WTF::IndexSparseSet::values):
(WTF::IndexSparseSet<OverflowHandler>::sort):
* wtf/StdLibExtras.h:
(WTF::mergeDeduplicatedSorted): Rapidly merge two sorted lists that don't have duplicates to produce a new sorted list that doesn't have duplicates.
* wtf/Vector.h:
(WTF::minCapacity>::uncheckedAppend): Inline this!
(WTF::removeRepeatedElements): This is a version of std::unique() that works naturally for Vectors.</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3LowerMacroscpp">trunk/Source/JavaScriptCore/b3/B3LowerMacros.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3LowerToAircpp">trunk/Source/JavaScriptCore/b3/B3LowerToAir.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirLivenessh">trunk/Source/JavaScriptCore/b3/air/AirLiveness.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirLowerMacroscpp">trunk/Source/JavaScriptCore/b3/air/AirLowerMacros.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirTmph">trunk/Source/JavaScriptCore/b3/air/AirTmp.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGStoreBarrierClusteringPhasecpp">trunk/Source/JavaScriptCore/dfg/DFGStoreBarrierClusteringPhase.cpp</a></li>
<li><a href="#trunkSourceWTFChangeLog">trunk/Source/WTF/ChangeLog</a></li>
<li><a href="#trunkSourceWTFwtfIndexSparseSeth">trunk/Source/WTF/wtf/IndexSparseSet.h</a></li>
<li><a href="#trunkSourceWTFwtfStdLibExtrash">trunk/Source/WTF/wtf/StdLibExtras.h</a></li>
<li><a href="#trunkSourceWTFwtfVectorh">trunk/Source/WTF/wtf/Vector.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (214408 => 214409)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2017-03-26 21:39:27 UTC (rev 214408)
+++ trunk/Source/JavaScriptCore/ChangeLog 2017-03-26 22:11:13 UTC (rev 214409)
</span><span class="lines">@@ -1,3 +1,28 @@
</span><ins>+2017-03-25 Filip Pizlo <fpizlo@apple.com>
+
+ Air::Liveness shouldn't need HashSets
+ https://bugs.webkit.org/show_bug.cgi?id=170102
+
+ Reviewed by Yusuke Suzuki.
+
+ This converts Air::Liveness<> to no longer use HashSets or BitVectors. This turns out to be
+ easy because it's cheap enough to do a sorted merge of the things being added to liveAtHead and
+ the things in the predecessors' liveAtTail. This turns out to be faster - it's a 2% overall
+ compile time progression on WasmBench.
+
+ * b3/B3LowerToAir.cpp:
+ (JSC::B3::Air::LowerToAir::lower): Add a FIXME unrelated to this patch.
+ * b3/air/AirLiveness.h:
+ (JSC::B3::Air::AbstractLiveness::AbstractLiveness):
+ (JSC::B3::Air::AbstractLiveness::LocalCalc::LocalCalc):
+ (JSC::B3::Air::AbstractLiveness::rawLiveAtHead):
+ (JSC::B3::Air::AbstractLiveness::liveAtHead):
+ (JSC::B3::Air::AbstractLiveness::liveAtTail):
+ * b3/air/AirTmp.h:
+ (JSC::B3::Air::Tmp::bank):
+ (JSC::B3::Air::Tmp::tmpIndex):
+ * dfg/DFGStoreBarrierClusteringPhase.cpp:
+
</ins><span class="cx"> 2017-03-26 Filip Pizlo <fpizlo@apple.com>
</span><span class="cx">
</span><span class="cx"> Air should use RegisterSet for RegLiveness
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3LowerMacroscpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3LowerMacros.cpp (214408 => 214409)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3LowerMacros.cpp 2017-03-26 21:39:27 UTC (rev 214408)
+++ trunk/Source/JavaScriptCore/b3/B3LowerMacros.cpp 2017-03-26 22:11:13 UTC (rev 214409)
</span><span class="lines">@@ -612,6 +612,7 @@
</span><span class="cx">
</span><span class="cx"> bool lowerMacros(Procedure& proc)
</span><span class="cx"> {
</span><ins>+ PhaseScope phaseScope(proc, "B3::lowerMacros");
</ins><span class="cx"> LowerMacros lowerMacros(proc);
</span><span class="cx"> return lowerMacros.run();
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3LowerToAircpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3LowerToAir.cpp (214408 => 214409)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3LowerToAir.cpp 2017-03-26 21:39:27 UTC (rev 214408)
+++ trunk/Source/JavaScriptCore/b3/B3LowerToAir.cpp 2017-03-26 22:11:13 UTC (rev 214409)
</span><span class="lines">@@ -2597,6 +2597,8 @@
</span><span class="cx"> // This pattern is super useful on both x86 and ARM64, since the inversion of the CAS result
</span><span class="cx"> // can be done with zero cost on x86 (just flip the set from E to NE) and it's a progression
</span><span class="cx"> // on ARM64 (since STX returns 0 on success, so ordinarily we have to flip it).
</span><ins>+ // FIXME: This looks wrong for AtomicStrongCAS
+ // https://bugs.webkit.org/show_bug.cgi?id=169867
</ins><span class="cx"> if (m_value->child(1)->isInt(1)
</span><span class="cx"> && isAtomicCAS(m_value->child(0)->opcode())
</span><span class="cx"> && canBeInternal(m_value->child(0))) {
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirLivenessh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirLiveness.h (214408 => 214409)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirLiveness.h 2017-03-26 21:39:27 UTC (rev 214408)
+++ trunk/Source/JavaScriptCore/b3/air/AirLiveness.h 2017-03-26 22:11:13 UTC (rev 214409)
</span><span class="lines">@@ -32,8 +32,8 @@
</span><span class="cx"> #include "AirInstInlines.h"
</span><span class="cx"> #include "AirStackSlot.h"
</span><span class="cx"> #include "AirTmpInlines.h"
</span><ins>+#include "B3TimingScope.h"
</ins><span class="cx"> #include <wtf/IndexMap.h>
</span><del>-#include <wtf/IndexSet.h>
</del><span class="cx"> #include <wtf/IndexSparseSet.h>
</span><span class="cx"> #include <wtf/ListDump.h>
</span><span class="cx">
</span><span class="lines">@@ -41,8 +41,8 @@
</span><span class="cx">
</span><span class="cx"> template<Bank adapterBank, Arg::Temperature minimumTemperature = Arg::Cold>
</span><span class="cx"> struct TmpLivenessAdapter {
</span><ins>+ static constexpr const char* name = "TmpLiveness";
</ins><span class="cx"> typedef Tmp Thing;
</span><del>- typedef HashSet<unsigned> IndexSet;
</del><span class="cx">
</span><span class="cx"> TmpLivenessAdapter(Code&) { }
</span><span class="cx">
</span><span class="lines">@@ -58,8 +58,8 @@
</span><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> struct StackSlotLivenessAdapter {
</span><ins>+ static constexpr const char* name = "StackSlotLiveness";
</ins><span class="cx"> typedef StackSlot* Thing;
</span><del>- typedef HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> IndexSet;
</del><span class="cx">
</span><span class="cx"> StackSlotLivenessAdapter(Code& code)
</span><span class="cx"> : m_code(code)
</span><span class="lines">@@ -85,6 +85,7 @@
</span><span class="cx"> struct Workset;
</span><span class="cx"> public:
</span><span class="cx"> typedef typename Adapter::Thing Thing;
</span><ins>+ typedef Vector<unsigned, 4, UnsafeVectorOverflow> IndexVector;
</ins><span class="cx">
</span><span class="cx"> Liveness(Code& code)
</span><span class="cx"> : Adapter(code)
</span><span class="lines">@@ -92,9 +93,11 @@
</span><span class="cx"> , m_liveAtHead(code.size())
</span><span class="cx"> , m_liveAtTail(code.size())
</span><span class="cx"> {
</span><ins>+ TimingScope timingScope(Adapter::name);
+
</ins><span class="cx"> // The liveAtTail of each block automatically contains the LateUse's of the terminal.
</span><span class="cx"> for (BasicBlock* block : code) {
</span><del>- typename Adapter::IndexSet& liveAtTail = m_liveAtTail[block];
</del><ins>+ IndexVector& liveAtTail = m_liveAtTail[block];
</ins><span class="cx">
</span><span class="cx"> block->last().forEach<typename Adapter::Thing>(
</span><span class="cx"> [&] (typename Adapter::Thing& thing, Arg::Role role, Bank bank, Width) {
</span><span class="lines">@@ -101,15 +104,20 @@
</span><span class="cx"> if (Arg::isLateUse(role)
</span><span class="cx"> && Adapter::acceptsBank(bank)
</span><span class="cx"> && Adapter::acceptsRole(role))
</span><del>- liveAtTail.add(Adapter::valueToIndex(thing));
</del><ins>+ liveAtTail.append(Adapter::valueToIndex(thing));
</ins><span class="cx"> });
</span><ins>+
+ std::sort(liveAtTail.begin(), liveAtTail.end());
+ removeRepeatedElements(liveAtTail);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> // Blocks with new live values at tail.
</span><span class="cx"> BitVector dirtyBlocks;
</span><del>- for (size_t blockIndex = 0; blockIndex < code.size(); ++blockIndex)
</del><ins>+ for (size_t blockIndex = code.size(); blockIndex--;)
</ins><span class="cx"> dirtyBlocks.set(blockIndex);
</span><del>-
</del><ins>+
+ IndexVector mergeBuffer;
+
</ins><span class="cx"> bool changed;
</span><span class="cx"> do {
</span><span class="cx"> changed = false;
</span><span class="lines">@@ -135,7 +143,7 @@
</span><span class="cx"> m_workset.remove(Adapter::valueToIndex(thing));
</span><span class="cx"> });
</span><span class="cx">
</span><del>- Vector<unsigned>& liveAtHead = m_liveAtHead[block];
</del><ins>+ IndexVector& liveAtHead = m_liveAtHead[block];
</ins><span class="cx">
</span><span class="cx"> // We only care about Tmps that were discovered in this iteration. It is impossible
</span><span class="cx"> // to remove a live value from the head.
</span><span class="lines">@@ -154,15 +162,32 @@
</span><span class="cx"> liveAtHead.reserveCapacity(liveAtHead.size() + m_workset.size());
</span><span class="cx"> for (unsigned newValue : m_workset)
</span><span class="cx"> liveAtHead.uncheckedAppend(newValue);
</span><del>-
</del><ins>+
+ m_workset.sort();
+
</ins><span class="cx"> for (BasicBlock* predecessor : block->predecessors()) {
</span><del>- typename Adapter::IndexSet& liveAtTail = m_liveAtTail[predecessor];
- for (unsigned newValue : m_workset) {
- if (liveAtTail.add(newValue)) {
- if (!dirtyBlocks.quickSet(predecessor->index()))
- changed = true;
- }
</del><ins>+ 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;
</ins><span class="cx"> }
</span><ins>+
+ dirtyBlocks.quickSet(predecessor->index());
+ changed = true;
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx"> } while (changed);
</span><span class="lines">@@ -177,7 +202,7 @@
</span><span class="cx"> {
</span><span class="cx"> auto& workset = liveness.m_workset;
</span><span class="cx"> workset.clear();
</span><del>- typename Adapter::IndexSet& liveAtTail = liveness.m_liveAtTail[block];
</del><ins>+ IndexVector& liveAtTail = liveness.m_liveAtTail[block];
</ins><span class="cx"> for (unsigned index : liveAtTail)
</span><span class="cx"> workset.add(index);
</span><span class="cx"> }
</span><span class="lines">@@ -291,7 +316,7 @@
</span><span class="cx"> BasicBlock* m_block;
</span><span class="cx"> };
</span><span class="cx">
</span><del>- const Vector<unsigned>& rawLiveAtHead(BasicBlock* block)
</del><ins>+ const IndexVector& rawLiveAtHead(BasicBlock* block)
</ins><span class="cx"> {
</span><span class="cx"> return m_liveAtHead[block];
</span><span class="cx"> }
</span><span class="lines">@@ -359,14 +384,14 @@
</span><span class="cx"> const UnderlyingIterable& m_iterable;
</span><span class="cx"> };
</span><span class="cx">
</span><del>- Iterable<Vector<unsigned>> liveAtHead(BasicBlock* block)
</del><ins>+ Iterable<IndexVector> liveAtHead(BasicBlock* block)
</ins><span class="cx"> {
</span><del>- return Iterable<Vector<unsigned>>(*this, m_liveAtHead[block]);
</del><ins>+ return Iterable<IndexVector>(*this, m_liveAtHead[block]);
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- Iterable<typename Adapter::IndexSet> liveAtTail(BasicBlock* block)
</del><ins>+ Iterable<IndexVector> liveAtTail(BasicBlock* block)
</ins><span class="cx"> {
</span><del>- return Iterable<typename Adapter::IndexSet>(*this, m_liveAtTail[block]);
</del><ins>+ return Iterable<IndexVector>(*this, m_liveAtTail[block]);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> IndexSparseSet<UnsafeVectorOverflow>& workset() { return m_workset; }
</span><span class="lines">@@ -376,8 +401,8 @@
</span><span class="cx"> friend class LocalCalc::Iterable;
</span><span class="cx">
</span><span class="cx"> IndexSparseSet<UnsafeVectorOverflow> m_workset;
</span><del>- IndexMap<BasicBlock, Vector<unsigned>> m_liveAtHead;
- IndexMap<BasicBlock, typename Adapter::IndexSet> m_liveAtTail;
</del><ins>+ IndexMap<BasicBlock, IndexVector> m_liveAtHead;
+ IndexMap<BasicBlock, IndexVector> m_liveAtTail;
</ins><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="trunkSourceJavaScriptCoreb3airAirLowerMacroscpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirLowerMacros.cpp (214408 => 214409)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirLowerMacros.cpp 2017-03-26 21:39:27 UTC (rev 214408)
+++ trunk/Source/JavaScriptCore/b3/air/AirLowerMacros.cpp 2017-03-26 22:11:13 UTC (rev 214409)
</span><span class="lines">@@ -40,7 +40,7 @@
</span><span class="cx">
</span><span class="cx"> void lowerMacros(Code& code)
</span><span class="cx"> {
</span><del>- PhaseScope phaseScope(code, "lowerMacros");
</del><ins>+ PhaseScope phaseScope(code, "Air::lowerMacros");
</ins><span class="cx">
</span><span class="cx"> InsertionSet insertionSet(code);
</span><span class="cx"> for (BasicBlock* block : code) {
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirTmph"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirTmp.h (214408 => 214409)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirTmp.h 2017-03-26 21:39:27 UTC (rev 214408)
+++ trunk/Source/JavaScriptCore/b3/air/AirTmp.h 2017-03-26 22:11:13 UTC (rev 214409)
</span><span class="lines">@@ -27,6 +27,7 @@
</span><span class="cx">
</span><span class="cx"> #if ENABLE(B3_JIT)
</span><span class="cx">
</span><ins>+#include "B3Bank.h"
</ins><span class="cx"> #include "FPRInfo.h"
</span><span class="cx"> #include "GPRInfo.h"
</span><span class="cx"> #include "Reg.h"
</span><span class="lines">@@ -75,7 +76,7 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> explicit operator bool() const { return !!m_value; }
</span><del>-
</del><ins>+
</ins><span class="cx"> bool isGP() const
</span><span class="cx"> {
</span><span class="cx"> return isEncodedGP(m_value);
</span><span class="lines">@@ -86,6 +87,12 @@
</span><span class="cx"> return isEncodedFP(m_value);
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ // For null tmps, returns GP.
+ Bank bank() const
+ {
+ return isFP() ? FP : GP;
+ }
+
</ins><span class="cx"> bool isGPR() const
</span><span class="cx"> {
</span><span class="cx"> return isEncodedGPR(m_value);
</span><span class="lines">@@ -132,6 +139,14 @@
</span><span class="cx"> {
</span><span class="cx"> return decodeFPTmp(m_value);
</span><span class="cx"> }
</span><ins>+
+ unsigned tmpIndex(Bank bank) const
+ {
+ if (bank == GP)
+ return gpTmpIndex();
+ ASSERT(bank == FP);
+ return fpTmpIndex();
+ }
</ins><span class="cx">
</span><span class="cx"> unsigned tmpIndex() const
</span><span class="cx"> {
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGStoreBarrierClusteringPhasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGStoreBarrierClusteringPhase.cpp (214408 => 214409)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGStoreBarrierClusteringPhase.cpp 2017-03-26 21:39:27 UTC (rev 214408)
+++ trunk/Source/JavaScriptCore/dfg/DFGStoreBarrierClusteringPhase.cpp 2017-03-26 22:11:13 UTC (rev 214409)
</span><span class="lines">@@ -130,12 +130,12 @@
</span><span class="cx"> [&] (const ChildAndOrigin& a, const ChildAndOrigin& b) -> bool {
</span><span class="cx"> return a.child < b.child;
</span><span class="cx"> });
</span><del>- auto end = std::unique(
- m_neededBarriers.begin(), m_neededBarriers.end(),
</del><ins>+ removeRepeatedElements(
+ m_neededBarriers,
</ins><span class="cx"> [&] (const ChildAndOrigin& a, const ChildAndOrigin& b) -> bool{
</span><span class="cx"> return a.child == b.child;
</span><span class="cx"> });
</span><del>- for (auto iter = m_neededBarriers.begin(); iter != end; ++iter) {
</del><ins>+ for (auto iter = m_neededBarriers.begin(); iter != m_neededBarriers.end(); ++iter) {
</ins><span class="cx"> Node* child = iter->child;
</span><span class="cx"> CodeOrigin semanticOrigin = iter->semanticOrigin;
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWTFChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/ChangeLog (214408 => 214409)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/ChangeLog 2017-03-26 21:39:27 UTC (rev 214408)
+++ trunk/Source/WTF/ChangeLog 2017-03-26 22:11:13 UTC (rev 214409)
</span><span class="lines">@@ -1,3 +1,19 @@
</span><ins>+2017-03-25 Filip Pizlo <fpizlo@apple.com>
+
+ Air::Liveness shouldn't need HashSets
+ https://bugs.webkit.org/show_bug.cgi?id=170102
+
+ Reviewed by Yusuke Suzuki.
+
+ * wtf/IndexSparseSet.h: Add some helpers for a HashSet-free liveness analysis.
+ (WTF::IndexSparseSet::values):
+ (WTF::IndexSparseSet<OverflowHandler>::sort):
+ * wtf/StdLibExtras.h:
+ (WTF::mergeDeduplicatedSorted): Rapidly merge two sorted lists that don't have duplicates to produce a new sorted list that doesn't have duplicates.
+ * wtf/Vector.h:
+ (WTF::minCapacity>::uncheckedAppend): Inline this!
+ (WTF::removeRepeatedElements): This is a version of std::unique() that works naturally for Vectors.
+
</ins><span class="cx"> 2017-03-26 Filip Pizlo <fpizlo@apple.com>
</span><span class="cx">
</span><span class="cx"> Air should use RegisterSet for RegLiveness
</span></span></pre></div>
<a id="trunkSourceWTFwtfIndexSparseSeth"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/IndexSparseSet.h (214408 => 214409)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/IndexSparseSet.h 2017-03-26 21:39:27 UTC (rev 214408)
+++ trunk/Source/WTF/wtf/IndexSparseSet.h 2017-03-26 22:11:13 UTC (rev 214409)
</span><span class="lines">@@ -58,6 +58,10 @@
</span><span class="cx"> typedef typename ValueList::const_iterator const_iterator;
</span><span class="cx"> const_iterator begin() const;
</span><span class="cx"> const_iterator end() const;
</span><ins>+
+ void sort();
+
+ const ValueList& values() const { return m_values; }
</ins><span class="cx">
</span><span class="cx"> private:
</span><span class="cx"> Vector<unsigned, 0, OverflowHandler, 1> m_map;
</span><span class="lines">@@ -129,6 +133,12 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> template<typename OverflowHandler>
</span><ins>+void IndexSparseSet<OverflowHandler>::sort()
+{
+ std::sort(m_values.begin(), m_values.end());
+}
+
+template<typename OverflowHandler>
</ins><span class="cx"> auto IndexSparseSet<OverflowHandler>::begin() const -> const_iterator
</span><span class="cx"> {
</span><span class="cx"> return m_values.begin();
</span></span></pre></div>
<a id="trunkSourceWTFwtfStdLibExtrash"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/StdLibExtras.h (214408 => 214409)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/StdLibExtras.h 2017-03-26 21:39:27 UTC (rev 214408)
+++ trunk/Source/WTF/wtf/StdLibExtras.h 2017-03-26 22:11:13 UTC (rev 214409)
</span><span class="lines">@@ -408,6 +408,45 @@
</span><span class="cx"> typedef typename std::remove_cv<typename std::remove_reference<T>::type>::type type;
</span><span class="cx"> };
</span><span class="cx">
</span><ins>+template<typename IteratorTypeLeft, typename IteratorTypeRight, typename IteratorTypeDst>
+IteratorTypeDst mergeDeduplicatedSorted(IteratorTypeLeft leftBegin, IteratorTypeLeft leftEnd, IteratorTypeRight rightBegin, IteratorTypeRight rightEnd, IteratorTypeDst dstBegin)
+{
+ IteratorTypeLeft leftIter = leftBegin;
+ IteratorTypeRight rightIter = rightBegin;
+ IteratorTypeDst dstIter = dstBegin;
+
+ if (leftIter < leftEnd && rightIter < rightEnd) {
+ for (;;) {
+ auto left = *leftIter;
+ auto right = *rightIter;
+ if (left < right) {
+ *dstIter++ = left;
+ leftIter++;
+ if (leftIter >= leftEnd)
+ break;
+ } else if (left == right) {
+ *dstIter++ = left;
+ leftIter++;
+ rightIter++;
+ if (leftIter >= leftEnd || rightIter >= rightEnd)
+ break;
+ } else {
+ *dstIter++ = right;
+ rightIter++;
+ if (rightIter >= rightEnd)
+ break;
+ }
+ }
+ }
+
+ while (leftIter < leftEnd)
+ *dstIter++ = *leftIter++;
+ while (rightIter < rightEnd)
+ *dstIter++ = *rightIter++;
+
+ return dstIter;
+}
+
</ins><span class="cx"> } // namespace WTF
</span><span class="cx">
</span><span class="cx"> // This version of placement new omits a 0 check.
</span><span class="lines">@@ -489,6 +528,7 @@
</span><span class="cx"> using WTF::isPointerAligned;
</span><span class="cx"> using WTF::isStatelessLambda;
</span><span class="cx"> using WTF::is8ByteAligned;
</span><ins>+using WTF::mergeDeduplicatedSorted;
</ins><span class="cx"> using WTF::roundUpToMultipleOf;
</span><span class="cx"> using WTF::safeCast;
</span><span class="cx"> using WTF::tryBinarySearch;
</span></span></pre></div>
<a id="trunkSourceWTFwtfVectorh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/Vector.h (214408 => 214409)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/Vector.h 2017-03-26 21:39:27 UTC (rev 214408)
+++ trunk/Source/WTF/wtf/Vector.h 2017-03-26 22:11:13 UTC (rev 214409)
</span><span class="lines">@@ -1290,7 +1290,7 @@
</span><span class="cx"> // vector's capacity is large enough for the append to succeed.
</span><span class="cx">
</span><span class="cx"> template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
</span><del>-inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::uncheckedAppend(U&& value)
</del><ins>+ALWAYS_INLINE void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::uncheckedAppend(U&& value)
</ins><span class="cx"> {
</span><span class="cx"> ASSERT(size() < capacity());
</span><span class="cx">
</span><span class="lines">@@ -1501,10 +1501,26 @@
</span><span class="cx"> };
</span><span class="cx"> #endif
</span><span class="cx">
</span><ins>+template<typename VectorType, typename Func>
+size_t removeRepeatedElements(VectorType& vector, const Func& func)
+{
+ auto end = std::unique(vector.begin(), vector.end(), func);
+ size_t newSize = end - vector.begin();
+ vector.resize(newSize);
+ return newSize;
+}
+
+template<typename VectorType>
+size_t removeRepeatedElements(VectorType& vector)
+{
+ return removeRepeatedElements(vector, [] (auto& a, auto& b) { return a == b; });
+}
+
</ins><span class="cx"> } // namespace WTF
</span><span class="cx">
</span><span class="cx"> using WTF::Vector;
</span><span class="cx"> using WTF::UnsafeVectorOverflow;
</span><span class="cx"> using WTF::notFound;
</span><ins>+using WTF::removeRepeatedElements;
</ins><span class="cx">
</span><span class="cx"> #endif // WTF_Vector_h
</span></span></pre>
</div>
</div>
</body>
</html>