SelectionDAG.cpp File Reference

#include "llvm/CodeGen/SelectionDAG.h"
#include "llvm/Constants.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/GlobalAlias.h"
#include "llvm/GlobalVariable.h"
#include "llvm/Intrinsics.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Assembly/Writer.h"
#include "llvm/CallingConv.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineConstantPool.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineModuleInfo.h"
#include "llvm/CodeGen/PseudoSourceValue.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Target/TargetLowering.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.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 <algorithm>
#include <cmath>

Include dependency graph for SelectionDAG.cpp:

Go to the source code of this file.

Functions
static SDVTList	makeVTList (const MVT *VTs, unsigned NumVTs)
static const fltSemantics *	MVTToAPFloatSemantics (MVT VT)
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	AddNodeIDNode (FoldingSetNodeID &ID, const SDNode *N)
static unsigned	encodeMemSDNodeFlags (bool isVolatile, unsigned Alignment)
static SDValue	getMemsetValue (SDValue Value, MVT VT, SelectionDAG &DAG)
static SDValue	getMemsetStringVal (MVT VT, SelectionDAG &DAG, const TargetLowering &TLI, std::string &Str, unsigned Offset)
static SDValue	getMemBasePlusOffset (SDValue Base, unsigned Offset, SelectionDAG &DAG)
static bool	isMemSrcFromString (SDValue Src, std::string &Str)
static bool	MeetsMaxMemopRequirement (std::vector< MVT > &MemOps, SDValue Dst, SDValue Src, unsigned Limit, uint64_t Size, unsigned &Align, std::string &Str, bool &isSrcStr, SelectionDAG &DAG, const TargetLowering &TLI)
static SDValue	getMemcpyLoadsAndStores (SelectionDAG &DAG, SDValue Chain, SDValue Dst, SDValue Src, uint64_t Size, unsigned Align, bool AlwaysInline, const Value *DstSV, uint64_t DstSVOff, const Value *SrcSV, uint64_t SrcSVOff)
static SDValue	getMemmoveLoadsAndStores (SelectionDAG &DAG, SDValue Chain, SDValue Dst, SDValue Src, uint64_t Size, unsigned Align, bool AlwaysInline, const Value *DstSV, uint64_t DstSVOff, const Value *SrcSV, uint64_t SrcSVOff)
static SDValue	getMemsetStores (SelectionDAG &DAG, SDValue Chain, SDValue Dst, SDValue Src, uint64_t Size, unsigned Align, const Value *DstSV, uint64_t DstSVOff)
static void	findPredecessor (SDNode *N, const SDNode *P, bool &found, SmallPtrSet< SDNode *, 32 > &Visited)
static void	DumpNodes (const SDNode *N, unsigned indent, const SelectionDAG *G)

---

Function Documentation

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

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

Definition at line 358 of file SelectionDAG.cpp.

