#include "llvm/CodeGen/SelectionDAG.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SetVector.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	BaseIndexOffset
struct	MemOpLink
Defines
#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)
	If isNegatibleForFree returns true, return the newly negated expression.
static bool	isConstantSplatVector (SDNode *N, APInt &SplatValue)
static SDNode *	isConstantBuildVectorOrConstantInt (SDValue N)
static ConstantSDNode *	isConstOrConstSplat (SDValue N)
static ConstantFPSDNode *	isConstOrConstSplatFP (SDValue N)
static SDValue	getInputChainForNode (SDNode *N)
static SDValue	tryFoldToZero (SDLoc DL, const TargetLowering &TLI, EVT VT, SelectionDAG &DAG, bool LegalOperations, bool LegalTypes)
static bool	isBSwapHWordElement (SDValue N, SmallVectorImpl< SDNode * > &Parts)
static bool	MatchRotateHalf (SDValue Op, SDValue &Shift, SDValue &Mask)
	Match "(X shl/srl V1) & V2" where V2 may not be present.
static bool	matchRotateSub (SDValue Pos, SDValue Neg, unsigned OpSize)
static std::pair< SDValue, SDValue >	SplitVSETCC (const SDNode *N, SelectionDAG &DAG)
static SDValue	ConvertSelectToConcatVector (SDNode *N, SelectionDAG &DAG)
static SDNode *	tryToFoldExtendOfConstant (SDNode *N, const TargetLowering &TLI, SelectionDAG &DAG, bool LegalTypes, bool LegalOperations)
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.
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`.
static void	adjustCostForPairing (SmallVectorImpl< LoadedSlice > &LoadedSlices, LoadedSlice::Cost &GlobalLSCost)
	Adjust the `GlobalLSCost` according to the target paring capabilities and the layout of the slices.
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 (.
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)

Define Documentation

#define DEBUG_TYPE "dagcombine"

Definition at line 43 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 8516 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 8501 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 8484 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]`

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 7618 of file DAGCombiner.cpp.

References 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(), llvm::AArch64DB::ST, and SUB.

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

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 8723 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::AArch64DB::LD, and llvm::ISD::TokenFactor.

static SDValue ConvertSelectToConcatVector	(	SDNode *	N,
		SelectionDAG &	DAG
	)		`[static]`

Definition at line 4678 of file DAGCombiner.cpp.

References llvm::ISD::BUILD_VECTOR, llvm::ISD::CONCAT_VECTORS, llvm::SDValue::getNode(), llvm::SelectionDAG::getNode(), llvm::SDNode::getNumOperands(), llvm::SDValue::getOpcode(), llvm::SDNode::getOpcode(), llvm::SDValue::getOperand(), llvm::SDNode::getOperand(), llvm::SDNode::getValueType(), llvm::EVT::getVectorNumElements(), llvm::ConstantSDNode::isNullValue(), and llvm::ISD::UNDEF.

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]`

Return true if base is a frame index, which is known not to alias with anything but itself. Provides base object and offset as results.

Definition at line 11695 of file DAGCombiner.cpp.

References ADD, G, llvm::SDValue::getOpcode(), llvm::SDValue::getOperand(), and llvm::ConstantSDNode::getZExtValue().

static SDNode* getBuildPairElt	(	SDNode *	N,
		unsigned	i
	)		`[static]`

Definition at line 6220 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]

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

Definition at line 1414 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]`

If isNegatibleForFree returns true, return the newly negated expression.

Definition at line 545 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]`

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

Definition at line 3127 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 SDNode* isConstantBuildVectorOrConstantInt ( SDValue N ) [static]

Definition at line 674 of file DAGCombiner.cpp.

References llvm::dyn_cast(), llvm::SDValue::getNode(), and llvm::BuildVectorSDNode::isConstant().

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

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

Definition at line 659 of file DAGCombiner.cpp.

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

static ConstantSDNode* isConstOrConstSplat ( SDValue N ) [static]

Definition at line 685 of file DAGCombiner.cpp.

References llvm::EVT::getScalarType(), llvm::SDValue::getValueType(), llvm::SDNode::getValueType(), and llvm::BitVector::none().

static ConstantFPSDNode* isConstOrConstSplatFP ( SDValue N ) [static]

Definition at line 706 of file DAGCombiner.cpp.

References llvm::BitVector::none().

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

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 482 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 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 8584 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 5230 of file DAGCombiner.cpp.

References llvm::SelectionDAG::computeKnownBits(), 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]`

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

Definition at line 3494 of file DAGCombiner.cpp.

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

static bool matchRotateSub	(	SDValue	Pos,
		SDValue	Neg,
		unsigned	OpSize
	)		`[static]`

Definition at line 3521 of file DAGCombiner.cpp.

References llvm::ISD::ADD, llvm::ISD::AND, llvm::ISD::Constant, llvm::dyn_cast(), llvm::ConstantSDNode::getAPIntValue(), llvm::APInt::getLoBits(), llvm::SDValue::getOpcode(), llvm::SDValue::getOperand(), llvm::isPowerOf2_64(), llvm::Log2_64(), and SUB.

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

Definition at line 10631 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(), and I.

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

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 8798 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 4660 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, and llvm::SelectionDAG::SplitVectorOperand().

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 1744 of file DAGCombiner.cpp.

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

static SDNode* tryToFoldExtendOfConstant	(	SDNode *	N,
		const TargetLowering &	TLI,
		SelectionDAG &	DAG,
		bool	LegalTypes,
		bool	LegalOperations
	)		`[static]`

Classes

Defines

Functions

Define Documentation

Function Documentation