111 #define DEBUG_TYPE "instcombine"
115 using namespace llvm;
119 "Number of instruction combining iterations performed");
121 STATISTIC(NumCombined ,
"Number of insts combined");
122 STATISTIC(NumConstProp,
"Number of constant folds");
123 STATISTIC(NumDeadInst ,
"Number of dead inst eliminated");
124 STATISTIC(NumSunkInst ,
"Number of instructions sunk");
125 STATISTIC(NumExpand,
"Number of expansions");
126 STATISTIC(NumFactor ,
"Number of factorizations");
127 STATISTIC(NumReassoc ,
"Number of reassociations");
129 "Controls which instructions are visited");
144 "instcombine-max-sink-users",
cl::init(32),
145 cl::desc(
"Maximum number of undroppable users for instruction sinking"));
148 "instcombine-max-iterations",
149 cl::desc(
"Limit the maximum number of instruction combining iterations"),
153 "instcombine-infinite-loop-threshold",
154 cl::desc(
"Number of instruction combining iterations considered an "
160 cl::desc(
"Maximum array size considered when doing a combine"));
172 std::optional<Instruction *>
183 bool &KnownBitsComputed) {
200 *
this, II, DemandedElts, UndefElts, UndefElts2, UndefElts3,
215 bool InstCombinerImpl::isDesirableIntType(
unsigned BitWidth)
const {
234 bool InstCombinerImpl::shouldChangeType(
unsigned FromWidth,
235 unsigned ToWidth)
const {
236 bool FromLegal = FromWidth == 1 ||
DL.isLegalInteger(FromWidth);
237 bool ToLegal = ToWidth == 1 ||
DL.isLegalInteger(ToWidth);
241 if (ToWidth < FromWidth && isDesirableIntType(ToWidth))
246 if ((FromLegal || isDesirableIntType(FromWidth)) && !ToLegal)
251 if (!FromLegal && !ToLegal && ToWidth > FromWidth)
262 bool InstCombinerImpl::shouldChangeType(
Type *
From,
Type *To)
const {
268 unsigned FromWidth =
From->getPrimitiveSizeInBits();
270 return shouldChangeType(FromWidth, ToWidth);
279 auto *OBO = dyn_cast<OverflowingBinaryOperator>(&
I);
280 if (!OBO || !OBO->hasNoSignedWrap())
288 const APInt *BVal, *CVal;
292 bool Overflow =
false;
294 (void)BVal->
sadd_ov(*CVal, Overflow);
296 (
void)BVal->
ssub_ov(*CVal, Overflow);
302 auto *OBO = dyn_cast<OverflowingBinaryOperator>(&
I);
303 return OBO && OBO->hasNoUnsignedWrap();
307 auto *OBO = dyn_cast<OverflowingBinaryOperator>(&
I);
308 return OBO && OBO->hasNoSignedWrap();
317 I.clearSubclassOptionalData();
322 I.clearSubclassOptionalData();
323 I.setFastMathFlags(FMF);
332 auto *Cast = dyn_cast<CastInst>(BinOp1->
getOperand(0));
333 if (!Cast || !Cast->hasOneUse())
337 auto CastOpcode = Cast->getOpcode();
338 if (CastOpcode != Instruction::ZExt)
346 auto *BinOp2 = dyn_cast<BinaryOperator>(Cast->getOperand(0));
347 if (!BinOp2 || !BinOp2->hasOneUse() || BinOp2->getOpcode() != AssocOpcode)
361 Type *DestTy =
C1->getType();
371 Value *InstCombinerImpl::simplifyIntToPtrRoundTripCast(
Value *Val) {
372 auto *IntToPtr = dyn_cast<IntToPtrInst>(Val);
373 if (IntToPtr &&
DL.getTypeSizeInBits(IntToPtr->getDestTy()) ==
374 DL.getTypeSizeInBits(IntToPtr->getSrcTy())) {
375 auto *PtrToInt = dyn_cast<PtrToIntInst>(IntToPtr->getOperand(0));
376 Type *CastTy = IntToPtr->getDestTy();
379 PtrToInt->getSrcTy()->getPointerAddressSpace() &&
380 DL.getTypeSizeInBits(PtrToInt->getSrcTy()) ==
381 DL.getTypeSizeInBits(PtrToInt->getDestTy())) {
411 bool Changed =
false;
417 if (
I.isCommutative() && getComplexity(
I.getOperand(0)) <
418 getComplexity(
I.getOperand(1)))
419 Changed = !
I.swapOperands();
424 if (
I.isAssociative()) {
434 replaceOperand(
I, 0, A);
435 replaceOperand(
I, 1, V);
447 I.setHasNoUnsignedWrap(
true);
450 I.setHasNoSignedWrap(
true);
460 Value *A =
I.getOperand(0);
467 replaceOperand(
I, 0, V);
468 replaceOperand(
I, 1,
C);
479 if (
I.isAssociative() &&
I.isCommutative()) {
495 replaceOperand(
I, 0, V);
496 replaceOperand(
I, 1,
B);
508 Value *A =
I.getOperand(0);
515 replaceOperand(
I, 0,
B);
516 replaceOperand(
I, 1, V);
542 if (isa<FPMathOperator>(NewBO)) {
548 InsertNewInstWith(NewBO,
I);
550 replaceOperand(
I, 0, NewBO);
551 replaceOperand(
I, 1, CRes);
556 I.setHasNoUnsignedWrap(
true);
574 if (LOp == Instruction::And)
575 return ROp == Instruction::Or || ROp == Instruction::Xor;
578 if (LOp == Instruction::Or)
579 return ROp == Instruction::And;
607 if (isa<Constant>(V))
621 assert(
Op &&
"Expected a binary operator");
622 LHS =
Op->getOperand(0);
623 RHS =
Op->getOperand(1);
633 return Op->getOpcode();
642 assert(A &&
B &&
C &&
D &&
"All values must be provided");
645 Value *RetVal =
nullptr;
656 if (A ==
C || (InnerCommutative && A ==
D)) {
668 RetVal =
Builder.CreateBinOp(InnerOpcode, A, V);
676 if (
B ==
D || (InnerCommutative &&
B ==
C)) {
688 RetVal =
Builder.CreateBinOp(InnerOpcode, V,
B);
699 if (isa<OverflowingBinaryOperator>(RetVal)) {
702 if (isa<OverflowingBinaryOperator>(&
I)) {
703 HasNSW =
I.hasNoSignedWrap();
704 HasNUW =
I.hasNoUnsignedWrap();
706 if (
auto *LOBO = dyn_cast<OverflowingBinaryOperator>(
LHS)) {
707 HasNSW &= LOBO->hasNoSignedWrap();
708 HasNUW &= LOBO->hasNoUnsignedWrap();
711 if (
auto *ROBO = dyn_cast<OverflowingBinaryOperator>(
RHS)) {
712 HasNSW &= ROBO->hasNoSignedWrap();
713 HasNUW &= ROBO->hasNoUnsignedWrap();
726 cast<Instruction>(RetVal)->setHasNoSignedWrap(HasNSW);
729 cast<Instruction>(RetVal)->setHasNoUnsignedWrap(HasNUW);
750 if (Op0 && Op1 && LHSOpcode == RHSOpcode)
785 if (
Value *R = tryFactorizationFolds(
I))
796 auto SQDistributive = SQ.getWithInstruction(&
I).getWithoutUndef();
804 C =
Builder.CreateBinOp(InnerOpcode, L, R);
813 C =
Builder.CreateBinOp(TopLevelOpcode,
B,
C);
822 C =
Builder.CreateBinOp(TopLevelOpcode, A,
C);
835 auto SQDistributive = SQ.getWithInstruction(&
I).getWithoutUndef();
843 A =
Builder.CreateBinOp(InnerOpcode, L, R);
852 A =
Builder.CreateBinOp(TopLevelOpcode, A,
C);
861 A =
Builder.CreateBinOp(TopLevelOpcode, A,
B);
867 return SimplifySelectsFeedingBinaryOp(
I,
LHS,
RHS);
876 if (!LHSIsSelect && !RHSIsSelect)
881 if (isa<FPMathOperator>(&
I)) {
882 FMF =
I.getFastMathFlags();
889 Value *
Cond, *True =
nullptr, *False =
nullptr;
903 return Builder.CreateSelect(
Cond, True, Sub,
I.getName());
907 return Builder.CreateSelect(
Cond, Sub, False,
I.getName());
912 if (LHSIsSelect && RHSIsSelect && A ==
D) {
920 True =
Builder.CreateBinOp(Opcode,
B,
E);
921 else if (True && !False)
922 False =
Builder.CreateBinOp(Opcode,
C,
F);
950 void InstCombinerImpl::freelyInvertAllUsersOf(
Value *
I,
Value *IgnoredUser) {
952 if (U == IgnoredUser)
954 switch (cast<Instruction>(U)->
getOpcode()) {
956 auto *
SI = cast<SelectInst>(U);
958 SI->swapProfMetadata();
961 case Instruction::Br:
962 cast<BranchInst>(U)->swapSuccessors();
964 case Instruction::Xor:
965 replaceInstUsesWith(cast<Instruction>(*U),
I);
969 "canFreelyInvertAllUsersOf() ?");
976 Value *InstCombinerImpl::dyn_castNegVal(
Value *V)
const {
986 if (
C->getType()->getElementType()->isIntegerTy())
990 for (
unsigned i = 0,
e = CV->getNumOperands();
i !=
e; ++
i) {
995 if (isa<UndefValue>(Elt))
998 if (!isa<ConstantInt>(Elt))
1005 if (
auto *CV = dyn_cast<Constant>(V))
1006 if (CV->getType()->isVectorTy() &&
1007 CV->getType()->getScalarType()->isIntegerTy() && CV->getSplatValue())
1025 !
X->getType()->isIntOrIntVectorTy(1))
1038 auto *ConstSO = dyn_cast<Constant>(SO);
1045 ConstOps.push_back(ConstSO);
1046 else if (
auto *
C = dyn_cast<Constant>(
Op))
1047 ConstOps.push_back(
C);
1056 if (
auto *Cast = dyn_cast<CastInst>(&
I))
1057 return Builder.CreateCast(Cast->getOpcode(), SO,
I.getType());
1059 if (
auto *II = dyn_cast<IntrinsicInst>(&
I)) {
1061 "Expected constant-foldable intrinsic");
1064 return Builder.CreateUnaryIntrinsic(IID, SO);
1075 if (
auto *EI = dyn_cast<ExtractElementInst>(&
I))
1076 return Builder.CreateExtractElement(SO, EI->getIndexOperand());
1078 assert(
I.isBinaryOp() &&
"Unexpected opcode for select folding");
1081 bool ConstIsRHS = isa<Constant>(
I.getOperand(1));
1082 Constant *ConstOperand = cast<Constant>(
I.getOperand(ConstIsRHS));
1084 Value *Op0 = SO, *Op1 = ConstOperand;
1090 if (
auto *NewBOI = dyn_cast<Instruction>(NewBO))
1091 NewBOI->copyIRFlags(&
I);
1096 bool FoldWithMultiUse) {
1098 if (!
SI->hasOneUse() && !FoldWithMultiUse)
1101 Value *TV =
SI->getTrueValue();
1102 Value *FV =
SI->getFalseValue();
1103 if (!(isa<Constant>(TV) || isa<Constant>(FV)))
1107 if (
SI->getType()->isIntOrIntVectorTy(1))
1112 if (
auto *BC = dyn_cast<BitCastInst>(&
Op)) {
1113 VectorType *DestTy = dyn_cast<VectorType>(BC->getDestTy());
1114 VectorType *SrcTy = dyn_cast<VectorType>(BC->getSrcTy());
1117 if ((SrcTy ==
nullptr) != (DestTy ==
nullptr))
1132 if (
auto *CI = dyn_cast<CmpInst>(
SI->getCondition())) {
1133 if (CI->hasOneUse()) {
1134 Value *Op0 = CI->getOperand(0), *Op1 = CI->getOperand(1);
1149 if (!A->getType()->isIntOrIntVectorTy() || A->getType() !=
B->getType())
1158 if ((areLooselyEqual(TV, Op0) && areLooselyEqual(FV, Op1)) ||
1159 (areLooselyEqual(FV, Op0) && areLooselyEqual(TV, Op1)))
1167 if (!NewTV && !NewFV)
1180 if (NumPHIValues == 0)
1190 if (UI != &
I && !
I.isIdenticalTo(UI))
1201 Value *NonSimplifiedInVal =
nullptr;
1202 for (
unsigned i = 0;
i != NumPHIValues; ++
i) {
1212 Ops.push_back(InVal);
1214 Ops.push_back(
Op->DoPHITranslation(PN->
getParent(), InBB));
1224 NewPhiValues.push_back(NewVal);
1228 if (isa<PHINode>(InVal))
return nullptr;
1229 if (NonSimplifiedBB)
return nullptr;
1231 NonSimplifiedBB = InBB;
1232 NonSimplifiedInVal = InVal;
1233 NewPhiValues.push_back(
nullptr);
1237 if (isa<InvokeInst>(InVal))
1238 if (cast<Instruction>(InVal)->
getParent() == NonSimplifiedBB)
1255 if (NonSimplifiedBB !=
nullptr) {
1258 !DT.isReachableFromEntry(NonSimplifiedBB))
1264 InsertNewInstBefore(NewPN, *PN);
1270 if (NonSimplifiedBB) {
1274 U = NonSimplifiedInVal;
1278 InsertNewInstBefore(Clone, *NonSimplifiedBB->
getTerminator());
1281 for (
unsigned i = 0;
i != NumPHIValues; ++
i) {
1282 if (NewPhiValues[
i])
1290 if (
User == &
I)
continue;
1291 replaceInstUsesWith(*
User, NewPN);
1292 eraseInstFromFunction(*
User);
1294 return replaceInstUsesWith(
I, NewPN);
1301 auto *Phi0 = dyn_cast<PHINode>(BO.
getOperand(0));
1302 auto *Phi1 = dyn_cast<PHINode>(BO.
getOperand(1));
1303 if (!Phi0 || !Phi1 || !Phi0->hasOneUse() || !Phi1->hasOneUse() ||
1304 Phi0->getNumOperands() != 2 || Phi1->getNumOperands() != 2)
1316 ConstBB = Phi0->getIncomingBlock(0);
1317 OtherBB = Phi0->getIncomingBlock(1);
1319 ConstBB = Phi0->getIncomingBlock(1);
1320 OtherBB = Phi0->getIncomingBlock(0);
1330 auto *PredBlockBranch = dyn_cast<BranchInst>(OtherBB->
getTerminator());
1331 if (!PredBlockBranch || PredBlockBranch->isConditional() ||
1332 !DT.isReachableFromEntry(OtherBB))
1338 for (
auto BBIter = BO.
getParent()->
begin(); &*BBIter != &BO; ++BBIter)
1349 Builder.SetInsertPoint(PredBlockBranch);
1351 Phi0->getIncomingValueForBlock(OtherBB),
1352 Phi1->getIncomingValueForBlock(OtherBB));
1353 if (
auto *NotFoldedNewBO = dyn_cast<BinaryOperator>(NewBO))
1354 NotFoldedNewBO->copyIRFlags(&BO);
1364 if (!isa<Constant>(
I.getOperand(1)))
1367 if (
auto *Sel = dyn_cast<SelectInst>(
I.getOperand(0))) {
1370 }
else if (
auto *PN = dyn_cast<PHINode>(
I.getOperand(0))) {
1389 APInt Offset(
DL.getIndexTypeSizeInBits(PtrTy), IntOffset);
1391 if (!Offset.isZero())
1403 if (
GEP.hasAllZeroIndices() && !Src.hasAllZeroIndices() &&
1412 assert(isa<IntegerType>(Val->
getType()) &&
"Can only descale integers!");
1414 Scale.
getBitWidth() &&
"Scale not compatible with value!");
1418 NoSignedWrap =
true;
1450 std::pair<Instruction *, unsigned> Parent;
1454 bool RequireNoSignedWrap =
false;
1459 for (;;
Op = Parent.first->getOperand(Parent.second)) {
1462 APInt Quotient(Scale), Remainder(Scale);
1469 NoSignedWrap =
true;
1477 if (RequireNoSignedWrap && !NoSignedWrap)
1488 if (CI->getValue() == Scale) {
1496 if (!
Op->hasOneUse())
1499 Parent = std::make_pair(BO, 1);
1505 if (!
Op->hasOneUse())
1508 Parent = std::make_pair(BO, 0);
1512 if (logScale > 0 && BO->
getOpcode() == Instruction::Shl &&
1516 if (RequireNoSignedWrap && !NoSignedWrap)
1520 int32_t Amt = cast<ConstantInt>(BO->
getOperand(1))->
1524 if (Amt == logScale) {
1535 Parent = std::make_pair(BO, 1);
1541 if (!
Op->hasOneUse())
1544 if (
CastInst *Cast = dyn_cast<CastInst>(
Op)) {
1545 if (Cast->getOpcode() == Instruction::SExt) {
1547 unsigned SmallSize = Cast->getSrcTy()->getPrimitiveSizeInBits();
1559 RequireNoSignedWrap =
true;
1562 Parent = std::make_pair(Cast, 0);
1567 if (Cast->getOpcode() == Instruction::Trunc) {
1574 if (RequireNoSignedWrap)
1578 unsigned LargeSize = Cast->getSrcTy()->getPrimitiveSizeInBits();
1579 Parent = std::make_pair(Cast, 0);
1580 Scale = Scale.
sext(LargeSize);
1581 if (logScale + 1 == (int32_t)Cast->getType()->getPrimitiveSizeInBits())
1594 NoSignedWrap =
true;
1608 assert(Parent.first->hasOneUse() &&
"Drilled down when more than one use!");
1609 assert(
Op != Parent.first->getOperand(Parent.second) &&
1610 "Descaling was a no-op?");
1611 replaceOperand(*Parent.first, Parent.second,
Op);
1612 Worklist.push(Parent.first);
1627 NoSignedWrap &= OpNoSignedWrap;
1628 if (NoSignedWrap != OpNoSignedWrap) {
1630 Worklist.push(Ancestor);
1632 }
else if (Ancestor->
getOpcode() == Instruction::Trunc) {
1636 NoSignedWrap =
false;
1638 assert((Ancestor->
getOpcode() != Instruction::SExt || NoSignedWrap) &&
1639 "Failed to keep proper track of nsw flags while drilling down?");
1641 if (Ancestor == Val)
1646 assert(Ancestor->
hasOneUse() &&
"Drilled down when more than one use!");
1652 if (!isa<VectorType>(Inst.
getType()))
1658 cast<VectorType>(Inst.
getType())->getElementCount());
1660 cast<VectorType>(Inst.
getType())->getElementCount());
1665 Value *L0, *L1, *R0, *R1;
1670 cast<ShuffleVectorInst>(
LHS)->isConcat() &&
1671 cast<ShuffleVectorInst>(
RHS)->isConcat()) {
1678 if (
auto *BO = dyn_cast<BinaryOperator>(NewBO0))
1681 if (
auto *BO = dyn_cast<BinaryOperator>(NewBO1))
1688 if (
auto *BO = dyn_cast<BinaryOperator>(V))
1692 M, Intrinsic::experimental_vector_reverse, V->
getType());
1705 return createBinOpReverse(V1,
V2);
1709 return createBinOpReverse(V1,
RHS);
1713 return createBinOpReverse(
LHS,
V2);
1723 if (
auto *BO = dyn_cast<BinaryOperator>(XY))
1735 return createBinOpShuffle(V1,
V2,
Mask);
1744 auto *LShuf = cast<ShuffleVectorInst>(
LHS);
1745 auto *RShuf = cast<ShuffleVectorInst>(
RHS);
1750 if (LShuf->isSelect() &&
1752 RShuf->isSelect() &&
1770 auto *InstVTy = dyn_cast<FixedVectorType>(Inst.
getType());
1775 cast<FixedVectorType>(V1->
getType())->getNumElements() <=
1776 InstVTy->getNumElements()) {
1778 "Shuffle should not change scalar type");
1785 bool ConstOp1 = isa<Constant>(
RHS);
1787 unsigned SrcVecNumElts =
1788 cast<FixedVectorType>(V1->
getType())->getNumElements();
1791 bool MayChange =
true;
1792 unsigned NumElts = InstVTy->getNumElements();
1793 for (
unsigned I = 0;
I < NumElts; ++
I) {
1795 if (ShMask[
I] >= 0) {
1796 assert(ShMask[
I] < (
int)NumElts &&
"Not expecting narrowing shuffle");
1804 if (!CElt || (!isa<UndefValue>(NewCElt) && NewCElt != CElt) ||
1805 I >= SrcVecNumElts) {
1809 NewVecC[ShMask[
I]] = CElt;
1820 if (
I >= SrcVecNumElts || ShMask[
I] < 0) {
1837 NewC = getSafeVectorConstantForBinop(Opcode, NewC, ConstOp1);
1841 Value *NewLHS = ConstOp1 ? V1 : NewC;
1842 Value *NewRHS = ConstOp1 ? NewC : V1;
1843 return createBinOpShuffle(NewLHS, NewRHS,
Mask);
1850 if (isa<ShuffleVectorInst>(
RHS))
1878 Value *NewSplat =
Builder.CreateShuffleVector(NewBO, NewMask);
1883 if (isa<FPMathOperator>(R)) {
1884 R->copyFastMathFlags(&Inst);
1887 if (
auto *NewInstBO = dyn_cast<BinaryOperator>(NewBO))
1888 NewInstBO->copyIRFlags(R);
1917 cast<Operator>(Op1)->getOpcode() == CastOpc &&
1918 (Op0->
hasOneUse() || Op1->hasOneUse()))) {
1942 if (
auto *NewBinOp = dyn_cast<BinaryOperator>(NarrowBO)) {
1944 NewBinOp->setHasNoSignedWrap();
1946 NewBinOp->setHasNoUnsignedWrap();
1964 if (!
GEP.hasAllConstantIndices())
1979 bool IsInBounds =
GEP.isInBounds();
1980 Type *Ty =
GEP.getSourceElementType();
1981 Value *NewTrueC =
Builder.CreateGEP(Ty, TrueC, IndexC,
"", IsInBounds);
1982 Value *NewFalseC =
Builder.CreateGEP(Ty, FalseC, IndexC,
"", IsInBounds);
1994 if (Src->getResultElementType() ==
GEP.getSourceElementType() &&
1995 Src->getNumOperands() == 2 &&
GEP.getNumOperands() == 2 &&
1998 Value *SO1 = Src->getOperand(1);
2002 if (
Loop *L = LI->getLoopFor(
GEP.getParent())) {
2006 if (L->isLoopInvariant(GO1) && !L->isLoopInvariant(SO1)) {
2010 bool IsInBounds = Src->isInBounds() &&
GEP.isInBounds() &&
2014 Builder.SetInsertPoint(cast<Instruction>(Src));
2016 Src->getPointerOperand(), GO1,
2017 Src->getName(), IsInBounds);
2019 GEP.getSourceElementType(), NewSrc, {SO1});
2030 if (
auto *SrcGEP = dyn_cast<GEPOperator>(Src->getOperand(0)))
2036 Type *PtrTy = Src->getType()->getScalarType();
2038 (Src->hasOneUse() || Src->hasAllConstantIndices())) {
2042 bool IsFirstType =
true;
2043 unsigned NumVarIndices = 0;
2044 for (
auto Pair :
enumerate(Src->indices())) {
2045 if (!isa<ConstantInt>(Pair.value())) {
2047 IsFirstType =
false;
2048 NumVarIndices = Pair.index() + 1;
2054 APInt Offset(
DL.getIndexTypeSizeInBits(PtrTy), 0);
2055 if (NumVarIndices != Src->getNumIndices()) {
2057 if (isa<ScalableVectorType>(
BaseType))
2062 ConstantIndices.push_back(
2065 Offset +=
DL.getIndexedOffsetInType(
BaseType, ConstantIndices);
2069 if (!
GEP.accumulateConstantOffset(
DL, Offset))
2072 APInt OffsetOld = Offset;
2076 if (!Offset.isZero() || (!IsFirstType && !ConstIndices[0].isZero())) {
2079 if (Src->hasAllConstantIndices())
2082 Builder.getInt8Ty(), Src->getOperand(0),
2085 Builder.getInt8Ty(), Src->getOperand(0),
2093 Src->getNumIndices() - NumVarIndices));
2100 IsInBounds &= Idx.isNonNegative() == ConstIndices[0].isNonNegative();
2105 Src->getOperand(0), Indices,
2108 Src->getOperand(0), Indices,
2112 if (Src->getResultElementType() !=
GEP.getSourceElementType())
2118 bool EndsWithSequential =
false;
2121 EndsWithSequential =
I.isSequential();
2124 if (EndsWithSequential) {
2127 Value *SO1 = Src->getOperand(Src->getNumOperands()-1);
2145 if (Src->getNumOperands() == 2) {
2147 replaceOperand(
GEP, 0, Src->getOperand(0));
2148 replaceOperand(
GEP, 1, Sum);
2151 Indices.
append(Src->op_begin()+1, Src->op_end()-1);
2152 Indices.push_back(Sum);
2154 }
else if (isa<Constant>(*
GEP.idx_begin()) &&
2155 cast<Constant>(*
GEP.idx_begin())->isNullValue() &&
2156 Src->getNumOperands() != 1) {
2158 Indices.
append(Src->op_begin()+1, Src->op_end());
2162 if (!Indices.empty())
2165 Src->getSourceElementType(), Src->getOperand(0), Indices,
2168 Src->getOperand(0), Indices,
2183 Type *GEPEltType =
GEP.getSourceElementType();
2191 auto areMatchingArrayAndVecTypes = [](
Type *ArrTy,
Type *VecTy,
2193 auto *VecVTy = cast<FixedVectorType>(VecTy);
2196 DL.getTypeAllocSize(ArrTy) ==
DL.getTypeAllocSize(VecTy);
2198 if (
GEP.getNumOperands() == 3 &&
2199 ((GEPEltType->
isArrayTy() && isa<FixedVectorType>(SrcEltType) &&
2200 areMatchingArrayAndVecTypes(GEPEltType, SrcEltType,
DL)) ||
2201 (isa<FixedVectorType>(GEPEltType) && SrcEltType->
isArrayTy() &&
2202 areMatchingArrayAndVecTypes(SrcEltType, GEPEltType,
DL)))) {
2217 return replaceInstUsesWith(
GEP, NGEP);
2225 unsigned OffsetBits =
DL.getIndexTypeSizeInBits(
GEP.getType());
2226 APInt Offset(OffsetBits, 0);
2234 if (!isa<BitCastInst>(
SrcOp) &&
GEP.accumulateConstantOffset(
DL, Offset) &&
2241 if (isa<AllocaInst>(
SrcOp)) {
2247 replaceInstUsesWith(*BCI,
I);
2267 return replaceInstUsesWith(
GEP, NGEP);
2282 Type *GEPType =
GEP.getType();
2283 Type *GEPEltType =
GEP.getSourceElementType();
2284 bool IsGEPSrcEleScalable = isa<ScalableVectorType>(GEPEltType);
2286 SQ.getWithInstruction(&
GEP)))
2287 return replaceInstUsesWith(
GEP, V);
2292 if (
auto *GEPFVTy = dyn_cast<FixedVectorType>(GEPType)) {
2293 auto VWidth = GEPFVTy->getNumElements();
2294 APInt UndefElts(VWidth, 0);
2296 if (
Value *V = SimplifyDemandedVectorElts(&
GEP, AllOnesEltMask,
2299 return replaceInstUsesWith(
GEP, V);
2310 bool MadeChange =
false;
2314 Type *NewScalarIndexTy =
2315 DL.getIndexType(
GEP.getPointerOperandType()->getScalarType());
2324 Type *IndexTy = (*I)->getType();
2325 Type *NewIndexType =
2328 cast<VectorType>(IndexTy)->getElementCount())
2334 if (EltTy->
isSized() &&
DL.getTypeAllocSize(EltTy).isZero())
2340 if (IndexTy != NewIndexType) {
2344 *
I =
Builder.CreateIntCast(*
I, NewIndexType,
true);
2352 if (
auto *PN = dyn_cast<PHINode>(PtrOp)) {
2353 auto *Op1 = dyn_cast<GetElementPtrInst>(PN->getOperand(0));
2368 for (
auto I = PN->op_begin()+1,
E = PN->op_end();
I !=
E; ++
I) {
2369 auto *Op2 = dyn_cast<GetElementPtrInst>(*
I);
2370 if (!Op2 || Op1->getNumOperands() != Op2->getNumOperands() ||
2371 Op1->getSourceElementType() != Op2->getSourceElementType())
2379 Type *CurTy =
nullptr;
2381 for (
unsigned J = 0,
F = Op1->getNumOperands(); J !=
F; ++J) {
2382 if (Op1->getOperand(J)->getType() != Op2->getOperand(J)->getType())
2385 if (Op1->getOperand(J) != Op2->getOperand(J)) {
2394 assert(CurTy &&
"No current type?");
2414 CurTy = Op1->getSourceElementType();
2426 if (DI != -1 && !PN->hasOneUse())
2429 auto *NewGEP = cast<GetElementPtrInst>(Op1->clone());
2441 NewPN =
Builder.CreatePHI(Op1->getOperand(DI)->getType(),
2442 PN->getNumOperands());
2445 for (
auto &
I : PN->operands())
2446 NewPN->
addIncoming(cast<GEPOperator>(
I)->getOperand(DI),
2447 PN->getIncomingBlock(
I));
2449 NewGEP->setOperand(DI, NewPN);
2452 NewGEP->insertInto(
GEP.getParent(),
GEP.getParent()->getFirstInsertionPt());
2453 return replaceOperand(
GEP, 0, NewGEP);
2456 if (
auto *Src = dyn_cast<GEPOperator>(PtrOp))
2462 if (
GEP.getNumIndices() == 1 && !IsGEPSrcEleScalable) {
2463 unsigned AS =
GEP.getPointerAddressSpace();
2464 if (
GEP.getOperand(1)->getType()->getScalarSizeInBits() ==
2465 DL.getIndexSizeInBits(AS)) {
2466 uint64_t TyAllocSize =
DL.getTypeAllocSize(GEPEltType).getFixedValue();
2468 bool Matched =
false;
2471 if (TyAllocSize == 1) {
2472 V =
GEP.getOperand(1);
2474 }
else if (
match(
GEP.getOperand(1),
2476 if (TyAllocSize == 1ULL <<
C)
2478 }
else if (
match(
GEP.getOperand(1),
2480 if (TyAllocSize ==
C)
2508 if (StrippedPtr != PtrOp && !StrippedPtrTy->
isOpaque()) {
2509 bool HasZeroPointerIndex =
false;
2512 if (
auto *
C = dyn_cast<ConstantInt>(
GEP.getOperand(1)))
2513 HasZeroPointerIndex =
C->isZero();
2522 if (HasZeroPointerIndex) {
2523 if (
auto *CATy = dyn_cast<ArrayType>(GEPEltType)) {
2525 if (CATy->getElementType() == StrippedPtrEltTy) {
2529 StrippedPtrEltTy, StrippedPtr, Idx,
GEP.getName());
2542 if (
auto *XATy = dyn_cast<ArrayType>(StrippedPtrEltTy)) {
2544 if (CATy->getElementType() == XATy->getElementType()) {
2551 GEP.setSourceElementType(XATy);
2552 return replaceOperand(
GEP, 0, StrippedPtr);
2565 Builder.CreateGEP(StrippedPtrEltTy, StrippedPtr, Idx,
2566 GEP.getName(),
GEP.isInBounds());
2571 }
else if (
GEP.getNumOperands() == 2 && !IsGEPSrcEleScalable) {
2579 DL.getTypeAllocSize(GEPEltType)) {
2580 Type *IdxType =
DL.getIndexType(GEPType);
2582 Value *NewGEP =
Builder.CreateGEP(StrippedPtrEltTy, StrippedPtr, Idx,
2583 GEP.getName(),
GEP.isInBounds());
2596 uint64_t ResSize =
DL.getTypeAllocSize(GEPEltType).getFixedValue();
2598 DL.getTypeAllocSize(StrippedPtrEltTy).getFixedValue();
2599 if (ResSize && SrcSize % ResSize == 0) {
2602 uint64_t Scale = SrcSize / ResSize;
2608 "Index type does not match the Data Layout preferences");
2616 Builder.CreateGEP(StrippedPtrEltTy, StrippedPtr, NewIdx,
2617 GEP.getName(),
GEP.isInBounds() && NSW);
2634 uint64_t ResSize =
DL.getTypeAllocSize(GEPEltType).getFixedValue();
2638 if (ResSize && ArrayEltSize % ResSize == 0) {
2641 uint64_t Scale = ArrayEltSize / ResSize;
2647 "Index type does not match the Data Layout preferences");
2654 Type *IndTy =
DL.getIndexType(GEPType);
2658 Builder.CreateGEP(StrippedPtrEltTy, StrippedPtr, Off,
2659 GEP.getName(),
GEP.isInBounds() && NSW);
2672 Value *ASCStrippedPtrOp = PtrOp;
2673 if (
auto *ASC = dyn_cast<AddrSpaceCastInst>(PtrOp)) {
2678 if (
auto *BC = dyn_cast<BitCastInst>(ASC->getOperand(0)))
2679 ASCStrippedPtrOp = BC;
2682 if (
auto *BCI = dyn_cast<BitCastInst>(ASCStrippedPtrOp))
2686 if (!
GEP.isInBounds()) {
2689 APInt BasePtrOffset(IdxWidth, 0);
2690 Value *UnderlyingPtrOp =
2693 if (
auto *AI = dyn_cast<AllocaInst>(UnderlyingPtrOp)) {
2694 if (
GEP.accumulateConstantOffset(
DL, BasePtrOffset) &&
2698 DL.getTypeAllocSize(AI->getAllocatedType()).getKnownMinValue());
2699 if (BasePtrOffset.
ule(AllocSize)) {
2701 GEP.getSourceElementType(), PtrOp, Indices,
GEP.getName());
2715 if (isa<ConstantPointerNull>(V))
2717 if (
auto *LI = dyn_cast<LoadInst>(V))
2718 return isa<GlobalVariable>(LI->getPointerOperand());
2742 return Dest && Dest->Ptr == UsedV;
2750 Worklist.push_back(AI);
2756 switch (
I->getOpcode()) {
2761 case Instruction::AddrSpaceCast:
2762 case Instruction::BitCast:
2763 case Instruction::GetElementPtr:
2765 Worklist.push_back(
I);
2768 case Instruction::ICmp: {
2775 unsigned OtherIndex = (ICI->
getOperand(0) == PI) ? 1 : 0;
2789 case Intrinsic::memmove:
2791 case Intrinsic::memset: {
2793 if (
MI->isVolatile() ||
MI->getRawDest() != PI)
2797 case Intrinsic::assume:
2798 case Intrinsic::invariant_start:
2799 case Intrinsic::invariant_end:
2800 case Intrinsic::lifetime_start:
2801 case Intrinsic::lifetime_end:
2802 case Intrinsic::objectsize:
2805 case Intrinsic::launder_invariant_group:
2806 case Intrinsic::strip_invariant_group:
2808 Worklist.push_back(
I);
2829 Worklist.push_back(
I);
2837 if (
SI->isVolatile() ||
SI->getPointerOperand() != PI)
2845 }
while (!Worklist.empty());
2867 std::unique_ptr<DIBuilder> DIB;
2868 if (isa<AllocaInst>(
MI)) {
2874 for (
unsigned i = 0,
e =
Users.size();
i !=
e; ++
i) {
2886 replaceInstUsesWith(*
I, Result);
2887 eraseInstFromFunction(*
I);
2892 for (
unsigned i = 0,
e =
Users.size();
i !=
e; ++
i) {
2899 replaceInstUsesWith(*
C,
2901 C->isFalseWhenEqual()));
2902 }
else if (
auto *
SI = dyn_cast<StoreInst>(
I)) {
2903 for (
auto *DVI : DVIs)
2904 if (DVI->isAddressOfVariable())
2911 eraseInstFromFunction(*
I);
2944 for (
auto *DVI : DVIs)
2945 if (DVI->isAddressOfVariable() || DVI->getExpression()->startsWithDeref())
2946 DVI->eraseFromParent();
2948 return eraseInstFromFunction(
MI);
2992 if (FreeInstrBB->
size() != 2) {
2994 if (&Inst == &FI || &Inst == FreeInstrBBTerminator)
2996 auto *Cast = dyn_cast<CastInst>(&Inst);
2997 if (!Cast || !Cast->isNoopCast(
DL))
3018 "Broken CFG: missing edge from predecessor to successor");
3023 if (&Instr == FreeInstrBBTerminator)
3025 Instr.moveBefore(TI);
3028 "Only the branch instruction should remain");
3040 Attribute Dereferenceable =
Attrs.getParamAttr(0, Attribute::Dereferenceable);
3041 if (Dereferenceable.
isValid()) {
3044 Attribute::Dereferenceable);
3054 if (isa<UndefValue>(
Op)) {
3056 CreateNonTerminatorUnreachable(&FI);
3057 return eraseInstFromFunction(FI);
3062 if (isa<ConstantPointerNull>(
Op))
3063 return eraseInstFromFunction(FI);
3070 return eraseInstFromFunction(*replaceInstUsesWith(*CI, ReallocatedOp));
3084 if (TLI.getLibFunc(FI, Func) && TLI.has(Func) && Func == LibFunc_free)
3093 if (
auto *CI = dyn_cast<CallInst>(V))
3094 return CI->isMustTailCall();
3104 if (!VTy->
isIntegerTy() || isa<Constant>(ResultOp))
3115 return replaceOperand(RI, 0,
3126 while (
Instruction *Prev =
I.getPrevNonDebugInstruction()) {
3131 if (Prev->isEHPad())
3142 eraseInstFromFunction(*Prev);
3144 assert(
I.getParent()->sizeWithoutDebug() == 1 &&
"The block is now empty.");
3158 return BBI->isDebugOrPseudoInst() ||
3159 (isa<BitCastInst>(BBI) && BBI->getType()->isPointerTy());
3164 if (BBI != FirstInstr)
3166 }
while (BBI != FirstInstr && IsNoopInstrForStoreMerging(BBI));
3168 return dyn_cast<StoreInst>(BBI);
3172 if (mergeStoreIntoSuccessor(*
SI))
3180 return visitUnconditionalBranchInst(BI);
3188 return replaceOperand(BI, 0,
X);
3195 if (isa<SelectInst>(
Cond) &&
3201 return replaceOperand(BI, 0,
Or);
3212 !isCanonicalPredicate(Pred)) {
3214 auto *Cmp = cast<CmpInst>(
Cond);
3230 for (
auto Case :
SI.cases()) {
3232 assert(isa<ConstantInt>(NewCase) &&
3233 "Result of expression should be constant");
3234 Case.setValue(cast<ConstantInt>(NewCase));
3236 return replaceOperand(
SI, 0, Op0);
3245 for (
const auto &
C :
SI.cases()) {
3247 LeadingKnownZeros,
C.getCaseValue()->getValue().countLeadingZeros());
3249 LeadingKnownOnes,
C.getCaseValue()->getValue().countLeadingOnes());
3258 if (NewWidth > 0 && NewWidth < Known.
getBitWidth() &&
3259 shouldChangeType(Known.
getBitWidth(), NewWidth)) {
3264 for (
auto Case :
SI.cases()) {
3265 APInt TruncatedCase = Case.getCaseValue()->getValue().
trunc(NewWidth);
3268 return replaceOperand(
SI, 0, NewCond);
3281 const APInt *
C =
nullptr;
3283 if (*EV.
idx_begin() == 0 && (OvID == Intrinsic::smul_with_overflow ||
3284 OvID == Intrinsic::umul_with_overflow)) {
3289 if (
C->isPowerOf2()) {
3290 return BinaryOperator::CreateShl(
3300 if (!WO->hasOneUse())
3310 eraseInstFromFunction(*WO);
3314 assert(*EV.
idx_begin() == 1 &&
"Unexpected extract index for overflow inst");
3317 if (OvID == Intrinsic::usub_with_overflow)
3322 if (OvID == Intrinsic::smul_with_overflow &&
3323 WO->getLHS()->getType()->isIntOrIntVectorTy(1))
3324 return BinaryOperator::CreateAnd(WO->getLHS(), WO->getRHS());
3333 WO->getBinaryOp(), *
C, WO->getNoWrapKind());
3338 auto *OpTy = WO->getRHS()->getType();
3339 auto *NewLHS = WO->getLHS();
3353 return replaceInstUsesWith(EV, Agg);
3356 SQ.getWithInstruction(&EV)))
3357 return replaceInstUsesWith(EV, V);
3361 const unsigned *exti, *exte, *insi, *inse;
3362 for (exti = EV.
idx_begin(), insi =
IV->idx_begin(),
3363 exte = EV.
idx_end(), inse =
IV->idx_end();
3364 exti != exte && insi != inse;
3378 if (exti == exte && insi == inse)
3383 return replaceInstUsesWith(EV,
IV->getInsertedValueOperand());
3393 Value *NewEV =
Builder.CreateExtractValue(
IV->getAggregateOperand(),
3411 if (
Instruction *R = foldExtractOfOverflowIntrinsic(EV))
3414 if (
LoadInst *L = dyn_cast<LoadInst>(Agg)) {
3420 if (L->isSimple() && L->hasOneUse()) {
3424 Indices.push_back(
Builder.getInt32(0));
3425 for (
unsigned Idx : EV.
indices())
3426 Indices.push_back(
Builder.getInt32(Idx));
3432 L->getPointerOperand(), Indices);
3436 NL->setAAMetadata(L->getAAMetadata());
3439 return replaceInstUsesWith(EV,
NL);
3443 if (
auto *PN = dyn_cast<PHINode>(Agg))
3460 switch (Personality) {
3489 cast<ArrayType>(
LHS->
getType())->getNumElements()
3491 cast<ArrayType>(
RHS->
getType())->getNumElements();
3503 bool MakeNewInstruction =
false;
3509 bool isLastClause =
i + 1 ==
e;
3517 if (AlreadyCaught.
insert(TypeInfo).second) {
3519 NewClauses.push_back(CatchClause);
3522 MakeNewInstruction =
true;
3529 MakeNewInstruction =
true;
3530 CleanupFlag =
false;
3549 if (!NumTypeInfos) {
3550 NewClauses.push_back(FilterClause);
3552 MakeNewInstruction =
true;
3553 CleanupFlag =
false;
3557 bool MakeNewFilter =
false;
3559 if (isa<ConstantAggregateZero>(FilterClause)) {
3561 assert(NumTypeInfos > 0 &&
"Should have handled empty filter already!");
3567 MakeNewInstruction =
true;
3573 NewFilterElts.push_back(TypeInfo);
3574 if (NumTypeInfos > 1)
3575 MakeNewFilter =
true;
3579 NewFilterElts.
reserve(NumTypeInfos);
3584 bool SawCatchAll =
false;
3585 for (
unsigned j = 0;
j != NumTypeInfos; ++
j) {
3613 if (SeenInFilter.
insert(TypeInfo).second)
3614 NewFilterElts.push_back(cast<Constant>(Elt));
3619 MakeNewInstruction =
true;
3624 if (NewFilterElts.size() < NumTypeInfos)
3625 MakeNewFilter =
true;
3627 if (MakeNewFilter) {
3629 NewFilterElts.size());
3631 MakeNewInstruction =
true;
3634 NewClauses.push_back(FilterClause);
3640 if (MakeNewFilter && !NewFilterElts.size()) {
3641 assert(MakeNewInstruction &&
"New filter but not a new instruction!");
3642 CleanupFlag =
false;
3653 for (
unsigned i = 0,
e = NewClauses.size();
i + 1 <
e; ) {
3656 for (
j =
i;
j !=
e; ++
j)
3657 if (!isa<ArrayType>(NewClauses[
j]->
getType()))
3663 for (
unsigned k =
i; k + 1 <
j; ++k)
3669 MakeNewInstruction =
true;
3688 for (
unsigned i = 0;
i + 1 < NewClauses.size(); ++
i) {
3698 for (
unsigned j = NewClauses.size() - 1;
j !=
i; --
j) {
3699 Value *LFilter = NewClauses[
j];
3710 NewClauses.
erase(J);
3711 MakeNewInstruction =
true;
3721 if (isa<ConstantAggregateZero>(LFilter)) {
3724 if (isa<ConstantAggregateZero>(
Filter)) {
3725 assert(FElts <= LElts &&
"Should have handled this case earlier!");
3727 NewClauses.
erase(J);
3728 MakeNewInstruction =
true;
3734 if (isa<ConstantAggregateZero>(
Filter)) {
3737 assert(FElts > 0 &&
"Should have eliminated the empty filter earlier!");
3738 for (
unsigned l = 0;
l != LElts; ++
l)
3741 NewClauses.
erase(J);
3742 MakeNewInstruction =
true;
3753 bool AllFound =
true;
3754 for (
unsigned f = 0;
f != FElts; ++
f) {
3757 for (
unsigned l = 0;
l != LElts; ++
l) {
3759 if (LTypeInfo == FTypeInfo) {
3769 NewClauses.
erase(J);
3770 MakeNewInstruction =
true;
3778 if (MakeNewInstruction) {
3781 for (
unsigned i = 0,
e = NewClauses.size();
i !=
e; ++
i)
3786 if (NewClauses.empty())
3795 assert(!CleanupFlag &&
"Adding a cleanup, not removing one?!");
3820 auto *OrigOpInst = dyn_cast<Instruction>(OrigOp);
3825 if (!OrigOpInst || !OrigOpInst->hasOneUse() || isa<PHINode>(OrigOp))
3839 Use *MaybePoisonOperand =
nullptr;
3840 for (
Use &U : OrigOpInst->operands()) {
3841 if (isa<MetadataAsValue>(U.get()) ||
3844 if (!MaybePoisonOperand)
3845 MaybePoisonOperand = &U;
3850 OrigOpInst->dropPoisonGeneratingFlagsAndMetadata();
3853 if (!MaybePoisonOperand)
3856 Builder.SetInsertPoint(OrigOpInst);
3857 auto *FrozenMaybePoisonOperand =
Builder.CreateFreeze(
3858 MaybePoisonOperand->get(), MaybePoisonOperand->get()->
getName() +
".fr");
3860 replaceUse(*MaybePoisonOperand, FrozenMaybePoisonOperand);
3871 Use *StartU =
nullptr;
3876 Worklist.push_back(U.get());
3886 if (!StartU || Worklist.empty())
3889 Value *StartV = StartU->get();
3899 while (!Worklist.empty()) {
3901 if (!Visited.
insert(V).second)
3904 if (Visited.
size() > 32)
3916 DropFlags.push_back(
I);
3921 I->dropPoisonGeneratingFlagsAndMetadata();
3923 if (StartNeedsFreeze) {
3927 replaceUse(*StartU, FrozenStartV);
3929 return replaceInstUsesWith(FI, PN);
3935 if (isa<Constant>(
Op) ||
Op->hasOneUse())
3944 if (isa<Argument>(
Op)) {
3953 bool Changed =
false;
3954 if (&FI != MoveBefore) {
3959 Op->replaceUsesWithIf(&FI, [&](
Use &U) ->
bool {
3960 bool Dominates = DT.dominates(&FI, U);
3961 Changed |= Dominates;
3969 Value *Op0 =
I.getOperand(0);
3972 return replaceInstUsesWith(
I, V);
3975 if (
auto *PN = dyn_cast<PHINode>(Op0)) {
3982 if (
Value *NI = pushFreezeToPreventPoisonFromPropagating(
I))
3983 return replaceInstUsesWith(
I, NI);
3998 auto getUndefReplacement = [&
I](
Type *Ty) {
4001 for (
const auto *U :
I.users()) {
4010 else if (BestValue !=
C)
4011 BestValue = NullValue;
4013 assert(BestValue &&
"Must have at least one use");
4018 return replaceInstUsesWith(
I, getUndefReplacement(
I.getType()));
4022 Constant *ReplaceC = getUndefReplacement(
I.getType()->getScalarType());
4027 if (freezeOtherUses(
I))
4037 auto *CB = dyn_cast<CallBase>(
I);
4056 for (
const User *U :
I.users()) {
4057 if (Visited.
insert(U).second)
4058 AllocaUsers.push_back(U);
4062 while (!AllocaUsers.empty()) {
4063 auto *UserI = cast<Instruction>(AllocaUsers.
pop_back_val());
4064 if (isa<BitCastInst>(UserI) || isa<GetElementPtrInst>(UserI) ||
4065 isa<AddrSpaceCastInst>(UserI)) {
4086 if (isa<PHINode>(
I) ||
I->isEHPad() ||
I->mayThrow() || !
I->willReturn() ||
4094 if (isa<AllocaInst>(
I))
4102 if (
auto *CI = dyn_cast<CallInst>(
I)) {
4103 if (CI->isConvergent())
4109 if (
I->mayWriteToMemory()) {
4116 if (
I->mayReadFromMemory()) {
4123 E =
I->getParent()->end();
4125 if (Scan->mayWriteToMemory())
4129 I->dropDroppableUses([DestBlock](
const Use *U) {
4130 if (
auto *
I = dyn_cast<Instruction>(U->getUser()))
4131 return I->getParent() != DestBlock;
4138 I->moveBefore(&*InsertPos);
4152 if (DVI->getParent() == SrcBlock)
4153 DbgUsersToSink.push_back(DVI);
4155 [](
auto *A,
auto *
B) {
return B->comesBefore(A); });
4159 for (
auto *
User : DbgUsersToSink) {
4164 if (isa<DbgDeclareInst>(
User))
4169 User->getDebugLoc()->getInlinedAt());
4171 if (!SunkVariables.
insert(DbgUserVariable).second)
4176 if (isa<DbgAssignIntrinsic>(
User))
4179 DIIClones.emplace_back(cast<DbgVariableIntrinsic>(
User->clone()));
4180 if (isa<DbgDeclareInst>(
User) && isa<CastInst>(
I))
4181 DIIClones.back()->replaceVariableLocationOp(
I,
I->getOperand(0));
4186 if (!DIIClones.empty()) {
4191 DIIClone->insertBefore(&*InsertPos);
4200 while (!Worklist.isEmpty()) {
4209 eraseInstFromFunction(*
I);
4218 if (
I ==
nullptr)
continue;
4222 eraseInstFromFunction(*
I);
4231 if (!
I->use_empty() &&
4232 (
I->getNumOperands() == 0 || isa<Constant>(
I->getOperand(0)))) {
4238 replaceInstUsesWith(*
I,
C);
4241 eraseInstFromFunction(*
I);
4242 MadeIRChange =
true;
4250 auto getOptionalSinkBlockForInst =
4251 [
this](
Instruction *
I) -> std::optional<BasicBlock *> {
4253 return std::nullopt;
4257 unsigned NumUsers = 0;
4259 for (
auto *U :
I->users()) {
4260 if (U->isDroppable())
4263 return std::nullopt;
4267 if (
PHINode *PN = dyn_cast<PHINode>(UserInst)) {
4268 for (
unsigned i = 0;
i < PN->getNumIncomingValues();
i++) {
4269 if (PN->getIncomingValue(
i) ==
I) {
4273 if (UserParent && UserParent != PN->getIncomingBlock(
i))
4274 return std::nullopt;
4275 UserParent = PN->getIncomingBlock(
i);
4278 assert(UserParent &&
"expected to find user block!");
4280 if (UserParent && UserParent != UserInst->
getParent())
4281 return std::nullopt;
4287 if (NumUsers == 0) {
4290 if (UserParent ==
BB || !DT.isReachableFromEntry(UserParent))
4291 return std::nullopt;
4303 return std::nullopt;
4305 assert(DT.dominates(
BB, UserParent) &&
"Dominance relation broken?");
4313 return std::nullopt;
4318 auto OptBB = getOptionalSinkBlockForInst(
I);
4320 auto *UserParent = *OptBB;
4324 MadeIRChange =
true;
4328 for (
Use &U :
I->operands())
4329 if (
Instruction *OpI = dyn_cast<Instruction>(U.get()))
4336 Builder.CollectMetadataToCopy(
4337 I, {LLVMContext::MD_dbg, LLVMContext::MD_annotation});
4350 <<
" New = " << *Result <<
'\n');
4352 Result->copyMetadata(*
I,
4353 {LLVMContext::MD_dbg, LLVMContext::MD_annotation});
4355 I->replaceAllUsesWith(Result);
4358 Result->takeName(
I);
4365 if (isa<PHINode>(Result) != isa<PHINode>(
I)) {
4367 if (isa<PHINode>(
I))
4373 Result->insertInto(InstParent, InsertPos);
4376 Worklist.pushUsersToWorkList(*Result);
4377 Worklist.push(Result);
4379 eraseInstFromFunction(*
I);
4382 <<
" New = " << *
I <<
'\n');
4387 eraseInstFromFunction(*
I);
4389 Worklist.pushUsersToWorkList(*
I);
4393 MadeIRChange =
true;
4398 return MadeIRChange;
4414 if (!
I->hasMetadataOtherThanDebugLoc())
4417 auto Track = [](
Metadata *ScopeList,
auto &Container) {
4418 const auto *MDScopeList = dyn_cast_or_null<MDNode>(ScopeList);
4419 if (!MDScopeList || !Container.insert(MDScopeList).second)
4421 for (
const auto &
MDOperand : MDScopeList->operands())
4422 if (
auto *MDScope = dyn_cast<MDNode>(
MDOperand))
4423 Container.insert(MDScope);
4426 Track(
I->getMetadata(LLVMContext::MD_alias_scope), UsedAliasScopesAndLists);
4427 Track(
I->getMetadata(LLVMContext::MD_noalias), UsedNoAliasScopesAndLists);
4436 "llvm.experimental.noalias.scope.decl in use ?");
4439 "llvm.experimental.noalias.scope should refer to a single scope");
4441 if (
auto *MD = dyn_cast<MDNode>(
MDOperand))
4442 return !UsedAliasScopesAndLists.
contains(MD) ||
4443 !UsedNoAliasScopesAndLists.
contains(MD);
4461 bool MadeIRChange =
false;
4464 Worklist.push_back(&
F.front());
4479 if (!Inst.use_empty() &&
4480 (Inst.getNumOperands() == 0 || isa<Constant>(Inst.getOperand(0))))
4484 Inst.replaceAllUsesWith(
C);
4487 Inst.eraseFromParent();
4488 MadeIRChange =
true;
4493 for (
Use &U : Inst.operands()) {
4494 if (!isa<ConstantVector>(U) && !isa<ConstantExpr>(U))
4497 auto *
C = cast<Constant>(U);
4498 Constant *&FoldRes = FoldedConstants[
C];
4504 <<
"\n Old = " << *
C
4505 <<
"\n New = " << *FoldRes <<
'\n');
4507 MadeIRChange =
true;
4514 if (!Inst.isDebugOrPseudoInst()) {
4515 InstrsForInstructionWorklist.push_back(&Inst);
4516 SeenAliasScopes.
analyse(&Inst);
4523 if (
BranchInst *BI = dyn_cast<BranchInst>(TI)) {
4524 if (BI->isConditional() && isa<ConstantInt>(BI->getCondition())) {
4525 bool CondVal = cast<ConstantInt>(BI->getCondition())->getZExtValue();
4526 BasicBlock *ReachableBB = BI->getSuccessor(!CondVal);
4527 Worklist.push_back(ReachableBB);
4530 }
else if (
SwitchInst *
SI = dyn_cast<SwitchInst>(TI)) {
4532 Worklist.push_back(
SI->findCaseValue(
Cond)->getCaseSuccessor());
4538 }
while (!Worklist.empty());
4547 unsigned NumDeadInstInBB;
4548 unsigned NumDeadDbgInstInBB;
4549 std::tie(NumDeadInstInBB, NumDeadDbgInstInBB) =
4552 MadeIRChange |= NumDeadInstInBB + NumDeadDbgInstInBB > 0;
4553 NumDeadInst += NumDeadInstInBB;
4561 ICWorklist.
reserve(InstrsForInstructionWorklist.size());
4570 Inst->eraseFromParent();
4571 MadeIRChange =
true;
4575 ICWorklist.
push(Inst);
4578 return MadeIRChange;
4586 auto &
DL =
F.getParent()->getDataLayout();
4595 if (
auto *Assume = dyn_cast<AssumeInst>(
I))
4601 bool MadeIRChange =
false;
4613 unsigned Iteration = 0;
4615 ++NumWorklistIterations;
4620 "Instruction Combining seems stuck in an infinite loop after " +
4624 if (Iteration > MaxIterations) {
4625 LLVM_DEBUG(
dbgs() <<
"\n\n[IC] Iteration limit #" << MaxIterations
4626 <<
" on " <<
F.getName()
4627 <<
" reached; stopping before reaching a fixpoint\n");
4631 LLVM_DEBUG(
dbgs() <<
"\n\nINSTCOMBINE ITERATION #" << Iteration <<
" on "
4632 <<
F.getName() <<
"\n");
4637 ORE,
BFI, PSI,
DL, LI);
4643 MadeIRChange =
true;
4646 return MadeIRChange;
4652 : MaxIterations(MaxIterations) {}
4668 auto *
BFI = (PSI && PSI->hasProfileSummary()) ?
4672 BFI, PSI, MaxIterations, LI))
4703 auto AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
4704 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
F);
4705 auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);
4706 auto &
TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
F);
4707 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
4708 auto &ORE = getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
4711 auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
4712 auto *LI = LIWP ? &LIWP->getLoopInfo() :
nullptr;
4714 &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
4717 &getAnalysis<LazyBlockFrequencyInfoPass>().getBFI() :
4721 BFI, PSI, MaxIterations, LI);
4737 "Combine redundant instructions",
false,
false)