blob: f273a50b29da87bc03d9a45b942249d1c4c31bf0 [file] [log] [blame]
/*
* Copyright (C) 2013-2015 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#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) {
// We need to have a GetLocal, so this might as well be the one.
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) {
// Replace all references to this GetLocal with otherNode.
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) {
// PhantomLocal(SetLocal) doesn't make sense. PhantomLocal means: at this
// point I know I would have been interested in the value of this variable
// for the purpose of OSR. PhantomLocal(SetLocal) means: at this point I
// know that I would have read the value written by that SetLocal. This is
// redundant and inefficient, since really it just means that we want to
// keep the last MovHinted value of that local alive.
node->remove(m_graph);
return;
}
variable->setIsLoadedFrom(true);
// There is nothing wrong with having redundant Flush's. It just needs to
// be linked appropriately. Note that if there had already been a previous
// use at tail then we don't override it. It's fine for variablesAtTail to
// omit Flushes and PhantomLocals. On the other hand, having it refer to a
// Flush or a PhantomLocal if just before it the last use was a GetLocal would
// seriously confuse the CFA.
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>();
// Assumes that all phi references have been removed. Assumes that things that
// should be live have a non-zero ref count, but doesn't assume that the ref
// counts are correct beyond that (more formally !!logicalRefCount == !!actualRefCount
// but not logicalRefCount == actualRefCount). Assumes that it can break ref
// counts.
for (auto* node : *m_block) {
m_graph.performSubstitution(node);
// The rules for threaded CPS form:
//
// Head variable: describes what is live at the head of the basic block.
// Head variable links may refer to Flush, PhantomLocal, Phi, or SetArgumentDefinitely/SetArgumentMaybe.
// SetArgumentDefinitely/SetArgumentMaybe may only appear in the root block.
//
// Tail variable: the last thing that happened to the variable in the block.
// It may be a Flush, PhantomLocal, GetLocal, SetLocal, SetArgumentDefinitely/SetArgumentMaybe, or Phi.
// SetArgumentDefinitely/SetArgumentMaybe may only appear in the root block. Note that if there ever
// was a GetLocal to the variable, and it was followed by PhantomLocals and
// Flushes but not SetLocals, then the tail variable will be the GetLocal.
// This reflects the fact that you only care that the tail variable is a
// Flush or PhantomLocal if nothing else interesting happened. Likewise, if
// there ever was a SetLocal and it was followed by Flushes, then the tail
// variable will be a SetLocal and not those subsequent Flushes.
//
// Child of GetLocal: the operation that the GetLocal keeps alive. It may be
// a Phi from the current block. For arguments, it may be a SetArgumentDefinitely
// but it can't be a SetArgumentMaybe.
//
// Child of SetLocal: must be a value producing node.
//
// Child of Flush: it may be a Phi from the current block or a SetLocal. For
// arguments it may also be a SetArgumentDefinitely/SetArgumentMaybe.
//
// Child of PhantomLocal: it may be a Phi from the current block. For
// arguments it may also be a SetArgumentDefinitely/SetArgumentMaybe.
//
// Children of Phi: other Phis in the same basic block, or any of the
// following from predecessor blocks: SetLocal, Phi, or SetArgumentDefinitely/SetArgumentMaybe.
// These are computed by looking at the tail variables of the predecessor blocks
// and either using it directly (if it's a SetLocal, Phi, or SetArgumentDefinitely/SetArgumentMaybe) or
// loading that nodes child (if it's a GetLocal, PhanomLocal, or Flush - all
// of these will have children that are SetLocal, Phi, or SetArgumentDefinitely/SetArgumentMaybe).
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()
{
// Normally, a SetArgumentDefinitely denotes the start of a live range for a local's value on the stack.
// But those SetArguments used for the actual arguments to the machine CodeBlock get
// special-cased. We could have instead used two different node types - one for the arguments
// at the prologue case, and another for the other uses. But this seemed like IR overkill.
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>();
// Ensure that attempts to use this fail instantly.
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);
}
} } // namespace JSC::DFG
#endif // ENABLE(DFG_JIT)