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