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