#include "llvm/CodeGen/SelectionDAG.h"
#include "SDNodeDbgValue.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Assembly/Writer.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineConstantPool.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineModuleInfo.h"
#include "llvm/DebugInfo.h"
#include "llvm/IR/CallingConv.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/GlobalAlias.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/ManagedStatic.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/Mutex.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetIntrinsicInfo.h"
#include "llvm/Target/TargetLowering.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetOptions.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetSelectionDAGInfo.h"
#include <algorithm>
#include <cmath>

Include dependency graph for SelectionDAG.cpp:

Functions
static SDVTList	makeVTList (const EVT *VTs, unsigned NumVTs)

static int	isSignedOp (ISD::CondCode Opcode)

static void	AddNodeIDOpcode (FoldingSetNodeID &ID, unsigned OpC)

static void	AddNodeIDValueTypes (FoldingSetNodeID &ID, SDVTList VTList)

static void	AddNodeIDOperands (FoldingSetNodeID &ID, const SDValue *Ops, unsigned NumOps)

static void	AddNodeIDOperands (FoldingSetNodeID &ID, const SDUse *Ops, unsigned NumOps)

static void	AddNodeIDNode (FoldingSetNodeID &ID, unsigned short OpC, SDVTList VTList, const SDValue *OpList, unsigned N)

static void	AddNodeIDCustom (FoldingSetNodeID &ID, const SDNode *N)

static void	AddNodeIDNode (FoldingSetNodeID &ID, const SDNode *N)

static unsigned	encodeMemSDNodeFlags (int ConvType, ISD::MemIndexedMode AM, bool isVolatile, bool isNonTemporal, bool isInvariant)

static bool	doNotCSE (SDNode *N)
	doNotCSE - Return true if CSE should not be performed for this node. More...

static void	VerifyNodeCommon (SDNode *N)
	VerifyNodeCommon - Sanity check the given node. Aborts if it is invalid. More...

static void	VerifySDNode (SDNode *N)
	VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid. More...

static void	VerifyMachineNode (SDNode *N)

static void	commuteShuffle (SDValue &N1, SDValue &N2, SmallVectorImpl< int > &M)

static SDValue	getMemsetValue (SDValue Value, EVT VT, SelectionDAG &DAG, SDLoc dl)

static SDValue	getMemsetStringVal (EVT VT, SDLoc dl, SelectionDAG &DAG, const TargetLowering &TLI, StringRef Str)

static SDValue	getMemBasePlusOffset (SDValue Base, unsigned Offset, SDLoc dl, SelectionDAG &DAG)

static bool	isMemSrcFromString (SDValue Src, StringRef &Str)

static bool	FindOptimalMemOpLowering (std::vector< EVT > &MemOps, unsigned Limit, uint64_t Size, unsigned DstAlign, unsigned SrcAlign, bool IsMemset, bool ZeroMemset, bool MemcpyStrSrc, bool AllowOverlap, SelectionDAG &DAG, const TargetLowering &TLI)

static SDValue	getMemcpyLoadsAndStores (SelectionDAG &DAG, SDLoc dl, SDValue Chain, SDValue Dst, SDValue Src, uint64_t Size, unsigned Align, bool isVol, bool AlwaysInline, MachinePointerInfo DstPtrInfo, MachinePointerInfo SrcPtrInfo)

static SDValue	getMemmoveLoadsAndStores (SelectionDAG &DAG, SDLoc dl, SDValue Chain, SDValue Dst, SDValue Src, uint64_t Size, unsigned Align, bool isVol, bool AlwaysInline, MachinePointerInfo DstPtrInfo, MachinePointerInfo SrcPtrInfo)

static SDValue	getMemsetStores (SelectionDAG &DAG, SDLoc dl, SDValue Chain, SDValue Dst, SDValue Src, uint64_t Size, unsigned Align, bool isVol, MachinePointerInfo DstPtrInfo)
	Lower the call to 'memset' intrinsic function into a series of store operations. More...

static MachinePointerInfo	InferPointerInfo (SDValue Ptr, int64_t Offset=0)

static MachinePointerInfo	InferPointerInfo (SDValue Ptr, SDValue OffsetOp)

Variables
static ManagedStatic< std::set < EVT, EVT::compareRawBits > >	EVTs

