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