19using namespace PatternMatch;
21#define DEBUG_TYPE "instcombine"
39 unsigned MaximalPossibleTotalShiftAmount =
42 APInt MaximalRepresentableShiftAmount =
44 return MaximalRepresentableShiftAmount.
uge(MaximalPossibleTotalShiftAmount);
60 bool AnalyzeForSignBitExtraction) {
72 Value *Trunc =
nullptr;
91 if (AnalyzeForSignBitExtraction && !HadTwoRightShifts)
98 if (!IdenticalShOpcodes && !AnalyzeForSignBitExtraction)
104 if (Trunc && !AnalyzeForSignBitExtraction &&
109 auto *NewShAmt = dyn_cast_or_null<Constant>(
114 unsigned NewShAmtBitWidth = NewShAmt->getType()->getScalarSizeInBits();
115 unsigned XBitWidth =
X->getType()->getScalarSizeInBits();
118 APInt(NewShAmtBitWidth, XBitWidth))))
126 if (HadTwoRightShifts && (Trunc || AnalyzeForSignBitExtraction)) {
130 APInt(NewShAmtBitWidth, XBitWidth - 1))))
133 if (AnalyzeForSignBitExtraction)
137 assert(IdenticalShOpcodes &&
"Should not get here with different shifts.");
139 if (NewShAmt->getType() !=
X->getType()) {
141 X->getType(),
SQ.
DL);
153 if (ShiftOpcode == Instruction::BinaryOps::Shl) {
193 "The input must be 'shl'!");
208 bool HadTrunc = WidestTy != NarrowestTy;
240 MaskShAmt, ShiftShAmt,
false,
false, Q));
251 SumOfShAmts, ConstantInt::get(SumOfShAmts->getType()->getScalarType(),
254 Instruction::ZExt, SumOfShAmts, ExtendedTy, Q.
DL);
255 if (!ExtendedSumOfShAmts)
261 Instruction::Shl, ExtendedAllOnes, ExtendedSumOfShAmts, Q.
DL);
262 if (!ExtendedInvertedMask)
279 ShiftShAmt, MaskShAmt,
false,
false, Q));
291 ShAmtsDiff, ConstantInt::get(ShAmtsDiff->getType()->getScalarType(),
300 if (!ExtendedNumHighBitsToClear)
306 ExtendedNumHighBitsToClear, Q.
DL);
350 assert(
I.isShift() &&
"Expected a shift as input");
351 auto *BinInst = dyn_cast<BinaryOperator>(
I.getOperand(0));
353 (!BinInst->isBitwiseLogicOp() &&
354 BinInst->getOpcode() != Instruction::Add &&
355 BinInst->getOpcode() != Instruction::Sub) ||
356 !BinInst->hasOneUse())
365 if ((BinInst->getOpcode() == Instruction::Add ||
366 BinInst->getOpcode() == Instruction::Sub) &&
367 ShiftOpcode != Instruction::Shl)
370 Type *Ty =
I.getType();
375 auto matchFirstShift = [&](
Value *V,
Value *W) {
387 bool FirstShiftIsOp1 =
false;
388 if (matchFirstShift(BinInst->getOperand(0), BinInst->getOperand(1)))
389 Y = BinInst->getOperand(1);
390 else if (matchFirstShift(BinInst->getOperand(1), BinInst->getOperand(0))) {
391 Y = BinInst->getOperand(0);
392 FirstShiftIsOp1 = BinInst->getOpcode() == Instruction::Sub;
400 Value *Op1 = FirstShiftIsOp1 ? NewShift2 : NewShift1;
401 Value *Op2 = FirstShiftIsOp1 ? NewShift1 : NewShift2;
409 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
411 Type *Ty =
I.getType();
425 if (isa<Constant>(Op0))
426 if (
SelectInst *SI = dyn_cast<SelectInst>(Op1))
430 if (
Constant *CUI = dyn_cast<Constant>(Op1))
434 if (
auto *NewShift = cast_or_null<Instruction>(
446 if (
I.getOpcode() == Instruction::Shl) {
465 assert(!
AC->isZero() &&
"Expected simplify of shifted zero");
466 unsigned PosOffset = (-*AddC).getZExtValue();
468 auto isSuitableForPreShift = [PosOffset, &
I,
AC]() {
469 switch (
I.getOpcode()) {
472 case Instruction::Shl:
473 return (
I.hasNoSignedWrap() ||
I.hasNoUnsignedWrap()) &&
474 AC->eq(
AC->lshr(PosOffset).shl(PosOffset));
475 case Instruction::LShr:
476 return I.isExact() &&
AC->eq(
AC->shl(PosOffset).lshr(PosOffset));
477 case Instruction::AShr:
478 return I.isExact() &&
AC->eq(
AC->shl(PosOffset).ashr(PosOffset));
481 if (isSuitableForPreShift()) {
482 Constant *NewC = ConstantInt::get(Ty,
I.getOpcode() == Instruction::Shl
483 ?
AC->lshr(PosOffset)
484 :
AC->shl(PosOffset));
487 if (
I.getOpcode() == Instruction::Shl) {
515 if ((
I.getOpcode() == Instruction::LShr ||
516 I.getOpcode() == Instruction::AShr) &&
518 isa<CmpIntrinsic>(CmpIntr) &&
540 const APInt *InnerShiftConst;
547 bool IsInnerShl = InnerShift->
getOpcode() == Instruction::Shl;
548 if (IsInnerShl == IsOuterShl)
554 if (*InnerShiftConst == OuterShAmt)
564 if (InnerShiftConst->
ugt(OuterShAmt) && InnerShiftConst->
ult(TypeWidth)) {
567 IsInnerShl ? TypeWidth - InnerShAmt : InnerShAmt - OuterShAmt;
593 if (!
I)
return false;
597 if (!
I->hasOneUse())
return false;
599 switch (
I->getOpcode()) {
600 default:
return false;
601 case Instruction::And:
602 case Instruction::Or:
603 case Instruction::Xor:
608 case Instruction::Shl:
609 case Instruction::LShr:
612 case Instruction::Select: {
614 Value *TrueVal = SI->getTrueValue();
615 Value *FalseVal = SI->getFalseValue();
619 case Instruction::PHI: {
629 case Instruction::Mul: {
630 const APInt *MulConst;
632 return !IsLeftShift &&
match(
I->getOperand(1),
m_APInt(MulConst)) &&
643 bool IsInnerShl = InnerShift->
getOpcode() == Instruction::Shl;
653 auto NewInnerShift = [&](
unsigned ShAmt) {
654 InnerShift->
setOperand(1, ConstantInt::get(ShType, ShAmt));
667 if (IsInnerShl == IsOuterShl) {
669 if (InnerShAmt + OuterShAmt >= TypeWidth)
672 return NewInnerShift(InnerShAmt + OuterShAmt);
678 if (InnerShAmt == OuterShAmt) {
679 APInt Mask = IsInnerShl
683 ConstantInt::get(ShType, Mask));
684 if (
auto *AndI = dyn_cast<Instruction>(
And)) {
685 AndI->moveBefore(InnerShift);
691 assert(InnerShAmt > OuterShAmt &&
692 "Unexpected opposite direction logical shift pair");
698 return NewInnerShift(InnerShAmt - OuterShAmt);
706 if (
Constant *
C = dyn_cast<Constant>(V)) {
716 switch (
I->getOpcode()) {
718 case Instruction::And:
719 case Instruction::Or:
720 case Instruction::Xor:
728 case Instruction::Shl:
729 case Instruction::LShr:
733 case Instruction::Select:
739 case Instruction::PHI: {
746 isLeftShift, IC,
DL));
749 case Instruction::Mul: {
750 assert(!isLeftShift &&
"Unexpected shift direction!");
753 unsigned TypeWidth =
I->getType()->getScalarSizeInBits();
755 auto *
And = BinaryOperator::CreateAnd(Neg,
756 ConstantInt::get(
I->getType(), Mask));
770 case Instruction::Add:
771 return Shift.
getOpcode() == Instruction::Shl;
772 case Instruction::Or:
773 case Instruction::And:
775 case Instruction::Xor:
788 bool IsLeftShift =
I.getOpcode() == Instruction::Shl;
794 R->setHasNoUnsignedWrap(
I.hasNoUnsignedWrap() &&
798 R->setIsExact(
I.isExact() && BO0->
isExact());
802 Type *Ty =
I.getType();
811 Constant *NegDivC = ConstantInt::get(Ty, -(*DivC));
815 auto ExtOpcode = (
I.getOpcode() == Instruction::AShr) ? Instruction::SExt
825 "Shift over the type width should have been removed already");
829 if (
I.getOpcode() != Instruction::AShr &&
832 dbgs() <<
"ICE: GetShiftedValue propagating shift through expression"
833 " to eliminate shift:\n IN: "
834 << *Op0 <<
"\n SH: " <<
I <<
"\n");
846 if (
auto *Op0BO = dyn_cast<BinaryOperator>(Op0)) {
878 if (!isa<Constant>(FalseVal) && TBO->
getOperand(0) == FalseVal &&
895 if (!isa<Constant>(TrueVal) && FBO->
getOperand(0) == TrueVal &&
922 assert(
I.getOpcode() == Instruction::LShr);
925 Value *ShiftAmt =
I.getOperand(1);
926 Type *Ty =
I.getType();
931 const APInt *ShAmtAPInt =
nullptr;
932 Value *
X =
nullptr, *
Y =
nullptr;
943 if (
X->getType()->getScalarSizeInBits() != ShAmt ||
944 Y->getType()->getScalarSizeInBits() != ShAmt)
948 if (!
Add->hasOneUse()) {
953 TruncInst *Trunc = dyn_cast<TruncInst>(U);
971 if (!
Add->hasOneUse()) {
982 assert(
I.isShift() &&
"Expected a shift as input");
984 if (
I.getOpcode() == Instruction::Shl) {
985 if (
I.hasNoUnsignedWrap() &&
I.hasNoSignedWrap())
1006 bool Changed =
false;
1008 if (
I.getOpcode() == Instruction::Shl) {
1011 I.setHasNoUnsignedWrap();
1015 if (!
I.hasNoSignedWrap()) {
1019 I.setHasNoSignedWrap();
1029 I.setIsExact(Changed);
1038 I.hasNoSignedWrap(),
I.hasNoUnsignedWrap(), Q))
1050 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
1051 Type *Ty =
I.getType();
1056 unsigned ShAmtC =
C->getZExtValue();
1062 unsigned SrcWidth =
X->getType()->getScalarSizeInBits();
1063 if (ShAmtC < SrcWidth &&
1071 return BinaryOperator::CreateAnd(
X, ConstantInt::get(Ty, Mask));
1078 if (ShrAmt < ShAmtC) {
1080 Constant *ShiftDiff = ConstantInt::get(Ty, ShAmtC - ShrAmt);
1081 auto *NewShl = BinaryOperator::CreateShl(
X, ShiftDiff);
1082 NewShl->setHasNoUnsignedWrap(
1083 I.hasNoUnsignedWrap() ||
1085 cast<Instruction>(Op0)->getOpcode() == Instruction::LShr &&
1086 I.hasNoSignedWrap()));
1087 NewShl->setHasNoSignedWrap(
I.hasNoSignedWrap());
1090 if (ShrAmt > ShAmtC) {
1092 Constant *ShiftDiff = ConstantInt::get(Ty, ShrAmt - ShAmtC);
1094 cast<BinaryOperator>(Op0)->
getOpcode(),
X, ShiftDiff);
1095 NewShr->setIsExact(
true);
1103 if (ShrAmt < ShAmtC) {
1105 Constant *ShiftDiff = ConstantInt::get(Ty, ShAmtC - ShrAmt);
1106 auto *NewShl = BinaryOperator::CreateShl(
X, ShiftDiff);
1107 NewShl->setHasNoUnsignedWrap(
1108 I.hasNoUnsignedWrap() ||
1110 cast<Instruction>(Op0)->getOpcode() == Instruction::LShr &&
1111 I.hasNoSignedWrap()));
1112 NewShl->setHasNoSignedWrap(
I.hasNoSignedWrap());
1115 return BinaryOperator::CreateAnd(NewShl, ConstantInt::get(Ty, Mask));
1117 if (ShrAmt > ShAmtC) {
1119 Constant *ShiftDiff = ConstantInt::get(Ty, ShrAmt - ShAmtC);
1120 auto *OldShr = cast<BinaryOperator>(Op0);
1123 NewShr->setIsExact(OldShr->isExact());
1126 return BinaryOperator::CreateAnd(NewShr, ConstantInt::get(Ty, Mask));
1136 unsigned ShDiff = ShrAmtC > ShAmtC ? ShrAmtC - ShAmtC : ShAmtC - ShrAmtC;
1137 Constant *ShiftDiffC = ConstantInt::get(
X->getType(), ShDiff);
1138 auto ShiftOpc = ShrAmtC > ShAmtC ? Shr->
getOpcode() : Instruction::Shl;
1147 return BinaryOperator::CreateAnd(Trunc, ConstantInt::get(Ty, Mask));
1153 switch (BinOpcode) {
1156 case Instruction::Add:
1157 case Instruction::And:
1158 case Instruction::Or:
1159 case Instruction::Xor:
1160 case Instruction::Sub:
1168 isSuitableBinOpcode(Op0BO->
getOpcode())) {
1189 unsigned Op1Val =
C->getLimitedValue(
BitWidth);
1191 Constant *Mask = ConstantInt::get(Ty, Bits);
1192 return BinaryOperator::CreateAnd(
B, Mask);
1203 X->getName() +
".mask");
1205 if (
auto *Disjoint = dyn_cast<PossiblyDisjointInst>(Op0BO);
1206 Disjoint && Disjoint->isDisjoint())
1207 cast<PossiblyDisjointInst>(NewOp)->setIsDisjoint(
true);
1216 return BinaryOperator::CreateSub(NewLHS, NewShift);
1229 return BinaryOperator::CreateAnd(Mask,
X);
1235 return BinaryOperator::CreateShl(
AllOnes, Op1);
1256 return BinaryOperator::CreateLShr(
1264 return BinaryOperator::CreateAnd(NegX,
X);
1282 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
1283 Type *Ty =
I.getType();
1299 auto *NewSub = BinaryOperator::CreateNUWSub(
X, NewLshr);
1300 NewSub->setHasNoSignedWrap(
1309 return BinaryOperator::CreateAnd(
X,
Y);
1316 auto *NewSub = BinaryOperator::CreateNUWSub(NewLshr,
Y);
1317 NewSub->setHasNoSignedWrap(
1323 switch (BinOpcode) {
1326 case Instruction::Add:
1327 case Instruction::And:
1328 case Instruction::Or:
1329 case Instruction::Xor:
1340 if (isSuitableBinOpcode(Op0OB->
getOpcode())) {
1341 if (
auto *OBO = dyn_cast<OverflowingBinaryOperator>(Op0);
1342 !OBO || OBO->hasNoUnsignedWrap()) {
1344 Y, Op1,
"",
I.isExact() && Op0OB->
getOpcode() != Instruction::And);
1347 NewBinOp->setHasNoUnsignedWrap(
true);
1348 NewBinOp->setHasNoSignedWrap(OBO->hasNoSignedWrap());
1349 }
else if (
auto *Disjoint = dyn_cast<PossiblyDisjointInst>(Op0)) {
1350 cast<PossiblyDisjointInst>(NewBinOp)->setIsDisjoint(
1351 Disjoint->isDisjoint());
1359 unsigned ShAmtC =
C->getZExtValue();
1360 auto *
II = dyn_cast<IntrinsicInst>(Op0);
1362 (
II->getIntrinsicID() == Intrinsic::ctlz ||
1363 II->getIntrinsicID() == Intrinsic::cttz ||
1364 II->getIntrinsicID() == Intrinsic::ctpop)) {
1368 bool IsPop =
II->getIntrinsicID() == Intrinsic::ctpop;
1376 if (C1->
ult(ShAmtC)) {
1378 Constant *ShiftDiff = ConstantInt::get(Ty, ShAmtC - ShlAmtC);
1381 auto *NewLShr = BinaryOperator::CreateLShr(
X, ShiftDiff);
1382 NewLShr->setIsExact(
I.isExact());
1389 return BinaryOperator::CreateAnd(NewLShr, ConstantInt::get(Ty, Mask));
1391 }
else if (C1->
ugt(ShAmtC)) {
1393 Constant *ShiftDiff = ConstantInt::get(Ty, ShlAmtC - ShAmtC);
1396 auto *NewShl = BinaryOperator::CreateShl(
X, ShiftDiff);
1397 NewShl->setHasNoUnsignedWrap(
true);
1398 NewShl->setHasNoSignedWrap(ShAmtC > 0);
1405 return BinaryOperator::CreateAnd(NewShl, ConstantInt::get(Ty, Mask));
1411 return BinaryOperator::CreateAnd(
X, ConstantInt::get(Ty, Mask));
1423 unsigned Op1Val =
C->getLimitedValue(
BitWidth);
1425 Constant *Mask = ConstantInt::get(Ty, Bits);
1426 return BinaryOperator::CreateAnd(NewAdd, Mask);
1430 (!Ty->
isIntegerTy() || shouldChangeType(Ty,
X->getType()))) {
1432 "Big shift not simplified to zero?");
1439 unsigned SrcTyBitWidth =
X->getType()->getScalarSizeInBits();
1441 if (SrcTyBitWidth == 1) {
1442 auto *NewC = ConstantInt::get(
1447 if ((!Ty->
isIntegerTy() || shouldChangeType(Ty,
X->getType())) &&
1457 if (ShAmtC ==
BitWidth - SrcTyBitWidth) {
1459 unsigned NewShAmt = std::min(ShAmtC, SrcTyBitWidth - 1);
1479 return BinaryOperator::CreateAnd(Signbit,
X);
1486 unsigned SrcWidth =
X->getType()->getScalarSizeInBits();
1494 if (AmtSum < SrcWidth &&
1502 return BinaryOperator::CreateAnd(Trunc, ConstantInt::get(Ty, MaskC));
1508 if (
BitWidth > 2 && (*MulC - 1).isPowerOf2() &&
1518 auto *NewAdd = BinaryOperator::CreateNUWAdd(
1521 NewAdd->setHasNoSignedWrap(
1534 if (MulC->
eq(NewMulC.
shl(ShAmtC))) {
1536 BinaryOperator::CreateNUWMul(
X, ConstantInt::get(Ty, NewMulC));
1538 "lshr X, 0 should be handled by simplifyLShrInst.");
1539 NewMul->setHasNoSignedWrap(
true);
1547 if (
BitWidth > 2 && (*MulC - 1).isPowerOf2() &&
1549 return BinaryOperator::CreateNSWAdd(
1560 unsigned SrcWidth =
X->getType()->getScalarSizeInBits();
1561 unsigned WidthDiff =
BitWidth - SrcWidth;
1562 if (SrcWidth % 16 == 0) {
1564 if (ShAmtC >= WidthDiff) {
1571 Constant *ShiftDiff = ConstantInt::get(Ty, WidthDiff - ShAmtC);
1572 return BinaryOperator::CreateShl(NewZExt, ShiftDiff);
1579 Value *BoolX, *BoolY;
1584 (
X->hasOneUse() ||
Y->hasOneUse() || Op0->
hasOneUse())) {
1598 return BinaryOperator::CreateAnd(Mask,
X);
1604 return BinaryOperator::CreateLShr(
AllOnes, Op1);
1617 "Must be called with arithmetic right-shift instruction only.");
1623 APInt(
C->getType()->getScalarSizeInBits(),
1624 V->getType()->getScalarSizeInBits())));
1632 if (!
match(&OldAShr,
1638 !BitWidthSplat(C1, &OldAShr) || !BitWidthSplat(C2, &OldAShr))
1644 bool HadTrunc = MaybeTrunc != HighBitExtract;
1647 Value *
X, *NumLowBitsToSkip;
1653 if (!
match(NumLowBitsToSkip,
1656 !BitWidthSplat(C0, HighBitExtract))
1693 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
1694 Type *Ty =
I.getType();
1696 const APInt *ShAmtAPInt;
1705 ShAmt ==
BitWidth -
X->getType()->getScalarSizeInBits())
1714 if (ShlAmt < ShAmt) {
1716 Constant *ShiftDiff = ConstantInt::get(Ty, ShAmt - ShlAmt);
1717 auto *NewAShr = BinaryOperator::CreateAShr(
X, ShiftDiff);
1718 NewAShr->setIsExact(
I.isExact());
1721 if (ShlAmt > ShAmt) {
1723 Constant *ShiftDiff = ConstantInt::get(Ty, ShlAmt - ShAmt);
1725 NewShl->setHasNoSignedWrap(
true);
1734 AmtSum = std::min(AmtSum,
BitWidth - 1);
1736 return BinaryOperator::CreateAShr(
X, ConstantInt::get(Ty, AmtSum));
1740 (Ty->
isVectorTy() || shouldChangeType(Ty,
X->getType()))) {
1742 Type *SrcTy =
X->getType();
1761 (
BitWidth > 2 && (*MulC - 1).isPowerOf2() &&
1766 auto *NewAdd = BinaryOperator::CreateNSWAdd(
1769 NewAdd->setHasNoUnsignedWrap(
1786 Constant *Mask = ConstantInt::get(Ty, 1);
1790 cast<Constant>(cast<Instruction>(Op0)->getOperand(1)));
1800 Instruction *Lshr = BinaryOperator::CreateLShr(Op0, Op1);
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
This file provides internal interfaces used to implement the InstCombine.
static Value * foldShiftedShift(BinaryOperator *InnerShift, unsigned OuterShAmt, bool IsOuterShl, InstCombiner::BuilderTy &Builder)
Fold OuterShift (InnerShift X, C1), C2.
static bool setShiftFlags(BinaryOperator &I, const SimplifyQuery &Q)
static Instruction * dropRedundantMaskingOfLeftShiftInput(BinaryOperator *OuterShift, const SimplifyQuery &Q, InstCombiner::BuilderTy &Builder)
static bool canEvaluateShifted(Value *V, unsigned NumBits, bool IsLeftShift, InstCombinerImpl &IC, Instruction *CxtI)
See if we can compute the specified value, but shifted logically to the left or right by some number ...
bool canTryToConstantAddTwoShiftAmounts(Value *Sh0, Value *ShAmt0, Value *Sh1, Value *ShAmt1)
static Instruction * foldShiftOfShiftedBinOp(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
If we have a shift-by-constant of a bin op (bitwise logic op or add/sub w/ shl) that itself has a shi...
static bool canEvaluateShiftedShift(unsigned OuterShAmt, bool IsOuterShl, Instruction *InnerShift, InstCombinerImpl &IC, Instruction *CxtI)
Return true if we can simplify two logical (either left or right) shifts that have constant shift amo...
static Value * getShiftedValue(Value *V, unsigned NumBits, bool isLeftShift, InstCombinerImpl &IC, const DataLayout &DL)
When canEvaluateShifted() returns true for an expression, this function inserts the new computation t...
static bool canShiftBinOpWithConstantRHS(BinaryOperator &Shift, BinaryOperator *BO)
This file provides the interface for the instcombine pass implementation.
static bool hasNoSignedWrap(BinaryOperator &I)
static bool hasNoUnsignedWrap(BinaryOperator &I)
uint64_t IntrinsicInst * II
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static const MCExpr * MaskShift(const MCExpr *Val, uint32_t Mask, uint32_t Shift, MCContext &Ctx)
static SymbolRef::Type getType(const Symbol *Sym)
static std::optional< unsigned > getOpcode(ArrayRef< VPValue * > Values)
Returns the opcode of Values or ~0 if they do not all agree.
Class for arbitrary precision integers.
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
bool isNegatedPowerOf2() const
Check if this APInt's negated value is a power of two greater than zero.
static APInt getSignMask(unsigned BitWidth)
Get the SignMask for a specific bit width.
bool isMinSignedValue() const
Determine if this is the smallest signed value.
uint64_t getZExtValue() const
Get zero extended value.
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
bool ult(const APInt &RHS) const
Unsigned less than comparison.
bool isNegative() const
Determine sign of this APInt.
bool eq(const APInt &RHS) const
Equality comparison.
unsigned countr_zero() const
Count the number of trailing zero bits.
unsigned logBase2() const
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
APInt shl(unsigned shiftAmt) const
Left-shift function.
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)
Constructs an APInt value that has the top hiBitsSet bits set.
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
static BinaryOperator * CreateNeg(Value *Op, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Helper functions to construct and inspect unary operations (NEG and NOT) via binary operators SUB and...
BinaryOps getOpcode() const
static BinaryOperator * CreateNot(Value *Op, const Twine &Name="", InsertPosition InsertBefore=nullptr)
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), InsertPosition InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
static CastInst * CreateTruncOrBitCast(Value *S, Type *Ty, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Create a Trunc or BitCast cast instruction.
static CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass's ...
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_SLE
signed less or equal
@ ICMP_ULT
unsigned less than
@ ICMP_SGE
signed greater or equal
static Constant * getSub(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
static Constant * getNot(Constant *C)
static Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
static Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
static ConstantInt * getSigned(IntegerType *Ty, int64_t V)
Return a ConstantInt with the specified value for the specified type.
This is an important base class in LLVM.
static Constant * replaceUndefsWith(Constant *C, Constant *Replacement)
Try to replace undefined constant C or undefined elements in C with Replacement.
static Constant * mergeUndefsWith(Constant *C, Constant *Other)
Merges undefs of a Constant with another Constant, along with the undefs already present.
static Constant * getAllOnesValue(Type *Ty)
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
A parsed version of the target data layout string in and methods for querying it.
CallInst * CreateUnaryIntrinsic(Intrinsic::ID ID, Value *V, Instruction *FMFSource=nullptr, const Twine &Name="")
Create a call to intrinsic ID with 1 operand which is mangled on its type.
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
Value * CreateIsNotNeg(Value *Arg, const Twine &Name="")
Return a boolean value testing if Arg > -1.
Value * CreateNeg(Value *V, const Twine &Name="", bool HasNSW=false)
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
InstTy * Insert(InstTy *I, const Twine &Name="") const
Insert and return the specified instruction.
Value * CreateShl(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="", bool IsNonNeg=false)
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreateIsNotNull(Value *Arg, const Twine &Name="")
Return a boolean value testing if Arg != 0.
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Value * CreateICmpSLT(Value *LHS, Value *RHS, const Twine &Name="")
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Value * CreateAShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
Instruction * FoldOpIntoSelect(Instruction &Op, SelectInst *SI, bool FoldWithMultiUse=false)
Given an instruction with a select as one operand and a constant as the other operand,...
Instruction * visitLShr(BinaryOperator &I)
Instruction * foldBinOpIntoSelectOrPhi(BinaryOperator &I)
This is a convenience wrapper function for the above two functions.
Value * reassociateShiftAmtsOfTwoSameDirectionShifts(BinaryOperator *Sh0, const SimplifyQuery &SQ, bool AnalyzeForSignBitExtraction=false)
Instruction * visitAShr(BinaryOperator &I)
Instruction * eraseInstFromFunction(Instruction &I) override
Combiner aware instruction erasure.
Instruction * visitShl(BinaryOperator &I)
Instruction * foldBinopWithPhiOperands(BinaryOperator &BO)
For a binary operator with 2 phi operands, try to hoist the binary operation before the phi.
Instruction * foldVariableSignZeroExtensionOfVariableHighBitExtract(BinaryOperator &OldAShr)
Instruction * commonShiftTransforms(BinaryOperator &I)
bool SimplifyDemandedInstructionBits(Instruction &Inst)
Tries to simplify operands to an integer instruction based on its demanded bits.
Instruction * foldVectorBinop(BinaryOperator &Inst)
Canonicalize the position of binops relative to shufflevector.
Instruction * FoldShiftByConstant(Value *Op0, Constant *Op1, BinaryOperator &I)
Instruction * replaceInstUsesWith(Instruction &I, Value *V)
A combiner-aware RAUW-like routine.
Instruction * InsertNewInstWith(Instruction *New, BasicBlock::iterator Old)
Same as InsertNewInstBefore, but also sets the debug loc.
void addToWorklist(Instruction *I)
Instruction * replaceOperand(Instruction &I, unsigned OpNum, Value *V)
Replace operand of instruction and add old operand to the worklist.
void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth, const Instruction *CxtI) const
bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth=0, const Instruction *CxtI=nullptr) const
void setHasNoUnsignedWrap(bool b=true)
Set or clear the nuw flag on this instruction, which must be an operator which supports this flag.
bool hasNoUnsignedWrap() const LLVM_READONLY
Determine whether the no unsigned wrap flag is set.
bool hasNoSignedWrap() const LLVM_READONLY
Determine whether the no signed wrap flag is set.
void copyIRFlags(const Value *V, bool IncludeWrapFlags=true)
Convenience method to copy supported exact, fast-math, and (optionally) wrapping flags from V to this...
void setHasNoSignedWrap(bool b=true)
Set or clear the nsw flag on this instruction, which must be an operator which supports this flag.
bool isCommutative() const LLVM_READONLY
Return true if the instruction is commutative:
bool isExact() const LLVM_READONLY
Determine whether the exact flag is set.
bool isLogicalShift() const
Return true if this is a logical shift left or a logical shift right.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
void setIsExact(bool b=true)
Set or clear the exact flag on this instruction, which must be an operator which supports this flag.
op_range incoming_values()
void setIncomingValue(unsigned i, Value *V)
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
This class represents a sign extension of integer types.
This class represents the LLVM 'select' instruction.
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", InsertPosition InsertBefore=nullptr, Instruction *MDFrom=nullptr)
This class represents a truncation of integer types.
The instances of the Type class are immutable: once they are created, they are never changed.
bool isVectorTy() const
True if this is an instance of VectorType.
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
Type * getExtendedType() const
Given scalar/vector integer type, returns a type with elements twice as wide as in the original type.
bool isIntegerTy() const
True if this is an instance of IntegerType.
void setOperand(unsigned i, Value *Val)
Value * getOperand(unsigned i) const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
StringRef getName() const
Return a constant reference to the value's name.
void takeName(Value *V)
Transfer the name from V to this value.
This class represents zero extension of integer types.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
cst_pred_ty< is_all_ones > m_AllOnes()
Match an integer or vector with all bits set.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
cst_pred_ty< is_power2 > m_Power2()
Match an integer or vector power-of-2.
match_combine_or< CastInst_match< OpTy, TruncInst >, OpTy > m_TruncOrSelf(const OpTy &Op)
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
BinaryOp_match< LHS, RHS, Instruction::And, true > m_c_And(const LHS &L, const RHS &R)
Matches an And with LHS and RHS in either order.
CastInst_match< OpTy, TruncInst > m_Trunc(const OpTy &Op)
Matches Trunc.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Sub, OverflowingBinaryOperator::NoSignedWrap > m_NSWSub(const LHS &L, const RHS &R)
specific_intval< false > m_SpecificInt(const APInt &V)
Match a specific integer value or vector with all elements equal to the value.
match_combine_or< CastInst_match< OpTy, ZExtInst >, OpTy > m_ZExtOrSelf(const OpTy &Op)
bool match(Val *V, const Pattern &P)
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
BinOpPred_match< LHS, RHS, is_right_shift_op > m_Shr(const LHS &L, const RHS &R)
Matches logical shift operations.
specific_intval< true > m_SpecificIntAllowPoison(const APInt &V)
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
match_combine_and< LTy, RTy > m_CombineAnd(const LTy &L, const RTy &R)
Combine two pattern matchers matching L && R.
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
deferredval_ty< Value > m_Deferred(Value *const &V)
Like m_Specific(), but works if the specific value to match is determined as part of the same match()...
OneUse_match< T > m_OneUse(const T &SubPattern)
BinaryOp_match< cst_pred_ty< is_zero_int >, ValTy, Instruction::Sub > m_Neg(const ValTy &V)
Matches a 'Neg' as 'sub 0, V'.
match_combine_and< class_match< Constant >, match_unless< constantexpr_match > > m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Shl, OverflowingBinaryOperator::NoSignedWrap > m_NSWShl(const LHS &L, const RHS &R)
CastInst_match< OpTy, ZExtInst > m_ZExt(const OpTy &Op)
Matches ZExt.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Shl, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWShl(const LHS &L, const RHS &R)
OverflowingBinaryOp_match< LHS, RHS, Instruction::Mul, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWMul(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Add, true > m_c_Add(const LHS &L, const RHS &R)
Matches a Add with LHS and RHS in either order.
BinaryOp_match< LHS, RHS, Instruction::SDiv > m_SDiv(const LHS &L, const RHS &R)
OverflowingBinaryOp_match< LHS, RHS, Instruction::Sub, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWSub(const LHS &L, const RHS &R)
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
AnyBinaryOp_match< LHS, RHS, true > m_c_BinOp(const LHS &L, const RHS &R)
Matches a BinaryOperator with LHS and RHS in either order.
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
Exact_match< T > m_Exact(const T &SubPattern)
BinOpPred_match< LHS, RHS, is_shift_op > m_Shift(const LHS &L, const RHS &R)
Matches shift operations.
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::SRem > m_SRem(const LHS &L, const RHS &R)
BinaryOp_match< cst_pred_ty< is_all_ones >, ValTy, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
CastInst_match< OpTy, SExtInst > m_SExt(const OpTy &Op)
Matches SExt.
BinaryOp_match< LHS, RHS, Instruction::Or, true > m_c_Or(const LHS &L, const RHS &R)
Matches an Or with LHS and RHS in either order.
match_combine_or< OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap >, DisjointOr_match< LHS, RHS > > m_NUWAddLike(const LHS &L, const RHS &R)
Match either "add nuw" or "or disjoint".
OverflowingBinaryOp_match< LHS, RHS, Instruction::Mul, OverflowingBinaryOperator::NoSignedWrap > m_NSWMul(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
cst_pred_ty< icmp_pred_with_threshold > m_SpecificInt_ICMP(ICmpInst::Predicate Predicate, const APInt &Threshold)
Match an integer or vector with every element comparing 'pred' (eg/ne/...) to Threshold.
This is an optimization pass for GlobalISel generic memory operations.
Value * simplifyAShrInst(Value *Op0, Value *Op1, bool IsExact, const SimplifyQuery &Q)
Given operands for a AShr, fold the result or return nulll.
Value * simplifySubInst(Value *LHS, Value *RHS, bool IsNSW, bool IsNUW, const SimplifyQuery &Q)
Given operands for a Sub, fold the result or return null.
Value * simplifyAddInst(Value *LHS, Value *RHS, bool IsNSW, bool IsNUW, const SimplifyQuery &Q)
Given operands for an Add, fold the result or return null.
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
Value * simplifyShlInst(Value *Op0, Value *Op1, bool IsNSW, bool IsNUW, const SimplifyQuery &Q)
Given operands for a Shl, fold the result or return null.
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Value * simplifyLShrInst(Value *Op0, Value *Op1, bool IsExact, const SimplifyQuery &Q)
Given operands for a LShr, fold the result or return null.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Constant * ConstantFoldCastOperand(unsigned Opcode, Constant *C, Type *DestTy, const DataLayout &DL)
Attempt to constant fold a cast with the specified operand.
Constant * ConstantFoldBinaryOpOperands(unsigned Opcode, Constant *LHS, Constant *RHS, const DataLayout &DL)
Attempt to constant fold a binary operation with the specified operands.
@ And
Bitwise or logical AND of integers.
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
constexpr unsigned BitWidth
unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return the number of times the sign bit of the register is replicated into the other bits.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
unsigned countMinSignBits() const
Returns the number of times the sign bit is replicated into the other bits.
unsigned countMinTrailingZeros() const
Returns the minimum number of trailing zero bits.
unsigned getBitWidth() const
Get the bit width of this value.
unsigned countMinLeadingZeros() const
Returns the minimum number of leading zero bits.
APInt getMaxValue() const
Return the maximal unsigned value possible given these KnownBits.
SimplifyQuery getWithInstruction(const Instruction *I) const