static ManagedStatic< EVTArray >	SimpleVTArray

static ManagedStatic < sys::SmartMutex< true > >	VTMutex

Function Documentation

static void AddNodeIDCustom	(	FoldingSetNodeID &	ID,
		const SDNode *	N
	)

static

AddNodeIDCustom - If this is an SDNode with special info, add this info to the NodeID data.

Definition at line 365 of file SelectionDAG.cpp.

Referenced by AddNodeIDNode().

static void AddNodeIDNode	(	FoldingSetNodeID &	ID,
		unsigned short	OpC,
		SDVTList	VTList,
		const SDValue *	OpList,
		unsigned	N
	)

static

Definition at line 355 of file SelectionDAG.cpp.

References AddNodeIDOpcode(), AddNodeIDOperands(), and AddNodeIDValueTypes().

static void AddNodeIDNode	(	FoldingSetNodeID &	ID,
		const SDNode *	N
	)

static

AddNodeIDNode - Generic routine for adding a nodes info to the NodeID data.

Definition at line 494 of file SelectionDAG.cpp.

References AddNodeIDCustom(), AddNodeIDOpcode(), AddNodeIDOperands(), AddNodeIDValueTypes(), llvm::SDNode::getNumOperands(), llvm::SDNode::getOpcode(), llvm::SDNode::getVTList(), and llvm::SDNode::op_begin().

static void AddNodeIDOpcode	(	FoldingSetNodeID &	ID,
		unsigned	OpC
	)

static

AddNodeIDOpcode - Add the node opcode to the NodeID data.

Definition at line 325 of file SelectionDAG.cpp.

References llvm::FoldingSetNodeID::AddInteger().

Referenced by AddNodeIDNode().

static void AddNodeIDOperands	(	FoldingSetNodeID &	ID,
		const SDValue *	Ops,
		unsigned	NumOps
	)

static

AddNodeIDOperands - Various routines for adding operands to the NodeID data.

Definition at line 337 of file SelectionDAG.cpp.

References llvm::FoldingSetNodeID::AddInteger(), and llvm::FoldingSetNodeID::AddPointer().

Referenced by AddNodeIDNode().

static void AddNodeIDOperands	(	FoldingSetNodeID &	ID,
		const SDUse *	Ops,
		unsigned	NumOps
	)

static

AddNodeIDOperands - Various routines for adding operands to the NodeID data.

Definition at line 347 of file SelectionDAG.cpp.

References llvm::FoldingSetNodeID::AddInteger(), llvm::FoldingSetNodeID::AddPointer(), llvm::SDUse::getNode(), and llvm::SDUse::getResNo().

static void AddNodeIDValueTypes	(	FoldingSetNodeID &	ID,
		SDVTList	VTList
	)

static

AddNodeIDValueTypes - Value type lists are intern'd so we can represent them solely with their pointer.

Definition at line 331 of file SelectionDAG.cpp.

References llvm::FoldingSetNodeID::AddPointer(), and llvm::SDVTList::VTs.

Referenced by AddNodeIDNode().

static void commuteShuffle	(	SDValue &	N1,
		SDValue &	N2,
		SmallVectorImpl< int > &	M
	)

static

Definition at line 1340 of file SelectionDAG.cpp.

References llvm::SmallVectorTemplateCommon< T, typename >::size(), and std::swap().

Referenced by llvm::SelectionDAG::getVectorShuffle().

static bool doNotCSE ( SDNode * N )

static

doNotCSE - Return true if CSE should not be performed for this node.

Definition at line 528 of file SelectionDAG.cpp.

References llvm::ISD::EH_LABEL, llvm::SDNode::getNumValues(), llvm::SDNode::getOpcode(), llvm::SDNode::getValueType(), llvm::MVT::Glue, and llvm::ISD::HANDLENODE.

static unsigned encodeMemSDNodeFlags	(	int	ConvType,
		ISD::MemIndexedMode	AM,
		bool	isVolatile,
		bool	isNonTemporal,
		bool	isInvariant
	)

inlinestatic

encodeMemSDNodeFlags - Generic routine for computing a value for use in the CSE map that carries volatility, temporalness, indexing mode, and extension/truncation information.

Definition at line 510 of file SelectionDAG.cpp.

