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