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     void EmitSelectCC(SDOperand Cond, MVT::ValueType SVT,
 352                       unsigned RTrue, unsigned RFalse, unsigned RDest);
 353     unsigned SelectExpr(SDOperand N);
 354     bool SelectAddress(SDOperand N, X86AddressMode &AM);
 355     void Select(SDOperand N);
 356   };
 357 }
 358
 359 /// SelectAddress - Add the specified node to the specified addressing mode,
 360 /// returning true if it cannot be done.
 361 bool ISel::SelectAddress(SDOperand N, X86AddressMode &AM) {
 362   switch (N.getOpcode()) {
 363   default: break;
 364   case ISD::FrameIndex:
 365     if (AM.BaseType == X86AddressMode::RegBase && AM.Base.Reg == 0) {
 366       AM.BaseType = X86AddressMode::FrameIndexBase;
 367       AM.Base.FrameIndex = cast<FrameIndexSDNode>(N)->getIndex();
 368       return false;
 369     }
 370     break;
 371   case ISD::GlobalAddress:
 372     if (AM.GV == 0) {
 373       AM.GV = cast<GlobalAddressSDNode>(N)->getGlobal();
 374       return false;
 375     }
 376     break;
 377   case ISD::Constant:
 378     AM.Disp += cast<ConstantSDNode>(N)->getValue();
 379     return false;
 380   case ISD::SHL:
 381     if (AM.IndexReg == 0 || AM.Scale == 1)
 382       if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.Val->getOperand(1))) {
 383         unsigned Val = CN->getValue();
 384         if (Val == 1 || Val == 2 || Val == 3) {
 385           AM.Scale = 1 << Val;
 386           AM.IndexReg = SelectExpr(N.Val->getOperand(0));
 387           return false;
 388         }
 389       }
 390     break;
 391
 392   case ISD::ADD: {
 393     X86AddressMode Backup = AM;
 394     if (!SelectAddress(N.Val->getOperand(0), AM) &&
 395         !SelectAddress(N.Val->getOperand(1), AM))
 396       return false;
 397     AM = Backup;
 398     break;
 399   }
 400   }
 401
 402   if (AM.BaseType != X86AddressMode::RegBase ||
 403       AM.Base.Reg)
 404     return true;
 405
 406   // Default, generate it as a register.
 407   AM.BaseType = X86AddressMode::RegBase;
 408   AM.Base.Reg = SelectExpr(N);
 409   return false;
 410 }
 411
 412 /// Emit2SetCCsAndLogical - Emit the following sequence of instructions,
 413 /// assuming that the temporary registers are in the 8-bit register class.
 414 ///
 415 ///  Tmp1 = setcc1
 416 ///  Tmp2 = setcc2
 417 ///  DestReg = logicalop Tmp1, Tmp2
 418 ///
 419 static void Emit2SetCCsAndLogical(MachineBasicBlock *BB, unsigned SetCC1,
 420                                   unsigned SetCC2, unsigned LogicalOp,
 421                                   unsigned DestReg) {
 422   SSARegMap *RegMap = BB->getParent()->getSSARegMap();
 423   unsigned Tmp1 = RegMap->createVirtualRegister(X86::R8RegisterClass);
 424   unsigned Tmp2 = RegMap->createVirtualRegister(X86::R8RegisterClass);
 425   BuildMI(BB, SetCC1, 0, Tmp1);
 426   BuildMI(BB, SetCC2, 0, Tmp2);
 427   BuildMI(BB, LogicalOp, 2, DestReg).addReg(Tmp1).addReg(Tmp2);
 428 }
 429
 430 /// EmitSetCC - Emit the code to set the specified 8-bit register to 1 if the
 431 /// condition codes match the specified SetCCOpcode.  Note that some conditions
 432 /// require multiple instructions to generate the correct value.
 433 static void EmitSetCC(MachineBasicBlock *BB, unsigned DestReg,
 434                       ISD::CondCode SetCCOpcode, bool isFP) {
 435   unsigned Opc;
 436   if (!isFP) {
 437     switch (SetCCOpcode) {
 438     default: assert(0 && "Illegal integer SetCC!");
 439     case ISD::SETEQ: Opc = X86::SETEr; break;
 440     case ISD::SETGT: Opc = X86::SETGr; break;
 441     case ISD::SETGE: Opc = X86::SETGEr; break;
 442     case ISD::SETLT: Opc = X86::SETLr; break;
 443     case ISD::SETLE: Opc = X86::SETLEr; break;
 444     case ISD::SETNE: Opc = X86::SETNEr; break;
 445     case ISD::SETULT: Opc = X86::SETBr; break;
 446     case ISD::SETUGT: Opc = X86::SETAr; break;
 447     case ISD::SETULE: Opc = X86::SETBEr; break;
 448     case ISD::SETUGE: Opc = X86::SETAEr; break;
 449     }
 450   } else {
 451     // On a floating point condition, the flags are set as follows:
 452     // ZF  PF  CF   op
 453     //  0 | 0 | 0 | X > Y
 454     //  0 | 0 | 1 | X < Y
 455     //  1 | 0 | 0 | X == Y
 456     //  1 | 1 | 1 | unordered
 457     //
 458     switch (SetCCOpcode) {
 459     default: assert(0 && "Invalid FP setcc!");
 460     case ISD::SETUEQ:
 461     case ISD::SETEQ:
 462       Opc = X86::SETEr;    // True if ZF = 1
 463       break;
 464     case ISD::SETOGT:
 465     case ISD::SETGT:
 466       Opc = X86::SETAr;    // True if CF = 0 and ZF = 0
 467       break;
 468     case ISD::SETOGE:
 469     case ISD::SETGE:
 470       Opc = X86::SETAEr;   // True if CF = 0
 471       break;
 472     case ISD::SETULT:
 473     case ISD::SETLT:
 474       Opc = X86::SETBr;    // True if CF = 1
 475       break;
 476     case ISD::SETULE:
 477     case ISD::SETLE:
 478       Opc = X86::SETBEr;   // True if CF = 1 or ZF = 1
 479       break;
 480     case ISD::SETONE:
 481     case ISD::SETNE:
 482       Opc = X86::SETNEr;   // True if ZF = 0
 483       break;
 484     case ISD::SETUO:
 485       Opc = X86::SETPr;    // True if PF = 1
 486       break;
 487     case ISD::SETO:
 488       Opc = X86::SETNPr;   // True if PF = 0
 489       break;
 490     case ISD::SETOEQ:      // !PF & ZF
 491       Emit2SetCCsAndLogical(BB, X86::SETNPr, X86::SETEr, X86::AND8rr, DestReg);
 492       return;
 493     case ISD::SETOLT:      // !PF & CF
 494       Emit2SetCCsAndLogical(BB, X86::SETNPr, X86::SETBr, X86::AND8rr, DestReg);
 495       return;
 496     case ISD::SETOLE:      // !PF & (CF || ZF)
 497       Emit2SetCCsAndLogical(BB, X86::SETNPr, X86::SETBEr, X86::AND8rr, DestReg);
 498       return;
 499     case ISD::SETUGT:      // PF | (!ZF & !CF)
 500       Emit2SetCCsAndLogical(BB, X86::SETPr, X86::SETAr, X86::OR8rr, DestReg);
 501       return;
 502     case ISD::SETUGE:      // PF | !CF
 503       Emit2SetCCsAndLogical(BB, X86::SETPr, X86::SETAEr, X86::OR8rr, DestReg);
 504       return;
 505     case ISD::SETUNE:      // PF | !ZF
 506       Emit2SetCCsAndLogical(BB, X86::SETPr, X86::SETNEr, X86::OR8rr, DestReg);
 507       return;
 508     }
 509   }
 510   BuildMI(BB, Opc, 0, DestReg);
 511 }
 512
 513
 514 /// EmitBranchCC - Emit code into BB that arranges for control to transfer to
 515 /// the Dest block if the Cond condition is true.  If we cannot fold this
 516 /// condition into the branch, return true.
 517 ///
 518 bool ISel::EmitBranchCC(MachineBasicBlock *Dest, SDOperand Cond) {
 519   // FIXME: Evaluate whether it would be good to emit code like (X < Y) | (A >
 520   // B) using two conditional branches instead of one condbr, two setcc's, and
 521   // an or.
 522   if ((Cond.getOpcode() == ISD::OR ||
 523        Cond.getOpcode() == ISD::AND) && Cond.Val->hasOneUse()) {
 524     // And and or set the flags for us, so there is no need to emit a TST of the
 525     // result.  It is only safe to do this if there is only a single use of the
 526     // AND/OR though, otherwise we don't know it will be emitted here.
 527     SelectExpr(Cond);
 528     BuildMI(BB, X86::JNE, 1).addMBB(Dest);
 529     return false;
 530   }
 531
 532   // Codegen br not C -> JE.
 533   if (Cond.getOpcode() == ISD::XOR)
 534     if (ConstantSDNode *NC = dyn_cast<ConstantSDNode>(Cond.Val->getOperand(1)))
 535       if (NC->isAllOnesValue()) {
 536         unsigned CondR = SelectExpr(Cond.Val->getOperand(0));
 537         BuildMI(BB, X86::TEST8rr, 2).addReg(CondR).addReg(CondR);
 538         BuildMI(BB, X86::JE, 1).addMBB(Dest);
 539         return false;
 540       }
 541
 542   SetCCSDNode *SetCC = dyn_cast<SetCCSDNode>(Cond);
 543   if (SetCC == 0)
 544     return true;                       // Can only handle simple setcc's so far.
 545
 546   unsigned Opc;
 547
 548   // Handle integer conditions first.
 549   if (MVT::isInteger(SetCC->getOperand(0).getValueType())) {
 550     switch (SetCC->getCondition()) {
 551     default: assert(0 && "Illegal integer SetCC!");
 552     case ISD::SETEQ: Opc = X86::JE; break;
 553     case ISD::SETGT: Opc = X86::JG; break;
 554     case ISD::SETGE: Opc = X86::JGE; break;
 555     case ISD::SETLT: Opc = X86::JL; break;
 556     case ISD::SETLE: Opc = X86::JLE; break;
 557     case ISD::SETNE: Opc = X86::JNE; break;
 558     case ISD::SETULT: Opc = X86::JB; break;
 559     case ISD::SETUGT: Opc = X86::JA; break;
 560     case ISD::SETULE: Opc = X86::JBE; break;
 561     case ISD::SETUGE: Opc = X86::JAE; break;
 562     }
 563     EmitCMP(SetCC->getOperand(0), SetCC->getOperand(1));
 564     BuildMI(BB, Opc, 1).addMBB(Dest);
 565     return false;
 566   }
 567
 568   ContainsFPCode = true;
 569   unsigned Opc2 = 0;  // Second branch if needed.
 570
 571   // On a floating point condition, the flags are set as follows:
 572   // ZF  PF  CF   op
 573   //  0 | 0 | 0 | X > Y
 574   //  0 | 0 | 1 | X < Y
 575   //  1 | 0 | 0 | X == Y
 576   //  1 | 1 | 1 | unordered
 577   //
 578   switch (SetCC->getCondition()) {
 579   default: assert(0 && "Invalid FP setcc!");
 580   case ISD::SETUEQ:
 581   case ISD::SETEQ:   Opc = X86::JE;  break;     // True if ZF = 1
 582   case ISD::SETOGT:
 583   case ISD::SETGT:   Opc = X86::JA;  break;     // True if CF = 0 and ZF = 0
 584   case ISD::SETOGE:
 585   case ISD::SETGE:   Opc = X86::JAE; break;     // True if CF = 0
 586   case ISD::SETULT:
 587   case ISD::SETLT:   Opc = X86::JB;  break;     // True if CF = 1
 588   case ISD::SETULE:
 589   case ISD::SETLE:   Opc = X86::JBE; break;     // True if CF = 1 or ZF = 1
 590   case ISD::SETONE:
 591   case ISD::SETNE:   Opc = X86::JNE; break;     // True if ZF = 0
 592   case ISD::SETUO:   Opc = X86::JP;  break;     // True if PF = 1
 593   case ISD::SETO:    Opc = X86::JNP; break;     // True if PF = 0
 594   case ISD::SETUGT:      // PF = 1 | (ZF = 0 & CF = 0)
 595     Opc = X86::JA;       // ZF = 0 & CF = 0
 596     Opc2 = X86::JP;      // PF = 1
 597     break;
 598   case ISD::SETUGE:      // PF = 1 | CF = 0
 599     Opc = X86::JAE;      // CF = 0
 600     Opc2 = X86::JP;      // PF = 1
 601     break;
 602   case ISD::SETUNE:      // PF = 1 | ZF = 0
 603     Opc = X86::JNE;      // ZF = 0
 604     Opc2 = X86::JP;      // PF = 1
 605     break;
 606   case ISD::SETOEQ:      // PF = 0 & ZF = 1
 607     //X86::JNP, X86::JE
 608     //X86::AND8rr
 609     return true;    // FIXME: Emit more efficient code for this branch.
 610   case ISD::SETOLT:      // PF = 0 & CF = 1
 611     //X86::JNP, X86::JB
 612     //X86::AND8rr
 613     return true;    // FIXME: Emit more efficient code for this branch.
 614   case ISD::SETOLE:      // PF = 0 & (CF = 1 || ZF = 1)
 615     //X86::JNP, X86::JBE
 616     //X86::AND8rr
 617     return true;    // FIXME: Emit more efficient code for this branch.
 618   }
 619
 620   EmitCMP(SetCC->getOperand(0), SetCC->getOperand(1));
 621   BuildMI(BB, Opc, 1).addMBB(Dest);
 622   if (Opc2)
 623     BuildMI(BB, Opc2, 1).addMBB(Dest);
 624   return false;
 625 }
 626
 627 /// EmitSelectCC - Emit code into BB that performs a select operation between
 628 /// the two registers RTrue and RFalse, generating a result into RDest.  Return
 629 /// true if the fold cannot be performed.
 630 ///
 631 void ISel::EmitSelectCC(SDOperand Cond, MVT::ValueType SVT,
 632                         unsigned RTrue, unsigned RFalse, unsigned RDest) {
 633   enum Condition {
 634     EQ, NE, LT, LE, GT, GE, B, BE, A, AE, P, NP,
 635     NOT_SET
 636   } CondCode = NOT_SET;
 637
 638   static const unsigned CMOVTAB16[] = {
 639     X86::CMOVE16rr,  X86::CMOVNE16rr, X86::CMOVL16rr,  X86::CMOVLE16rr,
 640     X86::CMOVG16rr,  X86::CMOVGE16rr, X86::CMOVB16rr,  X86::CMOVBE16rr,
 641     X86::CMOVA16rr,  X86::CMOVAE16rr, X86::CMOVP16rr,  X86::CMOVNP16rr,
 642   };
 643   static const unsigned CMOVTAB32[] = {
 644     X86::CMOVE32rr,  X86::CMOVNE32rr, X86::CMOVL32rr,  X86::CMOVLE32rr,
 645     X86::CMOVG32rr,  X86::CMOVGE32rr, X86::CMOVB32rr,  X86::CMOVBE32rr,
 646     X86::CMOVA32rr,  X86::CMOVAE32rr, X86::CMOVP32rr,  X86::CMOVNP32rr,
 647   };
 648   static const unsigned CMOVTABFP[] = {
 649     X86::FCMOVE ,  X86::FCMOVNE, /*missing*/0, /*missing*/0,
 650     /*missing*/0,  /*missing*/0, X86::FCMOVB , X86::FCMOVBE,
 651     X86::FCMOVA ,  X86::FCMOVAE, X86::FCMOVP , X86::FCMOVNP
 652   };
 653
 654   if (SetCCSDNode *SetCC = dyn_cast<SetCCSDNode>(Cond)) {
 655     if (MVT::isInteger(SetCC->getOperand(0).getValueType())) {
 656       switch (SetCC->getCondition()) {
 657       default: assert(0 && "Unknown integer comparison!");
 658       case ISD::SETEQ:  CondCode = EQ; break;
 659       case ISD::SETGT:  CondCode = GT; break;
 660       case ISD::SETGE:  CondCode = GE; break;
 661       case ISD::SETLT:  CondCode = LT; break;
 662       case ISD::SETLE:  CondCode = LE; break;
 663       case ISD::SETNE:  CondCode = NE; break;
 664       case ISD::SETULT: CondCode = B; break;
 665       case ISD::SETUGT: CondCode = A; break;
 666       case ISD::SETULE: CondCode = BE; break;
 667       case ISD::SETUGE: CondCode = AE; break;
 668       }
 669     } else {
 670       // On a floating point condition, the flags are set as follows:
 671       // ZF  PF  CF   op
 672       //  0 | 0 | 0 | X > Y
 673       //  0 | 0 | 1 | X < Y
 674       //  1 | 0 | 0 | X == Y
 675       //  1 | 1 | 1 | unordered
 676       //
 677       switch (SetCC->getCondition()) {
 678       default: assert(0 && "Unknown FP comparison!");
 679       case ISD::SETUEQ:
 680       case ISD::SETEQ:  CondCode = EQ; break;     // True if ZF = 1
 681       case ISD::SETOGT:
 682       case ISD::SETGT:  CondCode = A;  break;     // True if CF = 0 and ZF = 0
 683       case ISD::SETOGE:
 684       case ISD::SETGE:  CondCode = AE; break;     // True if CF = 0
 685       case ISD::SETULT:
 686       case ISD::SETLT:  CondCode = B;  break;     // True if CF = 1
 687       case ISD::SETULE:
 688       case ISD::SETLE:  CondCode = BE; break;     // True if CF = 1 or ZF = 1
 689       case ISD::SETONE:
 690       case ISD::SETNE:  CondCode = NE; break;     // True if ZF = 0
 691       case ISD::SETUO:  CondCode = P;  break;     // True if PF = 1
 692       case ISD::SETO:   CondCode = NP; break;     // True if PF = 0
 693       case ISD::SETUGT:      // PF = 1 | (ZF = 0 & CF = 0)
 694       case ISD::SETUGE:      // PF = 1 | CF = 0
 695       case ISD::SETUNE:      // PF = 1 | ZF = 0
 696       case ISD::SETOEQ:      // PF = 0 & ZF = 1
 697       case ISD::SETOLT:      // PF = 0 & CF = 1
 698       case ISD::SETOLE:      // PF = 0 & (CF = 1 || ZF = 1)
 699         // We cannot emit this comparison as a single cmov.
 700         break;
 701       }
 702     }
 703   }
 704
 705   unsigned Opc = 0;
 706   if (CondCode != NOT_SET) {
 707     switch (SVT) {
 708     default: assert(0 && "Cannot select this type!");
 709     case MVT::i16: Opc = CMOVTAB16[CondCode]; break;
 710     case MVT::i32: Opc = CMOVTAB32[CondCode]; break;
 711     case MVT::f32:
 712     case MVT::f64: Opc = CMOVTABFP[CondCode]; ContainsFPCode = true; break;
 713     }
 714   }
 715
 716   // Finally, if we weren't able to fold this, just emit the condition and test
 717   // it.
 718   if (CondCode == NOT_SET || Opc == 0) {
 719     // Get the condition into the zero flag.
 720     unsigned CondReg = SelectExpr(Cond);
 721     BuildMI(BB, X86::TEST8rr, 2).addReg(CondReg).addReg(CondReg);
 722
 723     switch (SVT) {
 724     default: assert(0 && "Cannot select this type!");
 725     case MVT::i16: Opc = X86::CMOVE16rr; break;
 726     case MVT::i32: Opc = X86::CMOVE32rr; break;
 727     case MVT::f32:
 728     case MVT::f64: Opc = X86::FCMOVE; ContainsFPCode = true; break;
 729     }
 730   } else {
 731     // FIXME: CMP R, 0 -> TEST R, R
 732     EmitCMP(Cond.getOperand(0), Cond.getOperand(1));
 733   }
 734   BuildMI(BB, Opc, 2, RDest).addReg(RTrue).addReg(RFalse);
 735 }
 736
 737 void ISel::EmitCMP(SDOperand LHS, SDOperand RHS) {
 738   unsigned Tmp1 = SelectExpr(LHS), Opc;
 739   if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(RHS)) {
 740     Opc = 0;
 741     switch (RHS.getValueType()) {
 742     default: break;
 743     case MVT::i1:
 744     case MVT::i8:  Opc = X86::CMP8ri;  break;
 745     case MVT::i16: Opc = X86::CMP16ri; break;
 746     case MVT::i32: Opc = X86::CMP32ri; break;
 747     }
 748     if (Opc) {
 749       BuildMI(BB, Opc, 2).addReg(Tmp1).addImm(CN->getValue());
 750       return;
 751     }
 752   }
 753
 754   switch (LHS.getValueType()) {
 755   default: assert(0 && "Cannot compare this value!");
 756   case MVT::i1:
 757   case MVT::i8:  Opc = X86::CMP8rr;  break;
 758   case MVT::i16: Opc = X86::CMP16rr; break;
 759   case MVT::i32: Opc = X86::CMP32rr; break;
 760   case MVT::f32:
 761   case MVT::f64: Opc = X86::FUCOMIr; ContainsFPCode = true; break;
 762   }
 763   unsigned Tmp2 = SelectExpr(RHS);
 764   BuildMI(BB, Opc, 2).addReg(Tmp1).addReg(Tmp2);
 765 }
 766
 767 unsigned ISel::SelectExpr(SDOperand N) {
 768   unsigned Result;
 769   unsigned Tmp1, Tmp2, Tmp3;
 770   unsigned Opc = 0;
 771
 772   SDNode *Node = N.Val;
 773
 774   if (Node->getOpcode() == ISD::CopyFromReg)
 775     // Just use the specified register as our input.
 776     return dyn_cast<CopyRegSDNode>(Node)->getReg();
 777
 778   // If there are multiple uses of this expression, memorize the
 779   // register it is code generated in, instead of emitting it multiple
 780   // times.
 781   // FIXME: Disabled for our current selection model.
 782   if (1 || !Node->hasOneUse()) {
 783     unsigned &Reg = ExprMap[N];
 784     if (Reg) return Reg;
 785
 786     if (N.getOpcode() != ISD::CALL)
 787       Reg = Result = (N.getValueType() != MVT::Other) ?
 788                          MakeReg(N.getValueType()) : 1;
 789     else {
 790       // If this is a call instruction, make sure to prepare ALL of the result
 791       // values as well as the chain.
 792       if (Node->getNumValues() == 1)
 793         Reg = Result = 1;  // Void call, just a chain.
 794       else {
 795         Result = MakeReg(Node->getValueType(0));
 796         ExprMap[N.getValue(0)] = Result;
 797         for (unsigned i = 1, e = N.Val->getNumValues()-1; i != e; ++i)
 798           ExprMap[N.getValue(i)] = MakeReg(Node->getValueType(i));
 799         ExprMap[SDOperand(Node, Node->getNumValues()-1)] = 1;
 800       }
 801     }
 802   } else {
 803     Result = MakeReg(N.getValueType());
 804   }
 805
 806   switch (N.getOpcode()) {
 807   default:
 808     Node->dump();
 809     assert(0 && "Node not handled!\n");
 810   case ISD::FrameIndex:
 811     Tmp1 = cast<FrameIndexSDNode>(N)->getIndex();
 812     addFrameReference(BuildMI(BB, X86::LEA32r, 4, Result), (int)Tmp1);
 813     return Result;
 814   case ISD::ConstantPool:
 815     Tmp1 = cast<ConstantPoolSDNode>(N)->getIndex();
 816     addConstantPoolReference(BuildMI(BB, X86::LEA32r, 4, Result), Tmp1);
 817     return Result;
 818   case ISD::ConstantFP:
 819     ContainsFPCode = true;
 820     Tmp1 = Result;   // Intermediate Register
 821     if (cast<ConstantFPSDNode>(N)->getValue() < 0.0 ||
 822         cast<ConstantFPSDNode>(N)->isExactlyValue(-0.0))
 823       Tmp1 = MakeReg(MVT::f64);
 824
 825     if (cast<ConstantFPSDNode>(N)->isExactlyValue(+0.0) ||
 826         cast<ConstantFPSDNode>(N)->isExactlyValue(-0.0))
 827       BuildMI(BB, X86::FLD0, 0, Tmp1);
 828     else if (cast<ConstantFPSDNode>(N)->isExactlyValue(+1.0) ||
 829              cast<ConstantFPSDNode>(N)->isExactlyValue(-1.0))
 830       BuildMI(BB, X86::FLD1, 0, Tmp1);
 831     else
 832       assert(0 && "Unexpected constant!");
 833     if (Tmp1 != Result)
 834       BuildMI(BB, X86::FCHS, 1, Result).addReg(Tmp1);
 835     return Result;
 836   case ISD::Constant:
 837     switch (N.getValueType()) {
 838     default: assert(0 && "Cannot use constants of this type!");
 839     case MVT::i1:
 840     case MVT::i8:  Opc = X86::MOV8ri;  break;
 841     case MVT::i16: Opc = X86::MOV16ri; break;
 842     case MVT::i32: Opc = X86::MOV32ri; break;
 843     }
 844     BuildMI(BB, Opc, 1,Result).addImm(cast<ConstantSDNode>(N)->getValue());
 845     return Result;
 846   case ISD::GlobalAddress: {
 847     GlobalValue *GV = cast<GlobalAddressSDNode>(N)->getGlobal();
 848     BuildMI(BB, X86::MOV32ri, 1, Result).addGlobalAddress(GV);
 849     return Result;
 850   }
 851   case ISD::ExternalSymbol: {
 852     const char *Sym = cast<ExternalSymbolSDNode>(N)->getSymbol();
 853     BuildMI(BB, X86::MOV32ri, 1, Result).addExternalSymbol(Sym);
 854     return Result;
 855   }
 856   case ISD::FP_EXTEND:
 857     Tmp1 = SelectExpr(N.getOperand(0));
 858     BuildMI(BB, X86::FpMOV, 1, Result).addReg(Tmp1);
 859     ContainsFPCode = true;
 860     return Result;
 861   case ISD::ZERO_EXTEND: {
 862     int DestIs16 = N.getValueType() == MVT::i16;
 863     int SrcIs16  = N.getOperand(0).getValueType() == MVT::i16;
 864     Tmp1 = SelectExpr(N.getOperand(0));
 865
 866     // FIXME: This hack is here for zero extension casts from bool to i8.  This
 867     // would not be needed if bools were promoted by Legalize.
 868     if (N.getValueType() == MVT::i8) {
 869       BuildMI(BB, X86::MOV8rr, 1, Result).addReg(Tmp1);
 870       return Result;
 871     }
 872
 873     static const unsigned Opc[3] = {
 874       X86::MOVZX32rr8, X86::MOVZX32rr16, X86::MOVZX16rr8
 875     };
 876     BuildMI(BB, Opc[SrcIs16+DestIs16*2], 1, Result).addReg(Tmp1);
 877     return Result;
 878   }
 879   case ISD::SIGN_EXTEND: {
 880     int DestIs16 = N.getValueType() == MVT::i16;
 881     int SrcIs16  = N.getOperand(0).getValueType() == MVT::i16;
 882
 883     // FIXME: Legalize should promote bools to i8!
 884     assert(N.getOperand(0).getValueType() != MVT::i1 &&
 885            "Sign extend from bool not implemented!");
 886
 887     static const unsigned Opc[3] = {
 888       X86::MOVSX32rr8, X86::MOVSX32rr16, X86::MOVSX16rr8
 889     };
 890     Tmp1 = SelectExpr(N.getOperand(0));
 891     BuildMI(BB, Opc[SrcIs16+DestIs16*2], 1, Result).addReg(Tmp1);
 892     return Result;
 893   }
 894   case ISD::TRUNCATE:
 895     // Handle cast of LARGER int to SMALLER int using a move to EAX followed by
 896     // a move out of AX or AL.
 897     switch (N.getOperand(0).getValueType()) {
 898     default: assert(0 && "Unknown truncate!");
 899     case MVT::i8:  Tmp2 = X86::AL;  Opc = X86::MOV8rr;  break;
 900     case MVT::i16: Tmp2 = X86::AX;  Opc = X86::MOV16rr; break;
 901     case MVT::i32: Tmp2 = X86::EAX; Opc = X86::MOV32rr; break;
 902     }
 903     Tmp1 = SelectExpr(N.getOperand(0));
 904     BuildMI(BB, Opc, 1, Tmp2).addReg(Tmp1);
 905
 906     switch (N.getValueType()) {
 907     default: assert(0 && "Unknown truncate!");
 908     case MVT::i1:
 909     case MVT::i8:  Tmp2 = X86::AL;  Opc = X86::MOV8rr;  break;
 910     case MVT::i16: Tmp2 = X86::AX;  Opc = X86::MOV16rr; break;
 911     }
 912     BuildMI(BB, Opc, 1, Result).addReg(Tmp2);
 913     return Result;
 914
 915   case ISD::FP_ROUND:
 916     // Truncate from double to float by storing to memory as float,
 917     // then reading it back into a register.
 918
 919     // Create as stack slot to use.
 920     // FIXME: This should automatically be made by the Legalizer!
 921     Tmp1 = TLI.getTargetData().getFloatAlignment();
 922     Tmp2 = BB->getParent()->getFrameInfo()->CreateStackObject(4, Tmp1);
 923
 924     // Codegen the input.
 925     Tmp1 = SelectExpr(N.getOperand(0));
 926
 927     // Emit the store, then the reload.
 928     addFrameReference(BuildMI(BB, X86::FST32m, 5), Tmp2).addReg(Tmp1);
 929     addFrameReference(BuildMI(BB, X86::FLD32m, 5, Result), Tmp2);
 930     ContainsFPCode = true;
 931     return Result;
 932
 933   case ISD::SINT_TO_FP:
 934   case ISD::UINT_TO_FP: {
 935     // FIXME: Most of this grunt work should be done by legalize!
 936
 937     // Promote the integer to a type supported by FLD.  We do this because there
 938     // are no unsigned FLD instructions, so we must promote an unsigned value to
 939     // a larger signed value, then use FLD on the larger value.
 940     //
 941     MVT::ValueType PromoteType = MVT::Other;
 942     MVT::ValueType SrcTy = N.getOperand(0).getValueType();
 943     unsigned PromoteOpcode = 0;
 944     unsigned RealDestReg = Result;
 945     switch (SrcTy) {
 946     case MVT::i1:
 947     case MVT::i8:
 948       // We don't have the facilities for directly loading byte sized data from
 949       // memory (even signed).  Promote it to 16 bits.
 950       PromoteType = MVT::i16;
 951       PromoteOpcode = Node->getOpcode() == ISD::SINT_TO_FP ?
 952         X86::MOVSX16rr8 : X86::MOVZX16rr8;
 953       break;
 954     case MVT::i16:
 955       if (Node->getOpcode() == ISD::UINT_TO_FP) {
 956         PromoteType = MVT::i32;
 957         PromoteOpcode = X86::MOVZX32rr16;
 958       }
 959       break;
 960     default:
 961       // Don't fild into the real destination.
 962       if (Node->getOpcode() == ISD::UINT_TO_FP)
 963         Result = MakeReg(Node->getValueType(0));
 964       break;
 965     }
 966
 967     Tmp1 = SelectExpr(N.getOperand(0));  // Get the operand register
 968
 969     if (PromoteType != MVT::Other) {
 970       Tmp2 = MakeReg(PromoteType);
 971       BuildMI(BB, PromoteOpcode, 1, Tmp2).addReg(Tmp1);
 972       SrcTy = PromoteType;
 973       Tmp1 = Tmp2;
 974     }
 975
 976     // Spill the integer to memory and reload it from there.
 977     unsigned Size = MVT::getSizeInBits(SrcTy)/8;
 978     MachineFunction *F = BB->getParent();
 979     int FrameIdx = F->getFrameInfo()->CreateStackObject(Size, Size);
 980
 981     switch (SrcTy) {
 982     case MVT::i64:
 983       // FIXME: this won't work for cast [u]long to FP
 984       addFrameReference(BuildMI(BB, X86::MOV32mr, 5),
 985                         FrameIdx).addReg(Tmp1);
 986       addFrameReference(BuildMI(BB, X86::MOV32mr, 5),
 987                         FrameIdx, 4).addReg(Tmp1+1);
 988       addFrameReference(BuildMI(BB, X86::FILD64m, 5, Result), FrameIdx);
 989       break;
 990     case MVT::i32:
 991       addFrameReference(BuildMI(BB, X86::MOV32mr, 5),
 992                         FrameIdx).addReg(Tmp1);
 993       addFrameReference(BuildMI(BB, X86::FILD32m, 5, Result), FrameIdx);
 994       break;
 995     case MVT::i16:
 996       addFrameReference(BuildMI(BB, X86::MOV16mr, 5),
 997                         FrameIdx).addReg(Tmp1);
 998       addFrameReference(BuildMI(BB, X86::FILD16m, 5, Result), FrameIdx);
 999       break;
1000     default: break; // No promotion required.
1001     }
1002
1003     if (Node->getOpcode() == ISD::UINT_TO_FP && SrcTy == MVT::i32) {
1004       // If this is a cast from uint -> double, we need to be careful when if
1005       // the "sign" bit is set.  If so, we don't want to make a negative number,
1006       // we want to make a positive number.  Emit code to add an offset if the
1007       // sign bit is set.
1008
1009       // Compute whether the sign bit is set by shifting the reg right 31 bits.
1010       unsigned IsNeg = MakeReg(MVT::i32);
1011       BuildMI(BB, X86::SHR32ri, 2, IsNeg).addReg(Tmp1).addImm(31);
1012
1013       // Create a CP value that has the offset in one word and 0 in the other.
1014       static ConstantInt *TheOffset = ConstantUInt::get(Type::ULongTy,
1015                                                         0x4f80000000000000ULL);
1016       unsigned CPI = F->getConstantPool()->getConstantPoolIndex(TheOffset);
1017       BuildMI(BB, X86::FADD32m, 5, RealDestReg).addReg(Result)
1018         .addConstantPoolIndex(CPI).addZImm(4).addReg(IsNeg).addSImm(0);
1019
1020     } else if (Node->getOpcode() == ISD::UINT_TO_FP && SrcTy == MVT::i64) {
1021       // We need special handling for unsigned 64-bit integer sources.  If the
1022       // input number has the "sign bit" set, then we loaded it incorrectly as a
1023       // negative 64-bit number.  In this case, add an offset value.
1024
1025       // Emit a test instruction to see if the dynamic input value was signed.
1026       BuildMI(BB, X86::TEST32rr, 2).addReg(Tmp1+1).addReg(Tmp1+1);
1027
1028       // If the sign bit is set, get a pointer to an offset, otherwise get a
1029       // pointer to a zero.
1030       MachineConstantPool *CP = F->getConstantPool();
1031       unsigned Zero = MakeReg(MVT::i32);
1032       Constant *Null = Constant::getNullValue(Type::UIntTy);
1033       addConstantPoolReference(BuildMI(BB, X86::LEA32r, 5, Zero),
1034                                CP->getConstantPoolIndex(Null));
1035       unsigned Offset = MakeReg(MVT::i32);
1036       Constant *OffsetCst = ConstantUInt::get(Type::UIntTy, 0x5f800000);
1037
1038       addConstantPoolReference(BuildMI(BB, X86::LEA32r, 5, Offset),
1039                                CP->getConstantPoolIndex(OffsetCst));
1040       unsigned Addr = MakeReg(MVT::i32);
1041       BuildMI(BB, X86::CMOVS32rr, 2, Addr).addReg(Zero).addReg(Offset);
1042
1043       // Load the constant for an add.  FIXME: this could make an 'fadd' that
1044       // reads directly from memory, but we don't support these yet.
1045       unsigned ConstReg = MakeReg(MVT::f64);
1046       addDirectMem(BuildMI(BB, X86::FLD32m, 4, ConstReg), Addr);
1047
1048       BuildMI(BB, X86::FpADD, 2, RealDestReg).addReg(ConstReg).addReg(Result);
1049     }
1050     return RealDestReg;
1051   }
1052   case ISD::FP_TO_SINT:
1053   case ISD::FP_TO_UINT: {
1054     // FIXME: Most of this grunt work should be done by legalize!
1055     Tmp1 = SelectExpr(N.getOperand(0));  // Get the operand register
1056
1057     // Change the floating point control register to use "round towards zero"
1058     // mode when truncating to an integer value.
1059     //
1060     MachineFunction *F = BB->getParent();
1061     int CWFrameIdx = F->getFrameInfo()->CreateStackObject(2, 2);
1062     addFrameReference(BuildMI(BB, X86::FNSTCW16m, 4), CWFrameIdx);
1063
1064     // Load the old value of the high byte of the control word...
1065     unsigned HighPartOfCW = MakeReg(MVT::i8);
1066     addFrameReference(BuildMI(BB, X86::MOV8rm, 4, HighPartOfCW),
1067                       CWFrameIdx, 1);
1068
1069     // Set the high part to be round to zero...
1070     addFrameReference(BuildMI(BB, X86::MOV8mi, 5),
1071                       CWFrameIdx, 1).addImm(12);
1072
1073     // Reload the modified control word now...
1074     addFrameReference(BuildMI(BB, X86::FLDCW16m, 4), CWFrameIdx);
1075
1076     // Restore the memory image of control word to original value
1077     addFrameReference(BuildMI(BB, X86::MOV8mr, 5),
1078                       CWFrameIdx, 1).addReg(HighPartOfCW);
1079
1080     // We don't have the facilities for directly storing byte sized data to
1081     // memory.  Promote it to 16 bits.  We also must promote unsigned values to
1082     // larger classes because we only have signed FP stores.
1083     MVT::ValueType StoreClass = Node->getValueType(0);
1084     if (StoreClass == MVT::i8 || Node->getOpcode() == ISD::FP_TO_UINT)
1085       switch (StoreClass) {
1086       case MVT::i8:  StoreClass = MVT::i16; break;
1087       case MVT::i16: StoreClass = MVT::i32; break;
1088       case MVT::i32: StoreClass = MVT::i64; break;
1089         // The following treatment of cLong may not be perfectly right,
1090         // but it survives chains of casts of the form
1091         // double->ulong->double.
1092       case MVT::i64:  StoreClass = MVT::i64;  break;
1093       default: assert(0 && "Unknown store class!");
1094       }
1095
1096     // Spill the integer to memory and reload it from there.
1097     unsigned Size = MVT::getSizeInBits(StoreClass)/8;
1098     int FrameIdx = F->getFrameInfo()->CreateStackObject(Size, Size);
1099
1100     switch (StoreClass) {
1101     default: assert(0 && "Unknown store class!");
1102     case MVT::i16:
1103       addFrameReference(BuildMI(BB, X86::FIST16m, 5), FrameIdx).addReg(Tmp1);
1104       break;
1105     case MVT::i32:
1106       addFrameReference(BuildMI(BB, X86::FIST32m, 5), FrameIdx).addReg(Tmp1);
1107       break;
1108     case MVT::i64:
1109       addFrameReference(BuildMI(BB, X86::FISTP64m, 5), FrameIdx).addReg(Tmp1);
1110       break;
1111     }
1112
1113     switch (Node->getValueType(0)) {
1114     default:
1115       assert(0 && "Unknown integer type!");
1116     case MVT::i64:
1117       // FIXME: this isn't gunna work.
1118       addFrameReference(BuildMI(BB, X86::MOV32rm, 4, Result), FrameIdx);
1119       addFrameReference(BuildMI(BB, X86::MOV32rm, 4, Result+1), FrameIdx, 4);
1120     case MVT::i32:
1121       addFrameReference(BuildMI(BB, X86::MOV32rm, 4, Result), FrameIdx);
1122       break;
1123     case MVT::i16:
1124       addFrameReference(BuildMI(BB, X86::MOV16rm, 4, Result), FrameIdx);
1125       break;
1126     case MVT::i8:
1127       addFrameReference(BuildMI(BB, X86::MOV8rm, 4, Result), FrameIdx);
1128       break;
1129     }
1130
1131     // Reload the original control word now.
1132     addFrameReference(BuildMI(BB, X86::FLDCW16m, 4), CWFrameIdx);
1133     return Result;
1134   }
1135   case ISD::ADD:
1136     // See if we can codegen this as an LEA to fold operations together.
1137     if (N.getValueType() == MVT::i32) {
1138       X86AddressMode AM;
1139       if (!SelectAddress(N.getOperand(0), AM) &&
1140           !SelectAddress(N.getOperand(1), AM)) {
1141         // If this is not just an add, emit the LEA.  For a simple add (like
1142         // reg+reg or reg+imm), we just emit an add.  It might be a good idea to
1143         // leave this as LEA, then peephole it to 'ADD' after two address elim
1144         // happens.
1145         if (AM.Scale != 1 || AM.BaseType == X86AddressMode::FrameIndexBase ||
1146             AM.GV || (AM.Base.Reg && AM.IndexReg && AM.Disp)) {
1147           addFullAddress(BuildMI(BB, X86::LEA32r, 4, Result), AM);
1148           return Result;
1149         }
1150       }
1151     }
1152     Tmp1 = SelectExpr(N.getOperand(0));
1153     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1154       Opc = 0;
1155       if (CN->getValue() == 1) {   // add X, 1 -> inc X
1156         switch (N.getValueType()) {
1157         default: assert(0 && "Cannot integer add this type!");
1158         case MVT::i8:  Opc = X86::INC8r; break;
1159         case MVT::i16: Opc = X86::INC16r; break;
1160         case MVT::i32: Opc = X86::INC32r; break;
1161         }
1162       } else if (CN->isAllOnesValue()) { // add X, -1 -> dec X
1163         switch (N.getValueType()) {
1164         default: assert(0 && "Cannot integer add this type!");
1165         case MVT::i8:  Opc = X86::DEC8r; break;
1166         case MVT::i16: Opc = X86::DEC16r; break;
1167         case MVT::i32: Opc = X86::DEC32r; break;
1168         }
1169       }
1170
1171       if (Opc) {
1172         BuildMI(BB, Opc, 1, Result).addReg(Tmp1);
1173         return Result;
1174       }
1175
1176       switch (N.getValueType()) {
1177       default: assert(0 && "Cannot add this type!");
1178       case MVT::i8:  Opc = X86::ADD8ri; break;
1179       case MVT::i16: Opc = X86::ADD16ri; break;
1180       case MVT::i32: Opc = X86::ADD32ri; break;
1181       }
1182       if (Opc) {
1183         BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(CN->getValue());
1184         return Result;
1185       }
1186     }
1187
1188     Tmp2 = SelectExpr(N.getOperand(1));
1189     switch (N.getValueType()) {
1190     default: assert(0 && "Cannot add this type!");
1191     case MVT::i8:  Opc = X86::ADD8rr; break;
1192     case MVT::i16: Opc = X86::ADD16rr; break;
1193     case MVT::i32: Opc = X86::ADD32rr; break;
1194     case MVT::f32:
1195     case MVT::f64: Opc = X86::FpADD; ContainsFPCode = true; break;
1196     }
1197     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1198     return Result;
1199   case ISD::SUB:
1200     if (MVT::isInteger(N.getValueType()))
1201       if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(0)))
1202         if (CN->isNullValue()) {   // 0 - N -> neg N
1203           switch (N.getValueType()) {
1204           default: assert(0 && "Cannot sub this type!");
1205           case MVT::i1:
1206           case MVT::i8:  Opc = X86::NEG8r;  break;
1207           case MVT::i16: Opc = X86::NEG16r; break;
1208           case MVT::i32: Opc = X86::NEG32r; break;
1209           }
1210           Tmp1 = SelectExpr(N.getOperand(1));
1211           BuildMI(BB, Opc, 1, Result).addReg(Tmp1);
1212           return Result;
1213         }
1214
1215     Tmp1 = SelectExpr(N.getOperand(0));
1216     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1217       switch (N.getValueType()) {
1218       default: assert(0 && "Cannot sub this type!");
1219       case MVT::i1:
1220       case MVT::i8:  Opc = X86::SUB8ri;  break;
1221       case MVT::i16: Opc = X86::SUB16ri; break;
1222       case MVT::i32: Opc = X86::SUB32ri; break;
1223       }
1224       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(CN->getValue());
1225       return Result;
1226     }
1227     Tmp2 = SelectExpr(N.getOperand(1));
1228     switch (N.getValueType()) {
1229     default: assert(0 && "Cannot add this type!");
1230     case MVT::i1:
1231     case MVT::i8:  Opc = X86::SUB8rr; break;
1232     case MVT::i16: Opc = X86::SUB16rr; break;
1233     case MVT::i32: Opc = X86::SUB32rr; break;
1234     case MVT::f32:
1235     case MVT::f64: Opc = X86::FpSUB; ContainsFPCode = true; break;
1236     }
1237     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1238     return Result;
1239
1240   case ISD::AND:
1241     Tmp1 = SelectExpr(N.getOperand(0));
1242     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1243       switch (N.getValueType()) {
1244       default: assert(0 && "Cannot add this type!");
1245       case MVT::i1:
1246       case MVT::i8:  Opc = X86::AND8ri;  break;
1247       case MVT::i16: Opc = X86::AND16ri; break;
1248       case MVT::i32: Opc = X86::AND32ri; break;
1249       }
1250       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(CN->getValue());
1251       return Result;
1252     }
1253     Tmp2 = SelectExpr(N.getOperand(1));
1254     switch (N.getValueType()) {
1255     default: assert(0 && "Cannot add this type!");
1256     case MVT::i1:
1257     case MVT::i8:  Opc = X86::AND8rr; break;
1258     case MVT::i16: Opc = X86::AND16rr; break;
1259     case MVT::i32: Opc = X86::AND32rr; break;
1260     }
1261     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1262     return Result;
1263   case ISD::OR:
1264     Tmp1 = SelectExpr(N.getOperand(0));
1265     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1266       switch (N.getValueType()) {
1267       default: assert(0 && "Cannot add this type!");
1268       case MVT::i1:
1269       case MVT::i8:  Opc = X86::OR8ri;  break;
1270       case MVT::i16: Opc = X86::OR16ri; break;
1271       case MVT::i32: Opc = X86::OR32ri; break;
1272       }
1273       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(CN->getValue());
1274       return Result;
1275     }
1276     Tmp2 = SelectExpr(N.getOperand(1));
1277     switch (N.getValueType()) {
1278     default: assert(0 && "Cannot add this type!");
1279     case MVT::i1:
1280     case MVT::i8:  Opc = X86::OR8rr; break;
1281     case MVT::i16: Opc = X86::OR16rr; break;
1282     case MVT::i32: Opc = X86::OR32rr; break;
1283     }
1284     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1285     return Result;
1286   case ISD::XOR:
1287     Tmp1 = SelectExpr(N.getOperand(0));
1288     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1289       switch (N.getValueType()) {
1290       default: assert(0 && "Cannot add this type!");
1291       case MVT::i1:
1292       case MVT::i8:  Opc = X86::XOR8ri;  break;
1293       case MVT::i16: Opc = X86::XOR16ri; break;
1294       case MVT::i32: Opc = X86::XOR32ri; break;
1295       }
1296       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(CN->getValue());
1297       return Result;
1298     }
1299     Tmp2 = SelectExpr(N.getOperand(1));
1300     switch (N.getValueType()) {
1301     default: assert(0 && "Cannot add this type!");
1302     case MVT::i1:
1303     case MVT::i8:  Opc = X86::XOR8rr; break;
1304     case MVT::i16: Opc = X86::XOR16rr; break;
1305     case MVT::i32: Opc = X86::XOR32rr; break;
1306     }
1307     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1308     return Result;
1309
1310   case ISD::MUL:
1311     Tmp1 = SelectExpr(N.getOperand(0));
1312     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1313       Opc = 0;
1314       switch (N.getValueType()) {
1315       default: assert(0 && "Cannot multiply this type!");
1316       case MVT::i8:  break;
1317       case MVT::i16: Opc = X86::IMUL16rri; break;
1318       case MVT::i32: Opc = X86::IMUL32rri; break;
1319       }
1320       if (Opc) {
1321         BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(CN->getValue());
1322         return Result;
1323       }
1324     }
1325     Tmp2 = SelectExpr(N.getOperand(1));
1326     switch (N.getValueType()) {
1327     default: assert(0 && "Cannot add this type!");
1328     case MVT::i8:
1329       // Must use the MUL instruction, which forces use of AL.
1330       BuildMI(BB, X86::MOV8rr, 1, X86::AL).addReg(Tmp1);
1331       BuildMI(BB, X86::MUL8r, 1).addReg(Tmp2);
1332       BuildMI(BB, X86::MOV8rr, 1, Result).addReg(X86::AL);
1333       return Result;
1334     case MVT::i16: Opc = X86::IMUL16rr; break;
1335     case MVT::i32: Opc = X86::IMUL32rr; break;
1336     case MVT::f32:
1337     case MVT::f64: Opc = X86::FpMUL; ContainsFPCode = true; break;
1338     }
1339     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1340     return Result;
1341
1342   case ISD::SELECT:
1343     // FIXME: implement folding of setcc into select.
1344     if (N.getValueType() != MVT::i1 && N.getValueType() != MVT::i8) {
1345       Tmp2 = SelectExpr(N.getOperand(1));
1346       Tmp3 = SelectExpr(N.getOperand(2));
1347       EmitSelectCC(N.getOperand(0), N.getValueType(), Tmp2, Tmp3, Result);
1348       return Result;
1349     } else {
1350       // FIXME: This should not be implemented here, it should be in the generic
1351       // code!
1352       Tmp2 = SelectExpr(CurDAG->getNode(ISD::ZERO_EXTEND, MVT::i16,
1353                                         N.getOperand(1)));
1354       Tmp3 = SelectExpr(CurDAG->getNode(ISD::ZERO_EXTEND, MVT::i16,
1355                                         N.getOperand(2)));
1356       unsigned TmpReg = MakeReg(MVT::i16);
1357       EmitSelectCC(N.getOperand(0), MVT::i16, Tmp2, Tmp3, TmpReg);
1358       // FIXME: need subregs to do better than this!
1359       BuildMI(BB, X86::MOV16rr, 1, X86::AX).addReg(TmpReg);
1360       BuildMI(BB, X86::MOV8rr, 1, Result).addReg(X86::AL);
1361       return Result;
1362     }
1363
1364   case ISD::SDIV:
1365   case ISD::UDIV:
1366   case ISD::SREM:
1367   case ISD::UREM: {
1368     Tmp1 = SelectExpr(N.getOperand(0));
1369
1370     if (N.getOpcode() == ISD::SDIV)
1371       if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1372         // FIXME: These special cases should be handled by the lowering impl!
1373         unsigned RHS = CN->getValue();
1374         bool isNeg = false;
1375         if ((int)RHS < 0) {
1376           isNeg = true;
1377           RHS = -RHS;
1378         }
1379         if (RHS && (RHS & (RHS-1)) == 0) {   // Signed division by power of 2?
1380           unsigned Log = log2(RHS);
1381           unsigned TmpReg = MakeReg(N.getValueType());
1382           unsigned SAROpc, SHROpc, ADDOpc, NEGOpc;
1383           switch (N.getValueType()) {
1384           default: assert("Unknown type to signed divide!");
1385           case MVT::i8:
1386             SAROpc = X86::SAR8ri;
1387             SHROpc = X86::SHR8ri;
1388             ADDOpc = X86::ADD8rr;
1389             NEGOpc = X86::NEG8r;
1390             break;
1391           case MVT::i16:
1392             SAROpc = X86::SAR16ri;
1393             SHROpc = X86::SHR16ri;
1394             ADDOpc = X86::ADD16rr;
1395             NEGOpc = X86::NEG16r;
1396             break;
1397           case MVT::i32:
1398             SAROpc = X86::SAR32ri;
1399             SHROpc = X86::SHR32ri;
1400             ADDOpc = X86::ADD32rr;
1401             NEGOpc = X86::NEG32r;
1402             break;
1403           }
1404           BuildMI(BB, SAROpc, 2, TmpReg).addReg(Tmp1).addImm(Log-1);
1405           unsigned TmpReg2 = MakeReg(N.getValueType());
1406           BuildMI(BB, SHROpc, 2, TmpReg2).addReg(TmpReg).addImm(32-Log);
1407           unsigned TmpReg3 = MakeReg(N.getValueType());
1408           BuildMI(BB, ADDOpc, 2, TmpReg3).addReg(Tmp1).addReg(TmpReg2);
1409
1410           unsigned TmpReg4 = isNeg ? MakeReg(N.getValueType()) : Result;
1411           BuildMI(BB, SAROpc, 2, TmpReg4).addReg(TmpReg3).addImm(Log);
1412           if (isNeg)
1413             BuildMI(BB, NEGOpc, 1, Result).addReg(TmpReg4);
1414           return Result;
1415         }
1416       }
1417
1418     Tmp2 = SelectExpr(N.getOperand(1));
1419
1420     bool isSigned = N.getOpcode() == ISD::SDIV || N.getOpcode() == ISD::SREM;
1421     bool isDiv    = N.getOpcode() == ISD::SDIV || N.getOpcode() == ISD::UDIV;
1422     unsigned LoReg, HiReg, DivOpcode, MovOpcode, ClrOpcode, SExtOpcode;
1423     switch (N.getValueType()) {
1424     default: assert(0 && "Cannot sdiv this type!");
1425     case MVT::i8:
1426       DivOpcode = isSigned ? X86::IDIV8r : X86::DIV8r;
1427       LoReg = X86::AL;
1428       HiReg = X86::AH;
1429       MovOpcode = X86::MOV8rr;
1430       ClrOpcode = X86::MOV8ri;
1431       SExtOpcode = X86::CBW;
1432       break;
1433     case MVT::i16:
1434       DivOpcode = isSigned ? X86::IDIV16r : X86::DIV16r;
1435       LoReg = X86::AX;
1436       HiReg = X86::DX;
1437       MovOpcode = X86::MOV16rr;
1438       ClrOpcode = X86::MOV16ri;
1439       SExtOpcode = X86::CWD;
1440       break;
1441     case MVT::i32:
1442       DivOpcode = isSigned ? X86::IDIV32r : X86::DIV32r;
1443       LoReg =X86::EAX;
1444       HiReg = X86::EDX;
1445       MovOpcode = X86::MOV32rr;
1446       ClrOpcode = X86::MOV32ri;
1447       SExtOpcode = X86::CDQ;
1448       break;
1449     case MVT::i64: assert(0 && "FIXME: implement i64 DIV/REM libcalls!");
1450     case MVT::f32:
1451     case MVT::f64:
1452       ContainsFPCode = true;
1453       if (N.getOpcode() == ISD::SDIV)
1454         BuildMI(BB, X86::FpDIV, 2, Result).addReg(Tmp1).addReg(Tmp2);
1455       else
1456         assert(0 && "FIXME: Emit frem libcall to fmod!");
1457       return Result;
1458     }
1459
1460     // Set up the low part.
1461     BuildMI(BB, MovOpcode, 1, LoReg).addReg(Tmp1);
1462
1463     if (isSigned) {
1464       // Sign extend the low part into the high part.
1465       BuildMI(BB, SExtOpcode, 0);
1466     } else {
1467       // Zero out the high part, effectively zero extending the input.
1468       BuildMI(BB, ClrOpcode, 1, HiReg).addImm(0);
1469     }
1470
1471     // Emit the DIV/IDIV instruction.
1472     BuildMI(BB, DivOpcode, 1).addReg(Tmp2);
1473
1474     // Get the result of the divide or rem.
1475     BuildMI(BB, MovOpcode, 1, Result).addReg(isDiv ? LoReg : HiReg);
1476     return Result;
1477   }
1478
1479   case ISD::SHL:
1480     Tmp1 = SelectExpr(N.getOperand(0));
1481     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1482       switch (N.getValueType()) {
1483       default: assert(0 && "Cannot shift this type!");
1484       case MVT::i8:  Opc = X86::SHL8ri; break;
1485       case MVT::i16: Opc = X86::SHL16ri; break;
1486       case MVT::i32: Opc = X86::SHL32ri; break;
1487       }
1488       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(CN->getValue());
1489       return Result;
1490     }
1491     Tmp2 = SelectExpr(N.getOperand(1));
1492     switch (N.getValueType()) {
1493     default: assert(0 && "Cannot shift this type!");
1494     case MVT::i8 : Opc = X86::SHL8rCL; break;
1495     case MVT::i16: Opc = X86::SHL16rCL; break;
1496     case MVT::i32: Opc = X86::SHL32rCL; break;
1497     }
1498     BuildMI(BB, X86::MOV8rr, 1, X86::CL).addReg(Tmp2);
1499     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1500     return Result;
1501   case ISD::SRL:
1502     Tmp1 = SelectExpr(N.getOperand(0));
1503     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1504       switch (N.getValueType()) {
1505       default: assert(0 && "Cannot shift this type!");
1506       case MVT::i8:  Opc = X86::SHR8ri; break;
1507       case MVT::i16: Opc = X86::SHR16ri; break;
1508       case MVT::i32: Opc = X86::SHR32ri; break;
1509       }
1510       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(CN->getValue());
1511       return Result;
1512     }
1513     Tmp2 = SelectExpr(N.getOperand(1));
1514     switch (N.getValueType()) {
1515     default: assert(0 && "Cannot shift this type!");
1516     case MVT::i8 : Opc = X86::SHR8rCL; break;
1517     case MVT::i16: Opc = X86::SHR16rCL; break;
1518     case MVT::i32: Opc = X86::SHR32rCL; break;
1519     }
1520     BuildMI(BB, X86::MOV8rr, 1, X86::CL).addReg(Tmp2);
1521     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1522     return Result;
1523   case ISD::SRA:
1524     Tmp1 = SelectExpr(N.getOperand(0));
1525     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1526       switch (N.getValueType()) {
1527       default: assert(0 && "Cannot shift this type!");
1528       case MVT::i8:  Opc = X86::SAR8ri; break;
1529       case MVT::i16: Opc = X86::SAR16ri; break;
1530       case MVT::i32: Opc = X86::SAR32ri; break;
1531       }
1532       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(CN->getValue());
1533       return Result;
1534     }
1535     Tmp2 = SelectExpr(N.getOperand(1));
1536     switch (N.getValueType()) {
1537     default: assert(0 && "Cannot shift this type!");
1538     case MVT::i8 : Opc = X86::SAR8rCL; break;
1539     case MVT::i16: Opc = X86::SAR16rCL; break;
1540     case MVT::i32: Opc = X86::SAR32rCL; break;
1541     }
1542     BuildMI(BB, X86::MOV8rr, 1, X86::CL).addReg(Tmp2);
1543     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1544     return Result;
1545
1546   case ISD::SETCC:
1547     if (MVT::isFloatingPoint(N.getOperand(0).getValueType()))
1548       ContainsFPCode = true;
1549     EmitCMP(N.getOperand(0), N.getOperand(1));
1550     EmitSetCC(BB, Result, cast<SetCCSDNode>(N)->getCondition(),
1551               MVT::isFloatingPoint(N.getOperand(1).getValueType()));
1552     return Result;
1553   case ISD::LOAD: {
1554     // The chain for this load is now lowered.
1555     LoweredTokens.insert(SDOperand(Node, 1));
1556     Select(N.getOperand(0));
1557
1558     // Make sure we generate both values.
1559     if (Result != 1)
1560       ExprMap[N.getValue(1)] = 1;   // Generate the token
1561     else
1562       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
1563
1564     switch (Node->getValueType(0)) {
1565     default: assert(0 && "Cannot load this type!");
1566     case MVT::i1:
1567     case MVT::i8:  Opc = X86::MOV8rm; break;
1568     case MVT::i16: Opc = X86::MOV16rm; break;
1569     case MVT::i32: Opc = X86::MOV32rm; break;
1570     case MVT::f32: Opc = X86::FLD32m; ContainsFPCode = true; break;
1571     case MVT::f64: Opc = X86::FLD64m; ContainsFPCode = true; break;
1572     }
1573     if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(N.getOperand(1))){
1574       addConstantPoolReference(BuildMI(BB, Opc, 4, Result), CP->getIndex());
1575     } else {
1576       X86AddressMode AM;
1577       SelectAddress(N.getOperand(1), AM);
1578       addFullAddress(BuildMI(BB, Opc, 4, Result), AM);
1579     }
1580     return Result;
1581   }
1582   case ISD::DYNAMIC_STACKALLOC:
1583     Select(N.getOperand(0));
1584
1585     // Generate both result values.
1586     if (Result != 1)
1587       ExprMap[N.getValue(1)] = 1;   // Generate the token
1588     else
1589       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
1590
1591     // FIXME: We are currently ignoring the requested alignment for handling
1592     // greater than the stack alignment.  This will need to be revisited at some
1593     // point.  Align = N.getOperand(2);
1594
1595     if (!isa<ConstantSDNode>(N.getOperand(2)) ||
1596         cast<ConstantSDNode>(N.getOperand(2))->getValue() != 0) {
1597       std::cerr << "Cannot allocate stack object with greater alignment than"
1598                 << " the stack alignment yet!";
1599       abort();
1600     }
1601
1602     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1603       BuildMI(BB, X86::SUB32ri, 2, X86::ESP).addReg(X86::ESP)
1604         .addImm(CN->getValue());
1605     } else {
1606       Tmp1 = SelectExpr(N.getOperand(1));
1607
1608       // Subtract size from stack pointer, thereby allocating some space.
1609       BuildMI(BB, X86::SUB32rr, 2, X86::ESP).addReg(X86::ESP).addReg(Tmp1);
1610     }
1611
1612     // Put a pointer to the space into the result register, by copying the stack
1613     // pointer.
1614     BuildMI(BB, X86::MOV32rr, 1, Result).addReg(X86::ESP);
1615     return Result;
1616
1617   case ISD::CALL:
1618     // The chain for this call is now lowered.
1619     LoweredTokens.insert(N.getValue(Node->getNumValues()-1));
1620
1621     Select(N.getOperand(0));
1622     if (GlobalAddressSDNode *GASD =
1623                dyn_cast<GlobalAddressSDNode>(N.getOperand(1))) {
1624       BuildMI(BB, X86::CALLpcrel32, 1).addGlobalAddress(GASD->getGlobal(),true);
1625     } else if (ExternalSymbolSDNode *ESSDN =
1626                dyn_cast<ExternalSymbolSDNode>(N.getOperand(1))) {
1627       BuildMI(BB, X86::CALLpcrel32,
1628               1).addExternalSymbol(ESSDN->getSymbol(), true);
1629     } else {
1630       Tmp1 = SelectExpr(N.getOperand(1));
1631       BuildMI(BB, X86::CALL32r, 1).addReg(Tmp1);
1632     }
1633     switch (Node->getValueType(0)) {
1634     default: assert(0 && "Unknown value type for call result!");
1635     case MVT::Other: return 1;
1636     case MVT::i1:
1637     case MVT::i8:
1638       BuildMI(BB, X86::MOV8rr, 1, Result).addReg(X86::AL);
1639       break;
1640     case MVT::i16:
1641       BuildMI(BB, X86::MOV16rr, 1, Result).addReg(X86::AX);
1642       break;
1643     case MVT::i32:
1644       BuildMI(BB, X86::MOV32rr, 1, Result).addReg(X86::EAX);
1645       if (Node->getValueType(1) == MVT::i32)
1646         BuildMI(BB, X86::MOV32rr, 1, Result+1).addReg(X86::EDX);
1647       break;
1648     case MVT::f32:
1649     case MVT::f64:     // Floating-point return values live in %ST(0)
1650       ContainsFPCode = true;
1651       BuildMI(BB, X86::FpGETRESULT, 1, Result);
1652       break;
1653     }
1654     return Result+N.ResNo;
1655   }
1656
1657   return 0;
1658 }
1659
1660 void ISel::Select(SDOperand N) {
1661   unsigned Tmp1, Tmp2, Opc;
1662
1663   // FIXME: Disable for our current expansion model!
1664   if (/*!N->hasOneUse() &&*/ !LoweredTokens.insert(N).second)
1665     return;  // Already selected.
1666
1667   switch (N.getOpcode()) {
1668   default:
1669     N.Val->dump(); std::cerr << "\n";
1670     assert(0 && "Node not handled yet!");
1671   case ISD::EntryToken: return;  // Noop
1672   case ISD::CopyToReg:
1673     Select(N.getOperand(0));
1674     Tmp1 = SelectExpr(N.getOperand(1));
1675     Tmp2 = cast<CopyRegSDNode>(N)->getReg();
1676
1677     if (Tmp1 != Tmp2) {
1678       switch (N.getOperand(1).getValueType()) {
1679       default: assert(0 && "Invalid type for operation!");
1680       case MVT::i1:
1681       case MVT::i8:  Opc = X86::MOV8rr; break;
1682       case MVT::i16: Opc = X86::MOV16rr; break;
1683       case MVT::i32: Opc = X86::MOV32rr; break;
1684       case MVT::f32:
1685       case MVT::f64: Opc = X86::FpMOV; break;
1686       }
1687       BuildMI(BB, Opc, 1, Tmp2).addReg(Tmp1);
1688     }
1689     return;
1690   case ISD::RET:
1691     Select(N.getOperand(0));
1692     switch (N.getNumOperands()) {
1693     default:
1694       assert(0 && "Unknown return instruction!");
1695     case 3:
1696       assert(N.getOperand(1).getValueType() == MVT::i32 &&
1697              N.getOperand(2).getValueType() == MVT::i32 &&
1698              "Unknown two-register value!");
1699       Tmp1 = SelectExpr(N.getOperand(1));
1700       Tmp2 = SelectExpr(N.getOperand(2));
1701       BuildMI(BB, X86::MOV32rr, 1, X86::EAX).addReg(Tmp1);
1702       BuildMI(BB, X86::MOV32rr, 1, X86::EDX).addReg(Tmp2);
1703       // Declare that EAX & EDX are live on exit.
1704       BuildMI(BB, X86::IMPLICIT_USE, 3).addReg(X86::EAX).addReg(X86::EDX)
1705         .addReg(X86::ESP);
1706       break;
1707     case 2:
1708       Tmp1 = SelectExpr(N.getOperand(1));
1709       switch (N.getOperand(1).getValueType()) {
1710       default: assert(0 && "All other types should have been promoted!!");
1711       case MVT::f64:
1712         BuildMI(BB, X86::FpSETRESULT, 1).addReg(Tmp1);
1713         // Declare that top-of-stack is live on exit
1714         BuildMI(BB, X86::IMPLICIT_USE, 2).addReg(X86::ST0).addReg(X86::ESP);
1715         break;
1716       case MVT::i32:
1717         BuildMI(BB, X86::MOV32rr, 1, X86::EAX).addReg(Tmp1);
1718         BuildMI(BB, X86::IMPLICIT_USE, 2).addReg(X86::EAX).addReg(X86::ESP);
1719         break;
1720       }
1721       break;
1722     case 1:
1723       break;
1724     }
1725     BuildMI(BB, X86::RET, 0); // Just emit a 'ret' instruction
1726     return;
1727   case ISD::BR: {
1728     Select(N.getOperand(0));
1729     MachineBasicBlock *Dest =
1730       cast<BasicBlockSDNode>(N.getOperand(1))->getBasicBlock();
1731     BuildMI(BB, X86::JMP, 1).addMBB(Dest);
1732     return;
1733   }
1734
1735   case ISD::BRCOND: {
1736     Select(N.getOperand(0));
1737     MachineBasicBlock *Dest =
1738       cast<BasicBlockSDNode>(N.getOperand(2))->getBasicBlock();
1739     // Try to fold a setcc into the branch.  If this fails, emit a test/jne
1740     // pair.
1741     if (EmitBranchCC(Dest, N.getOperand(1))) {
1742       Tmp1 = SelectExpr(N.getOperand(1));
1743       BuildMI(BB, X86::TEST8rr, 2).addReg(Tmp1).addReg(Tmp1);
1744       BuildMI(BB, X86::JNE, 1).addMBB(Dest);
1745     }
1746     return;
1747   }
1748   case ISD::LOAD:
1749   case ISD::CALL:
1750   case ISD::DYNAMIC_STACKALLOC:
1751     SelectExpr(N);
1752     return;
1753   case ISD::STORE: {
1754     Select(N.getOperand(0));
1755     // Select the address.
1756     X86AddressMode AM;
1757     SelectAddress(N.getOperand(2), AM);
1758
1759     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1760       Opc = 0;
1761       switch (CN->getValueType(0)) {
1762       default: assert(0 && "Invalid type for operation!");
1763       case MVT::i1:
1764       case MVT::i8:  Opc = X86::MOV8mi; break;
1765       case MVT::i16: Opc = X86::MOV16mi; break;
1766       case MVT::i32: Opc = X86::MOV32mi; break;
1767       case MVT::f32:
1768       case MVT::f64: break;
1769       }
1770       if (Opc) {
1771         addFullAddress(BuildMI(BB, Opc, 4+1), AM).addImm(CN->getValue());
1772         return;
1773       }
1774     }
1775     Tmp1 = SelectExpr(N.getOperand(1));
1776
1777     switch (N.getOperand(1).getValueType()) {
1778     default: assert(0 && "Cannot store this type!");
1779     case MVT::i1:
1780     case MVT::i8:  Opc = X86::MOV8mr; break;
1781     case MVT::i16: Opc = X86::MOV16mr; break;
1782     case MVT::i32: Opc = X86::MOV32mr; break;
1783     case MVT::f32: Opc = X86::FST32m; ContainsFPCode = true; break;
1784     case MVT::f64: Opc = X86::FST64m; ContainsFPCode = true; break;
1785     }
1786     addFullAddress(BuildMI(BB, Opc, 4+1), AM).addReg(Tmp1);
1787     return;
1788   }
1789   case ISD::ADJCALLSTACKDOWN:
1790   case ISD::ADJCALLSTACKUP:
1791     Select(N.getOperand(0));
1792     Tmp1 = cast<ConstantSDNode>(N.getOperand(1))->getValue();
1793
1794     Opc = N.getOpcode() == ISD::ADJCALLSTACKDOWN ? X86::ADJCALLSTACKDOWN :
1795                                                    X86::ADJCALLSTACKUP;
1796     BuildMI(BB, Opc, 1).addImm(Tmp1);
1797     return;
1798   }
1799   assert(0 && "Should not be reached!");
1800 }
1801
1802
1803 /// createX86PatternInstructionSelector - This pass converts an LLVM function
1804 /// into a machine code representation using pattern matching and a machine
1805 /// description file.
1806 ///
1807 FunctionPass *llvm::createX86PatternInstructionSelector(TargetMachine &TM) {
1808   return new ISel(TM);
1809 }