--- /dev/null
+/*
+ * Copyright (C) 2013 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 "DFGBasicBlockInlines.h"
+#include "DFGGraph.h"
+#include "DFGPhase.h"
+#include "Operations.h"
+
+namespace JSC { namespace DFG {
+
+class CPSRethreadingPhase : public Phase {
+public:
+ CPSRethreadingPhase(Graph& graph)
+ : Phase(graph, "CPS rethreading")
+ {
+ }
+
+ bool run()
+ {
+ if (m_graph.m_form == ThreadedCPS)
+ return false;
+
+ clearIsLoadedFrom();
+ freeUnnecessaryNodes();
+ canonicalizeLocalsInBlocks();
+ propagatePhis<LocalOperand>();
+ propagatePhis<ArgumentOperand>();
+
+ 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()
+ {
+ SamplingRegion samplingRegion("DFG CPS Rethreading: freeUnnecessaryNodes");
+
+ for (BlockIndex blockIndex = m_graph.m_blocks.size(); blockIndex--;) {
+ BasicBlock* block = m_graph.m_blocks[blockIndex].get();
+ 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())
+ continue;
+ switch (node->child1()->op()) {
+ case Phi:
+ case SetArgument:
+ case SetLocal:
+ node->convertToPhantomLocal();
+ break;
+ default:
+ ASSERT(node->child1()->hasResult());
+ break;
+ }
+ break;
+ case Nop:
+ continue;
+ default:
+ break;
+ }
+ node->replacement = 0; // Reset the replacement since the next phase will use it.
+ block->at(toIndex++) = node;
+ }
+ block->resize(toIndex);
+
+ for (unsigned phiIndex = block->phis.size(); phiIndex--;)
+ m_graph.m_allocator.free(block->phis[phiIndex]);
+ block->phis.resize(0);
+ }
+ }
+
+ template<OperandKind operandKind>
+ void clearVariablesAtHeadAndTail()
+ {
+ 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) = 0;
+ m_block->variablesAtTail.atFor<operandKind>(i) = 0;
+ }
+ }
+
+ ALWAYS_INLINE Node* addPhiSilently(BasicBlock* block, const CodeOrigin& codeOrigin, VariableAccessData* variable)
+ {
+ Node* result = m_graph.addNode(SpecNone, Phi, codeOrigin, OpInfo(variable));
+ block->phis.append(result);
+ return result;
+ }
+
+ template<OperandKind operandKind>
+ ALWAYS_INLINE Node* addPhi(BasicBlock* block, const CodeOrigin& codeOrigin, VariableAccessData* variable, size_t index)
+ {
+ Node* result = addPhiSilently(block, codeOrigin, variable);
+ phiStackFor<operandKind>().append(PhiStackEntry(block, index, result));
+ return result;
+ }
+
+ template<OperandKind operandKind>
+ ALWAYS_INLINE Node* addPhi(const CodeOrigin& codeOrigin, VariableAccessData* variable, size_t index)
+ {
+ return addPhi<operandKind>(m_block, codeOrigin, 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() == 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 (variable->isCaptured()) {
+ variable->setIsLoadedFrom(true);
+ if (otherNode->op() == GetLocal)
+ otherNode = otherNode->child1().node();
+ else
+ ASSERT(otherNode->op() == SetLocal || otherNode->op() == SetArgument);
+
+ ASSERT(otherNode->op() == Phi || otherNode->op() == SetLocal || otherNode->op() == SetArgument);
+
+ // Keep this GetLocal but link it to the prior ones.
+ 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->replacement = otherNode;
+ return;
+ }
+
+ ASSERT(otherNode->op() == SetLocal);
+ node->replacement = otherNode->child1().node();
+ return;
+ }
+
+ variable->setIsLoadedFrom(true);
+ Node* phi = addPhi<operandKind>(node->codeOrigin, 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 (operandIsArgument(variable->local()))
+ canonicalizeGetLocalFor<ArgumentOperand>(node, variable, operandToArgument(variable->local()));
+ else
+ canonicalizeGetLocalFor<LocalOperand>(node, variable, variable->local());
+ }
+
+ void canonicalizeSetLocal(Node* node)
+ {
+ m_block->variablesAtTail.setOperand(node->local(), node);
+ }
+
+ 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) {
+ // 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
+ // be keeping the operand to the SetLocal alive. The SetLocal may die, and
+ // we'll be fine because OSR tracks dead SetLocals.
+
+ // So we turn this into a Phantom on the child of the SetLocal.
+
+ node->convertToPhantom();
+ node->children.setChild1(otherNode->child1());
+ 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->codeOrigin, 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 (operandIsArgument(variable->local()))
+ canonicalizeFlushOrPhantomLocalFor<nodeType, ArgumentOperand>(node, variable, operandToArgument(variable->local()));
+ else
+ canonicalizeFlushOrPhantomLocalFor<nodeType, LocalOperand>(node, variable, variable->local());
+ }
+
+ void canonicalizeSetArgument(Node* node)
+ {
+ int local = node->local();
+ ASSERT(operandIsArgument(local));
+ int argument = operandToArgument(local);
+ m_block->variablesAtHead.setArgumentFirstTime(argument, node);
+ m_block->variablesAtTail.setArgumentFirstTime(argument, node);
+ }
+
+ void canonicalizeLocalsInBlock()
+ {
+ if (!m_block)
+ return;
+ ASSERT(m_block->isReachable);
+
+ clearVariablesAtHeadAndTail<ArgumentOperand>();
+ clearVariablesAtHeadAndTail<LocalOperand>();
+
+ // 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 (unsigned nodeIndex = 0; nodeIndex < m_block->size(); ++nodeIndex) {
+ Node* node = m_block->at(nodeIndex);
+
+ 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 SetArgument.
+ // SetArgument 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, or SetArgument.
+ // SetArgument 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.
+ //
+ // Child of GetLocal: the operation that the GetLocal keeps alive. For
+ // uncaptured locals, it may be a Phi from the current block. For arguments,
+ // it may be a SetArgument. For captured locals and arguments it may also be
+ // a SetLocal.
+ //
+ // 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 SetArgument.
+ //
+ // Child of PhantomLocal: it may be a Phi from the current block. For
+ // arguments it may also be a SetArgument.
+ //
+ // Children of Phi: other Phis in the same basic block, or any of the
+ // following from predecessor blocks: SetLocal, Phi, or SetArgument. 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 SetArgument) or
+ // loading that nodes child (if it's a GetLocal, PhanomLocal, or Flush - all
+ // of these will have children that are SetLocal, Phi, or SetArgument).
+
+ switch (node->op()) {
+ case GetLocal:
+ canonicalizeGetLocal(node);
+ break;
+
+ case SetLocal:
+ canonicalizeSetLocal(node);
+ break;
+
+ case Flush:
+ canonicalizeFlushOrPhantomLocal<Flush>(node);
+ break;
+
+ case PhantomLocal:
+ canonicalizeFlushOrPhantomLocal<PhantomLocal>(node);
+ break;
+
+ case SetArgument:
+ canonicalizeSetArgument(node);
+ break;
+
+ default:
+ break;
+ }
+ }
+ }
+
+ void canonicalizeLocalsInBlocks()
+ {
+ SamplingRegion samplingRegion("DFG CPS Rethreading: canonicalizeLocalsInBlocks");
+
+ for (m_blockIndex = m_graph.m_blocks.size(); m_blockIndex--;) {
+ m_block = m_graph.m_blocks[m_blockIndex].get();
+ canonicalizeLocalsInBlock();
+ }
+ }
+
+ template<OperandKind operandKind>
+ void propagatePhis()
+ {
+ Vector<PhiStackEntry, 128>& phiStack = operandKind == ArgumentOperand ? m_argumentPhiStack : m_localPhiStack;
+
+ SamplingRegion samplingRegion("DFG CPS Rethreading: propagatePhis");
+
+ // Ensure that attempts to use this fail instantly.
+ m_block = 0;
+ m_blockIndex = NoBlock;
+
+ while (!phiStack.isEmpty()) {
+ PhiStackEntry entry = phiStack.last();
+ phiStack.removeLast();
+
+ BasicBlock* block = entry.m_block;
+ PredecessorList& predecessors = block->m_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 = m_graph.m_blocks[predecessors[i]].get();
+
+ Node* variableInPrevious = predecessorBlock->variablesAtTail.atFor<operandKind>(index);
+ if (!variableInPrevious) {
+ variableInPrevious = addPhi<operandKind>(predecessorBlock, currentPhi->codeOrigin, 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->codeOrigin, 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;
+ }
+
+ BlockIndex m_blockIndex;
+ BasicBlock* m_block;
+ Vector<PhiStackEntry, 128> m_argumentPhiStack;
+ Vector<PhiStackEntry, 128> m_localPhiStack;
+};
+
+bool performCPSRethreading(Graph& graph)
+{
+ SamplingRegion samplingRegion("DFG CPS Rethreading Phase");
+ return runPhase<CPSRethreadingPhase>(graph);
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
projects / apple / javascriptcore.git / blobdiff