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

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

#if ENABLE(DFG_JIT)

#include "DFGGraph.h"
#include "DFGPhase.h"
#include "DFGValueSource.h"
#include "JSCInlines.h"

namespace JSC { namespace DFG {

class StackLayoutPhase : public Phase {
    static const bool verbose = false;
    
public:
    StackLayoutPhase(Graph& graph)
        : Phase(graph, "stack layout")
    {
    }
    
    bool run()
    {
        SymbolTable* symbolTable = codeBlock()->symbolTable();

        // This enumerates the locals that we actually care about and packs them. So for example
        // if we use local 1, 3, 4, 5, 7, then we remap them: 1->0, 3->1, 4->2, 5->3, 7->4. We
        // treat a variable as being "used" if there exists an access to it (SetLocal, GetLocal,
        // Flush, PhantomLocal).
        
        BitVector usedLocals;
        
        // Collect those variables that are used from IR.
        bool hasGetLocalUnlinked = false;
        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);
                switch (node->op()) {
                case GetLocal:
                case SetLocal:
                case Flush:
                case PhantomLocal: {
                    VariableAccessData* variable = node->variableAccessData();
                    if (variable->local().isArgument())
                        break;
                    usedLocals.set(variable->local().toLocal());
                    break;
                }
                    
                case GetLocalUnlinked: {
                    VirtualRegister operand = node->unlinkedLocal();
                    if (operand.isArgument())
                        break;
                    usedLocals.set(operand.toLocal());
                    hasGetLocalUnlinked = true;
                    break;
                }
                    
                default:
                    break;
                }
            }
        }
        
        // Ensure that captured variables and captured inline arguments are pinned down.
        // They should have been because of flushes, except that the flushes can be optimized
        // away.
        if (symbolTable) {
            for (int i = symbolTable->captureStart(); i > symbolTable->captureEnd(); i--)
                usedLocals.set(VirtualRegister(i).toLocal());
        }
        if (codeBlock()->usesArguments()) {
            usedLocals.set(codeBlock()->argumentsRegister().toLocal());
            usedLocals.set(unmodifiedArgumentsRegister(codeBlock()->argumentsRegister()).toLocal());
        }
        if (codeBlock()->uncheckedActivationRegister().isValid())
            usedLocals.set(codeBlock()->activationRegister().toLocal());
        for (InlineCallFrameSet::iterator iter = m_graph.m_plan.inlineCallFrames->begin(); !!iter; ++iter) {
            InlineCallFrame* inlineCallFrame = *iter;
            if (!m_graph.usesArguments(inlineCallFrame))
                continue;
            
            VirtualRegister argumentsRegister = m_graph.argumentsRegisterFor(inlineCallFrame);
            usedLocals.set(argumentsRegister.toLocal());
            usedLocals.set(unmodifiedArgumentsRegister(argumentsRegister).toLocal());
            
            for (unsigned argument = inlineCallFrame->arguments.size(); argument-- > 1;) {
                usedLocals.set(VirtualRegister(
                    virtualRegisterForArgument(argument).offset() +
                    inlineCallFrame->stackOffset).toLocal());
            }
        }
        
        Vector<unsigned> allocation(usedLocals.size());
        m_graph.m_nextMachineLocal = 0;
        for (unsigned i = 0; i < usedLocals.size(); ++i) {
            if (!usedLocals.get(i)) {
                allocation[i] = UINT_MAX;
                continue;
            }
            
            allocation[i] = m_graph.m_nextMachineLocal++;
        }
        
        for (unsigned i = m_graph.m_variableAccessData.size(); i--;) {
            VariableAccessData* variable = &m_graph.m_variableAccessData[i];
            if (!variable->isRoot())
                continue;
            
            if (variable->local().isArgument()) {
                variable->machineLocal() = variable->local();
                continue;
            }
            
            size_t local = variable->local().toLocal();
            if (local >= allocation.size())
                continue;
            
            if (allocation[local] == UINT_MAX)
                continue;
            
            variable->machineLocal() = virtualRegisterForLocal(
                allocation[variable->local().toLocal()]);
        }
        
        if (codeBlock()->usesArguments()) {
            VirtualRegister argumentsRegister = virtualRegisterForLocal(
                allocation[codeBlock()->argumentsRegister().toLocal()]);
            RELEASE_ASSERT(
                virtualRegisterForLocal(allocation[
                    unmodifiedArgumentsRegister(
                        codeBlock()->argumentsRegister()).toLocal()])
                == unmodifiedArgumentsRegister(argumentsRegister));
            codeBlock()->setArgumentsRegister(argumentsRegister);
        }
        
        if (codeBlock()->uncheckedActivationRegister().isValid()) {
            codeBlock()->setActivationRegister(
                virtualRegisterForLocal(allocation[codeBlock()->activationRegister().toLocal()]));
        }
        
