LLVM 22.0.0git
AggressiveInstCombine.cpp File Reference

Go to the source code of this file.

Classes

struct  LoadOps
 This is used by foldLoadsRecursive() to capture a Root Load node which is of type or(load, load) and recursively build the wide load. More...
struct  PartStore
 ValWidth bits starting at ValOffset of Val stored at PtrBase+PtrOffset. More...

Macros

#define DEBUG_TYPE   "aggressive-instcombine"

Functions

 STATISTIC (NumAnyOrAllBitsSet, "Number of any/all-bits-set patterns folded")
 STATISTIC (NumGuardedRotates, "Number of guarded rotates transformed into funnel shifts")
 STATISTIC (NumGuardedFunnelShifts, "Number of guarded funnel shifts transformed into funnel shifts")
 STATISTIC (NumPopCountRecognized, "Number of popcount idioms recognized")
static bool foldGuardedFunnelShift (Instruction &I, const DominatorTree &DT)
 Match a pattern for a bitwise funnel/rotate operation that partially guards against undefined behavior by branching around the funnel-shift/rotation when the shift amount is 0.
static bool matchAndOrChain (Value *V, MaskOps &MOps)
 This is a recursive helper for foldAnyOrAllBitsSet() that walks through a chain of 'and' or 'or' instructions looking for shift ops of a common source value.
static bool foldAnyOrAllBitsSet (Instruction &I)
 Match patterns that correspond to "any-bits-set" and "all-bits-set".
static bool tryToRecognizePopCount (Instruction &I)
static bool tryToFPToSat (Instruction &I, TargetTransformInfo &TTI)
 Fold smin(smax(fptosi(x), C1), C2) to llvm.fptosi.sat(x), providing C1 and C2 saturate the value of the fp conversion.
static bool foldSqrt (CallInst *Call, LibFunc Func, TargetTransformInfo &TTI, TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree &DT)
 Try to replace a mathlib call to sqrt with the LLVM intrinsic.
static bool isCTTZTable (Constant *Table, const APInt &Mul, const APInt &Shift, const APInt &AndMask, Type *AccessTy, unsigned InputBits, const APInt &GEPIdxFactor, const DataLayout &DL)
static bool tryToRecognizeTableBasedCttz (Instruction &I, const DataLayout &DL)
static bool foldLoadsRecursive (Value *V, LoadOps &LOps, const DataLayout &DL, AliasAnalysis &AA)
static bool foldConsecutiveLoads (Instruction &I, const DataLayout &DL, TargetTransformInfo &TTI, AliasAnalysis &AA, const DominatorTree &DT)
static std::optional< PartStorematchPartStore (Instruction &I, const DataLayout &DL)
static bool mergeConsecutivePartStores (ArrayRef< PartStore > Parts, unsigned Width, const DataLayout &DL, TargetTransformInfo &TTI)
static bool mergePartStores (SmallVectorImpl< PartStore > &Parts, const DataLayout &DL, TargetTransformInfo &TTI)
static bool foldConsecutiveStores (BasicBlock &BB, const DataLayout &DL, TargetTransformInfo &TTI, AliasAnalysis &AA)
static ValueoptimizeShiftInOrChain (Value *V, IRBuilder<> &Builder)
 Combine away instructions providing they are still equivalent when compared against 0.
static bool foldICmpOrChain (Instruction &I, const DataLayout &DL, TargetTransformInfo &TTI, AliasAnalysis &AA, const DominatorTree &DT)
static std::pair< APInt, APIntgetStrideAndModOffsetOfGEP (Value *PtrOp, const DataLayout &DL)
static bool foldPatternedLoads (Instruction &I, const DataLayout &DL)
 If C is a constant patterned array and all valid loaded results for given alignment are same to a constant, return that constant.
static bool foldMemChr (CallInst *Call, DomTreeUpdater *DTU, const DataLayout &DL)
 Convert memchr with a small constant string into a switch.
static bool foldLibCalls (Instruction &I, TargetTransformInfo &TTI, TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree &DT, const DataLayout &DL, bool &MadeCFGChange)
static bool foldUnusualPatterns (Function &F, DominatorTree &DT, TargetTransformInfo &TTI, TargetLibraryInfo &TLI, AliasAnalysis &AA, AssumptionCache &AC, bool &MadeCFGChange)
 This is the entry point for folds that could be implemented in regular InstCombine, but they are separated because they are not expected to occur frequently and/or have more than a constant-length pattern match.
static bool runImpl (Function &F, AssumptionCache &AC, TargetTransformInfo &TTI, TargetLibraryInfo &TLI, DominatorTree &DT, AliasAnalysis &AA, bool &MadeCFGChange)
 This is the entry point for all transforms.

Variables

