LLVM 20.0.0git
|
#include "llvm/Transforms/AggressiveInstCombine/AggressiveInstCombine.h"
#include "AggressiveInstCombineInternal.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/BasicAliasAnalysis.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/BuildLibCalls.h"
#include "llvm/Transforms/Utils/Local.h"
Go to the source code of this file.
Classes | |
struct | MaskOps |
This is used by foldAnyOrAllBitsSet() to capture a source value (Root) and the bit indexes (Mask) needed by a masked compare. More... | |
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... | |
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 (const ConstantDataArray &Table, uint64_t Mul, uint64_t Shift, uint64_t InputBits) |
static bool | tryToRecognizeTableBasedCttz (Instruction &I) |
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::pair< APInt, APInt > | getStrideAndModOffsetOfGEP (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< unsigned > | MaxInstrsToScan ("aggressive-instcombine-max-scan-instrs", cl::init(64), cl::Hidden, cl::desc("Max number of instructions to scan for aggressive instcombine.")) |
static 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.")) |
static 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.")) |
#define DEBUG_TYPE "aggressive-instcombine" |
Definition at line 39 of file AggressiveInstCombine.cpp.
|
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 247 of file AggressiveInstCombine.cpp.
References llvm::And, llvm::IRBuilderBase::CreateAnd(), llvm::IRBuilderBase::CreateICmpEQ(), llvm::IRBuilderBase::CreateIsNotNull(), llvm::IRBuilderBase::CreateZExt(), MaskOps::FoundAnd1, I, llvm::PatternMatch::m_And(), llvm::PatternMatch::m_c_And(), llvm::PatternMatch::m_One(), llvm::PatternMatch::m_OneUse(), llvm::PatternMatch::m_Or(), llvm::PatternMatch::m_Value(), MaskOps::Mask, llvm::PatternMatch::match(), matchAndOrChain(), and MaskOps::Root.
Referenced by foldUnusualPatterns().
|
static |
Definition at line 777 of file AggressiveInstCombine.cpp.
References LoadOps::AATags, llvm::TargetTransformInfo::allowsMisalignedMemoryAccesses(), llvm::IRBuilderBase::CreateAlignedLoad(), llvm::IRBuilderBase::CreatePtrAdd(), llvm::IRBuilderBase::CreateShl(), llvm::IRBuilderBase::CreateZExt(), DL, llvm::DominatorTree::dominates(), llvm::CallingConv::Fast, foldLoadsRecursive(), LoadOps::FoundRoot, llvm::IntegerType::get(), llvm::IRBuilderBase::getInt32(), llvm::Value::getType(), llvm::APInt::getZExtValue(), I, llvm::TargetTransformInfo::isTypeLegal(), LoadOps::LoadSize, LoadOps::Root, LoadOps::RootInsert, llvm::Instruction::setAAMetadata(), llvm::IRBuilderBase::SetInsertPoint(), LoadOps::Shift, llvm::Value::stripAndAccumulateConstantOffsets(), llvm::Value::takeName(), and LoadOps::ZextType.
Referenced by foldUnusualPatterns().
|
static |
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.
Definition at line 65 of file AggressiveInstCombine.cpp.
References assert(), llvm::IRBuilderBase::CreateCall(), llvm::IRBuilderBase::CreateFreeze(), llvm::DominatorTree::dominates(), F, llvm::Intrinsic::getDeclaration(), llvm::BasicBlock::getFirstInsertionPt(), llvm::BasicBlock::getTerminator(), I, llvm::CmpInst::ICMP_EQ, llvm::isGuaranteedNotToBePoison(), llvm::isPowerOf2_32(), llvm::PatternMatch::m_Br(), llvm::PatternMatch::m_c_Or(), llvm::PatternMatch::m_Deferred(), llvm::PatternMatch::m_LShr(), llvm::PatternMatch::m_OneUse(), llvm::PatternMatch::m_Shl(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_SpecificBB(), llvm::PatternMatch::m_SpecificICmp(), llvm::PatternMatch::m_SpecificInt(), llvm::PatternMatch::m_Sub(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_ZeroInt(), llvm::PatternMatch::match(), matchFunnelShift(), llvm::Intrinsic::not_intrinsic, and std::swap().
Referenced by foldUnusualPatterns().
|
static |
Definition at line 1183 of file AggressiveInstCombine.cpp.
References DL, foldMemChr(), foldSqrt(), llvm::TargetLibraryInfo::getLibFunc(), I, and llvm::isLibFuncEmittable().
Referenced by foldUnusualPatterns().
|
static |
Definition at line 629 of file AggressiveInstCombine.cpp.
References LoadOps::AATags, llvm::AAMDNodes::concat(), DL, End, foldLoadsRecursive(), LoadOps::FoundRoot, llvm::MemoryLocation::get(), llvm::IntegerType::get(), llvm::Instruction::getAAMetadata(), llvm::Value::getContext(), llvm::AAResults::getModRefInfo(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::LoadInst::getPointerAddressSpace(), llvm::LoadInst::getPointerOperand(), llvm::Type::getPrimitiveSizeInBits(), llvm::Value::getType(), llvm::MemoryLocation::getWithNewSize(), llvm::APInt::getZExtValue(), llvm::isModSet(), llvm::isPowerOf2_64(), llvm::LoadInst::isSimple(), LoadOps::LoadSize, llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_c_Or(), llvm::PatternMatch::m_Instruction(), llvm::PatternMatch::m_OneUse(), llvm::PatternMatch::m_Or(), llvm::PatternMatch::m_Shl(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_ZExt(), llvm::make_range(), llvm::PatternMatch::match(), MaxInstrsToScan, llvm::Reverse, LoadOps::Root, LoadOps::RootInsert, LoadOps::Shift, llvm::APInt::slt(), llvm::Value::stripAndAccumulateConstantOffsets(), std::swap(), X, and LoadOps::ZextType.
Referenced by foldConsecutiveLoads(), and foldLoadsRecursive().
|
static |
Convert memchr with a small constant string into a switch.
Definition at line 1109 of file AggressiveInstCombine.cpp.
References llvm::PHINode::addIncoming(), llvm::GenericDomTreeUpdater< DerivedT, DomTreeT, PostDomTreeT >::applyUpdates(), llvm::sampleprof::Base, llvm::BasicBlock::begin(), llvm::BasicBlock::Create(), llvm::PHINode::Create(), llvm::IRBuilderBase::CreateBr(), llvm::IRBuilderBase::CreateInBoundsPtrAdd(), llvm::IRBuilderBase::CreatePHI(), llvm::IRBuilderBase::CreateSwitch(), llvm::IRBuilderBase::CreateTrunc(), DL, llvm::Instruction::eraseFromParent(), llvm::getConstantStringInfo(), llvm::IRBuilderBase::getInt8Ty(), llvm::Constant::getNullValue(), llvm::BasicBlock::getParent(), llvm::BasicBlock::getTerminator(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), MemChrInlineThreshold, N, PHI, llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::IRBuilderBase::SetInsertPoint(), and llvm::SplitBlock().
Referenced by foldLibCalls().
|
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 880 of file AggressiveInstCombine.cpp.
References llvm::CallingConv::C, llvm::ConstantFoldLoadFromConst(), DL, getAlign(), getStrideAndModOffsetOfGEP(), llvm::getUnderlyingObject(), and I.
Referenced by foldUnusualPatterns().
|
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 411 of file AggressiveInstCombine.cpp.
References llvm::cannotBeOrderedLessThanZero(), llvm::IRBuilderBase::CreateCall(), llvm::Intrinsic::getDeclaration(), llvm::TargetTransformInfo::haveFastSqrt(), and llvm::IRBuilderBase::setFastMathFlags().
Referenced by foldLibCalls().
|
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 1229 of file AggressiveInstCombine.cpp.
References DL, F, foldAnyOrAllBitsSet(), foldConsecutiveLoads(), foldGuardedFunnelShift(), foldLibCalls(), foldPatternedLoads(), I, llvm::DominatorTree::isReachableFromEntry(), llvm::make_early_inc_range(), llvm::reverse(), llvm::SimplifyInstructionsInBlock(), tryToFPToSat(), tryToRecognizePopCount(), and tryToRecognizeTableBasedCttz().
Referenced by runImpl().
|
static |
Definition at line 839 of file AggressiveInstCombine.cpp.
References DL, GEP, llvm::APInt::getOneBitSet(), llvm::Value::getType(), llvm::APIntOps::GreatestCommonDivisor(), llvm::APInt::isNegative(), and llvm::APInt::srem().
Referenced by foldPatternedLoads().
|
static |
Definition at line 450 of file AggressiveInstCombine.cpp.
References llvm::APInt::getBitsSetFrom(), llvm::ConstantDataSequential::getElementAsInteger(), llvm::ConstantDataSequential::getNumElements(), llvm::Length, and Mul.
Referenced by tryToRecognizeTableBasedCttz().
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 201 of file AggressiveInstCombine.cpp.
References MaskOps::FoundAnd1, 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(), MaskOps::Mask, llvm::PatternMatch::match(), MaskOps::MatchAndChain, matchAndOrChain(), MaskOps::Root, llvm::APInt::setBit(), and llvm::APInt::uge().
Referenced by foldAnyOrAllBitsSet(), and matchAndOrChain().
|
static |
This is the entry point for all transforms.
Pass manager differences are handled in the callers of this function.
Definition at line 1271 of file AggressiveInstCombine.cpp.
References DL, F, foldUnusualPatterns(), and llvm::TruncInstCombine::run().
STATISTIC | ( | NumAnyOrAllBitsSet | , |
"Number of any/all-bits-set patterns folded" | |||
) |
STATISTIC | ( | NumGuardedFunnelShifts | , |
"Number of guarded funnel shifts transformed into funnel shifts" | |||
) |
STATISTIC | ( | NumGuardedRotates | , |
"Number of guarded rotates transformed into funnel shifts" | |||
) |
STATISTIC | ( | NumPopCountRecognized | , |
"Number of popcount idioms recognized" | |||
) |
|
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 355 of file AggressiveInstCombine.cpp.
References llvm::IRBuilderBase::CreateCall(), llvm::IRBuilderBase::CreateSExt(), llvm::IntegerType::get(), llvm::TargetTransformInfo::getCastInstrCost(), llvm::Type::getContext(), llvm::Intrinsic::getDeclaration(), llvm::TargetTransformInfo::getIntrinsicInstrCost(), I, llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_FPToSI(), llvm::PatternMatch::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().
|
static |
Definition at line 291 of file AggressiveInstCombine.cpp.
References llvm::IRBuilderBase::CreateCall(), llvm::dbgs(), llvm::Intrinsic::getDeclaration(), llvm::Type::getScalarSizeInBits(), llvm::APInt::getSplat(), I, llvm::Type::isIntOrIntVectorTy(), LLVM_DEBUG, llvm::PatternMatch::m_And(), llvm::PatternMatch::m_c_Add(), llvm::PatternMatch::m_Deferred(), llvm::PatternMatch::m_LShr(), llvm::PatternMatch::m_Mul(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_SpecificInt(), llvm::PatternMatch::m_Sub(), llvm::PatternMatch::m_Value(), MaskShift(), and llvm::PatternMatch::match().
Referenced by foldUnusualPatterns().
|
static |
Definition at line 529 of file AggressiveInstCombine.cpp.
References B, GEP, llvm::ConstantDataSequential::getElementAsInteger(), llvm::GlobalVariable::getInitializer(), llvm::LoadInst::getPointerOperand(), llvm::Type::getScalarSizeInBits(), llvm::Value::getType(), llvm::GlobalVariable::hasInitializer(), I, llvm::GlobalVariable::isConstant(), isCTTZTable(), llvm::Type::isIntegerTy(), llvm::Log2_32(), llvm::PatternMatch::m_c_And(), llvm::PatternMatch::m_ConstantInt(), llvm::PatternMatch::m_Deferred(), llvm::PatternMatch::m_LShr(), llvm::PatternMatch::m_Mul(), llvm::PatternMatch::m_Neg(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_ZeroInt(), llvm::PatternMatch::m_ZExtOrSelf(), llvm::PatternMatch::match(), llvm::Value::replaceAllUsesWith(), and Select.
Referenced by foldUnusualPatterns().
|
static |
Referenced by foldLoadsRecursive().
|
static |
Referenced by foldMemChr().
|
static |