fb0af1b994e425bf33e8707395a4f0922265f2df
[WebKit-https.git] / Source / JavaScriptCore / wasm / WASMB3IRGenerator.cpp
1 /*
2  * Copyright (C) 2016 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 "WASMB3IRGenerator.h"
28
29 #if ENABLE(WEBASSEMBLY)
30
31 #include "B3BasicBlockInlines.h"
32 #include "B3FixSSA.h"
33 #include "B3Validate.h"
34 #include "B3ValueInlines.h"
35 #include "B3Variable.h"
36 #include "B3VariableValue.h"
37 #include "VirtualRegister.h"
38 #include "WASMCallingConvention.h"
39 #include "WASMFunctionParser.h"
40 #include <wtf/Optional.h>
41
42 void dumpProcedure(void* ptr)
43 {
44     JSC::B3::Procedure* proc = static_cast<JSC::B3::Procedure*>(ptr);
45     proc->dump(WTF::dataFile());
46 }
47
48 namespace JSC { namespace WASM {
49
50 namespace {
51
52 using namespace B3;
53
54 const bool verbose = false;
55
56 inline B3::Opcode toB3Op(BinaryOpType op)
57 {
58     switch (op) {
59 #define CREATE_CASE(name, op, b3op) case BinaryOpType::name: return b3op;
60     FOR_EACH_WASM_BINARY_OP(CREATE_CASE)
61 #undef CREATE_CASE
62     }
63     RELEASE_ASSERT_NOT_REACHED();
64 }
65
66 inline B3::Opcode toB3Op(UnaryOpType op)
67 {
68     switch (op) {
69 #define CREATE_CASE(name, op, b3op) case UnaryOpType::name: return b3op;
70     FOR_EACH_WASM_UNARY_OP(CREATE_CASE)
71 #undef CREATE_CASE
72     }
73     RELEASE_ASSERT_NOT_REACHED();
74 }
75
76 class B3IRGenerator {
77 private:
78     class LazyBlock {
79     public:
80         LazyBlock(BasicBlock* block)
81             : m_block(block)
82         {
83         }
84
85         explicit operator bool() const { return !!m_block; }
86
87         BasicBlock* get(Procedure& proc)
88         {
89             if (!m_block)
90                 m_block = proc.addBlock();
91             return m_block;
92         }
93
94         void dump(PrintStream& out) const
95         {
96             if (m_block)
97                 out.print(*m_block);
98             else
99                 out.print("Uninitialized");
100         }
101
102     private:
103         BasicBlock* m_block { nullptr };
104     };
105
106 public:
107     struct ControlData {
108         ControlData(Optional<Vector<Variable*>>&& stack, BasicBlock* special = nullptr, BasicBlock* continuation = nullptr)
109             : continuation(continuation)
110             , special(special)
111             , stack(stack)
112         {
113         }
114
115         void dump(PrintStream& out) const
116         {
117             switch (type()) {
118             case BlockType::If:
119                 out.print("If:    ");
120                 break;
121             case BlockType::Block:
122                 out.print("Block: ");
123                 break;
124             case BlockType::Loop:
125                 out.print("Loop:  ");
126                 break;
127             }
128             out.print("Continuation: ", continuation, ", Special: ");
129             if (special)
130                 out.print(*special);
131             else
132                 out.print("None");
133         }
134
135         BlockType type() const
136         {
137             if (!special)
138                 return BlockType::Block;
139             if (continuation)
140                 return BlockType::If;
141             return BlockType::Loop;
142         }
143
144         BasicBlock* targetBlockForBranch(Procedure& proc)
145         {
146             if (special)
147                 return special;
148             return continuation.get(proc);
149         }
150
151     private:
152         friend class B3IRGenerator;
153         // We use a LazyBlock for the continuation since B3::validate does not like orphaned blocks. Note,
154         // it's possible to create an orphaned block by doing something like (block (return (...))). In
155         // that example, if we eagerly allocate a BasicBlock for the continuation it will never be reachable.
156         LazyBlock continuation;
157         BasicBlock* special;
158         Optional<Vector<Variable*>> stack;
159     };
160
161     typedef Value* ExpressionType;
162     typedef ControlData ControlType;
163     static constexpr ExpressionType emptyExpression = nullptr;
164
165     B3IRGenerator(Procedure&);
166
167     void addArguments(const Vector<Type>&);
168     void addLocal(Type, uint32_t);
169     ExpressionType addConstant(Type, uint64_t);
170
171     bool WARN_UNUSED_RETURN getLocal(uint32_t index, ExpressionType& result);
172     bool WARN_UNUSED_RETURN setLocal(uint32_t index, ExpressionType value);
173
174     bool WARN_UNUSED_RETURN binaryOp(BinaryOpType, ExpressionType left, ExpressionType right, ExpressionType& result);
175     bool WARN_UNUSED_RETURN unaryOp(UnaryOpType, ExpressionType arg, ExpressionType& result);
176
177     ControlData WARN_UNUSED_RETURN addBlock();
178     ControlData WARN_UNUSED_RETURN addLoop();
179     ControlData WARN_UNUSED_RETURN addIf(ExpressionType condition);
180     bool WARN_UNUSED_RETURN addElse(ControlData&);
181
182     bool WARN_UNUSED_RETURN addReturn(const Vector<ExpressionType, 1>& returnValues);
183     bool WARN_UNUSED_RETURN addBranch(ControlData&, ExpressionType condition, const Vector<ExpressionType, 1>& returnValues);
184     bool WARN_UNUSED_RETURN endBlock(ControlData&, Vector<ExpressionType, 1>& expressionStack);
185
186     bool isContinuationReachable(ControlData&);
187
188     void dump(const Vector<ControlType>& controlStack, const Vector<ExpressionType, 1>& expressionStack);
189
190 private:
191     void unify(Variable* target, const ExpressionType source);
192     Vector<Variable*> initializeIncommingTypes(BasicBlock*, const Vector<ExpressionType, 1>&);
193     void unifyValuesWithBlock(const Vector<ExpressionType, 1>& resultStack, Optional<Vector<Variable*>>& stack, BasicBlock* target);
194
195     Procedure& m_proc;
196     BasicBlock* m_currentBlock;
197     Vector<Variable*> m_locals;
198 };
199
200 B3IRGenerator::B3IRGenerator(Procedure& procedure)
201     : m_proc(procedure)
202 {
203     m_currentBlock = m_proc.addBlock();
204 }
205
206 void B3IRGenerator::addLocal(Type type, uint32_t count)
207 {
208     m_locals.reserveCapacity(m_locals.size() + count);
209     for (uint32_t i = 0; i < count; ++i)
210         m_locals.append(m_proc.addVariable(toB3Type(type)));
211 }
212
213 void B3IRGenerator::addArguments(const Vector<Type>& types)
214 {
215     ASSERT(!m_locals.size());
216     m_locals.grow(types.size());
217     jscCallingConvention().iterate(types, m_proc, m_currentBlock, Origin(),
218         [&] (ExpressionType argument, unsigned i) {
219             Variable* argumentVariable = m_proc.addVariable(argument->type());
220             m_locals[i] = argumentVariable;
221             m_currentBlock->appendNew<VariableValue>(m_proc, Set, Origin(), argumentVariable, argument);
222         });
223 }
224
225 bool WARN_UNUSED_RETURN B3IRGenerator::getLocal(uint32_t index, ExpressionType& result)
226 {
227     ASSERT(m_locals[index]);
228     result = m_currentBlock->appendNew<VariableValue>(m_proc, B3::Get, Origin(), m_locals[index]);
229     return true;
230 }
231
232 bool WARN_UNUSED_RETURN B3IRGenerator::setLocal(uint32_t index, ExpressionType value)
233 {
234     ASSERT(m_locals[index]);
235     m_currentBlock->appendNew<VariableValue>(m_proc, B3::Set, Origin(), m_locals[index], value);
236     return true;
237 }
238
239 bool B3IRGenerator::unaryOp(UnaryOpType op, ExpressionType arg, ExpressionType& result)
240 {
241     result = m_currentBlock->appendNew<Value>(m_proc, toB3Op(op), Origin(), arg);
242     return true;
243 }
244
245 bool B3IRGenerator::binaryOp(BinaryOpType op, ExpressionType left, ExpressionType right, ExpressionType& result)
246 {
247     result = m_currentBlock->appendNew<Value>(m_proc, toB3Op(op), Origin(), left, right);
248     return true;
249 }
250
251 B3IRGenerator::ExpressionType B3IRGenerator::addConstant(Type type, uint64_t value)
252 {
253     switch (type) {
254     case Int32:
255         return m_currentBlock->appendNew<Const32Value>(m_proc, Origin(), static_cast<int32_t>(value));
256     case Int64:
257         return m_currentBlock->appendNew<Const64Value>(m_proc, Origin(), value);
258     case Float:
259         return m_currentBlock->appendNew<ConstFloatValue>(m_proc, Origin(), bitwise_cast<float>(static_cast<int32_t>(value)));
260     case Double:
261         return m_currentBlock->appendNew<ConstDoubleValue>(m_proc, Origin(), bitwise_cast<double>(value));
262     default:
263         RELEASE_ASSERT_NOT_REACHED();
264         return nullptr;
265     }
266 }
267
268 B3IRGenerator::ControlData B3IRGenerator::addBlock()
269 {
270     return ControlData(Nullopt);
271 }
272
273 B3IRGenerator::ControlData B3IRGenerator::addLoop()
274 {
275     BasicBlock* body = m_proc.addBlock();
276     m_currentBlock->appendNewControlValue(m_proc, Jump, Origin(), body);
277     body->addPredecessor(m_currentBlock);
278     m_currentBlock = body;
279     return ControlData(Vector<Variable*>(), body);
280 }
281
282 B3IRGenerator::ControlData B3IRGenerator::addIf(ExpressionType condition)
283 {
284     // FIXME: This needs to do some kind of stack passing.
285
286     BasicBlock* taken = m_proc.addBlock();
287     BasicBlock* notTaken = m_proc.addBlock();
288     BasicBlock* continuation = m_proc.addBlock();
289
290     m_currentBlock->appendNew<Value>(m_proc, B3::Branch, Origin(), condition);
291     m_currentBlock->setSuccessors(FrequentedBlock(taken), FrequentedBlock(notTaken));
292     taken->addPredecessor(m_currentBlock);
293     notTaken->addPredecessor(m_currentBlock);
294
295     m_currentBlock = taken;
296     return ControlData(Nullopt, notTaken, continuation);
297 }
298
299 bool B3IRGenerator::addElse(ControlData& data)
300 {
301     ASSERT(data.continuation);
302     m_currentBlock = data.special;
303     // Clear the special pointer so that when we parse the end we don't think that this block is an if block.
304     data.special = nullptr;
305     ASSERT(data.type() == BlockType::Block);
306     return true;
307 }
308
309 bool B3IRGenerator::addReturn(const Vector<ExpressionType, 1>& returnValues)
310 {
311     ASSERT(returnValues.size() <= 1);
312     if (returnValues.size())
313         m_currentBlock->appendNewControlValue(m_proc, B3::Return, Origin(), returnValues[0]);
314     else
315         m_currentBlock->appendNewControlValue(m_proc, B3::Return, Origin());
316     return true;
317 }
318
319 bool B3IRGenerator::addBranch(ControlData& data, ExpressionType condition, const Vector<ExpressionType, 1>& returnValues)
320 {
321     BasicBlock* target = data.targetBlockForBranch(m_proc);
322     unifyValuesWithBlock(returnValues, data.stack, target);
323     if (condition) {
324         BasicBlock* continuation = m_proc.addBlock();
325         m_currentBlock->appendNew<Value>(m_proc, B3::Branch, Origin(), condition);
326         m_currentBlock->setSuccessors(FrequentedBlock(target), FrequentedBlock(continuation));
327         target->addPredecessor(m_currentBlock);
328         continuation->addPredecessor(m_currentBlock);
329         m_currentBlock = continuation;
330     } else {
331         m_currentBlock->appendNewControlValue(m_proc, Jump, Origin(), FrequentedBlock(target));
332         target->addPredecessor(m_currentBlock);
333     }
334
335     return true;
336 }
337
338 bool B3IRGenerator::endBlock(ControlData& data, Vector<ExpressionType, 1>& expressionStack)
339 {
340     if (!data.continuation)
341         return true;
342
343     BasicBlock* continuation = data.continuation.get(m_proc);
344     if (data.type() == BlockType::If) {
345         ASSERT(!data.special->size() && !data.special->successors().size());
346         // Since we don't have any else block we need to point the notTaken branch to the continuation.
347         data.special->appendNewControlValue(m_proc, Jump, Origin());
348         data.special->setSuccessors(FrequentedBlock(continuation));
349         continuation->addPredecessor(data.special);
350     }
351
352     unifyValuesWithBlock(expressionStack, data.stack, continuation);
353     m_currentBlock->appendNewControlValue(m_proc, Jump, Origin(), continuation);
354     continuation->addPredecessor(m_currentBlock);
355     m_currentBlock = continuation;
356     return true;
357 }
358
359 bool B3IRGenerator::isContinuationReachable(ControlData& data)
360 {
361     // If nothing targets the continuation of the current block then we don't want to create
362     // an orphaned BasicBlock since it can't be reached by fallthrough.
363     if (!data.continuation)
364         return false;
365
366     m_currentBlock = data.continuation.get(m_proc);
367     if (data.type() == BlockType::If) {
368         data.special->appendNewControlValue(m_proc, Jump, Origin(), m_currentBlock);
369         m_currentBlock->addPredecessor(data.special);
370     }
371
372     return true;
373 }
374
375 void B3IRGenerator::unify(Variable* variable, ExpressionType source)
376 {
377     m_currentBlock->appendNew<VariableValue>(m_proc, Set, Origin(), variable, source);
378 }
379
380 Vector<Variable*> B3IRGenerator::initializeIncommingTypes(BasicBlock* block, const Vector<ExpressionType, 1>& source)
381 {
382     Vector<Variable*> result;
383     result.reserveInitialCapacity(source.size());
384     for (ExpressionType expr : source) {
385         ASSERT(expr->type() != B3::Void);
386         Variable* var = m_proc.addVariable(expr->type());
387         result.append(var);
388         block->appendNew<VariableValue>(m_proc, B3::Get, Origin(), var);
389     }
390
391     return result;
392 }
393
394 void B3IRGenerator::unifyValuesWithBlock(const Vector<ExpressionType, 1>& resultStack, Optional<Vector<Variable*>>& stack, BasicBlock* target)
395 {
396     if (!stack) {
397         stack = initializeIncommingTypes(target, resultStack);
398         return;
399     }
400
401     ASSERT(stack.value().size() == resultStack.size());
402
403     for (size_t i = 0; i < resultStack.size(); ++i)
404         unify(stack.value()[i], resultStack[i]);
405 }
406
407 void B3IRGenerator::dump(const Vector<ControlType>& controlStack, const Vector<ExpressionType, 1>& expressionStack)
408 {
409     dataLogLn("Processing Graph:");
410     dataLog(m_proc);
411     dataLogLn("With current block:", *m_currentBlock);
412     dataLogLn("Control stack:");
413     for (const ControlType& data : controlStack)
414         dataLogLn("  ", data);
415     dataLogLn("ExpressionStack:");
416     for (const ExpressionType& expression : expressionStack)
417         dataLogLn("  ", *expression);
418     dataLogLn("\n");
419 }
420
421 } // anonymous namespace
422
423 std::unique_ptr<Compilation> parseAndCompile(VM& vm, Vector<uint8_t>& source, FunctionInformation info, unsigned optLevel)
424 {
425     Procedure procedure;
426     B3IRGenerator context(procedure);
427     FunctionParser<B3IRGenerator> parser(context, source, info);
428     if (!parser.parse())
429         RELEASE_ASSERT_NOT_REACHED();
430
431     procedure.resetReachability();
432     validate(procedure, "After parsing:\n");
433
434     fixSSA(procedure);
435     if (verbose)
436         dataLog("Post SSA: ", procedure);
437     return std::make_unique<Compilation>(vm, procedure, optLevel);
438 }
439
440 } } // namespace JSC::WASM
441
442 #endif // ENABLE(WEBASSEMBLY)