Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (214916 => 214917)
--- trunk/Source/_javascript_Core/ChangeLog 2017-04-05 00:23:46 UTC (rev 214916)
+++ trunk/Source/_javascript_Core/ChangeLog 2017-04-05 00:25:02 UTC (rev 214917)
@@ -1,3 +1,47 @@
+2017-04-04 Filip Pizlo <[email protected]>
+
+ B3::fixSSA() needs a tune-up
+ https://bugs.webkit.org/show_bug.cgi?id=170485
+
+ Reviewed by Saam Barati.
+
+ After the various optimizations to liveness, register allocation, and other phases, the
+ fixSSA() phase now looks like one of the top offenders. This includes a bunch of
+ changes to make this phase run faster. This is a ~7% wasm -O1 compile time progression.
+
+ Here's what I did:
+
+ - We now use IndexSparseSet instead of IndexMap for tracking variable values. This
+ makes it cheaper to chew through small blocks while there is a non-trivial number of
+ total variables.
+
+ - We now do a "local SSA conversion" pass before anything else. This eliminates
+ obvious Get's. If we were using temporary Variables, it would eliminate many of
+ those. That's useful for when we use demoteValues() and duplciateTails(). For wasm
+ -O1, we mainly care about the fact that it makes a bunch of Set's dead.
+
+ - We now do a Set DCE pass after the local SSA but before SSA conversion. This ensures
+ that any block-local live intervals of Variables disappear and don't need further
+ consideration.
+
+ - We now cache the reaching defs calculation.
+
+ - We now perform the reaching defs calculation lazily.
+
+ * b3/B3FixSSA.cpp:
+ (JSC::B3::demoteValues):
+ (JSC::B3::fixSSA):
+ * b3/B3SSACalculator.cpp:
+ (JSC::B3::SSACalculator::reachingDefAtTail):
+ * b3/B3VariableLiveness.cpp:
+ (JSC::B3::VariableLiveness::VariableLiveness):
+ * b3/air/AirLiveness.h:
+ (JSC::B3::Air::Liveness::Liveness):
+ * dfg/DFGLivenessAnalysisPhase.cpp:
+ (JSC::DFG::LivenessAnalysisPhase::LivenessAnalysisPhase): Deleted.
+ (JSC::DFG::LivenessAnalysisPhase::run): Deleted.
+ (JSC::DFG::LivenessAnalysisPhase::processBlock): Deleted.
+
2017-04-04 Joseph Pecoraro <[email protected]>
Remove stale LLVM Header Path includes from _javascript_Core
Modified: trunk/Source/_javascript_Core/b3/B3FixSSA.cpp (214916 => 214917)
--- trunk/Source/_javascript_Core/b3/B3FixSSA.cpp 2017-04-05 00:23:46 UTC (rev 214916)
+++ trunk/Source/_javascript_Core/b3/B3FixSSA.cpp 2017-04-05 00:25:02 UTC (rev 214917)
@@ -42,103 +42,83 @@
#include "B3VariableValue.h"
#include <wtf/CommaPrinter.h>
#include <wtf/IndexSet.h>
+#include <wtf/IndexSparseSet.h>
namespace JSC { namespace B3 {
namespace {
+
const bool verbose = false;
-} // anonymous namespace
-void demoteValues(Procedure& proc, const IndexSet<Value*>& values)
+void killDeadVariables(Procedure& proc)
{
- HashMap<Value*, Variable*> map;
- HashMap<Value*, Variable*> phiMap;
+ IndexSet<Variable*> liveVariables;
+ for (Value* value : proc.values()) {
+ if (value->opcode() == Get)
+ liveVariables.add(value->as<VariableValue>()->variable());
+ }
- // Create stack slots.
- for (Value* value : values.values(proc.values())) {
- map.add(value, proc.addVariable(value->type()));
-
- if (value->opcode() == Phi)
- phiMap.add(value, proc.addVariable(value->type()));
+ for (Value* value : proc.values()) {
+ if (value->opcode() == Set && !liveVariables.contains(value->as<VariableValue>()->variable()))
+ value->replaceWithNop();
}
- if (verbose) {
- dataLog("Demoting values as follows:\n");
- dataLog(" map = ");
- CommaPrinter comma;
- for (auto& entry : map)
- dataLog(comma, *entry.key, "=>", *entry.value);
- dataLog("\n");
- dataLog(" phiMap = ");
- comma = CommaPrinter();
- for (auto& entry : phiMap)
- dataLog(comma, *entry.key, "=>", *entry.value);
- dataLog("\n");
+ for (Variable* variable : proc.variables()) {
+ if (!liveVariables.contains(variable))
+ proc.deleteVariable(variable);
}
+}
- // Change accesses to the values to accesses to the stack slots.
- InsertionSet insertionSet(proc);
- for (BasicBlock* block : proc) {
+void fixSSALocally(Procedure& proc)
+{
+ IndexSparseSet<KeyValuePair<unsigned, Value*>> mapping(proc.variables().size());
+ for (BasicBlock* block : proc.blocksInPreOrder()) {
+ mapping.clear();
+
for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
Value* value = block->at(valueIndex);
+ value->performSubstitution();
- if (value->opcode() == Phi) {
- if (Variable* variable = phiMap.get(value)) {
- value->replaceWithIdentity(
- insertionSet.insert<VariableValue>(
- valueIndex, Get, value->origin(), variable));
- }
- } else {
- for (Value*& child : value->children()) {
- if (Variable* variable = map.get(child)) {
- child = insertionSet.insert<VariableValue>(
- valueIndex, Get, value->origin(), variable);
- }
- }
+ switch (value->opcode()) {
+ case Get: {
+ VariableValue* variableValue = value->as<VariableValue>();
+ Variable* variable = variableValue->variable();
- if (UpsilonValue* upsilon = value->as<UpsilonValue>()) {
- if (Variable* variable = phiMap.get(upsilon->phi())) {
- insertionSet.insert<VariableValue>(
- valueIndex, Set, upsilon->origin(), variable, upsilon->child(0));
- value->replaceWithNop();
- }
- }
+ if (KeyValuePair<unsigned, Value*>* replacement = mapping.get(variable->index()))
+ value->replaceWithIdentity(replacement->value);
+ break;
}
+
+ case Set: {
+ VariableValue* variableValue = value->as<VariableValue>();
+ Variable* variable = variableValue->variable();
- if (Variable* variable = map.get(value)) {
- insertionSet.insert<VariableValue>(
- valueIndex + 1, Set, value->origin(), variable, value);
+ mapping.set(variable->index(), value->child(0));
+ break;
}
+
+ default:
+ break;
+ }
}
- insertionSet.execute(block);
}
}
-bool fixSSA(Procedure& proc)
+void fixSSAGlobally(Procedure& proc)
{
- PhaseScope phaseScope(proc, "fixSSA");
-
- // Just for sanity, remove any unused variables first. It's unlikely that this code has any
- // bugs having to do with dead variables, but it would be silly to have to fix such a bug if
- // it did arise.
- IndexSet<Variable*> liveVariables;
- for (Value* value : proc.values()) {
- if (VariableValue* variableValue = value->as<VariableValue>())
- liveVariables.add(variableValue->variable());
+ VariableLiveness liveness(proc);
+
+ // Kill any dead Set's. Each Set creates work for us, so this is profitable.
+ for (BasicBlock* block : proc) {
+ VariableLiveness::LocalCalc localCalc(liveness, block);
+ for (unsigned valueIndex = block->size(); valueIndex--;) {
+ Value* value = block->at(valueIndex);
+ if (value->opcode() == Set && !localCalc.isLive(value->as<VariableValue>()->variable()))
+ value->replaceWithNop();
+ localCalc.execute(valueIndex);
+ }
}
-
- for (Variable* variable : proc.variables()) {
- if (!liveVariables.contains(variable))
- proc.deleteVariable(variable);
- }
-
- if (proc.variables().isEmpty())
- return false;
-
- // We know that we have variables to optimize, so do that now.
- breakCriticalEdges(proc);
- VariableLiveness liveness(proc);
VariableLiveness::LiveAtHead liveAtHead = liveness.liveAtHead();
SSACalculator ssa(proc);
@@ -168,39 +148,51 @@
}
// Decide where Phis are to be inserted. This creates them but does not insert them.
- ssa.computePhis(
- [&] (SSACalculator::Variable* calcVar, BasicBlock* block) -> Value* {
- Variable* variable = calcVarToVariable[calcVar->index()];
- if (!liveAtHead.isLiveAtHead(block, variable))
- return nullptr;
-
- Value* phi = proc.add<Value>(Phi, variable->type(), block->at(0)->origin());
- if (verbose) {
- dataLog(
- "Adding Phi for ", pointerDump(variable), " at ", *block, ": ",
- deepDump(proc, phi), "\n");
- }
- return phi;
- });
+ {
+ TimingScope timingScope("fixSSA: computePhis");
+ ssa.computePhis(
+ [&] (SSACalculator::Variable* calcVar, BasicBlock* block) -> Value* {
+ Variable* variable = calcVarToVariable[calcVar->index()];
+ if (!liveAtHead.isLiveAtHead(block, variable))
+ return nullptr;
+
+ Value* phi = proc.add<Value>(Phi, variable->type(), block->at(0)->origin());
+ if (verbose) {
+ dataLog(
+ "Adding Phi for ", pointerDump(variable), " at ", *block, ": ",
+ deepDump(proc, phi), "\n");
+ }
+ return phi;
+ });
+ }
// Now perform the conversion.
+ TimingScope timingScope("fixSSA: convert");
InsertionSet insertionSet(proc);
- IndexMap<Variable*, Value*> mapping(proc.variables().size());
+ IndexSparseSet<KeyValuePair<unsigned, Value*>> mapping(proc.variables().size());
for (BasicBlock* block : proc.blocksInPreOrder()) {
mapping.clear();
-
- for (Variable* variable : liveness.liveAtHead(block)) {
+
+ auto ensureMapping = [&] (Variable* variable, unsigned valueIndex, Origin origin) -> Value* {
+ KeyValuePair<unsigned, Value*>* found = mapping.get(variable->index());
+ if (found)
+ return found->value;
+
SSACalculator::Variable* calcVar = variableToCalcVar[variable];
SSACalculator::Def* def = ssa.reachingDefAtHead(block, calcVar);
- if (def)
- mapping[variable] = def->value();
- }
+ if (def) {
+ mapping.set(variable->index(), def->value());
+ return def->value();
+ }
+
+ return insertionSet.insertBottom(valueIndex, origin, variable->type());
+ };
for (SSACalculator::Def* phiDef : ssa.phisForBlock(block)) {
Variable* variable = calcVarToVariable[phiDef->variable()->index()];
insertionSet.insertValue(0, phiDef->value());
- mapping[variable] = phiDef->value();
+ mapping.set(variable->index(), phiDef->value());
}
for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
@@ -212,12 +204,7 @@
VariableValue* variableValue = value->as<VariableValue>();
Variable* variable = variableValue->variable();
- if (Value* replacement = mapping[variable])
- value->replaceWithIdentity(replacement);
- else {
- value->replaceWithIdentity(
- insertionSet.insertBottom(valueIndex, value));
- }
+ value->replaceWithIdentity(ensureMapping(variable, valueIndex, value->origin()));
break;
}
@@ -225,7 +212,7 @@
VariableValue* variableValue = value->as<VariableValue>();
Variable* variable = variableValue->variable();
- mapping[variable] = value->child(0);
+ mapping.set(variable->index(), value->child(0));
value->replaceWithNop();
break;
}
@@ -243,7 +230,7 @@
SSACalculator::Variable* calcVar = phiDef->variable();
Variable* variable = calcVarToVariable[calcVar->index()];
- Value* mappedValue = mapping[variable];
+ Value* mappedValue = ensureMapping(variable, upsilonInsertionPoint, upsilonOrigin);
if (verbose) {
dataLog(
"Mapped value for ", *variable, " with successor Phi ", *phi,
@@ -250,9 +237,6 @@
" at end of ", *block, ": ", pointerDump(mappedValue), "\n");
}
- if (!mappedValue)
- mappedValue = insertionSet.insertBottom(upsilonInsertionPoint, phi);
-
insertionSet.insert<UpsilonValue>(
upsilonInsertionPoint, upsilonOrigin, mappedValue, phi);
}
@@ -265,7 +249,96 @@
dataLog("B3 after SSA conversion:\n");
dataLog(proc);
}
+}
+} // anonymous namespace
+
+void demoteValues(Procedure& proc, const IndexSet<Value*>& values)
+{
+ HashMap<Value*, Variable*> map;
+ HashMap<Value*, Variable*> phiMap;
+
+ // Create stack slots.
+ for (Value* value : values.values(proc.values())) {
+ map.add(value, proc.addVariable(value->type()));
+
+ if (value->opcode() == Phi)
+ phiMap.add(value, proc.addVariable(value->type()));
+ }
+
+ if (verbose) {
+ dataLog("Demoting values as follows:\n");
+ dataLog(" map = ");
+ CommaPrinter comma;
+ for (auto& entry : map)
+ dataLog(comma, *entry.key, "=>", *entry.value);
+ dataLog("\n");
+ dataLog(" phiMap = ");
+ comma = CommaPrinter();
+ for (auto& entry : phiMap)
+ dataLog(comma, *entry.key, "=>", *entry.value);
+ dataLog("\n");
+ }
+
+ // Change accesses to the values to accesses to the stack slots.
+ InsertionSet insertionSet(proc);
+ for (BasicBlock* block : proc) {
+ for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
+ Value* value = block->at(valueIndex);
+
+ if (value->opcode() == Phi) {
+ if (Variable* variable = phiMap.get(value)) {
+ value->replaceWithIdentity(
+ insertionSet.insert<VariableValue>(
+ valueIndex, Get, value->origin(), variable));
+ }
+ } else {
+ for (Value*& child : value->children()) {
+ if (Variable* variable = map.get(child)) {
+ child = insertionSet.insert<VariableValue>(
+ valueIndex, Get, value->origin(), variable);
+ }
+ }
+
+ if (UpsilonValue* upsilon = value->as<UpsilonValue>()) {
+ if (Variable* variable = phiMap.get(upsilon->phi())) {
+ insertionSet.insert<VariableValue>(
+ valueIndex, Set, upsilon->origin(), variable, upsilon->child(0));
+ value->replaceWithNop();
+ }
+ }
+ }
+
+ if (Variable* variable = map.get(value)) {
+ insertionSet.insert<VariableValue>(
+ valueIndex + 1, Set, value->origin(), variable, value);
+ }
+ }
+ insertionSet.execute(block);
+ }
+}
+
+bool fixSSA(Procedure& proc)
+{
+ PhaseScope phaseScope(proc, "fixSSA");
+
+ // Lots of variables have trivial local liveness. We can allocate those without any
+ // trouble.
+ fixSSALocally(proc);
+
+ // Just for sanity, remove any unused variables first. It's unlikely that this code has any
+ // bugs having to do with dead variables, but it would be silly to have to fix such a bug if
+ // it did arise.
+ killDeadVariables(proc);
+
+ if (proc.variables().isEmpty())
+ return false;
+
+ // We know that we have variables to optimize, so do that now.
+ breakCriticalEdges(proc);
+
+ fixSSAGlobally(proc);
+
return true;
}
Modified: trunk/Source/_javascript_Core/b3/B3SSACalculator.cpp (214916 => 214917)
--- trunk/Source/_javascript_Core/b3/B3SSACalculator.cpp 2017-04-05 00:23:46 UTC (rev 214916)
+++ trunk/Source/_javascript_Core/b3/B3SSACalculator.cpp 2017-04-05 00:25:02 UTC (rev 214917)
@@ -98,11 +98,14 @@
return reachingDefAtTail(m_dominators->idom(block), variable);
}
-SSACalculator::Def* SSACalculator::reachingDefAtTail(BasicBlock* block, Variable* variable)
+SSACalculator::Def* SSACalculator::reachingDefAtTail(BasicBlock* startingBlock, Variable* variable)
{
- for (; block; block = m_dominators->idom(block)) {
- if (Def* def = m_data[block].m_defs.get(variable))
+ for (BasicBlock* block = startingBlock; block; block = m_dominators->idom(block)) {
+ if (Def* def = m_data[block].m_defs.get(variable)) {
+ for (BasicBlock* otherBlock = startingBlock; otherBlock != block; otherBlock = m_dominators->idom(otherBlock))
+ m_data[block].m_defs.add(variable, def);
return def;
+ }
}
return nullptr;
}
Modified: trunk/Source/_javascript_Core/b3/B3VariableLiveness.cpp (214916 => 214917)
--- trunk/Source/_javascript_Core/b3/B3VariableLiveness.cpp 2017-04-05 00:23:46 UTC (rev 214916)
+++ trunk/Source/_javascript_Core/b3/B3VariableLiveness.cpp 2017-04-05 00:25:02 UTC (rev 214917)
@@ -28,11 +28,14 @@
#if ENABLE(B3_JIT)
+#include "B3TimingScope.h"
+
namespace JSC { namespace B3 {
VariableLiveness::VariableLiveness(Procedure& proc)
: WTF::Liveness<VariableLivenessAdapter>(proc.cfg(), proc)
{
+ TimingScope timingScope("B3::VariableLiveness");
compute();
}
Modified: trunk/Source/_javascript_Core/b3/air/AirLiveness.h (214916 => 214917)
--- trunk/Source/_javascript_Core/b3/air/AirLiveness.h 2017-04-05 00:23:46 UTC (rev 214916)
+++ trunk/Source/_javascript_Core/b3/air/AirLiveness.h 2017-04-05 00:25:02 UTC (rev 214917)
@@ -28,6 +28,7 @@
#if ENABLE(B3_JIT)
#include "AirLivenessAdapter.h"
+#include "B3TimingScope.h"
#include <wtf/Liveness.h>
namespace JSC { namespace B3 { namespace Air {
@@ -39,6 +40,7 @@
: WTF::Liveness<Adapter>(code.cfg(), code)
{
SuperSamplerScope samplingScope(false);
+ TimingScope timingScope("Air::Liveness");
WTF::Liveness<Adapter>::compute();
}
};
Modified: trunk/Source/_javascript_Core/dfg/DFGLivenessAnalysisPhase.cpp (214916 => 214917)
--- trunk/Source/_javascript_Core/dfg/DFGLivenessAnalysisPhase.cpp 2017-04-05 00:23:46 UTC (rev 214916)
+++ trunk/Source/_javascript_Core/dfg/DFGLivenessAnalysisPhase.cpp 2017-04-05 00:25:02 UTC (rev 214917)
@@ -41,6 +41,8 @@
namespace JSC { namespace DFG {
+namespace {
+
// Uncomment this to log hashtable operations.
// static const char templateString[] = "unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>";
// typedef LoggingHashSet<templateString, unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> LiveSet;
@@ -47,6 +49,8 @@
typedef HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> LiveSet;
+typedef IndexSparseSet<unsigned, DefaultIndexSparseSetTraits<unsigned>, UnsafeVectorOverflow> Workset;
+
class LivenessAnalysisPhase : public Phase {
public:
LivenessAnalysisPhase(Graph& graph)
@@ -57,7 +61,7 @@
, m_liveAtTail(m_graph)
{
m_graph.m_indexingCache->recompute();
- m_workset = std::make_unique<IndexSparseSet<UnsafeVectorOverflow>>(m_graph.m_indexingCache->numIndices());
+ m_workset = std::make_unique<Workset>(m_graph.m_indexingCache->numIndices());
}
bool run()
@@ -185,9 +189,11 @@
BlockMap<LiveSet> m_liveAtTail;
// Single sparse set allocated once and used by every basic block.
- std::unique_ptr<IndexSparseSet<UnsafeVectorOverflow>> m_workset;
+ std::unique_ptr<Workset> m_workset;
};
+} // anonymous namespace
+
bool performLivenessAnalysis(Graph& graph)
{
graph.packNodeIndices();
Modified: trunk/Source/WTF/ChangeLog (214916 => 214917)
--- trunk/Source/WTF/ChangeLog 2017-04-05 00:23:46 UTC (rev 214916)
+++ trunk/Source/WTF/ChangeLog 2017-04-05 00:25:02 UTC (rev 214917)
@@ -1,5 +1,40 @@
2017-04-04 Filip Pizlo <[email protected]>
+ B3::fixSSA() needs a tune-up
+ https://bugs.webkit.org/show_bug.cgi?id=170485
+
+ Reviewed by Saam Barati.
+
+ This makes IndexSparseSet capable of being used as a map if you instantiate it with
+ KeyValuePair<unsigned, ValueType>.
+
+ * wtf/HashTraits.h:
+ * wtf/IndexSparseSet.h:
+ (WTF::DefaultIndexSparseSetTraits::create):
+ (WTF::DefaultIndexSparseSetTraits::key):
+ (WTF::OverflowHandler>::IndexSparseSet):
+ (WTF::OverflowHandler>::add):
+ (WTF::OverflowHandler>::set):
+ (WTF::OverflowHandler>::remove):
+ (WTF::OverflowHandler>::clear):
+ (WTF::OverflowHandler>::size):
+ (WTF::OverflowHandler>::isEmpty):
+ (WTF::OverflowHandler>::contains):
+ (WTF::OverflowHandler>::sort):
+ (WTF::IndexSparseSet<OverflowHandler>::IndexSparseSet): Deleted.
+ (WTF::IndexSparseSet<OverflowHandler>::add): Deleted.
+ (WTF::IndexSparseSet<OverflowHandler>::remove): Deleted.
+ (WTF::IndexSparseSet<OverflowHandler>::clear): Deleted.
+ (WTF::IndexSparseSet<OverflowHandler>::size): Deleted.
+ (WTF::IndexSparseSet<OverflowHandler>::isEmpty): Deleted.
+ (WTF::IndexSparseSet<OverflowHandler>::contains): Deleted.
+ (WTF::IndexSparseSet<OverflowHandler>::sort): Deleted.
+ * wtf/Liveness.h:
+ (WTF::Liveness::LocalCalc::Iterable::iterator::iterator):
+ (WTF::Liveness::workset):
+
+2017-04-04 Filip Pizlo <[email protected]>
+
Don't need to Air::reportUsedRegisters for wasm at -O1
https://bugs.webkit.org/show_bug.cgi?id=170459
Modified: trunk/Source/WTF/wtf/HashTraits.h (214916 => 214917)
--- trunk/Source/WTF/wtf/HashTraits.h 2017-04-05 00:23:46 UTC (rev 214916)
+++ trunk/Source/WTF/wtf/HashTraits.h 2017-04-05 00:25:02 UTC (rev 214917)
@@ -371,6 +371,7 @@
} // namespace WTF
using WTF::HashTraits;
+using WTF::KeyValuePair;
using WTF::PairHashTraits;
using WTF::NullableHashTraits;
using WTF::SimpleClassHashTraits;
Modified: trunk/Source/WTF/wtf/IndexSparseSet.h (214916 => 214917)
--- trunk/Source/WTF/wtf/IndexSparseSet.h 2017-04-05 00:23:46 UTC (rev 214916)
+++ trunk/Source/WTF/wtf/IndexSparseSet.h 2017-04-05 00:25:02 UTC (rev 214917)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2015 Apple Inc. All Rights Reserved.
+ * Copyright (C) 2015-2017 Apple Inc. All Rights Reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -26,6 +26,7 @@
#ifndef IndexSparseSet_h
#define IndexSparseSet_h
+#include <wtf/HashTraits.h>
#include <wtf/Vector.h>
namespace WTF {
@@ -41,13 +42,47 @@
// The assumption here is that we only need a sparse subset of number live at any
// time.
-template<typename OverflowHandler = CrashOnOverflow>
+template<typename T>
+struct DefaultIndexSparseSetTraits {
+ typedef T EntryType;
+
+ static T create(unsigned entry)
+ {
+ return entry;
+ }
+
+ static unsigned key(const T& entry)
+ {
+ return entry;
+ }
+};
+
+template<typename KeyType, typename ValueType>
+struct DefaultIndexSparseSetTraits<KeyValuePair<KeyType, ValueType>> {
+ typedef KeyValuePair<KeyType, ValueType> EntryType;
+
+ template<typename PassedValueType>
+ static EntryType create(unsigned key, PassedValueType&& value)
+ {
+ return EntryType(key, std::forward<PassedValueType>(value));
+ }
+
+ static unsigned key(const EntryType& entry)
+ {
+ return entry.key;
+ }
+};
+
+template<typename EntryType = unsigned, typename EntryTypeTraits = DefaultIndexSparseSetTraits<EntryType>, typename OverflowHandler = CrashOnOverflow>
class IndexSparseSet {
- typedef Vector<unsigned, 0, OverflowHandler> ValueList;
+ typedef Vector<EntryType, 0, OverflowHandler> ValueList;
public:
explicit IndexSparseSet(unsigned size);
- bool add(unsigned);
+ template<typename... Arguments>
+ bool add(unsigned, Arguments&&...);
+ template<typename... Arguments>
+ bool set(unsigned, Arguments&&...);
bool remove(unsigned);
void clear();
@@ -54,6 +89,8 @@
unsigned size() const;
bool isEmpty() const;
bool contains(unsigned) const;
+ const EntryType* get(unsigned) const;
+ EntryType* get(unsigned);
typedef typename ValueList::const_iterator const_iterator;
const_iterator begin() const;
@@ -68,35 +105,51 @@
ValueList m_values;
};
-template<typename OverflowHandler>
-inline IndexSparseSet<OverflowHandler>::IndexSparseSet(unsigned size)
+template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
+inline IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::IndexSparseSet(unsigned size)
{
m_map.resize(size);
}
-template<typename OverflowHandler>
-inline bool IndexSparseSet<OverflowHandler>::add(unsigned value)
+template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
+template<typename... Arguments>
+inline bool IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::add(unsigned value, Arguments&&... arguments)
{
if (contains(value))
return false;
unsigned newPosition = m_values.size();
- m_values.append(value);
+ m_values.append(EntryTypeTraits::create(value, std::forward<Arguments>(arguments)...));
m_map[value] = newPosition;
return true;
}
-template<typename OverflowHandler>
-inline bool IndexSparseSet<OverflowHandler>::remove(unsigned value)
+template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
+template<typename... Arguments>
+inline bool IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::set(unsigned value, Arguments&&... arguments)
{
+ if (EntryType* entry = get(value)) {
+ *entry = EntryTypeTraits::create(value, std::forward<Arguments>(arguments)...);
+ return false;
+ }
+
+ unsigned newPosition = m_values.size();
+ m_values.append(EntryTypeTraits::create(value, std::forward<Arguments>(arguments)...));
+ m_map[value] = newPosition;
+ return true;
+}
+
+template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
+inline bool IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::remove(unsigned value)
+{
unsigned position = m_map[value];
if (position >= m_values.size())
return false;
if (m_values[position] == value) {
- unsigned lastValue = m_values.last();
- m_values[position] = lastValue;
- m_map[lastValue] = position;
+ EntryType lastValue = m_values.last();
+ m_values[position] = WTFMove(lastValue);
+ m_map[EntryTypeTraits::key(lastValue)] = position;
m_values.removeLast();
return true;
}
@@ -104,48 +157,72 @@
return false;
}
-template<typename OverflowHandler>
-void IndexSparseSet<OverflowHandler>::clear()
+template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
+void IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::clear()
{
m_values.resize(0);
}
-template<typename OverflowHandler>
-unsigned IndexSparseSet<OverflowHandler>::size() const
+template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
+unsigned IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::size() const
{
return m_values.size();
}
-template<typename OverflowHandler>
-bool IndexSparseSet<OverflowHandler>::isEmpty() const
+template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
+bool IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::isEmpty() const
{
return !size();
}
-template<typename OverflowHandler>
-bool IndexSparseSet<OverflowHandler>::contains(unsigned value) const
+template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
+bool IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::contains(unsigned value) const
{
unsigned position = m_map[value];
if (position >= m_values.size())
return false;
- return m_values[position] == value;
+ return EntryTypeTraits::key(m_values[position]) == value;
}
-template<typename OverflowHandler>
-void IndexSparseSet<OverflowHandler>::sort()
+template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
+auto IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::get(unsigned value) -> EntryType*
{
- std::sort(m_values.begin(), m_values.end());
+ unsigned position = m_map[value];
+ if (position >= m_values.size())
+ return nullptr;
+
+ EntryType& entry = m_values[position];
+ if (EntryTypeTraits::key(entry) != value)
+ return nullptr;
+
+ return &entry;
}
-template<typename OverflowHandler>
-auto IndexSparseSet<OverflowHandler>::begin() const -> const_iterator
+template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
+auto IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::get(unsigned value) const -> const EntryType*
{
+ return const_cast<IndexSparseSet*>(this)->get(value);
+}
+
+template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
+void IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::sort()
+{
+ std::sort(
+ m_values.begin(), m_values.end(),
+ [&] (const EntryType& a, const EntryType& b) {
+ return EntryTypeTraits::key(a) < EntryTypeTraits::key(b);
+ });
+}
+
+template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
+auto IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::begin() const -> const_iterator
+{
return m_values.begin();
}
-template<typename OverflowHandler>
-auto IndexSparseSet<OverflowHandler>::end() const -> const_iterator
+template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
+auto IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::end() const -> const_iterator
{
return m_values.end();
}
@@ -152,6 +229,7 @@
} // namespace WTF
+using WTF::DefaultIndexSparseSetTraits;
using WTF::IndexSparseSet;
#endif // IndexSparseSet_h
Modified: trunk/Source/WTF/wtf/Liveness.h (214916 => 214917)
--- trunk/Source/WTF/wtf/Liveness.h 2017-04-05 00:23:46 UTC (rev 214916)
+++ trunk/Source/WTF/wtf/Liveness.h 2017-04-05 00:25:02 UTC (rev 214917)
@@ -40,6 +40,7 @@
typedef typename Adapter::CFG CFG;
typedef typename Adapter::Thing Thing;
typedef Vector<unsigned, 4, UnsafeVectorOverflow> IndexVector;
+ typedef IndexSparseSet<unsigned, DefaultIndexSparseSetTraits<unsigned>, UnsafeVectorOverflow> Workset;
template<typename... Arguments>
Liveness(CFG& cfg, Arguments&&... arguments)
@@ -74,7 +75,7 @@
class iterator {
public:
- iterator(Adapter& adapter, IndexSparseSet<UnsafeVectorOverflow>::const_iterator sparceSetIterator)
+ iterator(Adapter& adapter, Workset::const_iterator sparceSetIterator)
: m_adapter(adapter)
, m_sparceSetIterator(sparceSetIterator)
{
@@ -96,7 +97,7 @@
private:
Adapter& m_adapter;
- IndexSparseSet<UnsafeVectorOverflow>::const_iterator m_sparceSetIterator;
+ Workset::const_iterator m_sparceSetIterator;
};
iterator begin() const { return iterator(m_liveness, m_liveness.m_workset.begin()); }
@@ -227,7 +228,7 @@
return Iterable<IndexVector>(*this, m_liveAtTail[block]);
}
- IndexSparseSet<UnsafeVectorOverflow>& workset() { return m_workset; }
+ Workset& workset() { return m_workset; }
class LiveAtHead {
public:
@@ -359,7 +360,7 @@
friend class LocalCalc::Iterable;
CFG& m_cfg;
- IndexSparseSet<UnsafeVectorOverflow> m_workset;
+ Workset m_workset;
typename CFG::template Map<IndexVector> m_liveAtHead;
typename CFG::template Map<IndexVector> m_liveAtTail;
};
