lib/Target/X86/X86ISelDAGToDAG.cpp

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