1/*
2 * Copyright (C) 2016 Yusuke Suzuki <[email protected]>
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 "BytecodeGeneratorBaseInlines.h"
32#include "BytecodeLivenessAnalysisInlines.h"
33#include "BytecodeRewriter.h"
34#include "BytecodeStructs.h"
35#include "BytecodeUseDef.h"
36#include "IdentifierInlines.h"
37#include "InterpreterInlines.h"
38#include "JSCInlines.h"
39#include "JSCJSValueInlines.h"
40#include "JSGenerator.h"
41#include "Label.h"
42#include "StrongInlines.h"
43#include "UnlinkedCodeBlock.h"
44#include "UnlinkedMetadataTableInlines.h"
45#include <wtf/Optional.h>
46
47namespace JSC {
48
49struct YieldData {
50 InstructionStream::Offset point { 0 };
51 VirtualRegister argument { 0 };
52 FastBitVector liveness;
53};
54
55class BytecodeGeneratorification {
56public:
57 typedef Vector<YieldData> Yields;
58
59 struct GeneratorFrameData {
60 InstructionStream::Offset m_point;
61 VirtualRegister m_dst;
62 VirtualRegister m_scope;
63 VirtualRegister m_symbolTable;
64 VirtualRegister m_initialValue;
65 };
66
67 BytecodeGeneratorification(BytecodeGenerator& bytecodeGenerator, UnlinkedCodeBlock* codeBlock, InstructionStreamWriter& instructions, SymbolTable* generatorFrameSymbolTable, int generatorFrameSymbolTableIndex)
68 : m_bytecodeGenerator(bytecodeGenerator)
69 , m_codeBlock(codeBlock)
70 , m_instructions(instructions)
71 , m_graph(m_codeBlock, m_instructions)
72 , m_generatorFrameSymbolTable(codeBlock->vm(), generatorFrameSymbolTable)
73 , m_generatorFrameSymbolTableIndex(generatorFrameSymbolTableIndex)
74 {
75 for (BytecodeBasicBlock* block : m_graph) {
76 for (const auto offset : block->offsets()) {
77 const auto instruction = m_instructions.at(offset);
78 switch (instruction->opcodeID()) {
79 case op_enter: {
80 m_enterPoint = instruction.offset();
81 break;
82 }
83
84 case op_yield: {
85 auto bytecode = instruction->as<OpYield>();
86 unsigned liveCalleeLocalsIndex = bytecode.m_yieldPoint;
87 if (liveCalleeLocalsIndex >= m_yields.size())
88 m_yields.resize(liveCalleeLocalsIndex + 1);
89 YieldData& data = m_yields[liveCalleeLocalsIndex];
90 data.point = instruction.offset();
91 data.argument = bytecode.m_argument;
92 break;
93 }
94
95 case op_create_generator_frame_environment: {
96 auto bytecode = instruction->as<OpCreateGeneratorFrameEnvironment>();
97 GeneratorFrameData data;
98 data.m_point = instruction.offset();
99 data.m_dst = bytecode.m_dst;
100 data.m_scope = bytecode.m_scope;
101 data.m_symbolTable = bytecode.m_symbolTable;
102 data.m_initialValue = bytecode.m_initialValue;
103 m_generatorFrameData = WTFMove(data);
104 break;
105 }
106
107 default:
108 break;
109 }
110 }
111 }
112 }
113
114 struct Storage {
115 Identifier identifier;
116 unsigned identifierIndex;
117 ScopeOffset scopeOffset;
118 };
119
120 void run();
121
122 BytecodeGraph& graph() { return m_graph; }
123
124 const Yields& yields() const
125 {
126 return m_yields;
127 }
128
129 Yields& yields()
130 {
131 return m_yields;
132 }
133
134 InstructionStream::Ref enterPoint() const
135 {
136 return m_instructions.at(m_enterPoint);
137 }
138
139 Optional<GeneratorFrameData> generatorFrameData() const
140 {
141 return m_generatorFrameData;
142 }
143
144 const InstructionStream& instructions() const
145 {
146 return m_instructions;
147 }
148
149private:
150 Storage storageForGeneratorLocal(VM& vm, unsigned index)
151 {
152 // We assign a symbol to a register. There is one-on-one corresponding between a register and a symbol.
153 // By doing so, we allocate the specific storage to save the given register.
154 // This allow us not to save all the live registers even if the registers are not overwritten from the previous resuming time.
155 // It means that, the register can be retrieved even if the immediate previous op_save does not save it.
156
157 if (m_storages.size() <= index)
158 m_storages.resize(index + 1);
159 if (Optional<Storage> storage = m_storages[index])
160 return *storage;
161
162 Identifier identifier = Identifier::from(vm, index);
163 unsigned identifierIndex = m_codeBlock->numberOfIdentifiers();
164 m_codeBlock->addIdentifier(identifier);
165 ScopeOffset scopeOffset = m_generatorFrameSymbolTable->takeNextScopeOffset(NoLockingNecessary);
166 m_generatorFrameSymbolTable->set(NoLockingNecessary, identifier.impl(), SymbolTableEntry(VarOffset(scopeOffset)));
167
168 Storage storage = {
169 identifier,
170 identifierIndex,
171 scopeOffset
172 };
173 m_storages[index] = storage;
174 return storage;
175 }
176
177 BytecodeGenerator& m_bytecodeGenerator;
178 InstructionStream::Offset m_enterPoint;
179 Optional<GeneratorFrameData> m_generatorFrameData;
180 UnlinkedCodeBlock* m_codeBlock;
181 InstructionStreamWriter& m_instructions;
182 BytecodeGraph m_graph;
183 Vector<Optional<Storage>> m_storages;
184 Yields m_yields;
185 Strong<SymbolTable> m_generatorFrameSymbolTable;
186 int m_generatorFrameSymbolTableIndex;
187};
188
189class GeneratorLivenessAnalysis : public BytecodeLivenessPropagation {
190public:
191 GeneratorLivenessAnalysis(BytecodeGeneratorification& generatorification)
192 : m_generatorification(generatorification)
193 {
194 }
195
196 void run(UnlinkedCodeBlock* codeBlock, InstructionStreamWriter& instructions)
197 {
198 // Perform modified liveness analysis to determine which locals are live at the merge points.
199 // This produces the conservative results for the question, "which variables should be saved and resumed?".
200
201 runLivenessFixpoint(codeBlock, instructions, m_generatorification.graph());
202
203 for (YieldData& data : m_generatorification.yields())
204 data.liveness = getLivenessInfoAtBytecodeIndex(codeBlock, instructions, m_generatorification.graph(), BytecodeIndex(m_generatorification.instructions().at(data.point).next().offset()));
205 }
206
207private:
208 BytecodeGeneratorification& m_generatorification;
209};
210
211void BytecodeGeneratorification::run()
212{
213 // We calculate the liveness at each merge point. This gives us the information which registers should be saved and resumed conservatively.
214
215 VM& vm = m_bytecodeGenerator.vm();
216 {
217 GeneratorLivenessAnalysis pass(*this);
218 pass.run(m_codeBlock, m_instructions);
219 }
220
221 BytecodeRewriter rewriter(m_bytecodeGenerator, m_graph, m_codeBlock, m_instructions);
222
223 // Setup the global switch for the generator.
224 {
225 auto nextToEnterPoint = enterPoint().next();
226 unsigned switchTableIndex = m_codeBlock->numberOfSwitchJumpTables();
227 VirtualRegister state = virtualRegisterForArgument(static_cast<int32_t>(JSGenerator::GeneratorArgument::State));
228 auto& jumpTable = m_codeBlock->addSwitchJumpTable();
229 jumpTable.min = 0;
230 jumpTable.branchOffsets.resize(m_yields.size() + 1);
231 jumpTable.branchOffsets.fill(0);
232 jumpTable.add(0, nextToEnterPoint.offset());
233 for (unsigned i = 0; i < m_yields.size(); ++i)
234 jumpTable.add(i + 1, m_yields[i].point);
235
236 rewriter.insertFragmentBefore(nextToEnterPoint, [&] (BytecodeRewriter::Fragment& fragment) {
237 fragment.appendInstruction<OpSwitchImm>(switchTableIndex, BoundLabel(nextToEnterPoint.offset()), state);
238 });
239 }
240
241 for (const YieldData& data : m_yields) {
242 VirtualRegister scope = virtualRegisterForArgument(static_cast<int32_t>(JSGenerator::GeneratorArgument::Frame));
243
244 auto instruction = m_instructions.at(data.point);
245 // Emit save sequence.
246 rewriter.insertFragmentBefore(instruction, [&] (BytecodeRewriter::Fragment& fragment) {
247 data.liveness.forEachSetBit([&](size_t index) {
248 VirtualRegister operand = virtualRegisterForLocal(index);
249 Storage storage = storageForGeneratorLocal(vm, index);
250
251 fragment.appendInstruction<OpPutToScope>(
252 scope, // scope
253 storage.identifierIndex, // identifier
254 operand, // value
255 GetPutInfo(DoNotThrowIfNotFound, LocalClosureVar, InitializationMode::NotInitialization), // info
256 SymbolTableOrScopeDepth::symbolTable(VirtualRegister { m_generatorFrameSymbolTableIndex }), // symbol table constant index
257 storage.scopeOffset.offset() // scope offset
258 );
259 });
260
261 // Insert op_ret just after save sequence.
262 fragment.appendInstruction<OpRet>(data.argument);
263 });
264
265 // Emit resume sequence.
266 rewriter.insertFragmentAfter(instruction, [&] (BytecodeRewriter::Fragment& fragment) {
267 data.liveness.forEachSetBit([&](size_t index) {
268 VirtualRegister operand = virtualRegisterForLocal(index);
269 Storage storage = storageForGeneratorLocal(vm, index);
270
271 fragment.appendInstruction<OpGetFromScope>(
272 operand, // dst
273 scope, // scope
274 storage.identifierIndex, // identifier
275 GetPutInfo(DoNotThrowIfNotFound, LocalClosureVar, InitializationMode::NotInitialization), // info
276 0, // local scope depth
277 storage.scopeOffset.offset() // scope offset
278 );
279 });
280 });
281
282 // Clip the unnecessary bytecodes.
283 rewriter.removeBytecode(instruction);
284 }
285
286 if (m_generatorFrameData) {
287 auto instruction = m_instructions.at(m_generatorFrameData->m_point);
288 rewriter.insertFragmentAfter(instruction, [&] (BytecodeRewriter::Fragment& fragment) {
289 if (!m_generatorFrameSymbolTable->scopeSize()) {
290 // This will cause us to put jsUndefined() into the generator frame's scope value.
291 fragment.appendInstruction<OpMov>(m_generatorFrameData->m_dst, m_generatorFrameData->m_initialValue);
292 } else
293 fragment.appendInstruction<OpCreateLexicalEnvironment>(m_generatorFrameData->m_dst, m_generatorFrameData->m_scope, m_generatorFrameData->m_symbolTable, m_generatorFrameData->m_initialValue);
294 });
295 rewriter.removeBytecode(instruction);
296 }
297
298 rewriter.execute();
299}
300
301void performGeneratorification(BytecodeGenerator& bytecodeGenerator, UnlinkedCodeBlock* codeBlock, InstructionStreamWriter& instructions, SymbolTable* generatorFrameSymbolTable, int generatorFrameSymbolTableIndex)
302{
303 if (Options::dumpBytecodesBeforeGeneratorification())
304 CodeBlockBytecodeDumper<UnlinkedCodeBlock>::dumpBlock(codeBlock, instructions, WTF::dataFile());
305
306 BytecodeGeneratorification pass(bytecodeGenerator, codeBlock, instructions, generatorFrameSymbolTable, generatorFrameSymbolTableIndex);
307 pass.run();
308}
309
310} // namespace JSC
311