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