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 stackmap or patchpoint intrinsic call's live variable operands
 565 /// to a stackmap or patchpoint machine instruction.
 566 bool FastISel::addStackMapLiveVars(SmallVectorImpl<MachineOperand> &Ops,
 567                                    const CallInst *CI, unsigned StartIdx) {
 568   for (unsigned i = StartIdx, e = CI->getNumArgOperands(); i != e; ++i) {
 569     Value *Val = CI->getArgOperand(i);
 570     // Check for constants and encode them with a StackMaps::ConstantOp prefix.
 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       // Values coming from a stack location also require a sepcial encoding,
 579       // but that is added later on by the target specific frame index
 580       // elimination implementation.
 581       auto SI = FuncInfo.StaticAllocaMap.find(AI);
 582       if (SI != FuncInfo.StaticAllocaMap.end())
 583         Ops.push_back(MachineOperand::CreateFI(SI->second));
 584       else
 585         return false;
 586     } else {
 587       unsigned Reg = getRegForValue(Val);
 588       if (Reg == 0)
 589         return false;
 590       Ops.push_back(MachineOperand::CreateReg(Reg, /*IsDef=*/false));
 591     }
 592   }
 593
 594   return true;
 595 }
 596
 597 bool FastISel::SelectStackmap(const CallInst *I) {
 598   // void @llvm.experimental.stackmap(i64 <id>, i32 <numShadowBytes>,
 599   //                                  [live variables...])
 600   assert(I->getCalledFunction()->getReturnType()->isVoidTy() &&
 601          "Stackmap cannot return a value.");
 602
 603   // The stackmap intrinsic only records the live variables (the arguments
 604   // passed to it) and emits NOPS (if requested). Unlike the patchpoint
 605   // intrinsic, this won't be lowered to a function call. This means we don't
 606   // have to worry about calling conventions and target-specific lowering code.
 607   // Instead we perform the call lowering right here.
 608   //
 609   // CALLSEQ_START(0)
 610   // STACKMAP(id, nbytes, ...)
 611   // CALLSEQ_END(0, 0)
 612   //
 613   SmallVector<MachineOperand, 32> Ops;
 614
 615   // Add the <id> and <numBytes> constants.
 616   assert(isa<ConstantInt>(I->getOperand(PatchPointOpers::IDPos)) &&
 617          "Expected a constant integer.");
 618   const auto *ID = cast<ConstantInt>(I->getOperand(PatchPointOpers::IDPos));
 619   Ops.push_back(MachineOperand::CreateImm(ID->getZExtValue()));
 620
 621   assert(isa<ConstantInt>(I->getOperand(PatchPointOpers::NBytesPos)) &&
 622          "Expected a constant integer.");
 623   const auto *NumBytes =
 624     cast<ConstantInt>(I->getOperand(PatchPointOpers::NBytesPos));
 625   Ops.push_back(MachineOperand::CreateImm(NumBytes->getZExtValue()));
 626
 627   // Push live variables for the stack map (skipping the first two arguments
 628   // <id> and <numBytes>).
 629   if (!addStackMapLiveVars(Ops, I, 2))
 630     return false;
 631
 632   // We are not adding any register mask info here, because the stackmap doesn't
 633   // clobber anything.
 634
 635   // Add scratch registers as implicit def and early clobber.
 636   CallingConv::ID CC = I->getCallingConv();
 637   const MCPhysReg *ScratchRegs = TLI.getScratchRegisters(CC);
 638   for (unsigned i = 0; ScratchRegs[i]; ++i)
 639     Ops.push_back(MachineOperand::CreateReg(
 640       ScratchRegs[i], /*IsDef=*/true, /*IsImp=*/true, /*IsKill=*/false,
 641       /*IsDead=*/false, /*IsUndef=*/false, /*IsEarlyClobber=*/true));
 642
 643   // Issue CALLSEQ_START
 644   unsigned AdjStackDown = TII.getCallFrameSetupOpcode();
 645   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AdjStackDown))
 646     .addImm(0);
 647
 648   // Issue STACKMAP.
 649   MachineInstrBuilder MIB = BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
 650                                     TII.get(TargetOpcode::STACKMAP));
 651   for (auto const &MO : Ops)
 652     MIB.addOperand(MO);
 653
 654   // Issue CALLSEQ_END
 655   unsigned AdjStackUp = TII.getCallFrameDestroyOpcode();
 656   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AdjStackUp))
 657     .addImm(0).addImm(0);
 658
 659   // Inform the Frame Information that we have a stackmap in this function.
 660   FuncInfo.MF->getFrameInfo()->setHasStackMap();
 661
 662   return true;
 663 }
 664
 665 bool FastISel::SelectCall(const User *I) {
 666   const CallInst *Call = cast<CallInst>(I);
 667
 668   // Handle simple inline asms.
 669   if (const InlineAsm *IA = dyn_cast<InlineAsm>(Call->getCalledValue())) {
 670     // Don't attempt to handle constraints.
 671     if (!IA->getConstraintString().empty())
 672       return false;
 673
 674     unsigned ExtraInfo = 0;
 675     if (IA->hasSideEffects())
 676       ExtraInfo |= InlineAsm::Extra_HasSideEffects;
 677     if (IA->isAlignStack())
 678       ExtraInfo |= InlineAsm::Extra_IsAlignStack;
 679
 680     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
 681             TII.get(TargetOpcode::INLINEASM))
 682       .addExternalSymbol(IA->getAsmString().c_str())
 683       .addImm(ExtraInfo);
 684     return true;
 685   }
 686
 687   MachineModuleInfo &MMI = FuncInfo.MF->getMMI();
 688   ComputeUsesVAFloatArgument(*Call, &MMI);
 689
 690   // Handle intrinsic function calls.
 691   if (const auto *II = dyn_cast<IntrinsicInst>(Call))
 692     return SelectIntrinsicCall(II);
 693
 694   // Usually, it does not make sense to initialize a value,
 695   // make an unrelated function call and use the value, because
 696   // it tends to be spilled on the stack. So, we move the pointer
 697   // to the last local value to the beginning of the block, so that
 698   // all the values which have already been materialized,
 699   // appear after the call. It also makes sense to skip intrinsics
 700   // since they tend to be inlined.
 701   flushLocalValueMap();
 702
 703   // An arbitrary call. Bail.
 704   return false;
 705 }
 706
 707 bool FastISel::SelectIntrinsicCall(const IntrinsicInst *II) {
 708   switch (II->getIntrinsicID()) {
 709   default: break;
 710   // At -O0 we don't care about the lifetime intrinsics.
 711   case Intrinsic::lifetime_start:
 712   case Intrinsic::lifetime_end:
 713   // The donothing intrinsic does, well, nothing.
 714   case Intrinsic::donothing:
 715     return true;
 716   case Intrinsic::dbg_declare: {
 717     const DbgDeclareInst *DI = cast<DbgDeclareInst>(II);
 718     DIVariable DIVar(DI->getVariable());
 719     assert((!DIVar || DIVar.isVariable()) &&
 720            "Variable in DbgDeclareInst should be either null or a DIVariable.");
 721     if (!DIVar || !FuncInfo.MF->getMMI().hasDebugInfo()) {
 722       DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n");
 723       return true;
 724     }
 725
 726     const Value *Address = DI->getAddress();
 727     if (!Address || isa<UndefValue>(Address)) {
 728       DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n");
 729       return true;
 730     }
 731
 732     unsigned Offset = 0;
 733     Optional<MachineOperand> Op;
 734     if (const Argument *Arg = dyn_cast<Argument>(Address))
 735       // Some arguments' frame index is recorded during argument lowering.
 736       Offset = FuncInfo.getArgumentFrameIndex(Arg);
 737     if (Offset)
 738       Op = MachineOperand::CreateFI(Offset);
 739     if (!Op)
 740       if (unsigned Reg = lookUpRegForValue(Address))
 741         Op = MachineOperand::CreateReg(Reg, false);
 742
 743     // If we have a VLA that has a "use" in a metadata node that's then used
 744     // here but it has no other uses, then we have a problem. E.g.,
 745     //
 746     //   int foo (const int *x) {
 747     //     char a[*x];
 748     //     return 0;
 749     //   }
 750     //
 751     // If we assign 'a' a vreg and fast isel later on has to use the selection
 752     // DAG isel, it will want to copy the value to the vreg. However, there are
 753     // no uses, which goes counter to what selection DAG isel expects.
 754     if (!Op && !Address->use_empty() && isa<Instruction>(Address) &&
 755         (!isa<AllocaInst>(Address) ||
 756          !FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(Address))))
 757       Op = MachineOperand::CreateReg(FuncInfo.InitializeRegForValue(Address),
 758                                      false);
 759
 760     if (Op) {
 761       if (Op->isReg()) {
 762         Op->setIsDebug(true);
 763         BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
 764                 TII.get(TargetOpcode::DBG_VALUE), false, Op->getReg(), 0,
 765                 DI->getVariable());
 766       } else
 767         BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
 768                 TII.get(TargetOpcode::DBG_VALUE))
 769           .addOperand(*Op)
 770           .addImm(0)
 771           .addMetadata(DI->getVariable());
 772     } else {
 773       // We can't yet handle anything else here because it would require
 774       // generating code, thus altering codegen because of debug info.
 775       DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n");
 776     }
 777     return true;
 778   }
 779   case Intrinsic::dbg_value: {
 780     // This form of DBG_VALUE is target-independent.
 781     const DbgValueInst *DI = cast<DbgValueInst>(II);
 782     const MCInstrDesc &II = TII.get(TargetOpcode::DBG_VALUE);
 783     const Value *V = DI->getValue();
 784     if (!V) {
 785       // Currently the optimizer can produce this; insert an undef to
 786       // help debugging.  Probably the optimizer should not do this.
 787       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
 788         .addReg(0U).addImm(DI->getOffset())
 789         .addMetadata(DI->getVariable());
 790     } else if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
 791       if (CI->getBitWidth() > 64)
 792         BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
 793           .addCImm(CI).addImm(DI->getOffset())
 794           .addMetadata(DI->getVariable());
 795       else
 796         BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
 797           .addImm(CI->getZExtValue()).addImm(DI->getOffset())
 798           .addMetadata(DI->getVariable());
 799     } else if (const ConstantFP *CF = dyn_cast<ConstantFP>(V)) {
 800       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
 801         .addFPImm(CF).addImm(DI->getOffset())
 802         .addMetadata(DI->getVariable());
 803     } else if (unsigned Reg = lookUpRegForValue(V)) {
 804       // FIXME: This does not handle register-indirect values at offset 0.
 805       bool IsIndirect = DI->getOffset() != 0;
 806       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, IsIndirect,
 807               Reg, DI->getOffset(), DI->getVariable());
 808     } else {
 809       // We can't yet handle anything else here because it would require
 810       // generating code, thus altering codegen because of debug info.
 811       DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n");
 812     }
 813     return true;
 814   }
 815   case Intrinsic::objectsize: {
 816     ConstantInt *CI = cast<ConstantInt>(II->getArgOperand(1));
 817     unsigned long long Res = CI->isZero() ? -1ULL : 0;
 818     Constant *ResCI = ConstantInt::get(II->getType(), Res);
 819     unsigned ResultReg = getRegForValue(ResCI);
 820     if (ResultReg == 0)
 821       return false;
 822     UpdateValueMap(II, ResultReg);
 823     return true;
 824   }
 825   case Intrinsic::expect: {
 826     unsigned ResultReg = getRegForValue(II->getArgOperand(0));
 827     if (ResultReg == 0)
 828       return false;
 829     UpdateValueMap(II, ResultReg);
 830     return true;
 831   }
 832   case Intrinsic::experimental_stackmap:
 833     return SelectStackmap(II);
 834   }
 835
 836   return FastLowerIntrinsicCall(II);
 837 }
 838
 839 bool FastISel::SelectCast(const User *I, unsigned Opcode) {
 840   EVT SrcVT = TLI.getValueType(I->getOperand(0)->getType());
 841   EVT DstVT = TLI.getValueType(I->getType());
 842
 843   if (SrcVT == MVT::Other || !SrcVT.isSimple() ||
 844       DstVT == MVT::Other || !DstVT.isSimple())
 845     // Unhandled type. Halt "fast" selection and bail.
 846     return false;
 847
 848   // Check if the destination type is legal.
 849   if (!TLI.isTypeLegal(DstVT))
 850     return false;
 851
 852   // Check if the source operand is legal.
 853   if (!TLI.isTypeLegal(SrcVT))
 854     return false;
 855
 856   unsigned InputReg = getRegForValue(I->getOperand(0));
 857   if (!InputReg)
 858     // Unhandled operand.  Halt "fast" selection and bail.
 859     return false;
 860
 861   bool InputRegIsKill = hasTrivialKill(I->getOperand(0));
 862
 863   unsigned ResultReg = FastEmit_r(SrcVT.getSimpleVT(),
 864                                   DstVT.getSimpleVT(),
 865                                   Opcode,
 866                                   InputReg, InputRegIsKill);
 867   if (!ResultReg)
 868     return false;
 869
 870   UpdateValueMap(I, ResultReg);
 871   return true;
 872 }
 873
 874 bool FastISel::SelectBitCast(const User *I) {
 875   // If the bitcast doesn't change the type, just use the operand value.
 876   if (I->getType() == I->getOperand(0)->getType()) {
 877     unsigned Reg = getRegForValue(I->getOperand(0));
 878     if (Reg == 0)
 879       return false;
 880     UpdateValueMap(I, Reg);
 881     return true;
 882   }
 883
 884   // Bitcasts of other values become reg-reg copies or BITCAST operators.
 885   EVT SrcEVT = TLI.getValueType(I->getOperand(0)->getType());
 886   EVT DstEVT = TLI.getValueType(I->getType());
 887   if (SrcEVT == MVT::Other || DstEVT == MVT::Other ||
 888       !TLI.isTypeLegal(SrcEVT) || !TLI.isTypeLegal(DstEVT))
 889     // Unhandled type. Halt "fast" selection and bail.
 890     return false;
 891
 892   MVT SrcVT = SrcEVT.getSimpleVT();
 893   MVT DstVT = DstEVT.getSimpleVT();
 894   unsigned Op0 = getRegForValue(I->getOperand(0));
 895   if (Op0 == 0)
 896     // Unhandled operand. Halt "fast" selection and bail.
 897     return false;
 898
 899   bool Op0IsKill = hasTrivialKill(I->getOperand(0));
 900
 901   // First, try to perform the bitcast by inserting a reg-reg copy.
 902   unsigned ResultReg = 0;
 903   if (SrcVT == DstVT) {
 904     const TargetRegisterClass* SrcClass = TLI.getRegClassFor(SrcVT);
 905     const TargetRegisterClass* DstClass = TLI.getRegClassFor(DstVT);
 906     // Don't attempt a cross-class copy. It will likely fail.
 907     if (SrcClass == DstClass) {
 908       ResultReg = createResultReg(DstClass);
 909       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
 910               TII.get(TargetOpcode::COPY), ResultReg).addReg(Op0);
 911     }
 912   }
 913
 914   // If the reg-reg copy failed, select a BITCAST opcode.
 915   if (!ResultReg)
 916     ResultReg = FastEmit_r(SrcVT, DstVT, ISD::BITCAST, Op0, Op0IsKill);
 917
 918   if (!ResultReg)
 919     return false;
 920
 921   UpdateValueMap(I, ResultReg);
 922   return true;
 923 }
 924
 925 bool
 926 FastISel::SelectInstruction(const Instruction *I) {
 927   // Just before the terminator instruction, insert instructions to
 928   // feed PHI nodes in successor blocks.
 929   if (isa<TerminatorInst>(I))
 930     if (!HandlePHINodesInSuccessorBlocks(I->getParent()))
 931       return false;
 932
 933   DbgLoc = I->getDebugLoc();
 934
 935   MachineBasicBlock::iterator SavedInsertPt = FuncInfo.InsertPt;
 936
 937   if (const CallInst *Call = dyn_cast<CallInst>(I)) {
 938     const Function *F = Call->getCalledFunction();
 939     LibFunc::Func Func;
 940
 941     // As a special case, don't handle calls to builtin library functions that
 942     // may be translated directly to target instructions.
 943     if (F && !F->hasLocalLinkage() && F->hasName() &&
 944         LibInfo->getLibFunc(F->getName(), Func) &&
 945         LibInfo->hasOptimizedCodeGen(Func))
 946       return false;
 947
 948     // Don't handle Intrinsic::trap if a trap funciton is specified.
 949     if (F && F->getIntrinsicID() == Intrinsic::trap &&
 950         !TM.Options.getTrapFunctionName().empty())
 951       return false;
 952   }
 953
 954   // First, try doing target-independent selection.
 955   if (SelectOperator(I, I->getOpcode())) {
 956     ++NumFastIselSuccessIndependent;
 957     DbgLoc = DebugLoc();
 958     return true;
 959   }
 960   // Remove dead code.  However, ignore call instructions since we've flushed
 961   // the local value map and recomputed the insert point.
 962   if (!isa<CallInst>(I)) {
 963     recomputeInsertPt();
 964     if (SavedInsertPt != FuncInfo.InsertPt)
 965       removeDeadCode(FuncInfo.InsertPt, SavedInsertPt);
 966   }
 967
 968   // Next, try calling the target to attempt to handle the instruction.
 969   SavedInsertPt = FuncInfo.InsertPt;
 970   if (TargetSelectInstruction(I)) {
 971     ++NumFastIselSuccessTarget;
 972     DbgLoc = DebugLoc();
 973     return true;
 974   }
 975   // Check for dead code and remove as necessary.
 976   recomputeInsertPt();
 977   if (SavedInsertPt != FuncInfo.InsertPt)
 978     removeDeadCode(FuncInfo.InsertPt, SavedInsertPt);
 979
 980   DbgLoc = DebugLoc();
 981   return false;
 982 }
 983
 984 /// FastEmitBranch - Emit an unconditional branch to the given block,
 985 /// unless it is the immediate (fall-through) successor, and update
 986 /// the CFG.
 987 void
 988 FastISel::FastEmitBranch(MachineBasicBlock *MSucc, DebugLoc DbgLoc) {
 989   if (FuncInfo.MBB->getBasicBlock()->size() > 1 &&
 990       FuncInfo.MBB->isLayoutSuccessor(MSucc)) {
 991     // For more accurate line information if this is the only instruction
 992     // in the block then emit it, otherwise we have the unconditional
 993     // fall-through case, which needs no instructions.
 994   } else {
 995     // The unconditional branch case.
 996     TII.InsertBranch(*FuncInfo.MBB, MSucc, nullptr,
 997                      SmallVector<MachineOperand, 0>(), DbgLoc);
 998   }
 999   uint32_t BranchWeight = 0;
1000   if (FuncInfo.BPI)
1001     BranchWeight = FuncInfo.BPI->getEdgeWeight(FuncInfo.MBB->getBasicBlock(),
1002                                                MSucc->getBasicBlock());
1003   FuncInfo.MBB->addSuccessor(MSucc, BranchWeight);
1004 }
1005
1006 /// SelectFNeg - Emit an FNeg operation.
1007 ///
1008 bool
1009 FastISel::SelectFNeg(const User *I) {
1010   unsigned OpReg = getRegForValue(BinaryOperator::getFNegArgument(I));
1011   if (OpReg == 0) return false;
1012
1013   bool OpRegIsKill = hasTrivialKill(I);
1014
1015   // If the target has ISD::FNEG, use it.
1016   EVT VT = TLI.getValueType(I->getType());
1017   unsigned ResultReg = FastEmit_r(VT.getSimpleVT(), VT.getSimpleVT(),
1018                                   ISD::FNEG, OpReg, OpRegIsKill);
1019   if (ResultReg != 0) {
1020     UpdateValueMap(I, ResultReg);
1021     return true;
1022   }
1023
1024   // Bitcast the value to integer, twiddle the sign bit with xor,
1025   // and then bitcast it back to floating-point.
1026   if (VT.getSizeInBits() > 64) return false;
1027   EVT IntVT = EVT::getIntegerVT(I->getContext(), VT.getSizeInBits());
1028   if (!TLI.isTypeLegal(IntVT))
1029     return false;
1030
1031   unsigned IntReg = FastEmit_r(VT.getSimpleVT(), IntVT.getSimpleVT(),
1032                                ISD::BITCAST, OpReg, OpRegIsKill);
1033   if (IntReg == 0)
1034     return false;
1035
1036   unsigned IntResultReg = FastEmit_ri_(IntVT.getSimpleVT(), ISD::XOR,
1037                                        IntReg, /*Kill=*/true,
1038                                        UINT64_C(1) << (VT.getSizeInBits()-1),
1039                                        IntVT.getSimpleVT());
1040   if (IntResultReg == 0)
1041     return false;
1042
1043   ResultReg = FastEmit_r(IntVT.getSimpleVT(), VT.getSimpleVT(),
1044                          ISD::BITCAST, IntResultReg, /*Kill=*/true);
1045   if (ResultReg == 0)
1046     return false;
1047
1048   UpdateValueMap(I, ResultReg);
1049   return true;
1050 }
1051
1052 bool
1053 FastISel::SelectExtractValue(const User *U) {
1054   const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(U);
1055   if (!EVI)
1056     return false;
1057
1058   // Make sure we only try to handle extracts with a legal result.  But also
1059   // allow i1 because it's easy.
1060   EVT RealVT = TLI.getValueType(EVI->getType(), /*AllowUnknown=*/true);
1061   if (!RealVT.isSimple())
1062     return false;
1063   MVT VT = RealVT.getSimpleVT();
1064   if (!TLI.isTypeLegal(VT) && VT != MVT::i1)
1065     return false;
1066
1067   const Value *Op0 = EVI->getOperand(0);
1068   Type *AggTy = Op0->getType();
1069
1070   // Get the base result register.
1071   unsigned ResultReg;
1072   DenseMap<const Value *, unsigned>::iterator I = FuncInfo.ValueMap.find(Op0);
1073   if (I != FuncInfo.ValueMap.end())
1074     ResultReg = I->second;
1075   else if (isa<Instruction>(Op0))
1076     ResultReg = FuncInfo.InitializeRegForValue(Op0);
1077   else
1078     return false; // fast-isel can't handle aggregate constants at the moment
1079
1080   // Get the actual result register, which is an offset from the base register.
1081   unsigned VTIndex = ComputeLinearIndex(AggTy, EVI->getIndices());
1082
1083   SmallVector<EVT, 4> AggValueVTs;
1084   ComputeValueVTs(TLI, AggTy, AggValueVTs);
1085
1086   for (unsigned i = 0; i < VTIndex; i++)
1087     ResultReg += TLI.getNumRegisters(FuncInfo.Fn->getContext(), AggValueVTs[i]);
1088
1089   UpdateValueMap(EVI, ResultReg);
1090   return true;
1091 }
1092
1093 bool
1094 FastISel::SelectOperator(const User *I, unsigned Opcode) {
1095   switch (Opcode) {
1096   case Instruction::Add:
1097     return SelectBinaryOp(I, ISD::ADD);
1098   case Instruction::FAdd:
1099     return SelectBinaryOp(I, ISD::FADD);
1100   case Instruction::Sub:
1101     return SelectBinaryOp(I, ISD::SUB);
1102   case Instruction::FSub:
1103     // FNeg is currently represented in LLVM IR as a special case of FSub.
1104     if (BinaryOperator::isFNeg(I))
1105       return SelectFNeg(I);
1106     return SelectBinaryOp(I, ISD::FSUB);
1107   case Instruction::Mul:
1108     return SelectBinaryOp(I, ISD::MUL);
1109   case Instruction::FMul:
1110     return SelectBinaryOp(I, ISD::FMUL);
1111   case Instruction::SDiv:
1112     return SelectBinaryOp(I, ISD::SDIV);
1113   case Instruction::UDiv:
1114     return SelectBinaryOp(I, ISD::UDIV);
1115   case Instruction::FDiv:
1116     return SelectBinaryOp(I, ISD::FDIV);
1117   case Instruction::SRem:
1118     return SelectBinaryOp(I, ISD::SREM);
1119   case Instruction::URem:
1120     return SelectBinaryOp(I, ISD::UREM);
1121   case Instruction::FRem:
1122     return SelectBinaryOp(I, ISD::FREM);
1123   case Instruction::Shl:
1124     return SelectBinaryOp(I, ISD::SHL);
1125   case Instruction::LShr:
1126     return SelectBinaryOp(I, ISD::SRL);
1127   case Instruction::AShr:
1128     return SelectBinaryOp(I, ISD::SRA);
1129   case Instruction::And:
1130     return SelectBinaryOp(I, ISD::AND);
1131   case Instruction::Or:
1132     return SelectBinaryOp(I, ISD::OR);
1133   case Instruction::Xor:
1134     return SelectBinaryOp(I, ISD::XOR);
1135
1136   case Instruction::GetElementPtr:
1137     return SelectGetElementPtr(I);
1138
1139   case Instruction::Br: {
1140     const BranchInst *BI = cast<BranchInst>(I);
1141
1142     if (BI->isUnconditional()) {
1143       const BasicBlock *LLVMSucc = BI->getSuccessor(0);
1144       MachineBasicBlock *MSucc = FuncInfo.MBBMap[LLVMSucc];
1145       FastEmitBranch(MSucc, BI->getDebugLoc());
1146       return true;
1147     }
1148
1149     // Conditional branches are not handed yet.
1150     // Halt "fast" selection and bail.
1151     return false;
1152   }
1153
1154   case Instruction::Unreachable:
1155     if (TM.Options.TrapUnreachable)
1156       return FastEmit_(MVT::Other, MVT::Other, ISD::TRAP) != 0;
1157     else
1158       return true;
1159
1160   case Instruction::Alloca:
1161     // FunctionLowering has the static-sized case covered.
1162     if (FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(I)))
1163       return true;
1164
1165     // Dynamic-sized alloca is not handled yet.
1166     return false;
1167
1168   case Instruction::Call:
1169     return SelectCall(I);
1170
1171   case Instruction::BitCast:
1172     return SelectBitCast(I);
1173
1174   case Instruction::FPToSI:
1175     return SelectCast(I, ISD::FP_TO_SINT);
1176   case Instruction::ZExt:
1177     return SelectCast(I, ISD::ZERO_EXTEND);
1178   case Instruction::SExt:
1179     return SelectCast(I, ISD::SIGN_EXTEND);
1180   case Instruction::Trunc:
1181     return SelectCast(I, ISD::TRUNCATE);
1182   case Instruction::SIToFP:
1183     return SelectCast(I, ISD::SINT_TO_FP);
1184
1185   case Instruction::IntToPtr: // Deliberate fall-through.
1186   case Instruction::PtrToInt: {
1187     EVT SrcVT = TLI.getValueType(I->getOperand(0)->getType());
1188     EVT DstVT = TLI.getValueType(I->getType());
1189     if (DstVT.bitsGT(SrcVT))
1190       return SelectCast(I, ISD::ZERO_EXTEND);
1191     if (DstVT.bitsLT(SrcVT))
1192       return SelectCast(I, ISD::TRUNCATE);
1193     unsigned Reg = getRegForValue(I->getOperand(0));
1194     if (Reg == 0) return false;
1195     UpdateValueMap(I, Reg);
1196     return true;
1197   }
1198
1199   case Instruction::ExtractValue:
1200     return SelectExtractValue(I);
1201
1202   case Instruction::PHI:
1203     llvm_unreachable("FastISel shouldn't visit PHI nodes!");
1204
1205   default:
1206     // Unhandled instruction. Halt "fast" selection and bail.
1207     return false;
1208   }
1209 }
1210
1211 FastISel::FastISel(FunctionLoweringInfo &funcInfo,
1212                    const TargetLibraryInfo *libInfo)
1213   : FuncInfo(funcInfo),
1214     MF(funcInfo.MF),
1215     MRI(FuncInfo.MF->getRegInfo()),
1216     MFI(*FuncInfo.MF->getFrameInfo()),
1217     MCP(*FuncInfo.MF->getConstantPool()),
1218     TM(FuncInfo.MF->getTarget()),
1219     DL(*TM.getDataLayout()),
1220     TII(*TM.getInstrInfo()),
1221     TLI(*TM.getTargetLowering()),
1222     TRI(*TM.getRegisterInfo()),
1223     LibInfo(libInfo) {
1224 }
1225
1226 FastISel::~FastISel() {}
1227
1228 bool FastISel::FastLowerArguments() {
1229   return false;
1230 }
1231
1232 bool FastISel::FastLowerIntrinsicCall(const IntrinsicInst */*II*/) {
1233   return false;
1234 }
1235
1236 unsigned FastISel::FastEmit_(MVT, MVT,
1237                              unsigned) {
1238   return 0;
1239 }
1240
1241 unsigned FastISel::FastEmit_r(MVT, MVT,
1242                               unsigned,
1243                               unsigned /*Op0*/, bool /*Op0IsKill*/) {
1244   return 0;
1245 }
1246
1247 unsigned FastISel::FastEmit_rr(MVT, MVT,
1248                                unsigned,
1249                                unsigned /*Op0*/, bool /*Op0IsKill*/,
1250                                unsigned /*Op1*/, bool /*Op1IsKill*/) {
1251   return 0;
1252 }
1253
1254 unsigned FastISel::FastEmit_i(MVT, MVT, unsigned, uint64_t /*Imm*/) {
1255   return 0;
1256 }
1257
1258 unsigned FastISel::FastEmit_f(MVT, MVT,
1259                               unsigned, const ConstantFP * /*FPImm*/) {
1260   return 0;
1261 }
1262
1263 unsigned FastISel::FastEmit_ri(MVT, MVT,
1264                                unsigned,
1265                                unsigned /*Op0*/, bool /*Op0IsKill*/,
1266                                uint64_t /*Imm*/) {
1267   return 0;
1268 }
1269
1270 unsigned FastISel::FastEmit_rf(MVT, MVT,
1271                                unsigned,
1272                                unsigned /*Op0*/, bool /*Op0IsKill*/,
1273                                const ConstantFP * /*FPImm*/) {
1274   return 0;
1275 }
1276
1277 unsigned FastISel::FastEmit_rri(MVT, MVT,
1278                                 unsigned,
1279                                 unsigned /*Op0*/, bool /*Op0IsKill*/,
1280                                 unsigned /*Op1*/, bool /*Op1IsKill*/,
1281                                 uint64_t /*Imm*/) {
1282   return 0;
1283 }
1284
1285 /// FastEmit_ri_ - This method is a wrapper of FastEmit_ri. It first tries
1286 /// to emit an instruction with an immediate operand using FastEmit_ri.
1287 /// If that fails, it materializes the immediate into a register and try
1288 /// FastEmit_rr instead.
1289 unsigned FastISel::FastEmit_ri_(MVT VT, unsigned Opcode,
1290                                 unsigned Op0, bool Op0IsKill,
1291                                 uint64_t Imm, MVT ImmType) {
1292   // If this is a multiply by a power of two, emit this as a shift left.
1293   if (Opcode == ISD::MUL && isPowerOf2_64(Imm)) {
1294     Opcode = ISD::SHL;
1295     Imm = Log2_64(Imm);
1296   } else if (Opcode == ISD::UDIV && isPowerOf2_64(Imm)) {
1297     // div x, 8 -> srl x, 3
1298     Opcode = ISD::SRL;
1299     Imm = Log2_64(Imm);
1300   }
1301
1302   // Horrible hack (to be removed), check to make sure shift amounts are
1303   // in-range.
1304   if ((Opcode == ISD::SHL || Opcode == ISD::SRA || Opcode == ISD::SRL) &&
1305       Imm >= VT.getSizeInBits())
1306     return 0;
1307
1308   // First check if immediate type is legal. If not, we can't use the ri form.
1309   unsigned ResultReg = FastEmit_ri(VT, VT, Opcode, Op0, Op0IsKill, Imm);
1310   if (ResultReg != 0)
1311     return ResultReg;
1312   unsigned MaterialReg = FastEmit_i(ImmType, ImmType, ISD::Constant, Imm);
1313   if (MaterialReg == 0) {
1314     // This is a bit ugly/slow, but failing here means falling out of
1315     // fast-isel, which would be very slow.
1316     IntegerType *ITy = IntegerType::get(FuncInfo.Fn->getContext(),
1317                                               VT.getSizeInBits());
1318     MaterialReg = getRegForValue(ConstantInt::get(ITy, Imm));
1319     assert (MaterialReg != 0 && "Unable to materialize imm.");
1320     if (MaterialReg == 0) return 0;
1321   }
1322   return FastEmit_rr(VT, VT, Opcode,
1323                      Op0, Op0IsKill,
1324                      MaterialReg, /*Kill=*/true);
1325 }
1326
1327 unsigned FastISel::createResultReg(const TargetRegisterClass* RC) {
1328   return MRI.createVirtualRegister(RC);
1329 }
1330
1331 unsigned FastISel::constrainOperandRegClass(const MCInstrDesc &II,
1332                                             unsigned Op, unsigned OpNum) {
1333   if (TargetRegisterInfo::isVirtualRegister(Op)) {
1334     const TargetRegisterClass *RegClass =
1335         TII.getRegClass(II, OpNum, &TRI, *FuncInfo.MF);
1336     if (!MRI.constrainRegClass(Op, RegClass)) {
1337       // If it's not legal to COPY between the register classes, something
1338       // has gone very wrong before we got here.
1339       unsigned NewOp = createResultReg(RegClass);
1340       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1341               TII.get(TargetOpcode::COPY), NewOp).addReg(Op);
1342       return NewOp;
1343     }
1344   }
1345   return Op;
1346 }
1347
1348 unsigned FastISel::FastEmitInst_(unsigned MachineInstOpcode,
1349                                  const TargetRegisterClass* RC) {
1350   unsigned ResultReg = createResultReg(RC);
1351   const MCInstrDesc &II = TII.get(MachineInstOpcode);
1352
1353   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg);
1354   return ResultReg;
1355 }
1356
1357 unsigned FastISel::FastEmitInst_r(unsigned MachineInstOpcode,
1358                                   const TargetRegisterClass *RC,
1359                                   unsigned Op0, bool Op0IsKill) {
1360   const MCInstrDesc &II = TII.get(MachineInstOpcode);
1361
1362   unsigned ResultReg = createResultReg(RC);
1363   Op0 = constrainOperandRegClass(II, Op0, II.getNumDefs());
1364
1365   if (II.getNumDefs() >= 1)
1366     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
1367       .addReg(Op0, Op0IsKill * RegState::Kill);
1368   else {
1369     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
1370       .addReg(Op0, Op0IsKill * RegState::Kill);
1371     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1372             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
1373   }
1374
1375   return ResultReg;
1376 }
1377
1378 unsigned FastISel::FastEmitInst_rr(unsigned MachineInstOpcode,
1379                                    const TargetRegisterClass *RC,
1380                                    unsigned Op0, bool Op0IsKill,
1381                                    unsigned Op1, bool Op1IsKill) {
1382   const MCInstrDesc &II = TII.get(MachineInstOpcode);
1383
1384   unsigned ResultReg = createResultReg(RC);
1385   Op0 = constrainOperandRegClass(II, Op0, II.getNumDefs());
1386   Op1 = constrainOperandRegClass(II, Op1, II.getNumDefs() + 1);
1387
1388   if (II.getNumDefs() >= 1)
1389     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
1390       .addReg(Op0, Op0IsKill * RegState::Kill)
1391       .addReg(Op1, Op1IsKill * RegState::Kill);
1392   else {
1393     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
1394       .addReg(Op0, Op0IsKill * RegState::Kill)
1395       .addReg(Op1, Op1IsKill * RegState::Kill);
1396     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1397             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
1398   }
1399   return ResultReg;
1400 }
1401
1402 unsigned FastISel::FastEmitInst_rrr(unsigned MachineInstOpcode,
1403                                    const TargetRegisterClass *RC,
1404                                    unsigned Op0, bool Op0IsKill,
1405                                    unsigned Op1, bool Op1IsKill,
1406                                    unsigned Op2, bool Op2IsKill) {
1407   const MCInstrDesc &II = TII.get(MachineInstOpcode);
1408
1409   unsigned ResultReg = createResultReg(RC);
1410   Op0 = constrainOperandRegClass(II, Op0, II.getNumDefs());
1411   Op1 = constrainOperandRegClass(II, Op1, II.getNumDefs() + 1);
1412   Op2 = constrainOperandRegClass(II, Op2, II.getNumDefs() + 2);
1413
1414   if (II.getNumDefs() >= 1)
1415     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
1416       .addReg(Op0, Op0IsKill * RegState::Kill)
1417       .addReg(Op1, Op1IsKill * RegState::Kill)
1418       .addReg(Op2, Op2IsKill * RegState::Kill);
1419   else {
1420     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
1421       .addReg(Op0, Op0IsKill * RegState::Kill)
1422       .addReg(Op1, Op1IsKill * RegState::Kill)
1423       .addReg(Op2, Op2IsKill * RegState::Kill);
1424     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1425             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
1426   }
1427   return ResultReg;
1428 }
1429
1430 unsigned FastISel::FastEmitInst_ri(unsigned MachineInstOpcode,
1431                                    const TargetRegisterClass *RC,
1432                                    unsigned Op0, bool Op0IsKill,
1433                                    uint64_t Imm) {
1434   const MCInstrDesc &II = TII.get(MachineInstOpcode);
1435
1436   unsigned ResultReg = createResultReg(RC);
1437   RC = TII.getRegClass(II, II.getNumDefs(), &TRI, *FuncInfo.MF);
1438   MRI.constrainRegClass(Op0, RC);
1439
1440   if (II.getNumDefs() >= 1)
1441     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
1442       .addReg(Op0, Op0IsKill * RegState::Kill)
1443       .addImm(Imm);
1444   else {
1445     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
1446       .addReg(Op0, Op0IsKill * RegState::Kill)
1447       .addImm(Imm);
1448     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1449             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
1450   }
1451   return ResultReg;
1452 }
1453
1454 unsigned FastISel::FastEmitInst_rii(unsigned MachineInstOpcode,
1455                                    const TargetRegisterClass *RC,
1456                                    unsigned Op0, bool Op0IsKill,
1457                                    uint64_t Imm1, uint64_t Imm2) {
1458   const MCInstrDesc &II = TII.get(MachineInstOpcode);
1459
1460   unsigned ResultReg = createResultReg(RC);
1461   Op0 = constrainOperandRegClass(II, Op0, II.getNumDefs());
1462
1463   if (II.getNumDefs() >= 1)
1464     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
1465       .addReg(Op0, Op0IsKill * RegState::Kill)
1466       .addImm(Imm1)
1467       .addImm(Imm2);
1468   else {
1469     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
1470       .addReg(Op0, Op0IsKill * RegState::Kill)
1471       .addImm(Imm1)
1472       .addImm(Imm2);
1473     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1474             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
1475   }
1476   return ResultReg;
1477 }
1478
1479 unsigned FastISel::FastEmitInst_rf(unsigned MachineInstOpcode,
1480                                    const TargetRegisterClass *RC,
1481                                    unsigned Op0, bool Op0IsKill,
1482                                    const ConstantFP *FPImm) {
1483   const MCInstrDesc &II = TII.get(MachineInstOpcode);
1484
1485   unsigned ResultReg = createResultReg(RC);
1486   Op0 = constrainOperandRegClass(II, Op0, II.getNumDefs());
1487
1488   if (II.getNumDefs() >= 1)
1489     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
1490       .addReg(Op0, Op0IsKill * RegState::Kill)
1491       .addFPImm(FPImm);
1492   else {
1493     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
1494       .addReg(Op0, Op0IsKill * RegState::Kill)
1495       .addFPImm(FPImm);
1496     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1497             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
1498   }
1499   return ResultReg;
1500 }
1501
1502 unsigned FastISel::FastEmitInst_rri(unsigned MachineInstOpcode,
1503                                     const TargetRegisterClass *RC,
1504                                     unsigned Op0, bool Op0IsKill,
1505                                     unsigned Op1, bool Op1IsKill,
1506                                     uint64_t Imm) {
1507   const MCInstrDesc &II = TII.get(MachineInstOpcode);
1508
1509   unsigned ResultReg = createResultReg(RC);
1510   Op0 = constrainOperandRegClass(II, Op0, II.getNumDefs());
1511   Op1 = constrainOperandRegClass(II, Op1, II.getNumDefs() + 1);
1512
1513   if (II.getNumDefs() >= 1)
1514     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
1515       .addReg(Op0, Op0IsKill * RegState::Kill)
1516       .addReg(Op1, Op1IsKill * RegState::Kill)
1517       .addImm(Imm);
1518   else {
1519     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
1520       .addReg(Op0, Op0IsKill * RegState::Kill)
1521       .addReg(Op1, Op1IsKill * RegState::Kill)
1522       .addImm(Imm);
1523     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1524             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
1525   }
1526   return ResultReg;
1527 }
1528
1529 unsigned FastISel::FastEmitInst_rrii(unsigned MachineInstOpcode,
1530                                      const TargetRegisterClass *RC,
1531                                      unsigned Op0, bool Op0IsKill,
1532                                      unsigned Op1, bool Op1IsKill,
1533                                      uint64_t Imm1, uint64_t Imm2) {
1534   const MCInstrDesc &II = TII.get(MachineInstOpcode);
1535
1536   unsigned ResultReg = createResultReg(RC);
1537   Op0 = constrainOperandRegClass(II, Op0, II.getNumDefs());
1538   Op1 = constrainOperandRegClass(II, Op1, II.getNumDefs() + 1);
1539
1540   if (II.getNumDefs() >= 1)
1541     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
1542       .addReg(Op0, Op0IsKill * RegState::Kill)
1543       .addReg(Op1, Op1IsKill * RegState::Kill)
1544       .addImm(Imm1).addImm(Imm2);
1545   else {
1546     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
1547       .addReg(Op0, Op0IsKill * RegState::Kill)
1548       .addReg(Op1, Op1IsKill * RegState::Kill)
1549       .addImm(Imm1).addImm(Imm2);
1550     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1551             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
1552   }
1553   return ResultReg;
1554 }
1555
1556 unsigned FastISel::FastEmitInst_i(unsigned MachineInstOpcode,
1557                                   const TargetRegisterClass *RC,
1558                                   uint64_t Imm) {
1559   unsigned ResultReg = createResultReg(RC);
1560   const MCInstrDesc &II = TII.get(MachineInstOpcode);
1561
1562   if (II.getNumDefs() >= 1)
1563     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg).addImm(Imm);
1564   else {
1565     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II).addImm(Imm);
1566     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1567             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
1568   }
1569   return ResultReg;
1570 }
1571
1572 unsigned FastISel::FastEmitInst_ii(unsigned MachineInstOpcode,
1573                                   const TargetRegisterClass *RC,
1574                                   uint64_t Imm1, uint64_t Imm2) {
1575   unsigned ResultReg = createResultReg(RC);
1576   const MCInstrDesc &II = TII.get(MachineInstOpcode);
1577
1578   if (II.getNumDefs() >= 1)
1579     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
1580       .addImm(Imm1).addImm(Imm2);
1581   else {
1582     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II).addImm(Imm1).addImm(Imm2);
1583     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1584             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
1585   }
1586   return ResultReg;
1587 }
1588
1589 unsigned FastISel::FastEmitInst_extractsubreg(MVT RetVT,
1590                                               unsigned Op0, bool Op0IsKill,
1591                                               uint32_t Idx) {
1592   unsigned ResultReg = createResultReg(TLI.getRegClassFor(RetVT));
1593   assert(TargetRegisterInfo::isVirtualRegister(Op0) &&
1594          "Cannot yet extract from physregs");
1595   const TargetRegisterClass *RC = MRI.getRegClass(Op0);
1596   MRI.constrainRegClass(Op0, TRI.getSubClassWithSubReg(RC, Idx));
1597   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt,
1598           DbgLoc, TII.get(TargetOpcode::COPY), ResultReg)
1599     .addReg(Op0, getKillRegState(Op0IsKill), Idx);
1600   return ResultReg;
1601 }
1602
1603 /// FastEmitZExtFromI1 - Emit MachineInstrs to compute the value of Op
1604 /// with all but the least significant bit set to zero.
1605 unsigned FastISel::FastEmitZExtFromI1(MVT VT, unsigned Op0, bool Op0IsKill) {
1606   return FastEmit_ri(VT, VT, ISD::AND, Op0, Op0IsKill, 1);
1607 }
1608
1609 /// HandlePHINodesInSuccessorBlocks - Handle PHI nodes in successor blocks.
1610 /// Emit code to ensure constants are copied into registers when needed.
1611 /// Remember the virtual registers that need to be added to the Machine PHI
1612 /// nodes as input.  We cannot just directly add them, because expansion
1613 /// might result in multiple MBB's for one BB.  As such, the start of the
1614 /// BB might correspond to a different MBB than the end.
1615 bool FastISel::HandlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB) {
1616   const TerminatorInst *TI = LLVMBB->getTerminator();
1617
1618   SmallPtrSet<MachineBasicBlock *, 4> SuccsHandled;
1619   unsigned OrigNumPHINodesToUpdate = FuncInfo.PHINodesToUpdate.size();
1620
1621   // Check successor nodes' PHI nodes that expect a constant to be available
1622   // from this block.
1623   for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) {
1624     const BasicBlock *SuccBB = TI->getSuccessor(succ);
1625     if (!isa<PHINode>(SuccBB->begin())) continue;
1626     MachineBasicBlock *SuccMBB = FuncInfo.MBBMap[SuccBB];
1627
1628     // If this terminator has multiple identical successors (common for
1629     // switches), only handle each succ once.
1630     if (!SuccsHandled.insert(SuccMBB)) continue;
1631
1632     MachineBasicBlock::iterator MBBI = SuccMBB->begin();
1633
1634     // At this point we know that there is a 1-1 correspondence between LLVM PHI
1635     // nodes and Machine PHI nodes, but the incoming operands have not been
1636     // emitted yet.
1637     for (BasicBlock::const_iterator I = SuccBB->begin();
1638          const PHINode *PN = dyn_cast<PHINode>(I); ++I) {
1639
1640       // Ignore dead phi's.
1641       if (PN->use_empty()) continue;
1642
1643       // Only handle legal types. Two interesting things to note here. First,
1644       // by bailing out early, we may leave behind some dead instructions,
1645       // since SelectionDAG's HandlePHINodesInSuccessorBlocks will insert its
1646       // own moves. Second, this check is necessary because FastISel doesn't
1647       // use CreateRegs to create registers, so it always creates
1648       // exactly one register for each non-void instruction.
1649       EVT VT = TLI.getValueType(PN->getType(), /*AllowUnknown=*/true);
1650       if (VT == MVT::Other || !TLI.isTypeLegal(VT)) {
1651         // Handle integer promotions, though, because they're common and easy.
1652         if (VT == MVT::i1 || VT == MVT::i8 || VT == MVT::i16)
1653           VT = TLI.getTypeToTransformTo(LLVMBB->getContext(), VT);
1654         else {
1655           FuncInfo.PHINodesToUpdate.resize(OrigNumPHINodesToUpdate);
1656           return false;
1657         }
1658       }
1659
1660       const Value *PHIOp = PN->getIncomingValueForBlock(LLVMBB);
1661
1662       // Set the DebugLoc for the copy. Prefer the location of the operand
1663       // if there is one; use the location of the PHI otherwise.
1664       DbgLoc = PN->getDebugLoc();
1665       if (const Instruction *Inst = dyn_cast<Instruction>(PHIOp))
1666         DbgLoc = Inst->getDebugLoc();
1667
1668       unsigned Reg = getRegForValue(PHIOp);
1669       if (Reg == 0) {
1670         FuncInfo.PHINodesToUpdate.resize(OrigNumPHINodesToUpdate);
1671         return false;
1672       }
1673       FuncInfo.PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg));
1674       DbgLoc = DebugLoc();
1675     }
1676   }
1677
1678   return true;
1679 }
1680
1681 bool FastISel::tryToFoldLoad(const LoadInst *LI, const Instruction *FoldInst) {
1682   assert(LI->hasOneUse() &&
1683       "tryToFoldLoad expected a LoadInst with a single use");
1684   // We know that the load has a single use, but don't know what it is.  If it
1685   // isn't one of the folded instructions, then we can't succeed here.  Handle
1686   // this by scanning the single-use users of the load until we get to FoldInst.
1687   unsigned MaxUsers = 6;  // Don't scan down huge single-use chains of instrs.
1688
1689   const Instruction *TheUser = LI->user_back();
1690   while (TheUser != FoldInst &&   // Scan up until we find FoldInst.
1691          // Stay in the right block.
1692          TheUser->getParent() == FoldInst->getParent() &&
1693          --MaxUsers) {  // Don't scan too far.
1694     // If there are multiple or no uses of this instruction, then bail out.
1695     if (!TheUser->hasOneUse())
1696       return false;
1697
1698     TheUser = TheUser->user_back();
1699   }
1700
1701   // If we didn't find the fold instruction, then we failed to collapse the
1702   // sequence.
1703   if (TheUser != FoldInst)
1704     return false;
1705
1706   // Don't try to fold volatile loads.  Target has to deal with alignment
1707   // constraints.
1708   if (LI->isVolatile())
1709     return false;
1710
1711   // Figure out which vreg this is going into.  If there is no assigned vreg yet
1712   // then there actually was no reference to it.  Perhaps the load is referenced
1713   // by a dead instruction.
1714   unsigned LoadReg = getRegForValue(LI);
1715   if (LoadReg == 0)
1716     return false;
1717
1718   // We can't fold if this vreg has no uses or more than one use.  Multiple uses
1719   // may mean that the instruction got lowered to multiple MIs, or the use of
1720   // the loaded value ended up being multiple operands of the result.
1721   if (!MRI.hasOneUse(LoadReg))
1722     return false;
1723
1724   MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(LoadReg);
1725   MachineInstr *User = RI->getParent();
1726
1727   // Set the insertion point properly.  Folding the load can cause generation of
1728   // other random instructions (like sign extends) for addressing modes; make
1729   // sure they get inserted in a logical place before the new instruction.
1730   FuncInfo.InsertPt = User;
1731   FuncInfo.MBB = User->getParent();
1732
1733   // Ask the target to try folding the load.
1734   return tryToFoldLoadIntoMI(User, RI.getOperandNo(), LI);
1735 }
1736
1737 bool FastISel::canFoldAddIntoGEP(const User *GEP, const Value *Add) {
1738   // Must be an add.
1739   if (!isa<AddOperator>(Add))
1740     return false;
1741   // Type size needs to match.
1742   if (DL.getTypeSizeInBits(GEP->getType()) !=
1743       DL.getTypeSizeInBits(Add->getType()))
1744     return false;
1745   // Must be in the same basic block.
1746   if (isa<Instruction>(Add) &&
1747       FuncInfo.MBBMap[cast<Instruction>(Add)->getParent()] != FuncInfo.MBB)
1748     return false;
1749   // Must have a constant operand.
1750   return isa<ConstantInt>(cast<AddOperator>(Add)->getOperand(1));
1751 }
1752
1753 MachineMemOperand *
1754 FastISel::createMachineMemOperandFor(const Instruction *I) const {
1755   const Value *Ptr;
1756   Type *ValTy;
1757   unsigned Alignment;
1758   unsigned Flags;
1759   bool IsVolatile;
1760
1761   if (const auto *LI = dyn_cast<LoadInst>(I)) {
1762     Alignment = LI->getAlignment();
1763     IsVolatile = LI->isVolatile();
1764     Flags = MachineMemOperand::MOLoad;
1765     Ptr = LI->getPointerOperand();
1766     ValTy = LI->getType();
1767   } else if (const auto *SI = dyn_cast<StoreInst>(I)) {
1768     Alignment = SI->getAlignment();
1769     IsVolatile = SI->isVolatile();
1770     Flags = MachineMemOperand::MOStore;
1771     Ptr = SI->getPointerOperand();
1772     ValTy = SI->getValueOperand()->getType();
1773   } else {
1774     return nullptr;
1775   }
1776
1777   bool IsNonTemporal = I->getMetadata("nontemporal") != nullptr;
1778   bool IsInvariant = I->getMetadata("invariant.load") != nullptr;
1779   const MDNode *TBAAInfo = I->getMetadata(LLVMContext::MD_tbaa);
1780   const MDNode *Ranges = I->getMetadata(LLVMContext::MD_range);
1781
1782   if (Alignment == 0)  // Ensure that codegen never sees alignment 0.
1783     Alignment = DL.getABITypeAlignment(ValTy);
1784
1785   unsigned Size = TM.getDataLayout()->getTypeStoreSize(ValTy);
1786
1787   if (IsVolatile)
1788     Flags |= MachineMemOperand::MOVolatile;
1789   if (IsNonTemporal)
1790     Flags |= MachineMemOperand::MONonTemporal;
1791   if (IsInvariant)
1792     Flags |= MachineMemOperand::MOInvariant;
1793
1794   return FuncInfo.MF->getMachineMemOperand(MachinePointerInfo(Ptr), Flags, Size,
1795                                            Alignment, TBAAInfo, Ranges);
1796 }