<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[214917] trunk/Source</title>
</head>
<body>
<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; }
#msg dl a { font-weight: bold}
#msg dl a:link { color:#fc3; }
#msg dl a:active { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/214917">214917</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2017-04-04 17:25:02 -0700 (Tue, 04 Apr 2017)</dd>
</dl>
<h3>Log Message</h3>
<pre>B3::fixSSA() needs a tune-up
https://bugs.webkit.org/show_bug.cgi?id=170485
Reviewed by Saam Barati.
Source/JavaScriptCore:
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.
Source/WTF:
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):</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3FixSSAcpp">trunk/Source/JavaScriptCore/b3/B3FixSSA.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3SSACalculatorcpp">trunk/Source/JavaScriptCore/b3/B3SSACalculator.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3VariableLivenesscpp">trunk/Source/JavaScriptCore/b3/B3VariableLiveness.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirLivenessh">trunk/Source/JavaScriptCore/b3/air/AirLiveness.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGLivenessAnalysisPhasecpp">trunk/Source/JavaScriptCore/dfg/DFGLivenessAnalysisPhase.cpp</a></li>
<li><a href="#trunkSourceWTFChangeLog">trunk/Source/WTF/ChangeLog</a></li>
<li><a href="#trunkSourceWTFwtfHashTraitsh">trunk/Source/WTF/wtf/HashTraits.h</a></li>
<li><a href="#trunkSourceWTFwtfIndexSparseSeth">trunk/Source/WTF/wtf/IndexSparseSet.h</a></li>
<li><a href="#trunkSourceWTFwtfLivenessh">trunk/Source/WTF/wtf/Liveness.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (214916 => 214917)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2017-04-05 00:23:46 UTC (rev 214916)
+++ trunk/Source/JavaScriptCore/ChangeLog 2017-04-05 00:25:02 UTC (rev 214917)
</span><span class="lines">@@ -1,3 +1,47 @@
</span><ins>+2017-04-04 Filip Pizlo <fpizlo@apple.com>
+
+ 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.
+
</ins><span class="cx"> 2017-04-04 Joseph Pecoraro <pecoraro@apple.com>
</span><span class="cx">
</span><span class="cx"> Remove stale LLVM Header Path includes from JavaScriptCore
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3FixSSAcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3FixSSA.cpp (214916 => 214917)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3FixSSA.cpp 2017-04-05 00:23:46 UTC (rev 214916)
+++ trunk/Source/JavaScriptCore/b3/B3FixSSA.cpp 2017-04-05 00:25:02 UTC (rev 214917)
</span><span class="lines">@@ -42,103 +42,83 @@
</span><span class="cx"> #include "B3VariableValue.h"
</span><span class="cx"> #include <wtf/CommaPrinter.h>
</span><span class="cx"> #include <wtf/IndexSet.h>
</span><ins>+#include <wtf/IndexSparseSet.h>
</ins><span class="cx">
</span><span class="cx"> namespace JSC { namespace B3 {
</span><span class="cx">
</span><span class="cx"> namespace {
</span><ins>+
</ins><span class="cx"> const bool verbose = false;
</span><del>-} // anonymous namespace
</del><span class="cx">
</span><del>-void demoteValues(Procedure& proc, const IndexSet<Value*>& values)
</del><ins>+void killDeadVariables(Procedure& proc)
</ins><span class="cx"> {
</span><del>- HashMap<Value*, Variable*> map;
- HashMap<Value*, Variable*> phiMap;
</del><ins>+ IndexSet<Variable*> liveVariables;
+ for (Value* value : proc.values()) {
+ if (value->opcode() == Get)
+ liveVariables.add(value->as<VariableValue>()->variable());
+ }
</ins><span class="cx">
</span><del>- // 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()));
</del><ins>+ for (Value* value : proc.values()) {
+ if (value->opcode() == Set && !liveVariables.contains(value->as<VariableValue>()->variable()))
+ value->replaceWithNop();
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- 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");
</del><ins>+ for (Variable* variable : proc.variables()) {
+ if (!liveVariables.contains(variable))
+ proc.deleteVariable(variable);
</ins><span class="cx"> }
</span><ins>+}
</ins><span class="cx">
</span><del>- // Change accesses to the values to accesses to the stack slots.
- InsertionSet insertionSet(proc);
- for (BasicBlock* block : proc) {
</del><ins>+void fixSSALocally(Procedure& proc)
+{
+ IndexSparseSet<KeyValuePair<unsigned, Value*>> mapping(proc.variables().size());
+ for (BasicBlock* block : proc.blocksInPreOrder()) {
+ mapping.clear();
+
</ins><span class="cx"> for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
</span><span class="cx"> Value* value = block->at(valueIndex);
</span><ins>+ value->performSubstitution();
</ins><span class="cx">
</span><del>- 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);
- }
- }
</del><ins>+ switch (value->opcode()) {
+ case Get: {
+ VariableValue* variableValue = value->as<VariableValue>();
+ Variable* variable = variableValue->variable();
</ins><span class="cx">
</span><del>- 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();
- }
- }
</del><ins>+ if (KeyValuePair<unsigned, Value*>* replacement = mapping.get(variable->index()))
+ value->replaceWithIdentity(replacement->value);
+ break;
</ins><span class="cx"> }
</span><ins>+
+ case Set: {
+ VariableValue* variableValue = value->as<VariableValue>();
+ Variable* variable = variableValue->variable();
</ins><span class="cx">
</span><del>- if (Variable* variable = map.get(value)) {
- insertionSet.insert<VariableValue>(
- valueIndex + 1, Set, value->origin(), variable, value);
</del><ins>+ mapping.set(variable->index(), value->child(0));
+ break;
</ins><span class="cx"> }
</span><ins>+
+ default:
+ break;
+ }
</ins><span class="cx"> }
</span><del>- insertionSet.execute(block);
</del><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><del>-bool fixSSA(Procedure& proc)
</del><ins>+void fixSSAGlobally(Procedure& proc)
</ins><span class="cx"> {
</span><del>- 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());
</del><ins>+ 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);
+ }
</ins><span class="cx"> }
</span><del>-
- 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);
</del><span class="cx">
</span><del>- VariableLiveness liveness(proc);
</del><span class="cx"> VariableLiveness::LiveAtHead liveAtHead = liveness.liveAtHead();
</span><span class="cx">
</span><span class="cx"> SSACalculator ssa(proc);
</span><span class="lines">@@ -168,39 +148,51 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> // Decide where Phis are to be inserted. This creates them but does not insert them.
</span><del>- 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;
- });
</del><ins>+ {
+ 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;
+ });
+ }
</ins><span class="cx">
</span><span class="cx"> // Now perform the conversion.
</span><ins>+ TimingScope timingScope("fixSSA: convert");
</ins><span class="cx"> InsertionSet insertionSet(proc);
</span><del>- IndexMap<Variable*, Value*> mapping(proc.variables().size());
</del><ins>+ IndexSparseSet<KeyValuePair<unsigned, Value*>> mapping(proc.variables().size());
</ins><span class="cx"> for (BasicBlock* block : proc.blocksInPreOrder()) {
</span><span class="cx"> mapping.clear();
</span><del>-
- for (Variable* variable : liveness.liveAtHead(block)) {
</del><ins>+
+ auto ensureMapping = [&] (Variable* variable, unsigned valueIndex, Origin origin) -> Value* {
+ KeyValuePair<unsigned, Value*>* found = mapping.get(variable->index());
+ if (found)
+ return found->value;
+
</ins><span class="cx"> SSACalculator::Variable* calcVar = variableToCalcVar[variable];
</span><span class="cx"> SSACalculator::Def* def = ssa.reachingDefAtHead(block, calcVar);
</span><del>- if (def)
- mapping[variable] = def->value();
- }
</del><ins>+ if (def) {
+ mapping.set(variable->index(), def->value());
+ return def->value();
+ }
+
+ return insertionSet.insertBottom(valueIndex, origin, variable->type());
+ };
</ins><span class="cx">
</span><span class="cx"> for (SSACalculator::Def* phiDef : ssa.phisForBlock(block)) {
</span><span class="cx"> Variable* variable = calcVarToVariable[phiDef->variable()->index()];
</span><span class="cx">
</span><span class="cx"> insertionSet.insertValue(0, phiDef->value());
</span><del>- mapping[variable] = phiDef->value();
</del><ins>+ mapping.set(variable->index(), phiDef->value());
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
</span><span class="lines">@@ -212,12 +204,7 @@
</span><span class="cx"> VariableValue* variableValue = value->as<VariableValue>();
</span><span class="cx"> Variable* variable = variableValue->variable();
</span><span class="cx">
</span><del>- if (Value* replacement = mapping[variable])
- value->replaceWithIdentity(replacement);
- else {
- value->replaceWithIdentity(
- insertionSet.insertBottom(valueIndex, value));
- }
</del><ins>+ value->replaceWithIdentity(ensureMapping(variable, valueIndex, value->origin()));
</ins><span class="cx"> break;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -225,7 +212,7 @@
</span><span class="cx"> VariableValue* variableValue = value->as<VariableValue>();
</span><span class="cx"> Variable* variable = variableValue->variable();
</span><span class="cx">
</span><del>- mapping[variable] = value->child(0);
</del><ins>+ mapping.set(variable->index(), value->child(0));
</ins><span class="cx"> value->replaceWithNop();
</span><span class="cx"> break;
</span><span class="cx"> }
</span><span class="lines">@@ -243,7 +230,7 @@
</span><span class="cx"> SSACalculator::Variable* calcVar = phiDef->variable();
</span><span class="cx"> Variable* variable = calcVarToVariable[calcVar->index()];
</span><span class="cx">
</span><del>- Value* mappedValue = mapping[variable];
</del><ins>+ Value* mappedValue = ensureMapping(variable, upsilonInsertionPoint, upsilonOrigin);
</ins><span class="cx"> if (verbose) {
</span><span class="cx"> dataLog(
</span><span class="cx"> "Mapped value for ", *variable, " with successor Phi ", *phi,
</span><span class="lines">@@ -250,9 +237,6 @@
</span><span class="cx"> " at end of ", *block, ": ", pointerDump(mappedValue), "\n");
</span><span class="cx"> }
</span><span class="cx">
</span><del>- if (!mappedValue)
- mappedValue = insertionSet.insertBottom(upsilonInsertionPoint, phi);
-
</del><span class="cx"> insertionSet.insert<UpsilonValue>(
</span><span class="cx"> upsilonInsertionPoint, upsilonOrigin, mappedValue, phi);
</span><span class="cx"> }
</span><span class="lines">@@ -265,7 +249,96 @@
</span><span class="cx"> dataLog("B3 after SSA conversion:\n");
</span><span class="cx"> dataLog(proc);
</span><span class="cx"> }
</span><ins>+}
</ins><span class="cx">
</span><ins>+} // 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);
+
</ins><span class="cx"> return true;
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3SSACalculatorcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3SSACalculator.cpp (214916 => 214917)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3SSACalculator.cpp 2017-04-05 00:23:46 UTC (rev 214916)
+++ trunk/Source/JavaScriptCore/b3/B3SSACalculator.cpp 2017-04-05 00:25:02 UTC (rev 214917)
</span><span class="lines">@@ -98,11 +98,14 @@
</span><span class="cx"> return reachingDefAtTail(m_dominators->idom(block), variable);
</span><span class="cx"> }
</span><span class="cx">
</span><del>-SSACalculator::Def* SSACalculator::reachingDefAtTail(BasicBlock* block, Variable* variable)
</del><ins>+SSACalculator::Def* SSACalculator::reachingDefAtTail(BasicBlock* startingBlock, Variable* variable)
</ins><span class="cx"> {
</span><del>- for (; block; block = m_dominators->idom(block)) {
- if (Def* def = m_data[block].m_defs.get(variable))
</del><ins>+ 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);
</ins><span class="cx"> return def;
</span><ins>+ }
</ins><span class="cx"> }
</span><span class="cx"> return nullptr;
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3VariableLivenesscpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3VariableLiveness.cpp (214916 => 214917)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3VariableLiveness.cpp 2017-04-05 00:23:46 UTC (rev 214916)
+++ trunk/Source/JavaScriptCore/b3/B3VariableLiveness.cpp 2017-04-05 00:25:02 UTC (rev 214917)
</span><span class="lines">@@ -28,11 +28,14 @@
</span><span class="cx">
</span><span class="cx"> #if ENABLE(B3_JIT)
</span><span class="cx">
</span><ins>+#include "B3TimingScope.h"
+
</ins><span class="cx"> namespace JSC { namespace B3 {
</span><span class="cx">
</span><span class="cx"> VariableLiveness::VariableLiveness(Procedure& proc)
</span><span class="cx"> : WTF::Liveness<VariableLivenessAdapter>(proc.cfg(), proc)
</span><span class="cx"> {
</span><ins>+ TimingScope timingScope("B3::VariableLiveness");
</ins><span class="cx"> compute();
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirLivenessh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirLiveness.h (214916 => 214917)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirLiveness.h 2017-04-05 00:23:46 UTC (rev 214916)
+++ trunk/Source/JavaScriptCore/b3/air/AirLiveness.h 2017-04-05 00:25:02 UTC (rev 214917)
</span><span class="lines">@@ -28,6 +28,7 @@
</span><span class="cx"> #if ENABLE(B3_JIT)
</span><span class="cx">
</span><span class="cx"> #include "AirLivenessAdapter.h"
</span><ins>+#include "B3TimingScope.h"
</ins><span class="cx"> #include <wtf/Liveness.h>
</span><span class="cx">
</span><span class="cx"> namespace JSC { namespace B3 { namespace Air {
</span><span class="lines">@@ -39,6 +40,7 @@
</span><span class="cx"> : WTF::Liveness<Adapter>(code.cfg(), code)
</span><span class="cx"> {
</span><span class="cx"> SuperSamplerScope samplingScope(false);
</span><ins>+ TimingScope timingScope("Air::Liveness");
</ins><span class="cx"> WTF::Liveness<Adapter>::compute();
</span><span class="cx"> }
</span><span class="cx"> };
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGLivenessAnalysisPhasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGLivenessAnalysisPhase.cpp (214916 => 214917)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGLivenessAnalysisPhase.cpp 2017-04-05 00:23:46 UTC (rev 214916)
+++ trunk/Source/JavaScriptCore/dfg/DFGLivenessAnalysisPhase.cpp 2017-04-05 00:25:02 UTC (rev 214917)
</span><span class="lines">@@ -41,6 +41,8 @@
</span><span class="cx">
</span><span class="cx"> namespace JSC { namespace DFG {
</span><span class="cx">
</span><ins>+namespace {
+
</ins><span class="cx"> // Uncomment this to log hashtable operations.
</span><span class="cx"> // static const char templateString[] = "unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>";
</span><span class="cx"> // typedef LoggingHashSet<templateString, unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> LiveSet;
</span><span class="lines">@@ -47,6 +49,8 @@
</span><span class="cx">
</span><span class="cx"> typedef HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> LiveSet;
</span><span class="cx">
</span><ins>+typedef IndexSparseSet<unsigned, DefaultIndexSparseSetTraits<unsigned>, UnsafeVectorOverflow> Workset;
+
</ins><span class="cx"> class LivenessAnalysisPhase : public Phase {
</span><span class="cx"> public:
</span><span class="cx"> LivenessAnalysisPhase(Graph& graph)
</span><span class="lines">@@ -57,7 +61,7 @@
</span><span class="cx"> , m_liveAtTail(m_graph)
</span><span class="cx"> {
</span><span class="cx"> m_graph.m_indexingCache->recompute();
</span><del>- m_workset = std::make_unique<IndexSparseSet<UnsafeVectorOverflow>>(m_graph.m_indexingCache->numIndices());
</del><ins>+ m_workset = std::make_unique<Workset>(m_graph.m_indexingCache->numIndices());
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> bool run()
</span><span class="lines">@@ -185,9 +189,11 @@
</span><span class="cx"> BlockMap<LiveSet> m_liveAtTail;
</span><span class="cx">
</span><span class="cx"> // Single sparse set allocated once and used by every basic block.
</span><del>- std::unique_ptr<IndexSparseSet<UnsafeVectorOverflow>> m_workset;
</del><ins>+ std::unique_ptr<Workset> m_workset;
</ins><span class="cx"> };
</span><span class="cx">
</span><ins>+} // anonymous namespace
+
</ins><span class="cx"> bool performLivenessAnalysis(Graph& graph)
</span><span class="cx"> {
</span><span class="cx"> graph.packNodeIndices();
</span></span></pre></div>
<a id="trunkSourceWTFChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/ChangeLog (214916 => 214917)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -1,5 +1,40 @@
</span><span class="cx"> 2017-04-04 Filip Pizlo <fpizlo@apple.com>
</span><span class="cx">
</span><ins>+ 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 <fpizlo@apple.com>
+
</ins><span class="cx"> Don't need to Air::reportUsedRegisters for wasm at -O1
</span><span class="cx"> https://bugs.webkit.org/show_bug.cgi?id=170459
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWTFwtfHashTraitsh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/HashTraits.h (214916 => 214917)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -371,6 +371,7 @@
</span><span class="cx"> } // namespace WTF
</span><span class="cx">
</span><span class="cx"> using WTF::HashTraits;
</span><ins>+using WTF::KeyValuePair;
</ins><span class="cx"> using WTF::PairHashTraits;
</span><span class="cx"> using WTF::NullableHashTraits;
</span><span class="cx"> using WTF::SimpleClassHashTraits;
</span></span></pre></div>
<a id="trunkSourceWTFwtfIndexSparseSeth"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/IndexSparseSet.h (214916 => 214917)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2015 Apple Inc. All Rights Reserved.
</del><ins>+ * Copyright (C) 2015-2017 Apple Inc. All Rights Reserved.
</ins><span class="cx"> *
</span><span class="cx"> * Redistribution and use in source and binary forms, with or without
</span><span class="cx"> * modification, are permitted provided that the following conditions
</span><span class="lines">@@ -26,6 +26,7 @@
</span><span class="cx"> #ifndef IndexSparseSet_h
</span><span class="cx"> #define IndexSparseSet_h
</span><span class="cx">
</span><ins>+#include <wtf/HashTraits.h>
</ins><span class="cx"> #include <wtf/Vector.h>
</span><span class="cx">
</span><span class="cx"> namespace WTF {
</span><span class="lines">@@ -41,13 +42,47 @@
</span><span class="cx"> // The assumption here is that we only need a sparse subset of number live at any
</span><span class="cx"> // time.
</span><span class="cx">
</span><del>-template<typename OverflowHandler = CrashOnOverflow>
</del><ins>+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>
</ins><span class="cx"> class IndexSparseSet {
</span><del>- typedef Vector<unsigned, 0, OverflowHandler> ValueList;
</del><ins>+ typedef Vector<EntryType, 0, OverflowHandler> ValueList;
</ins><span class="cx"> public:
</span><span class="cx"> explicit IndexSparseSet(unsigned size);
</span><span class="cx">
</span><del>- bool add(unsigned);
</del><ins>+ template<typename... Arguments>
+ bool add(unsigned, Arguments&&...);
+ template<typename... Arguments>
+ bool set(unsigned, Arguments&&...);
</ins><span class="cx"> bool remove(unsigned);
</span><span class="cx"> void clear();
</span><span class="cx">
</span><span class="lines">@@ -54,6 +89,8 @@
</span><span class="cx"> unsigned size() const;
</span><span class="cx"> bool isEmpty() const;
</span><span class="cx"> bool contains(unsigned) const;
</span><ins>+ const EntryType* get(unsigned) const;
+ EntryType* get(unsigned);
</ins><span class="cx">
</span><span class="cx"> typedef typename ValueList::const_iterator const_iterator;
</span><span class="cx"> const_iterator begin() const;
</span><span class="lines">@@ -68,35 +105,51 @@
</span><span class="cx"> ValueList m_values;
</span><span class="cx"> };
</span><span class="cx">
</span><del>-template<typename OverflowHandler>
-inline IndexSparseSet<OverflowHandler>::IndexSparseSet(unsigned size)
</del><ins>+template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
+inline IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::IndexSparseSet(unsigned size)
</ins><span class="cx"> {
</span><span class="cx"> m_map.resize(size);
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename OverflowHandler>
-inline bool IndexSparseSet<OverflowHandler>::add(unsigned value)
</del><ins>+template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
+template<typename... Arguments>
+inline bool IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::add(unsigned value, Arguments&&... arguments)
</ins><span class="cx"> {
</span><span class="cx"> if (contains(value))
</span><span class="cx"> return false;
</span><span class="cx">
</span><span class="cx"> unsigned newPosition = m_values.size();
</span><del>- m_values.append(value);
</del><ins>+ m_values.append(EntryTypeTraits::create(value, std::forward<Arguments>(arguments)...));
</ins><span class="cx"> m_map[value] = newPosition;
</span><span class="cx"> return true;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename OverflowHandler>
-inline bool IndexSparseSet<OverflowHandler>::remove(unsigned value)
</del><ins>+template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
+template<typename... Arguments>
+inline bool IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::set(unsigned value, Arguments&&... arguments)
</ins><span class="cx"> {
</span><ins>+ 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)
+{
</ins><span class="cx"> unsigned position = m_map[value];
</span><span class="cx"> if (position >= m_values.size())
</span><span class="cx"> return false;
</span><span class="cx">
</span><span class="cx"> if (m_values[position] == value) {
</span><del>- unsigned lastValue = m_values.last();
- m_values[position] = lastValue;
- m_map[lastValue] = position;
</del><ins>+ EntryType lastValue = m_values.last();
+ m_values[position] = WTFMove(lastValue);
+ m_map[EntryTypeTraits::key(lastValue)] = position;
</ins><span class="cx"> m_values.removeLast();
</span><span class="cx"> return true;
</span><span class="cx"> }
</span><span class="lines">@@ -104,48 +157,72 @@
</span><span class="cx"> return false;
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename OverflowHandler>
-void IndexSparseSet<OverflowHandler>::clear()
</del><ins>+template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
+void IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::clear()
</ins><span class="cx"> {
</span><span class="cx"> m_values.resize(0);
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename OverflowHandler>
-unsigned IndexSparseSet<OverflowHandler>::size() const
</del><ins>+template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
+unsigned IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::size() const
</ins><span class="cx"> {
</span><span class="cx"> return m_values.size();
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename OverflowHandler>
-bool IndexSparseSet<OverflowHandler>::isEmpty() const
</del><ins>+template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
+bool IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::isEmpty() const
</ins><span class="cx"> {
</span><span class="cx"> return !size();
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename OverflowHandler>
-bool IndexSparseSet<OverflowHandler>::contains(unsigned value) const
</del><ins>+template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
+bool IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::contains(unsigned value) const
</ins><span class="cx"> {
</span><span class="cx"> unsigned position = m_map[value];
</span><span class="cx"> if (position >= m_values.size())
</span><span class="cx"> return false;
</span><span class="cx">
</span><del>- return m_values[position] == value;
</del><ins>+ return EntryTypeTraits::key(m_values[position]) == value;
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename OverflowHandler>
-void IndexSparseSet<OverflowHandler>::sort()
</del><ins>+template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
+auto IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::get(unsigned value) -> EntryType*
</ins><span class="cx"> {
</span><del>- std::sort(m_values.begin(), m_values.end());
</del><ins>+ 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;
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename OverflowHandler>
-auto IndexSparseSet<OverflowHandler>::begin() const -> const_iterator
</del><ins>+template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
+auto IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::get(unsigned value) const -> const EntryType*
</ins><span class="cx"> {
</span><ins>+ 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
+{
</ins><span class="cx"> return m_values.begin();
</span><span class="cx"> }
</span><span class="cx">
</span><del>-template<typename OverflowHandler>
-auto IndexSparseSet<OverflowHandler>::end() const -> const_iterator
</del><ins>+template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
+auto IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::end() const -> const_iterator
</ins><span class="cx"> {
</span><span class="cx"> return m_values.end();
</span><span class="cx"> }
</span><span class="lines">@@ -152,6 +229,7 @@
</span><span class="cx">
</span><span class="cx"> } // namespace WTF
</span><span class="cx">
</span><ins>+using WTF::DefaultIndexSparseSetTraits;
</ins><span class="cx"> using WTF::IndexSparseSet;
</span><span class="cx">
</span><span class="cx"> #endif // IndexSparseSet_h
</span></span></pre></div>
<a id="trunkSourceWTFwtfLivenessh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/Liveness.h (214916 => 214917)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -40,6 +40,7 @@
</span><span class="cx"> typedef typename Adapter::CFG CFG;
</span><span class="cx"> typedef typename Adapter::Thing Thing;
</span><span class="cx"> typedef Vector<unsigned, 4, UnsafeVectorOverflow> IndexVector;
</span><ins>+ typedef IndexSparseSet<unsigned, DefaultIndexSparseSetTraits<unsigned>, UnsafeVectorOverflow> Workset;
</ins><span class="cx">
</span><span class="cx"> template<typename... Arguments>
</span><span class="cx"> Liveness(CFG& cfg, Arguments&&... arguments)
</span><span class="lines">@@ -74,7 +75,7 @@
</span><span class="cx">
</span><span class="cx"> class iterator {
</span><span class="cx"> public:
</span><del>- iterator(Adapter& adapter, IndexSparseSet<UnsafeVectorOverflow>::const_iterator sparceSetIterator)
</del><ins>+ iterator(Adapter& adapter, Workset::const_iterator sparceSetIterator)
</ins><span class="cx"> : m_adapter(adapter)
</span><span class="cx"> , m_sparceSetIterator(sparceSetIterator)
</span><span class="cx"> {
</span><span class="lines">@@ -96,7 +97,7 @@
</span><span class="cx">
</span><span class="cx"> private:
</span><span class="cx"> Adapter& m_adapter;
</span><del>- IndexSparseSet<UnsafeVectorOverflow>::const_iterator m_sparceSetIterator;
</del><ins>+ Workset::const_iterator m_sparceSetIterator;
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> iterator begin() const { return iterator(m_liveness, m_liveness.m_workset.begin()); }
</span><span class="lines">@@ -227,7 +228,7 @@
</span><span class="cx"> return Iterable<IndexVector>(*this, m_liveAtTail[block]);
</span><span class="cx"> }
</span><span class="cx">
</span><del>- IndexSparseSet<UnsafeVectorOverflow>& workset() { return m_workset; }
</del><ins>+ Workset& workset() { return m_workset; }
</ins><span class="cx">
</span><span class="cx"> class LiveAtHead {
</span><span class="cx"> public:
</span><span class="lines">@@ -359,7 +360,7 @@
</span><span class="cx"> friend class LocalCalc::Iterable;
</span><span class="cx">
</span><span class="cx"> CFG& m_cfg;
</span><del>- IndexSparseSet<UnsafeVectorOverflow> m_workset;
</del><ins>+ Workset m_workset;
</ins><span class="cx"> typename CFG::template Map<IndexVector> m_liveAtHead;
</span><span class="cx"> typename CFG::template Map<IndexVector> m_liveAtTail;
</span><span class="cx"> };
</span></span></pre>
</div>
</div>
</body>
</html>