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/Analysis/VectorUtils.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/MachineModuleInfoImpls.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, Attribute::Range})
    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::LAST_INTEGER_VALUETYPE;
    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::LAST_INTEGER_VALUETYPE;
    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.
      unsigned 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);
}
 
SDValue TargetLowering::expandIndirectJTBranch(const SDLoc &dl, SDValue Value,
                                               SDValue Addr, int JTI,
                                               SelectionDAG &DAG) const {
  SDValue Chain = Value;
  // Jump table debug info is only needed if CodeView is enabled.
  if (DAG.getTarget().getTargetTriple().isOSBinFormatCOFF()) {
    Chain = DAG.getJumpTableDebugInfo(JTI, Chain, dl);
  }
  return DAG.getNode(ISD::BRIND, dl, MVT::Other, Chain, Addr);
}
 
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))
    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();
 
  // Early-out if we've ended up calling an undemanded node, leave this to
  // constant folding.
  if (DemandedBits.isZero() || DemandedElts.isZero())
    return false;
 
  // 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,
                                      Op->getFlags());
      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 isTruncateFree/isZExtFree and ANY_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 &DemandedBits,
                                      TargetLoweringOpt &TLO) const {
  assert(Op.getNumOperands() == 2 &&
         "ShrinkDemandedOp only supports binary operators!");
  assert(Op.getNode()->getNumValues() == 1 &&
         "ShrinkDemandedOp only supports nodes with one result!");
 
  EVT VT = Op.getValueType();
  SelectionDAG &DAG = TLO.DAG;
  SDLoc dl(Op);
 
  // Early return, as this function cannot handle vector types.
  if (VT.isVector())
    return false;
 
  assert(Op.getOperand(0).getValueType().getScalarSizeInBits() == BitWidth &&
         Op.getOperand(1).getValueType().getScalarSizeInBits() == BitWidth &&
         "ShrinkDemandedOp only supports operands that have the same size!");
 
  // 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 = DemandedBits.getActiveBits();
  for (unsigned SmallVTBits = llvm::bit_ceil(DemandedSize);
       SmallVTBits < BitWidth; SmallVTBits = NextPowerOf2(SmallVTBits)) {
    EVT SmallVT = EVT::getIntegerVT(*DAG.getContext(), SmallVTBits);
    if (TLI.isTruncateFree(VT, SmallVT) && TLI.isZExtFree(SmallVT, VT)) {
      // 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, VT, 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();
 
  // Since the number of lanes in a scalable vector is unknown at compile time,
  // we track one bit which is implicitly broadcast to all lanes.  This means
  // that all lanes in a scalable vector are considered demanded.
  APInt DemandedElts = VT.isFixedLengthVector()
                           ? 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();
 
  // 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: {
    if (VT.isScalableVector())
      return SDValue();
 
    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::FREEZE: {
    SDValue N0 = Op.getOperand(0);
    if (DAG.isGuaranteedNotToBeUndefOrPoison(N0, DemandedElts,
                                             /*PoisonOnly=*/false))
      return N0;
    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 (std::optional<uint64_t> MaxSA =
            DAG.getValidMaximumShiftAmount(Op, DemandedElts, Depth + 1)) {
      SDValue Op0 = Op.getOperand(0);
      unsigned ShAmt = *MaxSA;
      unsigned NumSignBits =
          DAG.ComputeNumSignBits(Op0, DemandedElts, Depth + 1);
      unsigned UpperDemandedBits = BitWidth - DemandedBits.countr_zero();
      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 &&
        shouldRemoveRedundantExtend(Op))
      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 (VT.isScalableVector())
      return SDValue();
 
    // 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 (VT.isScalableVector())
      return SDValue();
 
    // 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: {
    if (VT.isScalableVector())
      return SDValue();
 
    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;
    break;
  }
  case ISD::VECTOR_SHUFFLE: {
    assert(!VT.isScalableVector());
    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:
    // TODO: Probably okay to remove after audit; here to reduce change size
    // in initial enablement patch for scalable vectors
    if (VT.isScalableVector())
      return SDValue();
 
    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();
  // Since the number of lanes in a scalable vector is unknown at compile time,
  // we track one bit which is implicitly broadcast to all lanes.  This means
  // that all lanes in a scalable vector are considered demanded.
  APInt DemandedElts = VT.isFixedLengthVector()
                           ? 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,
                                 TargetLowering::TargetLoweringOpt &TLO,
                                 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);
  SDValue Add2;
  auto MatchOperands = [&](SDValue Op1, SDValue Op2, SDValue Op3, SDValue A) {
    ConstantSDNode *ConstOp;
    if ((ConstOp = isConstOrConstSplat(Op2, DemandedElts)) &&
        ConstOp->isOne()) {
      ExtOpA = Op1;
      ExtOpB = Op3;
      Add2 = A;
      return true;
    }
    if ((ConstOp = isConstOrConstSplat(Op3, DemandedElts)) &&
        ConstOp->isOne()) {
      ExtOpA = Op1;
      ExtOpB = Op2;
      Add2 = A;
      return true;
    }
    return false;
  };
  bool IsCeil =
      (ExtOpA.getOpcode() == ISD::ADD &&
       MatchOperands(ExtOpA.getOperand(0), ExtOpA.getOperand(1), ExtOpB, ExtOpA)) ||
      (ExtOpB.getOpcode() == ISD::ADD &&
       MatchOperands(ExtOpB.getOperand(0), ExtOpB.getOperand(1), ExtOpA, ExtOpB));
 
  // 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.
  SelectionDAG &DAG = TLO.DAG;
  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(), llvm::bit_ceil(MinWidth));
  if (NVT.getScalarSizeInBits() > VT.getScalarSizeInBits())
    return SDValue();
  if (VT.isVector())
    NVT = EVT::getVectorVT(*DAG.getContext(), NVT, VT.getVectorElementCount());
  if (TLO.LegalTypes() && !TLI.isOperationLegal(AVGOpc, NVT)) {
    // If we could not transform, and (both) adds are nuw/nsw, we can use the
    // larger type size to do the transform.
    if (TLO.LegalOperations() && !TLI.isOperationLegal(AVGOpc, VT))
      return SDValue();
    if (DAG.willNotOverflowAdd(IsSigned, Add.getOperand(0),
                               Add.getOperand(1)) &&
        (!Add2 || DAG.willNotOverflowAdd(IsSigned, Add2.getOperand(0),
                                         Add2.getOperand(1))))
      NVT = VT;
    else
      return SDValue();
  }
 
  // Don't create a AVGFLOOR node with a scalar constant unless its legal as
  // this is likely to stop other folds (reassociation, value tracking etc.)
  if (!IsCeil && !TLI.isOperationLegal(AVGOpc, NVT) &&
      (isa<ConstantSDNode>(ExtOpA) || isa<ConstantSDNode>(ExtOpB)))
    return SDValue();
 
  SDLoc DL(Op);
  SDValue ResultAVG =
      DAG.getNode(AVGOpc, DL, NVT, DAG.getExtOrTrunc(IsSigned, ExtOpA, DL, NVT),
                  DAG.getExtOrTrunc(IsSigned, ExtOpB, DL, NVT));
  return DAG.getExtOrTrunc(IsSigned, ResultAVG, DL, VT);
}
 
/// 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);
 
  EVT VT = Op.getValueType();
  bool IsLE = TLO.DAG.getDataLayout().isLittleEndian();
  unsigned NumElts = OriginalDemandedElts.getBitWidth();
  assert((!VT.isFixedLengthVector() || NumElts == VT.getVectorNumElements()) &&
         "Unexpected vector size");
 
  APInt DemandedBits = OriginalDemandedBits;
  APInt DemandedElts = OriginalDemandedElts;
  SDLoc dl(Op);
 
  // 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(Op->getAsAPIntVal());
    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 (VT.isScalableVector())
      return false;
    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::SPLAT_VECTOR: {
    SDValue Scl = Op.getOperand(0);
    APInt DemandedSclBits = DemandedBits.zextOrTrunc(Scl.getValueSizeInBits());
    KnownBits KnownScl;
    if (SimplifyDemandedBits(Scl, DemandedSclBits, KnownScl, TLO, Depth + 1))
      return true;
 
    // Implicitly truncate the bits to match the official semantics of
    // SPLAT_VECTOR.
    Known = KnownScl.trunc(BitWidth);
    break;
  }
  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: {
    if (VT.isScalableVector())
      return false;
    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 = Known.intersectWith(KnownVec);
 
    return false;
  }
  case ISD::INSERT_SUBVECTOR: {
    if (VT.isScalableVector())
      return false;
    // 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 = Known.intersectWith(KnownSub);
    if (!!DemandedSrcElts)
      Known = Known.intersectWith(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: {
    if (VT.isScalableVector())
      return false;
    // 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: {
    if (VT.isScalableVector())
      return false;
    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 = Known.intersectWith(Known2);
    }
    break;
  }
  case ISD::VECTOR_SHUFFLE: {
    assert(!VT.isScalableVector());
    ArrayRef<int> ShuffleMask = cast<ShuffleVectorSDNode>(Op)->getMask();
 
    // Collect demanded elements from shuffle operands..
    APInt DemandedLHS, DemandedRHS;
    if (!getShuffleDemandedElts(NumElts, ShuffleMask, DemandedElts, DemandedLHS,
                                DemandedRHS))
      break;
 
    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 = Known.intersectWith(Known2);
      }
      if (!!DemandedRHS) {
        if (SimplifyDemandedBits(Op1, DemandedBits, DemandedRHS, Known2, TLO,
                                 Depth + 1))
          return true;
        Known = Known.intersectWith(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, DemandedElts)) {
      // 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 && !VT.isScalableVector() &&
        (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;
    if (SimplifyDemandedBits(Op0, ~Known.Zero & DemandedBits, DemandedElts,
                             Known2, TLO, Depth + 1))
      return true;
 
    // 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);
    SDNodeFlags Flags = Op.getNode()->getFlags();
    if (SimplifyDemandedBits(Op1, DemandedBits, DemandedElts, Known, TLO,
                             Depth + 1)) {
      if (Flags.hasDisjoint()) {
        Flags.setDisjoint(false);
        Op->setFlags(Flags);
      }
      return true;
    }
 
    if (SimplifyDemandedBits(Op0, ~Known.One & DemandedBits, DemandedElts,
                             Known2, TLO, Depth + 1)) {
      if (Flags.hasDisjoint()) {
        Flags.setDisjoint(false);
        Op->setFlags(Flags);
      }
      return true;
    }
 
    // 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;
    if (SimplifyDemandedBits(Op0, DemandedBits, DemandedElts, Known2, TLO,
                             Depth + 1))
      return true;
 
    // 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, DemandedElts,
                             Known, TLO, Depth + 1))
      return true;
    if (SimplifyDemandedBits(Op.getOperand(1), DemandedBits, DemandedElts,
                             Known2, TLO, Depth + 1))
      return true;
 
    // 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 = Known.intersectWith(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;
 
    // Only known if known in both the LHS and RHS.
    Known = Known.intersectWith(Known2);
    break;
  case ISD::SELECT_CC:
    if (SimplifyDemandedBits(Op.getOperand(3), DemandedBits, DemandedElts,
                             Known, TLO, Depth + 1))
      return true;
    if (SimplifyDemandedBits(Op.getOperand(2), DemandedBits, DemandedElts,
                             Known2, TLO, Depth + 1))
      return true;
 
    // 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 = Known.intersectWith(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 (std::optional<uint64_t> KnownSA =
            TLO.DAG.getValidShiftAmount(Op, DemandedElts, Depth + 1)) {
      unsigned ShAmt = *KnownSA;
      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 (std::optional<uint64_t> InnerSA =
                  TLO.DAG.getValidShiftAmount(Op0, DemandedElts, Depth + 2)) {
            unsigned C1 = *InnerSA;
            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)) {
          SDValue NarrowShl = TLO.DAG.getNode(
              ISD::SHL, dl, InnerVT, InnerOp,
              TLO.DAG.getShiftAmountConstant(ShAmt, InnerVT, dl));
          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 (std::optional<uint64_t> SA2 = TLO.DAG.getValidShiftAmount(
                  InnerOp, DemandedElts, Depth + 2)) {
            unsigned InnerShAmt = *SA2;
            if (InnerShAmt < ShAmt && InnerShAmt < InnerBits &&
                DemandedBits.getActiveBits() <=
                    (InnerBits - InnerShAmt + ShAmt) &&
                DemandedBits.countr_zero() >= 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)) {
        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.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.isAllOnes() || !DemandedElts.isAllOnes()) {
        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);
        }
      }
 
      // TODO: Can we merge this fold with the one below?
      // Try shrinking the operation as long as the shift amount will still be
      // in range.
      if (ShAmt < DemandedBits.getActiveBits() && !VT.isVector() &&
          Op.getNode()->hasOneUse()) {
        // Search for the smallest integer type with free casts to and from
        // Op's type. For expedience, just check power-of-2 integer types.
        unsigned DemandedSize = DemandedBits.getActiveBits();
        for (unsigned SmallVTBits = llvm::bit_ceil(DemandedSize);
             SmallVTBits < BitWidth; SmallVTBits = NextPowerOf2(SmallVTBits)) {
          EVT SmallVT = EVT::getIntegerVT(*TLO.DAG.getContext(), SmallVTBits);
          if (isNarrowingProfitable(VT, SmallVT) &&
              isTypeDesirableForOp(ISD::SHL, SmallVT) &&
              isTruncateFree(VT, SmallVT) && isZExtFree(SmallVT, VT) &&
              (!TLO.LegalOperations() || isOperationLegal(ISD::SHL, SmallVT))) {
            assert(DemandedSize <= SmallVTBits &&
                   "Narrowed below demanded bits?");
            // We found a type with free casts.
            SDValue NarrowShl = TLO.DAG.getNode(
                ISD::SHL, dl, SmallVT,
                TLO.DAG.getNode(ISD::TRUNCATE, dl, SmallVT, Op.getOperand(0)),
                TLO.DAG.getShiftAmountConstant(ShAmt, SmallVT, dl));
            return TLO.CombineTo(
                Op, TLO.DAG.getNode(ISD::ANY_EXTEND, dl, VT, NarrowShl));
          }
        }
      }
 
      // Narrow shift to lower half - similar to ShrinkDemandedOp.
      // (shl i64:x, K) -> (i64 zero_extend (shl (i32 (trunc i64:x)), K))
      // Only do this if we demand the upper half so the knownbits are correct.
      unsigned HalfWidth = BitWidth / 2;
      if ((BitWidth % 2) == 0 && !VT.isVector() && ShAmt < HalfWidth &&
          DemandedBits.countLeadingOnes() >= HalfWidth) {
        EVT HalfVT = EVT::getIntegerVT(*TLO.DAG.getContext(), HalfWidth);
        if (isNarrowingProfitable(VT, HalfVT) &&
            isTypeDesirableForOp(ISD::SHL, HalfVT) &&
            isTruncateFree(VT, HalfVT) && isZExtFree(HalfVT, VT) &&
            (!TLO.LegalOperations() || isOperationLegal(ISD::SHL, HalfVT))) {
          // If we're demanding the upper bits at all, we must ensure
          // that the upper bits of the shift result are known to be zero,
          // which is equivalent to the narrow shift being NUW.
          if (bool IsNUW = (Known.countMinLeadingZeros() >= HalfWidth)) {
            bool IsNSW = Known.countMinSignBits() > HalfWidth;
            SDNodeFlags Flags;
            Flags.setNoSignedWrap(IsNSW);
            Flags.setNoUnsignedWrap(IsNUW);
            SDValue NewOp = TLO.DAG.getNode(ISD::TRUNCATE, dl, HalfVT, Op0);
            SDValue NewShiftAmt =
                TLO.DAG.getShiftAmountConstant(ShAmt, HalfVT, dl);
            SDValue NewShift = TLO.DAG.getNode(ISD::SHL, dl, HalfVT, NewOp,
                                               NewShiftAmt, Flags);
            SDValue NewExt =
                TLO.DAG.getNode(ISD::ZERO_EXTEND, dl, VT, NewShift);
            return TLO.CombineTo(Op, NewExt);
          }
        }
      }
    } 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.countl_zero()) {
        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 (std::optional<uint64_t> MaxSA =
            TLO.DAG.getValidMaximumShiftAmount(Op, DemandedElts, Depth + 1)) {
      unsigned ShAmt = *MaxSA;
      unsigned NumSignBits =
          TLO.DAG.ComputeNumSignBits(Op0, DemandedElts, Depth + 1);
      unsigned UpperDemandedBits = BitWidth - DemandedBits.countr_zero();
      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();
 
    if (std::optional<uint64_t> KnownSA =
            TLO.DAG.getValidShiftAmount(Op, DemandedElts, Depth + 1)) {
      unsigned ShAmt = *KnownSA;
      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 (std::optional<uint64_t> InnerSA =
                  TLO.DAG.getValidShiftAmount(Op0, DemandedElts, Depth + 2)) {
            unsigned C1 = *InnerSA;
            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);
 
      // Narrow shift to lower half - similar to ShrinkDemandedOp.
      // (srl i64:x, K) -> (i64 zero_extend (srl (i32 (trunc i64:x)), K))
      if ((BitWidth % 2) == 0 && !VT.isVector()) {
        APInt HiBits = APInt::getHighBitsSet(BitWidth, BitWidth / 2);
        EVT HalfVT = EVT::getIntegerVT(*TLO.DAG.getContext(), BitWidth / 2);
        if (isNarrowingProfitable(VT, HalfVT) &&
            isTypeDesirableForOp(ISD::SRL, HalfVT) &&
            isTruncateFree(VT, HalfVT) && isZExtFree(HalfVT, VT) &&
            (!TLO.LegalOperations() || isOperationLegal(ISD::SRL, HalfVT)) &&
            ((InDemandedMask.countLeadingZeros() >= (BitWidth / 2)) ||
             TLO.DAG.MaskedValueIsZero(Op0, HiBits))) {
          SDValue NewOp = TLO.DAG.getNode(ISD::TRUNCATE, dl, HalfVT, Op0);
          SDValue NewShiftAmt =
              TLO.DAG.getShiftAmountConstant(ShAmt, HalfVT, dl);
          SDValue NewShift =
              TLO.DAG.getNode(ISD::SRL, dl, HalfVT, NewOp, NewShiftAmt);
          return TLO.CombineTo(
              Op, TLO.DAG.getNode(ISD::ZERO_EXTEND, dl, VT, NewShift));
        }
      }
 
      // Compute the new bits that are at the top now.
      if (SimplifyDemandedBits(Op0, InDemandedMask, DemandedElts, Known, TLO,
                               Depth + 1))
        return true;
      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.isAllOnes() || !DemandedElts.isAllOnes()) {
        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);
        }
      }
    } else {
      // Use generic knownbits computation as it has support for non-uniform
      // shift amounts.
      Known = TLO.DAG.computeKnownBits(Op, DemandedElts, Depth);
    }
 
    // Try to match AVG patterns (after shift simplification).
    if (SDValue AVG = combineShiftToAVG(Op, TLO, *this, DemandedBits,
                                        DemandedElts, Depth + 1))
      return TLO.CombineTo(Op, AVG);
 
    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.countr_zero();
    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));
 
    if (std::optional<uint64_t> KnownSA =
            TLO.DAG.getValidShiftAmount(Op, DemandedElts, Depth + 1)) {
      unsigned ShAmt = *KnownSA;
      if (ShAmt == 0)
        return TLO.CombineTo(Op, Op0);
 
      // fold (sra (shl x, c1), c1) -> sext_inreg for some c1 and target
      // supports sext_inreg.
      if (Op0.getOpcode() == ISD::SHL) {
        if (std::optional<uint64_t> InnerSA =
                TLO.DAG.getValidShiftAmount(Op0, DemandedElts, Depth + 2)) {
          unsigned LowBits = BitWidth - ShAmt;
          EVT ExtVT = EVT::getIntegerVT(*TLO.DAG.getContext(), LowBits);
          if (VT.isVector())
            ExtVT = EVT::getVectorVT(*TLO.DAG.getContext(), ExtVT,
                                     VT.getVectorElementCount());
 
          if (*InnerSA == ShAmt) {
            if (!TLO.LegalOperations() ||
                getOperationAction(ISD::SIGN_EXTEND_INREG, ExtVT) == Legal)
              return TLO.CombineTo(
                  Op, TLO.DAG.getNode(ISD::SIGN_EXTEND_INREG, dl, VT,
                                      Op0.getOperand(0),
                                      TLO.DAG.getValueType(ExtVT)));
 
            // Even if we can't convert to sext_inreg, we might be able to
            // remove this shift pair if the input is already sign extended.
            unsigned NumSignBits =
                TLO.DAG.ComputeNumSignBits(Op0.getOperand(0), DemandedElts);
            if (NumSignBits > ShAmt)
              return TLO.CombineTo(Op, Op0.getOperand(0));
          }
        }
      }
 
      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.countl_zero() < ShAmt)
        InDemandedMask.setSignBit();
 
      if (SimplifyDemandedBits(Op0, InDemandedMask, DemandedElts, Known, TLO,
                               Depth + 1))
        return true;
      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.countl_zero() >= 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);
        }
      }
    }
 
    // Try to match AVG patterns (after shift simplification).
    if (SDValue AVG = combineShiftToAVG(Op, TLO, *this, DemandedBits,
                                        DemandedElts, Depth + 1))
      return TLO.CombineTo(Op, AVG);
 
    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 = Known.unionWith(Known2);
 
      // 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.countr_zero() >= (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.countl_zero() >= (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::SMIN:
  case ISD::SMAX:
  case ISD::UMIN:
  case ISD::UMAX: {
    unsigned Opc = Op.getOpcode();
    SDValue Op0 = Op.getOperand(0);
    SDValue Op1 = Op.getOperand(1);
 
    // If we're only demanding signbits, then we can simplify to OR/AND node.
    unsigned BitOp =
        (Opc == ISD::SMIN || Opc == ISD::UMAX) ? ISD::OR : ISD::AND;
    unsigned NumSignBits =
        std::min(TLO.DAG.ComputeNumSignBits(Op0, DemandedElts, Depth + 1),
                 TLO.DAG.ComputeNumSignBits(Op1, DemandedElts, Depth + 1));
    unsigned NumDemandedUpperBits = BitWidth - DemandedBits.countr_zero();
    if (NumSignBits >= NumDemandedUpperBits)
      return TLO.CombineTo(Op, TLO.DAG.getNode(BitOp, SDLoc(Op), VT, Op0, Op1));
 
    // Check if one arg is always less/greater than (or equal) to the other arg.
    KnownBits Known0 = TLO.DAG.computeKnownBits(Op0, DemandedElts, Depth + 1);
    KnownBits Known1 = TLO.DAG.computeKnownBits(Op1, DemandedElts, Depth + 1);
    switch (Opc) {
    case ISD::SMIN:
      if (std::optional<bool> IsSLE = KnownBits::sle(Known0, Known1))
        return TLO.CombineTo(Op, *IsSLE ? Op0 : Op1);
      if (std::optional<bool> IsSLT = KnownBits::slt(Known0, Known1))
        return TLO.CombineTo(Op, *IsSLT ? Op0 : Op1);
      Known = KnownBits::smin(Known0, Known1);
      break;
    case ISD::SMAX:
      if (std::optional<bool> IsSGE = KnownBits::sge(Known0, Known1))
        return TLO.CombineTo(Op, *IsSGE ? Op0 : Op1);
      if (std::optional<bool> IsSGT = KnownBits::sgt(Known0, Known1))
        return TLO.CombineTo(Op, *IsSGT ? Op0 : Op1);
      Known = KnownBits::smax(Known0, Known1);
      break;
    case ISD::UMIN:
      if (std::optional<bool> IsULE = KnownBits::ule(Known0, Known1))
        return TLO.CombineTo(Op, *IsULE ? Op0 : Op1);
      if (std::optional<bool> IsULT = KnownBits::ult(Known0, Known1))
        return TLO.CombineTo(Op, *IsULT ? Op0 : Op1);
      Known = KnownBits::umin(Known0, Known1);
      break;
    case ISD::UMAX:
      if (std::optional<bool> IsUGE = KnownBits::uge(Known0, Known1))
        return TLO.CombineTo(Op, *IsUGE ? Op0 : Op1);
      if (std::optional<bool> IsUGT = KnownBits::ugt(Known0, Known1))
        return TLO.CombineTo(Op, *IsUGT ? Op0 : Op1);
      Known = KnownBits::umax(Known0, Known1);
      break;
    }
    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.countl_zero();
    unsigned NTZ = DemandedBits.countr_zero();
 
    // 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)) {
        unsigned ShiftAmount = NLZ > NTZ ? NLZ - NTZ : NTZ - NLZ;
        SDValue ShAmt = TLO.DAG.getShiftAmountConstant(ShiftAmount, VT, dl);
        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.getShiftAmountConstant(BitWidth - ExVTBits, 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;
 
    // 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_VECTOR_INREG:
    if (VT.isScalableVector())
      return false;
    [[fallthrough]];
  case ISD::ZERO_EXTEND: {
    SDValue Src = Op.getOperand(0);
    EVT SrcVT = Src.getValueType();
    unsigned InBits = SrcVT.getScalarSizeInBits();
    unsigned InElts = SrcVT.isFixedLengthVector() ? 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));
    }
 
    SDNodeFlags Flags = Op->getFlags();
    APInt InDemandedBits = DemandedBits.trunc(InBits);
    APInt InDemandedElts = DemandedElts.zext(InElts);
    if (SimplifyDemandedBits(Src, InDemandedBits, InDemandedElts, Known, TLO,
                             Depth + 1)) {
      if (Flags.hasNonNeg()) {
        Flags.setNonNeg(false);
        Op->setFlags(Flags);
      }
      return true;
    }
    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_VECTOR_INREG:
    if (VT.isScalableVector())
      return false;
    [[fallthrough]];
  case ISD::SIGN_EXTEND: {
    SDValue Src = Op.getOperand(0);
    EVT SrcVT = Src.getValueType();
    unsigned InBits = SrcVT.getScalarSizeInBits();
    unsigned InElts = SrcVT.isFixedLengthVector() ? SrcVT.getVectorNumElements() : 1;
    bool IsVecInReg = Op.getOpcode() == ISD::SIGN_EXTEND_VECTOR_INREG;
 
    APInt InDemandedElts = DemandedElts.zext(InElts);
    APInt InDemandedBits = DemandedBits.trunc(InBits);
 
    // Since some of the sign extended bits are demanded, we know that the sign
    // bit is demanded.
    InDemandedBits.setBit(InBits - 1);
 
    // 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));
 
      // Don't lose an all signbits 0/-1 splat on targets with 0/-1 booleans.
      if (getBooleanContents(VT) != ZeroOrNegativeOneBooleanContent ||
          TLO.DAG.ComputeNumSignBits(Src, InDemandedElts, Depth + 1) !=
              InBits) {
        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));
      }
    }
 
    if (SimplifyDemandedBits(Src, InDemandedBits, InDemandedElts, Known, TLO,
                             Depth + 1))
      return true;
    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)) {
        SDNodeFlags Flags;
        if (!IsVecInReg)
          Flags.setNonNeg(true);
        return TLO.CombineTo(Op, TLO.DAG.getNode(Opc, dl, VT, Src, Flags));
      }
    }
 
    // 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_VECTOR_INREG:
    if (VT.isScalableVector())
      return false;
    [[fallthrough]];
  case ISD::ANY_EXTEND: {
    SDValue Src = Op.getOperand(0);
    EVT SrcVT = Src.getValueType();
    unsigned InBits = SrcVT.getScalarSizeInBits();
    unsigned InElts = SrcVT.isFixedLengthVector() ? 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.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()) {
        if (isTruncateFree(Src, VT) &&
            !isTruncateFree(Src.getValueType(), VT)) {
          // If truncate is only free at trunc(srl), do not turn it into
          // srl(trunc). The check is done by first check the truncate is free
          // at Src's opcode(srl), then check the truncate is not done by
          // referencing sub-register. In test, if both trunc(srl) and
          // srl(trunc)'s trunc are free, srl(trunc) performs better. If only
          // trunc(srl)'s trunc is free, trunc(srl) is better.
          break;
        }
 
        std::optional<uint64_t> ShAmtC =
            TLO.DAG.getValidShiftAmount(Src, DemandedElts, Depth + 2);
        if (!ShAmtC || *ShAmtC >= BitWidth)
          break;
        uint64_t ShVal = *ShAmtC;
 
        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.getShiftAmountConstant(ShVal, VT, dl);
          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;
    }
 
    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;
 
    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: {
    if (VT.isScalableVector())
      return false;
    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;
 
      // 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.getBitcast(VT, DemandedSrc);
          return TLO.CombineTo(Op, NewOp);
        }
      }
    }
 
    // 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.countr_zero();
      ConstantSDNode *C = isConstOrConstSplat(Op.getOperand(1), DemandedElts);
      if (C && C->getAPIntValue().countr_zero() == CTZ) {
        SDValue AmtC = TLO.DAG.getShiftAmountConstant(CTZ, VT, dl);
        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.countl_zero();
    APInt LoMask = APInt::getLowBitsSet(BitWidth, BitWidth - DemandedBitsLZ);
    KnownBits KnownOp0, KnownOp1;
    auto GetDemandedBitsLHSMask = [&](APInt Demanded,
                                      const KnownBits &KnownRHS) {
      if (Op.getOpcode() == ISD::MUL)
        Demanded.clearHighBits(KnownRHS.countMinTrailingZeros());
      return Demanded;
    };
    if (SimplifyDemandedBits(Op1, LoMask, DemandedElts, KnownOp1, TLO,
                             Depth + 1) ||
        SimplifyDemandedBits(Op0, GetDemandedBitsLHSMask(LoMask, KnownOp1),
                             DemandedElts, KnownOp0, 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;
    }
 
    // neg x with only low bit demanded is simply x.
    if (Op.getOpcode() == ISD::SUB && DemandedBits.isOne() &&
        isNullConstant(Op0))
      return TLO.CombineTo(Op, Op1);
 
    // 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) {
      SDValue ShlAmtC = TLO.DAG.getShiftAmountConstant(ShlAmt, VT, dl);
      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);
      }
    }
 
    if (Op.getOpcode() == ISD::MUL) {
      Known = KnownBits::mul(KnownOp0, KnownOp1);
    } else { // Op.getOpcode() is either ISD::ADD or ISD::SUB.
      Known = KnownBits::computeForAddSub(
          Op.getOpcode() == ISD::ADD, Flags.hasNoSignedWrap(),
          Flags.hasNoUnsignedWrap(), KnownOp0, KnownOp1);
    }
    break;
  }
  default:
    // We also ask the target about intrinsics (which could be specific to it).
    if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
        Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN) {
      // TODO: Probably okay to remove after audit; here to reduce change size
      // in initial enablement patch for scalable vectors
      if (Op.getValueType().isScalableVector())
        break;
      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 (auto *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.isFixedLengthVector() ? VT.getVectorNumElements() : 1;
  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, Op->getFlags());
      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::FREEZE: {
    SDValue N0 = Op.getOperand(0);
    if (TLO.DAG.isGuaranteedNotToBeUndefOrPoison(N0, DemandedElts,
                                                 /*PoisonOnly=*/false))
      return TLO.CombineTo(Op, N0);
 
    // TODO: Replace this with the general fold from DAGCombiner::visitFREEZE
    // freeze(op(x, ...)) -> op(freeze(x), ...).
    if (N0.getOpcode() == ISD::SCALAR_TO_VECTOR && DemandedElts == 1)
      return TLO.CombineTo(
          Op, TLO.DAG.getNode(ISD::SCALAR_TO_VECTOR, DL, VT,
                              TLO.DAG.getFreeze(N0.getOperand(0))));
    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->ops());
        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, ZeroSel;
    if (SimplifyDemandedVectorElts(Sel, DemandedElts, UndefSel, ZeroSel, 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, ZeroSel, 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::AVGCEILS:
  case ISD::AVGCEILU:
  case ISD::AVGFLOORS:
  case ISD::AVGFLOORU:
  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!");
 
  // If Op can't create undef/poison and none of its operands are undef/poison
  // then Op is never undef/poison.
  return !canCreateUndefOrPoisonForTargetNode(Op, DemandedElts, DAG, PoisonOnly,
                                              /*ConsiderFlags*/ true, Depth) &&
         all_of(Op->ops(), [&](SDValue V) {
           return DAG.isGuaranteedNotToBeUndefOrPoison(V, PoisonOnly,
                                                       Depth + 1);
         });
}
 
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,
                                               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 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);
  }
 
  // Try to eliminate a power-of-2 mask constant by converting to a signbit
  // test in a narrow type that we can truncate to with no cost. Examples:
  // (i32 X & 32768) == 0 --> (trunc X to i16) >= 0
  // (i32 X & 32768) != 0 --> (trunc X to i16) < 0
  // TODO: This conservatively checks for type legality on the source and
  //       destination types. That may inhibit optimizations, but it also
  //       allows setcc->shift transforms that may be more beneficial.
  auto *AndC = dyn_cast<ConstantSDNode>(N0.getOperand(1));
  if (AndC && isNullConstant(N1) && AndC->getAPIntValue().isPowerOf2() &&
      isTypeLegal(OpVT) && N0.hasOneUse()) {
    EVT NarrowVT = EVT::getIntegerVT(*DAG.getContext(),
                                     AndC->getAPIntValue().getActiveBits());
    if (isTruncateFree(OpVT, NarrowVT) && isTypeLegal(NarrowVT)) {
      SDValue Trunc = DAG.getZExtOrTrunc(N0.getOperand(0), DL, NarrowVT);
      SDValue Zero = DAG.getConstant(0, DL, NarrowVT);
      return DAG.getSetCC(DL, VT, Trunc, Zero,
                          Cond == ISD::SETEQ ? ISD::SETGE : ISD::SETLT);
    }
  }
 
  // 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();
  }
 
  // TODO: We should invert (X & Y) eq/ne 0 -> (X & Y) ne/eq Y if
  // `isXAndYEqZeroPreferableToXAndYEqY` is false. This is a bit difficult as
  // its liable to create and infinite loop.
  SDValue Zero = DAG.getConstant(0, DL, OpVT);
  if (isXAndYEqZeroPreferableToXAndYEqY(Cond, OpVT) &&
      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).
    if (isNullConstant(Y))
      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();
 
  // Unfold into:  sext_inreg(%x) cond %x
  // Where 'cond' will be either 'eq' or 'ne'.
  SDValue SExtInReg = DAG.getNode(
      ISD::SIGN_EXTEND_INREG, DL, XVT, X,
      DAG.getValueType(EVT::getIntegerVT(*DAG.getContext(), KeptBits)));
  return DAG.getSetCC(DL, SCCVT, SExtInReg, X, NewCond);
}
 
