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 "X86MachineFunctionInfo.h"
  17 #include "X86RegisterInfo.h"
  18 #include "X86Subtarget.h"
  19 #include "X86TargetMachine.h"
  20 #include "llvm/ADT/Statistic.h"
  21 #include "llvm/CodeGen/MachineFrameInfo.h"
  22 #include "llvm/CodeGen/MachineFunction.h"
  23 #include "llvm/CodeGen/SelectionDAGISel.h"
  24 #include "llvm/Config/llvm-config.h"
  25 #include "llvm/IR/ConstantRange.h"
  26 #include "llvm/IR/Function.h"
  27 #include "llvm/IR/Instructions.h"
  28 #include "llvm/IR/Intrinsics.h"
  29 #include "llvm/IR/Type.h"
  30 #include "llvm/Support/Debug.h"
  31 #include "llvm/Support/ErrorHandling.h"
  32 #include "llvm/Support/KnownBits.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(SelectionDAG *DAG = nullptr) {
 105       dbgs() << "X86ISelAddressMode " << this << '\n';
 106       dbgs() << "Base_Reg ";
 107       if (Base_Reg.getNode())
 108         Base_Reg.getNode()->dump(DAG);
 109       else
 110         dbgs() << "nul\n";
 111       if (BaseType == FrameIndexBase)
 112         dbgs() << " Base.FrameIndex " << Base_FrameIndex << '\n';
 113       dbgs() << " Scale " << Scale << '\n'
 114              << "IndexReg ";
 115       if (IndexReg.getNode())
 116         IndexReg.getNode()->dump(DAG);
 117       else
 118         dbgs() << "nul\n";
 119       dbgs() << " Disp " << Disp << '\n'
 120              << "GV ";
 121       if (GV)
 122         GV->dump();
 123       else
 124         dbgs() << "nul";
 125       dbgs() << " CP ";
 126       if (CP)
 127         CP->dump();
 128       else
 129         dbgs() << "nul";
 130       dbgs() << '\n'
 131              << "ES ";
 132       if (ES)
 133         dbgs() << ES;
 134       else
 135         dbgs() << "nul";
 136       dbgs() << " MCSym ";
 137       if (MCSym)
 138         dbgs() << MCSym;
 139       else
 140         dbgs() << "nul";
 141       dbgs() << " JT" << JT << " Align" << Align << '\n';
 142     }
 143 #endif
 144   };
 145 }
 146
 147 namespace {
 148   //===--------------------------------------------------------------------===//
 149   /// ISel - X86-specific code to select X86 machine instructions for
 150   /// SelectionDAG operations.
 151   ///
 152   class X86DAGToDAGISel final : public SelectionDAGISel {
 153     /// Keep a pointer to the X86Subtarget around so that we can
 154     /// make the right decision when generating code for different targets.
 155     const X86Subtarget *Subtarget;
 156
 157     /// If true, selector should try to optimize for code size instead of
 158     /// performance.
 159     bool OptForSize;
 160
 161     /// If true, selector should try to optimize for minimum code size.
 162     bool OptForMinSize;
 163
 164   public:
 165     explicit X86DAGToDAGISel(X86TargetMachine &tm, CodeGenOpt::Level OptLevel)
 166         : SelectionDAGISel(tm, OptLevel), OptForSize(false),
 167           OptForMinSize(false) {}
 168
 169     StringRef getPassName() const override {
 170       return "X86 DAG->DAG Instruction Selection";
 171     }
 172
 173     bool runOnMachineFunction(MachineFunction &MF) override {
 174       // Reset the subtarget each time through.
 175       Subtarget = &MF.getSubtarget<X86Subtarget>();
 176       SelectionDAGISel::runOnMachineFunction(MF);
 177       return true;
 178     }
 179
 180     void EmitFunctionEntryCode() override;
 181
 182     bool IsProfitableToFold(SDValue N, SDNode *U, SDNode *Root) const override;
 183
 184     void PreprocessISelDAG() override;
 185     void PostprocessISelDAG() override;
 186
 187 // Include the pieces autogenerated from the target description.
 188 #include "X86GenDAGISel.inc"
 189
 190   private:
 191     void Select(SDNode *N) override;
 192
 193     bool foldOffsetIntoAddress(uint64_t Offset, X86ISelAddressMode &AM);
 194     bool matchLoadInAddress(LoadSDNode *N, X86ISelAddressMode &AM);
 195     bool matchWrapper(SDValue N, X86ISelAddressMode &AM);
 196     bool matchAddress(SDValue N, X86ISelAddressMode &AM);
 197     bool matchVectorAddress(SDValue N, X86ISelAddressMode &AM);
 198     bool matchAdd(SDValue N, X86ISelAddressMode &AM, unsigned Depth);
 199     bool matchAddressRecursively(SDValue N, X86ISelAddressMode &AM,
 200                                  unsigned Depth);
 201     bool matchAddressBase(SDValue N, X86ISelAddressMode &AM);
 202     bool selectAddr(SDNode *Parent, SDValue N, SDValue &Base,
 203                     SDValue &Scale, SDValue &Index, SDValue &Disp,
 204                     SDValue &Segment);
 205     bool selectVectorAddr(SDNode *Parent, SDValue N, SDValue &Base,
 206                           SDValue &Scale, SDValue &Index, SDValue &Disp,
 207                           SDValue &Segment);
 208     bool selectMOV64Imm32(SDValue N, SDValue &Imm);
 209     bool selectLEAAddr(SDValue N, SDValue &Base,
 210                        SDValue &Scale, SDValue &Index, SDValue &Disp,
 211                        SDValue &Segment);
 212     bool selectLEA64_32Addr(SDValue N, SDValue &Base,
 213                             SDValue &Scale, SDValue &Index, SDValue &Disp,
 214                             SDValue &Segment);
 215     bool selectTLSADDRAddr(SDValue N, SDValue &Base,
 216                            SDValue &Scale, SDValue &Index, SDValue &Disp,
 217                            SDValue &Segment);
 218     bool selectScalarSSELoad(SDNode *Root, SDNode *Parent, SDValue N,
 219                              SDValue &Base, SDValue &Scale,
 220                              SDValue &Index, SDValue &Disp,
 221                              SDValue &Segment,
 222                              SDValue &NodeWithChain);
 223     bool selectRelocImm(SDValue N, SDValue &Op);
 224
 225     bool tryFoldLoad(SDNode *Root, SDNode *P, SDValue N,
 226                      SDValue &Base, SDValue &Scale,
 227                      SDValue &Index, SDValue &Disp,
 228                      SDValue &Segment);
 229
 230     // Convenience method where P is also root.
 231     bool tryFoldLoad(SDNode *P, SDValue N,
 232                      SDValue &Base, SDValue &Scale,
 233                      SDValue &Index, SDValue &Disp,
 234                      SDValue &Segment) {
 235       return tryFoldLoad(P, P, N, Base, Scale, Index, Disp, Segment);
 236     }
 237
 238     // Try to fold a vector load. This makes sure the load isn't non-temporal.
 239     bool tryFoldVecLoad(SDNode *Root, SDNode *P, SDValue N,
 240                         SDValue &Base, SDValue &Scale,
 241                         SDValue &Index, SDValue &Disp,
 242                         SDValue &Segment);
 243
 244     /// Implement addressing mode selection for inline asm expressions.
 245     bool SelectInlineAsmMemoryOperand(const SDValue &Op,
 246                                       unsigned ConstraintID,
 247                                       std::vector<SDValue> &OutOps) override;
 248
 249     void emitSpecialCodeForMain();
 250
 251     inline void getAddressOperands(X86ISelAddressMode &AM, const SDLoc &DL,
 252                                    SDValue &Base, SDValue &Scale,
 253                                    SDValue &Index, SDValue &Disp,
 254                                    SDValue &Segment) {
 255       Base = (AM.BaseType == X86ISelAddressMode::FrameIndexBase)
 256                  ? CurDAG->getTargetFrameIndex(
 257                        AM.Base_FrameIndex,
 258                        TLI->getPointerTy(CurDAG->getDataLayout()))
 259                  : AM.Base_Reg;
 260       Scale = getI8Imm(AM.Scale, DL);
 261       Index = AM.IndexReg;
 262       // These are 32-bit even in 64-bit mode since RIP-relative offset
 263       // is 32-bit.
 264       if (AM.GV)
 265         Disp = CurDAG->getTargetGlobalAddress(AM.GV, SDLoc(),
 266                                               MVT::i32, AM.Disp,
 267                                               AM.SymbolFlags);
 268       else if (AM.CP)
 269         Disp = CurDAG->getTargetConstantPool(AM.CP, MVT::i32,
 270                                              AM.Align, AM.Disp, AM.SymbolFlags);
 271       else if (AM.ES) {
 272         assert(!AM.Disp && "Non-zero displacement is ignored with ES.");
 273         Disp = CurDAG->getTargetExternalSymbol(AM.ES, MVT::i32, AM.SymbolFlags);
 274       } else if (AM.MCSym) {
 275         assert(!AM.Disp && "Non-zero displacement is ignored with MCSym.");
 276         assert(AM.SymbolFlags == 0 && "oo");
 277         Disp = CurDAG->getMCSymbol(AM.MCSym, MVT::i32);
 278       } else if (AM.JT != -1) {
 279         assert(!AM.Disp && "Non-zero displacement is ignored with JT.");
 280         Disp = CurDAG->getTargetJumpTable(AM.JT, MVT::i32, AM.SymbolFlags);
 281       } else if (AM.BlockAddr)
 282         Disp = CurDAG->getTargetBlockAddress(AM.BlockAddr, MVT::i32, AM.Disp,
 283                                              AM.SymbolFlags);
 284       else
 285         Disp = CurDAG->getTargetConstant(AM.Disp, DL, MVT::i32);
 286
 287       if (AM.Segment.getNode())
 288         Segment = AM.Segment;
 289       else
 290         Segment = CurDAG->getRegister(0, MVT::i32);
 291     }
 292
 293     // Utility function to determine whether we should avoid selecting
 294     // immediate forms of instructions for better code size or not.
 295     // At a high level, we'd like to avoid such instructions when
 296     // we have similar constants used within the same basic block
 297     // that can be kept in a register.
 298     //
 299     bool shouldAvoidImmediateInstFormsForSize(SDNode *N) const {
 300       uint32_t UseCount = 0;
 301
 302       // Do not want to hoist if we're not optimizing for size.
 303       // TODO: We'd like to remove this restriction.
 304       // See the comment in X86InstrInfo.td for more info.
 305       if (!OptForSize)
 306         return false;
 307
 308       // Walk all the users of the immediate.
 309       for (SDNode::use_iterator UI = N->use_begin(),
 310            UE = N->use_end(); (UI != UE) && (UseCount < 2); ++UI) {
 311
 312         SDNode *User = *UI;
 313
 314         // This user is already selected. Count it as a legitimate use and
 315         // move on.
 316         if (User->isMachineOpcode()) {
 317           UseCount++;
 318           continue;
 319         }
 320
 321         // We want to count stores of immediates as real uses.
 322         if (User->getOpcode() == ISD::STORE &&
 323             User->getOperand(1).getNode() == N) {
 324           UseCount++;
 325           continue;
 326         }
 327
 328         // We don't currently match users that have > 2 operands (except
 329         // for stores, which are handled above)
 330         // Those instruction won't match in ISEL, for now, and would
 331         // be counted incorrectly.
 332         // This may change in the future as we add additional instruction
 333         // types.
 334         if (User->getNumOperands() != 2)
 335           continue;
 336
 337         // Immediates that are used for offsets as part of stack
 338         // manipulation should be left alone. These are typically
 339         // used to indicate SP offsets for argument passing and
 340         // will get pulled into stores/pushes (implicitly).
 341         if (User->getOpcode() == X86ISD::ADD ||
 342             User->getOpcode() == ISD::ADD    ||
 343             User->getOpcode() == X86ISD::SUB ||
 344             User->getOpcode() == ISD::SUB) {
 345
 346           // Find the other operand of the add/sub.
 347           SDValue OtherOp = User->getOperand(0);
 348           if (OtherOp.getNode() == N)
 349             OtherOp = User->getOperand(1);
 350
 351           // Don't count if the other operand is SP.
 352           RegisterSDNode *RegNode;
 353           if (OtherOp->getOpcode() == ISD::CopyFromReg &&
 354               (RegNode = dyn_cast_or_null<RegisterSDNode>(
 355                  OtherOp->getOperand(1).getNode())))
 356             if ((RegNode->getReg() == X86::ESP) ||
 357                 (RegNode->getReg() == X86::RSP))
 358               continue;
 359         }
 360
 361         // ... otherwise, count this and move on.
 362         UseCount++;
 363       }
 364
 365       // If we have more than 1 use, then recommend for hoisting.
 366       return (UseCount > 1);
 367     }
 368
 369     /// Return a target constant with the specified value of type i8.
 370     inline SDValue getI8Imm(unsigned Imm, const SDLoc &DL) {
 371       return CurDAG->getTargetConstant(Imm, DL, MVT::i8);
 372     }
 373
 374     /// Return a target constant with the specified value, of type i32.
 375     inline SDValue getI32Imm(unsigned Imm, const SDLoc &DL) {
 376       return CurDAG->getTargetConstant(Imm, DL, MVT::i32);
 377     }
 378
 379     /// Return a target constant with the specified value, of type i64.
 380     inline SDValue getI64Imm(uint64_t Imm, const SDLoc &DL) {
 381       return CurDAG->getTargetConstant(Imm, DL, MVT::i64);
 382     }
 383
 384     SDValue getExtractVEXTRACTImmediate(SDNode *N, unsigned VecWidth,
 385                                         const SDLoc &DL) {
 386       assert((VecWidth == 128 || VecWidth == 256) && "Unexpected vector width");
 387       uint64_t Index = N->getConstantOperandVal(1);
 388       MVT VecVT = N->getOperand(0).getSimpleValueType();
 389       return getI8Imm((Index * VecVT.getScalarSizeInBits()) / VecWidth, DL);
 390     }
 391
 392     SDValue getInsertVINSERTImmediate(SDNode *N, unsigned VecWidth,
 393                                       const SDLoc &DL) {
 394       assert((VecWidth == 128 || VecWidth == 256) && "Unexpected vector width");
 395       uint64_t Index = N->getConstantOperandVal(2);
 396       MVT VecVT = N->getSimpleValueType(0);
 397       return getI8Imm((Index * VecVT.getScalarSizeInBits()) / VecWidth, DL);
 398     }
 399
 400     /// Return an SDNode that returns the value of the global base register.
 401     /// Output instructions required to initialize the global base register,
 402     /// if necessary.
 403     SDNode *getGlobalBaseReg();
 404
 405     /// Return a reference to the TargetMachine, casted to the target-specific
 406     /// type.
 407     const X86TargetMachine &getTargetMachine() const {
 408       return static_cast<const X86TargetMachine &>(TM);
 409     }
 410
 411     /// Return a reference to the TargetInstrInfo, casted to the target-specific
 412     /// type.
 413     const X86InstrInfo *getInstrInfo() const {
 414       return Subtarget->getInstrInfo();
 415     }
 416
 417     /// Address-mode matching performs shift-of-and to and-of-shift
 418     /// reassociation in order to expose more scaled addressing
 419     /// opportunities.
 420     bool ComplexPatternFuncMutatesDAG() const override {
 421       return true;
 422     }
 423
 424     bool isSExtAbsoluteSymbolRef(unsigned Width, SDNode *N) const;
 425
 426     /// Returns whether this is a relocatable immediate in the range
 427     /// [-2^Width .. 2^Width-1].
 428     template <unsigned Width> bool isSExtRelocImm(SDNode *N) const {
 429       if (auto *CN = dyn_cast<ConstantSDNode>(N))
 430         return isInt<Width>(CN->getSExtValue());
 431       return isSExtAbsoluteSymbolRef(Width, N);
 432     }
 433
 434     // Indicates we should prefer to use a non-temporal load for this load.
 435     bool useNonTemporalLoad(LoadSDNode *N) const {
 436       if (!N->isNonTemporal())
 437         return false;
 438
 439       unsigned StoreSize = N->getMemoryVT().getStoreSize();
 440
 441       if (N->getAlignment() < StoreSize)
 442         return false;
 443
 444       switch (StoreSize) {
 445       default: llvm_unreachable("Unsupported store size");
 446       case 16:
 447         return Subtarget->hasSSE41();
 448       case 32:
 449         return Subtarget->hasAVX2();
 450       case 64:
 451         return Subtarget->hasAVX512();
 452       }
 453     }
 454
 455     bool foldLoadStoreIntoMemOperand(SDNode *Node);
 456     bool matchBEXTRFromAnd(SDNode *Node);
 457     bool shrinkAndImmediate(SDNode *N);
 458     bool isMaskZeroExtended(SDNode *N) const;
 459
 460     MachineSDNode *emitPCMPISTR(unsigned ROpc, unsigned MOpc, bool MayFoldLoad,
 461                                 const SDLoc &dl, MVT VT, SDNode *Node);
 462     MachineSDNode *emitPCMPESTR(unsigned ROpc, unsigned MOpc, bool MayFoldLoad,
 463                                 const SDLoc &dl, MVT VT, SDNode *Node,
 464                                 SDValue &InFlag);
 465   };
 466 }
 467
 468
 469 // Returns true if this masked compare can be implemented legally with this
 470 // type.
 471 static bool isLegalMaskCompare(SDNode *N, const X86Subtarget *Subtarget) {
 472   unsigned Opcode = N->getOpcode();
 473   if (Opcode == X86ISD::CMPM || Opcode == ISD::SETCC ||
 474       Opcode == X86ISD::CMPM_RND || Opcode == X86ISD::VFPCLASS) {
 475     // We can get 256-bit 8 element types here without VLX being enabled. When
 476     // this happens we will use 512-bit operations and the mask will not be
 477     // zero extended.
 478     EVT OpVT = N->getOperand(0).getValueType();
 479     if (OpVT.is256BitVector() || OpVT.is128BitVector())
 480       return Subtarget->hasVLX();
 481
 482     return true;
 483   }
 484   // Scalar opcodes use 128 bit registers, but aren't subject to the VLX check.
 485   if (Opcode == X86ISD::VFPCLASSS || Opcode == X86ISD::FSETCCM ||
 486       Opcode == X86ISD::FSETCCM_RND)
 487     return true;
 488
 489   return false;
 490 }
 491
 492 // Returns true if we can assume the writer of the mask has zero extended it
 493 // for us.
 494 bool X86DAGToDAGISel::isMaskZeroExtended(SDNode *N) const {
 495   // If this is an AND, check if we have a compare on either side. As long as
 496   // one side guarantees the mask is zero extended, the AND will preserve those
 497   // zeros.
 498   if (N->getOpcode() == ISD::AND)
 499     return isLegalMaskCompare(N->getOperand(0).getNode(), Subtarget) ||
 500            isLegalMaskCompare(N->getOperand(1).getNode(), Subtarget);
 501
 502   return isLegalMaskCompare(N, Subtarget);
 503 }
 504
 505 bool
 506 X86DAGToDAGISel::IsProfitableToFold(SDValue N, SDNode *U, SDNode *Root) const {
 507   if (OptLevel == CodeGenOpt::None) return false;
 508
 509   if (!N.hasOneUse())
 510     return false;
 511
 512   if (N.getOpcode() != ISD::LOAD)
 513     return true;
 514
 515   // If N is a load, do additional profitability checks.
 516   if (U == Root) {
 517     switch (U->getOpcode()) {
 518     default: break;
 519     case X86ISD::ADD:
 520     case X86ISD::SUB:
 521     case X86ISD::AND:
 522     case X86ISD::XOR:
 523     case X86ISD::OR:
 524     case ISD::ADD:
 525     case ISD::ADDCARRY:
 526     case ISD::AND:
 527     case ISD::OR:
 528     case ISD::XOR: {
 529       SDValue Op1 = U->getOperand(1);
 530
 531       // If the other operand is a 8-bit immediate we should fold the immediate
 532       // instead. This reduces code size.
 533       // e.g.
 534       // movl 4(%esp), %eax
 535       // addl $4, %eax
 536       // vs.
 537       // movl $4, %eax
 538       // addl 4(%esp), %eax
 539       // The former is 2 bytes shorter. In case where the increment is 1, then
 540       // the saving can be 4 bytes (by using incl %eax).
 541       if (ConstantSDNode *Imm = dyn_cast<ConstantSDNode>(Op1)) {
 542         if (Imm->getAPIntValue().isSignedIntN(8))
 543           return false;
 544
 545         // If this is a 64-bit AND with an immediate that fits in 32-bits,
 546         // prefer using the smaller and over folding the load. This is needed to
 547         // make sure immediates created by shrinkAndImmediate are always folded.
 548         // Ideally we would narrow the load during DAG combine and get the
 549         // best of both worlds.
 550         if (U->getOpcode() == ISD::AND &&
 551             Imm->getAPIntValue().getBitWidth() == 64 &&
 552             Imm->getAPIntValue().isIntN(32))
 553           return false;
 554       }
 555
 556       // If the other operand is a TLS address, we should fold it instead.
 557       // This produces
 558       // movl    %gs:0, %eax
 559       // leal    i@NTPOFF(%eax), %eax
 560       // instead of
 561       // movl    $i@NTPOFF, %eax
 562       // addl    %gs:0, %eax
 563       // if the block also has an access to a second TLS address this will save
 564       // a load.
 565       // FIXME: This is probably also true for non-TLS addresses.
 566       if (Op1.getOpcode() == X86ISD::Wrapper) {
 567         SDValue Val = Op1.getOperand(0);
 568         if (Val.getOpcode() == ISD::TargetGlobalTLSAddress)
 569           return false;
 570       }
 571     }
 572     }
 573   }
 574
 575   return true;
 576 }
 577
 578 /// Replace the original chain operand of the call with
 579 /// load's chain operand and move load below the call's chain operand.
 580 static void moveBelowOrigChain(SelectionDAG *CurDAG, SDValue Load,
 581                                SDValue Call, SDValue OrigChain) {
 582   SmallVector<SDValue, 8> Ops;
 583   SDValue Chain = OrigChain.getOperand(0);
 584   if (Chain.getNode() == Load.getNode())
 585     Ops.push_back(Load.getOperand(0));
 586   else {
 587     assert(Chain.getOpcode() == ISD::TokenFactor &&
 588            "Unexpected chain operand");
 589     for (unsigned i = 0, e = Chain.getNumOperands(); i != e; ++i)
 590       if (Chain.getOperand(i).getNode() == Load.getNode())
 591         Ops.push_back(Load.getOperand(0));
 592       else
 593         Ops.push_back(Chain.getOperand(i));
 594     SDValue NewChain =
 595       CurDAG->getNode(ISD::TokenFactor, SDLoc(Load), MVT::Other, Ops);
 596     Ops.clear();
 597     Ops.push_back(NewChain);
 598   }
 599   Ops.append(OrigChain->op_begin() + 1, OrigChain->op_end());
 600   CurDAG->UpdateNodeOperands(OrigChain.getNode(), Ops);
 601   CurDAG->UpdateNodeOperands(Load.getNode(), Call.getOperand(0),
 602                              Load.getOperand(1), Load.getOperand(2));
 603
 604   Ops.clear();
 605   Ops.push_back(SDValue(Load.getNode(), 1));
 606   Ops.append(Call->op_begin() + 1, Call->op_end());
 607   CurDAG->UpdateNodeOperands(Call.getNode(), Ops);
 608 }
 609
 610 /// Return true if call address is a load and it can be
 611 /// moved below CALLSEQ_START and the chains leading up to the call.
 612 /// Return the CALLSEQ_START by reference as a second output.
 613 /// In the case of a tail call, there isn't a callseq node between the call
 614 /// chain and the load.
 615 static bool isCalleeLoad(SDValue Callee, SDValue &Chain, bool HasCallSeq) {
 616   // The transformation is somewhat dangerous if the call's chain was glued to
 617   // the call. After MoveBelowOrigChain the load is moved between the call and
 618   // the chain, this can create a cycle if the load is not folded. So it is
 619   // *really* important that we are sure the load will be folded.
 620   if (Callee.getNode() == Chain.getNode() || !Callee.hasOneUse())
 621     return false;
 622   LoadSDNode *LD = dyn_cast<LoadSDNode>(Callee.getNode());
 623   if (!LD ||
 624       LD->isVolatile() ||
 625       LD->getAddressingMode() != ISD::UNINDEXED ||
 626       LD->getExtensionType() != ISD::NON_EXTLOAD)
 627     return false;
 628
 629   // Now let's find the callseq_start.
 630   while (HasCallSeq && Chain.getOpcode() != ISD::CALLSEQ_START) {
 631     if (!Chain.hasOneUse())
 632       return false;
 633     Chain = Chain.getOperand(0);
 634   }
 635
 636   if (!Chain.getNumOperands())
 637     return false;
 638   // Since we are not checking for AA here, conservatively abort if the chain
 639   // writes to memory. It's not safe to move the callee (a load) across a store.
 640   if (isa<MemSDNode>(Chain.getNode()) &&
 641       cast<MemSDNode>(Chain.getNode())->writeMem())
 642     return false;
 643   if (Chain.getOperand(0).getNode() == Callee.getNode())
 644     return true;
 645   if (Chain.getOperand(0).getOpcode() == ISD::TokenFactor &&
 646       Callee.getValue(1).isOperandOf(Chain.getOperand(0).getNode()) &&
 647       Callee.getValue(1).hasOneUse())
 648     return true;
 649   return false;
 650 }
 651
 652 void X86DAGToDAGISel::PreprocessISelDAG() {
 653   // OptFor[Min]Size are used in pattern predicates that isel is matching.
 654   OptForSize = MF->getFunction().optForSize();
 655   OptForMinSize = MF->getFunction().optForMinSize();
 656   assert((!OptForMinSize || OptForSize) && "OptForMinSize implies OptForSize");
 657
 658   for (SelectionDAG::allnodes_iterator I = CurDAG->allnodes_begin(),
 659        E = CurDAG->allnodes_end(); I != E; ) {
 660     SDNode *N = &*I++; // Preincrement iterator to avoid invalidation issues.
 661
 662     // If this is a target specific AND node with no flag usages, turn it back
 663     // into ISD::AND to enable test instruction matching.
 664     if (N->getOpcode() == X86ISD::AND && !N->hasAnyUseOfValue(1)) {
 665       SDValue Res = CurDAG->getNode(ISD::AND, SDLoc(N), N->getValueType(0),
 666                                     N->getOperand(0), N->getOperand(1));
 667       --I;
 668       CurDAG->ReplaceAllUsesOfValueWith(SDValue(N, 0), Res);
 669       ++I;
 670       CurDAG->DeleteNode(N);
 671     }
 672
 673     if (OptLevel != CodeGenOpt::None &&
 674         // Only do this when the target can fold the load into the call or
 675         // jmp.
 676         !Subtarget->useRetpoline() &&
 677         ((N->getOpcode() == X86ISD::CALL && !Subtarget->slowTwoMemOps()) ||
 678          (N->getOpcode() == X86ISD::TC_RETURN &&
 679           (Subtarget->is64Bit() ||
 680            !getTargetMachine().isPositionIndependent())))) {
 681       /// Also try moving call address load from outside callseq_start to just
 682       /// before the call to allow it to be folded.
 683       ///
 684       ///     [Load chain]
 685       ///         ^
 686       ///         |
 687       ///       [Load]
 688       ///       ^    ^
 689       ///       |    |
 690       ///      /      \--
 691       ///     /          |
 692       ///[CALLSEQ_START] |
 693       ///     ^          |
 694       ///     |          |
 695       /// [LOAD/C2Reg]   |
 696       ///     |          |
 697       ///      \        /
 698       ///       \      /
 699       ///       [CALL]
 700       bool HasCallSeq = N->getOpcode() == X86ISD::CALL;
 701       SDValue Chain = N->getOperand(0);
 702       SDValue Load  = N->getOperand(1);
 703       if (!isCalleeLoad(Load, Chain, HasCallSeq))
 704         continue;
 705       moveBelowOrigChain(CurDAG, Load, SDValue(N, 0), Chain);
 706       ++NumLoadMoved;
 707       continue;
 708     }
 709
 710     // Lower fpround and fpextend nodes that target the FP stack to be store and
 711     // load to the stack.  This is a gross hack.  We would like to simply mark
 712     // these as being illegal, but when we do that, legalize produces these when
 713     // it expands calls, then expands these in the same legalize pass.  We would
 714     // like dag combine to be able to hack on these between the call expansion
 715     // and the node legalization.  As such this pass basically does "really
 716     // late" legalization of these inline with the X86 isel pass.
 717     // FIXME: This should only happen when not compiled with -O0.
 718     if (N->getOpcode() != ISD::FP_ROUND && N->getOpcode() != ISD::FP_EXTEND)
 719       continue;
 720
 721     MVT SrcVT = N->getOperand(0).getSimpleValueType();
 722     MVT DstVT = N->getSimpleValueType(0);
 723
 724     // If any of the sources are vectors, no fp stack involved.
 725     if (SrcVT.isVector() || DstVT.isVector())
 726       continue;
 727
 728     // If the source and destination are SSE registers, then this is a legal
 729     // conversion that should not be lowered.
 730     const X86TargetLowering *X86Lowering =
 731         static_cast<const X86TargetLowering *>(TLI);
 732     bool SrcIsSSE = X86Lowering->isScalarFPTypeInSSEReg(SrcVT);
 733     bool DstIsSSE = X86Lowering->isScalarFPTypeInSSEReg(DstVT);
 734     if (SrcIsSSE && DstIsSSE)
 735       continue;
 736
 737     if (!SrcIsSSE && !DstIsSSE) {
 738       // If this is an FPStack extension, it is a noop.
 739       if (N->getOpcode() == ISD::FP_EXTEND)
 740         continue;
 741       // If this is a value-preserving FPStack truncation, it is a noop.
 742       if (N->getConstantOperandVal(1))
 743         continue;
 744     }
 745
 746     // Here we could have an FP stack truncation or an FPStack <-> SSE convert.
 747     // FPStack has extload and truncstore.  SSE can fold direct loads into other
 748     // operations.  Based on this, decide what we want to do.
 749     MVT MemVT;
 750     if (N->getOpcode() == ISD::FP_ROUND)
 751       MemVT = DstVT;  // FP_ROUND must use DstVT, we can't do a 'trunc load'.
 752     else
 753       MemVT = SrcIsSSE ? SrcVT : DstVT;
 754
 755     SDValue MemTmp = CurDAG->CreateStackTemporary(MemVT);
 756     SDLoc dl(N);
 757
 758     // FIXME: optimize the case where the src/dest is a load or store?
 759     SDValue Store =
 760         CurDAG->getTruncStore(CurDAG->getEntryNode(), dl, N->getOperand(0),
 761                               MemTmp, MachinePointerInfo(), MemVT);
 762     SDValue Result = CurDAG->getExtLoad(ISD::EXTLOAD, dl, DstVT, Store, MemTmp,
 763                                         MachinePointerInfo(), MemVT);
 764
 765     // We're about to replace all uses of the FP_ROUND/FP_EXTEND with the
 766     // extload we created.  This will cause general havok on the dag because
 767     // anything below the conversion could be folded into other existing nodes.
 768     // To avoid invalidating 'I', back it up to the convert node.
 769     --I;
 770     CurDAG->ReplaceAllUsesOfValueWith(SDValue(N, 0), Result);
 771
 772     // Now that we did that, the node is dead.  Increment the iterator to the
 773     // next node to process, then delete N.
 774     ++I;
 775     CurDAG->DeleteNode(N);
 776   }
 777 }
 778
 779
 780 void X86DAGToDAGISel::PostprocessISelDAG() {
 781   // Skip peepholes at -O0.
 782   if (TM.getOptLevel() == CodeGenOpt::None)
 783     return;
 784
 785   // Attempt to remove vectors moves that were inserted to zero upper bits.
 786
 787   SelectionDAG::allnodes_iterator Position(CurDAG->getRoot().getNode());
 788   ++Position;
 789
 790   while (Position != CurDAG->allnodes_begin()) {
 791     SDNode *N = &*--Position;
 792     // Skip dead nodes and any non-machine opcodes.
 793     if (N->use_empty() || !N->isMachineOpcode())
 794       continue;
 795
 796     if (N->getMachineOpcode() != TargetOpcode::SUBREG_TO_REG)
 797       continue;
 798
 799     unsigned SubRegIdx = N->getConstantOperandVal(2);
 800     if (SubRegIdx != X86::sub_xmm && SubRegIdx != X86::sub_ymm)
 801       continue;
 802
 803     SDValue Move = N->getOperand(1);
 804     if (!Move.isMachineOpcode())
 805       continue;
 806
 807     // Make sure its one of the move opcodes we recognize.
 808     switch (Move.getMachineOpcode()) {
 809     default:
 810       continue;
 811     case X86::VMOVAPDrr:       case X86::VMOVUPDrr:
 812     case X86::VMOVAPSrr:       case X86::VMOVUPSrr:
 813     case X86::VMOVDQArr:       case X86::VMOVDQUrr:
 814     case X86::VMOVAPDYrr:      case X86::VMOVUPDYrr:
 815     case X86::VMOVAPSYrr:      case X86::VMOVUPSYrr:
 816     case X86::VMOVDQAYrr:      case X86::VMOVDQUYrr:
 817     case X86::VMOVAPDZ128rr:   case X86::VMOVUPDZ128rr:
 818     case X86::VMOVAPSZ128rr:   case X86::VMOVUPSZ128rr:
 819     case X86::VMOVDQA32Z128rr: case X86::VMOVDQU32Z128rr:
 820     case X86::VMOVDQA64Z128rr: case X86::VMOVDQU64Z128rr:
 821     case X86::VMOVAPDZ256rr:   case X86::VMOVUPDZ256rr:
 822     case X86::VMOVAPSZ256rr:   case X86::VMOVUPSZ256rr:
 823     case X86::VMOVDQA32Z256rr: case X86::VMOVDQU32Z256rr:
 824     case X86::VMOVDQA64Z256rr: case X86::VMOVDQU64Z256rr:
 825       break;
 826     }
 827
 828     SDValue In = Move.getOperand(0);
 829     if (!In.isMachineOpcode() ||
 830         In.getMachineOpcode() <= TargetOpcode::GENERIC_OP_END)
 831       continue;
 832
 833     // Producing instruction is another vector instruction. We can drop the
 834     // move.
 835     CurDAG->UpdateNodeOperands(N, N->getOperand(0), In, N->getOperand(2));
 836
 837     // If the move is now dead, delete it.
 838     if (Move.getNode()->use_empty())
 839       CurDAG->RemoveDeadNode(Move.getNode());
 840   }
 841 }
 842
 843
 844 /// Emit any code that needs to be executed only in the main function.
 845 void X86DAGToDAGISel::emitSpecialCodeForMain() {
 846   if (Subtarget->isTargetCygMing()) {
 847     TargetLowering::ArgListTy Args;
 848     auto &DL = CurDAG->getDataLayout();
 849
 850     TargetLowering::CallLoweringInfo CLI(*CurDAG);
 851     CLI.setChain(CurDAG->getRoot())
 852         .setCallee(CallingConv::C, Type::getVoidTy(*CurDAG->getContext()),
 853                    CurDAG->getExternalSymbol("__main", TLI->getPointerTy(DL)),
 854                    std::move(Args));
 855     const TargetLowering &TLI = CurDAG->getTargetLoweringInfo();
 856     std::pair<SDValue, SDValue> Result = TLI.LowerCallTo(CLI);
 857     CurDAG->setRoot(Result.second);
 858   }
 859 }
 860
 861 void X86DAGToDAGISel::EmitFunctionEntryCode() {
 862   // If this is main, emit special code for main.
 863   const Function &F = MF->getFunction();
 864   if (F.hasExternalLinkage() && F.getName() == "main")
 865     emitSpecialCodeForMain();
 866 }
 867
 868 static bool isDispSafeForFrameIndex(int64_t Val) {
 869   // On 64-bit platforms, we can run into an issue where a frame index
 870   // includes a displacement that, when added to the explicit displacement,
 871   // will overflow the displacement field. Assuming that the frame index
 872   // displacement fits into a 31-bit integer  (which is only slightly more
 873   // aggressive than the current fundamental assumption that it fits into
 874   // a 32-bit integer), a 31-bit disp should always be safe.
 875   return isInt<31>(Val);
 876 }
 877
 878 bool X86DAGToDAGISel::foldOffsetIntoAddress(uint64_t Offset,
 879                                             X86ISelAddressMode &AM) {
 880   // If there's no offset to fold, we don't need to do any work.
 881   if (Offset == 0)
 882     return false;
 883
 884   // Cannot combine ExternalSymbol displacements with integer offsets.
 885   if (AM.ES || AM.MCSym)
 886     return true;
 887
 888   int64_t Val = AM.Disp + Offset;
 889   CodeModel::Model M = TM.getCodeModel();
 890   if (Subtarget->is64Bit()) {
 891     if (!X86::isOffsetSuitableForCodeModel(Val, M,
 892                                            AM.hasSymbolicDisplacement()))
 893       return true;
 894     // In addition to the checks required for a register base, check that
 895     // we do not try to use an unsafe Disp with a frame index.
 896     if (AM.BaseType == X86ISelAddressMode::FrameIndexBase &&
 897         !isDispSafeForFrameIndex(Val))
 898       return true;
 899   }
 900   AM.Disp = Val;
 901   return false;
 902
 903 }
 904
 905 bool X86DAGToDAGISel::matchLoadInAddress(LoadSDNode *N, X86ISelAddressMode &AM){
 906   SDValue Address = N->getOperand(1);
 907
 908   // load gs:0 -> GS segment register.
 909   // load fs:0 -> FS segment register.
 910   //
 911   // This optimization is valid because the GNU TLS model defines that
 912   // gs:0 (or fs:0 on X86-64) contains its own address.
 913   // For more information see http://people.redhat.com/drepper/tls.pdf
 914   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Address))
 915     if (C->getSExtValue() == 0 && AM.Segment.getNode() == nullptr &&
 916         (Subtarget->isTargetGlibc() || Subtarget->isTargetAndroid() ||
 917          Subtarget->isTargetFuchsia()))
 918       switch (N->getPointerInfo().getAddrSpace()) {
 919       case 256:
 920         AM.Segment = CurDAG->getRegister(X86::GS, MVT::i16);
 921         return false;
 922       case 257:
 923         AM.Segment = CurDAG->getRegister(X86::FS, MVT::i16);
 924         return false;
 925       // Address space 258 is not handled here, because it is not used to
 926       // address TLS areas.
 927       }
 928
 929   return true;
 930 }
 931
 932 /// Try to match X86ISD::Wrapper and X86ISD::WrapperRIP nodes into an addressing
 933 /// mode. These wrap things that will resolve down into a symbol reference.
 934 /// If no match is possible, this returns true, otherwise it returns false.
 935 bool X86DAGToDAGISel::matchWrapper(SDValue N, X86ISelAddressMode &AM) {
 936   // If the addressing mode already has a symbol as the displacement, we can
 937   // never match another symbol.
 938   if (AM.hasSymbolicDisplacement())
 939     return true;
 940
 941   bool IsRIPRel = N.getOpcode() == X86ISD::WrapperRIP;
 942
 943   // Only do this address mode folding for 64-bit if we're in the small code
 944   // model.
 945   // FIXME: But we can do GOTPCREL addressing in the medium code model.
 946   CodeModel::Model M = TM.getCodeModel();
 947   if (Subtarget->is64Bit() && M != CodeModel::Small && M != CodeModel::Kernel)
 948     return true;
 949
 950   // Base and index reg must be 0 in order to use %rip as base.
 951   if (IsRIPRel && AM.hasBaseOrIndexReg())
 952     return true;
 953
 954   // Make a local copy in case we can't do this fold.
 955   X86ISelAddressMode Backup = AM;
 956
 957   int64_t Offset = 0;
 958   SDValue N0 = N.getOperand(0);
 959   if (GlobalAddressSDNode *G = dyn_cast<GlobalAddressSDNode>(N0)) {
 960     AM.GV = G->getGlobal();
 961     AM.SymbolFlags = G->getTargetFlags();
 962     Offset = G->getOffset();
 963   } else if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(N0)) {
 964     AM.CP = CP->getConstVal();
 965     AM.Align = CP->getAlignment();
 966     AM.SymbolFlags = CP->getTargetFlags();
 967     Offset = CP->getOffset();
 968   } else if (ExternalSymbolSDNode *S = dyn_cast<ExternalSymbolSDNode>(N0)) {
 969     AM.ES = S->getSymbol();
 970     AM.SymbolFlags = S->getTargetFlags();
 971   } else if (auto *S = dyn_cast<MCSymbolSDNode>(N0)) {
 972     AM.MCSym = S->getMCSymbol();
 973   } else if (JumpTableSDNode *J = dyn_cast<JumpTableSDNode>(N0)) {
 974     AM.JT = J->getIndex();
 975     AM.SymbolFlags = J->getTargetFlags();
 976   } else if (BlockAddressSDNode *BA = dyn_cast<BlockAddressSDNode>(N0)) {
 977     AM.BlockAddr = BA->getBlockAddress();
 978     AM.SymbolFlags = BA->getTargetFlags();
 979     Offset = BA->getOffset();
 980   } else
 981     llvm_unreachable("Unhandled symbol reference node.");
 982
 983   if (foldOffsetIntoAddress(Offset, AM)) {
 984     AM = Backup;
 985     return true;
 986   }
 987
 988   if (IsRIPRel)
 989     AM.setBaseReg(CurDAG->getRegister(X86::RIP, MVT::i64));
 990
 991   // Commit the changes now that we know this fold is safe.
 992   return false;
 993 }
 994
 995 /// Add the specified node to the specified addressing mode, returning true if
 996 /// it cannot be done. This just pattern matches for the addressing mode.
 997 bool X86DAGToDAGISel::matchAddress(SDValue N, X86ISelAddressMode &AM) {
 998   if (matchAddressRecursively(N, AM, 0))
 999     return true;
1000
1001   // Post-processing: Convert lea(,%reg,2) to lea(%reg,%reg), which has
1002   // a smaller encoding and avoids a scaled-index.
1003   if (AM.Scale == 2 &&
1004       AM.BaseType == X86ISelAddressMode::RegBase &&
1005       AM.Base_Reg.getNode() == nullptr) {
1006     AM.Base_Reg = AM.IndexReg;
1007     AM.Scale = 1;
1008   }
1009
1010   // Post-processing: Convert foo to foo(%rip), even in non-PIC mode,
1011   // because it has a smaller encoding.
1012   // TODO: Which other code models can use this?
1013   if (TM.getCodeModel() == CodeModel::Small &&
1014       Subtarget->is64Bit() &&
1015       AM.Scale == 1 &&
1016       AM.BaseType == X86ISelAddressMode::RegBase &&
1017       AM.Base_Reg.getNode() == nullptr &&
1018       AM.IndexReg.getNode() == nullptr &&
1019       AM.SymbolFlags == X86II::MO_NO_FLAG &&
1020       AM.hasSymbolicDisplacement())
1021     AM.Base_Reg = CurDAG->getRegister(X86::RIP, MVT::i64);
1022
1023   return false;
1024 }
1025
1026 bool X86DAGToDAGISel::matchAdd(SDValue N, X86ISelAddressMode &AM,
1027                                unsigned Depth) {
1028   // Add an artificial use to this node so that we can keep track of
1029   // it if it gets CSE'd with a different node.
1030   HandleSDNode Handle(N);
1031
1032   X86ISelAddressMode Backup = AM;
1033   if (!matchAddressRecursively(N.getOperand(0), AM, Depth+1) &&
1034       !matchAddressRecursively(Handle.getValue().getOperand(1), AM, Depth+1))
1035     return false;
1036   AM = Backup;
1037
1038   // Try again after commuting the operands.
1039   if (!matchAddressRecursively(Handle.getValue().getOperand(1), AM, Depth+1) &&
1040       !matchAddressRecursively(Handle.getValue().getOperand(0), AM, Depth+1))
1041     return false;
1042   AM = Backup;
1043
1044   // If we couldn't fold both operands into the address at the same time,
1045   // see if we can just put each operand into a register and fold at least
1046   // the add.
1047   if (AM.BaseType == X86ISelAddressMode::RegBase &&
1048       !AM.Base_Reg.getNode() &&
1049       !AM.IndexReg.getNode()) {
1050     N = Handle.getValue();
1051     AM.Base_Reg = N.getOperand(0);
1052     AM.IndexReg = N.getOperand(1);
1053     AM.Scale = 1;
1054     return false;
1055   }
1056   N = Handle.getValue();
1057   return true;
1058 }
1059
1060 // Insert a node into the DAG at least before the Pos node's position. This
1061 // will reposition the node as needed, and will assign it a node ID that is <=
1062 // the Pos node's ID. Note that this does *not* preserve the uniqueness of node
1063 // IDs! The selection DAG must no longer depend on their uniqueness when this
1064 // is used.
1065 static void insertDAGNode(SelectionDAG &DAG, SDValue Pos, SDValue N) {
1066   if (N->getNodeId() == -1 ||
1067       (SelectionDAGISel::getUninvalidatedNodeId(N.getNode()) >
1068        SelectionDAGISel::getUninvalidatedNodeId(Pos.getNode()))) {
1069     DAG.RepositionNode(Pos->getIterator(), N.getNode());
1070     // Mark Node as invalid for pruning as after this it may be a successor to a
1071     // selected node but otherwise be in the same position of Pos.
1072     // Conservatively mark it with the same -abs(Id) to assure node id
1073     // invariant is preserved.
1074     N->setNodeId(Pos->getNodeId());
1075     SelectionDAGISel::InvalidateNodeId(N.getNode());
1076   }
1077 }
1078
1079 // Transform "(X >> (8-C1)) & (0xff << C1)" to "((X >> 8) & 0xff) << C1" if
1080 // safe. This allows us to convert the shift and and into an h-register
1081 // extract and a scaled index. Returns false if the simplification is
1082 // performed.
1083 static bool foldMaskAndShiftToExtract(SelectionDAG &DAG, SDValue N,
1084                                       uint64_t Mask,
1085                                       SDValue Shift, SDValue X,
1086                                       X86ISelAddressMode &AM) {
1087   if (Shift.getOpcode() != ISD::SRL ||
1088       !isa<ConstantSDNode>(Shift.getOperand(1)) ||
1089       !Shift.hasOneUse())
1090     return true;
1091
1092   int ScaleLog = 8 - Shift.getConstantOperandVal(1);
1093   if (ScaleLog <= 0 || ScaleLog >= 4 ||
1094       Mask != (0xffu << ScaleLog))
1095     return true;
1096
1097   MVT VT = N.getSimpleValueType();
1098   SDLoc DL(N);
1099   SDValue Eight = DAG.getConstant(8, DL, MVT::i8);
1100   SDValue NewMask = DAG.getConstant(0xff, DL, VT);
1101   SDValue Srl = DAG.getNode(ISD::SRL, DL, VT, X, Eight);
1102   SDValue And = DAG.getNode(ISD::AND, DL, VT, Srl, NewMask);
1103   SDValue ShlCount = DAG.getConstant(ScaleLog, DL, MVT::i8);
1104   SDValue Shl = DAG.getNode(ISD::SHL, DL, VT, And, ShlCount);
1105
1106   // Insert the new nodes into the topological ordering. We must do this in
1107   // a valid topological ordering as nothing is going to go back and re-sort
1108   // these nodes. We continually insert before 'N' in sequence as this is
1109   // essentially a pre-flattened and pre-sorted sequence of nodes. There is no
1110   // hierarchy left to express.
1111   insertDAGNode(DAG, N, Eight);
1112   insertDAGNode(DAG, N, Srl);
1113   insertDAGNode(DAG, N, NewMask);
1114   insertDAGNode(DAG, N, And);
1115   insertDAGNode(DAG, N, ShlCount);
1116   insertDAGNode(DAG, N, Shl);
1117   DAG.ReplaceAllUsesWith(N, Shl);
1118   AM.IndexReg = And;
1119   AM.Scale = (1 << ScaleLog);
1120   return false;
1121 }
1122
1123 // Transforms "(X << C1) & C2" to "(X & (C2>>C1)) << C1" if safe and if this
1124 // allows us to fold the shift into this addressing mode. Returns false if the
1125 // transform succeeded.
1126 static bool foldMaskedShiftToScaledMask(SelectionDAG &DAG, SDValue N,
1127                                         uint64_t Mask,
1128                                         SDValue Shift, SDValue X,
1129                                         X86ISelAddressMode &AM) {
1130   if (Shift.getOpcode() != ISD::SHL ||
1131       !isa<ConstantSDNode>(Shift.getOperand(1)))
1132     return true;
1133
1134   // Not likely to be profitable if either the AND or SHIFT node has more
1135   // than one use (unless all uses are for address computation). Besides,
1136   // isel mechanism requires their node ids to be reused.
1137   if (!N.hasOneUse() || !Shift.hasOneUse())
1138     return true;
1139
1140   // Verify that the shift amount is something we can fold.
1141   unsigned ShiftAmt = Shift.getConstantOperandVal(1);
1142   if (ShiftAmt != 1 && ShiftAmt != 2 && ShiftAmt != 3)
1143     return true;
1144
1145   MVT VT = N.getSimpleValueType();
1146   SDLoc DL(N);
1147   SDValue NewMask = DAG.getConstant(Mask >> ShiftAmt, DL, VT);
1148   SDValue NewAnd = DAG.getNode(ISD::AND, DL, VT, X, NewMask);
1149   SDValue NewShift = DAG.getNode(ISD::SHL, DL, VT, NewAnd, Shift.getOperand(1));
1150
1151   // Insert the new nodes into the topological ordering. We must do this in
1152   // a valid topological ordering as nothing is going to go back and re-sort
1153   // these nodes. We continually insert before 'N' in sequence as this is
1154   // essentially a pre-flattened and pre-sorted sequence of nodes. There is no
1155   // hierarchy left to express.
1156   insertDAGNode(DAG, N, NewMask);
1157   insertDAGNode(DAG, N, NewAnd);
1158   insertDAGNode(DAG, N, NewShift);
1159   DAG.ReplaceAllUsesWith(N, NewShift);
1160
1161   AM.Scale = 1 << ShiftAmt;
1162   AM.IndexReg = NewAnd;
1163   return false;
1164 }
1165
1166 // Implement some heroics to detect shifts of masked values where the mask can
1167 // be replaced by extending the shift and undoing that in the addressing mode
1168 // scale. Patterns such as (shl (srl x, c1), c2) are canonicalized into (and
1169 // (srl x, SHIFT), MASK) by DAGCombines that don't know the shl can be done in
1170 // the addressing mode. This results in code such as:
1171 //
1172 //   int f(short *y, int *lookup_table) {
1173 //     ...
1174 //     return *y + lookup_table[*y >> 11];
1175 //   }
1176 //
1177 // Turning into:
1178 //   movzwl (%rdi), %eax
1179 //   movl %eax, %ecx
1180 //   shrl $11, %ecx
1181 //   addl (%rsi,%rcx,4), %eax
1182 //
1183 // Instead of:
1184 //   movzwl (%rdi), %eax
1185 //   movl %eax, %ecx
1186 //   shrl $9, %ecx
1187 //   andl $124, %rcx
1188 //   addl (%rsi,%rcx), %eax
1189 //
1190 // Note that this function assumes the mask is provided as a mask *after* the
1191 // value is shifted. The input chain may or may not match that, but computing
1192 // such a mask is trivial.
1193 static bool foldMaskAndShiftToScale(SelectionDAG &DAG, SDValue N,
1194                                     uint64_t Mask,
1195                                     SDValue Shift, SDValue X,
1196                                     X86ISelAddressMode &AM) {
1197   if (Shift.getOpcode() != ISD::SRL || !Shift.hasOneUse() ||
1198       !isa<ConstantSDNode>(Shift.getOperand(1)))
1199     return true;
1200
1201   unsigned ShiftAmt = Shift.getConstantOperandVal(1);
1202   unsigned MaskLZ = countLeadingZeros(Mask);
1203   unsigned MaskTZ = countTrailingZeros(Mask);
1204
1205   // The amount of shift we're trying to fit into the addressing mode is taken
1206   // from the trailing zeros of the mask.
1207   unsigned AMShiftAmt = MaskTZ;
1208
1209   // There is nothing we can do here unless the mask is removing some bits.
1210   // Also, the addressing mode can only represent shifts of 1, 2, or 3 bits.
1211   if (AMShiftAmt <= 0 || AMShiftAmt > 3) return true;
1212
1213   // We also need to ensure that mask is a continuous run of bits.
1214   if (countTrailingOnes(Mask >> MaskTZ) + MaskTZ + MaskLZ != 64) return true;
1215
1216   // Scale the leading zero count down based on the actual size of the value.
1217   // Also scale it down based on the size of the shift.
1218   unsigned ScaleDown = (64 - X.getSimpleValueType().getSizeInBits()) + ShiftAmt;
1219   if (MaskLZ < ScaleDown)
1220     return true;
1221   MaskLZ -= ScaleDown;
1222
1223   // The final check is to ensure that any masked out high bits of X are
1224   // already known to be zero. Otherwise, the mask has a semantic impact
1225   // other than masking out a couple of low bits. Unfortunately, because of
1226   // the mask, zero extensions will be removed from operands in some cases.
1227   // This code works extra hard to look through extensions because we can
1228   // replace them with zero extensions cheaply if necessary.
1229   bool ReplacingAnyExtend = false;
1230   if (X.getOpcode() == ISD::ANY_EXTEND) {
1231     unsigned ExtendBits = X.getSimpleValueType().getSizeInBits() -
1232                           X.getOperand(0).getSimpleValueType().getSizeInBits();
1233     // Assume that we'll replace the any-extend with a zero-extend, and
1234     // narrow the search to the extended value.
1235     X = X.getOperand(0);
1236     MaskLZ = ExtendBits > MaskLZ ? 0 : MaskLZ - ExtendBits;
1237     ReplacingAnyExtend = true;
1238   }
1239   APInt MaskedHighBits =
1240     APInt::getHighBitsSet(X.getSimpleValueType().getSizeInBits(), MaskLZ);
1241   KnownBits Known;
1242   DAG.computeKnownBits(X, Known);
1243   if (MaskedHighBits != Known.Zero) return true;
1244
1245   // We've identified a pattern that can be transformed into a single shift
1246   // and an addressing mode. Make it so.
1247   MVT VT = N.getSimpleValueType();
1248   if (ReplacingAnyExtend) {
1249     assert(X.getValueType() != VT);
1250     // We looked through an ANY_EXTEND node, insert a ZERO_EXTEND.
1251     SDValue NewX = DAG.getNode(ISD::ZERO_EXTEND, SDLoc(X), VT, X);
1252     insertDAGNode(DAG, N, NewX);
1253     X = NewX;
1254   }
1255   SDLoc DL(N);
1256   SDValue NewSRLAmt = DAG.getConstant(ShiftAmt + AMShiftAmt, DL, MVT::i8);
1257   SDValue NewSRL = DAG.getNode(ISD::SRL, DL, VT, X, NewSRLAmt);
1258   SDValue NewSHLAmt = DAG.getConstant(AMShiftAmt, DL, MVT::i8);
1259   SDValue NewSHL = DAG.getNode(ISD::SHL, DL, VT, NewSRL, NewSHLAmt);
1260
1261   // Insert the new nodes into the topological ordering. We must do this in
1262   // a valid topological ordering as nothing is going to go back and re-sort
1263   // these nodes. We continually insert before 'N' in sequence as this is
1264   // essentially a pre-flattened and pre-sorted sequence of nodes. There is no
1265   // hierarchy left to express.
1266   insertDAGNode(DAG, N, NewSRLAmt);
1267   insertDAGNode(DAG, N, NewSRL);
1268   insertDAGNode(DAG, N, NewSHLAmt);
1269   insertDAGNode(DAG, N, NewSHL);
1270   DAG.ReplaceAllUsesWith(N, NewSHL);
1271
1272   AM.Scale = 1 << AMShiftAmt;
1273   AM.IndexReg = NewSRL;
1274   return false;
1275 }
1276
1277 bool X86DAGToDAGISel::matchAddressRecursively(SDValue N, X86ISelAddressMode &AM,
1278                                               unsigned Depth) {
1279   SDLoc dl(N);
1280   LLVM_DEBUG({
1281     dbgs() << "MatchAddress: ";
1282     AM.dump(CurDAG);
1283   });
1284   // Limit recursion.
1285   if (Depth > 5)
1286     return matchAddressBase(N, AM);
1287
1288   // If this is already a %rip relative address, we can only merge immediates
1289   // into it.  Instead of handling this in every case, we handle it here.
1290   // RIP relative addressing: %rip + 32-bit displacement!
1291   if (AM.isRIPRelative()) {
1292     // FIXME: JumpTable and ExternalSymbol address currently don't like
1293     // displacements.  It isn't very important, but this should be fixed for
1294     // consistency.
1295     if (!(AM.ES || AM.MCSym) && AM.JT != -1)
1296       return true;
1297
1298     if (ConstantSDNode *Cst = dyn_cast<ConstantSDNode>(N))
1299       if (!foldOffsetIntoAddress(Cst->getSExtValue(), AM))
1300         return false;
1301     return true;
1302   }
1303
1304   switch (N.getOpcode()) {
1305   default: break;
1306   case ISD::LOCAL_RECOVER: {
1307     if (!AM.hasSymbolicDisplacement() && AM.Disp == 0)
1308       if (const auto *ESNode = dyn_cast<MCSymbolSDNode>(N.getOperand(0))) {
1309         // Use the symbol and don't prefix it.
1310         AM.MCSym = ESNode->getMCSymbol();
1311         return false;
1312       }
1313     break;
1314   }
1315   case ISD::Constant: {
1316     uint64_t Val = cast<ConstantSDNode>(N)->getSExtValue();
1317     if (!foldOffsetIntoAddress(Val, AM))
1318       return false;
1319     break;
1320   }
1321
1322   case X86ISD::Wrapper:
1323   case X86ISD::WrapperRIP:
1324     if (!matchWrapper(N, AM))
1325       return false;
1326     break;
1327
1328   case ISD::LOAD:
1329     if (!matchLoadInAddress(cast<LoadSDNode>(N), AM))
1330       return false;
1331     break;
1332
1333   case ISD::FrameIndex:
1334     if (AM.BaseType == X86ISelAddressMode::RegBase &&
1335         AM.Base_Reg.getNode() == nullptr &&
1336         (!Subtarget->is64Bit() || isDispSafeForFrameIndex(AM.Disp))) {
1337       AM.BaseType = X86ISelAddressMode::FrameIndexBase;
1338       AM.Base_FrameIndex = cast<FrameIndexSDNode>(N)->getIndex();
1339       return false;
1340     }
1341     break;
1342
1343   case ISD::SHL:
1344     if (AM.IndexReg.getNode() != nullptr || AM.Scale != 1)
1345       break;
1346
1347     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1348       unsigned Val = CN->getZExtValue();
1349       // Note that we handle x<<1 as (,x,2) rather than (x,x) here so
1350       // that the base operand remains free for further matching. If
1351       // the base doesn't end up getting used, a post-processing step
1352       // in MatchAddress turns (,x,2) into (x,x), which is cheaper.
1353       if (Val == 1 || Val == 2 || Val == 3) {
1354         AM.Scale = 1 << Val;
1355         SDValue ShVal = N.getOperand(0);
1356
1357         // Okay, we know that we have a scale by now.  However, if the scaled
1358         // value is an add of something and a constant, we can fold the
1359         // constant into the disp field here.
1360         if (CurDAG->isBaseWithConstantOffset(ShVal)) {
1361           AM.IndexReg = ShVal.getOperand(0);
1362           ConstantSDNode *AddVal = cast<ConstantSDNode>(ShVal.getOperand(1));
1363           uint64_t Disp = (uint64_t)AddVal->getSExtValue() << Val;
1364           if (!foldOffsetIntoAddress(Disp, AM))
1365             return false;
1366         }
1367
1368         AM.IndexReg = ShVal;
1369         return false;
1370       }
1371     }
1372     break;
1373
1374   case ISD::SRL: {
1375     // Scale must not be used already.
1376     if (AM.IndexReg.getNode() != nullptr || AM.Scale != 1) break;
1377
1378     SDValue And = N.getOperand(0);
1379     if (And.getOpcode() != ISD::AND) break;
1380     SDValue X = And.getOperand(0);
1381
1382     // We only handle up to 64-bit values here as those are what matter for
1383     // addressing mode optimizations.
1384     if (X.getSimpleValueType().getSizeInBits() > 64) break;
1385
1386     // The mask used for the transform is expected to be post-shift, but we
1387     // found the shift first so just apply the shift to the mask before passing
1388     // it down.
1389     if (!isa<ConstantSDNode>(N.getOperand(1)) ||
1390         !isa<ConstantSDNode>(And.getOperand(1)))
1391       break;
1392     uint64_t Mask = And.getConstantOperandVal(1) >> N.getConstantOperandVal(1);
1393
1394     // Try to fold the mask and shift into the scale, and return false if we
1395     // succeed.
1396     if (!foldMaskAndShiftToScale(*CurDAG, N, Mask, N, X, AM))
1397       return false;
1398     break;
1399   }
1400
1401   case ISD::SMUL_LOHI:
1402   case ISD::UMUL_LOHI:
1403     // A mul_lohi where we need the low part can be folded as a plain multiply.
1404     if (N.getResNo() != 0) break;
1405     LLVM_FALLTHROUGH;
1406   case ISD::MUL:
1407   case X86ISD::MUL_IMM:
1408     // X*[3,5,9] -> X+X*[2,4,8]
1409     if (AM.BaseType == X86ISelAddressMode::RegBase &&
1410         AM.Base_Reg.getNode() == nullptr &&
1411         AM.IndexReg.getNode() == nullptr) {
1412       if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1)))
1413         if (CN->getZExtValue() == 3 || CN->getZExtValue() == 5 ||
1414             CN->getZExtValue() == 9) {
1415           AM.Scale = unsigned(CN->getZExtValue())-1;
1416
1417           SDValue MulVal = N.getOperand(0);
1418           SDValue Reg;
1419
1420           // Okay, we know that we have a scale by now.  However, if the scaled
1421           // value is an add of something and a constant, we can fold the
1422           // constant into the disp field here.
1423           if (MulVal.getNode()->getOpcode() == ISD::ADD && MulVal.hasOneUse() &&
1424               isa<ConstantSDNode>(MulVal.getOperand(1))) {
1425             Reg = MulVal.getOperand(0);
1426             ConstantSDNode *AddVal =
1427               cast<ConstantSDNode>(MulVal.getOperand(1));
1428             uint64_t Disp = AddVal->getSExtValue() * CN->getZExtValue();
1429             if (foldOffsetIntoAddress(Disp, AM))
1430               Reg = N.getOperand(0);
1431           } else {
1432             Reg = N.getOperand(0);
1433           }
1434
1435           AM.IndexReg = AM.Base_Reg = Reg;
1436           return false;
1437         }
1438     }
1439     break;
1440
1441   case ISD::SUB: {
1442     // Given A-B, if A can be completely folded into the address and
1443     // the index field with the index field unused, use -B as the index.
1444     // This is a win if a has multiple parts that can be folded into
1445     // the address. Also, this saves a mov if the base register has
1446     // other uses, since it avoids a two-address sub instruction, however
1447     // it costs an additional mov if the index register has other uses.
1448
1449     // Add an artificial use to this node so that we can keep track of
1450     // it if it gets CSE'd with a different node.
1451     HandleSDNode Handle(N);
1452
1453     // Test if the LHS of the sub can be folded.
1454     X86ISelAddressMode Backup = AM;
1455     if (matchAddressRecursively(N.getOperand(0), AM, Depth+1)) {
1456       AM = Backup;
1457       break;
1458     }
1459     // Test if the index field is free for use.
1460     if (AM.IndexReg.getNode() || AM.isRIPRelative()) {
1461       AM = Backup;
1462       break;
1463     }
1464
1465     int Cost = 0;
1466     SDValue RHS = Handle.getValue().getOperand(1);
1467     // If the RHS involves a register with multiple uses, this
1468     // transformation incurs an extra mov, due to the neg instruction
1469     // clobbering its operand.
1470     if (!RHS.getNode()->hasOneUse() ||
1471         RHS.getNode()->getOpcode() == ISD::CopyFromReg ||
1472         RHS.getNode()->getOpcode() == ISD::TRUNCATE ||
1473         RHS.getNode()->getOpcode() == ISD::ANY_EXTEND ||
1474         (RHS.getNode()->getOpcode() == ISD::ZERO_EXTEND &&
1475          RHS.getOperand(0).getValueType() == MVT::i32))
1476       ++Cost;
1477     // If the base is a register with multiple uses, this
1478     // transformation may save a mov.
1479     // FIXME: Don't rely on DELETED_NODEs.
1480     if ((AM.BaseType == X86ISelAddressMode::RegBase && AM.Base_Reg.getNode() &&
1481          AM.Base_Reg->getOpcode() != ISD::DELETED_NODE &&
1482          !AM.Base_Reg.getNode()->hasOneUse()) ||
1483         AM.BaseType == X86ISelAddressMode::FrameIndexBase)
1484       --Cost;
1485     // If the folded LHS was interesting, this transformation saves
1486     // address arithmetic.
1487     if ((AM.hasSymbolicDisplacement() && !Backup.hasSymbolicDisplacement()) +
1488         ((AM.Disp != 0) && (Backup.Disp == 0)) +
1489         (AM.Segment.getNode() && !Backup.Segment.getNode()) >= 2)
1490       --Cost;
1491     // If it doesn't look like it may be an overall win, don't do it.
1492     if (Cost >= 0) {
1493       AM = Backup;
1494       break;
1495     }
1496
1497     // Ok, the transformation is legal and appears profitable. Go for it.
1498     SDValue Zero = CurDAG->getConstant(0, dl, N.getValueType());
1499     SDValue Neg = CurDAG->getNode(ISD::SUB, dl, N.getValueType(), Zero, RHS);
1500     AM.IndexReg = Neg;
1501     AM.Scale = 1;
1502
1503     // Insert the new nodes into the topological ordering.
1504     insertDAGNode(*CurDAG, Handle.getValue(), Zero);
1505     insertDAGNode(*CurDAG, Handle.getValue(), Neg);
1506     return false;
1507   }
1508
1509   case ISD::ADD:
1510     if (!matchAdd(N, AM, Depth))
1511       return false;
1512     break;
1513
1514   case ISD::OR:
1515     // We want to look through a transform in InstCombine and DAGCombiner that
1516     // turns 'add' into 'or', so we can treat this 'or' exactly like an 'add'.
1517     // Example: (or (and x, 1), (shl y, 3)) --> (add (and x, 1), (shl y, 3))
1518     // An 'lea' can then be used to match the shift (multiply) and add:
1519     // and $1, %esi
1520     // lea (%rsi, %rdi, 8), %rax
1521     if (CurDAG->haveNoCommonBitsSet(N.getOperand(0), N.getOperand(1)) &&
1522         !matchAdd(N, AM, Depth))
1523       return false;
1524     break;
1525
1526   case ISD::AND: {
1527     // Perform some heroic transforms on an and of a constant-count shift
1528     // with a constant to enable use of the scaled offset field.
1529
1530     // Scale must not be used already.
1531     if (AM.IndexReg.getNode() != nullptr || AM.Scale != 1) break;
1532
1533     SDValue Shift = N.getOperand(0);
1534     if (Shift.getOpcode() != ISD::SRL && Shift.getOpcode() != ISD::SHL) break;
1535     SDValue X = Shift.getOperand(0);
1536
1537     // We only handle up to 64-bit values here as those are what matter for
1538     // addressing mode optimizations.
1539     if (X.getSimpleValueType().getSizeInBits() > 64) break;
1540
1541     if (!isa<ConstantSDNode>(N.getOperand(1)))
1542       break;
1543     uint64_t Mask = N.getConstantOperandVal(1);
1544
1545     // Try to fold the mask and shift into an extract and scale.
1546     if (!foldMaskAndShiftToExtract(*CurDAG, N, Mask, Shift, X, AM))
1547       return false;
1548
1549     // Try to fold the mask and shift directly into the scale.
1550     if (!foldMaskAndShiftToScale(*CurDAG, N, Mask, Shift, X, AM))
1551       return false;
1552
1553     // Try to swap the mask and shift to place shifts which can be done as
1554     // a scale on the outside of the mask.
1555     if (!foldMaskedShiftToScaledMask(*CurDAG, N, Mask, Shift, X, AM))
1556       return false;
1557     break;
1558   }
1559   }
1560
1561   return matchAddressBase(N, AM);
1562 }
1563
1564 /// Helper for MatchAddress. Add the specified node to the
1565 /// specified addressing mode without any further recursion.
1566 bool X86DAGToDAGISel::matchAddressBase(SDValue N, X86ISelAddressMode &AM) {
1567   // Is the base register already occupied?
1568   if (AM.BaseType != X86ISelAddressMode::RegBase || AM.Base_Reg.getNode()) {
1569     // If so, check to see if the scale index register is set.
1570     if (!AM.IndexReg.getNode()) {
1571       AM.IndexReg = N;
1572       AM.Scale = 1;
1573       return false;
1574     }
1575
1576     // Otherwise, we cannot select it.
1577     return true;
1578   }
1579
1580   // Default, generate it as a register.
1581   AM.BaseType = X86ISelAddressMode::RegBase;
1582   AM.Base_Reg = N;
1583   return false;
1584 }
1585
1586 /// Helper for selectVectorAddr. Handles things that can be folded into a
1587 /// gather scatter address. The index register and scale should have already
1588 /// been handled.
1589 bool X86DAGToDAGISel::matchVectorAddress(SDValue N, X86ISelAddressMode &AM) {
1590   // TODO: Support other operations.
1591   switch (N.getOpcode()) {
1592   case ISD::Constant: {
1593     uint64_t Val = cast<ConstantSDNode>(N)->getSExtValue();
1594     if (!foldOffsetIntoAddress(Val, AM))
1595       return false;
1596     break;
1597   }
1598   case X86ISD::Wrapper:
1599     if (!matchWrapper(N, AM))
1600       return false;
1601     break;
1602   }
1603
1604   return matchAddressBase(N, AM);
1605 }
1606
1607 bool X86DAGToDAGISel::selectVectorAddr(SDNode *Parent, SDValue N, SDValue &Base,
1608                                        SDValue &Scale, SDValue &Index,
1609                                        SDValue &Disp, SDValue &Segment) {
1610   X86ISelAddressMode AM;
1611   auto *Mgs = cast<X86MaskedGatherScatterSDNode>(Parent);
1612   AM.IndexReg = Mgs->getIndex();
1613   AM.Scale = cast<ConstantSDNode>(Mgs->getScale())->getZExtValue();
1614
1615   unsigned AddrSpace = cast<MemSDNode>(Parent)->getPointerInfo().getAddrSpace();
1616   // AddrSpace 256 -> GS, 257 -> FS, 258 -> SS.
1617   if (AddrSpace == 256)
1618     AM.Segment = CurDAG->getRegister(X86::GS, MVT::i16);
1619   if (AddrSpace == 257)
1620     AM.Segment = CurDAG->getRegister(X86::FS, MVT::i16);
1621   if (AddrSpace == 258)
1622     AM.Segment = CurDAG->getRegister(X86::SS, MVT::i16);
1623
1624   // Try to match into the base and displacement fields.
1625   if (matchVectorAddress(N, AM))
1626     return false;
1627
1628   MVT VT = N.getSimpleValueType();
1629   if (AM.BaseType == X86ISelAddressMode::RegBase) {
1630     if (!AM.Base_Reg.getNode())
1631       AM.Base_Reg = CurDAG->getRegister(0, VT);
1632   }
1633
1634   getAddressOperands(AM, SDLoc(N), Base, Scale, Index, Disp, Segment);
1635   return true;
1636 }
1637
1638 /// Returns true if it is able to pattern match an addressing mode.
1639 /// It returns the operands which make up the maximal addressing mode it can
1640 /// match by reference.
1641 ///
1642 /// Parent is the parent node of the addr operand that is being matched.  It
1643 /// is always a load, store, atomic node, or null.  It is only null when
1644 /// checking memory operands for inline asm nodes.
1645 bool X86DAGToDAGISel::selectAddr(SDNode *Parent, SDValue N, SDValue &Base,
1646                                  SDValue &Scale, SDValue &Index,
1647                                  SDValue &Disp, SDValue &Segment) {
1648   X86ISelAddressMode AM;
1649
1650   if (Parent &&
1651       // This list of opcodes are all the nodes that have an "addr:$ptr" operand
1652       // that are not a MemSDNode, and thus don't have proper addrspace info.
1653       Parent->getOpcode() != ISD::INTRINSIC_W_CHAIN && // unaligned loads, fixme
1654       Parent->getOpcode() != ISD::INTRINSIC_VOID && // nontemporal stores
1655       Parent->getOpcode() != X86ISD::TLSCALL && // Fixme
1656       Parent->getOpcode() != X86ISD::EH_SJLJ_SETJMP && // setjmp
1657       Parent->getOpcode() != X86ISD::EH_SJLJ_LONGJMP) { // longjmp
1658     unsigned AddrSpace =
1659       cast<MemSDNode>(Parent)->getPointerInfo().getAddrSpace();
1660     // AddrSpace 256 -> GS, 257 -> FS, 258 -> SS.
1661     if (AddrSpace == 256)
1662       AM.Segment = CurDAG->getRegister(X86::GS, MVT::i16);
1663     if (AddrSpace == 257)
1664       AM.Segment = CurDAG->getRegister(X86::FS, MVT::i16);
1665     if (AddrSpace == 258)
1666       AM.Segment = CurDAG->getRegister(X86::SS, MVT::i16);
1667   }
1668
1669   if (matchAddress(N, AM))
1670     return false;
1671
1672   MVT VT = N.getSimpleValueType();
1673   if (AM.BaseType == X86ISelAddressMode::RegBase) {
1674     if (!AM.Base_Reg.getNode())
1675       AM.Base_Reg = CurDAG->getRegister(0, VT);
1676   }
1677
1678   if (!AM.IndexReg.getNode())
1679     AM.IndexReg = CurDAG->getRegister(0, VT);
1680
1681   getAddressOperands(AM, SDLoc(N), Base, Scale, Index, Disp, Segment);
1682   return true;
1683 }
1684
1685 // We can only fold a load if all nodes between it and the root node have a
1686 // single use. If there are additional uses, we could end up duplicating the
1687 // load.
1688 static bool hasSingleUsesFromRoot(SDNode *Root, SDNode *User) {
1689   while (User != Root) {
1690     if (!User->hasOneUse())
1691       return false;
1692     User = *User->use_begin();
1693   }
1694
1695   return true;
1696 }
1697
1698 /// Match a scalar SSE load. In particular, we want to match a load whose top
1699 /// elements are either undef or zeros. The load flavor is derived from the
1700 /// type of N, which is either v4f32 or v2f64.
1701 ///
1702 /// We also return:
1703 ///   PatternChainNode: this is the matched node that has a chain input and
1704 ///   output.
1705 bool X86DAGToDAGISel::selectScalarSSELoad(SDNode *Root, SDNode *Parent,
1706                                           SDValue N, SDValue &Base,
1707                                           SDValue &Scale, SDValue &Index,
1708                                           SDValue &Disp, SDValue &Segment,
1709                                           SDValue &PatternNodeWithChain) {
1710   if (!hasSingleUsesFromRoot(Root, Parent))
1711     return false;
1712
1713   // We can allow a full vector load here since narrowing a load is ok.
1714   if (ISD::isNON_EXTLoad(N.getNode())) {
1715     PatternNodeWithChain = N;
1716     if (IsProfitableToFold(PatternNodeWithChain, N.getNode(), Root) &&
1717         IsLegalToFold(PatternNodeWithChain, Parent, Root, OptLevel)) {
1718       LoadSDNode *LD = cast<LoadSDNode>(PatternNodeWithChain);
1719       return selectAddr(LD, LD->getBasePtr(), Base, Scale, Index, Disp,
1720                         Segment);
1721     }
1722   }
1723
1724   // We can also match the special zero extended load opcode.
1725   if (N.getOpcode() == X86ISD::VZEXT_LOAD) {
1726     PatternNodeWithChain = N;
1727     if (IsProfitableToFold(PatternNodeWithChain, N.getNode(), Root) &&
1728         IsLegalToFold(PatternNodeWithChain, Parent, Root, OptLevel)) {
1729       auto *MI = cast<MemIntrinsicSDNode>(PatternNodeWithChain);
1730       return selectAddr(MI, MI->getBasePtr(), Base, Scale, Index, Disp,
1731                         Segment);
1732     }
1733   }
1734
1735   // Need to make sure that the SCALAR_TO_VECTOR and load are both only used
1736   // once. Otherwise the load might get duplicated and the chain output of the
1737   // duplicate load will not be observed by all dependencies.
1738   if (N.getOpcode() == ISD::SCALAR_TO_VECTOR && N.getNode()->hasOneUse()) {
1739     PatternNodeWithChain = N.getOperand(0);
1740     if (ISD::isNON_EXTLoad(PatternNodeWithChain.getNode()) &&
1741         IsProfitableToFold(PatternNodeWithChain, N.getNode(), Root) &&
1742         IsLegalToFold(PatternNodeWithChain, N.getNode(), Root, OptLevel)) {
1743       LoadSDNode *LD = cast<LoadSDNode>(PatternNodeWithChain);
1744       return selectAddr(LD, LD->getBasePtr(), Base, Scale, Index, Disp,
1745                         Segment);
1746     }
1747   }
1748
1749   // Also handle the case where we explicitly require zeros in the top
1750   // elements.  This is a vector shuffle from the zero vector.
1751   if (N.getOpcode() == X86ISD::VZEXT_MOVL && N.getNode()->hasOneUse() &&
1752       // Check to see if the top elements are all zeros (or bitcast of zeros).
1753       N.getOperand(0).getOpcode() == ISD::SCALAR_TO_VECTOR &&
1754       N.getOperand(0).getNode()->hasOneUse()) {
1755     PatternNodeWithChain = N.getOperand(0).getOperand(0);
1756     if (ISD::isNON_EXTLoad(PatternNodeWithChain.getNode()) &&
1757         IsProfitableToFold(PatternNodeWithChain, N.getNode(), Root) &&
1758         IsLegalToFold(PatternNodeWithChain, N.getNode(), Root, OptLevel)) {
1759       // Okay, this is a zero extending load.  Fold it.
1760       LoadSDNode *LD = cast<LoadSDNode>(PatternNodeWithChain);
1761       return selectAddr(LD, LD->getBasePtr(), Base, Scale, Index, Disp,
1762                         Segment);
1763     }
1764   }
1765
1766   return false;
1767 }
1768
1769
1770 bool X86DAGToDAGISel::selectMOV64Imm32(SDValue N, SDValue &Imm) {
1771   if (const ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N)) {
1772     uint64_t ImmVal = CN->getZExtValue();
1773     if (!isUInt<32>(ImmVal))
1774       return false;
1775
1776     Imm = CurDAG->getTargetConstant(ImmVal, SDLoc(N), MVT::i64);
1777     return true;
1778   }
1779
1780   // In static codegen with small code model, we can get the address of a label
1781   // into a register with 'movl'
1782   if (N->getOpcode() != X86ISD::Wrapper)
1783     return false;
1784
1785   N = N.getOperand(0);
1786
1787   // At least GNU as does not accept 'movl' for TPOFF relocations.
1788   // FIXME: We could use 'movl' when we know we are targeting MC.
1789   if (N->getOpcode() == ISD::TargetGlobalTLSAddress)
1790     return false;
1791
1792   Imm = N;
1793   if (N->getOpcode() != ISD::TargetGlobalAddress)
1794     return TM.getCodeModel() == CodeModel::Small;
1795
1796   Optional<ConstantRange> CR =
1797       cast<GlobalAddressSDNode>(N)->getGlobal()->getAbsoluteSymbolRange();
1798   if (!CR)
1799     return TM.getCodeModel() == CodeModel::Small;
1800
1801   return CR->getUnsignedMax().ult(1ull << 32);
1802 }
1803
1804 bool X86DAGToDAGISel::selectLEA64_32Addr(SDValue N, SDValue &Base,
1805                                          SDValue &Scale, SDValue &Index,
1806                                          SDValue &Disp, SDValue &Segment) {
1807   // Save the debug loc before calling selectLEAAddr, in case it invalidates N.
1808   SDLoc DL(N);
1809
1810   if (!selectLEAAddr(N, Base, Scale, Index, Disp, Segment))
1811     return false;
1812
1813   RegisterSDNode *RN = dyn_cast<RegisterSDNode>(Base);
1814   if (RN && RN->getReg() == 0)
1815     Base = CurDAG->getRegister(0, MVT::i64);
1816   else if (Base.getValueType() == MVT::i32 && !dyn_cast<FrameIndexSDNode>(Base)) {
1817     // Base could already be %rip, particularly in the x32 ABI.
1818     Base = SDValue(CurDAG->getMachineNode(
1819                        TargetOpcode::SUBREG_TO_REG, DL, MVT::i64,
1820                        CurDAG->getTargetConstant(0, DL, MVT::i64),
1821                        Base,
1822                        CurDAG->getTargetConstant(X86::sub_32bit, DL, MVT::i32)),
1823                    0);
1824   }
1825
1826   RN = dyn_cast<RegisterSDNode>(Index);
1827   if (RN && RN->getReg() == 0)
1828     Index = CurDAG->getRegister(0, MVT::i64);
1829   else {
1830     assert(Index.getValueType() == MVT::i32 &&
1831            "Expect to be extending 32-bit registers for use in LEA");
1832     Index = SDValue(CurDAG->getMachineNode(
1833                         TargetOpcode::SUBREG_TO_REG, DL, MVT::i64,
1834                         CurDAG->getTargetConstant(0, DL, MVT::i64),
1835                         Index,
1836                         CurDAG->getTargetConstant(X86::sub_32bit, DL,
1837                                                   MVT::i32)),
1838                     0);
1839   }
1840
1841   return true;
1842 }
1843
1844 /// Calls SelectAddr and determines if the maximal addressing
1845 /// mode it matches can be cost effectively emitted as an LEA instruction.
1846 bool X86DAGToDAGISel::selectLEAAddr(SDValue N,
1847                                     SDValue &Base, SDValue &Scale,
1848                                     SDValue &Index, SDValue &Disp,
1849                                     SDValue &Segment) {
1850   X86ISelAddressMode AM;
1851
1852   // Save the DL and VT before calling matchAddress, it can invalidate N.
1853   SDLoc DL(N);
1854   MVT VT = N.getSimpleValueType();
1855
1856   // Set AM.Segment to prevent MatchAddress from using one. LEA doesn't support
1857   // segments.
1858   SDValue Copy = AM.Segment;
1859   SDValue T = CurDAG->getRegister(0, MVT::i32);
1860   AM.Segment = T;
1861   if (matchAddress(N, AM))
1862     return false;
1863   assert (T == AM.Segment);
1864   AM.Segment = Copy;
1865
1866   unsigned Complexity = 0;
1867   if (AM.BaseType == X86ISelAddressMode::RegBase)
1868     if (AM.Base_Reg.getNode())
1869       Complexity = 1;
1870     else
1871       AM.Base_Reg = CurDAG->getRegister(0, VT);
1872   else if (AM.BaseType == X86ISelAddressMode::FrameIndexBase)
1873     Complexity = 4;
1874
1875   if (AM.IndexReg.getNode())
1876     Complexity++;
1877   else
1878     AM.IndexReg = CurDAG->getRegister(0, VT);
1879
1880   // Don't match just leal(,%reg,2). It's cheaper to do addl %reg, %reg, or with
1881   // a simple shift.
1882   if (AM.Scale > 1)
1883     Complexity++;
1884
1885   // FIXME: We are artificially lowering the criteria to turn ADD %reg, $GA
1886   // to a LEA. This is determined with some experimentation but is by no means
1887   // optimal (especially for code size consideration). LEA is nice because of
1888   // its three-address nature. Tweak the cost function again when we can run
1889   // convertToThreeAddress() at register allocation time.
1890   if (AM.hasSymbolicDisplacement()) {
1891     // For X86-64, always use LEA to materialize RIP-relative addresses.
1892     if (Subtarget->is64Bit())
1893       Complexity = 4;
1894     else
1895       Complexity += 2;
1896   }
1897
1898   if (AM.Disp && (AM.Base_Reg.getNode() || AM.IndexReg.getNode()))
1899     Complexity++;
1900
1901   // If it isn't worth using an LEA, reject it.
1902   if (Complexity <= 2)
1903     return false;
1904
1905   getAddressOperands(AM, DL, Base, Scale, Index, Disp, Segment);
1906   return true;
1907 }
1908
1909 /// This is only run on TargetGlobalTLSAddress nodes.
1910 bool X86DAGToDAGISel::selectTLSADDRAddr(SDValue N, SDValue &Base,
1911                                         SDValue &Scale, SDValue &Index,
1912                                         SDValue &Disp, SDValue &Segment) {
1913   assert(N.getOpcode() == ISD::TargetGlobalTLSAddress);
1914   const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
1915
1916   X86ISelAddressMode AM;
1917   AM.GV = GA->getGlobal();
1918   AM.Disp += GA->getOffset();
1919   AM.Base_Reg = CurDAG->getRegister(0, N.getValueType());
1920   AM.SymbolFlags = GA->getTargetFlags();
1921
1922   if (N.getValueType() == MVT::i32) {
1923     AM.Scale = 1;
1924     AM.IndexReg = CurDAG->getRegister(X86::EBX, MVT::i32);
1925   } else {
1926     AM.IndexReg = CurDAG->getRegister(0, MVT::i64);
1927   }
1928
1929   getAddressOperands(AM, SDLoc(N), Base, Scale, Index, Disp, Segment);
1930   return true;
1931 }
1932
1933 bool X86DAGToDAGISel::selectRelocImm(SDValue N, SDValue &Op) {
1934   if (auto *CN = dyn_cast<ConstantSDNode>(N)) {
1935     Op = CurDAG->getTargetConstant(CN->getAPIntValue(), SDLoc(CN),
1936                                    N.getValueType());
1937     return true;
1938   }
1939
1940   // Keep track of the original value type and whether this value was
1941   // truncated. If we see a truncation from pointer type to VT that truncates
1942   // bits that are known to be zero, we can use a narrow reference.
1943   EVT VT = N.getValueType();
1944   bool WasTruncated = false;
1945   if (N.getOpcode() == ISD::TRUNCATE) {
1946     WasTruncated = true;
1947     N = N.getOperand(0);
1948   }
1949
1950   if (N.getOpcode() != X86ISD::Wrapper)
1951     return false;
1952
1953   // We can only use non-GlobalValues as immediates if they were not truncated,
1954   // as we do not have any range information. If we have a GlobalValue and the
1955   // address was not truncated, we can select it as an operand directly.
1956   unsigned Opc = N.getOperand(0)->getOpcode();
1957   if (Opc != ISD::TargetGlobalAddress || !WasTruncated) {
1958     Op = N.getOperand(0);
1959     // We can only select the operand directly if we didn't have to look past a
1960     // truncate.
1961     return !WasTruncated;
1962   }
1963
1964   // Check that the global's range fits into VT.
1965   auto *GA = cast<GlobalAddressSDNode>(N.getOperand(0));
1966   Optional<ConstantRange> CR = GA->getGlobal()->getAbsoluteSymbolRange();
1967   if (!CR || CR->getUnsignedMax().uge(1ull << VT.getSizeInBits()))
1968     return false;
1969
1970   // Okay, we can use a narrow reference.
1971   Op = CurDAG->getTargetGlobalAddress(GA->getGlobal(), SDLoc(N), VT,
1972                                       GA->getOffset(), GA->getTargetFlags());
1973   return true;
1974 }
1975
1976 bool X86DAGToDAGISel::tryFoldLoad(SDNode *Root, SDNode *P, SDValue N,
1977                                   SDValue &Base, SDValue &Scale,
1978                                   SDValue &Index, SDValue &Disp,
1979                                   SDValue &Segment) {
1980   if (!ISD::isNON_EXTLoad(N.getNode()) ||
1981       !IsProfitableToFold(N, P, Root) ||
1982       !IsLegalToFold(N, P, Root, OptLevel))
1983     return false;
1984
1985   return selectAddr(N.getNode(),
1986                     N.getOperand(1), Base, Scale, Index, Disp, Segment);
1987 }
1988
1989 bool X86DAGToDAGISel::tryFoldVecLoad(SDNode *Root, SDNode *P, SDValue N,
1990                                      SDValue &Base, SDValue &Scale,
1991                                      SDValue &Index, SDValue &Disp,
1992                                      SDValue &Segment) {
1993   if (!ISD::isNON_EXTLoad(N.getNode()) ||
1994       useNonTemporalLoad(cast<LoadSDNode>(N)) ||
1995       !IsProfitableToFold(N, P, Root) ||
1996       !IsLegalToFold(N, P, Root, OptLevel))
1997     return false;
1998
1999   return selectAddr(N.getNode(),
2000                     N.getOperand(1), Base, Scale, Index, Disp, Segment);
2001 }
2002
2003 /// Return an SDNode that returns the value of the global base register.
2004 /// Output instructions required to initialize the global base register,
2005 /// if necessary.
2006 SDNode *X86DAGToDAGISel::getGlobalBaseReg() {
2007   unsigned GlobalBaseReg = getInstrInfo()->getGlobalBaseReg(MF);
2008   auto &DL = MF->getDataLayout();
2009   return CurDAG->getRegister(GlobalBaseReg, TLI->getPointerTy(DL)).getNode();
2010 }
2011
2012 bool X86DAGToDAGISel::isSExtAbsoluteSymbolRef(unsigned Width, SDNode *N) const {
2013   if (N->getOpcode() == ISD::TRUNCATE)
2014     N = N->getOperand(0).getNode();
2015   if (N->getOpcode() != X86ISD::Wrapper)
2016     return false;
2017
2018   auto *GA = dyn_cast<GlobalAddressSDNode>(N->getOperand(0));
2019   if (!GA)
2020     return false;
2021
2022   Optional<ConstantRange> CR = GA->getGlobal()->getAbsoluteSymbolRange();
2023   return CR && CR->getSignedMin().sge(-1ull << Width) &&
2024          CR->getSignedMax().slt(1ull << Width);
2025 }
2026
2027 /// Test whether the given X86ISD::CMP node has any uses which require the SF
2028 /// or OF bits to be accurate.
2029 static bool hasNoSignedComparisonUses(SDNode *N) {
2030   // Examine each user of the node.
2031   for (SDNode::use_iterator UI = N->use_begin(),
2032          UE = N->use_end(); UI != UE; ++UI) {
2033     // Only examine CopyToReg uses.
2034     if (UI->getOpcode() != ISD::CopyToReg)
2035       return false;
2036     // Only examine CopyToReg uses that copy to EFLAGS.
2037     if (cast<RegisterSDNode>(UI->getOperand(1))->getReg() !=
2038           X86::EFLAGS)
2039       return false;
2040     // Examine each user of the CopyToReg use.
2041     for (SDNode::use_iterator FlagUI = UI->use_begin(),
2042            FlagUE = UI->use_end(); FlagUI != FlagUE; ++FlagUI) {
2043       // Only examine the Flag result.
2044       if (FlagUI.getUse().getResNo() != 1) continue;
2045       // Anything unusual: assume conservatively.
2046       if (!FlagUI->isMachineOpcode()) return false;
2047       // Examine the opcode of the user.
2048       switch (FlagUI->getMachineOpcode()) {
2049       // These comparisons don't treat the most significant bit specially.
2050       case X86::SETAr: case X86::SETAEr: case X86::SETBr: case X86::SETBEr:
2051       case X86::SETEr: case X86::SETNEr: case X86::SETPr: case X86::SETNPr:
2052       case X86::SETAm: case X86::SETAEm: case X86::SETBm: case X86::SETBEm:
2053       case X86::SETEm: case X86::SETNEm: case X86::SETPm: case X86::SETNPm:
2054       case X86::JA_1: case X86::JAE_1: case X86::JB_1: case X86::JBE_1:
2055       case X86::JE_1: case X86::JNE_1: case X86::JP_1: case X86::JNP_1:
2056       case X86::CMOVA16rr: case X86::CMOVA16rm:
2057       case X86::CMOVA32rr: case X86::CMOVA32rm:
2058       case X86::CMOVA64rr: case X86::CMOVA64rm:
2059       case X86::CMOVAE16rr: case X86::CMOVAE16rm:
2060       case X86::CMOVAE32rr: case X86::CMOVAE32rm:
2061       case X86::CMOVAE64rr: case X86::CMOVAE64rm:
2062       case X86::CMOVB16rr: case X86::CMOVB16rm:
2063       case X86::CMOVB32rr: case X86::CMOVB32rm:
2064       case X86::CMOVB64rr: case X86::CMOVB64rm:
2065       case X86::CMOVBE16rr: case X86::CMOVBE16rm:
2066       case X86::CMOVBE32rr: case X86::CMOVBE32rm:
2067       case X86::CMOVBE64rr: case X86::CMOVBE64rm:
2068       case X86::CMOVE16rr: case X86::CMOVE16rm:
2069       case X86::CMOVE32rr: case X86::CMOVE32rm:
2070       case X86::CMOVE64rr: case X86::CMOVE64rm:
2071       case X86::CMOVNE16rr: case X86::CMOVNE16rm:
2072       case X86::CMOVNE32rr: case X86::CMOVNE32rm:
2073       case X86::CMOVNE64rr: case X86::CMOVNE64rm:
2074       case X86::CMOVNP16rr: case X86::CMOVNP16rm:
2075       case X86::CMOVNP32rr: case X86::CMOVNP32rm:
2076       case X86::CMOVNP64rr: case X86::CMOVNP64rm:
2077       case X86::CMOVP16rr: case X86::CMOVP16rm:
2078       case X86::CMOVP32rr: case X86::CMOVP32rm:
2079       case X86::CMOVP64rr: case X86::CMOVP64rm:
2080         continue;
2081       // Anything else: assume conservatively.
2082       default: return false;
2083       }
2084     }
2085   }
2086   return true;
2087 }
2088
2089 /// Test whether the given node which sets flags has any uses which require the
2090 /// CF flag to be accurate.
2091 static bool hasNoCarryFlagUses(SDNode *N) {
2092   // Examine each user of the node.
2093   for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end(); UI != UE;
2094        ++UI) {
2095     // Only check things that use the flags.
2096     if (UI.getUse().getResNo() != 1)
2097       continue;
2098     // Only examine CopyToReg uses.
2099     if (UI->getOpcode() != ISD::CopyToReg)
2100       return false;
2101     // Only examine CopyToReg uses that copy to EFLAGS.
2102     if (cast<RegisterSDNode>(UI->getOperand(1))->getReg() != X86::EFLAGS)
2103       return false;
2104     // Examine each user of the CopyToReg use.
2105     for (SDNode::use_iterator FlagUI = UI->use_begin(), FlagUE = UI->use_end();
2106          FlagUI != FlagUE; ++FlagUI) {
2107       // Only examine the Flag result.
2108       if (FlagUI.getUse().getResNo() != 1)
2109         continue;
2110       // Anything unusual: assume conservatively.
2111       if (!FlagUI->isMachineOpcode())
2112         return false;
2113       // Examine the opcode of the user.
2114       switch (FlagUI->getMachineOpcode()) {
2115       // Comparisons which don't examine the CF flag.
2116       case X86::SETOr: case X86::SETNOr: case X86::SETEr: case X86::SETNEr:
2117       case X86::SETSr: case X86::SETNSr: case X86::SETPr: case X86::SETNPr:
2118       case X86::SETLr: case X86::SETGEr: case X86::SETLEr: case X86::SETGr:
2119       case X86::JO_1: case X86::JNO_1: case X86::JE_1: case X86::JNE_1:
2120       case X86::JS_1: case X86::JNS_1: case X86::JP_1: case X86::JNP_1:
2121       case X86::JL_1: case X86::JGE_1: case X86::JLE_1: case X86::JG_1:
2122       case X86::CMOVO16rr: case X86::CMOVO32rr: case X86::CMOVO64rr:
2123       case X86::CMOVO16rm: case X86::CMOVO32rm: case X86::CMOVO64rm:
2124       case X86::CMOVNO16rr: case X86::CMOVNO32rr: case X86::CMOVNO64rr:
2125       case X86::CMOVNO16rm: case X86::CMOVNO32rm: case X86::CMOVNO64rm:
2126       case X86::CMOVE16rr: case X86::CMOVE32rr: case X86::CMOVE64rr:
2127       case X86::CMOVE16rm: case X86::CMOVE32rm: case X86::CMOVE64rm:
2128       case X86::CMOVNE16rr: case X86::CMOVNE32rr: case X86::CMOVNE64rr:
2129       case X86::CMOVNE16rm: case X86::CMOVNE32rm: case X86::CMOVNE64rm:
2130       case X86::CMOVS16rr: case X86::CMOVS32rr: case X86::CMOVS64rr:
2131       case X86::CMOVS16rm: case X86::CMOVS32rm: case X86::CMOVS64rm:
2132       case X86::CMOVNS16rr: case X86::CMOVNS32rr: case X86::CMOVNS64rr:
2133       case X86::CMOVNS16rm: case X86::CMOVNS32rm: case X86::CMOVNS64rm:
2134       case X86::CMOVP16rr: case X86::CMOVP32rr: case X86::CMOVP64rr:
2135       case X86::CMOVP16rm: case X86::CMOVP32rm: case X86::CMOVP64rm:
2136       case X86::CMOVNP16rr: case X86::CMOVNP32rr: case X86::CMOVNP64rr:
2137       case X86::CMOVNP16rm: case X86::CMOVNP32rm: case X86::CMOVNP64rm:
2138       case X86::CMOVL16rr: case X86::CMOVL32rr: case X86::CMOVL64rr:
2139       case X86::CMOVL16rm: case X86::CMOVL32rm: case X86::CMOVL64rm:
2140       case X86::CMOVGE16rr: case X86::CMOVGE32rr: case X86::CMOVGE64rr:
2141       case X86::CMOVGE16rm: case X86::CMOVGE32rm: case X86::CMOVGE64rm:
2142       case X86::CMOVLE16rr: case X86::CMOVLE32rr: case X86::CMOVLE64rr:
2143       case X86::CMOVLE16rm: case X86::CMOVLE32rm: case X86::CMOVLE64rm:
2144       case X86::CMOVG16rr: case X86::CMOVG32rr: case X86::CMOVG64rr:
2145       case X86::CMOVG16rm: case X86::CMOVG32rm: case X86::CMOVG64rm:
2146         continue;
2147       // Anything else: assume conservatively.
2148       default:
2149         return false;
2150       }
2151     }
2152   }
2153   return true;
2154 }
2155
2156 /// Check whether or not the chain ending in StoreNode is suitable for doing
2157 /// the {load; op; store} to modify transformation.
2158 static bool isFusableLoadOpStorePattern(StoreSDNode *StoreNode,
2159                                         SDValue StoredVal, SelectionDAG *CurDAG,
2160                                         LoadSDNode *&LoadNode,
2161                                         SDValue &InputChain) {
2162   // is the stored value result 0 of the load?
2163   if (StoredVal.getResNo() != 0) return false;
2164
2165   // are there other uses of the loaded value than the inc or dec?
2166   if (!StoredVal.getNode()->hasNUsesOfValue(1, 0)) return false;
2167
2168   // is the store non-extending and non-indexed?
2169   if (!ISD::isNormalStore(StoreNode) || StoreNode->isNonTemporal())
2170     return false;
2171
2172   SDValue Load = StoredVal->getOperand(0);
2173   // Is the stored value a non-extending and non-indexed load?
2174   if (!ISD::isNormalLoad(Load.getNode())) return false;
2175
2176   // Return LoadNode by reference.
2177   LoadNode = cast<LoadSDNode>(Load);
2178
2179   // Is store the only read of the loaded value?
2180   if (!Load.hasOneUse())
2181     return false;
2182
2183   // Is the address of the store the same as the load?
2184   if (LoadNode->getBasePtr() != StoreNode->getBasePtr() ||
2185       LoadNode->getOffset() != StoreNode->getOffset())
2186     return false;
2187
2188   bool FoundLoad = false;
2189   SmallVector<SDValue, 4> ChainOps;
2190   SmallVector<const SDNode *, 4> LoopWorklist;
2191   SmallPtrSet<const SDNode *, 16> Visited;
2192   const unsigned int Max = 1024;
2193
2194   //  Visualization of Load-Op-Store fusion:
2195   // -------------------------
2196   // Legend:
2197   //    *-lines = Chain operand dependencies.
2198   //    |-lines = Normal operand dependencies.
2199   //    Dependencies flow down and right. n-suffix references multiple nodes.
2200   //
2201   //        C                        Xn  C
2202   //        *                         *  *
2203   //        *                          * *
2204   //  Xn  A-LD    Yn                    TF         Yn
2205   //   *    * \   |                       *        |
2206   //    *   *  \  |                        *       |
2207   //     *  *   \ |             =>       A--LD_OP_ST
2208   //      * *    \|                                 \
2209   //       TF    OP                                  \
2210   //         *   | \                                  Zn
2211   //          *  |  \
2212   //         A-ST    Zn
2213   //
2214
2215   // This merge induced dependences from: #1: Xn -> LD, OP, Zn
2216   //                                      #2: Yn -> LD
2217   //                                      #3: ST -> Zn
2218
2219   // Ensure the transform is safe by checking for the dual
2220   // dependencies to make sure we do not induce a loop.
2221
2222   // As LD is a predecessor to both OP and ST we can do this by checking:
2223   //  a). if LD is a predecessor to a member of Xn or Yn.
2224   //  b). if a Zn is a predecessor to ST.
2225
2226   // However, (b) can only occur through being a chain predecessor to
2227   // ST, which is the same as Zn being a member or predecessor of Xn,
2228   // which is a subset of LD being a predecessor of Xn. So it's
2229   // subsumed by check (a).
2230
2231   SDValue Chain = StoreNode->getChain();
2232
2233   // Gather X elements in ChainOps.
2234   if (Chain == Load.getValue(1)) {
2235     FoundLoad = true;
2236     ChainOps.push_back(Load.getOperand(0));
2237   } else if (Chain.getOpcode() == ISD::TokenFactor) {
2238     for (unsigned i = 0, e = Chain.getNumOperands(); i != e; ++i) {
2239       SDValue Op = Chain.getOperand(i);
2240       if (Op == Load.getValue(1)) {
2241         FoundLoad = true;
2242         // Drop Load, but keep its chain. No cycle check necessary.
2243         ChainOps.push_back(Load.getOperand(0));
2244         continue;
2245       }
2246       LoopWorklist.push_back(Op.getNode());
2247       ChainOps.push_back(Op);
2248     }
2249   }
2250
2251   if (!FoundLoad)
2252     return false;
2253
2254   // Worklist is currently Xn. Add Yn to worklist.
2255   for (SDValue Op : StoredVal->ops())
2256     if (Op.getNode() != LoadNode)
2257       LoopWorklist.push_back(Op.getNode());
2258
2259   // Check (a) if Load is a predecessor to Xn + Yn
2260   if (SDNode::hasPredecessorHelper(Load.getNode(), Visited, LoopWorklist, Max,
2261                                    true))
2262     return false;
2263
2264   InputChain =
2265       CurDAG->getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ChainOps);
2266   return true;
2267 }
2268
2269 // Change a chain of {load; op; store} of the same value into a simple op
2270 // through memory of that value, if the uses of the modified value and its
2271 // address are suitable.
2272 //
2273 // The tablegen pattern memory operand pattern is currently not able to match
2274 // the case where the EFLAGS on the original operation are used.
2275 //
2276 // To move this to tablegen, we'll need to improve tablegen to allow flags to
2277 // be transferred from a node in the pattern to the result node, probably with
2278 // a new keyword. For example, we have this
2279 // def DEC64m : RI<0xFF, MRM1m, (outs), (ins i64mem:$dst), "dec{q}\t$dst",
2280 //  [(store (add (loadi64 addr:$dst), -1), addr:$dst),
2281 //   (implicit EFLAGS)]>;
2282 // but maybe need something like this
2283 // def DEC64m : RI<0xFF, MRM1m, (outs), (ins i64mem:$dst), "dec{q}\t$dst",
2284 //  [(store (add (loadi64 addr:$dst), -1), addr:$dst),
2285 //   (transferrable EFLAGS)]>;
2286 //
2287 // Until then, we manually fold these and instruction select the operation
2288 // here.
2289 bool X86DAGToDAGISel::foldLoadStoreIntoMemOperand(SDNode *Node) {
2290   StoreSDNode *StoreNode = cast<StoreSDNode>(Node);
2291   SDValue StoredVal = StoreNode->getOperand(1);
2292   unsigned Opc = StoredVal->getOpcode();
2293
2294   // Before we try to select anything, make sure this is memory operand size
2295   // and opcode we can handle. Note that this must match the code below that
2296   // actually lowers the opcodes.
2297   EVT MemVT = StoreNode->getMemoryVT();
2298   if (MemVT != MVT::i64 && MemVT != MVT::i32 && MemVT != MVT::i16 &&
2299       MemVT != MVT::i8)
2300     return false;
2301   switch (Opc) {
2302   default:
2303     return false;
2304   case X86ISD::INC:
2305   case X86ISD::DEC:
2306   case X86ISD::ADD:
2307   case X86ISD::ADC:
2308   case X86ISD::SUB:
2309   case X86ISD::SBB:
2310   case X86ISD::AND:
2311   case X86ISD::OR:
2312   case X86ISD::XOR:
2313     break;
2314   }
2315
2316   LoadSDNode *LoadNode = nullptr;
2317   SDValue InputChain;
2318   if (!isFusableLoadOpStorePattern(StoreNode, StoredVal, CurDAG, LoadNode,
2319                                    InputChain))
2320     return false;
2321
2322   SDValue Base, Scale, Index, Disp, Segment;
2323   if (!selectAddr(LoadNode, LoadNode->getBasePtr(), Base, Scale, Index, Disp,
2324                   Segment))
2325     return false;
2326
2327   auto SelectOpcode = [&](unsigned Opc64, unsigned Opc32, unsigned Opc16,
2328                           unsigned Opc8) {
2329     switch (MemVT.getSimpleVT().SimpleTy) {
2330     case MVT::i64:
2331       return Opc64;
2332     case MVT::i32:
2333       return Opc32;
2334     case MVT::i16:
2335       return Opc16;
2336     case MVT::i8:
2337       return Opc8;
2338     default:
2339       llvm_unreachable("Invalid size!");
2340     }
2341   };
2342
2343   MachineSDNode *Result;
2344   switch (Opc) {
2345   case X86ISD::INC:
2346   case X86ISD::DEC: {
2347     unsigned NewOpc =
2348         Opc == X86ISD::INC
2349             ? SelectOpcode(X86::INC64m, X86::INC32m, X86::INC16m, X86::INC8m)
2350             : SelectOpcode(X86::DEC64m, X86::DEC32m, X86::DEC16m, X86::DEC8m);
2351     const SDValue Ops[] = {Base, Scale, Index, Disp, Segment, InputChain};
2352     Result =
2353         CurDAG->getMachineNode(NewOpc, SDLoc(Node), MVT::i32, MVT::Other, Ops);
2354     break;
2355   }
2356   case X86ISD::ADD:
2357   case X86ISD::ADC:
2358   case X86ISD::SUB:
2359   case X86ISD::SBB:
2360   case X86ISD::AND:
2361   case X86ISD::OR:
2362   case X86ISD::XOR: {
2363     auto SelectRegOpcode = [SelectOpcode](unsigned Opc) {
2364       switch (Opc) {
2365       case X86ISD::ADD:
2366         return SelectOpcode(X86::ADD64mr, X86::ADD32mr, X86::ADD16mr,
2367                             X86::ADD8mr);
2368       case X86ISD::ADC:
2369         return SelectOpcode(X86::ADC64mr, X86::ADC32mr, X86::ADC16mr,
2370                             X86::ADC8mr);
2371       case X86ISD::SUB:
2372         return SelectOpcode(X86::SUB64mr, X86::SUB32mr, X86::SUB16mr,
2373                             X86::SUB8mr);
2374       case X86ISD::SBB:
2375         return SelectOpcode(X86::SBB64mr, X86::SBB32mr, X86::SBB16mr,
2376                             X86::SBB8mr);
2377       case X86ISD::AND:
2378         return SelectOpcode(X86::AND64mr, X86::AND32mr, X86::AND16mr,
2379                             X86::AND8mr);
2380       case X86ISD::OR:
2381         return SelectOpcode(X86::OR64mr, X86::OR32mr, X86::OR16mr, X86::OR8mr);
2382       case X86ISD::XOR:
2383         return SelectOpcode(X86::XOR64mr, X86::XOR32mr, X86::XOR16mr,
2384                             X86::XOR8mr);
2385       default:
2386         llvm_unreachable("Invalid opcode!");
2387       }
2388     };
2389     auto SelectImm8Opcode = [SelectOpcode](unsigned Opc) {
2390       switch (Opc) {
2391       case X86ISD::ADD:
2392         return SelectOpcode(X86::ADD64mi8, X86::ADD32mi8, X86::ADD16mi8, 0);
2393       case X86ISD::ADC:
2394         return SelectOpcode(X86::ADC64mi8, X86::ADC32mi8, X86::ADC16mi8, 0);
2395       case X86ISD::SUB:
2396         return SelectOpcode(X86::SUB64mi8, X86::SUB32mi8, X86::SUB16mi8, 0);
2397       case X86ISD::SBB:
2398         return SelectOpcode(X86::SBB64mi8, X86::SBB32mi8, X86::SBB16mi8, 0);
2399       case X86ISD::AND:
2400         return SelectOpcode(X86::AND64mi8, X86::AND32mi8, X86::AND16mi8, 0);
2401       case X86ISD::OR:
2402         return SelectOpcode(X86::OR64mi8, X86::OR32mi8, X86::OR16mi8, 0);
2403       case X86ISD::XOR:
2404         return SelectOpcode(X86::XOR64mi8, X86::XOR32mi8, X86::XOR16mi8, 0);
2405       default:
2406         llvm_unreachable("Invalid opcode!");
2407       }
2408     };
2409     auto SelectImmOpcode = [SelectOpcode](unsigned Opc) {
2410       switch (Opc) {
2411       case X86ISD::ADD:
2412         return SelectOpcode(X86::ADD64mi32, X86::ADD32mi, X86::ADD16mi,
2413                             X86::ADD8mi);
2414       case X86ISD::ADC:
2415         return SelectOpcode(X86::ADC64mi32, X86::ADC32mi, X86::ADC16mi,
2416                             X86::ADC8mi);
2417       case X86ISD::SUB:
2418         return SelectOpcode(X86::SUB64mi32, X86::SUB32mi, X86::SUB16mi,
2419                             X86::SUB8mi);
2420       case X86ISD::SBB:
2421         return SelectOpcode(X86::SBB64mi32, X86::SBB32mi, X86::SBB16mi,
2422                             X86::SBB8mi);
2423       case X86ISD::AND:
2424         return SelectOpcode(X86::AND64mi32, X86::AND32mi, X86::AND16mi,
2425                             X86::AND8mi);
2426       case X86ISD::OR:
2427         return SelectOpcode(X86::OR64mi32, X86::OR32mi, X86::OR16mi,
2428                             X86::OR8mi);
2429       case X86ISD::XOR:
2430         return SelectOpcode(X86::XOR64mi32, X86::XOR32mi, X86::XOR16mi,
2431                             X86::XOR8mi);
2432       default:
2433         llvm_unreachable("Invalid opcode!");
2434       }
2435     };
2436
2437     unsigned NewOpc = SelectRegOpcode(Opc);
2438     SDValue Operand = StoredVal->getOperand(1);
2439
2440     // See if the operand is a constant that we can fold into an immediate
2441     // operand.
2442     if (auto *OperandC = dyn_cast<ConstantSDNode>(Operand)) {
2443       auto OperandV = OperandC->getAPIntValue();
2444
2445       // Check if we can shrink the operand enough to fit in an immediate (or
2446       // fit into a smaller immediate) by negating it and switching the
2447       // operation.
2448       if ((Opc == X86ISD::ADD || Opc == X86ISD::SUB) &&
2449           ((MemVT != MVT::i8 && OperandV.getMinSignedBits() > 8 &&
2450             (-OperandV).getMinSignedBits() <= 8) ||
2451            (MemVT == MVT::i64 && OperandV.getMinSignedBits() > 32 &&
2452             (-OperandV).getMinSignedBits() <= 32)) &&
2453           hasNoCarryFlagUses(StoredVal.getNode())) {
2454         OperandV = -OperandV;
2455         Opc = Opc == X86ISD::ADD ? X86ISD::SUB : X86ISD::ADD;
2456       }
2457
2458       // First try to fit this into an Imm8 operand. If it doesn't fit, then try
2459       // the larger immediate operand.
2460       if (MemVT != MVT::i8 && OperandV.getMinSignedBits() <= 8) {
2461         Operand = CurDAG->getTargetConstant(OperandV, SDLoc(Node), MemVT);
2462         NewOpc = SelectImm8Opcode(Opc);
2463       } else if (OperandV.getActiveBits() <= MemVT.getSizeInBits() &&
2464                  (MemVT != MVT::i64 || OperandV.getMinSignedBits() <= 32)) {
2465         Operand = CurDAG->getTargetConstant(OperandV, SDLoc(Node), MemVT);
2466         NewOpc = SelectImmOpcode(Opc);
2467       }
2468     }
2469
2470     if (Opc == X86ISD::ADC || Opc == X86ISD::SBB) {
2471       SDValue CopyTo =
2472           CurDAG->getCopyToReg(InputChain, SDLoc(Node), X86::EFLAGS,
2473                                StoredVal.getOperand(2), SDValue());
2474
2475       const SDValue Ops[] = {Base,    Scale,   Index,  Disp,
2476                              Segment, Operand, CopyTo, CopyTo.getValue(1)};
2477       Result = CurDAG->getMachineNode(NewOpc, SDLoc(Node), MVT::i32, MVT::Other,
2478                                       Ops);
2479     } else {
2480       const SDValue Ops[] = {Base,    Scale,   Index,     Disp,
2481                              Segment, Operand, InputChain};
2482       Result = CurDAG->getMachineNode(NewOpc, SDLoc(Node), MVT::i32, MVT::Other,
2483                                       Ops);
2484     }
2485     break;
2486   }
2487   default:
2488     llvm_unreachable("Invalid opcode!");
2489   }
2490
2491   MachineSDNode::mmo_iterator MemOp = MF->allocateMemRefsArray(2);
2492   MemOp[0] = StoreNode->getMemOperand();
2493   MemOp[1] = LoadNode->getMemOperand();
2494   Result->setMemRefs(MemOp, MemOp + 2);
2495
2496   // Update Load Chain uses as well.
2497   ReplaceUses(SDValue(LoadNode, 1), SDValue(Result, 1));
2498   ReplaceUses(SDValue(StoreNode, 0), SDValue(Result, 1));
2499   ReplaceUses(SDValue(StoredVal.getNode(), 1), SDValue(Result, 0));
2500   CurDAG->RemoveDeadNode(Node);
2501   return true;
2502 }
2503
2504 // See if this is an (X >> C1) & C2 that we can match to BEXTR/BEXTRI.
2505 bool X86DAGToDAGISel::matchBEXTRFromAnd(SDNode *Node) {
2506   MVT NVT = Node->getSimpleValueType(0);
2507   SDLoc dl(Node);
2508
2509   SDValue N0 = Node->getOperand(0);
2510   SDValue N1 = Node->getOperand(1);
2511
2512   if (!Subtarget->hasBMI() && !Subtarget->hasTBM())
2513     return false;
2514
2515   // Must have a shift right.
2516   if (N0->getOpcode() != ISD::SRL && N0->getOpcode() != ISD::SRA)
2517     return false;
2518
2519   // Shift can't have additional users.
2520   if (!N0->hasOneUse())
2521     return false;
2522
2523   // Only supported for 32 and 64 bits.
2524   if (NVT != MVT::i32 && NVT != MVT::i64)
2525     return false;
2526
2527   // Shift amount and RHS of and must be constant.
2528   ConstantSDNode *MaskCst = dyn_cast<ConstantSDNode>(N1);
2529   ConstantSDNode *ShiftCst = dyn_cast<ConstantSDNode>(N0->getOperand(1));
2530   if (!MaskCst || !ShiftCst)
2531     return false;
2532
2533   // And RHS must be a mask.
2534   uint64_t Mask = MaskCst->getZExtValue();
2535   if (!isMask_64(Mask))
2536     return false;
2537
2538   uint64_t Shift = ShiftCst->getZExtValue();
2539   uint64_t MaskSize = countPopulation(Mask);
2540
2541   // Don't interfere with something that can be handled by extracting AH.
2542   // TODO: If we are able to fold a load, BEXTR might still be better than AH.
2543   if (Shift == 8 && MaskSize == 8)
2544     return false;
2545
2546   // Make sure we are only using bits that were in the original value, not
2547   // shifted in.
2548   if (Shift + MaskSize > NVT.getSizeInBits())
2549     return false;
2550
2551   // Create a BEXTR node and run it through selection.
2552   SDValue C = CurDAG->getConstant(Shift | (MaskSize << 8), dl, NVT);
2553   SDValue New = CurDAG->getNode(X86ISD::BEXTR, dl, NVT,
2554                                 N0->getOperand(0), C);
2555   ReplaceNode(Node, New.getNode());
2556   SelectCode(New.getNode());
2557   return true;
2558 }
2559
2560 // Emit a PCMISTR(I/M) instruction.
2561 MachineSDNode *X86DAGToDAGISel::emitPCMPISTR(unsigned ROpc, unsigned MOpc,
2562                                              bool MayFoldLoad, const SDLoc &dl,
2563                                              MVT VT, SDNode *Node) {
2564   SDValue N0 = Node->getOperand(0);
2565   SDValue N1 = Node->getOperand(1);
2566   SDValue Imm = Node->getOperand(2);
2567   const ConstantInt *Val = cast<ConstantSDNode>(Imm)->getConstantIntValue();
2568   Imm = CurDAG->getTargetConstant(*Val, SDLoc(Node), Imm.getValueType());
2569
2570   // If there is a load, it will be behind a bitcast. We don't need to check
2571   // alignment on this load.
2572   SDValue Tmp0, Tmp1, Tmp2, Tmp3, Tmp4;
2573   if (MayFoldLoad && N1->getOpcode() == ISD::BITCAST && N1->hasOneUse() &&
2574       tryFoldVecLoad(Node, N1.getNode(), N1.getOperand(0), Tmp0, Tmp1, Tmp2,
2575                      Tmp3, Tmp4)) {
2576     SDValue Load = N1.getOperand(0);
2577     SDValue Ops[] = { N0, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, Imm,
2578                       Load.getOperand(0) };
2579     SDVTList VTs = CurDAG->getVTList(VT, MVT::i32, MVT::Other);
2580     MachineSDNode *CNode = CurDAG->getMachineNode(MOpc, dl, VTs, Ops);
2581     // Update the chain.
2582     ReplaceUses(Load.getValue(1), SDValue(CNode, 2));
2583     // Record the mem-refs
2584     MachineSDNode::mmo_iterator MemOp = MF->allocateMemRefsArray(1);
2585     MemOp[0] = cast<LoadSDNode>(Load)->getMemOperand();
2586     CNode->setMemRefs(MemOp, MemOp + 1);
2587     return CNode;
2588   }
2589
2590   SDValue Ops[] = { N0, N1, Imm };
2591   SDVTList VTs = CurDAG->getVTList(VT, MVT::i32);
2592   MachineSDNode *CNode = CurDAG->getMachineNode(ROpc, dl, VTs, Ops);
2593   return CNode;
2594 }
2595
2596 // Emit a PCMESTR(I/M) instruction. Also return the Glue result in case we need
2597 // to emit a second instruction after this one. This is needed since we have two
2598 // copyToReg nodes glued before this and we need to continue that glue through.
2599 MachineSDNode *X86DAGToDAGISel::emitPCMPESTR(unsigned ROpc, unsigned MOpc,
2600                                              bool MayFoldLoad, const SDLoc &dl,
2601                                              MVT VT, SDNode *Node,
2602                                              SDValue &InFlag) {
2603   SDValue N0 = Node->getOperand(0);
2604   SDValue N2 = Node->getOperand(2);
2605   SDValue Imm = Node->getOperand(4);
2606   const ConstantInt *Val = cast<ConstantSDNode>(Imm)->getConstantIntValue();
2607   Imm = CurDAG->getTargetConstant(*Val, SDLoc(Node), Imm.getValueType());
2608
2609   // If there is a load, it will be behind a bitcast. We don't need to check
2610   // alignment on this load.
2611   SDValue Tmp0, Tmp1, Tmp2, Tmp3, Tmp4;
2612   if (MayFoldLoad && N2->getOpcode() == ISD::BITCAST && N2->hasOneUse() &&
2613       tryFoldVecLoad(Node, N2.getNode(), N2.getOperand(0), Tmp0, Tmp1, Tmp2,
2614                      Tmp3, Tmp4)) {
2615     SDValue Load = N2.getOperand(0);
2616     SDValue Ops[] = { N0, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, Imm,
2617                       Load.getOperand(0), InFlag };
2618     SDVTList VTs = CurDAG->getVTList(VT, MVT::i32, MVT::Other, MVT::Glue);
2619     MachineSDNode *CNode = CurDAG->getMachineNode(MOpc, dl, VTs, Ops);
2620     InFlag = SDValue(CNode, 3);
2621     // Update the chain.
2622     ReplaceUses(Load.getValue(1), SDValue(CNode, 2));
2623     // Record the mem-refs
2624     MachineSDNode::mmo_iterator MemOp = MF->allocateMemRefsArray(1);
2625     MemOp[0] = cast<LoadSDNode>(Load)->getMemOperand();
2626     CNode->setMemRefs(MemOp, MemOp + 1);
2627     return CNode;
2628   }
2629
2630   SDValue Ops[] = { N0, N2, Imm, InFlag };
2631   SDVTList VTs = CurDAG->getVTList(VT, MVT::i32, MVT::Glue);
2632   MachineSDNode *CNode = CurDAG->getMachineNode(ROpc, dl, VTs, Ops);
2633   InFlag = SDValue(CNode, 2);
2634   return CNode;
2635 }
2636
2637 /// If the high bits of an 'and' operand are known zero, try setting the
2638 /// high bits of an 'and' constant operand to produce a smaller encoding by
2639 /// creating a small, sign-extended negative immediate rather than a large
2640 /// positive one. This reverses a transform in SimplifyDemandedBits that
2641 /// shrinks mask constants by clearing bits. There is also a possibility that
2642 /// the 'and' mask can be made -1, so the 'and' itself is unnecessary. In that
2643 /// case, just replace the 'and'. Return 'true' if the node is replaced.
2644 bool X86DAGToDAGISel::shrinkAndImmediate(SDNode *And) {
2645   // i8 is unshrinkable, i16 should be promoted to i32, and vector ops don't
2646   // have immediate operands.
2647   MVT VT = And->getSimpleValueType(0);
2648   if (VT != MVT::i32 && VT != MVT::i64)
2649     return false;
2650
2651   auto *And1C = dyn_cast<ConstantSDNode>(And->getOperand(1));
2652   if (!And1C)
2653     return false;
2654
2655   // Bail out if the mask constant is already negative. It's can't shrink more.
2656   // If the upper 32 bits of a 64 bit mask are all zeros, we have special isel
2657   // patterns to use a 32-bit and instead of a 64-bit and by relying on the
2658   // implicit zeroing of 32 bit ops. So we should check if the lower 32 bits
2659   // are negative too.
2660   APInt MaskVal = And1C->getAPIntValue();
2661   unsigned MaskLZ = MaskVal.countLeadingZeros();
2662   if (!MaskLZ || (VT == MVT::i64 && MaskLZ == 32))
2663     return false;
2664
2665   // Don't extend into the upper 32 bits of a 64 bit mask.
2666   if (VT == MVT::i64 && MaskLZ >= 32) {
2667     MaskLZ -= 32;
2668     MaskVal = MaskVal.trunc(32);
2669   }
2670
2671   SDValue And0 = And->getOperand(0);
2672   APInt HighZeros = APInt::getHighBitsSet(MaskVal.getBitWidth(), MaskLZ);
2673   APInt NegMaskVal = MaskVal | HighZeros;
2674
2675   // If a negative constant would not allow a smaller encoding, there's no need
2676   // to continue. Only change the constant when we know it's a win.
2677   unsigned MinWidth = NegMaskVal.getMinSignedBits();
2678   if (MinWidth > 32 || (MinWidth > 8 && MaskVal.getMinSignedBits() <= 32))
2679     return false;
2680
2681   // Extend masks if we truncated above.
2682   if (VT == MVT::i64 && MaskVal.getBitWidth() < 64) {
2683     NegMaskVal = NegMaskVal.zext(64);
2684     HighZeros = HighZeros.zext(64);
2685   }
2686
2687   // The variable operand must be all zeros in the top bits to allow using the
2688   // new, negative constant as the mask.
2689   if (!CurDAG->MaskedValueIsZero(And0, HighZeros))
2690     return false;
2691
2692   // Check if the mask is -1. In that case, this is an unnecessary instruction
2693   // that escaped earlier analysis.
2694   if (NegMaskVal.isAllOnesValue()) {
2695     ReplaceNode(And, And0.getNode());
2696     return true;
2697   }
2698
2699   // A negative mask allows a smaller encoding. Create a new 'and' node.
2700   SDValue NewMask = CurDAG->getConstant(NegMaskVal, SDLoc(And), VT);
2701   SDValue NewAnd = CurDAG->getNode(ISD::AND, SDLoc(And), VT, And0, NewMask);
2702   ReplaceNode(And, NewAnd.getNode());
2703   SelectCode(NewAnd.getNode());
2704   return true;
2705 }
2706
2707 void X86DAGToDAGISel::Select(SDNode *Node) {
2708   MVT NVT = Node->getSimpleValueType(0);
2709   unsigned Opcode = Node->getOpcode();
2710   SDLoc dl(Node);
2711
2712   if (Node->isMachineOpcode()) {
2713     LLVM_DEBUG(dbgs() << "== "; Node->dump(CurDAG); dbgs() << '\n');
2714     Node->setNodeId(-1);
2715     return;   // Already selected.
2716   }
2717
2718   switch (Opcode) {
2719   default: break;
2720   case ISD::BRIND: {
2721     if (Subtarget->isTargetNaCl())
2722       // NaCl has its own pass where jmp %r32 are converted to jmp %r64. We
2723       // leave the instruction alone.
2724       break;
2725     if (Subtarget->isTarget64BitILP32()) {
2726       // Converts a 32-bit register to a 64-bit, zero-extended version of
2727       // it. This is needed because x86-64 can do many things, but jmp %r32
2728       // ain't one of them.
2729       const SDValue &Target = Node->getOperand(1);
2730       assert(Target.getSimpleValueType() == llvm::MVT::i32);
2731       SDValue ZextTarget = CurDAG->getZExtOrTrunc(Target, dl, EVT(MVT::i64));
2732       SDValue Brind = CurDAG->getNode(ISD::BRIND, dl, MVT::Other,
2733                                       Node->getOperand(0), ZextTarget);
2734       ReplaceNode(Node, Brind.getNode());
2735       SelectCode(ZextTarget.getNode());
2736       SelectCode(Brind.getNode());
2737       return;
2738     }
2739     break;
2740   }
2741   case X86ISD::GlobalBaseReg:
2742     ReplaceNode(Node, getGlobalBaseReg());
2743     return;
2744
2745   case X86ISD::SELECT:
2746   case X86ISD::SHRUNKBLEND: {
2747     // SHRUNKBLEND selects like a regular VSELECT. Same with X86ISD::SELECT.
2748     SDValue VSelect = CurDAG->getNode(
2749         ISD::VSELECT, SDLoc(Node), Node->getValueType(0), Node->getOperand(0),
2750         Node->getOperand(1), Node->getOperand(2));
2751     ReplaceNode(Node, VSelect.getNode());
2752     SelectCode(VSelect.getNode());
2753     // We already called ReplaceUses.
2754     return;
2755   }
2756
2757   case ISD::AND:
2758     if (matchBEXTRFromAnd(Node))
2759       return;
2760     if (shrinkAndImmediate(Node))
2761       return;
2762
2763     LLVM_FALLTHROUGH;
2764   case ISD::OR:
2765   case ISD::XOR: {
2766
2767     // For operations of the form (x << C1) op C2, check if we can use a smaller
2768     // encoding for C2 by transforming it into (x op (C2>>C1)) << C1.
2769     SDValue N0 = Node->getOperand(0);
2770     SDValue N1 = Node->getOperand(1);
2771
2772     if (N0->getOpcode() != ISD::SHL || !N0->hasOneUse())
2773       break;
2774
2775     // i8 is unshrinkable, i16 should be promoted to i32.
2776     if (NVT != MVT::i32 && NVT != MVT::i64)
2777       break;
2778
2779     ConstantSDNode *Cst = dyn_cast<ConstantSDNode>(N1);
2780     ConstantSDNode *ShlCst = dyn_cast<ConstantSDNode>(N0->getOperand(1));
2781     if (!Cst || !ShlCst)
2782       break;
2783
2784     int64_t Val = Cst->getSExtValue();
2785     uint64_t ShlVal = ShlCst->getZExtValue();
2786
2787     // Make sure that we don't change the operation by removing bits.
2788     // This only matters for OR and XOR, AND is unaffected.
2789     uint64_t RemovedBitsMask = (1ULL << ShlVal) - 1;
2790     if (Opcode != ISD::AND && (Val & RemovedBitsMask) != 0)
2791       break;
2792
2793     unsigned ShlOp, AddOp, Op;
2794     MVT CstVT = NVT;
2795
2796     // Check the minimum bitwidth for the new constant.
2797     // TODO: AND32ri is the same as AND64ri32 with zext imm.
2798     // TODO: MOV32ri+OR64r is cheaper than MOV64ri64+OR64rr
2799     // TODO: Using 16 and 8 bit operations is also possible for or32 & xor32.
2800     if (!isInt<8>(Val) && isInt<8>(Val >> ShlVal))
2801       CstVT = MVT::i8;
2802     else if (!isInt<32>(Val) && isInt<32>(Val >> ShlVal))
2803       CstVT = MVT::i32;
2804
2805     // Bail if there is no smaller encoding.
2806     if (NVT == CstVT)
2807       break;
2808
2809     switch (NVT.SimpleTy) {
2810     default: llvm_unreachable("Unsupported VT!");
2811     case MVT::i32:
2812       assert(CstVT == MVT::i8);
2813       ShlOp = X86::SHL32ri;
2814       AddOp = X86::ADD32rr;
2815
2816       switch (Opcode) {
2817       default: llvm_unreachable("Impossible opcode");
2818       case ISD::AND: Op = X86::AND32ri8; break;
2819       case ISD::OR:  Op =  X86::OR32ri8; break;
2820       case ISD::XOR: Op = X86::XOR32ri8; break;
2821       }
2822       break;
2823     case MVT::i64:
2824       assert(CstVT == MVT::i8 || CstVT == MVT::i32);
2825       ShlOp = X86::SHL64ri;
2826       AddOp = X86::ADD64rr;
2827
2828       switch (Opcode) {
2829       default: llvm_unreachable("Impossible opcode");
2830       case ISD::AND: Op = CstVT==MVT::i8? X86::AND64ri8 : X86::AND64ri32; break;
2831       case ISD::OR:  Op = CstVT==MVT::i8?  X86::OR64ri8 :  X86::OR64ri32; break;
2832       case ISD::XOR: Op = CstVT==MVT::i8? X86::XOR64ri8 : X86::XOR64ri32; break;
2833       }
2834       break;
2835     }
2836
2837     // Emit the smaller op and the shift.
2838     SDValue NewCst = CurDAG->getTargetConstant(Val >> ShlVal, dl, CstVT);
2839     SDNode *New = CurDAG->getMachineNode(Op, dl, NVT, N0->getOperand(0),NewCst);
2840     if (ShlVal == 1)
2841       CurDAG->SelectNodeTo(Node, AddOp, NVT, SDValue(New, 0),
2842                            SDValue(New, 0));
2843     else
2844       CurDAG->SelectNodeTo(Node, ShlOp, NVT, SDValue(New, 0),
2845                            getI8Imm(ShlVal, dl));
2846     return;
2847   }
2848   case X86ISD::UMUL8:
2849   case X86ISD::SMUL8: {
2850     SDValue N0 = Node->getOperand(0);
2851     SDValue N1 = Node->getOperand(1);
2852
2853     unsigned Opc = (Opcode == X86ISD::SMUL8 ? X86::IMUL8r : X86::MUL8r);
2854
2855     SDValue InFlag = CurDAG->getCopyToReg(CurDAG->getEntryNode(), dl, X86::AL,
2856                                           N0, SDValue()).getValue(1);
2857
2858     SDVTList VTs = CurDAG->getVTList(NVT, MVT::i32);
2859     SDValue Ops[] = {N1, InFlag};
2860     SDNode *CNode = CurDAG->getMachineNode(Opc, dl, VTs, Ops);
2861
2862     ReplaceNode(Node, CNode);
2863     return;
2864   }
2865
2866   case X86ISD::UMUL: {
2867     SDValue N0 = Node->getOperand(0);
2868     SDValue N1 = Node->getOperand(1);
2869
2870     unsigned LoReg, Opc;
2871     switch (NVT.SimpleTy) {
2872     default: llvm_unreachable("Unsupported VT!");
2873     // MVT::i8 is handled by X86ISD::UMUL8.
2874     case MVT::i16: LoReg = X86::AX;  Opc = X86::MUL16r; break;
2875     case MVT::i32: LoReg = X86::EAX; Opc = X86::MUL32r; break;
2876     case MVT::i64: LoReg = X86::RAX; Opc = X86::MUL64r; break;
2877     }
2878
2879     SDValue InFlag = CurDAG->getCopyToReg(CurDAG->getEntryNode(), dl, LoReg,
2880                                           N0, SDValue()).getValue(1);
2881
2882     SDVTList VTs = CurDAG->getVTList(NVT, NVT, MVT::i32);
2883     SDValue Ops[] = {N1, InFlag};
2884     SDNode *CNode = CurDAG->getMachineNode(Opc, dl, VTs, Ops);
2885
2886     ReplaceNode(Node, CNode);
2887     return;
2888   }
2889
2890   case ISD::SMUL_LOHI:
2891   case ISD::UMUL_LOHI: {
2892     SDValue N0 = Node->getOperand(0);
2893     SDValue N1 = Node->getOperand(1);
2894
2895     unsigned Opc, MOpc;
2896     bool isSigned = Opcode == ISD::SMUL_LOHI;
2897     bool hasBMI2 = Subtarget->hasBMI2();
2898     if (!isSigned) {
2899       switch (NVT.SimpleTy) {
2900       default: llvm_unreachable("Unsupported VT!");
2901       case MVT::i32: Opc = hasBMI2 ? X86::MULX32rr : X86::MUL32r;
2902                      MOpc = hasBMI2 ? X86::MULX32rm : X86::MUL32m; break;
2903       case MVT::i64: Opc = hasBMI2 ? X86::MULX64rr : X86::MUL64r;
2904                      MOpc = hasBMI2 ? X86::MULX64rm : X86::MUL64m; break;
2905       }
2906     } else {
2907       switch (NVT.SimpleTy) {
2908       default: llvm_unreachable("Unsupported VT!");
2909       case MVT::i32: Opc = X86::IMUL32r; MOpc = X86::IMUL32m; break;
2910       case MVT::i64: Opc = X86::IMUL64r; MOpc = X86::IMUL64m; break;
2911       }
2912     }
2913
2914     unsigned SrcReg, LoReg, HiReg;
2915     switch (Opc) {
2916     default: llvm_unreachable("Unknown MUL opcode!");
2917     case X86::IMUL32r:
2918     case X86::MUL32r:
2919       SrcReg = LoReg = X86::EAX; HiReg = X86::EDX;
2920       break;
2921     case X86::IMUL64r:
2922     case X86::MUL64r:
2923       SrcReg = LoReg = X86::RAX; HiReg = X86::RDX;
2924       break;
2925     case X86::MULX32rr:
2926       SrcReg = X86::EDX; LoReg = HiReg = 0;
2927       break;
2928     case X86::MULX64rr:
2929       SrcReg = X86::RDX; LoReg = HiReg = 0;
2930       break;
2931     }
2932
2933     SDValue Tmp0, Tmp1, Tmp2, Tmp3, Tmp4;
2934     bool foldedLoad = tryFoldLoad(Node, N1, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4);
2935     // Multiply is commmutative.
2936     if (!foldedLoad) {
2937       foldedLoad = tryFoldLoad(Node, N0, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4);
2938       if (foldedLoad)
2939         std::swap(N0, N1);
2940     }
2941
2942     SDValue InFlag = CurDAG->getCopyToReg(CurDAG->getEntryNode(), dl, SrcReg,
2943                                           N0, SDValue()).getValue(1);
2944     SDValue ResHi, ResLo;
2945
2946     if (foldedLoad) {
2947       SDValue Chain;
2948       MachineSDNode *CNode = nullptr;
2949       SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, N1.getOperand(0),
2950                         InFlag };
2951       if (MOpc == X86::MULX32rm || MOpc == X86::MULX64rm) {
2952         SDVTList VTs = CurDAG->getVTList(NVT, NVT, MVT::Other, MVT::Glue);
2953         CNode = CurDAG->getMachineNode(MOpc, dl, VTs, Ops);
2954         ResHi = SDValue(CNode, 0);
2955         ResLo = SDValue(CNode, 1);
2956         Chain = SDValue(CNode, 2);
2957         InFlag = SDValue(CNode, 3);
2958       } else {
2959         SDVTList VTs = CurDAG->getVTList(MVT::Other, MVT::Glue);
2960         CNode = CurDAG->getMachineNode(MOpc, dl, VTs, Ops);
2961         Chain = SDValue(CNode, 0);
2962         InFlag = SDValue(CNode, 1);
2963       }
2964
2965       // Update the chain.
2966       ReplaceUses(N1.getValue(1), Chain);
2967       // Record the mem-refs
2968       MachineSDNode::mmo_iterator MemOp = MF->allocateMemRefsArray(1);
2969       MemOp[0] = cast<LoadSDNode>(N1)->getMemOperand();
2970       CNode->setMemRefs(MemOp, MemOp + 1);
2971     } else {
2972       SDValue Ops[] = { N1, InFlag };
2973       if (Opc == X86::MULX32rr || Opc == X86::MULX64rr) {
2974         SDVTList VTs = CurDAG->getVTList(NVT, NVT, MVT::Glue);
2975         SDNode *CNode = CurDAG->getMachineNode(Opc, dl, VTs, Ops);
2976         ResHi = SDValue(CNode, 0);
2977         ResLo = SDValue(CNode, 1);
2978         InFlag = SDValue(CNode, 2);
2979       } else {
2980         SDVTList VTs = CurDAG->getVTList(MVT::Glue);
2981         SDNode *CNode = CurDAG->getMachineNode(Opc, dl, VTs, Ops);
2982         InFlag = SDValue(CNode, 0);
2983       }
2984     }
2985
2986     // Copy the low half of the result, if it is needed.
2987     if (!SDValue(Node, 0).use_empty()) {
2988       if (!ResLo.getNode()) {
2989         assert(LoReg && "Register for low half is not defined!");
2990         ResLo = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl, LoReg, NVT,
2991                                        InFlag);
2992         InFlag = ResLo.getValue(2);
2993       }
2994       ReplaceUses(SDValue(Node, 0), ResLo);
2995       LLVM_DEBUG(dbgs() << "=> "; ResLo.getNode()->dump(CurDAG);
2996                  dbgs() << '\n');
2997     }
2998     // Copy the high half of the result, if it is needed.
2999     if (!SDValue(Node, 1).use_empty()) {
3000       if (!ResHi.getNode()) {
3001         assert(HiReg && "Register for high half is not defined!");
3002         ResHi = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl, HiReg, NVT,
3003                                        InFlag);
3004         InFlag = ResHi.getValue(2);
3005       }
3006       ReplaceUses(SDValue(Node, 1), ResHi);
3007       LLVM_DEBUG(dbgs() << "=> "; ResHi.getNode()->dump(CurDAG);
3008                  dbgs() << '\n');
3009     }
3010
3011     CurDAG->RemoveDeadNode(Node);
3012     return;
3013   }
3014
3015   case ISD::SDIVREM:
3016   case ISD::UDIVREM:
3017   case X86ISD::SDIVREM8_SEXT_HREG:
3018   case X86ISD::UDIVREM8_ZEXT_HREG: {
3019     SDValue N0 = Node->getOperand(0);
3020     SDValue N1 = Node->getOperand(1);
3021
3022     unsigned Opc, MOpc;
3023     bool isSigned = (Opcode == ISD::SDIVREM ||
3024                      Opcode == X86ISD::SDIVREM8_SEXT_HREG);
3025     if (!isSigned) {
3026       switch (NVT.SimpleTy) {
3027       default: llvm_unreachable("Unsupported VT!");
3028       case MVT::i8:  Opc = X86::DIV8r;  MOpc = X86::DIV8m;  break;
3029       case MVT::i16: Opc = X86::DIV16r; MOpc = X86::DIV16m; break;
3030       case MVT::i32: Opc = X86::DIV32r; MOpc = X86::DIV32m; break;
3031       case MVT::i64: Opc = X86::DIV64r; MOpc = X86::DIV64m; break;
3032       }
3033     } else {
3034       switch (NVT.SimpleTy) {
3035       default: llvm_unreachable("Unsupported VT!");
3036       case MVT::i8:  Opc = X86::IDIV8r;  MOpc = X86::IDIV8m;  break;
3037       case MVT::i16: Opc = X86::IDIV16r; MOpc = X86::IDIV16m; break;
3038       case MVT::i32: Opc = X86::IDIV32r; MOpc = X86::IDIV32m; break;
3039       case MVT::i64: Opc = X86::IDIV64r; MOpc = X86::IDIV64m; break;
3040       }
3041     }
3042
3043     unsigned LoReg, HiReg, ClrReg;
3044     unsigned SExtOpcode;
3045     switch (NVT.SimpleTy) {
3046     default: llvm_unreachable("Unsupported VT!");
3047     case MVT::i8:
3048       LoReg = X86::AL;  ClrReg = HiReg = X86::AH;
3049       SExtOpcode = X86::CBW;
3050       break;
3051     case MVT::i16:
3052       LoReg = X86::AX;  HiReg = X86::DX;
3053       ClrReg = X86::DX;
3054       SExtOpcode = X86::CWD;
3055       break;
3056     case MVT::i32:
3057       LoReg = X86::EAX; ClrReg = HiReg = X86::EDX;
3058       SExtOpcode = X86::CDQ;
3059       break;
3060     case MVT::i64:
3061       LoReg = X86::RAX; ClrReg = HiReg = X86::RDX;
3062       SExtOpcode = X86::CQO;
3063       break;
3064     }
3065
3066     SDValue Tmp0, Tmp1, Tmp2, Tmp3, Tmp4;
3067     bool foldedLoad = tryFoldLoad(Node, N1, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4);
3068     bool signBitIsZero = CurDAG->SignBitIsZero(N0);
3069
3070     SDValue InFlag;
3071     if (NVT == MVT::i8 && (!isSigned || signBitIsZero)) {
3072       // Special case for div8, just use a move with zero extension to AX to
3073       // clear the upper 8 bits (AH).
3074       SDValue Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, Move, Chain;
3075       if (tryFoldLoad(Node, N0, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4)) {
3076         SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, N0.getOperand(0) };
3077         Move =
3078           SDValue(CurDAG->getMachineNode(X86::MOVZX32rm8, dl, MVT::i32,
3079                                          MVT::Other, Ops), 0);
3080         Chain = Move.getValue(1);
3081         ReplaceUses(N0.getValue(1), Chain);
3082       } else {
3083         Move =
3084           SDValue(CurDAG->getMachineNode(X86::MOVZX32rr8, dl, MVT::i32, N0),0);
3085         Chain = CurDAG->getEntryNode();
3086       }
3087       Chain  = CurDAG->getCopyToReg(Chain, dl, X86::EAX, Move, SDValue());
3088       InFlag = Chain.getValue(1);
3089     } else {
3090       InFlag =
3091         CurDAG->getCopyToReg(CurDAG->getEntryNode(), dl,
3092                              LoReg, N0, SDValue()).getValue(1);
3093       if (isSigned && !signBitIsZero) {
3094         // Sign extend the low part into the high part.
3095         InFlag =
3096           SDValue(CurDAG->getMachineNode(SExtOpcode, dl, MVT::Glue, InFlag),0);
3097       } else {
3098         // Zero out the high part, effectively zero extending the input.
3099         SDValue ClrNode = SDValue(CurDAG->getMachineNode(X86::MOV32r0, dl, NVT), 0);
3100         switch (NVT.SimpleTy) {
3101         case MVT::i16:
3102           ClrNode =
3103               SDValue(CurDAG->getMachineNode(
3104                           TargetOpcode::EXTRACT_SUBREG, dl, MVT::i16, ClrNode,
3105                           CurDAG->getTargetConstant(X86::sub_16bit, dl,
3106                                                     MVT::i32)),
3107                       0);
3108           break;
3109         case MVT::i32:
3110           break;
3111         case MVT::i64:
3112           ClrNode =
3113               SDValue(CurDAG->getMachineNode(
3114                           TargetOpcode::SUBREG_TO_REG, dl, MVT::i64,
3115                           CurDAG->getTargetConstant(0, dl, MVT::i64), ClrNode,
3116                           CurDAG->getTargetConstant(X86::sub_32bit, dl,
3117                                                     MVT::i32)),
3118                       0);
3119           break;
3120         default:
3121           llvm_unreachable("Unexpected division source");
3122         }
3123
3124         InFlag = CurDAG->getCopyToReg(CurDAG->getEntryNode(), dl, ClrReg,
3125                                       ClrNode, InFlag).getValue(1);
3126       }
3127     }
3128
3129     if (foldedLoad) {
3130       SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, Tmp4, N1.getOperand(0),
3131                         InFlag };
3132       MachineSDNode *CNode =
3133         CurDAG->getMachineNode(MOpc, dl, MVT::Other, MVT::Glue, Ops);
3134       InFlag = SDValue(CNode, 1);
3135       // Update the chain.
3136       ReplaceUses(N1.getValue(1), SDValue(CNode, 0));
3137       // Record the mem-refs
3138       MachineSDNode::mmo_iterator MemOp = MF->allocateMemRefsArray(1);
3139       MemOp[0] = cast<LoadSDNode>(N1)->getMemOperand();
3140       CNode->setMemRefs(MemOp, MemOp + 1);
3141     } else {
3142       InFlag =
3143         SDValue(CurDAG->getMachineNode(Opc, dl, MVT::Glue, N1, InFlag), 0);
3144     }
3145
3146     // Prevent use of AH in a REX instruction by explicitly copying it to
3147     // an ABCD_L register.
3148     //
3149     // The current assumption of the register allocator is that isel
3150     // won't generate explicit references to the GR8_ABCD_H registers. If
3151     // the allocator and/or the backend get enhanced to be more robust in
3152     // that regard, this can be, and should be, removed.
3153     if (HiReg == X86::AH && !SDValue(Node, 1).use_empty()) {
3154       SDValue AHCopy = CurDAG->getRegister(X86::AH, MVT::i8);
3155       unsigned AHExtOpcode =
3156           isSigned ? X86::MOVSX32rr8_NOREX : X86::MOVZX32rr8_NOREX;
3157
3158       SDNode *RNode = CurDAG->getMachineNode(AHExtOpcode, dl, MVT::i32,
3159                                              MVT::Glue, AHCopy, InFlag);
3160       SDValue Result(RNode, 0);
3161       InFlag = SDValue(RNode, 1);
3162
3163       if (Opcode == X86ISD::UDIVREM8_ZEXT_HREG ||
3164           Opcode == X86ISD::SDIVREM8_SEXT_HREG) {
3165         assert(Node->getValueType(1) == MVT::i32 && "Unexpected result type!");
3166       } else {
3167         Result =
3168             CurDAG->getTargetExtractSubreg(X86::sub_8bit, dl, MVT::i8, Result);
3169       }
3170       ReplaceUses(SDValue(Node, 1), Result);
3171       LLVM_DEBUG(dbgs() << "=> "; Result.getNode()->dump(CurDAG);
3172                  dbgs() << '\n');
3173     }
3174     // Copy the division (low) result, if it is needed.
3175     if (!SDValue(Node, 0).use_empty()) {
3176       SDValue Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl,
3177                                                 LoReg, NVT, InFlag);
3178       InFlag = Result.getValue(2);
3179       ReplaceUses(SDValue(Node, 0), Result);
3180       LLVM_DEBUG(dbgs() << "=> "; Result.getNode()->dump(CurDAG);
3181                  dbgs() << '\n');
3182     }
3183     // Copy the remainder (high) result, if it is needed.
3184     if (!SDValue(Node, 1).use_empty()) {
3185       SDValue Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl,
3186                                               HiReg, NVT, InFlag);
3187       InFlag = Result.getValue(2);
3188       ReplaceUses(SDValue(Node, 1), Result);
3189       LLVM_DEBUG(dbgs() << "=> "; Result.getNode()->dump(CurDAG);
3190                  dbgs() << '\n');
3191     }
3192     CurDAG->RemoveDeadNode(Node);
3193     return;
3194   }
3195
3196   case X86ISD::CMP: {
3197     SDValue N0 = Node->getOperand(0);
3198     SDValue N1 = Node->getOperand(1);
3199
3200     if (N0.getOpcode() == ISD::TRUNCATE && N0.hasOneUse() &&
3201         hasNoSignedComparisonUses(Node))
3202       N0 = N0.getOperand(0);
3203
3204     // Look for (X86cmp (and $op, $imm), 0) and see if we can convert it to
3205     // use a smaller encoding.
3206     // Look past the truncate if CMP is the only use of it.
3207     if (N0.getOpcode() == ISD::AND &&
3208         N0.getNode()->hasOneUse() &&
3209         N0.getValueType() != MVT::i8 &&
3210         X86::isZeroNode(N1)) {
3211       ConstantSDNode *C = dyn_cast<ConstantSDNode>(N0.getOperand(1));
3212       if (!C) break;
3213       uint64_t Mask = C->getZExtValue();
3214
3215       MVT VT;
3216       int SubRegOp;
3217       unsigned Op;
3218
3219       if (isUInt<8>(Mask) &&
3220           (!(Mask & 0x80) || hasNoSignedComparisonUses(Node))) {
3221         // For example, convert "testl %eax, $8" to "testb %al, $8"
3222         VT = MVT::i8;
3223         SubRegOp = X86::sub_8bit;
3224         Op = X86::TEST8ri;
3225       } else if (OptForMinSize && isUInt<16>(Mask) &&
3226                  (!(Mask & 0x8000) || hasNoSignedComparisonUses(Node))) {
3227         // For example, "testl %eax, $32776" to "testw %ax, $32776".
3228         // NOTE: We only want to form TESTW instructions if optimizing for
3229         // min size. Otherwise we only save one byte and possibly get a length
3230         // changing prefix penalty in the decoders.
3231         VT = MVT::i16;
3232         SubRegOp = X86::sub_16bit;
3233         Op = X86::TEST16ri;
3234       } else if (isUInt<32>(Mask) && N0.getValueType() != MVT::i16 &&
3235                  (!(Mask & 0x80000000) || hasNoSignedComparisonUses(Node))) {
3236         // For example, "testq %rax, $268468232" to "testl %eax, $268468232".
3237         // NOTE: We only want to run that transform if N0 is 32 or 64 bits.
3238         // Otherwize, we find ourselves in a position where we have to do
3239         // promotion. If previous passes did not promote the and, we assume
3240         // they had a good reason not to and do not promote here.
3241         VT = MVT::i32;
3242         SubRegOp = X86::sub_32bit;
3243         Op = X86::TEST32ri;
3244       } else {
3245         // No eligible transformation was found.
3246         break;
3247       }
3248
3249       SDValue Imm = CurDAG->getTargetConstant(Mask, dl, VT);
3250       SDValue Reg = N0.getOperand(0);
3251
3252       // Extract the subregister if necessary.
3253       if (N0.getValueType() != VT)
3254         Reg = CurDAG->getTargetExtractSubreg(SubRegOp, dl, VT, Reg);
3255
3256       // Emit a testl or testw.
3257       SDNode *NewNode = CurDAG->getMachineNode(Op, dl, MVT::i32, Reg, Imm);
3258       // Replace CMP with TEST.
3259       ReplaceNode(Node, NewNode);
3260       return;
3261     }
3262     break;
3263   }
3264   case X86ISD::PCMPISTR: {
3265     if (!Subtarget->hasSSE42())
3266       break;
3267
3268     bool NeedIndex = !SDValue(Node, 0).use_empty();
3269     bool NeedMask = !SDValue(Node, 1).use_empty();
3270     // We can't fold a load if we are going to make two instructions.
3271     bool MayFoldLoad = !NeedIndex || !NeedMask;
3272
3273     MachineSDNode *CNode;
3274     if (NeedMask) {
3275       unsigned ROpc = Subtarget->hasAVX() ? X86::VPCMPISTRMrr : X86::PCMPISTRMrr;
3276       unsigned MOpc = Subtarget->hasAVX() ? X86::VPCMPISTRMrm : X86::PCMPISTRMrm;
3277       CNode = emitPCMPISTR(ROpc, MOpc, MayFoldLoad, dl, MVT::v16i8, Node);
3278       ReplaceUses(SDValue(Node, 1), SDValue(CNode, 0));
3279     }
3280     if (NeedIndex || !NeedMask) {
3281       unsigned ROpc = Subtarget->hasAVX() ? X86::VPCMPISTRIrr : X86::PCMPISTRIrr;
3282       unsigned MOpc = Subtarget->hasAVX() ? X86::VPCMPISTRIrm : X86::PCMPISTRIrm;
3283       CNode = emitPCMPISTR(ROpc, MOpc, MayFoldLoad, dl, MVT::i32, Node);
3284       ReplaceUses(SDValue(Node, 0), SDValue(CNode, 0));
3285     }
3286
3287     // Connect the flag usage to the last instruction created.
3288     ReplaceUses(SDValue(Node, 2), SDValue(CNode, 0));
3289     CurDAG->RemoveDeadNode(Node);
3290     return;
3291   }
3292   case X86ISD::PCMPESTR: {
3293     if (!Subtarget->hasSSE42())
3294       break;
3295
3296     // Copy the two implicit register inputs.
3297     SDValue InFlag = CurDAG->getCopyToReg(CurDAG->getEntryNode(), dl, X86::EAX,
3298                                           Node->getOperand(1),
3299                                           SDValue()).getValue(1);
3300     InFlag = CurDAG->getCopyToReg(CurDAG->getEntryNode(), dl, X86::EDX,
3301                                   Node->getOperand(3), InFlag).getValue(1);
3302
3303     bool NeedIndex = !SDValue(Node, 0).use_empty();
3304     bool NeedMask = !SDValue(Node, 1).use_empty();
3305     // We can't fold a load if we are going to make two instructions.
3306     bool MayFoldLoad = !NeedIndex || !NeedMask;
3307
3308     MachineSDNode *CNode;
3309     if (NeedMask) {
3310       unsigned ROpc = Subtarget->hasAVX() ? X86::VPCMPESTRMrr : X86::PCMPESTRMrr;
3311       unsigned MOpc = Subtarget->hasAVX() ? X86::VPCMPESTRMrm : X86::PCMPESTRMrm;
3312       CNode = emitPCMPESTR(ROpc, MOpc, MayFoldLoad, dl, MVT::v16i8, Node,
3313                            InFlag);
3314       ReplaceUses(SDValue(Node, 1), SDValue(CNode, 0));
3315     }
3316     if (NeedIndex || !NeedMask) {
3317       unsigned ROpc = Subtarget->hasAVX() ? X86::VPCMPESTRIrr : X86::PCMPESTRIrr;
3318       unsigned MOpc = Subtarget->hasAVX() ? X86::VPCMPESTRIrm : X86::PCMPESTRIrm;
3319       CNode = emitPCMPESTR(ROpc, MOpc, MayFoldLoad, dl, MVT::i32, Node, InFlag);
3320       ReplaceUses(SDValue(Node, 0), SDValue(CNode, 0));
3321     }
3322     // Connect the flag usage to the last instruction created.
3323     ReplaceUses(SDValue(Node, 2), SDValue(CNode, 1));
3324     CurDAG->RemoveDeadNode(Node);
3325     return;
3326   }
3327
3328   case ISD::STORE:
3329     if (foldLoadStoreIntoMemOperand(Node))
3330       return;
3331     break;
3332   }
3333
3334   SelectCode(Node);
3335 }
3336
3337 bool X86DAGToDAGISel::
3338 SelectInlineAsmMemoryOperand(const SDValue &Op, unsigned ConstraintID,
3339                              std::vector<SDValue> &OutOps) {
3340   SDValue Op0, Op1, Op2, Op3, Op4;
3341   switch (ConstraintID) {
3342   default:
3343     llvm_unreachable("Unexpected asm memory constraint");
3344   case InlineAsm::Constraint_i:
3345     // FIXME: It seems strange that 'i' is needed here since it's supposed to
3346     //        be an immediate and not a memory constraint.
3347     LLVM_FALLTHROUGH;
3348   case InlineAsm::Constraint_o: // offsetable        ??
3349   case InlineAsm::Constraint_v: // not offsetable    ??
3350   case InlineAsm::Constraint_m: // memory
3351   case InlineAsm::Constraint_X:
3352     if (!selectAddr(nullptr, Op, Op0, Op1, Op2, Op3, Op4))
3353       return true;
3354     break;
3355   }
3356
3357   OutOps.push_back(Op0);
3358   OutOps.push_back(Op1);
3359   OutOps.push_back(Op2);
3360   OutOps.push_back(Op3);
3361   OutOps.push_back(Op4);
3362   return false;
3363 }
3364
3365 /// This pass converts a legalized DAG into a X86-specific DAG,
3366 /// ready for instruction scheduling.
3367 FunctionPass *llvm::createX86ISelDag(X86TargetMachine &TM,
3368                                      CodeGenOpt::Level OptLevel) {
3369   return new X86DAGToDAGISel(TM, OptLevel);
3370 }