Referenced by llvm::SelectionDAG::getLoad(), llvm::SelectionDAG::getStore(), llvm::SelectionDAG::getTruncStore(), and llvm::MemSDNode::MemSDNode().

static bool FindOptimalMemOpLowering	(	std::vector< EVT > &	MemOps,
		unsigned	Limit,
		uint64_t	Size,
		unsigned	DstAlign,
		unsigned	SrcAlign,
		bool	IsMemset,
		bool	ZeroMemset,
		bool	MemcpyStrSrc,
		bool	AllowOverlap,
		SelectionDAG &	DAG,
		const TargetLowering &	TLI
	)

static

FindOptimalMemOpLowering - Determines the optimial series memory ops to replace the memset / memcpy. Return true if the number of memory ops is below the threshold. It returns the types of the sequence of memory ops to perform memset / memcpy by reference.

Definition at line 3589 of file SelectionDAG.cpp.

References llvm::TargetLoweringBase::allowsUnalignedMemoryAccesses(), llvm::EVT::bitsGT(), llvm::MVT::f64, llvm::CallingConv::Fast, llvm::TargetLoweringBase::getDataLayout(), llvm::SelectionDAG::getMachineFunction(), llvm::TargetLoweringBase::getOptimalMemOpType(), llvm::DataLayout::getPointerPrefAlignment(), llvm::TargetLoweringBase::getPointerTy(), llvm::EVT::getSimpleVT(), llvm::EVT::getSizeInBits(), llvm::MVT::i16, llvm::MVT::i32, llvm::MVT::i64, llvm::MVT::i8, llvm::EVT::isFloatingPoint(), llvm::MVT::isInteger(), llvm::TargetLoweringBase::isOperationLegalOrCustom(), llvm::TargetLoweringBase::isSafeMemOpType(), llvm::TargetLoweringBase::isTypeLegal(), llvm::EVT::isVector(), llvm::MVT::Other, llvm::MVT::SimpleTy, and llvm::ISD::STORE.

Referenced by getMemcpyLoadsAndStores(), getMemmoveLoadsAndStores(), and getMemsetStores().

static SDValue getMemBasePlusOffset	(	SDValue	Base,
		unsigned	Offset,
		SDLoc	dl,
		SelectionDAG &	DAG
	)

static

getMemBasePlusOffset - Returns base and offset node for the

Definition at line 3559 of file SelectionDAG.cpp.

References llvm::ISD::ADD, llvm::SelectionDAG::getConstant(), llvm::SelectionDAG::getNode(), and llvm::SDValue::getValueType().

Referenced by getMemcpyLoadsAndStores(), getMemmoveLoadsAndStores(), and getMemsetStores().

static SDValue getMemcpyLoadsAndStores	(	SelectionDAG &	DAG,
		SDLoc	dl,
		SDValue	Chain,
		SDValue	Dst,
		SDValue	Src,
		uint64_t	Size,
		unsigned	Align,
		bool	isVol,
		bool	AlwaysInline,
		MachinePointerInfo	DstPtrInfo,
		MachinePointerInfo	SrcPtrInfo
	)

static

Definition at line 3690 of file SelectionDAG.cpp.

Referenced by llvm::SelectionDAG::getMemcpy().

static SDValue getMemmoveLoadsAndStores	(	SelectionDAG &	DAG,
		SDLoc	dl,
		SDValue	Chain,
		SDValue	Dst,
		SDValue	Src,
		uint64_t	Size,
		unsigned	Align,
		bool	isVol,
		bool	AlwaysInline,
		MachinePointerInfo	DstPtrInfo,
		MachinePointerInfo	SrcPtrInfo
	)

static

Definition at line 3808 of file SelectionDAG.cpp.

