DFGPutStackSinkingPhase.cpp [plain text]
#include "config.h"
#include "DFGPutStackSinkingPhase.h"
#if ENABLE(DFG_JIT)
#include "DFGBlockMapInlines.h"
#include "DFGGraph.h"
#include "DFGInsertionSet.h"
#include "DFGPhase.h"
#include "DFGPreciseLocalClobberize.h"
#include "DFGSSACalculator.h"
#include "DFGValidate.h"
#include "JSCInlines.h"
#include "OperandsInlines.h"
namespace JSC { namespace DFG {
namespace {
namespace DFGPutStackSinkingPhaseInternal {
static const bool verbose = false;
}
class PutStackSinkingPhase : public Phase {
public:
PutStackSinkingPhase(Graph& graph)
: Phase(graph, "PutStack sinking")
{
}
bool run()
{
if (DFGPutStackSinkingPhaseInternal::verbose) {
dataLog("Graph before PutStack sinking:\n");
m_graph.dump();
}
m_graph.ensureSSADominators();
SSACalculator ssaCalculator(m_graph);
InsertionSet insertionSet(m_graph);
BlockMap<Operands<bool>> liveAtHead(m_graph);
BlockMap<Operands<bool>> liveAtTail(m_graph);
for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
liveAtHead[block] = Operands<bool>(OperandsLike, block->variablesAtHead);
liveAtTail[block] = Operands<bool>(OperandsLike, block->variablesAtHead);
liveAtHead[block].fill(false);
liveAtTail[block].fill(false);
}
bool changed;
do {
changed = false;
for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
BasicBlock* block = m_graph.block(blockIndex);
if (!block)
continue;
Operands<bool> live = liveAtTail[block];
for (unsigned nodeIndex = block->size(); nodeIndex--;) {
Node* node = block->at(nodeIndex);
if (DFGPutStackSinkingPhaseInternal::verbose)
dataLog("Live at ", node, ": ", live, "\n");
Vector<VirtualRegister, 4> reads;
Vector<VirtualRegister, 4> writes;
auto escapeHandler = [&] (VirtualRegister operand) {
if (operand.isHeader())
return;
if (DFGPutStackSinkingPhaseInternal::verbose)
dataLog(" ", operand, " is live at ", node, "\n");
reads.append(operand);
};
auto writeHandler = [&] (VirtualRegister operand) {
if (operand.isHeader())
return;
RELEASE_ASSERT(node->op() == PutStack || node->op() == LoadVarargs || node->op() == ForwardVarargs || node->op() == KillStack);
writes.append(operand);
};
preciseLocalClobberize(
m_graph, node, escapeHandler, writeHandler,
[&] (VirtualRegister, LazyNode) { });
for (VirtualRegister operand : writes)
live.operand(operand) = false;
for (VirtualRegister operand : reads)
live.operand(operand) = true;
}
if (live == liveAtHead[block])
continue;
liveAtHead[block] = live;
changed = true;
for (BasicBlock* predecessor : block->predecessors) {
for (size_t i = live.size(); i--;)
liveAtTail[predecessor][i] |= live[i];
}
}
} while (changed);
for (size_t i = liveAtHead.atIndex(0).numberOfArguments(); i--;)
DFG_ASSERT(m_graph, nullptr, liveAtHead.atIndex(0).argument(i));
BlockMap<Operands<FlushFormat>> deferredAtHead(m_graph);
BlockMap<Operands<FlushFormat>> deferredAtTail(m_graph);
for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
deferredAtHead[block] =
Operands<FlushFormat>(OperandsLike, block->variablesAtHead);
deferredAtTail[block] =
Operands<FlushFormat>(OperandsLike, block->variablesAtHead);
}
for (unsigned local = deferredAtHead.atIndex(0).numberOfLocals(); local--;)
deferredAtHead.atIndex(0).local(local) = ConflictingFlush;
do {
changed = false;
for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
Operands<FlushFormat> deferred = deferredAtHead[block];
for (Node* node : *block) {
if (DFGPutStackSinkingPhaseInternal::verbose)
dataLog("Deferred at ", node, ":", deferred, "\n");
if (node->op() == GetStack) {
bool isConflicting =
deferred.operand(node->stackAccessData()->local) == ConflictingFlush;
if (validationEnabled())
DFG_ASSERT(m_graph, node, !isConflicting);
if (isConflicting) {
return false;
}
continue;
} else if (node->op() == PutStack) {
VirtualRegister operand = node->stackAccessData()->local;
deferred.operand(operand) = node->stackAccessData()->format;
continue;
} else if (node->op() == KillStack) {
deferred.operand(node->unlinkedLocal()) = ConflictingFlush;
continue;
}
auto escapeHandler = [&] (VirtualRegister operand) {
if (DFGPutStackSinkingPhaseInternal::verbose)
dataLog("For ", node, " escaping ", operand, "\n");
if (operand.isHeader())
return;
deferred.operand(operand) = DeadFlush;
};
auto writeHandler = [&] (VirtualRegister operand) {
if (operand.isHeader())
return;
RELEASE_ASSERT(node->op() == LoadVarargs || node->op() == ForwardVarargs);
deferred.operand(operand) = DeadFlush;
};
preciseLocalClobberize(
m_graph, node, escapeHandler, writeHandler,
[&] (VirtualRegister, LazyNode) { });
}
if (deferred == deferredAtTail[block])
continue;
deferredAtTail[block] = deferred;
changed = true;
for (BasicBlock* successor : block->successors()) {
for (size_t i = deferred.size(); i--;) {
if (DFGPutStackSinkingPhaseInternal::verbose)
dataLog("Considering ", VirtualRegister(deferred.operandForIndex(i)), " at ", pointerDump(block), "->", pointerDump(successor), ": ", deferred[i], " and ", deferredAtHead[successor][i], " merges to ");
deferredAtHead[successor][i] =
merge(deferredAtHead[successor][i], deferred[i]);
if (DFGPutStackSinkingPhaseInternal::verbose)
dataLog(deferredAtHead[successor][i], "\n");
}
}
}
} while (changed);
Operands<SSACalculator::Variable*> operandToVariable(
OperandsLike, m_graph.block(0)->variablesAtHead);
Vector<VirtualRegister> indexToOperand;
for (size_t i = m_graph.block(0)->variablesAtHead.size(); i--;) {
VirtualRegister operand(m_graph.block(0)->variablesAtHead.operandForIndex(i));
SSACalculator::Variable* variable = ssaCalculator.newVariable();
operandToVariable.operand(operand) = variable;
ASSERT(indexToOperand.size() == variable->index());
indexToOperand.append(operand);
}
HashSet<Node*> putStacksToSink;
for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
for (Node* node : *block) {
switch (node->op()) {
case PutStack:
putStacksToSink.add(node);
ssaCalculator.newDef(
operandToVariable.operand(node->stackAccessData()->local),
block, node->child1().node());
break;
case GetStack:
ssaCalculator.newDef(
operandToVariable.operand(node->stackAccessData()->local),
block, node);
break;
default:
break;
}
}
}
ssaCalculator.computePhis(
[&] (SSACalculator::Variable* variable, BasicBlock* block) -> Node* {
VirtualRegister operand = indexToOperand[variable->index()];
if (!liveAtHead[block].operand(operand))
return nullptr;
FlushFormat format = deferredAtHead[block].operand(operand);
if (!isConcrete(format))
return nullptr;
if (DFGPutStackSinkingPhaseInternal::verbose)
dataLog("Adding Phi for ", operand, " at ", pointerDump(block), "\n");
Node* phiNode = m_graph.addNode(SpecHeapTop, Phi, block->at(0)->origin.withInvalidExit());
phiNode->mergeFlags(resultFor(format));
return phiNode;
});
Operands<Node*> mapping(OperandsLike, m_graph.block(0)->variablesAtHead);
Operands<FlushFormat> deferred;
for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
mapping.fill(nullptr);
for (size_t i = mapping.size(); i--;) {
VirtualRegister operand(mapping.operandForIndex(i));
SSACalculator::Variable* variable = operandToVariable.operand(operand);
SSACalculator::Def* def = ssaCalculator.reachingDefAtHead(block, variable);
if (!def)
continue;
mapping.operand(operand) = def->value();
}
if (DFGPutStackSinkingPhaseInternal::verbose)
dataLog("Mapping at top of ", pointerDump(block), ": ", mapping, "\n");
for (SSACalculator::Def* phiDef : ssaCalculator.phisForBlock(block)) {
VirtualRegister operand = indexToOperand[phiDef->variable()->index()];
insertionSet.insert(0, phiDef->value());
if (DFGPutStackSinkingPhaseInternal::verbose)
dataLog(" Mapping ", operand, " to ", phiDef->value(), "\n");
mapping.operand(operand) = phiDef->value();
}
deferred = deferredAtHead[block];
for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
Node* node = block->at(nodeIndex);
if (DFGPutStackSinkingPhaseInternal::verbose)
dataLog("Deferred at ", node, ":", deferred, "\n");
switch (node->op()) {
case PutStack: {
StackAccessData* data = node->stackAccessData();
VirtualRegister operand = data->local;
deferred.operand(operand) = data->format;
if (DFGPutStackSinkingPhaseInternal::verbose)
dataLog(" Mapping ", operand, " to ", node->child1().node(), " at ", node, "\n");
mapping.operand(operand) = node->child1().node();
break;
}
case GetStack: {
StackAccessData* data = node->stackAccessData();
FlushFormat format = deferred.operand(data->local);
if (!isConcrete(format)) {
DFG_ASSERT(
m_graph, node,
deferred.operand(data->local) != ConflictingFlush, deferred.operand(data->local));
mapping.operand(data->local) = node;
break;
}
DFG_ASSERT(m_graph, node, format == data->format, format, data->format);
Node* incoming = mapping.operand(data->local);
node->child1() = incoming->defaultEdge();
node->convertToIdentity();
break;
}
case KillStack: {
deferred.operand(node->unlinkedLocal()) = ConflictingFlush;
break;
}
default: {
auto escapeHandler = [&] (VirtualRegister operand) {
if (DFGPutStackSinkingPhaseInternal::verbose)
dataLog("For ", node, " escaping ", operand, "\n");
if (operand.isHeader())
return;
FlushFormat format = deferred.operand(operand);
if (!isConcrete(format)) {
deferred.operand(operand) = DeadFlush;
return;
}
if (DFGPutStackSinkingPhaseInternal::verbose)
dataLog("Inserting a PutStack for ", operand, " at ", node, "\n");
Node* incoming = mapping.operand(operand);
DFG_ASSERT(m_graph, node, incoming);
insertionSet.insertNode(
nodeIndex, SpecNone, PutStack, node->origin,
OpInfo(m_graph.m_stackAccessData.add(operand, format)),
Edge(incoming, uncheckedUseKindFor(format)));
deferred.operand(operand) = DeadFlush;
};
auto writeHandler = [&] (VirtualRegister operand) {
if (operand.isHeader())
return;
RELEASE_ASSERT(node->op() == LoadVarargs || node->op() == ForwardVarargs);
deferred.operand(operand) = DeadFlush;
};
preciseLocalClobberize(
m_graph, node, escapeHandler, writeHandler,
[&] (VirtualRegister, LazyNode) { });
break;
} }
}
NodeAndIndex terminal = block->findTerminal();
size_t upsilonInsertionPoint = terminal.index;
NodeOrigin upsilonOrigin = terminal.node->origin;
for (BasicBlock* successorBlock : block->successors()) {
for (SSACalculator::Def* phiDef : ssaCalculator.phisForBlock(successorBlock)) {
Node* phiNode = phiDef->value();
SSACalculator::Variable* variable = phiDef->variable();
VirtualRegister operand = indexToOperand[variable->index()];
if (DFGPutStackSinkingPhaseInternal::verbose)
dataLog("Creating Upsilon for ", operand, " at ", pointerDump(block), "->", pointerDump(successorBlock), "\n");
FlushFormat format = deferredAtHead[successorBlock].operand(operand);
DFG_ASSERT(m_graph, nullptr, isConcrete(format), format);
UseKind useKind = uncheckedUseKindFor(format);
Node* incoming;
if (isConcrete(deferred.operand(operand))) {
incoming = mapping.operand(operand);
DFG_ASSERT(m_graph, phiNode, incoming);
} else {
incoming = insertionSet.insertNode(
upsilonInsertionPoint, SpecNone, GetStack, upsilonOrigin,
OpInfo(m_graph.m_stackAccessData.add(operand, format)));
incoming->setResult(resultFor(format));
}
insertionSet.insertNode(
upsilonInsertionPoint, SpecNone, Upsilon, upsilonOrigin,
OpInfo(phiNode), Edge(incoming, useKind));
}
}
insertionSet.execute(block);
}
for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
for (auto* node : *block) {
if (!putStacksToSink.contains(node))
continue;
node->remove(m_graph);
}
}
if (DFGPutStackSinkingPhaseInternal::verbose) {
dataLog("Graph after PutStack sinking:\n");
m_graph.dump();
}
return true;
}
};
}
bool performPutStackSinking(Graph& graph)
{
return runPhase<PutStackSinkingPhase>(graph);
}
} }
#endif // ENABLE(DFG_JIT)