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;
99 :
TTI(
TTI), Builder(Builder), Worklist(Worklist),
100 MinimizeSize(MinimizeSize), AA(AA), AC(AC), TLI(TLI), DT(DT),
DL(
DL),
101 SQ(
DL, &TLI, &DT, &AC), ORE(ORE), BFI(BFI), PSI(PSI), LI(LI) {}
109 if (
auto *BitCast = dyn_cast<BitCastInst>(V))
110 if (!OneUseOnly || BitCast->hasOneUse())
111 return BitCast->getOperand(0);
135 if (isa<Instruction>(V)) {
136 if (isa<CastInst>(V) ||
match(V, m_Neg(PatternMatch::m_Value())) ||
137 match(V, m_Not(PatternMatch::m_Value())) ||
142 if (isa<Argument>(V))
144 return isa<Constant>(V) ? (isa<UndefValue>(V) ? 0 : 1) : 2;
154 case CmpInst::ICMP_NE:
155 case CmpInst::ICMP_ULE:
156 case CmpInst::ICMP_SLE:
157 case CmpInst::ICMP_UGE:
158 case CmpInst::ICMP_SGE:
160 case CmpInst::FCMP_ONE:
161 case CmpInst::FCMP_OLE:
162 case CmpInst::FCMP_OGE:
173 bool &TrueIfSigned) {
175 case ICmpInst::ICMP_SLT:
178 case ICmpInst::ICMP_SLE:
180 return RHS.isAllOnes();
181 case ICmpInst::ICMP_SGT:
182 TrueIfSigned =
false;
183 return RHS.isAllOnes();
184 case ICmpInst::ICMP_SGE:
185 TrueIfSigned =
false;
187 case ICmpInst::ICMP_UGT:
190 return RHS.isMaxSignedValue();
191 case ICmpInst::ICMP_UGE:
194 return RHS.isMinSignedValue();
195 case ICmpInst::ICMP_ULT:
197 TrueIfSigned =
false;
198 return RHS.isMinSignedValue();
199 case ICmpInst::ICMP_ULE:
201 TrueIfSigned =
false;
202 return RHS.isMaxSignedValue();
210 return ConstantExpr::getAdd(
C, ConstantInt::get(
C->getType(), 1));
215 return ConstantExpr::getSub(
C, ConstantInt::get(
C->getType(), 1));
218 std::optional<std::pair<
230 return match(&
SI, PatternMatch::m_LogicalAnd(PatternMatch::m_Value(),
231 PatternMatch::m_Value())) ||
232 match(&
SI, PatternMatch::m_LogicalOr(PatternMatch::m_Value(),
233 PatternMatch::m_Value()));
243 Value *getFreelyInvertedImpl(
Value *V,
bool WillInvertAllUses,
250 return getFreelyInvertedImpl(V, WillInvertAllUses, Builder, DoesConsume,
257 return getFreelyInverted(V, WillInvertAllUses, Builder, Unused);
268 return getFreelyInverted(V, WillInvertAllUses,
nullptr,
269 DoesConsume) !=
nullptr;
274 return isFreeToInvert(V, WillInvertAllUses, Unused);
284 for (
Use &U : V->uses()) {
285 if (U.getUser() == IgnoredUser)
288 auto *
I = cast<Instruction>(U.getUser());
289 switch (
I->getOpcode()) {
290 case Instruction::Select:
291 if (U.getOperandNo() != 0)
293 if (shouldAvoidAbsorbingNotIntoSelect(*cast<SelectInst>(
I)))
296 case Instruction::Br:
297 assert(U.getOperandNo() == 0 &&
"Must be branching on that value.");
299 case Instruction::Xor:
301 if (!
match(
I, m_Not(PatternMatch::m_Value())))
319 bool IsRHSConstant) {
320 auto *InVTy = cast<FixedVectorType>(In->getType());
322 Type *EltTy = InVTy->getElementType();
323 auto *SafeC = ConstantExpr::getBinOpIdentity(
Opcode, EltTy, IsRHSConstant);
329 case Instruction::SRem:
330 case Instruction::URem:
331 SafeC = ConstantInt::get(EltTy, 1);
333 case Instruction::FRem:
334 SafeC = ConstantFP::get(EltTy, 1.0);
338 "Only rem opcodes have no identity constant for RHS");
342 case Instruction::Shl:
343 case Instruction::LShr:
344 case Instruction::AShr:
345 case Instruction::SDiv:
346 case Instruction::UDiv:
347 case Instruction::SRem:
348 case Instruction::URem:
349 case Instruction::Sub:
350 case Instruction::FSub:
351 case Instruction::FDiv:
352 case Instruction::FRem:
353 SafeC = Constant::getNullValue(EltTy);
360 assert(SafeC &&
"Must have safe constant for binop");
361 unsigned NumElts = InVTy->getNumElements();
363 for (
unsigned i = 0; i != NumElts; ++i) {
364 Constant *
C = In->getAggregateElement(i);
365 Out[i] = isa<UndefValue>(
C) ? SafeC :
C;
367 return ConstantVector::get(Out);
385 std::optional<Instruction *> targetInstCombineIntrinsic(
IntrinsicInst &II);
386 std::optional<Value *>
389 bool &KnownBitsComputed);
390 std::optional<Value *> targetSimplifyDemandedVectorEltsIntrinsic(
401 assert(New && !New->getParent() &&
402 "New instruction already inserted into a basic block!");
403 New->insertBefore(Old);
410 New->setDebugLoc(Old->getDebugLoc());
411 return InsertNewInstBefore(New, Old);
423 if (
I.use_empty())
return nullptr;
430 V = PoisonValue::get(
I.getType());
433 <<
" with " << *V <<
'\n');
436 if (V->use_empty() && isa<Instruction>(V) && !V->hasName() &&
I.hasName())
439 I.replaceAllUsesWith(V);
445 Value *OldOp =
I.getOperand(OpNum);
446 I.setOperand(OpNum, V);
540 unsigned Depth = 0) = 0;
544 bool AllowMultipleUsers =
false) = 0;
546 bool isValidAddrSpaceCast(
unsigned FromAS,
unsigned ToAS)
const;
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
IRBuilder< TargetFolder > BuilderTy
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())
static constexpr uint32_t Opcode
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
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...
bool isFreeToInvert(Value *V, bool WillInvertAllUses)
virtual Instruction * eraseInstFromFunction(Instruction &I)=0
Combiner aware instruction erasure.
bool isFreeToInvert(Value *V, bool WillInvertAllUses, bool &DoesConsume)
Return true if the specified value is free to invert (apply ~ to).
DominatorTree & getDominatorTree() const
virtual ~InstCombiner()=default
LoopInfo * getLoopInfo() const
static unsigned getComplexity(Value *V)
Assign a complexity or rank value to LLVM Values.
SmallDenseMap< BasicBlock *, SmallVector< BasicBlock * >, 8 > PredOrder
Order of predecessors to canonicalize phi nodes towards.
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 shouldAvoidAbsorbingNotIntoSelect(const SelectInst &SI)
OverflowResult computeOverflowForSignedAdd(const WithCache< const Value * > &LHS, const WithCache< 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
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...
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...
Value * getFreelyInverted(Value *V, bool WillInvertAllUses, BuilderTy *Builder)
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
OverflowResult computeOverflowForUnsignedAdd(const WithCache< const Value * > &LHS, const WithCache< const Value * > &RHS, const Instruction *CxtI) const
Value * getFreelyInverted(Value *V, bool WillInvertAllUses, BuilderTy *Builder, bool &DoesConsume)
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.
bool match(Val *V, const Pattern &P)
FNeg_match< OpTy > m_FNeg(const OpTy &X)
Match 'fneg X' as 'fsub -0.0, X'.
This is an optimization pass for GlobalISel generic memory operations.
bool MaskedValueIsZero(const Value *V, const APInt &Mask, const SimplifyQuery &DL, unsigned Depth=0)
Return true if 'V & Mask' is known to be zero.
OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const SimplifyQuery &SQ)
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.
OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const SimplifyQuery &SQ)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS, const SimplifyQuery &SQ)
OverflowResult computeOverflowForSignedAdd(const WithCache< const Value * > &LHS, const WithCache< const Value * > &RHS, const SimplifyQuery &SQ)
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...
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const SimplifyQuery &SQ)
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.
OverflowResult computeOverflowForUnsignedAdd(const WithCache< const Value * > &LHS, const WithCache< const Value * > &RHS, const SimplifyQuery &SQ)
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.
SimplifyQuery getWithInstruction(const Instruction *I) const