--- /dev/null
+/*
+ * Copyright (C) 2013, 2014 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 "DFGSSAConversionPhase.h"
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGBasicBlockInlines.h"
+#include "DFGGraph.h"
+#include "DFGInsertionSet.h"
+#include "DFGPhase.h"
+#include "JSCInlines.h"
+
+namespace JSC { namespace DFG {
+
+class SSAConversionPhase : public Phase {
+ static const bool verbose = false;
+ static const bool dumpGraph = false;
+
+public:
+ SSAConversionPhase(Graph& graph)
+ : Phase(graph, "SSA conversion")
+ , m_insertionSet(graph)
+ , m_changed(false)
+ {
+ }
+
+ bool run()
+ {
+ RELEASE_ASSERT(m_graph.m_form == ThreadedCPS);
+
+ if (dumpGraph) {
+ dataLog("Graph dump at top of SSA conversion:\n");
+ m_graph.dump();
+ }
+
+ // Eliminate all duplicate or self-pointing Phi edges. This means that
+ // we transform:
+ //
+ // p: Phi(@n1, @n2, @n3)
+ //
+ // into:
+ //
+ // p: Phi(@x)
+ //
+ // if each @ni in {@n1, @n2, @n3} is either equal to @p to is equal
+ // to @x, for exactly one other @x. Additionally, trivial Phis (i.e.
+ // p: Phi(@x)) are forwarded, so that if have an edge to such @p, we
+ // replace it with @x. This loop does this for Phis only; later we do
+ // such forwarding for Phi references found in other nodes.
+ //
+ // See Aycock and Horspool in CC'00 for a better description of what
+ // we're doing here.
+ do {
+ m_changed = false;
+ for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+ BasicBlock* block = m_graph.block(blockIndex);
+ if (!block)
+ continue;
+ for (unsigned phiIndex = block->phis.size(); phiIndex--;) {
+ Node* phi = block->phis[phiIndex];
+ if (phi->variableAccessData()->isCaptured())
+ continue;
+ forwardPhiChildren(phi);
+ deduplicateChildren(phi);
+ }
+ }
+ } while (m_changed);
+
+ // For each basic block, for each local live at the head of that block,
+ // figure out what node we should be referring to instead of that local.
+ // If it turns out to be a non-trivial Phi, make sure that we create an
+ // SSA Phi and Upsilons in predecessor blocks. We reuse
+ // BasicBlock::variablesAtHead for tracking which nodes to refer to.
+ Operands<bool> nonTrivialPhis(OperandsLike, m_graph.block(0)->variablesAtHead);
+ for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+ BasicBlock* block = m_graph.block(blockIndex);
+ if (!block)
+ continue;
+
+ nonTrivialPhis.fill(false);
+ for (unsigned i = block->phis.size(); i--;) {
+ Node* phi = block->phis[i];
+ if (!phi->children.justOneChild())
+ nonTrivialPhis.operand(phi->local()) = true;
+ }
+
+ for (unsigned i = block->variablesAtHead.size(); i--;) {
+ Node* node = block->variablesAtHead[i];
+ if (!node)
+ continue;
+
+ if (verbose)
+ dataLog("At block #", blockIndex, " for operand r", block->variablesAtHead.operandForIndex(i), " have node ", node, "\n");
+
+ VariableAccessData* variable = node->variableAccessData();
+ if (variable->isCaptured()) {
+ // Poison this entry in variablesAtHead because we don't
+ // want anyone to try to refer to it, if the variable is
+ // captured.
+ block->variablesAtHead[i] = 0;
+ continue;
+ }
+
+ switch (node->op()) {
+ case Phi:
+ case SetArgument:
+ break;
+ case Flush:
+ case GetLocal:
+ case PhantomLocal:
+ node = node->child1().node();
+ break;
+ default:
+ RELEASE_ASSERT_NOT_REACHED();
+ }
+ RELEASE_ASSERT(node->op() == Phi || node->op() == SetArgument);
+
+ bool isFlushed = !!(node->flags() & NodeIsFlushed);
+
+ if (node->op() == Phi) {
+ if (!nonTrivialPhis.operand(node->local())) {
+ Edge edge = node->children.justOneChild();
+ ASSERT(edge);
+ if (verbose)
+ dataLog(" One child: ", edge, ", ", RawPointer(edge.node()), "\n");
+ node = edge.node(); // It's something from a different basic block.
+ } else {
+ if (verbose)
+ dataLog(" Non-trivial.\n");
+ // It's a non-trivial Phi.
+ FlushFormat format = variable->flushFormat();
+ NodeFlags result = resultFor(format);
+ UseKind useKind = useKindFor(format);
+
+ node = m_insertionSet.insertNode(0, SpecNone, Phi, NodeOrigin());
+ if (verbose)
+ dataLog(" Inserted new node: ", node, "\n");
+ node->mergeFlags(result);
+ RELEASE_ASSERT((node->flags() & NodeResultMask) == result);
+
+ for (unsigned j = block->predecessors.size(); j--;) {
+ BasicBlock* predecessor = block->predecessors[j];
+ predecessor->appendNonTerminal(
+ m_graph, SpecNone, Upsilon, predecessor->last()->origin,
+ OpInfo(node), Edge(predecessor->variablesAtTail[i], useKind));
+ }
+
+ if (isFlushed) {
+ // Do nothing. For multiple reasons.
+
+ // Reason #1: If the local is flushed then we don't need to bother
+ // with a MovHint since every path to this point in the code will
+ // have flushed the bytecode variable using a SetLocal and hence
+ // the Availability::flushedAt() will agree, and that will be
+ // sufficient for figuring out how to recover the variable's value.
+
+ // Reason #2: If we had inserted a MovHint and the Phi function had
+ // died (because the only user of the value was the "flush" - i.e.
+ // some asynchronous runtime thingy) then the MovHint would turn
+ // into a ZombieHint, which would fool us into thinking that the
+ // variable is dead.
+
+ // Reason #3: If we had inserted a MovHint then even if the Phi
+ // stayed alive, we would still end up generating inefficient code
+ // since we would be telling the OSR exit compiler to use some SSA
+ // value for the bytecode variable rather than just telling it that
+ // the value was already on the stack.
+ } else {
+ m_insertionSet.insertNode(
+ 0, SpecNone, MovHint, NodeOrigin(),
+ OpInfo(variable->local().offset()), node->defaultEdge());
+ }
+ }
+ }
+
+ block->variablesAtHead[i] = node;
+ }
+
+ m_insertionSet.execute(block);
+ }
+
+ if (verbose) {
+ dataLog("Variables at head after SSA Phi insertion:\n");
+ for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+ BasicBlock* block = m_graph.block(blockIndex);
+ if (!block)
+ continue;
+ dataLog(" ", *block, ": ", block->variablesAtHead, "\n");
+ }
+ }
+
+ // At this point variablesAtHead in each block refers to either:
+ //
+ // 1) A new SSA phi in the current block.
+ // 2) A SetArgument, which will soon get converted into a GetArgument.
+ // 3) An old CPS phi in a different block.
+ //
+ // We don't have to do anything for (1) and (2), but we do need to
+ // do a replacement for (3).
+
+ // Clear all replacements, since other phases may have used them.
+ m_graph.clearReplacements();
+
+ if (dumpGraph) {
+ dataLog("Graph just before identifying replacements:\n");
+ m_graph.dump();
+ }
+
+ // For all of the old CPS Phis, figure out what they correspond to in SSA.
+ for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+ BasicBlock* block = m_graph.block(blockIndex);
+ if (!block)
+ continue;
+ if (verbose)
+ dataLog("Dealing with block #", blockIndex, "\n");
+ for (unsigned phiIndex = block->phis.size(); phiIndex--;) {
+ Node* phi = block->phis[phiIndex];
+ if (verbose) {
+ dataLog(
+ "Considering ", phi, " (", RawPointer(phi), "), for r",
+ phi->local(), ", and its replacement in ", *block, ", ",
+ block->variablesAtHead.operand(phi->local()), "\n");
+ }
+ ASSERT(phi != block->variablesAtHead.operand(phi->local()));
+ phi->misc.replacement = block->variablesAtHead.operand(phi->local());
+ }
+ }
+
+ // Now make sure that all variablesAtHead in each block points to the
+ // canonical SSA value. Prior to this, variablesAtHead[local] may point to
+ // an old CPS Phi in a different block.
+ for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+ BasicBlock* block = m_graph.block(blockIndex);
+ if (!block)
+ continue;
+ for (size_t i = block->variablesAtHead.size(); i--;) {
+ Node* node = block->variablesAtHead[i];
+ if (!node)
+ continue;
+ while (node->misc.replacement) {
+ ASSERT(node != node->misc.replacement);
+ node = node->misc.replacement;
+ }
+ block->variablesAtHead[i] = node;
+ }
+ }
+
+ if (verbose) {
+ dataLog("Variables at head after convergence:\n");
+ for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+ BasicBlock* block = m_graph.block(blockIndex);
+ if (!block)
+ continue;
+ dataLog(" ", *block, ": ", block->variablesAtHead, "\n");
+ }
+ }
+
+ // Convert operations over locals into operations over SSA nodes.
+ // - GetLocal over captured variables lose their phis.
+ // - GetLocal over uncaptured variables die and get replaced with references
+ // to the node specified by variablesAtHead.
+ // - SetLocal gets NodeMustGenerate if it's flushed, or turns into a
+ // Check otherwise.
+ // - Flush loses its children and turns into a Phantom.
+ // - PhantomLocal becomes Phantom, and its child is whatever is specified
+ // by variablesAtHead.
+ // - SetArgument turns into GetArgument unless it's a captured variable.
+ // - Upsilons get their children fixed to refer to the true value of that local
+ // at the end of the block. Prior to this loop, Upsilons will refer to
+ // variableAtTail[operand], which may be any of Flush, PhantomLocal, GetLocal,
+ // SetLocal, SetArgument, or Phi. We accomplish this by setting the
+ // replacement pointers of all of those nodes to refer to either
+ // variablesAtHead[operand], or the child of the SetLocal.
+ for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+ BasicBlock* block = m_graph.block(blockIndex);
+ if (!block)
+ continue;
+
+ for (unsigned phiIndex = block->phis.size(); phiIndex--;) {
+ block->phis[phiIndex]->misc.replacement =
+ block->variablesAtHead.operand(block->phis[phiIndex]->local());
+ }
+ for (unsigned nodeIndex = block->size(); nodeIndex--;)
+ ASSERT(!block->at(nodeIndex)->misc.replacement);
+
+ for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
+ Node* node = block->at(nodeIndex);
+
+ m_graph.performSubstitution(node);
+
+ switch (node->op()) {
+ case SetLocal: {
+ VariableAccessData* variable = node->variableAccessData();
+ if (variable->isCaptured() || !!(node->flags() & NodeIsFlushed))
+ node->mergeFlags(NodeMustGenerate);
+ else
+ node->setOpAndDefaultFlags(Check);
+ node->misc.replacement = node->child1().node(); // Only for Upsilons.
+ break;
+ }
+
+ case GetLocal: {
+ // It seems tempting to just do forwardPhi(GetLocal), except that we
+ // could have created a new (SSA) Phi, and the GetLocal could still be
+ // referring to an old (CPS) Phi. Uses variablesAtHead to tell us what
+ // to refer to.
+ node->children.reset();
+ VariableAccessData* variable = node->variableAccessData();
+ if (variable->isCaptured())
+ break;
+ node->convertToPhantom();
+ node->misc.replacement = block->variablesAtHead.operand(variable->local());
+ break;
+ }
+
+ case Flush: {
+ node->children.reset();
+ node->convertToPhantom();
+ // This is only for Upsilons. An Upsilon will only refer to a Flush if
+ // there were no SetLocals or GetLocals in the block.
+ node->misc.replacement = block->variablesAtHead.operand(node->local());
+ break;
+ }
+
+ case PhantomLocal: {
+ ASSERT(node->child1().useKind() == UntypedUse);
+ VariableAccessData* variable = node->variableAccessData();
+ if (variable->isCaptured()) {
+ // This is a fun case. We could have a captured variable that had some
+ // or all of its uses strength reduced to phantoms rather than flushes.
+ // SSA conversion will currently still treat it as flushed, in the sense
+ // that it will just keep the SetLocal. Therefore, there is nothing that
+ // needs to be done here: we don't need to also keep the source value
+ // alive. And even if we did want to keep the source value alive, we
+ // wouldn't be able to, because the variablesAtHead value for a captured
+ // local wouldn't have been computed by the Phi reduction algorithm
+ // above.
+ node->children.reset();
+ } else {
+ node->child1() =
+ block->variablesAtHead.operand(variable->local())->defaultEdge();
+ }
+ node->convertToPhantom();
+ // This is only for Upsilons. An Upsilon will only refer to a
+ // PhantomLocal if there were no SetLocals or GetLocals in the block.
+ node->misc.replacement = block->variablesAtHead.operand(variable->local());
+ break;
+ }
+
+ case SetArgument: {
+ VariableAccessData* variable = node->variableAccessData();
+ if (variable->isCaptured())
+ break;
+ node->setOpAndDefaultFlags(GetArgument);
+ node->setResult(resultFor(node->variableAccessData()->flushFormat()));
+ break;
+ }
+
+ default:
+ break;
+ }
+ }
+ }
+
+ // Free all CPS phis and reset variables vectors.
+ 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 = adoptPtr(new BasicBlock::SSAData(block));
+ }
+
+ m_graph.m_arguments.clear();
+
+ m_graph.m_form = SSA;
+ return true;
+ }
+
+private:
+ void forwardPhiChildren(Node* node)
+ {
+ for (unsigned i = 0; i < AdjacencyList::Size; ++i) {
+ Edge& edge = node->children.child(i);
+ if (!edge)
+ break;
+ m_changed |= forwardPhiEdge(edge);
+ }
+ }
+
+ Node* forwardPhi(Node* node)
+ {
+ for (;;) {
+ switch (node->op()) {
+ case Phi: {
+ Edge edge = node->children.justOneChild();
+ if (!edge)
+ return node;
+ node = edge.node();
+ break;
+ }
+ case GetLocal:
+ case SetLocal:
+ if (node->variableAccessData()->isCaptured())
+ return node;
+ node = node->child1().node();
+ break;
+ default:
+ return node;
+ }
+ }
+ }
+
+ bool forwardPhiEdge(Edge& edge)
+ {
+ Node* newNode = forwardPhi(edge.node());
+ if (newNode == edge.node())
+ return false;
+ edge.setNode(newNode);
+ return true;
+ }
+
+ void deduplicateChildren(Node* node)
+ {
+ for (unsigned i = 0; i < AdjacencyList::Size; ++i) {
+ Edge edge = node->children.child(i);
+ if (!edge)
+ break;
+ if (edge == node) {
+ node->children.removeEdge(i--);
+ m_changed = true;
+ continue;
+ }
+ for (unsigned j = i + 1; j < AdjacencyList::Size; ++j) {
+ if (node->children.child(j) == edge) {
+ node->children.removeEdge(j--);
+ m_changed = true;
+ }
+ }
+ }
+ }
+
+ InsertionSet m_insertionSet;
+ bool m_changed;
+};
+
+bool performSSAConversion(Graph& graph)
+{
+ SamplingRegion samplingRegion("DFG SSA Conversion Phase");
+ return runPhase<SSAConversionPhase>(graph);
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
projects / apple / javascriptcore.git / blobdiff