Go to the documentation of this file.
18 #ifndef LLVM_TRANSFORMS_INSTCOMBINE_INSTCOMBINER_H
19 #define LLVM_TRANSFORMS_INSTCOMBINE_INSTCOMBINER_H
30 #define DEBUG_TYPE "instcombine"
36 class AssumptionCache;
37 class ProfileSummaryInfo;
38 class TargetLibraryInfo;
39 class TargetTransformInfo;
83 bool MadeIRChange =
false;
93 MinimizeSize(MinimizeSize),
AA(
AA), AC(AC), TLI(TLI), DT(DT),
DL(
DL),
94 SQ(
DL, &TLI, &DT, &AC), ORE(ORE),
BFI(
BFI), PSI(PSI), LI(LI) {}
102 if (
auto *BitCast = dyn_cast<BitCastInst>(V))
103 if (!OneUseOnly || BitCast->hasOneUse())
104 return BitCast->getOperand(0);
128 if (isa<Instruction>(V)) {
135 if (isa<Argument>(V))
137 return isa<Constant>(V) ? (isa<UndefValue>(V) ? 0 : 1) : 2;
166 bool &TrueIfSigned) {
173 return RHS.isAllOnes();
175 TrueIfSigned =
false;
176 return RHS.isAllOnes();
178 TrueIfSigned =
false;
183 return RHS.isMaxSignedValue();
187 return RHS.isMinSignedValue();
190 TrueIfSigned =
false;
191 return RHS.isMinSignedValue();
194 TrueIfSigned =
false;
195 return RHS.isMaxSignedValue();
247 return WillInvertAllUses;
252 return WillInvertAllUses;
257 return WillInvertAllUses;
263 return WillInvertAllUses;
269 return WillInvertAllUses;
281 if (U.getUser() == IgnoredUser)
284 auto *
I = cast<Instruction>(U.getUser());
285 switch (
I->getOpcode()) {
287 if (U.getOperandNo() != 0)
289 if (shouldAvoidAbsorbingNotIntoSelect(*cast<SelectInst>(
I)))
292 case Instruction::Br:
293 assert(U.getOperandNo() == 0 &&
"Must be branching on that value.");
295 case Instruction::Xor:
315 bool IsRHSConstant) {
316 auto *InVTy = cast<FixedVectorType>(
In->getType());
318 Type *EltTy = InVTy->getElementType();
325 case Instruction::SRem:
326 case Instruction::URem:
329 case Instruction::FRem:
334 "Only rem opcodes have no identity constant for RHS");
338 case Instruction::Shl:
339 case Instruction::LShr:
340 case Instruction::AShr:
341 case Instruction::SDiv:
342 case Instruction::UDiv:
343 case Instruction::SRem:
344 case Instruction::URem:
345 case Instruction::Sub:
346 case Instruction::FSub:
347 case Instruction::FDiv:
348 case Instruction::FRem:
356 assert(SafeC &&
"Must have safe constant for binop");
357 unsigned NumElts = InVTy->getNumElements();
359 for (
unsigned i = 0;
i != NumElts; ++
i) {
361 Out[
i] = isa<UndefValue>(
C) ? SafeC :
C;
385 bool &KnownBitsComputed);
397 assert(New && !New->getParent() &&
398 "New instruction already inserted into a basic block!");
408 return InsertNewInstBefore(New, Old);
431 <<
" with " << *V <<
'\n');
433 I.replaceAllUsesWith(V);
440 I.setOperand(OpNum, V);
521 virtual bool SimplifyDemandedBits(
Instruction *
I,
unsigned OpNo,
523 unsigned Depth = 0) = 0;
525 SimplifyDemandedVectorElts(
Value *V,
APInt DemandedElts,
APInt &UndefElts,
527 bool AllowMultipleUsers =
false) = 0;
static bool shouldAvoidAbsorbingNotIntoSelect(const SelectInst &SI)
TargetLibraryInfo & getTargetLibraryInfo() const
This is an optimization pass for GlobalISel generic memory operations.
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.
A parsed version of the target data layout string in and methods for querying it.
static bool isFreeToInvert(Value *V, bool WillInvertAllUses)
Return true if the specified value is free to invert (apply ~ to).
void addValue(Value *V)
Add value to the worklist if it is an instruction.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
DominatorTree & getDominatorTree() const
OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
unsigned ComputeNumSignBits(const Value *Op, unsigned Depth=0, const Instruction *CxtI=nullptr) const
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
BlockFrequencyInfo * getBlockFrequencyInfo() const
@ FCMP_ONE
0 1 1 0 True if ordered and operands are unequal
OverflowResult computeOverflowForUnsignedAdd(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth, const Instruction *CxtI) const
unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Get the upper bound on bit size for this Value Op as a signed integer.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
@ ICMP_SGT
signed greater than
The instances of the Type class are immutable: once they are created, they are never changed.
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 addToWorklist(Instruction *I)
OverflowResult computeOverflowForUnsignedAdd(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
@ ICMP_SLE
signed less or equal
LLVM Basic Block Representation.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
static Constant * getSub(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
static Constant * getBinOpIdentity(unsigned Opcode, Type *Ty, bool AllowRHSConstant=false, bool NSZ=false)
Return the identity constant for a binary opcode.
Instruction * replaceOperand(Instruction &I, unsigned OpNum, Value *V)
Replace operand of instruction and add old operand to the worklist.
OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
unsigned ComputeMaxSignificantBits(const Value *Op, unsigned Depth=0, const Instruction *CxtI=nullptr) const
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
bool match(Val *V, const Pattern &P)
(vector float) vec_cmpeq(*A, *B) C
@ ICMP_ULE
unsigned less or equal
bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero=false, unsigned Depth=0, const Instruction *CxtI=nullptr)
iterator_range< use_iterator > uses()
void replaceUse(Use &U, Value *NewValue)
Replace use and add the previously used value to the worklist.
KnownBits computeKnownBits(const Value *V, unsigned Depth, const Instruction *CxtI) const
match_combine_or< match_combine_or< MaxMin_match< ICmpInst, LHS, RHS, smax_pred_ty >, MaxMin_match< ICmpInst, LHS, RHS, smin_pred_ty > >, match_combine_or< MaxMin_match< ICmpInst, LHS, RHS, umax_pred_ty >, MaxMin_match< ICmpInst, LHS, RHS, umin_pred_ty > > > m_MaxOrMin(const LHS &L, const RHS &R)
FNeg_match< OpTy > m_FNeg(const OpTy &X)
Match 'fneg X' as 'fsub -0.0, X'.
OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
OptimizationRemarkEmitter & ORE
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
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 unsigned getComplexity(Value *V)
Assign a complexity or rank value to LLVM Values.
static Constant * SubOne(Constant *C)
Subtract one from a Constant.
Analysis providing profile information.
This class is the base class for the comparison instructions.
static Constant * getSafeVectorConstantForBinop(BinaryOperator::BinaryOps Opcode, Constant *In, bool IsRHSConstant)
Some binary operators require special handling to avoid poison and undefined behavior.
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
This is an important base class in LLVM.
match_combine_and< class_match< Constant >, match_unless< class_match< ConstantExpr > > > m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
AssumptionCache & getAssumptionCache() const
static Constant * AddOne(Constant *C)
Add one to a Constant.
const DataLayout & getDataLayout() const
LogicalOp_match< LHS, RHS, Instruction::Or > m_LogicalOr(const LHS &L, const RHS &R)
Matches L || R either in the form of L | R or L ? true : R.
void push(Instruction *I)
Push the instruction onto the worklist stack.
static bool isCanonicalPredicate(CmpInst::Predicate Pred)
Predicate canonicalization reduces the number of patterns that need to be matched by other transforms...
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)
static bool canFreelyInvertAllUsersOf(Value *V, Value *IgnoredUser)
Given i1 V, can every user of V be freely adapted if V is changed to !V ? InstCombine's freelyInvertA...
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, OptimizationRemarkEmitter *ORE=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
StandardInstrumentations SI(Debug, VerifyEach)
@ FCMP_OGE
0 0 1 1 True if ordered and greater than or equal
InstCombiner(InstructionWorklist &Worklist, BuilderTy &Builder, bool MinimizeSize, AAResults *AA, AssumptionCache &AC, TargetLibraryInfo &TLI, TargetTransformInfo &TTI, DominatorTree &DT, OptimizationRemarkEmitter &ORE, BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, const DataLayout &DL, LoopInfo *LI)
@ ICMP_UGE
unsigned greater or equal
This class represents the LLVM 'select' instruction.
print Print MemDeps of function
Instruction * InsertNewInstBefore(Instruction *New, Instruction &Old)
Inserts an instruction New before instruction Old.
InstructionWorklist & Worklist
A worklist of the instructions that need to be simplified.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Class for arbitrary precision integers.
@ ICMP_SLT
signed less than
A cache of @llvm.assume calls within a function.
@ ICMP_ULT
unsigned less than
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth=0, const Instruction *CxtI=nullptr) const
self_iterator getIterator()
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
#define LLVM_LIBRARY_VISIBILITY
LLVM_LIBRARY_VISIBILITY - If a class marked with this attribute is linked into a shared library,...
Instruction * InsertNewInstWith(Instruction *New, Instruction &Old)
Same as InsertNewInstBefore, but also sets the debug loc.
static Constant * get(ArrayRef< Constant * > V)
Instruction * replaceInstUsesWith(Instruction &I, Value *V)
A combiner-aware RAUW-like routine.
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
static Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
static Constant * get(Type *Ty, double V)
This returns a ConstantFP, or a vector containing a splat of a ConstantFP, for the specified value in...
Provides information about what library functions are available for the current target.
InstructionWorklist - This is the worklist management logic for InstCombine and other simplification ...
@ ICMP_SGE
signed greater or equal
OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
The core instruction combiner logic.
A wrapper class for inspecting calls to intrinsic functions.
LoopInfo * getLoopInfo() const
cst_pred_ty< is_any_apint > m_AnyIntegralConstant()
Match an integer or vector with any integral constant.
OptimizationRemarkEmitter & getOptimizationRemarkEmitter() const
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
@ ICMP_UGT
unsigned greater than
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
const SimplifyQuery & getSimplifyQuery() const
const BasicBlock * getParent() const
BinaryOp_match< SpecificConstantMatch, SrcTy, TargetOpcode::G_SUB > m_Neg(const SrcTy &&Src)
Matches a register negated by a G_SUB.
@ FCMP_OLE
0 1 0 1 True if ordered and less than or equal
void pushUsersToWorkList(Instruction &I)
When an instruction is simplified, add all users of the instruction to the work lists because they mi...
static bool isSignBitCheck(ICmpInst::Predicate Pred, const APInt &RHS, bool &TrueIfSigned)
Given an exploded icmp instruction, return true if the comparison only checks the sign bit.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
BinaryOp_match< SrcTy, SpecificConstantMatch, TargetOpcode::G_XOR, true > m_Not(const SrcTy &&Src)
Matches a register not-ed by a G_XOR.
bool isKnownToBeAPowerOfTwo(const Value *V, const DataLayout &DL, bool OrZero=false, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if the given value is known to have exactly one bit set when defined.
static Value * peekThroughBitcast(Value *V, bool OneUseOnly=false)
Return the source operand of a potentially bitcasted value while optionally checking if it has one us...
ProfileSummaryInfo * getProfileSummaryInfo() const
LLVM Value Representation.
LogicalOp_match< LHS, RHS, Instruction::And > m_LogicalAnd(const LHS &L, const RHS &R)
Matches L && R either in the form of L & R or L ? R : false.
OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
A Use represents the edge between a Value definition and its users.