lib/Target/AArch64/AArch64FastISel.cpp

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