[apple/javascriptcore.git] / dfg / DFGSSAConversionPhase.cpp

/*
 * 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 "DFGSSAConversionPhase.h"

#if ENABLE(DFG_JIT)

#include "DFGBasicBlockInlines.h"
#include "DFGGraph.h"
#include "DFGInsertionSet.h"
#include "DFGPhase.h"
#include "DFGSSACalculator.h"
#include "DFGVariableAccessDataDump.h"
#include "JSCInlines.h"

namespace JSC { namespace DFG {

class SSAConversionPhase : public Phase {
    static const bool verbose = false;
    
public:
    SSAConversionPhase(Graph& graph)
        : Phase(graph, "SSA conversion")
        , m_calculator(graph)
        , m_insertionSet(graph)
    {
    }
    
    bool run()
    {
        RELEASE_ASSERT(m_graph.m_form == ThreadedCPS);
        
        m_graph.clearReplacements();
        m_graph.m_dominators.computeIfNecessary(m_graph);
        
        if (verbose) {
            dataLog("Graph before SSA transformation:\n");
            m_graph.dump();
        }

        // Create a SSACalculator::Variable for every root VariableAccessData.
        for (VariableAccessData& variable : m_graph.m_variableAccessData) {
            if (!variable.isRoot())
                continue;
            
            SSACalculator::Variable* ssaVariable = m_calculator.newVariable();
            ASSERT(ssaVariable->index() == m_variableForSSAIndex.size());
            m_variableForSSAIndex.append(&variable);
            m_ssaVariableForVariable.add(&variable, ssaVariable);
        }
        
        // Find all SetLocals and create Defs for them. We handle SetArgument by creating a
        // GetLocal, and recording the flush format.
        for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
            BasicBlock* block = m_graph.block(blockIndex);
            if (!block)
                continue;
            
            // Must process the block in forward direction because we want to see the last
            // assignment for every local.
            for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
                Node* node = block->at(nodeIndex);
                if (node->op() != SetLocal && node->op() != SetArgument)
                    continue;
                
                VariableAccessData* variable = node->variableAccessData();
                
                Node* childNode;
                if (node->op() == SetLocal)
                    childNode = node->child1().node();
                else {
                    ASSERT(node->op() == SetArgument);
                    childNode = m_insertionSet.insertNode(
                        nodeIndex, node->variableAccessData()->prediction(),
                        GetStack, node->origin,
                        OpInfo(m_graph.m_stackAccessData.add(variable->local(), variable->flushFormat())));
                    if (!ASSERT_DISABLED)
                        m_argumentGetters.add(childNode);
                    m_argumentMapping.add(node, childNode);
                }
                
                m_calculator.newDef(
                    m_ssaVariableForVariable.get(variable), block, childNode);
            }
            
            m_insertionSet.execute(block);
        }
        
        // Decide where Phis are to be inserted. This creates the Phi's but doesn't insert them
        // yet. We will later know where to insert them because SSACalculator is such a bro.
        m_calculator.computePhis(
            [&] (SSACalculator::Variable* ssaVariable, BasicBlock* block) -> Node* {
                VariableAccessData* variable = m_variableForSSAIndex[ssaVariable->index()];
                
                // Prune by liveness. This doesn't buy us much other than compile times.
                Node* headNode = block->variablesAtHead.operand(variable->local());
                if (!headNode)
                    return nullptr;

                // There is the possibiltiy of "rebirths". The SSA calculator will already prune
                // rebirths for the same VariableAccessData. But it will not be able to prune
                // rebirths that arose from the same local variable number but a different
                // VariableAccessData. We do that pruning here.
                //
                // Here's an example of a rebirth that this would catch:
                //
                //     var x;
                //     if (foo) {
                //         if (bar) {
                //             x = 42;
                //         } else {
                //             x = 43;
                //         }
                //         print(x);
                //         x = 44;
                //     } else {
                //         x = 45;
                //     }
                //     print(x); // Without this check, we'd have a Phi for x = 42|43 here.
                //
                // FIXME: Consider feeding local variable numbers, not VariableAccessData*'s, as
                // the "variables" for SSACalculator. That would allow us to eliminate this
                // special case.
                // https://bugs.webkit.org/show_bug.cgi?id=136641
                if (headNode->variableAccessData() != variable)
                    return nullptr;
                
                Node* phiNode = m_graph.addNode(
                    variable->prediction(), Phi, NodeOrigin());
                FlushFormat format = variable->flushFormat();
                NodeFlags result = resultFor(format);
                phiNode->mergeFlags(result);
                return phiNode;
            });
        
        if (verbose) {
            dataLog("Computed Phis, about to transform the graph.\n");
            dataLog("\n");
            dataLog("Graph:\n");
            m_graph.dump();
            dataLog("\n");
            dataLog("Mappings:\n");
            for (unsigned i = 0; i < m_variableForSSAIndex.size(); ++i)
                dataLog("    ", i, ": ", VariableAccessDataDump(m_graph, m_variableForSSAIndex[i]), "\n");
            dataLog("\n");
            dataLog("SSA calculator: ", m_calculator, "\n");
        }
        
        // Do the bulk of the SSA conversion. For each block, this tracks the operand->Node
        // mapping based on a combination of what the SSACalculator tells us, and us walking over
        // the block in forward order. We use our own data structure, valueForOperand, for
        // determining the local mapping, but we rely on SSACalculator for the non-local mapping.
        //
        // This does three things at once:
        //
        // - Inserts the Phis in all of the places where they need to go. We've already created
        //   them and they are accounted for in the SSACalculator's data structures, but we
        //   haven't inserted them yet, mostly because we want to insert all of a block's Phis in
        //   one go to amortize the cost of node insertion.
        //
        // - Create and insert Upsilons.
        //
        // - Convert all of the preexisting SSA nodes (other than the old CPS Phi nodes) into SSA
        //   form by replacing as follows:
        //
        //   - MovHint has KillLocal prepended to it.
        //
        //   - GetLocal die and get replaced with references to the node specified by
        //     valueForOperand.
        //
        //   - SetLocal turns into PutStack 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
        //     valueForOperand.
        //
        //   - SetArgument is removed. Note that GetStack nodes have already been inserted.
        Operands<Node*> valueForOperand(OperandsLike, m_graph.block(0)->variablesAtHead);
        for (BasicBlock* block : m_graph.blocksInPreOrder()) {
            valueForOperand.clear();
            
            // CPS will claim that the root block has all arguments live. But we have already done
            // the first step of SSA conversion: argument locals are no longer live at head;
            // instead we have GetStack nodes for extracting the values of arguments. So, we
            // skip the at-head available value calculation for the root block.
            if (block != m_graph.block(0)) {
                for (size_t i = valueForOperand.size(); i--;) {
                    Node* nodeAtHead = block->variablesAtHead[i];
                    if (!nodeAtHead)
                        continue;
                    
                    VariableAccessData* variable = nodeAtHead->variableAccessData();
                    
                    if (verbose)
                        dataLog("Considering live variable ", VariableAccessDataDump(m_graph, variable), " at head of block ", *block, "\n");
                    
                    SSACalculator::Variable* ssaVariable = m_ssaVariableForVariable.get(variable);
                    SSACalculator::Def* def = m_calculator.reachingDefAtHead(block, ssaVariable);
                    if (!def) {
                        // If we are required to insert a Phi, then we won't have a reaching def
                        // at head.
                        continue;
                    }
                    
                    Node* node = def->value();
                    if (node->replacement()) {
                        // This will occur when a SetLocal had a GetLocal as its source. The
                        // GetLocal would get replaced with an actual SSA value by the time we get
                        // here. Note that the SSA value with which the GetLocal got replaced
                        // would not in turn have a replacement.
                        node = node->replacement();
                        ASSERT(!node->replacement());
                    }
                    if (verbose)
                        dataLog("Mapping: ", VirtualRegister(valueForOperand.operandForIndex(i)), " -> ", node, "\n");
                    valueForOperand[i] = node;
                }
            }
            
            // Insert Phis by asking the calculator what phis there are in this block. Also update
            // valueForOperand with those Phis. For Phis associated with variables that are not
            // flushed, we also insert a MovHint.
            size_t phiInsertionPoint = 0;
            for (SSACalculator::Def* phiDef : m_calculator.phisForBlock(block)) {
                VariableAccessData* variable = m_variableForSSAIndex[phiDef->variable()->index()];
                
                m_insertionSet.insert(phiInsertionPoint, phiDef->value());
                valueForOperand.operand(variable->local()) = phiDef->value();
                
                m_insertionSet.insertNode(
                    phiInsertionPoint, SpecNone, MovHint, NodeOrigin(),
                    OpInfo(variable->local().offset()), phiDef->value()->defaultEdge());
            }
            
            for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
                Node* node = block->at(nodeIndex);
                
                if (verbose) {
                    dataLog("Processing node ", node, ":\n");
                    m_graph.dump(WTF::dataFile(), "    ", node);
                }
                
                m_graph.performSubstitution(node);
                
                switch (node->op()) {
                case MovHint: {
                    m_insertionSet.insertNode(
                        nodeIndex, SpecNone, KillStack, node->origin,
                        OpInfo(node->unlinkedLocal().offset()));
                    break;
                }
                    
                case SetLocal: {
                    VariableAccessData* variable = node->variableAccessData();
                    Node* child = node->child1().node();
                    
                    if (!!(node->flags() & NodeIsFlushed)) {
                        node->convertToPutStack(
                            m_graph.m_stackAccessData.add(
                                variable->local(), variable->flushFormat()));
                    } else
                        node->remove();
                    
                    if (verbose)
                        dataLog("Mapping: ", variable->local(), " -> ", child, "\n");
                    valueForOperand.operand(variable->local()) = child;
                    break;
                }
                    
                case GetStack: {
                    ASSERT(m_argumentGetters.contains(node));
                    valueForOperand.operand(node->stackAccessData()->local) = node;
                    break;
                }
                    
                case GetLocal: {
                    VariableAccessData* variable = node->variableAccessData();
                    node->children.reset();
                    
                    node->remove();
                    if (verbose)
                        dataLog("Replacing node ", node, " with ", valueForOperand.operand(variable->local()), "\n");
                    node->setReplacement(valueForOperand.operand(variable->local()));
                    break;
                }
                    
                case Flush: {
                    node->children.reset();
                    node->remove();
                    break;
                }
                    
                case PhantomLocal: {
                    ASSERT(node->child1().useKind() == UntypedUse);
                    VariableAccessData* variable = node->variableAccessData();
                    node->child1() = valueForOperand.operand(variable->local())->defaultEdge();
                    node->remove();
                    break;
                }
                    
                case SetArgument: {
                    node->remove();
                    break;
                }
                    
                default:
                    break;
                }
            }
            
            // We want to insert Upsilons just before the end of the block. On the surface this
            // seems dangerous because the Upsilon will have a checking UseKind. But, we will not
            // actually be performing the check at the point of the Upsilon; the check will
            // already have been performed at the point where the original SetLocal was.
            NodeAndIndex terminal = block->findTerminal();
            size_t upsilonInsertionPoint = terminal.index;
            NodeOrigin upsilonOrigin = terminal.node->origin;
            for (unsigned successorIndex = block->numSuccessors(); successorIndex--;) {
                BasicBlock* successorBlock = block->successor(successorIndex);
                for (SSACalculator::Def* phiDef : m_calculator.phisForBlock(successorBlock)) {
                    Node* phiNode = phiDef->value();
                    SSACalculator::Variable* ssaVariable = phiDef->variable();
                    VariableAccessData* variable = m_variableForSSAIndex[ssaVariable->index()];
                    FlushFormat format = variable->flushFormat();
                    UseKind useKind = useKindFor(format);
                    
                    m_insertionSet.insertNode(
                        upsilonInsertionPoint, SpecNone, Upsilon, upsilonOrigin,
                        OpInfo(phiNode), Edge(
                            valueForOperand.operand(variable->local()),
                            useKind));
                }
            }
            
            m_insertionSet.execute(block);
        }
        
        // 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 = std::make_unique<BasicBlock::SSAData>(block);
        }
        
        m_graph.m_argumentFormats.resize(m_graph.m_arguments.size());
        for (unsigned i = m_graph.m_arguments.size(); i--;) {
            FlushFormat format = FlushedJSValue;

            Node* node = m_argumentMapping.get(m_graph.m_arguments[i]);
            
            RELEASE_ASSERT(node);
            format = node->stackAccessData()->format;
            
            m_graph.m_argumentFormats[i] = format;
            m_graph.m_arguments[i] = node; // Record the load that loads the arguments for the benefit of exit profiling.
        }
        
        m_graph.m_form = SSA;

        if (verbose) {
            dataLog("Graph after SSA transformation:\n");
            m_graph.dump();
        }

        return true;
    }

private:
    SSACalculator m_calculator;
    InsertionSet m_insertionSet;
    HashMap<VariableAccessData*, SSACalculator::Variable*> m_ssaVariableForVariable;
    HashMap<Node*, Node*> m_argumentMapping;
    HashSet<Node*> m_argumentGetters;
    Vector<VariableAccessData*> m_variableForSSAIndex;
};

bool performSSAConversion(Graph& graph)
{
    SamplingRegion samplingRegion("DFG SSA Conversion Phase");
    return runPhase<SSAConversionPhase>(graph);
}

} } // namespace JSC::DFG

#endif // ENABLE(DFG_JIT)
Commit	Line	Data
81345200	1	/*
ed1e77d3	2	* Copyright (C) 2013-2015 Apple Inc. All rights reserved.
81345200 A	3	*
	4	* Redistribution and use in source and binary forms, with or without
	5	* modification, are permitted provided that the following conditions
	6	* are met:
	7	* 1. Redistributions of source code must retain the above copyright
	8	* notice, this list of conditions and the following disclaimer.
	9	* 2. Redistributions in binary form must reproduce the above copyright
	10	* notice, this list of conditions and the following disclaimer in the
	11	* documentation and/or other materials provided with the distribution.
	12	*
	13	* THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
	14	* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	15	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
	16	* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
	17	* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
	18	* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
	19	* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
	20	* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
	21	* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
	22	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
	23	* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
	24	*/
	25
	26	#include "config.h"
	27	#include "DFGSSAConversionPhase.h"
	28
	29	#if ENABLE(DFG_JIT)
	30
	31	#include "DFGBasicBlockInlines.h"
	32	#include "DFGGraph.h"
	33	#include "DFGInsertionSet.h"
	34	#include "DFGPhase.h"
