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/Target/TargetData.h"
  51 #include "llvm/Target/TargetInstrInfo.h"
  52 #include "llvm/Target/TargetLowering.h"
  53 #include "llvm/Target/TargetMachine.h"
  54 #include "SelectionDAGBuild.h"
  55 using namespace llvm;
  56
  57 unsigned FastISel::getRegForValue(Value *V) {
  58   MVT::SimpleValueType VT = TLI.getValueType(V->getType()).getSimpleVT();
  59
  60   // Ignore illegal types. We must do this before looking up the value
  61   // in ValueMap because Arguments are given virtual registers regardless
  62   // of whether FastISel can handle them.
  63   if (!TLI.isTypeLegal(VT)) {
  64     // Promote MVT::i1 to a legal type though, because it's common and easy.
  65     if (VT == MVT::i1)
  66       VT = TLI.getTypeToTransformTo(VT).getSimpleVT();
  67     else
  68       return 0;
  69   }
  70
  71   // Look up the value to see if we already have a register for it. We
  72   // cache values defined by Instructions across blocks, and other values
  73   // only locally. This is because Instructions already have the SSA
  74   // def-dominatess-use requirement enforced.
  75   if (ValueMap.count(V))
  76     return ValueMap[V];
  77   unsigned Reg = LocalValueMap[V];
  78   if (Reg != 0)
  79     return Reg;
  80
  81   if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
  82     if (CI->getValue().getActiveBits() <= 64)
  83       Reg = FastEmit_i(VT, VT, ISD::Constant, CI->getZExtValue());
  84   } else if (isa<AllocaInst>(V)) {
  85     Reg = TargetMaterializeAlloca(cast<AllocaInst>(V));
  86   } else if (isa<ConstantPointerNull>(V)) {
  87     // Translate this as an integer zero so that it can be
  88     // local-CSE'd with actual integer zeros.
  89     Reg = getRegForValue(Constant::getNullValue(TD.getIntPtrType()));
  90   } else if (ConstantFP *CF = dyn_cast<ConstantFP>(V)) {
  91     Reg = FastEmit_f(VT, VT, ISD::ConstantFP, CF);
  92
  93     if (!Reg) {
  94       const APFloat &Flt = CF->getValueAPF();
  95       MVT IntVT = TLI.getPointerTy();
  96
  97       uint64_t x[2];
  98       uint32_t IntBitWidth = IntVT.getSizeInBits();
  99       bool isExact;
 100       (void) Flt.convertToInteger(x, IntBitWidth, /*isSigned=*/true,
 101                                 APFloat::rmTowardZero, &isExact);
 102       if (isExact) {
 103         APInt IntVal(IntBitWidth, 2, x);
 104
 105         unsigned IntegerReg = getRegForValue(ConstantInt::get(IntVal));
 106         if (IntegerReg != 0)
 107           Reg = FastEmit_r(IntVT.getSimpleVT(), VT, ISD::SINT_TO_FP, IntegerReg);
 108       }
 109     }
 110   } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
 111     if (!SelectOperator(CE, CE->getOpcode())) return 0;
 112     Reg = LocalValueMap[CE];
 113   } else if (isa<UndefValue>(V)) {
 114     Reg = createResultReg(TLI.getRegClassFor(VT));
 115     BuildMI(MBB, TII.get(TargetInstrInfo::IMPLICIT_DEF), Reg);
 116   }
 117
 118   // If target-independent code couldn't handle the value, give target-specific
 119   // code a try.
 120   if (!Reg && isa<Constant>(V))
 121     Reg = TargetMaterializeConstant(cast<Constant>(V));
 122
 123   // Don't cache constant materializations in the general ValueMap.
 124   // To do so would require tracking what uses they dominate.
 125   if (Reg != 0)
 126     LocalValueMap[V] = Reg;
 127   return Reg;
 128 }
 129
 130 unsigned FastISel::lookUpRegForValue(Value *V) {
 131   // Look up the value to see if we already have a register for it. We
 132   // cache values defined by Instructions across blocks, and other values
 133   // only locally. This is because Instructions already have the SSA
 134   // def-dominatess-use requirement enforced.
 135   if (ValueMap.count(V))
 136     return ValueMap[V];
 137   return LocalValueMap[V];
 138 }
 139
 140 /// UpdateValueMap - Update the value map to include the new mapping for this
 141 /// instruction, or insert an extra copy to get the result in a previous
 142 /// determined register.
 143 /// NOTE: This is only necessary because we might select a block that uses
 144 /// a value before we select the block that defines the value.  It might be
 145 /// possible to fix this by selecting blocks in reverse postorder.
 146 void FastISel::UpdateValueMap(Value* I, unsigned Reg) {
 147   if (!isa<Instruction>(I)) {
 148     LocalValueMap[I] = Reg;
 149     return;
 150   }
 151   if (!ValueMap.count(I))
 152     ValueMap[I] = Reg;
 153   else
 154     TII.copyRegToReg(*MBB, MBB->end(), ValueMap[I],
 155                      Reg, MRI.getRegClass(Reg), MRI.getRegClass(Reg));
 156 }
 157
 158 unsigned FastISel::getRegForGEPIndex(Value *Idx) {
 159   unsigned IdxN = getRegForValue(Idx);
 160   if (IdxN == 0)
 161     // Unhandled operand. Halt "fast" selection and bail.
 162     return 0;
 163
 164   // If the index is smaller or larger than intptr_t, truncate or extend it.
 165   MVT PtrVT = TLI.getPointerTy();
 166   MVT IdxVT = MVT::getMVT(Idx->getType(), /*HandleUnknown=*/false);
 167   if (IdxVT.bitsLT(PtrVT))
 168     IdxN = FastEmit_r(IdxVT.getSimpleVT(), PtrVT.getSimpleVT(),
 169                       ISD::SIGN_EXTEND, IdxN);
 170   else if (IdxVT.bitsGT(PtrVT))
 171     IdxN = FastEmit_r(IdxVT.getSimpleVT(), PtrVT.getSimpleVT(),
 172                       ISD::TRUNCATE, IdxN);
 173   return IdxN;
 174 }
 175
 176 /// SelectBinaryOp - Select and emit code for a binary operator instruction,
 177 /// which has an opcode which directly corresponds to the given ISD opcode.
 178 ///
 179 bool FastISel::SelectBinaryOp(User *I, ISD::NodeType ISDOpcode) {
 180   MVT VT = MVT::getMVT(I->getType(), /*HandleUnknown=*/true);
 181   if (VT == MVT::Other || !VT.isSimple())
 182     // Unhandled type. Halt "fast" selection and bail.
 183     return false;
 184
 185   // We only handle legal types. For example, on x86-32 the instruction
 186   // selector contains all of the 64-bit instructions from x86-64,
 187   // under the assumption that i64 won't be used if the target doesn't
 188   // support it.
 189   if (!TLI.isTypeLegal(VT)) {
 190     // MVT::i1 is special. Allow AND, OR, or XOR because they
 191     // don't require additional zeroing, which makes them easy.
 192     if (VT == MVT::i1 &&
 193         (ISDOpcode == ISD::AND || ISDOpcode == ISD::OR ||
 194          ISDOpcode == ISD::XOR))
 195       VT = TLI.getTypeToTransformTo(VT);
 196     else
 197       return false;
 198   }
 199
 200   unsigned Op0 = getRegForValue(I->getOperand(0));
 201   if (Op0 == 0)
 202     // Unhandled operand. Halt "fast" selection and bail.
 203     return false;
 204
 205   // Check if the second operand is a constant and handle it appropriately.
 206   if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
 207     unsigned ResultReg = FastEmit_ri(VT.getSimpleVT(), VT.getSimpleVT(),
 208                                      ISDOpcode, Op0, CI->getZExtValue());
 209     if (ResultReg != 0) {
 210       // We successfully emitted code for the given LLVM Instruction.
 211       UpdateValueMap(I, ResultReg);
 212       return true;
 213     }
 214   }
 215
 216   // Check if the second operand is a constant float.
 217   if (ConstantFP *CF = dyn_cast<ConstantFP>(I->getOperand(1))) {
 218     unsigned ResultReg = FastEmit_rf(VT.getSimpleVT(), VT.getSimpleVT(),
 219                                      ISDOpcode, Op0, CF);
 220     if (ResultReg != 0) {
 221       // We successfully emitted code for the given LLVM Instruction.
 222       UpdateValueMap(I, ResultReg);
 223       return true;
 224     }
 225   }
 226
 227   unsigned Op1 = getRegForValue(I->getOperand(1));
 228   if (Op1 == 0)
 229     // Unhandled operand. Halt "fast" selection and bail.
 230     return false;
 231
 232   // Now we have both operands in registers. Emit the instruction.
 233   unsigned ResultReg = FastEmit_rr(VT.getSimpleVT(), VT.getSimpleVT(),
 234                                    ISDOpcode, Op0, Op1);
 235   if (ResultReg == 0)
 236     // Target-specific code wasn't able to find a machine opcode for
 237     // the given ISD opcode and type. Halt "fast" selection and bail.
 238     return false;
 239
 240   // We successfully emitted code for the given LLVM Instruction.
 241   UpdateValueMap(I, ResultReg);
 242   return true;
 243 }
 244
 245 bool FastISel::SelectGetElementPtr(User *I) {
 246   unsigned N = getRegForValue(I->getOperand(0));
 247   if (N == 0)
 248     // Unhandled operand. Halt "fast" selection and bail.
 249     return false;
 250
 251   const Type *Ty = I->getOperand(0)->getType();
 252   MVT::SimpleValueType VT = TLI.getPointerTy().getSimpleVT();
 253   for (GetElementPtrInst::op_iterator OI = I->op_begin()+1, E = I->op_end();
 254        OI != E; ++OI) {
 255     Value *Idx = *OI;
 256     if (const StructType *StTy = dyn_cast<StructType>(Ty)) {
 257       unsigned Field = cast<ConstantInt>(Idx)->getZExtValue();
 258       if (Field) {
 259         // N = N + Offset
 260         uint64_t Offs = TD.getStructLayout(StTy)->getElementOffset(Field);
 261         // FIXME: This can be optimized by combining the add with a
 262         // subsequent one.
 263         N = FastEmit_ri_(VT, ISD::ADD, N, Offs, VT);
 264         if (N == 0)
 265           // Unhandled operand. Halt "fast" selection and bail.
 266           return false;
 267       }
 268       Ty = StTy->getElementType(Field);
 269     } else {
 270       Ty = cast<SequentialType>(Ty)->getElementType();
 271
 272       // If this is a constant subscript, handle it quickly.
 273       if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) {
 274         if (CI->getZExtValue() == 0) continue;
 275         uint64_t Offs =
 276           TD.getABITypeSize(Ty)*cast<ConstantInt>(CI)->getSExtValue();
 277         N = FastEmit_ri_(VT, ISD::ADD, N, Offs, VT);
 278         if (N == 0)
 279           // Unhandled operand. Halt "fast" selection and bail.
 280           return false;
 281         continue;
 282       }
 283
 284       // N = N + Idx * ElementSize;
 285       uint64_t ElementSize = TD.getABITypeSize(Ty);
 286       unsigned IdxN = getRegForGEPIndex(Idx);
 287       if (IdxN == 0)
 288         // Unhandled operand. Halt "fast" selection and bail.
 289         return false;
 290
 291       if (ElementSize != 1) {
 292         IdxN = FastEmit_ri_(VT, ISD::MUL, IdxN, ElementSize, VT);
 293         if (IdxN == 0)
 294           // Unhandled operand. Halt "fast" selection and bail.
 295           return false;
 296       }
 297       N = FastEmit_rr(VT, VT, ISD::ADD, N, IdxN);
 298       if (N == 0)
 299         // Unhandled operand. Halt "fast" selection and bail.
 300         return false;
 301     }
 302   }
 303
 304   // We successfully emitted code for the given LLVM Instruction.
 305   UpdateValueMap(I, N);
 306   return true;
 307 }
 308
 309 bool FastISel::SelectCall(User *I) {
 310   Function *F = cast<CallInst>(I)->getCalledFunction();
 311   if (!F) return false;
 312
 313   unsigned IID = F->getIntrinsicID();
 314   switch (IID) {
 315   default: break;
 316   case Intrinsic::dbg_stoppoint: {
 317     DbgStopPointInst *SPI = cast<DbgStopPointInst>(I);
 318     if (MMI && SPI->getContext() && MMI->Verify(SPI->getContext())) {
 319       DebugInfoDesc *DD = MMI->getDescFor(SPI->getContext());
 320       assert(DD && "Not a debug information descriptor");
 321       const CompileUnitDesc *CompileUnit = cast<CompileUnitDesc>(DD);
 322       unsigned SrcFile = MMI->RecordSource(CompileUnit);
 323       unsigned Line = SPI->getLine();
 324       unsigned Col = SPI->getColumn();
 325       unsigned ID = MMI->RecordSourceLine(Line, Col, SrcFile);
 326       const TargetInstrDesc &II = TII.get(TargetInstrInfo::DBG_LABEL);
 327       BuildMI(MBB, II).addImm(ID);
 328     }
 329     return true;
 330   }
 331   case Intrinsic::dbg_region_start: {
 332     DbgRegionStartInst *RSI = cast<DbgRegionStartInst>(I);
 333     if (MMI && RSI->getContext() && MMI->Verify(RSI->getContext())) {
 334       unsigned ID = MMI->RecordRegionStart(RSI->getContext());
 335       const TargetInstrDesc &II = TII.get(TargetInstrInfo::DBG_LABEL);
 336       BuildMI(MBB, II).addImm(ID);
 337     }
 338     return true;
 339   }
 340   case Intrinsic::dbg_region_end: {
 341     DbgRegionEndInst *REI = cast<DbgRegionEndInst>(I);
 342     if (MMI && REI->getContext() && MMI->Verify(REI->getContext())) {
 343       unsigned ID = MMI->RecordRegionEnd(REI->getContext());
 344       const TargetInstrDesc &II = TII.get(TargetInstrInfo::DBG_LABEL);
 345       BuildMI(MBB, II).addImm(ID);
 346     }
 347     return true;
 348   }
 349   case Intrinsic::dbg_func_start: {
 350     if (!MMI) return true;
 351     DbgFuncStartInst *FSI = cast<DbgFuncStartInst>(I);
 352     Value *SP = FSI->getSubprogram();
 353     if (SP && MMI->Verify(SP)) {
 354       // llvm.dbg.func.start implicitly defines a dbg_stoppoint which is
 355       // what (most?) gdb expects.
 356       DebugInfoDesc *DD = MMI->getDescFor(SP);
 357       assert(DD && "Not a debug information descriptor");
 358       SubprogramDesc *Subprogram = cast<SubprogramDesc>(DD);
 359       const CompileUnitDesc *CompileUnit = Subprogram->getFile();
 360       unsigned SrcFile = MMI->RecordSource(CompileUnit);
 361       // Record the source line but does not create a label for the normal
 362       // function start. It will be emitted at asm emission time. However,
 363       // create a label if this is a beginning of inlined function.
 364       unsigned LabelID = MMI->RecordSourceLine(Subprogram->getLine(), 0, SrcFile);
 365       if (MMI->getSourceLines().size() != 1) {
 366         const TargetInstrDesc &II = TII.get(TargetInstrInfo::DBG_LABEL);
 367         BuildMI(MBB, II).addImm(LabelID);
 368       }
 369     }
 370     return true;
 371   }
 372   case Intrinsic::dbg_declare: {
 373     DbgDeclareInst *DI = cast<DbgDeclareInst>(I);
 374     Value *Variable = DI->getVariable();
 375     if (MMI && Variable && MMI->Verify(Variable)) {
 376       // Determine the address of the declared object.
 377       Value *Address = DI->getAddress();
 378       if (BitCastInst *BCI = dyn_cast<BitCastInst>(Address))
 379         Address = BCI->getOperand(0);
 380       AllocaInst *AI = dyn_cast<AllocaInst>(Address);
 381       // Don't handle byval struct arguments, for example.
 382       if (!AI) break;
 383       DenseMap<const AllocaInst*, int>::iterator SI =
 384         StaticAllocaMap.find(AI);
 385       assert(SI != StaticAllocaMap.end() && "Invalid dbg.declare!");
 386       int FI = SI->second;
 387
 388       // Determine the debug globalvariable.
 389       GlobalValue *GV = cast<GlobalVariable>(Variable);
 390
 391       // Build the DECLARE instruction.
 392       const TargetInstrDesc &II = TII.get(TargetInstrInfo::DECLARE);
 393       BuildMI(MBB, II).addFrameIndex(FI).addGlobalAddress(GV);
 394     }
 395     return true;
 396   }
 397   case Intrinsic::eh_exception: {
 398     MVT VT = TLI.getValueType(I->getType());
 399     switch (TLI.getOperationAction(ISD::EXCEPTIONADDR, VT)) {
 400     default: break;
 401     case TargetLowering::Expand: {
 402       if (!MBB->isLandingPad()) {
 403         // FIXME: Mark exception register as live in.  Hack for PR1508.
 404         unsigned Reg = TLI.getExceptionAddressRegister();
 405         if (Reg) MBB->addLiveIn(Reg);
 406       }
 407       unsigned Reg = TLI.getExceptionAddressRegister();
 408       const TargetRegisterClass *RC = TLI.getRegClassFor(VT);
 409       unsigned ResultReg = createResultReg(RC);
 410       bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
 411                                            Reg, RC, RC);
 412       assert(InsertedCopy && "Can't copy address registers!");
 413       InsertedCopy = InsertedCopy;
 414       UpdateValueMap(I, ResultReg);
 415       return true;
 416     }
 417     }
 418     break;
 419   }
 420   case Intrinsic::eh_selector_i32:
 421   case Intrinsic::eh_selector_i64: {
 422     MVT VT = TLI.getValueType(I->getType());
 423     switch (TLI.getOperationAction(ISD::EHSELECTION, VT)) {
 424     default: break;
 425     case TargetLowering::Expand: {
 426       MVT VT = (IID == Intrinsic::eh_selector_i32 ?
 427                            MVT::i32 : MVT::i64);
 428
 429       if (MMI) {
 430         if (MBB->isLandingPad())
 431           AddCatchInfo(*cast<CallInst>(I), MMI, MBB);
 432         else {
 433 #ifndef NDEBUG
 434           CatchInfoLost.insert(cast<CallInst>(I));
 435 #endif
 436           // FIXME: Mark exception selector register as live in.  Hack for PR1508.
 437           unsigned Reg = TLI.getExceptionSelectorRegister();
 438           if (Reg) MBB->addLiveIn(Reg);
 439         }
 440
 441         unsigned Reg = TLI.getExceptionSelectorRegister();
 442         const TargetRegisterClass *RC = TLI.getRegClassFor(VT);
 443         unsigned ResultReg = createResultReg(RC);
 444         bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
 445                                              Reg, RC, RC);
 446         assert(InsertedCopy && "Can't copy address registers!");
 447         InsertedCopy = InsertedCopy;
 448         UpdateValueMap(I, ResultReg);
 449       } else {
 450         unsigned ResultReg =
 451           getRegForValue(Constant::getNullValue(I->getType()));
 452         UpdateValueMap(I, ResultReg);
 453       }
 454       return true;
 455     }
 456     }
 457     break;
 458   }
 459   }
 460   return false;
 461 }
 462
 463 bool FastISel::SelectCast(User *I, ISD::NodeType Opcode) {
 464   MVT SrcVT = TLI.getValueType(I->getOperand(0)->getType());
 465   MVT DstVT = TLI.getValueType(I->getType());
 466
 467   if (SrcVT == MVT::Other || !SrcVT.isSimple() ||
 468       DstVT == MVT::Other || !DstVT.isSimple() ||
 469       !TLI.isTypeLegal(DstVT))
 470     // Unhandled type. Halt "fast" selection and bail.
 471     return false;
 472
 473   // Check if the source operand is legal. Or as a special case,
 474   // it may be i1 if we're doing zero-extension because that's
 475   // trivially easy and somewhat common.
 476   if (!TLI.isTypeLegal(SrcVT)) {
 477     if (SrcVT == MVT::i1 && Opcode == ISD::ZERO_EXTEND)
 478       SrcVT = TLI.getTypeToTransformTo(SrcVT);
 479     else
 480       // Unhandled type. Halt "fast" selection and bail.
 481       return false;
 482   }
 483
 484   unsigned InputReg = getRegForValue(I->getOperand(0));
 485   if (!InputReg)
 486     // Unhandled operand.  Halt "fast" selection and bail.
 487     return false;
 488
 489   unsigned ResultReg = FastEmit_r(SrcVT.getSimpleVT(),
 490                                   DstVT.getSimpleVT(),
 491                                   Opcode,
 492                                   InputReg);
 493   if (!ResultReg)
 494     return false;
 495
 496   UpdateValueMap(I, ResultReg);
 497   return true;
 498 }
 499
 500 bool FastISel::SelectBitCast(User *I) {
 501   // If the bitcast doesn't change the type, just use the operand value.
 502   if (I->getType() == I->getOperand(0)->getType()) {
 503     unsigned Reg = getRegForValue(I->getOperand(0));
 504     if (Reg == 0)
 505       return false;
 506     UpdateValueMap(I, Reg);
 507     return true;
 508   }
 509
 510   // Bitcasts of other values become reg-reg copies or BIT_CONVERT operators.
 511   MVT SrcVT = TLI.getValueType(I->getOperand(0)->getType());
 512   MVT DstVT = TLI.getValueType(I->getType());
 513
 514   if (SrcVT == MVT::Other || !SrcVT.isSimple() ||
 515       DstVT == MVT::Other || !DstVT.isSimple() ||
 516       !TLI.isTypeLegal(SrcVT) || !TLI.isTypeLegal(DstVT))
 517     // Unhandled type. Halt "fast" selection and bail.
 518     return false;
 519
 520   unsigned Op0 = getRegForValue(I->getOperand(0));
 521   if (Op0 == 0)
 522     // Unhandled operand. Halt "fast" selection and bail.
 523     return false;
 524
 525   // First, try to perform the bitcast by inserting a reg-reg copy.
 526   unsigned ResultReg = 0;
 527   if (SrcVT.getSimpleVT() == DstVT.getSimpleVT()) {
 528     TargetRegisterClass* SrcClass = TLI.getRegClassFor(SrcVT);
 529     TargetRegisterClass* DstClass = TLI.getRegClassFor(DstVT);
 530     ResultReg = createResultReg(DstClass);
 531
 532     bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
 533                                          Op0, DstClass, SrcClass);
 534     if (!InsertedCopy)
 535       ResultReg = 0;
 536   }
 537
 538   // If the reg-reg copy failed, select a BIT_CONVERT opcode.
 539   if (!ResultReg)
 540     ResultReg = FastEmit_r(SrcVT.getSimpleVT(), DstVT.getSimpleVT(),
 541                            ISD::BIT_CONVERT, Op0);
 542
 543   if (!ResultReg)
 544     return false;
 545
 546   UpdateValueMap(I, ResultReg);
 547   return true;
 548 }
 549
 550 bool
 551 FastISel::SelectInstruction(Instruction *I) {
 552   return SelectOperator(I, I->getOpcode());
 553 }
 554
 555 /// FastEmitBranch - Emit an unconditional branch to the given block,
 556 /// unless it is the immediate (fall-through) successor, and update
 557 /// the CFG.
 558 void
 559 FastISel::FastEmitBranch(MachineBasicBlock *MSucc) {
 560   MachineFunction::iterator NextMBB =
 561      next(MachineFunction::iterator(MBB));
 562
 563   if (MBB->isLayoutSuccessor(MSucc)) {
 564     // The unconditional fall-through case, which needs no instructions.
 565   } else {
 566     // The unconditional branch case.
 567     TII.InsertBranch(*MBB, MSucc, NULL, SmallVector<MachineOperand, 0>());
 568   }
 569   MBB->addSuccessor(MSucc);
 570 }
 571
 572 bool
 573 FastISel::SelectOperator(User *I, unsigned Opcode) {
 574   switch (Opcode) {
 575   case Instruction::Add: {
 576     ISD::NodeType Opc = I->getType()->isFPOrFPVector() ? ISD::FADD : ISD::ADD;
 577     return SelectBinaryOp(I, Opc);
 578   }
 579   case Instruction::Sub: {
 580     ISD::NodeType Opc = I->getType()->isFPOrFPVector() ? ISD::FSUB : ISD::SUB;
 581     return SelectBinaryOp(I, Opc);
 582   }
 583   case Instruction::Mul: {
 584     ISD::NodeType Opc = I->getType()->isFPOrFPVector() ? ISD::FMUL : ISD::MUL;
 585     return SelectBinaryOp(I, Opc);
 586   }
 587   case Instruction::SDiv:
 588     return SelectBinaryOp(I, ISD::SDIV);
 589   case Instruction::UDiv:
 590     return SelectBinaryOp(I, ISD::UDIV);
 591   case Instruction::FDiv:
 592     return SelectBinaryOp(I, ISD::FDIV);
 593   case Instruction::SRem:
 594     return SelectBinaryOp(I, ISD::SREM);
 595   case Instruction::URem:
 596     return SelectBinaryOp(I, ISD::UREM);
 597   case Instruction::FRem:
 598     return SelectBinaryOp(I, ISD::FREM);
 599   case Instruction::Shl:
 600     return SelectBinaryOp(I, ISD::SHL);
 601   case Instruction::LShr:
 602     return SelectBinaryOp(I, ISD::SRL);
 603   case Instruction::AShr:
 604     return SelectBinaryOp(I, ISD::SRA);
 605   case Instruction::And:
 606     return SelectBinaryOp(I, ISD::AND);
 607   case Instruction::Or:
 608     return SelectBinaryOp(I, ISD::OR);
 609   case Instruction::Xor:
 610     return SelectBinaryOp(I, ISD::XOR);
 611
 612   case Instruction::GetElementPtr:
 613     return SelectGetElementPtr(I);
 614
 615   case Instruction::Br: {
 616     BranchInst *BI = cast<BranchInst>(I);
 617
 618     if (BI->isUnconditional()) {
 619       BasicBlock *LLVMSucc = BI->getSuccessor(0);
 620       MachineBasicBlock *MSucc = MBBMap[LLVMSucc];
 621       FastEmitBranch(MSucc);
 622       return true;
 623     }
 624
 625     // Conditional branches are not handed yet.
 626     // Halt "fast" selection and bail.
 627     return false;
 628   }
 629
 630   case Instruction::Unreachable:
 631     // Nothing to emit.
 632     return true;
 633
 634   case Instruction::PHI:
 635     // PHI nodes are already emitted.
 636     return true;
 637
 638   case Instruction::Alloca:
 639     // FunctionLowering has the static-sized case covered.
 640     if (StaticAllocaMap.count(cast<AllocaInst>(I)))
 641       return true;
 642
 643     // Dynamic-sized alloca is not handled yet.
 644     return false;
 645
 646   case Instruction::Call:
 647     return SelectCall(I);
 648
 649   case Instruction::BitCast:
 650     return SelectBitCast(I);
 651
 652   case Instruction::FPToSI:
 653     return SelectCast(I, ISD::FP_TO_SINT);
 654   case Instruction::ZExt:
 655     return SelectCast(I, ISD::ZERO_EXTEND);
 656   case Instruction::SExt:
 657     return SelectCast(I, ISD::SIGN_EXTEND);
 658   case Instruction::Trunc:
 659     return SelectCast(I, ISD::TRUNCATE);
 660   case Instruction::SIToFP:
 661     return SelectCast(I, ISD::SINT_TO_FP);
 662
 663   case Instruction::IntToPtr: // Deliberate fall-through.
 664   case Instruction::PtrToInt: {
 665     MVT SrcVT = TLI.getValueType(I->getOperand(0)->getType());
 666     MVT DstVT = TLI.getValueType(I->getType());
 667     if (DstVT.bitsGT(SrcVT))
 668       return SelectCast(I, ISD::ZERO_EXTEND);
 669     if (DstVT.bitsLT(SrcVT))
 670       return SelectCast(I, ISD::TRUNCATE);
 671     unsigned Reg = getRegForValue(I->getOperand(0));
 672     if (Reg == 0) return false;
 673     UpdateValueMap(I, Reg);
 674     return true;
 675   }
 676
 677   default:
 678     // Unhandled instruction. Halt "fast" selection and bail.
 679     return false;
 680   }
 681 }
 682
 683 FastISel::FastISel(MachineFunction &mf,
 684                    MachineModuleInfo *mmi,
 685                    DenseMap<const Value *, unsigned> &vm,
 686                    DenseMap<const BasicBlock *, MachineBasicBlock *> &bm,
 687                    DenseMap<const AllocaInst *, int> &am
 688 #ifndef NDEBUG
 689                    , SmallSet<Instruction*, 8> &cil
 690 #endif
 691                    )
 692   : MBB(0),
 693     ValueMap(vm),
 694     MBBMap(bm),
 695     StaticAllocaMap(am),
 696 #ifndef NDEBUG
 697     CatchInfoLost(cil),
 698 #endif
 699     MF(mf),
 700     MMI(mmi),
 701     MRI(MF.getRegInfo()),
 702     MFI(*MF.getFrameInfo()),
 703     MCP(*MF.getConstantPool()),
 704     TM(MF.getTarget()),
 705     TD(*TM.getTargetData()),
 706     TII(*TM.getInstrInfo()),
 707     TLI(*TM.getTargetLowering()) {
 708 }
 709
 710 FastISel::~FastISel() {}
 711
 712 unsigned FastISel::FastEmit_(MVT::SimpleValueType, MVT::SimpleValueType,
 713                              ISD::NodeType) {
 714   return 0;
 715 }
 716
 717 unsigned FastISel::FastEmit_r(MVT::SimpleValueType, MVT::SimpleValueType,
 718                               ISD::NodeType, unsigned /*Op0*/) {
 719   return 0;
 720 }
 721
 722 unsigned FastISel::FastEmit_rr(MVT::SimpleValueType, MVT::SimpleValueType,
 723                                ISD::NodeType, unsigned /*Op0*/,
 724                                unsigned /*Op0*/) {
 725   return 0;
 726 }
 727
 728 unsigned FastISel::FastEmit_i(MVT::SimpleValueType, MVT::SimpleValueType,
 729                               ISD::NodeType, uint64_t /*Imm*/) {
 730   return 0;
 731 }
 732
 733 unsigned FastISel::FastEmit_f(MVT::SimpleValueType, MVT::SimpleValueType,
 734                               ISD::NodeType, ConstantFP * /*FPImm*/) {
 735   return 0;
 736 }
 737
 738 unsigned FastISel::FastEmit_ri(MVT::SimpleValueType, MVT::SimpleValueType,
 739                                ISD::NodeType, unsigned /*Op0*/,
 740                                uint64_t /*Imm*/) {
 741   return 0;
 742 }
 743
 744 unsigned FastISel::FastEmit_rf(MVT::SimpleValueType, MVT::SimpleValueType,
 745                                ISD::NodeType, unsigned /*Op0*/,
 746                                ConstantFP * /*FPImm*/) {
 747   return 0;
 748 }
 749
 750 unsigned FastISel::FastEmit_rri(MVT::SimpleValueType, MVT::SimpleValueType,
 751                                 ISD::NodeType,
 752                                 unsigned /*Op0*/, unsigned /*Op1*/,
 753                                 uint64_t /*Imm*/) {
 754   return 0;
 755 }
 756
 757 /// FastEmit_ri_ - This method is a wrapper of FastEmit_ri. It first tries
 758 /// to emit an instruction with an immediate operand using FastEmit_ri.
 759 /// If that fails, it materializes the immediate into a register and try
 760 /// FastEmit_rr instead.
 761 unsigned FastISel::FastEmit_ri_(MVT::SimpleValueType VT, ISD::NodeType Opcode,
 762                                 unsigned Op0, uint64_t Imm,
 763                                 MVT::SimpleValueType ImmType) {
 764   // First check if immediate type is legal. If not, we can't use the ri form.
 765   unsigned ResultReg = FastEmit_ri(VT, VT, Opcode, Op0, Imm);
 766   if (ResultReg != 0)
 767     return ResultReg;
 768   unsigned MaterialReg = FastEmit_i(ImmType, ImmType, ISD::Constant, Imm);
 769   if (MaterialReg == 0)
 770     return 0;
 771   return FastEmit_rr(VT, VT, Opcode, Op0, MaterialReg);
 772 }
 773
 774 /// FastEmit_rf_ - This method is a wrapper of FastEmit_ri. It first tries
 775 /// to emit an instruction with a floating-point immediate operand using
 776 /// FastEmit_rf. If that fails, it materializes the immediate into a register
 777 /// and try FastEmit_rr instead.
 778 unsigned FastISel::FastEmit_rf_(MVT::SimpleValueType VT, ISD::NodeType Opcode,
 779                                 unsigned Op0, ConstantFP *FPImm,
 780                                 MVT::SimpleValueType ImmType) {
 781   // First check if immediate type is legal. If not, we can't use the rf form.
 782   unsigned ResultReg = FastEmit_rf(VT, VT, Opcode, Op0, FPImm);
 783   if (ResultReg != 0)
 784     return ResultReg;
 785
 786   // Materialize the constant in a register.
 787   unsigned MaterialReg = FastEmit_f(ImmType, ImmType, ISD::ConstantFP, FPImm);
 788   if (MaterialReg == 0) {
 789     // If the target doesn't have a way to directly enter a floating-point
 790     // value into a register, use an alternate approach.
 791     // TODO: The current approach only supports floating-point constants
 792     // that can be constructed by conversion from integer values. This should
 793     // be replaced by code that creates a load from a constant-pool entry,
 794     // which will require some target-specific work.
 795     const APFloat &Flt = FPImm->getValueAPF();
 796     MVT IntVT = TLI.getPointerTy();
 797
 798     uint64_t x[2];
 799     uint32_t IntBitWidth = IntVT.getSizeInBits();
 800     bool isExact;
 801     (void) Flt.convertToInteger(x, IntBitWidth, /*isSigned=*/true,
 802                              APFloat::rmTowardZero, &isExact);
 803     if (!isExact)
 804       return 0;
 805     APInt IntVal(IntBitWidth, 2, x);
 806
 807     unsigned IntegerReg = FastEmit_i(IntVT.getSimpleVT(), IntVT.getSimpleVT(),
 808                                      ISD::Constant, IntVal.getZExtValue());
 809     if (IntegerReg == 0)
 810       return 0;
 811     MaterialReg = FastEmit_r(IntVT.getSimpleVT(), VT,
 812                              ISD::SINT_TO_FP, IntegerReg);
 813     if (MaterialReg == 0)
 814       return 0;
 815   }
 816   return FastEmit_rr(VT, VT, Opcode, Op0, MaterialReg);
 817 }
 818
 819 unsigned FastISel::createResultReg(const TargetRegisterClass* RC) {
 820   return MRI.createVirtualRegister(RC);
 821 }
 822
 823 unsigned FastISel::FastEmitInst_(unsigned MachineInstOpcode,
 824                                  const TargetRegisterClass* RC) {
 825   unsigned ResultReg = createResultReg(RC);
 826   const TargetInstrDesc &II = TII.get(MachineInstOpcode);
 827
 828   BuildMI(MBB, II, ResultReg);
 829   return ResultReg;
 830 }
 831
 832 unsigned FastISel::FastEmitInst_r(unsigned MachineInstOpcode,
 833                                   const TargetRegisterClass *RC,
 834                                   unsigned Op0) {
 835   unsigned ResultReg = createResultReg(RC);
 836   const TargetInstrDesc &II = TII.get(MachineInstOpcode);
 837
 838   if (II.getNumDefs() >= 1)
 839     BuildMI(MBB, II, ResultReg).addReg(Op0);
 840   else {
 841     BuildMI(MBB, II).addReg(Op0);
 842     bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
 843                                          II.ImplicitDefs[0], RC, RC);
 844     if (!InsertedCopy)
 845       ResultReg = 0;
 846   }
 847
 848   return ResultReg;
 849 }
 850
 851 unsigned FastISel::FastEmitInst_rr(unsigned MachineInstOpcode,
 852                                    const TargetRegisterClass *RC,
 853                                    unsigned Op0, unsigned Op1) {
 854   unsigned ResultReg = createResultReg(RC);
 855   const TargetInstrDesc &II = TII.get(MachineInstOpcode);
 856
 857   if (II.getNumDefs() >= 1)
 858     BuildMI(MBB, II, ResultReg).addReg(Op0).addReg(Op1);
 859   else {
 860     BuildMI(MBB, II).addReg(Op0).addReg(Op1);
 861     bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
 862                                          II.ImplicitDefs[0], RC, RC);
 863     if (!InsertedCopy)
 864       ResultReg = 0;
 865   }
 866   return ResultReg;
 867 }
 868
 869 unsigned FastISel::FastEmitInst_ri(unsigned MachineInstOpcode,
 870                                    const TargetRegisterClass *RC,
 871                                    unsigned Op0, uint64_t Imm) {
 872   unsigned ResultReg = createResultReg(RC);
 873   const TargetInstrDesc &II = TII.get(MachineInstOpcode);
 874
 875   if (II.getNumDefs() >= 1)
 876     BuildMI(MBB, II, ResultReg).addReg(Op0).addImm(Imm);
 877   else {
 878     BuildMI(MBB, II).addReg(Op0).addImm(Imm);
 879     bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
 880                                          II.ImplicitDefs[0], RC, RC);
 881     if (!InsertedCopy)
 882       ResultReg = 0;
 883   }
 884   return ResultReg;
 885 }
 886
 887 unsigned FastISel::FastEmitInst_rf(unsigned MachineInstOpcode,
 888                                    const TargetRegisterClass *RC,
 889                                    unsigned Op0, ConstantFP *FPImm) {
 890   unsigned ResultReg = createResultReg(RC);
 891   const TargetInstrDesc &II = TII.get(MachineInstOpcode);
 892
 893   if (II.getNumDefs() >= 1)
 894     BuildMI(MBB, II, ResultReg).addReg(Op0).addFPImm(FPImm);
 895   else {
 896     BuildMI(MBB, II).addReg(Op0).addFPImm(FPImm);
 897     bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
 898                                          II.ImplicitDefs[0], RC, RC);
 899     if (!InsertedCopy)
 900       ResultReg = 0;
 901   }
 902   return ResultReg;
 903 }
 904
 905 unsigned FastISel::FastEmitInst_rri(unsigned MachineInstOpcode,
 906                                     const TargetRegisterClass *RC,
 907                                     unsigned Op0, unsigned Op1, uint64_t Imm) {
 908   unsigned ResultReg = createResultReg(RC);
 909   const TargetInstrDesc &II = TII.get(MachineInstOpcode);
 910
 911   if (II.getNumDefs() >= 1)
 912     BuildMI(MBB, II, ResultReg).addReg(Op0).addReg(Op1).addImm(Imm);
 913   else {
 914     BuildMI(MBB, II).addReg(Op0).addReg(Op1).addImm(Imm);
 915     bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
 916                                          II.ImplicitDefs[0], RC, RC);
 917     if (!InsertedCopy)
 918       ResultReg = 0;
 919   }
 920   return ResultReg;
 921 }
 922
 923 unsigned FastISel::FastEmitInst_i(unsigned MachineInstOpcode,
 924                                   const TargetRegisterClass *RC,
 925                                   uint64_t Imm) {
 926   unsigned ResultReg = createResultReg(RC);
 927   const TargetInstrDesc &II = TII.get(MachineInstOpcode);
 928
 929   if (II.getNumDefs() >= 1)
 930     BuildMI(MBB, II, ResultReg).addImm(Imm);
 931   else {
 932     BuildMI(MBB, II).addImm(Imm);
 933     bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
 934                                          II.ImplicitDefs[0], RC, RC);
 935     if (!InsertedCopy)
 936       ResultReg = 0;
 937   }
 938   return ResultReg;
 939 }
 940
 941 unsigned FastISel::FastEmitInst_extractsubreg(unsigned Op0, uint32_t Idx) {
 942   const TargetRegisterClass* RC = MRI.getRegClass(Op0);
 943   const TargetRegisterClass* SRC = *(RC->subregclasses_begin()+Idx-1);
 944
 945   unsigned ResultReg = createResultReg(SRC);
 946   const TargetInstrDesc &II = TII.get(TargetInstrInfo::EXTRACT_SUBREG);
 947
 948   if (II.getNumDefs() >= 1)
 949     BuildMI(MBB, II, ResultReg).addReg(Op0).addImm(Idx);
 950   else {
 951     BuildMI(MBB, II).addReg(Op0).addImm(Idx);
 952     bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
 953                                          II.ImplicitDefs[0], RC, RC);
 954     if (!InsertedCopy)
 955       ResultReg = 0;
 956   }
 957   return ResultReg;
 958 }