| //===-- 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/BitVector.h" |
| #include "llvm/ADT/STLExtras.h" |
| #include "llvm/CodeGen/CallingConvLower.h" |
| #include "llvm/CodeGen/MachineFrameInfo.h" |
| #include "llvm/CodeGen/MachineFunction.h" |
| #include "llvm/CodeGen/MachineJumpTableInfo.h" |
| #include "llvm/CodeGen/MachineRegisterInfo.h" |
| #include "llvm/CodeGen/SelectionDAG.h" |
| #include "llvm/CodeGen/TargetRegisterInfo.h" |
| #include "llvm/CodeGen/TargetSubtargetInfo.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/ErrorHandling.h" |
| #include "llvm/Support/KnownBits.h" |
| #include "llvm/Support/MathExtras.h" |
| #include "llvm/Target/TargetLoweringObjectFile.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(); |
| |
| // Conservatively require the attributes of the call to match those of |
| // the return. Ignore NoAlias and NonNull because they don't affect the |
| // call sequence. |
| AttributeList CallerAttrs = F.getAttributes(); |
| if (AttrBuilder(CallerAttrs, AttributeList::ReturnIndex) |
| .removeAttribute(Attribute::NoAlias) |
| .removeAttribute(Attribute::NonNull) |
| .hasAttributes()) |
| return false; |
| |
| // It's not safe to eliminate the sign / zero extension of the return value. |
| if (CallerAttrs.hasAttribute(AttributeList::ReturnIndex, Attribute::ZExt) || |
| CallerAttrs.hasAttribute(AttributeList::ReturnIndex, 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; |
| unsigned 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::CopyFromReg) |
| return false; |
| unsigned 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(ImmutableCallSite *CS, |
| unsigned ArgIdx) { |
| IsSExt = CS->paramHasAttr(ArgIdx, Attribute::SExt); |
| IsZExt = CS->paramHasAttr(ArgIdx, Attribute::ZExt); |
| IsInReg = CS->paramHasAttr(ArgIdx, Attribute::InReg); |
| IsSRet = CS->paramHasAttr(ArgIdx, Attribute::StructRet); |
| IsNest = CS->paramHasAttr(ArgIdx, Attribute::Nest); |
| IsByVal = CS->paramHasAttr(ArgIdx, Attribute::ByVal); |
| IsInAlloca = CS->paramHasAttr(ArgIdx, Attribute::InAlloca); |
| IsReturned = CS->paramHasAttr(ArgIdx, Attribute::Returned); |
| IsSwiftSelf = CS->paramHasAttr(ArgIdx, Attribute::SwiftSelf); |
| IsSwiftError = CS->paramHasAttr(ArgIdx, Attribute::SwiftError); |
| Alignment = CS->getParamAlignment(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, bool isSigned, |
| const SDLoc &dl, bool doesNotReturn, |
| bool isReturnValueUsed) const { |
| TargetLowering::ArgListTy Args; |
| Args.reserve(Ops.size()); |
| |
| TargetLowering::ArgListEntry Entry; |
| for (SDValue Op : Ops) { |
| Entry.Node = Op; |
| Entry.Ty = Entry.Node.getValueType().getTypeForEVT(*DAG.getContext()); |
| Entry.IsSExt = shouldSignExtendTypeInLibCall(Op.getValueType(), isSigned); |
| Entry.IsZExt = !shouldSignExtendTypeInLibCall(Op.getValueType(), isSigned); |
| 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, isSigned); |
| CLI.setDebugLoc(dl) |
| .setChain(DAG.getEntryNode()) |
| .setLibCallee(getLibcallCallingConv(LC), RetTy, Callee, std::move(Args)) |
| .setNoReturn(doesNotReturn) |
| .setDiscardResult(!isReturnValueUsed) |
| .setSExtResult(signExtend) |
| .setZExtResult(!signExtend); |
| return LowerCallTo(CLI); |
| } |
| |
| /// 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 { |
| 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::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::SETO: |
| LC1 = (VT == MVT::f32) ? RTLIB::O_F32 : |
| (VT == MVT::f64) ? RTLIB::O_F64 : |
| (VT == MVT::f128) ? RTLIB::O_F128 : RTLIB::O_PPCF128; |
| break; |
| case ISD::SETONE: |
| // SETONE = SETOLT | SETOGT |
| LC1 = (VT == MVT::f32) ? RTLIB::OLT_F32 : |
| (VT == MVT::f64) ? RTLIB::OLT_F64 : |
| (VT == MVT::f128) ? RTLIB::OLT_F128 : RTLIB::OLT_PPCF128; |
| LC2 = (VT == MVT::f32) ? RTLIB::OGT_F32 : |
| (VT == MVT::f64) ? RTLIB::OGT_F64 : |
| (VT == MVT::f128) ? RTLIB::OGT_F128 : RTLIB::OGT_PPCF128; |
| break; |
| 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 comparions lib calls. |
| EVT RetVT = getCmpLibcallReturnType(); |
| SDValue Ops[2] = {NewLHS, NewRHS}; |
| NewLHS = makeLibCall(DAG, LC1, RetVT, Ops, false /*sign irrelevant*/, |
| dl).first; |
| NewRHS = DAG.getConstant(0, dl, RetVT); |
| |
| CCCode = getCmpLibcallCC(LC1); |
| if (ShouldInvertCC) |
| CCCode = getSetCCInverse(CCCode, /*isInteger=*/true); |
| |
| if (LC2 != RTLIB::UNKNOWN_LIBCALL) { |
| SDValue Tmp = DAG.getNode( |
| ISD::SETCC, dl, |
| getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), RetVT), |
| NewLHS, NewRHS, DAG.getCondCode(CCCode)); |
| NewLHS = makeLibCall(DAG, LC2, RetVT, Ops, false/*sign irrelevant*/, |
| dl).first; |
| NewLHS = DAG.getNode( |
| ISD::SETCC, dl, |
| getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), RetVT), |
| NewLHS, NewRHS, DAG.getCondCode(getCmpLibcallCC(LC2))); |
| NewLHS = DAG.getNode(ISD::OR, dl, Tmp.getValueType(), Tmp, NewLHS); |
| NewRHS = SDValue(); |
| } |
| } |
| |
| /// Return the entry encoding for a jump table in the current function. The |
| /// returned value is a member of the MachineJumpTableInfo::JTEntryKind enum. |
| unsigned TargetLowering::getJumpTableEncoding() const { |
| // In non-pic modes, just use the address of a block. |
| if (!isPositionIndependent()) |
| return MachineJumpTableInfo::EK_BlockAddress; |
| |
| // In PIC mode, if the target supports a GPRel32 directive, use it. |
| if (getTargetMachine().getMCAsmInfo()->getGPRel32Directive() != nullptr) |
| return MachineJumpTableInfo::EK_GPRel32BlockAddress; |
| |
| // Otherwise, use a label difference. |
| return MachineJumpTableInfo::EK_LabelDifference32; |
| } |
| |
| SDValue TargetLowering::getPICJumpTableRelocBase(SDValue Table, |
| SelectionDAG &DAG) const { |
| // If our PIC model is GP relative, use the global offset table as the base. |
| unsigned JTEncoding = getJumpTableEncoding(); |
| |
| if ((JTEncoding == MachineJumpTableInfo::EK_GPRel64BlockAddress) || |
| (JTEncoding == MachineJumpTableInfo::EK_GPRel32BlockAddress)) |
| return DAG.getGLOBAL_OFFSET_TABLE(getPointerTy(DAG.getDataLayout())); |
| |
| return Table; |
| } |
| |
| /// This returns the relocation base for the given PIC jumptable, the same as |
| /// getPICJumpTableRelocBase, but as an MCExpr. |
| const MCExpr * |
| TargetLowering::getPICJumpTableRelocBaseExpr(const MachineFunction *MF, |
| unsigned JTI,MCContext &Ctx) const{ |
| // The normal PIC reloc base is the label at the start of the jump table. |
| return MCSymbolRefExpr::create(MF->getJTISymbol(JTI, Ctx), Ctx); |
| } |
| |
| bool |
| TargetLowering::isOffsetFoldingLegal(const GlobalAddressSDNode *GA) const { |
| const TargetMachine &TM = getTargetMachine(); |
| const GlobalValue *GV = GA->getGlobal(); |
| |
| // If the address is not even local to this DSO we will have to load it from |
| // a got and then add the offset. |
| if (!TM.shouldAssumeDSOLocal(*GV->getParent(), GV)) |
| return false; |
| |
| // If the code is position independent we will have to add a base register. |
| if (isPositionIndependent()) |
| return false; |
| |
| // Otherwise we can do it. |
| return true; |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // Optimization Methods |
| //===----------------------------------------------------------------------===// |
| |
| /// If the specified instruction has a constant integer operand and there are |
| /// bits set in that constant that are not demanded, then clear those bits and |
| /// return true. |
| bool TargetLowering::ShrinkDemandedConstant(SDValue Op, const APInt &Demanded, |
| TargetLoweringOpt &TLO) const { |
| SelectionDAG &DAG = TLO.DAG; |
| SDLoc DL(Op); |
| unsigned Opcode = Op.getOpcode(); |
| |
| // Do target-specific constant optimization. |
| if (targetShrinkDemandedConstant(Op, Demanded, 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) |
| 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 && Demanded.isSubsetOf(C)) |
| return false; |
| |
| if (!C.isSubsetOf(Demanded)) { |
| EVT VT = Op.getValueType(); |
| SDValue NewC = DAG.getConstant(Demanded & C, DL, VT); |
| SDValue NewOp = DAG.getNode(Opcode, DL, VT, Op.getOperand(0), NewC); |
| return TLO.CombineTo(Op, NewOp); |
| } |
| |
| break; |
| } |
| } |
| |
| return false; |
| } |
| |
| /// Convert x+y to (VT)((SmallVT)x+(SmallVT)y) if the casts are free. |
| /// This uses isZExtFree and ZERO_EXTEND for the widening cast, but it could be |
| /// generalized for targets with other types of implicit widening casts. |
| bool TargetLowering::ShrinkDemandedOp(SDValue Op, unsigned BitWidth, |
| const APInt &Demanded, |
| TargetLoweringOpt &TLO) const { |
| assert(Op.getNumOperands() == 2 && |
| "ShrinkDemandedOp only supports binary operators!"); |
| assert(Op.getNode()->getNumValues() == 1 && |
| "ShrinkDemandedOp only supports nodes with one result!"); |
| |
| SelectionDAG &DAG = TLO.DAG; |
| SDLoc dl(Op); |
| |
| // Early return, as this function cannot handle vector types. |
| if (Op.getValueType().isVector()) |
| return false; |
| |
| // Don't do this if the node has another user, which may require the |
| // full value. |
| if (!Op.getNode()->hasOneUse()) |
| return false; |
| |
| // Search for the smallest integer type with free casts to and from |
| // Op's type. For expedience, just check power-of-2 integer types. |
| const TargetLowering &TLI = DAG.getTargetLoweringInfo(); |
| unsigned DemandedSize = Demanded.getActiveBits(); |
| unsigned SmallVTBits = DemandedSize; |
| if (!isPowerOf2_32(SmallVTBits)) |
| SmallVTBits = NextPowerOf2(SmallVTBits); |
| for (; SmallVTBits < BitWidth; SmallVTBits = NextPowerOf2(SmallVTBits)) { |
| EVT SmallVT = EVT::getIntegerVT(*DAG.getContext(), SmallVTBits); |
| if (TLI.isTruncateFree(Op.getValueType(), SmallVT) && |
| TLI.isZExtFree(SmallVT, Op.getValueType())) { |
| // We found a type with free casts. |
| SDValue X = DAG.getNode( |
| Op.getOpcode(), dl, SmallVT, |
| DAG.getNode(ISD::TRUNCATE, dl, SmallVT, Op.getOperand(0)), |
| DAG.getNode(ISD::TRUNCATE, dl, SmallVT, Op.getOperand(1))); |
| assert(DemandedSize <= SmallVTBits && "Narrowed below demanded bits?"); |
| SDValue Z = DAG.getNode(ISD::ANY_EXTEND, dl, Op.getValueType(), X); |
| return TLO.CombineTo(Op, Z); |
| } |
| } |
| return false; |
| } |
| |
| bool TargetLowering::SimplifyDemandedBits(SDValue Op, const APInt &DemandedBits, |
| DAGCombinerInfo &DCI) const { |
| SelectionDAG &DAG = DCI.DAG; |
| TargetLoweringOpt TLO(DAG, !DCI.isBeforeLegalize(), |
| !DCI.isBeforeLegalizeOps()); |
| KnownBits Known; |
| |
| bool Simplified = SimplifyDemandedBits(Op, DemandedBits, Known, TLO); |
| if (Simplified) { |
| DCI.AddToWorklist(Op.getNode()); |
| DCI.CommitTargetLoweringOpt(TLO); |
| } |
| return Simplified; |
| } |
| |
| bool TargetLowering::SimplifyDemandedBits(SDValue Op, const APInt &DemandedBits, |
| KnownBits &Known, |
| TargetLoweringOpt &TLO, |
| unsigned Depth, |
| bool AssumeSingleUse) const { |
| EVT VT = Op.getValueType(); |
| APInt DemandedElts = VT.isVector() |
| ? APInt::getAllOnesValue(VT.getVectorNumElements()) |
| : APInt(1, 1); |
| return SimplifyDemandedBits(Op, DemandedBits, DemandedElts, Known, TLO, Depth, |
| AssumeSingleUse); |
| } |
| |
| /// 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!"); |
| |
| unsigned NumElts = OriginalDemandedElts.getBitWidth(); |
| assert((!Op.getValueType().isVector() || |
| NumElts == Op.getValueType().getVectorNumElements()) && |
| "Unexpected vector size"); |
| |
| APInt DemandedBits = OriginalDemandedBits; |
| APInt DemandedElts = OriginalDemandedElts; |
| SDLoc dl(Op); |
| auto &DL = TLO.DAG.getDataLayout(); |
| |
| // Don't know anything. |
| Known = KnownBits(BitWidth); |
| |
| if (Op.getOpcode() == ISD::Constant) { |
| // We know all of the bits for a constant! |
| Known.One = cast<ConstantSDNode>(Op)->getAPIntValue(); |
| Known.Zero = ~Known.One; |
| return false; |
| } |
| |
| // Other users may use these bits. |
| EVT VT = Op.getValueType(); |
| if (!Op.getNode()->hasOneUse() && !AssumeSingleUse) { |
| if (Depth != 0) { |
| // If not at the root, Just compute the Known bits to |
| // simplify things downstream. |
| Known = TLO.DAG.computeKnownBits(Op, DemandedElts, Depth); |
| return false; |
| } |
| // If this is the root being simplified, allow it to have multiple uses, |
| // just set the DemandedBits/Elts to all bits. |
| DemandedBits = APInt::getAllOnesValue(BitWidth); |
| DemandedElts = APInt::getAllOnesValue(NumElts); |
| } else if (OriginalDemandedBits == 0 || OriginalDemandedElts == 0) { |
| // Not demanding any bits/elts from Op. |
| if (!Op.isUndef()) |
| return TLO.CombineTo(Op, TLO.DAG.getUNDEF(VT)); |
| return false; |
| } else if (Depth == 6) { // Limit search depth. |
| return false; |
| } |
| |
| KnownBits Known2, KnownOut; |
| switch (Op.getOpcode()) { |
| case ISD::BUILD_VECTOR: |
| // Collect the known bits that are shared by every constant vector element. |
| Known.Zero.setAllBits(); Known.One.setAllBits(); |
| for (SDValue SrcOp : Op->ops()) { |
| if (!isa<ConstantSDNode>(SrcOp)) { |
| // We can only handle all constant values - bail out with no known bits. |
| Known = KnownBits(BitWidth); |
| return false; |
| } |
| Known2.One = cast<ConstantSDNode>(SrcOp)->getAPIntValue(); |
| Known2.Zero = ~Known2.One; |
| |
| // BUILD_VECTOR can implicitly truncate sources, we must handle this. |
| if (Known2.One.getBitWidth() != BitWidth) { |
| assert(Known2.getBitWidth() > BitWidth && |
| "Expected BUILD_VECTOR implicit truncation"); |
| Known2 = Known2.trunc(BitWidth); |
| } |
| |
| // Known bits are the values that are shared by every element. |
| // TODO: support per-element known bits. |
| Known.One &= Known2.One; |
| Known.Zero &= Known2.Zero; |
| } |
| return false; // Don't fall through, will infinitely loop. |
| case ISD::CONCAT_VECTORS: { |
| Known.Zero.setAllBits(); |
| Known.One.setAllBits(); |
| EVT SubVT = Op.getOperand(0).getValueType(); |
| unsigned NumSubVecs = Op.getNumOperands(); |
| unsigned NumSubElts = SubVT.getVectorNumElements(); |
| for (unsigned i = 0; i != NumSubVecs; ++i) { |
| APInt DemandedSubElts = |
| DemandedElts.extractBits(NumSubElts, i * NumSubElts); |
| if (SimplifyDemandedBits(Op.getOperand(i), DemandedBits, DemandedSubElts, |
| Known2, TLO, Depth + 1)) |
| return true; |
| // Known bits are shared by every demanded subvector element. |
| if (!!DemandedSubElts) { |
| Known.One &= Known2.One; |
| Known.Zero &= Known2.Zero; |
| } |
| } |
| break; |
| } |
| case ISD::VECTOR_SHUFFLE: { |
| ArrayRef<int> ShuffleMask = cast<ShuffleVectorSDNode>(Op)->getMask(); |
| |
| // Collect demanded elements from shuffle operands.. |
| APInt DemandedLHS(NumElts, 0); |
| APInt DemandedRHS(NumElts, 0); |
| for (unsigned i = 0; i != NumElts; ++i) { |
| if (!DemandedElts[i]) |
| continue; |
| int M = ShuffleMask[i]; |
| if (M < 0) { |
| // For UNDEF elements, we don't know anything about the common state of |
| // the shuffle result. |
| DemandedLHS.clearAllBits(); |
| DemandedRHS.clearAllBits(); |
| break; |
| } |
| assert(0 <= M && M < (int)(2 * NumElts) && "Shuffle index out of range"); |
| if (M < (int)NumElts) |
| DemandedLHS.setBit(M); |
| else |
| DemandedRHS.setBit(M - NumElts); |
| } |
| |
| if (!!DemandedLHS || !!DemandedRHS) { |
| Known.Zero.setAllBits(); |
| Known.One.setAllBits(); |
| if (!!DemandedLHS) { |
| if (SimplifyDemandedBits(Op.getOperand(0), DemandedBits, DemandedLHS, |
| Known2, TLO, Depth + 1)) |
| return true; |
| Known.One &= Known2.One; |
| Known.Zero &= Known2.Zero; |
| } |
| if (!!DemandedRHS) { |
| if (SimplifyDemandedBits(Op.getOperand(1), DemandedBits, DemandedRHS, |
| Known2, TLO, Depth + 1)) |
| return true; |
| Known.One &= Known2.One; |
| Known.Zero &= Known2.Zero; |
| } |
| } |
| break; |
| } |
| case ISD::AND: { |
| SDValue Op0 = Op.getOperand(0); |
| SDValue Op1 = Op.getOperand(1); |
| |
| // If the RHS is a constant, check to see if the LHS would be zero without |
| // using the bits from the RHS. Below, we use knowledge about the RHS to |
| // simplify the LHS, here we're using information from the LHS to simplify |
| // the RHS. |
| if (ConstantSDNode *RHSC = isConstOrConstSplat(Op1)) { |
| // Do not increment Depth here; that can cause an infinite loop. |
| KnownBits LHSKnown = TLO.DAG.computeKnownBits(Op0, DemandedElts, Depth); |
| // If the LHS already has zeros where RHSC does, this 'and' is dead. |
| if ((LHSKnown.Zero & DemandedBits) == |
| (~RHSC->getAPIntValue() & DemandedBits)) |
| return TLO.CombineTo(Op, Op0); |
| |
| // If any of the set bits in the RHS are known zero on the LHS, shrink |
| // the constant. |
| if (ShrinkDemandedConstant(Op, ~LHSKnown.Zero & DemandedBits, 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); |
| } |
| } |
| |
| if (SimplifyDemandedBits(Op1, DemandedBits, DemandedElts, Known, TLO, Depth + 1)) |
| return true; |
| assert(!Known.hasConflict() && "Bits known to be one AND zero?"); |
| if (SimplifyDemandedBits(Op0, ~Known.Zero & DemandedBits, DemandedElts, Known2, TLO, |
| Depth + 1)) |
| return true; |
| assert(!Known2.hasConflict() && "Bits known to be one AND zero?"); |
| |
| // If all of the demanded bits are known one on one side, return the other. |
| // These bits cannot contribute to the result of the 'and'. |
| if (DemandedBits.isSubsetOf(Known2.Zero | Known.One)) |
| return TLO.CombineTo(Op, Op0); |
| if (DemandedBits.isSubsetOf(Known.Zero | Known2.One)) |
| return TLO.CombineTo(Op, Op1); |
| // If all of the demanded bits in the inputs are known zeros, return zero. |
| if (DemandedBits.isSubsetOf(Known.Zero | Known2.Zero)) |
| return TLO.CombineTo(Op, TLO.DAG.getConstant(0, dl, VT)); |
| // If the RHS is a constant, see if we can simplify it. |
| if (ShrinkDemandedConstant(Op, ~Known2.Zero & DemandedBits, TLO)) |
| return true; |
| // If the operation can be done in a smaller type, do so. |
| if (ShrinkDemandedOp(Op, BitWidth, DemandedBits, TLO)) |
| return true; |
| |
| // Output known-1 bits are only known if set in both the LHS & RHS. |
| Known.One &= Known2.One; |
| // Output known-0 are known to be clear if zero in either the LHS | RHS. |
| Known.Zero |= Known2.Zero; |
| break; |
| } |
| case ISD::OR: { |
| SDValue Op0 = Op.getOperand(0); |
| SDValue Op1 = Op.getOperand(1); |
| |
| if (SimplifyDemandedBits(Op1, DemandedBits, DemandedElts, Known, TLO, Depth + 1)) |
| return true; |
| assert(!Known.hasConflict() && "Bits known to be one AND zero?"); |
| if (SimplifyDemandedBits(Op0, ~Known.One & DemandedBits, DemandedElts, Known2, TLO, |
| Depth + 1)) |
| return true; |
| assert(!Known2.hasConflict() && "Bits known to be one AND zero?"); |
| |
| // If all of the demanded bits are known zero on one side, return the other. |
| // These bits cannot contribute to the result of the 'or'. |
| if (DemandedBits.isSubsetOf(Known2.One | Known.Zero)) |
| return TLO.CombineTo(Op, Op0); |
| if (DemandedBits.isSubsetOf(Known.One | Known2.Zero)) |
| return TLO.CombineTo(Op, Op1); |
| // If the RHS is a constant, see if we can simplify it. |
| if (ShrinkDemandedConstant(Op, DemandedBits, TLO)) |
| return true; |
| // If the operation can be done in a smaller type, do so. |
| if (ShrinkDemandedOp(Op, BitWidth, DemandedBits, TLO)) |
| return true; |
| |
| // Output known-0 bits are only known if clear in both the LHS & RHS. |
| Known.Zero &= Known2.Zero; |
| // Output known-1 are known to be set if set in either the LHS | RHS. |
| Known.One |= Known2.One; |
| break; |
| } |
| case ISD::XOR: { |
| SDValue Op0 = Op.getOperand(0); |
| SDValue Op1 = Op.getOperand(1); |
| |
| if (SimplifyDemandedBits(Op1, DemandedBits, DemandedElts, Known, TLO, Depth + 1)) |
| return true; |
| assert(!Known.hasConflict() && "Bits known to be one AND zero?"); |
| if (SimplifyDemandedBits(Op0, DemandedBits, DemandedElts, Known2, TLO, Depth + 1)) |
| return true; |
| assert(!Known2.hasConflict() && "Bits known to be one AND zero?"); |
| |
| // If all of the demanded bits are known zero on one side, return the other. |
| // These bits cannot contribute to the result of the 'xor'. |
| if (DemandedBits.isSubsetOf(Known.Zero)) |
| return TLO.CombineTo(Op, Op0); |
| if (DemandedBits.isSubsetOf(Known2.Zero)) |
| return TLO.CombineTo(Op, Op1); |
| // If the operation can be done in a smaller type, do so. |
| if (ShrinkDemandedOp(Op, BitWidth, DemandedBits, TLO)) |
| return true; |
| |
| // If all of the unknown bits are known to be zero on one side or the other |
| // (but not both) 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)); |
| |
| // Output known-0 bits are known if clear or set in both the LHS & RHS. |
| KnownOut.Zero = (Known.Zero & Known2.Zero) | (Known.One & Known2.One); |
| // Output known-1 are known to be set if set in only one of the LHS, RHS. |
| KnownOut.One = (Known.Zero & Known2.One) | (Known.One & Known2.Zero); |
| |
| if (ConstantSDNode *C = isConstOrConstSplat(Op1)) { |
| // If one side is a constant, and all of the known set bits on the other |
| // side are also set in the constant, 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->isAllOnesValue()) { |
| if (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); |
| } |
| // If we can't turn this into a 'not', try to shrink the constant. |
| if (ShrinkDemandedConstant(Op, DemandedBits, TLO)) |
| return true; |
| } |
| } |
| |
| Known = std::move(KnownOut); |
| break; |
| } |
| case ISD::SELECT: |
| if (SimplifyDemandedBits(Op.getOperand(2), DemandedBits, Known, TLO, |
| Depth + 1)) |
| return true; |
| if (SimplifyDemandedBits(Op.getOperand(1), DemandedBits, Known2, TLO, |
| Depth + 1)) |
| return true; |
| assert(!Known.hasConflict() && "Bits known to be one AND zero?"); |
| assert(!Known2.hasConflict() && "Bits known to be one AND zero?"); |
| |
| // If the operands are constants, see if we can simplify them. |
| if (ShrinkDemandedConstant(Op, DemandedBits, TLO)) |
| return true; |
| |
| // Only known if known in both the LHS and RHS. |
| Known.One &= Known2.One; |
| Known.Zero &= Known2.Zero; |
| break; |
| case ISD::SELECT_CC: |
| if (SimplifyDemandedBits(Op.getOperand(3), DemandedBits, Known, TLO, |
| Depth + 1)) |
| return true; |
| if (SimplifyDemandedBits(Op.getOperand(2), DemandedBits, Known2, TLO, |
| Depth + 1)) |
| return true; |
| assert(!Known.hasConflict() && "Bits known to be one AND zero?"); |
| assert(!Known2.hasConflict() && "Bits known to be one AND zero?"); |
| |
| // If the operands are constants, see if we can simplify them. |
| if (ShrinkDemandedConstant(Op, DemandedBits, TLO)) |
| return true; |
| |
| // Only known if known in both the LHS and RHS. |
| Known.One &= Known2.One; |
| Known.Zero &= Known2.Zero; |
| 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(VT) == |
| 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); |
| |
| if (ConstantSDNode *SA = isConstOrConstSplat(Op1)) { |
| // If the shift count is an invalid immediate, don't do anything. |
| if (SA->getAPIntValue().uge(BitWidth)) |
| break; |
| |
| unsigned ShAmt = SA->getZExtValue(); |
| |
| // 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. |
| if (Op0.getOpcode() == ISD::SRL) { |
| if (ShAmt && |
| (DemandedBits & APInt::getLowBitsSet(BitWidth, ShAmt)) == 0) { |
| if (ConstantSDNode *SA2 = isConstOrConstSplat(Op0.getOperand(1))) { |
| if (SA2->getAPIntValue().ult(BitWidth)) { |
| unsigned C1 = SA2->getZExtValue(); |
| unsigned Opc = ISD::SHL; |
| int Diff = ShAmt - C1; |
| if (Diff < 0) { |
| Diff = -Diff; |
| Opc = ISD::SRL; |
| } |
| |
| SDValue NewSA = TLO.DAG.getConstant(Diff, dl, Op1.getValueType()); |
| return TLO.CombineTo( |
| Op, TLO.DAG.getNode(Opc, dl, VT, Op0.getOperand(0), NewSA)); |
| } |
| } |
| } |
| } |
| |
| if (SimplifyDemandedBits(Op0, DemandedBits.lshr(ShAmt), DemandedElts, Known, TLO, |
| Depth + 1)) |
| return true; |
| |
| // 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. |
| if (Op0.getOpcode() == ISD::ANY_EXTEND) { |
| SDValue InnerOp = Op0.getOperand(0); |
| EVT InnerVT = InnerOp.getValueType(); |
| unsigned InnerBits = InnerVT.getScalarSizeInBits(); |
| if (ShAmt < InnerBits && DemandedBits.getActiveBits() <= InnerBits && |
| isTypeDesirableForOp(ISD::SHL, InnerVT)) { |
| EVT ShTy = getShiftAmountTy(InnerVT, DL); |
| if (!APInt(BitWidth, ShAmt).isIntN(ShTy.getSizeInBits())) |
| ShTy = InnerVT; |
| SDValue NarrowShl = |
| TLO.DAG.getNode(ISD::SHL, dl, InnerVT, InnerOp, |
| TLO.DAG.getConstant(ShAmt, dl, ShTy)); |
| return TLO.CombineTo( |
| Op, TLO.DAG.getNode(ISD::ANY_EXTEND, dl, VT, NarrowShl)); |
| } |
| // Repeat the SHL optimization above in cases where an extension |
| // intervenes: (shl (anyext (shr x, c1)), c2) to |
| // (shl (anyext x), c2-c1). This requires that the bottom c1 bits |
| // aren't demanded (as above) and that the shifted upper c1 bits of |
| // x aren't demanded. |
| if (Op0.hasOneUse() && InnerOp.getOpcode() == ISD::SRL && |
| InnerOp.hasOneUse()) { |
| if (ConstantSDNode *SA2 = |
| isConstOrConstSplat(InnerOp.getOperand(1))) { |
| unsigned InnerShAmt = SA2->getLimitedValue(InnerBits); |
| if (InnerShAmt < ShAmt && InnerShAmt < InnerBits && |
| DemandedBits.getActiveBits() <= |
| (InnerBits - InnerShAmt + ShAmt) && |
| DemandedBits.countTrailingZeros() >= ShAmt) { |
| SDValue NewSA = TLO.DAG.getConstant(ShAmt - InnerShAmt, dl, |
| Op1.getValueType()); |
| 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)); |
| } |
| } |
| } |
| } |
| |
| Known.Zero <<= ShAmt; |
| Known.One <<= ShAmt; |
| // low bits known zero. |
| Known.Zero.setLowBits(ShAmt); |
| } |
| break; |
| } |
| case ISD::SRL: { |
| SDValue Op0 = Op.getOperand(0); |
| SDValue Op1 = Op.getOperand(1); |
| |
| if (ConstantSDNode *SA = isConstOrConstSplat(Op1)) { |
| // If the shift count is an invalid immediate, don't do anything. |
| if (SA->getAPIntValue().uge(BitWidth)) |
| break; |
| |
| unsigned ShAmt = SA->getZExtValue(); |
| 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 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. |
| if (Op0.getOpcode() == ISD::SHL) { |
| if (ConstantSDNode *SA2 = isConstOrConstSplat(Op0.getOperand(1))) { |
| if (ShAmt && |
| (DemandedBits & APInt::getHighBitsSet(BitWidth, ShAmt)) == 0) { |
| if (SA2->getAPIntValue().ult(BitWidth)) { |
| unsigned C1 = SA2->getZExtValue(); |
| unsigned Opc = ISD::SRL; |
| int Diff = ShAmt - C1; |
| if (Diff < 0) { |
| Diff = -Diff; |
| Opc = ISD::SHL; |
| } |
| |
| SDValue NewSA = TLO.DAG.getConstant(Diff, dl, Op1.getValueType()); |
| return TLO.CombineTo( |
| Op, TLO.DAG.getNode(Opc, dl, VT, Op0.getOperand(0), NewSA)); |
| } |
| } |
| } |
| } |
| |
| // Compute the new bits that are at the top now. |
| if (SimplifyDemandedBits(Op0, InDemandedMask, DemandedElts, Known, TLO, Depth + 1)) |
| return true; |
| assert(!Known.hasConflict() && "Bits known to be one AND zero?"); |
| Known.Zero.lshrInPlace(ShAmt); |
| Known.One.lshrInPlace(ShAmt); |
| |
| Known.Zero.setHighBits(ShAmt); // High bits known zero. |
| } |
| break; |
| } |
| case ISD::SRA: { |
| SDValue Op0 = Op.getOperand(0); |
| SDValue Op1 = Op.getOperand(1); |
| |
| // 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.isOneValue()) |
| return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SRL, dl, VT, Op0, Op1)); |
| |
| if (ConstantSDNode *SA = isConstOrConstSplat(Op1)) { |
| // If the shift count is an invalid immediate, don't do anything. |
| if (SA->getAPIntValue().uge(BitWidth)) |
| break; |
| |
| unsigned ShAmt = SA->getZExtValue(); |
| APInt InDemandedMask = (DemandedBits << ShAmt); |
| |
| // If the shift is exact, then it does demand the low bits (and knows that |
| // they are zero). |
| if (Op->getFlags().hasExact()) |
| InDemandedMask.setLowBits(ShAmt); |
| |
| // If any of the demanded bits are produced by the sign extension, we also |
| // demand the input sign bit. |
| if (DemandedBits.countLeadingZeros() < ShAmt) |
| InDemandedMask.setSignBit(); |
| |
| if (SimplifyDemandedBits(Op0, InDemandedMask, DemandedElts, Known, TLO, Depth + 1)) |
| return true; |
| assert(!Known.hasConflict() && "Bits known to be one AND zero?"); |
| Known.Zero.lshrInPlace(ShAmt); |
| Known.One.lshrInPlace(ShAmt); |
| |
| // If the input sign bit is known to be zero, or if none of the top bits |
| // are demanded, turn this into an unsigned shift right. |
| if (Known.Zero[BitWidth - ShAmt - 1] || |
| DemandedBits.countLeadingZeros() >= ShAmt) { |
| SDNodeFlags Flags; |
| Flags.setExact(Op->getFlags().hasExact()); |
| return TLO.CombineTo( |
| Op, TLO.DAG.getNode(ISD::SRL, dl, VT, Op0, Op1, Flags)); |
| } |
| |
| int Log2 = DemandedBits.exactLogBase2(); |
| if (Log2 >= 0) { |
| // The bit must come from the sign. |
| SDValue NewSA = |
| TLO.DAG.getConstant(BitWidth - 1 - Log2, dl, Op1.getValueType()); |
| 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); |
| } |
| 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)) { |
| unsigned Amt = SA->getAPIntValue().urem(BitWidth); |
| |
| // For fshl, 0-shift returns the 1st arg. |
| // For fshr, 0-shift returns the 2nd arg. |
| if (Amt == 0) { |
| if (SimplifyDemandedBits(IsFSHL ? Op0 : Op1, DemandedBits, DemandedElts, |
| Known, TLO, Depth + 1)) |
| return true; |
| break; |
| } |
| |
| // fshl: (Op0 << Amt) | (Op1 >> (BW - Amt)) |
| // fshr: (Op0 << (BW - Amt)) | (Op1 >> Amt) |
| APInt Demanded0 = DemandedBits.lshr(IsFSHL ? Amt : (BitWidth - Amt)); |
| APInt Demanded1 = DemandedBits << (IsFSHL ? (BitWidth - Amt) : Amt); |
| if (SimplifyDemandedBits(Op0, Demanded0, DemandedElts, Known2, TLO, |
| Depth + 1)) |
| return true; |
| if (SimplifyDemandedBits(Op1, Demanded1, DemandedElts, Known, TLO, |
| Depth + 1)) |
| return true; |
| |
| Known2.One <<= (IsFSHL ? Amt : (BitWidth - Amt)); |
| Known2.Zero <<= (IsFSHL ? Amt : (BitWidth - Amt)); |
| Known.One.lshrInPlace(IsFSHL ? (BitWidth - Amt) : Amt); |
| Known.Zero.lshrInPlace(IsFSHL ? (BitWidth - Amt) : Amt); |
| Known.One |= Known2.One; |
| Known.Zero |= Known2.Zero; |
| } |
| 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()) { |
| bool AlreadySignExtended = |
| TLO.DAG.ComputeNumSignBits(Op0) >= BitWidth - ExVTBits + 1; |
| // 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. |
| EVT ShiftAmtTy = VT; |
| if (TLO.LegalTypes() && !ShiftAmtTy.isVector()) |
| ShiftAmtTy = getShiftAmountTy(ShiftAmtTy, DL); |
| |
| SDValue ShiftAmt = |
| TLO.DAG.getConstant(BitWidth - ExVTBits, dl, ShiftAmtTy); |
| 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, Known, TLO, Depth + 1)) |
| return true; |
| assert(!Known.hasConflict() && "Bits known to be one AND zero?"); |
| |
| // If the sign bit of the input is known set or clear, then we know the |
| // top bits of the result. |
| |
| // If the input sign bit is known zero, convert this into a zero extension. |
| if (Known.Zero[ExVTBits - 1]) |
| return TLO.CombineTo( |
| Op, TLO.DAG.getZeroExtendInReg(Op0, dl, ExVT.getScalarType())); |
| |
| 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.Zero = KnownLo.Zero.zext(BitWidth) | |
| KnownHi.Zero.zext(BitWidth).shl(HalfBitWidth); |
| |
| Known.One = KnownLo.One.zext(BitWidth) | |
| KnownHi.One.zext(BitWidth).shl(HalfBitWidth); |
| break; |
| } |
| case ISD::ZERO_EXTEND: { |
| SDValue Src = Op.getOperand(0); |
| unsigned InBits = Src.getScalarValueSizeInBits(); |
| |
| // If none of the top bits are demanded, convert this into an any_extend. |
| if (DemandedBits.getActiveBits() <= InBits) |
| return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ANY_EXTEND, dl, VT, Src)); |
| |
| APInt InDemandedBits = DemandedBits.trunc(InBits); |
| if (SimplifyDemandedBits(Src, InDemandedBits, Known, TLO, Depth+1)) |
| return true; |
| assert(!Known.hasConflict() && "Bits known to be one AND zero?"); |
| Known = Known.zext(BitWidth); |
| Known.Zero.setBitsFrom(InBits); |
| break; |
| } |
| case ISD::SIGN_EXTEND: { |
| SDValue Src = Op.getOperand(0); |
| unsigned InBits = Src.getScalarValueSizeInBits(); |
| |
| // If none of the top bits are demanded, convert this into an any_extend. |
| if (DemandedBits.getActiveBits() <= InBits) |
| return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ANY_EXTEND, dl, VT, Src)); |
| |
| // Since some of the sign extended bits are demanded, we know that the sign |
| // bit is demanded. |
| APInt InDemandedBits = DemandedBits.trunc(InBits); |
| InDemandedBits.setBit(InBits - 1); |
| |
| if (SimplifyDemandedBits(Src, InDemandedBits, Known, TLO, Depth + 1)) |
| return true; |
| assert(!Known.hasConflict() && "Bits known to be one AND zero?"); |
| // 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()) |
| return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Src)); |
| break; |
| } |
| case ISD::SIGN_EXTEND_VECTOR_INREG: { |
| // TODO - merge this with SIGN_EXTEND above? |
| SDValue Src = Op.getOperand(0); |
| unsigned InBits = Src.getScalarValueSizeInBits(); |
| |
| APInt InDemandedBits = DemandedBits.trunc(InBits); |
| |
| // If some of the sign extended bits are demanded, we know that the sign |
| // bit is demanded. |
| if (InBits < DemandedBits.getActiveBits()) |
| InDemandedBits.setBit(InBits - 1); |
| |
| if (SimplifyDemandedBits(Src, InDemandedBits, Known, TLO, Depth + 1)) |
| return true; |
| assert(!Known.hasConflict() && "Bits known to be one AND zero?"); |
| // If the sign bit is known one, the top bits match. |
| Known = Known.sext(BitWidth); |
| break; |
| } |
| case ISD::ANY_EXTEND: { |
| SDValue Src = Op.getOperand(0); |
| unsigned InBits = Src.getScalarValueSizeInBits(); |
| APInt InDemandedBits = DemandedBits.trunc(InBits); |
| if (SimplifyDemandedBits(Src, InDemandedBits, Known, TLO, Depth+1)) |
| return true; |
| assert(!Known.hasConflict() && "Bits known to be one AND zero?"); |
| Known = Known.zext(BitWidth); |
| 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, Known, TLO, Depth + 1)) |
| return true; |
| Known = Known.trunc(BitWidth); |
| |
| // If the input is only used by this truncate, see if we can shrink it based |
| // on the known demanded bits. |
| if (Src.getNode()->hasOneUse()) { |
| 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; |
| ConstantSDNode *ShAmt = dyn_cast<ConstantSDNode>(Src.getOperand(1)); |
| if (!ShAmt) |
| break; |
| SDValue Shift = Src.getOperand(1); |
| if (TLO.LegalTypes()) { |
| uint64_t ShVal = ShAmt->getZExtValue(); |
| Shift = TLO.DAG.getConstant(ShVal, dl, getShiftAmountTy(VT, DL)); |
| } |
| |
| if (ShAmt->getZExtValue() < BitWidth) { |
| APInt HighBits = APInt::getHighBitsSet(OperandBitWidth, |
| OperandBitWidth - BitWidth); |
| HighBits.lshrInPlace(ShAmt->getZExtValue()); |
| 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 NewTrunc = |
| TLO.DAG.getNode(ISD::TRUNCATE, dl, VT, Src.getOperand(0)); |
| return TLO.CombineTo( |
| Op, TLO.DAG.getNode(ISD::SRL, dl, VT, NewTrunc, Shift)); |
| } |
| } |
| break; |
| } |
| } |
| |
| assert(!Known.hasConflict() && "Bits known to be one AND zero?"); |
| break; |
| } |
| case ISD::AssertZext: { |
| // AssertZext demands all of the high bits, plus any of the low bits |
| // demanded by its users. |
| EVT ZVT = cast<VTSDNode>(Op.getOperand(1))->getVT(); |
| APInt InMask = APInt::getLowBitsSet(BitWidth, ZVT.getSizeInBits()); |
| if (SimplifyDemandedBits(Op.getOperand(0), ~InMask | DemandedBits, |
| Known, TLO, Depth+1)) |
| return true; |
| assert(!Known.hasConflict() && "Bits known to be one AND zero?"); |
| |
| Known.Zero |= ~InMask; |
| break; |
| } |
| case ISD::EXTRACT_VECTOR_ELT: { |
| SDValue Src = Op.getOperand(0); |
| SDValue Idx = Op.getOperand(1); |
| unsigned NumSrcElts = Src.getValueType().getVectorNumElements(); |
| unsigned EltBitWidth = Src.getScalarValueSizeInBits(); |
| |
| // Demand the bits from every vector element without a constant index. |
| APInt DemandedSrcElts = APInt::getAllOnesValue(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; |
| |
| Known = Known2; |
| if (BitWidth > EltBitWidth) |
| Known = Known.zext(BitWidth); |
| break; |
| } |
| case ISD::BITCAST: { |
| SDValue Src = Op.getOperand(0); |
| EVT SrcVT = Src.getValueType(); |
| unsigned NumSrcEltBits = SrcVT.getScalarSizeInBits(); |
| |
| // If this is an FP->Int bitcast and if the sign bit is the only |
| // thing demanded, turn this into a FGETSIGN. |
| if (!TLO.LegalOperations() && !VT.isVector() && !SrcVT.isVector() && |
| DemandedBits == APInt::getSignMask(Op.getValueSizeInBits()) && |
| SrcVT.isFloatingPoint()) { |
| bool OpVTLegal = isOperationLegalOrCustom(ISD::FGETSIGN, VT); |
| bool i32Legal = isOperationLegalOrCustom(ISD::FGETSIGN, MVT::i32); |
| if ((OpVTLegal || i32Legal) && VT.isSimple() && SrcVT != MVT::f16 && |
| SrcVT != MVT::f128) { |
| // Cannot eliminate/lower SHL for f128 yet. |
| EVT Ty = OpVTLegal ? VT : MVT::i32; |
| // Make a FGETSIGN + SHL to move the sign bit into the appropriate |
| // place. We expect the SHL to be eliminated by other optimizations. |
| SDValue Sign = TLO.DAG.getNode(ISD::FGETSIGN, dl, Ty, Src); |
| unsigned OpVTSizeInBits = Op.getValueSizeInBits(); |
| if (!OpVTLegal && OpVTSizeInBits > 32) |
| Sign = TLO.DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Sign); |
| unsigned ShVal = Op.getValueSizeInBits() - 1; |
| SDValue ShAmt = TLO.DAG.getConstant(ShVal, dl, VT); |
| return TLO.CombineTo(Op, |
| TLO.DAG.getNode(ISD::SHL, dl, VT, Sign, ShAmt)); |
| } |
| } |
| // If bitcast from a vector, see if we can use SimplifyDemandedVectorElts by |
| // demanding the element if any bits from it are demanded. |
| // TODO - bigendian once we have test coverage. |
| // TODO - bool vectors once SimplifyDemandedVectorElts has SETCC support. |
| if (SrcVT.isVector() && NumSrcEltBits > 1 && |
| (BitWidth % NumSrcEltBits) == 0 && |
| TLO.DAG.getDataLayout().isLittleEndian()) { |
| unsigned Scale = BitWidth / NumSrcEltBits; |
| auto GetDemandedSubMask = [&](APInt &DemandedSubElts) -> bool { |
| DemandedSubElts = APInt::getNullValue(Scale); |
| for (unsigned i = 0; i != Scale; ++i) { |
| unsigned Offset = i * NumSrcEltBits; |
| APInt Sub = DemandedBits.extractBits(NumSrcEltBits, Offset); |
| if (!Sub.isNullValue()) |
| DemandedSubElts.setBit(i); |
| } |
| return true; |
| }; |
| |
| APInt DemandedSubElts; |
| if (GetDemandedSubMask(DemandedSubElts)) { |
| unsigned NumSrcElts = SrcVT.getVectorNumElements(); |
| APInt DemandedElts = APInt::getSplat(NumSrcElts, DemandedSubElts); |
| |
| APInt KnownUndef, KnownZero; |
| if (SimplifyDemandedVectorElts(Src, DemandedElts, KnownUndef, KnownZero, |
| TLO, Depth + 1)) |
| return true; |
| } |
| } |
| // If this is a bitcast, let computeKnownBits handle it. Only do this on a |
| // recursive call where Known may be useful to the caller. |
| if (Depth > 0) { |
| Known = TLO.DAG.computeKnownBits(Op, Depth); |
| return false; |
| } |
| break; |
| } |
| case ISD::ADD: |
| case ISD::MUL: |
| 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); |
| unsigned DemandedBitsLZ = DemandedBits.countLeadingZeros(); |
| APInt LoMask = APInt::getLowBitsSet(BitWidth, BitWidth - DemandedBitsLZ); |
| if (SimplifyDemandedBits(Op0, LoMask, DemandedElts, Known2, TLO, Depth + 1) || |
| SimplifyDemandedBits(Op1, LoMask, DemandedElts, Known2, TLO, Depth + 1) || |
| // See if the operation should be performed at a smaller bit width. |
| ShrinkDemandedOp(Op, BitWidth, DemandedBits, TLO)) { |
| 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); |
| SDValue NewOp = TLO.DAG.getNode(Op.getOpcode(), dl, VT, Op0, Op1, |
| Flags); |
| return TLO.CombineTo(Op, NewOp); |
| } |
| return true; |
| } |
| |
| // 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->isAllOnesValue() && !C->isOne() && |
| (C->getAPIntValue() | HighMask).isAllOnesValue()) { |
| SDValue Neg1 = TLO.DAG.getAllOnesConstant(dl, VT); |
| // We can't guarantee that the new math op doesn't wrap, so explicitly |
| // clear those flags to prevent folding with a potential existing node |
| // that has those flags set. |
| SDNodeFlags Flags; |
| Flags.setNoSignedWrap(false); |
| Flags.setNoUnsignedWrap(false); |
| SDValue NewOp = TLO.DAG.getNode(Op.getOpcode(), dl, VT, Op0, Neg1, Flags); |
| return TLO.CombineTo(Op, NewOp); |
| } |
| |
| LLVM_FALLTHROUGH; |
| } |
| default: |
| if (Op.getOpcode() >= ISD::BUILTIN_OP_END) { |
| if (SimplifyDemandedBitsForTargetNode(Op, DemandedBits, DemandedElts, |
| Known, TLO, Depth)) |
| return true; |
| break; |
| } |
| |
| // Just use computeKnownBits to compute output bits. |
| Known = TLO.DAG.computeKnownBits(Op, DemandedElts, Depth); |
| break; |
| } |
| |
| // If we know the value of all of the demanded bits, return this as a |
| // constant. |
| if (DemandedBits.isSubsetOf(Known.Zero | Known.One)) { |
| // Avoid folding to a constant if any OpaqueConstant is involved. |
| const SDNode *N = Op.getNode(); |
| for (SDNodeIterator I = SDNodeIterator::begin(N), |
| E = SDNodeIterator::end(N); |
| I != E; ++I) { |
| SDNode *Op = *I; |
| if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op)) |
| if (C->isOpaque()) |
| return false; |
| } |
| // TODO: Handle float bits as well. |
| if (VT.isInteger()) |
| return TLO.CombineTo(Op, TLO.DAG.getConstant(Known.One, dl, VT)); |
| } |
| |
| return false; |
| } |
| |
| bool TargetLowering::SimplifyDemandedVectorElts(SDValue Op, |
| const APInt &DemandedElts, |
| APInt &KnownUndef, |
| APInt &KnownZero, |
| DAGCombinerInfo &DCI) const { |
| SelectionDAG &DAG = DCI.DAG; |
| TargetLoweringOpt TLO(DAG, !DCI.isBeforeLegalize(), |
| !DCI.isBeforeLegalizeOps()); |
| |
| 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(ISD::isBinaryOp(BO.getNode()) && VT.isVector() && "Vector binop only"); |
| |
| EVT EltVT = VT.getVectorElementType(); |
| unsigned NumElts = VT.getVectorNumElements(); |
| assert(UndefOp0.getBitWidth() == NumElts && |
| UndefOp1.getBitWidth() == NumElts && "Bad type for undef analysis"); |
| |
| auto getUndefOrConstantElt = [&](SDValue V, unsigned Index, |
| const APInt &UndefVals) { |
| if (UndefVals[Index]) |
| return DAG.getUNDEF(EltVT); |
| |
| if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) { |
| // Try hard to make sure that the getNode() call is not creating temporary |
| // nodes. Ignore opaque integers because they do not constant fold. |
| SDValue Elt = BV->getOperand(Index); |
| auto *C = dyn_cast<ConstantSDNode>(Elt); |
| if (isa<ConstantFPSDNode>(Elt) || Elt.isUndef() || (C && !C->isOpaque())) |
| return Elt; |
| } |
| |
| return SDValue(); |
| }; |
| |
| APInt KnownUndef = APInt::getNullValue(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 &DemandedEltMask, APInt &KnownUndef, |
| APInt &KnownZero, TargetLoweringOpt &TLO, unsigned Depth, |
| bool AssumeSingleUse) const { |
| EVT VT = Op.getValueType(); |
| APInt DemandedElts = DemandedEltMask; |
| unsigned NumElts = DemandedElts.getBitWidth(); |
| assert(VT.isVector() && "Expected vector op"); |
| assert(VT.getVectorNumElements() == NumElts && |
| "Mask size mismatches value type element count!"); |
| |
| KnownUndef = KnownZero = APInt::getNullValue(NumElts); |
| |
| // Undef operand. |
| if (Op.isUndef()) { |
| KnownUndef.setAllBits(); |
| return false; |
| } |
| |
| // If Op has other users, assume that all elements are needed. |
| if (!Op.getNode()->hasOneUse() && !AssumeSingleUse) |
| 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 >= 6) |
| return false; |
| |
| SDLoc DL(Op); |
| unsigned EltSizeInBits = VT.getScalarSizeInBits(); |
| |
| switch (Op.getOpcode()) { |
| case ISD::SCALAR_TO_VECTOR: { |
| if (!DemandedElts[0]) { |
| KnownUndef.setAllBits(); |
| return TLO.CombineTo(Op, TLO.DAG.getUNDEF(VT)); |
| } |
| 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 SrcZero, SrcUndef; |
| APInt SrcDemandedElts = APInt::getNullValue(NumSrcElts); |
| |
| // 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; |
| for (unsigned i = 0; i != NumElts; ++i) |
| if (DemandedElts[i]) |
| SrcDemandedElts.setBit(i / Scale); |
| |
| 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 (TLO.DAG.getDataLayout().isLittleEndian()) { |
| unsigned SrcEltSizeInBits = SrcVT.getScalarSizeInBits(); |
| APInt SrcDemandedBits = APInt::getNullValue(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, Known, TLO, Depth + 1)) |
| return true; |
| } |
| |
| // 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; |
| for (unsigned i = 0; i != NumElts; ++i) |
| if (DemandedElts[i]) |
| SrcDemandedElts.setBits(i * Scale, (i + 1) * Scale); |
| |
| 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).isAllOnesValue()) |
| KnownZero.setBit(i); |
| if (SrcUndef.extractBits(Scale, i * Scale).isAllOnesValue()) |
| KnownUndef.setBit(i); |
| } |
| } |
| } |
| break; |
| } |
| case ISD::BUILD_VECTOR: { |
| // Check all elements and simplify any unused elements with UNDEF. |
| if (!DemandedElts.isAllOnesValue()) { |
| // Don't simplify BROADCASTS. |
| if (llvm::any_of(Op->op_values(), |
| [&](SDValue Elt) { return Op.getOperand(0) != Elt; })) { |
| SmallVector<SDValue, 32> Ops(Op->op_begin(), Op->op_end()); |
| bool Updated = false; |
| for (unsigned i = 0; i != NumElts; ++i) { |
| if (!DemandedElts[i] && !Ops[i].isUndef()) { |
| Ops[i] = TLO.DAG.getUNDEF(Ops[0].getValueType()); |
| KnownUndef.setBit(i); |
| Updated = true; |
| } |
| } |
| if (Updated) |
| return TLO.CombineTo(Op, TLO.DAG.getBuildVector(VT, DL, Ops)); |
| } |
| } |
| for (unsigned i = 0; i != NumElts; ++i) { |
| SDValue SrcOp = Op.getOperand(i); |
| if (SrcOp.isUndef()) { |
| KnownUndef.setBit(i); |
| } else if (EltSizeInBits == SrcOp.getScalarValueSizeInBits() && |
| (isNullConstant(SrcOp) || isNullFPConstant(SrcOp))) { |
| KnownZero.setBit(i); |
| } |
| } |
| break; |
| } |
| case ISD::CONCAT_VECTORS: { |
| EVT SubVT = Op.getOperand(0).getValueType(); |
| unsigned NumSubVecs = Op.getNumOperands(); |
| unsigned NumSubElts = SubVT.getVectorNumElements(); |
| for (unsigned i = 0; i != NumSubVecs; ++i) { |
| SDValue SubOp = Op.getOperand(i); |
| APInt SubElts = DemandedElts.extractBits(NumSubElts, i * NumSubElts); |
| APInt SubUndef, SubZero; |
| if (SimplifyDemandedVectorElts(SubOp, SubElts, SubUndef, SubZero, TLO, |
| Depth + 1)) |
| return true; |
| KnownUndef.insertBits(SubUndef, i * NumSubElts); |
| KnownZero.insertBits(SubZero, i * NumSubElts); |
| } |
| break; |
| } |
| case ISD::INSERT_SUBVECTOR: { |
| if (!isa<ConstantSDNode>(Op.getOperand(2))) |
| break; |
| SDValue Base = Op.getOperand(0); |
| SDValue Sub = Op.getOperand(1); |
| EVT SubVT = Sub.getValueType(); |
| unsigned NumSubElts = SubVT.getVectorNumElements(); |
| const APInt& Idx = cast<ConstantSDNode>(Op.getOperand(2))->getAPIntValue(); |
| if (Idx.ugt(NumElts - NumSubElts)) |
| break; |
| unsigned SubIdx = Idx.getZExtValue(); |
| APInt SubElts = DemandedElts.extractBits(NumSubElts, SubIdx); |
| APInt SubUndef, SubZero; |
| if (SimplifyDemandedVectorElts(Sub, SubElts, SubUndef, SubZero, TLO, |
| Depth + 1)) |
| return true; |
| APInt BaseElts = DemandedElts; |
| BaseElts.insertBits(APInt::getNullValue(NumSubElts), SubIdx); |
| if (SimplifyDemandedVectorElts(Base, BaseElts, KnownUndef, KnownZero, TLO, |
| Depth + 1)) |
| return true; |
| KnownUndef.insertBits(SubUndef, SubIdx); |
| KnownZero.insertBits(SubZero, SubIdx); |
| break; |
| } |
| case ISD::EXTRACT_SUBVECTOR: { |
| SDValue Src = Op.getOperand(0); |
| ConstantSDNode *SubIdx = dyn_cast<ConstantSDNode>(Op.getOperand(1)); |
| unsigned NumSrcElts = Src.getValueType().getVectorNumElements(); |
| if (SubIdx && SubIdx->getAPIntValue().ule(NumSrcElts - NumElts)) { |
| // Offset the demanded elts by the subvector index. |
| uint64_t Idx = SubIdx->getZExtValue(); |
| APInt SrcElts = DemandedElts.zextOrSelf(NumSrcElts).shl(Idx); |
| APInt SrcUndef, SrcZero; |
| if (SimplifyDemandedVectorElts(Src, SrcElts, SrcUndef, SrcZero, TLO, |
| Depth + 1)) |
| return true; |
| KnownUndef = SrcUndef.extractBits(NumElts, Idx); |
| KnownZero = SrcZero.extractBits(NumElts, Idx); |
| } |
| 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.clearBit(Idx); |
| if (Scl.isUndef()) |
| KnownUndef.setBit(Idx); |
| |
| KnownZero.clearBit(Idx); |
| if (isNullConstant(Scl) || isNullFPConstant(Scl)) |
| KnownZero.setBit(Idx); |
| 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: { |
| // Try to transform the select condition based on the current demanded |
| // elements. |
| // TODO: If a condition element is undef, we can choose from one arm of the |
| // select (and if one arm is undef, then we can propagate that to the |
| // result). |
| // TODO - add support for constant vselect masks (see IR version of this). |
| APInt UnusedUndef, UnusedZero; |
| if (SimplifyDemandedVectorElts(Op.getOperand(0), DemandedElts, UnusedUndef, |
| UnusedZero, 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(Op.getOperand(1), DemandedLHS, UndefLHS, |
| ZeroLHS, TLO, Depth + 1)) |
| return true; |
| if (SimplifyDemandedVectorElts(Op.getOperand(2), DemandedRHS, UndefRHS, |
| ZeroRHS, TLO, Depth + 1)) |
| return true; |
| |
| KnownUndef = UndefLHS & UndefRHS; |
| KnownZero = ZeroLHS & ZeroRHS; |
| break; |
| } |
| case ISD::VECTOR_SHUFFLE: { |
| ArrayRef<int> ShuffleMask = cast<ShuffleVectorSDNode>(Op)->getMask(); |
| |
| // Collect demanded elements from shuffle operands.. |
| APInt DemandedLHS(NumElts, 0); |
| APInt DemandedRHS(NumElts, 0); |
| for (unsigned i = 0; i != NumElts; ++i) { |
| 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(Op.getOperand(0), DemandedLHS, UndefLHS, |
| ZeroLHS, TLO, Depth + 1)) |
| return true; |
| if (SimplifyDemandedVectorElts(Op.getOperand(1), 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.begin(), ShuffleMask.end()); |
| 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 && |
| isShuffleMaskLegal(NewMask, VT)) |
| return TLO.CombineTo(Op, |
| TLO.DAG.getVectorShuffle(VT, DL, Op.getOperand(0), |
| Op.getOperand(1), NewMask)); |
| |
| // 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::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.zextOrSelf(NumSrcElts); |
| if (SimplifyDemandedVectorElts(Src, DemandedSrcElts, SrcUndef, |
| SrcZero, TLO, Depth + 1)) |
| return true; |
| KnownZero = SrcZero.zextOrTrunc(NumElts); |
| KnownUndef = SrcUndef.zextOrTrunc(NumElts); |
| |
| 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(); |
| } |
| break; |
| } |
| |
| // TODO: There are more binop opcodes that could be handled here - MUL, MIN, |
| // MAX, saturated math, etc. |
| case ISD::OR: |
| case ISD::XOR: |
| case ISD::ADD: |
| case ISD::SUB: |
| case ISD::FADD: |
| case ISD::FSUB: |
| case ISD::FMUL: |
| case ISD::FDIV: |
| case ISD::FREM: { |
| APInt UndefRHS, ZeroRHS; |
| if (SimplifyDemandedVectorElts(Op.getOperand(1), DemandedElts, UndefRHS, |
| ZeroRHS, TLO, Depth + 1)) |
| return true; |
| APInt UndefLHS, ZeroLHS; |
| if (SimplifyDemandedVectorElts(Op.getOperand(0), DemandedElts, UndefLHS, |
| ZeroLHS, TLO, Depth + 1)) |
| return true; |
| |
| KnownZero = ZeroLHS & ZeroRHS; |
| KnownUndef = getKnownUndefForVectorBinop(Op, TLO.DAG, UndefLHS, UndefRHS); |
| break; |
| } |
| case ISD::AND: { |
| APInt SrcUndef, SrcZero; |
| if (SimplifyDemandedVectorElts(Op.getOperand(1), DemandedElts, SrcUndef, |
| SrcZero, TLO, Depth + 1)) |
| return true; |
| if (SimplifyDemandedVectorElts(Op.getOperand(0), DemandedElts, KnownUndef, |
| KnownZero, TLO, Depth + 1)) |
| return true; |
| |
| // 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; |
| 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::getAllOnesValue(EltSizeInBits); |
| if (SimplifyDemandedBits(Op, DemandedBits, DemandedEltMask, 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::computeKnownBitsForFrameIndex(const SDValue Op, |
| KnownBits &Known, |
| const APInt &DemandedElts, |
| const SelectionDAG &DAG, |
| unsigned Depth) const { |
| assert(isa<FrameIndexSDNode>(Op) && "expected FrameIndex"); |
| |
| if (unsigned Align = DAG.InferPtrAlignment(Op)) { |
| // The low bits are known zero if the pointer is aligned. |
| Known.Zero.setLowBits(Log2_32(Align)); |
| } |
| } |
| |
| /// 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; |
| } |
| |
| 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; |
| } |
| |
| 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; |
| } |
| |
| // 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(const SDNode *N) const { |
| if (!N) |
| return false; |
| |
| APInt CVal; |
| if (auto *CN = dyn_cast<ConstantSDNode>(N)) { |
| CVal = CN->getAPIntValue(); |
| } else if (auto *BV = dyn_cast<BuildVectorSDNode>(N)) { |
| auto *CN = BV->getConstantSplatNode(); |
| if (!CN) |
| return false; |
| |
| // If this is a truncating build vector, truncate the splat value. |
| // Otherwise, we may fail to match the expected values below. |
| unsigned BVEltWidth = BV->getValueType(0).getScalarSizeInBits(); |
| CVal = CN->getAPIntValue(); |
| if (BVEltWidth < CVal.getBitWidth()) |
| CVal = CVal.trunc(BVEltWidth); |
| } else { |
| return false; |
| } |
| |
| switch (getBooleanContents(N->getValueType(0))) { |
| case UndefinedBooleanContent: |
| return CVal[0]; |
| case ZeroOrOneBooleanContent: |
| return CVal.isOneValue(); |
| case ZeroOrNegativeOneBooleanContent: |
| return CVal.isAllOnesValue(); |
| } |
| |
| llvm_unreachable("Invalid boolean contents"); |
| } |
| |
| bool TargetLowering::isConstFalseVal(const SDNode *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->isNullValue(); |
| } |
| |
| 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->isAllOnesValue() && 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 { |
| // Match these patterns in any of their permutations: |
| // (X & Y) == Y |
| // (X & Y) != Y |
| if (N1.getOpcode() == ISD::AND && N0.getOpcode() != ISD::AND) |
| std::swap(N0, N1); |
| |
| EVT OpVT = N0.getValueType(); |
| if (N0.getOpcode() != ISD::AND || !OpVT.isInteger() || |
| (Cond != ISD::SETEQ && Cond != ISD::SETNE)) |
| return SDValue(); |
| |
| 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(); |
| } |
| |
| SelectionDAG &DAG = DCI.DAG; |
| SDValue Zero = DAG.getConstant(0, DL, OpVT); |
| if (DAG.isKnownToBeAPowerOfTwo(Y)) { |
| // Simplify X & Y == Y to X & Y != 0 if Y has exactly one bit set. |
| // Note that where Y is variable and is known to have at most one bit set |
| // (for example, if it is Z & 1) we cannot do this; the expressions are not |
| // equivalent when Y == 0. |
| Cond = ISD::getSetCCInverse(Cond, /*isInteger=*/true); |
| if (DCI.isBeforeLegalizeOps() || |
| isCondCodeLegal(Cond, N0.getSimpleValueType())) |
| return DAG.getSetCC(DL, VT, N0, Zero, Cond); |
| } else if (N0.hasOneUse() && hasAndNotCompare(Y)) { |
| // If the target supports an 'and-not' or 'and-complement' logic operation, |
| // try to use that to make a comparison operation more efficient. |
| // But don't do this transform if the mask is a single bit because there are |
| // more efficient ways to deal with that case (for example, 'bt' on x86 or |
| // 'rlwinm' on PPC). |
| |
| // Bail out if the compare operand that we want to turn into a zero is |
| // already a zero (otherwise, infinite loop). |
| auto *YConst = dyn_cast<ConstantSDNode>(Y); |
| if (YConst && YConst->isNullValue()) |
| 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(); |
| NewCond = getSetCCInverse(NewCond, /*isInteger=*/true); |
| 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"); |
| |
|