- Revision
- 203921
- Author
- benja...@webkit.org
- Date
- 2016-07-29 13:58:35 -0700 (Fri, 29 Jul 2016)
Log Message
[JSC] Use the same data structures for DFG and Air Liveness Analysis
https://bugs.webkit.org/show_bug.cgi?id=160346
Reviewed by Geoffrey Garen.
In Air, we minimized memory accesses during liveness analysis
with a couple of tricks:
-Use a single Sparse Set ADT for the live value of each block.
-Manipulate compact positive indices instead of hashing values.
This patch brings the same ideas to DFG.
This patch still uses the same fixpoint algorithms.
The reason is Edge's KillStatus used by other phases. We cannot
use a block-boundary liveness algorithm and update KillStatus
simultaneously. It's something I'll probably revisit at some point.
* dfg/DFGAbstractInterpreterInlines.h:
(JSC::DFG::AbstractInterpreter<AbstractStateType>::forAllValues):
(JSC::DFG::AbstractInterpreter<AbstractStateType>::dump):
* dfg/DFGBasicBlock.h:
* dfg/DFGGraph.h:
(JSC::DFG::Graph::maxNodeCount):
(JSC::DFG::Graph::nodeAt):
* dfg/DFGInPlaceAbstractState.cpp:
(JSC::DFG::setLiveValues):
(JSC::DFG::InPlaceAbstractState::endBasicBlock):
* dfg/DFGLivenessAnalysisPhase.cpp:
(JSC::DFG::LivenessAnalysisPhase::LivenessAnalysisPhase):
(JSC::DFG::LivenessAnalysisPhase::run):
(JSC::DFG::LivenessAnalysisPhase::processBlock):
(JSC::DFG::LivenessAnalysisPhase::addChildUse):
(JSC::DFG::LivenessAnalysisPhase::process): Deleted.
Modified Paths
Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (203920 => 203921)
--- trunk/Source/_javascript_Core/ChangeLog 2016-07-29 20:43:42 UTC (rev 203920)
+++ trunk/Source/_javascript_Core/ChangeLog 2016-07-29 20:58:35 UTC (rev 203921)
@@ -1,3 +1,39 @@
+2016-07-29 Benjamin Poulain <benja...@webkit.org>
+
+ [JSC] Use the same data structures for DFG and Air Liveness Analysis
+ https://bugs.webkit.org/show_bug.cgi?id=160346
+
+ Reviewed by Geoffrey Garen.
+
+ In Air, we minimized memory accesses during liveness analysis
+ with a couple of tricks:
+ -Use a single Sparse Set ADT for the live value of each block.
+ -Manipulate compact positive indices instead of hashing values.
+
+ This patch brings the same ideas to DFG.
+
+ This patch still uses the same fixpoint algorithms.
+ The reason is Edge's KillStatus used by other phases. We cannot
+ use a block-boundary liveness algorithm and update KillStatus
+ simultaneously. It's something I'll probably revisit at some point.
+
+ * dfg/DFGAbstractInterpreterInlines.h:
+ (JSC::DFG::AbstractInterpreter<AbstractStateType>::forAllValues):
+ (JSC::DFG::AbstractInterpreter<AbstractStateType>::dump):
+ * dfg/DFGBasicBlock.h:
+ * dfg/DFGGraph.h:
+ (JSC::DFG::Graph::maxNodeCount):
+ (JSC::DFG::Graph::nodeAt):
+ * dfg/DFGInPlaceAbstractState.cpp:
+ (JSC::DFG::setLiveValues):
+ (JSC::DFG::InPlaceAbstractState::endBasicBlock):
+ * dfg/DFGLivenessAnalysisPhase.cpp:
+ (JSC::DFG::LivenessAnalysisPhase::LivenessAnalysisPhase):
+ (JSC::DFG::LivenessAnalysisPhase::run):
+ (JSC::DFG::LivenessAnalysisPhase::processBlock):
+ (JSC::DFG::LivenessAnalysisPhase::addChildUse):
+ (JSC::DFG::LivenessAnalysisPhase::process): Deleted.
+
2016-07-29 Yusuke Suzuki <utatane....@gmail.com>
Unreviewed, ByValInfo is only used in JIT enabled environments
Modified: trunk/Source/_javascript_Core/dfg/DFGAbstractInterpreterInlines.h (203920 => 203921)
--- trunk/Source/_javascript_Core/dfg/DFGAbstractInterpreterInlines.h 2016-07-29 20:43:42 UTC (rev 203920)
+++ trunk/Source/_javascript_Core/dfg/DFGAbstractInterpreterInlines.h 2016-07-29 20:58:35 UTC (rev 203921)
@@ -2963,10 +2963,8 @@
for (size_t i = clobberLimit; i--;)
functor(forNode(m_state.block()->at(i)));
if (m_graph.m_form == SSA) {
- HashSet<Node*>::iterator iter = m_state.block()->ssa->liveAtHead.begin();
- HashSet<Node*>::iterator end = m_state.block()->ssa->liveAtHead.end();
- for (; iter != end; ++iter)
- functor(forNode(*iter));
+ for (Node* node : m_state.block()->ssa->liveAtHead)
+ functor(forNode(node));
}
for (size_t i = m_state.variables().numberOfArguments(); i--;)
functor(m_state.variables().argument(i));
@@ -3024,10 +3022,7 @@
CommaPrinter comma(" ");
HashSet<Node*> seen;
if (m_graph.m_form == SSA) {
- HashSet<Node*>::iterator iter = m_state.block()->ssa->liveAtHead.begin();
- HashSet<Node*>::iterator end = m_state.block()->ssa->liveAtHead.end();
- for (; iter != end; ++iter) {
- Node* node = *iter;
+ for (Node* node : m_state.block()->ssa->liveAtHead) {
seen.add(node);
AbstractValue& value = forNode(node);
if (value.isClear())
@@ -3044,10 +3039,7 @@
out.print(comma, node, ":", value);
}
if (m_graph.m_form == SSA) {
- HashSet<Node*>::iterator iter = m_state.block()->ssa->liveAtTail.begin();
- HashSet<Node*>::iterator end = m_state.block()->ssa->liveAtTail.end();
- for (; iter != end; ++iter) {
- Node* node = *iter;
+ for (Node* node : m_state.block()->ssa->liveAtTail) {
if (seen.contains(node))
continue;
AbstractValue& value = forNode(node);
Modified: trunk/Source/_javascript_Core/dfg/DFGBasicBlock.h (203920 => 203921)
--- trunk/Source/_javascript_Core/dfg/DFGBasicBlock.h 2016-07-29 20:43:42 UTC (rev 203920)
+++ trunk/Source/_javascript_Core/dfg/DFGBasicBlock.h 2016-07-29 20:58:35 UTC (rev 203921)
@@ -249,10 +249,9 @@
AvailabilityMap availabilityAtHead;
AvailabilityMap availabilityAtTail;
-
- bool liveAtTailIsDirty { false };
- HashSet<Node*> liveAtTail;
- HashSet<Node*> liveAtHead;
+
+ Vector<Node*> liveAtHead;
+ Vector<Node*> liveAtTail;
struct NodeAbstractValuePair {
Node* node;
AbstractValue value;
Modified: trunk/Source/_javascript_Core/dfg/DFGGraph.h (203920 => 203921)
--- trunk/Source/_javascript_Core/dfg/DFGGraph.h 2016-07-29 20:43:42 UTC (rev 203920)
+++ trunk/Source/_javascript_Core/dfg/DFGGraph.h 2016-07-29 20:58:35 UTC (rev 203921)
@@ -195,6 +195,8 @@
return node;
}
void deleteNode(Node*);
+ unsigned maxNodeCount() const { return m_nodes.size(); }
+ Node* nodeAt(unsigned index) const { return m_nodes[index]; }
void dethread();
Modified: trunk/Source/_javascript_Core/dfg/DFGInPlaceAbstractState.cpp (203920 => 203921)
--- trunk/Source/_javascript_Core/dfg/DFGInPlaceAbstractState.cpp 2016-07-29 20:43:42 UTC (rev 203920)
+++ trunk/Source/_javascript_Core/dfg/DFGInPlaceAbstractState.cpp 2016-07-29 20:58:35 UTC (rev 203921)
@@ -74,17 +74,14 @@
m_structureClobberState = basicBlock->cfaStructureClobberStateAtHead;
}
-static void setLiveValues(HashMap<Node*, AbstractValue>& values, HashSet<Node*>& live)
+static void setLiveValues(HashMap<Node*, AbstractValue>& values, const Vector<Node*>& liveNodes)
{
values.clear();
-
- HashSet<Node*>::iterator iter = live.begin();
- HashSet<Node*>::iterator end = live.end();
- for (; iter != end; ++iter)
- values.add(*iter, AbstractValue());
+ for (Node* node : liveNodes)
+ values.add(node, AbstractValue());
}
-static void setLiveValues(Vector<BasicBlock::SSAData::NodeAbstractValuePair>& values, HashSet<Node*>& live)
+static void setLiveValues(Vector<BasicBlock::SSAData::NodeAbstractValuePair>& values, const Vector<Node*>& live)
{
values.resize(0);
values.reserveCapacity(live.size());
@@ -203,10 +200,7 @@
for (size_t i = 0; i < block->valuesAtTail.size(); ++i)
changed |= block->valuesAtTail[i].merge(m_variables[i]);
- HashSet<Node*>::iterator iter = block->ssa->liveAtTail.begin();
- HashSet<Node*>::iterator end = block->ssa->liveAtTail.end();
- for (; iter != end; ++iter) {
- Node* node = *iter;
+ for (Node* node : block->ssa->liveAtTail) {
changed |= block->ssa->valuesAtTail.find(node)->value.merge(forNode(node));
}
break;
Modified: trunk/Source/_javascript_Core/dfg/DFGLivenessAnalysisPhase.cpp (203920 => 203921)
--- trunk/Source/_javascript_Core/dfg/DFGLivenessAnalysisPhase.cpp 2016-07-29 20:43:42 UTC (rev 203920)
+++ trunk/Source/_javascript_Core/dfg/DFGLivenessAnalysisPhase.cpp 2016-07-29 20:58:35 UTC (rev 203921)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2013, 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2013, 2015-2016 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -29,10 +29,13 @@
#if ENABLE(DFG_JIT)
#include "DFGBasicBlockInlines.h"
+#include "DFGBlockMapInlines.h"
#include "DFGGraph.h"
#include "DFGInsertionSet.h"
#include "DFGPhase.h"
#include "JSCInlines.h"
+#include <wtf/BitVector.h>
+#include <wtf/IndexSparseSet.h>
namespace JSC { namespace DFG {
@@ -40,60 +43,76 @@
public:
LivenessAnalysisPhase(Graph& graph)
: Phase(graph, "liveness analysis")
+ , m_dirtyBlocks(m_graph.numBlocks())
+ , m_liveAtHead(m_graph)
+ , m_liveAtTail(m_graph)
+ , m_workset(graph.maxNodeCount() - 1)
{
}
-
+
bool run()
{
- ASSERT(m_graph.m_form == SSA);
-
- // Liveness is a backwards analysis; the roots are the blocks that
- // end in a terminal (Return/Throw/ThrowReferenceError). For now, we
- // use a fixpoint formulation since liveness is a rapid analysis with
- // convergence guaranteed after O(connectivity).
-
- // Start by assuming that everything is dead.
- for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+ // Start with all valid block dirty.
+ BlockIndex numBlock = m_graph.numBlocks();
+ m_dirtyBlocks.ensureSize(numBlock);
+ for (BlockIndex blockIndex = 0; blockIndex < numBlock; ++blockIndex) {
+ if (m_graph.block(blockIndex))
+ m_dirtyBlocks.quickSet(blockIndex);
+ }
+
+ // Fixpoint until we do not add any new live values at tail.
+ bool changed;
+ do {
+ changed = false;
+
+ for (BlockIndex blockIndex = numBlock; blockIndex--;) {
+ if (!m_dirtyBlocks.quickClear(blockIndex))
+ continue;
+
+ changed |= processBlock(blockIndex);
+ }
+ } while (changed);
+
+ // Update the per-block node list for live and tail.
+ for (BlockIndex blockIndex = numBlock; blockIndex--;) {
BasicBlock* block = m_graph.block(blockIndex);
if (!block)
continue;
- block->ssa->liveAtTailIsDirty = true;
- block->ssa->liveAtHead.clear();
- block->ssa->liveAtTail.clear();
+
+ {
+ const auto& liveAtHeadIndices = m_liveAtHead[blockIndex];
+ Vector<Node*>& liveAtHead = block->ssa->liveAtHead;
+ liveAtHead.resize(0);
+ liveAtHead.reserveCapacity(liveAtHeadIndices.size());
+ for (unsigned index : liveAtHeadIndices)
+ liveAtHead.uncheckedAppend(m_graph.nodeAt(index));
+ }
+ {
+ const auto& liveAtTailIndices = m_liveAtTail[blockIndex];
+ Vector<Node*>& liveAtTail = block->ssa->liveAtTail;
+ liveAtTail.resize(0);
+ liveAtTail.reserveCapacity(liveAtTailIndices.size());
+ for (unsigned index : m_liveAtTail[blockIndex])
+ liveAtTail.uncheckedAppend(m_graph.nodeAt(index));
+ }
}
-
- do {
- m_changed = false;
- for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;)
- process(blockIndex);
- } while (m_changed);
-
- if (!m_graph.block(0)->ssa->liveAtHead.isEmpty()) {
- DFG_CRASH(
- m_graph, nullptr,
- toCString(
- "Bad liveness analysis result: live at root is not empty: ",
- nodeListDump(m_graph.block(0)->ssa->liveAtHead)).data());
- }
-
+
return true;
}
private:
- void process(BlockIndex blockIndex)
+ bool processBlock(BlockIndex blockIndex)
{
BasicBlock* block = m_graph.block(blockIndex);
- if (!block)
- return;
+ ASSERT_WITH_MESSAGE(block, "Only dirty blocks needs updates. A null block should never be dirty.");
- if (!block->ssa->liveAtTailIsDirty)
- return;
- block->ssa->liveAtTailIsDirty = false;
+ m_workset.clear();
+ for (unsigned index : m_liveAtTail[blockIndex])
+ m_workset.add(index);
- m_live = block->ssa->liveAtTail;
for (unsigned nodeIndex = block->size(); nodeIndex--;) {
Node* node = block->at(nodeIndex);
-
+
// Given an Upsilon:
//
// n: Upsilon(@x, ^p)
@@ -114,49 +133,64 @@
switch (node->op()) {
case Upsilon: {
+ ASSERT_WITH_MESSAGE(!m_workset.contains(node->index()), "Upsilon should not be used as defs by other nodes.");
+
Node* phi = node->phi();
- m_live.remove(phi);
- m_live.remove(node);
- m_live.add(node->child1().node());
+ m_workset.remove(phi->index());
+ m_workset.add(node->child1()->index());
break;
}
-
case Phi: {
break;
}
-
default:
- m_live.remove(node);
+ m_workset.remove(node->index());
DFG_NODE_DO_TO_CHILDREN(m_graph, node, addChildUse);
break;
}
}
-
- for (Node* node : m_live) {
- if (!block->ssa->liveAtHead.contains(node)) {
- m_changed = true;
- for (unsigned i = block->predecessors.size(); i--;) {
- BasicBlock* predecessor = block->predecessors[i];
- if (predecessor->ssa->liveAtTail.add(node).isNewEntry)
- predecessor->ssa->liveAtTailIsDirty = true;
+
+ // Update live at head.
+ auto& liveAtHead = m_liveAtHead[blockIndex];
+ if (m_workset.size() == liveAtHead.size())
+ return false;
+
+ for (unsigned liveIndexAtHead : liveAtHead)
+ m_workset.remove(liveIndexAtHead);
+ ASSERT(!m_workset.isEmpty());
+
+ liveAtHead.reserveCapacity(liveAtHead.size() + m_workset.size());
+ for (unsigned newValue : m_workset)
+ liveAtHead.uncheckedAppend(newValue);
+
+ bool changedPredecessor = false;
+ for (BasicBlock* predecessor : block->predecessors) {
+ auto& liveAtTail = m_liveAtTail[predecessor];
+ for (unsigned newValue : m_workset) {
+ if (liveAtTail.add(newValue)) {
+ if (!m_dirtyBlocks.quickSet(predecessor->index))
+ changedPredecessor = true;
}
}
}
- block->ssa->liveAtHead = WTFMove(m_live);
+ return changedPredecessor;
}
-
- void addChildUse(Node*, Edge& edge)
+
+ ALWAYS_INLINE void addChildUse(Node*, Edge& edge)
{
- addChildUse(edge);
+ bool newEntry = m_workset.add(edge->index());
+ edge.setKillStatus(newEntry ? DoesKill : DoesNotKill);
}
-
- void addChildUse(Edge& edge)
- {
- edge.setKillStatus(m_live.add(edge.node()).isNewEntry ? DoesKill : DoesNotKill);
- }
-
- bool m_changed;
- HashSet<Node*> m_live;
+
+ // Blocks with new live values at tail.
+ BitVector m_dirtyBlocks;
+
+ // Live values per block edge.
+ BlockMap<Vector<unsigned, 0, UnsafeVectorOverflow, 1>> m_liveAtHead;
+ BlockMap<HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>>> m_liveAtTail;
+
+ // Single sparse set allocated once and used by every basic block.
+ IndexSparseSet<UnsafeVectorOverflow> m_workset;
};
bool performLivenessAnalysis(Graph& graph)
