#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/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:

Classes
class	llvm::SchedDFSImpl
	Internal state used to compute SchedDFSResult. More...

Namespaces
	llvm
	List of target independent CodeGen pass IDs.

Macros
#define	DEBUG_TYPE "misched"

Typedefs
typedef SmallVector < PointerIntPair< const Value *, 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, SmallPtrSet< const SUnit *, 16 > &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"))

Macro Definition Documentation

#define DEBUG_TYPE "misched"

Definition at line 15 of file ScheduleDAGInstrs.cpp.

Typedef Documentation

typedef SmallVector<PointerIntPair<const Value *, 1, bool>, 4> UnderlyingObjectsVector

Definition at line 122 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`
	)

inlinestatic

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

Definition at line 640 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 609 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 65 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 93 of file ScheduleDAGInstrs.cpp.

References llvm::SmallVectorTemplateCommon< T >::begin(), llvm::SmallVectorBase::empty(), llvm::SmallVectorTemplateCommon< T >::end(), llvm::Operator::getOpcode(), llvm::Value::getType(), getUnderlyingObjectFromInt(), llvm::GetUnderlyingObjects(), I, llvm::ARM_PROC::IE, llvm::SmallPtrSet< PtrType, SmallSize >::insert(), llvm::Type::isPointerTy(), llvm::SmallVectorImpl< T >::pop_back_val(), and llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::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 127 of file ScheduleDAGInstrs.cpp.

References llvm::SmallVectorTemplateCommon< T >::begin(), llvm::SmallVectorImpl< T >::clear(), llvm::SmallVectorTemplateCommon< T >::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 1250 of file ScheduleDAGInstrs.cpp.

References llvm::SDep::Data, and llvm::SUnit::Succs.

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

static bool isGlobalMemoryObject	(	AliasAnalysis *	AA,
		MachineInstr *	MI
	)

inlinestatic

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 451 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
	)

inlinestatic

Definition at line 461 of file ScheduleDAGInstrs.cpp.

References llvm::SmallVectorTemplateCommon< T >::begin(), llvm::SmallVectorTemplateCommon< T >::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,
		SmallPtrSet< const SUnit *, 16 > &	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 564 of file ScheduleDAGInstrs.cpp.

References llvm::SUnit::addPred(), llvm::SUnit::getInstr(), I, llvm::SmallPtrSet< PtrType, SmallSize >::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 503 of file ScheduleDAGInstrs.cpp.

References llvm::AliasAnalysis::alias(), llvm::MachineMemOperand::getOffset(), llvm::MachineMemOperand::getSize(), llvm::MachineMemOperand::getTBAAInfo(), llvm::MachineMemOperand::getValue(), llvm::MachineInstr::hasOneMemOperand(), isUnsafeMemoryObject(), llvm_unreachable, llvm::MachineInstr::mayStore(), llvm::MachineInstr::memoperands_begin(), and llvm::AliasAnalysis::NoAlias.

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().

Classes

Namespaces

Macros

Typedefs

Functions

Variables

Macro Definition Documentation

Typedef Documentation

Function Documentation

Variable Documentation