lib/Target/AArch64/AArch64FastISel.cpp

   1 //===-- AArch6464FastISel.cpp - AArch64 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 // This file defines the AArch64-specific support for the FastISel class. Some
  11 // of the target-specific code is generated by tablegen in the file
  12 // AArch64GenFastISel.inc, which is #included here.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "AArch64.h"
  17 #include "AArch64Subtarget.h"
  18 #include "AArch64TargetMachine.h"
  19 #include "MCTargetDesc/AArch64AddressingModes.h"
  20 #include "llvm/Analysis/BranchProbabilityInfo.h"
  21 #include "llvm/CodeGen/CallingConvLower.h"
  22 #include "llvm/CodeGen/FastISel.h"
  23 #include "llvm/CodeGen/FunctionLoweringInfo.h"
  24 #include "llvm/CodeGen/MachineConstantPool.h"
  25 #include "llvm/CodeGen/MachineFrameInfo.h"
  26 #include "llvm/CodeGen/MachineInstrBuilder.h"
  27 #include "llvm/CodeGen/MachineRegisterInfo.h"
  28 #include "llvm/IR/CallingConv.h"
  29 #include "llvm/IR/DataLayout.h"
  30 #include "llvm/IR/DerivedTypes.h"
  31 #include "llvm/IR/Function.h"
  32 #include "llvm/IR/GetElementPtrTypeIterator.h"
  33 #include "llvm/IR/GlobalAlias.h"
  34 #include "llvm/IR/GlobalVariable.h"
  35 #include "llvm/IR/Instructions.h"
  36 #include "llvm/IR/IntrinsicInst.h"
  37 #include "llvm/IR/Operator.h"
  38 #include "llvm/Support/CommandLine.h"
  39 using namespace llvm;
  40
  41 namespace {
  42
  43 class AArch64FastISel final : public FastISel {
  44   class Address {
  45   public:
  46     typedef enum {
  47       RegBase,
  48       FrameIndexBase
  49     } BaseKind;
  50
  51   private:
  52     BaseKind Kind;
  53     AArch64_AM::ShiftExtendType ExtType;
  54     union {
  55       unsigned Reg;
  56       int FI;
  57     } Base;
  58     unsigned OffsetReg;
  59     unsigned Shift;
  60     int64_t Offset;
  61     const GlobalValue *GV;
  62
  63   public:
  64     Address() : Kind(RegBase), ExtType(AArch64_AM::InvalidShiftExtend),
  65       OffsetReg(0), Shift(0), Offset(0), GV(nullptr) { Base.Reg = 0; }
  66     void setKind(BaseKind K) { Kind = K; }
  67     BaseKind getKind() const { return Kind; }
  68     void setExtendType(AArch64_AM::ShiftExtendType E) { ExtType = E; }
  69     AArch64_AM::ShiftExtendType getExtendType() const { return ExtType; }
  70     bool isRegBase() const { return Kind == RegBase; }
  71     bool isFIBase() const { return Kind == FrameIndexBase; }
  72     void setReg(unsigned Reg) {
  73       assert(isRegBase() && "Invalid base register access!");
  74       Base.Reg = Reg;
  75     }
  76     unsigned getReg() const {
  77       assert(isRegBase() && "Invalid base register access!");
  78       return Base.Reg;
  79     }
  80     void setOffsetReg(unsigned Reg) {
  81       assert(isRegBase() && "Invalid offset register access!");
  82       OffsetReg = Reg;
  83     }
  84     unsigned getOffsetReg() const {
  85       assert(isRegBase() && "Invalid offset register access!");
  86       return OffsetReg;
  87     }
  88     void setFI(unsigned FI) {
  89       assert(isFIBase() && "Invalid base frame index  access!");
  90       Base.FI = FI;
  91     }
  92     unsigned getFI() const {
  93       assert(isFIBase() && "Invalid base frame index access!");
  94       return Base.FI;
  95     }
  96     void setOffset(int64_t O) { Offset = O; }
  97     int64_t getOffset() { return Offset; }
  98     void setShift(unsigned S) { Shift = S; }
  99     unsigned getShift() { return Shift; }
 100
 101     void setGlobalValue(const GlobalValue *G) { GV = G; }
 102     const GlobalValue *getGlobalValue() { return GV; }
 103   };
 104
 105   /// Subtarget - Keep a pointer to the AArch64Subtarget around so that we can
 106   /// make the right decision when generating code for different targets.
 107   const AArch64Subtarget *Subtarget;
 108   LLVMContext *Context;
 109
 110   bool fastLowerArguments() override;
 111   bool fastLowerCall(CallLoweringInfo &CLI) override;
 112   bool fastLowerIntrinsicCall(const IntrinsicInst *II) override;
 113
 114 private:
 115   // Selection routines.
 116   bool selectAddSub(const Instruction *I);
 117   bool selectLogicalOp(const Instruction *I);
 118   bool selectLoad(const Instruction *I);
 119   bool selectStore(const Instruction *I);
 120   bool selectBranch(const Instruction *I);
 121   bool selectIndirectBr(const Instruction *I);
 122   bool selectCmp(const Instruction *I);
 123   bool selectSelect(const Instruction *I);
 124   bool selectFPExt(const Instruction *I);
 125   bool selectFPTrunc(const Instruction *I);
 126   bool selectFPToInt(const Instruction *I, bool Signed);
 127   bool selectIntToFP(const Instruction *I, bool Signed);
 128   bool selectRem(const Instruction *I, unsigned ISDOpcode);
 129   bool selectRet(const Instruction *I);
 130   bool selectTrunc(const Instruction *I);
 131   bool selectIntExt(const Instruction *I);
 132   bool selectMul(const Instruction *I);
 133   bool selectShift(const Instruction *I);
 134   bool selectBitCast(const Instruction *I);
 135   bool selectFRem(const Instruction *I);
 136
 137   // Utility helper routines.
 138   bool isTypeLegal(Type *Ty, MVT &VT);
 139   bool isTypeSupported(Type *Ty, MVT &VT, bool IsVectorAllowed = false);
 140   bool isValueAvailable(const Value *V) const;
 141   bool computeAddress(const Value *Obj, Address &Addr, Type *Ty = nullptr);
 142   bool computeCallAddress(const Value *V, Address &Addr);
 143   bool simplifyAddress(Address &Addr, MVT VT);
 144   void addLoadStoreOperands(Address &Addr, const MachineInstrBuilder &MIB,
 145                             unsigned Flags, unsigned ScaleFactor,
 146                             MachineMemOperand *MMO);
 147   bool isMemCpySmall(uint64_t Len, unsigned Alignment);
 148   bool tryEmitSmallMemCpy(Address Dest, Address Src, uint64_t Len,
 149                           unsigned Alignment);
 150   bool foldXALUIntrinsic(AArch64CC::CondCode &CC, const Instruction *I,
 151                          const Value *Cond);
 152
 153   // Emit helper routines.
 154   unsigned emitAddSub(bool UseAdd, MVT RetVT, const Value *LHS,
 155                       const Value *RHS, bool SetFlags = false,
 156                       bool WantResult = true,  bool IsZExt = false);
 157   unsigned emitAddSub_rr(bool UseAdd, MVT RetVT, unsigned LHSReg,
 158                          bool LHSIsKill, unsigned RHSReg, bool RHSIsKill,
 159                          bool SetFlags = false, bool WantResult = true);
 160   unsigned emitAddSub_ri(bool UseAdd, MVT RetVT, unsigned LHSReg,
 161                          bool LHSIsKill, uint64_t Imm, bool SetFlags = false,
 162                          bool WantResult = true);
 163   unsigned emitAddSub_rs(bool UseAdd, MVT RetVT, unsigned LHSReg,
 164                          bool LHSIsKill, unsigned RHSReg, bool RHSIsKill,
 165                          AArch64_AM::ShiftExtendType ShiftType,
 166                          uint64_t ShiftImm, bool SetFlags = false,
 167                          bool WantResult = true);
 168   unsigned emitAddSub_rx(bool UseAdd, MVT RetVT, unsigned LHSReg,
 169                          bool LHSIsKill, unsigned RHSReg, bool RHSIsKill,
 170                           AArch64_AM::ShiftExtendType ExtType,
 171                           uint64_t ShiftImm, bool SetFlags = false,
 172                          bool WantResult = true);
 173
 174   // Emit functions.
 175   bool emitCmp(const Value *LHS, const Value *RHS, bool IsZExt);
 176   bool emitICmp(MVT RetVT, const Value *LHS, const Value *RHS, bool IsZExt);
 177   bool emitICmp_ri(MVT RetVT, unsigned LHSReg, bool LHSIsKill, uint64_t Imm);
 178   bool emitFCmp(MVT RetVT, const Value *LHS, const Value *RHS);
 179   bool emitLoad(MVT VT, unsigned &ResultReg, Address Addr,
 180                 MachineMemOperand *MMO = nullptr);
 181   bool emitStore(MVT VT, unsigned SrcReg, Address Addr,
 182                  MachineMemOperand *MMO = nullptr);
 183   unsigned emitIntExt(MVT SrcVT, unsigned SrcReg, MVT DestVT, bool isZExt);
 184   unsigned emiti1Ext(unsigned SrcReg, MVT DestVT, bool isZExt);
 185   unsigned emitAdd(MVT RetVT, const Value *LHS, const Value *RHS,
 186                    bool SetFlags = false, bool WantResult = true,
 187                    bool IsZExt = false);
 188   unsigned emitSub(MVT RetVT, const Value *LHS, const Value *RHS,
 189                    bool SetFlags = false, bool WantResult = true,
 190                    bool IsZExt = false);
 191   unsigned emitSubs_rr(MVT RetVT, unsigned LHSReg, bool LHSIsKill,
 192                        unsigned RHSReg, bool RHSIsKill, bool WantResult = true);
 193   unsigned emitSubs_rs(MVT RetVT, unsigned LHSReg, bool LHSIsKill,
 194                        unsigned RHSReg, bool RHSIsKill,
 195                        AArch64_AM::ShiftExtendType ShiftType, uint64_t ShiftImm,
 196                        bool WantResult = true);
 197   unsigned emitLogicalOp(unsigned ISDOpc, MVT RetVT, const Value *LHS,
 198                          const Value *RHS);
 199   unsigned emitLogicalOp_ri(unsigned ISDOpc, MVT RetVT, unsigned LHSReg,
 200                             bool LHSIsKill, uint64_t Imm);
 201   unsigned emitLogicalOp_rs(unsigned ISDOpc, MVT RetVT, unsigned LHSReg,
 202                             bool LHSIsKill, unsigned RHSReg, bool RHSIsKill,
 203                             uint64_t ShiftImm);
 204   unsigned emitAnd_ri(MVT RetVT, unsigned LHSReg, bool LHSIsKill, uint64_t Imm);
 205   unsigned emitMul_rr(MVT RetVT, unsigned Op0, bool Op0IsKill,
 206                       unsigned Op1, bool Op1IsKill);
 207   unsigned emitSMULL_rr(MVT RetVT, unsigned Op0, bool Op0IsKill,
 208                         unsigned Op1, bool Op1IsKill);
 209   unsigned emitUMULL_rr(MVT RetVT, unsigned Op0, bool Op0IsKill,
 210                         unsigned Op1, bool Op1IsKill);
 211   unsigned emitLSL_rr(MVT RetVT, unsigned Op0Reg, bool Op0IsKill,
 212                       unsigned Op1Reg, bool Op1IsKill);
 213   unsigned emitLSL_ri(MVT RetVT, MVT SrcVT, unsigned Op0Reg, bool Op0IsKill,
 214                       uint64_t Imm, bool IsZExt = true);
 215   unsigned emitLSR_rr(MVT RetVT, unsigned Op0Reg, bool Op0IsKill,
 216                       unsigned Op1Reg, bool Op1IsKill);
 217   unsigned emitLSR_ri(MVT RetVT, MVT SrcVT, unsigned Op0Reg, bool Op0IsKill,
 218                       uint64_t Imm, bool IsZExt = true);
 219   unsigned emitASR_rr(MVT RetVT, unsigned Op0Reg, bool Op0IsKill,
 220                       unsigned Op1Reg, bool Op1IsKill);
 221   unsigned emitASR_ri(MVT RetVT, MVT SrcVT, unsigned Op0Reg, bool Op0IsKill,
 222                       uint64_t Imm, bool IsZExt = false);
 223
 224   unsigned materializeInt(const ConstantInt *CI, MVT VT);
 225   unsigned materializeFP(const ConstantFP *CFP, MVT VT);
 226   unsigned materializeGV(const GlobalValue *GV);
 227
 228   // Call handling routines.
 229 private:
 230   CCAssignFn *CCAssignFnForCall(CallingConv::ID CC) const;
 231   bool processCallArgs(CallLoweringInfo &CLI, SmallVectorImpl<MVT> &ArgVTs,
 232                        unsigned &NumBytes);
 233   bool finishCall(CallLoweringInfo &CLI, MVT RetVT, unsigned NumBytes);
 234
 235 public:
 236   // Backend specific FastISel code.
 237   unsigned fastMaterializeAlloca(const AllocaInst *AI) override;
 238   unsigned fastMaterializeConstant(const Constant *C) override;
 239   unsigned fastMaterializeFloatZero(const ConstantFP* CF) override;
 240
 241   explicit AArch64FastISel(FunctionLoweringInfo &FuncInfo,
 242                          const TargetLibraryInfo *LibInfo)
 243       : FastISel(FuncInfo, LibInfo, /*SkipTargetIndependentISel=*/true) {
 244     Subtarget = &TM.getSubtarget<AArch64Subtarget>();
 245     Context = &FuncInfo.Fn->getContext();
 246   }
 247
 248   bool fastSelectInstruction(const Instruction *I) override;
 249
 250 #include "AArch64GenFastISel.inc"
 251 };
 252
 253 } // end anonymous namespace
 254
 255 #include "AArch64GenCallingConv.inc"
 256
 257 CCAssignFn *AArch64FastISel::CCAssignFnForCall(CallingConv::ID CC) const {
 258   if (CC == CallingConv::WebKit_JS)
 259     return CC_AArch64_WebKit_JS;
 260   return Subtarget->isTargetDarwin() ? CC_AArch64_DarwinPCS : CC_AArch64_AAPCS;
 261 }
 262
 263 unsigned AArch64FastISel::fastMaterializeAlloca(const AllocaInst *AI) {
 264   assert(TLI.getValueType(AI->getType(), true) == MVT::i64 &&
 265          "Alloca should always return a pointer.");
 266
 267   // Don't handle dynamic allocas.
 268   if (!FuncInfo.StaticAllocaMap.count(AI))
 269     return 0;
 270
 271   DenseMap<const AllocaInst *, int>::iterator SI =
 272       FuncInfo.StaticAllocaMap.find(AI);
 273
 274   if (SI != FuncInfo.StaticAllocaMap.end()) {
 275     unsigned ResultReg = createResultReg(&AArch64::GPR64spRegClass);
 276     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AArch64::ADDXri),
 277             ResultReg)
 278         .addFrameIndex(SI->second)
 279         .addImm(0)
 280         .addImm(0);
 281     return ResultReg;
 282   }
 283
 284   return 0;
 285 }
 286
 287 unsigned AArch64FastISel::materializeInt(const ConstantInt *CI, MVT VT) {
 288   if (VT > MVT::i64)
 289     return 0;
 290
 291   if (!CI->isZero())
 292     return fastEmit_i(VT, VT, ISD::Constant, CI->getZExtValue());
 293
 294   // Create a copy from the zero register to materialize a "0" value.
 295   const TargetRegisterClass *RC = (VT == MVT::i64) ? &AArch64::GPR64RegClass
 296                                                    : &AArch64::GPR32RegClass;
 297   unsigned ZeroReg = (VT == MVT::i64) ? AArch64::XZR : AArch64::WZR;
 298   unsigned ResultReg = createResultReg(RC);
 299   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(TargetOpcode::COPY),
 300           ResultReg).addReg(ZeroReg, getKillRegState(true));
 301   return ResultReg;
 302 }
 303
 304 unsigned AArch64FastISel::materializeFP(const ConstantFP *CFP, MVT VT) {
 305   // Positive zero (+0.0) has to be materialized with a fmov from the zero
 306   // register, because the immediate version of fmov cannot encode zero.
 307   if (CFP->isNullValue())
 308     return fastMaterializeFloatZero(CFP);
 309
 310   if (VT != MVT::f32 && VT != MVT::f64)
 311     return 0;
 312
 313   const APFloat Val = CFP->getValueAPF();
 314   bool Is64Bit = (VT == MVT::f64);
 315   // This checks to see if we can use FMOV instructions to materialize
 316   // a constant, otherwise we have to materialize via the constant pool.
 317   if (TLI.isFPImmLegal(Val, VT)) {
 318     int Imm =
 319         Is64Bit ? AArch64_AM::getFP64Imm(Val) : AArch64_AM::getFP32Imm(Val);
 320     assert((Imm != -1) && "Cannot encode floating-point constant.");
 321     unsigned Opc = Is64Bit ? AArch64::FMOVDi : AArch64::FMOVSi;
 322     return fastEmitInst_i(Opc, TLI.getRegClassFor(VT), Imm);
 323   }
 324
 325   // Materialize via constant pool.  MachineConstantPool wants an explicit
 326   // alignment.
 327   unsigned Align = DL.getPrefTypeAlignment(CFP->getType());
 328   if (Align == 0)
 329     Align = DL.getTypeAllocSize(CFP->getType());
 330
 331   unsigned CPI = MCP.getConstantPoolIndex(cast<Constant>(CFP), Align);
 332   unsigned ADRPReg = createResultReg(&AArch64::GPR64commonRegClass);
 333   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AArch64::ADRP),
 334           ADRPReg).addConstantPoolIndex(CPI, 0, AArch64II::MO_PAGE);
 335
 336   unsigned Opc = Is64Bit ? AArch64::LDRDui : AArch64::LDRSui;
 337   unsigned ResultReg = createResultReg(TLI.getRegClassFor(VT));
 338   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(Opc), ResultReg)
 339       .addReg(ADRPReg)
 340       .addConstantPoolIndex(CPI, 0, AArch64II::MO_PAGEOFF | AArch64II::MO_NC);
 341   return ResultReg;
 342 }
 343
 344 unsigned AArch64FastISel::materializeGV(const GlobalValue *GV) {
 345   // We can't handle thread-local variables quickly yet.
 346   if (GV->isThreadLocal())
 347     return 0;
 348
 349   // MachO still uses GOT for large code-model accesses, but ELF requires
 350   // movz/movk sequences, which FastISel doesn't handle yet.
 351   if (TM.getCodeModel() != CodeModel::Small && !Subtarget->isTargetMachO())
 352     return 0;
 353
 354   unsigned char OpFlags = Subtarget->ClassifyGlobalReference(GV, TM);
 355
 356   EVT DestEVT = TLI.getValueType(GV->getType(), true);
 357   if (!DestEVT.isSimple())
 358     return 0;
 359
 360   unsigned ADRPReg = createResultReg(&AArch64::GPR64commonRegClass);
 361   unsigned ResultReg;
 362
 363   if (OpFlags & AArch64II::MO_GOT) {
 364     // ADRP + LDRX
 365     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AArch64::ADRP),
 366             ADRPReg)
 367       .addGlobalAddress(GV, 0, AArch64II::MO_GOT | AArch64II::MO_PAGE);
 368
 369     ResultReg = createResultReg(&AArch64::GPR64RegClass);
 370     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AArch64::LDRXui),
 371             ResultReg)
 372       .addReg(ADRPReg)
 373       .addGlobalAddress(GV, 0, AArch64II::MO_GOT | AArch64II::MO_PAGEOFF |
 374                         AArch64II::MO_NC);
 375   } else if (OpFlags & AArch64II::MO_CONSTPOOL) {
 376     // We can't handle addresses loaded from a constant pool quickly yet.
 377     return 0;
 378   } else {
 379     // ADRP + ADDX
 380     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AArch64::ADRP),
 381             ADRPReg)
 382       .addGlobalAddress(GV, 0, AArch64II::MO_PAGE);
 383
 384     ResultReg = createResultReg(&AArch64::GPR64spRegClass);
 385     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AArch64::ADDXri),
 386             ResultReg)
 387       .addReg(ADRPReg)
 388       .addGlobalAddress(GV, 0, AArch64II::MO_PAGEOFF | AArch64II::MO_NC)
 389       .addImm(0);
 390   }
 391   return ResultReg;
 392 }
 393
 394 unsigned AArch64FastISel::fastMaterializeConstant(const Constant *C) {
 395   EVT CEVT = TLI.getValueType(C->getType(), true);
 396
 397   // Only handle simple types.
 398   if (!CEVT.isSimple())
 399     return 0;
 400   MVT VT = CEVT.getSimpleVT();
 401
 402   if (const auto *CI = dyn_cast<ConstantInt>(C))
 403     return materializeInt(CI, VT);
 404   else if (const ConstantFP *CFP = dyn_cast<ConstantFP>(C))
 405     return materializeFP(CFP, VT);
 406   else if (const GlobalValue *GV = dyn_cast<GlobalValue>(C))
 407     return materializeGV(GV);
 408
 409   return 0;
 410 }
 411
 412 unsigned AArch64FastISel::fastMaterializeFloatZero(const ConstantFP* CFP) {
 413   assert(CFP->isNullValue() &&
 414          "Floating-point constant is not a positive zero.");
 415   MVT VT;
 416   if (!isTypeLegal(CFP->getType(), VT))
 417     return 0;
 418
 419   if (VT != MVT::f32 && VT != MVT::f64)
 420     return 0;
 421
 422   bool Is64Bit = (VT == MVT::f64);
 423   unsigned ZReg = Is64Bit ? AArch64::XZR : AArch64::WZR;
 424   unsigned Opc = Is64Bit ? AArch64::FMOVXDr : AArch64::FMOVWSr;
 425   return fastEmitInst_r(Opc, TLI.getRegClassFor(VT), ZReg, /*IsKill=*/true);
 426 }
 427
 428 /// \brief Check if the multiply is by a power-of-2 constant.
 429 static bool isMulPowOf2(const Value *I) {
 430   if (const auto *MI = dyn_cast<MulOperator>(I)) {
 431     if (const auto *C = dyn_cast<ConstantInt>(MI->getOperand(0)))
 432       if (C->getValue().isPowerOf2())
 433         return true;
 434     if (const auto *C = dyn_cast<ConstantInt>(MI->getOperand(1)))
 435       if (C->getValue().isPowerOf2())
 436         return true;
 437   }
 438   return false;
 439 }
 440
 441 // Computes the address to get to an object.
 442 bool AArch64FastISel::computeAddress(const Value *Obj, Address &Addr, Type *Ty)
 443 {
 444   const User *U = nullptr;
 445   unsigned Opcode = Instruction::UserOp1;
 446   if (const Instruction *I = dyn_cast<Instruction>(Obj)) {
 447     // Don't walk into other basic blocks unless the object is an alloca from
 448     // another block, otherwise it may not have a virtual register assigned.
 449     if (FuncInfo.StaticAllocaMap.count(static_cast<const AllocaInst *>(Obj)) ||
 450         FuncInfo.MBBMap[I->getParent()] == FuncInfo.MBB) {
 451       Opcode = I->getOpcode();
 452       U = I;
 453     }
 454   } else if (const ConstantExpr *C = dyn_cast<ConstantExpr>(Obj)) {
 455     Opcode = C->getOpcode();
 456     U = C;
 457   }
 458
 459   if (const PointerType *Ty = dyn_cast<PointerType>(Obj->getType()))
 460     if (Ty->getAddressSpace() > 255)
 461       // Fast instruction selection doesn't support the special
 462       // address spaces.
 463       return false;
 464
 465   switch (Opcode) {
 466   default:
 467     break;
 468   case Instruction::BitCast: {
 469     // Look through bitcasts.
 470     return computeAddress(U->getOperand(0), Addr, Ty);
 471   }
 472   case Instruction::IntToPtr: {
 473     // Look past no-op inttoptrs.
 474     if (TLI.getValueType(U->getOperand(0)->getType()) == TLI.getPointerTy())
 475       return computeAddress(U->getOperand(0), Addr, Ty);
 476     break;
 477   }
 478   case Instruction::PtrToInt: {
 479     // Look past no-op ptrtoints.
 480     if (TLI.getValueType(U->getType()) == TLI.getPointerTy())
 481       return computeAddress(U->getOperand(0), Addr, Ty);
 482     break;
 483   }
 484   case Instruction::GetElementPtr: {
 485     Address SavedAddr = Addr;
 486     uint64_t TmpOffset = Addr.getOffset();
 487
 488     // Iterate through the GEP folding the constants into offsets where
 489     // we can.
 490     gep_type_iterator GTI = gep_type_begin(U);
 491     for (User::const_op_iterator i = U->op_begin() + 1, e = U->op_end(); i != e;
 492          ++i, ++GTI) {
 493       const Value *Op = *i;
 494       if (StructType *STy = dyn_cast<StructType>(*GTI)) {
 495         const StructLayout *SL = DL.getStructLayout(STy);
 496         unsigned Idx = cast<ConstantInt>(Op)->getZExtValue();
 497         TmpOffset += SL->getElementOffset(Idx);
 498       } else {
 499         uint64_t S = DL.getTypeAllocSize(GTI.getIndexedType());
 500         for (;;) {
 501           if (const ConstantInt *CI = dyn_cast<ConstantInt>(Op)) {
 502             // Constant-offset addressing.
 503             TmpOffset += CI->getSExtValue() * S;
 504             break;
 505           }
 506           if (canFoldAddIntoGEP(U, Op)) {
 507             // A compatible add with a constant operand. Fold the constant.
 508             ConstantInt *CI =
 509                 cast<ConstantInt>(cast<AddOperator>(Op)->getOperand(1));
 510             TmpOffset += CI->getSExtValue() * S;
 511             // Iterate on the other operand.
 512             Op = cast<AddOperator>(Op)->getOperand(0);
 513             continue;
 514           }
 515           // Unsupported
 516           goto unsupported_gep;
 517         }
 518       }
 519     }
 520
 521     // Try to grab the base operand now.
 522     Addr.setOffset(TmpOffset);
 523     if (computeAddress(U->getOperand(0), Addr, Ty))
 524       return true;
 525
 526     // We failed, restore everything and try the other options.
 527     Addr = SavedAddr;
 528
 529   unsupported_gep:
 530     break;
 531   }
 532   case Instruction::Alloca: {
 533     const AllocaInst *AI = cast<AllocaInst>(Obj);
 534     DenseMap<const AllocaInst *, int>::iterator SI =
 535         FuncInfo.StaticAllocaMap.find(AI);
 536     if (SI != FuncInfo.StaticAllocaMap.end()) {
 537       Addr.setKind(Address::FrameIndexBase);
 538       Addr.setFI(SI->second);
 539       return true;
 540     }
 541     break;
 542   }
 543   case Instruction::Add: {
 544     // Adds of constants are common and easy enough.
 545     const Value *LHS = U->getOperand(0);
 546     const Value *RHS = U->getOperand(1);
 547
 548     if (isa<ConstantInt>(LHS))
 549       std::swap(LHS, RHS);
 550
 551     if (const ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
 552       Addr.setOffset(Addr.getOffset() + (uint64_t)CI->getSExtValue());
 553       return computeAddress(LHS, Addr, Ty);
 554     }
 555
 556     Address Backup = Addr;
 557     if (computeAddress(LHS, Addr, Ty) && computeAddress(RHS, Addr, Ty))
 558       return true;
 559     Addr = Backup;
 560
 561     break;
 562   }
 563   case Instruction::Shl:
 564     if (Addr.getOffsetReg())
 565       break;
 566
 567     if (const auto *CI = dyn_cast<ConstantInt>(U->getOperand(1))) {
 568       unsigned Val = CI->getZExtValue();
 569       if (Val < 1 || Val > 3)
 570         break;
 571
 572       uint64_t NumBytes = 0;
 573       if (Ty && Ty->isSized()) {
 574         uint64_t NumBits = DL.getTypeSizeInBits(Ty);
 575         NumBytes = NumBits / 8;
 576         if (!isPowerOf2_64(NumBits))
 577           NumBytes = 0;
 578       }
 579
 580       if (NumBytes != (1ULL << Val))
 581         break;
 582
 583       Addr.setShift(Val);
 584       Addr.setExtendType(AArch64_AM::LSL);
 585
 586       if (const auto *I = dyn_cast<Instruction>(U->getOperand(0)))
 587         if (FuncInfo.MBBMap[I->getParent()] == FuncInfo.MBB)
 588           U = I;
 589
 590       if (const auto *ZE = dyn_cast<ZExtInst>(U))
 591         if (ZE->getOperand(0)->getType()->isIntegerTy(32))
 592           Addr.setExtendType(AArch64_AM::UXTW);
 593
 594       if (const auto *SE = dyn_cast<SExtInst>(U))
 595         if (SE->getOperand(0)->getType()->isIntegerTy(32))
 596           Addr.setExtendType(AArch64_AM::SXTW);
 597
 598       unsigned Reg = getRegForValue(U->getOperand(0));
 599       if (!Reg)
 600         return false;
 601       Addr.setOffsetReg(Reg);
 602       return true;
 603     }
 604     break;
 605   case Instruction::Mul: {
 606     if (Addr.getOffsetReg())
 607       break;
 608
 609     if (!isMulPowOf2(U))
 610       break;
 611
 612     const Value *LHS = U->getOperand(0);
 613     const Value *RHS = U->getOperand(1);
 614
 615     // Canonicalize power-of-2 value to the RHS.
 616     if (const auto *C = dyn_cast<ConstantInt>(LHS))
 617       if (C->getValue().isPowerOf2())
 618         std::swap(LHS, RHS);
 619
 620     assert(isa<ConstantInt>(RHS) && "Expected an ConstantInt.");
 621     const auto *C = cast<ConstantInt>(RHS);
 622     unsigned Val = C->getValue().logBase2();
 623     if (Val < 1 || Val > 3)
 624       break;
 625
 626     uint64_t NumBytes = 0;
 627     if (Ty && Ty->isSized()) {
 628       uint64_t NumBits = DL.getTypeSizeInBits(Ty);
 629       NumBytes = NumBits / 8;
 630       if (!isPowerOf2_64(NumBits))
 631         NumBytes = 0;
 632     }
 633
 634     if (NumBytes != (1ULL << Val))
 635       break;
 636
 637     Addr.setShift(Val);
 638     Addr.setExtendType(AArch64_AM::LSL);
 639
 640     if (const auto *I = dyn_cast<Instruction>(LHS))
 641       if (FuncInfo.MBBMap[I->getParent()] == FuncInfo.MBB)
 642         U = I;
 643
 644     if (const auto *ZE = dyn_cast<ZExtInst>(U))
 645       if (ZE->getOperand(0)->getType()->isIntegerTy(32)) {
 646         Addr.setExtendType(AArch64_AM::UXTW);
 647         LHS = U->getOperand(0);
 648       }
 649
 650     if (const auto *SE = dyn_cast<SExtInst>(U))
 651       if (SE->getOperand(0)->getType()->isIntegerTy(32)) {
 652         Addr.setExtendType(AArch64_AM::SXTW);
 653         LHS = U->getOperand(0);
 654       }
 655
 656     unsigned Reg = getRegForValue(LHS);
 657     if (!Reg)
 658       return false;
 659     Addr.setOffsetReg(Reg);
 660     return true;
 661   }
 662   } // end switch
 663
 664   if (Addr.getReg()) {
 665     if (!Addr.getOffsetReg()) {
 666       unsigned Reg = getRegForValue(Obj);
 667       if (!Reg)
 668         return false;
 669       Addr.setOffsetReg(Reg);
 670       return true;
 671     }
 672     return false;
 673   }
 674
 675   unsigned Reg = getRegForValue(Obj);
 676   if (!Reg)
 677     return false;
 678   Addr.setReg(Reg);
 679   return true;
 680 }
 681
 682 bool AArch64FastISel::computeCallAddress(const Value *V, Address &Addr) {
 683   const User *U = nullptr;
 684   unsigned Opcode = Instruction::UserOp1;
 685   bool InMBB = true;
 686
 687   if (const auto *I = dyn_cast<Instruction>(V)) {
 688     Opcode = I->getOpcode();
 689     U = I;
 690     InMBB = I->getParent() == FuncInfo.MBB->getBasicBlock();
 691   } else if (const auto *C = dyn_cast<ConstantExpr>(V)) {
 692     Opcode = C->getOpcode();
 693     U = C;
 694   }
 695
 696   switch (Opcode) {
 697   default: break;
 698   case Instruction::BitCast:
 699     // Look past bitcasts if its operand is in the same BB.
 700     if (InMBB)
 701       return computeCallAddress(U->getOperand(0), Addr);
 702     break;
 703   case Instruction::IntToPtr:
 704     // Look past no-op inttoptrs if its operand is in the same BB.
 705     if (InMBB &&
 706         TLI.getValueType(U->getOperand(0)->getType()) == TLI.getPointerTy())
 707       return computeCallAddress(U->getOperand(0), Addr);
 708     break;
 709   case Instruction::PtrToInt:
 710     // Look past no-op ptrtoints if its operand is in the same BB.
 711     if (InMBB &&
 712         TLI.getValueType(U->getType()) == TLI.getPointerTy())
 713       return computeCallAddress(U->getOperand(0), Addr);
 714     break;
 715   }
 716
 717   if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
 718     Addr.setGlobalValue(GV);
 719     return true;
 720   }
 721
 722   // If all else fails, try to materialize the value in a register.
 723   if (!Addr.getGlobalValue()) {
 724     Addr.setReg(getRegForValue(V));
 725     return Addr.getReg() != 0;
 726   }
 727
 728   return false;
 729 }
 730
 731
 732 bool AArch64FastISel::isTypeLegal(Type *Ty, MVT &VT) {
 733   EVT evt = TLI.getValueType(Ty, true);
 734
 735   // Only handle simple types.
 736   if (evt == MVT::Other || !evt.isSimple())
 737     return false;
 738   VT = evt.getSimpleVT();
 739
 740   // This is a legal type, but it's not something we handle in fast-isel.
 741   if (VT == MVT::f128)
 742     return false;
 743
 744   // Handle all other legal types, i.e. a register that will directly hold this
 745   // value.
 746   return TLI.isTypeLegal(VT);
 747 }
 748
 749 /// \brief Determine if the value type is supported by FastISel.
 750 ///
 751 /// FastISel for AArch64 can handle more value types than are legal. This adds
 752 /// simple value type such as i1, i8, and i16.
 753 bool AArch64FastISel::isTypeSupported(Type *Ty, MVT &VT, bool IsVectorAllowed) {
 754   if (Ty->isVectorTy() && !IsVectorAllowed)
 755     return false;
 756
 757   if (isTypeLegal(Ty, VT))
 758     return true;
 759
 760   // If this is a type than can be sign or zero-extended to a basic operation
 761   // go ahead and accept it now.
 762   if (VT == MVT::i1 || VT == MVT::i8 || VT == MVT::i16)
 763     return true;
 764
 765   return false;
 766 }
 767
 768 bool AArch64FastISel::isValueAvailable(const Value *V) const {
 769   if (!isa<Instruction>(V))
 770     return true;
 771
 772   const auto *I = cast<Instruction>(V);
 773   if (FuncInfo.MBBMap[I->getParent()] == FuncInfo.MBB)
 774     return true;
 775
 776   return false;
 777 }
 778
 779 bool AArch64FastISel::simplifyAddress(Address &Addr, MVT VT) {
 780   unsigned ScaleFactor;
 781   switch (VT.SimpleTy) {
 782   default: return false;
 783   case MVT::i1:  // fall-through
 784   case MVT::i8:  ScaleFactor = 1; break;
 785   case MVT::i16: ScaleFactor = 2; break;
 786   case MVT::i32: // fall-through
 787   case MVT::f32: ScaleFactor = 4; break;
 788   case MVT::i64: // fall-through
 789   case MVT::f64: ScaleFactor = 8; break;
 790   }
 791
 792   bool ImmediateOffsetNeedsLowering = false;
 793   bool RegisterOffsetNeedsLowering = false;
 794   int64_t Offset = Addr.getOffset();
 795   if (((Offset < 0) || (Offset & (ScaleFactor - 1))) && !isInt<9>(Offset))
 796     ImmediateOffsetNeedsLowering = true;
 797   else if (Offset > 0 && !(Offset & (ScaleFactor - 1)) &&
 798            !isUInt<12>(Offset / ScaleFactor))
 799     ImmediateOffsetNeedsLowering = true;
 800
 801   // Cannot encode an offset register and an immediate offset in the same
 802   // instruction. Fold the immediate offset into the load/store instruction and
 803   // emit an additonal add to take care of the offset register.
 804   if (!ImmediateOffsetNeedsLowering && Addr.getOffset() && Addr.isRegBase() &&
 805       Addr.getOffsetReg())
 806     RegisterOffsetNeedsLowering = true;
 807
 808   // Cannot encode zero register as base.
 809   if (Addr.isRegBase() && Addr.getOffsetReg() && !Addr.getReg())
 810     RegisterOffsetNeedsLowering = true;
 811
 812   // If this is a stack pointer and the offset needs to be simplified then put
 813   // the alloca address into a register, set the base type back to register and
 814   // continue. This should almost never happen.
 815   if (ImmediateOffsetNeedsLowering && Addr.isFIBase()) {
 816     unsigned ResultReg = createResultReg(&AArch64::GPR64spRegClass);
 817     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AArch64::ADDXri),
 818             ResultReg)
 819       .addFrameIndex(Addr.getFI())
 820       .addImm(0)
 821       .addImm(0);
 822     Addr.setKind(Address::RegBase);
 823     Addr.setReg(ResultReg);
 824   }
 825
 826   if (RegisterOffsetNeedsLowering) {
 827     unsigned ResultReg = 0;
 828     if (Addr.getReg()) {
 829       if (Addr.getExtendType() == AArch64_AM::SXTW ||
 830           Addr.getExtendType() == AArch64_AM::UXTW   )
 831         ResultReg = emitAddSub_rx(/*UseAdd=*/true, MVT::i64, Addr.getReg(),
 832                                   /*TODO:IsKill=*/false, Addr.getOffsetReg(),
 833                                   /*TODO:IsKill=*/false, Addr.getExtendType(),
 834                                   Addr.getShift());
 835       else
 836         ResultReg = emitAddSub_rs(/*UseAdd=*/true, MVT::i64, Addr.getReg(),
 837                                   /*TODO:IsKill=*/false, Addr.getOffsetReg(),
 838                                   /*TODO:IsKill=*/false, AArch64_AM::LSL,
 839                                   Addr.getShift());
 840     } else {
 841       if (Addr.getExtendType() == AArch64_AM::UXTW)
 842         ResultReg = emitLSL_ri(MVT::i64, MVT::i32, Addr.getOffsetReg(),
 843                                /*Op0IsKill=*/false, Addr.getShift(),
 844                                /*IsZExt=*/true);
 845       else if (Addr.getExtendType() == AArch64_AM::SXTW)
 846         ResultReg = emitLSL_ri(MVT::i64, MVT::i32, Addr.getOffsetReg(),
 847                                /*Op0IsKill=*/false, Addr.getShift(),
 848                                /*IsZExt=*/false);
 849       else
 850         ResultReg = emitLSL_ri(MVT::i64, MVT::i64, Addr.getOffsetReg(),
 851                                /*Op0IsKill=*/false, Addr.getShift());
 852     }
 853     if (!ResultReg)
 854       return false;
 855
 856     Addr.setReg(ResultReg);
 857     Addr.setOffsetReg(0);
 858     Addr.setShift(0);
 859     Addr.setExtendType(AArch64_AM::InvalidShiftExtend);
 860   }
 861
 862   // Since the offset is too large for the load/store instruction get the
 863   // reg+offset into a register.
 864   if (ImmediateOffsetNeedsLowering) {
 865     unsigned ResultReg = 0;
 866     if (Addr.getReg())
 867       ResultReg = fastEmit_ri_(MVT::i64, ISD::ADD, Addr.getReg(),
 868                                /*IsKill=*/false, Offset, MVT::i64);
 869     else
 870       ResultReg = fastEmit_i(MVT::i64, MVT::i64, ISD::Constant, Offset);
 871
 872     if (!ResultReg)
 873       return false;
 874     Addr.setReg(ResultReg);
 875     Addr.setOffset(0);
 876   }
 877   return true;
 878 }
 879
 880 void AArch64FastISel::addLoadStoreOperands(Address &Addr,
 881                                            const MachineInstrBuilder &MIB,
 882                                            unsigned Flags,
 883                                            unsigned ScaleFactor,
 884                                            MachineMemOperand *MMO) {
 885   int64_t Offset = Addr.getOffset() / ScaleFactor;
 886   // Frame base works a bit differently. Handle it separately.
 887   if (Addr.isFIBase()) {
 888     int FI = Addr.getFI();
 889     // FIXME: We shouldn't be using getObjectSize/getObjectAlignment.  The size
 890     // and alignment should be based on the VT.
 891     MMO = FuncInfo.MF->getMachineMemOperand(
 892       MachinePointerInfo::getFixedStack(FI, Offset), Flags,
 893       MFI.getObjectSize(FI), MFI.getObjectAlignment(FI));
 894     // Now add the rest of the operands.
 895     MIB.addFrameIndex(FI).addImm(Offset);
 896   } else {
 897     assert(Addr.isRegBase() && "Unexpected address kind.");
 898     const MCInstrDesc &II = MIB->getDesc();
 899     unsigned Idx = (Flags & MachineMemOperand::MOStore) ? 1 : 0;
 900     Addr.setReg(
 901       constrainOperandRegClass(II, Addr.getReg(), II.getNumDefs()+Idx));
 902     Addr.setOffsetReg(
 903       constrainOperandRegClass(II, Addr.getOffsetReg(), II.getNumDefs()+Idx+1));
 904     if (Addr.getOffsetReg()) {
 905       assert(Addr.getOffset() == 0 && "Unexpected offset");
 906       bool IsSigned = Addr.getExtendType() == AArch64_AM::SXTW ||
 907                       Addr.getExtendType() == AArch64_AM::SXTX;
 908       MIB.addReg(Addr.getReg());
 909       MIB.addReg(Addr.getOffsetReg());
 910       MIB.addImm(IsSigned);
 911       MIB.addImm(Addr.getShift() != 0);
 912     } else {
 913       MIB.addReg(Addr.getReg());
 914       MIB.addImm(Offset);
 915     }
 916   }
 917
 918   if (MMO)
 919     MIB.addMemOperand(MMO);
 920 }
 921
 922 unsigned AArch64FastISel::emitAddSub(bool UseAdd, MVT RetVT, const Value *LHS,
 923                                      const Value *RHS, bool SetFlags,
 924                                      bool WantResult,  bool IsZExt) {
 925   AArch64_AM::ShiftExtendType ExtendType = AArch64_AM::InvalidShiftExtend;
 926   bool NeedExtend = false;
 927   switch (RetVT.SimpleTy) {
 928   default:
 929     return 0;
 930   case MVT::i1:
 931     NeedExtend = true;
 932     break;
 933   case MVT::i8:
 934     NeedExtend = true;
 935     ExtendType = IsZExt ? AArch64_AM::UXTB : AArch64_AM::SXTB;
 936     break;
 937   case MVT::i16:
 938     NeedExtend = true;
 939     ExtendType = IsZExt ? AArch64_AM::UXTH : AArch64_AM::SXTH;
 940     break;
 941   case MVT::i32:  // fall-through
 942   case MVT::i64:
 943     break;
 944   }
 945   MVT SrcVT = RetVT;
 946   RetVT.SimpleTy = std::max(RetVT.SimpleTy, MVT::i32);
 947
 948   // Canonicalize immediates to the RHS first.
 949   if (UseAdd && isa<ConstantInt>(LHS) && !isa<ConstantInt>(RHS))
 950     std::swap(LHS, RHS);
 951
 952   // Canonicalize mul by power of 2 to the RHS.
 953   if (UseAdd && LHS->hasOneUse() && isValueAvailable(LHS))
 954     if (isMulPowOf2(LHS))
 955       std::swap(LHS, RHS);
 956
 957   // Canonicalize shift immediate to the RHS.
 958   if (UseAdd && LHS->hasOneUse() && isValueAvailable(LHS))
 959     if (const auto *SI = dyn_cast<BinaryOperator>(LHS))
 960       if (isa<ConstantInt>(SI->getOperand(1)))
 961         if (SI->getOpcode() == Instruction::Shl  ||
 962             SI->getOpcode() == Instruction::LShr ||
 963             SI->getOpcode() == Instruction::AShr   )
 964           std::swap(LHS, RHS);
 965
 966   unsigned LHSReg = getRegForValue(LHS);
 967   if (!LHSReg)
 968     return 0;
 969   bool LHSIsKill = hasTrivialKill(LHS);
 970
 971   if (NeedExtend)
 972     LHSReg = emitIntExt(SrcVT, LHSReg, RetVT, IsZExt);
 973
 974   unsigned ResultReg = 0;
 975   if (const auto *C = dyn_cast<ConstantInt>(RHS)) {
 976     uint64_t Imm = IsZExt ? C->getZExtValue() : C->getSExtValue();
 977     if (C->isNegative())
 978       ResultReg = emitAddSub_ri(!UseAdd, RetVT, LHSReg, LHSIsKill, -Imm,
 979                                 SetFlags, WantResult);
 980     else
 981       ResultReg = emitAddSub_ri(UseAdd, RetVT, LHSReg, LHSIsKill, Imm, SetFlags,
 982                                 WantResult);
 983   }
 984   if (ResultReg)
 985     return ResultReg;
 986
 987   // Only extend the RHS within the instruction if there is a valid extend type.
 988   if (ExtendType != AArch64_AM::InvalidShiftExtend && RHS->hasOneUse() &&
 989       isValueAvailable(RHS)) {
 990     if (const auto *SI = dyn_cast<BinaryOperator>(RHS))
 991       if (const auto *C = dyn_cast<ConstantInt>(SI->getOperand(1)))
 992         if ((SI->getOpcode() == Instruction::Shl) && (C->getZExtValue() < 4)) {
 993           unsigned RHSReg = getRegForValue(SI->getOperand(0));
 994           if (!RHSReg)
 995             return 0;
 996           bool RHSIsKill = hasTrivialKill(SI->getOperand(0));
 997           return emitAddSub_rx(UseAdd, RetVT, LHSReg, LHSIsKill, RHSReg,
 998                                RHSIsKill, ExtendType, C->getZExtValue(),
 999                                SetFlags, WantResult);
1000         }
1001     unsigned RHSReg = getRegForValue(RHS);
1002     if (!RHSReg)
1003       return 0;
1004     bool RHSIsKill = hasTrivialKill(RHS);
1005     return emitAddSub_rx(UseAdd, RetVT, LHSReg, LHSIsKill, RHSReg, RHSIsKill,
1006                          ExtendType, 0, SetFlags, WantResult);
1007   }
1008
1009   // Check if the mul can be folded into the instruction.
1010   if (RHS->hasOneUse() && isValueAvailable(RHS))
1011     if (isMulPowOf2(RHS)) {
1012       const Value *MulLHS = cast<MulOperator>(RHS)->getOperand(0);
1013       const Value *MulRHS = cast<MulOperator>(RHS)->getOperand(1);
1014
1015       if (const auto *C = dyn_cast<ConstantInt>(MulLHS))
1016         if (C->getValue().isPowerOf2())
1017           std::swap(MulLHS, MulRHS);
1018
1019       assert(isa<ConstantInt>(MulRHS) && "Expected a ConstantInt.");
1020       uint64_t ShiftVal = cast<ConstantInt>(MulRHS)->getValue().logBase2();
1021       unsigned RHSReg = getRegForValue(MulLHS);
1022       if (!RHSReg)
1023         return 0;
1024       bool RHSIsKill = hasTrivialKill(MulLHS);
1025       return emitAddSub_rs(UseAdd, RetVT, LHSReg, LHSIsKill, RHSReg, RHSIsKill,
1026                            AArch64_AM::LSL, ShiftVal, SetFlags, WantResult);
1027     }
1028
1029   // Check if the shift can be folded into the instruction.
1030   if (RHS->hasOneUse() && isValueAvailable(RHS))
1031     if (const auto *SI = dyn_cast<BinaryOperator>(RHS)) {
1032       if (const auto *C = dyn_cast<ConstantInt>(SI->getOperand(1))) {
1033         AArch64_AM::ShiftExtendType ShiftType = AArch64_AM::InvalidShiftExtend;
1034         switch (SI->getOpcode()) {
1035         default: break;
1036         case Instruction::Shl:  ShiftType = AArch64_AM::LSL; break;
1037         case Instruction::LShr: ShiftType = AArch64_AM::LSR; break;
1038         case Instruction::AShr: ShiftType = AArch64_AM::ASR; break;
1039         }
1040         uint64_t ShiftVal = C->getZExtValue();
1041         if (ShiftType != AArch64_AM::InvalidShiftExtend) {
1042           unsigned RHSReg = getRegForValue(SI->getOperand(0));
1043           if (!RHSReg)
1044             return 0;
1045           bool RHSIsKill = hasTrivialKill(SI->getOperand(0));
1046           return emitAddSub_rs(UseAdd, RetVT, LHSReg, LHSIsKill, RHSReg,
1047                                RHSIsKill, ShiftType, ShiftVal, SetFlags,
1048                                WantResult);
1049         }
1050       }
1051     }
1052
1053   unsigned RHSReg = getRegForValue(RHS);
1054   if (!RHSReg)
1055     return 0;
1056   bool RHSIsKill = hasTrivialKill(RHS);
1057
1058   if (NeedExtend)
1059     RHSReg = emitIntExt(SrcVT, RHSReg, RetVT, IsZExt);
1060
1061   return emitAddSub_rr(UseAdd, RetVT, LHSReg, LHSIsKill, RHSReg, RHSIsKill,
1062                        SetFlags, WantResult);
1063 }
1064
1065 unsigned AArch64FastISel::emitAddSub_rr(bool UseAdd, MVT RetVT, unsigned LHSReg,
1066                                         bool LHSIsKill, unsigned RHSReg,
1067                                         bool RHSIsKill, bool SetFlags,
1068                                         bool WantResult) {
1069   assert(LHSReg && RHSReg && "Invalid register number.");
1070
1071   if (RetVT != MVT::i32 && RetVT != MVT::i64)
1072     return 0;
1073
1074   static const unsigned OpcTable[2][2][2] = {
1075     { { AArch64::SUBWrr,  AArch64::SUBXrr  },
1076       { AArch64::ADDWrr,  AArch64::ADDXrr  }  },
1077     { { AArch64::SUBSWrr, AArch64::SUBSXrr },
1078       { AArch64::ADDSWrr, AArch64::ADDSXrr }  }
1079   };
1080   bool Is64Bit = RetVT == MVT::i64;
1081   unsigned Opc = OpcTable[SetFlags][UseAdd][Is64Bit];
1082   const TargetRegisterClass *RC =
1083       Is64Bit ? &AArch64::GPR64RegClass : &AArch64::GPR32RegClass;
1084   unsigned ResultReg;
1085   if (WantResult)
1086     ResultReg = createResultReg(RC);
1087   else
1088     ResultReg = Is64Bit ? AArch64::XZR : AArch64::WZR;
1089
1090   const MCInstrDesc &II = TII.get(Opc);
1091   LHSReg = constrainOperandRegClass(II, LHSReg, II.getNumDefs());
1092   RHSReg = constrainOperandRegClass(II, RHSReg, II.getNumDefs() + 1);
1093   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
1094       .addReg(LHSReg, getKillRegState(LHSIsKill))
1095       .addReg(RHSReg, getKillRegState(RHSIsKill));
1096   return ResultReg;
1097 }
1098
1099 unsigned AArch64FastISel::emitAddSub_ri(bool UseAdd, MVT RetVT, unsigned LHSReg,
1100                                         bool LHSIsKill, uint64_t Imm,
1101                                         bool SetFlags, bool WantResult) {
1102   assert(LHSReg && "Invalid register number.");
1103
1104   if (RetVT != MVT::i32 && RetVT != MVT::i64)
1105     return 0;
1106
1107   unsigned ShiftImm;
1108   if (isUInt<12>(Imm))
1109     ShiftImm = 0;
1110   else if ((Imm & 0xfff000) == Imm) {
1111     ShiftImm = 12;
1112     Imm >>= 12;
1113   } else
1114     return 0;
1115
1116   static const unsigned OpcTable[2][2][2] = {
1117     { { AArch64::SUBWri,  AArch64::SUBXri  },
1118       { AArch64::ADDWri,  AArch64::ADDXri  }  },
1119     { { AArch64::SUBSWri, AArch64::SUBSXri },
1120       { AArch64::ADDSWri, AArch64::ADDSXri }  }
1121   };
1122   bool Is64Bit = RetVT == MVT::i64;
1123   unsigned Opc = OpcTable[SetFlags][UseAdd][Is64Bit];
1124   const TargetRegisterClass *RC;
1125   if (SetFlags)
1126     RC = Is64Bit ? &AArch64::GPR64RegClass : &AArch64::GPR32RegClass;
1127   else
1128     RC = Is64Bit ? &AArch64::GPR64spRegClass : &AArch64::GPR32spRegClass;
1129   unsigned ResultReg;
1130   if (WantResult)
1131     ResultReg = createResultReg(RC);
1132   else
1133     ResultReg = Is64Bit ? AArch64::XZR : AArch64::WZR;
1134
1135   const MCInstrDesc &II = TII.get(Opc);
1136   LHSReg = constrainOperandRegClass(II, LHSReg, II.getNumDefs());
1137   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
1138       .addReg(LHSReg, getKillRegState(LHSIsKill))
1139       .addImm(Imm)
1140       .addImm(getShifterImm(AArch64_AM::LSL, ShiftImm));
1141   return ResultReg;
1142 }
1143
1144 unsigned AArch64FastISel::emitAddSub_rs(bool UseAdd, MVT RetVT, unsigned LHSReg,
1145                                         bool LHSIsKill, unsigned RHSReg,
1146                                         bool RHSIsKill,
1147                                         AArch64_AM::ShiftExtendType ShiftType,
1148                                         uint64_t ShiftImm, bool SetFlags,
1149                                         bool WantResult) {
1150   assert(LHSReg && RHSReg && "Invalid register number.");
1151
1152   if (RetVT != MVT::i32 && RetVT != MVT::i64)
1153     return 0;
1154
1155   static const unsigned OpcTable[2][2][2] = {
1156     { { AArch64::SUBWrs,  AArch64::SUBXrs  },
1157       { AArch64::ADDWrs,  AArch64::ADDXrs  }  },
1158     { { AArch64::SUBSWrs, AArch64::SUBSXrs },
1159       { AArch64::ADDSWrs, AArch64::ADDSXrs }  }
1160   };
1161   bool Is64Bit = RetVT == MVT::i64;
1162   unsigned Opc = OpcTable[SetFlags][UseAdd][Is64Bit];
1163   const TargetRegisterClass *RC =
1164       Is64Bit ? &AArch64::GPR64RegClass : &AArch64::GPR32RegClass;
1165   unsigned ResultReg;
1166   if (WantResult)
1167     ResultReg = createResultReg(RC);
1168   else
1169     ResultReg = Is64Bit ? AArch64::XZR : AArch64::WZR;
1170
1171   const MCInstrDesc &II = TII.get(Opc);
1172   LHSReg = constrainOperandRegClass(II, LHSReg, II.getNumDefs());
1173   RHSReg = constrainOperandRegClass(II, RHSReg, II.getNumDefs() + 1);
1174   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
1175       .addReg(LHSReg, getKillRegState(LHSIsKill))
1176       .addReg(RHSReg, getKillRegState(RHSIsKill))
1177       .addImm(getShifterImm(ShiftType, ShiftImm));
1178   return ResultReg;
1179 }
1180
1181 unsigned AArch64FastISel::emitAddSub_rx(bool UseAdd, MVT RetVT, unsigned LHSReg,
1182                                         bool LHSIsKill, unsigned RHSReg,
1183                                         bool RHSIsKill,
1184                                         AArch64_AM::ShiftExtendType ExtType,
1185                                         uint64_t ShiftImm, bool SetFlags,
1186                                         bool WantResult) {
1187   assert(LHSReg && RHSReg && "Invalid register number.");
1188
1189   if (RetVT != MVT::i32 && RetVT != MVT::i64)
1190     return 0;
1191
1192   static const unsigned OpcTable[2][2][2] = {
1193     { { AArch64::SUBWrx,  AArch64::SUBXrx  },
1194       { AArch64::ADDWrx,  AArch64::ADDXrx  }  },
1195     { { AArch64::SUBSWrx, AArch64::SUBSXrx },
1196       { AArch64::ADDSWrx, AArch64::ADDSXrx }  }
1197   };
1198   bool Is64Bit = RetVT == MVT::i64;
1199   unsigned Opc = OpcTable[SetFlags][UseAdd][Is64Bit];
1200   const TargetRegisterClass *RC = nullptr;
1201   if (SetFlags)
1202     RC = Is64Bit ? &AArch64::GPR64RegClass : &AArch64::GPR32RegClass;
1203   else
1204     RC = Is64Bit ? &AArch64::GPR64spRegClass : &AArch64::GPR32spRegClass;
1205   unsigned ResultReg;
1206   if (WantResult)
1207     ResultReg = createResultReg(RC);
1208   else
1209     ResultReg = Is64Bit ? AArch64::XZR : AArch64::WZR;
1210
1211   const MCInstrDesc &II = TII.get(Opc);
1212   LHSReg = constrainOperandRegClass(II, LHSReg, II.getNumDefs());
1213   RHSReg = constrainOperandRegClass(II, RHSReg, II.getNumDefs() + 1);
1214   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
1215       .addReg(LHSReg, getKillRegState(LHSIsKill))
1216       .addReg(RHSReg, getKillRegState(RHSIsKill))
1217       .addImm(getArithExtendImm(ExtType, ShiftImm));
1218   return ResultReg;
1219 }
1220
1221 bool AArch64FastISel::emitCmp(const Value *LHS, const Value *RHS, bool IsZExt) {
1222   Type *Ty = LHS->getType();
1223   EVT EVT = TLI.getValueType(Ty, true);
1224   if (!EVT.isSimple())
1225     return false;
1226   MVT VT = EVT.getSimpleVT();
1227
1228   switch (VT.SimpleTy) {
1229   default:
1230     return false;
1231   case MVT::i1:
1232   case MVT::i8:
1233   case MVT::i16:
1234   case MVT::i32:
1235   case MVT::i64:
1236     return emitICmp(VT, LHS, RHS, IsZExt);
1237   case MVT::f32:
1238   case MVT::f64:
1239     return emitFCmp(VT, LHS, RHS);
1240   }
1241 }
1242
1243 bool AArch64FastISel::emitICmp(MVT RetVT, const Value *LHS, const Value *RHS,
1244                                bool IsZExt) {
1245   return emitSub(RetVT, LHS, RHS, /*SetFlags=*/true, /*WantResult=*/false,
1246                  IsZExt) != 0;
1247 }
1248
1249 bool AArch64FastISel::emitICmp_ri(MVT RetVT, unsigned LHSReg, bool LHSIsKill,
1250                                   uint64_t Imm) {
1251   return emitAddSub_ri(/*UseAdd=*/false, RetVT, LHSReg, LHSIsKill, Imm,
1252                        /*SetFlags=*/true, /*WantResult=*/false) != 0;
1253 }
1254
1255 bool AArch64FastISel::emitFCmp(MVT RetVT, const Value *LHS, const Value *RHS) {
1256   if (RetVT != MVT::f32 && RetVT != MVT::f64)
1257     return false;
1258
1259   // Check to see if the 2nd operand is a constant that we can encode directly
1260   // in the compare.
1261   bool UseImm = false;
1262   if (const auto *CFP = dyn_cast<ConstantFP>(RHS))
1263     if (CFP->isZero() && !CFP->isNegative())
1264       UseImm = true;
1265
1266   unsigned LHSReg = getRegForValue(LHS);
1267   if (!LHSReg)
1268     return false;
1269   bool LHSIsKill = hasTrivialKill(LHS);
1270
1271   if (UseImm) {
1272     unsigned Opc = (RetVT == MVT::f64) ? AArch64::FCMPDri : AArch64::FCMPSri;
1273     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(Opc))
1274         .addReg(LHSReg, getKillRegState(LHSIsKill));
1275     return true;
1276   }
1277
1278   unsigned RHSReg = getRegForValue(RHS);
1279   if (!RHSReg)
1280     return false;
1281   bool RHSIsKill = hasTrivialKill(RHS);
1282
1283   unsigned Opc = (RetVT == MVT::f64) ? AArch64::FCMPDrr : AArch64::FCMPSrr;
1284   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(Opc))
1285       .addReg(LHSReg, getKillRegState(LHSIsKill))
1286       .addReg(RHSReg, getKillRegState(RHSIsKill));
1287   return true;
1288 }
1289
1290 unsigned AArch64FastISel::emitAdd(MVT RetVT, const Value *LHS, const Value *RHS,
1291                                   bool SetFlags, bool WantResult, bool IsZExt) {
1292   return emitAddSub(/*UseAdd=*/true, RetVT, LHS, RHS, SetFlags, WantResult,
1293                     IsZExt);
1294 }
1295
1296 unsigned AArch64FastISel::emitSub(MVT RetVT, const Value *LHS, const Value *RHS,
1297                                   bool SetFlags, bool WantResult, bool IsZExt) {
1298   return emitAddSub(/*UseAdd=*/false, RetVT, LHS, RHS, SetFlags, WantResult,
1299                     IsZExt);
1300 }
1301
1302 unsigned AArch64FastISel::emitSubs_rr(MVT RetVT, unsigned LHSReg,
1303                                       bool LHSIsKill, unsigned RHSReg,
1304                                       bool RHSIsKill, bool WantResult) {
1305   return emitAddSub_rr(/*UseAdd=*/false, RetVT, LHSReg, LHSIsKill, RHSReg,
1306                        RHSIsKill, /*SetFlags=*/true, WantResult);
1307 }
1308
1309 unsigned AArch64FastISel::emitSubs_rs(MVT RetVT, unsigned LHSReg,
1310                                       bool LHSIsKill, unsigned RHSReg,
1311                                       bool RHSIsKill,
1312                                       AArch64_AM::ShiftExtendType ShiftType,
1313                                       uint64_t ShiftImm, bool WantResult) {
1314   return emitAddSub_rs(/*UseAdd=*/false, RetVT, LHSReg, LHSIsKill, RHSReg,
1315                        RHSIsKill, ShiftType, ShiftImm, /*SetFlags=*/true,
1316                        WantResult);
1317 }
1318
1319 unsigned AArch64FastISel::emitLogicalOp(unsigned ISDOpc, MVT RetVT,
1320                                         const Value *LHS, const Value *RHS) {
1321   // Canonicalize immediates to the RHS first.
1322   if (isa<ConstantInt>(LHS) && !isa<ConstantInt>(RHS))
1323     std::swap(LHS, RHS);
1324
1325   // Canonicalize mul by power-of-2 to the RHS.
1326   if (LHS->hasOneUse() && isValueAvailable(LHS))
1327     if (isMulPowOf2(LHS))
1328       std::swap(LHS, RHS);
1329
1330   // Canonicalize shift immediate to the RHS.
1331   if (LHS->hasOneUse() && isValueAvailable(LHS))
1332     if (const auto *SI = dyn_cast<ShlOperator>(LHS))
1333       if (isa<ConstantInt>(SI->getOperand(1)))
1334         std::swap(LHS, RHS);
1335
1336   unsigned LHSReg = getRegForValue(LHS);
1337   if (!LHSReg)
1338     return 0;
1339   bool LHSIsKill = hasTrivialKill(LHS);
1340
1341   unsigned ResultReg = 0;
1342   if (const auto *C = dyn_cast<ConstantInt>(RHS)) {
1343     uint64_t Imm = C->getZExtValue();
1344     ResultReg = emitLogicalOp_ri(ISDOpc, RetVT, LHSReg, LHSIsKill, Imm);
1345   }
1346   if (ResultReg)
1347     return ResultReg;
1348
1349   // Check if the mul can be folded into the instruction.
1350   if (RHS->hasOneUse() && isValueAvailable(RHS))
1351     if (isMulPowOf2(RHS)) {
1352       const Value *MulLHS = cast<MulOperator>(RHS)->getOperand(0);
1353       const Value *MulRHS = cast<MulOperator>(RHS)->getOperand(1);
1354
1355       if (const auto *C = dyn_cast<ConstantInt>(MulLHS))
1356         if (C->getValue().isPowerOf2())
1357           std::swap(MulLHS, MulRHS);
1358
1359       assert(isa<ConstantInt>(MulRHS) && "Expected a ConstantInt.");
1360       uint64_t ShiftVal = cast<ConstantInt>(MulRHS)->getValue().logBase2();
1361
1362       unsigned RHSReg = getRegForValue(MulLHS);
1363       if (!RHSReg)
1364         return 0;
1365       bool RHSIsKill = hasTrivialKill(MulLHS);
1366       return emitLogicalOp_rs(ISDOpc, RetVT, LHSReg, LHSIsKill, RHSReg,
1367                               RHSIsKill, ShiftVal);
1368     }
1369
1370   // Check if the shift can be folded into the instruction.
1371   if (RHS->hasOneUse() && isValueAvailable(RHS))
1372     if (const auto *SI = dyn_cast<ShlOperator>(RHS))
1373       if (const auto *C = dyn_cast<ConstantInt>(SI->getOperand(1))) {
1374         uint64_t ShiftVal = C->getZExtValue();
1375         unsigned RHSReg = getRegForValue(SI->getOperand(0));
1376         if (!RHSReg)
1377           return 0;
1378         bool RHSIsKill = hasTrivialKill(SI->getOperand(0));
1379         return emitLogicalOp_rs(ISDOpc, RetVT, LHSReg, LHSIsKill, RHSReg,
1380                                 RHSIsKill, ShiftVal);
1381       }
1382
1383   unsigned RHSReg = getRegForValue(RHS);
1384   if (!RHSReg)
1385     return 0;
1386   bool RHSIsKill = hasTrivialKill(RHS);
1387
1388   MVT VT = std::max(MVT::i32, RetVT.SimpleTy);
1389   ResultReg = fastEmit_rr(VT, VT, ISDOpc, LHSReg, LHSIsKill, RHSReg, RHSIsKill);
1390   if (RetVT >= MVT::i8 && RetVT <= MVT::i16) {
1391     uint64_t Mask = (RetVT == MVT::i8) ? 0xff : 0xffff;
1392     ResultReg = emitAnd_ri(MVT::i32, ResultReg, /*IsKill=*/true, Mask);
1393   }
1394   return ResultReg;
1395 }
1396
1397 unsigned AArch64FastISel::emitLogicalOp_ri(unsigned ISDOpc, MVT RetVT,
1398                                            unsigned LHSReg, bool LHSIsKill,
1399                                            uint64_t Imm) {
1400   assert((ISD::AND + 1 == ISD::OR) && (ISD::AND + 2 == ISD::XOR) &&
1401          "ISD nodes are not consecutive!");
1402   static const unsigned OpcTable[3][2] = {
1403     { AArch64::ANDWri, AArch64::ANDXri },
1404     { AArch64::ORRWri, AArch64::ORRXri },
1405     { AArch64::EORWri, AArch64::EORXri }
1406   };
1407   const TargetRegisterClass *RC;
1408   unsigned Opc;
1409   unsigned RegSize;
1410   switch (RetVT.SimpleTy) {
1411   default:
1412     return 0;
1413   case MVT::i1:
1414   case MVT::i8:
1415   case MVT::i16:
1416   case MVT::i32: {
1417     unsigned Idx = ISDOpc - ISD::AND;
1418     Opc = OpcTable[Idx][0];
1419     RC = &AArch64::GPR32spRegClass;
1420     RegSize = 32;
1421     break;
1422   }
1423   case MVT::i64:
1424     Opc = OpcTable[ISDOpc - ISD::AND][1];
1425     RC = &AArch64::GPR64spRegClass;
1426     RegSize = 64;
1427     break;
1428   }
1429
1430   if (!AArch64_AM::isLogicalImmediate(Imm, RegSize))
1431     return 0;
1432
1433   unsigned ResultReg =
1434       fastEmitInst_ri(Opc, RC, LHSReg, LHSIsKill,
1435                       AArch64_AM::encodeLogicalImmediate(Imm, RegSize));
1436   if (RetVT >= MVT::i8 && RetVT <= MVT::i16 && ISDOpc != ISD::AND) {
1437     uint64_t Mask = (RetVT == MVT::i8) ? 0xff : 0xffff;
1438     ResultReg = emitAnd_ri(MVT::i32, ResultReg, /*IsKill=*/true, Mask);
1439   }
1440   return ResultReg;
1441 }
1442
1443 unsigned AArch64FastISel::emitLogicalOp_rs(unsigned ISDOpc, MVT RetVT,
1444                                            unsigned LHSReg, bool LHSIsKill,
1445                                            unsigned RHSReg, bool RHSIsKill,
1446                                            uint64_t ShiftImm) {
1447   assert((ISD::AND + 1 == ISD::OR) && (ISD::AND + 2 == ISD::XOR) &&
1448          "ISD nodes are not consecutive!");
1449   static const unsigned OpcTable[3][2] = {
1450     { AArch64::ANDWrs, AArch64::ANDXrs },
1451     { AArch64::ORRWrs, AArch64::ORRXrs },
1452     { AArch64::EORWrs, AArch64::EORXrs }
1453   };
1454   const TargetRegisterClass *RC;
1455   unsigned Opc;
1456   switch (RetVT.SimpleTy) {
1457   default:
1458     return 0;
1459   case MVT::i1:
1460   case MVT::i8:
1461   case MVT::i16:
1462   case MVT::i32:
1463     Opc = OpcTable[ISDOpc - ISD::AND][0];
1464     RC = &AArch64::GPR32RegClass;
1465     break;
1466   case MVT::i64:
1467     Opc = OpcTable[ISDOpc - ISD::AND][1];
1468     RC = &AArch64::GPR64RegClass;
1469     break;
1470   }
1471   unsigned ResultReg =
1472       fastEmitInst_rri(Opc, RC, LHSReg, LHSIsKill, RHSReg, RHSIsKill,
1473                        AArch64_AM::getShifterImm(AArch64_AM::LSL, ShiftImm));
1474   if (RetVT >= MVT::i8 && RetVT <= MVT::i16) {
1475     uint64_t Mask = (RetVT == MVT::i8) ? 0xff : 0xffff;
1476     ResultReg = emitAnd_ri(MVT::i32, ResultReg, /*IsKill=*/true, Mask);
1477   }
1478   return ResultReg;
1479 }
1480
1481 unsigned AArch64FastISel::emitAnd_ri(MVT RetVT, unsigned LHSReg, bool LHSIsKill,
1482                                      uint64_t Imm) {
1483   return emitLogicalOp_ri(ISD::AND, RetVT, LHSReg, LHSIsKill, Imm);
1484 }
1485
1486 bool AArch64FastISel::emitLoad(MVT VT, unsigned &ResultReg, Address Addr,
1487                                MachineMemOperand *MMO) {
1488   // Simplify this down to something we can handle.
1489   if (!simplifyAddress(Addr, VT))
1490     return false;
1491
1492   unsigned ScaleFactor;
1493   switch (VT.SimpleTy) {
1494   default: llvm_unreachable("Unexpected value type.");
1495   case MVT::i1:  // fall-through
1496   case MVT::i8:  ScaleFactor = 1; break;
1497   case MVT::i16: ScaleFactor = 2; break;
1498   case MVT::i32: // fall-through
1499   case MVT::f32: ScaleFactor = 4; break;
1500   case MVT::i64: // fall-through
1501   case MVT::f64: ScaleFactor = 8; break;
1502   }
1503
1504   // Negative offsets require unscaled, 9-bit, signed immediate offsets.
1505   // Otherwise, we try using scaled, 12-bit, unsigned immediate offsets.
1506   bool UseScaled = true;
1507   if ((Addr.getOffset() < 0) || (Addr.getOffset() & (ScaleFactor - 1))) {
1508     UseScaled = false;
1509     ScaleFactor = 1;
1510   }
1511
1512   static const unsigned OpcTable[4][6] = {
1513     { AArch64::LDURBBi,  AArch64::LDURHHi,  AArch64::LDURWi,  AArch64::LDURXi,
1514       AArch64::LDURSi,   AArch64::LDURDi },
1515     { AArch64::LDRBBui,  AArch64::LDRHHui,  AArch64::LDRWui,  AArch64::LDRXui,
1516       AArch64::LDRSui,   AArch64::LDRDui },
1517     { AArch64::LDRBBroX, AArch64::LDRHHroX, AArch64::LDRWroX, AArch64::LDRXroX,
1518       AArch64::LDRSroX,  AArch64::LDRDroX },
1519     { AArch64::LDRBBroW, AArch64::LDRHHroW, AArch64::LDRWroW, AArch64::LDRXroW,
1520       AArch64::LDRSroW,  AArch64::LDRDroW }
1521   };
1522
1523   unsigned Opc;
1524   const TargetRegisterClass *RC;
1525   bool VTIsi1 = false;
1526   bool UseRegOffset = Addr.isRegBase() && !Addr.getOffset() && Addr.getReg() &&
1527                       Addr.getOffsetReg();
1528   unsigned Idx = UseRegOffset ? 2 : UseScaled ? 1 : 0;
1529   if (Addr.getExtendType() == AArch64_AM::UXTW ||
1530       Addr.getExtendType() == AArch64_AM::SXTW)
1531     Idx++;
1532
1533   switch (VT.SimpleTy) {
1534   default: llvm_unreachable("Unexpected value type.");
1535   case MVT::i1:  VTIsi1 = true; // Intentional fall-through.
1536   case MVT::i8:  Opc = OpcTable[Idx][0]; RC = &AArch64::GPR32RegClass; break;
1537   case MVT::i16: Opc = OpcTable[Idx][1]; RC = &AArch64::GPR32RegClass; break;
1538   case MVT::i32: Opc = OpcTable[Idx][2]; RC = &AArch64::GPR32RegClass; break;
1539   case MVT::i64: Opc = OpcTable[Idx][3]; RC = &AArch64::GPR64RegClass; break;
1540   case MVT::f32: Opc = OpcTable[Idx][4]; RC = &AArch64::FPR32RegClass; break;
1541   case MVT::f64: Opc = OpcTable[Idx][5]; RC = &AArch64::FPR64RegClass; break;
1542   }
1543
1544   // Create the base instruction, then add the operands.
1545   ResultReg = createResultReg(RC);
1546   MachineInstrBuilder MIB = BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1547                                     TII.get(Opc), ResultReg);
1548   addLoadStoreOperands(Addr, MIB, MachineMemOperand::MOLoad, ScaleFactor, MMO);
1549
1550   // Loading an i1 requires special handling.
1551   if (VTIsi1) {
1552     unsigned ANDReg = emitAnd_ri(MVT::i32, ResultReg, /*IsKill=*/true, 1);
1553     assert(ANDReg && "Unexpected AND instruction emission failure.");
1554     ResultReg = ANDReg;
1555   }
1556   return true;
1557 }
1558
1559 bool AArch64FastISel::selectAddSub(const Instruction *I) {
1560   MVT VT;
1561   if (!isTypeSupported(I->getType(), VT, /*IsVectorAllowed=*/true))
1562     return false;
1563
1564   if (VT.isVector())
1565     return selectOperator(I, I->getOpcode());
1566
1567   unsigned ResultReg;
1568   switch (I->getOpcode()) {
1569   default:
1570     llvm_unreachable("Unexpected instruction.");
1571   case Instruction::Add:
1572     ResultReg = emitAdd(VT, I->getOperand(0), I->getOperand(1));
1573     break;
1574   case Instruction::Sub:
1575     ResultReg = emitSub(VT, I->getOperand(0), I->getOperand(1));
1576     break;
1577   }
1578   if (!ResultReg)
1579     return false;
1580
1581   updateValueMap(I, ResultReg);
1582   return true;
1583 }
1584
1585 bool AArch64FastISel::selectLogicalOp(const Instruction *I) {
1586   MVT VT;
1587   if (!isTypeSupported(I->getType(), VT, /*IsVectorAllowed=*/true))
1588     return false;
1589
1590   if (VT.isVector())
1591     return selectOperator(I, I->getOpcode());
1592
1593   unsigned ResultReg;
1594   switch (I->getOpcode()) {
1595   default:
1596     llvm_unreachable("Unexpected instruction.");
1597   case Instruction::And:
1598     ResultReg = emitLogicalOp(ISD::AND, VT, I->getOperand(0), I->getOperand(1));
1599     break;
1600   case Instruction::Or:
1601     ResultReg = emitLogicalOp(ISD::OR, VT, I->getOperand(0), I->getOperand(1));
1602     break;
1603   case Instruction::Xor:
1604     ResultReg = emitLogicalOp(ISD::XOR, VT, I->getOperand(0), I->getOperand(1));
1605     break;
1606   }
1607   if (!ResultReg)
1608     return false;
1609
1610   updateValueMap(I, ResultReg);
1611   return true;
1612 }
1613
1614 bool AArch64FastISel::selectLoad(const Instruction *I) {
1615   MVT VT;
1616   // Verify we have a legal type before going any further.  Currently, we handle
1617   // simple types that will directly fit in a register (i32/f32/i64/f64) or
1618   // those that can be sign or zero-extended to a basic operation (i1/i8/i16).
1619   if (!isTypeSupported(I->getType(), VT, /*IsVectorAllowed=*/true) ||
1620       cast<LoadInst>(I)->isAtomic())
1621     return false;
1622
1623   // See if we can handle this address.
1624   Address Addr;
1625   if (!computeAddress(I->getOperand(0), Addr, I->getType()))
1626     return false;
1627
1628   unsigned ResultReg;
1629   if (!emitLoad(VT, ResultReg, Addr, createMachineMemOperandFor(I)))
1630     return false;
1631
1632   updateValueMap(I, ResultReg);
1633   return true;
1634 }
1635
1636 bool AArch64FastISel::emitStore(MVT VT, unsigned SrcReg, Address Addr,
1637                                 MachineMemOperand *MMO) {
1638   // Simplify this down to something we can handle.
1639   if (!simplifyAddress(Addr, VT))
1640     return false;
1641
1642   unsigned ScaleFactor;
1643   switch (VT.SimpleTy) {
1644   default: llvm_unreachable("Unexpected value type.");
1645   case MVT::i1:  // fall-through
1646   case MVT::i8:  ScaleFactor = 1; break;
1647   case MVT::i16: ScaleFactor = 2; break;
1648   case MVT::i32: // fall-through
1649   case MVT::f32: ScaleFactor = 4; break;
1650   case MVT::i64: // fall-through
1651   case MVT::f64: ScaleFactor = 8; break;
1652   }
1653
1654   // Negative offsets require unscaled, 9-bit, signed immediate offsets.
1655   // Otherwise, we try using scaled, 12-bit, unsigned immediate offsets.
1656   bool UseScaled = true;
1657   if ((Addr.getOffset() < 0) || (Addr.getOffset() & (ScaleFactor - 1))) {
1658     UseScaled = false;
1659     ScaleFactor = 1;
1660   }
1661
1662
1663   static const unsigned OpcTable[4][6] = {
1664     { AArch64::STURBBi,  AArch64::STURHHi,  AArch64::STURWi,  AArch64::STURXi,
1665       AArch64::STURSi,   AArch64::STURDi },
1666     { AArch64::STRBBui,  AArch64::STRHHui,  AArch64::STRWui,  AArch64::STRXui,
1667       AArch64::STRSui,   AArch64::STRDui },
1668     { AArch64::STRBBroX, AArch64::STRHHroX, AArch64::STRWroX, AArch64::STRXroX,
1669       AArch64::STRSroX,  AArch64::STRDroX },
1670     { AArch64::STRBBroW, AArch64::STRHHroW, AArch64::STRWroW, AArch64::STRXroW,
1671       AArch64::STRSroW,  AArch64::STRDroW }
1672
1673   };
1674
1675   unsigned Opc;
1676   bool VTIsi1 = false;
1677   bool UseRegOffset = Addr.isRegBase() && !Addr.getOffset() && Addr.getReg() &&
1678                       Addr.getOffsetReg();
1679   unsigned Idx = UseRegOffset ? 2 : UseScaled ? 1 : 0;
1680   if (Addr.getExtendType() == AArch64_AM::UXTW ||
1681       Addr.getExtendType() == AArch64_AM::SXTW)
1682     Idx++;
1683
1684   switch (VT.SimpleTy) {
1685   default: llvm_unreachable("Unexpected value type.");
1686   case MVT::i1:  VTIsi1 = true;
1687   case MVT::i8:  Opc = OpcTable[Idx][0]; break;
1688   case MVT::i16: Opc = OpcTable[Idx][1]; break;
1689   case MVT::i32: Opc = OpcTable[Idx][2]; break;
1690   case MVT::i64: Opc = OpcTable[Idx][3]; break;
1691   case MVT::f32: Opc = OpcTable[Idx][4]; break;
1692   case MVT::f64: Opc = OpcTable[Idx][5]; break;
1693   }
1694
1695   // Storing an i1 requires special handling.
1696   if (VTIsi1 && SrcReg != AArch64::WZR) {
1697     unsigned ANDReg = emitAnd_ri(MVT::i32, SrcReg, /*TODO:IsKill=*/false, 1);
1698     assert(ANDReg && "Unexpected AND instruction emission failure.");
1699     SrcReg = ANDReg;
1700   }
1701   // Create the base instruction, then add the operands.
1702   const MCInstrDesc &II = TII.get(Opc);
1703   SrcReg = constrainOperandRegClass(II, SrcReg, II.getNumDefs());
1704   MachineInstrBuilder MIB =
1705       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II).addReg(SrcReg);
1706   addLoadStoreOperands(Addr, MIB, MachineMemOperand::MOStore, ScaleFactor, MMO);
1707
1708   return true;
1709 }
1710
1711 bool AArch64FastISel::selectStore(const Instruction *I) {
1712   MVT VT;
1713   const Value *Op0 = I->getOperand(0);
1714   // Verify we have a legal type before going any further.  Currently, we handle
1715   // simple types that will directly fit in a register (i32/f32/i64/f64) or
1716   // those that can be sign or zero-extended to a basic operation (i1/i8/i16).
1717   if (!isTypeSupported(Op0->getType(), VT, /*IsVectorAllowed=*/true) ||
1718       cast<StoreInst>(I)->isAtomic())
1719     return false;
1720
1721   // Get the value to be stored into a register. Use the zero register directly
1722   // when possible to avoid an unnecessary copy and a wasted register.
1723   unsigned SrcReg = 0;
1724   if (const auto *CI = dyn_cast<ConstantInt>(Op0)) {
1725     if (CI->isZero())
1726       SrcReg = (VT == MVT::i64) ? AArch64::XZR : AArch64::WZR;
1727   } else if (const auto *CF = dyn_cast<ConstantFP>(Op0)) {
1728     if (CF->isZero() && !CF->isNegative()) {
1729       VT = MVT::getIntegerVT(VT.getSizeInBits());
1730       SrcReg = (VT == MVT::i64) ? AArch64::XZR : AArch64::WZR;
1731     }
1732   }
1733
1734   if (!SrcReg)
1735     SrcReg = getRegForValue(Op0);
1736
1737   if (!SrcReg)
1738     return false;
1739
1740   // See if we can handle this address.
1741   Address Addr;
1742   if (!computeAddress(I->getOperand(1), Addr, I->getOperand(0)->getType()))
1743     return false;
1744
1745   if (!emitStore(VT, SrcReg, Addr, createMachineMemOperandFor(I)))
1746     return false;
1747   return true;
1748 }
1749
1750 static AArch64CC::CondCode getCompareCC(CmpInst::Predicate Pred) {
1751   switch (Pred) {
1752   case CmpInst::FCMP_ONE:
1753   case CmpInst::FCMP_UEQ:
1754   default:
1755     // AL is our "false" for now. The other two need more compares.
1756     return AArch64CC::AL;
1757   case CmpInst::ICMP_EQ:
1758   case CmpInst::FCMP_OEQ:
1759     return AArch64CC::EQ;
1760   case CmpInst::ICMP_SGT:
1761   case CmpInst::FCMP_OGT:
1762     return AArch64CC::GT;
1763   case CmpInst::ICMP_SGE:
1764   case CmpInst::FCMP_OGE:
1765     return AArch64CC::GE;
1766   case CmpInst::ICMP_UGT:
1767   case CmpInst::FCMP_UGT:
1768     return AArch64CC::HI;
1769   case CmpInst::FCMP_OLT:
1770     return AArch64CC::MI;
1771   case CmpInst::ICMP_ULE:
1772   case CmpInst::FCMP_OLE:
1773     return AArch64CC::LS;
1774   case CmpInst::FCMP_ORD:
1775     return AArch64CC::VC;
1776   case CmpInst::FCMP_UNO:
1777     return AArch64CC::VS;
1778   case CmpInst::FCMP_UGE:
1779     return AArch64CC::PL;
1780   case CmpInst::ICMP_SLT:
1781   case CmpInst::FCMP_ULT:
1782     return AArch64CC::LT;
1783   case CmpInst::ICMP_SLE:
1784   case CmpInst::FCMP_ULE:
1785     return AArch64CC::LE;
1786   case CmpInst::FCMP_UNE:
1787   case CmpInst::ICMP_NE:
1788     return AArch64CC::NE;
1789   case CmpInst::ICMP_UGE:
1790     return AArch64CC::HS;
1791   case CmpInst::ICMP_ULT:
1792     return AArch64CC::LO;
1793   }
1794 }
1795
1796 /// \brief Check if the comparison against zero and the following branch can be
1797 /// folded into a single instruction (CBZ or CBNZ).
1798 static bool canFoldZeroIntoBranch(const CmpInst *CI) {
1799   CmpInst::Predicate Predicate = CI->getPredicate();
1800   if ((Predicate != CmpInst::ICMP_EQ) && (Predicate != CmpInst::ICMP_NE))
1801     return false;
1802
1803   Type *Ty = CI->getOperand(0)->getType();
1804   if (!Ty->isIntegerTy())
1805     return false;
1806
1807   unsigned BW = cast<IntegerType>(Ty)->getBitWidth();
1808   if (BW != 1 && BW != 8 && BW != 16 && BW != 32 && BW != 64)
1809     return false;
1810
1811   if (const auto *C = dyn_cast<ConstantInt>(CI->getOperand(0)))
1812     if (C->isNullValue())
1813       return true;
1814
1815   if (const auto *C = dyn_cast<ConstantInt>(CI->getOperand(1)))
1816     if (C->isNullValue())
1817       return true;
1818
1819   return false;
1820 }
1821
1822 bool AArch64FastISel::selectBranch(const Instruction *I) {
1823   const BranchInst *BI = cast<BranchInst>(I);
1824   if (BI->isUnconditional()) {
1825     MachineBasicBlock *MSucc = FuncInfo.MBBMap[BI->getSuccessor(0)];
1826     fastEmitBranch(MSucc, BI->getDebugLoc());
1827     return true;
1828   }
1829
1830   MachineBasicBlock *TBB = FuncInfo.MBBMap[BI->getSuccessor(0)];
1831   MachineBasicBlock *FBB = FuncInfo.MBBMap[BI->getSuccessor(1)];
1832
1833   AArch64CC::CondCode CC = AArch64CC::NE;
1834   if (const CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition())) {
1835     if (CI->hasOneUse() && isValueAvailable(CI)) {
1836       // Try to optimize or fold the cmp.
1837       CmpInst::Predicate Predicate = optimizeCmpPredicate(CI);
1838       switch (Predicate) {
1839       default:
1840         break;
1841       case CmpInst::FCMP_FALSE:
1842         fastEmitBranch(FBB, DbgLoc);
1843         return true;
1844       case CmpInst::FCMP_TRUE:
1845         fastEmitBranch(TBB, DbgLoc);
1846         return true;
1847       }
1848
1849       // Try to take advantage of fallthrough opportunities.
1850       if (FuncInfo.MBB->isLayoutSuccessor(TBB)) {
1851         std::swap(TBB, FBB);
1852         Predicate = CmpInst::getInversePredicate(Predicate);
1853       }
1854
1855       // Try to optimize comparisons against zero.
1856       if (canFoldZeroIntoBranch(CI)) {
1857         const Value *LHS = CI->getOperand(0);
1858         const Value *RHS = CI->getOperand(1);
1859
1860         // Canonicalize zero values to the RHS.
1861         if (const auto *C = dyn_cast<ConstantInt>(LHS))
1862           if (C->isNullValue())
1863             std::swap(LHS, RHS);
1864
1865         static const unsigned OpcTable[2][2] = {
1866           {AArch64::CBZW,  AArch64::CBZX }, {AArch64::CBNZW, AArch64::CBNZX}
1867         };
1868         bool IsCmpNE = Predicate == CmpInst::ICMP_NE;
1869         bool Is64Bit = LHS->getType()->isIntegerTy(64);
1870         unsigned Opc = OpcTable[IsCmpNE][Is64Bit];
1871
1872         unsigned SrcReg = getRegForValue(LHS);
1873         if (!SrcReg)
1874           return false;
1875         bool SrcIsKill = hasTrivialKill(LHS);
1876
1877         // Emit the combined compare and branch instruction.
1878         BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(Opc))
1879             .addReg(SrcReg, getKillRegState(SrcIsKill))
1880             .addMBB(TBB);
1881
1882         // Obtain the branch weight and add the TrueBB to the successor list.
1883         uint32_t BranchWeight = 0;
1884         if (FuncInfo.BPI)
1885           BranchWeight = FuncInfo.BPI->getEdgeWeight(BI->getParent(),
1886                                                      TBB->getBasicBlock());
1887         FuncInfo.MBB->addSuccessor(TBB, BranchWeight);
1888
1889         fastEmitBranch(FBB, DbgLoc);
1890         return true;
1891       }
1892
1893       // Emit the cmp.
1894       if (!emitCmp(CI->getOperand(0), CI->getOperand(1), CI->isUnsigned()))
1895         return false;
1896
1897       // FCMP_UEQ and FCMP_ONE cannot be checked with a single branch
1898       // instruction.
1899       CC = getCompareCC(Predicate);
1900       AArch64CC::CondCode ExtraCC = AArch64CC::AL;
1901       switch (Predicate) {
1902       default:
1903         break;
1904       case CmpInst::FCMP_UEQ:
1905         ExtraCC = AArch64CC::EQ;
1906         CC = AArch64CC::VS;
1907         break;
1908       case CmpInst::FCMP_ONE:
1909         ExtraCC = AArch64CC::MI;
1910         CC = AArch64CC::GT;
1911         break;
1912       }
1913       assert((CC != AArch64CC::AL) && "Unexpected condition code.");
1914
1915       // Emit the extra branch for FCMP_UEQ and FCMP_ONE.
1916       if (ExtraCC != AArch64CC::AL) {
1917         BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AArch64::Bcc))
1918             .addImm(ExtraCC)
1919             .addMBB(TBB);
1920       }
1921
1922       // Emit the branch.
1923       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AArch64::Bcc))
1924           .addImm(CC)
1925           .addMBB(TBB);
1926
1927       // Obtain the branch weight and add the TrueBB to the successor list.
1928       uint32_t BranchWeight = 0;
1929       if (FuncInfo.BPI)
1930         BranchWeight = FuncInfo.BPI->getEdgeWeight(BI->getParent(),
1931                                                   TBB->getBasicBlock());
1932       FuncInfo.MBB->addSuccessor(TBB, BranchWeight);
1933
1934       fastEmitBranch(FBB, DbgLoc);
1935       return true;
1936     }
1937   } else if (TruncInst *TI = dyn_cast<TruncInst>(BI->getCondition())) {
1938     MVT SrcVT;
1939     if (TI->hasOneUse() && isValueAvailable(TI) &&
1940         isTypeSupported(TI->getOperand(0)->getType(), SrcVT)) {
1941       unsigned CondReg = getRegForValue(TI->getOperand(0));
1942       if (!CondReg)
1943         return false;
1944       bool CondIsKill = hasTrivialKill(TI->getOperand(0));
1945
1946       // Issue an extract_subreg to get the lower 32-bits.
1947       if (SrcVT == MVT::i64) {
1948         CondReg = fastEmitInst_extractsubreg(MVT::i32, CondReg, CondIsKill,
1949                                              AArch64::sub_32);
1950         CondIsKill = true;
1951       }
1952
1953       unsigned ANDReg = emitAnd_ri(MVT::i32, CondReg, CondIsKill, 1);
1954       assert(ANDReg && "Unexpected AND instruction emission failure.");
1955       emitICmp_ri(MVT::i32, ANDReg, /*IsKill=*/true, 0);
1956
1957       if (FuncInfo.MBB->isLayoutSuccessor(TBB)) {
1958         std::swap(TBB, FBB);
1959         CC = AArch64CC::EQ;
1960       }
1961       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AArch64::Bcc))
1962           .addImm(CC)
1963           .addMBB(TBB);
1964
1965       // Obtain the branch weight and add the TrueBB to the successor list.
1966       uint32_t BranchWeight = 0;
1967       if (FuncInfo.BPI)
1968         BranchWeight = FuncInfo.BPI->getEdgeWeight(BI->getParent(),
1969                                                   TBB->getBasicBlock());
1970       FuncInfo.MBB->addSuccessor(TBB, BranchWeight);
1971
1972       fastEmitBranch(FBB, DbgLoc);
1973       return true;
1974     }
1975   } else if (const auto *CI = dyn_cast<ConstantInt>(BI->getCondition())) {
1976     uint64_t Imm = CI->getZExtValue();
1977     MachineBasicBlock *Target = (Imm == 0) ? FBB : TBB;
1978     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AArch64::B))
1979         .addMBB(Target);
1980
1981     // Obtain the branch weight and add the target to the successor list.
1982     uint32_t BranchWeight = 0;
1983     if (FuncInfo.BPI)
1984       BranchWeight = FuncInfo.BPI->getEdgeWeight(BI->getParent(),
1985                                                  Target->getBasicBlock());
1986     FuncInfo.MBB->addSuccessor(Target, BranchWeight);
1987     return true;
1988   } else if (foldXALUIntrinsic(CC, I, BI->getCondition())) {
1989     // Fake request the condition, otherwise the intrinsic might be completely
1990     // optimized away.
1991     unsigned CondReg = getRegForValue(BI->getCondition());
1992     if (!CondReg)
1993       return false;
1994
1995     // Emit the branch.
1996     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AArch64::Bcc))
1997       .addImm(CC)
1998       .addMBB(TBB);
1999
2000     // Obtain the branch weight and add the TrueBB to the successor list.
2001     uint32_t BranchWeight = 0;
2002     if (FuncInfo.BPI)
2003       BranchWeight = FuncInfo.BPI->getEdgeWeight(BI->getParent(),
2004                                                  TBB->getBasicBlock());
2005     FuncInfo.MBB->addSuccessor(TBB, BranchWeight);
2006
2007     fastEmitBranch(FBB, DbgLoc);
2008     return true;
2009   }
2010
2011   unsigned CondReg = getRegForValue(BI->getCondition());
2012   if (CondReg == 0)
2013     return false;
2014   bool CondRegIsKill = hasTrivialKill(BI->getCondition());
2015
2016   // We've been divorced from our compare!  Our block was split, and
2017   // now our compare lives in a predecessor block.  We musn't
2018   // re-compare here, as the children of the compare aren't guaranteed
2019   // live across the block boundary (we *could* check for this).
2020   // Regardless, the compare has been done in the predecessor block,
2021   // and it left a value for us in a virtual register.  Ergo, we test
2022   // the one-bit value left in the virtual register.
2023   emitICmp_ri(MVT::i32, CondReg, CondRegIsKill, 0);
2024
2025   if (FuncInfo.MBB->isLayoutSuccessor(TBB)) {
2026     std::swap(TBB, FBB);
2027     CC = AArch64CC::EQ;
2028   }
2029
2030   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AArch64::Bcc))
2031       .addImm(CC)
2032       .addMBB(TBB);
2033
2034   // Obtain the branch weight and add the TrueBB to the successor list.
2035   uint32_t BranchWeight = 0;
2036   if (FuncInfo.BPI)
2037     BranchWeight = FuncInfo.BPI->getEdgeWeight(BI->getParent(),
2038                                                TBB->getBasicBlock());
2039   FuncInfo.MBB->addSuccessor(TBB, BranchWeight);
2040
2041   fastEmitBranch(FBB, DbgLoc);
2042   return true;
2043 }
2044
2045 bool AArch64FastISel::selectIndirectBr(const Instruction *I) {
2046   const IndirectBrInst *BI = cast<IndirectBrInst>(I);
2047   unsigned AddrReg = getRegForValue(BI->getOperand(0));
2048   if (AddrReg == 0)
2049     return false;
2050
2051   // Emit the indirect branch.
2052   const MCInstrDesc &II = TII.get(AArch64::BR);
2053   AddrReg = constrainOperandRegClass(II, AddrReg,  II.getNumDefs());
2054   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II).addReg(AddrReg);
2055
2056   // Make sure the CFG is up-to-date.
2057   for (unsigned i = 0, e = BI->getNumSuccessors(); i != e; ++i)
2058     FuncInfo.MBB->addSuccessor(FuncInfo.MBBMap[BI->getSuccessor(i)]);
2059
2060   return true;
2061 }
2062
2063 bool AArch64FastISel::selectCmp(const Instruction *I) {
2064   const CmpInst *CI = cast<CmpInst>(I);
2065
2066   // Try to optimize or fold the cmp.
2067   CmpInst::Predicate Predicate = optimizeCmpPredicate(CI);
2068   unsigned ResultReg = 0;
2069   switch (Predicate) {
2070   default:
2071     break;
2072   case CmpInst::FCMP_FALSE:
2073     ResultReg = createResultReg(&AArch64::GPR32RegClass);
2074     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
2075             TII.get(TargetOpcode::COPY), ResultReg)
2076         .addReg(AArch64::WZR, getKillRegState(true));
2077     break;
2078   case CmpInst::FCMP_TRUE:
2079     ResultReg = fastEmit_i(MVT::i32, MVT::i32, ISD::Constant, 1);
2080     break;
2081   }
2082
2083   if (ResultReg) {
2084     updateValueMap(I, ResultReg);
2085     return true;
2086   }
2087
2088   // Emit the cmp.
2089   if (!emitCmp(CI->getOperand(0), CI->getOperand(1), CI->isUnsigned()))
2090     return false;
2091
2092   ResultReg = createResultReg(&AArch64::GPR32RegClass);
2093
2094   // FCMP_UEQ and FCMP_ONE cannot be checked with a single instruction. These
2095   // condition codes are inverted, because they are used by CSINC.
2096   static unsigned CondCodeTable[2][2] = {
2097     { AArch64CC::NE, AArch64CC::VC },
2098     { AArch64CC::PL, AArch64CC::LE }
2099   };
2100   unsigned *CondCodes = nullptr;
2101   switch (Predicate) {
2102   default:
2103     break;
2104   case CmpInst::FCMP_UEQ:
2105     CondCodes = &CondCodeTable[0][0];
2106     break;
2107   case CmpInst::FCMP_ONE:
2108     CondCodes = &CondCodeTable[1][0];
2109     break;
2110   }
2111
2112   if (CondCodes) {
2113     unsigned TmpReg1 = createResultReg(&AArch64::GPR32RegClass);
2114     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AArch64::CSINCWr),
2115             TmpReg1)
2116         .addReg(AArch64::WZR, getKillRegState(true))
2117         .addReg(AArch64::WZR, getKillRegState(true))
2118         .addImm(CondCodes[0]);
2119     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AArch64::CSINCWr),
2120             ResultReg)
2121         .addReg(TmpReg1, getKillRegState(true))
2122         .addReg(AArch64::WZR, getKillRegState(true))
2123         .addImm(CondCodes[1]);
2124
2125     updateValueMap(I, ResultReg);
2126     return true;
2127   }
2128
2129   // Now set a register based on the comparison.
2130   AArch64CC::CondCode CC = getCompareCC(Predicate);
2131   assert((CC != AArch64CC::AL) && "Unexpected condition code.");
2132   AArch64CC::CondCode invertedCC = getInvertedCondCode(CC);
2133   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AArch64::CSINCWr),
2134           ResultReg)
2135       .addReg(AArch64::WZR, getKillRegState(true))
2136       .addReg(AArch64::WZR, getKillRegState(true))
2137       .addImm(invertedCC);
2138
2139   updateValueMap(I, ResultReg);
2140   return true;
2141 }
2142
2143 bool AArch64FastISel::selectSelect(const Instruction *I) {
2144   const SelectInst *SI = cast<SelectInst>(I);
2145
2146   EVT DestEVT = TLI.getValueType(SI->getType(), true);
2147   if (!DestEVT.isSimple())
2148     return false;
2149
2150   MVT DestVT = DestEVT.getSimpleVT();
2151   if (DestVT != MVT::i32 && DestVT != MVT::i64 && DestVT != MVT::f32 &&
2152       DestVT != MVT::f64)
2153     return false;
2154
2155   unsigned SelectOpc;
2156   const TargetRegisterClass *RC = nullptr;
2157   switch (DestVT.SimpleTy) {
2158   default: return false;
2159   case MVT::i32:
2160     SelectOpc = AArch64::CSELWr;    RC = &AArch64::GPR32RegClass; break;
2161   case MVT::i64:
2162     SelectOpc = AArch64::CSELXr;    RC = &AArch64::GPR64RegClass; break;
2163   case MVT::f32:
2164     SelectOpc = AArch64::FCSELSrrr; RC = &AArch64::FPR32RegClass; break;
2165   case MVT::f64:
2166     SelectOpc = AArch64::FCSELDrrr; RC = &AArch64::FPR64RegClass; break;
2167   }
2168
2169   const Value *Cond = SI->getCondition();
2170   bool NeedTest = true;
2171   AArch64CC::CondCode CC = AArch64CC::NE;
2172   if (foldXALUIntrinsic(CC, I, Cond))
2173     NeedTest = false;
2174
2175   unsigned CondReg = getRegForValue(Cond);
2176   if (!CondReg)
2177     return false;
2178   bool CondIsKill = hasTrivialKill(Cond);
2179
2180   if (NeedTest) {
2181     unsigned ANDReg = emitAnd_ri(MVT::i32, CondReg, CondIsKill, 1);
2182     assert(ANDReg && "Unexpected AND instruction emission failure.");
2183     emitICmp_ri(MVT::i32, ANDReg, /*IsKill=*/true, 0);
2184   }
2185
2186   unsigned TrueReg = getRegForValue(SI->getTrueValue());
2187   bool TrueIsKill = hasTrivialKill(SI->getTrueValue());
2188
2189   unsigned FalseReg = getRegForValue(SI->getFalseValue());
2190   bool FalseIsKill = hasTrivialKill(SI->getFalseValue());
2191
2192   if (!TrueReg || !FalseReg)
2193     return false;
2194
2195   unsigned ResultReg = fastEmitInst_rri(SelectOpc, RC, TrueReg, TrueIsKill,
2196                                         FalseReg, FalseIsKill, CC);
2197   updateValueMap(I, ResultReg);
2198   return true;
2199 }
2200
2201 bool AArch64FastISel::selectFPExt(const Instruction *I) {
2202   Value *V = I->getOperand(0);
2203   if (!I->getType()->isDoubleTy() || !V->getType()->isFloatTy())
2204     return false;
2205
2206   unsigned Op = getRegForValue(V);
2207   if (Op == 0)
2208     return false;
2209
2210   unsigned ResultReg = createResultReg(&AArch64::FPR64RegClass);
2211   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AArch64::FCVTDSr),
2212           ResultReg).addReg(Op);
2213   updateValueMap(I, ResultReg);
2214   return true;
2215 }
2216
2217 bool AArch64FastISel::selectFPTrunc(const Instruction *I) {
2218   Value *V = I->getOperand(0);
2219   if (!I->getType()->isFloatTy() || !V->getType()->isDoubleTy())
2220     return false;
2221
2222   unsigned Op = getRegForValue(V);
2223   if (Op == 0)
2224     return false;
2225
2226   unsigned ResultReg = createResultReg(&AArch64::FPR32RegClass);
2227   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AArch64::FCVTSDr),
2228           ResultReg).addReg(Op);
2229   updateValueMap(I, ResultReg);
2230   return true;
2231 }
2232
2233 // FPToUI and FPToSI
2234 bool AArch64FastISel::selectFPToInt(const Instruction *I, bool Signed) {
2235   MVT DestVT;
2236   if (!isTypeLegal(I->getType(), DestVT) || DestVT.isVector())
2237     return false;
2238
2239   unsigned SrcReg = getRegForValue(I->getOperand(0));
2240   if (SrcReg == 0)
2241     return false;
2242
2243   EVT SrcVT = TLI.getValueType(I->getOperand(0)->getType(), true);
2244   if (SrcVT == MVT::f128)
2245     return false;
2246
2247   unsigned Opc;
2248   if (SrcVT == MVT::f64) {
2249     if (Signed)
2250       Opc = (DestVT == MVT::i32) ? AArch64::FCVTZSUWDr : AArch64::FCVTZSUXDr;
2251     else
2252       Opc = (DestVT == MVT::i32) ? AArch64::FCVTZUUWDr : AArch64::FCVTZUUXDr;
2253   } else {
2254     if (Signed)
2255       Opc = (DestVT == MVT::i32) ? AArch64::FCVTZSUWSr : AArch64::FCVTZSUXSr;
2256     else
2257       Opc = (DestVT == MVT::i32) ? AArch64::FCVTZUUWSr : AArch64::FCVTZUUXSr;
2258   }
2259   unsigned ResultReg = createResultReg(
2260       DestVT == MVT::i32 ? &AArch64::GPR32RegClass : &AArch64::GPR64RegClass);
2261   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(Opc), ResultReg)
2262       .addReg(SrcReg);
2263   updateValueMap(I, ResultReg);
2264   return true;
2265 }
2266
2267 bool AArch64FastISel::selectIntToFP(const Instruction *I, bool Signed) {
2268   MVT DestVT;
2269   if (!isTypeLegal(I->getType(), DestVT) || DestVT.isVector())
2270     return false;
2271   assert ((DestVT == MVT::f32 || DestVT == MVT::f64) &&
2272           "Unexpected value type.");
2273
2274   unsigned SrcReg = getRegForValue(I->getOperand(0));
2275   if (!SrcReg)
2276     return false;
2277   bool SrcIsKill = hasTrivialKill(I->getOperand(0));
2278
2279   EVT SrcVT = TLI.getValueType(I->getOperand(0)->getType(), true);
2280
2281   // Handle sign-extension.
2282   if (SrcVT == MVT::i16 || SrcVT == MVT::i8 || SrcVT == MVT::i1) {
2283     SrcReg =
2284         emitIntExt(SrcVT.getSimpleVT(), SrcReg, MVT::i32, /*isZExt*/ !Signed);
2285     if (!SrcReg)
2286       return false;
2287     SrcIsKill = true;
2288   }
2289
2290   unsigned Opc;
2291   if (SrcVT == MVT::i64) {
2292     if (Signed)
2293       Opc = (DestVT == MVT::f32) ? AArch64::SCVTFUXSri : AArch64::SCVTFUXDri;
2294     else
2295       Opc = (DestVT == MVT::f32) ? AArch64::UCVTFUXSri : AArch64::UCVTFUXDri;
2296   } else {
2297     if (Signed)
2298       Opc = (DestVT == MVT::f32) ? AArch64::SCVTFUWSri : AArch64::SCVTFUWDri;
2299     else
2300       Opc = (DestVT == MVT::f32) ? AArch64::UCVTFUWSri : AArch64::UCVTFUWDri;
2301   }
2302
2303   unsigned ResultReg = fastEmitInst_r(Opc, TLI.getRegClassFor(DestVT), SrcReg,
2304                                       SrcIsKill);
2305   updateValueMap(I, ResultReg);
2306   return true;
2307 }
2308
2309 bool AArch64FastISel::fastLowerArguments() {
2310   if (!FuncInfo.CanLowerReturn)
2311     return false;
2312
2313   const Function *F = FuncInfo.Fn;
2314   if (F->isVarArg())
2315     return false;
2316
2317   CallingConv::ID CC = F->getCallingConv();
2318   if (CC != CallingConv::C)
2319     return false;
2320
2321   // Only handle simple cases of up to 8 GPR and FPR each.
2322   unsigned GPRCnt = 0;
2323   unsigned FPRCnt = 0;
2324   unsigned Idx = 0;
2325   for (auto const &Arg : F->args()) {
2326     // The first argument is at index 1.
2327     ++Idx;
2328     if (F->getAttributes().hasAttribute(Idx, Attribute::ByVal) ||
2329         F->getAttributes().hasAttribute(Idx, Attribute::InReg) ||
2330         F->getAttributes().hasAttribute(Idx, Attribute::StructRet) ||
2331         F->getAttributes().hasAttribute(Idx, Attribute::Nest))
2332       return false;
2333
2334     Type *ArgTy = Arg.getType();
2335     if (ArgTy->isStructTy() || ArgTy->isArrayTy())
2336       return false;
2337
2338     EVT ArgVT = TLI.getValueType(ArgTy);
2339     if (!ArgVT.isSimple())
2340       return false;
2341
2342     MVT VT = ArgVT.getSimpleVT().SimpleTy;
2343     if (VT.isFloatingPoint() && !Subtarget->hasFPARMv8())
2344       return false;
2345
2346     if (VT.isVector() &&
2347         (!Subtarget->hasNEON() || !Subtarget->isLittleEndian()))
2348       return false;
2349
2350     if (VT >= MVT::i1 && VT <= MVT::i64)
2351       ++GPRCnt;
2352     else if ((VT >= MVT::f16 && VT <= MVT::f64) || VT.is64BitVector() ||
2353              VT.is128BitVector())
2354       ++FPRCnt;
2355     else
2356       return false;
2357
2358     if (GPRCnt > 8 || FPRCnt > 8)
2359       return false;
2360   }
2361
2362   static const MCPhysReg Registers[6][8] = {
2363     { AArch64::W0, AArch64::W1, AArch64::W2, AArch64::W3, AArch64::W4,
2364       AArch64::W5, AArch64::W6, AArch64::W7 },
2365     { AArch64::X0, AArch64::X1, AArch64::X2, AArch64::X3, AArch64::X4,
2366       AArch64::X5, AArch64::X6, AArch64::X7 },
2367     { AArch64::H0, AArch64::H1, AArch64::H2, AArch64::H3, AArch64::H4,
2368       AArch64::H5, AArch64::H6, AArch64::H7 },
2369     { AArch64::S0, AArch64::S1, AArch64::S2, AArch64::S3, AArch64::S4,
2370       AArch64::S5, AArch64::S6, AArch64::S7 },
2371     { AArch64::D0, AArch64::D1, AArch64::D2, AArch64::D3, AArch64::D4,
2372       AArch64::D5, AArch64::D6, AArch64::D7 },
2373     { AArch64::Q0, AArch64::Q1, AArch64::Q2, AArch64::Q3, AArch64::Q4,
2374       AArch64::Q5, AArch64::Q6, AArch64::Q7 }
2375   };
2376
2377   unsigned GPRIdx = 0;
2378   unsigned FPRIdx = 0;
2379   for (auto const &Arg : F->args()) {
2380     MVT VT = TLI.getSimpleValueType(Arg.getType());
2381     unsigned SrcReg;
2382     const TargetRegisterClass *RC;
2383     if (VT >= MVT::i1 && VT <= MVT::i32) {
2384       SrcReg = Registers[0][GPRIdx++];
2385       RC = &AArch64::GPR32RegClass;
2386       VT = MVT::i32;
2387     } else if (VT == MVT::i64) {
2388       SrcReg = Registers[1][GPRIdx++];
2389       RC = &AArch64::GPR64RegClass;
2390     } else if (VT == MVT::f16) {
2391       SrcReg = Registers[2][FPRIdx++];
2392       RC = &AArch64::FPR16RegClass;
2393     } else if (VT ==  MVT::f32) {
2394       SrcReg = Registers[3][FPRIdx++];
2395       RC = &AArch64::FPR32RegClass;
2396     } else if ((VT == MVT::f64) || VT.is64BitVector()) {
2397       SrcReg = Registers[4][FPRIdx++];
2398       RC = &AArch64::FPR64RegClass;
2399     } else if (VT.is128BitVector()) {
2400       SrcReg = Registers[5][FPRIdx++];
2401       RC = &AArch64::FPR128RegClass;
2402     } else
2403       llvm_unreachable("Unexpected value type.");
2404
2405     unsigned DstReg = FuncInfo.MF->addLiveIn(SrcReg, RC);
2406     // FIXME: Unfortunately it's necessary to emit a copy from the livein copy.
2407     // Without this, EmitLiveInCopies may eliminate the livein if its only
2408     // use is a bitcast (which isn't turned into an instruction).
2409     unsigned ResultReg = createResultReg(RC);
2410     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
2411             TII.get(TargetOpcode::COPY), ResultReg)
2412         .addReg(DstReg, getKillRegState(true));
2413     updateValueMap(&Arg, ResultReg);
2414   }
2415   return true;
2416 }
2417
2418 bool AArch64FastISel::processCallArgs(CallLoweringInfo &CLI,
2419                                       SmallVectorImpl<MVT> &OutVTs,
2420                                       unsigned &NumBytes) {
2421   CallingConv::ID CC = CLI.CallConv;
2422   SmallVector<CCValAssign, 16> ArgLocs;
2423   CCState CCInfo(CC, false, *FuncInfo.MF, ArgLocs, *Context);
2424   CCInfo.AnalyzeCallOperands(OutVTs, CLI.OutFlags, CCAssignFnForCall(CC));
2425
2426   // Get a count of how many bytes are to be pushed on the stack.
2427   NumBytes = CCInfo.getNextStackOffset();
2428
2429   // Issue CALLSEQ_START
2430   unsigned AdjStackDown = TII.getCallFrameSetupOpcode();
2431   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AdjStackDown))
2432     .addImm(NumBytes);
2433
2434   // Process the args.
2435   for (unsigned i = 0, e = ArgLocs.size(); i != e; ++i) {
2436     CCValAssign &VA = ArgLocs[i];
2437     const Value *ArgVal = CLI.OutVals[VA.getValNo()];
2438     MVT ArgVT = OutVTs[VA.getValNo()];
2439
2440     unsigned ArgReg = getRegForValue(ArgVal);
2441     if (!ArgReg)
2442       return false;
2443
2444     // Handle arg promotion: SExt, ZExt, AExt.
2445     switch (VA.getLocInfo()) {
2446     case CCValAssign::Full:
2447       break;
2448     case CCValAssign::SExt: {
2449       MVT DestVT = VA.getLocVT();
2450       MVT SrcVT = ArgVT;
2451       ArgReg = emitIntExt(SrcVT, ArgReg, DestVT, /*isZExt=*/false);
2452       if (!ArgReg)
2453         return false;
2454       break;
2455     }
2456     case CCValAssign::AExt:
2457     // Intentional fall-through.
2458     case CCValAssign::ZExt: {
2459       MVT DestVT = VA.getLocVT();
2460       MVT SrcVT = ArgVT;
2461       ArgReg = emitIntExt(SrcVT, ArgReg, DestVT, /*isZExt=*/true);
2462       if (!ArgReg)
2463         return false;
2464       break;
2465     }
2466     default:
2467       llvm_unreachable("Unknown arg promotion!");
2468     }
2469
2470     // Now copy/store arg to correct locations.
2471     if (VA.isRegLoc() && !VA.needsCustom()) {
2472       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
2473               TII.get(TargetOpcode::COPY), VA.getLocReg()).addReg(ArgReg);
2474       CLI.OutRegs.push_back(VA.getLocReg());
2475     } else if (VA.needsCustom()) {
2476       // FIXME: Handle custom args.
2477       return false;
2478     } else {
2479       assert(VA.isMemLoc() && "Assuming store on stack.");
2480
2481       // Don't emit stores for undef values.
2482       if (isa<UndefValue>(ArgVal))
2483         continue;
2484
2485       // Need to store on the stack.
2486       unsigned ArgSize = (ArgVT.getSizeInBits() + 7) / 8;
2487
2488       unsigned BEAlign = 0;
2489       if (ArgSize < 8 && !Subtarget->isLittleEndian())
2490         BEAlign = 8 - ArgSize;
2491
2492       Address Addr;
2493       Addr.setKind(Address::RegBase);
2494       Addr.setReg(AArch64::SP);
2495       Addr.setOffset(VA.getLocMemOffset() + BEAlign);
2496
2497       unsigned Alignment = DL.getABITypeAlignment(ArgVal->getType());
2498       MachineMemOperand *MMO = FuncInfo.MF->getMachineMemOperand(
2499         MachinePointerInfo::getStack(Addr.getOffset()),
2500         MachineMemOperand::MOStore, ArgVT.getStoreSize(), Alignment);
2501
2502       if (!emitStore(ArgVT, ArgReg, Addr, MMO))
2503         return false;
2504     }
2505   }
2506   return true;
2507 }
2508
2509 bool AArch64FastISel::finishCall(CallLoweringInfo &CLI, MVT RetVT,
2510                                  unsigned NumBytes) {
2511   CallingConv::ID CC = CLI.CallConv;
2512
2513   // Issue CALLSEQ_END
2514   unsigned AdjStackUp = TII.getCallFrameDestroyOpcode();
2515   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AdjStackUp))
2516     .addImm(NumBytes).addImm(0);
2517
2518   // Now the return value.
2519   if (RetVT != MVT::isVoid) {
2520     SmallVector<CCValAssign, 16> RVLocs;
2521     CCState CCInfo(CC, false, *FuncInfo.MF, RVLocs, *Context);
2522     CCInfo.AnalyzeCallResult(RetVT, CCAssignFnForCall(CC));
2523
2524     // Only handle a single return value.
2525     if (RVLocs.size() != 1)
2526       return false;
2527
2528     // Copy all of the result registers out of their specified physreg.
2529     MVT CopyVT = RVLocs[0].getValVT();
2530     unsigned ResultReg = createResultReg(TLI.getRegClassFor(CopyVT));
2531     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
2532             TII.get(TargetOpcode::COPY), ResultReg)
2533         .addReg(RVLocs[0].getLocReg());
2534     CLI.InRegs.push_back(RVLocs[0].getLocReg());
2535
2536     CLI.ResultReg = ResultReg;
2537     CLI.NumResultRegs = 1;
2538   }
2539
2540   return true;
2541 }
2542
2543 bool AArch64FastISel::fastLowerCall(CallLoweringInfo &CLI) {
2544   CallingConv::ID CC  = CLI.CallConv;
2545   bool IsTailCall     = CLI.IsTailCall;
2546   bool IsVarArg       = CLI.IsVarArg;
2547   const Value *Callee = CLI.Callee;
2548   const char *SymName = CLI.SymName;
2549
2550   if (!Callee && !SymName)
2551     return false;
2552
2553   // Allow SelectionDAG isel to handle tail calls.
2554   if (IsTailCall)
2555     return false;
2556
2557   CodeModel::Model CM = TM.getCodeModel();
2558   // Only support the small and large code model.
2559   if (CM != CodeModel::Small && CM != CodeModel::Large)
2560     return false;
2561
2562   // FIXME: Add large code model support for ELF.
2563   if (CM == CodeModel::Large && !Subtarget->isTargetMachO())
2564     return false;
2565
2566   // Let SDISel handle vararg functions.
2567   if (IsVarArg)
2568     return false;
2569
2570   // FIXME: Only handle *simple* calls for now.
2571   MVT RetVT;
2572   if (CLI.RetTy->isVoidTy())
2573     RetVT = MVT::isVoid;
2574   else if (!isTypeLegal(CLI.RetTy, RetVT))
2575     return false;
2576
2577   for (auto Flag : CLI.OutFlags)
2578     if (Flag.isInReg() || Flag.isSRet() || Flag.isNest() || Flag.isByVal())
2579       return false;
2580
2581   // Set up the argument vectors.
2582   SmallVector<MVT, 16> OutVTs;
2583   OutVTs.reserve(CLI.OutVals.size());
2584
2585   for (auto *Val : CLI.OutVals) {
2586     MVT VT;
2587     if (!isTypeLegal(Val->getType(), VT) &&
2588         !(VT == MVT::i1 || VT == MVT::i8 || VT == MVT::i16))
2589       return false;
2590
2591     // We don't handle vector parameters yet.
2592     if (VT.isVector() || VT.getSizeInBits() > 64)
2593       return false;
2594
2595     OutVTs.push_back(VT);
2596   }
2597
2598   Address Addr;
2599   if (Callee && !computeCallAddress(Callee, Addr))
2600     return false;
2601
2602   // Handle the arguments now that we've gotten them.
2603   unsigned NumBytes;
2604   if (!processCallArgs(CLI, OutVTs, NumBytes))
2605     return false;
2606
2607   // Issue the call.
2608   MachineInstrBuilder MIB;
2609   if (CM == CodeModel::Small) {
2610     const MCInstrDesc &II = TII.get(Addr.getReg() ? AArch64::BLR : AArch64::BL);
2611     MIB = BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II);
2612     if (SymName)
2613       MIB.addExternalSymbol(SymName, 0);
2614     else if (Addr.getGlobalValue())
2615       MIB.addGlobalAddress(Addr.getGlobalValue(), 0, 0);
2616     else if (Addr.getReg()) {
2617       unsigned Reg = constrainOperandRegClass(II, Addr.getReg(), 0);
2618       MIB.addReg(Reg);
2619     } else
2620       return false;
2621   } else {
2622     unsigned CallReg = 0;
2623     if (SymName) {
2624       unsigned ADRPReg = createResultReg(&AArch64::GPR64commonRegClass);
2625       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AArch64::ADRP),
2626               ADRPReg)
2627         .addExternalSymbol(SymName, AArch64II::MO_GOT | AArch64II::MO_PAGE);
2628
2629       CallReg = createResultReg(&AArch64::GPR64RegClass);
2630       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AArch64::LDRXui),
2631               CallReg)
2632         .addReg(ADRPReg)
2633         .addExternalSymbol(SymName, AArch64II::MO_GOT | AArch64II::MO_PAGEOFF |
2634                            AArch64II::MO_NC);
2635     } else if (Addr.getGlobalValue())
2636       CallReg = materializeGV(Addr.getGlobalValue());
2637     else if (Addr.getReg())
2638       CallReg = Addr.getReg();
2639
2640     if (!CallReg)
2641       return false;
2642
2643     const MCInstrDesc &II = TII.get(AArch64::BLR);
2644     CallReg = constrainOperandRegClass(II, CallReg, 0);
2645     MIB = BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II).addReg(CallReg);
2646   }
2647
2648   // Add implicit physical register uses to the call.
2649   for (auto Reg : CLI.OutRegs)
2650     MIB.addReg(Reg, RegState::Implicit);
2651
2652   // Add a register mask with the call-preserved registers.
2653   // Proper defs for return values will be added by setPhysRegsDeadExcept().
2654   MIB.addRegMask(TRI.getCallPreservedMask(CC));
2655
2656   CLI.Call = MIB;
2657
2658   // Finish off the call including any return values.
2659   return finishCall(CLI, RetVT, NumBytes);
2660 }
2661
2662 bool AArch64FastISel::isMemCpySmall(uint64_t Len, unsigned Alignment) {
2663   if (Alignment)
2664     return Len / Alignment <= 4;
2665   else
2666     return Len < 32;
2667 }
2668
2669 bool AArch64FastISel::tryEmitSmallMemCpy(Address Dest, Address Src,
2670                                          uint64_t Len, unsigned Alignment) {
2671   // Make sure we don't bloat code by inlining very large memcpy's.
2672   if (!isMemCpySmall(Len, Alignment))
2673     return false;
2674
2675   int64_t UnscaledOffset = 0;
2676   Address OrigDest = Dest;
2677   Address OrigSrc = Src;
2678
2679   while (Len) {
2680     MVT VT;
2681     if (!Alignment || Alignment >= 8) {
2682       if (Len >= 8)
2683         VT = MVT::i64;
2684       else if (Len >= 4)
2685         VT = MVT::i32;
2686       else if (Len >= 2)
2687         VT = MVT::i16;
2688       else {
2689         VT = MVT::i8;
2690       }
2691     } else {
2692       // Bound based on alignment.
2693       if (Len >= 4 && Alignment == 4)
2694         VT = MVT::i32;
2695       else if (Len >= 2 && Alignment == 2)
2696         VT = MVT::i16;
2697       else {
2698         VT = MVT::i8;
2699       }
2700     }
2701
2702     bool RV;
2703     unsigned ResultReg;
2704     RV = emitLoad(VT, ResultReg, Src);
2705     if (!RV)
2706       return false;
2707
2708     RV = emitStore(VT, ResultReg, Dest);
2709     if (!RV)
2710       return false;
2711
2712     int64_t Size = VT.getSizeInBits() / 8;
2713     Len -= Size;
2714     UnscaledOffset += Size;
2715
2716     // We need to recompute the unscaled offset for each iteration.
2717     Dest.setOffset(OrigDest.getOffset() + UnscaledOffset);
2718     Src.setOffset(OrigSrc.getOffset() + UnscaledOffset);
2719   }
2720
2721   return true;
2722 }
2723
2724 /// \brief Check if it is possible to fold the condition from the XALU intrinsic
2725 /// into the user. The condition code will only be updated on success.
2726 bool AArch64FastISel::foldXALUIntrinsic(AArch64CC::CondCode &CC,
2727                                         const Instruction *I,
2728                                         const Value *Cond) {
2729   if (!isa<ExtractValueInst>(Cond))
2730     return false;
2731
2732   const auto *EV = cast<ExtractValueInst>(Cond);
2733   if (!isa<IntrinsicInst>(EV->getAggregateOperand()))
2734     return false;
2735
2736   const auto *II = cast<IntrinsicInst>(EV->getAggregateOperand());
2737   MVT RetVT;
2738   const Function *Callee = II->getCalledFunction();
2739   Type *RetTy =
2740   cast<StructType>(Callee->getReturnType())->getTypeAtIndex(0U);
2741   if (!isTypeLegal(RetTy, RetVT))
2742     return false;
2743
2744   if (RetVT != MVT::i32 && RetVT != MVT::i64)
2745     return false;
2746
2747   AArch64CC::CondCode TmpCC;
2748   switch (II->getIntrinsicID()) {
2749     default: return false;
2750     case Intrinsic::sadd_with_overflow:
2751     case Intrinsic::ssub_with_overflow: TmpCC = AArch64CC::VS; break;
2752     case Intrinsic::uadd_with_overflow: TmpCC = AArch64CC::HS; break;
2753     case Intrinsic::usub_with_overflow: TmpCC = AArch64CC::LO; break;
2754     case Intrinsic::smul_with_overflow:
2755     case Intrinsic::umul_with_overflow: TmpCC = AArch64CC::NE; break;
2756   }
2757
2758   // Check if both instructions are in the same basic block.
2759   if (!isValueAvailable(II))
2760     return false;
2761
2762   // Make sure nothing is in the way
2763   BasicBlock::const_iterator Start = I;
2764   BasicBlock::const_iterator End = II;
2765   for (auto Itr = std::prev(Start); Itr != End; --Itr) {
2766     // We only expect extractvalue instructions between the intrinsic and the
2767     // instruction to be selected.
2768     if (!isa<ExtractValueInst>(Itr))
2769       return false;
2770
2771     // Check that the extractvalue operand comes from the intrinsic.
2772     const auto *EVI = cast<ExtractValueInst>(Itr);
2773     if (EVI->getAggregateOperand() != II)
2774       return false;
2775   }
2776
2777   CC = TmpCC;
2778   return true;
2779 }
2780
2781 bool AArch64FastISel::fastLowerIntrinsicCall(const IntrinsicInst *II) {
2782   // FIXME: Handle more intrinsics.
2783   switch (II->getIntrinsicID()) {
2784   default: return false;
2785   case Intrinsic::frameaddress: {
2786     MachineFrameInfo *MFI = FuncInfo.MF->getFrameInfo();
2787     MFI->setFrameAddressIsTaken(true);
2788
2789     const AArch64RegisterInfo *RegInfo =
2790         static_cast<const AArch64RegisterInfo *>(
2791             TM.getSubtargetImpl()->getRegisterInfo());
2792     unsigned FramePtr = RegInfo->getFrameRegister(*(FuncInfo.MF));
2793     unsigned SrcReg = MRI.createVirtualRegister(&AArch64::GPR64RegClass);
2794     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
2795             TII.get(TargetOpcode::COPY), SrcReg).addReg(FramePtr);
2796     // Recursively load frame address
2797     // ldr x0, [fp]
2798     // ldr x0, [x0]
2799     // ldr x0, [x0]
2800     // ...
2801     unsigned DestReg;
2802     unsigned Depth = cast<ConstantInt>(II->getOperand(0))->getZExtValue();
2803     while (Depth--) {
2804       DestReg = fastEmitInst_ri(AArch64::LDRXui, &AArch64::GPR64RegClass,
2805                                 SrcReg, /*IsKill=*/true, 0);
2806       assert(DestReg && "Unexpected LDR instruction emission failure.");
2807       SrcReg = DestReg;
2808     }
2809
2810     updateValueMap(II, SrcReg);
2811     return true;
2812   }
2813   case Intrinsic::memcpy:
2814   case Intrinsic::memmove: {
2815     const auto *MTI = cast<MemTransferInst>(II);
2816     // Don't handle volatile.
2817     if (MTI->isVolatile())
2818       return false;
2819
2820     // Disable inlining for memmove before calls to ComputeAddress.  Otherwise,
2821     // we would emit dead code because we don't currently handle memmoves.
2822     bool IsMemCpy = (II->getIntrinsicID() == Intrinsic::memcpy);
2823     if (isa<ConstantInt>(MTI->getLength()) && IsMemCpy) {
2824       // Small memcpy's are common enough that we want to do them without a call
2825       // if possible.
2826       uint64_t Len = cast<ConstantInt>(MTI->getLength())->getZExtValue();
2827       unsigned Alignment = MTI->getAlignment();
2828       if (isMemCpySmall(Len, Alignment)) {
2829         Address Dest, Src;
2830         if (!computeAddress(MTI->getRawDest(), Dest) ||
2831             !computeAddress(MTI->getRawSource(), Src))
2832           return false;
2833         if (tryEmitSmallMemCpy(Dest, Src, Len, Alignment))
2834           return true;
2835       }
2836     }
2837
2838     if (!MTI->getLength()->getType()->isIntegerTy(64))
2839       return false;
2840
2841     if (MTI->getSourceAddressSpace() > 255 || MTI->getDestAddressSpace() > 255)
2842       // Fast instruction selection doesn't support the special
2843       // address spaces.
2844       return false;
2845
2846     const char *IntrMemName = isa<MemCpyInst>(II) ? "memcpy" : "memmove";
2847     return lowerCallTo(II, IntrMemName, II->getNumArgOperands() - 2);
2848   }
2849   case Intrinsic::memset: {
2850     const MemSetInst *MSI = cast<MemSetInst>(II);
2851     // Don't handle volatile.
2852     if (MSI->isVolatile())
2853       return false;
2854
2855     if (!MSI->getLength()->getType()->isIntegerTy(64))
2856       return false;
2857
2858     if (MSI->getDestAddressSpace() > 255)
2859       // Fast instruction selection doesn't support the special
2860       // address spaces.
2861       return false;
2862
2863     return lowerCallTo(II, "memset", II->getNumArgOperands() - 2);
2864   }
2865   case Intrinsic::sin:
2866   case Intrinsic::cos:
2867   case Intrinsic::pow: {
2868     MVT RetVT;
2869     if (!isTypeLegal(II->getType(), RetVT))
2870       return false;
2871
2872     if (RetVT != MVT::f32 && RetVT != MVT::f64)
2873       return false;
2874
2875     static const RTLIB::Libcall LibCallTable[3][2] = {
2876       { RTLIB::SIN_F32, RTLIB::SIN_F64 },
2877       { RTLIB::COS_F32, RTLIB::COS_F64 },
2878       { RTLIB::POW_F32, RTLIB::POW_F64 }
2879     };
2880     RTLIB::Libcall LC;
2881     bool Is64Bit = RetVT == MVT::f64;
2882     switch (II->getIntrinsicID()) {
2883     default:
2884       llvm_unreachable("Unexpected intrinsic.");
2885     case Intrinsic::sin:
2886       LC = LibCallTable[0][Is64Bit];
2887       break;
2888     case Intrinsic::cos:
2889       LC = LibCallTable[1][Is64Bit];
2890       break;
2891     case Intrinsic::pow:
2892       LC = LibCallTable[2][Is64Bit];
2893       break;
2894     }
2895
2896     ArgListTy Args;
2897     Args.reserve(II->getNumArgOperands());
2898
2899     // Populate the argument list.
2900     for (auto &Arg : II->arg_operands()) {
2901       ArgListEntry Entry;
2902       Entry.Val = Arg;
2903       Entry.Ty = Arg->getType();
2904       Args.push_back(Entry);
2905     }
2906
2907     CallLoweringInfo CLI;
2908     CLI.setCallee(TLI.getLibcallCallingConv(LC), II->getType(),
2909                   TLI.getLibcallName(LC), std::move(Args));
2910     if (!lowerCallTo(CLI))
2911       return false;
2912     updateValueMap(II, CLI.ResultReg);
2913     return true;
2914   }
2915   case Intrinsic::trap: {
2916     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AArch64::BRK))
2917         .addImm(1);
2918     return true;
2919   }
2920   case Intrinsic::sqrt: {
2921     Type *RetTy = II->getCalledFunction()->getReturnType();
2922
2923     MVT VT;
2924     if (!isTypeLegal(RetTy, VT))
2925       return false;
2926
2927     unsigned Op0Reg = getRegForValue(II->getOperand(0));
2928     if (!Op0Reg)
2929       return false;
2930     bool Op0IsKill = hasTrivialKill(II->getOperand(0));
2931
2932     unsigned ResultReg = fastEmit_r(VT, VT, ISD::FSQRT, Op0Reg, Op0IsKill);
2933     if (!ResultReg)
2934       return false;
2935
2936     updateValueMap(II, ResultReg);
2937     return true;
2938   }
2939   case Intrinsic::sadd_with_overflow:
2940   case Intrinsic::uadd_with_overflow:
2941   case Intrinsic::ssub_with_overflow:
2942   case Intrinsic::usub_with_overflow:
2943   case Intrinsic::smul_with_overflow:
2944   case Intrinsic::umul_with_overflow: {
2945     // This implements the basic lowering of the xalu with overflow intrinsics.
2946     const Function *Callee = II->getCalledFunction();
2947     auto *Ty = cast<StructType>(Callee->getReturnType());
2948     Type *RetTy = Ty->getTypeAtIndex(0U);
2949
2950     MVT VT;
2951     if (!isTypeLegal(RetTy, VT))
2952       return false;
2953
2954     if (VT != MVT::i32 && VT != MVT::i64)
2955       return false;
2956
2957     const Value *LHS = II->getArgOperand(0);
2958     const Value *RHS = II->getArgOperand(1);
2959     // Canonicalize immediate to the RHS.
2960     if (isa<ConstantInt>(LHS) && !isa<ConstantInt>(RHS) &&
2961         isCommutativeIntrinsic(II))
2962       std::swap(LHS, RHS);
2963
2964     unsigned ResultReg1 = 0, ResultReg2 = 0, MulReg = 0;
2965     AArch64CC::CondCode CC = AArch64CC::Invalid;
2966     switch (II->getIntrinsicID()) {
2967     default: llvm_unreachable("Unexpected intrinsic!");
2968     case Intrinsic::sadd_with_overflow:
2969       ResultReg1 = emitAdd(VT, LHS, RHS, /*SetFlags=*/true);
2970       CC = AArch64CC::VS;
2971       break;
2972     case Intrinsic::uadd_with_overflow:
2973       ResultReg1 = emitAdd(VT, LHS, RHS, /*SetFlags=*/true);
2974       CC = AArch64CC::HS;
2975       break;
2976     case Intrinsic::ssub_with_overflow:
2977       ResultReg1 = emitSub(VT, LHS, RHS, /*SetFlags=*/true);
2978       CC = AArch64CC::VS;
2979       break;
2980     case Intrinsic::usub_with_overflow:
2981       ResultReg1 = emitSub(VT, LHS, RHS, /*SetFlags=*/true);
2982       CC = AArch64CC::LO;
2983       break;
2984     case Intrinsic::smul_with_overflow: {
2985       CC = AArch64CC::NE;
2986       unsigned LHSReg = getRegForValue(LHS);
2987       if (!LHSReg)
2988         return false;
2989       bool LHSIsKill = hasTrivialKill(LHS);
2990
2991       unsigned RHSReg = getRegForValue(RHS);
2992       if (!RHSReg)
2993         return false;
2994       bool RHSIsKill = hasTrivialKill(RHS);
2995
2996       if (VT == MVT::i32) {
2997         MulReg = emitSMULL_rr(MVT::i64, LHSReg, LHSIsKill, RHSReg, RHSIsKill);
2998         unsigned ShiftReg = emitLSR_ri(MVT::i64, MVT::i64, MulReg,
2999                                        /*IsKill=*/false, 32);
3000         MulReg = fastEmitInst_extractsubreg(VT, MulReg, /*IsKill=*/true,
3001                                             AArch64::sub_32);
3002         ShiftReg = fastEmitInst_extractsubreg(VT, ShiftReg, /*IsKill=*/true,
3003                                               AArch64::sub_32);
3004         emitSubs_rs(VT, ShiftReg, /*IsKill=*/true, MulReg, /*IsKill=*/false,
3005                     AArch64_AM::ASR, 31, /*WantResult=*/false);
3006       } else {
3007         assert(VT == MVT::i64 && "Unexpected value type.");
3008         MulReg = emitMul_rr(VT, LHSReg, LHSIsKill, RHSReg, RHSIsKill);
3009         unsigned SMULHReg = fastEmit_rr(VT, VT, ISD::MULHS, LHSReg, LHSIsKill,
3010                                         RHSReg, RHSIsKill);
3011         emitSubs_rs(VT, SMULHReg, /*IsKill=*/true, MulReg, /*IsKill=*/false,
3012                     AArch64_AM::ASR, 63, /*WantResult=*/false);
3013       }
3014       break;
3015     }
3016     case Intrinsic::umul_with_overflow: {
3017       CC = AArch64CC::NE;
3018       unsigned LHSReg = getRegForValue(LHS);
3019       if (!LHSReg)
3020         return false;
3021       bool LHSIsKill = hasTrivialKill(LHS);
3022
3023       unsigned RHSReg = getRegForValue(RHS);
3024       if (!RHSReg)
3025         return false;
3026       bool RHSIsKill = hasTrivialKill(RHS);
3027
3028       if (VT == MVT::i32) {
3029         MulReg = emitUMULL_rr(MVT::i64, LHSReg, LHSIsKill, RHSReg, RHSIsKill);
3030         emitSubs_rs(MVT::i64, AArch64::XZR, /*IsKill=*/true, MulReg,
3031                     /*IsKill=*/false, AArch64_AM::LSR, 32,
3032                     /*WantResult=*/false);
3033         MulReg = fastEmitInst_extractsubreg(VT, MulReg, /*IsKill=*/true,
3034                                             AArch64::sub_32);
3035       } else {
3036         assert(VT == MVT::i64 && "Unexpected value type.");
3037         MulReg = emitMul_rr(VT, LHSReg, LHSIsKill, RHSReg, RHSIsKill);
3038         unsigned UMULHReg = fastEmit_rr(VT, VT, ISD::MULHU, LHSReg, LHSIsKill,
3039                                         RHSReg, RHSIsKill);
3040         emitSubs_rr(VT, AArch64::XZR, /*IsKill=*/true, UMULHReg,
3041                     /*IsKill=*/false, /*WantResult=*/false);
3042       }
3043       break;
3044     }
3045     }
3046
3047     if (MulReg) {
3048       ResultReg1 = createResultReg(TLI.getRegClassFor(VT));
3049       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
3050               TII.get(TargetOpcode::COPY), ResultReg1).addReg(MulReg);
3051     }
3052
3053     ResultReg2 = fastEmitInst_rri(AArch64::CSINCWr, &AArch64::GPR32RegClass,
3054                                   AArch64::WZR, /*IsKill=*/true, AArch64::WZR,
3055                                   /*IsKill=*/true, getInvertedCondCode(CC));
3056     assert((ResultReg1 + 1) == ResultReg2 &&
3057            "Nonconsecutive result registers.");
3058     updateValueMap(II, ResultReg1, 2);
3059     return true;
3060   }
3061   }
3062   return false;
3063 }
3064
3065 bool AArch64FastISel::selectRet(const Instruction *I) {
3066   const ReturnInst *Ret = cast<ReturnInst>(I);
3067   const Function &F = *I->getParent()->getParent();
3068
3069   if (!FuncInfo.CanLowerReturn)
3070     return false;
3071
3072   if (F.isVarArg())
3073     return false;
3074
3075   // Build a list of return value registers.
3076   SmallVector<unsigned, 4> RetRegs;
3077
3078   if (Ret->getNumOperands() > 0) {
3079     CallingConv::ID CC = F.getCallingConv();
3080     SmallVector<ISD::OutputArg, 4> Outs;
3081     GetReturnInfo(F.getReturnType(), F.getAttributes(), Outs, TLI);
3082
3083     // Analyze operands of the call, assigning locations to each operand.
3084     SmallVector<CCValAssign, 16> ValLocs;
3085     CCState CCInfo(CC, F.isVarArg(), *FuncInfo.MF, ValLocs, I->getContext());
3086     CCAssignFn *RetCC = CC == CallingConv::WebKit_JS ? RetCC_AArch64_WebKit_JS
3087                                                      : RetCC_AArch64_AAPCS;
3088     CCInfo.AnalyzeReturn(Outs, RetCC);
3089
3090     // Only handle a single return value for now.
3091     if (ValLocs.size() != 1)
3092       return false;
3093
3094     CCValAssign &VA = ValLocs[0];
3095     const Value *RV = Ret->getOperand(0);
3096
3097     // Don't bother handling odd stuff for now.
3098     if ((VA.getLocInfo() != CCValAssign::Full) &&
3099         (VA.getLocInfo() != CCValAssign::BCvt))
3100       return false;
3101
3102     // Only handle register returns for now.
3103     if (!VA.isRegLoc())
3104       return false;
3105
3106     unsigned Reg = getRegForValue(RV);
3107     if (Reg == 0)
3108       return false;
3109
3110     unsigned SrcReg = Reg + VA.getValNo();
3111     unsigned DestReg = VA.getLocReg();
3112     // Avoid a cross-class copy. This is very unlikely.
3113     if (!MRI.getRegClass(SrcReg)->contains(DestReg))
3114       return false;
3115
3116     EVT RVEVT = TLI.getValueType(RV->getType());
3117     if (!RVEVT.isSimple())
3118       return false;
3119
3120     // Vectors (of > 1 lane) in big endian need tricky handling.
3121     if (RVEVT.isVector() && RVEVT.getVectorNumElements() > 1 &&
3122         !Subtarget->isLittleEndian())
3123       return false;
3124
3125     MVT RVVT = RVEVT.getSimpleVT();
3126     if (RVVT == MVT::f128)
3127       return false;
3128
3129     MVT DestVT = VA.getValVT();
3130     // Special handling for extended integers.
3131     if (RVVT != DestVT) {
3132       if (RVVT != MVT::i1 && RVVT != MVT::i8 && RVVT != MVT::i16)
3133         return false;
3134
3135       if (!Outs[0].Flags.isZExt() && !Outs[0].Flags.isSExt())
3136         return false;
3137
3138       bool IsZExt = Outs[0].Flags.isZExt();
3139       SrcReg = emitIntExt(RVVT, SrcReg, DestVT, IsZExt);
3140       if (SrcReg == 0)
3141         return false;
3142     }
3143
3144     // Make the copy.
3145     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
3146             TII.get(TargetOpcode::COPY), DestReg).addReg(SrcReg);
3147
3148     // Add register to return instruction.
3149     RetRegs.push_back(VA.getLocReg());
3150   }
3151
3152   MachineInstrBuilder MIB = BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
3153                                     TII.get(AArch64::RET_ReallyLR));
3154   for (unsigned i = 0, e = RetRegs.size(); i != e; ++i)
3155     MIB.addReg(RetRegs[i], RegState::Implicit);
3156   return true;
3157 }
3158
3159 bool AArch64FastISel::selectTrunc(const Instruction *I) {
3160   Type *DestTy = I->getType();
3161   Value *Op = I->getOperand(0);
3162   Type *SrcTy = Op->getType();
3163
3164   EVT SrcEVT = TLI.getValueType(SrcTy, true);
3165   EVT DestEVT = TLI.getValueType(DestTy, true);
3166   if (!SrcEVT.isSimple())
3167     return false;
3168   if (!DestEVT.isSimple())
3169     return false;
3170
3171   MVT SrcVT = SrcEVT.getSimpleVT();
3172   MVT DestVT = DestEVT.getSimpleVT();
3173
3174   if (SrcVT != MVT::i64 && SrcVT != MVT::i32 && SrcVT != MVT::i16 &&
3175       SrcVT != MVT::i8)
3176     return false;
3177   if (DestVT != MVT::i32 && DestVT != MVT::i16 && DestVT != MVT::i8 &&
3178       DestVT != MVT::i1)
3179     return false;
3180
3181   unsigned SrcReg = getRegForValue(Op);
3182   if (!SrcReg)
3183     return false;
3184   bool SrcIsKill = hasTrivialKill(Op);
3185
3186   // If we're truncating from i64 to a smaller non-legal type then generate an
3187   // AND. Otherwise, we know the high bits are undefined and a truncate only
3188   // generate a COPY. We cannot mark the source register also as result
3189   // register, because this can incorrectly transfer the kill flag onto the
3190   // source register.
3191   unsigned ResultReg;
3192   if (SrcVT == MVT::i64) {
3193     uint64_t Mask = 0;
3194     switch (DestVT.SimpleTy) {
3195     default:
3196       // Trunc i64 to i32 is handled by the target-independent fast-isel.
3197       return false;
3198     case MVT::i1:
3199       Mask = 0x1;
3200       break;
3201     case MVT::i8:
3202       Mask = 0xff;
3203       break;
3204     case MVT::i16:
3205       Mask = 0xffff;
3206       break;
3207     }
3208     // Issue an extract_subreg to get the lower 32-bits.
3209     unsigned Reg32 = fastEmitInst_extractsubreg(MVT::i32, SrcReg, SrcIsKill,
3210                                                 AArch64::sub_32);
3211     // Create the AND instruction which performs the actual truncation.
3212     ResultReg = emitAnd_ri(MVT::i32, Reg32, /*IsKill=*/true, Mask);
3213     assert(ResultReg && "Unexpected AND instruction emission failure.");
3214   } else {
3215     ResultReg = createResultReg(&AArch64::GPR32RegClass);
3216     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
3217             TII.get(TargetOpcode::COPY), ResultReg)
3218         .addReg(SrcReg, getKillRegState(SrcIsKill));
3219   }
3220
3221   updateValueMap(I, ResultReg);
3222   return true;
3223 }
3224
3225 unsigned AArch64FastISel::emiti1Ext(unsigned SrcReg, MVT DestVT, bool IsZExt) {
3226   assert((DestVT == MVT::i8 || DestVT == MVT::i16 || DestVT == MVT::i32 ||
3227           DestVT == MVT::i64) &&
3228          "Unexpected value type.");
3229   // Handle i8 and i16 as i32.
3230   if (DestVT == MVT::i8 || DestVT == MVT::i16)
3231     DestVT = MVT::i32;
3232
3233   if (IsZExt) {
3234     unsigned ResultReg = emitAnd_ri(MVT::i32, SrcReg, /*TODO:IsKill=*/false, 1);
3235     assert(ResultReg && "Unexpected AND instruction emission failure.");
3236     if (DestVT == MVT::i64) {
3237       // We're ZExt i1 to i64.  The ANDWri Wd, Ws, #1 implicitly clears the
3238       // upper 32 bits.  Emit a SUBREG_TO_REG to extend from Wd to Xd.
3239       unsigned Reg64 = MRI.createVirtualRegister(&AArch64::GPR64RegClass);
3240       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
3241               TII.get(AArch64::SUBREG_TO_REG), Reg64)
3242           .addImm(0)
3243           .addReg(ResultReg)
3244           .addImm(AArch64::sub_32);
3245       ResultReg = Reg64;
3246     }
3247     return ResultReg;
3248   } else {
3249     if (DestVT == MVT::i64) {
3250       // FIXME: We're SExt i1 to i64.
3251       return 0;
3252     }
3253     return fastEmitInst_rii(AArch64::SBFMWri, &AArch64::GPR32RegClass, SrcReg,
3254                             /*TODO:IsKill=*/false, 0, 0);
3255   }
3256 }
3257
3258 unsigned AArch64FastISel::emitMul_rr(MVT RetVT, unsigned Op0, bool Op0IsKill,
3259                                       unsigned Op1, bool Op1IsKill) {
3260   unsigned Opc, ZReg;
3261   switch (RetVT.SimpleTy) {
3262   default: return 0;
3263   case MVT::i8:
3264   case MVT::i16:
3265   case MVT::i32:
3266     RetVT = MVT::i32;
3267     Opc = AArch64::MADDWrrr; ZReg = AArch64::WZR; break;
3268   case MVT::i64:
3269     Opc = AArch64::MADDXrrr; ZReg = AArch64::XZR; break;
3270   }
3271
3272   const TargetRegisterClass *RC =
3273       (RetVT == MVT::i64) ? &AArch64::GPR64RegClass : &AArch64::GPR32RegClass;
3274   return fastEmitInst_rrr(Opc, RC, Op0, Op0IsKill, Op1, Op1IsKill,
3275                           /*IsKill=*/ZReg, true);
3276 }
3277
3278 unsigned AArch64FastISel::emitSMULL_rr(MVT RetVT, unsigned Op0, bool Op0IsKill,
3279                                         unsigned Op1, bool Op1IsKill) {
3280   if (RetVT != MVT::i64)
3281     return 0;
3282
3283   return fastEmitInst_rrr(AArch64::SMADDLrrr, &AArch64::GPR64RegClass,
3284                           Op0, Op0IsKill, Op1, Op1IsKill,
3285                           AArch64::XZR, /*IsKill=*/true);
3286 }
3287
3288 unsigned AArch64FastISel::emitUMULL_rr(MVT RetVT, unsigned Op0, bool Op0IsKill,
3289                                         unsigned Op1, bool Op1IsKill) {
3290   if (RetVT != MVT::i64)
3291     return 0;
3292
3293   return fastEmitInst_rrr(AArch64::UMADDLrrr, &AArch64::GPR64RegClass,
3294                           Op0, Op0IsKill, Op1, Op1IsKill,
3295                           AArch64::XZR, /*IsKill=*/true);
3296 }
3297
3298 unsigned AArch64FastISel::emitLSL_rr(MVT RetVT, unsigned Op0Reg, bool Op0IsKill,
3299                                      unsigned Op1Reg, bool Op1IsKill) {
3300   unsigned Opc = 0;
3301   bool NeedTrunc = false;
3302   uint64_t Mask = 0;
3303   switch (RetVT.SimpleTy) {
3304   default: return 0;
3305   case MVT::i8:  Opc = AArch64::LSLVWr; NeedTrunc = true; Mask = 0xff;   break;
3306   case MVT::i16: Opc = AArch64::LSLVWr; NeedTrunc = true; Mask = 0xffff; break;
3307   case MVT::i32: Opc = AArch64::LSLVWr;                                  break;
3308   case MVT::i64: Opc = AArch64::LSLVXr;                                  break;
3309   }
3310
3311   const TargetRegisterClass *RC =
3312       (RetVT == MVT::i64) ? &AArch64::GPR64RegClass : &AArch64::GPR32RegClass;
3313   if (NeedTrunc) {
3314     Op1Reg = emitAnd_ri(MVT::i32, Op1Reg, Op1IsKill, Mask);
3315     Op1IsKill = true;
3316   }
3317   unsigned ResultReg = fastEmitInst_rr(Opc, RC, Op0Reg, Op0IsKill, Op1Reg,
3318                                        Op1IsKill);
3319   if (NeedTrunc)
3320     ResultReg = emitAnd_ri(MVT::i32, ResultReg, /*IsKill=*/true, Mask);
3321   return ResultReg;
3322 }
3323
3324 unsigned AArch64FastISel::emitLSL_ri(MVT RetVT, MVT SrcVT, unsigned Op0,
3325                                      bool Op0IsKill, uint64_t Shift,
3326                                      bool IsZext) {
3327   assert(RetVT.SimpleTy >= SrcVT.SimpleTy &&
3328          "Unexpected source/return type pair.");
3329   assert((SrcVT == MVT::i8 || SrcVT == MVT::i16 || SrcVT == MVT::i32 ||
3330           SrcVT == MVT::i64) && "Unexpected source value type.");
3331   assert((RetVT == MVT::i8 || RetVT == MVT::i16 || RetVT == MVT::i32 ||
3332           RetVT == MVT::i64) && "Unexpected return value type.");
3333
3334   bool Is64Bit = (RetVT == MVT::i64);
3335   unsigned RegSize = Is64Bit ? 64 : 32;
3336   unsigned DstBits = RetVT.getSizeInBits();
3337   unsigned SrcBits = SrcVT.getSizeInBits();
3338
3339   // Don't deal with undefined shifts.
3340   if (Shift >= DstBits)
3341     return 0;
3342
3343   // For immediate shifts we can fold the zero-/sign-extension into the shift.
3344   // {S|U}BFM Wd, Wn, #r, #s
3345   // Wd<32+s-r,32-r> = Wn<s:0> when r > s
3346
3347   // %1 = {s|z}ext i8 {0b1010_1010|0b0101_0101} to i16
3348   // %2 = shl i16 %1, 4
3349   // Wd<32+7-28,32-28> = Wn<7:0> <- clamp s to 7
3350   // 0b1111_1111_1111_1111__1111_1010_1010_0000 sext
3351   // 0b0000_0000_0000_0000__0000_0101_0101_0000 sext | zext
3352   // 0b0000_0000_0000_0000__0000_1010_1010_0000 zext
3353
3354   // %1 = {s|z}ext i8 {0b1010_1010|0b0101_0101} to i16
3355   // %2 = shl i16 %1, 8
3356   // Wd<32+7-24,32-24> = Wn<7:0>
3357   // 0b1111_1111_1111_1111__1010_1010_0000_0000 sext
3358   // 0b0000_0000_0000_0000__0101_0101_0000_0000 sext | zext
3359   // 0b0000_0000_0000_0000__1010_1010_0000_0000 zext
3360
3361   // %1 = {s|z}ext i8 {0b1010_1010|0b0101_0101} to i16
3362   // %2 = shl i16 %1, 12
3363   // Wd<32+3-20,32-20> = Wn<3:0>
3364   // 0b1111_1111_1111_1111__1010_0000_0000_0000 sext
3365   // 0b0000_0000_0000_0000__0101_0000_0000_0000 sext | zext
3366   // 0b0000_0000_0000_0000__1010_0000_0000_0000 zext
3367
3368   unsigned ImmR = RegSize - Shift;
3369   // Limit the width to the length of the source type.
3370   unsigned ImmS = std::min<unsigned>(SrcBits - 1, DstBits - 1 - Shift);
3371   static const unsigned OpcTable[2][2] = {
3372     {AArch64::SBFMWri, AArch64::SBFMXri},
3373     {AArch64::UBFMWri, AArch64::UBFMXri}
3374   };
3375   unsigned Opc = OpcTable[IsZext][Is64Bit];
3376   const TargetRegisterClass *RC =
3377       Is64Bit ? &AArch64::GPR64RegClass : &AArch64::GPR32RegClass;
3378   if (SrcVT.SimpleTy <= MVT::i32 && RetVT == MVT::i64) {
3379     unsigned TmpReg = MRI.createVirtualRegister(RC);
3380     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
3381             TII.get(AArch64::SUBREG_TO_REG), TmpReg)
3382         .addImm(0)
3383         .addReg(Op0, getKillRegState(Op0IsKill))
3384         .addImm(AArch64::sub_32);
3385     Op0 = TmpReg;
3386     Op0IsKill = true;
3387   }
3388   return fastEmitInst_rii(Opc, RC, Op0, Op0IsKill, ImmR, ImmS);
3389 }
3390
3391 unsigned AArch64FastISel::emitLSR_rr(MVT RetVT, unsigned Op0Reg, bool Op0IsKill,
3392                                      unsigned Op1Reg, bool Op1IsKill) {
3393   unsigned Opc = 0;
3394   bool NeedTrunc = false;
3395   uint64_t Mask = 0;
3396   switch (RetVT.SimpleTy) {
3397   default: return 0;
3398   case MVT::i8:  Opc = AArch64::LSRVWr; NeedTrunc = true; Mask = 0xff;   break;
3399   case MVT::i16: Opc = AArch64::LSRVWr; NeedTrunc = true; Mask = 0xffff; break;
3400   case MVT::i32: Opc = AArch64::LSRVWr; break;
3401   case MVT::i64: Opc = AArch64::LSRVXr; break;
3402   }
3403
3404   const TargetRegisterClass *RC =
3405       (RetVT == MVT::i64) ? &AArch64::GPR64RegClass : &AArch64::GPR32RegClass;
3406   if (NeedTrunc) {
3407     Op0Reg = emitAnd_ri(MVT::i32, Op0Reg, Op0IsKill, Mask);
3408     Op1Reg = emitAnd_ri(MVT::i32, Op1Reg, Op1IsKill, Mask);
3409     Op0IsKill = Op1IsKill = true;
3410   }
3411   unsigned ResultReg = fastEmitInst_rr(Opc, RC, Op0Reg, Op0IsKill, Op1Reg,
3412                                        Op1IsKill);
3413   if (NeedTrunc)
3414     ResultReg = emitAnd_ri(MVT::i32, ResultReg, /*IsKill=*/true, Mask);
3415   return ResultReg;
3416 }
3417
3418 unsigned AArch64FastISel::emitLSR_ri(MVT RetVT, MVT SrcVT, unsigned Op0,
3419                                      bool Op0IsKill, uint64_t Shift,
3420                                      bool IsZExt) {
3421   assert(RetVT.SimpleTy >= SrcVT.SimpleTy &&
3422          "Unexpected source/return type pair.");
3423   assert((SrcVT == MVT::i8 || SrcVT == MVT::i16 || SrcVT == MVT::i32 ||
3424           SrcVT == MVT::i64) && "Unexpected source value type.");
3425   assert((RetVT == MVT::i8 || RetVT == MVT::i16 || RetVT == MVT::i32 ||
3426           RetVT == MVT::i64) && "Unexpected return value type.");
3427
3428   bool Is64Bit = (RetVT == MVT::i64);
3429   unsigned RegSize = Is64Bit ? 64 : 32;
3430   unsigned DstBits = RetVT.getSizeInBits();
3431   unsigned SrcBits = SrcVT.getSizeInBits();
3432
3433   // Don't deal with undefined shifts.
3434   if (Shift >= DstBits)
3435     return 0;
3436
3437   // For immediate shifts we can fold the zero-/sign-extension into the shift.
3438   // {S|U}BFM Wd, Wn, #r, #s
3439   // Wd<s-r:0> = Wn<s:r> when r <= s
3440
3441   // %1 = {s|z}ext i8 {0b1010_1010|0b0101_0101} to i16
3442   // %2 = lshr i16 %1, 4
3443   // Wd<7-4:0> = Wn<7:4>
3444   // 0b0000_0000_0000_0000__0000_1111_1111_1010 sext
3445   // 0b0000_0000_0000_0000__0000_0000_0000_0101 sext | zext
3446   // 0b0000_0000_0000_0000__0000_0000_0000_1010 zext
3447
3448   // %1 = {s|z}ext i8 {0b1010_1010|0b0101_0101} to i16
3449   // %2 = lshr i16 %1, 8
3450   // Wd<7-7,0> = Wn<7:7>
3451   // 0b0000_0000_0000_0000__0000_0000_1111_1111 sext
3452   // 0b0000_0000_0000_0000__0000_0000_0000_0000 sext
3453   // 0b0000_0000_0000_0000__0000_0000_0000_0000 zext
3454
3455   // %1 = {s|z}ext i8 {0b1010_1010|0b0101_0101} to i16
3456   // %2 = lshr i16 %1, 12
3457   // Wd<7-7,0> = Wn<7:7> <- clamp r to 7
3458   // 0b0000_0000_0000_0000__0000_0000_0000_1111 sext
3459   // 0b0000_0000_0000_0000__0000_0000_0000_0000 sext
3460   // 0b0000_0000_0000_0000__0000_0000_0000_0000 zext
3461
3462   if (Shift >= SrcBits && IsZExt)
3463     return materializeInt(ConstantInt::get(*Context, APInt(RegSize, 0)), RetVT);
3464
3465   // It is not possible to fold a sign-extend into the LShr instruction. In this
3466   // case emit a sign-extend.
3467   if (!IsZExt) {
3468     Op0 = emitIntExt(SrcVT, Op0, RetVT, IsZExt);
3469     if (!Op0)
3470       return 0;
3471     Op0IsKill = true;
3472     SrcVT = RetVT;
3473     SrcBits = SrcVT.getSizeInBits();
3474     IsZExt = true;
3475   }
3476
3477   unsigned ImmR = std::min<unsigned>(SrcBits - 1, Shift);
3478   unsigned ImmS = SrcBits - 1;
3479   static const unsigned OpcTable[2][2] = {
3480     {AArch64::SBFMWri, AArch64::SBFMXri},
3481     {AArch64::UBFMWri, AArch64::UBFMXri}
3482   };
3483   unsigned Opc = OpcTable[IsZExt][Is64Bit];
3484   const TargetRegisterClass *RC =
3485       Is64Bit ? &AArch64::GPR64RegClass : &AArch64::GPR32RegClass;
3486   if (SrcVT.SimpleTy <= MVT::i32 && RetVT == MVT::i64) {
3487     unsigned TmpReg = MRI.createVirtualRegister(RC);
3488     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
3489             TII.get(AArch64::SUBREG_TO_REG), TmpReg)
3490         .addImm(0)
3491         .addReg(Op0, getKillRegState(Op0IsKill))
3492         .addImm(AArch64::sub_32);
3493     Op0 = TmpReg;
3494     Op0IsKill = true;
3495   }
3496   return fastEmitInst_rii(Opc, RC, Op0, Op0IsKill, ImmR, ImmS);
3497 }
3498
3499 unsigned AArch64FastISel::emitASR_rr(MVT RetVT, unsigned Op0Reg, bool Op0IsKill,
3500                                      unsigned Op1Reg, bool Op1IsKill) {
3501   unsigned Opc = 0;
3502   bool NeedTrunc = false;
3503   uint64_t Mask = 0;
3504   switch (RetVT.SimpleTy) {
3505   default: return 0;
3506   case MVT::i8:  Opc = AArch64::ASRVWr; NeedTrunc = true; Mask = 0xff;   break;
3507   case MVT::i16: Opc = AArch64::ASRVWr; NeedTrunc = true; Mask = 0xffff; break;
3508   case MVT::i32: Opc = AArch64::ASRVWr;                                  break;
3509   case MVT::i64: Opc = AArch64::ASRVXr;                                  break;
3510   }
3511
3512   const TargetRegisterClass *RC =
3513       (RetVT == MVT::i64) ? &AArch64::GPR64RegClass : &AArch64::GPR32RegClass;
3514   if (NeedTrunc) {
3515     Op0Reg = emitIntExt(RetVT, Op0Reg, MVT::i32, /*IsZExt=*/false);
3516     Op1Reg = emitAnd_ri(MVT::i32, Op1Reg, Op1IsKill, Mask);
3517     Op0IsKill = Op1IsKill = true;
3518   }
3519   unsigned ResultReg = fastEmitInst_rr(Opc, RC, Op0Reg, Op0IsKill, Op1Reg,
3520                                        Op1IsKill);
3521   if (NeedTrunc)
3522     ResultReg = emitAnd_ri(MVT::i32, ResultReg, /*IsKill=*/true, Mask);
3523   return ResultReg;
3524 }
3525
3526 unsigned AArch64FastISel::emitASR_ri(MVT RetVT, MVT SrcVT, unsigned Op0,
3527                                      bool Op0IsKill, uint64_t Shift,
3528                                      bool IsZExt) {
3529   assert(RetVT.SimpleTy >= SrcVT.SimpleTy &&
3530          "Unexpected source/return type pair.");
3531   assert((SrcVT == MVT::i8 || SrcVT == MVT::i16 || SrcVT == MVT::i32 ||
3532           SrcVT == MVT::i64) && "Unexpected source value type.");
3533   assert((RetVT == MVT::i8 || RetVT == MVT::i16 || RetVT == MVT::i32 ||
3534           RetVT == MVT::i64) && "Unexpected return value type.");
3535
3536   bool Is64Bit = (RetVT == MVT::i64);
3537   unsigned RegSize = Is64Bit ? 64 : 32;
3538   unsigned DstBits = RetVT.getSizeInBits();
3539   unsigned SrcBits = SrcVT.getSizeInBits();
3540
3541   // Don't deal with undefined shifts.
3542   if (Shift >= DstBits)
3543     return 0;
3544
3545   // For immediate shifts we can fold the zero-/sign-extension into the shift.
3546   // {S|U}BFM Wd, Wn, #r, #s
3547   // Wd<s-r:0> = Wn<s:r> when r <= s
3548
3549   // %1 = {s|z}ext i8 {0b1010_1010|0b0101_0101} to i16
3550   // %2 = ashr i16 %1, 4
3551   // Wd<7-4:0> = Wn<7:4>
3552   // 0b1111_1111_1111_1111__1111_1111_1111_1010 sext
3553   // 0b0000_0000_0000_0000__0000_0000_0000_0101 sext | zext
3554   // 0b0000_0000_0000_0000__0000_0000_0000_1010 zext
3555
3556   // %1 = {s|z}ext i8 {0b1010_1010|0b0101_0101} to i16
3557   // %2 = ashr i16 %1, 8
3558   // Wd<7-7,0> = Wn<7:7>
3559   // 0b1111_1111_1111_1111__1111_1111_1111_1111 sext
3560   // 0b0000_0000_0000_0000__0000_0000_0000_0000 sext
3561   // 0b0000_0000_0000_0000__0000_0000_0000_0000 zext
3562
3563   // %1 = {s|z}ext i8 {0b1010_1010|0b0101_0101} to i16
3564   // %2 = ashr i16 %1, 12
3565   // Wd<7-7,0> = Wn<7:7> <- clamp r to 7
3566   // 0b1111_1111_1111_1111__1111_1111_1111_1111 sext
3567   // 0b0000_0000_0000_0000__0000_0000_0000_0000 sext
3568   // 0b0000_0000_0000_0000__0000_0000_0000_0000 zext
3569
3570   if (Shift >= SrcBits && IsZExt)
3571     return materializeInt(ConstantInt::get(*Context, APInt(RegSize, 0)), RetVT);
3572
3573   unsigned ImmR = std::min<unsigned>(SrcBits - 1, Shift);
3574   unsigned ImmS = SrcBits - 1;
3575   static const unsigned OpcTable[2][2] = {
3576     {AArch64::SBFMWri, AArch64::SBFMXri},
3577     {AArch64::UBFMWri, AArch64::UBFMXri}
3578   };
3579   unsigned Opc = OpcTable[IsZExt][Is64Bit];
3580   const TargetRegisterClass *RC =
3581       Is64Bit ? &AArch64::GPR64RegClass : &AArch64::GPR32RegClass;
3582   if (SrcVT.SimpleTy <= MVT::i32 && RetVT == MVT::i64) {
3583     unsigned TmpReg = MRI.createVirtualRegister(RC);
3584     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
3585             TII.get(AArch64::SUBREG_TO_REG), TmpReg)
3586         .addImm(0)
3587         .addReg(Op0, getKillRegState(Op0IsKill))
3588         .addImm(AArch64::sub_32);
3589     Op0 = TmpReg;
3590     Op0IsKill = true;
3591   }
3592   return fastEmitInst_rii(Opc, RC, Op0, Op0IsKill, ImmR, ImmS);
3593 }
3594
3595 unsigned AArch64FastISel::emitIntExt(MVT SrcVT, unsigned SrcReg, MVT DestVT,
3596                                      bool IsZExt) {
3597   assert(DestVT != MVT::i1 && "ZeroExt/SignExt an i1?");
3598
3599   // FastISel does not have plumbing to deal with extensions where the SrcVT or
3600   // DestVT are odd things, so test to make sure that they are both types we can
3601   // handle (i1/i8/i16/i32 for SrcVT and i8/i16/i32/i64 for DestVT), otherwise
3602   // bail out to SelectionDAG.
3603   if (((DestVT != MVT::i8) && (DestVT != MVT::i16) &&
3604        (DestVT != MVT::i32) && (DestVT != MVT::i64)) ||
3605       ((SrcVT !=  MVT::i1) && (SrcVT !=  MVT::i8) &&
3606        (SrcVT !=  MVT::i16) && (SrcVT !=  MVT::i32)))
3607     return 0;
3608
3609   unsigned Opc;
3610   unsigned Imm = 0;
3611
3612   switch (SrcVT.SimpleTy) {
3613   default:
3614     return 0;
3615   case MVT::i1:
3616     return emiti1Ext(SrcReg, DestVT, IsZExt);
3617   case MVT::i8:
3618     if (DestVT == MVT::i64)
3619       Opc = IsZExt ? AArch64::UBFMXri : AArch64::SBFMXri;
3620     else
3621       Opc = IsZExt ? AArch64::UBFMWri : AArch64::SBFMWri;
3622     Imm = 7;
3623     break;
3624   case MVT::i16:
3625     if (DestVT == MVT::i64)
3626       Opc = IsZExt ? AArch64::UBFMXri : AArch64::SBFMXri;
3627     else
3628       Opc = IsZExt ? AArch64::UBFMWri : AArch64::SBFMWri;
3629     Imm = 15;
3630     break;
3631   case MVT::i32:
3632     assert(DestVT == MVT::i64 && "IntExt i32 to i32?!?");
3633     Opc = IsZExt ? AArch64::UBFMXri : AArch64::SBFMXri;
3634     Imm = 31;
3635     break;
3636   }
3637
3638   // Handle i8 and i16 as i32.
3639   if (DestVT == MVT::i8 || DestVT == MVT::i16)
3640     DestVT = MVT::i32;
3641   else if (DestVT == MVT::i64) {
3642     unsigned Src64 = MRI.createVirtualRegister(&AArch64::GPR64RegClass);
3643     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
3644             TII.get(AArch64::SUBREG_TO_REG), Src64)
3645         .addImm(0)
3646         .addReg(SrcReg)
3647         .addImm(AArch64::sub_32);
3648     SrcReg = Src64;
3649   }
3650
3651   const TargetRegisterClass *RC =
3652       (DestVT == MVT::i64) ? &AArch64::GPR64RegClass : &AArch64::GPR32RegClass;
3653   return fastEmitInst_rii(Opc, RC, SrcReg, /*TODO:IsKill=*/false, 0, Imm);
3654 }
3655
3656 bool AArch64FastISel::selectIntExt(const Instruction *I) {
3657   // On ARM, in general, integer casts don't involve legal types; this code
3658   // handles promotable integers.  The high bits for a type smaller than
3659   // the register size are assumed to be undefined.
3660   Type *DestTy = I->getType();
3661   Value *Src = I->getOperand(0);
3662   Type *SrcTy = Src->getType();
3663
3664   unsigned SrcReg = getRegForValue(Src);
3665   if (!SrcReg)
3666     return false;
3667
3668   EVT SrcEVT = TLI.getValueType(SrcTy, true);
3669   EVT DestEVT = TLI.getValueType(DestTy, true);
3670   if (!SrcEVT.isSimple())
3671     return false;
3672   if (!DestEVT.isSimple())
3673     return false;
3674
3675   MVT SrcVT = SrcEVT.getSimpleVT();
3676   MVT DestVT = DestEVT.getSimpleVT();
3677   unsigned ResultReg = 0;
3678
3679   bool IsZExt = isa<ZExtInst>(I);
3680   // Check if it is an argument and if it is already zero/sign-extended.
3681   if (const auto *Arg = dyn_cast<Argument>(Src)) {
3682     if ((IsZExt && Arg->hasZExtAttr()) || (!IsZExt && Arg->hasSExtAttr())) {
3683       if (DestVT == MVT::i64) {
3684         ResultReg = createResultReg(TLI.getRegClassFor(DestVT));
3685         BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
3686                 TII.get(AArch64::SUBREG_TO_REG), ResultReg)
3687           .addImm(0)
3688           .addReg(SrcReg)
3689           .addImm(AArch64::sub_32);
3690       } else
3691         ResultReg = SrcReg;
3692     }
3693   }
3694
3695   if (!ResultReg)
3696     ResultReg = emitIntExt(SrcVT, SrcReg, DestVT, IsZExt);
3697
3698   if (!ResultReg)
3699     return false;
3700
3701   updateValueMap(I, ResultReg);
3702   return true;
3703 }
3704
3705 bool AArch64FastISel::selectRem(const Instruction *I, unsigned ISDOpcode) {
3706   EVT DestEVT = TLI.getValueType(I->getType(), true);
3707   if (!DestEVT.isSimple())
3708     return false;
3709
3710   MVT DestVT = DestEVT.getSimpleVT();
3711   if (DestVT != MVT::i64 && DestVT != MVT::i32)
3712     return false;
3713
3714   unsigned DivOpc;
3715   bool Is64bit = (DestVT == MVT::i64);
3716   switch (ISDOpcode) {
3717   default:
3718     return false;
3719   case ISD::SREM:
3720     DivOpc = Is64bit ? AArch64::SDIVXr : AArch64::SDIVWr;
3721     break;
3722   case ISD::UREM:
3723     DivOpc = Is64bit ? AArch64::UDIVXr : AArch64::UDIVWr;
3724     break;
3725   }
3726   unsigned MSubOpc = Is64bit ? AArch64::MSUBXrrr : AArch64::MSUBWrrr;
3727   unsigned Src0Reg = getRegForValue(I->getOperand(0));
3728   if (!Src0Reg)
3729     return false;
3730   bool Src0IsKill = hasTrivialKill(I->getOperand(0));
3731
3732   unsigned Src1Reg = getRegForValue(I->getOperand(1));
3733   if (!Src1Reg)
3734     return false;
3735   bool Src1IsKill = hasTrivialKill(I->getOperand(1));
3736
3737   const TargetRegisterClass *RC =
3738       (DestVT == MVT::i64) ? &AArch64::GPR64RegClass : &AArch64::GPR32RegClass;
3739   unsigned QuotReg = fastEmitInst_rr(DivOpc, RC, Src0Reg, /*IsKill=*/false,
3740                                      Src1Reg, /*IsKill=*/false);
3741   assert(QuotReg && "Unexpected DIV instruction emission failure.");
3742   // The remainder is computed as numerator - (quotient * denominator) using the
3743   // MSUB instruction.
3744   unsigned ResultReg = fastEmitInst_rrr(MSubOpc, RC, QuotReg, /*IsKill=*/true,
3745                                         Src1Reg, Src1IsKill, Src0Reg,
3746                                         Src0IsKill);
3747   updateValueMap(I, ResultReg);
3748   return true;
3749 }
3750
3751 bool AArch64FastISel::selectMul(const Instruction *I) {
3752   MVT VT;
3753   if (!isTypeSupported(I->getType(), VT, /*IsVectorAllowed=*/true))
3754     return false;
3755
3756   if (VT.isVector())
3757     return selectBinaryOp(I, ISD::MUL);
3758
3759   const Value *Src0 = I->getOperand(0);
3760   const Value *Src1 = I->getOperand(1);
3761   if (const auto *C = dyn_cast<ConstantInt>(Src0))
3762     if (C->getValue().isPowerOf2())
3763       std::swap(Src0, Src1);
3764
3765   // Try to simplify to a shift instruction.
3766   if (const auto *C = dyn_cast<ConstantInt>(Src1))
3767     if (C->getValue().isPowerOf2()) {
3768       uint64_t ShiftVal = C->getValue().logBase2();
3769       MVT SrcVT = VT;
3770       bool IsZExt = true;
3771       if (const auto *ZExt = dyn_cast<ZExtInst>(Src0)) {
3772         MVT VT;
3773         if (isValueAvailable(ZExt) && isTypeSupported(ZExt->getSrcTy(), VT)) {
3774           SrcVT = VT;
3775           IsZExt = true;
3776           Src0 = ZExt->getOperand(0);
3777         }
3778       } else if (const auto *SExt = dyn_cast<SExtInst>(Src0)) {
3779         MVT VT;
3780         if (isValueAvailable(SExt) && isTypeSupported(SExt->getSrcTy(), VT)) {
3781           SrcVT = VT;
3782           IsZExt = false;
3783           Src0 = SExt->getOperand(0);
3784         }
3785       }
3786
3787       unsigned Src0Reg = getRegForValue(Src0);
3788       if (!Src0Reg)
3789         return false;
3790       bool Src0IsKill = hasTrivialKill(Src0);
3791
3792       unsigned ResultReg =
3793           emitLSL_ri(VT, SrcVT, Src0Reg, Src0IsKill, ShiftVal, IsZExt);
3794
3795       if (ResultReg) {
3796         updateValueMap(I, ResultReg);
3797         return true;
3798       }
3799     }
3800
3801   unsigned Src0Reg = getRegForValue(I->getOperand(0));
3802   if (!Src0Reg)
3803     return false;
3804   bool Src0IsKill = hasTrivialKill(I->getOperand(0));
3805
3806   unsigned Src1Reg = getRegForValue(I->getOperand(1));
3807   if (!Src1Reg)
3808     return false;
3809   bool Src1IsKill = hasTrivialKill(I->getOperand(1));
3810
3811   unsigned ResultReg = emitMul_rr(VT, Src0Reg, Src0IsKill, Src1Reg, Src1IsKill);
3812
3813   if (!ResultReg)
3814     return false;
3815
3816   updateValueMap(I, ResultReg);
3817   return true;
3818 }
3819
3820 bool AArch64FastISel::selectShift(const Instruction *I) {
3821   MVT RetVT;
3822   if (!isTypeSupported(I->getType(), RetVT, /*IsVectorAllowed=*/true))
3823     return false;
3824
3825   if (RetVT.isVector())
3826     return selectOperator(I, I->getOpcode());
3827
3828   if (const auto *C = dyn_cast<ConstantInt>(I->getOperand(1))) {
3829     unsigned ResultReg = 0;
3830     uint64_t ShiftVal = C->getZExtValue();
3831     MVT SrcVT = RetVT;
3832     bool IsZExt = (I->getOpcode() == Instruction::AShr) ? false : true;
3833     const Value *Op0 = I->getOperand(0);
3834     if (const auto *ZExt = dyn_cast<ZExtInst>(Op0)) {
3835       MVT TmpVT;
3836       if (isValueAvailable(ZExt) && isTypeSupported(ZExt->getSrcTy(), TmpVT)) {
3837         SrcVT = TmpVT;
3838         IsZExt = true;
3839         Op0 = ZExt->getOperand(0);
3840       }
3841     } else if (const auto *SExt = dyn_cast<SExtInst>(Op0)) {
3842       MVT TmpVT;
3843       if (isValueAvailable(SExt) && isTypeSupported(SExt->getSrcTy(), TmpVT)) {
3844         SrcVT = TmpVT;
3845         IsZExt = false;
3846         Op0 = SExt->getOperand(0);
3847       }
3848     }
3849
3850     unsigned Op0Reg = getRegForValue(Op0);
3851     if (!Op0Reg)
3852       return false;
3853     bool Op0IsKill = hasTrivialKill(Op0);
3854
3855     switch (I->getOpcode()) {
3856     default: llvm_unreachable("Unexpected instruction.");
3857     case Instruction::Shl:
3858       ResultReg = emitLSL_ri(RetVT, SrcVT, Op0Reg, Op0IsKill, ShiftVal, IsZExt);
3859       break;
3860     case Instruction::AShr:
3861       ResultReg = emitASR_ri(RetVT, SrcVT, Op0Reg, Op0IsKill, ShiftVal, IsZExt);
3862       break;
3863     case Instruction::LShr:
3864       ResultReg = emitLSR_ri(RetVT, SrcVT, Op0Reg, Op0IsKill, ShiftVal, IsZExt);
3865       break;
3866     }
3867     if (!ResultReg)
3868       return false;
3869
3870     updateValueMap(I, ResultReg);
3871     return true;
3872   }
3873
3874   unsigned Op0Reg = getRegForValue(I->getOperand(0));
3875   if (!Op0Reg)
3876     return false;
3877   bool Op0IsKill = hasTrivialKill(I->getOperand(0));
3878
3879   unsigned Op1Reg = getRegForValue(I->getOperand(1));
3880   if (!Op1Reg)
3881     return false;
3882   bool Op1IsKill = hasTrivialKill(I->getOperand(1));
3883
3884   unsigned ResultReg = 0;
3885   switch (I->getOpcode()) {
3886   default: llvm_unreachable("Unexpected instruction.");
3887   case Instruction::Shl:
3888     ResultReg = emitLSL_rr(RetVT, Op0Reg, Op0IsKill, Op1Reg, Op1IsKill);
3889     break;
3890   case Instruction::AShr:
3891     ResultReg = emitASR_rr(RetVT, Op0Reg, Op0IsKill, Op1Reg, Op1IsKill);
3892     break;
3893   case Instruction::LShr:
3894     ResultReg = emitLSR_rr(RetVT, Op0Reg, Op0IsKill, Op1Reg, Op1IsKill);
3895     break;
3896   }
3897
3898   if (!ResultReg)
3899     return false;
3900
3901   updateValueMap(I, ResultReg);
3902   return true;
3903 }
3904
3905 bool AArch64FastISel::selectBitCast(const Instruction *I) {
3906   MVT RetVT, SrcVT;
3907
3908   if (!isTypeLegal(I->getOperand(0)->getType(), SrcVT))
3909     return false;
3910   if (!isTypeLegal(I->getType(), RetVT))
3911     return false;
3912
3913   unsigned Opc;
3914   if (RetVT == MVT::f32 && SrcVT == MVT::i32)
3915     Opc = AArch64::FMOVWSr;
3916   else if (RetVT == MVT::f64 && SrcVT == MVT::i64)
3917     Opc = AArch64::FMOVXDr;
3918   else if (RetVT == MVT::i32 && SrcVT == MVT::f32)
3919     Opc = AArch64::FMOVSWr;
3920   else if (RetVT == MVT::i64 && SrcVT == MVT::f64)
3921     Opc = AArch64::FMOVDXr;
3922   else
3923     return false;
3924
3925   const TargetRegisterClass *RC = nullptr;
3926   switch (RetVT.SimpleTy) {
3927   default: llvm_unreachable("Unexpected value type.");
3928   case MVT::i32: RC = &AArch64::GPR32RegClass; break;
3929   case MVT::i64: RC = &AArch64::GPR64RegClass; break;
3930   case MVT::f32: RC = &AArch64::FPR32RegClass; break;
3931   case MVT::f64: RC = &AArch64::FPR64RegClass; break;
3932   }
3933   unsigned Op0Reg = getRegForValue(I->getOperand(0));
3934   if (!Op0Reg)
3935     return false;
3936   bool Op0IsKill = hasTrivialKill(I->getOperand(0));
3937   unsigned ResultReg = fastEmitInst_r(Opc, RC, Op0Reg, Op0IsKill);
3938
3939   if (!ResultReg)
3940     return false;
3941
3942   updateValueMap(I, ResultReg);
3943   return true;
3944 }
3945
3946 bool AArch64FastISel::selectFRem(const Instruction *I) {
3947   MVT RetVT;
3948   if (!isTypeLegal(I->getType(), RetVT))
3949     return false;
3950
3951   RTLIB::Libcall LC;
3952   switch (RetVT.SimpleTy) {
3953   default:
3954     return false;
3955   case MVT::f32:
3956     LC = RTLIB::REM_F32;
3957     break;
3958   case MVT::f64:
3959     LC = RTLIB::REM_F64;
3960     break;
3961   }
3962
3963   ArgListTy Args;
3964   Args.reserve(I->getNumOperands());
3965
3966   // Populate the argument list.
3967   for (auto &Arg : I->operands()) {
3968     ArgListEntry Entry;
3969     Entry.Val = Arg;
3970     Entry.Ty = Arg->getType();
3971     Args.push_back(Entry);
3972   }
3973
3974   CallLoweringInfo CLI;
3975   CLI.setCallee(TLI.getLibcallCallingConv(LC), I->getType(),
3976                 TLI.getLibcallName(LC), std::move(Args));
3977   if (!lowerCallTo(CLI))
3978     return false;
3979   updateValueMap(I, CLI.ResultReg);
3980   return true;
3981 }
3982
3983 bool AArch64FastISel::fastSelectInstruction(const Instruction *I) {
3984   switch (I->getOpcode()) {
3985   default:
3986     break;
3987   case Instruction::Add:
3988   case Instruction::Sub:
3989     return selectAddSub(I);
3990   case Instruction::Mul:
3991     return selectMul(I);
3992   case Instruction::SRem:
3993     if (!selectBinaryOp(I, ISD::SREM))
3994       return selectRem(I, ISD::SREM);
3995     return true;
3996   case Instruction::URem:
3997     if (!selectBinaryOp(I, ISD::UREM))
3998       return selectRem(I, ISD::UREM);
3999     return true;
4000   case Instruction::Shl:
4001   case Instruction::LShr:
4002   case Instruction::AShr:
4003     return selectShift(I);
4004   case Instruction::And:
4005   case Instruction::Or:
4006   case Instruction::Xor:
4007     return selectLogicalOp(I);
4008   case Instruction::Br:
4009     return selectBranch(I);
4010   case Instruction::IndirectBr:
4011     return selectIndirectBr(I);
4012   case Instruction::BitCast:
4013     if (!FastISel::selectBitCast(I))
4014       return selectBitCast(I);
4015     return true;
4016   case Instruction::FPToSI:
4017     if (!selectCast(I, ISD::FP_TO_SINT))
4018       return selectFPToInt(I, /*Signed=*/true);
4019     return true;
4020   case Instruction::FPToUI:
4021     return selectFPToInt(I, /*Signed=*/false);
4022   case Instruction::ZExt:
4023     if (!selectCast(I, ISD::ZERO_EXTEND))
4024       return selectIntExt(I);
4025     return true;
4026   case Instruction::SExt:
4027     if (!selectCast(I, ISD::SIGN_EXTEND))
4028       return selectIntExt(I);
4029     return true;
4030   case Instruction::Trunc:
4031     if (!selectCast(I, ISD::TRUNCATE))
4032       return selectTrunc(I);
4033     return true;
4034   case Instruction::FPExt:
4035     return selectFPExt(I);
4036   case Instruction::FPTrunc:
4037     return selectFPTrunc(I);
4038   case Instruction::SIToFP:
4039     if (!selectCast(I, ISD::SINT_TO_FP))
4040       return selectIntToFP(I, /*Signed=*/true);
4041     return true;
4042   case Instruction::UIToFP:
4043     return selectIntToFP(I, /*Signed=*/false);
4044   case Instruction::Load:
4045     return selectLoad(I);
4046   case Instruction::Store:
4047     return selectStore(I);
4048   case Instruction::FCmp:
4049   case Instruction::ICmp:
4050     return selectCmp(I);
4051   case Instruction::Select:
4052     return selectSelect(I);
4053   case Instruction::Ret:
4054     return selectRet(I);
4055   case Instruction::FRem:
4056     return selectFRem(I);
4057   }
4058
4059   // fall-back to target-independent instruction selection.
4060   return selectOperator(I, I->getOpcode());
4061   // Silence warnings.
4062   (void)&CC_AArch64_DarwinPCS_VarArg;
4063 }
4064
4065 namespace llvm {
4066 llvm::FastISel *AArch64::createFastISel(FunctionLoweringInfo &FuncInfo,
4067                                         const TargetLibraryInfo *LibInfo) {
4068   return new AArch64FastISel(FuncInfo, LibInfo);
4069 }
4070 }