lib/Target/X86/X86ISelDAGToDAG.cpp

   1 //===- X86ISelDAGToDAG.cpp - A DAG pattern matching inst selector for X86 -===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines a DAG pattern matching instruction selector for X86,
  11 // converting from a legalized dag to a X86 dag.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 // Force NDEBUG on in any optimized build on Darwin.
  16 //
  17 // FIXME: This is a huge hack, to work around ridiculously awful compile times
  18 // on this file with gcc-4.2 on Darwin, in Release mode.
  19 #if (!defined(__llvm__) && defined(__APPLE__) && \
  20      defined(__OPTIMIZE__) && !defined(NDEBUG))
  21 #define NDEBUG
  22 #endif
  23
  24 #define DEBUG_TYPE "x86-isel"
  25 #include "X86.h"
  26 #include "X86InstrBuilder.h"
  27 #include "X86ISelLowering.h"
  28 #include "X86MachineFunctionInfo.h"
  29 #include "X86RegisterInfo.h"
  30 #include "X86Subtarget.h"
  31 #include "X86TargetMachine.h"
  32 #include "llvm/GlobalValue.h"
  33 #include "llvm/Instructions.h"
  34 #include "llvm/Intrinsics.h"
  35 #include "llvm/Support/CFG.h"
  36 #include "llvm/Type.h"
  37 #include "llvm/CodeGen/MachineConstantPool.h"
  38 #include "llvm/CodeGen/MachineFunction.h"
  39 #include "llvm/CodeGen/MachineFrameInfo.h"
  40 #include "llvm/CodeGen/MachineInstrBuilder.h"
  41 #include "llvm/CodeGen/MachineRegisterInfo.h"
  42 #include "llvm/CodeGen/SelectionDAGISel.h"
  43 #include "llvm/Target/TargetMachine.h"
  44 #include "llvm/Target/TargetOptions.h"
  45 #include "llvm/Support/Debug.h"
  46 #include "llvm/Support/ErrorHandling.h"
  47 #include "llvm/Support/MathExtras.h"
  48 #include "llvm/Support/raw_ostream.h"
  49 #include "llvm/ADT/SmallPtrSet.h"
  50 #include "llvm/ADT/Statistic.h"
  51 using namespace llvm;
  52
  53 STATISTIC(NumLoadMoved, "Number of loads moved below TokenFactor");
  54
  55 //===----------------------------------------------------------------------===//
  56 //                      Pattern Matcher Implementation
  57 //===----------------------------------------------------------------------===//
  58
  59 namespace {
  60   /// X86ISelAddressMode - This corresponds to X86AddressMode, but uses
  61   /// SDValue's instead of register numbers for the leaves of the matched
  62   /// tree.
  63   struct X86ISelAddressMode {
  64     enum {
  65       RegBase,
  66       FrameIndexBase
  67     } BaseType;
  68
  69     struct {            // This is really a union, discriminated by BaseType!
  70       SDValue Reg;
  71       int FrameIndex;
  72     } Base;
  73
  74     unsigned Scale;
  75     SDValue IndexReg;
  76     int32_t Disp;
  77     SDValue Segment;
  78     GlobalValue *GV;
  79     Constant *CP;
  80     BlockAddress *BlockAddr;
  81     const char *ES;
  82     int JT;
  83     unsigned Align;    // CP alignment.
  84     unsigned char SymbolFlags;  // X86II::MO_*
  85
  86     X86ISelAddressMode()
  87       : BaseType(RegBase), Scale(1), IndexReg(), Disp(0),
  88         Segment(), GV(0), CP(0), BlockAddr(0), ES(0), JT(-1), Align(0),
  89         SymbolFlags(X86II::MO_NO_FLAG) {
  90     }
  91
  92     bool hasSymbolicDisplacement() const {
  93       return GV != 0 || CP != 0 || ES != 0 || JT != -1 || BlockAddr != 0;
  94     }
  95
  96     bool hasBaseOrIndexReg() const {
  97       return IndexReg.getNode() != 0 || Base.Reg.getNode() != 0;
  98     }
  99
 100     /// isRIPRelative - Return true if this addressing mode is already RIP
 101     /// relative.
 102     bool isRIPRelative() const {
 103       if (BaseType != RegBase) return false;
 104       if (RegisterSDNode *RegNode =
 105             dyn_cast_or_null<RegisterSDNode>(Base.Reg.getNode()))
 106         return RegNode->getReg() == X86::RIP;
 107       return false;
 108     }
 109
 110     void setBaseReg(SDValue Reg) {
 111       BaseType = RegBase;
 112       Base.Reg = Reg;
 113     }
 114
 115     void dump() {
 116       dbgs() << "X86ISelAddressMode " << this << '\n';
 117       dbgs() << "Base.Reg ";
 118       if (Base.Reg.getNode() != 0)
 119         Base.Reg.getNode()->dump();
 120       else
 121         dbgs() << "nul";
 122       dbgs() << " Base.FrameIndex " << Base.FrameIndex << '\n'
 123              << " Scale" << Scale << '\n'
 124              << "IndexReg ";
 125       if (IndexReg.getNode() != 0)
 126         IndexReg.getNode()->dump();
 127       else
 128         dbgs() << "nul";
 129       dbgs() << " Disp " << Disp << '\n'
 130              << "GV ";
 131       if (GV)
 132         GV->dump();
 133       else
 134         dbgs() << "nul";
 135       dbgs() << " CP ";
 136       if (CP)
 137         CP->dump();
 138       else
 139         dbgs() << "nul";
 140       dbgs() << '\n'
 141              << "ES ";
 142       if (ES)
 143         dbgs() << ES;
 144       else
 145         dbgs() << "nul";
 146       dbgs() << " JT" << JT << " Align" << Align << '\n';
 147     }
 148   };
 149 }
 150
 151 namespace {
 152   //===--------------------------------------------------------------------===//
 153   /// ISel - X86 specific code to select X86 machine instructions for
 154   /// SelectionDAG operations.
 155   ///
 156   class X86DAGToDAGISel : public SelectionDAGISel {
 157     /// X86Lowering - This object fully describes how to lower LLVM code to an
 158     /// X86-specific SelectionDAG.
 159     X86TargetLowering &X86Lowering;
 160
 161     /// Subtarget - Keep a pointer to the X86Subtarget around so that we can
 162     /// make the right decision when generating code for different targets.
 163     const X86Subtarget *Subtarget;
 164
 165     /// OptForSize - If true, selector should try to optimize for code size
 166     /// instead of performance.
 167     bool OptForSize;
 168
 169   public:
 170     explicit X86DAGToDAGISel(X86TargetMachine &tm, CodeGenOpt::Level OptLevel)
 171       : SelectionDAGISel(tm, OptLevel),
 172         X86Lowering(*tm.getTargetLowering()),
 173         Subtarget(&tm.getSubtarget<X86Subtarget>()),
 174         OptForSize(false) {}
 175
 176     virtual const char *getPassName() const {
 177       return "X86 DAG->DAG Instruction Selection";
 178     }
 179
 180     /// InstructionSelect - This callback is invoked by
 181     /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
 182     virtual void InstructionSelect();
 183
 184     virtual void EmitFunctionEntryCode(Function &Fn, MachineFunction &MF);
 185
 186     virtual bool IsProfitableToFold(SDValue N, SDNode *U, SDNode *Root) const;
 187
 188     virtual bool IsLegalToFold(SDValue N, SDNode *U, SDNode *Root) const;
 189
 190 // Include the pieces autogenerated from the target description.
 191 #include "X86GenDAGISel.inc"
 192
 193   private:
 194     SDNode *Select(SDNode *N);
 195     SDNode *SelectAtomic64(SDNode *Node, unsigned Opc);
 196     SDNode *SelectAtomicLoadAdd(SDNode *Node, EVT NVT);
 197
 198     bool MatchSegmentBaseAddress(SDValue N, X86ISelAddressMode &AM);
 199     bool MatchLoad(SDValue N, X86ISelAddressMode &AM);
 200     bool MatchWrapper(SDValue N, X86ISelAddressMode &AM);
 201     bool MatchAddress(SDValue N, X86ISelAddressMode &AM);
 202     bool MatchAddressRecursively(SDValue N, X86ISelAddressMode &AM,
 203                                  unsigned Depth);
 204     bool MatchAddressBase(SDValue N, X86ISelAddressMode &AM);
 205     bool SelectAddr(SDNode *Op, SDValue N, SDValue &Base,
 206                     SDValue &Scale, SDValue &Index, SDValue &Disp,
 207                     SDValue &Segment);
 208     bool SelectLEAAddr(SDNode *Op, SDValue N, SDValue &Base,
 209                        SDValue &Scale, SDValue &Index, SDValue &Disp);
 210     bool SelectTLSADDRAddr(SDNode *Op, SDValue N, SDValue &Base,
 211                        SDValue &Scale, SDValue &Index, SDValue &Disp);
 212     bool SelectScalarSSELoad(SDNode *Root, SDValue N,
 213                              SDValue &Base, SDValue &Scale,
 214                              SDValue &Index, SDValue &Disp,
 215                              SDValue &Segment,
 216                              SDValue &PatternChainResult,
 217                              SDValue &PatternInputChain);
 218     bool TryFoldLoad(SDNode *P, SDValue N,
 219                      SDValue &Base, SDValue &Scale,
 220                      SDValue &Index, SDValue &Disp,
 221                      SDValue &Segment);
 222     void PreprocessForRMW();
 223     void PreprocessForFPConvert();
 224
 225     /// SelectInlineAsmMemoryOperand - Implement addressing mode selection for
 226     /// inline asm expressions.
 227     virtual bool SelectInlineAsmMemoryOperand(const SDValue &Op,
 228                                               char ConstraintCode,
 229                                               std::vector<SDValue> &OutOps);
 230
 231     void EmitSpecialCodeForMain(MachineBasicBlock *BB, MachineFrameInfo *MFI);
 232
 233     inline void getAddressOperands(X86ISelAddressMode &AM, SDValue &Base,
 234                                    SDValue &Scale, SDValue &Index,
 235                                    SDValue &Disp, SDValue &Segment) {
 236       Base  = (AM.BaseType == X86ISelAddressMode::FrameIndexBase) ?
 237         CurDAG->getTargetFrameIndex(AM.Base.FrameIndex, TLI.getPointerTy()) :
 238         AM.Base.Reg;
 239       Scale = getI8Imm(AM.Scale);
 240       Index = AM.IndexReg;
 241       // These are 32-bit even in 64-bit mode since RIP relative offset
 242       // is 32-bit.
 243       if (AM.GV)
 244         Disp = CurDAG->getTargetGlobalAddress(AM.GV, MVT::i32, AM.Disp,
 245                                               AM.SymbolFlags);
 246       else if (AM.CP)
 247         Disp = CurDAG->getTargetConstantPool(AM.CP, MVT::i32,
 248                                              AM.Align, AM.Disp, AM.SymbolFlags);
 249       else if (AM.ES)
 250         Disp = CurDAG->getTargetExternalSymbol(AM.ES, MVT::i32, AM.SymbolFlags);
 251       else if (AM.JT != -1)
 252         Disp = CurDAG->getTargetJumpTable(AM.JT, MVT::i32, AM.SymbolFlags);
 253       else if (AM.BlockAddr)
 254         Disp = CurDAG->getBlockAddress(AM.BlockAddr, MVT::i32,
 255                                        true, AM.SymbolFlags);
 256       else
 257         Disp = CurDAG->getTargetConstant(AM.Disp, MVT::i32);
 258
 259       if (AM.Segment.getNode())
 260         Segment = AM.Segment;
 261       else
 262         Segment = CurDAG->getRegister(0, MVT::i32);
 263     }
 264
 265     /// getI8Imm - Return a target constant with the specified value, of type
 266     /// i8.
 267     inline SDValue getI8Imm(unsigned Imm) {
 268       return CurDAG->getTargetConstant(Imm, MVT::i8);
 269     }
 270
 271     /// getI16Imm - Return a target constant with the specified value, of type
 272     /// i16.
 273     inline SDValue getI16Imm(unsigned Imm) {
 274       return CurDAG->getTargetConstant(Imm, MVT::i16);
 275     }
 276
 277     /// getI32Imm - Return a target constant with the specified value, of type
 278     /// i32.
 279     inline SDValue getI32Imm(unsigned Imm) {
 280       return CurDAG->getTargetConstant(Imm, MVT::i32);
 281     }
 282
 283     /// getGlobalBaseReg - Return an SDNode that returns the value of
 284     /// the global base register. Output instructions required to
 285     /// initialize the global base register, if necessary.
 286     ///
 287     SDNode *getGlobalBaseReg();
 288
 289     /// getTargetMachine - Return a reference to the TargetMachine, casted
 290     /// to the target-specific type.
 291     const X86TargetMachine &getTargetMachine() {
 292       return static_cast<const X86TargetMachine &>(TM);
 293     }
 294
 295     /// getInstrInfo - Return a reference to the TargetInstrInfo, casted
 296     /// to the target-specific type.
 297     const X86InstrInfo *getInstrInfo() {
 298       return getTargetMachine().getInstrInfo();
 299     }
 300
 301 #ifndef NDEBUG
 302     unsigned Indent;
 303 #endif
 304   };
 305 }
 306
 307
 308 bool
 309 X86DAGToDAGISel::IsProfitableToFold(SDValue N, SDNode *U, SDNode *Root) const {
 310   if (OptLevel == CodeGenOpt::None) return false;
 311
 312   if (!N.hasOneUse())
 313     return false;
 314
 315   if (N.getOpcode() != ISD::LOAD)
 316     return true;
 317
 318   // If N is a load, do additional profitability checks.
 319   if (U == Root) {
 320     switch (U->getOpcode()) {
 321     default: break;
 322     case X86ISD::ADD:
 323     case X86ISD::SUB:
 324     case X86ISD::AND:
 325     case X86ISD::XOR:
 326     case X86ISD::OR:
 327     case ISD::ADD:
 328     case ISD::ADDC:
 329     case ISD::ADDE:
 330     case ISD::AND:
 331     case ISD::OR:
 332     case ISD::XOR: {
 333       SDValue Op1 = U->getOperand(1);
 334
 335       // If the other operand is a 8-bit immediate we should fold the immediate
 336       // instead. This reduces code size.
 337       // e.g.
 338       // movl 4(%esp), %eax
 339       // addl $4, %eax
 340       // vs.
 341       // movl $4, %eax
 342       // addl 4(%esp), %eax
 343       // The former is 2 bytes shorter. In case where the increment is 1, then
 344       // the saving can be 4 bytes (by using incl %eax).
 345       if (ConstantSDNode *Imm = dyn_cast<ConstantSDNode>(Op1))
 346         if (Imm->getAPIntValue().isSignedIntN(8))
 347           return false;
 348
 349       // If the other operand is a TLS address, we should fold it instead.
 350       // This produces
 351       // movl    %gs:0, %eax
 352       // leal    i@NTPOFF(%eax), %eax
 353       // instead of
 354       // movl    $i@NTPOFF, %eax
 355       // addl    %gs:0, %eax
 356       // if the block also has an access to a second TLS address this will save
 357       // a load.
 358       // FIXME: This is probably also true for non TLS addresses.
 359       if (Op1.getOpcode() == X86ISD::Wrapper) {
 360         SDValue Val = Op1.getOperand(0);
 361         if (Val.getOpcode() == ISD::TargetGlobalTLSAddress)
 362           return false;
 363       }
 364     }
 365     }
 366   }
 367
 368   return true;
 369 }
 370
 371
 372 bool X86DAGToDAGISel::IsLegalToFold(SDValue N, SDNode *U, SDNode *Root) const {
 373   if (OptLevel == CodeGenOpt::None) return false;
 374
 375   // Proceed to 'generic' cycle finder code
 376   return SelectionDAGISel::IsLegalToFold(N, U, Root);
 377 }
 378
 379 /// MoveBelowTokenFactor - Replace TokenFactor operand with load's chain operand
 380 /// and move load below the TokenFactor. Replace store's chain operand with
 381 /// load's chain result.
 382 static void MoveBelowTokenFactor(SelectionDAG *CurDAG, SDValue Load,
 383                                  SDValue Store, SDValue TF) {
 384   SmallVector<SDValue, 4> Ops;
 385   for (unsigned i = 0, e = TF.getNode()->getNumOperands(); i != e; ++i)
 386     if (Load.getNode() == TF.getOperand(i).getNode())
 387       Ops.push_back(Load.getOperand(0));
 388     else
 389       Ops.push_back(TF.getOperand(i));
 390   SDValue NewTF = CurDAG->UpdateNodeOperands(TF, &Ops[0], Ops.size());
 391   SDValue NewLoad = CurDAG->UpdateNodeOperands(Load, NewTF,
 392                                                Load.getOperand(1),
 393                                                Load.getOperand(2));
 394   CurDAG->UpdateNodeOperands(Store, NewLoad.getValue(1), Store.getOperand(1),
 395                              Store.getOperand(2), Store.getOperand(3));
 396 }
 397
 398 /// isRMWLoad - Return true if N is a load that's part of RMW sub-DAG.  The
 399 /// chain produced by the load must only be used by the store's chain operand,
 400 /// otherwise this may produce a cycle in the DAG.
 401 ///
 402 static bool isRMWLoad(SDValue N, SDValue Chain, SDValue Address,
 403                       SDValue &Load) {
 404   if (N.getOpcode() == ISD::BIT_CONVERT) {
 405     if (!N.hasOneUse())
 406       return false;
 407     N = N.getOperand(0);
 408   }
 409
 410   LoadSDNode *LD = dyn_cast<LoadSDNode>(N);
 411   if (!LD || LD->isVolatile())
 412     return false;
 413   if (LD->getAddressingMode() != ISD::UNINDEXED)
 414     return false;
 415
 416   ISD::LoadExtType ExtType = LD->getExtensionType();
 417   if (ExtType != ISD::NON_EXTLOAD && ExtType != ISD::EXTLOAD)
 418     return false;
 419
 420   if (N.hasOneUse() &&
 421       LD->hasNUsesOfValue(1, 1) &&
 422       N.getOperand(1) == Address &&
 423       LD->isOperandOf(Chain.getNode())) {
 424     Load = N;
 425     return true;
 426   }
 427   return false;
 428 }
 429
 430 /// MoveBelowCallSeqStart - Replace CALLSEQ_START operand with load's chain
 431 /// operand and move load below the call's chain operand.
 432 static void MoveBelowCallSeqStart(SelectionDAG *CurDAG, SDValue Load,
 433                                   SDValue Call, SDValue CallSeqStart) {
 434   SmallVector<SDValue, 8> Ops;
 435   SDValue Chain = CallSeqStart.getOperand(0);
 436   if (Chain.getNode() == Load.getNode())
 437     Ops.push_back(Load.getOperand(0));
 438   else {
 439     assert(Chain.getOpcode() == ISD::TokenFactor &&
 440            "Unexpected CallSeqStart chain operand");
 441     for (unsigned i = 0, e = Chain.getNumOperands(); i != e; ++i)
 442       if (Chain.getOperand(i).getNode() == Load.getNode())
 443         Ops.push_back(Load.getOperand(0));
 444       else
 445         Ops.push_back(Chain.getOperand(i));
 446     SDValue NewChain =
 447       CurDAG->getNode(ISD::TokenFactor, Load.getDebugLoc(),
 448                       MVT::Other, &Ops[0], Ops.size());
 449     Ops.clear();
 450     Ops.push_back(NewChain);
 451   }
 452   for (unsigned i = 1, e = CallSeqStart.getNumOperands(); i != e; ++i)
 453     Ops.push_back(CallSeqStart.getOperand(i));
 454   CurDAG->UpdateNodeOperands(CallSeqStart, &Ops[0], Ops.size());
 455   CurDAG->UpdateNodeOperands(Load, Call.getOperand(0),
 456                              Load.getOperand(1), Load.getOperand(2));
 457   Ops.clear();
 458   Ops.push_back(SDValue(Load.getNode(), 1));
 459   for (unsigned i = 1, e = Call.getNode()->getNumOperands(); i != e; ++i)
 460     Ops.push_back(Call.getOperand(i));
 461   CurDAG->UpdateNodeOperands(Call, &Ops[0], Ops.size());
 462 }
 463
 464 /// isCalleeLoad - Return true if call address is a load and it can be
 465 /// moved below CALLSEQ_START and the chains leading up to the call.
 466 /// Return the CALLSEQ_START by reference as a second output.
 467 static bool isCalleeLoad(SDValue Callee, SDValue &Chain) {
 468   if (Callee.getNode() == Chain.getNode() || !Callee.hasOneUse())
 469     return false;
 470   LoadSDNode *LD = dyn_cast<LoadSDNode>(Callee.getNode());
 471   if (!LD ||
 472       LD->isVolatile() ||
 473       LD->getAddressingMode() != ISD::UNINDEXED ||
 474       LD->getExtensionType() != ISD::NON_EXTLOAD)
 475     return false;
 476
 477   // Now let's find the callseq_start.
 478   while (Chain.getOpcode() != ISD::CALLSEQ_START) {
 479     if (!Chain.hasOneUse())
 480       return false;
 481     Chain = Chain.getOperand(0);
 482   }
 483
 484   if (Chain.getOperand(0).getNode() == Callee.getNode())
 485     return true;
 486   if (Chain.getOperand(0).getOpcode() == ISD::TokenFactor &&
 487       Callee.getValue(1).isOperandOf(Chain.getOperand(0).getNode()) &&
 488       Callee.getValue(1).hasOneUse())
 489     return true;
 490   return false;
 491 }
 492
 493
 494 /// PreprocessForRMW - Preprocess the DAG to make instruction selection better.
 495 /// This is only run if not in -O0 mode.
 496 /// This allows the instruction selector to pick more read-modify-write
 497 /// instructions. This is a common case:
 498 ///
 499 ///     [Load chain]
 500 ///         ^
 501 ///         |
 502 ///       [Load]
 503 ///       ^    ^
 504 ///       |    |
 505 ///      /      \-
 506 ///     /         |
 507 /// [TokenFactor] [Op]
 508 ///     ^          ^
 509 ///     |          |
 510 ///      \        /
 511 ///       \      /
 512 ///       [Store]
 513 ///
 514 /// The fact the store's chain operand != load's chain will prevent the
 515 /// (store (op (load))) instruction from being selected. We can transform it to:
 516 ///
 517 ///     [Load chain]
 518 ///         ^
 519 ///         |
 520 ///    [TokenFactor]
 521 ///         ^
 522 ///         |
 523 ///       [Load]
 524 ///       ^    ^
 525 ///       |    |
 526 ///       |     \-
 527 ///       |       |
 528 ///       |     [Op]
 529 ///       |       ^
 530 ///       |       |
 531 ///       \      /
 532 ///        \    /
 533 ///       [Store]
 534 void X86DAGToDAGISel::PreprocessForRMW() {
 535   for (SelectionDAG::allnodes_iterator I = CurDAG->allnodes_begin(),
 536          E = CurDAG->allnodes_end(); I != E; ++I) {
 537     if (I->getOpcode() == X86ISD::CALL) {
 538       /// Also try moving call address load from outside callseq_start to just
 539       /// before the call to allow it to be folded.
 540       ///
 541       ///     [Load chain]
 542       ///         ^
 543       ///         |
 544       ///       [Load]
 545       ///       ^    ^
 546       ///       |    |
 547       ///      /      \--
 548       ///     /          |
 549       ///[CALLSEQ_START] |
 550       ///     ^          |
 551       ///     |          |
 552       /// [LOAD/C2Reg]   |
 553       ///     |          |
 554       ///      \        /
 555       ///       \      /
 556       ///       [CALL]
 557       SDValue Chain = I->getOperand(0);
 558       SDValue Load  = I->getOperand(1);
 559       if (!isCalleeLoad(Load, Chain))
 560         continue;
 561       MoveBelowCallSeqStart(CurDAG, Load, SDValue(I, 0), Chain);
 562       ++NumLoadMoved;
 563       continue;
 564     }
 565
 566     if (!ISD::isNON_TRUNCStore(I))
 567       continue;
 568     SDValue Chain = I->getOperand(0);
 569
 570     if (Chain.getNode()->getOpcode() != ISD::TokenFactor)
 571       continue;
 572
 573     SDValue N1 = I->getOperand(1);
 574     SDValue N2 = I->getOperand(2);
 575     if ((N1.getValueType().isFloatingPoint() &&
 576          !N1.getValueType().isVector()) ||
 577         !N1.hasOneUse())
 578       continue;
 579
 580     bool RModW = false;
 581     SDValue Load;
 582     unsigned Opcode = N1.getNode()->getOpcode();
 583     switch (Opcode) {
 584     case ISD::ADD:
 585     case ISD::MUL:
 586     case ISD::AND:
 587     case ISD::OR:
 588     case ISD::XOR:
 589     case ISD::ADDC:
 590     case ISD::ADDE:
 591     case ISD::VECTOR_SHUFFLE: {
 592       SDValue N10 = N1.getOperand(0);
 593       SDValue N11 = N1.getOperand(1);
 594       RModW = isRMWLoad(N10, Chain, N2, Load);
 595       if (!RModW)
 596         RModW = isRMWLoad(N11, Chain, N2, Load);
 597       break;
 598     }
 599     case ISD::SUB:
 600     case ISD::SHL:
 601     case ISD::SRA:
 602     case ISD::SRL:
 603     case ISD::ROTL:
 604     case ISD::ROTR:
 605     case ISD::SUBC:
 606     case ISD::SUBE:
 607     case X86ISD::SHLD:
 608     case X86ISD::SHRD: {
 609       SDValue N10 = N1.getOperand(0);
 610       RModW = isRMWLoad(N10, Chain, N2, Load);
 611       break;
 612     }
 613     }
 614
 615     if (RModW) {
 616       MoveBelowTokenFactor(CurDAG, Load, SDValue(I, 0), Chain);
 617       ++NumLoadMoved;
 618       checkForCycles(I);
 619     }
 620   }
 621 }
 622
 623
 624 /// PreprocessForFPConvert - Walk over the dag lowering fpround and fpextend
 625 /// nodes that target the FP stack to be store and load to the stack.  This is a
 626 /// gross hack.  We would like to simply mark these as being illegal, but when
 627 /// we do that, legalize produces these when it expands calls, then expands
 628 /// these in the same legalize pass.  We would like dag combine to be able to
 629 /// hack on these between the call expansion and the node legalization.  As such
 630 /// this pass basically does "really late" legalization of these inline with the
 631 /// X86 isel pass.
 632 void X86DAGToDAGISel::PreprocessForFPConvert() {
 633   for (SelectionDAG::allnodes_iterator I = CurDAG->allnodes_begin(),
 634        E = CurDAG->allnodes_end(); I != E; ) {
 635     SDNode *N = I++;  // Preincrement iterator to avoid invalidation issues.
 636     if (N->getOpcode() != ISD::FP_ROUND && N->getOpcode() != ISD::FP_EXTEND)
 637       continue;
 638
 639     // If the source and destination are SSE registers, then this is a legal
 640     // conversion that should not be lowered.
 641     EVT SrcVT = N->getOperand(0).getValueType();
 642     EVT DstVT = N->getValueType(0);
 643     bool SrcIsSSE = X86Lowering.isScalarFPTypeInSSEReg(SrcVT);
 644     bool DstIsSSE = X86Lowering.isScalarFPTypeInSSEReg(DstVT);
 645     if (SrcIsSSE && DstIsSSE)
 646       continue;
 647
 648     if (!SrcIsSSE && !DstIsSSE) {
 649       // If this is an FPStack extension, it is a noop.
 650       if (N->getOpcode() == ISD::FP_EXTEND)
 651         continue;
 652       // If this is a value-preserving FPStack truncation, it is a noop.
 653       if (N->getConstantOperandVal(1))
 654         continue;
 655     }
 656
 657     // Here we could have an FP stack truncation or an FPStack <-> SSE convert.
 658     // FPStack has extload and truncstore.  SSE can fold direct loads into other
 659     // operations.  Based on this, decide what we want to do.
 660     EVT MemVT;
 661     if (N->getOpcode() == ISD::FP_ROUND)
 662       MemVT = DstVT;  // FP_ROUND must use DstVT, we can't do a 'trunc load'.
 663     else
 664       MemVT = SrcIsSSE ? SrcVT : DstVT;
 665
 666     SDValue MemTmp = CurDAG->CreateStackTemporary(MemVT);
 667     DebugLoc dl = N->getDebugLoc();
 668
 669     // FIXME: optimize the case where the src/dest is a load or store?
 670     SDValue Store = CurDAG->getTruncStore(CurDAG->getEntryNode(), dl,
 671                                           N->getOperand(0),
 672                                           MemTmp, NULL, 0, MemVT,
 673                                           false, false, 0);
 674     SDValue Result = CurDAG->getExtLoad(ISD::EXTLOAD, dl, DstVT, Store, MemTmp,
 675                                         NULL, 0, MemVT, false, false, 0);
 676
 677     // We're about to replace all uses of the FP_ROUND/FP_EXTEND with the
 678     // extload we created.  This will cause general havok on the dag because
 679     // anything below the conversion could be folded into other existing nodes.
 680     // To avoid invalidating 'I', back it up to the convert node.
 681     --I;
 682     CurDAG->ReplaceAllUsesOfValueWith(SDValue(N, 0), Result);
 683
 684     // Now that we did that, the node is dead.  Increment the iterator to the
 685     // next node to process, then delete N.
 686     ++I;
 687     CurDAG->DeleteNode(N);
 688   }
 689 }
 690
 691 /// InstructionSelectBasicBlock - This callback is invoked by SelectionDAGISel
 692 /// when it has created a SelectionDAG for us to codegen.
 693 void X86DAGToDAGISel::InstructionSelect() {
 694   const Function *F = MF->getFunction();
 695   OptForSize = F->hasFnAttr(Attribute::OptimizeForSize);
 696
 697   if (OptLevel != CodeGenOpt::None)
 698     PreprocessForRMW();
 699
 700   // FIXME: This should only happen when not compiled with -O0.
 701   PreprocessForFPConvert();
 702
 703   // Codegen the basic block.
 704 #ifndef NDEBUG
 705   DEBUG(dbgs() << "===== Instruction selection begins:\n");
 706   Indent = 0;
 707 #endif
 708   SelectRoot(*CurDAG);
 709 #ifndef NDEBUG
 710   DEBUG(dbgs() << "===== Instruction selection ends:\n");
 711 #endif
 712
 713   CurDAG->RemoveDeadNodes();
 714 }
 715
 716 /// EmitSpecialCodeForMain - Emit any code that needs to be executed only in
 717 /// the main function.
 718 void X86DAGToDAGISel::EmitSpecialCodeForMain(MachineBasicBlock *BB,
 719                                              MachineFrameInfo *MFI) {
 720   const TargetInstrInfo *TII = TM.getInstrInfo();
 721   if (Subtarget->isTargetCygMing())
 722     BuildMI(BB, DebugLoc::getUnknownLoc(),
 723             TII->get(X86::CALLpcrel32)).addExternalSymbol("__main");
 724 }
 725
 726 void X86DAGToDAGISel::EmitFunctionEntryCode(Function &Fn, MachineFunction &MF) {
 727   // If this is main, emit special code for main.
 728   MachineBasicBlock *BB = MF.begin();
 729   if (Fn.hasExternalLinkage() && Fn.getName() == "main")
 730     EmitSpecialCodeForMain(BB, MF.getFrameInfo());
 731 }
 732
 733
 734 bool X86DAGToDAGISel::MatchSegmentBaseAddress(SDValue N,
 735                                               X86ISelAddressMode &AM) {
 736   assert(N.getOpcode() == X86ISD::SegmentBaseAddress);
 737   SDValue Segment = N.getOperand(0);
 738
 739   if (AM.Segment.getNode() == 0) {
 740     AM.Segment = Segment;
 741     return false;
 742   }
 743
 744   return true;
 745 }
 746
 747 bool X86DAGToDAGISel::MatchLoad(SDValue N, X86ISelAddressMode &AM) {
 748   // This optimization is valid because the GNU TLS model defines that
 749   // gs:0 (or fs:0 on X86-64) contains its own address.
 750   // For more information see http://people.redhat.com/drepper/tls.pdf
 751
 752   SDValue Address = N.getOperand(1);
 753   if (Address.getOpcode() == X86ISD::SegmentBaseAddress &&
 754       !MatchSegmentBaseAddress (Address, AM))
 755     return false;
 756
 757   return true;
 758 }
 759
 760 /// MatchWrapper - Try to match X86ISD::Wrapper and X86ISD::WrapperRIP nodes
 761 /// into an addressing mode.  These wrap things that will resolve down into a
 762 /// symbol reference.  If no match is possible, this returns true, otherwise it
 763 /// returns false.
 764 bool X86DAGToDAGISel::MatchWrapper(SDValue N, X86ISelAddressMode &AM) {
 765   // If the addressing mode already has a symbol as the displacement, we can
 766   // never match another symbol.
 767   if (AM.hasSymbolicDisplacement())
 768     return true;
 769
 770   SDValue N0 = N.getOperand(0);
 771   CodeModel::Model M = TM.getCodeModel();
 772
 773   // Handle X86-64 rip-relative addresses.  We check this before checking direct
 774   // folding because RIP is preferable to non-RIP accesses.
 775   if (Subtarget->is64Bit() &&
 776       // Under X86-64 non-small code model, GV (and friends) are 64-bits, so
 777       // they cannot be folded into immediate fields.
 778       // FIXME: This can be improved for kernel and other models?
 779       (M == CodeModel::Small || M == CodeModel::Kernel) &&
 780       // Base and index reg must be 0 in order to use %rip as base and lowering
 781       // must allow RIP.
 782       !AM.hasBaseOrIndexReg() && N.getOpcode() == X86ISD::WrapperRIP) {
 783     if (GlobalAddressSDNode *G = dyn_cast<GlobalAddressSDNode>(N0)) {
 784       int64_t Offset = AM.Disp + G->getOffset();
 785       if (!X86::isOffsetSuitableForCodeModel(Offset, M)) return true;
 786       AM.GV = G->getGlobal();
 787       AM.Disp = Offset;
 788       AM.SymbolFlags = G->getTargetFlags();
 789     } else if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(N0)) {
 790       int64_t Offset = AM.Disp + CP->getOffset();
 791       if (!X86::isOffsetSuitableForCodeModel(Offset, M)) return true;
 792       AM.CP = CP->getConstVal();
 793       AM.Align = CP->getAlignment();
 794       AM.Disp = Offset;
 795       AM.SymbolFlags = CP->getTargetFlags();
 796     } else if (ExternalSymbolSDNode *S = dyn_cast<ExternalSymbolSDNode>(N0)) {
 797       AM.ES = S->getSymbol();
 798       AM.SymbolFlags = S->getTargetFlags();
 799     } else if (JumpTableSDNode *J = dyn_cast<JumpTableSDNode>(N0)) {
 800       AM.JT = J->getIndex();
 801       AM.SymbolFlags = J->getTargetFlags();
 802     } else {
 803       AM.BlockAddr = cast<BlockAddressSDNode>(N0)->getBlockAddress();
 804       AM.SymbolFlags = cast<BlockAddressSDNode>(N0)->getTargetFlags();
 805     }
 806
 807     if (N.getOpcode() == X86ISD::WrapperRIP)
 808       AM.setBaseReg(CurDAG->getRegister(X86::RIP, MVT::i64));
 809     return false;
 810   }
 811
 812   // Handle the case when globals fit in our immediate field: This is true for
 813   // X86-32 always and X86-64 when in -static -mcmodel=small mode.  In 64-bit
 814   // mode, this results in a non-RIP-relative computation.
 815   if (!Subtarget->is64Bit() ||
 816       ((M == CodeModel::Small || M == CodeModel::Kernel) &&
 817        TM.getRelocationModel() == Reloc::Static)) {
 818     if (GlobalAddressSDNode *G = dyn_cast<GlobalAddressSDNode>(N0)) {
 819       AM.GV = G->getGlobal();
 820       AM.Disp += G->getOffset();
 821       AM.SymbolFlags = G->getTargetFlags();
 822     } else if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(N0)) {
 823       AM.CP = CP->getConstVal();
 824       AM.Align = CP->getAlignment();
 825       AM.Disp += CP->getOffset();
 826       AM.SymbolFlags = CP->getTargetFlags();
 827     } else if (ExternalSymbolSDNode *S = dyn_cast<ExternalSymbolSDNode>(N0)) {
 828       AM.ES = S->getSymbol();
 829       AM.SymbolFlags = S->getTargetFlags();
 830     } else if (JumpTableSDNode *J = dyn_cast<JumpTableSDNode>(N0)) {
 831       AM.JT = J->getIndex();
 832       AM.SymbolFlags = J->getTargetFlags();
 833     } else {
 834       AM.BlockAddr = cast<BlockAddressSDNode>(N0)->getBlockAddress();
 835       AM.SymbolFlags = cast<BlockAddressSDNode>(N0)->getTargetFlags();
 836     }
 837     return false;
 838   }
 839
 840   return true;
 841 }
 842
 843 /// MatchAddress - Add the specified node to the specified addressing mode,
 844 /// returning true if it cannot be done.  This just pattern matches for the
 845 /// addressing mode.
 846 bool X86DAGToDAGISel::MatchAddress(SDValue N, X86ISelAddressMode &AM) {
 847   if (MatchAddressRecursively(N, AM, 0))
 848     return true;
 849
 850   // Post-processing: Convert lea(,%reg,2) to lea(%reg,%reg), which has
 851   // a smaller encoding and avoids a scaled-index.
 852   if (AM.Scale == 2 &&
 853       AM.BaseType == X86ISelAddressMode::RegBase &&
 854       AM.Base.Reg.getNode() == 0) {
 855     AM.Base.Reg = AM.IndexReg;
 856     AM.Scale = 1;
 857   }
 858
 859   // Post-processing: Convert foo to foo(%rip), even in non-PIC mode,
 860   // because it has a smaller encoding.
 861   // TODO: Which other code models can use this?
 862   if (TM.getCodeModel() == CodeModel::Small &&
 863       Subtarget->is64Bit() &&
 864       AM.Scale == 1 &&
 865       AM.BaseType == X86ISelAddressMode::RegBase &&
 866       AM.Base.Reg.getNode() == 0 &&
 867       AM.IndexReg.getNode() == 0 &&
 868       AM.SymbolFlags == X86II::MO_NO_FLAG &&
 869       AM.hasSymbolicDisplacement())
 870     AM.Base.Reg = CurDAG->getRegister(X86::RIP, MVT::i64);
 871
 872   return false;
 873 }
 874
 875 bool X86DAGToDAGISel::MatchAddressRecursively(SDValue N, X86ISelAddressMode &AM,
 876                                               unsigned Depth) {
 877   bool is64Bit = Subtarget->is64Bit();
 878   DebugLoc dl = N.getDebugLoc();
 879   DEBUG({
 880       dbgs() << "MatchAddress: ";
 881       AM.dump();
 882     });
 883   // Limit recursion.
 884   if (Depth > 5)
 885     return MatchAddressBase(N, AM);
 886
 887   CodeModel::Model M = TM.getCodeModel();
 888
 889   // If this is already a %rip relative address, we can only merge immediates
 890   // into it.  Instead of handling this in every case, we handle it here.
 891   // RIP relative addressing: %rip + 32-bit displacement!
 892   if (AM.isRIPRelative()) {
 893     // FIXME: JumpTable and ExternalSymbol address currently don't like
 894     // displacements.  It isn't very important, but this should be fixed for
 895     // consistency.
 896     if (!AM.ES && AM.JT != -1) return true;
 897
 898     if (ConstantSDNode *Cst = dyn_cast<ConstantSDNode>(N)) {
 899       int64_t Val = AM.Disp + Cst->getSExtValue();
 900       if (X86::isOffsetSuitableForCodeModel(Val, M,
 901                                             AM.hasSymbolicDisplacement())) {
 902         AM.Disp = Val;
 903         return false;
 904       }
 905     }
 906     return true;
 907   }
 908
 909   switch (N.getOpcode()) {
 910   default: break;
 911   case ISD::Constant: {
 912     uint64_t Val = cast<ConstantSDNode>(N)->getSExtValue();
 913     if (!is64Bit ||
 914         X86::isOffsetSuitableForCodeModel(AM.Disp + Val, M,
 915                                           AM.hasSymbolicDisplacement())) {
 916       AM.Disp += Val;
 917       return false;
 918     }
 919     break;
 920   }
 921
 922   case X86ISD::SegmentBaseAddress:
 923     if (!MatchSegmentBaseAddress(N, AM))
 924       return false;
 925     break;
 926
 927   case X86ISD::Wrapper:
 928   case X86ISD::WrapperRIP:
 929     if (!MatchWrapper(N, AM))
 930       return false;
 931     break;
 932
 933   case ISD::LOAD:
 934     if (!MatchLoad(N, AM))
 935       return false;
 936     break;
 937
 938   case ISD::FrameIndex:
 939     if (AM.BaseType == X86ISelAddressMode::RegBase
 940         && AM.Base.Reg.getNode() == 0) {
 941       AM.BaseType = X86ISelAddressMode::FrameIndexBase;
 942       AM.Base.FrameIndex = cast<FrameIndexSDNode>(N)->getIndex();
 943       return false;
 944     }
 945     break;
 946
 947   case ISD::SHL:
 948     if (AM.IndexReg.getNode() != 0 || AM.Scale != 1)
 949       break;
 950
 951     if (ConstantSDNode
 952           *CN = dyn_cast<ConstantSDNode>(N.getNode()->getOperand(1))) {
 953       unsigned Val = CN->getZExtValue();
 954       // Note that we handle x<<1 as (,x,2) rather than (x,x) here so
 955       // that the base operand remains free for further matching. If
 956       // the base doesn't end up getting used, a post-processing step
 957       // in MatchAddress turns (,x,2) into (x,x), which is cheaper.
 958       if (Val == 1 || Val == 2 || Val == 3) {
 959         AM.Scale = 1 << Val;
 960         SDValue ShVal = N.getNode()->getOperand(0);
 961
 962         // Okay, we know that we have a scale by now.  However, if the scaled
 963         // value is an add of something and a constant, we can fold the
 964         // constant into the disp field here.
 965         if (ShVal.getNode()->getOpcode() == ISD::ADD &&
 966             isa<ConstantSDNode>(ShVal.getNode()->getOperand(1))) {
 967           AM.IndexReg = ShVal.getNode()->getOperand(0);
 968           ConstantSDNode *AddVal =
 969             cast<ConstantSDNode>(ShVal.getNode()->getOperand(1));
 970           uint64_t Disp = AM.Disp + (AddVal->getSExtValue() << Val);
 971           if (!is64Bit ||
 972               X86::isOffsetSuitableForCodeModel(Disp, M,
 973                                                 AM.hasSymbolicDisplacement()))
 974             AM.Disp = Disp;
 975           else
 976             AM.IndexReg = ShVal;
 977         } else {
 978           AM.IndexReg = ShVal;
 979         }
 980         return false;
 981       }
 982     break;
 983     }
 984
 985   case ISD::SMUL_LOHI:
 986   case ISD::UMUL_LOHI:
 987     // A mul_lohi where we need the low part can be folded as a plain multiply.
 988     if (N.getResNo() != 0) break;
 989     // FALL THROUGH
 990   case ISD::MUL:
 991   case X86ISD::MUL_IMM:
 992     // X*[3,5,9] -> X+X*[2,4,8]
 993     if (AM.BaseType == X86ISelAddressMode::RegBase &&
 994         AM.Base.Reg.getNode() == 0 &&
 995         AM.IndexReg.getNode() == 0) {
 996       if (ConstantSDNode
 997             *CN = dyn_cast<ConstantSDNode>(N.getNode()->getOperand(1)))
 998         if (CN->getZExtValue() == 3 || CN->getZExtValue() == 5 ||
 999             CN->getZExtValue() == 9) {
1000           AM.Scale = unsigned(CN->getZExtValue())-1;
1001
1002           SDValue MulVal = N.getNode()->getOperand(0);
1003           SDValue Reg;
1004
1005           // Okay, we know that we have a scale by now.  However, if the scaled
1006           // value is an add of something and a constant, we can fold the
1007           // constant into the disp field here.
1008           if (MulVal.getNode()->getOpcode() == ISD::ADD && MulVal.hasOneUse() &&
1009               isa<ConstantSDNode>(MulVal.getNode()->getOperand(1))) {
1010             Reg = MulVal.getNode()->getOperand(0);
1011             ConstantSDNode *AddVal =
1012               cast<ConstantSDNode>(MulVal.getNode()->getOperand(1));
1013             uint64_t Disp = AM.Disp + AddVal->getSExtValue() *
1014                                       CN->getZExtValue();
1015             if (!is64Bit ||
1016                 X86::isOffsetSuitableForCodeModel(Disp, M,
1017                                                   AM.hasSymbolicDisplacement()))
1018               AM.Disp = Disp;
1019             else
1020               Reg = N.getNode()->getOperand(0);
1021           } else {
1022             Reg = N.getNode()->getOperand(0);
1023           }
1024
1025           AM.IndexReg = AM.Base.Reg = Reg;
1026           return false;
1027         }
1028     }
1029     break;
1030
1031   case ISD::SUB: {
1032     // Given A-B, if A can be completely folded into the address and
1033     // the index field with the index field unused, use -B as the index.
1034     // This is a win if a has multiple parts that can be folded into
1035     // the address. Also, this saves a mov if the base register has
1036     // other uses, since it avoids a two-address sub instruction, however
1037     // it costs an additional mov if the index register has other uses.
1038
1039     // Test if the LHS of the sub can be folded.
1040     X86ISelAddressMode Backup = AM;
1041     if (MatchAddressRecursively(N.getNode()->getOperand(0), AM, Depth+1)) {
1042       AM = Backup;
1043       break;
1044     }
1045     // Test if the index field is free for use.
1046     if (AM.IndexReg.getNode() || AM.isRIPRelative()) {
1047       AM = Backup;
1048       break;
1049     }
1050     int Cost = 0;
1051     SDValue RHS = N.getNode()->getOperand(1);
1052     // If the RHS involves a register with multiple uses, this
1053     // transformation incurs an extra mov, due to the neg instruction
1054     // clobbering its operand.
1055     if (!RHS.getNode()->hasOneUse() ||
1056         RHS.getNode()->getOpcode() == ISD::CopyFromReg ||
1057         RHS.getNode()->getOpcode() == ISD::TRUNCATE ||
1058         RHS.getNode()->getOpcode() == ISD::ANY_EXTEND ||
1059         (RHS.getNode()->getOpcode() == ISD::ZERO_EXTEND &&
1060          RHS.getNode()->getOperand(0).getValueType() == MVT::i32))
1061       ++Cost;
1062     // If the base is a register with multiple uses, this
1063     // transformation may save a mov.
1064     if ((AM.BaseType == X86ISelAddressMode::RegBase &&
1065          AM.Base.Reg.getNode() &&
1066          !AM.Base.Reg.getNode()->hasOneUse()) ||
1067         AM.BaseType == X86ISelAddressMode::FrameIndexBase)
1068       --Cost;
1069     // If the folded LHS was interesting, this transformation saves
1070     // address arithmetic.
1071     if ((AM.hasSymbolicDisplacement() && !Backup.hasSymbolicDisplacement()) +
1072         ((AM.Disp != 0) && (Backup.Disp == 0)) +
1073         (AM.Segment.getNode() && !Backup.Segment.getNode()) >= 2)
1074       --Cost;
1075     // If it doesn't look like it may be an overall win, don't do it.
1076     if (Cost >= 0) {
1077       AM = Backup;
1078       break;
1079     }
1080
1081     // Ok, the transformation is legal and appears profitable. Go for it.
1082     SDValue Zero = CurDAG->getConstant(0, N.getValueType());
1083     SDValue Neg = CurDAG->getNode(ISD::SUB, dl, N.getValueType(), Zero, RHS);
1084     AM.IndexReg = Neg;
1085     AM.Scale = 1;
1086
1087     // Insert the new nodes into the topological ordering.
1088     if (Zero.getNode()->getNodeId() == -1 ||
1089         Zero.getNode()->getNodeId() > N.getNode()->getNodeId()) {
1090       CurDAG->RepositionNode(N.getNode(), Zero.getNode());
1091       Zero.getNode()->setNodeId(N.getNode()->getNodeId());
1092     }
1093     if (Neg.getNode()->getNodeId() == -1 ||
1094         Neg.getNode()->getNodeId() > N.getNode()->getNodeId()) {
1095       CurDAG->RepositionNode(N.getNode(), Neg.getNode());
1096       Neg.getNode()->setNodeId(N.getNode()->getNodeId());
1097     }
1098     return false;
1099   }
1100
1101   case ISD::ADD: {
1102     X86ISelAddressMode Backup = AM;
1103     if (!MatchAddressRecursively(N.getNode()->getOperand(0), AM, Depth+1) &&
1104         !MatchAddressRecursively(N.getNode()->getOperand(1), AM, Depth+1))
1105       return false;
1106     AM = Backup;
1107     if (!MatchAddressRecursively(N.getNode()->getOperand(1), AM, Depth+1) &&
1108         !MatchAddressRecursively(N.getNode()->getOperand(0), AM, Depth+1))
1109       return false;
1110     AM = Backup;
1111
1112     // If we couldn't fold both operands into the address at the same time,
1113     // see if we can just put each operand into a register and fold at least
1114     // the add.
1115     if (AM.BaseType == X86ISelAddressMode::RegBase &&
1116         !AM.Base.Reg.getNode() &&
1117         !AM.IndexReg.getNode()) {
1118       AM.Base.Reg = N.getNode()->getOperand(0);
1119       AM.IndexReg = N.getNode()->getOperand(1);
1120       AM.Scale = 1;
1121       return false;
1122     }
1123     break;
1124   }
1125
1126   case ISD::OR:
1127     // Handle "X | C" as "X + C" iff X is known to have C bits clear.
1128     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1129       X86ISelAddressMode Backup = AM;
1130       uint64_t Offset = CN->getSExtValue();
1131       // Start with the LHS as an addr mode.
1132       if (!MatchAddressRecursively(N.getOperand(0), AM, Depth+1) &&
1133           // Address could not have picked a GV address for the displacement.
1134           AM.GV == NULL &&
1135           // On x86-64, the resultant disp must fit in 32-bits.
1136           (!is64Bit ||
1137            X86::isOffsetSuitableForCodeModel(AM.Disp + Offset, M,
1138                                              AM.hasSymbolicDisplacement())) &&
1139           // Check to see if the LHS & C is zero.
1140           CurDAG->MaskedValueIsZero(N.getOperand(0), CN->getAPIntValue())) {
1141         AM.Disp += Offset;
1142         return false;
1143       }
1144       AM = Backup;
1145     }
1146     break;
1147
1148   case ISD::AND: {
1149     // Perform some heroic transforms on an and of a constant-count shift
1150     // with a constant to enable use of the scaled offset field.
1151
1152     SDValue Shift = N.getOperand(0);
1153     if (Shift.getNumOperands() != 2) break;
1154
1155     // Scale must not be used already.
1156     if (AM.IndexReg.getNode() != 0 || AM.Scale != 1) break;
1157
1158     SDValue X = Shift.getOperand(0);
1159     ConstantSDNode *C2 = dyn_cast<ConstantSDNode>(N.getOperand(1));
1160     ConstantSDNode *C1 = dyn_cast<ConstantSDNode>(Shift.getOperand(1));
1161     if (!C1 || !C2) break;
1162
1163     // Handle "(X >> (8-C1)) & C2" as "(X >> 8) & 0xff)" if safe. This
1164     // allows us to convert the shift and and into an h-register extract and
1165     // a scaled index.
1166     if (Shift.getOpcode() == ISD::SRL && Shift.hasOneUse()) {
1167       unsigned ScaleLog = 8 - C1->getZExtValue();
1168       if (ScaleLog > 0 && ScaleLog < 4 &&
1169           C2->getZExtValue() == (UINT64_C(0xff) << ScaleLog)) {
1170         SDValue Eight = CurDAG->getConstant(8, MVT::i8);
1171         SDValue Mask = CurDAG->getConstant(0xff, N.getValueType());
1172         SDValue Srl = CurDAG->getNode(ISD::SRL, dl, N.getValueType(),
1173                                       X, Eight);
1174         SDValue And = CurDAG->getNode(ISD::AND, dl, N.getValueType(),
1175                                       Srl, Mask);
1176         SDValue ShlCount = CurDAG->getConstant(ScaleLog, MVT::i8);
1177         SDValue Shl = CurDAG->getNode(ISD::SHL, dl, N.getValueType(),
1178                                       And, ShlCount);
1179
1180         // Insert the new nodes into the topological ordering.
1181         if (Eight.getNode()->getNodeId() == -1 ||
1182             Eight.getNode()->getNodeId() > X.getNode()->getNodeId()) {
1183           CurDAG->RepositionNode(X.getNode(), Eight.getNode());
1184           Eight.getNode()->setNodeId(X.getNode()->getNodeId());
1185         }
1186         if (Mask.getNode()->getNodeId() == -1 ||
1187             Mask.getNode()->getNodeId() > X.getNode()->getNodeId()) {
1188           CurDAG->RepositionNode(X.getNode(), Mask.getNode());
1189           Mask.getNode()->setNodeId(X.getNode()->getNodeId());
1190         }
1191         if (Srl.getNode()->getNodeId() == -1 ||
1192             Srl.getNode()->getNodeId() > Shift.getNode()->getNodeId()) {
1193           CurDAG->RepositionNode(Shift.getNode(), Srl.getNode());
1194           Srl.getNode()->setNodeId(Shift.getNode()->getNodeId());
1195         }
1196         if (And.getNode()->getNodeId() == -1 ||
1197             And.getNode()->getNodeId() > N.getNode()->getNodeId()) {
1198           CurDAG->RepositionNode(N.getNode(), And.getNode());
1199           And.getNode()->setNodeId(N.getNode()->getNodeId());
1200         }
1201         if (ShlCount.getNode()->getNodeId() == -1 ||
1202             ShlCount.getNode()->getNodeId() > X.getNode()->getNodeId()) {
1203           CurDAG->RepositionNode(X.getNode(), ShlCount.getNode());
1204           ShlCount.getNode()->setNodeId(N.getNode()->getNodeId());
1205         }
1206         if (Shl.getNode()->getNodeId() == -1 ||
1207             Shl.getNode()->getNodeId() > N.getNode()->getNodeId()) {
1208           CurDAG->RepositionNode(N.getNode(), Shl.getNode());
1209           Shl.getNode()->setNodeId(N.getNode()->getNodeId());
1210         }
1211         CurDAG->ReplaceAllUsesWith(N, Shl);
1212         AM.IndexReg = And;
1213         AM.Scale = (1 << ScaleLog);
1214         return false;
1215       }
1216     }
1217
1218     // Handle "(X << C1) & C2" as "(X & (C2>>C1)) << C1" if safe and if this
1219     // allows us to fold the shift into this addressing mode.
1220     if (Shift.getOpcode() != ISD::SHL) break;
1221
1222     // Not likely to be profitable if either the AND or SHIFT node has more
1223     // than one use (unless all uses are for address computation). Besides,
1224     // isel mechanism requires their node ids to be reused.
1225     if (!N.hasOneUse() || !Shift.hasOneUse())
1226       break;
1227
1228     // Verify that the shift amount is something we can fold.
1229     unsigned ShiftCst = C1->getZExtValue();
1230     if (ShiftCst != 1 && ShiftCst != 2 && ShiftCst != 3)
1231       break;
1232
1233     // Get the new AND mask, this folds to a constant.
1234     SDValue NewANDMask = CurDAG->getNode(ISD::SRL, dl, N.getValueType(),
1235                                          SDValue(C2, 0), SDValue(C1, 0));
1236     SDValue NewAND = CurDAG->getNode(ISD::AND, dl, N.getValueType(), X,
1237                                      NewANDMask);
1238     SDValue NewSHIFT = CurDAG->getNode(ISD::SHL, dl, N.getValueType(),
1239                                        NewAND, SDValue(C1, 0));
1240
1241     // Insert the new nodes into the topological ordering.
1242     if (C1->getNodeId() > X.getNode()->getNodeId()) {
1243       CurDAG->RepositionNode(X.getNode(), C1);
1244       C1->setNodeId(X.getNode()->getNodeId());
1245     }
1246     if (NewANDMask.getNode()->getNodeId() == -1 ||
1247         NewANDMask.getNode()->getNodeId() > X.getNode()->getNodeId()) {
1248       CurDAG->RepositionNode(X.getNode(), NewANDMask.getNode());
1249       NewANDMask.getNode()->setNodeId(X.getNode()->getNodeId());
1250     }
1251     if (NewAND.getNode()->getNodeId() == -1 ||
1252         NewAND.getNode()->getNodeId() > Shift.getNode()->getNodeId()) {
1253       CurDAG->RepositionNode(Shift.getNode(), NewAND.getNode());
1254       NewAND.getNode()->setNodeId(Shift.getNode()->getNodeId());
1255     }
1256     if (NewSHIFT.getNode()->getNodeId() == -1 ||
1257         NewSHIFT.getNode()->getNodeId() > N.getNode()->getNodeId()) {
1258       CurDAG->RepositionNode(N.getNode(), NewSHIFT.getNode());
1259       NewSHIFT.getNode()->setNodeId(N.getNode()->getNodeId());
1260     }
1261
1262     CurDAG->ReplaceAllUsesWith(N, NewSHIFT);
1263
1264     AM.Scale = 1 << ShiftCst;
1265     AM.IndexReg = NewAND;
1266     return false;
1267   }
1268   }
1269
1270   return MatchAddressBase(N, AM);
1271 }
1272
1273 /// MatchAddressBase - Helper for MatchAddress. Add the specified node to the
1274 /// specified addressing mode without any further recursion.
1275 bool X86DAGToDAGISel::MatchAddressBase(SDValue N, X86ISelAddressMode &AM) {
1276   // Is the base register already occupied?
1277   if (AM.BaseType != X86ISelAddressMode::RegBase || AM.Base.Reg.getNode()) {
1278     // If so, check to see if the scale index register is set.
1279     if (AM.IndexReg.getNode() == 0) {
1280       AM.IndexReg = N;
1281       AM.Scale = 1;
1282       return false;
1283     }
1284
1285     // Otherwise, we cannot select it.
1286     return true;
1287   }
1288
1289   // Default, generate it as a register.
1290   AM.BaseType = X86ISelAddressMode::RegBase;
1291   AM.Base.Reg = N;
1292   return false;
1293 }
1294
1295 /// SelectAddr - returns true if it is able pattern match an addressing mode.
1296 /// It returns the operands which make up the maximal addressing mode it can
1297 /// match by reference.
1298 bool X86DAGToDAGISel::SelectAddr(SDNode *Op, SDValue N, SDValue &Base,
1299                                  SDValue &Scale, SDValue &Index,
1300                                  SDValue &Disp, SDValue &Segment) {
1301   X86ISelAddressMode AM;
1302   if (MatchAddress(N, AM))
1303     return false;
1304
1305   EVT VT = N.getValueType();
1306   if (AM.BaseType == X86ISelAddressMode::RegBase) {
1307     if (!AM.Base.Reg.getNode())
1308       AM.Base.Reg = CurDAG->getRegister(0, VT);
1309   }
1310
1311   if (!AM.IndexReg.getNode())
1312     AM.IndexReg = CurDAG->getRegister(0, VT);
1313
1314   getAddressOperands(AM, Base, Scale, Index, Disp, Segment);
1315   return true;
1316 }
1317
1318 /// SelectScalarSSELoad - Match a scalar SSE load.  In particular, we want to
1319 /// match a load whose top elements are either undef or zeros.  The load flavor
1320 /// is derived from the type of N, which is either v4f32 or v2f64.
1321 ///
1322 /// We also return:
1323 ///  PatternInputChain: this is the chain node input to the pattern that the
1324 ///    newly selected instruction should use.
1325 ///  PatternChainResult: this is chain result matched by the pattern which
1326 ///    should be replaced with the chain result of the matched node.
1327 bool X86DAGToDAGISel::SelectScalarSSELoad(SDNode *Root,
1328                                           SDValue N, SDValue &Base,
1329                                           SDValue &Scale, SDValue &Index,
1330                                           SDValue &Disp, SDValue &Segment,
1331                                           SDValue &PatternChainResult,
1332                                           SDValue &PatternInputChain) {
1333   if (N.getOpcode() == ISD::SCALAR_TO_VECTOR) {
1334     PatternChainResult = N.getOperand(0).getValue(1);
1335     if (ISD::isNON_EXTLoad(PatternChainResult.getNode()) &&
1336         PatternChainResult.getValue(0).hasOneUse() &&
1337         IsProfitableToFold(N.getOperand(0),PatternChainResult.getNode(),Root) &&
1338         IsLegalToFold(N.getOperand(0), N.getNode(), Root)) {
1339       LoadSDNode *LD = cast<LoadSDNode>(PatternChainResult);
1340       if (!SelectAddr(Root, LD->getBasePtr(), Base, Scale, Index, Disp,Segment))
1341         return false;
1342       PatternInputChain = LD->getChain();
1343       return true;
1344     }
1345   }
1346
1347   // Also handle the case where we explicitly require zeros in the top
1348   // elements.  This is a vector shuffle from the zero vector.
1349   if (N.getOpcode() == X86ISD::VZEXT_MOVL && N.getNode()->hasOneUse() &&
1350       // Check to see if the top elements are all zeros (or bitcast of zeros).
1351       N.getOperand(0).getOpcode() == ISD::SCALAR_TO_VECTOR &&
1352       N.getOperand(0).getNode()->hasOneUse() &&
1353       ISD::isNON_EXTLoad(N.getOperand(0).getOperand(0).getNode()) &&
1354       N.getOperand(0).getOperand(0).hasOneUse() &&
1355       IsProfitableToFold(N.getOperand(0), N.getNode(), Root) &&
1356       IsLegalToFold(N.getOperand(0), N.getNode(), Root)) {
1357     // Okay, this is a zero extending load.  Fold it.
1358     LoadSDNode *LD = cast<LoadSDNode>(N.getOperand(0).getOperand(0));
1359     if (!SelectAddr(Root, LD->getBasePtr(), Base, Scale, Index, Disp, Segment))
1360       return false;
1361     PatternInputChain = LD->getChain();
1362     PatternChainResult = SDValue(LD, 1);
1363     return true;
1364   }
1365   return false;
1366 }
1367
1368
1369 /// SelectLEAAddr - it calls SelectAddr and determines if the maximal addressing
1370 /// mode it matches can be cost effectively emitted as an LEA instruction.
1371 bool X86DAGToDAGISel::SelectLEAAddr(SDNode *Op, SDValue N,
1372                                     SDValue &Base, SDValue &Scale,
1373                                     SDValue &Index, SDValue &Disp) {
1374   X86ISelAddressMode AM;
1375
1376   // Set AM.Segment to prevent MatchAddress from using one. LEA doesn't support
1377   // segments.
1378   SDValue Copy = AM.Segment;
1379   SDValue T = CurDAG->getRegister(0, MVT::i32);
1380   AM.Segment = T;
1381   if (MatchAddress(N, AM))
1382     return false;
1383   assert (T == AM.Segment);
1384   AM.Segment = Copy;
1385
1386   EVT VT = N.getValueType();
1387   unsigned Complexity = 0;
1388   if (AM.BaseType == X86ISelAddressMode::RegBase)
1389     if (AM.Base.Reg.getNode())
1390       Complexity = 1;
1391     else
1392       AM.Base.Reg = CurDAG->getRegister(0, VT);
1393   else if (AM.BaseType == X86ISelAddressMode::FrameIndexBase)
1394     Complexity = 4;
1395
1396   if (AM.IndexReg.getNode())
1397     Complexity++;
1398   else
1399     AM.IndexReg = CurDAG->getRegister(0, VT);
1400
1401   // Don't match just leal(,%reg,2). It's cheaper to do addl %reg, %reg, or with
1402   // a simple shift.
1403   if (AM.Scale > 1)
1404     Complexity++;
1405
1406   // FIXME: We are artificially lowering the criteria to turn ADD %reg, $GA
1407   // to a LEA. This is determined with some expermentation but is by no means
1408   // optimal (especially for code size consideration). LEA is nice because of
1409   // its three-address nature. Tweak the cost function again when we can run
1410   // convertToThreeAddress() at register allocation time.
1411   if (AM.hasSymbolicDisplacement()) {
1412     // For X86-64, we should always use lea to materialize RIP relative
1413     // addresses.
1414     if (Subtarget->is64Bit())
1415       Complexity = 4;
1416     else
1417       Complexity += 2;
1418   }
1419
1420   if (AM.Disp && (AM.Base.Reg.getNode() || AM.IndexReg.getNode()))
1421     Complexity++;
1422
1423   // If it isn't worth using an LEA, reject it.
1424   if (Complexity <= 2)
1425     return false;
1426
1427   SDValue Segment;
1428   getAddressOperands(AM, Base, Scale, Index, Disp, Segment);
1429   return true;
1430 }
1431
1432 /// SelectTLSADDRAddr - This is only run on TargetGlobalTLSAddress nodes.
1433 bool X86DAGToDAGISel::SelectTLSADDRAddr(SDNode *Op, SDValue N, SDValue &Base,
1434                                         SDValue &Scale, SDValue &Index,
1435                                         SDValue &Disp) {
1436   assert(N.getOpcode() == ISD::TargetGlobalTLSAddress);
1437   const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
1438
1439   X86ISelAddressMode AM;
1440   AM.GV = GA->getGlobal();
1441   AM.Disp += GA->getOffset();
1442   AM.Base.Reg = CurDAG->getRegister(0, N.getValueType());
1443   AM.SymbolFlags = GA->getTargetFlags();
1444
1445   if (N.getValueType() == MVT::i32) {
1446     AM.Scale = 1;
1447     AM.IndexReg = CurDAG->getRegister(X86::EBX, MVT::i32);
1448   } else {
1449     AM.IndexReg = CurDAG->getRegister(0, MVT::i64);
1450   }
1451
1452   SDValue Segment;
1453   getAddressOperands(AM, Base, Scale, Index, Disp, Segment);
1454   return true;
1455 }
1456
1457
1458 bool X86DAGToDAGISel::TryFoldLoad(SDNode *P, SDValue N,
1459                                   SDValue &Base, SDValue &Scale,
1460                                   SDValue &Index, SDValue &Disp,
1461                                   SDValue &Segment) {
1462   if (ISD::isNON_EXTLoad(N.getNode()) &&
1463       IsProfitableToFold(N, P, P) &&
1464       IsLegalToFold(N, P, P))
1465     return SelectAddr(P, N.getOperand(1), Base, Scale, Index, Disp, Segment);
1466   return false;
1467 }
1468
1469 /// getGlobalBaseReg - Return an SDNode that returns the value of
1470 /// the global base register. Output instructions required to
1471 /// initialize the global base register, if necessary.
1472 ///
1473 SDNode *X86DAGToDAGISel::getGlobalBaseReg() {
1474   unsigned GlobalBaseReg = getInstrInfo()->getGlobalBaseReg(MF);
1475   return CurDAG->getRegister(GlobalBaseReg, TLI.getPointerTy()).getNode();
1476 }
1477
1478 static SDNode *FindCallStartFromCall(SDNode *Node) {
1479   if (Node->getOpcode() == ISD::CALLSEQ_START) return Node;
1480     assert(Node->getOperand(0).getValueType() == MVT::Other &&
1481          "Node doesn't have a token chain argument!");
1482   return FindCallStartFromCall(Node->getOperand(0).getNode());
1483 }
1484
1485 SDNode *X86DAGToDAGISel::SelectAtomic64(SDNode *Node, unsigned Opc) {
1486   SDValue Chain = Node->getOperand(0);
1487   SDValue In1 = Node->getOperand(1);
1488   SDValue In2L = Node->getOperand(2);
1489   SDValue In2H = Node->getOperand(3);
1490   SDValue Tmp0, Tmp1, Tmp2, Tmp3, Tmp4;
1491   if (!SelectAddr(In1.getNode(), In1, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4))
1492     return NULL;
1493   MachineSDNode::mmo_iterator MemOp = MF->allocateMemRefsArray(1);
1494   MemOp[0] = cast<MemSDNode>(Node)->getMemOperand();
1495   const SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, In2L, In2H, Chain};
1496   SDNode *ResNode = CurDAG->getMachineNode(Opc, Node->getDebugLoc(),
1497                                            MVT::i32, MVT::i32, MVT::Other, Ops,
1498                                            array_lengthof(Ops));
1499   cast<MachineSDNode>(ResNode)->setMemRefs(MemOp, MemOp + 1);
1500   return ResNode;
1501 }
1502
1503 SDNode *X86DAGToDAGISel::SelectAtomicLoadAdd(SDNode *Node, EVT NVT) {
1504   if (Node->hasAnyUseOfValue(0))
1505     return 0;
1506
1507   // Optimize common patterns for __sync_add_and_fetch and
1508   // __sync_sub_and_fetch where the result is not used. This allows us
1509   // to use "lock" version of add, sub, inc, dec instructions.
1510   // FIXME: Do not use special instructions but instead add the "lock"
1511   // prefix to the target node somehow. The extra information will then be
1512   // transferred to machine instruction and it denotes the prefix.
1513   SDValue Chain = Node->getOperand(0);
1514   SDValue Ptr = Node->getOperand(1);
1515   SDValue Val = Node->getOperand(2);
1516   SDValue Tmp0, Tmp1, Tmp2, Tmp3, Tmp4;
1517   if (!SelectAddr(Ptr.getNode(), Ptr, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4))
1518     return 0;
1519
1520   bool isInc = false, isDec = false, isSub = false, isCN = false;
1521   ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Val);
1522   if (CN) {
1523     isCN = true;
1524     int64_t CNVal = CN->getSExtValue();
1525     if (CNVal == 1)
1526       isInc = true;
1527     else if (CNVal == -1)
1528       isDec = true;
1529     else if (CNVal >= 0)
1530       Val = CurDAG->getTargetConstant(CNVal, NVT);
1531     else {
1532       isSub = true;
1533       Val = CurDAG->getTargetConstant(-CNVal, NVT);
1534     }
1535   } else if (Val.hasOneUse() &&
1536              Val.getOpcode() == ISD::SUB &&
1537              X86::isZeroNode(Val.getOperand(0))) {
1538     isSub = true;
1539     Val = Val.getOperand(1);
1540   }
1541
1542   unsigned Opc = 0;
1543   switch (NVT.getSimpleVT().SimpleTy) {
1544   default: return 0;
1545   case MVT::i8:
1546     if (isInc)
1547       Opc = X86::LOCK_INC8m;
1548     else if (isDec)
1549       Opc = X86::LOCK_DEC8m;
1550     else if (isSub) {
1551       if (isCN)
1552         Opc = X86::LOCK_SUB8mi;
1553       else
1554         Opc = X86::LOCK_SUB8mr;
1555     } else {
1556       if (isCN)
1557         Opc = X86::LOCK_ADD8mi;
1558       else
1559         Opc = X86::LOCK_ADD8mr;
1560     }
1561     break;
1562   case MVT::i16:
1563     if (isInc)
1564       Opc = X86::LOCK_INC16m;
1565     else if (isDec)
1566       Opc = X86::LOCK_DEC16m;
1567     else if (isSub) {
1568       if (isCN) {
1569         if (Predicate_i16immSExt8(Val.getNode()))
1570           Opc = X86::LOCK_SUB16mi8;
1571         else
1572           Opc = X86::LOCK_SUB16mi;
1573       } else
1574         Opc = X86::LOCK_SUB16mr;
1575     } else {
1576       if (isCN) {
1577         if (Predicate_i16immSExt8(Val.getNode()))
1578           Opc = X86::LOCK_ADD16mi8;
1579         else
1580           Opc = X86::LOCK_ADD16mi;
1581       } else
1582         Opc = X86::LOCK_ADD16mr;
1583     }
1584     break;
1585   case MVT::i32:
1586     if (isInc)
1587       Opc = X86::LOCK_INC32m;
1588     else if (isDec)
1589       Opc = X86::LOCK_DEC32m;
1590     else if (isSub) {
1591       if (isCN) {
1592         if (Predicate_i32immSExt8(Val.getNode()))
1593           Opc = X86::LOCK_SUB32mi8;
1594         else
1595           Opc = X86::LOCK_SUB32mi;
1596       } else
1597         Opc = X86::LOCK_SUB32mr;
1598     } else {
1599       if (isCN) {
1600         if (Predicate_i32immSExt8(Val.getNode()))
1601           Opc = X86::LOCK_ADD32mi8;
1602         else
1603           Opc = X86::LOCK_ADD32mi;
1604       } else
1605         Opc = X86::LOCK_ADD32mr;
1606     }
1607     break;
1608   case MVT::i64:
1609     if (isInc)
1610       Opc = X86::LOCK_INC64m;
1611     else if (isDec)
1612       Opc = X86::LOCK_DEC64m;
1613     else if (isSub) {
1614       Opc = X86::LOCK_SUB64mr;
1615       if (isCN) {
1616         if (Predicate_i64immSExt8(Val.getNode()))
1617           Opc = X86::LOCK_SUB64mi8;
1618         else if (Predicate_i64immSExt32(Val.getNode()))
1619           Opc = X86::LOCK_SUB64mi32;
1620       }
1621     } else {
1622       Opc = X86::LOCK_ADD64mr;
1623       if (isCN) {
1624         if (Predicate_i64immSExt8(Val.getNode()))
1625           Opc = X86::LOCK_ADD64mi8;
1626         else if (Predicate_i64immSExt32(Val.getNode()))
1627           Opc = X86::LOCK_ADD64mi32;
1628       }
1629     }
1630     break;
1631   }
1632
1633   DebugLoc dl = Node->getDebugLoc();
1634   SDValue Undef = SDValue(CurDAG->getMachineNode(TargetOpcode::IMPLICIT_DEF,
1635                                                  dl, NVT), 0);
1636   MachineSDNode::mmo_iterator MemOp = MF->allocateMemRefsArray(1);
1637   MemOp[0] = cast<MemSDNode>(Node)->getMemOperand();
1638   if (isInc || isDec) {
1639     SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, Chain };
1640     SDValue Ret = SDValue(CurDAG->getMachineNode(Opc, dl, MVT::Other, Ops, 6), 0);
1641     cast<MachineSDNode>(Ret)->setMemRefs(MemOp, MemOp + 1);
1642     SDValue RetVals[] = { Undef, Ret };
1643     return CurDAG->getMergeValues(RetVals, 2, dl).getNode();
1644   } else {
1645     SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, Val, Chain };
1646     SDValue Ret = SDValue(CurDAG->getMachineNode(Opc, dl, MVT::Other, Ops, 7), 0);
1647     cast<MachineSDNode>(Ret)->setMemRefs(MemOp, MemOp + 1);
1648     SDValue RetVals[] = { Undef, Ret };
1649     return CurDAG->getMergeValues(RetVals, 2, dl).getNode();
1650   }
1651 }
1652
1653 /// HasNoSignedComparisonUses - Test whether the given X86ISD::CMP node has
1654 /// any uses which require the SF or OF bits to be accurate.
1655 static bool HasNoSignedComparisonUses(SDNode *N) {
1656   // Examine each user of the node.
1657   for (SDNode::use_iterator UI = N->use_begin(),
1658          UE = N->use_end(); UI != UE; ++UI) {
1659     // Only examine CopyToReg uses.
1660     if (UI->getOpcode() != ISD::CopyToReg)
1661       return false;
1662     // Only examine CopyToReg uses that copy to EFLAGS.
1663     if (cast<RegisterSDNode>(UI->getOperand(1))->getReg() !=
1664           X86::EFLAGS)
1665       return false;
1666     // Examine each user of the CopyToReg use.
1667     for (SDNode::use_iterator FlagUI = UI->use_begin(),
1668            FlagUE = UI->use_end(); FlagUI != FlagUE; ++FlagUI) {
1669       // Only examine the Flag result.
1670       if (FlagUI.getUse().getResNo() != 1) continue;
1671       // Anything unusual: assume conservatively.
1672       if (!FlagUI->isMachineOpcode()) return false;
1673       // Examine the opcode of the user.
1674       switch (FlagUI->getMachineOpcode()) {
1675       // These comparisons don't treat the most significant bit specially.
1676       case X86::SETAr: case X86::SETAEr: case X86::SETBr: case X86::SETBEr:
1677       case X86::SETEr: case X86::SETNEr: case X86::SETPr: case X86::SETNPr:
1678       case X86::SETAm: case X86::SETAEm: case X86::SETBm: case X86::SETBEm:
1679       case X86::SETEm: case X86::SETNEm: case X86::SETPm: case X86::SETNPm:
1680       case X86::JA_4: case X86::JAE_4: case X86::JB_4: case X86::JBE_4:
1681       case X86::JE_4: case X86::JNE_4: case X86::JP_4: case X86::JNP_4:
1682       case X86::CMOVA16rr: case X86::CMOVA16rm:
1683       case X86::CMOVA32rr: case X86::CMOVA32rm:
1684       case X86::CMOVA64rr: case X86::CMOVA64rm:
1685       case X86::CMOVAE16rr: case X86::CMOVAE16rm:
1686       case X86::CMOVAE32rr: case X86::CMOVAE32rm:
1687       case X86::CMOVAE64rr: case X86::CMOVAE64rm:
1688       case X86::CMOVB16rr: case X86::CMOVB16rm:
1689       case X86::CMOVB32rr: case X86::CMOVB32rm:
1690       case X86::CMOVB64rr: case X86::CMOVB64rm:
1691       case X86::CMOVBE16rr: case X86::CMOVBE16rm:
1692       case X86::CMOVBE32rr: case X86::CMOVBE32rm:
1693       case X86::CMOVBE64rr: case X86::CMOVBE64rm:
1694       case X86::CMOVE16rr: case X86::CMOVE16rm:
1695       case X86::CMOVE32rr: case X86::CMOVE32rm:
1696       case X86::CMOVE64rr: case X86::CMOVE64rm:
1697       case X86::CMOVNE16rr: case X86::CMOVNE16rm:
1698       case X86::CMOVNE32rr: case X86::CMOVNE32rm:
1699       case X86::CMOVNE64rr: case X86::CMOVNE64rm:
1700       case X86::CMOVNP16rr: case X86::CMOVNP16rm:
1701       case X86::CMOVNP32rr: case X86::CMOVNP32rm:
1702       case X86::CMOVNP64rr: case X86::CMOVNP64rm:
1703       case X86::CMOVP16rr: case X86::CMOVP16rm:
1704       case X86::CMOVP32rr: case X86::CMOVP32rm:
1705       case X86::CMOVP64rr: case X86::CMOVP64rm:
1706         continue;
1707       // Anything else: assume conservatively.
1708       default: return false;
1709       }
1710     }
1711   }
1712   return true;
1713 }
1714
1715 SDNode *X86DAGToDAGISel::Select(SDNode *Node) {
1716   EVT NVT = Node->getValueType(0);
1717   unsigned Opc, MOpc;
1718   unsigned Opcode = Node->getOpcode();
1719   DebugLoc dl = Node->getDebugLoc();
1720
1721 #ifndef NDEBUG
1722   DEBUG({
1723       dbgs() << std::string(Indent, ' ') << "Selecting: ";
1724       Node->dump(CurDAG);
1725       dbgs() << '\n';
1726     });
1727   Indent += 2;
1728 #endif
1729
1730   if (Node->isMachineOpcode()) {
1731 #ifndef NDEBUG
1732     DEBUG({
1733         dbgs() << std::string(Indent-2, ' ') << "== ";
1734         Node->dump(CurDAG);
1735         dbgs() << '\n';
1736       });
1737     Indent -= 2;
1738 #endif
1739     return NULL;   // Already selected.
1740   }
1741
1742   switch (Opcode) {
1743   default: break;
1744   case X86ISD::GlobalBaseReg:
1745     return getGlobalBaseReg();
1746
1747   case X86ISD::ATOMOR64_DAG:
1748     return SelectAtomic64(Node, X86::ATOMOR6432);
1749   case X86ISD::ATOMXOR64_DAG:
1750     return SelectAtomic64(Node, X86::ATOMXOR6432);
1751   case X86ISD::ATOMADD64_DAG:
1752     return SelectAtomic64(Node, X86::ATOMADD6432);
1753   case X86ISD::ATOMSUB64_DAG:
1754     return SelectAtomic64(Node, X86::ATOMSUB6432);
1755   case X86ISD::ATOMNAND64_DAG:
1756     return SelectAtomic64(Node, X86::ATOMNAND6432);
1757   case X86ISD::ATOMAND64_DAG:
1758     return SelectAtomic64(Node, X86::ATOMAND6432);
1759   case X86ISD::ATOMSWAP64_DAG:
1760     return SelectAtomic64(Node, X86::ATOMSWAP6432);
1761
1762   case ISD::ATOMIC_LOAD_ADD: {
1763     SDNode *RetVal = SelectAtomicLoadAdd(Node, NVT);
1764     if (RetVal)
1765       return RetVal;
1766     break;
1767   }
1768
1769   case ISD::SMUL_LOHI:
1770   case ISD::UMUL_LOHI: {
1771     SDValue N0 = Node->getOperand(0);
1772     SDValue N1 = Node->getOperand(1);
1773
1774     bool isSigned = Opcode == ISD::SMUL_LOHI;
1775     if (!isSigned) {
1776       switch (NVT.getSimpleVT().SimpleTy) {
1777       default: llvm_unreachable("Unsupported VT!");
1778       case MVT::i8:  Opc = X86::MUL8r;  MOpc = X86::MUL8m;  break;
1779       case MVT::i16: Opc = X86::MUL16r; MOpc = X86::MUL16m; break;
1780       case MVT::i32: Opc = X86::MUL32r; MOpc = X86::MUL32m; break;
1781       case MVT::i64: Opc = X86::MUL64r; MOpc = X86::MUL64m; break;
1782       }
1783     } else {
1784       switch (NVT.getSimpleVT().SimpleTy) {
1785       default: llvm_unreachable("Unsupported VT!");
1786       case MVT::i8:  Opc = X86::IMUL8r;  MOpc = X86::IMUL8m;  break;
1787       case MVT::i16: Opc = X86::IMUL16r; MOpc = X86::IMUL16m; break;
1788       case MVT::i32: Opc = X86::IMUL32r; MOpc = X86::IMUL32m; break;
1789       case MVT::i64: Opc = X86::IMUL64r; MOpc = X86::IMUL64m; break;
1790       }
1791     }
1792
1793     unsigned LoReg, HiReg;
1794     switch (NVT.getSimpleVT().SimpleTy) {
1795     default: llvm_unreachable("Unsupported VT!");
1796     case MVT::i8:  LoReg = X86::AL;  HiReg = X86::AH;  break;
1797     case MVT::i16: LoReg = X86::AX;  HiReg = X86::DX;  break;
1798     case MVT::i32: LoReg = X86::EAX; HiReg = X86::EDX; break;
1799     case MVT::i64: LoReg = X86::RAX; HiReg = X86::RDX; break;
1800     }
1801
1802     SDValue Tmp0, Tmp1, Tmp2, Tmp3, Tmp4;
1803     bool foldedLoad = TryFoldLoad(Node, N1, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4);
1804     // Multiply is commmutative.
1805     if (!foldedLoad) {
1806       foldedLoad = TryFoldLoad(Node, N0, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4);
1807       if (foldedLoad)
1808         std::swap(N0, N1);
1809     }
1810
1811     SDValue InFlag = CurDAG->getCopyToReg(CurDAG->getEntryNode(), dl, LoReg,
1812                                             N0, SDValue()).getValue(1);
1813
1814     if (foldedLoad) {
1815       SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, N1.getOperand(0),
1816                         InFlag };
1817       SDNode *CNode =
1818         CurDAG->getMachineNode(MOpc, dl, MVT::Other, MVT::Flag, Ops,
1819                                array_lengthof(Ops));
1820       InFlag = SDValue(CNode, 1);
1821       // Update the chain.
1822       ReplaceUses(N1.getValue(1), SDValue(CNode, 0));
1823     } else {
1824       InFlag =
1825         SDValue(CurDAG->getMachineNode(Opc, dl, MVT::Flag, N1, InFlag), 0);
1826     }
1827
1828     // Copy the low half of the result, if it is needed.
1829     if (!SDValue(Node, 0).use_empty()) {
1830       SDValue Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl,
1831                                                 LoReg, NVT, InFlag);
1832       InFlag = Result.getValue(2);
1833       ReplaceUses(SDValue(Node, 0), Result);
1834 #ifndef NDEBUG
1835       DEBUG({
1836           dbgs() << std::string(Indent-2, ' ') << "=> ";
1837           Result.getNode()->dump(CurDAG);
1838           dbgs() << '\n';
1839         });
1840 #endif
1841     }
1842     // Copy the high half of the result, if it is needed.
1843     if (!SDValue(Node, 1).use_empty()) {
1844       SDValue Result;
1845       if (HiReg == X86::AH && Subtarget->is64Bit()) {
1846         // Prevent use of AH in a REX instruction by referencing AX instead.
1847         // Shift it down 8 bits.
1848         Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl,
1849                                         X86::AX, MVT::i16, InFlag);
1850         InFlag = Result.getValue(2);
1851         Result = SDValue(CurDAG->getMachineNode(X86::SHR16ri, dl, MVT::i16,
1852                                                 Result,
1853                                    CurDAG->getTargetConstant(8, MVT::i8)), 0);
1854         // Then truncate it down to i8.
1855         Result = CurDAG->getTargetExtractSubreg(X86::SUBREG_8BIT, dl,
1856                                                 MVT::i8, Result);
1857       } else {
1858         Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl,
1859                                         HiReg, NVT, InFlag);
1860         InFlag = Result.getValue(2);
1861       }
1862       ReplaceUses(SDValue(Node, 1), Result);
1863 #ifndef NDEBUG
1864       DEBUG({
1865           dbgs() << std::string(Indent-2, ' ') << "=> ";
1866           Result.getNode()->dump(CurDAG);
1867           dbgs() << '\n';
1868         });
1869 #endif
1870     }
1871
1872 #ifndef NDEBUG
1873     Indent -= 2;
1874 #endif
1875
1876     return NULL;
1877   }
1878
1879   case ISD::SDIVREM:
1880   case ISD::UDIVREM: {
1881     SDValue N0 = Node->getOperand(0);
1882     SDValue N1 = Node->getOperand(1);
1883
1884     bool isSigned = Opcode == ISD::SDIVREM;
1885     if (!isSigned) {
1886       switch (NVT.getSimpleVT().SimpleTy) {
1887       default: llvm_unreachable("Unsupported VT!");
1888       case MVT::i8:  Opc = X86::DIV8r;  MOpc = X86::DIV8m;  break;
1889       case MVT::i16: Opc = X86::DIV16r; MOpc = X86::DIV16m; break;
1890       case MVT::i32: Opc = X86::DIV32r; MOpc = X86::DIV32m; break;
1891       case MVT::i64: Opc = X86::DIV64r; MOpc = X86::DIV64m; break;
1892       }
1893     } else {
1894       switch (NVT.getSimpleVT().SimpleTy) {
1895       default: llvm_unreachable("Unsupported VT!");
1896       case MVT::i8:  Opc = X86::IDIV8r;  MOpc = X86::IDIV8m;  break;
1897       case MVT::i16: Opc = X86::IDIV16r; MOpc = X86::IDIV16m; break;
1898       case MVT::i32: Opc = X86::IDIV32r; MOpc = X86::IDIV32m; break;
1899       case MVT::i64: Opc = X86::IDIV64r; MOpc = X86::IDIV64m; break;
1900       }
1901     }
1902
1903     unsigned LoReg, HiReg, ClrReg;
1904     unsigned ClrOpcode, SExtOpcode;
1905     switch (NVT.getSimpleVT().SimpleTy) {
1906     default: llvm_unreachable("Unsupported VT!");
1907     case MVT::i8:
1908       LoReg = X86::AL;  ClrReg = HiReg = X86::AH;
1909       ClrOpcode  = 0;
1910       SExtOpcode = X86::CBW;
1911       break;
1912     case MVT::i16:
1913       LoReg = X86::AX;  HiReg = X86::DX;
1914       ClrOpcode  = X86::MOV16r0; ClrReg = X86::DX;
1915       SExtOpcode = X86::CWD;
1916       break;
1917     case MVT::i32:
1918       LoReg = X86::EAX; ClrReg = HiReg = X86::EDX;
1919       ClrOpcode  = X86::MOV32r0;
1920       SExtOpcode = X86::CDQ;
1921       break;
1922     case MVT::i64:
1923       LoReg = X86::RAX; ClrReg = HiReg = X86::RDX;
1924       ClrOpcode  = X86::MOV64r0;
1925       SExtOpcode = X86::CQO;
1926       break;
1927     }
1928
1929     SDValue Tmp0, Tmp1, Tmp2, Tmp3, Tmp4;
1930     bool foldedLoad = TryFoldLoad(Node, N1, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4);
1931     bool signBitIsZero = CurDAG->SignBitIsZero(N0);
1932
1933     SDValue InFlag;
1934     if (NVT == MVT::i8 && (!isSigned || signBitIsZero)) {
1935       // Special case for div8, just use a move with zero extension to AX to
1936       // clear the upper 8 bits (AH).
1937       SDValue Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, Move, Chain;
1938       if (TryFoldLoad(Node, N0, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4)) {
1939         SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, N0.getOperand(0) };
1940         Move =
1941           SDValue(CurDAG->getMachineNode(X86::MOVZX16rm8, dl, MVT::i16,
1942                                          MVT::Other, Ops,
1943                                          array_lengthof(Ops)), 0);
1944         Chain = Move.getValue(1);
1945         ReplaceUses(N0.getValue(1), Chain);
1946       } else {
1947         Move =
1948           SDValue(CurDAG->getMachineNode(X86::MOVZX16rr8, dl, MVT::i16, N0),0);
1949         Chain = CurDAG->getEntryNode();
1950       }
1951       Chain  = CurDAG->getCopyToReg(Chain, dl, X86::AX, Move, SDValue());
1952       InFlag = Chain.getValue(1);
1953     } else {
1954       InFlag =
1955         CurDAG->getCopyToReg(CurDAG->getEntryNode(), dl,
1956                              LoReg, N0, SDValue()).getValue(1);
1957       if (isSigned && !signBitIsZero) {
1958         // Sign extend the low part into the high part.
1959         InFlag =
1960           SDValue(CurDAG->getMachineNode(SExtOpcode, dl, MVT::Flag, InFlag),0);
1961       } else {
1962         // Zero out the high part, effectively zero extending the input.
1963         SDValue ClrNode =
1964           SDValue(CurDAG->getMachineNode(ClrOpcode, dl, NVT), 0);
1965         InFlag = CurDAG->getCopyToReg(CurDAG->getEntryNode(), dl, ClrReg,
1966                                       ClrNode, InFlag).getValue(1);
1967       }
1968     }
1969
1970     if (foldedLoad) {
1971       SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, N1.getOperand(0),
1972                         InFlag };
1973       SDNode *CNode =
1974         CurDAG->getMachineNode(MOpc, dl, MVT::Other, MVT::Flag, Ops,
1975                                array_lengthof(Ops));
1976       InFlag = SDValue(CNode, 1);
1977       // Update the chain.
1978       ReplaceUses(N1.getValue(1), SDValue(CNode, 0));
1979     } else {
1980       InFlag =
1981         SDValue(CurDAG->getMachineNode(Opc, dl, MVT::Flag, N1, InFlag), 0);
1982     }
1983
1984     // Copy the division (low) result, if it is needed.
1985     if (!SDValue(Node, 0).use_empty()) {
1986       SDValue Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl,
1987                                                 LoReg, NVT, InFlag);
1988       InFlag = Result.getValue(2);
1989       ReplaceUses(SDValue(Node, 0), Result);
1990 #ifndef NDEBUG
1991       DEBUG({
1992           dbgs() << std::string(Indent-2, ' ') << "=> ";
1993           Result.getNode()->dump(CurDAG);
1994           dbgs() << '\n';
1995         });
1996 #endif
1997     }
1998     // Copy the remainder (high) result, if it is needed.
1999     if (!SDValue(Node, 1).use_empty()) {
2000       SDValue Result;
2001       if (HiReg == X86::AH && Subtarget->is64Bit()) {
2002         // Prevent use of AH in a REX instruction by referencing AX instead.
2003         // Shift it down 8 bits.
2004         Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl,
2005                                         X86::AX, MVT::i16, InFlag);
2006         InFlag = Result.getValue(2);
2007         Result = SDValue(CurDAG->getMachineNode(X86::SHR16ri, dl, MVT::i16,
2008                                       Result,
2009                                       CurDAG->getTargetConstant(8, MVT::i8)),
2010                          0);
2011         // Then truncate it down to i8.
2012         Result = CurDAG->getTargetExtractSubreg(X86::SUBREG_8BIT, dl,
2013                                                 MVT::i8, Result);
2014       } else {
2015         Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl,
2016                                         HiReg, NVT, InFlag);
2017         InFlag = Result.getValue(2);
2018       }
2019       ReplaceUses(SDValue(Node, 1), Result);
2020 #ifndef NDEBUG
2021       DEBUG({
2022           dbgs() << std::string(Indent-2, ' ') << "=> ";
2023           Result.getNode()->dump(CurDAG);
2024           dbgs() << '\n';
2025         });
2026 #endif
2027     }
2028
2029 #ifndef NDEBUG
2030     Indent -= 2;
2031 #endif
2032
2033     return NULL;
2034   }
2035
2036   case X86ISD::CMP: {
2037     SDValue N0 = Node->getOperand(0);
2038     SDValue N1 = Node->getOperand(1);
2039
2040     // Look for (X86cmp (and $op, $imm), 0) and see if we can convert it to
2041     // use a smaller encoding.
2042     if (N0.getNode()->getOpcode() == ISD::AND && N0.getNode()->hasOneUse() &&
2043         N0.getValueType() != MVT::i8 &&
2044         X86::isZeroNode(N1)) {
2045       ConstantSDNode *C = dyn_cast<ConstantSDNode>(N0.getNode()->getOperand(1));
2046       if (!C) break;
2047
2048       // For example, convert "testl %eax, $8" to "testb %al, $8"
2049       if ((C->getZExtValue() & ~UINT64_C(0xff)) == 0 &&
2050           (!(C->getZExtValue() & 0x80) ||
2051            HasNoSignedComparisonUses(Node))) {
2052         SDValue Imm = CurDAG->getTargetConstant(C->getZExtValue(), MVT::i8);
2053         SDValue Reg = N0.getNode()->getOperand(0);
2054
2055         // On x86-32, only the ABCD registers have 8-bit subregisters.
2056         if (!Subtarget->is64Bit()) {
2057           TargetRegisterClass *TRC = 0;
2058           switch (N0.getValueType().getSimpleVT().SimpleTy) {
2059           case MVT::i32: TRC = &X86::GR32_ABCDRegClass; break;
2060           case MVT::i16: TRC = &X86::GR16_ABCDRegClass; break;
2061           default: llvm_unreachable("Unsupported TEST operand type!");
2062           }
2063           SDValue RC = CurDAG->getTargetConstant(TRC->getID(), MVT::i32);
2064           Reg = SDValue(CurDAG->getMachineNode(X86::COPY_TO_REGCLASS, dl,
2065                                                Reg.getValueType(), Reg, RC), 0);
2066         }
2067
2068         // Extract the l-register.
2069         SDValue Subreg = CurDAG->getTargetExtractSubreg(X86::SUBREG_8BIT, dl,
2070                                                         MVT::i8, Reg);
2071
2072         // Emit a testb.
2073         return CurDAG->getMachineNode(X86::TEST8ri, dl, MVT::i32, Subreg, Imm);
2074       }
2075
2076       // For example, "testl %eax, $2048" to "testb %ah, $8".
2077       if ((C->getZExtValue() & ~UINT64_C(0xff00)) == 0 &&
2078           (!(C->getZExtValue() & 0x8000) ||
2079            HasNoSignedComparisonUses(Node))) {
2080         // Shift the immediate right by 8 bits.
2081         SDValue ShiftedImm = CurDAG->getTargetConstant(C->getZExtValue() >> 8,
2082                                                        MVT::i8);
2083         SDValue Reg = N0.getNode()->getOperand(0);
2084
2085         // Put the value in an ABCD register.
2086         TargetRegisterClass *TRC = 0;
2087         switch (N0.getValueType().getSimpleVT().SimpleTy) {
2088         case MVT::i64: TRC = &X86::GR64_ABCDRegClass; break;
2089         case MVT::i32: TRC = &X86::GR32_ABCDRegClass; break;
2090         case MVT::i16: TRC = &X86::GR16_ABCDRegClass; break;
2091         default: llvm_unreachable("Unsupported TEST operand type!");
2092         }
2093         SDValue RC = CurDAG->getTargetConstant(TRC->getID(), MVT::i32);
2094         Reg = SDValue(CurDAG->getMachineNode(X86::COPY_TO_REGCLASS, dl,
2095                                              Reg.getValueType(), Reg, RC), 0);
2096
2097         // Extract the h-register.
2098         SDValue Subreg = CurDAG->getTargetExtractSubreg(X86::SUBREG_8BIT_HI, dl,
2099                                                         MVT::i8, Reg);
2100
2101         // Emit a testb. No special NOREX tricks are needed since there's
2102         // only one GPR operand!
2103         return CurDAG->getMachineNode(X86::TEST8ri, dl, MVT::i32,
2104                                       Subreg, ShiftedImm);
2105       }
2106
2107       // For example, "testl %eax, $32776" to "testw %ax, $32776".
2108       if ((C->getZExtValue() & ~UINT64_C(0xffff)) == 0 &&
2109           N0.getValueType() != MVT::i16 &&
2110           (!(C->getZExtValue() & 0x8000) ||
2111            HasNoSignedComparisonUses(Node))) {
2112         SDValue Imm = CurDAG->getTargetConstant(C->getZExtValue(), MVT::i16);
2113         SDValue Reg = N0.getNode()->getOperand(0);
2114
2115         // Extract the 16-bit subregister.
2116         SDValue Subreg = CurDAG->getTargetExtractSubreg(X86::SUBREG_16BIT, dl,
2117                                                         MVT::i16, Reg);
2118
2119         // Emit a testw.
2120         return CurDAG->getMachineNode(X86::TEST16ri, dl, MVT::i32, Subreg, Imm);
2121       }
2122
2123       // For example, "testq %rax, $268468232" to "testl %eax, $268468232".
2124       if ((C->getZExtValue() & ~UINT64_C(0xffffffff)) == 0 &&
2125           N0.getValueType() == MVT::i64 &&
2126           (!(C->getZExtValue() & 0x80000000) ||
2127            HasNoSignedComparisonUses(Node))) {
2128         SDValue Imm = CurDAG->getTargetConstant(C->getZExtValue(), MVT::i32);
2129         SDValue Reg = N0.getNode()->getOperand(0);
2130
2131         // Extract the 32-bit subregister.
2132         SDValue Subreg = CurDAG->getTargetExtractSubreg(X86::SUBREG_32BIT, dl,
2133                                                         MVT::i32, Reg);
2134
2135         // Emit a testl.
2136         return CurDAG->getMachineNode(X86::TEST32ri, dl, MVT::i32, Subreg, Imm);
2137       }
2138     }
2139     break;
2140   }
2141   }
2142
2143   SDNode *ResNode = SelectCode(Node);
2144
2145 #ifndef NDEBUG
2146   DEBUG({
2147       dbgs() << std::string(Indent-2, ' ') << "=> ";
2148       if (ResNode == NULL || ResNode == Node)
2149         Node->dump(CurDAG);
2150       else
2151         ResNode->dump(CurDAG);
2152       dbgs() << '\n';
2153     });
2154   Indent -= 2;
2155 #endif
2156
2157   return ResNode;
2158 }
2159
2160 bool X86DAGToDAGISel::
2161 SelectInlineAsmMemoryOperand(const SDValue &Op, char ConstraintCode,
2162                              std::vector<SDValue> &OutOps) {
2163   SDValue Op0, Op1, Op2, Op3, Op4;
2164   switch (ConstraintCode) {
2165   case 'o':   // offsetable        ??
2166   case 'v':   // not offsetable    ??
2167   default: return true;
2168   case 'm':   // memory
2169     if (!SelectAddr(Op.getNode(), Op, Op0, Op1, Op2, Op3, Op4))
2170       return true;
2171     break;
2172   }
2173
2174   OutOps.push_back(Op0);
2175   OutOps.push_back(Op1);
2176   OutOps.push_back(Op2);
2177   OutOps.push_back(Op3);
2178   OutOps.push_back(Op4);
2179   return false;
2180 }
2181
2182 /// createX86ISelDag - This pass converts a legalized DAG into a
2183 /// X86-specific DAG, ready for instruction scheduling.
2184 ///
2185 FunctionPass *llvm::createX86ISelDag(X86TargetMachine &TM,
2186                                      llvm::CodeGenOpt::Level OptLevel) {
2187   return new X86DAGToDAGISel(TM, OptLevel);
2188 }