23 using namespace PatternMatch;
25 #define DEBUG_TYPE "instcombine"
56 assert(
I.isBitwiseLogicOp() &&
"Unexpected opcode for bswap simplifying");
58 Value *OldLHS =
I.getOperand(0);
59 Value *OldRHS =
I.getOperand(1);
81 Value *BinOp =
Builder.CreateBinOp(
I.getOpcode(), NewLHS, NewRHS);
91 const APInt &Hi,
bool isSigned,
93 assert((isSigned ? Lo.slt(Hi) : Lo.ult(Hi)) &&
94 "Lo is not < Hi in range emission code!");
101 if (isSigned ? Lo.isMinSignedValue() : Lo.isMinValue()) {
111 return Builder.CreateICmp(Pred, VMinusLo, HiMinusLo);
158 const APInt *ConstA =
nullptr, *ConstB =
nullptr, *ConstC =
nullptr;
163 bool IsAPow2 = ConstA && ConstA->
isPowerOf2();
164 bool IsBPow2 = ConstB && ConstB->isPowerOf2();
165 unsigned MaskVal = 0;
166 if (ConstC && ConstC->isZero()) {
185 }
else if (ConstA && ConstC && ConstC->
isSubsetOf(*ConstA)) {
195 }
else if (ConstB && ConstC && ConstC->isSubsetOf(*ConstB)) {
256 Value *L11, *L12, *L21, *L22;
259 L21 = L22 = L1 =
nullptr;
284 if (R11 == L11 || R11 == L12 || R11 == L21 || R11 == L22) {
287 }
else if (R12 == L11 || R12 == L12 || R12 == L21 || R12 == L22) {
304 if (R11 == L11 || R11 == L12 || R11 == L21 || R11 == L22) {
309 }
else if (R12 == L11 || R12 == L12 || R12 == L21 || R12 == L22) {
328 if (R11 == L11 || R11 == L12 || R11 == L21 || R11 == L22) {
333 }
else if (R12 == L11 || R12 == L12 || R12 == L21 || R12 == L22) {
342 assert(Ok &&
"Failed to find AND on the right side of the RHS icmp.");
348 }
else if (L12 == A) {
351 }
else if (L21 == A) {
354 }
else if (L22 == A) {
432 return Builder.CreateICmp(NewCC, NewAnd, NewMaskedValue);
436 return (
C1->getValue() & C2->getValue()) ==
C1->getValue();
439 return (
C1->getValue() & C2->getValue()) == C2->getValue();
448 if (!IsSubSetOrEqual(BCst, DCst) && !IsSuperSetOrEqual(BCst, DCst))
460 if (IsSubSetOrEqual(BCst, DCst))
471 if (IsSuperSetOrEqual(BCst, DCst))
476 assert(IsSubSetOrEqual(BCst, DCst) &&
"Precondition due to above code");
494 "Expected equality predicates for masked type of icmps.");
524 Value *A =
nullptr, *
B =
nullptr, *
C =
nullptr, *
D =
nullptr, *
E =
nullptr;
531 "Expected equality predicates for masked type of icmps.");
532 unsigned LHSMask = MaskPair->first;
533 unsigned RHSMask = MaskPair->second;
534 unsigned Mask = LHSMask & RHSMask;
539 LHS,
RHS, IsAnd, A,
B,
C,
D,
E, PredL, PredR, LHSMask, RHSMask,
573 return Builder.CreateICmp(NewCC, NewAnd, Zero);
580 return Builder.CreateICmp(NewCC, NewAnd, NewOr);
587 return Builder.CreateICmp(NewCC, NewAnd2, A);
593 const APInt *ConstB, *ConstD;
603 APInt NewMask = *ConstB & *ConstD;
604 if (NewMask == *ConstB)
606 else if (NewMask == *ConstD)
615 APInt NewMask = *ConstB | *ConstD;
616 if (NewMask == *ConstB)
618 else if (NewMask == *ConstD)
633 const APInt *OldConstC, *OldConstE;
637 const APInt ConstC = PredL != NewCC ? *ConstB ^ *OldConstC : *OldConstC;
638 const APInt ConstE = PredR != NewCC ? *ConstD ^ *OldConstE : *OldConstE;
642 if (((*ConstB & *ConstD) & (ConstC ^ ConstE)).getBoolValue())
648 return Builder.CreateICmp(NewCC, NewAnd, NewOr2);
695 default:
return nullptr;
706 return Builder.CreateICmp(NewPred, Input, RangeEnd);
717 if (
LHS->getPredicate() != Pred ||
RHS->getPredicate() != Pred)
785 auto tryToMatchSignedTruncationCheck = [](
ICmpInst *ICmp,
Value *&
X,
786 APInt &SignBitMask) ->
bool {
803 if (tryToMatchSignedTruncationCheck(ICmp1, X1, HighestBit))
805 else if (tryToMatchSignedTruncationCheck(ICmp0, X1, HighestBit))
810 assert(HighestBit.
isPowerOf2() &&
"expected to be power of two (non-zero)");
814 APInt &UnsetBitsMask) ->
bool {
818 Pred,
X, UnsetBitsMask,
826 UnsetBitsMask = *
Mask;
835 if (!tryToDecompose(OtherICmp, X0, UnsetBitsMask))
838 assert(!UnsetBitsMask.
isZero() &&
"empty mask makes no sense.");
853 APInt SignBitsMask = ~(HighestBit - 1U);
860 if (!UnsetBitsMask.
isSubsetOf(SignBitsMask)) {
861 APInt OtherHighestBit = (~UnsetBitsMask) + 1U;
870 CxtI.
getName() +
".simplified");
935 auto IsKnownNonZero = [&](
Value *V) {
942 if (
match(UnsignedICmp,
947 if (!IsKnownNonZero(NonZero))
949 return IsKnownNonZero(NonZero);
958 IsAnd && GetKnownNonZeroAndOther(
B, A))
961 !IsAnd && GetKnownNonZeroAndOther(
B, A))
969 if (!
match(UnsignedICmp,
1013 unsigned NumOriginalBits =
X->getType()->getScalarSizeInBits();
1020 Shift->ule(NumOriginalBits - NumExtractedBits))
1021 return {{
Y, (unsigned)
Shift->getZExtValue(), NumExtractedBits}};
1022 return {{
X, 0, NumExtractedBits}};
1029 V =
Builder.CreateLShr(V,
P.StartBit);
1032 V =
Builder.CreateTrunc(V, TruncTy);
1052 if (!L0 || !R0 || !L1 || !R1)
1079 return Builder.CreateICmp(Pred, LValue, RValue);
1089 bool IsAnd = Logic.
getOpcode() == Instruction::And;
1090 assert((IsAnd || Logic.
getOpcode() == Instruction::Or) &&
"Wrong logic op");
1118 if (!SubstituteCmp) {
1123 SubstituteCmp =
Builder.CreateICmp(Pred1,
Y,
C);
1132 Value *InstCombinerImpl::foldAndOrOfICmpsUsingRanges(
ICmpInst *ICmp1,
1144 const APInt *Offset1 =
nullptr, *Offset2 =
nullptr;
1179 if (!LowerDiff.
isPowerOf2() || LowerDiff != UpperDiff ||
1200 bool IsAnd,
bool IsLogicalSelect) {
1201 Value *LHS0 =
LHS->getOperand(0), *LHS1 =
LHS->getOperand(1);
1202 Value *RHS0 =
RHS->getOperand(0), *RHS1 =
RHS->getOperand(1);
1205 if (LHS0 == RHS1 && RHS0 == LHS1) {
1225 if (LHS0 == RHS0 && LHS1 == RHS1) {
1228 unsigned NewPred = IsAnd ? FCmpCodeL & FCmpCodeR : FCmpCodeL | FCmpCodeR;
1234 FMF &=
RHS->getFastMathFlags();
1235 Builder.setFastMathFlags(FMF);
1241 if (!IsLogicalSelect &&
1254 return Builder.CreateFCmp(PredL, LHS0, RHS0);
1267 assert((Opcode == Instruction::And || Opcode == Instruction::Or) &&
1268 "Expecting and/or op for fcmp transform");
1288 Pred != NanPred ||
X->getType() !=
Y->getType())
1292 Pred != NanPred ||
X->getType() !=
Y->getType())
1298 if (
auto *NewFCmpInst = dyn_cast<FCmpInst>(NewFCmp)) {
1300 NewFCmpInst->copyIRFlags(Op0);
1301 NewFCmpInst->andIRFlags(BO10);
1312 assert((Opcode == Instruction::And || Opcode == Instruction::Or) &&
1313 "Trying to match De Morgan's Laws with something other than and/or");
1317 (Opcode == Instruction::And) ? Instruction::Or : Instruction::And;
1319 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
1326 Builder.CreateBinOp(FlippedOpcode, A,
B,
I.getName() +
".demorgan");
1345 bool InstCombinerImpl::shouldOptimizeCast(
CastInst *CI) {
1354 if (
const auto *PrecedingCI = dyn_cast<CastInst>(CastSrc))
1355 if (isEliminableCastPair(PrecedingCI, CI))
1380 if (ZextTruncC ==
C) {
1383 return new ZExtInst(NewOp, DestTy);
1390 if (SextTruncC ==
C) {
1393 return new SExtInst(NewOp, DestTy);
1402 auto LogicOpc =
I.getOpcode();
1403 assert(
I.isBitwiseLogicOp() &&
"Unexpected opcode for bitwise logic folding");
1405 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
1406 CastInst *Cast0 = dyn_cast<CastInst>(Op0);
1412 Type *DestTy =
I.getType();
1420 CastInst *Cast1 = dyn_cast<CastInst>(Op1);
1434 if (shouldOptimizeCast(Cast0) && shouldOptimizeCast(Cast1)) {
1435 Value *NewOp =
Builder.CreateBinOp(LogicOpc, Cast0Src, Cast1Src,
1441 if (LogicOpc == Instruction::Xor)
1446 ICmpInst *ICmp0 = dyn_cast<ICmpInst>(Cast0Src);
1447 ICmpInst *ICmp1 = dyn_cast<ICmpInst>(Cast1Src);
1448 if (ICmp0 && ICmp1) {
1450 foldAndOrOfICmps(ICmp0, ICmp1,
I, LogicOpc == Instruction::And))
1457 FCmpInst *FCmp0 = dyn_cast<FCmpInst>(Cast0Src);
1458 FCmpInst *FCmp1 = dyn_cast<FCmpInst>(Cast1Src);
1460 if (
Value *R = foldLogicOfFCmps(FCmp0, FCmp1, LogicOpc == Instruction::And))
1468 assert(
I.getOpcode() == Instruction::And);
1469 Value *Op0 =
I.getOperand(0);
1470 Value *Op1 =
I.getOperand(1);
1478 return BinaryOperator::CreateXor(A,
B);
1494 assert(
I.getOpcode() == Instruction::Or);
1495 Value *Op0 =
I.getOperand(0);
1496 Value *Op1 =
I.getOperand(1);
1521 return BinaryOperator::CreateXor(A,
B);
1541 Value *Op0 =
And.getOperand(0), *Op1 =
And.getOperand(1);
1555 if (!isa<VectorType>(Ty) && !shouldChangeType(Ty,
X->getType()))
1562 if (Opc == Instruction::LShr || Opc == Instruction::Shl)
1569 Value *NewBO = Opc == Instruction::Sub ?
Builder.CreateBinOp(Opc, NewC,
X)
1570 :
Builder.CreateBinOp(Opc,
X, NewC);
1579 assert(Opcode == Instruction::And || Opcode == Instruction::Or);
1583 (Opcode == Instruction::And) ? Instruction::Or : Instruction::And;
1585 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
1592 const auto matchNotOrAnd =
1593 [Opcode, FlippedOpcode](
Value *
Op,
auto m_A,
auto m_B,
auto m_C,
1594 Value *&
X,
bool CountUses =
false) ->
bool {
1595 if (CountUses && !
Op->hasOneUse())
1602 return !CountUses ||
X->hasOneUse();
1618 return (Opcode == Instruction::Or)
1619 ? BinaryOperator::CreateAnd(
Xor,
Builder.CreateNot(A))
1628 return (Opcode == Instruction::Or)
1629 ? BinaryOperator::CreateAnd(
Xor,
Builder.CreateNot(
B))
1638 Opcode,
Builder.CreateBinOp(FlippedOpcode,
B,
C), A));
1645 Opcode,
Builder.CreateBinOp(FlippedOpcode, A,
C),
B));
1651 if (Opcode == Instruction::Or && Op0->
hasOneUse() &&
1658 Value *
Or = cast<BinaryOperator>(
X)->getOperand(0);
1690 return (Opcode == Instruction::Or)
1692 : BinaryOperator::CreateOr(
Xor,
X);
1719 Type *Ty =
I.getType();
1722 SQ.getWithInstruction(&
I)))
1723 return replaceInstUsesWith(
I, V);
1725 if (SimplifyAssociativeOrCommutative(
I))
1736 if (SimplifyDemandedInstructionBits(
I))
1747 if (
Value *V = SimplifyUsingDistributiveLaws(
I))
1748 return replaceInstUsesWith(
I, V);
1751 return replaceInstUsesWith(
I, V);
1753 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
1772 return BinaryOperator::CreateXor(
And, NewC);
1783 APInt Together = *
C & *OrC;
1797 Value *NewRHS =
Builder.CreateAnd(
Y, Op1,
Y->getName() +
".masked");
1803 Value *NewLHS =
Builder.CreateAnd(
X, Op1,
X->getName() +
".masked");
1809 const APInt *ShiftC;
1816 return BinaryOperator::CreateLShr(Sext, ShAmtC);
1832 if ((*AddC & LowMask).
isZero())
1833 return BinaryOperator::CreateAnd(
X, Op1);
1839 if (Op0->
hasOneUse() &&
C->isPowerOf2() && (*AddC & (*
C - 1)) == 0) {
1840 assert((*
C & *AddC) != 0 &&
"Expected common bit");
1842 return BinaryOperator::CreateXor(NewAnd, Op1);
1849 switch (
B->getOpcode()) {
1850 case Instruction::Xor:
1851 case Instruction::Or:
1854 case Instruction::Sub:
1867 C->isIntN(
X->getType()->getScalarSizeInBits())) {
1868 unsigned XWidth =
X->getType()->getScalarSizeInBits();
1883 ICmpInst::Predicate::ICMP_EQ,
1886 X->getType()->getScalarSizeInBits())))) {
1887 auto *SExt =
Builder.CreateSExt(
X, Ty,
X->getName() +
".signext");
1888 auto *SanitizedSignMask = cast<Constant>(Op1);
1896 return BinaryOperator::CreateAnd(SExt, SanitizedSignMask);
1902 if (
I.getType()->isIntOrIntVectorTy(1)) {
1903 if (
auto *SI0 = dyn_cast<SelectInst>(Op0)) {
1905 foldAndOrOfSelectUsingImpliedCond(Op1, *SI0,
true))
1908 if (
auto *SI1 = dyn_cast<SelectInst>(Op1)) {
1910 foldAndOrOfSelectUsingImpliedCond(Op0, *SI1,
true))
1915 if (
Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(
I))
1925 return BinaryOperator::CreateAnd(Op0,
Builder.CreateNot(
B));
1928 return BinaryOperator::CreateAnd(Op1,
Builder.CreateNot(
B));
1932 return BinaryOperator::CreateAnd(Op0,
B);
1935 return BinaryOperator::CreateAnd(Op1,
B);
1940 if (Op1->hasOneUse() || isFreeToInvert(
C,
C->hasOneUse()))
1941 return BinaryOperator::CreateAnd(Op0,
Builder.CreateNot(
C));
1946 if (Op0->
hasOneUse() || isFreeToInvert(
C,
C->hasOneUse()))
1947 return BinaryOperator::CreateAnd(Op1,
Builder.CreateNot(
C));
1955 return BinaryOperator::CreateAnd(A,
B);
1963 return BinaryOperator::CreateAnd(A,
B);
1971 return BinaryOperator::CreateAnd(
Builder.CreateNot(A),
B);
1979 return BinaryOperator::CreateAnd(
Builder.CreateNot(A),
B);
1987 return replaceInstUsesWith(
I, Res);
1992 if (
auto *Cmp = dyn_cast<ICmpInst>(
X))
1993 if (
Value *Res = foldAndOrOfICmps(
LHS, Cmp,
I,
true))
1994 return replaceInstUsesWith(
I,
Builder.CreateAnd(Res,
Y));
1995 if (
auto *Cmp = dyn_cast<ICmpInst>(
Y))
1996 if (
Value *Res = foldAndOrOfICmps(
LHS, Cmp,
I,
true))
1997 return replaceInstUsesWith(
I,
Builder.CreateAnd(Res,
X));
2000 if (
auto *Cmp = dyn_cast<ICmpInst>(
X))
2001 if (
Value *Res = foldAndOrOfICmps(Cmp,
RHS,
I,
true))
2002 return replaceInstUsesWith(
I,
Builder.CreateAnd(Res,
Y));
2003 if (
auto *Cmp = dyn_cast<ICmpInst>(
Y))
2004 if (
Value *Res = foldAndOrOfICmps(Cmp,
RHS,
I,
true))
2005 return replaceInstUsesWith(
I,
Builder.CreateAnd(Res,
X));
2009 if (
FCmpInst *
LHS = dyn_cast<FCmpInst>(
I.getOperand(0)))
2010 if (
FCmpInst *
RHS = dyn_cast<FCmpInst>(
I.getOperand(1)))
2011 if (
Value *Res = foldLogicOfFCmps(
LHS,
RHS,
true))
2012 return replaceInstUsesWith(
I, Res);
2017 if (
Instruction *CastedAnd = foldCastedBitwiseLogic(
I))
2030 A->getType()->isIntOrIntVectorTy(1))
2033 A->getType()->isIntOrIntVectorTy(1))
2053 if (sinkNotIntoOtherHandOfAndOrOr(
I))
2058 Value *Start =
nullptr, *Step =
nullptr;
2060 return replaceInstUsesWith(
I,
Builder.CreateAnd(Start, Step));
2067 bool MatchBitReversals) {
2075 for (
auto *Inst : Insts)
2076 Worklist.push(Inst);
2084 unsigned Width =
Or.getType()->getScalarSizeInBits();
2093 Value *ShVal0, *ShVal1, *ShAmt0, *ShAmt1;
2100 if (Or0->
getOpcode() == BinaryOperator::LShr) {
2106 Or1->
getOpcode() == BinaryOperator::LShr &&
2107 "Illegal or(shift,shift) pair");
2113 const APInt *LI, *RI;
2138 if (ShVal0 != ShVal1)
2168 Value *ShAmt = matchShiftAmount(ShAmt0, ShAmt1,
Width);
2171 ShAmt = matchShiftAmount(ShAmt1, ShAmt0,
Width);
2177 Intrinsic::ID IID = IsFshl ? Intrinsic::fshl : Intrinsic::fshr;
2185 assert(
Or.getOpcode() == Instruction::Or &&
"bswap requires an 'or'");
2186 Value *Op0 =
Or.getOperand(0), *Op1 =
Or.getOperand(1);
2190 if ((
Width & 1) != 0)
2192 unsigned HalfWidth =
Width / 2;
2195 if (!isa<ZExtInst>(Op0))
2199 Value *LowerSrc, *ShlVal, *UpperSrc;
2212 NewUpper =
Builder.CreateShl(NewUpper, HalfWidth);
2215 return Builder.CreateCall(
F, BinOp);
2220 Value *LowerBSwap, *UpperBSwap;
2223 return ConcatIntrinsicCalls(Intrinsic::bswap, UpperBSwap, LowerBSwap);
2227 Value *LowerBRev, *UpperBRev;
2230 return ConcatIntrinsicCalls(Intrinsic::bitreverse, UpperBRev, LowerBRev);
2237 unsigned NumElts = cast<FixedVectorType>(
C1->getType())->getNumElements();
2238 for (
unsigned i = 0;
i != NumElts; ++
i) {
2241 if (!EltC1 || !EltC2)
2258 Type *Ty =
A->getType();
2274 if (
A->getType()->isIntOrIntVectorTy()) {
2276 if (NumSignBits ==
A->getType()->getScalarSizeInBits() &&
2295 Cond->getType()->isIntOrIntVectorTy(1)) {
2321 Cond->getType()->isIntOrIntVectorTy(1) &&
2335 Type *OrigType =
A->getType();
2338 if (
Value *
Cond = getSelectCondition(A,
B)) {
2343 Type *SelTy =
A->getType();
2344 if (
auto *VecTy = dyn_cast<VectorType>(
Cond->getType())) {
2346 unsigned Elts = VecTy->getElementCount().getKnownMinValue();
2350 Type *EltTy =
Builder.getIntNTy(SelEltSize / Elts);
2367 IsAnd ?
LHS->getInversePredicate() :
LHS->getPredicate();
2369 IsAnd ?
RHS->getInversePredicate() :
RHS->getPredicate();
2398 if (
Value *V = foldAndOrOfICmpsOfAndWithPow2(
LHS,
RHS, &BO, IsAnd))
2402 Value *LHS0 =
LHS->getOperand(0), *RHS0 =
RHS->getOperand(0);
2403 Value *LHS1 =
LHS->getOperand(1), *RHS1 =
RHS->getOperand(1);
2404 const APInt *LHSC =
nullptr, *RHSC =
nullptr;
2411 if (LHS0 == RHS1 && LHS1 == RHS0) {
2415 if (LHS0 == RHS0 && LHS1 == RHS1) {
2418 bool IsSigned =
LHS->isSigned() ||
RHS->isSigned();
2446 if (
Value *V = simplifyRangeCheck(
LHS,
RHS, !IsAnd))
2451 if (
Value *V = simplifyRangeCheck(
RHS,
LHS, !IsAnd))
2476 return Builder.CreateICmp(PredL, NewOr,
2491 const APInt *AndC, *SmallC =
nullptr, *BigC =
nullptr;
2505 if (SmallC && BigC) {
2511 if ((Low & *AndC).
isZero() && (Low & *BigC).
isZero()) {
2515 return Builder.CreateICmp(PredL, NewAnd, NewVal);
2520 return foldAndOrOfICmpsUsingRanges(
LHS,
RHS, IsAnd);
2528 SQ.getWithInstruction(&
I)))
2529 return replaceInstUsesWith(
I, V);
2531 if (SimplifyAssociativeOrCommutative(
I))
2542 if (SimplifyDemandedInstructionBits(
I))
2553 if (
Value *V = SimplifyUsingDistributiveLaws(
I))
2554 return replaceInstUsesWith(
I, V);
2557 return replaceInstUsesWith(
I, V);
2559 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
2560 Type *Ty =
I.getType();
2562 if (
auto *SI0 = dyn_cast<SelectInst>(Op0)) {
2564 foldAndOrOfSelectUsingImpliedCond(Op1, *SI0,
false))
2567 if (
auto *SI1 = dyn_cast<SelectInst>(Op1)) {
2569 foldAndOrOfSelectUsingImpliedCond(Op0, *SI1,
false))
2574 if (
Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(
I))
2577 if (
Instruction *BitOp = matchBSwapOrBitReverse(
I,
true,
2585 return replaceInstUsesWith(
I,
Concat);
2618 return BinaryOperator::CreateOr(
Builder.CreateAnd(
X, *C0),
B);
2621 return BinaryOperator::CreateOr(
Builder.CreateAnd(
X, *
C1), A);
2625 return BinaryOperator::CreateXor(
Builder.CreateAnd(
X, *C0),
B);
2628 return BinaryOperator::CreateXor(
Builder.CreateAnd(
X, *
C1), A);
2637 return BinaryOperator::CreateAnd(A, C01);
2644 return BinaryOperator::CreateAnd(
B, C01);
2648 const APInt *C2, *C3;
2654 return BinaryOperator::CreateAnd(
Or, C01);
2662 if (Op0->
hasOneUse() || Op1->hasOneUse()) {
2664 if (
Value *V = matchSelectFromAndOr(A,
C,
B,
D))
2665 return replaceInstUsesWith(
I, V);
2666 if (
Value *V = matchSelectFromAndOr(A,
C,
D,
B))
2667 return replaceInstUsesWith(
I, V);
2668 if (
Value *V = matchSelectFromAndOr(
C, A,
B,
D))
2669 return replaceInstUsesWith(
I, V);
2670 if (
Value *V = matchSelectFromAndOr(
C, A,
D,
B))
2671 return replaceInstUsesWith(
I, V);
2672 if (
Value *V = matchSelectFromAndOr(
B,
D, A,
C))
2673 return replaceInstUsesWith(
I, V);
2674 if (
Value *V = matchSelectFromAndOr(
B,
D,
C, A))
2675 return replaceInstUsesWith(
I, V);
2676 if (
Value *V = matchSelectFromAndOr(
D,
B, A,
C))
2677 return replaceInstUsesWith(
I, V);
2678 if (
Value *V = matchSelectFromAndOr(
D,
B,
C, A))
2679 return replaceInstUsesWith(
I, V);
2686 return BinaryOperator::CreateOr(Op0,
C);
2691 return BinaryOperator::CreateOr(Op1,
C);
2695 return BinaryOperator::CreateOr(
C, Op1);
2699 return BinaryOperator::CreateOr(Op0,
C);
2703 return BinaryOperator::CreateOr(Op1,
Builder.CreateAnd(A,
C));
2709 bool SwappedForXor =
false;
2712 SwappedForXor =
true;
2721 if (Op0 == A || Op0 ==
B)
2722 return BinaryOperator::CreateOr(A,
B);
2726 return BinaryOperator::CreateOr(A,
B);
2728 if ((Op0->
hasOneUse() || Op1->hasOneUse()) &&
2734 return BinaryOperator::CreateOr(Not, Op0);
2737 Value *Not =
Builder.CreateNot(A, A->getName() +
".not");
2738 return BinaryOperator::CreateOr(Not, Op0);
2746 if ((Op0 ==
B->getOperand(0) || Op0 ==
B->getOperand(1)) &&
2747 Op1->hasOneUse() && (
B->getOpcode() == Instruction::Or ||
2748 B->getOpcode() == Instruction::Xor)) {
2749 Value *NotOp = Op0 ==
B->getOperand(0) ?
B->getOperand(1) :
2752 return BinaryOperator::CreateOr(Not, Op0);
2763 return replaceInstUsesWith(
I, Res);
2769 if (
auto *Cmp = dyn_cast<ICmpInst>(
X))
2770 if (
Value *Res = foldAndOrOfICmps(
LHS, Cmp,
I,
false))
2771 return replaceInstUsesWith(
I,
Builder.CreateOr(Res,
Y));
2772 if (
auto *Cmp = dyn_cast<ICmpInst>(
Y))
2773 if (
Value *Res = foldAndOrOfICmps(
LHS, Cmp,
I,
false))
2774 return replaceInstUsesWith(
I,
Builder.CreateOr(Res,
X));
2777 if (
auto *Cmp = dyn_cast<ICmpInst>(
X))
2778 if (
Value *Res = foldAndOrOfICmps(Cmp,
RHS,
I,
false))
2779 return replaceInstUsesWith(
I,
Builder.CreateOr(Res,
Y));
2780 if (
auto *Cmp = dyn_cast<ICmpInst>(
Y))
2781 if (
Value *Res = foldAndOrOfICmps(Cmp,
RHS,
I,
false))
2782 return replaceInstUsesWith(
I,
Builder.CreateOr(Res,
X));
2786 if (
FCmpInst *
LHS = dyn_cast<FCmpInst>(
I.getOperand(0)))
2787 if (
FCmpInst *
RHS = dyn_cast<FCmpInst>(
I.getOperand(1)))
2788 if (
Value *Res = foldLogicOfFCmps(
LHS,
RHS,
false))
2789 return replaceInstUsesWith(
I, Res);
2806 A->getType()->isIntOrIntVectorTy(1))
2809 A->getType()->isIntOrIntVectorTy(1))
2822 return BinaryOperator::CreateOr(Inner, CI);
2829 Value *
X =
nullptr, *
Y =
nullptr;
2830 if (Op0->
hasOneUse() && Op1->hasOneUse() &&
2853 canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(
I))
2857 Value *
Mul, *Ov, *MulIsNotZero, *UMulWithOv;
2874 if (
match(UMulWithOv, m_Intrinsic<Intrinsic::umul_with_overflow>(
2878 return BinaryOperator::CreateAnd(NotNullA, NotNullB);
2883 if (sinkNotIntoOtherHandOfAndOrOr(
I))
2898 Value *Start =
nullptr, *Step =
nullptr;
2900 return replaceInstUsesWith(
I,
Builder.CreateOr(Start, Step));
2916 return BinaryOperator::CreateOr(
2928 return BinaryOperator::CreateOr(
2939 assert(
I.getOpcode() == Instruction::Xor);
2940 Value *Op0 =
I.getOperand(0);
2941 Value *Op1 =
I.getOperand(1);
2952 return BinaryOperator::CreateXor(A,
B);
2960 return BinaryOperator::CreateXor(A,
B);
2968 return BinaryOperator::CreateXor(A,
B);
2990 assert(
I.getOpcode() == Instruction::Xor &&
I.getOperand(0) ==
LHS &&
2991 I.getOperand(1) ==
RHS &&
"Should be 'xor' with these operands");
2994 if (
LHS->getOperand(0) ==
RHS->getOperand(1) &&
2995 LHS->getOperand(1) ==
RHS->getOperand(0))
2996 LHS->swapOperands();
2997 if (
LHS->getOperand(0) ==
RHS->getOperand(0) &&
2998 LHS->getOperand(1) ==
RHS->getOperand(1)) {
3000 Value *Op0 =
LHS->getOperand(0), *Op1 =
LHS->getOperand(1);
3003 bool IsSigned =
LHS->isSigned() ||
RHS->isSigned();
3012 Value *LHS0 =
LHS->getOperand(0), *LHS1 =
LHS->getOperand(1);
3013 Value *RHS0 =
RHS->getOperand(0), *RHS1 =
RHS->getOperand(1);
3047 if (OrICmp ==
LHS && AndICmp ==
RHS) {
3052 if (OrICmp ==
RHS && AndICmp ==
LHS) {
3057 if (
X &&
Y && (
Y->hasOneUse() || canFreelyInvertAllUsersOf(
Y, &
I))) {
3059 Y->setPredicate(
Y->getInversePredicate());
3061 if (!
Y->hasOneUse()) {
3068 Builder.SetInsertPoint(
Y->getParent(), ++(
Y->getIterator()));
3071 Worklist.pushUsersToWorkList(*
Y);
3072 Y->replaceUsesWithIf(NotY,
3073 [NotY](
Use &U) {
return U.
getUser() != NotY; });
3113 return BinaryOperator::CreateXor(NewA,
X);
3125 return BinaryOperator::CreateOr(
LHS,
RHS);
3154 return BinaryOperator::CreateXor(NotX,
Y,
I.getName() +
".demorgan");
3161 assert(
Xor.getOpcode() == Instruction::Xor &&
"Expected an xor instruction.");
3167 Value *Op0 =
Xor.getOperand(0), *Op1 =
Xor.getOperand(1);
3182 auto *Add = cast<BinaryOperator>(Op0);
3183 Value *NegA =
Builder.CreateNeg(A,
"", Add->hasNoUnsignedWrap(),
3184 Add->hasNoSignedWrap());
3197 switch (
I.getOpcode()) {
3198 case Instruction::And:
3199 NewOpc = Instruction::Or;
3201 case Instruction::Or:
3202 NewOpc = Instruction::And;
3224 replaceInstUsesWith(
I, NewBinOp);
3228 freelyInvertAllUsersOf(NewBinOp);
3246 Type *Ty =
I.getType();
3250 return BinaryOperator::CreateOr(
X, NotY);
3261 return BinaryOperator::CreateAnd(
X, NotY);
3271 if (NotVal->
getOpcode() == Instruction::And ||
3272 NotVal->
getOpcode() == Instruction::Or) {
3282 if (NotVal->
getOpcode() == Instruction::And)
3283 return BinaryOperator::CreateOr(NotX, NotY);
3284 return BinaryOperator::CreateAnd(NotX, NotY);
3293 return BinaryOperator::CreateAnd(DecX, NotY);
3298 return BinaryOperator::CreateAShr(
X,
Y);
3346 return replaceInstUsesWith(
I, NotOp);
3352 auto *II = dyn_cast<IntrinsicInst>(NotOp);
3353 if (II && II->hasOneUse()) {
3355 isFreeToInvert(
X,
X->hasOneUse()) &&
3356 isFreeToInvert(
Y,
Y->hasOneUse())) {
3360 Value *InvMaxMin =
Builder.CreateBinaryIntrinsic(InvID, NotX, NotY);
3361 return replaceInstUsesWith(
I, InvMaxMin);
3366 Value *InvMaxMin =
Builder.CreateBinaryIntrinsic(InvID,
X, NotY);
3367 return replaceInstUsesWith(
I, InvMaxMin);
3380 if (
auto *Sel = dyn_cast<SelectInst>(NotOp)) {
3381 Value *TV = Sel->getTrueValue();
3382 Value *FV = Sel->getFalseValue();
3383 auto *CmpT = dyn_cast<CmpInst>(TV);
3384 auto *CmpF = dyn_cast<CmpInst>(FV);
3385 bool InvertibleT = (CmpT && CmpT->hasOneUse()) || isa<Constant>(TV);
3386 bool InvertibleF = (CmpF && CmpF->hasOneUse()) || isa<Constant>(FV);
3387 if (InvertibleT && InvertibleF) {
3389 CmpT->setPredicate(CmpT->getInversePredicate());
3393 CmpF->setPredicate(CmpF->getInversePredicate());
3396 return replaceInstUsesWith(
I, Sel);
3412 SQ.getWithInstruction(&
I)))
3413 return replaceInstUsesWith(
I, V);
3415 if (SimplifyAssociativeOrCommutative(
I))
3428 if (
Value *V = SimplifyUsingDistributiveLaws(
I))
3429 return replaceInstUsesWith(
I, V);
3433 if (SimplifyDemandedInstructionBits(
I))
3437 return replaceInstUsesWith(
I, V);
3446 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
3450 return BinaryOperator::CreateOr(Op0, Op1);
3467 return BinaryOperator::CreateXor(
3490 *CA ==
X->getType()->getScalarSizeInBits() - 1 &&
3492 assert(!
C1->isZeroValue() &&
"Unexpected xor with 0");
3498 Type *Ty =
I.getType();
3550 auto *Opnd0 =
Builder.CreateLShr(
X, C2);
3551 Opnd0->takeName(Op0);
3556 if (
Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(
I))
3562 return BinaryOperator::CreateAnd(
X,
Builder.CreateNot(Op0));
3566 return BinaryOperator::CreateAnd(
X,
Builder.CreateNot(Op1));
3571 return BinaryOperator::CreateAnd(Op0,
Builder.CreateNot(
X));
3579 return BinaryOperator::CreateAnd(Op1,
Builder.CreateNot(
X));
3585 return BinaryOperator::CreateXor(
3591 return BinaryOperator::CreateXor(
3597 return BinaryOperator::CreateOr(A,
B);
3601 return BinaryOperator::CreateOr(A,
B);
3611 return BinaryOperator::CreateOr(A,
B);
3626 if (
B ==
C ||
B ==
D)
3632 return BinaryOperator::CreateAnd(
Builder.CreateXor(
B,
C), NotA);
3636 if (
auto *
LHS = dyn_cast<ICmpInst>(
I.getOperand(0)))
3637 if (
auto *
RHS = dyn_cast<ICmpInst>(
I.getOperand(1)))
3639 return replaceInstUsesWith(
I, V);
3641 if (
Instruction *CastedXor = foldCastedBitwiseLogic(
I))
3655 return BinaryOperator::CreateXor(
Builder.CreateXor(
X,
Y),
C1);