References Align(), llvm::SmallVectorImpl< T >::clear(), llvm::dyn_cast(), FindOptimalMemOpLowering(), llvm::DataLayout::getABITypeAlignment(), llvm::Function::getAttributes(), llvm::SelectionDAG::getContext(), llvm::TargetLoweringBase::getDataLayout(), llvm::MachineFunction::getFrameInfo(), llvm::MachineFunction::getFunction(), llvm::FrameIndexSDNode::getIndex(), llvm::SelectionDAG::getLoad(), llvm::SelectionDAG::getMachineFunction(), llvm::TargetLoweringBase::getMaxStoresPerMemmove(), getMemBasePlusOffset(), llvm::SelectionDAG::getNode(), llvm::MachineFrameInfo::getObjectAlignment(), llvm::SDValue::getOpcode(), llvm::EVT::getSizeInBits(), llvm::SelectionDAG::getStore(), llvm::SelectionDAG::getTargetLoweringInfo(), llvm::SDValue::getValue(), llvm::MachinePointerInfo::getWithOffset(), llvm::SelectionDAG::InferPtrAlignment(), llvm::MachineFrameInfo::isFixedObjectIndex(), llvm::Attribute::OptimizeForSize, llvm::MVT::Other, llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::MachineFrameInfo::setObjectAlignment(), llvm::SmallVectorTemplateCommon< T, typename >::size(), llvm::SmallVectorTemplateCommon< T >::size(), llvm::SPII::Store, llvm::ISD::TokenFactor, and llvm::ISD::UNDEF.

Referenced by llvm::SelectionDAG::getMemmove().

static SDValue getMemsetStores	(	SelectionDAG &	DAG,
		SDLoc	dl,
		SDValue	Chain,
		SDValue	Dst,
		SDValue	Src,
		uint64_t	Size,
		unsigned	Align,
		bool	isVol,
		MachinePointerInfo	DstPtrInfo
	)

static

Lower the call to 'memset' intrinsic function into a series of store operations.

Parameters

DAG	Selection DAG where lowered code is placed.
dl	Link to corresponding IR location.
Chain	Control flow dependency.
Dst	Pointer to destination memory location.
Src	Value of byte to write into the memory.
Size	Number of bytes to write.
Align	Alignment of the destination in bytes.
isVol	True if destination is volatile.
DstPtrInfo	IR information on the memory pointer.

Returns: New head in the control flow, if lowering was successful, empty SDValue otherwise.

The function tries to replace 'llvm.memset' intrinsic with several store operations and value calculation code. This is usually profitable for small memory size.

Definition at line 3907 of file SelectionDAG.cpp.

References Align(), llvm::EVT::bitsLT(), llvm::dyn_cast(), FindOptimalMemOpLowering(), llvm::DataLayout::getABITypeAlignment(), llvm::Function::getAttributes(), llvm::SelectionDAG::getContext(), llvm::TargetLoweringBase::getDataLayout(), llvm::MachineFunction::getFrameInfo(), llvm::MachineFunction::getFunction(), llvm::FrameIndexSDNode::getIndex(), llvm::SelectionDAG::getMachineFunction(), llvm::TargetLoweringBase::getMaxStoresPerMemset(), getMemBasePlusOffset(), getMemsetValue(), llvm::SelectionDAG::getNode(), llvm::MachineFrameInfo::getObjectAlignment(), llvm::SDValue::getOpcode(), llvm::EVT::getSizeInBits(), llvm::SelectionDAG::getStore(), llvm::SelectionDAG::getTargetLoweringInfo(), llvm::SDValue::getValueType(), llvm::MachinePointerInfo::getWithOffset(), llvm::MachineFrameInfo::isFixedObjectIndex(), llvm::TargetLoweringBase::isTruncateFree(), llvm::EVT::isVector(), llvm::Attribute::OptimizeForSize, llvm::MVT::Other, llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::MachineFrameInfo::setObjectAlignment(), llvm::SmallVectorTemplateCommon< T >::size(), llvm::SmallVectorTemplateCommon< T, typename >::size(), llvm::SPII::Store, llvm::ISD::TokenFactor, llvm::ISD::TRUNCATE, and llvm::ISD::UNDEF.

Referenced by llvm::SelectionDAG::getMemset().

static SDValue getMemsetStringVal	(	EVT	VT,
		SDLoc	dl,
		SelectionDAG &	DAG,
		const TargetLowering &	TLI,
		StringRef	Str
	)

static

getMemsetStringVal - Similar to getMemsetValue. Except this is only used when a memcpy is turned into a memset when the source is a constant string ptr.

Definition at line 3517 of file SelectionDAG.cpp.

