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