lib/Target/X86/X86ISelPattern.cpp

   1 //===-- X86ISelPattern.cpp - A pattern matching inst selector for X86 -----===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines a pattern matching instruction selector for X86.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "X86.h"
  15 #include "X86InstrBuilder.h"
  16 #include "X86RegisterInfo.h"
  17 #include "llvm/Constants.h"                   // FIXME: REMOVE
  18 #include "llvm/Function.h"
  19 #include "llvm/CodeGen/MachineConstantPool.h" // FIXME: REMOVE
  20 #include "llvm/CodeGen/MachineFunction.h"
  21 #include "llvm/CodeGen/MachineFrameInfo.h"
  22 #include "llvm/CodeGen/SelectionDAG.h"
  23 #include "llvm/CodeGen/SelectionDAGISel.h"
  24 #include "llvm/CodeGen/SSARegMap.h"
  25 #include "llvm/Target/TargetData.h"
  26 #include "llvm/Target/TargetLowering.h"
  27 #include "llvm/Support/MathExtras.h"
  28 #include "llvm/ADT/Statistic.h"
  29 #include <set>
  30 using namespace llvm;
  31
  32 //===----------------------------------------------------------------------===//
  33 //  X86TargetLowering - X86 Implementation of the TargetLowering interface
  34 namespace {
  35   class X86TargetLowering : public TargetLowering {
  36     int VarArgsFrameIndex;            // FrameIndex for start of varargs area.
  37     int ReturnAddrIndex;              // FrameIndex for return slot.
  38   public:
  39     X86TargetLowering(TargetMachine &TM) : TargetLowering(TM) {
  40       // Set up the TargetLowering object.
  41       addRegisterClass(MVT::i8, X86::R8RegisterClass);
  42       addRegisterClass(MVT::i16, X86::R16RegisterClass);
  43       addRegisterClass(MVT::i32, X86::R32RegisterClass);
  44       addRegisterClass(MVT::f64, X86::RFPRegisterClass);
  45
  46       // FIXME: Eliminate these two classes when legalize can handle promotions
  47       // well.
  48       addRegisterClass(MVT::i1, X86::R8RegisterClass);
  49       addRegisterClass(MVT::f32, X86::RFPRegisterClass);
  50
  51       computeRegisterProperties();
  52
  53       setOperationUnsupported(ISD::MUL, MVT::i8);
  54       setOperationUnsupported(ISD::SELECT, MVT::i1);
  55       setOperationUnsupported(ISD::SELECT, MVT::i8);
  56
  57       addLegalFPImmediate(+0.0); // FLD0
  58       addLegalFPImmediate(+1.0); // FLD1
  59       addLegalFPImmediate(-0.0); // FLD0/FCHS
  60       addLegalFPImmediate(-1.0); // FLD1/FCHS
  61     }
  62
  63     /// LowerArguments - This hook must be implemented to indicate how we should
  64     /// lower the arguments for the specified function, into the specified DAG.
  65     virtual std::vector<SDOperand>
  66     LowerArguments(Function &F, SelectionDAG &DAG);
  67
  68     /// LowerCallTo - This hook lowers an abstract call to a function into an
  69     /// actual call.
  70     virtual std::pair<SDOperand, SDOperand>
  71     LowerCallTo(SDOperand Chain, const Type *RetTy, SDOperand Callee,
  72                 ArgListTy &Args, SelectionDAG &DAG);
  73
  74     virtual std::pair<SDOperand, SDOperand>
  75     LowerVAStart(SDOperand Chain, SelectionDAG &DAG);
  76
  77     virtual std::pair<SDOperand,SDOperand>
  78     LowerVAArgNext(bool isVANext, SDOperand Chain, SDOperand VAList,
  79                    const Type *ArgTy, SelectionDAG &DAG);
  80
  81     virtual std::pair<SDOperand, SDOperand>
  82     LowerFrameReturnAddress(bool isFrameAddr, SDOperand Chain, unsigned Depth,
  83                             SelectionDAG &DAG);
  84   };
  85 }
  86
  87
  88 std::vector<SDOperand>
  89 X86TargetLowering::LowerArguments(Function &F, SelectionDAG &DAG) {
  90   std::vector<SDOperand> ArgValues;
  91
  92   // Add DAG nodes to load the arguments...  On entry to a function on the X86,
  93   // the stack frame looks like this:
  94   //
  95   // [ESP] -- return address
  96   // [ESP + 4] -- first argument (leftmost lexically)
  97   // [ESP + 8] -- second argument, if first argument is four bytes in size
  98   //    ...
  99   //
 100   MachineFunction &MF = DAG.getMachineFunction();
 101   MachineFrameInfo *MFI = MF.getFrameInfo();
 102
 103   unsigned ArgOffset = 0;   // Frame mechanisms handle retaddr slot
 104   for (Function::aiterator I = F.abegin(), E = F.aend(); I != E; ++I) {
 105     MVT::ValueType ObjectVT = getValueType(I->getType());
 106     unsigned ArgIncrement = 4;
 107     unsigned ObjSize;
 108     switch (ObjectVT) {
 109     default: assert(0 && "Unhandled argument type!");
 110     case MVT::i1:
 111     case MVT::i8:  ObjSize = 1;                break;
 112     case MVT::i16: ObjSize = 2;                break;
 113     case MVT::i32: ObjSize = 4;                break;
 114     case MVT::i64: ObjSize = ArgIncrement = 8; break;
 115     case MVT::f32: ObjSize = 4;                break;
 116     case MVT::f64: ObjSize = ArgIncrement = 8; break;
 117     }
 118     // Create the frame index object for this incoming parameter...
 119     int FI = MFI->CreateFixedObject(ObjSize, ArgOffset);
 120
 121     // Create the SelectionDAG nodes corresponding to a load from this parameter
 122     SDOperand FIN = DAG.getFrameIndex(FI, MVT::i32);
 123
 124     // Don't codegen dead arguments.  FIXME: remove this check when we can nuke
 125     // dead loads.
 126     SDOperand ArgValue;
 127     if (!I->use_empty())
 128       ArgValue = DAG.getLoad(ObjectVT, DAG.getEntryNode(), FIN);
 129     else {
 130       if (MVT::isInteger(ObjectVT))
 131         ArgValue = DAG.getConstant(0, ObjectVT);
 132       else
 133         ArgValue = DAG.getConstantFP(0, ObjectVT);
 134     }
 135     ArgValues.push_back(ArgValue);
 136
 137     ArgOffset += ArgIncrement;   // Move on to the next argument...
 138   }
 139
 140   // If the function takes variable number of arguments, make a frame index for
 141   // the start of the first vararg value... for expansion of llvm.va_start.
 142   if (F.isVarArg())
 143     VarArgsFrameIndex = MFI->CreateFixedObject(1, ArgOffset);
 144   ReturnAddrIndex = 0;  // No return address slot generated yet.
 145   return ArgValues;
 146 }
 147
 148 std::pair<SDOperand, SDOperand>
 149 X86TargetLowering::LowerCallTo(SDOperand Chain,
 150                                const Type *RetTy, SDOperand Callee,
 151                                ArgListTy &Args, SelectionDAG &DAG) {
 152   // Count how many bytes are to be pushed on the stack.
 153   unsigned NumBytes = 0;
 154
 155   if (Args.empty()) {
 156     // Save zero bytes.
 157     Chain = DAG.getNode(ISD::ADJCALLSTACKDOWN, MVT::Other, Chain,
 158                         DAG.getConstant(0, getPointerTy()));
 159   } else {
 160     for (unsigned i = 0, e = Args.size(); i != e; ++i)
 161       switch (getValueType(Args[i].second)) {
 162       default: assert(0 && "Unknown value type!");
 163       case MVT::i1:
 164       case MVT::i8:
 165       case MVT::i16:
 166       case MVT::i32:
 167       case MVT::f32:
 168         NumBytes += 4;
 169         break;
 170       case MVT::i64:
 171       case MVT::f64:
 172         NumBytes += 8;
 173         break;
 174       }
 175
 176     Chain = DAG.getNode(ISD::ADJCALLSTACKDOWN, MVT::Other, Chain,
 177                         DAG.getConstant(NumBytes, getPointerTy()));
 178
 179     // Arguments go on the stack in reverse order, as specified by the ABI.
 180     unsigned ArgOffset = 0;
 181     SDOperand StackPtr = DAG.getCopyFromReg(X86::ESP, MVT::i32);
 182     for (unsigned i = 0, e = Args.size(); i != e; ++i) {
 183       unsigned ArgReg;
 184       SDOperand PtrOff = DAG.getConstant(ArgOffset, getPointerTy());
 185       PtrOff = DAG.getNode(ISD::ADD, MVT::i32, StackPtr, PtrOff);
 186
 187       switch (getValueType(Args[i].second)) {
 188       default: assert(0 && "Unexpected ValueType for argument!");
 189       case MVT::i1:
 190       case MVT::i8:
 191       case MVT::i16:
 192         // Promote the integer to 32 bits.  If the input type is signed use a
 193         // sign extend, otherwise use a zero extend.
 194         if (Args[i].second->isSigned())
 195           Args[i].first =DAG.getNode(ISD::SIGN_EXTEND, MVT::i32, Args[i].first);
 196         else
 197           Args[i].first =DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, Args[i].first);
 198
 199         // FALL THROUGH
 200       case MVT::i32:
 201       case MVT::f32:
 202         // FIXME: Note that all of these stores are independent of each other.
 203         Chain = DAG.getNode(ISD::STORE, MVT::Other, Chain,
 204                             Args[i].first, PtrOff);
 205         ArgOffset += 4;
 206         break;
 207       case MVT::i64:
 208       case MVT::f64:
 209         // FIXME: Note that all of these stores are independent of each other.
 210         Chain = DAG.getNode(ISD::STORE, MVT::Other, Chain,
 211                             Args[i].first, PtrOff);
 212         ArgOffset += 8;
 213         break;
 214       }
 215     }
 216   }
 217
 218   std::vector<MVT::ValueType> RetVals;
 219   MVT::ValueType RetTyVT = getValueType(RetTy);
 220   if (RetTyVT != MVT::isVoid)
 221     RetVals.push_back(RetTyVT);
 222   RetVals.push_back(MVT::Other);
 223
 224   SDOperand TheCall = SDOperand(DAG.getCall(RetVals, Chain, Callee), 0);
 225   Chain = TheCall.getValue(RetTyVT != MVT::isVoid);
 226   Chain = DAG.getNode(ISD::ADJCALLSTACKUP, MVT::Other, Chain,
 227                       DAG.getConstant(NumBytes, getPointerTy()));
 228   return std::make_pair(TheCall, Chain);
 229 }
 230
 231 std::pair<SDOperand, SDOperand>
 232 X86TargetLowering::LowerVAStart(SDOperand Chain, SelectionDAG &DAG) {
 233   // vastart just returns the address of the VarArgsFrameIndex slot.
 234   return std::make_pair(DAG.getFrameIndex(VarArgsFrameIndex, MVT::i32), Chain);
 235 }
 236
 237 std::pair<SDOperand,SDOperand> X86TargetLowering::
 238 LowerVAArgNext(bool isVANext, SDOperand Chain, SDOperand VAList,
 239                const Type *ArgTy, SelectionDAG &DAG) {
 240   MVT::ValueType ArgVT = getValueType(ArgTy);
 241   SDOperand Result;
 242   if (!isVANext) {
 243     Result = DAG.getLoad(ArgVT, DAG.getEntryNode(), VAList);
 244   } else {
 245     unsigned Amt;
 246     if (ArgVT == MVT::i32)
 247       Amt = 4;
 248     else {
 249       assert((ArgVT == MVT::i64 || ArgVT == MVT::f64) &&
 250              "Other types should have been promoted for varargs!");
 251       Amt = 8;
 252     }
 253     Result = DAG.getNode(ISD::ADD, VAList.getValueType(), VAList,
 254                          DAG.getConstant(Amt, VAList.getValueType()));
 255   }
 256   return std::make_pair(Result, Chain);
 257 }
 258
 259
 260 std::pair<SDOperand, SDOperand> X86TargetLowering::
 261 LowerFrameReturnAddress(bool isFrameAddress, SDOperand Chain, unsigned Depth,
 262                         SelectionDAG &DAG) {
 263   SDOperand Result;
 264   if (Depth)        // Depths > 0 not supported yet!
 265     Result = DAG.getConstant(0, getPointerTy());
 266   else {
 267     if (ReturnAddrIndex == 0) {
 268       // Set up a frame object for the return address.
 269       MachineFunction &MF = DAG.getMachineFunction();
 270       ReturnAddrIndex = MF.getFrameInfo()->CreateFixedObject(4, -4);
 271     }
 272
 273     SDOperand RetAddrFI = DAG.getFrameIndex(ReturnAddrIndex, MVT::i32);
 274
 275     if (!isFrameAddress)
 276       // Just load the return address
 277       Result = DAG.getLoad(MVT::i32, DAG.getEntryNode(), RetAddrFI);
 278     else
 279       Result = DAG.getNode(ISD::SUB, MVT::i32, RetAddrFI,
 280                            DAG.getConstant(4, MVT::i32));
 281   }
 282   return std::make_pair(Result, Chain);
 283 }
 284
 285
 286
 287
 288
 289 namespace {
 290   Statistic<>
 291   NumFPKill("x86-codegen", "Number of FP_REG_KILL instructions added");
 292
 293   //===--------------------------------------------------------------------===//
 294   /// ISel - X86 specific code to select X86 machine instructions for
 295   /// SelectionDAG operations.
 296   ///
 297   class ISel : public SelectionDAGISel {
 298     /// ContainsFPCode - Every instruction we select that uses or defines a FP
 299     /// register should set this to true.
 300     bool ContainsFPCode;
 301
 302     /// X86Lowering - This object fully describes how to lower LLVM code to an
 303     /// X86-specific SelectionDAG.
 304     X86TargetLowering X86Lowering;
 305
 306
 307     /// ExprMap - As shared expressions are codegen'd, we keep track of which
 308     /// vreg the value is produced in, so we only emit one copy of each compiled
 309     /// tree.
 310     std::map<SDOperand, unsigned> ExprMap;
 311     std::set<SDOperand> LoweredTokens;
 312
 313   public:
 314     ISel(TargetMachine &TM) : SelectionDAGISel(X86Lowering), X86Lowering(TM) {
 315     }
 316
 317     /// InstructionSelectBasicBlock - This callback is invoked by
 318     /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
 319     virtual void InstructionSelectBasicBlock(SelectionDAG &DAG) {
 320       // While we're doing this, keep track of whether we see any FP code for
 321       // FP_REG_KILL insertion.
 322       ContainsFPCode = false;
 323
 324       // Codegen the basic block.
 325       Select(DAG.getRoot());
 326
 327       // Insert FP_REG_KILL instructions into basic blocks that need them.  This
 328       // only occurs due to the floating point stackifier not being aggressive
 329       // enough to handle arbitrary global stackification.
 330       //
 331       // Currently we insert an FP_REG_KILL instruction into each block that
 332       // uses or defines a floating point virtual register.
 333       //
 334       // When the global register allocators (like linear scan) finally update
 335       // live variable analysis, we can keep floating point values in registers
 336       // across basic blocks.  This will be a huge win, but we are waiting on
 337       // the global allocators before we can do this.
 338       //
 339       if (ContainsFPCode && BB->succ_size()) {
 340         BuildMI(*BB, BB->getFirstTerminator(), X86::FP_REG_KILL, 0);
 341         ++NumFPKill;
 342       }
 343
 344       // Clear state used for selection.
 345       ExprMap.clear();
 346       LoweredTokens.clear();
 347     }
 348
 349     void EmitCMP(SDOperand LHS, SDOperand RHS);
 350     bool EmitBranchCC(MachineBasicBlock *Dest, SDOperand Cond);
 351     unsigned SelectExpr(SDOperand N);
 352     bool SelectAddress(SDOperand N, X86AddressMode &AM);
 353     void Select(SDOperand N);
 354   };
 355 }
 356
 357 /// SelectAddress - Add the specified node to the specified addressing mode,
 358 /// returning true if it cannot be done.
 359 bool ISel::SelectAddress(SDOperand N, X86AddressMode &AM) {
 360   switch (N.getOpcode()) {
 361   default: break;
 362   case ISD::FrameIndex:
 363     if (AM.BaseType == X86AddressMode::RegBase && AM.Base.Reg == 0) {
 364       AM.BaseType = X86AddressMode::FrameIndexBase;
 365       AM.Base.FrameIndex = cast<FrameIndexSDNode>(N)->getIndex();
 366       return false;
 367     }
 368     break;
 369   case ISD::GlobalAddress:
 370     if (AM.GV == 0) {
 371       AM.GV = cast<GlobalAddressSDNode>(N)->getGlobal();
 372       return false;
 373     }
 374     break;
 375   case ISD::Constant:
 376     AM.Disp += cast<ConstantSDNode>(N)->getValue();
 377     return false;
 378   case ISD::SHL:
 379     if (AM.IndexReg == 0 || AM.Scale == 1)
 380       if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.Val->getOperand(1))) {
 381         unsigned Val = CN->getValue();
 382         if (Val == 1 || Val == 2 || Val == 3) {
 383           AM.Scale = 1 << Val;
 384           AM.IndexReg = SelectExpr(N.Val->getOperand(0));
 385           return false;
 386         }
 387       }
 388     break;
 389
 390   case ISD::ADD: {
 391     X86AddressMode Backup = AM;
 392     if (!SelectAddress(N.Val->getOperand(0), AM) &&
 393         !SelectAddress(N.Val->getOperand(1), AM))
 394       return false;
 395     AM = Backup;
 396     break;
 397   }
 398   }
 399
 400   if (AM.BaseType != X86AddressMode::RegBase ||
 401       AM.Base.Reg)
 402     return true;
 403
 404   // Default, generate it as a register.
 405   AM.BaseType = X86AddressMode::RegBase;
 406   AM.Base.Reg = SelectExpr(N);
 407   return false;
 408 }
 409
 410 /// Emit2SetCCsAndLogical - Emit the following sequence of instructions,
 411 /// assuming that the temporary registers are in the 8-bit register class.
 412 ///
 413 ///  Tmp1 = setcc1
 414 ///  Tmp2 = setcc2
 415 ///  DestReg = logicalop Tmp1, Tmp2
 416 ///
 417 static void Emit2SetCCsAndLogical(MachineBasicBlock *BB, unsigned SetCC1,
 418                                   unsigned SetCC2, unsigned LogicalOp,
 419                                   unsigned DestReg) {
 420   SSARegMap *RegMap = BB->getParent()->getSSARegMap();
 421   unsigned Tmp1 = RegMap->createVirtualRegister(X86::R8RegisterClass);
 422   unsigned Tmp2 = RegMap->createVirtualRegister(X86::R8RegisterClass);
 423   BuildMI(BB, SetCC1, 0, Tmp1);
 424   BuildMI(BB, SetCC2, 0, Tmp2);
 425   BuildMI(BB, LogicalOp, 2, DestReg).addReg(Tmp1).addReg(Tmp2);
 426 }
 427
 428 /// EmitSetCC - Emit the code to set the specified 8-bit register to 1 if the
 429 /// condition codes match the specified SetCCOpcode.  Note that some conditions
 430 /// require multiple instructions to generate the correct value.
 431 static void EmitSetCC(MachineBasicBlock *BB, unsigned DestReg,
 432                       ISD::CondCode SetCCOpcode, bool isFP) {
 433   unsigned Opc;
 434   if (!isFP) {
 435     switch (SetCCOpcode) {
 436     default: assert(0 && "Illegal integer SetCC!");
 437     case ISD::SETEQ: Opc = X86::SETEr; break;
 438     case ISD::SETGT: Opc = X86::SETGr; break;
 439     case ISD::SETGE: Opc = X86::SETGEr; break;
 440     case ISD::SETLT: Opc = X86::SETLr; break;
 441     case ISD::SETLE: Opc = X86::SETLEr; break;
 442     case ISD::SETNE: Opc = X86::SETNEr; break;
 443     case ISD::SETULT: Opc = X86::SETBr; break;
 444     case ISD::SETUGT: Opc = X86::SETAr; break;
 445     case ISD::SETULE: Opc = X86::SETBEr; break;
 446     case ISD::SETUGE: Opc = X86::SETAEr; break;
 447     }
 448   } else {
 449     // On a floating point condition, the flags are set as follows:
 450     // ZF  PF  CF   op
 451     //  0 | 0 | 0 | X > Y
 452     //  0 | 0 | 1 | X < Y
 453     //  1 | 0 | 0 | X == Y
 454     //  1 | 1 | 1 | unordered
 455     //
 456     switch (SetCCOpcode) {
 457     default: assert(0 && "Invalid FP setcc!");
 458     case ISD::SETUEQ:
 459     case ISD::SETEQ:
 460       Opc = X86::SETEr;    // True if ZF = 1
 461       break;
 462     case ISD::SETOGT:
 463     case ISD::SETGT:
 464       Opc = X86::SETAr;    // True if CF = 0 and ZF = 0
 465       break;
 466     case ISD::SETOGE:
 467     case ISD::SETGE:
 468       Opc = X86::SETAEr;   // True if CF = 0
 469       break;
 470     case ISD::SETULT:
 471     case ISD::SETLT:
 472       Opc = X86::SETBr;    // True if CF = 1
 473       break;
 474     case ISD::SETULE:
 475     case ISD::SETLE:
 476       Opc = X86::SETBEr;   // True if CF = 1 or ZF = 1
 477       break;
 478     case ISD::SETONE:
 479     case ISD::SETNE:
 480       Opc = X86::SETNEr;   // True if ZF = 0
 481       break;
 482     case ISD::SETUO:
 483       Opc = X86::SETPr;    // True if PF = 1
 484       break;
 485     case ISD::SETO:
 486       Opc = X86::SETNPr;   // True if PF = 0
 487       break;
 488     case ISD::SETOEQ:      // !PF & ZF
 489       Emit2SetCCsAndLogical(BB, X86::SETNPr, X86::SETEr, X86::AND8rr, DestReg);
 490       return;
 491     case ISD::SETOLT:      // !PF & CF
 492       Emit2SetCCsAndLogical(BB, X86::SETNPr, X86::SETBr, X86::AND8rr, DestReg);
 493       return;
 494     case ISD::SETOLE:      // !PF & (CF || ZF)
 495       Emit2SetCCsAndLogical(BB, X86::SETNPr, X86::SETBEr, X86::AND8rr, DestReg);
 496       return;
 497     case ISD::SETUGT:      // PF | (!ZF & !CF)
 498       Emit2SetCCsAndLogical(BB, X86::SETPr, X86::SETAr, X86::OR8rr, DestReg);
 499       return;
 500     case ISD::SETUGE:      // PF | !CF
 501       Emit2SetCCsAndLogical(BB, X86::SETPr, X86::SETAEr, X86::OR8rr, DestReg);
 502       return;
 503     case ISD::SETUNE:      // PF | !ZF
 504       Emit2SetCCsAndLogical(BB, X86::SETPr, X86::SETNEr, X86::OR8rr, DestReg);
 505       return;
 506     }
 507   }
 508   BuildMI(BB, Opc, 0, DestReg);
 509 }
 510
 511
 512 /// EmitBranchCC - Emit code into BB that arranges for control to transfer to
 513 /// the Dest block if the Cond condition is true.  If we cannot fold this
 514 /// condition into the branch, return true.
 515 ///
 516 bool ISel::EmitBranchCC(MachineBasicBlock *Dest, SDOperand Cond) {
 517   // FIXME: Evaluate whether it would be good to emit code like (X < Y) | (A >
 518   // B) using two conditional branches instead of one condbr, two setcc's, and
 519   // an or.
 520   if ((Cond.getOpcode() == ISD::OR ||
 521        Cond.getOpcode() == ISD::AND) && Cond.Val->hasOneUse()) {
 522     // And and or set the flags for us, so there is no need to emit a TST of the
 523     // result.  It is only safe to do this if there is only a single use of the
 524     // AND/OR though, otherwise we don't know it will be emitted here.
 525     SelectExpr(Cond);
 526     BuildMI(BB, X86::JNE, 1).addMBB(Dest);
 527     return false;
 528   }
 529
 530   // Codegen br not C -> JE.
 531   if (Cond.getOpcode() == ISD::XOR)
 532     if (ConstantSDNode *NC = dyn_cast<ConstantSDNode>(Cond.Val->getOperand(1)))
 533       if (NC->isAllOnesValue()) {
 534         unsigned CondR = SelectExpr(Cond.Val->getOperand(0));
 535         BuildMI(BB, X86::TEST8rr, 2).addReg(CondR).addReg(CondR);
 536         BuildMI(BB, X86::JE, 1).addMBB(Dest);
 537         return false;
 538       }
 539
 540   SetCCSDNode *SetCC = dyn_cast<SetCCSDNode>(Cond);
 541   if (SetCC == 0)
 542     return true;                       // Can only handle simple setcc's so far.
 543
 544   unsigned Opc;
 545
 546   // Handle integer conditions first.
 547   if (MVT::isInteger(SetCC->getOperand(0).getValueType())) {
 548     switch (SetCC->getCondition()) {
 549     default: assert(0 && "Illegal integer SetCC!");
 550     case ISD::SETEQ: Opc = X86::JE; break;
 551     case ISD::SETGT: Opc = X86::JG; break;
 552     case ISD::SETGE: Opc = X86::JGE; break;
 553     case ISD::SETLT: Opc = X86::JL; break;
 554     case ISD::SETLE: Opc = X86::JLE; break;
 555     case ISD::SETNE: Opc = X86::JNE; break;
 556     case ISD::SETULT: Opc = X86::JB; break;
 557     case ISD::SETUGT: Opc = X86::JA; break;
 558     case ISD::SETULE: Opc = X86::JBE; break;
 559     case ISD::SETUGE: Opc = X86::JAE; break;
 560     }
 561     EmitCMP(SetCC->getOperand(0), SetCC->getOperand(1));
 562     BuildMI(BB, Opc, 1).addMBB(Dest);
 563     return false;
 564   }
 565
 566   ContainsFPCode = true;
 567   unsigned Opc2 = 0;  // Second branch if needed.
 568
 569   // On a floating point condition, the flags are set as follows:
 570   // ZF  PF  CF   op
 571   //  0 | 0 | 0 | X > Y
 572   //  0 | 0 | 1 | X < Y
 573   //  1 | 0 | 0 | X == Y
 574   //  1 | 1 | 1 | unordered
 575   //
 576   switch (SetCC->getCondition()) {
 577   default: assert(0 && "Invalid FP setcc!");
 578   case ISD::SETUEQ:
 579   case ISD::SETEQ:   Opc = X86::JE;  break;     // True if ZF = 1
 580   case ISD::SETOGT:
 581   case ISD::SETGT:   Opc = X86::JA;  break;     // True if CF = 0 and ZF = 0
 582   case ISD::SETOGE:
 583   case ISD::SETGE:   Opc = X86::JAE; break;     // True if CF = 0
 584   case ISD::SETULT:
 585   case ISD::SETLT:   Opc = X86::JB;  break;     // True if CF = 1
 586   case ISD::SETULE:
 587   case ISD::SETLE:   Opc = X86::JBE; break;     // True if CF = 1 or ZF = 1
 588   case ISD::SETONE:
 589   case ISD::SETNE:   Opc = X86::JNE; break;     // True if ZF = 0
 590   case ISD::SETUO:   Opc = X86::JP;  break;     // True if PF = 1
 591   case ISD::SETO:    Opc = X86::JNP; break;     // True if PF = 0
 592   case ISD::SETUGT:      // PF = 1 | (ZF = 0 & CF = 0)
 593     Opc = X86::JA;       // ZF = 0 & CF = 0
 594     Opc2 = X86::JP;      // PF = 1
 595     break;
 596   case ISD::SETUGE:      // PF = 1 | CF = 0
 597     Opc = X86::JAE;      // CF = 0
 598     Opc2 = X86::JP;      // PF = 1
 599     break;
 600   case ISD::SETUNE:      // PF = 1 | ZF = 0
 601     Opc = X86::JNE;      // ZF = 0
 602     Opc2 = X86::JP;      // PF = 1
 603     break;
 604   case ISD::SETOEQ:      // PF = 0 & ZF = 1
 605     //X86::JNP, X86::JE
 606     //X86::AND8rr
 607     return true;    // FIXME: Emit more efficient code for this branch.
 608   case ISD::SETOLT:      // PF = 0 & CF = 1
 609     //X86::JNP, X86::JB
 610     //X86::AND8rr
 611     return true;    // FIXME: Emit more efficient code for this branch.
 612   case ISD::SETOLE:      // PF = 0 & (CF = 1 || ZF = 1)
 613     //X86::JNP, X86::JBE
 614     //X86::AND8rr
 615     return true;    // FIXME: Emit more efficient code for this branch.
 616   }
 617
 618   EmitCMP(SetCC->getOperand(0), SetCC->getOperand(1));
 619   BuildMI(BB, Opc, 1).addMBB(Dest);
 620   if (Opc2)
 621     BuildMI(BB, Opc2, 1).addMBB(Dest);
 622   return false;
 623 }
 624
 625 void ISel::EmitCMP(SDOperand LHS, SDOperand RHS) {
 626   unsigned Tmp1 = SelectExpr(LHS), Opc;
 627   if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(RHS)) {
 628     Opc = 0;
 629     switch (RHS.getValueType()) {
 630     default: break;
 631     case MVT::i1:
 632     case MVT::i8:  Opc = X86::CMP8ri;  break;
 633     case MVT::i16: Opc = X86::CMP16ri; break;
 634     case MVT::i32: Opc = X86::CMP32ri; break;
 635     }
 636     if (Opc) {
 637       BuildMI(BB, Opc, 2).addReg(Tmp1).addImm(CN->getValue());
 638       return;
 639     }
 640   }
 641
 642   switch (LHS.getValueType()) {
 643   default: assert(0 && "Cannot compare this value!");
 644   case MVT::i1:
 645   case MVT::i8:  Opc = X86::CMP8rr;  break;
 646   case MVT::i16: Opc = X86::CMP16rr; break;
 647   case MVT::i32: Opc = X86::CMP32rr; break;
 648   case MVT::f32:
 649   case MVT::f64: Opc = X86::FUCOMIr; ContainsFPCode = true; break;
 650   }
 651   unsigned Tmp2 = SelectExpr(RHS);
 652   BuildMI(BB, Opc, 2).addReg(Tmp1).addReg(Tmp2);
 653 }
 654
 655 unsigned ISel::SelectExpr(SDOperand N) {
 656   unsigned Result;
 657   unsigned Tmp1, Tmp2, Tmp3;
 658   unsigned Opc = 0;
 659
 660   SDNode *Node = N.Val;
 661
 662   if (Node->getOpcode() == ISD::CopyFromReg)
 663     // Just use the specified register as our input.
 664     return dyn_cast<CopyRegSDNode>(Node)->getReg();
 665
 666   // If there are multiple uses of this expression, memorize the
 667   // register it is code generated in, instead of emitting it multiple
 668   // times.
 669   // FIXME: Disabled for our current selection model.
 670   if (1 || !Node->hasOneUse()) {
 671     unsigned &Reg = ExprMap[N];
 672     if (Reg) return Reg;
 673
 674     if (N.getOpcode() != ISD::CALL)
 675       Reg = Result = (N.getValueType() != MVT::Other) ?
 676                          MakeReg(N.getValueType()) : 1;
 677     else {
 678       // If this is a call instruction, make sure to prepare ALL of the result
 679       // values as well as the chain.
 680       if (Node->getNumValues() == 1)
 681         Reg = Result = 1;  // Void call, just a chain.
 682       else {
 683         Result = MakeReg(Node->getValueType(0));
 684         ExprMap[N.getValue(0)] = Result;
 685         for (unsigned i = 1, e = N.Val->getNumValues()-1; i != e; ++i)
 686           ExprMap[N.getValue(i)] = MakeReg(Node->getValueType(i));
 687         ExprMap[SDOperand(Node, Node->getNumValues()-1)] = 1;
 688       }
 689     }
 690   } else {
 691     Result = MakeReg(N.getValueType());
 692   }
 693
 694   switch (N.getOpcode()) {
 695   default:
 696     Node->dump();
 697     assert(0 && "Node not handled!\n");
 698   case ISD::FrameIndex:
 699     Tmp1 = cast<FrameIndexSDNode>(N)->getIndex();
 700     addFrameReference(BuildMI(BB, X86::LEA32r, 4, Result), (int)Tmp1);
 701     return Result;
 702   case ISD::ConstantPool:
 703     Tmp1 = cast<ConstantPoolSDNode>(N)->getIndex();
 704     addConstantPoolReference(BuildMI(BB, X86::LEA32r, 4, Result), Tmp1);
 705     return Result;
 706   case ISD::ConstantFP:
 707     ContainsFPCode = true;
 708     Tmp1 = Result;   // Intermediate Register
 709     if (cast<ConstantFPSDNode>(N)->getValue() < 0.0 ||
 710         cast<ConstantFPSDNode>(N)->isExactlyValue(-0.0))
 711       Tmp1 = MakeReg(MVT::f64);
 712
 713     if (cast<ConstantFPSDNode>(N)->isExactlyValue(+0.0) ||
 714         cast<ConstantFPSDNode>(N)->isExactlyValue(-0.0))
 715       BuildMI(BB, X86::FLD0, 0, Tmp1);
 716     else if (cast<ConstantFPSDNode>(N)->isExactlyValue(+1.0) ||
 717              cast<ConstantFPSDNode>(N)->isExactlyValue(-1.0))
 718       BuildMI(BB, X86::FLD1, 0, Tmp1);
 719     else
 720       assert(0 && "Unexpected constant!");
 721     if (Tmp1 != Result)
 722       BuildMI(BB, X86::FCHS, 1, Result).addReg(Tmp1);
 723     return Result;
 724   case ISD::Constant:
 725     switch (N.getValueType()) {
 726     default: assert(0 && "Cannot use constants of this type!");
 727     case MVT::i1:
 728     case MVT::i8:  Opc = X86::MOV8ri;  break;
 729     case MVT::i16: Opc = X86::MOV16ri; break;
 730     case MVT::i32: Opc = X86::MOV32ri; break;
 731     }
 732     BuildMI(BB, Opc, 1,Result).addImm(cast<ConstantSDNode>(N)->getValue());
 733     return Result;
 734   case ISD::GlobalAddress: {
 735     GlobalValue *GV = cast<GlobalAddressSDNode>(N)->getGlobal();
 736     BuildMI(BB, X86::MOV32ri, 1, Result).addGlobalAddress(GV);
 737     return Result;
 738   }
 739   case ISD::ExternalSymbol: {
 740     const char *Sym = cast<ExternalSymbolSDNode>(N)->getSymbol();
 741     BuildMI(BB, X86::MOV32ri, 1, Result).addExternalSymbol(Sym);
 742     return Result;
 743   }
 744   case ISD::FP_EXTEND:
 745     Tmp1 = SelectExpr(N.getOperand(0));
 746     BuildMI(BB, X86::FpMOV, 1, Result).addReg(Tmp1);
 747     ContainsFPCode = true;
 748     return Result;
 749   case ISD::ZERO_EXTEND: {
 750     int DestIs16 = N.getValueType() == MVT::i16;
 751     int SrcIs16  = N.getOperand(0).getValueType() == MVT::i16;
 752     Tmp1 = SelectExpr(N.getOperand(0));
 753
 754     // FIXME: This hack is here for zero extension casts from bool to i8.  This
 755     // would not be needed if bools were promoted by Legalize.
 756     if (N.getValueType() == MVT::i8) {
 757       BuildMI(BB, X86::MOV8rr, 1, Result).addReg(Tmp1);
 758       return Result;
 759     }
 760
 761     static const unsigned Opc[3] = {
 762       X86::MOVZX32rr8, X86::MOVZX32rr16, X86::MOVZX16rr8
 763     };
 764     BuildMI(BB, Opc[SrcIs16+DestIs16*2], 1, Result).addReg(Tmp1);
 765     return Result;
 766   }
 767   case ISD::SIGN_EXTEND: {
 768     int DestIs16 = N.getValueType() == MVT::i16;
 769     int SrcIs16  = N.getOperand(0).getValueType() == MVT::i16;
 770
 771     // FIXME: Legalize should promote bools to i8!
 772     assert(N.getOperand(0).getValueType() != MVT::i1 &&
 773            "Sign extend from bool not implemented!");
 774
 775     static const unsigned Opc[3] = {
 776       X86::MOVSX32rr8, X86::MOVSX32rr16, X86::MOVSX16rr8
 777     };
 778     Tmp1 = SelectExpr(N.getOperand(0));
 779     BuildMI(BB, Opc[SrcIs16+DestIs16*2], 1, Result).addReg(Tmp1);
 780     return Result;
 781   }
 782   case ISD::TRUNCATE:
 783     // Handle cast of LARGER int to SMALLER int using a move to EAX followed by
 784     // a move out of AX or AL.
 785     switch (N.getOperand(0).getValueType()) {
 786     default: assert(0 && "Unknown truncate!");
 787     case MVT::i8:  Tmp2 = X86::AL;  Opc = X86::MOV8rr;  break;
 788     case MVT::i16: Tmp2 = X86::AX;  Opc = X86::MOV16rr; break;
 789     case MVT::i32: Tmp2 = X86::EAX; Opc = X86::MOV32rr; break;
 790     }
 791     Tmp1 = SelectExpr(N.getOperand(0));
 792     BuildMI(BB, Opc, 1, Tmp2).addReg(Tmp1);
 793
 794     switch (N.getValueType()) {
 795     default: assert(0 && "Unknown truncate!");
 796     case MVT::i1:
 797     case MVT::i8:  Tmp2 = X86::AL;  Opc = X86::MOV8rr;  break;
 798     case MVT::i16: Tmp2 = X86::AX;  Opc = X86::MOV16rr; break;
 799     }
 800     BuildMI(BB, Opc, 1, Result).addReg(Tmp2);
 801     return Result;
 802
 803   case ISD::FP_ROUND:
 804     // Truncate from double to float by storing to memory as float,
 805     // then reading it back into a register.
 806
 807     // Create as stack slot to use.
 808     // FIXME: This should automatically be made by the Legalizer!
 809     Tmp1 = TLI.getTargetData().getFloatAlignment();
 810     Tmp2 = BB->getParent()->getFrameInfo()->CreateStackObject(4, Tmp1);
 811
 812     // Codegen the input.
 813     Tmp1 = SelectExpr(N.getOperand(0));
 814
 815     // Emit the store, then the reload.
 816     addFrameReference(BuildMI(BB, X86::FST32m, 5), Tmp2).addReg(Tmp1);
 817     addFrameReference(BuildMI(BB, X86::FLD32m, 5, Result), Tmp2);
 818     ContainsFPCode = true;
 819     return Result;
 820
 821   case ISD::SINT_TO_FP:
 822   case ISD::UINT_TO_FP: {
 823     // FIXME: Most of this grunt work should be done by legalize!
 824
 825     // Promote the integer to a type supported by FLD.  We do this because there
 826     // are no unsigned FLD instructions, so we must promote an unsigned value to
 827     // a larger signed value, then use FLD on the larger value.
 828     //
 829     MVT::ValueType PromoteType = MVT::Other;
 830     MVT::ValueType SrcTy = N.getOperand(0).getValueType();
 831     unsigned PromoteOpcode = 0;
 832     unsigned RealDestReg = Result;
 833     switch (SrcTy) {
 834     case MVT::i1:
 835     case MVT::i8:
 836       // We don't have the facilities for directly loading byte sized data from
 837       // memory (even signed).  Promote it to 16 bits.
 838       PromoteType = MVT::i16;
 839       PromoteOpcode = Node->getOpcode() == ISD::SINT_TO_FP ?
 840         X86::MOVSX16rr8 : X86::MOVZX16rr8;
 841       break;
 842     case MVT::i16:
 843       if (Node->getOpcode() == ISD::UINT_TO_FP) {
 844         PromoteType = MVT::i32;
 845         PromoteOpcode = X86::MOVZX32rr16;
 846       }
 847       break;
 848     default:
 849       // Don't fild into the real destination.
 850       if (Node->getOpcode() == ISD::UINT_TO_FP)
 851         Result = MakeReg(Node->getValueType(0));
 852       break;
 853     }
 854
 855     Tmp1 = SelectExpr(N.getOperand(0));  // Get the operand register
 856
 857     if (PromoteType != MVT::Other) {
 858       Tmp2 = MakeReg(PromoteType);
 859       BuildMI(BB, PromoteOpcode, 1, Tmp2).addReg(Tmp1);
 860       SrcTy = PromoteType;
 861       Tmp1 = Tmp2;
 862     }
 863
 864     // Spill the integer to memory and reload it from there.
 865     unsigned Size = MVT::getSizeInBits(SrcTy)/8;
 866     MachineFunction *F = BB->getParent();
 867     int FrameIdx = F->getFrameInfo()->CreateStackObject(Size, Size);
 868
 869     switch (SrcTy) {
 870     case MVT::i64:
 871       // FIXME: this won't work for cast [u]long to FP
 872       addFrameReference(BuildMI(BB, X86::MOV32mr, 5),
 873                         FrameIdx).addReg(Tmp1);
 874       addFrameReference(BuildMI(BB, X86::MOV32mr, 5),
 875                         FrameIdx, 4).addReg(Tmp1+1);
 876       addFrameReference(BuildMI(BB, X86::FILD64m, 5, Result), FrameIdx);
 877       break;
 878     case MVT::i32:
 879       addFrameReference(BuildMI(BB, X86::MOV32mr, 5),
 880                         FrameIdx).addReg(Tmp1);
 881       addFrameReference(BuildMI(BB, X86::FILD32m, 5, Result), FrameIdx);
 882       break;
 883     case MVT::i16:
 884       addFrameReference(BuildMI(BB, X86::MOV16mr, 5),
 885                         FrameIdx).addReg(Tmp1);
 886       addFrameReference(BuildMI(BB, X86::FILD16m, 5, Result), FrameIdx);
 887       break;
 888     default: break; // No promotion required.
 889     }
 890
 891     if (Node->getOpcode() == ISD::UINT_TO_FP && SrcTy == MVT::i32) {
 892       // If this is a cast from uint -> double, we need to be careful when if
 893       // the "sign" bit is set.  If so, we don't want to make a negative number,
 894       // we want to make a positive number.  Emit code to add an offset if the
 895       // sign bit is set.
 896
 897       // Compute whether the sign bit is set by shifting the reg right 31 bits.
 898       unsigned IsNeg = MakeReg(MVT::i32);
 899       BuildMI(BB, X86::SHR32ri, 2, IsNeg).addReg(Tmp1).addImm(31);
 900
 901       // Create a CP value that has the offset in one word and 0 in the other.
 902       static ConstantInt *TheOffset = ConstantUInt::get(Type::ULongTy,
 903                                                         0x4f80000000000000ULL);
 904       unsigned CPI = F->getConstantPool()->getConstantPoolIndex(TheOffset);
 905       BuildMI(BB, X86::FADD32m, 5, RealDestReg).addReg(Result)
 906         .addConstantPoolIndex(CPI).addZImm(4).addReg(IsNeg).addSImm(0);
 907
 908     } else if (Node->getOpcode() == ISD::UINT_TO_FP && SrcTy == MVT::i64) {
 909       // We need special handling for unsigned 64-bit integer sources.  If the
 910       // input number has the "sign bit" set, then we loaded it incorrectly as a
 911       // negative 64-bit number.  In this case, add an offset value.
 912
 913       // Emit a test instruction to see if the dynamic input value was signed.
 914       BuildMI(BB, X86::TEST32rr, 2).addReg(Tmp1+1).addReg(Tmp1+1);
 915
 916       // If the sign bit is set, get a pointer to an offset, otherwise get a
 917       // pointer to a zero.
 918       MachineConstantPool *CP = F->getConstantPool();
 919       unsigned Zero = MakeReg(MVT::i32);
 920       Constant *Null = Constant::getNullValue(Type::UIntTy);
 921       addConstantPoolReference(BuildMI(BB, X86::LEA32r, 5, Zero),
 922                                CP->getConstantPoolIndex(Null));
 923       unsigned Offset = MakeReg(MVT::i32);
 924       Constant *OffsetCst = ConstantUInt::get(Type::UIntTy, 0x5f800000);
 925
 926       addConstantPoolReference(BuildMI(BB, X86::LEA32r, 5, Offset),
 927                                CP->getConstantPoolIndex(OffsetCst));
 928       unsigned Addr = MakeReg(MVT::i32);
 929       BuildMI(BB, X86::CMOVS32rr, 2, Addr).addReg(Zero).addReg(Offset);
 930
 931       // Load the constant for an add.  FIXME: this could make an 'fadd' that
 932       // reads directly from memory, but we don't support these yet.
 933       unsigned ConstReg = MakeReg(MVT::f64);
 934       addDirectMem(BuildMI(BB, X86::FLD32m, 4, ConstReg), Addr);
 935
 936       BuildMI(BB, X86::FpADD, 2, RealDestReg).addReg(ConstReg).addReg(Result);
 937     }
 938     return RealDestReg;
 939   }
 940   case ISD::FP_TO_SINT:
 941   case ISD::FP_TO_UINT: {
 942     // FIXME: Most of this grunt work should be done by legalize!
 943     Tmp1 = SelectExpr(N.getOperand(0));  // Get the operand register
 944
 945     // Change the floating point control register to use "round towards zero"
 946     // mode when truncating to an integer value.
 947     //
 948     MachineFunction *F = BB->getParent();
 949     int CWFrameIdx = F->getFrameInfo()->CreateStackObject(2, 2);
 950     addFrameReference(BuildMI(BB, X86::FNSTCW16m, 4), CWFrameIdx);
 951
 952     // Load the old value of the high byte of the control word...
 953     unsigned HighPartOfCW = MakeReg(MVT::i8);
 954     addFrameReference(BuildMI(BB, X86::MOV8rm, 4, HighPartOfCW),
 955                       CWFrameIdx, 1);
 956
 957     // Set the high part to be round to zero...
 958     addFrameReference(BuildMI(BB, X86::MOV8mi, 5),
 959                       CWFrameIdx, 1).addImm(12);
 960
 961     // Reload the modified control word now...
 962     addFrameReference(BuildMI(BB, X86::FLDCW16m, 4), CWFrameIdx);
 963
 964     // Restore the memory image of control word to original value
 965     addFrameReference(BuildMI(BB, X86::MOV8mr, 5),
 966                       CWFrameIdx, 1).addReg(HighPartOfCW);
 967
 968     // We don't have the facilities for directly storing byte sized data to
 969     // memory.  Promote it to 16 bits.  We also must promote unsigned values to
 970     // larger classes because we only have signed FP stores.
 971     MVT::ValueType StoreClass = Node->getValueType(0);
 972     if (StoreClass == MVT::i8 || Node->getOpcode() == ISD::FP_TO_UINT)
 973       switch (StoreClass) {
 974       case MVT::i8:  StoreClass = MVT::i16; break;
 975       case MVT::i16: StoreClass = MVT::i32; break;
 976       case MVT::i32: StoreClass = MVT::i64; break;
 977         // The following treatment of cLong may not be perfectly right,
 978         // but it survives chains of casts of the form
 979         // double->ulong->double.
 980       case MVT::i64:  StoreClass = MVT::i64;  break;
 981       default: assert(0 && "Unknown store class!");
 982       }
 983
 984     // Spill the integer to memory and reload it from there.
 985     unsigned Size = MVT::getSizeInBits(StoreClass)/8;
 986     int FrameIdx = F->getFrameInfo()->CreateStackObject(Size, Size);
 987
 988     switch (StoreClass) {
 989     default: assert(0 && "Unknown store class!");
 990     case MVT::i16:
 991       addFrameReference(BuildMI(BB, X86::FIST16m, 5), FrameIdx).addReg(Tmp1);
 992       break;
 993     case MVT::i32:
 994       addFrameReference(BuildMI(BB, X86::FIST32m, 5), FrameIdx).addReg(Tmp1);
 995       break;
 996     case MVT::i64:
 997       addFrameReference(BuildMI(BB, X86::FISTP64m, 5), FrameIdx).addReg(Tmp1);
 998       break;
 999     }
1000
1001     switch (Node->getValueType(0)) {
1002     default:
1003       assert(0 && "Unknown integer type!");
1004     case MVT::i64:
1005       // FIXME: this isn't gunna work.
1006       addFrameReference(BuildMI(BB, X86::MOV32rm, 4, Result), FrameIdx);
1007       addFrameReference(BuildMI(BB, X86::MOV32rm, 4, Result+1), FrameIdx, 4);
1008     case MVT::i32:
1009       addFrameReference(BuildMI(BB, X86::MOV32rm, 4, Result), FrameIdx);
1010       break;
1011     case MVT::i16:
1012       addFrameReference(BuildMI(BB, X86::MOV16rm, 4, Result), FrameIdx);
1013       break;
1014     case MVT::i8:
1015       addFrameReference(BuildMI(BB, X86::MOV8rm, 4, Result), FrameIdx);
1016       break;
1017     }
1018
1019     // Reload the original control word now.
1020     addFrameReference(BuildMI(BB, X86::FLDCW16m, 4), CWFrameIdx);
1021     return Result;
1022   }
1023   case ISD::ADD:
1024     // See if we can codegen this as an LEA to fold operations together.
1025     if (N.getValueType() == MVT::i32) {
1026       X86AddressMode AM;
1027       if (!SelectAddress(N.getOperand(0), AM) &&
1028           !SelectAddress(N.getOperand(1), AM)) {
1029         // If this is not just an add, emit the LEA.  For a simple add (like
1030         // reg+reg or reg+imm), we just emit an add.  If might be a good idea to
1031         // leave this as LEA, then peephole it to 'ADD' after two address elim
1032         // happens.
1033         if (AM.Scale != 1 || AM.BaseType == X86AddressMode::FrameIndexBase ||
1034             AM.Base.Reg && AM.IndexReg && (AM.Disp || AM.GV)) {
1035           addFullAddress(BuildMI(BB, X86::LEA32r, 4, Result), AM);
1036           return Result;
1037         }
1038       }
1039     }
1040     Tmp1 = SelectExpr(N.getOperand(0));
1041     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1042       Opc = 0;
1043       if (CN->getValue() == 1) {   // add X, 1 -> inc X
1044         switch (N.getValueType()) {
1045         default: assert(0 && "Cannot integer add this type!");
1046         case MVT::i8:  Opc = X86::INC8r; break;
1047         case MVT::i16: Opc = X86::INC16r; break;
1048         case MVT::i32: Opc = X86::INC32r; break;
1049         }
1050       } else if (CN->isAllOnesValue()) { // add X, -1 -> dec X
1051         switch (N.getValueType()) {
1052         default: assert(0 && "Cannot integer add this type!");
1053         case MVT::i8:  Opc = X86::DEC8r; break;
1054         case MVT::i16: Opc = X86::DEC16r; break;
1055         case MVT::i32: Opc = X86::DEC32r; break;
1056         }
1057       }
1058
1059       if (Opc) {
1060         BuildMI(BB, Opc, 1, Result).addReg(Tmp1);
1061         return Result;
1062       }
1063
1064       switch (N.getValueType()) {
1065       default: assert(0 && "Cannot add this type!");
1066       case MVT::i8:  Opc = X86::ADD8ri; break;
1067       case MVT::i16: Opc = X86::ADD16ri; break;
1068       case MVT::i32: Opc = X86::ADD32ri; break;
1069       }
1070       if (Opc) {
1071         BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(CN->getValue());
1072         return Result;
1073       }
1074     }
1075
1076     Tmp2 = SelectExpr(N.getOperand(1));
1077     switch (N.getValueType()) {
1078     default: assert(0 && "Cannot add this type!");
1079     case MVT::i8:  Opc = X86::ADD8rr; break;
1080     case MVT::i16: Opc = X86::ADD16rr; break;
1081     case MVT::i32: Opc = X86::ADD32rr; break;
1082     case MVT::f32:
1083     case MVT::f64: Opc = X86::FpADD; ContainsFPCode = true; break;
1084     }
1085     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1086     return Result;
1087   case ISD::SUB:
1088     if (MVT::isInteger(N.getValueType()))
1089       if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(0)))
1090         if (CN->isNullValue()) {   // 0 - N -> neg N
1091           switch (N.getValueType()) {
1092           default: assert(0 && "Cannot sub this type!");
1093           case MVT::i1:
1094           case MVT::i8:  Opc = X86::NEG8r;  break;
1095           case MVT::i16: Opc = X86::NEG16r; break;
1096           case MVT::i32: Opc = X86::NEG32r; break;
1097           }
1098           Tmp1 = SelectExpr(N.getOperand(1));
1099           BuildMI(BB, Opc, 1, Result).addReg(Tmp1);
1100           return Result;
1101         }
1102
1103     Tmp1 = SelectExpr(N.getOperand(0));
1104     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1105       switch (N.getValueType()) {
1106       default: assert(0 && "Cannot sub this type!");
1107       case MVT::i1:
1108       case MVT::i8:  Opc = X86::SUB8ri;  break;
1109       case MVT::i16: Opc = X86::SUB16ri; break;
1110       case MVT::i32: Opc = X86::SUB32ri; break;
1111       }
1112       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(CN->getValue());
1113       return Result;
1114     }
1115     Tmp2 = SelectExpr(N.getOperand(1));
1116     switch (N.getValueType()) {
1117     default: assert(0 && "Cannot add this type!");
1118     case MVT::i1:
1119     case MVT::i8:  Opc = X86::SUB8rr; break;
1120     case MVT::i16: Opc = X86::SUB16rr; break;
1121     case MVT::i32: Opc = X86::SUB32rr; break;
1122     case MVT::f32:
1123     case MVT::f64: Opc = X86::FpSUB; ContainsFPCode = true; break;
1124     }
1125     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1126     return Result;
1127
1128   case ISD::AND:
1129     Tmp1 = SelectExpr(N.getOperand(0));
1130     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1131       switch (N.getValueType()) {
1132       default: assert(0 && "Cannot add this type!");
1133       case MVT::i1:
1134       case MVT::i8:  Opc = X86::AND8ri;  break;
1135       case MVT::i16: Opc = X86::AND16ri; break;
1136       case MVT::i32: Opc = X86::AND32ri; break;
1137       }
1138       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(CN->getValue());
1139       return Result;
1140     }
1141     Tmp2 = SelectExpr(N.getOperand(1));
1142     switch (N.getValueType()) {
1143     default: assert(0 && "Cannot add this type!");
1144     case MVT::i1:
1145     case MVT::i8:  Opc = X86::AND8rr; break;
1146     case MVT::i16: Opc = X86::AND16rr; break;
1147     case MVT::i32: Opc = X86::AND32rr; break;
1148     }
1149     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1150     return Result;
1151   case ISD::OR:
1152     Tmp1 = SelectExpr(N.getOperand(0));
1153     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1154       switch (N.getValueType()) {
1155       default: assert(0 && "Cannot add this type!");
1156       case MVT::i1:
1157       case MVT::i8:  Opc = X86::OR8ri;  break;
1158       case MVT::i16: Opc = X86::OR16ri; break;
1159       case MVT::i32: Opc = X86::OR32ri; break;
1160       }
1161       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(CN->getValue());
1162       return Result;
1163     }
1164     Tmp2 = SelectExpr(N.getOperand(1));
1165     switch (N.getValueType()) {
1166     default: assert(0 && "Cannot add this type!");
1167     case MVT::i1:
1168     case MVT::i8:  Opc = X86::OR8rr; break;
1169     case MVT::i16: Opc = X86::OR16rr; break;
1170     case MVT::i32: Opc = X86::OR32rr; break;
1171     }
1172     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1173     return Result;
1174   case ISD::XOR:
1175     Tmp1 = SelectExpr(N.getOperand(0));
1176     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1177       switch (N.getValueType()) {
1178       default: assert(0 && "Cannot add this type!");
1179       case MVT::i1:
1180       case MVT::i8:  Opc = X86::XOR8ri;  break;
1181       case MVT::i16: Opc = X86::XOR16ri; break;
1182       case MVT::i32: Opc = X86::XOR32ri; break;
1183       }
1184       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(CN->getValue());
1185       return Result;
1186     }
1187     Tmp2 = SelectExpr(N.getOperand(1));
1188     switch (N.getValueType()) {
1189     default: assert(0 && "Cannot add this type!");
1190     case MVT::i1:
1191     case MVT::i8:  Opc = X86::XOR8rr; break;
1192     case MVT::i16: Opc = X86::XOR16rr; break;
1193     case MVT::i32: Opc = X86::XOR32rr; break;
1194     }
1195     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1196     return Result;
1197
1198   case ISD::MUL:
1199     Tmp1 = SelectExpr(N.getOperand(0));
1200     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1201       Opc = 0;
1202       switch (N.getValueType()) {
1203       default: assert(0 && "Cannot multiply this type!");
1204       case MVT::i8:  break;
1205       case MVT::i16: Opc = X86::IMUL16rri; break;
1206       case MVT::i32: Opc = X86::IMUL32rri; break;
1207       }
1208       if (Opc) {
1209         BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(CN->getValue());
1210         return Result;
1211       }
1212     }
1213     Tmp2 = SelectExpr(N.getOperand(1));
1214     switch (N.getValueType()) {
1215     default: assert(0 && "Cannot add this type!");
1216     case MVT::i8: assert(0 && "FIXME: MUL i8 not implemented yet!");
1217     case MVT::i16: Opc = X86::IMUL16rr; break;
1218     case MVT::i32: Opc = X86::IMUL32rr; break;
1219     case MVT::f32:
1220     case MVT::f64: Opc = X86::FpMUL; ContainsFPCode = true; break;
1221     }
1222     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1223     return Result;
1224
1225   case ISD::SELECT:
1226     // FIXME: implement folding of setcc into select.
1227     if (N.getValueType() != MVT::i1 && N.getValueType() != MVT::i8) {
1228       Tmp2 = SelectExpr(N.getOperand(1));
1229       Tmp3 = SelectExpr(N.getOperand(2));
1230       Tmp1 = SelectExpr(N.getOperand(0));
1231
1232       switch (N.getValueType()) {
1233       default: assert(0 && "Cannot select this type!");
1234       case MVT::i16: Opc = X86::CMOVE16rr; break;
1235       case MVT::i32: Opc = X86::CMOVE32rr; break;
1236       case MVT::f32:
1237       case MVT::f64: Opc = X86::FCMOVE; ContainsFPCode = true; break;
1238       }
1239
1240       // Get the condition into the zero flag.
1241       BuildMI(BB, X86::TEST8rr, 2).addReg(Tmp1).addReg(Tmp1);
1242       BuildMI(BB, Opc, 2, Result).addReg(Tmp2).addReg(Tmp3);
1243       return Result;
1244     } else {
1245       // FIXME: This should not be implemented here, it should be in the generic
1246       // code!
1247       Tmp2 = SelectExpr(CurDAG->getNode(ISD::ZERO_EXTEND, MVT::i16,
1248                                         N.getOperand(1)));
1249       Tmp3 = SelectExpr(CurDAG->getNode(ISD::ZERO_EXTEND, MVT::i16,
1250                                         N.getOperand(2)));
1251       Tmp1 = SelectExpr(N.getOperand(0));
1252       BuildMI(BB, X86::TEST8rr, 2).addReg(Tmp1).addReg(Tmp1);
1253       // FIXME: need subregs to do better than this!
1254       unsigned TmpReg = MakeReg(MVT::i16);
1255       BuildMI(BB, X86::CMOVE16rr, 2, TmpReg).addReg(Tmp2).addReg(Tmp3);
1256       BuildMI(BB, X86::MOV16rr, 1, X86::AX).addReg(TmpReg);
1257       BuildMI(BB, X86::MOV8rr, 1, Result).addReg(X86::AL);
1258       return Result;
1259     }
1260
1261   case ISD::SDIV:
1262   case ISD::UDIV:
1263   case ISD::SREM:
1264   case ISD::UREM: {
1265     Tmp1 = SelectExpr(N.getOperand(0));
1266
1267     if (N.getOpcode() == ISD::SDIV)
1268       if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1269         // FIXME: These special cases should be handled by the lowering impl!
1270         unsigned RHS = CN->getValue();
1271         bool isNeg = false;
1272         if ((int)RHS < 0) {
1273           isNeg = true;
1274           RHS = -RHS;
1275         }
1276         if (RHS && (RHS & (RHS-1)) == 0) {   // Signed division by power of 2?
1277           unsigned Log = log2(RHS);
1278           unsigned TmpReg = MakeReg(N.getValueType());
1279           unsigned SAROpc, SHROpc, ADDOpc, NEGOpc;
1280           switch (N.getValueType()) {
1281           default: assert("Unknown type to signed divide!");
1282           case MVT::i8:
1283             SAROpc = X86::SAR8ri;
1284             SHROpc = X86::SHR8ri;
1285             ADDOpc = X86::ADD8rr;
1286             NEGOpc = X86::NEG8r;
1287             break;
1288           case MVT::i16:
1289             SAROpc = X86::SAR16ri;
1290             SHROpc = X86::SHR16ri;
1291             ADDOpc = X86::ADD16rr;
1292             NEGOpc = X86::NEG16r;
1293             break;
1294           case MVT::i32:
1295             SAROpc = X86::SAR32ri;
1296             SHROpc = X86::SHR32ri;
1297             ADDOpc = X86::ADD32rr;
1298             NEGOpc = X86::NEG32r;
1299             break;
1300           }
1301           BuildMI(BB, SAROpc, 2, TmpReg).addReg(Tmp1).addImm(Log-1);
1302           unsigned TmpReg2 = MakeReg(N.getValueType());
1303           BuildMI(BB, SHROpc, 2, TmpReg2).addReg(TmpReg).addImm(32-Log);
1304           unsigned TmpReg3 = MakeReg(N.getValueType());
1305           BuildMI(BB, ADDOpc, 2, TmpReg3).addReg(Tmp1).addReg(TmpReg2);
1306
1307           unsigned TmpReg4 = isNeg ? MakeReg(N.getValueType()) : Result;
1308           BuildMI(BB, SAROpc, 2, TmpReg4).addReg(TmpReg3).addImm(Log);
1309           if (isNeg)
1310             BuildMI(BB, NEGOpc, 1, Result).addReg(TmpReg4);
1311           return Result;
1312         }
1313       }
1314
1315     Tmp2 = SelectExpr(N.getOperand(1));
1316
1317     bool isSigned = N.getOpcode() == ISD::SDIV || N.getOpcode() == ISD::SREM;
1318     bool isDiv    = N.getOpcode() == ISD::SDIV || N.getOpcode() == ISD::UDIV;
1319     unsigned LoReg, HiReg, DivOpcode, MovOpcode, ClrOpcode, SExtOpcode;
1320     switch (N.getValueType()) {
1321     default: assert(0 && "Cannot sdiv this type!");
1322     case MVT::i8:
1323       DivOpcode = isSigned ? X86::IDIV8r : X86::DIV8r;
1324       LoReg = X86::AL;
1325       HiReg = X86::AH;
1326       MovOpcode = X86::MOV8rr;
1327       ClrOpcode = X86::MOV8ri;
1328       SExtOpcode = X86::CBW;
1329       break;
1330     case MVT::i16:
1331       DivOpcode = isSigned ? X86::IDIV16r : X86::DIV16r;
1332       LoReg = X86::AX;
1333       HiReg = X86::DX;
1334       MovOpcode = X86::MOV16rr;
1335       ClrOpcode = X86::MOV16ri;
1336       SExtOpcode = X86::CWD;
1337       break;
1338     case MVT::i32:
1339       DivOpcode = isSigned ? X86::IDIV32r : X86::DIV32r;
1340       LoReg =X86::EAX;
1341       HiReg = X86::EDX;
1342       MovOpcode = X86::MOV32rr;
1343       ClrOpcode = X86::MOV32ri;
1344       SExtOpcode = X86::CDQ;
1345       break;
1346     case MVT::i64: assert(0 && "FIXME: implement i64 DIV/REM libcalls!");
1347     case MVT::f32:
1348     case MVT::f64:
1349       ContainsFPCode = true;
1350       if (N.getOpcode() == ISD::SDIV)
1351         BuildMI(BB, X86::FpDIV, 2, Result).addReg(Tmp1).addReg(Tmp2);
1352       else
1353         assert(0 && "FIXME: Emit frem libcall to fmod!");
1354       return Result;
1355     }
1356
1357     // Set up the low part.
1358     BuildMI(BB, MovOpcode, 1, LoReg).addReg(Tmp1);
1359
1360     if (isSigned) {
1361       // Sign extend the low part into the high part.
1362       BuildMI(BB, SExtOpcode, 0);
1363     } else {
1364       // Zero out the high part, effectively zero extending the input.
1365       BuildMI(BB, ClrOpcode, 1, HiReg).addImm(0);
1366     }
1367
1368     // Emit the DIV/IDIV instruction.
1369     BuildMI(BB, DivOpcode, 1).addReg(Tmp2);
1370
1371     // Get the result of the divide or rem.
1372     BuildMI(BB, MovOpcode, 1, Result).addReg(isDiv ? LoReg : HiReg);
1373     return Result;
1374   }
1375
1376   case ISD::SHL:
1377     Tmp1 = SelectExpr(N.getOperand(0));
1378     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1379       switch (N.getValueType()) {
1380       default: assert(0 && "Cannot shift this type!");
1381       case MVT::i8:  Opc = X86::SHL8ri; break;
1382       case MVT::i16: Opc = X86::SHL16ri; break;
1383       case MVT::i32: Opc = X86::SHL32ri; break;
1384       }
1385       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(CN->getValue());
1386       return Result;
1387     }
1388     Tmp2 = SelectExpr(N.getOperand(1));
1389     switch (N.getValueType()) {
1390     default: assert(0 && "Cannot shift this type!");
1391     case MVT::i8 : Opc = X86::SHL8rCL; break;
1392     case MVT::i16: Opc = X86::SHL16rCL; break;
1393     case MVT::i32: Opc = X86::SHL32rCL; break;
1394     }
1395     BuildMI(BB, X86::MOV8rr, 1, X86::CL).addReg(Tmp2);
1396     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1397     return Result;
1398   case ISD::SRL:
1399     Tmp1 = SelectExpr(N.getOperand(0));
1400     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1401       switch (N.getValueType()) {
1402       default: assert(0 && "Cannot shift this type!");
1403       case MVT::i8:  Opc = X86::SHR8ri; break;
1404       case MVT::i16: Opc = X86::SHR16ri; break;
1405       case MVT::i32: Opc = X86::SHR32ri; break;
1406       }
1407       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(CN->getValue());
1408       return Result;
1409     }
1410     Tmp2 = SelectExpr(N.getOperand(1));
1411     switch (N.getValueType()) {
1412     default: assert(0 && "Cannot shift this type!");
1413     case MVT::i8 : Opc = X86::SHR8rCL; break;
1414     case MVT::i16: Opc = X86::SHR16rCL; break;
1415     case MVT::i32: Opc = X86::SHR32rCL; break;
1416     }
1417     BuildMI(BB, X86::MOV8rr, 1, X86::CL).addReg(Tmp2);
1418     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1419     return Result;
1420   case ISD::SRA:
1421     Tmp1 = SelectExpr(N.getOperand(0));
1422     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1423       switch (N.getValueType()) {
1424       default: assert(0 && "Cannot shift this type!");
1425       case MVT::i8:  Opc = X86::SAR8ri; break;
1426       case MVT::i16: Opc = X86::SAR16ri; break;
1427       case MVT::i32: Opc = X86::SAR32ri; break;
1428       }
1429       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(CN->getValue());
1430       return Result;
1431     }
1432     Tmp2 = SelectExpr(N.getOperand(1));
1433     switch (N.getValueType()) {
1434     default: assert(0 && "Cannot shift this type!");
1435     case MVT::i8 : Opc = X86::SAR8rCL; break;
1436     case MVT::i16: Opc = X86::SAR16rCL; break;
1437     case MVT::i32: Opc = X86::SAR32rCL; break;
1438     }
1439     BuildMI(BB, X86::MOV8rr, 1, X86::CL).addReg(Tmp2);
1440     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1441     return Result;
1442
1443   case ISD::SETCC:
1444     if (MVT::isFloatingPoint(N.getOperand(0).getValueType()))
1445       ContainsFPCode = true;
1446     EmitCMP(N.getOperand(0), N.getOperand(1));
1447     EmitSetCC(BB, Result, cast<SetCCSDNode>(N)->getCondition(),
1448               MVT::isFloatingPoint(N.getOperand(1).getValueType()));
1449     return Result;
1450   case ISD::LOAD: {
1451     // The chain for this load is now lowered.
1452     LoweredTokens.insert(SDOperand(Node, 1));
1453     Select(N.getOperand(0));
1454
1455     // Make sure we generate both values.
1456     if (Result != 1)
1457       ExprMap[N.getValue(1)] = 1;   // Generate the token
1458     else
1459       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
1460
1461     switch (Node->getValueType(0)) {
1462     default: assert(0 && "Cannot load this type!");
1463     case MVT::i1:
1464     case MVT::i8:  Opc = X86::MOV8rm; break;
1465     case MVT::i16: Opc = X86::MOV16rm; break;
1466     case MVT::i32: Opc = X86::MOV32rm; break;
1467     case MVT::f32: Opc = X86::FLD32m; ContainsFPCode = true; break;
1468     case MVT::f64: Opc = X86::FLD64m; ContainsFPCode = true; break;
1469     }
1470     if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(N.getOperand(1))){
1471       addConstantPoolReference(BuildMI(BB, Opc, 4, Result), CP->getIndex());
1472     } else {
1473       X86AddressMode AM;
1474       SelectAddress(N.getOperand(1), AM);
1475       addFullAddress(BuildMI(BB, Opc, 4, Result), AM);
1476     }
1477     return Result;
1478   }
1479   case ISD::DYNAMIC_STACKALLOC:
1480     Select(N.getOperand(0));
1481
1482     // Generate both result values.
1483     if (Result != 1)
1484       ExprMap[N.getValue(1)] = 1;   // Generate the token
1485     else
1486       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
1487
1488     // FIXME: We are currently ignoring the requested alignment for handling
1489     // greater than the stack alignment.  This will need to be revisited at some
1490     // point.  Align = N.getOperand(2);
1491
1492     if (!isa<ConstantSDNode>(N.getOperand(2)) ||
1493         cast<ConstantSDNode>(N.getOperand(2))->getValue() != 0) {
1494       std::cerr << "Cannot allocate stack object with greater alignment than"
1495                 << " the stack alignment yet!";
1496       abort();
1497     }
1498
1499     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1500       BuildMI(BB, X86::SUB32ri, 2, X86::ESP).addReg(X86::ESP)
1501         .addImm(CN->getValue());
1502     } else {
1503       Tmp1 = SelectExpr(N.getOperand(1));
1504
1505       // Subtract size from stack pointer, thereby allocating some space.
1506       BuildMI(BB, X86::SUB32rr, 2, X86::ESP).addReg(X86::ESP).addReg(Tmp1);
1507     }
1508
1509     // Put a pointer to the space into the result register, by copying the stack
1510     // pointer.
1511     BuildMI(BB, X86::MOV32rr, 1, Result).addReg(X86::ESP);
1512     return Result;
1513
1514   case ISD::CALL:
1515     // The chain for this call is now lowered.
1516     LoweredTokens.insert(N.getValue(Node->getNumValues()-1));
1517
1518     Select(N.getOperand(0));
1519     if (GlobalAddressSDNode *GASD =
1520                dyn_cast<GlobalAddressSDNode>(N.getOperand(1))) {
1521       BuildMI(BB, X86::CALLpcrel32, 1).addGlobalAddress(GASD->getGlobal(),true);
1522     } else if (ExternalSymbolSDNode *ESSDN =
1523                dyn_cast<ExternalSymbolSDNode>(N.getOperand(1))) {
1524       BuildMI(BB, X86::CALLpcrel32,
1525               1).addExternalSymbol(ESSDN->getSymbol(), true);
1526     } else {
1527       Tmp1 = SelectExpr(N.getOperand(1));
1528       BuildMI(BB, X86::CALL32r, 1).addReg(Tmp1);
1529     }
1530     switch (Node->getValueType(0)) {
1531     default: assert(0 && "Unknown value type for call result!");
1532     case MVT::Other: return 1;
1533     case MVT::i1:
1534     case MVT::i8:
1535       BuildMI(BB, X86::MOV8rr, 1, Result).addReg(X86::AL);
1536       break;
1537     case MVT::i16:
1538       BuildMI(BB, X86::MOV16rr, 1, Result).addReg(X86::AX);
1539       break;
1540     case MVT::i32:
1541       BuildMI(BB, X86::MOV32rr, 1, Result).addReg(X86::EAX);
1542       if (Node->getValueType(1) == MVT::i32)
1543         BuildMI(BB, X86::MOV32rr, 1, Result+1).addReg(X86::EDX);
1544       break;
1545     case MVT::f32:
1546     case MVT::f64:     // Floating-point return values live in %ST(0)
1547       ContainsFPCode = true;
1548       BuildMI(BB, X86::FpGETRESULT, 1, Result);
1549       break;
1550     }
1551     return Result+N.ResNo;
1552   }
1553
1554   return 0;
1555 }
1556
1557 void ISel::Select(SDOperand N) {
1558   unsigned Tmp1, Tmp2, Opc;
1559
1560   // FIXME: Disable for our current expansion model!
1561   if (/*!N->hasOneUse() &&*/ !LoweredTokens.insert(N).second)
1562     return;  // Already selected.
1563
1564   switch (N.getOpcode()) {
1565   default:
1566     N.Val->dump(); std::cerr << "\n";
1567     assert(0 && "Node not handled yet!");
1568   case ISD::EntryToken: return;  // Noop
1569   case ISD::CopyToReg:
1570     Select(N.getOperand(0));
1571     Tmp1 = SelectExpr(N.getOperand(1));
1572     Tmp2 = cast<CopyRegSDNode>(N)->getReg();
1573
1574     if (Tmp1 != Tmp2) {
1575       switch (N.getOperand(1).getValueType()) {
1576       default: assert(0 && "Invalid type for operation!");
1577       case MVT::i1:
1578       case MVT::i8:  Opc = X86::MOV8rr; break;
1579       case MVT::i16: Opc = X86::MOV16rr; break;
1580       case MVT::i32: Opc = X86::MOV32rr; break;
1581       case MVT::f32:
1582       case MVT::f64: Opc = X86::FpMOV; break;
1583       }
1584       BuildMI(BB, Opc, 1, Tmp2).addReg(Tmp1);
1585     }
1586     return;
1587   case ISD::RET:
1588     Select(N.getOperand(0));
1589     switch (N.getNumOperands()) {
1590     default:
1591       assert(0 && "Unknown return instruction!");
1592     case 3:
1593       assert(N.getOperand(1).getValueType() == MVT::i32 &&
1594              N.getOperand(2).getValueType() == MVT::i32 &&
1595              "Unknown two-register value!");
1596       Tmp1 = SelectExpr(N.getOperand(1));
1597       Tmp2 = SelectExpr(N.getOperand(2));
1598       BuildMI(BB, X86::MOV32rr, 1, X86::EAX).addReg(Tmp1);
1599       BuildMI(BB, X86::MOV32rr, 1, X86::EDX).addReg(Tmp2);
1600       // Declare that EAX & EDX are live on exit.
1601       BuildMI(BB, X86::IMPLICIT_USE, 3).addReg(X86::EAX).addReg(X86::EDX)
1602         .addReg(X86::ESP);
1603       break;
1604     case 2:
1605       Tmp1 = SelectExpr(N.getOperand(1));
1606       switch (N.getOperand(1).getValueType()) {
1607       default: assert(0 && "All other types should have been promoted!!");
1608       case MVT::f64:
1609         BuildMI(BB, X86::FpSETRESULT, 1).addReg(Tmp1);
1610         // Declare that top-of-stack is live on exit
1611         BuildMI(BB, X86::IMPLICIT_USE, 2).addReg(X86::ST0).addReg(X86::ESP);
1612         break;
1613       case MVT::i32:
1614         BuildMI(BB, X86::MOV32rr, 1, X86::EAX).addReg(Tmp1);
1615         BuildMI(BB, X86::IMPLICIT_USE, 2).addReg(X86::EAX).addReg(X86::ESP);
1616         break;
1617       }
1618       break;
1619     case 1:
1620       break;
1621     }
1622     BuildMI(BB, X86::RET, 0); // Just emit a 'ret' instruction
1623     return;
1624   case ISD::BR: {
1625     Select(N.getOperand(0));
1626     MachineBasicBlock *Dest =
1627       cast<BasicBlockSDNode>(N.getOperand(1))->getBasicBlock();
1628     BuildMI(BB, X86::JMP, 1).addMBB(Dest);
1629     return;
1630   }
1631
1632   case ISD::BRCOND: {
1633     Select(N.getOperand(0));
1634     MachineBasicBlock *Dest =
1635       cast<BasicBlockSDNode>(N.getOperand(2))->getBasicBlock();
1636     // Try to fold a setcc into the branch.  If this fails, emit a test/jne
1637     // pair.
1638     if (EmitBranchCC(Dest, N.getOperand(1))) {
1639       Tmp1 = SelectExpr(N.getOperand(1));
1640       BuildMI(BB, X86::TEST8rr, 2).addReg(Tmp1).addReg(Tmp1);
1641       BuildMI(BB, X86::JNE, 1).addMBB(Dest);
1642     }
1643     return;
1644   }
1645   case ISD::LOAD:
1646   case ISD::CALL:
1647   case ISD::DYNAMIC_STACKALLOC:
1648     SelectExpr(N);
1649     return;
1650   case ISD::STORE: {
1651     Select(N.getOperand(0));
1652     // Select the address.
1653     X86AddressMode AM;
1654     SelectAddress(N.getOperand(2), AM);
1655
1656     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1657       Opc = 0;
1658       switch (CN->getValueType(0)) {
1659       default: assert(0 && "Invalid type for operation!");
1660       case MVT::i1:
1661       case MVT::i8:  Opc = X86::MOV8mi; break;
1662       case MVT::i16: Opc = X86::MOV16mi; break;
1663       case MVT::i32: Opc = X86::MOV32mi; break;
1664       case MVT::f32:
1665       case MVT::f64: break;
1666       }
1667       if (Opc) {
1668         addFullAddress(BuildMI(BB, Opc, 4+1), AM).addImm(CN->getValue());
1669         return;
1670       }
1671     }
1672     Tmp1 = SelectExpr(N.getOperand(1));
1673
1674     switch (N.getOperand(1).getValueType()) {
1675     default: assert(0 && "Cannot store this type!");
1676     case MVT::i1:
1677     case MVT::i8:  Opc = X86::MOV8mr; break;
1678     case MVT::i16: Opc = X86::MOV16mr; break;
1679     case MVT::i32: Opc = X86::MOV32mr; break;
1680     case MVT::f32: Opc = X86::FST32m; ContainsFPCode = true; break;
1681     case MVT::f64: Opc = X86::FST64m; ContainsFPCode = true; break;
1682     }
1683     addFullAddress(BuildMI(BB, Opc, 4+1), AM).addReg(Tmp1);
1684     return;
1685   }
1686   case ISD::ADJCALLSTACKDOWN:
1687   case ISD::ADJCALLSTACKUP:
1688     Select(N.getOperand(0));
1689     Tmp1 = cast<ConstantSDNode>(N.getOperand(1))->getValue();
1690
1691     Opc = N.getOpcode() == ISD::ADJCALLSTACKDOWN ? X86::ADJCALLSTACKDOWN :
1692                                                    X86::ADJCALLSTACKUP;
1693     BuildMI(BB, Opc, 1).addImm(Tmp1);
1694     return;
1695   }
1696   assert(0 && "Should not be reached!");
1697 }
1698
1699
1700 /// createX86PatternInstructionSelector - This pass converts an LLVM function
1701 /// into a machine code representation using pattern matching and a machine
1702 /// description file.
1703 ///
1704 FunctionPass *llvm::createX86PatternInstructionSelector(TargetMachine &TM) {
1705   return new ISel(TM);
1706 }