TargetLowering.cpp

Go to the documentation of this file.

//===-- TargetLowering.cpp - Implement the TargetLowering class -----------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This implements the TargetLowering class.
//
//===----------------------------------------------------------------------===//
 
#include "llvm/CodeGen/TargetLowering.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/CodeGen/CallingConvLower.h"
#include "llvm/CodeGen/CodeGenCommonISel.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineJumpTableInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/SelectionDAG.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/MC/MCAsmInfo.h"
#include "llvm/MC/MCExpr.h"
#include "llvm/Support/DivisionByConstantInfo.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/KnownBits.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Target/TargetMachine.h"
#include <cctype>
using namespace llvm;
 
/// NOTE: The TargetMachine owns TLOF.
TargetLowering::TargetLowering(const TargetMachine &tm)
    : TargetLoweringBase(tm) {}
 
const char *TargetLowering::getTargetNodeName(unsigned Opcode) const {
  return nullptr;
}
 
bool TargetLowering::isPositionIndependent() const {
  return getTargetMachine().isPositionIndependent();
}
 
/// Check whether a given call node is in tail position within its function. If
/// so, it sets Chain to the input chain of the tail call.
bool TargetLowering::isInTailCallPosition(SelectionDAG &DAG, SDNode *Node,
                                          SDValue &Chain) const {
  const Function &F = DAG.getMachineFunction().getFunction();
 
  // First, check if tail calls have been disabled in this function.
  if (F.getFnAttribute("disable-tail-calls").getValueAsBool())
    return false;
 
  // Conservatively require the attributes of the call to match those of
  // the return. Ignore following attributes because they don't affect the
  // call sequence.
  AttrBuilder CallerAttrs(F.getContext(), F.getAttributes().getRetAttrs());
  for (const auto &Attr : {Attribute::Alignment, Attribute::Dereferenceable,
                           Attribute::DereferenceableOrNull, Attribute::NoAlias,
                           Attribute::NonNull, Attribute::NoUndef})
    CallerAttrs.removeAttribute(Attr);
 
  if (CallerAttrs.hasAttributes())
    return false;
 
  // It's not safe to eliminate the sign / zero extension of the return value.
  if (CallerAttrs.contains(Attribute::ZExt) ||
      CallerAttrs.contains(Attribute::SExt))
    return false;
 
  // Check if the only use is a function return node.
  return isUsedByReturnOnly(Node, Chain);
}
 
bool TargetLowering::parametersInCSRMatch(const MachineRegisterInfo &MRI,
    const uint32_t *CallerPreservedMask,
    const SmallVectorImpl<CCValAssign> &ArgLocs,
    const SmallVectorImpl<SDValue> &OutVals) const {
  for (unsigned I = 0, E = ArgLocs.size(); I != E; ++I) {
    const CCValAssign &ArgLoc = ArgLocs[I];
    if (!ArgLoc.isRegLoc())
      continue;
    MCRegister Reg = ArgLoc.getLocReg();
    // Only look at callee saved registers.
    if (MachineOperand::clobbersPhysReg(CallerPreservedMask, Reg))
      continue;
    // Check that we pass the value used for the caller.
    // (We look for a CopyFromReg reading a virtual register that is used
    //  for the function live-in value of register Reg)
    SDValue Value = OutVals[I];
    if (Value->getOpcode() == ISD::AssertZext)
      Value = Value.getOperand(0);
    if (Value->getOpcode() != ISD::CopyFromReg)
      return false;
    Register ArgReg = cast<RegisterSDNode>(Value->getOperand(1))->getReg();
    if (MRI.getLiveInPhysReg(ArgReg) != Reg)
      return false;
  }
  return true;
}
 
/// Set CallLoweringInfo attribute flags based on a call instruction
/// and called function attributes.
void TargetLoweringBase::ArgListEntry::setAttributes(const CallBase *Call,
                                                     unsigned ArgIdx) {
  IsSExt = Call->paramHasAttr(ArgIdx, Attribute::SExt);
  IsZExt = Call->paramHasAttr(ArgIdx, Attribute::ZExt);
  IsInReg = Call->paramHasAttr(ArgIdx, Attribute::InReg);
  IsSRet = Call->paramHasAttr(ArgIdx, Attribute::StructRet);
  IsNest = Call->paramHasAttr(ArgIdx, Attribute::Nest);
  IsByVal = Call->paramHasAttr(ArgIdx, Attribute::ByVal);
  IsPreallocated = Call->paramHasAttr(ArgIdx, Attribute::Preallocated);
  IsInAlloca = Call->paramHasAttr(ArgIdx, Attribute::InAlloca);
  IsReturned = Call->paramHasAttr(ArgIdx, Attribute::Returned);
  IsSwiftSelf = Call->paramHasAttr(ArgIdx, Attribute::SwiftSelf);
  IsSwiftAsync = Call->paramHasAttr(ArgIdx, Attribute::SwiftAsync);
  IsSwiftError = Call->paramHasAttr(ArgIdx, Attribute::SwiftError);
  Alignment = Call->getParamStackAlign(ArgIdx);
  IndirectType = nullptr;
  assert(IsByVal + IsPreallocated + IsInAlloca + IsSRet <= 1 &&
         "multiple ABI attributes?");
  if (IsByVal) {
    IndirectType = Call->getParamByValType(ArgIdx);
    if (!Alignment)
      Alignment = Call->getParamAlign(ArgIdx);
  }
  if (IsPreallocated)
    IndirectType = Call->getParamPreallocatedType(ArgIdx);
  if (IsInAlloca)
    IndirectType = Call->getParamInAllocaType(ArgIdx);
  if (IsSRet)
    IndirectType = Call->getParamStructRetType(ArgIdx);
}
 
/// Generate a libcall taking the given operands as arguments and returning a
/// result of type RetVT.
std::pair<SDValue, SDValue>
TargetLowering::makeLibCall(SelectionDAG &DAG, RTLIB::Libcall LC, EVT RetVT,
                            ArrayRef<SDValue> Ops,
                            MakeLibCallOptions CallOptions,
                            const SDLoc &dl,
                            SDValue InChain) const {
  if (!InChain)
    InChain = DAG.getEntryNode();
 
  TargetLowering::ArgListTy Args;
  Args.reserve(Ops.size());
 
  TargetLowering::ArgListEntry Entry;
  for (unsigned i = 0; i < Ops.size(); ++i) {
    SDValue NewOp = Ops[i];
    Entry.Node = NewOp;
    Entry.Ty = Entry.Node.getValueType().getTypeForEVT(*DAG.getContext());
    Entry.IsSExt = shouldSignExtendTypeInLibCall(NewOp.getValueType(),
                                                 CallOptions.IsSExt);
    Entry.IsZExt = !Entry.IsSExt;
 
    if (CallOptions.IsSoften &&
        !shouldExtendTypeInLibCall(CallOptions.OpsVTBeforeSoften[i])) {
      Entry.IsSExt = Entry.IsZExt = false;
    }
    Args.push_back(Entry);
  }
 
  if (LC == RTLIB::UNKNOWN_LIBCALL)
    report_fatal_error("Unsupported library call operation!");
  SDValue Callee = DAG.getExternalSymbol(getLibcallName(LC),
                                         getPointerTy(DAG.getDataLayout()));
 
  Type *RetTy = RetVT.getTypeForEVT(*DAG.getContext());
  TargetLowering::CallLoweringInfo CLI(DAG);
  bool signExtend = shouldSignExtendTypeInLibCall(RetVT, CallOptions.IsSExt);
  bool zeroExtend = !signExtend;
 
  if (CallOptions.IsSoften &&
      !shouldExtendTypeInLibCall(CallOptions.RetVTBeforeSoften)) {
    signExtend = zeroExtend = false;
  }
 
  CLI.setDebugLoc(dl)
      .setChain(InChain)
      .setLibCallee(getLibcallCallingConv(LC), RetTy, Callee, std::move(Args))
      .setNoReturn(CallOptions.DoesNotReturn)
      .setDiscardResult(!CallOptions.IsReturnValueUsed)
      .setIsPostTypeLegalization(CallOptions.IsPostTypeLegalization)
      .setSExtResult(signExtend)
      .setZExtResult(zeroExtend);
  return LowerCallTo(CLI);
}
 
bool TargetLowering::findOptimalMemOpLowering(
    std::vector<EVT> &MemOps, unsigned Limit, const MemOp &Op, unsigned DstAS,
    unsigned SrcAS, const AttributeList &FuncAttributes) const {
  if (Limit != ~unsigned(0) && Op.isMemcpyWithFixedDstAlign() &&
      Op.getSrcAlign() < Op.getDstAlign())
    return false;
 
  EVT VT = getOptimalMemOpType(Op, FuncAttributes);
 
  if (VT == MVT::Other) {
    // Use the largest integer type whose alignment constraints are satisfied.
    // We only need to check DstAlign here as SrcAlign is always greater or
    // equal to DstAlign (or zero).
    VT = MVT::i64;
    if (Op.isFixedDstAlign())
      while (Op.getDstAlign() < (VT.getSizeInBits() / 8) &&
             !allowsMisalignedMemoryAccesses(VT, DstAS, Op.getDstAlign()))
        VT = (MVT::SimpleValueType)(VT.getSimpleVT().SimpleTy - 1);
    assert(VT.isInteger());
 
    // Find the largest legal integer type.
    MVT LVT = MVT::i64;
    while (!isTypeLegal(LVT))
      LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
    assert(LVT.isInteger());
 
    // If the type we've chosen is larger than the largest legal integer type
    // then use that instead.
    if (VT.bitsGT(LVT))
      VT = LVT;
  }
 
  unsigned NumMemOps = 0;
  uint64_t Size = Op.size();
  while (Size) {
    unsigned VTSize = VT.getSizeInBits() / 8;
    while (VTSize > Size) {
      // For now, only use non-vector load / store's for the left-over pieces.
      EVT NewVT = VT;
      unsigned NewVTSize;
 
      bool Found = false;
      if (VT.isVector() || VT.isFloatingPoint()) {
        NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
        if (isOperationLegalOrCustom(ISD::STORE, NewVT) &&
            isSafeMemOpType(NewVT.getSimpleVT()))
          Found = true;
        else if (NewVT == MVT::i64 &&
                 isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
                 isSafeMemOpType(MVT::f64)) {
          // i64 is usually not legal on 32-bit targets, but f64 may be.
          NewVT = MVT::f64;
          Found = true;
        }
      }
 
      if (!Found) {
        do {
          NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
          if (NewVT == MVT::i8)
            break;
        } while (!isSafeMemOpType(NewVT.getSimpleVT()));
      }
      NewVTSize = NewVT.getSizeInBits() / 8;
 
      // If the new VT cannot cover all of the remaining bits, then consider
      // issuing a (or a pair of) unaligned and overlapping load / store.
      bool Fast;
      if (NumMemOps && Op.allowOverlap() && NewVTSize < Size &&
          allowsMisalignedMemoryAccesses(
              VT, DstAS, Op.isFixedDstAlign() ? Op.getDstAlign() : Align(1),
              MachineMemOperand::MONone, &Fast) &&
          Fast)
        VTSize = Size;
      else {
        VT = NewVT;
        VTSize = NewVTSize;
      }
    }
 
    if (++NumMemOps > Limit)
      return false;
 
    MemOps.push_back(VT);
    Size -= VTSize;
  }
 
  return true;
}
 
/// Soften the operands of a comparison. This code is shared among BR_CC,
/// SELECT_CC, and SETCC handlers.
void TargetLowering::softenSetCCOperands(SelectionDAG &DAG, EVT VT,
                                         SDValue &NewLHS, SDValue &NewRHS,
                                         ISD::CondCode &CCCode,
                                         const SDLoc &dl, const SDValue OldLHS,
                                         const SDValue OldRHS) const {
  SDValue Chain;
  return softenSetCCOperands(DAG, VT, NewLHS, NewRHS, CCCode, dl, OldLHS,
                             OldRHS, Chain);
}
 
void TargetLowering::softenSetCCOperands(SelectionDAG &DAG, EVT VT,
                                         SDValue &NewLHS, SDValue &NewRHS,
                                         ISD::CondCode &CCCode,
                                         const SDLoc &dl, const SDValue OldLHS,
                                         const SDValue OldRHS,
                                         SDValue &Chain,
                                         bool IsSignaling) const {
  // FIXME: Currently we cannot really respect all IEEE predicates due to libgcc
  // not supporting it. We can update this code when libgcc provides such
  // functions.
 
  assert((VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128 || VT == MVT::ppcf128)
         && "Unsupported setcc type!");
 
  // Expand into one or more soft-fp libcall(s).
  RTLIB::Libcall LC1 = RTLIB::UNKNOWN_LIBCALL, LC2 = RTLIB::UNKNOWN_LIBCALL;
  bool ShouldInvertCC = false;
  switch (CCCode) {
  case ISD::SETEQ:
  case ISD::SETOEQ:
    LC1 = (VT == MVT::f32) ? RTLIB::OEQ_F32 :
          (VT == MVT::f64) ? RTLIB::OEQ_F64 :
          (VT == MVT::f128) ? RTLIB::OEQ_F128 : RTLIB::OEQ_PPCF128;
    break;
  case ISD::SETNE:
  case ISD::SETUNE:
    LC1 = (VT == MVT::f32) ? RTLIB::UNE_F32 :
          (VT == MVT::f64) ? RTLIB::UNE_F64 :
          (VT == MVT::f128) ? RTLIB::UNE_F128 : RTLIB::UNE_PPCF128;
    break;
  case ISD::SETGE:
  case ISD::SETOGE:
    LC1 = (VT == MVT::f32) ? RTLIB::OGE_F32 :
          (VT == MVT::f64) ? RTLIB::OGE_F64 :
          (VT == MVT::f128) ? RTLIB::OGE_F128 : RTLIB::OGE_PPCF128;
    break;
  case ISD::SETLT:
  case ISD::SETOLT:
    LC1 = (VT == MVT::f32) ? RTLIB::OLT_F32 :
          (VT == MVT::f64) ? RTLIB::OLT_F64 :
          (VT == MVT::f128) ? RTLIB::OLT_F128 : RTLIB::OLT_PPCF128;
    break;
  case ISD::SETLE:
  case ISD::SETOLE:
    LC1 = (VT == MVT::f32) ? RTLIB::OLE_F32 :
          (VT == MVT::f64) ? RTLIB::OLE_F64 :
          (VT == MVT::f128) ? RTLIB::OLE_F128 : RTLIB::OLE_PPCF128;
    break;
  case ISD::SETGT:
  case ISD::SETOGT:
    LC1 = (VT == MVT::f32) ? RTLIB::OGT_F32 :
          (VT == MVT::f64) ? RTLIB::OGT_F64 :
          (VT == MVT::f128) ? RTLIB::OGT_F128 : RTLIB::OGT_PPCF128;
    break;
  case ISD::SETO:
    ShouldInvertCC = true;
    [[fallthrough]];
  case ISD::SETUO:
    LC1 = (VT == MVT::f32) ? RTLIB::UO_F32 :
          (VT == MVT::f64) ? RTLIB::UO_F64 :
          (VT == MVT::f128) ? RTLIB::UO_F128 : RTLIB::UO_PPCF128;
    break;
  case ISD::SETONE:
    // SETONE = O && UNE
    ShouldInvertCC = true;
    [[fallthrough]];
  case ISD::SETUEQ:
    LC1 = (VT == MVT::f32) ? RTLIB::UO_F32 :
          (VT == MVT::f64) ? RTLIB::UO_F64 :
          (VT == MVT::f128) ? RTLIB::UO_F128 : RTLIB::UO_PPCF128;
    LC2 = (VT == MVT::f32) ? RTLIB::OEQ_F32 :
          (VT == MVT::f64) ? RTLIB::OEQ_F64 :
          (VT == MVT::f128) ? RTLIB::OEQ_F128 : RTLIB::OEQ_PPCF128;
    break;
  default:
    // Invert CC for unordered comparisons
    ShouldInvertCC = true;
    switch (CCCode) {
    case ISD::SETULT:
      LC1 = (VT == MVT::f32) ? RTLIB::OGE_F32 :
            (VT == MVT::f64) ? RTLIB::OGE_F64 :
            (VT == MVT::f128) ? RTLIB::OGE_F128 : RTLIB::OGE_PPCF128;
      break;
    case ISD::SETULE:
      LC1 = (VT == MVT::f32) ? RTLIB::OGT_F32 :
            (VT == MVT::f64) ? RTLIB::OGT_F64 :
            (VT == MVT::f128) ? RTLIB::OGT_F128 : RTLIB::OGT_PPCF128;
      break;
    case ISD::SETUGT:
      LC1 = (VT == MVT::f32) ? RTLIB::OLE_F32 :
            (VT == MVT::f64) ? RTLIB::OLE_F64 :
            (VT == MVT::f128) ? RTLIB::OLE_F128 : RTLIB::OLE_PPCF128;
      break;
    case ISD::SETUGE:
      LC1 = (VT == MVT::f32) ? RTLIB::OLT_F32 :
            (VT == MVT::f64) ? RTLIB::OLT_F64 :
            (VT == MVT::f128) ? RTLIB::OLT_F128 : RTLIB::OLT_PPCF128;
      break;
    default: llvm_unreachable("Do not know how to soften this setcc!");
    }
  }
 
  // Use the target specific return value for comparison lib calls.
  EVT RetVT = getCmpLibcallReturnType();
  SDValue Ops[2] = {NewLHS, NewRHS};
  TargetLowering::MakeLibCallOptions CallOptions;
  EVT OpsVT[2] = { OldLHS.getValueType(),
                   OldRHS.getValueType() };
  CallOptions.setTypeListBeforeSoften(OpsVT, RetVT, true);
  auto Call = makeLibCall(DAG, LC1, RetVT, Ops, CallOptions, dl, Chain);
  NewLHS = Call.first;
  NewRHS = DAG.getConstant(0, dl, RetVT);
 
  CCCode = getCmpLibcallCC(LC1);
  if (ShouldInvertCC) {
    assert(RetVT.isInteger());
    CCCode = getSetCCInverse(CCCode, RetVT);
  }
 
  if (LC2 == RTLIB::UNKNOWN_LIBCALL) {
    // Update Chain.
    Chain = Call.second;
  } else {
    EVT SetCCVT =
        getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), RetVT);
    SDValue Tmp = DAG.getSetCC(dl, SetCCVT, NewLHS, NewRHS, CCCode);
    auto Call2 = makeLibCall(DAG, LC2, RetVT, Ops, CallOptions, dl, Chain);
    CCCode = getCmpLibcallCC(LC2);
    if (ShouldInvertCC)
      CCCode = getSetCCInverse(CCCode, RetVT);
    NewLHS = DAG.getSetCC(dl, SetCCVT, Call2.first, NewRHS, CCCode);
    if (Chain)
      Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, Call.second,
                          Call2.second);
    NewLHS = DAG.getNode(ShouldInvertCC ? ISD::AND : ISD::OR, dl,
                         Tmp.getValueType(), Tmp, NewLHS);
    NewRHS = SDValue();
  }
}
 
/// Return the entry encoding for a jump table in the current function. The
/// returned value is a member of the MachineJumpTableInfo::JTEntryKind enum.
unsigned TargetLowering::getJumpTableEncoding() const {
  // In non-pic modes, just use the address of a block.
  if (!isPositionIndependent())
    return MachineJumpTableInfo::EK_BlockAddress;
 
  // In PIC mode, if the target supports a GPRel32 directive, use it.
  if (getTargetMachine().getMCAsmInfo()->getGPRel32Directive() != nullptr)
    return MachineJumpTableInfo::EK_GPRel32BlockAddress;
 
  // Otherwise, use a label difference.
  return MachineJumpTableInfo::EK_LabelDifference32;
}
 
SDValue TargetLowering::getPICJumpTableRelocBase(SDValue Table,
                                                 SelectionDAG &DAG) const {
  // If our PIC model is GP relative, use the global offset table as the base.
  unsigned JTEncoding = getJumpTableEncoding();
 
  if ((JTEncoding == MachineJumpTableInfo::EK_GPRel64BlockAddress) ||
      (JTEncoding == MachineJumpTableInfo::EK_GPRel32BlockAddress))
    return DAG.getGLOBAL_OFFSET_TABLE(getPointerTy(DAG.getDataLayout()));
 
  return Table;
}
 
/// This returns the relocation base for the given PIC jumptable, the same as
/// getPICJumpTableRelocBase, but as an MCExpr.
const MCExpr *
TargetLowering::getPICJumpTableRelocBaseExpr(const MachineFunction *MF,
                                             unsigned JTI,MCContext &Ctx) const{
  // The normal PIC reloc base is the label at the start of the jump table.
  return MCSymbolRefExpr::create(MF->getJTISymbol(JTI, Ctx), Ctx);
}
 
bool
TargetLowering::isOffsetFoldingLegal(const GlobalAddressSDNode *GA) const {
  const TargetMachine &TM = getTargetMachine();
  const GlobalValue *GV = GA->getGlobal();
 
  // If the address is not even local to this DSO we will have to load it from
  // a got and then add the offset.
  if (!TM.shouldAssumeDSOLocal(*GV->getParent(), GV))
    return false;
 
  // If the code is position independent we will have to add a base register.
  if (isPositionIndependent())
    return false;
 
  // Otherwise we can do it.
  return true;
}
 
//===----------------------------------------------------------------------===//
//  Optimization Methods
//===----------------------------------------------------------------------===//
 
/// If the specified instruction has a constant integer operand and there are
/// bits set in that constant that are not demanded, then clear those bits and
/// return true.
bool TargetLowering::ShrinkDemandedConstant(SDValue Op,
                                            const APInt &DemandedBits,
                                            const APInt &DemandedElts,
                                            TargetLoweringOpt &TLO) const {
  SDLoc DL(Op);
  unsigned Opcode = Op.getOpcode();
 
  // Do target-specific constant optimization.
  if (targetShrinkDemandedConstant(Op, DemandedBits, DemandedElts, TLO))
    return TLO.New.getNode();
 
  // FIXME: ISD::SELECT, ISD::SELECT_CC
  switch (Opcode) {
  default:
    break;
  case ISD::XOR:
  case ISD::AND:
  case ISD::OR: {
    auto *Op1C = dyn_cast<ConstantSDNode>(Op.getOperand(1));
    if (!Op1C || Op1C->isOpaque())
      return false;
 
    // If this is a 'not' op, don't touch it because that's a canonical form.
    const APInt &C = Op1C->getAPIntValue();
    if (Opcode == ISD::XOR && DemandedBits.isSubsetOf(C))
      return false;
 
    if (!C.isSubsetOf(DemandedBits)) {
      EVT VT = Op.getValueType();
      SDValue NewC = TLO.DAG.getConstant(DemandedBits & C, DL, VT);
      SDValue NewOp = TLO.DAG.getNode(Opcode, DL, VT, Op.getOperand(0), NewC);
      return TLO.CombineTo(Op, NewOp);
    }
 
    break;
  }
  }
 
  return false;
}
 
bool TargetLowering::ShrinkDemandedConstant(SDValue Op,
                                            const APInt &DemandedBits,
                                            TargetLoweringOpt &TLO) const {
  EVT VT = Op.getValueType();
  APInt DemandedElts = VT.isVector()
                           ? APInt::getAllOnes(VT.getVectorNumElements())
                           : APInt(1, 1);
  return ShrinkDemandedConstant(Op, DemandedBits, DemandedElts, TLO);
}
 
/// Convert x+y to (VT)((SmallVT)x+(SmallVT)y) if the casts are free.
/// This uses isZExtFree and ZERO_EXTEND for the widening cast, but it could be
/// generalized for targets with other types of implicit widening casts.
bool TargetLowering::ShrinkDemandedOp(SDValue Op, unsigned BitWidth,
                                      const APInt &Demanded,
                                      TargetLoweringOpt &TLO) const {
  assert(Op.getNumOperands() == 2 &&
         "ShrinkDemandedOp only supports binary operators!");
  assert(Op.getNode()->getNumValues() == 1 &&
         "ShrinkDemandedOp only supports nodes with one result!");
 
  SelectionDAG &DAG = TLO.DAG;
  SDLoc dl(Op);
 
  // Early return, as this function cannot handle vector types.
  if (Op.getValueType().isVector())
    return false;
 
  // Don't do this if the node has another user, which may require the
  // full value.
  if (!Op.getNode()->hasOneUse())
    return false;
 
  // Search for the smallest integer type with free casts to and from
  // Op's type. For expedience, just check power-of-2 integer types.
  const TargetLowering &TLI = DAG.getTargetLoweringInfo();
  unsigned DemandedSize = Demanded.getActiveBits();
  unsigned SmallVTBits = DemandedSize;
  if (!isPowerOf2_32(SmallVTBits))
    SmallVTBits = NextPowerOf2(SmallVTBits);
  for (; SmallVTBits < BitWidth; SmallVTBits = NextPowerOf2(SmallVTBits)) {
    EVT SmallVT = EVT::getIntegerVT(*DAG.getContext(), SmallVTBits);
    if (TLI.isTruncateFree(Op.getValueType(), SmallVT) &&
        TLI.isZExtFree(SmallVT, Op.getValueType())) {
      // We found a type with free casts.
      SDValue X = DAG.getNode(
          Op.getOpcode(), dl, SmallVT,
          DAG.getNode(ISD::TRUNCATE, dl, SmallVT, Op.getOperand(0)),
          DAG.getNode(ISD::TRUNCATE, dl, SmallVT, Op.getOperand(1)));
      assert(DemandedSize <= SmallVTBits && "Narrowed below demanded bits?");
      SDValue Z = DAG.getNode(ISD::ANY_EXTEND, dl, Op.getValueType(), X);
      return TLO.CombineTo(Op, Z);
    }
  }
  return false;
}
 
