Wasm should support call_indirect
[WebKit-https.git] / Source / JavaScriptCore / wasm / WasmFunctionParser.h
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 #pragma once
27
28 #if ENABLE(WEBASSEMBLY)
29
30 #include "WasmParser.h"
31 #include <wtf/DataLog.h>
32
33 namespace JSC { namespace Wasm {
34
35 enum class BlockType {
36     If,
37     Block,
38     Loop
39 };
40
41 template<typename Context>
42 class FunctionParser : public Parser {
43 public:
44     typedef typename Context::ExpressionType ExpressionType;
45     typedef typename Context::ControlType ControlType;
46     typedef typename Context::ExpressionList ExpressionList;
47
48     FunctionParser(Context&, const uint8_t* functionStart, size_t functionLength, const Signature*, const ImmutableFunctionIndexSpace&, const ModuleInformation&);
49
50     bool WARN_UNUSED_RETURN parse();
51
52     struct ControlEntry {
53         ExpressionList enclosedExpressionStack;
54         ControlType controlData;
55     };
56
57 private:
58     static const bool verbose = false;
59
60     bool WARN_UNUSED_RETURN parseBody();
61     bool WARN_UNUSED_RETURN parseExpression(OpType);
62     bool WARN_UNUSED_RETURN parseUnreachableExpression(OpType);
63     bool WARN_UNUSED_RETURN addReturn();
64     bool WARN_UNUSED_RETURN unifyControl(Vector<ExpressionType>&, unsigned level);
65
66     bool WARN_UNUSED_RETURN popExpressionStack(ExpressionType& result);
67
68     template<OpType>
69     bool WARN_UNUSED_RETURN unaryCase();
70
71     template<OpType>
72     bool WARN_UNUSED_RETURN binaryCase();
73
74     bool setErrorMessage(String&& message)
75     {
76         m_context.setErrorMessage(WTFMove(message));
77         return false;
78     }
79
80     Context& m_context;
81     ExpressionList m_expressionStack;
82     Vector<ControlEntry> m_controlStack;
83     const Signature* m_signature;
84     const ImmutableFunctionIndexSpace& m_functionIndexSpace;
85     const ModuleInformation& m_info;
86     unsigned m_unreachableBlocks { 0 };
87 };
88
89 template<typename Context>
90 FunctionParser<Context>::FunctionParser(Context& context, const uint8_t* functionStart, size_t functionLength, const Signature* signature, const ImmutableFunctionIndexSpace& functionIndexSpace, const ModuleInformation& info)
91     : Parser(functionStart, functionLength)
92     , m_context(context)
93     , m_signature(signature)
94     , m_functionIndexSpace(functionIndexSpace)
95     , m_info(info)
96 {
97     if (verbose)
98         dataLogLn("Parsing function starting at: ", (uintptr_t)functionStart, " of length: ", functionLength);
99 }
100
101 template<typename Context>
102 bool FunctionParser<Context>::parse()
103 {
104     if (!m_context.addArguments(m_signature->arguments))
105         return false;
106
107     uint32_t localCount;
108     if (!parseVarUInt32(localCount))
109         return false;
110
111     for (uint32_t i = 0; i < localCount; ++i) {
112         uint32_t numberOfLocals;
113         if (!parseVarUInt32(numberOfLocals))
114             return false;
115
116         Type typeOfLocal;
117         if (!parseValueType(typeOfLocal))
118             return false;
119
120         if (!m_context.addLocal(typeOfLocal, numberOfLocals))
121             return false;
122     }
123
124     return parseBody();
125 }
126
127 template<typename Context>
128 bool FunctionParser<Context>::parseBody()
129 {
130     while (true) {
131         uint8_t op;
132         if (!parseUInt8(op) || !isValidOpType(op)) {
133             if (verbose)
134                 WTF::dataLogLn("attempted to decode invalid op: ", RawPointer(reinterpret_cast<void*>(op)), " at offset: ", RawPointer(reinterpret_cast<void*>(m_offset)));
135             return false;
136         }
137
138         if (verbose) {
139             dataLogLn("processing op (", m_unreachableBlocks, "): ",  RawPointer(reinterpret_cast<void*>(op)), " at offset: ", RawPointer(reinterpret_cast<void*>(m_offset)));
140             m_context.dump(m_controlStack, m_expressionStack);
141         }
142
143         if (op == OpType::End && !m_controlStack.size())
144             return m_unreachableBlocks ? true : addReturn();
145
146         if (m_unreachableBlocks) {
147             if (!parseUnreachableExpression(static_cast<OpType>(op))) {
148                 if (verbose)
149                     dataLogLn("failed to process unreachable op:", op);
150                 return false;
151             }
152         } else if (!parseExpression(static_cast<OpType>(op))) {
153             if (verbose)
154                 dataLogLn("failed to process op:", op);
155             return false;
156         }
157
158     }
159
160     RELEASE_ASSERT_NOT_REACHED();
161 }
162
163 template<typename Context>
164 bool FunctionParser<Context>::addReturn()
165 {
166     ExpressionList returnValues;
167     if (m_signature->returnType != Void) {
168         ExpressionType returnValue;
169         if (!popExpressionStack(returnValue))
170             return false;
171         returnValues.append(returnValue);
172     }
173
174     m_unreachableBlocks = 1;
175     return m_context.addReturn(returnValues);
176 }
177
178 template<typename Context>
179 template<OpType op>
180 bool FunctionParser<Context>::binaryCase()
181 {
182     ExpressionType right;
183     if (!popExpressionStack(right))
184         return false;
185
186     ExpressionType left;
187     if (!popExpressionStack(left))
188         return false;
189
190     ExpressionType result;
191     if (!m_context.template addOp<op>(left, right, result))
192         return false;
193     m_expressionStack.append(result);
194     return true;
195 }
196
197 template<typename Context>
198 template<OpType op>
199 bool FunctionParser<Context>::unaryCase()
200 {
201     ExpressionType value;
202     if (!popExpressionStack(value))
203         return false;
204
205     ExpressionType result;
206     if (!m_context.template addOp<op>(value, result))
207         return false;
208     m_expressionStack.append(result);
209     return true;
210 }
211
212 template<typename Context>
213 bool FunctionParser<Context>::parseExpression(OpType op)
214 {
215     switch (op) {
216 #define CREATE_CASE(name, id, b3op, inc) case OpType::name: return binaryCase<OpType::name>();
217     FOR_EACH_WASM_SIMPLE_BINARY_OP(CREATE_CASE)
218 #undef CREATE_CASE
219
220     case OpType::F32ConvertUI64: return unaryCase<OpType::F32ConvertUI64>();
221     case OpType::F64ConvertUI64: return unaryCase<OpType::F64ConvertUI64>();
222     case OpType::F32Nearest: return unaryCase<OpType::F32Nearest>();
223     case OpType::F64Nearest: return unaryCase<OpType::F64Nearest>();
224     case OpType::F32Trunc: return unaryCase<OpType::F32Trunc>();
225     case OpType::F64Trunc: return unaryCase<OpType::F64Trunc>();
226     case OpType::I32Ctz: return unaryCase<OpType::I32Ctz>();
227     case OpType::I64Ctz: return unaryCase<OpType::I64Ctz>();
228     case OpType::I32Popcnt: return unaryCase<OpType::I32Popcnt>();
229     case OpType::I64Popcnt: return unaryCase<OpType::I64Popcnt>();
230     case OpType::I32TruncSF32: return unaryCase<OpType::I32TruncSF32>();
231     case OpType::I32TruncUF32: return unaryCase<OpType::I32TruncUF32>();
232     case OpType::I32TruncSF64: return unaryCase<OpType::I32TruncSF64>();
233     case OpType::I32TruncUF64: return unaryCase<OpType::I32TruncUF64>();
234     case OpType::I64TruncSF32: return unaryCase<OpType::I64TruncSF32>();
235     case OpType::I64TruncUF32: return unaryCase<OpType::I64TruncUF32>();
236     case OpType::I64TruncSF64: return unaryCase<OpType::I64TruncSF64>();
237     case OpType::I64TruncUF64: return unaryCase<OpType::I64TruncUF64>();
238 #define CREATE_CASE(name, id, b3op, inc) case OpType::name: return unaryCase<OpType::name>();
239     FOR_EACH_WASM_SIMPLE_UNARY_OP(CREATE_CASE)
240 #undef CREATE_CASE
241
242     case OpType::Select: {
243         ExpressionType condition;
244         if (!popExpressionStack(condition))
245             return false;
246
247         ExpressionType zero;
248         if (!popExpressionStack(zero))
249             return false;
250
251         ExpressionType nonZero;
252         if (!popExpressionStack(nonZero))
253             return false;
254
255         ExpressionType result;
256         if (!m_context.addSelect(condition, nonZero, zero, result))
257             return false;
258
259         m_expressionStack.append(result);
260         return true;
261     }
262
263 #define CREATE_CASE(name, id, b3op, inc) case OpType::name:
264     FOR_EACH_WASM_MEMORY_LOAD_OP(CREATE_CASE) {
265         uint32_t alignment;
266         if (!parseVarUInt32(alignment))
267             return false;
268
269         uint32_t offset;
270         if (!parseVarUInt32(offset))
271             return false;
272
273         ExpressionType pointer;
274         if (!popExpressionStack(pointer))
275             return false;
276
277         ExpressionType result;
278         if (!m_context.load(static_cast<LoadOpType>(op), pointer, result, offset))
279             return false;
280         m_expressionStack.append(result);
281         return true;
282     }
283
284     FOR_EACH_WASM_MEMORY_STORE_OP(CREATE_CASE) {
285         uint32_t alignment;
286         if (!parseVarUInt32(alignment))
287             return false;
288
289         uint32_t offset;
290         if (!parseVarUInt32(offset))
291             return false;
292
293         ExpressionType value;
294         if (!popExpressionStack(value))
295             return false;
296
297         ExpressionType pointer;
298         if (!popExpressionStack(pointer))
299             return false;
300
301         return m_context.store(static_cast<StoreOpType>(op), pointer, value, offset);
302     }
303 #undef CREATE_CASE
304
305     case OpType::F32Const:
306     case OpType::I32Const: {
307         uint32_t constant;
308         if (!parseVarUInt32(constant))
309             return false;
310         m_expressionStack.append(m_context.addConstant(I32, constant));
311         return true;
312     }
313
314     case OpType::F64Const:
315     case OpType::I64Const: {
316         uint64_t constant;
317         if (!parseVarUInt64(constant))
318             return false;
319         m_expressionStack.append(m_context.addConstant(I64, constant));
320         return true;
321     }
322
323     case OpType::GetLocal: {
324         uint32_t index;
325         if (!parseVarUInt32(index))
326             return false;
327         ExpressionType result;
328         if (!m_context.getLocal(index, result))
329             return false;
330
331         m_expressionStack.append(result);
332         return true;
333     }
334
335     case OpType::SetLocal: {
336         uint32_t index;
337         if (!parseVarUInt32(index))
338             return false;
339         ExpressionType value;
340         if (!popExpressionStack(value))
341             return false;
342         return m_context.setLocal(index, value);
343     }
344
345     case OpType::TeeLocal: {
346         uint32_t index;
347         if (!parseVarUInt32(index))
348             return false;
349         if (!m_expressionStack.size())
350             return false;
351         return m_context.setLocal(index, m_expressionStack.last());
352     }
353
354     case OpType::Call: {
355         uint32_t functionIndex;
356         if (!parseVarUInt32(functionIndex))
357             return false;
358
359         if (functionIndex >= m_functionIndexSpace.size)
360             return false;
361
362         const Signature* calleeSignature = m_functionIndexSpace.buffer.get()[functionIndex].signature;
363
364         if (calleeSignature->arguments.size() > m_expressionStack.size())
365             return false;
366
367         size_t firstArgumentIndex = m_expressionStack.size() - calleeSignature->arguments.size();
368         Vector<ExpressionType> args;
369         args.reserveInitialCapacity(calleeSignature->arguments.size());
370         for (unsigned i = firstArgumentIndex; i < m_expressionStack.size(); ++i)
371             args.append(m_expressionStack[i]);
372         m_expressionStack.shrink(firstArgumentIndex);
373
374         ExpressionType result = Context::emptyExpression;
375         if (!m_context.addCall(functionIndex, calleeSignature, args, result))
376             return false;
377
378         if (result != Context::emptyExpression)
379             m_expressionStack.append(result);
380
381         return true;
382     }
383
384     case OpType::CallIndirect: {
385         uint32_t signatureIndex;
386         if (!parseVarUInt32(signatureIndex))
387             return false;
388
389         uint8_t reserved;
390         if (!parseVarUInt1(reserved))
391             return false;
392
393         if (m_info.signatures.size() <= signatureIndex)
394             return setErrorMessage("Tried to use a signature outside the range of valid signatures");
395
396         const Signature* calleeSignature = &m_info.signatures[signatureIndex];
397         size_t argumentCount = calleeSignature->arguments.size() + 1; // Add the callee's index.
398         if (argumentCount > m_expressionStack.size())
399             return setErrorMessage("Not enough values on the stack for call_indirect");
400
401         Vector<ExpressionType> args;
402         if (!args.tryReserveCapacity(argumentCount))
403             return setErrorMessage("Out of memory");
404
405         size_t firstArgumentIndex = m_expressionStack.size() - argumentCount;
406         for (unsigned i = firstArgumentIndex; i < m_expressionStack.size(); ++i)
407             args.uncheckedAppend(m_expressionStack[i]);
408         m_expressionStack.shrink(firstArgumentIndex);
409
410         ExpressionType result = Context::emptyExpression;
411         if (!m_context.addCallIndirect(calleeSignature, args, result))
412             return false;
413
414         if (result != Context::emptyExpression)
415             m_expressionStack.append(result);
416
417         return true;
418     }
419
420     case OpType::Block: {
421         Type inlineSignature;
422         if (!parseResultType(inlineSignature))
423             return false;
424
425         m_controlStack.append({ WTFMove(m_expressionStack), m_context.addBlock(inlineSignature) });
426         m_expressionStack = ExpressionList();
427         return true;
428     }
429
430     case OpType::Loop: {
431         Type inlineSignature;
432         if (!parseResultType(inlineSignature))
433             return false;
434
435         m_controlStack.append({ WTFMove(m_expressionStack), m_context.addLoop(inlineSignature) });
436         m_expressionStack = ExpressionList();
437         return true;
438     }
439
440     case OpType::If: {
441         Type inlineSignature;
442         if (!parseResultType(inlineSignature))
443             return false;
444
445         ExpressionType condition;
446         if (!popExpressionStack(condition))
447             return false;
448
449         ControlType control;
450         if (!m_context.addIf(condition, inlineSignature, control))
451             return false;
452
453         m_controlStack.append({ WTFMove(m_expressionStack), control });
454         m_expressionStack = ExpressionList();
455         return true;
456     }
457
458     case OpType::Else: {
459         if (!m_controlStack.size()) {
460             setErrorMessage("Attempted to use else block at the top-level of a function");
461             return false;
462         }
463
464         if (!m_context.addElse(m_controlStack.last().controlData, m_expressionStack))
465             return false;
466         m_expressionStack.shrink(0);
467         return true;
468     }
469
470     case OpType::Br:
471     case OpType::BrIf: {
472         uint32_t target;
473         if (!parseVarUInt32(target) || target >= m_controlStack.size())
474             return false;
475
476         ExpressionType condition = Context::emptyExpression;
477         if (op == OpType::BrIf) {
478             if (!popExpressionStack(condition))
479                 return false;
480         } else
481             m_unreachableBlocks = 1;
482
483         ControlType& data = m_controlStack[m_controlStack.size() - 1 - target].controlData;
484
485         return m_context.addBranch(data, condition, m_expressionStack);
486     }
487
488     case OpType::BrTable: {
489         uint32_t numberOfTargets;
490         if (!parseVarUInt32(numberOfTargets))
491             return false;
492
493         Vector<ControlType*> targets;
494         if (!targets.tryReserveCapacity(numberOfTargets))
495             return false;
496
497         for (uint32_t i = 0; i < numberOfTargets; ++i) {
498             uint32_t target;
499             if (!parseVarUInt32(target))
500                 return false;
501
502             if (target >= m_controlStack.size())
503                 return false;
504
505             targets.uncheckedAppend(&m_controlStack[m_controlStack.size() - 1 - target].controlData);
506         }
507
508         uint32_t defaultTarget;
509         if (!parseVarUInt32(defaultTarget))
510             return false;
511
512         if (defaultTarget >= m_controlStack.size())
513             return false;
514
515         ExpressionType condition;
516         if (!popExpressionStack(condition))
517             return false;
518         
519         if (!m_context.addSwitch(condition, targets, m_controlStack[m_controlStack.size() - 1 - defaultTarget].controlData, m_expressionStack))
520             return false;
521
522         m_unreachableBlocks = 1;
523         return true;
524     }
525
526     case OpType::Return: {
527         return addReturn();
528     }
529
530     case OpType::End: {
531         ControlEntry data = m_controlStack.takeLast();
532         // FIXME: This is a little weird in that it will modify the expressionStack for the result of the block.
533         // That's a little too effectful for me but I don't have a better API right now.
534         // see: https://bugs.webkit.org/show_bug.cgi?id=164353
535         if (!m_context.endBlock(data, m_expressionStack))
536             return false;
537         m_expressionStack.swap(data.enclosedExpressionStack);
538         return true;
539     }
540
541     case OpType::Unreachable: {
542         m_unreachableBlocks = 1;
543         return true;
544     }
545
546     case OpType::Drop: {
547         if (!m_expressionStack.size()) {
548             setErrorMessage("Attempted to drop an expression from an empty stack.");
549             return false;
550         }
551         m_expressionStack.takeLast();
552         return true;
553     }
554
555     case OpType::Nop: {
556         return true;
557     }
558
559     case OpType::GrowMemory:
560     case OpType::CurrentMemory:
561     case OpType::GetGlobal:
562     case OpType::SetGlobal: {
563         // FIXME: Not yet implemented.
564         return false;
565     }
566     }
567
568     ASSERT_NOT_REACHED();
569 }
570
571 template<typename Context>
572 bool FunctionParser<Context>::parseUnreachableExpression(OpType op)
573 {
574     ASSERT(m_unreachableBlocks);
575     switch (op) {
576     case OpType::Else: {
577         if (m_unreachableBlocks > 1)
578             return true;
579
580         ControlEntry& data = m_controlStack.last();
581         m_unreachableBlocks = 0;
582         if (!m_context.addElseToUnreachable(data.controlData))
583             return false;
584         m_expressionStack.shrink(0);
585         return true;
586     }
587
588     case OpType::End: {
589         if (m_unreachableBlocks == 1) {
590             ControlEntry data = m_controlStack.takeLast();
591             if (!m_context.addEndToUnreachable(data))
592                 return false;
593             m_expressionStack.swap(data.enclosedExpressionStack);
594         }
595         m_unreachableBlocks--;
596         return true;
597     }
598
599     case OpType::Loop:
600     case OpType::If:
601     case OpType::Block: {
602         m_unreachableBlocks++;
603         return true;
604     }
605
606     // two immediate cases
607     case OpType::Br:
608     case OpType::BrIf: {
609         uint32_t unused;
610         if (!parseVarUInt32(unused))
611             return false;
612         return parseVarUInt32(unused);
613     }
614
615     // one immediate cases
616     case OpType::F32Const:
617     case OpType::I32Const:
618     case OpType::F64Const:
619     case OpType::I64Const:
620     case OpType::SetLocal:
621     case OpType::GetLocal: {
622         uint32_t unused;
623         return parseVarUInt32(unused);
624     }
625
626     default:
627         break;
628     }
629     return true;
630 }
631
632 template<typename Context>
633 bool FunctionParser<Context>::popExpressionStack(ExpressionType& result)
634 {
635     if (m_expressionStack.size()) {
636         result = m_expressionStack.takeLast();
637         return true;
638     }
639
640     setErrorMessage("Attempted to use a stack value when none existed");
641     return false;
642 }
643
644 } } // namespace JSC::Wasm
645
646 #endif // ENABLE(WEBASSEMBLY)