Update WASM towards 0xc
[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(Procedure& proc, Type signature, BasicBlock* special = nullptr, BasicBlock* continuation = nullptr)
109             : continuation(continuation)
110             , special(special)
111         {
112             if (signature != Void)
113                 result.append(proc.addVariable(toB3Type(signature)));
114         }
115
116         void dump(PrintStream& out) const
117         {
118             switch (type()) {
119             case BlockType::If:
120                 out.print("If:    ");
121                 break;
122             case BlockType::Block:
123                 out.print("Block: ");
124                 break;
125             case BlockType::Loop:
126                 out.print("Loop:  ");
127                 break;
128             }
129             out.print("Continuation: ", continuation, ", Special: ");
130             if (special)
131                 out.print(*special);
132             else
133                 out.print("None");
134         }
135
136         BlockType type() const
137         {
138             if (!special)
139                 return BlockType::Block;
140             if (continuation)
141                 return BlockType::If;
142             return BlockType::Loop;
143         }
144
145         BasicBlock* targetBlockForBranch(Procedure& proc)
146         {
147             if (type() == BlockType::Loop)
148                 return special;
149             return continuation.get(proc);
150         }
151
152     private:
153         friend class B3IRGenerator;
154         // We use a LazyBlock for the continuation since B3::validate does not like orphaned blocks. Note,
155         // it's possible to create an orphaned block by doing something like (block (return (...))). In
156         // that example, if we eagerly allocate a BasicBlock for the continuation it will never be reachable.
157         LazyBlock continuation;
158         BasicBlock* special;
159         Vector<Variable*, 1> result;
160     };
161
162     typedef Value* ExpressionType;
163     typedef ControlData ControlType;
164     typedef Vector<ExpressionType, 1> ExpressionList;
165     typedef Vector<Variable*, 1> ResultList;
166     static constexpr ExpressionType emptyExpression = nullptr;
167
168     B3IRGenerator(Procedure&);
169
170     void addArguments(const Vector<Type>&);
171     void addLocal(Type, uint32_t);
172     ExpressionType addConstant(Type, uint64_t);
173
174     bool WARN_UNUSED_RETURN getLocal(uint32_t index, ExpressionType& result);
175     bool WARN_UNUSED_RETURN setLocal(uint32_t index, ExpressionType value);
176
177     bool WARN_UNUSED_RETURN binaryOp(BinaryOpType, ExpressionType left, ExpressionType right, ExpressionType& result);
178     bool WARN_UNUSED_RETURN unaryOp(UnaryOpType, ExpressionType arg, ExpressionType& result);
179
180     ControlData WARN_UNUSED_RETURN addBlock(Type signature);
181     ControlData WARN_UNUSED_RETURN addLoop(Type signature);
182     ControlData WARN_UNUSED_RETURN addIf(ExpressionType condition, Type signature);
183     bool WARN_UNUSED_RETURN addElse(ControlData&);
184
185     bool WARN_UNUSED_RETURN addReturn(const ExpressionList& returnValues);
186     bool WARN_UNUSED_RETURN addBranch(ControlData&, ExpressionType condition, const ExpressionList& returnValues);
187     bool WARN_UNUSED_RETURN endBlock(ControlData&, ExpressionList& expressionStack);
188
189     bool isContinuationReachable(ControlData&);
190
191     void dump(const Vector<ControlType>& controlStack, const ExpressionList& expressionStack);
192
193 private:
194     void unify(Variable* target, const ExpressionType source);
195     void unifyValuesWithBlock(const ExpressionList& resultStack, ResultList& stack);
196
197     Procedure& m_proc;
198     BasicBlock* m_currentBlock;
199     Vector<Variable*> m_locals;
200 };
201
202 B3IRGenerator::B3IRGenerator(Procedure& procedure)
203     : m_proc(procedure)
204 {
205     m_currentBlock = m_proc.addBlock();
206 }
207
208 void B3IRGenerator::addLocal(Type type, uint32_t count)
209 {
210     m_locals.reserveCapacity(m_locals.size() + count);
211     for (uint32_t i = 0; i < count; ++i)
212         m_locals.append(m_proc.addVariable(toB3Type(type)));
213 }
214
215 void B3IRGenerator::addArguments(const Vector<Type>& types)
216 {
217     ASSERT(!m_locals.size());
218     m_locals.grow(types.size());
219     jscCallingConvention().iterate(types, m_proc, m_currentBlock, Origin(),
220         [&] (ExpressionType argument, unsigned i) {
221             Variable* argumentVariable = m_proc.addVariable(argument->type());
222             m_locals[i] = argumentVariable;
223             m_currentBlock->appendNew<VariableValue>(m_proc, Set, Origin(), argumentVariable, argument);
224         });
225 }
226
227 bool WARN_UNUSED_RETURN B3IRGenerator::getLocal(uint32_t index, ExpressionType& result)
228 {
229     ASSERT(m_locals[index]);
230     result = m_currentBlock->appendNew<VariableValue>(m_proc, B3::Get, Origin(), m_locals[index]);
231     return true;
232 }
233
234 bool WARN_UNUSED_RETURN B3IRGenerator::setLocal(uint32_t index, ExpressionType value)
235 {
236     ASSERT(m_locals[index]);
237     m_currentBlock->appendNew<VariableValue>(m_proc, B3::Set, Origin(), m_locals[index], value);
238     return true;
239 }
240
241 bool B3IRGenerator::unaryOp(UnaryOpType op, ExpressionType arg, ExpressionType& result)
242 {
243     result = m_currentBlock->appendNew<Value>(m_proc, toB3Op(op), Origin(), arg);
244     return true;
245 }
246
247 bool B3IRGenerator::binaryOp(BinaryOpType op, ExpressionType left, ExpressionType right, ExpressionType& result)
248 {
249     result = m_currentBlock->appendNew<Value>(m_proc, toB3Op(op), Origin(), left, right);
250     return true;
251 }
252
253 B3IRGenerator::ExpressionType B3IRGenerator::addConstant(Type type, uint64_t value)
254 {
255     switch (type) {
256     case Int32:
257         return m_currentBlock->appendNew<Const32Value>(m_proc, Origin(), static_cast<int32_t>(value));
258     case Int64:
259         return m_currentBlock->appendNew<Const64Value>(m_proc, Origin(), value);
260     case Float:
261         return m_currentBlock->appendNew<ConstFloatValue>(m_proc, Origin(), bitwise_cast<float>(static_cast<int32_t>(value)));
262     case Double:
263         return m_currentBlock->appendNew<ConstDoubleValue>(m_proc, Origin(), bitwise_cast<double>(value));
264     default:
265         RELEASE_ASSERT_NOT_REACHED();
266         return nullptr;
267     }
268 }
269
270 B3IRGenerator::ControlData B3IRGenerator::addBlock(Type signature)
271 {
272     return ControlData(m_proc, signature);
273 }
274
275 B3IRGenerator::ControlData B3IRGenerator::addLoop(Type signature)
276 {
277     BasicBlock* body = m_proc.addBlock();
278     m_currentBlock->appendNewControlValue(m_proc, Jump, Origin(), body);
279     body->addPredecessor(m_currentBlock);
280     m_currentBlock = body;
281     return ControlData(m_proc, signature, body);
282 }
283
284 B3IRGenerator::ControlData B3IRGenerator::addIf(ExpressionType condition, Type signature)
285 {
286     // FIXME: This needs to do some kind of stack passing.
287
288     BasicBlock* taken = m_proc.addBlock();
289     BasicBlock* notTaken = m_proc.addBlock();
290     BasicBlock* continuation = m_proc.addBlock();
291
292     m_currentBlock->appendNew<Value>(m_proc, B3::Branch, Origin(), condition);
293     m_currentBlock->setSuccessors(FrequentedBlock(taken), FrequentedBlock(notTaken));
294     taken->addPredecessor(m_currentBlock);
295     notTaken->addPredecessor(m_currentBlock);
296
297     m_currentBlock = taken;
298     return ControlData(m_proc, signature, notTaken, continuation);
299 }
300
301 bool B3IRGenerator::addElse(ControlData& data)
302 {
303     ASSERT(data.continuation);
304     m_currentBlock = data.special;
305     // Clear the special pointer so that when we parse the end we don't think that this block is an if block.
306     data.special = nullptr;
307     ASSERT(data.type() == BlockType::Block);
308     return true;
309 }
310
311 bool B3IRGenerator::addReturn(const ExpressionList& returnValues)
312 {
313     ASSERT(returnValues.size() <= 1);
314     if (returnValues.size())
315         m_currentBlock->appendNewControlValue(m_proc, B3::Return, Origin(), returnValues[0]);
316     else
317         m_currentBlock->appendNewControlValue(m_proc, B3::Return, Origin());
318     return true;
319 }
320
321 bool B3IRGenerator::addBranch(ControlData& data, ExpressionType condition, const ExpressionList& returnValues)
322 {
323     BasicBlock* target = data.targetBlockForBranch(m_proc);
324     unifyValuesWithBlock(returnValues, data.result);
325     if (condition) {
326         BasicBlock* continuation = m_proc.addBlock();
327         m_currentBlock->appendNew<Value>(m_proc, B3::Branch, Origin(), condition);
328         m_currentBlock->setSuccessors(FrequentedBlock(target), FrequentedBlock(continuation));
329         target->addPredecessor(m_currentBlock);
330         continuation->addPredecessor(m_currentBlock);
331         m_currentBlock = continuation;
332     } else {
333         m_currentBlock->appendNewControlValue(m_proc, Jump, Origin(), FrequentedBlock(target));
334         target->addPredecessor(m_currentBlock);
335     }
336
337     return true;
338 }
339
340 bool B3IRGenerator::endBlock(ControlData& data, ExpressionList& expressionStack)
341 {
342     if (!data.continuation)
343         return true;
344
345     BasicBlock* continuation = data.continuation.get(m_proc);
346     if (data.type() == BlockType::If) {
347         ASSERT(!data.special->size() && !data.special->successors().size());
348         // Since we don't have any else block we need to point the notTaken branch to the continuation.
349         data.special->appendNewControlValue(m_proc, Jump, Origin());
350         data.special->setSuccessors(FrequentedBlock(continuation));
351         continuation->addPredecessor(data.special);
352     }
353
354     unifyValuesWithBlock(expressionStack, data.result);
355     m_currentBlock->appendNewControlValue(m_proc, Jump, Origin(), continuation);
356     continuation->addPredecessor(m_currentBlock);
357     m_currentBlock = continuation;
358     return true;
359 }
360
361 bool B3IRGenerator::isContinuationReachable(ControlData& data)
362 {
363     // If nothing targets the continuation of the current block then we don't want to create
364     // an orphaned BasicBlock since it can't be reached by fallthrough.
365     if (!data.continuation)
366         return false;
367
368     m_currentBlock = data.continuation.get(m_proc);
369     if (data.type() == BlockType::If) {
370         data.special->appendNewControlValue(m_proc, Jump, Origin(), m_currentBlock);
371         m_currentBlock->addPredecessor(data.special);
372     }
373
374     return true;
375 }
376
377 void B3IRGenerator::unify(Variable* variable, ExpressionType source)
378 {
379     m_currentBlock->appendNew<VariableValue>(m_proc, Set, Origin(), variable, source);
380 }
381
382 void B3IRGenerator::unifyValuesWithBlock(const ExpressionList& resultStack, ResultList& result)
383 {
384     ASSERT(result.size() >= resultStack.size());
385
386     for (size_t i = 0; i < resultStack.size(); ++i)
387         unify(result[i], resultStack[i]);
388 }
389
390 void B3IRGenerator::dump(const Vector<ControlType>& controlStack, const ExpressionList& expressionStack)
391 {
392     dataLogLn("Processing Graph:");
393     dataLog(m_proc);
394     dataLogLn("With current block:", *m_currentBlock);
395     dataLogLn("Control stack:");
396     for (const ControlType& data : controlStack)
397         dataLogLn("  ", data);
398     dataLogLn("ExpressionStack:");
399     for (const ExpressionType& expression : expressionStack)
400         dataLogLn("  ", *expression);
401     dataLogLn("\n");
402 }
403
404 } // anonymous namespace
405
406 std::unique_ptr<Compilation> parseAndCompile(VM& vm, Vector<uint8_t>& source, FunctionInformation info, unsigned optLevel)
407 {
408     Procedure procedure;
409     B3IRGenerator context(procedure);
410     FunctionParser<B3IRGenerator> parser(context, source, info);
411     if (!parser.parse())
412         RELEASE_ASSERT_NOT_REACHED();
413
414     procedure.resetReachability();
415     validate(procedure, "After parsing:\n");
416
417     fixSSA(procedure);
418     if (verbose)
419         dataLog("Post SSA: ", procedure);
420     return std::make_unique<Compilation>(vm, procedure, optLevel);
421 }
422
423 } } // namespace JSC::WASM
424
425 #endif // ENABLE(WEBASSEMBLY)