Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (192850 => 192851)
--- trunk/Source/_javascript_Core/ChangeLog 2015-12-01 02:15:47 UTC (rev 192850)
+++ trunk/Source/_javascript_Core/ChangeLog 2015-12-01 02:26:57 UTC (rev 192851)
@@ -1,3 +1,96 @@
+2015-11-30 Benjamin Poulain <bpoul...@apple.com>
+
+ [JSC] Speed up Air Liveness Analysis on Tmps
+ https://bugs.webkit.org/show_bug.cgi?id=151556
+
+ Reviewed by Filip Pizlo.
+
+ Liveness Analysis scales poorly on large graphs like the ones
+ generated by testComplex().
+ This patch introduces a faster of Liveness using the continuous indices
+ of values instead of the values themselves.
+
+ There are two main areas of improvements:
+ 1) Reduce the cost of doing a LocalCalc over a BasicBlock.
+ 2) Reduce how many LocalCalc are needed to converge to a solution.
+
+ Most of the costs of LocalCalc are from HashSet manipulations.
+ The HashSet operations are O(1) but the constant is large enough
+ to be a problem.
+
+ I used a similar trick as the Register Allocator to remove hashing
+ and collision handling: the absolute value of the Tmp is used as an index
+ into a flat array.
+
+ I used Briggs's Sparse Set implementation for the local live information
+ at each instruction. It has great properties for doing the local calculation:
+ -No memory reallocation.
+ -O(1) add() and remove() with a small constant.
+ -Strict O(n) iteration.
+ -O(1) clear().
+
+ The values Live-At-Head are now stored into a Vector. The Sparse Set
+ is used to maintain the Tmp uniqueness.
+
+ When forwarding new liveness at head to the predecessor, I start by removing
+ everything that was already in live-at-head. We can assume that any value
+ in that list has already been added to the predecessors.
+ This leaves us with a small-ish number of Tmps to add to live-at-head
+ and to the predecessors.
+
+ The speed up convergence, I used the same trick as DFG's liveness: keep
+ a set of dirty blocks to process. In practice, all the blocks without
+ back-edges converge quickly, and we only propagate liveness as needed.
+
+ This patch reduces the time taken by "testComplex(64, 384)" by another 5%.
+
+ The remaining things to do for Liveness are:
+ -Skip the first block for the fix point (it is often large and doing a local
+ calc on it is useless).
+ -Find a better Data Structure for live-at-tail (updating the HashSet takes
+ > 50% of the total convergence time).
+
+ * _javascript_Core.xcodeproj/project.pbxproj:
+ * b3/air/AirIteratedRegisterCoalescing.cpp:
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::build):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::getAlias):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::getAliasWhenSpilling):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::allocatedReg):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::tmpArraySize):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::initializeDegrees):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::addEdges):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::addEdge):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::makeWorkList):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::simplify):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::forEachAdjacent):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::hasBeenSimplified):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::decrementDegree):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::forEachNodeMoves):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::isMoveRelated):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::enableMovesOnValue):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::precoloredCoalescingHeuristic):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::conservativeHeuristic):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::addWorkList):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::combine):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::freezeMoves):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::selectSpill):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::assignColors):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::dumpInterferenceGraphInDot):
+ (JSC::B3::Air::iteratedRegisterCoalescingOnType):
+ (JSC::B3::Air::iteratedRegisterCoalescing):
+ (JSC::B3::Air::AbsoluteTmpHelper<Arg::GP>::absoluteIndex): Deleted.
+ (JSC::B3::Air::AbsoluteTmpHelper<Arg::GP>::tmpFromAbsoluteIndex): Deleted.
+ (JSC::B3::Air::AbsoluteTmpHelper<Arg::FP>::absoluteIndex): Deleted.
+ (JSC::B3::Air::AbsoluteTmpHelper<Arg::FP>::tmpFromAbsoluteIndex): Deleted.
+ * b3/air/AirReportUsedRegisters.cpp:
+ (JSC::B3::Air::reportUsedRegisters):
+ * b3/air/AirTmpInlines.h:
+ (JSC::B3::Air::AbsoluteTmpMapper<Arg::GP>::absoluteIndex):
+ (JSC::B3::Air::AbsoluteTmpMapper<Arg::GP>::tmpFromAbsoluteIndex):
+ (JSC::B3::Air::AbsoluteTmpMapper<Arg::FP>::absoluteIndex):
+ (JSC::B3::Air::AbsoluteTmpMapper<Arg::FP>::tmpFromAbsoluteIndex):
+ * b3/air/AirLiveness.h: Added.
+
2015-11-30 Saam barati <sbar...@apple.com>
FTL OSR Exits that are exception handlers should not have two different entrances. Instead, we should have two discrete OSR exits that do different things.
Modified: trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj (192850 => 192851)
--- trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2015-12-01 02:15:47 UTC (rev 192850)
+++ trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2015-12-01 02:26:57 UTC (rev 192851)
@@ -814,7 +814,6 @@
0FEC857F1BDACDC70080FF74 /* AirInst.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FEC855A1BDACDC70080FF74 /* AirInst.cpp */; };
0FEC85801BDACDC70080FF74 /* AirInst.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEC855B1BDACDC70080FF74 /* AirInst.h */; };
0FEC85811BDACDC70080FF74 /* AirInstInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEC855C1BDACDC70080FF74 /* AirInstInlines.h */; };
- 0FEC85821BDACDC70080FF74 /* AirLiveness.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEC855D1BDACDC70080FF74 /* AirLiveness.h */; };
0FEC85831BDACDC70080FF74 /* AirPhaseScope.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FEC855E1BDACDC70080FF74 /* AirPhaseScope.cpp */; };
0FEC85841BDACDC70080FF74 /* AirPhaseScope.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEC855F1BDACDC70080FF74 /* AirPhaseScope.h */; };
0FEC85851BDACDC70080FF74 /* AirRegisterPriority.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FEC85601BDACDC70080FF74 /* AirRegisterPriority.cpp */; };
@@ -1088,6 +1087,7 @@
2600B5A7152BAAA70091EE5F /* JSStringJoiner.h in Headers */ = {isa = PBXBuildFile; fileRef = 2600B5A5152BAAA70091EE5F /* JSStringJoiner.h */; };
26718BA41BE99F780052017B /* AirIteratedRegisterCoalescing.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 26718BA21BE99F780052017B /* AirIteratedRegisterCoalescing.cpp */; };
26718BA51BE99F780052017B /* AirIteratedRegisterCoalescing.h in Headers */ = {isa = PBXBuildFile; fileRef = 26718BA31BE99F780052017B /* AirIteratedRegisterCoalescing.h */; };
+ 2684D4381C00161C0081D663 /* AirLiveness.h in Headers */ = {isa = PBXBuildFile; fileRef = 2684D4371C00161C0081D663 /* AirLiveness.h */; };
269D636E1BFBE5D100101B1D /* FTLB3Output.h in Headers */ = {isa = PBXBuildFile; fileRef = 269D636D1BFBE5D000101B1D /* FTLB3Output.h */; };
26BB57601BFC4328005F12EB /* FTLB3Output.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 26BB575F1BFC4328005F12EB /* FTLB3Output.cpp */; };
2A05ABD51961DF2400341750 /* JSPropertyNameEnumerator.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 2A05ABD31961DF2400341750 /* JSPropertyNameEnumerator.cpp */; };
@@ -2895,7 +2895,6 @@
0FEC855A1BDACDC70080FF74 /* AirInst.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = AirInst.cpp; path = b3/air/AirInst.cpp; sourceTree = "<group>"; };
0FEC855B1BDACDC70080FF74 /* AirInst.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirInst.h; path = b3/air/AirInst.h; sourceTree = "<group>"; };
0FEC855C1BDACDC70080FF74 /* AirInstInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirInstInlines.h; path = b3/air/AirInstInlines.h; sourceTree = "<group>"; };
- 0FEC855D1BDACDC70080FF74 /* AirLiveness.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirLiveness.h; path = b3/air/AirLiveness.h; sourceTree = "<group>"; };
0FEC855E1BDACDC70080FF74 /* AirPhaseScope.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = AirPhaseScope.cpp; path = b3/air/AirPhaseScope.cpp; sourceTree = "<group>"; };
0FEC855F1BDACDC70080FF74 /* AirPhaseScope.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirPhaseScope.h; path = b3/air/AirPhaseScope.h; sourceTree = "<group>"; };
0FEC85601BDACDC70080FF74 /* AirRegisterPriority.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = AirRegisterPriority.cpp; path = b3/air/AirRegisterPriority.cpp; sourceTree = "<group>"; };
@@ -3124,6 +3123,7 @@
264091FA1BE2FD4100684DB2 /* AirOpcode.opcodes */ = {isa = PBXFileReference; lastKnownFileType = text; name = AirOpcode.opcodes; path = b3/air/AirOpcode.opcodes; sourceTree = "<group>"; };
26718BA21BE99F780052017B /* AirIteratedRegisterCoalescing.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = AirIteratedRegisterCoalescing.cpp; path = b3/air/AirIteratedRegisterCoalescing.cpp; sourceTree = "<group>"; };
26718BA31BE99F780052017B /* AirIteratedRegisterCoalescing.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirIteratedRegisterCoalescing.h; path = b3/air/AirIteratedRegisterCoalescing.h; sourceTree = "<group>"; };
+ 2684D4371C00161C0081D663 /* AirLiveness.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirLiveness.h; path = b3/air/AirLiveness.h; sourceTree = "<group>"; };
269D636D1BFBE5D000101B1D /* FTLB3Output.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = FTLB3Output.h; path = ftl/FTLB3Output.h; sourceTree = "<group>"; };
26BB575F1BFC4328005F12EB /* FTLB3Output.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = FTLB3Output.cpp; path = ftl/FTLB3Output.cpp; sourceTree = "<group>"; };
2A05ABD31961DF2400341750 /* JSPropertyNameEnumerator.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = JSPropertyNameEnumerator.cpp; sourceTree = "<group>"; };
@@ -4631,7 +4631,7 @@
0FEC855C1BDACDC70080FF74 /* AirInstInlines.h */,
26718BA21BE99F780052017B /* AirIteratedRegisterCoalescing.cpp */,
26718BA31BE99F780052017B /* AirIteratedRegisterCoalescing.h */,
- 0FEC855D1BDACDC70080FF74 /* AirLiveness.h */,
+ 2684D4371C00161C0081D663 /* AirLiveness.h */,
264091FA1BE2FD4100684DB2 /* AirOpcode.opcodes */,
0FB3878C1BFBC44D00E3AB1E /* AirOptimizeBlockOrder.cpp */,
0FB3878D1BFBC44D00E3AB1E /* AirOptimizeBlockOrder.h */,
@@ -6674,7 +6674,6 @@
0FEC857E1BDACDC70080FF74 /* AirInsertionSet.h in Headers */,
0FEC85801BDACDC70080FF74 /* AirInst.h in Headers */,
0FEC85811BDACDC70080FF74 /* AirInstInlines.h in Headers */,
- 0FEC85821BDACDC70080FF74 /* AirLiveness.h in Headers */,
0FEC85841BDACDC70080FF74 /* AirPhaseScope.h in Headers */,
0FEC85861BDACDC70080FF74 /* AirRegisterPriority.h in Headers */,
0F45703D1BE45F0A0062A629 /* AirReportUsedRegisters.h in Headers */,
@@ -7697,6 +7696,7 @@
0F572D4F16879FDD00E57FBD /* ThunkGenerator.h in Headers */,
A7386556118697B400540279 /* ThunkGenerators.h in Headers */,
141448CD13A1783700F5BA1A /* TinyBloomFilter.h in Headers */,
+ 2684D4381C00161C0081D663 /* AirLiveness.h in Headers */,
0F55989817C86C5800A1E543 /* ToNativeFromValue.h in Headers */,
0F2D4DE919832DAC007D4B19 /* ToThisStatus.h in Headers */,
5D53726F0E1C54880021E549 /* Tracing.h in Headers */,
Modified: trunk/Source/_javascript_Core/b3/B3IndexMap.h (192850 => 192851)
--- trunk/Source/_javascript_Core/b3/B3IndexMap.h 2015-12-01 02:15:47 UTC (rev 192850)
+++ trunk/Source/_javascript_Core/b3/B3IndexMap.h 2015-12-01 02:26:57 UTC (rev 192851)
@@ -58,6 +58,11 @@
{
return m_vector[key->index()];
}
+
+ void clear()
+ {
+ m_vector.clear();
+ }
private:
Vector<Value> m_vector;
Modified: trunk/Source/_javascript_Core/b3/air/AirAllocateStack.cpp (192850 => 192851)
--- trunk/Source/_javascript_Core/b3/air/AirAllocateStack.cpp 2015-12-01 02:15:47 UTC (rev 192850)
+++ trunk/Source/_javascript_Core/b3/air/AirAllocateStack.cpp 2015-12-01 02:26:57 UTC (rev 192851)
@@ -136,16 +136,16 @@
}
// Now we handle the anonymous slots.
- Liveness<StackSlot*> liveness(code);
+ StackSlotLiveness liveness(code);
IndexMap<StackSlot, HashSet<StackSlot*>> interference(code.stackSlots().size());
Vector<StackSlot*> slots;
for (BasicBlock* block : code) {
- Liveness<StackSlot*>::LocalCalc localCalc(liveness, block);
+ StackSlotLiveness::LocalCalc localCalc(liveness, block);
auto interfere = [&] (Inst& inst) {
if (verbose)
- dataLog("Interfering: ", pointerListDump(localCalc.live()), "\n");
+ dataLog("Interfering: ", WTF::pointerListDump(localCalc.live()), "\n");
inst.forEachArg(
[&] (Arg& arg, Arg::Role role, Arg::Type) {
Modified: trunk/Source/_javascript_Core/b3/air/AirIteratedRegisterCoalescing.cpp (192850 => 192851)
--- trunk/Source/_javascript_Core/b3/air/AirIteratedRegisterCoalescing.cpp 2015-12-01 02:15:47 UTC (rev 192850)
+++ trunk/Source/_javascript_Core/b3/air/AirIteratedRegisterCoalescing.cpp 2015-12-01 02:26:57 UTC (rev 192851)
@@ -34,6 +34,7 @@
#include "AirLiveness.h"
#include "AirPhaseScope.h"
#include "AirRegisterPriority.h"
+#include "AirTmpInlines.h"
#include <wtf/ListDump.h>
#include <wtf/ListHashSet.h>
@@ -77,75 +78,100 @@
}
};
-
-// The speed of the alocator depends directly on how fast we can query information associated with a Tmp
-// and/or its ownership to a set.
-//
-// HashSet/HashMap operations are overly expensive for that.
-//
-// Instead of a Hash structure, Tmp are indexed directly by value in Arrays. The internal integer is used as the index
-// to reference them quickly. In some sets, we do not care about the colored regs, we still allocate the memory for them
-// and just do not use it.
template<Arg::Type type>
-struct AbsoluteTmpHelper;
-
-template<>
-struct AbsoluteTmpHelper<Arg::GP> {
- static unsigned absoluteIndex(const Tmp& tmp)
+class IteratedRegisterCoalescingAllocator {
+public:
+ IteratedRegisterCoalescingAllocator(Code& code, const HashSet<Tmp>& unspillableTmp)
+ : m_unspillableTmp(unspillableTmp)
+ , m_numberOfRegisters(regsInPriorityOrder(type).size())
{
- ASSERT(tmp.isGP());
- ASSERT(static_cast<int>(tmp.internalValue()) > 0);
- return tmp.internalValue();
+ initializeDegrees(code);
+
+ unsigned tmpArraySize = this->tmpArraySize(code);
+ m_adjacencyList.resize(tmpArraySize);
+ m_moveList.resize(tmpArraySize);
+ m_coalescedTmps.resize(tmpArraySize);
+ m_isOnSelectStack.ensureSize(tmpArraySize);
+
+ build(code);
+ allocate();
}
- static unsigned absoluteIndex(unsigned tmpIndex)
+ Tmp getAlias(Tmp tmp) const
{
- return absoluteIndex(Tmp::gpTmpForIndex(tmpIndex));
+ Tmp alias = tmp;
+ while (Tmp nextAlias = m_coalescedTmps[AbsoluteTmpMapper<type>::absoluteIndex(alias)])
+ alias = nextAlias;
+ return alias;
}
- static Tmp tmpFromAbsoluteIndex(unsigned tmpIndex)
+ Tmp getAliasWhenSpilling(Tmp tmp) const
{
- return Tmp::tmpForInternalValue(tmpIndex);
+ ASSERT_WITH_MESSAGE(!m_spilledTmp.isEmpty(), "This function is only valid for coalescing during spilling.");
+
+ if (m_coalescedTmpsAtSpill.isEmpty())
+ return tmp;
+
+ Tmp alias = tmp;
+ while (Tmp nextAlias = m_coalescedTmpsAtSpill[AbsoluteTmpMapper<type>::absoluteIndex(alias)])
+ alias = nextAlias;
+
+ ASSERT_WITH_MESSAGE(!m_spilledTmp.contains(tmp) || alias == tmp, "The aliases at spill should always be colorable. Something went horribly wrong.");
+
+ return alias;
}
-};
-template<>
-struct AbsoluteTmpHelper<Arg::FP> {
- static unsigned absoluteIndex(const Tmp& tmp)
+ const HashSet<Tmp>& spilledTmp() const { return m_spilledTmp; }
+ Reg allocatedReg(Tmp tmp) const
{
- ASSERT(tmp.isFP());
- ASSERT(static_cast<int>(tmp.internalValue()) < 0);
- return -tmp.internalValue();
+ ASSERT(!tmp.isReg());
+ ASSERT(m_coloredTmp.size());
+ ASSERT(tmp.isGP() == (type == Arg::GP));
+
+ Reg reg = m_coloredTmp[AbsoluteTmpMapper<type>::absoluteIndex(tmp)];
+ if (!reg) {
+ // We only care about Tmps that interfere. A Tmp that never interfere with anything
+ // can take any register.
+ reg = regsInPriorityOrder(type).first();
+ }
+ return reg;
}
- static unsigned absoluteIndex(unsigned tmpIndex)
+private:
+ static unsigned tmpArraySize(Code& code)
{
- return absoluteIndex(Tmp::fpTmpForIndex(tmpIndex));
+ unsigned numTmps = code.numTmps(type);
+ return AbsoluteTmpMapper<type>::absoluteIndex(numTmps);
}
- static Tmp tmpFromAbsoluteIndex(unsigned tmpIndex)
+ void initializeDegrees(Code& code)
{
- return Tmp::tmpForInternalValue(-tmpIndex);
+ unsigned tmpArraySize = this->tmpArraySize(code);
+ m_degrees.resize(tmpArraySize);
+
+ // All precolored registers have an "infinite" degree.
+ unsigned firstNonRegIndex = AbsoluteTmpMapper<type>::absoluteIndex(0);
+ for (unsigned i = 0; i < firstNonRegIndex; ++i)
+ m_degrees[i] = std::numeric_limits<unsigned>::max();
+
+ bzero(m_degrees.data() + firstNonRegIndex, (tmpArraySize - firstNonRegIndex) * sizeof(unsigned));
}
-};
-template<Arg::Type type>
-class IteratedRegisterCoalescingAllocator {
-public:
- IteratedRegisterCoalescingAllocator(Code& code, const HashSet<Tmp>& unspillableTmp)
- : m_unspillableTmp(unspillableTmp)
- , m_numberOfRegisters(regsInPriorityOrder(type).size())
+ void build(Code& code)
{
- initializeDegrees(code);
-
- unsigned tmpArraySize = this->tmpArraySize(code);
- m_adjacencyList.resize(tmpArraySize);
- m_moveList.resize(tmpArraySize);
- m_coalescedTmps.resize(tmpArraySize);
- m_isOnSelectStack.ensureSize(tmpArraySize);
+ TmpLiveness<type> liveness(code);
+ for (BasicBlock* block : code) {
+ typename TmpLiveness<type>::LocalCalc localCalc(liveness, block);
+ for (unsigned instIndex = block->size(); instIndex--;) {
+ Inst& inst = block->at(instIndex);
+ Inst* nextInst = instIndex + 1 < block->size() ? &block->at(instIndex + 1) : nullptr;
+ build(inst, nextInst, localCalc);
+ localCalc.execute(instIndex);
+ }
+ }
}
- void build(Inst& inst, Inst* nextInst, const Liveness<Tmp>::LocalCalc& localCalc)
+ void build(Inst& inst, Inst* nextInst, const typename TmpLiveness<type>::LocalCalc& localCalc)
{
inst.forEachTmpWithExtraClobberedRegs(
nextInst,
@@ -191,12 +217,12 @@
m_activeMoves.ensureSize(nextMoveIndex + 1);
for (const Arg& arg : inst.args) {
- auto& list = m_moveList[AbsoluteTmpHelper<type>::absoluteIndex(arg.tmp())];
+ auto& list = m_moveList[AbsoluteTmpMapper<type>::absoluteIndex(arg.tmp())];
list.add(nextMoveIndex);
}
for (const Tmp& liveTmp : localCalc.live()) {
- if (liveTmp != useTmp && liveTmp.isGP() == (type == Arg::GP))
+ if (liveTmp != useTmp)
addEdge(defTmp, liveTmp);
}
@@ -204,8 +230,10 @@
if (nextInst && nextInst->hasSpecial()) {
nextInst->extraEarlyClobberedRegs().forEach(
[&] (Reg reg) {
- for (const Tmp& liveTmp : localCalc.live()) {
- addEdge(Tmp(reg), liveTmp);
+ if (reg.isGPR() == (type == Arg::GP)) {
+ for (const Tmp& liveTmp : localCalc.live()) {
+ addEdge(Tmp(reg), liveTmp);
+ }
}
});
}
@@ -213,105 +241,8 @@
addEdges(inst, nextInst, localCalc.live());
}
- void allocate()
+ void addEdges(Inst& inst, Inst* nextInst, typename TmpLiveness<type>::LocalCalc::Iterable liveTmp)
{
- ASSERT_WITH_MESSAGE(m_activeMoves.size() >= m_coalescingCandidates.size(), "The activeMove set should be big enough for the quick operations of BitVector.");
-
- makeWorkList();
-
- if (debug) {
- dataLog("Interference: ", listDump(m_interferenceEdges), "\n");
- dumpInterferenceGraphInDot(WTF::dataFile());
- dataLog("Initial work list\n");
- dumpWorkLists(WTF::dataFile());
- }
-
- do {
- if (traceDebug) {
- dataLog("Before Graph simplification iteration\n");
- dumpWorkLists(WTF::dataFile());
- }
-
- if (!m_simplifyWorklist.isEmpty())
- simplify();
- else if (!m_worklistMoves.isEmpty())
- coalesce();
- else if (!m_freezeWorklist.isEmpty())
- freeze();
- else if (!m_spillWorklist.isEmpty())
- selectSpill();
-
- if (traceDebug) {
- dataLog("After Graph simplification iteration\n");
- dumpWorkLists(WTF::dataFile());
- }
- } while (!m_simplifyWorklist.isEmpty() || !m_worklistMoves.isEmpty() || !m_freezeWorklist.isEmpty() || !m_spillWorklist.isEmpty());
-
- assignColors();
- }
-
- Tmp getAlias(Tmp tmp) const
- {
- Tmp alias = tmp;
- while (Tmp nextAlias = m_coalescedTmps[AbsoluteTmpHelper<type>::absoluteIndex(alias)])
- alias = nextAlias;
- return alias;
- }
-
- Tmp getAliasWhenSpilling(Tmp tmp) const
- {
- ASSERT_WITH_MESSAGE(!m_spilledTmp.isEmpty(), "This function is only valid for coalescing during spilling.");
-
- if (m_coalescedTmpsAtSpill.isEmpty())
- return tmp;
-
- Tmp alias = tmp;
- while (Tmp nextAlias = m_coalescedTmpsAtSpill[AbsoluteTmpHelper<type>::absoluteIndex(alias)])
- alias = nextAlias;
-
- ASSERT_WITH_MESSAGE(!m_spilledTmp.contains(tmp) || alias == tmp, "The aliases at spill should always be colorable. Something went horribly wrong.");
-
- return alias;
- }
-
- const HashSet<Tmp>& spilledTmp() const { return m_spilledTmp; }
- Reg allocatedReg(Tmp tmp) const
- {
- ASSERT(!tmp.isReg());
- ASSERT(m_coloredTmp.size());
- ASSERT(tmp.isGP() == (type == Arg::GP));
-
- Reg reg = m_coloredTmp[AbsoluteTmpHelper<type>::absoluteIndex(tmp)];
- if (!reg) {
- // We only care about Tmps that interfere. A Tmp that never interfere with anything
- // can take any register.
- reg = regsInPriorityOrder(type).first();
- }
- return reg;
- }
-
-private:
- static unsigned tmpArraySize(Code& code)
- {
- unsigned numTmps = code.numTmps(type);
- return AbsoluteTmpHelper<type>::absoluteIndex(numTmps);
- }
-
- void initializeDegrees(Code& code)
- {
- unsigned tmpArraySize = this->tmpArraySize(code);
- m_degrees.resize(tmpArraySize);
-
- // All precolored registers have an "infinite" degree.
- unsigned firstNonRegIndex = AbsoluteTmpHelper<type>::absoluteIndex(0);
- for (unsigned i = 0; i < firstNonRegIndex; ++i)
- m_degrees[i] = std::numeric_limits<unsigned>::max();
-
- bzero(m_degrees.data() + firstNonRegIndex, (tmpArraySize - firstNonRegIndex) * sizeof(unsigned));
- }
-
- void addEdges(Inst& inst, Inst* nextInst, const HashSet<Tmp>& liveTmp)
- {
// All the Def()s interfere with everthing live.
inst.forEachTmpWithExtraClobberedRegs(
nextInst,
@@ -333,32 +264,32 @@
if (m_interferenceEdges.add(InterferenceEdge(a, b)).isNewEntry) {
if (!a.isReg()) {
- ASSERT(!m_adjacencyList[AbsoluteTmpHelper<type>::absoluteIndex(a)].contains(b));
- m_adjacencyList[AbsoluteTmpHelper<type>::absoluteIndex(a)].append(b);
- m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(a)]++;
+ ASSERT(!m_adjacencyList[AbsoluteTmpMapper<type>::absoluteIndex(a)].contains(b));
+ m_adjacencyList[AbsoluteTmpMapper<type>::absoluteIndex(a)].append(b);
+ m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(a)]++;
}
if (!b.isReg()) {
- ASSERT(!m_adjacencyList[AbsoluteTmpHelper<type>::absoluteIndex(b)].contains(a));
- m_adjacencyList[AbsoluteTmpHelper<type>::absoluteIndex(b)].append(a);
- m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(b)]++;
+ ASSERT(!m_adjacencyList[AbsoluteTmpMapper<type>::absoluteIndex(b)].contains(a));
+ m_adjacencyList[AbsoluteTmpMapper<type>::absoluteIndex(b)].append(a);
+ m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(b)]++;
}
}
}
void makeWorkList()
{
- unsigned firstNonRegIndex = AbsoluteTmpHelper<type>::absoluteIndex(0);
+ unsigned firstNonRegIndex = AbsoluteTmpMapper<type>::absoluteIndex(0);
for (unsigned i = firstNonRegIndex; i < m_degrees.size(); ++i) {
unsigned degree = m_degrees[i];
if (!degree)
continue;
- Tmp tmp = AbsoluteTmpHelper<type>::tmpFromAbsoluteIndex(i);
+ Tmp tmp = AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(i);
if (degree >= m_numberOfRegisters)
m_spillWorklist.add(tmp);
- else if (!m_moveList[AbsoluteTmpHelper<type>::absoluteIndex(tmp)].isEmpty())
+ else if (!m_moveList[AbsoluteTmpMapper<type>::absoluteIndex(tmp)].isEmpty())
m_freezeWorklist.add(tmp);
else
m_simplifyWorklist.append(tmp);
@@ -370,9 +301,9 @@
Tmp last = m_simplifyWorklist.takeLast();
ASSERT(!m_selectStack.contains(last));
- ASSERT(!m_isOnSelectStack.get(AbsoluteTmpHelper<type>::absoluteIndex(last)));
+ ASSERT(!m_isOnSelectStack.get(AbsoluteTmpMapper<type>::absoluteIndex(last)));
m_selectStack.append(last);
- m_isOnSelectStack.quickSet(AbsoluteTmpHelper<type>::absoluteIndex(last));
+ m_isOnSelectStack.quickSet(AbsoluteTmpMapper<type>::absoluteIndex(last));
forEachAdjacent(last, [this](Tmp adjacentTmp) {
decrementDegree(adjacentTmp);
@@ -382,7 +313,7 @@
template<typename Function>
void forEachAdjacent(Tmp tmp, Function function)
{
- for (Tmp adjacentTmp : m_adjacencyList[AbsoluteTmpHelper<type>::absoluteIndex(tmp)]) {
+ for (Tmp adjacentTmp : m_adjacencyList[AbsoluteTmpMapper<type>::absoluteIndex(tmp)]) {
if (!hasBeenSimplified(adjacentTmp))
function(adjacentTmp);
}
@@ -390,14 +321,14 @@
bool hasBeenSimplified(Tmp tmp)
{
- return m_isOnSelectStack.quickGet(AbsoluteTmpHelper<type>::absoluteIndex(tmp)) || !!m_coalescedTmps[AbsoluteTmpHelper<type>::absoluteIndex(tmp)];
+ return m_isOnSelectStack.quickGet(AbsoluteTmpMapper<type>::absoluteIndex(tmp)) || !!m_coalescedTmps[AbsoluteTmpMapper<type>::absoluteIndex(tmp)];
}
void decrementDegree(Tmp tmp)
{
- ASSERT(m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(tmp)]);
+ ASSERT(m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(tmp)]);
- unsigned oldDegree = m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(tmp)]--;
+ unsigned oldDegree = m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(tmp)]--;
if (oldDegree == m_numberOfRegisters) {
enableMovesOnValueAndAdjacents(tmp);
m_spillWorklist.remove(tmp);
@@ -411,7 +342,7 @@
template<typename Function>
void forEachNodeMoves(Tmp tmp, Function function)
{
- for (unsigned moveIndex : m_moveList[AbsoluteTmpHelper<type>::absoluteIndex(tmp)]) {
+ for (unsigned moveIndex : m_moveList[AbsoluteTmpMapper<type>::absoluteIndex(tmp)]) {
if (m_activeMoves.quickGet(moveIndex) || m_worklistMoves.contains(moveIndex))
function(moveIndex);
}
@@ -419,7 +350,7 @@
bool isMoveRelated(Tmp tmp)
{
- for (unsigned moveIndex : m_moveList[AbsoluteTmpHelper<type>::absoluteIndex(tmp)]) {
+ for (unsigned moveIndex : m_moveList[AbsoluteTmpMapper<type>::absoluteIndex(tmp)]) {
if (m_activeMoves.quickGet(moveIndex) || m_worklistMoves.contains(moveIndex))
return true;
}
@@ -428,7 +359,7 @@
void enableMovesOnValue(Tmp tmp)
{
- for (unsigned moveIndex : m_moveList[AbsoluteTmpHelper<type>::absoluteIndex(tmp)]) {
+ for (unsigned moveIndex : m_moveList[AbsoluteTmpMapper<type>::absoluteIndex(tmp)]) {
if (m_activeMoves.quickClear(moveIndex))
m_worklistMoves.returnMove(moveIndex);
}
@@ -500,11 +431,11 @@
// If any adjacent of the non-colored node is not an adjacent of the colored node AND has a degree >= K
// there is a risk that this node needs to have the same color as our precolored node. If we coalesce such
// move, we may create an uncolorable graph.
- const auto& adjacentsOfV = m_adjacencyList[AbsoluteTmpHelper<type>::absoluteIndex(v)];
+ const auto& adjacentsOfV = m_adjacencyList[AbsoluteTmpMapper<type>::absoluteIndex(v)];
for (Tmp adjacentTmp : adjacentsOfV) {
if (!adjacentTmp.isReg()
&& !hasBeenSimplified(adjacentTmp)
- && m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(adjacentTmp)] >= m_numberOfRegisters
+ && m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(adjacentTmp)] >= m_numberOfRegisters
&& !m_interferenceEdges.contains(InterferenceEdge(u, adjacentTmp)))
return false;
}
@@ -522,8 +453,8 @@
ASSERT(!u.isReg());
ASSERT(!v.isReg());
- const auto& adjacentsOfU = m_adjacencyList[AbsoluteTmpHelper<type>::absoluteIndex(u)];
- const auto& adjacentsOfV = m_adjacencyList[AbsoluteTmpHelper<type>::absoluteIndex(v)];
+ const auto& adjacentsOfU = m_adjacencyList[AbsoluteTmpMapper<type>::absoluteIndex(u)];
+ const auto& adjacentsOfV = m_adjacencyList[AbsoluteTmpMapper<type>::absoluteIndex(v)];
if (adjacentsOfU.size() + adjacentsOfV.size() < m_numberOfRegisters) {
// Shortcut: if the total number of adjacents is less than the number of register, the condition is always met.
@@ -535,7 +466,7 @@
for (Tmp adjacentTmp : adjacentsOfU) {
ASSERT(adjacentTmp != v);
ASSERT(adjacentTmp != u);
- if (!hasBeenSimplified(adjacentTmp) && m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(adjacentTmp)] >= m_numberOfRegisters) {
+ if (!hasBeenSimplified(adjacentTmp) && m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(adjacentTmp)] >= m_numberOfRegisters) {
auto addResult = highOrderAdjacents.add(adjacentTmp);
if (addResult.isNewEntry && highOrderAdjacents.size() >= m_numberOfRegisters)
return false;
@@ -544,7 +475,7 @@
for (Tmp adjacentTmp : adjacentsOfV) {
ASSERT(adjacentTmp != u);
ASSERT(adjacentTmp != v);
- if (!hasBeenSimplified(adjacentTmp) && m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(adjacentTmp)] >= m_numberOfRegisters) {
+ if (!hasBeenSimplified(adjacentTmp) && m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(adjacentTmp)] >= m_numberOfRegisters) {
auto addResult = highOrderAdjacents.add(adjacentTmp);
if (addResult.isNewEntry && highOrderAdjacents.size() >= m_numberOfRegisters)
return false;
@@ -557,7 +488,7 @@
void addWorkList(Tmp tmp)
{
- if (!tmp.isReg() && m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(tmp)] < m_numberOfRegisters && !isMoveRelated(tmp)) {
+ if (!tmp.isReg() && m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(tmp)] < m_numberOfRegisters && !isMoveRelated(tmp)) {
m_freezeWorklist.remove(tmp);
m_simplifyWorklist.append(tmp);
}
@@ -568,18 +499,18 @@
if (!m_freezeWorklist.remove(v))
m_spillWorklist.remove(v);
- ASSERT(!m_coalescedTmps[AbsoluteTmpHelper<type>::absoluteIndex(v)]);
- m_coalescedTmps[AbsoluteTmpHelper<type>::absoluteIndex(v)] = u;
+ ASSERT(!m_coalescedTmps[AbsoluteTmpMapper<type>::absoluteIndex(v)]);
+ m_coalescedTmps[AbsoluteTmpMapper<type>::absoluteIndex(v)] = u;
- auto& vMoves = m_moveList[AbsoluteTmpHelper<type>::absoluteIndex(v)];
- m_moveList[AbsoluteTmpHelper<type>::absoluteIndex(u)].add(vMoves.begin(), vMoves.end());
+ auto& vMoves = m_moveList[AbsoluteTmpMapper<type>::absoluteIndex(v)];
+ m_moveList[AbsoluteTmpMapper<type>::absoluteIndex(u)].add(vMoves.begin(), vMoves.end());
forEachAdjacent(v, [this, u] (Tmp adjacentTmp) {
addEdge(adjacentTmp, u);
decrementDegree(adjacentTmp);
});
- if (m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(u)] >= m_numberOfRegisters && m_freezeWorklist.remove(u))
+ if (m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(u)] >= m_numberOfRegisters && m_freezeWorklist.remove(u))
m_spillWorklist.add(u);
}
@@ -600,7 +531,7 @@
const MoveOperands& moveOperands = m_coalescingCandidates[moveIndex];
Tmp originalOtherTmp = moveOperands.src != tmp ? moveOperands.src : moveOperands.dst;
Tmp otherTmp = getAlias(originalOtherTmp);
- if (m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(otherTmp)] < m_numberOfRegisters && !isMoveRelated(otherTmp)) {
+ if (m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(otherTmp)] < m_numberOfRegisters && !isMoveRelated(otherTmp)) {
if (m_freezeWorklist.remove(otherTmp))
m_simplifyWorklist.append(otherTmp);
}
@@ -625,11 +556,11 @@
RELEASE_ASSERT_WITH_MESSAGE(iterator != m_spillWorklist.end(), "It is not possible to color the Air graph with the number of available registers.");
auto victimIterator = iterator;
- unsigned maxDegree = m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(*iterator)];
+ unsigned maxDegree = m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(*iterator)];
++iterator;
for (;iterator != m_spillWorklist.end(); ++iterator) {
- unsigned tmpDegree = m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(*iterator)];
+ unsigned tmpDegree = m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(*iterator)];
if (tmpDegree > maxDegree) {
if (m_unspillableTmp.contains(*iterator))
continue;
@@ -645,6 +576,43 @@
freezeMoves(victimTmp);
}
+ void allocate()
+ {
+ ASSERT_WITH_MESSAGE(m_activeMoves.size() >= m_coalescingCandidates.size(), "The activeMove set should be big enough for the quick operations of BitVector.");
+
+ makeWorkList();
+
+ if (debug) {
+ dataLog("Interference: ", listDump(m_interferenceEdges), "\n");
+ dumpInterferenceGraphInDot(WTF::dataFile());
+ dataLog("Initial work list\n");
+ dumpWorkLists(WTF::dataFile());
+ }
+
+ do {
+ if (traceDebug) {
+ dataLog("Before Graph simplification iteration\n");
+ dumpWorkLists(WTF::dataFile());
+ }
+
+ if (!m_simplifyWorklist.isEmpty())
+ simplify();
+ else if (!m_worklistMoves.isEmpty())
+ coalesce();
+ else if (!m_freezeWorklist.isEmpty())
+ freeze();
+ else if (!m_spillWorklist.isEmpty())
+ selectSpill();
+
+ if (traceDebug) {
+ dataLog("After Graph simplification iteration\n");
+ dumpWorkLists(WTF::dataFile());
+ }
+ } while (!m_simplifyWorklist.isEmpty() || !m_worklistMoves.isEmpty() || !m_freezeWorklist.isEmpty() || !m_spillWorklist.isEmpty());
+
+ assignColors();
+ }
+
void assignColors()
{
ASSERT(m_simplifyWorklist.isEmpty());
@@ -668,17 +636,17 @@
while (!m_selectStack.isEmpty()) {
Tmp tmp = m_selectStack.takeLast();
ASSERT(!tmp.isReg());
- ASSERT(!m_coloredTmp[AbsoluteTmpHelper<type>::absoluteIndex(tmp)]);
+ ASSERT(!m_coloredTmp[AbsoluteTmpMapper<type>::absoluteIndex(tmp)]);
RegisterSet coloredRegisters;
- for (Tmp adjacentTmp : m_adjacencyList[AbsoluteTmpHelper<type>::absoluteIndex(tmp)]) {
+ for (Tmp adjacentTmp : m_adjacencyList[AbsoluteTmpMapper<type>::absoluteIndex(tmp)]) {
Tmp aliasTmp = getAlias(adjacentTmp);
if (aliasTmp.isReg()) {
coloredRegisters.set(aliasTmp.reg());
continue;
}
- Reg reg = m_coloredTmp[AbsoluteTmpHelper<type>::absoluteIndex(aliasTmp)];
+ Reg reg = m_coloredTmp[AbsoluteTmpMapper<type>::absoluteIndex(aliasTmp)];
if (reg)
coloredRegisters.set(reg);
}
@@ -686,7 +654,7 @@
bool colorAssigned = false;
for (Reg reg : registersInPriorityOrder) {
if (!coloredRegisters.get(reg)) {
- m_coloredTmp[AbsoluteTmpHelper<type>::absoluteIndex(tmp)] = reg;
+ m_coloredTmp[AbsoluteTmpMapper<type>::absoluteIndex(tmp)] = reg;
colorAssigned = true;
break;
}
@@ -718,7 +686,7 @@
}
for (const auto& tmp : tmpsWithInterferences)
- out.print(" ", tmp.internalValue(), " [label=\"", tmp, " (", m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(tmp)], ")\"];\n");
+ out.print(" ", tmp.internalValue(), " [label=\"", tmp, " (", m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(tmp)], ")\"];\n");
for (const auto& edge : m_interferenceEdges)
out.print(" ", edge.first().internalValue(), " -- ", edge.second().internalValue(), ";\n");
@@ -1039,23 +1007,12 @@
}
template<Arg::Type type>
-static void iteratedRegisterCoalescingOnType(Code& code, HashSet<Tmp>& unspillableTmps, unsigned& numIterations)
+static void iteratedRegisterCoalescingOnType(Code& code, unsigned& numIterations)
{
+ HashSet<Tmp> unspillableTmps;
while (true) {
numIterations++;
IteratedRegisterCoalescingAllocator<type> allocator(code, unspillableTmps);
- Liveness<Tmp> liveness(code);
- for (BasicBlock* block : code) {
- Liveness<Tmp>::LocalCalc localCalc(liveness, block);
- for (unsigned instIndex = block->size(); instIndex--;) {
- Inst& inst = block->at(instIndex);
- Inst* nextInst = instIndex + 1 < block->size() ? &block->at(instIndex + 1) : nullptr;
- allocator.build(inst, nextInst, localCalc);
- localCalc.execute(instIndex);
- }
- }
-
- allocator.allocate();
if (allocator.spilledTmp().isEmpty()) {
assignRegisterToTmpInProgram(code, allocator);
return;
@@ -1068,56 +1025,11 @@
{
PhaseScope phaseScope(code, "iteratedRegisterCoalescing");
- bool gpIsColored = false;
- bool fpIsColored = false;
unsigned numIterations = 0;
- HashSet<Tmp> unspillableGPs;
- HashSet<Tmp> unspillableFPs;
+ iteratedRegisterCoalescingOnType<Arg::GP>(code, numIterations);
+ iteratedRegisterCoalescingOnType<Arg::FP>(code, numIterations);
- // First we run both allocator together as long as they both spill.
- while (!gpIsColored && !fpIsColored) {
- numIterations++;
- IteratedRegisterCoalescingAllocator<Arg::GP> gpAllocator(code, unspillableGPs);
- IteratedRegisterCoalescingAllocator<Arg::FP> fpAllocator(code, unspillableFPs);
-
- // Liveness Analysis can be prohibitively expensive. It is shared
- // between the two allocators to avoid doing it twice.
- Liveness<Tmp> liveness(code);
- for (BasicBlock* block : code) {
- Liveness<Tmp>::LocalCalc localCalc(liveness, block);
- for (unsigned instIndex = block->size(); instIndex--;) {
- Inst& inst = block->at(instIndex);
- Inst* nextInst = instIndex + 1 < block->size() ? &block->at(instIndex + 1) : nullptr;
-
- gpAllocator.build(inst, nextInst, localCalc);
- fpAllocator.build(inst, nextInst, localCalc);
-
- localCalc.execute(instIndex);
- }
- }
-
- gpAllocator.allocate();
- fpAllocator.allocate();
-
- if (gpAllocator.spilledTmp().isEmpty()) {
- assignRegisterToTmpInProgram(code, gpAllocator);
- gpIsColored = true;
- } else
- addSpillAndFillToProgram<Arg::GP>(code, gpAllocator, unspillableGPs);
-
- if (fpAllocator.spilledTmp().isEmpty()) {
- assignRegisterToTmpInProgram(code, fpAllocator);
- fpIsColored = true;
- } else
- addSpillAndFillToProgram<Arg::FP>(code, fpAllocator, unspillableFPs);
- };
-
- if (!gpIsColored)
- iteratedRegisterCoalescingOnType<Arg::GP>(code, unspillableGPs, numIterations);
- if (!fpIsColored)
- iteratedRegisterCoalescingOnType<Arg::FP>(code, unspillableFPs, numIterations);
-
if (reportStats)
dataLog("Num iterations = ", numIterations, "\n");
}
Modified: trunk/Source/_javascript_Core/b3/air/AirLiveness.h (192850 => 192851)
--- trunk/Source/_javascript_Core/b3/air/AirLiveness.h 2015-12-01 02:15:47 UTC (rev 192850)
+++ trunk/Source/_javascript_Core/b3/air/AirLiveness.h 2015-12-01 02:26:57 UTC (rev 192851)
@@ -20,7 +20,7 @@
* 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.
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#ifndef AirLiveness_h
@@ -29,130 +29,236 @@
#if ENABLE(B3_JIT)
#include "AirBasicBlock.h"
+#include "AirTmpInlines.h"
#include "B3IndexMap.h"
#include "B3IndexSet.h"
+#include <wtf/IndexSparseSet.h>
namespace JSC { namespace B3 { namespace Air {
-// You can compute liveness over Tmp's or over Arg's. If you compute over Arg's, you get both
-// stack liveness and tmp liveness.
-template<typename Thing>
-class Liveness {
-public:
- template<typename T>
- static bool isAlive(const T& thing) { return thing.isAlive(); }
+template<Arg::Type adapterType>
+struct TmpLivenessAdapter {
+ typedef Tmp Thing;
+ typedef HashSet<unsigned> IndexSet;
- static bool isAlive(StackSlot* slot) { return slot->kind() == StackSlotKind::Anonymous; }
-
- Liveness(Code& code)
+ TmpLivenessAdapter(Code&) { }
+
+ static unsigned maxIndex(Code& code)
{
- m_liveAtHead.resize(code.size());
- m_liveAtTail.resize(code.size());
+ unsigned numTmps = code.numTmps(adapterType);
+ return AbsoluteTmpMapper<adapterType>::absoluteIndex(numTmps);
+ }
+ static bool acceptsType(Arg::Type type) { return type == adapterType; }
+ static unsigned valueToIndex(Tmp tmp) { return AbsoluteTmpMapper<adapterType>::absoluteIndex(tmp); }
+ static Tmp indexToValue(unsigned index) { return AbsoluteTmpMapper<adapterType>::tmpFromAbsoluteIndex(index); }
+};
+struct StackSlotLivenessAdapter {
+ typedef StackSlot* Thing;
+ typedef HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> IndexSet;
+
+ StackSlotLivenessAdapter(Code& code)
+ : m_code(code)
+ {
+ }
+
+ static unsigned maxIndex(Code& code)
+ {
+ return code.stackSlots().size() - 1;
+ }
+ static bool acceptsType(Arg::Type) { return true; }
+ static unsigned valueToIndex(StackSlot* stackSlot) { return stackSlot->index(); }
+ StackSlot* indexToValue(unsigned index) { return m_code.stackSlots()[index]; }
+
+private:
+ Code& m_code;
+};
+
+template<typename Adapter>
+class AbstractLiveness : private Adapter {
+ struct Workset;
+public:
+ AbstractLiveness(Code& code)
+ : Adapter(code)
+ , m_workset(Adapter::maxIndex(code))
+ , m_liveAtHead(code.size())
+ , m_liveAtTail(code.size())
+ {
// The liveAtTail of each block automatically contains the LateUse's of the terminal.
for (BasicBlock* block : code) {
- HashSet<Thing>& live = m_liveAtTail[block];
- block->last().forEach<Thing>(
- [&] (Thing& thing, Arg::Role role, Arg::Type) {
- if (Arg::isLateUse(role))
- live.add(thing);
+ typename Adapter::IndexSet& liveAtTail = m_liveAtTail[block];
+
+ block->last().forEach<typename Adapter::Thing>(
+ [&] (typename Adapter::Thing& thing, Arg::Role role, Arg::Type type) {
+ if (Arg::isLateUse(role) && Adapter::acceptsType(type))
+ liveAtTail.add(Adapter::valueToIndex(thing));
});
}
- IndexSet<BasicBlock> seen;
+ // Blocks with new live values at tail.
+ BitVector dirtyBlocks;
+ for (size_t blockIndex = 0; blockIndex < code.size(); ++blockIndex)
+ dirtyBlocks.set(blockIndex);
- bool changed = true;
- while (changed) {
+ bool changed;
+ do {
changed = false;
for (size_t blockIndex = code.size(); blockIndex--;) {
BasicBlock* block = code.at(blockIndex);
if (!block)
continue;
+
+ if (!dirtyBlocks.quickClear(blockIndex))
+ continue;
+
LocalCalc localCalc(*this, block);
for (size_t instIndex = block->size(); instIndex--;)
localCalc.execute(instIndex);
- bool firstTime = seen.add(block);
- if (!firstTime && localCalc.live() == m_liveAtHead[block])
+
+ Vector<unsigned>& 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;
- changed = true;
+
+ liveAtHead.reserveCapacity(liveAtHead.size() + m_workset.size());
+ for (unsigned newValue : m_workset)
+ liveAtHead.uncheckedAppend(newValue);
+
for (BasicBlock* predecessor : block->predecessors()) {
- m_liveAtTail[predecessor].add(
- localCalc.live().begin(), localCalc.live().end());
+ typename Adapter::IndexSet& liveAtTail = m_liveAtTail[predecessor];
+ for (unsigned newValue : m_workset) {
+ if (liveAtTail.add(newValue)) {
+ if (dirtyBlocks.quickSet(predecessor->index()))
+ changed = true;
+ }
+ }
}
- m_liveAtHead[block] = localCalc.takeLive();
}
- }
- }
+ } while (changed);
- const HashSet<Thing>& liveAtHead(BasicBlock* block) const
- {
- return m_liveAtHead[block];
+ m_liveAtHead.clear();
}
- const HashSet<Thing>& liveAtTail(BasicBlock* block) const
- {
- return m_liveAtTail[block];
- }
-
// This calculator has to be run in reverse.
class LocalCalc {
public:
- LocalCalc(Liveness& liveness, BasicBlock* block)
- : m_live(liveness.liveAtTail(block))
+ LocalCalc(AbstractLiveness& liveness, BasicBlock* block)
+ : m_liveness(liveness)
, m_block(block)
{
+ auto& workset = liveness.m_workset;
+ workset.clear();
+ typename Adapter::IndexSet& liveAtTail = liveness.m_liveAtTail[block];
+ for (unsigned index : liveAtTail)
+ workset.add(index);
}
- const HashSet<Thing>& live() const { return m_live; }
- HashSet<Thing>&& takeLive() { return WTF::move(m_live); }
+ struct Iterator {
+ 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;
+ };
+
+ struct Iterable {
+ Iterable(AbstractLiveness& liveness)
+ : m_liveness(liveness)
+ {
+ }
+
+ Iterator begin() const { return Iterator(m_liveness, m_liveness.m_workset.begin()); }
+ Iterator end() const { return Iterator(m_liveness, m_liveness.m_workset.end()); }
+
+ private:
+ AbstractLiveness& m_liveness;
+ };
+
+ Iterable live() const
+ {
+ return Iterable(m_liveness);
+ }
+
void execute(unsigned instIndex)
{
Inst& inst = m_block->at(instIndex);
-
+ auto& workset = m_liveness.m_workset;
// First handle def's.
- inst.forEach<Thing>(
- [this] (Thing& arg, Arg::Role role, Arg::Type) {
- if (!isAlive(arg))
- return;
- if (Arg::isDef(role))
- m_live.remove(arg);
+ inst.forEach<typename Adapter::Thing>(
+ [&] (typename Adapter::Thing& thing, Arg::Role role, Arg::Type type) {
+ if (Arg::isDef(role) && Adapter::acceptsType(type))
+ workset.remove(Adapter::valueToIndex(thing));
});
// Then handle use's.
- inst.forEach<Thing>(
- [this] (Thing& arg, Arg::Role role, Arg::Type) {
- if (!isAlive(arg))
- return;
- if (Arg::isEarlyUse(role))
- m_live.add(arg);
+ inst.forEach<typename Adapter::Thing>(
+ [&] (typename Adapter::Thing& thing, Arg::Role role, Arg::Type type) {
+ if (Arg::isEarlyUse(role) && Adapter::acceptsType(type))
+ 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<Thing>(
- [this] (Thing& arg, Arg::Role role, Arg::Type) {
- if (!Arg::isLateUse(role))
- return;
- if (isAlive(arg))
- m_live.add(arg);
+ prevInst.forEach<typename Adapter::Thing>(
+ [&] (typename Adapter::Thing& thing, Arg::Role role, Arg::Type type) {
+ if (Arg::isLateUse(role) && Adapter::acceptsType(type))
+ workset.add(Adapter::valueToIndex(thing));
});
}
}
private:
- HashSet<Thing> m_live;
+ AbstractLiveness& m_liveness;
BasicBlock* m_block;
};
private:
- IndexMap<BasicBlock, HashSet<Thing>> m_liveAtHead;
- IndexMap<BasicBlock, HashSet<Thing>> m_liveAtTail;
+ friend class LocalCalc;
+ friend struct LocalCalc::Iterable;
+
+ IndexSparseSet<UnsafeVectorOverflow> m_workset;
+ IndexMap<BasicBlock, Vector<unsigned>> m_liveAtHead;
+ IndexMap<BasicBlock, typename Adapter::IndexSet> m_liveAtTail;
};
+template<Arg::Type type>
+using TmpLiveness = AbstractLiveness<TmpLivenessAdapter<type>>;
+
+typedef AbstractLiveness<TmpLivenessAdapter<Arg::GP>> GPLiveness;
+typedef AbstractLiveness<TmpLivenessAdapter<Arg::FP>> FPLiveness;
+typedef AbstractLiveness<StackSlotLivenessAdapter> StackSlotLiveness;
+
} } } // namespace JSC::B3::Air
#endif // ENABLE(B3_JIT)
Modified: trunk/Source/_javascript_Core/b3/air/AirReportUsedRegisters.cpp (192850 => 192851)
--- trunk/Source/_javascript_Core/b3/air/AirReportUsedRegisters.cpp 2015-12-01 02:15:47 UTC (rev 192850)
+++ trunk/Source/_javascript_Core/b3/air/AirReportUsedRegisters.cpp 2015-12-01 02:26:57 UTC (rev 192851)
@@ -41,22 +41,29 @@
// FIXME: We should tell liveness to only track Regs.
// https://bugs.webkit.org/show_bug.cgi?id=150751
- Liveness<Tmp> liveness(code);
+ GPLiveness gpLiveness(code);
+ FPLiveness fpLiveness(code);
for (BasicBlock* block : code) {
- Liveness<Tmp>::LocalCalc localCalc(liveness, block);
+ GPLiveness::LocalCalc gpLocalCalc(gpLiveness, block);
+ FPLiveness::LocalCalc fpLocalCalc(fpLiveness, block);
for (unsigned instIndex = block->size(); instIndex--;) {
Inst& inst = block->at(instIndex);
if (inst.hasSpecial()) {
RegisterSet registerSet;
- for (Tmp tmp : localCalc.live()) {
- if (tmp.isReg())
- registerSet.set(tmp.reg());
+ for (Tmp tmp : gpLocalCalc.live()) {
+ ASSERT(tmp.isGP());
+ registerSet.set(tmp.reg());
}
+ for (Tmp tmp : fpLocalCalc.live()) {
+ ASSERT(tmp.isFP());
+ registerSet.set(tmp.reg());
+ }
inst.reportUsedRegisters(registerSet);
}
- localCalc.execute(instIndex);
+ gpLocalCalc.execute(instIndex);
+ fpLocalCalc.execute(instIndex);
}
}
}
Modified: trunk/Source/_javascript_Core/b3/air/AirSpillEverything.cpp (192850 => 192851)
--- trunk/Source/_javascript_Core/b3/air/AirSpillEverything.cpp 2015-12-01 02:15:47 UTC (rev 192850)
+++ trunk/Source/_javascript_Core/b3/air/AirSpillEverything.cpp 2015-12-01 02:26:57 UTC (rev 192851)
@@ -44,17 +44,24 @@
// We want to know the set of registers used at every point in every basic block.
IndexMap<BasicBlock, Vector<RegisterSet>> usedRegisters(code.size());
- Liveness<Tmp> liveness(code);
+ GPLiveness gpLiveness(code);
+ FPLiveness fpLiveness(code);
for (BasicBlock* block : code) {
- Liveness<Tmp>::LocalCalc localCalc(liveness, block);
+ GPLiveness::LocalCalc gpLocalCalc(gpLiveness, block);
+ FPLiveness::LocalCalc fpLocalCalc(fpLiveness, block);
+
usedRegisters[block].resize(block->size() + 1);
auto setUsedRegisters = [&] (unsigned index, Inst& inst) {
RegisterSet& registerSet = usedRegisters[block][index];
- for (Tmp tmp : localCalc.live()) {
+ for (Tmp tmp : gpLocalCalc.live()) {
if (tmp.isReg())
registerSet.set(tmp.reg());
}
+ for (Tmp tmp : fpLocalCalc.live()) {
+ if (tmp.isReg())
+ registerSet.set(tmp.reg());
+ }
// Gotta account for dead assignments to registers. These may happen because the input
// code is suboptimal.
@@ -69,7 +76,8 @@
for (unsigned instIndex = block->size(); instIndex--;) {
Inst& inst = block->at(instIndex);
setUsedRegisters(instIndex + 1, inst);
- localCalc.execute(instIndex);
+ gpLocalCalc.execute(instIndex);
+ fpLocalCalc.execute(instIndex);
}
Inst nop;
Modified: trunk/Source/_javascript_Core/b3/air/AirTmpInlines.h (192850 => 192851)
--- trunk/Source/_javascript_Core/b3/air/AirTmpInlines.h 2015-12-01 02:15:47 UTC (rev 192850)
+++ trunk/Source/_javascript_Core/b3/air/AirTmpInlines.h 2015-12-01 02:26:57 UTC (rev 192851)
@@ -38,6 +38,51 @@
*this = arg.tmp();
}
+// When a Hash structure is too slow or when Sets contains most values, you can
+// use direct array addressing with Tmps.
+template<Arg::Type type>
+struct AbsoluteTmpMapper;
+
+template<>
+struct AbsoluteTmpMapper<Arg::GP> {
+ static unsigned absoluteIndex(const Tmp& tmp)
+ {
+ ASSERT(tmp.isGP());
+ ASSERT(static_cast<int>(tmp.internalValue()) > 0);
+ return tmp.internalValue();
+ }
+
+ static unsigned absoluteIndex(unsigned tmpIndex)
+ {
+ return absoluteIndex(Tmp::gpTmpForIndex(tmpIndex));
+ }
+
+ static Tmp tmpFromAbsoluteIndex(unsigned tmpIndex)
+ {
+ return Tmp::tmpForInternalValue(tmpIndex);
+ }
+};
+
+template<>
+struct AbsoluteTmpMapper<Arg::FP> {
+ static unsigned absoluteIndex(const Tmp& tmp)
+ {
+ ASSERT(tmp.isFP());
+ ASSERT(static_cast<int>(tmp.internalValue()) < 0);
+ return -tmp.internalValue();
+ }
+
+ static unsigned absoluteIndex(unsigned tmpIndex)
+ {
+ return absoluteIndex(Tmp::fpTmpForIndex(tmpIndex));
+ }
+
+ static Tmp tmpFromAbsoluteIndex(unsigned tmpIndex)
+ {
+ return Tmp::tmpForInternalValue(-tmpIndex);
+ }
+};
+
} } } // namespace JSC::B3::Air
#endif // ENABLE(B3_JIT)
Modified: trunk/Source/WTF/ChangeLog (192850 => 192851)
--- trunk/Source/WTF/ChangeLog 2015-12-01 02:15:47 UTC (rev 192850)
+++ trunk/Source/WTF/ChangeLog 2015-12-01 02:26:57 UTC (rev 192851)
@@ -1,3 +1,20 @@
+2015-11-30 Benjamin Poulain <bpoul...@apple.com>
+
+ [JSC] Speed up Air Liveness Analysis on Tmps
+ https://bugs.webkit.org/show_bug.cgi?id=151556
+
+ Reviewed by Filip Pizlo.
+
+ * WTF.xcodeproj/project.pbxproj:
+ * wtf/IndexSparseSet.h: Added.
+ (WTF::IndexSparseSet<OverflowHandler>::IndexSparseSet):
+ (WTF::IndexSparseSet<OverflowHandler>::add):
+ (WTF::IndexSparseSet<OverflowHandler>::remove):
+ (WTF::IndexSparseSet<OverflowHandler>::clear):
+ (WTF::IndexSparseSet<OverflowHandler>::size):
+ (WTF::IndexSparseSet<OverflowHandler>::isEmpty):
+ (WTF::IndexSparseSet<OverflowHandler>::contains):
+
2015-11-30 Tim Horton <timothy_hor...@apple.com>
Get rid of the !USE(ASYNC_NSTEXTINPUTCLIENT) codepath
Modified: trunk/Source/WTF/WTF.xcodeproj/project.pbxproj (192850 => 192851)
--- trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2015-12-01 02:15:47 UTC (rev 192850)
+++ trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2015-12-01 02:26:57 UTC (rev 192851)
@@ -86,6 +86,7 @@
1FA47C8B152502DA00568D1B /* WebCoreThread.h in Headers */ = {isa = PBXBuildFile; fileRef = 1FA47C89152502DA00568D1B /* WebCoreThread.h */; };
26147B0A15DDCCDC00DDB907 /* IntegerToStringConversion.h in Headers */ = {isa = PBXBuildFile; fileRef = 26147B0815DDCCDC00DDB907 /* IntegerToStringConversion.h */; };
26299B6E17A9E5B800ADEBE5 /* Ref.h in Headers */ = {isa = PBXBuildFile; fileRef = 26299B6D17A9E5B800ADEBE5 /* Ref.h */; };
+ 2684D4361C000D400081D663 /* IndexSparseSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 2684D4351C000D400081D663 /* IndexSparseSet.h */; };
2C05385415BC819000F21B96 /* GregorianDateTime.h in Headers */ = {isa = PBXBuildFile; fileRef = 2C05385315BC819000F21B96 /* GregorianDateTime.h */; };
2CCD892A15C0390200285083 /* GregorianDateTime.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 2CCD892915C0390200285083 /* GregorianDateTime.cpp */; };
2CDED0EF18115C38004DBA70 /* RunLoopCF.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 2CDED0EE18115C38004DBA70 /* RunLoopCF.cpp */; };
@@ -386,6 +387,7 @@
1FA47C89152502DA00568D1B /* WebCoreThread.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = WebCoreThread.h; sourceTree = "<group>"; };
26147B0815DDCCDC00DDB907 /* IntegerToStringConversion.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = IntegerToStringConversion.h; sourceTree = "<group>"; };
26299B6D17A9E5B800ADEBE5 /* Ref.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Ref.h; sourceTree = "<group>"; };
+ 2684D4351C000D400081D663 /* IndexSparseSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = IndexSparseSet.h; sourceTree = "<group>"; };
2C05385315BC819000F21B96 /* GregorianDateTime.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = GregorianDateTime.h; sourceTree = "<group>"; };
2CCD892915C0390200285083 /* GregorianDateTime.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = GregorianDateTime.cpp; sourceTree = "<group>"; };
2CDED0EE18115C38004DBA70 /* RunLoopCF.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = RunLoopCF.cpp; sourceTree = "<group>"; };
@@ -801,6 +803,7 @@
A8A472B9151A825A004123FF /* HashTable.h */,
A8A472BA151A825A004123FF /* HashTraits.h */,
A8A472BB151A825A004123FF /* HexNumber.h */,
+ 2684D4351C000D400081D663 /* IndexSparseSet.h */,
A8A472BC151A825A004123FF /* InlineASM.h */,
A70DA0821799F04D00529A9B /* Insertion.h */,
7CDD7FF7186D291E007433CD /* IteratorAdaptors.h */,
@@ -1229,6 +1232,7 @@
A748745317A0BDAE00FA04CB /* SixCharacterHash.h in Headers */,
A8A47426151A825B004123FF /* Spectrum.h in Headers */,
A8A47428151A825B004123FF /* StackBounds.h in Headers */,
+ 2684D4361C000D400081D663 /* IndexSparseSet.h in Headers */,
FEDACD3E1630F83F00C69634 /* StackStats.h in Headers */,
A8A47429151A825B004123FF /* StaticConstructors.h in Headers */,
A8A4742A151A825B004123FF /* StdLibExtras.h in Headers */,
Added: trunk/Source/WTF/wtf/IndexSparseSet.h (0 => 192851)
--- trunk/Source/WTF/wtf/IndexSparseSet.h (rev 0)
+++ trunk/Source/WTF/wtf/IndexSparseSet.h 2015-12-01 02:26:57 UTC (rev 192851)
@@ -0,0 +1,143 @@
+/*
+ * Copyright (C) 2015 Apple Inc. All Rights Reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef IndexSparseSet_h
+#define IndexSparseSet_h
+
+#include <wtf/Vector.h>
+
+namespace WTF {
+
+// IndexSparseSet is an efficient set of integers that can only be valued
+// between zero and size() - 1.
+//
+// The implementation is using Briggs Sparse Set representation. We allocate
+// memory from 0 to size() - 1 to do mapping in O(1), but we never initialize
+// that memory. When adding/removing values to the set, they are added in a list
+// and the corresponding bucket is initialized to the position in the list.
+//
+// The assumption here is that we only need a sparse subset of number live at any
+// time.
+
+template<typename OverflowHandler = CrashOnOverflow>
+class IndexSparseSet {
+ typedef Vector<unsigned, 0, OverflowHandler> ValueList;
+public:
+ explicit IndexSparseSet(unsigned maxValue);
+
+ void add(unsigned);
+ void remove(unsigned);
+ void clear();
+
+ unsigned size() const;
+ bool isEmpty() const;
+ bool contains(unsigned) const;
+
+ typedef typename ValueList::const_iterator const_iterator;
+ const_iterator begin() const;
+ const_iterator end() const;
+
+private:
+ Vector<unsigned, 0, OverflowHandler, 1> m_map;
+ ValueList m_values;
+};
+
+template<typename OverflowHandler>
+inline IndexSparseSet<OverflowHandler>::IndexSparseSet(unsigned maxValue)
+{
+ m_map.resize(maxValue + 1);
+}
+
+template<typename OverflowHandler>
+inline void IndexSparseSet<OverflowHandler>::add(unsigned value)
+{
+ if (contains(value))
+ return;
+
+ unsigned newPosition = m_values.size();
+ m_values.append(value);
+ m_map[value] = newPosition;
+}
+
+template<typename OverflowHandler>
+inline void IndexSparseSet<OverflowHandler>::remove(unsigned value)
+{
+ unsigned position = m_map[value];
+ if (position >= m_values.size())
+ return;
+
+ if (m_values[position] == value) {
+ unsigned lastValue = m_values.last();
+ m_values[position] = lastValue;
+ m_map[lastValue] = position;
+ m_values.removeLast();
+ }
+}
+
+template<typename OverflowHandler>
+void IndexSparseSet<OverflowHandler>::clear()
+{
+ m_values.resize(0);
+}
+
+template<typename OverflowHandler>
+unsigned IndexSparseSet<OverflowHandler>::size() const
+{
+ return m_values.size();
+}
+
+template<typename OverflowHandler>
+bool IndexSparseSet<OverflowHandler>::isEmpty() const
+{
+ return !size();
+}
+
+template<typename OverflowHandler>
+bool IndexSparseSet<OverflowHandler>::contains(unsigned value) const
+{
+ unsigned position = m_map[value];
+ if (position >= m_values.size())
+ return false;
+
+ return m_values[position] == value;
+}
+
+template<typename OverflowHandler>
+auto IndexSparseSet<OverflowHandler>::begin() const -> const_iterator
+{
+ return m_values.begin();
+}
+
+template<typename OverflowHandler>
+auto IndexSparseSet<OverflowHandler>::end() const -> const_iterator
+{
+ return m_values.end();
+}
+
+} // namespace WTF
+
+using WTF::IndexSparseSet;
+
+#endif // IndexSparseSet_h
