47 #define DEBUG_TYPE "instsimplify"
51 STATISTIC(NumExpand,
"Number of expansions");
52 STATISTIC(NumReassoc,
"Number of reassociations");
80 if (
auto *BO = dyn_cast<BinaryOperator>(
Cond))
81 BinOpCode = BO->getOpcode();
86 if (BinOpCode == BinaryOperator::Or) {
88 }
else if (BinOpCode == BinaryOperator::And) {
110 Pred1 != Pred2 || Pred1 != ExpectedPred)
130 CmpInst *Cmp = dyn_cast<CmpInst>(V);
134 Value *CLHS = Cmp->getOperand(0), *CRHS = Cmp->getOperand(1);
135 if (CPred == Pred && CLHS ==
LHS && CRHS ==
RHS)
151 if (SimplifiedCmp ==
Cond) {
159 return SimplifiedCmp;
166 unsigned MaxRecurse) {
175 unsigned MaxRecurse) {
185 unsigned MaxRecurse) {
219 if (!
I->getParent() || !
P->getParent() || !
I->getFunction())
228 if (
I->getParent()->isEntryBlock() && !isa<InvokeInst>(
I) &&
241 auto *
B = dyn_cast<BinaryOperator>(V);
242 if (!
B ||
B->getOpcode() != OpcodeToExpand)
244 Value *B0 =
B->getOperand(0), *
B1 =
B->getOperand(1);
255 if ((L == B0 && R ==
B1) ||
276 unsigned MaxRecurse) {
293 unsigned MaxRecurse) {
396 unsigned MaxRecurse) {
402 if (isa<SelectInst>(
LHS)) {
403 SI = cast<SelectInst>(
LHS);
405 assert(isa<SelectInst>(
RHS) &&
"No select instruction operand!");
406 SI = cast<SelectInst>(
RHS);
433 if (TV ==
SI->getTrueValue() && FV ==
SI->getFalseValue())
439 if ((FV && !TV) || (TV && !FV)) {
447 Value *UnsimplifiedBranch = FV ?
SI->getTrueValue() :
SI->getFalseValue();
448 Value *UnsimplifiedLHS =
SI ==
LHS ? UnsimplifiedBranch :
LHS;
449 Value *UnsimplifiedRHS =
SI ==
LHS ?
RHS : UnsimplifiedBranch;
450 if (
Simplified->getOperand(0) == UnsimplifiedLHS &&
454 Simplified->getOperand(1) == UnsimplifiedLHS &&
474 unsigned MaxRecurse) {
480 if (!isa<SelectInst>(
LHS)) {
484 assert(isa<SelectInst>(
LHS) &&
"Not comparing with a select instruction!");
487 Value *TV =
SI->getTrueValue();
488 Value *FV =
SI->getFalseValue();
520 unsigned MaxRecurse) {
526 if (isa<PHINode>(
LHS)) {
527 PI = cast<PHINode>(
LHS);
532 assert(isa<PHINode>(
RHS) &&
"No PHI instruction operand!");
533 PI = cast<PHINode>(
RHS);
540 Value *CommonValue =
nullptr;
549 if (!V || (CommonValue && V != CommonValue))
568 if (!isa<PHINode>(
LHS)) {
572 assert(isa<PHINode>(
LHS) &&
"Not comparing with a phi instruction!");
580 Value *CommonValue =
nullptr;
594 if (!V || (CommonValue && V != CommonValue))
605 if (
auto *CLHS = dyn_cast<Constant>(Op0)) {
606 if (
auto *CRHS = dyn_cast<Constant>(Op1)) {
610 case Instruction::FAdd:
611 case Instruction::FSub:
612 case Instruction::FMul:
613 case Instruction::FDiv:
614 case Instruction::FRem:
615 if (Q.
CxtI !=
nullptr)
636 if (isa<PoisonValue>(Op1))
712 bool AllowNonInbounds =
false) {
719 return Offset.sextOrTrunc(
DL.getIndexTypeSizeInBits(V->
getType()));
739 if (
auto *VecTy = dyn_cast<VectorType>(
LHS->
getType()))
753 if (isa<PoisonValue>(Op0) || isa<PoisonValue>(Op1))
789 Value *
X =
nullptr, *
Y =
nullptr, *Z = Op1;
847 if (
X->getType() ==
Y->getType())
886 unsigned MaxRecurse) {
891 if (isa<PoisonValue>(Op1))
928 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
935 if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
951 bool IsDiv = (Opcode == Instruction::SDiv || Opcode == Instruction::UDiv);
952 bool IsSigned = (Opcode == Instruction::SDiv || Opcode == Instruction::SRem);
969 auto *Op1C = dyn_cast<Constant>(Op1);
970 auto *VTy = dyn_cast<FixedVectorType>(Ty);
972 unsigned NumElts = VTy->getNumElements();
973 for (
unsigned i = 0;
i != NumElts; ++
i) {
982 if (isa<PoisonValue>(Op0))
1014 auto *
Mul = cast<OverflowingBinaryOperator>(Op0);
1034 Constant *
C = dyn_cast_or_null<Constant>(V);
1035 return (
C &&
C->isAllOnesValue());
1041 unsigned MaxRecurse,
bool IsSigned) {
1054 Type *Ty =
X->getType();
1070 if (
C->isMinSignedValue())
1109 bool IsSigned = Opcode == Instruction::SDiv;
1121 (void)
C1->getValue().umul_ov(C2->
getValue(), Overflow);
1128 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
1134 if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
1138 if (
isDivZero(Op0, Op1, Q, MaxRecurse, IsSigned))
1154 if ((Opcode == Instruction::SRem &&
1156 (Opcode == Instruction::URem &&
1162 ((Opcode == Instruction::SRem &&
1164 (Opcode == Instruction::URem &&
1170 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
1176 if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
1181 if (
isDivZero(Op0, Op1, Q, MaxRecurse, Opcode == Instruction::SRem))
1190 unsigned MaxRecurse) {
1195 return simplifyDiv(Instruction::SDiv, Op0, Op1, Q, MaxRecurse);
1205 unsigned MaxRecurse) {
1206 return simplifyDiv(Instruction::UDiv, Op0, Op1, Q, MaxRecurse);
1216 unsigned MaxRecurse) {
1227 return simplifyRem(Instruction::SRem, Op0, Op1, Q, MaxRecurse);
1237 unsigned MaxRecurse) {
1238 return simplifyRem(Instruction::URem, Op0, Op1, Q, MaxRecurse);
1247 Constant *
C = dyn_cast<Constant>(Amount);
1257 if (CI->getValue().uge(CI->getType()->getScalarSizeInBits()))
1261 if (isa<ConstantVector>(
C) || isa<ConstantDataVector>(
C)) {
1262 for (
unsigned I = 0,
1263 E = cast<FixedVectorType>(
C->getType())->getNumElements();
1277 unsigned MaxRecurse) {
1282 if (isa<PoisonValue>(Op0))
1303 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
1309 if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
1327 assert(Opcode == Instruction::Shl &&
"Expected shl for nsw instruction");
1346 Value *Op1,
bool isExact,
1365 if (Op0Known.
One[0])
1377 simplifyShift(Instruction::Shl, Op0, Op1, isNSW, Q, MaxRecurse))
1424 const APInt *ShRAmt, *ShLAmt;
1427 *ShRAmt == *ShLAmt) {
1430 if (ShRAmt->
uge(EffWidthY))
1478 ICmpInst *UnsignedICmp,
bool IsAnd,
1492 if (
match(UnsignedICmp,
1510 return IsAnd ? UnsignedICmp : ZeroICmp;
1516 return IsAnd ? ZeroICmp : UnsignedICmp;
1522 if (
match(UnsignedICmp,
1527 return UnsignedICmp;
1531 return UnsignedICmp;
1538 else if (
match(UnsignedICmp,
1549 return IsAnd ? ZeroICmp : UnsignedICmp;
1555 return IsAnd ? UnsignedICmp : ZeroICmp;
1565 return IsAnd ? UnsignedICmp : ZeroICmp;
1570 return IsAnd ? ZeroICmp : UnsignedICmp;
1655 if (IsAnd && Range0.intersectWith(Range1).isEmptySet())
1660 if (!IsAnd && Range0.unionWith(Range1).isFullSet())
1668 if (Range0.contains(Range1))
1669 return IsAnd ? Cmp1 : Cmp0;
1670 if (Range1.contains(Range0))
1671 return IsAnd ? Cmp0 : Cmp1;
1725 auto *AddInst = cast<OverflowingBinaryOperator>(Op0->
getOperand(0));
1726 if (AddInst->getOperand(1) != Op1->
getOperand(1))
1733 const APInt Delta = *
C1 - *C0;
1734 if (C0->isStrictlyPositive()) {
1748 if (C0->getBoolValue() && isNUW) {
1786 MinMaxC = HasNotOp ? ~*
C : *
C;
1787 else if (isa<ConstantPointerNull>(Cmp0->
getOperand(1)))
1887 auto *AddInst = cast<BinaryOperator>(Op0->
getOperand(0));
1888 if (AddInst->getOperand(1) != Op1->
getOperand(1))
1895 const APInt Delta = *
C1 - *C0;
1896 if (C0->isStrictlyPositive()) {
1910 if (C0->getBoolValue() && isNUW) {
1958 Value *LHS0 =
LHS->getOperand(0), *LHS1 =
LHS->getOperand(1);
1959 Value *RHS0 =
RHS->getOperand(0), *RHS1 =
RHS->getOperand(1);
1995 Value *Op1,
bool IsAnd) {
1997 auto *Cast0 = dyn_cast<CastInst>(Op0);
1998 auto *Cast1 = dyn_cast<CastInst>(Op1);
1999 if (Cast0 && Cast1 && Cast0->getOpcode() == Cast1->getOpcode() &&
2000 Cast0->getSrcTy() == Cast1->getSrcTy()) {
2001 Op0 = Cast0->getOperand(0);
2002 Op1 = Cast1->getOperand(0);
2006 auto *ICmp0 = dyn_cast<ICmpInst>(Op0);
2007 auto *ICmp1 = dyn_cast<ICmpInst>(Op1);
2012 auto *FCmp0 = dyn_cast<FCmpInst>(Op0);
2013 auto *FCmp1 = dyn_cast<FCmpInst>(Op1);
2024 if (
auto *
C = dyn_cast<Constant>(V))
2057 unsigned MaxRecurse) {
2062 if (isa<PoisonValue>(Op1))
2118 (~(*
Mask)).
shl(*ShAmt).isZero())
2161 Instruction::Or, Q, MaxRecurse))
2166 Instruction::Xor, Q, MaxRecurse))
2169 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) {
2187 if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
2211 if (EffWidthY <= ShftCnt) {
2251 assert(
X->getType() ==
Y->getType() &&
"Expected same type for 'or' ops");
2252 Type *Ty =
X->getType();
2336 unsigned MaxRecurse) {
2341 if (isa<PoisonValue>(Op1))
2375 C->ule(
X->getType()->getScalarSizeInBits())) {
2423 Instruction::And, Q, MaxRecurse))
2426 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) {
2470 if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
2493 unsigned MaxRecurse) {
2498 if (isa<PoisonValue>(Op1))
2536 if (
Value *R = foldAndOrNot(Op0, Op1))
2538 if (
Value *R = foldAndOrNot(Op1, Op0))
2577 CmpInst *Cmp = dyn_cast<CmpInst>(
SI->getCondition());
2580 Value *CmpLHS = Cmp->getOperand(0), *CmpRHS = Cmp->getOperand(1);
2581 if (Pred == Cmp->getPredicate() &&
LHS == CmpLHS &&
RHS == CmpRHS)
2584 LHS == CmpRHS &&
RHS == CmpLHS)
2597 if (
const AllocaInst *AI = dyn_cast<AllocaInst>(V))
2598 return AI->getParent() && AI->getFunction() && AI->isStaticAlloca();
2599 if (
const GlobalValue *GV = dyn_cast<GlobalValue>(V))
2600 return (GV->hasLocalLinkage() || GV->hasHiddenVisibility() ||
2601 GV->hasProtectedVisibility() || GV->hasGlobalUnnamedAddr()) &&
2602 !GV->isThreadLocal();
2603 if (
const Argument *A = dyn_cast<Argument>(V))
2604 return A->hasByValAttr();
2637 auto isByValArg = [](
const Value *V) {
2638 const Argument *A = dyn_cast<Argument>(V);
2639 return A && A->hasByValAttr();
2645 return isa<AllocaInst>(
V2) || isa<GlobalVariable>(
V2) || isByValArg(
V2);
2647 return isa<AllocaInst>(V1) || isa<GlobalVariable>(V1) || isByValArg(V1);
2649 return isa<AllocaInst>(V1) &&
2650 (isa<AllocaInst>(
V2) || isa<GlobalVariable>(
V2));
2752 if (
auto *
I = dyn_cast<Instruction>(V))
2753 return I->getFunction();
2754 if (
auto *A = dyn_cast<Argument>(V))
2755 return A->getParent();
2762 LHSOffset.
ult(LHSSize) && RHSOffset.
ult(RHSSize)) {
2789 if ((IsNAC(LHSUObjs) && IsAllocDisjoint(RHSUObjs)) ||
2790 (IsNAC(RHSUObjs) && IsAllocDisjoint(LHSUObjs)))
2829 auto ExtractNotLHS = [](
Value *V) ->
Value * {
3019 *MulC != 0 &&
C->
urem(*MulC) != 0) ||
3021 *MulC != 0 &&
C->
srem(*MulC) != 0)))
3030 unsigned MaxRecurse) {
3156 (
APInt(
C1->getBitWidth(), 1) << *
C1).ule(*C2))) {
3196 return (
C1->slt(*C2) &&
C1->isNonNegative()) ||
3197 (C2->
slt(*
C1) &&
C1->isNonPositive());
3205 unsigned MaxRecurse) {
3208 if (MaxRecurse && (LBO || RBO)) {
3210 Value *A =
nullptr, *
B =
nullptr, *
C =
nullptr, *
D =
nullptr;
3212 bool NoLHSWrapProblem =
false, NoRHSWrapProblem =
false;
3235 if ((A ==
RHS ||
B ==
RHS) && NoLHSWrapProblem)
3242 if ((
C ==
LHS ||
D ==
LHS) && NoRHSWrapProblem)
3245 C ==
LHS ?
D :
C, Q, MaxRecurse - 1))
3249 bool CanSimplify = (NoLHSWrapProblem && NoRHSWrapProblem) ||
3251 if (A &&
C && (A ==
C || A ==
D ||
B ==
C ||
B ==
D) && CanSimplify) {
3258 }
else if (A ==
D) {
3262 }
else if (
B ==
C) {
3290 if (
C->isStrictlyPositive()) {
3296 if (
C->isNonNegative()) {
3344 case Instruction::UDiv:
3345 case Instruction::LShr:
3353 case Instruction::SDiv:
3361 case Instruction::AShr:
3368 case Instruction::Shl: {
3389 unsigned MaxRecurse) {
3551 (A ==
C || A ==
D ||
B ==
C ||
B ==
D)) {
3560 (A ==
C || A ==
D ||
B ==
C ||
B ==
D)) {
3584 CallInst *Assume = cast<CallInst>(AssumeVH);
3610 assert(!isa<UndefValue>(
LHS) &&
"Unexpected icmp undef,%X");
3615 if (isa<PoisonValue>(
RHS))
3642 if (isa<Instruction>(
RHS) && isa<Instruction>(
LHS)) {
3643 auto RHS_Instr = cast<Instruction>(
RHS);
3644 auto LHS_Instr = cast<Instruction>(
LHS);
3649 *RHS_Instr->getMetadata(LLVMContext::MD_range));
3651 *LHS_Instr->getMetadata(LLVMContext::MD_range));
3653 if (LHS_CR.icmp(Pred, RHS_CR))
3662 if (isa<CastInst>(
LHS) && (isa<Constant>(
RHS) || isa<CastInst>(
RHS))) {
3670 if (MaxRecurse && isa<PtrToIntInst>(LI) &&
3679 if (RI->getOperand(0)->getType() == SrcTy)
3687 if (isa<ZExtInst>(
LHS)) {
3691 if (MaxRecurse && SrcTy == RI->getOperand(0)->getType())
3695 RI->getOperand(0), Q, MaxRecurse - 1))
3699 else if (
SExtInst *RI = dyn_cast<SExtInst>(
RHS)) {
3700 if (
SrcOp == RI->getOperand(0)) {
3717 if (RExt == CI && MaxRecurse)
3719 SrcOp, Trunc, Q, MaxRecurse - 1))
3743 return CI->getValue().isNegative()
3749 return CI->getValue().isNegative()
3757 if (isa<SExtInst>(
LHS)) {
3761 if (MaxRecurse && SrcTy == RI->getOperand(0)->getType())
3768 else if (
ZExtInst *RI = dyn_cast<ZExtInst>(
RHS)) {
3769 if (
SrcOp == RI->getOperand(0)) {
3786 if (RExt == CI && MaxRecurse)
3806 return CI->getValue().isNegative()
3811 return CI->getValue().isNegative()
3863 if (
auto *CLHS = dyn_cast<PtrToIntOperator>(
LHS))
3864 if (
auto *CRHS = dyn_cast<PtrToIntOperator>(
RHS))
3870 CRHS->getPointerOperand(), Q))
3875 if (isa<SelectInst>(
LHS) || isa<SelectInst>(
RHS))
3881 if (isa<PHINode>(
LHS) || isa<PHINode>(
RHS))
3897 unsigned MaxRecurse) {
3925 "Comparison must be either ordered or unordered");
3931 if (isa<PoisonValue>(
LHS) || isa<PoisonValue>(
RHS))
3956 if (
C->isInfinity()) {
3957 if (
C->isNegative()) {
3996 if (
C->isNegative() && !
C->isNegZero()) {
3997 assert(!
C->isNaN() &&
"Unexpected NaN constant!");
4090 if (isa<SelectInst>(
LHS) || isa<SelectInst>(
RHS))
4096 if (isa<PHINode>(
LHS) || isa<PHINode>(
RHS))
4110 bool AllowRefinement,
4111 unsigned MaxRecurse) {
4112 assert(!
Op->getType()->isVectorTy() &&
"This is not safe for vectors");
4119 if (isa<Constant>(
Op))
4122 auto *
I = dyn_cast<Instruction>(V);
4129 [&](
Value *V) { return V == Op ? RepOp : V; });
4131 if (!AllowRefinement) {
4136 if (
auto *BO = dyn_cast<BinaryOperator>(
I)) {
4137 unsigned Opcode = BO->getOpcode();
4146 if ((Opcode == Instruction::And || Opcode == Instruction::Or) &&
4147 NewOps[0] == NewOps[1])
4151 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(
I)) {
4153 if (NewOps.size() == 2 &&
match(NewOps[1],
m_Zero()) &&
4157 }
else if (MaxRecurse) {
4171 if (
auto *
B = dyn_cast<BinaryOperator>(
I))
4172 return PreventSelfSimplify(
simplifyBinOp(
B->getOpcode(), NewOps[0],
4173 NewOps[1], Q, MaxRecurse - 1));
4177 NewOps[1], Q, MaxRecurse - 1));
4179 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(
I))
4181 GEP->getSourceElementType(), NewOps[0],
makeArrayRef(NewOps).slice(1),
4182 GEP->isInBounds(), Q, MaxRecurse - 1));
4184 if (isa<SelectInst>(
I))
4186 NewOps[0], NewOps[1], NewOps[2], Q, MaxRecurse - 1));
4193 for (
Value *NewOp : NewOps) {
4194 if (
Constant *ConstOp = dyn_cast<Constant>(NewOp))
4195 ConstOps.push_back(ConstOp);
4214 ConstOps[1], Q.
DL, Q.
TLI);
4216 if (
LoadInst *LI = dyn_cast<LoadInst>(
I))
4217 if (!LI->isVolatile())
4225 bool AllowRefinement) {
4233 const APInt *
Y,
bool TrueWhenUnset) {
4248 if (
Y->isPowerOf2()) {
4284 unsigned MaxRecurse) {
4286 Value *CmpLHS, *CmpRHS;
4299 if (
TrueVal->getType()->isIntOrIntVectorTy()) {
4307 X->getType()->getScalarSizeInBits());