DFGCPSRethreadingPhase.cpp [plain text]
#include "config.h"
#include "DFGCPSRethreadingPhase.h"
#if ENABLE(DFG_JIT)
#include "DFGGraph.h"
#include "DFGPhase.h"
#include "JSCJSValueInlines.h"
namespace JSC { namespace DFG {
class CPSRethreadingPhase : public Phase {
static constexpr bool verbose = false;
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<OperandKind::Local>();
propagatePhis<OperandKind::Argument>();
propagatePhis<OperandKind::Tmp>();
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 SetArgumentMaybe:
DFG_CRASH(m_graph, node, "Invalid Phantom(@SetArgumentMaybe)");
break;
case Phi:
case SetArgumentDefinitely:
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() != SetArgumentMaybe);
ASSERT(otherNode->op() == SetLocal || otherNode->op() == SetArgumentDefinitely);
break;
default:
break;
}
ASSERT(otherNode->op() != SetArgumentMaybe);
ASSERT(otherNode->op() == SetLocal || otherNode->op() == SetArgumentDefinitely || otherNode->op() == GetLocal);
ASSERT(otherNode->variableAccessData() == variable);
if (otherNode->op() == SetArgumentDefinitely) {
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();
switch (variable->operand().kind()) {
case OperandKind::Argument: {
canonicalizeGetLocalFor<OperandKind::Argument>(node, variable, variable->operand().toArgument());
break;
}
case OperandKind::Local: {
canonicalizeGetLocalFor<OperandKind::Local>(node, variable, variable->operand().toLocal());
break;
}
case OperandKind::Tmp: {
canonicalizeGetLocalFor<OperandKind::Tmp>(node, variable, variable->operand().value());
break;
}
}
}
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:
ASSERT(otherNode->child1().node());
otherNode = otherNode->child1().node();
break;
default:
break;
}
ASSERT(otherNode->op() == Phi || otherNode->op() == SetLocal || otherNode->op() == SetArgumentDefinitely || otherNode->op() == SetArgumentMaybe);
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();
switch (variable->operand().kind()) {
case OperandKind::Argument: {
canonicalizeFlushOrPhantomLocalFor<nodeType, OperandKind::Argument>(node, variable, variable->operand().toArgument());
break;
}
case OperandKind::Local: {
canonicalizeFlushOrPhantomLocalFor<nodeType, OperandKind::Local>(node, variable, variable->operand().toLocal());
break;
}
case OperandKind::Tmp: {
canonicalizeFlushOrPhantomLocalFor<nodeType, OperandKind::Tmp>(node, variable, variable->operand().value());
break;
}
}
}
void canonicalizeSet(Node* node)
{
m_block->variablesAtTail.setOperand(node->operand(), node);
}
void canonicalizeLocalsInBlock()
{
if (!m_block)
return;
ASSERT(m_block->isReachable);
clearVariables<OperandKind::Argument>();
clearVariables<OperandKind::Local>();
clearVariables<OperandKind::Tmp>();
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 SetArgumentDefinitely:
case SetArgumentMaybe:
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 = phiStackFor<operandKind>();
m_block = nullptr;
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;
if (verbose) {
dataLog(" Iterating on phi from block ", block, " ");
m_graph.dump(WTF::dataFile(), "", currentPhi);
}
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;
dataLogLnIf(verbose, " No variable in predecessor ", predecessorBlock, " creating a new phi: ", variableInPrevious);
} else {
switch (variableInPrevious->op()) {
case GetLocal:
case PhantomLocal:
case Flush:
dataLogLnIf(verbose, " Variable in predecessor ", predecessorBlock, " ", variableInPrevious, " needs to be forwarded to first child ", variableInPrevious->child1().node());
ASSERT(variableInPrevious->variableAccessData() == variableInPrevious->child1()->variableAccessData());
variableInPrevious = variableInPrevious->child1().node();
break;
default:
break;
}
}
ASSERT(
variableInPrevious->op() == SetLocal
|| variableInPrevious->op() == Phi
|| variableInPrevious->op() == SetArgumentDefinitely
|| variableInPrevious->op() == SetArgumentMaybe);
if (verbose)
m_graph.dump(WTF::dataFile(), " Adding new variable from predecessor ", variableInPrevious);
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, nullptr);
}
}
}
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()
{
switch (operandKind) {
case OperandKind::Argument: return m_argumentPhiStack;
case OperandKind::Local: return m_localPhiStack;
case OperandKind::Tmp: return m_tmpPhiStack;
}
RELEASE_ASSERT_NOT_REACHED();
}
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 SetArgumentDefinitely:
case SetArgumentMaybe:
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<PhiStackEntry, 128> m_tmpPhiStack;
Vector<Node*, 128> m_flushedLocalOpWorklist;
};
bool performCPSRethreading(Graph& graph)
{
return runPhase<CPSRethreadingPhase>(graph);
}
} }
#endif // ENABLE(DFG_JIT)