DFGLivenessAnalysisPhase.cpp [plain text]
#include "config.h"
#include "DFGLivenessAnalysisPhase.h"
#if ENABLE(DFG_JIT)
#include "DFGBasicBlockInlines.h"
#include "DFGBlockMapInlines.h"
#include "DFGFlowIndexing.h"
#include "DFGGraph.h"
#include "DFGInsertionSet.h"
#include "DFGPhase.h"
#include "JSCInlines.h"
#include <wtf/BitVector.h>
#include <wtf/IndexSparseSet.h>
#include <wtf/LoggingHashSet.h>
namespace JSC { namespace DFG {
namespace {
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)
: Phase(graph, "liveness analysis")
, m_dirtyBlocks(m_graph.numBlocks())
, m_indexing(*m_graph.m_indexingCache)
, m_liveAtHead(m_graph)
, m_liveAtTail(m_graph)
{
m_graph.m_indexingCache->recompute();
m_workset = std::make_unique<Workset>(m_graph.m_indexingCache->numIndices());
}
bool run()
{
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);
}
bool changed;
do {
changed = false;
for (BlockIndex blockIndex = numBlock; blockIndex--;) {
if (!m_dirtyBlocks.quickClear(blockIndex))
continue;
changed |= processBlock(blockIndex);
}
} while (changed);
for (BlockIndex blockIndex = numBlock; blockIndex--;) {
BasicBlock* block = m_graph.block(blockIndex);
if (!block)
continue;
{
const Vector<unsigned, 0, UnsafeVectorOverflow, 1>& liveAtHeadIndices = m_liveAtHead[blockIndex];
Vector<NodeFlowProjection>& liveAtHead = block->ssa->liveAtHead;
liveAtHead.shrink(0);
liveAtHead.reserveCapacity(liveAtHeadIndices.size());
for (unsigned index : liveAtHeadIndices)
liveAtHead.uncheckedAppend(m_indexing.nodeProjection(index));
}
{
const LiveSet& liveAtTailIndices = m_liveAtTail[blockIndex];
Vector<NodeFlowProjection>& liveAtTail = block->ssa->liveAtTail;
liveAtTail.shrink(0);
liveAtTail.reserveCapacity(liveAtTailIndices.size());
for (unsigned index : m_liveAtTail[blockIndex])
liveAtTail.uncheckedAppend(m_indexing.nodeProjection(index));
}
}
return true;
}
private:
bool processBlock(BlockIndex blockIndex)
{
BasicBlock* block = m_graph.block(blockIndex);
ASSERT_WITH_MESSAGE(block, "Only dirty blocks needs updates. A null block should never be dirty.");
m_workset->clear();
for (unsigned index : m_liveAtTail[blockIndex])
m_workset->add(index);
for (unsigned nodeIndex = block->size(); nodeIndex--;) {
Node* node = block->at(nodeIndex);
auto handleEdge = [&] (Edge& edge) {
bool newEntry = m_workset->add(m_indexing.index(edge.node()));
edge.setKillStatus(newEntry ? DoesKill : DoesNotKill);
};
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_workset->remove(m_indexing.shadowIndex(phi));
handleEdge(node->child1());
break;
}
case Phi: {
m_workset->remove(m_indexing.index(node));
m_workset->add(m_indexing.shadowIndex(node));
break;
}
default:
m_workset->remove(m_indexing.index(node));
m_graph.doToChildren(node, handleEdge);
break;
}
}
Vector<unsigned, 0, UnsafeVectorOverflow, 1>& 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) {
LiveSet& liveAtTail = m_liveAtTail[predecessor];
for (unsigned newValue : *m_workset) {
if (liveAtTail.add(newValue)) {
if (!m_dirtyBlocks.quickSet(predecessor->index))
changedPredecessor = true;
}
}
}
return changedPredecessor;
}
BitVector m_dirtyBlocks;
FlowIndexing& m_indexing;
BlockMap<Vector<unsigned, 0, UnsafeVectorOverflow, 1>> m_liveAtHead;
BlockMap<LiveSet> m_liveAtTail;
std::unique_ptr<Workset> m_workset;
};
}
bool performLivenessAnalysis(Graph& graph)
{
graph.packNodeIndices();
return runPhase<LivenessAnalysisPhase>(graph);
}
} }
#endif // ENABLE(DFG_JIT)