ScheduleDAGInstrs.cpp File Reference

#include "llvm/CodeGen/ScheduleDAGInstrs.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineMemOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/PseudoSourceValue.h"
#include "llvm/CodeGen/RegisterPressure.h"
#include "llvm/CodeGen/ScheduleDFS.h"
#include "llvm/IR/Operator.h"
#include "llvm/MC/MCInstrItineraries.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Format.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetSubtargetInfo.h"
#include <queue>

Include dependency graph for ScheduleDAGInstrs.cpp:

Go to the source code of this file.

Classes
class	llvm::SchedDFSImpl
	Internal state used to compute SchedDFSResult. More...
struct	llvm::SchedDFSImpl::RootData
Namespaces
namespace	llvm
	List of target independent CodeGen pass IDs.
Defines
#define	DEBUG_TYPE   "misched"
Typedefs
typedef PointerUnion< const Value *, const PseudoSourceValue * >	ValueType
typedef SmallVector < PointerIntPair< ValueType, 1, bool >, 4 >	UnderlyingObjectsVector
Functions
static const Value *	getUnderlyingObjectFromInt (const Value *V)
static void	getUnderlyingObjects (const Value *V, SmallVectorImpl< Value * > &Objects)
static void	getUnderlyingObjectsForInstr (const MachineInstr *MI, const MachineFrameInfo *MFI, UnderlyingObjectsVector &Objects)
static bool	isGlobalMemoryObject (AliasAnalysis *AA, MachineInstr *MI)
static bool	isUnsafeMemoryObject (MachineInstr *MI, const MachineFrameInfo *MFI)
static bool	MIsNeedChainEdge (AliasAnalysis *AA, const MachineFrameInfo *MFI, MachineInstr *MIa, MachineInstr *MIb)
static unsigned	iterateChainSucc (AliasAnalysis *AA, const MachineFrameInfo *MFI, SUnit *SUa, SUnit *SUb, SUnit *ExitSU, unsigned *Depth, SmallPtrSetImpl< const SUnit * > &Visited)
static void	adjustChainDeps (AliasAnalysis *AA, const MachineFrameInfo *MFI, SUnit *SU, SUnit *ExitSU, std::set< SUnit * > &CheckList, unsigned LatencyToLoad)
static void	addChainDependency (AliasAnalysis *AA, const MachineFrameInfo *MFI, SUnit *SUa, SUnit *SUb, std::set< SUnit * > &RejectList, unsigned TrueMemOrderLatency=0, bool isNormalMemory=false)
static bool	hasDataSucc (const SUnit *SU)
raw_ostream &	llvm::operator<< (raw_ostream &OS, const ILPValue &Val)
Variables
static cl::opt< bool >	EnableAASchedMI ("enable-aa-sched-mi", cl::Hidden, cl::ZeroOrMore, cl::init(false), cl::desc("Enable use of AA during MI GAD construction"))
static cl::opt< bool >	UseTBAA ("use-tbaa-in-sched-mi", cl::Hidden, cl::init(true), cl::desc("Enable use of TBAA during MI GAD construction"))

---

Define Documentation

#define DEBUG_TYPE   "misched"

Definition at line 43 of file ScheduleDAGInstrs.cpp.

---

Typedef Documentation

typedef SmallVector<PointerIntPair<ValueType, 1, bool>, 4> UnderlyingObjectsVector

Definition at line 129 of file ScheduleDAGInstrs.cpp.

typedef PointerUnion<const Value *, const PseudoSourceValue *> ValueType

Definition at line 127 of file ScheduleDAGInstrs.cpp.

---

Function Documentation

static void addChainDependency	(	AliasAnalysis *	AA,
		const MachineFrameInfo *	MFI,
		SUnit *	SUa,
		SUnit *	SUb,
		std::set< SUnit * > &	RejectList,
		unsigned	TrueMemOrderLatency = 0,
		bool	isNormalMemory = false
	)		[inline, static]

