lib/CodeGen/SelectionDAG/TargetLowering.cpp

   1 //===-- TargetLowering.cpp - Implement the TargetLowering class -----------===//
   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 implements the TargetLowering class.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/CodeGen/TargetLowering.h"
  15 #include "llvm/ADT/BitVector.h"
  16 #include "llvm/ADT/STLExtras.h"
  17 #include "llvm/CodeGen/CallingConvLower.h"
  18 #include "llvm/CodeGen/MachineFrameInfo.h"
  19 #include "llvm/CodeGen/MachineFunction.h"
  20 #include "llvm/CodeGen/MachineJumpTableInfo.h"
  21 #include "llvm/CodeGen/MachineRegisterInfo.h"
  22 #include "llvm/CodeGen/SelectionDAG.h"
  23 #include "llvm/CodeGen/TargetRegisterInfo.h"
  24 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  25 #include "llvm/IR/DataLayout.h"
  26 #include "llvm/IR/DerivedTypes.h"
  27 #include "llvm/IR/GlobalVariable.h"
  28 #include "llvm/IR/LLVMContext.h"
  29 #include "llvm/MC/MCAsmInfo.h"
  30 #include "llvm/MC/MCExpr.h"
  31 #include "llvm/Support/ErrorHandling.h"
  32 #include "llvm/Support/KnownBits.h"
  33 #include "llvm/Support/MathExtras.h"
  34 #include "llvm/Target/TargetLoweringObjectFile.h"
  35 #include "llvm/Target/TargetMachine.h"
  36 #include <cctype>
  37 using namespace llvm;
  38
  39 /// NOTE: The TargetMachine owns TLOF.
  40 TargetLowering::TargetLowering(const TargetMachine &tm)
  41   : TargetLoweringBase(tm) {}
  42
  43 const char *TargetLowering::getTargetNodeName(unsigned Opcode) const {
  44   return nullptr;
  45 }
  46
  47 bool TargetLowering::isPositionIndependent() const {
  48   return getTargetMachine().isPositionIndependent();
  49 }
  50
  51 /// Check whether a given call node is in tail position within its function. If
  52 /// so, it sets Chain to the input chain of the tail call.
  53 bool TargetLowering::isInTailCallPosition(SelectionDAG &DAG, SDNode *Node,
  54                                           SDValue &Chain) const {
  55   const Function &F = DAG.getMachineFunction().getFunction();
  56
  57   // Conservatively require the attributes of the call to match those of
  58   // the return. Ignore NoAlias and NonNull because they don't affect the
  59   // call sequence.
  60   AttributeList CallerAttrs = F.getAttributes();
  61   if (AttrBuilder(CallerAttrs, AttributeList::ReturnIndex)
  62           .removeAttribute(Attribute::NoAlias)
  63           .removeAttribute(Attribute::NonNull)
  64           .hasAttributes())
  65     return false;
  66
  67   // It's not safe to eliminate the sign / zero extension of the return value.
  68   if (CallerAttrs.hasAttribute(AttributeList::ReturnIndex, Attribute::ZExt) ||
  69       CallerAttrs.hasAttribute(AttributeList::ReturnIndex, Attribute::SExt))
  70     return false;
  71
  72   // Check if the only use is a function return node.
  73   return isUsedByReturnOnly(Node, Chain);
  74 }
  75
  76 bool TargetLowering::parametersInCSRMatch(const MachineRegisterInfo &MRI,
  77     const uint32_t *CallerPreservedMask,
  78     const SmallVectorImpl<CCValAssign> &ArgLocs,
  79     const SmallVectorImpl<SDValue> &OutVals) const {
  80   for (unsigned I = 0, E = ArgLocs.size(); I != E; ++I) {
  81     const CCValAssign &ArgLoc = ArgLocs[I];
  82     if (!ArgLoc.isRegLoc())
  83       continue;
  84     unsigned Reg = ArgLoc.getLocReg();
  85     // Only look at callee saved registers.
  86     if (MachineOperand::clobbersPhysReg(CallerPreservedMask, Reg))
  87       continue;
  88     // Check that we pass the value used for the caller.
  89     // (We look for a CopyFromReg reading a virtual register that is used
  90     //  for the function live-in value of register Reg)
  91     SDValue Value = OutVals[I];
  92     if (Value->getOpcode() != ISD::CopyFromReg)
  93       return false;
  94     unsigned ArgReg = cast<RegisterSDNode>(Value->getOperand(1))->getReg();
  95     if (MRI.getLiveInPhysReg(ArgReg) != Reg)
  96       return false;
  97   }
  98   return true;
  99 }
 100
 101 /// Set CallLoweringInfo attribute flags based on a call instruction
 102 /// and called function attributes.
 103 void TargetLoweringBase::ArgListEntry::setAttributes(ImmutableCallSite *CS,
 104                                                      unsigned ArgIdx) {
 105   IsSExt = CS->paramHasAttr(ArgIdx, Attribute::SExt);
 106   IsZExt = CS->paramHasAttr(ArgIdx, Attribute::ZExt);
 107   IsInReg = CS->paramHasAttr(ArgIdx, Attribute::InReg);
 108   IsSRet = CS->paramHasAttr(ArgIdx, Attribute::StructRet);
 109   IsNest = CS->paramHasAttr(ArgIdx, Attribute::Nest);
 110   IsByVal = CS->paramHasAttr(ArgIdx, Attribute::ByVal);
 111   IsInAlloca = CS->paramHasAttr(ArgIdx, Attribute::InAlloca);
 112   IsReturned = CS->paramHasAttr(ArgIdx, Attribute::Returned);
 113   IsSwiftSelf = CS->paramHasAttr(ArgIdx, Attribute::SwiftSelf);
 114   IsSwiftError = CS->paramHasAttr(ArgIdx, Attribute::SwiftError);
 115   Alignment  = CS->getParamAlignment(ArgIdx);
 116 }
 117
 118 /// Generate a libcall taking the given operands as arguments and returning a
 119 /// result of type RetVT.
 120 std::pair<SDValue, SDValue>
 121 TargetLowering::makeLibCall(SelectionDAG &DAG, RTLIB::Libcall LC, EVT RetVT,
 122                             ArrayRef<SDValue> Ops, bool isSigned,
 123                             const SDLoc &dl, bool doesNotReturn,
 124                             bool isReturnValueUsed) const {
 125   TargetLowering::ArgListTy Args;
 126   Args.reserve(Ops.size());
 127
 128   TargetLowering::ArgListEntry Entry;
 129   for (SDValue Op : Ops) {
 130     Entry.Node = Op;
 131     Entry.Ty = Entry.Node.getValueType().getTypeForEVT(*DAG.getContext());
 132     Entry.IsSExt = shouldSignExtendTypeInLibCall(Op.getValueType(), isSigned);
 133     Entry.IsZExt = !shouldSignExtendTypeInLibCall(Op.getValueType(), isSigned);
 134     Args.push_back(Entry);
 135   }
 136
 137   if (LC == RTLIB::UNKNOWN_LIBCALL)
 138     report_fatal_error("Unsupported library call operation!");
 139   SDValue Callee = DAG.getExternalSymbol(getLibcallName(LC),
 140                                          getPointerTy(DAG.getDataLayout()));
 141
 142   Type *RetTy = RetVT.getTypeForEVT(*DAG.getContext());
 143   TargetLowering::CallLoweringInfo CLI(DAG);
 144   bool signExtend = shouldSignExtendTypeInLibCall(RetVT, isSigned);
 145   CLI.setDebugLoc(dl)
 146       .setChain(DAG.getEntryNode())
 147       .setLibCallee(getLibcallCallingConv(LC), RetTy, Callee, std::move(Args))
 148       .setNoReturn(doesNotReturn)
 149       .setDiscardResult(!isReturnValueUsed)
 150       .setSExtResult(signExtend)
 151       .setZExtResult(!signExtend);
 152   return LowerCallTo(CLI);
 153 }
 154
 155 /// Soften the operands of a comparison. This code is shared among BR_CC,
 156 /// SELECT_CC, and SETCC handlers.
 157 void TargetLowering::softenSetCCOperands(SelectionDAG &DAG, EVT VT,
 158                                          SDValue &NewLHS, SDValue &NewRHS,
 159                                          ISD::CondCode &CCCode,
 160                                          const SDLoc &dl) const {
 161   assert((VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128 || VT == MVT::ppcf128)
 162          && "Unsupported setcc type!");
 163
 164   // Expand into one or more soft-fp libcall(s).
 165   RTLIB::Libcall LC1 = RTLIB::UNKNOWN_LIBCALL, LC2 = RTLIB::UNKNOWN_LIBCALL;
 166   bool ShouldInvertCC = false;
 167   switch (CCCode) {
 168   case ISD::SETEQ:
 169   case ISD::SETOEQ:
 170     LC1 = (VT == MVT::f32) ? RTLIB::OEQ_F32 :
 171           (VT == MVT::f64) ? RTLIB::OEQ_F64 :
 172           (VT == MVT::f128) ? RTLIB::OEQ_F128 : RTLIB::OEQ_PPCF128;
 173     break;
 174   case ISD::SETNE:
 175   case ISD::SETUNE:
 176     LC1 = (VT == MVT::f32) ? RTLIB::UNE_F32 :
 177           (VT == MVT::f64) ? RTLIB::UNE_F64 :
 178           (VT == MVT::f128) ? RTLIB::UNE_F128 : RTLIB::UNE_PPCF128;
 179     break;
 180   case ISD::SETGE:
 181   case ISD::SETOGE:
 182     LC1 = (VT == MVT::f32) ? RTLIB::OGE_F32 :
 183           (VT == MVT::f64) ? RTLIB::OGE_F64 :
 184           (VT == MVT::f128) ? RTLIB::OGE_F128 : RTLIB::OGE_PPCF128;
 185     break;
 186   case ISD::SETLT:
 187   case ISD::SETOLT:
 188     LC1 = (VT == MVT::f32) ? RTLIB::OLT_F32 :
 189           (VT == MVT::f64) ? RTLIB::OLT_F64 :
 190           (VT == MVT::f128) ? RTLIB::OLT_F128 : RTLIB::OLT_PPCF128;
 191     break;
 192   case ISD::SETLE:
 193   case ISD::SETOLE:
 194     LC1 = (VT == MVT::f32) ? RTLIB::OLE_F32 :
 195           (VT == MVT::f64) ? RTLIB::OLE_F64 :
 196           (VT == MVT::f128) ? RTLIB::OLE_F128 : RTLIB::OLE_PPCF128;
 197     break;
 198   case ISD::SETGT:
 199   case ISD::SETOGT:
 200     LC1 = (VT == MVT::f32) ? RTLIB::OGT_F32 :
 201           (VT == MVT::f64) ? RTLIB::OGT_F64 :
 202           (VT == MVT::f128) ? RTLIB::OGT_F128 : RTLIB::OGT_PPCF128;
 203     break;
 204   case ISD::SETUO:
 205     LC1 = (VT == MVT::f32) ? RTLIB::UO_F32 :
 206           (VT == MVT::f64) ? RTLIB::UO_F64 :
 207           (VT == MVT::f128) ? RTLIB::UO_F128 : RTLIB::UO_PPCF128;
 208     break;
 209   case ISD::SETO:
 210     LC1 = (VT == MVT::f32) ? RTLIB::O_F32 :
 211           (VT == MVT::f64) ? RTLIB::O_F64 :
 212           (VT == MVT::f128) ? RTLIB::O_F128 : RTLIB::O_PPCF128;
 213     break;
 214   case ISD::SETONE:
 215     // SETONE = SETOLT | SETOGT
 216     LC1 = (VT == MVT::f32) ? RTLIB::OLT_F32 :
 217           (VT == MVT::f64) ? RTLIB::OLT_F64 :
 218           (VT == MVT::f128) ? RTLIB::OLT_F128 : RTLIB::OLT_PPCF128;
 219     LC2 = (VT == MVT::f32) ? RTLIB::OGT_F32 :
 220           (VT == MVT::f64) ? RTLIB::OGT_F64 :
 221           (VT == MVT::f128) ? RTLIB::OGT_F128 : RTLIB::OGT_PPCF128;
 222     break;
 223   case ISD::SETUEQ:
 224     LC1 = (VT == MVT::f32) ? RTLIB::UO_F32 :
 225           (VT == MVT::f64) ? RTLIB::UO_F64 :
 226           (VT == MVT::f128) ? RTLIB::UO_F128 : RTLIB::UO_PPCF128;
 227     LC2 = (VT == MVT::f32) ? RTLIB::OEQ_F32 :
 228           (VT == MVT::f64) ? RTLIB::OEQ_F64 :
 229           (VT == MVT::f128) ? RTLIB::OEQ_F128 : RTLIB::OEQ_PPCF128;
 230     break;
 231   default:
 232     // Invert CC for unordered comparisons
 233     ShouldInvertCC = true;
 234     switch (CCCode) {
 235     case ISD::SETULT:
 236       LC1 = (VT == MVT::f32) ? RTLIB::OGE_F32 :
 237             (VT == MVT::f64) ? RTLIB::OGE_F64 :
 238             (VT == MVT::f128) ? RTLIB::OGE_F128 : RTLIB::OGE_PPCF128;
 239       break;
 240     case ISD::SETULE:
 241       LC1 = (VT == MVT::f32) ? RTLIB::OGT_F32 :
 242             (VT == MVT::f64) ? RTLIB::OGT_F64 :
 243             (VT == MVT::f128) ? RTLIB::OGT_F128 : RTLIB::OGT_PPCF128;
 244       break;
 245     case ISD::SETUGT:
 246       LC1 = (VT == MVT::f32) ? RTLIB::OLE_F32 :
 247             (VT == MVT::f64) ? RTLIB::OLE_F64 :
 248             (VT == MVT::f128) ? RTLIB::OLE_F128 : RTLIB::OLE_PPCF128;
 249       break;
 250     case ISD::SETUGE:
 251       LC1 = (VT == MVT::f32) ? RTLIB::OLT_F32 :
 252             (VT == MVT::f64) ? RTLIB::OLT_F64 :
 253             (VT == MVT::f128) ? RTLIB::OLT_F128 : RTLIB::OLT_PPCF128;
 254       break;
 255     default: llvm_unreachable("Do not know how to soften this setcc!");
 256     }
 257   }
 258
 259   // Use the target specific return value for comparions lib calls.
 260   EVT RetVT = getCmpLibcallReturnType();
 261   SDValue Ops[2] = {NewLHS, NewRHS};
 262   NewLHS = makeLibCall(DAG, LC1, RetVT, Ops, false /*sign irrelevant*/,
 263                        dl).first;
 264   NewRHS = DAG.getConstant(0, dl, RetVT);
 265
 266   CCCode = getCmpLibcallCC(LC1);
 267   if (ShouldInvertCC)
 268     CCCode = getSetCCInverse(CCCode, /*isInteger=*/true);
 269
 270   if (LC2 != RTLIB::UNKNOWN_LIBCALL) {
 271     SDValue Tmp = DAG.getNode(
 272         ISD::SETCC, dl,
 273         getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), RetVT),
 274         NewLHS, NewRHS, DAG.getCondCode(CCCode));
 275     NewLHS = makeLibCall(DAG, LC2, RetVT, Ops, false/*sign irrelevant*/,
 276                          dl).first;
 277     NewLHS = DAG.getNode(
 278         ISD::SETCC, dl,
 279         getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), RetVT),
 280         NewLHS, NewRHS, DAG.getCondCode(getCmpLibcallCC(LC2)));
 281     NewLHS = DAG.getNode(ISD::OR, dl, Tmp.getValueType(), Tmp, NewLHS);
 282     NewRHS = SDValue();
 283   }
 284 }
 285
 286 /// Return the entry encoding for a jump table in the current function. The
 287 /// returned value is a member of the MachineJumpTableInfo::JTEntryKind enum.
 288 unsigned TargetLowering::getJumpTableEncoding() const {
 289   // In non-pic modes, just use the address of a block.
 290   if (!isPositionIndependent())
 291     return MachineJumpTableInfo::EK_BlockAddress;
 292
 293   // In PIC mode, if the target supports a GPRel32 directive, use it.
 294   if (getTargetMachine().getMCAsmInfo()->getGPRel32Directive() != nullptr)
 295     return MachineJumpTableInfo::EK_GPRel32BlockAddress;
 296
 297   // Otherwise, use a label difference.
 298   return MachineJumpTableInfo::EK_LabelDifference32;
 299 }
 300
 301 SDValue TargetLowering::getPICJumpTableRelocBase(SDValue Table,
 302                                                  SelectionDAG &DAG) const {
 303   // If our PIC model is GP relative, use the global offset table as the base.
 304   unsigned JTEncoding = getJumpTableEncoding();
 305
 306   if ((JTEncoding == MachineJumpTableInfo::EK_GPRel64BlockAddress) ||
 307       (JTEncoding == MachineJumpTableInfo::EK_GPRel32BlockAddress))
 308     return DAG.getGLOBAL_OFFSET_TABLE(getPointerTy(DAG.getDataLayout()));
 309
 310   return Table;
 311 }
 312
 313 /// This returns the relocation base for the given PIC jumptable, the same as
 314 /// getPICJumpTableRelocBase, but as an MCExpr.
 315 const MCExpr *
 316 TargetLowering::getPICJumpTableRelocBaseExpr(const MachineFunction *MF,
 317                                              unsigned JTI,MCContext &Ctx) const{
 318   // The normal PIC reloc base is the label at the start of the jump table.
 319   return MCSymbolRefExpr::create(MF->getJTISymbol(JTI, Ctx), Ctx);
 320 }
 321
 322 bool
 323 TargetLowering::isOffsetFoldingLegal(const GlobalAddressSDNode *GA) const {
 324   const TargetMachine &TM = getTargetMachine();
 325   const GlobalValue *GV = GA->getGlobal();
 326
 327   // If the address is not even local to this DSO we will have to load it from
 328   // a got and then add the offset.
 329   if (!TM.shouldAssumeDSOLocal(*GV->getParent(), GV))
 330     return false;
 331
 332   // If the code is position independent we will have to add a base register.
 333   if (isPositionIndependent())
 334     return false;
 335
 336   // Otherwise we can do it.
 337   return true;
 338 }
 339
 340 //===----------------------------------------------------------------------===//
 341 //  Optimization Methods
 342 //===----------------------------------------------------------------------===//
 343
 344 /// If the specified instruction has a constant integer operand and there are
 345 /// bits set in that constant that are not demanded, then clear those bits and
 346 /// return true.
 347 bool TargetLowering::ShrinkDemandedConstant(SDValue Op, const APInt &Demanded,
 348                                             TargetLoweringOpt &TLO) const {
 349   SelectionDAG &DAG = TLO.DAG;
 350   SDLoc DL(Op);
 351   unsigned Opcode = Op.getOpcode();
 352
 353   // Do target-specific constant optimization.
 354   if (targetShrinkDemandedConstant(Op, Demanded, TLO))
 355     return TLO.New.getNode();
 356
 357   // FIXME: ISD::SELECT, ISD::SELECT_CC
 358   switch (Opcode) {
 359   default:
 360     break;
 361   case ISD::XOR:
 362   case ISD::AND:
 363   case ISD::OR: {
 364     auto *Op1C = dyn_cast<ConstantSDNode>(Op.getOperand(1));
 365     if (!Op1C)
 366       return false;
 367
 368     // If this is a 'not' op, don't touch it because that's a canonical form.
 369     const APInt &C = Op1C->getAPIntValue();
 370     if (Opcode == ISD::XOR && Demanded.isSubsetOf(C))
 371       return false;
 372
 373     if (!C.isSubsetOf(Demanded)) {
 374       EVT VT = Op.getValueType();
 375       SDValue NewC = DAG.getConstant(Demanded & C, DL, VT);
 376       SDValue NewOp = DAG.getNode(Opcode, DL, VT, Op.getOperand(0), NewC);
 377       return TLO.CombineTo(Op, NewOp);
 378     }
 379
 380     break;
 381   }
 382   }
 383
 384   return false;
 385 }
 386
 387 /// Convert x+y to (VT)((SmallVT)x+(SmallVT)y) if the casts are free.
 388 /// This uses isZExtFree and ZERO_EXTEND for the widening cast, but it could be
 389 /// generalized for targets with other types of implicit widening casts.
 390 bool TargetLowering::ShrinkDemandedOp(SDValue Op, unsigned BitWidth,
 391                                       const APInt &Demanded,
 392                                       TargetLoweringOpt &TLO) const {
 393   assert(Op.getNumOperands() == 2 &&
 394          "ShrinkDemandedOp only supports binary operators!");
 395   assert(Op.getNode()->getNumValues() == 1 &&
 396          "ShrinkDemandedOp only supports nodes with one result!");
 397
 398   SelectionDAG &DAG = TLO.DAG;
 399   SDLoc dl(Op);
 400
 401   // Early return, as this function cannot handle vector types.
 402   if (Op.getValueType().isVector())
 403     return false;
 404
 405   // Don't do this if the node has another user, which may require the
 406   // full value.
 407   if (!Op.getNode()->hasOneUse())
 408     return false;
 409
 410   // Search for the smallest integer type with free casts to and from
 411   // Op's type. For expedience, just check power-of-2 integer types.
 412   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
 413   unsigned DemandedSize = Demanded.getActiveBits();
 414   unsigned SmallVTBits = DemandedSize;
 415   if (!isPowerOf2_32(SmallVTBits))
 416     SmallVTBits = NextPowerOf2(SmallVTBits);
 417   for (; SmallVTBits < BitWidth; SmallVTBits = NextPowerOf2(SmallVTBits)) {
 418     EVT SmallVT = EVT::getIntegerVT(*DAG.getContext(), SmallVTBits);
 419     if (TLI.isTruncateFree(Op.getValueType(), SmallVT) &&
 420         TLI.isZExtFree(SmallVT, Op.getValueType())) {
 421       // We found a type with free casts.
 422       SDValue X = DAG.getNode(
 423           Op.getOpcode(), dl, SmallVT,
 424           DAG.getNode(ISD::TRUNCATE, dl, SmallVT, Op.getOperand(0)),
 425           DAG.getNode(ISD::TRUNCATE, dl, SmallVT, Op.getOperand(1)));
 426       assert(DemandedSize <= SmallVTBits && "Narrowed below demanded bits?");
 427       SDValue Z = DAG.getNode(ISD::ANY_EXTEND, dl, Op.getValueType(), X);
 428       return TLO.CombineTo(Op, Z);
 429     }
 430   }
 431   return false;
 432 }
 433
 434 bool
 435 TargetLowering::SimplifyDemandedBits(SDNode *User, unsigned OpIdx,
 436                                      const APInt &DemandedBits,
 437                                      DAGCombinerInfo &DCI,
 438                                      TargetLoweringOpt &TLO) const {
 439   SDValue Op = User->getOperand(OpIdx);
 440   KnownBits Known;
 441
 442   if (!SimplifyDemandedBits(Op, DemandedBits, Known, TLO, 0, true))
 443     return false;
 444
 445
 446   // Old will not always be the same as Op.  For example:
 447   //
 448   // Demanded = 0xffffff
 449   // Op = i64 truncate (i32 and x, 0xffffff)
 450   // In this case simplify demand bits will want to replace the 'and' node
 451   // with the value 'x', which will give us:
 452   // Old = i32 and x, 0xffffff
 453   // New = x
 454   if (TLO.Old.hasOneUse()) {
 455     // For the one use case, we just commit the change.
 456     DCI.CommitTargetLoweringOpt(TLO);
 457     return true;
 458   }
 459
 460   // If Old has more than one use then it must be Op, because the
 461   // AssumeSingleUse flag is not propogated to recursive calls of
 462   // SimplifyDemanded bits, so the only node with multiple use that
 463   // it will attempt to combine will be Op.
 464   assert(TLO.Old == Op);
 465
 466   SmallVector <SDValue, 4> NewOps;
 467   for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i) {
 468     if (i == OpIdx) {
 469       NewOps.push_back(TLO.New);
 470       continue;
 471     }
 472     NewOps.push_back(User->getOperand(i));
 473   }
 474   User = TLO.DAG.UpdateNodeOperands(User, NewOps);
 475   // Op has less users now, so we may be able to perform additional combines
 476   // with it.
 477   DCI.AddToWorklist(Op.getNode());
 478   // User's operands have been updated, so we may be able to do new combines
 479   // with it.
 480   DCI.AddToWorklist(User);
 481   return true;
 482 }
 483
 484 bool TargetLowering::SimplifyDemandedBits(SDValue Op, const APInt &DemandedBits,
 485                                           DAGCombinerInfo &DCI) const {
 486   SelectionDAG &DAG = DCI.DAG;
 487   TargetLoweringOpt TLO(DAG, !DCI.isBeforeLegalize(),
 488                         !DCI.isBeforeLegalizeOps());
 489   KnownBits Known;
 490
 491   bool Simplified = SimplifyDemandedBits(Op, DemandedBits, Known, TLO);
 492   if (Simplified) {
 493     DCI.AddToWorklist(Op.getNode());
 494     DCI.CommitTargetLoweringOpt(TLO);
 495   }
 496   return Simplified;
 497 }
 498
 499 /// Look at Op. At this point, we know that only the OriginalDemandedBits of the
 500 /// result of Op are ever used downstream. If we can use this information to
 501 /// simplify Op, create a new simplified DAG node and return true, returning the
 502 /// original and new nodes in Old and New. Otherwise, analyze the expression and
 503 /// return a mask of Known bits for the expression (used to simplify the
 504 /// caller).  The Known bits may only be accurate for those bits in the
 505 /// DemandedMask.
 506 bool TargetLowering::SimplifyDemandedBits(SDValue Op,
 507                                           const APInt &OriginalDemandedBits,
 508                                           KnownBits &Known,
 509                                           TargetLoweringOpt &TLO,
 510                                           unsigned Depth,
 511                                           bool AssumeSingleUse) const {
 512   unsigned BitWidth = OriginalDemandedBits.getBitWidth();
 513   assert(Op.getScalarValueSizeInBits() == BitWidth &&
 514          "Mask size mismatches value type size!");
 515   APInt DemandedBits = OriginalDemandedBits;
 516   SDLoc dl(Op);
 517   auto &DL = TLO.DAG.getDataLayout();
 518
 519   // Don't know anything.
 520   Known = KnownBits(BitWidth);
 521
 522   if (Op.getOpcode() == ISD::Constant) {
 523     // We know all of the bits for a constant!
 524     Known.One = cast<ConstantSDNode>(Op)->getAPIntValue();
 525     Known.Zero = ~Known.One;
 526     return false;
 527   }
 528
 529   // Other users may use these bits.
 530   EVT VT = Op.getValueType();
 531   if (!Op.getNode()->hasOneUse() && !AssumeSingleUse) {
 532     if (Depth != 0) {
 533       // If not at the root, Just compute the Known bits to
 534       // simplify things downstream.
 535       TLO.DAG.computeKnownBits(Op, Known, Depth);
 536       return false;
 537     }
 538     // If this is the root being simplified, allow it to have multiple uses,
 539     // just set the DemandedBits to all bits.
 540     DemandedBits = APInt::getAllOnesValue(BitWidth);
 541   } else if (OriginalDemandedBits == 0) {
 542     // Not demanding any bits from Op.
 543     if (!Op.isUndef())
 544       return TLO.CombineTo(Op, TLO.DAG.getUNDEF(VT));
 545     return false;
 546   } else if (Depth == 6) {        // Limit search depth.
 547     return false;
 548   }
 549
 550   KnownBits Known2, KnownOut;
 551   switch (Op.getOpcode()) {
 552   case ISD::BUILD_VECTOR:
 553     // Collect the known bits that are shared by every constant vector element.
 554     Known.Zero.setAllBits(); Known.One.setAllBits();
 555     for (SDValue SrcOp : Op->ops()) {
 556       if (!isa<ConstantSDNode>(SrcOp)) {
 557         // We can only handle all constant values - bail out with no known bits.
 558         Known = KnownBits(BitWidth);
 559         return false;
 560       }
 561       Known2.One = cast<ConstantSDNode>(SrcOp)->getAPIntValue();
 562       Known2.Zero = ~Known2.One;
 563
 564       // BUILD_VECTOR can implicitly truncate sources, we must handle this.
 565       if (Known2.One.getBitWidth() != BitWidth) {
 566         assert(Known2.getBitWidth() > BitWidth &&
 567                "Expected BUILD_VECTOR implicit truncation");
 568         Known2 = Known2.trunc(BitWidth);
 569       }
 570
 571       // Known bits are the values that are shared by every element.
 572       // TODO: support per-element known bits.
 573       Known.One &= Known2.One;
 574       Known.Zero &= Known2.Zero;
 575     }
 576     return false;   // Don't fall through, will infinitely loop.
 577   case ISD::CONCAT_VECTORS:
 578     Known.Zero.setAllBits();
 579     Known.One.setAllBits();
 580     for (SDValue SrcOp : Op->ops()) {
 581       if (SimplifyDemandedBits(SrcOp, DemandedBits, Known2, TLO, Depth + 1))
 582         return true;
 583       // Known bits are the values that are shared by every subvector.
 584       Known.One &= Known2.One;
 585       Known.Zero &= Known2.Zero;
 586     }
 587     break;
 588   case ISD::AND: {
 589     SDValue Op0 = Op.getOperand(0);
 590     SDValue Op1 = Op.getOperand(1);
 591
 592     // If the RHS is a constant, check to see if the LHS would be zero without
 593     // using the bits from the RHS.  Below, we use knowledge about the RHS to
 594     // simplify the LHS, here we're using information from the LHS to simplify
 595     // the RHS.
 596     if (ConstantSDNode *RHSC = isConstOrConstSplat(Op1)) {
 597       KnownBits LHSKnown;
 598       // Do not increment Depth here; that can cause an infinite loop.
 599       TLO.DAG.computeKnownBits(Op0, LHSKnown, Depth);
 600       // If the LHS already has zeros where RHSC does, this 'and' is dead.
 601       if ((LHSKnown.Zero & DemandedBits) ==
 602           (~RHSC->getAPIntValue() & DemandedBits))
 603         return TLO.CombineTo(Op, Op0);
 604
 605       // If any of the set bits in the RHS are known zero on the LHS, shrink
 606       // the constant.
 607       if (ShrinkDemandedConstant(Op, ~LHSKnown.Zero & DemandedBits, TLO))
 608         return true;
 609
 610       // Bitwise-not (xor X, -1) is a special case: we don't usually shrink its
 611       // constant, but if this 'and' is only clearing bits that were just set by
 612       // the xor, then this 'and' can be eliminated by shrinking the mask of
 613       // the xor. For example, for a 32-bit X:
 614       // and (xor (srl X, 31), -1), 1 --> xor (srl X, 31), 1
 615       if (isBitwiseNot(Op0) && Op0.hasOneUse() &&
 616           LHSKnown.One == ~RHSC->getAPIntValue()) {
 617         SDValue Xor = TLO.DAG.getNode(ISD::XOR, dl, VT, Op0.getOperand(0), Op1);
 618         return TLO.CombineTo(Op, Xor);
 619       }
 620     }
 621
 622     if (SimplifyDemandedBits(Op1, DemandedBits, Known, TLO, Depth + 1))
 623       return true;
 624     assert(!Known.hasConflict() && "Bits known to be one AND zero?");
 625     if (SimplifyDemandedBits(Op0, ~Known.Zero & DemandedBits, Known2, TLO,
 626                              Depth + 1))
 627       return true;
 628     assert(!Known2.hasConflict() && "Bits known to be one AND zero?");
 629
 630     // If all of the demanded bits are known one on one side, return the other.
 631     // These bits cannot contribute to the result of the 'and'.
 632     if (DemandedBits.isSubsetOf(Known2.Zero | Known.One))
 633       return TLO.CombineTo(Op, Op0);
 634     if (DemandedBits.isSubsetOf(Known.Zero | Known2.One))
 635       return TLO.CombineTo(Op, Op1);
 636     // If all of the demanded bits in the inputs are known zeros, return zero.
 637     if (DemandedBits.isSubsetOf(Known.Zero | Known2.Zero))
 638       return TLO.CombineTo(Op, TLO.DAG.getConstant(0, dl, VT));
 639     // If the RHS is a constant, see if we can simplify it.
 640     if (ShrinkDemandedConstant(Op, ~Known2.Zero & DemandedBits, TLO))
 641       return true;
 642     // If the operation can be done in a smaller type, do so.
 643     if (ShrinkDemandedOp(Op, BitWidth, DemandedBits, TLO))
 644       return true;
 645
 646     // Output known-1 bits are only known if set in both the LHS & RHS.
 647     Known.One &= Known2.One;
 648     // Output known-0 are known to be clear if zero in either the LHS | RHS.
 649     Known.Zero |= Known2.Zero;
 650     break;
 651   }
 652   case ISD::OR: {
 653     SDValue Op0 = Op.getOperand(0);
 654     SDValue Op1 = Op.getOperand(1);
 655
 656     if (SimplifyDemandedBits(Op1, DemandedBits, Known, TLO, Depth + 1))
 657       return true;
 658     assert(!Known.hasConflict() && "Bits known to be one AND zero?");
 659     if (SimplifyDemandedBits(Op0, ~Known.One & DemandedBits, Known2, TLO, Depth + 1))
 660       return true;
 661     assert(!Known2.hasConflict() && "Bits known to be one AND zero?");
 662
 663     // If all of the demanded bits are known zero on one side, return the other.
 664     // These bits cannot contribute to the result of the 'or'.
 665     if (DemandedBits.isSubsetOf(Known2.One | Known.Zero))
 666       return TLO.CombineTo(Op, Op0);
 667     if (DemandedBits.isSubsetOf(Known.One | Known2.Zero))
 668       return TLO.CombineTo(Op, Op1);
 669     // If the RHS is a constant, see if we can simplify it.
 670     if (ShrinkDemandedConstant(Op, DemandedBits, TLO))
 671       return true;
 672     // If the operation can be done in a smaller type, do so.
 673     if (ShrinkDemandedOp(Op, BitWidth, DemandedBits, TLO))
 674       return true;
 675
 676     // Output known-0 bits are only known if clear in both the LHS & RHS.
 677     Known.Zero &= Known2.Zero;
 678     // Output known-1 are known to be set if set in either the LHS | RHS.
 679     Known.One |= Known2.One;
 680     break;
 681   }
 682   case ISD::XOR: {
 683     SDValue Op0 = Op.getOperand(0);
 684     SDValue Op1 = Op.getOperand(1);
 685
 686     if (SimplifyDemandedBits(Op1, DemandedBits, Known, TLO, Depth + 1))
 687       return true;
 688     assert(!Known.hasConflict() && "Bits known to be one AND zero?");
 689     if (SimplifyDemandedBits(Op0, DemandedBits, Known2, TLO, Depth + 1))
 690       return true;
 691     assert(!Known2.hasConflict() && "Bits known to be one AND zero?");
 692
 693     // If all of the demanded bits are known zero on one side, return the other.
 694     // These bits cannot contribute to the result of the 'xor'.
 695     if (DemandedBits.isSubsetOf(Known.Zero))
 696       return TLO.CombineTo(Op, Op0);
 697     if (DemandedBits.isSubsetOf(Known2.Zero))
 698       return TLO.CombineTo(Op, Op1);
 699     // If the operation can be done in a smaller type, do so.
 700     if (ShrinkDemandedOp(Op, BitWidth, DemandedBits, TLO))
 701       return true;
 702
 703     // If all of the unknown bits are known to be zero on one side or the other
 704     // (but not both) turn this into an *inclusive* or.
 705     //    e.g. (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0
 706     if (DemandedBits.isSubsetOf(Known.Zero | Known2.Zero))
 707       return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::OR, dl, VT, Op0, Op1));
 708
 709     // Output known-0 bits are known if clear or set in both the LHS & RHS.
 710     KnownOut.Zero = (Known.Zero & Known2.Zero) | (Known.One & Known2.One);
 711     // Output known-1 are known to be set if set in only one of the LHS, RHS.
 712     KnownOut.One = (Known.Zero & Known2.One) | (Known.One & Known2.Zero);
 713
 714     if (ConstantSDNode *C = isConstOrConstSplat(Op1)) {
 715       // If one side is a constant, and all of the known set bits on the other
 716       // side are also set in the constant, turn this into an AND, as we know
 717       // the bits will be cleared.
 718       //    e.g. (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2
 719       // NB: it is okay if more bits are known than are requested
 720       if (C->getAPIntValue() == Known2.One) {
 721         SDValue ANDC =
 722             TLO.DAG.getConstant(~C->getAPIntValue() & DemandedBits, dl, VT);
 723         return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::AND, dl, VT, Op0, ANDC));
 724       }
 725
 726       // If the RHS is a constant, see if we can change it. Don't alter a -1
 727       // constant because that's a 'not' op, and that is better for combining
 728       // and codegen.
 729       if (!C->isAllOnesValue()) {
 730         if (DemandedBits.isSubsetOf(C->getAPIntValue())) {
 731           // We're flipping all demanded bits. Flip the undemanded bits too.
 732           SDValue New = TLO.DAG.getNOT(dl, Op0, VT);
 733           return TLO.CombineTo(Op, New);
 734         }
 735         // If we can't turn this into a 'not', try to shrink the constant.
 736         if (ShrinkDemandedConstant(Op, DemandedBits, TLO))
 737           return true;
 738       }
 739     }
 740
 741     Known = std::move(KnownOut);
 742     break;
 743   }
 744   case ISD::SELECT:
 745     if (SimplifyDemandedBits(Op.getOperand(2), DemandedBits, Known, TLO,
 746                              Depth + 1))
 747       return true;
 748     if (SimplifyDemandedBits(Op.getOperand(1), DemandedBits, Known2, TLO,
 749                              Depth + 1))
 750       return true;
 751     assert(!Known.hasConflict() && "Bits known to be one AND zero?");
 752     assert(!Known2.hasConflict() && "Bits known to be one AND zero?");
 753
 754     // If the operands are constants, see if we can simplify them.
 755     if (ShrinkDemandedConstant(Op, DemandedBits, TLO))
 756       return true;
 757
 758     // Only known if known in both the LHS and RHS.
 759     Known.One &= Known2.One;
 760     Known.Zero &= Known2.Zero;
 761     break;
 762   case ISD::SELECT_CC:
 763     if (SimplifyDemandedBits(Op.getOperand(3), DemandedBits, Known, TLO,
 764                              Depth + 1))
 765       return true;
 766     if (SimplifyDemandedBits(Op.getOperand(2), DemandedBits, Known2, TLO,
 767                              Depth + 1))
 768       return true;
 769     assert(!Known.hasConflict() && "Bits known to be one AND zero?");
 770     assert(!Known2.hasConflict() && "Bits known to be one AND zero?");
 771
 772     // If the operands are constants, see if we can simplify them.
 773     if (ShrinkDemandedConstant(Op, DemandedBits, TLO))
 774       return true;
 775
 776     // Only known if known in both the LHS and RHS.
 777     Known.One &= Known2.One;
 778     Known.Zero &= Known2.Zero;
 779     break;
 780   case ISD::SETCC: {
 781     SDValue Op0 = Op.getOperand(0);
 782     SDValue Op1 = Op.getOperand(1);
 783     ISD::CondCode CC = cast<CondCodeSDNode>(Op.getOperand(2))->get();
 784     // If (1) we only need the sign-bit, (2) the setcc operands are the same
 785     // width as the setcc result, and (3) the result of a setcc conforms to 0 or
 786     // -1, we may be able to bypass the setcc.
 787     if (DemandedBits.isSignMask() &&
 788         Op0.getScalarValueSizeInBits() == BitWidth &&
 789         getBooleanContents(VT) ==
 790             BooleanContent::ZeroOrNegativeOneBooleanContent) {
 791       // If we're testing X < 0, then this compare isn't needed - just use X!
 792       // FIXME: We're limiting to integer types here, but this should also work
 793       // if we don't care about FP signed-zero. The use of SETLT with FP means
 794       // that we don't care about NaNs.
 795       if (CC == ISD::SETLT && Op1.getValueType().isInteger() &&
 796           (isNullConstant(Op1) || ISD::isBuildVectorAllZeros(Op1.getNode())))
 797         return TLO.CombineTo(Op, Op0);
 798
 799       // TODO: Should we check for other forms of sign-bit comparisons?
 800       // Examples: X <= -1, X >= 0
 801     }
 802     if (getBooleanContents(Op0.getValueType()) ==
 803             TargetLowering::ZeroOrOneBooleanContent &&
 804         BitWidth > 1)
 805       Known.Zero.setBitsFrom(1);
 806     break;
 807   }
 808   case ISD::SHL: {
 809     SDValue Op0 = Op.getOperand(0);
 810     SDValue Op1 = Op.getOperand(1);
 811
 812     if (ConstantSDNode *SA = isConstOrConstSplat(Op1)) {
 813       // If the shift count is an invalid immediate, don't do anything.
 814       if (SA->getAPIntValue().uge(BitWidth))
 815         break;
 816
 817       unsigned ShAmt = SA->getZExtValue();
 818
 819       // If this is ((X >>u C1) << ShAmt), see if we can simplify this into a
 820       // single shift.  We can do this if the bottom bits (which are shifted
 821       // out) are never demanded.
 822       if (Op0.getOpcode() == ISD::SRL) {
 823         if (ShAmt &&
 824             (DemandedBits & APInt::getLowBitsSet(BitWidth, ShAmt)) == 0) {
 825           if (ConstantSDNode *SA2 = isConstOrConstSplat(Op0.getOperand(1))) {
 826             if (SA2->getAPIntValue().ult(BitWidth)) {
 827               unsigned C1 = SA2->getZExtValue();
 828               unsigned Opc = ISD::SHL;
 829               int Diff = ShAmt - C1;
 830               if (Diff < 0) {
 831                 Diff = -Diff;
 832                 Opc = ISD::SRL;
 833               }
 834
 835               SDValue NewSA = TLO.DAG.getConstant(Diff, dl, Op1.getValueType());
 836               return TLO.CombineTo(
 837                   Op, TLO.DAG.getNode(Opc, dl, VT, Op0.getOperand(0), NewSA));
 838             }
 839           }
 840         }
 841       }
 842
 843       if (SimplifyDemandedBits(Op0, DemandedBits.lshr(ShAmt), Known, TLO,
 844                                Depth + 1))
 845         return true;
 846
 847       // Convert (shl (anyext x, c)) to (anyext (shl x, c)) if the high bits
 848       // are not demanded. This will likely allow the anyext to be folded away.
 849       if (Op0.getOpcode() == ISD::ANY_EXTEND) {
 850         SDValue InnerOp = Op0.getOperand(0);
 851         EVT InnerVT = InnerOp.getValueType();
 852         unsigned InnerBits = InnerVT.getScalarSizeInBits();
 853         if (ShAmt < InnerBits && DemandedBits.getActiveBits() <= InnerBits &&
 854             isTypeDesirableForOp(ISD::SHL, InnerVT)) {
 855           EVT ShTy = getShiftAmountTy(InnerVT, DL);
 856           if (!APInt(BitWidth, ShAmt).isIntN(ShTy.getSizeInBits()))
 857             ShTy = InnerVT;
 858           SDValue NarrowShl =
 859               TLO.DAG.getNode(ISD::SHL, dl, InnerVT, InnerOp,
 860                               TLO.DAG.getConstant(ShAmt, dl, ShTy));
 861           return TLO.CombineTo(
 862               Op, TLO.DAG.getNode(ISD::ANY_EXTEND, dl, VT, NarrowShl));
 863         }
 864         // Repeat the SHL optimization above in cases where an extension
 865         // intervenes: (shl (anyext (shr x, c1)), c2) to
 866         // (shl (anyext x), c2-c1).  This requires that the bottom c1 bits
 867         // aren't demanded (as above) and that the shifted upper c1 bits of
 868         // x aren't demanded.
 869         if (Op0.hasOneUse() && InnerOp.getOpcode() == ISD::SRL &&
 870             InnerOp.hasOneUse()) {
 871           if (ConstantSDNode *SA2 =
 872                   isConstOrConstSplat(InnerOp.getOperand(1))) {
 873             unsigned InnerShAmt = SA2->getLimitedValue(InnerBits);
 874             if (InnerShAmt < ShAmt && InnerShAmt < InnerBits &&
 875                 DemandedBits.getActiveBits() <=
 876                     (InnerBits - InnerShAmt + ShAmt) &&
 877                 DemandedBits.countTrailingZeros() >= ShAmt) {
 878               SDValue NewSA = TLO.DAG.getConstant(ShAmt - InnerShAmt, dl,
 879                                                   Op1.getValueType());
 880               SDValue NewExt = TLO.DAG.getNode(ISD::ANY_EXTEND, dl, VT,
 881                                                InnerOp.getOperand(0));
 882               return TLO.CombineTo(
 883                   Op, TLO.DAG.getNode(ISD::SHL, dl, VT, NewExt, NewSA));
 884             }
 885           }
 886         }
 887       }
 888
 889       Known.Zero <<= ShAmt;
 890       Known.One <<= ShAmt;
 891       // low bits known zero.
 892       Known.Zero.setLowBits(ShAmt);
 893     }
 894     break;
 895   }
 896   case ISD::SRL: {
 897     SDValue Op0 = Op.getOperand(0);
 898     SDValue Op1 = Op.getOperand(1);
 899
 900     if (ConstantSDNode *SA = isConstOrConstSplat(Op1)) {
 901       // If the shift count is an invalid immediate, don't do anything.
 902       if (SA->getAPIntValue().uge(BitWidth))
 903         break;
 904
 905       unsigned ShAmt = SA->getZExtValue();
 906       APInt InDemandedMask = (DemandedBits << ShAmt);
 907
 908       // If the shift is exact, then it does demand the low bits (and knows that
 909       // they are zero).
 910       if (Op->getFlags().hasExact())
 911         InDemandedMask.setLowBits(ShAmt);
 912
 913       // If this is ((X << C1) >>u ShAmt), see if we can simplify this into a
 914       // single shift.  We can do this if the top bits (which are shifted out)
 915       // are never demanded.
 916       if (Op0.getOpcode() == ISD::SHL) {
 917         if (ConstantSDNode *SA2 = isConstOrConstSplat(Op0.getOperand(1))) {
 918           if (ShAmt &&
 919               (DemandedBits & APInt::getHighBitsSet(BitWidth, ShAmt)) == 0) {
 920             if (SA2->getAPIntValue().ult(BitWidth)) {
 921               unsigned C1 = SA2->getZExtValue();
 922               unsigned Opc = ISD::SRL;
 923               int Diff = ShAmt - C1;
 924               if (Diff < 0) {
 925                 Diff = -Diff;
 926                 Opc = ISD::SHL;
 927               }
 928
 929               SDValue NewSA = TLO.DAG.getConstant(Diff, dl, Op1.getValueType());
 930               return TLO.CombineTo(
 931                   Op, TLO.DAG.getNode(Opc, dl, VT, Op0.getOperand(0), NewSA));
 932             }
 933           }
 934         }
 935       }
 936
 937       // Compute the new bits that are at the top now.
 938       if (SimplifyDemandedBits(Op0, InDemandedMask, Known, TLO, Depth + 1))
 939         return true;
 940       assert(!Known.hasConflict() && "Bits known to be one AND zero?");
 941       Known.Zero.lshrInPlace(ShAmt);
 942       Known.One.lshrInPlace(ShAmt);
 943
 944       Known.Zero.setHighBits(ShAmt); // High bits known zero.
 945     }
 946     break;
 947   }
 948   case ISD::SRA: {
 949     SDValue Op0 = Op.getOperand(0);
 950     SDValue Op1 = Op.getOperand(1);
 951
 952     // If this is an arithmetic shift right and only the low-bit is set, we can
 953     // always convert this into a logical shr, even if the shift amount is
 954     // variable.  The low bit of the shift cannot be an input sign bit unless
 955     // the shift amount is >= the size of the datatype, which is undefined.
 956     if (DemandedBits.isOneValue())
 957       return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SRL, dl, VT, Op0, Op1));
 958
 959     if (ConstantSDNode *SA = isConstOrConstSplat(Op1)) {
 960       // If the shift count is an invalid immediate, don't do anything.
 961       if (SA->getAPIntValue().uge(BitWidth))
 962         break;
 963
 964       unsigned ShAmt = SA->getZExtValue();
 965       APInt InDemandedMask = (DemandedBits << ShAmt);
 966
 967       // If the shift is exact, then it does demand the low bits (and knows that
 968       // they are zero).
 969       if (Op->getFlags().hasExact())
 970         InDemandedMask.setLowBits(ShAmt);
 971
 972       // If any of the demanded bits are produced by the sign extension, we also
 973       // demand the input sign bit.
 974       if (DemandedBits.countLeadingZeros() < ShAmt)
 975         InDemandedMask.setSignBit();
 976
 977       if (SimplifyDemandedBits(Op0, InDemandedMask, Known, TLO, Depth + 1))
 978         return true;
 979       assert(!Known.hasConflict() && "Bits known to be one AND zero?");
 980       Known.Zero.lshrInPlace(ShAmt);
 981       Known.One.lshrInPlace(ShAmt);
 982
 983       // If the input sign bit is known to be zero, or if none of the top bits
 984       // are demanded, turn this into an unsigned shift right.
 985       if (Known.Zero[BitWidth - ShAmt - 1] ||
 986           DemandedBits.countLeadingZeros() >= ShAmt) {
 987         SDNodeFlags Flags;
 988         Flags.setExact(Op->getFlags().hasExact());
 989         return TLO.CombineTo(
 990             Op, TLO.DAG.getNode(ISD::SRL, dl, VT, Op0, Op1, Flags));
 991       }
 992
 993       int Log2 = DemandedBits.exactLogBase2();
 994       if (Log2 >= 0) {
 995         // The bit must come from the sign.
 996         SDValue NewSA =
 997             TLO.DAG.getConstant(BitWidth - 1 - Log2, dl, Op1.getValueType());
 998         return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SRL, dl, VT, Op0, NewSA));
 999       }
