#include "llvm/CodeGen/SelectionDAG.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetLowering.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetOptions.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetSubtargetInfo.h"
#include <algorithm>

Include dependency graph for DAGCombiner.cpp:

Classes
struct	LoadedSliceSorter
	Sorts LoadedSlice according to their offset. More...

struct	BaseIndexOffset

struct	MemOpLink

struct	ConsecutiveMemoryChainSorter
	Sorts store nodes in a link according to their offset from a shared. More...

Macros
#define	DEBUG_TYPE "dagcombine"

Functions
	STATISTIC (NodesCombined,"Number of dag nodes combined")

	STATISTIC (PreIndexedNodes,"Number of pre-indexed nodes created")

	STATISTIC (PostIndexedNodes,"Number of post-indexed nodes created")

	STATISTIC (OpsNarrowed,"Number of load/op/store narrowed")

	STATISTIC (LdStFP2Int,"Number of fp load/store pairs transformed to int")

	STATISTIC (SlicedLoads,"Number of load sliced")

static char	isNegatibleForFree (SDValue Op, bool LegalOperations, const TargetLowering &TLI, const TargetOptions *Options, unsigned Depth=0)

static SDValue	GetNegatedExpression (SDValue Op, SelectionDAG &DAG, bool LegalOperations, unsigned Depth=0)

static bool	isSetCCEquivalent (SDValue N, SDValue &LHS, SDValue &RHS, SDValue &CC)

static bool	isOneUseSetCC (SDValue N)

static SDValue	getInputChainForNode (SDNode *N)

static SDValue	combineShlAddConstant (SDLoc DL, SDValue N0, SDValue N1, SelectionDAG &DAG)

static SDValue	tryFoldToZero (SDLoc DL, const TargetLowering &TLI, EVT VT, SelectionDAG &DAG, bool LegalOperations, bool LegalTypes)

static bool	isConstantSplatVector (SDNode *N, APInt &SplatValue)

static bool	isBSwapHWordElement (SDValue N, SmallVectorImpl< SDNode * > &Parts)

static bool	MatchRotateHalf (SDValue Op, SDValue &Shift, SDValue &Mask)
	MatchRotateHalf - Match "(X shl/srl V1) & V2" where V2 may not be present. More...

static std::pair< SDValue, SDValue >	SplitVSETCC (const SDNode *N, SelectionDAG &DAG)

static bool	ExtendUsesToFormExtLoad (SDNode N, SDValue N0, unsigned ExtOpc, SmallVectorImpl< SDNode > &ExtendNodes, const TargetLowering &TLI)

static bool	isTruncateOf (SelectionDAG &DAG, SDValue N, SDValue &Op, APInt &KnownZero)

static SDNode *	getBuildPairElt (SDNode *N, unsigned i)

static bool	canFoldInAddressingMode (SDNode N, SDNode Use, SelectionDAG &DAG, const TargetLowering &TLI)

static bool	areUsedBitsDense (const APInt &UsedBits)
	Check that all bits set in `UsedBits` form a dense region, i.e., `UsedBits` looks like 0..0 1..1 0..0. More...

static bool	areSlicesNextToEachOther (const LoadedSlice &First, const LoadedSlice &Second)
	Check whether or not `First` and `Second` are next to each other in memory. This means that there is no hole between the bits loaded by `First` and the bits loaded by `Second`. More...

static void	adjustCostForPairing (SmallVectorImpl< LoadedSlice > &LoadedSlices, LoadedSlice::Cost &GlobalLSCost)
	Adjust the `GlobalLSCost` according to the target paring capabilities and the layout of the slices. More...

