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/Function.h"
  43 #include "llvm/GlobalVariable.h"
  44 #include "llvm/Instructions.h"
  45 #include "llvm/IntrinsicInst.h"
  46 #include "llvm/CodeGen/FastISel.h"
  47 #include "llvm/CodeGen/MachineInstrBuilder.h"
  48 #include "llvm/CodeGen/MachineModuleInfo.h"
  49 #include "llvm/CodeGen/MachineRegisterInfo.h"
  50 #include "llvm/Analysis/DebugInfo.h"
  51 #include "llvm/Target/TargetData.h"
  52 #include "llvm/Target/TargetInstrInfo.h"
  53 #include "llvm/Target/TargetLowering.h"
  54 #include "llvm/Target/TargetMachine.h"
  55 #include "llvm/Support/ErrorHandling.h"
  56 #include "FunctionLoweringInfo.h"
  57 using namespace llvm;
  58
  59 bool FastISel::hasTrivialKill(const Value *V) const {
  60   // Don't consider constants or arguments to have trivial kills. Only
  61   // instructions with a single use in the same basic block.
  62   const Instruction *I = dyn_cast<Instruction>(V);
  63   return I &&
  64          I->hasOneUse() &&
  65          cast<Instruction>(I->use_begin())->getParent() == I->getParent();
  66 }
  67
  68 unsigned FastISel::getRegForValue(const Value *V) {
  69   EVT RealVT = TLI.getValueType(V->getType(), /*AllowUnknown=*/true);
  70   // Don't handle non-simple values in FastISel.
  71   if (!RealVT.isSimple())
  72     return 0;
  73
  74   // Ignore illegal types. We must do this before looking up the value
  75   // in ValueMap because Arguments are given virtual registers regardless
  76   // of whether FastISel can handle them.
  77   MVT VT = RealVT.getSimpleVT();
  78   if (!TLI.isTypeLegal(VT)) {
  79     // Promote MVT::i1 to a legal type though, because it's common and easy.
  80     if (VT == MVT::i1)
  81       VT = TLI.getTypeToTransformTo(V->getContext(), VT).getSimpleVT();
  82     else
  83       return 0;
  84   }
  85
  86   // Look up the value to see if we already have a register for it. We
  87   // cache values defined by Instructions across blocks, and other values
  88   // only locally. This is because Instructions already have the SSA
  89   // def-dominates-use requirement enforced.
  90   if (ValueMap.count(V))
  91     return ValueMap[V];
  92   unsigned Reg = LocalValueMap[V];
  93   if (Reg != 0)
  94     return Reg;
  95
  96   // In bottom-up mode, just create the virtual register which will be used
  97   // to hold the value. It will be materialized later.
  98   if (IsBottomUp) {
  99     Reg = createResultReg(TLI.getRegClassFor(VT));
 100     if (isa<Instruction>(V))
 101       ValueMap[V] = Reg;
 102     else
 103       LocalValueMap[V] = Reg;
 104     return Reg;
 105   }
 106
 107   return materializeRegForValue(V, VT);
 108 }
 109
 110 /// materializeRegForValue - Helper for getRegForVale. This function is
 111 /// called when the value isn't already available in a register and must
 112 /// be materialized with new instructions.
 113 unsigned FastISel::materializeRegForValue(const Value *V, MVT VT) {
 114   unsigned Reg = 0;
 115
 116   if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
 117     if (CI->getValue().getActiveBits() <= 64)
 118       Reg = FastEmit_i(VT, VT, ISD::Constant, CI->getZExtValue());
 119   } else if (isa<AllocaInst>(V)) {
 120     Reg = TargetMaterializeAlloca(cast<AllocaInst>(V));
 121   } else if (isa<ConstantPointerNull>(V)) {
 122     // Translate this as an integer zero so that it can be
 123     // local-CSE'd with actual integer zeros.
 124     Reg =
 125       getRegForValue(Constant::getNullValue(TD.getIntPtrType(V->getContext())));
 126   } else if (const ConstantFP *CF = dyn_cast<ConstantFP>(V)) {
 127     // Try to emit the constant directly.
 128     Reg = FastEmit_f(VT, VT, ISD::ConstantFP, CF);
 129
 130     if (!Reg) {
 131       // Try to emit the constant by using an integer constant with a cast.
 132       const APFloat &Flt = CF->getValueAPF();
 133       EVT IntVT = TLI.getPointerTy();
 134
 135       uint64_t x[2];
 136       uint32_t IntBitWidth = IntVT.getSizeInBits();
 137       bool isExact;
 138       (void) Flt.convertToInteger(x, IntBitWidth, /*isSigned=*/true,
 139                                 APFloat::rmTowardZero, &isExact);
 140       if (isExact) {
 141         APInt IntVal(IntBitWidth, 2, x);
 142
 143         unsigned IntegerReg =
 144           getRegForValue(ConstantInt::get(V->getContext(), IntVal));
 145         if (IntegerReg != 0)
 146           Reg = FastEmit_r(IntVT.getSimpleVT(), VT, ISD::SINT_TO_FP,
 147                            IntegerReg, /*Kill=*/false);
 148       }
 149     }
 150   } else if (const Operator *Op = dyn_cast<Operator>(V)) {
 151     if (!SelectOperator(Op, Op->getOpcode())) return 0;
 152     Reg = LocalValueMap[Op];
 153   } else if (isa<UndefValue>(V)) {
 154     Reg = createResultReg(TLI.getRegClassFor(VT));
 155     BuildMI(MBB, DL, TII.get(TargetOpcode::IMPLICIT_DEF), Reg);
 156   }
 157
 158   // If target-independent code couldn't handle the value, give target-specific
 159   // code a try.
 160   if (!Reg && isa<Constant>(V))
 161     Reg = TargetMaterializeConstant(cast<Constant>(V));
 162
 163   // Don't cache constant materializations in the general ValueMap.
 164   // To do so would require tracking what uses they dominate.
 165   if (Reg != 0)
 166     LocalValueMap[V] = Reg;
 167   return Reg;
 168 }
 169
 170 unsigned FastISel::lookUpRegForValue(const Value *V) {
 171   // Look up the value to see if we already have a register for it. We
 172   // cache values defined by Instructions across blocks, and other values
 173   // only locally. This is because Instructions already have the SSA
 174   // def-dominates-use requirement enforced.
 175   if (ValueMap.count(V))
 176     return ValueMap[V];
 177   return LocalValueMap[V];
 178 }
 179
 180 /// UpdateValueMap - Update the value map to include the new mapping for this
 181 /// instruction, or insert an extra copy to get the result in a previous
 182 /// determined register.
 183 /// NOTE: This is only necessary because we might select a block that uses
 184 /// a value before we select the block that defines the value.  It might be
 185 /// possible to fix this by selecting blocks in reverse postorder.
 186 unsigned FastISel::UpdateValueMap(const Value *I, unsigned Reg) {
 187   if (!isa<Instruction>(I)) {
 188     LocalValueMap[I] = Reg;
 189     return Reg;
 190   }
 191
 192   unsigned &AssignedReg = ValueMap[I];
 193   if (AssignedReg == 0)
 194     AssignedReg = Reg;
 195   else if (Reg != AssignedReg) {
 196     const TargetRegisterClass *RegClass = MRI.getRegClass(Reg);
 197     TII.copyRegToReg(*MBB, MBB->end(), AssignedReg,
 198                      Reg, RegClass, RegClass, DL);
 199   }
 200   return AssignedReg;
 201 }
 202
 203 std::pair<unsigned, bool> FastISel::getRegForGEPIndex(const Value *Idx) {
 204   unsigned IdxN = getRegForValue(Idx);
 205   if (IdxN == 0)
 206     // Unhandled operand. Halt "fast" selection and bail.
 207     return std::pair<unsigned, bool>(0, false);
 208
 209   bool IdxNIsKill = hasTrivialKill(Idx);
 210
 211   // If the index is smaller or larger than intptr_t, truncate or extend it.
 212   MVT PtrVT = TLI.getPointerTy();
 213   EVT IdxVT = EVT::getEVT(Idx->getType(), /*HandleUnknown=*/false);
 214   if (IdxVT.bitsLT(PtrVT)) {
 215     IdxN = FastEmit_r(IdxVT.getSimpleVT(), PtrVT, ISD::SIGN_EXTEND,
 216                       IdxN, IdxNIsKill);
 217     IdxNIsKill = true;
 218   }
 219   else if (IdxVT.bitsGT(PtrVT)) {
 220     IdxN = FastEmit_r(IdxVT.getSimpleVT(), PtrVT, ISD::TRUNCATE,
 221                       IdxN, IdxNIsKill);
 222     IdxNIsKill = true;
 223   }
 224   return std::pair<unsigned, bool>(IdxN, IdxNIsKill);
 225 }
 226
 227 /// SelectBinaryOp - Select and emit code for a binary operator instruction,
 228 /// which has an opcode which directly corresponds to the given ISD opcode.
 229 ///
 230 bool FastISel::SelectBinaryOp(const User *I, unsigned ISDOpcode) {
 231   EVT VT = EVT::getEVT(I->getType(), /*HandleUnknown=*/true);
 232   if (VT == MVT::Other || !VT.isSimple())
 233     // Unhandled type. Halt "fast" selection and bail.
 234     return false;
 235
 236   // We only handle legal types. For example, on x86-32 the instruction
 237   // selector contains all of the 64-bit instructions from x86-64,
 238   // under the assumption that i64 won't be used if the target doesn't
 239   // support it.
 240   if (!TLI.isTypeLegal(VT)) {
 241     // MVT::i1 is special. Allow AND, OR, or XOR because they
 242     // don't require additional zeroing, which makes them easy.
 243     if (VT == MVT::i1 &&
 244         (ISDOpcode == ISD::AND || ISDOpcode == ISD::OR ||
 245          ISDOpcode == ISD::XOR))
 246       VT = TLI.getTypeToTransformTo(I->getContext(), VT);
 247     else
 248       return false;
 249   }
 250
 251   unsigned Op0 = getRegForValue(I->getOperand(0));
 252   if (Op0 == 0)
 253     // Unhandled operand. Halt "fast" selection and bail.
 254     return false;
 255
 256   bool Op0IsKill = hasTrivialKill(I->getOperand(0));
 257
 258   // Check if the second operand is a constant and handle it appropriately.
 259   if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
 260     unsigned ResultReg = FastEmit_ri(VT.getSimpleVT(), VT.getSimpleVT(),
 261                                      ISDOpcode, Op0, Op0IsKill,
 262                                      CI->getZExtValue());
 263     if (ResultReg != 0) {
 264       // We successfully emitted code for the given LLVM Instruction.
 265       UpdateValueMap(I, ResultReg);
 266       return true;
 267     }
 268   }
 269
 270   // Check if the second operand is a constant float.
 271   if (ConstantFP *CF = dyn_cast<ConstantFP>(I->getOperand(1))) {
 272     unsigned ResultReg = FastEmit_rf(VT.getSimpleVT(), VT.getSimpleVT(),
 273                                      ISDOpcode, Op0, Op0IsKill, CF);
 274     if (ResultReg != 0) {
 275       // We successfully emitted code for the given LLVM Instruction.
 276       UpdateValueMap(I, ResultReg);
 277       return true;
 278     }
 279   }
 280
 281   unsigned Op1 = getRegForValue(I->getOperand(1));
 282   if (Op1 == 0)
 283     // Unhandled operand. Halt "fast" selection and bail.
 284     return false;
 285
 286   bool Op1IsKill = hasTrivialKill(I->getOperand(1));
 287
 288   // Now we have both operands in registers. Emit the instruction.
 289   unsigned ResultReg = FastEmit_rr(VT.getSimpleVT(), VT.getSimpleVT(),
 290                                    ISDOpcode,
 291                                    Op0, Op0IsKill,
 292                                    Op1, Op1IsKill);
 293   if (ResultReg == 0)
 294     // Target-specific code wasn't able to find a machine opcode for
 295     // the given ISD opcode and type. Halt "fast" selection and bail.
 296     return false;
 297
 298   // We successfully emitted code for the given LLVM Instruction.
 299   UpdateValueMap(I, ResultReg);
 300   return true;
 301 }
 302
 303 bool FastISel::SelectGetElementPtr(const User *I) {
 304   unsigned N = getRegForValue(I->getOperand(0));
 305   if (N == 0)
 306     // Unhandled operand. Halt "fast" selection and bail.
 307     return false;
 308
 309   bool NIsKill = hasTrivialKill(I->getOperand(0));
 310
 311   const Type *Ty = I->getOperand(0)->getType();
 312   MVT VT = TLI.getPointerTy();
 313   for (GetElementPtrInst::const_op_iterator OI = I->op_begin()+1,
 314        E = I->op_end(); OI != E; ++OI) {
 315     const Value *Idx = *OI;
 316     if (const StructType *StTy = dyn_cast<StructType>(Ty)) {
 317       unsigned Field = cast<ConstantInt>(Idx)->getZExtValue();
 318       if (Field) {
 319         // N = N + Offset
 320         uint64_t Offs = TD.getStructLayout(StTy)->getElementOffset(Field);
 321         // FIXME: This can be optimized by combining the add with a
 322         // subsequent one.
 323         N = FastEmit_ri_(VT, ISD::ADD, N, NIsKill, Offs, VT);
 324         if (N == 0)
 325           // Unhandled operand. Halt "fast" selection and bail.
 326           return false;
 327         NIsKill = true;
 328       }
 329       Ty = StTy->getElementType(Field);
 330     } else {
 331       Ty = cast<SequentialType>(Ty)->getElementType();
 332
 333       // If this is a constant subscript, handle it quickly.
 334       if (const ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) {
 335         if (CI->getZExtValue() == 0) continue;
 336         uint64_t Offs =
 337           TD.getTypeAllocSize(Ty)*cast<ConstantInt>(CI)->getSExtValue();
 338         N = FastEmit_ri_(VT, ISD::ADD, N, NIsKill, Offs, VT);
 339         if (N == 0)
 340           // Unhandled operand. Halt "fast" selection and bail.
 341           return false;
 342         NIsKill = true;
 343         continue;
 344       }
 345
 346       // N = N + Idx * ElementSize;
 347       uint64_t ElementSize = TD.getTypeAllocSize(Ty);
 348       std::pair<unsigned, bool> Pair = getRegForGEPIndex(Idx);
 349       unsigned IdxN = Pair.first;
 350       bool IdxNIsKill = Pair.second;
 351       if (IdxN == 0)
 352         // Unhandled operand. Halt "fast" selection and bail.
 353         return false;
 354
 355       if (ElementSize != 1) {
 356         IdxN = FastEmit_ri_(VT, ISD::MUL, IdxN, IdxNIsKill, ElementSize, VT);
 357         if (IdxN == 0)
 358           // Unhandled operand. Halt "fast" selection and bail.
 359           return false;
 360         IdxNIsKill = true;
 361       }
 362       N = FastEmit_rr(VT, VT, ISD::ADD, N, NIsKill, IdxN, IdxNIsKill);
 363       if (N == 0)
 364         // Unhandled operand. Halt "fast" selection and bail.
 365         return false;
 366     }
 367   }
 368
 369   // We successfully emitted code for the given LLVM Instruction.
 370   UpdateValueMap(I, N);
 371   return true;
 372 }
 373
 374 bool FastISel::SelectCall(const User *I) {
 375   const Function *F = cast<CallInst>(I)->getCalledFunction();
 376   if (!F) return false;
 377
 378   // Handle selected intrinsic function calls.
 379   unsigned IID = F->getIntrinsicID();
 380   switch (IID) {
 381   default: break;
 382   case Intrinsic::dbg_declare: {
 383     const DbgDeclareInst *DI = cast<DbgDeclareInst>(I);
 384     if (!DIVariable(DI->getVariable()).Verify() ||
 385         !MF.getMMI().hasDebugInfo())
 386       return true;
 387
 388     const Value *Address = DI->getAddress();
 389     if (!Address)
 390       return true;
 391     if (isa<UndefValue>(Address))
 392       return true;
 393     const AllocaInst *AI = dyn_cast<AllocaInst>(Address);
 394     // Don't handle byval struct arguments or VLAs, for example.
 395     // Note that if we have a byval struct argument, fast ISel is turned off;
 396     // those are handled in SelectionDAGBuilder.
 397     if (AI) {
 398       DenseMap<const AllocaInst*, int>::iterator SI =
 399         StaticAllocaMap.find(AI);
 400       if (SI == StaticAllocaMap.end()) break; // VLAs.
 401       int FI = SI->second;
 402       if (!DI->getDebugLoc().isUnknown())
 403         MF.getMMI().setVariableDbgInfo(DI->getVariable(), FI, DI->getDebugLoc());
 404     } else
 405       // Building the map above is target independent.  Generating DBG_VALUE
 406       // inline is target dependent; do this now.
 407       (void)TargetSelectInstruction(cast<Instruction>(I));
 408     return true;
 409   }
 410   case Intrinsic::dbg_value: {
 411     // This form of DBG_VALUE is target-independent.
 412     const DbgValueInst *DI = cast<DbgValueInst>(I);
 413     const TargetInstrDesc &II = TII.get(TargetOpcode::DBG_VALUE);
 414     const Value *V = DI->getValue();
 415     if (!V) {
 416       // Currently the optimizer can produce this; insert an undef to
 417       // help debugging.  Probably the optimizer should not do this.
 418       BuildMI(MBB, DL, II).addReg(0U).addImm(DI->getOffset()).
 419                                      addMetadata(DI->getVariable());
 420     } else if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
 421       BuildMI(MBB, DL, II).addImm(CI->getZExtValue()).addImm(DI->getOffset()).
 422                                      addMetadata(DI->getVariable());
 423     } else if (const ConstantFP *CF = dyn_cast<ConstantFP>(V)) {
 424       BuildMI(MBB, DL, II).addFPImm(CF).addImm(DI->getOffset()).
 425                                      addMetadata(DI->getVariable());
 426     } else if (unsigned Reg = lookUpRegForValue(V)) {
 427       BuildMI(MBB, DL, II).addReg(Reg, RegState::Debug).addImm(DI->getOffset()).
 428                                      addMetadata(DI->getVariable());
 429     } else {
 430       // We can't yet handle anything else here because it would require
 431       // generating code, thus altering codegen because of debug info.
 432       // Insert an undef so we can see what we dropped.
 433       BuildMI(MBB, DL, II).addReg(0U).addImm(DI->getOffset()).
 434                                      addMetadata(DI->getVariable());
 435     }
 436     return true;
 437   }
 438   case Intrinsic::eh_exception: {
 439     EVT VT = TLI.getValueType(I->getType());
 440     switch (TLI.getOperationAction(ISD::EXCEPTIONADDR, VT)) {
 441     default: break;
 442     case TargetLowering::Expand: {
 443       assert(MBB->isLandingPad() && "Call to eh.exception not in landing pad!");
 444       unsigned Reg = TLI.getExceptionAddressRegister();
 445       const TargetRegisterClass *RC = TLI.getRegClassFor(VT);
 446       unsigned ResultReg = createResultReg(RC);
 447       bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
 448                                            Reg, RC, RC, DL);
 449       assert(InsertedCopy && "Can't copy address registers!");
 450       InsertedCopy = InsertedCopy;
 451       UpdateValueMap(I, ResultReg);
 452       return true;
 453     }
 454     }
 455     break;
 456   }
 457   case Intrinsic::eh_selector: {
 458     EVT VT = TLI.getValueType(I->getType());
 459     switch (TLI.getOperationAction(ISD::EHSELECTION, VT)) {
 460     default: break;
 461     case TargetLowering::Expand: {
 462       if (MBB->isLandingPad())
 463         AddCatchInfo(*cast<CallInst>(I), &MF.getMMI(), MBB);
 464       else {
 465 #ifndef NDEBUG
 466         CatchInfoLost.insert(cast<CallInst>(I));
 467 #endif
 468         // FIXME: Mark exception selector register as live in.  Hack for PR1508.
 469         unsigned Reg = TLI.getExceptionSelectorRegister();
 470         if (Reg) MBB->addLiveIn(Reg);
 471       }
 472
 473       unsigned Reg = TLI.getExceptionSelectorRegister();
 474       EVT SrcVT = TLI.getPointerTy();
 475       const TargetRegisterClass *RC = TLI.getRegClassFor(SrcVT);
 476       unsigned ResultReg = createResultReg(RC);
 477       bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg, Reg,
 478                                            RC, RC, DL);
 479       assert(InsertedCopy && "Can't copy address registers!");
 480       InsertedCopy = InsertedCopy;
 481
 482       bool ResultRegIsKill = hasTrivialKill(I);
 483
 484       // Cast the register to the type of the selector.
 485       if (SrcVT.bitsGT(MVT::i32))
 486         ResultReg = FastEmit_r(SrcVT.getSimpleVT(), MVT::i32, ISD::TRUNCATE,
 487                                ResultReg, ResultRegIsKill);
 488       else if (SrcVT.bitsLT(MVT::i32))
 489         ResultReg = FastEmit_r(SrcVT.getSimpleVT(), MVT::i32,
 490                                ISD::SIGN_EXTEND, ResultReg, ResultRegIsKill);
 491       if (ResultReg == 0)
 492         // Unhandled operand. Halt "fast" selection and bail.
 493         return false;
 494
 495       UpdateValueMap(I, ResultReg);
 496
 497       return true;
 498     }
 499     }
 500     break;
 501   }
 502   }
 503
 504   // An arbitrary call. Bail.
 505   return false;
 506 }
 507
 508 bool FastISel::SelectCast(const User *I, unsigned Opcode) {
 509   EVT SrcVT = TLI.getValueType(I->getOperand(0)->getType());
 510   EVT DstVT = TLI.getValueType(I->getType());
 511
 512   if (SrcVT == MVT::Other || !SrcVT.isSimple() ||
 513       DstVT == MVT::Other || !DstVT.isSimple())
 514     // Unhandled type. Halt "fast" selection and bail.
 515     return false;
 516
 517   // Check if the destination type is legal. Or as a special case,
 518   // it may be i1 if we're doing a truncate because that's
 519   // easy and somewhat common.
 520   if (!TLI.isTypeLegal(DstVT))
 521     if (DstVT != MVT::i1 || Opcode != ISD::TRUNCATE)
 522       // Unhandled type. Halt "fast" selection and bail.
 523       return false;
 524
 525   // Check if the source operand is legal. Or as a special case,
 526   // it may be i1 if we're doing zero-extension because that's
 527   // easy and somewhat common.
 528   if (!TLI.isTypeLegal(SrcVT))
 529     if (SrcVT != MVT::i1 || Opcode != ISD::ZERO_EXTEND)
 530       // Unhandled type. Halt "fast" selection and bail.
 531       return false;
 532
 533   unsigned InputReg = getRegForValue(I->getOperand(0));
 534   if (!InputReg)
 535     // Unhandled operand.  Halt "fast" selection and bail.
 536     return false;
 537
 538   bool InputRegIsKill = hasTrivialKill(I->getOperand(0));
 539
 540   // If the operand is i1, arrange for the high bits in the register to be zero.
 541   if (SrcVT == MVT::i1) {
 542    SrcVT = TLI.getTypeToTransformTo(I->getContext(), SrcVT);
 543    InputReg = FastEmitZExtFromI1(SrcVT.getSimpleVT(), InputReg, InputRegIsKill);
 544    if (!InputReg)
 545      return false;
 546    InputRegIsKill = true;
 547   }
 548   // If the result is i1, truncate to the target's type for i1 first.
 549   if (DstVT == MVT::i1)
 550     DstVT = TLI.getTypeToTransformTo(I->getContext(), DstVT);
 551
 552   unsigned ResultReg = FastEmit_r(SrcVT.getSimpleVT(),
 553                                   DstVT.getSimpleVT(),
 554                                   Opcode,
 555                                   InputReg, InputRegIsKill);
 556   if (!ResultReg)
 557     return false;
 558
 559   UpdateValueMap(I, ResultReg);
 560   return true;
 561 }
 562
 563 bool FastISel::SelectBitCast(const User *I) {
 564   // If the bitcast doesn't change the type, just use the operand value.
 565   if (I->getType() == I->getOperand(0)->getType()) {
 566     unsigned Reg = getRegForValue(I->getOperand(0));
 567     if (Reg == 0)
 568       return false;
 569     UpdateValueMap(I, Reg);
 570     return true;
 571   }
 572
 573   // Bitcasts of other values become reg-reg copies or BIT_CONVERT operators.
 574   EVT SrcVT = TLI.getValueType(I->getOperand(0)->getType());
 575   EVT DstVT = TLI.getValueType(I->getType());
 576
 577   if (SrcVT == MVT::Other || !SrcVT.isSimple() ||
 578       DstVT == MVT::Other || !DstVT.isSimple() ||
 579       !TLI.isTypeLegal(SrcVT) || !TLI.isTypeLegal(DstVT))
 580     // Unhandled type. Halt "fast" selection and bail.
 581     return false;
 582
 583   unsigned Op0 = getRegForValue(I->getOperand(0));
 584   if (Op0 == 0)
 585     // Unhandled operand. Halt "fast" selection and bail.
 586     return false;
 587
 588   bool Op0IsKill = hasTrivialKill(I->getOperand(0));
 589
 590   // First, try to perform the bitcast by inserting a reg-reg copy.
 591   unsigned ResultReg = 0;
 592   if (SrcVT.getSimpleVT() == DstVT.getSimpleVT()) {
 593     TargetRegisterClass* SrcClass = TLI.getRegClassFor(SrcVT);
 594     TargetRegisterClass* DstClass = TLI.getRegClassFor(DstVT);
 595     ResultReg = createResultReg(DstClass);
 596
 597     bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
 598                                          Op0, DstClass, SrcClass, DL);
 599     if (!InsertedCopy)
 600       ResultReg = 0;
 601   }
 602
 603   // If the reg-reg copy failed, select a BIT_CONVERT opcode.
 604   if (!ResultReg)
 605     ResultReg = FastEmit_r(SrcVT.getSimpleVT(), DstVT.getSimpleVT(),
 606                            ISD::BIT_CONVERT, Op0, Op0IsKill);
 607
 608   if (!ResultReg)
 609     return false;
 610
 611   UpdateValueMap(I, ResultReg);
 612   return true;
 613 }
 614
 615 bool
 616 FastISel::SelectInstruction(const Instruction *I) {
 617   // Just before the terminator instruction, insert instructions to
 618   // feed PHI nodes in successor blocks.
 619   if (isa<TerminatorInst>(I))
 620     if (!HandlePHINodesInSuccessorBlocks(I->getParent()))
 621       return false;
 622
 623   DL = I->getDebugLoc();
 624
 625   // First, try doing target-independent selection.
 626   if (SelectOperator(I, I->getOpcode())) {
 627     DL = DebugLoc();
 628     return true;
 629   }
 630
 631   // Next, try calling the target to attempt to handle the instruction.
 632   if (TargetSelectInstruction(I)) {
 633     DL = DebugLoc();
 634     return true;
 635   }
 636
 637   DL = DebugLoc();
 638   return false;
 639 }
 640
 641 /// FastEmitBranch - Emit an unconditional branch to the given block,
 642 /// unless it is the immediate (fall-through) successor, and update
 643 /// the CFG.
 644 void
 645 FastISel::FastEmitBranch(MachineBasicBlock *MSucc) {
 646   if (MBB->isLayoutSuccessor(MSucc)) {
 647     // The unconditional fall-through case, which needs no instructions.
 648   } else {
 649     // The unconditional branch case.
 650     TII.InsertBranch(*MBB, MSucc, NULL, SmallVector<MachineOperand, 0>());
 651   }
 652   MBB->addSuccessor(MSucc);
 653 }
 654
 655 /// SelectFNeg - Emit an FNeg operation.
 656 ///
 657 bool
 658 FastISel::SelectFNeg(const User *I) {
 659   unsigned OpReg = getRegForValue(BinaryOperator::getFNegArgument(I));
 660   if (OpReg == 0) return false;
 661
 662   bool OpRegIsKill = hasTrivialKill(I);
 663
 664   // If the target has ISD::FNEG, use it.
 665   EVT VT = TLI.getValueType(I->getType());
 666   unsigned ResultReg = FastEmit_r(VT.getSimpleVT(), VT.getSimpleVT(),
 667                                   ISD::FNEG, OpReg, OpRegIsKill);
 668   if (ResultReg != 0) {
 669     UpdateValueMap(I, ResultReg);
 670     return true;
 671   }
 672
 673   // Bitcast the value to integer, twiddle the sign bit with xor,
 674   // and then bitcast it back to floating-point.
 675   if (VT.getSizeInBits() > 64) return false;
 676   EVT IntVT = EVT::getIntegerVT(I->getContext(), VT.getSizeInBits());
 677   if (!TLI.isTypeLegal(IntVT))
 678     return false;
 679
 680   unsigned IntReg = FastEmit_r(VT.getSimpleVT(), IntVT.getSimpleVT(),
 681                                ISD::BIT_CONVERT, OpReg, OpRegIsKill);
 682   if (IntReg == 0)
 683     return false;
 684
 685   unsigned IntResultReg = FastEmit_ri_(IntVT.getSimpleVT(), ISD::XOR,
 686                                        IntReg, /*Kill=*/true,
 687                                        UINT64_C(1) << (VT.getSizeInBits()-1),
 688                                        IntVT.getSimpleVT());
 689   if (IntResultReg == 0)
 690     return false;
 691
 692   ResultReg = FastEmit_r(IntVT.getSimpleVT(), VT.getSimpleVT(),
 693                          ISD::BIT_CONVERT, IntResultReg, /*Kill=*/true);
 694   if (ResultReg == 0)
 695     return false;
 696
 697   UpdateValueMap(I, ResultReg);
 698   return true;
 699 }
 700
 701 bool
 702 FastISel::SelectOperator(const User *I, unsigned Opcode) {
 703   switch (Opcode) {
 704   case Instruction::Add:
 705     return SelectBinaryOp(I, ISD::ADD);
 706   case Instruction::FAdd:
 707     return SelectBinaryOp(I, ISD::FADD);
 708   case Instruction::Sub:
 709     return SelectBinaryOp(I, ISD::SUB);
 710   case Instruction::FSub:
 711     // FNeg is currently represented in LLVM IR as a special case of FSub.
 712     if (BinaryOperator::isFNeg(I))
 713       return SelectFNeg(I);
 714     return SelectBinaryOp(I, ISD::FSUB);
 715   case Instruction::Mul:
 716     return SelectBinaryOp(I, ISD::MUL);
 717   case Instruction::FMul:
 718     return SelectBinaryOp(I, ISD::FMUL);
 719   case Instruction::SDiv:
 720     return SelectBinaryOp(I, ISD::SDIV);
 721   case Instruction::UDiv:
 722     return SelectBinaryOp(I, ISD::UDIV);
 723   case Instruction::FDiv:
 724     return SelectBinaryOp(I, ISD::FDIV);
 725   case Instruction::SRem:
 726     return SelectBinaryOp(I, ISD::SREM);
 727   case Instruction::URem:
 728     return SelectBinaryOp(I, ISD::UREM);
 729   case Instruction::FRem:
 730     return SelectBinaryOp(I, ISD::FREM);
 731   case Instruction::Shl:
 732     return SelectBinaryOp(I, ISD::SHL);
 733   case Instruction::LShr:
 734     return SelectBinaryOp(I, ISD::SRL);
 735   case Instruction::AShr:
 736     return SelectBinaryOp(I, ISD::SRA);
 737   case Instruction::And:
 738     return SelectBinaryOp(I, ISD::AND);
 739   case Instruction::Or:
 740     return SelectBinaryOp(I, ISD::OR);
 741   case Instruction::Xor:
 742     return SelectBinaryOp(I, ISD::XOR);
 743
 744   case Instruction::GetElementPtr:
 745     return SelectGetElementPtr(I);
 746
 747   case Instruction::Br: {
 748     const BranchInst *BI = cast<BranchInst>(I);
 749
 750     if (BI->isUnconditional()) {
 751       const BasicBlock *LLVMSucc = BI->getSuccessor(0);
 752       MachineBasicBlock *MSucc = MBBMap[LLVMSucc];
 753       FastEmitBranch(MSucc);
 754       return true;
 755     }
 756
 757     // Conditional branches are not handed yet.
 758     // Halt "fast" selection and bail.
 759     return false;
 760   }
 761
 762   case Instruction::Unreachable:
 763     // Nothing to emit.
 764     return true;
 765
 766   case Instruction::Alloca:
 767     // FunctionLowering has the static-sized case covered.
 768     if (StaticAllocaMap.count(cast<AllocaInst>(I)))
 769       return true;
 770
 771     // Dynamic-sized alloca is not handled yet.
 772     return false;
 773
 774   case Instruction::Call:
 775     return SelectCall(I);
 776
 777   case Instruction::BitCast:
 778     return SelectBitCast(I);
 779
 780   case Instruction::FPToSI:
 781     return SelectCast(I, ISD::FP_TO_SINT);
 782   case Instruction::ZExt:
 783     return SelectCast(I, ISD::ZERO_EXTEND);
 784   case Instruction::SExt:
 785     return SelectCast(I, ISD::SIGN_EXTEND);
 786   case Instruction::Trunc:
 787     return SelectCast(I, ISD::TRUNCATE);
 788   case Instruction::SIToFP:
 789     return SelectCast(I, ISD::SINT_TO_FP);
 790
 791   case Instruction::IntToPtr: // Deliberate fall-through.
 792   case Instruction::PtrToInt: {
 793     EVT SrcVT = TLI.getValueType(I->getOperand(0)->getType());
 794     EVT DstVT = TLI.getValueType(I->getType());
 795     if (DstVT.bitsGT(SrcVT))
 796       return SelectCast(I, ISD::ZERO_EXTEND);
 797     if (DstVT.bitsLT(SrcVT))
 798       return SelectCast(I, ISD::TRUNCATE);
 799     unsigned Reg = getRegForValue(I->getOperand(0));
 800     if (Reg == 0) return false;
 801     UpdateValueMap(I, Reg);
 802     return true;
 803   }
 804
 805   case Instruction::PHI:
 806     llvm_unreachable("FastISel shouldn't visit PHI nodes!");
 807
 808   default:
 809     // Unhandled instruction. Halt "fast" selection and bail.
 810     return false;
 811   }
 812 }
 813
 814 FastISel::FastISel(MachineFunction &mf,
 815                    DenseMap<const Value *, unsigned> &vm,
 816                    DenseMap<const BasicBlock *, MachineBasicBlock *> &bm,
 817                    DenseMap<const AllocaInst *, int> &am,
 818                    std::vector<std::pair<MachineInstr*, unsigned> > &pn
 819 #ifndef NDEBUG
 820                    , SmallSet<const Instruction *, 8> &cil
 821 #endif
 822                    )
 823   : MBB(0),
 824     ValueMap(vm),
 825     MBBMap(bm),
 826     StaticAllocaMap(am),
 827     PHINodesToUpdate(pn),
 828 #ifndef NDEBUG
 829     CatchInfoLost(cil),
 830 #endif
 831     MF(mf),
 832     MRI(MF.getRegInfo()),
 833     MFI(*MF.getFrameInfo()),
 834     MCP(*MF.getConstantPool()),
 835     TM(MF.getTarget()),
 836     TD(*TM.getTargetData()),
 837     TII(*TM.getInstrInfo()),
 838     TLI(*TM.getTargetLowering()),
 839     IsBottomUp(false) {
 840 }
 841
 842 FastISel::~FastISel() {}
 843
 844 unsigned FastISel::FastEmit_(MVT, MVT,
 845                              unsigned) {
 846   return 0;
 847 }
 848
 849 unsigned FastISel::FastEmit_r(MVT, MVT,
 850                               unsigned,
 851                               unsigned /*Op0*/, bool /*Op0IsKill*/) {
 852   return 0;
 853 }
 854
 855 unsigned FastISel::FastEmit_rr(MVT, MVT,
 856                                unsigned,
 857                                unsigned /*Op0*/, bool /*Op0IsKill*/,
 858                                unsigned /*Op1*/, bool /*Op1IsKill*/) {
 859   return 0;
 860 }
 861
 862 unsigned FastISel::FastEmit_i(MVT, MVT, unsigned, uint64_t /*Imm*/) {
 863   return 0;
 864 }
 865
 866 unsigned FastISel::FastEmit_f(MVT, MVT,
 867                               unsigned, const ConstantFP * /*FPImm*/) {
 868   return 0;
 869 }
 870
 871 unsigned FastISel::FastEmit_ri(MVT, MVT,
 872                                unsigned,
 873                                unsigned /*Op0*/, bool /*Op0IsKill*/,
 874                                uint64_t /*Imm*/) {
 875   return 0;
 876 }
 877
 878 unsigned FastISel::FastEmit_rf(MVT, MVT,
 879                                unsigned,
 880                                unsigned /*Op0*/, bool /*Op0IsKill*/,
 881                                const ConstantFP * /*FPImm*/) {
 882   return 0;
 883 }
 884
 885 unsigned FastISel::FastEmit_rri(MVT, MVT,
 886                                 unsigned,
 887                                 unsigned /*Op0*/, bool /*Op0IsKill*/,
 888                                 unsigned /*Op1*/, bool /*Op1IsKill*/,
 889                                 uint64_t /*Imm*/) {
 890   return 0;
 891 }
 892
 893 /// FastEmit_ri_ - This method is a wrapper of FastEmit_ri. It first tries
 894 /// to emit an instruction with an immediate operand using FastEmit_ri.
 895 /// If that fails, it materializes the immediate into a register and try
 896 /// FastEmit_rr instead.
 897 unsigned FastISel::FastEmit_ri_(MVT VT, unsigned Opcode,
 898                                 unsigned Op0, bool Op0IsKill,
 899                                 uint64_t Imm, MVT ImmType) {
 900   // First check if immediate type is legal. If not, we can't use the ri form.
 901   unsigned ResultReg = FastEmit_ri(VT, VT, Opcode, Op0, Op0IsKill, Imm);
 902   if (ResultReg != 0)
 903     return ResultReg;
 904   unsigned MaterialReg = FastEmit_i(ImmType, ImmType, ISD::Constant, Imm);
 905   if (MaterialReg == 0)
 906     return 0;
 907   return FastEmit_rr(VT, VT, Opcode,
 908                      Op0, Op0IsKill,
 909                      MaterialReg, /*Kill=*/true);
 910 }
 911
 912 /// FastEmit_rf_ - This method is a wrapper of FastEmit_ri. It first tries
 913 /// to emit an instruction with a floating-point immediate operand using
 914 /// FastEmit_rf. If that fails, it materializes the immediate into a register
 915 /// and try FastEmit_rr instead.
 916 unsigned FastISel::FastEmit_rf_(MVT VT, unsigned Opcode,
 917                                 unsigned Op0, bool Op0IsKill,
 918                                 const ConstantFP *FPImm, MVT ImmType) {
 919   // First check if immediate type is legal. If not, we can't use the rf form.
 920   unsigned ResultReg = FastEmit_rf(VT, VT, Opcode, Op0, Op0IsKill, FPImm);
 921   if (ResultReg != 0)
 922     return ResultReg;
 923
 924   // Materialize the constant in a register.
 925   unsigned MaterialReg = FastEmit_f(ImmType, ImmType, ISD::ConstantFP, FPImm);
 926   if (MaterialReg == 0) {
 927     // If the target doesn't have a way to directly enter a floating-point
 928     // value into a register, use an alternate approach.
 929     // TODO: The current approach only supports floating-point constants
 930     // that can be constructed by conversion from integer values. This should
 931     // be replaced by code that creates a load from a constant-pool entry,
 932     // which will require some target-specific work.
 933     const APFloat &Flt = FPImm->getValueAPF();
 934     EVT IntVT = TLI.getPointerTy();
 935
 936     uint64_t x[2];
 937     uint32_t IntBitWidth = IntVT.getSizeInBits();
 938     bool isExact;
 939     (void) Flt.convertToInteger(x, IntBitWidth, /*isSigned=*/true,
 940                              APFloat::rmTowardZero, &isExact);
 941     if (!isExact)
 942       return 0;
 943     APInt IntVal(IntBitWidth, 2, x);
 944
 945     unsigned IntegerReg = FastEmit_i(IntVT.getSimpleVT(), IntVT.getSimpleVT(),
 946                                      ISD::Constant, IntVal.getZExtValue());
 947     if (IntegerReg == 0)
 948       return 0;
 949     MaterialReg = FastEmit_r(IntVT.getSimpleVT(), VT,
 950                              ISD::SINT_TO_FP, IntegerReg, /*Kill=*/true);
 951     if (MaterialReg == 0)
 952       return 0;
 953   }
 954   return FastEmit_rr(VT, VT, Opcode,
 955                      Op0, Op0IsKill,
 956                      MaterialReg, /*Kill=*/true);
 957 }
 958
 959 unsigned FastISel::createResultReg(const TargetRegisterClass* RC) {
 960   return MRI.createVirtualRegister(RC);
 961 }
 962
 963 unsigned FastISel::FastEmitInst_(unsigned MachineInstOpcode,
 964                                  const TargetRegisterClass* RC) {
 965   unsigned ResultReg = createResultReg(RC);
 966   const TargetInstrDesc &II = TII.get(MachineInstOpcode);
 967
 968   BuildMI(MBB, DL, II, ResultReg);
 969   return ResultReg;
 970 }
 971
 972 unsigned FastISel::FastEmitInst_r(unsigned MachineInstOpcode,
 973                                   const TargetRegisterClass *RC,
 974                                   unsigned Op0, bool Op0IsKill) {
 975   unsigned ResultReg = createResultReg(RC);
 976   const TargetInstrDesc &II = TII.get(MachineInstOpcode);
 977
 978   if (II.getNumDefs() >= 1)
 979     BuildMI(MBB, DL, II, ResultReg).addReg(Op0, Op0IsKill * RegState::Kill);
 980   else {
 981     BuildMI(MBB, DL, II).addReg(Op0, Op0IsKill * RegState::Kill);
 982     bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
 983                                          II.ImplicitDefs[0], RC, RC, DL);
 984     if (!InsertedCopy)
 985       ResultReg = 0;
 986   }
 987
 988   return ResultReg;
 989 }
 990
 991 unsigned FastISel::FastEmitInst_rr(unsigned MachineInstOpcode,
 992                                    const TargetRegisterClass *RC,
 993                                    unsigned Op0, bool Op0IsKill,
 994                                    unsigned Op1, bool Op1IsKill) {
 995   unsigned ResultReg = createResultReg(RC);
 996   const TargetInstrDesc &II = TII.get(MachineInstOpcode);
 997
 998   if (II.getNumDefs() >= 1)
 999     BuildMI(MBB, DL, II, ResultReg)
1000       .addReg(Op0, Op0IsKill * RegState::Kill)
1001       .addReg(Op1, Op1IsKill * RegState::Kill);
1002   else {
1003     BuildMI(MBB, DL, II)
1004       .addReg(Op0, Op0IsKill * RegState::Kill)
1005       .addReg(Op1, Op1IsKill * RegState::Kill);
1006     bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
1007                                          II.ImplicitDefs[0], RC, RC, DL);
1008     if (!InsertedCopy)
1009       ResultReg = 0;
1010   }
1011   return ResultReg;
1012 }
1013
1014 unsigned FastISel::FastEmitInst_ri(unsigned MachineInstOpcode,
1015                                    const TargetRegisterClass *RC,
1016                                    unsigned Op0, bool Op0IsKill,
1017                                    uint64_t Imm) {
1018   unsigned ResultReg = createResultReg(RC);
1019   const TargetInstrDesc &II = TII.get(MachineInstOpcode);
1020
1021   if (II.getNumDefs() >= 1)
1022     BuildMI(MBB, DL, II, ResultReg)
1023       .addReg(Op0, Op0IsKill * RegState::Kill)
1024       .addImm(Imm);
1025   else {
1026     BuildMI(MBB, DL, II)
1027       .addReg(Op0, Op0IsKill * RegState::Kill)
1028       .addImm(Imm);
1029     bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
1030                                          II.ImplicitDefs[0], RC, RC, DL);
1031     if (!InsertedCopy)
1032       ResultReg = 0;
1033   }
1034   return ResultReg;
1035 }
1036
1037 unsigned FastISel::FastEmitInst_rf(unsigned MachineInstOpcode,
1038                                    const TargetRegisterClass *RC,
1039                                    unsigned Op0, bool Op0IsKill,
1040                                    const ConstantFP *FPImm) {
1041   unsigned ResultReg = createResultReg(RC);
1042   const TargetInstrDesc &II = TII.get(MachineInstOpcode);
1043
1044   if (II.getNumDefs() >= 1)
1045     BuildMI(MBB, DL, II, ResultReg)
1046       .addReg(Op0, Op0IsKill * RegState::Kill)
1047       .addFPImm(FPImm);
1048   else {
1049     BuildMI(MBB, DL, II)
1050       .addReg(Op0, Op0IsKill * RegState::Kill)
1051       .addFPImm(FPImm);
1052     bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
1053                                          II.ImplicitDefs[0], RC, RC, DL);
1054     if (!InsertedCopy)
1055       ResultReg = 0;
1056   }
1057   return ResultReg;
1058 }
1059
1060 unsigned FastISel::FastEmitInst_rri(unsigned MachineInstOpcode,
1061                                     const TargetRegisterClass *RC,
1062                                     unsigned Op0, bool Op0IsKill,
1063                                     unsigned Op1, bool Op1IsKill,
1064                                     uint64_t Imm) {
1065   unsigned ResultReg = createResultReg(RC);
1066   const TargetInstrDesc &II = TII.get(MachineInstOpcode);
1067
1068   if (II.getNumDefs() >= 1)
1069     BuildMI(MBB, DL, II, ResultReg)
1070       .addReg(Op0, Op0IsKill * RegState::Kill)
1071       .addReg(Op1, Op1IsKill * RegState::Kill)
1072       .addImm(Imm);
1073   else {
1074     BuildMI(MBB, DL, II)
1075       .addReg(Op0, Op0IsKill * RegState::Kill)
1076       .addReg(Op1, Op1IsKill * RegState::Kill)
1077       .addImm(Imm);
1078     bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
1079                                          II.ImplicitDefs[0], RC, RC, DL);
1080     if (!InsertedCopy)
1081       ResultReg = 0;
1082   }
1083   return ResultReg;
1084 }
1085
1086 unsigned FastISel::FastEmitInst_i(unsigned MachineInstOpcode,
1087                                   const TargetRegisterClass *RC,
1088                                   uint64_t Imm) {
1089   unsigned ResultReg = createResultReg(RC);
1090   const TargetInstrDesc &II = TII.get(MachineInstOpcode);
1091
1092   if (II.getNumDefs() >= 1)
1093     BuildMI(MBB, DL, II, ResultReg).addImm(Imm);
1094   else {
1095     BuildMI(MBB, DL, II).addImm(Imm);
1096     bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
1097                                          II.ImplicitDefs[0], RC, RC, DL);
1098     if (!InsertedCopy)
1099       ResultReg = 0;
1100   }
1101   return ResultReg;
1102 }
1103
1104 unsigned FastISel::FastEmitInst_extractsubreg(MVT RetVT,
1105                                               unsigned Op0, bool Op0IsKill,
1106                                               uint32_t Idx) {
1107   const TargetRegisterClass* RC = MRI.getRegClass(Op0);
1108
1109   unsigned ResultReg = createResultReg(TLI.getRegClassFor(RetVT));
1110   const TargetInstrDesc &II = TII.get(TargetOpcode::EXTRACT_SUBREG);
1111
1112   if (II.getNumDefs() >= 1)
1113     BuildMI(MBB, DL, II, ResultReg)
1114       .addReg(Op0, Op0IsKill * RegState::Kill)
1115       .addImm(Idx);
1116   else {
1117     BuildMI(MBB, DL, II)
1118       .addReg(Op0, Op0IsKill * RegState::Kill)
1119       .addImm(Idx);
1120     bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
1121                                          II.ImplicitDefs[0], RC, RC, DL);
1122     if (!InsertedCopy)
1123       ResultReg = 0;
1124   }
1125   return ResultReg;
1126 }
1127
1128 /// FastEmitZExtFromI1 - Emit MachineInstrs to compute the value of Op
1129 /// with all but the least significant bit set to zero.
1130 unsigned FastISel::FastEmitZExtFromI1(MVT VT, unsigned Op0, bool Op0IsKill) {
1131   return FastEmit_ri(VT, VT, ISD::AND, Op0, Op0IsKill, 1);
1132 }
1133
1134 /// HandlePHINodesInSuccessorBlocks - Handle PHI nodes in successor blocks.
1135 /// Emit code to ensure constants are copied into registers when needed.
1136 /// Remember the virtual registers that need to be added to the Machine PHI
1137 /// nodes as input.  We cannot just directly add them, because expansion
1138 /// might result in multiple MBB's for one BB.  As such, the start of the
1139 /// BB might correspond to a different MBB than the end.
1140 bool FastISel::HandlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB) {
1141   const TerminatorInst *TI = LLVMBB->getTerminator();
1142
1143   SmallPtrSet<MachineBasicBlock *, 4> SuccsHandled;
1144   unsigned OrigNumPHINodesToUpdate = PHINodesToUpdate.size();
1145
1146   // Check successor nodes' PHI nodes that expect a constant to be available
1147   // from this block.
1148   for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) {
1149     const BasicBlock *SuccBB = TI->getSuccessor(succ);
1150     if (!isa<PHINode>(SuccBB->begin())) continue;
1151     MachineBasicBlock *SuccMBB = MBBMap[SuccBB];
1152
1153     // If this terminator has multiple identical successors (common for
1154     // switches), only handle each succ once.
1155     if (!SuccsHandled.insert(SuccMBB)) continue;
1156
1157     MachineBasicBlock::iterator MBBI = SuccMBB->begin();
1158
1159     // At this point we know that there is a 1-1 correspondence between LLVM PHI
1160     // nodes and Machine PHI nodes, but the incoming operands have not been
1161     // emitted yet.
1162     for (BasicBlock::const_iterator I = SuccBB->begin();
1163          const PHINode *PN = dyn_cast<PHINode>(I); ++I) {
1164
1165       // Ignore dead phi's.
1166       if (PN->use_empty()) continue;
1167
1168       // Only handle legal types. Two interesting things to note here. First,
1169       // by bailing out early, we may leave behind some dead instructions,
1170       // since SelectionDAG's HandlePHINodesInSuccessorBlocks will insert its
1171       // own moves. Second, this check is necessary becuase FastISel doesn't
1172       // use CreateRegForValue to create registers, so it always creates
1173       // exactly one register for each non-void instruction.
1174       EVT VT = TLI.getValueType(PN->getType(), /*AllowUnknown=*/true);
1175       if (VT == MVT::Other || !TLI.isTypeLegal(VT)) {
1176         // Promote MVT::i1.
1177         if (VT == MVT::i1)
1178           VT = TLI.getTypeToTransformTo(LLVMBB->getContext(), VT);
1179         else {
1180           PHINodesToUpdate.resize(OrigNumPHINodesToUpdate);
1181           return false;
1182         }
1183       }
1184
1185       const Value *PHIOp = PN->getIncomingValueForBlock(LLVMBB);
1186
1187       // Set the DebugLoc for the copy. Prefer the location of the operand
1188       // if there is one; use the location of the PHI otherwise.
1189       DL = PN->getDebugLoc();
1190       if (const Instruction *Inst = dyn_cast<Instruction>(PHIOp))
1191         DL = Inst->getDebugLoc();
1192
1193       unsigned Reg = getRegForValue(PHIOp);
1194       if (Reg == 0) {
1195         PHINodesToUpdate.resize(OrigNumPHINodesToUpdate);
1196         return false;
1197       }
1198       PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg));
1199       DL = DebugLoc();
1200     }
1201   }
1202
1203   return true;
1204 }