Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (214408 => 214409)
--- trunk/Source/_javascript_Core/ChangeLog 2017-03-26 21:39:27 UTC (rev 214408)
+++ trunk/Source/_javascript_Core/ChangeLog 2017-03-26 22:11:13 UTC (rev 214409)
@@ -1,3 +1,28 @@
+2017-03-25 Filip Pizlo <[email protected]>
+
+ 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:
+
2017-03-26 Filip Pizlo <[email protected]>
Air should use RegisterSet for RegLiveness
Modified: trunk/Source/_javascript_Core/b3/B3LowerMacros.cpp (214408 => 214409)
--- trunk/Source/_javascript_Core/b3/B3LowerMacros.cpp 2017-03-26 21:39:27 UTC (rev 214408)
+++ trunk/Source/_javascript_Core/b3/B3LowerMacros.cpp 2017-03-26 22:11:13 UTC (rev 214409)
@@ -612,6 +612,7 @@
bool lowerMacros(Procedure& proc)
{
+ PhaseScope phaseScope(proc, "B3::lowerMacros");
LowerMacros lowerMacros(proc);
return lowerMacros.run();
}
Modified: trunk/Source/_javascript_Core/b3/B3LowerToAir.cpp (214408 => 214409)
--- trunk/Source/_javascript_Core/b3/B3LowerToAir.cpp 2017-03-26 21:39:27 UTC (rev 214408)
+++ trunk/Source/_javascript_Core/b3/B3LowerToAir.cpp 2017-03-26 22:11:13 UTC (rev 214409)
@@ -2597,6 +2597,8 @@
// This pattern is super useful on both x86 and ARM64, since the inversion of the CAS result
// can be done with zero cost on x86 (just flip the set from E to NE) and it's a progression
// on ARM64 (since STX returns 0 on success, so ordinarily we have to flip it).
+ // FIXME: This looks wrong for AtomicStrongCAS
+ // https://bugs.webkit.org/show_bug.cgi?id=169867
if (m_value->child(1)->isInt(1)
&& isAtomicCAS(m_value->child(0)->opcode())
&& canBeInternal(m_value->child(0))) {
Modified: trunk/Source/_javascript_Core/b3/air/AirLiveness.h (214408 => 214409)
--- trunk/Source/_javascript_Core/b3/air/AirLiveness.h 2017-03-26 21:39:27 UTC (rev 214408)
+++ trunk/Source/_javascript_Core/b3/air/AirLiveness.h 2017-03-26 22:11:13 UTC (rev 214409)
@@ -32,8 +32,8 @@
#include "AirInstInlines.h"
#include "AirStackSlot.h"
#include "AirTmpInlines.h"
+#include "B3TimingScope.h"
#include <wtf/IndexMap.h>
-#include <wtf/IndexSet.h>
#include <wtf/IndexSparseSet.h>
#include <wtf/ListDump.h>
@@ -41,8 +41,8 @@
template<Bank adapterBank, Arg::Temperature minimumTemperature = Arg::Cold>
struct TmpLivenessAdapter {
+ static constexpr const char* name = "TmpLiveness";
typedef Tmp Thing;
- typedef HashSet<unsigned> IndexSet;
TmpLivenessAdapter(Code&) { }
@@ -58,8 +58,8 @@
};
struct StackSlotLivenessAdapter {
+ static constexpr const char* name = "StackSlotLiveness";
typedef StackSlot* Thing;
- typedef HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> IndexSet;
StackSlotLivenessAdapter(Code& code)
: m_code(code)
@@ -85,6 +85,7 @@
struct Workset;
public:
typedef typename Adapter::Thing Thing;
+ typedef Vector<unsigned, 4, UnsafeVectorOverflow> IndexVector;
Liveness(Code& code)
: Adapter(code)
@@ -92,9 +93,11 @@
, m_liveAtHead(code.size())
, m_liveAtTail(code.size())
{
+ TimingScope timingScope(Adapter::name);
+
// The liveAtTail of each block automatically contains the LateUse's of the terminal.
for (BasicBlock* block : code) {
- typename Adapter::IndexSet& liveAtTail = m_liveAtTail[block];
+ IndexVector& liveAtTail = m_liveAtTail[block];
block->last().forEach<typename Adapter::Thing>(
[&] (typename Adapter::Thing& thing, Arg::Role role, Bank bank, Width) {
@@ -101,15 +104,20 @@
if (Arg::isLateUse(role)
&& Adapter::acceptsBank(bank)
&& Adapter::acceptsRole(role))
- liveAtTail.add(Adapter::valueToIndex(thing));
+ 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 = 0; blockIndex < code.size(); ++blockIndex)
+ for (size_t blockIndex = code.size(); blockIndex--;)
dirtyBlocks.set(blockIndex);
-
+
+ IndexVector mergeBuffer;
+
bool changed;
do {
changed = false;
@@ -135,7 +143,7 @@
m_workset.remove(Adapter::valueToIndex(thing));
});
- Vector<unsigned>& liveAtHead = m_liveAtHead[block];
+ 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.
@@ -154,15 +162,32 @@
liveAtHead.reserveCapacity(liveAtHead.size() + m_workset.size());
for (unsigned newValue : m_workset)
liveAtHead.uncheckedAppend(newValue);
-
+
+ m_workset.sort();
+
for (BasicBlock* predecessor : block->predecessors()) {
- typename Adapter::IndexSet& liveAtTail = m_liveAtTail[predecessor];
- for (unsigned newValue : m_workset) {
- if (liveAtTail.add(newValue)) {
- if (!dirtyBlocks.quickSet(predecessor->index()))
- changed = true;
- }
+ 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);
@@ -177,7 +202,7 @@
{
auto& workset = liveness.m_workset;
workset.clear();
- typename Adapter::IndexSet& liveAtTail = liveness.m_liveAtTail[block];
+ IndexVector& liveAtTail = liveness.m_liveAtTail[block];
for (unsigned index : liveAtTail)
workset.add(index);
}
@@ -291,7 +316,7 @@
BasicBlock* m_block;
};
- const Vector<unsigned>& rawLiveAtHead(BasicBlock* block)
+ const IndexVector& rawLiveAtHead(BasicBlock* block)
{
return m_liveAtHead[block];
}
@@ -359,14 +384,14 @@
const UnderlyingIterable& m_iterable;
};
- Iterable<Vector<unsigned>> liveAtHead(BasicBlock* block)
+ Iterable<IndexVector> liveAtHead(BasicBlock* block)
{
- return Iterable<Vector<unsigned>>(*this, m_liveAtHead[block]);
+ return Iterable<IndexVector>(*this, m_liveAtHead[block]);
}
- Iterable<typename Adapter::IndexSet> liveAtTail(BasicBlock* block)
+ Iterable<IndexVector> liveAtTail(BasicBlock* block)
{
- return Iterable<typename Adapter::IndexSet>(*this, m_liveAtTail[block]);
+ return Iterable<IndexVector>(*this, m_liveAtTail[block]);
}
IndexSparseSet<UnsafeVectorOverflow>& workset() { return m_workset; }
@@ -376,8 +401,8 @@
friend class LocalCalc::Iterable;
IndexSparseSet<UnsafeVectorOverflow> m_workset;
- IndexMap<BasicBlock, Vector<unsigned>> m_liveAtHead;
- IndexMap<BasicBlock, typename Adapter::IndexSet> m_liveAtTail;
+ IndexMap<BasicBlock, IndexVector> m_liveAtHead;
+ IndexMap<BasicBlock, IndexVector> m_liveAtTail;
};
template<Bank bank, Arg::Temperature minimumTemperature = Arg::Cold>
Modified: trunk/Source/_javascript_Core/b3/air/AirLowerMacros.cpp (214408 => 214409)
--- trunk/Source/_javascript_Core/b3/air/AirLowerMacros.cpp 2017-03-26 21:39:27 UTC (rev 214408)
+++ trunk/Source/_javascript_Core/b3/air/AirLowerMacros.cpp 2017-03-26 22:11:13 UTC (rev 214409)
@@ -40,7 +40,7 @@
void lowerMacros(Code& code)
{
- PhaseScope phaseScope(code, "lowerMacros");
+ PhaseScope phaseScope(code, "Air::lowerMacros");
InsertionSet insertionSet(code);
for (BasicBlock* block : code) {
Modified: trunk/Source/_javascript_Core/b3/air/AirTmp.h (214408 => 214409)
--- trunk/Source/_javascript_Core/b3/air/AirTmp.h 2017-03-26 21:39:27 UTC (rev 214408)
+++ trunk/Source/_javascript_Core/b3/air/AirTmp.h 2017-03-26 22:11:13 UTC (rev 214409)
@@ -27,6 +27,7 @@
#if ENABLE(B3_JIT)
+#include "B3Bank.h"
#include "FPRInfo.h"
#include "GPRInfo.h"
#include "Reg.h"
@@ -75,7 +76,7 @@
}
explicit operator bool() const { return !!m_value; }
-
+
bool isGP() const
{
return isEncodedGP(m_value);
@@ -86,6 +87,12 @@
return isEncodedFP(m_value);
}
+ // For null tmps, returns GP.
+ Bank bank() const
+ {
+ return isFP() ? FP : GP;
+ }
+
bool isGPR() const
{
return isEncodedGPR(m_value);
@@ -132,6 +139,14 @@
{
return decodeFPTmp(m_value);
}
+
+ unsigned tmpIndex(Bank bank) const
+ {
+ if (bank == GP)
+ return gpTmpIndex();
+ ASSERT(bank == FP);
+ return fpTmpIndex();
+ }
unsigned tmpIndex() const
{
Modified: trunk/Source/_javascript_Core/dfg/DFGStoreBarrierClusteringPhase.cpp (214408 => 214409)
--- trunk/Source/_javascript_Core/dfg/DFGStoreBarrierClusteringPhase.cpp 2017-03-26 21:39:27 UTC (rev 214408)
+++ trunk/Source/_javascript_Core/dfg/DFGStoreBarrierClusteringPhase.cpp 2017-03-26 22:11:13 UTC (rev 214409)
@@ -130,12 +130,12 @@
[&] (const ChildAndOrigin& a, const ChildAndOrigin& b) -> bool {
return a.child < b.child;
});
- auto end = std::unique(
- m_neededBarriers.begin(), m_neededBarriers.end(),
+ removeRepeatedElements(
+ m_neededBarriers,
[&] (const ChildAndOrigin& a, const ChildAndOrigin& b) -> bool{
return a.child == b.child;
});
- for (auto iter = m_neededBarriers.begin(); iter != end; ++iter) {
+ for (auto iter = m_neededBarriers.begin(); iter != m_neededBarriers.end(); ++iter) {
Node* child = iter->child;
CodeOrigin semanticOrigin = iter->semanticOrigin;
Modified: trunk/Source/WTF/ChangeLog (214408 => 214409)
--- 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)
@@ -1,3 +1,19 @@
+2017-03-25 Filip Pizlo <[email protected]>
+
+ 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.
+
2017-03-26 Filip Pizlo <[email protected]>
Air should use RegisterSet for RegLiveness
Modified: trunk/Source/WTF/wtf/IndexSparseSet.h (214408 => 214409)
--- 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)
@@ -58,6 +58,10 @@
typedef typename ValueList::const_iterator const_iterator;
const_iterator begin() const;
const_iterator end() const;
+
+ void sort();
+
+ const ValueList& values() const { return m_values; }
private:
Vector<unsigned, 0, OverflowHandler, 1> m_map;
@@ -129,6 +133,12 @@
}
template<typename OverflowHandler>
+void IndexSparseSet<OverflowHandler>::sort()
+{
+ std::sort(m_values.begin(), m_values.end());
+}
+
+template<typename OverflowHandler>
auto IndexSparseSet<OverflowHandler>::begin() const -> const_iterator
{
return m_values.begin();
Modified: trunk/Source/WTF/wtf/StdLibExtras.h (214408 => 214409)
--- 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)
@@ -408,6 +408,45 @@
typedef typename std::remove_cv<typename std::remove_reference<T>::type>::type type;
};
+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;
+}
+
} // namespace WTF
// This version of placement new omits a 0 check.
@@ -489,6 +528,7 @@
using WTF::isPointerAligned;
using WTF::isStatelessLambda;
using WTF::is8ByteAligned;
+using WTF::mergeDeduplicatedSorted;
using WTF::roundUpToMultipleOf;
using WTF::safeCast;
using WTF::tryBinarySearch;
Modified: trunk/Source/WTF/wtf/Vector.h (214408 => 214409)
--- 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)
@@ -1290,7 +1290,7 @@
// vector's capacity is large enough for the append to succeed.
template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> template<typename U>
-inline void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::uncheckedAppend(U&& value)
+ALWAYS_INLINE void Vector<T, inlineCapacity, OverflowHandler, minCapacity>::uncheckedAppend(U&& value)
{
ASSERT(size() < capacity());
@@ -1501,10 +1501,26 @@
};
#endif
+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; });
+}
+
} // namespace WTF
using WTF::Vector;
using WTF::UnsafeVectorOverflow;
using WTF::notFound;
+using WTF::removeRepeatedElements;
#endif // WTF_Vector_h
