lib/Target/WebAssembly/WebAssemblyISelLowering.cpp

   1 //=- WebAssemblyISelLowering.cpp - WebAssembly DAG Lowering Implementation -==//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 ///
   9 /// \file
  10 /// This file implements the WebAssemblyTargetLowering class.
  11 ///
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "WebAssemblyISelLowering.h"
  15 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
  16 #include "WebAssemblyMachineFunctionInfo.h"
  17 #include "WebAssemblySubtarget.h"
  18 #include "WebAssemblyTargetMachine.h"
  19 #include "llvm/CodeGen/Analysis.h"
  20 #include "llvm/CodeGen/CallingConvLower.h"
  21 #include "llvm/CodeGen/MachineInstrBuilder.h"
  22 #include "llvm/CodeGen/MachineJumpTableInfo.h"
  23 #include "llvm/CodeGen/MachineModuleInfo.h"
  24 #include "llvm/CodeGen/MachineRegisterInfo.h"
  25 #include "llvm/CodeGen/SelectionDAG.h"
  26 #include "llvm/CodeGen/WasmEHFuncInfo.h"
  27 #include "llvm/IR/DiagnosticInfo.h"
  28 #include "llvm/IR/DiagnosticPrinter.h"
  29 #include "llvm/IR/Function.h"
  30 #include "llvm/IR/Intrinsics.h"
  31 #include "llvm/Support/Debug.h"
  32 #include "llvm/Support/ErrorHandling.h"
  33 #include "llvm/Support/raw_ostream.h"
  34 #include "llvm/Target/TargetOptions.h"
  35 using namespace llvm;
  36
  37 #define DEBUG_TYPE "wasm-lower"
  38
  39 WebAssemblyTargetLowering::WebAssemblyTargetLowering(
  40     const TargetMachine &TM, const WebAssemblySubtarget &STI)
  41     : TargetLowering(TM), Subtarget(&STI) {
  42   auto MVTPtr = Subtarget->hasAddr64() ? MVT::i64 : MVT::i32;
  43
  44   // Booleans always contain 0 or 1.
  45   setBooleanContents(ZeroOrOneBooleanContent);
  46   // Except in SIMD vectors
  47   setBooleanVectorContents(ZeroOrNegativeOneBooleanContent);
  48   // WebAssembly does not produce floating-point exceptions on normal floating
  49   // point operations.
  50   setHasFloatingPointExceptions(false);
  51   // We don't know the microarchitecture here, so just reduce register pressure.
  52   setSchedulingPreference(Sched::RegPressure);
  53   // Tell ISel that we have a stack pointer.
  54   setStackPointerRegisterToSaveRestore(
  55       Subtarget->hasAddr64() ? WebAssembly::SP64 : WebAssembly::SP32);
  56   // Set up the register classes.
  57   addRegisterClass(MVT::i32, &WebAssembly::I32RegClass);
  58   addRegisterClass(MVT::i64, &WebAssembly::I64RegClass);
  59   addRegisterClass(MVT::f32, &WebAssembly::F32RegClass);
  60   addRegisterClass(MVT::f64, &WebAssembly::F64RegClass);
  61   if (Subtarget->hasSIMD128()) {
  62     addRegisterClass(MVT::v16i8, &WebAssembly::V128RegClass);
  63     addRegisterClass(MVT::v8i16, &WebAssembly::V128RegClass);
  64     addRegisterClass(MVT::v4i32, &WebAssembly::V128RegClass);
  65     addRegisterClass(MVT::v4f32, &WebAssembly::V128RegClass);
  66   }
  67   if (Subtarget->hasUnimplementedSIMD128()) {
  68     addRegisterClass(MVT::v2i64, &WebAssembly::V128RegClass);
  69     addRegisterClass(MVT::v2f64, &WebAssembly::V128RegClass);
  70   }
  71   // Compute derived properties from the register classes.
  72   computeRegisterProperties(Subtarget->getRegisterInfo());
  73
  74   setOperationAction(ISD::GlobalAddress, MVTPtr, Custom);
  75   setOperationAction(ISD::ExternalSymbol, MVTPtr, Custom);
  76   setOperationAction(ISD::JumpTable, MVTPtr, Custom);
  77   setOperationAction(ISD::BlockAddress, MVTPtr, Custom);
  78   setOperationAction(ISD::BRIND, MVT::Other, Custom);
  79
  80   // Take the default expansion for va_arg, va_copy, and va_end. There is no
  81   // default action for va_start, so we do that custom.
  82   setOperationAction(ISD::VASTART, MVT::Other, Custom);
  83   setOperationAction(ISD::VAARG, MVT::Other, Expand);
  84   setOperationAction(ISD::VACOPY, MVT::Other, Expand);
  85   setOperationAction(ISD::VAEND, MVT::Other, Expand);
  86
  87   for (auto T : {MVT::f32, MVT::f64, MVT::v4f32, MVT::v2f64}) {
  88     // Don't expand the floating-point types to constant pools.
  89     setOperationAction(ISD::ConstantFP, T, Legal);
  90     // Expand floating-point comparisons.
  91     for (auto CC : {ISD::SETO, ISD::SETUO, ISD::SETUEQ, ISD::SETONE,
  92                     ISD::SETULT, ISD::SETULE, ISD::SETUGT, ISD::SETUGE})
  93       setCondCodeAction(CC, T, Expand);
  94     // Expand floating-point library function operators.
  95     for (auto Op :
  96          {ISD::FSIN, ISD::FCOS, ISD::FSINCOS, ISD::FPOW, ISD::FREM, ISD::FMA})
  97       setOperationAction(Op, T, Expand);
  98     // Note supported floating-point library function operators that otherwise
  99     // default to expand.
 100     for (auto Op :
 101          {ISD::FCEIL, ISD::FFLOOR, ISD::FTRUNC, ISD::FNEARBYINT, ISD::FRINT})
 102       setOperationAction(Op, T, Legal);
 103     // Support minimum and maximum, which otherwise default to expand.
 104     setOperationAction(ISD::FMINIMUM, T, Legal);
 105     setOperationAction(ISD::FMAXIMUM, T, Legal);
 106     // WebAssembly currently has no builtin f16 support.
 107     setOperationAction(ISD::FP16_TO_FP, T, Expand);
 108     setOperationAction(ISD::FP_TO_FP16, T, Expand);
 109     setLoadExtAction(ISD::EXTLOAD, T, MVT::f16, Expand);
 110     setTruncStoreAction(T, MVT::f16, Expand);
 111   }
 112
 113   // Expand unavailable integer operations.
 114   for (auto Op :
 115        {ISD::BSWAP, ISD::SMUL_LOHI, ISD::UMUL_LOHI, ISD::MULHS, ISD::MULHU,
 116         ISD::SDIVREM, ISD::UDIVREM, ISD::SHL_PARTS, ISD::SRA_PARTS,
 117         ISD::SRL_PARTS, ISD::ADDC, ISD::ADDE, ISD::SUBC, ISD::SUBE}) {
 118     for (auto T : {MVT::i32, MVT::i64})
 119       setOperationAction(Op, T, Expand);
 120     if (Subtarget->hasSIMD128())
 121       for (auto T : {MVT::v16i8, MVT::v8i16, MVT::v4i32})
 122         setOperationAction(Op, T, Expand);
 123     if (Subtarget->hasUnimplementedSIMD128())
 124       setOperationAction(Op, MVT::v2i64, Expand);
 125   }
 126
 127   // SIMD-specific configuration
 128   if (Subtarget->hasSIMD128()) {
 129     // Support saturating add for i8x16 and i16x8
 130     for (auto Op : {ISD::SADDSAT, ISD::UADDSAT})
 131       for (auto T : {MVT::v16i8, MVT::v8i16})
 132         setOperationAction(Op, T, Legal);
 133
 134     // Custom lower BUILD_VECTORs to minimize number of replace_lanes
 135     for (auto T : {MVT::v16i8, MVT::v8i16, MVT::v4i32, MVT::v4f32})
 136       setOperationAction(ISD::BUILD_VECTOR, T, Custom);
 137     if (Subtarget->hasUnimplementedSIMD128())
 138       for (auto T : {MVT::v2i64, MVT::v2f64})
 139         setOperationAction(ISD::BUILD_VECTOR, T, Custom);
 140
 141     // We have custom shuffle lowering to expose the shuffle mask
 142     for (auto T : {MVT::v16i8, MVT::v8i16, MVT::v4i32, MVT::v4f32})
 143       setOperationAction(ISD::VECTOR_SHUFFLE, T, Custom);
 144     if (Subtarget->hasUnimplementedSIMD128())
 145       for (auto T: {MVT::v2i64, MVT::v2f64})
 146         setOperationAction(ISD::VECTOR_SHUFFLE, T, Custom);
 147
 148     // Custom lowering since wasm shifts must have a scalar shift amount
 149     for (auto Op : {ISD::SHL, ISD::SRA, ISD::SRL}) {
 150       for (auto T : {MVT::v16i8, MVT::v8i16, MVT::v4i32})
 151         setOperationAction(Op, T, Custom);
 152       if (Subtarget->hasUnimplementedSIMD128())
 153         setOperationAction(Op, MVT::v2i64, Custom);
 154     }
 155
 156     // Custom lower lane accesses to expand out variable indices
 157     for (auto Op : {ISD::EXTRACT_VECTOR_ELT, ISD::INSERT_VECTOR_ELT}) {
 158       for (auto T : {MVT::v16i8, MVT::v8i16, MVT::v4i32, MVT::v4f32})
 159         setOperationAction(Op, T, Custom);
 160       if (Subtarget->hasUnimplementedSIMD128())
 161         for (auto T : {MVT::v2i64, MVT::v2f64})
 162           setOperationAction(Op, T, Custom);
 163     }
 164
 165     // There is no i64x2.mul instruction
 166     setOperationAction(ISD::MUL, MVT::v2i64, Expand);
 167
 168     // There are no vector select instructions
 169     for (auto Op : {ISD::VSELECT, ISD::SELECT_CC, ISD::SELECT}) {
 170       for (auto T : {MVT::v16i8, MVT::v8i16, MVT::v4i32, MVT::v4f32})
 171         setOperationAction(Op, T, Expand);
 172       if (Subtarget->hasUnimplementedSIMD128())
 173         for (auto T : {MVT::v2i64, MVT::v2f64})
 174           setOperationAction(Op, T, Expand);
 175     }
 176
 177     // Expand integer operations supported for scalars but not SIMD
 178     for (auto Op : {ISD::CTLZ, ISD::CTTZ, ISD::CTPOP, ISD::SDIV, ISD::UDIV,
 179                     ISD::SREM, ISD::UREM, ISD::ROTL, ISD::ROTR}) {
 180       for (auto T : {MVT::v16i8, MVT::v8i16, MVT::v4i32})
 181         setOperationAction(Op, T, Expand);
 182       if (Subtarget->hasUnimplementedSIMD128())
 183         setOperationAction(Op, MVT::v2i64, Expand);
 184     }
 185
 186     // Expand float operations supported for scalars but not SIMD
 187     for (auto Op : {ISD::FCEIL, ISD::FFLOOR, ISD::FTRUNC, ISD::FNEARBYINT,
 188                     ISD::FCOPYSIGN}) {
 189       setOperationAction(Op, MVT::v4f32, Expand);
 190       if (Subtarget->hasUnimplementedSIMD128())
 191         setOperationAction(Op, MVT::v2f64, Expand);
 192     }
 193
 194     // Expand additional SIMD ops that V8 hasn't implemented yet
 195     if (!Subtarget->hasUnimplementedSIMD128()) {
 196       setOperationAction(ISD::FSQRT, MVT::v4f32, Expand);
 197       setOperationAction(ISD::FDIV, MVT::v4f32, Expand);
 198     }
 199   }
 200
 201   // As a special case, these operators use the type to mean the type to
 202   // sign-extend from.
 203   setOperationAction(ISD::SIGN_EXTEND_INREG, MVT::i1, Expand);
 204   if (!Subtarget->hasSignExt()) {
 205     // Sign extends are legal only when extending a vector extract
 206     auto Action = Subtarget->hasSIMD128() ? Custom : Expand;
 207     for (auto T : {MVT::i8, MVT::i16, MVT::i32})
 208       setOperationAction(ISD::SIGN_EXTEND_INREG, T, Action);
 209   }
 210   for (auto T : MVT::integer_vector_valuetypes())
 211     setOperationAction(ISD::SIGN_EXTEND_INREG, T, Expand);
 212
 213   // Dynamic stack allocation: use the default expansion.
 214   setOperationAction(ISD::STACKSAVE, MVT::Other, Expand);
 215   setOperationAction(ISD::STACKRESTORE, MVT::Other, Expand);
 216   setOperationAction(ISD::DYNAMIC_STACKALLOC, MVTPtr, Expand);
 217
 218   setOperationAction(ISD::FrameIndex, MVT::i32, Custom);
 219   setOperationAction(ISD::CopyToReg, MVT::Other, Custom);
 220
 221   // Expand these forms; we pattern-match the forms that we can handle in isel.
 222   for (auto T : {MVT::i32, MVT::i64, MVT::f32, MVT::f64})
 223     for (auto Op : {ISD::BR_CC, ISD::SELECT_CC})
 224       setOperationAction(Op, T, Expand);
 225
 226   // We have custom switch handling.
 227   setOperationAction(ISD::BR_JT, MVT::Other, Custom);
 228
 229   // WebAssembly doesn't have:
 230   //  - Floating-point extending loads.
 231   //  - Floating-point truncating stores.
 232   //  - i1 extending loads.
 233   //  - extending/truncating SIMD loads/stores
 234   setLoadExtAction(ISD::EXTLOAD, MVT::f64, MVT::f32, Expand);
 235   setTruncStoreAction(MVT::f64, MVT::f32, Expand);
 236   for (auto T : MVT::integer_valuetypes())
 237     for (auto Ext : {ISD::EXTLOAD, ISD::ZEXTLOAD, ISD::SEXTLOAD})
 238       setLoadExtAction(Ext, T, MVT::i1, Promote);
 239   if (Subtarget->hasSIMD128()) {
 240     for (auto T : {MVT::v16i8, MVT::v8i16, MVT::v4i32, MVT::v2i64, MVT::v4f32,
 241                    MVT::v2f64}) {
 242       for (auto MemT : MVT::vector_valuetypes()) {
 243         if (MVT(T) != MemT) {
 244           setTruncStoreAction(T, MemT, Expand);
 245           for (auto Ext : {ISD::EXTLOAD, ISD::ZEXTLOAD, ISD::SEXTLOAD})
 246             setLoadExtAction(Ext, T, MemT, Expand);
 247         }
 248       }
 249     }
 250   }
 251
 252   // Don't do anything clever with build_pairs
 253   setOperationAction(ISD::BUILD_PAIR, MVT::i64, Expand);
 254
 255   // Trap lowers to wasm unreachable
 256   setOperationAction(ISD::TRAP, MVT::Other, Legal);
 257
 258   // Exception handling intrinsics
 259   setOperationAction(ISD::INTRINSIC_WO_CHAIN, MVT::Other, Custom);
 260   setOperationAction(ISD::INTRINSIC_VOID, MVT::Other, Custom);
 261
 262   setMaxAtomicSizeInBitsSupported(64);
 263
 264   if (Subtarget->hasBulkMemory()) {
 265     // Use memory.copy and friends over multiple loads and stores
 266     MaxStoresPerMemcpy = 1;
 267     MaxStoresPerMemcpyOptSize = 1;
 268     MaxStoresPerMemmove = 1;
 269     MaxStoresPerMemmoveOptSize = 1;
 270     MaxStoresPerMemset = 1;
 271     MaxStoresPerMemsetOptSize = 1;
 272   }
 273 }
 274
 275 TargetLowering::AtomicExpansionKind
 276 WebAssemblyTargetLowering::shouldExpandAtomicRMWInIR(AtomicRMWInst *AI) const {
 277   // We have wasm instructions for these
 278   switch (AI->getOperation()) {
 279   case AtomicRMWInst::Add:
 280   case AtomicRMWInst::Sub:
 281   case AtomicRMWInst::And:
 282   case AtomicRMWInst::Or:
 283   case AtomicRMWInst::Xor:
 284   case AtomicRMWInst::Xchg:
 285     return AtomicExpansionKind::None;
 286   default:
 287     break;
 288   }
 289   return AtomicExpansionKind::CmpXChg;
 290 }
 291
 292 FastISel *WebAssemblyTargetLowering::createFastISel(
 293     FunctionLoweringInfo &FuncInfo, const TargetLibraryInfo *LibInfo) const {
 294   return WebAssembly::createFastISel(FuncInfo, LibInfo);
 295 }
 296
 297 bool WebAssemblyTargetLowering::isOffsetFoldingLegal(
 298     const GlobalAddressSDNode * /*GA*/) const {
 299   // All offsets can be folded.
 300   return true;
 301 }
 302
 303 MVT WebAssemblyTargetLowering::getScalarShiftAmountTy(const DataLayout & /*DL*/,
 304                                                       EVT VT) const {
 305   unsigned BitWidth = NextPowerOf2(VT.getSizeInBits() - 1);
 306   if (BitWidth > 1 && BitWidth < 8)
 307     BitWidth = 8;
 308
 309   if (BitWidth > 64) {
 310     // The shift will be lowered to a libcall, and compiler-rt libcalls expect
 311     // the count to be an i32.
 312     BitWidth = 32;
 313     assert(BitWidth >= Log2_32_Ceil(VT.getSizeInBits()) &&
 314            "32-bit shift counts ought to be enough for anyone");
 315   }
 316
 317   MVT Result = MVT::getIntegerVT(BitWidth);
 318   assert(Result != MVT::INVALID_SIMPLE_VALUE_TYPE &&
 319          "Unable to represent scalar shift amount type");
 320   return Result;
 321 }
 322
 323 // Lower an fp-to-int conversion operator from the LLVM opcode, which has an
 324 // undefined result on invalid/overflow, to the WebAssembly opcode, which
 325 // traps on invalid/overflow.
 326 static MachineBasicBlock *LowerFPToInt(MachineInstr &MI, DebugLoc DL,
 327                                        MachineBasicBlock *BB,
 328                                        const TargetInstrInfo &TII,
 329                                        bool IsUnsigned, bool Int64,
 330                                        bool Float64, unsigned LoweredOpcode) {
 331   MachineRegisterInfo &MRI = BB->getParent()->getRegInfo();
 332
 333   unsigned OutReg = MI.getOperand(0).getReg();
 334   unsigned InReg = MI.getOperand(1).getReg();
 335
 336   unsigned Abs = Float64 ? WebAssembly::ABS_F64 : WebAssembly::ABS_F32;
 337   unsigned FConst = Float64 ? WebAssembly::CONST_F64 : WebAssembly::CONST_F32;
 338   unsigned LT = Float64 ? WebAssembly::LT_F64 : WebAssembly::LT_F32;
 339   unsigned GE = Float64 ? WebAssembly::GE_F64 : WebAssembly::GE_F32;
 340   unsigned IConst = Int64 ? WebAssembly::CONST_I64 : WebAssembly::CONST_I32;
 341   unsigned Eqz = WebAssembly::EQZ_I32;
 342   unsigned And = WebAssembly::AND_I32;
 343   int64_t Limit = Int64 ? INT64_MIN : INT32_MIN;
 344   int64_t Substitute = IsUnsigned ? 0 : Limit;
 345   double CmpVal = IsUnsigned ? -(double)Limit * 2.0 : -(double)Limit;
 346   auto &Context = BB->getParent()->getFunction().getContext();
 347   Type *Ty = Float64 ? Type::getDoubleTy(Context) : Type::getFloatTy(Context);
 348
 349   const BasicBlock *LLVMBB = BB->getBasicBlock();
 350   MachineFunction *F = BB->getParent();
 351   MachineBasicBlock *TrueMBB = F->CreateMachineBasicBlock(LLVMBB);
 352   MachineBasicBlock *FalseMBB = F->CreateMachineBasicBlock(LLVMBB);
 353   MachineBasicBlock *DoneMBB = F->CreateMachineBasicBlock(LLVMBB);
 354
 355   MachineFunction::iterator It = ++BB->getIterator();
 356   F->insert(It, FalseMBB);
 357   F->insert(It, TrueMBB);
 358   F->insert(It, DoneMBB);
 359
 360   // Transfer the remainder of BB and its successor edges to DoneMBB.
 361   DoneMBB->splice(DoneMBB->begin(), BB, std::next(MI.getIterator()), BB->end());
 362   DoneMBB->transferSuccessorsAndUpdatePHIs(BB);
 363
 364   BB->addSuccessor(TrueMBB);
 365   BB->addSuccessor(FalseMBB);
 366   TrueMBB->addSuccessor(DoneMBB);
 367   FalseMBB->addSuccessor(DoneMBB);
 368
 369   unsigned Tmp0, Tmp1, CmpReg, EqzReg, FalseReg, TrueReg;
 370   Tmp0 = MRI.createVirtualRegister(MRI.getRegClass(InReg));
 371   Tmp1 = MRI.createVirtualRegister(MRI.getRegClass(InReg));
 372   CmpReg = MRI.createVirtualRegister(&WebAssembly::I32RegClass);
 373   EqzReg = MRI.createVirtualRegister(&WebAssembly::I32RegClass);
 374   FalseReg = MRI.createVirtualRegister(MRI.getRegClass(OutReg));
 375   TrueReg = MRI.createVirtualRegister(MRI.getRegClass(OutReg));
 376
 377   MI.eraseFromParent();
 378   // For signed numbers, we can do a single comparison to determine whether
 379   // fabs(x) is within range.
 380   if (IsUnsigned) {
 381     Tmp0 = InReg;
 382   } else {
 383     BuildMI(BB, DL, TII.get(Abs), Tmp0).addReg(InReg);
 384   }
 385   BuildMI(BB, DL, TII.get(FConst), Tmp1)
 386       .addFPImm(cast<ConstantFP>(ConstantFP::get(Ty, CmpVal)));
 387   BuildMI(BB, DL, TII.get(LT), CmpReg).addReg(Tmp0).addReg(Tmp1);
 388
 389   // For unsigned numbers, we have to do a separate comparison with zero.
 390   if (IsUnsigned) {
 391     Tmp1 = MRI.createVirtualRegister(MRI.getRegClass(InReg));
 392     unsigned SecondCmpReg =
 393         MRI.createVirtualRegister(&WebAssembly::I32RegClass);
 394     unsigned AndReg = MRI.createVirtualRegister(&WebAssembly::I32RegClass);
 395     BuildMI(BB, DL, TII.get(FConst), Tmp1)
 396         .addFPImm(cast<ConstantFP>(ConstantFP::get(Ty, 0.0)));
 397     BuildMI(BB, DL, TII.get(GE), SecondCmpReg).addReg(Tmp0).addReg(Tmp1);
 398     BuildMI(BB, DL, TII.get(And), AndReg).addReg(CmpReg).addReg(SecondCmpReg);
 399     CmpReg = AndReg;
 400   }
 401
 402   BuildMI(BB, DL, TII.get(Eqz), EqzReg).addReg(CmpReg);
 403
 404   // Create the CFG diamond to select between doing the conversion or using
 405   // the substitute value.
 406   BuildMI(BB, DL, TII.get(WebAssembly::BR_IF)).addMBB(TrueMBB).addReg(EqzReg);
 407   BuildMI(FalseMBB, DL, TII.get(LoweredOpcode), FalseReg).addReg(InReg);
 408   BuildMI(FalseMBB, DL, TII.get(WebAssembly::BR)).addMBB(DoneMBB);
 409   BuildMI(TrueMBB, DL, TII.get(IConst), TrueReg).addImm(Substitute);
 410   BuildMI(*DoneMBB, DoneMBB->begin(), DL, TII.get(TargetOpcode::PHI), OutReg)
 411       .addReg(FalseReg)
 412       .addMBB(FalseMBB)
 413       .addReg(TrueReg)
 414       .addMBB(TrueMBB);
 415
 416   return DoneMBB;
 417 }
 418
 419 MachineBasicBlock *WebAssemblyTargetLowering::EmitInstrWithCustomInserter(
 420     MachineInstr &MI, MachineBasicBlock *BB) const {
 421   const TargetInstrInfo &TII = *Subtarget->getInstrInfo();
 422   DebugLoc DL = MI.getDebugLoc();
 423
 424   switch (MI.getOpcode()) {
 425   default:
 426     llvm_unreachable("Unexpected instr type to insert");
 427   case WebAssembly::FP_TO_SINT_I32_F32:
 428     return LowerFPToInt(MI, DL, BB, TII, false, false, false,
 429                         WebAssembly::I32_TRUNC_S_F32);
 430   case WebAssembly::FP_TO_UINT_I32_F32:
 431     return LowerFPToInt(MI, DL, BB, TII, true, false, false,
 432                         WebAssembly::I32_TRUNC_U_F32);
 433   case WebAssembly::FP_TO_SINT_I64_F32:
 434     return LowerFPToInt(MI, DL, BB, TII, false, true, false,
 435                         WebAssembly::I64_TRUNC_S_F32);
 436   case WebAssembly::FP_TO_UINT_I64_F32:
 437     return LowerFPToInt(MI, DL, BB, TII, true, true, false,
 438                         WebAssembly::I64_TRUNC_U_F32);
 439   case WebAssembly::FP_TO_SINT_I32_F64:
 440     return LowerFPToInt(MI, DL, BB, TII, false, false, true,
 441                         WebAssembly::I32_TRUNC_S_F64);
 442   case WebAssembly::FP_TO_UINT_I32_F64:
 443     return LowerFPToInt(MI, DL, BB, TII, true, false, true,
 444                         WebAssembly::I32_TRUNC_U_F64);
 445   case WebAssembly::FP_TO_SINT_I64_F64:
 446     return LowerFPToInt(MI, DL, BB, TII, false, true, true,
 447                         WebAssembly::I64_TRUNC_S_F64);
 448   case WebAssembly::FP_TO_UINT_I64_F64:
 449     return LowerFPToInt(MI, DL, BB, TII, true, true, true,
 450                         WebAssembly::I64_TRUNC_U_F64);
 451     llvm_unreachable("Unexpected instruction to emit with custom inserter");
 452   }
 453 }
 454
 455 const char *
 456 WebAssemblyTargetLowering::getTargetNodeName(unsigned Opcode) const {
 457   switch (static_cast<WebAssemblyISD::NodeType>(Opcode)) {
 458   case WebAssemblyISD::FIRST_NUMBER:
 459     break;
 460 #define HANDLE_NODETYPE(NODE)                                                  \
 461   case WebAssemblyISD::NODE:                                                   \
 462     return "WebAssemblyISD::" #NODE;
 463 #include "WebAssemblyISD.def"
 464 #undef HANDLE_NODETYPE
 465   }
 466   return nullptr;
 467 }
 468
 469 std::pair<unsigned, const TargetRegisterClass *>
 470 WebAssemblyTargetLowering::getRegForInlineAsmConstraint(
 471     const TargetRegisterInfo *TRI, StringRef Constraint, MVT VT) const {
 472   // First, see if this is a constraint that directly corresponds to a
 473   // WebAssembly register class.
 474   if (Constraint.size() == 1) {
 475     switch (Constraint[0]) {
 476     case 'r':
 477       assert(VT != MVT::iPTR && "Pointer MVT not expected here");
 478       if (Subtarget->hasSIMD128() && VT.isVector()) {
 479         if (VT.getSizeInBits() == 128)
 480           return std::make_pair(0U, &WebAssembly::V128RegClass);
 481       }
 482       if (VT.isInteger() && !VT.isVector()) {
 483         if (VT.getSizeInBits() <= 32)
 484           return std::make_pair(0U, &WebAssembly::I32RegClass);
 485         if (VT.getSizeInBits() <= 64)
 486           return std::make_pair(0U, &WebAssembly::I64RegClass);
 487       }
 488       break;
 489     default:
 490       break;
 491     }
 492   }
 493
 494   return TargetLowering::getRegForInlineAsmConstraint(TRI, Constraint, VT);
 495 }
 496
 497 bool WebAssemblyTargetLowering::isCheapToSpeculateCttz() const {
 498   // Assume ctz is a relatively cheap operation.
 499   return true;
 500 }
 501
 502 bool WebAssemblyTargetLowering::isCheapToSpeculateCtlz() const {
 503   // Assume clz is a relatively cheap operation.
 504   return true;
 505 }
 506
 507 bool WebAssemblyTargetLowering::isLegalAddressingMode(const DataLayout &DL,
 508                                                       const AddrMode &AM,
 509                                                       Type *Ty, unsigned AS,
 510                                                       Instruction *I) const {
 511   // WebAssembly offsets are added as unsigned without wrapping. The
 512   // isLegalAddressingMode gives us no way to determine if wrapping could be
 513   // happening, so we approximate this by accepting only non-negative offsets.
 514   if (AM.BaseOffs < 0)
 515     return false;
 516
 517   // WebAssembly has no scale register operands.
 518   if (AM.Scale != 0)
 519     return false;
 520
 521   // Everything else is legal.
 522   return true;
 523 }
 524
 525 bool WebAssemblyTargetLowering::allowsMisalignedMemoryAccesses(
 526     EVT /*VT*/, unsigned /*AddrSpace*/, unsigned /*Align*/, bool *Fast) const {
 527   // WebAssembly supports unaligned accesses, though it should be declared
 528   // with the p2align attribute on loads and stores which do so, and there
 529   // may be a performance impact. We tell LLVM they're "fast" because
 530   // for the kinds of things that LLVM uses this for (merging adjacent stores
 531   // of constants, etc.), WebAssembly implementations will either want the
 532   // unaligned access or they'll split anyway.
 533   if (Fast)
 534     *Fast = true;
 535   return true;
 536 }
 537
 538 bool WebAssemblyTargetLowering::isIntDivCheap(EVT VT,
 539                                               AttributeList Attr) const {
 540   // The current thinking is that wasm engines will perform this optimization,
 541   // so we can save on code size.
 542   return true;
 543 }
 544
 545 EVT WebAssemblyTargetLowering::getSetCCResultType(const DataLayout &DL,
 546                                                   LLVMContext &C,
 547                                                   EVT VT) const {
 548   if (VT.isVector())
 549     return VT.changeVectorElementTypeToInteger();
 550
 551   return TargetLowering::getSetCCResultType(DL, C, VT);
 552 }
 553
 554 bool WebAssemblyTargetLowering::getTgtMemIntrinsic(IntrinsicInfo &Info,
 555                                                    const CallInst &I,
 556                                                    MachineFunction &MF,
 557                                                    unsigned Intrinsic) const {
 558   switch (Intrinsic) {
 559   case Intrinsic::wasm_atomic_notify:
 560     Info.opc = ISD::INTRINSIC_W_CHAIN;
 561     Info.memVT = MVT::i32;
 562     Info.ptrVal = I.getArgOperand(0);
 563     Info.offset = 0;
 564     Info.align = 4;
 565     // atomic.notify instruction does not really load the memory specified with
 566     // this argument, but MachineMemOperand should either be load or store, so
 567     // we set this to a load.
 568     // FIXME Volatile isn't really correct, but currently all LLVM atomic
 569     // instructions are treated as volatiles in the backend, so we should be
 570     // consistent. The same applies for wasm_atomic_wait intrinsics too.
 571     Info.flags = MachineMemOperand::MOVolatile | MachineMemOperand::MOLoad;
 572     return true;
 573   case Intrinsic::wasm_atomic_wait_i32:
 574     Info.opc = ISD::INTRINSIC_W_CHAIN;
 575     Info.memVT = MVT::i32;
 576     Info.ptrVal = I.getArgOperand(0);
 577     Info.offset = 0;
 578     Info.align = 4;
 579     Info.flags = MachineMemOperand::MOVolatile | MachineMemOperand::MOLoad;
 580     return true;
 581   case Intrinsic::wasm_atomic_wait_i64:
 582     Info.opc = ISD::INTRINSIC_W_CHAIN;
 583     Info.memVT = MVT::i64;
 584     Info.ptrVal = I.getArgOperand(0);
 585     Info.offset = 0;
 586     Info.align = 8;
 587     Info.flags = MachineMemOperand::MOVolatile | MachineMemOperand::MOLoad;
 588     return true;
 589   default:
 590     return false;
 591   }
 592 }
 593
 594 //===----------------------------------------------------------------------===//
 595 // WebAssembly Lowering private implementation.
 596 //===----------------------------------------------------------------------===//
 597
 598 //===----------------------------------------------------------------------===//
 599 // Lowering Code
 600 //===----------------------------------------------------------------------===//
 601
 602 static void fail(const SDLoc &DL, SelectionDAG &DAG, const char *Msg) {
 603   MachineFunction &MF = DAG.getMachineFunction();
 604   DAG.getContext()->diagnose(
 605       DiagnosticInfoUnsupported(MF.getFunction(), Msg, DL.getDebugLoc()));
 606 }
 607
 608 // Test whether the given calling convention is supported.
 609 static bool callingConvSupported(CallingConv::ID CallConv) {
 610   // We currently support the language-independent target-independent
 611   // conventions. We don't yet have a way to annotate calls with properties like
 612   // "cold", and we don't have any call-clobbered registers, so these are mostly
 613   // all handled the same.
 614   return CallConv == CallingConv::C || CallConv == CallingConv::Fast ||
 615          CallConv == CallingConv::Cold ||
 616          CallConv == CallingConv::PreserveMost ||
 617          CallConv == CallingConv::PreserveAll ||
 618          CallConv == CallingConv::CXX_FAST_TLS;
 619 }
 620
 621 SDValue
 622 WebAssemblyTargetLowering::LowerCall(CallLoweringInfo &CLI,
 623                                      SmallVectorImpl<SDValue> &InVals) const {
 624   SelectionDAG &DAG = CLI.DAG;
 625   SDLoc DL = CLI.DL;
 626   SDValue Chain = CLI.Chain;
 627   SDValue Callee = CLI.Callee;
 628   MachineFunction &MF = DAG.getMachineFunction();
 629   auto Layout = MF.getDataLayout();
 630
 631   CallingConv::ID CallConv = CLI.CallConv;
 632   if (!callingConvSupported(CallConv))
 633     fail(DL, DAG,
 634          "WebAssembly doesn't support language-specific or target-specific "
 635          "calling conventions yet");
 636   if (CLI.IsPatchPoint)
 637     fail(DL, DAG, "WebAssembly doesn't support patch point yet");
 638
 639   // WebAssembly doesn't currently support explicit tail calls. If they are
 640   // required, fail. Otherwise, just disable them.
 641   if ((CallConv == CallingConv::Fast && CLI.IsTailCall &&
 642        MF.getTarget().Options.GuaranteedTailCallOpt) ||
 643       (CLI.CS && CLI.CS.isMustTailCall()))
 644     fail(DL, DAG, "WebAssembly doesn't support tail call yet");
 645   CLI.IsTailCall = false;
 646
 647   SmallVectorImpl<ISD::InputArg> &Ins = CLI.Ins;
 648   if (Ins.size() > 1)
 649     fail(DL, DAG, "WebAssembly doesn't support more than 1 returned value yet");
 650
 651   SmallVectorImpl<ISD::OutputArg> &Outs = CLI.Outs;
 652   SmallVectorImpl<SDValue> &OutVals = CLI.OutVals;
 653   unsigned NumFixedArgs = 0;
 654   for (unsigned I = 0; I < Outs.size(); ++I) {
 655     const ISD::OutputArg &Out = Outs[I];
 656     SDValue &OutVal = OutVals[I];
 657     if (Out.Flags.isNest())
 658       fail(DL, DAG, "WebAssembly hasn't implemented nest arguments");
 659     if (Out.Flags.isInAlloca())
 660       fail(DL, DAG, "WebAssembly hasn't implemented inalloca arguments");
 661     if (Out.Flags.isInConsecutiveRegs())
 662       fail(DL, DAG, "WebAssembly hasn't implemented cons regs arguments");
 663     if (Out.Flags.isInConsecutiveRegsLast())
 664       fail(DL, DAG, "WebAssembly hasn't implemented cons regs last arguments");
 665     if (Out.Flags.isByVal() && Out.Flags.getByValSize() != 0) {
 666       auto &MFI = MF.getFrameInfo();
 667       int FI = MFI.CreateStackObject(Out.Flags.getByValSize(),
 668                                      Out.Flags.getByValAlign(),
 669                                      /*isSS=*/false);
 670       SDValue SizeNode =
 671           DAG.getConstant(Out.Flags.getByValSize(), DL, MVT::i32);
 672       SDValue FINode = DAG.getFrameIndex(FI, getPointerTy(Layout));
 673       Chain = DAG.getMemcpy(
 674           Chain, DL, FINode, OutVal, SizeNode, Out.Flags.getByValAlign(),
 675           /*isVolatile*/ false, /*AlwaysInline=*/false,
 676           /*isTailCall*/ false, MachinePointerInfo(), MachinePointerInfo());
 677       OutVal = FINode;
 678     }
 679     // Count the number of fixed args *after* legalization.
 680     NumFixedArgs += Out.IsFixed;
 681   }
 682
 683   bool IsVarArg = CLI.IsVarArg;
 684   auto PtrVT = getPointerTy(Layout);
 685
 686   // Analyze operands of the call, assigning locations to each operand.
 687   SmallVector<CCValAssign, 16> ArgLocs;
 688   CCState CCInfo(CallConv, IsVarArg, MF, ArgLocs, *DAG.getContext());
 689
 690   if (IsVarArg) {
 691     // Outgoing non-fixed arguments are placed in a buffer. First
 692     // compute their offsets and the total amount of buffer space needed.
 693     for (unsigned I = NumFixedArgs; I < Outs.size(); ++I) {
 694       const ISD::OutputArg &Out = Outs[I];
 695       SDValue &Arg = OutVals[I];
 696       EVT VT = Arg.getValueType();
 697       assert(VT != MVT::iPTR && "Legalized args should be concrete");
 698       Type *Ty = VT.getTypeForEVT(*DAG.getContext());
 699       unsigned Align = std::max(Out.Flags.getOrigAlign(),
 700                                 Layout.getABITypeAlignment(Ty));
 701       unsigned Offset = CCInfo.AllocateStack(Layout.getTypeAllocSize(Ty),
 702                                              Align);
 703       CCInfo.addLoc(CCValAssign::getMem(ArgLocs.size(), VT.getSimpleVT(),
 704                                         Offset, VT.getSimpleVT(),
 705                                         CCValAssign::Full));
 706     }
 707   }
 708
 709   unsigned NumBytes = CCInfo.getAlignedCallFrameSize();
 710
 711   SDValue FINode;
 712   if (IsVarArg && NumBytes) {
 713     // For non-fixed arguments, next emit stores to store the argument values
 714     // to the stack buffer at the offsets computed above.
 715     int FI = MF.getFrameInfo().CreateStackObject(NumBytes,
 716                                                  Layout.getStackAlignment(),
 717                                                  /*isSS=*/false);
 718     unsigned ValNo = 0;
 719     SmallVector<SDValue, 8> Chains;
 720     for (SDValue Arg :
 721          make_range(OutVals.begin() + NumFixedArgs, OutVals.end())) {
 722       assert(ArgLocs[ValNo].getValNo() == ValNo &&
 723              "ArgLocs should remain in order and only hold varargs args");
 724       unsigned Offset = ArgLocs[ValNo++].getLocMemOffset();
 725       FINode = DAG.getFrameIndex(FI, getPointerTy(Layout));
 726       SDValue Add = DAG.getNode(ISD::ADD, DL, PtrVT, FINode,
 727                                 DAG.getConstant(Offset, DL, PtrVT));
 728       Chains.push_back(
 729           DAG.getStore(Chain, DL, Arg, Add,
 730                        MachinePointerInfo::getFixedStack(MF, FI, Offset), 0));
 731     }
 732     if (!Chains.empty())
 733       Chain = DAG.getNode(ISD::TokenFactor, DL, MVT::Other, Chains);
 734   } else if (IsVarArg) {
 735     FINode = DAG.getIntPtrConstant(0, DL);
 736   }
 737
 738   // Compute the operands for the CALLn node.
 739   SmallVector<SDValue, 16> Ops;
 740   Ops.push_back(Chain);
 741   Ops.push_back(Callee);
 742
 743   // Add all fixed arguments. Note that for non-varargs calls, NumFixedArgs
 744   // isn't reliable.
 745   Ops.append(OutVals.begin(),
 746              IsVarArg ? OutVals.begin() + NumFixedArgs : OutVals.end());
 747   // Add a pointer to the vararg buffer.
 748   if (IsVarArg)
 749     Ops.push_back(FINode);
 750
 751   SmallVector<EVT, 8> InTys;
 752   for (const auto &In : Ins) {
 753     assert(!In.Flags.isByVal() && "byval is not valid for return values");
 754     assert(!In.Flags.isNest() && "nest is not valid for return values");
 755     if (In.Flags.isInAlloca())
 756       fail(DL, DAG, "WebAssembly hasn't implemented inalloca return values");
 757     if (In.Flags.isInConsecutiveRegs())
 758       fail(DL, DAG, "WebAssembly hasn't implemented cons regs return values");
 759     if (In.Flags.isInConsecutiveRegsLast())
 760       fail(DL, DAG,
 761            "WebAssembly hasn't implemented cons regs last return values");
 762     // Ignore In.getOrigAlign() because all our arguments are passed in
 763     // registers.
 764     InTys.push_back(In.VT);
 765   }
 766   InTys.push_back(MVT::Other);
 767   SDVTList InTyList = DAG.getVTList(InTys);
 768   SDValue Res =
 769       DAG.getNode(Ins.empty() ? WebAssemblyISD::CALL0 : WebAssemblyISD::CALL1,
 770                   DL, InTyList, Ops);
 771   if (Ins.empty()) {
 772     Chain = Res;
 773   } else {
 774     InVals.push_back(Res);
 775     Chain = Res.getValue(1);
 776   }
 777
 778   return Chain;
 779 }
 780
 781 bool WebAssemblyTargetLowering::CanLowerReturn(
 782     CallingConv::ID /*CallConv*/, MachineFunction & /*MF*/, bool /*IsVarArg*/,
 783     const SmallVectorImpl<ISD::OutputArg> &Outs,
 784     LLVMContext & /*Context*/) const {
 785   // WebAssembly can't currently handle returning tuples.
 786   return Outs.size() <= 1;
 787 }
 788
 789 SDValue WebAssemblyTargetLowering::LowerReturn(
 790     SDValue Chain, CallingConv::ID CallConv, bool /*IsVarArg*/,
 791     const SmallVectorImpl<ISD::OutputArg> &Outs,
 792     const SmallVectorImpl<SDValue> &OutVals, const SDLoc &DL,
 793     SelectionDAG &DAG) const {
 794   assert(Outs.size() <= 1 && "WebAssembly can only return up to one value");
 795   if (!callingConvSupported(CallConv))
 796     fail(DL, DAG, "WebAssembly doesn't support non-C calling conventions");
 797
 798   SmallVector<SDValue, 4> RetOps(1, Chain);
 799   RetOps.append(OutVals.begin(), OutVals.end());
 800   Chain = DAG.getNode(WebAssemblyISD::RETURN, DL, MVT::Other, RetOps);
 801
 802   // Record the number and types of the return values.
 803   for (const ISD::OutputArg &Out : Outs) {
 804     assert(!Out.Flags.isByVal() && "byval is not valid for return values");
 805     assert(!Out.Flags.isNest() && "nest is not valid for return values");
 806     assert(Out.IsFixed && "non-fixed return value is not valid");
 807     if (Out.Flags.isInAlloca())
 808       fail(DL, DAG, "WebAssembly hasn't implemented inalloca results");
 809     if (Out.Flags.isInConsecutiveRegs())
 810       fail(DL, DAG, "WebAssembly hasn't implemented cons regs results");
 811     if (Out.Flags.isInConsecutiveRegsLast())
 812       fail(DL, DAG, "WebAssembly hasn't implemented cons regs last results");
 813   }
 814
 815   return Chain;
 816 }
 817
 818 SDValue WebAssemblyTargetLowering::LowerFormalArguments(
 819     SDValue Chain, CallingConv::ID CallConv, bool IsVarArg,
 820     const SmallVectorImpl<ISD::InputArg> &Ins, const SDLoc &DL,
 821     SelectionDAG &DAG, SmallVectorImpl<SDValue> &InVals) const {
 822   if (!callingConvSupported(CallConv))
 823     fail(DL, DAG, "WebAssembly doesn't support non-C calling conventions");
 824
 825   MachineFunction &MF = DAG.getMachineFunction();
 826   auto *MFI = MF.getInfo<WebAssemblyFunctionInfo>();
 827
 828   // Set up the incoming ARGUMENTS value, which serves to represent the liveness
 829   // of the incoming values before they're represented by virtual registers.
 830   MF.getRegInfo().addLiveIn(WebAssembly::ARGUMENTS);
 831
 832   for (const ISD::InputArg &In : Ins) {
 833     if (In.Flags.isInAlloca())
 834       fail(DL, DAG, "WebAssembly hasn't implemented inalloca arguments");
 835     if (In.Flags.isNest())
 836       fail(DL, DAG, "WebAssembly hasn't implemented nest arguments");
 837     if (In.Flags.isInConsecutiveRegs())
 838       fail(DL, DAG, "WebAssembly hasn't implemented cons regs arguments");
 839     if (In.Flags.isInConsecutiveRegsLast())
 840       fail(DL, DAG, "WebAssembly hasn't implemented cons regs last arguments");
 841     // Ignore In.getOrigAlign() because all our arguments are passed in
 842     // registers.
 843     InVals.push_back(In.Used ? DAG.getNode(WebAssemblyISD::ARGUMENT, DL, In.VT,
 844                                            DAG.getTargetConstant(InVals.size(),
 845                                                                  DL, MVT::i32))
 846                              : DAG.getUNDEF(In.VT));
 847
 848     // Record the number and types of arguments.
 849     MFI->addParam(In.VT);
 850   }
 851
 852   // Varargs are copied into a buffer allocated by the caller, and a pointer to
 853   // the buffer is passed as an argument.
 854   if (IsVarArg) {
 855     MVT PtrVT = getPointerTy(MF.getDataLayout());
 856     unsigned VarargVreg =
 857         MF.getRegInfo().createVirtualRegister(getRegClassFor(PtrVT));
 858     MFI->setVarargBufferVreg(VarargVreg);
 859     Chain = DAG.getCopyToReg(
 860         Chain, DL, VarargVreg,
 861         DAG.getNode(WebAssemblyISD::ARGUMENT, DL, PtrVT,
 862                     DAG.getTargetConstant(Ins.size(), DL, MVT::i32)));
 863     MFI->addParam(PtrVT);
 864   }
 865
 866   // Record the number and types of arguments and results.
 867   SmallVector<MVT, 4> Params;
 868   SmallVector<MVT, 4> Results;
 869   computeSignatureVTs(MF.getFunction().getFunctionType(), MF.getFunction(),
 870                       DAG.getTarget(), Params, Results);
 871   for (MVT VT : Results)
 872     MFI->addResult(VT);
 873   // TODO: Use signatures in WebAssemblyMachineFunctionInfo too and unify
 874   // the param logic here with ComputeSignatureVTs
 875   assert(MFI->getParams().size() == Params.size() &&
 876          std::equal(MFI->getParams().begin(), MFI->getParams().end(),
 877                     Params.begin()));
 878
 879   return Chain;
 880 }
 881
 882 //===----------------------------------------------------------------------===//
 883 //  Custom lowering hooks.
 884 //===----------------------------------------------------------------------===//
 885
 886 SDValue WebAssemblyTargetLowering::LowerOperation(SDValue Op,
 887                                                   SelectionDAG &DAG) const {
 888   SDLoc DL(Op);
 889   switch (Op.getOpcode()) {
 890   default:
 891     llvm_unreachable("unimplemented operation lowering");
 892     return SDValue();
 893   case ISD::FrameIndex:
 894     return LowerFrameIndex(Op, DAG);
 895   case ISD::GlobalAddress:
 896     return LowerGlobalAddress(Op, DAG);
 897   case ISD::ExternalSymbol:
 898     return LowerExternalSymbol(Op, DAG);
 899   case ISD::JumpTable:
 900     return LowerJumpTable(Op, DAG);
 901   case ISD::BR_JT:
 902     return LowerBR_JT(Op, DAG);
 903   case ISD::VASTART:
 904     return LowerVASTART(Op, DAG);
 905   case ISD::BlockAddress:
 906   case ISD::BRIND:
 907     fail(DL, DAG, "WebAssembly hasn't implemented computed gotos");
 908     return SDValue();
 909   case ISD::RETURNADDR: // Probably nothing meaningful can be returned here.
 910     fail(DL, DAG, "WebAssembly hasn't implemented __builtin_return_address");
 911     return SDValue();
 912   case ISD::FRAMEADDR:
 913     return LowerFRAMEADDR(Op, DAG);
 914   case ISD::CopyToReg:
 915     return LowerCopyToReg(Op, DAG);
 916   case ISD::EXTRACT_VECTOR_ELT:
 917   case ISD::INSERT_VECTOR_ELT:
 918     return LowerAccessVectorElement(Op, DAG);
 919   case ISD::INTRINSIC_VOID:
 920   case ISD::INTRINSIC_WO_CHAIN:
 921   case ISD::INTRINSIC_W_CHAIN:
 922     return LowerIntrinsic(Op, DAG);
 923   case ISD::SIGN_EXTEND_INREG:
 924     return LowerSIGN_EXTEND_INREG(Op, DAG);
 925   case ISD::BUILD_VECTOR:
 926     return LowerBUILD_VECTOR(Op, DAG);
 927   case ISD::VECTOR_SHUFFLE:
 928     return LowerVECTOR_SHUFFLE(Op, DAG);
 929   case ISD::SHL:
 930   case ISD::SRA:
 931   case ISD::SRL:
 932     return LowerShift(Op, DAG);
 933   }
 934 }
 935
 936 SDValue WebAssemblyTargetLowering::LowerCopyToReg(SDValue Op,
 937                                                   SelectionDAG &DAG) const {
 938   SDValue Src = Op.getOperand(2);
 939   if (isa<FrameIndexSDNode>(Src.getNode())) {
 940     // CopyToReg nodes don't support FrameIndex operands. Other targets select
 941     // the FI to some LEA-like instruction, but since we don't have that, we
 942     // need to insert some kind of instruction that can take an FI operand and
 943     // produces a value usable by CopyToReg (i.e. in a vreg). So insert a dummy
 944     // local.copy between Op and its FI operand.
 945     SDValue Chain = Op.getOperand(0);
 946     SDLoc DL(Op);
 947     unsigned Reg = cast<RegisterSDNode>(Op.getOperand(1))->getReg();
 948     EVT VT = Src.getValueType();
 949     SDValue Copy(DAG.getMachineNode(VT == MVT::i32 ? WebAssembly::COPY_I32
 950                                                    : WebAssembly::COPY_I64,
 951                                     DL, VT, Src),
 952                  0);
 953     return Op.getNode()->getNumValues() == 1
 954                ? DAG.getCopyToReg(Chain, DL, Reg, Copy)
 955                : DAG.getCopyToReg(Chain, DL, Reg, Copy,
 956                                   Op.getNumOperands() == 4 ? Op.getOperand(3)
 957                                                            : SDValue());
 958   }
 959   return SDValue();
 960 }
 961
 962 SDValue WebAssemblyTargetLowering::LowerFrameIndex(SDValue Op,
 963                                                    SelectionDAG &DAG) const {
 964   int FI = cast<FrameIndexSDNode>(Op)->getIndex();
 965   return DAG.getTargetFrameIndex(FI, Op.getValueType());
 966 }
 967
 968 SDValue WebAssemblyTargetLowering::LowerFRAMEADDR(SDValue Op,
 969                                                   SelectionDAG &DAG) const {
 970   // Non-zero depths are not supported by WebAssembly currently. Use the
 971   // legalizer's default expansion, which is to return 0 (what this function is
 972   // documented to do).
 973   if (Op.getConstantOperandVal(0) > 0)
 974     return SDValue();
 975
 976   DAG.getMachineFunction().getFrameInfo().setFrameAddressIsTaken(true);
 977   EVT VT = Op.getValueType();
 978   unsigned FP =
 979       Subtarget->getRegisterInfo()->getFrameRegister(DAG.getMachineFunction());
 980   return DAG.getCopyFromReg(DAG.getEntryNode(), SDLoc(Op), FP, VT);
 981 }
 982
 983 SDValue WebAssemblyTargetLowering::LowerGlobalAddress(SDValue Op,
 984                                                       SelectionDAG &DAG) const {
 985   SDLoc DL(Op);
 986   const auto *GA = cast<GlobalAddressSDNode>(Op);
 987   EVT VT = Op.getValueType();
 988   assert(GA->getTargetFlags() == 0 &&
 989          "Unexpected target flags on generic GlobalAddressSDNode");
 990   if (GA->getAddressSpace() != 0)
 991     fail(DL, DAG, "WebAssembly only expects the 0 address space");
 992   return DAG.getNode(
 993       WebAssemblyISD::Wrapper, DL, VT,
 994       DAG.getTargetGlobalAddress(GA->getGlobal(), DL, VT, GA->getOffset()));
 995 }
 996
 997 SDValue
 998 WebAssemblyTargetLowering::LowerExternalSymbol(SDValue Op,
 999                                                SelectionDAG &DAG) const {
1000   SDLoc DL(Op);
1001   const auto *ES = cast<ExternalSymbolSDNode>(Op);
1002   EVT VT = Op.getValueType();
1003   assert(ES->getTargetFlags() == 0 &&
1004          "Unexpected target flags on generic ExternalSymbolSDNode");
1005   // Set the TargetFlags to 0x1 which indicates that this is a "function"
1006   // symbol rather than a data symbol. We do this unconditionally even though
1007   // we don't know anything about the symbol other than its name, because all
1008   // external symbols used in target-independent SelectionDAG code are for
1009   // functions.
1010   return DAG.getNode(
1011       WebAssemblyISD::Wrapper, DL, VT,
1012       DAG.getTargetExternalSymbol(ES->getSymbol(), VT,
1013                                   WebAssemblyII::MO_SYMBOL_FUNCTION));
1014 }
1015
1016 SDValue WebAssemblyTargetLowering::LowerJumpTable(SDValue Op,
1017                                                   SelectionDAG &DAG) const {
1018   // There's no need for a Wrapper node because we always incorporate a jump
1019   // table operand into a BR_TABLE instruction, rather than ever
1020   // materializing it in a register.
1021   const JumpTableSDNode *JT = cast<JumpTableSDNode>(Op);
1022   return DAG.getTargetJumpTable(JT->getIndex(), Op.getValueType(),
1023                                 JT->getTargetFlags());
1024 }
1025
1026 SDValue WebAssemblyTargetLowering::LowerBR_JT(SDValue Op,
1027                                               SelectionDAG &DAG) const {
1028   SDLoc DL(Op);
1029   SDValue Chain = Op.getOperand(0);
1030   const auto *JT = cast<JumpTableSDNode>(Op.getOperand(1));
1031   SDValue Index = Op.getOperand(2);
1032   assert(JT->getTargetFlags() == 0 && "WebAssembly doesn't set target flags");
1033
1034   SmallVector<SDValue, 8> Ops;
1035   Ops.push_back(Chain);
1036   Ops.push_back(Index);
1037
1038   MachineJumpTableInfo *MJTI = DAG.getMachineFunction().getJumpTableInfo();
1039   const auto &MBBs = MJTI->getJumpTables()[JT->getIndex()].MBBs;
1040
1041   // Add an operand for each case.
1042   for (auto MBB : MBBs)
1043     Ops.push_back(DAG.getBasicBlock(MBB));
1044
1045   // TODO: For now, we just pick something arbitrary for a default case for now.
1046   // We really want to sniff out the guard and put in the real default case (and
1047   // delete the guard).
1048   Ops.push_back(DAG.getBasicBlock(MBBs[0]));
1049
1050   return DAG.getNode(WebAssemblyISD::BR_TABLE, DL, MVT::Other, Ops);
1051 }
1052
1053 SDValue WebAssemblyTargetLowering::LowerVASTART(SDValue Op,
1054                                                 SelectionDAG &DAG) const {
1055   SDLoc DL(Op);
1056   EVT PtrVT = getPointerTy(DAG.getMachineFunction().getDataLayout());
1057
1058   auto *MFI = DAG.getMachineFunction().getInfo<WebAssemblyFunctionInfo>();
1059   const Value *SV = cast<SrcValueSDNode>(Op.getOperand(2))->getValue();
1060
1061   SDValue ArgN = DAG.getCopyFromReg(DAG.getEntryNode(), DL,
1062                                     MFI->getVarargBufferVreg(), PtrVT);
1063   return DAG.getStore(Op.getOperand(0), DL, ArgN, Op.getOperand(1),
1064                       MachinePointerInfo(SV), 0);
1065 }
1066
1067 SDValue WebAssemblyTargetLowering::LowerIntrinsic(SDValue Op,
1068                                                   SelectionDAG &DAG) const {
1069   MachineFunction &MF = DAG.getMachineFunction();
1070   unsigned IntNo;
1071   switch (Op.getOpcode()) {
1072   case ISD::INTRINSIC_VOID:
1073   case ISD::INTRINSIC_W_CHAIN:
1074     IntNo = cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
1075     break;
1076   case ISD::INTRINSIC_WO_CHAIN:
1077     IntNo = cast<ConstantSDNode>(Op.getOperand(0))->getZExtValue();
1078     break;
1079   default:
1080     llvm_unreachable("Invalid intrinsic");
1081   }
1082   SDLoc DL(Op);
1083
1084   switch (IntNo) {
1085   default:
1086     return SDValue(); // Don't custom lower most intrinsics.
1087
1088   case Intrinsic::wasm_lsda: {
1089     EVT VT = Op.getValueType();
1090     const TargetLowering &TLI = DAG.getTargetLoweringInfo();
1091     MVT PtrVT = TLI.getPointerTy(DAG.getDataLayout());
1092     auto &Context = MF.getMMI().getContext();
1093     MCSymbol *S = Context.getOrCreateSymbol(Twine("GCC_except_table") +
1094                                             Twine(MF.getFunctionNumber()));
1095     return DAG.getNode(WebAssemblyISD::Wrapper, DL, VT,
1096                        DAG.getMCSymbol(S, PtrVT));
1097   }
1098
1099   case Intrinsic::wasm_throw: {
1100     // We only support C++ exceptions for now
1101     int Tag = cast<ConstantSDNode>(Op.getOperand(2).getNode())->getZExtValue();
1102     if (Tag != CPP_EXCEPTION)
1103       llvm_unreachable("Invalid tag!");
1104     const TargetLowering &TLI = DAG.getTargetLoweringInfo();
1105     MVT PtrVT = TLI.getPointerTy(DAG.getDataLayout());
1106     const char *SymName = MF.createExternalSymbolName("__cpp_exception");
1107     SDValue SymNode =
1108         DAG.getNode(WebAssemblyISD::Wrapper, DL, PtrVT,
1109                     DAG.getTargetExternalSymbol(
1110                         SymName, PtrVT, WebAssemblyII::MO_SYMBOL_EVENT));
1111     return DAG.getNode(WebAssemblyISD::THROW, DL,
1112                        MVT::Other, // outchain type
1113                        {
1114                            Op.getOperand(0), // inchain
1115                            SymNode,          // exception symbol
1116                            Op.getOperand(3)  // thrown value
1117                        });
1118   }
1119   }
1120 }
1121
1122 SDValue
1123 WebAssemblyTargetLowering::LowerSIGN_EXTEND_INREG(SDValue Op,
1124                                                   SelectionDAG &DAG) const {
1125   // If sign extension operations are disabled, allow sext_inreg only if operand
1126   // is a vector extract. SIMD does not depend on sign extension operations, but
1127   // allowing sext_inreg in this context lets us have simple patterns to select
1128   // extract_lane_s instructions. Expanding sext_inreg everywhere would be
1129   // simpler in this file, but would necessitate large and brittle patterns to
1130   // undo the expansion and select extract_lane_s instructions.
1131   assert(!Subtarget->hasSignExt() && Subtarget->hasSIMD128());
1132   if (Op.getOperand(0).getOpcode() == ISD::EXTRACT_VECTOR_ELT)
1133     return Op;
1134   // Otherwise expand
1135   return SDValue();
1136 }
1137
1138 SDValue WebAssemblyTargetLowering::LowerBUILD_VECTOR(SDValue Op,
1139                                                      SelectionDAG &DAG) const {
1140   SDLoc DL(Op);
1141   const EVT VecT = Op.getValueType();
1142   const EVT LaneT = Op.getOperand(0).getValueType();
1143   const size_t Lanes = Op.getNumOperands();
1144   auto IsConstant = [](const SDValue &V) {
1145     return V.getOpcode() == ISD::Constant || V.getOpcode() == ISD::ConstantFP;
1146   };
1147
1148   // Find the most common operand, which is approximately the best to splat
1149   using Entry = std::pair<SDValue, size_t>;
1150   SmallVector<Entry, 16> ValueCounts;
1151   size_t NumConst = 0, NumDynamic = 0;
1152   for (const SDValue &Lane : Op->op_values()) {
1153     if (Lane.isUndef()) {
1154       continue;
1155     } else if (IsConstant(Lane)) {
1156       NumConst++;
1157     } else {
1158       NumDynamic++;
1159     }
1160     auto CountIt = std::find_if(ValueCounts.begin(), ValueCounts.end(),
1161                                 [&Lane](Entry A) { return A.first == Lane; });
1162     if (CountIt == ValueCounts.end()) {
1163       ValueCounts.emplace_back(Lane, 1);
1164     } else {
1165       CountIt->second++;
1166     }
1167   }
1168   auto CommonIt =
1169       std::max_element(ValueCounts.begin(), ValueCounts.end(),
1170                        [](Entry A, Entry B) { return A.second < B.second; });
1171   assert(CommonIt != ValueCounts.end() && "Unexpected all-undef build_vector");
1172   SDValue SplatValue = CommonIt->first;
1173   size_t NumCommon = CommonIt->second;
1174
1175   // If v128.const is available, consider using it instead of a splat
1176   if (Subtarget->hasUnimplementedSIMD128()) {
1177     // {i32,i64,f32,f64}.const opcode, and value
1178     const size_t ConstBytes = 1 + std::max(size_t(4), 16 / Lanes);
1179     // SIMD prefix and opcode
1180     const size_t SplatBytes = 2;
1181     const size_t SplatConstBytes = SplatBytes + ConstBytes;
1182     // SIMD prefix, opcode, and lane index
1183     const size_t ReplaceBytes = 3;
1184     const size_t ReplaceConstBytes = ReplaceBytes + ConstBytes;
1185     // SIMD prefix, v128.const opcode, and 128-bit value
1186     const size_t VecConstBytes = 18;
1187     // Initial v128.const and a replace_lane for each non-const operand
1188     const size_t ConstInitBytes = VecConstBytes + NumDynamic * ReplaceBytes;
1189     // Initial splat and all necessary replace_lanes
1190     const size_t SplatInitBytes =
1191         IsConstant(SplatValue)
1192             // Initial constant splat
1193             ? (SplatConstBytes +
1194                // Constant replace_lanes
1195                (NumConst - NumCommon) * ReplaceConstBytes +
1196                // Dynamic replace_lanes
1197                (NumDynamic * ReplaceBytes))
1198             // Initial dynamic splat
1199             : (SplatBytes +
1200                // Constant replace_lanes
1201                (NumConst * ReplaceConstBytes) +
1202                // Dynamic replace_lanes
1203                (NumDynamic - NumCommon) * ReplaceBytes);
1204     if (ConstInitBytes < SplatInitBytes) {
1205       // Create build_vector that will lower to initial v128.const
1206       SmallVector<SDValue, 16> ConstLanes;
1207       for (const SDValue &Lane : Op->op_values()) {
1208         if (IsConstant(Lane)) {
1209           ConstLanes.push_back(Lane);
1210         } else if (LaneT.isFloatingPoint()) {
1211           ConstLanes.push_back(DAG.getConstantFP(0, DL, LaneT));
1212         } else {
1213           ConstLanes.push_back(DAG.getConstant(0, DL, LaneT));
1214         }
1215       }
1216       SDValue Result = DAG.getBuildVector(VecT, DL, ConstLanes);
1217       // Add replace_lane instructions for non-const lanes
1218       for (size_t I = 0; I < Lanes; ++I) {
1219         const SDValue &Lane = Op->getOperand(I);
1220         if (!Lane.isUndef() && !IsConstant(Lane))
1221           Result = DAG.getNode(ISD::INSERT_VECTOR_ELT, DL, VecT, Result, Lane,
1222                                DAG.getConstant(I, DL, MVT::i32));
1223       }
1224       return Result;
1225     }
1226   }
1227   // Use a splat for the initial vector
1228   SDValue Result = DAG.getSplatBuildVector(VecT, DL, SplatValue);
1229   // Add replace_lane instructions for other values
1230   for (size_t I = 0; I < Lanes; ++I) {
1231     const SDValue &Lane = Op->getOperand(I);
1232     if (Lane != SplatValue)
1233       Result = DAG.getNode(ISD::INSERT_VECTOR_ELT, DL, VecT, Result, Lane,
1234                            DAG.getConstant(I, DL, MVT::i32));
1235   }
1236   return Result;
1237 }
1238
1239 SDValue
1240 WebAssemblyTargetLowering::LowerVECTOR_SHUFFLE(SDValue Op,
1241                                                SelectionDAG &DAG) const {
1242   SDLoc DL(Op);
1243   ArrayRef<int> Mask = cast<ShuffleVectorSDNode>(Op.getNode())->getMask();
1244   MVT VecType = Op.getOperand(0).getSimpleValueType();
1245   assert(VecType.is128BitVector() && "Unexpected shuffle vector type");
1246   size_t LaneBytes = VecType.getVectorElementType().getSizeInBits() / 8;
1247
1248   // Space for two vector args and sixteen mask indices
1249   SDValue Ops[18];
1250   size_t OpIdx = 0;
1251   Ops[OpIdx++] = Op.getOperand(0);
1252   Ops[OpIdx++] = Op.getOperand(1);
1253
1254   // Expand mask indices to byte indices and materialize them as operands
1255   for (int M : Mask) {
1256     for (size_t J = 0; J < LaneBytes; ++J) {
1257       // Lower undefs (represented by -1 in mask) to zero
1258       uint64_t ByteIndex = M == -1 ? 0 : (uint64_t)M * LaneBytes + J;
1259       Ops[OpIdx++] = DAG.getConstant(ByteIndex, DL, MVT::i32);
1260     }
1261   }
1262
1263   return DAG.getNode(WebAssemblyISD::SHUFFLE, DL, Op.getValueType(), Ops);
1264 }
1265
1266 SDValue
1267 WebAssemblyTargetLowering::LowerAccessVectorElement(SDValue Op,
1268                                                     SelectionDAG &DAG) const {
1269   // Allow constant lane indices, expand variable lane indices
1270   SDNode *IdxNode = Op.getOperand(Op.getNumOperands() - 1).getNode();
1271   if (isa<ConstantSDNode>(IdxNode) || IdxNode->isUndef())
1272     return Op;
1273   else
1274     // Perform default expansion
1275     return SDValue();
1276 }
1277
1278 static SDValue unrollVectorShift(SDValue Op, SelectionDAG &DAG) {
1279   EVT LaneT = Op.getSimpleValueType().getVectorElementType();
1280   // 32-bit and 64-bit unrolled shifts will have proper semantics
1281   if (LaneT.bitsGE(MVT::i32))
1282     return DAG.UnrollVectorOp(Op.getNode());
1283   // Otherwise mask the shift value to get proper semantics from 32-bit shift
1284   SDLoc DL(Op);
1285   SDValue ShiftVal = Op.getOperand(1);
1286   uint64_t MaskVal = LaneT.getSizeInBits() - 1;
1287   SDValue MaskedShiftVal = DAG.getNode(
1288       ISD::AND,                    // mask opcode
1289       DL, ShiftVal.getValueType(), // masked value type
1290       ShiftVal,                    // original shift value operand
1291       DAG.getConstant(MaskVal, DL, ShiftVal.getValueType()) // mask operand
1292   );
1293
1294   return DAG.UnrollVectorOp(
1295       DAG.getNode(Op.getOpcode(),        // original shift opcode
1296                   DL, Op.getValueType(), // original return type
1297                   Op.getOperand(0),      // original vector operand,
1298                   MaskedShiftVal         // new masked shift value operand
1299                   )
1300           .getNode());
1301 }
1302
1303 SDValue WebAssemblyTargetLowering::LowerShift(SDValue Op,
1304                                               SelectionDAG &DAG) const {
1305   SDLoc DL(Op);
1306
1307   // Only manually lower vector shifts
1308   assert(Op.getSimpleValueType().isVector());
1309
1310   // Expand all vector shifts until V8 fixes its implementation
1311   // TODO: remove this once V8 is fixed
1312   if (!Subtarget->hasUnimplementedSIMD128())
1313     return unrollVectorShift(Op, DAG);
1314
1315   // Unroll non-splat vector shifts
1316   BuildVectorSDNode *ShiftVec;
1317   SDValue SplatVal;
1318   if (!(ShiftVec = dyn_cast<BuildVectorSDNode>(Op.getOperand(1).getNode())) ||
1319       !(SplatVal = ShiftVec->getSplatValue()))
1320     return unrollVectorShift(Op, DAG);
1321
1322   // All splats except i64x2 const splats are handled by patterns
1323   auto *SplatConst = dyn_cast<ConstantSDNode>(SplatVal);
1324   if (!SplatConst || Op.getSimpleValueType() != MVT::v2i64)
1325     return Op;
1326
1327   // i64x2 const splats are custom lowered to avoid unnecessary wraps
1328   unsigned Opcode;
1329   switch (Op.getOpcode()) {
1330   case ISD::SHL:
1331     Opcode = WebAssemblyISD::VEC_SHL;
1332     break;
1333   case ISD::SRA:
1334     Opcode = WebAssemblyISD::VEC_SHR_S;
1335     break;
1336   case ISD::SRL:
1337     Opcode = WebAssemblyISD::VEC_SHR_U;
1338     break;
1339   default:
1340     llvm_unreachable("unexpected opcode");
1341   }
1342   APInt Shift = SplatConst->getAPIntValue().zextOrTrunc(32);
1343   return DAG.getNode(Opcode, DL, Op.getValueType(), Op.getOperand(0),
1344                      DAG.getConstant(Shift, DL, MVT::i32));
1345 }
1346
1347 //===----------------------------------------------------------------------===//
1348 //                          WebAssembly Optimization Hooks
1349 //===----------------------------------------------------------------------===//