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/BasicAliasAnalysis.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/TargetLibraryInfo.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/LegacyPassManager.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.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...

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	foldUnusualPatterns (Function &F, DominatorTree &DT)
	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, TargetLibraryInfo &TLI, DominatorTree &DT)
	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
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 38 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 265 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().

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 76 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, llvm::Value::replaceAllUsesWith(), and std::swap().

Referenced by foldUnusualPatterns().

foldUnusualPatterns()

static bool foldUnusualPatterns ( Function &  F, DominatorTree &  DT  )

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

References BB, F, foldAnyOrAllBitsSet(), foldGuardedFunnelShift(), I, llvm::DominatorTree::isReachableFromEntry(), llvm::make_range(), llvm::SimplifyInstructionsInBlock(), and tryToRecognizePopCount().

Referenced by runImpl().

INITIALIZE_PASS_BEGIN()

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

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 219 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, TargetLibraryInfo &  TLI, DominatorTree &  DT  )

static

This is the entry point for all transforms.

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

Definition at line 397 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"
	)

tryToRecognizePopCount()

static bool tryToRecognizePopCount ( Instruction &  I )

static

Definition at line 309 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().

Variable Documentation

expressions

aggressive Combine pattern based expressions

Definition at line 444 of file AggressiveInstCombine.cpp.

false

aggressive Combine pattern based false

Definition at line 444 of file AggressiveInstCombine.cpp.

instcombine

aggressive instcombine

Definition at line 443 of file AggressiveInstCombine.cpp.