bool TargetLowering::SimplifyDemandedBits(SDValue Op, const APInt &DemandedBits,
                                          DAGCombinerInfo &DCI) const {
  SelectionDAG &DAG = DCI.DAG;
  TargetLoweringOpt TLO(DAG, !DCI.isBeforeLegalize(),
                        !DCI.isBeforeLegalizeOps());
  KnownBits Known;
 
  bool Simplified = SimplifyDemandedBits(Op, DemandedBits, Known, TLO);
  if (Simplified) {
    DCI.AddToWorklist(Op.getNode());
    DCI.CommitTargetLoweringOpt(TLO);
  }
  return Simplified;
}
 
bool TargetLowering::SimplifyDemandedBits(SDValue Op, const APInt &DemandedBits,
                                          const APInt &DemandedElts,
                                          DAGCombinerInfo &DCI) const {
  SelectionDAG &DAG = DCI.DAG;
  TargetLoweringOpt TLO(DAG, !DCI.isBeforeLegalize(),
                        !DCI.isBeforeLegalizeOps());
  KnownBits Known;
 
  bool Simplified =
      SimplifyDemandedBits(Op, DemandedBits, DemandedElts, Known, TLO);
  if (Simplified) {
    DCI.AddToWorklist(Op.getNode());
    DCI.CommitTargetLoweringOpt(TLO);
  }
  return Simplified;
}
 
bool TargetLowering::SimplifyDemandedBits(SDValue Op, const APInt &DemandedBits,
                                          KnownBits &Known,
                                          TargetLoweringOpt &TLO,
                                          unsigned Depth,
                                          bool AssumeSingleUse) const {
  EVT VT = Op.getValueType();
 
  // TODO: We can probably do more work on calculating the known bits and
  // simplifying the operations for scalable vectors, but for now we just
  // bail out.
  if (VT.isScalableVector()) {
    // Pretend we don't know anything for now.
    Known = KnownBits(DemandedBits.getBitWidth());
    return false;
  }
 
  APInt DemandedElts = VT.isVector()
                           ? APInt::getAllOnes(VT.getVectorNumElements())
                           : APInt(1, 1);
  return SimplifyDemandedBits(Op, DemandedBits, DemandedElts, Known, TLO, Depth,
                              AssumeSingleUse);
}
 
// TODO: Under what circumstances can we create nodes? Constant folding?
SDValue TargetLowering::SimplifyMultipleUseDemandedBits(
    SDValue Op, const APInt &DemandedBits, const APInt &DemandedElts,
    SelectionDAG &DAG, unsigned Depth) const {
  EVT VT = Op.getValueType();
 
  // Pretend we don't know anything about scalable vectors for now.
  // TODO: We can probably do more work on simplifying the operations for
  // scalable vectors, but for now we just bail out.
  if (VT.isScalableVector())
    return SDValue();
 
  // Limit search depth.
  if (Depth >= SelectionDAG::MaxRecursionDepth)
    return SDValue();
 
  // Ignore UNDEFs.
  if (Op.isUndef())
    return SDValue();
 
  // Not demanding any bits/elts from Op.
  if (DemandedBits == 0 || DemandedElts == 0)
    return DAG.getUNDEF(VT);
 
  bool IsLE = DAG.getDataLayout().isLittleEndian();
  unsigned NumElts = DemandedElts.getBitWidth();
  unsigned BitWidth = DemandedBits.getBitWidth();
  KnownBits LHSKnown, RHSKnown;
  switch (Op.getOpcode()) {
  case ISD::BITCAST: {
    SDValue Src = peekThroughBitcasts(Op.getOperand(0));
    EVT SrcVT = Src.getValueType();
    EVT DstVT = Op.getValueType();
    if (SrcVT == DstVT)
      return Src;
 
    unsigned NumSrcEltBits = SrcVT.getScalarSizeInBits();
    unsigned NumDstEltBits = DstVT.getScalarSizeInBits();
    if (NumSrcEltBits == NumDstEltBits)
      if (SDValue V = SimplifyMultipleUseDemandedBits(
              Src, DemandedBits, DemandedElts, DAG, Depth + 1))
        return DAG.getBitcast(DstVT, V);
 
    if (SrcVT.isVector() && (NumDstEltBits % NumSrcEltBits) == 0) {
      unsigned Scale = NumDstEltBits / NumSrcEltBits;
      unsigned NumSrcElts = SrcVT.getVectorNumElements();
      APInt DemandedSrcBits = APInt::getZero(NumSrcEltBits);
      APInt DemandedSrcElts = APInt::getZero(NumSrcElts);
      for (unsigned i = 0; i != Scale; ++i) {
        unsigned EltOffset = IsLE ? i : (Scale - 1 - i);
        unsigned BitOffset = EltOffset * NumSrcEltBits;
        APInt Sub = DemandedBits.extractBits(NumSrcEltBits, BitOffset);
        if (!Sub.isZero()) {
          DemandedSrcBits |= Sub;
          for (unsigned j = 0; j != NumElts; ++j)
            if (DemandedElts[j])
              DemandedSrcElts.setBit((j * Scale) + i);
        }
      }
 
      if (SDValue V = SimplifyMultipleUseDemandedBits(
              Src, DemandedSrcBits, DemandedSrcElts, DAG, Depth + 1))
        return DAG.getBitcast(DstVT, V);
    }
 
    // TODO - bigendian once we have test coverage.
    if (IsLE && (NumSrcEltBits % NumDstEltBits) == 0) {
      unsigned Scale = NumSrcEltBits / NumDstEltBits;
      unsigned NumSrcElts = SrcVT.isVector() ? SrcVT.getVectorNumElements() : 1;
      APInt DemandedSrcBits = APInt::getZero(NumSrcEltBits);
      APInt DemandedSrcElts = APInt::getZero(NumSrcElts);
      for (unsigned i = 0; i != NumElts; ++i)
        if (DemandedElts[i]) {
          unsigned Offset = (i % Scale) * NumDstEltBits;
          DemandedSrcBits.insertBits(DemandedBits, Offset);
          DemandedSrcElts.setBit(i / Scale);
        }
 
      if (SDValue V = SimplifyMultipleUseDemandedBits(
              Src, DemandedSrcBits, DemandedSrcElts, DAG, Depth + 1))
        return DAG.getBitcast(DstVT, V);
    }
 
    break;
  }
  case ISD::AND: {
    LHSKnown = DAG.computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
    RHSKnown = DAG.computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
 
    // If all of the demanded bits are known 1 on one side, return the other.
    // These bits cannot contribute to the result of the 'and' in this
    // context.
    if (DemandedBits.isSubsetOf(LHSKnown.Zero | RHSKnown.One))
      return Op.getOperand(0);
    if (DemandedBits.isSubsetOf(RHSKnown.Zero | LHSKnown.One))
      return Op.getOperand(1);
    break;
  }
  case ISD::OR: {
    LHSKnown = DAG.computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
    RHSKnown = DAG.computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
 
    // If all of the demanded bits are known zero on one side, return the
    // other.  These bits cannot contribute to the result of the 'or' in this
    // context.
    if (DemandedBits.isSubsetOf(LHSKnown.One | RHSKnown.Zero))
      return Op.getOperand(0);
    if (DemandedBits.isSubsetOf(RHSKnown.One | LHSKnown.Zero))
      return Op.getOperand(1);
    break;
  }
  case ISD::XOR: {
    LHSKnown = DAG.computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
    RHSKnown = DAG.computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
 
    // If all of the demanded bits are known zero on one side, return the
    // other.
    if (DemandedBits.isSubsetOf(RHSKnown.Zero))
      return Op.getOperand(0);
    if (DemandedBits.isSubsetOf(LHSKnown.Zero))
      return Op.getOperand(1);
    break;
  }
  case ISD::SHL: {
    // If we are only demanding sign bits then we can use the shift source
    // directly.
    if (const APInt *MaxSA =
            DAG.getValidMaximumShiftAmountConstant(Op, DemandedElts)) {
      SDValue Op0 = Op.getOperand(0);
      unsigned ShAmt = MaxSA->getZExtValue();
      unsigned NumSignBits =
          DAG.ComputeNumSignBits(Op0, DemandedElts, Depth + 1);
      unsigned UpperDemandedBits = BitWidth - DemandedBits.countTrailingZeros();
      if (NumSignBits > ShAmt && (NumSignBits - ShAmt) >= (UpperDemandedBits))
        return Op0;
    }
    break;
  }
  case ISD::SETCC: {
    SDValue Op0 = Op.getOperand(0);
    SDValue Op1 = Op.getOperand(1);
    ISD::CondCode CC = cast<CondCodeSDNode>(Op.getOperand(2))->get();
    // If (1) we only need the sign-bit, (2) the setcc operands are the same
    // width as the setcc result, and (3) the result of a setcc conforms to 0 or
    // -1, we may be able to bypass the setcc.
    if (DemandedBits.isSignMask() &&
        Op0.getScalarValueSizeInBits() == BitWidth &&
        getBooleanContents(Op0.getValueType()) ==
            BooleanContent::ZeroOrNegativeOneBooleanContent) {
      // If we're testing X < 0, then this compare isn't needed - just use X!
      // FIXME: We're limiting to integer types here, but this should also work
      // if we don't care about FP signed-zero. The use of SETLT with FP means
      // that we don't care about NaNs.
      if (CC == ISD::SETLT && Op1.getValueType().isInteger() &&
          (isNullConstant(Op1) || ISD::isBuildVectorAllZeros(Op1.getNode())))
        return Op0;
    }
    break;
  }
  case ISD::SIGN_EXTEND_INREG: {
    // If none of the extended bits are demanded, eliminate the sextinreg.
    SDValue Op0 = Op.getOperand(0);
    EVT ExVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
    unsigned ExBits = ExVT.getScalarSizeInBits();
    if (DemandedBits.getActiveBits() <= ExBits)
      return Op0;
    // If the input is already sign extended, just drop the extension.
    unsigned NumSignBits = DAG.ComputeNumSignBits(Op0, DemandedElts, Depth + 1);
    if (NumSignBits >= (BitWidth - ExBits + 1))
      return Op0;
    break;
  }
  case ISD::ANY_EXTEND_VECTOR_INREG:
  case ISD::SIGN_EXTEND_VECTOR_INREG:
  case ISD::ZERO_EXTEND_VECTOR_INREG: {
    // If we only want the lowest element and none of extended bits, then we can
    // return the bitcasted source vector.
    SDValue Src = Op.getOperand(0);
    EVT SrcVT = Src.getValueType();
    EVT DstVT = Op.getValueType();
    if (IsLE && DemandedElts == 1 &&
        DstVT.getSizeInBits() == SrcVT.getSizeInBits() &&
        DemandedBits.getActiveBits() <= SrcVT.getScalarSizeInBits()) {
      return DAG.getBitcast(DstVT, Src);
    }
    break;
  }
  case ISD::INSERT_VECTOR_ELT: {
    // If we don't demand the inserted element, return the base vector.
    SDValue Vec = Op.getOperand(0);
    auto *CIdx = dyn_cast<ConstantSDNode>(Op.getOperand(2));
    EVT VecVT = Vec.getValueType();
    if (CIdx && CIdx->getAPIntValue().ult(VecVT.getVectorNumElements()) &&
        !DemandedElts[CIdx->getZExtValue()])
      return Vec;
    break;
  }
  case ISD::INSERT_SUBVECTOR: {
    SDValue Vec = Op.getOperand(0);
    SDValue Sub = Op.getOperand(1);
    uint64_t Idx = Op.getConstantOperandVal(2);
    unsigned NumSubElts = Sub.getValueType().getVectorNumElements();
    APInt DemandedSubElts = DemandedElts.extractBits(NumSubElts, Idx);
    // If we don't demand the inserted subvector, return the base vector.
    if (DemandedSubElts == 0)
      return Vec;
    // If this simply widens the lowest subvector, see if we can do it earlier.
    // TODO: REMOVE ME - SimplifyMultipleUseDemandedBits shouldn't be creating
    // general nodes like this.
    if (Idx == 0 && Vec.isUndef()) {
      if (SDValue NewSub = SimplifyMultipleUseDemandedBits(
              Sub, DemandedBits, DemandedSubElts, DAG, Depth + 1))
        return DAG.getNode(Op.getOpcode(), SDLoc(Op), Op.getValueType(),
                           Op.getOperand(0), NewSub, Op.getOperand(2));
    }
    break;
  }
  case ISD::VECTOR_SHUFFLE: {
    ArrayRef<int> ShuffleMask = cast<ShuffleVectorSDNode>(Op)->getMask();
 
    // If all the demanded elts are from one operand and are inline,
    // then we can use the operand directly.
    bool AllUndef = true, IdentityLHS = true, IdentityRHS = true;
    for (unsigned i = 0; i != NumElts; ++i) {
      int M = ShuffleMask[i];
      if (M < 0 || !DemandedElts[i])
        continue;
      AllUndef = false;
      IdentityLHS &= (M == (int)i);
      IdentityRHS &= ((M - NumElts) == i);
    }
 
    if (AllUndef)
      return DAG.getUNDEF(Op.getValueType());
    if (IdentityLHS)
      return Op.getOperand(0);
    if (IdentityRHS)
      return Op.getOperand(1);
    break;
  }
  default:
    if (Op.getOpcode() >= ISD::BUILTIN_OP_END)
      if (SDValue V = SimplifyMultipleUseDemandedBitsForTargetNode(
              Op, DemandedBits, DemandedElts, DAG, Depth))
        return V;
    break;
  }
  return SDValue();
}
 
SDValue TargetLowering::SimplifyMultipleUseDemandedBits(
    SDValue Op, const APInt &DemandedBits, SelectionDAG &DAG,
    unsigned Depth) const {
  EVT VT = Op.getValueType();
 
  // Pretend we don't know anything about scalable vectors for now.
  // TODO: We can probably do more work on simplifying the operations for
  // scalable vectors, but for now we just bail out.
  if (VT.isScalableVector())
    return SDValue();
 
  APInt DemandedElts = VT.isVector()
                           ? APInt::getAllOnes(VT.getVectorNumElements())
                           : APInt(1, 1);
  return SimplifyMultipleUseDemandedBits(Op, DemandedBits, DemandedElts, DAG,
                                         Depth);
}
 
SDValue TargetLowering::SimplifyMultipleUseDemandedVectorElts(
    SDValue Op, const APInt &DemandedElts, SelectionDAG &DAG,
    unsigned Depth) const {
  APInt DemandedBits = APInt::getAllOnes(Op.getScalarValueSizeInBits());
  return SimplifyMultipleUseDemandedBits(Op, DemandedBits, DemandedElts, DAG,
                                         Depth);
}
 
// Attempt to form ext(avgfloor(A, B)) from shr(add(ext(A), ext(B)), 1).
//      or to form ext(avgceil(A, B)) from shr(add(ext(A), ext(B), 1), 1).
static SDValue combineShiftToAVG(SDValue Op, SelectionDAG &DAG,
                                 const TargetLowering &TLI,
                                 const APInt &DemandedBits,
                                 const APInt &DemandedElts,
                                 unsigned Depth) {
  assert((Op.getOpcode() == ISD::SRL || Op.getOpcode() == ISD::SRA) &&
         "SRL or SRA node is required here!");
  // Is the right shift using an immediate value of 1?
  ConstantSDNode *N1C = isConstOrConstSplat(Op.getOperand(1), DemandedElts);
  if (!N1C || !N1C->isOne())
    return SDValue();
 
  // We are looking for an avgfloor
  // add(ext, ext)
  // or one of these as a avgceil
  // add(add(ext, ext), 1)
  // add(add(ext, 1), ext)
  // add(ext, add(ext, 1))
  SDValue Add = Op.getOperand(0);
  if (Add.getOpcode() != ISD::ADD)
    return SDValue();
 
  SDValue ExtOpA = Add.getOperand(0);
  SDValue ExtOpB = Add.getOperand(1);
  auto MatchOperands = [&](SDValue Op1, SDValue Op2, SDValue Op3) {
    ConstantSDNode *ConstOp;
    if ((ConstOp = isConstOrConstSplat(Op1, DemandedElts)) &&
        ConstOp->isOne()) {
      ExtOpA = Op2;
      ExtOpB = Op3;
      return true;
    }
    if ((ConstOp = isConstOrConstSplat(Op2, DemandedElts)) &&
        ConstOp->isOne()) {
      ExtOpA = Op1;
      ExtOpB = Op3;
      return true;
    }
    if ((ConstOp = isConstOrConstSplat(Op3, DemandedElts)) &&
        ConstOp->isOne()) {
      ExtOpA = Op1;
      ExtOpB = Op2;
      return true;
    }
    return false;
  };
  bool IsCeil =
      (ExtOpA.getOpcode() == ISD::ADD &&
       MatchOperands(ExtOpA.getOperand(0), ExtOpA.getOperand(1), ExtOpB)) ||
      (ExtOpB.getOpcode() == ISD::ADD &&
       MatchOperands(ExtOpB.getOperand(0), ExtOpB.getOperand(1), ExtOpA));
 
  // If the shift is signed (sra):
  //  - Needs >= 2 sign bit for both operands.
  //  - Needs >= 2 zero bits.
  // If the shift is unsigned (srl):
  //  - Needs >= 1 zero bit for both operands.
  //  - Needs 1 demanded bit zero and >= 2 sign bits.
  unsigned ShiftOpc = Op.getOpcode();
  bool IsSigned = false;
  unsigned KnownBits;
  unsigned NumSignedA = DAG.ComputeNumSignBits(ExtOpA, DemandedElts, Depth);
  unsigned NumSignedB = DAG.ComputeNumSignBits(ExtOpB, DemandedElts, Depth);
  unsigned NumSigned = std::min(NumSignedA, NumSignedB) - 1;
  unsigned NumZeroA =
      DAG.computeKnownBits(ExtOpA, DemandedElts, Depth).countMinLeadingZeros();
  unsigned NumZeroB =
      DAG.computeKnownBits(ExtOpB, DemandedElts, Depth).countMinLeadingZeros();
  unsigned NumZero = std::min(NumZeroA, NumZeroB);
 
  switch (ShiftOpc) {
  default:
    llvm_unreachable("Unexpected ShiftOpc in combineShiftToAVG");
  case ISD::SRA: {
    if (NumZero >= 2 && NumSigned < NumZero) {
      IsSigned = false;
      KnownBits = NumZero;
      break;
    }
    if (NumSigned >= 1) {
      IsSigned = true;
      KnownBits = NumSigned;
      break;
    }
    return SDValue();
  }
  case ISD::SRL: {
    if (NumZero >= 1 && NumSigned < NumZero) {
      IsSigned = false;
      KnownBits = NumZero;
      break;
    }
    if (NumSigned >= 1 && DemandedBits.isSignBitClear()) {
      IsSigned = true;
      KnownBits = NumSigned;
      break;
    }
    return SDValue();
  }
  }
 
  unsigned AVGOpc = IsCeil ? (IsSigned ? ISD::AVGCEILS : ISD::AVGCEILU)
                           : (IsSigned ? ISD::AVGFLOORS : ISD::AVGFLOORU);
 
  // Find the smallest power-2 type that is legal for this vector size and
  // operation, given the original type size and the number of known sign/zero
  // bits.
  EVT VT = Op.getValueType();
  unsigned MinWidth =
      std::max<unsigned>(VT.getScalarSizeInBits() - KnownBits, 8);
  EVT NVT = EVT::getIntegerVT(*DAG.getContext(), PowerOf2Ceil(MinWidth));
  if (VT.isVector())
    NVT = EVT::getVectorVT(*DAG.getContext(), NVT, VT.getVectorElementCount());
  if (!TLI.isOperationLegalOrCustom(AVGOpc, NVT))
    return SDValue();
 
  SDLoc DL(Op);
  SDValue ResultAVG =
      DAG.getNode(AVGOpc, DL, NVT, DAG.getNode(ISD::TRUNCATE, DL, NVT, ExtOpA),
                  DAG.getNode(ISD::TRUNCATE, DL, NVT, ExtOpB));
  return DAG.getNode(IsSigned ? ISD::SIGN_EXTEND : ISD::ZERO_EXTEND, DL, VT,
                     ResultAVG);
}
 
