- Revision
- 198935
- Author
- [email protected]
- Date
- 2016-03-31 18:48:34 -0700 (Thu, 31 Mar 2016)
Log Message
[JSC] CFA's valuesAtHead should be a list, not a map
https://bugs.webkit.org/show_bug.cgi?id=156087
Patch by Benjamin Poulain <[email protected]> on 2016-03-31
Reviewed by Mark Lam.
One more step toward moving to the Air-style of liveness analysis:
Make DFG's valuesAtHead a list of Node*-AbstractValue.
This patch alone is already a speedup because our many CFAs
spend an unreasonable amount of time updating at block boundaries.
* dfg/DFGBasicBlock.h:
* dfg/DFGCFAPhase.cpp:
(JSC::DFG::CFAPhase::performBlockCFA):
* dfg/DFGGraph.cpp:
(JSC::DFG::Graph::dump):
* dfg/DFGInPlaceAbstractState.cpp:
(JSC::DFG::InPlaceAbstractState::beginBasicBlock):
(JSC::DFG::setLiveValues):
(JSC::DFG::InPlaceAbstractState::merge):
* dfg/DFGNode.h:
(JSC::DFG::nodeValuePairComparator):
(JSC::DFG::nodeValuePairListDump):
Modified Paths
Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (198934 => 198935)
--- trunk/Source/_javascript_Core/ChangeLog 2016-04-01 01:40:25 UTC (rev 198934)
+++ trunk/Source/_javascript_Core/ChangeLog 2016-04-01 01:48:34 UTC (rev 198935)
@@ -1,3 +1,29 @@
+2016-03-31 Benjamin Poulain <[email protected]>
+
+ [JSC] CFA's valuesAtHead should be a list, not a map
+ https://bugs.webkit.org/show_bug.cgi?id=156087
+
+ Reviewed by Mark Lam.
+
+ One more step toward moving to the Air-style of liveness analysis:
+
+ Make DFG's valuesAtHead a list of Node*-AbstractValue.
+ This patch alone is already a speedup because our many CFAs
+ spend an unreasonable amount of time updating at block boundaries.
+
+ * dfg/DFGBasicBlock.h:
+ * dfg/DFGCFAPhase.cpp:
+ (JSC::DFG::CFAPhase::performBlockCFA):
+ * dfg/DFGGraph.cpp:
+ (JSC::DFG::Graph::dump):
+ * dfg/DFGInPlaceAbstractState.cpp:
+ (JSC::DFG::InPlaceAbstractState::beginBasicBlock):
+ (JSC::DFG::setLiveValues):
+ (JSC::DFG::InPlaceAbstractState::merge):
+ * dfg/DFGNode.h:
+ (JSC::DFG::nodeValuePairComparator):
+ (JSC::DFG::nodeValuePairListDump):
+
2016-03-31 Saam barati <[email protected]>
Revert rewrite const as var workaround
Modified: trunk/Source/_javascript_Core/dfg/DFGBasicBlock.h (198934 => 198935)
--- trunk/Source/_javascript_Core/dfg/DFGBasicBlock.h 2016-04-01 01:40:25 UTC (rev 198934)
+++ trunk/Source/_javascript_Core/dfg/DFGBasicBlock.h 2016-04-01 01:48:34 UTC (rev 198935)
@@ -245,7 +245,11 @@
bool liveAtTailIsDirty { false };
HashSet<Node*> liveAtTail;
HashSet<Node*> liveAtHead;
- HashMap<Node*, AbstractValue> valuesAtHead;
+ struct NodeAbstractValuePair {
+ Node* node;
+ AbstractValue value;
+ };
+ Vector<NodeAbstractValuePair> valuesAtHead;
HashMap<Node*, AbstractValue> valuesAtTail;
SSAData(BasicBlock*);
Modified: trunk/Source/_javascript_Core/dfg/DFGCFAPhase.cpp (198934 => 198935)
--- trunk/Source/_javascript_Core/dfg/DFGCFAPhase.cpp 2016-04-01 01:40:25 UTC (rev 198934)
+++ trunk/Source/_javascript_Core/dfg/DFGCFAPhase.cpp 2016-04-01 01:48:34 UTC (rev 198935)
@@ -148,7 +148,7 @@
if (m_verbose) {
dataLog(" head vars: ", block->valuesAtHead, "\n");
if (m_graph.m_form == SSA)
- dataLog(" head regs: ", mapDump(block->ssa->valuesAtHead), "\n");
+ dataLog(" head regs: ", nodeValuePairListDump(block->ssa->valuesAtHead), "\n");
}
for (unsigned i = 0; i < block->size(); ++i) {
if (m_verbose) {
Modified: trunk/Source/_javascript_Core/dfg/DFGGraph.cpp (198934 => 198935)
--- trunk/Source/_javascript_Core/dfg/DFGGraph.cpp 2016-04-01 01:40:25 UTC (rev 198934)
+++ trunk/Source/_javascript_Core/dfg/DFGGraph.cpp 2016-04-01 01:48:34 UTC (rev 198935)
@@ -512,7 +512,7 @@
RELEASE_ASSERT(block->ssa);
out.print(" Availability: ", block->ssa->availabilityAtHead, "\n");
out.print(" Live: ", nodeListDump(block->ssa->liveAtHead), "\n");
- out.print(" Values: ", nodeMapDump(block->ssa->valuesAtHead, context), "\n");
+ out.print(" Values: ", nodeValuePairListDump(block->ssa->valuesAtHead, context), "\n");
break;
} }
for (size_t i = 0; i < block->size(); ++i) {
Modified: trunk/Source/_javascript_Core/dfg/DFGInPlaceAbstractState.cpp (198934 => 198935)
--- trunk/Source/_javascript_Core/dfg/DFGInPlaceAbstractState.cpp 2016-04-01 01:40:25 UTC (rev 198934)
+++ trunk/Source/_javascript_Core/dfg/DFGInPlaceAbstractState.cpp 2016-04-01 01:48:34 UTC (rev 198935)
@@ -63,7 +63,7 @@
if (m_graph.m_form == SSA) {
for (auto& entry : basicBlock->ssa->valuesAtHead)
- forNode(entry.key) = entry.value;
+ forNode(entry.node) = entry.value;
}
basicBlock->cfaShouldRevisit = false;
basicBlock->cfaHasVisited = true;
@@ -84,6 +84,14 @@
values.add(*iter, AbstractValue());
}
+static void setLiveValues(Vector<BasicBlock::SSAData::NodeAbstractValuePair>& values, HashSet<Node*>& live)
+{
+ values.resize(0);
+ values.reserveCapacity(live.size());
+ for (Node* node : live)
+ values.uncheckedAppend(BasicBlock::SSAData::NodeAbstractValuePair { node, AbstractValue() });
+}
+
void InPlaceAbstractState::initialize()
{
BasicBlock* root = m_graph.block(0);
@@ -300,7 +308,7 @@
changed |= to->valuesAtHead[i].merge(from->valuesAtTail[i]);
for (auto& entry : to->ssa->valuesAtHead) {
- Node* node = entry.key;
+ Node* node = entry.node;
if (verbose)
dataLog(" Merging for ", node, ": from ", from->ssa->valuesAtTail.find(node)->value, " to ", entry.value, "\n");
changed |= entry.value.merge(
Modified: trunk/Source/_javascript_Core/dfg/DFGNode.h (198934 => 198935)
--- trunk/Source/_javascript_Core/dfg/DFGNode.h 2016-04-01 01:40:25 UTC (rev 198934)
+++ trunk/Source/_javascript_Core/dfg/DFGNode.h 2016-04-01 01:48:34 UTC (rev 198935)
@@ -2341,6 +2341,25 @@
return out.toCString();
}
+template<typename IteratorType>
+inline bool nodeValuePairComparator(IteratorType a, IteratorType b)
+{
+ return nodeComparator(a.node, b.node);
+}
+
+template<typename T>
+CString nodeValuePairListDump(const T& nodeValuePairList, DumpContext* context = 0)
+{
+ T sortedList = nodeValuePairList;
+ std::sort(sortedList.begin(), sortedList.end(), nodeValuePairComparator<decltype(*sortedList.begin())>);
+
+ StringPrintStream out;
+ CommaPrinter comma;
+ for (const auto& pair : sortedList)
+ out.print(comma, pair.node, "=>", inContext(pair.value, context));
+ return out.toCString();
+}
+
} } // namespace JSC::DFG
namespace WTF {