1000
1001       if (Known.One[BitWidth - ShAmt - 1])
1002         // New bits are known one.
1003         Known.One.setHighBits(ShAmt);
1004     }
1005     break;
1006   }
1007   case ISD::SIGN_EXTEND_INREG: {
1008     SDValue Op0 = Op.getOperand(0);
1009     EVT ExVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1010     unsigned ExVTBits = ExVT.getScalarSizeInBits();
1011
1012     // If we only care about the highest bit, don't bother shifting right.
1013     if (DemandedBits.isSignMask()) {
1014       bool AlreadySignExtended =
1015           TLO.DAG.ComputeNumSignBits(Op0) >= BitWidth - ExVTBits + 1;
1016       // However if the input is already sign extended we expect the sign
1017       // extension to be dropped altogether later and do not simplify.
1018       if (!AlreadySignExtended) {
1019         // Compute the correct shift amount type, which must be getShiftAmountTy
1020         // for scalar types after legalization.
1021         EVT ShiftAmtTy = VT;
1022         if (TLO.LegalTypes() && !ShiftAmtTy.isVector())
1023           ShiftAmtTy = getShiftAmountTy(ShiftAmtTy, DL);
1024
1025         SDValue ShiftAmt =
1026             TLO.DAG.getConstant(BitWidth - ExVTBits, dl, ShiftAmtTy);
1027         return TLO.CombineTo(Op,
1028                              TLO.DAG.getNode(ISD::SHL, dl, VT, Op0, ShiftAmt));
1029       }
1030     }
1031
1032     // If none of the extended bits are demanded, eliminate the sextinreg.
1033     if (DemandedBits.getActiveBits() <= ExVTBits)
1034       return TLO.CombineTo(Op, Op0);
1035
1036     APInt InputDemandedBits = DemandedBits.getLoBits(ExVTBits);
1037
1038     // Since the sign extended bits are demanded, we know that the sign
1039     // bit is demanded.
1040     InputDemandedBits.setBit(ExVTBits - 1);
1041
1042     if (SimplifyDemandedBits(Op0, InputDemandedBits, Known, TLO, Depth + 1))
1043       return true;
1044     assert(!Known.hasConflict() && "Bits known to be one AND zero?");
1045
1046     // If the sign bit of the input is known set or clear, then we know the
1047     // top bits of the result.
1048
1049     // If the input sign bit is known zero, convert this into a zero extension.
1050     if (Known.Zero[ExVTBits - 1])
1051       return TLO.CombineTo(
1052           Op, TLO.DAG.getZeroExtendInReg(Op0, dl, ExVT.getScalarType()));
1053
1054     APInt Mask = APInt::getLowBitsSet(BitWidth, ExVTBits);
1055     if (Known.One[ExVTBits - 1]) { // Input sign bit known set
1056       Known.One.setBitsFrom(ExVTBits);
1057       Known.Zero &= Mask;
1058     } else { // Input sign bit unknown
1059       Known.Zero &= Mask;
1060       Known.One &= Mask;
1061     }
1062     break;
1063   }
1064   case ISD::BUILD_PAIR: {
1065     EVT HalfVT = Op.getOperand(0).getValueType();
1066     unsigned HalfBitWidth = HalfVT.getScalarSizeInBits();
1067
1068     APInt MaskLo = DemandedBits.getLoBits(HalfBitWidth).trunc(HalfBitWidth);
1069     APInt MaskHi = DemandedBits.getHiBits(HalfBitWidth).trunc(HalfBitWidth);
1070
1071     KnownBits KnownLo, KnownHi;
1072
1073     if (SimplifyDemandedBits(Op.getOperand(0), MaskLo, KnownLo, TLO, Depth + 1))
1074       return true;
1075
1076     if (SimplifyDemandedBits(Op.getOperand(1), MaskHi, KnownHi, TLO, Depth + 1))
1077       return true;
1078
1079     Known.Zero = KnownLo.Zero.zext(BitWidth) |
1080                 KnownHi.Zero.zext(BitWidth).shl(HalfBitWidth);
1081
1082     Known.One = KnownLo.One.zext(BitWidth) |
1083                KnownHi.One.zext(BitWidth).shl(HalfBitWidth);
1084     break;
1085   }
1086   case ISD::ZERO_EXTEND: {
1087     SDValue Src = Op.getOperand(0);
1088     unsigned InBits = Src.getScalarValueSizeInBits();
1089
1090     // If none of the top bits are demanded, convert this into an any_extend.
1091     if (DemandedBits.getActiveBits() <= InBits)
1092       return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ANY_EXTEND, dl, VT, Src));
1093
1094     APInt InDemandedBits = DemandedBits.trunc(InBits);
1095     if (SimplifyDemandedBits(Src, InDemandedBits, Known, TLO, Depth+1))
1096       return true;
1097     assert(!Known.hasConflict() && "Bits known to be one AND zero?");
1098     Known = Known.zext(BitWidth);
1099     Known.Zero.setBitsFrom(InBits);
1100     break;
1101   }
1102   case ISD::SIGN_EXTEND: {
1103     SDValue Src = Op.getOperand(0);
1104     unsigned InBits = Src.getScalarValueSizeInBits();
1105
1106     // If none of the top bits are demanded, convert this into an any_extend.
1107     if (DemandedBits.getActiveBits() <= InBits)
1108       return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ANY_EXTEND, dl, VT, Src));
1109
1110     // Since some of the sign extended bits are demanded, we know that the sign
1111     // bit is demanded.
1112     APInt InDemandedBits = DemandedBits.trunc(InBits);
1113     InDemandedBits.setBit(InBits - 1);
1114
1115     if (SimplifyDemandedBits(Src, InDemandedBits, Known, TLO, Depth + 1))
1116       return true;
1117     assert(!Known.hasConflict() && "Bits known to be one AND zero?");
1118     // If the sign bit is known one, the top bits match.
1119     Known = Known.sext(BitWidth);
1120
1121     // If the sign bit is known zero, convert this to a zero extend.
1122     if (Known.isNonNegative())
1123       return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Src));
1124     break;
1125   }
1126   case ISD::SIGN_EXTEND_VECTOR_INREG: {
1127     // TODO - merge this with SIGN_EXTEND above?
1128     SDValue Src = Op.getOperand(0);
1129     unsigned InBits = Src.getScalarValueSizeInBits();
1130
1131     APInt InDemandedBits = DemandedBits.trunc(InBits);
1132
1133     // If some of the sign extended bits are demanded, we know that the sign
1134     // bit is demanded.
1135     if (InBits < DemandedBits.getActiveBits())
1136       InDemandedBits.setBit(InBits - 1);
1137
1138     if (SimplifyDemandedBits(Src, InDemandedBits, Known, TLO, Depth + 1))
1139       return true;
1140     assert(!Known.hasConflict() && "Bits known to be one AND zero?");
1141     // If the sign bit is known one, the top bits match.
1142     Known = Known.sext(BitWidth);
1143     break;
1144   }
1145   case ISD::ANY_EXTEND: {
1146     SDValue Src = Op.getOperand(0);
1147     unsigned InBits = Src.getScalarValueSizeInBits();
1148     APInt InDemandedBits = DemandedBits.trunc(InBits);
1149     if (SimplifyDemandedBits(Src, InDemandedBits, Known, TLO, Depth+1))
1150       return true;
1151     assert(!Known.hasConflict() && "Bits known to be one AND zero?");
1152     Known = Known.zext(BitWidth);
1153     break;
1154   }
1155   case ISD::TRUNCATE: {
1156     SDValue Src = Op.getOperand(0);
1157
1158     // Simplify the input, using demanded bit information, and compute the known
1159     // zero/one bits live out.
1160     unsigned OperandBitWidth = Src.getScalarValueSizeInBits();
1161     APInt TruncMask = DemandedBits.zext(OperandBitWidth);
1162     if (SimplifyDemandedBits(Src, TruncMask, Known, TLO, Depth + 1))
1163       return true;
1164     Known = Known.trunc(BitWidth);
1165
1166     // If the input is only used by this truncate, see if we can shrink it based
1167     // on the known demanded bits.
1168     if (Src.getNode()->hasOneUse()) {
1169       switch (Src.getOpcode()) {
1170       default:
1171         break;
1172       case ISD::SRL:
1173         // Shrink SRL by a constant if none of the high bits shifted in are
1174         // demanded.
1175         if (TLO.LegalTypes() && !isTypeDesirableForOp(ISD::SRL, VT))
1176           // Do not turn (vt1 truncate (vt2 srl)) into (vt1 srl) if vt1 is
1177           // undesirable.
1178           break;
1179         ConstantSDNode *ShAmt = dyn_cast<ConstantSDNode>(Src.getOperand(1));
1180         if (!ShAmt)
1181           break;
1182         SDValue Shift = Src.getOperand(1);
1183         if (TLO.LegalTypes()) {
1184           uint64_t ShVal = ShAmt->getZExtValue();
1185           Shift = TLO.DAG.getConstant(ShVal, dl, getShiftAmountTy(VT, DL));
1186         }
1187
1188         if (ShAmt->getZExtValue() < BitWidth) {
1189           APInt HighBits = APInt::getHighBitsSet(OperandBitWidth,
1190                                                  OperandBitWidth - BitWidth);
1191           HighBits.lshrInPlace(ShAmt->getZExtValue());
1192           HighBits = HighBits.trunc(BitWidth);
1193
1194           if (!(HighBits & DemandedBits)) {
1195             // None of the shifted in bits are needed.  Add a truncate of the
1196             // shift input, then shift it.
1197             SDValue NewTrunc =
1198                 TLO.DAG.getNode(ISD::TRUNCATE, dl, VT, Src.getOperand(0));
1199             return TLO.CombineTo(
1200                 Op, TLO.DAG.getNode(ISD::SRL, dl, VT, NewTrunc, Shift));
1201           }
1202         }
1203         break;
1204       }
1205     }
1206
1207     assert(!Known.hasConflict() && "Bits known to be one AND zero?");
1208     break;
1209   }
1210   case ISD::AssertZext: {
1211     // AssertZext demands all of the high bits, plus any of the low bits
1212     // demanded by its users.
1213     EVT ZVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1214     APInt InMask = APInt::getLowBitsSet(BitWidth, ZVT.getSizeInBits());
1215     if (SimplifyDemandedBits(Op.getOperand(0), ~InMask | DemandedBits,
1216                              Known, TLO, Depth+1))
1217       return true;
1218     assert(!Known.hasConflict() && "Bits known to be one AND zero?");
1219
1220     Known.Zero |= ~InMask;
1221     break;
1222   }
1223   case ISD::EXTRACT_VECTOR_ELT: {
1224     // Demand the bits from every vector element.
1225     SDValue Src = Op.getOperand(0);
1226     unsigned EltBitWidth = Src.getScalarValueSizeInBits();
1227
1228     // If BitWidth > EltBitWidth the value is anyext:ed. So we do not know
1229     // anything about the extended bits.
1230     APInt DemandedSrcBits = DemandedBits;
1231     if (BitWidth > EltBitWidth)
1232       DemandedSrcBits = DemandedSrcBits.trunc(EltBitWidth);
1233
1234     if (SimplifyDemandedBits(Src, DemandedSrcBits, Known2, TLO, Depth + 1))
1235         return true;
1236
1237     Known = Known2;
1238     if (BitWidth > EltBitWidth)
1239       Known = Known.zext(BitWidth);
1240     break;
1241   }
1242   case ISD::BITCAST: {
1243     SDValue Src = Op.getOperand(0);
1244     EVT SrcVT = Src.getValueType();
1245     unsigned NumSrcEltBits = SrcVT.getScalarSizeInBits();
1246
1247     // If this is an FP->Int bitcast and if the sign bit is the only
1248     // thing demanded, turn this into a FGETSIGN.
1249     if (!TLO.LegalOperations() && !VT.isVector() && !SrcVT.isVector() &&
1250         DemandedBits == APInt::getSignMask(Op.getValueSizeInBits()) &&
1251         SrcVT.isFloatingPoint()) {
1252       bool OpVTLegal = isOperationLegalOrCustom(ISD::FGETSIGN, VT);
1253       bool i32Legal = isOperationLegalOrCustom(ISD::FGETSIGN, MVT::i32);
1254       if ((OpVTLegal || i32Legal) && VT.isSimple() && SrcVT != MVT::f16 &&
1255           SrcVT != MVT::f128) {
1256         // Cannot eliminate/lower SHL for f128 yet.
1257         EVT Ty = OpVTLegal ? VT : MVT::i32;
1258         // Make a FGETSIGN + SHL to move the sign bit into the appropriate
1259         // place.  We expect the SHL to be eliminated by other optimizations.
1260         SDValue Sign = TLO.DAG.getNode(ISD::FGETSIGN, dl, Ty, Src);
1261         unsigned OpVTSizeInBits = Op.getValueSizeInBits();
1262         if (!OpVTLegal && OpVTSizeInBits > 32)
1263           Sign = TLO.DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Sign);
1264         unsigned ShVal = Op.getValueSizeInBits() - 1;
1265         SDValue ShAmt = TLO.DAG.getConstant(ShVal, dl, VT);
1266         return TLO.CombineTo(Op,
1267                              TLO.DAG.getNode(ISD::SHL, dl, VT, Sign, ShAmt));
1268       }
1269     }
1270     // If bitcast from a vector, see if we can use SimplifyDemandedVectorElts by
1271     // demanding the element if any bits from it are demanded.
1272     // TODO - bigendian once we have test coverage.
1273     // TODO - bool vectors once SimplifyDemandedVectorElts has SETCC support.
1274     if (SrcVT.isVector() && NumSrcEltBits > 1 &&
1275         (BitWidth % NumSrcEltBits) == 0 &&
1276         TLO.DAG.getDataLayout().isLittleEndian()) {
1277       unsigned Scale = BitWidth / NumSrcEltBits;
1278       auto GetDemandedSubMask = [&](APInt &DemandedSubElts) -> bool {
1279         DemandedSubElts = APInt::getNullValue(Scale);
1280         for (unsigned i = 0; i != Scale; ++i) {
1281           unsigned Offset = i * NumSrcEltBits;
1282           APInt Sub = DemandedBits.extractBits(NumSrcEltBits, Offset);
1283           if (!Sub.isNullValue())
1284             DemandedSubElts.setBit(i);
1285         }
1286         return true;
1287       };
1288
1289       APInt DemandedSubElts;
1290       if (GetDemandedSubMask(DemandedSubElts)) {
1291         unsigned NumSrcElts = SrcVT.getVectorNumElements();
1292         APInt DemandedElts = APInt::getSplat(NumSrcElts, DemandedSubElts);
1293
1294         APInt KnownUndef, KnownZero;
1295         if (SimplifyDemandedVectorElts(Src, DemandedElts, KnownUndef, KnownZero,
1296                                        TLO, Depth + 1))
1297           return true;
1298       }
1299     }
1300     // If this is a bitcast, let computeKnownBits handle it.  Only do this on a
1301     // recursive call where Known may be useful to the caller.
1302     if (Depth > 0) {
1303       TLO.DAG.computeKnownBits(Op, Known, Depth);
1304       return false;
1305     }
1306     break;
1307   }
1308   case ISD::ADD:
1309   case ISD::MUL:
1310   case ISD::SUB: {
1311     // Add, Sub, and Mul don't demand any bits in positions beyond that
1312     // of the highest bit demanded of them.
1313     SDValue Op0 = Op.getOperand(0), Op1 = Op.getOperand(1);
1314     unsigned DemandedBitsLZ = DemandedBits.countLeadingZeros();
1315     APInt LoMask = APInt::getLowBitsSet(BitWidth, BitWidth - DemandedBitsLZ);
1316     if (SimplifyDemandedBits(Op0, LoMask, Known2, TLO, Depth + 1) ||
1317         SimplifyDemandedBits(Op1, LoMask, Known2, TLO, Depth + 1) ||
1318         // See if the operation should be performed at a smaller bit width.
1319         ShrinkDemandedOp(Op, BitWidth, DemandedBits, TLO)) {
1320       SDNodeFlags Flags = Op.getNode()->getFlags();
1321       if (Flags.hasNoSignedWrap() || Flags.hasNoUnsignedWrap()) {
1322         // Disable the nsw and nuw flags. We can no longer guarantee that we
1323         // won't wrap after simplification.
1324         Flags.setNoSignedWrap(false);
1325         Flags.setNoUnsignedWrap(false);
1326         SDValue NewOp = TLO.DAG.getNode(Op.getOpcode(), dl, VT, Op0, Op1,
1327                                         Flags);
1328         return TLO.CombineTo(Op, NewOp);
1329       }
1330       return true;
1331     }
1332
1333     // If we have a constant operand, we may be able to turn it into -1 if we
1334     // do not demand the high bits. This can make the constant smaller to
1335     // encode, allow more general folding, or match specialized instruction
1336     // patterns (eg, 'blsr' on x86). Don't bother changing 1 to -1 because that
1337     // is probably not useful (and could be detrimental).
1338     ConstantSDNode *C = isConstOrConstSplat(Op1);
1339     APInt HighMask = APInt::getHighBitsSet(BitWidth, DemandedBitsLZ);
1340     if (C && !C->isAllOnesValue() && !C->isOne() &&
1341         (C->getAPIntValue() | HighMask).isAllOnesValue()) {
1342       SDValue Neg1 = TLO.DAG.getAllOnesConstant(dl, VT);
1343       // We can't guarantee that the new math op doesn't wrap, so explicitly
1344       // clear those flags to prevent folding with a potential existing node
1345       // that has those flags set.
1346       SDNodeFlags Flags;
1347       Flags.setNoSignedWrap(false);
1348       Flags.setNoUnsignedWrap(false);
1349       SDValue NewOp = TLO.DAG.getNode(Op.getOpcode(), dl, VT, Op0, Neg1, Flags);
1350       return TLO.CombineTo(Op, NewOp);
1351     }
1352
1353     LLVM_FALLTHROUGH;
1354   }
1355   default:
1356     if (Op.getOpcode() >= ISD::BUILTIN_OP_END) {
1357       if (SimplifyDemandedBitsForTargetNode(Op, DemandedBits, Known, TLO,
1358                                             Depth))
1359         return true;
1360       break;
1361     }
1362
1363     // Just use computeKnownBits to compute output bits.
1364     TLO.DAG.computeKnownBits(Op, Known, Depth);
1365     break;
1366   }
1367
1368   // If we know the value of all of the demanded bits, return this as a
1369   // constant.
1370   if (DemandedBits.isSubsetOf(Known.Zero | Known.One)) {
1371     // Avoid folding to a constant if any OpaqueConstant is involved.
1372     const SDNode *N = Op.getNode();
1373     for (SDNodeIterator I = SDNodeIterator::begin(N),
1374                         E = SDNodeIterator::end(N);
1375          I != E; ++I) {
1376       SDNode *Op = *I;
1377       if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op))
1378         if (C->isOpaque())
1379           return false;
1380     }
1381     // TODO: Handle float bits as well.
1382     if (VT.isInteger())
1383       return TLO.CombineTo(Op, TLO.DAG.getConstant(Known.One, dl, VT));
1384   }
1385
1386   return false;
1387 }
1388
1389 bool TargetLowering::SimplifyDemandedVectorElts(SDValue Op,
1390                                                 const APInt &DemandedElts,
1391                                                 APInt &KnownUndef,
1392                                                 APInt &KnownZero,
1393                                                 DAGCombinerInfo &DCI) const {
1394   SelectionDAG &DAG = DCI.DAG;
1395   TargetLoweringOpt TLO(DAG, !DCI.isBeforeLegalize(),
1396                         !DCI.isBeforeLegalizeOps());
1397
1398   bool Simplified =
1399       SimplifyDemandedVectorElts(Op, DemandedElts, KnownUndef, KnownZero, TLO);
1400   if (Simplified) {
1401     DCI.AddToWorklist(Op.getNode());
1402     DCI.CommitTargetLoweringOpt(TLO);
1403   }
1404   return Simplified;
1405 }
1406
1407 bool TargetLowering::SimplifyDemandedVectorElts(
1408     SDValue Op, const APInt &DemandedEltMask, APInt &KnownUndef,
1409     APInt &KnownZero, TargetLoweringOpt &TLO, unsigned Depth,
1410     bool AssumeSingleUse) const {
1411   EVT VT = Op.getValueType();
1412   APInt DemandedElts = DemandedEltMask;
1413   unsigned NumElts = DemandedElts.getBitWidth();
1414   assert(VT.isVector() && "Expected vector op");
1415   assert(VT.getVectorNumElements() == NumElts &&
1416          "Mask size mismatches value type element count!");
1417
1418   KnownUndef = KnownZero = APInt::getNullValue(NumElts);
1419
1420   // Undef operand.
1421   if (Op.isUndef()) {
1422     KnownUndef.setAllBits();
1423     return false;
1424   }
1425
1426   // If Op has other users, assume that all elements are needed.
1427   if (!Op.getNode()->hasOneUse() && !AssumeSingleUse)
1428     DemandedElts.setAllBits();
1429
1430   // Not demanding any elements from Op.
1431   if (DemandedElts == 0) {
1432     KnownUndef.setAllBits();
1433     return TLO.CombineTo(Op, TLO.DAG.getUNDEF(VT));
1434   }
1435
1436   // Limit search depth.
1437   if (Depth >= 6)
1438     return false;
1439
1440   SDLoc DL(Op);
1441   unsigned EltSizeInBits = VT.getScalarSizeInBits();
1442
1443   switch (Op.getOpcode()) {
1444   case ISD::SCALAR_TO_VECTOR: {
1445     if (!DemandedElts[0]) {
1446       KnownUndef.setAllBits();
1447       return TLO.CombineTo(Op, TLO.DAG.getUNDEF(VT));
1448     }
1449     KnownUndef.setHighBits(NumElts - 1);
1450     break;
1451   }
1452   case ISD::BITCAST: {
1453     SDValue Src = Op.getOperand(0);
1454     EVT SrcVT = Src.getValueType();
1455
1456     // We only handle vectors here.
1457     // TODO - investigate calling SimplifyDemandedBits/ComputeKnownBits?
1458     if (!SrcVT.isVector())
1459       break;
1460
1461     // Fast handling of 'identity' bitcasts.
1462     unsigned NumSrcElts = SrcVT.getVectorNumElements();
1463     if (NumSrcElts == NumElts)
1464       return SimplifyDemandedVectorElts(Src, DemandedElts, KnownUndef,
1465                                         KnownZero, TLO, Depth + 1);
1466
1467     APInt SrcZero, SrcUndef;
1468     APInt SrcDemandedElts = APInt::getNullValue(NumSrcElts);
1469
1470     // Bitcast from 'large element' src vector to 'small element' vector, we
1471     // must demand a source element if any DemandedElt maps to it.
1472     if ((NumElts % NumSrcElts) == 0) {
1473       unsigned Scale = NumElts / NumSrcElts;
1474       for (unsigned i = 0; i != NumElts; ++i)
1475         if (DemandedElts[i])
1476           SrcDemandedElts.setBit(i / Scale);
1477
1478       if (SimplifyDemandedVectorElts(Src, SrcDemandedElts, SrcUndef, SrcZero,
1479                                      TLO, Depth + 1))
1480         return true;
1481
1482       // Try calling SimplifyDemandedBits, converting demanded elts to the bits
1483       // of the large element.
1484       // TODO - bigendian once we have test coverage.
1485       if (TLO.DAG.getDataLayout().isLittleEndian()) {
1486         unsigned SrcEltSizeInBits = SrcVT.getScalarSizeInBits();
1487         APInt SrcDemandedBits = APInt::getNullValue(SrcEltSizeInBits);
1488         for (unsigned i = 0; i != NumElts; ++i)
1489           if (DemandedElts[i]) {
1490             unsigned Ofs = (i % Scale) * EltSizeInBits;
1491             SrcDemandedBits.setBits(Ofs, Ofs + EltSizeInBits);
1492           }
1493
1494         KnownBits Known;
1495         if (SimplifyDemandedBits(Src, SrcDemandedBits, Known, TLO, Depth + 1))
1496           return true;
1497       }
1498
1499       // If the src element is zero/undef then all the output elements will be -
1500       // only demanded elements are guaranteed to be correct.
1501       for (unsigned i = 0; i != NumSrcElts; ++i) {
1502         if (SrcDemandedElts[i]) {
1503           if (SrcZero[i])
1504             KnownZero.setBits(i * Scale, (i + 1) * Scale);
1505           if (SrcUndef[i])
1506             KnownUndef.setBits(i * Scale, (i + 1) * Scale);
1507         }
1508       }
1509     }
1510
1511     // Bitcast from 'small element' src vector to 'large element' vector, we
1512     // demand all smaller source elements covered by the larger demanded element
1513     // of this vector.
1514     if ((NumSrcElts % NumElts) == 0) {
1515       unsigned Scale = NumSrcElts / NumElts;
1516       for (unsigned i = 0; i != NumElts; ++i)
1517         if (DemandedElts[i])
1518           SrcDemandedElts.setBits(i * Scale, (i + 1) * Scale);
1519
1520       if (SimplifyDemandedVectorElts(Src, SrcDemandedElts, SrcUndef, SrcZero,
1521                                      TLO, Depth + 1))
1522         return true;
1523
1524       // If all the src elements covering an output element are zero/undef, then
1525       // the output element will be as well, assuming it was demanded.
1526       for (unsigned i = 0; i != NumElts; ++i) {
1527         if (DemandedElts[i]) {
1528           if (SrcZero.extractBits(Scale, i * Scale).isAllOnesValue())
1529             KnownZero.setBit(i);
1530           if (SrcUndef.extractBits(Scale, i * Scale).isAllOnesValue())
1531             KnownUndef.setBit(i);
1532         }
1533       }
1534     }
1535     break;
1536   }
1537   case ISD::BUILD_VECTOR: {
1538     // Check all elements and simplify any unused elements with UNDEF.
1539     if (!DemandedElts.isAllOnesValue()) {
1540       // Don't simplify BROADCASTS.
1541       if (llvm::any_of(Op->op_values(),
1542                        [&](SDValue Elt) { return Op.getOperand(0) != Elt; })) {
1543         SmallVector<SDValue, 32> Ops(Op->op_begin(), Op->op_end());
1544         bool Updated = false;
1545         for (unsigned i = 0; i != NumElts; ++i) {
1546           if (!DemandedElts[i] && !Ops[i].isUndef()) {
1547             Ops[i] = TLO.DAG.getUNDEF(Ops[0].getValueType());
1548             KnownUndef.setBit(i);
1549             Updated = true;
1550           }
1551         }
1552         if (Updated)
1553           return TLO.CombineTo(Op, TLO.DAG.getBuildVector(VT, DL, Ops));
1554       }
1555     }
1556     for (unsigned i = 0; i != NumElts; ++i) {
1557       SDValue SrcOp = Op.getOperand(i);
1558       if (SrcOp.isUndef()) {
1559         KnownUndef.setBit(i);
1560       } else if (EltSizeInBits == SrcOp.getScalarValueSizeInBits() &&
1561                  (isNullConstant(SrcOp) || isNullFPConstant(SrcOp))) {
1562         KnownZero.setBit(i);
1563       }
1564     }
1565     break;
1566   }
1567   case ISD::CONCAT_VECTORS: {
1568     EVT SubVT = Op.getOperand(0).getValueType();
1569     unsigned NumSubVecs = Op.getNumOperands();
1570     unsigned NumSubElts = SubVT.getVectorNumElements();
1571     for (unsigned i = 0; i != NumSubVecs; ++i) {
1572       SDValue SubOp = Op.getOperand(i);
1573       APInt SubElts = DemandedElts.extractBits(NumSubElts, i * NumSubElts);
1574       APInt SubUndef, SubZero;
1575       if (SimplifyDemandedVectorElts(SubOp, SubElts, SubUndef, SubZero, TLO,
1576                                      Depth + 1))
1577         return true;
1578       KnownUndef.insertBits(SubUndef, i * NumSubElts);
1579       KnownZero.insertBits(SubZero, i * NumSubElts);
1580     }
1581     break;
1582   }
1583   case ISD::INSERT_SUBVECTOR: {
1584     if (!isa<ConstantSDNode>(Op.getOperand(2)))
1585       break;
1586     SDValue Base = Op.getOperand(0);
1587     SDValue Sub = Op.getOperand(1);
1588     EVT SubVT = Sub.getValueType();
1589     unsigned NumSubElts = SubVT.getVectorNumElements();
1590     const APInt& Idx = cast<ConstantSDNode>(Op.getOperand(2))->getAPIntValue();
1591     if (Idx.ugt(NumElts - NumSubElts))
1592       break;
1593     unsigned SubIdx = Idx.getZExtValue();
1594     APInt SubElts = DemandedElts.extractBits(NumSubElts, SubIdx);
1595     APInt SubUndef, SubZero;
1596     if (SimplifyDemandedVectorElts(Sub, SubElts, SubUndef, SubZero, TLO,
1597                                    Depth + 1))
1598       return true;
1599     APInt BaseElts = DemandedElts;
1600     BaseElts.insertBits(APInt::getNullValue(NumSubElts), SubIdx);
1601     if (SimplifyDemandedVectorElts(Base, BaseElts, KnownUndef, KnownZero, TLO,
1602                                    Depth + 1))
1603       return true;
1604     KnownUndef.insertBits(SubUndef, SubIdx);
1605     KnownZero.insertBits(SubZero, SubIdx);
1606     break;
1607   }
1608   case ISD::EXTRACT_SUBVECTOR: {
1609     SDValue Src = Op.getOperand(0);
1610     ConstantSDNode *SubIdx = dyn_cast<ConstantSDNode>(Op.getOperand(1));
1611     unsigned NumSrcElts = Src.getValueType().getVectorNumElements();
1612     if (SubIdx && SubIdx->getAPIntValue().ule(NumSrcElts - NumElts)) {
1613       // Offset the demanded elts by the subvector index.
1614       uint64_t Idx = SubIdx->getZExtValue();
1615       APInt SrcElts = DemandedElts.zextOrSelf(NumSrcElts).shl(Idx);
1616       APInt SrcUndef, SrcZero;
1617       if (SimplifyDemandedVectorElts(Src, SrcElts, SrcUndef, SrcZero, TLO,
1618                                      Depth + 1))
1619         return true;
1620       KnownUndef = SrcUndef.extractBits(NumElts, Idx);
1621       KnownZero = SrcZero.extractBits(NumElts, Idx);
1622     }
1623     break;
1624   }
1625   case ISD::INSERT_VECTOR_ELT: {
1626     SDValue Vec = Op.getOperand(0);
1627     SDValue Scl = Op.getOperand(1);
1628     auto *CIdx = dyn_cast<ConstantSDNode>(Op.getOperand(2));
1629
1630     // For a legal, constant insertion index, if we don't need this insertion
1631     // then strip it, else remove it from the demanded elts.
1632     if (CIdx && CIdx->getAPIntValue().ult(NumElts)) {
1633       unsigned Idx = CIdx->getZExtValue();
1634       if (!DemandedElts[Idx])
1635         return TLO.CombineTo(Op, Vec);
1636
1637       APInt DemandedVecElts(DemandedElts);
1638       DemandedVecElts.clearBit(Idx);
1639       if (SimplifyDemandedVectorElts(Vec, DemandedVecElts, KnownUndef,
1640                                      KnownZero, TLO, Depth + 1))
1641         return true;
1642
1643       KnownUndef.clearBit(Idx);
1644       if (Scl.isUndef())
1645         KnownUndef.setBit(Idx);
1646
1647       KnownZero.clearBit(Idx);
1648       if (isNullConstant(Scl) || isNullFPConstant(Scl))
1649         KnownZero.setBit(Idx);
1650       break;
1651     }
1652
1653     APInt VecUndef, VecZero;
1654     if (SimplifyDemandedVectorElts(Vec, DemandedElts, VecUndef, VecZero, TLO,
1655                                    Depth + 1))
1656       return true;
1657     // Without knowing the insertion index we can't set KnownUndef/KnownZero.
1658     break;
1659   }
1660   case ISD::VSELECT: {
1661     // Try to transform the select condition based on the current demanded
1662     // elements.
1663     // TODO: If a condition element is undef, we can choose from one arm of the
1664     //       select (and if one arm is undef, then we can propagate that to the
1665     //       result).
1666     // TODO - add support for constant vselect masks (see IR version of this).
1667     APInt UnusedUndef, UnusedZero;
1668     if (SimplifyDemandedVectorElts(Op.getOperand(0), DemandedElts, UnusedUndef,
1669                                    UnusedZero, TLO, Depth + 1))
1670       return true;
1671
1672     // See if we can simplify either vselect operand.
1673     APInt DemandedLHS(DemandedElts);
1674     APInt DemandedRHS(DemandedElts);
1675     APInt UndefLHS, ZeroLHS;
1676     APInt UndefRHS, ZeroRHS;
1677     if (SimplifyDemandedVectorElts(Op.getOperand(1), DemandedLHS, UndefLHS,
1678                                    ZeroLHS, TLO, Depth + 1))
1679       return true;
1680     if (SimplifyDemandedVectorElts(Op.getOperand(2), DemandedRHS, UndefRHS,
1681                                    ZeroRHS, TLO, Depth + 1))
1682       return true;
1683
1684     KnownUndef = UndefLHS & UndefRHS;
1685     KnownZero = ZeroLHS & ZeroRHS;
1686     break;
1687   }
1688   case ISD::VECTOR_SHUFFLE: {
1689     ArrayRef<int> ShuffleMask = cast<ShuffleVectorSDNode>(Op)->getMask();
1690
1691     // Collect demanded elements from shuffle operands..
1692     APInt DemandedLHS(NumElts, 0);
1693     APInt DemandedRHS(NumElts, 0);
1694     for (unsigned i = 0; i != NumElts; ++i) {
1695       int M = ShuffleMask[i];
1696       if (M < 0 || !DemandedElts[i])
1697         continue;
1698       assert(0 <= M && M < (int)(2 * NumElts) && "Shuffle index out of range");
1699       if (M < (int)NumElts)
1700         DemandedLHS.setBit(M);
1701       else
1702         DemandedRHS.setBit(M - NumElts);
1703     }
1704
1705     // See if we can simplify either shuffle operand.
1706     APInt UndefLHS, ZeroLHS;
1707     APInt UndefRHS, ZeroRHS;
1708     if (SimplifyDemandedVectorElts(Op.getOperand(0), DemandedLHS, UndefLHS,
1709                                    ZeroLHS, TLO, Depth + 1))
1710       return true;
1711     if (SimplifyDemandedVectorElts(Op.getOperand(1), DemandedRHS, UndefRHS,
1712                                    ZeroRHS, TLO, Depth + 1))
1713       return true;
1714
1715     // Simplify mask using undef elements from LHS/RHS.
1716     bool Updated = false;
1717     bool IdentityLHS = true, IdentityRHS = true;
1718     SmallVector<int, 32> NewMask(ShuffleMask.begin(), ShuffleMask.end());
1719     for (unsigned i = 0; i != NumElts; ++i) {
1720       int &M = NewMask[i];
1721       if (M < 0)
1722         continue;
1723       if (!DemandedElts[i] || (M < (int)NumElts && UndefLHS[M]) ||
1724           (M >= (int)NumElts && UndefRHS[M - NumElts])) {
1725         Updated = true;
1726         M = -1;
1727       }
1728       IdentityLHS &= (M < 0) || (M == (int)i);
1729       IdentityRHS &= (M < 0) || ((M - NumElts) == i);
1730     }
1731
1732     // Update legal shuffle masks based on demanded elements if it won't reduce
1733     // to Identity which can cause premature removal of the shuffle mask.
1734     if (Updated && !IdentityLHS && !IdentityRHS && !TLO.LegalOps &&
1735         isShuffleMaskLegal(NewMask, VT))
1736       return TLO.CombineTo(Op,
1737                            TLO.DAG.getVectorShuffle(VT, DL, Op.getOperand(0),
1738                                                     Op.getOperand(1), NewMask));
1739
1740     // Propagate undef/zero elements from LHS/RHS.
1741     for (unsigned i = 0; i != NumElts; ++i) {
1742       int M = ShuffleMask[i];
1743       if (M < 0) {
1744         KnownUndef.setBit(i);
1745       } else if (M < (int)NumElts) {
1746         if (UndefLHS[M])
1747           KnownUndef.setBit(i);
1748         if (ZeroLHS[M])
1749           KnownZero.setBit(i);
1750       } else {
1751         if (UndefRHS[M - NumElts])
1752           KnownUndef.setBit(i);
1753         if (ZeroRHS[M - NumElts])
1754           KnownZero.setBit(i);
1755       }
1756     }
1757     break;
1758   }
1759   case ISD::SIGN_EXTEND_VECTOR_INREG:
1760   case ISD::ZERO_EXTEND_VECTOR_INREG: {
1761     APInt SrcUndef, SrcZero;
1762     SDValue Src = Op.getOperand(0);
1763     unsigned NumSrcElts = Src.getValueType().getVectorNumElements();
1764     APInt DemandedSrcElts = DemandedElts.zextOrSelf(NumSrcElts);
1765     if (SimplifyDemandedVectorElts(Src, DemandedSrcElts, SrcUndef,
1766                                    SrcZero, TLO, Depth + 1))
1767       return true;
1768     KnownZero = SrcZero.zextOrTrunc(NumElts);
1769     KnownUndef = SrcUndef.zextOrTrunc(NumElts);
1770     break;
1771   }
1772   case ISD::ADD:
1773   case ISD::SUB:
1774   case ISD::FADD:
1775   case ISD::FSUB:
1776   case ISD::FMUL:
1777   case ISD::FDIV:
1778   case ISD::FREM: {
1779     APInt SrcUndef, SrcZero;
1780     if (SimplifyDemandedVectorElts(Op.getOperand(1), DemandedElts, SrcUndef,
1781                                    SrcZero, TLO, Depth + 1))
1782       return true;
1783     if (SimplifyDemandedVectorElts(Op.getOperand(0), DemandedElts, KnownUndef,
1784                                    KnownZero, TLO, Depth + 1))
1785       return true;
1786     KnownZero &= SrcZero;
1787     KnownUndef &= SrcUndef;
1788     break;
1789   }
1790   case ISD::TRUNCATE:
1791   case ISD::SIGN_EXTEND:
1792   case ISD::ZERO_EXTEND:
1793     if (SimplifyDemandedVectorElts(Op.getOperand(0), DemandedElts, KnownUndef,
1794                                    KnownZero, TLO, Depth + 1))
1795       return true;
1796     break;
1797   default: {
1798     if (Op.getOpcode() >= ISD::BUILTIN_OP_END)
1799       if (SimplifyDemandedVectorEltsForTargetNode(Op, DemandedElts, KnownUndef,
1800                                                   KnownZero, TLO, Depth))
1801         return true;
1802     break;
1803   }
1804   }
1805   assert((KnownUndef & KnownZero) == 0 && "Elements flagged as undef AND zero");
1806
1807   // Constant fold all undef cases.
1808   // TODO: Handle zero cases as well.
1809   if (DemandedElts.isSubsetOf(KnownUndef))
1810     return TLO.CombineTo(Op, TLO.DAG.getUNDEF(VT));
1811
1812   return false;
1813 }
1814
1815 /// Determine which of the bits specified in Mask are known to be either zero or
1816 /// one and return them in the Known.
1817 void TargetLowering::computeKnownBitsForTargetNode(const SDValue Op,
1818                                                    KnownBits &Known,
1819                                                    const APInt &DemandedElts,
1820                                                    const SelectionDAG &DAG,
1821                                                    unsigned Depth) const {
1822   assert((Op.getOpcode() >= ISD::BUILTIN_OP_END ||
1823           Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
1824           Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
1825           Op.getOpcode() == ISD::INTRINSIC_VOID) &&
1826          "Should use MaskedValueIsZero if you don't know whether Op"
1827          " is a target node!");
1828   Known.resetAll();
1829 }
1830
1831 void TargetLowering::computeKnownBitsForFrameIndex(const SDValue Op,
1832                                                    KnownBits &Known,
1833                                                    const APInt &DemandedElts,
1834                                                    const SelectionDAG &DAG,
1835                                                    unsigned Depth) const {
1836   assert(isa<FrameIndexSDNode>(Op) && "expected FrameIndex");
1837
1838   if (unsigned Align = DAG.InferPtrAlignment(Op)) {
1839     // The low bits are known zero if the pointer is aligned.
1840     Known.Zero.setLowBits(Log2_32(Align));
1841   }
1842 }
1843
1844 /// This method can be implemented by targets that want to expose additional
1845 /// information about sign bits to the DAG Combiner.
1846 unsigned TargetLowering::ComputeNumSignBitsForTargetNode(SDValue Op,
1847                                                          const APInt &,
1848                                                          const SelectionDAG &,
1849                                                          unsigned Depth) const {
1850   assert((Op.getOpcode() >= ISD::BUILTIN_OP_END ||
1851           Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
1852           Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
1853           Op.getOpcode() == ISD::INTRINSIC_VOID) &&
1854          "Should use ComputeNumSignBits if you don't know whether Op"
1855          " is a target node!");
1856   return 1;
1857 }
1858
1859 bool TargetLowering::SimplifyDemandedVectorEltsForTargetNode(
1860     SDValue Op, const APInt &DemandedElts, APInt &KnownUndef, APInt &KnownZero,
1861     TargetLoweringOpt &TLO, unsigned Depth) const {
1862   assert((Op.getOpcode() >= ISD::BUILTIN_OP_END ||
1863           Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
1864           Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
1865           Op.getOpcode() == ISD::INTRINSIC_VOID) &&
1866          "Should use SimplifyDemandedVectorElts if you don't know whether Op"
1867          " is a target node!");
1868   return false;
1869 }
1870
1871 bool TargetLowering::SimplifyDemandedBitsForTargetNode(
1872     SDValue Op, const APInt &DemandedBits, KnownBits &Known,
1873     TargetLoweringOpt &TLO, unsigned Depth) const {
1874   assert((Op.getOpcode() >= ISD::BUILTIN_OP_END ||
1875           Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
1876           Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
1877           Op.getOpcode() == ISD::INTRINSIC_VOID) &&
1878          "Should use SimplifyDemandedBits if you don't know whether Op"
1879          " is a target node!");
1880   EVT VT = Op.getValueType();
1881   APInt DemandedElts = VT.isVector()
1882                            ? APInt::getAllOnesValue(VT.getVectorNumElements())
1883                            : APInt(1, 1);
1884   computeKnownBitsForTargetNode(Op, Known, DemandedElts, TLO.DAG, Depth);
1885   return false;
1886 }
1887
1888 bool TargetLowering::isKnownNeverNaNForTargetNode(SDValue Op,
1889                                                   const SelectionDAG &DAG,
1890                                                   bool SNaN,
1891                                                   unsigned Depth) const {
1892   assert((Op.getOpcode() >= ISD::BUILTIN_OP_END ||
1893           Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
1894           Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
1895           Op.getOpcode() == ISD::INTRINSIC_VOID) &&
1896          "Should use isKnownNeverNaN if you don't know whether Op"
1897          " is a target node!");
1898   return false;
1899 }
1900
1901 // FIXME: Ideally, this would use ISD::isConstantSplatVector(), but that must
1902 // work with truncating build vectors and vectors with elements of less than
1903 // 8 bits.
1904 bool TargetLowering::isConstTrueVal(const SDNode *N) const {
1905   if (!N)
1906     return false;
1907
1908   APInt CVal;
1909   if (auto *CN = dyn_cast<ConstantSDNode>(N)) {
1910     CVal = CN->getAPIntValue();
1911   } else if (auto *BV = dyn_cast<BuildVectorSDNode>(N)) {
1912     auto *CN = BV->getConstantSplatNode();
1913     if (!CN)
1914       return false;
1915
1916     // If this is a truncating build vector, truncate the splat value.
1917     // Otherwise, we may fail to match the expected values below.
1918     unsigned BVEltWidth = BV->getValueType(0).getScalarSizeInBits();
1919     CVal = CN->getAPIntValue();
1920     if (BVEltWidth < CVal.getBitWidth())
1921       CVal = CVal.trunc(BVEltWidth);
1922   } else {
1923     return false;
1924   }
1925
1926   switch (getBooleanContents(N->getValueType(0))) {
1927   case UndefinedBooleanContent:
1928     return CVal[0];
1929   case ZeroOrOneBooleanContent:
1930     return CVal.isOneValue();
1931   case ZeroOrNegativeOneBooleanContent:
1932     return CVal.isAllOnesValue();
1933   }
1934
1935   llvm_unreachable("Invalid boolean contents");
1936 }
1937
1938 bool TargetLowering::isConstFalseVal(const SDNode *N) const {
1939   if (!N)
1940     return false;
1941
1942   const ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N);
1943   if (!CN) {
1944     const BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(N);
1945     if (!BV)
1946       return false;
1947
1948     // Only interested in constant splats, we don't care about undef
1949     // elements in identifying boolean constants and getConstantSplatNode
1950     // returns NULL if all ops are undef;
1951     CN = BV->getConstantSplatNode();
1952     if (!CN)
1953       return false;
1954   }
1955
1956   if (getBooleanContents(N->getValueType(0)) == UndefinedBooleanContent)
1957     return !CN->getAPIntValue()[0];
1958
1959   return CN->isNullValue();
1960 }
1961
1962 bool TargetLowering::isExtendedTrueVal(const ConstantSDNode *N, EVT VT,
1963                                        bool SExt) const {
1964   if (VT == MVT::i1)
1965     return N->isOne();
1966
1967   TargetLowering::BooleanContent Cnt = getBooleanContents(VT);
1968   switch (Cnt) {
1969   case TargetLowering::ZeroOrOneBooleanContent:
1970     // An extended value of 1 is always true, unless its original type is i1,
1971     // in which case it will be sign extended to -1.
1972     return (N->isOne() && !SExt) || (SExt && (N->getValueType(0) != MVT::i1));
1973   case TargetLowering::UndefinedBooleanContent:
1974   case TargetLowering::ZeroOrNegativeOneBooleanContent:
1975     return N->isAllOnesValue() && SExt;
1976   }
1977   llvm_unreachable("Unexpected enumeration.");
1978 }
1979
1980 /// This helper function of SimplifySetCC tries to optimize the comparison when
1981 /// either operand of the SetCC node is a bitwise-and instruction.
1982 SDValue TargetLowering::simplifySetCCWithAnd(EVT VT, SDValue N0, SDValue N1,
1983                                              ISD::CondCode Cond,
1984                                              DAGCombinerInfo &DCI,
1985                                              const SDLoc &DL) const {
1986   // Match these patterns in any of their permutations:
1987   // (X & Y) == Y
1988   // (X & Y) != Y
1989   if (N1.getOpcode() == ISD::AND && N0.getOpcode() != ISD::AND)
1990     std::swap(N0, N1);
1991
1992   EVT OpVT = N0.getValueType();
1993   if (N0.getOpcode() != ISD::AND || !OpVT.isInteger() ||
1994       (Cond != ISD::SETEQ && Cond != ISD::SETNE))
1995     return SDValue();
1996
1997   SDValue X, Y;
1998   if (N0.getOperand(0) == N1) {
1999     X = N0.getOperand(1);
2000     Y = N0.getOperand(0);
2001   } else if (N0.getOperand(1) == N1) {
2002     X = N0.getOperand(0);
2003     Y = N0.getOperand(1);
2004   } else {
2005     return SDValue();
2006   }
2007
2008   SelectionDAG &DAG = DCI.DAG;
2009   SDValue Zero = DAG.getConstant(0, DL, OpVT);
2010   if (DAG.isKnownToBeAPowerOfTwo(Y)) {
2011     // Simplify X & Y == Y to X & Y != 0 if Y has exactly one bit set.
2012     // Note that where Y is variable and is known to have at most one bit set
2013     // (for example, if it is Z & 1) we cannot do this; the expressions are not
2014     // equivalent when Y == 0.
2015     Cond = ISD::getSetCCInverse(Cond, /*isInteger=*/true);
2016     if (DCI.isBeforeLegalizeOps() ||
2017         isCondCodeLegal(Cond, N0.getSimpleValueType()))
2018       return DAG.getSetCC(DL, VT, N0, Zero, Cond);
2019   } else if (N0.hasOneUse() && hasAndNotCompare(Y)) {
2020     // If the target supports an 'and-not' or 'and-complement' logic operation,
2021     // try to use that to make a comparison operation more efficient.
2022     // But don't do this transform if the mask is a single bit because there are
2023     // more efficient ways to deal with that case (for example, 'bt' on x86 or
2024     // 'rlwinm' on PPC).
2025
2026     // Bail out if the compare operand that we want to turn into a zero is
2027     // already a zero (otherwise, infinite loop).
2028     auto *YConst = dyn_cast<ConstantSDNode>(Y);
2029     if (YConst && YConst->isNullValue())
2030       return SDValue();
2031
2032     // Transform this into: ~X & Y == 0.
2033     SDValue NotX = DAG.getNOT(SDLoc(X), X, OpVT);
2034     SDValue NewAnd = DAG.getNode(ISD::AND, SDLoc(N0), OpVT, NotX, Y);
2035     return DAG.getSetCC(DL, VT, NewAnd, Zero, Cond);
2036   }
2037
2038   return SDValue();
2039 }
2040
2041 /// There are multiple IR patterns that could be checking whether certain
2042 /// truncation of a signed number would be lossy or not. The pattern which is
2043 /// best at IR level, may not lower optimally. Thus, we want to unfold it.
2044 /// We are looking for the following pattern: (KeptBits is a constant)
2045 ///   (add %x, (1 << (KeptBits-1))) srccond (1 << KeptBits)
2046 /// KeptBits won't be bitwidth(x), that will be constant-folded to true/false.
2047 /// KeptBits also can't be 1, that would have been folded to  %x dstcond 0
2048 /// We will unfold it into the natural trunc+sext pattern:
2049 ///   ((%x << C) a>> C) dstcond %x
2050 /// Where  C = bitwidth(x) - KeptBits  and  C u< bitwidth(x)
2051 SDValue TargetLowering::optimizeSetCCOfSignedTruncationCheck(
2052     EVT SCCVT, SDValue N0, SDValue N1, ISD::CondCode Cond, DAGCombinerInfo &DCI,
2053     const SDLoc &DL) const {
2054   // We must be comparing with a constant.
2055   ConstantSDNode *C1;
2056   if (!(C1 = dyn_cast<ConstantSDNode>(N1)))
2057     return SDValue();
2058
2059   // N0 should be:  add %x, (1 << (KeptBits-1))
2060   if (N0->getOpcode() != ISD::ADD)
2061     return SDValue();
2062
2063   // And we must be 'add'ing a constant.
2064   ConstantSDNode *C01;
2065   if (!(C01 = dyn_cast<ConstantSDNode>(N0->getOperand(1))))
2066     return SDValue();
2067
2068   SDValue X = N0->getOperand(0);
2069   EVT XVT = X.getValueType();
2070
2071   // Validate constants ...
2072
2073   APInt I1 = C1->getAPIntValue();
2074
2075   ISD::CondCode NewCond;
2076   if (Cond == ISD::CondCode::SETULT) {
2077     NewCond = ISD::CondCode::SETEQ;
2078   } else if (Cond == ISD::CondCode::SETULE) {
2079     NewCond = ISD::CondCode::SETEQ;
2080     // But need to 'canonicalize' the constant.
2081     I1 += 1;
2082   } else if (Cond == ISD::CondCode::SETUGT) {
2083     NewCond = ISD::CondCode::SETNE;
2084     // But need to 'canonicalize' the constant.
2085     I1 += 1;
2086   } else if (Cond == ISD::CondCode::SETUGE) {
2087     NewCond = ISD::CondCode::SETNE;
2088   } else
2089     return SDValue();
2090
2091   APInt I01 = C01->getAPIntValue();
2092
2093   auto checkConstants = [&I1, &I01]() -> bool {
2094     // Both of them must be power-of-two, and the constant from setcc is bigger.
2095     return I1.ugt(I01) && I1.isPowerOf2() && I01.isPowerOf2();
2096   };
2097
2098   if (checkConstants()) {
2099     // Great, e.g. got  icmp ult i16 (add i16 %x, 128), 256
2100   } else {
2101     // What if we invert constants? (and the target predicate)
2102     I1.negate();
2103     I01.negate();
2104     NewCond = getSetCCInverse(NewCond, /*isInteger=*/true);
2105     if (!checkConstants())
2106       return SDValue();
2107     // Great, e.g. got  icmp uge i16 (add i16 %x, -128), -256
2108   }
2109
2110   // They are power-of-two, so which bit is set?
2111   const unsigned KeptBits = I1.logBase2();
2112   const unsigned KeptBitsMinusOne = I01.logBase2();
2113
2114   // Magic!
2115   if (KeptBits != (KeptBitsMinusOne + 1))
2116     return SDValue();
2117   assert(KeptBits > 0 && KeptBits < XVT.getSizeInBits() && "unreachable");
2118
2119   // We don't want to do this in every single case.
2120   SelectionDAG &DAG = DCI.DAG;
2121   if (!DAG.getTargetLoweringInfo().shouldTransformSignedTruncationCheck(
2122           XVT, KeptBits))
2123     return SDValue();
2124
2125   const unsigned MaskedBits = XVT.getSizeInBits() - KeptBits;
2126   assert(MaskedBits > 0 && MaskedBits < XVT.getSizeInBits() && "unreachable");
2127
2128   // Unfold into:  ((%x << C) a>> C) cond %x
2129   // Where 'cond' will be either 'eq' or 'ne'.
2130   SDValue ShiftAmt = DAG.getConstant(MaskedBits, DL, XVT);
2131   SDValue T0 = DAG.getNode(ISD::SHL, DL, XVT, X, ShiftAmt);
2132   SDValue T1 = DAG.getNode(ISD::SRA, DL, XVT, T0, ShiftAmt);
2133   SDValue T2 = DAG.getSetCC(DL, SCCVT, T1, X, NewCond);
2134
2135   return T2;
2136 }
2137
2138 /// Try to simplify a setcc built with the specified operands and cc. If it is
2139 /// unable to simplify it, return a null SDValue.
2140 SDValue TargetLowering::SimplifySetCC(EVT VT, SDValue N0, SDValue N1,
2141                                       ISD::CondCode Cond, bool foldBooleans,
2142                                       DAGCombinerInfo &DCI,
2143                                       const SDLoc &dl) const {
2144   SelectionDAG &DAG = DCI.DAG;
2145   EVT OpVT = N0.getValueType();
2146
2147   // These setcc operations always fold.
2148   switch (Cond) {
2149   default: break;
2150   case ISD::SETFALSE:
2151   case ISD::SETFALSE2: return DAG.getBoolConstant(false, dl, VT, OpVT);
2152   case ISD::SETTRUE:
2153   case ISD::SETTRUE2:  return DAG.getBoolConstant(true, dl, VT, OpVT);
2154   }
2155
2156   // Ensure that the constant occurs on the RHS and fold constant comparisons.
2157   // TODO: Handle non-splat vector constants. All undef causes trouble.
2158   ISD::CondCode SwappedCC = ISD::getSetCCSwappedOperands(Cond);
2159   if (isConstOrConstSplat(N0) &&
2160       (DCI.isBeforeLegalizeOps() ||
2161        isCondCodeLegal(SwappedCC, N0.getSimpleValueType())))
2162     return DAG.getSetCC(dl, VT, N1, N0, SwappedCC);
2163
2164   if (auto *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
2165     const APInt &C1 = N1C->getAPIntValue();
2166
2167     // If the LHS is '(srl (ctlz x), 5)', the RHS is 0/1, and this is an
2168     // equality comparison, then we're just comparing whether X itself is
2169     // zero.
2170     if (N0.getOpcode() == ISD::SRL && (C1.isNullValue() || C1.isOneValue()) &&
2171         N0.getOperand(0).getOpcode() == ISD::CTLZ &&
2172         N0.getOperand(1).getOpcode() == ISD::Constant) {
2173       const APInt &ShAmt
2174         = cast<ConstantSDNode>(N0.getOperand(1))->getAPIntValue();
2175       if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
2176           ShAmt == Log2_32(N0.getValueSizeInBits())) {
2177         if ((C1 == 0) == (Cond == ISD::SETEQ)) {
2178           // (srl (ctlz x), 5) == 0  -> X != 0
2179           // (srl (ctlz x), 5) != 1  -> X != 0
2180           Cond = ISD::SETNE;
2181         } else {
2182           // (srl (ctlz x), 5) != 0  -> X == 0
2183           // (srl (ctlz x), 5) == 1  -> X == 0
2184           Cond = ISD::SETEQ;
2185         }
2186         SDValue Zero = DAG.getConstant(0, dl, N0.getValueType());
2187         return DAG.getSetCC(dl, VT, N0.getOperand(0).getOperand(0),
2188                             Zero, Cond);
2189       }
2190     }
2191
2192     SDValue CTPOP = N0;
2193     // Look through truncs that don't change the value of a ctpop.
2194     if (N0.hasOneUse() && N0.getOpcode() == ISD::TRUNCATE)
2195       CTPOP = N0.getOperand(0);
2196
2197     if (CTPOP.hasOneUse() && CTPOP.getOpcode() == ISD::CTPOP &&
2198         (N0 == CTPOP ||
2199          N0.getValueSizeInBits() > Log2_32_Ceil(CTPOP.getValueSizeInBits()))) {
2200       EVT CTVT = CTPOP.getValueType();
2201       SDValue CTOp = CTPOP.getOperand(0);
2202
2203       // (ctpop x) u< 2 -> (x & x-1) == 0
2204       // (ctpop x) u> 1 -> (x & x-1) != 0
2205       if ((Cond == ISD::SETULT && C1 == 2) || (Cond == ISD::SETUGT && C1 == 1)){
2206         SDValue Sub = DAG.getNode(ISD::SUB, dl, CTVT, CTOp,
2207                                   DAG.getConstant(1, dl, CTVT));
2208         SDValue And = DAG.getNode(ISD::AND, dl, CTVT, CTOp, Sub);
2209         ISD::CondCode CC = Cond == ISD::SETULT ? ISD::SETEQ : ISD::SETNE;
2210         return DAG.getSetCC(dl, VT, And, DAG.getConstant(0, dl, CTVT), CC);
2211       }
2212
2213       // TODO: (ctpop x) == 1 -> x && (x & x-1) == 0 iff ctpop is illegal.
2214     }
2215
2216     // (zext x) == C --> x == (trunc C)
2217     // (sext x) == C --> x == (trunc C)
2218     if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
2219         DCI.isBeforeLegalize() && N0->hasOneUse()) {
2220       unsigned MinBits = N0.getValueSizeInBits();
2221       SDValue PreExt;
2222       bool Signed = false;
2223       if (N0->getOpcode() == ISD::ZERO_EXTEND) {
2224         // ZExt
2225         MinBits = N0->getOperand(0).getValueSizeInBits();
2226         PreExt = N0->getOperand(0);
2227       } else if (N0->getOpcode() == ISD::AND) {
2228         // DAGCombine turns costly ZExts into ANDs
2229         if (auto *C = dyn_cast<ConstantSDNode>(N0->getOperand(1)))
2230           if ((C->getAPIntValue()+1).isPowerOf2()) {
2231             MinBits = C->getAPIntValue().countTrailingOnes();
2232             PreExt = N0->getOperand(0);
2233           }
2234       } else if (N0->getOpcode() == ISD::SIGN_EXTEND) {
2235         // SExt
2236         MinBits = N0->getOperand(0).getValueSizeInBits();
2237         PreExt = N0->getOperand(0);
2238         Signed = true;
2239       } else if (auto *LN0 = dyn_cast<LoadSDNode>(N0)) {
2240         // ZEXTLOAD / SEXTLOAD
2241         if (LN0->getExtensionType() == ISD::ZEXTLOAD) {
2242           MinBits = LN0->getMemoryVT().getSizeInBits();
2243           PreExt = N0;
2244         } else if (LN0->getExtensionType() == ISD::SEXTLOAD) {
2245           Signed = true;
2246           MinBits = LN0->getMemoryVT().getSizeInBits();
2247           PreExt = N0;
2248         }
2249       }
2250
2251       // Figure out how many bits we need to preserve this constant.
2252       unsigned ReqdBits = Signed ?
2253         C1.getBitWidth() - C1.getNumSignBits() + 1 :
2254         C1.getActiveBits();
2255
2256       // Make sure we're not losing bits from the constant.
2257       if (MinBits > 0 &&
2258           MinBits < C1.getBitWidth() &&
2259           MinBits >= ReqdBits) {
2260         EVT MinVT = EVT::getIntegerVT(*DAG.getContext(), MinBits);
2261         if (isTypeDesirableForOp(ISD::SETCC, MinVT)) {
2262           // Will get folded away.
2263           SDValue Trunc = DAG.getNode(ISD::TRUNCATE, dl, MinVT, PreExt);
2264           if (MinBits == 1 && C1 == 1)
2265             // Invert the condition.
2266             return DAG.getSetCC(dl, VT, Trunc, DAG.getConstant(0, dl, MVT::i1),
2267                                 Cond == ISD::SETEQ ? ISD::SETNE : ISD::SETEQ);
2268           SDValue C = DAG.getConstant(C1.trunc(MinBits), dl, MinVT);
2269           return DAG.getSetCC(dl, VT, Trunc, C, Cond);
2270         }
2271
2272         // If truncating the setcc operands is not desirable, we can still
2273         // simplify the expression in some cases:
2274         // setcc ([sz]ext (setcc x, y, cc)), 0, setne) -> setcc (x, y, cc)
2275         // setcc ([sz]ext (setcc x, y, cc)), 0, seteq) -> setcc (x, y, inv(cc))
2276         // setcc (zext (setcc x, y, cc)), 1, setne) -> setcc (x, y, inv(cc))
2277         // setcc (zext (setcc x, y, cc)), 1, seteq) -> setcc (x, y, cc)
2278         // setcc (sext (setcc x, y, cc)), -1, setne) -> setcc (x, y, inv(cc))
2279         // setcc (sext (setcc x, y, cc)), -1, seteq) -> setcc (x, y, cc)
2280         SDValue TopSetCC = N0->getOperand(0);
2281         unsigned N0Opc = N0->getOpcode();
2282         bool SExt = (N0Opc == ISD::SIGN_EXTEND);
2283         if (TopSetCC.getValueType() == MVT::i1 && VT == MVT::i1 &&
2284             TopSetCC.getOpcode() == ISD::SETCC &&
2285             (N0Opc == ISD::ZERO_EXTEND || N0Opc == ISD::SIGN_EXTEND) &&
2286             (isConstFalseVal(N1C) ||
2287              isExtendedTrueVal(N1C, N0->getValueType(0), SExt))) {
2288
2289           bool Inverse = (N1C->isNullValue() && Cond == ISD::SETEQ) ||
2290                          (!N1C->isNullValue() && Cond == ISD::SETNE);
2291
2292           if (!Inverse)
2293             return TopSetCC;
2294
2295           ISD::CondCode InvCond = ISD::getSetCCInverse(
2296               cast<CondCodeSDNode>(TopSetCC.getOperand(2))->get(),
2297               TopSetCC.getOperand(0).getValueType().isInteger());
2298           return DAG.getSetCC(dl, VT, TopSetCC.getOperand(0),
2299                                       TopSetCC.getOperand(1),
2300                                       InvCond);
2301         }
2302       }
2303     }
2304
2305     // If the LHS is '(and load, const)', the RHS is 0, the test is for
2306     // equality or unsigned, and all 1 bits of the const are in the same
2307     // partial word, see if we can shorten the load.
2308     if (DCI.isBeforeLegalize() &&
2309         !ISD::isSignedIntSetCC(Cond) &&
2310         N0.getOpcode() == ISD::AND && C1 == 0 &&
2311         N0.getNode()->hasOneUse() &&
2312         isa<LoadSDNode>(N0.getOperand(0)) &&
2313         N0.getOperand(0).getNode()->hasOneUse() &&
2314         isa<ConstantSDNode>(N0.getOperand(1))) {
2315       LoadSDNode *Lod = cast<LoadSDNode>(N0.getOperand(0));
2316       APInt bestMask;
2317       unsigned bestWidth = 0, bestOffset = 0;
2318       if (!Lod->isVolatile() && Lod->isUnindexed()) {
2319         unsigned origWidth = N0.getValueSizeInBits();
2320         unsigned maskWidth = origWidth;
2321         // We can narrow (e.g.) 16-bit extending loads on 32-bit target to
2322         // 8 bits, but have to be careful...
2323         if (Lod->getExtensionType() != ISD::NON_EXTLOAD)
2324           origWidth = Lod->getMemoryVT().getSizeInBits();
2325         const APInt &Mask =
2326           cast<ConstantSDNode>(N0.getOperand(1))->getAPIntValue();
2327         for (unsigned width = origWidth / 2; width>=8; width /= 2) {
2328           APInt newMask = APInt::getLowBitsSet(maskWidth, width);
2329           for (unsigned offset=0; offset<origWidth/width; offset++) {
2330             if (Mask.isSubsetOf(newMask)) {
2331               if (DAG.getDataLayout().isLittleEndian())
2332                 bestOffset = (uint64_t)offset * (width/8);
2333               else
2334                 bestOffset = (origWidth/width - offset - 1) * (width/8);
2335               bestMask = Mask.lshr(offset * (width/8) * 8);
2336               bestWidth = width;
2337               break;
2338             }
2339             newMask <<= width;
2340           }
2341         }
2342       }
2343       if (bestWidth) {
2344         EVT newVT = EVT::getIntegerVT(*DAG.getContext(), bestWidth);
2345         if (newVT.isRound() &&
2346             shouldReduceLoadWidth(Lod, ISD::NON_EXTLOAD, newVT)) {
2347           EVT PtrType = Lod->getOperand(1).getValueType();
2348           SDValue Ptr = Lod->getBasePtr();
2349           if (bestOffset != 0)
2350             Ptr = DAG.getNode(ISD::ADD, dl, PtrType, Lod->getBasePtr(),
2351                               DAG.getConstant(bestOffset, dl, PtrType));
2352           unsigned NewAlign = MinAlign(Lod->getAlignment(), bestOffset);
2353           SDValue NewLoad = DAG.getLoad(
2354               newVT, dl, Lod->getChain(), Ptr,
2355               Lod->getPointerInfo().getWithOffset(bestOffset), NewAlign);
2356           return DAG.getSetCC(dl, VT,
2357                               DAG.getNode(ISD::AND, dl, newVT, NewLoad,
2358                                       DAG.getConstant(bestMask.trunc(bestWidth),
2359                                                       dl, newVT)),
2360                               DAG.getConstant(0LL, dl, newVT), Cond);
2361         }
2362       }
2363     }
2364
2365     // If the LHS is a ZERO_EXTEND, perform the comparison on the input.
2366     if (N0.getOpcode() == ISD::ZERO_EXTEND) {
2367       unsigned InSize = N0.getOperand(0).getValueSizeInBits();
2368
2369       // If the comparison constant has bits in the upper part, the
2370       // zero-extended value could never match.
2371       if (C1.intersects(APInt::getHighBitsSet(C1.getBitWidth(),
2372                                               C1.getBitWidth() - InSize))) {
2373         switch (Cond) {
2374         case ISD::SETUGT:
2375         case ISD::SETUGE:
2376         case ISD::SETEQ:
2377           return DAG.getConstant(0, dl, VT);
2378         case ISD::SETULT:
2379         case ISD::SETULE:
2380         case ISD::SETNE:
2381           return DAG.getConstant(1, dl, VT);
2382         case ISD::SETGT:
2383         case ISD::SETGE:
2384           // True if the sign bit of C1 is set.
2385           return DAG.getConstant(C1.isNegative(), dl, VT);
2386         case ISD::SETLT:
2387         case ISD::SETLE:
2388           // True if the sign bit of C1 isn't set.
2389           return DAG.getConstant(C1.isNonNegative(), dl, VT);
2390         default:
2391           break;
2392         }
2393       }
2394
2395       // Otherwise, we can perform the comparison with the low bits.
2396       switch (Cond) {
2397       case ISD::SETEQ:
2398       case ISD::SETNE:
2399       case ISD::SETUGT:
2400       case ISD::SETUGE:
2401       case ISD::SETULT:
2402       case ISD::SETULE: {
2403         EVT newVT = N0.getOperand(0).getValueType();
2404         if (DCI.isBeforeLegalizeOps() ||
2405             (isOperationLegal(ISD::SETCC, newVT) &&
2406              isCondCodeLegal(Cond, newVT.getSimpleVT()))) {
2407           EVT NewSetCCVT =
2408               getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), newVT);
2409           SDValue NewConst = DAG.getConstant(C1.trunc(InSize), dl, newVT);
2410
2411           SDValue NewSetCC = DAG.getSetCC(dl, NewSetCCVT, N0.getOperand(0),
2412                                           NewConst, Cond);
2413           return DAG.getBoolExtOrTrunc(NewSetCC, dl, VT, N0.getValueType());
2414         }
2415         break;
2416       }
2417       default:
2418         break;   // todo, be more careful with signed comparisons
2419       }
2420     } else if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG &&
2421                (Cond == ISD::SETEQ || Cond == ISD::SETNE)) {
2422       EVT ExtSrcTy = cast<VTSDNode>(N0.getOperand(1))->getVT();
2423       unsigned ExtSrcTyBits = ExtSrcTy.getSizeInBits();
2424       EVT ExtDstTy = N0.getValueType();
2425       unsigned ExtDstTyBits = ExtDstTy.getSizeInBits();
2426
2427       // If the constant doesn't fit into the number of bits for the source of
2428       // the sign extension, it is impossible for both sides to be equal.
2429       if (C1.getMinSignedBits() > ExtSrcTyBits)
2430         return DAG.getConstant(Cond == ISD::SETNE, dl, VT);
2431
2432       SDValue ZextOp;
2433       EVT Op0Ty = N0.getOperand(0).getValueType();
2434       if (Op0Ty == ExtSrcTy) {
2435         ZextOp = N0.getOperand(0);
2436       } else {
2437         APInt Imm = APInt::getLowBitsSet(ExtDstTyBits, ExtSrcTyBits);
2438         ZextOp = DAG.getNode(ISD::AND, dl, Op0Ty, N0.getOperand(0),
2439                               DAG.getConstant(Imm, dl, Op0Ty));
2440       }
2441       if (!DCI.isCalledByLegalizer())
2442         DCI.AddToWorklist(ZextOp.getNode());
2443       // Otherwise, make this a use of a zext.
2444       return DAG.getSetCC(dl, VT, ZextOp,
2445                           DAG.getConstant(C1 & APInt::getLowBitsSet(
2446                                                               ExtDstTyBits,
2447                                                               ExtSrcTyBits),
2448                                           dl, ExtDstTy),
2449                           Cond);
2450     } else if ((N1C->isNullValue() || N1C->isOne()) &&
2451                 (Cond == ISD::SETEQ || Cond == ISD::SETNE)) {
2452       // SETCC (SETCC), [0|1], [EQ|NE]  -> SETCC
2453       if (N0.getOpcode() == ISD::SETCC &&
2454           isTypeLegal(VT) && VT.bitsLE(N0.getValueType())) {
2455         bool TrueWhenTrue = (Cond == ISD::SETEQ) ^ (!N1C->isOne());
2456         if (TrueWhenTrue)
2457           return DAG.getNode(ISD::TRUNCATE, dl, VT, N0);
2458         // Invert the condition.
2459         ISD::CondCode CC = cast<CondCodeSDNode>(N0.getOperand(2))->get();
2460         CC = ISD::getSetCCInverse(CC,
2461                                   N0.getOperand(0).getValueType().isInteger());
2462         if (DCI.isBeforeLegalizeOps() ||
2463             isCondCodeLegal(CC, N0.getOperand(0).getSimpleValueType()))
2464           return DAG.getSetCC(dl, VT, N0.getOperand(0), N0.getOperand(1), CC);
2465       }
2466
2467       if ((N0.getOpcode() == ISD::XOR ||
2468            (N0.getOpcode() == ISD::AND &&
2469             N0.getOperand(0).getOpcode() == ISD::XOR &&
2470             N0.getOperand(1) == N0.getOperand(0).getOperand(1))) &&
2471           isa<ConstantSDNode>(N0.getOperand(1)) &&
2472           cast<ConstantSDNode>(N0.getOperand(1))->isOne()) {
2473         // If this is (X^1) == 0/1, swap the RHS and eliminate the xor.  We
2474         // can only do this if the top bits are known zero.
2475         unsigned BitWidth = N0.getValueSizeInBits();
2476         if (DAG.MaskedValueIsZero(N0,
2477                                   APInt::getHighBitsSet(BitWidth,
2478                                                         BitWidth-1))) {
2479           // Okay, get the un-inverted input value.
2480           SDValue Val;
2481           if (N0.getOpcode() == ISD::XOR) {
2482             Val = N0.getOperand(0);
2483           } else {
2484             assert(N0.getOpcode() == ISD::AND &&
2485                     N0.getOperand(0).getOpcode() == ISD::XOR);
2486             // ((X^1)&1)^1 -> X & 1
2487             Val = DAG.getNode(ISD::AND, dl, N0.getValueType(),
2488                               N0.getOperand(0).getOperand(0),
2489                               N0.getOperand(1));
2490           }
2491
2492           return DAG.getSetCC(dl, VT, Val, N1,
2493                               Cond == ISD::SETEQ ? ISD::SETNE : ISD::SETEQ);
2494         }
2495       } else if (N1C->isOne() &&
2496                  (VT == MVT::i1 ||
2497                   getBooleanContents(N0->getValueType(0)) ==
2498                       ZeroOrOneBooleanContent)) {
2499         SDValue Op0 = N0;
2500         if (Op0.getOpcode() == ISD::TRUNCATE)
2501           Op0 = Op0.getOperand(0);
2502
2503         if ((Op0.getOpcode() == ISD::XOR) &&
2504             Op0.getOperand(0).getOpcode() == ISD::SETCC &&
2505             Op0.getOperand(1).getOpcode() == ISD::SETCC) {
2506           // (xor (setcc), (setcc)) == / != 1 -> (setcc) != / == (setcc)
2507           Cond = (Cond == ISD::SETEQ) ? ISD::SETNE : ISD::SETEQ;
2508           return DAG.getSetCC(dl, VT, Op0.getOperand(0), Op0.getOperand(1),
2509                               Cond);
2510         }
2511         if (Op0.getOpcode() == ISD::AND &&
2512             isa<ConstantSDNode>(Op0.getOperand(1)) &&
2513             cast<ConstantSDNode>(Op0.getOperand(1))->isOne()) {
2514           // If this is (X&1) == / != 1, normalize it to (X&1) != / == 0.
2515           if (Op0.getValueType().bitsGT(VT))
2516             Op0 = DAG.getNode(ISD::AND, dl, VT,
2517                           DAG.getNode(ISD::TRUNCATE, dl, VT, Op0.getOperand(0)),
2518                           DAG.getConstant(1, dl, VT));
2519           else if (Op0.getValueType().bitsLT(VT))
2520             Op0 = DAG.getNode(ISD::AND, dl, VT,
2521                         DAG.getNode(ISD::ANY_EXTEND, dl, VT, Op0.getOperand(0)),
2522                         DAG.getConstant(1, dl, VT));
2523
2524           return DAG.getSetCC(dl, VT, Op0,
2525                               DAG.getConstant(0, dl, Op0.getValueType()),
2526                               Cond == ISD::SETEQ ? ISD::SETNE : ISD::SETEQ);
2527         }
2528         if (Op0.getOpcode() == ISD::AssertZext &&
2529             cast<VTSDNode>(Op0.getOperand(1))->getVT() == MVT::i1)
2530           return DAG.getSetCC(dl, VT, Op0,
2531                               DAG.getConstant(0, dl, Op0.getValueType()),
2532                               Cond == ISD::SETEQ ? ISD::SETNE : ISD::SETEQ);
2533       }
2534     }
2535
2536     if (SDValue V =
2537             optimizeSetCCOfSignedTruncationCheck(VT, N0, N1, Cond, DCI, dl))
2538       return V;
2539   }
2540
2541   // These simplifications apply to splat vectors as well.
2542   // TODO: Handle more splat vector cases.
2543   if (auto *N1C = isConstOrConstSplat(N1)) {
2544     const APInt &C1 = N1C->getAPIntValue();
2545
2546     APInt MinVal, MaxVal;
2547     unsigned OperandBitSize = N1C->getValueType(0).getScalarSizeInBits();
2548     if (ISD::isSignedIntSetCC(Cond)) {
2549       MinVal = APInt::getSignedMinValue(OperandBitSize);
2550       MaxVal = APInt::getSignedMaxValue(OperandBitSize);
2551     } else {
2552       MinVal = APInt::getMinValue(OperandBitSize);
2553       MaxVal = APInt::getMaxValue(OperandBitSize);
2554     }
2555
2556     // Canonicalize GE/LE comparisons to use GT/LT comparisons.
2557     if (Cond == ISD::SETGE || Cond == ISD::SETUGE) {
2558       // X >= MIN --> true
2559       if (C1 == MinVal)
2560         return DAG.getBoolConstant(true, dl, VT, OpVT);
2561
2562       if (!VT.isVector()) { // TODO: Support this for vectors.
2563         // X >= C0 --> X > (C0 - 1)
2564         APInt C = C1 - 1;
2565         ISD::CondCode NewCC = (Cond == ISD::SETGE) ? ISD::SETGT : ISD::SETUGT;
2566         if ((DCI.isBeforeLegalizeOps() ||
2567              isCondCodeLegal(NewCC, VT.getSimpleVT())) &&
2568             (!N1C->isOpaque() || (C.getBitWidth() <= 64 &&
2569                                   isLegalICmpImmediate(C.getSExtValue())))) {
2570           return DAG.getSetCC(dl, VT, N0,
2571                               DAG.getConstant(C, dl, N1.getValueType()),
2572                               NewCC);
2573         }
2574       }
2575     }
2576
2577     if (Cond == ISD::SETLE || Cond == ISD::SETULE) {
2578       // X <= MAX --> true
2579       if (C1 == MaxVal)
2580         return DAG.getBoolConstant(true, dl, VT, OpVT);
2581
2582       // X <= C0 --> X < (C0 + 1)
2583       if (!VT.isVector()) { // TODO: Support this for vectors.
2584         APInt C = C1 + 1;
2585         ISD::CondCode NewCC = (Cond == ISD::SETLE) ? ISD::SETLT : ISD::SETULT;
2586         if ((DCI.isBeforeLegalizeOps() ||
2587              isCondCodeLegal(NewCC, VT.getSimpleVT())) &&
2588             (!N1C->isOpaque() || (C.getBitWidth() <= 64 &&
2589                                   isLegalICmpImmediate(C.getSExtValue())))) {
2590           return DAG.getSetCC(dl, VT, N0,
2591                               DAG.getConstant(C, dl, N1.getValueType()),
2592                               NewCC);
2593         }
2594       }
2595     }
2596
2597     if (Cond == ISD::SETLT || Cond == ISD::SETULT) {
2598       if (C1 == MinVal)
2599         return DAG.getBoolConstant(false, dl, VT, OpVT); // X < MIN --> false
2600
2601       // TODO: Support this for vectors after legalize ops.
2602       if (!VT.isVector() || DCI.isBeforeLegalizeOps()) {
2603         // Canonicalize setlt X, Max --> setne X, Max
2604         if (C1 == MaxVal)
2605           return DAG.getSetCC(dl, VT, N0, N1, ISD::SETNE);
2606
2607         // If we have setult X, 1, turn it into seteq X, 0
2608         if (C1 == MinVal+1)
2609           return DAG.getSetCC(dl, VT, N0,
2610                               DAG.getConstant(MinVal, dl, N0.getValueType()),
2611                               ISD::SETEQ);
2612       }
2613     }
2614
2615     if (Cond == ISD::SETGT || Cond == ISD::SETUGT) {
2616       if (C1 == MaxVal)
2617         return DAG.getBoolConstant(false, dl, VT, OpVT); // X > MAX --> false
2618
2619       // TODO: Support this for vectors after legalize ops.
2620       if (!VT.isVector() || DCI.isBeforeLegalizeOps()) {
2621         // Canonicalize setgt X, Min --> setne X, Min
2622         if (C1 == MinVal)
2623           return DAG.getSetCC(dl, VT, N0, N1, ISD::SETNE);
2624
2625         // If we have setugt X, Max-1, turn it into seteq X, Max
2626         if (C1 == MaxVal-1)
2627           return DAG.getSetCC(dl, VT, N0,
2628                               DAG.getConstant(MaxVal, dl, N0.getValueType()),
2629                               ISD::SETEQ);
2630       }
2631     }
2632
2633     // If we have "setcc X, C0", check to see if we can shrink the immediate
2634     // by changing cc.
2635     // TODO: Support this for vectors after legalize ops.
2636     if (!VT.isVector() || DCI.isBeforeLegalizeOps()) {
2637       // SETUGT X, SINTMAX  -> SETLT X, 0
2638       if (Cond == ISD::SETUGT &&
2639           C1 == APInt::getSignedMaxValue(OperandBitSize))
2640         return DAG.getSetCC(dl, VT, N0,
2641                             DAG.getConstant(0, dl, N1.getValueType()),
2642                             ISD::SETLT);
2643
2644       // SETULT X, SINTMIN  -> SETGT X, -1
2645       if (Cond == ISD::SETULT &&
2646           C1 == APInt::getSignedMinValue(OperandBitSize)) {
2647         SDValue ConstMinusOne =
2648             DAG.getConstant(APInt::getAllOnesValue(OperandBitSize), dl,
2649                             N1.getValueType());
2650         return DAG.getSetCC(dl, VT, N0, ConstMinusOne, ISD::SETGT);
2651       }
2652     }
2653   }
2654
2655   // Back to non-vector simplifications.
2656   // TODO: Can we do these for vector splats?
2657   if (auto *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
2658     const APInt &C1 = N1C->getAPIntValue();
2659
2660     // Fold bit comparisons when we can.
2661     if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
2662         (VT == N0.getValueType() ||
2663          (isTypeLegal(VT) && VT.bitsLE(N0.getValueType()))) &&
2664         N0.getOpcode() == ISD::AND) {
2665       auto &DL = DAG.getDataLayout();
2666       if (auto *AndRHS = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
2667         EVT ShiftTy = getShiftAmountTy(N0.getValueType(), DL,
2668                                        !DCI.isBeforeLegalize());
2669         if (Cond == ISD::SETNE && C1 == 0) {// (X & 8) != 0  -->  (X & 8) >> 3
2670           // Perform the xform if the AND RHS is a single bit.
2671           if (AndRHS->getAPIntValue().isPowerOf2()) {
2672             return DAG.getNode(ISD::TRUNCATE, dl, VT,
2673                               DAG.getNode(ISD::SRL, dl, N0.getValueType(), N0,
2674                    DAG.getConstant(AndRHS->getAPIntValue().logBase2(), dl,
2675                                    ShiftTy)));
2676           }
2677         } else if (Cond == ISD::SETEQ && C1 == AndRHS->getAPIntValue()) {
2678           // (X & 8) == 8  -->  (X & 8) >> 3
2679           // Perform the xform if C1 is a single bit.
2680           if (C1.isPowerOf2()) {
2681             return DAG.getNode(ISD::TRUNCATE, dl, VT,
2682                                DAG.getNode(ISD::SRL, dl, N0.getValueType(), N0,
2683                                       DAG.getConstant(C1.logBase2(), dl,
2684                                                       ShiftTy)));
2685           }
2686         }
2687       }
2688     }
2689
2690     if (C1.getMinSignedBits() <= 64 &&
2691         !isLegalICmpImmediate(C1.getSExtValue())) {
2692       // (X & -256) == 256 -> (X >> 8) == 1
2693       if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
2694           N0.getOpcode() == ISD::AND && N0.hasOneUse()) {
2695         if (auto *AndRHS = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
2696           const APInt &AndRHSC = AndRHS->getAPIntValue();
2697           if ((-AndRHSC).isPowerOf2() && (AndRHSC & C1) == C1) {
2698             unsigned ShiftBits = AndRHSC.countTrailingZeros();
2699             auto &DL = DAG.getDataLayout();
2700             EVT ShiftTy = getShiftAmountTy(N0.getValueType(), DL,
2701                                            !DCI.isBeforeLegalize());
2702             EVT CmpTy = N0.getValueType();
2703             SDValue Shift = DAG.getNode(ISD::SRL, dl, CmpTy, N0.getOperand(0),
2704                                         DAG.getConstant(ShiftBits, dl,
2705                                                         ShiftTy));
2706             SDValue CmpRHS = DAG.getConstant(C1.lshr(ShiftBits), dl, CmpTy);
2707             return DAG.getSetCC(dl, VT, Shift, CmpRHS, Cond);
2708           }
2709         }
2710       } else if (Cond == ISD::SETULT || Cond == ISD::SETUGE ||
2711                  Cond == ISD::SETULE || Cond == ISD::SETUGT) {
2712         bool AdjOne = (Cond == ISD::SETULE || Cond == ISD::SETUGT);
2713         // X <  0x100000000 -> (X >> 32) <  1
2714         // X >= 0x100000000 -> (X >> 32) >= 1
2715         // X <= 0x0ffffffff -> (X >> 32) <  1
2716         // X >  0x0ffffffff -> (X >> 32) >= 1
2717         unsigned ShiftBits;
2718         APInt NewC = C1;
2719         ISD::CondCode NewCond = Cond;
2720         if (AdjOne) {
2721           ShiftBits = C1.countTrailingOnes();
2722           NewC = NewC + 1;
2723           NewCond = (Cond == ISD::SETULE) ? ISD::SETULT : ISD::SETUGE;
2724         } else {
2725           ShiftBits = C1.countTrailingZeros();
2726         }
2727         NewC.lshrInPlace(ShiftBits);
2728         if (ShiftBits && NewC.getMinSignedBits() <= 64 &&
2729           isLegalICmpImmediate(NewC.getSExtValue())) {
2730           auto &DL = DAG.getDataLayout();
2731           EVT ShiftTy = getShiftAmountTy(N0.getValueType(), DL,
2732                                          !DCI.isBeforeLegalize());
2733           EVT CmpTy = N0.getValueType();
2734           SDValue Shift = DAG.getNode(ISD::SRL, dl, CmpTy, N0,
2735                                       DAG.getConstant(ShiftBits, dl, ShiftTy));
2736           SDValue CmpRHS = DAG.getConstant(NewC, dl, CmpTy);
2737           return DAG.getSetCC(dl, VT, Shift, CmpRHS, NewCond);
2738         }
2739       }
2740     }
2741   }
2742
2743   if (isa<ConstantFPSDNode>(N0.getNode())) {
2744     // Constant fold or commute setcc.
2745     SDValue O = DAG.FoldSetCC(VT, N0, N1, Cond, dl);
2746     if (O.getNode()) return O;
2747   } else if (auto *CFP = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
2748     // If the RHS of an FP comparison is a constant, simplify it away in
2749     // some cases.
2750     if (CFP->getValueAPF().isNaN()) {
2751       // If an operand is known to be a nan, we can fold it.
2752       switch (ISD::getUnorderedFlavor(Cond)) {
2753       default: llvm_unreachable("Unknown flavor!");
2754       case 0:  // Known false.
2755         return DAG.getBoolConstant(false, dl, VT, OpVT);
2756       case 1:  // Known true.
2757         return DAG.getBoolConstant(true, dl, VT, OpVT);
2758       case 2:  // Undefined.
2759         return DAG.getUNDEF(VT);
2760       }
2761     }
2762
2763     // Otherwise, we know the RHS is not a NaN.  Simplify the node to drop the
2764     // constant if knowing that the operand is non-nan is enough.  We prefer to
2765     // have SETO(x,x) instead of SETO(x, 0.0) because this avoids having to
2766     // materialize 0.0.
2767     if (Cond == ISD::SETO || Cond == ISD::SETUO)
2768       return DAG.getSetCC(dl, VT, N0, N0, Cond);
2769
2770     // setcc (fneg x), C -> setcc swap(pred) x, -C
2771     if (N0.getOpcode() == ISD::FNEG) {
2772       ISD::CondCode SwapCond = ISD::getSetCCSwappedOperands(Cond);
2773       if (DCI.isBeforeLegalizeOps() ||
2774           isCondCodeLegal(SwapCond, N0.getSimpleValueType())) {
2775         SDValue NegN1 = DAG.getNode(ISD::FNEG, dl, N0.getValueType(), N1);
2776         return DAG.getSetCC(dl, VT, N0.getOperand(0), NegN1, SwapCond);
2777       }
2778     }
2779
2780     // If the condition is not legal, see if we can find an equivalent one
2781     // which is legal.
2782     if (!isCondCodeLegal(Cond, N0.getSimpleValueType())) {
2783       // If the comparison was an awkward floating-point == or != and one of
2784       // the comparison operands is infinity or negative infinity, convert the
2785       // condition to a less-awkward <= or >=.
2786       if (CFP->getValueAPF().isInfinity()) {
2787         if (CFP->getValueAPF().isNegative()) {
2788           if (Cond == ISD::SETOEQ &&
2789               isCondCodeLegal(ISD::SETOLE, N0.getSimpleValueType()))
2790             return DAG.getSetCC(dl, VT, N0, N1, ISD::SETOLE);
2791           if (Cond == ISD::SETUEQ &&
2792               isCondCodeLegal(ISD::SETOLE, N0.getSimpleValueType()))
2793             return DAG.getSetCC(dl, VT, N0, N1, ISD::SETULE);
2794           if (Cond == ISD::SETUNE &&
2795               isCondCodeLegal(ISD::SETUGT, N0.getSimpleValueType()))
2796             return DAG.getSetCC(dl, VT, N0, N1, ISD::SETUGT);
2797           if (Cond == ISD::SETONE &&
2798               isCondCodeLegal(ISD::SETUGT, N0.getSimpleValueType()))
2799             return DAG.getSetCC(dl, VT, N0, N1, ISD::SETOGT);
2800         } else {
2801           if (Cond == ISD::SETOEQ &&
2802               isCondCodeLegal(ISD::SETOGE, N0.getSimpleValueType()))
2803             return DAG.getSetCC(dl, VT, N0, N1, ISD::SETOGE);
2804           if (Cond == ISD::SETUEQ &&
2805               isCondCodeLegal(ISD::SETOGE, N0.getSimpleValueType()))
2806             return DAG.getSetCC(dl, VT, N0, N1, ISD::SETUGE);
2807           if (Cond == ISD::SETUNE &&
2808               isCondCodeLegal(ISD::SETULT, N0.getSimpleValueType()))
2809             return DAG.getSetCC(dl, VT, N0, N1, ISD::SETULT);
2810           if (Cond == ISD::SETONE &&
2811               isCondCodeLegal(ISD::SETULT, N0.getSimpleValueType()))
2812             return DAG.getSetCC(dl, VT, N0, N1, ISD::SETOLT);
2813         }
2814       }
2815     }
2816   }
2817
2818   if (N0 == N1) {
2819     // The sext(setcc()) => setcc() optimization relies on the appropriate
2820     // constant being emitted.
2821
2822     bool EqTrue = ISD::isTrueWhenEqual(Cond);
2823
2824     // We can always fold X == X for integer setcc's.
2825     if (N0.getValueType().isInteger())
2826       return DAG.getBoolConstant(EqTrue, dl, VT, OpVT);
2827
2828     unsigned UOF = ISD::getUnorderedFlavor(Cond);
2829     if (UOF == 2)   // FP operators that are undefined on NaNs.
2830       return DAG.getBoolConstant(EqTrue, dl, VT, OpVT);
2831     if (UOF == unsigned(EqTrue))
2832       return DAG.getBoolConstant(EqTrue, dl, VT, OpVT);
2833     // Otherwise, we can't fold it.  However, we can simplify it to SETUO/SETO
2834     // if it is not already.
2835     ISD::CondCode NewCond = UOF == 0 ? ISD::SETO : ISD::SETUO;
2836     if (NewCond != Cond &&
2837         (DCI.isBeforeLegalizeOps() ||
2838          isCondCodeLegal(NewCond, N0.getSimpleValueType())))
2839       return DAG.getSetCC(dl, VT, N0, N1, NewCond);
2840   }
2841
2842   if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
2843       N0.getValueType().isInteger()) {
2844     if (N0.getOpcode() == ISD::ADD || N0.getOpcode() == ISD::SUB ||
2845         N0.getOpcode() == ISD::XOR) {
2846       // Simplify (X+Y) == (X+Z) -->  Y == Z
2847       if (N0.getOpcode() == N1.getOpcode()) {
2848         if (N0.getOperand(0) == N1.getOperand(0))
2849           return DAG.getSetCC(dl, VT, N0.getOperand(1), N1.getOperand(1), Cond);
2850         if (N0.getOperand(1) == N1.getOperand(1))
2851           return DAG.getSetCC(dl, VT, N0.getOperand(0), N1.getOperand(0), Cond);
2852         if (isCommutativeBinOp(N0.getOpcode())) {
2853           // If X op Y == Y op X, try other combinations.
2854           if (N0.getOperand(0) == N1.getOperand(1))
2855             return DAG.getSetCC(dl, VT, N0.getOperand(1), N1.getOperand(0),
2856                                 Cond);
2857           if (N0.getOperand(1) == N1.getOperand(0))
2858             return DAG.getSetCC(dl, VT, N0.getOperand(0), N1.getOperand(1),
2859                                 Cond);
2860         }
2861       }
2862
2863       // If RHS is a legal immediate value for a compare instruction, we need
2864       // to be careful about increasing register pressure needlessly.
2865       bool LegalRHSImm = false;
2866
2867       if (auto *RHSC = dyn_cast<ConstantSDNode>(N1)) {
2868         if (auto *LHSR = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
2869           // Turn (X+C1) == C2 --> X == C2-C1
2870           if (N0.getOpcode() == ISD::ADD && N0.getNode()->hasOneUse()) {
2871             return DAG.getSetCC(dl, VT, N0.getOperand(0),
2872                                 DAG.getConstant(RHSC->getAPIntValue()-
2873                                                 LHSR->getAPIntValue(),
2874                                 dl, N0.getValueType()), Cond);
2875           }
2876
2877           // Turn (X^C1) == C2 into X == C1^C2 iff X&~C1 = 0.
2878           if (N0.getOpcode() == ISD::XOR)
2879             // If we know that all of the inverted bits are zero, don't bother
2880             // performing the inversion.
2881             if (DAG.MaskedValueIsZero(N0.getOperand(0), ~LHSR->getAPIntValue()))
2882               return
2883                 DAG.getSetCC(dl, VT, N0.getOperand(0),
2884                              DAG.getConstant(LHSR->getAPIntValue() ^
2885                                                RHSC->getAPIntValue(),
2886                                              dl, N0.getValueType()),
2887                              Cond);
2888         }
2889
2890         // Turn (C1-X) == C2 --> X == C1-C2
2891         if (auto *SUBC = dyn_cast<ConstantSDNode>(N0.getOperand(0))) {
2892           if (N0.getOpcode() == ISD::SUB && N0.getNode()->hasOneUse()) {
2893             return
2894               DAG.getSetCC(dl, VT, N0.getOperand(1),
2895                            DAG.getConstant(SUBC->getAPIntValue() -
2896                                              RHSC->getAPIntValue(),
2897                                            dl, N0.getValueType()),
2898                            Cond);
2899           }
2900         }
2901
2902         // Could RHSC fold directly into a compare?
2903         if (RHSC->getValueType(0).getSizeInBits() <= 64)
2904           LegalRHSImm = isLegalICmpImmediate(RHSC->getSExtValue());
2905       }
2906
2907       // Simplify (X+Z) == X -->  Z == 0
2908       // Don't do this if X is an immediate that can fold into a cmp
2909       // instruction and X+Z has other uses. It could be an induction variable
2910       // chain, and the transform would increase register pressure.
2911       if (!LegalRHSImm || N0.getNode()->hasOneUse()) {
2912         if (N0.getOperand(0) == N1)
2913           return DAG.getSetCC(dl, VT, N0.getOperand(1),
2914                               DAG.getConstant(0, dl, N0.getValueType()), Cond);
2915         if (N0.getOperand(1) == N1) {
2916           if (isCommutativeBinOp(N0.getOpcode()))
2917             return DAG.getSetCC(dl, VT, N0.getOperand(0),
2918                                 DAG.getConstant(0, dl, N0.getValueType()),
2919                                 Cond);
2920           if (N0.getNode()->hasOneUse()) {
2921             assert(N0.getOpcode() == ISD::SUB && "Unexpected operation!");
2922             auto &DL = DAG.getDataLayout();
2923             // (Z-X) == X  --> Z == X<<1
2924             SDValue SH = DAG.getNode(
2925                 ISD::SHL, dl, N1.getValueType(), N1,
2926                 DAG.getConstant(1, dl,
2927                                 getShiftAmountTy(N1.getValueType(), DL,
2928                                                  !DCI.isBeforeLegalize())));
2929             if (!DCI.isCalledByLegalizer())
2930               DCI.AddToWorklist(SH.getNode());
2931             return DAG.getSetCC(dl, VT, N0.getOperand(0), SH, Cond);
2932           }
2933         }
2934       }
2935     }
2936
2937     if (N1.getOpcode() == ISD::ADD || N1.getOpcode() == ISD::SUB ||
2938         N1.getOpcode() == ISD::XOR) {
2939       // Simplify  X == (X+Z) -->  Z == 0
2940       if (N1.getOperand(0) == N0)
2941         return DAG.getSetCC(dl, VT, N1.getOperand(1),
2942                         DAG.getConstant(0, dl, N1.getValueType()), Cond);
2943       if (N1.getOperand(1) == N0) {
2944         if (isCommutativeBinOp(N1.getOpcode()))
2945           return DAG.getSetCC(dl, VT, N1.getOperand(0),
2946                           DAG.getConstant(0, dl, N1.getValueType()), Cond);
2947         if (N1.getNode()->hasOneUse()) {
2948           assert(N1.getOpcode() == ISD::SUB && "Unexpected operation!");
2949           auto &DL = DAG.getDataLayout();
2950           // X == (Z-X)  --> X<<1 == Z
2951           SDValue SH = DAG.getNode(
2952               ISD::SHL, dl, N1.getValueType(), N0,
2953               DAG.getConstant(1, dl, getShiftAmountTy(N0.getValueType(), DL,
2954                                                       !DCI.isBeforeLegalize())));
2955           if (!DCI.isCalledByLegalizer())
2956             DCI.AddToWorklist(SH.getNode());
2957           return DAG.getSetCC(dl, VT, SH, N1.getOperand(0), Cond);
2958         }
2959       }
2960     }
2961
2962     if (SDValue V = simplifySetCCWithAnd(VT, N0, N1, Cond, DCI, dl))
2963       return V;
2964   }
2965
2966   // Fold away ALL boolean setcc's.
2967   SDValue Temp;
2968   if (N0.getValueType().getScalarType() == MVT::i1 && foldBooleans) {
2969     EVT OpVT = N0.getValueType();
2970     switch (Cond) {
2971     default: llvm_unreachable("Unknown integer setcc!");
2972     case ISD::SETEQ:  // X == Y  -> ~(X^Y)
2973       Temp = DAG.getNode(ISD::XOR, dl, OpVT, N0, N1);
2974       N0 = DAG.getNOT(dl, Temp, OpVT);
2975       if (!DCI.isCalledByLegalizer())
2976         DCI.AddToWorklist(Temp.getNode());
2977       break;
2978     case ISD::SETNE:  // X != Y   -->  (X^Y)
2979       N0 = DAG.getNode(ISD::XOR, dl, OpVT, N0, N1);
2980       break;
2981     case ISD::SETGT:  // X >s Y   -->  X == 0 & Y == 1  -->  ~X & Y
2982     case ISD::SETULT: // X <u Y   -->  X == 0 & Y == 1  -->  ~X & Y
2983       Temp = DAG.getNOT(dl, N0, OpVT);
2984       N0 = DAG.getNode(ISD::AND, dl, OpVT, N1, Temp);
2985       if (!DCI.isCalledByLegalizer())
2986         DCI.AddToWorklist(Temp.getNode());
2987       break;
2988     case ISD::SETLT:  // X <s Y   --> X == 1 & Y == 0  -->  ~Y & X
2989     case ISD::SETUGT: // X >u Y   --> X == 1 & Y == 0  -->  ~Y & X
2990       Temp = DAG.getNOT(dl, N1, OpVT);
2991       N0 = DAG.getNode(ISD::AND, dl, OpVT, N0, Temp);
2992       if (!DCI.isCalledByLegalizer())
2993         DCI.AddToWorklist(Temp.getNode());
2994       break;
2995     case ISD::SETULE: // X <=u Y  --> X == 0 | Y == 1  -->  ~X | Y
2996     case ISD::SETGE:  // X >=s Y  --> X == 0 | Y == 1  -->  ~X | Y
2997       Temp = DAG.getNOT(dl, N0, OpVT);
2998       N0 = DAG.getNode(ISD::OR, dl, OpVT, N1, Temp);
2999       if (!DCI.isCalledByLegalizer())
3000         DCI.AddToWorklist(Temp.getNode());
3001       break;
3002     case ISD::SETUGE: // X >=u Y  --> X == 1 | Y == 0  -->  ~Y | X
3003     case ISD::SETLE:  // X <=s Y  --> X == 1 | Y == 0  -->  ~Y | X
3004       Temp = DAG.getNOT(dl, N1, OpVT);
3005       N0 = DAG.getNode(ISD::OR, dl, OpVT, N0, Temp);
3006       break;
3007     }
3008     if (VT.getScalarType() != MVT::i1) {
3009       if (!DCI.isCalledByLegalizer())
3010         DCI.AddToWorklist(N0.getNode());
3011       // FIXME: If running after legalize, we probably can't do this.
3012       ISD::NodeType ExtendCode = getExtendForContent(getBooleanContents(OpVT));
3013       N0 = DAG.getNode(ExtendCode, dl, VT, N0);
3014     }
3015     return N0;
3016   }
3017
3018   // Could not fold it.
3019   return SDValue();
3020 }
3021
3022 /// Returns true (and the GlobalValue and the offset) if the node is a
3023 /// GlobalAddress + offset.
3024 bool TargetLowering::isGAPlusOffset(SDNode *WN, const GlobalValue *&GA,
3025                                     int64_t &Offset) const {
3026
3027   SDNode *N = unwrapAddress(SDValue(WN, 0)).getNode();
3028
3029   if (auto *GASD = dyn_cast<GlobalAddressSDNode>(N)) {
3030     GA = GASD->getGlobal();
3031     Offset += GASD->getOffset();
3032     return true;
3033   }
3034
3035   if (N->getOpcode() == ISD::ADD) {
3036     SDValue N1 = N->getOperand(0);
3037     SDValue N2 = N->getOperand(1);
3038     if (isGAPlusOffset(N1.getNode(), GA, Offset)) {
3039       if (auto *V = dyn_cast<ConstantSDNode>(N2)) {
3040         Offset += V->getSExtValue();
3041         return true;
3042       }
3043     } else if (isGAPlusOffset(N2.getNode(), GA, Offset)) {
3044       if (auto *V = dyn_cast<ConstantSDNode>(N1)) {
3045         Offset += V->getSExtValue();
3046         return true;
3047       }
3048     }
3049   }
3050
3051   return false;
3052 }
3053
3054 SDValue TargetLowering::PerformDAGCombine(SDNode *N,
3055                                           DAGCombinerInfo &DCI) const {
3056   // Default implementation: no optimization.
3057   return SDValue();
3058 }
3059
3060 //===----------------------------------------------------------------------===//
3061 //  Inline Assembler Implementation Methods
3062 //===----------------------------------------------------------------------===//
3063
3064 TargetLowering::ConstraintType
3065 TargetLowering::getConstraintType(StringRef Constraint) const {
3066   unsigned S = Constraint.size();
3067
3068   if (S == 1) {
3069     switch (Constraint[0]) {
3070     default: break;
3071     case 'r': return C_RegisterClass;
3072     case 'm':    // memory
3073     case 'o':    // offsetable
3074     case 'V':    // not offsetable
3075       return C_Memory;
3076     case 'i':    // Simple Integer or Relocatable Constant
3077     case 'n':    // Simple Integer
3078     case 'E':    // Floating Point Constant
3079     case 'F':    // Floating Point Constant
3080     case 's':    // Relocatable Constant
3081     case 'p':    // Address.
3082     case 'X':    // Allow ANY value.
3083     case 'I':    // Target registers.
3084     case 'J':
3085     case 'K':
3086     case 'L':
3087     case 'M':
3088     case 'N':
3089     case 'O':
3090     case 'P':
3091     case '<':
3092     case '>':
3093       return C_Other;
3094     }
3095   }
3096
3097   if (S > 1 && Constraint[0] == '{' && Constraint[S-1] == '}') {
3098     if (S == 8 && Constraint.substr(1, 6) == "memory") // "{memory}"
3099       return C_Memory;
3100     return C_Register;
3101   }
3102   return C_Unknown;
3103 }
3104
3105 /// Try to replace an X constraint, which matches anything, with another that
3106 /// has more specific requirements based on the type of the corresponding
3107 /// operand.
3108 const char *TargetLowering::LowerXConstraint(EVT ConstraintVT) const{
3109   if (ConstraintVT.isInteger())
3110     return "r";
3111   if (ConstraintVT.isFloatingPoint())
3112     return "f";      // works for many targets
3113   return nullptr;
3114 }
3115
3116 /// Lower the specified operand into the Ops vector.
3117 /// If it is invalid, don't add anything to Ops.
3118 void TargetLowering::LowerAsmOperandForConstraint(SDValue Op,
3119                                                   std::string &Constraint,
3120                                                   std::vector<SDValue> &Ops,
3121                                                   SelectionDAG &DAG) const {
3122
3123   if (Constraint.length() > 1) return;
3124
3125   char ConstraintLetter = Constraint[0];
3126   switch (ConstraintLetter) {
3127   default: break;
3128   case 'X':     // Allows any operand; labels (basic block) use this.
3129     if (Op.getOpcode() == ISD::BasicBlock) {
3130       Ops.push_back(Op);
3131       return;
3132     }
3133     LLVM_FALLTHROUGH;
3134   case 'i':    // Simple Integer or Relocatable Constant
3135   case 'n':    // Simple Integer
3136   case 's': {  // Relocatable Constant
3137     // These operands are interested in values of the form (GV+C), where C may
3138     // be folded in as an offset of GV, or it may be explicitly added.  Also, it
3139     // is possible and fine if either GV or C are missing.
3140     ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op);
3141     GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(Op);
3142
3143     // If we have "(add GV, C)", pull out GV/C
3144     if (Op.getOpcode() == ISD::ADD) {
3145       C = dyn_cast<ConstantSDNode>(Op.getOperand(1));
3146       GA = dyn_cast<GlobalAddressSDNode>(Op.getOperand(0));
3147       if (!C || !GA) {
3148         C = dyn_cast<ConstantSDNode>(Op.getOperand(0));
3149         GA = dyn_cast<GlobalAddressSDNode>(Op.getOperand(1));
3150       }
3151       if (!C || !GA) {
3152         C = nullptr;
3153         GA = nullptr;
3154       }
3155     }
3156
3157     // If we find a valid operand, map to the TargetXXX version so that the
3158     // value itself doesn't get selected.
3159     if (GA) {   // Either &GV   or   &GV+C
3160       if (ConstraintLetter != 'n') {
3161         int64_t Offs = GA->getOffset();
3162         if (C) Offs += C->getZExtValue();
3163         Ops.push_back(DAG.getTargetGlobalAddress(GA->getGlobal(),
3164                                                  C ? SDLoc(C) : SDLoc(),
3165                                                  Op.getValueType(), Offs));
3166       }
3167       return;
3168     }
3169     if (C) {   // just C, no GV.
3170       // Simple constants are not allowed for 's'.
3171       if (ConstraintLetter != 's') {
3172         // gcc prints these as sign extended.  Sign extend value to 64 bits
3173         // now; without this it would get ZExt'd later in
3174         // ScheduleDAGSDNodes::EmitNode, which is very generic.
3175         Ops.push_back(DAG.getTargetConstant(C->getSExtValue(),
3176                                             SDLoc(C), MVT::i64));
3177       }
3178       return;
3179     }
3180     break;
3181   }
3182   }
3183 }
3184
3185 std::pair<unsigned, const TargetRegisterClass *>
3186 TargetLowering::getRegForInlineAsmConstraint(const TargetRegisterInfo *RI,
3187                                              StringRef Constraint,
3188                                              MVT VT) const {
3189   if (Constraint.empty() || Constraint[0] != '{')
3190     return std::make_pair(0u, static_cast<TargetRegisterClass*>(nullptr));
3191   assert(*(Constraint.end()-1) == '}' && "Not a brace enclosed constraint?");
3192
3193   // Remove the braces from around the name.
3194   StringRef RegName(Constraint.data()+1, Constraint.size()-2);
3195
3196   std::pair<unsigned, const TargetRegisterClass*> R =
3197     std::make_pair(0u, static_cast<const TargetRegisterClass*>(nullptr));
3198
3199   // Figure out which register class contains this reg.
3200   for (const TargetRegisterClass *RC : RI->regclasses()) {
3201     // If none of the value types for this register class are valid, we
3202     // can't use it.  For example, 64-bit reg classes on 32-bit targets.
3203     if (!isLegalRC(*RI, *RC))
3204       continue;
3205
3206     for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end();
3207          I != E; ++I) {
3208       if (RegName.equals_lower(RI->getRegAsmName(*I))) {
3209         std::pair<unsigned, const TargetRegisterClass*> S =
3210           std::make_pair(*I, RC);
3211
3212         // If this register class has the requested value type, return it,
3213         // otherwise keep searching and return the first class found
3214         // if no other is found which explicitly has the requested type.
3215         if (RI->isTypeLegalForClass(*RC, VT))
3216           return S;
3217         if (!R.second)
3218           R = S;
3219       }
3220     }
3221   }
3222
3223   return R;
3224 }
3225
3226 //===----------------------------------------------------------------------===//
3227 // Constraint Selection.
3228
3229 /// Return true of this is an input operand that is a matching constraint like
3230 /// "4".
3231 bool TargetLowering::AsmOperandInfo::isMatchingInputConstraint() const {
3232   assert(!ConstraintCode.empty() && "No known constraint!");
3233   return isdigit(static_cast<unsigned char>(ConstraintCode[0]));
3234 }
3235
3236 /// If this is an input matching constraint, this method returns the output
3237 /// operand it matches.
3238 unsigned TargetLowering::AsmOperandInfo::getMatchedOperand() const {
3239   assert(!ConstraintCode.empty() && "No known constraint!");
3240   return atoi(ConstraintCode.c_str());
3241 }
3242
3243 /// Split up the constraint string from the inline assembly value into the
3244 /// specific constraints and their prefixes, and also tie in the associated
3245 /// operand values.
3246 /// If this returns an empty vector, and if the constraint string itself
3247 /// isn't empty, there was an error parsing.
3248 TargetLowering::AsmOperandInfoVector
3249 TargetLowering::ParseConstraints(const DataLayout &DL,
3250                                  const TargetRegisterInfo *TRI,
3251                                  ImmutableCallSite CS) const {
3252   /// Information about all of the constraints.
3253   AsmOperandInfoVector ConstraintOperands;
3254   const InlineAsm *IA = cast<InlineAsm>(CS.getCalledValue());
3255   unsigned maCount = 0; // Largest number of multiple alternative constraints.
3256
3257   // Do a prepass over the constraints, canonicalizing them, and building up the
3258   // ConstraintOperands list.
3259   unsigned ArgNo = 0;   // ArgNo - The argument of the CallInst.
3260   unsigned ResNo = 0;   // ResNo - The result number of the next output.
3261
3262   for (InlineAsm::ConstraintInfo &CI : IA->ParseConstraints()) {
3263     ConstraintOperands.emplace_back(std::move(CI));
3264     AsmOperandInfo &OpInfo = ConstraintOperands.back();
3265
3266     // Update multiple alternative constraint count.
3267     if (OpInfo.multipleAlternatives.size() > maCount)
3268       maCount = OpInfo.multipleAlternatives.size();
3269
3270     OpInfo.ConstraintVT = MVT::Other;
3271
3272     // Compute the value type for each operand.
3273     switch (OpInfo.Type) {
3274     case InlineAsm::isOutput:
3275       // Indirect outputs just consume an argument.
3276       if (OpInfo.isIndirect) {
3277         OpInfo.CallOperandVal = const_cast<Value *>(CS.getArgument(ArgNo++));
3278         break;
3279       }
3280
3281       // The return value of the call is this value.  As such, there is no
3282       // corresponding argument.
3283       assert(!CS.getType()->isVoidTy() &&
3284              "Bad inline asm!");
3285       if (StructType *STy = dyn_cast<StructType>(CS.getType())) {
3286         OpInfo.ConstraintVT =
3287             getSimpleValueType(DL, STy->getElementType(ResNo));
3288       } else {
3289         assert(ResNo == 0 && "Asm only has one result!");
3290         OpInfo.ConstraintVT = getSimpleValueType(DL, CS.getType());
3291       }
3292       ++ResNo;
3293       break;
3294     case InlineAsm::isInput:
3295       OpInfo.CallOperandVal = const_cast<Value *>(CS.getArgument(ArgNo++));
3296       break;
3297     case InlineAsm::isClobber:
3298       // Nothing to do.
3299       break;
3300     }
3301
3302     if (OpInfo.CallOperandVal) {
3303       llvm::Type *OpTy = OpInfo.CallOperandVal->getType();
3304       if (OpInfo.isIndirect) {
3305         llvm::PointerType *PtrTy = dyn_cast<PointerType>(OpTy);
3306         if (!PtrTy)
3307           report_fatal_error("Indirect operand for inline asm not a pointer!");
3308         OpTy = PtrTy->getElementType();
3309       }
3310
3311       // Look for vector wrapped in a struct. e.g. { <16 x i8> }.
3312       if (StructType *STy = dyn_cast<StructType>(OpTy))
3313         if (STy->getNumElements() == 1)
3314           OpTy = STy->getElementType(0);
3315
3316       // If OpTy is not a single value, it may be a struct/union that we
3317       // can tile with integers.
3318       if (!OpTy->isSingleValueType() && OpTy->isSized()) {
3319         unsigned BitSize = DL.getTypeSizeInBits(OpTy);
3320         switch (BitSize) {
3321         default: break;
3322         case 1:
3323         case 8:
3324         case 16:
3325         case 32:
3326         case 64:
3327         case 128:
3328           OpInfo.ConstraintVT =
3329             MVT::getVT(IntegerType::get(OpTy->getContext(), BitSize), true);
3330           break;
3331         }
3332       } else if (PointerType *PT = dyn_cast<PointerType>(OpTy)) {
3333         unsigned PtrSize = DL.getPointerSizeInBits(PT->getAddressSpace());
3334         OpInfo.ConstraintVT = MVT::getIntegerVT(PtrSize);
3335       } else {
3336         OpInfo.ConstraintVT = MVT::getVT(OpTy, true);
3337       }
3338     }
3339   }
3340
3341   // If we have multiple alternative constraints, select the best alternative.
3342   if (!ConstraintOperands.empty()) {
3343     if (maCount) {
3344       unsigned bestMAIndex = 0;
3345       int bestWeight = -1;
3346       // weight:  -1 = invalid match, and 0 = so-so match to 5 = good match.
3347       int weight = -1;
3348       unsigned maIndex;
3349       // Compute the sums of the weights for each alternative, keeping track
3350       // of the best (highest weight) one so far.
3351       for (maIndex = 0; maIndex < maCount; ++maIndex) {
3352         int weightSum = 0;
3353         for (unsigned cIndex = 0, eIndex = ConstraintOperands.size();
3354             cIndex != eIndex; ++cIndex) {
3355           AsmOperandInfo& OpInfo = ConstraintOperands[cIndex];
3356           if (OpInfo.Type == InlineAsm::isClobber)
3357             continue;
3358
3359           // If this is an output operand with a matching input operand,
3360           // look up the matching input. If their types mismatch, e.g. one
3361           // is an integer, the other is floating point, or their sizes are
3362           // different, flag it as an maCantMatch.
3363           if (OpInfo.hasMatchingInput()) {
3364             AsmOperandInfo &Input = ConstraintOperands[OpInfo.MatchingInput];
3365             if (OpInfo.ConstraintVT != Input.ConstraintVT) {
3366               if ((OpInfo.ConstraintVT.isInteger() !=
3367                    Input.ConstraintVT.isInteger()) ||
3368                   (OpInfo.ConstraintVT.getSizeInBits() !=
3369                    Input.ConstraintVT.getSizeInBits())) {
3370                 weightSum = -1;  // Can't match.
3371                 break;
3372               }
3373             }
3374           }
3375           weight = getMultipleConstraintMatchWeight(OpInfo, maIndex);
3376           if (weight == -1) {
3377             weightSum = -1;
3378             break;
3379           }
3380           weightSum += weight;
3381         }
3382         // Update best.
3383         if (weightSum > bestWeight) {
3384           bestWeight = weightSum;
3385           bestMAIndex = maIndex;
3386         }
3387       }
3388
3389       // Now select chosen alternative in each constraint.
3390       for (unsigned cIndex = 0, eIndex = ConstraintOperands.size();
3391           cIndex != eIndex; ++cIndex) {
3392         AsmOperandInfo& cInfo = ConstraintOperands[cIndex];
3393         if (cInfo.Type == InlineAsm::isClobber)
3394           continue;
3395         cInfo.selectAlternative(bestMAIndex);
3396       }
3397     }
3398   }
3399
3400   // Check and hook up tied operands, choose constraint code to use.
3401   for (unsigned cIndex = 0, eIndex = ConstraintOperands.size();
3402       cIndex != eIndex; ++cIndex) {
3403     AsmOperandInfo& OpInfo = ConstraintOperands[cIndex];
3404
3405     // If this is an output operand with a matching input operand, look up the
3406     // matching input. If their types mismatch, e.g. one is an integer, the
3407     // other is floating point, or their sizes are different, flag it as an
3408     // error.
3409     if (OpInfo.hasMatchingInput()) {
3410       AsmOperandInfo &Input = ConstraintOperands[OpInfo.MatchingInput];
3411
3412       if (OpInfo.ConstraintVT != Input.ConstraintVT) {
3413         std::pair<unsigned, const TargetRegisterClass *> MatchRC =
3414             getRegForInlineAsmConstraint(TRI, OpInfo.ConstraintCode,
3415                                          OpInfo.ConstraintVT);
3416         std::pair<unsigned, const TargetRegisterClass *> InputRC =
3417             getRegForInlineAsmConstraint(TRI, Input.ConstraintCode,
3418                                          Input.ConstraintVT);
3419         if ((OpInfo.ConstraintVT.isInteger() !=
3420              Input.ConstraintVT.isInteger()) ||
3421             (MatchRC.second != InputRC.second)) {
3422           report_fatal_error("Unsupported asm: input constraint"
3423                              " with a matching output constraint of"
3424                              " incompatible type!");
3425         }
3426       }
3427     }
3428   }
3429
3430   return ConstraintOperands;
3431 }
3432
3433 /// Return an integer indicating how general CT is.
3434 static unsigned getConstraintGenerality(TargetLowering::ConstraintType CT) {
3435   switch (CT) {
3436   case TargetLowering::C_Other:
3437   case TargetLowering::C_Unknown:
3438     return 0;
3439   case TargetLowering::C_Register:
3440     return 1;
3441   case TargetLowering::C_RegisterClass:
3442     return 2;
3443   case TargetLowering::C_Memory:
3444     return 3;
3445   }
3446   llvm_unreachable("Invalid constraint type");
3447 }
3448
3449 /// Examine constraint type and operand type and determine a weight value.
3450 /// This object must already have been set up with the operand type
3451 /// and the current alternative constraint selected.
3452 TargetLowering::ConstraintWeight
3453   TargetLowering::getMultipleConstraintMatchWeight(
3454     AsmOperandInfo &info, int maIndex) const {
3455   InlineAsm::ConstraintCodeVector *rCodes;
3456   if (maIndex >= (int)info.multipleAlternatives.size())
3457     rCodes = &info.Codes;
3458   else
3459     rCodes = &info.multipleAlternatives[maIndex].Codes;
3460   ConstraintWeight BestWeight = CW_Invalid;
3461
3462   // Loop over the options, keeping track of the most general one.
3463   for (unsigned i = 0, e = rCodes->size(); i != e; ++i) {
3464     ConstraintWeight weight =
3465       getSingleConstraintMatchWeight(info, (*rCodes)[i].c_str());
3466     if (weight > BestWeight)
3467       BestWeight = weight;
3468   }
3469
3470   return BestWeight;
3471 }
3472
3473 /// Examine constraint type and operand type and determine a weight value.
3474 /// This object must already have been set up with the operand type
3475 /// and the current alternative constraint selected.
3476 TargetLowering::ConstraintWeight
3477   TargetLowering::getSingleConstraintMatchWeight(
3478     AsmOperandInfo &info, const char *constraint) const {
3479   ConstraintWeight weight = CW_Invalid;
3480   Value *CallOperandVal = info.CallOperandVal;
3481     // If we don't have a value, we can't do a match,
3482     // but allow it at the lowest weight.
3483   if (!CallOperandVal)
3484     return CW_Default;
3485   // Look at the constraint type.
3486   switch (*constraint) {
3487     case 'i': // immediate integer.
3488     case 'n': // immediate integer with a known value.
3489       if (isa<ConstantInt>(CallOperandVal))
3490         weight = CW_Constant;
3491       break;
3492     case 's': // non-explicit intregal immediate.
3493       if (isa<GlobalValue>(CallOperandVal))
3494         weight = CW_Constant;
3495       break;
3496     case 'E': // immediate float if host format.
3497     case 'F': // immediate float.
3498       if (isa<ConstantFP>(CallOperandVal))
3499         weight = CW_Constant;
3500       break;
3501     case '<': // memory operand with autodecrement.
3502     case '>': // memory operand with autoincrement.
3503     case 'm': // memory operand.
3504     case 'o': // offsettable memory operand
3505     case 'V': // non-offsettable memory operand
3506       weight = CW_Memory;
3507       break;
3508     case 'r': // general register.
3509     case 'g': // general register, memory operand or immediate integer.
3510               // note: Clang converts "g" to "imr".
3511       if (CallOperandVal->getType()->isIntegerTy())
3512         weight = CW_Register;
3513       break;
3514     case 'X': // any operand.
3515     default:
3516       weight = CW_Default;
3517       break;
3518   }
3519   return weight;
3520 }
3521
3522 /// If there are multiple different constraints that we could pick for this
3523 /// operand (e.g. "imr") try to pick the 'best' one.
3524 /// This is somewhat tricky: constraints fall into four classes:
3525 ///    Other         -> immediates and magic values
3526 ///    Register      -> one specific register
3527 ///    RegisterClass -> a group of regs
3528 ///    Memory        -> memory
3529 /// Ideally, we would pick the most specific constraint possible: if we have
3530 /// something that fits into a register, we would pick it.  The problem here
3531 /// is that if we have something that could either be in a register or in
3532 /// memory that use of the register could cause selection of *other*
3533 /// operands to fail: they might only succeed if we pick memory.  Because of
3534 /// this the heuristic we use is:
3535 ///
3536 ///  1) If there is an 'other' constraint, and if the operand is valid for
3537 ///     that constraint, use it.  This makes us take advantage of 'i'
3538 ///     constraints when available.
3539 ///  2) Otherwise, pick the most general constraint present.  This prefers
3540 ///     'm' over 'r', for example.
3541 ///
3542 static void ChooseConstraint(TargetLowering::AsmOperandInfo &OpInfo,
3543                              const TargetLowering &TLI,
3544                              SDValue Op, SelectionDAG *DAG) {
3545   assert(OpInfo.Codes.size() > 1 && "Doesn't have multiple constraint options");
3546   unsigned BestIdx = 0;
3547   TargetLowering::ConstraintType BestType = TargetLowering::C_Unknown;
3548   int BestGenerality = -1;
3549
3550   // Loop over the options, keeping track of the most general one.
3551   for (unsigned i = 0, e = OpInfo.Codes.size(); i != e; ++i) {
3552     TargetLowering::ConstraintType CType =
3553       TLI.getConstraintType(OpInfo.Codes[i]);
3554
3555     // If this is an 'other' constraint, see if the operand is valid for it.
3556     // For example, on X86 we might have an 'rI' constraint.  If the operand
3557     // is an integer in the range [0..31] we want to use I (saving a load
3558     // of a register), otherwise we must use 'r'.
3559     if (CType == TargetLowering::C_Other && Op.getNode()) {
3560       assert(OpInfo.Codes[i].size() == 1 &&
3561              "Unhandled multi-letter 'other' constraint");
3562       std::vector<SDValue> ResultOps;
3563       TLI.LowerAsmOperandForConstraint(Op, OpInfo.Codes[i],
3564                                        ResultOps, *DAG);
3565       if (!ResultOps.empty()) {
3566         BestType = CType;
3567         BestIdx = i;
3568         break;
3569       }
3570     }
3571
3572     // Things with matching constraints can only be registers, per gcc
3573     // documentation.  This mainly affects "g" constraints.
3574     if (CType == TargetLowering::C_Memory && OpInfo.hasMatchingInput())
3575       continue;
3576
3577     // This constraint letter is more general than the previous one, use it.
3578     int Generality = getConstraintGenerality(CType);
3579     if (Generality > BestGenerality) {
3580       BestType = CType;
3581       BestIdx = i;
3582       BestGenerality = Generality;
3583     }
3584   }
3585
3586   OpInfo.ConstraintCode = OpInfo.Codes[BestIdx];
3587   OpInfo.ConstraintType = BestType;
3588 }
3589
3590 /// Determines the constraint code and constraint type to use for the specific
3591 /// AsmOperandInfo, setting OpInfo.ConstraintCode and OpInfo.ConstraintType.
3592 void TargetLowering::ComputeConstraintToUse(AsmOperandInfo &OpInfo,
3593                                             SDValue Op,
3594                                             SelectionDAG *DAG) const {
3595   assert(!OpInfo.Codes.empty() && "Must have at least one constraint");
3596
3597   // Single-letter constraints ('r') are very common.
3598   if (OpInfo.Codes.size() == 1) {
3599     OpInfo.ConstraintCode = OpInfo.Codes[0];
3600     OpInfo.ConstraintType = getConstraintType(OpInfo.ConstraintCode);
3601   } else {
3602     ChooseConstraint(OpInfo, *this, Op, DAG);
3603   }
3604
3605   // 'X' matches anything.
3606   if (OpInfo.ConstraintCode == "X" && OpInfo.CallOperandVal) {
3607     // Labels and constants are handled elsewhere ('X' is the only thing
3608     // that matches labels).  For Functions, the type here is the type of
3609     // the result, which is not what we want to look at; leave them alone.
3610     Value *v = OpInfo.CallOperandVal;
3611     if (isa<BasicBlock>(v) || isa<ConstantInt>(v) || isa<Function>(v)) {
3612       OpInfo.CallOperandVal = v;
3613       return;
3614     }
3615
3616     // Otherwise, try to resolve it to something we know about by looking at
3617     // the actual operand type.
3618     if (const char *Repl = LowerXConstraint(OpInfo.ConstraintVT)) {
3619       OpInfo.ConstraintCode = Repl;
3620       OpInfo.ConstraintType = getConstraintType(OpInfo.ConstraintCode);
3621     }
3622   }
3623 }
3624
3625 /// Given an exact SDIV by a constant, create a multiplication
3626 /// with the multiplicative inverse of the constant.
3627 static SDValue BuildExactSDIV(const TargetLowering &TLI, SDNode *N,
3628                               const SDLoc &dl, SelectionDAG &DAG,
3629                               SmallVectorImpl<SDNode *> &Created) {
3630   SDValue Op0 = N->getOperand(0);
3631   SDValue Op1 = N->getOperand(1);
3632   EVT VT = N->getValueType(0);
3633   EVT SVT = VT.getScalarType();
3634   EVT ShVT = TLI.getShiftAmountTy(VT, DAG.getDataLayout());
3635   EVT ShSVT = ShVT.getScalarType();
3636
3637   bool UseSRA = false;
3638   SmallVector<SDValue, 16> Shifts, Factors;
3639
3640   auto BuildSDIVPattern = [&](ConstantSDNode *C) {
3641     if (C->isNullValue())
3642       return false;
3643     APInt Divisor = C->getAPIntValue();
3644     unsigned Shift = Divisor.countTrailingZeros();
3645     if (Shift) {
3646       Divisor.ashrInPlace(Shift);
3647       UseSRA = true;
3648     }
3649     // Calculate the multiplicative inverse, using Newton's method.
3650     APInt t;
3651     APInt Factor = Divisor;
3652     while ((t = Divisor * Factor) != 1)
3653       Factor *= APInt(Divisor.getBitWidth(), 2) - t;
3654     Shifts.push_back(DAG.getConstant(Shift, dl, ShSVT));
3655     Factors.push_back(DAG.getConstant(Factor, dl, SVT));
3656     return true;
3657   };
3658
3659   // Collect all magic values from the build vector.
3660   if (!ISD::matchUnaryPredicate(Op1, BuildSDIVPattern))
3661     return SDValue();
3662
3663   SDValue Shift, Factor;
3664   if (VT.isVector()) {
3665     Shift = DAG.getBuildVector(ShVT, dl, Shifts);
3666     Factor = DAG.getBuildVector(VT, dl, Factors);
3667   } else {
3668     Shift = Shifts[0];
3669     Factor = Factors[0];
3670   }
3671
3672   SDValue Res = Op0;
3673
3674   // Shift the value upfront if it is even, so the LSB is one.
3675   if (UseSRA) {
3676     // TODO: For UDIV use SRL instead of SRA.
3677     SDNodeFlags Flags;
3678     Flags.setExact(true);
3679     Res = DAG.getNode(ISD::SRA, dl, VT, Res, Shift, Flags);
3680     Created.push_back(Res.getNode());
3681   }
3682
3683   return DAG.getNode(ISD::MUL, dl, VT, Res, Factor);
3684 }
3685
3686 SDValue TargetLowering::BuildSDIVPow2(SDNode *N, const APInt &Divisor,
3687                                      SelectionDAG &DAG,
3688                                      SmallVectorImpl<SDNode *> &Created) const {
3689   AttributeList Attr = DAG.getMachineFunction().getFunction().getAttributes();
3690   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3691   if (TLI.isIntDivCheap(N->getValueType(0), Attr))
3692     return SDValue(N,0); // Lower SDIV as SDIV
3693   return SDValue();
3694 }
3695
3696 /// Given an ISD::SDIV node expressing a divide by constant,
3697 /// return a DAG expression to select that will generate the same value by
3698 /// multiplying by a magic number.
3699 /// Ref: "Hacker's Delight" or "The PowerPC Compiler Writer's Guide".
3700 SDValue TargetLowering::BuildSDIV(SDNode *N, SelectionDAG &DAG,
3701                                   bool IsAfterLegalization,
3702                                   SmallVectorImpl<SDNode *> &Created) const {
3703   SDLoc dl(N);
3704   EVT VT = N->getValueType(0);
3705   EVT SVT = VT.getScalarType();
3706   EVT ShVT = getShiftAmountTy(VT, DAG.getDataLayout());
3707   EVT ShSVT = ShVT.getScalarType();
3708   unsigned EltBits = VT.getScalarSizeInBits();
3709
3710   // Check to see if we can do this.
3711   // FIXME: We should be more aggressive here.
3712   if (!isTypeLegal(VT))
3713     return SDValue();
3714
3715   // If the sdiv has an 'exact' bit we can use a simpler lowering.
3716   if (N->getFlags().hasExact())
3717     return BuildExactSDIV(*this, N, dl, DAG, Created);
3718
3719   SmallVector<SDValue, 16> MagicFactors, Factors, Shifts, ShiftMasks;
3720
3721   auto BuildSDIVPattern = [&](ConstantSDNode *C) {
3722     if (C->isNullValue())
3723       return false;
3724
3725     const APInt &Divisor = C->getAPIntValue();
3726     APInt::ms magics = Divisor.magic();
3727     int NumeratorFactor = 0;
3728     int ShiftMask = -1;
3729
3730     if (Divisor.isOneValue() || Divisor.isAllOnesValue()) {
3731       // If d is +1/-1, we just multiply the numerator by +1/-1.
3732       NumeratorFactor = Divisor.getSExtValue();
3733       magics.m = 0;
3734       magics.s = 0;
3735       ShiftMask = 0;
3736     } else if (Divisor.isStrictlyPositive() && magics.m.isNegative()) {
3737       // If d > 0 and m < 0, add the numerator.
3738       NumeratorFactor = 1;
3739     } else if (Divisor.isNegative() && magics.m.isStrictlyPositive()) {
3740       // If d < 0 and m > 0, subtract the numerator.
3741       NumeratorFactor = -1;
3742     }
3743
3744     MagicFactors.push_back(DAG.getConstant(magics.m, dl, SVT));
3745     Factors.push_back(DAG.getConstant(NumeratorFactor, dl, SVT));
3746     Shifts.push_back(DAG.getConstant(magics.s, dl, ShSVT));
3747     ShiftMasks.push_back(DAG.getConstant(ShiftMask, dl, SVT));
3748     return true;
3749   };
3750
3751   SDValue N0 = N->getOperand(0);
3752   SDValue N1 = N->getOperand(1);
3753
3754   // Collect the shifts / magic values from each element.
3755   if (!ISD::matchUnaryPredicate(N1, BuildSDIVPattern))
3756     return SDValue();
3757
3758   SDValue MagicFactor, Factor, Shift, ShiftMask;
3759   if (VT.isVector()) {
3760     MagicFactor = DAG.getBuildVector(VT, dl, MagicFactors);
3761     Factor = DAG.getBuildVector(VT, dl, Factors);
3762     Shift = DAG.getBuildVector(ShVT, dl, Shifts);
3763     ShiftMask = DAG.getBuildVector(VT, dl, ShiftMasks);
3764   } else {
3765     MagicFactor = MagicFactors[0];
3766     Factor = Factors[0];
3767     Shift = Shifts[0];
3768     ShiftMask = ShiftMasks[0];
3769   }
3770
3771   // Multiply the numerator (operand 0) by the magic value.
3772   // FIXME: We should support doing a MUL in a wider type.
3773   SDValue Q;
3774   if (IsAfterLegalization ? isOperationLegal(ISD::MULHS, VT)
3775                           : isOperationLegalOrCustom(ISD::MULHS, VT))
3776     Q = DAG.getNode(ISD::MULHS, dl, VT, N0, MagicFactor);
3777   else if (IsAfterLegalization ? isOperationLegal(ISD::SMUL_LOHI, VT)
3778                                : isOperationLegalOrCustom(ISD::SMUL_LOHI, VT)) {
3779     SDValue LoHi =
3780         DAG.getNode(ISD::SMUL_LOHI, dl, DAG.getVTList(VT, VT), N0, MagicFactor);
3781     Q = SDValue(LoHi.getNode(), 1);
3782   } else
3783     return SDValue(); // No mulhs or equivalent.
3784   Created.push_back(Q.getNode());
3785
3786   // (Optionally) Add/subtract the numerator using Factor.
3787   Factor = DAG.getNode(ISD::MUL, dl, VT, N0, Factor);
3788   Created.push_back(Factor.getNode());
3789   Q = DAG.getNode(ISD::ADD, dl, VT, Q, Factor);
3790   Created.push_back(Q.getNode());
3791
3792   // Shift right algebraic by shift value.
3793   Q = DAG.getNode(ISD::SRA, dl, VT, Q, Shift);
3794   Created.push_back(Q.getNode());
3795
3796   // Extract the sign bit, mask it and add it to the quotient.
3797   SDValue SignShift = DAG.getConstant(EltBits - 1, dl, ShVT);
3798   SDValue T = DAG.getNode(ISD::SRL, dl, VT, Q, SignShift);
3799   Created.push_back(T.getNode());
3800   T = DAG.getNode(ISD::AND, dl, VT, T, ShiftMask);
3801   Created.push_back(T.getNode());
3802   return DAG.getNode(ISD::ADD, dl, VT, Q, T);
3803 }
3804
3805 /// Given an ISD::UDIV node expressing a divide by constant,
3806 /// return a DAG expression to select that will generate the same value by
3807 /// multiplying by a magic number.
3808 /// Ref: "Hacker's Delight" or "The PowerPC Compiler Writer's Guide".
3809 SDValue TargetLowering::BuildUDIV(SDNode *N, SelectionDAG &DAG,
3810                                   bool IsAfterLegalization,
3811                                   SmallVectorImpl<SDNode *> &Created) const {
3812   SDLoc dl(N);
3813   EVT VT = N->getValueType(0);
3814   EVT SVT = VT.getScalarType();
3815   EVT ShVT = getShiftAmountTy(VT, DAG.getDataLayout());
3816   EVT ShSVT = ShVT.getScalarType();
3817   unsigned EltBits = VT.getScalarSizeInBits();
3818
3819   // Check to see if we can do this.
3820   // FIXME: We should be more aggressive here.
3821   if (!isTypeLegal(VT))
3822     return SDValue();
3823
3824   bool UseNPQ = false;
3825   SmallVector<SDValue, 16> PreShifts, PostShifts, MagicFactors, NPQFactors;
3826
3827   auto BuildUDIVPattern = [&](ConstantSDNode *C) {
3828     if (C->isNullValue())
3829       return false;
3830     // FIXME: We should use a narrower constant when the upper
3831     // bits are known to be zero.
3832     APInt Divisor = C->getAPIntValue();
3833     APInt::mu magics = Divisor.magicu();
3834     unsigned PreShift = 0, PostShift = 0;
3835
3836     // If the divisor is even, we can avoid using the expensive fixup by
3837     // shifting the divided value upfront.
3838     if (magics.a != 0 && !Divisor[0]) {
3839       PreShift = Divisor.countTrailingZeros();
3840       // Get magic number for the shifted divisor.
3841       magics = Divisor.lshr(PreShift).magicu(PreShift);
3842       assert(magics.a == 0 && "Should use cheap fixup now");
3843     }
3844
3845     APInt Magic = magics.m;
3846
3847     unsigned SelNPQ;
3848     if (magics.a == 0 || Divisor.isOneValue()) {
3849       assert(magics.s < Divisor.getBitWidth() &&
3850              "We shouldn't generate an undefined shift!");
3851       PostShift = magics.s;
3852       SelNPQ = false;
3853     } else {
3854       PostShift = magics.s - 1;
3855       SelNPQ = true;
3856     }
3857
3858     PreShifts.push_back(DAG.getConstant(PreShift, dl, ShSVT));
3859     MagicFactors.push_back(DAG.getConstant(Magic, dl, SVT));
3860     NPQFactors.push_back(
3861         DAG.getConstant(SelNPQ ? APInt::getOneBitSet(EltBits, EltBits - 1)
3862                                : APInt::getNullValue(EltBits),
3863                         dl, SVT));
3864     PostShifts.push_back(DAG.getConstant(PostShift, dl, ShSVT));
3865     UseNPQ |= SelNPQ;
3866     return true;
3867   };
3868
3869   SDValue N0 = N->getOperand(0);
3870   SDValue N1 = N->getOperand(1);
3871
3872   // Collect the shifts/magic values from each element.
3873   if (!ISD::matchUnaryPredicate(N1, BuildUDIVPattern))
3874     return SDValue();
3875
3876   SDValue PreShift, PostShift, MagicFactor, NPQFactor;
3877   if (VT.isVector()) {
3878     PreShift = DAG.getBuildVector(ShVT, dl, PreShifts);
3879     MagicFactor = DAG.getBuildVector(VT, dl, MagicFactors);
3880     NPQFactor = DAG.getBuildVector(VT, dl, NPQFactors);
3881     PostShift = DAG.getBuildVector(ShVT, dl, PostShifts);
3882   } else {
3883     PreShift = PreShifts[0];
3884     MagicFactor = MagicFactors[0];
3885     PostShift = PostShifts[0];
3886   }
3887
3888   SDValue Q = N0;
3889   Q = DAG.getNode(ISD::SRL, dl, VT, Q, PreShift);
3890   Created.push_back(Q.getNode());
3891
3892   // FIXME: We should support doing a MUL in a wider type.
3893   auto GetMULHU = [&](SDValue X, SDValue Y) {
3894     if (IsAfterLegalization ? isOperationLegal(ISD::MULHU, VT)
3895                             : isOperationLegalOrCustom(ISD::MULHU, VT))
3896       return DAG.getNode(ISD::MULHU, dl, VT, X, Y);
3897     if (IsAfterLegalization ? isOperationLegal(ISD::UMUL_LOHI, VT)
3898                             : isOperationLegalOrCustom(ISD::UMUL_LOHI, VT)) {
3899       SDValue LoHi =
3900           DAG.getNode(ISD::UMUL_LOHI, dl, DAG.getVTList(VT, VT), X, Y);
3901       return SDValue(LoHi.getNode(), 1);
3902     }
3903     return SDValue(); // No mulhu or equivalent
3904   };
3905
3906   // Multiply the numerator (operand 0) by the magic value.
3907   Q = GetMULHU(Q, MagicFactor);
3908   if (!Q)
3909     return SDValue();
3910
3911   Created.push_back(Q.getNode());
3912
3913   if (UseNPQ) {
3914     SDValue NPQ = DAG.getNode(ISD::SUB, dl, VT, N0, Q);
3915     Created.push_back(NPQ.getNode());
3916
3917     // For vectors we might have a mix of non-NPQ/NPQ paths, so use
3918     // MULHU to act as a SRL-by-1 for NPQ, else multiply by zero.
3919     if (VT.isVector())
3920       NPQ = GetMULHU(NPQ, NPQFactor);
3921     else
3922       NPQ = DAG.getNode(ISD::SRL, dl, VT, NPQ, DAG.getConstant(1, dl, ShVT));
3923
3924     Created.push_back(NPQ.getNode());
3925
3926     Q = DAG.getNode(ISD::ADD, dl, VT, NPQ, Q);
3927     Created.push_back(Q.getNode());
3928   }
3929
3930   Q = DAG.getNode(ISD::SRL, dl, VT, Q, PostShift);
3931   Created.push_back(Q.getNode());
3932
3933   SDValue One = DAG.getConstant(1, dl, VT);
3934   SDValue IsOne = DAG.getSetCC(dl, VT, N1, One, ISD::SETEQ);
3935   return DAG.getSelect(dl, VT, IsOne, N0, Q);
3936 }
3937
3938 bool TargetLowering::
3939 verifyReturnAddressArgumentIsConstant(SDValue Op, SelectionDAG &DAG) const {
3940   if (!isa<ConstantSDNode>(Op.getOperand(0))) {
3941     DAG.getContext()->emitError("argument to '__builtin_return_address' must "
3942                                 "be a constant integer");
3943     return true;
3944   }
3945
3946   return false;
3947 }
3948
3949 //===----------------------------------------------------------------------===//
3950 // Legalization Utilities
3951 //===----------------------------------------------------------------------===//
3952
3953 bool TargetLowering::expandMUL_LOHI(unsigned Opcode, EVT VT, SDLoc dl,
3954                                     SDValue LHS, SDValue RHS,
3955                                     SmallVectorImpl<SDValue> &Result,
3956                                     EVT HiLoVT, SelectionDAG &DAG,
3957                                     MulExpansionKind Kind, SDValue LL,
3958                                     SDValue LH, SDValue RL, SDValue RH) const {
3959   assert(Opcode == ISD::MUL || Opcode == ISD::UMUL_LOHI ||
3960          Opcode == ISD::SMUL_LOHI);
3961
3962   bool HasMULHS = (Kind == MulExpansionKind::Always) ||
3963                   isOperationLegalOrCustom(ISD::MULHS, HiLoVT);
3964   bool HasMULHU = (Kind == MulExpansionKind::Always) ||
3965                   isOperationLegalOrCustom(ISD::MULHU, HiLoVT);
3966   bool HasSMUL_LOHI = (Kind == MulExpansionKind::Always) ||
3967                       isOperationLegalOrCustom(ISD::SMUL_LOHI, HiLoVT);
3968   bool HasUMUL_LOHI = (Kind == MulExpansionKind::Always) ||
3969                       isOperationLegalOrCustom(ISD::UMUL_LOHI, HiLoVT);
3970
3971   if (!HasMULHU && !HasMULHS && !HasUMUL_LOHI && !HasSMUL_LOHI)
3972     return false;
3973
3974   unsigned OuterBitSize = VT.getScalarSizeInBits();
3975   unsigned InnerBitSize = HiLoVT.getScalarSizeInBits();
3976   unsigned LHSSB = DAG.ComputeNumSignBits(LHS);
3977   unsigned RHSSB = DAG.ComputeNumSignBits(RHS);
3978
3979   // LL, LH, RL, and RH must be either all NULL or all set to a value.
3980   assert((LL.getNode() && LH.getNode() && RL.getNode() && RH.getNode()) ||
3981          (!LL.getNode() && !LH.getNode() && !RL.getNode() && !RH.getNode()));
3982
3983   SDVTList VTs = DAG.getVTList(HiLoVT, HiLoVT);
3984   auto MakeMUL_LOHI = [&](SDValue L, SDValue R, SDValue &Lo, SDValue &Hi,
3985                           bool Signed) -> bool {
3986     if ((Signed && HasSMUL_LOHI) || (!Signed && HasUMUL_LOHI)) {
3987       Lo = DAG.getNode(Signed ? ISD::SMUL_LOHI : ISD::UMUL_LOHI, dl, VTs, L, R);
3988       Hi = SDValue(Lo.getNode(), 1);
3989       return true;
3990     }
3991     if ((Signed && HasMULHS) || (!Signed && HasMULHU)) {
3992       Lo = DAG.getNode(ISD::MUL, dl, HiLoVT, L, R);
3993       Hi = DAG.getNode(Signed ? ISD::MULHS : ISD::MULHU, dl, HiLoVT, L, R);
3994       return true;
3995     }
3996     return false;
3997   };
3998
3999   SDValue Lo, Hi;
4000
4001   if (!LL.getNode() && !RL.getNode() &&
4002       isOperationLegalOrCustom(ISD::TRUNCATE, HiLoVT)) {
4003     LL = DAG.getNode(ISD::TRUNCATE, dl, HiLoVT, LHS);
4004     RL = DAG.getNode(ISD::TRUNCATE, dl, HiLoVT, RHS);
4005   }
4006
4007   if (!LL.getNode())
4008     return false;
4009
4010   APInt HighMask = APInt::getHighBitsSet(OuterBitSize, InnerBitSize);
4011   if (DAG.MaskedValueIsZero(LHS, HighMask) &&
4012       DAG.MaskedValueIsZero(RHS, HighMask)) {
4013     // The inputs are both zero-extended.
4014     if (MakeMUL_LOHI(LL, RL, Lo, Hi, false)) {
4015       Result.push_back(Lo);
4016       Result.push_back(Hi);
4017       if (Opcode != ISD::MUL) {
4018         SDValue Zero = DAG.getConstant(0, dl, HiLoVT);
4019         Result.push_back(Zero);
4020         Result.push_back(Zero);
4021       }
4022       return true;
4023     }
4024   }
4025
4026   if (!VT.isVector() && Opcode == ISD::MUL && LHSSB > InnerBitSize &&
4027       RHSSB > InnerBitSize) {
4028     // The input values are both sign-extended.
4029     // TODO non-MUL case?
4030     if (MakeMUL_LOHI(LL, RL, Lo, Hi, true)) {
4031       Result.push_back(Lo);
4032       Result.push_back(Hi);
4033       return true;
4034     }
4035   }
4036
4037   unsigned ShiftAmount = OuterBitSize - InnerBitSize;
4038   EVT ShiftAmountTy = getShiftAmountTy(VT, DAG.getDataLayout());
4039   if (APInt::getMaxValue(ShiftAmountTy.getSizeInBits()).ult(ShiftAmount)) {
4040     // FIXME getShiftAmountTy does not always return a sensible result when VT
4041     // is an illegal type, and so the type may be too small to fit the shift
4042     // amount. Override it with i32. The shift will have to be legalized.
4043     ShiftAmountTy = MVT::i32;
4044   }
4045   SDValue Shift = DAG.getConstant(ShiftAmount, dl, ShiftAmountTy);
4046
4047   if (!LH.getNode() && !RH.getNode() &&
4048       isOperationLegalOrCustom(ISD::SRL, VT) &&
4049       isOperationLegalOrCustom(ISD::TRUNCATE, HiLoVT)) {
4050     LH = DAG.getNode(ISD::SRL, dl, VT, LHS, Shift);
4051     LH = DAG.getNode(ISD::TRUNCATE, dl, HiLoVT, LH);
4052     RH = DAG.getNode(ISD::SRL, dl, VT, RHS, Shift);
4053     RH = DAG.getNode(ISD::TRUNCATE, dl, HiLoVT, RH);
4054   }
4055
4056   if (!LH.getNode())
4057     return false;
4058
4059   if (!MakeMUL_LOHI(LL, RL, Lo, Hi, false))
4060     return false;
4061
4062   Result.push_back(Lo);
4063
4064   if (Opcode == ISD::MUL) {
4065     RH = DAG.getNode(ISD::MUL, dl, HiLoVT, LL, RH);
4066     LH = DAG.getNode(ISD::MUL, dl, HiLoVT, LH, RL);
4067     Hi = DAG.getNode(ISD::ADD, dl, HiLoVT, Hi, RH);
4068     Hi = DAG.getNode(ISD::ADD, dl, HiLoVT, Hi, LH);
4069     Result.push_back(Hi);
4070     return true;
4071   }
4072
4073   // Compute the full width result.
4074   auto Merge = [&](SDValue Lo, SDValue Hi) -> SDValue {
4075     Lo = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Lo);
4076     Hi = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Hi);
4077     Hi = DAG.getNode(ISD::SHL, dl, VT, Hi, Shift);
4078     return DAG.getNode(ISD::OR, dl, VT, Lo, Hi);
4079   };
4080
4081   SDValue Next = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Hi);
4082   if (!MakeMUL_LOHI(LL, RH, Lo, Hi, false))
4083     return false;
4084
4085   // This is effectively the add part of a multiply-add of half-sized operands,
4086   // so it cannot overflow.
4087   Next = DAG.getNode(ISD::ADD, dl, VT, Next, Merge(Lo, Hi));
4088
4089   if (!MakeMUL_LOHI(LH, RL, Lo, Hi, false))
4090     return false;
4091
4092   SDValue Zero = DAG.getConstant(0, dl, HiLoVT);
4093   EVT BoolType = getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), VT);
4094
4095   bool UseGlue = (isOperationLegalOrCustom(ISD::ADDC, VT) &&
4096                   isOperationLegalOrCustom(ISD::ADDE, VT));
4097   if (UseGlue)
4098     Next = DAG.getNode(ISD::ADDC, dl, DAG.getVTList(VT, MVT::Glue), Next,
4099                        Merge(Lo, Hi));
4100   else
4101     Next = DAG.getNode(ISD::ADDCARRY, dl, DAG.getVTList(VT, BoolType), Next,
4102                        Merge(Lo, Hi), DAG.getConstant(0, dl, BoolType));
4103
4104   SDValue Carry = Next.getValue(1);
4105   Result.push_back(DAG.getNode(ISD::TRUNCATE, dl, HiLoVT, Next));
4106   Next = DAG.getNode(ISD::SRL, dl, VT, Next, Shift);
4107
4108   if (!MakeMUL_LOHI(LH, RH, Lo, Hi, Opcode == ISD::SMUL_LOHI))
4109     return false;
4110
4111   if (UseGlue)
4112     Hi = DAG.getNode(ISD::ADDE, dl, DAG.getVTList(HiLoVT, MVT::Glue), Hi, Zero,
4113                      Carry);
4114   else
4115     Hi = DAG.getNode(ISD::ADDCARRY, dl, DAG.getVTList(HiLoVT, BoolType), Hi,
4116                      Zero, Carry);
4117
4118   Next = DAG.getNode(ISD::ADD, dl, VT, Next, Merge(Lo, Hi));
4119
4120   if (Opcode == ISD::SMUL_LOHI) {
4121     SDValue NextSub = DAG.getNode(ISD::SUB, dl, VT, Next,
4122                                   DAG.getNode(ISD::ZERO_EXTEND, dl, VT, RL));
4123     Next = DAG.getSelectCC(dl, LH, Zero, NextSub, Next, ISD::SETLT);
4124
4125     NextSub = DAG.getNode(ISD::SUB, dl, VT, Next,
4126                           DAG.getNode(ISD::ZERO_EXTEND, dl, VT, LL));
4127     Next = DAG.getSelectCC(dl, RH, Zero, NextSub, Next, ISD::SETLT);
4128   }
4129
4130   Result.push_back(DAG.getNode(ISD::TRUNCATE, dl, HiLoVT, Next));
4131   Next = DAG.getNode(ISD::SRL, dl, VT, Next, Shift);
4132   Result.push_back(DAG.getNode(ISD::TRUNCATE, dl, HiLoVT, Next));
4133   return true;
4134 }
4135
4136 bool TargetLowering::expandMUL(SDNode *N, SDValue &Lo, SDValue &Hi, EVT HiLoVT,
4137                                SelectionDAG &DAG, MulExpansionKind Kind,
4138                                SDValue LL, SDValue LH, SDValue RL,
4139                                SDValue RH) const {
4140   SmallVector<SDValue, 2> Result;
4141   bool Ok = expandMUL_LOHI(N->getOpcode(), N->getValueType(0), N,
4142                            N->getOperand(0), N->getOperand(1), Result, HiLoVT,
4143                            DAG, Kind, LL, LH, RL, RH);
4144   if (Ok) {
4145     assert(Result.size() == 2);
4146     Lo = Result[0];
4147     Hi = Result[1];
4148   }
4149   return Ok;
4150 }
4151
4152 bool TargetLowering::expandFunnelShift(SDNode *Node, SDValue &Result,
4153                                        SelectionDAG &DAG) const {
4154   EVT VT = Node->getValueType(0);
4155
4156   if (VT.isVector() && (!isOperationLegalOrCustom(ISD::SHL, VT) ||
4157                         !isOperationLegalOrCustom(ISD::SRL, VT) ||
4158                         !isOperationLegalOrCustom(ISD::SUB, VT) ||
4159                         !isOperationLegalOrCustomOrPromote(ISD::OR, VT)))
4160     return false;
4161
4162   // fshl: (X << (Z % BW)) | (Y >> (BW - (Z % BW)))
4163   // fshr: (X << (BW - (Z % BW))) | (Y >> (Z % BW))
4164   SDValue X = Node->getOperand(0);
4165   SDValue Y = Node->getOperand(1);
4166   SDValue Z = Node->getOperand(2);
4167
4168   unsigned EltSizeInBits = VT.getScalarSizeInBits();
4169   bool IsFSHL = Node->getOpcode() == ISD::FSHL;
4170   SDLoc DL(SDValue(Node, 0));
4171
4172   EVT ShVT = Z.getValueType();
4173   SDValue BitWidthC = DAG.getConstant(EltSizeInBits, DL, ShVT);
4174   SDValue Zero = DAG.getConstant(0, DL, ShVT);
4175
4176   SDValue ShAmt;
4177   if (isPowerOf2_32(EltSizeInBits)) {
4178     SDValue Mask = DAG.getConstant(EltSizeInBits - 1, DL, ShVT);
4179     ShAmt = DAG.getNode(ISD::AND, DL, ShVT, Z, Mask);
4180   } else {
4181     ShAmt = DAG.getNode(ISD::UREM, DL, ShVT, Z, BitWidthC);
4182   }
4183
4184   SDValue InvShAmt = DAG.getNode(ISD::SUB, DL, ShVT, BitWidthC, ShAmt);
4185   SDValue ShX = DAG.getNode(ISD::SHL, DL, VT, X, IsFSHL ? ShAmt : InvShAmt);
4186   SDValue ShY = DAG.getNode(ISD::SRL, DL, VT, Y, IsFSHL ? InvShAmt : ShAmt);
4187   SDValue Or = DAG.getNode(ISD::OR, DL, VT, ShX, ShY);
4188
4189   // If (Z % BW == 0), then the opposite direction shift is shift-by-bitwidth,
4190   // and that is undefined. We must compare and select to avoid UB.
4191   EVT CCVT = getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), ShVT);
4192
4193   // For fshl, 0-shift returns the 1st arg (X).
4194   // For fshr, 0-shift returns the 2nd arg (Y).
4195   SDValue IsZeroShift = DAG.getSetCC(DL, CCVT, ShAmt, Zero, ISD::SETEQ);
4196   Result = DAG.getSelect(DL, VT, IsZeroShift, IsFSHL ? X : Y, Or);
4197   return true;
4198 }
4199
4200 bool TargetLowering::expandFP_TO_SINT(SDNode *Node, SDValue &Result,
4201                                SelectionDAG &DAG) const {
4202   SDValue Src = Node->getOperand(0);
4203   EVT SrcVT = Src.getValueType();
4204   EVT DstVT = Node->getValueType(0);
4205   SDLoc dl(SDValue(Node, 0));
4206
4207   // FIXME: Only f32 to i64 conversions are supported.
4208   if (SrcVT != MVT::f32 || DstVT != MVT::i64)
4209     return false;
4210
4211   // Expand f32 -> i64 conversion
4212   // This algorithm comes from compiler-rt's implementation of fixsfdi:
4213   // https://github.com/llvm-mirror/compiler-rt/blob/master/lib/builtins/fixsfdi.c
4214   unsigned SrcEltBits = SrcVT.getScalarSizeInBits();
4215   EVT IntVT = SrcVT.changeTypeToInteger();
4216   EVT IntShVT = getShiftAmountTy(IntVT, DAG.getDataLayout());
4217
4218   SDValue ExponentMask = DAG.getConstant(0x7F800000, dl, IntVT);
4219   SDValue ExponentLoBit = DAG.getConstant(23, dl, IntVT);
4220   SDValue Bias = DAG.getConstant(127, dl, IntVT);
4221   SDValue SignMask = DAG.getConstant(APInt::getSignMask(SrcEltBits), dl, IntVT);
4222   SDValue SignLowBit = DAG.getConstant(SrcEltBits - 1, dl, IntVT);
4223   SDValue MantissaMask = DAG.getConstant(0x007FFFFF, dl, IntVT);
4224
4225   SDValue Bits = DAG.getNode(ISD::BITCAST, dl, IntVT, Src);
4226
4227   SDValue ExponentBits = DAG.getNode(
4228       ISD::SRL, dl, IntVT, DAG.getNode(ISD::AND, dl, IntVT, Bits, ExponentMask),
4229       DAG.getZExtOrTrunc(ExponentLoBit, dl, IntShVT));
4230   SDValue Exponent = DAG.getNode(ISD::SUB, dl, IntVT, ExponentBits, Bias);
4231
4232   SDValue Sign = DAG.getNode(ISD::SRA, dl, IntVT,
4233                              DAG.getNode(ISD::AND, dl, IntVT, Bits, SignMask),
4234                              DAG.getZExtOrTrunc(SignLowBit, dl, IntShVT));
4235   Sign = DAG.getSExtOrTrunc(Sign, dl, DstVT);
4236
4237   SDValue R = DAG.getNode(ISD::OR, dl, IntVT,
4238                           DAG.getNode(ISD::AND, dl, IntVT, Bits, MantissaMask),
4239                           DAG.getConstant(0x00800000, dl, IntVT));
4240
4241   R = DAG.getZExtOrTrunc(R, dl, DstVT);
4242
4243   R = DAG.getSelectCC(
4244       dl, Exponent, ExponentLoBit,
4245       DAG.getNode(ISD::SHL, dl, DstVT, R,
4246                   DAG.getZExtOrTrunc(
4247                       DAG.getNode(ISD::SUB, dl, IntVT, Exponent, ExponentLoBit),
4248                       dl, IntShVT)),
4249       DAG.getNode(ISD::SRL, dl, DstVT, R,
4250                   DAG.getZExtOrTrunc(
4251                       DAG.getNode(ISD::SUB, dl, IntVT, ExponentLoBit, Exponent),
4252                       dl, IntShVT)),
4253       ISD::SETGT);
4254
4255   SDValue Ret = DAG.getNode(ISD::SUB, dl, DstVT,
4256                             DAG.getNode(ISD::XOR, dl, DstVT, R, Sign), Sign);
4257
4258   Result = DAG.getSelectCC(dl, Exponent, DAG.getConstant(0, dl, IntVT),
4259                            DAG.getConstant(0, dl, DstVT), Ret, ISD::SETLT);
4260   return true;
4261 }
4262
4263 bool TargetLowering::expandFP_TO_UINT(SDNode *Node, SDValue &Result,
4264                                       SelectionDAG &DAG) const {
4265   SDLoc dl(SDValue(Node, 0));
4266   SDValue Src = Node->getOperand(0);
4267
4268   EVT SrcVT = Src.getValueType();
4269   EVT DstVT = Node->getValueType(0);
4270   EVT SetCCVT =
4271       getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), SrcVT);
4272
4273   // Only expand vector types if we have the appropriate vector bit operations.
4274   if (DstVT.isVector() && (!isOperationLegalOrCustom(ISD::FP_TO_SINT, DstVT) ||
4275                            !isOperationLegalOrCustomOrPromote(ISD::XOR, SrcVT)))
4276     return false;
4277
4278   // If the maximum float value is smaller then the signed integer range,
4279   // the destination signmask can't be represented by the float, so we can
4280   // just use FP_TO_SINT directly.
4281   const fltSemantics &APFSem = DAG.EVTToAPFloatSemantics(SrcVT);
4282   APFloat APF(APFSem, APInt::getNullValue(SrcVT.getScalarSizeInBits()));
4283   APInt SignMask = APInt::getSignMask(DstVT.getScalarSizeInBits());
4284   if (APFloat::opOverflow &
4285       APF.convertFromAPInt(SignMask, false, APFloat::rmNearestTiesToEven)) {
4286     Result = DAG.getNode(ISD::FP_TO_SINT, dl, DstVT, Src);
4287     return true;
4288   }
4289
4290   SDValue Cst = DAG.getConstantFP(APF, dl, SrcVT);
4291   SDValue Sel = DAG.getSetCC(dl, SetCCVT, Src, Cst, ISD::SETLT);
4292
4293   bool Strict = shouldUseStrictFP_TO_INT(SrcVT, DstVT, /*IsSigned*/ false);
4294   if (Strict) {
4295     // Expand based on maximum range of FP_TO_SINT, if the value exceeds the
4296     // signmask then offset (the result of which should be fully representable).
4297     // Sel = Src < 0x8000000000000000
4298     // Val = select Sel, Src, Src - 0x8000000000000000
4299     // Ofs = select Sel, 0, 0x8000000000000000
4300     // Result = fp_to_sint(Val) ^ Ofs
4301
4302     // TODO: Should any fast-math-flags be set for the FSUB?
4303     SDValue Val = DAG.getSelect(dl, SrcVT, Sel, Src,
4304                                 DAG.getNode(ISD::FSUB, dl, SrcVT, Src, Cst));
4305     SDValue Ofs = DAG.getSelect(dl, DstVT, Sel, DAG.getConstant(0, dl, DstVT),
4306                                 DAG.getConstant(SignMask, dl, DstVT));
4307     Result = DAG.getNode(ISD::XOR, dl, DstVT,
4308                          DAG.getNode(ISD::FP_TO_SINT, dl, DstVT, Val), Ofs);
4309   } else {
4310     // Expand based on maximum range of FP_TO_SINT:
4311     // True = fp_to_sint(Src)
4312     // False = 0x8000000000000000 + fp_to_sint(Src - 0x8000000000000000)
4313     // Result = select (Src < 0x8000000000000000), True, False
4314
4315     SDValue True = DAG.getNode(ISD::FP_TO_SINT, dl, DstVT, Src);
4316     // TODO: Should any fast-math-flags be set for the FSUB?
4317     SDValue False = DAG.getNode(ISD::FP_TO_SINT, dl, DstVT,
4318                                 DAG.getNode(ISD::FSUB, dl, SrcVT, Src, Cst));
4319     False = DAG.getNode(ISD::XOR, dl, DstVT, False,
4320                         DAG.getConstant(SignMask, dl, DstVT));
4321     Result = DAG.getSelect(dl, DstVT, Sel, True, False);
4322   }
4323   return true;
4324 }
4325
4326 bool TargetLowering::expandUINT_TO_FP(SDNode *Node, SDValue &Result,
4327                                       SelectionDAG &DAG) const {
4328   SDValue Src = Node->getOperand(0);
4329   EVT SrcVT = Src.getValueType();
4330   EVT DstVT = Node->getValueType(0);
4331
4332   if (SrcVT.getScalarType() != MVT::i64)
4333     return false;
4334
4335   SDLoc dl(SDValue(Node, 0));
4336   EVT ShiftVT = getShiftAmountTy(SrcVT, DAG.getDataLayout());
4337
4338   if (DstVT.getScalarType() == MVT::f32) {
4339     // Only expand vector types if we have the appropriate vector bit
4340     // operations.
4341     if (SrcVT.isVector() &&
4342         (!isOperationLegalOrCustom(ISD::SRL, SrcVT) ||
4343          !isOperationLegalOrCustom(ISD::FADD, DstVT) ||
4344          !isOperationLegalOrCustom(ISD::SINT_TO_FP, SrcVT) ||
4345          !isOperationLegalOrCustomOrPromote(ISD::OR, SrcVT) ||
4346          !isOperationLegalOrCustomOrPromote(ISD::AND, SrcVT)))
4347       return false;
4348
4349     // For unsigned conversions, convert them to signed conversions using the
4350     // algorithm from the x86_64 __floatundidf in compiler_rt.
4351     SDValue Fast = DAG.getNode(ISD::SINT_TO_FP, dl, DstVT, Src);
4352
4353     SDValue ShiftConst = DAG.getConstant(1, dl, ShiftVT);
4354     SDValue Shr = DAG.getNode(ISD::SRL, dl, SrcVT, Src, ShiftConst);
4355     SDValue AndConst = DAG.getConstant(1, dl, SrcVT);
4356     SDValue And = DAG.getNode(ISD::AND, dl, SrcVT, Src, AndConst);
4357     SDValue Or = DAG.getNode(ISD::OR, dl, SrcVT, And, Shr);
4358
4359     SDValue SignCvt = DAG.getNode(ISD::SINT_TO_FP, dl, DstVT, Or);
4360     SDValue Slow = DAG.getNode(ISD::FADD, dl, DstVT, SignCvt, SignCvt);
4361
4362     // TODO: This really should be implemented using a branch rather than a
4363     // select.  We happen to get lucky and machinesink does the right
4364     // thing most of the time.  This would be a good candidate for a
4365     // pseudo-op, or, even better, for whole-function isel.
4366     EVT SetCCVT =
4367         getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), SrcVT);
4368
4369     SDValue SignBitTest = DAG.getSetCC(
4370         dl, SetCCVT, Src, DAG.getConstant(0, dl, SrcVT), ISD::SETLT);
4371     Result = DAG.getSelect(dl, DstVT, SignBitTest, Slow, Fast);
4372     return true;
4373   }
4374
4375   if (DstVT.getScalarType() == MVT::f64) {
4376     // Only expand vector types if we have the appropriate vector bit
4377     // operations.
4378     if (SrcVT.isVector() &&
4379         (!isOperationLegalOrCustom(ISD::SRL, SrcVT) ||
4380          !isOperationLegalOrCustom(ISD::FADD, DstVT) ||
4381          !isOperationLegalOrCustom(ISD::FSUB, DstVT) ||
4382          !isOperationLegalOrCustomOrPromote(ISD::OR, SrcVT) ||
4383          !isOperationLegalOrCustomOrPromote(ISD::AND, SrcVT)))
4384       return false;
4385
4386     // Implementation of unsigned i64 to f64 following the algorithm in
4387     // __floatundidf in compiler_rt. This implementation has the advantage
4388     // of performing rounding correctly, both in the default rounding mode
4389     // and in all alternate rounding modes.
4390     SDValue TwoP52 = DAG.getConstant(UINT64_C(0x4330000000000000), dl, SrcVT);
4391     SDValue TwoP84PlusTwoP52 = DAG.getConstantFP(
4392         BitsToDouble(UINT64_C(0x4530000000100000)), dl, DstVT);
4393     SDValue TwoP84 = DAG.getConstant(UINT64_C(0x4530000000000000), dl, SrcVT);
4394     SDValue LoMask = DAG.getConstant(UINT64_C(0x00000000FFFFFFFF), dl, SrcVT);
4395     SDValue HiShift = DAG.getConstant(32, dl, ShiftVT);
4396
4397     SDValue Lo = DAG.getNode(ISD::AND, dl, SrcVT, Src, LoMask);
4398     SDValue Hi = DAG.getNode(ISD::SRL, dl, SrcVT, Src, HiShift);
4399     SDValue LoOr = DAG.getNode(ISD::OR, dl, SrcVT, Lo, TwoP52);
4400     SDValue HiOr = DAG.getNode(ISD::OR, dl, SrcVT, Hi, TwoP84);
4401     SDValue LoFlt = DAG.getBitcast(DstVT, LoOr);
4402     SDValue HiFlt = DAG.getBitcast(DstVT, HiOr);
4403     SDValue HiSub = DAG.getNode(ISD::FSUB, dl, DstVT, HiFlt, TwoP84PlusTwoP52);
4404     Result = DAG.getNode(ISD::FADD, dl, DstVT, LoFlt, HiSub);
4405     return true;
4406   }
4407
4408   return false;
4409 }
4410
4411 SDValue TargetLowering::expandFMINNUM_FMAXNUM(SDNode *Node,
4412                                               SelectionDAG &DAG) const {
4413   SDLoc dl(Node);
4414   unsigned NewOp = Node->getOpcode() == ISD::FMINNUM ?
4415     ISD::FMINNUM_IEEE : ISD::FMAXNUM_IEEE;
4416   EVT VT = Node->getValueType(0);
4417   if (isOperationLegalOrCustom(NewOp, VT)) {
4418     SDValue Quiet0 = Node->getOperand(0);
4419     SDValue Quiet1 = Node->getOperand(1);
4420
4421     if (!Node->getFlags().hasNoNaNs()) {
4422       // Insert canonicalizes if it's possible we need to quiet to get correct
4423       // sNaN behavior.
4424       if (!DAG.isKnownNeverSNaN(Quiet0)) {
4425         Quiet0 = DAG.getNode(ISD::FCANONICALIZE, dl, VT, Quiet0,
4426                              Node->getFlags());
4427       }
4428       if (!DAG.isKnownNeverSNaN(Quiet1)) {
4429         Quiet1 = DAG.getNode(ISD::FCANONICALIZE, dl, VT, Quiet1,
4430                              Node->getFlags());
4431       }
4432     }
4433
4434     return DAG.getNode(NewOp, dl, VT, Quiet0, Quiet1, Node->getFlags());
4435   }
4436
4437   return SDValue();
4438 }
4439
4440 bool TargetLowering::expandCTPOP(SDNode *Node, SDValue &Result,
4441                                  SelectionDAG &DAG) const {
4442   SDLoc dl(Node);
4443   EVT VT = Node->getValueType(0);
4444   EVT ShVT = getShiftAmountTy(VT, DAG.getDataLayout());
4445   SDValue Op = Node->getOperand(0);
4446   unsigned Len = VT.getScalarSizeInBits();
4447   assert(VT.isInteger() && "CTPOP not implemented for this type.");
4448
4449   // TODO: Add support for irregular type lengths.
4450   if (!(Len <= 128 && Len % 8 == 0))
4451     return false;
4452
4453   // Only expand vector types if we have the appropriate vector bit operations.
4454   if (VT.isVector() && (!isOperationLegalOrCustom(ISD::ADD, VT) ||
4455                         !isOperationLegalOrCustom(ISD::SUB, VT) ||
4456                         !isOperationLegalOrCustom(ISD::SRL, VT) ||
4457                         (Len != 8 && !isOperationLegalOrCustom(ISD::MUL, VT)) ||
4458                         !isOperationLegalOrCustomOrPromote(ISD::AND, VT)))
4459     return false;
4460
4461   // This is the "best" algorithm from
4462   // http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
4463   SDValue Mask55 =
4464       DAG.getConstant(APInt::getSplat(Len, APInt(8, 0x55)), dl, VT);
4465   SDValue Mask33 =
4466       DAG.getConstant(APInt::getSplat(Len, APInt(8, 0x33)), dl, VT);
4467   SDValue Mask0F =
4468       DAG.getConstant(APInt::getSplat(Len, APInt(8, 0x0F)), dl, VT);
4469   SDValue Mask01 =
4470       DAG.getConstant(APInt::getSplat(Len, APInt(8, 0x01)), dl, VT);
4471
4472   // v = v - ((v >> 1) & 0x55555555...)
4473   Op = DAG.getNode(ISD::SUB, dl, VT, Op,
4474                    DAG.getNode(ISD::AND, dl, VT,
4475                                DAG.getNode(ISD::SRL, dl, VT, Op,
4476                                            DAG.getConstant(1, dl, ShVT)),
4477                                Mask55));
4478   // v = (v & 0x33333333...) + ((v >> 2) & 0x33333333...)
4479   Op = DAG.getNode(ISD::ADD, dl, VT, DAG.getNode(ISD::AND, dl, VT, Op, Mask33),
4480                    DAG.getNode(ISD::AND, dl, VT,
4481                                DAG.getNode(ISD::SRL, dl, VT, Op,
4482                                            DAG.getConstant(2, dl, ShVT)),
4483                                Mask33));
4484   // v = (v + (v >> 4)) & 0x0F0F0F0F...
4485   Op = DAG.getNode(ISD::AND, dl, VT,
4486                    DAG.getNode(ISD::ADD, dl, VT, Op,
4487                                DAG.getNode(ISD::SRL, dl, VT, Op,
4488                                            DAG.getConstant(4, dl, ShVT))),
4489                    Mask0F);
4490   // v = (v * 0x01010101...) >> (Len - 8)
4491   if (Len > 8)
4492     Op =
4493         DAG.getNode(ISD::SRL, dl, VT, DAG.getNode(ISD::MUL, dl, VT, Op, Mask01),
4494                     DAG.getConstant(Len - 8, dl, ShVT));
4495
4496   Result = Op;
4497   return true;
4498 }
4499
4500 bool TargetLowering::expandCTLZ(SDNode *Node, SDValue &Result,
4501                                 SelectionDAG &DAG) const {
4502   SDLoc dl(Node);
4503   EVT VT = Node->getValueType(0);
4504   EVT ShVT = getShiftAmountTy(VT, DAG.getDataLayout());
4505   SDValue Op = Node->getOperand(0);
4506   unsigned NumBitsPerElt = VT.getScalarSizeInBits();
4507
4508   // If the non-ZERO_UNDEF version is supported we can use that instead.
4509   if (Node->getOpcode() == ISD::CTLZ_ZERO_UNDEF &&
4510       isOperationLegalOrCustom(ISD::CTLZ, VT)) {
4511     Result = DAG.getNode(ISD::CTLZ, dl, VT, Op);
4512     return true;
4513   }
4514
4515   // If the ZERO_UNDEF version is supported use that and handle the zero case.
4516   if (isOperationLegalOrCustom(ISD::CTLZ_ZERO_UNDEF, VT)) {
4517     EVT SetCCVT =
4518         getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), VT);
4519     SDValue CTLZ = DAG.getNode(ISD::CTLZ_ZERO_UNDEF, dl, VT, Op);
4520     SDValue Zero = DAG.getConstant(0, dl, VT);
4521     SDValue SrcIsZero = DAG.getSetCC(dl, SetCCVT, Op, Zero, ISD::SETEQ);
4522     Result = DAG.getNode(ISD::SELECT, dl, VT, SrcIsZero,
4523                          DAG.getConstant(NumBitsPerElt, dl, VT), CTLZ);
4524     return true;
4525   }
4526
4527   // Only expand vector types if we have the appropriate vector bit operations.
4528   if (VT.isVector() && (!isPowerOf2_32(NumBitsPerElt) ||
4529                         !isOperationLegalOrCustom(ISD::CTPOP, VT) ||
4530                         !isOperationLegalOrCustom(ISD::SRL, VT) ||
4531                         !isOperationLegalOrCustomOrPromote(ISD::OR, VT)))
4532     return false;
4533
4534   // for now, we do this:
4535   // x = x | (x >> 1);
4536   // x = x | (x >> 2);
4537   // ...
4538   // x = x | (x >>16);
4539   // x = x | (x >>32); // for 64-bit input
4540   // return popcount(~x);
4541   //
4542   // Ref: "Hacker's Delight" by Henry Warren
4543   for (unsigned i = 0; (1U << i) <= (NumBitsPerElt / 2); ++i) {
4544     SDValue Tmp = DAG.getConstant(1ULL << i, dl, ShVT);
4545     Op = DAG.getNode(ISD::OR, dl, VT, Op,
4546                      DAG.getNode(ISD::SRL, dl, VT, Op, Tmp));
4547   }
4548   Op = DAG.getNOT(dl, Op, VT);
4549   Result = DAG.getNode(ISD::CTPOP, dl, VT, Op);
4550   return true;
4551 }
4552
4553 bool TargetLowering::expandCTTZ(SDNode *Node, SDValue &Result,
4554                                 SelectionDAG &DAG) const {
4555   SDLoc dl(Node);
4556   EVT VT = Node->getValueType(0);
4557   SDValue Op = Node->getOperand(0);
4558   unsigned NumBitsPerElt = VT.getScalarSizeInBits();
4559
4560   // If the non-ZERO_UNDEF version is supported we can use that instead.
4561   if (Node->getOpcode() == ISD::CTTZ_ZERO_UNDEF &&
4562       isOperationLegalOrCustom(ISD::CTTZ, VT)) {
4563     Result = DAG.getNode(ISD::CTTZ, dl, VT, Op);
4564     return true;
4565   }
4566
4567   // If the ZERO_UNDEF version is supported use that and handle the zero case.
4568   if (isOperationLegalOrCustom(ISD::CTTZ_ZERO_UNDEF, VT)) {
4569     EVT SetCCVT =
4570         getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), VT);
4571     SDValue CTTZ = DAG.getNode(ISD::CTTZ_ZERO_UNDEF, dl, VT, Op);
4572     SDValue Zero = DAG.getConstant(0, dl, VT);
4573     SDValue SrcIsZero = DAG.getSetCC(dl, SetCCVT, Op, Zero, ISD::SETEQ);
4574     Result = DAG.getNode(ISD::SELECT, dl, VT, SrcIsZero,
4575                          DAG.getConstant(NumBitsPerElt, dl, VT), CTTZ);
4576     return true;
4577   }
4578
4579   // Only expand vector types if we have the appropriate vector bit operations.
4580   if (VT.isVector() && (!isPowerOf2_32(NumBitsPerElt) ||
4581                         (!isOperationLegalOrCustom(ISD::CTPOP, VT) &&
4582                          !isOperationLegalOrCustom(ISD::CTLZ, VT)) ||
4583                         !isOperationLegalOrCustom(ISD::SUB, VT) ||
4584                         !isOperationLegalOrCustomOrPromote(ISD::AND, VT) ||
4585                         !isOperationLegalOrCustomOrPromote(ISD::XOR, VT)))
4586     return false;
4587
4588   // for now, we use: { return popcount(~x & (x - 1)); }
4589   // unless the target has ctlz but not ctpop, in which case we use:
4590   // { return 32 - nlz(~x & (x-1)); }
4591   // Ref: "Hacker's Delight" by Henry Warren
4592   SDValue Tmp = DAG.getNode(
4593       ISD::AND, dl, VT, DAG.getNOT(dl, Op, VT),
4594       DAG.getNode(ISD::SUB, dl, VT, Op, DAG.getConstant(1, dl, VT)));
4595
4596   // If ISD::CTLZ is legal and CTPOP isn't, then do that instead.
4597   if (isOperationLegal(ISD::CTLZ, VT) && !isOperationLegal(ISD::CTPOP, VT)) {
4598     Result =
4599         DAG.getNode(ISD::SUB, dl, VT, DAG.getConstant(NumBitsPerElt, dl, VT),
4600                     DAG.getNode(ISD::CTLZ, dl, VT, Tmp));
4601     return true;
4602   }
4603
4604   Result = DAG.getNode(ISD::CTPOP, dl, VT, Tmp);
4605   return true;
4606 }
4607
4608 SDValue TargetLowering::scalarizeVectorLoad(LoadSDNode *LD,
4609                                             SelectionDAG &DAG) const {
4610   SDLoc SL(LD);
4611   SDValue Chain = LD->getChain();
4612   SDValue BasePTR = LD->getBasePtr();
4613   EVT SrcVT = LD->getMemoryVT();
4614   ISD::LoadExtType ExtType = LD->getExtensionType();
4615
4616   unsigned NumElem = SrcVT.getVectorNumElements();
4617
4618   EVT SrcEltVT = SrcVT.getScalarType();
4619   EVT DstEltVT = LD->getValueType(0).getScalarType();
4620
4621   unsigned Stride = SrcEltVT.getSizeInBits() / 8;
4622   assert(SrcEltVT.isByteSized());
4623
4624   SmallVector<SDValue, 8> Vals;
4625   SmallVector<SDValue, 8> LoadChains;
4626
4627   for (unsigned Idx = 0; Idx < NumElem; ++Idx) {
4628     SDValue ScalarLoad =
4629         DAG.getExtLoad(ExtType, SL, DstEltVT, Chain, BasePTR,
4630                        LD->getPointerInfo().getWithOffset(Idx * Stride),
4631                        SrcEltVT, MinAlign(LD->getAlignment(), Idx * Stride),
4632                        LD->getMemOperand()->getFlags(), LD->getAAInfo());
4633
4634     BasePTR = DAG.getObjectPtrOffset(SL, BasePTR, Stride);
4635
4636     Vals.push_back(ScalarLoad.getValue(0));
4637     LoadChains.push_back(ScalarLoad.getValue(1));
4638   }
4639
4640   SDValue NewChain = DAG.getNode(ISD::TokenFactor, SL, MVT::Other, LoadChains);
4641   SDValue Value = DAG.getBuildVector(LD->getValueType(0), SL, Vals);
4642
4643   return DAG.getMergeValues({ Value, NewChain }, SL);
4644 }
4645
4646 SDValue TargetLowering::scalarizeVectorStore(StoreSDNode *ST,
4647                                              SelectionDAG &DAG) const {
4648   SDLoc SL(ST);
4649
4650   SDValue Chain = ST->getChain();
4651   SDValue BasePtr = ST->getBasePtr();
4652   SDValue Value = ST->getValue();
4653   EVT StVT = ST->getMemoryVT();
4654
4655   // The type of the data we want to save
4656   EVT RegVT = Value.getValueType();
4657   EVT RegSclVT = RegVT.getScalarType();
4658
4659   // The type of data as saved in memory.
4660   EVT MemSclVT = StVT.getScalarType();
4661
4662   EVT IdxVT = getVectorIdxTy(DAG.getDataLayout());
4663   unsigned NumElem = StVT.getVectorNumElements();
4664
4665   // A vector must always be stored in memory as-is, i.e. without any padding
4666   // between the elements, since various code depend on it, e.g. in the
4667   // handling of a bitcast of a vector type to int, which may be done with a
4668   // vector store followed by an integer load. A vector that does not have
4669   // elements that are byte-sized must therefore be stored as an integer
4670   // built out of the extracted vector elements.
4671   if (!MemSclVT.isByteSized()) {
4672     unsigned NumBits = StVT.getSizeInBits();
4673     EVT IntVT = EVT::getIntegerVT(*DAG.getContext(), NumBits);
4674
4675     SDValue CurrVal = DAG.getConstant(0, SL, IntVT);
4676
4677     for (unsigned Idx = 0; Idx < NumElem; ++Idx) {
4678       SDValue Elt = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, SL, RegSclVT, Value,
4679                                 DAG.getConstant(Idx, SL, IdxVT));
4680       SDValue Trunc = DAG.getNode(ISD::TRUNCATE, SL, MemSclVT, Elt);
4681       SDValue ExtElt = DAG.getNode(ISD::ZERO_EXTEND, SL, IntVT, Trunc);
4682       unsigned ShiftIntoIdx =
4683           (DAG.getDataLayout().isBigEndian() ? (NumElem - 1) - Idx : Idx);
4684       SDValue ShiftAmount =
4685           DAG.getConstant(ShiftIntoIdx * MemSclVT.getSizeInBits(), SL, IntVT);
4686       SDValue ShiftedElt =
4687           DAG.getNode(ISD::SHL, SL, IntVT, ExtElt, ShiftAmount);
4688       CurrVal = DAG.getNode(ISD::OR, SL, IntVT, CurrVal, ShiftedElt);
4689     }
4690
4691     return DAG.getStore(Chain, SL, CurrVal, BasePtr, ST->getPointerInfo(),
4692                         ST->getAlignment(), ST->getMemOperand()->getFlags(),
4693                         ST->getAAInfo());
4694   }
4695
4696   // Store Stride in bytes
4697   unsigned Stride = MemSclVT.getSizeInBits() / 8;
4698   assert (Stride && "Zero stride!");
4699   // Extract each of the elements from the original vector and save them into
4700   // memory individually.
4701   SmallVector<SDValue, 8> Stores;
4702   for (unsigned Idx = 0; Idx < NumElem; ++Idx) {
4703     SDValue Elt = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, SL, RegSclVT, Value,
4704                               DAG.getConstant(Idx, SL, IdxVT));
4705
4706     SDValue Ptr = DAG.getObjectPtrOffset(SL, BasePtr, Idx * Stride);
4707
4708     // This scalar TruncStore may be illegal, but we legalize it later.
4709     SDValue Store = DAG.getTruncStore(
4710         Chain, SL, Elt, Ptr, ST->getPointerInfo().getWithOffset(Idx * Stride),
4711         MemSclVT, MinAlign(ST->getAlignment(), Idx * Stride),
4712         ST->getMemOperand()->getFlags(), ST->getAAInfo());
4713
4714     Stores.push_back(Store);
4715   }
4716
4717   return DAG.getNode(ISD::TokenFactor, SL, MVT::Other, Stores);
4718 }
4719
4720 std::pair<SDValue, SDValue>
4721 TargetLowering::expandUnalignedLoad(LoadSDNode *LD, SelectionDAG &DAG) const {
4722   assert(LD->getAddressingMode() == ISD::UNINDEXED &&
4723          "unaligned indexed loads not implemented!");
4724   SDValue Chain = LD->getChain();
4725   SDValue Ptr = LD->getBasePtr();
4726   EVT VT = LD->getValueType(0);
4727   EVT LoadedVT = LD->getMemoryVT();
4728   SDLoc dl(LD);
4729   auto &MF = DAG.getMachineFunction();
4730
4731   if (VT.isFloatingPoint() || VT.isVector()) {
4732     EVT intVT = EVT::getIntegerVT(*DAG.getContext(), LoadedVT.getSizeInBits());
4733     if (isTypeLegal(intVT) && isTypeLegal(LoadedVT)) {
4734       if (!isOperationLegalOrCustom(ISD::LOAD, intVT) &&
4735           LoadedVT.isVector()) {
4736         // Scalarize the load and let the individual components be handled.
4737         SDValue Scalarized = scalarizeVectorLoad(LD, DAG);
4738         if (Scalarized->getOpcode() == ISD::MERGE_VALUES)
4739           return std::make_pair(Scalarized.getOperand(0), Scalarized.getOperand(1));
4740         return std::make_pair(Scalarized.getValue(0), Scalarized.getValue(1));
4741       }
4742
4743       // Expand to a (misaligned) integer load of the same size,
4744       // then bitconvert to floating point or vector.
4745       SDValue newLoad = DAG.getLoad(intVT, dl, Chain, Ptr,
4746                                     LD->getMemOperand());
4747       SDValue Result = DAG.getNode(ISD::BITCAST, dl, LoadedVT, newLoad);
4748       if (LoadedVT != VT)
4749         Result = DAG.getNode(VT.isFloatingPoint() ? ISD::FP_EXTEND :
4750                              ISD::ANY_EXTEND, dl, VT, Result);
4751
4752       return std::make_pair(Result, newLoad.getValue(1));
4753     }
4754
4755     // Copy the value to a (aligned) stack slot using (unaligned) integer
4756     // loads and stores, then do a (aligned) load from the stack slot.
4757     MVT RegVT = getRegisterType(*DAG.getContext(), intVT);
4758     unsigned LoadedBytes = LoadedVT.getStoreSize();
4759     unsigned RegBytes = RegVT.getSizeInBits() / 8;
4760     unsigned NumRegs = (LoadedBytes + RegBytes - 1) / RegBytes;
4761
4762     // Make sure the stack slot is also aligned for the register type.
4763     SDValue StackBase = DAG.CreateStackTemporary(LoadedVT, RegVT);
4764     auto FrameIndex = cast<FrameIndexSDNode>(StackBase.getNode())->getIndex();
4765     SmallVector<SDValue, 8> Stores;
4766     SDValue StackPtr = StackBase;
4767     unsigned Offset = 0;
4768
4769     EVT PtrVT = Ptr.getValueType();
4770     EVT StackPtrVT = StackPtr.getValueType();
4771
4772     SDValue PtrIncrement = DAG.getConstant(RegBytes, dl, PtrVT);
4773     SDValue StackPtrIncrement = DAG.getConstant(RegBytes, dl, StackPtrVT);
4774
4775     // Do all but one copies using the full register width.
4776     for (unsigned i = 1; i < NumRegs; i++) {
4777       // Load one integer register's worth from the original location.
4778       SDValue Load = DAG.getLoad(
4779           RegVT, dl, Chain, Ptr, LD->getPointerInfo().getWithOffset(Offset),
4780           MinAlign(LD->getAlignment(), Offset), LD->getMemOperand()->getFlags(),
4781           LD->getAAInfo());
4782       // Follow the load with a store to the stack slot.  Remember the store.
4783       Stores.push_back(DAG.getStore(
4784           Load.getValue(1), dl, Load, StackPtr,
4785           MachinePointerInfo::getFixedStack(MF, FrameIndex, Offset)));
4786       // Increment the pointers.
4787       Offset += RegBytes;
4788
4789       Ptr = DAG.getObjectPtrOffset(dl, Ptr, PtrIncrement);
4790       StackPtr = DAG.getObjectPtrOffset(dl, StackPtr, StackPtrIncrement);
4791     }
4792
4793     // The last copy may be partial.  Do an extending load.
4794     EVT MemVT = EVT::getIntegerVT(*DAG.getContext(),
4795                                   8 * (LoadedBytes - Offset));
4796     SDValue Load =
4797         DAG.getExtLoad(ISD::EXTLOAD, dl, RegVT, Chain, Ptr,
4798                        LD->getPointerInfo().getWithOffset(Offset), MemVT,
4799                        MinAlign(LD->getAlignment(), Offset),
4800                        LD->getMemOperand()->getFlags(), LD->getAAInfo());
4801     // Follow the load with a store to the stack slot.  Remember the store.
4802     // On big-endian machines this requires a truncating store to ensure
4803     // that the bits end up in the right place.
4804     Stores.push_back(DAG.getTruncStore(
4805         Load.getValue(1), dl, Load, StackPtr,
4806         MachinePointerInfo::getFixedStack(MF, FrameIndex, Offset), MemVT));
4807
4808     // The order of the stores doesn't matter - say it with a TokenFactor.
4809     SDValue TF = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Stores);
4810
4811     // Finally, perform the original load only redirected to the stack slot.
4812     Load = DAG.getExtLoad(LD->getExtensionType(), dl, VT, TF, StackBase,
4813                           MachinePointerInfo::getFixedStack(MF, FrameIndex, 0),
4814                           LoadedVT);
4815
4816     // Callers expect a MERGE_VALUES node.
4817     return std::make_pair(Load, TF);
4818   }
4819
4820   assert(LoadedVT.isInteger() && !LoadedVT.isVector() &&
4821          "Unaligned load of unsupported type.");
4822
4823   // Compute the new VT that is half the size of the old one.  This is an
4824   // integer MVT.
4825   unsigned NumBits = LoadedVT.getSizeInBits();
4826   EVT NewLoadedVT;
4827   NewLoadedVT = EVT::getIntegerVT(*DAG.getContext(), NumBits/2);
4828   NumBits >>= 1;
4829
4830   unsigned Alignment = LD->getAlignment();
4831   unsigned IncrementSize = NumBits / 8;
4832   ISD::LoadExtType HiExtType = LD->getExtensionType();
4833
4834   // If the original load is NON_EXTLOAD, the hi part load must be ZEXTLOAD.
4835   if (HiExtType == ISD::NON_EXTLOAD)
4836     HiExtType = ISD::ZEXTLOAD;
4837
4838   // Load the value in two parts
4839   SDValue Lo, Hi;
4840   if (DAG.getDataLayout().isLittleEndian()) {
4841     Lo = DAG.getExtLoad(ISD::ZEXTLOAD, dl, VT, Chain, Ptr, LD->getPointerInfo(),
4842                         NewLoadedVT, Alignment, LD->getMemOperand()->getFlags(),
4843                         LD->getAAInfo());
4844
4845     Ptr = DAG.getObjectPtrOffset(dl, Ptr, IncrementSize);
4846     Hi = DAG.getExtLoad(HiExtType, dl, VT, Chain, Ptr,
4847                         LD->getPointerInfo().getWithOffset(IncrementSize),
4848                         NewLoadedVT, MinAlign(Alignment, IncrementSize),
4849                         LD->getMemOperand()->getFlags(), LD->getAAInfo());
4850   } else {
4851     Hi = DAG.getExtLoad(HiExtType, dl, VT, Chain, Ptr, LD->getPointerInfo(),
4852                         NewLoadedVT, Alignment, LD->getMemOperand()->getFlags(),
4853                         LD->getAAInfo());
4854
4855     Ptr = DAG.getObjectPtrOffset(dl, Ptr, IncrementSize);
4856     Lo = DAG.getExtLoad(ISD::ZEXTLOAD, dl, VT, Chain, Ptr,
4857                         LD->getPointerInfo().getWithOffset(IncrementSize),
4858                         NewLoadedVT, MinAlign(Alignment, IncrementSize),
4859                         LD->getMemOperand()->getFlags(), LD->getAAInfo());
4860   }
4861
4862   // aggregate the two parts
4863   SDValue ShiftAmount =
4864       DAG.getConstant(NumBits, dl, getShiftAmountTy(Hi.getValueType(),
4865                                                     DAG.getDataLayout()));
4866   SDValue Result = DAG.getNode(ISD::SHL, dl, VT, Hi, ShiftAmount);
4867   Result = DAG.getNode(ISD::OR, dl, VT, Result, Lo);
4868
4869   SDValue TF = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Lo.getValue(1),
4870                              Hi.getValue(1));
4871
4872   return std::make_pair(Result, TF);
4873 }
4874
4875 SDValue TargetLowering::expandUnalignedStore(StoreSDNode *ST,
4876                                              SelectionDAG &DAG) const {
4877   assert(ST->getAddressingMode() == ISD::UNINDEXED &&
4878          "unaligned indexed stores not implemented!");
4879   SDValue Chain = ST->getChain();
4880   SDValue Ptr = ST->getBasePtr();
4881   SDValue Val = ST->getValue();
4882   EVT VT = Val.getValueType();
4883   int Alignment = ST->getAlignment();
4884   auto &MF = DAG.getMachineFunction();
4885   EVT MemVT = ST->getMemoryVT();
4886
4887   SDLoc dl(ST);
4888   if (MemVT.isFloatingPoint() || MemVT.isVector()) {
4889     EVT intVT = EVT::getIntegerVT(*DAG.getContext(), VT.getSizeInBits());
4890     if (isTypeLegal(intVT)) {
4891       if (!isOperationLegalOrCustom(ISD::STORE, intVT) &&
4892           MemVT.isVector()) {
4893         // Scalarize the store and let the individual components be handled.
4894         SDValue Result = scalarizeVectorStore(ST, DAG);
4895
4896         return Result;
4897       }
4898       // Expand to a bitconvert of the value to the integer type of the
4899       // same size, then a (misaligned) int store.
4900       // FIXME: Does not handle truncating floating point stores!
4901       SDValue Result = DAG.getNode(ISD::BITCAST, dl, intVT, Val);
4902       Result = DAG.getStore(Chain, dl, Result, Ptr, ST->getPointerInfo(),
4903                             Alignment, ST->getMemOperand()->getFlags());
4904       return Result;
4905     }
4906     // Do a (aligned) store to a stack slot, then copy from the stack slot
4907     // to the final destination using (unaligned) integer loads and stores.
4908     EVT StoredVT = ST->getMemoryVT();
4909     MVT RegVT =
4910       getRegisterType(*DAG.getContext(),
4911                       EVT::getIntegerVT(*DAG.getContext(),
4912                                         StoredVT.getSizeInBits()));
4913     EVT PtrVT = Ptr.getValueType();
4914     unsigned StoredBytes = StoredVT.getStoreSize();
4915     unsigned RegBytes = RegVT.getSizeInBits() / 8;
4916     unsigned NumRegs = (StoredBytes + RegBytes - 1) / RegBytes;
4917
4918     // Make sure the stack slot is also aligned for the register type.
4919     SDValue StackPtr = DAG.CreateStackTemporary(StoredVT, RegVT);
4920     auto FrameIndex = cast<FrameIndexSDNode>(StackPtr.getNode())->getIndex();
4921
4922     // Perform the original store, only redirected to the stack slot.
4923     SDValue Store = DAG.getTruncStore(
4924         Chain, dl, Val, StackPtr,
4925         MachinePointerInfo::getFixedStack(MF, FrameIndex, 0), StoredVT);
4926
4927     EVT StackPtrVT = StackPtr.getValueType();
4928
4929     SDValue PtrIncrement = DAG.getConstant(RegBytes, dl, PtrVT);
4930     SDValue StackPtrIncrement = DAG.getConstant(RegBytes, dl, StackPtrVT);
4931     SmallVector<SDValue, 8> Stores;
4932     unsigned Offset = 0;
4933
4934     // Do all but one copies using the full register width.
4935     for (unsigned i = 1; i < NumRegs; i++) {
4936       // Load one integer register's worth from the stack slot.
4937       SDValue Load = DAG.getLoad(
4938           RegVT, dl, Store, StackPtr,
4939           MachinePointerInfo::getFixedStack(MF, FrameIndex, Offset));
4940       // Store it to the final location.  Remember the store.
4941       Stores.push_back(DAG.getStore(Load.getValue(1), dl, Load, Ptr,
4942                                     ST->getPointerInfo().getWithOffset(Offset),
4943                                     MinAlign(ST->getAlignment(), Offset),
4944                                     ST->getMemOperand()->getFlags()));
4945       // Increment the pointers.
4946       Offset += RegBytes;
4947       StackPtr = DAG.getObjectPtrOffset(dl, StackPtr, StackPtrIncrement);
4948       Ptr = DAG.getObjectPtrOffset(dl, Ptr, PtrIncrement);
4949     }
4950
4951     // The last store may be partial.  Do a truncating store.  On big-endian
4952     // machines this requires an extending load from the stack slot to ensure
4953     // that the bits are in the right place.
4954     EVT MemVT = EVT::getIntegerVT(*DAG.getContext(),
4955                                   8 * (StoredBytes - Offset));
4956
4957     // Load from the stack slot.
4958     SDValue Load = DAG.getExtLoad(
4959         ISD::EXTLOAD, dl, RegVT, Store, StackPtr,
4960         MachinePointerInfo::getFixedStack(MF, FrameIndex, Offset), MemVT);
4961
4962     Stores.push_back(
4963         DAG.getTruncStore(Load.getValue(1), dl, Load, Ptr,
4964                           ST->getPointerInfo().getWithOffset(Offset), MemVT,
4965                           MinAlign(ST->getAlignment(), Offset),
4966                           ST->getMemOperand()->getFlags(), ST->getAAInfo()));
4967     // The order of the stores doesn't matter - say it with a TokenFactor.
4968     SDValue Result = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Stores);
4969     return Result;
4970   }
4971
4972   assert(ST->getMemoryVT().isInteger() &&
4973          !ST->getMemoryVT().isVector() &&
4974          "Unaligned store of unknown type.");
4975   // Get the half-size VT
4976   EVT NewStoredVT = ST->getMemoryVT().getHalfSizedIntegerVT(*DAG.getContext());
4977   int NumBits = NewStoredVT.getSizeInBits();
4978   int IncrementSize = NumBits / 8;
4979
4980   // Divide the stored value in two parts.
4981   SDValue ShiftAmount =
4982       DAG.getConstant(NumBits, dl, getShiftAmountTy(Val.getValueType(),
4983                                                     DAG.getDataLayout()));
4984   SDValue Lo = Val;
4985   SDValue Hi = DAG.getNode(ISD::SRL, dl, VT, Val, ShiftAmount);
4986
4987   // Store the two parts
4988   SDValue Store1, Store2;
4989   Store1 = DAG.getTruncStore(Chain, dl,
4990                              DAG.getDataLayout().isLittleEndian() ? Lo : Hi,
4991                              Ptr, ST->getPointerInfo(), NewStoredVT, Alignment,
4992                              ST->getMemOperand()->getFlags());
4993
4994   Ptr = DAG.getObjectPtrOffset(dl, Ptr, IncrementSize);
4995   Alignment = MinAlign(Alignment, IncrementSize);
4996   Store2 = DAG.getTruncStore(
4997       Chain, dl, DAG.getDataLayout().isLittleEndian() ? Hi : Lo, Ptr,
4998       ST->getPointerInfo().getWithOffset(IncrementSize), NewStoredVT, Alignment,
4999       ST->getMemOperand()->getFlags(), ST->getAAInfo());
5000
5001   SDValue Result =
5002     DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Store1, Store2);
5003   return Result;
5004 }
5005
5006 SDValue
5007 TargetLowering::IncrementMemoryAddress(SDValue Addr, SDValue Mask,
5008                                        const SDLoc &DL, EVT DataVT,
5009                                        SelectionDAG &DAG,
5010                                        bool IsCompressedMemory) const {
5011   SDValue Increment;
5012   EVT AddrVT = Addr.getValueType();
5013   EVT MaskVT = Mask.getValueType();
5014   assert(DataVT.getVectorNumElements() == MaskVT.getVectorNumElements() &&
5015          "Incompatible types of Data and Mask");
5016   if (IsCompressedMemory) {
5017     // Incrementing the pointer according to number of '1's in the mask.
5018     EVT MaskIntVT = EVT::getIntegerVT(*DAG.getContext(), MaskVT.getSizeInBits());
5019     SDValue MaskInIntReg = DAG.getBitcast(MaskIntVT, Mask);
5020     if (MaskIntVT.getSizeInBits() < 32) {
5021       MaskInIntReg = DAG.getNode(ISD::ZERO_EXTEND, DL, MVT::i32, MaskInIntReg);
5022       MaskIntVT = MVT::i32;
5023     }
5024
5025     // Count '1's with POPCNT.
5026     Increment = DAG.getNode(ISD::CTPOP, DL, MaskIntVT, MaskInIntReg);
5027     Increment = DAG.getZExtOrTrunc(Increment, DL, AddrVT);
5028     // Scale is an element size in bytes.
5029     SDValue Scale = DAG.getConstant(DataVT.getScalarSizeInBits() / 8, DL,
5030                                     AddrVT);
5031     Increment = DAG.getNode(ISD::MUL, DL, AddrVT, Increment, Scale);
5032   } else
5033     Increment = DAG.getConstant(DataVT.getStoreSize(), DL, AddrVT);
5034
5035   return DAG.getNode(ISD::ADD, DL, AddrVT, Addr, Increment);
5036 }
5037
5038 static SDValue clampDynamicVectorIndex(SelectionDAG &DAG,
5039                                        SDValue Idx,
5040                                        EVT VecVT,
5041                                        const SDLoc &dl) {
5042   if (isa<ConstantSDNode>(Idx))
5043     return Idx;
5044
5045   EVT IdxVT = Idx.getValueType();
5046   unsigned NElts = VecVT.getVectorNumElements();
5047   if (isPowerOf2_32(NElts)) {
5048     APInt Imm = APInt::getLowBitsSet(IdxVT.getSizeInBits(),
5049                                      Log2_32(NElts));
5050     return DAG.getNode(ISD::AND, dl, IdxVT, Idx,
5051                        DAG.getConstant(Imm, dl, IdxVT));
5052   }
5053
5054   return DAG.getNode(ISD::UMIN, dl, IdxVT, Idx,
5055                      DAG.getConstant(NElts - 1, dl, IdxVT));
5056 }
5057
5058 SDValue TargetLowering::getVectorElementPointer(SelectionDAG &DAG,
5059                                                 SDValue VecPtr, EVT VecVT,
5060                                                 SDValue Index) const {
5061   SDLoc dl(Index);
5062   // Make sure the index type is big enough to compute in.
5063   Index = DAG.getZExtOrTrunc(Index, dl, VecPtr.getValueType());
5064
5065   EVT EltVT = VecVT.getVectorElementType();
5066
5067   // Calculate the element offset and add it to the pointer.
5068   unsigned EltSize = EltVT.getSizeInBits() / 8; // FIXME: should be ABI size.
5069   assert(EltSize * 8 == EltVT.getSizeInBits() &&
5070          "Converting bits to bytes lost precision");
5071
5072   Index = clampDynamicVectorIndex(DAG, Index, VecVT, dl);
5073
5074   EVT IdxVT = Index.getValueType();
5075
5076   Index = DAG.getNode(ISD::MUL, dl, IdxVT, Index,
5077                       DAG.getConstant(EltSize, dl, IdxVT));
5078   return DAG.getNode(ISD::ADD, dl, IdxVT, VecPtr, Index);
5079 }
5080
5081 //===----------------------------------------------------------------------===//
5082 // Implementation of Emulated TLS Model
5083 //===----------------------------------------------------------------------===//
5084
5085 SDValue TargetLowering::LowerToTLSEmulatedModel(const GlobalAddressSDNode *GA,
5086                                                 SelectionDAG &DAG) const {
5087   // Access to address of TLS varialbe xyz is lowered to a function call:
5088   //   __emutls_get_address( address of global variable named "__emutls_v.xyz" )
5089   EVT PtrVT = getPointerTy(DAG.getDataLayout());
5090   PointerType *VoidPtrType = Type::getInt8PtrTy(*DAG.getContext());
5091   SDLoc dl(GA);
5092
5093   ArgListTy Args;
5094   ArgListEntry Entry;
5095   std::string NameString = ("__emutls_v." + GA->getGlobal()->getName()).str();
5096   Module *VariableModule = const_cast<Module*>(GA->getGlobal()->getParent());
5097   StringRef EmuTlsVarName(NameString);
5098   GlobalVariable *EmuTlsVar = VariableModule->getNamedGlobal(EmuTlsVarName);
5099   assert(EmuTlsVar && "Cannot find EmuTlsVar ");
5100   Entry.Node = DAG.getGlobalAddress(EmuTlsVar, dl, PtrVT);
5101   Entry.Ty = VoidPtrType;
5102   Args.push_back(Entry);
5103
5104   SDValue EmuTlsGetAddr = DAG.getExternalSymbol("__emutls_get_address", PtrVT);
5105
5106   TargetLowering::CallLoweringInfo CLI(DAG);
5107   CLI.setDebugLoc(dl).setChain(DAG.getEntryNode());
5108   CLI.setLibCallee(CallingConv::C, VoidPtrType, EmuTlsGetAddr, std::move(Args));
5109   std::pair<SDValue, SDValue> CallResult = LowerCallTo(CLI);
5110
5111   // TLSADDR will be codegen'ed as call. Inform MFI that function has calls.
5112   // At last for X86 targets, maybe good for other targets too?
5113   MachineFrameInfo &MFI = DAG.getMachineFunction().getFrameInfo();
5114   MFI.setAdjustsStack(true);  // Is this only for X86 target?
5115   MFI.setHasCalls(true);
5116
5117   assert((GA->getOffset() == 0) &&
5118          "Emulated TLS must have zero offset in GlobalAddressSDNode");
5119   return CallResult.first;
5120 }
5121
5122 SDValue TargetLowering::lowerCmpEqZeroToCtlzSrl(SDValue Op,
5123                                                 SelectionDAG &DAG) const {
5124   assert((Op->getOpcode() == ISD::SETCC) && "Input has to be a SETCC node.");
5125   if (!isCtlzFast())
5126     return SDValue();
5127   ISD::CondCode CC = cast<CondCodeSDNode>(Op.getOperand(2))->get();
5128   SDLoc dl(Op);
5129   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
5130     if (C->isNullValue() && CC == ISD::SETEQ) {
5131       EVT VT = Op.getOperand(0).getValueType();
5132       SDValue Zext = Op.getOperand(0);
5133       if (VT.bitsLT(MVT::i32)) {
5134         VT = MVT::i32;
5135         Zext = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Op.getOperand(0));
5136       }
5137       unsigned Log2b = Log2_32(VT.getSizeInBits());
5138       SDValue Clz = DAG.getNode(ISD::CTLZ, dl, VT, Zext);
5139       SDValue Scc = DAG.getNode(ISD::SRL, dl, VT, Clz,
5140                                 DAG.getConstant(Log2b, dl, MVT::i32));
5141       return DAG.getNode(ISD::TRUNCATE, dl, MVT::i32, Scc);
5142     }
5143   }
5144   return SDValue();
5145 }
5146
5147 SDValue TargetLowering::getExpandedSaturationAdditionSubtraction(
5148     SDNode *Node, SelectionDAG &DAG) const {
5149   unsigned Opcode = Node->getOpcode();
5150   unsigned OverflowOp;
5151   switch (Opcode) {
5152   case ISD::SADDSAT:
5153     OverflowOp = ISD::SADDO;
5154     break;
5155   case ISD::UADDSAT:
5156     OverflowOp = ISD::UADDO;
5157     break;
5158   case ISD::SSUBSAT:
5159     OverflowOp = ISD::SSUBO;
5160     break;
5161   case ISD::USUBSAT:
5162     OverflowOp = ISD::USUBO;
5163     break;
5164   default:
5165     llvm_unreachable("Expected method to receive signed or unsigned saturation "
5166                      "addition or subtraction node.");
5167   }
5168   assert(Node->getNumOperands() == 2 && "Expected node to have 2 operands.");
5169
5170   SDLoc dl(Node);
5171   SDValue LHS = Node->getOperand(0);
5172   SDValue RHS = Node->getOperand(1);
5173   assert(LHS.getValueType().isScalarInteger() &&
5174          "Expected operands to be integers. Vector of int arguments should "
5175          "already be unrolled.");
5176   assert(RHS.getValueType().isScalarInteger() &&
5177          "Expected operands to be integers. Vector of int arguments should "
5178          "already be unrolled.");
5179   assert(LHS.getValueType() == RHS.getValueType() &&
5180          "Expected both operands to be the same type");
5181
5182   unsigned BitWidth = LHS.getValueSizeInBits();
5183   EVT ResultType = LHS.getValueType();
5184   EVT BoolVT =
5185       getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), ResultType);
5186   SDValue Result =
5187       DAG.getNode(OverflowOp, dl, DAG.getVTList(ResultType, BoolVT), LHS, RHS);
5188   SDValue SumDiff = Result.getValue(0);
5189   SDValue Overflow = Result.getValue(1);
5190   SDValue Zero = DAG.getConstant(0, dl, ResultType);
5191
5192   if (Opcode == ISD::UADDSAT) {
5193     // Just need to check overflow for SatMax.
5194     APInt MaxVal = APInt::getMaxValue(BitWidth);
5195     SDValue SatMax = DAG.getConstant(MaxVal, dl, ResultType);
5196     return DAG.getSelect(dl, ResultType, Overflow, SatMax, SumDiff);
5197   } else if (Opcode == ISD::USUBSAT) {
5198     // Just need to check overflow for SatMin.
5199     APInt MinVal = APInt::getMinValue(BitWidth);
5200     SDValue SatMin = DAG.getConstant(MinVal, dl, ResultType);
5201     return DAG.getSelect(dl, ResultType, Overflow, SatMin, SumDiff);
5202   } else {
5203     // SatMax -> Overflow && SumDiff < 0
5204     // SatMin -> Overflow && SumDiff >= 0
5205     APInt MinVal = APInt::getSignedMinValue(BitWidth);
5206     APInt MaxVal = APInt::getSignedMaxValue(BitWidth);
5207     SDValue SatMin = DAG.getConstant(MinVal, dl, ResultType);
5208     SDValue SatMax = DAG.getConstant(MaxVal, dl, ResultType);
5209     SDValue SumNeg = DAG.getSetCC(dl, BoolVT, SumDiff, Zero, ISD::SETLT);
5210     Result = DAG.getSelect(dl, ResultType, SumNeg, SatMax, SatMin);
5211     return DAG.getSelect(dl, ResultType, Overflow, Result, SumDiff);
5212   }
5213 }
5214
5215 SDValue
5216 TargetLowering::getExpandedFixedPointMultiplication(SDNode *Node,
5217                                                     SelectionDAG &DAG) const {
5218   assert(Node->getOpcode() == ISD::SMULFIX && "Expected opcode to be SMULFIX.");
5219   assert(Node->getNumOperands() == 3 &&
5220          "Expected signed fixed point multiplication to have 3 operands.");
5221
5222   SDLoc dl(Node);
5223   SDValue LHS = Node->getOperand(0);
5224   SDValue RHS = Node->getOperand(1);
5225   assert(LHS.getValueType().isScalarInteger() &&
5226          "Expected operands to be integers. Vector of int arguments should "
5227          "already be unrolled.");
5228   assert(RHS.getValueType().isScalarInteger() &&
5229          "Expected operands to be integers. Vector of int arguments should "
5230          "already be unrolled.");
5231   assert(LHS.getValueType() == RHS.getValueType() &&
5232          "Expected both operands to be the same type");
5233
5234   unsigned Scale = Node->getConstantOperandVal(2);
5235   EVT VT = LHS.getValueType();
5236   assert(Scale < VT.getScalarSizeInBits() &&
5237          "Expected scale to be less than the number of bits.");
5238
5239   if (!Scale)
5240     return DAG.getNode(ISD::MUL, dl, VT, LHS, RHS);
5241
5242   // Get the upper and lower bits of the result.
5243   SDValue Lo, Hi;
5244   if (isOperationLegalOrCustom(ISD::SMUL_LOHI, VT)) {
5245     SDValue Result =
5246         DAG.getNode(ISD::SMUL_LOHI, dl, DAG.getVTList(VT, VT), LHS, RHS);
5247     Lo = Result.getValue(0);
5248     Hi = Result.getValue(1);
5249   } else if (isOperationLegalOrCustom(ISD::MULHS, VT)) {
5250     Lo = DAG.getNode(ISD::MUL, dl, VT, LHS, RHS);
5251     Hi = DAG.getNode(ISD::MULHS, dl, VT, LHS, RHS);
5252   } else {
5253     report_fatal_error("Unable to expand signed fixed point multiplication.");
5254   }
5255
5256   // The result will need to be shifted right by the scale since both operands
5257   // are scaled. The result is given to us in 2 halves, so we only want part of
5258   // both in the result.
5259   EVT ShiftTy = getShiftAmountTy(VT, DAG.getDataLayout());
5260   Lo = DAG.getNode(ISD::SRL, dl, VT, Lo, DAG.getConstant(Scale, dl, ShiftTy));
5261   Hi = DAG.getNode(
5262       ISD::SHL, dl, VT, Hi,
5263       DAG.getConstant(VT.getScalarSizeInBits() - Scale, dl, ShiftTy));
5264   return DAG.getNode(ISD::OR, dl, VT, Lo, Hi);
5265 }