Add support for Wasm ctz and popcnt
[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 Vector<FunctionInformation>& functions);
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     void setErrorMessage(String&& message) { m_context.setErrorMessage(WTFMove(message)); }
75
76     Context& m_context;
77     ExpressionList m_expressionStack;
78     Vector<ControlEntry> m_controlStack;
79     const Signature* m_signature;
80     const Vector<FunctionInformation>& m_functions;
81     unsigned m_unreachableBlocks { 0 };
82 };
83
84 template<typename Context>
85 FunctionParser<Context>::FunctionParser(Context& context, const uint8_t* functionStart, size_t functionLength, const Signature* signature, const Vector<FunctionInformation>& functions)
86     : Parser(functionStart, functionLength)
87     , m_context(context)
88     , m_signature(signature)
89     , m_functions(functions)
90 {
91     if (verbose)
92         dataLogLn("Parsing function starting at: ", (uintptr_t)functionStart, " of length: ", functionLength);
93 }
94
95 template<typename Context>
96 bool FunctionParser<Context>::parse()
97 {
98     if (!m_context.addArguments(m_signature->arguments))
99         return false;
100
101     uint32_t localCount;
102     if (!parseVarUInt32(localCount))
103         return false;
104
105     for (uint32_t i = 0; i < localCount; ++i) {
106         uint32_t numberOfLocals;
107         if (!parseVarUInt32(numberOfLocals))
108             return false;
109
110         Type typeOfLocal;
111         if (!parseValueType(typeOfLocal))
112             return false;
113
114         if (!m_context.addLocal(typeOfLocal, numberOfLocals))
115             return false;
116     }
117
118     return parseBody();
119 }
120
121 template<typename Context>
122 bool FunctionParser<Context>::parseBody()
123 {
124     while (true) {
125         uint8_t op;
126         if (!parseUInt8(op) || !isValidOpType(op)) {
127             if (verbose)
128                 WTF::dataLogLn("attempted to decode invalid op: ", RawPointer(reinterpret_cast<void*>(op)), " at offset: ", RawPointer(reinterpret_cast<void*>(m_offset)));
129             return false;
130         }
131
132         if (verbose) {
133             dataLogLn("processing op (", m_unreachableBlocks, "): ",  RawPointer(reinterpret_cast<void*>(op)), " at offset: ", RawPointer(reinterpret_cast<void*>(m_offset)));
134             m_context.dump(m_controlStack, m_expressionStack);
135         }
136
137         if (op == OpType::End && !m_controlStack.size())
138             return m_unreachableBlocks ? true : addReturn();
139
140         if (m_unreachableBlocks) {
141             if (!parseUnreachableExpression(static_cast<OpType>(op))) {
142                 if (verbose)
143                     dataLogLn("failed to process unreachable op:", op);
144                 return false;
145             }
146         } else if (!parseExpression(static_cast<OpType>(op))) {
147             if (verbose)
148                 dataLogLn("failed to process op:", op);
149             return false;
150         }
151
152     }
153
154     RELEASE_ASSERT_NOT_REACHED();
155 }
156
157 template<typename Context>
158 bool FunctionParser<Context>::addReturn()
159 {
160     ExpressionList returnValues;
161     if (m_signature->returnType != Void) {
162         ExpressionType returnValue;
163         if (!popExpressionStack(returnValue))
164             return false;
165         returnValues.append(returnValue);
166     }
167
168     m_unreachableBlocks = 1;
169     return m_context.addReturn(returnValues);
170 }
171
172 template<typename Context>
173 template<OpType op>
174 bool FunctionParser<Context>::binaryCase()
175 {
176     ExpressionType right;
177     if (!popExpressionStack(right))
178         return false;
179
180     ExpressionType left;
181     if (!popExpressionStack(left))
182         return false;
183
184     ExpressionType result;
185     if (!m_context.template addOp<op>(left, right, result))
186         return false;
187     m_expressionStack.append(result);
188     return true;
189 }
190
191 template<typename Context>
192 template<OpType op>
193 bool FunctionParser<Context>::unaryCase()
194 {
195     ExpressionType value;
196     if (!popExpressionStack(value))
197         return false;
198
199     ExpressionType result;
200     if (!m_context.template addOp<op>(value, result))
201         return false;
202     m_expressionStack.append(result);
203     return true;
204 }
205
206 template<typename Context>
207 bool FunctionParser<Context>::parseExpression(OpType op)
208 {
209     switch (op) {
210 #define CREATE_CASE(name, id, b3op, inc) case OpType::name: return binaryCase<OpType::name>();
211     FOR_EACH_WASM_SIMPLE_BINARY_OP(CREATE_CASE)
212 #undef CREATE_CASE
213
214     case OpType::F32ConvertUI64: return unaryCase<OpType::F32ConvertUI64>();
215     case OpType::F64ConvertUI64: return unaryCase<OpType::F64ConvertUI64>();
216     case OpType::F32Nearest: return unaryCase<OpType::F32Nearest>();
217     case OpType::F64Nearest: return unaryCase<OpType::F64Nearest>();
218     case OpType::F32Trunc: return unaryCase<OpType::F32Trunc>();
219     case OpType::F64Trunc: return unaryCase<OpType::F64Trunc>();
220     case OpType::I32Ctz: return unaryCase<OpType::I32Ctz>();
221     case OpType::I64Ctz: return unaryCase<OpType::I64Ctz>();
222     case OpType::I32Popcnt: return unaryCase<OpType::I32Popcnt>();
223     case OpType::I64Popcnt: return unaryCase<OpType::I64Popcnt>();
224 #define CREATE_CASE(name, id, b3op, inc) case OpType::name: return unaryCase<OpType::name>();
225     FOR_EACH_WASM_SIMPLE_UNARY_OP(CREATE_CASE)
226 #undef CREATE_CASE
227
228     case OpType::Select: {
229         ExpressionType condition;
230         if (!popExpressionStack(condition))
231             return false;
232
233         ExpressionType zero;
234         if (!popExpressionStack(zero))
235             return false;
236
237         ExpressionType nonZero;
238         if (!popExpressionStack(nonZero))
239             return false;
240
241         ExpressionType result;
242         if (!m_context.addSelect(condition, nonZero, zero, result))
243             return false;
244
245         m_expressionStack.append(result);
246         return true;
247     }
248
249 #define CREATE_CASE(name, id, b3op, inc) case OpType::name:
250     FOR_EACH_WASM_MEMORY_LOAD_OP(CREATE_CASE) {
251         uint32_t alignment;
252         if (!parseVarUInt32(alignment))
253             return false;
254
255         uint32_t offset;
256         if (!parseVarUInt32(offset))
257             return false;
258
259         ExpressionType pointer;
260         if (!popExpressionStack(pointer))
261             return false;
262
263         ExpressionType result;
264         if (!m_context.load(static_cast<LoadOpType>(op), pointer, result, offset))
265             return false;
266         m_expressionStack.append(result);
267         return true;
268     }
269
270     FOR_EACH_WASM_MEMORY_STORE_OP(CREATE_CASE) {
271         uint32_t alignment;
272         if (!parseVarUInt32(alignment))
273             return false;
274
275         uint32_t offset;
276         if (!parseVarUInt32(offset))
277             return false;
278
279         ExpressionType value;
280         if (!popExpressionStack(value))
281             return false;
282
283         ExpressionType pointer;
284         if (!popExpressionStack(pointer))
285             return false;
286
287         return m_context.store(static_cast<StoreOpType>(op), pointer, value, offset);
288     }
289 #undef CREATE_CASE
290
291     case OpType::F32Const:
292     case OpType::I32Const: {
293         uint32_t constant;
294         if (!parseVarUInt32(constant))
295             return false;
296         m_expressionStack.append(m_context.addConstant(I32, constant));
297         return true;
298     }
299
300     case OpType::F64Const:
301     case OpType::I64Const: {
302         uint64_t constant;
303         if (!parseVarUInt64(constant))
304             return false;
305         m_expressionStack.append(m_context.addConstant(I64, constant));
306         return true;
307     }
308
309     case OpType::GetLocal: {
310         uint32_t index;
311         if (!parseVarUInt32(index))
312             return false;
313         ExpressionType result;
314         if (!m_context.getLocal(index, result))
315             return false;
316
317         m_expressionStack.append(result);
318         return true;
319     }
320
321     case OpType::SetLocal: {
322         uint32_t index;
323         if (!parseVarUInt32(index))
324             return false;
325         ExpressionType value;
326         if (!popExpressionStack(value))
327             return false;
328         return m_context.setLocal(index, value);
329     }
330
331     case OpType::Call: {
332         uint32_t functionIndex;
333         if (!parseVarUInt32(functionIndex))
334             return false;
335
336         if (functionIndex >= m_functions.size())
337             return false;
338
339         const FunctionInformation& info = m_functions[functionIndex];
340
341         if (info.signature->arguments.size() > m_expressionStack.size())
342             return false;
343
344         size_t firstArgumentIndex = m_expressionStack.size() - info.signature->arguments.size();
345         Vector<ExpressionType> args;
346         args.reserveInitialCapacity(info.signature->arguments.size());
347         for (unsigned i = firstArgumentIndex; i < m_expressionStack.size(); ++i)
348             args.append(m_expressionStack[i]);
349         m_expressionStack.shrink(firstArgumentIndex);
350
351         ExpressionType result = Context::emptyExpression;
352         if (!m_context.addCall(functionIndex, info, args, result))
353             return false;
354
355         if (result != Context::emptyExpression)
356             m_expressionStack.append(result);
357
358         return true;
359     }
360
361     case OpType::Block: {
362         Type inlineSignature;
363         if (!parseResultType(inlineSignature))
364             return false;
365
366         m_controlStack.append({ WTFMove(m_expressionStack), m_context.addBlock(inlineSignature) });
367         m_expressionStack = ExpressionList();
368         return true;
369     }
370
371     case OpType::Loop: {
372         Type inlineSignature;
373         if (!parseResultType(inlineSignature))
374             return false;
375
376         m_controlStack.append({ WTFMove(m_expressionStack), m_context.addLoop(inlineSignature) });
377         m_expressionStack = ExpressionList();
378         return true;
379     }
380
381     case OpType::If: {
382         Type inlineSignature;
383         if (!parseResultType(inlineSignature))
384             return false;
385
386         ExpressionType condition;
387         if (!popExpressionStack(condition))
388             return false;
389
390         ControlType control;
391         if (!m_context.addIf(condition, inlineSignature, control))
392             return false;
393
394         m_controlStack.append({ WTFMove(m_expressionStack), control });
395         m_expressionStack = ExpressionList();
396         return true;
397     }
398
399     case OpType::Else: {
400         if (!m_controlStack.size()) {
401             setErrorMessage("Attempted to use else block at the top-level of a function");
402             return false;
403         }
404
405         if (!m_context.addElse(m_controlStack.last().controlData, m_expressionStack))
406             return false;
407         m_expressionStack.shrink(0);
408         return true;
409     }
410
411     case OpType::Br:
412     case OpType::BrIf: {
413         uint32_t target;
414         if (!parseVarUInt32(target) || target >= m_controlStack.size())
415             return false;
416
417         ExpressionType condition = Context::emptyExpression;
418         if (op == OpType::BrIf) {
419             if (!popExpressionStack(condition))
420                 return false;
421         } else
422             m_unreachableBlocks = 1;
423
424         ControlType& data = m_controlStack[m_controlStack.size() - 1 - target].controlData;
425
426         return m_context.addBranch(data, condition, m_expressionStack);
427     }
428
429     case OpType::BrTable: {
430         uint32_t numberOfTargets;
431         if (!parseVarUInt32(numberOfTargets))
432             return false;
433
434         Vector<ControlType*> targets;
435         if (!targets.tryReserveCapacity(numberOfTargets))
436             return false;
437
438         for (uint32_t i = 0; i < numberOfTargets; ++i) {
439             uint32_t target;
440             if (!parseVarUInt32(target))
441                 return false;
442
443             if (target >= m_controlStack.size())
444                 return false;
445
446             targets.uncheckedAppend(&m_controlStack[m_controlStack.size() - 1 - target].controlData);
447         }
448
449         uint32_t defaultTarget;
450         if (!parseVarUInt32(defaultTarget))
451             return false;
452
453         if (defaultTarget >= m_controlStack.size())
454             return false;
455
456         ExpressionType condition;
457         if (!popExpressionStack(condition))
458             return false;
459         
460         if (!m_context.addSwitch(condition, targets, m_controlStack[m_controlStack.size() - 1 - defaultTarget].controlData, m_expressionStack))
461             return false;
462
463         m_unreachableBlocks = 1;
464         return true;
465     }
466
467     case OpType::Return: {
468         return addReturn();
469     }
470
471     case OpType::End: {
472         ControlEntry data = m_controlStack.takeLast();
473         // FIXME: This is a little weird in that it will modify the expressionStack for the result of the block.
474         // That's a little too effectful for me but I don't have a better API right now.
475         // see: https://bugs.webkit.org/show_bug.cgi?id=164353
476         if (!m_context.endBlock(data, m_expressionStack))
477             return false;
478         m_expressionStack.swap(data.enclosedExpressionStack);
479         return true;
480     }
481
482     case OpType::Unreachable: {
483         m_unreachableBlocks = 1;
484         return true;
485     }
486
487     default: {
488         // FIXME: Not yet implemented.
489         return false;
490     }
491     }
492
493     ASSERT_NOT_REACHED();
494 }
495
496 template<typename Context>
497 bool FunctionParser<Context>::parseUnreachableExpression(OpType op)
498 {
499     ASSERT(m_unreachableBlocks);
500     switch (op) {
501     case OpType::Else: {
502         if (m_unreachableBlocks > 1)
503             return true;
504
505         ControlEntry& data = m_controlStack.last();
506         m_unreachableBlocks = 0;
507         if (!m_context.addElseToUnreachable(data.controlData))
508             return false;
509         m_expressionStack.shrink(0);
510         return true;
511     }
512
513     case OpType::End: {
514         if (m_unreachableBlocks == 1) {
515             ControlEntry data = m_controlStack.takeLast();
516             if (!m_context.addEndToUnreachable(data))
517                 return false;
518             m_expressionStack.swap(data.enclosedExpressionStack);
519         }
520         m_unreachableBlocks--;
521         return true;
522     }
523
524     case OpType::Loop:
525     case OpType::If:
526     case OpType::Block: {
527         m_unreachableBlocks++;
528         return true;
529     }
530
531     // two immediate cases
532     case OpType::Br:
533     case OpType::BrIf: {
534         uint32_t unused;
535         if (!parseVarUInt32(unused))
536             return false;
537         return parseVarUInt32(unused);
538     }
539
540     // one immediate cases
541     case OpType::F32Const:
542     case OpType::I32Const:
543     case OpType::F64Const:
544     case OpType::I64Const:
545     case OpType::SetLocal:
546     case OpType::GetLocal: {
547         uint32_t unused;
548         return parseVarUInt32(unused);
549     }
550
551     default:
552         break;
553     }
554     return true;
555 }
556
557 template<typename Context>
558 bool FunctionParser<Context>::popExpressionStack(ExpressionType& result)
559 {
560     if (m_expressionStack.size()) {
561         result = m_expressionStack.takeLast();
562         return true;
563     }
564
565     setErrorMessage("Attempted to use a stack value when none existed");
566     return false;
567 }
568
569 } } // namespace JSC::Wasm
570
571 #endif // ENABLE(WEBASSEMBLY)