| /* |
| * 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" |
| |
| #if ENABLE(DFG_JIT) |
| |
| #include "DFGSSAConversionPhase.h" |
| |
| #include "DFGBasicBlockInlines.h" |
| #include "DFGGraph.h" |
| #include "DFGInsertionSet.h" |
| #include "DFGPhase.h" |
| #include "Operations.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(); |
| } |
| |
| // Figure out which SetLocal's need flushing. Need to do this while the |
| // Phi graph is still intact. |
| 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(); |
| ASSERT(m_flushedLocalOps.contains(node)); |
| DFG_NODE_DO_TO_CHILDREN(m_graph, node, addFlushedLocalEdge); |
| } |
| |
| // 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 = m_flushedLocalOps.contains(node); |
| |
| 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, CodeOrigin()); |
| 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()->codeOrigin, |
| 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, CodeOrigin(), |
| OpInfo(variable->local().offset()), Edge(node)); |
| } |
| } |
| } |
| |
| 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 but remains, because we want to know when a |
| // flushed SetLocal's value is no longer needed. This also makes it simpler |
| // to reason about the format of a local, since we can just do a backwards |
| // analysis (see FlushLivenessAnalysisPhase). As part of the backwards |
| // analysis, we say that the type of a local can be either int32, double, |
| // value, or dead. |
| // - 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() || m_flushedLocalOps.contains(node)) |
| 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(); |
| // 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: { |
| VariableAccessData* variable = node->variableAccessData(); |
| if (variable->isCaptured()) |
| break; |
| node->child1().setNode(block->variablesAtHead.operand(variable->local())); |
| 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->mergeFlags(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; |
| } |
| } |
| } |
| } |
| |
| void addFlushedLocalOp(Node* node) |
| { |
| if (m_flushedLocalOps.contains(node)) |
| return; |
| m_flushedLocalOps.add(node); |
| m_flushedLocalOpWorklist.append(node); |
| } |
| |
| void addFlushedLocalEdge(Node*, Edge edge) |
| { |
| addFlushedLocalOp(edge.node()); |
| } |
| |
| InsertionSet m_insertionSet; |
| HashSet<Node*> m_flushedLocalOps; |
| Vector<Node*> m_flushedLocalOpWorklist; |
| bool m_changed; |
| }; |
| |
| bool performSSAConversion(Graph& graph) |
| { |
| SamplingRegion samplingRegion("DFG SSA Conversion Phase"); |
| return runPhase<SSAConversionPhase>(graph); |
| } |
| |
| } } // namespace JSC::DFG |
| |
| #endif // ENABLE(DFG_JIT) |
| |