/// Look at Op. At this point, we know that only the OriginalDemandedBits of the
/// result of Op are ever used downstream. If we can use this information to
/// simplify Op, create a new simplified DAG node and return true, returning the
/// original and new nodes in Old and New. Otherwise, analyze the expression and
/// return a mask of Known bits for the expression (used to simplify the
/// caller).  The Known bits may only be accurate for those bits in the
/// OriginalDemandedBits and OriginalDemandedElts.
bool TargetLowering::SimplifyDemandedBits(
    SDValue Op, const APInt &OriginalDemandedBits,
    const APInt &OriginalDemandedElts, KnownBits &Known, TargetLoweringOpt &TLO,
    unsigned Depth, bool AssumeSingleUse) const {
  unsigned BitWidth = OriginalDemandedBits.getBitWidth();
  assert(Op.getScalarValueSizeInBits() == BitWidth &&
         "Mask size mismatches value type size!");
 
  // Don't know anything.
  Known = KnownBits(BitWidth);
 
  // TODO: We can probably do more work on calculating the known bits and
  // simplifying the operations for scalable vectors, but for now we just
  // bail out.
  EVT VT = Op.getValueType();
  if (VT.isScalableVector())
    return false;
 
  bool IsLE = TLO.DAG.getDataLayout().isLittleEndian();
  unsigned NumElts = OriginalDemandedElts.getBitWidth();
  assert((!VT.isVector() || NumElts == VT.getVectorNumElements()) &&
         "Unexpected vector size");
 
  APInt DemandedBits = OriginalDemandedBits;
  APInt DemandedElts = OriginalDemandedElts;
  SDLoc dl(Op);
  auto &DL = TLO.DAG.getDataLayout();
 
  // Undef operand.
  if (Op.isUndef())
    return false;
 
  // We can't simplify target constants.
  if (Op.getOpcode() == ISD::TargetConstant)
    return false;
 
  if (Op.getOpcode() == ISD::Constant) {
    // We know all of the bits for a constant!
    Known = KnownBits::makeConstant(cast<ConstantSDNode>(Op)->getAPIntValue());
    return false;
  }
 
  if (Op.getOpcode() == ISD::ConstantFP) {
    // We know all of the bits for a floating point constant!
    Known = KnownBits::makeConstant(
        cast<ConstantFPSDNode>(Op)->getValueAPF().bitcastToAPInt());
    return false;
  }
 
  // Other users may use these bits.
  bool HasMultiUse = false;
  if (!AssumeSingleUse && !Op.getNode()->hasOneUse()) {
    if (Depth >= SelectionDAG::MaxRecursionDepth) {
      // Limit search depth.
      return false;
    }
    // Allow multiple uses, just set the DemandedBits/Elts to all bits.
    DemandedBits = APInt::getAllOnes(BitWidth);
    DemandedElts = APInt::getAllOnes(NumElts);
    HasMultiUse = true;
  } else if (OriginalDemandedBits == 0 || OriginalDemandedElts == 0) {
    // Not demanding any bits/elts from Op.
    return TLO.CombineTo(Op, TLO.DAG.getUNDEF(VT));
  } else if (Depth >= SelectionDAG::MaxRecursionDepth) {
    // Limit search depth.
    return false;
  }
 
  KnownBits Known2;
  switch (Op.getOpcode()) {
  case ISD::SCALAR_TO_VECTOR: {
    if (!DemandedElts[0])
      return TLO.CombineTo(Op, TLO.DAG.getUNDEF(VT));
 
    KnownBits SrcKnown;
    SDValue Src = Op.getOperand(0);
    unsigned SrcBitWidth = Src.getScalarValueSizeInBits();
    APInt SrcDemandedBits = DemandedBits.zext(SrcBitWidth);
    if (SimplifyDemandedBits(Src, SrcDemandedBits, SrcKnown, TLO, Depth + 1))
      return true;
 
    // Upper elements are undef, so only get the knownbits if we just demand
    // the bottom element.
    if (DemandedElts == 1)
      Known = SrcKnown.anyextOrTrunc(BitWidth);
    break;
  }
  case ISD::BUILD_VECTOR:
    // Collect the known bits that are shared by every demanded element.
    // TODO: Call SimplifyDemandedBits for non-constant demanded elements.
    Known = TLO.DAG.computeKnownBits(Op, DemandedElts, Depth);
    return false; // Don't fall through, will infinitely loop.
  case ISD::LOAD: {
    auto *LD = cast<LoadSDNode>(Op);
    if (getTargetConstantFromLoad(LD)) {
      Known = TLO.DAG.computeKnownBits(Op, DemandedElts, Depth);
      return false; // Don't fall through, will infinitely loop.
    }
    if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
      // If this is a ZEXTLoad and we are looking at the loaded value.
      EVT MemVT = LD->getMemoryVT();
      unsigned MemBits = MemVT.getScalarSizeInBits();
      Known.Zero.setBitsFrom(MemBits);
      return false; // Don't fall through, will infinitely loop.
    }
    break;
  }
  case ISD::INSERT_VECTOR_ELT: {
    SDValue Vec = Op.getOperand(0);
    SDValue Scl = Op.getOperand(1);
    auto *CIdx = dyn_cast<ConstantSDNode>(Op.getOperand(2));
    EVT VecVT = Vec.getValueType();
 
    // If index isn't constant, assume we need all vector elements AND the
    // inserted element.
    APInt DemandedVecElts(DemandedElts);
    if (CIdx && CIdx->getAPIntValue().ult(VecVT.getVectorNumElements())) {
      unsigned Idx = CIdx->getZExtValue();
      DemandedVecElts.clearBit(Idx);
 
      // Inserted element is not required.
      if (!DemandedElts[Idx])
        return TLO.CombineTo(Op, Vec);
    }
 
    KnownBits KnownScl;
    unsigned NumSclBits = Scl.getScalarValueSizeInBits();
    APInt DemandedSclBits = DemandedBits.zextOrTrunc(NumSclBits);
    if (SimplifyDemandedBits(Scl, DemandedSclBits, KnownScl, TLO, Depth + 1))
      return true;
 
    Known = KnownScl.anyextOrTrunc(BitWidth);
 
    KnownBits KnownVec;
    if (SimplifyDemandedBits(Vec, DemandedBits, DemandedVecElts, KnownVec, TLO,
                             Depth + 1))
      return true;
 
    if (!!DemandedVecElts)
      Known = KnownBits::commonBits(Known, KnownVec);
 
    return false;
  }
  case ISD::INSERT_SUBVECTOR: {
    // Demand any elements from the subvector and the remainder from the src its
    // inserted into.
    SDValue Src = Op.getOperand(0);
    SDValue Sub = Op.getOperand(1);
    uint64_t Idx = Op.getConstantOperandVal(2);
    unsigned NumSubElts = Sub.getValueType().getVectorNumElements();
    APInt DemandedSubElts = DemandedElts.extractBits(NumSubElts, Idx);
    APInt DemandedSrcElts = DemandedElts;
    DemandedSrcElts.insertBits(APInt::getZero(NumSubElts), Idx);
 
    KnownBits KnownSub, KnownSrc;
    if (SimplifyDemandedBits(Sub, DemandedBits, DemandedSubElts, KnownSub, TLO,
                             Depth + 1))
      return true;
    if (SimplifyDemandedBits(Src, DemandedBits, DemandedSrcElts, KnownSrc, TLO,
                             Depth + 1))
      return true;
 
    Known.Zero.setAllBits();
    Known.One.setAllBits();
    if (!!DemandedSubElts)
      Known = KnownBits::commonBits(Known, KnownSub);
    if (!!DemandedSrcElts)
      Known = KnownBits::commonBits(Known, KnownSrc);
 
    // Attempt to avoid multi-use src if we don't need anything from it.
    if (!DemandedBits.isAllOnes() || !DemandedSubElts.isAllOnes() ||
        !DemandedSrcElts.isAllOnes()) {
      SDValue NewSub = SimplifyMultipleUseDemandedBits(
          Sub, DemandedBits, DemandedSubElts, TLO.DAG, Depth + 1);
      SDValue NewSrc = SimplifyMultipleUseDemandedBits(
          Src, DemandedBits, DemandedSrcElts, TLO.DAG, Depth + 1);
      if (NewSub || NewSrc) {
        NewSub = NewSub ? NewSub : Sub;
        NewSrc = NewSrc ? NewSrc : Src;
        SDValue NewOp = TLO.DAG.getNode(Op.getOpcode(), dl, VT, NewSrc, NewSub,
                                        Op.getOperand(2));
        return TLO.CombineTo(Op, NewOp);
      }
    }
    break;
  }
  case ISD::EXTRACT_SUBVECTOR: {
    // Offset the demanded elts by the subvector index.
    SDValue Src = Op.getOperand(0);
    if (Src.getValueType().isScalableVector())
      break;
    uint64_t Idx = Op.getConstantOperandVal(1);
    unsigned NumSrcElts = Src.getValueType().getVectorNumElements();
    APInt DemandedSrcElts = DemandedElts.zext(NumSrcElts).shl(Idx);
 
    if (SimplifyDemandedBits(Src, DemandedBits, DemandedSrcElts, Known, TLO,
                             Depth + 1))
      return true;
 
    // Attempt to avoid multi-use src if we don't need anything from it.
    if (!DemandedBits.isAllOnes() || !DemandedSrcElts.isAllOnes()) {
      SDValue DemandedSrc = SimplifyMultipleUseDemandedBits(
          Src, DemandedBits, DemandedSrcElts, TLO.DAG, Depth + 1);
      if (DemandedSrc) {
        SDValue NewOp = TLO.DAG.getNode(Op.getOpcode(), dl, VT, DemandedSrc,
                                        Op.getOperand(1));
        return TLO.CombineTo(Op, NewOp);
      }
    }
    break;
  }
  case ISD::CONCAT_VECTORS: {
    Known.Zero.setAllBits();
    Known.One.setAllBits();
    EVT SubVT = Op.getOperand(0).getValueType();
    unsigned NumSubVecs = Op.getNumOperands();
    unsigned NumSubElts = SubVT.getVectorNumElements();
    for (unsigned i = 0; i != NumSubVecs; ++i) {
      APInt DemandedSubElts =
          DemandedElts.extractBits(NumSubElts, i * NumSubElts);
      if (SimplifyDemandedBits(Op.getOperand(i), DemandedBits, DemandedSubElts,
                               Known2, TLO, Depth + 1))
        return true;
      // Known bits are shared by every demanded subvector element.
      if (!!DemandedSubElts)
        Known = KnownBits::commonBits(Known, Known2);
    }
    break;
  }
  case ISD::VECTOR_SHUFFLE: {
    ArrayRef<int> ShuffleMask = cast<ShuffleVectorSDNode>(Op)->getMask();
 
    // Collect demanded elements from shuffle operands..
    APInt DemandedLHS(NumElts, 0);
    APInt DemandedRHS(NumElts, 0);
    for (unsigned i = 0; i != NumElts; ++i) {
      if (!DemandedElts[i])
        continue;
      int M = ShuffleMask[i];
      if (M < 0) {
        // For UNDEF elements, we don't know anything about the common state of
        // the shuffle result.
        DemandedLHS.clearAllBits();
        DemandedRHS.clearAllBits();
        break;
      }
      assert(0 <= M && M < (int)(2 * NumElts) && "Shuffle index out of range");
      if (M < (int)NumElts)
        DemandedLHS.setBit(M);
      else
        DemandedRHS.setBit(M - NumElts);
    }
 
    if (!!DemandedLHS || !!DemandedRHS) {
      SDValue Op0 = Op.getOperand(0);
      SDValue Op1 = Op.getOperand(1);
 
      Known.Zero.setAllBits();
      Known.One.setAllBits();
      if (!!DemandedLHS) {
        if (SimplifyDemandedBits(Op0, DemandedBits, DemandedLHS, Known2, TLO,
                                 Depth + 1))
          return true;
        Known = KnownBits::commonBits(Known, Known2);
      }
      if (!!DemandedRHS) {
        if (SimplifyDemandedBits(Op1, DemandedBits, DemandedRHS, Known2, TLO,
                                 Depth + 1))
          return true;
        Known = KnownBits::commonBits(Known, Known2);
      }
 
      // Attempt to avoid multi-use ops if we don't need anything from them.
      SDValue DemandedOp0 = SimplifyMultipleUseDemandedBits(
          Op0, DemandedBits, DemandedLHS, TLO.DAG, Depth + 1);
      SDValue DemandedOp1 = SimplifyMultipleUseDemandedBits(
          Op1, DemandedBits, DemandedRHS, TLO.DAG, Depth + 1);
      if (DemandedOp0 || DemandedOp1) {
        Op0 = DemandedOp0 ? DemandedOp0 : Op0;
        Op1 = DemandedOp1 ? DemandedOp1 : Op1;
        SDValue NewOp = TLO.DAG.getVectorShuffle(VT, dl, Op0, Op1, ShuffleMask);
        return TLO.CombineTo(Op, NewOp);
      }
    }
    break;
  }
  case ISD::AND: {
    SDValue Op0 = Op.getOperand(0);
    SDValue Op1 = Op.getOperand(1);
 
    // If the RHS is a constant, check to see if the LHS would be zero without
    // using the bits from the RHS.  Below, we use knowledge about the RHS to
    // simplify the LHS, here we're using information from the LHS to simplify
    // the RHS.
    if (ConstantSDNode *RHSC = isConstOrConstSplat(Op1)) {
      // Do not increment Depth here; that can cause an infinite loop.
      KnownBits LHSKnown = TLO.DAG.computeKnownBits(Op0, DemandedElts, Depth);
      // If the LHS already has zeros where RHSC does, this 'and' is dead.
      if ((LHSKnown.Zero & DemandedBits) ==
          (~RHSC->getAPIntValue() & DemandedBits))
        return TLO.CombineTo(Op, Op0);
 
      // If any of the set bits in the RHS are known zero on the LHS, shrink
      // the constant.
      if (ShrinkDemandedConstant(Op, ~LHSKnown.Zero & DemandedBits,
                                 DemandedElts, TLO))
        return true;
 
      // Bitwise-not (xor X, -1) is a special case: we don't usually shrink its
      // constant, but if this 'and' is only clearing bits that were just set by
      // the xor, then this 'and' can be eliminated by shrinking the mask of
      // the xor. For example, for a 32-bit X:
      // and (xor (srl X, 31), -1), 1 --> xor (srl X, 31), 1
      if (isBitwiseNot(Op0) && Op0.hasOneUse() &&
          LHSKnown.One == ~RHSC->getAPIntValue()) {
        SDValue Xor = TLO.DAG.getNode(ISD::XOR, dl, VT, Op0.getOperand(0), Op1);
        return TLO.CombineTo(Op, Xor);
      }
    }
 
    // AND(INSERT_SUBVECTOR(C,X,I),M) -> INSERT_SUBVECTOR(AND(C,M),X,I)
    // iff 'C' is Undef/Constant and AND(X,M) == X (for DemandedBits).
    if (Op0.getOpcode() == ISD::INSERT_SUBVECTOR &&
        (Op0.getOperand(0).isUndef() ||
         ISD::isBuildVectorOfConstantSDNodes(Op0.getOperand(0).getNode())) &&
        Op0->hasOneUse()) {
      unsigned NumSubElts =
          Op0.getOperand(1).getValueType().getVectorNumElements();
      unsigned SubIdx = Op0.getConstantOperandVal(2);
      APInt DemandedSub =
          APInt::getBitsSet(NumElts, SubIdx, SubIdx + NumSubElts);
      KnownBits KnownSubMask =
          TLO.DAG.computeKnownBits(Op1, DemandedSub & DemandedElts, Depth + 1);
      if (DemandedBits.isSubsetOf(KnownSubMask.One)) {
        SDValue NewAnd =
            TLO.DAG.getNode(ISD::AND, dl, VT, Op0.getOperand(0), Op1);
        SDValue NewInsert =
            TLO.DAG.getNode(ISD::INSERT_SUBVECTOR, dl, VT, NewAnd,
                            Op0.getOperand(1), Op0.getOperand(2));
        return TLO.CombineTo(Op, NewInsert);
      }
    }
 
    if (SimplifyDemandedBits(Op1, DemandedBits, DemandedElts, Known, TLO,
                             Depth + 1))
      return true;
    assert(!Known.hasConflict() && "Bits known to be one AND zero?");
    if (SimplifyDemandedBits(Op0, ~Known.Zero & DemandedBits, DemandedElts,
                             Known2, TLO, Depth + 1))
      return true;
    assert(!Known2.hasConflict() && "Bits known to be one AND zero?");
 
    // If all of the demanded bits are known one on one side, return the other.
    // These bits cannot contribute to the result of the 'and'.
    if (DemandedBits.isSubsetOf(Known2.Zero | Known.One))
      return TLO.CombineTo(Op, Op0);
    if (DemandedBits.isSubsetOf(Known.Zero | Known2.One))
      return TLO.CombineTo(Op, Op1);
    // If all of the demanded bits in the inputs are known zeros, return zero.
    if (DemandedBits.isSubsetOf(Known.Zero | Known2.Zero))
      return TLO.CombineTo(Op, TLO.DAG.getConstant(0, dl, VT));
    // If the RHS is a constant, see if we can simplify it.
    if (ShrinkDemandedConstant(Op, ~Known2.Zero & DemandedBits, DemandedElts,
                               TLO))
      return true;
    // If the operation can be done in a smaller type, do so.
    if (ShrinkDemandedOp(Op, BitWidth, DemandedBits, TLO))
      return true;
 
    // Attempt to avoid multi-use ops if we don't need anything from them.
    if (!DemandedBits.isAllOnes() || !DemandedElts.isAllOnes()) {
      SDValue DemandedOp0 = SimplifyMultipleUseDemandedBits(
          Op0, DemandedBits, DemandedElts, TLO.DAG, Depth + 1);
      SDValue DemandedOp1 = SimplifyMultipleUseDemandedBits(
          Op1, DemandedBits, DemandedElts, TLO.DAG, Depth + 1);
      if (DemandedOp0 || DemandedOp1) {
        Op0 = DemandedOp0 ? DemandedOp0 : Op0;
        Op1 = DemandedOp1 ? DemandedOp1 : Op1;
        SDValue NewOp = TLO.DAG.getNode(Op.getOpcode(), dl, VT, Op0, Op1);
        return TLO.CombineTo(Op, NewOp);
      }
    }
 
    Known &= Known2;
    break;
  }
  case ISD::OR: {
    SDValue Op0 = Op.getOperand(0);
    SDValue Op1 = Op.getOperand(1);
 
    if (SimplifyDemandedBits(Op1, DemandedBits, DemandedElts, Known, TLO,
                             Depth + 1))
      return true;
    assert(!Known.hasConflict() && "Bits known to be one AND zero?");
    if (SimplifyDemandedBits(Op0, ~Known.One & DemandedBits, DemandedElts,
                             Known2, TLO, Depth + 1))
      return true;
    assert(!Known2.hasConflict() && "Bits known to be one AND zero?");
 
    // If all of the demanded bits are known zero on one side, return the other.
    // These bits cannot contribute to the result of the 'or'.
    if (DemandedBits.isSubsetOf(Known2.One | Known.Zero))
      return TLO.CombineTo(Op, Op0);
    if (DemandedBits.isSubsetOf(Known.One | Known2.Zero))
      return TLO.CombineTo(Op, Op1);
    // If the RHS is a constant, see if we can simplify it.
    if (ShrinkDemandedConstant(Op, DemandedBits, DemandedElts, TLO))
      return true;
    // If the operation can be done in a smaller type, do so.
    if (ShrinkDemandedOp(Op, BitWidth, DemandedBits, TLO))
      return true;
 
    // Attempt to avoid multi-use ops if we don't need anything from them.
    if (!DemandedBits.isAllOnes() || !DemandedElts.isAllOnes()) {
      SDValue DemandedOp0 = SimplifyMultipleUseDemandedBits(
          Op0, DemandedBits, DemandedElts, TLO.DAG, Depth + 1);
      SDValue DemandedOp1 = SimplifyMultipleUseDemandedBits(
          Op1, DemandedBits, DemandedElts, TLO.DAG, Depth + 1);
      if (DemandedOp0 || DemandedOp1) {
        Op0 = DemandedOp0 ? DemandedOp0 : Op0;
        Op1 = DemandedOp1 ? DemandedOp1 : Op1;
        SDValue NewOp = TLO.DAG.getNode(Op.getOpcode(), dl, VT, Op0, Op1);
        return TLO.CombineTo(Op, NewOp);
      }
    }
 
    // (or (and X, C1), (and (or X, Y), C2)) -> (or (and X, C1|C2), (and Y, C2))
    // TODO: Use SimplifyMultipleUseDemandedBits to peek through masks.
    if (Op0.getOpcode() == ISD::AND && Op1.getOpcode() == ISD::AND &&
        Op0->hasOneUse() && Op1->hasOneUse()) {
      // Attempt to match all commutations - m_c_Or would've been useful!
      for (int I = 0; I != 2; ++I) {
        SDValue X = Op.getOperand(I).getOperand(0);
        SDValue C1 = Op.getOperand(I).getOperand(1);
        SDValue Alt = Op.getOperand(1 - I).getOperand(0);
        SDValue C2 = Op.getOperand(1 - I).getOperand(1);
        if (Alt.getOpcode() == ISD::OR) {
          for (int J = 0; J != 2; ++J) {
            if (X == Alt.getOperand(J)) {
              SDValue Y = Alt.getOperand(1 - J);
              if (SDValue C12 = TLO.DAG.FoldConstantArithmetic(ISD::OR, dl, VT,
                                                               {C1, C2})) {
                SDValue MaskX = TLO.DAG.getNode(ISD::AND, dl, VT, X, C12);
                SDValue MaskY = TLO.DAG.getNode(ISD::AND, dl, VT, Y, C2);
                return TLO.CombineTo(
                    Op, TLO.DAG.getNode(ISD::OR, dl, VT, MaskX, MaskY));
              }
            }
          }
        }
      }
    }
 
    Known |= Known2;
    break;
  }
  case ISD::XOR: {
    SDValue Op0 = Op.getOperand(0);
    SDValue Op1 = Op.getOperand(1);
 
    if (SimplifyDemandedBits(Op1, DemandedBits, DemandedElts, Known, TLO,
                             Depth + 1))
      return true;
    assert(!Known.hasConflict() && "Bits known to be one AND zero?");
    if (SimplifyDemandedBits(Op0, DemandedBits, DemandedElts, Known2, TLO,
                             Depth + 1))
      return true;
    assert(!Known2.hasConflict() && "Bits known to be one AND zero?");
 
    // If all of the demanded bits are known zero on one side, return the other.
    // These bits cannot contribute to the result of the 'xor'.
    if (DemandedBits.isSubsetOf(Known.Zero))
      return TLO.CombineTo(Op, Op0);
    if (DemandedBits.isSubsetOf(Known2.Zero))
      return TLO.CombineTo(Op, Op1);
    // If the operation can be done in a smaller type, do so.
    if (ShrinkDemandedOp(Op, BitWidth, DemandedBits, TLO))
      return true;
 
    // If all of the unknown bits are known to be zero on one side or the other
    // turn this into an *inclusive* or.
    //    e.g. (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0
    if (DemandedBits.isSubsetOf(Known.Zero | Known2.Zero))
      return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::OR, dl, VT, Op0, Op1));
 
    ConstantSDNode *C = isConstOrConstSplat(Op1, DemandedElts);
    if (C) {
      // If one side is a constant, and all of the set bits in the constant are
      // also known set on the other side, turn this into an AND, as we know
      // the bits will be cleared.
      //    e.g. (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2
      // NB: it is okay if more bits are known than are requested
      if (C->getAPIntValue() == Known2.One) {
        SDValue ANDC =
            TLO.DAG.getConstant(~C->getAPIntValue() & DemandedBits, dl, VT);
        return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::AND, dl, VT, Op0, ANDC));
      }
 
      // If the RHS is a constant, see if we can change it. Don't alter a -1
      // constant because that's a 'not' op, and that is better for combining
      // and codegen.
      if (!C->isAllOnes() && DemandedBits.isSubsetOf(C->getAPIntValue())) {
        // We're flipping all demanded bits. Flip the undemanded bits too.
        SDValue New = TLO.DAG.getNOT(dl, Op0, VT);
        return TLO.CombineTo(Op, New);
      }
 
      unsigned Op0Opcode = Op0.getOpcode();
      if ((Op0Opcode == ISD::SRL || Op0Opcode == ISD::SHL) && Op0.hasOneUse()) {
        if (ConstantSDNode *ShiftC =
                isConstOrConstSplat(Op0.getOperand(1), DemandedElts)) {
          // Don't crash on an oversized shift. We can not guarantee that a
          // bogus shift has been simplified to undef.
          if (ShiftC->getAPIntValue().ult(BitWidth)) {
            uint64_t ShiftAmt = ShiftC->getZExtValue();
            APInt Ones = APInt::getAllOnes(BitWidth);
            Ones = Op0Opcode == ISD::SHL ? Ones.shl(ShiftAmt)
                                         : Ones.lshr(ShiftAmt);
            const TargetLowering &TLI = TLO.DAG.getTargetLoweringInfo();
            if ((DemandedBits & C->getAPIntValue()) == (DemandedBits & Ones) &&
                TLI.isDesirableToCommuteXorWithShift(Op.getNode())) {
              // If the xor constant is a demanded mask, do a 'not' before the
              // shift:
              // xor (X << ShiftC), XorC --> (not X) << ShiftC
              // xor (X >> ShiftC), XorC --> (not X) >> ShiftC
              SDValue Not = TLO.DAG.getNOT(dl, Op0.getOperand(0), VT);
              return TLO.CombineTo(Op, TLO.DAG.getNode(Op0Opcode, dl, VT, Not,
                                                       Op0.getOperand(1)));
            }
          }
        }
      }
    }
 
    // If we can't turn this into a 'not', try to shrink the constant.
    if (!C || !C->isAllOnes())
      if (ShrinkDemandedConstant(Op, DemandedBits, DemandedElts, TLO))
        return true;
 
    // Attempt to avoid multi-use ops if we don't need anything from them.
    if (!DemandedBits.isAllOnes() || !DemandedElts.isAllOnes()) {
      SDValue DemandedOp0 = SimplifyMultipleUseDemandedBits(
          Op0, DemandedBits, DemandedElts, TLO.DAG, Depth + 1);
      SDValue DemandedOp1 = SimplifyMultipleUseDemandedBits(
          Op1, DemandedBits, DemandedElts, TLO.DAG, Depth + 1);
      if (DemandedOp0 || DemandedOp1) {
        Op0 = DemandedOp0 ? DemandedOp0 : Op0;
        Op1 = DemandedOp1 ? DemandedOp1 : Op1;
        SDValue NewOp = TLO.DAG.getNode(Op.getOpcode(), dl, VT, Op0, Op1);
        return TLO.CombineTo(Op, NewOp);
      }
    }
 
    Known ^= Known2;
    break;
  }
  case ISD::SELECT:
    if (SimplifyDemandedBits(Op.getOperand(2), DemandedBits, Known, TLO,
                             Depth + 1))
      return true;
    if (SimplifyDemandedBits(Op.getOperand(1), DemandedBits, Known2, TLO,
                             Depth + 1))
      return true;
    assert(!Known.hasConflict() && "Bits known to be one AND zero?");
    assert(!Known2.hasConflict() && "Bits known to be one AND zero?");
 
    // If the operands are constants, see if we can simplify them.
    if (ShrinkDemandedConstant(Op, DemandedBits, DemandedElts, TLO))
      return true;
 
    // Only known if known in both the LHS and RHS.
    Known = KnownBits::commonBits(Known, Known2);
    break;
  case ISD::VSELECT:
    if (SimplifyDemandedBits(Op.getOperand(2), DemandedBits, DemandedElts,
                             Known, TLO, Depth + 1))
      return true;
    if (SimplifyDemandedBits(Op.getOperand(1), DemandedBits, DemandedElts,
                             Known2, TLO, Depth + 1))
      return true;
    assert(!Known.hasConflict() && "Bits known to be one AND zero?");
    assert(!Known2.hasConflict() && "Bits known to be one AND zero?");
 
    // Only known if known in both the LHS and RHS.
    Known = KnownBits::commonBits(Known, Known2);
    break;
  case ISD::SELECT_CC:
    if (SimplifyDemandedBits(Op.getOperand(3), DemandedBits, Known, TLO,
                             Depth + 1))
      return true;
    if (SimplifyDemandedBits(Op.getOperand(2), DemandedBits, Known2, TLO,
                             Depth + 1))
      return true;
    assert(!Known.hasConflict() && "Bits known to be one AND zero?");
    assert(!Known2.hasConflict() && "Bits known to be one AND zero?");
 
    // If the operands are constants, see if we can simplify them.
    if (ShrinkDemandedConstant(Op, DemandedBits, DemandedElts, TLO))
      return true;
 
    // Only known if known in both the LHS and RHS.
    Known = KnownBits::commonBits(Known, Known2);
    break;
  case ISD::SETCC: {
    SDValue Op0 = Op.getOperand(0);
    SDValue Op1 = Op.getOperand(1);
    ISD::CondCode CC = cast<CondCodeSDNode>(Op.getOperand(2))->get();
    // If (1) we only need the sign-bit, (2) the setcc operands are the same
    // width as the setcc result, and (3) the result of a setcc conforms to 0 or
    // -1, we may be able to bypass the setcc.
    if (DemandedBits.isSignMask() &&
        Op0.getScalarValueSizeInBits() == BitWidth &&
        getBooleanContents(Op0.getValueType()) ==
            BooleanContent::ZeroOrNegativeOneBooleanContent) {
      // If we're testing X < 0, then this compare isn't needed - just use X!
      // FIXME: We're limiting to integer types here, but this should also work
      // if we don't care about FP signed-zero. The use of SETLT with FP means
      // that we don't care about NaNs.
      if (CC == ISD::SETLT && Op1.getValueType().isInteger() &&
          (isNullConstant(Op1) || ISD::isBuildVectorAllZeros(Op1.getNode())))
        return TLO.CombineTo(Op, Op0);
 
      // TODO: Should we check for other forms of sign-bit comparisons?
      // Examples: X <= -1, X >= 0
    }
    if (getBooleanContents(Op0.getValueType()) ==
            TargetLowering::ZeroOrOneBooleanContent &&
        BitWidth > 1)
      Known.Zero.setBitsFrom(1);
    break;
  }
  case ISD::SHL: {
    SDValue Op0 = Op.getOperand(0);
    SDValue Op1 = Op.getOperand(1);
    EVT ShiftVT = Op1.getValueType();
 
    if (const APInt *SA =
            TLO.DAG.getValidShiftAmountConstant(Op, DemandedElts)) {
      unsigned ShAmt = SA->getZExtValue();
      if (ShAmt == 0)
        return TLO.CombineTo(Op, Op0);
 
      // If this is ((X >>u C1) << ShAmt), see if we can simplify this into a
      // single shift.  We can do this if the bottom bits (which are shifted
      // out) are never demanded.
      // TODO - support non-uniform vector amounts.
      if (Op0.getOpcode() == ISD::SRL) {
        if (!DemandedBits.intersects(APInt::getLowBitsSet(BitWidth, ShAmt))) {
          if (const APInt *SA2 =
                  TLO.DAG.getValidShiftAmountConstant(Op0, DemandedElts)) {
            unsigned C1 = SA2->getZExtValue();
            unsigned Opc = ISD::SHL;
            int Diff = ShAmt - C1;
            if (Diff < 0) {
              Diff = -Diff;
              Opc = ISD::SRL;
            }
            SDValue NewSA = TLO.DAG.getConstant(Diff, dl, ShiftVT);
            return TLO.CombineTo(
                Op, TLO.DAG.getNode(Opc, dl, VT, Op0.getOperand(0), NewSA));
          }
        }
      }
 
      // Convert (shl (anyext x, c)) to (anyext (shl x, c)) if the high bits
      // are not demanded. This will likely allow the anyext to be folded away.
      // TODO - support non-uniform vector amounts.
      if (Op0.getOpcode() == ISD::ANY_EXTEND) {
        SDValue InnerOp = Op0.getOperand(0);
        EVT InnerVT = InnerOp.getValueType();
        unsigned InnerBits = InnerVT.getScalarSizeInBits();
        if (ShAmt < InnerBits && DemandedBits.getActiveBits() <= InnerBits &&
            isTypeDesirableForOp(ISD::SHL, InnerVT)) {
          EVT ShTy = getShiftAmountTy(InnerVT, DL);
          if (!APInt(BitWidth, ShAmt).isIntN(ShTy.getSizeInBits()))
            ShTy = InnerVT;
          SDValue NarrowShl =
              TLO.DAG.getNode(ISD::SHL, dl, InnerVT, InnerOp,
                              TLO.DAG.getConstant(ShAmt, dl, ShTy));
          return TLO.CombineTo(
              Op, TLO.DAG.getNode(ISD::ANY_EXTEND, dl, VT, NarrowShl));
        }
 
        // Repeat the SHL optimization above in cases where an extension
        // intervenes: (shl (anyext (shr x, c1)), c2) to
        // (shl (anyext x), c2-c1).  This requires that the bottom c1 bits
        // aren't demanded (as above) and that the shifted upper c1 bits of
        // x aren't demanded.
        // TODO - support non-uniform vector amounts.
        if (InnerOp.getOpcode() == ISD::SRL && Op0.hasOneUse() &&
            InnerOp.hasOneUse()) {
          if (const APInt *SA2 =
                  TLO.DAG.getValidShiftAmountConstant(InnerOp, DemandedElts)) {
            unsigned InnerShAmt = SA2->getZExtValue();
            if (InnerShAmt < ShAmt && InnerShAmt < InnerBits &&
                DemandedBits.getActiveBits() <=
                    (InnerBits - InnerShAmt + ShAmt) &&
                DemandedBits.countTrailingZeros() >= ShAmt) {
              SDValue NewSA =
                  TLO.DAG.getConstant(ShAmt - InnerShAmt, dl, ShiftVT);
              SDValue NewExt = TLO.DAG.getNode(ISD::ANY_EXTEND, dl, VT,
                                               InnerOp.getOperand(0));
              return TLO.CombineTo(
                  Op, TLO.DAG.getNode(ISD::SHL, dl, VT, NewExt, NewSA));
            }
          }
        }
      }
 
      APInt InDemandedMask = DemandedBits.lshr(ShAmt);
      if (SimplifyDemandedBits(Op0, InDemandedMask, DemandedElts, Known, TLO,
                               Depth + 1))
        return true;
      assert(!Known.hasConflict() && "Bits known to be one AND zero?");
      Known.Zero <<= ShAmt;
      Known.One <<= ShAmt;
      // low bits known zero.
      Known.Zero.setLowBits(ShAmt);
 
      // Attempt to avoid multi-use ops if we don't need anything from them.
      if (!InDemandedMask.isAllOnesValue() || !DemandedElts.isAllOnesValue()) {
        SDValue DemandedOp0 = SimplifyMultipleUseDemandedBits(
            Op0, InDemandedMask, DemandedElts, TLO.DAG, Depth + 1);
        if (DemandedOp0) {
          SDValue NewOp = TLO.DAG.getNode(ISD::SHL, dl, VT, DemandedOp0, Op1);
          return TLO.CombineTo(Op, NewOp);
        }
      }
 
      // Try shrinking the operation as long as the shift amount will still be
      // in range.
      if ((ShAmt < DemandedBits.getActiveBits()) &&
          ShrinkDemandedOp(Op, BitWidth, DemandedBits, TLO))
        return true;
    } else {
      // This is a variable shift, so we can't shift the demand mask by a known
      // amount. But if we are not demanding high bits, then we are not
      // demanding those bits from the pre-shifted operand either.
      if (unsigned CTLZ = DemandedBits.countLeadingZeros()) {
        APInt DemandedFromOp(APInt::getLowBitsSet(BitWidth, BitWidth - CTLZ));
        if (SimplifyDemandedBits(Op0, DemandedFromOp, DemandedElts, Known, TLO,
                                 Depth + 1)) {
          SDNodeFlags Flags = Op.getNode()->getFlags();
          if (Flags.hasNoSignedWrap() || Flags.hasNoUnsignedWrap()) {
            // Disable the nsw and nuw flags. We can no longer guarantee that we
            // won't wrap after simplification.
            Flags.setNoSignedWrap(false);
            Flags.setNoUnsignedWrap(false);
            Op->setFlags(Flags);
          }
          return true;
        }
        Known.resetAll();
      }
    }
 
    // If we are only demanding sign bits then we can use the shift source
    // directly.
    if (const APInt *MaxSA =
            TLO.DAG.getValidMaximumShiftAmountConstant(Op, DemandedElts)) {
      unsigned ShAmt = MaxSA->getZExtValue();
      unsigned NumSignBits =
          TLO.DAG.ComputeNumSignBits(Op0, DemandedElts, Depth + 1);
      unsigned UpperDemandedBits = BitWidth - DemandedBits.countTrailingZeros();
      if (NumSignBits > ShAmt && (NumSignBits - ShAmt) >= (UpperDemandedBits))
        return TLO.CombineTo(Op, Op0);
    }
    break;
  }
  case ISD::SRL: {
    SDValue Op0 = Op.getOperand(0);
    SDValue Op1 = Op.getOperand(1);
    EVT ShiftVT = Op1.getValueType();
 
    // Try to match AVG patterns.
    if (SDValue AVG = combineShiftToAVG(Op, TLO.DAG, *this, DemandedBits,
                                        DemandedElts, Depth + 1))
      return TLO.CombineTo(Op, AVG);
 
    if (const APInt *SA =
            TLO.DAG.getValidShiftAmountConstant(Op, DemandedElts)) {
      unsigned ShAmt = SA->getZExtValue();
      if (ShAmt == 0)
        return TLO.CombineTo(Op, Op0);
 
      // If this is ((X << C1) >>u ShAmt), see if we can simplify this into a
      // single shift.  We can do this if the top bits (which are shifted out)
      // are never demanded.
      // TODO - support non-uniform vector amounts.
      if (Op0.getOpcode() == ISD::SHL) {
        if (!DemandedBits.intersects(APInt::getHighBitsSet(BitWidth, ShAmt))) {
          if (const APInt *SA2 =
                  TLO.DAG.getValidShiftAmountConstant(Op0, DemandedElts)) {
            unsigned C1 = SA2->getZExtValue();
            unsigned Opc = ISD::SRL;
            int Diff = ShAmt - C1;
            if (Diff < 0) {
              Diff = -Diff;
              Opc = ISD::SHL;
            }
            SDValue NewSA = TLO.DAG.getConstant(Diff, dl, ShiftVT);
            return TLO.CombineTo(
                Op, TLO.DAG.getNode(Opc, dl, VT, Op0.getOperand(0), NewSA));
          }
        }
      }
 
      APInt InDemandedMask = (DemandedBits << ShAmt);
 
      // If the shift is exact, then it does demand the low bits (and knows that
      // they are zero).
      if (Op->getFlags().hasExact())
        InDemandedMask.setLowBits(ShAmt);
 
      // Compute the new bits that are at the top now.
      if (SimplifyDemandedBits(Op0, InDemandedMask, DemandedElts, Known, TLO,
                               Depth + 1))
        return true;
      assert(!Known.hasConflict() && "Bits known to be one AND zero?");
      Known.Zero.lshrInPlace(ShAmt);
      Known.One.lshrInPlace(ShAmt);
      // High bits known zero.
      Known.Zero.setHighBits(ShAmt);
 
      // Attempt to avoid multi-use ops if we don't need anything from them.
      if (!InDemandedMask.isAllOnesValue() || !DemandedElts.isAllOnesValue()) {
        SDValue DemandedOp0 = SimplifyMultipleUseDemandedBits(
            Op0, InDemandedMask, DemandedElts, TLO.DAG, Depth + 1);
        if (DemandedOp0) {
          SDValue NewOp = TLO.DAG.getNode(ISD::SRL, dl, VT, DemandedOp0, Op1);
          return TLO.CombineTo(Op, NewOp);
        }
      }
    }
    break;
  }
  case ISD::SRA: {
    SDValue Op0 = Op.getOperand(0);
    SDValue Op1 = Op.getOperand(1);
    EVT ShiftVT = Op1.getValueType();
 
    // If we only want bits that already match the signbit then we don't need
    // to shift.
    unsigned NumHiDemandedBits = BitWidth - DemandedBits.countTrailingZeros();
    if (TLO.DAG.ComputeNumSignBits(Op0, DemandedElts, Depth + 1) >=
        NumHiDemandedBits)
      return TLO.CombineTo(Op, Op0);
 
    // If this is an arithmetic shift right and only the low-bit is set, we can
    // always convert this into a logical shr, even if the shift amount is
    // variable.  The low bit of the shift cannot be an input sign bit unless
    // the shift amount is >= the size of the datatype, which is undefined.
    if (DemandedBits.isOne())
      return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SRL, dl, VT, Op0, Op1));
 
    // Try to match AVG patterns.
    if (SDValue AVG = combineShiftToAVG(Op, TLO.DAG, *this, DemandedBits,
                                        DemandedElts, Depth + 1))
      return TLO.CombineTo(Op, AVG);
 
    if (const APInt *SA =
            TLO.DAG.getValidShiftAmountConstant(Op, DemandedElts)) {
      unsigned ShAmt = SA->getZExtValue();
      if (ShAmt == 0)
        return TLO.CombineTo(Op, Op0);
 
      APInt InDemandedMask = (DemandedBits << ShAmt);
 
      // If the shift is exact, then it does demand the low bits (and knows that
      // they are zero).
      if (Op->getFlags().hasExact())
        InDemandedMask.setLowBits(ShAmt);
 
      // If any of the demanded bits are produced by the sign extension, we also
      // demand the input sign bit.
      if (DemandedBits.countLeadingZeros() < ShAmt)
        InDemandedMask.setSignBit();
 
      if (SimplifyDemandedBits(Op0, InDemandedMask, DemandedElts, Known, TLO,
                               Depth + 1))
        return true;
      assert(!Known.hasConflict() && "Bits known to be one AND zero?");
      Known.Zero.lshrInPlace(ShAmt);
      Known.One.lshrInPlace(ShAmt);
 
      // If the input sign bit is known to be zero, or if none of the top bits
      // are demanded, turn this into an unsigned shift right.
      if (Known.Zero[BitWidth - ShAmt - 1] ||
          DemandedBits.countLeadingZeros() >= ShAmt) {
        SDNodeFlags Flags;
        Flags.setExact(Op->getFlags().hasExact());
        return TLO.CombineTo(
            Op, TLO.DAG.getNode(ISD::SRL, dl, VT, Op0, Op1, Flags));
      }
 
      int Log2 = DemandedBits.exactLogBase2();
      if (Log2 >= 0) {
        // The bit must come from the sign.
        SDValue NewSA = TLO.DAG.getConstant(BitWidth - 1 - Log2, dl, ShiftVT);
        return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SRL, dl, VT, Op0, NewSA));
      }
 
      if (Known.One[BitWidth - ShAmt - 1])
        // New bits are known one.
        Known.One.setHighBits(ShAmt);
 
      // Attempt to avoid multi-use ops if we don't need anything from them.
      if (!InDemandedMask.isAllOnes() || !DemandedElts.isAllOnes()) {
        SDValue DemandedOp0 = SimplifyMultipleUseDemandedBits(
            Op0, InDemandedMask, DemandedElts, TLO.DAG, Depth + 1);
        if (DemandedOp0) {
          SDValue NewOp = TLO.DAG.getNode(ISD::SRA, dl, VT, DemandedOp0, Op1);
          return TLO.CombineTo(Op, NewOp);
        }
      }
    }
    break;
  }
  case ISD::FSHL:
  case ISD::FSHR: {
    SDValue Op0 = Op.getOperand(0);
    SDValue Op1 = Op.getOperand(1);
    SDValue Op2 = Op.getOperand(2);
    bool IsFSHL = (Op.getOpcode() == ISD::FSHL);
 
    if (ConstantSDNode *SA = isConstOrConstSplat(Op2, DemandedElts)) {
      unsigned Amt = SA->getAPIntValue().urem(BitWidth);
 
      // For fshl, 0-shift returns the 1st arg.
      // For fshr, 0-shift returns the 2nd arg.
      if (Amt == 0) {
        if (SimplifyDemandedBits(IsFSHL ? Op0 : Op1, DemandedBits, DemandedElts,
                                 Known, TLO, Depth + 1))
          return true;
        break;
      }
 
      // fshl: (Op0 << Amt) | (Op1 >> (BW - Amt))
      // fshr: (Op0 << (BW - Amt)) | (Op1 >> Amt)
      APInt Demanded0 = DemandedBits.lshr(IsFSHL ? Amt : (BitWidth - Amt));
      APInt Demanded1 = DemandedBits << (IsFSHL ? (BitWidth - Amt) : Amt);
      if (SimplifyDemandedBits(Op0, Demanded0, DemandedElts, Known2, TLO,
                               Depth + 1))
        return true;
      if (SimplifyDemandedBits(Op1, Demanded1, DemandedElts, Known, TLO,
                               Depth + 1))
        return true;
 
      Known2.One <<= (IsFSHL ? Amt : (BitWidth - Amt));
      Known2.Zero <<= (IsFSHL ? Amt : (BitWidth - Amt));
      Known.One.lshrInPlace(IsFSHL ? (BitWidth - Amt) : Amt);
      Known.Zero.lshrInPlace(IsFSHL ? (BitWidth - Amt) : Amt);
      Known.One |= Known2.One;
      Known.Zero |= Known2.Zero;
 
      // Attempt to avoid multi-use ops if we don't need anything from them.
      if (!Demanded0.isAllOnes() || !Demanded1.isAllOnes() ||
          !DemandedElts.isAllOnes()) {
        SDValue DemandedOp0 = SimplifyMultipleUseDemandedBits(
            Op0, Demanded0, DemandedElts, TLO.DAG, Depth + 1);
        SDValue DemandedOp1 = SimplifyMultipleUseDemandedBits(
            Op1, Demanded1, DemandedElts, TLO.DAG, Depth + 1);
        if (DemandedOp0 || DemandedOp1) {
          DemandedOp0 = DemandedOp0 ? DemandedOp0 : Op0;
          DemandedOp1 = DemandedOp1 ? DemandedOp1 : Op1;
          SDValue NewOp = TLO.DAG.getNode(Op.getOpcode(), dl, VT, DemandedOp0,
                                          DemandedOp1, Op2);
          return TLO.CombineTo(Op, NewOp);
        }
      }
    }
 
    // For pow-2 bitwidths we only demand the bottom modulo amt bits.
    if (isPowerOf2_32(BitWidth)) {
      APInt DemandedAmtBits(Op2.getScalarValueSizeInBits(), BitWidth - 1);
      if (SimplifyDemandedBits(Op2, DemandedAmtBits, DemandedElts,
                               Known2, TLO, Depth + 1))
        return true;
    }
    break;
  }
  case ISD::ROTL:
  case ISD::ROTR: {
    SDValue Op0 = Op.getOperand(0);
    SDValue Op1 = Op.getOperand(1);
    bool IsROTL = (Op.getOpcode() == ISD::ROTL);
 
    // If we're rotating an 0/-1 value, then it stays an 0/-1 value.
    if (BitWidth == TLO.DAG.ComputeNumSignBits(Op0, DemandedElts, Depth + 1))
      return TLO.CombineTo(Op, Op0);
 
    if (ConstantSDNode *SA = isConstOrConstSplat(Op1, DemandedElts)) {
      unsigned Amt = SA->getAPIntValue().urem(BitWidth);
      unsigned RevAmt = BitWidth - Amt;
 
      // rotl: (Op0 << Amt) | (Op0 >> (BW - Amt))
      // rotr: (Op0 << (BW - Amt)) | (Op0 >> Amt)
      APInt Demanded0 = DemandedBits.rotr(IsROTL ? Amt : RevAmt);
      if (SimplifyDemandedBits(Op0, Demanded0, DemandedElts, Known2, TLO,
                               Depth + 1))
        return true;
 
      // rot*(x, 0) --> x
      if (Amt == 0)
        return TLO.CombineTo(Op, Op0);
 
      // See if we don't demand either half of the rotated bits.
      if ((!TLO.LegalOperations() || isOperationLegal(ISD::SHL, VT)) &&
          DemandedBits.countTrailingZeros() >= (IsROTL ? Amt : RevAmt)) {
        Op1 = TLO.DAG.getConstant(IsROTL ? Amt : RevAmt, dl, Op1.getValueType());
        return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SHL, dl, VT, Op0, Op1));
      }
      if ((!TLO.LegalOperations() || isOperationLegal(ISD::SRL, VT)) &&
          DemandedBits.countLeadingZeros() >= (IsROTL ? RevAmt : Amt)) {
        Op1 = TLO.DAG.getConstant(IsROTL ? RevAmt : Amt, dl, Op1.getValueType());
        return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SRL, dl, VT, Op0, Op1));
      }
    }
 
    // For pow-2 bitwidths we only demand the bottom modulo amt bits.
    if (isPowerOf2_32(BitWidth)) {
      APInt DemandedAmtBits(Op1.getScalarValueSizeInBits(), BitWidth - 1);
      if (SimplifyDemandedBits(Op1, DemandedAmtBits, DemandedElts, Known2, TLO,
                               Depth + 1))
        return true;
    }
    break;
  }
  case ISD::UMIN: {
    // Check if one arg is always less than (or equal) to the other arg.
    SDValue Op0 = Op.getOperand(0);
    SDValue Op1 = Op.getOperand(1);
    KnownBits Known0 = TLO.DAG.computeKnownBits(Op0, DemandedElts, Depth + 1);
    KnownBits Known1 = TLO.DAG.computeKnownBits(Op1, DemandedElts, Depth + 1);
    Known = KnownBits::umin(Known0, Known1);
    if (Optional<bool> IsULE = KnownBits::ule(Known0, Known1))
      return TLO.CombineTo(Op, IsULE.value() ? Op0 : Op1);
    if (Optional<bool> IsULT = KnownBits::ult(Known0, Known1))
      return TLO.CombineTo(Op, IsULT.value() ? Op0 : Op1);
    break;
  }
  case ISD::UMAX: {
    // Check if one arg is always greater than (or equal) to the other arg.
    SDValue Op0 = Op.getOperand(0);
    SDValue Op1 = Op.getOperand(1);
    KnownBits Known0 = TLO.DAG.computeKnownBits(Op0, DemandedElts, Depth + 1);
    KnownBits Known1 = TLO.DAG.computeKnownBits(Op1, DemandedElts, Depth + 1);
    Known = KnownBits::umax(Known0, Known1);
    if (Optional<bool> IsUGE = KnownBits::uge(Known0, Known1))
      return TLO.CombineTo(Op, IsUGE.value() ? Op0 : Op1);
    if (Optional<bool> IsUGT = KnownBits::ugt(Known0, Known1))
      return TLO.CombineTo(Op, IsUGT.value() ? Op0 : Op1);
    break;
  }
  case ISD::BITREVERSE: {
    SDValue Src = Op.getOperand(0);
    APInt DemandedSrcBits = DemandedBits.reverseBits();
    if (SimplifyDemandedBits(Src, DemandedSrcBits, DemandedElts, Known2, TLO,
                             Depth + 1))
      return true;
    Known.One = Known2.One.reverseBits();
    Known.Zero = Known2.Zero.reverseBits();
    break;
  }
  case ISD::BSWAP: {
    SDValue Src = Op.getOperand(0);
 
    // If the only bits demanded come from one byte of the bswap result,
    // just shift the input byte into position to eliminate the bswap.
    unsigned NLZ = DemandedBits.countLeadingZeros();
    unsigned NTZ = DemandedBits.countTrailingZeros();
 
    // Round NTZ down to the next byte.  If we have 11 trailing zeros, then
    // we need all the bits down to bit 8.  Likewise, round NLZ.  If we
    // have 14 leading zeros, round to 8.
    NLZ = alignDown(NLZ, 8);
    NTZ = alignDown(NTZ, 8);
    // If we need exactly one byte, we can do this transformation.
    if (BitWidth - NLZ - NTZ == 8) {
      // Replace this with either a left or right shift to get the byte into
      // the right place.
      unsigned ShiftOpcode = NLZ > NTZ ? ISD::SRL : ISD::SHL;
      if (!TLO.LegalOperations() || isOperationLegal(ShiftOpcode, VT)) {
        EVT ShiftAmtTy = getShiftAmountTy(VT, DL);
        unsigned ShiftAmount = NLZ > NTZ ? NLZ - NTZ : NTZ - NLZ;
        SDValue ShAmt = TLO.DAG.getConstant(ShiftAmount, dl, ShiftAmtTy);
        SDValue NewOp = TLO.DAG.getNode(ShiftOpcode, dl, VT, Src, ShAmt);
        return TLO.CombineTo(Op, NewOp);
      }
    }
 
    APInt DemandedSrcBits = DemandedBits.byteSwap();
    if (SimplifyDemandedBits(Src, DemandedSrcBits, DemandedElts, Known2, TLO,
                             Depth + 1))
      return true;
    Known.One = Known2.One.byteSwap();
    Known.Zero = Known2.Zero.byteSwap();
    break;
  }
  case ISD::CTPOP: {
    // If only 1 bit is demanded, replace with PARITY as long as we're before
    // op legalization.
    // FIXME: Limit to scalars for now.
    if (DemandedBits.isOne() && !TLO.LegalOps && !VT.isVector())
      return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::PARITY, dl, VT,
                                               Op.getOperand(0)));
 
    Known = TLO.DAG.computeKnownBits(Op, DemandedElts, Depth);
    break;
  }
  case ISD::SIGN_EXTEND_INREG: {
    SDValue Op0 = Op.getOperand(0);
    EVT ExVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
    unsigned ExVTBits = ExVT.getScalarSizeInBits();
 
    // If we only care about the highest bit, don't bother shifting right.
    if (DemandedBits.isSignMask()) {
      unsigned MinSignedBits =
          TLO.DAG.ComputeMaxSignificantBits(Op0, DemandedElts, Depth + 1);
      bool AlreadySignExtended = ExVTBits >= MinSignedBits;
      // However if the input is already sign extended we expect the sign
      // extension to be dropped altogether later and do not simplify.
      if (!AlreadySignExtended) {
        // Compute the correct shift amount type, which must be getShiftAmountTy
        // for scalar types after legalization.
        SDValue ShiftAmt = TLO.DAG.getConstant(BitWidth - ExVTBits, dl,
                                               getShiftAmountTy(VT, DL));
        return TLO.CombineTo(Op,
                             TLO.DAG.getNode(ISD::SHL, dl, VT, Op0, ShiftAmt));
      }
    }
 
    // If none of the extended bits are demanded, eliminate the sextinreg.
    if (DemandedBits.getActiveBits() <= ExVTBits)
      return TLO.CombineTo(Op, Op0);
 
    APInt InputDemandedBits = DemandedBits.getLoBits(ExVTBits);
 
    // Since the sign extended bits are demanded, we know that the sign
    // bit is demanded.
    InputDemandedBits.setBit(ExVTBits - 1);
 
    if (SimplifyDemandedBits(Op0, InputDemandedBits, DemandedElts, Known, TLO,
                             Depth + 1))
      return true;
    assert(!Known.hasConflict() && "Bits known to be one AND zero?");
 
    // If the sign bit of the input is known set or clear, then we know the
    // top bits of the result.
 
    // If the input sign bit is known zero, convert this into a zero extension.
    if (Known.Zero[ExVTBits - 1])
      return TLO.CombineTo(Op, TLO.DAG.getZeroExtendInReg(Op0, dl, ExVT));
 
    APInt Mask = APInt::getLowBitsSet(BitWidth, ExVTBits);
    if (Known.One[ExVTBits - 1]) { // Input sign bit known set
      Known.One.setBitsFrom(ExVTBits);
      Known.Zero &= Mask;
    } else { // Input sign bit unknown
      Known.Zero &= Mask;
      Known.One &= Mask;
    }
    break;
  }
  case ISD::BUILD_PAIR: {
    EVT HalfVT = Op.getOperand(0).getValueType();
    unsigned HalfBitWidth = HalfVT.getScalarSizeInBits();
 
    APInt MaskLo = DemandedBits.getLoBits(HalfBitWidth).trunc(HalfBitWidth);
    APInt MaskHi = DemandedBits.getHiBits(HalfBitWidth).trunc(HalfBitWidth);
 
    KnownBits KnownLo, KnownHi;
 
    if (SimplifyDemandedBits(Op.getOperand(0), MaskLo, KnownLo, TLO, Depth + 1))
      return true;
 
    if (SimplifyDemandedBits(Op.getOperand(1), MaskHi, KnownHi, TLO, Depth + 1))
      return true;
 
    Known = KnownHi.concat(KnownLo);
    break;
  }
  case ISD::ZERO_EXTEND:
  case ISD::ZERO_EXTEND_VECTOR_INREG: {
    SDValue Src = Op.getOperand(0);
    EVT SrcVT = Src.getValueType();
    unsigned InBits = SrcVT.getScalarSizeInBits();
    unsigned InElts = SrcVT.isVector() ? SrcVT.getVectorNumElements() : 1;
    bool IsVecInReg = Op.getOpcode() == ISD::ZERO_EXTEND_VECTOR_INREG;
 
    // If none of the top bits are demanded, convert this into an any_extend.
    if (DemandedBits.getActiveBits() <= InBits) {
      // If we only need the non-extended bits of the bottom element
      // then we can just bitcast to the result.
      if (IsLE && IsVecInReg && DemandedElts == 1 &&
          VT.getSizeInBits() == SrcVT.getSizeInBits())
        return TLO.CombineTo(Op, TLO.DAG.getBitcast(VT, Src));
 
      unsigned Opc =
          IsVecInReg ? ISD::ANY_EXTEND_VECTOR_INREG : ISD::ANY_EXTEND;
      if (!TLO.LegalOperations() || isOperationLegal(Opc, VT))
        return TLO.CombineTo(Op, TLO.DAG.getNode(Opc, dl, VT, Src));
    }
 
    APInt InDemandedBits = DemandedBits.trunc(InBits);
    APInt InDemandedElts = DemandedElts.zext(InElts);
    if (SimplifyDemandedBits(Src, InDemandedBits, InDemandedElts, Known, TLO,
                             Depth + 1))
      return true;
    assert(!Known.hasConflict() && "Bits known to be one AND zero?");
    assert(Known.getBitWidth() == InBits && "Src width has changed?");
    Known = Known.zext(BitWidth);
 
    // Attempt to avoid multi-use ops if we don't need anything from them.
    if (SDValue NewSrc = SimplifyMultipleUseDemandedBits(
            Src, InDemandedBits, InDemandedElts, TLO.DAG, Depth + 1))
      return TLO.CombineTo(Op, TLO.DAG.getNode(Op.getOpcode(), dl, VT, NewSrc));
    break;
  }
  case ISD::SIGN_EXTEND:
  case ISD::SIGN_EXTEND_VECTOR_INREG: {
    SDValue Src = Op.getOperand(0);
    EVT SrcVT = Src.getValueType();
    unsigned InBits = SrcVT.getScalarSizeInBits();
    unsigned InElts = SrcVT.isVector() ? SrcVT.getVectorNumElements() : 1;
    bool IsVecInReg = Op.getOpcode() == ISD::SIGN_EXTEND_VECTOR_INREG;
 
    // If none of the top bits are demanded, convert this into an any_extend.
    if (DemandedBits.getActiveBits() <= InBits) {
      // If we only need the non-extended bits of the bottom element
      // then we can just bitcast to the result.
      if (IsLE && IsVecInReg && DemandedElts == 1 &&
          VT.getSizeInBits() == SrcVT.getSizeInBits())
        return TLO.CombineTo(Op, TLO.DAG.getBitcast(VT, Src));
 
      unsigned Opc =
          IsVecInReg ? ISD::ANY_EXTEND_VECTOR_INREG : ISD::ANY_EXTEND;
      if (!TLO.LegalOperations() || isOperationLegal(Opc, VT))
        return TLO.CombineTo(Op, TLO.DAG.getNode(Opc, dl, VT, Src));
    }
 
    APInt InDemandedBits = DemandedBits.trunc(InBits);
    APInt InDemandedElts = DemandedElts.zext(InElts);
 
    // Since some of the sign extended bits are demanded, we know that the sign
    // bit is demanded.
    InDemandedBits.setBit(InBits - 1);
 
    if (SimplifyDemandedBits(Src, InDemandedBits, InDemandedElts, Known, TLO,
                             Depth + 1))
      return true;
    assert(!Known.hasConflict() && "Bits known to be one AND zero?");
    assert(Known.getBitWidth() == InBits && "Src width has changed?");
 
    // If the sign bit is known one, the top bits match.
    Known = Known.sext(BitWidth);
 
    // If the sign bit is known zero, convert this to a zero extend.
    if (Known.isNonNegative()) {
      unsigned Opc =
          IsVecInReg ? ISD::ZERO_EXTEND_VECTOR_INREG : ISD::ZERO_EXTEND;
      if (!TLO.LegalOperations() || isOperationLegal(Opc, VT))
        return TLO.CombineTo(Op, TLO.DAG.getNode(Opc, dl, VT, Src));
    }
 
    // Attempt to avoid multi-use ops if we don't need anything from them.
    if (SDValue NewSrc = SimplifyMultipleUseDemandedBits(
            Src, InDemandedBits, InDemandedElts, TLO.DAG, Depth + 1))
      return TLO.CombineTo(Op, TLO.DAG.getNode(Op.getOpcode(), dl, VT, NewSrc));
    break;
  }
  case ISD::ANY_EXTEND:
  case ISD::ANY_EXTEND_VECTOR_INREG: {
    SDValue Src = Op.getOperand(0);
    EVT SrcVT = Src.getValueType();
    unsigned InBits = SrcVT.getScalarSizeInBits();
    unsigned InElts = SrcVT.isVector() ? SrcVT.getVectorNumElements() : 1;
    bool IsVecInReg = Op.getOpcode() == ISD::ANY_EXTEND_VECTOR_INREG;
 
    // If we only need the bottom element then we can just bitcast.
    // TODO: Handle ANY_EXTEND?
    if (IsLE && IsVecInReg && DemandedElts == 1 &&
        VT.getSizeInBits() == SrcVT.getSizeInBits())
      return TLO.CombineTo(Op, TLO.DAG.getBitcast(VT, Src));
 
    APInt InDemandedBits = DemandedBits.trunc(InBits);
    APInt InDemandedElts = DemandedElts.zext(InElts);
    if (SimplifyDemandedBits(Src, InDemandedBits, InDemandedElts, Known, TLO,
                             Depth + 1))
      return true;
    assert(!Known.hasConflict() && "Bits known to be one AND zero?");
    assert(Known.getBitWidth() == InBits && "Src width has changed?");
    Known = Known.anyext(BitWidth);
 
    // Attempt to avoid multi-use ops if we don't need anything from them.
    if (SDValue NewSrc = SimplifyMultipleUseDemandedBits(
            Src, InDemandedBits, InDemandedElts, TLO.DAG, Depth + 1))
      return TLO.CombineTo(Op, TLO.DAG.getNode(Op.getOpcode(), dl, VT, NewSrc));
    break;
  }
  case ISD::TRUNCATE: {
    SDValue Src = Op.getOperand(0);
 
    // Simplify the input, using demanded bit information, and compute the known
    // zero/one bits live out.
    unsigned OperandBitWidth = Src.getScalarValueSizeInBits();
    APInt TruncMask = DemandedBits.zext(OperandBitWidth);
    if (SimplifyDemandedBits(Src, TruncMask, DemandedElts, Known, TLO,
                             Depth + 1))
      return true;
    Known = Known.trunc(BitWidth);
 
    // Attempt to avoid multi-use ops if we don't need anything from them.
    if (SDValue NewSrc = SimplifyMultipleUseDemandedBits(
            Src, TruncMask, DemandedElts, TLO.DAG, Depth + 1))
      return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::TRUNCATE, dl, VT, NewSrc));
 
    // If the input is only used by this truncate, see if we can shrink it based
    // on the known demanded bits.
    switch (Src.getOpcode()) {
    default:
      break;
    case ISD::SRL:
      // Shrink SRL by a constant if none of the high bits shifted in are
      // demanded.
      if (TLO.LegalTypes() && !isTypeDesirableForOp(ISD::SRL, VT))
        // Do not turn (vt1 truncate (vt2 srl)) into (vt1 srl) if vt1 is
        // undesirable.
        break;
 
      if (Src.getNode()->hasOneUse()) {
        const APInt *ShAmtC =
            TLO.DAG.getValidShiftAmountConstant(Src, DemandedElts);
        if (!ShAmtC || ShAmtC->uge(BitWidth))
          break;
        uint64_t ShVal = ShAmtC->getZExtValue();
 
        APInt HighBits =
            APInt::getHighBitsSet(OperandBitWidth, OperandBitWidth - BitWidth);
        HighBits.lshrInPlace(ShVal);
        HighBits = HighBits.trunc(BitWidth);
 
        if (!(HighBits & DemandedBits)) {
          // None of the shifted in bits are needed.  Add a truncate of the
          // shift input, then shift it.
          SDValue NewShAmt = TLO.DAG.getConstant(
              ShVal, dl, getShiftAmountTy(VT, DL, TLO.LegalTypes()));
          SDValue NewTrunc =
              TLO.DAG.getNode(ISD::TRUNCATE, dl, VT, Src.getOperand(0));
          return TLO.CombineTo(
              Op, TLO.DAG.getNode(ISD::SRL, dl, VT, NewTrunc, NewShAmt));
        }
      }
      break;
    }
 
    assert(!Known.hasConflict() && "Bits known to be one AND zero?");
    break;
  }
  case ISD::AssertZext: {
    // AssertZext demands all of the high bits, plus any of the low bits
    // demanded by its users.
    EVT ZVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
    APInt InMask = APInt::getLowBitsSet(BitWidth, ZVT.getSizeInBits());
    if (SimplifyDemandedBits(Op.getOperand(0), ~InMask | DemandedBits, Known,
                             TLO, Depth + 1))
      return true;
    assert(!Known.hasConflict() && "Bits known to be one AND zero?");
 
    Known.Zero |= ~InMask;
    Known.One &= (~Known.Zero);
    break;
  }
  case ISD::EXTRACT_VECTOR_ELT: {
    SDValue Src = Op.getOperand(0);
    SDValue Idx = Op.getOperand(1);
    ElementCount SrcEltCnt = Src.getValueType().getVectorElementCount();
    unsigned EltBitWidth = Src.getScalarValueSizeInBits();
 
    if (SrcEltCnt.isScalable())
      return false;
 
    // Demand the bits from every vector element without a constant index.
    unsigned NumSrcElts = SrcEltCnt.getFixedValue();
    APInt DemandedSrcElts = APInt::getAllOnes(NumSrcElts);
    if (auto *CIdx = dyn_cast<ConstantSDNode>(Idx))
      if (CIdx->getAPIntValue().ult(NumSrcElts))
        DemandedSrcElts = APInt::getOneBitSet(NumSrcElts, CIdx->getZExtValue());
 
    // If BitWidth > EltBitWidth the value is anyext:ed. So we do not know
    // anything about the extended bits.
    APInt DemandedSrcBits = DemandedBits;
    if (BitWidth > EltBitWidth)
      DemandedSrcBits = DemandedSrcBits.trunc(EltBitWidth);
 
    if (SimplifyDemandedBits(Src, DemandedSrcBits, DemandedSrcElts, Known2, TLO,
                             Depth + 1))
      return true;
 
    // Attempt to avoid multi-use ops if we don't need anything from them.
    if (!DemandedSrcBits.isAllOnes() || !DemandedSrcElts.isAllOnes()) {
      if (SDValue DemandedSrc = SimplifyMultipleUseDemandedBits(
              Src, DemandedSrcBits, DemandedSrcElts, TLO.DAG, Depth + 1)) {
        SDValue NewOp =
            TLO.DAG.getNode(Op.getOpcode(), dl, VT, DemandedSrc, Idx);
        return TLO.CombineTo(Op, NewOp);
      }
    }
 
    Known = Known2;
    if (BitWidth > EltBitWidth)
      Known = Known.anyext(BitWidth);
    break;
  }
  case ISD::BITCAST: {
    SDValue Src = Op.getOperand(0);
    EVT SrcVT = Src.getValueType();
    unsigned NumSrcEltBits = SrcVT.getScalarSizeInBits();
 
    // If this is an FP->Int bitcast and if the sign bit is the only
    // thing demanded, turn this into a FGETSIGN.
    if (!TLO.LegalOperations() && !VT.isVector() && !SrcVT.isVector() &&
        DemandedBits == APInt::getSignMask(Op.getValueSizeInBits()) &&
        SrcVT.isFloatingPoint()) {
      bool OpVTLegal = isOperationLegalOrCustom(ISD::FGETSIGN, VT);
      bool i32Legal = isOperationLegalOrCustom(ISD::FGETSIGN, MVT::i32);
      if ((OpVTLegal || i32Legal) && VT.isSimple() && SrcVT != MVT::f16 &&
          SrcVT != MVT::f128) {
        // Cannot eliminate/lower SHL for f128 yet.
        EVT Ty = OpVTLegal ? VT : MVT::i32;
        // Make a FGETSIGN + SHL to move the sign bit into the appropriate
        // place.  We expect the SHL to be eliminated by other optimizations.
        SDValue Sign = TLO.DAG.getNode(ISD::FGETSIGN, dl, Ty, Src);
        unsigned OpVTSizeInBits = Op.getValueSizeInBits();
        if (!OpVTLegal && OpVTSizeInBits > 32)
          Sign = TLO.DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Sign);
        unsigned ShVal = Op.getValueSizeInBits() - 1;
        SDValue ShAmt = TLO.DAG.getConstant(ShVal, dl, VT);
        return TLO.CombineTo(Op,
                             TLO.DAG.getNode(ISD::SHL, dl, VT, Sign, ShAmt));
      }
    }
 
    // Bitcast from a vector using SimplifyDemanded Bits/VectorElts.
    // Demand the elt/bit if any of the original elts/bits are demanded.
    if (SrcVT.isVector() && (BitWidth % NumSrcEltBits) == 0) {
      unsigned Scale = BitWidth / NumSrcEltBits;
      unsigned NumSrcElts = SrcVT.getVectorNumElements();
      APInt DemandedSrcBits = APInt::getZero(NumSrcEltBits);
      APInt DemandedSrcElts = APInt::getZero(NumSrcElts);
      for (unsigned i = 0; i != Scale; ++i) {
        unsigned EltOffset = IsLE ? i : (Scale - 1 - i);
        unsigned BitOffset = EltOffset * NumSrcEltBits;
        APInt Sub = DemandedBits.extractBits(NumSrcEltBits, BitOffset);
        if (!Sub.isZero()) {
          DemandedSrcBits |= Sub;
          for (unsigned j = 0; j != NumElts; ++j)
            if (DemandedElts[j])
              DemandedSrcElts.setBit((j * Scale) + i);
        }
      }
 
      APInt KnownSrcUndef, KnownSrcZero;
      if (SimplifyDemandedVectorElts(Src, DemandedSrcElts, KnownSrcUndef,
                                     KnownSrcZero, TLO, Depth + 1))
        return true;
 
      KnownBits KnownSrcBits;
      if (SimplifyDemandedBits(Src, DemandedSrcBits, DemandedSrcElts,
                               KnownSrcBits, TLO, Depth + 1))
        return true;
    } else if (IsLE && (NumSrcEltBits % BitWidth) == 0) {
      // TODO - bigendian once we have test coverage.
      unsigned Scale = NumSrcEltBits / BitWidth;
      unsigned NumSrcElts = SrcVT.isVector() ? SrcVT.getVectorNumElements() : 1;
      APInt DemandedSrcBits = APInt::getZero(NumSrcEltBits);
      APInt DemandedSrcElts = APInt::getZero(NumSrcElts);
      for (unsigned i = 0; i != NumElts; ++i)
        if (DemandedElts[i]) {
          unsigned Offset = (i % Scale) * BitWidth;
          DemandedSrcBits.insertBits(DemandedBits, Offset);
          DemandedSrcElts.setBit(i / Scale);
        }
 
      if (SrcVT.isVector()) {
        APInt KnownSrcUndef, KnownSrcZero;
        if (SimplifyDemandedVectorElts(Src, DemandedSrcElts, KnownSrcUndef,
                                       KnownSrcZero, TLO, Depth + 1))
          return true;
      }
 
      KnownBits KnownSrcBits;
      if (SimplifyDemandedBits(Src, DemandedSrcBits, DemandedSrcElts,
                               KnownSrcBits, TLO, Depth + 1))
        return true;
    }
 
    // If this is a bitcast, let computeKnownBits handle it.  Only do this on a
    // recursive call where Known may be useful to the caller.
    if (Depth > 0) {
      Known = TLO.DAG.computeKnownBits(Op, DemandedElts, Depth);
      return false;
    }
    break;
  }
  case ISD::MUL:
    if (DemandedBits.isPowerOf2()) {
      // The LSB of X*Y is set only if (X & 1) == 1 and (Y & 1) == 1.
      // If we demand exactly one bit N and we have "X * (C' << N)" where C' is
      // odd (has LSB set), then the left-shifted low bit of X is the answer.
      unsigned CTZ = DemandedBits.countTrailingZeros();
      ConstantSDNode *C = isConstOrConstSplat(Op.getOperand(1), DemandedElts);
      if (C && C->getAPIntValue().countTrailingZeros() == CTZ) {
        EVT ShiftAmtTy = getShiftAmountTy(VT, TLO.DAG.getDataLayout());
        SDValue AmtC = TLO.DAG.getConstant(CTZ, dl, ShiftAmtTy);
        SDValue Shl = TLO.DAG.getNode(ISD::SHL, dl, VT, Op.getOperand(0), AmtC);
        return TLO.CombineTo(Op, Shl);
      }
    }
    // For a squared value "X * X", the bottom 2 bits are 0 and X[0] because:
    // X * X is odd iff X is odd.
    // 'Quadratic Reciprocity': X * X -> 0 for bit[1]
    if (Op.getOperand(0) == Op.getOperand(1) && DemandedBits.ult(4)) {
      SDValue One = TLO.DAG.getConstant(1, dl, VT);
      SDValue And1 = TLO.DAG.getNode(ISD::AND, dl, VT, Op.getOperand(0), One);
      return TLO.CombineTo(Op, And1);
    }
    [[fallthrough]];
  case ISD::ADD:
  case ISD::SUB: {
    // Add, Sub, and Mul don't demand any bits in positions beyond that
    // of the highest bit demanded of them.
    SDValue Op0 = Op.getOperand(0), Op1 = Op.getOperand(1);
    SDNodeFlags Flags = Op.getNode()->getFlags();
    unsigned DemandedBitsLZ = DemandedBits.countLeadingZeros();
    APInt LoMask = APInt::getLowBitsSet(BitWidth, BitWidth - DemandedBitsLZ);
    if (SimplifyDemandedBits(Op0, LoMask, DemandedElts, Known2, TLO,
                             Depth + 1) ||
        SimplifyDemandedBits(Op1, LoMask, DemandedElts, Known2, TLO,
                             Depth + 1) ||
        // See if the operation should be performed at a smaller bit width.
        ShrinkDemandedOp(Op, BitWidth, DemandedBits, TLO)) {
      if (Flags.hasNoSignedWrap() || Flags.hasNoUnsignedWrap()) {
        // Disable the nsw and nuw flags. We can no longer guarantee that we
        // won't wrap after simplification.
        Flags.setNoSignedWrap(false);
        Flags.setNoUnsignedWrap(false);
        Op->setFlags(Flags);
      }
      return true;
    }
 
    // Attempt to avoid multi-use ops if we don't need anything from them.
    if (!LoMask.isAllOnes() || !DemandedElts.isAllOnes()) {
      SDValue DemandedOp0 = SimplifyMultipleUseDemandedBits(
          Op0, LoMask, DemandedElts, TLO.DAG, Depth + 1);
      SDValue DemandedOp1 = SimplifyMultipleUseDemandedBits(
          Op1, LoMask, DemandedElts, TLO.DAG, Depth + 1);
      if (DemandedOp0 || DemandedOp1) {
        Flags.setNoSignedWrap(false);
        Flags.setNoUnsignedWrap(false);
        Op0 = DemandedOp0 ? DemandedOp0 : Op0;
        Op1 = DemandedOp1 ? DemandedOp1 : Op1;
        SDValue NewOp =
            TLO.DAG.getNode(Op.getOpcode(), dl, VT, Op0, Op1, Flags);
        return TLO.CombineTo(Op, NewOp);
      }
    }
 
    // If we have a constant operand, we may be able to turn it into -1 if we
    // do not demand the high bits. This can make the constant smaller to
    // encode, allow more general folding, or match specialized instruction
    // patterns (eg, 'blsr' on x86). Don't bother changing 1 to -1 because that
    // is probably not useful (and could be detrimental).
    ConstantSDNode *C = isConstOrConstSplat(Op1);
    APInt HighMask = APInt::getHighBitsSet(BitWidth, DemandedBitsLZ);
    if (C && !C->isAllOnes() && !C->isOne() &&
        (C->getAPIntValue() | HighMask).isAllOnes()) {
      SDValue Neg1 = TLO.DAG.getAllOnesConstant(dl, VT);
      // Disable the nsw and nuw flags. We can no longer guarantee that we
      // won't wrap after simplification.
      Flags.setNoSignedWrap(false);
      Flags.setNoUnsignedWrap(false);
      SDValue NewOp = TLO.DAG.getNode(Op.getOpcode(), dl, VT, Op0, Neg1, Flags);
      return TLO.CombineTo(Op, NewOp);
    }
 
    // Match a multiply with a disguised negated-power-of-2 and convert to a
    // an equivalent shift-left amount.
    // Example: (X * MulC) + Op1 --> Op1 - (X << log2(-MulC))
    auto getShiftLeftAmt = [&HighMask](SDValue Mul) -> unsigned {
      if (Mul.getOpcode() != ISD::MUL || !Mul.hasOneUse())
        return 0;
 
      // Don't touch opaque constants. Also, ignore zero and power-of-2
      // multiplies. Those will get folded later.
      ConstantSDNode *MulC = isConstOrConstSplat(Mul.getOperand(1));
      if (MulC && !MulC->isOpaque() && !MulC->isZero() &&
          !MulC->getAPIntValue().isPowerOf2()) {
        APInt UnmaskedC = MulC->getAPIntValue() | HighMask;
        if (UnmaskedC.isNegatedPowerOf2())
          return (-UnmaskedC).logBase2();
      }
      return 0;
    };
 
    auto foldMul = [&](ISD::NodeType NT, SDValue X, SDValue Y, unsigned ShlAmt) {
      EVT ShiftAmtTy = getShiftAmountTy(VT, TLO.DAG.getDataLayout());
      SDValue ShlAmtC = TLO.DAG.getConstant(ShlAmt, dl, ShiftAmtTy);
      SDValue Shl = TLO.DAG.getNode(ISD::SHL, dl, VT, X, ShlAmtC);
      SDValue Res = TLO.DAG.getNode(NT, dl, VT, Y, Shl);
      return TLO.CombineTo(Op, Res);
    };
 
    if (isOperationLegalOrCustom(ISD::SHL, VT)) {
      if (Op.getOpcode() == ISD::ADD) {
        // (X * MulC) + Op1 --> Op1 - (X << log2(-MulC))
        if (unsigned ShAmt = getShiftLeftAmt(Op0))
          return foldMul(ISD::SUB, Op0.getOperand(0), Op1, ShAmt);
        // Op0 + (X * MulC) --> Op0 - (X << log2(-MulC))
        if (unsigned ShAmt = getShiftLeftAmt(Op1))
          return foldMul(ISD::SUB, Op1.getOperand(0), Op0, ShAmt);
      }
      if (Op.getOpcode() == ISD::SUB) {
        // Op0 - (X * MulC) --> Op0 + (X << log2(-MulC))
        if (unsigned ShAmt = getShiftLeftAmt(Op1))
          return foldMul(ISD::ADD, Op1.getOperand(0), Op0, ShAmt);
      }
    }
 
    [[fallthrough]];
  }
  default:
    if (Op.getOpcode() >= ISD::BUILTIN_OP_END) {
      if (SimplifyDemandedBitsForTargetNode(Op, DemandedBits, DemandedElts,
                                            Known, TLO, Depth))
        return true;
      break;
    }
 
    // Just use computeKnownBits to compute output bits.
    Known = TLO.DAG.computeKnownBits(Op, DemandedElts, Depth);
    break;
  }
 
  // If we know the value of all of the demanded bits, return this as a
  // constant.
  if (!isTargetCanonicalConstantNode(Op) &&
      DemandedBits.isSubsetOf(Known.Zero | Known.One)) {
    // Avoid folding to a constant if any OpaqueConstant is involved.
    const SDNode *N = Op.getNode();
    for (SDNode *Op :
         llvm::make_range(SDNodeIterator::begin(N), SDNodeIterator::end(N))) {
      if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op))
        if (C->isOpaque())
          return false;
    }
    if (VT.isInteger())
      return TLO.CombineTo(Op, TLO.DAG.getConstant(Known.One, dl, VT));
    if (VT.isFloatingPoint())
      return TLO.CombineTo(
          Op,
          TLO.DAG.getConstantFP(
              APFloat(TLO.DAG.EVTToAPFloatSemantics(VT), Known.One), dl, VT));
  }
 
  // A multi use 'all demanded elts' simplify failed to find any knownbits.
  // Try again just for the original demanded elts.
  // Ensure we do this AFTER constant folding above.
  if (HasMultiUse && Known.isUnknown() && !OriginalDemandedElts.isAllOnes())
    Known = TLO.DAG.computeKnownBits(Op, OriginalDemandedElts, Depth);
 
  return false;
}
 