static cl::opt< unsignedMaxInstrsToScan ("aggressive-instcombine-max-scan-instrs", cl::init(64), cl::Hidden, cl::desc("Max number of instructions to scan for aggressive instcombine."))
static cl::opt< unsignedStrNCmpInlineThreshold ("strncmp-inline-threshold", cl::init(3), cl::Hidden, cl::desc("The maximum length of a constant string for a builtin string cmp " "call eligible for inlining. The default value is 3."))
static cl::opt< unsignedMemChrInlineThreshold ("memchr-inline-threshold", cl::init(3), cl::Hidden, cl::desc("The maximum length of a constant string to " "inline a memchr call."))

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "aggressive-instcombine"

Definition at line 40 of file AggressiveInstCombine.cpp.

Function Documentation

◆ foldAnyOrAllBitsSet()

bool foldAnyOrAllBitsSet ( Instruction & I)
static

Match patterns that correspond to "any-bits-set" and "all-bits-set".

These will include a chain of 'or' or 'and'-shifted bits from a common source value: and (or (lshr X, C), ...), 1 --> (X & CMask) != 0 and (and (lshr X, C), ...), 1 --> (X & CMask) == CMask Note: "any-bits-clear" and "all-bits-clear" are variations of these patterns that differ only with a final 'not' of the result. We expect that final 'not' to be folded with the compare that we create here (invert predicate).

Definition at line 250 of file AggressiveInstCombine.cpp.

References llvm::cast(), I, llvm::PatternMatch::m_And(), llvm::PatternMatch::m_c_And(), llvm::PatternMatch::m_One(), llvm::MIPatternMatch::m_OneUse(), llvm::PatternMatch::m_Or(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), and matchAndOrChain().

Referenced by foldUnusualPatterns().

◆ foldConsecutiveLoads()

◆ foldConsecutiveStores()

◆ foldGuardedFunnelShift()

◆ foldICmpOrChain()

◆ foldLibCalls()

◆ foldLoadsRecursive()

◆ foldMemChr()

◆ foldPatternedLoads()

bool foldPatternedLoads ( Instruction & I,
const DataLayout & DL )
static

If C is a constant patterned array and all valid loaded results for given alignment are same to a constant, return that constant.

Definition at line 1078 of file AggressiveInstCombine.cpp.

References llvm::CallingConv::C, llvm::ConstantFoldLoadFromConst(), DL, llvm::dyn_cast(), E(), getAlign(), getStrideAndModOffsetOfGEP(), llvm::getUnderlyingObject(), and I.

Referenced by foldUnusualPatterns().

◆ foldSqrt()

bool foldSqrt ( CallInst * Call,
LibFunc Func,
TargetTransformInfo & TTI,
TargetLibraryInfo & TLI,
AssumptionCache & AC,
DominatorTree & DT )
static

Try to replace a mathlib call to sqrt with the LLVM intrinsic.

This avoids pessimistic codegen that has to account for setting errno and can enable vectorization.

Definition at line 430 of file AggressiveInstCombine.cpp.

References Call, and llvm::cannotBeOrderedLessThanZero().

Referenced by foldLibCalls().

◆ foldUnusualPatterns()

bool foldUnusualPatterns ( Function & F,
DominatorTree & DT,
TargetTransformInfo & TTI,
TargetLibraryInfo & TLI,
AliasAnalysis & AA,
AssumptionCache & AC,
bool & MadeCFGChange )
static

This is the entry point for folds that could be implemented in regular InstCombine, but they are separated because they are not expected to occur frequently and/or have more than a constant-length pattern match.

Definition at line 1443 of file AggressiveInstCombine.cpp.

References DL, F, foldAnyOrAllBitsSet(), foldConsecutiveLoads(), foldConsecutiveStores(), foldGuardedFunnelShift(), foldICmpOrChain(), foldLibCalls(), foldPatternedLoads(), I, llvm::DominatorTree::isReachableFromEntry(), llvm::make_early_inc_range(), llvm::reverse(), llvm::SimplifyInstructionsInBlock(), tryToFPToSat(), tryToRecognizePopCount(), and tryToRecognizeTableBasedCttz().

Referenced by runImpl().

◆ getStrideAndModOffsetOfGEP()

◆ isCTTZTable()

bool isCTTZTable ( Constant * Table,
const APInt & Mul,
const APInt & Shift,
const APInt & AndMask,
Type * AccessTy,
unsigned InputBits,
const APInt & GEPIdxFactor,
const DataLayout & DL )
static

◆ matchAndOrChain()

bool matchAndOrChain ( Value * V,
MaskOps & MOps )
static

This is a recursive helper for foldAnyOrAllBitsSet() that walks through a chain of 'and' or 'or' instructions looking for shift ops of a common source value.

Examples: or (or (or X, (X >> 3)), (X >> 5)), (X >> 8) returns { X, 0x129 } and (and (X >> 1), 1), (X >> 4) returns { X, 0x12 }

