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