Home | History | Annotate | Download | only in src 
      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 
     63 std::string toStdString(WasmName Name) {
     64   return std::string(Name.name, Name.length);
     65 }
     66 
     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 
     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 
    128 std::string fnNameFromId(uint32_t Id) {
    129   return std::string("fn") + to_string(Id);
    130 }
    131 
    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;
    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 
    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 
    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:
    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 
   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 
   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 
   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 
   1461 WasmTranslator::WasmTranslator(GlobalContext *Ctx)
   1462     : Translator(Ctx), Buffer(InitialBufferSize) {}
   1463 
   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