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);
1435 shouldOptimizeCast(Cast0) && shouldOptimizeCast(Cast1)) {
1436 Value *NewOp =
Builder.CreateBinOp(LogicOpc, Cast0Src, Cast1Src,
1442 if (LogicOpc == Instruction::Xor)
1447 ICmpInst *ICmp0 = dyn_cast<ICmpInst>(Cast0Src);
1448 ICmpInst *ICmp1 = dyn_cast<ICmpInst>(Cast1Src);
1449 if (ICmp0 && ICmp1) {
1451 foldAndOrOfICmps(ICmp0, ICmp1,
I, LogicOpc == Instruction::And))
1458 FCmpInst *FCmp0 = dyn_cast<FCmpInst>(Cast0Src);
1459 FCmpInst *FCmp1 = dyn_cast<FCmpInst>(Cast1Src);
1461 if (
Value *R = foldLogicOfFCmps(FCmp0, FCmp1, LogicOpc == Instruction::And))
1469 assert(
I.getOpcode() == Instruction::And);
1470 Value *Op0 =
I.getOperand(0);
1471 Value *Op1 =
I.getOperand(1);
1479 return BinaryOperator::CreateXor(A,
B);
1495 assert(
I.getOpcode() == Instruction::Or);
1496 Value *Op0 =
I.getOperand(0);
1497 Value *Op1 =
I.getOperand(1);
1522 return BinaryOperator::CreateXor(A,
B);
1542 Value *Op0 =
And.getOperand(0), *Op1 =
And.getOperand(1);
1556 if (!isa<VectorType>(Ty) && !shouldChangeType(Ty,
X->getType()))
1563 if (Opc == Instruction::LShr || Opc == Instruction::Shl)
1570 Value *NewBO = Opc == Instruction::Sub ?
Builder.CreateBinOp(Opc, NewC,
X)
1571 :
Builder.CreateBinOp(Opc,
X, NewC);
1580 assert(Opcode == Instruction::And || Opcode == Instruction::Or);
1584 (Opcode == Instruction::And) ? Instruction::Or : Instruction::And;
1586 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
1593 const auto matchNotOrAnd =
1594 [Opcode, FlippedOpcode](
Value *
Op,
auto m_A,
auto m_B,
auto m_C,
1595 Value *&
X,
bool CountUses =
false) ->
bool {
1596 if (CountUses && !
Op->hasOneUse())
1603 return !CountUses ||
X->hasOneUse();
1619 return (Opcode == Instruction::Or)
1620 ? BinaryOperator::CreateAnd(
Xor,
Builder.CreateNot(A))
1629 return (Opcode == Instruction::Or)
1630 ? BinaryOperator::CreateAnd(
Xor,
Builder.CreateNot(
B))
1639 Opcode,
Builder.CreateBinOp(FlippedOpcode,
B,
C), A));
1646 Opcode,
Builder.CreateBinOp(FlippedOpcode, A,
C),
B));
1652 if (Opcode == Instruction::Or && Op0->
hasOneUse() &&
1659 Value *
Or = cast<BinaryOperator>(
X)->getOperand(0);
1691 return (Opcode == Instruction::Or)
1693 : BinaryOperator::CreateOr(
Xor,
X);
1720 Type *Ty =
I.getType();
1723 SQ.getWithInstruction(&
I)))
1724 return replaceInstUsesWith(
I, V);
1726 if (SimplifyAssociativeOrCommutative(
I))
1737 if (SimplifyDemandedInstructionBits(
I))
1748 if (
Value *V = SimplifyUsingDistributiveLaws(
I))
1749 return replaceInstUsesWith(
I, V);
1752 return replaceInstUsesWith(
I, V);
1754 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
1773 return BinaryOperator::CreateXor(
And, NewC);
1784 APInt Together = *
C & *OrC;
1798 Value *NewRHS =
Builder.CreateAnd(
Y, Op1,
Y->getName() +
".masked");
1804 Value *NewLHS =
Builder.CreateAnd(
X, Op1,
X->getName() +
".masked");
1810 const APInt *ShiftC;
1817 return BinaryOperator::CreateLShr(Sext, ShAmtC);
1833 if ((*AddC & LowMask).
isZero())
1834 return BinaryOperator::CreateAnd(
X, Op1);
1840 if (Op0->
hasOneUse() &&
C->isPowerOf2() && (*AddC & (*
C - 1)) == 0) {
1841 assert((*
C & *AddC) != 0 &&
"Expected common bit");
1843 return BinaryOperator::CreateXor(NewAnd, Op1);
1850 switch (
B->getOpcode()) {
1851 case Instruction::Xor:
1852 case Instruction::Or:
1855 case Instruction::Sub:
1868 C->isIntN(
X->getType()->getScalarSizeInBits())) {
1869 unsigned XWidth =
X->getType()->getScalarSizeInBits();
1884 ICmpInst::Predicate::ICMP_EQ,
1887 X->getType()->getScalarSizeInBits())))) {
1888 auto *SExt =
Builder.CreateSExt(
X, Ty,
X->getName() +
".signext");
1889 auto *SanitizedSignMask = cast<Constant>(Op1);
1897 return BinaryOperator::CreateAnd(SExt, SanitizedSignMask);
1903 if (
I.getType()->isIntOrIntVectorTy(1)) {
1904 if (
auto *SI0 = dyn_cast<SelectInst>(Op0)) {
1906 foldAndOrOfSelectUsingImpliedCond(Op1, *SI0,
true))
1909 if (
auto *SI1 = dyn_cast<SelectInst>(Op1)) {
1911 foldAndOrOfSelectUsingImpliedCond(Op0, *SI1,
true))
1916 if (
Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(
I))
1926 return BinaryOperator::CreateAnd(Op0,
Builder.CreateNot(
B));
1929 return BinaryOperator::CreateAnd(Op1,
Builder.CreateNot(
B));
1933 return BinaryOperator::CreateAnd(Op0,
B);
1936 return BinaryOperator::CreateAnd(Op1,
B);
1941 if (Op1->hasOneUse() || isFreeToInvert(
C,
C->hasOneUse()))
1942 return BinaryOperator::CreateAnd(Op0,
Builder.CreateNot(
C));
1947 if (Op0->
hasOneUse() || isFreeToInvert(
C,
C->hasOneUse()))
1948 return BinaryOperator::CreateAnd(Op1,
Builder.CreateNot(
C));
1956 return BinaryOperator::CreateAnd(A,
B);
1964 return BinaryOperator::CreateAnd(A,
B);
1972 return BinaryOperator::CreateAnd(
Builder.CreateNot(A),
B);
1980 return BinaryOperator::CreateAnd(
Builder.CreateNot(A),
B);
1988 return replaceInstUsesWith(
I, Res);
1993 if (
auto *Cmp = dyn_cast<ICmpInst>(
X))
1994 if (
Value *Res = foldAndOrOfICmps(
LHS, Cmp,
I,
true))
1995 return replaceInstUsesWith(
I,
Builder.CreateAnd(Res,
Y));
1996 if (
auto *Cmp = dyn_cast<ICmpInst>(
Y))
1997 if (
Value *Res = foldAndOrOfICmps(
LHS, Cmp,
I,
true))
1998 return replaceInstUsesWith(
I,
Builder.CreateAnd(Res,
X));
2001 if (
auto *Cmp = dyn_cast<ICmpInst>(
X))
2002 if (
Value *Res = foldAndOrOfICmps(Cmp,
RHS,
I,
true))
2003 return replaceInstUsesWith(
I,
Builder.CreateAnd(Res,
Y));
2004 if (
auto *Cmp = dyn_cast<ICmpInst>(
Y))
2005 if (
Value *Res = foldAndOrOfICmps(Cmp,
RHS,
I,
true))
2006 return replaceInstUsesWith(
I,
Builder.CreateAnd(Res,
X));
2010 if (
FCmpInst *
LHS = dyn_cast<FCmpInst>(
I.getOperand(0)))
2011 if (
FCmpInst *
RHS = dyn_cast<FCmpInst>(
I.getOperand(1)))
2012 if (
Value *Res = foldLogicOfFCmps(
LHS,
RHS,
true))
2013 return replaceInstUsesWith(
I, Res);
2018 if (
Instruction *CastedAnd = foldCastedBitwiseLogic(
I))
2031 A->getType()->isIntOrIntVectorTy(1))
2034 A->getType()->isIntOrIntVectorTy(1))
2054 if (sinkNotIntoOtherHandOfAndOrOr(
I))
2059 Value *Start =
nullptr, *Step =
nullptr;
2061 return replaceInstUsesWith(
I,
Builder.CreateAnd(Start, Step));
2068 bool MatchBitReversals) {
2076 for (
auto *Inst : Insts)
2077 Worklist.push(Inst);
2085 unsigned Width =
Or.getType()->getScalarSizeInBits();
2094 Value *ShVal0, *ShVal1, *ShAmt0, *ShAmt1;
2101 if (Or0->
getOpcode() == BinaryOperator::LShr) {
2107 Or1->
getOpcode() == BinaryOperator::LShr &&
2108 "Illegal or(shift,shift) pair");
2114 const APInt *LI, *RI;
2139 if (ShVal0 != ShVal1)
2169 Value *ShAmt = matchShiftAmount(ShAmt0, ShAmt1,
Width);
2172 ShAmt = matchShiftAmount(ShAmt1, ShAmt0,
Width);
2178 Intrinsic::ID IID = IsFshl ? Intrinsic::fshl : Intrinsic::fshr;
2186 assert(
Or.getOpcode() == Instruction::Or &&
"bswap requires an 'or'");
2187 Value *Op0 =
Or.getOperand(0), *Op1 =
Or.getOperand(1);
2191 if ((
Width & 1) != 0)
2193 unsigned HalfWidth =
Width / 2;
2196 if (!isa<ZExtInst>(Op0))
2200 Value *LowerSrc, *ShlVal, *UpperSrc;
2213 NewUpper =
Builder.CreateShl(NewUpper, HalfWidth);
2216 return Builder.CreateCall(
F, BinOp);
2221 Value *LowerBSwap, *UpperBSwap;
2224 return ConcatIntrinsicCalls(Intrinsic::bswap, UpperBSwap, LowerBSwap);
2228 Value *LowerBRev, *UpperBRev;
2231 return ConcatIntrinsicCalls(Intrinsic::bitreverse, UpperBRev, LowerBRev);
2238 unsigned NumElts = cast<FixedVectorType>(
C1->getType())->getNumElements();
2239 for (
unsigned i = 0;
i != NumElts; ++
i) {
2242 if (!EltC1 || !EltC2)
2259 Type *Ty =
A->getType();
2275 if (
A->getType()->isIntOrIntVectorTy()) {
2277 if (NumSignBits ==
A->getType()->getScalarSizeInBits() &&
2296 Cond->getType()->isIntOrIntVectorTy(1)) {
2322 Cond->getType()->isIntOrIntVectorTy(1) &&
2336 Type *OrigType =
A->getType();
2339 if (
Value *
Cond = getSelectCondition(A,
B)) {
2344 Type *SelTy =
A->getType();
2345 if (
auto *VecTy = dyn_cast<VectorType>(
Cond->getType())) {
2347 unsigned Elts = VecTy->getElementCount().getKnownMinValue();
2351 Type *EltTy =
Builder.getIntNTy(SelEltSize / Elts);
2368 IsAnd ?
LHS->getInversePredicate() :
LHS->getPredicate();
2370 IsAnd ?
RHS->getInversePredicate() :
RHS->getPredicate();
2399 if (
Value *V = foldAndOrOfICmpsOfAndWithPow2(
LHS,
RHS, &BO, IsAnd))
2403 Value *LHS0 =
LHS->getOperand(0), *RHS0 =
RHS->getOperand(0);
2404 Value *LHS1 =
LHS->getOperand(1), *RHS1 =
RHS->getOperand(1);
2405 const APInt *LHSC =
nullptr, *RHSC =
nullptr;
2412 if (LHS0 == RHS1 && LHS1 == RHS0) {
2416 if (LHS0 == RHS0 && LHS1 == RHS1) {
2419 bool IsSigned =
LHS->isSigned() ||
RHS->isSigned();
2447 if (
Value *V = simplifyRangeCheck(
LHS,
RHS, !IsAnd))
2452 if (
Value *V = simplifyRangeCheck(
RHS,
LHS, !IsAnd))
2477 return Builder.CreateICmp(PredL, NewOr,
2492 const APInt *AndC, *SmallC =
nullptr, *BigC =
nullptr;
2506 if (SmallC && BigC) {
2512 if ((Low & *AndC).
isZero() && (Low & *BigC).
isZero()) {
2516 return Builder.CreateICmp(PredL, NewAnd, NewVal);
2521 return foldAndOrOfICmpsUsingRanges(
LHS,
RHS, IsAnd);
2529 SQ.getWithInstruction(&
I)))
2530 return replaceInstUsesWith(
I, V);
2532 if (SimplifyAssociativeOrCommutative(
I))
2543 if (SimplifyDemandedInstructionBits(
I))
2554 if (
Value *V = SimplifyUsingDistributiveLaws(
I))
2555 return replaceInstUsesWith(
I, V);
2558 return replaceInstUsesWith(
I, V);
2560 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
2561 Type *Ty =
I.getType();
2563 if (
auto *SI0 = dyn_cast<SelectInst>(Op0)) {
2565 foldAndOrOfSelectUsingImpliedCond(Op1, *SI0,
false))
2568 if (
auto *SI1 = dyn_cast<SelectInst>(Op1)) {
2570 foldAndOrOfSelectUsingImpliedCond(Op0, *SI1,
false))
2575 if (
Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(
I))
2578 if (
Instruction *BitOp = matchBSwapOrBitReverse(
I,
true,
2586 return replaceInstUsesWith(
I,
Concat);
2619 return BinaryOperator::CreateOr(
Builder.CreateAnd(
X, *C0),
B);
2622 return BinaryOperator::CreateOr(
Builder.CreateAnd(
X, *
C1), A);
2626 return BinaryOperator::CreateXor(
Builder.CreateAnd(
X, *C0),
B);
2629 return BinaryOperator::CreateXor(
Builder.CreateAnd(
X, *
C1), A);
2638 return BinaryOperator::CreateAnd(A, C01);
2645 return BinaryOperator::CreateAnd(
B, C01);
2649 const APInt *C2, *C3;
2655 return BinaryOperator::CreateAnd(
Or, C01);
2663 if (Op0->
hasOneUse() || Op1->hasOneUse()) {
2665 if (
Value *V = matchSelectFromAndOr(A,
C,
B,
D))
2666 return replaceInstUsesWith(
I, V);
2667 if (
Value *V = matchSelectFromAndOr(A,
C,
D,
B))
2668 return replaceInstUsesWith(
I, V);
2669 if (
Value *V = matchSelectFromAndOr(
C, A,
B,
D))
2670 return replaceInstUsesWith(
I, V);
2671 if (
Value *V = matchSelectFromAndOr(
C, A,
D,
B))
2672 return replaceInstUsesWith(
I, V);
2673 if (
Value *V = matchSelectFromAndOr(
B,
D, A,
C))
2674 return replaceInstUsesWith(
I, V);
2675 if (
Value *V = matchSelectFromAndOr(
B,
D,
C, A))
2676 return replaceInstUsesWith(
I, V);
2677 if (
Value *V = matchSelectFromAndOr(
D,
B, A,
C))
2678 return replaceInstUsesWith(
I, V);
2679 if (
Value *V = matchSelectFromAndOr(
D,
B,
C, A))
2680 return replaceInstUsesWith(
I, V);
2687 return BinaryOperator::CreateOr(Op0,
C);
2692 return BinaryOperator::CreateOr(Op1,
C);
2696 return BinaryOperator::CreateOr(
C, Op1);
2700 return BinaryOperator::CreateOr(Op0,
C);
2704 return BinaryOperator::CreateOr(Op1,
Builder.CreateAnd(A,
C));
2710 bool SwappedForXor =
false;
2713 SwappedForXor =
true;
2722 if (Op0 == A || Op0 ==
B)
2723 return BinaryOperator::CreateOr(A,
B);
2727 return BinaryOperator::CreateOr(A,
B);
2729 if ((Op0->
hasOneUse() || Op1->hasOneUse()) &&
2735 return BinaryOperator::CreateOr(Not, Op0);
2738 Value *Not =
Builder.CreateNot(A, A->getName() +
".not");
2739 return BinaryOperator::CreateOr(Not, Op0);
2747 if ((Op0 ==
B->getOperand(0) || Op0 ==
B->getOperand(1)) &&
2748 Op1->hasOneUse() && (
B->getOpcode() == Instruction::Or ||
2749 B->getOpcode() == Instruction::Xor)) {
2750 Value *NotOp = Op0 ==
B->getOperand(0) ?
B->getOperand(1) :
2753 return BinaryOperator::CreateOr(Not, Op0);
2764 return replaceInstUsesWith(
I, Res);
2770 if (
auto *Cmp = dyn_cast<ICmpInst>(
X))
2771 if (
Value *Res = foldAndOrOfICmps(
LHS, Cmp,
I,
false))
2772 return replaceInstUsesWith(
I,
Builder.CreateOr(Res,
Y));
2773 if (
auto *Cmp = dyn_cast<ICmpInst>(
Y))
2774 if (
Value *Res = foldAndOrOfICmps(
LHS, Cmp,
I,
false))
2775 return replaceInstUsesWith(
I,
Builder.CreateOr(Res,
X));
2778 if (
auto *Cmp = dyn_cast<ICmpInst>(
X))
2779 if (
Value *Res = foldAndOrOfICmps(Cmp,
RHS,
I,
false))
2780 return replaceInstUsesWith(
I,
Builder.CreateOr(Res,
Y));
2781 if (
auto *Cmp = dyn_cast<ICmpInst>(
Y))
2782 if (
Value *Res = foldAndOrOfICmps(Cmp,
RHS,
I,
false))
2783 return replaceInstUsesWith(
I,
Builder.CreateOr(Res,
X));
2787 if (
FCmpInst *
LHS = dyn_cast<FCmpInst>(
I.getOperand(0)))
2788 if (
FCmpInst *
RHS = dyn_cast<FCmpInst>(
I.getOperand(1)))
2789 if (
Value *Res = foldLogicOfFCmps(
LHS,
RHS,
false))
2790 return replaceInstUsesWith(
I, Res);
2807 A->getType()->isIntOrIntVectorTy(1))
2810 A->getType()->isIntOrIntVectorTy(1))
2823 return BinaryOperator::CreateOr(Inner, CI);
2830 Value *
X =
nullptr, *
Y =
nullptr;
2831 if (Op0->
hasOneUse() && Op1->hasOneUse() &&
2854 canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(
I))
2858 Value *
Mul, *Ov, *MulIsNotZero, *UMulWithOv;
2875 if (
match(UMulWithOv, m_Intrinsic<Intrinsic::umul_with_overflow>(
2879 return BinaryOperator::CreateAnd(NotNullA, NotNullB);
2884 if (sinkNotIntoOtherHandOfAndOrOr(
I))
2899 Value *Start =
nullptr, *Step =
nullptr;
2901 return replaceInstUsesWith(
I,
Builder.CreateOr(Start, Step));
2917 return BinaryOperator::CreateOr(
2929 return BinaryOperator::CreateOr(
2940 assert(
I.getOpcode() == Instruction::Xor);
2941 Value *Op0 =
I.getOperand(0);
2942 Value *Op1 =
I.getOperand(1);
2953 return BinaryOperator::CreateXor(A,
B);
2961 return BinaryOperator::CreateXor(A,
B);
2969 return BinaryOperator::CreateXor(A,
B);
2991 assert(
I.getOpcode() == Instruction::Xor &&
I.getOperand(0) ==
LHS &&
2992 I.getOperand(1) ==
RHS &&
"Should be 'xor' with these operands");
2995 if (
LHS->getOperand(0) ==
RHS->getOperand(1) &&
2996 LHS->getOperand(1) ==
RHS->getOperand(0))
2997 LHS->swapOperands();
2998 if (
LHS->getOperand(0) ==
RHS->getOperand(0) &&
2999 LHS->getOperand(1) ==
RHS->getOperand(1)) {
3001 Value *Op0 =
LHS->getOperand(0), *Op1 =
LHS->getOperand(1);
3004 bool IsSigned =
LHS->isSigned() ||
RHS->isSigned();
3013 Value *LHS0 =
LHS->getOperand(0), *LHS1 =
LHS->getOperand(1);
3014 Value *RHS0 =
RHS->getOperand(0), *RHS1 =
RHS->getOperand(1);
3048 if (OrICmp ==
LHS && AndICmp ==
RHS) {
3053 if (OrICmp ==
RHS && AndICmp ==
LHS) {
3058 if (
X &&
Y && (
Y->hasOneUse() || canFreelyInvertAllUsersOf(
Y, &
I))) {
3060 Y->setPredicate(
Y->getInversePredicate());
3062 if (!
Y->hasOneUse()) {
3069 Builder.SetInsertPoint(
Y->getParent(), ++(
Y->getIterator()));
3072 Worklist.pushUsersToWorkList(*
Y);
3073 Y->replaceUsesWithIf(NotY,
3074 [NotY](
Use &U) {
return U.
getUser() != NotY; });
3114 return BinaryOperator::CreateXor(NewA,
X);
3126 return BinaryOperator::CreateOr(
LHS,
RHS);
3155 return BinaryOperator::CreateXor(NotX,
Y,
I.getName() +
".demorgan");
3162 assert(
Xor.getOpcode() == Instruction::Xor &&
"Expected an xor instruction.");
3168 Value *Op0 =
Xor.getOperand(0), *Op1 =
Xor.getOperand(1);
3183 auto *Add = cast<BinaryOperator>(Op0);
3184 Value *NegA =
Builder.CreateNeg(A,
"", Add->hasNoUnsignedWrap(),
3185 Add->hasNoSignedWrap());
3198 switch (
I.getOpcode()) {
3199 case Instruction::And:
3200 NewOpc = Instruction::Or;
3202 case Instruction::Or:
3203 NewOpc = Instruction::And;
3225 replaceInstUsesWith(
I, NewBinOp);
3229 freelyInvertAllUsersOf(NewBinOp);
3247 Type *Ty =
I.getType();
3251 return BinaryOperator::CreateOr(
X, NotY);
3262 return BinaryOperator::CreateAnd(
X, NotY);
3272 if (NotVal->
getOpcode() == Instruction::And ||
3273 NotVal->
getOpcode() == Instruction::Or) {
3283 if (NotVal->
getOpcode() == Instruction::And)
3284 return BinaryOperator::CreateOr(NotX, NotY);
3285 return BinaryOperator::CreateAnd(NotX, NotY);
3294 return BinaryOperator::CreateAnd(DecX, NotY);
3299 return BinaryOperator::CreateAShr(
X,
Y);
3347 return replaceInstUsesWith(
I, NotOp);
3353 auto *II = dyn_cast<IntrinsicInst>(NotOp);
3354 if (II && II->hasOneUse()) {
3356 isFreeToInvert(
X,
X->hasOneUse()) &&
3357 isFreeToInvert(
Y,
Y->hasOneUse())) {
3361 Value *InvMaxMin =
Builder.CreateBinaryIntrinsic(InvID, NotX, NotY);
3362 return replaceInstUsesWith(
I, InvMaxMin);
3367 Value *InvMaxMin =
Builder.CreateBinaryIntrinsic(InvID,
X, NotY);
3368 return replaceInstUsesWith(
I, InvMaxMin);
3381 if (
auto *Sel = dyn_cast<SelectInst>(NotOp)) {
3382 Value *TV = Sel->getTrueValue();
3383 Value *FV = Sel->getFalseValue();
3384 auto *CmpT = dyn_cast<CmpInst>(TV);
3385 auto *CmpF = dyn_cast<CmpInst>(FV);
3386 bool InvertibleT = (CmpT && CmpT->hasOneUse()) || isa<Constant>(TV);
3387 bool InvertibleF = (CmpF && CmpF->hasOneUse()) || isa<Constant>(FV);
3388 if (InvertibleT && InvertibleF) {
3390 CmpT->setPredicate(CmpT->getInversePredicate());
3394 CmpF->setPredicate(CmpF->getInversePredicate());
3397 return replaceInstUsesWith(
I, Sel);
3413 SQ.getWithInstruction(&
I)))
3414 return replaceInstUsesWith(
I, V);
3416 if (SimplifyAssociativeOrCommutative(
I))
3429 if (
Value *V = SimplifyUsingDistributiveLaws(
I))
3430 return replaceInstUsesWith(
I, V);
3434 if (SimplifyDemandedInstructionBits(
I))
3438 return replaceInstUsesWith(
I, V);
3447 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
3451 return BinaryOperator::CreateOr(Op0, Op1);
3468 return BinaryOperator::CreateXor(
3491 *CA ==
X->getType()->getScalarSizeInBits() - 1 &&
3493 assert(!
C1->isZeroValue() &&
"Unexpected xor with 0");
3499 Type *Ty =
I.getType();
3551 auto *Opnd0 =
Builder.CreateLShr(
X, C2);
3552 Opnd0->takeName(Op0);
3557 if (
Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(
I))
3563 return BinaryOperator::CreateAnd(
X,
Builder.CreateNot(Op0));
3567 return BinaryOperator::CreateAnd(
X,
Builder.CreateNot(Op1));
3572 return BinaryOperator::CreateAnd(Op0,
Builder.CreateNot(
X));
3580 return BinaryOperator::CreateAnd(Op1,
Builder.CreateNot(
X));
3586 return BinaryOperator::CreateXor(
3592 return BinaryOperator::CreateXor(
3598 return BinaryOperator::CreateOr(A,
B);
3602 return BinaryOperator::CreateOr(A,
B);
3612 return BinaryOperator::CreateOr(A,
B);
3627 if (
B ==
C ||
B ==
D)
3633 return BinaryOperator::CreateAnd(
Builder.CreateXor(
B,
C), NotA);
3637 if (
auto *
LHS = dyn_cast<ICmpInst>(
I.getOperand(0)))
3638 if (
auto *
RHS = dyn_cast<ICmpInst>(
I.getOperand(1)))
3640 return replaceInstUsesWith(
I, V);
3642 if (
Instruction *CastedXor = foldCastedBitwiseLogic(
I))
3656 return BinaryOperator::CreateXor(
Builder.CreateXor(
X,
Y),
C1);