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