1/*
2 * Copyright (C) 2016 Yusuke Suzuki <utatane.tea@gmail.com>
3 * Copyright (C) 2016-2019 Apple Inc. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
15 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
16 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
18 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
19 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
20 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
21 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
22 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
23 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
24 * THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27#include "config.h"
28#include "BytecodeGeneratorification.h"
29
30#include "BytecodeDumper.h"
31#include "BytecodeLivenessAnalysisInlines.h"
32#include "BytecodeRewriter.h"
33#include "BytecodeStructs.h"
34#include "BytecodeUseDef.h"
35#include "IdentifierInlines.h"
36#include "InterpreterInlines.h"
37#include "JSCInlines.h"
38#include "JSCJSValueInlines.h"
39#include "JSGeneratorFunction.h"
40#include "Label.h"
41#include "StrongInlines.h"
42#include "UnlinkedCodeBlock.h"
43#include "UnlinkedMetadataTableInlines.h"
44#include <wtf/Optional.h>
45
46namespace JSC {
47
48struct YieldData {
49 InstructionStream::Offset point { 0 };
50 VirtualRegister argument { 0 };
51 FastBitVector liveness;
52};
53
54class BytecodeGeneratorification {
55public:
56 typedef Vector<YieldData> Yields;
57
58 struct GeneratorFrameData {
59 InstructionStream::Offset m_point;
60 VirtualRegister m_dst;
61 VirtualRegister m_scope;
62 VirtualRegister m_symbolTable;
63 VirtualRegister m_initialValue;
64 };
65
66 BytecodeGeneratorification(BytecodeGenerator& bytecodeGenerator, UnlinkedCodeBlock* codeBlock, InstructionStreamWriter& instructions, SymbolTable* generatorFrameSymbolTable, int generatorFrameSymbolTableIndex)
67 : m_bytecodeGenerator(bytecodeGenerator)
68 , m_codeBlock(codeBlock)
69 , m_instructions(instructions)
70 , m_graph(m_codeBlock, m_instructions)
71 , m_generatorFrameSymbolTable(*codeBlock->vm(), generatorFrameSymbolTable)
72 , m_generatorFrameSymbolTableIndex(generatorFrameSymbolTableIndex)
73 {
74 for (BytecodeBasicBlock* block : m_graph) {
75 for (const auto offset : block->offsets()) {
76 const auto instruction = m_instructions.at(offset);
77 switch (instruction->opcodeID()) {
78 case op_enter: {
79 m_enterPoint = instruction.offset();
80 break;
81 }
82
83 case op_yield: {
84 auto bytecode = instruction->as<OpYield>();
85 unsigned liveCalleeLocalsIndex = bytecode.m_yieldPoint;
86 if (liveCalleeLocalsIndex >= m_yields.size())
87 m_yields.resize(liveCalleeLocalsIndex + 1);
88 YieldData& data = m_yields[liveCalleeLocalsIndex];
89 data.point = instruction.offset();
90 data.argument = bytecode.m_argument;
91 break;
92 }
93
94 case op_create_generator_frame_environment: {
95 auto bytecode = instruction->as<OpCreateGeneratorFrameEnvironment>();
96 GeneratorFrameData data;
97 data.m_point = instruction.offset();
98 data.m_dst = bytecode.m_dst;
99 data.m_scope = bytecode.m_scope;
100 data.m_symbolTable = bytecode.m_symbolTable;
101 data.m_initialValue = bytecode.m_initialValue;
102 m_generatorFrameData = WTFMove(data);
103 break;
104 }
105
106 default:
107 break;
108 }
109 }
110 }
111 }
112
113 struct Storage {
114 Identifier identifier;
115 unsigned identifierIndex;
116 ScopeOffset scopeOffset;
117 };
118
119 void run();
120
121 BytecodeGraph& graph() { return m_graph; }
122
123 const Yields& yields() const
124 {
125 return m_yields;
126 }
127
128 Yields& yields()
129 {
130 return m_yields;
131 }
132
133 InstructionStream::Ref enterPoint() const
134 {
135 return m_instructions.at(m_enterPoint);
136 }
137
138 Optional<GeneratorFrameData> generatorFrameData() const
139 {
140 return m_generatorFrameData;
141 }
142
143 const InstructionStream& instructions() const
144 {
145 return m_instructions;
146 }
147
148private:
149 Storage storageForGeneratorLocal(VM& vm, unsigned index)
150 {
151 // We assign a symbol to a register. There is one-on-one corresponding between a register and a symbol.
152 // By doing so, we allocate the specific storage to save the given register.
153 // This allow us not to save all the live registers even if the registers are not overwritten from the previous resuming time.
154 // It means that, the register can be retrieved even if the immediate previous op_save does not save it.
155
156 if (m_storages.size() <= index)
157 m_storages.resize(index + 1);
158 if (Optional<Storage> storage = m_storages[index])
159 return *storage;
160
161 Identifier identifier = Identifier::from(&vm, index);
162 unsigned identifierIndex = m_codeBlock->numberOfIdentifiers();
163 m_codeBlock->addIdentifier(identifier);
164 ScopeOffset scopeOffset = m_generatorFrameSymbolTable->takeNextScopeOffset(NoLockingNecessary);
165 m_generatorFrameSymbolTable->set(NoLockingNecessary, identifier.impl(), SymbolTableEntry(VarOffset(scopeOffset)));
166
167 Storage storage = {
168 identifier,
169 identifierIndex,
170 scopeOffset
171 };
172 m_storages[index] = storage;
173 return storage;
174 }
175
176 BytecodeGenerator& m_bytecodeGenerator;
177 InstructionStream::Offset m_enterPoint;
178 Optional<GeneratorFrameData> m_generatorFrameData;
179 UnlinkedCodeBlock* m_codeBlock;
180 InstructionStreamWriter& m_instructions;
181 BytecodeGraph m_graph;
182 Vector<Optional<Storage>> m_storages;
183 Yields m_yields;
184 Strong<SymbolTable> m_generatorFrameSymbolTable;
185 int m_generatorFrameSymbolTableIndex;
186};
187
188class GeneratorLivenessAnalysis : public BytecodeLivenessPropagation {
189public:
190 GeneratorLivenessAnalysis(BytecodeGeneratorification& generatorification)
191 : m_generatorification(generatorification)
192 {
193 }
194
195 void run(UnlinkedCodeBlock* codeBlock, InstructionStreamWriter& instructions)
196 {
197 // Perform modified liveness analysis to determine which locals are live at the merge points.
198 // This produces the conservative results for the question, "which variables should be saved and resumed?".
199
200 runLivenessFixpoint(codeBlock, instructions, m_generatorification.graph());
201
202 for (YieldData& data : m_generatorification.yields())
203 data.liveness = getLivenessInfoAtBytecodeOffset(codeBlock, instructions, m_generatorification.graph(), m_generatorification.instructions().at(data.point).next().offset());
204 }
205
206private:
207 BytecodeGeneratorification& m_generatorification;
208};
209
210void BytecodeGeneratorification::run()
211{
212 // We calculate the liveness at each merge point. This gives us the information which registers should be saved and resumed conservatively.
213
214 VM& vm = *m_bytecodeGenerator.vm();
215 {
216 GeneratorLivenessAnalysis pass(*this);
217 pass.run(m_codeBlock, m_instructions);
218 }
219
220 BytecodeRewriter rewriter(m_bytecodeGenerator, m_graph, m_codeBlock, m_instructions);
221
222 // Setup the global switch for the generator.
223 {
224 auto nextToEnterPoint = enterPoint().next();
225 unsigned switchTableIndex = m_codeBlock->numberOfSwitchJumpTables();
226 VirtualRegister state = virtualRegisterForArgument(static_cast<int32_t>(JSGeneratorFunction::GeneratorArgument::State));
227 auto& jumpTable = m_codeBlock->addSwitchJumpTable();
228 jumpTable.min = 0;
229 jumpTable.branchOffsets.resize(m_yields.size() + 1);
230 jumpTable.branchOffsets.fill(0);
231 jumpTable.add(0, nextToEnterPoint.offset());
232 for (unsigned i = 0; i < m_yields.size(); ++i)
233 jumpTable.add(i + 1, m_yields[i].point);
234
235 rewriter.insertFragmentBefore(nextToEnterPoint, [&] (BytecodeRewriter::Fragment& fragment) {
236 fragment.appendInstruction<OpSwitchImm>(switchTableIndex, BoundLabel(nextToEnterPoint.offset()), state);
237 });
238 }
239
240 for (const YieldData& data : m_yields) {
241 VirtualRegister scope = virtualRegisterForArgument(static_cast<int32_t>(JSGeneratorFunction::GeneratorArgument::Frame));
242
243 auto instruction = m_instructions.at(data.point);
244 // Emit save sequence.
245 rewriter.insertFragmentBefore(instruction, [&] (BytecodeRewriter::Fragment& fragment) {
246 data.liveness.forEachSetBit([&](size_t index) {
247 VirtualRegister operand = virtualRegisterForLocal(index);
248 Storage storage = storageForGeneratorLocal(vm, index);
249
250 fragment.appendInstruction<OpPutToScope>(
251 scope, // scope
252 storage.identifierIndex, // identifier
253 operand, // value
254 GetPutInfo(DoNotThrowIfNotFound, LocalClosureVar, InitializationMode::NotInitialization), // info
255 SymbolTableOrScopeDepth::symbolTable(VirtualRegister { m_generatorFrameSymbolTableIndex }), // symbol table constant index
256 storage.scopeOffset.offset() // scope offset
257 );
258 });
259
260 // Insert op_ret just after save sequence.
261 fragment.appendInstruction<OpRet>(data.argument);
262 });
263
264 // Emit resume sequence.
265 rewriter.insertFragmentAfter(instruction, [&] (BytecodeRewriter::Fragment& fragment) {
266 data.liveness.forEachSetBit([&](size_t index) {
267 VirtualRegister operand = virtualRegisterForLocal(index);
268 Storage storage = storageForGeneratorLocal(vm, index);
269
270 fragment.appendInstruction<OpGetFromScope>(
271 operand, // dst
272 scope, // scope
273 storage.identifierIndex, // identifier
274 GetPutInfo(DoNotThrowIfNotFound, LocalClosureVar, InitializationMode::NotInitialization), // info
275 0, // local scope depth
276 storage.scopeOffset.offset() // scope offset
277 );
278 });
279 });
280
281 // Clip the unnecessary bytecodes.
282 rewriter.removeBytecode(instruction);
283 }
284
285 if (m_generatorFrameData) {
286 auto instruction = m_instructions.at(m_generatorFrameData->m_point);
287 rewriter.insertFragmentAfter(instruction, [&] (BytecodeRewriter::Fragment& fragment) {
288 if (!m_generatorFrameSymbolTable->scopeSize()) {
289 // This will cause us to put jsUndefined() into the generator frame's scope value.
290 fragment.appendInstruction<OpMov>(m_generatorFrameData->m_dst, m_generatorFrameData->m_initialValue);
291 } else
292 fragment.appendInstruction<OpCreateLexicalEnvironment>(m_generatorFrameData->m_dst, m_generatorFrameData->m_scope, m_generatorFrameData->m_symbolTable, m_generatorFrameData->m_initialValue);
293 });
294 rewriter.removeBytecode(instruction);
295 }
296
297 rewriter.execute();
298}
299
300void performGeneratorification(BytecodeGenerator& bytecodeGenerator, UnlinkedCodeBlock* codeBlock, InstructionStreamWriter& instructions, SymbolTable* generatorFrameSymbolTable, int generatorFrameSymbolTableIndex)
301{
302 if (Options::dumpBytecodesBeforeGeneratorification())
303 BytecodeDumper<UnlinkedCodeBlock>::dumpBlock(codeBlock, instructions, WTF::dataFile());
304
305 BytecodeGeneratorification pass(bytecodeGenerator, codeBlock, instructions, generatorFrameSymbolTable, generatorFrameSymbolTableIndex);
306 pass.run();
307}
308
309} // namespace JSC
310