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