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
50using namespace std;
51using namespace Ice;
52using namespace v8::internal;
53using namespace v8::internal::wasm;
54using v8::internal::wasm::DecodeWasmModule;
55
56#undef LOG
57#define LOG(Expr) log([&](Ostream & out) { Expr; })
58
59namespace {
60// 64KB
61const uint32_t WASM_PAGE_SIZE = 64 << 10;
62
63std::string toStdString(WasmName Name) {
64  return std::string(Name.name, Name.length);
65}
66
67Ice::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
93Ice::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
128std::string fnNameFromId(uint32_t Id) {
129  return std::string("fn") + to_string(Id);
130}
131
132std::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.
150class 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
156public:
157  OperandNode() = default;
158  explicit OperandNode(Operand *Operand)
159      : Data(reinterpret_cast<uintptr_t>(Operand)) {}
160  explicit OperandNode(CfgNode *Node)
161      : Data(reinterpret_cast<uintptr_t>(Node) | NODE_FLAG) {}
162  explicit OperandNode(nullptr_t) : Data(UNDEF_PTR) {}
163
164  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
174  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
184  explicit operator bool() const { return (Data != UNDEF_PTR) && Data; }
185  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  }
190  bool operator!=(const OperandNode &Rhs) const { return !(*this == Rhs); }
191
192  bool isOperand() const { return (Data != UNDEF_PTR) && !(Data & NODE_FLAG); }
193  bool isCfgNode() const { return (Data != UNDEF_PTR) && (Data & NODE_FLAG); }
194
195  Operand *toOperand() const { return static_cast<Operand *>(*this); }
196
197  CfgNode *toCfgNode() const { return static_cast<CfgNode *>(*this); }
198};
199
200Ostream &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
215bool 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
255class 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
263public:
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.
268  Node *Buffer(size_t Count) {
269    LOG(out << "Buffer(" << Count << ")\n");
270    return Func->allocateArrayOf<Node>(Count);
271  }
272
273  Node Error() { llvm::report_fatal_error("Error"); }
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  }
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  }
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  }
306  void Terminate(Node Effect, Node Control) {
307    // TODO(eholk): this is almost certainly wrong
308    LOG(out << "Terminate(" << Effect << ", " << Control << ")"
309            << "\n");
310  }
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  }
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  }
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  }
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  }
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  }
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  }
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  }
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  }
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  }
933  uint32_t InputCount(CfgNode *Node) const { return Node->getInEdges().size(); }
934  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  }
950  void AppendToMerge(CfgNode *Merge, CfgNode *From) const {
951    From->appendInst(InstBr::create(Func, Merge));
952  }
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  //-----------------------------------------------------------------------
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;
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  }
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  }
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  }
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  }
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  }
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
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  }
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  }
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  }
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  //-----------------------------------------------------------------------
1190  Node MemSize(uint32_t Offset) {
1191    (void)Offset;
1192    llvm::report_fatal_error("MemSize");
1193  }
1194  Node LoadGlobal(uint32_t Index) {
1195    (void)Index;
1196    llvm::report_fatal_error("LoadGlobal");
1197  }
1198  Node StoreGlobal(uint32_t Index, Node Val) {
1199    (void)Index;
1200    (void)Val;
1201    llvm::report_fatal_error("StoreGlobal");
1202  }
1203
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  }
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
1263  static void PrintDebugName(OperandNode Node) {
1264    (void)Node;
1265    llvm::report_fatal_error("PrintDebugName");
1266  }
1267
1268  CfgNode *Control() {
1269    return ControlPtr ? ControlPtr->toCfgNode() : Func->getEntryNode();
1270  }
1271  Node Effect() { return *EffectPtr; }
1272
1273  void set_module(wasm::ModuleEnv *Module) { this->Module = Module; }
1274
1275  void set_control_ptr(Node *Control) { this->ControlPtr = Control; }
1276
1277  void set_effect_ptr(Node *Effect) { this->EffectPtr = Effect; }
1278
1279private:
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
1297  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
1305  void setDefiningInst(Operand *Op, InstPhi *Phi) {
1306    LOG(out << "\n== setDefiningInst(" << Op << ", " << Phi << ") ==\n");
1307    PhiMap.emplace(Op, Phi);
1308  }
1309
1310  template <typename T = Variable> T *makeVariable(Ice::Type Type) {
1311    return makeVariable<T>(Type, Control());
1312  }
1313
1314  template <typename T = Variable>
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
1321  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
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  }
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
1358  Operand *getWasmMemory() {
1359    assert(WasmMemory != nullptr);
1360    return WasmMemory;
1361  }
1362
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
1425  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
1433std::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
1459constexpr SizeT InitialBufferSize = 16 << 10; // 16KB
1460
1461WasmTranslator::WasmTranslator(GlobalContext *Ctx)
1462    : Translator(Ctx), Buffer(InitialBufferSize) {}
1463
1464void 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