DFGCPSRethreadingPhase.cpp [plain text]
#include "config.h"
#include "DFGCPSRethreadingPhase.h"
#if ENABLE(DFG_JIT)
#include "DFGBasicBlockInlines.h"
#include "DFGGraph.h"
#include "DFGPhase.h"
#include "JSCInlines.h"
namespace JSC { namespace DFG {
class CPSRethreadingPhase : public Phase {
public:
CPSRethreadingPhase(Graph& graph)
: Phase(graph, "CPS rethreading")
{
}
bool run()
{
RELEASE_ASSERT(m_graph.m_refCountState == EverythingIsLive);
if (m_graph.m_form == ThreadedCPS)
return false;
clearIsLoadedFrom();
freeUnnecessaryNodes();
m_graph.clearReplacements();
canonicalizeLocalsInBlocks();
specialCaseArguments();
propagatePhis<LocalOperand>();
propagatePhis<ArgumentOperand>();
computeIsFlushed();
m_graph.m_form = ThreadedCPS;
return true;
}
private:
void clearIsLoadedFrom()
{
for (unsigned i = 0; i < m_graph.m_variableAccessData.size(); ++i)
m_graph.m_variableAccessData[i].setIsLoadedFrom(false);
}
void freeUnnecessaryNodes()
{
for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
BasicBlock* block = m_graph.block(blockIndex);
if (!block)
continue;
ASSERT(block->isReachable);
unsigned fromIndex = 0;
unsigned toIndex = 0;
while (fromIndex < block->size()) {
Node* node = block->at(fromIndex++);
switch (node->op()) {
case GetLocal:
case Flush:
case PhantomLocal:
node->children.setChild1(Edge());
break;
case Phantom:
if (!node->child1()) {
m_graph.deleteNode(node);
continue;
}
switch (node->child1()->op()) {
case Phi:
case SetArgument:
case SetLocal:
node->convertPhantomToPhantomLocal();
break;
default:
ASSERT(node->child1()->hasResult());
break;
}
break;
default:
break;
}
block->at(toIndex++) = node;
}
block->resize(toIndex);
for (unsigned phiIndex = block->phis.size(); phiIndex--;)
m_graph.deleteNode(block->phis[phiIndex]);
block->phis.resize(0);
}
}
template<OperandKind operandKind>
void clearVariables()
{
ASSERT(
m_block->variablesAtHead.sizeFor<operandKind>()
== m_block->variablesAtTail.sizeFor<operandKind>());
for (unsigned i = m_block->variablesAtHead.sizeFor<operandKind>(); i--;) {
m_block->variablesAtHead.atFor<operandKind>(i) = nullptr;
m_block->variablesAtTail.atFor<operandKind>(i) = nullptr;
}
}
ALWAYS_INLINE Node* addPhiSilently(BasicBlock* block, const NodeOrigin& origin, VariableAccessData* variable)
{
Node* result = m_graph.addNode(Phi, origin, OpInfo(variable));
block->phis.append(result);
return result;
}
template<OperandKind operandKind>
ALWAYS_INLINE Node* addPhi(BasicBlock* block, const NodeOrigin& origin, VariableAccessData* variable, size_t index)
{
Node* result = addPhiSilently(block, origin, variable);
phiStackFor<operandKind>().append(PhiStackEntry(block, index, result));
return result;
}
template<OperandKind operandKind>
ALWAYS_INLINE Node* addPhi(const NodeOrigin& origin, VariableAccessData* variable, size_t index)
{
return addPhi<operandKind>(m_block, origin, variable, index);
}
template<OperandKind operandKind>
void canonicalizeGetLocalFor(Node* node, VariableAccessData* variable, size_t idx)
{
ASSERT(!node->child1());
if (Node* otherNode = m_block->variablesAtTail.atFor<operandKind>(idx)) {
ASSERT(otherNode->variableAccessData() == variable);
switch (otherNode->op()) {
case Flush:
case PhantomLocal:
otherNode = otherNode->child1().node();
if (otherNode->op() == Phi) {
node->children.setChild1(Edge(otherNode));
m_block->variablesAtTail.atFor<operandKind>(idx) = node;
return;
}
ASSERT(otherNode->op() == SetLocal || otherNode->op() == SetArgument);
break;
default:
break;
}
ASSERT(otherNode->op() == SetLocal || otherNode->op() == SetArgument || otherNode->op() == GetLocal);
ASSERT(otherNode->variableAccessData() == variable);
if (otherNode->op() == SetArgument) {
variable->setIsLoadedFrom(true);
node->children.setChild1(Edge(otherNode));
m_block->variablesAtTail.atFor<operandKind>(idx) = node;
return;
}
if (otherNode->op() == GetLocal) {
node->replaceWith(m_graph, otherNode);
return;
}
ASSERT(otherNode->op() == SetLocal);
node->replaceWith(m_graph, otherNode->child1().node());
return;
}
variable->setIsLoadedFrom(true);
Node* phi = addPhi<operandKind>(node->origin, variable, idx);
node->children.setChild1(Edge(phi));
m_block->variablesAtHead.atFor<operandKind>(idx) = phi;
m_block->variablesAtTail.atFor<operandKind>(idx) = node;
}
void canonicalizeGetLocal(Node* node)
{
VariableAccessData* variable = node->variableAccessData();
if (variable->local().isArgument())
canonicalizeGetLocalFor<ArgumentOperand>(node, variable, variable->local().toArgument());
else
canonicalizeGetLocalFor<LocalOperand>(node, variable, variable->local().toLocal());
}
template<NodeType nodeType, OperandKind operandKind>
void canonicalizeFlushOrPhantomLocalFor(Node* node, VariableAccessData* variable, size_t idx)
{
ASSERT(!node->child1());
if (Node* otherNode = m_block->variablesAtTail.atFor<operandKind>(idx)) {
ASSERT(otherNode->variableAccessData() == variable);
switch (otherNode->op()) {
case Flush:
case PhantomLocal:
case GetLocal:
otherNode = otherNode->child1().node();
break;
default:
break;
}
ASSERT(otherNode->op() == Phi || otherNode->op() == SetLocal || otherNode->op() == SetArgument);
if (nodeType == PhantomLocal && otherNode->op() == SetLocal) {
node->remove(m_graph);
return;
}
variable->setIsLoadedFrom(true);
node->children.setChild1(Edge(otherNode));
return;
}
variable->setIsLoadedFrom(true);
node->children.setChild1(Edge(addPhi<operandKind>(node->origin, variable, idx)));
m_block->variablesAtHead.atFor<operandKind>(idx) = node;
m_block->variablesAtTail.atFor<operandKind>(idx) = node;
}
template<NodeType nodeType>
void canonicalizeFlushOrPhantomLocal(Node* node)
{
VariableAccessData* variable = node->variableAccessData();
if (variable->local().isArgument())
canonicalizeFlushOrPhantomLocalFor<nodeType, ArgumentOperand>(node, variable, variable->local().toArgument());
else
canonicalizeFlushOrPhantomLocalFor<nodeType, LocalOperand>(node, variable, variable->local().toLocal());
}
void canonicalizeSet(Node* node)
{
m_block->variablesAtTail.setOperand(node->local(), node);
}
void canonicalizeLocalsInBlock()
{
if (!m_block)
return;
ASSERT(m_block->isReachable);
clearVariables<ArgumentOperand>();
clearVariables<LocalOperand>();
for (auto* node : *m_block) {
m_graph.performSubstitution(node);
switch (node->op()) {
case GetLocal:
canonicalizeGetLocal(node);
break;
case SetLocal:
canonicalizeSet(node);
break;
case Flush:
canonicalizeFlushOrPhantomLocal<Flush>(node);
break;
case PhantomLocal:
canonicalizeFlushOrPhantomLocal<PhantomLocal>(node);
break;
case SetArgument:
canonicalizeSet(node);
break;
default:
break;
}
}
}
void canonicalizeLocalsInBlocks()
{
for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
m_block = m_graph.block(blockIndex);
canonicalizeLocalsInBlock();
}
}
void specialCaseArguments()
{
for (auto& pair : m_graph.m_rootToArguments) {
BasicBlock* entrypoint = pair.key;
const ArgumentsVector& arguments = pair.value;
for (unsigned i = arguments.size(); i--;)
entrypoint->variablesAtHead.setArgumentFirstTime(i, arguments[i]);
}
}
template<OperandKind operandKind>
void propagatePhis()
{
Vector<PhiStackEntry, 128>& phiStack = operandKind == ArgumentOperand ? m_argumentPhiStack : m_localPhiStack;
m_block = 0;
while (!phiStack.isEmpty()) {
PhiStackEntry entry = phiStack.last();
phiStack.removeLast();
BasicBlock* block = entry.m_block;
PredecessorList& predecessors = block->predecessors;
Node* currentPhi = entry.m_phi;
VariableAccessData* variable = currentPhi->variableAccessData();
size_t index = entry.m_index;
for (size_t i = predecessors.size(); i--;) {
BasicBlock* predecessorBlock = predecessors[i];
Node* variableInPrevious = predecessorBlock->variablesAtTail.atFor<operandKind>(index);
if (!variableInPrevious) {
variableInPrevious = addPhi<operandKind>(predecessorBlock, currentPhi->origin, variable, index);
predecessorBlock->variablesAtTail.atFor<operandKind>(index) = variableInPrevious;
predecessorBlock->variablesAtHead.atFor<operandKind>(index) = variableInPrevious;
} else {
switch (variableInPrevious->op()) {
case GetLocal:
case PhantomLocal:
case Flush:
ASSERT(variableInPrevious->variableAccessData() == variableInPrevious->child1()->variableAccessData());
variableInPrevious = variableInPrevious->child1().node();
break;
default:
break;
}
}
ASSERT(
variableInPrevious->op() == SetLocal
|| variableInPrevious->op() == Phi
|| variableInPrevious->op() == SetArgument);
if (!currentPhi->child1()) {
currentPhi->children.setChild1(Edge(variableInPrevious));
continue;
}
if (!currentPhi->child2()) {
currentPhi->children.setChild2(Edge(variableInPrevious));
continue;
}
if (!currentPhi->child3()) {
currentPhi->children.setChild3(Edge(variableInPrevious));
continue;
}
Node* newPhi = addPhiSilently(block, currentPhi->origin, variable);
newPhi->children = currentPhi->children;
currentPhi->children.initialize(newPhi, variableInPrevious, 0);
}
}
}
struct PhiStackEntry {
PhiStackEntry(BasicBlock* block, size_t index, Node* phi)
: m_block(block)
, m_index(index)
, m_phi(phi)
{
}
BasicBlock* m_block;
size_t m_index;
Node* m_phi;
};
template<OperandKind operandKind>
Vector<PhiStackEntry, 128>& phiStackFor()
{
if (operandKind == ArgumentOperand)
return m_argumentPhiStack;
return m_localPhiStack;
}
void computeIsFlushed()
{
m_graph.clearFlagsOnAllNodes(NodeIsFlushed);
for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
BasicBlock* block = m_graph.block(blockIndex);
if (!block)
continue;
for (unsigned nodeIndex = block->size(); nodeIndex--;) {
Node* node = block->at(nodeIndex);
if (node->op() != Flush)
continue;
addFlushedLocalOp(node);
}
}
while (!m_flushedLocalOpWorklist.isEmpty()) {
Node* node = m_flushedLocalOpWorklist.takeLast();
switch (node->op()) {
case SetLocal:
case SetArgument:
break;
case Flush:
case Phi:
ASSERT(node->flags() & NodeIsFlushed);
DFG_NODE_DO_TO_CHILDREN(m_graph, node, addFlushedLocalEdge);
break;
default:
DFG_CRASH(m_graph, node, "Invalid node in flush graph");
break;
}
}
}
void addFlushedLocalOp(Node* node)
{
if (node->mergeFlags(NodeIsFlushed))
m_flushedLocalOpWorklist.append(node);
}
void addFlushedLocalEdge(Node*, Edge edge)
{
addFlushedLocalOp(edge.node());
}
BasicBlock* m_block;
Vector<PhiStackEntry, 128> m_argumentPhiStack;
Vector<PhiStackEntry, 128> m_localPhiStack;
Vector<Node*, 128> m_flushedLocalOpWorklist;
};
bool performCPSRethreading(Graph& graph)
{
return runPhase<CPSRethreadingPhase>(graph);
}
} }
#endif // ENABLE(DFG_JIT)