lib/CodeGen/SelectionDAG/FastISel.cpp

   1 //===-- FastISel.cpp - Implementation of the FastISel class ---------------===//
   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 contains the implementation of the FastISel class.
  11 //
  12 // "Fast" instruction selection is designed to emit very poor code quickly.
  13 // Also, it is not designed to be able to do much lowering, so most illegal
  14 // types (e.g. i64 on 32-bit targets) and operations are not supported.  It is
  15 // also not intended to be able to do much optimization, except in a few cases
  16 // where doing optimizations reduces overall compile time.  For example, folding
  17 // constants into immediate fields is often done, because it's cheap and it
  18 // reduces the number of instructions later phases have to examine.
  19 //
  20 // "Fast" instruction selection is able to fail gracefully and transfer
  21 // control to the SelectionDAG selector for operations that it doesn't
  22 // support.  In many cases, this allows us to avoid duplicating a lot of
  23 // the complicated lowering logic that SelectionDAG currently has.
  24 //
  25 // The intended use for "fast" instruction selection is "-O0" mode
  26 // compilation, where the quality of the generated code is irrelevant when
  27 // weighed against the speed at which the code can be generated.  Also,
  28 // at -O0, the LLVM optimizers are not running, and this makes the
  29 // compile time of codegen a much higher portion of the overall compile
  30 // time.  Despite its limitations, "fast" instruction selection is able to
  31 // handle enough code on its own to provide noticeable overall speedups
  32 // in -O0 compiles.
  33 //
  34 // Basic operations are supported in a target-independent way, by reading
  35 // the same instruction descriptions that the SelectionDAG selector reads,
  36 // and identifying simple arithmetic operations that can be directly selected
  37 // from simple operators.  More complicated operations currently require
  38 // target-specific code.
  39 //
  40 //===----------------------------------------------------------------------===//
  41
  42 #include "llvm/CodeGen/Analysis.h"
  43 #include "llvm/CodeGen/FastISel.h"
  44 #include "llvm/ADT/Optional.h"
  45 #include "llvm/ADT/Statistic.h"
  46 #include "llvm/Analysis/BranchProbabilityInfo.h"
  47 #include "llvm/Analysis/Loads.h"
  48 #include "llvm/CodeGen/Analysis.h"
  49 #include "llvm/CodeGen/FunctionLoweringInfo.h"
  50 #include "llvm/CodeGen/MachineFrameInfo.h"
  51 #include "llvm/CodeGen/MachineInstrBuilder.h"
  52 #include "llvm/CodeGen/MachineModuleInfo.h"
  53 #include "llvm/CodeGen/MachineRegisterInfo.h"
  54 #include "llvm/CodeGen/StackMaps.h"
  55 #include "llvm/IR/DataLayout.h"
  56 #include "llvm/IR/DebugInfo.h"
  57 #include "llvm/IR/Function.h"
  58 #include "llvm/IR/GlobalVariable.h"
  59 #include "llvm/IR/Instructions.h"
  60 #include "llvm/IR/IntrinsicInst.h"
  61 #include "llvm/IR/Operator.h"
  62 #include "llvm/Support/Debug.h"
  63 #include "llvm/Support/ErrorHandling.h"
  64 #include "llvm/Target/TargetInstrInfo.h"
  65 #include "llvm/Target/TargetLibraryInfo.h"
  66 #include "llvm/Target/TargetLowering.h"
  67 #include "llvm/Target/TargetMachine.h"
  68 using namespace llvm;
  69
  70 #define DEBUG_TYPE "isel"
  71
  72 STATISTIC(NumFastIselSuccessIndependent, "Number of insts selected by "
  73           "target-independent selector");
  74 STATISTIC(NumFastIselSuccessTarget, "Number of insts selected by "
  75           "target-specific selector");
  76 STATISTIC(NumFastIselDead, "Number of dead insts removed on failure");
  77
  78 /// \brief Set CallLoweringInfo attribute flags based on a call instruction
  79 /// and called function attributes.
  80 void FastISel::ArgListEntry::setAttributes(ImmutableCallSite *CS,
  81                                            unsigned AttrIdx) {
  82   isSExt     = CS->paramHasAttr(AttrIdx, Attribute::SExt);
  83   isZExt     = CS->paramHasAttr(AttrIdx, Attribute::ZExt);
  84   isInReg    = CS->paramHasAttr(AttrIdx, Attribute::InReg);
  85   isSRet     = CS->paramHasAttr(AttrIdx, Attribute::StructRet);
  86   isNest     = CS->paramHasAttr(AttrIdx, Attribute::Nest);
  87   isByVal    = CS->paramHasAttr(AttrIdx, Attribute::ByVal);
  88   isInAlloca = CS->paramHasAttr(AttrIdx, Attribute::InAlloca);
  89   isReturned = CS->paramHasAttr(AttrIdx, Attribute::Returned);
  90   Alignment  = CS->getParamAlignment(AttrIdx);
  91 }
  92
  93 /// startNewBlock - Set the current block to which generated machine
  94 /// instructions will be appended, and clear the local CSE map.
  95 ///
  96 void FastISel::startNewBlock() {
  97   LocalValueMap.clear();
  98
  99   // Instructions are appended to FuncInfo.MBB. If the basic block already
 100   // contains labels or copies, use the last instruction as the last local
 101   // value.
 102   EmitStartPt = nullptr;
 103   if (!FuncInfo.MBB->empty())
 104     EmitStartPt = &FuncInfo.MBB->back();
 105   LastLocalValue = EmitStartPt;
 106 }
 107
 108 bool FastISel::LowerArguments() {
 109   if (!FuncInfo.CanLowerReturn)
 110     // Fallback to SDISel argument lowering code to deal with sret pointer
 111     // parameter.
 112     return false;
 113
 114   if (!FastLowerArguments())
 115     return false;
 116
 117   // Enter arguments into ValueMap for uses in non-entry BBs.
 118   for (Function::const_arg_iterator I = FuncInfo.Fn->arg_begin(),
 119          E = FuncInfo.Fn->arg_end(); I != E; ++I) {
 120     DenseMap<const Value *, unsigned>::iterator VI = LocalValueMap.find(I);
 121     assert(VI != LocalValueMap.end() && "Missed an argument?");
 122     FuncInfo.ValueMap[I] = VI->second;
 123   }
 124   return true;
 125 }
 126
 127 void FastISel::flushLocalValueMap() {
 128   LocalValueMap.clear();
 129   LastLocalValue = EmitStartPt;
 130   recomputeInsertPt();
 131 }
 132
 133 bool FastISel::hasTrivialKill(const Value *V) const {
 134   // Don't consider constants or arguments to have trivial kills.
 135   const Instruction *I = dyn_cast<Instruction>(V);
 136   if (!I)
 137     return false;
 138
 139   // No-op casts are trivially coalesced by fast-isel.
 140   if (const CastInst *Cast = dyn_cast<CastInst>(I))
 141     if (Cast->isNoopCast(DL.getIntPtrType(Cast->getContext())) &&
 142         !hasTrivialKill(Cast->getOperand(0)))
 143       return false;
 144
 145   // GEPs with all zero indices are trivially coalesced by fast-isel.
 146   if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I))
 147     if (GEP->hasAllZeroIndices() && !hasTrivialKill(GEP->getOperand(0)))
 148       return false;
 149
 150   // Only instructions with a single use in the same basic block are considered
 151   // to have trivial kills.
 152   return I->hasOneUse() &&
 153          !(I->getOpcode() == Instruction::BitCast ||
 154            I->getOpcode() == Instruction::PtrToInt ||
 155            I->getOpcode() == Instruction::IntToPtr) &&
 156          cast<Instruction>(*I->user_begin())->getParent() == I->getParent();
 157 }
 158
 159 unsigned FastISel::getRegForValue(const Value *V) {
 160   EVT RealVT = TLI.getValueType(V->getType(), /*AllowUnknown=*/true);
 161   // Don't handle non-simple values in FastISel.
 162   if (!RealVT.isSimple())
 163     return 0;
 164
 165   // Ignore illegal types. We must do this before looking up the value
 166   // in ValueMap because Arguments are given virtual registers regardless
 167   // of whether FastISel can handle them.
 168   MVT VT = RealVT.getSimpleVT();
 169   if (!TLI.isTypeLegal(VT)) {
 170     // Handle integer promotions, though, because they're common and easy.
 171     if (VT == MVT::i1 || VT == MVT::i8 || VT == MVT::i16)
 172       VT = TLI.getTypeToTransformTo(V->getContext(), VT).getSimpleVT();
 173     else
 174       return 0;
 175   }
 176
 177   // Look up the value to see if we already have a register for it.
 178   unsigned Reg = lookUpRegForValue(V);
 179   if (Reg != 0)
 180     return Reg;
 181
 182   // In bottom-up mode, just create the virtual register which will be used
 183   // to hold the value. It will be materialized later.
 184   if (isa<Instruction>(V) &&
 185       (!isa<AllocaInst>(V) ||
 186        !FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(V))))
 187     return FuncInfo.InitializeRegForValue(V);
 188
 189   SavePoint SaveInsertPt = enterLocalValueArea();
 190
 191   // Materialize the value in a register. Emit any instructions in the
 192   // local value area.
 193   Reg = materializeRegForValue(V, VT);
 194
 195   leaveLocalValueArea(SaveInsertPt);
 196
 197   return Reg;
 198 }
 199
 200 /// materializeRegForValue - Helper for getRegForValue. This function is
 201 /// called when the value isn't already available in a register and must
 202 /// be materialized with new instructions.
 203 unsigned FastISel::materializeRegForValue(const Value *V, MVT VT) {
 204   unsigned Reg = 0;
 205
 206   if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
 207     if (CI->getValue().getActiveBits() <= 64)
 208       Reg = FastEmit_i(VT, VT, ISD::Constant, CI->getZExtValue());
 209   } else if (isa<AllocaInst>(V)) {
 210     Reg = TargetMaterializeAlloca(cast<AllocaInst>(V));
 211   } else if (isa<ConstantPointerNull>(V)) {
 212     // Translate this as an integer zero so that it can be
 213     // local-CSE'd with actual integer zeros.
 214     Reg =
 215       getRegForValue(Constant::getNullValue(DL.getIntPtrType(V->getContext())));
 216   } else if (const ConstantFP *CF = dyn_cast<ConstantFP>(V)) {
 217     if (CF->isNullValue()) {
 218       Reg = TargetMaterializeFloatZero(CF);
 219     } else {
 220       // Try to emit the constant directly.
 221       Reg = FastEmit_f(VT, VT, ISD::ConstantFP, CF);
 222     }
 223
 224     if (!Reg) {
 225       // Try to emit the constant by using an integer constant with a cast.
 226       const APFloat &Flt = CF->getValueAPF();
 227       EVT IntVT = TLI.getPointerTy();
 228
 229       uint64_t x[2];
 230       uint32_t IntBitWidth = IntVT.getSizeInBits();
 231       bool isExact;
 232       (void) Flt.convertToInteger(x, IntBitWidth, /*isSigned=*/true,
 233                                   APFloat::rmTowardZero, &isExact);
 234       if (isExact) {
 235         APInt IntVal(IntBitWidth, x);
 236
 237         unsigned IntegerReg =
 238           getRegForValue(ConstantInt::get(V->getContext(), IntVal));
 239         if (IntegerReg != 0)
 240           Reg = FastEmit_r(IntVT.getSimpleVT(), VT, ISD::SINT_TO_FP,
 241                            IntegerReg, /*Kill=*/false);
 242       }
 243     }
 244   } else if (const Operator *Op = dyn_cast<Operator>(V)) {
 245     if (!SelectOperator(Op, Op->getOpcode()))
 246       if (!isa<Instruction>(Op) ||
 247           !TargetSelectInstruction(cast<Instruction>(Op)))
 248         return 0;
 249     Reg = lookUpRegForValue(Op);
 250   } else if (isa<UndefValue>(V)) {
 251     Reg = createResultReg(TLI.getRegClassFor(VT));
 252     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
 253             TII.get(TargetOpcode::IMPLICIT_DEF), Reg);
 254   }
 255
 256   // If target-independent code couldn't handle the value, give target-specific
 257   // code a try.
 258   if (!Reg && isa<Constant>(V))
 259     Reg = TargetMaterializeConstant(cast<Constant>(V));
 260
 261   // Don't cache constant materializations in the general ValueMap.
 262   // To do so would require tracking what uses they dominate.
 263   if (Reg != 0) {
 264     LocalValueMap[V] = Reg;
 265     LastLocalValue = MRI.getVRegDef(Reg);
 266   }
 267   return Reg;
 268 }
 269
 270 unsigned FastISel::lookUpRegForValue(const Value *V) {
 271   // Look up the value to see if we already have a register for it. We
 272   // cache values defined by Instructions across blocks, and other values
 273   // only locally. This is because Instructions already have the SSA
 274   // def-dominates-use requirement enforced.
 275   DenseMap<const Value *, unsigned>::iterator I = FuncInfo.ValueMap.find(V);
 276   if (I != FuncInfo.ValueMap.end())
 277     return I->second;
 278   return LocalValueMap[V];
 279 }
 280
 281 /// UpdateValueMap - Update the value map to include the new mapping for this
 282 /// instruction, or insert an extra copy to get the result in a previous
 283 /// determined register.
 284 /// NOTE: This is only necessary because we might select a block that uses
 285 /// a value before we select the block that defines the value.  It might be
 286 /// possible to fix this by selecting blocks in reverse postorder.
 287 void FastISel::UpdateValueMap(const Value *I, unsigned Reg, unsigned NumRegs) {
 288   if (!isa<Instruction>(I)) {
 289     LocalValueMap[I] = Reg;
 290     return;
 291   }
 292
 293   unsigned &AssignedReg = FuncInfo.ValueMap[I];
 294   if (AssignedReg == 0)
 295     // Use the new register.
 296     AssignedReg = Reg;
 297   else if (Reg != AssignedReg) {
 298     // Arrange for uses of AssignedReg to be replaced by uses of Reg.
 299     for (unsigned i = 0; i < NumRegs; i++)
 300       FuncInfo.RegFixups[AssignedReg+i] = Reg+i;
 301
 302     AssignedReg = Reg;
 303   }
 304 }
 305
 306 std::pair<unsigned, bool> FastISel::getRegForGEPIndex(const Value *Idx) {
 307   unsigned IdxN = getRegForValue(Idx);
 308   if (IdxN == 0)
 309     // Unhandled operand. Halt "fast" selection and bail.
 310     return std::pair<unsigned, bool>(0, false);
 311
 312   bool IdxNIsKill = hasTrivialKill(Idx);
 313
 314   // If the index is smaller or larger than intptr_t, truncate or extend it.
 315   MVT PtrVT = TLI.getPointerTy();
 316   EVT IdxVT = EVT::getEVT(Idx->getType(), /*HandleUnknown=*/false);
 317   if (IdxVT.bitsLT(PtrVT)) {
 318     IdxN = FastEmit_r(IdxVT.getSimpleVT(), PtrVT, ISD::SIGN_EXTEND,
 319                       IdxN, IdxNIsKill);
 320     IdxNIsKill = true;
 321   }
 322   else if (IdxVT.bitsGT(PtrVT)) {
 323     IdxN = FastEmit_r(IdxVT.getSimpleVT(), PtrVT, ISD::TRUNCATE,
 324                       IdxN, IdxNIsKill);
 325     IdxNIsKill = true;
 326   }
 327   return std::pair<unsigned, bool>(IdxN, IdxNIsKill);
 328 }
 329
 330 void FastISel::recomputeInsertPt() {
 331   if (getLastLocalValue()) {
 332     FuncInfo.InsertPt = getLastLocalValue();
 333     FuncInfo.MBB = FuncInfo.InsertPt->getParent();
 334     ++FuncInfo.InsertPt;
 335   } else
 336     FuncInfo.InsertPt = FuncInfo.MBB->getFirstNonPHI();
 337
 338   // Now skip past any EH_LABELs, which must remain at the beginning.
 339   while (FuncInfo.InsertPt != FuncInfo.MBB->end() &&
 340          FuncInfo.InsertPt->getOpcode() == TargetOpcode::EH_LABEL)
 341     ++FuncInfo.InsertPt;
 342 }
 343
 344 void FastISel::removeDeadCode(MachineBasicBlock::iterator I,
 345                               MachineBasicBlock::iterator E) {
 346   assert (I && E && std::distance(I, E) > 0 && "Invalid iterator!");
 347   while (I != E) {
 348     MachineInstr *Dead = &*I;
 349     ++I;
 350     Dead->eraseFromParent();
 351     ++NumFastIselDead;
 352   }
 353   recomputeInsertPt();
 354 }
 355
 356 FastISel::SavePoint FastISel::enterLocalValueArea() {
 357   MachineBasicBlock::iterator OldInsertPt = FuncInfo.InsertPt;
 358   DebugLoc OldDL = DbgLoc;
 359   recomputeInsertPt();
 360   DbgLoc = DebugLoc();
 361   SavePoint SP = { OldInsertPt, OldDL };
 362   return SP;
 363 }
 364
 365 void FastISel::leaveLocalValueArea(SavePoint OldInsertPt) {
 366   if (FuncInfo.InsertPt != FuncInfo.MBB->begin())
 367     LastLocalValue = std::prev(FuncInfo.InsertPt);
 368
 369   // Restore the previous insert position.
 370   FuncInfo.InsertPt = OldInsertPt.InsertPt;
 371   DbgLoc = OldInsertPt.DL;
 372 }
 373
 374 /// SelectBinaryOp - Select and emit code for a binary operator instruction,
 375 /// which has an opcode which directly corresponds to the given ISD opcode.
 376 ///
 377 bool FastISel::SelectBinaryOp(const User *I, unsigned ISDOpcode) {
 378   EVT VT = EVT::getEVT(I->getType(), /*HandleUnknown=*/true);
 379   if (VT == MVT::Other || !VT.isSimple())
 380     // Unhandled type. Halt "fast" selection and bail.
 381     return false;
 382
 383   // We only handle legal types. For example, on x86-32 the instruction
 384   // selector contains all of the 64-bit instructions from x86-64,
 385   // under the assumption that i64 won't be used if the target doesn't
 386   // support it.
 387   if (!TLI.isTypeLegal(VT)) {
 388     // MVT::i1 is special. Allow AND, OR, or XOR because they
 389     // don't require additional zeroing, which makes them easy.
 390     if (VT == MVT::i1 &&
 391         (ISDOpcode == ISD::AND || ISDOpcode == ISD::OR ||
 392          ISDOpcode == ISD::XOR))
 393       VT = TLI.getTypeToTransformTo(I->getContext(), VT);
 394     else
 395       return false;
 396   }
 397
 398   // Check if the first operand is a constant, and handle it as "ri".  At -O0,
 399   // we don't have anything that canonicalizes operand order.
 400   if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(0)))
 401     if (isa<Instruction>(I) && cast<Instruction>(I)->isCommutative()) {
 402       unsigned Op1 = getRegForValue(I->getOperand(1));
 403       if (Op1 == 0) return false;
 404
 405       bool Op1IsKill = hasTrivialKill(I->getOperand(1));
 406
 407       unsigned ResultReg = FastEmit_ri_(VT.getSimpleVT(), ISDOpcode, Op1,
 408                                         Op1IsKill, CI->getZExtValue(),
 409                                         VT.getSimpleVT());
 410       if (ResultReg == 0) return false;
 411
 412       // We successfully emitted code for the given LLVM Instruction.
 413       UpdateValueMap(I, ResultReg);
 414       return true;
 415     }
 416
 417
 418   unsigned Op0 = getRegForValue(I->getOperand(0));
 419   if (Op0 == 0)   // Unhandled operand. Halt "fast" selection and bail.
 420     return false;
 421
 422   bool Op0IsKill = hasTrivialKill(I->getOperand(0));
 423
 424   // Check if the second operand is a constant and handle it appropriately.
 425   if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
 426     uint64_t Imm = CI->getZExtValue();
 427
 428     // Transform "sdiv exact X, 8" -> "sra X, 3".
 429     if (ISDOpcode == ISD::SDIV && isa<BinaryOperator>(I) &&
 430         cast<BinaryOperator>(I)->isExact() &&
 431         isPowerOf2_64(Imm)) {
 432       Imm = Log2_64(Imm);
 433       ISDOpcode = ISD::SRA;
 434     }
 435
 436     // Transform "urem x, pow2" -> "and x, pow2-1".
 437     if (ISDOpcode == ISD::UREM && isa<BinaryOperator>(I) &&
 438         isPowerOf2_64(Imm)) {
 439       --Imm;
 440       ISDOpcode = ISD::AND;
 441     }
 442
 443     unsigned ResultReg = FastEmit_ri_(VT.getSimpleVT(), ISDOpcode, Op0,
 444                                       Op0IsKill, Imm, VT.getSimpleVT());
 445     if (ResultReg == 0) return false;
 446
 447     // We successfully emitted code for the given LLVM Instruction.
 448     UpdateValueMap(I, ResultReg);
 449     return true;
 450   }
 451
 452   // Check if the second operand is a constant float.
 453   if (ConstantFP *CF = dyn_cast<ConstantFP>(I->getOperand(1))) {
 454     unsigned ResultReg = FastEmit_rf(VT.getSimpleVT(), VT.getSimpleVT(),
 455                                      ISDOpcode, Op0, Op0IsKill, CF);
 456     if (ResultReg != 0) {
 457       // We successfully emitted code for the given LLVM Instruction.
 458       UpdateValueMap(I, ResultReg);
 459       return true;
 460     }
 461   }
 462
 463   unsigned Op1 = getRegForValue(I->getOperand(1));
 464   if (Op1 == 0)
 465     // Unhandled operand. Halt "fast" selection and bail.
 466     return false;
 467
 468   bool Op1IsKill = hasTrivialKill(I->getOperand(1));
 469
 470   // Now we have both operands in registers. Emit the instruction.
 471   unsigned ResultReg = FastEmit_rr(VT.getSimpleVT(), VT.getSimpleVT(),
 472                                    ISDOpcode,
 473                                    Op0, Op0IsKill,
 474                                    Op1, Op1IsKill);
 475   if (ResultReg == 0)
 476     // Target-specific code wasn't able to find a machine opcode for
 477     // the given ISD opcode and type. Halt "fast" selection and bail.
 478     return false;
 479
 480   // We successfully emitted code for the given LLVM Instruction.
 481   UpdateValueMap(I, ResultReg);
 482   return true;
 483 }
 484
 485 bool FastISel::SelectGetElementPtr(const User *I) {
 486   unsigned N = getRegForValue(I->getOperand(0));
 487   if (N == 0)
 488     // Unhandled operand. Halt "fast" selection and bail.
 489     return false;
 490
 491   bool NIsKill = hasTrivialKill(I->getOperand(0));
 492
 493   // Keep a running tab of the total offset to coalesce multiple N = N + Offset
 494   // into a single N = N + TotalOffset.
 495   uint64_t TotalOffs = 0;
 496   // FIXME: What's a good SWAG number for MaxOffs?
 497   uint64_t MaxOffs = 2048;
 498   Type *Ty = I->getOperand(0)->getType();
 499   MVT VT = TLI.getPointerTy();
 500   for (GetElementPtrInst::const_op_iterator OI = I->op_begin()+1,
 501        E = I->op_end(); OI != E; ++OI) {
 502     const Value *Idx = *OI;
 503     if (StructType *StTy = dyn_cast<StructType>(Ty)) {
 504       unsigned Field = cast<ConstantInt>(Idx)->getZExtValue();
 505       if (Field) {
 506         // N = N + Offset
 507         TotalOffs += DL.getStructLayout(StTy)->getElementOffset(Field);
 508         if (TotalOffs >= MaxOffs) {
 509           N = FastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT);
 510           if (N == 0)
 511             // Unhandled operand. Halt "fast" selection and bail.
 512             return false;
 513           NIsKill = true;
 514           TotalOffs = 0;
 515         }
 516       }
 517       Ty = StTy->getElementType(Field);
 518     } else {
 519       Ty = cast<SequentialType>(Ty)->getElementType();
 520
 521       // If this is a constant subscript, handle it quickly.
 522       if (const ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) {
 523         if (CI->isZero()) continue;
 524         // N = N + Offset
 525         TotalOffs +=
 526           DL.getTypeAllocSize(Ty)*cast<ConstantInt>(CI)->getSExtValue();
 527         if (TotalOffs >= MaxOffs) {
 528           N = FastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT);
 529           if (N == 0)
 530             // Unhandled operand. Halt "fast" selection and bail.
 531             return false;
 532           NIsKill = true;
 533           TotalOffs = 0;
 534         }
 535         continue;
 536       }
 537       if (TotalOffs) {
 538         N = FastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT);
 539         if (N == 0)
 540           // Unhandled operand. Halt "fast" selection and bail.
 541           return false;
 542         NIsKill = true;
 543         TotalOffs = 0;
 544       }
 545
 546       // N = N + Idx * ElementSize;
 547       uint64_t ElementSize = DL.getTypeAllocSize(Ty);
 548       std::pair<unsigned, bool> Pair = getRegForGEPIndex(Idx);
 549       unsigned IdxN = Pair.first;
 550       bool IdxNIsKill = Pair.second;
 551       if (IdxN == 0)
 552         // Unhandled operand. Halt "fast" selection and bail.
 553         return false;
 554
 555       if (ElementSize != 1) {
 556         IdxN = FastEmit_ri_(VT, ISD::MUL, IdxN, IdxNIsKill, ElementSize, VT);
 557         if (IdxN == 0)
 558           // Unhandled operand. Halt "fast" selection and bail.
 559           return false;
 560         IdxNIsKill = true;
 561       }
 562       N = FastEmit_rr(VT, VT, ISD::ADD, N, NIsKill, IdxN, IdxNIsKill);
 563       if (N == 0)
 564         // Unhandled operand. Halt "fast" selection and bail.
 565         return false;
 566     }
 567   }
 568   if (TotalOffs) {
 569     N = FastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT);
 570     if (N == 0)
 571       // Unhandled operand. Halt "fast" selection and bail.
 572       return false;
 573   }
 574
 575   // We successfully emitted code for the given LLVM Instruction.
 576   UpdateValueMap(I, N);
 577   return true;
 578 }
 579
 580 /// \brief Add a stackmap or patchpoint intrinsic call's live variable operands
 581 /// to a stackmap or patchpoint machine instruction.
 582 bool FastISel::addStackMapLiveVars(SmallVectorImpl<MachineOperand> &Ops,
 583                                    const CallInst *CI, unsigned StartIdx) {
 584   for (unsigned i = StartIdx, e = CI->getNumArgOperands(); i != e; ++i) {
 585     Value *Val = CI->getArgOperand(i);
 586     // Check for constants and encode them with a StackMaps::ConstantOp prefix.
 587     if (auto *C = dyn_cast<ConstantInt>(Val)) {
 588       Ops.push_back(MachineOperand::CreateImm(StackMaps::ConstantOp));
 589       Ops.push_back(MachineOperand::CreateImm(C->getSExtValue()));
 590     } else if (isa<ConstantPointerNull>(Val)) {
 591       Ops.push_back(MachineOperand::CreateImm(StackMaps::ConstantOp));
 592       Ops.push_back(MachineOperand::CreateImm(0));
 593     } else if (auto *AI = dyn_cast<AllocaInst>(Val)) {
 594       // Values coming from a stack location also require a sepcial encoding,
 595       // but that is added later on by the target specific frame index
 596       // elimination implementation.
 597       auto SI = FuncInfo.StaticAllocaMap.find(AI);
 598       if (SI != FuncInfo.StaticAllocaMap.end())
 599         Ops.push_back(MachineOperand::CreateFI(SI->second));
 600       else
 601         return false;
 602     } else {
 603       unsigned Reg = getRegForValue(Val);
 604       if (Reg == 0)
 605         return false;
 606       Ops.push_back(MachineOperand::CreateReg(Reg, /*IsDef=*/false));
 607     }
 608   }
 609
 610   return true;
 611 }
 612
 613 bool FastISel::SelectStackmap(const CallInst *I) {
 614   // void @llvm.experimental.stackmap(i64 <id>, i32 <numShadowBytes>,
 615   //                                  [live variables...])
 616   assert(I->getCalledFunction()->getReturnType()->isVoidTy() &&
 617          "Stackmap cannot return a value.");
 618
 619   // The stackmap intrinsic only records the live variables (the arguments
 620   // passed to it) and emits NOPS (if requested). Unlike the patchpoint
 621   // intrinsic, this won't be lowered to a function call. This means we don't
 622   // have to worry about calling conventions and target-specific lowering code.
 623   // Instead we perform the call lowering right here.
 624   //
 625   // CALLSEQ_START(0)
 626   // STACKMAP(id, nbytes, ...)
 627   // CALLSEQ_END(0, 0)
 628   //
 629   SmallVector<MachineOperand, 32> Ops;
 630
 631   // Add the <id> and <numBytes> constants.
 632   assert(isa<ConstantInt>(I->getOperand(PatchPointOpers::IDPos)) &&
 633          "Expected a constant integer.");
 634   const auto *ID = cast<ConstantInt>(I->getOperand(PatchPointOpers::IDPos));
 635   Ops.push_back(MachineOperand::CreateImm(ID->getZExtValue()));
 636
 637   assert(isa<ConstantInt>(I->getOperand(PatchPointOpers::NBytesPos)) &&
 638          "Expected a constant integer.");
 639   const auto *NumBytes =
 640     cast<ConstantInt>(I->getOperand(PatchPointOpers::NBytesPos));
 641   Ops.push_back(MachineOperand::CreateImm(NumBytes->getZExtValue()));
 642
 643   // Push live variables for the stack map (skipping the first two arguments
 644   // <id> and <numBytes>).
 645   if (!addStackMapLiveVars(Ops, I, 2))
 646     return false;
 647
 648   // We are not adding any register mask info here, because the stackmap doesn't
 649   // clobber anything.
 650
 651   // Add scratch registers as implicit def and early clobber.
 652   CallingConv::ID CC = I->getCallingConv();
 653   const MCPhysReg *ScratchRegs = TLI.getScratchRegisters(CC);
 654   for (unsigned i = 0; ScratchRegs[i]; ++i)
 655     Ops.push_back(MachineOperand::CreateReg(
 656       ScratchRegs[i], /*IsDef=*/true, /*IsImp=*/true, /*IsKill=*/false,
 657       /*IsDead=*/false, /*IsUndef=*/false, /*IsEarlyClobber=*/true));
 658
 659   // Issue CALLSEQ_START
 660   unsigned AdjStackDown = TII.getCallFrameSetupOpcode();
 661   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AdjStackDown))
 662     .addImm(0);
 663
 664   // Issue STACKMAP.
 665   MachineInstrBuilder MIB = BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
 666                                     TII.get(TargetOpcode::STACKMAP));
 667   for (auto const &MO : Ops)
 668     MIB.addOperand(MO);
 669
 670   // Issue CALLSEQ_END
 671   unsigned AdjStackUp = TII.getCallFrameDestroyOpcode();
 672   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AdjStackUp))
 673     .addImm(0).addImm(0);
 674
 675   // Inform the Frame Information that we have a stackmap in this function.
 676   FuncInfo.MF->getFrameInfo()->setHasStackMap();
 677
 678   return true;
 679 }
 680
 681 /// Returns an AttributeSet representing the attributes applied to the return
 682 /// value of the given call.
 683 static AttributeSet getReturnAttrs(FastISel::CallLoweringInfo &CLI) {
 684   SmallVector<Attribute::AttrKind, 2> Attrs;
 685   if (CLI.RetSExt)
 686     Attrs.push_back(Attribute::SExt);
 687   if (CLI.RetZExt)
 688     Attrs.push_back(Attribute::ZExt);
 689   if (CLI.IsInReg)
 690     Attrs.push_back(Attribute::InReg);
 691
 692   return AttributeSet::get(CLI.RetTy->getContext(), AttributeSet::ReturnIndex,
 693                            Attrs);
 694 }
 695
 696 bool FastISel::LowerCallTo(const CallInst *CI, const char *SymName,
 697                            unsigned NumArgs) {
 698   ImmutableCallSite CS(CI);
 699
 700   PointerType *PT = cast<PointerType>(CS.getCalledValue()->getType());
 701   FunctionType *FTy = cast<FunctionType>(PT->getElementType());
 702   Type *RetTy = FTy->getReturnType();
 703
 704   ArgListTy Args;
 705   Args.reserve(NumArgs);
 706
 707   // Populate the argument list.
 708   // Attributes for args start at offset 1, after the return attribute.
 709   for (unsigned ArgI = 0; ArgI != NumArgs; ++ArgI) {
 710     Value *V = CI->getOperand(ArgI);
 711
 712     assert(!V->getType()->isEmptyTy() && "Empty type passed to intrinsic.");
 713
 714     ArgListEntry Entry;
 715     Entry.Val = V;
 716     Entry.Ty = V->getType();
 717     Entry.setAttributes(&CS, ArgI + 1);
 718     Args.push_back(Entry);
 719   }
 720
 721   CallLoweringInfo CLI;
 722   CLI.setCallee(RetTy, FTy, SymName, std::move(Args), CS, NumArgs);
 723
 724   return LowerCallTo(CLI);
 725 }
 726
 727 bool FastISel::LowerCallTo(CallLoweringInfo &CLI) {
 728   // Handle the incoming return values from the call.
 729   CLI.clearIns();
 730   SmallVector<EVT, 4> RetTys;
 731   ComputeValueVTs(TLI, CLI.RetTy, RetTys);
 732
 733   SmallVector<ISD::OutputArg, 4> Outs;
 734   GetReturnInfo(CLI.RetTy, getReturnAttrs(CLI), Outs, TLI);
 735
 736   bool CanLowerReturn = TLI.CanLowerReturn(CLI.CallConv, *FuncInfo.MF,
 737                                            CLI.IsVarArg, Outs,
 738                                            CLI.RetTy->getContext());
 739
 740   // FIXME: sret demotion isn't supported yet - bail out.
 741   if (!CanLowerReturn)
 742     return false;
 743
 744   for (unsigned I = 0, E = RetTys.size(); I != E; ++I) {
 745     EVT VT = RetTys[I];
 746     MVT RegisterVT = TLI.getRegisterType(CLI.RetTy->getContext(), VT);
 747     unsigned NumRegs = TLI.getNumRegisters(CLI.RetTy->getContext(), VT);
 748     for (unsigned i = 0; i != NumRegs; ++i) {
 749       ISD::InputArg MyFlags;
 750       MyFlags.VT = RegisterVT;
 751       MyFlags.ArgVT = VT;
 752       MyFlags.Used = CLI.IsReturnValueUsed;
 753       if (CLI.RetSExt)
 754         MyFlags.Flags.setSExt();
 755       if (CLI.RetZExt)
 756         MyFlags.Flags.setZExt();
 757       if (CLI.IsInReg)
 758         MyFlags.Flags.setInReg();
 759       CLI.Ins.push_back(MyFlags);
 760     }
 761   }
 762
 763   // Handle all of the outgoing arguments.
 764   CLI.clearOuts();
 765   for (auto &Arg : CLI.getArgs()) {
 766     Type *FinalType = Arg.Ty;
 767     if (Arg.isByVal)
 768       FinalType = cast<PointerType>(Arg.Ty)->getElementType();
 769     bool NeedsRegBlock = TLI.functionArgumentNeedsConsecutiveRegisters(
 770       FinalType, CLI.CallConv, CLI.IsVarArg);
 771
 772     ISD::ArgFlagsTy Flags;
 773     if (Arg.isZExt)
 774       Flags.setZExt();
 775     if (Arg.isSExt)
 776       Flags.setSExt();
 777     if (Arg.isInReg)
 778       Flags.setInReg();
 779     if (Arg.isSRet)
 780       Flags.setSRet();
 781     if (Arg.isByVal)
 782       Flags.setByVal();
 783     if (Arg.isInAlloca) {
 784       Flags.setInAlloca();
 785       // Set the byval flag for CCAssignFn callbacks that don't know about
 786       // inalloca. This way we can know how many bytes we should've allocated
 787       // and how many bytes a callee cleanup function will pop.  If we port
 788       // inalloca to more targets, we'll have to add custom inalloca handling in
 789       // the various CC lowering callbacks.
 790       Flags.setByVal();
 791     }
 792     if (Arg.isByVal || Arg.isInAlloca) {
 793       PointerType *Ty = cast<PointerType>(Arg.Ty);
 794       Type *ElementTy = Ty->getElementType();
 795       unsigned FrameSize = DL.getTypeAllocSize(ElementTy);
 796       // For ByVal, alignment should come from FE. BE will guess if this info is
 797       // not there, but there are cases it cannot get right.
 798       unsigned FrameAlign = Arg.Alignment;
 799       if (!FrameAlign)
 800         FrameAlign = TLI.getByValTypeAlignment(ElementTy);
 801       Flags.setByValSize(FrameSize);
 802       Flags.setByValAlign(FrameAlign);
 803     }
 804     if (Arg.isNest)
 805       Flags.setNest();
 806     if (NeedsRegBlock)
 807       Flags.setInConsecutiveRegs();
 808     unsigned OriginalAlignment = DL.getABITypeAlignment(Arg.Ty);
 809     Flags.setOrigAlign(OriginalAlignment);
 810
 811     CLI.OutVals.push_back(Arg.Val);
 812     CLI.OutFlags.push_back(Flags);
 813   }
 814
 815   if (!FastLowerCall(CLI))
 816     return false;
 817
 818   // Set all unused physreg defs as dead.
 819   assert(CLI.Call && "No call instruction specified.");
 820   CLI.Call->setPhysRegsDeadExcept(CLI.InRegs, TRI);
 821
 822   if (CLI.NumResultRegs && CLI.CS)
 823     UpdateValueMap(CLI.CS->getInstruction(), CLI.ResultReg, CLI.NumResultRegs);
 824
 825   return true;
 826 }
 827
 828 bool FastISel::LowerCall(const CallInst *CI) {
 829   ImmutableCallSite CS(CI);
 830
 831   PointerType *PT = cast<PointerType>(CS.getCalledValue()->getType());
 832   FunctionType *FuncTy = cast<FunctionType>(PT->getElementType());
 833   Type *RetTy = FuncTy->getReturnType();
 834
 835   ArgListTy Args;
 836   ArgListEntry Entry;
 837   Args.reserve(CS.arg_size());
 838
 839   for (ImmutableCallSite::arg_iterator i = CS.arg_begin(), e = CS.arg_end();
 840        i != e; ++i) {
 841     Value *V = *i;
 842
 843     // Skip empty types
 844     if (V->getType()->isEmptyTy())
 845       continue;
 846
 847     Entry.Val = V;
 848     Entry.Ty = V->getType();
 849
 850     // Skip the first return-type Attribute to get to params.
 851     Entry.setAttributes(&CS, i - CS.arg_begin() + 1);
 852     Args.push_back(Entry);
 853   }
 854
 855   // Check if target-independent constraints permit a tail call here.
 856   // Target-dependent constraints are checked within FastLowerCall.
 857   bool IsTailCall = CI->isTailCall();
 858   if (IsTailCall && !isInTailCallPosition(CS, TM, TLI))
 859     IsTailCall = false;
 860
 861   CallLoweringInfo CLI;
 862   CLI.setCallee(RetTy, FuncTy, CI->getCalledValue(), std::move(Args), CS)
 863     .setTailCall(IsTailCall);
 864
 865   return LowerCallTo(CLI);
 866 }
 867
 868 bool FastISel::SelectCall(const User *I) {
 869   const CallInst *Call = cast<CallInst>(I);
 870
 871   // Handle simple inline asms.
 872   if (const InlineAsm *IA = dyn_cast<InlineAsm>(Call->getCalledValue())) {
 873     // Don't attempt to handle constraints.
 874     if (!IA->getConstraintString().empty())
 875       return false;
 876
 877     unsigned ExtraInfo = 0;
 878     if (IA->hasSideEffects())
 879       ExtraInfo |= InlineAsm::Extra_HasSideEffects;
 880     if (IA->isAlignStack())
 881       ExtraInfo |= InlineAsm::Extra_IsAlignStack;
 882
 883     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
 884             TII.get(TargetOpcode::INLINEASM))
 885       .addExternalSymbol(IA->getAsmString().c_str())
 886       .addImm(ExtraInfo);
 887     return true;
 888   }
 889
 890   MachineModuleInfo &MMI = FuncInfo.MF->getMMI();
 891   ComputeUsesVAFloatArgument(*Call, &MMI);
 892
 893   // Handle intrinsic function calls.
 894   if (const auto *II = dyn_cast<IntrinsicInst>(Call))
 895     return SelectIntrinsicCall(II);
 896
 897   // Usually, it does not make sense to initialize a value,
 898   // make an unrelated function call and use the value, because
 899   // it tends to be spilled on the stack. So, we move the pointer
 900   // to the last local value to the beginning of the block, so that
 901   // all the values which have already been materialized,
 902   // appear after the call. It also makes sense to skip intrinsics
 903   // since they tend to be inlined.
 904   flushLocalValueMap();
 905
 906   return LowerCall(Call);
 907 }
 908
 909 bool FastISel::SelectIntrinsicCall(const IntrinsicInst *II) {
 910   switch (II->getIntrinsicID()) {
 911   default: break;
 912   // At -O0 we don't care about the lifetime intrinsics.
 913   case Intrinsic::lifetime_start:
 914   case Intrinsic::lifetime_end:
 915   // The donothing intrinsic does, well, nothing.
 916   case Intrinsic::donothing:
 917     return true;
 918   case Intrinsic::dbg_declare: {
 919     const DbgDeclareInst *DI = cast<DbgDeclareInst>(II);
 920     DIVariable DIVar(DI->getVariable());
 921     assert((!DIVar || DIVar.isVariable()) &&
 922            "Variable in DbgDeclareInst should be either null or a DIVariable.");
 923     if (!DIVar || !FuncInfo.MF->getMMI().hasDebugInfo()) {
 924       DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n");
 925       return true;
 926     }
 927
 928     const Value *Address = DI->getAddress();
 929     if (!Address || isa<UndefValue>(Address)) {
 930       DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n");
 931       return true;
 932     }
 933
 934     unsigned Offset = 0;
 935     Optional<MachineOperand> Op;
 936     if (const Argument *Arg = dyn_cast<Argument>(Address))
 937       // Some arguments' frame index is recorded during argument lowering.
 938       Offset = FuncInfo.getArgumentFrameIndex(Arg);
 939     if (Offset)
 940       Op = MachineOperand::CreateFI(Offset);
 941     if (!Op)
 942       if (unsigned Reg = lookUpRegForValue(Address))
 943         Op = MachineOperand::CreateReg(Reg, false);
 944
 945     // If we have a VLA that has a "use" in a metadata node that's then used
 946     // here but it has no other uses, then we have a problem. E.g.,
 947     //
 948     //   int foo (const int *x) {
 949     //     char a[*x];
 950     //     return 0;
 951     //   }
 952     //
 953     // If we assign 'a' a vreg and fast isel later on has to use the selection
 954     // DAG isel, it will want to copy the value to the vreg. However, there are
 955     // no uses, which goes counter to what selection DAG isel expects.
 956     if (!Op && !Address->use_empty() && isa<Instruction>(Address) &&
 957         (!isa<AllocaInst>(Address) ||
 958          !FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(Address))))
 959       Op = MachineOperand::CreateReg(FuncInfo.InitializeRegForValue(Address),
 960                                      false);
 961
 962     if (Op) {
 963       if (Op->isReg()) {
 964         Op->setIsDebug(true);
 965         BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
 966                 TII.get(TargetOpcode::DBG_VALUE), false, Op->getReg(), 0,
 967                 DI->getVariable());
 968       } else
 969         BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
 970                 TII.get(TargetOpcode::DBG_VALUE))
 971           .addOperand(*Op)
 972           .addImm(0)
 973           .addMetadata(DI->getVariable());
 974     } else {
 975       // We can't yet handle anything else here because it would require
 976       // generating code, thus altering codegen because of debug info.
 977       DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n");
 978     }
 979     return true;
 980   }
 981   case Intrinsic::dbg_value: {
 982     // This form of DBG_VALUE is target-independent.
 983     const DbgValueInst *DI = cast<DbgValueInst>(II);
 984     const MCInstrDesc &II = TII.get(TargetOpcode::DBG_VALUE);
 985     const Value *V = DI->getValue();
 986     if (!V) {
 987       // Currently the optimizer can produce this; insert an undef to
 988       // help debugging.  Probably the optimizer should not do this.
 989       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
 990         .addReg(0U).addImm(DI->getOffset())
 991         .addMetadata(DI->getVariable());
 992     } else if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
 993       if (CI->getBitWidth() > 64)
 994         BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
 995           .addCImm(CI).addImm(DI->getOffset())
 996           .addMetadata(DI->getVariable());
 997       else
 998         BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
 999           .addImm(CI->getZExtValue()).addImm(DI->getOffset())
1000           .addMetadata(DI->getVariable());
1001     } else if (const ConstantFP *CF = dyn_cast<ConstantFP>(V)) {
1002       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
1003         .addFPImm(CF).addImm(DI->getOffset())
1004         .addMetadata(DI->getVariable());
1005     } else if (unsigned Reg = lookUpRegForValue(V)) {
1006       // FIXME: This does not handle register-indirect values at offset 0.
1007       bool IsIndirect = DI->getOffset() != 0;
1008       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, IsIndirect,
1009               Reg, DI->getOffset(), DI->getVariable());
1010     } else {
1011       // We can't yet handle anything else here because it would require
1012       // generating code, thus altering codegen because of debug info.
1013       DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n");
1014     }
1015     return true;
1016   }
1017   case Intrinsic::objectsize: {
1018     ConstantInt *CI = cast<ConstantInt>(II->getArgOperand(1));
1019     unsigned long long Res = CI->isZero() ? -1ULL : 0;
1020     Constant *ResCI = ConstantInt::get(II->getType(), Res);
1021     unsigned ResultReg = getRegForValue(ResCI);
1022     if (ResultReg == 0)
1023       return false;
1024     UpdateValueMap(II, ResultReg);
1025     return true;
1026   }
1027   case Intrinsic::expect: {
1028     unsigned ResultReg = getRegForValue(II->getArgOperand(0));
1029     if (ResultReg == 0)
1030       return false;
1031     UpdateValueMap(II, ResultReg);
1032     return true;
1033   }
1034   case Intrinsic::experimental_stackmap:
1035     return SelectStackmap(II);
1036   }
1037
1038   return FastLowerIntrinsicCall(II);
1039 }
1040
1041 bool FastISel::SelectCast(const User *I, unsigned Opcode) {
1042   EVT SrcVT = TLI.getValueType(I->getOperand(0)->getType());
1043   EVT DstVT = TLI.getValueType(I->getType());
1044
1045   if (SrcVT == MVT::Other || !SrcVT.isSimple() ||
1046       DstVT == MVT::Other || !DstVT.isSimple())
1047     // Unhandled type. Halt "fast" selection and bail.
1048     return false;
1049
1050   // Check if the destination type is legal.
1051   if (!TLI.isTypeLegal(DstVT))
1052     return false;
1053
1054   // Check if the source operand is legal.
1055   if (!TLI.isTypeLegal(SrcVT))
1056     return false;
1057
1058   unsigned InputReg = getRegForValue(I->getOperand(0));
1059   if (!InputReg)
1060     // Unhandled operand.  Halt "fast" selection and bail.
1061     return false;
1062
1063   bool InputRegIsKill = hasTrivialKill(I->getOperand(0));
1064
1065   unsigned ResultReg = FastEmit_r(SrcVT.getSimpleVT(),
1066                                   DstVT.getSimpleVT(),
1067                                   Opcode,
1068                                   InputReg, InputRegIsKill);
1069   if (!ResultReg)
1070     return false;
1071
1072   UpdateValueMap(I, ResultReg);
1073   return true;
1074 }
1075
1076 bool FastISel::SelectBitCast(const User *I) {
1077   // If the bitcast doesn't change the type, just use the operand value.
1078   if (I->getType() == I->getOperand(0)->getType()) {
1079     unsigned Reg = getRegForValue(I->getOperand(0));
1080     if (Reg == 0)
1081       return false;
1082     UpdateValueMap(I, Reg);
1083     return true;
1084   }
1085
1086   // Bitcasts of other values become reg-reg copies or BITCAST operators.
1087   EVT SrcEVT = TLI.getValueType(I->getOperand(0)->getType());
1088   EVT DstEVT = TLI.getValueType(I->getType());
1089   if (SrcEVT == MVT::Other || DstEVT == MVT::Other ||
1090       !TLI.isTypeLegal(SrcEVT) || !TLI.isTypeLegal(DstEVT))
1091     // Unhandled type. Halt "fast" selection and bail.
1092     return false;
1093
1094   MVT SrcVT = SrcEVT.getSimpleVT();
1095   MVT DstVT = DstEVT.getSimpleVT();
1096   unsigned Op0 = getRegForValue(I->getOperand(0));
1097   if (Op0 == 0)
1098     // Unhandled operand. Halt "fast" selection and bail.
1099     return false;
1100
1101   bool Op0IsKill = hasTrivialKill(I->getOperand(0));
1102
1103   // First, try to perform the bitcast by inserting a reg-reg copy.
1104   unsigned ResultReg = 0;
1105   if (SrcVT == DstVT) {
1106     const TargetRegisterClass* SrcClass = TLI.getRegClassFor(SrcVT);
1107     const TargetRegisterClass* DstClass = TLI.getRegClassFor(DstVT);
1108     // Don't attempt a cross-class copy. It will likely fail.
1109     if (SrcClass == DstClass) {
1110       ResultReg = createResultReg(DstClass);
1111       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1112               TII.get(TargetOpcode::COPY), ResultReg).addReg(Op0);
1113     }
1114   }
1115
1116   // If the reg-reg copy failed, select a BITCAST opcode.
1117   if (!ResultReg)
1118     ResultReg = FastEmit_r(SrcVT, DstVT, ISD::BITCAST, Op0, Op0IsKill);
1119
1120   if (!ResultReg)
1121     return false;
1122
1123   UpdateValueMap(I, ResultReg);
1124   return true;
1125 }
1126
1127 bool
1128 FastISel::SelectInstruction(const Instruction *I) {
1129   // Just before the terminator instruction, insert instructions to
1130   // feed PHI nodes in successor blocks.
1131   if (isa<TerminatorInst>(I))
1132     if (!HandlePHINodesInSuccessorBlocks(I->getParent()))
1133       return false;
1134
1135   DbgLoc = I->getDebugLoc();
1136
1137   MachineBasicBlock::iterator SavedInsertPt = FuncInfo.InsertPt;
1138
1139   if (const CallInst *Call = dyn_cast<CallInst>(I)) {
1140     const Function *F = Call->getCalledFunction();
1141     LibFunc::Func Func;
1142
1143     // As a special case, don't handle calls to builtin library functions that
1144     // may be translated directly to target instructions.
1145     if (F && !F->hasLocalLinkage() && F->hasName() &&
1146         LibInfo->getLibFunc(F->getName(), Func) &&
1147         LibInfo->hasOptimizedCodeGen(Func))
1148       return false;
1149
1150     // Don't handle Intrinsic::trap if a trap funciton is specified.
1151     if (F && F->getIntrinsicID() == Intrinsic::trap &&
1152         !TM.Options.getTrapFunctionName().empty())
1153       return false;
1154   }
1155
1156   // First, try doing target-independent selection.
1157   if (SelectOperator(I, I->getOpcode())) {
1158     ++NumFastIselSuccessIndependent;
1159     DbgLoc = DebugLoc();
1160     return true;
1161   }
1162   // Remove dead code.  However, ignore call instructions since we've flushed
1163   // the local value map and recomputed the insert point.
1164   if (!isa<CallInst>(I)) {
1165     recomputeInsertPt();
1166     if (SavedInsertPt != FuncInfo.InsertPt)
1167       removeDeadCode(FuncInfo.InsertPt, SavedInsertPt);
1168   }
1169
1170   // Next, try calling the target to attempt to handle the instruction.
1171   SavedInsertPt = FuncInfo.InsertPt;
1172   if (TargetSelectInstruction(I)) {
1173     ++NumFastIselSuccessTarget;
1174     DbgLoc = DebugLoc();
1175     return true;
1176   }
1177   // Check for dead code and remove as necessary.
1178   recomputeInsertPt();
1179   if (SavedInsertPt != FuncInfo.InsertPt)
1180     removeDeadCode(FuncInfo.InsertPt, SavedInsertPt);
1181
1182   DbgLoc = DebugLoc();
1183   return false;
1184 }
1185
1186 /// FastEmitBranch - Emit an unconditional branch to the given block,
1187 /// unless it is the immediate (fall-through) successor, and update
1188 /// the CFG.
1189 void
1190 FastISel::FastEmitBranch(MachineBasicBlock *MSucc, DebugLoc DbgLoc) {
1191   if (FuncInfo.MBB->getBasicBlock()->size() > 1 &&
1192       FuncInfo.MBB->isLayoutSuccessor(MSucc)) {
1193     // For more accurate line information if this is the only instruction
1194     // in the block then emit it, otherwise we have the unconditional
1195     // fall-through case, which needs no instructions.
1196   } else {
1197     // The unconditional branch case.
1198     TII.InsertBranch(*FuncInfo.MBB, MSucc, nullptr,
1199                      SmallVector<MachineOperand, 0>(), DbgLoc);
1200   }
1201   uint32_t BranchWeight = 0;
1202   if (FuncInfo.BPI)
1203     BranchWeight = FuncInfo.BPI->getEdgeWeight(FuncInfo.MBB->getBasicBlock(),
1204                                                MSucc->getBasicBlock());
1205   FuncInfo.MBB->addSuccessor(MSucc, BranchWeight);
1206 }
1207
1208 /// SelectFNeg - Emit an FNeg operation.
1209 ///
1210 bool
1211 FastISel::SelectFNeg(const User *I) {
1212   unsigned OpReg = getRegForValue(BinaryOperator::getFNegArgument(I));
1213   if (OpReg == 0) return false;
1214
1215   bool OpRegIsKill = hasTrivialKill(I);
1216
1217   // If the target has ISD::FNEG, use it.
1218   EVT VT = TLI.getValueType(I->getType());
1219   unsigned ResultReg = FastEmit_r(VT.getSimpleVT(), VT.getSimpleVT(),
1220                                   ISD::FNEG, OpReg, OpRegIsKill);
1221   if (ResultReg != 0) {
1222     UpdateValueMap(I, ResultReg);
1223     return true;
1224   }
1225
1226   // Bitcast the value to integer, twiddle the sign bit with xor,
1227   // and then bitcast it back to floating-point.
1228   if (VT.getSizeInBits() > 64) return false;
1229   EVT IntVT = EVT::getIntegerVT(I->getContext(), VT.getSizeInBits());
1230   if (!TLI.isTypeLegal(IntVT))
1231     return false;
1232
1233   unsigned IntReg = FastEmit_r(VT.getSimpleVT(), IntVT.getSimpleVT(),
1234                                ISD::BITCAST, OpReg, OpRegIsKill);
1235   if (IntReg == 0)
1236     return false;
1237
1238   unsigned IntResultReg = FastEmit_ri_(IntVT.getSimpleVT(), ISD::XOR,
1239                                        IntReg, /*Kill=*/true,
1240                                        UINT64_C(1) << (VT.getSizeInBits()-1),
1241                                        IntVT.getSimpleVT());
1242   if (IntResultReg == 0)
1243     return false;
1244
1245   ResultReg = FastEmit_r(IntVT.getSimpleVT(), VT.getSimpleVT(),
1246                          ISD::BITCAST, IntResultReg, /*Kill=*/true);
1247   if (ResultReg == 0)
1248     return false;
1249
1250   UpdateValueMap(I, ResultReg);
1251   return true;
1252 }
1253
1254 bool
1255 FastISel::SelectExtractValue(const User *U) {
1256   const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(U);
1257   if (!EVI)
1258     return false;
1259
1260   // Make sure we only try to handle extracts with a legal result.  But also
1261   // allow i1 because it's easy.
1262   EVT RealVT = TLI.getValueType(EVI->getType(), /*AllowUnknown=*/true);
1263   if (!RealVT.isSimple())
1264     return false;
1265   MVT VT = RealVT.getSimpleVT();
1266   if (!TLI.isTypeLegal(VT) && VT != MVT::i1)
1267     return false;
1268
1269   const Value *Op0 = EVI->getOperand(0);
1270   Type *AggTy = Op0->getType();
1271
1272   // Get the base result register.
1273   unsigned ResultReg;
1274   DenseMap<const Value *, unsigned>::iterator I = FuncInfo.ValueMap.find(Op0);
1275   if (I != FuncInfo.ValueMap.end())
1276     ResultReg = I->second;
1277   else if (isa<Instruction>(Op0))
1278     ResultReg = FuncInfo.InitializeRegForValue(Op0);
1279   else
1280     return false; // fast-isel can't handle aggregate constants at the moment
1281
1282   // Get the actual result register, which is an offset from the base register.
1283   unsigned VTIndex = ComputeLinearIndex(AggTy, EVI->getIndices());
1284
1285   SmallVector<EVT, 4> AggValueVTs;
1286   ComputeValueVTs(TLI, AggTy, AggValueVTs);
1287
1288   for (unsigned i = 0; i < VTIndex; i++)
1289     ResultReg += TLI.getNumRegisters(FuncInfo.Fn->getContext(), AggValueVTs[i]);
1290
1291   UpdateValueMap(EVI, ResultReg);
1292   return true;
1293 }
1294
1295 bool
1296 FastISel::SelectOperator(const User *I, unsigned Opcode) {
1297   switch (Opcode) {
1298   case Instruction::Add:
1299     return SelectBinaryOp(I, ISD::ADD);
1300   case Instruction::FAdd:
1301     return SelectBinaryOp(I, ISD::FADD);
1302   case Instruction::Sub:
1303     return SelectBinaryOp(I, ISD::SUB);
1304   case Instruction::FSub:
1305     // FNeg is currently represented in LLVM IR as a special case of FSub.
1306     if (BinaryOperator::isFNeg(I))
1307       return SelectFNeg(I);
1308     return SelectBinaryOp(I, ISD::FSUB);
1309   case Instruction::Mul:
1310     return SelectBinaryOp(I, ISD::MUL);
1311   case Instruction::FMul:
1312     return SelectBinaryOp(I, ISD::FMUL);
1313   case Instruction::SDiv:
1314     return SelectBinaryOp(I, ISD::SDIV);
1315   case Instruction::UDiv:
1316     return SelectBinaryOp(I, ISD::UDIV);
1317   case Instruction::FDiv:
1318     return SelectBinaryOp(I, ISD::FDIV);
1319   case Instruction::SRem:
1320     return SelectBinaryOp(I, ISD::SREM);
1321   case Instruction::URem:
1322     return SelectBinaryOp(I, ISD::UREM);
1323   case Instruction::FRem:
1324     return SelectBinaryOp(I, ISD::FREM);
1325   case Instruction::Shl:
1326     return SelectBinaryOp(I, ISD::SHL);
1327   case Instruction::LShr:
1328     return SelectBinaryOp(I, ISD::SRL);
1329   case Instruction::AShr:
1330     return SelectBinaryOp(I, ISD::SRA);
1331   case Instruction::And:
1332     return SelectBinaryOp(I, ISD::AND);
1333   case Instruction::Or:
1334     return SelectBinaryOp(I, ISD::OR);
1335   case Instruction::Xor:
1336     return SelectBinaryOp(I, ISD::XOR);
1337
1338   case Instruction::GetElementPtr:
1339     return SelectGetElementPtr(I);
1340
1341   case Instruction::Br: {
1342     const BranchInst *BI = cast<BranchInst>(I);
1343
1344     if (BI->isUnconditional()) {
1345       const BasicBlock *LLVMSucc = BI->getSuccessor(0);
1346       MachineBasicBlock *MSucc = FuncInfo.MBBMap[LLVMSucc];
1347       FastEmitBranch(MSucc, BI->getDebugLoc());
1348       return true;
1349     }
1350
1351     // Conditional branches are not handed yet.
1352     // Halt "fast" selection and bail.
1353     return false;
1354   }
1355
1356   case Instruction::Unreachable:
1357     if (TM.Options.TrapUnreachable)
1358       return FastEmit_(MVT::Other, MVT::Other, ISD::TRAP) != 0;
1359     else
1360       return true;
1361
1362   case Instruction::Alloca:
1363     // FunctionLowering has the static-sized case covered.
1364     if (FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(I)))
1365       return true;
1366
1367     // Dynamic-sized alloca is not handled yet.
1368     return false;
1369
1370   case Instruction::Call:
1371     return SelectCall(I);
1372
1373   case Instruction::BitCast:
1374     return SelectBitCast(I);
1375
1376   case Instruction::FPToSI:
1377     return SelectCast(I, ISD::FP_TO_SINT);
1378   case Instruction::ZExt:
1379     return SelectCast(I, ISD::ZERO_EXTEND);
1380   case Instruction::SExt:
1381     return SelectCast(I, ISD::SIGN_EXTEND);
1382   case Instruction::Trunc:
1383     return SelectCast(I, ISD::TRUNCATE);
1384   case Instruction::SIToFP:
1385     return SelectCast(I, ISD::SINT_TO_FP);
1386
1387   case Instruction::IntToPtr: // Deliberate fall-through.
1388   case Instruction::PtrToInt: {
1389     EVT SrcVT = TLI.getValueType(I->getOperand(0)->getType());
1390     EVT DstVT = TLI.getValueType(I->getType());
1391     if (DstVT.bitsGT(SrcVT))
1392       return SelectCast(I, ISD::ZERO_EXTEND);
1393     if (DstVT.bitsLT(SrcVT))
1394       return SelectCast(I, ISD::TRUNCATE);
1395     unsigned Reg = getRegForValue(I->getOperand(0));
1396     if (Reg == 0) return false;
1397     UpdateValueMap(I, Reg);
1398     return true;
1399   }
1400
1401   case Instruction::ExtractValue:
1402     return SelectExtractValue(I);
1403
1404   case Instruction::PHI:
1405     llvm_unreachable("FastISel shouldn't visit PHI nodes!");
1406
1407   default:
1408     // Unhandled instruction. Halt "fast" selection and bail.
1409     return false;
1410   }
1411 }
1412
1413 FastISel::FastISel(FunctionLoweringInfo &funcInfo,
1414                    const TargetLibraryInfo *libInfo)
1415   : FuncInfo(funcInfo),
1416     MF(funcInfo.MF),
1417     MRI(FuncInfo.MF->getRegInfo()),
1418     MFI(*FuncInfo.MF->getFrameInfo()),
1419     MCP(*FuncInfo.MF->getConstantPool()),
1420     TM(FuncInfo.MF->getTarget()),
1421     DL(*TM.getDataLayout()),
1422     TII(*TM.getInstrInfo()),
1423     TLI(*TM.getTargetLowering()),
1424     TRI(*TM.getRegisterInfo()),
1425     LibInfo(libInfo) {
1426 }
1427
1428 FastISel::~FastISel() {}
1429
1430 bool FastISel::FastLowerArguments() {
1431   return false;
1432 }
1433
1434 bool FastISel::FastLowerCall(CallLoweringInfo &/*CLI*/) {
1435   return false;
1436 }
1437
1438 bool FastISel::FastLowerIntrinsicCall(const IntrinsicInst */*II*/) {
1439   return false;
1440 }
1441
1442 unsigned FastISel::FastEmit_(MVT, MVT,
1443                              unsigned) {
1444   return 0;
1445 }
1446
1447 unsigned FastISel::FastEmit_r(MVT, MVT,
1448                               unsigned,
1449                               unsigned /*Op0*/, bool /*Op0IsKill*/) {
1450   return 0;
1451 }
1452
1453 unsigned FastISel::FastEmit_rr(MVT, MVT,
1454                                unsigned,
1455                                unsigned /*Op0*/, bool /*Op0IsKill*/,
1456                                unsigned /*Op1*/, bool /*Op1IsKill*/) {
1457   return 0;
1458 }
1459
1460 unsigned FastISel::FastEmit_i(MVT, MVT, unsigned, uint64_t /*Imm*/) {
1461   return 0;
1462 }
1463
1464 unsigned FastISel::FastEmit_f(MVT, MVT,
1465                               unsigned, const ConstantFP * /*FPImm*/) {
1466   return 0;
1467 }
1468
1469 unsigned FastISel::FastEmit_ri(MVT, MVT,
1470                                unsigned,
1471                                unsigned /*Op0*/, bool /*Op0IsKill*/,
1472                                uint64_t /*Imm*/) {
1473   return 0;
1474 }
1475
1476 unsigned FastISel::FastEmit_rf(MVT, MVT,
1477                                unsigned,
1478                                unsigned /*Op0*/, bool /*Op0IsKill*/,
1479                                const ConstantFP * /*FPImm*/) {
1480   return 0;
1481 }
1482
1483 unsigned FastISel::FastEmit_rri(MVT, MVT,
1484                                 unsigned,
1485                                 unsigned /*Op0*/, bool /*Op0IsKill*/,
1486                                 unsigned /*Op1*/, bool /*Op1IsKill*/,
1487                                 uint64_t /*Imm*/) {
1488   return 0;
1489 }
1490
1491 /// FastEmit_ri_ - This method is a wrapper of FastEmit_ri. It first tries
1492 /// to emit an instruction with an immediate operand using FastEmit_ri.
1493 /// If that fails, it materializes the immediate into a register and try
1494 /// FastEmit_rr instead.
1495 unsigned FastISel::FastEmit_ri_(MVT VT, unsigned Opcode,
1496                                 unsigned Op0, bool Op0IsKill,
1497                                 uint64_t Imm, MVT ImmType) {
1498   // If this is a multiply by a power of two, emit this as a shift left.
1499   if (Opcode == ISD::MUL && isPowerOf2_64(Imm)) {
1500     Opcode = ISD::SHL;
1501     Imm = Log2_64(Imm);
1502   } else if (Opcode == ISD::UDIV && isPowerOf2_64(Imm)) {
1503     // div x, 8 -> srl x, 3
1504     Opcode = ISD::SRL;
1505     Imm = Log2_64(Imm);
1506   }
1507
1508   // Horrible hack (to be removed), check to make sure shift amounts are
1509   // in-range.
1510   if ((Opcode == ISD::SHL || Opcode == ISD::SRA || Opcode == ISD::SRL) &&
1511       Imm >= VT.getSizeInBits())
1512     return 0;
1513
1514   // First check if immediate type is legal. If not, we can't use the ri form.
1515   unsigned ResultReg = FastEmit_ri(VT, VT, Opcode, Op0, Op0IsKill, Imm);
1516   if (ResultReg != 0)
1517     return ResultReg;
1518   unsigned MaterialReg = FastEmit_i(ImmType, ImmType, ISD::Constant, Imm);
1519   if (MaterialReg == 0) {
1520     // This is a bit ugly/slow, but failing here means falling out of
1521     // fast-isel, which would be very slow.
1522     IntegerType *ITy = IntegerType::get(FuncInfo.Fn->getContext(),
1523                                               VT.getSizeInBits());
1524     MaterialReg = getRegForValue(ConstantInt::get(ITy, Imm));
1525     assert (MaterialReg != 0 && "Unable to materialize imm.");
1526     if (MaterialReg == 0) return 0;
1527   }
1528   return FastEmit_rr(VT, VT, Opcode,
1529                      Op0, Op0IsKill,
1530                      MaterialReg, /*Kill=*/true);
1531 }
1532
1533 unsigned FastISel::createResultReg(const TargetRegisterClass* RC) {
1534   return MRI.createVirtualRegister(RC);
1535 }
1536
1537 unsigned FastISel::constrainOperandRegClass(const MCInstrDesc &II,
1538                                             unsigned Op, unsigned OpNum) {
1539   if (TargetRegisterInfo::isVirtualRegister(Op)) {
1540     const TargetRegisterClass *RegClass =
1541         TII.getRegClass(II, OpNum, &TRI, *FuncInfo.MF);
1542     if (!MRI.constrainRegClass(Op, RegClass)) {
1543       // If it's not legal to COPY between the register classes, something
1544       // has gone very wrong before we got here.
1545       unsigned NewOp = createResultReg(RegClass);
1546       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1547               TII.get(TargetOpcode::COPY), NewOp).addReg(Op);
1548       return NewOp;
1549     }
1550   }
1551   return Op;
1552 }
1553
1554 unsigned FastISel::FastEmitInst_(unsigned MachineInstOpcode,
1555                                  const TargetRegisterClass* RC) {
1556   unsigned ResultReg = createResultReg(RC);
1557   const MCInstrDesc &II = TII.get(MachineInstOpcode);
1558
1559   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg);
1560   return ResultReg;
1561 }
1562
1563 unsigned FastISel::FastEmitInst_r(unsigned MachineInstOpcode,
1564                                   const TargetRegisterClass *RC,
1565                                   unsigned Op0, bool Op0IsKill) {
1566   const MCInstrDesc &II = TII.get(MachineInstOpcode);
1567
1568   unsigned ResultReg = createResultReg(RC);
1569   Op0 = constrainOperandRegClass(II, Op0, II.getNumDefs());
1570
1571   if (II.getNumDefs() >= 1)
1572     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
1573       .addReg(Op0, Op0IsKill * RegState::Kill);
1574   else {
1575     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
1576       .addReg(Op0, Op0IsKill * RegState::Kill);
1577     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1578             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
1579   }
1580
1581   return ResultReg;
1582 }
1583
1584 unsigned FastISel::FastEmitInst_rr(unsigned MachineInstOpcode,
1585                                    const TargetRegisterClass *RC,
1586                                    unsigned Op0, bool Op0IsKill,
1587                                    unsigned Op1, bool Op1IsKill) {
1588   const MCInstrDesc &II = TII.get(MachineInstOpcode);
1589
1590   unsigned ResultReg = createResultReg(RC);
1591   Op0 = constrainOperandRegClass(II, Op0, II.getNumDefs());
1592   Op1 = constrainOperandRegClass(II, Op1, II.getNumDefs() + 1);
1593
1594   if (II.getNumDefs() >= 1)
1595     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
1596       .addReg(Op0, Op0IsKill * RegState::Kill)
1597       .addReg(Op1, Op1IsKill * RegState::Kill);
1598   else {
1599     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
1600       .addReg(Op0, Op0IsKill * RegState::Kill)
1601       .addReg(Op1, Op1IsKill * RegState::Kill);
1602     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1603             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
1604   }
1605   return ResultReg;
1606 }
1607
1608 unsigned FastISel::FastEmitInst_rrr(unsigned MachineInstOpcode,
1609                                    const TargetRegisterClass *RC,
1610                                    unsigned Op0, bool Op0IsKill,
1611                                    unsigned Op1, bool Op1IsKill,
1612                                    unsigned Op2, bool Op2IsKill) {
1613   const MCInstrDesc &II = TII.get(MachineInstOpcode);
1614
1615   unsigned ResultReg = createResultReg(RC);
1616   Op0 = constrainOperandRegClass(II, Op0, II.getNumDefs());
1617   Op1 = constrainOperandRegClass(II, Op1, II.getNumDefs() + 1);
1618   Op2 = constrainOperandRegClass(II, Op2, II.getNumDefs() + 2);
1619
1620   if (II.getNumDefs() >= 1)
1621     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
1622       .addReg(Op0, Op0IsKill * RegState::Kill)
1623       .addReg(Op1, Op1IsKill * RegState::Kill)
1624       .addReg(Op2, Op2IsKill * RegState::Kill);
1625   else {
1626     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
1627       .addReg(Op0, Op0IsKill * RegState::Kill)
1628       .addReg(Op1, Op1IsKill * RegState::Kill)
1629       .addReg(Op2, Op2IsKill * RegState::Kill);
1630     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1631             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
1632   }
1633   return ResultReg;
1634 }
1635
1636 unsigned FastISel::FastEmitInst_ri(unsigned MachineInstOpcode,
1637                                    const TargetRegisterClass *RC,
1638                                    unsigned Op0, bool Op0IsKill,
1639                                    uint64_t Imm) {
1640   const MCInstrDesc &II = TII.get(MachineInstOpcode);
1641
1642   unsigned ResultReg = createResultReg(RC);
1643   RC = TII.getRegClass(II, II.getNumDefs(), &TRI, *FuncInfo.MF);
1644   MRI.constrainRegClass(Op0, RC);
1645
1646   if (II.getNumDefs() >= 1)
1647     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
1648       .addReg(Op0, Op0IsKill * RegState::Kill)
1649       .addImm(Imm);
1650   else {
1651     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
1652       .addReg(Op0, Op0IsKill * RegState::Kill)
1653       .addImm(Imm);
1654     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1655             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
1656   }
1657   return ResultReg;
1658 }
1659
1660 unsigned FastISel::FastEmitInst_rii(unsigned MachineInstOpcode,
1661                                    const TargetRegisterClass *RC,
1662                                    unsigned Op0, bool Op0IsKill,
1663                                    uint64_t Imm1, uint64_t Imm2) {
1664   const MCInstrDesc &II = TII.get(MachineInstOpcode);
1665
1666   unsigned ResultReg = createResultReg(RC);
1667   Op0 = constrainOperandRegClass(II, Op0, II.getNumDefs());
1668
1669   if (II.getNumDefs() >= 1)
1670     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
1671       .addReg(Op0, Op0IsKill * RegState::Kill)
1672       .addImm(Imm1)
1673       .addImm(Imm2);
1674   else {
1675     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
1676       .addReg(Op0, Op0IsKill * RegState::Kill)
1677       .addImm(Imm1)
1678       .addImm(Imm2);
1679     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1680             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
1681   }
1682   return ResultReg;
1683 }
1684
1685 unsigned FastISel::FastEmitInst_rf(unsigned MachineInstOpcode,
1686                                    const TargetRegisterClass *RC,
1687                                    unsigned Op0, bool Op0IsKill,
1688                                    const ConstantFP *FPImm) {
1689   const MCInstrDesc &II = TII.get(MachineInstOpcode);
1690
1691   unsigned ResultReg = createResultReg(RC);
1692   Op0 = constrainOperandRegClass(II, Op0, II.getNumDefs());
1693
1694   if (II.getNumDefs() >= 1)
1695     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
1696       .addReg(Op0, Op0IsKill * RegState::Kill)
1697       .addFPImm(FPImm);
1698   else {
1699     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
1700       .addReg(Op0, Op0IsKill * RegState::Kill)
1701       .addFPImm(FPImm);
1702     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1703             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
1704   }
1705   return ResultReg;
1706 }
1707
1708 unsigned FastISel::FastEmitInst_rri(unsigned MachineInstOpcode,
1709                                     const TargetRegisterClass *RC,
1710                                     unsigned Op0, bool Op0IsKill,
1711                                     unsigned Op1, bool Op1IsKill,
1712                                     uint64_t Imm) {
1713   const MCInstrDesc &II = TII.get(MachineInstOpcode);
1714
1715   unsigned ResultReg = createResultReg(RC);
1716   Op0 = constrainOperandRegClass(II, Op0, II.getNumDefs());
1717   Op1 = constrainOperandRegClass(II, Op1, II.getNumDefs() + 1);
1718
1719   if (II.getNumDefs() >= 1)
1720     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
1721       .addReg(Op0, Op0IsKill * RegState::Kill)
1722       .addReg(Op1, Op1IsKill * RegState::Kill)
1723       .addImm(Imm);
1724   else {
1725     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
1726       .addReg(Op0, Op0IsKill * RegState::Kill)
1727       .addReg(Op1, Op1IsKill * RegState::Kill)
1728       .addImm(Imm);
1729     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1730             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
1731   }
1732   return ResultReg;
1733 }
1734
1735 unsigned FastISel::FastEmitInst_rrii(unsigned MachineInstOpcode,
1736                                      const TargetRegisterClass *RC,
1737                                      unsigned Op0, bool Op0IsKill,
1738                                      unsigned Op1, bool Op1IsKill,
1739                                      uint64_t Imm1, uint64_t Imm2) {
1740   const MCInstrDesc &II = TII.get(MachineInstOpcode);
1741
1742   unsigned ResultReg = createResultReg(RC);
1743   Op0 = constrainOperandRegClass(II, Op0, II.getNumDefs());
1744   Op1 = constrainOperandRegClass(II, Op1, II.getNumDefs() + 1);
1745
1746   if (II.getNumDefs() >= 1)
1747     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
1748       .addReg(Op0, Op0IsKill * RegState::Kill)
1749       .addReg(Op1, Op1IsKill * RegState::Kill)
1750       .addImm(Imm1).addImm(Imm2);
1751   else {
1752     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
1753       .addReg(Op0, Op0IsKill * RegState::Kill)
1754       .addReg(Op1, Op1IsKill * RegState::Kill)
1755       .addImm(Imm1).addImm(Imm2);
1756     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1757             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
1758   }
1759   return ResultReg;
1760 }
1761
1762 unsigned FastISel::FastEmitInst_i(unsigned MachineInstOpcode,
1763                                   const TargetRegisterClass *RC,
1764                                   uint64_t Imm) {
1765   unsigned ResultReg = createResultReg(RC);
1766   const MCInstrDesc &II = TII.get(MachineInstOpcode);
1767
1768   if (II.getNumDefs() >= 1)
1769     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg).addImm(Imm);
1770   else {
1771     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II).addImm(Imm);
1772     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1773             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
1774   }
1775   return ResultReg;
1776 }
1777
1778 unsigned FastISel::FastEmitInst_ii(unsigned MachineInstOpcode,
1779                                   const TargetRegisterClass *RC,
1780                                   uint64_t Imm1, uint64_t Imm2) {
1781   unsigned ResultReg = createResultReg(RC);
1782   const MCInstrDesc &II = TII.get(MachineInstOpcode);
1783
1784   if (II.getNumDefs() >= 1)
1785     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
1786       .addImm(Imm1).addImm(Imm2);
1787   else {
1788     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II).addImm(Imm1).addImm(Imm2);
1789     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1790             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
1791   }
1792   return ResultReg;
1793 }
1794
1795 unsigned FastISel::FastEmitInst_extractsubreg(MVT RetVT,
1796                                               unsigned Op0, bool Op0IsKill,
1797                                               uint32_t Idx) {
1798   unsigned ResultReg = createResultReg(TLI.getRegClassFor(RetVT));
1799   assert(TargetRegisterInfo::isVirtualRegister(Op0) &&
1800          "Cannot yet extract from physregs");
1801   const TargetRegisterClass *RC = MRI.getRegClass(Op0);
1802   MRI.constrainRegClass(Op0, TRI.getSubClassWithSubReg(RC, Idx));
1803   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt,
1804           DbgLoc, TII.get(TargetOpcode::COPY), ResultReg)
1805     .addReg(Op0, getKillRegState(Op0IsKill), Idx);
1806   return ResultReg;
1807 }
1808
1809 /// FastEmitZExtFromI1 - Emit MachineInstrs to compute the value of Op
1810 /// with all but the least significant bit set to zero.
1811 unsigned FastISel::FastEmitZExtFromI1(MVT VT, unsigned Op0, bool Op0IsKill) {
1812   return FastEmit_ri(VT, VT, ISD::AND, Op0, Op0IsKill, 1);
1813 }
1814
1815 /// HandlePHINodesInSuccessorBlocks - Handle PHI nodes in successor blocks.
1816 /// Emit code to ensure constants are copied into registers when needed.
1817 /// Remember the virtual registers that need to be added to the Machine PHI
1818 /// nodes as input.  We cannot just directly add them, because expansion
1819 /// might result in multiple MBB's for one BB.  As such, the start of the
1820 /// BB might correspond to a different MBB than the end.
1821 bool FastISel::HandlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB) {
1822   const TerminatorInst *TI = LLVMBB->getTerminator();
1823
1824   SmallPtrSet<MachineBasicBlock *, 4> SuccsHandled;
1825   unsigned OrigNumPHINodesToUpdate = FuncInfo.PHINodesToUpdate.size();
1826
1827   // Check successor nodes' PHI nodes that expect a constant to be available
1828   // from this block.
1829   for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) {
1830     const BasicBlock *SuccBB = TI->getSuccessor(succ);
1831     if (!isa<PHINode>(SuccBB->begin())) continue;
1832     MachineBasicBlock *SuccMBB = FuncInfo.MBBMap[SuccBB];
1833
1834     // If this terminator has multiple identical successors (common for
1835     // switches), only handle each succ once.
1836     if (!SuccsHandled.insert(SuccMBB)) continue;
1837
1838     MachineBasicBlock::iterator MBBI = SuccMBB->begin();
1839
1840     // At this point we know that there is a 1-1 correspondence between LLVM PHI
1841     // nodes and Machine PHI nodes, but the incoming operands have not been
1842     // emitted yet.
1843     for (BasicBlock::const_iterator I = SuccBB->begin();
1844          const PHINode *PN = dyn_cast<PHINode>(I); ++I) {
1845
1846       // Ignore dead phi's.
1847       if (PN->use_empty()) continue;
1848
1849       // Only handle legal types. Two interesting things to note here. First,
1850       // by bailing out early, we may leave behind some dead instructions,
1851       // since SelectionDAG's HandlePHINodesInSuccessorBlocks will insert its
1852       // own moves. Second, this check is necessary because FastISel doesn't
1853       // use CreateRegs to create registers, so it always creates
1854       // exactly one register for each non-void instruction.
1855       EVT VT = TLI.getValueType(PN->getType(), /*AllowUnknown=*/true);
1856       if (VT == MVT::Other || !TLI.isTypeLegal(VT)) {
1857         // Handle integer promotions, though, because they're common and easy.
1858         if (VT == MVT::i1 || VT == MVT::i8 || VT == MVT::i16)
1859           VT = TLI.getTypeToTransformTo(LLVMBB->getContext(), VT);
1860         else {
1861           FuncInfo.PHINodesToUpdate.resize(OrigNumPHINodesToUpdate);
1862           return false;
1863         }
1864       }
1865
1866       const Value *PHIOp = PN->getIncomingValueForBlock(LLVMBB);
1867
1868       // Set the DebugLoc for the copy. Prefer the location of the operand
1869       // if there is one; use the location of the PHI otherwise.
1870       DbgLoc = PN->getDebugLoc();
1871       if (const Instruction *Inst = dyn_cast<Instruction>(PHIOp))
1872         DbgLoc = Inst->getDebugLoc();
1873
1874       unsigned Reg = getRegForValue(PHIOp);
1875       if (Reg == 0) {
1876         FuncInfo.PHINodesToUpdate.resize(OrigNumPHINodesToUpdate);
1877         return false;
1878       }
1879       FuncInfo.PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg));
1880       DbgLoc = DebugLoc();
1881     }
1882   }
1883
1884   return true;
1885 }
1886
1887 bool FastISel::tryToFoldLoad(const LoadInst *LI, const Instruction *FoldInst) {
1888   assert(LI->hasOneUse() &&
1889       "tryToFoldLoad expected a LoadInst with a single use");
1890   // We know that the load has a single use, but don't know what it is.  If it
1891   // isn't one of the folded instructions, then we can't succeed here.  Handle
1892   // this by scanning the single-use users of the load until we get to FoldInst.
1893   unsigned MaxUsers = 6;  // Don't scan down huge single-use chains of instrs.
1894
1895   const Instruction *TheUser = LI->user_back();
1896   while (TheUser != FoldInst &&   // Scan up until we find FoldInst.
1897          // Stay in the right block.
1898          TheUser->getParent() == FoldInst->getParent() &&
1899          --MaxUsers) {  // Don't scan too far.
1900     // If there are multiple or no uses of this instruction, then bail out.
1901     if (!TheUser->hasOneUse())
1902       return false;
1903
1904     TheUser = TheUser->user_back();
1905   }
1906
1907   // If we didn't find the fold instruction, then we failed to collapse the
1908   // sequence.
1909   if (TheUser != FoldInst)
1910     return false;
1911
1912   // Don't try to fold volatile loads.  Target has to deal with alignment
1913   // constraints.
1914   if (LI->isVolatile())
1915     return false;
1916
1917   // Figure out which vreg this is going into.  If there is no assigned vreg yet
1918   // then there actually was no reference to it.  Perhaps the load is referenced
1919   // by a dead instruction.
1920   unsigned LoadReg = getRegForValue(LI);
1921   if (LoadReg == 0)
1922     return false;
1923
1924   // We can't fold if this vreg has no uses or more than one use.  Multiple uses
1925   // may mean that the instruction got lowered to multiple MIs, or the use of
1926   // the loaded value ended up being multiple operands of the result.
1927   if (!MRI.hasOneUse(LoadReg))
1928     return false;
1929
1930   MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(LoadReg);
1931   MachineInstr *User = RI->getParent();
1932
1933   // Set the insertion point properly.  Folding the load can cause generation of
1934   // other random instructions (like sign extends) for addressing modes; make
1935   // sure they get inserted in a logical place before the new instruction.
1936   FuncInfo.InsertPt = User;
1937   FuncInfo.MBB = User->getParent();
1938
1939   // Ask the target to try folding the load.
1940   return tryToFoldLoadIntoMI(User, RI.getOperandNo(), LI);
1941 }
1942
1943 bool FastISel::canFoldAddIntoGEP(const User *GEP, const Value *Add) {
1944   // Must be an add.
1945   if (!isa<AddOperator>(Add))
1946     return false;
1947   // Type size needs to match.
1948   if (DL.getTypeSizeInBits(GEP->getType()) !=
1949       DL.getTypeSizeInBits(Add->getType()))
1950     return false;
1951   // Must be in the same basic block.
1952   if (isa<Instruction>(Add) &&
1953       FuncInfo.MBBMap[cast<Instruction>(Add)->getParent()] != FuncInfo.MBB)
1954     return false;
1955   // Must have a constant operand.
1956   return isa<ConstantInt>(cast<AddOperator>(Add)->getOperand(1));
1957 }
1958
1959 MachineMemOperand *
1960 FastISel::createMachineMemOperandFor(const Instruction *I) const {
1961   const Value *Ptr;
1962   Type *ValTy;
1963   unsigned Alignment;
1964   unsigned Flags;
1965   bool IsVolatile;
1966
1967   if (const auto *LI = dyn_cast<LoadInst>(I)) {
1968     Alignment = LI->getAlignment();
1969     IsVolatile = LI->isVolatile();
1970     Flags = MachineMemOperand::MOLoad;
1971     Ptr = LI->getPointerOperand();
1972     ValTy = LI->getType();
1973   } else if (const auto *SI = dyn_cast<StoreInst>(I)) {
1974     Alignment = SI->getAlignment();
1975     IsVolatile = SI->isVolatile();
1976     Flags = MachineMemOperand::MOStore;
1977     Ptr = SI->getPointerOperand();
1978     ValTy = SI->getValueOperand()->getType();
1979   } else {
1980     return nullptr;
1981   }
1982
1983   bool IsNonTemporal = I->getMetadata("nontemporal") != nullptr;
1984   bool IsInvariant = I->getMetadata("invariant.load") != nullptr;
1985   const MDNode *TBAAInfo = I->getMetadata(LLVMContext::MD_tbaa);
1986   const MDNode *Ranges = I->getMetadata(LLVMContext::MD_range);
1987
1988   if (Alignment == 0)  // Ensure that codegen never sees alignment 0.
1989     Alignment = DL.getABITypeAlignment(ValTy);
1990
1991   unsigned Size = TM.getDataLayout()->getTypeStoreSize(ValTy);
1992
1993   if (IsVolatile)
1994     Flags |= MachineMemOperand::MOVolatile;
1995   if (IsNonTemporal)
1996     Flags |= MachineMemOperand::MONonTemporal;
1997   if (IsInvariant)
1998     Flags |= MachineMemOperand::MOInvariant;
1999
2000   return FuncInfo.MF->getMachineMemOperand(MachinePointerInfo(Ptr), Flags, Size,
2001                                            Alignment, TBAAInfo, Ranges);
2002 }