Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1 | // Copyright 2015 the V8 project authors. All rights reserved. |
| 2 | // Use of this source code is governed by a BSD-style license that can be |
| 3 | // found in the LICENSE file. |
| 4 | |
| 5 | #ifndef V8_WASM_AST_DECODER_H_ |
| 6 | #define V8_WASM_AST_DECODER_H_ |
| 7 | |
| 8 | #include "src/signature.h" |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 9 | #include "src/wasm/decoder.h" |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 10 | #include "src/wasm/wasm-opcodes.h" |
| 11 | #include "src/wasm/wasm-result.h" |
| 12 | |
| 13 | namespace v8 { |
| 14 | namespace internal { |
| 15 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 16 | class BitVector; // forward declaration |
| 17 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 18 | namespace compiler { // external declarations from compiler. |
| 19 | class WasmGraphBuilder; |
| 20 | } |
| 21 | |
| 22 | namespace wasm { |
| 23 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 24 | // Helpers for decoding different kinds of operands which follow bytecodes. |
| 25 | struct LocalIndexOperand { |
| 26 | uint32_t index; |
| 27 | LocalType type; |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 28 | unsigned length; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 29 | |
| 30 | inline LocalIndexOperand(Decoder* decoder, const byte* pc) { |
| 31 | index = decoder->checked_read_u32v(pc, 1, &length, "local index"); |
| 32 | type = kAstStmt; |
| 33 | } |
| 34 | }; |
| 35 | |
| 36 | struct ImmI8Operand { |
| 37 | int8_t value; |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 38 | unsigned length; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 39 | inline ImmI8Operand(Decoder* decoder, const byte* pc) { |
| 40 | value = bit_cast<int8_t>(decoder->checked_read_u8(pc, 1, "immi8")); |
| 41 | length = 1; |
| 42 | } |
| 43 | }; |
| 44 | |
| 45 | struct ImmI32Operand { |
| 46 | int32_t value; |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 47 | unsigned length; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 48 | inline ImmI32Operand(Decoder* decoder, const byte* pc) { |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 49 | value = decoder->checked_read_i32v(pc, 1, &length, "immi32"); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 50 | } |
| 51 | }; |
| 52 | |
| 53 | struct ImmI64Operand { |
| 54 | int64_t value; |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 55 | unsigned length; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 56 | inline ImmI64Operand(Decoder* decoder, const byte* pc) { |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 57 | value = decoder->checked_read_i64v(pc, 1, &length, "immi64"); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 58 | } |
| 59 | }; |
| 60 | |
| 61 | struct ImmF32Operand { |
| 62 | float value; |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 63 | unsigned length; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 64 | inline ImmF32Operand(Decoder* decoder, const byte* pc) { |
| 65 | value = bit_cast<float>(decoder->checked_read_u32(pc, 1, "immf32")); |
| 66 | length = 4; |
| 67 | } |
| 68 | }; |
| 69 | |
| 70 | struct ImmF64Operand { |
| 71 | double value; |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 72 | unsigned length; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 73 | inline ImmF64Operand(Decoder* decoder, const byte* pc) { |
| 74 | value = bit_cast<double>(decoder->checked_read_u64(pc, 1, "immf64")); |
| 75 | length = 8; |
| 76 | } |
| 77 | }; |
| 78 | |
| 79 | struct GlobalIndexOperand { |
| 80 | uint32_t index; |
| 81 | LocalType type; |
| 82 | MachineType machine_type; |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 83 | unsigned length; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 84 | |
| 85 | inline GlobalIndexOperand(Decoder* decoder, const byte* pc) { |
| 86 | index = decoder->checked_read_u32v(pc, 1, &length, "global index"); |
| 87 | type = kAstStmt; |
| 88 | machine_type = MachineType::None(); |
| 89 | } |
| 90 | }; |
| 91 | |
Ben Murdoch | c561043 | 2016-08-08 18:44:38 +0100 | [diff] [blame] | 92 | struct Control; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 93 | struct BreakDepthOperand { |
Ben Murdoch | c561043 | 2016-08-08 18:44:38 +0100 | [diff] [blame] | 94 | uint32_t arity; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 95 | uint32_t depth; |
Ben Murdoch | c561043 | 2016-08-08 18:44:38 +0100 | [diff] [blame] | 96 | Control* target; |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 97 | unsigned length; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 98 | inline BreakDepthOperand(Decoder* decoder, const byte* pc) { |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 99 | unsigned len1 = 0; |
| 100 | unsigned len2 = 0; |
Ben Murdoch | c561043 | 2016-08-08 18:44:38 +0100 | [diff] [blame] | 101 | arity = decoder->checked_read_u32v(pc, 1, &len1, "argument count"); |
| 102 | depth = decoder->checked_read_u32v(pc, 1 + len1, &len2, "break depth"); |
| 103 | length = len1 + len2; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 104 | target = nullptr; |
| 105 | } |
| 106 | }; |
| 107 | |
Ben Murdoch | c561043 | 2016-08-08 18:44:38 +0100 | [diff] [blame] | 108 | struct CallIndirectOperand { |
| 109 | uint32_t arity; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 110 | uint32_t index; |
| 111 | FunctionSig* sig; |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 112 | unsigned length; |
Ben Murdoch | c561043 | 2016-08-08 18:44:38 +0100 | [diff] [blame] | 113 | inline CallIndirectOperand(Decoder* decoder, const byte* pc) { |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 114 | unsigned len1 = 0; |
| 115 | unsigned len2 = 0; |
Ben Murdoch | c561043 | 2016-08-08 18:44:38 +0100 | [diff] [blame] | 116 | arity = decoder->checked_read_u32v(pc, 1, &len1, "argument count"); |
| 117 | index = decoder->checked_read_u32v(pc, 1 + len1, &len2, "signature index"); |
| 118 | length = len1 + len2; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 119 | sig = nullptr; |
| 120 | } |
| 121 | }; |
| 122 | |
Ben Murdoch | c561043 | 2016-08-08 18:44:38 +0100 | [diff] [blame] | 123 | struct CallFunctionOperand { |
| 124 | uint32_t arity; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 125 | uint32_t index; |
| 126 | FunctionSig* sig; |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 127 | unsigned length; |
Ben Murdoch | c561043 | 2016-08-08 18:44:38 +0100 | [diff] [blame] | 128 | inline CallFunctionOperand(Decoder* decoder, const byte* pc) { |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 129 | unsigned len1 = 0; |
| 130 | unsigned len2 = 0; |
Ben Murdoch | c561043 | 2016-08-08 18:44:38 +0100 | [diff] [blame] | 131 | arity = decoder->checked_read_u32v(pc, 1, &len1, "argument count"); |
| 132 | index = decoder->checked_read_u32v(pc, 1 + len1, &len2, "function index"); |
| 133 | length = len1 + len2; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 134 | sig = nullptr; |
| 135 | } |
| 136 | }; |
| 137 | |
Ben Murdoch | c561043 | 2016-08-08 18:44:38 +0100 | [diff] [blame] | 138 | struct CallImportOperand { |
| 139 | uint32_t arity; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 140 | uint32_t index; |
| 141 | FunctionSig* sig; |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 142 | unsigned length; |
Ben Murdoch | c561043 | 2016-08-08 18:44:38 +0100 | [diff] [blame] | 143 | inline CallImportOperand(Decoder* decoder, const byte* pc) { |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 144 | unsigned len1 = 0; |
| 145 | unsigned len2 = 0; |
Ben Murdoch | c561043 | 2016-08-08 18:44:38 +0100 | [diff] [blame] | 146 | arity = decoder->checked_read_u32v(pc, 1, &len1, "argument count"); |
| 147 | index = decoder->checked_read_u32v(pc, 1 + len1, &len2, "import index"); |
| 148 | length = len1 + len2; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 149 | sig = nullptr; |
| 150 | } |
| 151 | }; |
| 152 | |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 153 | struct BranchTableOperand { |
Ben Murdoch | c561043 | 2016-08-08 18:44:38 +0100 | [diff] [blame] | 154 | uint32_t arity; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 155 | uint32_t table_count; |
| 156 | const byte* table; |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 157 | unsigned length; |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 158 | inline BranchTableOperand(Decoder* decoder, const byte* pc) { |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 159 | unsigned len1 = 0; |
| 160 | unsigned len2 = 0; |
Ben Murdoch | c561043 | 2016-08-08 18:44:38 +0100 | [diff] [blame] | 161 | arity = decoder->checked_read_u32v(pc, 1, &len1, "argument count"); |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 162 | table_count = |
Ben Murdoch | c561043 | 2016-08-08 18:44:38 +0100 | [diff] [blame] | 163 | decoder->checked_read_u32v(pc, 1 + len1, &len2, "table count"); |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 164 | if (table_count > (UINT_MAX / sizeof(uint32_t)) - 1 || |
| 165 | len1 + len2 > UINT_MAX - (table_count + 1) * sizeof(uint32_t)) { |
| 166 | decoder->error(pc, "branch table size overflow"); |
| 167 | } |
Ben Murdoch | c561043 | 2016-08-08 18:44:38 +0100 | [diff] [blame] | 168 | length = len1 + len2 + (table_count + 1) * sizeof(uint32_t); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 169 | |
Ben Murdoch | c561043 | 2016-08-08 18:44:38 +0100 | [diff] [blame] | 170 | uint32_t table_start = 1 + len1 + len2; |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 171 | if (decoder->check(pc, table_start, (table_count + 1) * sizeof(uint32_t), |
| 172 | "expected <table entries>")) { |
| 173 | table = pc + table_start; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 174 | } else { |
| 175 | table = nullptr; |
| 176 | } |
| 177 | } |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 178 | inline uint32_t read_entry(Decoder* decoder, unsigned i) { |
| 179 | DCHECK(i <= table_count); |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 180 | return table ? decoder->read_u32(table + i * sizeof(uint32_t)) : 0; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 181 | } |
| 182 | }; |
| 183 | |
| 184 | struct MemoryAccessOperand { |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 185 | uint32_t alignment; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 186 | uint32_t offset; |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 187 | unsigned length; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 188 | inline MemoryAccessOperand(Decoder* decoder, const byte* pc) { |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 189 | unsigned alignment_length; |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 190 | alignment = |
| 191 | decoder->checked_read_u32v(pc, 1, &alignment_length, "alignment"); |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 192 | unsigned offset_length; |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 193 | offset = decoder->checked_read_u32v(pc, 1 + alignment_length, |
| 194 | &offset_length, "offset"); |
| 195 | length = alignment_length + offset_length; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 196 | } |
| 197 | }; |
| 198 | |
Ben Murdoch | c561043 | 2016-08-08 18:44:38 +0100 | [diff] [blame] | 199 | struct ReturnArityOperand { |
| 200 | uint32_t arity; |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 201 | unsigned length; |
Ben Murdoch | c561043 | 2016-08-08 18:44:38 +0100 | [diff] [blame] | 202 | |
| 203 | inline ReturnArityOperand(Decoder* decoder, const byte* pc) { |
| 204 | arity = decoder->checked_read_u32v(pc, 1, &length, "return count"); |
| 205 | } |
| 206 | }; |
| 207 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 208 | typedef compiler::WasmGraphBuilder TFBuilder; |
| 209 | struct ModuleEnv; // forward declaration of module interface. |
| 210 | |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 211 | // All of the various data structures necessary to decode a function body. |
| 212 | struct FunctionBody { |
| 213 | ModuleEnv* module; // module environment |
| 214 | FunctionSig* sig; // function signature |
| 215 | const byte* base; // base of the module bytes, for error reporting |
| 216 | const byte* start; // start of the function body |
| 217 | const byte* end; // end of the function body |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 218 | }; |
| 219 | |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 220 | static inline FunctionBody FunctionBodyForTesting(const byte* start, |
| 221 | const byte* end) { |
| 222 | return {nullptr, nullptr, start, start, end}; |
| 223 | } |
| 224 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 225 | struct Tree; |
| 226 | typedef Result<Tree*> TreeResult; |
| 227 | |
| 228 | std::ostream& operator<<(std::ostream& os, const Tree& tree); |
| 229 | |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 230 | TreeResult VerifyWasmCode(base::AccountingAllocator* allocator, |
| 231 | FunctionBody& body); |
| 232 | TreeResult BuildTFGraph(base::AccountingAllocator* allocator, |
| 233 | TFBuilder* builder, FunctionBody& body); |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 234 | bool PrintAst(base::AccountingAllocator* allocator, const FunctionBody& body, |
| 235 | std::ostream& os, |
| 236 | std::vector<std::tuple<uint32_t, int, int>>* offset_table); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 237 | |
Ben Murdoch | c561043 | 2016-08-08 18:44:38 +0100 | [diff] [blame] | 238 | // A simplified form of AST printing, e.g. from a debugger. |
| 239 | void PrintAstForDebugging(const byte* start, const byte* end); |
| 240 | |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 241 | inline TreeResult VerifyWasmCode(base::AccountingAllocator* allocator, |
| 242 | ModuleEnv* module, FunctionSig* sig, |
| 243 | const byte* start, const byte* end) { |
| 244 | FunctionBody body = {module, sig, nullptr, start, end}; |
| 245 | return VerifyWasmCode(allocator, body); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 246 | } |
| 247 | |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 248 | inline TreeResult BuildTFGraph(base::AccountingAllocator* allocator, |
| 249 | TFBuilder* builder, ModuleEnv* module, |
| 250 | FunctionSig* sig, const byte* start, |
| 251 | const byte* end) { |
| 252 | FunctionBody body = {module, sig, nullptr, start, end}; |
| 253 | return BuildTFGraph(allocator, builder, body); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 254 | } |
| 255 | |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 256 | struct AstLocalDecls { |
| 257 | // The size of the encoded declarations. |
| 258 | uint32_t decls_encoded_size; // size of encoded declarations |
| 259 | |
| 260 | // Total number of locals. |
| 261 | uint32_t total_local_count; |
| 262 | |
| 263 | // List of {local type, count} pairs. |
| 264 | ZoneVector<std::pair<LocalType, uint32_t>> local_types; |
| 265 | |
| 266 | // Constructor initializes the vector. |
| 267 | explicit AstLocalDecls(Zone* zone) |
| 268 | : decls_encoded_size(0), total_local_count(0), local_types(zone) {} |
| 269 | }; |
| 270 | |
| 271 | bool DecodeLocalDecls(AstLocalDecls& decls, const byte* start, const byte* end); |
| 272 | BitVector* AnalyzeLoopAssignmentForTesting(Zone* zone, size_t num_locals, |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 273 | const byte* start, const byte* end); |
| 274 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 275 | // Computes the length of the opcode at the given address. |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 276 | unsigned OpcodeLength(const byte* pc, const byte* end); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 277 | |
| 278 | // Computes the arity (number of sub-nodes) of the opcode at the given address. |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 279 | unsigned OpcodeArity(const byte* pc, const byte* end); |
Ben Murdoch | c561043 | 2016-08-08 18:44:38 +0100 | [diff] [blame] | 280 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 281 | } // namespace wasm |
| 282 | } // namespace internal |
| 283 | } // namespace v8 |
| 284 | |
| 285 | #endif // V8_WASM_AST_DECODER_H_ |