        for (unsigned i = m_graph.m_inlineVariableData.size(); i--;) {
            InlineVariableData data = m_graph.m_inlineVariableData[i];
            InlineCallFrame* inlineCallFrame = data.inlineCallFrame;
            
            if (m_graph.usesArguments(inlineCallFrame)) {
                inlineCallFrame->argumentsRegister = virtualRegisterForLocal(
                    allocation[m_graph.argumentsRegisterFor(inlineCallFrame).toLocal()]);

                RELEASE_ASSERT(
                    virtualRegisterForLocal(allocation[unmodifiedArgumentsRegister(
                        m_graph.argumentsRegisterFor(inlineCallFrame)).toLocal()])
                    == unmodifiedArgumentsRegister(inlineCallFrame->argumentsRegister));
            }
            
            for (unsigned argument = inlineCallFrame->arguments.size(); argument-- > 1;) {
                ArgumentPosition& position = m_graph.m_argumentPositions[
                    data.argumentPositionStart + argument];
                VariableAccessData* variable = position.someVariable();
                ValueSource source;
                if (!variable)
                    source = ValueSource(SourceIsDead);
                else {
                    source = ValueSource::forFlushFormat(
                        variable->machineLocal(), variable->flushFormat());
                }
                inlineCallFrame->arguments[argument] = source.valueRecovery();
            }
            
            RELEASE_ASSERT(inlineCallFrame->isClosureCall == !!data.calleeVariable);
            if (inlineCallFrame->isClosureCall) {
                VariableAccessData* variable = data.calleeVariable->find();
                ValueSource source = ValueSource::forFlushFormat(
                    variable->machineLocal(),
                    variable->flushFormat());
                inlineCallFrame->calleeRecovery = source.valueRecovery();
            } else
                RELEASE_ASSERT(inlineCallFrame->calleeRecovery.isConstant());
        }
        
        if (symbolTable) {
            if (symbolTable->captureCount()) {
                unsigned captureStartLocal = allocation[
                    VirtualRegister(codeBlock()->symbolTable()->captureStart()).toLocal()];
                ASSERT(captureStartLocal != UINT_MAX);
                m_graph.m_machineCaptureStart = virtualRegisterForLocal(captureStartLocal).offset();
            } else
                m_graph.m_machineCaptureStart = virtualRegisterForLocal(0).offset();
        
            // This is an abomination. If we had captured an argument then the argument ends
            // up being "slow", meaning that loads of the argument go through an extra lookup
            // table.
            if (const SlowArgument* slowArguments = symbolTable->slowArguments()) {
                auto newSlowArguments = std::make_unique<SlowArgument[]>(
                    symbolTable->parameterCount());
                for (size_t i = symbolTable->parameterCount(); i--;) {
                    newSlowArguments[i] = slowArguments[i];
                    VirtualRegister reg = VirtualRegister(slowArguments[i].index);
                    if (reg.isLocal())
                        newSlowArguments[i].index = virtualRegisterForLocal(allocation[reg.toLocal()]).offset();
                }
            
                m_graph.m_slowArguments = WTF::move(newSlowArguments);
            }
        }
        
        // Fix GetLocalUnlinked's variable references.
        if (hasGetLocalUnlinked) {
            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);
                    switch (node->op()) {
                    case GetLocalUnlinked: {
                        VirtualRegister operand = node->unlinkedLocal();
                        if (operand.isLocal())
                            operand = virtualRegisterForLocal(allocation[operand.toLocal()]);
                        node->setUnlinkedMachineLocal(operand);
                        break;
                    }
                        
                    default:
                        break;
                    }
                }
            }
        }
        
        return true;
    }
};

bool performStackLayout(Graph& graph)
{
    SamplingRegion samplingRegion("DFG Stack Layout Phase");
    return runPhase<StackLayoutPhase>(graph);
}

} } // namespace JSC::DFG

