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 #include "X86.h"
  16 #include "X86InstrBuilder.h"
  17 #include "X86MachineFunctionInfo.h"
  18 #include "X86RegisterInfo.h"
  19 #include "X86Subtarget.h"
  20 #include "X86TargetMachine.h"
  21 #include "llvm/ADT/Statistic.h"
  22 #include "llvm/CodeGen/MachineFrameInfo.h"
  23 #include "llvm/CodeGen/MachineFunction.h"
  24 #include "llvm/CodeGen/MachineInstrBuilder.h"
  25 #include "llvm/CodeGen/MachineRegisterInfo.h"
  26 #include "llvm/CodeGen/SelectionDAGISel.h"
  27 #include "llvm/IR/Function.h"
  28 #include "llvm/IR/Instructions.h"
  29 #include "llvm/IR/Intrinsics.h"
  30 #include "llvm/IR/Type.h"
  31 #include "llvm/Support/Debug.h"
  32 #include "llvm/Support/ErrorHandling.h"
  33 #include "llvm/Support/MathExtras.h"
  34 #include "llvm/Support/raw_ostream.h"
  35 #include "llvm/Target/TargetMachine.h"
  36 #include "llvm/Target/TargetOptions.h"
  37 #include <stdint.h>
  38 using namespace llvm;
  39
  40 #define DEBUG_TYPE "x86-isel"
  41
  42 STATISTIC(NumLoadMoved, "Number of loads moved below TokenFactor");
  43
  44 //===----------------------------------------------------------------------===//
  45 //                      Pattern Matcher Implementation
  46 //===----------------------------------------------------------------------===//
  47
  48 namespace {
  49   /// This corresponds to X86AddressMode, but uses SDValue's instead of register
  50   /// numbers for the leaves of the matched tree.
  51   struct X86ISelAddressMode {
  52     enum {
  53       RegBase,
  54       FrameIndexBase
  55     } BaseType;
  56
  57     // This is really a union, discriminated by BaseType!
  58     SDValue Base_Reg;
  59     int Base_FrameIndex;
  60
  61     unsigned Scale;
  62     SDValue IndexReg;
  63     int32_t Disp;
  64     SDValue Segment;
  65     const GlobalValue *GV;
  66     const Constant *CP;
  67     const BlockAddress *BlockAddr;
  68     const char *ES;
  69     MCSymbol *MCSym;
  70     int JT;
  71     unsigned Align;    // CP alignment.
  72     unsigned char SymbolFlags;  // X86II::MO_*
  73
  74     X86ISelAddressMode()
  75         : BaseType(RegBase), Base_FrameIndex(0), Scale(1), IndexReg(), Disp(0),
  76           Segment(), GV(nullptr), CP(nullptr), BlockAddr(nullptr), ES(nullptr),
  77           MCSym(nullptr), JT(-1), Align(0), SymbolFlags(X86II::MO_NO_FLAG) {}
  78
  79     bool hasSymbolicDisplacement() const {
  80       return GV != nullptr || CP != nullptr || ES != nullptr ||
  81              MCSym != nullptr || JT != -1 || BlockAddr != nullptr;
  82     }
  83
  84     bool hasBaseOrIndexReg() const {
  85       return BaseType == FrameIndexBase ||
  86              IndexReg.getNode() != nullptr || Base_Reg.getNode() != nullptr;
  87     }
  88
  89     /// Return true if this addressing mode is already RIP-relative.
  90     bool isRIPRelative() const {
  91       if (BaseType != RegBase) return false;
  92       if (RegisterSDNode *RegNode =
  93             dyn_cast_or_null<RegisterSDNode>(Base_Reg.getNode()))
  94         return RegNode->getReg() == X86::RIP;
  95       return false;
  96     }
  97
  98     void setBaseReg(SDValue Reg) {
  99       BaseType = RegBase;
 100       Base_Reg = Reg;
 101     }
 102
 103 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 104     void dump() {
 105       dbgs() << "X86ISelAddressMode " << this << '\n';
 106       dbgs() << "Base_Reg ";
 107       if (Base_Reg.getNode())
 108         Base_Reg.getNode()->dump();
 109       else
 110         dbgs() << "nul";
 111       dbgs() << " Base.FrameIndex " << Base_FrameIndex << '\n'
 112              << " Scale" << Scale << '\n'
 113              << "IndexReg ";
 114       if (IndexReg.getNode())
 115         IndexReg.getNode()->dump();
 116       else
 117         dbgs() << "nul";
 118       dbgs() << " Disp " << Disp << '\n'
 119              << "GV ";
 120       if (GV)
 121         GV->dump();
 122       else
 123         dbgs() << "nul";
 124       dbgs() << " CP ";
 125       if (CP)
 126         CP->dump();
 127       else
 128         dbgs() << "nul";
 129       dbgs() << '\n'
 130              << "ES ";
 131       if (ES)
 132         dbgs() << ES;
 133       else
 134         dbgs() << "nul";
 135       dbgs() << " MCSym ";
 136       if (MCSym)
 137         dbgs() << MCSym;
 138       else
 139         dbgs() << "nul";
 140       dbgs() << " JT" << JT << " Align" << Align << '\n';
 141     }
 142 #endif
 143   };
 144 }
 145
 146 namespace {
 147   //===--------------------------------------------------------------------===//
 148   /// ISel - X86-specific code to select X86 machine instructions for
 149   /// SelectionDAG operations.
 150   ///
 151   class X86DAGToDAGISel final : public SelectionDAGISel {
 152     /// Keep a pointer to the X86Subtarget around so that we can
 153     /// make the right decision when generating code for different targets.
 154     const X86Subtarget *Subtarget;
 155
 156     /// If true, selector should try to optimize for code size instead of
 157     /// performance.
 158     bool OptForSize;
 159
 160   public:
 161     explicit X86DAGToDAGISel(X86TargetMachine &tm, CodeGenOpt::Level OptLevel)
 162         : SelectionDAGISel(tm, OptLevel), OptForSize(false) {}
 163
 164     const char *getPassName() const override {
 165       return "X86 DAG->DAG Instruction Selection";
 166     }
 167
 168     bool runOnMachineFunction(MachineFunction &MF) override {
 169       // Reset the subtarget each time through.
 170       Subtarget = &MF.getSubtarget<X86Subtarget>();
 171       SelectionDAGISel::runOnMachineFunction(MF);
 172       return true;
 173     }
 174
 175     void EmitFunctionEntryCode() override;
 176
 177     bool IsProfitableToFold(SDValue N, SDNode *U, SDNode *Root) const override;
 178
 179     void PreprocessISelDAG() override;
 180
 181     inline bool immSext8(SDNode *N) const {
 182       return isInt<8>(cast<ConstantSDNode>(N)->getSExtValue());
 183     }
 184
 185     // True if the 64-bit immediate fits in a 32-bit sign-extended field.
 186     inline bool i64immSExt32(SDNode *N) const {
 187       uint64_t v = cast<ConstantSDNode>(N)->getZExtValue();
 188       return (int64_t)v == (int32_t)v;
 189     }
 190
 191 // Include the pieces autogenerated from the target description.
 192 #include "X86GenDAGISel.inc"
 193
 194   private:
 195     SDNode *Select(SDNode *N) override;
 196     SDNode *selectGather(SDNode *N, unsigned Opc);
 197     SDNode *selectAtomicLoadArith(SDNode *Node, MVT NVT);
 198
 199     bool foldOffsetIntoAddress(uint64_t Offset, X86ISelAddressMode &AM);
 200     bool matchLoadInAddress(LoadSDNode *N, X86ISelAddressMode &AM);
 201     bool matchWrapper(SDValue N, X86ISelAddressMode &AM);
 202     bool matchAddress(SDValue N, X86ISelAddressMode &AM);
 203     bool matchAddressRecursively(SDValue N, X86ISelAddressMode &AM,
 204                                  unsigned Depth);
 205     bool matchAddressBase(SDValue N, X86ISelAddressMode &AM);
 206     bool selectAddr(SDNode *Parent, SDValue N, SDValue &Base,
 207                     SDValue &Scale, SDValue &Index, SDValue &Disp,
 208                     SDValue &Segment);
 209     bool selectVectorAddr(SDNode *Parent, SDValue N, SDValue &Base,
 210                           SDValue &Scale, SDValue &Index, SDValue &Disp,
 211                           SDValue &Segment);
 212     bool selectMOV64Imm32(SDValue N, SDValue &Imm);
 213     bool selectLEAAddr(SDValue N, SDValue &Base,
 214                        SDValue &Scale, SDValue &Index, SDValue &Disp,
 215                        SDValue &Segment);
 216     bool selectLEA64_32Addr(SDValue N, SDValue &Base,
 217                             SDValue &Scale, SDValue &Index, SDValue &Disp,
 218                             SDValue &Segment);
 219     bool selectTLSADDRAddr(SDValue N, SDValue &Base,
 220                            SDValue &Scale, SDValue &Index, SDValue &Disp,
 221                            SDValue &Segment);
 222     bool selectScalarSSELoad(SDNode *Root, SDValue N,
 223                              SDValue &Base, SDValue &Scale,
 224                              SDValue &Index, SDValue &Disp,
 225                              SDValue &Segment,
 226                              SDValue &NodeWithChain);
 227
 228     bool tryFoldLoad(SDNode *P, SDValue N,
 229                      SDValue &Base, SDValue &Scale,
 230                      SDValue &Index, SDValue &Disp,
 231                      SDValue &Segment);
 232
 233     /// Implement addressing mode selection for inline asm expressions.
 234     bool SelectInlineAsmMemoryOperand(const SDValue &Op,
 235                                       unsigned ConstraintID,
 236                                       std::vector<SDValue> &OutOps) override;
 237
 238     void emitSpecialCodeForMain();
 239
 240     inline void getAddressOperands(X86ISelAddressMode &AM, SDLoc DL,
 241                                    SDValue &Base, SDValue &Scale,
 242                                    SDValue &Index, SDValue &Disp,
 243                                    SDValue &Segment) {
 244       Base = (AM.BaseType == X86ISelAddressMode::FrameIndexBase)
 245                  ? CurDAG->getTargetFrameIndex(
 246                        AM.Base_FrameIndex,
 247                        TLI->getPointerTy(CurDAG->getDataLayout()))
 248                  : AM.Base_Reg;
 249       Scale = getI8Imm(AM.Scale, DL);
 250       Index = AM.IndexReg;
 251       // These are 32-bit even in 64-bit mode since RIP-relative offset
 252       // is 32-bit.
 253       if (AM.GV)
 254         Disp = CurDAG->getTargetGlobalAddress(AM.GV, SDLoc(),
 255                                               MVT::i32, AM.Disp,
 256                                               AM.SymbolFlags);
 257       else if (AM.CP)
 258         Disp = CurDAG->getTargetConstantPool(AM.CP, MVT::i32,
 259                                              AM.Align, AM.Disp, AM.SymbolFlags);
 260       else if (AM.ES) {
 261         assert(!AM.Disp && "Non-zero displacement is ignored with ES.");
 262         Disp = CurDAG->getTargetExternalSymbol(AM.ES, MVT::i32, AM.SymbolFlags);
 263       } else if (AM.MCSym) {
 264         assert(!AM.Disp && "Non-zero displacement is ignored with MCSym.");
 265         assert(AM.SymbolFlags == 0 && "oo");
 266         Disp = CurDAG->getMCSymbol(AM.MCSym, MVT::i32);
 267       } else if (AM.JT != -1) {
 268         assert(!AM.Disp && "Non-zero displacement is ignored with JT.");
 269         Disp = CurDAG->getTargetJumpTable(AM.JT, MVT::i32, AM.SymbolFlags);
 270       } else if (AM.BlockAddr)
 271         Disp = CurDAG->getTargetBlockAddress(AM.BlockAddr, MVT::i32, AM.Disp,
 272                                              AM.SymbolFlags);
 273       else
 274         Disp = CurDAG->getTargetConstant(AM.Disp, DL, MVT::i32);
 275
 276       if (AM.Segment.getNode())
 277         Segment = AM.Segment;
 278       else
 279         Segment = CurDAG->getRegister(0, MVT::i32);
 280     }
 281
 282     // Utility function to determine whether we should avoid selecting
 283     // immediate forms of instructions for better code size or not.
 284     // At a high level, we'd like to avoid such instructions when
 285     // we have similar constants used within the same basic block
 286     // that can be kept in a register.
 287     //
 288     bool shouldAvoidImmediateInstFormsForSize(SDNode *N) const {
 289       uint32_t UseCount = 0;
 290
 291       // Do not want to hoist if we're not optimizing for size.
 292       // TODO: We'd like to remove this restriction.
 293       // See the comment in X86InstrInfo.td for more info.
 294       if (!OptForSize)
 295         return false;
 296
 297       // Walk all the users of the immediate.
 298       for (SDNode::use_iterator UI = N->use_begin(),
 299            UE = N->use_end(); (UI != UE) && (UseCount < 2); ++UI) {
 300
 301         SDNode *User = *UI;
 302
 303         // This user is already selected. Count it as a legitimate use and
 304         // move on.
 305         if (User->isMachineOpcode()) {
 306           UseCount++;
 307           continue;
 308         }
 309
 310         // We want to count stores of immediates as real uses.
 311         if (User->getOpcode() == ISD::STORE &&
 312             User->getOperand(1).getNode() == N) {
 313           UseCount++;
 314           continue;
 315         }
 316
 317         // We don't currently match users that have > 2 operands (except
 318         // for stores, which are handled above)
 319         // Those instruction won't match in ISEL, for now, and would
 320         // be counted incorrectly.
 321         // This may change in the future as we add additional instruction
 322         // types.
 323         if (User->getNumOperands() != 2)
 324           continue;
 325
 326         // Immediates that are used for offsets as part of stack
 327         // manipulation should be left alone. These are typically
 328         // used to indicate SP offsets for argument passing and
 329         // will get pulled into stores/pushes (implicitly).
 330         if (User->getOpcode() == X86ISD::ADD ||
 331             User->getOpcode() == ISD::ADD    ||
 332             User->getOpcode() == X86ISD::SUB ||
 333             User->getOpcode() == ISD::SUB) {
 334
 335           // Find the other operand of the add/sub.
 336           SDValue OtherOp = User->getOperand(0);
 337           if (OtherOp.getNode() == N)
 338             OtherOp = User->getOperand(1);
 339
 340           // Don't count if the other operand is SP.
 341           RegisterSDNode *RegNode;
 342           if (OtherOp->getOpcode() == ISD::CopyFromReg &&
 343               (RegNode = dyn_cast_or_null<RegisterSDNode>(
 344                  OtherOp->getOperand(1).getNode())))
 345             if ((RegNode->getReg() == X86::ESP) ||
 346                 (RegNode->getReg() == X86::RSP))
 347               continue;
 348         }
 349
 350         // ... otherwise, count this and move on.
 351         UseCount++;
 352       }
 353
 354       // If we have more than 1 use, then recommend for hoisting.
 355       return (UseCount > 1);
 356     }
 357
 358     /// Return a target constant with the specified value of type i8.
 359     inline SDValue getI8Imm(unsigned Imm, SDLoc DL) {
 360       return CurDAG->getTargetConstant(Imm, DL, MVT::i8);
 361     }
 362
 363     /// Return a target constant with the specified value, of type i32.
 364     inline SDValue getI32Imm(unsigned Imm, SDLoc DL) {
 365       return CurDAG->getTargetConstant(Imm, DL, MVT::i32);
 366     }
 367
 368     /// Return an SDNode that returns the value of the global base register.
 369     /// Output instructions required to initialize the global base register,
 370     /// if necessary.
 371     SDNode *getGlobalBaseReg();
 372
 373     /// Return a reference to the TargetMachine, casted to the target-specific
 374     /// type.
 375     const X86TargetMachine &getTargetMachine() const {
 376       return static_cast<const X86TargetMachine &>(TM);
 377     }
 378
 379     /// Return a reference to the TargetInstrInfo, casted to the target-specific
 380     /// type.
 381     const X86InstrInfo *getInstrInfo() const {
 382       return Subtarget->getInstrInfo();
 383     }
 384
 385     /// \brief Address-mode matching performs shift-of-and to and-of-shift
 386     /// reassociation in order to expose more scaled addressing
 387     /// opportunities.
 388     bool ComplexPatternFuncMutatesDAG() const override {
 389       return true;
 390     }
 391   };
 392 }
 393
 394
 395 bool
 396 X86DAGToDAGISel::IsProfitableToFold(SDValue N, SDNode *U, SDNode *Root) const {
 397   if (OptLevel == CodeGenOpt::None) return false;
 398
 399   if (!N.hasOneUse())
 400     return false;
 401
 402   if (N.getOpcode() != ISD::LOAD)
 403     return true;
 404
 405   // If N is a load, do additional profitability checks.
 406   if (U == Root) {
 407     switch (U->getOpcode()) {
 408     default: break;
 409     case X86ISD::ADD:
 410     case X86ISD::SUB:
 411     case X86ISD::AND:
 412     case X86ISD::XOR:
 413     case X86ISD::OR:
 414     case ISD::ADD:
 415     case ISD::ADDC:
 416     case ISD::ADDE:
 417     case ISD::AND:
 418     case ISD::OR:
 419     case ISD::XOR: {
 420       SDValue Op1 = U->getOperand(1);
 421
 422       // If the other operand is a 8-bit immediate we should fold the immediate
 423       // instead. This reduces code size.
 424       // e.g.
 425       // movl 4(%esp), %eax
 426       // addl $4, %eax
 427       // vs.
 428       // movl $4, %eax
 429       // addl 4(%esp), %eax
 430       // The former is 2 bytes shorter. In case where the increment is 1, then
 431       // the saving can be 4 bytes (by using incl %eax).
 432       if (ConstantSDNode *Imm = dyn_cast<ConstantSDNode>(Op1))
 433         if (Imm->getAPIntValue().isSignedIntN(8))
 434           return false;
 435
 436       // If the other operand is a TLS address, we should fold it instead.
 437       // This produces
 438       // movl    %gs:0, %eax
 439       // leal    i@NTPOFF(%eax), %eax
 440       // instead of
 441       // movl    $i@NTPOFF, %eax
 442       // addl    %gs:0, %eax
 443       // if the block also has an access to a second TLS address this will save
 444       // a load.
 445       // FIXME: This is probably also true for non-TLS addresses.
 446       if (Op1.getOpcode() == X86ISD::Wrapper) {
 447         SDValue Val = Op1.getOperand(0);
 448         if (Val.getOpcode() == ISD::TargetGlobalTLSAddress)
 449           return false;
 450       }
 451     }
 452     }
 453   }
 454
 455   return true;
 456 }
 457
 458 /// Replace the original chain operand of the call with
 459 /// load's chain operand and move load below the call's chain operand.
 460 static void moveBelowOrigChain(SelectionDAG *CurDAG, SDValue Load,
 461                                SDValue Call, SDValue OrigChain) {
 462   SmallVector<SDValue, 8> Ops;
 463   SDValue Chain = OrigChain.getOperand(0);
 464   if (Chain.getNode() == Load.getNode())
 465     Ops.push_back(Load.getOperand(0));
 466   else {
 467     assert(Chain.getOpcode() == ISD::TokenFactor &&
 468            "Unexpected chain operand");
 469     for (unsigned i = 0, e = Chain.getNumOperands(); i != e; ++i)
 470       if (Chain.getOperand(i).getNode() == Load.getNode())
 471         Ops.push_back(Load.getOperand(0));
 472       else
 473         Ops.push_back(Chain.getOperand(i));
 474     SDValue NewChain =
 475       CurDAG->getNode(ISD::TokenFactor, SDLoc(Load), MVT::Other, Ops);
 476     Ops.clear();
 477     Ops.push_back(NewChain);
 478   }
 479   Ops.append(OrigChain->op_begin() + 1, OrigChain->op_end());
 480   CurDAG->UpdateNodeOperands(OrigChain.getNode(), Ops);
 481   CurDAG->UpdateNodeOperands(Load.getNode(), Call.getOperand(0),
 482                              Load.getOperand(1), Load.getOperand(2));
 483
 484   Ops.clear();
 485   Ops.push_back(SDValue(Load.getNode(), 1));
 486   Ops.append(Call->op_begin() + 1, Call->op_end());
 487   CurDAG->UpdateNodeOperands(Call.getNode(), Ops);
 488 }
 489
 490 /// Return true if call address is a load and it can be
 491 /// moved below CALLSEQ_START and the chains leading up to the call.
 492 /// Return the CALLSEQ_START by reference as a second output.
 493 /// In the case of a tail call, there isn't a callseq node between the call
 494 /// chain and the load.
 495 static bool isCalleeLoad(SDValue Callee, SDValue &Chain, bool HasCallSeq) {
 496   // The transformation is somewhat dangerous if the call's chain was glued to
 497   // the call. After MoveBelowOrigChain the load is moved between the call and
 498   // the chain, this can create a cycle if the load is not folded. So it is
 499   // *really* important that we are sure the load will be folded.
 500   if (Callee.getNode() == Chain.getNode() || !Callee.hasOneUse())
 501     return false;
 502   LoadSDNode *LD = dyn_cast<LoadSDNode>(Callee.getNode());
 503   if (!LD ||
 504       LD->isVolatile() ||
 505       LD->getAddressingMode() != ISD::UNINDEXED ||
 506       LD->getExtensionType() != ISD::NON_EXTLOAD)
 507     return false;
 508
 509   // Now let's find the callseq_start.
 510   while (HasCallSeq && Chain.getOpcode() != ISD::CALLSEQ_START) {
 511     if (!Chain.hasOneUse())
 512       return false;
 513     Chain = Chain.getOperand(0);
 514   }
 515
 516   if (!Chain.getNumOperands())
 517     return false;
 518   // Since we are not checking for AA here, conservatively abort if the chain
 519   // writes to memory. It's not safe to move the callee (a load) across a store.
 520   if (isa<MemSDNode>(Chain.getNode()) &&
 521       cast<MemSDNode>(Chain.getNode())->writeMem())
 522     return false;
 523   if (Chain.getOperand(0).getNode() == Callee.getNode())
 524     return true;
 525   if (Chain.getOperand(0).getOpcode() == ISD::TokenFactor &&
 526       Callee.getValue(1).isOperandOf(Chain.getOperand(0).getNode()) &&
 527       Callee.getValue(1).hasOneUse())
 528     return true;
 529   return false;
 530 }
 531
 532 void X86DAGToDAGISel::PreprocessISelDAG() {
 533   // OptForSize is used in pattern predicates that isel is matching.
 534   OptForSize = MF->getFunction()->optForSize();
 535
 536   for (SelectionDAG::allnodes_iterator I = CurDAG->allnodes_begin(),
 537        E = CurDAG->allnodes_end(); I != E; ) {
 538     SDNode *N = &*I++; // Preincrement iterator to avoid invalidation issues.
 539
 540     if (OptLevel != CodeGenOpt::None &&
 541         // Only does this when target favors doesn't favor register indirect
 542         // call.
 543         ((N->getOpcode() == X86ISD::CALL && !Subtarget->callRegIndirect()) ||
 544          (N->getOpcode() == X86ISD::TC_RETURN &&
 545           // Only does this if load can be folded into TC_RETURN.
 546           (Subtarget->is64Bit() ||
 547            getTargetMachine().getRelocationModel() != Reloc::PIC_)))) {
 548       /// Also try moving call address load from outside callseq_start to just
 549       /// before the call to allow it to be folded.
 550       ///
 551       ///     [Load chain]
 552       ///         ^
 553       ///         |
 554       ///       [Load]
 555       ///       ^    ^
 556       ///       |    |
 557       ///      /      \--
 558       ///     /          |
 559       ///[CALLSEQ_START] |
 560       ///     ^          |
 561       ///     |          |
 562       /// [LOAD/C2Reg]   |
 563       ///     |          |
 564       ///      \        /
 565       ///       \      /
 566       ///       [CALL]
 567       bool HasCallSeq = N->getOpcode() == X86ISD::CALL;
 568       SDValue Chain = N->getOperand(0);
 569       SDValue Load  = N->getOperand(1);
 570       if (!isCalleeLoad(Load, Chain, HasCallSeq))
 571         continue;
 572       moveBelowOrigChain(CurDAG, Load, SDValue(N, 0), Chain);
 573       ++NumLoadMoved;
 574       continue;
 575     }
 576
 577     // Lower fpround and fpextend nodes that target the FP stack to be store and
 578     // load to the stack.  This is a gross hack.  We would like to simply mark
 579     // these as being illegal, but when we do that, legalize produces these when
 580     // it expands calls, then expands these in the same legalize pass.  We would
 581     // like dag combine to be able to hack on these between the call expansion
 582     // and the node legalization.  As such this pass basically does "really
 583     // late" legalization of these inline with the X86 isel pass.
 584     // FIXME: This should only happen when not compiled with -O0.
 585     if (N->getOpcode() != ISD::FP_ROUND && N->getOpcode() != ISD::FP_EXTEND)
 586       continue;
 587
 588     MVT SrcVT = N->getOperand(0).getSimpleValueType();
 589     MVT DstVT = N->getSimpleValueType(0);
 590
 591     // If any of the sources are vectors, no fp stack involved.
 592     if (SrcVT.isVector() || DstVT.isVector())
 593       continue;
 594
 595     // If the source and destination are SSE registers, then this is a legal
 596     // conversion that should not be lowered.
 597     const X86TargetLowering *X86Lowering =
 598         static_cast<const X86TargetLowering *>(TLI);
 599     bool SrcIsSSE = X86Lowering->isScalarFPTypeInSSEReg(SrcVT);
 600     bool DstIsSSE = X86Lowering->isScalarFPTypeInSSEReg(DstVT);
 601     if (SrcIsSSE && DstIsSSE)
 602       continue;
 603
 604     if (!SrcIsSSE && !DstIsSSE) {
 605       // If this is an FPStack extension, it is a noop.
 606       if (N->getOpcode() == ISD::FP_EXTEND)
 607         continue;
 608       // If this is a value-preserving FPStack truncation, it is a noop.
 609       if (N->getConstantOperandVal(1))
 610         continue;
 611     }
 612
 613     // Here we could have an FP stack truncation or an FPStack <-> SSE convert.
 614     // FPStack has extload and truncstore.  SSE can fold direct loads into other
 615     // operations.  Based on this, decide what we want to do.
 616     MVT MemVT;
 617     if (N->getOpcode() == ISD::FP_ROUND)
 618       MemVT = DstVT;  // FP_ROUND must use DstVT, we can't do a 'trunc load'.
 619     else
 620       MemVT = SrcIsSSE ? SrcVT : DstVT;
 621
 622     SDValue MemTmp = CurDAG->CreateStackTemporary(MemVT);
 623     SDLoc dl(N);
 624
 625     // FIXME: optimize the case where the src/dest is a load or store?
 626     SDValue Store = CurDAG->getTruncStore(CurDAG->getEntryNode(), dl,
 627                                           N->getOperand(0),
 628                                           MemTmp, MachinePointerInfo(), MemVT,
 629                                           false, false, 0);
 630     SDValue Result = CurDAG->getExtLoad(ISD::EXTLOAD, dl, DstVT, Store, MemTmp,
 631                                         MachinePointerInfo(),
 632                                         MemVT, false, false, false, 0);
 633
 634     // We're about to replace all uses of the FP_ROUND/FP_EXTEND with the
 635     // extload we created.  This will cause general havok on the dag because
 636     // anything below the conversion could be folded into other existing nodes.
 637     // To avoid invalidating 'I', back it up to the convert node.
 638     --I;
 639     CurDAG->ReplaceAllUsesOfValueWith(SDValue(N, 0), Result);
 640
 641     // Now that we did that, the node is dead.  Increment the iterator to the
 642     // next node to process, then delete N.
 643     ++I;
 644     CurDAG->DeleteNode(N);
 645   }
 646 }
 647
 648
 649 /// Emit any code that needs to be executed only in the main function.
 650 void X86DAGToDAGISel::emitSpecialCodeForMain() {
 651   if (Subtarget->isTargetCygMing()) {
 652     TargetLowering::ArgListTy Args;
 653     auto &DL = CurDAG->getDataLayout();
 654
 655     TargetLowering::CallLoweringInfo CLI(*CurDAG);
 656     CLI.setChain(CurDAG->getRoot())
 657         .setCallee(CallingConv::C, Type::getVoidTy(*CurDAG->getContext()),
 658                    CurDAG->getExternalSymbol("__main", TLI->getPointerTy(DL)),
 659                    std::move(Args), 0);
 660     const TargetLowering &TLI = CurDAG->getTargetLoweringInfo();
 661     std::pair<SDValue, SDValue> Result = TLI.LowerCallTo(CLI);
 662     CurDAG->setRoot(Result.second);
 663   }
 664 }
 665
 666 void X86DAGToDAGISel::EmitFunctionEntryCode() {
 667   // If this is main, emit special code for main.
 668   if (const Function *Fn = MF->getFunction())
 669     if (Fn->hasExternalLinkage() && Fn->getName() == "main")
 670       emitSpecialCodeForMain();
 671 }
 672
 673 static bool isDispSafeForFrameIndex(int64_t Val) {
 674   // On 64-bit platforms, we can run into an issue where a frame index
 675   // includes a displacement that, when added to the explicit displacement,
 676   // will overflow the displacement field. Assuming that the frame index
 677   // displacement fits into a 31-bit integer  (which is only slightly more
 678   // aggressive than the current fundamental assumption that it fits into
 679   // a 32-bit integer), a 31-bit disp should always be safe.
 680   return isInt<31>(Val);
 681 }
 682
 683 bool X86DAGToDAGISel::foldOffsetIntoAddress(uint64_t Offset,
 684                                             X86ISelAddressMode &AM) {
 685   // Cannot combine ExternalSymbol displacements with integer offsets.
 686   if (Offset != 0 && (AM.ES || AM.MCSym))
 687     return true;
 688   int64_t Val = AM.Disp + Offset;
 689   CodeModel::Model M = TM.getCodeModel();
 690   if (Subtarget->is64Bit()) {
 691     if (!X86::isOffsetSuitableForCodeModel(Val, M,
 692                                            AM.hasSymbolicDisplacement()))
 693       return true;
 694     // In addition to the checks required for a register base, check that
 695     // we do not try to use an unsafe Disp with a frame index.
 696     if (AM.BaseType == X86ISelAddressMode::FrameIndexBase &&
 697         !isDispSafeForFrameIndex(Val))
 698       return true;
 699   }
 700   AM.Disp = Val;
 701   return false;
 702
 703 }
 704
 705 bool X86DAGToDAGISel::matchLoadInAddress(LoadSDNode *N, X86ISelAddressMode &AM){
 706   SDValue Address = N->getOperand(1);
 707
 708   // load gs:0 -> GS segment register.
 709   // load fs:0 -> FS segment register.
 710   //
 711   // This optimization is valid because the GNU TLS model defines that
 712   // gs:0 (or fs:0 on X86-64) contains its own address.
 713   // For more information see http://people.redhat.com/drepper/tls.pdf
 714   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Address))
 715     if (C->getSExtValue() == 0 && AM.Segment.getNode() == nullptr &&
 716         Subtarget->isTargetLinux())
 717       switch (N->getPointerInfo().getAddrSpace()) {
 718       case 256:
 719         AM.Segment = CurDAG->getRegister(X86::GS, MVT::i16);
 720         return false;
 721       case 257:
 722         AM.Segment = CurDAG->getRegister(X86::FS, MVT::i16);
 723         return false;
 724       }
 725
 726   return true;
 727 }
 728
 729 /// Try to match X86ISD::Wrapper and X86ISD::WrapperRIP nodes into an addressing
 730 /// mode. These wrap things that will resolve down into a symbol reference.
 731 /// If no match is possible, this returns true, otherwise it returns false.
 732 bool X86DAGToDAGISel::matchWrapper(SDValue N, X86ISelAddressMode &AM) {
 733   // If the addressing mode already has a symbol as the displacement, we can
 734   // never match another symbol.
 735   if (AM.hasSymbolicDisplacement())
 736     return true;
 737
 738   SDValue N0 = N.getOperand(0);
 739   CodeModel::Model M = TM.getCodeModel();
 740
 741   // Handle X86-64 rip-relative addresses.  We check this before checking direct
 742   // folding because RIP is preferable to non-RIP accesses.
 743   if (Subtarget->is64Bit() && N.getOpcode() == X86ISD::WrapperRIP &&
 744       // Under X86-64 non-small code model, GV (and friends) are 64-bits, so
 745       // they cannot be folded into immediate fields.
 746       // FIXME: This can be improved for kernel and other models?
 747       (M == CodeModel::Small || M == CodeModel::Kernel)) {
 748     // Base and index reg must be 0 in order to use %rip as base.
 749     if (AM.hasBaseOrIndexReg())
 750       return true;
 751     if (GlobalAddressSDNode *G = dyn_cast<GlobalAddressSDNode>(N0)) {
 752       X86ISelAddressMode Backup = AM;
 753       AM.GV = G->getGlobal();
 754       AM.SymbolFlags = G->getTargetFlags();
 755       if (foldOffsetIntoAddress(G->getOffset(), AM)) {
 756         AM = Backup;
 757         return true;
 758       }
 759     } else if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(N0)) {
 760       X86ISelAddressMode Backup = AM;
 761       AM.CP = CP->getConstVal();
 762       AM.Align = CP->getAlignment();
 763       AM.SymbolFlags = CP->getTargetFlags();
 764       if (foldOffsetIntoAddress(CP->getOffset(), AM)) {
 765         AM = Backup;
 766         return true;
 767       }
 768     } else if (ExternalSymbolSDNode *S = dyn_cast<ExternalSymbolSDNode>(N0)) {
 769       AM.ES = S->getSymbol();
 770       AM.SymbolFlags = S->getTargetFlags();
 771     } else if (auto *S = dyn_cast<MCSymbolSDNode>(N0)) {
 772       AM.MCSym = S->getMCSymbol();
 773     } else if (JumpTableSDNode *J = dyn_cast<JumpTableSDNode>(N0)) {
 774       AM.JT = J->getIndex();
 775       AM.SymbolFlags = J->getTargetFlags();
 776     } else if (BlockAddressSDNode *BA = dyn_cast<BlockAddressSDNode>(N0)) {
 777       X86ISelAddressMode Backup = AM;
 778       AM.BlockAddr = BA->getBlockAddress();
 779       AM.SymbolFlags = BA->getTargetFlags();
 780       if (foldOffsetIntoAddress(BA->getOffset(), AM)) {
 781         AM = Backup;
 782         return true;
 783       }
 784     } else
 785       llvm_unreachable("Unhandled symbol reference node.");
 786
 787     if (N.getOpcode() == X86ISD::WrapperRIP)
 788       AM.setBaseReg(CurDAG->getRegister(X86::RIP, MVT::i64));
 789     return false;
 790   }
 791
 792   // Handle the case when globals fit in our immediate field: This is true for
 793   // X86-32 always and X86-64 when in -mcmodel=small mode.  In 64-bit
 794   // mode, this only applies to a non-RIP-relative computation.
 795   if (!Subtarget->is64Bit() ||
 796       M == CodeModel::Small || M == CodeModel::Kernel) {
 797     assert(N.getOpcode() != X86ISD::WrapperRIP &&
 798            "RIP-relative addressing already handled");
 799     if (GlobalAddressSDNode *G = dyn_cast<GlobalAddressSDNode>(N0)) {
 800       AM.GV = G->getGlobal();
 801       AM.Disp += G->getOffset();
 802       AM.SymbolFlags = G->getTargetFlags();
 803     } else if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(N0)) {
 804       AM.CP = CP->getConstVal();
 805       AM.Align = CP->getAlignment();
 806       AM.Disp += CP->getOffset();
 807       AM.SymbolFlags = CP->getTargetFlags();
 808     } else if (ExternalSymbolSDNode *S = dyn_cast<ExternalSymbolSDNode>(N0)) {
 809       AM.ES = S->getSymbol();
 810       AM.SymbolFlags = S->getTargetFlags();
 811     } else if (auto *S = dyn_cast<MCSymbolSDNode>(N0)) {
 812       AM.MCSym = S->getMCSymbol();
 813     } else if (JumpTableSDNode *J = dyn_cast<JumpTableSDNode>(N0)) {
 814       AM.JT = J->getIndex();
 815       AM.SymbolFlags = J->getTargetFlags();
 816     } else if (BlockAddressSDNode *BA = dyn_cast<BlockAddressSDNode>(N0)) {
 817       AM.BlockAddr = BA->getBlockAddress();
 818       AM.Disp += BA->getOffset();
 819       AM.SymbolFlags = BA->getTargetFlags();
 820     } else
 821       llvm_unreachable("Unhandled symbol reference node.");
 822     return false;
 823   }
 824
 825   return true;
 826 }
 827
 828 /// Add the specified node to the specified addressing mode, returning true if
 829 /// it cannot be done. This just pattern matches for the addressing mode.
 830 bool X86DAGToDAGISel::matchAddress(SDValue N, X86ISelAddressMode &AM) {
 831   if (matchAddressRecursively(N, AM, 0))
 832     return true;
 833
 834   // Post-processing: Convert lea(,%reg,2) to lea(%reg,%reg), which has
 835   // a smaller encoding and avoids a scaled-index.
 836   if (AM.Scale == 2 &&
 837       AM.BaseType == X86ISelAddressMode::RegBase &&
 838       AM.Base_Reg.getNode() == nullptr) {
 839     AM.Base_Reg = AM.IndexReg;
 840     AM.Scale = 1;
 841   }
 842
 843   // Post-processing: Convert foo to foo(%rip), even in non-PIC mode,
 844   // because it has a smaller encoding.
 845   // TODO: Which other code models can use this?
 846   if (TM.getCodeModel() == CodeModel::Small &&
 847       Subtarget->is64Bit() &&
 848       AM.Scale == 1 &&
 849       AM.BaseType == X86ISelAddressMode::RegBase &&
 850       AM.Base_Reg.getNode() == nullptr &&
 851       AM.IndexReg.getNode() == nullptr &&
 852       AM.SymbolFlags == X86II::MO_NO_FLAG &&
 853       AM.hasSymbolicDisplacement())
 854     AM.Base_Reg = CurDAG->getRegister(X86::RIP, MVT::i64);
 855
 856   return false;
 857 }
 858
 859 // Insert a node into the DAG at least before the Pos node's position. This
 860 // will reposition the node as needed, and will assign it a node ID that is <=
 861 // the Pos node's ID. Note that this does *not* preserve the uniqueness of node
 862 // IDs! The selection DAG must no longer depend on their uniqueness when this
 863 // is used.
 864 static void insertDAGNode(SelectionDAG &DAG, SDValue Pos, SDValue N) {
 865   if (N.getNode()->getNodeId() == -1 ||
 866       N.getNode()->getNodeId() > Pos.getNode()->getNodeId()) {
 867     DAG.RepositionNode(Pos.getNode()->getIterator(), N.getNode());
 868     N.getNode()->setNodeId(Pos.getNode()->getNodeId());
 869   }
 870 }
 871
 872 // Transform "(X >> (8-C1)) & (0xff << C1)" to "((X >> 8) & 0xff) << C1" if
 873 // safe. This allows us to convert the shift and and into an h-register
 874 // extract and a scaled index. Returns false if the simplification is
 875 // performed.
 876 static bool foldMaskAndShiftToExtract(SelectionDAG &DAG, SDValue N,
 877                                       uint64_t Mask,
 878                                       SDValue Shift, SDValue X,
 879                                       X86ISelAddressMode &AM) {
 880   if (Shift.getOpcode() != ISD::SRL ||
 881       !isa<ConstantSDNode>(Shift.getOperand(1)) ||
 882       !Shift.hasOneUse())
 883     return true;
 884
 885   int ScaleLog = 8 - Shift.getConstantOperandVal(1);
 886   if (ScaleLog <= 0 || ScaleLog >= 4 ||
 887       Mask != (0xffu << ScaleLog))
 888     return true;
 889
 890   MVT VT = N.getSimpleValueType();
 891   SDLoc DL(N);
 892   SDValue Eight = DAG.getConstant(8, DL, MVT::i8);
 893   SDValue NewMask = DAG.getConstant(0xff, DL, VT);
 894   SDValue Srl = DAG.getNode(ISD::SRL, DL, VT, X, Eight);
 895   SDValue And = DAG.getNode(ISD::AND, DL, VT, Srl, NewMask);
 896   SDValue ShlCount = DAG.getConstant(ScaleLog, DL, MVT::i8);
 897   SDValue Shl = DAG.getNode(ISD::SHL, DL, VT, And, ShlCount);
 898
 899   // Insert the new nodes into the topological ordering. We must do this in
 900   // a valid topological ordering as nothing is going to go back and re-sort
 901   // these nodes. We continually insert before 'N' in sequence as this is
 902   // essentially a pre-flattened and pre-sorted sequence of nodes. There is no
 903   // hierarchy left to express.
 904   insertDAGNode(DAG, N, Eight);
 905   insertDAGNode(DAG, N, Srl);
 906   insertDAGNode(DAG, N, NewMask);
 907   insertDAGNode(DAG, N, And);
 908   insertDAGNode(DAG, N, ShlCount);
 909   insertDAGNode(DAG, N, Shl);
 910   DAG.ReplaceAllUsesWith(N, Shl);
 911   AM.IndexReg = And;
 912   AM.Scale = (1 << ScaleLog);
 913   return false;
 914 }
 915
 916 // Transforms "(X << C1) & C2" to "(X & (C2>>C1)) << C1" if safe and if this
 917 // allows us to fold the shift into this addressing mode. Returns false if the
 918 // transform succeeded.
 919 static bool foldMaskedShiftToScaledMask(SelectionDAG &DAG, SDValue N,
 920                                         uint64_t Mask,
 921                                         SDValue Shift, SDValue X,
 922                                         X86ISelAddressMode &AM) {
 923   if (Shift.getOpcode() != ISD::SHL ||
 924       !isa<ConstantSDNode>(Shift.getOperand(1)))
 925     return true;
 926
 927   // Not likely to be profitable if either the AND or SHIFT node has more
 928   // than one use (unless all uses are for address computation). Besides,
 929   // isel mechanism requires their node ids to be reused.
 930   if (!N.hasOneUse() || !Shift.hasOneUse())
 931     return true;
 932
 933   // Verify that the shift amount is something we can fold.
 934   unsigned ShiftAmt = Shift.getConstantOperandVal(1);
 935   if (ShiftAmt != 1 && ShiftAmt != 2 && ShiftAmt != 3)
 936     return true;
 937
 938   MVT VT = N.getSimpleValueType();
 939   SDLoc DL(N);
 940   SDValue NewMask = DAG.getConstant(Mask >> ShiftAmt, DL, VT);
 941   SDValue NewAnd = DAG.getNode(ISD::AND, DL, VT, X, NewMask);
 942   SDValue NewShift = DAG.getNode(ISD::SHL, DL, VT, NewAnd, Shift.getOperand(1));
 943
 944   // Insert the new nodes into the topological ordering. We must do this in
 945   // a valid topological ordering as nothing is going to go back and re-sort
 946   // these nodes. We continually insert before 'N' in sequence as this is
 947   // essentially a pre-flattened and pre-sorted sequence of nodes. There is no
 948   // hierarchy left to express.
 949   insertDAGNode(DAG, N, NewMask);
 950   insertDAGNode(DAG, N, NewAnd);
 951   insertDAGNode(DAG, N, NewShift);
 952   DAG.ReplaceAllUsesWith(N, NewShift);
 953
 954   AM.Scale = 1 << ShiftAmt;
 955   AM.IndexReg = NewAnd;
 956   return false;
 957 }
 958
 959 // Implement some heroics to detect shifts of masked values where the mask can
 960 // be replaced by extending the shift and undoing that in the addressing mode
 961 // scale. Patterns such as (shl (srl x, c1), c2) are canonicalized into (and
 962 // (srl x, SHIFT), MASK) by DAGCombines that don't know the shl can be done in
 963 // the addressing mode. This results in code such as:
 964 //
 965 //   int f(short *y, int *lookup_table) {
 966 //     ...
 967 //     return *y + lookup_table[*y >> 11];
 968 //   }
 969 //
 970 // Turning into:
 971 //   movzwl (%rdi), %eax
 972 //   movl %eax, %ecx
 973 //   shrl $11, %ecx
 974 //   addl (%rsi,%rcx,4), %eax
 975 //
 976 // Instead of:
 977 //   movzwl (%rdi), %eax
 978 //   movl %eax, %ecx
 979 //   shrl $9, %ecx
 980 //   andl $124, %rcx
 981 //   addl (%rsi,%rcx), %eax
 982 //
 983 // Note that this function assumes the mask is provided as a mask *after* the
 984 // value is shifted. The input chain may or may not match that, but computing
 985 // such a mask is trivial.
 986 static bool foldMaskAndShiftToScale(SelectionDAG &DAG, SDValue N,
 987                                     uint64_t Mask,
 988                                     SDValue Shift, SDValue X,
 989                                     X86ISelAddressMode &AM) {
 990   if (Shift.getOpcode() != ISD::SRL || !Shift.hasOneUse() ||
 991       !isa<ConstantSDNode>(Shift.getOperand(1)))
 992     return true;
 993
 994   unsigned ShiftAmt = Shift.getConstantOperandVal(1);
 995   unsigned MaskLZ = countLeadingZeros(Mask);
 996   unsigned MaskTZ = countTrailingZeros(Mask);
 997
 998   // The amount of shift we're trying to fit into the addressing mode is taken
 999   // from the trailing zeros of the mask.
1000   unsigned AMShiftAmt = MaskTZ;
1001
1002   // There is nothing we can do here unless the mask is removing some bits.
1003   // Also, the addressing mode can only represent shifts of 1, 2, or 3 bits.
1004   if (AMShiftAmt <= 0 || AMShiftAmt > 3) return true;
1005
1006   // We also need to ensure that mask is a continuous run of bits.
1007   if (countTrailingOnes(Mask >> MaskTZ) + MaskTZ + MaskLZ != 64) return true;
1008
1009   // Scale the leading zero count down based on the actual size of the value.
1010   // Also scale it down based on the size of the shift.
1011   MaskLZ -= (64 - X.getSimpleValueType().getSizeInBits()) + ShiftAmt;
1012
1013   // The final check is to ensure that any masked out high bits of X are
1014   // already known to be zero. Otherwise, the mask has a semantic impact
1015   // other than masking out a couple of low bits. Unfortunately, because of
1016   // the mask, zero extensions will be removed from operands in some cases.
1017   // This code works extra hard to look through extensions because we can
1018   // replace them with zero extensions cheaply if necessary.
1019   bool ReplacingAnyExtend = false;
1020   if (X.getOpcode() == ISD::ANY_EXTEND) {
1021     unsigned ExtendBits = X.getSimpleValueType().getSizeInBits() -
1022                           X.getOperand(0).getSimpleValueType().getSizeInBits();
1023     // Assume that we'll replace the any-extend with a zero-extend, and
1024     // narrow the search to the extended value.
1025     X = X.getOperand(0);
1026     MaskLZ = ExtendBits > MaskLZ ? 0 : MaskLZ - ExtendBits;
1027     ReplacingAnyExtend = true;
1028   }
1029   APInt MaskedHighBits =
1030     APInt::getHighBitsSet(X.getSimpleValueType().getSizeInBits(), MaskLZ);
1031   APInt KnownZero, KnownOne;
1032   DAG.computeKnownBits(X, KnownZero, KnownOne);
1033   if (MaskedHighBits != KnownZero) return true;
1034
1035   // We've identified a pattern that can be transformed into a single shift
1036   // and an addressing mode. Make it so.
1037   MVT VT = N.getSimpleValueType();
1038   if (ReplacingAnyExtend) {
1039     assert(X.getValueType() != VT);
1040     // We looked through an ANY_EXTEND node, insert a ZERO_EXTEND.
1041     SDValue NewX = DAG.getNode(ISD::ZERO_EXTEND, SDLoc(X), VT, X);
1042     insertDAGNode(DAG, N, NewX);
1043     X = NewX;
1044   }
1045   SDLoc DL(N);
1046   SDValue NewSRLAmt = DAG.getConstant(ShiftAmt + AMShiftAmt, DL, MVT::i8);
1047   SDValue NewSRL = DAG.getNode(ISD::SRL, DL, VT, X, NewSRLAmt);
1048   SDValue NewSHLAmt = DAG.getConstant(AMShiftAmt, DL, MVT::i8);
1049   SDValue NewSHL = DAG.getNode(ISD::SHL, DL, VT, NewSRL, NewSHLAmt);
1050
1051   // Insert the new nodes into the topological ordering. We must do this in
1052   // a valid topological ordering as nothing is going to go back and re-sort
1053   // these nodes. We continually insert before 'N' in sequence as this is
1054   // essentially a pre-flattened and pre-sorted sequence of nodes. There is no
1055   // hierarchy left to express.
1056   insertDAGNode(DAG, N, NewSRLAmt);
1057   insertDAGNode(DAG, N, NewSRL);
1058   insertDAGNode(DAG, N, NewSHLAmt);
1059   insertDAGNode(DAG, N, NewSHL);
1060   DAG.ReplaceAllUsesWith(N, NewSHL);
1061
1062   AM.Scale = 1 << AMShiftAmt;
1063   AM.IndexReg = NewSRL;
1064   return false;
1065 }
1066
1067 bool X86DAGToDAGISel::matchAddressRecursively(SDValue N, X86ISelAddressMode &AM,
1068                                               unsigned Depth) {
1069   SDLoc dl(N);
1070   DEBUG({
1071       dbgs() << "MatchAddress: ";
1072       AM.dump();
1073     });
1074   // Limit recursion.
1075   if (Depth > 5)
1076     return matchAddressBase(N, AM);
1077
1078   // If this is already a %rip relative address, we can only merge immediates
1079   // into it.  Instead of handling this in every case, we handle it here.
1080   // RIP relative addressing: %rip + 32-bit displacement!
1081   if (AM.isRIPRelative()) {
1082     // FIXME: JumpTable and ExternalSymbol address currently don't like
1083     // displacements.  It isn't very important, but this should be fixed for
1084     // consistency.
1085     if (!(AM.ES || AM.MCSym) && AM.JT != -1)
1086       return true;
1087
1088     if (ConstantSDNode *Cst = dyn_cast<ConstantSDNode>(N))
1089       if (!foldOffsetIntoAddress(Cst->getSExtValue(), AM))
1090         return false;
1091     return true;
1092   }
1093
1094   switch (N.getOpcode()) {
1095   default: break;
1096   case ISD::LOCAL_RECOVER: {
1097     if (!AM.hasSymbolicDisplacement() && AM.Disp == 0)
1098       if (const auto *ESNode = dyn_cast<MCSymbolSDNode>(N.getOperand(0))) {
1099         // Use the symbol and don't prefix it.
1100         AM.MCSym = ESNode->getMCSymbol();
1101         return false;
1102       }
1103     break;
1104   }
1105   case ISD::Constant: {
1106     uint64_t Val = cast<ConstantSDNode>(N)->getSExtValue();
1107     if (!foldOffsetIntoAddress(Val, AM))
1108       return false;
1109     break;
1110   }
1111
1112   case X86ISD::Wrapper:
1113   case X86ISD::WrapperRIP:
1114     if (!matchWrapper(N, AM))
1115       return false;
1116     break;
1117
1118   case ISD::LOAD:
1119     if (!matchLoadInAddress(cast<LoadSDNode>(N), AM))
1120       return false;
1121     break;
1122
1123   case ISD::FrameIndex:
1124     if (AM.BaseType == X86ISelAddressMode::RegBase &&
1125         AM.Base_Reg.getNode() == nullptr &&
1126         (!Subtarget->is64Bit() || isDispSafeForFrameIndex(AM.Disp))) {
1127       AM.BaseType = X86ISelAddressMode::FrameIndexBase;
1128       AM.Base_FrameIndex = cast<FrameIndexSDNode>(N)->getIndex();
1129       return false;
1130     }
1131     break;
1132
1133   case ISD::SHL:
1134     if (AM.IndexReg.getNode() != nullptr || AM.Scale != 1)
1135       break;
1136
1137     if (ConstantSDNode
1138           *CN = dyn_cast<ConstantSDNode>(N.getNode()->getOperand(1))) {
1139       unsigned Val = CN->getZExtValue();
1140       // Note that we handle x<<1 as (,x,2) rather than (x,x) here so
1141       // that the base operand remains free for further matching. If
1142       // the base doesn't end up getting used, a post-processing step
1143       // in MatchAddress turns (,x,2) into (x,x), which is cheaper.
1144       if (Val == 1 || Val == 2 || Val == 3) {
1145         AM.Scale = 1 << Val;
1146         SDValue ShVal = N.getNode()->getOperand(0);
1147
1148         // Okay, we know that we have a scale by now.  However, if the scaled
1149         // value is an add of something and a constant, we can fold the
1150         // constant into the disp field here.
1151         if (CurDAG->isBaseWithConstantOffset(ShVal)) {
1152           AM.IndexReg = ShVal.getNode()->getOperand(0);
1153           ConstantSDNode *AddVal =
1154             cast<ConstantSDNode>(ShVal.getNode()->getOperand(1));
1155           uint64_t Disp = (uint64_t)AddVal->getSExtValue() << Val;
1156           if (!foldOffsetIntoAddress(Disp, AM))
1157             return false;
1158         }
1159
1160         AM.IndexReg = ShVal;
1161         return false;
1162       }
1163     }
1164     break;
1165
1166   case ISD::SRL: {
1167     // Scale must not be used already.
1168     if (AM.IndexReg.getNode() != nullptr || AM.Scale != 1) break;
1169
1170     SDValue And = N.getOperand(0);
1171     if (And.getOpcode() != ISD::AND) break;
1172     SDValue X = And.getOperand(0);
1173
1174     // We only handle up to 64-bit values here as those are what matter for
1175     // addressing mode optimizations.
1176     if (X.getSimpleValueType().getSizeInBits() > 64) break;
1177
1178     // The mask used for the transform is expected to be post-shift, but we
1179     // found the shift first so just apply the shift to the mask before passing
1180     // it down.
1181     if (!isa<ConstantSDNode>(N.getOperand(1)) ||
1182         !isa<ConstantSDNode>(And.getOperand(1)))
1183       break;
1184     uint64_t Mask = And.getConstantOperandVal(1) >> N.getConstantOperandVal(1);
1185
1186     // Try to fold the mask and shift into the scale, and return false if we
1187     // succeed.
1188     if (!foldMaskAndShiftToScale(*CurDAG, N, Mask, N, X, AM))
1189       return false;
1190     break;
1191   }
1192
1193   case ISD::SMUL_LOHI:
1194   case ISD::UMUL_LOHI:
1195     // A mul_lohi where we need the low part can be folded as a plain multiply.
1196     if (N.getResNo() != 0) break;
1197     // FALL THROUGH
1198   case ISD::MUL:
1199   case X86ISD::MUL_IMM:
1200     // X*[3,5,9] -> X+X*[2,4,8]
1201     if (AM.BaseType == X86ISelAddressMode::RegBase &&
1202         AM.Base_Reg.getNode() == nullptr &&
1203         AM.IndexReg.getNode() == nullptr) {
1204       if (ConstantSDNode
1205             *CN = dyn_cast<ConstantSDNode>(N.getNode()->getOperand(1)))
1206         if (CN->getZExtValue() == 3 || CN->getZExtValue() == 5 ||
1207             CN->getZExtValue() == 9) {
1208           AM.Scale = unsigned(CN->getZExtValue())-1;
1209
1210           SDValue MulVal = N.getNode()->getOperand(0);
1211           SDValue Reg;
1212
1213           // Okay, we know that we have a scale by now.  However, if the scaled
1214           // value is an add of something and a constant, we can fold the
1215           // constant into the disp field here.
1216           if (MulVal.getNode()->getOpcode() == ISD::ADD && MulVal.hasOneUse() &&
1217               isa<ConstantSDNode>(MulVal.getNode()->getOperand(1))) {
1218             Reg = MulVal.getNode()->getOperand(0);
1219             ConstantSDNode *AddVal =
1220               cast<ConstantSDNode>(MulVal.getNode()->getOperand(1));
1221             uint64_t Disp = AddVal->getSExtValue() * CN->getZExtValue();
1222             if (foldOffsetIntoAddress(Disp, AM))
1223               Reg = N.getNode()->getOperand(0);
1224           } else {
1225             Reg = N.getNode()->getOperand(0);
1226           }
1227
1228           AM.IndexReg = AM.Base_Reg = Reg;
1229           return false;
1230         }
1231     }
1232     break;
1233
1234   case ISD::SUB: {
1235     // Given A-B, if A can be completely folded into the address and
1236     // the index field with the index field unused, use -B as the index.
1237     // This is a win if a has multiple parts that can be folded into
1238     // the address. Also, this saves a mov if the base register has
1239     // other uses, since it avoids a two-address sub instruction, however
1240     // it costs an additional mov if the index register has other uses.
1241
1242     // Add an artificial use to this node so that we can keep track of
1243     // it if it gets CSE'd with a different node.
1244     HandleSDNode Handle(N);
1245
1246     // Test if the LHS of the sub can be folded.
1247     X86ISelAddressMode Backup = AM;
1248     if (matchAddressRecursively(N.getNode()->getOperand(0), AM, Depth+1)) {
1249       AM = Backup;
1250       break;
1251     }
1252     // Test if the index field is free for use.
1253     if (AM.IndexReg.getNode() || AM.isRIPRelative()) {
1254       AM = Backup;
1255       break;
1256     }
1257
1258     int Cost = 0;
1259     SDValue RHS = Handle.getValue().getNode()->getOperand(1);
1260     // If the RHS involves a register with multiple uses, this
1261     // transformation incurs an extra mov, due to the neg instruction
1262     // clobbering its operand.
1263     if (!RHS.getNode()->hasOneUse() ||
1264         RHS.getNode()->getOpcode() == ISD::CopyFromReg ||
1265         RHS.getNode()->getOpcode() == ISD::TRUNCATE ||
1266         RHS.getNode()->getOpcode() == ISD::ANY_EXTEND ||
1267         (RHS.getNode()->getOpcode() == ISD::ZERO_EXTEND &&
1268          RHS.getNode()->getOperand(0).getValueType() == MVT::i32))
1269       ++Cost;
1270     // If the base is a register with multiple uses, this
1271     // transformation may save a mov.
1272     if ((AM.BaseType == X86ISelAddressMode::RegBase &&
1273          AM.Base_Reg.getNode() &&
1274          !AM.Base_Reg.getNode()->hasOneUse()) ||
1275         AM.BaseType == X86ISelAddressMode::FrameIndexBase)
1276       --Cost;
1277     // If the folded LHS was interesting, this transformation saves
1278     // address arithmetic.
1279     if ((AM.hasSymbolicDisplacement() && !Backup.hasSymbolicDisplacement()) +
1280         ((AM.Disp != 0) && (Backup.Disp == 0)) +
1281         (AM.Segment.getNode() && !Backup.Segment.getNode()) >= 2)
1282       --Cost;
1283     // If it doesn't look like it may be an overall win, don't do it.
1284     if (Cost >= 0) {
1285       AM = Backup;
1286       break;
1287     }
1288
1289     // Ok, the transformation is legal and appears profitable. Go for it.
1290     SDValue Zero = CurDAG->getConstant(0, dl, N.getValueType());
1291     SDValue Neg = CurDAG->getNode(ISD::SUB, dl, N.getValueType(), Zero, RHS);
1292     AM.IndexReg = Neg;
1293     AM.Scale = 1;
1294
1295     // Insert the new nodes into the topological ordering.
1296     insertDAGNode(*CurDAG, N, Zero);
1297     insertDAGNode(*CurDAG, N, Neg);
1298     return false;
1299   }
1300
1301   case ISD::ADD: {
1302     // Add an artificial use to this node so that we can keep track of
1303     // it if it gets CSE'd with a different node.
1304     HandleSDNode Handle(N);
1305
1306     X86ISelAddressMode Backup = AM;
1307     if (!matchAddressRecursively(N.getOperand(0), AM, Depth+1) &&
1308         !matchAddressRecursively(Handle.getValue().getOperand(1), AM, Depth+1))
1309       return false;
1310     AM = Backup;
1311
1312     // Try again after commuting the operands.
1313     if (!matchAddressRecursively(Handle.getValue().getOperand(1), AM, Depth+1)&&
1314         !matchAddressRecursively(Handle.getValue().getOperand(0), AM, Depth+1))
1315       return false;
1316     AM = Backup;
1317
1318     // If we couldn't fold both operands into the address at the same time,
1319     // see if we can just put each operand into a register and fold at least
1320     // the add.
1321     if (AM.BaseType == X86ISelAddressMode::RegBase &&
1322         !AM.Base_Reg.getNode() &&
1323         !AM.IndexReg.getNode()) {
1324       N = Handle.getValue();
1325       AM.Base_Reg = N.getOperand(0);
1326       AM.IndexReg = N.getOperand(1);
1327       AM.Scale = 1;
1328       return false;
1329     }
1330     N = Handle.getValue();
1331     break;
1332   }
1333
1334   case ISD::OR:
1335     // Handle "X | C" as "X + C" iff X is known to have C bits clear.
1336     if (CurDAG->isBaseWithConstantOffset(N)) {
1337       X86ISelAddressMode Backup = AM;
1338       ConstantSDNode *CN = cast<ConstantSDNode>(N.getOperand(1));
1339
1340       // Start with the LHS as an addr mode.
1341       if (!matchAddressRecursively(N.getOperand(0), AM, Depth+1) &&
1342           !foldOffsetIntoAddress(CN->getSExtValue(), AM))
1343         return false;
1344       AM = Backup;
1345     }
1346     break;
1347
1348   case ISD::AND: {
1349     // Perform some heroic transforms on an and of a constant-count shift
1350     // with a constant to enable use of the scaled offset field.
1351
1352     // Scale must not be used already.
1353     if (AM.IndexReg.getNode() != nullptr || AM.Scale != 1) break;
1354
1355     SDValue Shift = N.getOperand(0);
1356     if (Shift.getOpcode() != ISD::SRL && Shift.getOpcode() != ISD::SHL) break;
1357     SDValue X = Shift.getOperand(0);
1358
1359     // We only handle up to 64-bit values here as those are what matter for
1360     // addressing mode optimizations.
1361     if (X.getSimpleValueType().getSizeInBits() > 64) break;
1362
1363     if (!isa<ConstantSDNode>(N.getOperand(1)))
1364       break;
1365     uint64_t Mask = N.getConstantOperandVal(1);
1366
1367     // Try to fold the mask and shift into an extract and scale.
1368     if (!foldMaskAndShiftToExtract(*CurDAG, N, Mask, Shift, X, AM))
1369       return false;
1370
1371     // Try to fold the mask and shift directly into the scale.
1372     if (!foldMaskAndShiftToScale(*CurDAG, N, Mask, Shift, X, AM))
1373       return false;
1374
1375     // Try to swap the mask and shift to place shifts which can be done as
1376     // a scale on the outside of the mask.
1377     if (!foldMaskedShiftToScaledMask(*CurDAG, N, Mask, Shift, X, AM))
1378       return false;
1379     break;
1380   }
1381   }
1382
1383   return matchAddressBase(N, AM);
1384 }
1385
1386 /// Helper for MatchAddress. Add the specified node to the
1387 /// specified addressing mode without any further recursion.
1388 bool X86DAGToDAGISel::matchAddressBase(SDValue N, X86ISelAddressMode &AM) {
1389   // Is the base register already occupied?
1390   if (AM.BaseType != X86ISelAddressMode::RegBase || AM.Base_Reg.getNode()) {
1391     // If so, check to see if the scale index register is set.
1392     if (!AM.IndexReg.getNode()) {
1393       AM.IndexReg = N;
1394       AM.Scale = 1;
1395       return false;
1396     }
1397
1398     // Otherwise, we cannot select it.
1399     return true;
1400   }
1401
1402   // Default, generate it as a register.
1403   AM.BaseType = X86ISelAddressMode::RegBase;
1404   AM.Base_Reg = N;
1405   return false;
1406 }
1407
1408 bool X86DAGToDAGISel::selectVectorAddr(SDNode *Parent, SDValue N, SDValue &Base,
1409                                       SDValue &Scale, SDValue &Index,
1410                                       SDValue &Disp, SDValue &Segment) {
1411
1412   MaskedGatherScatterSDNode *Mgs = dyn_cast<MaskedGatherScatterSDNode>(Parent);
1413   if (!Mgs)
1414     return false;
1415   X86ISelAddressMode AM;
1416   unsigned AddrSpace = Mgs->getPointerInfo().getAddrSpace();
1417   // AddrSpace 256 -> GS, 257 -> FS.
1418   if (AddrSpace == 256)
1419     AM.Segment = CurDAG->getRegister(X86::GS, MVT::i16);
1420   if (AddrSpace == 257)
1421     AM.Segment = CurDAG->getRegister(X86::FS, MVT::i16);
1422
1423   SDLoc DL(N);
1424   Base = Mgs->getBasePtr();
1425   Index = Mgs->getIndex();
1426   unsigned ScalarSize = Mgs->getValue().getValueType().getScalarSizeInBits();
1427   Scale = getI8Imm(ScalarSize/8, DL);
1428
1429   // If Base is 0, the whole address is in index and the Scale is 1
1430   if (isa<ConstantSDNode>(Base)) {
1431     assert(dyn_cast<ConstantSDNode>(Base)->isNullValue() &&
1432            "Unexpected base in gather/scatter");
1433     Scale = getI8Imm(1, DL);
1434     Base = CurDAG->getRegister(0, MVT::i32);
1435   }
1436   if (AM.Segment.getNode())
1437     Segment = AM.Segment;
1438   else
1439     Segment = CurDAG->getRegister(0, MVT::i32);
1440   Disp = CurDAG->getTargetConstant(0, DL, MVT::i32);
1441   return true;
1442 }
1443
1444 /// Returns true if it is able to pattern match an addressing mode.
1445 /// It returns the operands which make up the maximal addressing mode it can
1446 /// match by reference.
1447 ///
1448 /// Parent is the parent node of the addr operand that is being matched.  It
1449 /// is always a load, store, atomic node, or null.  It is only null when
1450 /// checking memory operands for inline asm nodes.
1451 bool X86DAGToDAGISel::selectAddr(SDNode *Parent, SDValue N, SDValue &Base,
1452                                  SDValue &Scale, SDValue &Index,
1453                                  SDValue &Disp, SDValue &Segment) {
1454   X86ISelAddressMode AM;
1455
1456   if (Parent &&
1457       // This list of opcodes are all the nodes that have an "addr:$ptr" operand
1458       // that are not a MemSDNode, and thus don't have proper addrspace info.
1459       Parent->getOpcode() != ISD::INTRINSIC_W_CHAIN && // unaligned loads, fixme
1460       Parent->getOpcode() != ISD::INTRINSIC_VOID && // nontemporal stores
1461       Parent->getOpcode() != X86ISD::TLSCALL && // Fixme
1462       Parent->getOpcode() != X86ISD::EH_SJLJ_SETJMP && // setjmp
1463       Parent->getOpcode() != X86ISD::EH_SJLJ_LONGJMP) { // longjmp
1464     unsigned AddrSpace =
1465       cast<MemSDNode>(Parent)->getPointerInfo().getAddrSpace();
1466     // AddrSpace 256 -> GS, 257 -> FS.
1467     if (AddrSpace == 256)
1468       AM.Segment = CurDAG->getRegister(X86::GS, MVT::i16);
1469     if (AddrSpace == 257)
1470       AM.Segment = CurDAG->getRegister(X86::FS, MVT::i16);
1471   }
1472
1473   if (matchAddress(N, AM))
1474     return false;
1475
1476   MVT VT = N.getSimpleValueType();
1477   if (AM.BaseType == X86ISelAddressMode::RegBase) {
1478     if (!AM.Base_Reg.getNode())
1479       AM.Base_Reg = CurDAG->getRegister(0, VT);
1480   }
1481
1482   if (!AM.IndexReg.getNode())
1483     AM.IndexReg = CurDAG->getRegister(0, VT);
1484
1485   getAddressOperands(AM, SDLoc(N), Base, Scale, Index, Disp, Segment);
1486   return true;
1487 }
1488
1489 /// Match a scalar SSE load. In particular, we want to match a load whose top
1490 /// elements are either undef or zeros. The load flavor is derived from the
1491 /// type of N, which is either v4f32 or v2f64.
1492 ///
1493 /// We also return:
1494 ///   PatternChainNode: this is the matched node that has a chain input and
1495 ///   output.
1496 bool X86DAGToDAGISel::selectScalarSSELoad(SDNode *Root,
1497                                           SDValue N, SDValue &Base,
1498                                           SDValue &Scale, SDValue &Index,
1499                                           SDValue &Disp, SDValue &Segment,
1500                                           SDValue &PatternNodeWithChain) {
1501   if (N.getOpcode() == ISD::SCALAR_TO_VECTOR) {
1502     PatternNodeWithChain = N.getOperand(0);
1503     if (ISD::isNON_EXTLoad(PatternNodeWithChain.getNode()) &&
1504         PatternNodeWithChain.hasOneUse() &&
1505         IsProfitableToFold(N.getOperand(0), N.getNode(), Root) &&
1506         IsLegalToFold(N.getOperand(0), N.getNode(), Root, OptLevel)) {
1507       LoadSDNode *LD = cast<LoadSDNode>(PatternNodeWithChain);
1508       if (!selectAddr(LD, LD->getBasePtr(), Base, Scale, Index, Disp, Segment))
1509         return false;
1510       return true;
1511     }
1512   }
1513
1514   // Also handle the case where we explicitly require zeros in the top
1515   // elements.  This is a vector shuffle from the zero vector.
1516   if (N.getOpcode() == X86ISD::VZEXT_MOVL && N.getNode()->hasOneUse() &&
1517       // Check to see if the top elements are all zeros (or bitcast of zeros).
1518       N.getOperand(0).getOpcode() == ISD::SCALAR_TO_VECTOR &&
1519       N.getOperand(0).getNode()->hasOneUse() &&
1520       ISD::isNON_EXTLoad(N.getOperand(0).getOperand(0).getNode()) &&
1521       N.getOperand(0).getOperand(0).hasOneUse() &&
1522       IsProfitableToFold(N.getOperand(0), N.getNode(), Root) &&
1523       IsLegalToFold(N.getOperand(0), N.getNode(), Root, OptLevel)) {
1524     // Okay, this is a zero extending load.  Fold it.
1525     LoadSDNode *LD = cast<LoadSDNode>(N.getOperand(0).getOperand(0));
1526     if (!selectAddr(LD, LD->getBasePtr(), Base, Scale, Index, Disp, Segment))
1527       return false;
1528     PatternNodeWithChain = SDValue(LD, 0);
1529     return true;
1530   }
1531   return false;
1532 }
1533
1534
1535 bool X86DAGToDAGISel::selectMOV64Imm32(SDValue N, SDValue &Imm) {
1536   if (const ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N)) {
1537     uint64_t ImmVal = CN->getZExtValue();
1538     if ((uint32_t)ImmVal != (uint64_t)ImmVal)
1539       return false;
1540
1541     Imm = CurDAG->getTargetConstant(ImmVal, SDLoc(N), MVT::i64);
1542     return true;
1543   }
1544
1545   // In static codegen with small code model, we can get the address of a label
1546   // into a register with 'movl'. TableGen has already made sure we're looking
1547   // at a label of some kind.
1548   assert(N->getOpcode() == X86ISD::Wrapper &&
1549          "Unexpected node type for MOV32ri64");
1550   N = N.getOperand(0);
1551
1552   if (N->getOpcode() != ISD::TargetConstantPool &&
1553       N->getOpcode() != ISD::TargetJumpTable &&
1554       N->getOpcode() != ISD::TargetGlobalAddress &&
1555       N->getOpcode() != ISD::TargetExternalSymbol &&
1556       N->getOpcode() != ISD::MCSymbol &&
1557       N->getOpcode() != ISD::TargetBlockAddress)
1558     return false;
1559
1560   Imm = N;
1561   return TM.getCodeModel() == CodeModel::Small;
1562 }
1563
1564 bool X86DAGToDAGISel::selectLEA64_32Addr(SDValue N, SDValue &Base,
1565                                          SDValue &Scale, SDValue &Index,
1566                                          SDValue &Disp, SDValue &Segment) {
1567   if (!selectLEAAddr(N, Base, Scale, Index, Disp, Segment))
1568     return false;
1569
1570   SDLoc DL(N);
1571   RegisterSDNode *RN = dyn_cast<RegisterSDNode>(Base);
1572   if (RN && RN->getReg() == 0)
1573     Base = CurDAG->getRegister(0, MVT::i64);
1574   else if (Base.getValueType() == MVT::i32 && !dyn_cast<FrameIndexSDNode>(Base)) {
1575     // Base could already be %rip, particularly in the x32 ABI.
1576     Base = SDValue(CurDAG->getMachineNode(
1577                        TargetOpcode::SUBREG_TO_REG, DL, MVT::i64,
1578                        CurDAG->getTargetConstant(0, DL, MVT::i64),
1579                        Base,
1580                        CurDAG->getTargetConstant(X86::sub_32bit, DL, MVT::i32)),
1581                    0);
1582   }
1583
1584   RN = dyn_cast<RegisterSDNode>(Index);
1585   if (RN && RN->getReg() == 0)
1586     Index = CurDAG->getRegister(0, MVT::i64);
1587   else {
1588     assert(Index.getValueType() == MVT::i32 &&
1589            "Expect to be extending 32-bit registers for use in LEA");
1590     Index = SDValue(CurDAG->getMachineNode(
1591                         TargetOpcode::SUBREG_TO_REG, DL, MVT::i64,
1592                         CurDAG->getTargetConstant(0, DL, MVT::i64),
1593                         Index,
1594                         CurDAG->getTargetConstant(X86::sub_32bit, DL,
1595                                                   MVT::i32)),
1596                     0);
1597   }
1598
1599   return true;
1600 }
1601
1602 /// Calls SelectAddr and determines if the maximal addressing
1603 /// mode it matches can be cost effectively emitted as an LEA instruction.
1604 bool X86DAGToDAGISel::selectLEAAddr(SDValue N,
1605                                     SDValue &Base, SDValue &Scale,
1606                                     SDValue &Index, SDValue &Disp,
1607                                     SDValue &Segment) {
1608   X86ISelAddressMode AM;
1609
1610   // Set AM.Segment to prevent MatchAddress from using one. LEA doesn't support
1611   // segments.
1612   SDValue Copy = AM.Segment;
1613   SDValue T = CurDAG->getRegister(0, MVT::i32);
1614   AM.Segment = T;
1615   if (matchAddress(N, AM))
1616     return false;
1617   assert (T == AM.Segment);
1618   AM.Segment = Copy;
1619
1620   MVT VT = N.getSimpleValueType();
1621   unsigned Complexity = 0;
1622   if (AM.BaseType == X86ISelAddressMode::RegBase)
1623     if (AM.Base_Reg.getNode())
1624       Complexity = 1;
1625     else
1626       AM.Base_Reg = CurDAG->getRegister(0, VT);
1627   else if (AM.BaseType == X86ISelAddressMode::FrameIndexBase)
1628     Complexity = 4;
1629
1630   if (AM.IndexReg.getNode())
1631     Complexity++;
1632   else
1633     AM.IndexReg = CurDAG->getRegister(0, VT);
1634
1635   // Don't match just leal(,%reg,2). It's cheaper to do addl %reg, %reg, or with
1636   // a simple shift.
1637   if (AM.Scale > 1)
1638     Complexity++;
1639
1640   // FIXME: We are artificially lowering the criteria to turn ADD %reg, $GA
1641   // to a LEA. This is determined with some experimentation but is by no means
1642   // optimal (especially for code size consideration). LEA is nice because of
1643   // its three-address nature. Tweak the cost function again when we can run
1644   // convertToThreeAddress() at register allocation time.
1645   if (AM.hasSymbolicDisplacement()) {
1646     // For X86-64, always use LEA to materialize RIP-relative addresses.
1647     if (Subtarget->is64Bit())
1648       Complexity = 4;
1649     else
1650       Complexity += 2;
1651   }
1652
1653   if (AM.Disp && (AM.Base_Reg.getNode() || AM.IndexReg.getNode()))
1654     Complexity++;
1655
1656   // If it isn't worth using an LEA, reject it.
1657   if (Complexity <= 2)
1658     return false;
1659
1660   getAddressOperands(AM, SDLoc(N), Base, Scale, Index, Disp, Segment);
1661   return true;
1662 }
1663
1664 /// This is only run on TargetGlobalTLSAddress nodes.
1665 bool X86DAGToDAGISel::selectTLSADDRAddr(SDValue N, SDValue &Base,
1666                                         SDValue &Scale, SDValue &Index,
1667                                         SDValue &Disp, SDValue &Segment) {
1668   assert(N.getOpcode() == ISD::TargetGlobalTLSAddress);
1669   const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
1670
1671   X86ISelAddressMode AM;
1672   AM.GV = GA->getGlobal();
1673   AM.Disp += GA->getOffset();
1674   AM.Base_Reg = CurDAG->getRegister(0, N.getValueType());
1675   AM.SymbolFlags = GA->getTargetFlags();
1676
1677   if (N.getValueType() == MVT::i32) {
1678     AM.Scale = 1;
1679     AM.IndexReg = CurDAG->getRegister(X86::EBX, MVT::i32);
1680   } else {
1681     AM.IndexReg = CurDAG->getRegister(0, MVT::i64);
1682   }
1683
1684   getAddressOperands(AM, SDLoc(N), Base, Scale, Index, Disp, Segment);
1685   return true;
1686 }
1687
1688
1689 bool X86DAGToDAGISel::tryFoldLoad(SDNode *P, SDValue N,
1690                                   SDValue &Base, SDValue &Scale,
1691                                   SDValue &Index, SDValue &Disp,
1692                                   SDValue &Segment) {
1693   if (!ISD::isNON_EXTLoad(N.getNode()) ||
1694       !IsProfitableToFold(N, P, P) ||
1695       !IsLegalToFold(N, P, P, OptLevel))
1696     return false;
1697
1698   return selectAddr(N.getNode(),
1699                     N.getOperand(1), Base, Scale, Index, Disp, Segment);
1700 }
1701
1702 /// Return an SDNode that returns the value of the global base register.
1703 /// Output instructions required to initialize the global base register,
1704 /// if necessary.
1705 SDNode *X86DAGToDAGISel::getGlobalBaseReg() {
1706   unsigned GlobalBaseReg = getInstrInfo()->getGlobalBaseReg(MF);
1707   auto &DL = MF->getDataLayout();
1708   return CurDAG->getRegister(GlobalBaseReg, TLI->getPointerTy(DL)).getNode();
1709 }
1710
1711 /// Atomic opcode table
1712 ///
1713 enum AtomicOpc {
1714   ADD,
1715   SUB,
1716   INC,
1717   DEC,
1718   OR,
1719   AND,
1720   XOR,
1721   AtomicOpcEnd
1722 };
1723
1724 enum AtomicSz {
1725   ConstantI8,
1726   I8,
1727   SextConstantI16,
1728   ConstantI16,
1729   I16,
1730   SextConstantI32,
1731   ConstantI32,
1732   I32,
1733   SextConstantI64,
1734   ConstantI64,
1735   I64,
1736   AtomicSzEnd
1737 };
1738
1739 static const uint16_t AtomicOpcTbl[AtomicOpcEnd][AtomicSzEnd] = {
1740   {
1741     X86::LOCK_ADD8mi,
1742     X86::LOCK_ADD8mr,
1743     X86::LOCK_ADD16mi8,
1744     X86::LOCK_ADD16mi,
1745     X86::LOCK_ADD16mr,
1746     X86::LOCK_ADD32mi8,
1747     X86::LOCK_ADD32mi,
1748     X86::LOCK_ADD32mr,
1749     X86::LOCK_ADD64mi8,
1750     X86::LOCK_ADD64mi32,
1751     X86::LOCK_ADD64mr,
1752   },
1753   {
1754     X86::LOCK_SUB8mi,
1755     X86::LOCK_SUB8mr,
1756     X86::LOCK_SUB16mi8,
1757     X86::LOCK_SUB16mi,
1758     X86::LOCK_SUB16mr,
1759     X86::LOCK_SUB32mi8,
1760     X86::LOCK_SUB32mi,
1761     X86::LOCK_SUB32mr,
1762     X86::LOCK_SUB64mi8,
1763     X86::LOCK_SUB64mi32,
1764     X86::LOCK_SUB64mr,
1765   },
1766   {
1767     0,
1768     X86::LOCK_INC8m,
1769     0,
1770     0,
1771     X86::LOCK_INC16m,
1772     0,
1773     0,
1774     X86::LOCK_INC32m,
1775     0,
1776     0,
1777     X86::LOCK_INC64m,
1778   },
1779   {
1780     0,
1781     X86::LOCK_DEC8m,
1782     0,
1783     0,
1784     X86::LOCK_DEC16m,
1785     0,
1786     0,
1787     X86::LOCK_DEC32m,
1788     0,
1789     0,
1790     X86::LOCK_DEC64m,
1791   },
1792   {
1793     X86::LOCK_OR8mi,
1794     X86::LOCK_OR8mr,
1795     X86::LOCK_OR16mi8,
1796     X86::LOCK_OR16mi,
1797     X86::LOCK_OR16mr,
1798     X86::LOCK_OR32mi8,
1799     X86::LOCK_OR32mi,
1800     X86::LOCK_OR32mr,
1801     X86::LOCK_OR64mi8,
1802     X86::LOCK_OR64mi32,
1803     X86::LOCK_OR64mr,
1804   },
1805   {
1806     X86::LOCK_AND8mi,
1807     X86::LOCK_AND8mr,
1808     X86::LOCK_AND16mi8,
1809     X86::LOCK_AND16mi,
1810     X86::LOCK_AND16mr,
1811     X86::LOCK_AND32mi8,
1812     X86::LOCK_AND32mi,
1813     X86::LOCK_AND32mr,
1814     X86::LOCK_AND64mi8,
1815     X86::LOCK_AND64mi32,
1816     X86::LOCK_AND64mr,
1817   },
1818   {
1819     X86::LOCK_XOR8mi,
1820     X86::LOCK_XOR8mr,
1821     X86::LOCK_XOR16mi8,
1822     X86::LOCK_XOR16mi,
1823     X86::LOCK_XOR16mr,
1824     X86::LOCK_XOR32mi8,
1825     X86::LOCK_XOR32mi,
1826     X86::LOCK_XOR32mr,
1827     X86::LOCK_XOR64mi8,
1828     X86::LOCK_XOR64mi32,
1829     X86::LOCK_XOR64mr,
1830   }
1831 };
1832
1833 // Return the target constant operand for atomic-load-op and do simple
1834 // translations, such as from atomic-load-add to lock-sub. The return value is
1835 // one of the following 3 cases:
1836 // + target-constant, the operand could be supported as a target constant.
1837 // + empty, the operand is not needed any more with the new op selected.
1838 // + non-empty, otherwise.
1839 static SDValue getAtomicLoadArithTargetConstant(SelectionDAG *CurDAG,
1840                                                 SDLoc dl,
1841                                                 enum AtomicOpc &Op, MVT NVT,
1842                                                 SDValue Val,
1843                                                 const X86Subtarget *Subtarget) {
1844   if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Val)) {
1845     int64_t CNVal = CN->getSExtValue();
1846     // Quit if not 32-bit imm.
1847     if ((int32_t)CNVal != CNVal)
1848       return Val;
1849     // Quit if INT32_MIN: it would be negated as it is negative and overflow,
1850     // producing an immediate that does not fit in the 32 bits available for
1851     // an immediate operand to sub. However, it still fits in 32 bits for the
1852     // add (since it is not negated) so we can return target-constant.
1853     if (CNVal == INT32_MIN)
1854       return CurDAG->getTargetConstant(CNVal, dl, NVT);
1855     // For atomic-load-add, we could do some optimizations.
1856     if (Op == ADD) {
1857       // Translate to INC/DEC if ADD by 1 or -1.
1858       if (((CNVal == 1) || (CNVal == -1)) && !Subtarget->slowIncDec()) {
1859         Op = (CNVal == 1) ? INC : DEC;
1860         // No more constant operand after being translated into INC/DEC.
1861         return SDValue();
1862       }
1863       // Translate to SUB if ADD by negative value.
1864       if (CNVal < 0) {
1865         Op = SUB;
1866         CNVal = -CNVal;
1867       }
1868     }
1869     return CurDAG->getTargetConstant(CNVal, dl, NVT);
1870   }
1871
1872   // If the value operand is single-used, try to optimize it.
1873   if (Op == ADD && Val.hasOneUse()) {
1874     // Translate (atomic-load-add ptr (sub 0 x)) back to (lock-sub x).
1875     if (Val.getOpcode() == ISD::SUB && X86::isZeroNode(Val.getOperand(0))) {
1876       Op = SUB;
1877       return Val.getOperand(1);
1878     }
1879     // A special case for i16, which needs truncating as, in most cases, it's
1880     // promoted to i32. We will translate
1881     // (atomic-load-add (truncate (sub 0 x))) to (lock-sub (EXTRACT_SUBREG x))
1882     if (Val.getOpcode() == ISD::TRUNCATE && NVT == MVT::i16 &&
1883         Val.getOperand(0).getOpcode() == ISD::SUB &&
1884         X86::isZeroNode(Val.getOperand(0).getOperand(0))) {
1885       Op = SUB;
1886       Val = Val.getOperand(0);
1887       return CurDAG->getTargetExtractSubreg(X86::sub_16bit, dl, NVT,
1888                                             Val.getOperand(1));
1889     }
1890   }
1891
1892   return Val;
1893 }
1894
1895 SDNode *X86DAGToDAGISel::selectAtomicLoadArith(SDNode *Node, MVT NVT) {
1896   if (Node->hasAnyUseOfValue(0))
1897     return nullptr;
1898
1899   SDLoc dl(Node);
1900
1901   // Optimize common patterns for __sync_or_and_fetch and similar arith
1902   // operations where the result is not used. This allows us to use the "lock"
1903   // version of the arithmetic instruction.
1904   SDValue Chain = Node->getOperand(0);
1905   SDValue Ptr = Node->getOperand(1);
1906   SDValue Val = Node->getOperand(2);
1907   SDValue Base, Scale, Index, Disp, Segment;
1908   if (!selectAddr(Node, Ptr, Base, Scale, Index, Disp, Segment))
1909     return nullptr;
1910
1911   // Which index into the table.
1912   enum AtomicOpc Op;
1913   switch (Node->getOpcode()) {
1914     default:
1915       return nullptr;
1916     case ISD::ATOMIC_LOAD_OR:
1917       Op = OR;
1918       break;
1919     case ISD::ATOMIC_LOAD_AND:
1920       Op = AND;
1921       break;
1922     case ISD::ATOMIC_LOAD_XOR:
1923       Op = XOR;
1924       break;
1925     case ISD::ATOMIC_LOAD_ADD:
1926       Op = ADD;
1927       break;
1928   }
1929
1930   Val = getAtomicLoadArithTargetConstant(CurDAG, dl, Op, NVT, Val, Subtarget);
1931   bool isUnOp = !Val.getNode();
1932   bool isCN = Val.getNode() && (Val.getOpcode() == ISD::TargetConstant);
1933
1934   unsigned Opc = 0;
1935   switch (NVT.SimpleTy) {
1936     default: return nullptr;
1937     case MVT::i8:
1938       if (isCN)
1939         Opc = AtomicOpcTbl[Op][ConstantI8];
1940       else
1941         Opc = AtomicOpcTbl[Op][I8];
1942       break;
1943     case MVT::i16:
1944       if (isCN) {
1945         if (immSext8(Val.getNode()))
1946           Opc = AtomicOpcTbl[Op][SextConstantI16];
1947         else
1948           Opc = AtomicOpcTbl[Op][ConstantI16];
1949       } else
1950         Opc = AtomicOpcTbl[Op][I16];
1951       break;
1952     case MVT::i32:
1953       if (isCN) {
1954         if (immSext8(Val.getNode()))
1955           Opc = AtomicOpcTbl[Op][SextConstantI32];
1956         else
1957           Opc = AtomicOpcTbl[Op][ConstantI32];
1958       } else
1959         Opc = AtomicOpcTbl[Op][I32];
1960       break;
1961     case MVT::i64:
1962       if (isCN) {
1963         if (immSext8(Val.getNode()))
1964           Opc = AtomicOpcTbl[Op][SextConstantI64];
1965         else if (i64immSExt32(Val.getNode()))
1966           Opc = AtomicOpcTbl[Op][ConstantI64];
1967         else
1968           llvm_unreachable("True 64 bits constant in SelectAtomicLoadArith");
1969       } else
1970         Opc = AtomicOpcTbl[Op][I64];
1971       break;
1972   }
1973
1974   assert(Opc != 0 && "Invalid arith lock transform!");
1975
1976   // Building the new node.
1977   SDValue Ret;
1978   if (isUnOp) {
1979     SDValue Ops[] = { Base, Scale, Index, Disp, Segment, Chain };
1980     Ret = SDValue(CurDAG->getMachineNode(Opc, dl, MVT::Other, Ops), 0);
1981   } else {
1982     SDValue Ops[] = { Base, Scale, Index, Disp, Segment, Val, Chain };
1983     Ret = SDValue(CurDAG->getMachineNode(Opc, dl, MVT::Other, Ops), 0);
1984   }
1985
1986   // Copying the MachineMemOperand.
1987   MachineSDNode::mmo_iterator MemOp = MF->allocateMemRefsArray(1);
1988   MemOp[0] = cast<MemSDNode>(Node)->getMemOperand();
1989   cast<MachineSDNode>(Ret)->setMemRefs(MemOp, MemOp + 1);
1990
1991   // We need to have two outputs as that is what the original instruction had.
1992   // So we add a dummy, undefined output. This is safe as we checked first
1993   // that no-one uses our output anyway.
1994   SDValue Undef = SDValue(CurDAG->getMachineNode(TargetOpcode::IMPLICIT_DEF,
1995                                                  dl, NVT), 0);
1996   SDValue RetVals[] = { Undef, Ret };
1997   return CurDAG->getMergeValues(RetVals, dl).getNode();
1998 }
1999
2000 /// Test whether the given X86ISD::CMP node has any uses which require the SF
2001 /// or OF bits to be accurate.
2002 static bool hasNoSignedComparisonUses(SDNode *N) {
2003   // Examine each user of the node.
2004   for (SDNode::use_iterator UI = N->use_begin(),
2005          UE = N->use_end(); UI != UE; ++UI) {
2006     // Only examine CopyToReg uses.
2007     if (UI->getOpcode() != ISD::CopyToReg)
2008       return false;
2009     // Only examine CopyToReg uses that copy to EFLAGS.
2010     if (cast<RegisterSDNode>(UI->getOperand(1))->getReg() !=
2011           X86::EFLAGS)
2012       return false;
2013     // Examine each user of the CopyToReg use.
2014     for (SDNode::use_iterator FlagUI = UI->use_begin(),
2015            FlagUE = UI->use_end(); FlagUI != FlagUE; ++FlagUI) {
2016       // Only examine the Flag result.
2017       if (FlagUI.getUse().getResNo() != 1) continue;
2018       // Anything unusual: assume conservatively.
2019       if (!FlagUI->isMachineOpcode()) return false;
2020       // Examine the opcode of the user.
2021       switch (FlagUI->getMachineOpcode()) {
2022       // These comparisons don't treat the most significant bit specially.
2023       case X86::SETAr: case X86::SETAEr: case X86::SETBr: case X86::SETBEr:
2024       case X86::SETEr: case X86::SETNEr: case X86::SETPr: case X86::SETNPr:
2025       case X86::SETAm: case X86::SETAEm: case X86::SETBm: case X86::SETBEm:
2026       case X86::SETEm: case X86::SETNEm: case X86::SETPm: case X86::SETNPm:
2027       case X86::JA_1: case X86::JAE_1: case X86::JB_1: case X86::JBE_1:
2028       case X86::JE_1: case X86::JNE_1: case X86::JP_1: case X86::JNP_1:
2029       case X86::CMOVA16rr: case X86::CMOVA16rm:
2030       case X86::CMOVA32rr: case X86::CMOVA32rm:
2031       case X86::CMOVA64rr: case X86::CMOVA64rm:
2032       case X86::CMOVAE16rr: case X86::CMOVAE16rm:
2033       case X86::CMOVAE32rr: case X86::CMOVAE32rm:
2034       case X86::CMOVAE64rr: case X86::CMOVAE64rm:
2035       case X86::CMOVB16rr: case X86::CMOVB16rm:
2036       case X86::CMOVB32rr: case X86::CMOVB32rm:
2037       case X86::CMOVB64rr: case X86::CMOVB64rm:
2038       case X86::CMOVBE16rr: case X86::CMOVBE16rm:
2039       case X86::CMOVBE32rr: case X86::CMOVBE32rm:
2040       case X86::CMOVBE64rr: case X86::CMOVBE64rm:
2041       case X86::CMOVE16rr: case X86::CMOVE16rm:
2042       case X86::CMOVE32rr: case X86::CMOVE32rm:
2043       case X86::CMOVE64rr: case X86::CMOVE64rm:
2044       case X86::CMOVNE16rr: case X86::CMOVNE16rm:
2045       case X86::CMOVNE32rr: case X86::CMOVNE32rm:
2046       case X86::CMOVNE64rr: case X86::CMOVNE64rm:
2047       case X86::CMOVNP16rr: case X86::CMOVNP16rm:
2048       case X86::CMOVNP32rr: case X86::CMOVNP32rm:
2049       case X86::CMOVNP64rr: case X86::CMOVNP64rm:
2050       case X86::CMOVP16rr: case X86::CMOVP16rm:
2051       case X86::CMOVP32rr: case X86::CMOVP32rm:
2052       case X86::CMOVP64rr: case X86::CMOVP64rm:
2053         continue;
2054       // Anything else: assume conservatively.
2055       default: return false;
2056       }
2057     }
2058   }
2059   return true;
2060 }
2061
2062 /// Check whether or not the chain ending in StoreNode is suitable for doing
2063 /// the {load; increment or decrement; store} to modify transformation.
2064 static bool isLoadIncOrDecStore(StoreSDNode *StoreNode, unsigned Opc,
2065                                 SDValue StoredVal, SelectionDAG *CurDAG,
2066                                 LoadSDNode* &LoadNode, SDValue &InputChain) {
2067
2068   // is the value stored the result of a DEC or INC?
2069   if (!(Opc == X86ISD::DEC || Opc == X86ISD::INC)) return false;
2070
2071   // is the stored value result 0 of the load?
2072   if (StoredVal.getResNo() != 0) return false;
2073
2074   // are there other uses of the loaded value than the inc or dec?
2075   if (!StoredVal.getNode()->hasNUsesOfValue(1, 0)) return false;
2076
2077   // is the store non-extending and non-indexed?
2078   if (!ISD::isNormalStore(StoreNode) || StoreNode->isNonTemporal())
2079     return false;
2080
2081   SDValue Load = StoredVal->getOperand(0);
2082   // Is the stored value a non-extending and non-indexed load?
2083   if (!ISD::isNormalLoad(Load.getNode())) return false;
2084
2085   // Return LoadNode by reference.
2086   LoadNode = cast<LoadSDNode>(Load);
2087   // is the size of the value one that we can handle? (i.e. 64, 32, 16, or 8)
2088   EVT LdVT = LoadNode->getMemoryVT();
2089   if (LdVT != MVT::i64 && LdVT != MVT::i32 && LdVT != MVT::i16 &&
2090       LdVT != MVT::i8)
2091     return false;
2092
2093   // Is store the only read of the loaded value?
2094   if (!Load.hasOneUse())
2095     return false;
2096
2097   // Is the address of the store the same as the load?
2098   if (LoadNode->getBasePtr() != StoreNode->getBasePtr() ||
2099       LoadNode->getOffset() != StoreNode->getOffset())
2100     return false;
2101
2102   // Check if the chain is produced by the load or is a TokenFactor with
2103   // the load output chain as an operand. Return InputChain by reference.
2104   SDValue Chain = StoreNode->getChain();
2105
2106   bool ChainCheck = false;
2107   if (Chain == Load.getValue(1)) {
2108     ChainCheck = true;
2109     InputChain = LoadNode->getChain();
2110   } else if (Chain.getOpcode() == ISD::TokenFactor) {
2111     SmallVector<SDValue, 4> ChainOps;
2112     for (unsigned i = 0, e = Chain.getNumOperands(); i != e; ++i) {
2113       SDValue Op = Chain.getOperand(i);
2114       if (Op == Load.getValue(1)) {
2115         ChainCheck = true;
2116         continue;
2117       }
2118
2119       // Make sure using Op as part of the chain would not cause a cycle here.
2120       // In theory, we could check whether the chain node is a predecessor of
2121       // the load. But that can be very expensive. Instead visit the uses and
2122       // make sure they all have smaller node id than the load.
2123       int LoadId = LoadNode->getNodeId();
2124       for (SDNode::use_iterator UI = Op.getNode()->use_begin(),
2125              UE = UI->use_end(); UI != UE; ++UI) {
2126         if (UI.getUse().getResNo() != 0)
2127           continue;
2128         if (UI->getNodeId() > LoadId)
2129           return false;
2130       }
2131
2132       ChainOps.push_back(Op);
2133     }
2134
2135     if (ChainCheck)
2136       // Make a new TokenFactor with all the other input chains except
2137       // for the load.
2138       InputChain = CurDAG->getNode(ISD::TokenFactor, SDLoc(Chain),
2139                                    MVT::Other, ChainOps);
2140   }
2141   if (!ChainCheck)
2142     return false;
2143
2144   return true;
2145 }
2146
2147 /// Get the appropriate X86 opcode for an in-memory increment or decrement.
2148 /// Opc should be X86ISD::DEC or X86ISD::INC.
2149 static unsigned getFusedLdStOpcode(EVT &LdVT, unsigned Opc) {
2150   if (Opc == X86ISD::DEC) {
2151     if (LdVT == MVT::i64) return X86::DEC64m;
2152     if (LdVT == MVT::i32) return X86::DEC32m;
2153     if (LdVT == MVT::i16) return X86::DEC16m;
2154     if (LdVT == MVT::i8)  return X86::DEC8m;
2155   } else {
2156     assert(Opc == X86ISD::INC && "unrecognized opcode");
2157     if (LdVT == MVT::i64) return X86::INC64m;
2158     if (LdVT == MVT::i32) return X86::INC32m;
2159     if (LdVT == MVT::i16) return X86::INC16m;
2160     if (LdVT == MVT::i8)  return X86::INC8m;
2161   }
2162   llvm_unreachable("unrecognized size for LdVT");
2163 }
2164
2165 /// Customized ISel for GATHER operations.
2166 SDNode *X86DAGToDAGISel::selectGather(SDNode *Node, unsigned Opc) {
2167   // Operands of Gather: VSrc, Base, VIdx, VMask, Scale
2168   SDValue Chain = Node->getOperand(0);
2169   SDValue VSrc = Node->getOperand(2);
2170   SDValue Base = Node->getOperand(3);
2171   SDValue VIdx = Node->getOperand(4);
2172   SDValue VMask = Node->getOperand(5);
2173   ConstantSDNode *Scale = dyn_cast<ConstantSDNode>(Node->getOperand(6));
2174   if (!Scale)
2175     return nullptr;
2176
2177   SDVTList VTs = CurDAG->getVTList(VSrc.getValueType(), VSrc.getValueType(),
2178                                    MVT::Other);
2179
2180   SDLoc DL(Node);
2181
2182   // Memory Operands: Base, Scale, Index, Disp, Segment
2183   SDValue Disp = CurDAG->getTargetConstant(0, DL, MVT::i32);
2184   SDValue Segment = CurDAG->getRegister(0, MVT::i32);
2185   const SDValue Ops[] = { VSrc, Base, getI8Imm(Scale->getSExtValue(), DL), VIdx,
2186                           Disp, Segment, VMask, Chain};
2187   SDNode *ResNode = CurDAG->getMachineNode(Opc, DL, VTs, Ops);
2188   // Node has 2 outputs: VDst and MVT::Other.
2189   // ResNode has 3 outputs: VDst, VMask_wb, and MVT::Other.
2190   // We replace VDst of Node with VDst of ResNode, and Other of Node with Other
2191   // of ResNode.
2192   ReplaceUses(SDValue(Node, 0), SDValue(ResNode, 0));
2193   ReplaceUses(SDValue(Node, 1), SDValue(ResNode, 2));
2194   return ResNode;
2195 }
2196
2197 SDNode *X86DAGToDAGISel::Select(SDNode *Node) {
2198   MVT NVT = Node->getSimpleValueType(0);
2199   unsigned Opc, MOpc;
2200   unsigned Opcode = Node->getOpcode();
2201   SDLoc dl(Node);
2202
2203   DEBUG(dbgs() << "Selecting: "; Node->dump(CurDAG); dbgs() << '\n');
2204
2205   if (Node->isMachineOpcode()) {
2206     DEBUG(dbgs() << "== ";  Node->dump(CurDAG); dbgs() << '\n');
2207     Node->setNodeId(-1);
2208     return nullptr;   // Already selected.
2209   }
2210
2211   switch (Opcode) {
2212   default: break;
2213   case ISD::BRIND: {
2214     if (Subtarget->isTargetNaCl())
2215       // NaCl has its own pass where jmp %r32 are converted to jmp %r64. We
2216       // leave the instruction alone.
2217       break;
2218     if (Subtarget->isTarget64BitILP32()) {
2219       // Converts a 32-bit register to a 64-bit, zero-extended version of
2220       // it. This is needed because x86-64 can do many things, but jmp %r32
2221       // ain't one of them.
2222       const SDValue &Target = Node->getOperand(1);
2223       assert(Target.getSimpleValueType() == llvm::MVT::i32);
2224       SDValue ZextTarget = CurDAG->getZExtOrTrunc(Target, dl, EVT(MVT::i64));
2225       SDValue Brind = CurDAG->getNode(ISD::BRIND, dl, MVT::Other,
2226                                       Node->getOperand(0), ZextTarget);
2227       ReplaceUses(SDValue(Node, 0), Brind);
2228       SelectCode(ZextTarget.getNode());
2229       SelectCode(Brind.getNode());
2230       return nullptr;
2231     }
2232     break;
2233   }
2234   case ISD::INTRINSIC_W_CHAIN: {
2235     unsigned IntNo = cast<ConstantSDNode>(Node->getOperand(1))->getZExtValue();
2236     switch (IntNo) {
2237     default: break;
2238     case Intrinsic::x86_avx2_gather_d_pd:
2239     case Intrinsic::x86_avx2_gather_d_pd_256:
2240     case Intrinsic::x86_avx2_gather_q_pd:
2241     case Intrinsic::x86_avx2_gather_q_pd_256:
2242     case Intrinsic::x86_avx2_gather_d_ps:
2243     case Intrinsic::x86_avx2_gather_d_ps_256:
2244     case Intrinsic::x86_avx2_gather_q_ps:
2245     case Intrinsic::x86_avx2_gather_q_ps_256:
2246     case Intrinsic::x86_avx2_gather_d_q:
2247     case Intrinsic::x86_avx2_gather_d_q_256:
2248     case Intrinsic::x86_avx2_gather_q_q:
2249     case Intrinsic::x86_avx2_gather_q_q_256:
2250     case Intrinsic::x86_avx2_gather_d_d:
2251     case Intrinsic::x86_avx2_gather_d_d_256:
2252     case Intrinsic::x86_avx2_gather_q_d:
2253     case Intrinsic::x86_avx2_gather_q_d_256: {
2254       if (!Subtarget->hasAVX2())
2255         break;
2256       unsigned Opc;
2257       switch (IntNo) {
2258       default: llvm_unreachable("Impossible intrinsic");
2259       case Intrinsic::x86_avx2_gather_d_pd:     Opc = X86::VGATHERDPDrm;  break;
2260       case Intrinsic::x86_avx2_gather_d_pd_256: Opc = X86::VGATHERDPDYrm; break;
2261       case Intrinsic::x86_avx2_gather_q_pd:     Opc = X86::VGATHERQPDrm;  break;
2262       case Intrinsic::x86_avx2_gather_q_pd_256: Opc = X86::VGATHERQPDYrm; break;
2263       case Intrinsic::x86_avx2_gather_d_ps:     Opc = X86::VGATHERDPSrm;  break;
2264       case Intrinsic::x86_avx2_gather_d_ps_256: Opc = X86::VGATHERDPSYrm; break;
2265       case Intrinsic::x86_avx2_gather_q_ps:     Opc = X86::VGATHERQPSrm;  break;
2266       case Intrinsic::x86_avx2_gather_q_ps_256: Opc = X86::VGATHERQPSYrm; break;
2267       case Intrinsic::x86_avx2_gather_d_q:      Opc = X86::VPGATHERDQrm;  break;
2268       case Intrinsic::x86_avx2_gather_d_q_256:  Opc = X86::VPGATHERDQYrm; break;
2269       case Intrinsic::x86_avx2_gather_q_q:      Opc = X86::VPGATHERQQrm;  break;
2270       case Intrinsic::x86_avx2_gather_q_q_256:  Opc = X86::VPGATHERQQYrm; break;
2271       case Intrinsic::x86_avx2_gather_d_d:      Opc = X86::VPGATHERDDrm;  break;
2272       case Intrinsic::x86_avx2_gather_d_d_256:  Opc = X86::VPGATHERDDYrm; break;
2273       case Intrinsic::x86_avx2_gather_q_d:      Opc = X86::VPGATHERQDrm;  break;
2274       case Intrinsic::x86_avx2_gather_q_d_256:  Opc = X86::VPGATHERQDYrm; break;
2275       }
2276       SDNode *RetVal = selectGather(Node, Opc);
2277       if (RetVal)
2278         // We already called ReplaceUses inside SelectGather.
2279         return nullptr;
2280       break;
2281     }
2282     }
2283     break;
2284   }
2285   case X86ISD::GlobalBaseReg:
2286     return getGlobalBaseReg();
2287
2288   case X86ISD::SHRUNKBLEND: {
2289     // SHRUNKBLEND selects like a regular VSELECT.
2290     SDValue VSelect = CurDAG->getNode(
2291         ISD::VSELECT, SDLoc(Node), Node->getValueType(0), Node->getOperand(0),
2292         Node->getOperand(1), Node->getOperand(2));
2293     ReplaceUses(SDValue(Node, 0), VSelect);
2294     SelectCode(VSelect.getNode());
2295     // We already called ReplaceUses.
2296     return nullptr;
2297   }
2298
2299   case ISD::ATOMIC_LOAD_XOR:
2300   case ISD::ATOMIC_LOAD_AND:
2301   case ISD::ATOMIC_LOAD_OR:
2302   case ISD::ATOMIC_LOAD_ADD: {
2303     SDNode *RetVal = selectAtomicLoadArith(Node, NVT);
2304     if (RetVal)
2305       return RetVal;
2306     break;
2307   }
2308   case ISD::AND:
2309   case ISD::OR:
2310   case ISD::XOR: {
2311     // For operations of the form (x << C1) op C2, check if we can use a smaller
2312     // encoding for C2 by transforming it into (x op (C2>>C1)) << C1.
2313     SDValue N0 = Node->getOperand(0);
2314     SDValue N1 = Node->getOperand(1);
2315
2316     if (N0->getOpcode() != ISD::SHL || !N0->hasOneUse())
2317       break;
2318
2319     // i8 is unshrinkable, i16 should be promoted to i32.
2320     if (NVT != MVT::i32 && NVT != MVT::i64)
2321       break;
2322
2323     ConstantSDNode *Cst = dyn_cast<ConstantSDNode>(N1);
2324     ConstantSDNode *ShlCst = dyn_cast<ConstantSDNode>(N0->getOperand(1));
2325     if (!Cst || !ShlCst)
2326       break;
2327
2328     int64_t Val = Cst->getSExtValue();
2329     uint64_t ShlVal = ShlCst->getZExtValue();
2330
2331     // Make sure that we don't change the operation by removing bits.
2332     // This only matters for OR and XOR, AND is unaffected.
2333     uint64_t RemovedBitsMask = (1ULL << ShlVal) - 1;
2334     if (Opcode != ISD::AND && (Val & RemovedBitsMask) != 0)
2335       break;
2336
2337     unsigned ShlOp, AddOp, Op;
2338     MVT CstVT = NVT;
2339
2340     // Check the minimum bitwidth for the new constant.
2341     // TODO: AND32ri is the same as AND64ri32 with zext imm.
2342     // TODO: MOV32ri+OR64r is cheaper than MOV64ri64+OR64rr
2343     // TODO: Using 16 and 8 bit operations is also possible for or32 & xor32.
2344     if (!isInt<8>(Val) && isInt<8>(Val >> ShlVal))
2345       CstVT = MVT::i8;
2346     else if (!isInt<32>(Val) && isInt<32>(Val >> ShlVal))
2347       CstVT = MVT::i32;
2348
2349     // Bail if there is no smaller encoding.
2350     if (NVT == CstVT)
2351       break;
2352
2353     switch (NVT.SimpleTy) {
2354     default: llvm_unreachable("Unsupported VT!");
2355     case MVT::i32:
2356       assert(CstVT == MVT::i8);
2357       ShlOp = X86::SHL32ri;
2358       AddOp = X86::ADD32rr;
2359
2360       switch (Opcode) {
2361       default: llvm_unreachable("Impossible opcode");
2362       case ISD::AND: Op = X86::AND32ri8; break;
2363       case ISD::OR:  Op =  X86::OR32ri8; break;
2364       case ISD::XOR: Op = X86::XOR32ri8; break;
2365       }
2366       break;
2367     case MVT::i64:
2368       assert(CstVT == MVT::i8 || CstVT == MVT::i32);
2369       ShlOp = X86::SHL64ri;
2370       AddOp = X86::ADD64rr;
2371
2372       switch (Opcode) {
2373       default: llvm_unreachable("Impossible opcode");
2374       case ISD::AND: Op = CstVT==MVT::i8? X86::AND64ri8 : X86::AND64ri32; break;
2375       case ISD::OR:  Op = CstVT==MVT::i8?  X86::OR64ri8 :  X86::OR64ri32; break;
2376       case ISD::XOR: Op = CstVT==MVT::i8? X86::XOR64ri8 : X86::XOR64ri32; break;
2377       }
2378       break;
2379     }
2380
2381     // Emit the smaller op and the shift.
2382     SDValue NewCst = CurDAG->getTargetConstant(Val >> ShlVal, dl, CstVT);
2383     SDNode *New = CurDAG->getMachineNode(Op, dl, NVT, N0->getOperand(0),NewCst);
2384     if (ShlVal == 1)
2385       return CurDAG->SelectNodeTo(Node, AddOp, NVT, SDValue(New, 0),
2386                                   SDValue(New, 0));
2387     return CurDAG->SelectNodeTo(Node, ShlOp, NVT, SDValue(New, 0),
2388                                 getI8Imm(ShlVal, dl));
2389   }
2390   case X86ISD::UMUL8:
2391   case X86ISD::SMUL8: {
2392     SDValue N0 = Node->getOperand(0);
2393     SDValue N1 = Node->getOperand(1);
2394
2395     Opc = (Opcode == X86ISD::SMUL8 ? X86::IMUL8r : X86::MUL8r);
2396
2397     SDValue InFlag = CurDAG->getCopyToReg(CurDAG->getEntryNode(), dl, X86::AL,
2398                                           N0, SDValue()).getValue(1);
2399
2400     SDVTList VTs = CurDAG->getVTList(NVT, MVT::i32);
2401     SDValue Ops[] = {N1, InFlag};
2402     SDNode *CNode = CurDAG->getMachineNode(Opc, dl, VTs, Ops);
2403
2404     ReplaceUses(SDValue(Node, 0), SDValue(CNode, 0));
2405     ReplaceUses(SDValue(Node, 1), SDValue(CNode, 1));
2406     return nullptr;
2407   }
2408
2409   case X86ISD::UMUL: {
2410     SDValue N0 = Node->getOperand(0);
2411     SDValue N1 = Node->getOperand(1);
2412
2413     unsigned LoReg;
2414     switch (NVT.SimpleTy) {
2415     default: llvm_unreachable("Unsupported VT!");
2416     case MVT::i8:  LoReg = X86::AL;  Opc = X86::MUL8r; break;
2417     case MVT::i16: LoReg = X86::AX;  Opc = X86::MUL16r; break;
2418     case MVT::i32: LoReg = X86::EAX; Opc = X86::MUL32r; break;
2419     case MVT::i64: LoReg = X86::RAX; Opc = X86::MUL64r; break;
2420     }
2421
2422     SDValue InFlag = CurDAG->getCopyToReg(CurDAG->getEntryNode(), dl, LoReg,
2423                                           N0, SDValue()).getValue(1);
2424
2425     SDVTList VTs = CurDAG->getVTList(NVT, NVT, MVT::i32);
2426     SDValue Ops[] = {N1, InFlag};
2427     SDNode *CNode = CurDAG->getMachineNode(Opc, dl, VTs, Ops);
2428
2429     ReplaceUses(SDValue(Node, 0), SDValue(CNode, 0));
2430     ReplaceUses(SDValue(Node, 1), SDValue(CNode, 1));
2431     ReplaceUses(SDValue(Node, 2), SDValue(CNode, 2));
2432     return nullptr;
2433   }
2434
2435   case ISD::SMUL_LOHI:
2436   case ISD::UMUL_LOHI: {
2437     SDValue N0 = Node->getOperand(0);
2438     SDValue N1 = Node->getOperand(1);
2439
2440     bool isSigned = Opcode == ISD::SMUL_LOHI;
2441     bool hasBMI2 = Subtarget->hasBMI2();
2442     if (!isSigned) {
2443       switch (NVT.SimpleTy) {
2444       default: llvm_unreachable("Unsupported VT!");
2445       case MVT::i8:  Opc = X86::MUL8r;  MOpc = X86::MUL8m;  break;
2446       case MVT::i16: Opc = X86::MUL16r; MOpc = X86::MUL16m; break;
2447       case MVT::i32: Opc = hasBMI2 ? X86::MULX32rr : X86::MUL32r;
2448                      MOpc = hasBMI2 ? X86::MULX32rm : X86::MUL32m; break;
2449       case MVT::i64: Opc = hasBMI2 ? X86::MULX64rr : X86::MUL64r;
2450                      MOpc = hasBMI2 ? X86::MULX64rm : X86::MUL64m; break;
2451       }
2452     } else {
2453       switch (NVT.SimpleTy) {
2454       default: llvm_unreachable("Unsupported VT!");
2455       case MVT::i8:  Opc = X86::IMUL8r;  MOpc = X86::IMUL8m;  break;
2456       case MVT::i16: Opc = X86::IMUL16r; MOpc = X86::IMUL16m; break;
2457       case MVT::i32: Opc = X86::IMUL32r; MOpc = X86::IMUL32m; break;
2458       case MVT::i64: Opc = X86::IMUL64r; MOpc = X86::IMUL64m; break;
2459       }
2460     }
2461
2462     unsigned SrcReg, LoReg, HiReg;
2463     switch (Opc) {
2464     default: llvm_unreachable("Unknown MUL opcode!");
2465     case X86::IMUL8r:
2466     case X86::MUL8r:
2467       SrcReg = LoReg = X86::AL; HiReg = X86::AH;
2468       break;
2469     case X86::IMUL16r:
2470     case X86::MUL16r:
2471       SrcReg = LoReg = X86::AX; HiReg = X86::DX;
2472       break;
2473     case X86::IMUL32r:
2474     case X86::MUL32r:
2475       SrcReg = LoReg = X86::EAX; HiReg = X86::EDX;
2476       break;
2477     case X86::IMUL64r:
2478     case X86::MUL64r:
2479       SrcReg = LoReg = X86::RAX; HiReg = X86::RDX;
2480       break;
2481     case X86::MULX32rr:
2482       SrcReg = X86::EDX; LoReg = HiReg = 0;
2483       break;
2484     case X86::MULX64rr:
2485       SrcReg = X86::RDX; LoReg = HiReg = 0;
2486       break;
2487     }
2488
2489     SDValue Tmp0, Tmp1, Tmp2, Tmp3, Tmp4;
2490     bool foldedLoad = tryFoldLoad(Node, N1, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4);
2491     // Multiply is commmutative.
2492     if (!foldedLoad) {
2493       foldedLoad = tryFoldLoad(Node, N0, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4);
2494       if (foldedLoad)
2495         std::swap(N0, N1);
2496     }
2497
2498     SDValue InFlag = CurDAG->getCopyToReg(CurDAG->getEntryNode(), dl, SrcReg,
2499                                           N0, SDValue()).getValue(1);
2500     SDValue ResHi, ResLo;
2501
2502     if (foldedLoad) {
2503       SDValue Chain;
2504       SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, N1.getOperand(0),
2505                         InFlag };
2506       if (MOpc == X86::MULX32rm || MOpc == X86::MULX64rm) {
2507         SDVTList VTs = CurDAG->getVTList(NVT, NVT, MVT::Other, MVT::Glue);
2508         SDNode *CNode = CurDAG->getMachineNode(MOpc, dl, VTs, Ops);
2509         ResHi = SDValue(CNode, 0);
2510         ResLo = SDValue(CNode, 1);
2511         Chain = SDValue(CNode, 2);
2512         InFlag = SDValue(CNode, 3);
2513       } else {
2514         SDVTList VTs = CurDAG->getVTList(MVT::Other, MVT::Glue);
2515         SDNode *CNode = CurDAG->getMachineNode(MOpc, dl, VTs, Ops);
2516         Chain = SDValue(CNode, 0);
2517         InFlag = SDValue(CNode, 1);
2518       }
2519
2520       // Update the chain.
2521       ReplaceUses(N1.getValue(1), Chain);
2522     } else {
2523       SDValue Ops[] = { N1, InFlag };
2524       if (Opc == X86::MULX32rr || Opc == X86::MULX64rr) {
2525         SDVTList VTs = CurDAG->getVTList(NVT, NVT, MVT::Glue);
2526         SDNode *CNode = CurDAG->getMachineNode(Opc, dl, VTs, Ops);
2527         ResHi = SDValue(CNode, 0);
2528         ResLo = SDValue(CNode, 1);
2529         InFlag = SDValue(CNode, 2);
2530       } else {
2531         SDVTList VTs = CurDAG->getVTList(MVT::Glue);
2532         SDNode *CNode = CurDAG->getMachineNode(Opc, dl, VTs, Ops);
2533         InFlag = SDValue(CNode, 0);
2534       }
2535     }
2536
2537     // Prevent use of AH in a REX instruction by referencing AX instead.
2538     if (HiReg == X86::AH && Subtarget->is64Bit() &&
2539         !SDValue(Node, 1).use_empty()) {
2540       SDValue Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl,
2541                                               X86::AX, MVT::i16, InFlag);
2542       InFlag = Result.getValue(2);
2543       // Get the low part if needed. Don't use getCopyFromReg for aliasing
2544       // registers.
2545       if (!SDValue(Node, 0).use_empty())
2546         ReplaceUses(SDValue(Node, 1),
2547           CurDAG->getTargetExtractSubreg(X86::sub_8bit, dl, MVT::i8, Result));
2548
2549       // Shift AX down 8 bits.
2550       Result = SDValue(CurDAG->getMachineNode(X86::SHR16ri, dl, MVT::i16,
2551                                               Result,
2552                                      CurDAG->getTargetConstant(8, dl, MVT::i8)),
2553                        0);
2554       // Then truncate it down to i8.
2555       ReplaceUses(SDValue(Node, 1),
2556         CurDAG->getTargetExtractSubreg(X86::sub_8bit, dl, MVT::i8, Result));
2557     }
2558     // Copy the low half of the result, if it is needed.
2559     if (!SDValue(Node, 0).use_empty()) {
2560       if (!ResLo.getNode()) {
2561         assert(LoReg && "Register for low half is not defined!");
2562         ResLo = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl, LoReg, NVT,
2563                                        InFlag);
2564         InFlag = ResLo.getValue(2);
2565       }
2566       ReplaceUses(SDValue(Node, 0), ResLo);
2567       DEBUG(dbgs() << "=> "; ResLo.getNode()->dump(CurDAG); dbgs() << '\n');
2568     }
2569     // Copy the high half of the result, if it is needed.
2570     if (!SDValue(Node, 1).use_empty()) {
2571       if (!ResHi.getNode()) {
2572         assert(HiReg && "Register for high half is not defined!");
2573         ResHi = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl, HiReg, NVT,
2574                                        InFlag);
2575         InFlag = ResHi.getValue(2);
2576       }
2577       ReplaceUses(SDValue(Node, 1), ResHi);
2578       DEBUG(dbgs() << "=> "; ResHi.getNode()->dump(CurDAG); dbgs() << '\n');
2579     }
2580
2581     return nullptr;
2582   }
2583
2584   case ISD::SDIVREM:
2585   case ISD::UDIVREM:
2586   case X86ISD::SDIVREM8_SEXT_HREG:
2587   case X86ISD::UDIVREM8_ZEXT_HREG: {
2588     SDValue N0 = Node->getOperand(0);
2589     SDValue N1 = Node->getOperand(1);
2590
2591     bool isSigned = (Opcode == ISD::SDIVREM ||
2592                      Opcode == X86ISD::SDIVREM8_SEXT_HREG);
2593     if (!isSigned) {
2594       switch (NVT.SimpleTy) {
2595       default: llvm_unreachable("Unsupported VT!");
2596       case MVT::i8:  Opc = X86::DIV8r;  MOpc = X86::DIV8m;  break;
2597       case MVT::i16: Opc = X86::DIV16r; MOpc = X86::DIV16m; break;
2598       case MVT::i32: Opc = X86::DIV32r; MOpc = X86::DIV32m; break;
2599       case MVT::i64: Opc = X86::DIV64r; MOpc = X86::DIV64m; break;
2600       }
2601     } else {
2602       switch (NVT.SimpleTy) {
2603       default: llvm_unreachable("Unsupported VT!");
2604       case MVT::i8:  Opc = X86::IDIV8r;  MOpc = X86::IDIV8m;  break;
2605       case MVT::i16: Opc = X86::IDIV16r; MOpc = X86::IDIV16m; break;
2606       case MVT::i32: Opc = X86::IDIV32r; MOpc = X86::IDIV32m; break;
2607       case MVT::i64: Opc = X86::IDIV64r; MOpc = X86::IDIV64m; break;
2608       }
2609     }
2610
2611     unsigned LoReg, HiReg, ClrReg;
2612     unsigned SExtOpcode;
2613     switch (NVT.SimpleTy) {
2614     default: llvm_unreachable("Unsupported VT!");
2615     case MVT::i8:
2616       LoReg = X86::AL;  ClrReg = HiReg = X86::AH;
2617       SExtOpcode = X86::CBW;
2618       break;
2619     case MVT::i16:
2620       LoReg = X86::AX;  HiReg = X86::DX;
2621       ClrReg = X86::DX;
2622       SExtOpcode = X86::CWD;
2623       break;
2624     case MVT::i32:
2625       LoReg = X86::EAX; ClrReg = HiReg = X86::EDX;
2626       SExtOpcode = X86::CDQ;
2627       break;
2628     case MVT::i64:
2629       LoReg = X86::RAX; ClrReg = HiReg = X86::RDX;
2630       SExtOpcode = X86::CQO;
2631       break;
2632     }
2633
2634     SDValue Tmp0, Tmp1, Tmp2, Tmp3, Tmp4;
2635     bool foldedLoad = tryFoldLoad(Node, N1, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4);
2636     bool signBitIsZero = CurDAG->SignBitIsZero(N0);
2637
2638     SDValue InFlag;
2639     if (NVT == MVT::i8 && (!isSigned || signBitIsZero)) {
2640       // Special case for div8, just use a move with zero extension to AX to
2641       // clear the upper 8 bits (AH).
2642       SDValue Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, Move, Chain;
2643       if (tryFoldLoad(Node, N0, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4)) {
2644         SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, N0.getOperand(0) };
2645         Move =
2646           SDValue(CurDAG->getMachineNode(X86::MOVZX32rm8, dl, MVT::i32,
2647                                          MVT::Other, Ops), 0);
2648         Chain = Move.getValue(1);
2649         ReplaceUses(N0.getValue(1), Chain);
2650       } else {
2651         Move =
2652           SDValue(CurDAG->getMachineNode(X86::MOVZX32rr8, dl, MVT::i32, N0),0);
2653         Chain = CurDAG->getEntryNode();
2654       }
2655       Chain  = CurDAG->getCopyToReg(Chain, dl, X86::EAX, Move, SDValue());
2656       InFlag = Chain.getValue(1);
2657     } else {
2658       InFlag =
2659         CurDAG->getCopyToReg(CurDAG->getEntryNode(), dl,
2660                              LoReg, N0, SDValue()).getValue(1);
2661       if (isSigned && !signBitIsZero) {
2662         // Sign extend the low part into the high part.
2663         InFlag =
2664           SDValue(CurDAG->getMachineNode(SExtOpcode, dl, MVT::Glue, InFlag),0);
2665       } else {
2666         // Zero out the high part, effectively zero extending the input.
2667         SDValue ClrNode = SDValue(CurDAG->getMachineNode(X86::MOV32r0, dl, NVT), 0);
2668         switch (NVT.SimpleTy) {
2669         case MVT::i16:
2670           ClrNode =
2671               SDValue(CurDAG->getMachineNode(
2672                           TargetOpcode::EXTRACT_SUBREG, dl, MVT::i16, ClrNode,
2673                           CurDAG->getTargetConstant(X86::sub_16bit, dl,
2674                                                     MVT::i32)),
2675                       0);
2676           break;
2677         case MVT::i32:
2678           break;
2679         case MVT::i64:
2680           ClrNode =
2681               SDValue(CurDAG->getMachineNode(
2682                           TargetOpcode::SUBREG_TO_REG, dl, MVT::i64,
2683                           CurDAG->getTargetConstant(0, dl, MVT::i64), ClrNode,
2684                           CurDAG->getTargetConstant(X86::sub_32bit, dl,
2685                                                     MVT::i32)),
2686                       0);
2687           break;
2688         default:
2689           llvm_unreachable("Unexpected division source");
2690         }
2691
2692         InFlag = CurDAG->getCopyToReg(CurDAG->getEntryNode(), dl, ClrReg,
2693                                       ClrNode, InFlag).getValue(1);
2694       }
2695     }
2696
2697     if (foldedLoad) {
2698       SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, N1.getOperand(0),
2699                         InFlag };
2700       SDNode *CNode =
2701         CurDAG->getMachineNode(MOpc, dl, MVT::Other, MVT::Glue, Ops);
2702       InFlag = SDValue(CNode, 1);
2703       // Update the chain.
2704       ReplaceUses(N1.getValue(1), SDValue(CNode, 0));
2705     } else {
2706       InFlag =
2707         SDValue(CurDAG->getMachineNode(Opc, dl, MVT::Glue, N1, InFlag), 0);
2708     }
2709
2710     // Prevent use of AH in a REX instruction by explicitly copying it to
2711     // an ABCD_L register.
2712     //
2713     // The current assumption of the register allocator is that isel
2714     // won't generate explicit references to the GR8_ABCD_H registers. If
2715     // the allocator and/or the backend get enhanced to be more robust in
2716     // that regard, this can be, and should be, removed.
2717     if (HiReg == X86::AH && !SDValue(Node, 1).use_empty()) {
2718       SDValue AHCopy = CurDAG->getRegister(X86::AH, MVT::i8);
2719       unsigned AHExtOpcode =
2720           isSigned ? X86::MOVSX32_NOREXrr8 : X86::MOVZX32_NOREXrr8;
2721
2722       SDNode *RNode = CurDAG->getMachineNode(AHExtOpcode, dl, MVT::i32,
2723                                              MVT::Glue, AHCopy, InFlag);
2724       SDValue Result(RNode, 0);
2725       InFlag = SDValue(RNode, 1);
2726
2727       if (Opcode == X86ISD::UDIVREM8_ZEXT_HREG ||
2728           Opcode == X86ISD::SDIVREM8_SEXT_HREG) {
2729         if (Node->getValueType(1) == MVT::i64) {
2730           // It's not possible to directly movsx AH to a 64bit register, because
2731           // the latter needs the REX prefix, but the former can't have it.
2732           assert(Opcode != X86ISD::SDIVREM8_SEXT_HREG &&
2733                  "Unexpected i64 sext of h-register");
2734           Result =
2735               SDValue(CurDAG->getMachineNode(
2736                           TargetOpcode::SUBREG_TO_REG, dl, MVT::i64,
2737                           CurDAG->getTargetConstant(0, dl, MVT::i64), Result,
2738                           CurDAG->getTargetConstant(X86::sub_32bit, dl,
2739                                                     MVT::i32)),
2740                       0);
2741         }
2742       } else {
2743         Result =
2744             CurDAG->getTargetExtractSubreg(X86::sub_8bit, dl, MVT::i8, Result);
2745       }
2746       ReplaceUses(SDValue(Node, 1), Result);
2747       DEBUG(dbgs() << "=> "; Result.getNode()->dump(CurDAG); dbgs() << '\n');
2748     }
2749     // Copy the division (low) result, if it is needed.
2750     if (!SDValue(Node, 0).use_empty()) {
2751       SDValue Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl,
2752                                                 LoReg, NVT, InFlag);
2753       InFlag = Result.getValue(2);
2754       ReplaceUses(SDValue(Node, 0), Result);
2755       DEBUG(dbgs() << "=> "; Result.getNode()->dump(CurDAG); dbgs() << '\n');
2756     }
2757     // Copy the remainder (high) result, if it is needed.
2758     if (!SDValue(Node, 1).use_empty()) {
2759       SDValue Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl,
2760                                               HiReg, NVT, InFlag);
2761       InFlag = Result.getValue(2);
2762       ReplaceUses(SDValue(Node, 1), Result);
2763       DEBUG(dbgs() << "=> "; Result.getNode()->dump(CurDAG); dbgs() << '\n');
2764     }
2765     return nullptr;
2766   }
2767
2768   case X86ISD::CMP:
2769   case X86ISD::SUB: {
2770     // Sometimes a SUB is used to perform comparison.
2771     if (Opcode == X86ISD::SUB && Node->hasAnyUseOfValue(0))
2772       // This node is not a CMP.
2773       break;
2774     SDValue N0 = Node->getOperand(0);
2775     SDValue N1 = Node->getOperand(1);
2776
2777     if (N0.getOpcode() == ISD::TRUNCATE && N0.hasOneUse() &&
2778         hasNoSignedComparisonUses(Node))
2779       N0 = N0.getOperand(0);
2780
2781     // Look for (X86cmp (and $op, $imm), 0) and see if we can convert it to
2782     // use a smaller encoding.
2783     // Look past the truncate if CMP is the only use of it.
2784     if ((N0.getNode()->getOpcode() == ISD::AND ||
2785          (N0.getResNo() == 0 && N0.getNode()->getOpcode() == X86ISD::AND)) &&
2786         N0.getNode()->hasOneUse() &&
2787         N0.getValueType() != MVT::i8 &&
2788         X86::isZeroNode(N1)) {
2789       ConstantSDNode *C = dyn_cast<ConstantSDNode>(N0.getNode()->getOperand(1));
2790       if (!C) break;
2791
2792       // For example, convert "testl %eax, $8" to "testb %al, $8"
2793       if ((C->getZExtValue() & ~UINT64_C(0xff)) == 0 &&
2794           (!(C->getZExtValue() & 0x80) ||
2795            hasNoSignedComparisonUses(Node))) {
2796         SDValue Imm = CurDAG->getTargetConstant(C->getZExtValue(), dl, MVT::i8);
2797         SDValue Reg = N0.getNode()->getOperand(0);
2798
2799         // On x86-32, only the ABCD registers have 8-bit subregisters.
2800         if (!Subtarget->is64Bit()) {
2801           const TargetRegisterClass *TRC;
2802           switch (N0.getSimpleValueType().SimpleTy) {
2803           case MVT::i32: TRC = &X86::GR32_ABCDRegClass; break;
2804           case MVT::i16: TRC = &X86::GR16_ABCDRegClass; break;
2805           default: llvm_unreachable("Unsupported TEST operand type!");
2806           }
2807           SDValue RC = CurDAG->getTargetConstant(TRC->getID(), dl, MVT::i32);
2808           Reg = SDValue(CurDAG->getMachineNode(X86::COPY_TO_REGCLASS, dl,
2809                                                Reg.getValueType(), Reg, RC), 0);
2810         }
2811
2812         // Extract the l-register.
2813         SDValue Subreg = CurDAG->getTargetExtractSubreg(X86::sub_8bit, dl,
2814                                                         MVT::i8, Reg);
2815
2816         // Emit a testb.
2817         SDNode *NewNode = CurDAG->getMachineNode(X86::TEST8ri, dl, MVT::i32,
2818                                                  Subreg, Imm);
2819         // Replace SUB|CMP with TEST, since SUB has two outputs while TEST has
2820         // one, do not call ReplaceAllUsesWith.
2821         ReplaceUses(SDValue(Node, (Opcode == X86ISD::SUB ? 1 : 0)),
2822                     SDValue(NewNode, 0));
2823         return nullptr;
2824       }
2825
2826       // For example, "testl %eax, $2048" to "testb %ah, $8".
2827       if ((C->getZExtValue() & ~UINT64_C(0xff00)) == 0 &&
2828           (!(C->getZExtValue() & 0x8000) ||
2829            hasNoSignedComparisonUses(Node))) {
2830         // Shift the immediate right by 8 bits.
2831         SDValue ShiftedImm = CurDAG->getTargetConstant(C->getZExtValue() >> 8,
2832                                                        dl, MVT::i8);
2833         SDValue Reg = N0.getNode()->getOperand(0);
2834
2835         // Put the value in an ABCD register.
2836         const TargetRegisterClass *TRC;
2837         switch (N0.getSimpleValueType().SimpleTy) {
2838         case MVT::i64: TRC = &X86::GR64_ABCDRegClass; break;
2839         case MVT::i32: TRC = &X86::GR32_ABCDRegClass; break;
2840         case MVT::i16: TRC = &X86::GR16_ABCDRegClass; break;
2841         default: llvm_unreachable("Unsupported TEST operand type!");
2842         }
2843         SDValue RC = CurDAG->getTargetConstant(TRC->getID(), dl, MVT::i32);
2844         Reg = SDValue(CurDAG->getMachineNode(X86::COPY_TO_REGCLASS, dl,
2845                                              Reg.getValueType(), Reg, RC), 0);
2846
2847         // Extract the h-register.
2848         SDValue Subreg = CurDAG->getTargetExtractSubreg(X86::sub_8bit_hi, dl,
2849                                                         MVT::i8, Reg);
2850
2851         // Emit a testb.  The EXTRACT_SUBREG becomes a COPY that can only
2852         // target GR8_NOREX registers, so make sure the register class is
2853         // forced.
2854         SDNode *NewNode = CurDAG->getMachineNode(X86::TEST8ri_NOREX, dl,
2855                                                  MVT::i32, Subreg, ShiftedImm);
2856         // Replace SUB|CMP with TEST, since SUB has two outputs while TEST has
2857         // one, do not call ReplaceAllUsesWith.
2858         ReplaceUses(SDValue(Node, (Opcode == X86ISD::SUB ? 1 : 0)),
2859                     SDValue(NewNode, 0));
2860         return nullptr;
2861       }
2862
2863       // For example, "testl %eax, $32776" to "testw %ax, $32776".
2864       if ((C->getZExtValue() & ~UINT64_C(0xffff)) == 0 &&
2865           N0.getValueType() != MVT::i16 &&
2866           (!(C->getZExtValue() & 0x8000) ||
2867            hasNoSignedComparisonUses(Node))) {
2868         SDValue Imm = CurDAG->getTargetConstant(C->getZExtValue(), dl,
2869                                                 MVT::i16);
2870         SDValue Reg = N0.getNode()->getOperand(0);
2871
2872         // Extract the 16-bit subregister.
2873         SDValue Subreg = CurDAG->getTargetExtractSubreg(X86::sub_16bit, dl,
2874                                                         MVT::i16, Reg);
2875
2876         // Emit a testw.
2877         SDNode *NewNode = CurDAG->getMachineNode(X86::TEST16ri, dl, MVT::i32,
2878                                                  Subreg, Imm);
2879         // Replace SUB|CMP with TEST, since SUB has two outputs while TEST has
2880         // one, do not call ReplaceAllUsesWith.
2881         ReplaceUses(SDValue(Node, (Opcode == X86ISD::SUB ? 1 : 0)),
2882                     SDValue(NewNode, 0));
2883         return nullptr;
2884       }
2885
2886       // For example, "testq %rax, $268468232" to "testl %eax, $268468232".
2887       if ((C->getZExtValue() & ~UINT64_C(0xffffffff)) == 0 &&
2888           N0.getValueType() == MVT::i64 &&
2889           (!(C->getZExtValue() & 0x80000000) ||
2890            hasNoSignedComparisonUses(Node))) {
2891         SDValue Imm = CurDAG->getTargetConstant(C->getZExtValue(), dl,
2892                                                 MVT::i32);
2893         SDValue Reg = N0.getNode()->getOperand(0);
2894
2895         // Extract the 32-bit subregister.
2896         SDValue Subreg = CurDAG->getTargetExtractSubreg(X86::sub_32bit, dl,
2897                                                         MVT::i32, Reg);
2898
2899         // Emit a testl.
2900         SDNode *NewNode = CurDAG->getMachineNode(X86::TEST32ri, dl, MVT::i32,
2901                                                  Subreg, Imm);
2902         // Replace SUB|CMP with TEST, since SUB has two outputs while TEST has
2903         // one, do not call ReplaceAllUsesWith.
2904         ReplaceUses(SDValue(Node, (Opcode == X86ISD::SUB ? 1 : 0)),
2905                     SDValue(NewNode, 0));
2906         return nullptr;
2907       }
2908     }
2909     break;
2910   }
2911   case ISD::STORE: {
2912     // Change a chain of {load; incr or dec; store} of the same value into
2913     // a simple increment or decrement through memory of that value, if the
2914     // uses of the modified value and its address are suitable.
2915     // The DEC64m tablegen pattern is currently not able to match the case where
2916     // the EFLAGS on the original DEC are used. (This also applies to
2917     // {INC,DEC}X{64,32,16,8}.)
2918     // We'll need to improve tablegen to allow flags to be transferred from a
2919     // node in the pattern to the result node.  probably with a new keyword
2920     // for example, we have this
2921     // def DEC64m : RI<0xFF, MRM1m, (outs), (ins i64mem:$dst), "dec{q}\t$dst",
2922     //  [(store (add (loadi64 addr:$dst), -1), addr:$dst),
2923     //   (implicit EFLAGS)]>;
2924     // but maybe need something like this
2925     // def DEC64m : RI<0xFF, MRM1m, (outs), (ins i64mem:$dst), "dec{q}\t$dst",
2926     //  [(store (add (loadi64 addr:$dst), -1), addr:$dst),
2927     //   (transferrable EFLAGS)]>;
2928
2929     StoreSDNode *StoreNode = cast<StoreSDNode>(Node);
2930     SDValue StoredVal = StoreNode->getOperand(1);
2931     unsigned Opc = StoredVal->getOpcode();
2932
2933     LoadSDNode *LoadNode = nullptr;
2934     SDValue InputChain;
2935     if (!isLoadIncOrDecStore(StoreNode, Opc, StoredVal, CurDAG,
2936                              LoadNode, InputChain))
2937       break;
2938
2939     SDValue Base, Scale, Index, Disp, Segment;
2940     if (!selectAddr(LoadNode, LoadNode->getBasePtr(),
2941                     Base, Scale, Index, Disp, Segment))
2942       break;
2943
2944     MachineSDNode::mmo_iterator MemOp = MF->allocateMemRefsArray(2);
2945     MemOp[0] = StoreNode->getMemOperand();
2946     MemOp[1] = LoadNode->getMemOperand();
2947     const SDValue Ops[] = { Base, Scale, Index, Disp, Segment, InputChain };
2948     EVT LdVT = LoadNode->getMemoryVT();
2949     unsigned newOpc = getFusedLdStOpcode(LdVT, Opc);
2950     MachineSDNode *Result = CurDAG->getMachineNode(newOpc,
2951                                                    SDLoc(Node),
2952                                                    MVT::i32, MVT::Other, Ops);
2953     Result->setMemRefs(MemOp, MemOp + 2);
2954
2955     ReplaceUses(SDValue(StoreNode, 0), SDValue(Result, 1));
2956     ReplaceUses(SDValue(StoredVal.getNode(), 1), SDValue(Result, 0));
2957
2958     return Result;
2959   }
2960   }
2961
2962   SDNode *ResNode = SelectCode(Node);
2963
2964   DEBUG(dbgs() << "=> ";
2965         if (ResNode == nullptr || ResNode == Node)
2966           Node->dump(CurDAG);
2967         else
2968           ResNode->dump(CurDAG);
2969         dbgs() << '\n');
2970
2971   return ResNode;
2972 }
2973
2974 bool X86DAGToDAGISel::
2975 SelectInlineAsmMemoryOperand(const SDValue &Op, unsigned ConstraintID,
2976                              std::vector<SDValue> &OutOps) {
2977   SDValue Op0, Op1, Op2, Op3, Op4;
2978   switch (ConstraintID) {
2979   default:
2980     llvm_unreachable("Unexpected asm memory constraint");
2981   case InlineAsm::Constraint_i:
2982     // FIXME: It seems strange that 'i' is needed here since it's supposed to
2983     //        be an immediate and not a memory constraint.
2984     // Fallthrough.
2985   case InlineAsm::Constraint_o: // offsetable        ??
2986   case InlineAsm::Constraint_v: // not offsetable    ??
2987   case InlineAsm::Constraint_m: // memory
2988   case InlineAsm::Constraint_X:
2989     if (!selectAddr(nullptr, Op, Op0, Op1, Op2, Op3, Op4))
2990       return true;
2991     break;
2992   }
2993
2994   OutOps.push_back(Op0);
2995   OutOps.push_back(Op1);
2996   OutOps.push_back(Op2);
2997   OutOps.push_back(Op3);
2998   OutOps.push_back(Op4);
2999   return false;
3000 }
3001
3002 /// This pass converts a legalized DAG into a X86-specific DAG,
3003 /// ready for instruction scheduling.
3004 FunctionPass *llvm::createX86ISelDag(X86TargetMachine &TM,
3005                                      CodeGenOpt::Level OptLevel) {
3006   return new X86DAGToDAGISel(TM, OptLevel);
3007 }