bool TargetLowering::SimplifyDemandedVectorElts(SDValue Op,
                                                const APInt &DemandedElts,
                                                DAGCombinerInfo &DCI) const {
  SelectionDAG &DAG = DCI.DAG;
  TargetLoweringOpt TLO(DAG, !DCI.isBeforeLegalize(),
                        !DCI.isBeforeLegalizeOps());
 
  APInt KnownUndef, KnownZero;
  bool Simplified =
      SimplifyDemandedVectorElts(Op, DemandedElts, KnownUndef, KnownZero, TLO);
  if (Simplified) {
    DCI.AddToWorklist(Op.getNode());
    DCI.CommitTargetLoweringOpt(TLO);
  }
 
  return Simplified;
}
 
/// Given a vector binary operation and known undefined elements for each input
/// operand, compute whether each element of the output is undefined.
static APInt getKnownUndefForVectorBinop(SDValue BO, SelectionDAG &DAG,
                                         const APInt &UndefOp0,
                                         const APInt &UndefOp1) {
  EVT VT = BO.getValueType();
  assert(DAG.getTargetLoweringInfo().isBinOp(BO.getOpcode()) && VT.isVector() &&
         "Vector binop only");
 
  EVT EltVT = VT.getVectorElementType();
  unsigned NumElts = VT.getVectorNumElements();
  assert(UndefOp0.getBitWidth() == NumElts &&
         UndefOp1.getBitWidth() == NumElts && "Bad type for undef analysis");
 
  auto getUndefOrConstantElt = [&](SDValue V, unsigned Index,
                                   const APInt &UndefVals) {
    if (UndefVals[Index])
      return DAG.getUNDEF(EltVT);
 
    if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
      // Try hard to make sure that the getNode() call is not creating temporary
      // nodes. Ignore opaque integers because they do not constant fold.
      SDValue Elt = BV->getOperand(Index);
      auto *C = dyn_cast<ConstantSDNode>(Elt);
      if (isa<ConstantFPSDNode>(Elt) || Elt.isUndef() || (C && !C->isOpaque()))
        return Elt;
    }
 
    return SDValue();
  };
 
  APInt KnownUndef = APInt::getZero(NumElts);
  for (unsigned i = 0; i != NumElts; ++i) {
    // If both inputs for this element are either constant or undef and match
    // the element type, compute the constant/undef result for this element of
    // the vector.
    // TODO: Ideally we would use FoldConstantArithmetic() here, but that does
    // not handle FP constants. The code within getNode() should be refactored
    // to avoid the danger of creating a bogus temporary node here.
    SDValue C0 = getUndefOrConstantElt(BO.getOperand(0), i, UndefOp0);
    SDValue C1 = getUndefOrConstantElt(BO.getOperand(1), i, UndefOp1);
    if (C0 && C1 && C0.getValueType() == EltVT && C1.getValueType() == EltVT)
      if (DAG.getNode(BO.getOpcode(), SDLoc(BO), EltVT, C0, C1).isUndef())
        KnownUndef.setBit(i);
  }
  return KnownUndef;
}
 
