[apple/javascriptcore.git] / dfg / DFGStackLayoutPhase.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 "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()
    {
        // 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 hasNodesThatNeedFixup = 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());
                    hasNodesThatNeedFixup = true;
                    break;
                }
                    
                case LoadVarargs:
                case ForwardVarargs: {
                    LoadVarargsData* data = node->loadVarargsData();
                    if (data->count.isLocal())
                        usedLocals.set(data->count.toLocal());
                    if (data->start.isLocal()) {
                        // This part really relies on the contiguity of stack layout
                        // assignments.
                        ASSERT(VirtualRegister(data->start.offset() + data->limit - 1).isLocal());
                        for (unsigned i = data->limit; i--;) 
                            usedLocals.set(VirtualRegister(data->start.offset() + i).toLocal());
                    } // the else case shouldn't happen.
                    hasNodesThatNeedFixup = true;
                    break;
                }
                    
                case PutStack:
                case GetStack: {
                    StackAccessData* stack = node->stackAccessData();
                    if (stack->local.isArgument())
                        break;
                    usedLocals.set(stack->local.toLocal());
                    break;
                }
                    
                default:
                    break;
                }
            }
        }
        
        for (InlineCallFrameSet::iterator iter = m_graph.m_plan.inlineCallFrames->begin(); !!iter; ++iter) {
            InlineCallFrame* inlineCallFrame = *iter;
            
            if (inlineCallFrame->isVarargs()) {
                usedLocals.set(VirtualRegister(
                    JSStack::ArgumentCount + inlineCallFrame->stackOffset).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() = assign(allocation, variable->local());
        }
        
        for (StackAccessData* data : m_graph.m_stackAccessData) {
            if (!data->local.isLocal()) {
                data->machineLocal = data->local;
                continue;
            }
            
            if (static_cast<size_t>(data->local.toLocal()) >= allocation.size())
                continue;
            if (allocation[data->local.toLocal()] == UINT_MAX)
                continue;
            
            data->machineLocal = assign(allocation, data->local);
        }
        
        // This register is never valid for DFG code blocks.
        codeBlock()->setActivationRegister(VirtualRegister());
        if (LIKELY(!m_graph.hasDebuggerEnabled()))
            codeBlock()->setScopeRegister(VirtualRegister());
        else
            codeBlock()->setScopeRegister(assign(allocation, codeBlock()->scopeRegister()));

        for (unsigned i = m_graph.m_inlineVariableData.size(); i--;) {
            InlineVariableData data = m_graph.m_inlineVariableData[i];
            InlineCallFrame* inlineCallFrame = data.inlineCallFrame;
            
            if (inlineCallFrame->isVarargs()) {
                inlineCallFrame->argumentCountRegister = assign(
                    allocation, VirtualRegister(inlineCallFrame->stackOffset + JSStack::ArgumentCount));
            }
            
            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());
        }
        
        // Fix GetLocalUnlinked's variable references.
        if (hasNodesThatNeedFixup) {
            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: {
                        node->setUnlinkedMachineLocal(assign(allocation, node->unlinkedLocal()));
                        break;
                    }
                        
                    case LoadVarargs:
                    case ForwardVarargs: {
                        LoadVarargsData* data = node->loadVarargsData();
                        data->machineCount = assign(allocation, data->count);
                        data->machineStart = assign(allocation, data->start);
                        break;
                    }
                        
                    default:
                        break;
                    }
                }
            }
        }
        
        return true;
    }

private:
    VirtualRegister assign(const Vector<unsigned>& allocation, VirtualRegister src)
    {
        VirtualRegister result = src;
        if (result.isLocal()) {
            unsigned myAllocation = allocation[result.toLocal()];
            if (myAllocation == UINT_MAX)
                result = VirtualRegister();
            else
                result = virtualRegisterForLocal(myAllocation);
        }
        return result;
    }
};

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	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 "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	{
81345200 A	49	// This enumerates the locals that we actually care about and packs them. So for example
	50	// if we use local 1, 3, 4, 5, 7, then we remap them: 1->0, 3->1, 4->2, 5->3, 7->4. We
	51	// treat a variable as being "used" if there exists an access to it (SetLocal, GetLocal,
	52	// Flush, PhantomLocal).
	53
	54	BitVector usedLocals;
	55
	56	// Collect those variables that are used from IR.
