18#ifndef LLVM_TRANSFORMS_INSTCOMBINE_INSTCOMBINER_H
19#define LLVM_TRANSFORMS_INSTCOMBINE_INSTCOMBINER_H
32#define DEBUG_TYPE "instcombine"
39class OptimizationRemarkEmitter;
40class ProfileSummaryInfo;
41class TargetLibraryInfo;
42class TargetTransformInfo;
86 bool MadeIRChange =
false;
98 bool ComputedBackEdges =
false;
108 : TTIForTargetIntrinsicsOnly(
TTI), Builder(Builder), Worklist(Worklist),
109 MinimizeSize(MinimizeSize), AA(AA), AC(AC), TLI(TLI), DT(DT),
DL(
DL),
110 SQ(
DL, &TLI, &DT, &AC, nullptr,
true,
112 ORE(ORE), BFI(BFI), BPI(BPI), PSI(PSI), RPOT(RPOT) {}
120 if (
auto *BitCast = dyn_cast<BitCastInst>(V))
121 if (!OneUseOnly || BitCast->hasOneUse())
122 return BitCast->getOperand(0);
144 if (isa<Constant>(V))
145 return isa<UndefValue>(V) ? 0 : 1;
147 if (isa<CastInst>(V) || match(V, m_Neg(PatternMatch::m_Value())) ||
148 match(V, m_Not(PatternMatch::m_Value())) ||
149 match(V,
m_FNeg(PatternMatch::m_Value())))
162 case CmpInst::ICMP_NE:
163 case CmpInst::ICMP_ULE:
164 case CmpInst::ICMP_SLE:
165 case CmpInst::ICMP_UGE:
166 case CmpInst::ICMP_SGE:
168 case CmpInst::FCMP_ONE:
169 case CmpInst::FCMP_OLE:
170 case CmpInst::FCMP_OGE:
179 return ConstantExpr::getAdd(
C, ConstantInt::get(
C->getType(), 1));
184 return ConstantExpr::getSub(
C, ConstantInt::get(
C->getType(), 1));
187 std::optional<std::pair<
198 return match(&
SI, PatternMatch::m_LogicalAnd(PatternMatch::m_Value(),
199 PatternMatch::m_Value())) ||
200 match(&
SI, PatternMatch::m_LogicalOr(PatternMatch::m_Value(),
201 PatternMatch::m_Value()));
211 Value *getFreelyInvertedImpl(
Value *V,
bool WillInvertAllUses,
218 return getFreelyInvertedImpl(V, WillInvertAllUses, Builder, DoesConsume,
225 return getFreelyInverted(V, WillInvertAllUses, Builder, Unused);
236 return getFreelyInverted(V, WillInvertAllUses,
nullptr,
237 DoesConsume) !=
nullptr;
242 return isFreeToInvert(V, WillInvertAllUses, Unused);
252 for (
Use &U : V->uses()) {
253 if (U.getUser() == IgnoredUser)
256 auto *
I = cast<Instruction>(U.getUser());
257 switch (
I->getOpcode()) {
258 case Instruction::Select:
259 if (U.getOperandNo() != 0)
261 if (shouldAvoidAbsorbingNotIntoSelect(*cast<SelectInst>(
I)))
264 case Instruction::Br:
265 assert(U.getOperandNo() == 0 &&
"Must be branching on that value.");
267 case Instruction::Xor:
269 if (!match(
I, m_Not(PatternMatch::m_Value())))
287 bool IsRHSConstant) {
288 auto *InVTy = cast<FixedVectorType>(In->getType());
290 Type *EltTy = InVTy->getElementType();
291 auto *SafeC = ConstantExpr::getBinOpIdentity(Opcode, EltTy, IsRHSConstant);
297 case Instruction::SRem:
298 case Instruction::URem:
299 SafeC = ConstantInt::get(EltTy, 1);
301 case Instruction::FRem:
302 SafeC = ConstantFP::get(EltTy, 1.0);
306 "Only rem opcodes have no identity constant for RHS");
310 case Instruction::Shl:
311 case Instruction::LShr:
312 case Instruction::AShr:
313 case Instruction::SDiv:
314 case Instruction::UDiv:
315 case Instruction::SRem:
316 case Instruction::URem:
317 case Instruction::Sub:
318 case Instruction::FSub:
319 case Instruction::FDiv:
320 case Instruction::FRem:
321 SafeC = Constant::getNullValue(EltTy);
328 assert(SafeC &&
"Must have safe constant for binop");
329 unsigned NumElts = InVTy->getNumElements();
331 for (
unsigned i = 0; i != NumElts; ++i) {
332 Constant *
C = In->getAggregateElement(i);
333 Out[i] = isa<UndefValue>(
C) ? SafeC :
C;
335 return ConstantVector::get(Out);
352 std::optional<Instruction *> targetInstCombineIntrinsic(
IntrinsicInst &
II);
353 std::optional<Value *>
356 bool &KnownBitsComputed);
357 std::optional<Value *> targetSimplifyDemandedVectorEltsIntrinsic(
363 void computeBackEdges();
365 if (!ComputedBackEdges)
375 assert(New && !New->getParent() &&
376 "New instruction already inserted into a basic block!");
377 New->insertBefore(Old);
384 New->setDebugLoc(Old->getDebugLoc());
385 return InsertNewInstBefore(New, Old);
397 if (
I.use_empty())
return nullptr;
404 V = PoisonValue::get(
I.getType());
407 <<
" with " << *V <<
'\n');
410 if (V->use_empty() && isa<Instruction>(V) && !V->hasName() &&
I.hasName())
413 I.replaceAllUsesWith(V);
419 Value *OldOp =
I.getOperand(OpNum);
420 I.setOperand(OpNum, V);
474 bool IsNSW =
false)
const {
520 return SimplifyDemandedBits(
I, OpNo, DemandedMask, Known,
527 bool AllowMultipleUsers =
false) = 0;
529 bool isValidAddrSpaceCast(
unsigned FromAS,
unsigned ToAS)
const;
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
BlockVerifier::State From
IRBuilder< TargetFolder > BuilderTy
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
#define LLVM_LIBRARY_VISIBILITY
uint64_t IntrinsicInst * II
StandardInstrumentations SI(Mod->getContext(), Debug, VerifyEach)
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Class for arbitrary precision integers.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
InstListType::iterator iterator
Instruction iterators...
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Analysis providing branch probability information.
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
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
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
OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const Instruction *CxtI, bool IsNSW=false) const
virtual ~InstCombiner()=default
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.
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.
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.
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
static bool isCanonicalPredicate(CmpPredicate Pred)
Predicate canonicalization reduces the number of patterns that need to be matched by other transforms...
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.
BranchProbabilityInfo * BPI
bool SimplifyDemandedBits(Instruction *I, unsigned OpNo, const APInt &DemandedMask, KnownBits &Known)
ReversePostOrderTraversal< BasicBlock * > & RPOT
unsigned ComputeNumSignBits(const Value *Op, unsigned Depth=0, const Instruction *CxtI=nullptr) const
virtual bool SimplifyDemandedBits(Instruction *I, unsigned OpNo, const APInt &DemandedMask, KnownBits &Known, unsigned Depth, const SimplifyQuery &Q)=0
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)
SmallDenseSet< std::pair< const BasicBlock *, const BasicBlock * >, 8 > BackEdges
Backedges, used to avoid pushing instructions across backedges in cases where this may result in infi...
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
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
bool isBackEdge(const BasicBlock *From, const BasicBlock *To)
InstCombiner(InstructionWorklist &Worklist, BuilderTy &Builder, bool MinimizeSize, AAResults *AA, AssumptionCache &AC, TargetLibraryInfo &TLI, TargetTransformInfo &TTI, DominatorTree &DT, OptimizationRemarkEmitter &ORE, BlockFrequencyInfo *BFI, BranchProbabilityInfo *BPI, ProfileSummaryInfo *PSI, const DataLayout &DL, ReversePostOrderTraversal< BasicBlock * > &RPOT)
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.
bool contains(const_arg_type_t< ValueT > V) const
Check if the set contains the given element.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
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 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.
bool MaskedValueIsZero(const Value *V, const APInt &Mask, const SimplifyQuery &SQ, 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 IsNSW=false)
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