lib/Target/X86/X86ISelPattern.cpp

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