lib/Target/X86/X86ISelPattern.cpp

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