static bool	isSlicingProfitable (SmallVectorImpl< LoadedSlice > &LoadedSlices, const APInt &UsedBits, bool ForCodeSize)
	Check the profitability of all involved LoadedSlice. Currently, it is considered profitable if there is exactly two involved slices (1) which are (2) next to each other in memory, and whose cost (. More...

static std::pair< unsigned, unsigned >	CheckForMaskedLoad (SDValue V, SDValue Ptr, SDValue Chain)

static SDNode *	ShrinkLoadReplaceStoreWithStore (const std::pair< unsigned, unsigned > &MaskInfo, SDValue IVal, StoreSDNode St, DAGCombiner DC)

static SDValue	partitionShuffleOfConcats (SDNode *N, SelectionDAG &DAG)

static bool	FindBaseOffset (SDValue Ptr, SDValue &Base, int64_t &Offset, const GlobalValue &GV, const void &CV)
	FindBaseOffset - Return true if base is a frame index, which is known not. More...

Macro Definition Documentation

#define DEBUG_TYPE "dagcombine"

Definition at line 19 of file DAGCombiner.cpp.

Function Documentation

static void adjustCostForPairing	(	SmallVectorImpl< LoadedSlice > &	LoadedSlices,
		LoadedSlice::Cost &	GlobalLSCost
	)

static

Adjust the GlobalLSCost according to the target paring capabilities and the layout of the slices.

Precondition: GlobalLSCost should account for at least as many loads as there is in the slices in LoadedSlices.

Definition at line 7978 of file DAGCombiner.cpp.

References areSlicesNextToEachOther(), llvm::SmallVectorTemplateCommon< T >::begin(), llvm::SmallVectorTemplateCommon< T >::end(), and llvm::SmallVectorTemplateCommon< T >::size().

Referenced by isSlicingProfitable().

static bool areSlicesNextToEachOther	(	const LoadedSlice &	First,
		const LoadedSlice &	Second
	)

static

Check whether or not First and Second are next to each other in memory. This means that there is no hole between the bits loaded by First and the bits loaded by Second.

Definition at line 7963 of file DAGCombiner.cpp.

References areUsedBitsDense().

Referenced by adjustCostForPairing().

static bool areUsedBitsDense ( const APInt & UsedBits )

static

Check that all bits set in UsedBits form a dense region, i.e., UsedBits looks like 0..0 1..1 0..0.

Definition at line 7946 of file DAGCombiner.cpp.

References llvm::APInt::countLeadingZeros(), llvm::APInt::countTrailingZeros(), llvm::APInt::getActiveBits(), llvm::APInt::isAllOnesValue(), llvm::APInt::lshr(), and llvm::APInt::trunc().

Referenced by areSlicesNextToEachOther(), and isSlicingProfitable().

static bool canFoldInAddressingMode	(	SDNode *	N,
		SDNode *	Use,
		SelectionDAG &	DAG,
		const TargetLowering &	TLI
	)

static

canFoldInAddressingMode - Return true if 'Use' is a load or a store that uses N as its base pointer and that N may be folded in the load / store addressing mode.

Definition at line 7100 of file DAGCombiner.cpp.

References llvm::ISD::ADD, llvm::dyn_cast(), llvm::LoadSDNode::getBasePtr(), llvm::SelectionDAG::getContext(), llvm::SDValue::getNode(), llvm::SDNode::getOpcode(), llvm::SDNode::getOperand(), llvm::ConstantSDNode::getSExtValue(), llvm::EVT::getTypeForEVT(), llvm::SDNode::getValueType(), llvm::LSBaseSDNode::isIndexed(), llvm::TargetLoweringBase::isLegalAddressingMode(), N, llvm::A64DB::ST, and llvm::ISD::SUB.

static std::pair<unsigned, unsigned> CheckForMaskedLoad	(	SDValue	V,
		SDValue	Ptr,
		SDValue	Chain
	)

static

CheckForMaskedLoad - Check to see if V is (and load (ptr), imm), where the load is having specific bytes cleared out. If so, return the byte size being masked out and the shift amount.

Definition at line 8181 of file DAGCombiner.cpp.

References llvm::ISD::AND, llvm::countLeadingZeros(), llvm::CountTrailingOnes_64(), llvm::countTrailingZeros(), llvm::LoadSDNode::getBasePtr(), llvm::SDValue::getNode(), llvm::SDNode::getNumOperands(), llvm::SDNode::getOpcode(), llvm::SDNode::getOperand(), llvm::SDValue::getValueSizeInBits(), llvm::SDValue::getValueType(), llvm::MVT::i16, llvm::MVT::i32, llvm::MVT::i64, llvm::ISD::isNormalLoad(), llvm::A64DB::LD, and llvm::ISD::TokenFactor.

static SDValue combineShlAddConstant	(	SDLoc	DL,
		SDValue	N0,
		SDValue	N1,
		SelectionDAG &	DAG
	)

static

Definition at line 1380 of file DAGCombiner.cpp.

References llvm::ISD::ADD, llvm::dyn_cast(), llvm::SDValue::getNode(), llvm::SelectionDAG::getNode(), llvm::SDValue::getOpcode(), llvm::SDValue::getOperand(), llvm::SDValue::getValueType(), llvm::SDNode::hasOneUse(), and llvm::ISD::SHL.

static bool ExtendUsesToFormExtLoad	(	SDNode *	N,
		SDValue	N0,
		unsigned	ExtOpc,
		SmallVectorImpl< SDNode * > &	ExtendNodes,
		const TargetLowering &	TLI
	)

static

static bool FindBaseOffset	(	SDValue	Ptr,
		SDValue &	Base,
		int64_t &	Offset,
		const GlobalValue *&	GV,
		const void *&	CV
	)

static

FindBaseOffset - Return true if base is a frame index, which is known not.

Definition at line 10813 of file DAGCombiner.cpp.

References llvm::ISD::ADD, llvm::CallingConv::C, G, llvm::SDValue::getOpcode(), and llvm::SDValue::getOperand().

static SDNode* getBuildPairElt	(	SDNode *	N,
		unsigned	i
	)

static

Definition at line 5687 of file DAGCombiner.cpp.

References llvm::SDValue::getNode(), llvm::SDValue::getOpcode(), llvm::SDValue::getOperand(), llvm::SDNode::getOperand(), llvm::SDValue::getResNo(), and llvm::ISD::MERGE_VALUES.

static SDValue getInputChainForNode ( SDNode * N )

static

getInputChainForNode - Given a node, return its input chain if it has one, otherwise return a null sd operand.

Definition at line 1271 of file DAGCombiner.cpp.

References llvm::SDNode::getNumOperands(), llvm::SDNode::getOperand(), llvm::SDValue::getValueType(), and llvm::MVT::Other.

static SDValue GetNegatedExpression	(	SDValue	Op,
		SelectionDAG &	DAG,
		bool	LegalOperations,
		unsigned	Depth = `0`
	)

static

GetNegatedExpression - If isNegatibleForFree returns true, this function returns the newly negated expression.

Definition at line 491 of file DAGCombiner.cpp.

References llvm::APFloat::changeSign(), llvm::ISD::ConstantFP, llvm::ISD::FADD, llvm::ISD::FDIV, llvm::ISD::FMUL, llvm::ISD::FNEG, llvm::ISD::FP_EXTEND, llvm::ISD::FP_ROUND, llvm::ISD::FSIN, llvm::ISD::FSUB, llvm::SelectionDAG::getConstantFP(), llvm::SelectionDAG::getNode(), llvm::SDValue::getOpcode(), llvm::SDValue::getOperand(), llvm::SelectionDAG::getTarget(), llvm::SelectionDAG::getTargetLoweringInfo(), llvm::SDValue::getValueType(), llvm::SDValue::hasOneUse(), llvm::TargetOptions::HonorSignDependentRoundingFPMath(), isNegatibleForFree(), llvm_unreachable, llvm::TargetMachine::Options, and llvm::TargetOptions::UnsafeFPMath.

static bool isBSwapHWordElement	(	SDValue	N,
		SmallVectorImpl< SDNode * > &	Parts
	)

static

isBSwapHWordElement - Return true if the specified node is an element that makes up a 32-bit packed halfword byteswap. i.e. ((x&0xff)<<8)|((x&0xff00)>>8)|((x&0x00ff0000)<<8)|((x&0xff000000)>>8)

Definition at line 2990 of file DAGCombiner.cpp.

References llvm::ISD::AND, llvm::CallingConv::C, llvm::dyn_cast(), llvm::SDValue::getNode(), llvm::SDValue::getOpcode(), llvm::SDValue::getOperand(), llvm::ConstantSDNode::getZExtValue(), llvm::SDNode::hasOneUse(), llvm::ISD::SHL, and llvm::ISD::SRL.

static bool isConstantSplatVector	(	SDNode *	N,
		APInt &	SplatValue
	)

static

isConstantSplatVector - Returns true if N is a BUILD_VECTOR node whose elements are all the same constant or undefined.

Definition at line 1783 of file DAGCombiner.cpp.

References llvm::CallingConv::C, llvm::dyn_cast(), llvm::EVT::getSizeInBits(), llvm::SDNode::getValueType(), llvm::EVT::getVectorElementType(), llvm::BuildVectorSDNode::isConstantSplat(), and N.

static char isNegatibleForFree	(	SDValue	Op,
		bool	LegalOperations,
		const TargetLowering &	TLI,
		const TargetOptions *	Options,
		unsigned	Depth = `0`
	)

static

isNegatibleForFree - Return 1 if we can compute the negated form of the specified expression for the same cost as the expression itself, or 2 if we can compute the negated form more cheaply than the expression itself.

Definition at line 427 of file DAGCombiner.cpp.

References llvm::ISD::ConstantFP, llvm::ISD::FADD, llvm::ISD::FDIV, llvm::ISD::FMUL, llvm::ISD::FNEG, llvm::ISD::FP_EXTEND, llvm::ISD::FP_ROUND, llvm::ISD::FSIN, llvm::ISD::FSUB, llvm::SDValue::getOpcode(), llvm::SDValue::getOperand(), llvm::SDValue::getValueType(), llvm::SDValue::hasOneUse(), llvm::TargetLoweringBase::isOperationLegalOrCustom(), and llvm::TargetOptions::UnsafeFPMath.

Referenced by GetNegatedExpression().

static bool isOneUseSetCC ( SDValue N )

static

Definition at line 599 of file DAGCombiner.cpp.

References llvm::SDValue::getNode(), llvm::SDNode::hasOneUse(), and isSetCCEquivalent().

static bool isSetCCEquivalent	(	SDValue	N,
		SDValue &	LHS,
		SDValue &	RHS,
		SDValue &	CC
	)

static

Definition at line 575 of file DAGCombiner.cpp.

References llvm::ISD::Constant, llvm::SDValue::getOpcode(), llvm::SDValue::getOperand(), llvm::ISD::SELECT_CC, and llvm::ISD::SETCC.

Referenced by isOneUseSetCC().

static bool isSlicingProfitable	(	SmallVectorImpl< LoadedSlice > &	LoadedSlices,
		const APInt &	UsedBits,
		bool	ForCodeSize
	)

static

Check the profitability of all involved LoadedSlice. Currently, it is considered profitable if there is exactly two involved slices (1) which are (2) next to each other in memory, and whose cost (.

See Also: LoadedSlice::Cost) is smaller than the original load (3).

Note: The order of the elements in LoadedSlices may be modified, but not the elements themselves.

FIXME: When the cost model will be mature enough, we can relax constraints (1) and (2).

Definition at line 8042 of file DAGCombiner.cpp.

References adjustCostForPairing(), areUsedBitsDense(), and llvm::SmallVectorTemplateCommon< T >::size().

static bool isTruncateOf	(	SelectionDAG &	DAG,
		SDValue	N,
		SDValue &	Op,
		APInt &	KnownZero
	)

static

Definition at line 4752 of file DAGCombiner.cpp.

References llvm::SelectionDAG::ComputeMaskedBits(), llvm::dyn_cast(), llvm::SDNode::getOpcode(), llvm::SDNode::getOperand(), llvm::SDValue::getValueSizeInBits(), llvm::SDValue::getValueType(), llvm::SDNode::getValueType(), llvm::MVT::i1, llvm::ISD::SETCC, llvm::ISD::SETNE, and llvm::ISD::TRUNCATE.

static bool MatchRotateHalf	(	SDValue	Op,
		SDValue &	Shift,
		SDValue &	Mask
	)

static

MatchRotateHalf - Match "(X shl/srl V1) & V2" where V2 may not be present.

Definition at line 3287 of file DAGCombiner.cpp.

References llvm::ISD::AND, llvm::SDValue::getOpcode(), llvm::SDValue::getOperand(), llvm::ISD::SHL, and llvm::ISD::SRL.

static SDValue partitionShuffleOfConcats	(	SDNode *	N,
		SelectionDAG &	DAG
	)

static

Definition at line 9991 of file DAGCombiner.cpp.

References llvm::ISD::CONCAT_VECTORS, llvm::ShuffleVectorSDNode::getMaskElt(), llvm::SelectionDAG::getNode(), llvm::SDValue::getNumOperands(), llvm::SDValue::getOperand(), llvm::SDNode::getOperand(), llvm::SelectionDAG::getUNDEF(), llvm::SDValue::getValueType(), llvm::SDNode::getValueType(), llvm::EVT::getVectorNumElements(), I, and N.

static SDNode* ShrinkLoadReplaceStoreWithStore	(	const std::pair< unsigned, unsigned > &	MaskInfo,
		SDValue	IVal,
		StoreSDNode *	St,
		DAGCombiner *	DC
	)

static

ShrinkLoadReplaceStoreWithStore - Check to see if IVal is something that provides a value as specified by MaskInfo. If so, replace the specified store with a narrower store of truncated IVal.

Definition at line 8256 of file DAGCombiner.cpp.

References llvm::ISD::ADD, llvm::MemSDNode::getAlignment(), llvm::StoreSDNode::getBasePtr(), llvm::MemSDNode::getChain(), llvm::SelectionDAG::getConstant(), llvm::MVT::getIntegerVT(), llvm::SelectionDAG::getNode(), llvm::MemSDNode::getPointerInfo(), llvm::SelectionDAG::getStore(), llvm::EVT::getStoreSize(), llvm::SelectionDAG::getTargetLoweringInfo(), llvm::SDValue::getValueSizeInBits(), llvm::SDValue::getValueType(), llvm::MachinePointerInfo::getWithOffset(), llvm::TargetLoweringBase::isLittleEndian(), llvm::SelectionDAG::MaskedValueIsZero(), llvm::MinAlign(), llvm::ISD::SRL, and llvm::ISD::TRUNCATE.

static std::pair<SDValue, SDValue> SplitVSETCC	(	const SDNode *	N,
		SelectionDAG &	DAG
	)

static

Definition at line 4320 of file DAGCombiner.cpp.

References llvm::SelectionDAG::getNode(), llvm::SDNode::getOpcode(), llvm::SDNode::getOperand(), llvm::SelectionDAG::GetSplitDestVTs(), llvm::SDNode::getValueType(), llvm::HexagonISD::Hi, llvm::HexagonISD::Lo, llvm::SelectionDAG::SplitVectorOperand(), and llvm::tie().

STATISTIC	(	NodesCombined	,
		"Number of dag nodes combined"
	)

STATISTIC	(	PreIndexedNodes	,
		"Number of pre-indexed nodes created"
	)

STATISTIC	(	PostIndexedNodes	,
		"Number of post-indexed nodes created"
	)

STATISTIC	(	OpsNarrowed	,
		"Number of load/op/store narrowed"
	)

STATISTIC	(	LdStFP2Int	,
		"Number of fp load/store pairs transformed to int"
	)

STATISTIC	(	SlicedLoads	,
		"Number of load sliced"
	)

static SDValue tryFoldToZero	(	SDLoc	DL,
		const TargetLowering &	TLI,
		EVT	VT,
		SelectionDAG &	DAG,
		bool	LegalOperations,
		bool	LegalTypes
	)

static

Definition at line 1633 of file DAGCombiner.cpp.

References llvm::ISD::BUILD_VECTOR, llvm::SelectionDAG::getConstant(), llvm::TargetLoweringBase::isOperationLegal(), and llvm::EVT::isVector().

Classes

Macros

Functions

Macro Definition Documentation

Function Documentation