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