#endif // ENABLE(DFG_JIT)
Commit	Line	Data
81345200 A	1	/*
	2	* Copyright (C) 2013 Apple Inc. All rights reserved.
	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 "DFGStackLayoutPhase.h"
	28
	29	#if ENABLE(DFG_JIT)
	30
	31	#include "DFGGraph.h"
	32	#include "DFGPhase.h"
	33	#include "DFGValueSource.h"
	34	#include "JSCInlines.h"
	35
	36	namespace JSC { namespace DFG {
	37
	38	class StackLayoutPhase : public Phase {
	39	static const bool verbose = false;
	40
	41	public:
	42	StackLayoutPhase(Graph& graph)
	43	: Phase(graph, "stack layout")
	44	{
	45	}
	46
	47	bool run()
	48	{
	49	SymbolTable* symbolTable = codeBlock()->symbolTable();
	50
	51	// This enumerates the locals that we actually care about and packs them. So for example
	52	// if we use local 1, 3, 4, 5, 7, then we remap them: 1->0, 3->1, 4->2, 5->3, 7->4. We
	53	// treat a variable as being "used" if there exists an access to it (SetLocal, GetLocal,
	54	// Flush, PhantomLocal).
	55
	56	BitVector usedLocals;
	57
	58	// Collect those variables that are used from IR.
	59	bool hasGetLocalUnlinked = false;
	60	for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
	61	BasicBlock* block = m_graph.block(blockIndex);
	62	if (!block)
	63	continue;
	64	for (unsigned nodeIndex = block->size(); nodeIndex--;) {
65	Node* node = block->at(nodeIndex);
66	switch (node->op()) {
67	case GetLocal:
68	case SetLocal:
69	case Flush:
70	case PhantomLocal: {
71	VariableAccessData* variable = node->variableAccessData();
72	if (variable->local().isArgument())
73	break;
74	usedLocals.set(variable->local().toLocal());
75	break;
76	}
77
78	case GetLocalUnlinked: {
79	VirtualRegister operand = node->unlinkedLocal();
80	if (operand.isArgument())
81	break;
82	usedLocals.set(operand.toLocal());
83	hasGetLocalUnlinked = true;
84	break;
85	}
86
87	default:
88	break;
89	}
90	}
91	}
92
93	// Ensure that captured variables and captured inline arguments are pinned down.
94	// They should have been because of flushes, except that the flushes can be optimized
95	// away.
96	if (symbolTable) {
97	for (int i = symbolTable->captureStart(); i > symbolTable->captureEnd(); i--)
98	usedLocals.set(VirtualRegister(i).toLocal());
99	}
100	if (codeBlock()->usesArguments()) {
101	usedLocals.set(codeBlock()->argumentsRegister().toLocal());
102	usedLocals.set(unmodifiedArgumentsRegister(codeBlock()->argumentsRegister()).toLocal());
103	}
104	if (codeBlock()->uncheckedActivationRegister().isValid())
105	usedLocals.set(codeBlock()->activationRegister().toLocal());
106	for (InlineCallFrameSet::iterator iter = m_graph.m_plan.inlineCallFrames->begin(); !!iter; ++iter) {
107	InlineCallFrame* inlineCallFrame = *iter;
40a37d08	108	if (!m_graph.usesArguments(inlineCallFrame))
81345200 A	109	continue;
	110
	111	VirtualRegister argumentsRegister = m_graph.argumentsRegisterFor(inlineCallFrame);
	112	usedLocals.set(argumentsRegister.toLocal());
	113	usedLocals.set(unmodifiedArgumentsRegister(argumentsRegister).toLocal());
	114
	115	for (unsigned argument = inlineCallFrame->arguments.size(); argument-- > 1;) {
	116	usedLocals.set(VirtualRegister(
	117	virtualRegisterForArgument(argument).offset() +
	118	inlineCallFrame->stackOffset).toLocal());
	119	}
	120	}
	121
	122	Vector<unsigned> allocation(usedLocals.size());
	123	m_graph.m_nextMachineLocal = 0;
	124	for (unsigned i = 0; i < usedLocals.size(); ++i) {
	125	if (!usedLocals.get(i)) {
	126	allocation[i] = UINT_MAX;
	127	continue;
	128	}
	129
	130	allocation[i] = m_graph.m_nextMachineLocal++;
	131	}
	132
	133	for (unsigned i = m_graph.m_variableAccessData.size(); i--;) {
	134	VariableAccessData* variable = &m_graph.m_variableAccessData[i];
	135	if (!variable->isRoot())
	136	continue;
	137
	138	if (variable->local().isArgument()) {
	139	variable->machineLocal() = variable->local();
	140	continue;
	141	}
	142
	143	size_t local = variable->local().toLocal();
	144	if (local >= allocation.size())
	145	continue;
	146
	147	if (allocation[local] == UINT_MAX)
	148	continue;
	149
	150	variable->machineLocal() = virtualRegisterForLocal(
	151	allocation[variable->local().toLocal()]);
	152	}
	153
	154	if (codeBlock()->usesArguments()) {
	155	VirtualRegister argumentsRegister = virtualRegisterForLocal(
	156	allocation[codeBlock()->argumentsRegister().toLocal()]);
	157	RELEASE_ASSERT(
	158	virtualRegisterForLocal(allocation[
	159	unmodifiedArgumentsRegister(
	160	codeBlock()->argumentsRegister()).toLocal()])
	161	== unmodifiedArgumentsRegister(argumentsRegister));
	162	codeBlock()->setArgumentsRegister(argumentsRegister);
	163	}
	164
	165	if (codeBlock()->uncheckedActivationRegister().isValid()) {
	166	codeBlock()->setActivationRegister(
	167	virtualRegisterForLocal(allocation[codeBlock()->activationRegister().toLocal()]));
	168	}
	169
	170	for (unsigned i = m_graph.m_inlineVariableData.size(); i--;) {
	171	InlineVariableData data = m_graph.m_inlineVariableData[i];
	172	InlineCallFrame* inlineCallFrame = data.inlineCallFrame;
173
40a37d08	174	if (m_graph.usesArguments(inlineCallFrame)) {
81345200 A	175	inlineCallFrame->argumentsRegister = virtualRegisterForLocal(
	176	allocation[m_graph.argumentsRegisterFor(inlineCallFrame).toLocal()]);
	177
	178	RELEASE_ASSERT(
	179	virtualRegisterForLocal(allocation[unmodifiedArgumentsRegister(
	180	m_graph.argumentsRegisterFor(inlineCallFrame)).toLocal()])
	181	== unmodifiedArgumentsRegister(inlineCallFrame->argumentsRegister));
	182	}
	183
	184	for (unsigned argument = inlineCallFrame->arguments.size(); argument-- > 1;) {
	185	ArgumentPosition& position = m_graph.m_argumentPositions[
	186	data.argumentPositionStart + argument];
	187	VariableAccessData* variable = position.someVariable();
	188	ValueSource source;
	189	if (!variable)
	190	source = ValueSource(SourceIsDead);
	191	else {
	192	source = ValueSource::forFlushFormat(
	193	variable->machineLocal(), variable->flushFormat());
	194	}
	195	inlineCallFrame->arguments[argument] = source.valueRecovery();
	196	}
	197
	198	RELEASE_ASSERT(inlineCallFrame->isClosureCall == !!data.calleeVariable);
	199	if (inlineCallFrame->isClosureCall) {
	200	VariableAccessData* variable = data.calleeVariable->find();
	201	ValueSource source = ValueSource::forFlushFormat(
	202	variable->machineLocal(),
	203	variable->flushFormat());
	204	inlineCallFrame->calleeRecovery = source.valueRecovery();
	205	} else
	206	RELEASE_ASSERT(inlineCallFrame->calleeRecovery.isConstant());
	207	}
	208
	209	if (symbolTable) {
	210	if (symbolTable->captureCount()) {
	211	unsigned captureStartLocal = allocation[
	212	VirtualRegister(codeBlock()->symbolTable()->captureStart()).toLocal()];
	213	ASSERT(captureStartLocal != UINT_MAX);
	214	m_graph.m_machineCaptureStart = virtualRegisterForLocal(captureStartLocal).offset();
	215	} else
	216	m_graph.m_machineCaptureStart = virtualRegisterForLocal(0).offset();
	217
	218	// This is an abomination. If we had captured an argument then the argument ends
	219	// up being "slow", meaning that loads of the argument go through an extra lookup
	220	// table.
	221	if (const SlowArgument* slowArguments = symbolTable->slowArguments()) {
	222	auto newSlowArguments = std::make_unique<SlowArgument[]>(
	223	symbolTable->parameterCount());
	224	for (size_t i = symbolTable->parameterCount(); i--;) {
	225	newSlowArguments[i] = slowArguments[i];
	226	VirtualRegister reg = VirtualRegister(slowArguments[i].index);
	227	if (reg.isLocal())
	228	newSlowArguments[i].index = virtualRegisterForLocal(allocation[reg.toLocal()]).offset();
	229	}
	230
	231	m_graph.m_slowArguments = WTF::move(newSlowArguments);
	232	}
	233	}
	234
	235	// Fix GetLocalUnlinked's variable references.
	236	if (hasGetLocalUnlinked) {
	237	for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
	238	BasicBlock* block = m_graph.block(blockIndex);
239	if (!block)
240	continue;
241	for (unsigned nodeIndex = block->size(); nodeIndex--;) {
242	Node* node = block->at(nodeIndex);
243	switch (node->op()) {
244	case GetLocalUnlinked: {
245	VirtualRegister operand = node->unlinkedLocal();
246	if (operand.isLocal())
247	operand = virtualRegisterForLocal(allocation[operand.toLocal()]);
248	node->setUnlinkedMachineLocal(operand);
249	break;
250	}
251
252	default:
253	break;
254	}
255	}
256	}
257	}
258
259	return true;
260	}
261	};
262
263	bool performStackLayout(Graph& graph)
264	{
265	SamplingRegion samplingRegion("DFG Stack Layout Phase");
266	return runPhase<StackLayoutPhase>(graph);
267	}
268
269	} } // namespace JSC::DFG
270
271	#endif // ENABLE(DFG_JIT)
272