Definition at line 204 of file AggressiveInstCombine.cpp.

References llvm::APInt::getBitWidth(), llvm::APInt::getZExtValue(), llvm::PatternMatch::m_And(), llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_LShr(), llvm::PatternMatch::m_One(), llvm::PatternMatch::m_Or(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), matchAndOrChain(), llvm::APInt::setBit(), and llvm::APInt::uge().

Referenced by foldAnyOrAllBitsSet(), and matchAndOrChain().

◆ matchPartStore()

◆ mergeConsecutivePartStores()

◆ mergePartStores()

◆ optimizeShiftInOrChain()

Value * optimizeShiftInOrChain ( Value * V,
IRBuilder<> & Builder )
static

Combine away instructions providing they are still equivalent when compared against 0.

i.e do they have any bits set.

Definition at line 980 of file AggressiveInstCombine.cpp.

References A(), llvm::dyn_cast(), I, llvm::PatternMatch::m_CombineOr(), llvm::PatternMatch::m_NSWShl(), llvm::PatternMatch::m_NUWShl(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), and optimizeShiftInOrChain().

Referenced by foldICmpOrChain(), and optimizeShiftInOrChain().

◆ runImpl()

bool runImpl ( Function & F,
AssumptionCache & AC,
TargetTransformInfo & TTI,
TargetLibraryInfo & TLI,
DominatorTree & DT,
AliasAnalysis & AA,
bool & MadeCFGChange )
static

This is the entry point for all transforms.

Pass manager differences are handled in the callers of this function.

Definition at line 1489 of file AggressiveInstCombine.cpp.

References DL, F, foldUnusualPatterns(), and llvm::TruncInstCombine::run().

◆ STATISTIC() [1/4]

STATISTIC ( NumAnyOrAllBitsSet ,
"Number of any/all-bits-set patterns folded"  )

◆ STATISTIC() [2/4]

STATISTIC ( NumGuardedFunnelShifts ,
"Number of guarded funnel shifts transformed into funnel shifts"  )

◆ STATISTIC() [3/4]

STATISTIC ( NumGuardedRotates ,
"Number of guarded rotates transformed into funnel shifts"  )

◆ STATISTIC() [4/4]

STATISTIC ( NumPopCountRecognized ,
"Number of popcount idioms recognized"  )

◆ tryToFPToSat()

bool tryToFPToSat ( Instruction & I,
TargetTransformInfo & TTI )
static

Fold smin(smax(fptosi(x), C1), C2) to llvm.fptosi.sat(x), providing C1 and C2 saturate the value of the fp conversion.

The transform is not reversable as the fptosi.sat is more defined than the input - all values produce a valid value for the fptosi.sat, where as some produce poison for original that were out of range of the integer conversion. The reversed pattern may use fmax and fmin instead. As we cannot directly reverse the transform, and it is not always profitable, we make it conditional on the cost being reported as lower by TTI.

Definition at line 375 of file AggressiveInstCombine.cpp.

References llvm::dyn_cast(), llvm::IntegerType::get(), llvm::VectorType::get(), I, llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_FPToSI(), llvm::MIPatternMatch::m_OneUse(), llvm::PatternMatch::m_SMax(), llvm::PatternMatch::m_SMin(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), llvm::TargetTransformInfo::None, and llvm::TargetTransformInfo::TCK_RecipThroughput.

Referenced by foldUnusualPatterns().

◆ tryToRecognizePopCount()

◆ tryToRecognizeTableBasedCttz()

Variable Documentation

◆ MaxInstrsToScan

cl::opt< unsigned > MaxInstrsToScan("aggressive-instcombine-max-scan-instrs", cl::init(64), cl::Hidden, cl::desc("Max number of instructions to scan for aggressive instcombine.")) ( "aggressive-instcombine-max-scan-instrs" ,
cl::init(64) ,
cl::Hidden ,
cl::desc("Max number of instructions to scan for aggressive instcombine.")  )
static

◆ MemChrInlineThreshold

cl::opt< unsigned > MemChrInlineThreshold("memchr-inline-threshold", cl::init(3), cl::Hidden, cl::desc("The maximum length of a constant string to " "inline a memchr call.")) ( "memchr-inline-threshold" ,
cl::init(3) ,
cl::Hidden ,
cl::desc("The maximum length of a constant string to " "inline a memchr call.")  )
static

Referenced by foldMemChr().

◆ StrNCmpInlineThreshold

cl::opt< unsigned > StrNCmpInlineThreshold("strncmp-inline-threshold", cl::init(3), cl::Hidden, cl::desc("The maximum length of a constant string for a builtin string cmp " "call eligible for inlining. The default value is 3.")) ( "strncmp-inline-threshold" ,
cl::init(3) ,
cl::Hidden ,
cl::desc("The maximum length of a constant string for a builtin string cmp " "call eligible for inlining. The default value is 3.")  )
static