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