18#ifndef LLVM_TRANSFORMS_INSTCOMBINE_INSTCOMBINER_H
19#define LLVM_TRANSFORMS_INSTCOMBINE_INSTCOMBINER_H
30#define DEBUG_TYPE "instcombine"
37class OptimizationRemarkEmitter;
38class ProfileSummaryInfo;
39class TargetLibraryInfo;
40class TargetTransformInfo;
84 bool MadeIRChange =
false;
97 MinimizeSize(MinimizeSize), AA(AA), AC(AC), TLI(TLI), DT(DT),
DL(
DL),
98 SQ(
DL, &TLI, &DT, &AC), ORE(ORE), BFI(BFI), PSI(PSI), LI(LI) {}
106 if (
auto *BitCast = dyn_cast<BitCastInst>(V))
107 if (!OneUseOnly || BitCast->hasOneUse())
108 return BitCast->getOperand(0);
132 if (isa<Instruction>(V)) {
133 if (isa<CastInst>(V) ||
match(V, m_Neg(PatternMatch::m_Value())) ||
134 match(V, m_Not(PatternMatch::m_Value())) ||
139 if (isa<Argument>(V))
141 return isa<Constant>(V) ? (isa<UndefValue>(V) ? 0 : 1) : 2;
151 case CmpInst::ICMP_NE:
152 case CmpInst::ICMP_ULE:
153 case CmpInst::ICMP_SLE:
154 case CmpInst::ICMP_UGE:
155 case CmpInst::ICMP_SGE:
157 case CmpInst::FCMP_ONE:
158 case CmpInst::FCMP_OLE:
159 case CmpInst::FCMP_OGE:
170 bool &TrueIfSigned) {
172 case ICmpInst::ICMP_SLT:
175 case ICmpInst::ICMP_SLE:
177 return RHS.isAllOnes();
178 case ICmpInst::ICMP_SGT:
179 TrueIfSigned =
false;
180 return RHS.isAllOnes();
181 case ICmpInst::ICMP_SGE:
182 TrueIfSigned =
false;
184 case ICmpInst::ICMP_UGT:
187 return RHS.isMaxSignedValue();
188 case ICmpInst::ICMP_UGE:
191 return RHS.isMinSignedValue();
192 case ICmpInst::ICMP_ULT:
194 TrueIfSigned =
false;
195 return RHS.isMinSignedValue();
196 case ICmpInst::ICMP_ULE:
198 TrueIfSigned =
false;
199 return RHS.isMaxSignedValue();
207 return ConstantExpr::getAdd(
C, ConstantInt::get(
C->getType(), 1));
212 return ConstantExpr::getSub(
C, ConstantInt::get(
C->getType(), 1));
215 std::optional<std::pair<
227 return match(&
SI, PatternMatch::m_LogicalAnd(PatternMatch::m_Value(),
228 PatternMatch::m_Value())) ||
229 match(&
SI, PatternMatch::m_LogicalOr(PatternMatch::m_Value(),
230 PatternMatch::m_Value()));
241 if (
match(V, m_Not(PatternMatch::m_Value())))
245 if (
match(V, PatternMatch::m_AnyIntegralConstant()))
251 return WillInvertAllUses;
255 if (
match(V,
m_Add(PatternMatch::m_Value(), PatternMatch::m_ImmConstant())))
256 return WillInvertAllUses;
260 if (
match(V,
m_Sub(PatternMatch::m_ImmConstant(), PatternMatch::m_Value())))
261 return WillInvertAllUses;
265 m_Select(PatternMatch::m_Value(), m_Not(PatternMatch::m_Value()),
266 m_Not(PatternMatch::m_Value()))))
267 return WillInvertAllUses;
272 m_Not(PatternMatch::m_Value()))))
273 return WillInvertAllUses;
285 for (
Use &U : V->uses()) {
286 if (U.getUser() == IgnoredUser)
289 auto *
I = cast<Instruction>(U.getUser());
290 switch (
I->getOpcode()) {
291 case Instruction::Select:
292 if (U.getOperandNo() != 0)
294 if (shouldAvoidAbsorbingNotIntoSelect(*cast<SelectInst>(
I)))
297 case Instruction::Br:
298 assert(U.getOperandNo() == 0 &&
"Must be branching on that value.");
300 case Instruction::Xor:
302 if (!
match(
I, m_Not(PatternMatch::m_Value())))
320 bool IsRHSConstant) {
321 auto *InVTy = cast<FixedVectorType>(In->getType());
323 Type *EltTy = InVTy->getElementType();
324 auto *SafeC = ConstantExpr::getBinOpIdentity(Opcode, EltTy, IsRHSConstant);
330 case Instruction::SRem:
331 case Instruction::URem:
332 SafeC = ConstantInt::get(EltTy, 1);
334 case Instruction::FRem:
335 SafeC = ConstantFP::get(EltTy, 1.0);
339 "Only rem opcodes have no identity constant for RHS");
343 case Instruction::Shl:
344 case Instruction::LShr:
345 case Instruction::AShr:
346 case Instruction::SDiv:
347 case Instruction::UDiv:
348 case Instruction::SRem:
349 case Instruction::URem:
350 case Instruction::Sub:
351 case Instruction::FSub:
352 case Instruction::FDiv:
353 case Instruction::FRem:
354 SafeC = Constant::getNullValue(EltTy);
361 assert(SafeC &&
"Must have safe constant for binop");
362 unsigned NumElts = InVTy->getNumElements();
364 for (
unsigned i = 0; i != NumElts; ++i) {
365 Constant *
C = In->getAggregateElement(i);
366 Out[i] = isa<UndefValue>(
C) ? SafeC :
C;
368 return ConstantVector::get(Out);
386 std::optional<Instruction *> targetInstCombineIntrinsic(
IntrinsicInst &II);
387 std::optional<Value *>
390 bool &KnownBitsComputed);
391 std::optional<Value *> targetSimplifyDemandedVectorEltsIntrinsic(
402 assert(New && !New->getParent() &&
403 "New instruction already inserted into a basic block!");
404 New->insertBefore(Old);
411 New->setDebugLoc(Old->getDebugLoc());
412 return InsertNewInstBefore(New, Old);
424 if (
I.use_empty())
return nullptr;
431 V = PoisonValue::get(
I.getType());
434 <<
" with " << *V <<
'\n');
437 if (V->use_empty() && isa<Instruction>(V) && !V->hasName() &&
I.hasName())
440 I.replaceAllUsesWith(V);
446 Value *OldOp =
I.getOperand(OpNum);
447 I.setOperand(OpNum, V);
532 unsigned Depth = 0) = 0;
536 bool AllowMultipleUsers =
false) = 0;
538 bool isValidAddrSpaceCast(
unsigned FromAS,
unsigned ToAS)
const;
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
#define LLVM_LIBRARY_VISIBILITY
StandardInstrumentations SI(Mod->getContext(), Debug, VerifyEach)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Class for arbitrary precision integers.
A cache of @llvm.assume calls within a function.
InstListType::iterator iterator
Instruction iterators...
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
This class is the base class for the comparison instructions.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
This is an important base class in LLVM.
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
The core instruction combiner logic.
OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
static bool canFreelyInvertAllUsersOf(Instruction *V, Value *IgnoredUser)
Given i1 V, can every user of V be freely adapted if V is changed to !V ? InstCombine's freelyInvertA...
const DataLayout & getDataLayout() const
static bool isCanonicalPredicate(CmpInst::Predicate Pred)
Predicate canonicalization reduces the number of patterns that need to be matched by other transforms...
virtual Instruction * eraseInstFromFunction(Instruction &I)=0
Combiner aware instruction erasure.
DominatorTree & getDominatorTree() const
virtual ~InstCombiner()=default
LoopInfo * getLoopInfo() const
static unsigned getComplexity(Value *V)
Assign a complexity or rank value to LLVM Values.
TargetLibraryInfo & getTargetLibraryInfo() const
BlockFrequencyInfo * getBlockFrequencyInfo() const
bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero=false, unsigned Depth=0, const Instruction *CxtI=nullptr)
Instruction * InsertNewInstBefore(Instruction *New, BasicBlock::iterator Old)
Inserts an instruction New before instruction Old.
OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Instruction * replaceInstUsesWith(Instruction &I, Value *V)
A combiner-aware RAUW-like routine.
static bool isFreeToInvert(Value *V, bool WillInvertAllUses)
Return true if the specified value is free to invert (apply ~ to).
static bool shouldAvoidAbsorbingNotIntoSelect(const SelectInst &SI)
OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
static Constant * SubOne(Constant *C)
Subtract one from a Constant.
virtual bool SimplifyDemandedBits(Instruction *I, unsigned OpNo, const APInt &DemandedMask, KnownBits &Known, unsigned Depth=0)=0
KnownBits computeKnownBits(const Value *V, unsigned Depth, const Instruction *CxtI) const
void replaceUse(Use &U, Value *NewValue)
Replace use and add the previously used value to the worklist.
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)
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
InstructionWorklist & Worklist
A worklist of the instructions that need to be simplified.
Instruction * InsertNewInstWith(Instruction *New, BasicBlock::iterator Old)
Same as InsertNewInstBefore, but also sets the debug loc.
unsigned ComputeNumSignBits(const Value *Op, unsigned Depth=0, const Instruction *CxtI=nullptr) const
OverflowResult computeOverflowForUnsignedAdd(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
virtual Value * SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, APInt &UndefElts, unsigned Depth=0, bool AllowMultipleUsers=false)=0
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...
void addToWorklist(Instruction *I)
Instruction * replaceOperand(Instruction &I, unsigned OpNum, Value *V)
Replace operand of instruction and add old operand to the worklist.
static Constant * getSafeVectorConstantForBinop(BinaryOperator::BinaryOps Opcode, Constant *In, bool IsRHSConstant)
Some binary operators require special handling to avoid poison and undefined behavior.
OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
ProfileSummaryInfo * getProfileSummaryInfo() const
OptimizationRemarkEmitter & getOptimizationRemarkEmitter() const
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.
SmallDenseSet< std::pair< BasicBlock *, BasicBlock * >, 8 > DeadEdges
Edges that are known to never be taken.
void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth, const Instruction *CxtI) const
AssumptionCache & getAssumptionCache() const
bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth=0, const Instruction *CxtI=nullptr) const
OptimizationRemarkEmitter & ORE
const SimplifyQuery & getSimplifyQuery() const
static Constant * AddOne(Constant *C)
Add one to a Constant.
unsigned ComputeMaxSignificantBits(const Value *Op, unsigned Depth=0, const Instruction *CxtI=nullptr) const
InstructionWorklist - This is the worklist management logic for InstCombine and other simplification ...
void pushUsersToWorkList(Instruction &I)
When an instruction is simplified, add all users of the instruction to the work lists because they mi...
void add(Instruction *I)
Add instruction to the worklist.
void push(Instruction *I)
Push the instruction onto the worklist stack.
void handleUseCountDecrement(Value *V)
Should be called after decrementing the use-count on V.
A wrapper class for inspecting calls to intrinsic functions.
Analysis providing profile information.
This class represents the LLVM 'select' instruction.
Implements a dense probed hash-table based set with some number of buckets stored inline.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Provides information about what library functions are available for the current target.
The instances of the Type class are immutable: once they are created, they are never changed.
A Use represents the edge between a Value definition and its users.
LLVM Value Representation.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
bool match(Val *V, const Pattern &P)
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
FNeg_match< OpTy > m_FNeg(const OpTy &X)
Match 'fneg X' as 'fsub -0.0, X'.
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)
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
This is an optimization pass for GlobalISel generic memory operations.
OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)
OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
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.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)
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...
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.
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.
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.
OverflowResult computeOverflowForUnsignedAdd(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)