DFGSSAConversionPhase.cpp [plain text]
#include "config.h"
#include "DFGSSAConversionPhase.h"
#if ENABLE(DFG_JIT)
#include "DFGBasicBlockInlines.h"
#include "DFGGraph.h"
#include "DFGInsertionSet.h"
#include "DFGPhase.h"
#include "DFGSSACalculator.h"
#include "DFGVariableAccessDataDump.h"
#include "JSCInlines.h"
namespace JSC { namespace DFG {
class SSAConversionPhase : public Phase {
static const bool verbose = false;
public:
SSAConversionPhase(Graph& graph)
: Phase(graph, "SSA conversion")
, m_calculator(graph)
, m_insertionSet(graph)
{
}
bool run()
{
RELEASE_ASSERT(m_graph.m_form == ThreadedCPS);
m_graph.clearReplacements();
m_graph.ensureDominators();
if (verbose) {
dataLog("Graph before SSA transformation:\n");
m_graph.dump();
}
for (VariableAccessData& variable : m_graph.m_variableAccessData) {
if (!variable.isRoot())
continue;
SSACalculator::Variable* ssaVariable = m_calculator.newVariable();
ASSERT(ssaVariable->index() == m_variableForSSAIndex.size());
m_variableForSSAIndex.append(&variable);
m_ssaVariableForVariable.add(&variable, ssaVariable);
}
for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
BasicBlock* block = m_graph.block(blockIndex);
if (!block)
continue;
for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
Node* node = block->at(nodeIndex);
if (node->op() != SetLocal && node->op() != SetArgument)
continue;
VariableAccessData* variable = node->variableAccessData();
Node* childNode;
if (node->op() == SetLocal)
childNode = node->child1().node();
else {
ASSERT(node->op() == SetArgument);
childNode = m_insertionSet.insertNode(
nodeIndex, node->variableAccessData()->prediction(),
GetStack, node->origin,
OpInfo(m_graph.m_stackAccessData.add(variable->local(), variable->flushFormat())));
if (!ASSERT_DISABLED)
m_argumentGetters.add(childNode);
m_argumentMapping.add(node, childNode);
}
m_calculator.newDef(
m_ssaVariableForVariable.get(variable), block, childNode);
}
m_insertionSet.execute(block);
}
m_calculator.computePhis(
[&] (SSACalculator::Variable* ssaVariable, BasicBlock* block) -> Node* {
VariableAccessData* variable = m_variableForSSAIndex[ssaVariable->index()];
Node* headNode = block->variablesAtHead.operand(variable->local());
if (!headNode)
return nullptr;
if (headNode->variableAccessData() != variable)
return nullptr;
Node* phiNode = m_graph.addNode(
variable->prediction(), Phi, block->at(0)->origin.withInvalidExit());
FlushFormat format = variable->flushFormat();
NodeFlags result = resultFor(format);
phiNode->mergeFlags(result);
return phiNode;
});
if (verbose) {
dataLog("Computed Phis, about to transform the graph.\n");
dataLog("\n");
dataLog("Graph:\n");
m_graph.dump();
dataLog("\n");
dataLog("Mappings:\n");
for (unsigned i = 0; i < m_variableForSSAIndex.size(); ++i)
dataLog(" ", i, ": ", VariableAccessDataDump(m_graph, m_variableForSSAIndex[i]), "\n");
dataLog("\n");
dataLog("SSA calculator: ", m_calculator, "\n");
}
Operands<Node*> valueForOperand(OperandsLike, m_graph.block(0)->variablesAtHead);
for (BasicBlock* block : m_graph.blocksInPreOrder()) {
valueForOperand.clear();
if (block != m_graph.block(0)) {
for (size_t i = valueForOperand.size(); i--;) {
Node* nodeAtHead = block->variablesAtHead[i];
if (!nodeAtHead)
continue;
VariableAccessData* variable = nodeAtHead->variableAccessData();
if (verbose)
dataLog("Considering live variable ", VariableAccessDataDump(m_graph, variable), " at head of block ", *block, "\n");
SSACalculator::Variable* ssaVariable = m_ssaVariableForVariable.get(variable);
SSACalculator::Def* def = m_calculator.reachingDefAtHead(block, ssaVariable);
if (!def) {
continue;
}
Node* node = def->value();
if (node->replacement()) {
node = node->replacement();
ASSERT(!node->replacement());
}
if (verbose)
dataLog("Mapping: ", VirtualRegister(valueForOperand.operandForIndex(i)), " -> ", node, "\n");
valueForOperand[i] = node;
}
}
size_t phiInsertionPoint = 0;
for (SSACalculator::Def* phiDef : m_calculator.phisForBlock(block)) {
VariableAccessData* variable = m_variableForSSAIndex[phiDef->variable()->index()];
m_insertionSet.insert(phiInsertionPoint, phiDef->value());
valueForOperand.operand(variable->local()) = phiDef->value();
m_insertionSet.insertNode(
phiInsertionPoint, SpecNone, MovHint, block->at(0)->origin.withInvalidExit(),
OpInfo(variable->local().offset()), phiDef->value()->defaultEdge());
}
if (block->at(0)->origin.exitOK)
m_insertionSet.insertNode(phiInsertionPoint, SpecNone, ExitOK, block->at(0)->origin);
for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
Node* node = block->at(nodeIndex);
if (verbose) {
dataLog("Processing node ", node, ":\n");
m_graph.dump(WTF::dataFile(), " ", node);
}
m_graph.performSubstitution(node);
switch (node->op()) {
case MovHint: {
m_insertionSet.insertNode(
nodeIndex, SpecNone, KillStack, node->origin,
OpInfo(node->unlinkedLocal().offset()));
node->origin.exitOK = false; break;
}
case SetLocal: {
VariableAccessData* variable = node->variableAccessData();
Node* child = node->child1().node();
if (!!(node->flags() & NodeIsFlushed)) {
node->convertToPutStack(
m_graph.m_stackAccessData.add(
variable->local(), variable->flushFormat()));
} else
node->remove();
if (verbose)
dataLog("Mapping: ", variable->local(), " -> ", child, "\n");
valueForOperand.operand(variable->local()) = child;
break;
}
case GetStack: {
ASSERT(m_argumentGetters.contains(node));
valueForOperand.operand(node->stackAccessData()->local) = node;
break;
}
case GetLocal: {
VariableAccessData* variable = node->variableAccessData();
node->children.reset();
node->remove();
if (verbose)
dataLog("Replacing node ", node, " with ", valueForOperand.operand(variable->local()), "\n");
node->setReplacement(valueForOperand.operand(variable->local()));
break;
}
case Flush: {
node->children.reset();
node->remove();
break;
}
case PhantomLocal: {
ASSERT(node->child1().useKind() == UntypedUse);
VariableAccessData* variable = node->variableAccessData();
node->child1() = valueForOperand.operand(variable->local())->defaultEdge();
node->remove();
break;
}
case SetArgument: {
node->remove();
break;
}
default:
break;
}
}
NodeAndIndex terminal = block->findTerminal();
size_t upsilonInsertionPoint = terminal.index;
NodeOrigin upsilonOrigin = terminal.node->origin;
for (unsigned successorIndex = block->numSuccessors(); successorIndex--;) {
BasicBlock* successorBlock = block->successor(successorIndex);
for (SSACalculator::Def* phiDef : m_calculator.phisForBlock(successorBlock)) {
Node* phiNode = phiDef->value();
SSACalculator::Variable* ssaVariable = phiDef->variable();
VariableAccessData* variable = m_variableForSSAIndex[ssaVariable->index()];
FlushFormat format = variable->flushFormat();
UseKind useKind = uncheckedUseKindFor(format);
m_insertionSet.insertNode(
upsilonInsertionPoint, SpecNone, Upsilon, upsilonOrigin,
OpInfo(phiNode), Edge(
valueForOperand.operand(variable->local()),
useKind));
}
}
m_insertionSet.execute(block);
}
for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
BasicBlock* block = m_graph.block(blockIndex);
if (!block)
continue;
for (unsigned phiIndex = block->phis.size(); phiIndex--;)
m_graph.m_allocator.free(block->phis[phiIndex]);
block->phis.clear();
block->variablesAtHead.clear();
block->variablesAtTail.clear();
block->valuesAtHead.clear();
block->valuesAtHead.clear();
block->ssa = std::make_unique<BasicBlock::SSAData>(block);
}
m_graph.m_argumentFormats.resize(m_graph.m_arguments.size());
for (unsigned i = m_graph.m_arguments.size(); i--;) {
FlushFormat format = FlushedJSValue;
Node* node = m_argumentMapping.get(m_graph.m_arguments[i]);
RELEASE_ASSERT(node);
format = node->stackAccessData()->format;
m_graph.m_argumentFormats[i] = format;
m_graph.m_arguments[i] = node; }
m_graph.m_form = SSA;
if (verbose) {
dataLog("Graph after SSA transformation:\n");
m_graph.dump();
}
return true;
}
private:
SSACalculator m_calculator;
InsertionSet m_insertionSet;
HashMap<VariableAccessData*, SSACalculator::Variable*> m_ssaVariableForVariable;
HashMap<Node*, Node*> m_argumentMapping;
HashSet<Node*> m_argumentGetters;
Vector<VariableAccessData*> m_variableForSSAIndex;
};
bool performSSAConversion(Graph& graph)
{
return runPhase<SSAConversionPhase>(graph);
}
} }
#endif // ENABLE(DFG_JIT)