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