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