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