110#define DEBUG_TYPE "instcombine"
118 "Number of instruction combining iterations performed");
122STATISTIC(NumDeadInst ,
"Number of dead inst eliminated");
128 "Controls which instructions are visited");
142 "instcombine-max-sink-users",
cl::init(32),
143 cl::desc(
"Maximum number of undroppable users for instruction sinking"));
146 "instcombine-infinite-loop-threshold",
147 cl::desc(
"Number of instruction combining iterations considered an "
153 cl::desc(
"Maximum array size considered when doing a combine"));
165std::optional<Instruction *>
176 bool &KnownBitsComputed) {
193 *
this, II, DemandedElts, UndefElts, UndefElts2, UndefElts3,
208bool InstCombinerImpl::isDesirableIntType(
unsigned BitWidth)
const {
227bool InstCombinerImpl::shouldChangeType(
unsigned FromWidth,
228 unsigned ToWidth)
const {
234 if (ToWidth < FromWidth && isDesirableIntType(ToWidth))
239 if ((FromLegal || isDesirableIntType(FromWidth)) && !ToLegal)
244 if (!FromLegal && !ToLegal && ToWidth > FromWidth)
255bool InstCombinerImpl::shouldChangeType(
Type *
From,
Type *To)
const {
261 unsigned FromWidth =
From->getPrimitiveSizeInBits();
263 return shouldChangeType(FromWidth, ToWidth);
272 auto *OBO = dyn_cast<OverflowingBinaryOperator>(&
I);
273 if (!OBO || !OBO->hasNoSignedWrap())
278 if (Opcode != Instruction::Add && Opcode != Instruction::Sub)
281 const APInt *BVal, *CVal;
285 bool Overflow =
false;
286 if (Opcode == Instruction::Add)
287 (void)BVal->
sadd_ov(*CVal, Overflow);
289 (
void)BVal->
ssub_ov(*CVal, Overflow);
295 auto *OBO = dyn_cast<OverflowingBinaryOperator>(&
I);
296 return OBO && OBO->hasNoUnsignedWrap();
300 auto *OBO = dyn_cast<OverflowingBinaryOperator>(&
I);
301 return OBO && OBO->hasNoSignedWrap();
310 I.clearSubclassOptionalData();
315 I.clearSubclassOptionalData();
316 I.setFastMathFlags(FMF);
325 auto *Cast = dyn_cast<CastInst>(BinOp1->
getOperand(0));
326 if (!Cast || !Cast->hasOneUse())
330 auto CastOpcode = Cast->getOpcode();
331 if (CastOpcode != Instruction::ZExt)
339 auto *BinOp2 = dyn_cast<BinaryOperator>(Cast->getOperand(0));
340 if (!BinOp2 || !BinOp2->hasOneUse() || BinOp2->getOpcode() != AssocOpcode)
364Value *InstCombinerImpl::simplifyIntToPtrRoundTripCast(
Value *Val) {
365 auto *IntToPtr = dyn_cast<IntToPtrInst>(Val);
368 auto *PtrToInt = dyn_cast<PtrToIntInst>(IntToPtr->getOperand(0));
369 Type *CastTy = IntToPtr->getDestTy();
372 PtrToInt->getSrcTy()->getPointerAddressSpace() &&
404 bool Changed =
false;
412 Changed = !
I.swapOperands();
417 if (
I.isAssociative()) {
440 I.setHasNoUnsignedWrap(
true);
443 I.setHasNoSignedWrap(
true);
472 if (
I.isAssociative() &&
I.isCommutative()) {
535 if (isa<FPMathOperator>(NewBO)) {
549 I.setHasNoUnsignedWrap(
true);
567 if (LOp == Instruction::And)
568 return ROp == Instruction::Or || ROp == Instruction::Xor;
571 if (LOp == Instruction::Or)
572 return ROp == Instruction::And;
576 if (LOp == Instruction::Mul)
577 return ROp == Instruction::Add || ROp == Instruction::Sub;
600 if (isa<Constant>(V))
614 assert(Op &&
"Expected a binary operator");
615 LHS = Op->getOperand(0);
616 RHS = Op->getOperand(1);
617 if (TopOpcode == Instruction::Add || TopOpcode == Instruction::Sub) {
622 return Instruction::Mul;
626 return Op->getOpcode();
635 assert(
A &&
B &&
C &&
D &&
"All values must be provided");
638 Value *RetVal =
nullptr;
649 if (
A ==
C || (InnerCommutative &&
A ==
D)) {
661 RetVal =
Builder.CreateBinOp(InnerOpcode,
A, V);
669 if (
B ==
D || (InnerCommutative &&
B ==
C)) {
681 RetVal =
Builder.CreateBinOp(InnerOpcode, V,
B);
692 if (isa<OverflowingBinaryOperator>(RetVal)) {
695 if (isa<OverflowingBinaryOperator>(&
I)) {
696 HasNSW =
I.hasNoSignedWrap();
697 HasNUW =
I.hasNoUnsignedWrap();
699 if (
auto *LOBO = dyn_cast<OverflowingBinaryOperator>(
LHS)) {
700 HasNSW &= LOBO->hasNoSignedWrap();
701 HasNUW &= LOBO->hasNoUnsignedWrap();
704 if (
auto *ROBO = dyn_cast<OverflowingBinaryOperator>(
RHS)) {
705 HasNSW &= ROBO->hasNoSignedWrap();
706 HasNUW &= ROBO->hasNoUnsignedWrap();
709 if (TopLevelOpcode == Instruction::Add && InnerOpcode == Instruction::Mul) {
719 cast<Instruction>(RetVal)->setHasNoSignedWrap(HasNSW);
722 cast<Instruction>(RetVal)->setHasNoUnsignedWrap(HasNUW);
743 if (Op0 && Op1 && LHSOpcode == RHSOpcode)
869 if (!LHSIsSelect && !RHSIsSelect)
874 if (isa<FPMathOperator>(&
I)) {
875 FMF =
I.getFastMathFlags();
882 Value *
Cond, *True =
nullptr, *False =
nullptr;
890 if (Opcode != Instruction::Add || (!True && !False) || (True && False))
905 if (LHSIsSelect && RHSIsSelect &&
A ==
D) {
914 else if (True && !False)
943void InstCombinerImpl::freelyInvertAllUsersOf(
Value *
I,
Value *IgnoredUser) {
945 if (U == IgnoredUser)
947 switch (cast<Instruction>(U)->
getOpcode()) {
948 case Instruction::Select: {
949 auto *
SI = cast<SelectInst>(U);
951 SI->swapProfMetadata();
954 case Instruction::Br:
955 cast<BranchInst>(U)->swapSuccessors();
957 case Instruction::Xor:
962 "canFreelyInvertAllUsersOf() ?");
969Value *InstCombinerImpl::dyn_castNegVal(
Value *V)
const {
979 if (
C->getType()->getElementType()->isIntegerTy())
983 for (
unsigned i = 0, e = CV->getNumOperands(); i != e; ++i) {
988 if (isa<UndefValue>(Elt))
991 if (!isa<ConstantInt>(Elt))
998 if (
auto *CV = dyn_cast<Constant>(V))
999 if (CV->getType()->isVectorTy() &&
1000 CV->getType()->getScalarType()->isIntegerTy() && CV->getSplatValue())
1018 !
X->getType()->isIntOrIntVectorTy(1))
1031 auto *ConstSO = dyn_cast<Constant>(SO);
1036 for (
Value *Op :
I.operands()) {
1039 else if (
auto *
C = dyn_cast<Constant>(Op))
1056 bool FoldWithMultiUse) {
1058 if (!
SI->hasOneUse() && !FoldWithMultiUse)
1061 Value *TV =
SI->getTrueValue();
1062 Value *FV =
SI->getFalseValue();
1063 if (!(isa<Constant>(TV) || isa<Constant>(FV)))
1067 if (
SI->getType()->isIntOrIntVectorTy(1))
1072 if (
auto *BC = dyn_cast<BitCastInst>(&Op)) {
1073 VectorType *DestTy = dyn_cast<VectorType>(BC->getDestTy());
1074 VectorType *SrcTy = dyn_cast<VectorType>(BC->getSrcTy());
1077 if ((SrcTy ==
nullptr) != (DestTy ==
nullptr))
1092 if (
auto *CI = dyn_cast<CmpInst>(
SI->getCondition())) {
1093 if (CI->hasOneUse()) {
1094 Value *Op0 = CI->getOperand(0), *Op1 = CI->getOperand(1);
1109 if (!
A->getType()->isIntOrIntVectorTy() ||
A->getType() !=
B->getType())
1118 if ((areLooselyEqual(TV, Op0) && areLooselyEqual(FV, Op1)) ||
1119 (areLooselyEqual(FV, Op0) && areLooselyEqual(TV, Op1)))
1127 if (!NewTV && !NewFV)
1140 if (NumPHIValues == 0)
1150 if (UI != &
I && !
I.isIdenticalTo(UI))
1161 Value *NonSimplifiedInVal =
nullptr;
1162 for (
unsigned i = 0; i != NumPHIValues; ++i) {
1170 for (
Value *Op :
I.operands()) {
1188 if (isa<PHINode>(InVal))
return nullptr;
1189 if (NonSimplifiedBB)
return nullptr;
1191 NonSimplifiedBB = InBB;
1192 NonSimplifiedInVal = InVal;
1197 if (isa<InvokeInst>(InVal))
1198 if (cast<Instruction>(InVal)->
getParent() == NonSimplifiedBB)
1215 if (NonSimplifiedBB !=
nullptr) {
1230 if (NonSimplifiedBB) {
1234 U = NonSimplifiedInVal;
1236 U = U->DoPHITranslation(PN->
getParent(), NonSimplifiedBB);
1241 for (
unsigned i = 0; i != NumPHIValues; ++i) {
1242 if (NewPhiValues[i])
1250 if (
User == &
I)
continue;
1261 auto *Phi0 = dyn_cast<PHINode>(BO.
getOperand(0));
1262 auto *Phi1 = dyn_cast<PHINode>(BO.
getOperand(1));
1263 if (!Phi0 || !Phi1 || !Phi0->hasOneUse() || !Phi1->hasOneUse() ||
1264 Phi0->getNumOperands() != Phi1->getNumOperands())
1285 auto CanFoldIncomingValuePair = [&](std::tuple<Use &, Use &>
T) {
1286 auto &Phi0Use = std::get<0>(
T);
1287 auto &Phi1Use = std::get<1>(
T);
1288 if (Phi0->getIncomingBlock(Phi0Use) != Phi1->getIncomingBlock(Phi1Use))
1290 Value *Phi0UseV = Phi0Use.get();
1291 Value *Phi1UseV = Phi1Use.get();
1294 else if (Phi1UseV ==
C)
1301 if (
all_of(
zip(Phi0->operands(), Phi1->operands()),
1302 CanFoldIncomingValuePair)) {
1305 assert(NewIncomingValues.
size() == Phi0->getNumOperands() &&
1306 "The number of collected incoming values should equal the number "
1307 "of the original PHINode operands!");
1308 for (
unsigned I = 0;
I < Phi0->getNumOperands();
I++)
1309 NewPhi->
addIncoming(NewIncomingValues[
I], Phi0->getIncomingBlock(
I));
1314 if (Phi0->getNumOperands() != 2 || Phi1->getNumOperands() != 2)
1321 ConstBB = Phi0->getIncomingBlock(0);
1322 OtherBB = Phi0->getIncomingBlock(1);
1324 ConstBB = Phi0->getIncomingBlock(1);
1325 OtherBB = Phi0->getIncomingBlock(0);
1335 auto *PredBlockBranch = dyn_cast<BranchInst>(OtherBB->
getTerminator());
1336 if (!PredBlockBranch || PredBlockBranch->isConditional() ||
1343 for (
auto BBIter = BO.
getParent()->
begin(); &*BBIter != &BO; ++BBIter)
1356 Phi0->getIncomingValueForBlock(OtherBB),
1357 Phi1->getIncomingValueForBlock(OtherBB));
1358 if (
auto *NotFoldedNewBO = dyn_cast<BinaryOperator>(NewBO))
1359 NotFoldedNewBO->copyIRFlags(&BO);
1369 if (!isa<Constant>(
I.getOperand(1)))
1372 if (
auto *Sel = dyn_cast<SelectInst>(
I.getOperand(0))) {
1375 }
else if (
auto *PN = dyn_cast<PHINode>(
I.getOperand(0))) {
1390 Type *Ty = PtrTy->getNonOpaquePointerElementType();
1408 if (
GEP.hasAllZeroIndices() && !Src.hasAllZeroIndices() &&
1417 assert(isa<IntegerType>(Val->
getType()) &&
"Can only descale integers!");
1419 Scale.
getBitWidth() &&
"Scale not compatible with value!");
1423 NoSignedWrap =
true;
1455 std::pair<Instruction *, unsigned> Parent;
1459 bool RequireNoSignedWrap =
false;
1464 for (;; Op = Parent.first->getOperand(Parent.second)) {
1465 if (
ConstantInt *CI = dyn_cast<ConstantInt>(Op)) {
1467 APInt Quotient(Scale), Remainder(Scale);
1474 NoSignedWrap =
true;
1479 if (BO->
getOpcode() == Instruction::Mul) {
1482 if (RequireNoSignedWrap && !NoSignedWrap)
1493 if (CI->getValue() == Scale) {
1501 if (!Op->hasOneUse())
1504 Parent = std::make_pair(BO, 1);
1510 if (!Op->hasOneUse())
1513 Parent = std::make_pair(BO, 0);
1517 if (logScale > 0 && BO->
getOpcode() == Instruction::Shl &&
1521 if (RequireNoSignedWrap && !NoSignedWrap)
1525 int32_t Amt = cast<ConstantInt>(BO->
getOperand(1))->
1529 if (Amt == logScale) {
1540 Parent = std::make_pair(BO, 1);
1546 if (!Op->hasOneUse())
1549 if (
CastInst *Cast = dyn_cast<CastInst>(Op)) {
1550 if (Cast->getOpcode() == Instruction::SExt) {
1552 unsigned SmallSize = Cast->getSrcTy()->getPrimitiveSizeInBits();
1564 RequireNoSignedWrap =
true;
1567 Parent = std::make_pair(Cast, 0);
1572 if (Cast->getOpcode() == Instruction::Trunc) {
1579 if (RequireNoSignedWrap)
1583 unsigned LargeSize = Cast->getSrcTy()->getPrimitiveSizeInBits();
1584 Parent = std::make_pair(Cast, 0);
1585 Scale = Scale.
sext(LargeSize);
1586 if (logScale + 1 == (int32_t)Cast->getType()->getPrimitiveSizeInBits())
1599 NoSignedWrap =
true;
1613 assert(Parent.first->hasOneUse() &&
"Drilled down when more than one use!");
1614 assert(Op != Parent.first->getOperand(Parent.second) &&
1615 "Descaling was a no-op?");
1632 NoSignedWrap &= OpNoSignedWrap;
1633 if (NoSignedWrap != OpNoSignedWrap) {
1637 }
else if (Ancestor->
getOpcode() == Instruction::Trunc) {
1641 NoSignedWrap =
false;
1643 assert((Ancestor->
getOpcode() != Instruction::SExt || NoSignedWrap) &&
1644 "Failed to keep proper track of nsw flags while drilling down?");
1646 if (Ancestor == Val)
1651 assert(Ancestor->
hasOneUse() &&
"Drilled down when more than one use!");
1657 if (!isa<VectorType>(Inst.
getType()))
1663 cast<VectorType>(Inst.
getType())->getElementCount());
1665 cast<VectorType>(Inst.
getType())->getElementCount());
1670 Value *L0, *L1, *R0, *R1;
1675 cast<ShuffleVectorInst>(
LHS)->isConcat() &&
1676 cast<ShuffleVectorInst>(
RHS)->isConcat()) {
1683 if (
auto *BO = dyn_cast<BinaryOperator>(NewBO0))
1686 if (
auto *BO = dyn_cast<BinaryOperator>(NewBO1))
1693 if (
auto *BO = dyn_cast<BinaryOperator>(V))
1697 M, Intrinsic::experimental_vector_reverse, V->getType());
1710 return createBinOpReverse(V1, V2);
1714 return createBinOpReverse(V1,
RHS);
1718 return createBinOpReverse(
LHS, V2);
1728 if (
auto *BO = dyn_cast<BinaryOperator>(XY))
1737 V1->
getType() == V2->getType() &&
1740 return createBinOpShuffle(V1, V2, Mask);
1749 auto *LShuf = cast<ShuffleVectorInst>(
LHS);
1750 auto *RShuf = cast<ShuffleVectorInst>(
RHS);
1755 if (LShuf->isSelect() &&
1757 RShuf->isSelect() &&
1775 auto *InstVTy = dyn_cast<FixedVectorType>(Inst.
getType());
1780 cast<FixedVectorType>(V1->
getType())->getNumElements() <=
1781 InstVTy->getNumElements()) {
1783 "Shuffle should not change scalar type");
1790 bool ConstOp1 = isa<Constant>(
RHS);
1792 unsigned SrcVecNumElts =
1793 cast<FixedVectorType>(V1->
getType())->getNumElements();
1796 bool MayChange =
true;
1797 unsigned NumElts = InstVTy->getNumElements();
1798 for (
unsigned I = 0;
I < NumElts; ++
I) {
1800 if (ShMask[
I] >= 0) {
1801 assert(ShMask[
I] < (
int)NumElts &&
"Not expecting narrowing shuffle");
1809 if (!CElt || (!isa<UndefValue>(NewCElt) && NewCElt != CElt) ||
1810 I >= SrcVecNumElts) {
1814 NewVecC[ShMask[
I]] = CElt;
1825 if (
I >= SrcVecNumElts || ShMask[
I] < 0) {
1846 Value *NewLHS = ConstOp1 ? V1 : NewC;
1847 Value *NewRHS = ConstOp1 ? NewC : V1;
1848 return createBinOpShuffle(NewLHS, NewRHS, Mask);
1855 if (isa<ShuffleVectorInst>(
RHS))
1888 if (isa<FPMathOperator>(R)) {
1889 R->copyFastMathFlags(&Inst);
1892 if (
auto *NewInstBO = dyn_cast<BinaryOperator>(NewBO))
1893 NewInstBO->copyIRFlags(R);
1922 cast<Operator>(Op1)->getOpcode() == CastOpc &&
1923 (Op0->
hasOneUse() || Op1->hasOneUse()))) {
1941 if (!willNotOverflow(BO.
getOpcode(),
X,
Y, BO, IsSext))
1947 if (
auto *NewBinOp = dyn_cast<BinaryOperator>(NarrowBO)) {
1949 NewBinOp->setHasNoSignedWrap();
1951 NewBinOp->setHasNoUnsignedWrap();
1969 if (!
GEP.hasAllConstantIndices())
1984 bool IsInBounds =
GEP.isInBounds();
1985 Type *Ty =
GEP.getSourceElementType();
1986 Value *NewTrueC =
Builder.CreateGEP(Ty, TrueC, IndexC,
"", IsInBounds);
1987 Value *NewFalseC =
Builder.CreateGEP(Ty, FalseC, IndexC,
"", IsInBounds);
1999 if (Src->getResultElementType() ==
GEP.getSourceElementType() &&
2000 Src->getNumOperands() == 2 &&
GEP.getNumOperands() == 2 &&
2003 Value *SO1 = Src->getOperand(1);
2011 if (L->isLoopInvariant(GO1) && !L->isLoopInvariant(SO1)) {
2015 bool IsInBounds = Src->isInBounds() &&
GEP.isInBounds() &&
2021 Src->getPointerOperand(), GO1,
2022 Src->getName(), IsInBounds);
2024 GEP.getSourceElementType(), NewSrc, {SO1});
2035 if (
auto *SrcGEP = dyn_cast<GEPOperator>(Src->getOperand(0)))
2041 Type *PtrTy = Src->getType()->getScalarType();
2043 (Src->hasOneUse() || Src->hasAllConstantIndices())) {
2047 bool IsFirstType =
true;
2048 unsigned NumVarIndices = 0;
2049 for (
auto Pair :
enumerate(Src->indices())) {
2050 if (!isa<ConstantInt>(Pair.value())) {
2052 IsFirstType =
false;
2053 NumVarIndices = Pair.index() + 1;
2060 if (NumVarIndices != Src->getNumIndices()) {
2062 if (isa<ScalableVectorType>(
BaseType))
2081 if (!
Offset.isZero() || (!IsFirstType && !ConstIndices[0].isZero())) {
2084 if (Src->hasAllConstantIndices())
2098 Src->getNumIndices() - NumVarIndices));
2105 IsInBounds &=
Idx.isNonNegative() == ConstIndices[0].isNonNegative();
2110 Src->getOperand(0), Indices,
2113 Src->getOperand(0), Indices,
2117 if (Src->getResultElementType() !=
GEP.getSourceElementType())
2123 bool EndsWithSequential =
false;
2126 EndsWithSequential =
I.isSequential();
2129 if (EndsWithSequential) {
2132 Value *SO1 = Src->getOperand(Src->getNumOperands()-1);
2150 if (Src->getNumOperands() == 2) {
2156 Indices.
append(Src->op_begin()+1, Src->op_end()-1);
2159 }
else if (isa<Constant>(*
GEP.idx_begin()) &&
2160 cast<Constant>(*
GEP.idx_begin())->isNullValue() &&
2161 Src->getNumOperands() != 1) {
2163 Indices.
append(Src->op_begin()+1, Src->op_end());
2167 if (!Indices.
empty())
2170 Src->getSourceElementType(), Src->getOperand(0), Indices,
2173 Src->getOperand(0), Indices,
2188 Type *GEPEltType =
GEP.getSourceElementType();
2196 auto areMatchingArrayAndVecTypes = [](
Type *ArrTy,
Type *VecTy,
2198 auto *VecVTy = cast<FixedVectorType>(VecTy);
2203 if (
GEP.getNumOperands() == 3 &&
2204 ((GEPEltType->
isArrayTy() && isa<FixedVectorType>(SrcEltType) &&
2205 areMatchingArrayAndVecTypes(GEPEltType, SrcEltType,
DL)) ||
2206 (isa<FixedVectorType>(GEPEltType) && SrcEltType->
isArrayTy() &&
2207 areMatchingArrayAndVecTypes(SrcEltType, GEPEltType,
DL)))) {
2239 if (!isa<BitCastInst>(
SrcOp) &&
GEP.accumulateConstantOffset(
DL,
Offset) &&
2246 if (isa<AllocaInst>(
SrcOp)) {
2287 Type *GEPType =
GEP.getType();
2288 Type *GEPEltType =
GEP.getSourceElementType();
2289 bool IsGEPSrcEleScalable = isa<ScalableVectorType>(GEPEltType);
2297 if (
auto *GEPFVTy = dyn_cast<FixedVectorType>(GEPType)) {
2298 auto VWidth = GEPFVTy->getNumElements();
2299 APInt UndefElts(VWidth, 0);
2315 bool MadeChange =
false;
2319 Type *NewScalarIndexTy =
2329 Type *IndexTy = (*I)->getType();
2330 Type *NewIndexType =
2333 cast<VectorType>(IndexTy)->getElementCount())
2345 if (IndexTy != NewIndexType) {
2357 if (
auto *PN = dyn_cast<PHINode>(PtrOp)) {
2358 auto *Op1 = dyn_cast<GetElementPtrInst>(PN->getOperand(0));
2373 for (
auto I = PN->op_begin()+1,
E = PN->op_end();
I !=
E; ++
I) {
2374 auto *Op2 = dyn_cast<GetElementPtrInst>(*
I);
2375 if (!Op2 || Op1->getNumOperands() != Op2->getNumOperands() ||
2376 Op1->getSourceElementType() != Op2->getSourceElementType())
2384 Type *CurTy =
nullptr;
2386 for (
unsigned J = 0,
F = Op1->getNumOperands(); J !=
F; ++J) {
2387 if (Op1->getOperand(J)->getType() != Op2->getOperand(J)->getType())
2390 if (Op1->getOperand(J) != Op2->getOperand(J)) {
2399 assert(CurTy &&
"No current type?");
2419 CurTy = Op1->getSourceElementType();
2431 if (DI != -1 && !PN->hasOneUse())
2434 auto *NewGEP = cast<GetElementPtrInst>(Op1->clone());
2447 PN->getNumOperands());
2450 for (
auto &
I : PN->operands())
2451 NewPN->
addIncoming(cast<GEPOperator>(
I)->getOperand(DI),
2452 PN->getIncomingBlock(
I));
2454 NewGEP->setOperand(DI, NewPN);
2457 NewGEP->insertInto(
GEP.getParent(),
GEP.getParent()->getFirstInsertionPt());
2461 if (
auto *Src = dyn_cast<GEPOperator>(PtrOp))
2467 if (
GEP.getNumIndices() == 1 && !IsGEPSrcEleScalable) {
2468 unsigned AS =
GEP.getPointerAddressSpace();
2469 if (
GEP.getOperand(1)->getType()->getScalarSizeInBits() ==
2473 bool Matched =
false;
2476 if (TyAllocSize == 1) {
2477 V =
GEP.getOperand(1);
2479 }
else if (
match(
GEP.getOperand(1),
2481 if (TyAllocSize == 1ULL <<
C)
2483 }
else if (
match(
GEP.getOperand(1),
2485 if (TyAllocSize ==
C)
2513 if (StrippedPtr != PtrOp && !StrippedPtrTy->
isOpaque()) {
2514 bool HasZeroPointerIndex =
false;
2517 if (
auto *
C = dyn_cast<ConstantInt>(
GEP.getOperand(1)))
2518 HasZeroPointerIndex =
C->isZero();
2527 if (HasZeroPointerIndex) {
2528 if (
auto *CATy = dyn_cast<ArrayType>(GEPEltType)) {
2530 if (CATy->getElementType() == StrippedPtrEltTy) {
2534 StrippedPtrEltTy, StrippedPtr,
Idx,
GEP.getName());
2547 if (
auto *XATy = dyn_cast<ArrayType>(StrippedPtrEltTy)) {
2549 if (CATy->getElementType() == XATy->getElementType()) {
2556 GEP.setSourceElementType(XATy);
2571 GEP.getName(),
GEP.isInBounds());
2576 }
else if (
GEP.getNumOperands() == 2 && !IsGEPSrcEleScalable) {
2588 GEP.getName(),
GEP.isInBounds());
2604 if (ResSize && SrcSize % ResSize == 0) {
2606 unsigned BitWidth =
Idx->getType()->getPrimitiveSizeInBits();
2607 uint64_t Scale = SrcSize / ResSize;
2613 "Index type does not match the Data Layout preferences");
2622 GEP.getName(),
GEP.isInBounds() && NSW);
2643 if (ResSize && ArrayEltSize % ResSize == 0) {
2645 unsigned BitWidth =
Idx->getType()->getPrimitiveSizeInBits();
2646 uint64_t Scale = ArrayEltSize / ResSize;
2652 "Index type does not match the Data Layout preferences");
2664 GEP.getName(),
GEP.isInBounds() && NSW);
2677 Value *ASCStrippedPtrOp = PtrOp;
2678 if (
auto *ASC = dyn_cast<AddrSpaceCastInst>(PtrOp)) {
2683 if (
auto *BC = dyn_cast<BitCastInst>(ASC->getOperand(0)))
2684 ASCStrippedPtrOp = BC;
2687 if (
auto *BCI = dyn_cast<BitCastInst>(ASCStrippedPtrOp))
2691 if (!
GEP.isInBounds()) {
2694 APInt BasePtrOffset(IdxWidth, 0);
2695 Value *UnderlyingPtrOp =
2698 if (
auto *AI = dyn_cast<AllocaInst>(UnderlyingPtrOp)) {
2699 if (
GEP.accumulateConstantOffset(
DL, BasePtrOffset) &&
2704 if (BasePtrOffset.
ule(AllocSize)) {
2706 GEP.getSourceElementType(), PtrOp, Indices,
GEP.getName());
2720 if (isa<ConstantPointerNull>(V))
2722 if (
auto *LI = dyn_cast<LoadInst>(V))
2723 return isa<GlobalVariable>(LI->getPointerOperand());
2747 return Dest && Dest->Ptr == UsedV;
2761 switch (
I->getOpcode()) {
2766 case Instruction::AddrSpaceCast:
2767 case Instruction::BitCast:
2768 case Instruction::GetElementPtr:
2773 case Instruction::ICmp: {
2780 unsigned OtherIndex = (ICI->
getOperand(0) == PI) ? 1 : 0;
2787 case Instruction::Call:
2794 case Intrinsic::memmove:
2795 case Intrinsic::memcpy:
2796 case Intrinsic::memset: {
2798 if (
MI->isVolatile() ||
MI->getRawDest() != PI)
2802 case Intrinsic::assume:
2803 case Intrinsic::invariant_start:
2804 case Intrinsic::invariant_end:
2805 case Intrinsic::lifetime_start:
2806 case Intrinsic::lifetime_end:
2807 case Intrinsic::objectsize:
2810 case Intrinsic::launder_invariant_group:
2811 case Intrinsic::strip_invariant_group:
2840 case Instruction::Store: {
2842 if (
SI->isVolatile() ||
SI->getPointerOperand() != PI)
2850 }
while (!Worklist.
empty());
2872 std::unique_ptr<DIBuilder> DIB;
2873 if (isa<AllocaInst>(
MI)) {
2879 for (
unsigned i = 0, e =
Users.size(); i != e; ++i) {
2897 for (
unsigned i = 0, e =
Users.size(); i != e; ++i) {
2906 C->isFalseWhenEqual()));
2907 }
else if (
auto *
SI = dyn_cast<StoreInst>(
I)) {
2908 for (
auto *DVI : DVIs)
2909 if (DVI->isAddressOfVariable())
2949 for (
auto *DVI : DVIs)
2950 if (DVI->isAddressOfVariable() || DVI->getExpression()->startsWithDeref())
2951 DVI->eraseFromParent();
2997 if (FreeInstrBB->
size() != 2) {
2999 if (&Inst == &FI || &Inst == FreeInstrBBTerminator)
3001 auto *Cast = dyn_cast<CastInst>(&Inst);
3002 if (!Cast || !Cast->isNoopCast(
DL))
3023 "Broken CFG: missing edge from predecessor to successor");
3028 if (&Instr == FreeInstrBBTerminator)
3030 Instr.moveBefore(TI);
3033 "Only the branch instruction should remain");
3044 Attrs = Attrs.removeParamAttribute(FI.
getContext(), 0, Attribute::NonNull);
3045 Attribute Dereferenceable = Attrs.getParamAttr(0, Attribute::Dereferenceable);
3046 if (Dereferenceable.
isValid()) {
3048 Attrs = Attrs.removeParamAttribute(FI.
getContext(), 0,
3049 Attribute::Dereferenceable);
3050 Attrs = Attrs.addDereferenceableOrNullParamAttr(FI.
getContext(), 0, Bytes);
3059 if (isa<UndefValue>(Op)) {
3067 if (isa<ConstantPointerNull>(Op))
3072 CallInst *CI = dyn_cast<CallInst>(Op);
3098 if (
auto *CI = dyn_cast<CallInst>(V))
3099 return CI->isMustTailCall();
3109 if (!VTy->
isIntegerTy() || isa<Constant>(ResultOp))
3131 while (
Instruction *Prev =
I.getPrevNonDebugInstruction()) {
3136 if (Prev->isEHPad())
3149 assert(
I.getParent()->sizeWithoutDebug() == 1 &&
"The block is now empty.");
3163 return BBI->isDebugOrPseudoInst() ||
3164 (isa<BitCastInst>(BBI) && BBI->getType()->isPointerTy());
3169 if (BBI != FirstInstr)
3171 }
while (BBI != FirstInstr && IsNoopInstrForStoreMerging(BBI));
3173 return dyn_cast<StoreInst>(BBI);
3200 if (isa<SelectInst>(
Cond) &&
3219 auto *Cmp = cast<CmpInst>(
Cond);
3235 for (
auto Case :
SI.cases()) {
3237 assert(isa<ConstantInt>(NewCase) &&
3238 "Result of expression should be constant");
3239 Case.setValue(cast<ConstantInt>(NewCase));
3250 for (
const auto &
C :
SI.cases()) {
3252 std::min(LeadingKnownZeros,
C.getCaseValue()->getValue().countl_zero());
3254 std::min(LeadingKnownOnes,
C.getCaseValue()->getValue().countl_one());
3257 unsigned NewWidth = Known.
getBitWidth() - std::max(LeadingKnownZeros, LeadingKnownOnes);
3263 if (NewWidth > 0 && NewWidth < Known.
getBitWidth() &&
3264 shouldChangeType(Known.
getBitWidth(), NewWidth)) {
3269 for (
auto Case :
SI.cases()) {
3270 APInt TruncatedCase = Case.getCaseValue()->getValue().
trunc(NewWidth);
3286 const APInt *
C =
nullptr;
3288 if (*EV.
idx_begin() == 0 && (OvID == Intrinsic::smul_with_overflow ||
3289 OvID == Intrinsic::umul_with_overflow)) {
3294 if (
C->isPowerOf2()) {
3295 return BinaryOperator::CreateShl(
3305 if (!WO->hasOneUse())
3319 assert(*EV.
idx_begin() == 1 &&
"Unexpected extract index for overflow inst");
3322 if (OvID == Intrinsic::usub_with_overflow)
3327 if (OvID == Intrinsic::smul_with_overflow &&
3328 WO->getLHS()->getType()->isIntOrIntVectorTy(1))
3329 return BinaryOperator::CreateAnd(WO->getLHS(), WO->getRHS());
3338 WO->getBinaryOp(), *
C, WO->getNoWrapKind());
3343 auto *OpTy = WO->getRHS()->getType();
3344 auto *NewLHS = WO->getLHS();
3366 const unsigned *exti, *exte, *insi, *inse;
3367 for (exti = EV.
idx_begin(), insi =
IV->idx_begin(),
3368 exte = EV.
idx_end(), inse =
IV->idx_end();
3369 exti != exte && insi != inse;
3383 if (exti == exte && insi == inse)
3416 if (
Instruction *R = foldExtractOfOverflowIntrinsic(EV))
3419 if (
LoadInst *L = dyn_cast<LoadInst>(Agg)) {
3425 if (L->isSimple() && L->hasOneUse()) {
3437 L->getPointerOperand(), Indices);
3441 NL->setAAMetadata(L->getAAMetadata());
3448 if (
auto *PN = dyn_cast<PHINode>(Agg))
3465 switch (Personality) {
3494 cast<ArrayType>(
LHS->
getType())->getNumElements()
3496 cast<ArrayType>(
RHS->
getType())->getNumElements();
3508 bool MakeNewInstruction =
false;
3510 bool CleanupFlag =
LI.isCleanup();
3513 for (
unsigned i = 0, e =
LI.getNumClauses(); i != e; ++i) {
3514 bool isLastClause = i + 1 == e;
3515 if (
LI.isCatch(i)) {
3522 if (AlreadyCaught.
insert(TypeInfo).second) {
3527 MakeNewInstruction =
true;
3534 MakeNewInstruction =
true;
3535 CleanupFlag =
false;
3546 assert(
LI.isFilter(i) &&
"Unsupported landingpad clause!");
3554 if (!NumTypeInfos) {
3557 MakeNewInstruction =
true;
3558 CleanupFlag =
false;
3562 bool MakeNewFilter =
false;
3564 if (isa<ConstantAggregateZero>(FilterClause)) {
3566 assert(NumTypeInfos > 0 &&
"Should have handled empty filter already!");
3572 MakeNewInstruction =
true;
3579 if (NumTypeInfos > 1)
3580 MakeNewFilter =
true;
3584 NewFilterElts.
reserve(NumTypeInfos);
3589 bool SawCatchAll =
false;
3590 for (
unsigned j = 0; j != NumTypeInfos; ++j) {
3618 if (SeenInFilter.
insert(TypeInfo).second)
3619 NewFilterElts.
push_back(cast<Constant>(Elt));
3624 MakeNewInstruction =
true;
3629 if (NewFilterElts.
size() < NumTypeInfos)
3630 MakeNewFilter =
true;
3632 if (MakeNewFilter) {
3634 NewFilterElts.
size());
3636 MakeNewInstruction =
true;
3645 if (MakeNewFilter && !NewFilterElts.
size()) {
3646 assert(MakeNewInstruction &&
"New filter but not a new instruction!");
3647 CleanupFlag =
false;
3658 for (
unsigned i = 0, e = NewClauses.
size(); i + 1 < e; ) {
3661 for (j = i; j != e; ++j)
3662 if (!isa<ArrayType>(NewClauses[j]->
getType()))
3668 for (
unsigned k = i; k + 1 < j; ++k)
3672 std::stable_sort(NewClauses.
begin() + i, NewClauses.
begin() + j,
3674 MakeNewInstruction =
true;
3693 for (
unsigned i = 0; i + 1 < NewClauses.
size(); ++i) {
3703 for (
unsigned j = NewClauses.
size() - 1; j != i; --j) {
3704 Value *LFilter = NewClauses[j];
3715 NewClauses.
erase(J);
3716 MakeNewInstruction =
true;
3726 if (isa<ConstantAggregateZero>(LFilter)) {
3729 if (isa<ConstantAggregateZero>(
Filter)) {
3730 assert(FElts <= LElts &&
"Should have handled this case earlier!");
3732 NewClauses.
erase(J);
3733 MakeNewInstruction =
true;
3739 if (isa<ConstantAggregateZero>(
Filter)) {
3742 assert(FElts > 0 &&
"Should have eliminated the empty filter earlier!");
3743 for (
unsigned l = 0; l != LElts; ++l)
3746 NewClauses.
erase(J);
3747 MakeNewInstruction =
true;
3758 bool AllFound =
true;
3759 for (
unsigned f = 0; f != FElts; ++f) {
3762 for (
unsigned l = 0; l != LElts; ++l) {
3764 if (LTypeInfo == FTypeInfo) {
3774 NewClauses.
erase(J);
3775 MakeNewInstruction =
true;
3783 if (MakeNewInstruction) {
3786 for (
unsigned i = 0, e = NewClauses.
size(); i != e; ++i)
3791 if (NewClauses.
empty())
3799 if (
LI.isCleanup() != CleanupFlag) {
3800 assert(!CleanupFlag &&
"Adding a cleanup, not removing one?!");
3801 LI.setCleanup(CleanupFlag);
3825 auto *OrigOpInst = dyn_cast<Instruction>(OrigOp);
3830 if (!OrigOpInst || !OrigOpInst->hasOneUse() || isa<PHINode>(OrigOp))
3844 Use *MaybePoisonOperand =
nullptr;
3845 for (
Use &U : OrigOpInst->operands()) {
3846 if (isa<MetadataAsValue>(U.get()) ||
3849 if (!MaybePoisonOperand)
3850 MaybePoisonOperand = &U;
3855 OrigOpInst->dropPoisonGeneratingFlagsAndMetadata();
3858 if (!MaybePoisonOperand)
3863 MaybePoisonOperand->get(), MaybePoisonOperand->get()->
getName() +
".fr");
3865 replaceUse(*MaybePoisonOperand, FrozenMaybePoisonOperand);
3876 Use *StartU =
nullptr;
3894 Value *StartV = StartU->get();
3906 if (!Visited.
insert(V).second)
3909 if (Visited.
size() > 32)
3926 I->dropPoisonGeneratingFlagsAndMetadata();
3928 if (StartNeedsFreeze) {
3940 if (isa<Constant>(Op) || Op->hasOneUse())
3949 if (isa<Argument>(Op)) {
3958 bool Changed =
false;
3959 if (&FI != MoveBefore) {
3964 Op->replaceUsesWithIf(&FI, [&](
Use &U) ->
bool {
3966 Changed |= Dominates;
3975 for (
auto *U : V->users()) {
3976 if (isa<ShuffleVectorInst>(U))
3985 Value *Op0 =
I.getOperand(0);
3991 if (
auto *PN = dyn_cast<PHINode>(Op0)) {
4014 auto getUndefReplacement = [&
I](
Type *Ty) {
4017 for (
const auto *U :
I.users()) {
4026 else if (BestValue !=
C)
4027 BestValue = NullValue;
4029 assert(BestValue &&
"Must have at least one use");
4044 Constant *ReplaceC = getUndefReplacement(
I.getType()->getScalarType());
4059 auto *CB = dyn_cast<CallBase>(
I);
4078 for (
const User *U :
I.users()) {
4079 if (Visited.
insert(U).second)
4084 while (!AllocaUsers.
empty()) {
4085 auto *UserI = cast<Instruction>(AllocaUsers.
pop_back_val());
4086 if (isa<BitCastInst>(UserI) || isa<GetElementPtrInst>(UserI) ||
4087 isa<AddrSpaceCastInst>(UserI)) {
4108 if (isa<PHINode>(
I) ||
I->isEHPad() ||
I->mayThrow() || !
I->willReturn() ||
4116 if (isa<AllocaInst>(
I))
4124 if (
auto *CI = dyn_cast<CallInst>(
I)) {
4125 if (CI->isConvergent())
4131 if (
I->mayWriteToMemory()) {
4138 if (
I->mayReadFromMemory()) {
4145 E =
I->getParent()->end();
4147 if (Scan->mayWriteToMemory())
4151 I->dropDroppableUses([DestBlock](
const Use *U) {
4152 if (
auto *
I = dyn_cast<Instruction>(U->getUser()))
4153 return I->getParent() != DestBlock;
4160 I->moveBefore(&*InsertPos);
4174 if (DVI->getParent() == SrcBlock)
4177 [](
auto *
A,
auto *
B) {
return B->comesBefore(
A); });
4181 for (
auto *
User : DbgUsersToSink) {
4186 if (isa<DbgDeclareInst>(
User))
4191 User->getDebugLoc()->getInlinedAt());
4193 if (!SunkVariables.
insert(DbgUserVariable).second)
4198 if (isa<DbgAssignIntrinsic>(
User))
4201 DIIClones.emplace_back(cast<DbgVariableIntrinsic>(
User->clone()));
4202 if (isa<DbgDeclareInst>(
User) && isa<CastInst>(
I))
4203 DIIClones.back()->replaceVariableLocationOp(
I,
I->getOperand(0));
4208 if (!DIIClones.empty()) {
4213 DIIClone->insertBefore(&*InsertPos);
4240 if (
I ==
nullptr)
continue;
4255 auto getOptionalSinkBlockForInst =
4256 [
this](
Instruction *
I) -> std::optional<BasicBlock *> {
4258 return std::nullopt;
4262 unsigned NumUsers = 0;
4264 for (
auto *U :
I->users()) {
4265 if (U->isDroppable())
4268 return std::nullopt;
4272 if (
PHINode *PN = dyn_cast<PHINode>(UserInst)) {
4273 for (
unsigned i = 0; i < PN->getNumIncomingValues(); i++) {
4274 if (PN->getIncomingValue(i) ==
I) {
4278 if (UserParent && UserParent != PN->getIncomingBlock(i))
4279 return std::nullopt;
4280 UserParent = PN->getIncomingBlock(i);
4283 assert(UserParent &&
"expected to find user block!");
4285 if (UserParent && UserParent != UserInst->
getParent())
4286 return std::nullopt;
4292 if (NumUsers == 0) {
4296 return std::nullopt;
4308 return std::nullopt;
4318 return std::nullopt;
4323 auto OptBB = getOptionalSinkBlockForInst(
I);
4325 auto *UserParent = *OptBB;
4333 for (
Use &U :
I->operands())
4334 if (
Instruction *OpI = dyn_cast<Instruction>(U.get()))
4342 I, {LLVMContext::MD_dbg, LLVMContext::MD_annotation});
4355 <<
" New = " << *Result <<
'\n');
4357 Result->copyMetadata(*
I,
4358 {LLVMContext::MD_dbg, LLVMContext::MD_annotation});
4360 I->replaceAllUsesWith(Result);
4363 Result->takeName(
I);
4370 if (isa<PHINode>(Result) != isa<PHINode>(
I)) {
4372 if (isa<PHINode>(
I))
4378 Result->insertInto(InstParent, InsertPos);
4387 <<
" New = " << *
I <<
'\n');
4419 if (!
I->hasMetadataOtherThanDebugLoc())
4422 auto Track = [](
Metadata *ScopeList,
auto &Container) {
4423 const auto *MDScopeList = dyn_cast_or_null<MDNode>(ScopeList);
4424 if (!MDScopeList || !Container.insert(MDScopeList).second)
4426 for (
const auto &
MDOperand : MDScopeList->operands())
4427 if (
auto *MDScope = dyn_cast<MDNode>(
MDOperand))
4428 Container.insert(MDScope);
4431 Track(
I->getMetadata(LLVMContext::MD_alias_scope), UsedAliasScopesAndLists);
4432 Track(
I->getMetadata(LLVMContext::MD_noalias), UsedNoAliasScopesAndLists);
4441 "llvm.experimental.noalias.scope.decl in use ?");
4444 "llvm.experimental.noalias.scope should refer to a single scope");
4446 if (
auto *MD = dyn_cast<MDNode>(
MDOperand))
4447 return !UsedAliasScopesAndLists.
contains(MD) ||
4448 !UsedNoAliasScopesAndLists.
contains(MD);
4466 bool MadeIRChange =
false;
4479 if (!Visited.
insert(BB).second)
4484 if (!Inst.use_empty() &&
4485 (Inst.getNumOperands() == 0 || isa<Constant>(Inst.getOperand(0))))
4489 Inst.replaceAllUsesWith(
C);
4492 Inst.eraseFromParent();
4493 MadeIRChange =
true;
4498 for (
Use &U : Inst.operands()) {
4499 if (!isa<ConstantVector>(U) && !isa<ConstantExpr>(U))
4502 auto *
C = cast<Constant>(U);
4503 Constant *&FoldRes = FoldedConstants[
C];
4509 <<
"\n Old = " << *
C
4510 <<
"\n New = " << *FoldRes <<
'\n');
4512 MadeIRChange =
true;
4519 if (!Inst.isDebugOrPseudoInst()) {
4520 InstrsForInstructionWorklist.
push_back(&Inst);
4521 SeenAliasScopes.
analyse(&Inst);
4528 if (
BranchInst *BI = dyn_cast<BranchInst>(TI)) {
4529 if (BI->isConditional() && isa<ConstantInt>(BI->getCondition())) {
4530 bool CondVal = cast<ConstantInt>(BI->getCondition())->getZExtValue();
4531 BasicBlock *ReachableBB = BI->getSuccessor(!CondVal);
4535 }
else if (
SwitchInst *
SI = dyn_cast<SwitchInst>(TI)) {
4543 }
while (!Worklist.
empty());
4549 if (Visited.
count(&BB))
4552 unsigned NumDeadInstInBB;
4553 unsigned NumDeadDbgInstInBB;
4554 std::tie(NumDeadInstInBB, NumDeadDbgInstInBB) =
4557 MadeIRChange |= NumDeadInstInBB + NumDeadDbgInstInBB > 0;
4558 NumDeadInst += NumDeadInstInBB;
4566 ICWorklist.
reserve(InstrsForInstructionWorklist.
size());
4575 Inst->eraseFromParent();
4576 MadeIRChange =
true;
4580 ICWorklist.
push(Inst);
4583 return MadeIRChange;
4591 auto &
DL =
F.getParent()->getDataLayout();
4599 if (
auto *Assume = dyn_cast<AssumeInst>(
I))
4605 bool MadeIRChange =
false;
4610 unsigned Iteration = 0;
4612 ++NumWorklistIterations;
4617 "Instruction Combining seems stuck in an infinite loop after " +
4621 if (Iteration > MaxIterations) {
4622 LLVM_DEBUG(
dbgs() <<
"\n\n[IC] Iteration limit #" << MaxIterations
4623 <<
" on " <<
F.getName()
4624 <<
" reached; stopping before reaching a fixpoint\n");
4628 LLVM_DEBUG(
dbgs() <<
"\n\nINSTCOMBINE ITERATION #" << Iteration <<
" on "
4629 <<
F.getName() <<
"\n");
4634 ORE, BFI, PSI,
DL, LI);
4640 MadeIRChange =
true;
4643 return MadeIRChange;
4651 OS, MapClassName2PassName);
4654 OS << (Options.
UseLoopInfo ?
"" :
"no-") <<
"use-loop-info";
4676 auto *BFI = (PSI && PSI->hasProfileSummary()) ?
4711 auto AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
4712 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(