1 //===- subzero/src/WasmTranslator.cpp - WASM to Subzero Translation -------===//
2 //
3 // The Subzero Code Generator
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 ///
10 /// \file
11 /// \brief Defines a driver for translating Wasm bitcode into PNaCl bitcode.
12 ///
13 /// The translator uses V8's WebAssembly decoder to handle the binary Wasm
14 /// format but replaces the usual TurboFan builder with a new PNaCl builder.
15 ///
16 //===----------------------------------------------------------------------===//
17
18 #if ALLOW_WASM
19
20 #include "WasmTranslator.h"
21
22 #ifdef __clang__
23 #pragma clang diagnostic push
24 #pragma clang diagnostic ignored "-Wunused-parameter"
25 #pragma clang diagnostic ignored "-Wcovered-switch-default"
26 #endif // __clang__
27 #if defined(__GNUC__) && !defined(__clang__)
28 #pragma GCC diagnostic push
29 #pragma GCC diagnostic ignored "-Wunused-but-set-variable"
30 #endif // defined(__GNUC__) && !defined(__clang__)
31
32 #include "src/wasm/module-decoder.h"
33 #include "src/wasm/wasm-opcodes.h"
34 #include "src/zone.h"
35
36 #include "src/bit-vector.h"
37
38 #include "src/wasm/ast-decoder-impl.h"
39
40 #ifdef __clang__
41 #pragma clang diagnostic pop
42 #endif // __clang__
43 #if defined(__GNUC__) && !defined(__clang__)
44 #pragma GCC diagnostic pop
45 #endif // defined(__GNUC__) && !defined(__clang__)
46
47 #include "IceCfgNode.h"
48 #include "IceGlobalInits.h"
49
50 using namespace std;
51 using namespace Ice;
52 using namespace v8::internal;
53 using namespace v8::internal::wasm;
54 using v8::internal::wasm::DecodeWasmModule;
55
56 #undef LOG
57 #define LOG(Expr) log([&](Ostream & out) { Expr; })
58
59 namespace {
60 // 64KB
61 const uint32_t WASM_PAGE_SIZE = 64 << 10;
62
toStdString(WasmName Name)63 std::string toStdString(WasmName Name) {
64 return std::string(Name.name, Name.length);
65 }
66
toIceType(wasm::LocalType Type)67 Ice::Type toIceType(wasm::LocalType Type) {
68 switch (Type) {
69 case MachineRepresentation::kNone:
70 llvm::report_fatal_error("kNone type not supported");
71 case MachineRepresentation::kBit:
72 return IceType_i1;
73 case MachineRepresentation::kWord8:
74 return IceType_i8;
75 case MachineRepresentation::kWord16:
76 return IceType_i16;
77 case MachineRepresentation::kWord32:
78 return IceType_i32;
79 case MachineRepresentation::kWord64:
80 return IceType_i64;
81 case MachineRepresentation::kFloat32:
82 return IceType_f32;
83 case MachineRepresentation::kFloat64:
84 return IceType_f64;
85 case MachineRepresentation::kSimd128:
86 llvm::report_fatal_error("ambiguous SIMD type");
87 case MachineRepresentation::kTagged:
88 llvm::report_fatal_error("kTagged type not supported");
89 }
90 llvm::report_fatal_error("unexpected type");
91 }
92
toIceType(v8::internal::MachineType Type)93 Ice::Type toIceType(v8::internal::MachineType Type) {
94 // TODO (eholk): reorder these based on expected call frequency.
95 if (Type == MachineType::Int32()) {
96 return IceType_i32;
97 }
98 if (Type == MachineType::Uint32()) {
99 return IceType_i32;
100 }
101 if (Type == MachineType::Int8()) {
102 return IceType_i8;
103 }
104 if (Type == MachineType::Uint8()) {
105 return IceType_i8;
106 }
107 if (Type == MachineType::Int16()) {
108 return IceType_i16;
109 }
110 if (Type == MachineType::Uint16()) {
111 return IceType_i16;
112 }
113 if (Type == MachineType::Int64()) {
114 return IceType_i64;
115 }
116 if (Type == MachineType::Uint64()) {
117 return IceType_i64;
118 }
119 if (Type == MachineType::Float32()) {
120 return IceType_f32;
121 }
122 if (Type == MachineType::Float64()) {
123 return IceType_f64;
124 }
125 llvm::report_fatal_error("Unsupported MachineType");
126 }
127
fnNameFromId(uint32_t Id)128 std::string fnNameFromId(uint32_t Id) {
129 return std::string("fn") + to_string(Id);
130 }
131
getFunctionName(const WasmModule * Module,uint32_t func_index)132 std::string getFunctionName(const WasmModule *Module, uint32_t func_index) {
133 // Try to find the function name in the export table
134 for (const auto Export : Module->export_table) {
135 if (Export.func_index == func_index) {
136 return "__szwasm_" + toStdString(Module->GetName(Export.name_offset,
137 Export.name_length));
138 }
139 }
140 return fnNameFromId(func_index);
141 }
142
143 } // end of anonymous namespace
144
145 /// This class wraps either an Operand or a CfgNode.
146 ///
147 /// Turbofan's sea of nodes representation only has nodes for values, control
148 /// flow, etc. In Subzero these concepts are all separate. This class lets V8's
149 /// Wasm decoder treat Subzero objects as though they are all the same.
150 class OperandNode {
151 static constexpr uintptr_t NODE_FLAG = 1;
152 static constexpr uintptr_t UNDEF_PTR = (uintptr_t)-1;
153
154 uintptr_t Data = UNDEF_PTR;
155
156 public:
157 OperandNode() = default;
OperandNode(Operand * Operand)158 explicit OperandNode(Operand *Operand)
159 : Data(reinterpret_cast<uintptr_t>(Operand)) {}
OperandNode(CfgNode * Node)160 explicit OperandNode(CfgNode *Node)
161 : Data(reinterpret_cast<uintptr_t>(Node) | NODE_FLAG) {}
OperandNode(nullptr_t)162 explicit OperandNode(nullptr_t) : Data(UNDEF_PTR) {}
163
operator Operand*() const164 operator Operand *() const {
165 if (UNDEF_PTR == Data) {
166 return nullptr;
167 }
168 if (!isOperand()) {
169 llvm::report_fatal_error("This OperandNode is not an Operand");
170 }
171 return reinterpret_cast<Operand *>(Data);
172 }
173
operator CfgNode*() const174 operator CfgNode *() const {
175 if (UNDEF_PTR == Data) {
176 return nullptr;
177 }
178 if (!isCfgNode()) {
179 llvm::report_fatal_error("This OperandNode is not a CfgNode");
180 }
181 return reinterpret_cast<CfgNode *>(Data & ~NODE_FLAG);
182 }
183
operator bool() const184 explicit operator bool() const { return (Data != UNDEF_PTR) && Data; }
operator ==(const OperandNode & Rhs) const185 bool operator==(const OperandNode &Rhs) const {
186 return (Data == Rhs.Data) ||
187 (UNDEF_PTR == Data && (Rhs.Data == 0 || Rhs.Data == NODE_FLAG)) ||
188 (UNDEF_PTR == Rhs.Data && (Data == 0 || Data == NODE_FLAG));
189 }
operator !=(const OperandNode & Rhs) const190 bool operator!=(const OperandNode &Rhs) const { return !(*this == Rhs); }
191
isOperand() const192 bool isOperand() const { return (Data != UNDEF_PTR) && !(Data & NODE_FLAG); }
isCfgNode() const193 bool isCfgNode() const { return (Data != UNDEF_PTR) && (Data & NODE_FLAG); }
194
toOperand() const195 Operand *toOperand() const { return static_cast<Operand *>(*this); }
196
toCfgNode() const197 CfgNode *toCfgNode() const { return static_cast<CfgNode *>(*this); }
198 };
199
operator <<(Ostream & Out,const OperandNode & Op)200 Ostream &operator<<(Ostream &Out, const OperandNode &Op) {
201 if (Op.isOperand()) {
202 const auto *Oper = Op.toOperand();
203 Out << "(Operand*)" << Oper;
204 if (Oper) {
205 Out << "::" << Oper->getType();
206 }
207 } else if (Op.isCfgNode()) {
208 Out << "(CfgNode*)" << Op.toCfgNode();
209 } else {
210 Out << "nullptr";
211 }
212 return Out;
213 }
214
isComparison(wasm::WasmOpcode Opcode)215 bool isComparison(wasm::WasmOpcode Opcode) {
216 switch (Opcode) {
217 case kExprI32Ne:
218 case kExprI64Ne:
219 case kExprI32Eq:
220 case kExprI64Eq:
221 case kExprI32LtS:
222 case kExprI64LtS:
223 case kExprI32LtU:
224 case kExprI64LtU:
225 case kExprI32GeS:
226 case kExprI64GeS:
227 case kExprI32GtS:
228 case kExprI64GtS:
229 case kExprI32GtU:
230 case kExprI64GtU:
231 case kExprF32Eq:
232 case kExprF64Eq:
233 case kExprF32Ne:
234 case kExprF64Ne:
235 case kExprF32Le:
236 case kExprF64Le:
237 case kExprF32Lt:
238 case kExprF64Lt:
239 case kExprF32Ge:
240 case kExprF64Ge:
241 case kExprF32Gt:
242 case kExprF64Gt:
243 case kExprI32LeS:
244 case kExprI64LeS:
245 case kExprI32GeU:
246 case kExprI64GeU:
247 case kExprI32LeU:
248 case kExprI64LeU:
249 return true;
250 default:
251 return false;
252 }
253 }
254
255 class IceBuilder {
256 using Node = OperandNode;
257 using Variable = Ice::Variable;
258
259 IceBuilder() = delete;
260 IceBuilder(const IceBuilder &) = delete;
261 IceBuilder &operator=(const IceBuilder &) = delete;
262
263 public:
IceBuilder(class Cfg * Func)264 explicit IceBuilder(class Cfg *Func)
265 : ControlPtr(nullptr), Func(Func), Ctx(Func->getContext()) {}
266
267 /// Allocates a buffer of Nodes for use by V8.
Buffer(size_t Count)268 Node *Buffer(size_t Count) {
269 LOG(out << "Buffer(" << Count << ")\n");
270 return Func->allocateArrayOf<Node>(Count);
271 }
272
Error()273 Node Error() { llvm::report_fatal_error("Error"); }
Start(uint32_t Params)274 Node Start(uint32_t Params) {
275 LOG(out << "Start(" << Params << ") = ");
276 auto *Entry = Func->getEntryNode();
277 assert(Entry);
278 LOG(out << Node(Entry) << "\n");
279
280 // Load the WasmMemory address to make it available everywhere else in the
281 // function.
282 auto *WasmMemoryPtr =
283 Ctx->getConstantExternSym(Ctx->getGlobalString("WASM_MEMORY"));
284 assert(WasmMemory == nullptr);
285 auto *WasmMemoryV = makeVariable(getPointerType());
286 Entry->appendInst(InstLoad::create(Func, WasmMemoryV, WasmMemoryPtr));
287 WasmMemory = WasmMemoryV;
288
289 return OperandNode(Entry);
290 }
Param(uint32_t Index,wasm::LocalType Type)291 Node Param(uint32_t Index, wasm::LocalType Type) {
292 LOG(out << "Param(" << Index << ") = ");
293 auto *Arg = makeVariable(toIceType(Type));
294 assert(Index == NextArg);
295 Func->addArg(Arg);
296 ++NextArg;
297 LOG(out << Node(Arg) << "\n");
298 return OperandNode(Arg);
299 }
Loop(CfgNode * Entry)300 Node Loop(CfgNode *Entry) {
301 auto *Loop = Func->makeNode();
302 LOG(out << "Loop(" << Entry << ") = " << Loop << "\n");
303 Entry->appendInst(InstBr::create(Func, Loop));
304 return OperandNode(Loop);
305 }
Terminate(Node Effect,Node Control)306 void Terminate(Node Effect, Node Control) {
307 // TODO(eholk): this is almost certainly wrong
308 LOG(out << "Terminate(" << Effect << ", " << Control << ")"
309 << "\n");
310 }
Merge(uint32_t Count,Node * Controls)311 Node Merge(uint32_t Count, Node *Controls) {
312 LOG(out << "Merge(" << Count);
313 for (uint32_t i = 0; i < Count; ++i) {
314 LOG(out << ", " << Controls[i]);
315 }
316 LOG(out << ") = ");
317
318 auto *MergedNode = Func->makeNode();
319
320 for (uint32_t i = 0; i < Count; ++i) {
321 CfgNode *Control = Controls[i];
322 Control->appendInst(InstBr::create(Func, MergedNode));
323 }
324 LOG(out << (OperandNode)MergedNode << "\n");
325 return OperandNode(MergedNode);
326 }
Phi(wasm::LocalType,uint32_t Count,Node * Vals,Node Control)327 Node Phi(wasm::LocalType, uint32_t Count, Node *Vals, Node Control) {
328 LOG(out << "Phi(" << Count << ", " << Control);
329 for (uint32_t i = 0; i < Count; ++i) {
330 LOG(out << ", " << Vals[i]);
331 }
332 LOG(out << ") = ");
333
334 const auto &InEdges = Control.toCfgNode()->getInEdges();
335 assert(Count == InEdges.size());
336
337 assert(Count > 0);
338
339 auto *Dest = makeVariable(Vals[0].toOperand()->getType(), Control);
340
341 // Multiply by 200 in case more things get added later.
342
343 // TODO(eholk): find a better way besides multiplying by some arbitrary
344 // constant.
345 auto *Phi = InstPhi::create(Func, Count * 200, Dest);
346 for (uint32_t i = 0; i < Count; ++i) {
347 auto *Op = Vals[i].toOperand();
348 assert(Op);
349 Phi->addArgument(Op, InEdges[i]);
350 }
351 setDefiningInst(Dest, Phi);
352 Control.toCfgNode()->appendInst(Phi);
353 LOG(out << Node(Dest) << "\n");
354 return OperandNode(Dest);
355 }
EffectPhi(uint32_t Count,Node * Effects,Node Control)356 Node EffectPhi(uint32_t Count, Node *Effects, Node Control) {
357 // TODO(eholk): this function is almost certainly wrong.
358 LOG(out << "EffectPhi(" << Count << ", " << Control << "):\n");
359 for (uint32_t i = 0; i < Count; ++i) {
360 LOG(out << " " << Effects[i] << "\n");
361 }
362 return OperandNode(nullptr);
363 }
Int32Constant(int32_t Value)364 Node Int32Constant(int32_t Value) {
365 LOG(out << "Int32Constant(" << Value << ") = ");
366 auto *Const = Ctx->getConstantInt32(Value);
367 assert(Const);
368 assert(Control());
369 LOG(out << Node(Const) << "\n");
370 return OperandNode(Const);
371 }
Int64Constant(int64_t Value)372 Node Int64Constant(int64_t Value) {
373 LOG(out << "Int64Constant(" << Value << ") = ");
374 auto *Const = Ctx->getConstantInt64(Value);
375 assert(Const);
376 LOG(out << Node(Const) << "\n");
377 return OperandNode(Const);
378 }
Float32Constant(float Value)379 Node Float32Constant(float Value) {
380 LOG(out << "Float32Constant(" << Value << ") = ");
381 auto *Const = Ctx->getConstantFloat(Value);
382 assert(Const);
383 LOG(out << Node(Const) << "\n");
384 return OperandNode(Const);
385 }
Float64Constant(double Value)386 Node Float64Constant(double Value) {
387 LOG(out << "Float64Constant(" << Value << ") = ");
388 auto *Const = Ctx->getConstantDouble(Value);
389 assert(Const);
390 LOG(out << Node(Const) << "\n");
391 return OperandNode(Const);
392 }
Binop(wasm::WasmOpcode Opcode,Node Left,Node Right)393 Node Binop(wasm::WasmOpcode Opcode, Node Left, Node Right) {
394 LOG(out << "Binop(" << WasmOpcodes::OpcodeName(Opcode) << ", " << Left
395 << ", " << Right << ") = ");
396 BooleanVariable *BoolDest = nullptr;
397 Variable *Dest = nullptr;
398 if (isComparison(Opcode)) {
399 BoolDest = makeVariable<BooleanVariable>(IceType_i32);
400 Dest = BoolDest;
401 } else {
402 Dest = makeVariable(Left.toOperand()->getType());
403 }
404 switch (Opcode) {
405 case kExprI32Add:
406 case kExprI64Add:
407 Control()->appendInst(
408 InstArithmetic::create(Func, InstArithmetic::Add, Dest, Left, Right));
409 break;
410 case kExprF32Add:
411 case kExprF64Add:
412 Control()->appendInst(InstArithmetic::create(Func, InstArithmetic::Fadd,
413 Dest, Left, Right));
414 break;
415 case kExprI32Sub:
416 case kExprI64Sub:
417 Control()->appendInst(
418 InstArithmetic::create(Func, InstArithmetic::Sub, Dest, Left, Right));
419 break;
420 case kExprF32Sub:
421 case kExprF64Sub:
422 Control()->appendInst(InstArithmetic::create(Func, InstArithmetic::Fsub,
423 Dest, Left, Right));
424 break;
425 case kExprI32Mul:
426 case kExprI64Mul:
427 Control()->appendInst(
428 InstArithmetic::create(Func, InstArithmetic::Mul, Dest, Left, Right));
429 break;
430 case kExprF32Mul:
431 case kExprF64Mul:
432 Control()->appendInst(InstArithmetic::create(Func, InstArithmetic::Fmul,
433 Dest, Left, Right));
434 break;
435 case kExprI32DivS:
436 case kExprI64DivS:
437 Control()->appendInst(InstArithmetic::create(Func, InstArithmetic::Sdiv,
438 Dest, Left, Right));
439 break;
440 case kExprI32DivU:
441 case kExprI64DivU:
442 Control()->appendInst(InstArithmetic::create(Func, InstArithmetic::Udiv,
443 Dest, Left, Right));
444 break;
445 case kExprF32Div:
446 case kExprF64Div:
447 Control()->appendInst(InstArithmetic::create(Func, InstArithmetic::Fdiv,
448 Dest, Left, Right));
449 break;
450 case kExprI32RemU:
451 case kExprI64RemU:
452 Control()->appendInst(InstArithmetic::create(Func, InstArithmetic::Urem,
453 Dest, Left, Right));
454 break;
455 case kExprI32RemS:
456 case kExprI64RemS:
457 Control()->appendInst(InstArithmetic::create(Func, InstArithmetic::Srem,
458 Dest, Left, Right));
459 break;
460 case kExprI32Ior:
461 case kExprI64Ior:
462 Control()->appendInst(
463 InstArithmetic::create(Func, InstArithmetic::Or, Dest, Left, Right));
464 break;
465 case kExprI32Xor:
466 case kExprI64Xor:
467 Control()->appendInst(
468 InstArithmetic::create(Func, InstArithmetic::Xor, Dest, Left, Right));
469 break;
470 case kExprI32Shl:
471 case kExprI64Shl:
472 Control()->appendInst(
473 InstArithmetic::create(Func, InstArithmetic::Shl, Dest, Left, Right));
474 break;
475 case kExprI32Rol:
476 case kExprI64Rol: {
477 // TODO(eholk): add rotate as an ICE instruction to make it easier to take
478 // advantage of hardware support.
479
480 const auto DestTy = Left.toOperand()->getType();
481 const SizeT BitCount = typeWidthInBytes(DestTy) * CHAR_BIT;
482
483 auto *Masked = makeVariable(DestTy);
484 auto *Bottom = makeVariable(DestTy);
485 auto *Top = makeVariable(DestTy);
486 Control()->appendInst(
487 InstArithmetic::create(Func, InstArithmetic::And, Masked, Right,
488 Ctx->getConstantInt(DestTy, BitCount - 1)));
489 Control()->appendInst(
490 InstArithmetic::create(Func, InstArithmetic::Shl, Top, Left, Masked));
491 auto *RotShift = makeVariable(DestTy);
492 Control()->appendInst(InstArithmetic::create(
493 Func, InstArithmetic::Sub, RotShift,
494 Ctx->getConstantInt(DestTy, BitCount), Masked));
495 Control()->appendInst(InstArithmetic::create(Func, InstArithmetic::Lshr,
496 Bottom, Left, RotShift));
497 Control()->appendInst(
498 InstArithmetic::create(Func, InstArithmetic::Or, Dest, Top, Bottom));
499 break;
500 }
501 case kExprI32Ror:
502 case kExprI64Ror: {
503 // TODO(eholk): add rotate as an ICE instruction to make it easier to take
504 // advantage of hardware support.
505
506 const auto DestTy = Left.toOperand()->getType();
507 const SizeT BitCount = typeWidthInBytes(DestTy) * CHAR_BIT;
508
509 auto *Masked = makeVariable(DestTy);
510 auto *Bottom = makeVariable(DestTy);
511 auto *Top = makeVariable(DestTy);
512 Control()->appendInst(
513 InstArithmetic::create(Func, InstArithmetic::And, Masked, Right,
514 Ctx->getConstantInt(DestTy, BitCount - 1)));
515 Control()->appendInst(InstArithmetic::create(Func, InstArithmetic::Lshr,
516 Top, Left, Masked));
517 auto *RotShift = makeVariable(DestTy);
518 Control()->appendInst(InstArithmetic::create(
519 Func, InstArithmetic::Sub, RotShift,
520 Ctx->getConstantInt(DestTy, BitCount), Masked));
521 Control()->appendInst(InstArithmetic::create(Func, InstArithmetic::Shl,
522 Bottom, Left, RotShift));
523 Control()->appendInst(
524 InstArithmetic::create(Func, InstArithmetic::Or, Dest, Top, Bottom));
525 break;
526 }
527 case kExprI32ShrU:
528 case kExprI64ShrU:
529 Control()->appendInst(InstArithmetic::create(Func, InstArithmetic::Lshr,
530 Dest, Left, Right));
531 break;
532 case kExprI32ShrS:
533 case kExprI64ShrS:
534 Control()->appendInst(InstArithmetic::create(Func, InstArithmetic::Ashr,
535 Dest, Left, Right));
536 break;
537 case kExprI32And:
538 case kExprI64And:
539 Control()->appendInst(
540 InstArithmetic::create(Func, InstArithmetic::And, Dest, Left, Right));
541 break;
542 case kExprI32Ne:
543 case kExprI64Ne: {
544 auto *TmpDest = makeVariable(IceType_i1);
545 Control()->appendInst(
546 InstIcmp::create(Func, InstIcmp::Ne, TmpDest, Left, Right));
547 BoolDest->setBoolSource(TmpDest);
548 Control()->appendInst(
549 InstCast::create(Func, InstCast::Zext, Dest, TmpDest));
550 break;
551 }
552 case kExprI32Eq:
553 case kExprI64Eq: {
554 auto *TmpDest = makeVariable(IceType_i1);
555 Control()->appendInst(
556 InstIcmp::create(Func, InstIcmp::Eq, TmpDest, Left, Right));
557 BoolDest->setBoolSource(TmpDest);
558 Control()->appendInst(
559 InstCast::create(Func, InstCast::Zext, Dest, TmpDest));
560 break;
561 }
562 case kExprI32LtS:
563 case kExprI64LtS: {
564 auto *TmpDest = makeVariable(IceType_i1);
565 Control()->appendInst(
566 InstIcmp::create(Func, InstIcmp::Slt, TmpDest, Left, Right));
567 BoolDest->setBoolSource(TmpDest);
568 Control()->appendInst(
569 InstCast::create(Func, InstCast::Zext, Dest, TmpDest));
570 break;
571 }
572 case kExprI32LeS:
573 case kExprI64LeS: {
574 auto *TmpDest = makeVariable(IceType_i1);
575 Control()->appendInst(
576 InstIcmp::create(Func, InstIcmp::Sle, TmpDest, Left, Right));
577 BoolDest->setBoolSource(TmpDest);
578 Control()->appendInst(
579 InstCast::create(Func, InstCast::Zext, Dest, TmpDest));
580 break;
581 }
582 case kExprI32GeU:
583 case kExprI64GeU: {
584 auto *TmpDest = makeVariable(IceType_i1);
585 Control()->appendInst(
586 InstIcmp::create(Func, InstIcmp::Uge, TmpDest, Left, Right));
587 BoolDest->setBoolSource(TmpDest);
588 Control()->appendInst(
589 InstCast::create(Func, InstCast::Zext, Dest, TmpDest));
590 break;
591 }
592 case kExprI32LeU:
593 case kExprI64LeU: {
594 auto *TmpDest = makeVariable(IceType_i1);
595 Control()->appendInst(
596 InstIcmp::create(Func, InstIcmp::Ule, TmpDest, Left, Right));
597 BoolDest->setBoolSource(TmpDest);
598 Control()->appendInst(
599 InstCast::create(Func, InstCast::Zext, Dest, TmpDest));
600 break;
601 }
602 case kExprI32LtU:
603 case kExprI64LtU: {
604 auto *TmpDest = makeVariable(IceType_i1);
605 Control()->appendInst(
606 InstIcmp::create(Func, InstIcmp::Ult, TmpDest, Left, Right));
607 BoolDest->setBoolSource(TmpDest);
608 Control()->appendInst(
609 InstCast::create(Func, InstCast::Zext, Dest, TmpDest));
610 break;
611 }
612 case kExprI32GeS:
613 case kExprI64GeS: {
614 auto *TmpDest = makeVariable(IceType_i1);
615 Control()->appendInst(
616 InstIcmp::create(Func, InstIcmp::Sge, TmpDest, Left, Right));
617 BoolDest->setBoolSource(TmpDest);
618 Control()->appendInst(
619 InstCast::create(Func, InstCast::Zext, Dest, TmpDest));
620 break;
621 }
622 case kExprI32GtS:
623 case kExprI64GtS: {
624 auto *TmpDest = makeVariable(IceType_i1);
625 Control()->appendInst(
626 InstIcmp::create(Func, InstIcmp::Sgt, TmpDest, Left, Right));
627 BoolDest->setBoolSource(TmpDest);
628 Control()->appendInst(
629 InstCast::create(Func, InstCast::Zext, Dest, TmpDest));
630 break;
631 }
632 case kExprI32GtU:
633 case kExprI64GtU: {
634 auto *TmpDest = makeVariable(IceType_i1);
635 Control()->appendInst(
636 InstIcmp::create(Func, InstIcmp::Ugt, TmpDest, Left, Right));
637 BoolDest->setBoolSource(TmpDest);
638 Control()->appendInst(
639 InstCast::create(Func, InstCast::Zext, Dest, TmpDest));
640 break;
641 }
642 case kExprF32Eq:
643 case kExprF64Eq: {
644 auto *TmpDest = makeVariable(IceType_i1);
645 Control()->appendInst(
646 InstFcmp::create(Func, InstFcmp::Ueq, TmpDest, Left, Right));
647 BoolDest->setBoolSource(TmpDest);
648 Control()->appendInst(
649 InstCast::create(Func, InstCast::Zext, Dest, TmpDest));
650 break;
651 }
652 case kExprF32Ne:
653 case kExprF64Ne: {
654 auto *TmpDest = makeVariable(IceType_i1);
655 Control()->appendInst(
656 InstFcmp::create(Func, InstFcmp::Une, TmpDest, Left, Right));
657 BoolDest->setBoolSource(TmpDest);
658 Control()->appendInst(
659 InstCast::create(Func, InstCast::Zext, Dest, TmpDest));
660 break;
661 }
662 case kExprF32Le:
663 case kExprF64Le: {
664 auto *TmpDest = makeVariable(IceType_i1);
665 Control()->appendInst(
666 InstFcmp::create(Func, InstFcmp::Ule, TmpDest, Left, Right));
667 BoolDest->setBoolSource(TmpDest);
668 Control()->appendInst(
669 InstCast::create(Func, InstCast::Zext, Dest, TmpDest));
670 break;
671 }
672 case kExprF32Lt:
673 case kExprF64Lt: {
674 auto *TmpDest = makeVariable(IceType_i1);
675 Control()->appendInst(
676 InstFcmp::create(Func, InstFcmp::Ult, TmpDest, Left, Right));
677 BoolDest->setBoolSource(TmpDest);
678 Control()->appendInst(
679 InstCast::create(Func, InstCast::Zext, Dest, TmpDest));
680 break;
681 }
682 case kExprF32Ge:
683 case kExprF64Ge: {
684 auto *TmpDest = makeVariable(IceType_i1);
685 Control()->appendInst(
686 InstFcmp::create(Func, InstFcmp::Uge, TmpDest, Left, Right));
687 BoolDest->setBoolSource(TmpDest);
688 Control()->appendInst(
689 InstCast::create(Func, InstCast::Zext, Dest, TmpDest));
690 break;
691 }
692 case kExprF32Gt:
693 case kExprF64Gt: {
694 auto *TmpDest = makeVariable(IceType_i1);
695 Control()->appendInst(
696 InstFcmp::create(Func, InstFcmp::Ugt, TmpDest, Left, Right));
697 BoolDest->setBoolSource(TmpDest);
698 Control()->appendInst(
699 InstCast::create(Func, InstCast::Zext, Dest, TmpDest));
700 break;
701 }
702 default:
703 LOG(out << "Unknown binop: " << WasmOpcodes::OpcodeName(Opcode) << "\n");
704 llvm::report_fatal_error("Uncovered or invalid binop.");
705 return OperandNode(nullptr);
706 }
707 LOG(out << Dest << "\n");
708 return OperandNode(Dest);
709 }
Unop(wasm::WasmOpcode Opcode,Node Input)710 Node Unop(wasm::WasmOpcode Opcode, Node Input) {
711 LOG(out << "Unop(" << WasmOpcodes::OpcodeName(Opcode) << ", " << Input
712 << ") = ");
713 Variable *Dest = nullptr;
714 switch (Opcode) {
715 // TODO (eholk): merge these next two cases using getConstantInteger
716 case kExprI32Eqz: {
717 auto *BoolDest = makeVariable<BooleanVariable>(IceType_i32);
718 Dest = BoolDest;
719 auto *Tmp = makeVariable(IceType_i1);
720 Control()->appendInst(InstIcmp::create(Func, InstIcmp::Eq, Tmp, Input,
721 Ctx->getConstantInt32(0)));
722 BoolDest->setBoolSource(Tmp);
723 Control()->appendInst(InstCast::create(Func, InstCast::Zext, Dest, Tmp));
724 break;
725 }
726 case kExprI64Eqz: {
727 auto *BoolDest = makeVariable<BooleanVariable>(IceType_i32);
728 Dest = BoolDest;
729 auto *Tmp = makeVariable(IceType_i1);
730 Control()->appendInst(InstIcmp::create(Func, InstIcmp::Eq, Tmp, Input,
731 Ctx->getConstantInt64(0)));
732 BoolDest->setBoolSource(Tmp);
733 Control()->appendInst(InstCast::create(Func, InstCast::Zext, Dest, Tmp));
734 break;
735 }
736 case kExprI32Ctz: {
737 Dest = makeVariable(IceType_i32);
738 const auto FnName = Ctx->getGlobalString("llvm.cttz.i32");
739 bool BadInstrinsic = false;
740 const auto *Info = Ctx->getIntrinsicsInfo().find(FnName, BadInstrinsic);
741 assert(!BadInstrinsic);
742 assert(Info);
743
744 auto *Call = InstIntrinsicCall::create(
745 Func, 1, Dest, Ctx->getConstantExternSym(FnName), Info->Info);
746 Call->addArg(Input);
747 Control()->appendInst(Call);
748 break;
749 }
750 case kExprF32Neg: {
751 Dest = makeVariable(IceType_f32);
752 Control()->appendInst(InstArithmetic::create(
753 Func, InstArithmetic::Fsub, Dest, Ctx->getConstantFloat(0), Input));
754 break;
755 }
756 case kExprF64Neg: {
757 Dest = makeVariable(IceType_f64);
758 Control()->appendInst(InstArithmetic::create(
759 Func, InstArithmetic::Fsub, Dest, Ctx->getConstantDouble(0), Input));
760 break;
761 }
762 case kExprF32Abs: {
763 Dest = makeVariable(IceType_f32);
764 const auto FnName = Ctx->getGlobalString("llvm.fabs.f32");
765 bool BadInstrinsic = false;
766 const auto *Info = Ctx->getIntrinsicsInfo().find(FnName, BadInstrinsic);
767 assert(!BadInstrinsic);
768 assert(Info);
769
770 auto *Call = InstIntrinsicCall::create(
771 Func, 1, Dest, Ctx->getConstantExternSym(FnName), Info->Info);
772 Call->addArg(Input);
773 Control()->appendInst(Call);
774 break;
775 }
776 case kExprF64Abs: {
777 Dest = makeVariable(IceType_f64);
778 const auto FnName = Ctx->getGlobalString("llvm.fabs.f64");
779 bool BadInstrinsic = false;
780 const auto *Info = Ctx->getIntrinsicsInfo().find(FnName, BadInstrinsic);
781 assert(!BadInstrinsic);
782 assert(Info);
783
784 auto *Call = InstIntrinsicCall::create(
785 Func, 1, Dest, Ctx->getConstantExternSym(FnName), Info->Info);
786 Call->addArg(Input);
787 Control()->appendInst(Call);
788 break;
789 }
790 case kExprF32Floor: {
791 Dest = makeVariable(IceType_f64);
792 const auto FnName = Ctx->getGlobalString("env$$floor_f");
793 constexpr bool HasTailCall = false;
794
795 auto *Call = InstCall::create(
796 Func, 1, Dest, Ctx->getConstantExternSym(FnName), HasTailCall);
797 Call->addArg(Input);
798 Control()->appendInst(Call);
799 break;
800 }
801 case kExprF64Floor: {
802 Dest = makeVariable(IceType_f64);
803 const auto FnName = Ctx->getGlobalString("env$$floor_d");
804 constexpr bool HasTailCall = false;
805
806 auto *Call = InstCall::create(
807 Func, 1, Dest, Ctx->getConstantExternSym(FnName), HasTailCall);
808 Call->addArg(Input);
809 Control()->appendInst(Call);
810 break;
811 }
812 case kExprF32Sqrt: {
813 Dest = makeVariable(IceType_f32);
814 const auto FnName = Ctx->getGlobalString("llvm.sqrt.f32");
815 bool BadInstrinsic = false;
816 const auto *Info = Ctx->getIntrinsicsInfo().find(FnName, BadInstrinsic);
817 assert(!BadInstrinsic);
818 assert(Info);
819
820 auto *Call = InstIntrinsicCall::create(
821 Func, 1, Dest, Ctx->getConstantExternSym(FnName), Info->Info);
822 Call->addArg(Input);
823 Control()->appendInst(Call);
824 break;
825 }
826 case kExprF64Sqrt: {
827 Dest = makeVariable(IceType_f64);
828 const auto FnName = Ctx->getGlobalString("llvm.sqrt.f64");
829 bool BadInstrinsic = false;
830 const auto *Info = Ctx->getIntrinsicsInfo().find(FnName, BadInstrinsic);
831 assert(!BadInstrinsic);
832 assert(Info);
833
834 auto *Call = InstIntrinsicCall::create(
835 Func, 1, Dest, Ctx->getConstantExternSym(FnName), Info->Info);
836 Call->addArg(Input);
837 Control()->appendInst(Call);
838 break;
839 }
840 case kExprI64UConvertI32:
841 Dest = makeVariable(IceType_i64);
842 Control()->appendInst(
843 InstCast::create(Func, InstCast::Zext, Dest, Input));
844 break;
845 case kExprI64SConvertI32:
846 Dest = makeVariable(IceType_i64);
847 Control()->appendInst(
848 InstCast::create(Func, InstCast::Sext, Dest, Input));
849 break;
850 case kExprI32SConvertF32:
851 Dest = makeVariable(IceType_i32);
852 Control()->appendInst(
853 InstCast::create(Func, InstCast::Fptosi, Dest, Input));
854 break;
855 case kExprI32UConvertF32:
856 Dest = makeVariable(IceType_i32);
857 Control()->appendInst(
858 InstCast::create(Func, InstCast::Fptoui, Dest, Input));
859 break;
860 case kExprI32SConvertF64:
861 Dest = makeVariable(IceType_i32);
862 Control()->appendInst(
863 InstCast::create(Func, InstCast::Fptosi, Dest, Input));
864 break;
865 case kExprI32UConvertF64:
866 Dest = makeVariable(IceType_i32);
867 Control()->appendInst(
868 InstCast::create(Func, InstCast::Fptoui, Dest, Input));
869 break;
870 case kExprI32ReinterpretF32:
871 Dest = makeVariable(IceType_i32);
872 Control()->appendInst(
873 InstCast::create(Func, InstCast::Bitcast, Dest, Input));
874 break;
875 case kExprI64ReinterpretF64:
876 Dest = makeVariable(IceType_i64);
877 Control()->appendInst(
878 InstCast::create(Func, InstCast::Bitcast, Dest, Input));
879 break;
880 case kExprF64ReinterpretI64:
881 Dest = makeVariable(IceType_f64);
882 Control()->appendInst(
883 InstCast::create(Func, InstCast::Bitcast, Dest, Input));
884 break;
885 case kExprI32ConvertI64:
886 Dest = makeVariable(IceType_i32);
887 Control()->appendInst(
888 InstCast::create(Func, InstCast::Trunc, Dest, Input));
889 break;
890 case kExprF64SConvertI32:
891 Dest = makeVariable(IceType_f64);
892 Control()->appendInst(
893 InstCast::create(Func, InstCast::Sitofp, Dest, Input));
894 break;
895 case kExprF64UConvertI32:
896 Dest = makeVariable(IceType_f64);
897 Control()->appendInst(
898 InstCast::create(Func, InstCast::Uitofp, Dest, Input));
899 break;
900 case kExprF64ConvertF32:
901 Dest = makeVariable(IceType_f64);
902 Control()->appendInst(
903 InstCast::create(Func, InstCast::Fpext, Dest, Input));
904 break;
905 case kExprF32SConvertI32:
906 Dest = makeVariable(IceType_f32);
907 Control()->appendInst(
908 InstCast::create(Func, InstCast::Sitofp, Dest, Input));
909 break;
910 case kExprF32UConvertI32:
911 Dest = makeVariable(IceType_f32);
912 Control()->appendInst(
913 InstCast::create(Func, InstCast::Uitofp, Dest, Input));
914 break;
915 case kExprF32ReinterpretI32:
916 Dest = makeVariable(IceType_f32);
917 Control()->appendInst(
918 InstCast::create(Func, InstCast::Bitcast, Dest, Input));
919 break;
920 case kExprF32ConvertF64:
921 Dest = makeVariable(IceType_f32);
922 Control()->appendInst(
923 InstCast::create(Func, InstCast::Fptrunc, Dest, Input));
924 break;
925 default:
926 LOG(out << "Unknown unop: " << WasmOpcodes::OpcodeName(Opcode) << "\n");
927 llvm::report_fatal_error("Uncovered or invalid unop.");
928 return OperandNode(nullptr);
929 }
930 LOG(out << Dest << "\n");
931 return OperandNode(Dest);
932 }
InputCount(CfgNode * Node) const933 uint32_t InputCount(CfgNode *Node) const { return Node->getInEdges().size(); }
IsPhiWithMerge(Node Phi,Node Merge) const934 bool IsPhiWithMerge(Node Phi, Node Merge) const {
935 LOG(out << "IsPhiWithMerge(" << Phi << ", " << Merge << ")"
936 << "\n");
937 if (Phi && Phi.isOperand()) {
938 LOG(out << " ...is operand"
939 << "\n");
940 if (getDefiningInst(Phi)) {
941 LOG(out << " ...has defining instruction"
942 << "\n");
943 LOG(out << getDefNode(Phi) << "\n");
944 LOG(out << " ..." << (getDefNode(Phi) == Merge) << "\n");
945 return getDefNode(Phi) == Merge;
946 }
947 }
948 return false;
949 }
AppendToMerge(CfgNode * Merge,CfgNode * From) const950 void AppendToMerge(CfgNode *Merge, CfgNode *From) const {
951 From->appendInst(InstBr::create(Func, Merge));
952 }
AppendToPhi(Node Merge,Node Phi,Node From)953 void AppendToPhi(Node Merge, Node Phi, Node From) {
954 LOG(out << "AppendToPhi(" << Merge << ", " << Phi << ", " << From << ")"
955 << "\n");
956 auto *Inst = getDefiningInst(Phi);
957 assert(Inst->getDest()->getType() == From.toOperand()->getType());
958 Inst->addArgument(From, getDefNode(From));
959 }
960
961 //-----------------------------------------------------------------------
962 // Operations that read and/or write {control} and {effect}.
963 //-----------------------------------------------------------------------
Branch(Node Cond,Node * TrueNode,Node * FalseNode)964 Node Branch(Node Cond, Node *TrueNode, Node *FalseNode) {
965 // true_node and false_node appear to be out parameters.
966 LOG(out << "Branch(" << Cond << ", ");
967
968 // save control here because true_node appears to alias control.
969 auto *Ctrl = Control();
970
971 *TrueNode = OperandNode(Func->makeNode());
972 *FalseNode = OperandNode(Func->makeNode());
973
974 LOG(out << *TrueNode << ", " << *FalseNode << ")"
975 << "\n");
976
977 auto *CondBool = Cond.toOperand()->asBoolean();
978 if (CondBool == nullptr) {
979 CondBool = makeVariable(IceType_i1);
980 Ctrl->appendInst(InstIcmp::create(Func, InstIcmp::Ne, CondBool, Cond,
981 Ctx->getConstantInt32(0)));
982 }
983
984 Ctrl->appendInst(InstBr::create(Func, CondBool, *TrueNode, *FalseNode));
985 return OperandNode(nullptr);
986 }
987 InstSwitch *CurrentSwitch = nullptr;
988 CfgNode *SwitchNode = nullptr;
989 SizeT SwitchIndex = 0;
Switch(uint32_t Count,Node Key)990 Node Switch(uint32_t Count, Node Key) {
991 LOG(out << "Switch(" << Count << ", " << Key << ")\n");
992
993 assert(!CurrentSwitch);
994
995 auto *Default = Func->makeNode();
996 // Count - 1 because the decoder counts the default label but Subzero does
997 // not.
998 CurrentSwitch = InstSwitch::create(Func, Count - 1, Key, Default);
999 SwitchIndex = 0;
1000 SwitchNode = Control();
1001 // We don't actually append the switch to the CfgNode here because not all
1002 // the branches are ready.
1003 return Node(nullptr);
1004 }
IfValue(int32_t Value,Node)1005 Node IfValue(int32_t Value, Node) {
1006 LOG(out << "IfValue(" << Value << ") [Index = " << SwitchIndex << "]\n");
1007 assert(CurrentSwitch);
1008 auto *Target = Func->makeNode();
1009 CurrentSwitch->addBranch(SwitchIndex++, Value, Target);
1010 return Node(Target);
1011 }
IfDefault(Node)1012 Node IfDefault(Node) {
1013 LOG(out << "IfDefault(...) [Index = " << SwitchIndex << "]\n");
1014 assert(CurrentSwitch);
1015 assert(CurrentSwitch->getLabelDefault());
1016 // Now we append the switch, since this should be the last edge.
1017 assert(SwitchIndex == CurrentSwitch->getNumCases());
1018 SwitchNode->appendInst(CurrentSwitch);
1019 SwitchNode = nullptr;
1020 auto Default = Node(CurrentSwitch->getLabelDefault());
1021 CurrentSwitch = nullptr;
1022 return Default;
1023 }
Return(uint32_t Count,Node * Vals)1024 Node Return(uint32_t Count, Node *Vals) {
1025 assert(1 >= Count);
1026 LOG(out << "Return(");
1027 if (Count > 0)
1028 LOG(out << Vals[0]);
1029 LOG(out << ")"
1030 << "\n");
1031 auto *Instr =
1032 1 == Count ? InstRet::create(Func, Vals[0]) : InstRet::create(Func);
1033 Control()->appendInst(Instr);
1034 Control()->setHasReturn();
1035 LOG(out << Node(nullptr) << "\n");
1036 return OperandNode(nullptr);
1037 }
ReturnVoid()1038 Node ReturnVoid() {
1039 LOG(out << "ReturnVoid() = ");
1040 auto *Instr = InstRet::create(Func);
1041 Control()->appendInst(Instr);
1042 Control()->setHasReturn();
1043 LOG(out << Node(nullptr) << "\n");
1044 return OperandNode(nullptr);
1045 }
Unreachable()1046 Node Unreachable() {
1047 LOG(out << "Unreachable() = ");
1048 auto *Instr = InstUnreachable::create(Func);
1049 Control()->appendInst(Instr);
1050 LOG(out << Node(nullptr) << "\n");
1051 return OperandNode(nullptr);
1052 }
1053
CallDirect(uint32_t Index,Node * Args)1054 Node CallDirect(uint32_t Index, Node *Args) {
1055 LOG(out << "CallDirect(" << Index << ")"
1056 << "\n");
1057 assert(Module->IsValidFunction(Index));
1058 const auto *Module = this->Module->module;
1059 assert(Module);
1060 const auto &Target = Module->functions[Index];
1061 const auto *Sig = Target.sig;
1062 assert(Sig);
1063 const auto NumArgs = Sig->parameter_count();
1064 LOG(out << " number of args: " << NumArgs << "\n");
1065
1066 const auto TargetName = getFunctionName(Module, Index);
1067 LOG(out << " target name: " << TargetName << "\n");
1068
1069 assert(Sig->return_count() <= 1);
1070
1071 auto TargetOperand =
1072 Ctx->getConstantSym(0, Ctx->getGlobalString(TargetName));
1073
1074 auto *Dest = Sig->return_count() > 0
1075 ? makeVariable(toIceType(Sig->GetReturn()))
1076 : nullptr;
1077 auto *Call = InstCall::create(Func, NumArgs, Dest, TargetOperand,
1078 false /* HasTailCall */);
1079 for (uint32_t i = 0; i < NumArgs; ++i) {
1080 // The builder reserves the first argument for the code object.
1081 LOG(out << " args[" << i << "] = " << Args[i + 1] << "\n");
1082 Call->addArg(Args[i + 1]);
1083 }
1084
1085 Control()->appendInst(Call);
1086 LOG(out << "Call Result = " << Node(Dest) << "\n");
1087 return OperandNode(Dest);
1088 }
CallImport(uint32_t Index,Node * Args)1089 Node CallImport(uint32_t Index, Node *Args) {
1090 LOG(out << "CallImport(" << Index << ")"
1091 << "\n");
1092 const auto *Module = this->Module->module;
1093 assert(Module);
1094 const auto *Sig = this->Module->GetImportSignature(Index);
1095 assert(Sig);
1096 const auto NumArgs = Sig->parameter_count();
1097 LOG(out << " number of args: " << NumArgs << "\n");
1098
1099 const auto &Target = Module->import_table[Index];
1100 const auto ModuleName = toStdString(
1101 Module->GetName(Target.module_name_offset, Target.module_name_length));
1102 const auto FnName = toStdString(Module->GetName(
1103 Target.function_name_offset, Target.function_name_length));
1104
1105 const auto TargetName = Ctx->getGlobalString(ModuleName + "$$" + FnName);
1106 LOG(out << " target name: " << TargetName << "\n");
1107
1108 assert(Sig->return_count() <= 1);
1109
1110 auto TargetOperand = Ctx->getConstantExternSym(TargetName);
1111
1112 auto *Dest = Sig->return_count() > 0
1113 ? makeVariable(toIceType(Sig->GetReturn()))
1114 : nullptr;
1115 constexpr bool NoTailCall = false;
1116 auto *Call =
1117 InstCall::create(Func, NumArgs, Dest, TargetOperand, NoTailCall);
1118 for (uint32_t i = 0; i < NumArgs; ++i) {
1119 // The builder reserves the first argument for the code object.
1120 LOG(out << " args[" << i << "] = " << Args[i + 1] << "\n");
1121 assert(Args[i + 1].toOperand()->getType() == toIceType(Sig->GetParam(i)));
1122 Call->addArg(Args[i + 1]);
1123 }
1124
1125 Control()->appendInst(Call);
1126 LOG(out << "Call Result = " << Node(Dest) << "\n");
1127 return OperandNode(Dest);
1128 }
CallIndirect(uint32_t SigIndex,Node * Args)1129 Node CallIndirect(uint32_t SigIndex, Node *Args) {
1130 LOG(out << "CallIndirect(" << SigIndex << ")\n");
1131 // TODO(eholk): Compile to something better than a switch.
1132 const auto *Module = this->Module->module;
1133 assert(Module);
1134 const auto &IndirectTable = Module->function_table;
1135
1136 auto *Abort = getIndirectFailTarget();
1137
1138 assert(Args[0].toOperand());
1139
1140 auto *Switch = InstSwitch::create(Func, IndirectTable.size(),
1141 Args[0].toOperand(), Abort);
1142 assert(Abort);
1143
1144 const bool HasReturn = Module->signatures[SigIndex]->return_count() != 0;
1145 const Ice::Type DestTy =
1146 HasReturn ? toIceType(Module->signatures[SigIndex]->GetReturn())
1147 : IceType_void;
1148
1149 auto *Dest = HasReturn ? makeVariable(DestTy) : nullptr;
1150
1151 auto *ExitNode = Func->makeNode();
1152 auto *PhiInst =
1153 HasReturn ? InstPhi::create(Func, IndirectTable.size(), Dest) : nullptr;
1154
1155 for (uint32_t Index = 0; Index < IndirectTable.size(); ++Index) {
1156 const auto &Target = Module->functions[IndirectTable[Index]];
1157
1158 if (SigIndex == Target.sig_index) {
1159 auto *CallNode = Func->makeNode();
1160 auto *SavedControl = Control();
1161 *ControlPtr = OperandNode(CallNode);
1162 auto *Tmp = CallDirect(Target.func_index, Args).toOperand();
1163 *ControlPtr = OperandNode(SavedControl);
1164 if (PhiInst) {
1165 PhiInst->addArgument(Tmp, CallNode);
1166 }
1167 CallNode->appendInst(InstBr::create(Func, ExitNode));
1168 Switch->addBranch(Index, Index, CallNode);
1169 } else {
1170 Switch->addBranch(Index, Index, Abort);
1171 }
1172 }
1173
1174 if (PhiInst) {
1175 ExitNode->appendInst(PhiInst);
1176 }
1177
1178 Control()->appendInst(Switch);
1179 *ControlPtr = OperandNode(ExitNode);
1180 return OperandNode(Dest);
1181 }
Invert(Node Node)1182 Node Invert(Node Node) {
1183 (void)Node;
1184 llvm::report_fatal_error("Invert");
1185 }
1186
1187 //-----------------------------------------------------------------------
1188 // Operations that concern the linear memory.
1189 //-----------------------------------------------------------------------
MemSize(uint32_t Offset)1190 Node MemSize(uint32_t Offset) {
1191 (void)Offset;
1192 llvm::report_fatal_error("MemSize");
1193 }
LoadGlobal(uint32_t Index)1194 Node LoadGlobal(uint32_t Index) {
1195 (void)Index;
1196 llvm::report_fatal_error("LoadGlobal");
1197 }
StoreGlobal(uint32_t Index,Node Val)1198 Node StoreGlobal(uint32_t Index, Node Val) {
1199 (void)Index;
1200 (void)Val;
1201 llvm::report_fatal_error("StoreGlobal");
1202 }
1203
LoadMem(wasm::LocalType Type,MachineType MemType,Node Index,uint32_t Offset)1204 Node LoadMem(wasm::LocalType Type, MachineType MemType, Node Index,
1205 uint32_t Offset) {
1206 LOG(out << "LoadMem." << toIceType(MemType) << "(" << Index << "[" << Offset
1207 << "]) = ");
1208
1209 auto *RealAddr = sanitizeAddress(Index, Offset);
1210
1211 auto *LoadResult = makeVariable(toIceType(MemType));
1212 Control()->appendInst(InstLoad::create(Func, LoadResult, RealAddr));
1213
1214 // and cast, if needed
1215 Variable *Result = nullptr;
1216 if (toIceType(Type) != toIceType(MemType)) {
1217 auto DestType = toIceType(Type);
1218 Result = makeVariable(DestType);
1219 // TODO(eholk): handle signs correctly.
1220 if (isScalarIntegerType(DestType)) {
1221 if (MemType.IsSigned()) {
1222 Control()->appendInst(
1223 InstCast::create(Func, InstCast::Sext, Result, LoadResult));
1224 } else {
1225 Control()->appendInst(
1226 InstCast::create(Func, InstCast::Zext, Result, LoadResult));
1227 }
1228 } else if (isScalarFloatingType(DestType)) {
1229 Control()->appendInst(
1230 InstCast::create(Func, InstCast::Sitofp, Result, LoadResult));
1231 } else {
1232 llvm::report_fatal_error("Unsupported type for memory load");
1233 }
1234 } else {
1235 Result = LoadResult;
1236 }
1237
1238 LOG(out << Result << "\n");
1239 return OperandNode(Result);
1240 }
StoreMem(MachineType Type,Node Index,uint32_t Offset,Node Val)1241 void StoreMem(MachineType Type, Node Index, uint32_t Offset, Node Val) {
1242 LOG(out << "StoreMem." << toIceType(Type) << "(" << Index << "[" << Offset
1243 << "] = " << Val << ")"
1244 << "\n");
1245
1246 auto *RealAddr = sanitizeAddress(Index, Offset);
1247
1248 // cast the value to the right type, if needed
1249 Operand *StoreVal = nullptr;
1250 if (toIceType(Type) != Val.toOperand()->getType()) {
1251 auto *LocalStoreVal = makeVariable(toIceType(Type));
1252 Control()->appendInst(
1253 InstCast::create(Func, InstCast::Trunc, LocalStoreVal, Val));
1254 StoreVal = LocalStoreVal;
1255 } else {
1256 StoreVal = Val;
1257 }
1258
1259 // then store the memory
1260 Control()->appendInst(InstStore::create(Func, StoreVal, RealAddr));
1261 }
1262
PrintDebugName(OperandNode Node)1263 static void PrintDebugName(OperandNode Node) {
1264 (void)Node;
1265 llvm::report_fatal_error("PrintDebugName");
1266 }
1267
Control()1268 CfgNode *Control() {
1269 return ControlPtr ? ControlPtr->toCfgNode() : Func->getEntryNode();
1270 }
Effect()1271 Node Effect() { return *EffectPtr; }
1272
set_module(wasm::ModuleEnv * Module)1273 void set_module(wasm::ModuleEnv *Module) { this->Module = Module; }
1274
set_control_ptr(Node * Control)1275 void set_control_ptr(Node *Control) { this->ControlPtr = Control; }
1276
set_effect_ptr(Node * Effect)1277 void set_effect_ptr(Node *Effect) { this->EffectPtr = Effect; }
1278
1279 private:
1280 wasm::ModuleEnv *Module;
1281 Node *ControlPtr;
1282 Node *EffectPtr;
1283
1284 class Cfg *Func;
1285 GlobalContext *Ctx;
1286
1287 CfgNode *BoundsFailTarget = nullptr;
1288 CfgNode *IndirectFailTarget = nullptr;
1289
1290 SizeT NextArg = 0;
1291
1292 CfgUnorderedMap<Operand *, InstPhi *> PhiMap;
1293 CfgUnorderedMap<Operand *, CfgNode *> DefNodeMap;
1294
1295 Operand *WasmMemory = nullptr;
1296
getDefiningInst(Operand * Op) const1297 InstPhi *getDefiningInst(Operand *Op) const {
1298 const auto &Iter = PhiMap.find(Op);
1299 if (Iter == PhiMap.end()) {
1300 return nullptr;
1301 }
1302 return Iter->second;
1303 }
1304
setDefiningInst(Operand * Op,InstPhi * Phi)1305 void setDefiningInst(Operand *Op, InstPhi *Phi) {
1306 LOG(out << "\n== setDefiningInst(" << Op << ", " << Phi << ") ==\n");
1307 PhiMap.emplace(Op, Phi);
1308 }
1309
makeVariable(Ice::Type Type)1310 template <typename T = Variable> T *makeVariable(Ice::Type Type) {
1311 return makeVariable<T>(Type, Control());
1312 }
1313
1314 template <typename T = Variable>
makeVariable(Ice::Type Type,CfgNode * DefNode)1315 T *makeVariable(Ice::Type Type, CfgNode *DefNode) {
1316 auto *Var = Func->makeVariable<T>(Type);
1317 DefNodeMap.emplace(Var, DefNode);
1318 return Var;
1319 }
1320
getDefNode(Operand * Op) const1321 CfgNode *getDefNode(Operand *Op) const {
1322 const auto &Iter = DefNodeMap.find(Op);
1323 if (Iter == DefNodeMap.end()) {
1324 return nullptr;
1325 }
1326 return Iter->second;
1327 }
1328
getBoundsFailTarget()1329 CfgNode *getBoundsFailTarget() {
1330 if (!BoundsFailTarget) {
1331 // TODO (eholk): Move this node to the end of the CFG, or even better,
1332 // have only one abort block for the whole module.
1333 BoundsFailTarget = Func->makeNode();
1334 BoundsFailTarget->appendInst(InstCall::create(
1335 Func, 0, nullptr,
1336 Ctx->getConstantExternSym(Ctx->getGlobalString("__Sz_bounds_fail")),
1337 false));
1338 BoundsFailTarget->appendInst(InstUnreachable::create(Func));
1339 }
1340
1341 return BoundsFailTarget;
1342 }
getIndirectFailTarget()1343 CfgNode *getIndirectFailTarget() {
1344 if (!IndirectFailTarget) {
1345 // TODO (eholk): Move this node to the end of the CFG, or even better,
1346 // have only one abort block for the whole module.
1347 IndirectFailTarget = Func->makeNode();
1348 IndirectFailTarget->appendInst(InstCall::create(
1349 Func, 0, nullptr,
1350 Ctx->getConstantExternSym(Ctx->getGlobalString("__Sz_indirect_fail")),
1351 false));
1352 IndirectFailTarget->appendInst(InstUnreachable::create(Func));
1353 }
1354
1355 return IndirectFailTarget;
1356 }
1357
getWasmMemory()1358 Operand *getWasmMemory() {
1359 assert(WasmMemory != nullptr);
1360 return WasmMemory;
1361 }
1362
sanitizeAddress(Operand * Base,uint32_t Offset)1363 Operand *sanitizeAddress(Operand *Base, uint32_t Offset) {
1364 SizeT MemSize = Module->module->min_mem_pages * WASM_PAGE_SIZE;
1365
1366 bool ConstZeroBase = false;
1367
1368 // first, add the index and the offset together.
1369 if (auto *ConstBase = llvm::dyn_cast<ConstantInteger32>(Base)) {
1370 uint32_t RealOffset = Offset + ConstBase->getValue();
1371 if (RealOffset >= MemSize) {
1372 // We've proven this will always be an out of bounds access, so insert
1373 // an unconditional trap.
1374 Control()->appendInst(InstUnreachable::create(Func));
1375 // It doesn't matter what we return here, so return something that will
1376 // allow the rest of code generation to happen.
1377 //
1378 // We might be tempted to just abort translation here, but out of bounds
1379 // memory access is a runtime trap, not a compile error.
1380 return Ctx->getConstantZero(getPointerType());
1381 }
1382 Base = Ctx->getConstantInt32(RealOffset);
1383 ConstZeroBase = (0 == RealOffset);
1384 } else if (0 != Offset) {
1385 auto *Addr = makeVariable(Ice::getPointerType());
1386 auto *OffsetConstant = Ctx->getConstantInt32(Offset);
1387 Control()->appendInst(InstArithmetic::create(Func, InstArithmetic::Add,
1388 Addr, Base, OffsetConstant));
1389
1390 Base = Addr;
1391 }
1392
1393 // Do the bounds check if enabled
1394 if (getFlags().getWasmBoundsCheck() &&
1395 !llvm::isa<ConstantInteger32>(Base)) {
1396 // TODO (eholk): creating a new basic block on every memory access is
1397 // terrible (see https://goo.gl/Zj7DTr). Try adding a new instruction that
1398 // encapsulates this "abort if false" pattern.
1399 auto *CheckPassed = Func->makeNode();
1400 auto *CheckFailed = getBoundsFailTarget();
1401
1402 auto *Check = makeVariable(IceType_i1);
1403 Control()->appendInst(InstIcmp::create(Func, InstIcmp::Ult, Check, Base,
1404 Ctx->getConstantInt32(MemSize)));
1405 Control()->appendInst(
1406 InstBr::create(Func, Check, CheckPassed, CheckFailed));
1407
1408 *ControlPtr = OperandNode(CheckPassed);
1409 }
1410
1411 Ice::Operand *RealAddr = nullptr;
1412 auto MemBase = getWasmMemory();
1413 if (!ConstZeroBase) {
1414 auto RealAddrV = Func->makeVariable(Ice::getPointerType());
1415 Control()->appendInst(InstArithmetic::create(Func, InstArithmetic::Add,
1416 RealAddrV, Base, MemBase));
1417
1418 RealAddr = RealAddrV;
1419 } else {
1420 RealAddr = MemBase;
1421 }
1422 return RealAddr;
1423 }
1424
log(F Fn) const1425 template <typename F = std::function<void(Ostream &)>> void log(F Fn) const {
1426 if (BuildDefs::dump() && (getFlags().getVerbose() & IceV_Wasm)) {
1427 Fn(Ctx->getStrDump());
1428 Ctx->getStrDump().flush();
1429 }
1430 }
1431 };
1432
translateFunction(Zone * Zone,FunctionBody & Body)1433 std::unique_ptr<Cfg> WasmTranslator::translateFunction(Zone *Zone,
1434 FunctionBody &Body) {
1435 OstreamLocker L1(Ctx);
1436 auto Func = Cfg::create(Ctx, getNextSequenceNumber());
1437 TimerMarker T(TimerStack::TT_wasmGenIce, Func.get());
1438 Ice::CfgLocalAllocatorScope L2(Func.get());
1439
1440 // TODO(eholk): parse the function signature...
1441
1442 Func->setEntryNode(Func->makeNode());
1443
1444 IceBuilder Builder(Func.get());
1445 SR_WasmDecoder<OperandNode, IceBuilder> Decoder(Zone, &Builder, Body);
1446
1447 LOG(out << getFlags().getDefaultGlobalPrefix() << "\n");
1448 Decoder.Decode();
1449
1450 // We don't always know where the incoming branches are in phi nodes, so this
1451 // function finds them.
1452 Func->fixPhiNodes();
1453
1454 Func->computeInOutEdges();
1455
1456 return Func;
1457 }
1458
1459 constexpr SizeT InitialBufferSize = 16 << 10; // 16KB
1460
WasmTranslator(GlobalContext * Ctx)1461 WasmTranslator::WasmTranslator(GlobalContext *Ctx)
1462 : Translator(Ctx), Buffer(InitialBufferSize) {}
1463
translate(const std::string & IRFilename,std::unique_ptr<llvm::DataStreamer> InputStream)1464 void WasmTranslator::translate(
1465 const std::string &IRFilename,
1466 std::unique_ptr<llvm::DataStreamer> InputStream) {
1467 TimerMarker T(TimerStack::TT_wasm, Ctx);
1468
1469 LOG(out << "Initializing v8/wasm stuff..."
1470 << "\n");
1471 Zone Zone;
1472 ZoneScope _(&Zone);
1473
1474 SizeT BytesRead = 0;
1475 while (true) {
1476 BytesRead +=
1477 InputStream->GetBytes(&Buffer[BytesRead], Buffer.size() - BytesRead);
1478 LOG(out << "Read " << BytesRead << " bytes"
1479 << "\n");
1480 if (BytesRead < Buffer.size())
1481 break;
1482 Buffer.resize(Buffer.size() * 2);
1483 }
1484
1485 LOG(out << "Decoding module " << IRFilename << "\n");
1486
1487 constexpr v8::internal::Isolate *NoIsolate = nullptr;
1488 auto Result = DecodeWasmModule(NoIsolate, &Zone, Buffer.data(),
1489 Buffer.data() + BytesRead, false, kWasmOrigin);
1490
1491 auto Module = Result.val;
1492
1493 LOG(out << "Module info:"
1494 << "\n");
1495 LOG(out << " min_mem_pages: " << Module->min_mem_pages << "\n");
1496 LOG(out << " max_mem_pages: " << Module->max_mem_pages << "\n");
1497 LOG(out << " number of globals: " << Module->globals.size() << "\n");
1498 LOG(out << " number of signatures: " << Module->signatures.size()
1499 << "\n");
1500 LOG(out << " number of functions: " << Module->functions.size() << "\n");
1501 LOG(out << " number of data_segments: " << Module->data_segments.size()
1502 << "\n");
1503 LOG(out << " function table size: " << Module->function_table.size()
1504 << "\n");
1505 LOG(out << " import table size: " << Module->import_table.size()
1506 << "\n");
1507 LOG(out << " export table size: " << Module->export_table.size()
1508 << "\n");
1509
1510 LOG(out << "\n"
1511 << "Data segment information:"
1512 << "\n");
1513 uint32_t Id = 0;
1514 for (const auto Seg : Module->data_segments) {
1515 LOG(out << Id << ": (" << Seg.source_offset << ", " << Seg.source_size
1516 << ") => " << Seg.dest_addr);
1517 if (Seg.init) {
1518 LOG(out << " init\n");
1519 } else {
1520 LOG(out << "\n");
1521 }
1522 Id++;
1523 }
1524
1525 LOG(out << "\n"
1526 << "Import information:"
1527 << "\n");
1528 for (const auto Import : Module->import_table) {
1529 auto ModuleName = toStdString(
1530 Module->GetName(Import.module_name_offset, Import.module_name_length));
1531 auto FnName = toStdString(Module->GetName(Import.function_name_offset,
1532 Import.function_name_length));
1533 LOG(out << " " << Import.sig_index << ": " << ModuleName << "::" << FnName
1534 << "\n");
1535 }
1536
1537 LOG(out << "\n"
1538 << "Export information:"
1539 << "\n");
1540 for (const auto Export : Module->export_table) {
1541 LOG(out << " " << Export.func_index << ": "
1542 << toStdString(
1543 Module->GetName(Export.name_offset, Export.name_length))
1544 << " (" << Export.name_offset << ", " << Export.name_length << ")");
1545 LOG(out << "\n");
1546 }
1547
1548 LOG(out << "\n"
1549 << "Function information:"
1550 << "\n");
1551 for (const auto F : Module->functions) {
1552 LOG(out << " " << F.func_index << ": "
1553 << toStdString(Module->GetName(F.name_offset, F.name_length))
1554 << " (" << F.name_offset << ", " << F.name_length << ")");
1555 if (F.exported)
1556 LOG(out << " export");
1557 if (F.external)
1558 LOG(out << " extern");
1559 LOG(out << "\n");
1560 }
1561
1562 LOG(out << "\n"
1563 << "Indirect table:"
1564 << "\n");
1565 for (uint32_t F : Module->function_table) {
1566 LOG(out << " " << F << ": " << getFunctionName(Module, F) << "\n");
1567 }
1568
1569 ModuleEnv ModuleEnv;
1570 ModuleEnv.module = Module;
1571
1572 FunctionBody Body;
1573 Body.module = &ModuleEnv;
1574
1575 LOG(out << "Translating " << IRFilename << "\n");
1576
1577 {
1578 unique_ptr<VariableDeclarationList> Globals =
1579 makeUnique<VariableDeclarationList>();
1580
1581 // Global variables, etc go here.
1582 auto *WasmMemory = VariableDeclaration::createExternal(Globals.get());
1583 WasmMemory->setName(Ctx->getGlobalString("WASM_DATA_INIT"));
1584
1585 // Fill in the segments
1586 SizeT WritePtr = 0;
1587 for (const auto Seg : Module->data_segments) {
1588 // fill in gaps with zero.
1589 if (Seg.dest_addr > WritePtr) {
1590 WasmMemory->addInitializer(VariableDeclaration::ZeroInitializer::create(
1591 Globals.get(), Seg.dest_addr - WritePtr));
1592 WritePtr = Seg.dest_addr;
1593 }
1594
1595 // Add the data
1596 WasmMemory->addInitializer(VariableDeclaration::DataInitializer::create(
1597 Globals.get(), reinterpret_cast<const char *>(Module->module_start) +
1598 Seg.source_offset,
1599 Seg.source_size));
1600
1601 WritePtr += Seg.source_size;
1602 }
1603
1604 // Save the size of the initialized data in a global variable so the runtime
1605 // can use it to determine the initial heap break.
1606 auto *GlobalDataSize = VariableDeclaration::createExternal(Globals.get());
1607 GlobalDataSize->setName(Ctx->getGlobalString("WASM_DATA_SIZE"));
1608 GlobalDataSize->addInitializer(VariableDeclaration::DataInitializer::create(
1609 Globals.get(), reinterpret_cast<const char *>(&WritePtr),
1610 sizeof(WritePtr)));
1611
1612 // Save the number of pages for the runtime
1613 auto *GlobalNumPages = VariableDeclaration::createExternal(Globals.get());
1614 GlobalNumPages->setName(Ctx->getGlobalString("WASM_NUM_PAGES"));
1615 GlobalNumPages->addInitializer(VariableDeclaration::DataInitializer::create(
1616 Globals.get(), reinterpret_cast<const char *>(&Module->min_mem_pages),
1617 sizeof(Module->min_mem_pages)));
1618
1619 Globals->push_back(WasmMemory);
1620 Globals->push_back(GlobalDataSize);
1621 Globals->push_back(GlobalNumPages);
1622
1623 lowerGlobals(std::move(Globals));
1624 }
1625
1626 // Translate each function.
1627 for (const auto Fn : Module->functions) {
1628 const auto FnName = getFunctionName(Module, Fn.func_index);
1629
1630 LOG(out << " " << Fn.func_index << ": " << FnName << "...");
1631
1632 Body.sig = Fn.sig;
1633 Body.base = Buffer.data();
1634 Body.start = Buffer.data() + Fn.code_start_offset;
1635 Body.end = Buffer.data() + Fn.code_end_offset;
1636
1637 std::unique_ptr<Cfg> Func = nullptr;
1638 {
1639 TimerMarker T_func(getContext(), FnName);
1640 Func = translateFunction(&Zone, Body);
1641 Func->setFunctionName(Ctx->getGlobalString(FnName));
1642 }
1643 Ctx->optQueueBlockingPush(makeUnique<CfgOptWorkItem>(std::move(Func)));
1644 LOG(out << "done.\n");
1645 }
1646
1647 return;
1648 }
1649
1650 #endif // ALLOW_WASM
1651