Go to the documentation of this file.
15 #ifndef LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H
16 #define LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H
32 #define DEBUG_TYPE "instcombine"
48 class AssumptionCache;
49 class BlockFrequencyInfo;
55 class OptimizationRemarkEmitter;
56 class ProfileSummaryInfo;
57 class TargetLibraryInfo;
62 public InstVisitor<InstCombinerImpl, Instruction *> {
90 Value *OptimizePointerDifference(
111 Value *reassociateShiftAmtsOfTwoSameDirectionShifts(
113 bool AnalyzeForSignBitExtraction =
false);
114 Instruction *canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(
116 Instruction *foldVariableSignZeroExtensionOfVariableHighBitExtract(
184 const unsigned SIOpd);
187 const Twine &Suffix =
"");
190 bool shouldChangeType(
unsigned FromBitWidth,
unsigned ToBitWidth)
const;
205 bool shouldOptimizeCast(
CastInst *CI);
226 bool transformConstExprCastCall(
CallBase &Call);
248 bool DoTransform =
true);
252 bool willNotOverflowSignedAdd(
const Value *LHS,
const Value *RHS,
258 bool willNotOverflowUnsignedAdd(
const Value *LHS,
const Value *RHS,
259 const Instruction &CxtI)
const {
264 bool willNotOverflowAdd(
const Value *LHS,
const Value *RHS,
265 const Instruction &CxtI,
bool IsSigned)
const {
266 return IsSigned ? willNotOverflowSignedAdd(LHS, RHS, CxtI)
267 : willNotOverflowUnsignedAdd(LHS, RHS, CxtI);
270 bool willNotOverflowSignedSub(
const Value *LHS,
const Value *RHS,
271 const Instruction &CxtI)
const {
276 bool willNotOverflowUnsignedSub(
const Value *LHS,
const Value *RHS,
277 const Instruction &CxtI)
const {
282 bool willNotOverflowSub(
const Value *LHS,
const Value *RHS,
283 const Instruction &CxtI,
bool IsSigned)
const {
284 return IsSigned ? willNotOverflowSignedSub(LHS, RHS, CxtI)
285 : willNotOverflowUnsignedSub(LHS, RHS, CxtI);
288 bool willNotOverflowSignedMul(
const Value *LHS,
const Value *RHS,
289 const Instruction &CxtI)
const {
294 bool willNotOverflowUnsignedMul(
const Value *LHS,
const Value *RHS,
295 const Instruction &CxtI)
const {
300 bool willNotOverflowMul(
const Value *LHS,
const Value *RHS,
301 const Instruction &CxtI,
bool IsSigned)
const {
302 return IsSigned ? willNotOverflowSignedMul(LHS, RHS, CxtI)
303 : willNotOverflowUnsignedMul(LHS, RHS, CxtI);
307 const Value *RHS,
const Instruction &CxtI,
308 bool IsSigned)
const {
311 case Instruction::Sub:
return willNotOverflowSub(LHS, RHS, CxtI, IsSigned);
312 case Instruction::Mul:
return willNotOverflowMul(LHS, RHS, CxtI, IsSigned);
318 Instruction *scalarizePHI(ExtractElementInst &EI, PHINode *PN);
319 Instruction *foldCastedBitwiseLogic(BinaryOperator &
I);
320 Instruction *narrowBinOp(TruncInst &Trunc);
321 Instruction *narrowMaskedBinOp(BinaryOperator &And);
322 Instruction *narrowMathIfNoOverflow(BinaryOperator &
I);
323 Instruction *narrowFunnelShift(TruncInst &Trunc);
324 Instruction *optimizeBitCastFromPhi(CastInst &CI, PHINode *PN);
325 Instruction *matchSAddSubSat(SelectInst &MinMax1);
327 void freelyInvertAllUsersOf(
Value *V);
340 const CastInst *CI2);
342 Value *foldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS, BinaryOperator &And);
343 Value *foldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, BinaryOperator &Or);
344 Value *foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS, BinaryOperator &Xor);
349 Value *foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS,
bool IsAnd);
351 Value *foldAndOrOfICmpsOfAndWithPow2(ICmpInst *LHS, ICmpInst *RHS,
352 BinaryOperator &Logic);
356 Instruction *foldIntrinsicWithOverflowCommon(IntrinsicInst *II);
357 Instruction *foldFPSignBitOps(BinaryOperator &
I);
365 assert(New && !New->getParent() &&
366 "New instruction already inserted into a basic block!");
376 return InsertNewInstBefore(New, Old);
388 if (
I.use_empty())
return nullptr;
390 Worklist.pushUsersToWorkList(
I);
398 <<
" with " << *V <<
'\n');
400 I.replaceAllUsesWith(V);
407 Worklist.addValue(
I.getOperand(OpNum));
408 I.setOperand(OpNum, V);
414 Worklist.addValue(U);
445 assert(
I.use_empty() &&
"Cannot erase instruction that is used!");
450 for (
Use &Operand :
I.operands())
451 if (
auto *Inst = dyn_cast<Instruction>(Operand))
570 unsigned Depth = 0)
override;
576 const APInt &DemandedMask,
582 Value *simplifyShrShlDemandedBits(
588 bool SimplifyDemandedInstructionBits(
Instruction &Inst);
591 SimplifyDemandedVectorElts(
Value *V,
APInt DemandedElts,
APInt &UndefElts,
593 bool AllowMultipleUsers =
false)
override;
658 Value *foldUnsignedMultiplicationOverflowCheck(
ICmpInst &Cmp);
714 bool isSigned,
bool Inside);
722 bool MatchBitReversals);
727 Value *EvaluateInDifferentType(
Value *V,
Type *Ty,
bool isSigned);
746 const bool IsTrulyNegation;
753 #if LLVM_ENABLE_STATS
754 unsigned NumValuesVisitedInThisNegator = 0;
758 using Result = std::pair<ArrayRef<Instruction *> ,
761 std::array<Value *, 2> getSortedOperandsOfBinOp(
Instruction *
I);
787 #endif // LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H
bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero=false, unsigned Depth=0, const Instruction *CxtI=nullptr)
@ NeverOverflows
Never overflows.
Return a value (possibly void), from a function.
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.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
static Constant * get(StructType *T, ArrayRef< Constant * > V)
This class represents a no-op cast from one type to another.
instcombine should handle this C2 when C1
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Instruction * InsertNewInstBefore(Instruction *New, Instruction &Old)
Inserts an instruction New before instruction Old.
The landingpad instruction holds all of the information necessary to generate correct exception handl...
static InsertValueInst * Create(Value *Agg, Value *Val, ArrayRef< unsigned > Idxs, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
OverflowResult computeOverflowForUnsignedAdd(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
virtual ~InstCombinerImpl()
The instances of the Type class are immutable: once they are created, they are never changed.
KnownBits computeKnownBits(const Value *V, unsigned Depth, const Instruction *CxtI) const
Instruction * replaceInstUsesWith(Instruction &I, Value *V)
A combiner-aware RAUW-like routine.
An instruction for ordering other memory operations.
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.
SelectPatternFlavor
Specific patterns of select instructions we can match.
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.
Value * EmitGEPOffset(IRBuilderTy *Builder, const DataLayout &DL, User *GEP, bool NoAssumptions=false)
Given a getelementptr instruction/constantexpr, emit the code necessary to compute the offset from th...
LLVM Basic Block Representation.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Instruction * eraseInstFromFunction(Instruction &I) override
Combiner aware instruction erasure.
This is the shared class of boolean and integer constants.
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...
This class represents a conversion between pointers from one address space to another.
OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
(vector float) vec_cmpeq(*A, *B) C
Instruction * CreateOverflowTuple(IntrinsicInst *II, Value *Result, Constant *Overflow)
Creates a result tuple for an overflow intrinsic II with a given Result and a constant Overflow value...
This instruction compares its operands according to the predicate given to the constructor.
This instruction inserts a single (scalar) element into a VectorType value.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
InstCombineWorklist - This is the worklist management logic for InstCombine.
static PointerType * getInt1PtrTy(LLVMContext &C, unsigned AS=0)
static constexpr unsigned NegatorDefaultMaxDepth
OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
InstCombinerImpl(InstCombineWorklist &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)
Analysis providing profile information.
This class is the base class for the comparison instructions.
An instruction for storing to memory.
This is an important base class in LLVM.
This instruction compares its operands according to the predicate given to the constructor.
This class represents a cast from floating point to signed integer.
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
This class represents a truncation of integer types.
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)
CallBr instruction, tracking function calls that may not return control but instead transfer it to a ...
This is an important class for using LLVM in a threaded context.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
void replaceUse(Use &U, Value *NewValue)
Replace use and add the previously used value to the worklist.
Class to represent pointers.
OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
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())
This class represents the LLVM 'select' instruction.
This class represents a cast from floating point to unsigned integer.
Class for arbitrary precision integers.
This class represents zero extension of integer types.
static constexpr unsigned NegatorMaxNodesSSO
Instruction * visitInstruction(Instruction &I)
Specify what to return for unhandled instructions.
This represents the llvm.va_end intrinsic.
unsigned ComputeNumSignBits(const Value *Op, unsigned Depth=0, const Instruction *CxtI=nullptr) const
Class to represent struct types.
SmallVector< MachineOperand, 4 > Cond
A cache of @llvm.assume calls within a function.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Type * getType() const
All values are typed, get the type of this value.
LLVMContext & getContext() const
All values hold a context through their type.
self_iterator getIterator()
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This class represents a cast from a pointer to an integer.
#define LLVM_LIBRARY_VISIBILITY
LLVM_LIBRARY_VISIBILITY - If a class marked with this attribute is linked into a shared library,...
Base class for instruction visitors.
This is the base class for all instructions that perform data casts.
This class represents a sign extension of integer types.
An instruction for reading from memory.
an instruction that atomically reads a memory location, combines it with another value,...
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
static ConstantInt * getTrue(LLVMContext &Context)
Instruction * InsertNewInstWith(Instruction *New, Instruction &Old)
Same as InsertNewInstBefore, but also sets the debug loc.
This class represents any memset intrinsic.
OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
#define LLVM_NODISCARD
LLVM_NODISCARD - Warn if a type or return value is discarded.
void CreateNonTerminatorUnreachable(Instruction *InsertAt)
Create and insert the idiom we use to indicate a block is unreachable without having to rewrite the C...
void salvageDebugInfo(Instruction &I)
Assuming the instruction I is going to be deleted, attempt to salvage debug users of I by writing the...
Provides information about what library functions are available for the current target.
OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
This class represents a cast from an integer to a pointer.
The core instruction combiner logic.
A wrapper class for inspecting calls to intrinsic functions.
Instruction * replaceOperand(Instruction &I, unsigned OpNum, Value *V)
Replace operand of instruction and add old operand to the worklist.
This instruction constructs a fixed permutation of two input vectors.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
This class represents a freeze function that returns random concrete value if an operand is either a ...
This class represents a truncation of floating point types.
const BasicBlock * getParent() const
OverflowResult computeOverflowForUnsignedAdd(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
This class represents a function call, abstracting a target machine's calling convention.
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
This function has undefined behavior.
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.
BlockVerifier::State From
an instruction to allocate memory on the stack
Conditional or Unconditional Branch instruction.
This instruction inserts a struct field of array element value into an aggregate value.
static bool foldICmpWithDominatingICmp(CmpInst *Cmp, const TargetLowering &TLI)
For pattern like:
LLVM Value Representation.
bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth=0, const Instruction *CxtI=nullptr) const
void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth, const Instruction *CxtI) const
A Use represents the edge between a Value definition and its users.