References llvm::FoldingSetNodeID::AddInteger(), AddNodeIDOpcode(), AddNodeIDOperands(), AddNodeIDValueTypes(), llvm::FoldingSetNodeID::AddPointer(), llvm::MachineConstantPoolValue::AddSelectionDAGCSEId(), llvm::ISD::ARG_FLAGS, llvm::ISD::ATOMIC_CMP_SWAP_16, llvm::ISD::ATOMIC_CMP_SWAP_32, llvm::ISD::ATOMIC_CMP_SWAP_64, llvm::ISD::ATOMIC_CMP_SWAP_8, llvm::ISD::ATOMIC_LOAD_ADD_16, llvm::ISD::ATOMIC_LOAD_ADD_32, llvm::ISD::ATOMIC_LOAD_ADD_64, llvm::ISD::ATOMIC_LOAD_ADD_8, llvm::ISD::ATOMIC_LOAD_AND_16, llvm::ISD::ATOMIC_LOAD_AND_32, llvm::ISD::ATOMIC_LOAD_AND_64, llvm::ISD::ATOMIC_LOAD_AND_8, llvm::ISD::ATOMIC_LOAD_MAX_16, llvm::ISD::ATOMIC_LOAD_MAX_32, llvm::ISD::ATOMIC_LOAD_MAX_64, llvm::ISD::ATOMIC_LOAD_MAX_8, llvm::ISD::ATOMIC_LOAD_MIN_16, llvm::ISD::ATOMIC_LOAD_MIN_32, llvm::ISD::ATOMIC_LOAD_MIN_64, llvm::ISD::ATOMIC_LOAD_MIN_8, llvm::ISD::ATOMIC_LOAD_NAND_16, llvm::ISD::ATOMIC_LOAD_NAND_32, llvm::ISD::ATOMIC_LOAD_NAND_64, llvm::ISD::ATOMIC_LOAD_NAND_8, llvm::ISD::ATOMIC_LOAD_OR_16, llvm::ISD::ATOMIC_LOAD_OR_32, llvm::ISD::ATOMIC_LOAD_OR_64, llvm::ISD::ATOMIC_LOAD_OR_8, llvm::ISD::ATOMIC_LOAD_SUB_16, llvm::ISD::ATOMIC_LOAD_SUB_32, llvm::ISD::ATOMIC_LOAD_SUB_64, llvm::ISD::ATOMIC_LOAD_SUB_8, llvm::ISD::ATOMIC_LOAD_UMAX_16, llvm::ISD::ATOMIC_LOAD_UMAX_32, llvm::ISD::ATOMIC_LOAD_UMAX_64, llvm::ISD::ATOMIC_LOAD_UMAX_8, llvm::ISD::ATOMIC_LOAD_UMIN_16, llvm::ISD::ATOMIC_LOAD_UMIN_32, llvm::ISD::ATOMIC_LOAD_UMIN_64, llvm::ISD::ATOMIC_LOAD_UMIN_8, llvm::ISD::ATOMIC_LOAD_XOR_16, llvm::ISD::ATOMIC_LOAD_XOR_32, llvm::ISD::ATOMIC_LOAD_XOR_64, llvm::ISD::ATOMIC_LOAD_XOR_8, llvm::ISD::ATOMIC_SWAP_16, llvm::ISD::ATOMIC_SWAP_32, llvm::ISD::ATOMIC_SWAP_64, llvm::ISD::ATOMIC_SWAP_8, llvm::ISD::BasicBlock, llvm::Call, llvm::ISD::CALL, llvm::ISD::Constant, llvm::ISD::ConstantFP, llvm::ISD::ConstantPool, CP, llvm::ISD::DBG_STOPPOINT, llvm::ISD::FrameIndex, llvm::LSBaseSDNode::getAddressingMode(), llvm::ConstantPoolSDNode::getAlignment(), llvm::SelectionDAG::getArgFlags(), llvm::SelectionDAG::getBasicBlock(), llvm::CallSDNode::getCallingConv(), llvm::DbgStopPointSDNode::getColumn(), llvm::DbgStopPointSDNode::getCompileUnit(), llvm::ConstantPoolSDNode::getConstVal(), llvm::LoadSDNode::getExtensionType(), llvm::GlobalAddressSDNode::getGlobal(), llvm::DbgStopPointSDNode::getLine(), llvm::ConstantPoolSDNode::getMachineCPVal(), llvm::MemSDNode::getMemoryVT(), llvm::SDNode::getNumOperands(), llvm::ConstantPoolSDNode::getOffset(), llvm::GlobalAddressSDNode::getOffset(), llvm::SDNode::getOpcode(), llvm::MVT::getRawBits(), llvm::MemSDNode::getRawFlags(), llvm::SDNode::getVTList(), llvm::ISD::GlobalAddress, llvm::ISD::GlobalTLSAddress, llvm::ConstantPoolSDNode::isMachineConstantPoolEntry(), llvm::StoreSDNode::isTruncatingStore(), llvm::CallSDNode::isVarArg(), llvm::ISD::JumpTable, llvm::ISD::LOAD, llvm::ISD::MEMOPERAND, llvm::SDNode::op_begin(), llvm::MachineMemOperand::Profile(), llvm::ISD::Register, llvm::ISD::SRCVALUE, llvm::ISD::STORE, llvm::ISD::TargetConstant, llvm::ISD::TargetConstantFP, llvm::ISD::TargetConstantPool, llvm::ISD::TargetFrameIndex, llvm::ISD::TargetGlobalAddress, llvm::ISD::TargetGlobalTLSAddress, and llvm::ISD::TargetJumpTable.

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

Definition at line 347 of file SelectionDAG.cpp.

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

Referenced by llvm::SelectionDAG::getArgFlags(), llvm::SelectionDAG::getAtomic(), llvm::SelectionDAG::getBasicBlock(), llvm::SelectionDAG::getCall(), llvm::SelectionDAG::getConstant(), llvm::SelectionDAG::getConstantFP(), llvm::SelectionDAG::getConstantPool(), llvm::SelectionDAG::getFrameIndex(), llvm::SelectionDAG::getGlobalAddress(), llvm::SelectionDAG::getIndexedStore(), llvm::SelectionDAG::getJumpTable(), llvm::SelectionDAG::getLabel(), llvm::SelectionDAG::getLoad(), llvm::SelectionDAG::getMemOperand(), llvm::SelectionDAG::getNode(), llvm::SelectionDAG::getNodeIfExists(), llvm::SelectionDAG::getRegister(), llvm::SelectionDAG::getSrcValue(), llvm::SelectionDAG::getStore(), llvm::SelectionDAG::getTruncStore(), llvm::SelectionDAG::MorphNodeTo(), and llvm::SDNode::Profile().

