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"
49 class AssumptionCache;
50 class BlockFrequencyInfo;
56 class OptimizationRemarkEmitter;
57 class ProfileSummaryInfo;
58 class TargetLibraryInfo;
63 public InstVisitor<InstCombinerImpl, Instruction *> {
91 Value *OptimizePointerDifference(
112 Value *reassociateShiftAmtsOfTwoSameDirectionShifts(
114 bool AnalyzeForSignBitExtraction =
false);
115 Instruction *canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(
117 Instruction *foldVariableSignZeroExtensionOfVariableHighBitExtract(
190 const unsigned SIOpd);
193 const Twine &Suffix =
"");
197 bool isDesirableIntType(
unsigned BitWidth)
const;
198 bool shouldChangeType(
unsigned FromBitWidth,
unsigned ToBitWidth)
const;
211 bool shouldOptimizeCast(
CastInst *CI);
232 bool transformConstExprCastCall(
CallBase &Call);
261 const Instruction &CxtI)
const {
267 const Instruction &CxtI,
bool IsSigned)
const {
268 return IsSigned ? willNotOverflowSignedAdd(
LHS,
RHS, CxtI)
269 : willNotOverflowUnsignedAdd(
LHS,
RHS, CxtI);
273 const Instruction &CxtI)
const {
279 const Instruction &CxtI)
const {
285 const Instruction &CxtI,
bool IsSigned)
const {
286 return IsSigned ? willNotOverflowSignedSub(
LHS,
RHS, CxtI)
287 : willNotOverflowUnsignedSub(
LHS,
RHS, CxtI);
291 const Instruction &CxtI)
const {
297 const Instruction &CxtI)
const {
303 const Instruction &CxtI,
bool IsSigned)
const {
304 return IsSigned ? willNotOverflowSignedMul(
LHS,
RHS, CxtI)
305 : willNotOverflowUnsignedMul(
LHS,
RHS, CxtI);
309 const Value *
RHS,
const Instruction &CxtI,
310 bool IsSigned)
const {
313 case Instruction::Sub:
return willNotOverflowSub(
LHS,
RHS, CxtI, IsSigned);
320 Instruction *scalarizePHI(ExtractElementInst &EI, PHINode *PN);
321 Instruction *foldBitcastExtElt(ExtractElementInst &ExtElt);
322 Instruction *foldCastedBitwiseLogic(BinaryOperator &
I);
323 Instruction *foldBinopOfSextBoolToSelect(BinaryOperator &
I);
324 Instruction *narrowBinOp(TruncInst &Trunc);
325 Instruction *narrowMaskedBinOp(BinaryOperator &And);
326 Instruction *narrowMathIfNoOverflow(BinaryOperator &
I);
327 Instruction *narrowFunnelShift(TruncInst &Trunc);
328 Instruction *optimizeBitCastFromPhi(CastInst &CI, PHINode *PN);
329 Instruction *matchSAddSubSat(IntrinsicInst &MinMax1);
330 Instruction *foldNot(BinaryOperator &
I);
332 void freelyInvertAllUsersOf(
Value *V);
345 const CastInst *CI2);
346 Value *simplifyIntToPtrRoundTripCast(
Value *Val);
348 Value *foldAndOrOfICmps(ICmpInst *
LHS, ICmpInst *
RHS, Instruction &
I,
350 Value *foldXorOfICmps(ICmpInst *
LHS, ICmpInst *
RHS, BinaryOperator &Xor);
352 Value *foldEqOfParts(ICmpInst *Cmp0, ICmpInst *Cmp1,
bool IsAnd);
354 Value *foldAndOrOfICmpsUsingRanges(ICmpInst *ICmp1, ICmpInst *ICmp2,
360 Value *foldLogicOfFCmps(FCmpInst *
LHS, FCmpInst *
RHS,
bool IsAnd,
361 bool IsLogicalSelect =
false);
363 Value *foldAndOrOfICmpsOfAndWithPow2(ICmpInst *
LHS, ICmpInst *
RHS,
364 Instruction *CxtI,
bool IsAnd,
369 Instruction *foldIntrinsicWithOverflowCommon(IntrinsicInst *II);
370 Instruction *foldFPSignBitOps(BinaryOperator &
I);
376 Instruction *foldAndOrOfSelectUsingImpliedCond(
Value *
Op, SelectInst &
SI,
385 assert(New && !New->getParent() &&
386 "New instruction already inserted into a basic block!");
396 return InsertNewInstBefore(New, Old);
408 if (
I.use_empty())
return nullptr;
410 Worklist.pushUsersToWorkList(
I);
418 <<
" with " << *V <<
'\n');
420 I.replaceAllUsesWith(V);
427 Worklist.addValue(
I.getOperand(OpNum));
428 I.setOperand(OpNum, V);
434 Worklist.addValue(U);
455 assert(
I.use_empty() &&
"Cannot erase instruction that is used!");
460 for (
Use &Operand :
I.operands())
461 if (
auto *Inst = dyn_cast<Instruction>(Operand))
580 unsigned Depth = 0)
override;
586 const APInt &DemandedMask,
592 Value *simplifyShrShlDemandedBits(
598 bool SimplifyDemandedInstructionBits(
Instruction &Inst);
601 SimplifyDemandedVectorElts(
Value *V,
APInt DemandedElts,
APInt &UndefElts,
603 bool AllowMultipleUsers =
false)
override;
630 bool FoldWithMultiUse =
false);
745 bool isSigned,
bool Inside);
753 bool MatchBitReversals);
758 Value *EvaluateInDifferentType(
Value *V,
Type *Ty,
bool isSigned);
777 const bool IsTrulyNegation;
784 #if LLVM_ENABLE_STATS
785 unsigned NumValuesVisitedInThisNegator = 0;
789 using Result = std::pair<ArrayRef<Instruction *> ,
792 std::array<Value *, 2> getSortedOperandsOfBinOp(
Instruction *
I);
818 #endif // LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H
bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero=false, unsigned Depth=0, const Instruction *CxtI=nullptr)
This is an optimization pass for GlobalISel generic memory operations.
@ 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)
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...
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.
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
InstCombinerImpl(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)
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.
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.
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.
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
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 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")
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
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.
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())
StandardInstrumentations SI(Debug, VerifyEach)
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
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.
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
constexpr unsigned BitWidth
#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.
InstructionWorklist - This is the worklist management logic for InstCombine and other simplification ...
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
static const uint32_t IV[8]
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.
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.