ed1e77d3	57	bool hasNodesThatNeedFixup = false;
81345200 A	58	for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
	59	BasicBlock* block = m_graph.block(blockIndex);
	60	if (!block)
	61	continue;
	62	for (unsigned nodeIndex = block->size(); nodeIndex--;) {
	63	Node* node = block->at(nodeIndex);
	64	switch (node->op()) {
	65	case GetLocal:
	66	case SetLocal:
	67	case Flush:
	68	case PhantomLocal: {
	69	VariableAccessData* variable = node->variableAccessData();
	70	if (variable->local().isArgument())
	71	break;
	72	usedLocals.set(variable->local().toLocal());
	73	break;
	74	}
	75
	76	case GetLocalUnlinked: {
	77	VirtualRegister operand = node->unlinkedLocal();
	78	if (operand.isArgument())
	79	break;
	80	usedLocals.set(operand.toLocal());
ed1e77d3 A	81	hasNodesThatNeedFixup = true;
	82	break;
	83	}
	84
	85	case LoadVarargs:
	86	case ForwardVarargs: {
	87	LoadVarargsData* data = node->loadVarargsData();
	88	if (data->count.isLocal())
	89	usedLocals.set(data->count.toLocal());
	90	if (data->start.isLocal()) {
	91	// This part really relies on the contiguity of stack layout
	92	// assignments.
	93	ASSERT(VirtualRegister(data->start.offset() + data->limit - 1).isLocal());
	94	for (unsigned i = data->limit; i--;)
	95	usedLocals.set(VirtualRegister(data->start.offset() + i).toLocal());
	96	} // the else case shouldn't happen.
	97	hasNodesThatNeedFixup = true;
	98	break;
	99	}
	100
	101	case PutStack:
	102	case GetStack: {
	103	StackAccessData* stack = node->stackAccessData();
	104	if (stack->local.isArgument())
	105	break;
	106	usedLocals.set(stack->local.toLocal());
81345200 A	107	break;
	108	}
	109
	110	default:
	111	break;
	112	}
	113	}
	114	}
	115
81345200 A	116	for (InlineCallFrameSet::iterator iter = m_graph.m_plan.inlineCallFrames->begin(); !!iter; ++iter) {
81345200 A	117	InlineCallFrame* inlineCallFrame = *iter;
81345200	118
ed1e77d3 A	119	if (inlineCallFrame->isVarargs()) {
	120	usedLocals.set(VirtualRegister(
	121	JSStack::ArgumentCount + inlineCallFrame->stackOffset).toLocal());
	122	}
81345200 A	123
	124	for (unsigned argument = inlineCallFrame->arguments.size(); argument-- > 1;) {
	125	usedLocals.set(VirtualRegister(
	126	virtualRegisterForArgument(argument).offset() +
	127	inlineCallFrame->stackOffset).toLocal());
	128	}
	129	}
	130
	131	Vector<unsigned> allocation(usedLocals.size());
	132	m_graph.m_nextMachineLocal = 0;
	133	for (unsigned i = 0; i < usedLocals.size(); ++i) {
	134	if (!usedLocals.get(i)) {
	135	allocation[i] = UINT_MAX;
	136	continue;
	137	}
	138
	139	allocation[i] = m_graph.m_nextMachineLocal++;
	140	}
	141
	142	for (unsigned i = m_graph.m_variableAccessData.size(); i--;) {
	143	VariableAccessData* variable = &m_graph.m_variableAccessData[i];
	144	if (!variable->isRoot())
	145	continue;
	146
	147	if (variable->local().isArgument()) {
	148	variable->machineLocal() = variable->local();
	149	continue;
	150	}
	151
	152	size_t local = variable->local().toLocal();
	153	if (local >= allocation.size())
	154	continue;
	155
	156	if (allocation[local] == UINT_MAX)
	157	continue;
	158
ed1e77d3	159	variable->machineLocal() = assign(allocation, variable->local());
81345200 A	160	}
81345200 A	161
ed1e77d3 A	162	for (StackAccessData* data : m_graph.m_stackAccessData) {
	163	if (!data->local.isLocal()) {
	164	data->machineLocal = data->local;
	165	continue;
	166	}
	167
	168	if (static_cast<size_t>(data->local.toLocal()) >= allocation.size())
	169	continue;
	170	if (allocation[data->local.toLocal()] == UINT_MAX)
	171	continue;
	172
	173	data->machineLocal = assign(allocation, data->local);
81345200 A	174	}
81345200 A	175
ed1e77d3 A	176	// This register is never valid for DFG code blocks.
	177	codeBlock()->setActivationRegister(VirtualRegister());
	178	if (LIKELY(!m_graph.hasDebuggerEnabled()))
	179	codeBlock()->setScopeRegister(VirtualRegister());
	180	else
	181	codeBlock()->setScopeRegister(assign(allocation, codeBlock()->scopeRegister()));
	182
