21 #define DEBUG_TYPE "instcombine" 28 if (SimplifyDemandedInstructionBits(I))
32 if (isa<Constant>(Op0))
37 if (
Constant *CUI = dyn_cast<Constant>(Op1))
38 if (
Instruction *Res = FoldShiftByConstant(Op0, CUI, I))
75 const APInt *InnerShiftConst;
82 bool IsInnerShl = InnerShift->
getOpcode() == Instruction::Shl;
83 if (IsInnerShl == IsOuterShl)
89 if (*InnerShiftConst == OuterShAmt)
99 if (InnerShiftConst->ugt(OuterShAmt) && InnerShiftConst->ult(TypeWidth)) {
100 unsigned InnerShAmt = InnerShiftConst->getZExtValue();
102 IsInnerShl ? TypeWidth - InnerShAmt : InnerShAmt - OuterShAmt;
124 if (isa<Constant>(V))
128 if (!I)
return false;
143 uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits();
144 uint32_t BitWidth = Ty->getScalarSizeInBits();
148 return CanEvaluateTruncated(I->
getOperand(0), Ty);
160 default:
return false;
161 case Instruction::And:
162 case Instruction::Or:
163 case Instruction::Xor:
168 case Instruction::Shl:
169 case Instruction::LShr:
179 case Instruction::PHI: {
197 bool IsInnerShl = InnerShift->
getOpcode() == Instruction::Shl;
207 auto NewInnerShift = [&](
unsigned ShAmt) {
221 if (IsInnerShl == IsOuterShl) {
223 if (InnerShAmt + OuterShAmt >= TypeWidth)
226 return NewInnerShift(InnerShAmt + OuterShAmt);
232 if (InnerShAmt == OuterShAmt) {
238 if (
auto *AndI = dyn_cast<Instruction>(And)) {
239 AndI->moveBefore(InnerShift);
245 assert(InnerShAmt > OuterShAmt &&
246 "Unexpected opposite direction logical shift pair");
252 return NewInnerShift(InnerShAmt - OuterShAmt);
260 if (
Constant *
C = dyn_cast<Constant>(V)) {
266 if (
auto *
C = dyn_cast<Constant>(V))
278 case Instruction::And:
279 case Instruction::Or:
280 case Instruction::Xor:
288 case Instruction::Shl:
289 case Instruction::LShr:
299 case Instruction::PHI: {
306 isLeftShift, IC, DL));
318 bool HighBitSet =
false;
321 default: IsValid =
false;
break;
323 IsValid = Shift.
getOpcode() == Instruction::Shl;
325 case Instruction::Or:
326 case Instruction::Xor:
329 case Instruction::And:
340 if (IsValid && Shift.
getOpcode() == Instruction::AShr)
348 bool isLeftShift = I.
getOpcode() == Instruction::Shl;
356 if (I.
getOpcode() != Instruction::AShr &&
359 dbgs() <<
"ICE: GetShiftedValue propagating shift through expression" 360 " to eliminate shift:\n IN: " 361 << *Op0 <<
"\n SH: " << I <<
"\n");
363 return replaceInstUsesWith(
372 "Shift over the type width should have been removed already");
374 if (
Instruction *FoldedShift = foldBinOpIntoSelectOrPhi(I))
378 if (
TruncInst *TI = dyn_cast<TruncInst>(Op0)) {
398 unsigned DstSize = TI->getType()->getScalarSizeInBits();
413 Value *And = Builder.CreateAnd(NSh,
427 switch (Op0BO->getOpcode()) {
430 case Instruction::And:
431 case Instruction::Or:
432 case Instruction::Xor: {
435 if (isLeftShift && Op0BO->getOperand(1)->hasOneUse() &&
439 Builder.CreateShl(Op0BO->getOperand(0), Op1, Op0BO->
getName());
441 Value *
X = Builder.CreateBinOp(Op0BO->getOpcode(), YS, V1,
442 Op0BO->getOperand(1)->
getName());
449 return BinaryOperator::CreateAnd(X, Mask);
453 Value *Op0BOOp1 = Op0BO->getOperand(1);
454 if (isLeftShift && Op0BOOp1->
hasOneUse() &&
459 Builder.CreateShl(Op0BO->getOperand(0), Op1, Op0BO->
getName());
468 case Instruction::Sub: {
470 if (isLeftShift && Op0BO->getOperand(0)->hasOneUse() &&
474 Builder.CreateShl(Op0BO->getOperand(1), Op1, Op0BO->
getName());
476 Value *
X = Builder.CreateBinOp(Op0BO->getOpcode(), V1, YS,
477 Op0BO->getOperand(0)->
getName());
484 return BinaryOperator::CreateAnd(X, Mask);
488 if (isLeftShift && Op0BO->getOperand(0)->hasOneUse() &&
489 match(Op0BO->getOperand(0),
493 Builder.CreateShl(Op0BO->getOperand(1), Op1, Op0BO->
getName());
512 cast<Constant>(Op0BO->getOperand(1)), Op1);
515 Builder.CreateBinOp(I.
getOpcode(), Op0BO->getOperand(0), Op1);
526 if (isLeftShift && Op0BO->getOpcode() == Instruction::Sub &&
529 cast<Constant>(Op0BO->getOperand(0)), Op1);
531 Value *NewShift = Builder.CreateShl(Op0BO->getOperand(1), Op1);
534 return BinaryOperator::CreateSub(NewRHS, NewShift);
552 if (!isa<Constant>(FalseVal) && TBO->
getOperand(0) == FalseVal &&
559 Builder.CreateBinOp(I.
getOpcode(), FalseVal, Op1);
571 if (!isa<Constant>(TrueVal) && FBO->
getOperand(0) == TrueVal &&
578 Builder.CreateBinOp(I.
getOpcode(), TrueVal, Op1);
592 SQ.getWithInstruction(&I)))
593 return replaceInstUsesWith(I, V);
603 const APInt *ShAmtAPInt;
613 if (ShAmt < SrcWidth &&
615 return new ZExtInst(Builder.CreateShl(X, ShAmt), Ty);
629 if (ShrAmt < ShAmt) {
632 auto *NewShl = BinaryOperator::CreateShl(X, ShiftDiff);
637 if (ShrAmt > ShAmt) {
641 cast<BinaryOperator>(Op0)->
getOpcode(), X, ShiftDiff);
642 NewShr->setIsExact(
true);
650 if (AmtSum < BitWidth)
674 Value *
Mask = Builder.CreateShl(AllOnes, Op1);
675 return BinaryOperator::CreateAnd(Mask, X);
696 SQ.getWithInstruction(&I)))
697 return replaceInstUsesWith(I, V);
707 const APInt *ShAmtAPInt;
713 (II->getIntrinsicID() == Intrinsic::ctlz ||
714 II->getIntrinsicID() == Intrinsic::cttz ||
715 II->getIntrinsicID() == Intrinsic::ctpop)) {
721 Value *Cmp = Builder.CreateICmpEQ(II->getArgOperand(0), RHS);
728 if (ShOp1->
ult(ShAmt)) {
731 if (cast<BinaryOperator>(Op0)->hasNoUnsignedWrap()) {
733 auto *NewLShr = BinaryOperator::CreateLShr(X, ShiftDiff);
734 NewLShr->setIsExact(I.
isExact());
738 Value *NewLShr = Builder.CreateLShr(X, ShiftDiff,
"", I.
isExact());
742 if (ShOp1->
ugt(ShAmt)) {
745 if (cast<BinaryOperator>(Op0)->hasNoUnsignedWrap()) {
747 auto *NewShl = BinaryOperator::CreateShl(X, ShiftDiff);
748 NewShl->setHasNoUnsignedWrap(
true);
752 Value *NewShl = Builder.CreateShl(X, ShiftDiff);
765 "Big shift not simplified to zero?");
767 Value *NewLShr = Builder.CreateLShr(X, ShAmt);
775 if (ShAmt == BitWidth - 1) {
777 if (SrcTyBitWidth == 1)
782 Value *NewLShr = Builder.CreateLShr(X, SrcTyBitWidth - 1);
788 if (ShAmt == BitWidth - SrcTyBitWidth && Op0->
hasOneUse()) {
790 unsigned NewShAmt = std::min(ShAmt, SrcTyBitWidth - 1);
791 Value *AShr = Builder.CreateAShr(X, NewShAmt);
799 if (AmtSum < BitWidth)
816 Value *
Mask = Builder.CreateLShr(AllOnes, Op1);
817 return BinaryOperator::CreateAnd(Mask, X);
825 SQ.getWithInstruction(&I)))
826 return replaceInstUsesWith(I, V);
837 const APInt *ShAmtAPInt;
853 ShOp1->
ult(BitWidth)) {
855 if (ShlAmt < ShAmt) {
858 auto *NewAShr = BinaryOperator::CreateAShr(X, ShiftDiff);
859 NewAShr->setIsExact(I.
isExact());
862 if (ShlAmt > ShAmt) {
866 NewShl->setHasNoSignedWrap(
true);
872 ShOp1->
ult(BitWidth)) {
875 AmtSum = std::min(AmtSum, BitWidth - 1);
899 return BinaryOperator::CreateLShr(Op0, Op1);
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
BinOpPred_match< LHS, RHS, is_right_shift_op > m_Shr(const LHS &L, const RHS &R)
Matches logical shift operations.
A parsed version of the target data layout string in and methods for querying it. ...
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
uint64_t getZExtValue() const
Get zero extended value.
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
This class represents lattice values for constants.
BinaryOps getOpcode() const
BinaryOp_match< LHS, RHS, Instruction::SRem > m_SRem(const LHS &L, const RHS &R)
This class represents zero extension of integer types.
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
static bool canEvaluateShifted(Value *V, unsigned NumBits, bool IsLeftShift, InstCombiner &IC, Instruction *CxtI)
See if we can compute the specified value, but shifted logically to the left or right by some number ...
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Get a value with low bits set.
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
const Value * getTrueValue() const
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", Instruction *InsertBefore=nullptr, Instruction *MDFrom=nullptr)
LLVMContext & getContext() const
All values hold a context through their type.
void Add(Instruction *I)
Add - Add the specified instruction to the worklist if it isn't already in it.
This class represents a sign extension of integer types.
Value * SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, const SimplifyQuery &Q)
Given operands for a Shl, fold the result or return null.
bool isVectorTy() const
True if this is an instance of VectorType.
bool hasNoSignedWrap() const
Determine whether the no signed wrap flag is set.
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Value * SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact, const SimplifyQuery &Q)
Given operands for a LShr, fold the result or return null.
bool match(Val *V, const Pattern &P)
This class represents the LLVM 'select' instruction.
Instruction * commonShiftTransforms(BinaryOperator &I)
Exact_match< T > m_Exact(const T &SubPattern)
static Optional< unsigned > getOpcode(ArrayRef< VPValue *> Values)
Returns the opcode of Values or ~0 if they do not all agree.
bool isIntegerTy() const
True if this is an instance of IntegerType.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
The core instruction combiner logic.
bool MaskedValueIsZero(const Value *V, const APInt &Mask, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if 'V & Mask' is known to be zero.
void lshrInPlace(unsigned ShiftAmt)
Logical right-shift this APInt by ShiftAmt in place.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Constant * ConstantFoldConstant(const Constant *C, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldConstant - Attempt to fold the constant using the specified DataLayout.
static Constant * getZExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
void setIsExact(bool b=true)
Set or clear the exact flag on this instruction, which must be an operator which supports this flag...
Type * getType() const
All values are typed, get the type of this value.
CastClass_match< OpTy, Instruction::ZExt > m_ZExt(const OpTy &Op)
Matches ZExt.
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
const APInt & getValue() const
Return the constant as an APInt value reference.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
bool isKnownNonNegative(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Returns true if the give value is known to be non-negative.
cst_pred_ty< is_power2 > m_Power2()
Match an integer or vector power-of-2.
void takeName(Value *V)
Transfer the name from V to this value.
This class represents a truncation of integer types.
Value * getOperand(unsigned i) const
static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)
Get a value with high bits set.
OneUse_match< T > m_OneUse(const T &SubPattern)
bool isNegative() const
Determine sign of this APInt.
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...
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt...
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
The instances of the Type class are immutable: once they are created, they are never changed...
bool ult(const APInt &RHS) const
Unsigned less than comparison.
This is an important base class in LLVM.
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
static Constant * getAllOnesValue(Type *Ty)
Instruction * visitLShr(BinaryOperator &I)
static wasm::ValType getType(const TargetRegisterClass *RC)
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
bool isExact() const
Determine whether the exact flag is set.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
TargetLibraryInfo & getTargetLibraryInfo() const
InstCombineWorklist & Worklist
A worklist of the instructions that need to be simplified.
CastClass_match< OpTy, Instruction::SExt > m_SExt(const OpTy &Op)
Matches SExt.
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
static APInt getSignMask(unsigned BitWidth)
Get the SignMask for a specific bit width.
static Constant * getSplat(unsigned NumElts, Constant *Elt)
Return a ConstantVector with the specified constant in each element.
void setHasNoSignedWrap(bool b=true)
Set or clear the nsw flag on this instruction, which must be an operator which supports this flag...
uint64_t getLimitedValue(uint64_t Limit=~0ULL) const
getLimitedValue - If the value is smaller than the specified limit, return it, otherwise return the l...
This is the shared class of boolean and integer constants.
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type...
static bool canEvaluateShiftedShift(unsigned OuterShAmt, bool IsOuterShl, Instruction *InnerShift, InstCombiner &IC, Instruction *CxtI)
Return true if we can simplify two logical (either left or right) shifts that have constant shift amo...
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
static ConstantInt * getSigned(IntegerType *Ty, int64_t V)
Return a ConstantInt with the specified value for the specified type.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
void setOperand(unsigned i, Value *Val)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
Class to represent vector types.
Class for arbitrary precision integers.
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), Instruction *InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
Value * CreateShl(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
const Value * getFalseValue() const
static bool canShiftBinOpWithConstantRHS(BinaryOperator &Shift, BinaryOperator *BO, const APInt &C)
bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth=0, const Instruction *CxtI=nullptr) const
bool ugt(const APInt &RHS) const
Unsigned greather than comparison.
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...
StringRef getName() const
Return a constant reference to the value's name.
Value * SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact, const SimplifyQuery &Q)
Given operands for a AShr, fold the result or return nulll.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Shl, OverflowingBinaryOperator::NoSignedWrap > m_NSWShl(const LHS &L, const RHS &R)
static Value * getShiftedValue(Value *V, unsigned NumBits, bool isLeftShift, InstCombiner &IC, const DataLayout &DL)
When canEvaluateShifted() returns true for an expression, this function inserts the new computation t...
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
static Constant * getShl(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
bool isLogicalShift() const
Return true if this is a logical shift left or a logical shift right.
bool hasNoUnsignedWrap() const
Determine whether the no unsigned wrap flag is set.
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
void setHasNoUnsignedWrap(bool b=true)
Set or clear the nuw flag on this instruction, which must be an operator which supports this flag...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static Value * foldShiftedShift(BinaryOperator *InnerShift, unsigned OuterShAmt, bool IsOuterShl, InstCombiner::BuilderTy &Builder)
Fold OuterShift (InnerShift X, C1), C2.
LLVM Value Representation.
This file provides internal interfaces used to implement the InstCombine.
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
std::underlying_type< E >::type Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
bool hasOneUse() const
Return true if there is exactly one user of this value.
Instruction * visitAShr(BinaryOperator &I)
void setIncomingValue(unsigned i, Value *V)
Instruction * visitShl(BinaryOperator &I)
static BinaryOperator * CreateMul(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
op_range incoming_values()
Instruction * FoldShiftByConstant(Value *Op0, Constant *Op1, BinaryOperator &I)
A wrapper class for inspecting calls to intrinsic functions.
static Constant * get(unsigned Opcode, Constant *C1, unsigned Flags=0, Type *OnlyIfReducedTy=nullptr)
get - Return a unary operator constant expression, folding if possible.