Check whether two objects need a chain edge, if so, add it otherwise remember the rejected SU.

Definition at line 660 of file ScheduleDAGInstrs.cpp.

References llvm::SUnit::addPred(), llvm::SDep::Barrier, llvm::dbgs(), DEBUG, llvm::SUnit::getInstr(), llvm::SDep::MayAliasMem, MIsNeedChainEdge(), llvm::SUnit::NodeNum, and llvm::SDep::setLatency().

Referenced by llvm::ScheduleDAGInstrs::buildSchedGraph().

static void adjustChainDeps	(	AliasAnalysis *	AA,
		const MachineFrameInfo *	MFI,
		SUnit *	SU,
		SUnit *	ExitSU,
		std::set< SUnit * > &	CheckList,
		unsigned	LatencyToLoad
	)		[static]

This function assumes that "downward" from SU there exist tail/leaf of already constructed DAG. It iterates downward and checks whether SU can be aliasing any node dominated by it.

Definition at line 629 of file ScheduleDAGInstrs.cpp.

References llvm::SUnit::getInstr(), I, llvm::ARM_PROC::IE, iterateChainSucc(), llvm::SDep::MayAliasMem, MIsNeedChainEdge(), and llvm::SDep::setLatency().

Referenced by llvm::ScheduleDAGInstrs::buildSchedGraph().

static const Value* getUnderlyingObjectFromInt

(

const Value *

V

)

[static]

getUnderlyingObjectFromInt - This is the function that does the work of looking through basic ptrtoint+arithmetic+inttoptr sequences.

Definition at line 71 of file ScheduleDAGInstrs.cpp.

References llvm::Operator::getOpcode(), llvm::Value::getType(), and llvm::Type::isIntegerTy().

Referenced by getUnderlyingObjects().

static void getUnderlyingObjects	(	const Value *	V,
		SmallVectorImpl< Value * > &	Objects
	)		[static]

getUnderlyingObjects - This is a wrapper around GetUnderlyingObjects and adds support for basic ptrtoint+arithmetic+inttoptr sequences.

Definition at line 99 of file ScheduleDAGInstrs.cpp.

References llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::SmallVectorBase::empty(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::Operator::getOpcode(), llvm::Value::getType(), getUnderlyingObjectFromInt(), llvm::GetUnderlyingObjects(), I, llvm::ARM_PROC::IE, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::IntToPtr, llvm::Type::isPointerTy(), llvm::SmallVectorImpl< T >::pop_back_val(), and llvm::SmallVectorTemplateBase< T, isPodLike >::push_back().

Referenced by getUnderlyingObjectsForInstr(), and isUnsafeMemoryObject().

static void getUnderlyingObjectsForInstr	(	const MachineInstr *	MI,
		const MachineFrameInfo *	MFI,
		UnderlyingObjectsVector &	Objects
	)		[static]

getUnderlyingObjectsForInstr - If this machine instr has memory reference information and it can be tracked to a normal reference to a known object, return the Value for that object.

Definition at line 134 of file ScheduleDAGInstrs.cpp.

References llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::SmallVectorImpl< T >::clear(), llvm::SmallVectorTemplateCommon< T, typename >::end(), getUnderlyingObjects(), llvm::MachineInstr::hasOneMemOperand(), I, llvm::ARM_PROC::IE, llvm::isIdentifiedObject(), llvm::MachineInstr::memoperands_begin(), and llvm::SmallVectorTemplateBase< T, isPodLike >::push_back().

Referenced by llvm::ScheduleDAGInstrs::buildSchedGraph().

static bool hasDataSucc

(

const SUnit *

SU

)

[static]

Definition at line 1449 of file ScheduleDAGInstrs.cpp.

References llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::SDep::Data, llvm::SmallVectorTemplateCommon< T, typename >::end(), and llvm::SUnit::Succs.

Referenced by llvm::SchedDFSResult::compute().

static bool isGlobalMemoryObject	(	AliasAnalysis *	AA,
		MachineInstr *	MI
	)		[inline, static]

Return true if MI is an instruction we are unable to reason about (like a call or something with unmodeled side effects).

Definition at line 461 of file ScheduleDAGInstrs.cpp.

References llvm::MachineInstr::hasOrderedMemoryRef(), llvm::MachineInstr::hasUnmodeledSideEffects(), llvm::MachineInstr::isCall(), llvm::MachineInstr::isInvariantLoad(), and llvm::MachineInstr::mayLoad().

Referenced by llvm::ScheduleDAGInstrs::buildSchedGraph(), and iterateChainSucc().

static bool isUnsafeMemoryObject	(	MachineInstr *	MI,
		const MachineFrameInfo *	MFI
	)		[inline, static]

Definition at line 471 of file ScheduleDAGInstrs.cpp.

References llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::SmallVectorTemplateCommon< T, typename >::end(), getUnderlyingObjects(), llvm::MachineInstr::hasUnmodeledSideEffects(), I, llvm::ARM_PROC::IE, llvm::isIdentifiedObject(), llvm::MachineInstr::memoperands_begin(), and llvm::MachineInstr::memoperands_empty().

Referenced by MIsNeedChainEdge().

static unsigned iterateChainSucc	(	AliasAnalysis *	AA,
		const MachineFrameInfo *	MFI,
		SUnit *	SUa,
		SUnit *	SUb,
		SUnit *	ExitSU,
		unsigned *	Depth,
		SmallPtrSetImpl< const SUnit * > &	Visited
	)		[static]

This recursive function iterates over chain deps of SUb looking for "latest" node that needs a chain edge to SUa.

Definition at line 584 of file ScheduleDAGInstrs.cpp.

References llvm::SUnit::addPred(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::SUnit::getInstr(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), isGlobalMemoryObject(), llvm::SUnit::isSucc(), llvm::SDep::MayAliasMem, MIsNeedChainEdge(), and llvm::SUnit::Succs.

Referenced by adjustChainDeps().

static bool MIsNeedChainEdge	(	AliasAnalysis *	AA,
		const MachineFrameInfo *	MFI,
		MachineInstr *	MIa,
		MachineInstr *	MIb
	)		[static]

This returns true if the two MIs need a chain edge betwee them. If these are not even memory operations, we still may need chain deps between them. The question really is - could these two MIs be reordered during scheduling from memory dependency point of view.

Definition at line 511 of file ScheduleDAGInstrs.cpp.

References llvm::AliasAnalysis::alias(), llvm::TargetInstrInfo::areMemAccessesTriviallyDisjoint(), llvm::MachineMemOperand::getAAInfo(), llvm::TargetSubtargetInfo::getInstrInfo(), llvm::MachineMemOperand::getOffset(), llvm::MachineInstr::getParent(), llvm::MachineBasicBlock::getParent(), llvm::MachineMemOperand::getSize(), llvm::MachineFunction::getSubtarget(), llvm::MachineMemOperand::getValue(), llvm::MachineInstr::hasOneMemOperand(), isUnsafeMemoryObject(), llvm::MachineInstr::mayLoad(), llvm::MachineInstr::mayStore(), llvm::MachineInstr::memoperands_begin(), llvm::AliasAnalysis::NoAlias, TII, and UseTBAA.

Referenced by addChainDependency(), adjustChainDeps(), and iterateChainSucc().

---

Variable Documentation

cl::opt<bool> EnableAASchedMI("enable-aa-sched-mi", cl::Hidden, cl::ZeroOrMore, cl::init(false), cl::desc("Enable use of AA during MI GAD construction")) [static]

Referenced by llvm::ScheduleDAGInstrs::buildSchedGraph().

cl::opt<bool> UseTBAA("use-tbaa-in-sched-mi", cl::Hidden, cl::init(true), cl::desc("Enable use of TBAA during MI GAD construction")) [static]

Referenced by MIsNeedChainEdge().