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(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::fromUid(PrivateName());
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 {
215 GeneratorLivenessAnalysis pass(*this);
216 pass.run(m_codeBlock, m_instructions);
217 }
218
219 BytecodeRewriter rewriter(m_bytecodeGenerator, m_graph, m_codeBlock, m_instructions);
220
221 // Setup the global switch for the generator.
222 {
223 auto nextToEnterPoint = enterPoint().next();
224 unsigned switchTableIndex = m_codeBlock->numberOfSwitchJumpTables();
225 VirtualRegister state = virtualRegisterForArgument(static_cast<int32_t>(JSGeneratorFunction::GeneratorArgument::State));
226 auto& jumpTable = m_codeBlock->addSwitchJumpTable();
227 jumpTable.min = 0;
228 jumpTable.branchOffsets.resize(m_yields.size() + 1);
229 jumpTable.branchOffsets.fill(0);
230 jumpTable.add(0, nextToEnterPoint.offset());
231 for (unsigned i = 0; i < m_yields.size(); ++i)
232 jumpTable.add(i + 1, m_yields[i].point);
233
234 rewriter.insertFragmentBefore(nextToEnterPoint, [&] (BytecodeRewriter::Fragment& fragment) {
235 fragment.appendInstruction<OpSwitchImm>(switchTableIndex, BoundLabel(nextToEnterPoint.offset()), state);
236 });
237 }
238
239 for (const YieldData& data : m_yields) {
240 VirtualRegister scope = virtualRegisterForArgument(static_cast<int32_t>(JSGeneratorFunction::GeneratorArgument::Frame));
241
242 auto instruction = m_instructions.at(data.point);
243 // Emit save sequence.
244 rewriter.insertFragmentBefore(instruction, [&] (BytecodeRewriter::Fragment& fragment) {
245 data.liveness.forEachSetBit([&](size_t index) {
246 VirtualRegister operand = virtualRegisterForLocal(index);
247 Storage storage = storageForGeneratorLocal(index);
248
249 fragment.appendInstruction<OpPutToScope>(
250 scope, // scope
251 storage.identifierIndex, // identifier
252 operand, // value
253 GetPutInfo(DoNotThrowIfNotFound, LocalClosureVar, InitializationMode::NotInitialization), // info
254 m_generatorFrameSymbolTableIndex, // symbol table constant index
255 storage.scopeOffset.offset() // scope offset
256 );
257 });
258
259 // Insert op_ret just after save sequence.
260 fragment.appendInstruction<OpRet>(data.argument);
261 });
262
263 // Emit resume sequence.
264 rewriter.insertFragmentAfter(instruction, [&] (BytecodeRewriter::Fragment& fragment) {
265 data.liveness.forEachSetBit([&](size_t index) {
266 VirtualRegister operand = virtualRegisterForLocal(index);
267 Storage storage = storageForGeneratorLocal(index);
268
269 fragment.appendInstruction<OpGetFromScope>(
270 operand, // dst
271 scope, // scope
272 storage.identifierIndex, // identifier
273 GetPutInfo(DoNotThrowIfNotFound, LocalClosureVar, InitializationMode::NotInitialization), // info
274 0, // local scope depth
275 storage.scopeOffset.offset() // scope offset
276 );
277 });
278 });
279
280 // Clip the unnecessary bytecodes.
281 rewriter.removeBytecode(instruction);
282 }
283
284 if (m_generatorFrameData) {
285 auto instruction = m_instructions.at(m_generatorFrameData->m_point);
286 rewriter.insertFragmentAfter(instruction, [&] (BytecodeRewriter::Fragment& fragment) {
287 if (!m_generatorFrameSymbolTable->scopeSize()) {
288 // This will cause us to put jsUndefined() into the generator frame's scope value.
289 fragment.appendInstruction<OpMov>(m_generatorFrameData->m_dst, m_generatorFrameData->m_initialValue);
290 } else
291 fragment.appendInstruction<OpCreateLexicalEnvironment>(m_generatorFrameData->m_dst, m_generatorFrameData->m_scope, m_generatorFrameData->m_symbolTable, m_generatorFrameData->m_initialValue);
292 });
293 rewriter.removeBytecode(instruction);
294 }
295
296 rewriter.execute();
297}
298
299void performGeneratorification(BytecodeGenerator& bytecodeGenerator, UnlinkedCodeBlock* codeBlock, InstructionStreamWriter& instructions, SymbolTable* generatorFrameSymbolTable, int generatorFrameSymbolTableIndex)
300{
301 if (Options::dumpBytecodesBeforeGeneratorification())
302 BytecodeDumper<UnlinkedCodeBlock>::dumpBlock(codeBlock, instructions, WTF::dataFile());
303
304 BytecodeGeneratorification pass(bytecodeGenerator, codeBlock, instructions, generatorFrameSymbolTable, generatorFrameSymbolTableIndex);
305 pass.run();
306}
307
308} // namespace JSC
309