diff options
Diffstat (limited to 'llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp')
| -rw-r--r-- | llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp | 1486 |
1 files changed, 1090 insertions, 396 deletions
diff --git a/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp b/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp index 615bea2a4905..b104e995019f 100644 --- a/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp +++ b/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp @@ -461,8 +461,7 @@ namespace { SDValue visitAssertExt(SDNode *N); SDValue visitAssertAlign(SDNode *N); SDValue visitSIGN_EXTEND_INREG(SDNode *N); - SDValue visitSIGN_EXTEND_VECTOR_INREG(SDNode *N); - SDValue visitZERO_EXTEND_VECTOR_INREG(SDNode *N); + SDValue visitEXTEND_VECTOR_INREG(SDNode *N); SDValue visitTRUNCATE(SDNode *N); SDValue visitBITCAST(SDNode *N); SDValue visitFREEZE(SDNode *N); @@ -547,8 +546,11 @@ namespace { SDValue foldSignChangeInBitcast(SDNode *N); SDValue foldSelectCCToShiftAnd(const SDLoc &DL, SDValue N0, SDValue N1, SDValue N2, SDValue N3, ISD::CondCode CC); + SDValue foldSelectOfBinops(SDNode *N); + SDValue foldSextSetcc(SDNode *N); SDValue foldLogicOfSetCCs(bool IsAnd, SDValue N0, SDValue N1, const SDLoc &DL); + SDValue foldSubToUSubSat(EVT DstVT, SDNode *N); SDValue unfoldMaskedMerge(SDNode *N); SDValue unfoldExtremeBitClearingToShifts(SDNode *N); SDValue SimplifySetCC(EVT VT, SDValue N0, SDValue N1, ISD::CondCode Cond, @@ -1673,8 +1675,8 @@ SDValue DAGCombiner::visit(SDNode *N) { case ISD::AssertZext: return visitAssertExt(N); case ISD::AssertAlign: return visitAssertAlign(N); case ISD::SIGN_EXTEND_INREG: return visitSIGN_EXTEND_INREG(N); - case ISD::SIGN_EXTEND_VECTOR_INREG: return visitSIGN_EXTEND_VECTOR_INREG(N); - case ISD::ZERO_EXTEND_VECTOR_INREG: return visitZERO_EXTEND_VECTOR_INREG(N); + case ISD::SIGN_EXTEND_VECTOR_INREG: + case ISD::ZERO_EXTEND_VECTOR_INREG: return visitEXTEND_VECTOR_INREG(N); case ISD::TRUNCATE: return visitTRUNCATE(N); case ISD::BITCAST: return visitBITCAST(N); case ISD::BUILD_PAIR: return visitBUILD_PAIR(N); @@ -2259,9 +2261,9 @@ SDValue DAGCombiner::visitADDLike(SDNode *N) { return FoldedVOp; // fold (add x, 0) -> x, vector edition - if (ISD::isBuildVectorAllZeros(N1.getNode())) + if (ISD::isConstantSplatVectorAllZeros(N1.getNode())) return N0; - if (ISD::isBuildVectorAllZeros(N0.getNode())) + if (ISD::isConstantSplatVectorAllZeros(N0.getNode())) return N1; } @@ -2337,6 +2339,23 @@ SDValue DAGCombiner::visitADDLike(SDNode *N) { if (!reassociationCanBreakAddressingModePattern(ISD::ADD, DL, N0, N1)) { if (SDValue RADD = reassociateOps(ISD::ADD, DL, N0, N1, N->getFlags())) return RADD; + + // Reassociate (add (or x, c), y) -> (add add(x, y), c)) if (or x, c) is + // equivalent to (add x, c). + auto ReassociateAddOr = [&](SDValue N0, SDValue N1) { + if (N0.getOpcode() == ISD::OR && N0.hasOneUse() && + isConstantOrConstantVector(N0.getOperand(1), /* NoOpaque */ true) && + DAG.haveNoCommonBitsSet(N0.getOperand(0), N0.getOperand(1))) { + return DAG.getNode(ISD::ADD, DL, VT, + DAG.getNode(ISD::ADD, DL, VT, N1, N0.getOperand(0)), + N0.getOperand(1)); + } + return SDValue(); + }; + if (SDValue Add = ReassociateAddOr(N0, N1)) + return Add; + if (SDValue Add = ReassociateAddOr(N1, N0)) + return Add; } // fold ((0-A) + B) -> B-A if (N0.getOpcode() == ISD::SUB && isNullOrNullSplat(N0.getOperand(0))) @@ -2502,6 +2521,26 @@ SDValue DAGCombiner::visitADD(SDNode *N) { return DAG.getNode(ISD::ADD, DL, VT, N0.getOperand(0), VS); } + // Fold (add step_vector(c1), step_vector(c2) to step_vector(c1+c2)) + if (N0.getOpcode() == ISD::STEP_VECTOR && + N1.getOpcode() == ISD::STEP_VECTOR) { + const APInt &C0 = N0->getConstantOperandAPInt(0); + const APInt &C1 = N1->getConstantOperandAPInt(0); + APInt NewStep = C0 + C1; + return DAG.getStepVector(DL, VT, NewStep); + } + + // Fold a + step_vector(c1) + step_vector(c2) to a + step_vector(c1+c2) + if ((N0.getOpcode() == ISD::ADD) && + (N0.getOperand(1).getOpcode() == ISD::STEP_VECTOR) && + (N1.getOpcode() == ISD::STEP_VECTOR)) { + const APInt &SV0 = N0.getOperand(1)->getConstantOperandAPInt(0); + const APInt &SV1 = N1->getConstantOperandAPInt(0); + APInt NewStep = SV0 + SV1; + SDValue SV = DAG.getStepVector(DL, VT, NewStep); + return DAG.getNode(ISD::ADD, DL, VT, N0.getOperand(0), SV); + } + return SDValue(); } @@ -2517,9 +2556,9 @@ SDValue DAGCombiner::visitADDSAT(SDNode *N) { // TODO SimplifyVBinOp // fold (add_sat x, 0) -> x, vector edition - if (ISD::isBuildVectorAllZeros(N1.getNode())) + if (ISD::isConstantSplatVectorAllZeros(N1.getNode())) return N0; - if (ISD::isBuildVectorAllZeros(N0.getNode())) + if (ISD::isConstantSplatVectorAllZeros(N0.getNode())) return N1; } @@ -3125,6 +3164,82 @@ SDValue DAGCombiner::visitADDCARRYLike(SDValue N0, SDValue N1, SDValue CarryIn, return SDValue(); } +// Attempt to create a USUBSAT(LHS, RHS) node with DstVT, performing a +// clamp/truncation if necessary. +static SDValue getTruncatedUSUBSAT(EVT DstVT, EVT SrcVT, SDValue LHS, + SDValue RHS, SelectionDAG &DAG, + const SDLoc &DL) { + assert(DstVT.getScalarSizeInBits() <= SrcVT.getScalarSizeInBits() && + "Illegal truncation"); + + if (DstVT == SrcVT) + return DAG.getNode(ISD::USUBSAT, DL, DstVT, LHS, RHS); + + // If the LHS is zero-extended then we can perform the USUBSAT as DstVT by + // clamping RHS. + APInt UpperBits = APInt::getBitsSetFrom(SrcVT.getScalarSizeInBits(), + DstVT.getScalarSizeInBits()); + if (!DAG.MaskedValueIsZero(LHS, UpperBits)) + return SDValue(); + + SDValue SatLimit = + DAG.getConstant(APInt::getLowBitsSet(SrcVT.getScalarSizeInBits(), + DstVT.getScalarSizeInBits()), + DL, SrcVT); + RHS = DAG.getNode(ISD::UMIN, DL, SrcVT, RHS, SatLimit); + RHS = DAG.getNode(ISD::TRUNCATE, DL, DstVT, RHS); + LHS = DAG.getNode(ISD::TRUNCATE, DL, DstVT, LHS); + return DAG.getNode(ISD::USUBSAT, DL, DstVT, LHS, RHS); +} + +// Try to find umax(a,b) - b or a - umin(a,b) patterns that may be converted to +// usubsat(a,b), optionally as a truncated type. +SDValue DAGCombiner::foldSubToUSubSat(EVT DstVT, SDNode *N) { + if (N->getOpcode() != ISD::SUB || + !(!LegalOperations || hasOperation(ISD::USUBSAT, DstVT))) + return SDValue(); + + EVT SubVT = N->getValueType(0); + SDValue Op0 = N->getOperand(0); + SDValue Op1 = N->getOperand(1); + + // Try to find umax(a,b) - b or a - umin(a,b) patterns + // they may be converted to usubsat(a,b). + if (Op0.getOpcode() == ISD::UMAX && Op0.hasOneUse()) { + SDValue MaxLHS = Op0.getOperand(0); + SDValue MaxRHS = Op0.getOperand(1); + if (MaxLHS == Op1) + return getTruncatedUSUBSAT(DstVT, SubVT, MaxRHS, Op1, DAG, SDLoc(N)); + if (MaxRHS == Op1) + return getTruncatedUSUBSAT(DstVT, SubVT, MaxLHS, Op1, DAG, SDLoc(N)); + } + + if (Op1.getOpcode() == ISD::UMIN && Op1.hasOneUse()) { + SDValue MinLHS = Op1.getOperand(0); + SDValue MinRHS = Op1.getOperand(1); + if (MinLHS == Op0) + return getTruncatedUSUBSAT(DstVT, SubVT, Op0, MinRHS, DAG, SDLoc(N)); + if (MinRHS == Op0) + return getTruncatedUSUBSAT(DstVT, SubVT, Op0, MinLHS, DAG, SDLoc(N)); + } + + // sub(a,trunc(umin(zext(a),b))) -> usubsat(a,trunc(umin(b,SatLimit))) + if (Op1.getOpcode() == ISD::TRUNCATE && + Op1.getOperand(0).getOpcode() == ISD::UMIN && + Op1.getOperand(0).hasOneUse()) { + SDValue MinLHS = Op1.getOperand(0).getOperand(0); + SDValue MinRHS = Op1.getOperand(0).getOperand(1); + if (MinLHS.getOpcode() == ISD::ZERO_EXTEND && MinLHS.getOperand(0) == Op0) + return getTruncatedUSUBSAT(DstVT, MinLHS.getValueType(), MinLHS, MinRHS, + DAG, SDLoc(N)); + if (MinRHS.getOpcode() == ISD::ZERO_EXTEND && MinRHS.getOperand(0) == Op0) + return getTruncatedUSUBSAT(DstVT, MinLHS.getValueType(), MinRHS, MinLHS, + DAG, SDLoc(N)); + } + + return SDValue(); +} + // Since it may not be valid to emit a fold to zero for vector initializers // check if we can before folding. static SDValue tryFoldToZero(const SDLoc &DL, const TargetLowering &TLI, EVT VT, @@ -3148,7 +3263,7 @@ SDValue DAGCombiner::visitSUB(SDNode *N) { return FoldedVOp; // fold (sub x, 0) -> x, vector edition - if (ISD::isBuildVectorAllZeros(N1.getNode())) + if (ISD::isConstantSplatVectorAllZeros(N1.getNode())) return N0; } @@ -3207,6 +3322,17 @@ SDValue DAGCombiner::visitSUB(SDNode *N) { !TLI.isOperationLegalOrCustom(ISD::ABS, VT) && TLI.expandABS(N1.getNode(), Result, DAG, true)) return Result; + + // Fold neg(splat(neg(x)) -> splat(x) + if (VT.isVector()) { + SDValue N1S = DAG.getSplatValue(N1, true); + if (N1S && N1S.getOpcode() == ISD::SUB && + isNullConstant(N1S.getOperand(0))) { + if (VT.isScalableVector()) + return DAG.getSplatVector(VT, DL, N1S.getOperand(1)); + return DAG.getSplatBuildVector(VT, DL, N1S.getOperand(1)); + } + } } // Canonicalize (sub -1, x) -> ~x, i.e. (xor x, -1) @@ -3343,6 +3469,9 @@ SDValue DAGCombiner::visitSUB(SDNode *N) { if (SDValue V = foldAddSubMasked1(false, N0, N1, DAG, SDLoc(N))) return V; + if (SDValue V = foldSubToUSubSat(VT, N)) + return V; + // (x - y) - 1 -> add (xor y, -1), x if (N0.hasOneUse() && N0.getOpcode() == ISD::SUB && isOneOrOneSplat(N1)) { SDValue Xor = DAG.getNode(ISD::XOR, DL, VT, N0.getOperand(1), @@ -3434,12 +3563,19 @@ SDValue DAGCombiner::visitSUB(SDNode *N) { } } - // canonicalize (sub X, (vscale * C)) to (add X, (vscale * -C)) + // canonicalize (sub X, (vscale * C)) to (add X, (vscale * -C)) if (N1.getOpcode() == ISD::VSCALE) { const APInt &IntVal = N1.getConstantOperandAPInt(0); return DAG.getNode(ISD::ADD, DL, VT, N0, DAG.getVScale(DL, VT, -IntVal)); } + // canonicalize (sub X, step_vector(C)) to (add X, step_vector(-C)) + if (N1.getOpcode() == ISD::STEP_VECTOR && N1.hasOneUse()) { + APInt NewStep = -N1.getConstantOperandAPInt(0); + return DAG.getNode(ISD::ADD, DL, VT, N0, + DAG.getStepVector(DL, VT, NewStep)); + } + // Prefer an add for more folding potential and possibly better codegen: // sub N0, (lshr N10, width-1) --> add N0, (ashr N10, width-1) if (!LegalOperations && N1.getOpcode() == ISD::SRL && N1.hasOneUse()) { @@ -3478,7 +3614,7 @@ SDValue DAGCombiner::visitSUBSAT(SDNode *N) { // TODO SimplifyVBinOp // fold (sub_sat x, 0) -> x, vector edition - if (ISD::isBuildVectorAllZeros(N1.getNode())) + if (ISD::isConstantSplatVectorAllZeros(N1.getNode())) return N0; } @@ -3814,6 +3950,15 @@ SDValue DAGCombiner::visitMUL(SDNode *N) { return DAG.getVScale(SDLoc(N), VT, C0 * C1); } + // Fold (mul step_vector(C0), C1) to (step_vector(C0 * C1)). + APInt MulVal; + if (N0.getOpcode() == ISD::STEP_VECTOR) + if (ISD::isConstantSplatVector(N1.getNode(), MulVal)) { + const APInt &C0 = N0.getConstantOperandAPInt(0); + APInt NewStep = C0 * MulVal; + return DAG.getStepVector(SDLoc(N), VT, NewStep); + } + // Fold ((mul x, 0/undef) -> 0, // (mul x, 1) -> x) -> x) // -> and(x, mask) @@ -4323,11 +4468,15 @@ SDValue DAGCombiner::visitMULHS(SDNode *N) { if (VT.isVector()) { // fold (mulhs x, 0) -> 0 // do not return N0/N1, because undef node may exist. - if (ISD::isBuildVectorAllZeros(N0.getNode()) || - ISD::isBuildVectorAllZeros(N1.getNode())) + if (ISD::isConstantSplatVectorAllZeros(N0.getNode()) || + ISD::isConstantSplatVectorAllZeros(N1.getNode())) return DAG.getConstant(0, DL, VT); } + // fold (mulhs c1, c2) + if (SDValue C = DAG.FoldConstantArithmetic(ISD::MULHS, DL, VT, {N0, N1})) + return C; + // fold (mulhs x, 0) -> 0 if (isNullConstant(N1)) return N1; @@ -4371,11 +4520,15 @@ SDValue DAGCombiner::visitMULHU(SDNode *N) { if (VT.isVector()) { // fold (mulhu x, 0) -> 0 // do not return N0/N1, because undef node may exist. - if (ISD::isBuildVectorAllZeros(N0.getNode()) || - ISD::isBuildVectorAllZeros(N1.getNode())) + if (ISD::isConstantSplatVectorAllZeros(N0.getNode()) || + ISD::isConstantSplatVectorAllZeros(N1.getNode())) return DAG.getConstant(0, DL, VT); } + // fold (mulhu c1, c2) + if (SDValue C = DAG.FoldConstantArithmetic(ISD::MULHU, DL, VT, {N0, N1})) + return C; + // fold (mulhu x, 0) -> 0 if (isNullConstant(N1)) return N1; @@ -4551,6 +4704,21 @@ SDValue DAGCombiner::visitMULO(SDNode *N) { EVT CarryVT = N->getValueType(1); SDLoc DL(N); + ConstantSDNode *N0C = isConstOrConstSplat(N0); + ConstantSDNode *N1C = isConstOrConstSplat(N1); + + // fold operation with constant operands. + // TODO: Move this to FoldConstantArithmetic when it supports nodes with + // multiple results. + if (N0C && N1C) { + bool Overflow; + APInt Result = + IsSigned ? N0C->getAPIntValue().smul_ov(N1C->getAPIntValue(), Overflow) + : N0C->getAPIntValue().umul_ov(N1C->getAPIntValue(), Overflow); + return CombineTo(N, DAG.getConstant(Result, DL, VT), + DAG.getBoolConstant(Overflow, DL, CarryVT, CarryVT)); + } + // canonicalize constant to RHS. if (DAG.isConstantIntBuildVectorOrConstantInt(N0) && !DAG.isConstantIntBuildVectorOrConstantInt(N1)) @@ -4562,10 +4730,37 @@ SDValue DAGCombiner::visitMULO(SDNode *N) { DAG.getConstant(0, DL, CarryVT)); // (mulo x, 2) -> (addo x, x) - if (ConstantSDNode *C2 = isConstOrConstSplat(N1)) - if (C2->getAPIntValue() == 2) - return DAG.getNode(IsSigned ? ISD::SADDO : ISD::UADDO, DL, - N->getVTList(), N0, N0); + if (N1C && N1C->getAPIntValue() == 2) + return DAG.getNode(IsSigned ? ISD::SADDO : ISD::UADDO, DL, + N->getVTList(), N0, N0); + + if (IsSigned) { + // A 1 bit SMULO overflows if both inputs are 1. + if (VT.getScalarSizeInBits() == 1) { + SDValue And = DAG.getNode(ISD::AND, DL, VT, N0, N1); + return CombineTo(N, And, + DAG.getSetCC(DL, CarryVT, And, + DAG.getConstant(0, DL, VT), ISD::SETNE)); + } + + // Multiplying n * m significant bits yields a result of n + m significant + // bits. If the total number of significant bits does not exceed the + // result bit width (minus 1), there is no overflow. + unsigned SignBits = DAG.ComputeNumSignBits(N0); + if (SignBits > 1) + SignBits += DAG.ComputeNumSignBits(N1); + if (SignBits > VT.getScalarSizeInBits() + 1) + return CombineTo(N, DAG.getNode(ISD::MUL, DL, VT, N0, N1), + DAG.getConstant(0, DL, CarryVT)); + } else { + KnownBits N1Known = DAG.computeKnownBits(N1); + KnownBits N0Known = DAG.computeKnownBits(N0); + bool Overflow; + (void)N0Known.getMaxValue().umul_ov(N1Known.getMaxValue(), Overflow); + if (!Overflow) + return CombineTo(N, DAG.getNode(ISD::MUL, DL, VT, N0, N1), + DAG.getConstant(0, DL, CarryVT)); + } return SDValue(); } @@ -4883,20 +5078,20 @@ SDValue DAGCombiner::foldLogicOfSetCCs(bool IsAnd, SDValue N0, SDValue N1, ConstantSDNode *C0 = isConstOrConstSplat(LR); ConstantSDNode *C1 = isConstOrConstSplat(RR); if (LL == RL && C0 && C1 && !C0->isOpaque() && !C1->isOpaque()) { - // Canonicalize larger constant as C0. - if (C1->getAPIntValue().ugt(C0->getAPIntValue())) - std::swap(C0, C1); - + const APInt &CMax = + APIntOps::umax(C0->getAPIntValue(), C1->getAPIntValue()); + const APInt &CMin = + APIntOps::umin(C0->getAPIntValue(), C1->getAPIntValue()); // The difference of the constants must be a single bit. - const APInt &C0Val = C0->getAPIntValue(); - const APInt &C1Val = C1->getAPIntValue(); - if ((C0Val - C1Val).isPowerOf2()) { - // and/or (setcc X, C0, ne), (setcc X, C1, ne/eq) --> - // setcc ((add X, -C1), ~(C0 - C1)), 0, ne/eq - SDValue OffsetC = DAG.getConstant(-C1Val, DL, OpVT); - SDValue Add = DAG.getNode(ISD::ADD, DL, OpVT, LL, OffsetC); - SDValue MaskC = DAG.getConstant(~(C0Val - C1Val), DL, OpVT); - SDValue And = DAG.getNode(ISD::AND, DL, OpVT, Add, MaskC); + if ((CMax - CMin).isPowerOf2()) { + // and/or (setcc X, CMax, ne), (setcc X, CMin, ne/eq) --> + // setcc ((sub X, CMin), ~(CMax - CMin)), 0, ne/eq + SDValue Max = DAG.getNode(ISD::UMAX, DL, OpVT, LR, RR); + SDValue Min = DAG.getNode(ISD::UMIN, DL, OpVT, LR, RR); + SDValue Offset = DAG.getNode(ISD::SUB, DL, OpVT, LL, Min); + SDValue Diff = DAG.getNode(ISD::SUB, DL, OpVT, Max, Min); + SDValue Mask = DAG.getNOT(DL, Diff, OpVT); + SDValue And = DAG.getNode(ISD::AND, DL, OpVT, Offset, Mask); SDValue Zero = DAG.getConstant(0, DL, OpVT); return DAG.getSetCC(DL, VT, And, Zero, CC0); } @@ -5428,19 +5623,19 @@ SDValue DAGCombiner::visitAND(SDNode *N) { return FoldedVOp; // fold (and x, 0) -> 0, vector edition - if (ISD::isBuildVectorAllZeros(N0.getNode())) + if (ISD::isConstantSplatVectorAllZeros(N0.getNode())) // do not return N0, because undef node may exist in N0 return DAG.getConstant(APInt::getNullValue(N0.getScalarValueSizeInBits()), SDLoc(N), N0.getValueType()); - if (ISD::isBuildVectorAllZeros(N1.getNode())) + if (ISD::isConstantSplatVectorAllZeros(N1.getNode())) // do not return N1, because undef node may exist in N1 return DAG.getConstant(APInt::getNullValue(N1.getScalarValueSizeInBits()), SDLoc(N), N1.getValueType()); // fold (and x, -1) -> x, vector edition - if (ISD::isBuildVectorAllOnes(N0.getNode())) + if (ISD::isConstantSplatVectorAllOnes(N0.getNode())) return N1; - if (ISD::isBuildVectorAllOnes(N1.getNode())) + if (ISD::isConstantSplatVectorAllOnes(N1.getNode())) return N0; // fold (and (masked_load) (build_vec (x, ...))) to zext_masked_load @@ -6194,16 +6389,16 @@ SDValue DAGCombiner::visitOR(SDNode *N) { return FoldedVOp; // fold (or x, 0) -> x, vector edition - if (ISD::isBuildVectorAllZeros(N0.getNode())) + if (ISD::isConstantSplatVectorAllZeros(N0.getNode())) return N1; - if (ISD::isBuildVectorAllZeros(N1.getNode())) + if (ISD::isConstantSplatVectorAllZeros(N1.getNode())) return N0; // fold (or x, -1) -> -1, vector edition - if (ISD::isBuildVectorAllOnes(N0.getNode())) + if (ISD::isConstantSplatVectorAllOnes(N0.getNode())) // do not return N0, because undef node may exist in N0 return DAG.getAllOnesConstant(SDLoc(N), N0.getValueType()); - if (ISD::isBuildVectorAllOnes(N1.getNode())) + if (ISD::isConstantSplatVectorAllOnes(N1.getNode())) // do not return N1, because undef node may exist in N1 return DAG.getAllOnesConstant(SDLoc(N), N1.getValueType()); @@ -6517,8 +6712,11 @@ static SDValue extractShiftForRotate(SelectionDAG &DAG, SDValue OppShift, // reduces to a rotate in direction shift2 by Pos or (equivalently) a rotate // in direction shift1 by Neg. The range [0, EltSize) means that we only need // to consider shift amounts with defined behavior. +// +// The IsRotate flag should be set when the LHS of both shifts is the same. +// Otherwise if matching a general funnel shift, it should be clear. static bool matchRotateSub(SDValue Pos, SDValue Neg, unsigned EltSize, - SelectionDAG &DAG) { + SelectionDAG &DAG, bool IsRotate) { // If EltSize is a power of 2 then: // // (a) (Pos == 0 ? 0 : EltSize - Pos) == (EltSize - Pos) & (EltSize - 1) @@ -6550,8 +6748,11 @@ static bool matchRotateSub(SDValue Pos, SDValue Neg, unsigned EltSize, // always invokes undefined behavior for 32-bit X. // // Below, Mask == EltSize - 1 when using [A] and is all-ones otherwise. + // + // NOTE: We can only do this when matching an AND and not a general + // funnel shift. unsigned MaskLoBits = 0; - if (Neg.getOpcode() == ISD::AND && isPowerOf2_64(EltSize)) { + if (IsRotate && Neg.getOpcode() == ISD::AND && isPowerOf2_64(EltSize)) { if (ConstantSDNode *NegC = isConstOrConstSplat(Neg.getOperand(1))) { KnownBits Known = DAG.computeKnownBits(Neg.getOperand(0)); unsigned Bits = Log2_64(EltSize); @@ -6641,7 +6842,8 @@ SDValue DAGCombiner::MatchRotatePosNeg(SDValue Shifted, SDValue Pos, // (srl x, (*ext y))) -> // (rotr x, y) or (rotl x, (sub 32, y)) EVT VT = Shifted.getValueType(); - if (matchRotateSub(InnerPos, InnerNeg, VT.getScalarSizeInBits(), DAG)) { + if (matchRotateSub(InnerPos, InnerNeg, VT.getScalarSizeInBits(), DAG, + /*IsRotate*/ true)) { bool HasPos = TLI.isOperationLegalOrCustom(PosOpcode, VT); return DAG.getNode(HasPos ? PosOpcode : NegOpcode, DL, VT, Shifted, HasPos ? Pos : Neg); @@ -6670,7 +6872,7 @@ SDValue DAGCombiner::MatchFunnelPosNeg(SDValue N0, SDValue N1, SDValue Pos, // fold (or (shl x0, (*ext (sub 32, y))), // (srl x1, (*ext y))) -> // (fshr x0, x1, y) or (fshl x0, x1, (sub 32, y)) - if (matchRotateSub(InnerPos, InnerNeg, EltBits, DAG)) { + if (matchRotateSub(InnerPos, InnerNeg, EltBits, DAG, /*IsRotate*/ N0 == N1)) { bool HasPos = TLI.isOperationLegalOrCustom(PosOpcode, VT); return DAG.getNode(HasPos ? PosOpcode : NegOpcode, DL, VT, N0, N1, HasPos ? Pos : Neg); @@ -7098,14 +7300,22 @@ SDValue DAGCombiner::mergeTruncStores(StoreSDNode *N) { if (LegalOperations) return SDValue(); - // Collect all the stores in the chain. - SDValue Chain; - SmallVector<StoreSDNode *, 8> Stores; - for (StoreSDNode *Store = N; Store; Store = dyn_cast<StoreSDNode>(Chain)) { - // TODO: Allow unordered atomics when wider type is legal (see D66309) - EVT MemVT = Store->getMemoryVT(); - if (!(MemVT == MVT::i8 || MemVT == MVT::i16 || MemVT == MVT::i32) || - !Store->isSimple() || Store->isIndexed()) + // We only handle merging simple stores of 1-4 bytes. + // TODO: Allow unordered atomics when wider type is legal (see D66309) + EVT MemVT = N->getMemoryVT(); + if (!(MemVT == MVT::i8 || MemVT == MVT::i16 || MemVT == MVT::i32) || + !N->isSimple() || N->isIndexed()) + return SDValue(); + + // Collect all of the stores in the chain. + SDValue Chain = N->getChain(); + SmallVector<StoreSDNode *, 8> Stores = {N}; + while (auto *Store = dyn_cast<StoreSDNode>(Chain)) { + // All stores must be the same size to ensure that we are writing all of the + // bytes in the wide value. + // TODO: We could allow multiple sizes by tracking each stored byte. + if (Store->getMemoryVT() != MemVT || !Store->isSimple() || + Store->isIndexed()) return SDValue(); Stores.push_back(Store); Chain = Store->getChain(); @@ -7548,9 +7758,9 @@ SDValue DAGCombiner::visitXOR(SDNode *N) { return FoldedVOp; // fold (xor x, 0) -> x, vector edition - if (ISD::isBuildVectorAllZeros(N0.getNode())) + if (ISD::isConstantSplatVectorAllZeros(N0.getNode())) return N1; - if (ISD::isBuildVectorAllZeros(N1.getNode())) + if (ISD::isConstantSplatVectorAllZeros(N1.getNode())) return N0; } @@ -8253,6 +8463,17 @@ SDValue DAGCombiner::visitSHL(SDNode *N) { return DAG.getVScale(SDLoc(N), VT, C0 << C1); } + // Fold (shl step_vector(C0), C1) to (step_vector(C0 << C1)). + APInt ShlVal; + if (N0.getOpcode() == ISD::STEP_VECTOR) + if (ISD::isConstantSplatVector(N1.getNode(), ShlVal)) { + const APInt &C0 = N0.getConstantOperandAPInt(0); + if (ShlVal.ult(C0.getBitWidth())) { + APInt NewStep = C0 << ShlVal; + return DAG.getStepVector(SDLoc(N), VT, NewStep); + } + } + return SDValue(); } @@ -8361,13 +8582,17 @@ SDValue DAGCombiner::visitSRA(SDNode *N) { unsigned LowBits = OpSizeInBits - (unsigned)N1C->getZExtValue(); EVT ExtVT = EVT::getIntegerVT(*DAG.getContext(), LowBits); if (VT.isVector()) - ExtVT = EVT::getVectorVT(*DAG.getContext(), - ExtVT, VT.getVectorNumElements()); + ExtVT = EVT::getVectorVT(*DAG.getContext(), ExtVT, + VT.getVectorElementCount()); if (!LegalOperations || TLI.getOperationAction(ISD::SIGN_EXTEND_INREG, ExtVT) == TargetLowering::Legal) return DAG.getNode(ISD::SIGN_EXTEND_INREG, SDLoc(N), VT, N0.getOperand(0), 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. + if (DAG.ComputeNumSignBits(N0.getOperand(0)) > N1C->getZExtValue()) + return N0.getOperand(0); } // fold (sra (sra x, c1), c2) -> (sra x, (add c1, c2)) @@ -8390,9 +8615,14 @@ SDValue DAGCombiner::visitSRA(SDNode *N) { }; if (ISD::matchBinaryPredicate(N1, N0.getOperand(1), SumOfShifts)) { SDValue ShiftValue; - if (VT.isVector()) + if (N1.getOpcode() == ISD::BUILD_VECTOR) ShiftValue = DAG.getBuildVector(ShiftVT, DL, ShiftValues); - else + else if (N1.getOpcode() == ISD::SPLAT_VECTOR) { + assert(ShiftValues.size() == 1 && + "Expected matchBinaryPredicate to return one element for " + "SPLAT_VECTORs"); + ShiftValue = DAG.getSplatVector(ShiftVT, DL, ShiftValues[0]); + } else ShiftValue = ShiftValues[0]; return DAG.getNode(ISD::SRA, DL, VT, N0.getOperand(0), ShiftValue); } @@ -8412,7 +8642,7 @@ SDValue DAGCombiner::visitSRA(SDNode *N) { EVT TruncVT = EVT::getIntegerVT(Ctx, OpSizeInBits - N1C->getZExtValue()); if (VT.isVector()) - TruncVT = EVT::getVectorVT(Ctx, TruncVT, VT.getVectorNumElements()); + TruncVT = EVT::getVectorVT(Ctx, TruncVT, VT.getVectorElementCount()); // Determine the residual right-shift amount. int ShiftAmt = N1C->getZExtValue() - N01C->getZExtValue(); @@ -8452,7 +8682,7 @@ SDValue DAGCombiner::visitSRA(SDNode *N) { unsigned ShiftAmt = N1C->getZExtValue(); EVT TruncVT = EVT::getIntegerVT(Ctx, OpSizeInBits - ShiftAmt); if (VT.isVector()) - TruncVT = EVT::getVectorVT(Ctx, TruncVT, VT.getVectorNumElements()); + TruncVT = EVT::getVectorVT(Ctx, TruncVT, VT.getVectorElementCount()); // TODO: The simple type check probably belongs in the default hook // implementation and/or target-specific overrides (because @@ -8865,6 +9095,40 @@ SDValue DAGCombiner::visitFunnelShift(SDNode *N) { return SDValue(); } +// Given a ABS node, detect the following pattern: +// (ABS (SUB (EXTEND a), (EXTEND b))). +// Generates UABD/SABD instruction. +static SDValue combineABSToABD(SDNode *N, SelectionDAG &DAG, + const TargetLowering &TLI) { + SDValue AbsOp1 = N->getOperand(0); + SDValue Op0, Op1; + + if (AbsOp1.getOpcode() != ISD::SUB) + return SDValue(); + + Op0 = AbsOp1.getOperand(0); + Op1 = AbsOp1.getOperand(1); + + unsigned Opc0 = Op0.getOpcode(); + // Check if the operands of the sub are (zero|sign)-extended. + if (Opc0 != Op1.getOpcode() || + (Opc0 != ISD::ZERO_EXTEND && Opc0 != ISD::SIGN_EXTEND)) + return SDValue(); + + EVT VT1 = Op0.getOperand(0).getValueType(); + EVT VT2 = Op1.getOperand(0).getValueType(); + // Check if the operands are of same type and valid size. + unsigned ABDOpcode = (Opc0 == ISD::SIGN_EXTEND) ? ISD::ABDS : ISD::ABDU; + if (VT1 != VT2 || !TLI.isOperationLegalOrCustom(ABDOpcode, VT1)) + return SDValue(); + + Op0 = Op0.getOperand(0); + Op1 = Op1.getOperand(0); + SDValue ABD = + DAG.getNode(ABDOpcode, SDLoc(N), Op0->getValueType(0), Op0, Op1); + return DAG.getNode(ISD::ZERO_EXTEND, SDLoc(N), N->getValueType(0), ABD); +} + SDValue DAGCombiner::visitABS(SDNode *N) { SDValue N0 = N->getOperand(0); EVT VT = N->getValueType(0); @@ -8878,6 +9142,10 @@ SDValue DAGCombiner::visitABS(SDNode *N) { // fold (abs x) -> x iff not-negative if (DAG.SignBitIsZero(N0)) return N0; + + if (SDValue ABD = combineABSToABD(N, DAG, TLI)) + return ABD; + return SDValue(); } @@ -9038,8 +9306,8 @@ static SDValue foldSelectOfConstantsUsingSra(SDNode *N, SelectionDAG &DAG) { SDValue Cond = N->getOperand(0); SDValue C1 = N->getOperand(1); SDValue C2 = N->getOperand(2); - assert(isConstantOrConstantVector(C1) && isConstantOrConstantVector(C2) && - "Expected select-of-constants"); + if (!isConstantOrConstantVector(C1) || !isConstantOrConstantVector(C2)) + return SDValue(); EVT VT = N->getValueType(0); if (Cond.getOpcode() != ISD::SETCC || !Cond.hasOneUse() || @@ -9177,6 +9445,40 @@ SDValue DAGCombiner::foldSelectOfConstants(SDNode *N) { return SDValue(); } +static SDValue foldBoolSelectToLogic(SDNode *N, SelectionDAG &DAG) { + assert((N->getOpcode() == ISD::SELECT || N->getOpcode() == ISD::VSELECT) && + "Expected a (v)select"); + SDValue Cond = N->getOperand(0); + SDValue T = N->getOperand(1), F = N->getOperand(2); + EVT VT = N->getValueType(0); + if (VT != Cond.getValueType() || VT.getScalarSizeInBits() != 1) + return SDValue(); + + // select Cond, Cond, F --> or Cond, F + // select Cond, 1, F --> or Cond, F + if (Cond == T || isOneOrOneSplat(T, /* AllowUndefs */ true)) + return DAG.getNode(ISD::OR, SDLoc(N), VT, Cond, F); + + // select Cond, T, Cond --> and Cond, T + // select Cond, T, 0 --> and Cond, T + if (Cond == F || isNullOrNullSplat(F, /* AllowUndefs */ true)) + return DAG.getNode(ISD::AND, SDLoc(N), VT, Cond, T); + + // select Cond, T, 1 --> or (not Cond), T + if (isOneOrOneSplat(F, /* AllowUndefs */ true)) { + SDValue NotCond = DAG.getNOT(SDLoc(N), Cond, VT); + return DAG.getNode(ISD::OR, SDLoc(N), VT, NotCond, T); + } + + // select Cond, 0, F --> and (not Cond), F + if (isNullOrNullSplat(T, /* AllowUndefs */ true)) { + SDValue NotCond = DAG.getNOT(SDLoc(N), Cond, VT); + return DAG.getNode(ISD::AND, SDLoc(N), VT, NotCond, F); + } + + return SDValue(); +} + SDValue DAGCombiner::visitSELECT(SDNode *N) { SDValue N0 = N->getOperand(0); SDValue N1 = N->getOperand(1); @@ -9189,30 +9491,11 @@ SDValue DAGCombiner::visitSELECT(SDNode *N) { if (SDValue V = DAG.simplifySelect(N0, N1, N2)) return V; - // fold (select X, X, Y) -> (or X, Y) - // fold (select X, 1, Y) -> (or C, Y) - if (VT == VT0 && VT == MVT::i1 && (N0 == N1 || isOneConstant(N1))) - return DAG.getNode(ISD::OR, DL, VT, N0, N2); - if (SDValue V = foldSelectOfConstants(N)) return V; - // fold (select C, 0, X) -> (and (not C), X) - if (VT == VT0 && VT == MVT::i1 && isNullConstant(N1)) { - SDValue NOTNode = DAG.getNOT(SDLoc(N0), N0, VT); - AddToWorklist(NOTNode.getNode()); - return DAG.getNode(ISD::AND, DL, VT, NOTNode, N2); - } - // fold (select C, X, 1) -> (or (not C), X) - if (VT == VT0 && VT == MVT::i1 && isOneConstant(N2)) { - SDValue NOTNode = DAG.getNOT(SDLoc(N0), N0, VT); - AddToWorklist(NOTNode.getNode()); - return DAG.getNode(ISD::OR, DL, VT, NOTNode, N1); - } - // fold (select X, Y, X) -> (and X, Y) - // fold (select X, Y, 0) -> (and X, Y) - if (VT == VT0 && VT == MVT::i1 && (N0 == N2 || isNullConstant(N2))) - return DAG.getNode(ISD::AND, DL, VT, N0, N1); + if (SDValue V = foldBoolSelectToLogic(N, DAG)) + return V; // If we can fold this based on the true/false value, do so. if (SimplifySelectOps(N, N1, N2)) @@ -9358,9 +9641,14 @@ SDValue DAGCombiner::visitSELECT(SDNode *N) { return SelectNode; } - return SimplifySelect(DL, N0, N1, N2); + if (SDValue NewSel = SimplifySelect(DL, N0, N1, N2)) + return NewSel; } + if (!VT.isVector()) + if (SDValue BinOp = foldSelectOfBinops(N)) + return BinOp; + return SDValue(); } @@ -9471,20 +9759,20 @@ SDValue DAGCombiner::visitMSCATTER(SDNode *N) { SDLoc DL(N); // Zap scatters with a zero mask. - if (ISD::isBuildVectorAllZeros(Mask.getNode())) + if (ISD::isConstantSplatVectorAllZeros(Mask.getNode())) return Chain; if (refineUniformBase(BasePtr, Index, DAG)) { SDValue Ops[] = {Chain, StoreVal, Mask, BasePtr, Index, Scale}; return DAG.getMaskedScatter( - DAG.getVTList(MVT::Other), StoreVal.getValueType(), DL, Ops, + DAG.getVTList(MVT::Other), MSC->getMemoryVT(), DL, Ops, MSC->getMemOperand(), MSC->getIndexType(), MSC->isTruncatingStore()); } if (refineIndexType(MSC, Index, MSC->isIndexScaled(), DAG)) { SDValue Ops[] = {Chain, StoreVal, Mask, BasePtr, Index, Scale}; return DAG.getMaskedScatter( - DAG.getVTList(MVT::Other), StoreVal.getValueType(), DL, Ops, + DAG.getVTList(MVT::Other), MSC->getMemoryVT(), DL, Ops, MSC->getMemOperand(), MSC->getIndexType(), MSC->isTruncatingStore()); } @@ -9498,12 +9786,12 @@ SDValue DAGCombiner::visitMSTORE(SDNode *N) { SDLoc DL(N); // Zap masked stores with a zero mask. - if (ISD::isBuildVectorAllZeros(Mask.getNode())) + if (ISD::isConstantSplatVectorAllZeros(Mask.getNode())) return Chain; // If this is a masked load with an all ones mask, we can use a unmasked load. // FIXME: Can we do this for indexed, compressing, or truncating stores? - if (ISD::isBuildVectorAllOnes(Mask.getNode()) && + if (ISD::isConstantSplatVectorAllOnes(Mask.getNode()) && MST->isUnindexed() && !MST->isCompressingStore() && !MST->isTruncatingStore()) return DAG.getStore(MST->getChain(), SDLoc(N), MST->getValue(), @@ -9527,13 +9815,13 @@ SDValue DAGCombiner::visitMGATHER(SDNode *N) { SDLoc DL(N); // Zap gathers with a zero mask. - if (ISD::isBuildVectorAllZeros(Mask.getNode())) + if (ISD::isConstantSplatVectorAllZeros(Mask.getNode())) return CombineTo(N, PassThru, MGT->getChain()); if (refineUniformBase(BasePtr, Index, DAG)) { SDValue Ops[] = {Chain, PassThru, Mask, BasePtr, Index, Scale}; return DAG.getMaskedGather(DAG.getVTList(N->getValueType(0), MVT::Other), - PassThru.getValueType(), DL, Ops, + MGT->getMemoryVT(), DL, Ops, MGT->getMemOperand(), MGT->getIndexType(), MGT->getExtensionType()); } @@ -9541,7 +9829,7 @@ SDValue DAGCombiner::visitMGATHER(SDNode *N) { if (refineIndexType(MGT, Index, MGT->isIndexScaled(), DAG)) { SDValue Ops[] = {Chain, PassThru, Mask, BasePtr, Index, Scale}; return DAG.getMaskedGather(DAG.getVTList(N->getValueType(0), MVT::Other), - PassThru.getValueType(), DL, Ops, + MGT->getMemoryVT(), DL, Ops, MGT->getMemOperand(), MGT->getIndexType(), MGT->getExtensionType()); } @@ -9555,12 +9843,12 @@ SDValue DAGCombiner::visitMLOAD(SDNode *N) { SDLoc DL(N); // Zap masked loads with a zero mask. - if (ISD::isBuildVectorAllZeros(Mask.getNode())) + if (ISD::isConstantSplatVectorAllZeros(Mask.getNode())) return CombineTo(N, MLD->getPassThru(), MLD->getChain()); // If this is a masked load with an all ones mask, we can use a unmasked load. // FIXME: Can we do this for indexed, expanding, or extending loads? - if (ISD::isBuildVectorAllOnes(Mask.getNode()) && + if (ISD::isConstantSplatVectorAllOnes(Mask.getNode()) && MLD->isUnindexed() && !MLD->isExpandingLoad() && MLD->getExtensionType() == ISD::NON_EXTLOAD) { SDValue NewLd = DAG.getLoad(N->getValueType(0), SDLoc(N), MLD->getChain(), @@ -9650,6 +9938,9 @@ SDValue DAGCombiner::visitVSELECT(SDNode *N) { if (SDValue V = DAG.simplifySelect(N0, N1, N2)) return V; + if (SDValue V = foldBoolSelectToLogic(N, DAG)) + return V; + // vselect (not Cond), N1, N2 -> vselect Cond, N2, N1 if (SDValue F = extractBooleanFlip(N0, DAG, TLI, false)) return DAG.getSelect(DL, VT, F, N2, N1); @@ -9734,10 +10025,10 @@ SDValue DAGCombiner::visitVSELECT(SDNode *N) { // If it's on the left side invert the predicate to simplify logic below. SDValue Other; ISD::CondCode SatCC = CC; - if (ISD::isBuildVectorAllOnes(N1.getNode())) { + if (ISD::isConstantSplatVectorAllOnes(N1.getNode())) { Other = N2; SatCC = ISD::getSetCCInverse(SatCC, VT.getScalarType()); - } else if (ISD::isBuildVectorAllOnes(N2.getNode())) { + } else if (ISD::isConstantSplatVectorAllOnes(N2.getNode())) { Other = N1; } @@ -9758,7 +10049,9 @@ SDValue DAGCombiner::visitVSELECT(SDNode *N) { (OpLHS == CondLHS || OpRHS == CondLHS)) return DAG.getNode(ISD::UADDSAT, DL, VT, OpLHS, OpRHS); - if (isa<BuildVectorSDNode>(OpRHS) && isa<BuildVectorSDNode>(CondRHS) && + if (OpRHS.getOpcode() == CondRHS.getOpcode() && + (OpRHS.getOpcode() == ISD::BUILD_VECTOR || + OpRHS.getOpcode() == ISD::SPLAT_VECTOR) && CondLHS == OpLHS) { // If the RHS is a constant we have to reverse the const // canonicalization. @@ -9779,54 +10072,71 @@ SDValue DAGCombiner::visitVSELECT(SDNode *N) { // the left side invert the predicate to simplify logic below. SDValue Other; ISD::CondCode SatCC = CC; - if (ISD::isBuildVectorAllZeros(N1.getNode())) { + if (ISD::isConstantSplatVectorAllZeros(N1.getNode())) { Other = N2; SatCC = ISD::getSetCCInverse(SatCC, VT.getScalarType()); - } else if (ISD::isBuildVectorAllZeros(N2.getNode())) { + } else if (ISD::isConstantSplatVectorAllZeros(N2.getNode())) { Other = N1; } - if (Other && Other.getNumOperands() == 2 && Other.getOperand(0) == LHS) { + if (Other && Other.getNumOperands() == 2) { SDValue CondRHS = RHS; SDValue OpLHS = Other.getOperand(0), OpRHS = Other.getOperand(1); - // Look for a general sub with unsigned saturation first. - // x >= y ? x-y : 0 --> usubsat x, y - // x > y ? x-y : 0 --> usubsat x, y - if ((SatCC == ISD::SETUGE || SatCC == ISD::SETUGT) && - Other.getOpcode() == ISD::SUB && OpRHS == CondRHS) - return DAG.getNode(ISD::USUBSAT, DL, VT, OpLHS, OpRHS); + if (Other.getOpcode() == ISD::SUB && + LHS.getOpcode() == ISD::ZERO_EXTEND && LHS.getOperand(0) == OpLHS && + OpRHS.getOpcode() == ISD::TRUNCATE && OpRHS.getOperand(0) == RHS) { + // Look for a general sub with unsigned saturation first. + // zext(x) >= y ? x - trunc(y) : 0 + // --> usubsat(x,trunc(umin(y,SatLimit))) + // zext(x) > y ? x - trunc(y) : 0 + // --> usubsat(x,trunc(umin(y,SatLimit))) + if (SatCC == ISD::SETUGE || SatCC == ISD::SETUGT) + return getTruncatedUSUBSAT(VT, LHS.getValueType(), LHS, RHS, DAG, + DL); + } - if (auto *OpRHSBV = dyn_cast<BuildVectorSDNode>(OpRHS)) { - if (isa<BuildVectorSDNode>(CondRHS)) { - // If the RHS is a constant we have to reverse the const - // canonicalization. - // x > C-1 ? x+-C : 0 --> usubsat x, C - auto MatchUSUBSAT = [](ConstantSDNode *Op, ConstantSDNode *Cond) { - return (!Op && !Cond) || - (Op && Cond && - Cond->getAPIntValue() == (-Op->getAPIntValue() - 1)); - }; - if (SatCC == ISD::SETUGT && Other.getOpcode() == ISD::ADD && - ISD::matchBinaryPredicate(OpRHS, CondRHS, MatchUSUBSAT, - /*AllowUndefs*/ true)) { - OpRHS = DAG.getNode(ISD::SUB, DL, VT, DAG.getConstant(0, DL, VT), - OpRHS); - return DAG.getNode(ISD::USUBSAT, DL, VT, OpLHS, OpRHS); - } + if (OpLHS == LHS) { + // Look for a general sub with unsigned saturation first. + // x >= y ? x-y : 0 --> usubsat x, y + // x > y ? x-y : 0 --> usubsat x, y + if ((SatCC == ISD::SETUGE || SatCC == ISD::SETUGT) && + Other.getOpcode() == ISD::SUB && OpRHS == CondRHS) + return DAG.getNode(ISD::USUBSAT, DL, VT, OpLHS, OpRHS); - // Another special case: If C was a sign bit, the sub has been - // canonicalized into a xor. - // FIXME: Would it be better to use computeKnownBits to determine - // whether it's safe to decanonicalize the xor? - // x s< 0 ? x^C : 0 --> usubsat x, C - if (auto *OpRHSConst = OpRHSBV->getConstantSplatNode()) { + if (OpRHS.getOpcode() == ISD::BUILD_VECTOR || + OpRHS.getOpcode() == ISD::SPLAT_VECTOR) { + if (CondRHS.getOpcode() == ISD::BUILD_VECTOR || + CondRHS.getOpcode() == ISD::SPLAT_VECTOR) { + // If the RHS is a constant we have to reverse the const + // canonicalization. + // x > C-1 ? x+-C : 0 --> usubsat x, C + auto MatchUSUBSAT = [](ConstantSDNode *Op, ConstantSDNode *Cond) { + return (!Op && !Cond) || + (Op && Cond && + Cond->getAPIntValue() == (-Op->getAPIntValue() - 1)); + }; + if (SatCC == ISD::SETUGT && Other.getOpcode() == ISD::ADD && + ISD::matchBinaryPredicate(OpRHS, CondRHS, MatchUSUBSAT, + /*AllowUndefs*/ true)) { + OpRHS = DAG.getNode(ISD::SUB, DL, VT, + DAG.getConstant(0, DL, VT), OpRHS); + return DAG.getNode(ISD::USUBSAT, DL, VT, OpLHS, OpRHS); + } + + // Another special case: If C was a sign bit, the sub has been + // canonicalized into a xor. + // FIXME: Would it be better to use computeKnownBits to determine + // whether it's safe to decanonicalize the xor? + // x s< 0 ? x^C : 0 --> usubsat x, C + APInt SplatValue; if (SatCC == ISD::SETLT && Other.getOpcode() == ISD::XOR && - ISD::isBuildVectorAllZeros(CondRHS.getNode()) && - OpRHSConst->getAPIntValue().isSignMask()) { - // Note that we have to rebuild the RHS constant here to ensure - // we don't rely on particular values of undef lanes. - OpRHS = DAG.getConstant(OpRHSConst->getAPIntValue(), DL, VT); + ISD::isConstantSplatVector(OpRHS.getNode(), SplatValue) && + ISD::isConstantSplatVectorAllZeros(CondRHS.getNode()) && + SplatValue.isSignMask()) { + // Note that we have to rebuild the RHS constant here to + // ensure we don't rely on particular values of undef lanes. + OpRHS = DAG.getConstant(SplatValue, DL, VT); return DAG.getNode(ISD::USUBSAT, DL, VT, OpLHS, OpRHS); } } @@ -9839,11 +10149,11 @@ SDValue DAGCombiner::visitVSELECT(SDNode *N) { if (SimplifySelectOps(N, N1, N2)) return SDValue(N, 0); // Don't revisit N. - // Fold (vselect (build_vector all_ones), N1, N2) -> N1 - if (ISD::isBuildVectorAllOnes(N0.getNode())) + // Fold (vselect all_ones, N1, N2) -> N1 + if (ISD::isConstantSplatVectorAllOnes(N0.getNode())) return N1; - // Fold (vselect (build_vector all_zeros), N1, N2) -> N2 - if (ISD::isBuildVectorAllZeros(N0.getNode())) + // Fold (vselect all_zeros, N1, N2) -> N2 + if (ISD::isConstantSplatVectorAllZeros(N0.getNode())) return N2; // The ConvertSelectToConcatVector function is assuming both the above @@ -9913,9 +10223,62 @@ SDValue DAGCombiner::visitSETCC(SDNode *N) { bool PreferSetCC = N->hasOneUse() && N->use_begin()->getOpcode() == ISD::BRCOND; - SDValue Combined = SimplifySetCC( - N->getValueType(0), N->getOperand(0), N->getOperand(1), - cast<CondCodeSDNode>(N->getOperand(2))->get(), SDLoc(N), !PreferSetCC); + ISD::CondCode Cond = cast<CondCodeSDNode>(N->getOperand(2))->get(); + EVT VT = N->getValueType(0); + + // SETCC(FREEZE(X), CONST, Cond) + // => + // FREEZE(SETCC(X, CONST, Cond)) + // This is correct if FREEZE(X) has one use and SETCC(FREEZE(X), CONST, Cond) + // isn't equivalent to true or false. + // For example, SETCC(FREEZE(X), -128, SETULT) cannot be folded to + // FREEZE(SETCC(X, -128, SETULT)) because X can be poison. + // + // This transformation is beneficial because visitBRCOND can fold + // BRCOND(FREEZE(X)) to BRCOND(X). + + // Conservatively optimize integer comparisons only. + if (PreferSetCC) { + // Do this only when SETCC is going to be used by BRCOND. + + SDValue N0 = N->getOperand(0), N1 = N->getOperand(1); + ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0); + ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1); + bool Updated = false; + + // Is 'X Cond C' always true or false? + auto IsAlwaysTrueOrFalse = [](ISD::CondCode Cond, ConstantSDNode *C) { + bool False = (Cond == ISD::SETULT && C->isNullValue()) || + (Cond == ISD::SETLT && C->isMinSignedValue()) || + (Cond == ISD::SETUGT && C->isAllOnesValue()) || + (Cond == ISD::SETGT && C->isMaxSignedValue()); + bool True = (Cond == ISD::SETULE && C->isAllOnesValue()) || + (Cond == ISD::SETLE && C->isMaxSignedValue()) || + (Cond == ISD::SETUGE && C->isNullValue()) || + (Cond == ISD::SETGE && C->isMinSignedValue()); + return True || False; + }; + + if (N0->getOpcode() == ISD::FREEZE && N0.hasOneUse() && N1C) { + if (!IsAlwaysTrueOrFalse(Cond, N1C)) { + N0 = N0->getOperand(0); + Updated = true; + } + } + if (N1->getOpcode() == ISD::FREEZE && N1.hasOneUse() && N0C) { + if (!IsAlwaysTrueOrFalse(ISD::getSetCCSwappedOperands(Cond), + N0C)) { + N1 = N1->getOperand(0); + Updated = true; + } + } + + if (Updated) + return DAG.getFreeze(DAG.getSetCC(SDLoc(N), VT, N0, N1, Cond)); + } + + SDValue Combined = SimplifySetCC(VT, N->getOperand(0), N->getOperand(1), Cond, + SDLoc(N), !PreferSetCC); if (!Combined) return SDValue(); @@ -9949,6 +10312,77 @@ SDValue DAGCombiner::visitSETCCCARRY(SDNode *N) { return SDValue(); } +/// Check if N satisfies: +/// N is used once. +/// N is a Load. +/// The load is compatible with ExtOpcode. It means +/// If load has explicit zero/sign extension, ExpOpcode must have the same +/// extension. +/// Otherwise returns true. +static bool isCompatibleLoad(SDValue N, unsigned ExtOpcode) { + if (!N.hasOneUse()) + return false; + + if (!isa<LoadSDNode>(N)) + return false; + + LoadSDNode *Load = cast<LoadSDNode>(N); + ISD::LoadExtType LoadExt = Load->getExtensionType(); + if (LoadExt == ISD::NON_EXTLOAD || LoadExt == ISD::EXTLOAD) + return true; + + // Now LoadExt is either SEXTLOAD or ZEXTLOAD, ExtOpcode must have the same + // extension. + if ((LoadExt == ISD::SEXTLOAD && ExtOpcode != ISD::SIGN_EXTEND) || + (LoadExt == ISD::ZEXTLOAD && ExtOpcode != ISD::ZERO_EXTEND)) + return false; + + return true; +} + +/// Fold +/// (sext (select c, load x, load y)) -> (select c, sextload x, sextload y) +/// (zext (select c, load x, load y)) -> (select c, zextload x, zextload y) +/// (aext (select c, load x, load y)) -> (select c, extload x, extload y) +/// This function is called by the DAGCombiner when visiting sext/zext/aext +/// dag nodes (see for example method DAGCombiner::visitSIGN_EXTEND). +static SDValue tryToFoldExtendSelectLoad(SDNode *N, const TargetLowering &TLI, + SelectionDAG &DAG) { + unsigned Opcode = N->getOpcode(); + SDValue N0 = N->getOperand(0); + EVT VT = N->getValueType(0); + SDLoc DL(N); + + assert((Opcode == ISD::SIGN_EXTEND || Opcode == ISD::ZERO_EXTEND || + Opcode == ISD::ANY_EXTEND) && + "Expected EXTEND dag node in input!"); + + if (!(N0->getOpcode() == ISD::SELECT || N0->getOpcode() == ISD::VSELECT) || + !N0.hasOneUse()) + return SDValue(); + + SDValue Op1 = N0->getOperand(1); + SDValue Op2 = N0->getOperand(2); + if (!isCompatibleLoad(Op1, Opcode) || !isCompatibleLoad(Op2, Opcode)) + return SDValue(); + + auto ExtLoadOpcode = ISD::EXTLOAD; + if (Opcode == ISD::SIGN_EXTEND) + ExtLoadOpcode = ISD::SEXTLOAD; + else if (Opcode == ISD::ZERO_EXTEND) + ExtLoadOpcode = ISD::ZEXTLOAD; + + LoadSDNode *Load1 = cast<LoadSDNode>(Op1); + LoadSDNode *Load2 = cast<LoadSDNode>(Op2); + if (!TLI.isLoadExtLegal(ExtLoadOpcode, VT, Load1->getMemoryVT()) || + !TLI.isLoadExtLegal(ExtLoadOpcode, VT, Load2->getMemoryVT())) + return SDValue(); + + SDValue Ext1 = DAG.getNode(Opcode, DL, VT, Op1); + SDValue Ext2 = DAG.getNode(Opcode, DL, VT, Op2); + return DAG.getSelect(DL, VT, N0->getOperand(0), Ext1, Ext2); +} + /// Try to fold a sext/zext/aext dag node into a ConstantSDNode or /// a build_vector of constants. /// This function is called by the DAGCombiner when visiting sext/zext/aext @@ -10481,6 +10915,128 @@ static SDValue foldExtendedSignBitTest(SDNode *N, SelectionDAG &DAG, return SDValue(); } +SDValue DAGCombiner::foldSextSetcc(SDNode *N) { + SDValue N0 = N->getOperand(0); + if (N0.getOpcode() != ISD::SETCC) + return SDValue(); + + SDValue N00 = N0.getOperand(0); + SDValue N01 = N0.getOperand(1); + ISD::CondCode CC = cast<CondCodeSDNode>(N0.getOperand(2))->get(); + EVT VT = N->getValueType(0); + EVT N00VT = N00.getValueType(); + SDLoc DL(N); + + // On some architectures (such as SSE/NEON/etc) the SETCC result type is + // the same size as the compared operands. Try to optimize sext(setcc()) + // if this is the case. + if (VT.isVector() && !LegalOperations && + TLI.getBooleanContents(N00VT) == + TargetLowering::ZeroOrNegativeOneBooleanContent) { + EVT SVT = getSetCCResultType(N00VT); + + // If we already have the desired type, don't change it. + if (SVT != N0.getValueType()) { + // We know that the # elements of the results is the same as the + // # elements of the compare (and the # elements of the compare result + // for that matter). Check to see that they are the same size. If so, + // we know that the element size of the sext'd result matches the + // element size of the compare operands. + if (VT.getSizeInBits() == SVT.getSizeInBits()) + return DAG.getSetCC(DL, VT, N00, N01, CC); + + // If the desired elements are smaller or larger than the source + // elements, we can use a matching integer vector type and then + // truncate/sign extend. + EVT MatchingVecType = N00VT.changeVectorElementTypeToInteger(); + if (SVT == MatchingVecType) { + SDValue VsetCC = DAG.getSetCC(DL, MatchingVecType, N00, N01, CC); + return DAG.getSExtOrTrunc(VsetCC, DL, VT); + } + } + + // Try to eliminate the sext of a setcc by zexting the compare operands. + if (N0.hasOneUse() && TLI.isOperationLegalOrCustom(ISD::SETCC, VT) && + !TLI.isOperationLegalOrCustom(ISD::SETCC, SVT)) { + bool IsSignedCmp = ISD::isSignedIntSetCC(CC); + unsigned LoadOpcode = IsSignedCmp ? ISD::SEXTLOAD : ISD::ZEXTLOAD; + unsigned ExtOpcode = IsSignedCmp ? ISD::SIGN_EXTEND : ISD::ZERO_EXTEND; + + // We have an unsupported narrow vector compare op that would be legal + // if extended to the destination type. See if the compare operands + // can be freely extended to the destination type. + auto IsFreeToExtend = [&](SDValue V) { + if (isConstantOrConstantVector(V, /*NoOpaques*/ true)) + return true; + // Match a simple, non-extended load that can be converted to a + // legal {z/s}ext-load. + // TODO: Allow widening of an existing {z/s}ext-load? + if (!(ISD::isNON_EXTLoad(V.getNode()) && + ISD::isUNINDEXEDLoad(V.getNode()) && + cast<LoadSDNode>(V)->isSimple() && + TLI.isLoadExtLegal(LoadOpcode, VT, V.getValueType()))) + return false; + + // Non-chain users of this value must either be the setcc in this + // sequence or extends that can be folded into the new {z/s}ext-load. + for (SDNode::use_iterator UI = V->use_begin(), UE = V->use_end(); + UI != UE; ++UI) { + // Skip uses of the chain and the setcc. + SDNode *User = *UI; + if (UI.getUse().getResNo() != 0 || User == N0.getNode()) + continue; + // Extra users must have exactly the same cast we are about to create. + // TODO: This restriction could be eased if ExtendUsesToFormExtLoad() + // is enhanced similarly. + if (User->getOpcode() != ExtOpcode || User->getValueType(0) != VT) + return false; + } + return true; + }; + + if (IsFreeToExtend(N00) && IsFreeToExtend(N01)) { + SDValue Ext0 = DAG.getNode(ExtOpcode, DL, VT, N00); + SDValue Ext1 = DAG.getNode(ExtOpcode, DL, VT, N01); + return DAG.getSetCC(DL, VT, Ext0, Ext1, CC); + } + } + } + + // sext(setcc x, y, cc) -> (select (setcc x, y, cc), T, 0) + // Here, T can be 1 or -1, depending on the type of the setcc and + // getBooleanContents(). + unsigned SetCCWidth = N0.getScalarValueSizeInBits(); + + // To determine the "true" side of the select, we need to know the high bit + // of the value returned by the setcc if it evaluates to true. + // If the type of the setcc is i1, then the true case of the select is just + // sext(i1 1), that is, -1. + // If the type of the setcc is larger (say, i8) then the value of the high + // bit depends on getBooleanContents(), so ask TLI for a real "true" value + // of the appropriate width. + SDValue ExtTrueVal = (SetCCWidth == 1) + ? DAG.getAllOnesConstant(DL, VT) + : DAG.getBoolConstant(true, DL, VT, N00VT); + SDValue Zero = DAG.getConstant(0, DL, VT); + if (SDValue SCC = SimplifySelectCC(DL, N00, N01, ExtTrueVal, Zero, CC, true)) + return SCC; + + if (!VT.isVector() && !TLI.convertSelectOfConstantsToMath(VT)) { + EVT SetCCVT = getSetCCResultType(N00VT); + // Don't do this transform for i1 because there's a select transform + // that would reverse it. + // TODO: We should not do this transform at all without a target hook + // because a sext is likely cheaper than a select? + if (SetCCVT.getScalarSizeInBits() != 1 && + (!LegalOperations || TLI.isOperationLegal(ISD::SETCC, N00VT))) { + SDValue SetCC = DAG.getSetCC(DL, SetCCVT, N00, N01, CC); + return DAG.getSelect(DL, VT, SetCC, ExtTrueVal, Zero); + } + } + + return SDValue(); +} + SDValue DAGCombiner::visitSIGN_EXTEND(SDNode *N) { SDValue N0 = N->getOperand(0); EVT VT = N->getValueType(0); @@ -10612,76 +11168,8 @@ SDValue DAGCombiner::visitSIGN_EXTEND(SDNode *N) { if (SDValue V = foldExtendedSignBitTest(N, DAG, LegalOperations)) return V; - if (N0.getOpcode() == ISD::SETCC) { - SDValue N00 = N0.getOperand(0); - SDValue N01 = N0.getOperand(1); - ISD::CondCode CC = cast<CondCodeSDNode>(N0.getOperand(2))->get(); - EVT N00VT = N00.getValueType(); - - // sext(setcc) -> sext_in_reg(vsetcc) for vectors. - // Only do this before legalize for now. - if (VT.isVector() && !LegalOperations && - TLI.getBooleanContents(N00VT) == - TargetLowering::ZeroOrNegativeOneBooleanContent) { - // On some architectures (such as SSE/NEON/etc) the SETCC result type is - // of the same size as the compared operands. Only optimize sext(setcc()) - // if this is the case. - EVT SVT = getSetCCResultType(N00VT); - - // If we already have the desired type, don't change it. - if (SVT != N0.getValueType()) { - // We know that the # elements of the results is the same as the - // # elements of the compare (and the # elements of the compare result - // for that matter). Check to see that they are the same size. If so, - // we know that the element size of the sext'd result matches the - // element size of the compare operands. - if (VT.getSizeInBits() == SVT.getSizeInBits()) - return DAG.getSetCC(DL, VT, N00, N01, CC); - - // If the desired elements are smaller or larger than the source - // elements, we can use a matching integer vector type and then - // truncate/sign extend. - EVT MatchingVecType = N00VT.changeVectorElementTypeToInteger(); - if (SVT == MatchingVecType) { - SDValue VsetCC = DAG.getSetCC(DL, MatchingVecType, N00, N01, CC); - return DAG.getSExtOrTrunc(VsetCC, DL, VT); - } - } - } - - // sext(setcc x, y, cc) -> (select (setcc x, y, cc), T, 0) - // Here, T can be 1 or -1, depending on the type of the setcc and - // getBooleanContents(). - unsigned SetCCWidth = N0.getScalarValueSizeInBits(); - - // To determine the "true" side of the select, we need to know the high bit - // of the value returned by the setcc if it evaluates to true. - // If the type of the setcc is i1, then the true case of the select is just - // sext(i1 1), that is, -1. - // If the type of the setcc is larger (say, i8) then the value of the high - // bit depends on getBooleanContents(), so ask TLI for a real "true" value - // of the appropriate width. - SDValue ExtTrueVal = (SetCCWidth == 1) - ? DAG.getAllOnesConstant(DL, VT) - : DAG.getBoolConstant(true, DL, VT, N00VT); - SDValue Zero = DAG.getConstant(0, DL, VT); - if (SDValue SCC = - SimplifySelectCC(DL, N00, N01, ExtTrueVal, Zero, CC, true)) - return SCC; - - if (!VT.isVector() && !TLI.convertSelectOfConstantsToMath(VT)) { - EVT SetCCVT = getSetCCResultType(N00VT); - // Don't do this transform for i1 because there's a select transform - // that would reverse it. - // TODO: We should not do this transform at all without a target hook - // because a sext is likely cheaper than a select? - if (SetCCVT.getScalarSizeInBits() != 1 && - (!LegalOperations || TLI.isOperationLegal(ISD::SETCC, N00VT))) { - SDValue SetCC = DAG.getSetCC(DL, SetCCVT, N00, N01, CC); - return DAG.getSelect(DL, VT, SetCC, ExtTrueVal, Zero); - } - } - } + if (SDValue V = foldSextSetcc(N)) + return V; // fold (sext x) -> (zext x) if the sign bit is known zero. if ((!LegalOperations || TLI.isOperationLegal(ISD::ZERO_EXTEND, VT)) && @@ -10733,6 +11221,9 @@ SDValue DAGCombiner::visitSIGN_EXTEND(SDNode *N) { return DAG.getNode(ISD::ADD, DL, VT, Zext, DAG.getAllOnesConstant(DL, VT)); } + if (SDValue Res = tryToFoldExtendSelectLoad(N, TLI, DAG)) + return Res; + return SDValue(); } @@ -11045,6 +11536,9 @@ SDValue DAGCombiner::visitZERO_EXTEND(SDNode *N) { if (SDValue NewCtPop = widenCtPop(N, DAG)) return NewCtPop; + if (SDValue Res = tryToFoldExtendSelectLoad(N, TLI, DAG)) + return Res; + return SDValue(); } @@ -11197,6 +11691,9 @@ SDValue DAGCombiner::visitANY_EXTEND(SDNode *N) { if (SDValue NewCtPop = widenCtPop(N, DAG)) return NewCtPop; + if (SDValue Res = tryToFoldExtendSelectLoad(N, TLI, DAG)) + return Res; + return SDValue(); } @@ -11542,14 +12039,24 @@ SDValue DAGCombiner::visitSIGN_EXTEND_INREG(SDNode *N) { } // fold (sext_in_reg (*_extend_vector_inreg x)) -> (sext_vector_inreg x) - if ((N0.getOpcode() == ISD::ANY_EXTEND_VECTOR_INREG || - N0.getOpcode() == ISD::SIGN_EXTEND_VECTOR_INREG || - N0.getOpcode() == ISD::ZERO_EXTEND_VECTOR_INREG) && - N0.getOperand(0).getScalarValueSizeInBits() == ExtVTBits) { - if (!LegalOperations || - TLI.isOperationLegal(ISD::SIGN_EXTEND_VECTOR_INREG, VT)) - return DAG.getNode(ISD::SIGN_EXTEND_VECTOR_INREG, SDLoc(N), VT, - N0.getOperand(0)); + // if x is small enough or if we know that x has more than 1 sign bit and the + // sign_extend_inreg is extending from one of them. + if (N0.getOpcode() == ISD::ANY_EXTEND_VECTOR_INREG || + N0.getOpcode() == ISD::SIGN_EXTEND_VECTOR_INREG || + N0.getOpcode() == ISD::ZERO_EXTEND_VECTOR_INREG) { + SDValue N00 = N0.getOperand(0); + unsigned N00Bits = N00.getScalarValueSizeInBits(); + unsigned DstElts = N0.getValueType().getVectorMinNumElements(); + unsigned SrcElts = N00.getValueType().getVectorMinNumElements(); + bool IsZext = N0.getOpcode() == ISD::ZERO_EXTEND_VECTOR_INREG; + APInt DemandedSrcElts = APInt::getLowBitsSet(SrcElts, DstElts); + if ((N00Bits == ExtVTBits || + (!IsZext && (N00Bits < ExtVTBits || + (N00Bits - DAG.ComputeNumSignBits(N00, DemandedSrcElts)) < + ExtVTBits))) && + (!LegalOperations || + TLI.isOperationLegal(ISD::SIGN_EXTEND_VECTOR_INREG, VT))) + return DAG.getNode(ISD::SIGN_EXTEND_VECTOR_INREG, SDLoc(N), VT, N00); } // fold (sext_in_reg (zext x)) -> (sext x) @@ -11610,6 +12117,7 @@ SDValue DAGCombiner::visitSIGN_EXTEND_INREG(SDNode *N) { AddToWorklist(ExtLoad.getNode()); return SDValue(N, 0); // Return N so it doesn't get rechecked! } + // fold (sext_inreg (zextload x)) -> (sextload x) iff load has one use if (ISD::isZEXTLoad(N0.getNode()) && ISD::isUNINDEXEDLoad(N0.getNode()) && N0.hasOneUse() && @@ -11671,28 +12179,11 @@ SDValue DAGCombiner::visitSIGN_EXTEND_INREG(SDNode *N) { return SDValue(); } -SDValue DAGCombiner::visitSIGN_EXTEND_VECTOR_INREG(SDNode *N) { - SDValue N0 = N->getOperand(0); - EVT VT = N->getValueType(0); - - // sext_vector_inreg(undef) = 0 because the top bit will all be the same. - if (N0.isUndef()) - return DAG.getConstant(0, SDLoc(N), VT); - - if (SDValue Res = tryToFoldExtendOfConstant(N, TLI, DAG, LegalTypes)) - return Res; - - if (SimplifyDemandedVectorElts(SDValue(N, 0))) - return SDValue(N, 0); - - return SDValue(); -} - -SDValue DAGCombiner::visitZERO_EXTEND_VECTOR_INREG(SDNode *N) { +SDValue DAGCombiner::visitEXTEND_VECTOR_INREG(SDNode *N) { SDValue N0 = N->getOperand(0); EVT VT = N->getValueType(0); - // zext_vector_inreg(undef) = 0 because the top bits will be zero. + // {s/z}ext_vector_inreg(undef) = 0 because the top bits must be the same. if (N0.isUndef()) return DAG.getConstant(0, SDLoc(N), VT); @@ -11812,6 +12303,9 @@ SDValue DAGCombiner::visitTRUNCATE(SDNode *N) { } } + if (SDValue V = foldSubToUSubSat(VT, N0.getNode())) + return V; + // Attempt to pre-truncate BUILD_VECTOR sources. if (N0.getOpcode() == ISD::BUILD_VECTOR && !LegalOperations && TLI.isTruncateFree(SrcVT.getScalarType(), VT.getScalarType()) && @@ -12013,6 +12507,20 @@ SDValue DAGCombiner::visitTRUNCATE(SDNode *N) { return DAG.getNode(N0.getOpcode(), DL, VT, NarrowL, NarrowR); } } + break; + case ISD::USUBSAT: + // Truncate the USUBSAT only if LHS is a known zero-extension, its not + // enough to know that the upper bits are zero we must ensure that we don't + // introduce an extra truncate. + if (!LegalOperations && N0.hasOneUse() && + N0.getOperand(0).getOpcode() == ISD::ZERO_EXTEND && + N0.getOperand(0).getOperand(0).getScalarValueSizeInBits() <= + VT.getScalarSizeInBits() && + hasOperation(N0.getOpcode(), VT)) { + return getTruncatedUSUBSAT(VT, SrcVT, N0.getOperand(0), N0.getOperand(1), + DAG, SDLoc(N)); + } + break; } return SDValue(); @@ -12141,7 +12649,7 @@ SDValue DAGCombiner::visitBITCAST(SDNode *N) { VT.getVectorElementType()); // If the input is a constant, let getNode fold it. - if (isa<ConstantSDNode>(N0) || isa<ConstantFPSDNode>(N0)) { + if (isIntOrFPConstant(N0)) { // If we can't allow illegal operations, we need to check that this is just // a fp -> int or int -> conversion and that the resulting operation will // be legal. @@ -12374,12 +12882,7 @@ SDValue DAGCombiner::visitBUILD_PAIR(SDNode *N) { SDValue DAGCombiner::visitFREEZE(SDNode *N) { SDValue N0 = N->getOperand(0); - // (freeze (freeze x)) -> (freeze x) - if (N0.getOpcode() == ISD::FREEZE) - return N0; - - // If the input is a constant, return it. - if (isa<ConstantSDNode>(N0) || isa<ConstantFPSDNode>(N0)) + if (DAG.isGuaranteedNotToBeUndefOrPoison(N0, /*PoisonOnly*/ false)) return N0; return SDValue(); @@ -12500,11 +13003,6 @@ ConstantFoldBITCASTofBUILD_VECTOR(SDNode *BV, EVT DstEltVT) { return DAG.getBuildVector(VT, DL, Ops); } -static bool isContractable(SDNode *N) { - SDNodeFlags F = N->getFlags(); - return F.hasAllowContract() || F.hasAllowReassociation(); -} - /// Try to perform FMA combining on a given FADD node. SDValue DAGCombiner::visitFADDForFMACombine(SDNode *N) { SDValue N0 = N->getOperand(0); @@ -12526,16 +13024,15 @@ SDValue DAGCombiner::visitFADDForFMACombine(SDNode *N) { if (!HasFMAD && !HasFMA) return SDValue(); - bool CanFuse = Options.UnsafeFPMath || isContractable(N); bool CanReassociate = Options.UnsafeFPMath || N->getFlags().hasAllowReassociation(); bool AllowFusionGlobally = (Options.AllowFPOpFusion == FPOpFusion::Fast || - CanFuse || HasFMAD); + Options.UnsafeFPMath || HasFMAD); // If the addition is not contractable, do not combine. - if (!AllowFusionGlobally && !isContractable(N)) + if (!AllowFusionGlobally && !N->getFlags().hasAllowContract()) return SDValue(); - if (STI && STI->generateFMAsInMachineCombiner(OptLevel)) + if (TLI.generateFMAsInMachineCombiner(VT, OptLevel)) return SDValue(); // Always prefer FMAD to FMA for precision. @@ -12547,7 +13044,7 @@ SDValue DAGCombiner::visitFADDForFMACombine(SDNode *N) { auto isContractableFMUL = [AllowFusionGlobally](SDValue N) { if (N.getOpcode() != ISD::FMUL) return false; - return AllowFusionGlobally || isContractable(N.getNode()); + return AllowFusionGlobally || N->getFlags().hasAllowContract(); }; // If we have two choices trying to fold (fadd (fmul u, v), (fmul x, y)), // prefer to fold the multiply with fewer uses. @@ -12736,15 +13233,14 @@ SDValue DAGCombiner::visitFSUBForFMACombine(SDNode *N) { return SDValue(); const SDNodeFlags Flags = N->getFlags(); - bool CanFuse = Options.UnsafeFPMath || isContractable(N); bool AllowFusionGlobally = (Options.AllowFPOpFusion == FPOpFusion::Fast || - CanFuse || HasFMAD); + Options.UnsafeFPMath || HasFMAD); // If the subtraction is not contractable, do not combine. - if (!AllowFusionGlobally && !isContractable(N)) + if (!AllowFusionGlobally && !N->getFlags().hasAllowContract()) return SDValue(); - if (STI && STI->generateFMAsInMachineCombiner(OptLevel)) + if (TLI.generateFMAsInMachineCombiner(VT, OptLevel)) return SDValue(); // Always prefer FMAD to FMA for precision. @@ -12757,7 +13253,7 @@ SDValue DAGCombiner::visitFSUBForFMACombine(SDNode *N) { auto isContractableFMUL = [AllowFusionGlobally](SDValue N) { if (N.getOpcode() != ISD::FMUL) return false; - return AllowFusionGlobally || isContractable(N.getNode()); + return AllowFusionGlobally || N->getFlags().hasAllowContract(); }; // fold (fsub (fmul x, y), z) -> (fma x, y, (fneg z)) @@ -12887,13 +13383,23 @@ SDValue DAGCombiner::visitFSUBForFMACombine(SDNode *N) { } } + auto isReassociable = [Options](SDNode *N) { + return Options.UnsafeFPMath || N->getFlags().hasAllowReassociation(); + }; + + auto isContractableAndReassociableFMUL = [isContractableFMUL, + isReassociable](SDValue N) { + return isContractableFMUL(N) && isReassociable(N.getNode()); + }; + // More folding opportunities when target permits. - if (Aggressive) { + if (Aggressive && isReassociable(N)) { + bool CanFuse = Options.UnsafeFPMath || N->getFlags().hasAllowContract(); // fold (fsub (fma x, y, (fmul u, v)), z) // -> (fma x, y (fma u, v, (fneg z))) if (CanFuse && N0.getOpcode() == PreferredFusedOpcode && - isContractableFMUL(N0.getOperand(2)) && N0->hasOneUse() && - N0.getOperand(2)->hasOneUse()) { + isContractableAndReassociableFMUL(N0.getOperand(2)) && + N0->hasOneUse() && N0.getOperand(2)->hasOneUse()) { return DAG.getNode(PreferredFusedOpcode, SL, VT, N0.getOperand(0), N0.getOperand(1), DAG.getNode(PreferredFusedOpcode, SL, VT, @@ -12905,7 +13411,7 @@ SDValue DAGCombiner::visitFSUBForFMACombine(SDNode *N) { // fold (fsub x, (fma y, z, (fmul u, v))) // -> (fma (fneg y), z, (fma (fneg u), v, x)) if (CanFuse && N1.getOpcode() == PreferredFusedOpcode && - isContractableFMUL(N1.getOperand(2)) && + isContractableAndReassociableFMUL(N1.getOperand(2)) && N1->hasOneUse() && NoSignedZero) { SDValue N20 = N1.getOperand(2).getOperand(0); SDValue N21 = N1.getOperand(2).getOperand(1); @@ -12916,7 +13422,6 @@ SDValue DAGCombiner::visitFSUBForFMACombine(SDNode *N) { DAG.getNode(ISD::FNEG, SL, VT, N20), N21, N0)); } - // fold (fsub (fma x, y, (fpext (fmul u, v))), z) // -> (fma x, y (fma (fpext u), (fpext v), (fneg z))) if (N0.getOpcode() == PreferredFusedOpcode && @@ -12924,7 +13429,7 @@ SDValue DAGCombiner::visitFSUBForFMACombine(SDNode *N) { SDValue N02 = N0.getOperand(2); if (N02.getOpcode() == ISD::FP_EXTEND) { SDValue N020 = N02.getOperand(0); - if (isContractableFMUL(N020) && + if (isContractableAndReassociableFMUL(N020) && TLI.isFPExtFoldable(DAG, PreferredFusedOpcode, VT, N020.getValueType())) { return DAG.getNode( @@ -12948,7 +13453,7 @@ SDValue DAGCombiner::visitFSUBForFMACombine(SDNode *N) { SDValue N00 = N0.getOperand(0); if (N00.getOpcode() == PreferredFusedOpcode) { SDValue N002 = N00.getOperand(2); - if (isContractableFMUL(N002) && + if (isContractableAndReassociableFMUL(N002) && TLI.isFPExtFoldable(DAG, PreferredFusedOpcode, VT, N00.getValueType())) { return DAG.getNode( @@ -12970,7 +13475,7 @@ SDValue DAGCombiner::visitFSUBForFMACombine(SDNode *N) { N1.getOperand(2).getOpcode() == ISD::FP_EXTEND && N1->hasOneUse()) { SDValue N120 = N1.getOperand(2).getOperand(0); - if (isContractableFMUL(N120) && + if (isContractableAndReassociableFMUL(N120) && TLI.isFPExtFoldable(DAG, PreferredFusedOpcode, VT, N120.getValueType())) { SDValue N1200 = N120.getOperand(0); @@ -12997,7 +13502,7 @@ SDValue DAGCombiner::visitFSUBForFMACombine(SDNode *N) { SDValue N100 = CvtSrc.getOperand(0); SDValue N101 = CvtSrc.getOperand(1); SDValue N102 = CvtSrc.getOperand(2); - if (isContractableFMUL(N102) && + if (isContractableAndReassociableFMUL(N102) && TLI.isFPExtFoldable(DAG, PreferredFusedOpcode, VT, CvtSrc.getValueType())) { SDValue N1020 = N102.getOperand(0); @@ -13933,13 +14438,25 @@ static inline bool CanCombineFCOPYSIGN_EXTEND_ROUND(SDNode *N) { SDValue N1 = N->getOperand(1); if ((N1.getOpcode() == ISD::FP_EXTEND || N1.getOpcode() == ISD::FP_ROUND)) { + EVT N1VT = N1->getValueType(0); + EVT N1Op0VT = N1->getOperand(0).getValueType(); + + // Always fold no-op FP casts. + if (N1VT == N1Op0VT) + return true; + // Do not optimize out type conversion of f128 type yet. // For some targets like x86_64, configuration is changed to keep one f128 // value in one SSE register, but instruction selection cannot handle // FCOPYSIGN on SSE registers yet. - EVT N1VT = N1->getValueType(0); - EVT N1Op0VT = N1->getOperand(0).getValueType(); - return (N1VT == N1Op0VT || N1Op0VT != MVT::f128); + if (N1Op0VT == MVT::f128) + return false; + + // Avoid mismatched vector operand types, for better instruction selection. + if (N1Op0VT.isVector()) + return false; + + return true; } return false; } @@ -15971,12 +16488,9 @@ bool DAGCombiner::SliceUpLoad(SDNode *N) { // Prepare the argument for the new token factor for all the slices. SmallVector<SDValue, 8> ArgChains; - for (SmallVectorImpl<LoadedSlice>::const_iterator - LSIt = LoadedSlices.begin(), - LSItEnd = LoadedSlices.end(); - LSIt != LSItEnd; ++LSIt) { - SDValue SliceInst = LSIt->loadSlice(); - CombineTo(LSIt->Inst, SliceInst, true); + for (const LoadedSlice &LS : LoadedSlices) { + SDValue SliceInst = LS.loadSlice(); + CombineTo(LS.Inst, SliceInst, true); if (SliceInst.getOpcode() != ISD::LOAD) SliceInst = SliceInst.getOperand(0); assert(SliceInst->getOpcode() == ISD::LOAD && @@ -16408,6 +16922,9 @@ bool DAGCombiner::mergeStoresOfConstantsOrVecElts( if (NumStores < 2) return false; + assert((!UseTrunc || !UseVector) && + "This optimization cannot emit a vector truncating store"); + // The latest Node in the DAG. SDLoc DL(StoreNodes[0].MemNode); @@ -16631,7 +17148,7 @@ void DAGCombiner::getStoreMergeCandidates( case StoreSource::Constant: if (NoTypeMatch) return false; - if (!(isa<ConstantSDNode>(OtherBC) || isa<ConstantFPSDNode>(OtherBC))) + if (!isIntOrFPConstant(OtherBC)) return false; break; case StoreSource::Extract: @@ -16903,6 +17420,7 @@ bool DAGCombiner::tryStoreMergeOfConstants( bool UseVector = (LastLegalVectorType > LastLegalType) && AllowVectors; unsigned NumElem = (UseVector) ? LastLegalVectorType : LastLegalType; + bool UseTrunc = LastIntegerTrunc && !UseVector; // Check if we found a legal integer type that creates a meaningful // merge. @@ -16933,8 +17451,9 @@ bool DAGCombiner::tryStoreMergeOfConstants( continue; } - MadeChange |= mergeStoresOfConstantsOrVecElts( - StoreNodes, MemVT, NumElem, true, UseVector, LastIntegerTrunc); + MadeChange |= mergeStoresOfConstantsOrVecElts(StoreNodes, MemVT, NumElem, + /*IsConstantSrc*/ true, + UseVector, UseTrunc); // Remove merged stores for next iteration. StoreNodes.erase(StoreNodes.begin(), StoreNodes.begin() + NumElem); @@ -17003,7 +17522,8 @@ bool DAGCombiner::tryStoreMergeOfExtracts( } MadeChange |= mergeStoresOfConstantsOrVecElts( - StoreNodes, MemVT, NumStoresToMerge, false, true, false); + StoreNodes, MemVT, NumStoresToMerge, /*IsConstantSrc*/ false, + /*UseVector*/ true, /*UseTrunc*/ false); StoreNodes.erase(StoreNodes.begin(), StoreNodes.begin() + NumStoresToMerge); NumConsecutiveStores -= NumStoresToMerge; @@ -17022,8 +17542,6 @@ bool DAGCombiner::tryStoreMergeOfLoads(SmallVectorImpl<MemOpLink> &StoreNodes, unsigned NumMemElts = MemVT.isVector() ? MemVT.getVectorNumElements() : 1; bool MadeChange = false; - int64_t StartAddress = StoreNodes[0].OffsetFromBase; - // Look for load nodes which are used by the stored values. SmallVector<MemOpLink, 8> LoadNodes; @@ -17091,7 +17609,7 @@ bool DAGCombiner::tryStoreMergeOfLoads(SmallVectorImpl<MemOpLink> &StoreNodes, unsigned LastLegalIntegerType = 1; bool isDereferenceable = true; bool DoIntegerTruncate = false; - StartAddress = LoadNodes[0].OffsetFromBase; + int64_t StartAddress = LoadNodes[0].OffsetFromBase; SDValue LoadChain = FirstLoad->getChain(); for (unsigned i = 1; i < LoadNodes.size(); ++i) { // All loads must share the same chain. @@ -17582,6 +18100,7 @@ SDValue DAGCombiner::visitSTORE(SDNode *N) { if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(Value)) { if (Ld->getBasePtr() == Ptr && ST->getMemoryVT() == Ld->getMemoryVT() && ST->isUnindexed() && ST->isSimple() && + Ld->getAddressSpace() == ST->getAddressSpace() && // There can't be any side effects between the load and store, such as // a call or store. Chain.reachesChainWithoutSideEffects(SDValue(Ld, 1))) { @@ -17595,7 +18114,8 @@ SDValue DAGCombiner::visitSTORE(SDNode *N) { if (ST->isUnindexed() && ST->isSimple() && ST1->isUnindexed() && ST1->isSimple()) { if (ST1->getBasePtr() == Ptr && ST1->getValue() == Value && - ST->getMemoryVT() == ST1->getMemoryVT()) { + ST->getMemoryVT() == ST1->getMemoryVT() && + ST->getAddressSpace() == ST1->getAddressSpace()) { // If this is a store followed by a store with the same value to the // same location, then the store is dead/noop. return Chain; @@ -17606,7 +18126,8 @@ SDValue DAGCombiner::visitSTORE(SDNode *N) { // BaseIndexOffset and the code below requires knowing the size // of a vector, so bail out if MemoryVT is scalable. !ST->getMemoryVT().isScalableVector() && - !ST1->getMemoryVT().isScalableVector()) { + !ST1->getMemoryVT().isScalableVector() && + ST->getAddressSpace() == ST1->getAddressSpace()) { const BaseIndexOffset STBase = BaseIndexOffset::match(ST, DAG); const BaseIndexOffset ChainBase = BaseIndexOffset::match(ST1, DAG); unsigned STBitSize = ST->getMemoryVT().getFixedSizeInBits(); @@ -17625,10 +18146,11 @@ SDValue DAGCombiner::visitSTORE(SDNode *N) { // If this is an FP_ROUND or TRUNC followed by a store, fold this into a // truncating store. We can do this even if this is already a truncstore. - if ((Value.getOpcode() == ISD::FP_ROUND || Value.getOpcode() == ISD::TRUNCATE) - && Value.getNode()->hasOneUse() && ST->isUnindexed() && - TLI.isTruncStoreLegal(Value.getOperand(0).getValueType(), - ST->getMemoryVT())) { + if ((Value.getOpcode() == ISD::FP_ROUND || + Value.getOpcode() == ISD::TRUNCATE) && + Value.getNode()->hasOneUse() && ST->isUnindexed() && + TLI.canCombineTruncStore(Value.getOperand(0).getValueType(), + ST->getMemoryVT(), LegalOperations)) { return DAG.getTruncStore(Chain, SDLoc(N), Value.getOperand(0), Ptr, ST->getMemoryVT(), ST->getMemOperand()); } @@ -18086,26 +18608,19 @@ SDValue DAGCombiner::scalarizeExtractedVectorLoad(SDNode *EVE, EVT InVecVT, Alignment = NewAlign; - SDValue NewPtr = OriginalLoad->getBasePtr(); - SDValue Offset; - EVT PtrType = NewPtr.getValueType(); MachinePointerInfo MPI; SDLoc DL(EVE); if (auto *ConstEltNo = dyn_cast<ConstantSDNode>(EltNo)) { int Elt = ConstEltNo->getZExtValue(); unsigned PtrOff = VecEltVT.getSizeInBits() * Elt / 8; - Offset = DAG.getConstant(PtrOff, DL, PtrType); MPI = OriginalLoad->getPointerInfo().getWithOffset(PtrOff); } else { - Offset = DAG.getZExtOrTrunc(EltNo, DL, PtrType); - Offset = DAG.getNode( - ISD::MUL, DL, PtrType, Offset, - DAG.getConstant(VecEltVT.getStoreSize(), DL, PtrType)); // Discard the pointer info except the address space because the memory // operand can't represent this new access since the offset is variable. MPI = MachinePointerInfo(OriginalLoad->getPointerInfo().getAddrSpace()); } - NewPtr = DAG.getMemBasePlusOffset(NewPtr, Offset, DL); + SDValue NewPtr = TLI.getVectorElementPointer(DAG, OriginalLoad->getBasePtr(), + InVecVT, EltNo); // The replacement we need to do here is a little tricky: we need to // replace an extractelement of a load with a load. @@ -18710,6 +19225,9 @@ SDValue DAGCombiner::createBuildVecShuffle(const SDLoc &DL, SDNode *N, uint64_t InVT1Size = InVT1.getFixedSizeInBits(); uint64_t InVT2Size = InVT2.getFixedSizeInBits(); + assert(InVT2Size <= InVT1Size && + "Inputs must be sorted to be in non-increasing vector size order."); + // We can't generate a shuffle node with mismatched input and output types. // Try to make the types match the type of the output. if (InVT1 != VT || InVT2 != VT) { @@ -18736,7 +19254,10 @@ SDValue DAGCombiner::createBuildVecShuffle(const SDLoc &DL, SDNode *N, // Since we now have shorter input vectors, adjust the offset of the // second vector's start. Vec2Offset = NumElems; - } else if (InVT2Size <= InVT1Size) { + } else { + assert(InVT2Size <= InVT1Size && + "Second input is not going to be larger than the first one."); + // VecIn1 is wider than the output, and we have another, possibly // smaller input. Pad the smaller input with undefs, shuffle at the // input vector width, and extract the output. @@ -18755,11 +19276,6 @@ SDValue DAGCombiner::createBuildVecShuffle(const SDLoc &DL, SDNode *N, DAG.getUNDEF(InVT1), VecIn2, ZeroIdx); } ShuffleNumElems = NumElems * 2; - } else { - // Both VecIn1 and VecIn2 are wider than the output, and VecIn2 is wider - // than VecIn1. We can't handle this for now - this case will disappear - // when we start sorting the vectors by type. - return SDValue(); } } else if (InVT2Size * 2 == VTSize && InVT1Size == VTSize) { SmallVector<SDValue, 2> ConcatOps(2, DAG.getUNDEF(InVT2)); @@ -18884,6 +19400,15 @@ static SDValue reduceBuildVecToShuffleWithZero(SDNode *BV, SelectionDAG &DAG) { return DAG.getBitcast(VT, Shuf); } +// FIXME: promote to STLExtras. +template <typename R, typename T> +static auto getFirstIndexOf(R &&Range, const T &Val) { + auto I = find(Range, Val); + if (I == Range.end()) + return static_cast<decltype(std::distance(Range.begin(), I))>(-1); + return std::distance(Range.begin(), I); +} + // Check to see if this is a BUILD_VECTOR of a bunch of EXTRACT_VECTOR_ELT // operations. If the types of the vectors we're extracting from allow it, // turn this into a vector_shuffle node. @@ -18952,9 +19477,11 @@ SDValue DAGCombiner::reduceBuildVecToShuffle(SDNode *N) { // Have we seen this input vector before? // The vectors are expected to be tiny (usually 1 or 2 elements), so using // a map back from SDValues to numbers isn't worth it. - unsigned Idx = std::distance(VecIn.begin(), find(VecIn, ExtractedFromVec)); - if (Idx == VecIn.size()) + int Idx = getFirstIndexOf(VecIn, ExtractedFromVec); + if (Idx == -1) { // A new source vector? + Idx = VecIn.size(); VecIn.push_back(ExtractedFromVec); + } VectorMask[i] = Idx; } @@ -18989,7 +19516,9 @@ SDValue DAGCombiner::reduceBuildVecToShuffle(SDNode *N) { unsigned SplitSize = NearestPow2 / 2; EVT SplitVT = EVT::getVectorVT(*DAG.getContext(), InVT.getVectorElementType(), SplitSize); - if (TLI.isTypeLegal(SplitVT)) { + if (TLI.isTypeLegal(SplitVT) && + SplitSize + SplitVT.getVectorNumElements() <= + InVT.getVectorNumElements()) { SDValue VecIn2 = DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, SplitVT, Vec, DAG.getVectorIdxConstant(SplitSize, DL)); SDValue VecIn1 = DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, SplitVT, Vec, @@ -19008,9 +19537,28 @@ SDValue DAGCombiner::reduceBuildVecToShuffle(SDNode *N) { } } - // TODO: We want to sort the vectors by descending length, so that adjacent - // pairs have similar length, and the longer vector is always first in the - // pair. + // Sort input vectors by decreasing vector element count, + // while preserving the relative order of equally-sized vectors. + // Note that we keep the first "implicit zero vector as-is. + SmallVector<SDValue, 8> SortedVecIn(VecIn); + llvm::stable_sort(MutableArrayRef<SDValue>(SortedVecIn).drop_front(), + [](const SDValue &a, const SDValue &b) { + return a.getValueType().getVectorNumElements() > + b.getValueType().getVectorNumElements(); + }); + + // We now also need to rebuild the VectorMask, because it referenced element + // order in VecIn, and we just sorted them. + for (int &SourceVectorIndex : VectorMask) { + if (SourceVectorIndex <= 0) + continue; + unsigned Idx = getFirstIndexOf(SortedVecIn, VecIn[SourceVectorIndex]); + assert(Idx > 0 && Idx < SortedVecIn.size() && + VecIn[SourceVectorIndex] == SortedVecIn[Idx] && "Remapping failure"); + SourceVectorIndex = Idx; + } + + VecIn = std::move(SortedVecIn); // TODO: Should this fire if some of the input vectors has illegal type (like // it does now), or should we let legalization run its course first? @@ -19183,13 +19731,6 @@ SDValue DAGCombiner::visitBUILD_VECTOR(SDNode *N) { } } - // A splat of a single element is a SPLAT_VECTOR if supported on the target. - if (TLI.getOperationAction(ISD::SPLAT_VECTOR, VT) != TargetLowering::Expand) - if (SDValue V = cast<BuildVectorSDNode>(N)->getSplatValue()) { - assert(!V.isUndef() && "Splat of undef should have been handled earlier"); - return DAG.getNode(ISD::SPLAT_VECTOR, SDLoc(N), VT, V); - } - // Check if we can express BUILD VECTOR via subvector extract. if (!LegalTypes && (N->getNumOperands() > 1)) { SDValue Op0 = N->getOperand(0); @@ -19231,6 +19772,14 @@ SDValue DAGCombiner::visitBUILD_VECTOR(SDNode *N) { if (SDValue V = reduceBuildVecToShuffle(N)) return V; + // A splat of a single element is a SPLAT_VECTOR if supported on the target. + // Do this late as some of the above may replace the splat. + if (TLI.getOperationAction(ISD::SPLAT_VECTOR, VT) != TargetLowering::Expand) + if (SDValue V = cast<BuildVectorSDNode>(N)->getSplatValue()) { + assert(!V.isUndef() && "Splat of undef should have been handled earlier"); + return DAG.getNode(ISD::SPLAT_VECTOR, SDLoc(N), VT, V); + } + return SDValue(); } @@ -19879,7 +20428,8 @@ SDValue DAGCombiner::visitEXTRACT_SUBVECTOR(SDNode *N) { // Try to move vector bitcast after extract_subv by scaling extraction index: // extract_subv (bitcast X), Index --> bitcast (extract_subv X, Index') if (V.getOpcode() == ISD::BITCAST && - V.getOperand(0).getValueType().isVector()) { + V.getOperand(0).getValueType().isVector() && + (!LegalOperations || TLI.isOperationLegal(ISD::BITCAST, NVT))) { SDValue SrcOp = V.getOperand(0); EVT SrcVT = SrcOp.getValueType(); unsigned SrcNumElts = SrcVT.getVectorMinNumElements(); @@ -20052,6 +20602,9 @@ static SDValue foldShuffleOfConcatUndefs(ShuffleVectorSDNode *Shuf, for (unsigned i = 0; i != NumElts; ++i) { if (Mask[i] == -1) continue; + // If we reference the upper (undef) subvector then the element is undef. + if ((Mask[i] % NumElts) >= HalfNumElts) + continue; int M = Mask[i] < (int)NumElts ? Mask[i] : Mask[i] - (int)HalfNumElts; if (i < HalfNumElts) Mask0[i] = M; @@ -20213,7 +20766,7 @@ static SDValue combineShuffleOfScalars(ShuffleVectorSDNode *SVN, // generating a splat; semantically, this is fine, but it's likely to // generate low-quality code if the target can't reconstruct an appropriate // shuffle. - if (!Op.isUndef() && !isa<ConstantSDNode>(Op) && !isa<ConstantFPSDNode>(Op)) + if (!Op.isUndef() && !isIntOrFPConstant(Op)) if (!IsSplat && !DuplicateOps.insert(Op).second) return SDValue(); @@ -20798,44 +21351,15 @@ SDValue DAGCombiner::visitVECTOR_SHUFFLE(SDNode *N) { } } - if (Level < AfterLegalizeDAG && TLI.isTypeLegal(VT)) { - // Canonicalize shuffles according to rules: - // shuffle(A, shuffle(A, B)) -> shuffle(shuffle(A,B), A) - // shuffle(B, shuffle(A, B)) -> shuffle(shuffle(A,B), B) - // shuffle(B, shuffle(A, Undef)) -> shuffle(shuffle(A, Undef), B) - if (N1.getOpcode() == ISD::VECTOR_SHUFFLE && - N0.getOpcode() != ISD::VECTOR_SHUFFLE) { - // The incoming shuffle must be of the same type as the result of the - // current shuffle. - assert(N1->getOperand(0).getValueType() == VT && - "Shuffle types don't match"); - - SDValue SV0 = N1->getOperand(0); - SDValue SV1 = N1->getOperand(1); - bool HasSameOp0 = N0 == SV0; - bool IsSV1Undef = SV1.isUndef(); - if (HasSameOp0 || IsSV1Undef || N0 == SV1) - // Commute the operands of this shuffle so merging below will trigger. - return DAG.getCommutedVectorShuffle(*SVN); - } - - // Canonicalize splat shuffles to the RHS to improve merging below. - // shuffle(splat(A,u), shuffle(C,D)) -> shuffle'(shuffle(C,D), splat(A,u)) - if (N0.getOpcode() == ISD::VECTOR_SHUFFLE && - N1.getOpcode() == ISD::VECTOR_SHUFFLE && - cast<ShuffleVectorSDNode>(N0)->isSplat() && - !cast<ShuffleVectorSDNode>(N1)->isSplat()) { - return DAG.getCommutedVectorShuffle(*SVN); - } - } - // Compute the combined shuffle mask for a shuffle with SV0 as the first // operand, and SV1 as the second operand. - // i.e. Merge SVN(OtherSVN, N1) -> shuffle(SV0, SV1, Mask). - auto MergeInnerShuffle = [NumElts](ShuffleVectorSDNode *SVN, - ShuffleVectorSDNode *OtherSVN, SDValue N1, - SDValue &SV0, SDValue &SV1, - SmallVectorImpl<int> &Mask) -> bool { + // i.e. Merge SVN(OtherSVN, N1) -> shuffle(SV0, SV1, Mask) iff Commute = false + // Merge SVN(N1, OtherSVN) -> shuffle(SV0, SV1, Mask') iff Commute = true + auto MergeInnerShuffle = + [NumElts, &VT](bool Commute, ShuffleVectorSDNode *SVN, + ShuffleVectorSDNode *OtherSVN, SDValue N1, + const TargetLowering &TLI, SDValue &SV0, SDValue &SV1, + SmallVectorImpl<int> &Mask) -> bool { // Don't try to fold splats; they're likely to simplify somehow, or they // might be free. if (OtherSVN->isSplat()) @@ -20852,6 +21376,9 @@ SDValue DAGCombiner::visitVECTOR_SHUFFLE(SDNode *N) { continue; } + if (Commute) + Idx = (Idx < (int)NumElts) ? (Idx + NumElts) : (Idx - NumElts); + SDValue CurrentVec; if (Idx < (int)NumElts) { // This shuffle index refers to the inner shuffle N0. Lookup the inner @@ -20922,44 +21449,161 @@ SDValue DAGCombiner::visitVECTOR_SHUFFLE(SDNode *N) { // Bail out if we cannot convert the shuffle pair into a single shuffle. return false; } - return true; + + if (llvm::all_of(Mask, [](int M) { return M < 0; })) + return true; + + // Avoid introducing shuffles with illegal mask. + // shuffle(shuffle(A, B, M0), C, M1) -> shuffle(A, B, M2) + // shuffle(shuffle(A, B, M0), C, M1) -> shuffle(A, C, M2) + // shuffle(shuffle(A, B, M0), C, M1) -> shuffle(B, C, M2) + // shuffle(shuffle(A, B, M0), C, M1) -> shuffle(B, A, M2) + // shuffle(shuffle(A, B, M0), C, M1) -> shuffle(C, A, M2) + // shuffle(shuffle(A, B, M0), C, M1) -> shuffle(C, B, M2) + if (TLI.isShuffleMaskLegal(Mask, VT)) + return true; + + std::swap(SV0, SV1); + ShuffleVectorSDNode::commuteMask(Mask); + return TLI.isShuffleMaskLegal(Mask, VT); }; - // Try to fold according to rules: - // shuffle(shuffle(A, B, M0), C, M1) -> shuffle(A, B, M2) - // shuffle(shuffle(A, B, M0), C, M1) -> shuffle(A, C, M2) - // shuffle(shuffle(A, B, M0), C, M1) -> shuffle(B, C, M2) - // Don't try to fold shuffles with illegal type. - // Only fold if this shuffle is the only user of the other shuffle. - if (N0.getOpcode() == ISD::VECTOR_SHUFFLE && N->isOnlyUserOf(N0.getNode()) && - Level < AfterLegalizeDAG && TLI.isTypeLegal(VT)) { - ShuffleVectorSDNode *OtherSV = cast<ShuffleVectorSDNode>(N0); + if (Level < AfterLegalizeDAG && TLI.isTypeLegal(VT)) { + // Canonicalize shuffles according to rules: + // shuffle(A, shuffle(A, B)) -> shuffle(shuffle(A,B), A) + // shuffle(B, shuffle(A, B)) -> shuffle(shuffle(A,B), B) + // shuffle(B, shuffle(A, Undef)) -> shuffle(shuffle(A, Undef), B) + if (N1.getOpcode() == ISD::VECTOR_SHUFFLE && + N0.getOpcode() != ISD::VECTOR_SHUFFLE) { + // The incoming shuffle must be of the same type as the result of the + // current shuffle. + assert(N1->getOperand(0).getValueType() == VT && + "Shuffle types don't match"); + + SDValue SV0 = N1->getOperand(0); + SDValue SV1 = N1->getOperand(1); + bool HasSameOp0 = N0 == SV0; + bool IsSV1Undef = SV1.isUndef(); + if (HasSameOp0 || IsSV1Undef || N0 == SV1) + // Commute the operands of this shuffle so merging below will trigger. + return DAG.getCommutedVectorShuffle(*SVN); + } - // The incoming shuffle must be of the same type as the result of the - // current shuffle. - assert(OtherSV->getOperand(0).getValueType() == VT && - "Shuffle types don't match"); + // Canonicalize splat shuffles to the RHS to improve merging below. + // shuffle(splat(A,u), shuffle(C,D)) -> shuffle'(shuffle(C,D), splat(A,u)) + if (N0.getOpcode() == ISD::VECTOR_SHUFFLE && + N1.getOpcode() == ISD::VECTOR_SHUFFLE && + cast<ShuffleVectorSDNode>(N0)->isSplat() && + !cast<ShuffleVectorSDNode>(N1)->isSplat()) { + return DAG.getCommutedVectorShuffle(*SVN); + } - SDValue SV0, SV1; - SmallVector<int, 4> Mask; - if (MergeInnerShuffle(SVN, OtherSV, N1, SV0, SV1, Mask)) { - // Check if all indices in Mask are Undef. In case, propagate Undef. - if (llvm::all_of(Mask, [](int M) { return M < 0; })) - return DAG.getUNDEF(VT); + // Try to fold according to rules: + // shuffle(shuffle(A, B, M0), C, M1) -> shuffle(A, B, M2) + // shuffle(shuffle(A, B, M0), C, M1) -> shuffle(A, C, M2) + // shuffle(shuffle(A, B, M0), C, M1) -> shuffle(B, C, M2) + // Don't try to fold shuffles with illegal type. + // Only fold if this shuffle is the only user of the other shuffle. + // Try matching shuffle(C,shuffle(A,B)) commutted patterns as well. + for (int i = 0; i != 2; ++i) { + if (N->getOperand(i).getOpcode() == ISD::VECTOR_SHUFFLE && + N->isOnlyUserOf(N->getOperand(i).getNode())) { + // The incoming shuffle must be of the same type as the result of the + // current shuffle. + auto *OtherSV = cast<ShuffleVectorSDNode>(N->getOperand(i)); + assert(OtherSV->getOperand(0).getValueType() == VT && + "Shuffle types don't match"); - if (!SV0.getNode()) - SV0 = DAG.getUNDEF(VT); - if (!SV1.getNode()) - SV1 = DAG.getUNDEF(VT); + SDValue SV0, SV1; + SmallVector<int, 4> Mask; + if (MergeInnerShuffle(i != 0, SVN, OtherSV, N->getOperand(1 - i), TLI, + SV0, SV1, Mask)) { + // Check if all indices in Mask are Undef. In case, propagate Undef. + if (llvm::all_of(Mask, [](int M) { return M < 0; })) + return DAG.getUNDEF(VT); - // Avoid introducing shuffles with illegal mask. - // shuffle(shuffle(A, B, M0), C, M1) -> shuffle(A, B, M2) - // shuffle(shuffle(A, B, M0), C, M1) -> shuffle(A, C, M2) - // shuffle(shuffle(A, B, M0), C, M1) -> shuffle(B, C, M2) - // shuffle(shuffle(A, B, M0), C, M1) -> shuffle(B, A, M2) - // shuffle(shuffle(A, B, M0), C, M1) -> shuffle(C, A, M2) - // shuffle(shuffle(A, B, M0), C, M1) -> shuffle(C, B, M2) - return TLI.buildLegalVectorShuffle(VT, SDLoc(N), SV0, SV1, Mask, DAG); + return DAG.getVectorShuffle(VT, SDLoc(N), + SV0 ? SV0 : DAG.getUNDEF(VT), + SV1 ? SV1 : DAG.getUNDEF(VT), Mask); + } + } + } + + // Merge shuffles through binops if we are able to merge it with at least + // one other shuffles. + // shuffle(bop(shuffle(x,y),shuffle(z,w)),undef) + // shuffle(bop(shuffle(x,y),shuffle(z,w)),bop(shuffle(a,b),shuffle(c,d))) + unsigned SrcOpcode = N0.getOpcode(); + if (TLI.isBinOp(SrcOpcode) && N->isOnlyUserOf(N0.getNode()) && + (N1.isUndef() || + (SrcOpcode == N1.getOpcode() && N->isOnlyUserOf(N1.getNode())))) { + // Get binop source ops, or just pass on the undef. + SDValue Op00 = N0.getOperand(0); + SDValue Op01 = N0.getOperand(1); + SDValue Op10 = N1.isUndef() ? N1 : N1.getOperand(0); + SDValue Op11 = N1.isUndef() ? N1 : N1.getOperand(1); + // TODO: We might be able to relax the VT check but we don't currently + // have any isBinOp() that has different result/ops VTs so play safe until + // we have test coverage. + if (Op00.getValueType() == VT && Op10.getValueType() == VT && + Op01.getValueType() == VT && Op11.getValueType() == VT && + (Op00.getOpcode() == ISD::VECTOR_SHUFFLE || + Op10.getOpcode() == ISD::VECTOR_SHUFFLE || + Op01.getOpcode() == ISD::VECTOR_SHUFFLE || + Op11.getOpcode() == ISD::VECTOR_SHUFFLE)) { + auto CanMergeInnerShuffle = [&](SDValue &SV0, SDValue &SV1, + SmallVectorImpl<int> &Mask, bool LeftOp, + bool Commute) { + SDValue InnerN = Commute ? N1 : N0; + SDValue Op0 = LeftOp ? Op00 : Op01; + SDValue Op1 = LeftOp ? Op10 : Op11; + if (Commute) + std::swap(Op0, Op1); + // Only accept the merged shuffle if we don't introduce undef elements, + // or the inner shuffle already contained undef elements. + auto *SVN0 = dyn_cast<ShuffleVectorSDNode>(Op0); + return SVN0 && InnerN->isOnlyUserOf(SVN0) && + MergeInnerShuffle(Commute, SVN, SVN0, Op1, TLI, SV0, SV1, + Mask) && + (llvm::any_of(SVN0->getMask(), [](int M) { return M < 0; }) || + llvm::none_of(Mask, [](int M) { return M < 0; })); + }; + + // Ensure we don't increase the number of shuffles - we must merge a + // shuffle from at least one of the LHS and RHS ops. + bool MergedLeft = false; + SDValue LeftSV0, LeftSV1; + SmallVector<int, 4> LeftMask; + if (CanMergeInnerShuffle(LeftSV0, LeftSV1, LeftMask, true, false) || + CanMergeInnerShuffle(LeftSV0, LeftSV1, LeftMask, true, true)) { + MergedLeft = true; + } else { + LeftMask.assign(SVN->getMask().begin(), SVN->getMask().end()); + LeftSV0 = Op00, LeftSV1 = Op10; + } + + bool MergedRight = false; + SDValue RightSV0, RightSV1; + SmallVector<int, 4> RightMask; + if (CanMergeInnerShuffle(RightSV0, RightSV1, RightMask, false, false) || + CanMergeInnerShuffle(RightSV0, RightSV1, RightMask, false, true)) { + MergedRight = true; + } else { + RightMask.assign(SVN->getMask().begin(), SVN->getMask().end()); + RightSV0 = Op01, RightSV1 = Op11; + } + + if (MergedLeft || MergedRight) { + SDLoc DL(N); + SDValue LHS = DAG.getVectorShuffle( + VT, DL, LeftSV0 ? LeftSV0 : DAG.getUNDEF(VT), + LeftSV1 ? LeftSV1 : DAG.getUNDEF(VT), LeftMask); + SDValue RHS = DAG.getVectorShuffle( + VT, DL, RightSV0 ? RightSV0 : DAG.getUNDEF(VT), + RightSV1 ? RightSV1 : DAG.getUNDEF(VT), RightMask); + return DAG.getNode(SrcOpcode, DL, VT, LHS, RHS); + } + } } } @@ -21174,7 +21818,7 @@ SDValue DAGCombiner::visitFP16_TO_FP(SDNode *N) { SDValue N0 = N->getOperand(0); // fold fp16_to_fp(op & 0xffff) -> fp16_to_fp(op) - if (N0->getOpcode() == ISD::AND) { + if (!TLI.shouldKeepZExtForFP16Conv() && N0->getOpcode() == ISD::AND) { ConstantSDNode *AndConst = getAsNonOpaqueConstant(N0.getOperand(1)); if (AndConst && AndConst->getAPIntValue() == 0xffff) { return DAG.getNode(ISD::FP16_TO_FP, SDLoc(N), N->getValueType(0), @@ -21775,6 +22419,50 @@ SDValue DAGCombiner::foldSelectCCToShiftAnd(const SDLoc &DL, SDValue N0, return DAG.getNode(ISD::AND, DL, AType, Shift, N2); } +// Fold select(cc, binop(), binop()) -> binop(select(), select()) etc. +SDValue DAGCombiner::foldSelectOfBinops(SDNode *N) { + SDValue N0 = N->getOperand(0); + SDValue N1 = N->getOperand(1); + SDValue N2 = N->getOperand(2); + EVT VT = N->getValueType(0); + SDLoc DL(N); + + unsigned BinOpc = N1.getOpcode(); + if (!TLI.isBinOp(BinOpc) || (N2.getOpcode() != BinOpc)) + return SDValue(); + + if (!N->isOnlyUserOf(N0.getNode()) || !N->isOnlyUserOf(N1.getNode())) + return SDValue(); + + // Fold select(cond, binop(x, y), binop(z, y)) + // --> binop(select(cond, x, z), y) + if (N1.getOperand(1) == N2.getOperand(1)) { + SDValue NewSel = + DAG.getSelect(DL, VT, N0, N1.getOperand(0), N2.getOperand(0)); + SDValue NewBinOp = DAG.getNode(BinOpc, DL, VT, NewSel, N1.getOperand(1)); + NewBinOp->setFlags(N1->getFlags()); + NewBinOp->intersectFlagsWith(N2->getFlags()); + return NewBinOp; + } + + // Fold select(cond, binop(x, y), binop(x, z)) + // --> binop(x, select(cond, y, z)) + // Second op VT might be different (e.g. shift amount type) + if (N1.getOperand(0) == N2.getOperand(0) && + VT == N1.getOperand(1).getValueType() && + VT == N2.getOperand(1).getValueType()) { + SDValue NewSel = + DAG.getSelect(DL, VT, N0, N1.getOperand(1), N2.getOperand(1)); + SDValue NewBinOp = DAG.getNode(BinOpc, DL, VT, N1.getOperand(0), NewSel); + NewBinOp->setFlags(N1->getFlags()); + NewBinOp->intersectFlagsWith(N2->getFlags()); + return NewBinOp; + } + + // TODO: Handle isCommutativeBinOp patterns as well? + return SDValue(); +} + // Transform (fneg/fabs (bitconvert x)) to avoid loading constant pool values. SDValue DAGCombiner::foldSignChangeInBitcast(SDNode *N) { SDValue N0 = N->getOperand(0); @@ -22426,12 +23114,11 @@ bool DAGCombiner::isAlias(SDNode *Op0, SDNode *Op1) const { int64_t MinOffset = std::min(SrcValOffset0, SrcValOffset1); int64_t Overlap0 = *Size0 + SrcValOffset0 - MinOffset; int64_t Overlap1 = *Size1 + SrcValOffset1 - MinOffset; - AliasResult AAResult = AA->alias( - MemoryLocation(MUC0.MMO->getValue(), Overlap0, - UseTBAA ? MUC0.MMO->getAAInfo() : AAMDNodes()), - MemoryLocation(MUC1.MMO->getValue(), Overlap1, - UseTBAA ? MUC1.MMO->getAAInfo() : AAMDNodes())); - if (AAResult == NoAlias) + if (AA->isNoAlias( + MemoryLocation(MUC0.MMO->getValue(), Overlap0, + UseTBAA ? MUC0.MMO->getAAInfo() : AAMDNodes()), + MemoryLocation(MUC1.MMO->getValue(), Overlap1, + UseTBAA ? MUC1.MMO->getAAInfo() : AAMDNodes()))) return false; } @@ -22614,6 +23301,10 @@ bool DAGCombiner::parallelizeChainedStores(StoreSDNode *St) { if (BasePtr.getBase().isUndef()) return false; + // Do not handle stores to opaque types + if (St->getMemoryVT().isZeroSized()) + return false; + // BaseIndexOffset assumes that offsets are fixed-size, which // is not valid for scalable vectors where the offsets are // scaled by `vscale`, so bail out early. @@ -22624,6 +23315,9 @@ bool DAGCombiner::parallelizeChainedStores(StoreSDNode *St) { Intervals.insert(0, (St->getMemoryVT().getSizeInBits() + 7) / 8, Unit); while (StoreSDNode *Chain = dyn_cast<StoreSDNode>(STChain->getChain())) { + if (Chain->getMemoryVT().isScalableVector()) + return false; + // If the chain has more than one use, then we can't reorder the mem ops. if (!SDValue(Chain, 0)->hasOneUse()) break; |