static void AddNodeIDOpcode	(	FoldingSetNodeID &	ID,
		unsigned	OpC
	)			[static]

AddNodeIDOpcode - Add the node opcode to the NodeID data.

Definition at line 317 of file SelectionDAG.cpp.

References llvm::FoldingSetNodeID::AddInteger().

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 339 of file SelectionDAG.cpp.

References llvm::FoldingSetNodeID::AddInteger(), llvm::FoldingSetNodeID::AddPointer(), llvm::SDValue::getResNo(), llvm::SDUse::getSDValue(), and llvm::SDUse::getVal().

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

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

Definition at line 329 of file SelectionDAG.cpp.

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

Referenced by AddNodeIDNode().

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 323 of file SelectionDAG.cpp.

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

Referenced by AddNodeIDNode().

static void DumpNodes	(	const SDNode *	N,
		unsigned	indent,
		const SelectionDAG *	G
	)			[static]

Definition at line 5371 of file SelectionDAG.cpp.

static unsigned encodeMemSDNodeFlags	(	bool	isVolatile,
		unsigned	Alignment
	)			[static]

encodeMemSDNodeFlags - Generic routine for computing a value for use in the CSE map that carries both alignment and volatility information.

Definition at line 509 of file SelectionDAG.cpp.

References llvm::Log2_32().

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

static void findPredecessor	(	SDNode *	N,
		const SDNode *	P,
		bool &	found,
		SmallPtrSet< SDNode *, 32 > &	Visited
	)			[static]

Definition at line 4851 of file SelectionDAG.cpp.

References llvm::SDValue::getNode(), llvm::SDNode::getNumOperands(), llvm::SDNode::getOperand(), and llvm::SmallPtrSet< PtrType, SmallSize >::insert().

Referenced by llvm::SDNode::isPredecessorOf().

static SDValue getMemBasePlusOffset	(	SDValue	Base,
		unsigned	Offset,
		SelectionDAG &	DAG
	)			[static]

getMemBasePlusOffset - Returns base and offset node for the

Definition at line 2809 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,
		SDValue	Chain,
		SDValue	Dst,
		SDValue	Src,
		uint64_t	Size,
		unsigned	Align,
		bool	AlwaysInline,
		const Value *	DstSV,
		uint64_t	DstSVOff,
		const Value *	SrcSV,
		uint64_t	SrcSVOff
	)			[static]

Definition at line 2924 of file SelectionDAG.cpp.

References llvm::SelectionDAG::getLoad(), llvm::TargetLowering::getMaxStoresPerMemcpy(), getMemBasePlusOffset(), getMemsetStringVal(), llvm::SelectionDAG::getNode(), llvm::MVT::getSizeInBits(), llvm::SelectionDAG::getStore(), llvm::SelectionDAG::getTargetLoweringInfo(), llvm::MVT::isVector(), MeetsMaxMemopRequirement(), llvm::MVT::Other, llvm::SmallVectorImpl< T >::push_back(), llvm::SmallVectorImpl< T >::size(), llvm::SPII::Store, TLI, and llvm::ISD::TokenFactor.

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

static SDValue getMemmoveLoadsAndStores	(	SelectionDAG &	DAG,
		SDValue	Chain,
		SDValue	Dst,
		SDValue	Src,
		uint64_t	Size,
		unsigned	Align,
		bool	AlwaysInline,
		const Value *	DstSV,
		uint64_t	DstSVOff,
		const Value *	SrcSV,
		uint64_t	SrcSVOff
	)			[static]

Definition at line 2982 of file SelectionDAG.cpp.

References llvm::SmallVectorImpl< T >::clear(), llvm::SelectionDAG::getLoad(), llvm::TargetLowering::getMaxStoresPerMemmove(), getMemBasePlusOffset(), llvm::SelectionDAG::getNode(), llvm::MVT::getSizeInBits(), llvm::SelectionDAG::getStore(), llvm::SelectionDAG::getTargetLoweringInfo(), llvm::SDValue::getValue(), MeetsMaxMemopRequirement(), llvm::MVT::Other, llvm::SmallVectorImpl< T >::push_back(), llvm::SmallVectorImpl< T >::size(), llvm::SPII::Store, TLI, and llvm::ISD::TokenFactor.

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

static SDValue getMemsetStores	(	SelectionDAG &	DAG,
		SDValue	Chain,
		SDValue	Dst,
		SDValue	Src,
		uint64_t	Size,
		unsigned	Align,
		const Value *	DstSV,
		uint64_t	DstSVOff
	)			[static]

Definition at line 3040 of file SelectionDAG.cpp.