// (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)->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
  SDValue One = DAG.getShiftAmountConstant(1, OpVT, DL);
  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 cheap vector op.
    if (CTVT.isVector() && TLI.isCtpopFast(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
  if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) && C1 == 1) {
    // Keep the CTPOP if it is cheap.
    if (TLI.isCtpopFast(CTVT))
      return SDValue();
 
    SDValue Zero = DAG.getConstant(0, dl, CTVT);
    SDValue NegOne = DAG.getAllOnesConstant(dl, CTVT);
    assert(CTVT.isInteger());
    SDValue Add = DAG.getNode(ISD::ADD, dl, CTVT, CTOp, NegOne);
 
    // Its not uncommon for known-never-zero X to exist in (ctpop X) eq/ne 1, so
    // check before emitting a potentially unnecessary op.
    if (DAG.isKnownNeverZero(CTOp)) {
      // (ctpop x) == 1 --> (x & x-1) == 0
      // (ctpop x) != 1 --> (x & x-1) != 0
      SDValue And = DAG.getNode(ISD::AND, dl, CTVT, CTOp, Add);
      SDValue RHS = DAG.getSetCC(dl, VT, And, Zero, Cond);
      return RHS;
    }
 
    // (ctpop x) == 1 --> (x ^ x-1) >  x-1
    // (ctpop x) != 1 --> (x ^ x-1) <= x-1
    SDValue Xor = DAG.getNode(ISD::XOR, dl, CTVT, CTOp, Add);
    ISD::CondCode CmpCond = Cond == ISD::SETEQ ? ISD::SETUGT : ISD::SETULE;
    return DAG.getSetCC(dl, VT, Xor, Add, CmpCond);
  }
 
  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();
  };