1//===-- WebAssemblyFastISel.cpp - WebAssembly FastISel implementation -----===//
2//
3//                     The LLVM Compiler Infrastructure
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 This file defines the WebAssembly-specific support for the FastISel
12/// class. Some of the target-specific code is generated by tablegen in the file
13/// WebAssemblyGenFastISel.inc, which is #included here.
14///
15/// TODO: kill flags
16///
17//===----------------------------------------------------------------------===//
18
19#include "WebAssembly.h"
20#include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
21#include "WebAssemblyMachineFunctionInfo.h"
22#include "WebAssemblySubtarget.h"
23#include "WebAssemblyTargetMachine.h"
24#include "llvm/Analysis/BranchProbabilityInfo.h"
25#include "llvm/CodeGen/FastISel.h"
26#include "llvm/CodeGen/FunctionLoweringInfo.h"
27#include "llvm/CodeGen/MachineConstantPool.h"
28#include "llvm/CodeGen/MachineFrameInfo.h"
29#include "llvm/CodeGen/MachineInstrBuilder.h"
30#include "llvm/CodeGen/MachineRegisterInfo.h"
31#include "llvm/IR/DataLayout.h"
32#include "llvm/IR/DerivedTypes.h"
33#include "llvm/IR/Function.h"
34#include "llvm/IR/GetElementPtrTypeIterator.h"
35#include "llvm/IR/GlobalAlias.h"
36#include "llvm/IR/GlobalVariable.h"
37#include "llvm/IR/Instructions.h"
38#include "llvm/IR/IntrinsicInst.h"
39#include "llvm/IR/Operator.h"
40using namespace llvm;
41
42#define DEBUG_TYPE "wasm-fastisel"
43
44namespace {
45
46class WebAssemblyFastISel final : public FastISel {
47  // All possible address modes.
48  class Address {
49  public:
50    typedef enum { RegBase, FrameIndexBase } BaseKind;
51
52  private:
53    BaseKind Kind;
54    union {
55      unsigned Reg;
56      int FI;
57    } Base;
58
59    int64_t Offset;
60
61    const GlobalValue *GV;
62
63  public:
64    // Innocuous defaults for our address.
65    Address() : Kind(RegBase), Offset(0), GV(0) { Base.Reg = 0; }
66    void setKind(BaseKind K) { Kind = K; }
67    BaseKind getKind() const { return Kind; }
68    bool isRegBase() const { return Kind == RegBase; }
69    bool isFIBase() const { return Kind == FrameIndexBase; }
70    void setReg(unsigned Reg) {
71      assert(isRegBase() && "Invalid base register access!");
72      Base.Reg = Reg;
73    }
74    unsigned getReg() const {
75      assert(isRegBase() && "Invalid base register access!");
76      return Base.Reg;
77    }
78    void setFI(unsigned FI) {
79      assert(isFIBase() && "Invalid base frame index access!");
80      Base.FI = FI;
81    }
82    unsigned getFI() const {
83      assert(isFIBase() && "Invalid base frame index access!");
84      return Base.FI;
85    }
86
87    void setOffset(int64_t Offset_) { Offset = Offset_; }
88    int64_t getOffset() const { return Offset; }
89    void setGlobalValue(const GlobalValue *G) { GV = G; }
90    const GlobalValue *getGlobalValue() const { return GV; }
91  };
92
93  /// Keep a pointer to the WebAssemblySubtarget around so that we can make the
94  /// right decision when generating code for different targets.
95  const WebAssemblySubtarget *Subtarget;
96  LLVMContext *Context;
97
98private:
99  // Utility helper routines
100  MVT::SimpleValueType getSimpleType(Type *Ty) {
101    EVT VT = TLI.getValueType(DL, Ty, /*HandleUnknown=*/true);
102    return VT.isSimple() ? VT.getSimpleVT().SimpleTy :
103                           MVT::INVALID_SIMPLE_VALUE_TYPE;
104  }
105  MVT::SimpleValueType getLegalType(MVT::SimpleValueType VT) {
106    switch (VT) {
107    case MVT::i1:
108    case MVT::i8:
109    case MVT::i16:
110      return MVT::i32;
111    case MVT::i32:
112    case MVT::i64:
113    case MVT::f32:
114    case MVT::f64:
115      return VT;
116    default:
117      break;
118    }
119    return MVT::INVALID_SIMPLE_VALUE_TYPE;
120  }
121  bool computeAddress(const Value *Obj, Address &Addr);
122  void materializeLoadStoreOperands(Address &Addr);
123  void addLoadStoreOperands(const Address &Addr, const MachineInstrBuilder &MIB,
124                            MachineMemOperand *MMO);
125  unsigned maskI1Value(unsigned Reg, const Value *V);
126  unsigned getRegForI1Value(const Value *V, bool &Not);
127  unsigned zeroExtendToI32(unsigned Reg, const Value *V,
128                           MVT::SimpleValueType From);
129  unsigned signExtendToI32(unsigned Reg, const Value *V,
130                           MVT::SimpleValueType From);
131  unsigned zeroExtend(unsigned Reg, const Value *V,
132                      MVT::SimpleValueType From,
133                      MVT::SimpleValueType To);
134  unsigned signExtend(unsigned Reg, const Value *V,
135                      MVT::SimpleValueType From,
136                      MVT::SimpleValueType To);
137  unsigned getRegForUnsignedValue(const Value *V);
138  unsigned getRegForSignedValue(const Value *V);
139  unsigned getRegForPromotedValue(const Value *V, bool IsSigned);
140  unsigned notValue(unsigned Reg);
141  unsigned copyValue(unsigned Reg);
142
143  // Backend specific FastISel code.
144  unsigned fastMaterializeAlloca(const AllocaInst *AI) override;
145  unsigned fastMaterializeConstant(const Constant *C) override;
146  bool fastLowerArguments() override;
147
148  // Selection routines.
149  bool selectCall(const Instruction *I);
150  bool selectSelect(const Instruction *I);
151  bool selectTrunc(const Instruction *I);
152  bool selectZExt(const Instruction *I);
153  bool selectSExt(const Instruction *I);
154  bool selectICmp(const Instruction *I);
155  bool selectFCmp(const Instruction *I);
156  bool selectBitCast(const Instruction *I);
157  bool selectLoad(const Instruction *I);
158  bool selectStore(const Instruction *I);
159  bool selectBr(const Instruction *I);
160  bool selectRet(const Instruction *I);
161  bool selectUnreachable(const Instruction *I);
162
163public:
164  // Backend specific FastISel code.
165  WebAssemblyFastISel(FunctionLoweringInfo &FuncInfo,
166                      const TargetLibraryInfo *LibInfo)
167      : FastISel(FuncInfo, LibInfo, /*SkipTargetIndependentISel=*/true) {
168    Subtarget = &FuncInfo.MF->getSubtarget<WebAssemblySubtarget>();
169    Context = &FuncInfo.Fn->getContext();
170  }
171
172  bool fastSelectInstruction(const Instruction *I) override;
173
174#include "WebAssemblyGenFastISel.inc"
175};
176
177} // end anonymous namespace
178
179bool WebAssemblyFastISel::computeAddress(const Value *Obj, Address &Addr) {
180
181  const User *U = nullptr;
182  unsigned Opcode = Instruction::UserOp1;
183  if (const Instruction *I = dyn_cast<Instruction>(Obj)) {
184    // Don't walk into other basic blocks unless the object is an alloca from
185    // another block, otherwise it may not have a virtual register assigned.
186    if (FuncInfo.StaticAllocaMap.count(static_cast<const AllocaInst *>(Obj)) ||
187        FuncInfo.MBBMap[I->getParent()] == FuncInfo.MBB) {
188      Opcode = I->getOpcode();
189      U = I;
190    }
191  } else if (const ConstantExpr *C = dyn_cast<ConstantExpr>(Obj)) {
192    Opcode = C->getOpcode();
193    U = C;
194  }
195
196  if (auto *Ty = dyn_cast<PointerType>(Obj->getType()))
197    if (Ty->getAddressSpace() > 255)
198      // Fast instruction selection doesn't support the special
199      // address spaces.
200      return false;
201
202  if (const GlobalValue *GV = dyn_cast<GlobalValue>(Obj)) {
203    if (Addr.getGlobalValue())
204      return false;
205    Addr.setGlobalValue(GV);
206    return true;
207  }
208
209  switch (Opcode) {
210  default:
211    break;
212  case Instruction::BitCast: {
213    // Look through bitcasts.
214    return computeAddress(U->getOperand(0), Addr);
215  }
216  case Instruction::IntToPtr: {
217    // Look past no-op inttoptrs.
218    if (TLI.getValueType(DL, U->getOperand(0)->getType()) ==
219        TLI.getPointerTy(DL))
220      return computeAddress(U->getOperand(0), Addr);
221    break;
222  }
223  case Instruction::PtrToInt: {
224    // Look past no-op ptrtoints.
225    if (TLI.getValueType(DL, U->getType()) == TLI.getPointerTy(DL))
226      return computeAddress(U->getOperand(0), Addr);
227    break;
228  }
229  case Instruction::GetElementPtr: {
230    Address SavedAddr = Addr;
231    uint64_t TmpOffset = Addr.getOffset();
232    // Iterate through the GEP folding the constants into offsets where
233    // we can.
234    for (gep_type_iterator GTI = gep_type_begin(U), E = gep_type_end(U);
235         GTI != E; ++GTI) {
236      const Value *Op = GTI.getOperand();
237      if (StructType *STy = dyn_cast<StructType>(*GTI)) {
238        const StructLayout *SL = DL.getStructLayout(STy);
239        unsigned Idx = cast<ConstantInt>(Op)->getZExtValue();
240        TmpOffset += SL->getElementOffset(Idx);
241      } else {
242        uint64_t S = DL.getTypeAllocSize(GTI.getIndexedType());
243        for (;;) {
244          if (const ConstantInt *CI = dyn_cast<ConstantInt>(Op)) {
245            // Constant-offset addressing.
246            TmpOffset += CI->getSExtValue() * S;
247            break;
248          }
249          if (S == 1 && Addr.isRegBase() && Addr.getReg() == 0) {
250            // An unscaled add of a register. Set it as the new base.
251            Addr.setReg(getRegForValue(Op));
252            break;
253          }
254          if (canFoldAddIntoGEP(U, Op)) {
255            // A compatible add with a constant operand. Fold the constant.
256            ConstantInt *CI =
257                cast<ConstantInt>(cast<AddOperator>(Op)->getOperand(1));
258            TmpOffset += CI->getSExtValue() * S;
259            // Iterate on the other operand.
260            Op = cast<AddOperator>(Op)->getOperand(0);
261            continue;
262          }
263          // Unsupported
264          goto unsupported_gep;
265        }
266      }
267    }
268    // Try to grab the base operand now.
269    Addr.setOffset(TmpOffset);
270    if (computeAddress(U->getOperand(0), Addr))
271      return true;
272    // We failed, restore everything and try the other options.
273    Addr = SavedAddr;
274  unsupported_gep:
275    break;
276  }
277  case Instruction::Alloca: {
278    const AllocaInst *AI = cast<AllocaInst>(Obj);
279    DenseMap<const AllocaInst *, int>::iterator SI =
280        FuncInfo.StaticAllocaMap.find(AI);
281    if (SI != FuncInfo.StaticAllocaMap.end()) {
282      Addr.setKind(Address::FrameIndexBase);
283      Addr.setFI(SI->second);
284      return true;
285    }
286    break;
287  }
288  case Instruction::Add: {
289    // Adds of constants are common and easy enough.
290    const Value *LHS = U->getOperand(0);
291    const Value *RHS = U->getOperand(1);
292
293    if (isa<ConstantInt>(LHS))
294      std::swap(LHS, RHS);
295
296    if (const ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
297      Addr.setOffset(Addr.getOffset() + CI->getSExtValue());
298      return computeAddress(LHS, Addr);
299    }
300
301    Address Backup = Addr;
302    if (computeAddress(LHS, Addr) && computeAddress(RHS, Addr))
303      return true;
304    Addr = Backup;
305
306    break;
307  }
308  case Instruction::Sub: {
309    // Subs of constants are common and easy enough.
310    const Value *LHS = U->getOperand(0);
311    const Value *RHS = U->getOperand(1);
312
313    if (const ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
314      Addr.setOffset(Addr.getOffset() - CI->getSExtValue());
315      return computeAddress(LHS, Addr);
316    }
317    break;
318  }
319  }
320  Addr.setReg(getRegForValue(Obj));
321  return Addr.getReg() != 0;
322}
323
324void WebAssemblyFastISel::materializeLoadStoreOperands(Address &Addr) {
325  if (Addr.isRegBase()) {
326    unsigned Reg = Addr.getReg();
327    if (Reg == 0) {
328      Reg = createResultReg(Subtarget->hasAddr64() ?
329                            &WebAssembly::I64RegClass :
330                            &WebAssembly::I32RegClass);
331      unsigned Opc = Subtarget->hasAddr64() ?
332                     WebAssembly::CONST_I64 :
333                     WebAssembly::CONST_I32;
334      BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(Opc), Reg)
335         .addImm(0);
336      Addr.setReg(Reg);
337    }
338  }
339}
340
341void WebAssemblyFastISel::addLoadStoreOperands(const Address &Addr,
342                                               const MachineInstrBuilder &MIB,
343                                               MachineMemOperand *MMO) {
344  if (const GlobalValue *GV = Addr.getGlobalValue())
345    MIB.addGlobalAddress(GV, Addr.getOffset());
346  else
347    MIB.addImm(Addr.getOffset());
348
349  if (Addr.isRegBase())
350    MIB.addReg(Addr.getReg());
351  else
352    MIB.addFrameIndex(Addr.getFI());
353
354  // Set the alignment operand (this is rewritten in SetP2AlignOperands).
355  // TODO: Disable SetP2AlignOperands for FastISel and just do it here.
356  MIB.addImm(0);
357
358  MIB.addMemOperand(MMO);
359}
360
361unsigned WebAssemblyFastISel::maskI1Value(unsigned Reg, const Value *V) {
362  return zeroExtendToI32(Reg, V, MVT::i1);
363}
364
365unsigned WebAssemblyFastISel::getRegForI1Value(const Value *V, bool &Not) {
366  if (const ICmpInst *ICmp = dyn_cast<ICmpInst>(V))
367    if (const ConstantInt *C = dyn_cast<ConstantInt>(ICmp->getOperand(1)))
368      if (ICmp->isEquality() && C->isZero() && C->getType()->isIntegerTy(32)) {
369        Not = ICmp->isTrueWhenEqual();
370        return getRegForValue(ICmp->getOperand(0));
371      }
372
373  if (BinaryOperator::isNot(V)) {
374    Not = true;
375    return getRegForValue(BinaryOperator::getNotArgument(V));
376  }
377
378  Not = false;
379  return maskI1Value(getRegForValue(V), V);
380}
381
382unsigned WebAssemblyFastISel::zeroExtendToI32(unsigned Reg, const Value *V,
383                                              MVT::SimpleValueType From) {
384  switch (From) {
385  case MVT::i1:
386    // If the value is naturally an i1, we don't need to mask it.
387    // TODO: Recursively examine selects, phis, and, or, xor, constants.
388    if (From == MVT::i1 && V != nullptr) {
389      if (isa<CmpInst>(V) ||
390          (isa<Argument>(V) && cast<Argument>(V)->hasZExtAttr()))
391        return copyValue(Reg);
392    }
393  case MVT::i8:
394  case MVT::i16:
395    break;
396  case MVT::i32:
397    return copyValue(Reg);
398  default:
399    return 0;
400  }
401
402  unsigned Imm = createResultReg(&WebAssembly::I32RegClass);
403  BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
404          TII.get(WebAssembly::CONST_I32), Imm)
405    .addImm(~(~uint64_t(0) << MVT(From).getSizeInBits()));
406
407  unsigned Result = createResultReg(&WebAssembly::I32RegClass);
408  BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
409          TII.get(WebAssembly::AND_I32), Result)
410    .addReg(Reg)
411    .addReg(Imm);
412
413  return Result;
414}
415
416unsigned WebAssemblyFastISel::signExtendToI32(unsigned Reg, const Value *V,
417                                              MVT::SimpleValueType From) {
418  switch (From) {
419  case MVT::i1:
420  case MVT::i8:
421  case MVT::i16:
422    break;
423  case MVT::i32:
424    return copyValue(Reg);
425  default:
426    return 0;
427  }
428
429  unsigned Imm = createResultReg(&WebAssembly::I32RegClass);
430  BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
431          TII.get(WebAssembly::CONST_I32), Imm)
432    .addImm(32 - MVT(From).getSizeInBits());
433
434  unsigned Left = createResultReg(&WebAssembly::I32RegClass);
435  BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
436          TII.get(WebAssembly::SHL_I32), Left)
437    .addReg(Reg)
438    .addReg(Imm);
439
440  unsigned Right = createResultReg(&WebAssembly::I32RegClass);
441  BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
442          TII.get(WebAssembly::SHR_S_I32), Right)
443    .addReg(Left)
444    .addReg(Imm);
445
446  return Right;
447}
448
449unsigned WebAssemblyFastISel::zeroExtend(unsigned Reg, const Value *V,
450                                         MVT::SimpleValueType From,
451                                         MVT::SimpleValueType To) {
452  if (To == MVT::i64) {
453    if (From == MVT::i64)
454      return copyValue(Reg);
455
456    Reg = zeroExtendToI32(Reg, V, From);
457
458    unsigned Result = createResultReg(&WebAssembly::I64RegClass);
459    BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
460            TII.get(WebAssembly::I64_EXTEND_U_I32), Result)
461        .addReg(Reg);
462    return Result;
463  }
464
465  return zeroExtendToI32(Reg, V, From);
466}
467
468unsigned WebAssemblyFastISel::signExtend(unsigned Reg, const Value *V,
469                                         MVT::SimpleValueType From,
470                                         MVT::SimpleValueType To) {
471  if (To == MVT::i64) {
472    if (From == MVT::i64)
473      return copyValue(Reg);
474
475    Reg = signExtendToI32(Reg, V, From);
476
477    unsigned Result = createResultReg(&WebAssembly::I64RegClass);
478    BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
479            TII.get(WebAssembly::I64_EXTEND_S_I32), Result)
480        .addReg(Reg);
481    return Result;
482  }
483
484  return signExtendToI32(Reg, V, From);
485}
486
487unsigned WebAssemblyFastISel::getRegForUnsignedValue(const Value *V) {
488  MVT::SimpleValueType From = getSimpleType(V->getType());
489  MVT::SimpleValueType To = getLegalType(From);
490  return zeroExtend(getRegForValue(V), V, From, To);
491}
492
493unsigned WebAssemblyFastISel::getRegForSignedValue(const Value *V) {
494  MVT::SimpleValueType From = getSimpleType(V->getType());
495  MVT::SimpleValueType To = getLegalType(From);
496  return zeroExtend(getRegForValue(V), V, From, To);
497}
498
499unsigned WebAssemblyFastISel::getRegForPromotedValue(const Value *V,
500                                                     bool IsSigned) {
501  return IsSigned ? getRegForSignedValue(V) :
502                    getRegForUnsignedValue(V);
503}
504
505unsigned WebAssemblyFastISel::notValue(unsigned Reg) {
506  assert(MRI.getRegClass(Reg) == &WebAssembly::I32RegClass);
507
508  unsigned NotReg = createResultReg(&WebAssembly::I32RegClass);
509  BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
510          TII.get(WebAssembly::EQZ_I32), NotReg)
511    .addReg(Reg);
512  return NotReg;
513}
514
515unsigned WebAssemblyFastISel::copyValue(unsigned Reg) {
516  unsigned ResultReg = createResultReg(MRI.getRegClass(Reg));
517  BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
518          TII.get(WebAssembly::COPY), ResultReg)
519    .addReg(Reg);
520  return ResultReg;
521}
522
523unsigned WebAssemblyFastISel::fastMaterializeAlloca(const AllocaInst *AI) {
524  DenseMap<const AllocaInst *, int>::iterator SI =
525      FuncInfo.StaticAllocaMap.find(AI);
526
527  if (SI != FuncInfo.StaticAllocaMap.end()) {
528    unsigned ResultReg = createResultReg(Subtarget->hasAddr64() ?
529                                         &WebAssembly::I64RegClass :
530                                         &WebAssembly::I32RegClass);
531    unsigned Opc = Subtarget->hasAddr64() ?
532                   WebAssembly::COPY_LOCAL_I64 :
533                   WebAssembly::COPY_LOCAL_I32;
534    BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(Opc), ResultReg)
535        .addFrameIndex(SI->second);
536    return ResultReg;
537  }
538
539  return 0;
540}
541
542unsigned WebAssemblyFastISel::fastMaterializeConstant(const Constant *C) {
543  if (const GlobalValue *GV = dyn_cast<GlobalValue>(C)) {
544    unsigned ResultReg = createResultReg(Subtarget->hasAddr64() ?
545                                         &WebAssembly::I64RegClass :
546                                         &WebAssembly::I32RegClass);
547    unsigned Opc = Subtarget->hasAddr64() ?
548                   WebAssembly::CONST_I64 :
549                   WebAssembly::CONST_I32;
550    BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(Opc), ResultReg)
551       .addGlobalAddress(GV);
552    return ResultReg;
553  }
554
555  // Let target-independent code handle it.
556  return 0;
557}
558
559bool WebAssemblyFastISel::fastLowerArguments() {
560  if (!FuncInfo.CanLowerReturn)
561    return false;
562
563  const Function *F = FuncInfo.Fn;
564  if (F->isVarArg())
565    return false;
566
567  unsigned i = 0;
568  for (auto const &Arg : F->args()) {
569    const AttributeSet &Attrs = F->getAttributes();
570    if (Attrs.hasAttribute(i+1, Attribute::ByVal) ||
571        Attrs.hasAttribute(i+1, Attribute::SwiftSelf) ||
572        Attrs.hasAttribute(i+1, Attribute::SwiftError) ||
573        Attrs.hasAttribute(i+1, Attribute::InAlloca) ||
574        Attrs.hasAttribute(i+1, Attribute::Nest))
575      return false;
576
577    Type *ArgTy = Arg.getType();
578    if (ArgTy->isStructTy() || ArgTy->isArrayTy() || ArgTy->isVectorTy())
579      return false;
580
581    unsigned Opc;
582    const TargetRegisterClass *RC;
583    switch (getSimpleType(ArgTy)) {
584    case MVT::i1:
585    case MVT::i8:
586    case MVT::i16:
587    case MVT::i32:
588      Opc = WebAssembly::ARGUMENT_I32;
589      RC = &WebAssembly::I32RegClass;
590      break;
591    case MVT::i64:
592      Opc = WebAssembly::ARGUMENT_I64;
593      RC = &WebAssembly::I64RegClass;
594      break;
595    case MVT::f32:
596      Opc = WebAssembly::ARGUMENT_F32;
597      RC = &WebAssembly::F32RegClass;
598      break;
599    case MVT::f64:
600      Opc = WebAssembly::ARGUMENT_F64;
601      RC = &WebAssembly::F64RegClass;
602      break;
603    default:
604      return false;
605    }
606    unsigned ResultReg = createResultReg(RC);
607    BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(Opc), ResultReg)
608      .addImm(i);
609    updateValueMap(&Arg, ResultReg);
610
611    ++i;
612  }
613
614  MRI.addLiveIn(WebAssembly::ARGUMENTS);
615
616  auto *MFI = MF->getInfo<WebAssemblyFunctionInfo>();
617  for (auto const &Arg : F->args())
618    MFI->addParam(getLegalType(getSimpleType(Arg.getType())));
619
620  return true;
621}
622
623bool WebAssemblyFastISel::selectCall(const Instruction *I) {
624  const CallInst *Call = cast<CallInst>(I);
625
626  if (Call->isMustTailCall() || Call->isInlineAsm() ||
627      Call->getFunctionType()->isVarArg())
628    return false;
629
630  Function *Func = Call->getCalledFunction();
631  if (Func && Func->isIntrinsic())
632    return false;
633
634  FunctionType *FuncTy = Call->getFunctionType();
635  unsigned Opc;
636  bool IsDirect = Func != nullptr;
637  bool IsVoid = FuncTy->getReturnType()->isVoidTy();
638  unsigned ResultReg;
639  if (IsVoid) {
640    Opc = IsDirect ? WebAssembly::CALL_VOID : WebAssembly::CALL_INDIRECT_VOID;
641  } else {
642    MVT::SimpleValueType RetTy = getSimpleType(Call->getType());
643    switch (RetTy) {
644    case MVT::i1:
645    case MVT::i8:
646    case MVT::i16:
647    case MVT::i32:
648      Opc = IsDirect ? WebAssembly::CALL_I32 : WebAssembly::CALL_INDIRECT_I32;
649      ResultReg = createResultReg(&WebAssembly::I32RegClass);
650      break;
651    case MVT::i64:
652      Opc = IsDirect ? WebAssembly::CALL_I64 : WebAssembly::CALL_INDIRECT_I64;
653      ResultReg = createResultReg(&WebAssembly::I64RegClass);
654      break;
655    case MVT::f32:
656      Opc = IsDirect ? WebAssembly::CALL_F32 : WebAssembly::CALL_INDIRECT_F32;
657      ResultReg = createResultReg(&WebAssembly::F32RegClass);
658      break;
659    case MVT::f64:
660      Opc = IsDirect ? WebAssembly::CALL_F64 : WebAssembly::CALL_INDIRECT_F64;
661      ResultReg = createResultReg(&WebAssembly::F64RegClass);
662      break;
663    default:
664      return false;
665    }
666  }
667
668  SmallVector<unsigned, 8> Args;
669  for (unsigned i = 0, e = Call->getNumArgOperands(); i < e; ++i) {
670    Value *V = Call->getArgOperand(i);
671    MVT::SimpleValueType ArgTy = getSimpleType(V->getType());
672    if (ArgTy == MVT::INVALID_SIMPLE_VALUE_TYPE)
673      return false;
674
675    const AttributeSet &Attrs = Call->getAttributes();
676    if (Attrs.hasAttribute(i+1, Attribute::ByVal) ||
677        Attrs.hasAttribute(i+1, Attribute::SwiftSelf) ||
678        Attrs.hasAttribute(i+1, Attribute::SwiftError) ||
679        Attrs.hasAttribute(i+1, Attribute::InAlloca) ||
680        Attrs.hasAttribute(i+1, Attribute::Nest))
681      return false;
682
683    unsigned Reg;
684
685    if (Attrs.hasAttribute(i+1, Attribute::SExt))
686      Reg = getRegForSignedValue(V);
687    else if (Attrs.hasAttribute(i+1, Attribute::ZExt))
688      Reg = getRegForUnsignedValue(V);
689    else
690      Reg = getRegForValue(V);
691
692    if (Reg == 0)
693      return false;
694
695    Args.push_back(Reg);
696  }
697
698  auto MIB = BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(Opc));
699
700  if (!IsVoid)
701    MIB.addReg(ResultReg, RegState::Define);
702
703  if (IsDirect)
704    MIB.addGlobalAddress(Func);
705  else
706    MIB.addReg(getRegForValue(Call->getCalledValue()));
707
708  for (unsigned ArgReg : Args)
709    MIB.addReg(ArgReg);
710
711  if (!IsVoid)
712    updateValueMap(Call, ResultReg);
713  return true;
714}
715
716bool WebAssemblyFastISel::selectSelect(const Instruction *I) {
717  const SelectInst *Select = cast<SelectInst>(I);
718
719  bool Not;
720  unsigned CondReg  = getRegForI1Value(Select->getCondition(), Not);
721  if (CondReg == 0)
722    return false;
723
724  unsigned TrueReg  = getRegForValue(Select->getTrueValue());
725  if (TrueReg == 0)
726    return false;
727
728  unsigned FalseReg = getRegForValue(Select->getFalseValue());
729  if (FalseReg == 0)
730    return false;
731
732  if (Not)
733    std::swap(TrueReg, FalseReg);
734
735  unsigned Opc;
736  const TargetRegisterClass *RC;
737  switch (getSimpleType(Select->getType())) {
738  case MVT::i1:
739  case MVT::i8:
740  case MVT::i16:
741  case MVT::i32:
742    Opc = WebAssembly::SELECT_I32;
743    RC = &WebAssembly::I32RegClass;
744    break;
745  case MVT::i64:
746    Opc = WebAssembly::SELECT_I64;
747    RC = &WebAssembly::I64RegClass;
748    break;
749  case MVT::f32:
750    Opc = WebAssembly::SELECT_F32;
751    RC = &WebAssembly::F32RegClass;
752    break;
753  case MVT::f64:
754    Opc = WebAssembly::SELECT_F64;
755    RC = &WebAssembly::F64RegClass;
756    break;
757  default:
758    return false;
759  }
760
761  unsigned ResultReg = createResultReg(RC);
762  BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(Opc), ResultReg)
763    .addReg(TrueReg)
764    .addReg(FalseReg)
765    .addReg(CondReg);
766
767  updateValueMap(Select, ResultReg);
768  return true;
769}
770
771bool WebAssemblyFastISel::selectTrunc(const Instruction *I) {
772  const TruncInst *Trunc = cast<TruncInst>(I);
773
774  unsigned Reg = getRegForValue(Trunc->getOperand(0));
775  if (Reg == 0)
776    return false;
777
778  if (Trunc->getOperand(0)->getType()->isIntegerTy(64)) {
779    unsigned Result = createResultReg(&WebAssembly::I32RegClass);
780    BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
781            TII.get(WebAssembly::I32_WRAP_I64), Result)
782        .addReg(Reg);
783    Reg = Result;
784  }
785
786  updateValueMap(Trunc, Reg);
787  return true;
788}
789
790bool WebAssemblyFastISel::selectZExt(const Instruction *I) {
791  const ZExtInst *ZExt = cast<ZExtInst>(I);
792
793  const Value *Op = ZExt->getOperand(0);
794  MVT::SimpleValueType From = getSimpleType(Op->getType());
795  MVT::SimpleValueType To = getLegalType(getSimpleType(ZExt->getType()));
796  unsigned Reg = zeroExtend(getRegForValue(Op), Op, From, To);
797  if (Reg == 0)
798    return false;
799
800  updateValueMap(ZExt, Reg);
801  return true;
802}
803
804bool WebAssemblyFastISel::selectSExt(const Instruction *I) {
805  const SExtInst *SExt = cast<SExtInst>(I);
806
807  const Value *Op = SExt->getOperand(0);
808  MVT::SimpleValueType From = getSimpleType(Op->getType());
809  MVT::SimpleValueType To = getLegalType(getSimpleType(SExt->getType()));
810  unsigned Reg = signExtend(getRegForValue(Op), Op, From, To);
811  if (Reg == 0)
812    return false;
813
814  updateValueMap(SExt, Reg);
815  return true;
816}
817
818bool WebAssemblyFastISel::selectICmp(const Instruction *I) {
819  const ICmpInst *ICmp = cast<ICmpInst>(I);
820
821  bool I32 = getSimpleType(ICmp->getOperand(0)->getType()) != MVT::i64;
822  unsigned Opc;
823  bool isSigned = false;
824  switch (ICmp->getPredicate()) {
825  case ICmpInst::ICMP_EQ:
826    Opc = I32 ? WebAssembly::EQ_I32 : WebAssembly::EQ_I64;
827    break;
828  case ICmpInst::ICMP_NE:
829    Opc = I32 ? WebAssembly::NE_I32 : WebAssembly::NE_I64;
830    break;
831  case ICmpInst::ICMP_UGT:
832    Opc = I32 ? WebAssembly::GT_U_I32 : WebAssembly::GT_U_I64;
833    break;
834  case ICmpInst::ICMP_UGE:
835    Opc = I32 ? WebAssembly::GE_U_I32 : WebAssembly::GE_U_I64;
836    break;
837  case ICmpInst::ICMP_ULT:
838    Opc = I32 ? WebAssembly::LT_U_I32 : WebAssembly::LT_U_I64;
839    break;
840  case ICmpInst::ICMP_ULE:
841    Opc = I32 ? WebAssembly::LE_U_I32 : WebAssembly::LE_U_I64;
842    break;
843  case ICmpInst::ICMP_SGT:
844    Opc = I32 ? WebAssembly::GT_S_I32 : WebAssembly::GT_S_I64;
845    isSigned = true;
846    break;
847  case ICmpInst::ICMP_SGE:
848    Opc = I32 ? WebAssembly::GE_S_I32 : WebAssembly::GE_S_I64;
849    isSigned = true;
850    break;
851  case ICmpInst::ICMP_SLT:
852    Opc = I32 ? WebAssembly::LT_S_I32 : WebAssembly::LT_S_I64;
853    isSigned = true;
854    break;
855  case ICmpInst::ICMP_SLE:
856    Opc = I32 ? WebAssembly::LE_S_I32 : WebAssembly::LE_S_I64;
857    isSigned = true;
858    break;
859  default: return false;
860  }
861
862  unsigned LHS = getRegForPromotedValue(ICmp->getOperand(0), isSigned);
863  if (LHS == 0)
864    return false;
865
866  unsigned RHS = getRegForPromotedValue(ICmp->getOperand(1), isSigned);
867  if (RHS == 0)
868    return false;
869
870  unsigned ResultReg = createResultReg(&WebAssembly::I32RegClass);
871  BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(Opc), ResultReg)
872      .addReg(LHS)
873      .addReg(RHS);
874  updateValueMap(ICmp, ResultReg);
875  return true;
876}
877
878bool WebAssemblyFastISel::selectFCmp(const Instruction *I) {
879  const FCmpInst *FCmp = cast<FCmpInst>(I);
880
881  unsigned LHS = getRegForValue(FCmp->getOperand(0));
882  if (LHS == 0)
883    return false;
884
885  unsigned RHS = getRegForValue(FCmp->getOperand(1));
886  if (RHS == 0)
887    return false;
888
889  bool F32 = getSimpleType(FCmp->getOperand(0)->getType()) != MVT::f64;
890  unsigned Opc;
891  bool Not = false;
892  switch (FCmp->getPredicate()) {
893  case FCmpInst::FCMP_OEQ:
894    Opc = F32 ? WebAssembly::EQ_F32 : WebAssembly::EQ_F64;
895    break;
896  case FCmpInst::FCMP_UNE:
897    Opc = F32 ? WebAssembly::NE_F32 : WebAssembly::NE_F64;
898    break;
899  case FCmpInst::FCMP_OGT:
900    Opc = F32 ? WebAssembly::GT_F32 : WebAssembly::GT_F64;
901    break;
902  case FCmpInst::FCMP_OGE:
903    Opc = F32 ? WebAssembly::GE_F32 : WebAssembly::GE_F64;
904    break;
905  case FCmpInst::FCMP_OLT:
906    Opc = F32 ? WebAssembly::LT_F32 : WebAssembly::LT_F64;
907    break;
908  case FCmpInst::FCMP_OLE:
909    Opc = F32 ? WebAssembly::LE_F32 : WebAssembly::LE_F64;
910    break;
911  case FCmpInst::FCMP_UGT:
912    Opc = F32 ? WebAssembly::LE_F32 : WebAssembly::LE_F64;
913    Not = true;
914    break;
915  case FCmpInst::FCMP_UGE:
916    Opc = F32 ? WebAssembly::LT_F32 : WebAssembly::LT_F64;
917    Not = true;
918    break;
919  case FCmpInst::FCMP_ULT:
920    Opc = F32 ? WebAssembly::GE_F32 : WebAssembly::GE_F64;
921    Not = true;
922    break;
923  case FCmpInst::FCMP_ULE:
924    Opc = F32 ? WebAssembly::GT_F32 : WebAssembly::GT_F64;
925    Not = true;
926    break;
927  default:
928    return false;
929  }
930
931  unsigned ResultReg = createResultReg(&WebAssembly::I32RegClass);
932  BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(Opc), ResultReg)
933      .addReg(LHS)
934      .addReg(RHS);
935
936  if (Not)
937    ResultReg = notValue(ResultReg);
938
939  updateValueMap(FCmp, ResultReg);
940  return true;
941}
942
943bool WebAssemblyFastISel::selectBitCast(const Instruction *I) {
944  // Target-independent code can handle this, except it doesn't set the dead
945  // flag on the ARGUMENTS clobber, so we have to do that manually in order
946  // to satisfy code that expects this of isBitcast() instructions.
947  EVT VT = TLI.getValueType(DL, I->getOperand(0)->getType());
948  EVT RetVT = TLI.getValueType(DL, I->getType());
949  if (!VT.isSimple() || !RetVT.isSimple())
950    return false;
951
952  if (VT == RetVT) {
953    // No-op bitcast.
954    updateValueMap(I, getRegForValue(I->getOperand(0)));
955    return true;
956  }
957
958  unsigned Reg = fastEmit_ISD_BITCAST_r(VT.getSimpleVT(), RetVT.getSimpleVT(),
959                                        getRegForValue(I->getOperand(0)),
960                                        I->getOperand(0)->hasOneUse());
961  if (!Reg)
962    return false;
963  MachineBasicBlock::iterator Iter = FuncInfo.InsertPt;
964  --Iter;
965  assert(Iter->isBitcast());
966  Iter->setPhysRegsDeadExcept(ArrayRef<unsigned>(), TRI);
967  updateValueMap(I, Reg);
968  return true;
969}
970
971bool WebAssemblyFastISel::selectLoad(const Instruction *I) {
972  const LoadInst *Load = cast<LoadInst>(I);
973  if (Load->isAtomic())
974    return false;
975
976  Address Addr;
977  if (!computeAddress(Load->getPointerOperand(), Addr))
978    return false;
979
980  // TODO: Fold a following sign-/zero-extend into the load instruction.
981
982  unsigned Opc;
983  const TargetRegisterClass *RC;
984  switch (getSimpleType(Load->getType())) {
985  case MVT::i1:
986  case MVT::i8:
987    Opc = WebAssembly::LOAD8_U_I32;
988    RC = &WebAssembly::I32RegClass;
989    break;
990  case MVT::i16:
991    Opc = WebAssembly::LOAD16_U_I32;
992    RC = &WebAssembly::I32RegClass;
993    break;
994  case MVT::i32:
995    Opc = WebAssembly::LOAD_I32;
996    RC = &WebAssembly::I32RegClass;
997    break;
998  case MVT::i64:
999    Opc = WebAssembly::LOAD_I64;
1000    RC = &WebAssembly::I64RegClass;
1001    break;
1002  case MVT::f32:
1003    Opc = WebAssembly::LOAD_F32;
1004    RC = &WebAssembly::F32RegClass;
1005    break;
1006  case MVT::f64:
1007    Opc = WebAssembly::LOAD_F64;
1008    RC = &WebAssembly::F64RegClass;
1009    break;
1010  default:
1011    return false;
1012  }
1013
1014  materializeLoadStoreOperands(Addr);
1015
1016  unsigned ResultReg = createResultReg(RC);
1017  auto MIB = BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(Opc),
1018                     ResultReg);
1019
1020  addLoadStoreOperands(Addr, MIB, createMachineMemOperandFor(Load));
1021
1022  updateValueMap(Load, ResultReg);
1023  return true;
1024}
1025
1026bool WebAssemblyFastISel::selectStore(const Instruction *I) {
1027  const StoreInst *Store = cast<StoreInst>(I);
1028  if (Store->isAtomic())
1029    return false;
1030
1031  Address Addr;
1032  if (!computeAddress(Store->getPointerOperand(), Addr))
1033    return false;
1034
1035  unsigned Opc;
1036  const TargetRegisterClass *RC;
1037  bool VTIsi1 = false;
1038  switch (getSimpleType(Store->getValueOperand()->getType())) {
1039  case MVT::i1:
1040    VTIsi1 = true;
1041  case MVT::i8:
1042    Opc = WebAssembly::STORE8_I32;
1043    RC = &WebAssembly::I32RegClass;
1044    break;
1045  case MVT::i16:
1046    Opc = WebAssembly::STORE16_I32;
1047    RC = &WebAssembly::I32RegClass;
1048    break;
1049  case MVT::i32:
1050    Opc = WebAssembly::STORE_I32;
1051    RC = &WebAssembly::I32RegClass;
1052    break;
1053  case MVT::i64:
1054    Opc = WebAssembly::STORE_I64;
1055    RC = &WebAssembly::I64RegClass;
1056    break;
1057  case MVT::f32:
1058    Opc = WebAssembly::STORE_F32;
1059    RC = &WebAssembly::F32RegClass;
1060    break;
1061  case MVT::f64:
1062    Opc = WebAssembly::STORE_F64;
1063    RC = &WebAssembly::F64RegClass;
1064    break;
1065  default: return false;
1066  }
1067
1068  materializeLoadStoreOperands(Addr);
1069
1070  unsigned ValueReg = getRegForValue(Store->getValueOperand());
1071  if (VTIsi1)
1072    ValueReg = maskI1Value(ValueReg, Store->getValueOperand());
1073
1074  unsigned ResultReg = createResultReg(RC);
1075  auto MIB = BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(Opc),
1076                     ResultReg);
1077
1078  addLoadStoreOperands(Addr, MIB, createMachineMemOperandFor(Store));
1079
1080  MIB.addReg(ValueReg);
1081  return true;
1082}
1083
1084bool WebAssemblyFastISel::selectBr(const Instruction *I) {
1085  const BranchInst *Br = cast<BranchInst>(I);
1086  if (Br->isUnconditional()) {
1087    MachineBasicBlock *MSucc = FuncInfo.MBBMap[Br->getSuccessor(0)];
1088    fastEmitBranch(MSucc, Br->getDebugLoc());
1089    return true;
1090  }
1091
1092  MachineBasicBlock *TBB = FuncInfo.MBBMap[Br->getSuccessor(0)];
1093  MachineBasicBlock *FBB = FuncInfo.MBBMap[Br->getSuccessor(1)];
1094
1095  bool Not;
1096  unsigned CondReg = getRegForI1Value(Br->getCondition(), Not);
1097
1098  unsigned Opc = WebAssembly::BR_IF;
1099  if (Not)
1100    Opc = WebAssembly::BR_UNLESS;
1101
1102  BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(Opc))
1103      .addMBB(TBB)
1104      .addReg(CondReg);
1105
1106  finishCondBranch(Br->getParent(), TBB, FBB);
1107  return true;
1108}
1109
1110bool WebAssemblyFastISel::selectRet(const Instruction *I) {
1111  if (!FuncInfo.CanLowerReturn)
1112    return false;
1113
1114  const ReturnInst *Ret = cast<ReturnInst>(I);
1115
1116  if (Ret->getNumOperands() == 0) {
1117    BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1118            TII.get(WebAssembly::RETURN_VOID));
1119    return true;
1120  }
1121
1122  Value *RV = Ret->getOperand(0);
1123  unsigned Opc;
1124  switch (getSimpleType(RV->getType())) {
1125  case MVT::i1: case MVT::i8:
1126  case MVT::i16: case MVT::i32:
1127    Opc = WebAssembly::RETURN_I32;
1128    break;
1129  case MVT::i64:
1130    Opc = WebAssembly::RETURN_I64;
1131    break;
1132  case MVT::f32: Opc = WebAssembly::RETURN_F32; break;
1133  case MVT::f64: Opc = WebAssembly::RETURN_F64; break;
1134  default: return false;
1135  }
1136
1137  unsigned Reg;
1138  if (FuncInfo.Fn->getAttributes().hasAttribute(0, Attribute::SExt))
1139    Reg = getRegForSignedValue(RV);
1140  else if (FuncInfo.Fn->getAttributes().hasAttribute(0, Attribute::ZExt))
1141    Reg = getRegForUnsignedValue(RV);
1142  else
1143    Reg = getRegForValue(RV);
1144
1145  BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(Opc)).addReg(Reg);
1146  return true;
1147}
1148
1149bool WebAssemblyFastISel::selectUnreachable(const Instruction *I) {
1150  BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1151          TII.get(WebAssembly::UNREACHABLE));
1152  return true;
1153}
1154
1155bool WebAssemblyFastISel::fastSelectInstruction(const Instruction *I) {
1156  switch (I->getOpcode()) {
1157  case Instruction::Call:
1158    if (selectCall(I))
1159      return true;
1160    break;
1161  case Instruction::Select:      return selectSelect(I);
1162  case Instruction::Trunc:       return selectTrunc(I);
1163  case Instruction::ZExt:        return selectZExt(I);
1164  case Instruction::SExt:        return selectSExt(I);
1165  case Instruction::ICmp:        return selectICmp(I);
1166  case Instruction::FCmp:        return selectFCmp(I);
1167  case Instruction::BitCast:     return selectBitCast(I);
1168  case Instruction::Load:        return selectLoad(I);
1169  case Instruction::Store:       return selectStore(I);
1170  case Instruction::Br:          return selectBr(I);
1171  case Instruction::Ret:         return selectRet(I);
1172  case Instruction::Unreachable: return selectUnreachable(I);
1173  default: break;
1174  }
1175
1176  // Fall back to target-independent instruction selection.
1177  return selectOperator(I, I->getOpcode());
1178}
1179
1180FastISel *WebAssembly::createFastISel(FunctionLoweringInfo &FuncInfo,
1181                                      const TargetLibraryInfo *LibInfo) {
1182  return new WebAssemblyFastISel(FuncInfo, LibInfo);
1183}
1184