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