bool TargetLowering::SimplifyDemandedVectorElts(
    SDValue Op, const APInt &OriginalDemandedElts, APInt &KnownUndef,
    APInt &KnownZero, TargetLoweringOpt &TLO, unsigned Depth,
    bool AssumeSingleUse) const {
  EVT VT = Op.getValueType();
  unsigned Opcode = Op.getOpcode();
  APInt DemandedElts = OriginalDemandedElts;
  unsigned NumElts = DemandedElts.getBitWidth();
  assert(VT.isVector() && "Expected vector op");
 
  KnownUndef = KnownZero = APInt::getZero(NumElts);
 
  const TargetLowering &TLI = TLO.DAG.getTargetLoweringInfo();
  if (!TLI.shouldSimplifyDemandedVectorElts(Op, TLO))
    return false;
 
  // TODO: For now we assume we know nothing about scalable vectors.
  if (VT.isScalableVector())
    return false;
 
  assert(VT.getVectorNumElements() == NumElts &&
         "Mask size mismatches value type element count!");
 
  // Undef operand.
  if (Op.isUndef()) {
    KnownUndef.setAllBits();
    return false;
  }
 
  // If Op has other users, assume that all elements are needed.
  if (!AssumeSingleUse && !Op.getNode()->hasOneUse())
    DemandedElts.setAllBits();
 
  // Not demanding any elements from Op.
  if (DemandedElts == 0) {
    KnownUndef.setAllBits();
    return TLO.CombineTo(Op, TLO.DAG.getUNDEF(VT));
  }
 
  // Limit search depth.
  if (Depth >= SelectionDAG::MaxRecursionDepth)
    return false;
 
  SDLoc DL(Op);
  unsigned EltSizeInBits = VT.getScalarSizeInBits();
  bool IsLE = TLO.DAG.getDataLayout().isLittleEndian();
 
  // Helper for demanding the specified elements and all the bits of both binary
  // operands.
  auto SimplifyDemandedVectorEltsBinOp = [&](SDValue Op0, SDValue Op1) {
    SDValue NewOp0 = SimplifyMultipleUseDemandedVectorElts(Op0, DemandedElts,
                                                           TLO.DAG, Depth + 1);
    SDValue NewOp1 = SimplifyMultipleUseDemandedVectorElts(Op1, DemandedElts,
                                                           TLO.DAG, Depth + 1);
    if (NewOp0 || NewOp1) {
      SDValue NewOp = TLO.DAG.getNode(
          Opcode, SDLoc(Op), VT, NewOp0 ? NewOp0 : Op0, NewOp1 ? NewOp1 : Op1);
      return TLO.CombineTo(Op, NewOp);
    }
    return false;
  };
 
  switch (Opcode) {
  case ISD::SCALAR_TO_VECTOR: {
    if (!DemandedElts[0]) {
      KnownUndef.setAllBits();
      return TLO.CombineTo(Op, TLO.DAG.getUNDEF(VT));
    }
    SDValue ScalarSrc = Op.getOperand(0);
    if (ScalarSrc.getOpcode() == ISD::EXTRACT_VECTOR_ELT) {
      SDValue Src = ScalarSrc.getOperand(0);
      SDValue Idx = ScalarSrc.getOperand(1);
      EVT SrcVT = Src.getValueType();
 
      ElementCount SrcEltCnt = SrcVT.getVectorElementCount();
 
      if (SrcEltCnt.isScalable())
        return false;
 
      unsigned NumSrcElts = SrcEltCnt.getFixedValue();
      if (isNullConstant(Idx)) {
        APInt SrcDemandedElts = APInt::getOneBitSet(NumSrcElts, 0);
        APInt SrcUndef = KnownUndef.zextOrTrunc(NumSrcElts);
        APInt SrcZero = KnownZero.zextOrTrunc(NumSrcElts);
        if (SimplifyDemandedVectorElts(Src, SrcDemandedElts, SrcUndef, SrcZero,
                                       TLO, Depth + 1))
          return true;
      }
    }
    KnownUndef.setHighBits(NumElts - 1);
    break;
  }
  case ISD::BITCAST: {
    SDValue Src = Op.getOperand(0);
    EVT SrcVT = Src.getValueType();
 
    // We only handle vectors here.
    // TODO - investigate calling SimplifyDemandedBits/ComputeKnownBits?
    if (!SrcVT.isVector())
      break;
 
    // Fast handling of 'identity' bitcasts.
    unsigned NumSrcElts = SrcVT.getVectorNumElements();
    if (NumSrcElts == NumElts)
      return SimplifyDemandedVectorElts(Src, DemandedElts, KnownUndef,
                                        KnownZero, TLO, Depth + 1);
 
    APInt SrcDemandedElts, SrcZero, SrcUndef;
 
    // Bitcast from 'large element' src vector to 'small element' vector, we
    // must demand a source element if any DemandedElt maps to it.
    if ((NumElts % NumSrcElts) == 0) {
      unsigned Scale = NumElts / NumSrcElts;
      SrcDemandedElts = APIntOps::ScaleBitMask(DemandedElts, NumSrcElts);
      if (SimplifyDemandedVectorElts(Src, SrcDemandedElts, SrcUndef, SrcZero,
                                     TLO, Depth + 1))
        return true;
 
      // Try calling SimplifyDemandedBits, converting demanded elts to the bits
      // of the large element.
      // TODO - bigendian once we have test coverage.
      if (IsLE) {
        unsigned SrcEltSizeInBits = SrcVT.getScalarSizeInBits();
        APInt SrcDemandedBits = APInt::getZero(SrcEltSizeInBits);
        for (unsigned i = 0; i != NumElts; ++i)
          if (DemandedElts[i]) {
            unsigned Ofs = (i % Scale) * EltSizeInBits;
            SrcDemandedBits.setBits(Ofs, Ofs + EltSizeInBits);
          }
 
        KnownBits Known;
        if (SimplifyDemandedBits(Src, SrcDemandedBits, SrcDemandedElts, Known,
                                 TLO, Depth + 1))
          return true;
 
        // The bitcast has split each wide element into a number of
        // narrow subelements. We have just computed the Known bits
        // for wide elements. See if element splitting results in
        // some subelements being zero. Only for demanded elements!
        for (unsigned SubElt = 0; SubElt != Scale; ++SubElt) {
          if (!Known.Zero.extractBits(EltSizeInBits, SubElt * EltSizeInBits)
                   .isAllOnes())
            continue;
          for (unsigned SrcElt = 0; SrcElt != NumSrcElts; ++SrcElt) {
            unsigned Elt = Scale * SrcElt + SubElt;
            if (DemandedElts[Elt])
              KnownZero.setBit(Elt);
          }
        }
      }
 
      // If the src element is zero/undef then all the output elements will be -
      // only demanded elements are guaranteed to be correct.
      for (unsigned i = 0; i != NumSrcElts; ++i) {
        if (SrcDemandedElts[i]) {
          if (SrcZero[i])
            KnownZero.setBits(i * Scale, (i + 1) * Scale);
          if (SrcUndef[i])
            KnownUndef.setBits(i * Scale, (i + 1) * Scale);
        }
      }
    }
 
    // Bitcast from 'small element' src vector to 'large element' vector, we
    // demand all smaller source elements covered by the larger demanded element
    // of this vector.
    if ((NumSrcElts % NumElts) == 0) {
      unsigned Scale = NumSrcElts / NumElts;
      SrcDemandedElts = APIntOps::ScaleBitMask(DemandedElts, NumSrcElts);
      if (SimplifyDemandedVectorElts(Src, SrcDemandedElts, SrcUndef, SrcZero,
                                     TLO, Depth + 1))
        return true;
 
      // If all the src elements covering an output element are zero/undef, then
      // the output element will be as well, assuming it was demanded.
      for (unsigned i = 0; i != NumElts; ++i) {
        if (DemandedElts[i]) {
          if (SrcZero.extractBits(Scale, i * Scale).isAllOnes())
            KnownZero.setBit(i);
          if (SrcUndef.extractBits(Scale, i * Scale).isAllOnes())
            KnownUndef.setBit(i);
        }
      }
    }
    break;
  }
  case ISD::BUILD_VECTOR: {
    // Check all elements and simplify any unused elements with UNDEF.
    if (!DemandedElts.isAllOnes()) {
      // Don't simplify BROADCASTS.
      if (llvm::any_of(Op->op_values(),
                       [&](SDValue Elt) { return Op.getOperand(0) != Elt; })) {
        SmallVector<SDValue, 32> Ops(Op->op_begin(), Op->op_end());
        bool Updated = false;
        for (unsigned i = 0; i != NumElts; ++i) {
          if (!DemandedElts[i] && !Ops[i].isUndef()) {
            Ops[i] = TLO.DAG.getUNDEF(Ops[0].getValueType());
            KnownUndef.setBit(i);
            Updated = true;
          }
        }
        if (Updated)
          return TLO.CombineTo(Op, TLO.DAG.getBuildVector(VT, DL, Ops));
      }
    }
    for (unsigned i = 0; i != NumElts; ++i) {
      SDValue SrcOp = Op.getOperand(i);
      if (SrcOp.isUndef()) {
        KnownUndef.setBit(i);
      } else if (EltSizeInBits == SrcOp.getScalarValueSizeInBits() &&
                 (isNullConstant(SrcOp) || isNullFPConstant(SrcOp))) {
        KnownZero.setBit(i);
      }
    }
    break;
  }
  case ISD::CONCAT_VECTORS: {
    EVT SubVT = Op.getOperand(0).getValueType();
    unsigned NumSubVecs = Op.getNumOperands();
    unsigned NumSubElts = SubVT.getVectorNumElements();
    for (unsigned i = 0; i != NumSubVecs; ++i) {
      SDValue SubOp = Op.getOperand(i);
      APInt SubElts = DemandedElts.extractBits(NumSubElts, i * NumSubElts);
      APInt SubUndef, SubZero;
      if (SimplifyDemandedVectorElts(SubOp, SubElts, SubUndef, SubZero, TLO,
                                     Depth + 1))
        return true;
      KnownUndef.insertBits(SubUndef, i * NumSubElts);
      KnownZero.insertBits(SubZero, i * NumSubElts);
    }
 
    // Attempt to avoid multi-use ops if we don't need anything from them.
    if (!DemandedElts.isAllOnes()) {
      bool FoundNewSub = false;
      SmallVector<SDValue, 2> DemandedSubOps;
      for (unsigned i = 0; i != NumSubVecs; ++i) {
        SDValue SubOp = Op.getOperand(i);
        APInt SubElts = DemandedElts.extractBits(NumSubElts, i * NumSubElts);
        SDValue NewSubOp = SimplifyMultipleUseDemandedVectorElts(
            SubOp, SubElts, TLO.DAG, Depth + 1);
        DemandedSubOps.push_back(NewSubOp ? NewSubOp : SubOp);
        FoundNewSub = NewSubOp ? true : FoundNewSub;
      }
      if (FoundNewSub) {
        SDValue NewOp =
            TLO.DAG.getNode(Op.getOpcode(), SDLoc(Op), VT, DemandedSubOps);
        return TLO.CombineTo(Op, NewOp);
      }
    }
    break;
  }
  case ISD::INSERT_SUBVECTOR: {
    // Demand any elements from the subvector and the remainder from the src its
    // inserted into.
    SDValue Src = Op.getOperand(0);
    SDValue Sub = Op.getOperand(1);
    uint64_t Idx = Op.getConstantOperandVal(2);
    unsigned NumSubElts = Sub.getValueType().getVectorNumElements();
    APInt DemandedSubElts = DemandedElts.extractBits(NumSubElts, Idx);
    APInt DemandedSrcElts = DemandedElts;
    DemandedSrcElts.insertBits(APInt::getZero(NumSubElts), Idx);
 
    APInt SubUndef, SubZero;
    if (SimplifyDemandedVectorElts(Sub, DemandedSubElts, SubUndef, SubZero, TLO,
                                   Depth + 1))
      return true;
 
    // If none of the src operand elements are demanded, replace it with undef.
    if (!DemandedSrcElts && !Src.isUndef())
      return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::INSERT_SUBVECTOR, DL, VT,
                                               TLO.DAG.getUNDEF(VT), Sub,
                                               Op.getOperand(2)));
 
    if (SimplifyDemandedVectorElts(Src, DemandedSrcElts, KnownUndef, KnownZero,
                                   TLO, Depth + 1))
      return true;
    KnownUndef.insertBits(SubUndef, Idx);
    KnownZero.insertBits(SubZero, Idx);
 
    // Attempt to avoid multi-use ops if we don't need anything from them.
    if (!DemandedSrcElts.isAllOnes() || !DemandedSubElts.isAllOnes()) {
      SDValue NewSrc = SimplifyMultipleUseDemandedVectorElts(
          Src, DemandedSrcElts, TLO.DAG, Depth + 1);
      SDValue NewSub = SimplifyMultipleUseDemandedVectorElts(
          Sub, DemandedSubElts, TLO.DAG, Depth + 1);
      if (NewSrc || NewSub) {
        NewSrc = NewSrc ? NewSrc : Src;
        NewSub = NewSub ? NewSub : Sub;
        SDValue NewOp = TLO.DAG.getNode(Op.getOpcode(), SDLoc(Op), VT, NewSrc,
                                        NewSub, Op.getOperand(2));
        return TLO.CombineTo(Op, NewOp);
      }
    }
    break;
  }
  case ISD::EXTRACT_SUBVECTOR: {
    // Offset the demanded elts by the subvector index.
    SDValue Src = Op.getOperand(0);
    if (Src.getValueType().isScalableVector())
      break;
    uint64_t Idx = Op.getConstantOperandVal(1);
    unsigned NumSrcElts = Src.getValueType().getVectorNumElements();
    APInt DemandedSrcElts = DemandedElts.zext(NumSrcElts).shl(Idx);
 
    APInt SrcUndef, SrcZero;
    if (SimplifyDemandedVectorElts(Src, DemandedSrcElts, SrcUndef, SrcZero, TLO,
                                   Depth + 1))
      return true;
    KnownUndef = SrcUndef.extractBits(NumElts, Idx);
    KnownZero = SrcZero.extractBits(NumElts, Idx);
 
    // Attempt to avoid multi-use ops if we don't need anything from them.
    if (!DemandedElts.isAllOnes()) {
      SDValue NewSrc = SimplifyMultipleUseDemandedVectorElts(
          Src, DemandedSrcElts, TLO.DAG, Depth + 1);
      if (NewSrc) {
        SDValue NewOp = TLO.DAG.getNode(Op.getOpcode(), SDLoc(Op), VT, NewSrc,
                                        Op.getOperand(1));
        return TLO.CombineTo(Op, NewOp);
      }
    }
    break;
  }
  case ISD::INSERT_VECTOR_ELT: {
    SDValue Vec = Op.getOperand(0);
    SDValue Scl = Op.getOperand(1);
    auto *CIdx = dyn_cast<ConstantSDNode>(Op.getOperand(2));
 
    // For a legal, constant insertion index, if we don't need this insertion
    // then strip it, else remove it from the demanded elts.
    if (CIdx && CIdx->getAPIntValue().ult(NumElts)) {
      unsigned Idx = CIdx->getZExtValue();
      if (!DemandedElts[Idx])
        return TLO.CombineTo(Op, Vec);
 
      APInt DemandedVecElts(DemandedElts);
      DemandedVecElts.clearBit(Idx);
      if (SimplifyDemandedVectorElts(Vec, DemandedVecElts, KnownUndef,
                                     KnownZero, TLO, Depth + 1))
        return true;
 
      KnownUndef.setBitVal(Idx, Scl.isUndef());
 
      KnownZero.setBitVal(Idx, isNullConstant(Scl) || isNullFPConstant(Scl));
      break;
    }
 
    APInt VecUndef, VecZero;
    if (SimplifyDemandedVectorElts(Vec, DemandedElts, VecUndef, VecZero, TLO,
                                   Depth + 1))
      return true;
    // Without knowing the insertion index we can't set KnownUndef/KnownZero.
    break;
  }
  case ISD::VSELECT: {
    SDValue Sel = Op.getOperand(0);
    SDValue LHS = Op.getOperand(1);
    SDValue RHS = Op.getOperand(2);
 
    // Try to transform the select condition based on the current demanded
    // elements.
    APInt UndefSel, UndefZero;
    if (SimplifyDemandedVectorElts(Sel, DemandedElts, UndefSel, UndefZero, TLO,
                                   Depth + 1))
      return true;
 
    // See if we can simplify either vselect operand.
    APInt DemandedLHS(DemandedElts);
    APInt DemandedRHS(DemandedElts);
    APInt UndefLHS, ZeroLHS;
    APInt UndefRHS, ZeroRHS;
    if (SimplifyDemandedVectorElts(LHS, DemandedLHS, UndefLHS, ZeroLHS, TLO,
                                   Depth + 1))
      return true;
    if (SimplifyDemandedVectorElts(RHS, DemandedRHS, UndefRHS, ZeroRHS, TLO,
                                   Depth + 1))
      return true;
 
    KnownUndef = UndefLHS & UndefRHS;
    KnownZero = ZeroLHS & ZeroRHS;
 
    // If we know that the selected element is always zero, we don't need the
    // select value element.
    APInt DemandedSel = DemandedElts & ~KnownZero;
    if (DemandedSel != DemandedElts)
      if (SimplifyDemandedVectorElts(Sel, DemandedSel, UndefSel, UndefZero, TLO,
                                     Depth + 1))
        return true;
 
    break;
  }
  case ISD::VECTOR_SHUFFLE: {
    SDValue LHS = Op.getOperand(0);
    SDValue RHS = Op.getOperand(1);
    ArrayRef<int> ShuffleMask = cast<ShuffleVectorSDNode>(Op)->getMask();
 
    // Collect demanded elements from shuffle operands..
    APInt DemandedLHS(NumElts, 0);
    APInt DemandedRHS(NumElts, 0);
    for (unsigned i = 0; i != NumElts; ++i) {
      int M = ShuffleMask[i];
      if (M < 0 || !DemandedElts[i])
        continue;
      assert(0 <= M && M < (int)(2 * NumElts) && "Shuffle index out of range");
      if (M < (int)NumElts)
        DemandedLHS.setBit(M);
      else
        DemandedRHS.setBit(M - NumElts);
    }
 
    // See if we can simplify either shuffle operand.
    APInt UndefLHS, ZeroLHS;
    APInt UndefRHS, ZeroRHS;
    if (SimplifyDemandedVectorElts(LHS, DemandedLHS, UndefLHS, ZeroLHS, TLO,
                                   Depth + 1))
      return true;
    if (SimplifyDemandedVectorElts(RHS, DemandedRHS, UndefRHS, ZeroRHS, TLO,
                                   Depth + 1))
      return true;
 
    // Simplify mask using undef elements from LHS/RHS.
    bool Updated = false;
    bool IdentityLHS = true, IdentityRHS = true;
    SmallVector<int, 32> NewMask(ShuffleMask);
    for (unsigned i = 0; i != NumElts; ++i) {
      int &M = NewMask[i];
      if (M < 0)
        continue;
      if (!DemandedElts[i] || (M < (int)NumElts && UndefLHS[M]) ||
          (M >= (int)NumElts && UndefRHS[M - NumElts])) {
        Updated = true;
        M = -1;
      }
      IdentityLHS &= (M < 0) || (M == (int)i);
      IdentityRHS &= (M < 0) || ((M - NumElts) == i);
    }
 
    // Update legal shuffle masks based on demanded elements if it won't reduce
    // to Identity which can cause premature removal of the shuffle mask.
    if (Updated && !IdentityLHS && !IdentityRHS && !TLO.LegalOps) {
      SDValue LegalShuffle =
          buildLegalVectorShuffle(VT, DL, LHS, RHS, NewMask, TLO.DAG);
      if (LegalShuffle)
        return TLO.CombineTo(Op, LegalShuffle);
    }
 
    // Propagate undef/zero elements from LHS/RHS.
    for (unsigned i = 0; i != NumElts; ++i) {
      int M = ShuffleMask[i];
      if (M < 0) {
        KnownUndef.setBit(i);
      } else if (M < (int)NumElts) {
        if (UndefLHS[M])
          KnownUndef.setBit(i);
        if (ZeroLHS[M])
          KnownZero.setBit(i);
      } else {
        if (UndefRHS[M - NumElts])
          KnownUndef.setBit(i);
        if (ZeroRHS[M - NumElts])
          KnownZero.setBit(i);
      }
    }
    break;
  }
  case ISD::ANY_EXTEND_VECTOR_INREG:
  case ISD::SIGN_EXTEND_VECTOR_INREG:
  case ISD::ZERO_EXTEND_VECTOR_INREG: {
    APInt SrcUndef, SrcZero;
    SDValue Src = Op.getOperand(0);
    unsigned NumSrcElts = Src.getValueType().getVectorNumElements();
    APInt DemandedSrcElts = DemandedElts.zext(NumSrcElts);
    if (SimplifyDemandedVectorElts(Src, DemandedSrcElts, SrcUndef, SrcZero, TLO,
                                   Depth + 1))
      return true;
    KnownZero = SrcZero.zextOrTrunc(NumElts);
    KnownUndef = SrcUndef.zextOrTrunc(NumElts);
 
    if (IsLE && Op.getOpcode() == ISD::ANY_EXTEND_VECTOR_INREG &&
        Op.getValueSizeInBits() == Src.getValueSizeInBits() &&
        DemandedSrcElts == 1) {
      // aext - if we just need the bottom element then we can bitcast.
      return TLO.CombineTo(Op, TLO.DAG.getBitcast(VT, Src));
    }
 
    if (Op.getOpcode() == ISD::ZERO_EXTEND_VECTOR_INREG) {
      // zext(undef) upper bits are guaranteed to be zero.
      if (DemandedElts.isSubsetOf(KnownUndef))
        return TLO.CombineTo(Op, TLO.DAG.getConstant(0, SDLoc(Op), VT));
      KnownUndef.clearAllBits();
 
      // zext - if we just need the bottom element then we can mask:
      // zext(and(x,c)) -> and(x,c') iff the zext is the only user of the and.
      if (IsLE && DemandedSrcElts == 1 && Src.getOpcode() == ISD::AND &&
          Op->isOnlyUserOf(Src.getNode()) &&
          Op.getValueSizeInBits() == Src.getValueSizeInBits()) {
        SDLoc DL(Op);
        EVT SrcVT = Src.getValueType();
        EVT SrcSVT = SrcVT.getScalarType();
        SmallVector<SDValue> MaskElts;
        MaskElts.push_back(TLO.DAG.getAllOnesConstant(DL, SrcSVT));
        MaskElts.append(NumSrcElts - 1, TLO.DAG.getConstant(0, DL, SrcSVT));
        SDValue Mask = TLO.DAG.getBuildVector(SrcVT, DL, MaskElts);
        if (SDValue Fold = TLO.DAG.FoldConstantArithmetic(
                ISD::AND, DL, SrcVT, {Src.getOperand(1), Mask})) {
          Fold = TLO.DAG.getNode(ISD::AND, DL, SrcVT, Src.getOperand(0), Fold);
          return TLO.CombineTo(Op, TLO.DAG.getBitcast(VT, Fold));
        }
      }
    }
    break;
  }
 
  // TODO: There are more binop opcodes that could be handled here - MIN,
  // MAX, saturated math, etc.
  case ISD::ADD: {
    SDValue Op0 = Op.getOperand(0);
    SDValue Op1 = Op.getOperand(1);
    if (Op0 == Op1 && Op->isOnlyUserOf(Op0.getNode())) {
      APInt UndefLHS, ZeroLHS;
      if (SimplifyDemandedVectorElts(Op0, DemandedElts, UndefLHS, ZeroLHS, TLO,
                                     Depth + 1, /*AssumeSingleUse*/ true))
        return true;
    }
    [[fallthrough]];
  }
  case ISD::OR:
  case ISD::XOR:
  case ISD::SUB:
  case ISD::FADD:
  case ISD::FSUB:
  case ISD::FMUL:
  case ISD::FDIV:
  case ISD::FREM: {
    SDValue Op0 = Op.getOperand(0);
    SDValue Op1 = Op.getOperand(1);
 
    APInt UndefRHS, ZeroRHS;
    if (SimplifyDemandedVectorElts(Op1, DemandedElts, UndefRHS, ZeroRHS, TLO,
                                   Depth + 1))
      return true;
    APInt UndefLHS, ZeroLHS;
    if (SimplifyDemandedVectorElts(Op0, DemandedElts, UndefLHS, ZeroLHS, TLO,
                                   Depth + 1))
      return true;
 
    KnownZero = ZeroLHS & ZeroRHS;
    KnownUndef = getKnownUndefForVectorBinop(Op, TLO.DAG, UndefLHS, UndefRHS);
 
    // Attempt to avoid multi-use ops if we don't need anything from them.
    // TODO - use KnownUndef to relax the demandedelts?
    if (!DemandedElts.isAllOnes())
      if (SimplifyDemandedVectorEltsBinOp(Op0, Op1))
        return true;
    break;
  }
  case ISD::SHL:
  case ISD::SRL:
  case ISD::SRA:
  case ISD::ROTL:
  case ISD::ROTR: {
    SDValue Op0 = Op.getOperand(0);
    SDValue Op1 = Op.getOperand(1);
 
    APInt UndefRHS, ZeroRHS;
    if (SimplifyDemandedVectorElts(Op1, DemandedElts, UndefRHS, ZeroRHS, TLO,
                                   Depth + 1))
      return true;
    APInt UndefLHS, ZeroLHS;
    if (SimplifyDemandedVectorElts(Op0, DemandedElts, UndefLHS, ZeroLHS, TLO,
                                   Depth + 1))
      return true;
 
    KnownZero = ZeroLHS;
    KnownUndef = UndefLHS & UndefRHS; // TODO: use getKnownUndefForVectorBinop?
 
    // Attempt to avoid multi-use ops if we don't need anything from them.
    // TODO - use KnownUndef to relax the demandedelts?
    if (!DemandedElts.isAllOnes())
      if (SimplifyDemandedVectorEltsBinOp(Op0, Op1))
        return true;
    break;
  }
  case ISD::MUL:
  case ISD::MULHU:
  case ISD::MULHS:
  case ISD::AND: {
    SDValue Op0 = Op.getOperand(0);
    SDValue Op1 = Op.getOperand(1);
 
    APInt SrcUndef, SrcZero;
    if (SimplifyDemandedVectorElts(Op1, DemandedElts, SrcUndef, SrcZero, TLO,
                                   Depth + 1))
      return true;
    // If we know that a demanded element was zero in Op1 we don't need to
    // demand it in Op0 - its guaranteed to be zero.
    APInt DemandedElts0 = DemandedElts & ~SrcZero;
    if (SimplifyDemandedVectorElts(Op0, DemandedElts0, KnownUndef, KnownZero,
                                   TLO, Depth + 1))
      return true;
 
    KnownUndef &= DemandedElts0;
    KnownZero &= DemandedElts0;
 
    // If every element pair has a zero/undef then just fold to zero.
    // fold (and x, undef) -> 0  /  (and x, 0) -> 0
    // fold (mul x, undef) -> 0  /  (mul x, 0) -> 0
    if (DemandedElts.isSubsetOf(SrcZero | KnownZero | SrcUndef | KnownUndef))
      return TLO.CombineTo(Op, TLO.DAG.getConstant(0, SDLoc(Op), VT));
 
    // If either side has a zero element, then the result element is zero, even
    // if the other is an UNDEF.
    // TODO: Extend getKnownUndefForVectorBinop to also deal with known zeros
    // and then handle 'and' nodes with the rest of the binop opcodes.
    KnownZero |= SrcZero;
    KnownUndef &= SrcUndef;
    KnownUndef &= ~KnownZero;
 
    // Attempt to avoid multi-use ops if we don't need anything from them.
    if (!DemandedElts.isAllOnes())
      if (SimplifyDemandedVectorEltsBinOp(Op0, Op1))
        return true;
    break;
  }
  case ISD::TRUNCATE:
  case ISD::SIGN_EXTEND:
  case ISD::ZERO_EXTEND:
    if (SimplifyDemandedVectorElts(Op.getOperand(0), DemandedElts, KnownUndef,
                                   KnownZero, TLO, Depth + 1))
      return true;
 
    if (Op.getOpcode() == ISD::ZERO_EXTEND) {
      // zext(undef) upper bits are guaranteed to be zero.
      if (DemandedElts.isSubsetOf(KnownUndef))
        return TLO.CombineTo(Op, TLO.DAG.getConstant(0, SDLoc(Op), VT));
      KnownUndef.clearAllBits();
    }
    break;
  default: {
    if (Op.getOpcode() >= ISD::BUILTIN_OP_END) {
      if (SimplifyDemandedVectorEltsForTargetNode(Op, DemandedElts, KnownUndef,
                                                  KnownZero, TLO, Depth))
        return true;
    } else {
      KnownBits Known;
      APInt DemandedBits = APInt::getAllOnes(EltSizeInBits);
      if (SimplifyDemandedBits(Op, DemandedBits, OriginalDemandedElts, Known,
                               TLO, Depth, AssumeSingleUse))
        return true;
    }
    break;
  }
  }
  assert((KnownUndef & KnownZero) == 0 && "Elements flagged as undef AND zero");
 
  // Constant fold all undef cases.
  // TODO: Handle zero cases as well.
  if (DemandedElts.isSubsetOf(KnownUndef))
    return TLO.CombineTo(Op, TLO.DAG.getUNDEF(VT));
 
  return false;
}
 
