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