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