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
36namespace JSC { namespace DFG {
37
38class StackLayoutPhase : public Phase {
39    static const bool verbose = false;
40
41public:
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;
108            if (!inlineCallFrame->executable->usesArguments())
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
174            if (inlineCallFrame->executable->usesArguments()) {
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
263bool 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
273