/// Determine which of the bits specified in Mask are known to be either zero or
/// one and return them in the Known.
void TargetLowering::computeKnownBitsForTargetNode(const SDValue Op,
                                                   KnownBits &Known,
                                                   const APInt &DemandedElts,
                                                   const SelectionDAG &DAG,
                                                   unsigned Depth) const {
  assert((Op.getOpcode() >= ISD::BUILTIN_OP_END ||
          Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
          Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
          Op.getOpcode() == ISD::INTRINSIC_VOID) &&
         "Should use MaskedValueIsZero if you don't know whether Op"
         " is a target node!");
  Known.resetAll();
}
 
void TargetLowering::computeKnownBitsForTargetInstr(
    GISelKnownBits &Analysis, Register R, KnownBits &Known,
    const APInt &DemandedElts, const MachineRegisterInfo &MRI,
    unsigned Depth) const {
  Known.resetAll();
}
 
void TargetLowering::computeKnownBitsForFrameIndex(
  const int FrameIdx, KnownBits &Known, const MachineFunction &MF) const {
  // The low bits are known zero if the pointer is aligned.
  Known.Zero.setLowBits(Log2(MF.getFrameInfo().getObjectAlign(FrameIdx)));
}
 
Align TargetLowering::computeKnownAlignForTargetInstr(
  GISelKnownBits &Analysis, Register R, const MachineRegisterInfo &MRI,
  unsigned Depth) const {
  return Align(1);
}
 
