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 #define DEBUG_TYPE "x86-isel"
  16 #include "X86.h"
  17 #include "X86InstrBuilder.h"
  18 #include "X86ISelLowering.h"
  19 #include "X86MachineFunctionInfo.h"
  20 #include "X86RegisterInfo.h"
  21 #include "X86Subtarget.h"
  22 #include "X86TargetMachine.h"
  23 #include "llvm/GlobalValue.h"
  24 #include "llvm/Instructions.h"
  25 #include "llvm/Intrinsics.h"
  26 #include "llvm/Support/CFG.h"
  27 #include "llvm/Type.h"
  28 #include "llvm/CodeGen/MachineConstantPool.h"
  29 #include "llvm/CodeGen/MachineFunction.h"
  30 #include "llvm/CodeGen/MachineFrameInfo.h"
  31 #include "llvm/CodeGen/MachineInstrBuilder.h"
  32 #include "llvm/CodeGen/MachineRegisterInfo.h"
  33 #include "llvm/CodeGen/SelectionDAGISel.h"
  34 #include "llvm/Target/TargetMachine.h"
  35 #include "llvm/Target/TargetOptions.h"
  36 #include "llvm/Support/Compiler.h"
  37 #include "llvm/Support/Debug.h"
  38 #include "llvm/Support/MathExtras.h"
  39 #include "llvm/Support/Streams.h"
  40 #include "llvm/ADT/SmallPtrSet.h"
  41 #include "llvm/ADT/Statistic.h"
  42 using namespace llvm;
  43
  44 #include "llvm/Support/CommandLine.h"
  45 static cl::opt<bool> AvoidDupAddrCompute("x86-avoid-dup-address", cl::Hidden);
  46
  47 STATISTIC(NumLoadMoved, "Number of loads moved below TokenFactor");
  48
  49 //===----------------------------------------------------------------------===//
  50 //                      Pattern Matcher Implementation
  51 //===----------------------------------------------------------------------===//
  52
  53 namespace {
  54   /// X86ISelAddressMode - This corresponds to X86AddressMode, but uses
  55   /// SDValue's instead of register numbers for the leaves of the matched
  56   /// tree.
  57   struct X86ISelAddressMode {
  58     enum {
  59       RegBase,
  60       FrameIndexBase
  61     } BaseType;
  62
  63     struct {            // This is really a union, discriminated by BaseType!
  64       SDValue Reg;
  65       int FrameIndex;
  66     } Base;
  67
  68     bool isRIPRel;     // RIP as base?
  69     unsigned Scale;
  70     SDValue IndexReg;
  71     int32_t Disp;
  72     SDValue Segment;
  73     GlobalValue *GV;
  74     Constant *CP;
  75     const char *ES;
  76     int JT;
  77     unsigned Align;    // CP alignment.
  78
  79     X86ISelAddressMode()
  80       : BaseType(RegBase), isRIPRel(false), Scale(1), IndexReg(), Disp(0),
  81         Segment(), GV(0), CP(0), ES(0), JT(-1), Align(0) {
  82     }
  83
  84     bool hasSymbolicDisplacement() const {
  85       return GV != 0 || CP != 0 || ES != 0 || JT != -1;
  86     }
  87
  88     void dump() {
  89       cerr << "X86ISelAddressMode " << this << "\n";
  90       cerr << "Base.Reg ";
  91               if (Base.Reg.getNode() != 0) Base.Reg.getNode()->dump();
  92               else cerr << "nul";
  93       cerr << " Base.FrameIndex " << Base.FrameIndex << "\n";
  94       cerr << "isRIPRel " << isRIPRel << " Scale" << Scale << "\n";
  95       cerr << "IndexReg ";
  96               if (IndexReg.getNode() != 0) IndexReg.getNode()->dump();
  97               else cerr << "nul";
  98       cerr << " Disp " << Disp << "\n";
  99       cerr << "GV "; if (GV) GV->dump();
 100                      else cerr << "nul";
 101       cerr << " CP "; if (CP) CP->dump();
 102                      else cerr << "nul";
 103       cerr << "\n";
 104       cerr << "ES "; if (ES) cerr << ES; else cerr << "nul";
 105       cerr  << " JT" << JT << " Align" << Align << "\n";
 106     }
 107   };
 108 }
 109
 110 namespace {
 111   //===--------------------------------------------------------------------===//
 112   /// ISel - X86 specific code to select X86 machine instructions for
 113   /// SelectionDAG operations.
 114   ///
 115   class VISIBILITY_HIDDEN X86DAGToDAGISel : public SelectionDAGISel {
 116     /// X86Lowering - This object fully describes how to lower LLVM code to an
 117     /// X86-specific SelectionDAG.
 118     X86TargetLowering &X86Lowering;
 119
 120     /// Subtarget - Keep a pointer to the X86Subtarget around so that we can
 121     /// make the right decision when generating code for different targets.
 122     const X86Subtarget *Subtarget;
 123
 124     /// CurBB - Current BB being isel'd.
 125     ///
 126     MachineBasicBlock *CurBB;
 127
 128     /// OptForSize - If true, selector should try to optimize for code size
 129     /// instead of performance.
 130     bool OptForSize;
 131
 132   public:
 133     explicit X86DAGToDAGISel(X86TargetMachine &tm, CodeGenOpt::Level OptLevel)
 134       : SelectionDAGISel(tm, OptLevel),
 135         X86Lowering(*tm.getTargetLowering()),
 136         Subtarget(&tm.getSubtarget<X86Subtarget>()),
 137         OptForSize(false) {}
 138
 139     virtual const char *getPassName() const {
 140       return "X86 DAG->DAG Instruction Selection";
 141     }
 142
 143     /// InstructionSelect - This callback is invoked by
 144     /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
 145     virtual void InstructionSelect();
 146
 147     virtual void EmitFunctionEntryCode(Function &Fn, MachineFunction &MF);
 148
 149     virtual
 150       bool IsLegalAndProfitableToFold(SDNode *N, SDNode *U, SDNode *Root) const;
 151
 152 // Include the pieces autogenerated from the target description.
 153 #include "X86GenDAGISel.inc"
 154
 155   private:
 156     SDNode *Select(SDValue N);
 157     SDNode *SelectAtomic64(SDNode *Node, unsigned Opc);
 158
 159     bool MatchSegmentBaseAddress(SDValue N, X86ISelAddressMode &AM);
 160     bool MatchLoad(SDValue N, X86ISelAddressMode &AM);
 161     bool MatchWrapper(SDValue N, X86ISelAddressMode &AM);
 162     bool MatchAddress(SDValue N, X86ISelAddressMode &AM,
 163                       unsigned Depth = 0);
 164     bool MatchAddressBase(SDValue N, X86ISelAddressMode &AM);
 165     bool SelectAddr(SDValue Op, SDValue N, SDValue &Base,
 166                     SDValue &Scale, SDValue &Index, SDValue &Disp,
 167                     SDValue &Segment);
 168     bool SelectLEAAddr(SDValue Op, SDValue N, SDValue &Base,
 169                        SDValue &Scale, SDValue &Index, SDValue &Disp);
 170     bool SelectTLSADDRAddr(SDValue Op, SDValue N, SDValue &Base,
 171                        SDValue &Scale, SDValue &Index, SDValue &Disp);
 172     bool SelectScalarSSELoad(SDValue Op, SDValue Pred,
 173                              SDValue N, SDValue &Base, SDValue &Scale,
 174                              SDValue &Index, SDValue &Disp,
 175                              SDValue &Segment,
 176                              SDValue &InChain, SDValue &OutChain);
 177     bool TryFoldLoad(SDValue P, SDValue N,
 178                      SDValue &Base, SDValue &Scale,
 179                      SDValue &Index, SDValue &Disp,
 180                      SDValue &Segment);
 181     void PreprocessForRMW();
 182     void PreprocessForFPConvert();
 183
 184     /// SelectInlineAsmMemoryOperand - Implement addressing mode selection for
 185     /// inline asm expressions.
 186     virtual bool SelectInlineAsmMemoryOperand(const SDValue &Op,
 187                                               char ConstraintCode,
 188                                               std::vector<SDValue> &OutOps);
 189
 190     void EmitSpecialCodeForMain(MachineBasicBlock *BB, MachineFrameInfo *MFI);
 191
 192     inline void getAddressOperands(X86ISelAddressMode &AM, SDValue &Base,
 193                                    SDValue &Scale, SDValue &Index,
 194                                    SDValue &Disp, SDValue &Segment) {
 195       Base  = (AM.BaseType == X86ISelAddressMode::FrameIndexBase) ?
 196         CurDAG->getTargetFrameIndex(AM.Base.FrameIndex, TLI.getPointerTy()) :
 197         AM.Base.Reg;
 198       Scale = getI8Imm(AM.Scale);
 199       Index = AM.IndexReg;
 200       // These are 32-bit even in 64-bit mode since RIP relative offset
 201       // is 32-bit.
 202       if (AM.GV)
 203         Disp = CurDAG->getTargetGlobalAddress(AM.GV, MVT::i32, AM.Disp);
 204       else if (AM.CP)
 205         Disp = CurDAG->getTargetConstantPool(AM.CP, MVT::i32,
 206                                              AM.Align, AM.Disp);
 207       else if (AM.ES)
 208         Disp = CurDAG->getTargetExternalSymbol(AM.ES, MVT::i32);
 209       else if (AM.JT != -1)
 210         Disp = CurDAG->getTargetJumpTable(AM.JT, MVT::i32);
 211       else
 212         Disp = CurDAG->getTargetConstant(AM.Disp, MVT::i32);
 213
 214       if (AM.Segment.getNode())
 215         Segment = AM.Segment;
 216       else
 217         Segment = CurDAG->getRegister(0, MVT::i32);
 218     }
 219
 220     /// getI8Imm - Return a target constant with the specified value, of type
 221     /// i8.
 222     inline SDValue getI8Imm(unsigned Imm) {
 223       return CurDAG->getTargetConstant(Imm, MVT::i8);
 224     }
 225
 226     /// getI16Imm - Return a target constant with the specified value, of type
 227     /// i16.
 228     inline SDValue getI16Imm(unsigned Imm) {
 229       return CurDAG->getTargetConstant(Imm, MVT::i16);
 230     }
 231
 232     /// getI32Imm - Return a target constant with the specified value, of type
 233     /// i32.
 234     inline SDValue getI32Imm(unsigned Imm) {
 235       return CurDAG->getTargetConstant(Imm, MVT::i32);
 236     }
 237
 238     /// getGlobalBaseReg - Return an SDNode that returns the value of
 239     /// the global base register. Output instructions required to
 240     /// initialize the global base register, if necessary.
 241     ///
 242     SDNode *getGlobalBaseReg();
 243
 244     /// getTargetMachine - Return a reference to the TargetMachine, casted
 245     /// to the target-specific type.
 246     const X86TargetMachine &getTargetMachine() {
 247       return static_cast<const X86TargetMachine &>(TM);
 248     }
 249
 250     /// getInstrInfo - Return a reference to the TargetInstrInfo, casted
 251     /// to the target-specific type.
 252     const X86InstrInfo *getInstrInfo() {
 253       return getTargetMachine().getInstrInfo();
 254     }
 255
 256 #ifndef NDEBUG
 257     unsigned Indent;
 258 #endif
 259   };
 260 }
 261
 262
 263 bool X86DAGToDAGISel::IsLegalAndProfitableToFold(SDNode *N, SDNode *U,
 264                                                  SDNode *Root) const {
 265   if (OptLevel == CodeGenOpt::None) return false;
 266
 267   if (U == Root)
 268     switch (U->getOpcode()) {
 269     default: break;
 270     case ISD::ADD:
 271     case ISD::ADDC:
 272     case ISD::ADDE:
 273     case ISD::AND:
 274     case ISD::OR:
 275     case ISD::XOR: {
 276       SDValue Op1 = U->getOperand(1);
 277
 278       // If the other operand is a 8-bit immediate we should fold the immediate
 279       // instead. This reduces code size.
 280       // e.g.
 281       // movl 4(%esp), %eax
 282       // addl $4, %eax
 283       // vs.
 284       // movl $4, %eax
 285       // addl 4(%esp), %eax
 286       // The former is 2 bytes shorter. In case where the increment is 1, then
 287       // the saving can be 4 bytes (by using incl %eax).
 288       if (ConstantSDNode *Imm = dyn_cast<ConstantSDNode>(Op1))
 289         if (Imm->getAPIntValue().isSignedIntN(8))
 290           return false;
 291
 292       // If the other operand is a TLS address, we should fold it instead.
 293       // This produces
 294       // movl    %gs:0, %eax
 295       // leal    i@NTPOFF(%eax), %eax
 296       // instead of
 297       // movl    $i@NTPOFF, %eax
 298       // addl    %gs:0, %eax
 299       // if the block also has an access to a second TLS address this will save
 300       // a load.
 301       // FIXME: This is probably also true for non TLS addresses.
 302       if (Op1.getOpcode() == X86ISD::Wrapper) {
 303         SDValue Val = Op1.getOperand(0);
 304         if (Val.getOpcode() == ISD::TargetGlobalTLSAddress)
 305           return false;
 306       }
 307     }
 308     }
 309
 310   // Proceed to 'generic' cycle finder code
 311   return SelectionDAGISel::IsLegalAndProfitableToFold(N, U, Root);
 312 }
 313
 314 /// MoveBelowTokenFactor - Replace TokenFactor operand with load's chain operand
 315 /// and move load below the TokenFactor. Replace store's chain operand with
 316 /// load's chain result.
 317 static void MoveBelowTokenFactor(SelectionDAG *CurDAG, SDValue Load,
 318                                  SDValue Store, SDValue TF) {
 319   SmallVector<SDValue, 4> Ops;
 320   for (unsigned i = 0, e = TF.getNode()->getNumOperands(); i != e; ++i)
 321     if (Load.getNode() == TF.getOperand(i).getNode())
 322       Ops.push_back(Load.getOperand(0));
 323     else
 324       Ops.push_back(TF.getOperand(i));
 325   CurDAG->UpdateNodeOperands(TF, &Ops[0], Ops.size());
 326   CurDAG->UpdateNodeOperands(Load, TF, Load.getOperand(1), Load.getOperand(2));
 327   CurDAG->UpdateNodeOperands(Store, Load.getValue(1), Store.getOperand(1),
 328                              Store.getOperand(2), Store.getOperand(3));
 329 }
 330
 331 /// isRMWLoad - Return true if N is a load that's part of RMW sub-DAG.
 332 ///
 333 static bool isRMWLoad(SDValue N, SDValue Chain, SDValue Address,
 334                       SDValue &Load) {
 335   if (N.getOpcode() == ISD::BIT_CONVERT)
 336     N = N.getOperand(0);
 337
 338   LoadSDNode *LD = dyn_cast<LoadSDNode>(N);
 339   if (!LD || LD->isVolatile())
 340     return false;
 341   if (LD->getAddressingMode() != ISD::UNINDEXED)
 342     return false;
 343
 344   ISD::LoadExtType ExtType = LD->getExtensionType();
 345   if (ExtType != ISD::NON_EXTLOAD && ExtType != ISD::EXTLOAD)
 346     return false;
 347
 348   if (N.hasOneUse() &&
 349       N.getOperand(1) == Address &&
 350       N.getNode()->isOperandOf(Chain.getNode())) {
 351     Load = N;
 352     return true;
 353   }
 354   return false;
 355 }
 356
 357 /// MoveBelowCallSeqStart - Replace CALLSEQ_START operand with load's chain
 358 /// operand and move load below the call's chain operand.
 359 static void MoveBelowCallSeqStart(SelectionDAG *CurDAG, SDValue Load,
 360                                   SDValue Call, SDValue CallSeqStart) {
 361   SmallVector<SDValue, 8> Ops;
 362   SDValue Chain = CallSeqStart.getOperand(0);
 363   if (Chain.getNode() == Load.getNode())
 364     Ops.push_back(Load.getOperand(0));
 365   else {
 366     assert(Chain.getOpcode() == ISD::TokenFactor &&
 367            "Unexpected CallSeqStart chain operand");
 368     for (unsigned i = 0, e = Chain.getNumOperands(); i != e; ++i)
 369       if (Chain.getOperand(i).getNode() == Load.getNode())
 370         Ops.push_back(Load.getOperand(0));
 371       else
 372         Ops.push_back(Chain.getOperand(i));
 373     SDValue NewChain =
 374       CurDAG->getNode(ISD::TokenFactor, Load.getDebugLoc(),
 375                       MVT::Other, &Ops[0], Ops.size());
 376     Ops.clear();
 377     Ops.push_back(NewChain);
 378   }
 379   for (unsigned i = 1, e = CallSeqStart.getNumOperands(); i != e; ++i)
 380     Ops.push_back(CallSeqStart.getOperand(i));
 381   CurDAG->UpdateNodeOperands(CallSeqStart, &Ops[0], Ops.size());
 382   CurDAG->UpdateNodeOperands(Load, Call.getOperand(0),
 383                              Load.getOperand(1), Load.getOperand(2));
 384   Ops.clear();
 385   Ops.push_back(SDValue(Load.getNode(), 1));
 386   for (unsigned i = 1, e = Call.getNode()->getNumOperands(); i != e; ++i)
 387     Ops.push_back(Call.getOperand(i));
 388   CurDAG->UpdateNodeOperands(Call, &Ops[0], Ops.size());
 389 }
 390
 391 /// isCalleeLoad - Return true if call address is a load and it can be
 392 /// moved below CALLSEQ_START and the chains leading up to the call.
 393 /// Return the CALLSEQ_START by reference as a second output.
 394 static bool isCalleeLoad(SDValue Callee, SDValue &Chain) {
 395   if (Callee.getNode() == Chain.getNode() || !Callee.hasOneUse())
 396     return false;
 397   LoadSDNode *LD = dyn_cast<LoadSDNode>(Callee.getNode());
 398   if (!LD ||
 399       LD->isVolatile() ||
 400       LD->getAddressingMode() != ISD::UNINDEXED ||
 401       LD->getExtensionType() != ISD::NON_EXTLOAD)
 402     return false;
 403
 404   // Now let's find the callseq_start.
 405   while (Chain.getOpcode() != ISD::CALLSEQ_START) {
 406     if (!Chain.hasOneUse())
 407       return false;
 408     Chain = Chain.getOperand(0);
 409   }
 410
 411   if (Chain.getOperand(0).getNode() == Callee.getNode())
 412     return true;
 413   if (Chain.getOperand(0).getOpcode() == ISD::TokenFactor &&
 414       Callee.getValue(1).isOperandOf(Chain.getOperand(0).getNode()))
 415     return true;
 416   return false;
 417 }
 418
 419
 420 /// PreprocessForRMW - Preprocess the DAG to make instruction selection better.
 421 /// This is only run if not in -O0 mode.
 422 /// This allows the instruction selector to pick more read-modify-write
 423 /// instructions. This is a common case:
 424 ///
 425 ///     [Load chain]
 426 ///         ^
 427 ///         |
 428 ///       [Load]
 429 ///       ^    ^
 430 ///       |    |
 431 ///      /      \-
 432 ///     /         |
 433 /// [TokenFactor] [Op]
 434 ///     ^          ^
 435 ///     |          |
 436 ///      \        /
 437 ///       \      /
 438 ///       [Store]
 439 ///
 440 /// The fact the store's chain operand != load's chain will prevent the
 441 /// (store (op (load))) instruction from being selected. We can transform it to:
 442 ///
 443 ///     [Load chain]
 444 ///         ^
 445 ///         |
 446 ///    [TokenFactor]
 447 ///         ^
 448 ///         |
 449 ///       [Load]
 450 ///       ^    ^
 451 ///       |    |
 452 ///       |     \-
 453 ///       |       |
 454 ///       |     [Op]
 455 ///       |       ^
 456 ///       |       |
 457 ///       \      /
 458 ///        \    /
 459 ///       [Store]
 460 void X86DAGToDAGISel::PreprocessForRMW() {
 461   for (SelectionDAG::allnodes_iterator I = CurDAG->allnodes_begin(),
 462          E = CurDAG->allnodes_end(); I != E; ++I) {
 463     if (I->getOpcode() == X86ISD::CALL) {
 464       /// Also try moving call address load from outside callseq_start to just
 465       /// before the call to allow it to be folded.
 466       ///
 467       ///     [Load chain]
 468       ///         ^
 469       ///         |
 470       ///       [Load]
 471       ///       ^    ^
 472       ///       |    |
 473       ///      /      \--
 474       ///     /          |
 475       ///[CALLSEQ_START] |
 476       ///     ^          |
 477       ///     |          |
 478       /// [LOAD/C2Reg]   |
 479       ///     |          |
 480       ///      \        /
 481       ///       \      /
 482       ///       [CALL]
 483       SDValue Chain = I->getOperand(0);
 484       SDValue Load  = I->getOperand(1);
 485       if (!isCalleeLoad(Load, Chain))
 486         continue;
 487       MoveBelowCallSeqStart(CurDAG, Load, SDValue(I, 0), Chain);
 488       ++NumLoadMoved;
 489       continue;
 490     }
 491
 492     if (!ISD::isNON_TRUNCStore(I))
 493       continue;
 494     SDValue Chain = I->getOperand(0);
 495
 496     if (Chain.getNode()->getOpcode() != ISD::TokenFactor)
 497       continue;
 498
 499     SDValue N1 = I->getOperand(1);
 500     SDValue N2 = I->getOperand(2);
 501     if ((N1.getValueType().isFloatingPoint() &&
 502          !N1.getValueType().isVector()) ||
 503         !N1.hasOneUse())
 504       continue;
 505
 506     bool RModW = false;
 507     SDValue Load;
 508     unsigned Opcode = N1.getNode()->getOpcode();
 509     switch (Opcode) {
 510     case ISD::ADD:
 511     case ISD::MUL:
 512     case ISD::AND:
 513     case ISD::OR:
 514     case ISD::XOR:
 515     case ISD::ADDC:
 516     case ISD::ADDE:
 517     case ISD::VECTOR_SHUFFLE: {
 518       SDValue N10 = N1.getOperand(0);
 519       SDValue N11 = N1.getOperand(1);
 520       RModW = isRMWLoad(N10, Chain, N2, Load);
 521       if (!RModW)
 522         RModW = isRMWLoad(N11, Chain, N2, Load);
 523       break;
 524     }
 525     case ISD::SUB:
 526     case ISD::SHL:
 527     case ISD::SRA:
 528     case ISD::SRL:
 529     case ISD::ROTL:
 530     case ISD::ROTR:
 531     case ISD::SUBC:
 532     case ISD::SUBE:
 533     case X86ISD::SHLD:
 534     case X86ISD::SHRD: {
 535       SDValue N10 = N1.getOperand(0);
 536       RModW = isRMWLoad(N10, Chain, N2, Load);
 537       break;
 538     }
 539     }
 540
 541     if (RModW) {
 542       MoveBelowTokenFactor(CurDAG, Load, SDValue(I, 0), Chain);
 543       ++NumLoadMoved;
 544     }
 545   }
 546 }
 547
 548
 549 /// PreprocessForFPConvert - Walk over the dag lowering fpround and fpextend
 550 /// nodes that target the FP stack to be store and load to the stack.  This is a
 551 /// gross hack.  We would like to simply mark these as being illegal, but when
 552 /// we do that, legalize produces these when it expands calls, then expands
 553 /// these in the same legalize pass.  We would like dag combine to be able to
 554 /// hack on these between the call expansion and the node legalization.  As such
 555 /// this pass basically does "really late" legalization of these inline with the
 556 /// X86 isel pass.
 557 void X86DAGToDAGISel::PreprocessForFPConvert() {
 558   for (SelectionDAG::allnodes_iterator I = CurDAG->allnodes_begin(),
 559        E = CurDAG->allnodes_end(); I != E; ) {
 560     SDNode *N = I++;  // Preincrement iterator to avoid invalidation issues.
 561     if (N->getOpcode() != ISD::FP_ROUND && N->getOpcode() != ISD::FP_EXTEND)
 562       continue;
 563
 564     // If the source and destination are SSE registers, then this is a legal
 565     // conversion that should not be lowered.
 566     MVT SrcVT = N->getOperand(0).getValueType();
 567     MVT DstVT = N->getValueType(0);
 568     bool SrcIsSSE = X86Lowering.isScalarFPTypeInSSEReg(SrcVT);
 569     bool DstIsSSE = X86Lowering.isScalarFPTypeInSSEReg(DstVT);
 570     if (SrcIsSSE && DstIsSSE)
 571       continue;
 572
 573     if (!SrcIsSSE && !DstIsSSE) {
 574       // If this is an FPStack extension, it is a noop.
 575       if (N->getOpcode() == ISD::FP_EXTEND)
 576         continue;
 577       // If this is a value-preserving FPStack truncation, it is a noop.
 578       if (N->getConstantOperandVal(1))
 579         continue;
 580     }
 581
 582     // Here we could have an FP stack truncation or an FPStack <-> SSE convert.
 583     // FPStack has extload and truncstore.  SSE can fold direct loads into other
 584     // operations.  Based on this, decide what we want to do.
 585     MVT MemVT;
 586     if (N->getOpcode() == ISD::FP_ROUND)
 587       MemVT = DstVT;  // FP_ROUND must use DstVT, we can't do a 'trunc load'.
 588     else
 589       MemVT = SrcIsSSE ? SrcVT : DstVT;
 590
 591     SDValue MemTmp = CurDAG->CreateStackTemporary(MemVT);
 592     DebugLoc dl = N->getDebugLoc();
 593
 594     // FIXME: optimize the case where the src/dest is a load or store?
 595     SDValue Store = CurDAG->getTruncStore(CurDAG->getEntryNode(), dl,
 596                                           N->getOperand(0),
 597                                           MemTmp, NULL, 0, MemVT);
 598     SDValue Result = CurDAG->getExtLoad(ISD::EXTLOAD, dl, DstVT, Store, MemTmp,
 599                                         NULL, 0, MemVT);
 600
 601     // We're about to replace all uses of the FP_ROUND/FP_EXTEND with the
 602     // extload we created.  This will cause general havok on the dag because
 603     // anything below the conversion could be folded into other existing nodes.
 604     // To avoid invalidating 'I', back it up to the convert node.
 605     --I;
 606     CurDAG->ReplaceAllUsesOfValueWith(SDValue(N, 0), Result);
 607
 608     // Now that we did that, the node is dead.  Increment the iterator to the
 609     // next node to process, then delete N.
 610     ++I;
 611     CurDAG->DeleteNode(N);
 612   }
 613 }
 614
 615 /// InstructionSelectBasicBlock - This callback is invoked by SelectionDAGISel
 616 /// when it has created a SelectionDAG for us to codegen.
 617 void X86DAGToDAGISel::InstructionSelect() {
 618   CurBB = BB;  // BB can change as result of isel.
 619   const Function *F = CurDAG->getMachineFunction().getFunction();
 620   OptForSize = F->hasFnAttr(Attribute::OptimizeForSize);
 621
 622   DEBUG(BB->dump());
 623   if (OptLevel != CodeGenOpt::None)
 624     PreprocessForRMW();
 625
 626   // FIXME: This should only happen when not compiled with -O0.
 627   PreprocessForFPConvert();
 628
 629   // Codegen the basic block.
 630 #ifndef NDEBUG
 631   DOUT << "===== Instruction selection begins:\n";
 632   Indent = 0;
 633 #endif
 634   SelectRoot(*CurDAG);
 635 #ifndef NDEBUG
 636   DOUT << "===== Instruction selection ends:\n";
 637 #endif
 638
 639   CurDAG->RemoveDeadNodes();
 640 }
 641
 642 /// EmitSpecialCodeForMain - Emit any code that needs to be executed only in
 643 /// the main function.
 644 void X86DAGToDAGISel::EmitSpecialCodeForMain(MachineBasicBlock *BB,
 645                                              MachineFrameInfo *MFI) {
 646   const TargetInstrInfo *TII = TM.getInstrInfo();
 647   if (Subtarget->isTargetCygMing())
 648     BuildMI(BB, DebugLoc::getUnknownLoc(),
 649             TII->get(X86::CALLpcrel32)).addExternalSymbol("__main");
 650 }
 651
 652 void X86DAGToDAGISel::EmitFunctionEntryCode(Function &Fn, MachineFunction &MF) {
 653   // If this is main, emit special code for main.
 654   MachineBasicBlock *BB = MF.begin();
 655   if (Fn.hasExternalLinkage() && Fn.getName() == "main")
 656     EmitSpecialCodeForMain(BB, MF.getFrameInfo());
 657 }
 658
 659
 660 bool X86DAGToDAGISel::MatchSegmentBaseAddress(SDValue N,
 661                                               X86ISelAddressMode &AM) {
 662   assert(N.getOpcode() == X86ISD::SegmentBaseAddress);
 663   SDValue Segment = N.getOperand(0);
 664
 665   if (AM.Segment.getNode() == 0) {
 666     AM.Segment = Segment;
 667     return false;
 668   }
 669
 670   return true;
 671 }
 672
 673 bool X86DAGToDAGISel::MatchLoad(SDValue N, X86ISelAddressMode &AM) {
 674   // This optimization is valid because the GNU TLS model defines that
 675   // gs:0 (or fs:0 on X86-64) contains its own address.
 676   // For more information see http://people.redhat.com/drepper/tls.pdf
 677
 678   SDValue Address = N.getOperand(1);
 679   if (Address.getOpcode() == X86ISD::SegmentBaseAddress &&
 680       !MatchSegmentBaseAddress (Address, AM))
 681     return false;
 682
 683   return true;
 684 }
 685
 686 bool X86DAGToDAGISel::MatchWrapper(SDValue N, X86ISelAddressMode &AM) {
 687   bool SymbolicAddressesAreRIPRel =
 688     getTargetMachine().symbolicAddressesAreRIPRel();
 689   bool is64Bit = Subtarget->is64Bit();
 690   DOUT << "Wrapper: 64bit " << is64Bit;
 691   DOUT << " AM "; DEBUG(AM.dump()); DOUT << "\n";
 692
 693   // Under X86-64 non-small code model, GV (and friends) are 64-bits.
 694   if (is64Bit && (TM.getCodeModel() != CodeModel::Small))
 695     return true;
 696
 697   // Base and index reg must be 0 in order to use rip as base.
 698   bool canUsePICRel = !AM.Base.Reg.getNode() && !AM.IndexReg.getNode();
 699   if (is64Bit && !canUsePICRel && SymbolicAddressesAreRIPRel)
 700     return true;
 701
 702   if (AM.hasSymbolicDisplacement())
 703     return true;
 704   // If value is available in a register both base and index components have
 705   // been picked, we can't fit the result available in the register in the
 706   // addressing mode. Duplicate GlobalAddress or ConstantPool as displacement.
 707
 708   SDValue N0 = N.getOperand(0);
 709   if (GlobalAddressSDNode *G = dyn_cast<GlobalAddressSDNode>(N0)) {
 710     uint64_t Offset = G->getOffset();
 711     if (!is64Bit || isInt32(AM.Disp + Offset)) {
 712       GlobalValue *GV = G->getGlobal();
 713       bool isRIPRel = SymbolicAddressesAreRIPRel;
 714       if (N0.getOpcode() == llvm::ISD::TargetGlobalTLSAddress) {
 715         TLSModel::Model model =
 716           getTLSModel (GV, TM.getRelocationModel());
 717         if (is64Bit && model == TLSModel::InitialExec)
 718           isRIPRel = true;
 719       }
 720       AM.GV = GV;
 721       AM.Disp += Offset;
 722       AM.isRIPRel = isRIPRel;
 723       return false;
 724     }
 725   } else if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(N0)) {
 726     uint64_t Offset = CP->getOffset();
 727     if (!is64Bit || isInt32(AM.Disp + Offset)) {
 728       AM.CP = CP->getConstVal();
 729       AM.Align = CP->getAlignment();
 730       AM.Disp += Offset;
 731       AM.isRIPRel = SymbolicAddressesAreRIPRel;
 732       return false;
 733     }
 734   } else if (ExternalSymbolSDNode *S =dyn_cast<ExternalSymbolSDNode>(N0)) {
 735     AM.ES = S->getSymbol();
 736     AM.isRIPRel = SymbolicAddressesAreRIPRel;
 737     return false;
 738   } else if (JumpTableSDNode *J = dyn_cast<JumpTableSDNode>(N0)) {
 739     AM.JT = J->getIndex();
 740     AM.isRIPRel = SymbolicAddressesAreRIPRel;
 741     return false;
 742   }
 743
 744   return true;
 745 }
 746
 747 /// MatchAddress - Add the specified node to the specified addressing mode,
 748 /// returning true if it cannot be done.  This just pattern matches for the
 749 /// addressing mode.
 750 bool X86DAGToDAGISel::MatchAddress(SDValue N, X86ISelAddressMode &AM,
 751                                    unsigned Depth) {
 752   bool is64Bit = Subtarget->is64Bit();
 753   DebugLoc dl = N.getDebugLoc();
 754   DOUT << "MatchAddress: "; DEBUG(AM.dump());
 755   // Limit recursion.
 756   if (Depth > 5)
 757     return MatchAddressBase(N, AM);
 758
 759   // RIP relative addressing: %rip + 32-bit displacement!
 760   if (AM.isRIPRel) {
 761     if (!AM.ES && AM.JT != -1 && N.getOpcode() == ISD::Constant) {
 762       uint64_t Val = cast<ConstantSDNode>(N)->getSExtValue();
 763       if (!is64Bit || isInt32(AM.Disp + Val)) {
 764         AM.Disp += Val;
 765         return false;
 766       }
 767     }
 768     return true;
 769   }
 770
 771   switch (N.getOpcode()) {
 772   default: break;
 773   case ISD::Constant: {
 774     uint64_t Val = cast<ConstantSDNode>(N)->getSExtValue();
 775     if (!is64Bit || isInt32(AM.Disp + Val)) {
 776       AM.Disp += Val;
 777       return false;
 778     }
 779     break;
 780   }
 781
 782   case X86ISD::SegmentBaseAddress:
 783     if (!MatchSegmentBaseAddress(N, AM))
 784       return false;
 785     break;
 786
 787   case X86ISD::Wrapper:
 788     if (!MatchWrapper(N, AM))
 789       return false;
 790     break;
 791
 792   case ISD::LOAD:
 793     if (!MatchLoad(N, AM))
 794       return false;
 795     break;
 796
 797   case ISD::FrameIndex:
 798     if (AM.BaseType == X86ISelAddressMode::RegBase
 799         && AM.Base.Reg.getNode() == 0) {
 800       AM.BaseType = X86ISelAddressMode::FrameIndexBase;
 801       AM.Base.FrameIndex = cast<FrameIndexSDNode>(N)->getIndex();
 802       return false;
 803     }
 804     break;
 805
 806   case ISD::SHL:
 807     if (AM.IndexReg.getNode() != 0 || AM.Scale != 1 || AM.isRIPRel)
 808       break;
 809
 810     if (ConstantSDNode
 811           *CN = dyn_cast<ConstantSDNode>(N.getNode()->getOperand(1))) {
 812       unsigned Val = CN->getZExtValue();
 813       if (Val == 1 || Val == 2 || Val == 3) {
 814         AM.Scale = 1 << Val;
 815         SDValue ShVal = N.getNode()->getOperand(0);
 816
 817         // Okay, we know that we have a scale by now.  However, if the scaled
 818         // value is an add of something and a constant, we can fold the
 819         // constant into the disp field here.
 820         if (ShVal.getNode()->getOpcode() == ISD::ADD && ShVal.hasOneUse() &&
 821             isa<ConstantSDNode>(ShVal.getNode()->getOperand(1))) {
 822           AM.IndexReg = ShVal.getNode()->getOperand(0);
 823           ConstantSDNode *AddVal =
 824             cast<ConstantSDNode>(ShVal.getNode()->getOperand(1));
 825           uint64_t Disp = AM.Disp + (AddVal->getSExtValue() << Val);
 826           if (!is64Bit || isInt32(Disp))
 827             AM.Disp = Disp;
 828           else
 829             AM.IndexReg = ShVal;
 830         } else {
 831           AM.IndexReg = ShVal;
 832         }
 833         return false;
 834       }
 835     break;
 836     }
 837
 838   case ISD::SMUL_LOHI:
 839   case ISD::UMUL_LOHI:
 840     // A mul_lohi where we need the low part can be folded as a plain multiply.
 841     if (N.getResNo() != 0) break;
 842     // FALL THROUGH
 843   case ISD::MUL:
 844   case X86ISD::MUL_IMM:
 845     // X*[3,5,9] -> X+X*[2,4,8]
 846     if (AM.BaseType == X86ISelAddressMode::RegBase &&
 847         AM.Base.Reg.getNode() == 0 &&
 848         AM.IndexReg.getNode() == 0 &&
 849         !AM.isRIPRel) {
 850       if (ConstantSDNode
 851             *CN = dyn_cast<ConstantSDNode>(N.getNode()->getOperand(1)))
 852         if (CN->getZExtValue() == 3 || CN->getZExtValue() == 5 ||
 853             CN->getZExtValue() == 9) {
 854           AM.Scale = unsigned(CN->getZExtValue())-1;
 855
 856           SDValue MulVal = N.getNode()->getOperand(0);
 857           SDValue Reg;
 858
 859           // Okay, we know that we have a scale by now.  However, if the scaled
 860           // value is an add of something and a constant, we can fold the
 861           // constant into the disp field here.
 862           if (MulVal.getNode()->getOpcode() == ISD::ADD && MulVal.hasOneUse() &&
 863               isa<ConstantSDNode>(MulVal.getNode()->getOperand(1))) {
 864             Reg = MulVal.getNode()->getOperand(0);
 865             ConstantSDNode *AddVal =
 866               cast<ConstantSDNode>(MulVal.getNode()->getOperand(1));
 867             uint64_t Disp = AM.Disp + AddVal->getSExtValue() *
 868                                       CN->getZExtValue();
 869             if (!is64Bit || isInt32(Disp))
 870               AM.Disp = Disp;
 871             else
 872               Reg = N.getNode()->getOperand(0);
 873           } else {
 874             Reg = N.getNode()->getOperand(0);
 875           }
 876
 877           AM.IndexReg = AM.Base.Reg = Reg;
 878           return false;
 879         }
 880     }
 881     break;
 882
 883   case ISD::SUB: {
 884     // Given A-B, if A can be completely folded into the address and
 885     // the index field with the index field unused, use -B as the index.
 886     // This is a win if a has multiple parts that can be folded into
 887     // the address. Also, this saves a mov if the base register has
 888     // other uses, since it avoids a two-address sub instruction, however
 889     // it costs an additional mov if the index register has other uses.
 890
 891     // Test if the LHS of the sub can be folded.
 892     X86ISelAddressMode Backup = AM;
 893     if (MatchAddress(N.getNode()->getOperand(0), AM, Depth+1)) {
 894       AM = Backup;
 895       break;
 896     }
 897     // Test if the index field is free for use.
 898     if (AM.IndexReg.getNode() || AM.isRIPRel) {
 899       AM = Backup;
 900       break;
 901     }
 902     int Cost = 0;
 903     SDValue RHS = N.getNode()->getOperand(1);
 904     // If the RHS involves a register with multiple uses, this
 905     // transformation incurs an extra mov, due to the neg instruction
 906     // clobbering its operand.
 907     if (!RHS.getNode()->hasOneUse() ||
 908         RHS.getNode()->getOpcode() == ISD::CopyFromReg ||
 909         RHS.getNode()->getOpcode() == ISD::TRUNCATE ||
 910         RHS.getNode()->getOpcode() == ISD::ANY_EXTEND ||
 911         (RHS.getNode()->getOpcode() == ISD::ZERO_EXTEND &&
 912          RHS.getNode()->getOperand(0).getValueType() == MVT::i32))
 913       ++Cost;
 914     // If the base is a register with multiple uses, this
 915     // transformation may save a mov.
 916     if ((AM.BaseType == X86ISelAddressMode::RegBase &&
 917          AM.Base.Reg.getNode() &&
 918          !AM.Base.Reg.getNode()->hasOneUse()) ||
 919         AM.BaseType == X86ISelAddressMode::FrameIndexBase)
 920       --Cost;
 921     // If the folded LHS was interesting, this transformation saves
 922     // address arithmetic.
 923     if ((AM.hasSymbolicDisplacement() && !Backup.hasSymbolicDisplacement()) +
 924         ((AM.Disp != 0) && (Backup.Disp == 0)) +
 925         (AM.Segment.getNode() && !Backup.Segment.getNode()) >= 2)
 926       --Cost;
 927     // If it doesn't look like it may be an overall win, don't do it.
 928     if (Cost >= 0) {
 929       AM = Backup;
 930       break;
 931     }
 932
 933     // Ok, the transformation is legal and appears profitable. Go for it.
 934     SDValue Zero = CurDAG->getConstant(0, N.getValueType());
 935     SDValue Neg = CurDAG->getNode(ISD::SUB, dl, N.getValueType(), Zero, RHS);
 936     AM.IndexReg = Neg;
 937     AM.Scale = 1;
 938
 939     // Insert the new nodes into the topological ordering.
 940     if (Zero.getNode()->getNodeId() == -1 ||
 941         Zero.getNode()->getNodeId() > N.getNode()->getNodeId()) {
 942       CurDAG->RepositionNode(N.getNode(), Zero.getNode());
 943       Zero.getNode()->setNodeId(N.getNode()->getNodeId());
 944     }
 945     if (Neg.getNode()->getNodeId() == -1 ||
 946         Neg.getNode()->getNodeId() > N.getNode()->getNodeId()) {
 947       CurDAG->RepositionNode(N.getNode(), Neg.getNode());
 948       Neg.getNode()->setNodeId(N.getNode()->getNodeId());
 949     }
 950     return false;
 951   }
 952
 953   case ISD::ADD: {
 954     X86ISelAddressMode Backup = AM;
 955     if (!MatchAddress(N.getNode()->getOperand(0), AM, Depth+1) &&
 956         !MatchAddress(N.getNode()->getOperand(1), AM, Depth+1))
 957       return false;
 958     AM = Backup;
 959     if (!MatchAddress(N.getNode()->getOperand(1), AM, Depth+1) &&
 960         !MatchAddress(N.getNode()->getOperand(0), AM, Depth+1))
 961       return false;
 962     AM = Backup;
 963
 964     // If we couldn't fold both operands into the address at the same time,
 965     // see if we can just put each operand into a register and fold at least
 966     // the add.
 967     if (AM.BaseType == X86ISelAddressMode::RegBase &&
 968         !AM.Base.Reg.getNode() &&
 969         !AM.IndexReg.getNode() &&
 970         !AM.isRIPRel) {
 971       AM.Base.Reg = N.getNode()->getOperand(0);
 972       AM.IndexReg = N.getNode()->getOperand(1);
 973       AM.Scale = 1;
 974       return false;
 975     }
 976     break;
 977   }
 978
 979   case ISD::OR:
 980     // Handle "X | C" as "X + C" iff X is known to have C bits clear.
 981     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
 982       X86ISelAddressMode Backup = AM;
 983       uint64_t Offset = CN->getSExtValue();
 984       // Start with the LHS as an addr mode.
 985       if (!MatchAddress(N.getOperand(0), AM, Depth+1) &&
 986           // Address could not have picked a GV address for the displacement.
 987           AM.GV == NULL &&
 988           // On x86-64, the resultant disp must fit in 32-bits.
 989           (!is64Bit || isInt32(AM.Disp + Offset)) &&
 990           // Check to see if the LHS & C is zero.
 991           CurDAG->MaskedValueIsZero(N.getOperand(0), CN->getAPIntValue())) {
 992         AM.Disp += Offset;
 993         return false;
 994       }
 995       AM = Backup;
 996     }
 997     break;
 998
 999   case ISD::AND: {
1000     // Perform some heroic transforms on an and of a constant-count shift
1001     // with a constant to enable use of the scaled offset field.
1002
1003     SDValue Shift = N.getOperand(0);
1004     if (Shift.getNumOperands() != 2) break;
1005
1006     // Scale must not be used already.
1007     if (AM.IndexReg.getNode() != 0 || AM.Scale != 1) break;
1008
1009     // Not when RIP is used as the base.
1010     if (AM.isRIPRel) break;
1011
1012     SDValue X = Shift.getOperand(0);
1013     ConstantSDNode *C2 = dyn_cast<ConstantSDNode>(N.getOperand(1));
1014     ConstantSDNode *C1 = dyn_cast<ConstantSDNode>(Shift.getOperand(1));
1015     if (!C1 || !C2) break;
1016
1017     // Handle "(X >> (8-C1)) & C2" as "(X >> 8) & 0xff)" if safe. This
1018     // allows us to convert the shift and and into an h-register extract and
1019     // a scaled index.
1020     if (Shift.getOpcode() == ISD::SRL && Shift.hasOneUse()) {
1021       unsigned ScaleLog = 8 - C1->getZExtValue();
1022       if (ScaleLog > 0 && ScaleLog < 4 &&
1023           C2->getZExtValue() == (UINT64_C(0xff) << ScaleLog)) {
1024         SDValue Eight = CurDAG->getConstant(8, MVT::i8);
1025         SDValue Mask = CurDAG->getConstant(0xff, N.getValueType());
1026         SDValue Srl = CurDAG->getNode(ISD::SRL, dl, N.getValueType(),
1027                                       X, Eight);
1028         SDValue And = CurDAG->getNode(ISD::AND, dl, N.getValueType(),
1029                                       Srl, Mask);
1030         SDValue ShlCount = CurDAG->getConstant(ScaleLog, MVT::i8);
1031         SDValue Shl = CurDAG->getNode(ISD::SHL, dl, N.getValueType(),
1032                                       And, ShlCount);
1033
1034         // Insert the new nodes into the topological ordering.
1035         if (Eight.getNode()->getNodeId() == -1 ||
1036             Eight.getNode()->getNodeId() > X.getNode()->getNodeId()) {
1037           CurDAG->RepositionNode(X.getNode(), Eight.getNode());
1038           Eight.getNode()->setNodeId(X.getNode()->getNodeId());
1039         }
1040         if (Mask.getNode()->getNodeId() == -1 ||
1041             Mask.getNode()->getNodeId() > X.getNode()->getNodeId()) {
1042           CurDAG->RepositionNode(X.getNode(), Mask.getNode());
1043           Mask.getNode()->setNodeId(X.getNode()->getNodeId());
1044         }
1045         if (Srl.getNode()->getNodeId() == -1 ||
1046             Srl.getNode()->getNodeId() > Shift.getNode()->getNodeId()) {
1047           CurDAG->RepositionNode(Shift.getNode(), Srl.getNode());
1048           Srl.getNode()->setNodeId(Shift.getNode()->getNodeId());
1049         }
1050         if (And.getNode()->getNodeId() == -1 ||
1051             And.getNode()->getNodeId() > N.getNode()->getNodeId()) {
1052           CurDAG->RepositionNode(N.getNode(), And.getNode());
1053           And.getNode()->setNodeId(N.getNode()->getNodeId());
1054         }
1055         if (ShlCount.getNode()->getNodeId() == -1 ||
1056             ShlCount.getNode()->getNodeId() > X.getNode()->getNodeId()) {
1057           CurDAG->RepositionNode(X.getNode(), ShlCount.getNode());
1058           ShlCount.getNode()->setNodeId(N.getNode()->getNodeId());
1059         }
1060         if (Shl.getNode()->getNodeId() == -1 ||
1061             Shl.getNode()->getNodeId() > N.getNode()->getNodeId()) {
1062           CurDAG->RepositionNode(N.getNode(), Shl.getNode());
1063           Shl.getNode()->setNodeId(N.getNode()->getNodeId());
1064         }
1065         CurDAG->ReplaceAllUsesWith(N, Shl);
1066         AM.IndexReg = And;
1067         AM.Scale = (1 << ScaleLog);
1068         return false;
1069       }
1070     }
1071
1072     // Handle "(X << C1) & C2" as "(X & (C2>>C1)) << C1" if safe and if this
1073     // allows us to fold the shift into this addressing mode.
1074     if (Shift.getOpcode() != ISD::SHL) break;
1075
1076     // Not likely to be profitable if either the AND or SHIFT node has more
1077     // than one use (unless all uses are for address computation). Besides,
1078     // isel mechanism requires their node ids to be reused.
1079     if (!N.hasOneUse() || !Shift.hasOneUse())
1080       break;
1081
1082     // Verify that the shift amount is something we can fold.
1083     unsigned ShiftCst = C1->getZExtValue();
1084     if (ShiftCst != 1 && ShiftCst != 2 && ShiftCst != 3)
1085       break;
1086
1087     // Get the new AND mask, this folds to a constant.
1088     SDValue NewANDMask = CurDAG->getNode(ISD::SRL, dl, N.getValueType(),
1089                                          SDValue(C2, 0), SDValue(C1, 0));
1090     SDValue NewAND = CurDAG->getNode(ISD::AND, dl, N.getValueType(), X,
1091                                      NewANDMask);
1092     SDValue NewSHIFT = CurDAG->getNode(ISD::SHL, dl, N.getValueType(),
1093                                        NewAND, SDValue(C1, 0));
1094
1095     // Insert the new nodes into the topological ordering.
1096     if (C1->getNodeId() > X.getNode()->getNodeId()) {
1097       CurDAG->RepositionNode(X.getNode(), C1);
1098       C1->setNodeId(X.getNode()->getNodeId());
1099     }
1100     if (NewANDMask.getNode()->getNodeId() == -1 ||
1101         NewANDMask.getNode()->getNodeId() > X.getNode()->getNodeId()) {
1102       CurDAG->RepositionNode(X.getNode(), NewANDMask.getNode());
1103       NewANDMask.getNode()->setNodeId(X.getNode()->getNodeId());
1104     }
1105     if (NewAND.getNode()->getNodeId() == -1 ||
1106         NewAND.getNode()->getNodeId() > Shift.getNode()->getNodeId()) {
1107       CurDAG->RepositionNode(Shift.getNode(), NewAND.getNode());
1108       NewAND.getNode()->setNodeId(Shift.getNode()->getNodeId());
1109     }
1110     if (NewSHIFT.getNode()->getNodeId() == -1 ||
1111         NewSHIFT.getNode()->getNodeId() > N.getNode()->getNodeId()) {
1112       CurDAG->RepositionNode(N.getNode(), NewSHIFT.getNode());
1113       NewSHIFT.getNode()->setNodeId(N.getNode()->getNodeId());
1114     }
1115
1116     CurDAG->ReplaceAllUsesWith(N, NewSHIFT);
1117
1118     AM.Scale = 1 << ShiftCst;
1119     AM.IndexReg = NewAND;
1120     return false;
1121   }
1122   }
1123
1124   return MatchAddressBase(N, AM);
1125 }
1126
1127 /// MatchAddressBase - Helper for MatchAddress. Add the specified node to the
1128 /// specified addressing mode without any further recursion.
1129 bool X86DAGToDAGISel::MatchAddressBase(SDValue N, X86ISelAddressMode &AM) {
1130   // Is the base register already occupied?
1131   if (AM.BaseType != X86ISelAddressMode::RegBase || AM.Base.Reg.getNode()) {
1132     // If so, check to see if the scale index register is set.
1133     if (AM.IndexReg.getNode() == 0 && !AM.isRIPRel) {
1134       AM.IndexReg = N;
1135       AM.Scale = 1;
1136       return false;
1137     }
1138
1139     // Otherwise, we cannot select it.
1140     return true;
1141   }
1142
1143   // Default, generate it as a register.
1144   AM.BaseType = X86ISelAddressMode::RegBase;
1145   AM.Base.Reg = N;
1146   return false;
1147 }
1148
1149 /// SelectAddr - returns true if it is able pattern match an addressing mode.
1150 /// It returns the operands which make up the maximal addressing mode it can
1151 /// match by reference.
1152 bool X86DAGToDAGISel::SelectAddr(SDValue Op, SDValue N, SDValue &Base,
1153                                  SDValue &Scale, SDValue &Index,
1154                                  SDValue &Disp, SDValue &Segment) {
1155   X86ISelAddressMode AM;
1156   bool Done = false;
1157   if (AvoidDupAddrCompute && !N.hasOneUse()) {
1158     unsigned Opcode = N.getOpcode();
1159     if (Opcode != ISD::Constant && Opcode != ISD::FrameIndex &&
1160         Opcode != X86ISD::Wrapper) {
1161       // If we are able to fold N into addressing mode, then we'll allow it even
1162       // if N has multiple uses. In general, addressing computation is used as
1163       // addresses by all of its uses. But watch out for CopyToReg uses, that
1164       // means the address computation is liveout. It will be computed by a LEA
1165       // so we want to avoid computing the address twice.
1166       for (SDNode::use_iterator UI = N.getNode()->use_begin(),
1167              UE = N.getNode()->use_end(); UI != UE; ++UI) {
1168         if (UI->getOpcode() == ISD::CopyToReg) {
1169           MatchAddressBase(N, AM);
1170           Done = true;
1171           break;
1172         }
1173       }
1174     }
1175   }
1176
1177   if (!Done && MatchAddress(N, AM))
1178     return false;
1179
1180   MVT VT = N.getValueType();
1181   if (AM.BaseType == X86ISelAddressMode::RegBase) {
1182     if (!AM.Base.Reg.getNode())
1183       AM.Base.Reg = CurDAG->getRegister(0, VT);
1184   }
1185
1186   if (!AM.IndexReg.getNode())
1187     AM.IndexReg = CurDAG->getRegister(0, VT);
1188
1189   getAddressOperands(AM, Base, Scale, Index, Disp, Segment);
1190   return true;
1191 }
1192
1193 /// SelectScalarSSELoad - Match a scalar SSE load.  In particular, we want to
1194 /// match a load whose top elements are either undef or zeros.  The load flavor
1195 /// is derived from the type of N, which is either v4f32 or v2f64.
1196 bool X86DAGToDAGISel::SelectScalarSSELoad(SDValue Op, SDValue Pred,
1197                                           SDValue N, SDValue &Base,
1198                                           SDValue &Scale, SDValue &Index,
1199                                           SDValue &Disp, SDValue &Segment,
1200                                           SDValue &InChain,
1201                                           SDValue &OutChain) {
1202   if (N.getOpcode() == ISD::SCALAR_TO_VECTOR) {
1203     InChain = N.getOperand(0).getValue(1);
1204     if (ISD::isNON_EXTLoad(InChain.getNode()) &&
1205         InChain.getValue(0).hasOneUse() &&
1206         N.hasOneUse() &&
1207         IsLegalAndProfitableToFold(N.getNode(), Pred.getNode(), Op.getNode())) {
1208       LoadSDNode *LD = cast<LoadSDNode>(InChain);
1209       if (!SelectAddr(Op, LD->getBasePtr(), Base, Scale, Index, Disp, Segment))
1210         return false;
1211       OutChain = LD->getChain();
1212       return true;
1213     }
1214   }
1215
1216   // Also handle the case where we explicitly require zeros in the top
1217   // elements.  This is a vector shuffle from the zero vector.
1218   if (N.getOpcode() == X86ISD::VZEXT_MOVL && N.getNode()->hasOneUse() &&
1219       // Check to see if the top elements are all zeros (or bitcast of zeros).
1220       N.getOperand(0).getOpcode() == ISD::SCALAR_TO_VECTOR &&
1221       N.getOperand(0).getNode()->hasOneUse() &&
1222       ISD::isNON_EXTLoad(N.getOperand(0).getOperand(0).getNode()) &&
1223       N.getOperand(0).getOperand(0).hasOneUse()) {
1224     // Okay, this is a zero extending load.  Fold it.
1225     LoadSDNode *LD = cast<LoadSDNode>(N.getOperand(0).getOperand(0));
1226     if (!SelectAddr(Op, LD->getBasePtr(), Base, Scale, Index, Disp, Segment))
1227       return false;
1228     OutChain = LD->getChain();
1229     InChain = SDValue(LD, 1);
1230     return true;
1231   }
1232   return false;
1233 }
1234
1235
1236 /// SelectLEAAddr - it calls SelectAddr and determines if the maximal addressing
1237 /// mode it matches can be cost effectively emitted as an LEA instruction.
1238 bool X86DAGToDAGISel::SelectLEAAddr(SDValue Op, SDValue N,
1239                                     SDValue &Base, SDValue &Scale,
1240                                     SDValue &Index, SDValue &Disp) {
1241   X86ISelAddressMode AM;
1242
1243   // Set AM.Segment to prevent MatchAddress from using one. LEA doesn't support
1244   // segments.
1245   SDValue Copy = AM.Segment;
1246   SDValue T = CurDAG->getRegister(0, MVT::i32);
1247   AM.Segment = T;
1248   if (MatchAddress(N, AM))
1249     return false;
1250   assert (T == AM.Segment);
1251   AM.Segment = Copy;
1252
1253   MVT VT = N.getValueType();
1254   unsigned Complexity = 0;
1255   if (AM.BaseType == X86ISelAddressMode::RegBase)
1256     if (AM.Base.Reg.getNode())
1257       Complexity = 1;
1258     else
1259       AM.Base.Reg = CurDAG->getRegister(0, VT);
1260   else if (AM.BaseType == X86ISelAddressMode::FrameIndexBase)
1261     Complexity = 4;
1262
1263   if (AM.IndexReg.getNode())
1264     Complexity++;
1265   else
1266     AM.IndexReg = CurDAG->getRegister(0, VT);
1267
1268   // Don't match just leal(,%reg,2). It's cheaper to do addl %reg, %reg, or with
1269   // a simple shift.
1270   if (AM.Scale > 1)
1271     Complexity++;
1272
1273   // FIXME: We are artificially lowering the criteria to turn ADD %reg, $GA
1274   // to a LEA. This is determined with some expermentation but is by no means
1275   // optimal (especially for code size consideration). LEA is nice because of
1276   // its three-address nature. Tweak the cost function again when we can run
1277   // convertToThreeAddress() at register allocation time.
1278   if (AM.hasSymbolicDisplacement()) {
1279     // For X86-64, we should always use lea to materialize RIP relative
1280     // addresses.
1281     if (Subtarget->is64Bit())
1282       Complexity = 4;
1283     else
1284       Complexity += 2;
1285   }
1286
1287   if (AM.Disp && (AM.Base.Reg.getNode() || AM.IndexReg.getNode()))
1288     Complexity++;
1289
1290   if (Complexity > 2) {
1291     SDValue Segment;
1292     getAddressOperands(AM, Base, Scale, Index, Disp, Segment);
1293     return true;
1294   }
1295   return false;
1296 }
1297
1298 /// SelectTLSADDRAddr - This is only run on TargetGlobalTLSAddress nodes.
1299 bool X86DAGToDAGISel::SelectTLSADDRAddr(SDValue Op, SDValue N, SDValue &Base,
1300                                         SDValue &Scale, SDValue &Index,
1301                                         SDValue &Disp) {
1302   assert(Op.getOpcode() == X86ISD::TLSADDR);
1303   assert(N.getOpcode() == ISD::TargetGlobalTLSAddress);
1304   const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
1305
1306   X86ISelAddressMode AM;
1307   AM.GV = GA->getGlobal();
1308   AM.Disp += GA->getOffset();
1309   AM.Base.Reg = CurDAG->getRegister(0, N.getValueType());
1310
1311   if (N.getValueType() == MVT::i32) {
1312     AM.Scale = 1;
1313     AM.IndexReg = CurDAG->getRegister(X86::EBX, MVT::i32);
1314   } else {
1315     AM.IndexReg = CurDAG->getRegister(0, MVT::i64);
1316   }
1317
1318   SDValue Segment;
1319   getAddressOperands(AM, Base, Scale, Index, Disp, Segment);
1320   return true;
1321 }
1322
1323
1324 bool X86DAGToDAGISel::TryFoldLoad(SDValue P, SDValue N,
1325                                   SDValue &Base, SDValue &Scale,
1326                                   SDValue &Index, SDValue &Disp,
1327                                   SDValue &Segment) {
1328   if (ISD::isNON_EXTLoad(N.getNode()) &&
1329       N.hasOneUse() &&
1330       IsLegalAndProfitableToFold(N.getNode(), P.getNode(), P.getNode()))
1331     return SelectAddr(P, N.getOperand(1), Base, Scale, Index, Disp, Segment);
1332   return false;
1333 }
1334
1335 /// getGlobalBaseReg - Return an SDNode that returns the value of
1336 /// the global base register. Output instructions required to
1337 /// initialize the global base register, if necessary.
1338 ///
1339 SDNode *X86DAGToDAGISel::getGlobalBaseReg() {
1340   MachineFunction *MF = CurBB->getParent();
1341   unsigned GlobalBaseReg = getInstrInfo()->getGlobalBaseReg(MF);
1342   return CurDAG->getRegister(GlobalBaseReg, TLI.getPointerTy()).getNode();
1343 }
1344
1345 static SDNode *FindCallStartFromCall(SDNode *Node) {
1346   if (Node->getOpcode() == ISD::CALLSEQ_START) return Node;
1347     assert(Node->getOperand(0).getValueType() == MVT::Other &&
1348          "Node doesn't have a token chain argument!");
1349   return FindCallStartFromCall(Node->getOperand(0).getNode());
1350 }
1351
1352 SDNode *X86DAGToDAGISel::SelectAtomic64(SDNode *Node, unsigned Opc) {
1353   SDValue Chain = Node->getOperand(0);
1354   SDValue In1 = Node->getOperand(1);
1355   SDValue In2L = Node->getOperand(2);
1356   SDValue In2H = Node->getOperand(3);
1357   SDValue Tmp0, Tmp1, Tmp2, Tmp3, Tmp4;
1358   if (!SelectAddr(In1, In1, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4))
1359     return NULL;
1360   SDValue LSI = Node->getOperand(4);    // MemOperand
1361   const SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, In2L, In2H, LSI, Chain};
1362   return CurDAG->getTargetNode(Opc, Node->getDebugLoc(),
1363                                MVT::i32, MVT::i32, MVT::Other, Ops,
1364                                array_lengthof(Ops));
1365 }
1366
1367 SDNode *X86DAGToDAGISel::Select(SDValue N) {
1368   SDNode *Node = N.getNode();
1369   MVT NVT = Node->getValueType(0);
1370   unsigned Opc, MOpc;
1371   unsigned Opcode = Node->getOpcode();
1372   DebugLoc dl = Node->getDebugLoc();
1373
1374 #ifndef NDEBUG
1375   DOUT << std::string(Indent, ' ') << "Selecting: ";
1376   DEBUG(Node->dump(CurDAG));
1377   DOUT << "\n";
1378   Indent += 2;
1379 #endif
1380
1381   if (Node->isMachineOpcode()) {
1382 #ifndef NDEBUG
1383     DOUT << std::string(Indent-2, ' ') << "== ";
1384     DEBUG(Node->dump(CurDAG));
1385     DOUT << "\n";
1386     Indent -= 2;
1387 #endif
1388     return NULL;   // Already selected.
1389   }
1390
1391   switch (Opcode) {
1392     default: break;
1393     case X86ISD::GlobalBaseReg:
1394       return getGlobalBaseReg();
1395
1396     case X86ISD::ATOMOR64_DAG:
1397       return SelectAtomic64(Node, X86::ATOMOR6432);
1398     case X86ISD::ATOMXOR64_DAG:
1399       return SelectAtomic64(Node, X86::ATOMXOR6432);
1400     case X86ISD::ATOMADD64_DAG:
1401       return SelectAtomic64(Node, X86::ATOMADD6432);
1402     case X86ISD::ATOMSUB64_DAG:
1403       return SelectAtomic64(Node, X86::ATOMSUB6432);
1404     case X86ISD::ATOMNAND64_DAG:
1405       return SelectAtomic64(Node, X86::ATOMNAND6432);
1406     case X86ISD::ATOMAND64_DAG:
1407       return SelectAtomic64(Node, X86::ATOMAND6432);
1408     case X86ISD::ATOMSWAP64_DAG:
1409       return SelectAtomic64(Node, X86::ATOMSWAP6432);
1410
1411     case ISD::SMUL_LOHI:
1412     case ISD::UMUL_LOHI: {
1413       SDValue N0 = Node->getOperand(0);
1414       SDValue N1 = Node->getOperand(1);
1415
1416       bool isSigned = Opcode == ISD::SMUL_LOHI;
1417       if (!isSigned)
1418         switch (NVT.getSimpleVT()) {
1419         default: assert(0 && "Unsupported VT!");
1420         case MVT::i8:  Opc = X86::MUL8r;  MOpc = X86::MUL8m;  break;
1421         case MVT::i16: Opc = X86::MUL16r; MOpc = X86::MUL16m; break;
1422         case MVT::i32: Opc = X86::MUL32r; MOpc = X86::MUL32m; break;
1423         case MVT::i64: Opc = X86::MUL64r; MOpc = X86::MUL64m; break;
1424         }
1425       else
1426         switch (NVT.getSimpleVT()) {
1427         default: assert(0 && "Unsupported VT!");
1428         case MVT::i8:  Opc = X86::IMUL8r;  MOpc = X86::IMUL8m;  break;
1429         case MVT::i16: Opc = X86::IMUL16r; MOpc = X86::IMUL16m; break;
1430         case MVT::i32: Opc = X86::IMUL32r; MOpc = X86::IMUL32m; break;
1431         case MVT::i64: Opc = X86::IMUL64r; MOpc = X86::IMUL64m; break;
1432         }
1433
1434       unsigned LoReg, HiReg;
1435       switch (NVT.getSimpleVT()) {
1436       default: assert(0 && "Unsupported VT!");
1437       case MVT::i8:  LoReg = X86::AL;  HiReg = X86::AH;  break;
1438       case MVT::i16: LoReg = X86::AX;  HiReg = X86::DX;  break;
1439       case MVT::i32: LoReg = X86::EAX; HiReg = X86::EDX; break;
1440       case MVT::i64: LoReg = X86::RAX; HiReg = X86::RDX; break;
1441       }
1442
1443       SDValue Tmp0, Tmp1, Tmp2, Tmp3, Tmp4;
1444       bool foldedLoad = TryFoldLoad(N, N1, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4);
1445       // multiplty is commmutative
1446       if (!foldedLoad) {
1447         foldedLoad = TryFoldLoad(N, N0, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4);
1448         if (foldedLoad)
1449           std::swap(N0, N1);
1450       }
1451
1452       SDValue InFlag = CurDAG->getCopyToReg(CurDAG->getEntryNode(), dl, LoReg,
1453                                               N0, SDValue()).getValue(1);
1454
1455       if (foldedLoad) {
1456         SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, N1.getOperand(0),
1457                           InFlag };
1458         SDNode *CNode =
1459           CurDAG->getTargetNode(MOpc, dl, MVT::Other, MVT::Flag, Ops,
1460                                 array_lengthof(Ops));
1461         InFlag = SDValue(CNode, 1);
1462         // Update the chain.
1463         ReplaceUses(N1.getValue(1), SDValue(CNode, 0));
1464       } else {
1465         InFlag =
1466           SDValue(CurDAG->getTargetNode(Opc, dl, MVT::Flag, N1, InFlag), 0);
1467       }
1468
1469       // Copy the low half of the result, if it is needed.
1470       if (!N.getValue(0).use_empty()) {
1471         SDValue Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl,
1472                                                   LoReg, NVT, InFlag);
1473         InFlag = Result.getValue(2);
1474         ReplaceUses(N.getValue(0), Result);
1475 #ifndef NDEBUG
1476         DOUT << std::string(Indent-2, ' ') << "=> ";
1477         DEBUG(Result.getNode()->dump(CurDAG));
1478         DOUT << "\n";
1479 #endif
1480       }
1481       // Copy the high half of the result, if it is needed.
1482       if (!N.getValue(1).use_empty()) {
1483         SDValue Result;
1484         if (HiReg == X86::AH && Subtarget->is64Bit()) {
1485           // Prevent use of AH in a REX instruction by referencing AX instead.
1486           // Shift it down 8 bits.
1487           Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl,
1488                                           X86::AX, MVT::i16, InFlag);
1489           InFlag = Result.getValue(2);
1490           Result = SDValue(CurDAG->getTargetNode(X86::SHR16ri, dl, MVT::i16,
1491                                                  Result,
1492                                      CurDAG->getTargetConstant(8, MVT::i8)), 0);
1493           // Then truncate it down to i8.
1494           SDValue SRIdx = CurDAG->getTargetConstant(X86::SUBREG_8BIT, MVT::i32);
1495           Result = SDValue(CurDAG->getTargetNode(X86::EXTRACT_SUBREG, dl,
1496                                                    MVT::i8, Result, SRIdx), 0);
1497         } else {
1498           Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl,
1499                                           HiReg, NVT, InFlag);
1500           InFlag = Result.getValue(2);
1501         }
1502         ReplaceUses(N.getValue(1), Result);
1503 #ifndef NDEBUG
1504         DOUT << std::string(Indent-2, ' ') << "=> ";
1505         DEBUG(Result.getNode()->dump(CurDAG));
1506         DOUT << "\n";
1507 #endif
1508       }
1509
1510 #ifndef NDEBUG
1511       Indent -= 2;
1512 #endif
1513
1514       return NULL;
1515     }
1516
1517     case ISD::SDIVREM:
1518     case ISD::UDIVREM: {
1519       SDValue N0 = Node->getOperand(0);
1520       SDValue N1 = Node->getOperand(1);
1521
1522       bool isSigned = Opcode == ISD::SDIVREM;
1523       if (!isSigned)
1524         switch (NVT.getSimpleVT()) {
1525         default: assert(0 && "Unsupported VT!");
1526         case MVT::i8:  Opc = X86::DIV8r;  MOpc = X86::DIV8m;  break;
1527         case MVT::i16: Opc = X86::DIV16r; MOpc = X86::DIV16m; break;
1528         case MVT::i32: Opc = X86::DIV32r; MOpc = X86::DIV32m; break;
1529         case MVT::i64: Opc = X86::DIV64r; MOpc = X86::DIV64m; break;
1530         }
1531       else
1532         switch (NVT.getSimpleVT()) {
1533         default: assert(0 && "Unsupported VT!");
1534         case MVT::i8:  Opc = X86::IDIV8r;  MOpc = X86::IDIV8m;  break;
1535         case MVT::i16: Opc = X86::IDIV16r; MOpc = X86::IDIV16m; break;
1536         case MVT::i32: Opc = X86::IDIV32r; MOpc = X86::IDIV32m; break;
1537         case MVT::i64: Opc = X86::IDIV64r; MOpc = X86::IDIV64m; break;
1538         }
1539
1540       unsigned LoReg, HiReg;
1541       unsigned ClrOpcode, SExtOpcode;
1542       switch (NVT.getSimpleVT()) {
1543       default: assert(0 && "Unsupported VT!");
1544       case MVT::i8:
1545         LoReg = X86::AL;  HiReg = X86::AH;
1546         ClrOpcode  = 0;
1547         SExtOpcode = X86::CBW;
1548         break;
1549       case MVT::i16:
1550         LoReg = X86::AX;  HiReg = X86::DX;
1551         ClrOpcode  = X86::MOV16r0;
1552         SExtOpcode = X86::CWD;
1553         break;
1554       case MVT::i32:
1555         LoReg = X86::EAX; HiReg = X86::EDX;
1556         ClrOpcode  = X86::MOV32r0;
1557         SExtOpcode = X86::CDQ;
1558         break;
1559       case MVT::i64:
1560         LoReg = X86::RAX; HiReg = X86::RDX;
1561         ClrOpcode  = X86::MOV64r0;
1562         SExtOpcode = X86::CQO;
1563         break;
1564       }
1565
1566       SDValue Tmp0, Tmp1, Tmp2, Tmp3, Tmp4;
1567       bool foldedLoad = TryFoldLoad(N, N1, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4);
1568       bool signBitIsZero = CurDAG->SignBitIsZero(N0);
1569
1570       SDValue InFlag;
1571       if (NVT == MVT::i8 && (!isSigned || signBitIsZero)) {
1572         // Special case for div8, just use a move with zero extension to AX to
1573         // clear the upper 8 bits (AH).
1574         SDValue Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, Move, Chain;
1575         if (TryFoldLoad(N, N0, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4)) {
1576           SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, N0.getOperand(0) };
1577           Move =
1578             SDValue(CurDAG->getTargetNode(X86::MOVZX16rm8, dl, MVT::i16,
1579                                           MVT::Other, Ops,
1580                                           array_lengthof(Ops)), 0);
1581           Chain = Move.getValue(1);
1582           ReplaceUses(N0.getValue(1), Chain);
1583         } else {
1584           Move =
1585             SDValue(CurDAG->getTargetNode(X86::MOVZX16rr8, dl, MVT::i16, N0),0);
1586           Chain = CurDAG->getEntryNode();
1587         }
1588         Chain  = CurDAG->getCopyToReg(Chain, dl, X86::AX, Move, SDValue());
1589         InFlag = Chain.getValue(1);
1590       } else {
1591         InFlag =
1592           CurDAG->getCopyToReg(CurDAG->getEntryNode(), dl,
1593                                LoReg, N0, SDValue()).getValue(1);
1594         if (isSigned && !signBitIsZero) {
1595           // Sign extend the low part into the high part.
1596           InFlag =
1597             SDValue(CurDAG->getTargetNode(SExtOpcode, dl, MVT::Flag, InFlag),0);
1598         } else {
1599           // Zero out the high part, effectively zero extending the input.
1600           SDValue ClrNode = SDValue(CurDAG->getTargetNode(ClrOpcode, dl, NVT),
1601                                     0);
1602           InFlag = CurDAG->getCopyToReg(CurDAG->getEntryNode(), dl, HiReg,
1603                                         ClrNode, InFlag).getValue(1);
1604         }
1605       }
1606
1607       if (foldedLoad) {
1608         SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, N1.getOperand(0),
1609                           InFlag };
1610         SDNode *CNode =
1611           CurDAG->getTargetNode(MOpc, dl, MVT::Other, MVT::Flag, Ops,
1612                                 array_lengthof(Ops));
1613         InFlag = SDValue(CNode, 1);
1614         // Update the chain.
1615         ReplaceUses(N1.getValue(1), SDValue(CNode, 0));
1616       } else {
1617         InFlag =
1618           SDValue(CurDAG->getTargetNode(Opc, dl, MVT::Flag, N1, InFlag), 0);
1619       }
1620
1621       // Copy the division (low) result, if it is needed.
1622       if (!N.getValue(0).use_empty()) {
1623         SDValue Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl,
1624                                                   LoReg, NVT, InFlag);
1625         InFlag = Result.getValue(2);
1626         ReplaceUses(N.getValue(0), Result);
1627 #ifndef NDEBUG
1628         DOUT << std::string(Indent-2, ' ') << "=> ";
1629         DEBUG(Result.getNode()->dump(CurDAG));
1630         DOUT << "\n";
1631 #endif
1632       }
1633       // Copy the remainder (high) result, if it is needed.
1634       if (!N.getValue(1).use_empty()) {
1635         SDValue Result;
1636         if (HiReg == X86::AH && Subtarget->is64Bit()) {
1637           // Prevent use of AH in a REX instruction by referencing AX instead.
1638           // Shift it down 8 bits.
1639           Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl,
1640                                           X86::AX, MVT::i16, InFlag);
1641           InFlag = Result.getValue(2);
1642           Result = SDValue(CurDAG->getTargetNode(X86::SHR16ri, dl, MVT::i16,
1643                                         Result,
1644                                         CurDAG->getTargetConstant(8, MVT::i8)),
1645                            0);
1646           // Then truncate it down to i8.
1647           SDValue SRIdx = CurDAG->getTargetConstant(X86::SUBREG_8BIT, MVT::i32);
1648           Result = SDValue(CurDAG->getTargetNode(X86::EXTRACT_SUBREG, dl,
1649                                                    MVT::i8, Result, SRIdx), 0);
1650         } else {
1651           Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl,
1652                                           HiReg, NVT, InFlag);
1653           InFlag = Result.getValue(2);
1654         }
1655         ReplaceUses(N.getValue(1), Result);
1656 #ifndef NDEBUG
1657         DOUT << std::string(Indent-2, ' ') << "=> ";
1658         DEBUG(Result.getNode()->dump(CurDAG));
1659         DOUT << "\n";
1660 #endif
1661       }
1662
1663 #ifndef NDEBUG
1664       Indent -= 2;
1665 #endif
1666
1667       return NULL;
1668     }
1669
1670     case ISD::DECLARE: {
1671       // Handle DECLARE nodes here because the second operand may have been
1672       // wrapped in X86ISD::Wrapper.
1673       SDValue Chain = Node->getOperand(0);
1674       SDValue N1 = Node->getOperand(1);
1675       SDValue N2 = Node->getOperand(2);
1676       FrameIndexSDNode *FINode = dyn_cast<FrameIndexSDNode>(N1);
1677
1678       // FIXME: We need to handle this for VLAs.
1679       if (!FINode) {
1680         ReplaceUses(N.getValue(0), Chain);
1681         return NULL;
1682       }
1683
1684       if (N2.getOpcode() == ISD::ADD &&
1685           N2.getOperand(0).getOpcode() == X86ISD::GlobalBaseReg)
1686         N2 = N2.getOperand(1);
1687
1688       // If N2 is not Wrapper(decriptor) then the llvm.declare is mangled
1689       // somehow, just ignore it.
1690       if (N2.getOpcode() != X86ISD::Wrapper) {
1691         ReplaceUses(N.getValue(0), Chain);
1692         return NULL;
1693       }
1694       GlobalAddressSDNode *GVNode =
1695         dyn_cast<GlobalAddressSDNode>(N2.getOperand(0));
1696       if (GVNode == 0) {
1697         ReplaceUses(N.getValue(0), Chain);
1698         return NULL;
1699       }
1700       SDValue Tmp1 = CurDAG->getTargetFrameIndex(FINode->getIndex(),
1701                                                  TLI.getPointerTy());
1702       SDValue Tmp2 = CurDAG->getTargetGlobalAddress(GVNode->getGlobal(),
1703                                                     TLI.getPointerTy());
1704       SDValue Ops[] = { Tmp1, Tmp2, Chain };
1705       return CurDAG->getTargetNode(TargetInstrInfo::DECLARE, dl,
1706                                    MVT::Other, Ops,
1707                                    array_lengthof(Ops));
1708     }
1709   }
1710
1711   SDNode *ResNode = SelectCode(N);
1712
1713 #ifndef NDEBUG
1714   DOUT << std::string(Indent-2, ' ') << "=> ";
1715   if (ResNode == NULL || ResNode == N.getNode())
1716     DEBUG(N.getNode()->dump(CurDAG));
1717   else
1718     DEBUG(ResNode->dump(CurDAG));
1719   DOUT << "\n";
1720   Indent -= 2;
1721 #endif
1722
1723   return ResNode;
1724 }
1725
1726 bool X86DAGToDAGISel::
1727 SelectInlineAsmMemoryOperand(const SDValue &Op, char ConstraintCode,
1728                              std::vector<SDValue> &OutOps) {
1729   SDValue Op0, Op1, Op2, Op3, Op4;
1730   switch (ConstraintCode) {
1731   case 'o':   // offsetable        ??
1732   case 'v':   // not offsetable    ??
1733   default: return true;
1734   case 'm':   // memory
1735     if (!SelectAddr(Op, Op, Op0, Op1, Op2, Op3, Op4))
1736       return true;
1737     break;
1738   }
1739
1740   OutOps.push_back(Op0);
1741   OutOps.push_back(Op1);
1742   OutOps.push_back(Op2);
1743   OutOps.push_back(Op3);
1744   OutOps.push_back(Op4);
1745   return false;
1746 }
1747
1748 /// createX86ISelDag - This pass converts a legalized DAG into a
1749 /// X86-specific DAG, ready for instruction scheduling.
1750 ///
1751 FunctionPass *llvm::createX86ISelDag(X86TargetMachine &TM,
1752                                      llvm::CodeGenOpt::Level OptLevel) {
1753   return new X86DAGToDAGISel(TM, OptLevel);
1754 }