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 "X86Subtarget.h"
  18 #include "llvm/CallingConv.h"
  19 #include "llvm/Constants.h"
  20 #include "llvm/Instructions.h"
  21 #include "llvm/Function.h"
  22 #include "llvm/CodeGen/MachineConstantPool.h"
  23 #include "llvm/CodeGen/MachineFunction.h"
  24 #include "llvm/CodeGen/MachineFrameInfo.h"
  25 #include "llvm/CodeGen/SelectionDAG.h"
  26 #include "llvm/CodeGen/SelectionDAGISel.h"
  27 #include "llvm/CodeGen/SSARegMap.h"
  28 #include "llvm/Target/TargetData.h"
  29 #include "llvm/Target/TargetLowering.h"
  30 #include "llvm/Target/TargetMachine.h"
  31 #include "llvm/Target/TargetOptions.h"
  32 #include "llvm/Support/CFG.h"
  33 #include "llvm/Support/MathExtras.h"
  34 #include "llvm/ADT/Statistic.h"
  35 #include <set>
  36 #include <algorithm>
  37 using namespace llvm;
  38
  39 // FIXME: temporary.
  40 #include "llvm/Support/CommandLine.h"
  41 static cl::opt<bool> EnableFastCC("enable-x86-fastcc", cl::Hidden,
  42                                   cl::desc("Enable fastcc on X86"));
  43
  44 namespace {
  45   // X86 Specific DAG Nodes
  46   namespace X86ISD {
  47     enum NodeType {
  48       // Start the numbering where the builtin ops leave off.
  49       FIRST_NUMBER = ISD::BUILTIN_OP_END,
  50
  51       /// FILD64m - This instruction implements SINT_TO_FP with a
  52       /// 64-bit source in memory and a FP reg result.  This corresponds to
  53       /// the X86::FILD64m instruction.  It has two inputs (token chain and
  54       /// address) and two outputs (FP value and token chain).
  55       FILD64m,
  56
  57       /// FP_TO_INT*_IN_MEM - This instruction implements FP_TO_SINT with the
  58       /// integer destination in memory and a FP reg source.  This corresponds
  59       /// to the X86::FIST*m instructions and the rounding mode change stuff. It
  60       /// has two inputs (token chain and address) and two outputs (FP value and
  61       /// token chain).
  62       FP_TO_INT16_IN_MEM,
  63       FP_TO_INT32_IN_MEM,
  64       FP_TO_INT64_IN_MEM,
  65
  66       /// CALL/TAILCALL - These operations represent an abstract X86 call
  67       /// instruction, which includes a bunch of information.  In particular the
  68       /// operands of these node are:
  69       ///
  70       ///     #0 - The incoming token chain
  71       ///     #1 - The callee
  72       ///     #2 - The number of arg bytes the caller pushes on the stack.
  73       ///     #3 - The number of arg bytes the callee pops off the stack.
  74       ///     #4 - The value to pass in AL/AX/EAX (optional)
  75       ///     #5 - The value to pass in DL/DX/EDX (optional)
  76       ///
  77       /// The result values of these nodes are:
  78       ///
  79       ///     #0 - The outgoing token chain
  80       ///     #1 - The first register result value (optional)
  81       ///     #2 - The second register result value (optional)
  82       ///
  83       /// The CALL vs TAILCALL distinction boils down to whether the callee is
  84       /// known not to modify the caller's stack frame, as is standard with
  85       /// LLVM.
  86       CALL,
  87       TAILCALL,
  88     };
  89   }
  90 }
  91
  92 //===----------------------------------------------------------------------===//
  93 //  X86TargetLowering - X86 Implementation of the TargetLowering interface
  94 namespace {
  95   class X86TargetLowering : public TargetLowering {
  96     int VarArgsFrameIndex;            // FrameIndex for start of varargs area.
  97     int ReturnAddrIndex;              // FrameIndex for return slot.
  98     int BytesToPopOnReturn;           // Number of arg bytes ret should pop.
  99     int BytesCallerReserves;          // Number of arg bytes caller makes.
 100   public:
 101     X86TargetLowering(TargetMachine &TM) : TargetLowering(TM) {
 102       // Set up the TargetLowering object.
 103
 104       // X86 is weird, it always uses i8 for shift amounts and setcc results.
 105       setShiftAmountType(MVT::i8);
 106       setSetCCResultType(MVT::i8);
 107       setSetCCResultContents(ZeroOrOneSetCCResult);
 108       setShiftAmountFlavor(Mask);   // shl X, 32 == shl X, 0
 109
 110       // Set up the register classes.
 111       // FIXME: Eliminate these two classes when legalize can handle promotions
 112       // well.
 113       addRegisterClass(MVT::i1, X86::R8RegisterClass);
 114       addRegisterClass(MVT::i8, X86::R8RegisterClass);
 115       addRegisterClass(MVT::i16, X86::R16RegisterClass);
 116       addRegisterClass(MVT::i32, X86::R32RegisterClass);
 117
 118       // Promote all UINT_TO_FP to larger SINT_TO_FP's, as X86 doesn't have this
 119       // operation.
 120       setOperationAction(ISD::UINT_TO_FP       , MVT::i1   , Promote);
 121       setOperationAction(ISD::UINT_TO_FP       , MVT::i8   , Promote);
 122       setOperationAction(ISD::UINT_TO_FP       , MVT::i16  , Promote);
 123       setOperationAction(ISD::UINT_TO_FP       , MVT::i32  , Promote);
 124
 125       // Promote i1/i8 SINT_TO_FP to larger SINT_TO_FP's, as X86 doesn't have
 126       // this operation.
 127       setOperationAction(ISD::SINT_TO_FP       , MVT::i1   , Promote);
 128       setOperationAction(ISD::SINT_TO_FP       , MVT::i8   , Promote);
 129
 130       if (!X86ScalarSSE) {
 131         // We can handle SINT_TO_FP and FP_TO_SINT from/TO i64 even though i64
 132         // isn't legal.
 133         setOperationAction(ISD::SINT_TO_FP     , MVT::i64  , Custom);
 134         setOperationAction(ISD::FP_TO_SINT     , MVT::i64  , Custom);
 135         setOperationAction(ISD::FP_TO_SINT     , MVT::i32  , Custom);
 136         setOperationAction(ISD::FP_TO_SINT     , MVT::i16  , Custom);
 137       }
 138
 139       // Handle FP_TO_UINT by promoting the destination to a larger signed
 140       // conversion.
 141       setOperationAction(ISD::FP_TO_UINT       , MVT::i1   , Promote);
 142       setOperationAction(ISD::FP_TO_UINT       , MVT::i8   , Promote);
 143       setOperationAction(ISD::FP_TO_UINT       , MVT::i16  , Promote);
 144
 145       if (!X86ScalarSSE)
 146         setOperationAction(ISD::FP_TO_UINT     , MVT::i32  , Promote);
 147
 148       // Promote i1/i8 FP_TO_SINT to larger FP_TO_SINTS's, as X86 doesn't have
 149       // this operation.
 150       setOperationAction(ISD::FP_TO_SINT       , MVT::i1   , Promote);
 151       setOperationAction(ISD::FP_TO_SINT       , MVT::i8   , Promote);
 152       setOperationAction(ISD::FP_TO_SINT       , MVT::i16  , Promote);
 153
 154       setOperationAction(ISD::BRCONDTWOWAY     , MVT::Other, Expand);
 155       setOperationAction(ISD::BRTWOWAY_CC      , MVT::Other, Expand);
 156       setOperationAction(ISD::MEMMOVE          , MVT::Other, Expand);
 157       setOperationAction(ISD::SIGN_EXTEND_INREG, MVT::i16  , Expand);
 158       setOperationAction(ISD::SIGN_EXTEND_INREG, MVT::i1   , Expand);
 159       setOperationAction(ISD::FP_ROUND_INREG   , MVT::f32  , Expand);
 160       setOperationAction(ISD::SEXTLOAD         , MVT::i1   , Expand);
 161       setOperationAction(ISD::SREM             , MVT::f64  , Expand);
 162       setOperationAction(ISD::CTPOP            , MVT::i8   , Expand);
 163       setOperationAction(ISD::CTTZ             , MVT::i8   , Expand);
 164       setOperationAction(ISD::CTLZ             , MVT::i8   , Expand);
 165       setOperationAction(ISD::CTPOP            , MVT::i16  , Expand);
 166       setOperationAction(ISD::CTTZ             , MVT::i16  , Expand);
 167       setOperationAction(ISD::CTLZ             , MVT::i16  , Expand);
 168       setOperationAction(ISD::CTPOP            , MVT::i32  , Expand);
 169       setOperationAction(ISD::CTTZ             , MVT::i32  , Expand);
 170       setOperationAction(ISD::CTLZ             , MVT::i32  , Expand);
 171
 172       setOperationAction(ISD::READIO           , MVT::i1   , Expand);
 173       setOperationAction(ISD::READIO           , MVT::i8   , Expand);
 174       setOperationAction(ISD::READIO           , MVT::i16  , Expand);
 175       setOperationAction(ISD::READIO           , MVT::i32  , Expand);
 176       setOperationAction(ISD::WRITEIO          , MVT::i1   , Expand);
 177       setOperationAction(ISD::WRITEIO          , MVT::i8   , Expand);
 178       setOperationAction(ISD::WRITEIO          , MVT::i16  , Expand);
 179       setOperationAction(ISD::WRITEIO          , MVT::i32  , Expand);
 180
 181       // These should be promoted to a larger select which is supported.
 182       setOperationAction(ISD::SELECT           , MVT::i1   , Promote);
 183       setOperationAction(ISD::SELECT           , MVT::i8   , Promote);
 184
 185       if (X86ScalarSSE) {
 186         // Set up the FP register classes.
 187         addRegisterClass(MVT::f32, X86::RXMMRegisterClass);
 188         addRegisterClass(MVT::f64, X86::RXMMRegisterClass);
 189
 190         // SSE has no load+extend ops
 191         setOperationAction(ISD::EXTLOAD,  MVT::f32, Expand);
 192         setOperationAction(ISD::ZEXTLOAD, MVT::f32, Expand);
 193
 194         // SSE has no i16 to fp conversion, only i32
 195         setOperationAction(ISD::SINT_TO_FP, MVT::i16, Promote);
 196         setOperationAction(ISD::FP_TO_SINT, MVT::i16, Promote);
 197
 198         // Expand FP_TO_UINT into a select.
 199         // FIXME: We would like to use a Custom expander here eventually to do
 200         // the optimal thing for SSE vs. the default expansion in the legalizer.
 201         setOperationAction(ISD::FP_TO_UINT       , MVT::i32  , Expand);
 202
 203         // We don't support sin/cos/sqrt/fmod
 204         setOperationAction(ISD::FSIN , MVT::f64, Expand);
 205         setOperationAction(ISD::FCOS , MVT::f64, Expand);
 206         setOperationAction(ISD::FABS , MVT::f64, Expand);
 207         setOperationAction(ISD::FNEG , MVT::f64, Expand);
 208         setOperationAction(ISD::SREM , MVT::f64, Expand);
 209         setOperationAction(ISD::FSIN , MVT::f32, Expand);
 210         setOperationAction(ISD::FCOS , MVT::f32, Expand);
 211         setOperationAction(ISD::FABS , MVT::f32, Expand);
 212         setOperationAction(ISD::FNEG , MVT::f32, Expand);
 213         setOperationAction(ISD::SREM , MVT::f32, Expand);
 214
 215         addLegalFPImmediate(+0.0); // xorps / xorpd
 216       } else {
 217         // Set up the FP register classes.
 218         addRegisterClass(MVT::f64, X86::RFPRegisterClass);
 219
 220         if (!UnsafeFPMath) {
 221           setOperationAction(ISD::FSIN           , MVT::f64  , Expand);
 222           setOperationAction(ISD::FCOS           , MVT::f64  , Expand);
 223         }
 224
 225         addLegalFPImmediate(+0.0); // FLD0
 226         addLegalFPImmediate(+1.0); // FLD1
 227         addLegalFPImmediate(-0.0); // FLD0/FCHS
 228         addLegalFPImmediate(-1.0); // FLD1/FCHS
 229       }
 230       computeRegisterProperties();
 231
 232       maxStoresPerMemSet = 8; // For %llvm.memset -> sequence of stores
 233       maxStoresPerMemCpy = 8; // For %llvm.memcpy -> sequence of stores
 234       maxStoresPerMemMove = 8; // For %llvm.memmove -> sequence of stores
 235       allowUnalignedStores = true; // x86 supports it!
 236     }
 237
 238     // Return the number of bytes that a function should pop when it returns (in
 239     // addition to the space used by the return address).
 240     //
 241     unsigned getBytesToPopOnReturn() const { return BytesToPopOnReturn; }
 242
 243     // Return the number of bytes that the caller reserves for arguments passed
 244     // to this function.
 245     unsigned getBytesCallerReserves() const { return BytesCallerReserves; }
 246
 247     /// LowerOperation - Provide custom lowering hooks for some operations.
 248     ///
 249     virtual SDOperand LowerOperation(SDOperand Op, SelectionDAG &DAG);
 250
 251     /// LowerArguments - This hook must be implemented to indicate how we should
 252     /// lower the arguments for the specified function, into the specified DAG.
 253     virtual std::vector<SDOperand>
 254     LowerArguments(Function &F, SelectionDAG &DAG);
 255
 256     /// LowerCallTo - This hook lowers an abstract call to a function into an
 257     /// actual call.
 258     virtual std::pair<SDOperand, SDOperand>
 259     LowerCallTo(SDOperand Chain, const Type *RetTy, bool isVarArg, unsigned CC,
 260                 bool isTailCall, SDOperand Callee, ArgListTy &Args,
 261                 SelectionDAG &DAG);
 262
 263     virtual SDOperand LowerVAStart(SDOperand Chain, SDOperand VAListP,
 264                                    Value *VAListV, SelectionDAG &DAG);
 265     virtual std::pair<SDOperand,SDOperand>
 266       LowerVAArg(SDOperand Chain, SDOperand VAListP, Value *VAListV,
 267                  const Type *ArgTy, SelectionDAG &DAG);
 268
 269     virtual std::pair<SDOperand, SDOperand>
 270     LowerFrameReturnAddress(bool isFrameAddr, SDOperand Chain, unsigned Depth,
 271                             SelectionDAG &DAG);
 272
 273     SDOperand getReturnAddressFrameIndex(SelectionDAG &DAG);
 274
 275   private:
 276     // C Calling Convention implementation.
 277     std::vector<SDOperand> LowerCCCArguments(Function &F, SelectionDAG &DAG);
 278     std::pair<SDOperand, SDOperand>
 279     LowerCCCCallTo(SDOperand Chain, const Type *RetTy, bool isVarArg,
 280                    bool isTailCall,
 281                    SDOperand Callee, ArgListTy &Args, SelectionDAG &DAG);
 282
 283     // Fast Calling Convention implementation.
 284     std::vector<SDOperand> LowerFastCCArguments(Function &F, SelectionDAG &DAG);
 285     std::pair<SDOperand, SDOperand>
 286     LowerFastCCCallTo(SDOperand Chain, const Type *RetTy, bool isTailCall,
 287                       SDOperand Callee, ArgListTy &Args, SelectionDAG &DAG);
 288   };
 289 }
 290
 291 std::vector<SDOperand>
 292 X86TargetLowering::LowerArguments(Function &F, SelectionDAG &DAG) {
 293   if (F.getCallingConv() == CallingConv::Fast && EnableFastCC)
 294     return LowerFastCCArguments(F, DAG);
 295   return LowerCCCArguments(F, DAG);
 296 }
 297
 298 std::pair<SDOperand, SDOperand>
 299 X86TargetLowering::LowerCallTo(SDOperand Chain, const Type *RetTy,
 300                                bool isVarArg, unsigned CallingConv,
 301                                bool isTailCall,
 302                                SDOperand Callee, ArgListTy &Args,
 303                                SelectionDAG &DAG) {
 304   assert((!isVarArg || CallingConv == CallingConv::C) &&
 305          "Only C takes varargs!");
 306   if (CallingConv == CallingConv::Fast && EnableFastCC)
 307     return LowerFastCCCallTo(Chain, RetTy, isTailCall, Callee, Args, DAG);
 308   return  LowerCCCCallTo(Chain, RetTy, isVarArg, isTailCall, Callee, Args, DAG);
 309 }
 310
 311 //===----------------------------------------------------------------------===//
 312 //                    C Calling Convention implementation
 313 //===----------------------------------------------------------------------===//
 314
 315 std::vector<SDOperand>
 316 X86TargetLowering::LowerCCCArguments(Function &F, SelectionDAG &DAG) {
 317   std::vector<SDOperand> ArgValues;
 318
 319   MachineFunction &MF = DAG.getMachineFunction();
 320   MachineFrameInfo *MFI = MF.getFrameInfo();
 321
 322   // Add DAG nodes to load the arguments...  On entry to a function on the X86,
 323   // the stack frame looks like this:
 324   //
 325   // [ESP] -- return address
 326   // [ESP + 4] -- first argument (leftmost lexically)
 327   // [ESP + 8] -- second argument, if first argument is four bytes in size
 328   //    ...
 329   //
 330   unsigned ArgOffset = 0;   // Frame mechanisms handle retaddr slot
 331   for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) {
 332     MVT::ValueType ObjectVT = getValueType(I->getType());
 333     unsigned ArgIncrement = 4;
 334     unsigned ObjSize;
 335     switch (ObjectVT) {
 336     default: assert(0 && "Unhandled argument type!");
 337     case MVT::i1:
 338     case MVT::i8:  ObjSize = 1;                break;
 339     case MVT::i16: ObjSize = 2;                break;
 340     case MVT::i32: ObjSize = 4;                break;
 341     case MVT::i64: ObjSize = ArgIncrement = 8; break;
 342     case MVT::f32: ObjSize = 4;                break;
 343     case MVT::f64: ObjSize = ArgIncrement = 8; break;
 344     }
 345     // Create the frame index object for this incoming parameter...
 346     int FI = MFI->CreateFixedObject(ObjSize, ArgOffset);
 347
 348     // Create the SelectionDAG nodes corresponding to a load from this parameter
 349     SDOperand FIN = DAG.getFrameIndex(FI, MVT::i32);
 350
 351     // Don't codegen dead arguments.  FIXME: remove this check when we can nuke
 352     // dead loads.
 353     SDOperand ArgValue;
 354     if (!I->use_empty())
 355       ArgValue = DAG.getLoad(ObjectVT, DAG.getEntryNode(), FIN,
 356                              DAG.getSrcValue(NULL));
 357     else {
 358       if (MVT::isInteger(ObjectVT))
 359         ArgValue = DAG.getConstant(0, ObjectVT);
 360       else
 361         ArgValue = DAG.getConstantFP(0, ObjectVT);
 362     }
 363     ArgValues.push_back(ArgValue);
 364
 365     ArgOffset += ArgIncrement;   // Move on to the next argument...
 366   }
 367
 368   // If the function takes variable number of arguments, make a frame index for
 369   // the start of the first vararg value... for expansion of llvm.va_start.
 370   if (F.isVarArg())
 371     VarArgsFrameIndex = MFI->CreateFixedObject(1, ArgOffset);
 372   ReturnAddrIndex = 0;     // No return address slot generated yet.
 373   BytesToPopOnReturn = 0;  // Callee pops nothing.
 374   BytesCallerReserves = ArgOffset;
 375
 376   // Finally, inform the code generator which regs we return values in.
 377   switch (getValueType(F.getReturnType())) {
 378   default: assert(0 && "Unknown type!");
 379   case MVT::isVoid: break;
 380   case MVT::i1:
 381   case MVT::i8:
 382   case MVT::i16:
 383   case MVT::i32:
 384     MF.addLiveOut(X86::EAX);
 385     break;
 386   case MVT::i64:
 387     MF.addLiveOut(X86::EAX);
 388     MF.addLiveOut(X86::EDX);
 389     break;
 390   case MVT::f32:
 391   case MVT::f64:
 392     MF.addLiveOut(X86::ST0);
 393     break;
 394   }
 395   return ArgValues;
 396 }
 397
 398 std::pair<SDOperand, SDOperand>
 399 X86TargetLowering::LowerCCCCallTo(SDOperand Chain, const Type *RetTy,
 400                                   bool isVarArg, bool isTailCall,
 401                                   SDOperand Callee, ArgListTy &Args,
 402                                   SelectionDAG &DAG) {
 403   // Count how many bytes are to be pushed on the stack.
 404   unsigned NumBytes = 0;
 405
 406   if (Args.empty()) {
 407     // Save zero bytes.
 408     Chain = DAG.getNode(ISD::CALLSEQ_START, MVT::Other, Chain,
 409                         DAG.getConstant(0, getPointerTy()));
 410   } else {
 411     for (unsigned i = 0, e = Args.size(); i != e; ++i)
 412       switch (getValueType(Args[i].second)) {
 413       default: assert(0 && "Unknown value type!");
 414       case MVT::i1:
 415       case MVT::i8:
 416       case MVT::i16:
 417       case MVT::i32:
 418       case MVT::f32:
 419         NumBytes += 4;
 420         break;
 421       case MVT::i64:
 422       case MVT::f64:
 423         NumBytes += 8;
 424         break;
 425       }
 426
 427     Chain = DAG.getNode(ISD::CALLSEQ_START, MVT::Other, Chain,
 428                         DAG.getConstant(NumBytes, getPointerTy()));
 429
 430     // Arguments go on the stack in reverse order, as specified by the ABI.
 431     unsigned ArgOffset = 0;
 432     SDOperand StackPtr = DAG.getCopyFromReg(DAG.getEntryNode(),
 433                                             X86::ESP, MVT::i32);
 434     std::vector<SDOperand> Stores;
 435
 436     for (unsigned i = 0, e = Args.size(); i != e; ++i) {
 437       SDOperand PtrOff = DAG.getConstant(ArgOffset, getPointerTy());
 438       PtrOff = DAG.getNode(ISD::ADD, MVT::i32, StackPtr, PtrOff);
 439
 440       switch (getValueType(Args[i].second)) {
 441       default: assert(0 && "Unexpected ValueType for argument!");
 442       case MVT::i1:
 443       case MVT::i8:
 444       case MVT::i16:
 445         // Promote the integer to 32 bits.  If the input type is signed use a
 446         // sign extend, otherwise use a zero extend.
 447         if (Args[i].second->isSigned())
 448           Args[i].first =DAG.getNode(ISD::SIGN_EXTEND, MVT::i32, Args[i].first);
 449         else
 450           Args[i].first =DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, Args[i].first);
 451
 452         // FALL THROUGH
 453       case MVT::i32:
 454       case MVT::f32:
 455         Stores.push_back(DAG.getNode(ISD::STORE, MVT::Other, Chain,
 456                                      Args[i].first, PtrOff,
 457                                      DAG.getSrcValue(NULL)));
 458         ArgOffset += 4;
 459         break;
 460       case MVT::i64:
 461       case MVT::f64:
 462         Stores.push_back(DAG.getNode(ISD::STORE, MVT::Other, Chain,
 463                                      Args[i].first, PtrOff,
 464                                      DAG.getSrcValue(NULL)));
 465         ArgOffset += 8;
 466         break;
 467       }
 468     }
 469     Chain = DAG.getNode(ISD::TokenFactor, MVT::Other, Stores);
 470   }
 471
 472   std::vector<MVT::ValueType> RetVals;
 473   MVT::ValueType RetTyVT = getValueType(RetTy);
 474   RetVals.push_back(MVT::Other);
 475
 476   // The result values produced have to be legal.  Promote the result.
 477   switch (RetTyVT) {
 478   case MVT::isVoid: break;
 479   default:
 480     RetVals.push_back(RetTyVT);
 481     break;
 482   case MVT::i1:
 483   case MVT::i8:
 484   case MVT::i16:
 485     RetVals.push_back(MVT::i32);
 486     break;
 487   case MVT::f32:
 488     if (X86ScalarSSE)
 489       RetVals.push_back(MVT::f32);
 490     else
 491       RetVals.push_back(MVT::f64);
 492     break;
 493   case MVT::i64:
 494     RetVals.push_back(MVT::i32);
 495     RetVals.push_back(MVT::i32);
 496     break;
 497   }
 498   std::vector<SDOperand> Ops;
 499   Ops.push_back(Chain);
 500   Ops.push_back(Callee);
 501   Ops.push_back(DAG.getConstant(NumBytes, getPointerTy()));
 502   Ops.push_back(DAG.getConstant(0, getPointerTy()));
 503   SDOperand TheCall = DAG.getNode(isTailCall ? X86ISD::TAILCALL : X86ISD::CALL,
 504                                   RetVals, Ops);
 505   Chain = DAG.getNode(ISD::CALLSEQ_END, MVT::Other, TheCall);
 506
 507   SDOperand ResultVal;
 508   switch (RetTyVT) {
 509   case MVT::isVoid: break;
 510   default:
 511     ResultVal = TheCall.getValue(1);
 512     break;
 513   case MVT::i1:
 514   case MVT::i8:
 515   case MVT::i16:
 516     ResultVal = DAG.getNode(ISD::TRUNCATE, RetTyVT, TheCall.getValue(1));
 517     break;
 518   case MVT::f32:
 519     // FIXME: we would really like to remember that this FP_ROUND operation is
 520     // okay to eliminate if we allow excess FP precision.
 521     ResultVal = DAG.getNode(ISD::FP_ROUND, MVT::f32, TheCall.getValue(1));
 522     break;
 523   case MVT::i64:
 524     ResultVal = DAG.getNode(ISD::BUILD_PAIR, MVT::i64, TheCall.getValue(1),
 525                             TheCall.getValue(2));
 526     break;
 527   }
 528
 529   return std::make_pair(ResultVal, Chain);
 530 }
 531
 532 SDOperand
 533 X86TargetLowering::LowerVAStart(SDOperand Chain, SDOperand VAListP,
 534                                 Value *VAListV, SelectionDAG &DAG) {
 535   // vastart just stores the address of the VarArgsFrameIndex slot.
 536   SDOperand FR = DAG.getFrameIndex(VarArgsFrameIndex, MVT::i32);
 537   return DAG.getNode(ISD::STORE, MVT::Other, Chain, FR, VAListP,
 538                      DAG.getSrcValue(VAListV));
 539 }
 540
 541
 542 std::pair<SDOperand,SDOperand>
 543 X86TargetLowering::LowerVAArg(SDOperand Chain, SDOperand VAListP,
 544                               Value *VAListV, const Type *ArgTy,
 545                               SelectionDAG &DAG) {
 546   MVT::ValueType ArgVT = getValueType(ArgTy);
 547   SDOperand Val = DAG.getLoad(MVT::i32, Chain,
 548                               VAListP, DAG.getSrcValue(VAListV));
 549   SDOperand Result = DAG.getLoad(ArgVT, Chain, Val,
 550                                  DAG.getSrcValue(NULL));
 551   unsigned Amt;
 552   if (ArgVT == MVT::i32)
 553     Amt = 4;
 554   else {
 555     assert((ArgVT == MVT::i64 || ArgVT == MVT::f64) &&
 556            "Other types should have been promoted for varargs!");
 557     Amt = 8;
 558   }
 559   Val = DAG.getNode(ISD::ADD, Val.getValueType(), Val,
 560                     DAG.getConstant(Amt, Val.getValueType()));
 561   Chain = DAG.getNode(ISD::STORE, MVT::Other, Chain,
 562                       Val, VAListP, DAG.getSrcValue(VAListV));
 563   return std::make_pair(Result, Chain);
 564 }
 565
 566 //===----------------------------------------------------------------------===//
 567 //                    Fast Calling Convention implementation
 568 //===----------------------------------------------------------------------===//
 569 //
 570 // The X86 'fast' calling convention passes up to two integer arguments in
 571 // registers (an appropriate portion of EAX/EDX), passes arguments in C order,
 572 // and requires that the callee pop its arguments off the stack (allowing proper
 573 // tail calls), and has the same return value conventions as C calling convs.
 574 //
 575 // This calling convention always arranges for the callee pop value to be 8n+4
 576 // bytes, which is needed for tail recursion elimination and stack alignment
 577 // reasons.
 578 //
 579 // Note that this can be enhanced in the future to pass fp vals in registers
 580 // (when we have a global fp allocator) and do other tricks.
 581 //
 582
 583 /// AddLiveIn - This helper function adds the specified physical register to the
 584 /// MachineFunction as a live in value.  It also creates a corresponding virtual
 585 /// register for it.
 586 static unsigned AddLiveIn(MachineFunction &MF, unsigned PReg,
 587                           TargetRegisterClass *RC) {
 588   assert(RC->contains(PReg) && "Not the correct regclass!");
 589   unsigned VReg = MF.getSSARegMap()->createVirtualRegister(RC);
 590   MF.addLiveIn(PReg, VReg);
 591   return VReg;
 592 }
 593
 594
 595 std::vector<SDOperand>
 596 X86TargetLowering::LowerFastCCArguments(Function &F, SelectionDAG &DAG) {
 597   std::vector<SDOperand> ArgValues;
 598
 599   MachineFunction &MF = DAG.getMachineFunction();
 600   MachineFrameInfo *MFI = MF.getFrameInfo();
 601
 602   // Add DAG nodes to load the arguments...  On entry to a function the stack
 603   // frame looks like this:
 604   //
 605   // [ESP] -- return address
 606   // [ESP + 4] -- first nonreg argument (leftmost lexically)
 607   // [ESP + 8] -- second nonreg argument, if first argument is 4 bytes in size
 608   //    ...
 609   unsigned ArgOffset = 0;   // Frame mechanisms handle retaddr slot
 610
 611   // Keep track of the number of integer regs passed so far.  This can be either
 612   // 0 (neither EAX or EDX used), 1 (EAX is used) or 2 (EAX and EDX are both
 613   // used).
 614   unsigned NumIntRegs = 0;
 615
 616   for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) {
 617     MVT::ValueType ObjectVT = getValueType(I->getType());
 618     unsigned ArgIncrement = 4;
 619     unsigned ObjSize = 0;
 620     SDOperand ArgValue;
 621
 622     switch (ObjectVT) {
 623     default: assert(0 && "Unhandled argument type!");
 624     case MVT::i1:
 625     case MVT::i8:
 626       if (NumIntRegs < 2) {
 627         if (!I->use_empty()) {
 628           unsigned VReg = AddLiveIn(MF, NumIntRegs ? X86::DL : X86::AL,
 629                                     X86::R8RegisterClass);
 630           ArgValue = DAG.getCopyFromReg(DAG.getRoot(), VReg, MVT::i8);
 631           DAG.setRoot(ArgValue.getValue(1));
 632         }
 633         ++NumIntRegs;
 634         break;
 635       }
 636
 637       ObjSize = 1;
 638       break;
 639     case MVT::i16:
 640       if (NumIntRegs < 2) {
 641         if (!I->use_empty()) {
 642           unsigned VReg = AddLiveIn(MF, NumIntRegs ? X86::DX : X86::AX,
 643                                     X86::R16RegisterClass);
 644           ArgValue = DAG.getCopyFromReg(DAG.getRoot(), VReg, MVT::i16);
 645           DAG.setRoot(ArgValue.getValue(1));
 646         }
 647         ++NumIntRegs;
 648         break;
 649       }
 650       ObjSize = 2;
 651       break;
 652     case MVT::i32:
 653       if (NumIntRegs < 2) {
 654         if (!I->use_empty()) {
 655           unsigned VReg = AddLiveIn(MF,NumIntRegs ? X86::EDX : X86::EAX,
 656                                     X86::R32RegisterClass);
 657           ArgValue = DAG.getCopyFromReg(DAG.getRoot(), VReg, MVT::i32);
 658           DAG.setRoot(ArgValue.getValue(1));
 659         }
 660         ++NumIntRegs;
 661         break;
 662       }
 663       ObjSize = 4;
 664       break;
 665     case MVT::i64:
 666       if (NumIntRegs == 0) {
 667         if (!I->use_empty()) {
 668           unsigned BotReg = AddLiveIn(MF, X86::EAX, X86::R32RegisterClass);
 669           unsigned TopReg = AddLiveIn(MF, X86::EDX, X86::R32RegisterClass);
 670
 671           SDOperand Low = DAG.getCopyFromReg(DAG.getRoot(), BotReg, MVT::i32);
 672           SDOperand Hi  = DAG.getCopyFromReg(Low.getValue(1), TopReg, MVT::i32);
 673           DAG.setRoot(Hi.getValue(1));
 674
 675           ArgValue = DAG.getNode(ISD::BUILD_PAIR, MVT::i64, Low, Hi);
 676         }
 677         NumIntRegs = 2;
 678         break;
 679       } else if (NumIntRegs == 1) {
 680         if (!I->use_empty()) {
 681           unsigned BotReg = AddLiveIn(MF, X86::EDX, X86::R32RegisterClass);
 682           SDOperand Low = DAG.getCopyFromReg(DAG.getRoot(), BotReg, MVT::i32);
 683           DAG.setRoot(Low.getValue(1));
 684
 685           // Load the high part from memory.
 686           // Create the frame index object for this incoming parameter...
 687           int FI = MFI->CreateFixedObject(4, ArgOffset);
 688           SDOperand FIN = DAG.getFrameIndex(FI, MVT::i32);
 689           SDOperand Hi = DAG.getLoad(MVT::i32, DAG.getEntryNode(), FIN,
 690                                      DAG.getSrcValue(NULL));
 691           ArgValue = DAG.getNode(ISD::BUILD_PAIR, MVT::i64, Low, Hi);
 692         }
 693         ArgOffset += 4;
 694         NumIntRegs = 2;
 695         break;
 696       }
 697       ObjSize = ArgIncrement = 8;
 698       break;
 699     case MVT::f32: ObjSize = 4;                break;
 700     case MVT::f64: ObjSize = ArgIncrement = 8; break;
 701     }
 702
 703     // Don't codegen dead arguments.  FIXME: remove this check when we can nuke
 704     // dead loads.
 705     if (ObjSize && !I->use_empty()) {
 706       // Create the frame index object for this incoming parameter...
 707       int FI = MFI->CreateFixedObject(ObjSize, ArgOffset);
 708
 709       // Create the SelectionDAG nodes corresponding to a load from this
 710       // parameter.
 711       SDOperand FIN = DAG.getFrameIndex(FI, MVT::i32);
 712
 713       ArgValue = DAG.getLoad(ObjectVT, DAG.getEntryNode(), FIN,
 714                              DAG.getSrcValue(NULL));
 715     } else if (ArgValue.Val == 0) {
 716       if (MVT::isInteger(ObjectVT))
 717         ArgValue = DAG.getConstant(0, ObjectVT);
 718       else
 719         ArgValue = DAG.getConstantFP(0, ObjectVT);
 720     }
 721     ArgValues.push_back(ArgValue);
 722
 723     if (ObjSize)
 724       ArgOffset += ArgIncrement;   // Move on to the next argument.
 725   }
 726
 727   // Make sure the instruction takes 8n+4 bytes to make sure the start of the
 728   // arguments and the arguments after the retaddr has been pushed are aligned.
 729   if ((ArgOffset & 7) == 0)
 730     ArgOffset += 4;
 731
 732   VarArgsFrameIndex = 0xAAAAAAA;   // fastcc functions can't have varargs.
 733   ReturnAddrIndex = 0;             // No return address slot generated yet.
 734   BytesToPopOnReturn = ArgOffset;  // Callee pops all stack arguments.
 735   BytesCallerReserves = 0;
 736
 737   // Finally, inform the code generator which regs we return values in.
 738   switch (getValueType(F.getReturnType())) {
 739   default: assert(0 && "Unknown type!");
 740   case MVT::isVoid: break;
 741   case MVT::i1:
 742   case MVT::i8:
 743   case MVT::i16:
 744   case MVT::i32:
 745     MF.addLiveOut(X86::EAX);
 746     break;
 747   case MVT::i64:
 748     MF.addLiveOut(X86::EAX);
 749     MF.addLiveOut(X86::EDX);
 750     break;
 751   case MVT::f32:
 752   case MVT::f64:
 753     MF.addLiveOut(X86::ST0);
 754     break;
 755   }
 756   return ArgValues;
 757 }
 758
 759 std::pair<SDOperand, SDOperand>
 760 X86TargetLowering::LowerFastCCCallTo(SDOperand Chain, const Type *RetTy,
 761                                      bool isTailCall, SDOperand Callee,
 762                                      ArgListTy &Args, SelectionDAG &DAG) {
 763   // Count how many bytes are to be pushed on the stack.
 764   unsigned NumBytes = 0;
 765
 766   // Keep track of the number of integer regs passed so far.  This can be either
 767   // 0 (neither EAX or EDX used), 1 (EAX is used) or 2 (EAX and EDX are both
 768   // used).
 769   unsigned NumIntRegs = 0;
 770
 771   for (unsigned i = 0, e = Args.size(); i != e; ++i)
 772     switch (getValueType(Args[i].second)) {
 773     default: assert(0 && "Unknown value type!");
 774     case MVT::i1:
 775     case MVT::i8:
 776     case MVT::i16:
 777     case MVT::i32:
 778       if (NumIntRegs < 2) {
 779         ++NumIntRegs;
 780         break;
 781       }
 782       // fall through
 783     case MVT::f32:
 784       NumBytes += 4;
 785       break;
 786     case MVT::i64:
 787       if (NumIntRegs == 0) {
 788         NumIntRegs = 2;
 789         break;
 790       } else if (NumIntRegs == 1) {
 791         NumIntRegs = 2;
 792         NumBytes += 4;
 793         break;
 794       }
 795
 796       // fall through
 797     case MVT::f64:
 798       NumBytes += 8;
 799       break;
 800     }
 801
 802   // Make sure the instruction takes 8n+4 bytes to make sure the start of the
 803   // arguments and the arguments after the retaddr has been pushed are aligned.
 804   if ((NumBytes & 7) == 0)
 805     NumBytes += 4;
 806
 807   Chain = DAG.getNode(ISD::CALLSEQ_START, MVT::Other, Chain,
 808                       DAG.getConstant(NumBytes, getPointerTy()));
 809
 810   // Arguments go on the stack in reverse order, as specified by the ABI.
 811   unsigned ArgOffset = 0;
 812   SDOperand StackPtr = DAG.getCopyFromReg(DAG.getEntryNode(),
 813                                           X86::ESP, MVT::i32);
 814   NumIntRegs = 0;
 815   std::vector<SDOperand> Stores;
 816   std::vector<SDOperand> RegValuesToPass;
 817   for (unsigned i = 0, e = Args.size(); i != e; ++i) {
 818     switch (getValueType(Args[i].second)) {
 819     default: assert(0 && "Unexpected ValueType for argument!");
 820     case MVT::i1:
 821     case MVT::i8:
 822     case MVT::i16:
 823     case MVT::i32:
 824       if (NumIntRegs < 2) {
 825         RegValuesToPass.push_back(Args[i].first);
 826         ++NumIntRegs;
 827         break;
 828       }
 829       // Fall through
 830     case MVT::f32: {
 831       SDOperand PtrOff = DAG.getConstant(ArgOffset, getPointerTy());
 832       PtrOff = DAG.getNode(ISD::ADD, MVT::i32, StackPtr, PtrOff);
 833       Stores.push_back(DAG.getNode(ISD::STORE, MVT::Other, Chain,
 834                                    Args[i].first, PtrOff,
 835                                    DAG.getSrcValue(NULL)));
 836       ArgOffset += 4;
 837       break;
 838     }
 839     case MVT::i64:
 840       if (NumIntRegs < 2) {    // Can pass part of it in regs?
 841         SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, MVT::i32,
 842                                    Args[i].first, DAG.getConstant(1, MVT::i32));
 843         SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, MVT::i32,
 844                                    Args[i].first, DAG.getConstant(0, MVT::i32));
 845         RegValuesToPass.push_back(Lo);
 846         ++NumIntRegs;
 847         if (NumIntRegs < 2) {   // Pass both parts in regs?
 848           RegValuesToPass.push_back(Hi);
 849           ++NumIntRegs;
 850         } else {
 851           // Pass the high part in memory.
 852           SDOperand PtrOff = DAG.getConstant(ArgOffset, getPointerTy());
 853           PtrOff = DAG.getNode(ISD::ADD, MVT::i32, StackPtr, PtrOff);
 854           Stores.push_back(DAG.getNode(ISD::STORE, MVT::Other, Chain,
 855                                        Hi, PtrOff, DAG.getSrcValue(NULL)));
 856           ArgOffset += 4;
 857         }
 858         break;
 859       }
 860       // Fall through
 861     case MVT::f64:
 862       SDOperand PtrOff = DAG.getConstant(ArgOffset, getPointerTy());
 863       PtrOff = DAG.getNode(ISD::ADD, MVT::i32, StackPtr, PtrOff);
 864       Stores.push_back(DAG.getNode(ISD::STORE, MVT::Other, Chain,
 865                                    Args[i].first, PtrOff,
 866                                    DAG.getSrcValue(NULL)));
 867       ArgOffset += 8;
 868       break;
 869     }
 870   }
 871   if (!Stores.empty())
 872     Chain = DAG.getNode(ISD::TokenFactor, MVT::Other, Stores);
 873
 874   // Make sure the instruction takes 8n+4 bytes to make sure the start of the
 875   // arguments and the arguments after the retaddr has been pushed are aligned.
 876   if ((ArgOffset & 7) == 0)
 877     ArgOffset += 4;
 878
 879   std::vector<MVT::ValueType> RetVals;
 880   MVT::ValueType RetTyVT = getValueType(RetTy);
 881
 882   RetVals.push_back(MVT::Other);
 883
 884   // The result values produced have to be legal.  Promote the result.
 885   switch (RetTyVT) {
 886   case MVT::isVoid: break;
 887   default:
 888     RetVals.push_back(RetTyVT);
 889     break;
 890   case MVT::i1:
 891   case MVT::i8:
 892   case MVT::i16:
 893     RetVals.push_back(MVT::i32);
 894     break;
 895   case MVT::f32:
 896     if (X86ScalarSSE)
 897       RetVals.push_back(MVT::f32);
 898     else
 899       RetVals.push_back(MVT::f64);
 900     break;
 901   case MVT::i64:
 902     RetVals.push_back(MVT::i32);
 903     RetVals.push_back(MVT::i32);
 904     break;
 905   }
 906
 907   std::vector<SDOperand> Ops;
 908   Ops.push_back(Chain);
 909   Ops.push_back(Callee);
 910   Ops.push_back(DAG.getConstant(ArgOffset, getPointerTy()));
 911   // Callee pops all arg values on the stack.
 912   Ops.push_back(DAG.getConstant(ArgOffset, getPointerTy()));
 913
 914   // Pass register arguments as needed.
 915   Ops.insert(Ops.end(), RegValuesToPass.begin(), RegValuesToPass.end());
 916
 917   SDOperand TheCall = DAG.getNode(isTailCall ? X86ISD::TAILCALL : X86ISD::CALL,
 918                                   RetVals, Ops);
 919   Chain = DAG.getNode(ISD::CALLSEQ_END, MVT::Other, TheCall);
 920
 921   SDOperand ResultVal;
 922   switch (RetTyVT) {
 923   case MVT::isVoid: break;
 924   default:
 925     ResultVal = TheCall.getValue(1);
 926     break;
 927   case MVT::i1:
 928   case MVT::i8:
 929   case MVT::i16:
 930     ResultVal = DAG.getNode(ISD::TRUNCATE, RetTyVT, TheCall.getValue(1));
 931     break;
 932   case MVT::f32:
 933     // FIXME: we would really like to remember that this FP_ROUND operation is
 934     // okay to eliminate if we allow excess FP precision.
 935     ResultVal = DAG.getNode(ISD::FP_ROUND, MVT::f32, TheCall.getValue(1));
 936     break;
 937   case MVT::i64:
 938     ResultVal = DAG.getNode(ISD::BUILD_PAIR, MVT::i64, TheCall.getValue(1),
 939                             TheCall.getValue(2));
 940     break;
 941   }
 942
 943   return std::make_pair(ResultVal, Chain);
 944 }
 945
 946 SDOperand X86TargetLowering::getReturnAddressFrameIndex(SelectionDAG &DAG) {
 947   if (ReturnAddrIndex == 0) {
 948     // Set up a frame object for the return address.
 949     MachineFunction &MF = DAG.getMachineFunction();
 950     ReturnAddrIndex = MF.getFrameInfo()->CreateFixedObject(4, -4);
 951   }
 952
 953   return DAG.getFrameIndex(ReturnAddrIndex, MVT::i32);
 954 }
 955
 956
 957
 958 std::pair<SDOperand, SDOperand> X86TargetLowering::
 959 LowerFrameReturnAddress(bool isFrameAddress, SDOperand Chain, unsigned Depth,
 960                         SelectionDAG &DAG) {
 961   SDOperand Result;
 962   if (Depth)        // Depths > 0 not supported yet!
 963     Result = DAG.getConstant(0, getPointerTy());
 964   else {
 965     SDOperand RetAddrFI = getReturnAddressFrameIndex(DAG);
 966     if (!isFrameAddress)
 967       // Just load the return address
 968       Result = DAG.getLoad(MVT::i32, DAG.getEntryNode(), RetAddrFI,
 969                            DAG.getSrcValue(NULL));
 970     else
 971       Result = DAG.getNode(ISD::SUB, MVT::i32, RetAddrFI,
 972                            DAG.getConstant(4, MVT::i32));
 973   }
 974   return std::make_pair(Result, Chain);
 975 }
 976
 977 //===----------------------------------------------------------------------===//
 978 //                           X86 Custom Lowering Hooks
 979 //===----------------------------------------------------------------------===//
 980
 981 /// LowerOperation - Provide custom lowering hooks for some operations.
 982 ///
 983 SDOperand X86TargetLowering::LowerOperation(SDOperand Op, SelectionDAG &DAG) {
 984   switch (Op.getOpcode()) {
 985   default: assert(0 && "Should not custom lower this!");
 986   case ISD::SINT_TO_FP: {
 987     assert(Op.getValueType() == MVT::f64 &&
 988            Op.getOperand(0).getValueType() == MVT::i64 &&
 989            "Unknown SINT_TO_FP to lower!");
 990     // We lower sint64->FP into a store to a temporary stack slot, followed by a
 991     // FILD64m node.
 992     MachineFunction &MF = DAG.getMachineFunction();
 993     int SSFI = MF.getFrameInfo()->CreateStackObject(8, 8);
 994     SDOperand StackSlot = DAG.getFrameIndex(SSFI, getPointerTy());
 995     SDOperand Store = DAG.getNode(ISD::STORE, MVT::Other, DAG.getEntryNode(),
 996                            Op.getOperand(0), StackSlot, DAG.getSrcValue(NULL));
 997     std::vector<MVT::ValueType> RTs;
 998     RTs.push_back(MVT::f64);
 999     RTs.push_back(MVT::Other);
1000     std::vector<SDOperand> Ops;
1001     Ops.push_back(Store);
1002     Ops.push_back(StackSlot);
1003     return DAG.getNode(X86ISD::FILD64m, RTs, Ops);
1004   }
1005   case ISD::FP_TO_SINT: {
1006     assert(Op.getValueType() <= MVT::i64 && Op.getValueType() >= MVT::i16 &&
1007            Op.getOperand(0).getValueType() == MVT::f64 &&
1008            "Unknown FP_TO_SINT to lower!");
1009     // We lower FP->sint64 into FISTP64, followed by a load, all to a temporary
1010     // stack slot.
1011     MachineFunction &MF = DAG.getMachineFunction();
1012     unsigned MemSize = MVT::getSizeInBits(Op.getValueType())/8;
1013     int SSFI = MF.getFrameInfo()->CreateStackObject(MemSize, MemSize);
1014     SDOperand StackSlot = DAG.getFrameIndex(SSFI, getPointerTy());
1015
1016     unsigned Opc;
1017     switch (Op.getValueType()) {
1018     default: assert(0 && "Invalid FP_TO_SINT to lower!");
1019     case MVT::i16: Opc = X86ISD::FP_TO_INT16_IN_MEM; break;
1020     case MVT::i32: Opc = X86ISD::FP_TO_INT32_IN_MEM; break;
1021     case MVT::i64: Opc = X86ISD::FP_TO_INT64_IN_MEM; break;
1022     }
1023
1024     // Build the FP_TO_INT*_IN_MEM
1025     std::vector<SDOperand> Ops;
1026     Ops.push_back(DAG.getEntryNode());
1027     Ops.push_back(Op.getOperand(0));
1028     Ops.push_back(StackSlot);
1029     SDOperand FIST = DAG.getNode(Opc, MVT::Other, Ops);
1030
1031     // Load the result.
1032     return DAG.getLoad(Op.getValueType(), FIST, StackSlot,
1033                        DAG.getSrcValue(NULL));
1034   }
1035   }
1036 }
1037
1038
1039 //===----------------------------------------------------------------------===//
1040 //                      Pattern Matcher Implementation
1041 //===----------------------------------------------------------------------===//
1042
1043 namespace {
1044   /// X86ISelAddressMode - This corresponds to X86AddressMode, but uses
1045   /// SDOperand's instead of register numbers for the leaves of the matched
1046   /// tree.
1047   struct X86ISelAddressMode {
1048     enum {
1049       RegBase,
1050       FrameIndexBase,
1051     } BaseType;
1052
1053     struct {            // This is really a union, discriminated by BaseType!
1054       SDOperand Reg;
1055       int FrameIndex;
1056     } Base;
1057
1058     unsigned Scale;
1059     SDOperand IndexReg;
1060     unsigned Disp;
1061     GlobalValue *GV;
1062
1063     X86ISelAddressMode()
1064       : BaseType(RegBase), Scale(1), IndexReg(), Disp(), GV(0) {
1065     }
1066   };
1067 }
1068
1069
1070 namespace {
1071   Statistic<>
1072   NumFPKill("x86-codegen", "Number of FP_REG_KILL instructions added");
1073
1074   //===--------------------------------------------------------------------===//
1075   /// ISel - X86 specific code to select X86 machine instructions for
1076   /// SelectionDAG operations.
1077   ///
1078   class ISel : public SelectionDAGISel {
1079     /// ContainsFPCode - Every instruction we select that uses or defines a FP
1080     /// register should set this to true.
1081     bool ContainsFPCode;
1082
1083     /// X86Lowering - This object fully describes how to lower LLVM code to an
1084     /// X86-specific SelectionDAG.
1085     X86TargetLowering X86Lowering;
1086
1087     /// RegPressureMap - This keeps an approximate count of the number of
1088     /// registers required to evaluate each node in the graph.
1089     std::map<SDNode*, unsigned> RegPressureMap;
1090
1091     /// ExprMap - As shared expressions are codegen'd, we keep track of which
1092     /// vreg the value is produced in, so we only emit one copy of each compiled
1093     /// tree.
1094     std::map<SDOperand, unsigned> ExprMap;
1095
1096     /// TheDAG - The DAG being selected during Select* operations.
1097     SelectionDAG *TheDAG;
1098
1099     /// Subtarget - Keep a pointer to the X86Subtarget around so that we can
1100     /// make the right decision when generating code for different targets.
1101     const X86Subtarget *Subtarget;
1102   public:
1103     ISel(TargetMachine &TM) : SelectionDAGISel(X86Lowering), X86Lowering(TM) {
1104       Subtarget = &TM.getSubtarget<X86Subtarget>();
1105     }
1106
1107     virtual const char *getPassName() const {
1108       return "X86 Pattern Instruction Selection";
1109     }
1110
1111     unsigned getRegPressure(SDOperand O) {
1112       return RegPressureMap[O.Val];
1113     }
1114     unsigned ComputeRegPressure(SDOperand O);
1115
1116     /// InstructionSelectBasicBlock - This callback is invoked by
1117     /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
1118     virtual void InstructionSelectBasicBlock(SelectionDAG &DAG);
1119
1120     virtual void EmitFunctionEntryCode(Function &Fn, MachineFunction &MF);
1121
1122     bool isFoldableLoad(SDOperand Op, SDOperand OtherOp,
1123                         bool FloatPromoteOk = false);
1124     void EmitFoldedLoad(SDOperand Op, X86AddressMode &AM);
1125     bool TryToFoldLoadOpStore(SDNode *Node);
1126     bool EmitOrOpOp(SDOperand Op1, SDOperand Op2, unsigned DestReg);
1127     void EmitCMP(SDOperand LHS, SDOperand RHS, bool isOnlyUse);
1128     bool EmitBranchCC(MachineBasicBlock *Dest, SDOperand Chain, SDOperand Cond);
1129     void EmitSelectCC(SDOperand Cond, SDOperand True, SDOperand False,
1130                       MVT::ValueType SVT, unsigned RDest);
1131     unsigned SelectExpr(SDOperand N);
1132
1133     X86AddressMode SelectAddrExprs(const X86ISelAddressMode &IAM);
1134     bool MatchAddress(SDOperand N, X86ISelAddressMode &AM);
1135     void SelectAddress(SDOperand N, X86AddressMode &AM);
1136     bool EmitPotentialTailCall(SDNode *Node);
1137     void EmitFastCCToFastCCTailCall(SDNode *TailCallNode);
1138     void Select(SDOperand N);
1139   };
1140 }
1141
1142 /// EmitSpecialCodeForMain - Emit any code that needs to be executed only in
1143 /// the main function.
1144 static void EmitSpecialCodeForMain(MachineBasicBlock *BB,
1145                                    MachineFrameInfo *MFI) {
1146   // Switch the FPU to 64-bit precision mode for better compatibility and speed.
1147   int CWFrameIdx = MFI->CreateStackObject(2, 2);
1148   addFrameReference(BuildMI(BB, X86::FNSTCW16m, 4), CWFrameIdx);
1149
1150   // Set the high part to be 64-bit precision.
1151   addFrameReference(BuildMI(BB, X86::MOV8mi, 5),
1152                     CWFrameIdx, 1).addImm(2);
1153
1154   // Reload the modified control word now.
1155   addFrameReference(BuildMI(BB, X86::FLDCW16m, 4), CWFrameIdx);
1156 }
1157
1158 void ISel::EmitFunctionEntryCode(Function &Fn, MachineFunction &MF) {
1159   // If this function has live-in values, emit the copies from pregs to vregs at
1160   // the top of the function, before anything else.
1161   MachineBasicBlock *BB = MF.begin();
1162   if (MF.livein_begin() != MF.livein_end()) {
1163     SSARegMap *RegMap = MF.getSSARegMap();
1164     for (MachineFunction::livein_iterator LI = MF.livein_begin(),
1165          E = MF.livein_end(); LI != E; ++LI) {
1166       const TargetRegisterClass *RC = RegMap->getRegClass(LI->second);
1167       if (RC == X86::R8RegisterClass) {
1168         BuildMI(BB, X86::MOV8rr, 1, LI->second).addReg(LI->first);
1169       } else if (RC == X86::R16RegisterClass) {
1170         BuildMI(BB, X86::MOV16rr, 1, LI->second).addReg(LI->first);
1171       } else if (RC == X86::R32RegisterClass) {
1172         BuildMI(BB, X86::MOV32rr, 1, LI->second).addReg(LI->first);
1173       } else if (RC == X86::RFPRegisterClass) {
1174         BuildMI(BB, X86::FpMOV, 1, LI->second).addReg(LI->first);
1175       } else if (RC == X86::RXMMRegisterClass) {
1176         BuildMI(BB, X86::MOVAPDrr, 1, LI->second).addReg(LI->first);
1177       } else {
1178         assert(0 && "Unknown regclass!");
1179       }
1180     }
1181   }
1182
1183
1184   // If this is main, emit special code for main.
1185   if (Fn.hasExternalLinkage() && Fn.getName() == "main")
1186     EmitSpecialCodeForMain(BB, MF.getFrameInfo());
1187 }
1188
1189
1190 /// InstructionSelectBasicBlock - This callback is invoked by SelectionDAGISel
1191 /// when it has created a SelectionDAG for us to codegen.
1192 void ISel::InstructionSelectBasicBlock(SelectionDAG &DAG) {
1193   // While we're doing this, keep track of whether we see any FP code for
1194   // FP_REG_KILL insertion.
1195   ContainsFPCode = false;
1196   MachineFunction *MF = BB->getParent();
1197
1198   // Scan the PHI nodes that already are inserted into this basic block.  If any
1199   // of them is a PHI of a floating point value, we need to insert an
1200   // FP_REG_KILL.
1201   SSARegMap *RegMap = MF->getSSARegMap();
1202   if (BB != MF->begin())
1203     for (MachineBasicBlock::iterator I = BB->begin(), E = BB->end();
1204          I != E; ++I) {
1205       assert(I->getOpcode() == X86::PHI &&
1206              "Isn't just PHI nodes?");
1207       if (RegMap->getRegClass(I->getOperand(0).getReg()) ==
1208           X86::RFPRegisterClass) {
1209         ContainsFPCode = true;
1210         break;
1211       }
1212     }
1213
1214   // Compute the RegPressureMap, which is an approximation for the number of
1215   // registers required to compute each node.
1216   ComputeRegPressure(DAG.getRoot());
1217
1218   TheDAG = &DAG;
1219
1220   // Codegen the basic block.
1221   Select(DAG.getRoot());
1222
1223   TheDAG = 0;
1224
1225   // Finally, look at all of the successors of this block.  If any contain a PHI
1226   // node of FP type, we need to insert an FP_REG_KILL in this block.
1227   for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(),
1228          E = BB->succ_end(); SI != E && !ContainsFPCode; ++SI)
1229     for (MachineBasicBlock::iterator I = (*SI)->begin(), E = (*SI)->end();
1230          I != E && I->getOpcode() == X86::PHI; ++I) {
1231       if (RegMap->getRegClass(I->getOperand(0).getReg()) ==
1232           X86::RFPRegisterClass) {
1233         ContainsFPCode = true;
1234         break;
1235       }
1236     }
1237
1238   // Final check, check LLVM BB's that are successors to the LLVM BB
1239   // corresponding to BB for FP PHI nodes.
1240   const BasicBlock *LLVMBB = BB->getBasicBlock();
1241   const PHINode *PN;
1242   if (!ContainsFPCode)
1243     for (succ_const_iterator SI = succ_begin(LLVMBB), E = succ_end(LLVMBB);
1244          SI != E && !ContainsFPCode; ++SI)
1245       for (BasicBlock::const_iterator II = SI->begin();
1246            (PN = dyn_cast<PHINode>(II)); ++II)
1247         if (PN->getType()->isFloatingPoint()) {
1248           ContainsFPCode = true;
1249           break;
1250         }
1251
1252
1253   // Insert FP_REG_KILL instructions into basic blocks that need them.  This
1254   // only occurs due to the floating point stackifier not being aggressive
1255   // enough to handle arbitrary global stackification.
1256   //
1257   // Currently we insert an FP_REG_KILL instruction into each block that uses or
1258   // defines a floating point virtual register.
1259   //
1260   // When the global register allocators (like linear scan) finally update live
1261   // variable analysis, we can keep floating point values in registers across
1262   // basic blocks.  This will be a huge win, but we are waiting on the global
1263   // allocators before we can do this.
1264   //
1265   if (ContainsFPCode) {
1266     BuildMI(*BB, BB->getFirstTerminator(), X86::FP_REG_KILL, 0);
1267     ++NumFPKill;
1268   }
1269
1270   // Clear state used for selection.
1271   ExprMap.clear();
1272   RegPressureMap.clear();
1273 }
1274
1275
1276 // ComputeRegPressure - Compute the RegPressureMap, which is an approximation
1277 // for the number of registers required to compute each node.  This is basically
1278 // computing a generalized form of the Sethi-Ullman number for each node.
1279 unsigned ISel::ComputeRegPressure(SDOperand O) {
1280   SDNode *N = O.Val;
1281   unsigned &Result = RegPressureMap[N];
1282   if (Result) return Result;
1283
1284   // FIXME: Should operations like CALL (which clobber lots o regs) have a
1285   // higher fixed cost??
1286
1287   if (N->getNumOperands() == 0) {
1288     Result = 1;
1289   } else {
1290     unsigned MaxRegUse = 0;
1291     unsigned NumExtraMaxRegUsers = 0;
1292     for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
1293       unsigned Regs;
1294       if (N->getOperand(i).getOpcode() == ISD::Constant)
1295         Regs = 0;
1296       else
1297         Regs = ComputeRegPressure(N->getOperand(i));
1298       if (Regs > MaxRegUse) {
1299         MaxRegUse = Regs;
1300         NumExtraMaxRegUsers = 0;
1301       } else if (Regs == MaxRegUse &&
1302                  N->getOperand(i).getValueType() != MVT::Other) {
1303         ++NumExtraMaxRegUsers;
1304       }
1305     }
1306
1307     if (O.getOpcode() != ISD::TokenFactor)
1308       Result = MaxRegUse+NumExtraMaxRegUsers;
1309     else
1310       Result = MaxRegUse == 1 ? 0 : MaxRegUse-1;
1311   }
1312
1313   //std::cerr << " WEIGHT: " << Result << " ";  N->dump(); std::cerr << "\n";
1314   return Result;
1315 }
1316
1317 /// NodeTransitivelyUsesValue - Return true if N or any of its uses uses Op.
1318 /// The DAG cannot have cycles in it, by definition, so the visited set is not
1319 /// needed to prevent infinite loops.  The DAG CAN, however, have unbounded
1320 /// reuse, so it prevents exponential cases.
1321 ///
1322 static bool NodeTransitivelyUsesValue(SDOperand N, SDOperand Op,
1323                                       std::set<SDNode*> &Visited) {
1324   if (N == Op) return true;                        // Found it.
1325   SDNode *Node = N.Val;
1326   if (Node->getNumOperands() == 0 ||      // Leaf?
1327       Node->getNodeDepth() <= Op.getNodeDepth()) return false; // Can't find it?
1328   if (!Visited.insert(Node).second) return false;  // Already visited?
1329
1330   // Recurse for the first N-1 operands.
1331   for (unsigned i = 1, e = Node->getNumOperands(); i != e; ++i)
1332     if (NodeTransitivelyUsesValue(Node->getOperand(i), Op, Visited))
1333       return true;
1334
1335   // Tail recurse for the last operand.
1336   return NodeTransitivelyUsesValue(Node->getOperand(0), Op, Visited);
1337 }
1338
1339 X86AddressMode ISel::SelectAddrExprs(const X86ISelAddressMode &IAM) {
1340   X86AddressMode Result;
1341
1342   // If we need to emit two register operands, emit the one with the highest
1343   // register pressure first.
1344   if (IAM.BaseType == X86ISelAddressMode::RegBase &&
1345       IAM.Base.Reg.Val && IAM.IndexReg.Val) {
1346     bool EmitBaseThenIndex;
1347     if (getRegPressure(IAM.Base.Reg) > getRegPressure(IAM.IndexReg)) {
1348       std::set<SDNode*> Visited;
1349       EmitBaseThenIndex = true;
1350       // If Base ends up pointing to Index, we must emit index first.  This is
1351       // because of the way we fold loads, we may end up doing bad things with
1352       // the folded add.
1353       if (NodeTransitivelyUsesValue(IAM.Base.Reg, IAM.IndexReg, Visited))
1354         EmitBaseThenIndex = false;
1355     } else {
1356       std::set<SDNode*> Visited;
1357       EmitBaseThenIndex = false;
1358       // If Base ends up pointing to Index, we must emit index first.  This is
1359       // because of the way we fold loads, we may end up doing bad things with
1360       // the folded add.
1361       if (NodeTransitivelyUsesValue(IAM.IndexReg, IAM.Base.Reg, Visited))
1362         EmitBaseThenIndex = true;
1363     }
1364
1365     if (EmitBaseThenIndex) {
1366       Result.Base.Reg = SelectExpr(IAM.Base.Reg);
1367       Result.IndexReg = SelectExpr(IAM.IndexReg);
1368     } else {
1369       Result.IndexReg = SelectExpr(IAM.IndexReg);
1370       Result.Base.Reg = SelectExpr(IAM.Base.Reg);
1371     }
1372
1373   } else if (IAM.BaseType == X86ISelAddressMode::RegBase && IAM.Base.Reg.Val) {
1374     Result.Base.Reg = SelectExpr(IAM.Base.Reg);
1375   } else if (IAM.IndexReg.Val) {
1376     Result.IndexReg = SelectExpr(IAM.IndexReg);
1377   }
1378
1379   switch (IAM.BaseType) {
1380   case X86ISelAddressMode::RegBase:
1381     Result.BaseType = X86AddressMode::RegBase;
1382     break;
1383   case X86ISelAddressMode::FrameIndexBase:
1384     Result.BaseType = X86AddressMode::FrameIndexBase;
1385     Result.Base.FrameIndex = IAM.Base.FrameIndex;
1386     break;
1387   default:
1388     assert(0 && "Unknown base type!");
1389     break;
1390   }
1391   Result.Scale = IAM.Scale;
1392   Result.Disp = IAM.Disp;
1393   Result.GV = IAM.GV;
1394   return Result;
1395 }
1396
1397 /// SelectAddress - Pattern match the maximal addressing mode for this node and
1398 /// emit all of the leaf registers.
1399 void ISel::SelectAddress(SDOperand N, X86AddressMode &AM) {
1400   X86ISelAddressMode IAM;
1401   MatchAddress(N, IAM);
1402   AM = SelectAddrExprs(IAM);
1403 }
1404
1405 /// MatchAddress - Add the specified node to the specified addressing mode,
1406 /// returning true if it cannot be done.  This just pattern matches for the
1407 /// addressing mode, it does not cause any code to be emitted.  For that, use
1408 /// SelectAddress.
1409 bool ISel::MatchAddress(SDOperand N, X86ISelAddressMode &AM) {
1410   switch (N.getOpcode()) {
1411   default: break;
1412   case ISD::FrameIndex:
1413     if (AM.BaseType == X86ISelAddressMode::RegBase && AM.Base.Reg.Val == 0) {
1414       AM.BaseType = X86ISelAddressMode::FrameIndexBase;
1415       AM.Base.FrameIndex = cast<FrameIndexSDNode>(N)->getIndex();
1416       return false;
1417     }
1418     break;
1419   case ISD::GlobalAddress:
1420     if (AM.GV == 0) {
1421       GlobalValue *GV = cast<GlobalAddressSDNode>(N)->getGlobal();
1422       // For Darwin, external and weak symbols are indirect, so we want to load
1423       // the value at address GV, not the value of GV itself.  This means that
1424       // the GlobalAddress must be in the base or index register of the address,
1425       // not the GV offset field.
1426       if (Subtarget->getIndirectExternAndWeakGlobals() &&
1427           (GV->hasWeakLinkage() || GV->isExternal())) {
1428         break;
1429       } else {
1430         AM.GV = GV;
1431         return false;
1432       }
1433     }
1434     break;
1435   case ISD::Constant:
1436     AM.Disp += cast<ConstantSDNode>(N)->getValue();
1437     return false;
1438   case ISD::SHL:
1439     // We might have folded the load into this shift, so don't regen the value
1440     // if so.
1441     if (ExprMap.count(N)) break;
1442
1443     if (AM.IndexReg.Val == 0 && AM.Scale == 1)
1444       if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.Val->getOperand(1))) {
1445         unsigned Val = CN->getValue();
1446         if (Val == 1 || Val == 2 || Val == 3) {
1447           AM.Scale = 1 << Val;
1448           SDOperand ShVal = N.Val->getOperand(0);
1449
1450           // Okay, we know that we have a scale by now.  However, if the scaled
1451           // value is an add of something and a constant, we can fold the
1452           // constant into the disp field here.
1453           if (ShVal.Val->getOpcode() == ISD::ADD && ShVal.hasOneUse() &&
1454               isa<ConstantSDNode>(ShVal.Val->getOperand(1))) {
1455             AM.IndexReg = ShVal.Val->getOperand(0);
1456             ConstantSDNode *AddVal =
1457               cast<ConstantSDNode>(ShVal.Val->getOperand(1));
1458             AM.Disp += AddVal->getValue() << Val;
1459           } else {
1460             AM.IndexReg = ShVal;
1461           }
1462           return false;
1463         }
1464       }
1465     break;
1466   case ISD::MUL:
1467     // We might have folded the load into this mul, so don't regen the value if
1468     // so.
1469     if (ExprMap.count(N)) break;
1470
1471     // X*[3,5,9] -> X+X*[2,4,8]
1472     if (AM.IndexReg.Val == 0 && AM.BaseType == X86ISelAddressMode::RegBase &&
1473         AM.Base.Reg.Val == 0)
1474       if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.Val->getOperand(1)))
1475         if (CN->getValue() == 3 || CN->getValue() == 5 || CN->getValue() == 9) {
1476           AM.Scale = unsigned(CN->getValue())-1;
1477
1478           SDOperand MulVal = N.Val->getOperand(0);
1479           SDOperand Reg;
1480
1481           // Okay, we know that we have a scale by now.  However, if the scaled
1482           // value is an add of something and a constant, we can fold the
1483           // constant into the disp field here.
1484           if (MulVal.Val->getOpcode() == ISD::ADD && MulVal.hasOneUse() &&
1485               isa<ConstantSDNode>(MulVal.Val->getOperand(1))) {
1486             Reg = MulVal.Val->getOperand(0);
1487             ConstantSDNode *AddVal =
1488               cast<ConstantSDNode>(MulVal.Val->getOperand(1));
1489             AM.Disp += AddVal->getValue() * CN->getValue();
1490           } else {
1491             Reg = N.Val->getOperand(0);
1492           }
1493
1494           AM.IndexReg = AM.Base.Reg = Reg;
1495           return false;
1496         }
1497     break;
1498
1499   case ISD::ADD: {
1500     // We might have folded the load into this mul, so don't regen the value if
1501     // so.
1502     if (ExprMap.count(N)) break;
1503
1504     X86ISelAddressMode Backup = AM;
1505     if (!MatchAddress(N.Val->getOperand(0), AM) &&
1506         !MatchAddress(N.Val->getOperand(1), AM))
1507       return false;
1508     AM = Backup;
1509     if (!MatchAddress(N.Val->getOperand(1), AM) &&
1510         !MatchAddress(N.Val->getOperand(0), AM))
1511       return false;
1512     AM = Backup;
1513     break;
1514   }
1515   }
1516
1517   // Is the base register already occupied?
1518   if (AM.BaseType != X86ISelAddressMode::RegBase || AM.Base.Reg.Val) {
1519     // If so, check to see if the scale index register is set.
1520     if (AM.IndexReg.Val == 0) {
1521       AM.IndexReg = N;
1522       AM.Scale = 1;
1523       return false;
1524     }
1525
1526     // Otherwise, we cannot select it.
1527     return true;
1528   }
1529
1530   // Default, generate it as a register.
1531   AM.BaseType = X86ISelAddressMode::RegBase;
1532   AM.Base.Reg = N;
1533   return false;
1534 }
1535
1536 /// Emit2SetCCsAndLogical - Emit the following sequence of instructions,
1537 /// assuming that the temporary registers are in the 8-bit register class.
1538 ///
1539 ///  Tmp1 = setcc1
1540 ///  Tmp2 = setcc2
1541 ///  DestReg = logicalop Tmp1, Tmp2
1542 ///
1543 static void Emit2SetCCsAndLogical(MachineBasicBlock *BB, unsigned SetCC1,
1544                                   unsigned SetCC2, unsigned LogicalOp,
1545                                   unsigned DestReg) {
1546   SSARegMap *RegMap = BB->getParent()->getSSARegMap();
1547   unsigned Tmp1 = RegMap->createVirtualRegister(X86::R8RegisterClass);
1548   unsigned Tmp2 = RegMap->createVirtualRegister(X86::R8RegisterClass);
1549   BuildMI(BB, SetCC1, 0, Tmp1);
1550   BuildMI(BB, SetCC2, 0, Tmp2);
1551   BuildMI(BB, LogicalOp, 2, DestReg).addReg(Tmp1).addReg(Tmp2);
1552 }
1553
1554 /// EmitSetCC - Emit the code to set the specified 8-bit register to 1 if the
1555 /// condition codes match the specified SetCCOpcode.  Note that some conditions
1556 /// require multiple instructions to generate the correct value.
1557 static void EmitSetCC(MachineBasicBlock *BB, unsigned DestReg,
1558                       ISD::CondCode SetCCOpcode, bool isFP) {
1559   unsigned Opc;
1560   if (!isFP) {
1561     switch (SetCCOpcode) {
1562     default: assert(0 && "Illegal integer SetCC!");
1563     case ISD::SETEQ: Opc = X86::SETEr; break;
1564     case ISD::SETGT: Opc = X86::SETGr; break;
1565     case ISD::SETGE: Opc = X86::SETGEr; break;
1566     case ISD::SETLT: Opc = X86::SETLr; break;
1567     case ISD::SETLE: Opc = X86::SETLEr; break;
1568     case ISD::SETNE: Opc = X86::SETNEr; break;
1569     case ISD::SETULT: Opc = X86::SETBr; break;
1570     case ISD::SETUGT: Opc = X86::SETAr; break;
1571     case ISD::SETULE: Opc = X86::SETBEr; break;
1572     case ISD::SETUGE: Opc = X86::SETAEr; break;
1573     }
1574   } else {
1575     // On a floating point condition, the flags are set as follows:
1576     // ZF  PF  CF   op
1577     //  0 | 0 | 0 | X > Y
1578     //  0 | 0 | 1 | X < Y
1579     //  1 | 0 | 0 | X == Y
1580     //  1 | 1 | 1 | unordered
1581     //
1582     switch (SetCCOpcode) {
1583     default: assert(0 && "Invalid FP setcc!");
1584     case ISD::SETUEQ:
1585     case ISD::SETEQ:
1586       Opc = X86::SETEr;    // True if ZF = 1
1587       break;
1588     case ISD::SETOGT:
1589     case ISD::SETGT:
1590       Opc = X86::SETAr;    // True if CF = 0 and ZF = 0
1591       break;
1592     case ISD::SETOGE:
1593     case ISD::SETGE:
1594       Opc = X86::SETAEr;   // True if CF = 0
1595       break;
1596     case ISD::SETULT:
1597     case ISD::SETLT:
1598       Opc = X86::SETBr;    // True if CF = 1
1599       break;
1600     case ISD::SETULE:
1601     case ISD::SETLE:
1602       Opc = X86::SETBEr;   // True if CF = 1 or ZF = 1
1603       break;
1604     case ISD::SETONE:
1605     case ISD::SETNE:
1606       Opc = X86::SETNEr;   // True if ZF = 0
1607       break;
1608     case ISD::SETUO:
1609       Opc = X86::SETPr;    // True if PF = 1
1610       break;
1611     case ISD::SETO:
1612       Opc = X86::SETNPr;   // True if PF = 0
1613       break;
1614     case ISD::SETOEQ:      // !PF & ZF
1615       Emit2SetCCsAndLogical(BB, X86::SETNPr, X86::SETEr, X86::AND8rr, DestReg);
1616       return;
1617     case ISD::SETOLT:      // !PF & CF
1618       Emit2SetCCsAndLogical(BB, X86::SETNPr, X86::SETBr, X86::AND8rr, DestReg);
1619       return;
1620     case ISD::SETOLE:      // !PF & (CF || ZF)
1621       Emit2SetCCsAndLogical(BB, X86::SETNPr, X86::SETBEr, X86::AND8rr, DestReg);
1622       return;
1623     case ISD::SETUGT:      // PF | (!ZF & !CF)
1624       Emit2SetCCsAndLogical(BB, X86::SETPr, X86::SETAr, X86::OR8rr, DestReg);
1625       return;
1626     case ISD::SETUGE:      // PF | !CF
1627       Emit2SetCCsAndLogical(BB, X86::SETPr, X86::SETAEr, X86::OR8rr, DestReg);
1628       return;
1629     case ISD::SETUNE:      // PF | !ZF
1630       Emit2SetCCsAndLogical(BB, X86::SETPr, X86::SETNEr, X86::OR8rr, DestReg);
1631       return;
1632     }
1633   }
1634   BuildMI(BB, Opc, 0, DestReg);
1635 }
1636
1637
1638 /// EmitBranchCC - Emit code into BB that arranges for control to transfer to
1639 /// the Dest block if the Cond condition is true.  If we cannot fold this
1640 /// condition into the branch, return true.
1641 ///
1642 bool ISel::EmitBranchCC(MachineBasicBlock *Dest, SDOperand Chain,
1643                         SDOperand Cond) {
1644   // FIXME: Evaluate whether it would be good to emit code like (X < Y) | (A >
1645   // B) using two conditional branches instead of one condbr, two setcc's, and
1646   // an or.
1647   if ((Cond.getOpcode() == ISD::OR ||
1648        Cond.getOpcode() == ISD::AND) && Cond.Val->hasOneUse()) {
1649     // And and or set the flags for us, so there is no need to emit a TST of the
1650     // result.  It is only safe to do this if there is only a single use of the
1651     // AND/OR though, otherwise we don't know it will be emitted here.
1652     Select(Chain);
1653     SelectExpr(Cond);
1654     BuildMI(BB, X86::JNE, 1).addMBB(Dest);
1655     return false;
1656   }
1657
1658   // Codegen br not C -> JE.
1659   if (Cond.getOpcode() == ISD::XOR)
1660     if (ConstantSDNode *NC = dyn_cast<ConstantSDNode>(Cond.Val->getOperand(1)))
1661       if (NC->isAllOnesValue()) {
1662         unsigned CondR;
1663         if (getRegPressure(Chain) > getRegPressure(Cond)) {
1664           Select(Chain);
1665           CondR = SelectExpr(Cond.Val->getOperand(0));
1666         } else {
1667           CondR = SelectExpr(Cond.Val->getOperand(0));
1668           Select(Chain);
1669         }
1670         BuildMI(BB, X86::TEST8rr, 2).addReg(CondR).addReg(CondR);
1671         BuildMI(BB, X86::JE, 1).addMBB(Dest);
1672         return false;
1673       }
1674
1675   if (Cond.getOpcode() != ISD::SETCC)
1676     return true;                       // Can only handle simple setcc's so far.
1677   ISD::CondCode CC = cast<CondCodeSDNode>(Cond.getOperand(2))->get();
1678
1679   unsigned Opc;
1680
1681   // Handle integer conditions first.
1682   if (MVT::isInteger(Cond.getOperand(0).getValueType())) {
1683     switch (CC) {
1684     default: assert(0 && "Illegal integer SetCC!");
1685     case ISD::SETEQ: Opc = X86::JE; break;
1686     case ISD::SETGT: Opc = X86::JG; break;
1687     case ISD::SETGE: Opc = X86::JGE; break;
1688     case ISD::SETLT: Opc = X86::JL; break;
1689     case ISD::SETLE: Opc = X86::JLE; break;
1690     case ISD::SETNE: Opc = X86::JNE; break;
1691     case ISD::SETULT: Opc = X86::JB; break;
1692     case ISD::SETUGT: Opc = X86::JA; break;
1693     case ISD::SETULE: Opc = X86::JBE; break;
1694     case ISD::SETUGE: Opc = X86::JAE; break;
1695     }
1696     Select(Chain);
1697     EmitCMP(Cond.getOperand(0), Cond.getOperand(1), Cond.hasOneUse());
1698     BuildMI(BB, Opc, 1).addMBB(Dest);
1699     return false;
1700   }
1701
1702   unsigned Opc2 = 0;  // Second branch if needed.
1703
1704   // On a floating point condition, the flags are set as follows:
1705   // ZF  PF  CF   op
1706   //  0 | 0 | 0 | X > Y
1707   //  0 | 0 | 1 | X < Y
1708   //  1 | 0 | 0 | X == Y
1709   //  1 | 1 | 1 | unordered
1710   //
1711   switch (CC) {
1712   default: assert(0 && "Invalid FP setcc!");
1713   case ISD::SETUEQ:
1714   case ISD::SETEQ:   Opc = X86::JE;  break;     // True if ZF = 1
1715   case ISD::SETOGT:
1716   case ISD::SETGT:   Opc = X86::JA;  break;     // True if CF = 0 and ZF = 0
1717   case ISD::SETOGE:
1718   case ISD::SETGE:   Opc = X86::JAE; break;     // True if CF = 0
1719   case ISD::SETULT:
1720   case ISD::SETLT:   Opc = X86::JB;  break;     // True if CF = 1
1721   case ISD::SETULE:
1722   case ISD::SETLE:   Opc = X86::JBE; break;     // True if CF = 1 or ZF = 1
1723   case ISD::SETONE:
1724   case ISD::SETNE:   Opc = X86::JNE; break;     // True if ZF = 0
1725   case ISD::SETUO:   Opc = X86::JP;  break;     // True if PF = 1
1726   case ISD::SETO:    Opc = X86::JNP; break;     // True if PF = 0
1727   case ISD::SETUGT:      // PF = 1 | (ZF = 0 & CF = 0)
1728     Opc = X86::JA;       // ZF = 0 & CF = 0
1729     Opc2 = X86::JP;      // PF = 1
1730     break;
1731   case ISD::SETUGE:      // PF = 1 | CF = 0
1732     Opc = X86::JAE;      // CF = 0
1733     Opc2 = X86::JP;      // PF = 1
1734     break;
1735   case ISD::SETUNE:      // PF = 1 | ZF = 0
1736     Opc = X86::JNE;      // ZF = 0
1737     Opc2 = X86::JP;      // PF = 1
1738     break;
1739   case ISD::SETOEQ:      // PF = 0 & ZF = 1
1740     //X86::JNP, X86::JE
1741     //X86::AND8rr
1742     return true;    // FIXME: Emit more efficient code for this branch.
1743   case ISD::SETOLT:      // PF = 0 & CF = 1
1744     //X86::JNP, X86::JB
1745     //X86::AND8rr
1746     return true;    // FIXME: Emit more efficient code for this branch.
1747   case ISD::SETOLE:      // PF = 0 & (CF = 1 || ZF = 1)
1748     //X86::JNP, X86::JBE
1749     //X86::AND8rr
1750     return true;    // FIXME: Emit more efficient code for this branch.
1751   }
1752
1753   Select(Chain);
1754   EmitCMP(Cond.getOperand(0), Cond.getOperand(1), Cond.hasOneUse());
1755   BuildMI(BB, Opc, 1).addMBB(Dest);
1756   if (Opc2)
1757     BuildMI(BB, Opc2, 1).addMBB(Dest);
1758   return false;
1759 }
1760
1761 /// EmitSelectCC - Emit code into BB that performs a select operation between
1762 /// the two registers RTrue and RFalse, generating a result into RDest.
1763 ///
1764 void ISel::EmitSelectCC(SDOperand Cond, SDOperand True, SDOperand False,
1765                         MVT::ValueType SVT, unsigned RDest) {
1766   unsigned RTrue, RFalse;
1767   enum Condition {
1768     EQ, NE, LT, LE, GT, GE, B, BE, A, AE, P, NP,
1769     NOT_SET
1770   } CondCode = NOT_SET;
1771
1772   static const unsigned CMOVTAB16[] = {
1773     X86::CMOVE16rr,  X86::CMOVNE16rr, X86::CMOVL16rr,  X86::CMOVLE16rr,
1774     X86::CMOVG16rr,  X86::CMOVGE16rr, X86::CMOVB16rr,  X86::CMOVBE16rr,
1775     X86::CMOVA16rr,  X86::CMOVAE16rr, X86::CMOVP16rr,  X86::CMOVNP16rr,
1776   };
1777   static const unsigned CMOVTAB32[] = {
1778     X86::CMOVE32rr,  X86::CMOVNE32rr, X86::CMOVL32rr,  X86::CMOVLE32rr,
1779     X86::CMOVG32rr,  X86::CMOVGE32rr, X86::CMOVB32rr,  X86::CMOVBE32rr,
1780     X86::CMOVA32rr,  X86::CMOVAE32rr, X86::CMOVP32rr,  X86::CMOVNP32rr,
1781   };
1782   static const unsigned CMOVTABFP[] = {
1783     X86::FCMOVE ,  X86::FCMOVNE, /*missing*/0, /*missing*/0,
1784     /*missing*/0,  /*missing*/0, X86::FCMOVB , X86::FCMOVBE,
1785     X86::FCMOVA ,  X86::FCMOVAE, X86::FCMOVP , X86::FCMOVNP
1786   };
1787   static const int SSE_CMOVTAB[] = {
1788     /*CMPEQ*/   0, /*CMPNEQ*/   4, /*missing*/  0, /*missing*/  0,
1789     /*missing*/ 0, /*missing*/  0, /*CMPLT*/    1, /*CMPLE*/    2,
1790     /*CMPNLE*/  6, /*CMPNLT*/   5, /*CMPUNORD*/ 3, /*CMPORD*/   7
1791   };
1792
1793   if (Cond.getOpcode() == ISD::SETCC) {
1794     ISD::CondCode CC = cast<CondCodeSDNode>(Cond.getOperand(2))->get();
1795     if (MVT::isInteger(Cond.getOperand(0).getValueType())) {
1796       switch (CC) {
1797       default: assert(0 && "Unknown integer comparison!");
1798       case ISD::SETEQ:  CondCode = EQ; break;
1799       case ISD::SETGT:  CondCode = GT; break;
1800       case ISD::SETGE:  CondCode = GE; break;
1801       case ISD::SETLT:  CondCode = LT; break;
1802       case ISD::SETLE:  CondCode = LE; break;
1803       case ISD::SETNE:  CondCode = NE; break;
1804       case ISD::SETULT: CondCode = B; break;
1805       case ISD::SETUGT: CondCode = A; break;
1806       case ISD::SETULE: CondCode = BE; break;
1807       case ISD::SETUGE: CondCode = AE; break;
1808       }
1809     } else {
1810       // On a floating point condition, the flags are set as follows:
1811       // ZF  PF  CF   op
1812       //  0 | 0 | 0 | X > Y
1813       //  0 | 0 | 1 | X < Y
1814       //  1 | 0 | 0 | X == Y
1815       //  1 | 1 | 1 | unordered
1816       //
1817       switch (CC) {
1818       default: assert(0 && "Unknown FP comparison!");
1819       case ISD::SETUEQ:
1820       case ISD::SETEQ:  CondCode = EQ; break;     // True if ZF = 1
1821       case ISD::SETOGT:
1822       case ISD::SETGT:  CondCode = A;  break;     // True if CF = 0 and ZF = 0
1823       case ISD::SETOGE:
1824       case ISD::SETGE:  CondCode = AE; break;     // True if CF = 0
1825       case ISD::SETULT:
1826       case ISD::SETLT:  CondCode = B;  break;     // True if CF = 1
1827       case ISD::SETULE:
1828       case ISD::SETLE:  CondCode = BE; break;     // True if CF = 1 or ZF = 1
1829       case ISD::SETONE:
1830       case ISD::SETNE:  CondCode = NE; break;     // True if ZF = 0
1831       case ISD::SETUO:  CondCode = P;  break;     // True if PF = 1
1832       case ISD::SETO:   CondCode = NP; break;     // True if PF = 0
1833       case ISD::SETUGT:      // PF = 1 | (ZF = 0 & CF = 0)
1834       case ISD::SETUGE:      // PF = 1 | CF = 0
1835       case ISD::SETUNE:      // PF = 1 | ZF = 0
1836       case ISD::SETOEQ:      // PF = 0 & ZF = 1
1837       case ISD::SETOLT:      // PF = 0 & CF = 1
1838       case ISD::SETOLE:      // PF = 0 & (CF = 1 || ZF = 1)
1839         // We cannot emit this comparison as a single cmov.
1840         break;
1841       }
1842     }
1843
1844
1845     // There's no SSE equivalent of FCMOVE.  For cases where we set a condition
1846     // code above and one of the results of the select is +0.0, then we can fake
1847     // it up through a clever AND with mask.  Otherwise, we will fall through to
1848     // the code below that will use a PHI node to select the right value.
1849     if (X86ScalarSSE && (SVT == MVT::f32 || SVT == MVT::f64)) {
1850       if (Cond.getOperand(0).getValueType() == SVT &&
1851           NOT_SET != CondCode) {
1852         ConstantFPSDNode *CT = dyn_cast<ConstantFPSDNode>(True);
1853         ConstantFPSDNode *CF = dyn_cast<ConstantFPSDNode>(False);
1854         bool TrueZero = CT && CT->isExactlyValue(0.0);
1855         bool FalseZero = CF && CF->isExactlyValue(0.0);
1856         if (TrueZero || FalseZero) {
1857           SDOperand LHS = Cond.getOperand(0);
1858           SDOperand RHS = Cond.getOperand(1);
1859
1860           // Select the two halves of the condition
1861           unsigned RLHS, RRHS;
1862           if (getRegPressure(LHS) > getRegPressure(RHS)) {
1863             RLHS = SelectExpr(LHS);
1864             RRHS = SelectExpr(RHS);
1865           } else {
1866             RRHS = SelectExpr(RHS);
1867             RLHS = SelectExpr(LHS);
1868           }
1869
1870           // Emit the comparison and generate a mask from it
1871           unsigned MaskReg = MakeReg(SVT);
1872           unsigned Opc = (SVT == MVT::f32) ? X86::CMPSSrr : X86::CMPSDrr;
1873           BuildMI(BB, Opc, 3, MaskReg).addReg(RLHS).addReg(RRHS)
1874             .addImm(SSE_CMOVTAB[CondCode]);
1875
1876           if (TrueZero) {
1877             RFalse = SelectExpr(False);
1878             Opc = (SVT == MVT::f32) ? X86::ANDNPSrr : X86::ANDNPDrr;
1879             BuildMI(BB, Opc, 2, RDest).addReg(MaskReg).addReg(RFalse);
1880           } else {
1881             RTrue = SelectExpr(True);
1882             Opc = (SVT == MVT::f32) ? X86::ANDPSrr : X86::ANDPDrr;
1883             BuildMI(BB, Opc, 2, RDest).addReg(MaskReg).addReg(RTrue);
1884           }
1885           return;
1886         }
1887       }
1888     }
1889   }
1890
1891   // Select the true and false values for use in both the SSE PHI case, and the
1892   // integer or x87 cmov cases below.
1893   if (getRegPressure(True) > getRegPressure(False)) {
1894     RTrue = SelectExpr(True);
1895     RFalse = SelectExpr(False);
1896   } else {
1897     RFalse = SelectExpr(False);
1898     RTrue = SelectExpr(True);
1899   }
1900
1901   // Since there's no SSE equivalent of FCMOVE, and we couldn't generate an
1902   // AND with mask, we'll have to do the normal RISC thing and generate a PHI
1903   // node to select between the true and false values.
1904   if (X86ScalarSSE && (SVT == MVT::f32 || SVT == MVT::f64)) {
1905     // FIXME: emit a direct compare and branch rather than setting a cond reg
1906     //        and testing it.
1907     unsigned CondReg = SelectExpr(Cond);
1908     BuildMI(BB, X86::TEST8rr, 2).addReg(CondReg).addReg(CondReg);
1909
1910     // Create an iterator with which to insert the MBB for copying the false
1911     // value and the MBB to hold the PHI instruction for this SetCC.
1912     MachineBasicBlock *thisMBB = BB;
1913     const BasicBlock *LLVM_BB = BB->getBasicBlock();
1914     ilist<MachineBasicBlock>::iterator It = BB;
1915     ++It;
1916
1917     //  thisMBB:
1918     //  ...
1919     //   TrueVal = ...
1920     //   cmpTY ccX, r1, r2
1921     //   bCC sinkMBB
1922     //   fallthrough --> copy0MBB
1923     MachineBasicBlock *copy0MBB = new MachineBasicBlock(LLVM_BB);
1924     MachineBasicBlock *sinkMBB = new MachineBasicBlock(LLVM_BB);
1925     BuildMI(BB, X86::JNE, 1).addMBB(sinkMBB);
1926     MachineFunction *F = BB->getParent();
1927     F->getBasicBlockList().insert(It, copy0MBB);
1928     F->getBasicBlockList().insert(It, sinkMBB);
1929     // Update machine-CFG edges
1930     BB->addSuccessor(copy0MBB);
1931     BB->addSuccessor(sinkMBB);
1932
1933     //  copy0MBB:
1934     //   %FalseValue = ...
1935     //   # fallthrough to sinkMBB
1936     BB = copy0MBB;
1937     // Update machine-CFG edges
1938     BB->addSuccessor(sinkMBB);
1939
1940     //  sinkMBB:
1941     //   %Result = phi [ %FalseValue, copy0MBB ], [ %TrueValue, thisMBB ]
1942     //  ...
1943     BB = sinkMBB;
1944     BuildMI(BB, X86::PHI, 4, RDest).addReg(RFalse)
1945       .addMBB(copy0MBB).addReg(RTrue).addMBB(thisMBB);
1946     return;
1947   }
1948
1949   unsigned Opc = 0;
1950   if (CondCode != NOT_SET) {
1951     switch (SVT) {
1952     default: assert(0 && "Cannot select this type!");
1953     case MVT::i16: Opc = CMOVTAB16[CondCode]; break;
1954     case MVT::i32: Opc = CMOVTAB32[CondCode]; break;
1955     case MVT::f64: Opc = CMOVTABFP[CondCode]; break;
1956     }
1957   }
1958
1959   // Finally, if we weren't able to fold this, just emit the condition and test
1960   // it.
1961   if (CondCode == NOT_SET || Opc == 0) {
1962     // Get the condition into the zero flag.
1963     unsigned CondReg = SelectExpr(Cond);
1964     BuildMI(BB, X86::TEST8rr, 2).addReg(CondReg).addReg(CondReg);
1965
1966     switch (SVT) {
1967     default: assert(0 && "Cannot select this type!");
1968     case MVT::i16: Opc = X86::CMOVE16rr; break;
1969     case MVT::i32: Opc = X86::CMOVE32rr; break;
1970     case MVT::f64: Opc = X86::FCMOVE; break;
1971     }
1972   } else {
1973     // FIXME: CMP R, 0 -> TEST R, R
1974     EmitCMP(Cond.getOperand(0), Cond.getOperand(1), Cond.Val->hasOneUse());
1975     std::swap(RTrue, RFalse);
1976   }
1977   BuildMI(BB, Opc, 2, RDest).addReg(RTrue).addReg(RFalse);
1978 }
1979
1980 void ISel::EmitCMP(SDOperand LHS, SDOperand RHS, bool HasOneUse) {
1981   unsigned Opc;
1982   if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(RHS)) {
1983     Opc = 0;
1984     if (HasOneUse && isFoldableLoad(LHS, RHS)) {
1985       switch (RHS.getValueType()) {
1986       default: break;
1987       case MVT::i1:
1988       case MVT::i8:  Opc = X86::CMP8mi;  break;
1989       case MVT::i16: Opc = X86::CMP16mi; break;
1990       case MVT::i32: Opc = X86::CMP32mi; break;
1991       }
1992       if (Opc) {
1993         X86AddressMode AM;
1994         EmitFoldedLoad(LHS, AM);
1995         addFullAddress(BuildMI(BB, Opc, 5), AM).addImm(CN->getValue());
1996         return;
1997       }
1998     }
1999
2000     switch (RHS.getValueType()) {
2001     default: break;
2002     case MVT::i1:
2003     case MVT::i8:  Opc = X86::CMP8ri;  break;
2004     case MVT::i16: Opc = X86::CMP16ri; break;
2005     case MVT::i32: Opc = X86::CMP32ri; break;
2006     }
2007     if (Opc) {
2008       unsigned Tmp1 = SelectExpr(LHS);
2009       BuildMI(BB, Opc, 2).addReg(Tmp1).addImm(CN->getValue());
2010       return;
2011     }
2012   } else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(RHS)) {
2013     if (!X86ScalarSSE && (CN->isExactlyValue(+0.0) ||
2014                           CN->isExactlyValue(-0.0))) {
2015       unsigned Reg = SelectExpr(LHS);
2016       BuildMI(BB, X86::FTST, 1).addReg(Reg);
2017       BuildMI(BB, X86::FNSTSW8r, 0);
2018       BuildMI(BB, X86::SAHF, 1);
2019       return;
2020     }
2021   }
2022
2023   Opc = 0;
2024   if (HasOneUse && isFoldableLoad(LHS, RHS)) {
2025     switch (RHS.getValueType()) {
2026     default: break;
2027     case MVT::i1:
2028     case MVT::i8:  Opc = X86::CMP8mr;  break;
2029     case MVT::i16: Opc = X86::CMP16mr; break;
2030     case MVT::i32: Opc = X86::CMP32mr; break;
2031     }
2032     if (Opc) {
2033       X86AddressMode AM;
2034       EmitFoldedLoad(LHS, AM);
2035       unsigned Reg = SelectExpr(RHS);
2036       addFullAddress(BuildMI(BB, Opc, 5), AM).addReg(Reg);
2037       return;
2038     }
2039   }
2040
2041   switch (LHS.getValueType()) {
2042   default: assert(0 && "Cannot compare this value!");
2043   case MVT::i1:
2044   case MVT::i8:  Opc = X86::CMP8rr;  break;
2045   case MVT::i16: Opc = X86::CMP16rr; break;
2046   case MVT::i32: Opc = X86::CMP32rr; break;
2047   case MVT::f32: Opc = X86::UCOMISSrr; break;
2048   case MVT::f64: Opc = X86ScalarSSE ? X86::UCOMISDrr : X86::FUCOMIr; break;
2049   }
2050   unsigned Tmp1, Tmp2;
2051   if (getRegPressure(LHS) > getRegPressure(RHS)) {
2052     Tmp1 = SelectExpr(LHS);
2053     Tmp2 = SelectExpr(RHS);
2054   } else {
2055     Tmp2 = SelectExpr(RHS);
2056     Tmp1 = SelectExpr(LHS);
2057   }
2058   BuildMI(BB, Opc, 2).addReg(Tmp1).addReg(Tmp2);
2059 }
2060
2061 /// isFoldableLoad - Return true if this is a load instruction that can safely
2062 /// be folded into an operation that uses it.
2063 bool ISel::isFoldableLoad(SDOperand Op, SDOperand OtherOp, bool FloatPromoteOk){
2064   if (Op.getOpcode() == ISD::LOAD) {
2065     // FIXME: currently can't fold constant pool indexes.
2066     if (isa<ConstantPoolSDNode>(Op.getOperand(1)))
2067       return false;
2068   } else if (FloatPromoteOk && Op.getOpcode() == ISD::EXTLOAD &&
2069              cast<VTSDNode>(Op.getOperand(3))->getVT() == MVT::f32) {
2070     // FIXME: currently can't fold constant pool indexes.
2071     if (isa<ConstantPoolSDNode>(Op.getOperand(1)))
2072       return false;
2073   } else {
2074     return false;
2075   }
2076
2077   // If this load has already been emitted, we clearly can't fold it.
2078   assert(Op.ResNo == 0 && "Not a use of the value of the load?");
2079   if (ExprMap.count(Op.getValue(1))) return false;
2080   assert(!ExprMap.count(Op.getValue(0)) && "Value in map but not token chain?");
2081   assert(!ExprMap.count(Op.getValue(1))&&"Token lowered but value not in map?");
2082
2083   // If there is not just one use of its value, we cannot fold.
2084   if (!Op.Val->hasNUsesOfValue(1, 0)) return false;
2085
2086   // Finally, we cannot fold the load into the operation if this would induce a
2087   // cycle into the resultant dag.  To check for this, see if OtherOp (the other
2088   // operand of the operation we are folding the load into) can possible use the
2089   // chain node defined by the load.
2090   if (OtherOp.Val && !Op.Val->hasNUsesOfValue(0, 1)) { // Has uses of chain?
2091     std::set<SDNode*> Visited;
2092     if (NodeTransitivelyUsesValue(OtherOp, Op.getValue(1), Visited))
2093       return false;
2094   }
2095   return true;
2096 }
2097
2098
2099 /// EmitFoldedLoad - Ensure that the arguments of the load are code generated,
2100 /// and compute the address being loaded into AM.
2101 void ISel::EmitFoldedLoad(SDOperand Op, X86AddressMode &AM) {
2102   SDOperand Chain   = Op.getOperand(0);
2103   SDOperand Address = Op.getOperand(1);
2104
2105   if (getRegPressure(Chain) > getRegPressure(Address)) {
2106     Select(Chain);
2107     SelectAddress(Address, AM);
2108   } else {
2109     SelectAddress(Address, AM);
2110     Select(Chain);
2111   }
2112
2113   // The chain for this load is now lowered.
2114   assert(ExprMap.count(SDOperand(Op.Val, 1)) == 0 &&
2115          "Load emitted more than once?");
2116   if (!ExprMap.insert(std::make_pair(Op.getValue(1), 1)).second)
2117     assert(0 && "Load emitted more than once!");
2118 }
2119
2120 // EmitOrOpOp - Pattern match the expression (Op1|Op2), where we know that op1
2121 // and op2 are i8/i16/i32 values with one use each (the or).  If we can form a
2122 // SHLD or SHRD, emit the instruction (generating the value into DestReg) and
2123 // return true.
2124 bool ISel::EmitOrOpOp(SDOperand Op1, SDOperand Op2, unsigned DestReg) {
2125   if (Op1.getOpcode() == ISD::SHL && Op2.getOpcode() == ISD::SRL) {
2126     // good!
2127   } else if (Op2.getOpcode() == ISD::SHL && Op1.getOpcode() == ISD::SRL) {
2128     std::swap(Op1, Op2);  // Op1 is the SHL now.
2129   } else {
2130     return false;  // No match
2131   }
2132
2133   SDOperand ShlVal = Op1.getOperand(0);
2134   SDOperand ShlAmt = Op1.getOperand(1);
2135   SDOperand ShrVal = Op2.getOperand(0);
2136   SDOperand ShrAmt = Op2.getOperand(1);
2137
2138   unsigned RegSize = MVT::getSizeInBits(Op1.getValueType());
2139
2140   // Find out if ShrAmt = 32-ShlAmt  or  ShlAmt = 32-ShrAmt.
2141   if (ShlAmt.getOpcode() == ISD::SUB && ShlAmt.getOperand(1) == ShrAmt)
2142     if (ConstantSDNode *SubCST = dyn_cast<ConstantSDNode>(ShlAmt.getOperand(0)))
2143       if (SubCST->getValue() == RegSize) {
2144         // (A >> ShrAmt) | (A << (32-ShrAmt)) ==> ROR A, ShrAmt
2145         // (A >> ShrAmt) | (B << (32-ShrAmt)) ==> SHRD A, B, ShrAmt
2146         if (ShrVal == ShlVal) {
2147           unsigned Reg, ShAmt;
2148           if (getRegPressure(ShrVal) > getRegPressure(ShrAmt)) {
2149             Reg = SelectExpr(ShrVal);
2150             ShAmt = SelectExpr(ShrAmt);
2151           } else {
2152             ShAmt = SelectExpr(ShrAmt);
2153             Reg = SelectExpr(ShrVal);
2154           }
2155           BuildMI(BB, X86::MOV8rr, 1, X86::CL).addReg(ShAmt);
2156           unsigned Opc = RegSize == 8 ? X86::ROR8rCL :
2157                         (RegSize == 16 ? X86::ROR16rCL : X86::ROR32rCL);
2158           BuildMI(BB, Opc, 1, DestReg).addReg(Reg);
2159           return true;
2160         } else if (RegSize != 8) {
2161           unsigned AReg, BReg;
2162           if (getRegPressure(ShlVal) > getRegPressure(ShrVal)) {
2163             BReg = SelectExpr(ShlVal);
2164             AReg = SelectExpr(ShrVal);
2165           } else {
2166             AReg = SelectExpr(ShrVal);
2167             BReg = SelectExpr(ShlVal);
2168           }
2169           unsigned ShAmt = SelectExpr(ShrAmt);
2170           BuildMI(BB, X86::MOV8rr, 1, X86::CL).addReg(ShAmt);
2171           unsigned Opc = RegSize == 16 ? X86::SHRD16rrCL : X86::SHRD32rrCL;
2172           BuildMI(BB, Opc, 2, DestReg).addReg(AReg).addReg(BReg);
2173           return true;
2174         }
2175       }
2176
2177   if (ShrAmt.getOpcode() == ISD::SUB && ShrAmt.getOperand(1) == ShlAmt)
2178     if (ConstantSDNode *SubCST = dyn_cast<ConstantSDNode>(ShrAmt.getOperand(0)))
2179       if (SubCST->getValue() == RegSize) {
2180         // (A << ShlAmt) | (A >> (32-ShlAmt)) ==> ROL A, ShrAmt
2181         // (A << ShlAmt) | (B >> (32-ShlAmt)) ==> SHLD A, B, ShrAmt
2182         if (ShrVal == ShlVal) {
2183           unsigned Reg, ShAmt;
2184           if (getRegPressure(ShrVal) > getRegPressure(ShlAmt)) {
2185             Reg = SelectExpr(ShrVal);
2186             ShAmt = SelectExpr(ShlAmt);
2187           } else {
2188             ShAmt = SelectExpr(ShlAmt);
2189             Reg = SelectExpr(ShrVal);
2190           }
2191           BuildMI(BB, X86::MOV8rr, 1, X86::CL).addReg(ShAmt);
2192           unsigned Opc = RegSize == 8 ? X86::ROL8rCL :
2193                         (RegSize == 16 ? X86::ROL16rCL : X86::ROL32rCL);
2194           BuildMI(BB, Opc, 1, DestReg).addReg(Reg);
2195           return true;
2196         } else if (RegSize != 8) {
2197           unsigned AReg, BReg;
2198           if (getRegPressure(ShlVal) > getRegPressure(ShrVal)) {
2199             AReg = SelectExpr(ShlVal);
2200             BReg = SelectExpr(ShrVal);
2201           } else {
2202             BReg = SelectExpr(ShrVal);
2203             AReg = SelectExpr(ShlVal);
2204           }
2205           unsigned ShAmt = SelectExpr(ShlAmt);
2206           BuildMI(BB, X86::MOV8rr, 1, X86::CL).addReg(ShAmt);
2207           unsigned Opc = RegSize == 16 ? X86::SHLD16rrCL : X86::SHLD32rrCL;
2208           BuildMI(BB, Opc, 2, DestReg).addReg(AReg).addReg(BReg);
2209           return true;
2210         }
2211       }
2212
2213   if (ConstantSDNode *ShrCst = dyn_cast<ConstantSDNode>(ShrAmt))
2214     if (ConstantSDNode *ShlCst = dyn_cast<ConstantSDNode>(ShlAmt))
2215       if (ShrCst->getValue() < RegSize && ShlCst->getValue() < RegSize)
2216         if (ShrCst->getValue() == RegSize-ShlCst->getValue()) {
2217           // (A >> 5) | (A << 27) --> ROR A, 5
2218           // (A >> 5) | (B << 27) --> SHRD A, B, 5
2219           if (ShrVal == ShlVal) {
2220             unsigned Reg = SelectExpr(ShrVal);
2221             unsigned Opc = RegSize == 8 ? X86::ROR8ri :
2222               (RegSize == 16 ? X86::ROR16ri : X86::ROR32ri);
2223             BuildMI(BB, Opc, 2, DestReg).addReg(Reg).addImm(ShrCst->getValue());
2224             return true;
2225           } else if (RegSize != 8) {
2226             unsigned AReg, BReg;
2227             if (getRegPressure(ShlVal) > getRegPressure(ShrVal)) {
2228               BReg = SelectExpr(ShlVal);
2229               AReg = SelectExpr(ShrVal);
2230             } else {
2231               AReg = SelectExpr(ShrVal);
2232               BReg = SelectExpr(ShlVal);
2233             }
2234             unsigned Opc = RegSize == 16 ? X86::SHRD16rri8 : X86::SHRD32rri8;
2235             BuildMI(BB, Opc, 3, DestReg).addReg(AReg).addReg(BReg)
2236               .addImm(ShrCst->getValue());
2237             return true;
2238           }
2239         }
2240
2241   return false;
2242 }
2243
2244 unsigned ISel::SelectExpr(SDOperand N) {
2245   unsigned Result;
2246   unsigned Tmp1, Tmp2, Tmp3;
2247   unsigned Opc = 0;
2248   SDNode *Node = N.Val;
2249   SDOperand Op0, Op1;
2250
2251   if (Node->getOpcode() == ISD::CopyFromReg) {
2252     unsigned Reg = cast<RegisterSDNode>(Node->getOperand(1))->getReg();
2253     // Just use the specified register as our input if we can.
2254     if (MRegisterInfo::isVirtualRegister(Reg) || Reg == X86::ESP)
2255       return Reg;
2256   }
2257
2258   unsigned &Reg = ExprMap[N];
2259   if (Reg) return Reg;
2260
2261   switch (N.getOpcode()) {
2262   default:
2263     Reg = Result = (N.getValueType() != MVT::Other) ?
2264                             MakeReg(N.getValueType()) : 1;
2265     break;
2266   case X86ISD::TAILCALL:
2267   case X86ISD::CALL:
2268     // If this is a call instruction, make sure to prepare ALL of the result
2269     // values as well as the chain.
2270     ExprMap[N.getValue(0)] = 1;
2271     if (Node->getNumValues() > 1) {
2272       Result = MakeReg(Node->getValueType(1));
2273       ExprMap[N.getValue(1)] = Result;
2274       for (unsigned i = 2, e = Node->getNumValues(); i != e; ++i)
2275         ExprMap[N.getValue(i)] = MakeReg(Node->getValueType(i));
2276     } else {
2277       Result = 1;
2278     }
2279     break;
2280   case ISD::ADD_PARTS:
2281   case ISD::SUB_PARTS:
2282   case ISD::SHL_PARTS:
2283   case ISD::SRL_PARTS:
2284   case ISD::SRA_PARTS:
2285     Result = MakeReg(Node->getValueType(0));
2286     ExprMap[N.getValue(0)] = Result;
2287     for (unsigned i = 1, e = N.Val->getNumValues(); i != e; ++i)
2288       ExprMap[N.getValue(i)] = MakeReg(Node->getValueType(i));
2289     break;
2290   }
2291
2292   switch (N.getOpcode()) {
2293   default:
2294     Node->dump();
2295     assert(0 && "Node not handled!\n");
2296   case ISD::FP_EXTEND:
2297     assert(X86ScalarSSE && "Scalar SSE FP must be enabled to use f32");
2298     Tmp1 = SelectExpr(N.getOperand(0));
2299     BuildMI(BB, X86::CVTSS2SDrr, 1, Result).addReg(Tmp1);
2300     return Result;
2301   case ISD::FP_ROUND:
2302     assert(X86ScalarSSE && "Scalar SSE FP must be enabled to use f32");
2303     Tmp1 = SelectExpr(N.getOperand(0));
2304     BuildMI(BB, X86::CVTSD2SSrr, 1, Result).addReg(Tmp1);
2305     return Result;
2306   case ISD::CopyFromReg:
2307     Select(N.getOperand(0));
2308     if (Result == 1) {
2309       Reg = Result = ExprMap[N.getValue(0)] =
2310         MakeReg(N.getValue(0).getValueType());
2311     }
2312     Tmp1 = cast<RegisterSDNode>(Node->getOperand(1))->getReg();
2313     switch (Node->getValueType(0)) {
2314     default: assert(0 && "Cannot CopyFromReg this!");
2315     case MVT::i1:
2316     case MVT::i8:
2317       BuildMI(BB, X86::MOV8rr, 1, Result).addReg(Tmp1);
2318       return Result;
2319     case MVT::i16:
2320       BuildMI(BB, X86::MOV16rr, 1, Result).addReg(Tmp1);
2321       return Result;
2322     case MVT::i32:
2323       BuildMI(BB, X86::MOV32rr, 1, Result).addReg(Tmp1);
2324       return Result;
2325     }
2326
2327   case ISD::FrameIndex:
2328     Tmp1 = cast<FrameIndexSDNode>(N)->getIndex();
2329     addFrameReference(BuildMI(BB, X86::LEA32r, 4, Result), (int)Tmp1);
2330     return Result;
2331   case ISD::ConstantPool:
2332     Tmp1 = cast<ConstantPoolSDNode>(N)->getIndex();
2333     addConstantPoolReference(BuildMI(BB, X86::LEA32r, 4, Result), Tmp1);
2334     return Result;
2335   case ISD::ConstantFP:
2336     if (X86ScalarSSE) {
2337       assert(cast<ConstantFPSDNode>(N)->isExactlyValue(+0.0) &&
2338              "SSE only supports +0.0");
2339       Opc = (N.getValueType() == MVT::f32) ? X86::FLD0SS : X86::FLD0SD;
2340       BuildMI(BB, Opc, 0, Result);
2341       return Result;
2342     }
2343     ContainsFPCode = true;
2344     Tmp1 = Result;   // Intermediate Register
2345     if (cast<ConstantFPSDNode>(N)->getValue() < 0.0 ||
2346         cast<ConstantFPSDNode>(N)->isExactlyValue(-0.0))
2347       Tmp1 = MakeReg(MVT::f64);
2348
2349     if (cast<ConstantFPSDNode>(N)->isExactlyValue(+0.0) ||
2350         cast<ConstantFPSDNode>(N)->isExactlyValue(-0.0))
2351       BuildMI(BB, X86::FLD0, 0, Tmp1);
2352     else if (cast<ConstantFPSDNode>(N)->isExactlyValue(+1.0) ||
2353              cast<ConstantFPSDNode>(N)->isExactlyValue(-1.0))
2354       BuildMI(BB, X86::FLD1, 0, Tmp1);
2355     else
2356       assert(0 && "Unexpected constant!");
2357     if (Tmp1 != Result)
2358       BuildMI(BB, X86::FCHS, 1, Result).addReg(Tmp1);
2359     return Result;
2360   case ISD::Constant:
2361     switch (N.getValueType()) {
2362     default: assert(0 && "Cannot use constants of this type!");
2363     case MVT::i1:
2364     case MVT::i8:  Opc = X86::MOV8ri;  break;
2365     case MVT::i16: Opc = X86::MOV16ri; break;
2366     case MVT::i32: Opc = X86::MOV32ri; break;
2367     }
2368     BuildMI(BB, Opc, 1,Result).addImm(cast<ConstantSDNode>(N)->getValue());
2369     return Result;
2370   case ISD::UNDEF:
2371     if (Node->getValueType(0) == MVT::f64) {
2372       // FIXME: SHOULD TEACH STACKIFIER ABOUT UNDEF VALUES!
2373       BuildMI(BB, X86::FLD0, 0, Result);
2374     } else {
2375       BuildMI(BB, X86::IMPLICIT_DEF, 0, Result);
2376     }
2377     return Result;
2378   case ISD::GlobalAddress: {
2379     GlobalValue *GV = cast<GlobalAddressSDNode>(N)->getGlobal();
2380     // For Darwin, external and weak symbols are indirect, so we want to load
2381     // the value at address GV, not the value of GV itself.
2382     if (Subtarget->getIndirectExternAndWeakGlobals() &&
2383         (GV->hasWeakLinkage() || GV->isExternal())) {
2384       BuildMI(BB, X86::MOV32rm, 4, Result).addReg(0).addZImm(1).addReg(0)
2385         .addGlobalAddress(GV, false, 0);
2386     } else {
2387       BuildMI(BB, X86::MOV32ri, 1, Result).addGlobalAddress(GV);
2388     }
2389     return Result;
2390   }
2391   case ISD::ExternalSymbol: {
2392     const char *Sym = cast<ExternalSymbolSDNode>(N)->getSymbol();
2393     BuildMI(BB, X86::MOV32ri, 1, Result).addExternalSymbol(Sym);
2394     return Result;
2395   }
2396   case ISD::ZERO_EXTEND: {
2397     int DestIs16 = N.getValueType() == MVT::i16;
2398     int SrcIs16  = N.getOperand(0).getValueType() == MVT::i16;
2399
2400     // FIXME: This hack is here for zero extension casts from bool to i8.  This
2401     // would not be needed if bools were promoted by Legalize.
2402     if (N.getValueType() == MVT::i8) {
2403       Tmp1 = SelectExpr(N.getOperand(0));
2404       BuildMI(BB, X86::MOV8rr, 1, Result).addReg(Tmp1);
2405       return Result;
2406     }
2407
2408     if (isFoldableLoad(N.getOperand(0), SDOperand())) {
2409       static const unsigned Opc[3] = {
2410         X86::MOVZX32rm8, X86::MOVZX32rm16, X86::MOVZX16rm8
2411       };
2412
2413       X86AddressMode AM;
2414       EmitFoldedLoad(N.getOperand(0), AM);
2415       addFullAddress(BuildMI(BB, Opc[SrcIs16+DestIs16*2], 4, Result), AM);
2416
2417       return Result;
2418     }
2419
2420     static const unsigned Opc[3] = {
2421       X86::MOVZX32rr8, X86::MOVZX32rr16, X86::MOVZX16rr8
2422     };
2423     Tmp1 = SelectExpr(N.getOperand(0));
2424     BuildMI(BB, Opc[SrcIs16+DestIs16*2], 1, Result).addReg(Tmp1);
2425     return Result;
2426   }
2427   case ISD::SIGN_EXTEND: {
2428     int DestIs16 = N.getValueType() == MVT::i16;
2429     int SrcIs16  = N.getOperand(0).getValueType() == MVT::i16;
2430
2431     // FIXME: Legalize should promote bools to i8!
2432     assert(N.getOperand(0).getValueType() != MVT::i1 &&
2433            "Sign extend from bool not implemented!");
2434
2435     if (isFoldableLoad(N.getOperand(0), SDOperand())) {
2436       static const unsigned Opc[3] = {
2437         X86::MOVSX32rm8, X86::MOVSX32rm16, X86::MOVSX16rm8
2438       };
2439
2440       X86AddressMode AM;
2441       EmitFoldedLoad(N.getOperand(0), AM);
2442       addFullAddress(BuildMI(BB, Opc[SrcIs16+DestIs16*2], 4, Result), AM);
2443       return Result;
2444     }
2445
2446     static const unsigned Opc[3] = {
2447       X86::MOVSX32rr8, X86::MOVSX32rr16, X86::MOVSX16rr8
2448     };
2449     Tmp1 = SelectExpr(N.getOperand(0));
2450     BuildMI(BB, Opc[SrcIs16+DestIs16*2], 1, Result).addReg(Tmp1);
2451     return Result;
2452   }
2453   case ISD::TRUNCATE:
2454     // Fold TRUNCATE (LOAD P) into a smaller load from P.
2455     // FIXME: This should be performed by the DAGCombiner.
2456     if (isFoldableLoad(N.getOperand(0), SDOperand())) {
2457       switch (N.getValueType()) {
2458       default: assert(0 && "Unknown truncate!");
2459       case MVT::i1:
2460       case MVT::i8:  Opc = X86::MOV8rm;  break;
2461       case MVT::i16: Opc = X86::MOV16rm; break;
2462       }
2463       X86AddressMode AM;
2464       EmitFoldedLoad(N.getOperand(0), AM);
2465       addFullAddress(BuildMI(BB, Opc, 4, Result), AM);
2466       return Result;
2467     }
2468
2469     // Handle cast of LARGER int to SMALLER int using a move to EAX followed by
2470     // a move out of AX or AL.
2471     switch (N.getOperand(0).getValueType()) {
2472     default: assert(0 && "Unknown truncate!");
2473     case MVT::i8:  Tmp2 = X86::AL;  Opc = X86::MOV8rr;  break;
2474     case MVT::i16: Tmp2 = X86::AX;  Opc = X86::MOV16rr; break;
2475     case MVT::i32: Tmp2 = X86::EAX; Opc = X86::MOV32rr; break;
2476     }
2477     Tmp1 = SelectExpr(N.getOperand(0));
2478     BuildMI(BB, Opc, 1, Tmp2).addReg(Tmp1);
2479
2480     switch (N.getValueType()) {
2481     default: assert(0 && "Unknown truncate!");
2482     case MVT::i1:
2483     case MVT::i8:  Tmp2 = X86::AL;  Opc = X86::MOV8rr;  break;
2484     case MVT::i16: Tmp2 = X86::AX;  Opc = X86::MOV16rr; break;
2485     }
2486     BuildMI(BB, Opc, 1, Result).addReg(Tmp2);
2487     return Result;
2488
2489   case ISD::SINT_TO_FP: {
2490     Tmp1 = SelectExpr(N.getOperand(0));  // Get the operand register
2491     unsigned PromoteOpcode = 0;
2492
2493     // We can handle any sint to fp with the direct sse conversion instructions.
2494     if (X86ScalarSSE) {
2495       Opc = (N.getValueType() == MVT::f64) ? X86::CVTSI2SDrr : X86::CVTSI2SSrr;
2496       BuildMI(BB, Opc, 1, Result).addReg(Tmp1);
2497       return Result;
2498     }
2499
2500     ContainsFPCode = true;
2501
2502     // Spill the integer to memory and reload it from there.
2503     MVT::ValueType SrcTy = N.getOperand(0).getValueType();
2504     unsigned Size = MVT::getSizeInBits(SrcTy)/8;
2505     MachineFunction *F = BB->getParent();
2506     int FrameIdx = F->getFrameInfo()->CreateStackObject(Size, Size);
2507
2508     switch (SrcTy) {
2509     case MVT::i32:
2510       addFrameReference(BuildMI(BB, X86::MOV32mr, 5), FrameIdx).addReg(Tmp1);
2511       addFrameReference(BuildMI(BB, X86::FILD32m, 5, Result), FrameIdx);
2512       break;
2513     case MVT::i16:
2514       addFrameReference(BuildMI(BB, X86::MOV16mr, 5), FrameIdx).addReg(Tmp1);
2515       addFrameReference(BuildMI(BB, X86::FILD16m, 5, Result), FrameIdx);
2516       break;
2517     default: break; // No promotion required.
2518     }
2519     return Result;
2520   }
2521   case ISD::FP_TO_SINT:
2522     Tmp1 = SelectExpr(N.getOperand(0));  // Get the operand register
2523
2524     // If the target supports SSE2 and is performing FP operations in SSE regs
2525     // instead of the FP stack, then we can use the efficient CVTSS2SI and
2526     // CVTSD2SI instructions.
2527     assert(X86ScalarSSE);
2528     if (MVT::f32 == N.getOperand(0).getValueType()) {
2529       BuildMI(BB, X86::CVTTSS2SIrr, 1, Result).addReg(Tmp1);
2530     } else if (MVT::f64 == N.getOperand(0).getValueType()) {
2531       BuildMI(BB, X86::CVTTSD2SIrr, 1, Result).addReg(Tmp1);
2532     } else {
2533       assert(0 && "Not an f32 or f64?");
2534       abort();
2535     }
2536     return Result;
2537
2538   case ISD::ADD:
2539     Op0 = N.getOperand(0);
2540     Op1 = N.getOperand(1);
2541
2542     if (isFoldableLoad(Op0, Op1, true)) {
2543       std::swap(Op0, Op1);
2544       goto FoldAdd;
2545     }
2546
2547     if (isFoldableLoad(Op1, Op0, true)) {
2548     FoldAdd:
2549       switch (N.getValueType()) {
2550       default: assert(0 && "Cannot add this type!");
2551       case MVT::i1:
2552       case MVT::i8:  Opc = X86::ADD8rm;  break;
2553       case MVT::i16: Opc = X86::ADD16rm; break;
2554       case MVT::i32: Opc = X86::ADD32rm; break;
2555       case MVT::f32: Opc = X86::ADDSSrm; break;
2556       case MVT::f64:
2557         // For F64, handle promoted load operations (from F32) as well!
2558         if (X86ScalarSSE) {
2559           assert(Op1.getOpcode() == ISD::LOAD && "SSE load not promoted");
2560           Opc = X86::ADDSDrm;
2561         } else {
2562           Opc = Op1.getOpcode() == ISD::LOAD ? X86::FADD64m : X86::FADD32m;
2563         }
2564         break;
2565       }
2566       X86AddressMode AM;
2567       EmitFoldedLoad(Op1, AM);
2568       Tmp1 = SelectExpr(Op0);
2569       addFullAddress(BuildMI(BB, Opc, 5, Result).addReg(Tmp1), AM);
2570       return Result;
2571     }
2572
2573     // See if we can codegen this as an LEA to fold operations together.
2574     if (N.getValueType() == MVT::i32) {
2575       ExprMap.erase(N);
2576       X86ISelAddressMode AM;
2577       MatchAddress(N, AM);
2578       ExprMap[N] = Result;
2579
2580       // If this is not just an add, emit the LEA.  For a simple add (like
2581       // reg+reg or reg+imm), we just emit an add.  It might be a good idea to
2582       // leave this as LEA, then peephole it to 'ADD' after two address elim
2583       // happens.
2584       if (AM.Scale != 1 || AM.BaseType == X86ISelAddressMode::FrameIndexBase||
2585           AM.GV || (AM.Base.Reg.Val && AM.IndexReg.Val && AM.Disp)) {
2586         X86AddressMode XAM = SelectAddrExprs(AM);
2587         addFullAddress(BuildMI(BB, X86::LEA32r, 4, Result), XAM);
2588         return Result;
2589       }
2590     }
2591
2592     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Op1)) {
2593       Opc = 0;
2594       if (CN->getValue() == 1) {   // add X, 1 -> inc X
2595         switch (N.getValueType()) {
2596         default: assert(0 && "Cannot integer add this type!");
2597         case MVT::i8:  Opc = X86::INC8r; break;
2598         case MVT::i16: Opc = X86::INC16r; break;
2599         case MVT::i32: Opc = X86::INC32r; break;
2600         }
2601       } else if (CN->isAllOnesValue()) { // add X, -1 -> dec X
2602         switch (N.getValueType()) {
2603         default: assert(0 && "Cannot integer add this type!");
2604         case MVT::i8:  Opc = X86::DEC8r; break;
2605         case MVT::i16: Opc = X86::DEC16r; break;
2606         case MVT::i32: Opc = X86::DEC32r; break;
2607         }
2608       }
2609
2610       if (Opc) {
2611         Tmp1 = SelectExpr(Op0);
2612         BuildMI(BB, Opc, 1, Result).addReg(Tmp1);
2613         return Result;
2614       }
2615
2616       switch (N.getValueType()) {
2617       default: assert(0 && "Cannot add this type!");
2618       case MVT::i8:  Opc = X86::ADD8ri; break;
2619       case MVT::i16: Opc = X86::ADD16ri; break;
2620       case MVT::i32: Opc = X86::ADD32ri; break;
2621       }
2622       if (Opc) {
2623         Tmp1 = SelectExpr(Op0);
2624         BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(CN->getValue());
2625         return Result;
2626       }
2627     }
2628
2629     switch (N.getValueType()) {
2630     default: assert(0 && "Cannot add this type!");
2631     case MVT::i8:  Opc = X86::ADD8rr; break;
2632     case MVT::i16: Opc = X86::ADD16rr; break;
2633     case MVT::i32: Opc = X86::ADD32rr; break;
2634     case MVT::f32: Opc = X86::ADDSSrr; break;
2635     case MVT::f64: Opc = X86ScalarSSE ? X86::ADDSDrr : X86::FpADD; break;
2636     }
2637
2638     if (getRegPressure(Op0) > getRegPressure(Op1)) {
2639       Tmp1 = SelectExpr(Op0);
2640       Tmp2 = SelectExpr(Op1);
2641     } else {
2642       Tmp2 = SelectExpr(Op1);
2643       Tmp1 = SelectExpr(Op0);
2644     }
2645
2646     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
2647     return Result;
2648
2649   case ISD::FSQRT:
2650     Tmp1 = SelectExpr(Node->getOperand(0));
2651     if (X86ScalarSSE) {
2652       Opc = (N.getValueType() == MVT::f32) ? X86::SQRTSSrr : X86::SQRTSDrr;
2653       BuildMI(BB, Opc, 1, Result).addReg(Tmp1);
2654     } else {
2655       BuildMI(BB, X86::FSQRT, 1, Result).addReg(Tmp1);
2656     }
2657     return Result;
2658
2659   // FIXME:
2660   // Once we can spill 16 byte constants into the constant pool, we can
2661   // implement SSE equivalents of FABS and FCHS.
2662   case ISD::FABS:
2663   case ISD::FNEG:
2664   case ISD::FSIN:
2665   case ISD::FCOS:
2666     assert(N.getValueType()==MVT::f64 && "Illegal type for this operation");
2667     Tmp1 = SelectExpr(Node->getOperand(0));
2668     switch (N.getOpcode()) {
2669     default: assert(0 && "Unreachable!");
2670     case ISD::FABS: BuildMI(BB, X86::FABS, 1, Result).addReg(Tmp1); break;
2671     case ISD::FNEG: BuildMI(BB, X86::FCHS, 1, Result).addReg(Tmp1); break;
2672     case ISD::FSIN: BuildMI(BB, X86::FSIN, 1, Result).addReg(Tmp1); break;
2673     case ISD::FCOS: BuildMI(BB, X86::FCOS, 1, Result).addReg(Tmp1); break;
2674     }
2675     return Result;
2676
2677   case ISD::MULHU:
2678     switch (N.getValueType()) {
2679     default: assert(0 && "Unsupported VT!");
2680     case MVT::i8:  Tmp2 = X86::MUL8r;  break;
2681     case MVT::i16: Tmp2 = X86::MUL16r;  break;
2682     case MVT::i32: Tmp2 = X86::MUL32r;  break;
2683     }
2684     // FALL THROUGH
2685   case ISD::MULHS: {
2686     unsigned MovOpc, LowReg, HiReg;
2687     switch (N.getValueType()) {
2688     default: assert(0 && "Unsupported VT!");
2689     case MVT::i8:
2690       MovOpc = X86::MOV8rr;
2691       LowReg = X86::AL;
2692       HiReg = X86::AH;
2693       Opc = X86::IMUL8r;
2694       break;
2695     case MVT::i16:
2696       MovOpc = X86::MOV16rr;
2697       LowReg = X86::AX;
2698       HiReg = X86::DX;
2699       Opc = X86::IMUL16r;
2700       break;
2701     case MVT::i32:
2702       MovOpc = X86::MOV32rr;
2703       LowReg = X86::EAX;
2704       HiReg = X86::EDX;
2705       Opc = X86::IMUL32r;
2706       break;
2707     }
2708     if (Node->getOpcode() != ISD::MULHS)
2709       Opc = Tmp2;  // Get the MULHU opcode.
2710
2711     Op0 = Node->getOperand(0);
2712     Op1 = Node->getOperand(1);
2713     if (getRegPressure(Op0) > getRegPressure(Op1)) {
2714       Tmp1 = SelectExpr(Op0);
2715       Tmp2 = SelectExpr(Op1);
2716     } else {
2717       Tmp2 = SelectExpr(Op1);
2718       Tmp1 = SelectExpr(Op0);
2719     }
2720
2721     // FIXME: Implement folding of loads into the memory operands here!
2722     BuildMI(BB, MovOpc, 1, LowReg).addReg(Tmp1);
2723     BuildMI(BB, Opc, 1).addReg(Tmp2);
2724     BuildMI(BB, MovOpc, 1, Result).addReg(HiReg);
2725     return Result;
2726   }
2727
2728   case ISD::SUB:
2729   case ISD::MUL:
2730   case ISD::AND:
2731   case ISD::OR:
2732   case ISD::XOR: {
2733     static const unsigned SUBTab[] = {
2734       X86::SUB8ri, X86::SUB16ri, X86::SUB32ri, 0, 0,
2735       X86::SUB8rm, X86::SUB16rm, X86::SUB32rm, X86::FSUB32m, X86::FSUB64m,
2736       X86::SUB8rr, X86::SUB16rr, X86::SUB32rr, X86::FpSUB  , X86::FpSUB,
2737     };
2738     static const unsigned SSE_SUBTab[] = {
2739       X86::SUB8ri, X86::SUB16ri, X86::SUB32ri, 0, 0,
2740       X86::SUB8rm, X86::SUB16rm, X86::SUB32rm, X86::SUBSSrm, X86::SUBSDrm,
2741       X86::SUB8rr, X86::SUB16rr, X86::SUB32rr, X86::SUBSSrr, X86::SUBSDrr,
2742     };
2743     static const unsigned MULTab[] = {
2744       0, X86::IMUL16rri, X86::IMUL32rri, 0, 0,
2745       0, X86::IMUL16rm , X86::IMUL32rm, X86::FMUL32m, X86::FMUL64m,
2746       0, X86::IMUL16rr , X86::IMUL32rr, X86::FpMUL  , X86::FpMUL,
2747     };
2748     static const unsigned SSE_MULTab[] = {
2749       0, X86::IMUL16rri, X86::IMUL32rri, 0, 0,
2750       0, X86::IMUL16rm , X86::IMUL32rm, X86::MULSSrm, X86::MULSDrm,
2751       0, X86::IMUL16rr , X86::IMUL32rr, X86::MULSSrr, X86::MULSDrr,
2752     };
2753     static const unsigned ANDTab[] = {
2754       X86::AND8ri, X86::AND16ri, X86::AND32ri, 0, 0,
2755       X86::AND8rm, X86::AND16rm, X86::AND32rm, 0, 0,
2756       X86::AND8rr, X86::AND16rr, X86::AND32rr, 0, 0,
2757     };
2758     static const unsigned ORTab[] = {
2759       X86::OR8ri, X86::OR16ri, X86::OR32ri, 0, 0,
2760       X86::OR8rm, X86::OR16rm, X86::OR32rm, 0, 0,
2761       X86::OR8rr, X86::OR16rr, X86::OR32rr, 0, 0,
2762     };
2763     static const unsigned XORTab[] = {
2764       X86::XOR8ri, X86::XOR16ri, X86::XOR32ri, 0, 0,
2765       X86::XOR8rm, X86::XOR16rm, X86::XOR32rm, 0, 0,
2766       X86::XOR8rr, X86::XOR16rr, X86::XOR32rr, 0, 0,
2767     };
2768
2769     Op0 = Node->getOperand(0);
2770     Op1 = Node->getOperand(1);
2771
2772     if (Node->getOpcode() == ISD::OR && Op0.hasOneUse() && Op1.hasOneUse())
2773       if (EmitOrOpOp(Op0, Op1, Result)) // Match SHLD, SHRD, and rotates.
2774         return Result;
2775
2776     if (Node->getOpcode() == ISD::SUB)
2777       if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(0)))
2778         if (CN->isNullValue()) {   // 0 - N -> neg N
2779           switch (N.getValueType()) {
2780           default: assert(0 && "Cannot sub this type!");
2781           case MVT::i1:
2782           case MVT::i8:  Opc = X86::NEG8r;  break;
2783           case MVT::i16: Opc = X86::NEG16r; break;
2784           case MVT::i32: Opc = X86::NEG32r; break;
2785           }
2786           Tmp1 = SelectExpr(N.getOperand(1));
2787           BuildMI(BB, Opc, 1, Result).addReg(Tmp1);
2788           return Result;
2789         }
2790
2791     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Op1)) {
2792       if (CN->isAllOnesValue() && Node->getOpcode() == ISD::XOR) {
2793         Opc = 0;
2794         switch (N.getValueType()) {
2795         default: assert(0 && "Cannot add this type!");
2796         case MVT::i1:  break;  // Not supported, don't invert upper bits!
2797         case MVT::i8:  Opc = X86::NOT8r;  break;
2798         case MVT::i16: Opc = X86::NOT16r; break;
2799         case MVT::i32: Opc = X86::NOT32r; break;
2800         }
2801         if (Opc) {
2802           Tmp1 = SelectExpr(Op0);
2803           BuildMI(BB, Opc, 1, Result).addReg(Tmp1);
2804           return Result;
2805         }
2806       }
2807
2808       // Fold common multiplies into LEA instructions.
2809       if (Node->getOpcode() == ISD::MUL && N.getValueType() == MVT::i32) {
2810         switch ((int)CN->getValue()) {
2811         default: break;
2812         case 3:
2813         case 5:
2814         case 9:
2815           // Remove N from exprmap so SelectAddress doesn't get confused.
2816           ExprMap.erase(N);
2817           X86AddressMode AM;
2818           SelectAddress(N, AM);
2819           // Restore it to the map.
2820           ExprMap[N] = Result;
2821           addFullAddress(BuildMI(BB, X86::LEA32r, 4, Result), AM);
2822           return Result;
2823         }
2824       }
2825
2826       switch (N.getValueType()) {
2827       default: assert(0 && "Cannot xor this type!");
2828       case MVT::i1:
2829       case MVT::i8:  Opc = 0; break;
2830       case MVT::i16: Opc = 1; break;
2831       case MVT::i32: Opc = 2; break;
2832       }
2833       switch (Node->getOpcode()) {
2834       default: assert(0 && "Unreachable!");
2835       case ISD::SUB: Opc = X86ScalarSSE ? SSE_SUBTab[Opc] : SUBTab[Opc]; break;
2836       case ISD::MUL: Opc = X86ScalarSSE ? SSE_MULTab[Opc] : MULTab[Opc]; break;
2837       case ISD::AND: Opc = ANDTab[Opc]; break;
2838       case ISD::OR:  Opc =  ORTab[Opc]; break;
2839       case ISD::XOR: Opc = XORTab[Opc]; break;
2840       }
2841       if (Opc) {  // Can't fold MUL:i8 R, imm
2842         Tmp1 = SelectExpr(Op0);
2843         BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(CN->getValue());
2844         return Result;
2845       }
2846     }
2847
2848     if (isFoldableLoad(Op0, Op1, true))
2849       if (Node->getOpcode() != ISD::SUB) {
2850         std::swap(Op0, Op1);
2851         goto FoldOps;
2852       } else {
2853         // For FP, emit 'reverse' subract, with a memory operand.
2854         if (N.getValueType() == MVT::f64 && !X86ScalarSSE) {
2855           if (Op0.getOpcode() == ISD::EXTLOAD)
2856             Opc = X86::FSUBR32m;
2857           else
2858             Opc = X86::FSUBR64m;
2859
2860           X86AddressMode AM;
2861           EmitFoldedLoad(Op0, AM);
2862           Tmp1 = SelectExpr(Op1);
2863           addFullAddress(BuildMI(BB, Opc, 5, Result).addReg(Tmp1), AM);
2864           return Result;
2865         }
2866       }
2867
2868     if (isFoldableLoad(Op1, Op0, true)) {
2869     FoldOps:
2870       switch (N.getValueType()) {
2871       default: assert(0 && "Cannot operate on this type!");
2872       case MVT::i1:
2873       case MVT::i8:  Opc = 5; break;
2874       case MVT::i16: Opc = 6; break;
2875       case MVT::i32: Opc = 7; break;
2876       case MVT::f32: Opc = 8; break;
2877         // For F64, handle promoted load operations (from F32) as well!
2878       case MVT::f64:
2879         assert((!X86ScalarSSE || Op1.getOpcode() == ISD::LOAD) &&
2880                "SSE load should have been promoted");
2881         Opc = Op1.getOpcode() == ISD::LOAD ? 9 : 8; break;
2882       }
2883       switch (Node->getOpcode()) {
2884       default: assert(0 && "Unreachable!");
2885       case ISD::SUB: Opc = X86ScalarSSE ? SSE_SUBTab[Opc] : SUBTab[Opc]; break;
2886       case ISD::MUL: Opc = X86ScalarSSE ? SSE_MULTab[Opc] : MULTab[Opc]; break;
2887       case ISD::AND: Opc = ANDTab[Opc]; break;
2888       case ISD::OR:  Opc =  ORTab[Opc]; break;
2889       case ISD::XOR: Opc = XORTab[Opc]; break;
2890       }
2891
2892       X86AddressMode AM;
2893       EmitFoldedLoad(Op1, AM);
2894       Tmp1 = SelectExpr(Op0);
2895       if (Opc) {
2896         addFullAddress(BuildMI(BB, Opc, 5, Result).addReg(Tmp1), AM);
2897       } else {
2898         assert(Node->getOpcode() == ISD::MUL &&
2899                N.getValueType() == MVT::i8 && "Unexpected situation!");
2900         // Must use the MUL instruction, which forces use of AL.
2901         BuildMI(BB, X86::MOV8rr, 1, X86::AL).addReg(Tmp1);
2902         addFullAddress(BuildMI(BB, X86::MUL8m, 1), AM);
2903         BuildMI(BB, X86::MOV8rr, 1, Result).addReg(X86::AL);
2904       }
2905       return Result;
2906     }
2907
2908     if (getRegPressure(Op0) > getRegPressure(Op1)) {
2909       Tmp1 = SelectExpr(Op0);
2910       Tmp2 = SelectExpr(Op1);
2911     } else {
2912       Tmp2 = SelectExpr(Op1);
2913       Tmp1 = SelectExpr(Op0);
2914     }
2915
2916     switch (N.getValueType()) {
2917     default: assert(0 && "Cannot add this type!");
2918     case MVT::i1:
2919     case MVT::i8:  Opc = 10; break;
2920     case MVT::i16: Opc = 11; break;
2921     case MVT::i32: Opc = 12; break;
2922     case MVT::f32: Opc = 13; break;
2923     case MVT::f64: Opc = 14; break;
2924     }
2925     switch (Node->getOpcode()) {
2926     default: assert(0 && "Unreachable!");
2927     case ISD::SUB: Opc = X86ScalarSSE ? SSE_SUBTab[Opc] : SUBTab[Opc]; break;
2928     case ISD::MUL: Opc = X86ScalarSSE ? SSE_MULTab[Opc] : MULTab[Opc]; break;
2929     case ISD::AND: Opc = ANDTab[Opc]; break;
2930     case ISD::OR:  Opc =  ORTab[Opc]; break;
2931     case ISD::XOR: Opc = XORTab[Opc]; break;
2932     }
2933     if (Opc) {
2934       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
2935     } else {
2936       assert(Node->getOpcode() == ISD::MUL &&
2937              N.getValueType() == MVT::i8 && "Unexpected situation!");
2938       // Must use the MUL instruction, which forces use of AL.
2939       BuildMI(BB, X86::MOV8rr, 1, X86::AL).addReg(Tmp1);
2940       BuildMI(BB, X86::MUL8r, 1).addReg(Tmp2);
2941       BuildMI(BB, X86::MOV8rr, 1, Result).addReg(X86::AL);
2942     }
2943     return Result;
2944   }
2945   case ISD::ADD_PARTS:
2946   case ISD::SUB_PARTS: {
2947     assert(N.getNumOperands() == 4 && N.getValueType() == MVT::i32 &&
2948            "Not an i64 add/sub!");
2949     // Emit all of the operands.
2950     std::vector<unsigned> InVals;
2951     for (unsigned i = 0, e = N.getNumOperands(); i != e; ++i)
2952       InVals.push_back(SelectExpr(N.getOperand(i)));
2953     if (N.getOpcode() == ISD::ADD_PARTS) {
2954       BuildMI(BB, X86::ADD32rr, 2, Result).addReg(InVals[0]).addReg(InVals[2]);
2955       BuildMI(BB, X86::ADC32rr,2,Result+1).addReg(InVals[1]).addReg(InVals[3]);
2956     } else {
2957       BuildMI(BB, X86::SUB32rr, 2, Result).addReg(InVals[0]).addReg(InVals[2]);
2958       BuildMI(BB, X86::SBB32rr, 2,Result+1).addReg(InVals[1]).addReg(InVals[3]);
2959     }
2960     return Result+N.ResNo;
2961   }
2962
2963   case ISD::SHL_PARTS:
2964   case ISD::SRA_PARTS:
2965   case ISD::SRL_PARTS: {
2966     assert(N.getNumOperands() == 3 && N.getValueType() == MVT::i32 &&
2967            "Not an i64 shift!");
2968     unsigned ShiftOpLo = SelectExpr(N.getOperand(0));
2969     unsigned ShiftOpHi = SelectExpr(N.getOperand(1));
2970     unsigned TmpReg = MakeReg(MVT::i32);
2971     if (N.getOpcode() == ISD::SRA_PARTS) {
2972       // If this is a SHR of a Long, then we need to do funny sign extension
2973       // stuff.  TmpReg gets the value to use as the high-part if we are
2974       // shifting more than 32 bits.
2975       BuildMI(BB, X86::SAR32ri, 2, TmpReg).addReg(ShiftOpHi).addImm(31);
2976     } else {
2977       // Other shifts use a fixed zero value if the shift is more than 32 bits.
2978       BuildMI(BB, X86::MOV32ri, 1, TmpReg).addImm(0);
2979     }
2980
2981     // Initialize CL with the shift amount.
2982     unsigned ShiftAmountReg = SelectExpr(N.getOperand(2));
2983     BuildMI(BB, X86::MOV8rr, 1, X86::CL).addReg(ShiftAmountReg);
2984
2985     unsigned TmpReg2 = MakeReg(MVT::i32);
2986     unsigned TmpReg3 = MakeReg(MVT::i32);
2987     if (N.getOpcode() == ISD::SHL_PARTS) {
2988       // TmpReg2 = shld inHi, inLo
2989       BuildMI(BB, X86::SHLD32rrCL, 2,TmpReg2).addReg(ShiftOpHi)
2990         .addReg(ShiftOpLo);
2991       // TmpReg3 = shl  inLo, CL
2992       BuildMI(BB, X86::SHL32rCL, 1, TmpReg3).addReg(ShiftOpLo);
2993
2994       // Set the flags to indicate whether the shift was by more than 32 bits.
2995       BuildMI(BB, X86::TEST8ri, 2).addReg(X86::CL).addImm(32);
2996
2997       // DestHi = (>32) ? TmpReg3 : TmpReg2;
2998       BuildMI(BB, X86::CMOVNE32rr, 2,
2999               Result+1).addReg(TmpReg2).addReg(TmpReg3);
3000       // DestLo = (>32) ? TmpReg : TmpReg3;
3001       BuildMI(BB, X86::CMOVNE32rr, 2,
3002               Result).addReg(TmpReg3).addReg(TmpReg);
3003     } else {
3004       // TmpReg2 = shrd inLo, inHi
3005       BuildMI(BB, X86::SHRD32rrCL,2,TmpReg2).addReg(ShiftOpLo)
3006         .addReg(ShiftOpHi);
3007       // TmpReg3 = s[ah]r  inHi, CL
3008       BuildMI(BB, N.getOpcode() == ISD::SRA_PARTS ? X86::SAR32rCL
3009                                                   : X86::SHR32rCL, 1, TmpReg3)
3010         .addReg(ShiftOpHi);
3011
3012       // Set the flags to indicate whether the shift was by more than 32 bits.
3013       BuildMI(BB, X86::TEST8ri, 2).addReg(X86::CL).addImm(32);
3014
3015       // DestLo = (>32) ? TmpReg3 : TmpReg2;
3016       BuildMI(BB, X86::CMOVNE32rr, 2,
3017               Result).addReg(TmpReg2).addReg(TmpReg3);
3018
3019       // DestHi = (>32) ? TmpReg : TmpReg3;
3020       BuildMI(BB, X86::CMOVNE32rr, 2,
3021               Result+1).addReg(TmpReg3).addReg(TmpReg);
3022     }
3023     return Result+N.ResNo;
3024   }
3025
3026   case ISD::SELECT:
3027     EmitSelectCC(N.getOperand(0), N.getOperand(1), N.getOperand(2),
3028                  N.getValueType(), Result);
3029     return Result;
3030
3031   case ISD::SDIV:
3032   case ISD::UDIV:
3033   case ISD::SREM:
3034   case ISD::UREM: {
3035     assert((N.getOpcode() != ISD::SREM || MVT::isInteger(N.getValueType())) &&
3036            "We don't support this operator!");
3037
3038     if (N.getOpcode() == ISD::SDIV) {
3039       // We can fold loads into FpDIVs, but not really into any others.
3040       if (N.getValueType() == MVT::f64 && !X86ScalarSSE) {
3041         // Check for reversed and unreversed DIV.
3042         if (isFoldableLoad(N.getOperand(0), N.getOperand(1), true)) {
3043           if (N.getOperand(0).getOpcode() == ISD::EXTLOAD)
3044             Opc = X86::FDIVR32m;
3045           else
3046             Opc = X86::FDIVR64m;
3047           X86AddressMode AM;
3048           EmitFoldedLoad(N.getOperand(0), AM);
3049           Tmp1 = SelectExpr(N.getOperand(1));
3050           addFullAddress(BuildMI(BB, Opc, 5, Result).addReg(Tmp1), AM);
3051           return Result;
3052         } else if (isFoldableLoad(N.getOperand(1), N.getOperand(0), true) &&
3053                    N.getOperand(1).getOpcode() == ISD::LOAD) {
3054           if (N.getOperand(1).getOpcode() == ISD::EXTLOAD)
3055             Opc = X86::FDIV32m;
3056           else
3057             Opc = X86::FDIV64m;
3058           X86AddressMode AM;
3059           EmitFoldedLoad(N.getOperand(1), AM);
3060           Tmp1 = SelectExpr(N.getOperand(0));
3061           addFullAddress(BuildMI(BB, Opc, 5, Result).addReg(Tmp1), AM);
3062           return Result;
3063         }
3064       }
3065
3066       if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
3067         // FIXME: These special cases should be handled by the lowering impl!
3068         unsigned RHS = CN->getValue();
3069         bool isNeg = false;
3070         if ((int)RHS < 0) {
3071           isNeg = true;
3072           RHS = -RHS;
3073         }
3074         if (RHS && (RHS & (RHS-1)) == 0) {   // Signed division by power of 2?
3075           unsigned Log = Log2_32(RHS);
3076           unsigned SAROpc, SHROpc, ADDOpc, NEGOpc;
3077           switch (N.getValueType()) {
3078           default: assert("Unknown type to signed divide!");
3079           case MVT::i8:
3080             SAROpc = X86::SAR8ri;
3081             SHROpc = X86::SHR8ri;
3082             ADDOpc = X86::ADD8rr;
3083             NEGOpc = X86::NEG8r;
3084             break;
3085           case MVT::i16:
3086             SAROpc = X86::SAR16ri;
3087             SHROpc = X86::SHR16ri;
3088             ADDOpc = X86::ADD16rr;
3089             NEGOpc = X86::NEG16r;
3090             break;
3091           case MVT::i32:
3092             SAROpc = X86::SAR32ri;
3093             SHROpc = X86::SHR32ri;
3094             ADDOpc = X86::ADD32rr;
3095             NEGOpc = X86::NEG32r;
3096             break;
3097           }
3098           unsigned RegSize = MVT::getSizeInBits(N.getValueType());
3099           Tmp1 = SelectExpr(N.getOperand(0));
3100           unsigned TmpReg;
3101           if (Log != 1) {
3102             TmpReg = MakeReg(N.getValueType());
3103             BuildMI(BB, SAROpc, 2, TmpReg).addReg(Tmp1).addImm(Log-1);
3104           } else {
3105             TmpReg = Tmp1;
3106           }
3107           unsigned TmpReg2 = MakeReg(N.getValueType());
3108           BuildMI(BB, SHROpc, 2, TmpReg2).addReg(TmpReg).addImm(RegSize-Log);
3109           unsigned TmpReg3 = MakeReg(N.getValueType());
3110           BuildMI(BB, ADDOpc, 2, TmpReg3).addReg(Tmp1).addReg(TmpReg2);
3111
3112           unsigned TmpReg4 = isNeg ? MakeReg(N.getValueType()) : Result;
3113           BuildMI(BB, SAROpc, 2, TmpReg4).addReg(TmpReg3).addImm(Log);
3114           if (isNeg)
3115             BuildMI(BB, NEGOpc, 1, Result).addReg(TmpReg4);
3116           return Result;
3117         }
3118       }
3119     }
3120
3121     if (getRegPressure(N.getOperand(0)) > getRegPressure(N.getOperand(1))) {
3122       Tmp1 = SelectExpr(N.getOperand(0));
3123       Tmp2 = SelectExpr(N.getOperand(1));
3124     } else {
3125       Tmp2 = SelectExpr(N.getOperand(1));
3126       Tmp1 = SelectExpr(N.getOperand(0));
3127     }
3128
3129     bool isSigned = N.getOpcode() == ISD::SDIV || N.getOpcode() == ISD::SREM;
3130     bool isDiv    = N.getOpcode() == ISD::SDIV || N.getOpcode() == ISD::UDIV;
3131     unsigned LoReg, HiReg, DivOpcode, MovOpcode, ClrOpcode, SExtOpcode;
3132     switch (N.getValueType()) {
3133     default: assert(0 && "Cannot sdiv this type!");
3134     case MVT::i8:
3135       DivOpcode = isSigned ? X86::IDIV8r : X86::DIV8r;
3136       LoReg = X86::AL;
3137       HiReg = X86::AH;
3138       MovOpcode = X86::MOV8rr;
3139       ClrOpcode = X86::MOV8ri;
3140       SExtOpcode = X86::CBW;
3141       break;
3142     case MVT::i16:
3143       DivOpcode = isSigned ? X86::IDIV16r : X86::DIV16r;
3144       LoReg = X86::AX;
3145       HiReg = X86::DX;
3146       MovOpcode = X86::MOV16rr;
3147       ClrOpcode = X86::MOV16ri;
3148       SExtOpcode = X86::CWD;
3149       break;
3150     case MVT::i32:
3151       DivOpcode = isSigned ? X86::IDIV32r : X86::DIV32r;
3152       LoReg = X86::EAX;
3153       HiReg = X86::EDX;
3154       MovOpcode = X86::MOV32rr;
3155       ClrOpcode = X86::MOV32ri;
3156       SExtOpcode = X86::CDQ;
3157       break;
3158     case MVT::f32:
3159       BuildMI(BB, X86::DIVSSrr, 2, Result).addReg(Tmp1).addReg(Tmp2);
3160       return Result;
3161     case MVT::f64:
3162       Opc = X86ScalarSSE ? X86::DIVSDrr : X86::FpDIV;
3163       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
3164       return Result;
3165     }
3166
3167     // Set up the low part.
3168     BuildMI(BB, MovOpcode, 1, LoReg).addReg(Tmp1);
3169
3170     if (isSigned) {
3171       // Sign extend the low part into the high part.
3172       BuildMI(BB, SExtOpcode, 0);
3173     } else {
3174       // Zero out the high part, effectively zero extending the input.
3175       BuildMI(BB, ClrOpcode, 1, HiReg).addImm(0);
3176     }
3177
3178     // Emit the DIV/IDIV instruction.
3179     BuildMI(BB, DivOpcode, 1).addReg(Tmp2);
3180
3181     // Get the result of the divide or rem.
3182     BuildMI(BB, MovOpcode, 1, Result).addReg(isDiv ? LoReg : HiReg);
3183     return Result;
3184   }
3185
3186   case ISD::SHL:
3187     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
3188       if (CN->getValue() == 1) {   // X = SHL Y, 1  -> X = ADD Y, Y
3189         switch (N.getValueType()) {
3190         default: assert(0 && "Cannot shift this type!");
3191         case MVT::i8:  Opc = X86::ADD8rr; break;
3192         case MVT::i16: Opc = X86::ADD16rr; break;
3193         case MVT::i32: Opc = X86::ADD32rr; break;
3194         }
3195         Tmp1 = SelectExpr(N.getOperand(0));
3196         BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp1);
3197         return Result;
3198       }
3199
3200       switch (N.getValueType()) {
3201       default: assert(0 && "Cannot shift this type!");
3202       case MVT::i8:  Opc = X86::SHL8ri; break;
3203       case MVT::i16: Opc = X86::SHL16ri; break;
3204       case MVT::i32: Opc = X86::SHL32ri; break;
3205       }
3206       Tmp1 = SelectExpr(N.getOperand(0));
3207       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(CN->getValue());
3208       return Result;
3209     }
3210
3211     if (getRegPressure(N.getOperand(0)) > getRegPressure(N.getOperand(1))) {
3212       Tmp1 = SelectExpr(N.getOperand(0));
3213       Tmp2 = SelectExpr(N.getOperand(1));
3214     } else {
3215       Tmp2 = SelectExpr(N.getOperand(1));
3216       Tmp1 = SelectExpr(N.getOperand(0));
3217     }
3218
3219     switch (N.getValueType()) {
3220     default: assert(0 && "Cannot shift this type!");
3221     case MVT::i8 : Opc = X86::SHL8rCL; break;
3222     case MVT::i16: Opc = X86::SHL16rCL; break;
3223     case MVT::i32: Opc = X86::SHL32rCL; break;
3224     }
3225     BuildMI(BB, X86::MOV8rr, 1, X86::CL).addReg(Tmp2);
3226     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
3227     return Result;
3228   case ISD::SRL:
3229     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
3230       switch (N.getValueType()) {
3231       default: assert(0 && "Cannot shift this type!");
3232       case MVT::i8:  Opc = X86::SHR8ri; break;
3233       case MVT::i16: Opc = X86::SHR16ri; break;
3234       case MVT::i32: Opc = X86::SHR32ri; break;
3235       }
3236       Tmp1 = SelectExpr(N.getOperand(0));
3237       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(CN->getValue());
3238       return Result;
3239     }
3240
3241     if (getRegPressure(N.getOperand(0)) > getRegPressure(N.getOperand(1))) {
3242       Tmp1 = SelectExpr(N.getOperand(0));
3243       Tmp2 = SelectExpr(N.getOperand(1));
3244     } else {
3245       Tmp2 = SelectExpr(N.getOperand(1));
3246       Tmp1 = SelectExpr(N.getOperand(0));
3247     }
3248
3249     switch (N.getValueType()) {
3250     default: assert(0 && "Cannot shift this type!");
3251     case MVT::i8 : Opc = X86::SHR8rCL; break;
3252     case MVT::i16: Opc = X86::SHR16rCL; break;
3253     case MVT::i32: Opc = X86::SHR32rCL; break;
3254     }
3255     BuildMI(BB, X86::MOV8rr, 1, X86::CL).addReg(Tmp2);
3256     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
3257     return Result;
3258   case ISD::SRA:
3259     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
3260       switch (N.getValueType()) {
3261       default: assert(0 && "Cannot shift this type!");
3262       case MVT::i8:  Opc = X86::SAR8ri; break;
3263       case MVT::i16: Opc = X86::SAR16ri; break;
3264       case MVT::i32: Opc = X86::SAR32ri; break;
3265       }
3266       Tmp1 = SelectExpr(N.getOperand(0));
3267       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(CN->getValue());
3268       return Result;
3269     }
3270
3271     if (getRegPressure(N.getOperand(0)) > getRegPressure(N.getOperand(1))) {
3272       Tmp1 = SelectExpr(N.getOperand(0));
3273       Tmp2 = SelectExpr(N.getOperand(1));
3274     } else {
3275       Tmp2 = SelectExpr(N.getOperand(1));
3276       Tmp1 = SelectExpr(N.getOperand(0));
3277     }
3278
3279     switch (N.getValueType()) {
3280     default: assert(0 && "Cannot shift this type!");
3281     case MVT::i8 : Opc = X86::SAR8rCL; break;
3282     case MVT::i16: Opc = X86::SAR16rCL; break;
3283     case MVT::i32: Opc = X86::SAR32rCL; break;
3284     }
3285     BuildMI(BB, X86::MOV8rr, 1, X86::CL).addReg(Tmp2);
3286     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
3287     return Result;
3288
3289   case ISD::SETCC:
3290     EmitCMP(N.getOperand(0), N.getOperand(1), Node->hasOneUse());
3291     EmitSetCC(BB, Result, cast<CondCodeSDNode>(N.getOperand(2))->get(),
3292               MVT::isFloatingPoint(N.getOperand(1).getValueType()));
3293     return Result;
3294   case ISD::LOAD:
3295     // Make sure we generate both values.
3296     if (Result != 1) {  // Generate the token
3297       if (!ExprMap.insert(std::make_pair(N.getValue(1), 1)).second)
3298         assert(0 && "Load already emitted!?");
3299     } else
3300       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
3301
3302     switch (Node->getValueType(0)) {
3303     default: assert(0 && "Cannot load this type!");
3304     case MVT::i1:
3305     case MVT::i8:  Opc = X86::MOV8rm; break;
3306     case MVT::i16: Opc = X86::MOV16rm; break;
3307     case MVT::i32: Opc = X86::MOV32rm; break;
3308     case MVT::f32: Opc = X86::MOVSSrm; break;
3309     case MVT::f64:
3310       if (X86ScalarSSE) {
3311         Opc = X86::MOVSDrm;
3312       } else {
3313         Opc = X86::FLD64m;
3314         ContainsFPCode = true;
3315       }
3316       break;
3317     }
3318
3319     if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(N.getOperand(1))){
3320       Select(N.getOperand(0));
3321       addConstantPoolReference(BuildMI(BB, Opc, 4, Result), CP->getIndex());
3322     } else {
3323       X86AddressMode AM;
3324
3325       SDOperand Chain   = N.getOperand(0);
3326       SDOperand Address = N.getOperand(1);
3327       if (getRegPressure(Chain) > getRegPressure(Address)) {
3328         Select(Chain);
3329         SelectAddress(Address, AM);
3330       } else {
3331         SelectAddress(Address, AM);
3332         Select(Chain);
3333       }
3334
3335       addFullAddress(BuildMI(BB, Opc, 4, Result), AM);
3336     }
3337     return Result;
3338   case X86ISD::FILD64m:
3339     // Make sure we generate both values.
3340     assert(Result != 1 && N.getValueType() == MVT::f64);
3341     if (!ExprMap.insert(std::make_pair(N.getValue(1), 1)).second)
3342       assert(0 && "Load already emitted!?");
3343
3344     {
3345       X86AddressMode AM;
3346
3347       SDOperand Chain   = N.getOperand(0);
3348       SDOperand Address = N.getOperand(1);
3349       if (getRegPressure(Chain) > getRegPressure(Address)) {
3350         Select(Chain);
3351         SelectAddress(Address, AM);
3352       } else {
3353         SelectAddress(Address, AM);
3354         Select(Chain);
3355       }
3356
3357       addFullAddress(BuildMI(BB, X86::FILD64m, 4, Result), AM);
3358     }
3359     return Result;
3360
3361   case ISD::EXTLOAD:          // Arbitrarily codegen extloads as MOVZX*
3362   case ISD::ZEXTLOAD: {
3363     // Make sure we generate both values.
3364     if (Result != 1)
3365       ExprMap[N.getValue(1)] = 1;   // Generate the token
3366     else
3367       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
3368
3369     if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(N.getOperand(1)))
3370       if (Node->getValueType(0) == MVT::f64) {
3371         assert(cast<VTSDNode>(Node->getOperand(3))->getVT() == MVT::f32 &&
3372                "Bad EXTLOAD!");
3373         addConstantPoolReference(BuildMI(BB, X86::FLD32m, 4, Result),
3374                                  CP->getIndex());
3375         return Result;
3376       }
3377
3378     X86AddressMode AM;
3379     if (getRegPressure(Node->getOperand(0)) >
3380            getRegPressure(Node->getOperand(1))) {
3381       Select(Node->getOperand(0)); // chain
3382       SelectAddress(Node->getOperand(1), AM);
3383     } else {
3384       SelectAddress(Node->getOperand(1), AM);
3385       Select(Node->getOperand(0)); // chain
3386     }
3387
3388     switch (Node->getValueType(0)) {
3389     default: assert(0 && "Unknown type to sign extend to.");
3390     case MVT::f64:
3391       assert(cast<VTSDNode>(Node->getOperand(3))->getVT() == MVT::f32 &&
3392              "Bad EXTLOAD!");
3393       addFullAddress(BuildMI(BB, X86::FLD32m, 5, Result), AM);
3394       break;
3395     case MVT::i32:
3396       switch (cast<VTSDNode>(Node->getOperand(3))->getVT()) {
3397       default:
3398         assert(0 && "Bad zero extend!");
3399       case MVT::i1:
3400       case MVT::i8:
3401         addFullAddress(BuildMI(BB, X86::MOVZX32rm8, 5, Result), AM);
3402         break;
3403       case MVT::i16:
3404         addFullAddress(BuildMI(BB, X86::MOVZX32rm16, 5, Result), AM);
3405         break;
3406       }
3407       break;
3408     case MVT::i16:
3409       assert(cast<VTSDNode>(Node->getOperand(3))->getVT() <= MVT::i8 &&
3410              "Bad zero extend!");
3411       addFullAddress(BuildMI(BB, X86::MOVSX16rm8, 5, Result), AM);
3412       break;
3413     case MVT::i8:
3414       assert(cast<VTSDNode>(Node->getOperand(3))->getVT() == MVT::i1 &&
3415              "Bad zero extend!");
3416       addFullAddress(BuildMI(BB, X86::MOV8rm, 5, Result), AM);
3417       break;
3418     }
3419     return Result;
3420   }
3421   case ISD::SEXTLOAD: {
3422     // Make sure we generate both values.
3423     if (Result != 1)
3424       ExprMap[N.getValue(1)] = 1;   // Generate the token
3425     else
3426       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
3427
3428     X86AddressMode AM;
3429     if (getRegPressure(Node->getOperand(0)) >
3430            getRegPressure(Node->getOperand(1))) {
3431       Select(Node->getOperand(0)); // chain
3432       SelectAddress(Node->getOperand(1), AM);
3433     } else {
3434       SelectAddress(Node->getOperand(1), AM);
3435       Select(Node->getOperand(0)); // chain
3436     }
3437
3438     switch (Node->getValueType(0)) {
3439     case MVT::i8: assert(0 && "Cannot sign extend from bool!");
3440     default: assert(0 && "Unknown type to sign extend to.");
3441     case MVT::i32:
3442       switch (cast<VTSDNode>(Node->getOperand(3))->getVT()) {
3443       default:
3444       case MVT::i1: assert(0 && "Cannot sign extend from bool!");
3445       case MVT::i8:
3446         addFullAddress(BuildMI(BB, X86::MOVSX32rm8, 5, Result), AM);
3447         break;
3448       case MVT::i16:
3449         addFullAddress(BuildMI(BB, X86::MOVSX32rm16, 5, Result), AM);
3450         break;
3451       }
3452       break;
3453     case MVT::i16:
3454       assert(cast<VTSDNode>(Node->getOperand(3))->getVT() == MVT::i8 &&
3455              "Cannot sign extend from bool!");
3456       addFullAddress(BuildMI(BB, X86::MOVSX16rm8, 5, Result), AM);
3457       break;
3458     }
3459     return Result;
3460   }
3461
3462   case ISD::DYNAMIC_STACKALLOC:
3463     // Generate both result values.
3464     if (Result != 1)
3465       ExprMap[N.getValue(1)] = 1;   // Generate the token
3466     else
3467       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
3468
3469     // FIXME: We are currently ignoring the requested alignment for handling
3470     // greater than the stack alignment.  This will need to be revisited at some
3471     // point.  Align = N.getOperand(2);
3472
3473     if (!isa<ConstantSDNode>(N.getOperand(2)) ||
3474         cast<ConstantSDNode>(N.getOperand(2))->getValue() != 0) {
3475       std::cerr << "Cannot allocate stack object with greater alignment than"
3476                 << " the stack alignment yet!";
3477       abort();
3478     }
3479
3480     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
3481       Select(N.getOperand(0));
3482       BuildMI(BB, X86::SUB32ri, 2, X86::ESP).addReg(X86::ESP)
3483         .addImm(CN->getValue());
3484     } else {
3485       if (getRegPressure(N.getOperand(0)) > getRegPressure(N.getOperand(1))) {
3486         Select(N.getOperand(0));
3487         Tmp1 = SelectExpr(N.getOperand(1));
3488       } else {
3489         Tmp1 = SelectExpr(N.getOperand(1));
3490         Select(N.getOperand(0));
3491       }
3492
3493       // Subtract size from stack pointer, thereby allocating some space.
3494       BuildMI(BB, X86::SUB32rr, 2, X86::ESP).addReg(X86::ESP).addReg(Tmp1);
3495     }
3496
3497     // Put a pointer to the space into the result register, by copying the stack
3498     // pointer.
3499     BuildMI(BB, X86::MOV32rr, 1, Result).addReg(X86::ESP);
3500     return Result;
3501
3502   case X86ISD::TAILCALL:
3503   case X86ISD::CALL: {
3504     // The chain for this call is now lowered.
3505     ExprMap.insert(std::make_pair(N.getValue(0), 1));
3506
3507     bool isDirect = isa<GlobalAddressSDNode>(N.getOperand(1)) ||
3508                     isa<ExternalSymbolSDNode>(N.getOperand(1));
3509     unsigned Callee = 0;
3510     if (isDirect) {
3511       Select(N.getOperand(0));
3512     } else {
3513       if (getRegPressure(N.getOperand(0)) > getRegPressure(N.getOperand(1))) {
3514         Select(N.getOperand(0));
3515         Callee = SelectExpr(N.getOperand(1));
3516       } else {
3517         Callee = SelectExpr(N.getOperand(1));
3518         Select(N.getOperand(0));
3519       }
3520     }
3521
3522     // If this call has values to pass in registers, do so now.
3523     if (Node->getNumOperands() > 4) {
3524       // The first value is passed in (a part of) EAX, the second in EDX.
3525       unsigned RegOp1 = SelectExpr(N.getOperand(4));
3526       unsigned RegOp2 =
3527         Node->getNumOperands() > 5 ? SelectExpr(N.getOperand(5)) : 0;
3528
3529       switch (N.getOperand(4).getValueType()) {
3530       default: assert(0 && "Bad thing to pass in regs");
3531       case MVT::i1:
3532       case MVT::i8:  BuildMI(BB, X86::MOV8rr , 1,X86::AL).addReg(RegOp1); break;
3533       case MVT::i16: BuildMI(BB, X86::MOV16rr, 1,X86::AX).addReg(RegOp1); break;
3534       case MVT::i32: BuildMI(BB, X86::MOV32rr, 1,X86::EAX).addReg(RegOp1);break;
3535       }
3536       if (RegOp2)
3537         switch (N.getOperand(5).getValueType()) {
3538         default: assert(0 && "Bad thing to pass in regs");
3539         case MVT::i1:
3540         case MVT::i8:
3541           BuildMI(BB, X86::MOV8rr , 1, X86::DL).addReg(RegOp2);
3542           break;
3543         case MVT::i16:
3544           BuildMI(BB, X86::MOV16rr, 1, X86::DX).addReg(RegOp2);
3545           break;
3546         case MVT::i32:
3547           BuildMI(BB, X86::MOV32rr, 1, X86::EDX).addReg(RegOp2);
3548           break;
3549         }
3550     }
3551
3552     if (GlobalAddressSDNode *GASD =
3553                dyn_cast<GlobalAddressSDNode>(N.getOperand(1))) {
3554       BuildMI(BB, X86::CALLpcrel32, 1).addGlobalAddress(GASD->getGlobal(),true);
3555     } else if (ExternalSymbolSDNode *ESSDN =
3556                dyn_cast<ExternalSymbolSDNode>(N.getOperand(1))) {
3557       BuildMI(BB, X86::CALLpcrel32,
3558               1).addExternalSymbol(ESSDN->getSymbol(), true);
3559     } else {
3560       if (getRegPressure(N.getOperand(0)) > getRegPressure(N.getOperand(1))) {
3561         Select(N.getOperand(0));
3562         Tmp1 = SelectExpr(N.getOperand(1));
3563       } else {
3564         Tmp1 = SelectExpr(N.getOperand(1));
3565         Select(N.getOperand(0));
3566       }
3567
3568       BuildMI(BB, X86::CALL32r, 1).addReg(Tmp1);
3569     }
3570
3571     // Get caller stack amount and amount the callee added to the stack pointer.
3572     Tmp1 = cast<ConstantSDNode>(N.getOperand(2))->getValue();
3573     Tmp2 = cast<ConstantSDNode>(N.getOperand(3))->getValue();
3574     BuildMI(BB, X86::ADJCALLSTACKUP, 2).addImm(Tmp1).addImm(Tmp2);
3575
3576     if (Node->getNumValues() != 1)
3577       switch (Node->getValueType(1)) {
3578       default: assert(0 && "Unknown value type for call result!");
3579       case MVT::Other: return 1;
3580       case MVT::i1:
3581       case MVT::i8:
3582         BuildMI(BB, X86::MOV8rr, 1, Result).addReg(X86::AL);
3583         break;
3584       case MVT::i16:
3585         BuildMI(BB, X86::MOV16rr, 1, Result).addReg(X86::AX);
3586         break;
3587       case MVT::i32:
3588         BuildMI(BB, X86::MOV32rr, 1, Result).addReg(X86::EAX);
3589         if (Node->getNumValues() == 3 && Node->getValueType(2) == MVT::i32)
3590           BuildMI(BB, X86::MOV32rr, 1, Result+1).addReg(X86::EDX);
3591         break;
3592       case MVT::f64:     // Floating-point return values live in %ST(0)
3593         if (X86ScalarSSE) {
3594           ContainsFPCode = true;
3595           BuildMI(BB, X86::FpGETRESULT, 1, X86::FP0);
3596
3597           unsigned Size = MVT::getSizeInBits(MVT::f64)/8;
3598           MachineFunction *F = BB->getParent();
3599           int FrameIdx = F->getFrameInfo()->CreateStackObject(Size, Size);
3600           addFrameReference(BuildMI(BB, X86::FST64m, 5), FrameIdx).addReg(X86::FP0);
3601           addFrameReference(BuildMI(BB, X86::MOVSDrm, 4, Result), FrameIdx);
3602           break;
3603         } else {
3604           ContainsFPCode = true;
3605           BuildMI(BB, X86::FpGETRESULT, 1, Result);
3606           break;
3607         }
3608       }
3609     return Result+N.ResNo-1;
3610   }
3611   case ISD::READPORT:
3612     // First, determine that the size of the operand falls within the acceptable
3613     // range for this architecture.
3614     //
3615     if (Node->getOperand(1).getValueType() != MVT::i16) {
3616       std::cerr << "llvm.readport: Address size is not 16 bits\n";
3617       exit(1);
3618     }
3619
3620     // Make sure we generate both values.
3621     if (Result != 1) {  // Generate the token
3622       if (!ExprMap.insert(std::make_pair(N.getValue(1), 1)).second)
3623         assert(0 && "readport already emitted!?");
3624     } else
3625       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
3626
3627     Select(Node->getOperand(0));  // Select the chain.
3628
3629     // If the port is a single-byte constant, use the immediate form.
3630     if (ConstantSDNode *Port = dyn_cast<ConstantSDNode>(Node->getOperand(1)))
3631       if ((Port->getValue() & 255) == Port->getValue()) {
3632         switch (Node->getValueType(0)) {
3633         case MVT::i8:
3634           BuildMI(BB, X86::IN8ri, 1).addImm(Port->getValue());
3635           BuildMI(BB, X86::MOV8rr, 1, Result).addReg(X86::AL);
3636           return Result;
3637         case MVT::i16:
3638           BuildMI(BB, X86::IN16ri, 1).addImm(Port->getValue());
3639           BuildMI(BB, X86::MOV16rr, 1, Result).addReg(X86::AX);
3640           return Result;
3641         case MVT::i32:
3642           BuildMI(BB, X86::IN32ri, 1).addImm(Port->getValue());
3643           BuildMI(BB, X86::MOV32rr, 1, Result).addReg(X86::EAX);
3644           return Result;
3645         default: break;
3646         }
3647       }
3648
3649     // Now, move the I/O port address into the DX register and use the IN
3650     // instruction to get the input data.
3651     //
3652     Tmp1 = SelectExpr(Node->getOperand(1));
3653     BuildMI(BB, X86::MOV16rr, 1, X86::DX).addReg(Tmp1);
3654     switch (Node->getValueType(0)) {
3655     case MVT::i8:
3656       BuildMI(BB, X86::IN8rr, 0);
3657       BuildMI(BB, X86::MOV8rr, 1, Result).addReg(X86::AL);
3658       return Result;
3659     case MVT::i16:
3660       BuildMI(BB, X86::IN16rr, 0);
3661       BuildMI(BB, X86::MOV16rr, 1, Result).addReg(X86::AX);
3662       return Result;
3663     case MVT::i32:
3664       BuildMI(BB, X86::IN32rr, 0);
3665       BuildMI(BB, X86::MOV32rr, 1, Result).addReg(X86::EAX);
3666       return Result;
3667     default:
3668       std::cerr << "Cannot do input on this data type";
3669       exit(1);
3670     }
3671
3672   }
3673
3674   return 0;
3675 }
3676
3677 /// TryToFoldLoadOpStore - Given a store node, try to fold together a
3678 /// load/op/store instruction.  If successful return true.
3679 bool ISel::TryToFoldLoadOpStore(SDNode *Node) {
3680   assert(Node->getOpcode() == ISD::STORE && "Can only do this for stores!");
3681   SDOperand Chain  = Node->getOperand(0);
3682   SDOperand StVal  = Node->getOperand(1);
3683   SDOperand StPtr  = Node->getOperand(2);
3684
3685   // The chain has to be a load, the stored value must be an integer binary
3686   // operation with one use.
3687   if (!StVal.Val->hasOneUse() || StVal.Val->getNumOperands() != 2 ||
3688       MVT::isFloatingPoint(StVal.getValueType()))
3689     return false;
3690
3691   // Token chain must either be a factor node or the load to fold.
3692   if (Chain.getOpcode() != ISD::LOAD && Chain.getOpcode() != ISD::TokenFactor)
3693     return false;
3694
3695   SDOperand TheLoad;
3696
3697   // Check to see if there is a load from the same pointer that we're storing
3698   // to in either operand of the binop.
3699   if (StVal.getOperand(0).getOpcode() == ISD::LOAD &&
3700       StVal.getOperand(0).getOperand(1) == StPtr)
3701     TheLoad = StVal.getOperand(0);
3702   else if (StVal.getOperand(1).getOpcode() == ISD::LOAD &&
3703            StVal.getOperand(1).getOperand(1) == StPtr)
3704     TheLoad = StVal.getOperand(1);
3705   else
3706     return false;  // No matching load operand.
3707
3708   // We can only fold the load if there are no intervening side-effecting
3709   // operations.  This means that the store uses the load as its token chain, or
3710   // there are only token factor nodes in between the store and load.
3711   if (Chain != TheLoad.getValue(1)) {
3712     // Okay, the other option is that we have a store referring to (possibly
3713     // nested) token factor nodes.  For now, just try peeking through one level
3714     // of token factors to see if this is the case.
3715     bool ChainOk = false;
3716     if (Chain.getOpcode() == ISD::TokenFactor) {
3717       for (unsigned i = 0, e = Chain.getNumOperands(); i != e; ++i)
3718         if (Chain.getOperand(i) == TheLoad.getValue(1)) {
3719           ChainOk = true;
3720           break;
3721         }
3722     }
3723
3724     if (!ChainOk) return false;
3725   }
3726
3727   if (TheLoad.getOperand(1) != StPtr)
3728     return false;
3729
3730   // Make sure that one of the operands of the binop is the load, and that the
3731   // load folds into the binop.
3732   if (((StVal.getOperand(0) != TheLoad ||
3733         !isFoldableLoad(TheLoad, StVal.getOperand(1))) &&
3734        (StVal.getOperand(1) != TheLoad ||
3735         !isFoldableLoad(TheLoad, StVal.getOperand(0)))))
3736     return false;
3737
3738   // Finally, check to see if this is one of the ops we can handle!
3739   static const unsigned ADDTAB[] = {
3740     X86::ADD8mi, X86::ADD16mi, X86::ADD32mi,
3741     X86::ADD8mr, X86::ADD16mr, X86::ADD32mr,
3742   };
3743   static const unsigned SUBTAB[] = {
3744     X86::SUB8mi, X86::SUB16mi, X86::SUB32mi,
3745     X86::SUB8mr, X86::SUB16mr, X86::SUB32mr,
3746   };
3747   static const unsigned ANDTAB[] = {
3748     X86::AND8mi, X86::AND16mi, X86::AND32mi,
3749     X86::AND8mr, X86::AND16mr, X86::AND32mr,
3750   };
3751   static const unsigned ORTAB[] = {
3752     X86::OR8mi, X86::OR16mi, X86::OR32mi,
3753     X86::OR8mr, X86::OR16mr, X86::OR32mr,
3754   };
3755   static const unsigned XORTAB[] = {
3756     X86::XOR8mi, X86::XOR16mi, X86::XOR32mi,
3757     X86::XOR8mr, X86::XOR16mr, X86::XOR32mr,
3758   };
3759   static const unsigned SHLTAB[] = {
3760     X86::SHL8mi, X86::SHL16mi, X86::SHL32mi,
3761     /*Have to put the reg in CL*/0, 0, 0,
3762   };
3763   static const unsigned SARTAB[] = {
3764     X86::SAR8mi, X86::SAR16mi, X86::SAR32mi,
3765     /*Have to put the reg in CL*/0, 0, 0,
3766   };
3767   static const unsigned SHRTAB[] = {
3768     X86::SHR8mi, X86::SHR16mi, X86::SHR32mi,
3769     /*Have to put the reg in CL*/0, 0, 0,
3770   };
3771
3772   const unsigned *TabPtr = 0;
3773   switch (StVal.getOpcode()) {
3774   default:
3775     std::cerr << "CANNOT [mem] op= val: ";
3776     StVal.Val->dump(); std::cerr << "\n";
3777   case ISD::MUL:
3778   case ISD::SDIV:
3779   case ISD::UDIV:
3780   case ISD::SREM:
3781   case ISD::UREM: return false;
3782
3783   case ISD::ADD: TabPtr = ADDTAB; break;
3784   case ISD::SUB: TabPtr = SUBTAB; break;
3785   case ISD::AND: TabPtr = ANDTAB; break;
3786   case ISD:: OR: TabPtr =  ORTAB; break;
3787   case ISD::XOR: TabPtr = XORTAB; break;
3788   case ISD::SHL: TabPtr = SHLTAB; break;
3789   case ISD::SRA: TabPtr = SARTAB; break;
3790   case ISD::SRL: TabPtr = SHRTAB; break;
3791   }
3792
3793   // Handle: [mem] op= CST
3794   SDOperand Op0 = StVal.getOperand(0);
3795   SDOperand Op1 = StVal.getOperand(1);
3796   unsigned Opc = 0;
3797   if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Op1)) {
3798     switch (Op0.getValueType()) { // Use Op0's type because of shifts.
3799     default: break;
3800     case MVT::i1:
3801     case MVT::i8:  Opc = TabPtr[0]; break;
3802     case MVT::i16: Opc = TabPtr[1]; break;
3803     case MVT::i32: Opc = TabPtr[2]; break;
3804     }
3805
3806     if (Opc) {
3807       if (!ExprMap.insert(std::make_pair(TheLoad.getValue(1), 1)).second)
3808         assert(0 && "Already emitted?");
3809       Select(Chain);
3810
3811       X86AddressMode AM;
3812       if (getRegPressure(TheLoad.getOperand(0)) >
3813           getRegPressure(TheLoad.getOperand(1))) {
3814         Select(TheLoad.getOperand(0));
3815         SelectAddress(TheLoad.getOperand(1), AM);
3816       } else {
3817         SelectAddress(TheLoad.getOperand(1), AM);
3818         Select(TheLoad.getOperand(0));
3819       }
3820
3821       if (StVal.getOpcode() == ISD::ADD) {
3822         if (CN->getValue() == 1) {
3823           switch (Op0.getValueType()) {
3824           default: break;
3825           case MVT::i8:
3826             addFullAddress(BuildMI(BB, X86::INC8m, 4), AM);
3827             return true;
3828           case MVT::i16: Opc = TabPtr[1];
3829             addFullAddress(BuildMI(BB, X86::INC16m, 4), AM);
3830             return true;
3831           case MVT::i32: Opc = TabPtr[2];
3832             addFullAddress(BuildMI(BB, X86::INC32m, 4), AM);
3833             return true;
3834           }
3835         } else if (CN->getValue()+1 == 0) {   // [X] += -1 -> DEC [X]
3836           switch (Op0.getValueType()) {
3837           default: break;
3838           case MVT::i8:
3839             addFullAddress(BuildMI(BB, X86::DEC8m, 4), AM);
3840             return true;
3841           case MVT::i16: Opc = TabPtr[1];
3842             addFullAddress(BuildMI(BB, X86::DEC16m, 4), AM);
3843             return true;
3844           case MVT::i32: Opc = TabPtr[2];
3845             addFullAddress(BuildMI(BB, X86::DEC32m, 4), AM);
3846             return true;
3847           }
3848         }
3849       }
3850
3851       addFullAddress(BuildMI(BB, Opc, 4+1),AM).addImm(CN->getValue());
3852       return true;
3853     }
3854   }
3855
3856   // If we have [mem] = V op [mem], try to turn it into:
3857   // [mem] = [mem] op V.
3858   if (Op1 == TheLoad && StVal.getOpcode() != ISD::SUB &&
3859       StVal.getOpcode() != ISD::SHL && StVal.getOpcode() != ISD::SRA &&
3860       StVal.getOpcode() != ISD::SRL)
3861     std::swap(Op0, Op1);
3862
3863   if (Op0 != TheLoad) return false;
3864
3865   switch (Op0.getValueType()) {
3866   default: return false;
3867   case MVT::i1:
3868   case MVT::i8:  Opc = TabPtr[3]; break;
3869   case MVT::i16: Opc = TabPtr[4]; break;
3870   case MVT::i32: Opc = TabPtr[5]; break;
3871   }
3872
3873   // Table entry doesn't exist?
3874   if (Opc == 0) return false;
3875
3876   if (!ExprMap.insert(std::make_pair(TheLoad.getValue(1), 1)).second)
3877     assert(0 && "Already emitted?");
3878   Select(Chain);
3879   Select(TheLoad.getOperand(0));
3880
3881   X86AddressMode AM;
3882   SelectAddress(TheLoad.getOperand(1), AM);
3883   unsigned Reg = SelectExpr(Op1);
3884   addFullAddress(BuildMI(BB, Opc, 4+1), AM).addReg(Reg);
3885   return true;
3886 }
3887
3888 /// If node is a ret(tailcall) node, emit the specified tail call and return
3889 /// true, otherwise return false.
3890 ///
3891 /// FIXME: This whole thing should be a post-legalize optimization pass which
3892 /// recognizes and transforms the dag.  We don't want the selection phase doing
3893 /// this stuff!!
3894 ///
3895 bool ISel::EmitPotentialTailCall(SDNode *RetNode) {
3896   assert(RetNode->getOpcode() == ISD::RET && "Not a return");
3897
3898   SDOperand Chain = RetNode->getOperand(0);
3899
3900   // If this is a token factor node where one operand is a call, dig into it.
3901   SDOperand TokFactor;
3902   unsigned TokFactorOperand = 0;
3903   if (Chain.getOpcode() == ISD::TokenFactor) {
3904     for (unsigned i = 0, e = Chain.getNumOperands(); i != e; ++i)
3905       if (Chain.getOperand(i).getOpcode() == ISD::CALLSEQ_END ||
3906           Chain.getOperand(i).getOpcode() == X86ISD::TAILCALL) {
3907         TokFactorOperand = i;
3908         TokFactor = Chain;
3909         Chain = Chain.getOperand(i);
3910         break;
3911       }
3912     if (TokFactor.Val == 0) return false;  // No call operand.
3913   }
3914
3915   // Skip the CALLSEQ_END node if present.
3916   if (Chain.getOpcode() == ISD::CALLSEQ_END)
3917     Chain = Chain.getOperand(0);
3918
3919   // Is a tailcall the last control operation that occurs before the return?
3920   if (Chain.getOpcode() != X86ISD::TAILCALL)
3921     return false;
3922
3923   // If we return a value, is it the value produced by the call?
3924   if (RetNode->getNumOperands() > 1) {
3925     // Not returning the ret val of the call?
3926     if (Chain.Val->getNumValues() == 1 ||
3927         RetNode->getOperand(1) != Chain.getValue(1))
3928       return false;
3929
3930     if (RetNode->getNumOperands() > 2) {
3931       if (Chain.Val->getNumValues() == 2 ||
3932           RetNode->getOperand(2) != Chain.getValue(2))
3933         return false;
3934     }
3935     assert(RetNode->getNumOperands() <= 3);
3936   }
3937
3938   // CalleeCallArgAmt - The total number of bytes used for the callee arg area.
3939   // For FastCC, this will always be > 0.
3940   unsigned CalleeCallArgAmt =
3941     cast<ConstantSDNode>(Chain.getOperand(2))->getValue();
3942
3943   // CalleeCallArgPopAmt - The number of bytes in the call area popped by the
3944   // callee.  For FastCC this will always be > 0, for CCC this is always 0.
3945   unsigned CalleeCallArgPopAmt =
3946     cast<ConstantSDNode>(Chain.getOperand(3))->getValue();
3947
3948   // There are several cases we can handle here.  First, if the caller and
3949   // callee are both CCC functions, we can tailcall if the callee takes <= the
3950   // number of argument bytes that the caller does.
3951   if (CalleeCallArgPopAmt == 0 &&                  // Callee is C CallingConv?
3952       X86Lowering.getBytesToPopOnReturn() == 0) {  // Caller is C CallingConv?
3953     // Check to see if caller arg area size >= callee arg area size.
3954     if (X86Lowering.getBytesCallerReserves() >= CalleeCallArgAmt) {
3955       //std::cerr << "CCC TAILCALL UNIMP!\n";
3956       // If TokFactor is non-null, emit all operands.
3957
3958       //EmitCCCToCCCTailCall(Chain.Val);
3959       //return true;
3960     }
3961     return false;
3962   }
3963
3964   // Second, if both are FastCC functions, we can always perform the tail call.
3965   if (CalleeCallArgPopAmt && X86Lowering.getBytesToPopOnReturn()) {
3966     // If TokFactor is non-null, emit all operands before the call.
3967     if (TokFactor.Val) {
3968       for (unsigned i = 0, e = TokFactor.getNumOperands(); i != e; ++i)
3969         if (i != TokFactorOperand)
3970           Select(TokFactor.getOperand(i));
3971     }
3972
3973     EmitFastCCToFastCCTailCall(Chain.Val);
3974     return true;
3975   }
3976
3977   // We don't support mixed calls, due to issues with alignment.  We could in
3978   // theory handle some mixed calls from CCC -> FastCC if the stack is properly
3979   // aligned (which depends on the number of arguments to the callee).  TODO.
3980   return false;
3981 }
3982
3983 static SDOperand GetAdjustedArgumentStores(SDOperand Chain, int Offset,
3984                                            SelectionDAG &DAG) {
3985   MVT::ValueType StoreVT;
3986   switch (Chain.getOpcode()) {
3987   case ISD::CALLSEQ_START:
3988     // If we found the start of the call sequence, we're done.  We actually
3989     // strip off the CALLSEQ_START node, to avoid generating the
3990     // ADJCALLSTACKDOWN marker for the tail call.
3991     return Chain.getOperand(0);
3992   case ISD::TokenFactor: {
3993     std::vector<SDOperand> Ops;
3994     Ops.reserve(Chain.getNumOperands());
3995     for (unsigned i = 0, e = Chain.getNumOperands(); i != e; ++i)
3996       Ops.push_back(GetAdjustedArgumentStores(Chain.getOperand(i), Offset,DAG));
3997     return DAG.getNode(ISD::TokenFactor, MVT::Other, Ops);
3998   }
3999   case ISD::STORE:       // Normal store
4000     StoreVT = Chain.getOperand(1).getValueType();
4001     break;
4002   case ISD::TRUNCSTORE:  // FLOAT store
4003     StoreVT = cast<VTSDNode>(Chain.getOperand(4))->getVT();
4004     break;
4005   }
4006
4007   SDOperand OrigDest = Chain.getOperand(2);
4008   unsigned OrigOffset;
4009
4010   if (OrigDest.getOpcode() == ISD::CopyFromReg) {
4011     OrigOffset = 0;
4012     assert(cast<RegisterSDNode>(OrigDest.getOperand(1))->getReg() == X86::ESP);
4013   } else {
4014     // We expect only (ESP+C)
4015     assert(OrigDest.getOpcode() == ISD::ADD &&
4016            isa<ConstantSDNode>(OrigDest.getOperand(1)) &&
4017            OrigDest.getOperand(0).getOpcode() == ISD::CopyFromReg &&
4018            cast<RegisterSDNode>(OrigDest.getOperand(0).getOperand(1))->getReg()
4019                  == X86::ESP);
4020     OrigOffset = cast<ConstantSDNode>(OrigDest.getOperand(1))->getValue();
4021   }
4022
4023   // Compute the new offset from the incoming ESP value we wish to use.
4024   unsigned NewOffset = OrigOffset + Offset;
4025
4026   unsigned OpSize = (MVT::getSizeInBits(StoreVT)+7)/8;  // Bits -> Bytes
4027   MachineFunction &MF = DAG.getMachineFunction();
4028   int FI = MF.getFrameInfo()->CreateFixedObject(OpSize, NewOffset);
4029   SDOperand FIN = DAG.getFrameIndex(FI, MVT::i32);
4030
4031   SDOperand InChain = GetAdjustedArgumentStores(Chain.getOperand(0), Offset,
4032                                                 DAG);
4033   if (Chain.getOpcode() == ISD::STORE)
4034     return DAG.getNode(ISD::STORE, MVT::Other, InChain, Chain.getOperand(1),
4035                        FIN);
4036   assert(Chain.getOpcode() == ISD::TRUNCSTORE);
4037   return DAG.getNode(ISD::TRUNCSTORE, MVT::Other, InChain, Chain.getOperand(1),
4038                      FIN, DAG.getSrcValue(NULL), DAG.getValueType(StoreVT));
4039 }
4040
4041
4042 /// EmitFastCCToFastCCTailCall - Given a tailcall in the tail position to a
4043 /// fastcc function from a fastcc function, emit the code to emit a 'proper'
4044 /// tail call.
4045 void ISel::EmitFastCCToFastCCTailCall(SDNode *TailCallNode) {
4046   unsigned CalleeCallArgSize =
4047     cast<ConstantSDNode>(TailCallNode->getOperand(2))->getValue();
4048   unsigned CallerArgSize = X86Lowering.getBytesToPopOnReturn();
4049
4050   //std::cerr << "****\n*** EMITTING TAIL CALL!\n****\n";
4051
4052   // Adjust argument stores.  Instead of storing to [ESP], f.e., store to frame
4053   // indexes that are relative to the incoming ESP.  If the incoming and
4054   // outgoing arg sizes are the same we will store to [InESP] instead of
4055   // [CurESP] and the ESP referenced will be relative to the incoming function
4056   // ESP.
4057   int ESPOffset = CallerArgSize-CalleeCallArgSize;
4058   SDOperand AdjustedArgStores =
4059     GetAdjustedArgumentStores(TailCallNode->getOperand(0), ESPOffset, *TheDAG);
4060
4061   // Copy the return address of the caller into a virtual register so we don't
4062   // clobber it.
4063   SDOperand RetVal;
4064   if (ESPOffset) {
4065     SDOperand RetValAddr = X86Lowering.getReturnAddressFrameIndex(*TheDAG);
4066     RetVal = TheDAG->getLoad(MVT::i32, TheDAG->getEntryNode(),
4067                                        RetValAddr, TheDAG->getSrcValue(NULL));
4068     SelectExpr(RetVal);
4069   }
4070
4071   // Codegen all of the argument stores.
4072   Select(AdjustedArgStores);
4073
4074   if (RetVal.Val) {
4075     // Emit a store of the saved ret value to the new location.
4076     MachineFunction &MF = TheDAG->getMachineFunction();
4077     int ReturnAddrFI = MF.getFrameInfo()->CreateFixedObject(4, ESPOffset-4);
4078     SDOperand RetValAddr = TheDAG->getFrameIndex(ReturnAddrFI, MVT::i32);
4079     Select(TheDAG->getNode(ISD::STORE, MVT::Other, TheDAG->getEntryNode(),
4080                            RetVal, RetValAddr));
4081   }
4082
4083   // Get the destination value.
4084   SDOperand Callee = TailCallNode->getOperand(1);
4085   bool isDirect = isa<GlobalAddressSDNode>(Callee) ||
4086                   isa<ExternalSymbolSDNode>(Callee);
4087   unsigned CalleeReg = 0;
4088   if (!isDirect) CalleeReg = SelectExpr(Callee);
4089
4090   unsigned RegOp1 = 0;
4091   unsigned RegOp2 = 0;
4092
4093   if (TailCallNode->getNumOperands() > 4) {
4094     // The first value is passed in (a part of) EAX, the second in EDX.
4095     RegOp1 = SelectExpr(TailCallNode->getOperand(4));
4096     if (TailCallNode->getNumOperands() > 5)
4097       RegOp2 = SelectExpr(TailCallNode->getOperand(5));
4098
4099     switch (TailCallNode->getOperand(4).getValueType()) {
4100     default: assert(0 && "Bad thing to pass in regs");
4101     case MVT::i1:
4102     case MVT::i8:
4103       BuildMI(BB, X86::MOV8rr, 1, X86::AL).addReg(RegOp1);
4104       RegOp1 = X86::AL;
4105       break;
4106     case MVT::i16:
4107       BuildMI(BB, X86::MOV16rr, 1,X86::AX).addReg(RegOp1);
4108       RegOp1 = X86::AX;
4109       break;
4110     case MVT::i32:
4111       BuildMI(BB, X86::MOV32rr, 1,X86::EAX).addReg(RegOp1);
4112       RegOp1 = X86::EAX;
4113       break;
4114     }
4115     if (RegOp2)
4116       switch (TailCallNode->getOperand(5).getValueType()) {
4117       default: assert(0 && "Bad thing to pass in regs");
4118       case MVT::i1:
4119       case MVT::i8:
4120         BuildMI(BB, X86::MOV8rr, 1, X86::DL).addReg(RegOp2);
4121         RegOp2 = X86::DL;
4122         break;
4123       case MVT::i16:
4124         BuildMI(BB, X86::MOV16rr, 1, X86::DX).addReg(RegOp2);
4125         RegOp2 = X86::DX;
4126         break;
4127       case MVT::i32:
4128         BuildMI(BB, X86::MOV32rr, 1, X86::EDX).addReg(RegOp2);
4129         RegOp2 = X86::EDX;
4130         break;
4131       }
4132   }
4133
4134   // Adjust ESP.
4135   if (ESPOffset)
4136     BuildMI(BB, X86::ADJSTACKPTRri, 2,
4137             X86::ESP).addReg(X86::ESP).addImm(ESPOffset);
4138
4139   // TODO: handle jmp [mem]
4140   if (!isDirect) {
4141     BuildMI(BB, X86::TAILJMPr, 1).addReg(CalleeReg);
4142   } else if (GlobalAddressSDNode *GASD = dyn_cast<GlobalAddressSDNode>(Callee)){
4143     BuildMI(BB, X86::TAILJMPd, 1).addGlobalAddress(GASD->getGlobal(), true);
4144   } else {
4145     ExternalSymbolSDNode *ESSDN = cast<ExternalSymbolSDNode>(Callee);
4146     BuildMI(BB, X86::TAILJMPd, 1).addExternalSymbol(ESSDN->getSymbol(), true);
4147   }
4148   // ADD IMPLICIT USE RegOp1/RegOp2's
4149 }
4150
4151
4152 void ISel::Select(SDOperand N) {
4153   unsigned Tmp1, Tmp2, Opc;
4154
4155   if (!ExprMap.insert(std::make_pair(N, 1)).second)
4156     return;  // Already selected.
4157
4158   SDNode *Node = N.Val;
4159
4160   switch (Node->getOpcode()) {
4161   default:
4162     Node->dump(); std::cerr << "\n";
4163     assert(0 && "Node not handled yet!");
4164   case ISD::EntryToken: return;  // Noop
4165   case ISD::TokenFactor:
4166     if (Node->getNumOperands() == 2) {
4167       bool OneFirst =
4168         getRegPressure(Node->getOperand(1))>getRegPressure(Node->getOperand(0));
4169       Select(Node->getOperand(OneFirst));
4170       Select(Node->getOperand(!OneFirst));
4171     } else {
4172       std::vector<std::pair<unsigned, unsigned> > OpsP;
4173       for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
4174         OpsP.push_back(std::make_pair(getRegPressure(Node->getOperand(i)), i));
4175       std::sort(OpsP.begin(), OpsP.end());
4176       std::reverse(OpsP.begin(), OpsP.end());
4177       for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
4178         Select(Node->getOperand(OpsP[i].second));
4179     }
4180     return;
4181   case ISD::CopyToReg:
4182     if (getRegPressure(N.getOperand(0)) > getRegPressure(N.getOperand(2))) {
4183       Select(N.getOperand(0));
4184       Tmp1 = SelectExpr(N.getOperand(2));
4185     } else {
4186       Tmp1 = SelectExpr(N.getOperand(2));
4187       Select(N.getOperand(0));
4188     }
4189     Tmp2 = cast<RegisterSDNode>(N.getOperand(1))->getReg();
4190
4191     if (Tmp1 != Tmp2) {
4192       switch (N.getOperand(2).getValueType()) {
4193       default: assert(0 && "Invalid type for operation!");
4194       case MVT::i1:
4195       case MVT::i8:  Opc = X86::MOV8rr; break;
4196       case MVT::i16: Opc = X86::MOV16rr; break;
4197       case MVT::i32: Opc = X86::MOV32rr; break;
4198       case MVT::f32: Opc = X86::MOVAPSrr; break;
4199       case MVT::f64:
4200         if (X86ScalarSSE) {
4201           Opc = X86::MOVAPDrr;
4202         } else {
4203           Opc = X86::FpMOV;
4204           ContainsFPCode = true;
4205         }
4206         break;
4207       }
4208       BuildMI(BB, Opc, 1, Tmp2).addReg(Tmp1);
4209     }
4210     return;
4211   case ISD::RET:
4212     if (N.getOperand(0).getOpcode() == ISD::CALLSEQ_END ||
4213         N.getOperand(0).getOpcode() == X86ISD::TAILCALL ||
4214         N.getOperand(0).getOpcode() == ISD::TokenFactor)
4215       if (EmitPotentialTailCall(Node))
4216         return;
4217
4218     switch (N.getNumOperands()) {
4219     default:
4220       assert(0 && "Unknown return instruction!");
4221     case 3:
4222       assert(N.getOperand(1).getValueType() == MVT::i32 &&
4223              N.getOperand(2).getValueType() == MVT::i32 &&
4224              "Unknown two-register value!");
4225       if (getRegPressure(N.getOperand(1)) > getRegPressure(N.getOperand(2))) {
4226         Tmp1 = SelectExpr(N.getOperand(1));
4227         Tmp2 = SelectExpr(N.getOperand(2));
4228       } else {
4229         Tmp2 = SelectExpr(N.getOperand(2));
4230         Tmp1 = SelectExpr(N.getOperand(1));
4231       }
4232       Select(N.getOperand(0));
4233
4234       BuildMI(BB, X86::MOV32rr, 1, X86::EAX).addReg(Tmp1);
4235       BuildMI(BB, X86::MOV32rr, 1, X86::EDX).addReg(Tmp2);
4236       break;
4237     case 2:
4238       if (getRegPressure(N.getOperand(0)) > getRegPressure(N.getOperand(1))) {
4239         Select(N.getOperand(0));
4240         Tmp1 = SelectExpr(N.getOperand(1));
4241       } else {
4242         Tmp1 = SelectExpr(N.getOperand(1));
4243         Select(N.getOperand(0));
4244       }
4245       switch (N.getOperand(1).getValueType()) {
4246       default: assert(0 && "All other types should have been promoted!!");
4247       case MVT::f32:
4248         if (X86ScalarSSE) {
4249           // Spill the value to memory and reload it into top of stack.
4250           unsigned Size = MVT::getSizeInBits(MVT::f32)/8;
4251           MachineFunction *F = BB->getParent();
4252           int FrameIdx = F->getFrameInfo()->CreateStackObject(Size, Size);
4253           addFrameReference(BuildMI(BB, X86::MOVSSmr, 5), FrameIdx).addReg(Tmp1);
4254           addFrameReference(BuildMI(BB, X86::FLD32m, 4, X86::FP0), FrameIdx);
4255           BuildMI(BB, X86::FpSETRESULT, 1).addReg(X86::FP0);
4256           ContainsFPCode = true;
4257         } else {
4258           assert(0 && "MVT::f32 only legal with scalar sse fp");
4259           abort();
4260         }
4261         break;
4262       case MVT::f64:
4263         if (X86ScalarSSE) {
4264           // Spill the value to memory and reload it into top of stack.
4265           unsigned Size = MVT::getSizeInBits(MVT::f64)/8;
4266           MachineFunction *F = BB->getParent();
4267           int FrameIdx = F->getFrameInfo()->CreateStackObject(Size, Size);
4268           addFrameReference(BuildMI(BB, X86::MOVSDmr, 5), FrameIdx).addReg(Tmp1);
4269           addFrameReference(BuildMI(BB, X86::FLD64m, 4, X86::FP0), FrameIdx);
4270           BuildMI(BB, X86::FpSETRESULT, 1).addReg(X86::FP0);
4271           ContainsFPCode = true;
4272         } else {
4273           BuildMI(BB, X86::FpSETRESULT, 1).addReg(Tmp1);
4274         }
4275         break;
4276       case MVT::i32:
4277         BuildMI(BB, X86::MOV32rr, 1, X86::EAX).addReg(Tmp1);
4278         break;
4279       }
4280       break;
4281     case 1:
4282       Select(N.getOperand(0));
4283       break;
4284     }
4285     if (X86Lowering.getBytesToPopOnReturn() == 0)
4286       BuildMI(BB, X86::RET, 0); // Just emit a 'ret' instruction
4287     else
4288       BuildMI(BB, X86::RETI, 1).addImm(X86Lowering.getBytesToPopOnReturn());
4289     return;
4290   case ISD::BR: {
4291     Select(N.getOperand(0));
4292     MachineBasicBlock *Dest =
4293       cast<BasicBlockSDNode>(N.getOperand(1))->getBasicBlock();
4294     BuildMI(BB, X86::JMP, 1).addMBB(Dest);
4295     return;
4296   }
4297
4298   case ISD::BRCOND: {
4299     MachineBasicBlock *Dest =
4300       cast<BasicBlockSDNode>(N.getOperand(2))->getBasicBlock();
4301
4302     // Try to fold a setcc into the branch.  If this fails, emit a test/jne
4303     // pair.
4304     if (EmitBranchCC(Dest, N.getOperand(0), N.getOperand(1))) {
4305       if (getRegPressure(N.getOperand(0)) > getRegPressure(N.getOperand(1))) {
4306         Select(N.getOperand(0));
4307         Tmp1 = SelectExpr(N.getOperand(1));
4308       } else {
4309         Tmp1 = SelectExpr(N.getOperand(1));
4310         Select(N.getOperand(0));
4311       }
4312       BuildMI(BB, X86::TEST8rr, 2).addReg(Tmp1).addReg(Tmp1);
4313       BuildMI(BB, X86::JNE, 1).addMBB(Dest);
4314     }
4315
4316     return;
4317   }
4318
4319   case ISD::LOAD:
4320     // If this load could be folded into the only using instruction, and if it
4321     // is safe to emit the instruction here, try to do so now.
4322     if (Node->hasNUsesOfValue(1, 0)) {
4323       SDOperand TheVal = N.getValue(0);
4324       SDNode *User = 0;
4325       for (SDNode::use_iterator UI = Node->use_begin(); ; ++UI) {
4326         assert(UI != Node->use_end() && "Didn't find use!");
4327         SDNode *UN = *UI;
4328         for (unsigned i = 0, e = UN->getNumOperands(); i != e; ++i)
4329           if (UN->getOperand(i) == TheVal) {
4330             User = UN;
4331             goto FoundIt;
4332           }
4333       }
4334     FoundIt:
4335       // Only handle unary operators right now.
4336       if (User->getNumOperands() == 1) {
4337         ExprMap.erase(N);
4338         SelectExpr(SDOperand(User, 0));
4339         return;
4340       }
4341     }
4342     ExprMap.erase(N);
4343     SelectExpr(N);
4344     return;
4345   case ISD::READPORT:
4346   case ISD::EXTLOAD:
4347   case ISD::SEXTLOAD:
4348   case ISD::ZEXTLOAD:
4349   case ISD::DYNAMIC_STACKALLOC:
4350   case X86ISD::TAILCALL:
4351   case X86ISD::CALL:
4352     ExprMap.erase(N);
4353     SelectExpr(N);
4354     return;
4355   case ISD::CopyFromReg:
4356   case X86ISD::FILD64m:
4357     ExprMap.erase(N);
4358     SelectExpr(N.getValue(0));
4359     return;
4360
4361   case X86ISD::FP_TO_INT16_IN_MEM:
4362   case X86ISD::FP_TO_INT32_IN_MEM:
4363   case X86ISD::FP_TO_INT64_IN_MEM: {
4364     assert(N.getOperand(1).getValueType() == MVT::f64);
4365     X86AddressMode AM;
4366     Select(N.getOperand(0));   // Select the token chain
4367
4368     unsigned ValReg;
4369     if (getRegPressure(N.getOperand(1)) > getRegPressure(N.getOperand(2))) {
4370       ValReg = SelectExpr(N.getOperand(1));
4371       SelectAddress(N.getOperand(2), AM);
4372      } else {
4373        SelectAddress(N.getOperand(2), AM);
4374        ValReg = SelectExpr(N.getOperand(1));
4375      }
4376
4377     // Change the floating point control register to use "round towards zero"
4378     // mode when truncating to an integer value.
4379     //
4380     MachineFunction *F = BB->getParent();
4381     int CWFrameIdx = F->getFrameInfo()->CreateStackObject(2, 2);
4382     addFrameReference(BuildMI(BB, X86::FNSTCW16m, 4), CWFrameIdx);
4383
4384     // Load the old value of the high byte of the control word...
4385     unsigned OldCW = MakeReg(MVT::i16);
4386     addFrameReference(BuildMI(BB, X86::MOV16rm, 4, OldCW), CWFrameIdx);
4387
4388     // Set the high part to be round to zero...
4389     addFrameReference(BuildMI(BB, X86::MOV16mi, 5), CWFrameIdx).addImm(0xC7F);
4390
4391     // Reload the modified control word now...
4392     addFrameReference(BuildMI(BB, X86::FLDCW16m, 4), CWFrameIdx);
4393
4394     // Restore the memory image of control word to original value
4395     addFrameReference(BuildMI(BB, X86::MOV16mr, 5), CWFrameIdx).addReg(OldCW);
4396
4397     // Get the X86 opcode to use.
4398     switch (N.getOpcode()) {
4399     case X86ISD::FP_TO_INT16_IN_MEM: Tmp1 = X86::FIST16m; break;
4400     case X86ISD::FP_TO_INT32_IN_MEM: Tmp1 = X86::FIST32m; break;
4401     case X86ISD::FP_TO_INT64_IN_MEM: Tmp1 = X86::FISTP64m; break;
4402     }
4403
4404     addFullAddress(BuildMI(BB, Tmp1, 5), AM).addReg(ValReg);
4405
4406     // Reload the original control word now.
4407     addFrameReference(BuildMI(BB, X86::FLDCW16m, 4), CWFrameIdx);
4408     return;
4409   }
4410
4411   case ISD::TRUNCSTORE: {  // truncstore chain, val, ptr, SRCVALUE, storety
4412     X86AddressMode AM;
4413     MVT::ValueType StoredTy = cast<VTSDNode>(N.getOperand(4))->getVT();
4414     assert((StoredTy == MVT::i1 || StoredTy == MVT::f32 ||
4415             StoredTy == MVT::i16 /*FIXME: THIS IS JUST FOR TESTING!*/)
4416            && "Unsupported TRUNCSTORE for this target!");
4417
4418     if (StoredTy == MVT::i16) {
4419       // FIXME: This is here just to allow testing.  X86 doesn't really have a
4420       // TRUNCSTORE i16 operation, but this is required for targets that do not
4421       // have 16-bit integer registers.  We occasionally disable 16-bit integer
4422       // registers to test the promotion code.
4423       Select(N.getOperand(0));
4424       Tmp1 = SelectExpr(N.getOperand(1));
4425       SelectAddress(N.getOperand(2), AM);
4426
4427       BuildMI(BB, X86::MOV32rr, 1, X86::EAX).addReg(Tmp1);
4428       addFullAddress(BuildMI(BB, X86::MOV16mr, 5), AM).addReg(X86::AX);
4429       return;
4430     }
4431
4432     // Store of constant bool?
4433     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
4434       if (getRegPressure(N.getOperand(0)) > getRegPressure(N.getOperand(2))) {
4435         Select(N.getOperand(0));
4436         SelectAddress(N.getOperand(2), AM);
4437       } else {
4438         SelectAddress(N.getOperand(2), AM);
4439         Select(N.getOperand(0));
4440       }
4441       addFullAddress(BuildMI(BB, X86::MOV8mi, 5), AM).addImm(CN->getValue());
4442       return;
4443     }
4444
4445     switch (StoredTy) {
4446     default: assert(0 && "Cannot truncstore this type!");
4447     case MVT::i1: Opc = X86::MOV8mr; break;
4448     case MVT::f32:
4449       assert(!X86ScalarSSE && "Cannot truncstore scalar SSE regs");
4450       Opc = X86::FST32m; break;
4451     }
4452
4453     std::vector<std::pair<unsigned, unsigned> > RP;
4454     RP.push_back(std::make_pair(getRegPressure(N.getOperand(0)), 0));
4455     RP.push_back(std::make_pair(getRegPressure(N.getOperand(1)), 1));
4456     RP.push_back(std::make_pair(getRegPressure(N.getOperand(2)), 2));
4457     std::sort(RP.begin(), RP.end());
4458
4459     Tmp1 = 0;   // Silence a warning.
4460     for (unsigned i = 0; i != 3; ++i)
4461       switch (RP[2-i].second) {
4462       default: assert(0 && "Unknown operand number!");
4463       case 0: Select(N.getOperand(0)); break;
4464       case 1: Tmp1 = SelectExpr(N.getOperand(1)); break;
4465       case 2: SelectAddress(N.getOperand(2), AM); break;
4466       }
4467
4468     addFullAddress(BuildMI(BB, Opc, 4+1), AM).addReg(Tmp1);
4469     return;
4470   }
4471   case ISD::STORE: {
4472     X86AddressMode AM;
4473
4474     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
4475       Opc = 0;
4476       switch (CN->getValueType(0)) {
4477       default: assert(0 && "Invalid type for operation!");
4478       case MVT::i1:
4479       case MVT::i8:  Opc = X86::MOV8mi; break;
4480       case MVT::i16: Opc = X86::MOV16mi; break;
4481       case MVT::i32: Opc = X86::MOV32mi; break;
4482       }
4483       if (Opc) {
4484         if (getRegPressure(N.getOperand(0)) > getRegPressure(N.getOperand(2))) {
4485           Select(N.getOperand(0));
4486           SelectAddress(N.getOperand(2), AM);
4487         } else {
4488           SelectAddress(N.getOperand(2), AM);
4489           Select(N.getOperand(0));
4490         }
4491         addFullAddress(BuildMI(BB, Opc, 4+1), AM).addImm(CN->getValue());
4492         return;
4493       }
4494     } else if (GlobalAddressSDNode *GA =
4495                       dyn_cast<GlobalAddressSDNode>(N.getOperand(1))) {
4496       assert(GA->getValueType(0) == MVT::i32 && "Bad pointer operand");
4497
4498       if (getRegPressure(N.getOperand(0)) > getRegPressure(N.getOperand(2))) {
4499         Select(N.getOperand(0));
4500         SelectAddress(N.getOperand(2), AM);
4501       } else {
4502         SelectAddress(N.getOperand(2), AM);
4503         Select(N.getOperand(0));
4504       }
4505       GlobalValue *GV = GA->getGlobal();
4506       // For Darwin, external and weak symbols are indirect, so we want to load
4507       // the value at address GV, not the value of GV itself.
4508       if (Subtarget->getIndirectExternAndWeakGlobals() &&
4509           (GV->hasWeakLinkage() || GV->isExternal())) {
4510         Tmp1 = MakeReg(MVT::i32);
4511         BuildMI(BB, X86::MOV32rm, 4, Tmp1).addReg(0).addZImm(1).addReg(0)
4512           .addGlobalAddress(GV, false, 0);
4513         addFullAddress(BuildMI(BB, X86::MOV32mr, 4+1),AM).addReg(Tmp1);
4514       } else {
4515         addFullAddress(BuildMI(BB, X86::MOV32mi, 4+1),AM).addGlobalAddress(GV);
4516       }
4517       return;
4518     }
4519
4520     // Check to see if this is a load/op/store combination.
4521     if (TryToFoldLoadOpStore(Node))
4522       return;
4523
4524     switch (N.getOperand(1).getValueType()) {
4525     default: assert(0 && "Cannot store this type!");
4526     case MVT::i1:
4527     case MVT::i8:  Opc = X86::MOV8mr; break;
4528     case MVT::i16: Opc = X86::MOV16mr; break;
4529     case MVT::i32: Opc = X86::MOV32mr; break;
4530     case MVT::f32: Opc = X86::MOVSSmr; break;
4531     case MVT::f64: Opc = X86ScalarSSE ? X86::MOVSDmr : X86::FST64m; break;
4532     }
4533
4534     std::vector<std::pair<unsigned, unsigned> > RP;
4535     RP.push_back(std::make_pair(getRegPressure(N.getOperand(0)), 0));
4536     RP.push_back(std::make_pair(getRegPressure(N.getOperand(1)), 1));
4537     RP.push_back(std::make_pair(getRegPressure(N.getOperand(2)), 2));
4538     std::sort(RP.begin(), RP.end());
4539
4540     Tmp1 = 0; // Silence a warning.
4541     for (unsigned i = 0; i != 3; ++i)
4542       switch (RP[2-i].second) {
4543       default: assert(0 && "Unknown operand number!");
4544       case 0: Select(N.getOperand(0)); break;
4545       case 1: Tmp1 = SelectExpr(N.getOperand(1)); break;
4546       case 2: SelectAddress(N.getOperand(2), AM); break;
4547       }
4548
4549     addFullAddress(BuildMI(BB, Opc, 4+1), AM).addReg(Tmp1);
4550     return;
4551   }
4552   case ISD::CALLSEQ_START:
4553     Select(N.getOperand(0));
4554     // Stack amount
4555     Tmp1 = cast<ConstantSDNode>(N.getOperand(1))->getValue();
4556     BuildMI(BB, X86::ADJCALLSTACKDOWN, 1).addImm(Tmp1);
4557     return;
4558   case ISD::CALLSEQ_END:
4559     Select(N.getOperand(0));
4560     return;
4561   case ISD::MEMSET: {
4562     Select(N.getOperand(0));  // Select the chain.
4563     unsigned Align =
4564       (unsigned)cast<ConstantSDNode>(Node->getOperand(4))->getValue();
4565     if (Align == 0) Align = 1;
4566
4567     // Turn the byte code into # iterations
4568     unsigned CountReg;
4569     unsigned Opcode;
4570     if (ConstantSDNode *ValC = dyn_cast<ConstantSDNode>(Node->getOperand(2))) {
4571       unsigned Val = ValC->getValue() & 255;
4572
4573       // If the value is a constant, then we can potentially use larger sets.
4574       switch (Align & 3) {
4575       case 2:   // WORD aligned
4576         CountReg = MakeReg(MVT::i32);
4577         if (ConstantSDNode *I = dyn_cast<ConstantSDNode>(Node->getOperand(3))) {
4578           BuildMI(BB, X86::MOV32ri, 1, CountReg).addImm(I->getValue()/2);
4579         } else {
4580           unsigned ByteReg = SelectExpr(Node->getOperand(3));
4581           BuildMI(BB, X86::SHR32ri, 2, CountReg).addReg(ByteReg).addImm(1);
4582         }
4583         BuildMI(BB, X86::MOV16ri, 1, X86::AX).addImm((Val << 8) | Val);
4584         Opcode = X86::REP_STOSW;
4585         break;
4586       case 0:   // DWORD aligned
4587         CountReg = MakeReg(MVT::i32);
4588         if (ConstantSDNode *I = dyn_cast<ConstantSDNode>(Node->getOperand(3))) {
4589           BuildMI(BB, X86::MOV32ri, 1, CountReg).addImm(I->getValue()/4);
4590         } else {
4591           unsigned ByteReg = SelectExpr(Node->getOperand(3));
4592           BuildMI(BB, X86::SHR32ri, 2, CountReg).addReg(ByteReg).addImm(2);
4593         }
4594         Val = (Val << 8) | Val;
4595         BuildMI(BB, X86::MOV32ri, 1, X86::EAX).addImm((Val << 16) | Val);
4596         Opcode = X86::REP_STOSD;
4597         break;
4598       default:  // BYTE aligned
4599         CountReg = SelectExpr(Node->getOperand(3));
4600         BuildMI(BB, X86::MOV8ri, 1, X86::AL).addImm(Val);
4601         Opcode = X86::REP_STOSB;
4602         break;
4603       }
4604     } else {
4605       // If it's not a constant value we are storing, just fall back.  We could
4606       // try to be clever to form 16 bit and 32 bit values, but we don't yet.
4607       unsigned ValReg = SelectExpr(Node->getOperand(2));
4608       BuildMI(BB, X86::MOV8rr, 1, X86::AL).addReg(ValReg);
4609       CountReg = SelectExpr(Node->getOperand(3));
4610       Opcode = X86::REP_STOSB;
4611     }
4612
4613     // No matter what the alignment is, we put the source in ESI, the
4614     // destination in EDI, and the count in ECX.
4615     unsigned TmpReg1 = SelectExpr(Node->getOperand(1));
4616     BuildMI(BB, X86::MOV32rr, 1, X86::ECX).addReg(CountReg);
4617     BuildMI(BB, X86::MOV32rr, 1, X86::EDI).addReg(TmpReg1);
4618     BuildMI(BB, Opcode, 0);
4619     return;
4620   }
4621   case ISD::MEMCPY: {
4622     Select(N.getOperand(0));  // Select the chain.
4623     unsigned Align =
4624       (unsigned)cast<ConstantSDNode>(Node->getOperand(4))->getValue();
4625     if (Align == 0) Align = 1;
4626
4627     // Turn the byte code into # iterations
4628     unsigned CountReg;
4629     unsigned Opcode;
4630     switch (Align & 3) {
4631     case 2:   // WORD aligned
4632       CountReg = MakeReg(MVT::i32);
4633       if (ConstantSDNode *I = dyn_cast<ConstantSDNode>(Node->getOperand(3))) {
4634         BuildMI(BB, X86::MOV32ri, 1, CountReg).addImm(I->getValue()/2);
4635       } else {
4636         unsigned ByteReg = SelectExpr(Node->getOperand(3));
4637         BuildMI(BB, X86::SHR32ri, 2, CountReg).addReg(ByteReg).addImm(1);
4638       }
4639       Opcode = X86::REP_MOVSW;
4640       break;
4641     case 0:   // DWORD aligned
4642       CountReg = MakeReg(MVT::i32);
4643       if (ConstantSDNode *I = dyn_cast<ConstantSDNode>(Node->getOperand(3))) {
4644         BuildMI(BB, X86::MOV32ri, 1, CountReg).addImm(I->getValue()/4);
4645       } else {
4646         unsigned ByteReg = SelectExpr(Node->getOperand(3));
4647         BuildMI(BB, X86::SHR32ri, 2, CountReg).addReg(ByteReg).addImm(2);
4648       }
4649       Opcode = X86::REP_MOVSD;
4650       break;
4651     default:  // BYTE aligned
4652       CountReg = SelectExpr(Node->getOperand(3));
4653       Opcode = X86::REP_MOVSB;
4654       break;
4655     }
4656
4657     // No matter what the alignment is, we put the source in ESI, the
4658     // destination in EDI, and the count in ECX.
4659     unsigned TmpReg1 = SelectExpr(Node->getOperand(1));
4660     unsigned TmpReg2 = SelectExpr(Node->getOperand(2));
4661     BuildMI(BB, X86::MOV32rr, 1, X86::ECX).addReg(CountReg);
4662     BuildMI(BB, X86::MOV32rr, 1, X86::EDI).addReg(TmpReg1);
4663     BuildMI(BB, X86::MOV32rr, 1, X86::ESI).addReg(TmpReg2);
4664     BuildMI(BB, Opcode, 0);
4665     return;
4666   }
4667   case ISD::WRITEPORT:
4668     if (Node->getOperand(2).getValueType() != MVT::i16) {
4669       std::cerr << "llvm.writeport: Address size is not 16 bits\n";
4670       exit(1);
4671     }
4672     Select(Node->getOperand(0)); // Emit the chain.
4673
4674     Tmp1 = SelectExpr(Node->getOperand(1));
4675     switch (Node->getOperand(1).getValueType()) {
4676     case MVT::i8:
4677       BuildMI(BB, X86::MOV8rr, 1, X86::AL).addReg(Tmp1);
4678       Tmp2 = X86::OUT8ir;  Opc = X86::OUT8rr;
4679       break;
4680     case MVT::i16:
4681       BuildMI(BB, X86::MOV16rr, 1, X86::AX).addReg(Tmp1);
4682       Tmp2 = X86::OUT16ir; Opc = X86::OUT16rr;
4683       break;
4684     case MVT::i32:
4685       BuildMI(BB, X86::MOV32rr, 1, X86::EAX).addReg(Tmp1);
4686       Tmp2 = X86::OUT32ir; Opc = X86::OUT32rr;
4687       break;
4688     default:
4689       std::cerr << "llvm.writeport: invalid data type for X86 target";
4690       exit(1);
4691     }
4692
4693     // If the port is a single-byte constant, use the immediate form.
4694     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Node->getOperand(2)))
4695       if ((CN->getValue() & 255) == CN->getValue()) {
4696         BuildMI(BB, Tmp2, 1).addImm(CN->getValue());
4697         return;
4698       }
4699
4700     // Otherwise, move the I/O port address into the DX register.
4701     unsigned Reg = SelectExpr(Node->getOperand(2));
4702     BuildMI(BB, X86::MOV16rr, 1, X86::DX).addReg(Reg);
4703     BuildMI(BB, Opc, 0);
4704     return;
4705   }
4706   assert(0 && "Should not be reached!");
4707 }
4708
4709
4710 /// createX86PatternInstructionSelector - This pass converts an LLVM function
4711 /// into a machine code representation using pattern matching and a machine
4712 /// description file.
4713 ///
4714 FunctionPass *llvm::createX86PatternInstructionSelector(TargetMachine &TM) {
4715   return new ISel(TM);
4716 }