lib/Target/X86/X86ISelPattern.cpp

   1 //===-- X86ISelPattern.cpp - A pattern matching inst selector for X86 -----===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines a pattern matching instruction selector for X86.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "X86.h"
  15 #include "X86InstrBuilder.h"
  16 #include "X86RegisterInfo.h"
  17 #include "llvm/Constants.h"                   // FIXME: REMOVE
  18 #include "llvm/Function.h"
  19 #include "llvm/CodeGen/MachineConstantPool.h" // FIXME: REMOVE
  20 #include "llvm/CodeGen/MachineFunction.h"
  21 #include "llvm/CodeGen/MachineFrameInfo.h"
  22 #include "llvm/CodeGen/SelectionDAG.h"
  23 #include "llvm/CodeGen/SelectionDAGISel.h"
  24 #include "llvm/CodeGen/SSARegMap.h"
  25 #include "llvm/Target/TargetData.h"
  26 #include "llvm/Target/TargetLowering.h"
  27 #include "llvm/Support/MathExtras.h"
  28 #include "llvm/ADT/Statistic.h"
  29 #include <set>
  30 using namespace llvm;
  31
  32 //===----------------------------------------------------------------------===//
  33 //  X86TargetLowering - X86 Implementation of the TargetLowering interface
  34 namespace {
  35   class X86TargetLowering : public TargetLowering {
  36     int VarArgsFrameIndex;            // FrameIndex for start of varargs area.
  37     int ReturnAddrIndex;              // FrameIndex for return slot.
  38   public:
  39     X86TargetLowering(TargetMachine &TM) : TargetLowering(TM) {
  40       // Set up the TargetLowering object.
  41       addRegisterClass(MVT::i8, X86::R8RegisterClass);
  42       addRegisterClass(MVT::i16, X86::R16RegisterClass);
  43       addRegisterClass(MVT::i32, X86::R32RegisterClass);
  44       addRegisterClass(MVT::f64, X86::RFPRegisterClass);
  45
  46       // FIXME: Eliminate these two classes when legalize can handle promotions
  47       // well.
  48       addRegisterClass(MVT::i1, X86::R8RegisterClass);
  49       addRegisterClass(MVT::f32, X86::RFPRegisterClass);
  50
  51       computeRegisterProperties();
  52
  53       setOperationUnsupported(ISD::MEMMOVE, MVT::Other);
  54
  55       setOperationUnsupported(ISD::MUL, MVT::i8);
  56       setOperationUnsupported(ISD::SELECT, MVT::i1);
  57       setOperationUnsupported(ISD::SELECT, MVT::i8);
  58
  59       addLegalFPImmediate(+0.0); // FLD0
  60       addLegalFPImmediate(+1.0); // FLD1
  61       addLegalFPImmediate(-0.0); // FLD0/FCHS
  62       addLegalFPImmediate(-1.0); // FLD1/FCHS
  63     }
  64
  65     /// LowerArguments - This hook must be implemented to indicate how we should
  66     /// lower the arguments for the specified function, into the specified DAG.
  67     virtual std::vector<SDOperand>
  68     LowerArguments(Function &F, SelectionDAG &DAG);
  69
  70     /// LowerCallTo - This hook lowers an abstract call to a function into an
  71     /// actual call.
  72     virtual std::pair<SDOperand, SDOperand>
  73     LowerCallTo(SDOperand Chain, const Type *RetTy, SDOperand Callee,
  74                 ArgListTy &Args, SelectionDAG &DAG);
  75
  76     virtual std::pair<SDOperand, SDOperand>
  77     LowerVAStart(SDOperand Chain, SelectionDAG &DAG);
  78
  79     virtual std::pair<SDOperand,SDOperand>
  80     LowerVAArgNext(bool isVANext, SDOperand Chain, SDOperand VAList,
  81                    const Type *ArgTy, SelectionDAG &DAG);
  82
  83     virtual std::pair<SDOperand, SDOperand>
  84     LowerFrameReturnAddress(bool isFrameAddr, SDOperand Chain, unsigned Depth,
  85                             SelectionDAG &DAG);
  86   };
  87 }
  88
  89
  90 std::vector<SDOperand>
  91 X86TargetLowering::LowerArguments(Function &F, SelectionDAG &DAG) {
  92   std::vector<SDOperand> ArgValues;
  93
  94   // Add DAG nodes to load the arguments...  On entry to a function on the X86,
  95   // the stack frame looks like this:
  96   //
  97   // [ESP] -- return address
  98   // [ESP + 4] -- first argument (leftmost lexically)
  99   // [ESP + 8] -- second argument, if first argument is four bytes in size
 100   //    ...
 101   //
 102   MachineFunction &MF = DAG.getMachineFunction();
 103   MachineFrameInfo *MFI = MF.getFrameInfo();
 104
 105   unsigned ArgOffset = 0;   // Frame mechanisms handle retaddr slot
 106   for (Function::aiterator I = F.abegin(), E = F.aend(); I != E; ++I) {
 107     MVT::ValueType ObjectVT = getValueType(I->getType());
 108     unsigned ArgIncrement = 4;
 109     unsigned ObjSize;
 110     switch (ObjectVT) {
 111     default: assert(0 && "Unhandled argument type!");
 112     case MVT::i1:
 113     case MVT::i8:  ObjSize = 1;                break;
 114     case MVT::i16: ObjSize = 2;                break;
 115     case MVT::i32: ObjSize = 4;                break;
 116     case MVT::i64: ObjSize = ArgIncrement = 8; break;
 117     case MVT::f32: ObjSize = 4;                break;
 118     case MVT::f64: ObjSize = ArgIncrement = 8; break;
 119     }
 120     // Create the frame index object for this incoming parameter...
 121     int FI = MFI->CreateFixedObject(ObjSize, ArgOffset);
 122
 123     // Create the SelectionDAG nodes corresponding to a load from this parameter
 124     SDOperand FIN = DAG.getFrameIndex(FI, MVT::i32);
 125
 126     // Don't codegen dead arguments.  FIXME: remove this check when we can nuke
 127     // dead loads.
 128     SDOperand ArgValue;
 129     if (!I->use_empty())
 130       ArgValue = DAG.getLoad(ObjectVT, DAG.getEntryNode(), FIN);
 131     else {
 132       if (MVT::isInteger(ObjectVT))
 133         ArgValue = DAG.getConstant(0, ObjectVT);
 134       else
 135         ArgValue = DAG.getConstantFP(0, ObjectVT);
 136     }
 137     ArgValues.push_back(ArgValue);
 138
 139     ArgOffset += ArgIncrement;   // Move on to the next argument...
 140   }
 141
 142   // If the function takes variable number of arguments, make a frame index for
 143   // the start of the first vararg value... for expansion of llvm.va_start.
 144   if (F.isVarArg())
 145     VarArgsFrameIndex = MFI->CreateFixedObject(1, ArgOffset);
 146   ReturnAddrIndex = 0;  // No return address slot generated yet.
 147   return ArgValues;
 148 }
 149
 150 std::pair<SDOperand, SDOperand>
 151 X86TargetLowering::LowerCallTo(SDOperand Chain,
 152                                const Type *RetTy, SDOperand Callee,
 153                                ArgListTy &Args, SelectionDAG &DAG) {
 154   // Count how many bytes are to be pushed on the stack.
 155   unsigned NumBytes = 0;
 156
 157   if (Args.empty()) {
 158     // Save zero bytes.
 159     Chain = DAG.getNode(ISD::ADJCALLSTACKDOWN, MVT::Other, Chain,
 160                         DAG.getConstant(0, getPointerTy()));
 161   } else {
 162     for (unsigned i = 0, e = Args.size(); i != e; ++i)
 163       switch (getValueType(Args[i].second)) {
 164       default: assert(0 && "Unknown value type!");
 165       case MVT::i1:
 166       case MVT::i8:
 167       case MVT::i16:
 168       case MVT::i32:
 169       case MVT::f32:
 170         NumBytes += 4;
 171         break;
 172       case MVT::i64:
 173       case MVT::f64:
 174         NumBytes += 8;
 175         break;
 176       }
 177
 178     Chain = DAG.getNode(ISD::ADJCALLSTACKDOWN, MVT::Other, Chain,
 179                         DAG.getConstant(NumBytes, getPointerTy()));
 180
 181     // Arguments go on the stack in reverse order, as specified by the ABI.
 182     unsigned ArgOffset = 0;
 183     SDOperand StackPtr = DAG.getCopyFromReg(X86::ESP, MVT::i32);
 184     for (unsigned i = 0, e = Args.size(); i != e; ++i) {
 185       unsigned ArgReg;
 186       SDOperand PtrOff = DAG.getConstant(ArgOffset, getPointerTy());
 187       PtrOff = DAG.getNode(ISD::ADD, MVT::i32, StackPtr, PtrOff);
 188
 189       switch (getValueType(Args[i].second)) {
 190       default: assert(0 && "Unexpected ValueType for argument!");
 191       case MVT::i1:
 192       case MVT::i8:
 193       case MVT::i16:
 194         // Promote the integer to 32 bits.  If the input type is signed use a
 195         // sign extend, otherwise use a zero extend.
 196         if (Args[i].second->isSigned())
 197           Args[i].first =DAG.getNode(ISD::SIGN_EXTEND, MVT::i32, Args[i].first);
 198         else
 199           Args[i].first =DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, Args[i].first);
 200
 201         // FALL THROUGH
 202       case MVT::i32:
 203       case MVT::f32:
 204         // FIXME: Note that all of these stores are independent of each other.
 205         Chain = DAG.getNode(ISD::STORE, MVT::Other, Chain,
 206                             Args[i].first, PtrOff);
 207         ArgOffset += 4;
 208         break;
 209       case MVT::i64:
 210       case MVT::f64:
 211         // FIXME: Note that all of these stores are independent of each other.
 212         Chain = DAG.getNode(ISD::STORE, MVT::Other, Chain,
 213                             Args[i].first, PtrOff);
 214         ArgOffset += 8;
 215         break;
 216       }
 217     }
 218   }
 219
 220   std::vector<MVT::ValueType> RetVals;
 221   MVT::ValueType RetTyVT = getValueType(RetTy);
 222   if (RetTyVT != MVT::isVoid)
 223     RetVals.push_back(RetTyVT);
 224   RetVals.push_back(MVT::Other);
 225
 226   SDOperand TheCall = SDOperand(DAG.getCall(RetVals, Chain, Callee), 0);
 227   Chain = TheCall.getValue(RetTyVT != MVT::isVoid);
 228   Chain = DAG.getNode(ISD::ADJCALLSTACKUP, MVT::Other, Chain,
 229                       DAG.getConstant(NumBytes, getPointerTy()));
 230   return std::make_pair(TheCall, Chain);
 231 }
 232
 233 std::pair<SDOperand, SDOperand>
 234 X86TargetLowering::LowerVAStart(SDOperand Chain, SelectionDAG &DAG) {
 235   // vastart just returns the address of the VarArgsFrameIndex slot.
 236   return std::make_pair(DAG.getFrameIndex(VarArgsFrameIndex, MVT::i32), Chain);
 237 }
 238
 239 std::pair<SDOperand,SDOperand> X86TargetLowering::
 240 LowerVAArgNext(bool isVANext, SDOperand Chain, SDOperand VAList,
 241                const Type *ArgTy, SelectionDAG &DAG) {
 242   MVT::ValueType ArgVT = getValueType(ArgTy);
 243   SDOperand Result;
 244   if (!isVANext) {
 245     Result = DAG.getLoad(ArgVT, DAG.getEntryNode(), VAList);
 246   } else {
 247     unsigned Amt;
 248     if (ArgVT == MVT::i32)
 249       Amt = 4;
 250     else {
 251       assert((ArgVT == MVT::i64 || ArgVT == MVT::f64) &&
 252              "Other types should have been promoted for varargs!");
 253       Amt = 8;
 254     }
 255     Result = DAG.getNode(ISD::ADD, VAList.getValueType(), VAList,
 256                          DAG.getConstant(Amt, VAList.getValueType()));
 257   }
 258   return std::make_pair(Result, Chain);
 259 }
 260
 261
 262 std::pair<SDOperand, SDOperand> X86TargetLowering::
 263 LowerFrameReturnAddress(bool isFrameAddress, SDOperand Chain, unsigned Depth,
 264                         SelectionDAG &DAG) {
 265   SDOperand Result;
 266   if (Depth)        // Depths > 0 not supported yet!
 267     Result = DAG.getConstant(0, getPointerTy());
 268   else {
 269     if (ReturnAddrIndex == 0) {
 270       // Set up a frame object for the return address.
 271       MachineFunction &MF = DAG.getMachineFunction();
 272       ReturnAddrIndex = MF.getFrameInfo()->CreateFixedObject(4, -4);
 273     }
 274
 275     SDOperand RetAddrFI = DAG.getFrameIndex(ReturnAddrIndex, MVT::i32);
 276
 277     if (!isFrameAddress)
 278       // Just load the return address
 279       Result = DAG.getLoad(MVT::i32, DAG.getEntryNode(), RetAddrFI);
 280     else
 281       Result = DAG.getNode(ISD::SUB, MVT::i32, RetAddrFI,
 282                            DAG.getConstant(4, MVT::i32));
 283   }
 284   return std::make_pair(Result, Chain);
 285 }
 286
 287
 288
 289
 290
 291 namespace {
 292   Statistic<>
 293   NumFPKill("x86-codegen", "Number of FP_REG_KILL instructions added");
 294
 295   //===--------------------------------------------------------------------===//
 296   /// ISel - X86 specific code to select X86 machine instructions for
 297   /// SelectionDAG operations.
 298   ///
 299   class ISel : public SelectionDAGISel {
 300     /// ContainsFPCode - Every instruction we select that uses or defines a FP
 301     /// register should set this to true.
 302     bool ContainsFPCode;
 303
 304     /// X86Lowering - This object fully describes how to lower LLVM code to an
 305     /// X86-specific SelectionDAG.
 306     X86TargetLowering X86Lowering;
 307
 308     /// RegPressureMap - This keeps an approximate count of the number of
 309     /// registers required to evaluate each node in the graph.
 310     std::map<SDNode*, unsigned> RegPressureMap;
 311
 312     /// ExprMap - As shared expressions are codegen'd, we keep track of which
 313     /// vreg the value is produced in, so we only emit one copy of each compiled
 314     /// tree.
 315     std::map<SDOperand, unsigned> ExprMap;
 316     std::set<SDOperand> LoweredTokens;
 317
 318   public:
 319     ISel(TargetMachine &TM) : SelectionDAGISel(X86Lowering), X86Lowering(TM) {
 320     }
 321
 322     unsigned getRegPressure(SDOperand O) {
 323       return RegPressureMap[O.Val];
 324     }
 325     unsigned ComputeRegPressure(SDOperand O);
 326
 327     /// InstructionSelectBasicBlock - This callback is invoked by
 328     /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
 329     virtual void InstructionSelectBasicBlock(SelectionDAG &DAG) {
 330       // While we're doing this, keep track of whether we see any FP code for
 331       // FP_REG_KILL insertion.
 332       ContainsFPCode = false;
 333
 334       // Compute the RegPressureMap, which is an approximation for the number of
 335       // registers required to compute each node.
 336       ComputeRegPressure(DAG.getRoot());
 337
 338       //DAG.viewGraph();
 339
 340       // Codegen the basic block.
 341       Select(DAG.getRoot());
 342
 343       // Insert FP_REG_KILL instructions into basic blocks that need them.  This
 344       // only occurs due to the floating point stackifier not being aggressive
 345       // enough to handle arbitrary global stackification.
 346       //
 347       // Currently we insert an FP_REG_KILL instruction into each block that
 348       // uses or defines a floating point virtual register.
 349       //
 350       // When the global register allocators (like linear scan) finally update
 351       // live variable analysis, we can keep floating point values in registers
 352       // across basic blocks.  This will be a huge win, but we are waiting on
 353       // the global allocators before we can do this.
 354       //
 355       if (ContainsFPCode && BB->succ_size()) {
 356         BuildMI(*BB, BB->getFirstTerminator(), X86::FP_REG_KILL, 0);
 357         ++NumFPKill;
 358       }
 359
 360       // Clear state used for selection.
 361       ExprMap.clear();
 362       LoweredTokens.clear();
 363       RegPressureMap.clear();
 364     }
 365
 366     bool isFoldableLoad(SDOperand Op);
 367     void EmitFoldedLoad(SDOperand Op, X86AddressMode &AM);
 368
 369
 370     void EmitCMP(SDOperand LHS, SDOperand RHS);
 371     bool EmitBranchCC(MachineBasicBlock *Dest, SDOperand Chain, SDOperand Cond);
 372     void EmitSelectCC(SDOperand Cond, MVT::ValueType SVT,
 373                       unsigned RTrue, unsigned RFalse, unsigned RDest);
 374     unsigned SelectExpr(SDOperand N);
 375     bool SelectAddress(SDOperand N, X86AddressMode &AM);
 376     void Select(SDOperand N);
 377   };
 378 }
 379
 380 // ComputeRegPressure - Compute the RegPressureMap, which is an approximation
 381 // for the number of registers required to compute each node.  This is basically
 382 // computing a generalized form of the Sethi-Ullman number for each node.
 383 unsigned ISel::ComputeRegPressure(SDOperand O) {
 384   SDNode *N = O.Val;
 385   unsigned &Result = RegPressureMap[N];
 386   if (Result) return Result;
 387
 388   // FIXME: Should operations like CALL (which clobber lots o regs) have a
 389   // higher fixed cost??
 390
 391   if (N->getNumOperands() == 0) {
 392     Result = 1;
 393   } else {
 394     unsigned MaxRegUse = 0;
 395     unsigned NumExtraMaxRegUsers = 0;
 396     for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
 397       unsigned Regs;
 398       if (N->getOperand(i).getOpcode() == ISD::Constant)
 399         Regs = 0;
 400       else
 401         Regs = ComputeRegPressure(N->getOperand(i));
 402       if (Regs > MaxRegUse) {
 403         MaxRegUse = Regs;
 404         NumExtraMaxRegUsers = 0;
 405       } else if (Regs == MaxRegUse &&
 406                  N->getOperand(i).getValueType() != MVT::Other) {
 407         ++NumExtraMaxRegUsers;
 408       }
 409     }
 410
 411     Result = MaxRegUse+NumExtraMaxRegUsers;
 412   }
 413   //std::cerr << " WEIGHT: " << Result << " ";  N->dump(); std::cerr << "\n";
 414   return Result;
 415 }
 416
 417 /// SelectAddress - Add the specified node to the specified addressing mode,
 418 /// returning true if it cannot be done.
 419 bool ISel::SelectAddress(SDOperand N, X86AddressMode &AM) {
 420   switch (N.getOpcode()) {
 421   default: break;
 422   case ISD::FrameIndex:
 423     if (AM.BaseType == X86AddressMode::RegBase && AM.Base.Reg == 0) {
 424       AM.BaseType = X86AddressMode::FrameIndexBase;
 425       AM.Base.FrameIndex = cast<FrameIndexSDNode>(N)->getIndex();
 426       return false;
 427     }
 428     break;
 429   case ISD::GlobalAddress:
 430     if (AM.GV == 0) {
 431       AM.GV = cast<GlobalAddressSDNode>(N)->getGlobal();
 432       return false;
 433     }
 434     break;
 435   case ISD::Constant:
 436     AM.Disp += cast<ConstantSDNode>(N)->getValue();
 437     return false;
 438   case ISD::SHL:
 439     if (AM.IndexReg == 0 || AM.Scale == 1)
 440       if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.Val->getOperand(1))) {
 441         unsigned Val = CN->getValue();
 442         if (Val == 1 || Val == 2 || Val == 3) {
 443           AM.Scale = 1 << Val;
 444           SDOperand ShVal = N.Val->getOperand(0);
 445
 446           // Okay, we know that we have a scale by now.  However, if the scaled
 447           // value is an add of something and a constant, we can fold the
 448           // constant into the disp field here.
 449           if (ShVal.Val->getOpcode() == ISD::ADD &&
 450               isa<ConstantSDNode>(ShVal.Val->getOperand(1))) {
 451             AM.IndexReg = SelectExpr(ShVal.Val->getOperand(0));
 452             ConstantSDNode *AddVal =
 453               cast<ConstantSDNode>(ShVal.Val->getOperand(1));
 454             AM.Disp += AddVal->getValue() << Val;
 455           } else {
 456             AM.IndexReg = SelectExpr(ShVal);
 457           }
 458           return false;
 459         }
 460       }
 461     break;
 462   case ISD::MUL:
 463     // X*[3,5,9] -> X+X*[2,4,8]
 464     if (AM.IndexReg == 0 && AM.BaseType == X86AddressMode::RegBase &&
 465         AM.Base.Reg == 0)
 466       if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.Val->getOperand(1)))
 467         if (CN->getValue() == 3 || CN->getValue() == 5 || CN->getValue() == 9) {
 468           AM.Scale = unsigned(CN->getValue())-1;
 469
 470           SDOperand MulVal = N.Val->getOperand(0);
 471           unsigned Reg;
 472
 473           // Okay, we know that we have a scale by now.  However, if the scaled
 474           // value is an add of something and a constant, we can fold the
 475           // constant into the disp field here.
 476           if (MulVal.Val->getOpcode() == ISD::ADD &&
 477               isa<ConstantSDNode>(MulVal.Val->getOperand(1))) {
 478             Reg = SelectExpr(MulVal.Val->getOperand(0));
 479             ConstantSDNode *AddVal =
 480               cast<ConstantSDNode>(MulVal.Val->getOperand(1));
 481             AM.Disp += AddVal->getValue() * CN->getValue();
 482           } else {
 483             Reg = SelectExpr(N.Val->getOperand(0));
 484           }
 485
 486           AM.IndexReg = AM.Base.Reg = Reg;
 487           return false;
 488         }
 489     break;
 490
 491   case ISD::ADD: {
 492     X86AddressMode Backup = AM;
 493     if (!SelectAddress(N.Val->getOperand(0), AM) &&
 494         !SelectAddress(N.Val->getOperand(1), AM))
 495       return false;
 496     AM = Backup;
 497     break;
 498   }
 499   }
 500
 501   // Is the base register already occupied?
 502   if (AM.BaseType != X86AddressMode::RegBase || AM.Base.Reg) {
 503     // If so, check to see if the scale index register is set.
 504     if (AM.IndexReg == 0) {
 505       AM.IndexReg = SelectExpr(N);
 506       AM.Scale = 1;
 507       return false;
 508     }
 509
 510     // Otherwise, we cannot select it.
 511     return true;
 512   }
 513
 514   // Default, generate it as a register.
 515   AM.BaseType = X86AddressMode::RegBase;
 516   AM.Base.Reg = SelectExpr(N);
 517   return false;
 518 }
 519
 520 /// Emit2SetCCsAndLogical - Emit the following sequence of instructions,
 521 /// assuming that the temporary registers are in the 8-bit register class.
 522 ///
 523 ///  Tmp1 = setcc1
 524 ///  Tmp2 = setcc2
 525 ///  DestReg = logicalop Tmp1, Tmp2
 526 ///
 527 static void Emit2SetCCsAndLogical(MachineBasicBlock *BB, unsigned SetCC1,
 528                                   unsigned SetCC2, unsigned LogicalOp,
 529                                   unsigned DestReg) {
 530   SSARegMap *RegMap = BB->getParent()->getSSARegMap();
 531   unsigned Tmp1 = RegMap->createVirtualRegister(X86::R8RegisterClass);
 532   unsigned Tmp2 = RegMap->createVirtualRegister(X86::R8RegisterClass);
 533   BuildMI(BB, SetCC1, 0, Tmp1);
 534   BuildMI(BB, SetCC2, 0, Tmp2);
 535   BuildMI(BB, LogicalOp, 2, DestReg).addReg(Tmp1).addReg(Tmp2);
 536 }
 537
 538 /// EmitSetCC - Emit the code to set the specified 8-bit register to 1 if the
 539 /// condition codes match the specified SetCCOpcode.  Note that some conditions
 540 /// require multiple instructions to generate the correct value.
 541 static void EmitSetCC(MachineBasicBlock *BB, unsigned DestReg,
 542                       ISD::CondCode SetCCOpcode, bool isFP) {
 543   unsigned Opc;
 544   if (!isFP) {
 545     switch (SetCCOpcode) {
 546     default: assert(0 && "Illegal integer SetCC!");
 547     case ISD::SETEQ: Opc = X86::SETEr; break;
 548     case ISD::SETGT: Opc = X86::SETGr; break;
 549     case ISD::SETGE: Opc = X86::SETGEr; break;
 550     case ISD::SETLT: Opc = X86::SETLr; break;
 551     case ISD::SETLE: Opc = X86::SETLEr; break;
 552     case ISD::SETNE: Opc = X86::SETNEr; break;
 553     case ISD::SETULT: Opc = X86::SETBr; break;
 554     case ISD::SETUGT: Opc = X86::SETAr; break;
 555     case ISD::SETULE: Opc = X86::SETBEr; break;
 556     case ISD::SETUGE: Opc = X86::SETAEr; break;
 557     }
 558   } else {
 559     // On a floating point condition, the flags are set as follows:
 560     // ZF  PF  CF   op
 561     //  0 | 0 | 0 | X > Y
 562     //  0 | 0 | 1 | X < Y
 563     //  1 | 0 | 0 | X == Y
 564     //  1 | 1 | 1 | unordered
 565     //
 566     switch (SetCCOpcode) {
 567     default: assert(0 && "Invalid FP setcc!");
 568     case ISD::SETUEQ:
 569     case ISD::SETEQ:
 570       Opc = X86::SETEr;    // True if ZF = 1
 571       break;
 572     case ISD::SETOGT:
 573     case ISD::SETGT:
 574       Opc = X86::SETAr;    // True if CF = 0 and ZF = 0
 575       break;
 576     case ISD::SETOGE:
 577     case ISD::SETGE:
 578       Opc = X86::SETAEr;   // True if CF = 0
 579       break;
 580     case ISD::SETULT:
 581     case ISD::SETLT:
 582       Opc = X86::SETBr;    // True if CF = 1
 583       break;
 584     case ISD::SETULE:
 585     case ISD::SETLE:
 586       Opc = X86::SETBEr;   // True if CF = 1 or ZF = 1
 587       break;
 588     case ISD::SETONE:
 589     case ISD::SETNE:
 590       Opc = X86::SETNEr;   // True if ZF = 0
 591       break;
 592     case ISD::SETUO:
 593       Opc = X86::SETPr;    // True if PF = 1
 594       break;
 595     case ISD::SETO:
 596       Opc = X86::SETNPr;   // True if PF = 0
 597       break;
 598     case ISD::SETOEQ:      // !PF & ZF
 599       Emit2SetCCsAndLogical(BB, X86::SETNPr, X86::SETEr, X86::AND8rr, DestReg);
 600       return;
 601     case ISD::SETOLT:      // !PF & CF
 602       Emit2SetCCsAndLogical(BB, X86::SETNPr, X86::SETBr, X86::AND8rr, DestReg);
 603       return;
 604     case ISD::SETOLE:      // !PF & (CF || ZF)
 605       Emit2SetCCsAndLogical(BB, X86::SETNPr, X86::SETBEr, X86::AND8rr, DestReg);
 606       return;
 607     case ISD::SETUGT:      // PF | (!ZF & !CF)
 608       Emit2SetCCsAndLogical(BB, X86::SETPr, X86::SETAr, X86::OR8rr, DestReg);
 609       return;
 610     case ISD::SETUGE:      // PF | !CF
 611       Emit2SetCCsAndLogical(BB, X86::SETPr, X86::SETAEr, X86::OR8rr, DestReg);
 612       return;
 613     case ISD::SETUNE:      // PF | !ZF
 614       Emit2SetCCsAndLogical(BB, X86::SETPr, X86::SETNEr, X86::OR8rr, DestReg);
 615       return;
 616     }
 617   }
 618   BuildMI(BB, Opc, 0, DestReg);
 619 }
 620
 621
 622 /// EmitBranchCC - Emit code into BB that arranges for control to transfer to
 623 /// the Dest block if the Cond condition is true.  If we cannot fold this
 624 /// condition into the branch, return true.
 625 ///
 626 bool ISel::EmitBranchCC(MachineBasicBlock *Dest, SDOperand Chain,
 627                         SDOperand Cond) {
 628   // FIXME: Evaluate whether it would be good to emit code like (X < Y) | (A >
 629   // B) using two conditional branches instead of one condbr, two setcc's, and
 630   // an or.
 631   if ((Cond.getOpcode() == ISD::OR ||
 632        Cond.getOpcode() == ISD::AND) && Cond.Val->hasOneUse()) {
 633     // And and or set the flags for us, so there is no need to emit a TST of the
 634     // result.  It is only safe to do this if there is only a single use of the
 635     // AND/OR though, otherwise we don't know it will be emitted here.
 636     Select(Chain);
 637     SelectExpr(Cond);
 638     BuildMI(BB, X86::JNE, 1).addMBB(Dest);
 639     return false;
 640   }
 641
 642   // Codegen br not C -> JE.
 643   if (Cond.getOpcode() == ISD::XOR)
 644     if (ConstantSDNode *NC = dyn_cast<ConstantSDNode>(Cond.Val->getOperand(1)))
 645       if (NC->isAllOnesValue()) {
 646         unsigned CondR;
 647         if (getRegPressure(Chain) > getRegPressure(Cond)) {
 648           Select(Chain);
 649           CondR = SelectExpr(Cond.Val->getOperand(0));
 650         } else {
 651           CondR = SelectExpr(Cond.Val->getOperand(0));
 652           Select(Chain);
 653         }
 654         BuildMI(BB, X86::TEST8rr, 2).addReg(CondR).addReg(CondR);
 655         BuildMI(BB, X86::JE, 1).addMBB(Dest);
 656         return false;
 657       }
 658
 659   SetCCSDNode *SetCC = dyn_cast<SetCCSDNode>(Cond);
 660   if (SetCC == 0)
 661     return true;                       // Can only handle simple setcc's so far.
 662
 663   unsigned Opc;
 664
 665   // Handle integer conditions first.
 666   if (MVT::isInteger(SetCC->getOperand(0).getValueType())) {
 667     switch (SetCC->getCondition()) {
 668     default: assert(0 && "Illegal integer SetCC!");
 669     case ISD::SETEQ: Opc = X86::JE; break;
 670     case ISD::SETGT: Opc = X86::JG; break;
 671     case ISD::SETGE: Opc = X86::JGE; break;
 672     case ISD::SETLT: Opc = X86::JL; break;
 673     case ISD::SETLE: Opc = X86::JLE; break;
 674     case ISD::SETNE: Opc = X86::JNE; break;
 675     case ISD::SETULT: Opc = X86::JB; break;
 676     case ISD::SETUGT: Opc = X86::JA; break;
 677     case ISD::SETULE: Opc = X86::JBE; break;
 678     case ISD::SETUGE: Opc = X86::JAE; break;
 679     }
 680     Select(Chain);
 681     EmitCMP(SetCC->getOperand(0), SetCC->getOperand(1));
 682     BuildMI(BB, Opc, 1).addMBB(Dest);
 683     return false;
 684   }
 685
 686   unsigned Opc2 = 0;  // Second branch if needed.
 687
 688   // On a floating point condition, the flags are set as follows:
 689   // ZF  PF  CF   op
 690   //  0 | 0 | 0 | X > Y
 691   //  0 | 0 | 1 | X < Y
 692   //  1 | 0 | 0 | X == Y
 693   //  1 | 1 | 1 | unordered
 694   //
 695   switch (SetCC->getCondition()) {
 696   default: assert(0 && "Invalid FP setcc!");
 697   case ISD::SETUEQ:
 698   case ISD::SETEQ:   Opc = X86::JE;  break;     // True if ZF = 1
 699   case ISD::SETOGT:
 700   case ISD::SETGT:   Opc = X86::JA;  break;     // True if CF = 0 and ZF = 0
 701   case ISD::SETOGE:
 702   case ISD::SETGE:   Opc = X86::JAE; break;     // True if CF = 0
 703   case ISD::SETULT:
 704   case ISD::SETLT:   Opc = X86::JB;  break;     // True if CF = 1
 705   case ISD::SETULE:
 706   case ISD::SETLE:   Opc = X86::JBE; break;     // True if CF = 1 or ZF = 1
 707   case ISD::SETONE:
 708   case ISD::SETNE:   Opc = X86::JNE; break;     // True if ZF = 0
 709   case ISD::SETUO:   Opc = X86::JP;  break;     // True if PF = 1
 710   case ISD::SETO:    Opc = X86::JNP; break;     // True if PF = 0
 711   case ISD::SETUGT:      // PF = 1 | (ZF = 0 & CF = 0)
 712     Opc = X86::JA;       // ZF = 0 & CF = 0
 713     Opc2 = X86::JP;      // PF = 1
 714     break;
 715   case ISD::SETUGE:      // PF = 1 | CF = 0
 716     Opc = X86::JAE;      // CF = 0
 717     Opc2 = X86::JP;      // PF = 1
 718     break;
 719   case ISD::SETUNE:      // PF = 1 | ZF = 0
 720     Opc = X86::JNE;      // ZF = 0
 721     Opc2 = X86::JP;      // PF = 1
 722     break;
 723   case ISD::SETOEQ:      // PF = 0 & ZF = 1
 724     //X86::JNP, X86::JE
 725     //X86::AND8rr
 726     return true;    // FIXME: Emit more efficient code for this branch.
 727   case ISD::SETOLT:      // PF = 0 & CF = 1
 728     //X86::JNP, X86::JB
 729     //X86::AND8rr
 730     return true;    // FIXME: Emit more efficient code for this branch.
 731   case ISD::SETOLE:      // PF = 0 & (CF = 1 || ZF = 1)
 732     //X86::JNP, X86::JBE
 733     //X86::AND8rr
 734     return true;    // FIXME: Emit more efficient code for this branch.
 735   }
 736
 737   Select(Chain);
 738   EmitCMP(SetCC->getOperand(0), SetCC->getOperand(1));
 739   BuildMI(BB, Opc, 1).addMBB(Dest);
 740   if (Opc2)
 741     BuildMI(BB, Opc2, 1).addMBB(Dest);
 742   return false;
 743 }
 744
 745 /// EmitSelectCC - Emit code into BB that performs a select operation between
 746 /// the two registers RTrue and RFalse, generating a result into RDest.  Return
 747 /// true if the fold cannot be performed.
 748 ///
 749 void ISel::EmitSelectCC(SDOperand Cond, MVT::ValueType SVT,
 750                         unsigned RTrue, unsigned RFalse, unsigned RDest) {
 751   enum Condition {
 752     EQ, NE, LT, LE, GT, GE, B, BE, A, AE, P, NP,
 753     NOT_SET
 754   } CondCode = NOT_SET;
 755
 756   static const unsigned CMOVTAB16[] = {
 757     X86::CMOVE16rr,  X86::CMOVNE16rr, X86::CMOVL16rr,  X86::CMOVLE16rr,
 758     X86::CMOVG16rr,  X86::CMOVGE16rr, X86::CMOVB16rr,  X86::CMOVBE16rr,
 759     X86::CMOVA16rr,  X86::CMOVAE16rr, X86::CMOVP16rr,  X86::CMOVNP16rr,
 760   };
 761   static const unsigned CMOVTAB32[] = {
 762     X86::CMOVE32rr,  X86::CMOVNE32rr, X86::CMOVL32rr,  X86::CMOVLE32rr,
 763     X86::CMOVG32rr,  X86::CMOVGE32rr, X86::CMOVB32rr,  X86::CMOVBE32rr,
 764     X86::CMOVA32rr,  X86::CMOVAE32rr, X86::CMOVP32rr,  X86::CMOVNP32rr,
 765   };
 766   static const unsigned CMOVTABFP[] = {
 767     X86::FCMOVE ,  X86::FCMOVNE, /*missing*/0, /*missing*/0,
 768     /*missing*/0,  /*missing*/0, X86::FCMOVB , X86::FCMOVBE,
 769     X86::FCMOVA ,  X86::FCMOVAE, X86::FCMOVP , X86::FCMOVNP
 770   };
 771
 772   if (SetCCSDNode *SetCC = dyn_cast<SetCCSDNode>(Cond)) {
 773     if (MVT::isInteger(SetCC->getOperand(0).getValueType())) {
 774       switch (SetCC->getCondition()) {
 775       default: assert(0 && "Unknown integer comparison!");
 776       case ISD::SETEQ:  CondCode = EQ; break;
 777       case ISD::SETGT:  CondCode = GT; break;
 778       case ISD::SETGE:  CondCode = GE; break;
 779       case ISD::SETLT:  CondCode = LT; break;
 780       case ISD::SETLE:  CondCode = LE; break;
 781       case ISD::SETNE:  CondCode = NE; break;
 782       case ISD::SETULT: CondCode = B; break;
 783       case ISD::SETUGT: CondCode = A; break;
 784       case ISD::SETULE: CondCode = BE; break;
 785       case ISD::SETUGE: CondCode = AE; break;
 786       }
 787     } else {
 788       // On a floating point condition, the flags are set as follows:
 789       // ZF  PF  CF   op
 790       //  0 | 0 | 0 | X > Y
 791       //  0 | 0 | 1 | X < Y
 792       //  1 | 0 | 0 | X == Y
 793       //  1 | 1 | 1 | unordered
 794       //
 795       switch (SetCC->getCondition()) {
 796       default: assert(0 && "Unknown FP comparison!");
 797       case ISD::SETUEQ:
 798       case ISD::SETEQ:  CondCode = EQ; break;     // True if ZF = 1
 799       case ISD::SETOGT:
 800       case ISD::SETGT:  CondCode = A;  break;     // True if CF = 0 and ZF = 0
 801       case ISD::SETOGE:
 802       case ISD::SETGE:  CondCode = AE; break;     // True if CF = 0
 803       case ISD::SETULT:
 804       case ISD::SETLT:  CondCode = B;  break;     // True if CF = 1
 805       case ISD::SETULE:
 806       case ISD::SETLE:  CondCode = BE; break;     // True if CF = 1 or ZF = 1
 807       case ISD::SETONE:
 808       case ISD::SETNE:  CondCode = NE; break;     // True if ZF = 0
 809       case ISD::SETUO:  CondCode = P;  break;     // True if PF = 1
 810       case ISD::SETO:   CondCode = NP; break;     // True if PF = 0
 811       case ISD::SETUGT:      // PF = 1 | (ZF = 0 & CF = 0)
 812       case ISD::SETUGE:      // PF = 1 | CF = 0
 813       case ISD::SETUNE:      // PF = 1 | ZF = 0
 814       case ISD::SETOEQ:      // PF = 0 & ZF = 1
 815       case ISD::SETOLT:      // PF = 0 & CF = 1
 816       case ISD::SETOLE:      // PF = 0 & (CF = 1 || ZF = 1)
 817         // We cannot emit this comparison as a single cmov.
 818         break;
 819       }
 820     }
 821   }
 822
 823   unsigned Opc = 0;
 824   if (CondCode != NOT_SET) {
 825     switch (SVT) {
 826     default: assert(0 && "Cannot select this type!");
 827     case MVT::i16: Opc = CMOVTAB16[CondCode]; break;
 828     case MVT::i32: Opc = CMOVTAB32[CondCode]; break;
 829     case MVT::f32:
 830     case MVT::f64: Opc = CMOVTABFP[CondCode]; break;
 831     }
 832   }
 833
 834   // Finally, if we weren't able to fold this, just emit the condition and test
 835   // it.
 836   if (CondCode == NOT_SET || Opc == 0) {
 837     // Get the condition into the zero flag.
 838     unsigned CondReg = SelectExpr(Cond);
 839     BuildMI(BB, X86::TEST8rr, 2).addReg(CondReg).addReg(CondReg);
 840
 841     switch (SVT) {
 842     default: assert(0 && "Cannot select this type!");
 843     case MVT::i16: Opc = X86::CMOVE16rr; break;
 844     case MVT::i32: Opc = X86::CMOVE32rr; break;
 845     case MVT::f32:
 846     case MVT::f64: Opc = X86::FCMOVE; break;
 847     }
 848   } else {
 849     // FIXME: CMP R, 0 -> TEST R, R
 850     EmitCMP(Cond.getOperand(0), Cond.getOperand(1));
 851     std::swap(RTrue, RFalse);
 852   }
 853   BuildMI(BB, Opc, 2, RDest).addReg(RTrue).addReg(RFalse);
 854 }
 855
 856 void ISel::EmitCMP(SDOperand LHS, SDOperand RHS) {
 857   unsigned Opc;
 858   if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(RHS)) {
 859     Opc = 0;
 860     switch (RHS.getValueType()) {
 861     default: break;
 862     case MVT::i1:
 863     case MVT::i8:  Opc = X86::CMP8ri;  break;
 864     case MVT::i16: Opc = X86::CMP16ri; break;
 865     case MVT::i32: Opc = X86::CMP32ri; break;
 866     }
 867     if (Opc) {
 868       unsigned Tmp1 = SelectExpr(LHS);
 869       BuildMI(BB, Opc, 2).addReg(Tmp1).addImm(CN->getValue());
 870       return;
 871     }
 872   }
 873
 874   switch (LHS.getValueType()) {
 875   default: assert(0 && "Cannot compare this value!");
 876   case MVT::i1:
 877   case MVT::i8:  Opc = X86::CMP8rr;  break;
 878   case MVT::i16: Opc = X86::CMP16rr; break;
 879   case MVT::i32: Opc = X86::CMP32rr; break;
 880   case MVT::f32:
 881   case MVT::f64: Opc = X86::FUCOMIr; break;
 882   }
 883   unsigned Tmp1, Tmp2;
 884   if (getRegPressure(LHS) > getRegPressure(RHS)) {
 885     Tmp1 = SelectExpr(LHS);
 886     Tmp2 = SelectExpr(RHS);
 887   } else {
 888     Tmp2 = SelectExpr(RHS);
 889     Tmp1 = SelectExpr(LHS);
 890   }
 891   BuildMI(BB, Opc, 2).addReg(Tmp1).addReg(Tmp2);
 892 }
 893
 894 /// isFoldableLoad - Return true if this is a load instruction that can safely
 895 /// be folded into an operation that uses it.
 896 bool ISel::isFoldableLoad(SDOperand Op) {
 897   if (Op.getOpcode() != ISD::LOAD ||
 898       // FIXME: currently can't fold constant pool indexes.
 899       isa<ConstantPoolSDNode>(Op.getOperand(1)))
 900     return false;
 901
 902   // If this load has already been emitted, we clearly can't fold it.
 903   if (ExprMap.count(Op)) return false;
 904
 905   return Op.Val->use_size() == 2;
 906 }
 907
 908 /// EmitFoldedLoad - Ensure that the arguments of the load are code generated,
 909 /// and compute the address being loaded into AM.
 910 void ISel::EmitFoldedLoad(SDOperand Op, X86AddressMode &AM) {
 911   SDOperand Chain   = Op.getOperand(0);
 912   SDOperand Address = Op.getOperand(1);
 913   if (getRegPressure(Chain) > getRegPressure(Address)) {
 914     Select(Chain);
 915     SelectAddress(Address, AM);
 916   } else {
 917     SelectAddress(Address, AM);
 918     Select(Chain);
 919   }
 920
 921   // The chain for this load is now lowered.
 922   LoweredTokens.insert(SDOperand(Op.Val, 1));
 923   ExprMap[SDOperand(Op.Val, 1)] = 1;
 924 }
 925
 926 unsigned ISel::SelectExpr(SDOperand N) {
 927   unsigned Result;
 928   unsigned Tmp1, Tmp2, Tmp3;
 929   unsigned Opc = 0;
 930   SDNode *Node = N.Val;
 931   SDOperand Op0, Op1;
 932
 933   if (Node->getOpcode() == ISD::CopyFromReg)
 934     // Just use the specified register as our input.
 935     return dyn_cast<CopyRegSDNode>(Node)->getReg();
 936
 937   unsigned &Reg = ExprMap[N];
 938   if (Reg) return Reg;
 939
 940   if (N.getOpcode() != ISD::CALL)
 941     Reg = Result = (N.getValueType() != MVT::Other) ?
 942       MakeReg(N.getValueType()) : 1;
 943   else {
 944     // If this is a call instruction, make sure to prepare ALL of the result
 945     // values as well as the chain.
 946     if (Node->getNumValues() == 1)
 947       Reg = Result = 1;  // Void call, just a chain.
 948     else {
 949       Result = MakeReg(Node->getValueType(0));
 950       ExprMap[N.getValue(0)] = Result;
 951       for (unsigned i = 1, e = N.Val->getNumValues()-1; i != e; ++i)
 952         ExprMap[N.getValue(i)] = MakeReg(Node->getValueType(i));
 953       ExprMap[SDOperand(Node, Node->getNumValues()-1)] = 1;
 954     }
 955   }
 956
 957   switch (N.getOpcode()) {
 958   default:
 959     Node->dump();
 960     assert(0 && "Node not handled!\n");
 961   case ISD::FrameIndex:
 962     Tmp1 = cast<FrameIndexSDNode>(N)->getIndex();
 963     addFrameReference(BuildMI(BB, X86::LEA32r, 4, Result), (int)Tmp1);
 964     return Result;
 965   case ISD::ConstantPool:
 966     Tmp1 = cast<ConstantPoolSDNode>(N)->getIndex();
 967     addConstantPoolReference(BuildMI(BB, X86::LEA32r, 4, Result), Tmp1);
 968     return Result;
 969   case ISD::ConstantFP:
 970     ContainsFPCode = true;
 971     Tmp1 = Result;   // Intermediate Register
 972     if (cast<ConstantFPSDNode>(N)->getValue() < 0.0 ||
 973         cast<ConstantFPSDNode>(N)->isExactlyValue(-0.0))
 974       Tmp1 = MakeReg(MVT::f64);
 975
 976     if (cast<ConstantFPSDNode>(N)->isExactlyValue(+0.0) ||
 977         cast<ConstantFPSDNode>(N)->isExactlyValue(-0.0))
 978       BuildMI(BB, X86::FLD0, 0, Tmp1);
 979     else if (cast<ConstantFPSDNode>(N)->isExactlyValue(+1.0) ||
 980              cast<ConstantFPSDNode>(N)->isExactlyValue(-1.0))
 981       BuildMI(BB, X86::FLD1, 0, Tmp1);
 982     else
 983       assert(0 && "Unexpected constant!");
 984     if (Tmp1 != Result)
 985       BuildMI(BB, X86::FCHS, 1, Result).addReg(Tmp1);
 986     return Result;
 987   case ISD::Constant:
 988     switch (N.getValueType()) {
 989     default: assert(0 && "Cannot use constants of this type!");
 990     case MVT::i1:
 991     case MVT::i8:  Opc = X86::MOV8ri;  break;
 992     case MVT::i16: Opc = X86::MOV16ri; break;
 993     case MVT::i32: Opc = X86::MOV32ri; break;
 994     }
 995     BuildMI(BB, Opc, 1,Result).addImm(cast<ConstantSDNode>(N)->getValue());
 996     return Result;
 997   case ISD::GlobalAddress: {
 998     GlobalValue *GV = cast<GlobalAddressSDNode>(N)->getGlobal();
 999     BuildMI(BB, X86::MOV32ri, 1, Result).addGlobalAddress(GV);
1000     return Result;
1001   }
1002   case ISD::ExternalSymbol: {
1003     const char *Sym = cast<ExternalSymbolSDNode>(N)->getSymbol();
1004     BuildMI(BB, X86::MOV32ri, 1, Result).addExternalSymbol(Sym);
1005     return Result;
1006   }
1007   case ISD::FP_EXTEND:
1008     Tmp1 = SelectExpr(N.getOperand(0));
1009     BuildMI(BB, X86::FpMOV, 1, Result).addReg(Tmp1);
1010     return Result;
1011   case ISD::ZERO_EXTEND: {
1012     int DestIs16 = N.getValueType() == MVT::i16;
1013     int SrcIs16  = N.getOperand(0).getValueType() == MVT::i16;
1014     Tmp1 = SelectExpr(N.getOperand(0));
1015
1016     // FIXME: This hack is here for zero extension casts from bool to i8.  This
1017     // would not be needed if bools were promoted by Legalize.
1018     if (N.getValueType() == MVT::i8) {
1019       BuildMI(BB, X86::MOV8rr, 1, Result).addReg(Tmp1);
1020       return Result;
1021     }
1022
1023     static const unsigned Opc[3] = {
1024       X86::MOVZX32rr8, X86::MOVZX32rr16, X86::MOVZX16rr8
1025     };
1026     BuildMI(BB, Opc[SrcIs16+DestIs16*2], 1, Result).addReg(Tmp1);
1027     return Result;
1028   }
1029   case ISD::SIGN_EXTEND: {
1030     int DestIs16 = N.getValueType() == MVT::i16;
1031     int SrcIs16  = N.getOperand(0).getValueType() == MVT::i16;
1032
1033     // FIXME: Legalize should promote bools to i8!
1034     assert(N.getOperand(0).getValueType() != MVT::i1 &&
1035            "Sign extend from bool not implemented!");
1036
1037     static const unsigned Opc[3] = {
1038       X86::MOVSX32rr8, X86::MOVSX32rr16, X86::MOVSX16rr8
1039     };
1040     Tmp1 = SelectExpr(N.getOperand(0));
1041     BuildMI(BB, Opc[SrcIs16+DestIs16*2], 1, Result).addReg(Tmp1);
1042     return Result;
1043   }
1044   case ISD::TRUNCATE:
1045     // Handle cast of LARGER int to SMALLER int using a move to EAX followed by
1046     // a move out of AX or AL.
1047     switch (N.getOperand(0).getValueType()) {
1048     default: assert(0 && "Unknown truncate!");
1049     case MVT::i8:  Tmp2 = X86::AL;  Opc = X86::MOV8rr;  break;
1050     case MVT::i16: Tmp2 = X86::AX;  Opc = X86::MOV16rr; break;
1051     case MVT::i32: Tmp2 = X86::EAX; Opc = X86::MOV32rr; break;
1052     }
1053     Tmp1 = SelectExpr(N.getOperand(0));
1054     BuildMI(BB, Opc, 1, Tmp2).addReg(Tmp1);
1055
1056     switch (N.getValueType()) {
1057     default: assert(0 && "Unknown truncate!");
1058     case MVT::i1:
1059     case MVT::i8:  Tmp2 = X86::AL;  Opc = X86::MOV8rr;  break;
1060     case MVT::i16: Tmp2 = X86::AX;  Opc = X86::MOV16rr; break;
1061     }
1062     BuildMI(BB, Opc, 1, Result).addReg(Tmp2);
1063     return Result;
1064
1065   case ISD::FP_ROUND:
1066     // Truncate from double to float by storing to memory as float,
1067     // then reading it back into a register.
1068
1069     // Create as stack slot to use.
1070     // FIXME: This should automatically be made by the Legalizer!
1071     Tmp1 = TLI.getTargetData().getFloatAlignment();
1072     Tmp2 = BB->getParent()->getFrameInfo()->CreateStackObject(4, Tmp1);
1073
1074     // Codegen the input.
1075     Tmp1 = SelectExpr(N.getOperand(0));
1076
1077     // Emit the store, then the reload.
1078     addFrameReference(BuildMI(BB, X86::FST32m, 5), Tmp2).addReg(Tmp1);
1079     addFrameReference(BuildMI(BB, X86::FLD32m, 5, Result), Tmp2);
1080     return Result;
1081
1082   case ISD::SINT_TO_FP:
1083   case ISD::UINT_TO_FP: {
1084     // FIXME: Most of this grunt work should be done by legalize!
1085     ContainsFPCode = true;
1086
1087     // Promote the integer to a type supported by FLD.  We do this because there
1088     // are no unsigned FLD instructions, so we must promote an unsigned value to
1089     // a larger signed value, then use FLD on the larger value.
1090     //
1091     MVT::ValueType PromoteType = MVT::Other;
1092     MVT::ValueType SrcTy = N.getOperand(0).getValueType();
1093     unsigned PromoteOpcode = 0;
1094     unsigned RealDestReg = Result;
1095     switch (SrcTy) {
1096     case MVT::i1:
1097     case MVT::i8:
1098       // We don't have the facilities for directly loading byte sized data from
1099       // memory (even signed).  Promote it to 16 bits.
1100       PromoteType = MVT::i16;
1101       PromoteOpcode = Node->getOpcode() == ISD::SINT_TO_FP ?
1102         X86::MOVSX16rr8 : X86::MOVZX16rr8;
1103       break;
1104     case MVT::i16:
1105       if (Node->getOpcode() == ISD::UINT_TO_FP) {
1106         PromoteType = MVT::i32;
1107         PromoteOpcode = X86::MOVZX32rr16;
1108       }
1109       break;
1110     default:
1111       // Don't fild into the real destination.
1112       if (Node->getOpcode() == ISD::UINT_TO_FP)
1113         Result = MakeReg(Node->getValueType(0));
1114       break;
1115     }
1116
1117     Tmp1 = SelectExpr(N.getOperand(0));  // Get the operand register
1118
1119     if (PromoteType != MVT::Other) {
1120       Tmp2 = MakeReg(PromoteType);
1121       BuildMI(BB, PromoteOpcode, 1, Tmp2).addReg(Tmp1);
1122       SrcTy = PromoteType;
1123       Tmp1 = Tmp2;
1124     }
1125
1126     // Spill the integer to memory and reload it from there.
1127     unsigned Size = MVT::getSizeInBits(SrcTy)/8;
1128     MachineFunction *F = BB->getParent();
1129     int FrameIdx = F->getFrameInfo()->CreateStackObject(Size, Size);
1130
1131     switch (SrcTy) {
1132     case MVT::i64:
1133       // FIXME: this won't work for cast [u]long to FP
1134       addFrameReference(BuildMI(BB, X86::MOV32mr, 5),
1135                         FrameIdx).addReg(Tmp1);
1136       addFrameReference(BuildMI(BB, X86::MOV32mr, 5),
1137                         FrameIdx, 4).addReg(Tmp1+1);
1138       addFrameReference(BuildMI(BB, X86::FILD64m, 5, Result), FrameIdx);
1139       break;
1140     case MVT::i32:
1141       addFrameReference(BuildMI(BB, X86::MOV32mr, 5),
1142                         FrameIdx).addReg(Tmp1);
1143       addFrameReference(BuildMI(BB, X86::FILD32m, 5, Result), FrameIdx);
1144       break;
1145     case MVT::i16:
1146       addFrameReference(BuildMI(BB, X86::MOV16mr, 5),
1147                         FrameIdx).addReg(Tmp1);
1148       addFrameReference(BuildMI(BB, X86::FILD16m, 5, Result), FrameIdx);
1149       break;
1150     default: break; // No promotion required.
1151     }
1152
1153     if (Node->getOpcode() == ISD::UINT_TO_FP && SrcTy == MVT::i32) {
1154       // If this is a cast from uint -> double, we need to be careful when if
1155       // the "sign" bit is set.  If so, we don't want to make a negative number,
1156       // we want to make a positive number.  Emit code to add an offset if the
1157       // sign bit is set.
1158
1159       // Compute whether the sign bit is set by shifting the reg right 31 bits.
1160       unsigned IsNeg = MakeReg(MVT::i32);
1161       BuildMI(BB, X86::SHR32ri, 2, IsNeg).addReg(Tmp1).addImm(31);
1162
1163       // Create a CP value that has the offset in one word and 0 in the other.
1164       static ConstantInt *TheOffset = ConstantUInt::get(Type::ULongTy,
1165                                                         0x4f80000000000000ULL);
1166       unsigned CPI = F->getConstantPool()->getConstantPoolIndex(TheOffset);
1167       BuildMI(BB, X86::FADD32m, 5, RealDestReg).addReg(Result)
1168         .addConstantPoolIndex(CPI).addZImm(4).addReg(IsNeg).addSImm(0);
1169
1170     } else if (Node->getOpcode() == ISD::UINT_TO_FP && SrcTy == MVT::i64) {
1171       // We need special handling for unsigned 64-bit integer sources.  If the
1172       // input number has the "sign bit" set, then we loaded it incorrectly as a
1173       // negative 64-bit number.  In this case, add an offset value.
1174
1175       // Emit a test instruction to see if the dynamic input value was signed.
1176       BuildMI(BB, X86::TEST32rr, 2).addReg(Tmp1+1).addReg(Tmp1+1);
1177
1178       // If the sign bit is set, get a pointer to an offset, otherwise get a
1179       // pointer to a zero.
1180       MachineConstantPool *CP = F->getConstantPool();
1181       unsigned Zero = MakeReg(MVT::i32);
1182       Constant *Null = Constant::getNullValue(Type::UIntTy);
1183       addConstantPoolReference(BuildMI(BB, X86::LEA32r, 5, Zero),
1184                                CP->getConstantPoolIndex(Null));
1185       unsigned Offset = MakeReg(MVT::i32);
1186       Constant *OffsetCst = ConstantUInt::get(Type::UIntTy, 0x5f800000);
1187
1188       addConstantPoolReference(BuildMI(BB, X86::LEA32r, 5, Offset),
1189                                CP->getConstantPoolIndex(OffsetCst));
1190       unsigned Addr = MakeReg(MVT::i32);
1191       BuildMI(BB, X86::CMOVS32rr, 2, Addr).addReg(Zero).addReg(Offset);
1192
1193       // Load the constant for an add.  FIXME: this could make an 'fadd' that
1194       // reads directly from memory, but we don't support these yet.
1195       unsigned ConstReg = MakeReg(MVT::f64);
1196       addDirectMem(BuildMI(BB, X86::FLD32m, 4, ConstReg), Addr);
1197
1198       BuildMI(BB, X86::FpADD, 2, RealDestReg).addReg(ConstReg).addReg(Result);
1199     }
1200     return RealDestReg;
1201   }
1202   case ISD::FP_TO_SINT:
1203   case ISD::FP_TO_UINT: {
1204     // FIXME: Most of this grunt work should be done by legalize!
1205     Tmp1 = SelectExpr(N.getOperand(0));  // Get the operand register
1206
1207     // Change the floating point control register to use "round towards zero"
1208     // mode when truncating to an integer value.
1209     //
1210     MachineFunction *F = BB->getParent();
1211     int CWFrameIdx = F->getFrameInfo()->CreateStackObject(2, 2);
1212     addFrameReference(BuildMI(BB, X86::FNSTCW16m, 4), CWFrameIdx);
1213
1214     // Load the old value of the high byte of the control word...
1215     unsigned HighPartOfCW = MakeReg(MVT::i8);
1216     addFrameReference(BuildMI(BB, X86::MOV8rm, 4, HighPartOfCW),
1217                       CWFrameIdx, 1);
1218
1219     // Set the high part to be round to zero...
1220     addFrameReference(BuildMI(BB, X86::MOV8mi, 5),
1221                       CWFrameIdx, 1).addImm(12);
1222
1223     // Reload the modified control word now...
1224     addFrameReference(BuildMI(BB, X86::FLDCW16m, 4), CWFrameIdx);
1225
1226     // Restore the memory image of control word to original value
1227     addFrameReference(BuildMI(BB, X86::MOV8mr, 5),
1228                       CWFrameIdx, 1).addReg(HighPartOfCW);
1229
1230     // We don't have the facilities for directly storing byte sized data to
1231     // memory.  Promote it to 16 bits.  We also must promote unsigned values to
1232     // larger classes because we only have signed FP stores.
1233     MVT::ValueType StoreClass = Node->getValueType(0);
1234     if (StoreClass == MVT::i8 || Node->getOpcode() == ISD::FP_TO_UINT)
1235       switch (StoreClass) {
1236       case MVT::i8:  StoreClass = MVT::i16; break;
1237       case MVT::i16: StoreClass = MVT::i32; break;
1238       case MVT::i32: StoreClass = MVT::i64; break;
1239         // The following treatment of cLong may not be perfectly right,
1240         // but it survives chains of casts of the form
1241         // double->ulong->double.
1242       case MVT::i64:  StoreClass = MVT::i64;  break;
1243       default: assert(0 && "Unknown store class!");
1244       }
1245
1246     // Spill the integer to memory and reload it from there.
1247     unsigned Size = MVT::getSizeInBits(StoreClass)/8;
1248     int FrameIdx = F->getFrameInfo()->CreateStackObject(Size, Size);
1249
1250     switch (StoreClass) {
1251     default: assert(0 && "Unknown store class!");
1252     case MVT::i16:
1253       addFrameReference(BuildMI(BB, X86::FIST16m, 5), FrameIdx).addReg(Tmp1);
1254       break;
1255     case MVT::i32:
1256       addFrameReference(BuildMI(BB, X86::FIST32m, 5), FrameIdx).addReg(Tmp1);
1257       break;
1258     case MVT::i64:
1259       addFrameReference(BuildMI(BB, X86::FISTP64m, 5), FrameIdx).addReg(Tmp1);
1260       break;
1261     }
1262
1263     switch (Node->getValueType(0)) {
1264     default:
1265       assert(0 && "Unknown integer type!");
1266     case MVT::i64:
1267       // FIXME: this isn't gunna work.
1268       addFrameReference(BuildMI(BB, X86::MOV32rm, 4, Result), FrameIdx);
1269       addFrameReference(BuildMI(BB, X86::MOV32rm, 4, Result+1), FrameIdx, 4);
1270     case MVT::i32:
1271       addFrameReference(BuildMI(BB, X86::MOV32rm, 4, Result), FrameIdx);
1272       break;
1273     case MVT::i16:
1274       addFrameReference(BuildMI(BB, X86::MOV16rm, 4, Result), FrameIdx);
1275       break;
1276     case MVT::i8:
1277       addFrameReference(BuildMI(BB, X86::MOV8rm, 4, Result), FrameIdx);
1278       break;
1279     }
1280
1281     // Reload the original control word now.
1282     addFrameReference(BuildMI(BB, X86::FLDCW16m, 4), CWFrameIdx);
1283     return Result;
1284   }
1285   case ISD::ADD:
1286     Op0 = N.getOperand(0);
1287     Op1 = N.getOperand(1);
1288
1289     if (isFoldableLoad(Op0))
1290       std::swap(Op0, Op1);
1291
1292     if (isFoldableLoad(Op1)) {
1293       switch (N.getValueType()) {
1294       default: assert(0 && "Cannot add this type!");
1295       case MVT::i1:
1296       case MVT::i8:  Opc = X86::ADD8rm;  break;
1297       case MVT::i16: Opc = X86::ADD16rm; break;
1298       case MVT::i32: Opc = X86::ADD32rm; break;
1299       case MVT::f32: Opc = X86::FADD32m; break;
1300       case MVT::f64: Opc = X86::FADD64m; break;
1301       }
1302       X86AddressMode AM;
1303       if (getRegPressure(Op0) > getRegPressure(Op1)) {
1304         Tmp1 = SelectExpr(Op0);
1305         EmitFoldedLoad(Op1, AM);
1306       } else {
1307         EmitFoldedLoad(Op1, AM);
1308         Tmp1 = SelectExpr(Op0);
1309       }
1310       addFullAddress(BuildMI(BB, Opc, 5, Result).addReg(Tmp1), AM);
1311       return Result;
1312     }
1313
1314     // See if we can codegen this as an LEA to fold operations together.
1315     if (N.getValueType() == MVT::i32) {
1316       X86AddressMode AM;
1317       if (!SelectAddress(Op0, AM) && !SelectAddress(Op1, AM)) {
1318         // If this is not just an add, emit the LEA.  For a simple add (like
1319         // reg+reg or reg+imm), we just emit an add.  It might be a good idea to
1320         // leave this as LEA, then peephole it to 'ADD' after two address elim
1321         // happens.
1322         if (AM.Scale != 1 || AM.BaseType == X86AddressMode::FrameIndexBase ||
1323             AM.GV || (AM.Base.Reg && AM.IndexReg && AM.Disp)) {
1324           addFullAddress(BuildMI(BB, X86::LEA32r, 4, Result), AM);
1325           return Result;
1326         }
1327       }
1328     }
1329
1330     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Op1)) {
1331       Opc = 0;
1332       if (CN->getValue() == 1) {   // add X, 1 -> inc X
1333         switch (N.getValueType()) {
1334         default: assert(0 && "Cannot integer add this type!");
1335         case MVT::i8:  Opc = X86::INC8r; break;
1336         case MVT::i16: Opc = X86::INC16r; break;
1337         case MVT::i32: Opc = X86::INC32r; break;
1338         }
1339       } else if (CN->isAllOnesValue()) { // add X, -1 -> dec X
1340         switch (N.getValueType()) {
1341         default: assert(0 && "Cannot integer add this type!");
1342         case MVT::i8:  Opc = X86::DEC8r; break;
1343         case MVT::i16: Opc = X86::DEC16r; break;
1344         case MVT::i32: Opc = X86::DEC32r; break;
1345         }
1346       }
1347
1348       if (Opc) {
1349         Tmp1 = SelectExpr(Op0);
1350         BuildMI(BB, Opc, 1, Result).addReg(Tmp1);
1351         return Result;
1352       }
1353
1354       switch (N.getValueType()) {
1355       default: assert(0 && "Cannot add this type!");
1356       case MVT::i8:  Opc = X86::ADD8ri; break;
1357       case MVT::i16: Opc = X86::ADD16ri; break;
1358       case MVT::i32: Opc = X86::ADD32ri; break;
1359       }
1360       if (Opc) {
1361         Tmp1 = SelectExpr(Op0);
1362         BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(CN->getValue());
1363         return Result;
1364       }
1365     }
1366
1367     switch (N.getValueType()) {
1368     default: assert(0 && "Cannot add this type!");
1369     case MVT::i8:  Opc = X86::ADD8rr; break;
1370     case MVT::i16: Opc = X86::ADD16rr; break;
1371     case MVT::i32: Opc = X86::ADD32rr; break;
1372     case MVT::f32:
1373     case MVT::f64: Opc = X86::FpADD; break;
1374     }
1375
1376     if (getRegPressure(Op0) > getRegPressure(Op1)) {
1377       Tmp1 = SelectExpr(Op0);
1378       Tmp2 = SelectExpr(Op1);
1379     } else {
1380       Tmp2 = SelectExpr(Op1);
1381       Tmp1 = SelectExpr(Op0);
1382     }
1383
1384     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1385     return Result;
1386   case ISD::SUB:
1387   case ISD::MUL:
1388   case ISD::AND:
1389   case ISD::OR:
1390   case ISD::XOR:
1391     static const unsigned SUBTab[] = {
1392       X86::SUB8ri, X86::SUB16ri, X86::SUB32ri, 0, 0,
1393       X86::SUB8rm, X86::SUB16rm, X86::SUB32rm, X86::FSUB32m, X86::FSUB64m,
1394       X86::SUB8rr, X86::SUB16rr, X86::SUB32rr, X86::FpSUB  , X86::FpSUB,
1395     };
1396     static const unsigned MULTab[] = {
1397       0, X86::IMUL16rri, X86::IMUL32rri, 0, 0,
1398       0, X86::IMUL16rm , X86::IMUL32rm, X86::FMUL32m, X86::FMUL64m,
1399       0, X86::IMUL16rr , X86::IMUL32rr, X86::FpMUL  , X86::FpMUL,
1400     };
1401     static const unsigned ANDTab[] = {
1402       X86::AND8ri, X86::AND16ri, X86::AND32ri, 0, 0,
1403       X86::AND8rm, X86::AND16rm, X86::AND32rm, 0, 0,
1404       X86::AND8rr, X86::AND16rr, X86::AND32rr, 0, 0,
1405     };
1406     static const unsigned ORTab[] = {
1407       X86::OR8ri, X86::OR16ri, X86::OR32ri, 0, 0,
1408       X86::OR8rm, X86::OR16rm, X86::OR32rm, 0, 0,
1409       X86::OR8rr, X86::OR16rr, X86::OR32rr, 0, 0,
1410     };
1411     static const unsigned XORTab[] = {
1412       X86::XOR8ri, X86::XOR16ri, X86::XOR32ri, 0, 0,
1413       X86::XOR8rm, X86::XOR16rm, X86::XOR32rm, 0, 0,
1414       X86::XOR8rr, X86::XOR16rr, X86::XOR32rr, 0, 0,
1415     };
1416
1417     Op0 = Node->getOperand(0);
1418     Op1 = Node->getOperand(1);
1419
1420     if (Node->getOpcode() == ISD::SUB && MVT::isInteger(N.getValueType()))
1421       if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(0)))
1422         if (CN->isNullValue()) {   // 0 - N -> neg N
1423           switch (N.getValueType()) {
1424           default: assert(0 && "Cannot sub this type!");
1425           case MVT::i1:
1426           case MVT::i8:  Opc = X86::NEG8r;  break;
1427           case MVT::i16: Opc = X86::NEG16r; break;
1428           case MVT::i32: Opc = X86::NEG32r; break;
1429           }
1430           Tmp1 = SelectExpr(N.getOperand(1));
1431           BuildMI(BB, Opc, 1, Result).addReg(Tmp1);
1432           return Result;
1433         }
1434
1435     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Op1)) {
1436       if (CN->isAllOnesValue() && Node->getOpcode() == ISD::XOR) {
1437         switch (N.getValueType()) {
1438         default: assert(0 && "Cannot add this type!");
1439         case MVT::i1:
1440         case MVT::i8:  Opc = X86::NOT8r;  break;
1441         case MVT::i16: Opc = X86::NOT16r; break;
1442         case MVT::i32: Opc = X86::NOT32r; break;
1443         }
1444         Tmp1 = SelectExpr(Op0);
1445         BuildMI(BB, Opc, 1, Result).addReg(Tmp1);
1446         return Result;
1447       }
1448
1449       switch (N.getValueType()) {
1450       default: assert(0 && "Cannot xor this type!");
1451       case MVT::i1:
1452       case MVT::i8:  Opc = 0; break;
1453       case MVT::i16: Opc = 1; break;
1454       case MVT::i32: Opc = 2; break;
1455       }
1456       switch (Node->getOpcode()) {
1457       default: assert(0 && "Unreachable!");
1458       case ISD::SUB: Opc = SUBTab[Opc]; break;
1459       case ISD::MUL: Opc = MULTab[Opc]; break;
1460       case ISD::AND: Opc = ANDTab[Opc]; break;
1461       case ISD::OR:  Opc =  ORTab[Opc]; break;
1462       case ISD::XOR: Opc = XORTab[Opc]; break;
1463       }
1464       if (Opc) {  // Can't fold MUL:i8 R, imm
1465         Tmp1 = SelectExpr(Op0);
1466         BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(CN->getValue());
1467         return Result;
1468       }
1469     }
1470
1471     if (isFoldableLoad(Op0))
1472       if (Node->getOpcode() != ISD::SUB) {
1473         std::swap(Op0, Op1);
1474       } else {
1475         // Emit 'reverse' subract, with a memory operand.
1476         switch (N.getValueType()) {
1477         default: Opc = 0; break;
1478         case MVT::f32: Opc = X86::FSUBR32m; break;
1479         case MVT::f64: Opc = X86::FSUBR64m; break;
1480         }
1481         if (Opc) {
1482           X86AddressMode AM;
1483           if (getRegPressure(Op0) > getRegPressure(Op1)) {
1484             EmitFoldedLoad(Op0, AM);
1485             Tmp1 = SelectExpr(Op1);
1486           } else {
1487             Tmp1 = SelectExpr(Op1);
1488             EmitFoldedLoad(Op0, AM);
1489           }
1490           addFullAddress(BuildMI(BB, Opc, 5, Result).addReg(Tmp1), AM);
1491           return Result;
1492         }
1493       }
1494
1495     if (isFoldableLoad(Op1)) {
1496       switch (N.getValueType()) {
1497       default: assert(0 && "Cannot operate on this type!");
1498       case MVT::i1:
1499       case MVT::i8:  Opc = 5; break;
1500       case MVT::i16: Opc = 6; break;
1501       case MVT::i32: Opc = 7; break;
1502       case MVT::f32: Opc = 8; break;
1503       case MVT::f64: Opc = 9; break;
1504       }
1505       switch (Node->getOpcode()) {
1506       default: assert(0 && "Unreachable!");
1507       case ISD::SUB: Opc = SUBTab[Opc]; break;
1508       case ISD::MUL: Opc = MULTab[Opc]; break;
1509       case ISD::AND: Opc = ANDTab[Opc]; break;
1510       case ISD::OR:  Opc =  ORTab[Opc]; break;
1511       case ISD::XOR: Opc = XORTab[Opc]; break;
1512       }
1513
1514       X86AddressMode AM;
1515       if (getRegPressure(Op0) > getRegPressure(Op1)) {
1516         Tmp1 = SelectExpr(Op0);
1517         EmitFoldedLoad(Op1, AM);
1518       } else {
1519         EmitFoldedLoad(Op1, AM);
1520         Tmp1 = SelectExpr(Op0);
1521       }
1522       if (Opc) {
1523         addFullAddress(BuildMI(BB, Opc, 5, Result).addReg(Tmp1), AM);
1524       } else {
1525         assert(Node->getOpcode() == ISD::MUL &&
1526                N.getValueType() == MVT::i8 && "Unexpected situation!");
1527         // Must use the MUL instruction, which forces use of AL.
1528         BuildMI(BB, X86::MOV8rr, 1, X86::AL).addReg(Tmp1);
1529         addFullAddress(BuildMI(BB, X86::MUL8m, 1), AM);
1530         BuildMI(BB, X86::MOV8rr, 1, Result).addReg(X86::AL);
1531       }
1532       return Result;
1533     }
1534
1535     if (getRegPressure(Op0) > getRegPressure(Op1)) {
1536       Tmp1 = SelectExpr(Op0);
1537       Tmp2 = SelectExpr(Op1);
1538     } else {
1539       Tmp2 = SelectExpr(Op1);
1540       Tmp1 = SelectExpr(Op0);
1541     }
1542
1543     switch (N.getValueType()) {
1544     default: assert(0 && "Cannot add this type!");
1545     case MVT::i1:
1546     case MVT::i8:  Opc = 10; break;
1547     case MVT::i16: Opc = 11; break;
1548     case MVT::i32: Opc = 12; break;
1549     case MVT::f32: Opc = 13; break;
1550     case MVT::f64: Opc = 14; break;
1551     }
1552     switch (Node->getOpcode()) {
1553     default: assert(0 && "Unreachable!");
1554     case ISD::SUB: Opc = SUBTab[Opc]; break;
1555     case ISD::MUL: Opc = MULTab[Opc]; break;
1556     case ISD::AND: Opc = ANDTab[Opc]; break;
1557     case ISD::OR:  Opc =  ORTab[Opc]; break;
1558     case ISD::XOR: Opc = XORTab[Opc]; break;
1559     }
1560     if (Opc) {
1561       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1562     } else {
1563       assert(Node->getOpcode() == ISD::MUL &&
1564              N.getValueType() == MVT::i8 && "Unexpected situation!");
1565       // Must use the MUL instruction, which forces use of AL.
1566       BuildMI(BB, X86::MOV8rr, 1, X86::AL).addReg(Tmp1);
1567       BuildMI(BB, X86::MUL8r, 1).addReg(Tmp2);
1568       BuildMI(BB, X86::MOV8rr, 1, Result).addReg(X86::AL);
1569     }
1570     return Result;
1571
1572   case ISD::SELECT:
1573     if (N.getValueType() != MVT::i1 && N.getValueType() != MVT::i8) {
1574       if (getRegPressure(N.getOperand(1)) > getRegPressure(N.getOperand(2))) {
1575         Tmp2 = SelectExpr(N.getOperand(1));
1576         Tmp3 = SelectExpr(N.getOperand(2));
1577       } else {
1578         Tmp3 = SelectExpr(N.getOperand(2));
1579         Tmp2 = SelectExpr(N.getOperand(1));
1580       }
1581       EmitSelectCC(N.getOperand(0), N.getValueType(), Tmp2, Tmp3, Result);
1582       return Result;
1583     } else {
1584       // FIXME: This should not be implemented here, it should be in the generic
1585       // code!
1586       if (getRegPressure(N.getOperand(1)) > getRegPressure(N.getOperand(2))) {
1587         Tmp2 = SelectExpr(CurDAG->getNode(ISD::ZERO_EXTEND, MVT::i16,
1588                                           N.getOperand(1)));
1589         Tmp3 = SelectExpr(CurDAG->getNode(ISD::ZERO_EXTEND, MVT::i16,
1590                                           N.getOperand(2)));
1591       } else {
1592         Tmp3 = SelectExpr(CurDAG->getNode(ISD::ZERO_EXTEND, MVT::i16,
1593                                           N.getOperand(2)));
1594         Tmp2 = SelectExpr(CurDAG->getNode(ISD::ZERO_EXTEND, MVT::i16,
1595                                           N.getOperand(1)));
1596       }
1597       unsigned TmpReg = MakeReg(MVT::i16);
1598       EmitSelectCC(N.getOperand(0), MVT::i16, Tmp2, Tmp3, TmpReg);
1599       // FIXME: need subregs to do better than this!
1600       BuildMI(BB, X86::MOV16rr, 1, X86::AX).addReg(TmpReg);
1601       BuildMI(BB, X86::MOV8rr, 1, Result).addReg(X86::AL);
1602       return Result;
1603     }
1604
1605   case ISD::SDIV:
1606   case ISD::UDIV:
1607   case ISD::SREM:
1608   case ISD::UREM: {
1609     if (N.getOpcode() == ISD::SDIV)
1610       if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1611         // FIXME: These special cases should be handled by the lowering impl!
1612         unsigned RHS = CN->getValue();
1613         bool isNeg = false;
1614         if ((int)RHS < 0) {
1615           isNeg = true;
1616           RHS = -RHS;
1617         }
1618         if (RHS && (RHS & (RHS-1)) == 0) {   // Signed division by power of 2?
1619           unsigned Log = log2(RHS);
1620           unsigned TmpReg = MakeReg(N.getValueType());
1621           unsigned SAROpc, SHROpc, ADDOpc, NEGOpc;
1622           switch (N.getValueType()) {
1623           default: assert("Unknown type to signed divide!");
1624           case MVT::i8:
1625             SAROpc = X86::SAR8ri;
1626             SHROpc = X86::SHR8ri;
1627             ADDOpc = X86::ADD8rr;
1628             NEGOpc = X86::NEG8r;
1629             break;
1630           case MVT::i16:
1631             SAROpc = X86::SAR16ri;
1632             SHROpc = X86::SHR16ri;
1633             ADDOpc = X86::ADD16rr;
1634             NEGOpc = X86::NEG16r;
1635             break;
1636           case MVT::i32:
1637             SAROpc = X86::SAR32ri;
1638             SHROpc = X86::SHR32ri;
1639             ADDOpc = X86::ADD32rr;
1640             NEGOpc = X86::NEG32r;
1641             break;
1642           }
1643           Tmp1 = SelectExpr(N.getOperand(0));
1644           BuildMI(BB, SAROpc, 2, TmpReg).addReg(Tmp1).addImm(Log-1);
1645           unsigned TmpReg2 = MakeReg(N.getValueType());
1646           BuildMI(BB, SHROpc, 2, TmpReg2).addReg(TmpReg).addImm(32-Log);
1647           unsigned TmpReg3 = MakeReg(N.getValueType());
1648           BuildMI(BB, ADDOpc, 2, TmpReg3).addReg(Tmp1).addReg(TmpReg2);
1649
1650           unsigned TmpReg4 = isNeg ? MakeReg(N.getValueType()) : Result;
1651           BuildMI(BB, SAROpc, 2, TmpReg4).addReg(TmpReg3).addImm(Log);
1652           if (isNeg)
1653             BuildMI(BB, NEGOpc, 1, Result).addReg(TmpReg4);
1654           return Result;
1655         }
1656       }
1657
1658     if (getRegPressure(N.getOperand(0)) > getRegPressure(N.getOperand(1))) {
1659       Tmp1 = SelectExpr(N.getOperand(0));
1660       Tmp2 = SelectExpr(N.getOperand(1));
1661     } else {
1662       Tmp2 = SelectExpr(N.getOperand(1));
1663       Tmp1 = SelectExpr(N.getOperand(0));
1664     }
1665
1666     bool isSigned = N.getOpcode() == ISD::SDIV || N.getOpcode() == ISD::SREM;
1667     bool isDiv    = N.getOpcode() == ISD::SDIV || N.getOpcode() == ISD::UDIV;
1668     unsigned LoReg, HiReg, DivOpcode, MovOpcode, ClrOpcode, SExtOpcode;
1669     switch (N.getValueType()) {
1670     default: assert(0 && "Cannot sdiv this type!");
1671     case MVT::i8:
1672       DivOpcode = isSigned ? X86::IDIV8r : X86::DIV8r;
1673       LoReg = X86::AL;
1674       HiReg = X86::AH;
1675       MovOpcode = X86::MOV8rr;
1676       ClrOpcode = X86::MOV8ri;
1677       SExtOpcode = X86::CBW;
1678       break;
1679     case MVT::i16:
1680       DivOpcode = isSigned ? X86::IDIV16r : X86::DIV16r;
1681       LoReg = X86::AX;
1682       HiReg = X86::DX;
1683       MovOpcode = X86::MOV16rr;
1684       ClrOpcode = X86::MOV16ri;
1685       SExtOpcode = X86::CWD;
1686       break;
1687     case MVT::i32:
1688       DivOpcode = isSigned ? X86::IDIV32r : X86::DIV32r;
1689       LoReg =X86::EAX;
1690       HiReg = X86::EDX;
1691       MovOpcode = X86::MOV32rr;
1692       ClrOpcode = X86::MOV32ri;
1693       SExtOpcode = X86::CDQ;
1694       break;
1695     case MVT::i64: assert(0 && "FIXME: implement i64 DIV/REM libcalls!");
1696     case MVT::f32:
1697     case MVT::f64:
1698       if (N.getOpcode() == ISD::SDIV)
1699         BuildMI(BB, X86::FpDIV, 2, Result).addReg(Tmp1).addReg(Tmp2);
1700       else
1701         assert(0 && "FIXME: Emit frem libcall to fmod!");
1702       return Result;
1703     }
1704
1705     // Set up the low part.
1706     BuildMI(BB, MovOpcode, 1, LoReg).addReg(Tmp1);
1707
1708     if (isSigned) {
1709       // Sign extend the low part into the high part.
1710       BuildMI(BB, SExtOpcode, 0);
1711     } else {
1712       // Zero out the high part, effectively zero extending the input.
1713       BuildMI(BB, ClrOpcode, 1, HiReg).addImm(0);
1714     }
1715
1716     // Emit the DIV/IDIV instruction.
1717     BuildMI(BB, DivOpcode, 1).addReg(Tmp2);
1718
1719     // Get the result of the divide or rem.
1720     BuildMI(BB, MovOpcode, 1, Result).addReg(isDiv ? LoReg : HiReg);
1721     return Result;
1722   }
1723
1724   case ISD::SHL:
1725     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1726       if (CN->getValue() == 1) {   // X = SHL Y, 1  -> X = ADD Y, Y
1727         switch (N.getValueType()) {
1728         default: assert(0 && "Cannot shift this type!");
1729         case MVT::i8:  Opc = X86::ADD8rr; break;
1730         case MVT::i16: Opc = X86::ADD16rr; break;
1731         case MVT::i32: Opc = X86::ADD32rr; break;
1732         }
1733         Tmp1 = SelectExpr(N.getOperand(0));
1734         BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp1);
1735         return Result;
1736       }
1737
1738       switch (N.getValueType()) {
1739       default: assert(0 && "Cannot shift this type!");
1740       case MVT::i8:  Opc = X86::SHL8ri; break;
1741       case MVT::i16: Opc = X86::SHL16ri; break;
1742       case MVT::i32: Opc = X86::SHL32ri; break;
1743       }
1744       Tmp1 = SelectExpr(N.getOperand(0));
1745       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(CN->getValue());
1746       return Result;
1747     }
1748
1749     if (getRegPressure(N.getOperand(0)) > getRegPressure(N.getOperand(1))) {
1750       Tmp1 = SelectExpr(N.getOperand(0));
1751       Tmp2 = SelectExpr(N.getOperand(1));
1752     } else {
1753       Tmp2 = SelectExpr(N.getOperand(1));
1754       Tmp1 = SelectExpr(N.getOperand(0));
1755     }
1756
1757     switch (N.getValueType()) {
1758     default: assert(0 && "Cannot shift this type!");
1759     case MVT::i8 : Opc = X86::SHL8rCL; break;
1760     case MVT::i16: Opc = X86::SHL16rCL; break;
1761     case MVT::i32: Opc = X86::SHL32rCL; break;
1762     }
1763     BuildMI(BB, X86::MOV8rr, 1, X86::CL).addReg(Tmp2);
1764     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1765     return Result;
1766   case ISD::SRL:
1767     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1768       switch (N.getValueType()) {
1769       default: assert(0 && "Cannot shift this type!");
1770       case MVT::i8:  Opc = X86::SHR8ri; break;
1771       case MVT::i16: Opc = X86::SHR16ri; break;
1772       case MVT::i32: Opc = X86::SHR32ri; break;
1773       }
1774       Tmp1 = SelectExpr(N.getOperand(0));
1775       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(CN->getValue());
1776       return Result;
1777     }
1778
1779     if (getRegPressure(N.getOperand(0)) > getRegPressure(N.getOperand(1))) {
1780       Tmp1 = SelectExpr(N.getOperand(0));
1781       Tmp2 = SelectExpr(N.getOperand(1));
1782     } else {
1783       Tmp2 = SelectExpr(N.getOperand(1));
1784       Tmp1 = SelectExpr(N.getOperand(0));
1785     }
1786
1787     switch (N.getValueType()) {
1788     default: assert(0 && "Cannot shift this type!");
1789     case MVT::i8 : Opc = X86::SHR8rCL; break;
1790     case MVT::i16: Opc = X86::SHR16rCL; break;
1791     case MVT::i32: Opc = X86::SHR32rCL; break;
1792     }
1793     BuildMI(BB, X86::MOV8rr, 1, X86::CL).addReg(Tmp2);
1794     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1795     return Result;
1796   case ISD::SRA:
1797     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1798       switch (N.getValueType()) {
1799       default: assert(0 && "Cannot shift this type!");
1800       case MVT::i8:  Opc = X86::SAR8ri; break;
1801       case MVT::i16: Opc = X86::SAR16ri; break;
1802       case MVT::i32: Opc = X86::SAR32ri; break;
1803       }
1804       Tmp1 = SelectExpr(N.getOperand(0));
1805       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(CN->getValue());
1806       return Result;
1807     }
1808
1809     if (getRegPressure(N.getOperand(0)) > getRegPressure(N.getOperand(1))) {
1810       Tmp1 = SelectExpr(N.getOperand(0));
1811       Tmp2 = SelectExpr(N.getOperand(1));
1812     } else {
1813       Tmp2 = SelectExpr(N.getOperand(1));
1814       Tmp1 = SelectExpr(N.getOperand(0));
1815     }
1816
1817     switch (N.getValueType()) {
1818     default: assert(0 && "Cannot shift this type!");
1819     case MVT::i8 : Opc = X86::SAR8rCL; break;
1820     case MVT::i16: Opc = X86::SAR16rCL; break;
1821     case MVT::i32: Opc = X86::SAR32rCL; break;
1822     }
1823     BuildMI(BB, X86::MOV8rr, 1, X86::CL).addReg(Tmp2);
1824     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1825     return Result;
1826
1827   case ISD::SETCC:
1828     EmitCMP(N.getOperand(0), N.getOperand(1));
1829     EmitSetCC(BB, Result, cast<SetCCSDNode>(N)->getCondition(),
1830               MVT::isFloatingPoint(N.getOperand(1).getValueType()));
1831     return Result;
1832   case ISD::LOAD: {
1833     // Make sure we generate both values.
1834     if (Result != 1)
1835       ExprMap[N.getValue(1)] = 1;   // Generate the token
1836     else
1837       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
1838
1839     switch (Node->getValueType(0)) {
1840     default: assert(0 && "Cannot load this type!");
1841     case MVT::i1:
1842     case MVT::i8:  Opc = X86::MOV8rm; break;
1843     case MVT::i16: Opc = X86::MOV16rm; break;
1844     case MVT::i32: Opc = X86::MOV32rm; break;
1845     case MVT::f32: Opc = X86::FLD32m; ContainsFPCode = true; break;
1846     case MVT::f64: Opc = X86::FLD64m; ContainsFPCode = true; break;
1847     }
1848
1849     if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(N.getOperand(1))){
1850       Select(N.getOperand(0));
1851       addConstantPoolReference(BuildMI(BB, Opc, 4, Result), CP->getIndex());
1852     } else {
1853       X86AddressMode AM;
1854       EmitFoldedLoad(N, AM);
1855       addFullAddress(BuildMI(BB, Opc, 4, Result), AM);
1856     }
1857     return Result;
1858   }
1859   case ISD::DYNAMIC_STACKALLOC:
1860     // Generate both result values.
1861     if (Result != 1)
1862       ExprMap[N.getValue(1)] = 1;   // Generate the token
1863     else
1864       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
1865
1866     // FIXME: We are currently ignoring the requested alignment for handling
1867     // greater than the stack alignment.  This will need to be revisited at some
1868     // point.  Align = N.getOperand(2);
1869
1870     if (!isa<ConstantSDNode>(N.getOperand(2)) ||
1871         cast<ConstantSDNode>(N.getOperand(2))->getValue() != 0) {
1872       std::cerr << "Cannot allocate stack object with greater alignment than"
1873                 << " the stack alignment yet!";
1874       abort();
1875     }
1876
1877     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1878       Select(N.getOperand(0));
1879       BuildMI(BB, X86::SUB32ri, 2, X86::ESP).addReg(X86::ESP)
1880         .addImm(CN->getValue());
1881     } else {
1882       if (getRegPressure(N.getOperand(0)) > getRegPressure(N.getOperand(1))) {
1883         Select(N.getOperand(0));
1884         Tmp1 = SelectExpr(N.getOperand(1));
1885       } else {
1886         Tmp1 = SelectExpr(N.getOperand(1));
1887         Select(N.getOperand(0));
1888       }
1889
1890       // Subtract size from stack pointer, thereby allocating some space.
1891       BuildMI(BB, X86::SUB32rr, 2, X86::ESP).addReg(X86::ESP).addReg(Tmp1);
1892     }
1893
1894     // Put a pointer to the space into the result register, by copying the stack
1895     // pointer.
1896     BuildMI(BB, X86::MOV32rr, 1, Result).addReg(X86::ESP);
1897     return Result;
1898
1899   case ISD::CALL:
1900     // The chain for this call is now lowered.
1901     LoweredTokens.insert(N.getValue(Node->getNumValues()-1));
1902
1903     if (GlobalAddressSDNode *GASD =
1904                dyn_cast<GlobalAddressSDNode>(N.getOperand(1))) {
1905       Select(N.getOperand(0));
1906       BuildMI(BB, X86::CALLpcrel32, 1).addGlobalAddress(GASD->getGlobal(),true);
1907     } else if (ExternalSymbolSDNode *ESSDN =
1908                dyn_cast<ExternalSymbolSDNode>(N.getOperand(1))) {
1909       Select(N.getOperand(0));
1910       BuildMI(BB, X86::CALLpcrel32,
1911               1).addExternalSymbol(ESSDN->getSymbol(), true);
1912     } else {
1913       if (getRegPressure(N.getOperand(0)) > getRegPressure(N.getOperand(1))) {
1914         Select(N.getOperand(0));
1915         Tmp1 = SelectExpr(N.getOperand(1));
1916       } else {
1917         Tmp1 = SelectExpr(N.getOperand(1));
1918         Select(N.getOperand(0));
1919       }
1920
1921       BuildMI(BB, X86::CALL32r, 1).addReg(Tmp1);
1922     }
1923     switch (Node->getValueType(0)) {
1924     default: assert(0 && "Unknown value type for call result!");
1925     case MVT::Other: return 1;
1926     case MVT::i1:
1927     case MVT::i8:
1928       BuildMI(BB, X86::MOV8rr, 1, Result).addReg(X86::AL);
1929       break;
1930     case MVT::i16:
1931       BuildMI(BB, X86::MOV16rr, 1, Result).addReg(X86::AX);
1932       break;
1933     case MVT::i32:
1934       BuildMI(BB, X86::MOV32rr, 1, Result).addReg(X86::EAX);
1935       if (Node->getValueType(1) == MVT::i32)
1936         BuildMI(BB, X86::MOV32rr, 1, Result+1).addReg(X86::EDX);
1937       break;
1938     case MVT::f32:
1939     case MVT::f64:     // Floating-point return values live in %ST(0)
1940       ContainsFPCode = true;
1941       BuildMI(BB, X86::FpGETRESULT, 1, Result);
1942       break;
1943     }
1944     return Result+N.ResNo;
1945   }
1946
1947   return 0;
1948 }
1949
1950 void ISel::Select(SDOperand N) {
1951   unsigned Tmp1, Tmp2, Opc;
1952
1953   // FIXME: Disable for our current expansion model!
1954   if (/*!N->hasOneUse() &&*/ !LoweredTokens.insert(N).second)
1955     return;  // Already selected.
1956
1957   SDNode *Node = N.Val;
1958
1959   switch (Node->getOpcode()) {
1960   default:
1961     Node->dump(); std::cerr << "\n";
1962     assert(0 && "Node not handled yet!");
1963   case ISD::EntryToken: return;  // Noop
1964   case ISD::CopyToReg:
1965     Select(N.getOperand(0));
1966     Tmp1 = SelectExpr(N.getOperand(1));
1967     Tmp2 = cast<CopyRegSDNode>(N)->getReg();
1968
1969     if (Tmp1 != Tmp2) {
1970       switch (N.getOperand(1).getValueType()) {
1971       default: assert(0 && "Invalid type for operation!");
1972       case MVT::i1:
1973       case MVT::i8:  Opc = X86::MOV8rr; break;
1974       case MVT::i16: Opc = X86::MOV16rr; break;
1975       case MVT::i32: Opc = X86::MOV32rr; break;
1976       case MVT::f32:
1977       case MVT::f64: Opc = X86::FpMOV; ContainsFPCode = true; break;
1978       }
1979       BuildMI(BB, Opc, 1, Tmp2).addReg(Tmp1);
1980     }
1981     return;
1982   case ISD::RET:
1983     switch (N.getNumOperands()) {
1984     default:
1985       assert(0 && "Unknown return instruction!");
1986     case 3:
1987       assert(N.getOperand(1).getValueType() == MVT::i32 &&
1988              N.getOperand(2).getValueType() == MVT::i32 &&
1989              "Unknown two-register value!");
1990       if (getRegPressure(N.getOperand(1)) > getRegPressure(N.getOperand(2))) {
1991         Tmp1 = SelectExpr(N.getOperand(1));
1992         Tmp2 = SelectExpr(N.getOperand(2));
1993       } else {
1994         Tmp2 = SelectExpr(N.getOperand(2));
1995         Tmp1 = SelectExpr(N.getOperand(1));
1996       }
1997       Select(N.getOperand(0));
1998
1999       BuildMI(BB, X86::MOV32rr, 1, X86::EAX).addReg(Tmp1);
2000       BuildMI(BB, X86::MOV32rr, 1, X86::EDX).addReg(Tmp2);
2001       // Declare that EAX & EDX are live on exit.
2002       BuildMI(BB, X86::IMPLICIT_USE, 3).addReg(X86::EAX).addReg(X86::EDX)
2003         .addReg(X86::ESP);
2004       break;
2005     case 2:
2006       if (getRegPressure(N.getOperand(0)) > getRegPressure(N.getOperand(1))) {
2007         Select(N.getOperand(0));
2008         Tmp1 = SelectExpr(N.getOperand(1));
2009       } else {
2010         Tmp1 = SelectExpr(N.getOperand(1));
2011         Select(N.getOperand(0));
2012       }
2013       switch (N.getOperand(1).getValueType()) {
2014       default: assert(0 && "All other types should have been promoted!!");
2015       case MVT::f64:
2016         BuildMI(BB, X86::FpSETRESULT, 1).addReg(Tmp1);
2017         // Declare that top-of-stack is live on exit
2018         BuildMI(BB, X86::IMPLICIT_USE, 2).addReg(X86::ST0).addReg(X86::ESP);
2019         break;
2020       case MVT::i32:
2021         BuildMI(BB, X86::MOV32rr, 1, X86::EAX).addReg(Tmp1);
2022         BuildMI(BB, X86::IMPLICIT_USE, 2).addReg(X86::EAX).addReg(X86::ESP);
2023         break;
2024       }
2025       break;
2026     case 1:
2027       Select(N.getOperand(0));
2028       break;
2029     }
2030     BuildMI(BB, X86::RET, 0); // Just emit a 'ret' instruction
2031     return;
2032   case ISD::BR: {
2033     Select(N.getOperand(0));
2034     MachineBasicBlock *Dest =
2035       cast<BasicBlockSDNode>(N.getOperand(1))->getBasicBlock();
2036     BuildMI(BB, X86::JMP, 1).addMBB(Dest);
2037     return;
2038   }
2039
2040   case ISD::BRCOND: {
2041     MachineBasicBlock *Dest =
2042       cast<BasicBlockSDNode>(N.getOperand(2))->getBasicBlock();
2043
2044     // Try to fold a setcc into the branch.  If this fails, emit a test/jne
2045     // pair.
2046     if (EmitBranchCC(Dest, N.getOperand(0), N.getOperand(1))) {
2047       if (getRegPressure(N.getOperand(0)) > getRegPressure(N.getOperand(1))) {
2048         Select(N.getOperand(0));
2049         Tmp1 = SelectExpr(N.getOperand(1));
2050       } else {
2051         Tmp1 = SelectExpr(N.getOperand(1));
2052         Select(N.getOperand(0));
2053       }
2054       BuildMI(BB, X86::TEST8rr, 2).addReg(Tmp1).addReg(Tmp1);
2055       BuildMI(BB, X86::JNE, 1).addMBB(Dest);
2056     }
2057
2058     return;
2059   }
2060   case ISD::LOAD:
2061   case ISD::CALL:
2062   case ISD::DYNAMIC_STACKALLOC:
2063     SelectExpr(N);
2064     return;
2065   case ISD::STORE: {
2066     X86AddressMode AM;
2067
2068     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
2069       Opc = 0;
2070       switch (CN->getValueType(0)) {
2071       default: assert(0 && "Invalid type for operation!");
2072       case MVT::i1:
2073       case MVT::i8:  Opc = X86::MOV8mi; break;
2074       case MVT::i16: Opc = X86::MOV16mi; break;
2075       case MVT::i32: Opc = X86::MOV32mi; break;
2076       case MVT::f32:
2077       case MVT::f64: break;
2078       }
2079       if (Opc) {
2080         if (getRegPressure(N.getOperand(0)) > getRegPressure(N.getOperand(2))) {
2081           Select(N.getOperand(0));
2082           SelectAddress(N.getOperand(2), AM);
2083         } else {
2084           SelectAddress(N.getOperand(2), AM);
2085           Select(N.getOperand(0));
2086         }
2087         addFullAddress(BuildMI(BB, Opc, 4+1), AM).addImm(CN->getValue());
2088         return;
2089       }
2090     }
2091
2092     // Check to see if this is a load/op/store combination.
2093     if (N.getOperand(1).Val->hasOneUse() &&
2094         isFoldableLoad(N.getOperand(0).getValue(0))) {
2095       SDOperand TheLoad = N.getOperand(0).getValue(0);
2096       // Check to see if we are loading the same pointer that we're storing to.
2097       if (TheLoad.getOperand(1) == N.getOperand(2)) {
2098         // See if the stored value is a simple binary operator that uses the
2099         // load as one of its operands.
2100         SDOperand Op = N.getOperand(1);
2101         if (Op.Val->getNumOperands() == 2 &&
2102             (Op.getOperand(0) == TheLoad || Op.getOperand(1) == TheLoad)) {
2103           // Finally, check to see if this is one of the ops we can handle!
2104           static const unsigned ADDTAB[] = {
2105             X86::ADD8mi, X86::ADD16mi, X86::ADD32mi,
2106             X86::ADD8mr, X86::ADD16mr, X86::ADD32mr, 0, 0,
2107           };
2108
2109           const unsigned *TabPtr = 0;
2110           switch (Op.getOpcode()) {
2111           default: break;
2112           case ISD::ADD: TabPtr = ADDTAB; break;
2113           }
2114
2115           if (TabPtr) {
2116             // Handle: [mem] op= CST
2117             SDOperand Op0 = Op.getOperand(0);
2118             SDOperand Op1 = Op.getOperand(1);
2119             if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Op1)) {
2120               switch (CN->getValueType(0)) {
2121               default: break;
2122               case MVT::i1:
2123               case MVT::i8:  Opc = TabPtr[0]; break;
2124               case MVT::i16: Opc = TabPtr[1]; break;
2125               case MVT::i32: Opc = TabPtr[2]; break;
2126               }
2127
2128               if (Opc) {
2129                 if (getRegPressure(TheLoad.getOperand(0)) >
2130                     getRegPressure(TheLoad.getOperand(1))) {
2131                   Select(TheLoad.getOperand(0));
2132                   SelectAddress(TheLoad.getOperand(1), AM);
2133                 } else {
2134                   SelectAddress(TheLoad.getOperand(1), AM);
2135                   Select(TheLoad.getOperand(0));
2136                 }
2137
2138                 addFullAddress(BuildMI(BB, Opc, 4+1),AM).addImm(CN->getValue());
2139                 return;
2140               }
2141             }
2142
2143             // If we have [mem] = V op [mem], try to turn it into:
2144             // [mem] = [mem] op V.
2145             if (Op1 == TheLoad && 1 /*iscommutative*/)
2146               std::swap(Op0, Op1);
2147
2148             if (Op0 == TheLoad) {
2149               switch (Op0.getValueType()) {
2150               default: break;
2151               case MVT::i1:
2152               case MVT::i8:  Opc = TabPtr[3]; break;
2153               case MVT::i16: Opc = TabPtr[4]; break;
2154               case MVT::i32: Opc = TabPtr[5]; break;
2155               case MVT::f32: Opc = TabPtr[6]; break;
2156               case MVT::f64: Opc = TabPtr[7]; break;
2157               }
2158
2159               if (Opc) {
2160                 Select(TheLoad.getOperand(0));
2161                 SelectAddress(TheLoad.getOperand(1), AM);
2162                 unsigned Reg = SelectExpr(Op1);
2163                 addFullAddress(BuildMI(BB, Opc, 4+1),AM).addReg(Reg);
2164                 return;
2165               }
2166             }
2167             //Opc = TabPtr[Opc];
2168           }
2169         }
2170       }
2171     }
2172
2173
2174     switch (N.getOperand(1).getValueType()) {
2175     default: assert(0 && "Cannot store this type!");
2176     case MVT::i1:
2177     case MVT::i8:  Opc = X86::MOV8mr; break;
2178     case MVT::i16: Opc = X86::MOV16mr; break;
2179     case MVT::i32: Opc = X86::MOV32mr; break;
2180     case MVT::f32: Opc = X86::FST32m; break;
2181     case MVT::f64: Opc = X86::FST64m; break;
2182     }
2183
2184     std::vector<std::pair<unsigned, unsigned> > RP;
2185     RP.push_back(std::make_pair(getRegPressure(N.getOperand(0)), 0));
2186     RP.push_back(std::make_pair(getRegPressure(N.getOperand(1)), 1));
2187     RP.push_back(std::make_pair(getRegPressure(N.getOperand(2)), 2));
2188     std::sort(RP.begin(), RP.end());
2189
2190     for (unsigned i = 0; i != 3; ++i)
2191       switch (RP[2-i].second) {
2192       default: assert(0 && "Unknown operand number!");
2193       case 0: Select(N.getOperand(0)); break;
2194       case 1: Tmp1 = SelectExpr(N.getOperand(1)); break;
2195       case 2: SelectAddress(N.getOperand(2), AM); break;
2196       }
2197
2198     addFullAddress(BuildMI(BB, Opc, 4+1), AM).addReg(Tmp1);
2199     return;
2200   }
2201   case ISD::ADJCALLSTACKDOWN:
2202   case ISD::ADJCALLSTACKUP:
2203     Select(N.getOperand(0));
2204     Tmp1 = cast<ConstantSDNode>(N.getOperand(1))->getValue();
2205
2206     Opc = N.getOpcode() == ISD::ADJCALLSTACKDOWN ? X86::ADJCALLSTACKDOWN :
2207                                                    X86::ADJCALLSTACKUP;
2208     BuildMI(BB, Opc, 1).addImm(Tmp1);
2209     return;
2210   case ISD::MEMSET: {
2211     Select(N.getOperand(0));  // Select the chain.
2212     unsigned Align =
2213       (unsigned)cast<ConstantSDNode>(Node->getOperand(4))->getValue();
2214     if (Align == 0) Align = 1;
2215
2216     // Turn the byte code into # iterations
2217     unsigned CountReg;
2218     unsigned Opcode;
2219     if (ConstantSDNode *ValC = dyn_cast<ConstantSDNode>(Node->getOperand(2))) {
2220       unsigned Val = ValC->getValue() & 255;
2221
2222       // If the value is a constant, then we can potentially use larger sets.
2223       switch (Align & 3) {
2224       case 2:   // WORD aligned
2225         CountReg = MakeReg(MVT::i32);
2226         if (ConstantSDNode *I = dyn_cast<ConstantSDNode>(Node->getOperand(3))) {
2227           BuildMI(BB, X86::MOV32ri, 1, CountReg).addImm(I->getValue()/2);
2228         } else {
2229           unsigned ByteReg = SelectExpr(Node->getOperand(3));
2230           BuildMI(BB, X86::SHR32ri, 2, CountReg).addReg(ByteReg).addImm(1);
2231         }
2232         BuildMI(BB, X86::MOV16ri, 1, X86::AX).addImm((Val << 8) | Val);
2233         Opcode = X86::REP_STOSW;
2234         break;
2235       case 0:   // DWORD aligned
2236         CountReg = MakeReg(MVT::i32);
2237         if (ConstantSDNode *I = dyn_cast<ConstantSDNode>(Node->getOperand(3))) {
2238           BuildMI(BB, X86::MOV32ri, 1, CountReg).addImm(I->getValue()/4);
2239         } else {
2240           unsigned ByteReg = SelectExpr(Node->getOperand(3));
2241           BuildMI(BB, X86::SHR32ri, 2, CountReg).addReg(ByteReg).addImm(2);
2242         }
2243         Val = (Val << 8) | Val;
2244         BuildMI(BB, X86::MOV32ri, 1, X86::EAX).addImm((Val << 16) | Val);
2245         Opcode = X86::REP_STOSD;
2246         break;
2247       default:  // BYTE aligned
2248         CountReg = SelectExpr(Node->getOperand(3));
2249         BuildMI(BB, X86::MOV8ri, 1, X86::AL).addImm(Val);
2250         Opcode = X86::REP_STOSB;
2251         break;
2252       }
2253     } else {
2254       // If it's not a constant value we are storing, just fall back.  We could
2255       // try to be clever to form 16 bit and 32 bit values, but we don't yet.
2256       unsigned ValReg = SelectExpr(Node->getOperand(2));
2257       BuildMI(BB, X86::MOV8rr, 1, X86::AL).addReg(ValReg);
2258       CountReg = SelectExpr(Node->getOperand(3));
2259       Opcode = X86::REP_STOSB;
2260     }
2261
2262     // No matter what the alignment is, we put the source in ESI, the
2263     // destination in EDI, and the count in ECX.
2264     unsigned TmpReg1 = SelectExpr(Node->getOperand(1));
2265     BuildMI(BB, X86::MOV32rr, 1, X86::ECX).addReg(CountReg);
2266     BuildMI(BB, X86::MOV32rr, 1, X86::EDI).addReg(TmpReg1);
2267     BuildMI(BB, Opcode, 0);
2268     return;
2269   }
2270   case ISD::MEMCPY:
2271     Select(N.getOperand(0));  // Select the chain.
2272     unsigned Align =
2273       (unsigned)cast<ConstantSDNode>(Node->getOperand(4))->getValue();
2274     if (Align == 0) Align = 1;
2275
2276     // Turn the byte code into # iterations
2277     unsigned CountReg;
2278     unsigned Opcode;
2279     switch (Align & 3) {
2280     case 2:   // WORD aligned
2281       CountReg = MakeReg(MVT::i32);
2282       if (ConstantSDNode *I = dyn_cast<ConstantSDNode>(Node->getOperand(3))) {
2283         BuildMI(BB, X86::MOV32ri, 1, CountReg).addImm(I->getValue()/2);
2284       } else {
2285         unsigned ByteReg = SelectExpr(Node->getOperand(3));
2286         BuildMI(BB, X86::SHR32ri, 2, CountReg).addReg(ByteReg).addImm(1);
2287       }
2288       Opcode = X86::REP_MOVSW;
2289       break;
2290     case 0:   // DWORD aligned
2291       CountReg = MakeReg(MVT::i32);
2292       if (ConstantSDNode *I = dyn_cast<ConstantSDNode>(Node->getOperand(3))) {
2293         BuildMI(BB, X86::MOV32ri, 1, CountReg).addImm(I->getValue()/4);
2294       } else {
2295         unsigned ByteReg = SelectExpr(Node->getOperand(3));
2296         BuildMI(BB, X86::SHR32ri, 2, CountReg).addReg(ByteReg).addImm(2);
2297       }
2298       Opcode = X86::REP_MOVSD;
2299       break;
2300     default:  // BYTE aligned
2301       CountReg = SelectExpr(Node->getOperand(3));
2302       Opcode = X86::REP_MOVSB;
2303       break;
2304     }
2305
2306     // No matter what the alignment is, we put the source in ESI, the
2307     // destination in EDI, and the count in ECX.
2308     unsigned TmpReg1 = SelectExpr(Node->getOperand(1));
2309     unsigned TmpReg2 = SelectExpr(Node->getOperand(2));
2310     BuildMI(BB, X86::MOV32rr, 1, X86::ECX).addReg(CountReg);
2311     BuildMI(BB, X86::MOV32rr, 1, X86::EDI).addReg(TmpReg1);
2312     BuildMI(BB, X86::MOV32rr, 1, X86::ESI).addReg(TmpReg2);
2313     BuildMI(BB, Opcode, 0);
2314     return;
2315   }
2316   assert(0 && "Should not be reached!");
2317 }
2318
2319
2320 /// createX86PatternInstructionSelector - This pass converts an LLVM function
2321 /// into a machine code representation using pattern matching and a machine
2322 /// description file.
2323 ///
2324 FunctionPass *llvm::createX86PatternInstructionSelector(TargetMachine &TM) {
2325   return new ISel(TM);
2326 }