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