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