Lines Matching +full:fetch +full:- +full:depth
1 //===- InstructionCombining.cpp - Combine multiple instructions -----------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // InstructionCombining - Combine instructions to form fewer, simple
29 // 6. Multiplies with a power-of-two constant argument are transformed into
33 //===----------------------------------------------------------------------===//
130 DEBUG_COUNTER(VisitCounter, "instcombine-visit",
134 EnableCodeSinking("instcombine-code-sinking", cl::desc("Enable code sinking"),
138 "instcombine-max-sink-users", cl::init(32),
142 MaxArraySize("instcombine-maxarray-size", cl::init(1024),
152 static cl::opt<unsigned> ShouldLowerDbgDeclare("instcombine-lower-dbg-declare",
158 if (II.getCalledFunction()->isTargetIntrinsic()) {
168 if (II.getCalledFunction()->isTargetIntrinsic()) {
181 if (II.getCalledFunction()->isTargetIntrinsic()) {
206 // If a non-trivial GEP has other uses, rewrite it to avoid duplicating
208 if (Inst && !GEP->hasOneUse() && !GEP->hasAllConstantIndices() &&
209 !GEP->getSourceElementType()->isIntegerTy(8)) {
211 *Inst, Builder.CreateGEP(Builder.getInt8Ty(), GEP->getPointerOperand(),
212 Offset, "", GEP->getNoWrapFlags()));
258 // do allow things like i160 -> i64, but not i64 -> i160.
273 if (!From->isIntegerTy() || !To->isIntegerTy())
276 unsigned FromWidth = From->getPrimitiveSizeInBits();
277 unsigned ToWidth = To->getPrimitiveSizeInBits();
288 if (!OBO || !OBO->hasNoSignedWrap())
299 (void)BVal->sadd_ov(*CVal, Overflow);
302 (void)BVal->ssub_ov(*CVal, Overflow);
305 (void)BVal->smul_ov(*CVal, Overflow);
316 return OBO && OBO->hasNoUnsignedWrap();
321 return OBO && OBO->hasNoSignedWrap();
325 /// commutation. We preserve fast-math flags when applicable as they can be
341 /// (op (cast (op X, C2)), C1) --> (cast (op X, op (C1, C2)))
342 /// (op (cast (op X, C2)), C1) --> (op (cast X), op (C1, C2))
345 auto *Cast = dyn_cast<CastInst>(BinOp1->getOperand(0));
346 if (!Cast || !Cast->hasOneUse())
350 auto CastOpcode = Cast->getOpcode();
355 if (!BinOp1->isBitwiseLogicOp())
358 auto AssocOpcode = BinOp1->getOpcode();
359 auto *BinOp2 = dyn_cast<BinaryOperator>(Cast->getOperand(0));
360 if (!BinOp2 || !BinOp2->hasOneUse() || BinOp2->getOpcode() != AssocOpcode)
364 if (!match(BinOp1->getOperand(1), m_Constant(C1)) ||
365 !match(BinOp2->getOperand(1), m_Constant(C2)))
373 // (op (cast (op X, C2)), C1) --> (op (cast X), FoldedC)
375 Type *DestTy = C1->getType();
383 IC.replaceOperand(*Cast, 0, BinOp2->getOperand(0));
385 BinOp1->dropPoisonGeneratingFlags();
386 Cast->dropPoisonGeneratingFlags();
391 // inttoptr ( ptrtoint (x) ) --> x
394 if (IntToPtr && DL.getTypeSizeInBits(IntToPtr->getDestTy()) ==
395 DL.getTypeSizeInBits(IntToPtr->getSrcTy())) {
396 auto *PtrToInt = dyn_cast<PtrToIntInst>(IntToPtr->getOperand(0));
397 Type *CastTy = IntToPtr->getDestTy();
399 CastTy->getPointerAddressSpace() ==
400 PtrToInt->getSrcTy()->getPointerAddressSpace() &&
401 DL.getTypeSizeInBits(PtrToInt->getSrcTy()) ==
402 DL.getTypeSizeInBits(PtrToInt->getDestTy()))
403 return PtrToInt->getOperand(0);
442 replaceOperand(I, 0, Pair->first);
443 replaceOperand(I, 1, Pair->second);
453 if (Op0 && Op0->getOpcode() == Opcode) {
454 Value *A = Op0->getOperand(0);
455 Value *B = Op0->getOperand(1);
486 if (Op1 && Op1->getOpcode() == Opcode) {
488 Value *B = Op1->getOperand(0);
489 Value *C = Op1->getOperand(1);
514 if (Op0 && Op0->getOpcode() == Opcode) {
515 Value *A = Op0->getOperand(0);
516 Value *B = Op0->getOperand(1);
534 if (Op1 && Op1->getOpcode() == Opcode) {
536 Value *B = Op1->getOperand(0);
537 Value *C = Op1->getOperand(1);
558 Op0->getOpcode() == Opcode && Op1->getOpcode() == Opcode &&
571 Op0->getFastMathFlags() &
572 Op1->getFastMathFlags();
573 NewBO->setFastMathFlags(Flags);
576 NewBO->takeName(Op1);
599 // X & (Y | Z) <--> (X & Y) | (X & Z)
600 // X & (Y ^ Z) <--> (X & Y) ^ (X & Z)
604 // X | (Y & Z) <--> (X | Y) & (X | Z)
608 // X * (Y + Z) <--> (X * Y) + (X * Z)
609 // X * (Y - Z) <--> (X * Y) - (X * Z)
623 // (X {&|^} Y) >> Z <--> (X >> Z) {&|^} (Y >> Z) for all shifts.
637 return ConstantExpr::getBinOpIdentity(Opcode, V->getType());
641 /// it just returns the 'Op' inputs. But for special-cases like
649 LHS = Op->getOperand(0);
650 RHS = Op->getOperand(1);
654 // X << C --> X * (1 << C)
656 Instruction::Shl, ConstantInt::get(Op->getType(), 1), C);
663 if (OtherOp && OtherOp->getOpcode() == Instruction::AShr &&
665 // lshr nneg C, X --> ashr nneg C, X
669 return Op->getOpcode();
673 /// (e. g. "(A*B)+(A*C)" -> "A*(B+C)").
701 if (!V && (LHS->hasOneUse() || RHS->hasOneUse()))
702 V = Builder.CreateBinOp(TopLevelOpcode, B, D, RHS->getName());
721 if (!V && (LHS->hasOneUse() || RHS->hasOneUse()))
722 V = Builder.CreateBinOp(TopLevelOpcode, A, C, LHS->getName());
732 RetVal->takeName(&I);
734 // Try to add no-overflow flags to the final value.
743 HasNSW &= LOBO->hasNoSignedWrap();
744 HasNUW &= LOBO->hasNoUnsignedWrap();
748 HasNSW &= ROBO->hasNoSignedWrap();
749 HasNUW &= ROBO->hasNoUnsignedWrap();
761 if (match(V, m_APInt(CInt)) && !CInt->isMinSignedValue())
762 cast<Instruction>(RetVal)->setHasNoSignedWrap(HasNSW);
765 cast<Instruction>(RetVal)->setHasNoUnsignedWrap(HasNUW);
776 // -> (add/sub/disjoint_or C', (ctpop x))
778 // -> (cmp pred C', (ctpop x))
780 unsigned Opc = I->getOpcode();
785 // (ctpop (not x)) <-> (sub nuw nsw BitWidth(x) - (ctpop x))
795 if (cast<ICmpInst>(I)->isSigned())
808 if (!match(I->getOperand(1 - ConstIdx),
814 if (!match(I->getOperand(ConstIdx), m_ImmConstant(C)))
817 Type *Ty = Op->getType();
818 Constant *BitWidthC = ConstantInt::get(Ty, Ty->getScalarSizeInBits());
821 if (Opc == Instruction::ICmp && !cast<ICmpInst>(I)->isEquality()) {
824 if (!Cmp || !Cmp->isZeroValue())
830 if (!isFreeToInvert(Op, Op->hasOneUse(), Consumes) || !Consumes)
832 Value *NotOp = getFreelyInverted(Op, Op->hasOneUse(), &Builder);
851 R = Builder.CreateICmp(cast<ICmpInst>(I)->getSwappedPredicate(),
868 // -> (logic_shift (Binop1 (Binop2 X, inv_logic_shift(C1, C)), Y), C)
875 // -> (BinOp (logic_shift (BinOp X, Y)), Mask)
882 // -> (arithmetic_shift Binop1((not X), Y), Amt)
926 // If BinOp2 is `and`, any mask works (this only really helps for non-splat
940 auto MatchBinOp = [&](unsigned ShOpnum) -> Instruction * {
946 if (!match(I.getOperand(1 - ShOpnum),
959 unsigned ShOpc = IY->getOpcode();
960 if (ShOpc != IX->getOpcode())
964 auto *BO2 = dyn_cast<Instruction>(I.getOperand(1 - ShOpnum));
968 unsigned BinOpc = BO2->getOpcode();
1021 // -> (select C, (binop 1, T), (binop 0, F))
1024 // -> (select C, (binop -1, T), (binop 0, F))
1040 A->getType()->getScalarSizeInBits() == 1 &&
1060 C = Constant::getNullValue(V->getType());
1062 unsigned BitWidth = V->getType()->getScalarSizeInBits();
1063 C = Constant::getIntegerValue(V->getType(), APInt(BitWidth, 1));
1065 C = Constant::getAllOnesValue(V->getType());
1129 /// (eg "(A*B)+(A*C)" -> "A*(B+C)") or expanding out if this results in
1130 /// simplifications (eg: "A & (B | C) -> (A&B) | (A&C)" if this is a win).
1143 if (Op0 && rightDistributesOverLeft(Op0->getOpcode(), TopLevelOpcode)) {
1146 Value *A = Op0->getOperand(0), *B = Op0->getOperand(1), *C = RHS;
1147 Instruction::BinaryOps InnerOpcode = Op0->getOpcode(); // op'
1159 C->takeName(&I);
1164 if (L && L == ConstantExpr::getBinOpIdentity(InnerOpcode, L->getType())) {
1168 C->takeName(&I);
1173 if (R && R == ConstantExpr::getBinOpIdentity(InnerOpcode, R->getType())) {
1177 C->takeName(&I);
1182 if (Op1 && leftDistributesOverRight(TopLevelOpcode, Op1->getOpcode())) {
1185 Value *A = LHS, *B = Op1->getOperand(0), *C = Op1->getOperand(1);
1186 Instruction::BinaryOps InnerOpcode = Op1->getOpcode(); // op'
1198 A->takeName(&I);
1203 if (L && L == ConstantExpr::getBinOpIdentity(InnerOpcode, L->getType())) {
1207 A->takeName(&I);
1212 if (R && R == ConstantExpr::getBinOpIdentity(InnerOpcode, R->getType())) {
1216 A->takeName(&I);
1226 if (LHS->getParent() != RHS->getParent())
1229 if (LHS->getNumIncomingValues() < 2)
1232 if (!equal(LHS->blocks(), RHS->blocks()))
1235 Value *L0 = LHS->getIncomingValue(0);
1236 Value *R0 = RHS->getIncomingValue(0);
1238 for (unsigned I = 1, E = LHS->getNumIncomingValues(); I != E; ++I) {
1239 Value *L1 = LHS->getIncomingValue(I);
1240 Value *R1 = RHS->getIncomingValue(I);
1255 if (!LHSInst || !RHSInst || LHSInst->getOpcode() != RHSInst->getOpcode())
1257 switch (LHSInst->getOpcode()) {
1261 Value *Cond = LHSInst->getOperand(0);
1262 Value *TrueVal = LHSInst->getOperand(1);
1263 Value *FalseVal = LHSInst->getOperand(2);
1264 if (Cond == RHSInst->getOperand(0) && TrueVal == RHSInst->getOperand(2) &&
1265 FalseVal == RHSInst->getOperand(1))
1274 LHSMinMax->getPredicate() ==
1275 ICmpInst::getSwappedPredicate(RHSMinMax->getPredicate()) &&
1276 ((LHSMinMax->getLHS() == RHSMinMax->getLHS() &&
1277 LHSMinMax->getRHS() == RHSMinMax->getRHS()) ||
1278 (LHSMinMax->getLHS() == RHSMinMax->getRHS() &&
1279 LHSMinMax->getRHS() == RHSMinMax->getLHS())))
1280 return std::pair(LHSMinMax->getLHS(), LHSMinMax->getRHS());
1309 // Special-case for add/negate combination. Replace the zero in the negation
1311 // (Cond ? TVal : -N) + Z --> Cond ? True : (Z - N)
1312 // (Cond ? -N : FVal) + Z --> Cond ? (Z - N) : False
1313 auto foldAddNegate = [&](Value *TVal, Value *FVal, Value *Z) -> Value * {
1331 // (A ? B : C) op (A ? E : F) -> A ? (B op E) : (C op F)
1336 if (LHS->hasOneUse() && RHS->hasOneUse()) {
1342 } else if (LHSIsSelect && LHS->hasOneUse()) {
1343 // (A ? B : C) op Y -> A ? (B op Y) : (C op Y)
1349 } else if (RHSIsSelect && RHS->hasOneUse()) {
1350 // X op (D ? E : F) -> D ? (X op E) : (X op F)
1362 SI->takeName(&I);
1366 /// Freely adapt every user of V as-if V was changed to !V.
1370 for (User *U : make_early_inc_range(I->users())) {
1373 switch (cast<Instruction>(U)->getOpcode()) {
1376 SI->swapValues();
1377 SI->swapProfMetadata();
1382 BI->swapSuccessors(); // swaps prof metadata too
1384 BPI->swapSuccEdgesProbabilities(BI->getParent());
1393 llvm_unreachable("Got unexpected user - out of sync with "
1411 if (C->getType()->getElementType()->isIntegerTy())
1415 for (unsigned i = 0, e = CV->getNumOperands(); i != e; ++i) {
1416 Constant *Elt = CV->getAggregateElement(i);
1431 if (CV->getType()->isVectorTy() &&
1432 CV->getType()->getScalarType()->isIntegerTy() && CV->getSplatValue())
1440 // -> ({s|u}itofp (int_binop x, y))
1442 // -> ({s|u}itofp (int_binop x, (fpto{s|u}i FpC)))
1450 Type *IntTy = IntOps[0]->getType();
1452 unsigned IntSz = IntTy->getScalarSizeInBits();
1453 // This is the maximum number of inuse bits by the integer where the int -> fp
1456 APFloat::semanticsPrecision(FPTy->getScalarType()->getFltSemantics());
1464 auto IsNonZero = [&](unsigned OpNo) -> bool {
1471 auto IsNonNeg = [&](unsigned OpNo) -> bool {
1479 auto IsValidPromotion = [&](unsigned OpNo) -> bool {
1487 // can handle `MaxRepresentableBits == IntSz - 1` as the sign bit will be
1491 // Otherwise if its signed cast check that fp precisions >= bitwidth(op) -
1496 NumUsedLeadingBits[OpNo] = IntSz - ComputeNumSignBits(IntOps[OpNo]);
1497 // Finally for unsigned check that fp precision >= bitwidth(op) -
1501 IntSz - OpsKnown[OpNo].getKnownBits(SQ).countMinLeadingZeros();
1511 // Signed + Mul also requires that op is non-zero to avoid -0 cases.
1518 // Signed + Mul req non-zero
1538 if (IntTy != IntOps[1]->getType())
1592 IntBO->setHasNoSignedWrap(OutputSigned);
1593 IntBO->setHasNoUnsignedWrap(!OutputSigned);
1602 // -> ({s|u}itofp (int_binop x, y))
1604 // -> ({s|u}itofp (int_binop x, (fpto{s|u}i FpC)))
1633 /// A binop with a constant operand and a sign-extended boolean operand may be
1635 /// the constant with the two possible values of the extended boolean (0 or -1).
1637 // TODO: Handle non-commutative binop (constant is operand 0).
1645 !X->getType()->isIntOrIntVectorTy(1))
1648 // bo (sext i1 X), C --> select X, (bo -1, C), (bo 0, C)
1662 V = IsTrueArm ? SI->getTrueValue() : SI->getFalseValue();
1663 } else if (match(SI->getCondition(),
1681 Clone->replaceUsesOfWith(SI, NewOp);
1682 Clone->dropUBImplyingAttrsAndMetadata();
1690 if (!SI->hasOneUse() && !FoldWithMultiUse)
1693 Value *TV = SI->getTrueValue();
1694 Value *FV = SI->getFalseValue();
1697 if (SI->getType()->isIntOrIntVectorTy(1))
1703 // non-obfuscated minimum and maximum idioms. And in this case, at
1707 if (auto *CI = dyn_cast<FCmpInst>(SI->getCondition())) {
1708 if (CI->hasOneUse()) {
1709 Value *Op0 = CI->getOperand(0), *Op1 = CI->getOperand(1);
1727 return SelectInst::Create(SI->getCondition(), NewTV, NewFV, "", nullptr, SI);
1741 Ops.push_back(Op->DoPHITranslation(PN->getParent(), InBB));
1749 &I, Ops, SQ.getWithInstruction(InBB->getTerminator()));
1755 BranchInst *TerminatorBI = dyn_cast<BranchInst>(InBB->getTerminator());
1757 if (TerminatorBI && TerminatorBI->isConditional() &&
1758 TerminatorBI->getSuccessor(0) != TerminatorBI->getSuccessor(1) && ICmp) {
1759 bool LHSIsTrue = TerminatorBI->getSuccessor(0) == PN->getParent();
1761 TerminatorBI->getCondition(), ICmp->getCmpPredicate(), Ops[0], Ops[1],
1772 unsigned NumPHIValues = PN->getNumIncomingValues();
1779 bool OneUse = PN->hasOneUse();
1783 for (User *U : PN->users()) {
1792 // Check that all operands are phi-translatable.
1797 // Non-instructions never require phi-translation.
1802 // Phi-translate can handle phi nodes in the same block.
1804 if (I->getParent() == PN->getParent())
1807 // Operand dominates the block, no phi-translation necessary.
1808 if (DT.dominates(I, PN->getParent()))
1811 // Not phi-translatable, bail out.
1821 Value *InVal = PN->getIncomingValue(i);
1822 BasicBlock *InBB = PN->getIncomingBlock(i);
1832 if (!InVal->hasOneUser())
1843 cast<ZExtInst>(InVal)->getSrcTy()->isIntOrIntVectorTy(1) &&
1861 return nullptr; // More than one non-simplified value.
1864 // If there is exactly one non-simplified value, we can insert a copy of the
1869 BranchInst *BI = dyn_cast<BranchInst>(InBB->getTerminator());
1870 if (!BI || !BI->isUnconditional() || !DT.isReachableFromEntry(InBB))
1879 if (cast<Instruction>(InVal)->getParent() == InBB)
1883 // an infinite combine loop, and is generally non-profitable (especially
1885 if (isBackEdge(InBB, PN->getParent()))
1893 Value *Op = PN->getIncomingValue(OpIndex);
1894 BasicBlock *OpBB = PN->getIncomingBlock(OpIndex);
1899 for (Use &U : Clone->operands()) {
1903 U = U->DoPHITranslation(PN->getParent(), OpBB);
1905 Clone = InsertNewInstBefore(Clone, OpBB->getTerminator()->getIterator());
1913 PHINode *NewPN = PHINode::Create(I.getType(), PN->getNumIncomingValues());
1914 InsertNewInstBefore(NewPN, PN->getIterator());
1915 NewPN->takeName(PN);
1916 NewPN->setDebugLoc(PN->getDebugLoc());
1919 NewPN->addIncoming(NewPhiValues[i], PN->getIncomingBlock(i));
1922 for (User *U : make_early_inc_range(PN->users())) {
1946 if (!Phi0 || !Phi1 || !Phi0->hasOneUse() || !Phi1->hasOneUse() ||
1947 Phi0->getNumOperands() != Phi1->getNumOperands())
1951 if (BO.getParent() != Phi0->getParent() ||
1952 BO.getParent() != Phi1->getParent())
1971 if (Phi0->getIncomingBlock(Phi0Use) != Phi1->getIncomingBlock(Phi1Use))
1984 if (all_of(zip(Phi0->operands(), Phi1->operands()),
1987 PHINode::Create(Phi0->getType(), Phi0->getNumOperands());
1988 assert(NewIncomingValues.size() == Phi0->getNumOperands() &&
1991 for (unsigned I = 0; I < Phi0->getNumOperands(); I++)
1992 NewPhi->addIncoming(NewIncomingValues[I], Phi0->getIncomingBlock(I));
1997 if (Phi0->getNumOperands() != 2 || Phi1->getNumOperands() != 2)
2003 if (match(Phi0->getIncomingValue(0), m_ImmConstant(C0))) {
2004 ConstBB = Phi0->getIncomingBlock(0);
2005 OtherBB = Phi0->getIncomingBlock(1);
2006 } else if (match(Phi0->getIncomingValue(1), m_ImmConstant(C0))) {
2007 ConstBB = Phi0->getIncomingBlock(1);
2008 OtherBB = Phi0->getIncomingBlock(0);
2012 if (!match(Phi1->getIncomingValueForBlock(ConstBB), m_ImmConstant(C1)))
2017 // non-speculative op.
2018 auto *PredBlockBranch = dyn_cast<BranchInst>(OtherBB->getTerminator());
2019 if (!PredBlockBranch || PredBlockBranch->isConditional() ||
2026 for (auto BBIter = BO.getParent()->begin(); &*BBIter != &BO; ++BBIter)
2035 // Make a new binop in the predecessor block with the non-constant incoming
2039 Phi0->getIncomingValueForBlock(OtherBB),
2040 Phi1->getIncomingValueForBlock(OtherBB));
2042 NotFoldedNewBO->copyIRFlags(&BO);
2046 NewPhi->addIncoming(NewBO, OtherBB);
2047 NewPhi->addIncoming(NewC, ConstBB);
2081 assert(cast<VectorType>(LHS->getType())->getElementCount() ==
2082 cast<VectorType>(Inst.getType())->getElementCount());
2083 assert(cast<VectorType>(RHS->getType())->getElementCount() ==
2084 cast<VectorType>(Inst.getType())->getElementCount());
2093 LHS->hasOneUse() && RHS->hasOneUse() &&
2094 cast<ShuffleVectorInst>(LHS)->isConcat() &&
2095 cast<ShuffleVectorInst>(RHS)->isConcat()) {
2100 // but that requires an analysis of the binop-with-undef output value.
2103 BO->copyIRFlags(&Inst);
2106 BO->copyIRFlags(&Inst);
2113 BO->copyIRFlags(&Inst);
2116 M, Intrinsic::vector_reverse, V->getType());
2125 // Op(rev(V1), rev(V2)) -> rev(Op(V1, V2))
2127 (LHS->hasOneUse() || RHS->hasOneUse() ||
2128 (LHS == RHS && LHS->hasNUses(2))))
2131 // Op(rev(V1), RHSSplat)) -> rev(Op(V1, RHSSplat))
2132 if (LHS->hasOneUse() && isSplatValue(RHS))
2135 // Op(LHSSplat, rev(V2)) -> rev(Op(LHSSplat, V2))
2148 BO->copyIRFlags(&Inst);
2156 V1->getType() == V2->getType() &&
2157 (LHS->hasOneUse() || RHS->hasOneUse() || LHS == RHS)) {
2158 // Op(shuffle(V1, Mask), shuffle(V2, Mask)) -> shuffle(Op(V1, V2), Mask)
2162 // If both arguments of a commutative binop are select-shuffles that use the
2174 if (LShuf->isSelect() &&
2175 !is_contained(LShuf->getShuffleMask(), PoisonMaskElem) &&
2176 RShuf->isSelect() &&
2177 !is_contained(RShuf->getShuffleMask(), PoisonMaskElem)) {
2181 // LHS + RHS --> (V10+V20, V21+V11, V22+V12, V13+V23) --> V1 + V2
2183 NewBO->copyIRFlags(&Inst);
2199 cast<FixedVectorType>(V1->getType())->getNumElements() <=
2200 InstVTy->getNumElements()) {
2201 assert(InstVTy->getScalarType() == V1->getType()->getScalarType() &&
2207 // reorder is not possible. A 1-to-1 mapping is not required. Example:
2208 // ShMask = <1,1,2,2> and C = <5,5,6,6> --> NewC = <undef,5,6,undef>
2212 cast<FixedVectorType>(V1->getType())->getNumElements();
2213 PoisonValue *PoisonScalar = PoisonValue::get(C->getType()->getScalarType());
2216 unsigned NumElts = InstVTy->getNumElements();
2218 Constant *CElt = C->getAggregateElement(I);
2240 // TODO: We could shuffle those non-poison constant values into the
2243 // for target-independent shuffle creation.
2264 // Op(shuffle(V1, Mask), C) -> shuffle(Op(V1, NewC), Mask)
2265 // Op(C, shuffle(V1, Mask)) -> shuffle(Op(NewC, V1), Mask)
2285 X->getType() != Inst.getType() ||
2300 // bo (splat X), (bo Y, OtherOp) --> bo (splat (bo X, Y)), OtherOp
2306 // Intersect FMF on both new binops. Other (poison-generating) flags are
2309 R->copyFastMathFlags(&Inst);
2310 R->andIRFlags(RHS);
2313 NewInstBO->copyIRFlags(R);
2341 if (!(match(Op1, m_ZExtOrSExt(m_Value(Y))) && X->getType() == Y->getType() &&
2342 cast<Operator>(Op1)->getOpcode() == CastOpc &&
2343 (Op0->hasOneUse() || Op1->hasOneUse()))) {
2347 if (!Op0->hasOneUse() || !match(Op1, m_Constant(WideC)))
2349 Constant *NarrowC = getLosslessTrunc(WideC, X->getType(), CastOpc);
2364 // bo (ext X), (ext Y) --> ext (bo X, Y)
2365 // bo (ext X), C --> ext (bo X, C')
2369 NewBinOp->setHasNoSignedWrap();
2371 NewBinOp->setHasNoUnsignedWrap();
2398 // gep (select Cond, TrueC, FalseC), IndexC --> select Cond, TrueC', FalseC'
2424 Type *PtrTy = Src->getType()->getScalarType();
2428 if (C1->getBitWidth() != IndexSizeInBits ||
2429 C2->getBitWidth() != IndexSizeInBits)
2437 (Src->hasOneUse() && GEP.getOperand(1)->hasOneUse())) {
2448 // Combine Indices - If the source pointer to this getelementptr instruction
2457 // For constant GEPs, use a more general offset-based folding approach.
2458 Type *PtrTy = Src->getType()->getScalarType();
2460 (Src->hasOneUse() || Src->hasAllConstantIndices())) {
2466 for (auto Pair : enumerate(Src->indices())) {
2477 if (NumVarIndices != Src->getNumIndices()) {
2479 if (BaseType->isScalableTy())
2486 append_range(ConstantIndices, drop_begin(Src->indices(), NumVarIndices));
2502 append_range(Indices, drop_end(Src->indices(),
2503 Src->getNumIndices() - NumVarIndices));
2517 GEP, Builder.CreateGEP(Src->getSourceElementType(), Src->getOperand(0),
2521 if (Src->getResultElementType() != GEP.getSourceElementType())
2536 Value *SO1 = Src->getOperand(Src->getNumOperands()-1);
2543 if (SO1->getType() != GO1->getType())
2553 Indices.append(Src->op_begin()+1, Src->op_end()-1);
2557 cast<Constant>(*GEP.idx_begin())->isNullValue() &&
2558 Src->getNumOperands() != 1) {
2560 Indices.append(Src->op_begin()+1, Src->op_end());
2567 Src->getSourceElementType(), Src->getOperand(0), Indices, "",
2575 bool &DoesConsume, unsigned Depth) {
2577 // ~(~(X)) -> X.
2589 if (Depth++ >= MaxAnalysisRecursionDepth)
2601 return Builder->CreateCmp(I->getInversePredicate(), I->getOperand(0),
2602 I->getOperand(1));
2606 // If `V` is of the form `A + B` then `-1 - V` can be folded into
2607 // `(-1 - B) - A` if we are willing to invert all of the uses.
2609 if (auto *BV = getFreelyInvertedImpl(B, B->hasOneUse(), Builder,
2610 DoesConsume, Depth))
2611 return Builder ? Builder->CreateSub(BV, A) : NonNull;
2612 if (auto *AV = getFreelyInvertedImpl(A, A->hasOneUse(), Builder,
2613 DoesConsume, Depth))
2614 return Builder ? Builder->CreateSub(AV, B) : NonNull;
2621 if (auto *BV = getFreelyInvertedImpl(B, B->hasOneUse(), Builder,
2622 DoesConsume, Depth))
2623 return Builder ? Builder->CreateXor(A, BV) : NonNull;
2624 if (auto *AV = getFreelyInvertedImpl(A, A->hasOneUse(), Builder,
2625 DoesConsume, Depth))
2626 return Builder ? Builder->CreateXor(AV, B) : NonNull;
2630 // If `V` is of the form `B - A` then `-1 - V` can be folded into
2631 // `A + (-1 - B)` if we are willing to invert all of the uses.
2633 if (auto *AV = getFreelyInvertedImpl(A, A->hasOneUse(), Builder,
2634 DoesConsume, Depth))
2635 return Builder ? Builder->CreateAdd(AV, B) : NonNull;
2642 if (auto *AV = getFreelyInvertedImpl(A, A->hasOneUse(), Builder,
2643 DoesConsume, Depth))
2644 return Builder ? Builder->CreateAShr(AV, B) : NonNull;
2656 if (!getFreelyInvertedImpl(B, B->hasOneUse(), /*Builder*/ nullptr,
2657 LocalDoesConsume, Depth))
2659 if (Value *NotA = getFreelyInvertedImpl(A, A->hasOneUse(), Builder,
2660 LocalDoesConsume, Depth)) {
2663 Value *NotB = getFreelyInvertedImpl(B, B->hasOneUse(), Builder,
2664 DoesConsume, Depth);
2668 return Builder->CreateBinaryIntrinsic(
2669 getInverseMinMaxIntrinsic(II->getIntrinsicID()), NotA, NotB);
2670 return Builder->CreateSelect(Cond, NotA, NotB);
2679 for (Use &U : PN->operands()) {
2680 BasicBlock *IncomingBlock = PN->getIncomingBlock(U);
2683 /*Builder=*/nullptr, LocalDoesConsume, MaxAnalysisRecursionDepth - 1);
2696 Builder->SetInsertPoint(PN);
2698 Builder->CreatePHI(PN->getType(), PN->getNumIncomingValues());
2700 NewPN->addIncoming(Val, Pred);
2707 if (auto *AV = getFreelyInvertedImpl(A, A->hasOneUse(), Builder,
2708 DoesConsume, Depth))
2709 return Builder ? Builder->CreateSExt(AV, V->getType()) : NonNull;
2714 if (auto *AV = getFreelyInvertedImpl(A, A->hasOneUse(), Builder,
2715 DoesConsume, Depth))
2716 return Builder ? Builder->CreateTrunc(AV, V->getType()) : NonNull;
2721 // (~(A | B)) -> (~A & ~B)
2722 // (~(A & B)) -> (~A | ~B)
2725 Value *B) -> Value * {
2727 if (!getFreelyInvertedImpl(B, B->hasOneUse(), /*Builder=*/nullptr,
2728 LocalDoesConsume, Depth))
2730 if (auto *NotA = getFreelyInvertedImpl(A, A->hasOneUse(), Builder,
2731 LocalDoesConsume, Depth)) {
2732 auto *NotB = getFreelyInvertedImpl(B, B->hasOneUse(), Builder,
2733 LocalDoesConsume, Depth);
2736 return Builder ? Builder->CreateLogicalOp(Opcode, NotA, NotB) : NonNull;
2737 return Builder ? Builder->CreateBinOp(Opcode, NotA, NotB) : NonNull;
2766 if (GEPEltType->isIntegerTy(8))
2771 if (GEPEltType->isScalableTy())
2774 // gep i32 p, mul(O, C) -> gep i8, p, mul(O, C*4) to fold the two multiplies
2785 return PtrOpGep && PtrOpGep->hasAllConstantIndices() &&
2788 return match(V, m_APInt(C)) && !C->isZero();
2794 auto *Op1 = dyn_cast<GetElementPtrInst>(PN->getOperand(0));
2799 // through the back-edge of a loop. Folding a GEP into itself means that
2806 GEPNoWrapFlags NW = Op1->getNoWrapFlags();
2808 int DI = -1;
2810 for (auto I = PN->op_begin()+1, E = PN->op_end(); I !=E; ++I) {
2812 if (!Op2 || Op1->getNumOperands() != Op2->getNumOperands() ||
2813 Op1->getSourceElementType() != Op2->getSourceElementType())
2823 for (unsigned J = 0, F = Op1->getNumOperands(); J != F; ++J) {
2824 if (Op1->getOperand(J)->getType() != Op2->getOperand(J)->getType())
2827 if (Op1->getOperand(J) != Op2->getOperand(J)) {
2828 if (DI == -1) {
2837 if (CurTy->isStructTy())
2856 CurTy = Op1->getSourceElementType();
2859 GetElementPtrInst::getTypeAtIndex(CurTy, Op1->getOperand(J));
2864 NW &= Op2->getNoWrapFlags();
2870 if (DI != -1 && !PN->hasOneUse())
2873 auto *NewGEP = cast<GetElementPtrInst>(Op1->clone());
2874 NewGEP->setNoWrapFlags(NW);
2876 if (DI == -1) {
2887 NewPN = Builder.CreatePHI(Op1->getOperand(DI)->getType(),
2888 PN->getNumOperands());
2891 for (auto &I : PN->operands())
2892 NewPN->addIncoming(cast<GEPOperator>(I)->getOperand(DI),
2893 PN->getIncomingBlock(I));
2895 NewGEP->setOperand(DI, NewPN);
2898 NewGEP->insertBefore(*GEP.getParent(), GEP.getParent()->getFirstInsertionPt());
2914 // compile-time.
2916 auto VWidth = GEPFVTy->getNumElements();
2938 DL.getIndexType(GEP.getPointerOperandType()->getScalarType());
2947 Type *IndexTy = (*I)->getType();
2949 IndexTy->isVectorTy()
2951 cast<VectorType>(IndexTy)->getElementCount())
2957 if (EltTy->isSized() && DL.getTypeAllocSize(EltTy).isZero())
2958 if (!isa<Constant>(*I) || !match(I->get(), m_Zero())) {
2965 // it to what we need. If narrower, sign-extend it to what we need.
2975 if (!GEPEltType->isIntegerTy(8) && GEP.hasAllConstantIndices()) {
3002 if (GEP.getOperand(1)->getType()->getScalarSizeInBits() ==
3007 // Canonicalize (gep i8* X, (ptrtoint Y)-(ptrtoint X)) to (bitcast Y),
3015 GEPType == Y->getType()) {
3032 if (ExactIns->isExact()) {
3044 if (ExactIns->isExact() && ExactIns->hasOneUse()) {
3045 // Try to canonicalize non-i8 element type to i8 if the index is an
3047 // with a constant RHS, we can fold the non-i8 element scale into the
3053 C->uge(countr_zero(TyAllocSize)))
3054 NewC = *C - countr_zero(TyAllocSize);
3065 // For sdiv we need to make sure we arent creating INT_MIN / -1.
3072 static_cast<Instruction::BinaryOps>(ExactIns->getOpcode()), V,
3073 ConstantInt::get(V->getType(), *NewC));
3074 cast<BinaryOperator>(NewOp)->setIsExact();
3083 // We do not handle pointer-vector geps here.
3084 if (GEPType->isVectorTy())
3089 // is nsw, and the add operands are non-negative.
3106 cast<OverflowingBinaryOperator>(GEP.getOperand(1))->hasNoSignedWrap(),
3128 Builder.CreateSExt(Idx1, GEP.getOperand(1)->getType()), "",
3133 Builder.CreateSExt(C, GEP.getOperand(1)->getType()),
3140 DL.getIndexSizeInBits(PtrOp->getType()->getPointerAddressSpace());
3143 PtrOp->stripAndAccumulateInBoundsConstantOffsets(DL,
3146 uint64_t DerefBytes = UnderlyingPtrOp->getPointerDereferenceableBytes(
3160 // nusw + nneg -> nuw
3180 return isa<GlobalVariable>(LI->getPointerOperand());
3204 return Dest && Dest->Ptr == UsedV;
3216 for (User *U : PI->users()) {
3218 switch (I->getOpcode()) {
3235 if (!ICI->isEquality())
3237 unsigned OtherIndex = (ICI->getOperand(0) == PI) ? 1 : 0;
3238 if (!isNeverEqualToUnescapedAlloc(ICI->getOperand(OtherIndex), TLI, AI))
3246 // that is alignment is a power-of-2 and the size is a multiple of the
3250 return match(CB->getArgOperand(0), m_APInt(Alignment)) &&
3251 match(CB->getArgOperand(1), m_APInt(Size)) &&
3252 Alignment->isPowerOf2() && Size->urem(*Alignment).isZero();
3256 if (CB && TLI.getLibFunc(*CB->getCalledFunction(), TheLibFunc) &&
3265 // Ignore no-op and store intrinsics.
3267 switch (II->getIntrinsicID()) {
3275 if (MI->isVolatile() || MI->getRawDest() != PI)
3319 if (SI->isVolatile() || SI->getPointerOperand() != PI)
3366 if (II->getIntrinsicID() == Intrinsic::objectsize) {
3386 ConstantInt::get(Type::getInt1Ty(C->getContext()),
3387 C->isFalseWhenEqual()));
3390 if (DVI->isAddressOfVariable())
3393 if (DVR->isAddressOfVariable())
3398 replaceInstUsesWith(*I, PoisonValue::get(I->getType()));
3405 Module *M = II->getModule();
3407 InvokeInst::Create(F, II->getNormalDest(), II->getUnwindDest(), {}, "",
3408 II->getParent());
3437 if (DVI->isAddressOfVariable() || DVI->getExpression()->startsWithDeref())
3438 DVI->eraseFromParent();
3440 if (DVR->isAddressOfVariable() || DVR->getExpression()->startsWithDeref())
3441 DVR->eraseFromParent();
3460 /// The profitability is out-of concern here and this function should
3467 BasicBlock *PredBB = FreeInstrBB->getSinglePredecessor();
3479 Instruction *FreeInstrBBTerminator = FreeInstrBB->getTerminator();
3487 if (FreeInstrBB->size() != 2) {
3488 for (const Instruction &Inst : FreeInstrBB->instructionsWithoutDebug()) {
3492 if (!Cast || !Cast->isNoopCast(DL))
3497 Instruction *TI = PredBB->getTerminator();
3502 m_Specific(Op->stripPointerCasts())),
3520 Instr.moveBeforePreserving(TI->getIterator());
3522 assert(FreeInstrBB->size() == 1 &&
3526 // remove any attributes on its parameter that imply it's non-null, because
3528 // we can get miscompiles if we keep them. This is conservative if non-null is
3548 // free undef -> unreachable.
3563 if (CI && CI->hasOneUse())
3589 if (!RetVal || !AttributeFuncs::isNoFPClassCompatibleType(RetVal->getType()))
3593 FPClassTest ReturnClass = F->getAttributes().getRetNoFPClass();
3617 if (Prev->isEHPad())
3623 // even if it is not side-effect free.
3627 replaceInstUsesWith(*Prev, PoisonValue::get(Prev->getType()));
3642 // If this store is the second-to-last instruction in the basic block
3648 return BBI->isDebugOrPseudoInst() ||
3649 (isa<BitCastInst>(BBI) && BBI->getType()->isPointerTy());
3652 BasicBlock::iterator FirstInstr = BBI->getParent()->begin();
3655 --BBI;
3674 for (PHINode &PN : To->phis())
3689 BasicBlock *BB = I->getParent();
3691 make_range(std::next(BB->getTerminator()->getReverseIterator()),
3692 std::next(I->getReverseIterator())))) {
3693 if (!Inst.use_empty() && !Inst.getType()->isTokenTy()) {
3697 if (Inst.isEHPad() || Inst.getType()->isTokenTy())
3699 // RemoveDIs: erase debug-info on this instruction manually.
3706 if (handleUnreachableTerminator(BB->getTerminator(), Changed)) {
3726 handleUnreachableFrom(&BB->front(), Worklist);
3755 BPI->swapSuccEdgesProbabilities(BI.getParent());
3759 // Canonicalize logical-and-with-invert as logical-or-with-invert.
3761 // br (X && !Y), T, F --> br !(X && !Y), F, T --> br (!X || Y), F, T
3766 Value *NotX = Builder.CreateNot(X, "not." + X->getName());
3770 BPI->swapSuccEdgesProbabilities(BI.getParent());
3777 return replaceOperand(BI, 0, ConstantInt::getFalse(Cond->getType()));
3779 // Canonicalize, for example, fcmp_one -> fcmp_oeq.
3785 Cmp->setPredicate(CmpInst::getInversePredicate(Pred));
3788 BPI->swapSuccEdgesProbabilities(BI.getParent());
3799 BI.getSuccessor(!CI->getZExtValue()));
3807 for (auto &U : make_early_inc_range(Cond->uses())) {
3810 replaceUse(U, ConstantInt::getTrue(Cond->getType()));
3816 replaceUse(U, ConstantInt::getFalse(Cond->getType()));
3833 auto *C = dyn_cast<ConstantInt>(Select->getOperand(CstOpIdx));
3837 BasicBlock *CstBB = SI.findCaseValue(C)->getCaseSuccessor();
3840 Value *X = Select->getOperand(3 - CstOpIdx);
3843 if (!match(Select->getCondition(),
3852 if (!CR.contains(Case.getCaseValue()->getValue()))
3863 // Change 'switch (X+4) case 1:' into 'switch (X) case -3'.
3875 // Change 'switch (1-X) case 1:' into 'switch (X) case 0'.
3887 ShiftAmt < Op0->getType()->getScalarSizeInBits() &&
3889 return Case.getCaseValue()->getValue().countr_zero() >= ShiftAmt;
3893 if (Shl->hasNoUnsignedWrap() || Shl->hasNoSignedWrap() ||
3894 Shl->hasOneUse()) {
3896 if (!Shl->hasNoUnsignedWrap() && !Shl->hasNoSignedWrap()) {
3898 unsigned BitWidth = Op0->getType()->getScalarSizeInBits();
3900 Op0, APInt::getLowBitsSet(BitWidth, BitWidth - ShiftAmt));
3903 const APInt &CaseVal = Case.getCaseValue()->getValue();
3904 APInt ShiftedCase = Shl->hasNoSignedWrap() ? CaseVal.ashr(ShiftAmt)
3915 Type *SrcTy = Op0->getType();
3916 unsigned NewWidth = SrcTy->getScalarSizeInBits();
3919 const APInt &CaseVal = Case.getCaseValue()->getValue();
3924 APInt TruncatedCase = Case.getCaseValue()->getValue().trunc(NewWidth);
3949 std::min(LeadingKnownZeros, C.getCaseValue()->getValue().countl_zero());
3951 std::min(LeadingKnownOnes, C.getCaseValue()->getValue().countl_one());
3954 unsigned NewWidth = Known.getBitWidth() - std::max(LeadingKnownZeros, LeadingKnownOnes);
3957 // But do not shrink to a non-standard type, because backend can't generate
3967 APInt TruncatedCase = Case.getCaseValue()->getValue().trunc(NewWidth);
3979 SI.findCaseValue(CI)->getCaseSuccessor());
3992 Intrinsic::ID OvID = WO->getIntrinsicID();
3994 if (match(WO->getRHS(), m_APIntAllowPoison(C))) {
3997 // extractvalue (any_mul_with_overflow X, -1), 0 --> -X
3998 if (C->isAllOnes())
3999 return BinaryOperator::CreateNeg(WO->getLHS());
4000 // extractvalue (any_mul_with_overflow X, 2^n), 0 --> X << n
4001 if (C->isPowerOf2()) {
4003 WO->getLHS(),
4004 ConstantInt::get(WO->getLHS()->getType(), C->logBase2()));
4012 if (!WO->hasOneUse())
4018 Instruction::BinaryOps BinOp = WO->getBinaryOp();
4019 Value *LHS = WO->getLHS(), *RHS = WO->getRHS();
4021 replaceInstUsesWith(*WO, PoisonValue::get(WO->getType()));
4028 // (usub LHS, RHS) overflows when LHS is unsigned-less-than RHS.
4030 return new ICmpInst(ICmpInst::ICMP_ULT, WO->getLHS(), WO->getRHS());
4032 // smul with i1 types overflows when both sides are set: -1 * -1 == +1, but
4035 WO->getLHS()->getType()->isIntOrIntVectorTy(1))
4036 return BinaryOperator::CreateAnd(WO->getLHS(), WO->getRHS());
4038 // extractvalue (umul_with_overflow X, X), 1 -> X u> 2^(N/2)-1
4039 if (OvID == Intrinsic::umul_with_overflow && WO->getLHS() == WO->getRHS()) {
4040 unsigned BitWidth = WO->getLHS()->getType()->getScalarSizeInBits();
4044 ICmpInst::ICMP_UGT, WO->getLHS(),
4045 ConstantInt::get(WO->getLHS()->getType(),
4053 // Compute the no-wrap range for LHS given RHS=C, then construct an
4056 WO->getBinaryOp(), *C, WO->getNoWrapKind());
4061 auto *OpTy = WO->getRHS()->getType();
4062 auto *NewLHS = WO->getLHS();
4085 for (exti = EV.idx_begin(), insi = IV->idx_begin(),
4086 exte = EV.idx_end(), inse = IV->idx_end();
4098 return ExtractValueInst::Create(IV->getAggregateOperand(),
4106 return replaceInstUsesWith(EV, IV->getInsertedValueOperand());
4116 Value *NewEV = Builder.CreateExtractValue(IV->getAggregateOperand(),
4118 return InsertValueInst::Create(NewEV, IV->getInsertedValueOperand(),
4130 return ExtractValueInst::Create(IV->getInsertedValueOperand(),
4139 if (auto *STy = dyn_cast<StructType>(Agg->getType());
4140 STy && STy->isScalableTy())
4143 // If the (non-volatile) load only has one use, we can rewrite this to a
4148 if (L->isSimple() && L->hasOneUse()) {
4159 Value *GEP = Builder.CreateInBoundsGEP(L->getType(),
4160 L->getPointerOperand(), Indices);
4164 NL->setAAMetadata(L->getAAMetadata());
4176 // -> select cond, (extract TV), (extract FV)
4184 // the value inserted, if appropriate. Similarly for extracts from single-use
4186 // and if again single-use then via load (gep (gep)) to load (gep).
4205 // match foreign exceptions (or didn't, before gcc-4.7).
4217 return TypeInfo->isNullValue();
4224 cast<ArrayType>(LHS->getType())->getNumElements()
4226 cast<ArrayType>(RHS->getType())->getNumElements();
4230 // The logic here should be correct for any real-world personality function.
4232 // be conditioned on the personality function, like the catch-all logic is.
4234 classifyEHPersonality(LI.getParent()->getParent()->getPersonalityFn());
4239 SmallVector<Constant *, 16> NewClauses; // - Clauses for the new instruction;
4240 bool CleanupFlag = LI.isCleanup(); // - The new instruction is a cleanup.
4248 Constant *TypeInfo = CatchClause->stripPointerCasts();
4256 // Repeated catch clause - drop the redundant copy.
4260 // If this is a catch-all then there is no point in keeping any following
4278 ArrayType *FilterType = cast<ArrayType>(FilterClause->getType());
4279 unsigned NumTypeInfos = FilterType->getNumElements();
4295 // Not an empty filter - it contains at least one null typeinfo.
4298 Constant::getNullValue(FilterType->getElementType());
4299 // If this typeinfo is a catch-all then the filter can never match.
4318 // catch-alls. If so, the filter can be discarded.
4321 Constant *Elt = Filter->getOperand(j);
4322 Constant *TypeInfo = Elt->stripPointerCasts();
4324 // This element is a catch-all. Bail out, noting this fact.
4351 // A filter containing a catch-all cannot match anything by definition.
4363 FilterType = ArrayType::get(FilterType->getElementType(),
4392 if (!isa<ArrayType>(NewClauses[j]->getType()))
4426 ArrayType *FTy = dyn_cast<ArrayType>(Filter->getType());
4428 // Not a filter - skip it.
4430 unsigned FElts = FTy->getNumElements();
4433 for (unsigned j = NewClauses.size() - 1; j != i; --j) {
4435 ArrayType *LTy = dyn_cast<ArrayType>(LFilter->getType());
4437 // Not a filter - skip it.
4450 unsigned LElts = LTy->getNumElements();
4470 // Since Filter is non-empty and contains only zeros, it is a subset of
4474 if (LArray->getOperand(l)->isNullValue()) {
4475 // LFilter contains a zero - discard it.
4490 Value *FTypeInfo = FArray->getOperand(f)->stripPointerCasts();
4493 Value *LTypeInfo = LArray->getOperand(l)->stripPointerCasts();
4517 NLI->addClause(C);
4523 NLI->setCleanup(CleanupFlag);
4542 // conditions 1) one-use, 2) does not produce poison, and 3) has all but one
4543 // guaranteed-non-poison operands then push the freeze through to the one
4544 // operand that is not guaranteed non-poison. The actual transform is as
4548 // ; single guaranteed-non-poison operands
4560 if (!OrigOpInst || !OrigOpInst->hasOneUse() || isa<PHINode>(OrigOp))
4575 for (Use &U : OrigOpInst->operands()) {
4585 OrigOpInst->dropPoisonGeneratingAnnotations();
4587 // If all operands are guaranteed to be non-poison, we can drop freeze.
4593 MaybePoisonOperand->get(), MaybePoisonOperand->get()->getName() + ".fr");
4608 for (Use &U : PN->incoming_values()) {
4609 if (DT.dominates(PN->getParent(), PN->getIncomingBlock(U))) {
4624 Value *StartV = StartU->get();
4625 BasicBlock *StartBB = PN->getIncomingBlock(*StartU);
4629 if (StartNeedsFreeze && StartBB->getTerminator() == StartV)
4642 // Assume that PN is non-poison, because it will be after the transform.
4652 append_range(Worklist, I->operands());
4656 I->dropPoisonGeneratingAnnotations();
4659 Builder.SetInsertPoint(StartBB->getTerminator());
4661 StartV->getName() + ".fr");
4670 if (isa<Constant>(Op) || Op->hasOneUse())
4681 FI.getFunction()->getEntryBlock().getFirstNonPHIOrDbgOrAlloca();
4683 auto MoveBeforeOpt = cast<Instruction>(Op)->getInsertionPointAfterDef();
4691 MoveBefore = MoveBefore->getNextNonDebugInstruction()->getIterator();
4692 // Re-point iterator to come after any debug-info records, if we're
4698 FI.moveBefore(*MoveBefore->getParent(), MoveBefore);
4702 Op->replaceUsesWithIf(&FI, [&](Use &U) -> bool {
4713 for (auto *U : V->users()) {
4728 // freeze (phi const, x) --> phi const, (freeze x)
4740 // - or: pick -1
4741 // - select's condition: if the true value is constant, choose it by making
4743 // - default: pick 0
4747 // because we must produce the same value for all uses of the freeze -
4781 if (match(Op0, m_Constant(C)) && C->containsUndefOrPoisonElement()) {
4782 Constant *ReplaceC = getUndefReplacement(I.getType()->getScalarType());
4794 /// shows up for unused out-params in idiomatic C/C++ code. Note that this
4799 // TODO: handle e.g. store to alloca here - only worth doing if we extend
4806 auto *AI = dyn_cast<AllocaInst>(getUnderlyingObject(Dest->Ptr));
4842 BasicBlock *SrcBlock = I->getParent();
4844 // Cannot move control-flow-involving, volatile loads, vaarg, etc.
4845 if (isa<PHINode>(I) || I->isEHPad() || I->mayThrow() || !I->willReturn() ||
4846 I->isTerminator())
4857 if (isa<CatchSwitchInst>(DestBlock->getTerminator()))
4862 if (CI->isConvergent())
4868 if (I->mayWriteToMemory()) {
4875 if (I->mayReadFromMemory() &&
4876 !I->hasMetadata(LLVMContext::MD_invariant_load)) {
4880 if (DestBlock->getUniquePredecessor() != I->getParent())
4882 for (BasicBlock::iterator Scan = std::next(I->getIterator()),
4883 E = I->getParent()->end();
4885 if (Scan->mayWriteToMemory())
4889 I->dropDroppableUses([&](const Use *U) {
4890 auto *I = dyn_cast<Instruction>(U->getUser());
4891 if (I && I->getParent() != DestBlock) {
4900 BasicBlock::iterator InsertPos = DestBlock->getFirstInsertionPt();
4901 I->moveBefore(*DestBlock, InsertPos);
4919 // assignments can be re-ordered past other assignments to the same variable
4921 // undone. And salvaging all users outside of this block can un-necessarily
4922 // alter the lifetime of the live-value that the variable refers to.
4923 // Some of these things can be resolved by tolerating debug use-before-defs in
4924 // LLVM-IR, however it depends on the instruction-referencing CodeGen backend
4937 if (DbgUser->getParent() != DestBlock)
4944 if (DVI->getParent() == SrcBlock)
4947 [](auto *A, auto *B) { return B->comesBefore(A); });
4960 DebugVariable(User->getVariable(), User->getExpression(),
4961 User->getDebugLoc()->getInlinedAt());
4971 DIIClones.emplace_back(cast<DbgVariableIntrinsic>(User->clone()));
4973 DIIClones.back()->replaceVariableLocationOp(I, I->getOperand(0));
4983 DIIClone->insertBefore(InsertPos);
4996 // Fetch all DbgVariableRecords not already in the destination.
4999 if (DVR->getParent() != DestBlock)
5002 // Fetch a second collection, of DbgVariableRecords in the source block that
5006 if (DVR->getParent() == SrcBlock)
5013 auto Order = [](DbgVariableRecord *A, DbgVariableRecord *B) -> bool {
5014 return B->getInstruction()->comesBefore(A->getInstruction());
5028 DebugVariable(DVR->getVariable(), DVR->getExpression(),
5029 DVR->getDebugLoc()->getInlinedAt());
5030 CountMap[std::make_pair(DVR->getInstruction(), DbgUserVariable)] += 1;
5047 llvm::reverse(filterDbgVars(Inst->getDbgRecordRange()))) {
5050 DVR.getDebugLoc()->getInlinedAt());
5055 if (FilterIt->second != nullptr)
5057 FilterIt->second = &DVR;
5067 if (DVR->Type == DbgVariableRecord::LocationType::Declare)
5071 DebugVariable(DVR->getVariable(), DVR->getExpression(),
5072 DVR->getDebugLoc()->getInlinedAt());
5077 InstVarPair IVP = std::make_pair(DVR->getInstruction(), DbgUserVariable);
5081 if (It != FilterOutMap.end() && It->second != DVR)
5088 if (DVR->isDbgAssign())
5091 DVRClones.emplace_back(DVR->clone());
5105 // DVR-3 (third insertion goes here)
5106 // DVR-2 (second insertion goes here)
5107 // DVR-1 (first insertion goes here)
5108 // Any-Prior-DVRs
5112 InsertPos->getParent()->insertDbgRecordBefore(DVRClone, InsertPos);
5120 // worklist, which means they'll end up popped from the worklist in-order.
5152 [this](Instruction *I) -> std::optional<BasicBlock *> {
5156 BasicBlock *BB = I->getParent();
5160 for (Use &U : I->uses()) {
5162 if (User->isDroppable())
5168 // Special handling for Phi nodes - get the block the use occurs in.
5169 BasicBlock *UserBB = UserInst->getParent();
5171 UserBB = PN->getIncomingBlock(U);
5187 auto *Term = UserParent->getTerminator();
5193 // - I dominates the User (by SSA form);
5194 // - the User will be executed at most once.
5196 if (UserParent->getUniquePredecessor() != BB && !succ_empty(Term))
5222 for (Use &U : I->operands())
5236 LLVM_DEBUG(raw_string_ostream SS(OrigI); I->print(SS););
5249 if (!Result->getDebugLoc())
5250 Result->setDebugLoc(I->getDebugLoc());
5252 Result->copyMetadata(*I, LLVMContext::MD_annotation);
5254 I->replaceAllUsesWith(Result);
5257 Result->takeName(I);
5260 BasicBlock *InstParent = I->getParent();
5261 BasicBlock::iterator InsertPos = I->getIterator();
5266 if (isa<PHINode>(I)) // PHI -> Non-PHI
5267 InsertPos = InstParent->getFirstInsertionPt();
5268 else // Non-PHI -> PHI
5269 InsertPos = InstParent->getFirstNonPHIIt();
5272 Result->insertInto(InstParent, InsertPos);
5313 if (!I->hasMetadataOtherThanDebugLoc())
5320 for (const auto &MDOperand : MDScopeList->operands())
5325 Track(I->getMetadata(LLVMContext::MD_alias_scope), UsedAliasScopesAndLists);
5326 Track(I->getMetadata(LLVMContext::MD_noalias), UsedNoAliasScopesAndLists);
5334 assert(Decl->use_empty() &&
5336 const MDNode *MDSL = Decl->getScopeList();
5337 assert(MDSL->getNumOperands() == 1 &&
5339 auto &MDOperand = MDSL->getOperand(0);
5350 /// post-order and adding all reachable code to the worklist.
5367 for (PHINode &PN : Succ->phis())
5376 if (!BB->isEntryBlock() && all_of(predecessors(BB), [&](BasicBlock *Pred) {
5419 // these call instructions consumes non-trivial amount of time and
5429 Instruction *TI = BB->getTerminator();
5430 if (BranchInst *BI = dyn_cast<BranchInst>(TI); BI && BI->isConditional()) {
5431 if (isa<UndefValue>(BI->getCondition())) {
5436 if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition())) {
5437 bool CondVal = Cond->getZExtValue();
5438 HandleOnlyLiveSuccessor(BB, BI->getSuccessor(!CondVal));
5442 if (isa<UndefValue>(SI->getCondition())) {
5447 if (auto *Cond = dyn_cast<ConstantInt>(SI->getCondition())) {
5449 SI->findCaseValue(Cond)->getCaseSuccessor());
5485 Inst->eraseFromParent();
5516 !F.hasFnAttribute("instcombine-no-verify-fixpoint");
5518 /// Builder - This is an IRBuilder that automatically inserts new
5566 "Use 'instcombine<no-verify-fixpoint>' or function attribute "
5567 "'instcombine-no-verify-fixpoint' to suppress this error.",
5588 static_cast<PassInfoMixin<InstCombinePass> *>(this)->printPipeline(
5591 OS << "max-iterations=" << Options.MaxIterations << ";";
5592 OS << (Options.VerifyFixpoint ? "" : "no-") << "verify-fixpoint";
5615 auto *BFI = (PSI && PSI->hasProfileSummary()) ?
5666 (PSI && PSI->hasProfileSummary()) ?
5672 BPI = &WrapperPass->getBPI();