References llvm::TargetLowering::getMaxStoresPerMemset(), getMemBasePlusOffset(), getMemsetValue(), llvm::MVT::getSizeInBits(), llvm::SelectionDAG::getTargetLoweringInfo(), MeetsMaxMemopRequirement(), llvm::MVT::Other, llvm::SmallVectorImpl< T >::push_back(), llvm::SmallVectorImpl< T >::size(), llvm::SPII::Store, TLI, and llvm::ISD::TokenFactor.

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

static SDValue getMemsetStringVal	(	MVT	VT,
		SelectionDAG &	DAG,
		const TargetLowering &	TLI,
		std::string &	Str,
		unsigned	Offset
	)			[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 2781 of file SelectionDAG.cpp.

References llvm::ISD::BIT_CONVERT, llvm::MVT::f32, llvm::SelectionDAG::getConstant(), llvm::SelectionDAG::getNode(), llvm::MVT::getSizeInBits(), llvm::MVT::getVectorElementType(), llvm::MVT::getVectorNumElements(), llvm::MVT::getVectorVT(), llvm::MVT::i32, llvm::MVT::i64, llvm::MVT::isInteger(), llvm::TargetLowering::isLittleEndian(), llvm::MVT::isVector(), and Val.

Referenced by getMemcpyLoadsAndStores().

static SDValue getMemsetValue	(	SDValue	Value,
		MVT	VT,
		SelectionDAG &	DAG
	)			[static]

getMemsetValue - Vectorized representation of the memset value operand.

Definition at line 2751 of file SelectionDAG.cpp.

References llvm::CallingConv::C, llvm::SelectionDAG::getConstant(), llvm::SelectionDAG::getConstantFP(), llvm::SelectionDAG::getNode(), llvm::MVT::getSizeInBits(), llvm::MVT::getVectorElementType(), llvm::MVT::i8, llvm::MVT::isInteger(), llvm::MVT::isVector(), llvm::ISD::OR, llvm::ISD::SHL, Val, and llvm::ISD::ZERO_EXTEND.

Referenced by getMemsetStores().

static bool isMemSrcFromString	(	SDValue	Src,
		std::string &	Str
	)			[static]

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

Definition at line 2817 of file SelectionDAG.cpp.

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

Referenced by MeetsMaxMemopRequirement().

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 239 of file SelectionDAG.cpp.

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

Referenced by llvm::ISD::getSetCCAndOperation(), and llvm::ISD::getSetCCOrOperation().

static SDVTList makeVTList	(	const MVT *	VTs,
		unsigned	NumVTs
	)			[static]

makeVTList - Return an instance of the SDVTList struct initialized with the specified members.

Definition at line 46 of file SelectionDAG.cpp.

Referenced by llvm::SelectionDAG::getNode(), and llvm::SelectionDAG::getVTList().

static bool MeetsMaxMemopRequirement	(	std::vector< MVT > &	MemOps,
		SDValue	Dst,
		SDValue	Src,
		unsigned	Limit,
		uint64_t	Size,
		unsigned &	Align,
		std::string &	Str,
		bool &	isSrcStr,
		SelectionDAG &	DAG,
		const TargetLowering &	TLI
	)			[static]

MeetsMaxMemopRequirement - Determines if the number of memory ops required to replace the memset / memcpy is below the threshold. It also returns the types of the sequence of memory ops to perform memset / memcpy.

Definition at line 2842 of file SelectionDAG.cpp.

References llvm::TargetLowering::allowsUnalignedMemoryAccesses(), llvm::MVT::bitsGT(), FI, llvm::ISD::FrameIndex, llvm::TargetData::getABITypeAlignment(), llvm::MachineFunction::getFrameInfo(), llvm::SelectionDAG::getMachineFunction(), llvm::MachineFrameInfo::getObjectAlignment(), llvm::SDValue::getOpcode(), llvm::TargetLowering::getOptimalMemOpType(), llvm::MVT::getSimpleVT(), llvm::MVT::getSizeInBits(), llvm::TargetLowering::getTargetData(), llvm::MVT::getTypeForMVT(), llvm::MVT::i16, llvm::MVT::i32, llvm::MVT::i64, llvm::MVT::i8, llvm::MVT::iAny, llvm::MachineFrameInfo::isFixedObjectIndex(), llvm::MVT::isInteger(), isMemSrcFromString(), llvm::TargetLowering::isTypeLegal(), llvm::MVT::isVector(), MFI, and llvm::MachineFrameInfo::setObjectAlignment().

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

static const fltSemantics* MVTToAPFloatSemantics

(

MVT

VT

)

[static]

Definition at line 51 of file SelectionDAG.cpp.

References llvm::MVT::getSimpleVT().

Referenced by llvm::SelectionDAG::getNode(), and llvm::ConstantFPSDNode::isValueValidForType().