AggressiveInstCombine.cpp File Reference

#include "llvm/Transforms/AggressiveInstCombine/AggressiveInstCombine.h"
#include "AggressiveInstCombineInternal.h"
#include "llvm-c/Initialization.h"
#include "llvm-c/Transforms/AggressiveInstCombine.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/BasicAliasAnalysis.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/LegacyPassManager.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Transforms/Utils/BuildLibCalls.h"
#include "llvm/Transforms/Utils/Local.h"

Include dependency graph for AggressiveInstCombine.cpp:

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...

Namespaces
	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")
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. More...
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. More...
static bool	foldAnyOrAllBitsSet (Instruction &I)
	Match patterns that correspond to "any-bits-set" and "all-bits-set". More...
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. More...
static bool	foldSqrt (Instruction &I, TargetTransformInfo &TTI, TargetLibraryInfo &TLI)
	Try to replace a mathlib call to sqrt with the LLVM intrinsic. More...
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)
static bool	foldUnusualPatterns (Function &F, DominatorTree &DT, TargetTransformInfo &TTI, TargetLibraryInfo &TLI, AliasAnalysis &AA)
	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. More...
static bool	runImpl (Function &F, AssumptionCache &AC, TargetTransformInfo &TTI, TargetLibraryInfo &TLI, DominatorTree &DT, AliasAnalysis &AA)
	This is the entry point for all transforms. More...
	INITIALIZE_PASS_BEGIN (AggressiveInstCombinerLegacyPass, "aggressive-instcombine", "Combine pattern based expressions", false, false) INITIALIZE_PASS_END(AggressiveInstCombinerLegacyPass
void	LLVMInitializeAggressiveInstCombiner (LLVMPassRegistryRef R)
void	LLVMAddAggressiveInstCombinerPass (LLVMPassManagerRef PM)
	See llvm::createAggressiveInstCombinerPass function. More...

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."))
aggressive	instcombine
aggressive Combine pattern based	expressions
aggressive Combine pattern based	false

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "aggressive-instcombine"

Definition at line 44 of file AggressiveInstCombine.cpp.

Function Documentation

foldAnyOrAllBitsSet()

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

References llvm::And, Builder, MaskOps::FoundAnd1, llvm::ConstantInt::get(), 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(), llvm::BitmaskEnumDetail::Mask(), MaskOps::Mask, llvm::PatternMatch::match(), matchAndOrChain(), and MaskOps::Root.

Referenced by foldUnusualPatterns().

foldConsecutiveLoads()

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

static

Definition at line 789 of file AggressiveInstCombine.cpp.

References LoadOps::AATags, llvm::ARMBuildAttrs::Allowed, llvm::TargetTransformInfo::allowsMisalignedMemoryAccesses(), Builder, DL, foldLoadsRecursive(), LoadOps::FoundRoot, llvm::IntegerType::get(), llvm::Value::getContext(), I, llvm::TargetTransformInfo::isTypeLegal(), LoadOps::LoadSize, LoadOps::Root, llvm::Instruction::setAAMetadata(), LoadOps::Shift, llvm::Value::takeName(), and LoadOps::ZextType.

Referenced by foldUnusualPatterns().

foldGuardedFunnelShift()

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

References assert(), Builder, llvm::DominatorTree::dominates(), F, llvm::Intrinsic::getDeclaration(), llvm::BasicBlock::getFirstInsertionPt(), llvm::PHINode::getIncomingBlock(), llvm::Instruction::getModule(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::Type::getScalarSizeInBits(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), I, llvm::CmpInst::ICMP_EQ, llvm::isGuaranteedNotToBePoison(), llvm::isPowerOf2_32(), llvm::PatternMatch::m_Br(), llvm::PatternMatch::m_c_Or(), llvm::PatternMatch::m_ICmp(), llvm::PatternMatch::m_LShr(), llvm::PatternMatch::m_OneUse(), llvm::PatternMatch::m_Shl(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_SpecificBB(), llvm::PatternMatch::m_SpecificInt(), llvm::PatternMatch::m_Sub(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_ZeroInt(), llvm::PatternMatch::match(), matchFunnelShift(), llvm::Intrinsic::not_intrinsic, PHI, llvm::Value::replaceAllUsesWith(), and std::swap().

Referenced by foldUnusualPatterns().

foldLoadsRecursive()

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

static

Definition at line 657 of file AggressiveInstCombine.cpp.

References LoadOps::AATags, llvm::Instruction::comesBefore(), llvm::AAMDNodes::concat(), DL, LoadOps::FoundRoot, llvm::IntegerType::get(), llvm::MemoryLocation::get(), llvm::Instruction::getAAMetadata(), llvm::Value::getContext(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::Instruction::getParent(), llvm::LoadInst::getPointerAddressSpace(), llvm::LoadInst::getPointerOperand(), llvm::Type::getPrimitiveSizeInBits(), llvm::Value::getType(), llvm::APInt::getZExtValue(), llvm::isModSet(), llvm::isPowerOf2_64(), llvm::LoadInst::isSimple(), L2, 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, LoadOps::Root, LoadOps::Shift, llvm::Value::stripAndAccumulateConstantOffsets(), std::swap(), X, and LoadOps::ZextType.

Referenced by foldConsecutiveLoads().

foldSqrt()

static bool foldSqrt ( Instruction &  I, TargetTransformInfo &  TTI, TargetLibraryInfo &  TLI  )

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

References Arg, Builder, llvm::CannotBeOrderedLessThanZero(), llvm::Intrinsic::getDeclaration(), llvm::TargetLibraryInfo::getLibFunc(), llvm::TargetTransformInfo::haveFastSqrt(), I, llvm::isLibFuncEmittable(), and M.

Referenced by foldUnusualPatterns().

foldUnusualPatterns()

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

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

References BB, DL, F, foldAnyOrAllBitsSet(), foldConsecutiveLoads(), foldGuardedFunnelShift(), foldSqrt(), I, llvm::DominatorTree::isReachableFromEntry(), llvm::make_early_inc_range(), llvm::reverse(), llvm::SimplifyInstructionsInBlock(), tryToFPToSat(), tryToRecognizePopCount(), and tryToRecognizeTableBasedCttz().

Referenced by runImpl().

INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN	(	AggressiveInstCombinerLegacyPass	,
		"aggressive-instcombine"	,
		"Combine pattern based expressions"	,
		false	,
		false
	)

isCTTZTable()

static bool isCTTZTable ( const ConstantDataArray &  Table, uint64_t  Mul, uint64_t  Shift, uint64_t  InputBits  )

static

Definition at line 483 of file AggressiveInstCombine.cpp.

References llvm::APInt::getBitsSetFrom(), llvm::ConstantDataSequential::getElementAsInteger(), llvm::ConstantDataSequential::getNumElements(), i, llvm::BitmaskEnumDetail::Mask(), Mul, and Shift.

Referenced by tryToRecognizeTableBasedCttz().

matchAndOrChain()

static 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 228 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, MaskOps::Root, llvm::APInt::setBit(), and llvm::APInt::uge().

Referenced by foldAnyOrAllBitsSet().

runImpl()

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

static

This is the entry point for all transforms.

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

Definition at line 879 of file AggressiveInstCombine.cpp.

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

Referenced by llvm::AggressiveInstCombinePass::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()

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

References Builder, llvm::IntegerType::get(), llvm::VectorType::get(), llvm::TargetTransformInfo::getCastInstrCost(), llvm::Type::getContext(), llvm::Intrinsic::getDeclaration(), llvm::TargetTransformInfo::getIntrinsicInstrCost(), I, llvm::tgtok::In, 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, llvm::APIntOps::smax(), llvm::APIntOps::smin(), and llvm::TargetTransformInfo::TCK_RecipThroughput.

Referenced by foldUnusualPatterns().

tryToRecognizePopCount()

static bool tryToRecognizePopCount ( Instruction &  I )

static

Definition at line 318 of file AggressiveInstCombine.cpp.

References Builder, 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(), and llvm::PatternMatch::match().

Referenced by foldUnusualPatterns().

tryToRecognizeTableBasedCttz()

static bool tryToRecognizeTableBasedCttz ( Instruction &  I )

static

Definition at line 558 of file AggressiveInstCombine.cpp.

References B, GEP, llvm::ConstantInt::get(), 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 llvm::MCID::Select.

Referenced by foldUnusualPatterns().

Variable Documentation

expressions

aggressive Combine pattern based expressions

Definition at line 939 of file AggressiveInstCombine.cpp.

false

aggressive Combine pattern based false

Definition at line 939 of file AggressiveInstCombine.cpp.

instcombine

aggressive instcombine

Definition at line 938 of file AggressiveInstCombine.cpp.

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."))

static

Referenced by foldLoadsRecursive().