/// This method can be implemented by targets that want to expose additional
/// information about sign bits to the DAG Combiner.
unsigned TargetLowering::ComputeNumSignBitsForTargetNode(SDValue Op,
                                                         const APInt &,
                                                         const SelectionDAG &,
                                                         unsigned Depth) const {
  assert((Op.getOpcode() >= ISD::BUILTIN_OP_END ||
          Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
          Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
          Op.getOpcode() == ISD::INTRINSIC_VOID) &&
         "Should use ComputeNumSignBits if you don't know whether Op"
         " is a target node!");
  return 1;
}
 
unsigned TargetLowering::computeNumSignBitsForTargetInstr(
  GISelKnownBits &Analysis, Register R, const APInt &DemandedElts,
  const MachineRegisterInfo &MRI, unsigned Depth) const {
  return 1;
}
 
bool TargetLowering::SimplifyDemandedVectorEltsForTargetNode(
    SDValue Op, const APInt &DemandedElts, APInt &KnownUndef, APInt &KnownZero,
    TargetLoweringOpt &TLO, unsigned Depth) const {
  assert((Op.getOpcode() >= ISD::BUILTIN_OP_END ||
          Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
          Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
          Op.getOpcode() == ISD::INTRINSIC_VOID) &&
         "Should use SimplifyDemandedVectorElts if you don't know whether Op"
         " is a target node!");
  return false;
}
 
bool TargetLowering::SimplifyDemandedBitsForTargetNode(
    SDValue Op, const APInt &DemandedBits, const APInt &DemandedElts,
    KnownBits &Known, TargetLoweringOpt &TLO, unsigned Depth) const {
  assert((Op.getOpcode() >= ISD::BUILTIN_OP_END ||
          Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
          Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
          Op.getOpcode() == ISD::INTRINSIC_VOID) &&
         "Should use SimplifyDemandedBits if you don't know whether Op"
         " is a target node!");
  computeKnownBitsForTargetNode(Op, Known, DemandedElts, TLO.DAG, Depth);
  return false;
}
 
SDValue TargetLowering::SimplifyMultipleUseDemandedBitsForTargetNode(
    SDValue Op, const APInt &DemandedBits, const APInt &DemandedElts,
    SelectionDAG &DAG, unsigned Depth) const {
  assert(
      (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
       Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
       Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
       Op.getOpcode() == ISD::INTRINSIC_VOID) &&
      "Should use SimplifyMultipleUseDemandedBits if you don't know whether Op"
      " is a target node!");
  return SDValue();
}
 
SDValue
TargetLowering::buildLegalVectorShuffle(EVT VT, const SDLoc &DL, SDValue N0,
                                        SDValue N1, MutableArrayRef<int> Mask,
                                        SelectionDAG &DAG) const {
  bool LegalMask = isShuffleMaskLegal(Mask, VT);
  if (!LegalMask) {
    std::swap(N0, N1);
    ShuffleVectorSDNode::commuteMask(Mask);
    LegalMask = isShuffleMaskLegal(Mask, VT);
  }
 
  if (!LegalMask)
    return SDValue();
 
  return DAG.getVectorShuffle(VT, DL, N0, N1, Mask);
}
 
const Constant *TargetLowering::getTargetConstantFromLoad(LoadSDNode*) const {
  return nullptr;
}
 
bool TargetLowering::isGuaranteedNotToBeUndefOrPoisonForTargetNode(
    SDValue Op, const APInt &DemandedElts, const SelectionDAG &DAG,
    bool PoisonOnly, unsigned Depth) const {
  assert(
      (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
       Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
       Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
       Op.getOpcode() == ISD::INTRINSIC_VOID) &&
      "Should use isGuaranteedNotToBeUndefOrPoison if you don't know whether Op"
      " is a target node!");
  return false;
}
 
bool TargetLowering::canCreateUndefOrPoisonForTargetNode(
    SDValue Op, const APInt &DemandedElts, const SelectionDAG &DAG,
    bool PoisonOnly, bool ConsiderFlags, unsigned Depth) const {
  assert((Op.getOpcode() >= ISD::BUILTIN_OP_END ||
          Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
          Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
          Op.getOpcode() == ISD::INTRINSIC_VOID) &&
         "Should use canCreateUndefOrPoison if you don't know whether Op"
         " is a target node!");
  // Be conservative and return true.
  return true;
}
 
bool TargetLowering::isKnownNeverNaNForTargetNode(SDValue Op,
                                                  const SelectionDAG &DAG,
                                                  bool SNaN,
                                                  unsigned Depth) const {
  assert((Op.getOpcode() >= ISD::BUILTIN_OP_END ||
          Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
          Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
          Op.getOpcode() == ISD::INTRINSIC_VOID) &&
         "Should use isKnownNeverNaN if you don't know whether Op"
         " is a target node!");
  return false;
}
 
bool TargetLowering::isSplatValueForTargetNode(SDValue Op,
                                               const APInt &DemandedElts,
                                               APInt &UndefElts,
                                               unsigned Depth) const {
  assert((Op.getOpcode() >= ISD::BUILTIN_OP_END ||
          Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
          Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
          Op.getOpcode() == ISD::INTRINSIC_VOID) &&
         "Should use isSplatValue if you don't know whether Op"
         " is a target node!");
  return false;
}
 
// FIXME: Ideally, this would use ISD::isConstantSplatVector(), but that must
// work with truncating build vectors and vectors with elements of less than
// 8 bits.
bool TargetLowering::isConstTrueVal(SDValue N) const {
  if (!N)
    return false;
 
  unsigned EltWidth;
  APInt CVal;
  if (ConstantSDNode *CN = isConstOrConstSplat(N, /*AllowUndefs=*/false,
                                               /*AllowTruncation=*/true)) {
    CVal = CN->getAPIntValue();
    EltWidth = N.getValueType().getScalarSizeInBits();
  } else
    return false;
 
  // If this is a truncating splat, truncate the splat value.
  // Otherwise, we may fail to match the expected values below.
  if (EltWidth < CVal.getBitWidth())
    CVal = CVal.trunc(EltWidth);
 
  switch (getBooleanContents(N.getValueType())) {
  case UndefinedBooleanContent:
    return CVal[0];
  case ZeroOrOneBooleanContent:
    return CVal.isOne();
  case ZeroOrNegativeOneBooleanContent:
    return CVal.isAllOnes();
  }
 
  llvm_unreachable("Invalid boolean contents");
}
 
bool TargetLowering::isConstFalseVal(SDValue N) const {
  if (!N)
    return false;
 
  const ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N);
  if (!CN) {
    const BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(N);
    if (!BV)
      return false;
 
    // Only interested in constant splats, we don't care about undef
    // elements in identifying boolean constants and getConstantSplatNode
    // returns NULL if all ops are undef;
    CN = BV->getConstantSplatNode();
    if (!CN)
      return false;
  }
 
  if (getBooleanContents(N->getValueType(0)) == UndefinedBooleanContent)
    return !CN->getAPIntValue()[0];
 
  return CN->isZero();
}
 
bool TargetLowering::isExtendedTrueVal(const ConstantSDNode *N, EVT VT,
                                       bool SExt) const {
  if (VT == MVT::i1)
    return N->isOne();
 
  TargetLowering::BooleanContent Cnt = getBooleanContents(VT);
  switch (Cnt) {
  case TargetLowering::ZeroOrOneBooleanContent:
    // An extended value of 1 is always true, unless its original type is i1,
    // in which case it will be sign extended to -1.
    return (N->isOne() && !SExt) || (SExt && (N->getValueType(0) != MVT::i1));
  case TargetLowering::UndefinedBooleanContent:
  case TargetLowering::ZeroOrNegativeOneBooleanContent:
    return N->isAllOnes() && SExt;
  }
  llvm_unreachable("Unexpected enumeration.");
}
 
/// This helper function of SimplifySetCC tries to optimize the comparison when
/// either operand of the SetCC node is a bitwise-and instruction.
SDValue TargetLowering::foldSetCCWithAnd(EVT VT, SDValue N0, SDValue N1,
                                         ISD::CondCode Cond, const SDLoc &DL,
                                         DAGCombinerInfo &DCI) const {
  if (N1.getOpcode() == ISD::AND && N0.getOpcode() != ISD::AND)
    std::swap(N0, N1);
 
  SelectionDAG &DAG = DCI.DAG;
  EVT OpVT = N0.getValueType();
  if (N0.getOpcode() != ISD::AND || !OpVT.isInteger() ||
      (Cond != ISD::SETEQ && Cond != ISD::SETNE))
    return SDValue();
 
  // (X & Y) != 0 --> zextOrTrunc(X & Y)
  // iff everything but LSB is known zero:
  if (Cond == ISD::SETNE && isNullConstant(N1) &&
      (getBooleanContents(OpVT) == TargetLowering::UndefinedBooleanContent ||
       getBooleanContents(OpVT) == TargetLowering::ZeroOrOneBooleanContent)) {
    unsigned NumEltBits = OpVT.getScalarSizeInBits();
    APInt UpperBits = APInt::getHighBitsSet(NumEltBits, NumEltBits - 1);
    if (DAG.MaskedValueIsZero(N0, UpperBits))
      return DAG.getBoolExtOrTrunc(N0, DL, VT, OpVT);
  }
 
  // Match these patterns in any of their permutations:
  // (X & Y) == Y
  // (X & Y) != Y
  SDValue X, Y;
  if (N0.getOperand(0) == N1) {
    X = N0.getOperand(1);
    Y = N0.getOperand(0);
  } else if (N0.getOperand(1) == N1) {
    X = N0.getOperand(0);
    Y = N0.getOperand(1);
  } else {
    return SDValue();
  }
 
  SDValue Zero = DAG.getConstant(0, DL, OpVT);
  if (DAG.isKnownToBeAPowerOfTwo(Y)) {
    // Simplify X & Y == Y to X & Y != 0 if Y has exactly one bit set.
    // Note that where Y is variable and is known to have at most one bit set
    // (for example, if it is Z & 1) we cannot do this; the expressions are not
    // equivalent when Y == 0.
    assert(OpVT.isInteger());
    Cond = ISD::getSetCCInverse(Cond, OpVT);
    if (DCI.isBeforeLegalizeOps() ||
        isCondCodeLegal(Cond, N0.getSimpleValueType()))
      return DAG.getSetCC(DL, VT, N0, Zero, Cond);
  } else if (N0.hasOneUse() && hasAndNotCompare(Y)) {
    // If the target supports an 'and-not' or 'and-complement' logic operation,
    // try to use that to make a comparison operation more efficient.
    // But don't do this transform if the mask is a single bit because there are
    // more efficient ways to deal with that case (for example, 'bt' on x86 or
    // 'rlwinm' on PPC).
 
    // Bail out if the compare operand that we want to turn into a zero is
    // already a zero (otherwise, infinite loop).
    auto *YConst = dyn_cast<ConstantSDNode>(Y);
    if (YConst && YConst->isZero())
      return SDValue();
 
    // Transform this into: ~X & Y == 0.
    SDValue NotX = DAG.getNOT(SDLoc(X), X, OpVT);
    SDValue NewAnd = DAG.getNode(ISD::AND, SDLoc(N0), OpVT, NotX, Y);
    return DAG.getSetCC(DL, VT, NewAnd, Zero, Cond);
  }
 
  return SDValue();
}
 
/// There are multiple IR patterns that could be checking whether certain
/// truncation of a signed number would be lossy or not. The pattern which is
/// best at IR level, may not lower optimally. Thus, we want to unfold it.
/// We are looking for the following pattern: (KeptBits is a constant)
///   (add %x, (1 << (KeptBits-1))) srccond (1 << KeptBits)
/// KeptBits won't be bitwidth(x), that will be constant-folded to true/false.
/// KeptBits also can't be 1, that would have been folded to  %x dstcond 0
/// We will unfold it into the natural trunc+sext pattern:
///   ((%x << C) a>> C) dstcond %x
/// Where  C = bitwidth(x) - KeptBits  and  C u< bitwidth(x)
SDValue TargetLowering::optimizeSetCCOfSignedTruncationCheck(
    EVT SCCVT, SDValue N0, SDValue N1, ISD::CondCode Cond, DAGCombinerInfo &DCI,
    const SDLoc &DL) const {
  // We must be comparing with a constant.
  ConstantSDNode *C1;
  if (!(C1 = dyn_cast<ConstantSDNode>(N1)))
    return SDValue();
 
  // N0 should be:  add %x, (1 << (KeptBits-1))
  if (N0->getOpcode() != ISD::ADD)
    return SDValue();
 
  // And we must be 'add'ing a constant.
  ConstantSDNode *C01;
  if (!(C01 = dyn_cast<ConstantSDNode>(N0->getOperand(1))))
    return SDValue();
 
  SDValue X = N0->getOperand(0);
  EVT XVT = X.getValueType();
 
  // Validate constants ...
 
  APInt I1 = C1->getAPIntValue();
 
  ISD::CondCode NewCond;
  if (Cond == ISD::CondCode::SETULT) {
    NewCond = ISD::CondCode::SETEQ;
  } else if (Cond == ISD::CondCode::SETULE) {
    NewCond = ISD::CondCode::SETEQ;
    // But need to 'canonicalize' the constant.
    I1 += 1;
  } else if (Cond == ISD::CondCode::SETUGT) {
    NewCond = ISD::CondCode::SETNE;
    // But need to 'canonicalize' the constant.
    I1 += 1;
  } else if (Cond == ISD::CondCode::SETUGE) {
    NewCond = ISD::CondCode::SETNE;
  } else
    return SDValue();
 
  APInt I01 = C01->getAPIntValue();
 
  auto checkConstants = [&I1, &I01]() -> bool {
    // Both of them must be power-of-two, and the constant from setcc is bigger.
    return I1.ugt(I01) && I1.isPowerOf2() && I01.isPowerOf2();
  };
 
  if (checkConstants()) {
    // Great, e.g. got  icmp ult i16 (add i16 %x, 128), 256
  } else {
    // What if we invert constants? (and the target predicate)
    I1.negate();
    I01.negate();
    assert(XVT.isInteger());
    NewCond = getSetCCInverse(NewCond, XVT);
    if (!checkConstants())
      return SDValue();
    // Great, e.g. got  icmp uge i16 (add i16 %x, -128), -256
  }
 
  // They are power-of-two, so which bit is set?
  const unsigned KeptBits = I1.logBase2();
  const unsigned KeptBitsMinusOne = I01.logBase2();
 
  // Magic!
  if (KeptBits != (KeptBitsMinusOne + 1))
    return SDValue();
  assert(KeptBits > 0 && KeptBits < XVT.getSizeInBits() && "unreachable");
 
  // We don't want to do this in every single case.
  SelectionDAG &DAG = DCI.DAG;
  if (!DAG.getTargetLoweringInfo().shouldTransformSignedTruncationCheck(
          XVT, KeptBits))
    return SDValue();
 
  const unsigned MaskedBits = XVT.getSizeInBits() - KeptBits;
  assert(MaskedBits > 0 && MaskedBits < XVT.getSizeInBits() && "unreachable");
 
  // Unfold into:  ((%x << C) a>> C) cond %x
  // Where 'cond' will be either 'eq' or 'ne'.
  SDValue ShiftAmt = DAG.getConstant(MaskedBits, DL, XVT);
  SDValue T0 = DAG.getNode(ISD::SHL, DL, XVT, X, ShiftAmt);
  SDValue T1 = DAG.getNode(ISD::SRA, DL, XVT, T0, ShiftAmt);
  SDValue T2 = DAG.getSetCC(DL, SCCVT, T1, X, NewCond);
 
  return T2;
}
 