ed1e77d3 A	35	#include "DFGSSACalculator.h"
ed1e77d3 A	36	#include "DFGVariableAccessDataDump.h"
81345200 A	37	#include "JSCInlines.h"
	38
	39	namespace JSC { namespace DFG {
	40
	41	class SSAConversionPhase : public Phase {
	42	static const bool verbose = false;
81345200 A	43
	44	public:
	45	SSAConversionPhase(Graph& graph)
	46	: Phase(graph, "SSA conversion")
ed1e77d3	47	, m_calculator(graph)
81345200	48	, m_insertionSet(graph)
81345200 A	49	{
	50	}
	51
	52	bool run()
	53	{
	54	RELEASE_ASSERT(m_graph.m_form == ThreadedCPS);
	55
ed1e77d3 A	56	m_graph.clearReplacements();
	57	m_graph.m_dominators.computeIfNecessary(m_graph);
	58
	59	if (verbose) {
	60	dataLog("Graph before SSA transformation:\n");
81345200 A	61	m_graph.dump();
81345200 A	62	}
ed1e77d3 A	63
	64	// Create a SSACalculator::Variable for every root VariableAccessData.
	65	for (VariableAccessData& variable : m_graph.m_variableAccessData) {
	66	if (!variable.isRoot())
	67	continue;
	68
	69	SSACalculator::Variable* ssaVariable = m_calculator.newVariable();
	70	ASSERT(ssaVariable->index() == m_variableForSSAIndex.size());
	71	m_variableForSSAIndex.append(&variable);
	72	m_ssaVariableForVariable.add(&variable, ssaVariable);
	73	}
81345200	74
ed1e77d3 A	75	// Find all SetLocals and create Defs for them. We handle SetArgument by creating a
ed1e77d3 A	76	// GetLocal, and recording the flush format.
81345200 A	77	for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
	78	BasicBlock* block = m_graph.block(blockIndex);
	79	if (!block)
	80	continue;
ed1e77d3 A	81
	82	// Must process the block in forward direction because we want to see the last
	83	// assignment for every local.
	84	for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
	85	Node* node = block->at(nodeIndex);
	86	if (node->op() != SetLocal && node->op() != SetArgument)
81345200 A	87	continue;
81345200 A	88
81345200	89	VariableAccessData* variable = node->variableAccessData();
81345200	90
ed1e77d3 A	91	Node* childNode;
	92	if (node->op() == SetLocal)
	93	childNode = node->child1().node();
	94	else {
	95	ASSERT(node->op() == SetArgument);
	96	childNode = m_insertionSet.insertNode(
	97	nodeIndex, node->variableAccessData()->prediction(),
	98	GetStack, node->origin,
	99	OpInfo(m_graph.m_stackAccessData.add(variable->local(), variable->flushFormat())));
	100	if (!ASSERT_DISABLED)
	101	m_argumentGetters.add(childNode);
	102	m_argumentMapping.add(node, childNode);
81345200 A	103	}
81345200 A	104
ed1e77d3 A	105	m_calculator.newDef(
ed1e77d3 A	106	m_ssaVariableForVariable.get(variable), block, childNode);
81345200	107	}
ed1e77d3	108
81345200 A	109	m_insertionSet.execute(block);
	110	}
	111
ed1e77d3 A	112	// Decide where Phis are to be inserted. This creates the Phi's but doesn't insert them
	113	// yet. We will later know where to insert them because SSACalculator is such a bro.
	114	m_calculator.computePhis(
	115	[&] (SSACalculator::Variable* ssaVariable, BasicBlock* block) -> Node* {
	116	VariableAccessData* variable = m_variableForSSAIndex[ssaVariable->index()];
	117
	118	// Prune by liveness. This doesn't buy us much other than compile times.
	119	Node* headNode = block->variablesAtHead.operand(variable->local());
	120	if (!headNode)
	121	return nullptr;
	122
	123	// There is the possibiltiy of "rebirths". The SSA calculator will already prune
	124	// rebirths for the same VariableAccessData. But it will not be able to prune
	125	// rebirths that arose from the same local variable number but a different
	126	// VariableAccessData. We do that pruning here.
	127	//
	128	// Here's an example of a rebirth that this would catch:
	129	//
	130	// var x;
	131	// if (foo) {
	132	// if (bar) {
	133	// x = 42;
	134	// } else {
	135	// x = 43;
	136	// }
	137	// print(x);
	138	// x = 44;
	139	// } else {
	140	// x = 45;
	141	// }
	142	// print(x); // Without this check, we'd have a Phi for x = 42\|43 here.
	143	//
	144	// FIXME: Consider feeding local variable numbers, not VariableAccessData*'s, as
	145	// the "variables" for SSACalculator. That would allow us to eliminate this
	146	// special case.
	147	// https://bugs.webkit.org/show_bug.cgi?id=136641
	148	if (headNode->variableAccessData() != variable)
	149	return nullptr;
	150
	151	Node* phiNode = m_graph.addNode(
	152	variable->prediction(), Phi, NodeOrigin());
	153	FlushFormat format = variable->flushFormat();
	154	NodeFlags result = resultFor(format);
	155	phiNode->mergeFlags(result);
	156	return phiNode;
	157	});
	158
81345200	159	if (verbose) {
ed1e77d3 A	160	dataLog("Computed Phis, about to transform the graph.\n");
	161	dataLog("\n");
	162	dataLog("Graph:\n");
	163	m_graph.dump();
	164	dataLog("\n");
	165	dataLog("Mappings:\n");
	166	for (unsigned i = 0; i < m_variableForSSAIndex.size(); ++i)
	167	dataLog(" ", i, ": ", VariableAccessDataDump(m_graph, m_variableForSSAIndex[i]), "\n");
	168	dataLog("\n");
	169	dataLog("SSA calculator: ", m_calculator, "\n");
81345200 A	170	}
81345200 A	171
ed1e77d3 A	172	// Do the bulk of the SSA conversion. For each block, this tracks the operand->Node
	173	// mapping based on a combination of what the SSACalculator tells us, and us walking over
	174	// the block in forward order. We use our own data structure, valueForOperand, for
	175	// determining the local mapping, but we rely on SSACalculator for the non-local mapping.
81345200	176	//
ed1e77d3	177	// This does three things at once:
81345200	178	//
ed1e77d3 A	179	// - Inserts the Phis in all of the places where they need to go. We've already created
	180	// them and they are accounted for in the SSACalculator's data structures, but we
	181	// haven't inserted them yet, mostly because we want to insert all of a block's Phis in
	182	// one go to amortize the cost of node insertion.
	183	//
	184	// - Create and insert Upsilons.
	185	//
	186	// - Convert all of the preexisting SSA nodes (other than the old CPS Phi nodes) into SSA
	187	// form by replacing as follows:
	188	//
	189	// - MovHint has KillLocal prepended to it.
	190	//
	191	// - GetLocal die and get replaced with references to the node specified by
	192	// valueForOperand.
	193	//
	194	// - SetLocal turns into PutStack if it's flushed, or turns into a Check otherwise.
	195	//
	196	// - Flush loses its children and turns into a Phantom.
	197	//
	198	// - PhantomLocal becomes Phantom, and its child is whatever is specified by
	199	// valueForOperand.
	200	//
	201	// - SetArgument is removed. Note that GetStack nodes have already been inserted.
	202	Operands<Node*> valueForOperand(OperandsLike, m_graph.block(0)->variablesAtHead);
	203	for (BasicBlock* block : m_graph.blocksInPreOrder()) {
	204	valueForOperand.clear();
	205
	206	// CPS will claim that the root block has all arguments live. But we have already done
	207	// the first step of SSA conversion: argument locals are no longer live at head;
	208	// instead we have GetStack nodes for extracting the values of arguments. So, we
	209	// skip the at-head available value calculation for the root block.
	210	if (block != m_graph.block(0)) {
	211	for (size_t i = valueForOperand.size(); i--;) {
	212	Node* nodeAtHead = block->variablesAtHead[i];
	213	if (!nodeAtHead)
	214	continue;
	215
	216	VariableAccessData* variable = nodeAtHead->variableAccessData();
	217
	218	if (verbose)
	219	dataLog("Considering live variable ", VariableAccessDataDump(m_graph, variable), " at head of block ", *block, "\n");
	220
	221	SSACalculator::Variable* ssaVariable = m_ssaVariableForVariable.get(variable);
	222	SSACalculator::Def* def = m_calculator.reachingDefAtHead(block, ssaVariable);
	223	if (!def) {
	224	// If we are required to insert a Phi, then we won't have a reaching def
	225	// at head.
	226	continue;
	227	}
	228
	229	Node* node = def->value();
	230	if (node->replacement()) {
	231	// This will occur when a SetLocal had a GetLocal as its source. The
	232	// GetLocal would get replaced with an actual SSA value by the time we get
	233	// here. Note that the SSA value with which the GetLocal got replaced
	234	// would not in turn have a replacement.
	235	node = node->replacement();
	236	ASSERT(!node->replacement());
	237	}
	238	if (verbose)
	239	dataLog("Mapping: ", VirtualRegister(valueForOperand.operandForIndex(i)), " -> ", node, "\n");
	240	valueForOperand[i] = node;
81345200	241	}
81345200	242	}
81345200	243
ed1e77d3 A	244	// Insert Phis by asking the calculator what phis there are in this block. Also update
	245	// valueForOperand with those Phis. For Phis associated with variables that are not
	246	// flushed, we also insert a MovHint.
	247	size_t phiInsertionPoint = 0;
	248	for (SSACalculator::Def* phiDef : m_calculator.phisForBlock(block)) {
	249	VariableAccessData* variable = m_variableForSSAIndex[phiDef->variable()->index()];
	250
	251	m_insertionSet.insert(phiInsertionPoint, phiDef->value());
	252	valueForOperand.operand(variable->local()) = phiDef->value();
	253
	254	m_insertionSet.insertNode(
	255	phiInsertionPoint, SpecNone, MovHint, NodeOrigin(),
	256	OpInfo(variable->local().offset()), phiDef->value()->defaultEdge());
81345200	257	}
81345200 A	258
	259	for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
	260	Node* node = block->at(nodeIndex);
	261
ed1e77d3 A	262	if (verbose) {
	263	dataLog("Processing node ", node, ":\n");
	264	m_graph.dump(WTF::dataFile(), " ", node);
	265	}
	266
81345200 A	267	m_graph.performSubstitution(node);
	268
	269	switch (node->op()) {
ed1e77d3 A	270	case MovHint: {
	271	m_insertionSet.insertNode(
	272	nodeIndex, SpecNone, KillStack, node->origin,
	273	OpInfo(node->unlinkedLocal().offset()));
	274	break;
	275	}
	276
81345200 A	277	case SetLocal: {
81345200 A	278	VariableAccessData* variable = node->variableAccessData();
ed1e77d3 A	279	Node* child = node->child1().node();
	280
	281	if (!!(node->flags() & NodeIsFlushed)) {
	282	node->convertToPutStack(
	283	m_graph.m_stackAccessData.add(
	284	variable->local(), variable->flushFormat()));
	285	} else
	286	node->remove();
	287
	288	if (verbose)
	289	dataLog("Mapping: ", variable->local(), " -> ", child, "\n");
	290	valueForOperand.operand(variable->local()) = child;
	291	break;
	292	}
	293
	294	case GetStack: {
	295	ASSERT(m_argumentGetters.contains(node));
	296	valueForOperand.operand(node->stackAccessData()->local) = node;
81345200 A	297	break;
	298	}
	299
	300	case GetLocal: {
81345200	301	VariableAccessData* variable = node->variableAccessData();
ed1e77d3 A	302	node->children.reset();
	303
	304	node->remove();
	305	if (verbose)
	306	dataLog("Replacing node ", node, " with ", valueForOperand.operand(variable->local()), "\n");
	307	node->setReplacement(valueForOperand.operand(variable->local()));
81345200 A	308	break;
	309	}
	310
	311	case Flush: {
	312	node->children.reset();
ed1e77d3	313	node->remove();
81345200 A	314	break;
	315	}
	316
	317	case PhantomLocal: {
	318	ASSERT(node->child1().useKind() == UntypedUse);
	319	VariableAccessData* variable = node->variableAccessData();
ed1e77d3 A	320	node->child1() = valueForOperand.operand(variable->local())->defaultEdge();
ed1e77d3 A	321	node->remove();
81345200 A	322	break;
	323	}
	324
	325	case SetArgument: {
ed1e77d3	326	node->remove();
81345200 A	327	break;
81345200 A	328	}
ed1e77d3	329
81345200 A	330	default:
	331	break;
	332	}
	333	}
ed1e77d3 A	334
	335	// We want to insert Upsilons just before the end of the block. On the surface this
	336	// seems dangerous because the Upsilon will have a checking UseKind. But, we will not
	337	// actually be performing the check at the point of the Upsilon; the check will
	338	// already have been performed at the point where the original SetLocal was.
	339	NodeAndIndex terminal = block->findTerminal();
	340	size_t upsilonInsertionPoint = terminal.index;
	341	NodeOrigin upsilonOrigin = terminal.node->origin;
	342	for (unsigned successorIndex = block->numSuccessors(); successorIndex--;) {
	343	BasicBlock* successorBlock = block->successor(successorIndex);
	344	for (SSACalculator::Def* phiDef : m_calculator.phisForBlock(successorBlock)) {
	345	Node* phiNode = phiDef->value();
	346	SSACalculator::Variable* ssaVariable = phiDef->variable();
	347	VariableAccessData* variable = m_variableForSSAIndex[ssaVariable->index()];
	348	FlushFormat format = variable->flushFormat();
	349	UseKind useKind = useKindFor(format);
	350
	351	m_insertionSet.insertNode(
	352	upsilonInsertionPoint, SpecNone, Upsilon, upsilonOrigin,
	353	OpInfo(phiNode), Edge(
	354	valueForOperand.operand(variable->local()),
	355	useKind));
	356	}
	357	}
	358
	359	m_insertionSet.execute(block);
81345200 A	360	}
	361
	362	// Free all CPS phis and reset variables vectors.
	363	for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
	364	BasicBlock* block = m_graph.block(blockIndex);
	365	if (!block)
	366	continue;
	367	for (unsigned phiIndex = block->phis.size(); phiIndex--;)
	368	m_graph.m_allocator.free(block->phis[phiIndex]);
	369	block->phis.clear();
	370	block->variablesAtHead.clear();
	371	block->variablesAtTail.clear();
	372	block->valuesAtHead.clear();
	373	block->valuesAtHead.clear();
ed1e77d3	374	block->ssa = std::make_unique<BasicBlock::SSAData>(block);
81345200 A	375	}
81345200 A	376
ed1e77d3 A	377	m_graph.m_argumentFormats.resize(m_graph.m_arguments.size());
	378	for (unsigned i = m_graph.m_arguments.size(); i--;) {
	379	FlushFormat format = FlushedJSValue;
	380
	381	Node* node = m_argumentMapping.get(m_graph.m_arguments[i]);
	382
	383	RELEASE_ASSERT(node);
	384	format = node->stackAccessData()->format;
	385
	386	m_graph.m_argumentFormats[i] = format;
	387	m_graph.m_arguments[i] = node; // Record the load that loads the arguments for the benefit of exit profiling.
	388	}
81345200 A	389
81345200 A	390	m_graph.m_form = SSA;
81345200	391
ed1e77d3 A	392	if (verbose) {
	393	dataLog("Graph after SSA transformation:\n");
	394	m_graph.dump();
81345200	395	}
ed1e77d3	396
81345200 A	397	return true;
81345200 A	398	}
ed1e77d3 A	399
	400	private:
	401	SSACalculator m_calculator;
81345200	402	InsertionSet m_insertionSet;
ed1e77d3 A	403	HashMap<VariableAccessData, SSACalculator::Variable> m_ssaVariableForVariable;
	404	HashMap<Node, Node> m_argumentMapping;
	405	HashSet<Node*> m_argumentGetters;
	406	Vector<VariableAccessData*> m_variableForSSAIndex;
81345200 A	407	};
	408
	409	bool performSSAConversion(Graph& graph)
	410	{
	411	SamplingRegion samplingRegion("DFG SSA Conversion Phase");
	412	return runPhase<SSAConversionPhase>(graph);
	413	}
	414
	415	} } // namespace JSC::DFG
	416
	417	#endif // ENABLE(DFG_JIT)
	418