81345200 A	183	for (unsigned i = m_graph.m_inlineVariableData.size(); i--;) {
	184	InlineVariableData data = m_graph.m_inlineVariableData[i];
	185	InlineCallFrame* inlineCallFrame = data.inlineCallFrame;
	186
ed1e77d3 A	187	if (inlineCallFrame->isVarargs()) {
	188	inlineCallFrame->argumentCountRegister = assign(
	189	allocation, VirtualRegister(inlineCallFrame->stackOffset + JSStack::ArgumentCount));
81345200 A	190	}
	191
	192	for (unsigned argument = inlineCallFrame->arguments.size(); argument-- > 1;) {
	193	ArgumentPosition& position = m_graph.m_argumentPositions[
	194	data.argumentPositionStart + argument];
	195	VariableAccessData* variable = position.someVariable();
	196	ValueSource source;
	197	if (!variable)
	198	source = ValueSource(SourceIsDead);
	199	else {
	200	source = ValueSource::forFlushFormat(
	201	variable->machineLocal(), variable->flushFormat());
	202	}
	203	inlineCallFrame->arguments[argument] = source.valueRecovery();
	204	}
	205
	206	RELEASE_ASSERT(inlineCallFrame->isClosureCall == !!data.calleeVariable);
	207	if (inlineCallFrame->isClosureCall) {
	208	VariableAccessData* variable = data.calleeVariable->find();
	209	ValueSource source = ValueSource::forFlushFormat(
	210	variable->machineLocal(),
	211	variable->flushFormat());
	212	inlineCallFrame->calleeRecovery = source.valueRecovery();
	213	} else
	214	RELEASE_ASSERT(inlineCallFrame->calleeRecovery.isConstant());
	215	}
	216
81345200	217	// Fix GetLocalUnlinked's variable references.
ed1e77d3	218	if (hasNodesThatNeedFixup) {
81345200 A	219	for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
	220	BasicBlock* block = m_graph.block(blockIndex);
	221	if (!block)
	222	continue;
	223	for (unsigned nodeIndex = block->size(); nodeIndex--;) {
	224	Node* node = block->at(nodeIndex);
	225	switch (node->op()) {
	226	case GetLocalUnlinked: {
ed1e77d3 A	227	node->setUnlinkedMachineLocal(assign(allocation, node->unlinkedLocal()));
	228	break;
	229	}
	230
	231	case LoadVarargs:
	232	case ForwardVarargs: {
	233	LoadVarargsData* data = node->loadVarargsData();
	234	data->machineCount = assign(allocation, data->count);
	235	data->machineStart = assign(allocation, data->start);
81345200 A	236	break;
	237	}
	238
	239	default:
	240	break;
	241	}
	242	}
	243	}
	244	}
	245
	246	return true;
	247	}
ed1e77d3 A	248
	249	private:
	250	VirtualRegister assign(const Vector<unsigned>& allocation, VirtualRegister src)
	251	{
	252	VirtualRegister result = src;
	253	if (result.isLocal()) {
	254	unsigned myAllocation = allocation[result.toLocal()];
	255	if (myAllocation == UINT_MAX)
	256	result = VirtualRegister();
	257	else
	258	result = virtualRegisterForLocal(myAllocation);
	259	}
	260	return result;
	261	}
81345200 A	262	};
	263
	264	bool performStackLayout(Graph& graph)
	265	{
	266	SamplingRegion samplingRegion("DFG Stack Layout Phase");
	267	return runPhase<StackLayoutPhase>(graph);
	268	}
	269
	270	} } // namespace JSC::DFG
	271
	272	#endif // ENABLE(DFG_JIT)
	273