AggressiveInstCombine.cpp File Reference

#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/Instruction.h"
#include "llvm/IR/MDBuilder.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/ProfDataUtils.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.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	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...

Namespaces
namespace	llvm
	This is an optimization pass for GlobalISel generic memory operations.

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")
	STATISTIC (NumSelectCTTZFolded, "Number of select-based split cttz patterns folded")
	STATISTIC (NumSelectCTLZFolded, "Number of select-based split ctlz patterns folded")
static bool	foldSelectSplitCTTZ (Instruction &I, Value *LoTrunc, Value *HiResult, Value *LoResult, Type *HalfTy)
	Try to fold a select-based split cttz pattern into a single full-width cttz.
static bool	foldSelectSplitCTLZ (Instruction &I, Value *HiPart, Value *LoResult, Value *HiResult, Type *HalfTy)
	Same as foldSelectSplitCTTZ but for leading zeros (ctlz).
static bool	foldSelectSplitCTLZCTTZ (Instruction &I)
	Common entry point for folding select-based split cttz/ctlz patterns.
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 void	replaceWithPopCount (Instruction &I, Value *Root)
	Helper function to replace an instruction with a popcount intrinsic.
static Value *	matchPopCountBytes (Value *V, unsigned Len, const DataLayout &DL)
static bool	tryToRecognizePopCount (Instruction &I)
static bool	tryToRecognizePopCount1 (Instruction &I)
static bool	tryToRecognizePopCount2n3 (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	isLog2Table (Constant *Table, const APInt &Mul, const APInt &Shift, Type *AccessTy, unsigned InputBits, const APInt &GEPIdxFactor, const DataLayout &DL)
static bool	tryToRecognizeTableBasedLog2 (Instruction &I, const DataLayout &DL, TargetTransformInfo &TTI)
static bool	foldLoadsRecursive (Value *V, LoadOps &LOps, const DataLayout &DL, AliasAnalysis &AA, bool IsRoot=false)
static bool	foldConsecutiveLoads (Instruction &I, const DataLayout &DL, TargetTransformInfo &TTI, AliasAnalysis &AA, const DominatorTree &DT)
static std::optional< PartStore >	matchPartStore (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 Value *	optimizeShiftInOrChain (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, 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	foldMulHigh (Instruction &I)
	Match high part of long multiplication.
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."))

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "aggressive-instcombine"

Definition at line 44 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 415 of file AggressiveInstCombine.cpp.

References 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_Trunc(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), matchAndOrChain(), and X.

Referenced by foldUnusualPatterns().

foldConsecutiveLoads()

bool foldConsecutiveLoads ( Instruction & I, const DataLayout & DL, TargetTransformInfo & TTI, AliasAnalysis & AA, const DominatorTree & DT )

static

Definition at line 1390 of file AggressiveInstCombine.cpp.

References LoadOps::AATags, DL, llvm::DominatorTree::dominates(), llvm::CallingConv::Fast, foldLoadsRecursive(), LoadOps::FoundRoot, llvm::IntegerType::get(), llvm::Value::getType(), I, llvm::isa(), LoadOps::LoadSize, LoadOps::Root, LoadOps::RootInsert, llvm::Instruction::setAAMetadata(), LoadOps::Shift, llvm::Value::stripAndAccumulateConstantOffsets(), llvm::Value::takeName(), and LoadOps::ZextType.

Referenced by foldICmpOrChain(), and foldUnusualPatterns().

foldConsecutiveStores()

bool foldConsecutiveStores ( BasicBlock & BB, const DataLayout & DL, TargetTransformInfo & TTI, AliasAnalysis & AA )

static

Definition at line 1573 of file AggressiveInstCombine.cpp.

References llvm::SmallVectorImpl< T >::clear(), DL, llvm::SmallVectorTemplateCommon< T, typename >::empty(), llvm::MemoryLocation::getBeforeOrAfter(), llvm::BatchAAResults::getModRefInfo(), I, llvm::isModOrRefSet(), llvm::make_early_inc_range(), matchPartStore(), mergePartStores(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by foldUnusualPatterns().

foldGuardedFunnelShift()

bool foldGuardedFunnelShift ( Instruction & I, const DominatorTree & DT )

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 231 of file AggressiveInstCombine.cpp.

References assert(), llvm::cast(), llvm::DominatorTree::dominates(), 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::MIPatternMatch::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::MIPatternMatch::m_ZeroInt(), llvm::PatternMatch::match(), matchFunnelShift(), llvm::Intrinsic::not_intrinsic, and std::swap().

Referenced by foldUnusualPatterns().

foldICmpOrChain()

bool foldICmpOrChain ( Instruction & I, const DataLayout & DL, TargetTransformInfo & TTI, AliasAnalysis & AA, const DominatorTree & DT )

static

Definition at line 1642 of file AggressiveInstCombine.cpp.

References DL, llvm::dyn_cast(), foldConsecutiveLoads(), I, llvm::ICmpInst::isEquality(), llvm::PatternMatch::m_ICmp(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_Zero(), llvm::PatternMatch::match(), and optimizeShiftInOrChain().

Referenced by foldUnusualPatterns().

foldLibCalls()

bool foldLibCalls ( Instruction & I, TargetTransformInfo & TTI, TargetLibraryInfo & TLI, AssumptionCache & AC, DominatorTree & DT, const DataLayout & DL, bool & MadeCFGChange )

static

Definition at line 2036 of file AggressiveInstCombine.cpp.

References DL, llvm::dyn_cast(), foldMemChr(), foldSqrt(), llvm::TargetLibraryInfo::getLibFunc(), I, and llvm::isLibFuncEmittable().

Referenced by foldUnusualPatterns().

foldLoadsRecursive()

bool foldLoadsRecursive ( Value * V, LoadOps & LOps, const DataLayout & DL, AliasAnalysis & AA, bool IsRoot = false )

static

Definition at line 1241 of file AggressiveInstCombine.cpp.

References LoadOps::AATags, llvm::AAMDNodes::concat(), DL, llvm::dyn_cast(), foldLoadsRecursive(), LoadOps::FoundRoot, llvm::IntegerType::get(), llvm::MemoryLocation::get(), llvm::Instruction::getAAMetadata(), llvm::Value::getContext(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::LoadInst::getPointerAddressSpace(), llvm::LoadInst::getPointerOperand(), llvm::Type::getPrimitiveSizeInBits(), llvm::Value::getType(), llvm::isModSet(), llvm::LoadInst::isSimple(), LoadOps::LoadSize, llvm::PatternMatch::m_c_Or(), llvm::PatternMatch::m_Instruction(), llvm::MIPatternMatch::m_OneUse(), llvm::PatternMatch::m_ShlOrSelf(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_ZExt(), llvm::make_range(), llvm::PatternMatch::match(), MaxInstrsToScan, llvm::LocationSize::precise(), 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().

foldMemChr()

bool foldMemChr ( CallInst * Call, DomTreeUpdater * DTU, const DataLayout & DL )

static

Convert memchr with a small constant string into a switch.

Definition at line 1957 of file AggressiveInstCombine.cpp.

References llvm::PHINode::addIncoming(), llvm::GenericDomTreeUpdater< DerivedT, DomTreeT, PostDomTreeT >::applyUpdates(), llvm::sampleprof::Base, llvm::BasicBlock::begin(), Call, llvm::BasicBlock::Create(), llvm::PHINode::Create(), llvm::IRBuilderBase::CreateBr(), llvm::IRBuilderBase::CreateInBoundsPtrAdd(), llvm::IRBuilderBase::CreatePHI(), llvm::IRBuilderBase::CreateSwitch(), llvm::IRBuilderBase::CreateTrunc(), DEBUG_TYPE, DL, llvm::dyn_cast(), llvm::Instruction::eraseFromParent(), llvm::getConstantStringInfo(), llvm::IRBuilderBase::getInt8Ty(), llvm::Constant::getNullValue(), llvm::BasicBlock::getParent(), llvm::BasicBlock::getTerminator(), I, llvm::DominatorTreeBase< BasicBlock, false >::Insert, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::isa(), MemChrInlineThreshold, N, PHI, llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::IRBuilderBase::SetCurrentDebugLocation(), llvm::setExplicitlyUnknownBranchWeightsIfProfiled(), llvm::IRBuilderBase::SetInsertPoint(), and llvm::SplitBlock().

Referenced by foldLibCalls().

foldMulHigh()

bool foldMulHigh ( Instruction & I )

static

Match high part of long multiplication.

Considering a multiply made up of high and low parts, we can split the multiply into: x * y == (xh*T + xl) * (yh*T + yl) where xh == x>>32 and xl == x & 0xffffffff. T = 2^32. This expands to xh*yh*T*T + xh*yl*T + xl*yh*T + xl*yl which can be drawn as [ xh*yh ] [ xh*yl ] [ xl*yh ] [ xl*yl ] We are looking for the "high" half, which is xh*yh + xh*yl>>32 + xl*yh>>32 + some carrys. The carry makes this difficult and there are multiple ways of representing it. The ones we attempt to support here are: Carry: xh*yh + carry + lowsum carry = lowsum < xh*yl ? 0x1000000 : 0 lowsum = xh*yl + xl*yh + (xl*yl>>32) Ladder: xh*yh + c2>>32 + c3>>32 c2 = xh*yl + (xl*yl>>32); c3 = c2&0xffffffff + xl*yh or c2 = (xl*yh&0xffffffff) + xh*yl + (xl*yl>>32); c3 = xl*yh Carry4: xh*yh + carry + crosssum>>32 + (xl*yl + crosssum&0xffffffff) >> 32 crosssum = xh*yl + xl*yh carry = crosssum < xh*yl ? 0x1000000 : 0 Ladder4: xh*yh + (xl*yh)>>32 + (xh*yl)>>32 + low>>32; low = (xl*yl)>>32 + (xl*yh)&0xffffffff + (xh*yl)&0xffffffff

They all start by matching xh*yh + 2 or 3 other operands. The bottom of the tree is xh*yh, xh*yl, xl*yh and xl*yl.

Ladder4: xh*yh + (xl*yh)>>32 + (xh+yl)>>32 + low>>32; low = (xl*yl)>>32 + (xl*yh)&0xffffffff + (xh*yl)&0xffffffff

Definition at line 2109 of file AggressiveInstCombine.cpp.

References A(), B(), llvm::BitWidth, llvm::CallingConv::C, llvm::dbgs(), llvm::APInt::getLowBitsSet(), llvm::APInt::getOneBitSet(), llvm::Type::getWithNewBitWidth(), llvm::Value::hasNUsesOrMore(), llvm::Value::hasOneUse(), High, I, llvm::CmpInst::ICMP_ULT, LLVM_DEBUG, llvm::Low, llvm::PatternMatch::m_Add(), llvm::PatternMatch::m_And(), llvm::PatternMatch::m_c_Add(), llvm::PatternMatch::m_c_Mul(), llvm::PatternMatch::m_Instruction(), llvm::PatternMatch::m_LShr(), llvm::PatternMatch::m_Mul(), llvm::MIPatternMatch::m_OneUse(), llvm::PatternMatch::m_Select(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_SpecificICmp(), llvm::PatternMatch::m_SpecificInt(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_Zero(), llvm::PatternMatch::match(), Mul, std::swap(), llvm::Value::takeName(), X, and Y.

Referenced by foldUnusualPatterns().

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 1712 of file AggressiveInstCombine.cpp.

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

Referenced by foldUnusualPatterns().

foldSelectSplitCTLZ()

bool foldSelectSplitCTLZ ( Instruction & I, Value * HiPart, Value * LoResult, Value * HiResult, Type * HalfTy )

static

Same as foldSelectSplitCTTZ but for leading zeros (ctlz).

shr = lshr iN val, N/2 hi = trunc iN shr to i(N/2) cmp = icmp eq i(N/2) hi, 0 (or icmp eq iN shr, 0) lo = trunc iN val to i(N/2) ctlz_lo = call i(N/2) @llvm.ctlz.i(N/2)(i(N/2) lo, ...) lo_plus = add/or_disjoint i(N/2) ctlz_lo, N/2 ctlz_hi = call i(N/2) @llvm.ctlz.i(N/2)(i(N/2) hi, ...) result = select i1 cmp, i(N/2) lo_plus, i(N/2) ctlz_hi --> ctlz_wide = call iN @llvm.ctlz.iN(iN val, i1 false) result = trunc iN ctlz_wide to i(N/2)

Alive proof (for i64/i32): https://alive2.llvm.org/ce/z/WfQepH

Definition at line 147 of file AggressiveInstCombine.cpp.

References llvm::Type::getIntegerBitWidth(), llvm::Value::getType(), I, llvm::Type::isIntegerTy(), llvm::PatternMatch::m_AddLike(), llvm::PatternMatch::m_Ctlz(), llvm::PatternMatch::m_LShr(), llvm::MIPatternMatch::m_OneUse(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_SpecificInt(), llvm::PatternMatch::m_Trunc(), llvm::PatternMatch::m_Value(), and llvm::PatternMatch::match().

Referenced by foldSelectSplitCTLZCTTZ().

foldSelectSplitCTLZCTTZ()

bool foldSelectSplitCTLZCTTZ ( Instruction & I )

static

Common entry point for folding select-based split cttz/ctlz patterns.

Performs the initial select and type matching shared by both transforms, then delegates to foldSelectSplitCTTZ and foldSelectSplitCTLZ.

Definition at line 199 of file AggressiveInstCombine.cpp.

References Cond, foldSelectSplitCTLZ(), foldSelectSplitCTTZ(), I, llvm::CmpInst::ICMP_NE, llvm::ICmpInst::isEquality(), llvm::PatternMatch::m_ICmp(), llvm::PatternMatch::m_Select(), llvm::PatternMatch::m_Value(), llvm::MIPatternMatch::m_ZeroInt(), llvm::PatternMatch::match(), and std::swap().

Referenced by foldUnusualPatterns().

foldSelectSplitCTTZ()

bool foldSelectSplitCTTZ ( Instruction & I, Value * LoTrunc, Value * HiResult, Value * LoResult, Type * HalfTy )

static

Try to fold a select-based split cttz pattern into a single full-width cttz.

lo = trunc iN val to i(N/2) cmp = icmp eq i(N/2) lo, 0 shr = lshr iN val, N/2 hi = trunc iN shr to i(N/2) cttz_hi = call i(N/2) @llvm.cttz.i(N/2)(i(N/2) hi, ...) hi_plus = add/or_disjoint i(N/2) cttz_hi, N/2 cttz_lo = call i(N/2) @llvm.cttz.i(N/2)(i(N/2) lo, ...) result = select i1 cmp, i(N/2) hi_plus, i(N/2) cttz_lo --> cttz_wide = call iN @llvm.cttz.iN(iN val, i1 false) result = trunc iN cttz_wide to i(N/2) Alive proof (for i64/i32): https://alive2.llvm.org/ce/z/-s14-s

Definition at line 90 of file AggressiveInstCombine.cpp.

References llvm::Type::getIntegerBitWidth(), llvm::Value::getType(), I, llvm::Type::isIntegerTy(), llvm::PatternMatch::m_AddLike(), llvm::PatternMatch::m_Cttz(), llvm::PatternMatch::m_LShr(), llvm::MIPatternMatch::m_OneUse(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_SpecificInt(), llvm::PatternMatch::m_Trunc(), llvm::PatternMatch::m_Value(), and llvm::PatternMatch::match().

Referenced by foldSelectSplitCTLZCTTZ().

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 850 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 2405 of file AggressiveInstCombine.cpp.

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

Referenced by runImpl().

getStrideAndModOffsetOfGEP()

std::pair< APInt, APInt > getStrideAndModOffsetOfGEP ( Value * PtrOp, const DataLayout & DL )

static

Definition at line 1671 of file AggressiveInstCombine.cpp.

References DL, llvm::dyn_cast(), GEP, llvm::APInt::getOneBitSet(), llvm::Value::getType(), llvm::APIntOps::GreatestCommonDivisor(), llvm::isa(), llvm::APInt::isNegative(), and llvm::APInt::srem().

Referenced by foldPatternedLoads().

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

Definition at line 882 of file AggressiveInstCombine.cpp.

References llvm::CallingConv::C, llvm::ConstantFoldLoadFromConst(), DL, llvm::dyn_cast_or_null(), llvm::APInt::getOneBitSet(), and Mul.

Referenced by tryToRecognizeTableBasedCttz().

isLog2Table()

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

static

Definition at line 1045 of file AggressiveInstCombine.cpp.

References llvm::CallingConv::C, llvm::ConstantFoldLoadFromConst(), DL, llvm::dyn_cast_or_null(), llvm::APInt::getLowBitsSet(), llvm::APInt::isZero(), and Mul.

Referenced by tryToRecognizeTableBasedLog2().

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 369 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()

std::optional< PartStore > matchPartStore ( Instruction & I, const DataLayout & DL )

static

Definition at line 1466 of file AggressiveInstCombine.cpp.

References DL, llvm::dyn_cast(), llvm::Type::getPrimitiveSizeInBits(), llvm::Value::getType(), I, llvm::Type::isIntegerTy(), llvm::PatternMatch::m_LShrOrSelf(), llvm::PatternMatch::m_Trunc(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), and llvm::Value::stripAndAccumulateConstantOffsets().

Referenced by foldConsecutiveStores().

matchPopCountBytes()

Value * matchPopCountBytes ( Value * V, unsigned Len, const DataLayout & DL )

static

Definition at line 487 of file AggressiveInstCombine.cpp.

References DL, llvm::APInt::getSplat(), llvm::APInt::isSubsetOf(), llvm::PatternMatch::m_Add(), llvm::PatternMatch::m_And(), llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_c_Add(), llvm::PatternMatch::m_Deferred(), llvm::PatternMatch::m_LShr(), llvm::PatternMatch::m_Mul(), llvm::PatternMatch::m_SpecificInt(), llvm::PatternMatch::m_Sub(), llvm::PatternMatch::m_Value(), llvm::MaskedValueIsZero(), and llvm::PatternMatch::match().

Referenced by tryToRecognizePopCount(), and tryToRecognizePopCount2n3().

mergeConsecutivePartStores()

bool mergeConsecutivePartStores ( ArrayRef< PartStore > Parts, unsigned Width, const DataLayout & DL, TargetTransformInfo & TTI )

static

Definition at line 1490 of file AggressiveInstCombine.cpp.

References llvm::AAMDNodes::concat(), DL, llvm::drop_begin(), llvm::CallingConv::Fast, llvm::First, llvm::ArrayRef< T >::front(), llvm::Type::getIntNTy(), llvm::DebugLoc::getMergedLocations(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SmallVectorImpl< T >::reserve(), and llvm::ArrayRef< T >::size().

Referenced by mergePartStores().

mergePartStores()

bool mergePartStores ( SmallVectorImpl< PartStore > & Parts, const DataLayout & DL, TargetTransformInfo & TTI )

static

Definition at line 1540 of file AggressiveInstCombine.cpp.

References llvm::ArrayRef(), Changed, DL, llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::First, mergeConsecutivePartStores(), llvm::SmallVectorTemplateCommon< T, typename >::size(), and llvm::sort().

Referenced by foldConsecutiveStores().

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 1614 of file AggressiveInstCombine.cpp.

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

Referenced by foldICmpOrChain(), and optimizeShiftInOrChain().

replaceWithPopCount()

void replaceWithPopCount ( Instruction & I, Value * Root )

static

Helper function to replace an instruction with a popcount intrinsic.

This creates the ctpop intrinsic with an optional truncation appended at the end, and replaces all uses of the instruction.

Definition at line 465 of file AggressiveInstCombine.cpp.

References assert(), llvm::dbgs(), llvm::Type::getScalarSizeInBits(), llvm::Value::getType(), I, and LLVM_DEBUG.

Referenced by tryToRecognizePopCount(), tryToRecognizePopCount1(), and tryToRecognizePopCount2n3().

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 2456 of file AggressiveInstCombine.cpp.

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

STATISTIC() [1/6]

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

STATISTIC() [2/6]

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

STATISTIC() [3/6]

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

STATISTIC() [4/6]

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

STATISTIC() [5/6]

STATISTIC	(	NumSelectCTLZFolded	,
		"Number of select-based split ctlz patterns folded"	)

STATISTIC() [6/6]

STATISTIC	(	NumSelectCTTZFolded	,
		"Number of select-based split cttz patterns folded"	)

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 795 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()

bool tryToRecognizePopCount ( Instruction & I )

static

Definition at line 546 of file AggressiveInstCombine.cpp.

References llvm::APInt::getSplat(), I, llvm::PatternMatch::m_Mul(), llvm::PatternMatch::m_SpecificInt(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), matchPopCountBytes(), and replaceWithPopCount().

Referenced by foldUnusualPatterns().

tryToRecognizePopCount1()

bool tryToRecognizePopCount1 ( Instruction & I )

static

Definition at line 600 of file AggressiveInstCombine.cpp.

References llvm::APInt::getLowBitsSet(), llvm::APInt::getSplat(), I, llvm::isPowerOf2_32(), llvm::APInt::isSubsetOf(), llvm::APInt::isZero(), llvm::PatternMatch::m_And(), llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_c_Add(), llvm::PatternMatch::m_Deferred(), llvm::PatternMatch::m_LShr(), llvm::PatternMatch::m_SpecificInt(), llvm::PatternMatch::m_Value(), llvm::MaskedValueIsZero(), llvm::PatternMatch::match(), and replaceWithPopCount().

Referenced by foldUnusualPatterns().

tryToRecognizePopCount2n3()

bool tryToRecognizePopCount2n3 ( Instruction & I )

static

Definition at line 720 of file AggressiveInstCombine.cpp.

References llvm::APInt::countTrailingOnes(), llvm::APInt::getActiveBits(), llvm::Type::getScalarSizeInBits(), llvm::Value::getType(), I, llvm::isPowerOf2_32(), llvm::Log2_32(), llvm::PatternMatch::m_And(), llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_c_Add(), llvm::PatternMatch::m_Deferred(), llvm::PatternMatch::m_LShr(), llvm::MIPatternMatch::m_OneUse(), llvm::PatternMatch::m_SpecificInt(), llvm::PatternMatch::m_Trunc(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), matchPopCountBytes(), and replaceWithPopCount().

Referenced by foldUnusualPatterns().

tryToRecognizeTableBasedCttz()

bool tryToRecognizeTableBasedCttz ( Instruction & I, const DataLayout & DL )

static

Definition at line 957 of file AggressiveInstCombine.cpp.

References B(), llvm::cast(), llvm::ConstantFoldLoadFromConst(), llvm::MDBuilder::createUnlikelyBranchWeights(), DL, llvm::dyn_cast(), llvm::MapVector< KeyT, ValueT, MapType, VectorType, N >::front(), GEP, llvm::APInt::getAllOnes(), llvm::GlobalVariable::getInitializer(), llvm::LoadInst::getPointerOperand(), llvm::Type::getScalarSizeInBits(), llvm::Value::getType(), llvm::ConstantInt::getZExtValue(), llvm::GlobalVariable::hasInitializer(), I, llvm::GlobalVariable::isConstant(), isCTTZTable(), llvm::Type::isIntegerTy(), llvm::PatternMatch::m_And(), llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_c_And(), llvm::PatternMatch::m_CastOrSelf(), llvm::PatternMatch::m_Deferred(), llvm::PatternMatch::m_LShr(), llvm::PatternMatch::m_Mul(), llvm::MIPatternMatch::m_Neg(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), llvm::ProfcheckDisableMetadataFixes, llvm::Value::replaceAllUsesWith(), Select, and llvm::MapVector< KeyT, ValueT, MapType, VectorType, N >::size().

Referenced by foldUnusualPatterns().

tryToRecognizeTableBasedLog2()

bool tryToRecognizeTableBasedLog2 ( Instruction & I, const DataLayout & DL, TargetTransformInfo & TTI )

static

Definition at line 1125 of file AggressiveInstCombine.cpp.

References B(), llvm::cast(), llvm::ConstantFoldLoadFromConst(), llvm::MDBuilder::createUnlikelyBranchWeights(), DL, llvm::dyn_cast(), llvm::MapVector< KeyT, ValueT, MapType, VectorType, N >::front(), GEP, llvm::PoisonValue::get(), llvm::GlobalVariable::getInitializer(), llvm::LoadInst::getPointerOperand(), llvm::Value::getType(), llvm::GlobalVariable::hasInitializer(), I, llvm::GlobalVariable::isConstant(), llvm::Type::isIntegerTy(), isLog2Table(), llvm::Log2_32(), llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_c_Or(), llvm::PatternMatch::m_CastOrSelf(), llvm::PatternMatch::m_Deferred(), llvm::PatternMatch::m_LShr(), llvm::PatternMatch::m_Mul(), llvm::PatternMatch::m_SpecificInt(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), llvm::ProfcheckDisableMetadataFixes, llvm::Value::replaceAllUsesWith(), Select, llvm::MapVector< KeyT, ValueT, MapType, VectorType, N >::size(), llvm::Sub, llvm::TargetTransformInfo::TCC_Basic, llvm::TargetTransformInfo::TCK_SizeAndLatency, X, and Y.

Referenced by foldUnusualPatterns().

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

Referenced by foldLoadsRecursive(), and isMemModifiedBetween().

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