// (X & (C l>>/<< Y)) ==/!= 0  -->  ((X <</l>> Y) & C) ==/!= 0
SDValue TargetLowering::optimizeSetCCByHoistingAndByConstFromLogicalShift(
    EVT SCCVT, SDValue N0, SDValue N1C, ISD::CondCode Cond,
    DAGCombinerInfo &DCI, const SDLoc &DL) const {
  assert(isConstOrConstSplat(N1C) &&
         isConstOrConstSplat(N1C)->getAPIntValue().isZero() &&
         "Should be a comparison with 0.");
  assert((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
         "Valid only for [in]equality comparisons.");
 
  unsigned NewShiftOpcode;
  SDValue X, C, Y;
 
  SelectionDAG &DAG = DCI.DAG;
  const TargetLowering &TLI = DAG.getTargetLoweringInfo();
 
  // Look for '(C l>>/<< Y)'.
  auto Match = [&NewShiftOpcode, &X, &C, &Y, &TLI, &DAG](SDValue V) {
    // The shift should be one-use.
    if (!V.hasOneUse())
      return false;
    unsigned OldShiftOpcode = V.getOpcode();
    switch (OldShiftOpcode) {
    case ISD::SHL:
      NewShiftOpcode = ISD::SRL;
      break;
    case ISD::SRL:
      NewShiftOpcode = ISD::SHL;
      break;
    default:
      return false; // must be a logical shift.
    }
    // We should be shifting a constant.
    // FIXME: best to use isConstantOrConstantVector().
    C = V.getOperand(0);
    ConstantSDNode *CC =
        isConstOrConstSplat(C, /*AllowUndefs=*/true, /*AllowTruncation=*/true);
    if (!CC)
      return false;
    Y = V.getOperand(1);
 
    ConstantSDNode *XC =
        isConstOrConstSplat(X, /*AllowUndefs=*/true, /*AllowTruncation=*/true);
    return TLI.shouldProduceAndByConstByHoistingConstFromShiftsLHSOfAnd(
        X, XC, CC, Y, OldShiftOpcode, NewShiftOpcode, DAG);
  };
 
  // LHS of comparison should be an one-use 'and'.
  if (N0.getOpcode() != ISD::AND || !N0.hasOneUse())
    return SDValue();
 
  X = N0.getOperand(0);
  SDValue Mask = N0.getOperand(1);
 
  // 'and' is commutative!
  if (!Match(Mask)) {
    std::swap(X, Mask);
    if (!Match(Mask))
      return SDValue();
  }
 
  EVT VT = X.getValueType();
 
  // Produce:
  // ((X 'OppositeShiftOpcode' Y) & C) Cond 0
  SDValue T0 = DAG.getNode(NewShiftOpcode, DL, VT, X, Y);
  SDValue T1 = DAG.getNode(ISD::AND, DL, VT, T0, C);
  SDValue T2 = DAG.getSetCC(DL, SCCVT, T1, N1C, Cond);
  return T2;
}
 
/// Try to fold an equality comparison with a {add/sub/xor} binary operation as
/// the 1st operand (N0). Callers are expected to swap the N0/N1 parameters to
/// handle the commuted versions of these patterns.
SDValue TargetLowering::foldSetCCWithBinOp(EVT VT, SDValue N0, SDValue N1,
                                           ISD::CondCode Cond, const SDLoc &DL,
                                           DAGCombinerInfo &DCI) const {
  unsigned BOpcode = N0.getOpcode();
  assert((BOpcode == ISD::ADD || BOpcode == ISD::SUB || BOpcode == ISD::XOR) &&
         "Unexpected binop");
  assert((Cond == ISD::SETEQ || Cond == ISD::SETNE) && "Unexpected condcode");
 
  // (X + Y) == X --> Y == 0
  // (X - Y) == X --> Y == 0
  // (X ^ Y) == X --> Y == 0
  SelectionDAG &DAG = DCI.DAG;
  EVT OpVT = N0.getValueType();
  SDValue X = N0.getOperand(0);
  SDValue Y = N0.getOperand(1);
  if (X == N1)
    return DAG.getSetCC(DL, VT, Y, DAG.getConstant(0, DL, OpVT), Cond);
 
  if (Y != N1)
    return SDValue();
 
  // (X + Y) == Y --> X == 0
  // (X ^ Y) == Y --> X == 0
  if (BOpcode == ISD::ADD || BOpcode == ISD::XOR)
    return DAG.getSetCC(DL, VT, X, DAG.getConstant(0, DL, OpVT), Cond);
 
  // The shift would not be valid if the operands are boolean (i1).
  if (!N0.hasOneUse() || OpVT.getScalarSizeInBits() == 1)
    return SDValue();
 
  // (X - Y) == Y --> X == Y << 1
  EVT ShiftVT = getShiftAmountTy(OpVT, DAG.getDataLayout(),
                                 !DCI.isBeforeLegalize());
  SDValue One = DAG.getConstant(1, DL, ShiftVT);
  SDValue YShl1 = DAG.getNode(ISD::SHL, DL, N1.getValueType(), Y, One);
  if (!DCI.isCalledByLegalizer())
    DCI.AddToWorklist(YShl1.getNode());
  return DAG.getSetCC(DL, VT, X, YShl1, Cond);
}
 
static SDValue simplifySetCCWithCTPOP(const TargetLowering &TLI, EVT VT,
                                      SDValue N0, const APInt &C1,
                                      ISD::CondCode Cond, const SDLoc &dl,
                                      SelectionDAG &DAG) {
  // Look through truncs that don't change the value of a ctpop.
  // FIXME: Add vector support? Need to be careful with setcc result type below.
  SDValue CTPOP = N0;
  if (N0.getOpcode() == ISD::TRUNCATE && N0.hasOneUse() && !VT.isVector() &&
      N0.getScalarValueSizeInBits() > Log2_32(N0.getOperand(0).getScalarValueSizeInBits()))
    CTPOP = N0.getOperand(0);
 
  if (CTPOP.getOpcode() != ISD::CTPOP || !CTPOP.hasOneUse())
    return SDValue();
 
  EVT CTVT = CTPOP.getValueType();
  SDValue CTOp = CTPOP.getOperand(0);
 
  // Expand a power-of-2-or-zero comparison based on ctpop:
  // (ctpop x) u< 2 -> (x & x-1) == 0
  // (ctpop x) u> 1 -> (x & x-1) != 0
  if (Cond == ISD::SETULT || Cond == ISD::SETUGT) {
    // Keep the CTPOP if it is a legal vector op.
    if (CTVT.isVector() && TLI.isOperationLegal(ISD::CTPOP, CTVT))
      return SDValue();
 
    unsigned CostLimit = TLI.getCustomCtpopCost(CTVT, Cond);
    if (C1.ugt(CostLimit + (Cond == ISD::SETULT)))
      return SDValue();
    if (C1 == 0 && (Cond == ISD::SETULT))
      return SDValue(); // This is handled elsewhere.
 
    unsigned Passes = C1.getLimitedValue() - (Cond == ISD::SETULT);
 
    SDValue NegOne = DAG.getAllOnesConstant(dl, CTVT);
    SDValue Result = CTOp;
    for (unsigned i = 0; i < Passes; i++) {
      SDValue Add = DAG.getNode(ISD::ADD, dl, CTVT, Result, NegOne);
      Result = DAG.getNode(ISD::AND, dl, CTVT, Result, Add);
    }
    ISD::CondCode CC = Cond == ISD::SETULT ? ISD::SETEQ : ISD::SETNE;
    return DAG.getSetCC(dl, VT, Result, DAG.getConstant(0, dl, CTVT), CC);
  }
 
  // Expand a power-of-2 comparison based on ctpop:
  // (ctpop x) == 1 --> (x != 0) && ((x & x-1) == 0)
  // (ctpop x) != 1 --> (x == 0) || ((x & x-1) != 0)
  if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) && C1 == 1) {
    // Keep the CTPOP if it is legal.
    if (TLI.isOperationLegal(ISD::CTPOP, CTVT))
      return SDValue();
 
    SDValue Zero = DAG.getConstant(0, dl, CTVT);
    SDValue NegOne = DAG.getAllOnesConstant(dl, CTVT);
    assert(CTVT.isInteger());
    ISD::CondCode InvCond = ISD::getSetCCInverse(Cond, CTVT);
    SDValue Add = DAG.getNode(ISD::ADD, dl, CTVT, CTOp, NegOne);
    SDValue And = DAG.getNode(ISD::AND, dl, CTVT, CTOp, Add);
    SDValue LHS = DAG.getSetCC(dl, VT, CTOp, Zero, InvCond);
    SDValue RHS = DAG.getSetCC(dl, VT, And, Zero, Cond);
    unsigned LogicOpcode = Cond == ISD::SETEQ ? ISD::AND : ISD::OR;
    return DAG.getNode(LogicOpcode, dl, VT, LHS, RHS);
  }
 
  return SDValue();
}
 
static SDValue foldSetCCWithRotate(EVT VT, SDValue N0, SDValue N1,
                                   ISD::CondCode Cond, const SDLoc &dl,
                                   SelectionDAG &DAG) {
  if (Cond != ISD::SETEQ && Cond != ISD::SETNE)
    return SDValue();
 
  auto *C1 = isConstOrConstSplat(N1, /* AllowUndefs */ true);
  if (!C1 || !(C1->isZero() || C1->isAllOnes()))
    return SDValue();
 
  auto getRotateSource = [](SDValue X) {
    if (X.getOpcode() == ISD::ROTL || X.getOpcode() == ISD::ROTR)
      return X.getOperand(0);
    return SDValue();
  };
 
  // Peek through a rotated value compared against 0 or -1:
  // (rot X, Y) == 0/-1 --> X == 0/-1
  // (rot X, Y) != 0/-1 --> X != 0/-1
  if (SDValue R = getRotateSource(N0))
    return DAG.getSetCC(dl, VT, R, N1, Cond);
 
  // Peek through an 'or' of a rotated value compared against 0:
  // or (rot X, Y), Z ==/!= 0 --> (or X, Z) ==/!= 0
  // or Z, (rot X, Y) ==/!= 0 --> (or X, Z) ==/!= 0
  //
  // TODO: Add the 'and' with -1 sibling.
  // TODO: Recurse through a series of 'or' ops to find the rotate.
  EVT OpVT = N0.getValueType();
  if (N0.hasOneUse() && N0.getOpcode() == ISD::OR && C1->isZero()) {
    if (SDValue R = getRotateSource(N0.getOperand(0))) {
      SDValue NewOr = DAG.getNode(ISD::OR, dl, OpVT, R, N0.getOperand(1));
      return DAG.getSetCC(dl, VT, NewOr, N1, Cond);
    }
    if (SDValue R = getRotateSource(N0.getOperand(1))) {
      SDValue NewOr = DAG.getNode(ISD::OR, dl, OpVT, R, N0.getOperand(0));
      return DAG.getSetCC(dl, VT, NewOr, N1, Cond);
    }
  }
 
  return SDValue();
}
 
static SDValue foldSetCCWithFunnelShift(EVT VT, SDValue N0, SDValue N1,
                                        ISD::CondCode Cond, const SDLoc &dl,
                                        SelectionDAG &DAG) {
  // If we are testing for all-bits-clear, we might be able to do that with
  // less shifting since bit-order does not matter.
  if (Cond != ISD::SETEQ && Cond != ISD::SETNE)
    return SDValue();
 
  auto *C1 = isConstOrConstSplat(N1, /* AllowUndefs */ true);
  if (!C1 || !C1->isZero())
    return SDValue();
 
  if (!N0.hasOneUse() ||
      (N0.getOpcode() != ISD::FSHL && N0.getOpcode() != ISD::FSHR))
    return SDValue();
 
  unsigned BitWidth = N0.getScalarValueSizeInBits();
  auto *ShAmtC = isConstOrConstSplat(N0.getOperand(2));
  if (!ShAmtC || ShAmtC->getAPIntValue().uge(BitWidth))
    return SDValue();
 
  // Canonicalize fshr as fshl to reduce pattern-matching.
  unsigned ShAmt = ShAmtC->getZExtValue();
  if (N0.getOpcode() == ISD::FSHR)
    ShAmt = BitWidth - ShAmt;
 
  // Match an 'or' with a specific operand 'Other' in either commuted variant.
  SDValue X, Y;
  auto matchOr = [&X, &Y](SDValue Or, SDValue Other) {
    if (Or.getOpcode() != ISD::OR || !Or.hasOneUse())
      return false;
    if (Or.getOperand(0) == Other) {
      X = Or.getOperand(0);
      Y = Or.getOperand(1);
      return true;
    }
    if (Or.getOperand(1) == Other) {
      X = Or.getOperand(1);
      Y = Or.getOperand(0);
      return true;
    }
    return false;
  };
 
  EVT OpVT = N0.getValueType();
  EVT ShAmtVT = N0.getOperand(2).getValueType();
  SDValue F0 = N0.getOperand(0);
  SDValue F1 = N0.getOperand(1);
  if (matchOr(F0, F1)) {
    // fshl (or X, Y), X, C ==/!= 0 --> or (shl Y, C), X ==/!= 0
    SDValue NewShAmt = DAG.getConstant(ShAmt, dl, ShAmtVT);
    SDValue Shift = DAG.getNode(ISD::SHL, dl, OpVT, Y, NewShAmt);
    SDValue NewOr = DAG.getNode(ISD::OR, dl, OpVT, Shift, X);
    return DAG.getSetCC(dl, VT, NewOr, N1, Cond);
  }
  if (matchOr(F1, F0)) {
    // fshl X, (or X, Y), C ==/!= 0 --> or (srl Y, BW-C), X ==/!= 0
    SDValue NewShAmt = DAG.getConstant(BitWidth - ShAmt, dl, ShAmtVT);
    SDValue Shift = DAG.getNode(ISD::SRL, dl, OpVT, Y, NewShAmt);
    SDValue NewOr = DAG.getNode(ISD::OR, dl, OpVT, Shift, X);
    return DAG.getSetCC(dl, VT, NewOr, N1, Cond);
  }
 
  return SDValue();
}
 
/// Try to simplify a setcc built with the specified operands and cc. If it is
/// unable to simplify it, return a null SDValue.
SDValue TargetLowering::SimplifySetCC(EVT VT, SDValue N0, SDValue N1,
                                      ISD::CondCode Cond, bool foldBooleans,
                                      DAGCombinerInfo &DCI,
                                      const SDLoc &dl) const {
  SelectionDAG &DAG = DCI.DAG;
  const DataLayout &Layout = DAG.getDataLayout();
  EVT OpVT = N0.getValueType();
 
  // Constant fold or commute setcc.
  if (SDValue Fold = DAG.FoldSetCC(VT, N0, N1, Cond, dl))
    return Fold;
 
  bool N0ConstOrSplat =
      isConstOrConstSplat(N0, /*AllowUndefs*/ false, /*AllowTruncate*/ true);
  bool N1ConstOrSplat =
      isConstOrConstSplat(N1, /*AllowUndefs*/ false, /*AllowTruncate*/ true);
 
  // Ensure that the constant occurs on the RHS and fold constant comparisons.
  // TODO: Handle non-splat vector constants. All undef causes trouble.
  // FIXME: We can't yet fold constant scalable vector splats, so avoid an
  // infinite loop here when we encounter one.
  ISD::CondCode SwappedCC = ISD::getSetCCSwappedOperands(Cond);
  if (N0ConstOrSplat && (!OpVT.isScalableVector() || !N1ConstOrSplat) &&
      (DCI.isBeforeLegalizeOps() ||
       isCondCodeLegal(SwappedCC, N0.getSimpleValueType())))
    return DAG.getSetCC(dl, VT, N1, N0, SwappedCC);
 
  // If we have a subtract with the same 2 non-constant operands as this setcc
  // -- but in reverse order -- then try to commute the operands of this setcc
  // to match. A matching pair of setcc (cmp) and sub may be combined into 1
  // instruction on some targets.
  if (!N0ConstOrSplat && !N1ConstOrSplat &&
      (DCI.isBeforeLegalizeOps() ||
       isCondCodeLegal(SwappedCC, N0.getSimpleValueType())) &&
      DAG.doesNodeExist(ISD::SUB, DAG.getVTList(OpVT), {N1, N0}) &&
      !DAG.doesNodeExist(ISD::SUB, DAG.getVTList(OpVT), {N0, N1}))
    return DAG.getSetCC(dl, VT, N1, N0, SwappedCC);
 
  if (SDValue V = foldSetCCWithRotate(VT, N0, N1, Cond, dl, DAG))
    return V;
 
  if (SDValue V = foldSetCCWithFunnelShift(VT, N0, N1, Cond, dl, DAG))
    return V;
 
  if (auto *N1C = isConstOrConstSplat(N1)) {
    const APInt &C1 = N1C->getAPIntValue();
 
    // Optimize some CTPOP cases.
    if (SDValue V = simplifySetCCWithCTPOP(*this, VT, N0, C1, Cond, dl, DAG))
      return V;
 
    // If the LHS is '(srl (ctlz x), 5)', the RHS is 0/1, and this is an
    // equality comparison, then we're just comparing whether X itself is
    // zero.
    if (N0.getOpcode() == ISD::SRL && (C1.isZero() || C1.isOne()) &&
        N0.getOperand(0).getOpcode() == ISD::CTLZ &&
        isPowerOf2_32(N0.getScalarValueSizeInBits())) {
      if (ConstantSDNode *ShAmt = isConstOrConstSplat(N0.getOperand(1))) {
        if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
            ShAmt->getAPIntValue() == Log2_32(N0.getScalarValueSizeInBits())) {
          if ((C1 == 0) == (Cond == ISD::SETEQ)) {
            // (srl (ctlz x), 5) == 0  -> X != 0
            // (srl (ctlz x), 5) != 1  -> X != 0
            Cond = ISD::SETNE;
          } else {
            // (srl (ctlz x), 5) != 0  -> X == 0
            // (srl (ctlz x), 5) == 1  -> X == 0
            Cond = ISD::SETEQ;
          }
          SDValue Zero = DAG.getConstant(0, dl, N0.getValueType());
          return DAG.getSetCC(dl, VT, N0.getOperand(0).getOperand(0), Zero,
                              Cond);
        }
      }
    }
  }
 
  // FIXME: Support vectors.
  if (auto *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
    const APInt &C1 = N1C->getAPIntValue();
 
    // (zext x) == C --> x == (trunc C)
    // (sext x) == C --> x == (trunc C)
    if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
        DCI.isBeforeLegalize() && N0->hasOneUse()) {
      unsigned MinBits = N0.getValueSizeInBits();
      SDValue PreExt;
      bool Signed = false;
      if (N0->getOpcode() == ISD::ZERO_EXTEND) {
        // ZExt
        MinBits = N0->getOperand(0).getValueSizeInBits();
        PreExt = N0->getOperand(0);
      } else if (N0->getOpcode() == ISD::AND) {
        // DAGCombine turns costly ZExts into ANDs
        if (auto *C = dyn_cast<ConstantSDNode>(N0->getOperand(1)))
          if ((C->getAPIntValue()+1).isPowerOf2()) {
            MinBits = C->getAPIntValue().countTrailingOnes();
            PreExt = N0->getOperand(0);
          }
      } else if (N0->getOpcode() == ISD::SIGN_EXTEND) {
        // SExt
        MinBits = N0->getOperand(0).getValueSizeInBits();
        PreExt = N0->getOperand(0);
        Signed = true;
      } else if (auto *LN0 = dyn_cast<LoadSDNode>(N0)) {
        // ZEXTLOAD / SEXTLOAD
        if (LN0->getExtensionType() == ISD::ZEXTLOAD) {
          MinBits = LN0->getMemoryVT().getSizeInBits();
          PreExt = N0;
        } else if (LN0->getExtensionType() == ISD::SEXTLOAD) {
          Signed = true;
          MinBits = LN0->getMemoryVT().getSizeInBits();
          PreExt = N0;
        }
      }
 
      // Figure out how many bits we need to preserve this constant.
      unsigned ReqdBits = Signed ? C1.getMinSignedBits() : C1.getActiveBits();
 
      // Make sure we're not losing bits from the constant.
      if (MinBits > 0 &&
          MinBits < C1.getBitWidth() &&
          MinBits >= ReqdBits) {
        EVT MinVT = EVT::getIntegerVT(*DAG.getContext(), MinBits);
        if (isTypeDesirableForOp(ISD::SETCC, MinVT)) {
          // Will get folded away.
          SDValue Trunc = DAG.getNode(ISD::TRUNCATE, dl, MinVT, PreExt);
          if (MinBits == 1 && C1 == 1)
            // Invert the condition.
            return DAG.getSetCC(dl, VT, Trunc, DAG.getConstant(0, dl, MVT::i1),
                                Cond == ISD::SETEQ ? ISD::SETNE : ISD::SETEQ);
          SDValue C = DAG.getConstant(C1.trunc(MinBits), dl, MinVT);
          return DAG.getSetCC(dl, VT, Trunc, C, Cond);
        }
 
        // If truncating the setcc operands is not desirable, we can still
        // simplify the expression in some cases:
        // setcc ([sz]ext (setcc x, y, cc)), 0, setne) -> setcc (x, y, cc)
        // setcc ([sz]ext (setcc x, y, cc)), 0, seteq) -> setcc (x, y, inv(cc))
        // setcc (zext (setcc x, y, cc)), 1, setne) -> setcc (x, y, inv(cc))
        // setcc (zext (setcc x, y, cc)), 1, seteq) -> setcc (x, y, cc)
        // setcc (sext (setcc x, y, cc)), -1, setne) -> setcc (x, y, inv(cc))
        // setcc (sext (setcc x, y, cc)), -1, seteq) -> setcc (x, y, cc)
        SDValue TopSetCC = N0->getOperand(0);
        unsigned N0Opc = N0->getOpcode();
        bool SExt = (N0Opc == ISD::SIGN_EXTEND);
        if (TopSetCC.getValueType() == MVT::i1 && VT == MVT::i1 &&
            TopSetCC.getOpcode() == ISD::SETCC &&
            (N0Opc == ISD::ZERO_EXTEND || N0Opc == ISD::SIGN_EXTEND) &&
            (isConstFalseVal(N1) ||
             isExtendedTrueVal(N1C, N0->getValueType(0), SExt))) {
 
          bool Inverse = (N1C->isZero() && Cond == ISD::SETEQ) ||
                         (!N1C->isZero() && Cond == ISD::SETNE);
 
          if (!Inverse)
            return TopSetCC;
 
          ISD::CondCode InvCond = ISD::getSetCCInverse(
              cast<CondCodeSDNode>(TopSetCC.getOperand(2))->get(),
              TopSetCC.getOperand(0).getValueType());
          return DAG.getSetCC(dl, VT, TopSetCC.getOperand(0),
                                      TopSetCC.getOperand(1),
                                      InvCond);
        }
      }
    }
 
    // If the LHS is '(and load, const)', the RHS is 0, the test is for
    // equality or unsigned, and all 1 bits of the const are in the same
    // partial word, see if we can shorten the load.
    if (DCI.isBeforeLegalize() &&
        !ISD::isSignedIntSetCC(Cond) &&
        N0.getOpcode() == ISD::AND && C1 == 0 &&
        N0.getNode()->hasOneUse() &&
        isa<LoadSDNode>(N0.getOperand(0)) &&
        N0.getOperand(0).getNode()->hasOneUse() &&
        isa<ConstantSDNode>(N0.getOperand(1))) {
      LoadSDNode *Lod = cast<LoadSDNode>(N0.getOperand(0));
      APInt bestMask;
      unsigned bestWidth = 0, bestOffset = 0;
      if (Lod->isSimple() && Lod->isUnindexed()) {
        unsigned origWidth = N0.getValueSizeInBits();
        unsigned maskWidth = origWidth;
        // We can narrow (e.g.) 16-bit extending loads on 32-bit target to
        // 8 bits, but have to be careful...
        if (Lod->getExtensionType() != ISD::NON_EXTLOAD)
          origWidth = Lod->getMemoryVT().getSizeInBits();
        const APInt &Mask = N0.getConstantOperandAPInt(1);
        for (unsigned width = origWidth / 2; width>=8; width /= 2) {
          APInt newMask = APInt::getLowBitsSet(maskWidth, width);
          for (unsigned offset=0; offset<origWidth/width; offset++) {
            if (Mask.isSubsetOf(newMask)) {
              if (Layout.isLittleEndian())
                bestOffset = (uint64_t)offset * (width/8);
              else
                bestOffset = (origWidth/width - offset - 1) * (width/8);
              bestMask = Mask.lshr(offset * (width/8) * 8);
              bestWidth = width;
              break;
            }
            newMask <<= width;
          }
        }
      }
      if (bestWidth) {
        EVT newVT = EVT::getIntegerVT(*DAG.getContext(), bestWidth);
        if (newVT.isRound() &&
            shouldReduceLoadWidth(Lod, ISD::NON_EXTLOAD, newVT)) {
          SDValue Ptr = Lod->getBasePtr();
          if (bestOffset != 0)
            Ptr =
                DAG.getMemBasePlusOffset(Ptr, TypeSize::Fixed(bestOffset), dl);
          SDValue NewLoad =
              DAG.getLoad(newVT, dl, Lod->getChain(), Ptr,
                          Lod->getPointerInfo().getWithOffset(bestOffset),
                          Lod->getOriginalAlign());
          return DAG.getSetCC(dl, VT,
                              DAG.getNode(ISD::AND, dl, newVT, NewLoad,
                                      DAG.getConstant(bestMask.trunc(bestWidth),
                                                      dl, newVT)),
                              DAG.getConstant(0LL, dl, newVT), Cond);
        }
      }
    }
 
    // If the LHS is a ZERO_EXTEND, perform the comparison on the input.
    if (N0.getOpcode() == ISD::ZERO_EXTEND) {
      unsigned InSize = N0.getOperand(0).getValueSizeInBits();
 
      // If the comparison constant has bits in the upper part, the
      // zero-extended value could never match.
      if (C1.intersects(APInt::getHighBitsSet(C1.getBitWidth(),
                                              C1.getBitWidth() - InSize))) {
        switch (Cond) {
        case ISD::SETUGT:
        case ISD::SETUGE:
        case ISD::SETEQ:
          return DAG.getConstant(0, dl, VT);
        case ISD::SETULT:
        case ISD::SETULE:
        case ISD::SETNE:
          return DAG.getConstant(1, dl, VT);
        case ISD::SETGT:
        case ISD::SETGE:
          // True if the sign bit of C1 is set.
          return DAG.getConstant(C1.isNegative(), dl, VT);
        case ISD::SETLT:
        case ISD::SETLE:
          // True if the sign bit of C1 isn't set.
          return DAG.getConstant(C1.isNonNegative(), dl, VT);
        default:
          break;
        }
      }
 
      // Otherwise, we can perform the comparison with the low bits.
      switch (Cond) {
      case ISD::SETEQ:
      case ISD::SETNE:
      case ISD::SETUGT:
      case ISD::SETUGE:
      case ISD::SETULT:
      case ISD::SETULE: {
        EVT newVT = N0.getOperand(0).getValueType();
        if (DCI.isBeforeLegalizeOps() ||
            (isOperationLegal(ISD::SETCC, newVT) &&
             isCondCodeLegal(Cond, newVT.getSimpleVT()))) {
          EVT NewSetCCVT = getSetCCResultType(Layout, *DAG.getContext(), newVT);
          SDValue NewConst = DAG.getConstant(C1.trunc(InSize), dl, newVT);
 
          SDValue NewSetCC = DAG.getSetCC(dl, NewSetCCVT, N0.getOperand(0),
                                          NewConst, Cond);
          return DAG.getBoolExtOrTrunc(NewSetCC, dl, VT, N0.getValueType());
        }
        break;
      }
      default:
        break; // todo, be more careful with signed comparisons
      }
    } else if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG &&
               (Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
               !isSExtCheaperThanZExt(cast<VTSDNode>(N0.getOperand(1))->getVT(),
                                      OpVT)) {
      EVT ExtSrcTy = cast<VTSDNode>(N0.getOperand(1))->getVT();
      unsigned ExtSrcTyBits = ExtSrcTy.getSizeInBits();
      EVT ExtDstTy = N0.getValueType();
      unsigned ExtDstTyBits = ExtDstTy.getSizeInBits();
 
      // If the constant doesn't fit into the number of bits for the source of
      // the sign extension, it is impossible for both sides to be equal.
      if (C1.getMinSignedBits() > ExtSrcTyBits)
        return DAG.getBoolConstant(Cond == ISD::SETNE, dl, VT, OpVT);
 
      assert(ExtDstTy == N0.getOperand(0).getValueType() &&
             ExtDstTy != ExtSrcTy && "Unexpected types!");
      APInt Imm = APInt::getLowBitsSet(ExtDstTyBits, ExtSrcTyBits);
      SDValue ZextOp = DAG.getNode(ISD::AND, dl, ExtDstTy, N0.getOperand(0),
                                   DAG.getConstant(Imm, dl, ExtDstTy));
      if (!DCI.isCalledByLegalizer())
        DCI.AddToWorklist(ZextOp.getNode());
      // Otherwise, make this a use of a zext.
      return DAG.getSetCC(dl, VT, ZextOp,
                          DAG.getConstant(C1 & Imm, dl, ExtDstTy), Cond);
    } else if ((N1C->isZero() || N1C->isOne()) &&
               (