in llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp [3574:4479]
SDValue TargetLowering::SimplifySetCC(EVT VT, SDValue N0, SDValue N1,
ISD::CondCode Cond, bool foldBooleans,
DAGCombinerInfo &DCI,
const SDLoc &dl) const {
SelectionDAG &DAG = DCI.DAG;
const DataLayout &Layout = DAG.getDataLayout();
EVT OpVT = N0.getValueType();
// Constant fold or commute setcc.
if (SDValue Fold = DAG.FoldSetCC(VT, N0, N1, Cond, dl))
return Fold;
// Ensure that the constant occurs on the RHS and fold constant comparisons.
// TODO: Handle non-splat vector constants. All undef causes trouble.
// FIXME: We can't yet fold constant scalable vector splats, so avoid an
// infinite loop here when we encounter one.
ISD::CondCode SwappedCC = ISD::getSetCCSwappedOperands(Cond);
if (isConstOrConstSplat(N0) &&
(!OpVT.isScalableVector() || !isConstOrConstSplat(N1)) &&
(DCI.isBeforeLegalizeOps() ||
isCondCodeLegal(SwappedCC, N0.getSimpleValueType())))
return DAG.getSetCC(dl, VT, N1, N0, SwappedCC);
// If we have a subtract with the same 2 non-constant operands as this setcc
// -- but in reverse order -- then try to commute the operands of this setcc
// to match. A matching pair of setcc (cmp) and sub may be combined into 1
// instruction on some targets.
if (!isConstOrConstSplat(N0) && !isConstOrConstSplat(N1) &&
(DCI.isBeforeLegalizeOps() ||
isCondCodeLegal(SwappedCC, N0.getSimpleValueType())) &&
DAG.doesNodeExist(ISD::SUB, DAG.getVTList(OpVT), {N1, N0}) &&
!DAG.doesNodeExist(ISD::SUB, DAG.getVTList(OpVT), {N0, N1}))
return DAG.getSetCC(dl, VT, N1, N0, SwappedCC);
if (auto *N1C = isConstOrConstSplat(N1)) {
const APInt &C1 = N1C->getAPIntValue();
// Optimize some CTPOP cases.
if (SDValue V = simplifySetCCWithCTPOP(*this, VT, N0, C1, Cond, dl, DAG))
return V;
// If the LHS is '(srl (ctlz x), 5)', the RHS is 0/1, and this is an
// equality comparison, then we're just comparing whether X itself is
// zero.
if (N0.getOpcode() == ISD::SRL && (C1.isZero() || C1.isOne()) &&
N0.getOperand(0).getOpcode() == ISD::CTLZ &&
isPowerOf2_32(N0.getScalarValueSizeInBits())) {
if (ConstantSDNode *ShAmt = isConstOrConstSplat(N0.getOperand(1))) {
if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
ShAmt->getAPIntValue() == Log2_32(N0.getScalarValueSizeInBits())) {
if ((C1 == 0) == (Cond == ISD::SETEQ)) {
// (srl (ctlz x), 5) == 0 -> X != 0
// (srl (ctlz x), 5) != 1 -> X != 0
Cond = ISD::SETNE;
} else {
// (srl (ctlz x), 5) != 0 -> X == 0
// (srl (ctlz x), 5) == 1 -> X == 0
Cond = ISD::SETEQ;
}
SDValue Zero = DAG.getConstant(0, dl, N0.getValueType());
return DAG.getSetCC(dl, VT, N0.getOperand(0).getOperand(0), Zero,
Cond);
}
}
}
}
// FIXME: Support vectors.
if (auto *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
const APInt &C1 = N1C->getAPIntValue();
// (zext x) == C --> x == (trunc C)
// (sext x) == C --> x == (trunc C)
if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
DCI.isBeforeLegalize() && N0->hasOneUse()) {
unsigned MinBits = N0.getValueSizeInBits();
SDValue PreExt;
bool Signed = false;
if (N0->getOpcode() == ISD::ZERO_EXTEND) {
// ZExt
MinBits = N0->getOperand(0).getValueSizeInBits();
PreExt = N0->getOperand(0);
} else if (N0->getOpcode() == ISD::AND) {
// DAGCombine turns costly ZExts into ANDs
if (auto *C = dyn_cast<ConstantSDNode>(N0->getOperand(1)))
if ((C->getAPIntValue()+1).isPowerOf2()) {
MinBits = C->getAPIntValue().countTrailingOnes();
PreExt = N0->getOperand(0);
}
} else if (N0->getOpcode() == ISD::SIGN_EXTEND) {
// SExt
MinBits = N0->getOperand(0).getValueSizeInBits();
PreExt = N0->getOperand(0);
Signed = true;
} else if (auto *LN0 = dyn_cast<LoadSDNode>(N0)) {
// ZEXTLOAD / SEXTLOAD
if (LN0->getExtensionType() == ISD::ZEXTLOAD) {
MinBits = LN0->getMemoryVT().getSizeInBits();
PreExt = N0;
} else if (LN0->getExtensionType() == ISD::SEXTLOAD) {
Signed = true;
MinBits = LN0->getMemoryVT().getSizeInBits();
PreExt = N0;
}
}
// Figure out how many bits we need to preserve this constant.
unsigned ReqdBits = Signed ? C1.getMinSignedBits() : C1.getActiveBits();
// Make sure we're not losing bits from the constant.
if (MinBits > 0 &&
MinBits < C1.getBitWidth() &&
MinBits >= ReqdBits) {
EVT MinVT = EVT::getIntegerVT(*DAG.getContext(), MinBits);
if (isTypeDesirableForOp(ISD::SETCC, MinVT)) {
// Will get folded away.
SDValue Trunc = DAG.getNode(ISD::TRUNCATE, dl, MinVT, PreExt);
if (MinBits == 1 && C1 == 1)
// Invert the condition.
return DAG.getSetCC(dl, VT, Trunc, DAG.getConstant(0, dl, MVT::i1),
Cond == ISD::SETEQ ? ISD::SETNE : ISD::SETEQ);
SDValue C = DAG.getConstant(C1.trunc(MinBits), dl, MinVT);
return DAG.getSetCC(dl, VT, Trunc, C, Cond);
}
// If truncating the setcc operands is not desirable, we can still
// simplify the expression in some cases:
// setcc ([sz]ext (setcc x, y, cc)), 0, setne) -> setcc (x, y, cc)
// setcc ([sz]ext (setcc x, y, cc)), 0, seteq) -> setcc (x, y, inv(cc))
// setcc (zext (setcc x, y, cc)), 1, setne) -> setcc (x, y, inv(cc))
// setcc (zext (setcc x, y, cc)), 1, seteq) -> setcc (x, y, cc)
// setcc (sext (setcc x, y, cc)), -1, setne) -> setcc (x, y, inv(cc))
// setcc (sext (setcc x, y, cc)), -1, seteq) -> setcc (x, y, cc)
SDValue TopSetCC = N0->getOperand(0);
unsigned N0Opc = N0->getOpcode();
bool SExt = (N0Opc == ISD::SIGN_EXTEND);
if (TopSetCC.getValueType() == MVT::i1 && VT == MVT::i1 &&
TopSetCC.getOpcode() == ISD::SETCC &&
(N0Opc == ISD::ZERO_EXTEND || N0Opc == ISD::SIGN_EXTEND) &&
(isConstFalseVal(N1C) ||
isExtendedTrueVal(N1C, N0->getValueType(0), SExt))) {
bool Inverse = (N1C->isZero() && Cond == ISD::SETEQ) ||
(!N1C->isZero() && Cond == ISD::SETNE);
if (!Inverse)
return TopSetCC;
ISD::CondCode InvCond = ISD::getSetCCInverse(
cast<CondCodeSDNode>(TopSetCC.getOperand(2))->get(),
TopSetCC.getOperand(0).getValueType());
return DAG.getSetCC(dl, VT, TopSetCC.getOperand(0),
TopSetCC.getOperand(1),
InvCond);
}
}
}
// If the LHS is '(and load, const)', the RHS is 0, the test is for
// equality or unsigned, and all 1 bits of the const are in the same
// partial word, see if we can shorten the load.
if (DCI.isBeforeLegalize() &&
!ISD::isSignedIntSetCC(Cond) &&
N0.getOpcode() == ISD::AND && C1 == 0 &&
N0.getNode()->hasOneUse() &&
isa<LoadSDNode>(N0.getOperand(0)) &&
N0.getOperand(0).getNode()->hasOneUse() &&
isa<ConstantSDNode>(N0.getOperand(1))) {
LoadSDNode *Lod = cast<LoadSDNode>(N0.getOperand(0));
APInt bestMask;
unsigned bestWidth = 0, bestOffset = 0;
if (Lod->isSimple() && Lod->isUnindexed()) {
unsigned origWidth = N0.getValueSizeInBits();
unsigned maskWidth = origWidth;
// We can narrow (e.g.) 16-bit extending loads on 32-bit target to
// 8 bits, but have to be careful...
if (Lod->getExtensionType() != ISD::NON_EXTLOAD)
origWidth = Lod->getMemoryVT().getSizeInBits();
const APInt &Mask = N0.getConstantOperandAPInt(1);
for (unsigned width = origWidth / 2; width>=8; width /= 2) {
APInt newMask = APInt::getLowBitsSet(maskWidth, width);
for (unsigned offset=0; offset<origWidth/width; offset++) {
if (Mask.isSubsetOf(newMask)) {
if (Layout.isLittleEndian())
bestOffset = (uint64_t)offset * (width/8);
else
bestOffset = (origWidth/width - offset - 1) * (width/8);
bestMask = Mask.lshr(offset * (width/8) * 8);
bestWidth = width;
break;
}
newMask <<= width;
}
}
}
if (bestWidth) {
EVT newVT = EVT::getIntegerVT(*DAG.getContext(), bestWidth);
if (newVT.isRound() &&
shouldReduceLoadWidth(Lod, ISD::NON_EXTLOAD, newVT)) {
SDValue Ptr = Lod->getBasePtr();
if (bestOffset != 0)
Ptr =
DAG.getMemBasePlusOffset(Ptr, TypeSize::Fixed(bestOffset), dl);
SDValue NewLoad =
DAG.getLoad(newVT, dl, Lod->getChain(), Ptr,
Lod->getPointerInfo().getWithOffset(bestOffset),
Lod->getOriginalAlign());
return DAG.getSetCC(dl, VT,
DAG.getNode(ISD::AND, dl, newVT, NewLoad,
DAG.getConstant(bestMask.trunc(bestWidth),
dl, newVT)),
DAG.getConstant(0LL, dl, newVT), Cond);
}
}
}
// If the LHS is a ZERO_EXTEND, perform the comparison on the input.
if (N0.getOpcode() == ISD::ZERO_EXTEND) {
unsigned InSize = N0.getOperand(0).getValueSizeInBits();
// If the comparison constant has bits in the upper part, the
// zero-extended value could never match.
if (C1.intersects(APInt::getHighBitsSet(C1.getBitWidth(),
C1.getBitWidth() - InSize))) {
switch (Cond) {
case ISD::SETUGT:
case ISD::SETUGE:
case ISD::SETEQ:
return DAG.getConstant(0, dl, VT);
case ISD::SETULT:
case ISD::SETULE:
case ISD::SETNE:
return DAG.getConstant(1, dl, VT);
case ISD::SETGT:
case ISD::SETGE:
// True if the sign bit of C1 is set.
return DAG.getConstant(C1.isNegative(), dl, VT);
case ISD::SETLT:
case ISD::SETLE:
// True if the sign bit of C1 isn't set.
return DAG.getConstant(C1.isNonNegative(), dl, VT);
default:
break;
}
}
// Otherwise, we can perform the comparison with the low bits.
switch (Cond) {
case ISD::SETEQ:
case ISD::SETNE:
case ISD::SETUGT:
case ISD::SETUGE:
case ISD::SETULT:
case ISD::SETULE: {
EVT newVT = N0.getOperand(0).getValueType();
if (DCI.isBeforeLegalizeOps() ||
(isOperationLegal(ISD::SETCC, newVT) &&
isCondCodeLegal(Cond, newVT.getSimpleVT()))) {
EVT NewSetCCVT = getSetCCResultType(Layout, *DAG.getContext(), newVT);
SDValue NewConst = DAG.getConstant(C1.trunc(InSize), dl, newVT);
SDValue NewSetCC = DAG.getSetCC(dl, NewSetCCVT, N0.getOperand(0),
NewConst, Cond);
return DAG.getBoolExtOrTrunc(NewSetCC, dl, VT, N0.getValueType());
}
break;
}
default:
break; // todo, be more careful with signed comparisons
}
} else if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG &&
(Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
!isSExtCheaperThanZExt(cast<VTSDNode>(N0.getOperand(1))->getVT(),
OpVT)) {
EVT ExtSrcTy = cast<VTSDNode>(N0.getOperand(1))->getVT();
unsigned ExtSrcTyBits = ExtSrcTy.getSizeInBits();
EVT ExtDstTy = N0.getValueType();
unsigned ExtDstTyBits = ExtDstTy.getSizeInBits();
// If the constant doesn't fit into the number of bits for the source of
// the sign extension, it is impossible for both sides to be equal.
if (C1.getMinSignedBits() > ExtSrcTyBits)
return DAG.getBoolConstant(Cond == ISD::SETNE, dl, VT, OpVT);
assert(ExtDstTy == N0.getOperand(0).getValueType() &&
ExtDstTy != ExtSrcTy && "Unexpected types!");
APInt Imm = APInt::getLowBitsSet(ExtDstTyBits, ExtSrcTyBits);
SDValue ZextOp = DAG.getNode(ISD::AND, dl, ExtDstTy, N0.getOperand(0),
DAG.getConstant(Imm, dl, ExtDstTy));
if (!DCI.isCalledByLegalizer())
DCI.AddToWorklist(ZextOp.getNode());
// Otherwise, make this a use of a zext.
return DAG.getSetCC(dl, VT, ZextOp,
DAG.getConstant(C1 & Imm, dl, ExtDstTy), Cond);
} else if ((N1C->isZero() || N1C->isOne()) &&
(Cond == ISD::SETEQ || Cond == ISD::SETNE)) {
// SETCC (SETCC), [0|1], [EQ|NE] -> SETCC
if (N0.getOpcode() == ISD::SETCC &&
isTypeLegal(VT) && VT.bitsLE(N0.getValueType()) &&
(N0.getValueType() == MVT::i1 ||
getBooleanContents(N0.getOperand(0).getValueType()) ==
ZeroOrOneBooleanContent)) {
bool TrueWhenTrue = (Cond == ISD::SETEQ) ^ (!N1C->isOne());
if (TrueWhenTrue)
return DAG.getNode(ISD::TRUNCATE, dl, VT, N0);
// Invert the condition.
ISD::CondCode CC = cast<CondCodeSDNode>(N0.getOperand(2))->get();
CC = ISD::getSetCCInverse(CC, N0.getOperand(0).getValueType());
if (DCI.isBeforeLegalizeOps() ||
isCondCodeLegal(CC, N0.getOperand(0).getSimpleValueType()))
return DAG.getSetCC(dl, VT, N0.getOperand(0), N0.getOperand(1), CC);
}
if ((N0.getOpcode() == ISD::XOR ||
(N0.getOpcode() == ISD::AND &&
N0.getOperand(0).getOpcode() == ISD::XOR &&
N0.getOperand(1) == N0.getOperand(0).getOperand(1))) &&
isOneConstant(N0.getOperand(1))) {
// If this is (X^1) == 0/1, swap the RHS and eliminate the xor. We
// can only do this if the top bits are known zero.
unsigned BitWidth = N0.getValueSizeInBits();
if (DAG.MaskedValueIsZero(N0,
APInt::getHighBitsSet(BitWidth,
BitWidth-1))) {
// Okay, get the un-inverted input value.
SDValue Val;
if (N0.getOpcode() == ISD::XOR) {
Val = N0.getOperand(0);
} else {
assert(N0.getOpcode() == ISD::AND &&
N0.getOperand(0).getOpcode() == ISD::XOR);
// ((X^1)&1)^1 -> X & 1
Val = DAG.getNode(ISD::AND, dl, N0.getValueType(),
N0.getOperand(0).getOperand(0),
N0.getOperand(1));
}
return DAG.getSetCC(dl, VT, Val, N1,
Cond == ISD::SETEQ ? ISD::SETNE : ISD::SETEQ);
}
} else if (N1C->isOne()) {
SDValue Op0 = N0;
if (Op0.getOpcode() == ISD::TRUNCATE)
Op0 = Op0.getOperand(0);
if ((Op0.getOpcode() == ISD::XOR) &&
Op0.getOperand(0).getOpcode() == ISD::SETCC &&
Op0.getOperand(1).getOpcode() == ISD::SETCC) {
SDValue XorLHS = Op0.getOperand(0);
SDValue XorRHS = Op0.getOperand(1);
// Ensure that the input setccs return an i1 type or 0/1 value.
if (Op0.getValueType() == MVT::i1 ||
(getBooleanContents(XorLHS.getOperand(0).getValueType()) ==
ZeroOrOneBooleanContent &&
getBooleanContents(XorRHS.getOperand(0).getValueType()) ==
ZeroOrOneBooleanContent)) {
// (xor (setcc), (setcc)) == / != 1 -> (setcc) != / == (setcc)
Cond = (Cond == ISD::SETEQ) ? ISD::SETNE : ISD::SETEQ;
return DAG.getSetCC(dl, VT, XorLHS, XorRHS, Cond);
}
}
if (Op0.getOpcode() == ISD::AND && isOneConstant(Op0.getOperand(1))) {
// If this is (X&1) == / != 1, normalize it to (X&1) != / == 0.
if (Op0.getValueType().bitsGT(VT))
Op0 = DAG.getNode(ISD::AND, dl, VT,
DAG.getNode(ISD::TRUNCATE, dl, VT, Op0.getOperand(0)),
DAG.getConstant(1, dl, VT));
else if (Op0.getValueType().bitsLT(VT))
Op0 = DAG.getNode(ISD::AND, dl, VT,
DAG.getNode(ISD::ANY_EXTEND, dl, VT, Op0.getOperand(0)),
DAG.getConstant(1, dl, VT));
return DAG.getSetCC(dl, VT, Op0,
DAG.getConstant(0, dl, Op0.getValueType()),
Cond == ISD::SETEQ ? ISD::SETNE : ISD::SETEQ);
}
if (Op0.getOpcode() == ISD::AssertZext &&
cast<VTSDNode>(Op0.getOperand(1))->getVT() == MVT::i1)
return DAG.getSetCC(dl, VT, Op0,
DAG.getConstant(0, dl, Op0.getValueType()),
Cond == ISD::SETEQ ? ISD::SETNE : ISD::SETEQ);
}
}
// Given:
// icmp eq/ne (urem %x, %y), 0
// Iff %x has 0 or 1 bits set, and %y has at least 2 bits set, omit 'urem':
// icmp eq/ne %x, 0
if (N0.getOpcode() == ISD::UREM && N1C->isZero() &&
(Cond == ISD::SETEQ || Cond == ISD::SETNE)) {
KnownBits XKnown = DAG.computeKnownBits(N0.getOperand(0));
KnownBits YKnown = DAG.computeKnownBits(N0.getOperand(1));
if (XKnown.countMaxPopulation() == 1 && YKnown.countMinPopulation() >= 2)
return DAG.getSetCC(dl, VT, N0.getOperand(0), N1, Cond);
}
// Fold set_cc seteq (ashr X, BW-1), -1 -> set_cc setlt X, 0
// and set_cc setne (ashr X, BW-1), -1 -> set_cc setge X, 0
if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
N0.getOpcode() == ISD::SRA && isa<ConstantSDNode>(N0.getOperand(1)) &&
N0.getConstantOperandAPInt(1) == OpVT.getScalarSizeInBits() - 1 &&
N1C && N1C->isAllOnes()) {
return DAG.getSetCC(dl, VT, N0.getOperand(0),
DAG.getConstant(0, dl, OpVT),
Cond == ISD::SETEQ ? ISD::SETLT : ISD::SETGE);
}
if (SDValue V =
optimizeSetCCOfSignedTruncationCheck(VT, N0, N1, Cond, DCI, dl))
return V;
}
// These simplifications apply to splat vectors as well.
// TODO: Handle more splat vector cases.
if (auto *N1C = isConstOrConstSplat(N1)) {
const APInt &C1 = N1C->getAPIntValue();
APInt MinVal, MaxVal;
unsigned OperandBitSize = N1C->getValueType(0).getScalarSizeInBits();
if (ISD::isSignedIntSetCC(Cond)) {
MinVal = APInt::getSignedMinValue(OperandBitSize);
MaxVal = APInt::getSignedMaxValue(OperandBitSize);
} else {
MinVal = APInt::getMinValue(OperandBitSize);
MaxVal = APInt::getMaxValue(OperandBitSize);
}
// Canonicalize GE/LE comparisons to use GT/LT comparisons.
if (Cond == ISD::SETGE || Cond == ISD::SETUGE) {
// X >= MIN --> true
if (C1 == MinVal)
return DAG.getBoolConstant(true, dl, VT, OpVT);
if (!VT.isVector()) { // TODO: Support this for vectors.
// X >= C0 --> X > (C0 - 1)
APInt C = C1 - 1;
ISD::CondCode NewCC = (Cond == ISD::SETGE) ? ISD::SETGT : ISD::SETUGT;
if ((DCI.isBeforeLegalizeOps() ||
isCondCodeLegal(NewCC, VT.getSimpleVT())) &&
(!N1C->isOpaque() || (C.getBitWidth() <= 64 &&
isLegalICmpImmediate(C.getSExtValue())))) {
return DAG.getSetCC(dl, VT, N0,
DAG.getConstant(C, dl, N1.getValueType()),
NewCC);
}
}
}
if (Cond == ISD::SETLE || Cond == ISD::SETULE) {
// X <= MAX --> true
if (C1 == MaxVal)
return DAG.getBoolConstant(true, dl, VT, OpVT);
// X <= C0 --> X < (C0 + 1)
if (!VT.isVector()) { // TODO: Support this for vectors.
APInt C = C1 + 1;
ISD::CondCode NewCC = (Cond == ISD::SETLE) ? ISD::SETLT : ISD::SETULT;
if ((DCI.isBeforeLegalizeOps() ||
isCondCodeLegal(NewCC, VT.getSimpleVT())) &&
(!N1C->isOpaque() || (C.getBitWidth() <= 64 &&
isLegalICmpImmediate(C.getSExtValue())))) {
return DAG.getSetCC(dl, VT, N0,
DAG.getConstant(C, dl, N1.getValueType()),
NewCC);
}
}
}
if (Cond == ISD::SETLT || Cond == ISD::SETULT) {
if (C1 == MinVal)
return DAG.getBoolConstant(false, dl, VT, OpVT); // X < MIN --> false
// TODO: Support this for vectors after legalize ops.
if (!VT.isVector() || DCI.isBeforeLegalizeOps()) {
// Canonicalize setlt X, Max --> setne X, Max
if (C1 == MaxVal)
return DAG.getSetCC(dl, VT, N0, N1, ISD::SETNE);
// If we have setult X, 1, turn it into seteq X, 0
if (C1 == MinVal+1)
return DAG.getSetCC(dl, VT, N0,
DAG.getConstant(MinVal, dl, N0.getValueType()),
ISD::SETEQ);
}
}
if (Cond == ISD::SETGT || Cond == ISD::SETUGT) {
if (C1 == MaxVal)
return DAG.getBoolConstant(false, dl, VT, OpVT); // X > MAX --> false
// TODO: Support this for vectors after legalize ops.
if (!VT.isVector() || DCI.isBeforeLegalizeOps()) {
// Canonicalize setgt X, Min --> setne X, Min
if (C1 == MinVal)
return DAG.getSetCC(dl, VT, N0, N1, ISD::SETNE);
// If we have setugt X, Max-1, turn it into seteq X, Max
if (C1 == MaxVal-1)
return DAG.getSetCC(dl, VT, N0,
DAG.getConstant(MaxVal, dl, N0.getValueType()),
ISD::SETEQ);
}
}
if (Cond == ISD::SETEQ || Cond == ISD::SETNE) {
// (X & (C l>>/<< Y)) ==/!= 0 --> ((X <</l>> Y) & C) ==/!= 0
if (C1.isZero())
if (SDValue CC = optimizeSetCCByHoistingAndByConstFromLogicalShift(
VT, N0, N1, Cond, DCI, dl))
return CC;
// For all/any comparisons, replace or(x,shl(y,bw/2)) with and/or(x,y).
// For example, when high 32-bits of i64 X are known clear:
// all bits clear: (X | (Y<<32)) == 0 --> (X | Y) == 0
// all bits set: (X | (Y<<32)) == -1 --> (X & Y) == -1
bool CmpZero = N1C->getAPIntValue().isZero();
bool CmpNegOne = N1C->getAPIntValue().isAllOnes();
if ((CmpZero || CmpNegOne) && N0.hasOneUse()) {
// Match or(lo,shl(hi,bw/2)) pattern.
auto IsConcat = [&](SDValue V, SDValue &Lo, SDValue &Hi) {
unsigned EltBits = V.getScalarValueSizeInBits();
if (V.getOpcode() != ISD::OR || (EltBits % 2) != 0)
return false;
SDValue LHS = V.getOperand(0);
SDValue RHS = V.getOperand(1);
APInt HiBits = APInt::getHighBitsSet(EltBits, EltBits / 2);
// Unshifted element must have zero upperbits.
if (RHS.getOpcode() == ISD::SHL &&
isa<ConstantSDNode>(RHS.getOperand(1)) &&
RHS.getConstantOperandAPInt(1) == (EltBits / 2) &&
DAG.MaskedValueIsZero(LHS, HiBits)) {
Lo = LHS;
Hi = RHS.getOperand(0);
return true;
}
if (LHS.getOpcode() == ISD::SHL &&
isa<ConstantSDNode>(LHS.getOperand(1)) &&
LHS.getConstantOperandAPInt(1) == (EltBits / 2) &&
DAG.MaskedValueIsZero(RHS, HiBits)) {
Lo = RHS;
Hi = LHS.getOperand(0);
return true;
}
return false;
};
auto MergeConcat = [&](SDValue Lo, SDValue Hi) {
unsigned EltBits = N0.getScalarValueSizeInBits();
unsigned HalfBits = EltBits / 2;
APInt HiBits = APInt::getHighBitsSet(EltBits, HalfBits);
SDValue LoBits = DAG.getConstant(~HiBits, dl, OpVT);
SDValue HiMask = DAG.getNode(ISD::AND, dl, OpVT, Hi, LoBits);
SDValue NewN0 =
DAG.getNode(CmpZero ? ISD::OR : ISD::AND, dl, OpVT, Lo, HiMask);
SDValue NewN1 = CmpZero ? DAG.getConstant(0, dl, OpVT) : LoBits;
return DAG.getSetCC(dl, VT, NewN0, NewN1, Cond);
};
SDValue Lo, Hi;
if (IsConcat(N0, Lo, Hi))
return MergeConcat(Lo, Hi);
if (N0.getOpcode() == ISD::AND || N0.getOpcode() == ISD::OR) {
SDValue Lo0, Lo1, Hi0, Hi1;
if (IsConcat(N0.getOperand(0), Lo0, Hi0) &&
IsConcat(N0.getOperand(1), Lo1, Hi1)) {
return MergeConcat(DAG.getNode(N0.getOpcode(), dl, OpVT, Lo0, Lo1),
DAG.getNode(N0.getOpcode(), dl, OpVT, Hi0, Hi1));
}
}
}
}
// If we have "setcc X, C0", check to see if we can shrink the immediate
// by changing cc.
// TODO: Support this for vectors after legalize ops.
if (!VT.isVector() || DCI.isBeforeLegalizeOps()) {
// SETUGT X, SINTMAX -> SETLT X, 0
// SETUGE X, SINTMIN -> SETLT X, 0
if ((Cond == ISD::SETUGT && C1.isMaxSignedValue()) ||
(Cond == ISD::SETUGE && C1.isMinSignedValue()))
return DAG.getSetCC(dl, VT, N0,
DAG.getConstant(0, dl, N1.getValueType()),
ISD::SETLT);
// SETULT X, SINTMIN -> SETGT X, -1
// SETULE X, SINTMAX -> SETGT X, -1
if ((Cond == ISD::SETULT && C1.isMinSignedValue()) ||
(Cond == ISD::SETULE && C1.isMaxSignedValue()))
return DAG.getSetCC(dl, VT, N0,
DAG.getAllOnesConstant(dl, N1.getValueType()),
ISD::SETGT);
}
}
// Back to non-vector simplifications.
// TODO: Can we do these for vector splats?
if (auto *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
const TargetLowering &TLI = DAG.getTargetLoweringInfo();
const APInt &C1 = N1C->getAPIntValue();
EVT ShValTy = N0.getValueType();
// Fold bit comparisons when we can. This will result in an
// incorrect value when boolean false is negative one, unless
// the bitsize is 1 in which case the false value is the same
// in practice regardless of the representation.
if ((VT.getSizeInBits() == 1 ||
getBooleanContents(N0.getValueType()) == ZeroOrOneBooleanContent) &&
(Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
(VT == ShValTy || (isTypeLegal(VT) && VT.bitsLE(ShValTy))) &&
N0.getOpcode() == ISD::AND) {
if (auto *AndRHS = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
EVT ShiftTy =
getShiftAmountTy(ShValTy, Layout, !DCI.isBeforeLegalize());
if (Cond == ISD::SETNE && C1 == 0) {// (X & 8) != 0 --> (X & 8) >> 3
// Perform the xform if the AND RHS is a single bit.
unsigned ShCt = AndRHS->getAPIntValue().logBase2();
if (AndRHS->getAPIntValue().isPowerOf2() &&
!TLI.shouldAvoidTransformToShift(ShValTy, ShCt)) {
return DAG.getNode(ISD::TRUNCATE, dl, VT,
DAG.getNode(ISD::SRL, dl, ShValTy, N0,
DAG.getConstant(ShCt, dl, ShiftTy)));
}
} else if (Cond == ISD::SETEQ && C1 == AndRHS->getAPIntValue()) {
// (X & 8) == 8 --> (X & 8) >> 3
// Perform the xform if C1 is a single bit.
unsigned ShCt = C1.logBase2();
if (C1.isPowerOf2() &&
!TLI.shouldAvoidTransformToShift(ShValTy, ShCt)) {
return DAG.getNode(ISD::TRUNCATE, dl, VT,
DAG.getNode(ISD::SRL, dl, ShValTy, N0,
DAG.getConstant(ShCt, dl, ShiftTy)));
}
}
}
}
if (C1.getMinSignedBits() <= 64 &&
!isLegalICmpImmediate(C1.getSExtValue())) {
EVT ShiftTy = getShiftAmountTy(ShValTy, Layout, !DCI.isBeforeLegalize());
// (X & -256) == 256 -> (X >> 8) == 1
if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
N0.getOpcode() == ISD::AND && N0.hasOneUse()) {
if (auto *AndRHS = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
const APInt &AndRHSC = AndRHS->getAPIntValue();
if (AndRHSC.isNegatedPowerOf2() && (AndRHSC & C1) == C1) {
unsigned ShiftBits = AndRHSC.countTrailingZeros();
if (!TLI.shouldAvoidTransformToShift(ShValTy, ShiftBits)) {
SDValue Shift =
DAG.getNode(ISD::SRL, dl, ShValTy, N0.getOperand(0),
DAG.getConstant(ShiftBits, dl, ShiftTy));
SDValue CmpRHS = DAG.getConstant(C1.lshr(ShiftBits), dl, ShValTy);
return DAG.getSetCC(dl, VT, Shift, CmpRHS, Cond);
}
}
}
} else if (Cond == ISD::SETULT || Cond == ISD::SETUGE ||
Cond == ISD::SETULE || Cond == ISD::SETUGT) {
bool AdjOne = (Cond == ISD::SETULE || Cond == ISD::SETUGT);
// X < 0x100000000 -> (X >> 32) < 1
// X >= 0x100000000 -> (X >> 32) >= 1
// X <= 0x0ffffffff -> (X >> 32) < 1
// X > 0x0ffffffff -> (X >> 32) >= 1
unsigned ShiftBits;
APInt NewC = C1;
ISD::CondCode NewCond = Cond;
if (AdjOne) {
ShiftBits = C1.countTrailingOnes();
NewC = NewC + 1;
NewCond = (Cond == ISD::SETULE) ? ISD::SETULT : ISD::SETUGE;
} else {
ShiftBits = C1.countTrailingZeros();
}
NewC.lshrInPlace(ShiftBits);
if (ShiftBits && NewC.getMinSignedBits() <= 64 &&
isLegalICmpImmediate(NewC.getSExtValue()) &&
!TLI.shouldAvoidTransformToShift(ShValTy, ShiftBits)) {
SDValue Shift = DAG.getNode(ISD::SRL, dl, ShValTy, N0,
DAG.getConstant(ShiftBits, dl, ShiftTy));
SDValue CmpRHS = DAG.getConstant(NewC, dl, ShValTy);
return DAG.getSetCC(dl, VT, Shift, CmpRHS, NewCond);
}
}
}
}
if (!isa<ConstantFPSDNode>(N0) && isa<ConstantFPSDNode>(N1)) {
auto *CFP = cast<ConstantFPSDNode>(N1);
assert(!CFP->getValueAPF().isNaN() && "Unexpected NaN value");
// Otherwise, we know the RHS is not a NaN. Simplify the node to drop the
// constant if knowing that the operand is non-nan is enough. We prefer to
// have SETO(x,x) instead of SETO(x, 0.0) because this avoids having to
// materialize 0.0.
if (Cond == ISD::SETO || Cond == ISD::SETUO)
return DAG.getSetCC(dl, VT, N0, N0, Cond);
// setcc (fneg x), C -> setcc swap(pred) x, -C
if (N0.getOpcode() == ISD::FNEG) {
ISD::CondCode SwapCond = ISD::getSetCCSwappedOperands(Cond);
if (DCI.isBeforeLegalizeOps() ||
isCondCodeLegal(SwapCond, N0.getSimpleValueType())) {
SDValue NegN1 = DAG.getNode(ISD::FNEG, dl, N0.getValueType(), N1);
return DAG.getSetCC(dl, VT, N0.getOperand(0), NegN1, SwapCond);
}
}
// If the condition is not legal, see if we can find an equivalent one
// which is legal.
if (!isCondCodeLegal(Cond, N0.getSimpleValueType())) {
// If the comparison was an awkward floating-point == or != and one of
// the comparison operands is infinity or negative infinity, convert the
// condition to a less-awkward <= or >=.
if (CFP->getValueAPF().isInfinity()) {
bool IsNegInf = CFP->getValueAPF().isNegative();
ISD::CondCode NewCond = ISD::SETCC_INVALID;
switch (Cond) {
case ISD::SETOEQ: NewCond = IsNegInf ? ISD::SETOLE : ISD::SETOGE; break;
case ISD::SETUEQ: NewCond = IsNegInf ? ISD::SETULE : ISD::SETUGE; break;
case ISD::SETUNE: NewCond = IsNegInf ? ISD::SETUGT : ISD::SETULT; break;
case ISD::SETONE: NewCond = IsNegInf ? ISD::SETOGT : ISD::SETOLT; break;
default: break;
}
if (NewCond != ISD::SETCC_INVALID &&
isCondCodeLegal(NewCond, N0.getSimpleValueType()))
return DAG.getSetCC(dl, VT, N0, N1, NewCond);
}
}
}
if (N0 == N1) {
// The sext(setcc()) => setcc() optimization relies on the appropriate
// constant being emitted.
assert(!N0.getValueType().isInteger() &&
"Integer types should be handled by FoldSetCC");
bool EqTrue = ISD::isTrueWhenEqual(Cond);
unsigned UOF = ISD::getUnorderedFlavor(Cond);
if (UOF == 2) // FP operators that are undefined on NaNs.
return DAG.getBoolConstant(EqTrue, dl, VT, OpVT);
if (UOF == unsigned(EqTrue))
return DAG.getBoolConstant(EqTrue, dl, VT, OpVT);
// Otherwise, we can't fold it. However, we can simplify it to SETUO/SETO
// if it is not already.
ISD::CondCode NewCond = UOF == 0 ? ISD::SETO : ISD::SETUO;
if (NewCond != Cond &&
(DCI.isBeforeLegalizeOps() ||
isCondCodeLegal(NewCond, N0.getSimpleValueType())))
return DAG.getSetCC(dl, VT, N0, N1, NewCond);
}
if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
N0.getValueType().isInteger()) {
if (N0.getOpcode() == ISD::ADD || N0.getOpcode() == ISD::SUB ||
N0.getOpcode() == ISD::XOR) {
// Simplify (X+Y) == (X+Z) --> Y == Z
if (N0.getOpcode() == N1.getOpcode()) {
if (N0.getOperand(0) == N1.getOperand(0))
return DAG.getSetCC(dl, VT, N0.getOperand(1), N1.getOperand(1), Cond);
if (N0.getOperand(1) == N1.getOperand(1))
return DAG.getSetCC(dl, VT, N0.getOperand(0), N1.getOperand(0), Cond);
if (isCommutativeBinOp(N0.getOpcode())) {
// If X op Y == Y op X, try other combinations.
if (N0.getOperand(0) == N1.getOperand(1))
return DAG.getSetCC(dl, VT, N0.getOperand(1), N1.getOperand(0),
Cond);
if (N0.getOperand(1) == N1.getOperand(0))
return DAG.getSetCC(dl, VT, N0.getOperand(0), N1.getOperand(1),
Cond);
}
}
// If RHS is a legal immediate value for a compare instruction, we need
// to be careful about increasing register pressure needlessly.
bool LegalRHSImm = false;
if (auto *RHSC = dyn_cast<ConstantSDNode>(N1)) {
if (auto *LHSR = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
// Turn (X+C1) == C2 --> X == C2-C1
if (N0.getOpcode() == ISD::ADD && N0.getNode()->hasOneUse()) {
return DAG.getSetCC(dl, VT, N0.getOperand(0),
DAG.getConstant(RHSC->getAPIntValue()-
LHSR->getAPIntValue(),
dl, N0.getValueType()), Cond);
}
// Turn (X^C1) == C2 into X == C1^C2 iff X&~C1 = 0.
if (N0.getOpcode() == ISD::XOR)
// If we know that all of the inverted bits are zero, don't bother
// performing the inversion.
if (DAG.MaskedValueIsZero(N0.getOperand(0), ~LHSR->getAPIntValue()))
return
DAG.getSetCC(dl, VT, N0.getOperand(0),
DAG.getConstant(LHSR->getAPIntValue() ^
RHSC->getAPIntValue(),
dl, N0.getValueType()),
Cond);
}
// Turn (C1-X) == C2 --> X == C1-C2
if (auto *SUBC = dyn_cast<ConstantSDNode>(N0.getOperand(0))) {
if (N0.getOpcode() == ISD::SUB && N0.getNode()->hasOneUse()) {
return
DAG.getSetCC(dl, VT, N0.getOperand(1),
DAG.getConstant(SUBC->getAPIntValue() -
RHSC->getAPIntValue(),
dl, N0.getValueType()),
Cond);
}
}
// Could RHSC fold directly into a compare?
if (RHSC->getValueType(0).getSizeInBits() <= 64)
LegalRHSImm = isLegalICmpImmediate(RHSC->getSExtValue());
}
// (X+Y) == X --> Y == 0 and similar folds.
// Don't do this if X is an immediate that can fold into a cmp
// instruction and X+Y has other uses. It could be an induction variable
// chain, and the transform would increase register pressure.
if (!LegalRHSImm || N0.hasOneUse())
if (SDValue V = foldSetCCWithBinOp(VT, N0, N1, Cond, dl, DCI))
return V;
}
if (N1.getOpcode() == ISD::ADD || N1.getOpcode() == ISD::SUB ||
N1.getOpcode() == ISD::XOR)
if (SDValue V = foldSetCCWithBinOp(VT, N1, N0, Cond, dl, DCI))
return V;
if (SDValue V = foldSetCCWithAnd(VT, N0, N1, Cond, dl, DCI))
return V;
}
// Fold remainder of division by a constant.
if ((N0.getOpcode() == ISD::UREM || N0.getOpcode() == ISD::SREM) &&
N0.hasOneUse() && (Cond == ISD::SETEQ || Cond == ISD::SETNE)) {
AttributeList Attr = DAG.getMachineFunction().getFunction().getAttributes();
// When division is cheap or optimizing for minimum size,
// fall through to DIVREM creation by skipping this fold.
if (!isIntDivCheap(VT, Attr) && !Attr.hasFnAttr(Attribute::MinSize)) {
if (N0.getOpcode() == ISD::UREM) {
if (SDValue Folded = buildUREMEqFold(VT, N0, N1, Cond, DCI, dl))
return Folded;
} else if (N0.getOpcode() == ISD::SREM) {
if (SDValue Folded = buildSREMEqFold(VT, N0, N1, Cond, DCI, dl))
return Folded;
}
}
}
// Fold away ALL boolean setcc's.
if (N0.getValueType().getScalarType() == MVT::i1 && foldBooleans) {
SDValue Temp;
switch (Cond) {
default: llvm_unreachable("Unknown integer setcc!");
case ISD::SETEQ: // X == Y -> ~(X^Y)
Temp = DAG.getNode(ISD::XOR, dl, OpVT, N0, N1);
N0 = DAG.getNOT(dl, Temp, OpVT);
if (!DCI.isCalledByLegalizer())
DCI.AddToWorklist(Temp.getNode());
break;
case ISD::SETNE: // X != Y --> (X^Y)
N0 = DAG.getNode(ISD::XOR, dl, OpVT, N0, N1);
break;
case ISD::SETGT: // X >s Y --> X == 0 & Y == 1 --> ~X & Y
case ISD::SETULT: // X <u Y --> X == 0 & Y == 1 --> ~X & Y
Temp = DAG.getNOT(dl, N0, OpVT);
N0 = DAG.getNode(ISD::AND, dl, OpVT, N1, Temp);
if (!DCI.isCalledByLegalizer())
DCI.AddToWorklist(Temp.getNode());
break;
case ISD::SETLT: // X <s Y --> X == 1 & Y == 0 --> ~Y & X
case ISD::SETUGT: // X >u Y --> X == 1 & Y == 0 --> ~Y & X
Temp = DAG.getNOT(dl, N1, OpVT);
N0 = DAG.getNode(ISD::AND, dl, OpVT, N0, Temp);
if (!DCI.isCalledByLegalizer())
DCI.AddToWorklist(Temp.getNode());
break;
case ISD::SETULE: // X <=u Y --> X == 0 | Y == 1 --> ~X | Y
case ISD::SETGE: // X >=s Y --> X == 0 | Y == 1 --> ~X | Y
Temp = DAG.getNOT(dl, N0, OpVT);
N0 = DAG.getNode(ISD::OR, dl, OpVT, N1, Temp);
if (!DCI.isCalledByLegalizer())
DCI.AddToWorklist(Temp.getNode());
break;
case ISD::SETUGE: // X >=u Y --> X == 1 | Y == 0 --> ~Y | X
case ISD::SETLE: // X <=s Y --> X == 1 | Y == 0 --> ~Y | X
Temp = DAG.getNOT(dl, N1, OpVT);
N0 = DAG.getNode(ISD::OR, dl, OpVT, N0, Temp);
break;
}
if (VT.getScalarType() != MVT::i1) {
if (!DCI.isCalledByLegalizer())
DCI.AddToWorklist(N0.getNode());
// FIXME: If running after legalize, we probably can't do this.
ISD::NodeType ExtendCode = getExtendForContent(getBooleanContents(OpVT));
N0 = DAG.getNode(ExtendCode, dl, VT, N0);
}
return N0;
}
// Could not fold it.
return SDValue();
}