References llvm::ISD::BITCAST, llvm::StringRef::empty(), llvm::MVT::f32, llvm::MVT::f64, llvm::SelectionDAG::getConstant(), llvm::SelectionDAG::getConstantFP(), llvm::SelectionDAG::getContext(), llvm::TargetTransformInfo::getIntImmCost(), llvm::SelectionDAG::getNode(), llvm::EVT::getSizeInBits(), llvm::SelectionDAG::getTargetTransformInfo(), llvm::EVT::getTypeForEVT(), llvm::EVT::getVectorElementType(), llvm::EVT::getVectorNumElements(), llvm::EVT::getVectorVT(), llvm::MVT::i32, llvm::MVT::i64, llvm::EVT::isInteger(), llvm::TargetLoweringBase::isLittleEndian(), llvm::EVT::isVector(), llvm_unreachable, and llvm::StringRef::size().

Referenced by getMemcpyLoadsAndStores().

static SDValue getMemsetValue	(	SDValue	Value,
		EVT	VT,
		SelectionDAG &	DAG,
		SDLoc	dl
	)

static

getMemsetValue - Vectorized representation of the memset value operand.

Definition at line 3490 of file SelectionDAG.cpp.

References llvm::lltok::APFloat, llvm::CallingConv::C, llvm::SelectionDAG::EVTToAPFloatSemantics(), llvm::SelectionDAG::getConstant(), llvm::SelectionDAG::getConstantFP(), llvm::SelectionDAG::getNode(), llvm::SDValue::getOpcode(), llvm::EVT::getScalarType(), llvm::EVT::getSizeInBits(), llvm::APInt::getSplat(), llvm::EVT::isInteger(), Magic, llvm::ISD::MUL, llvm::ISD::UNDEF, and llvm::ISD::ZERO_EXTEND.

Referenced by getMemsetStores().

static MachinePointerInfo InferPointerInfo	(	SDValue	Ptr,
		int64_t	Offset = `0`
	)

static

InferPointerInfo - If the specified ptr/offset is a frame index, infer a MachinePointerInfo record from it. This is particularly useful because the code generator has many cases where it doesn't bother passing in a MachinePointerInfo to getLoad or getStore when it has "FI+Cst".

Definition at line 4453 of file SelectionDAG.cpp.

References llvm::ISD::ADD, llvm::MachinePointerInfo::getFixedStack(), llvm::SDValue::getOpcode(), and llvm::SDValue::getOperand().

Referenced by llvm::SelectionDAG::getLoad(), llvm::SelectionDAG::getStore(), llvm::SelectionDAG::getTruncStore(), and InferPointerInfo().

static MachinePointerInfo InferPointerInfo	(	SDValue	Ptr,
		SDValue	OffsetOp
	)

static

InferPointerInfo - If the specified ptr/offset is a frame index, infer a MachinePointerInfo record from it. This is particularly useful because the code generator has many cases where it doesn't bother passing in a MachinePointerInfo to getLoad or getStore when it has "FI+Cst".

Definition at line 4473 of file SelectionDAG.cpp.

References llvm::SDValue::getOpcode(), InferPointerInfo(), and llvm::ISD::UNDEF.

static bool isMemSrcFromString	(	SDValue	Src,
		StringRef &	Str
	)

static

isMemSrcFromString - Returns true if memcpy source is a string constant.

Definition at line 3568 of file SelectionDAG.cpp.

References llvm::ISD::ADD, llvm::ISD::Constant, G, llvm::getConstantStringInfo(), llvm::GlobalAddressSDNode::getGlobal(), llvm::SDValue::getOpcode(), llvm::SDValue::getOperand(), and llvm::ISD::GlobalAddress.

Referenced by getMemcpyLoadsAndStores().

static int isSignedOp ( ISD::CondCode Opcode )

static

isSignedOp - For an integer comparison, return 1 if the comparison is a signed operation and 2 if the result is an unsigned comparison. Return zero if the operation does not depend on the sign of the input (setne and seteq).

Definition at line 251 of file SelectionDAG.cpp.

References llvm_unreachable, llvm::ISD::SETEQ, llvm::ISD::SETGE, llvm::ISD::SETGT, llvm::ISD::SETLE, llvm::ISD::SETLT, llvm::ISD::SETNE, llvm::ISD::SETUGE, llvm::ISD::SETUGT, llvm::ISD::SETULE, and llvm::ISD::SETULT.