#include "llvm/CodeGen/MachineScheduler.h"
#include "llvm/ADT/OwningPtr.h"
#include "llvm/ADT/PriorityQueue.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/RegisterClassInfo.h"
#include "llvm/CodeGen/ScheduleDFS.h"
#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/GraphWriter.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
#include <queue>

Include dependency graph for MachineScheduler.cpp:

Classes
struct	llvm::GraphTraits< ScheduleDAGMI * >

struct	llvm::DOTGraphTraits< ScheduleDAGMI * >

Namespaces
	llvm
	List of target independent CodeGen pass IDs.

Macros
#define	DEBUG_TYPE "misched"

Functions
cl::opt< bool >	llvm::ForceTopDown ("misched-topdown", cl::Hidden, cl::desc("Force top-down list scheduling"))

cl::opt< bool >	llvm::ForceBottomUp ("misched-bottomup", cl::Hidden, cl::desc("Force bottom-up list scheduling"))

	INITIALIZE_PASS_BEGIN (MachineScheduler,"misched","Machine Instruction Scheduler", false, false) INITIALIZE_PASS_END(MachineScheduler

static ScheduleDAGInstrs *	useDefaultMachineSched (MachineSchedContext *C)

static ScheduleDAGInstrs *	createGenericSched (MachineSchedContext *C)

static MachineBasicBlock::const_iterator	priorNonDebug (MachineBasicBlock::const_iterator I, MachineBasicBlock::const_iterator Beg)
	Decrement this iterator until reaching the top or a non-debug instr. More...

static MachineBasicBlock::iterator	priorNonDebug (MachineBasicBlock::iterator I, MachineBasicBlock::const_iterator Beg)
	Non-const version. More...

static MachineBasicBlock::const_iterator	nextIfDebug (MachineBasicBlock::const_iterator I, MachineBasicBlock::const_iterator End)

static MachineBasicBlock::iterator	nextIfDebug (MachineBasicBlock::iterator I, MachineBasicBlock::const_iterator End)
	Non-const version. More...

static bool	tryLess (int TryVal, int CandVal, GenericScheduler::SchedCandidate &TryCand, GenericScheduler::SchedCandidate &Cand, GenericScheduler::CandReason Reason)
	Return true if this heuristic determines order. More...

static bool	tryGreater (int TryVal, int CandVal, GenericScheduler::SchedCandidate &TryCand, GenericScheduler::SchedCandidate &Cand, GenericScheduler::CandReason Reason)

static bool	tryPressure (const PressureChange &TryP, const PressureChange &CandP, GenericScheduler::SchedCandidate &TryCand, GenericScheduler::SchedCandidate &Cand, GenericScheduler::CandReason Reason)

static unsigned	getWeakLeft (const SUnit *SU, bool isTop)

static int	biasPhysRegCopy (const SUnit *SU, bool isTop)

static bool	tryLatency (GenericScheduler::SchedCandidate &TryCand, GenericScheduler::SchedCandidate &Cand, GenericScheduler::SchedBoundary &Zone)

static void	tracePick (const GenericScheduler::SchedCandidate &Cand, bool IsTop)

static ScheduleDAGInstrs *	createILPMaxScheduler (MachineSchedContext *C)

static ScheduleDAGInstrs *	createILPMinScheduler (MachineSchedContext *C)

static ScheduleDAGInstrs *	createInstructionShuffler (MachineSchedContext *C)

Variables
static cl::opt< bool >	ViewMISchedDAGs ("view-misched-dags", cl::Hidden, cl::desc("Pop up a window to show MISched dags after they are processed"))

static cl::opt< unsigned >	MISchedCutoff ("misched-cutoff", cl::Hidden, cl::desc("Stop scheduling after N instructions"), cl::init(~0U))

static cl::opt< bool >	EnableRegPressure ("misched-regpressure", cl::Hidden, cl::desc("Enable register pressure scheduling."), cl::init(true))

static cl::opt< bool >	EnableCyclicPath ("misched-cyclicpath", cl::Hidden, cl::desc("Enable cyclic critical path analysis."), cl::init(true))

static cl::opt< bool >	EnableLoadCluster ("misched-cluster", cl::Hidden, cl::desc("Enable load clustering."), cl::init(true))

static cl::opt< bool >	EnableMacroFusion ("misched-fusion", cl::Hidden, cl::desc("Enable scheduling for macro fusion."), cl::init(true))

static cl::opt< bool >	VerifyScheduling ("verify-misched", cl::Hidden, cl::desc("Verify machine instrs before and after machine scheduling"))

static const unsigned	MinSubtreeSize = 8

	misched

Machine Instruction	Scheduler

Machine Instruction	false

static cl::opt < MachineSchedRegistry::ScheduleDAGCtor, false, RegisterPassParser < MachineSchedRegistry > >	MachineSchedOpt ("misched", cl::init(&useDefaultMachineSched), cl::Hidden, cl::desc("Machine instruction scheduler to use"))
	MachineSchedOpt allows command line selection of the scheduler. More...

static MachineSchedRegistry	DefaultSchedRegistry ("default","Use the target's default scheduler choice.", useDefaultMachineSched)

static MachineSchedRegistry	GenericSchedRegistry ("converge","Standard converging scheduler.", createGenericSched)

static MachineSchedRegistry	ILPMaxRegistry ("ilpmax","Schedule bottom-up for max ILP", createILPMaxScheduler)

static MachineSchedRegistry	ILPMinRegistry ("ilpmin","Schedule bottom-up for min ILP", createILPMinScheduler)

static MachineSchedRegistry	ShufflerRegistry ("shuffle","Shuffle machine instructions alternating directions", createInstructionShuffler)

Macro Definition Documentation

#define DEBUG_TYPE "misched"

Definition at line 15 of file MachineScheduler.cpp.

Function Documentation

static int biasPhysRegCopy	(	const SUnit *	SU,
		bool	isTop
	)

static

Minimize physical register live ranges. Regalloc wants them adjacent to their physreg def/use.

FIXME: This is an unnecessary check on the critical path. Most are root/leaf copies which can be prescheduled. The rest (e.g. x86 MUL) could be bundled with the operation that produces or consumes the physreg. We'll do this when regalloc has support for parallel copies.

Definition at line 2389 of file MachineScheduler.cpp.

References llvm::SUnit::getInstr(), llvm::MachineInstr::getOperand(), llvm::MachineOperand::getReg(), llvm::MachineInstr::isCopy(), llvm::TargetRegisterInfo::isPhysicalRegister(), llvm::A64CC::MI, llvm::SUnit::NumPredsLeft, and llvm::SUnit::NumSuccsLeft.

static ScheduleDAGInstrs * createGenericSched ( MachineSchedContext * C )

static

Forward declare the standard machine scheduler. This will be used as the default scheduler if the target does not set a default.

Create the standard converging machine scheduler. This will be used as the default scheduler if the target does not set a default.

Definition at line 2834 of file MachineScheduler.cpp.

References llvm::ScheduleDAGMI::addMutation(), llvm::TargetInstrInfo::enableClusterLoads(), EnableLoadCluster, EnableMacroFusion, llvm::ScheduleDAG::TII, and llvm::ScheduleDAG::TRI.

static ScheduleDAGInstrs* createILPMaxScheduler ( MachineSchedContext * C )

static

Definition at line 2951 of file MachineScheduler.cpp.

static ScheduleDAGInstrs* createILPMinScheduler ( MachineSchedContext * C )

static

Definition at line 2954 of file MachineScheduler.cpp.

static ScheduleDAGInstrs* createInstructionShuffler ( MachineSchedContext * C )

static

Definition at line 3039 of file MachineScheduler.cpp.

References llvm::ForceBottomUp, and llvm::ForceTopDown.

static unsigned getWeakLeft	(	const SUnit *	SU,
		bool	isTop
	)

static

Definition at line 2378 of file MachineScheduler.cpp.

References llvm::SUnit::WeakPredsLeft, and llvm::SUnit::WeakSuccsLeft.

INITIALIZE_PASS_BEGIN	(	MachineScheduler	,
		"misched"	,
		"Machine Instruction Scheduler"	,
		false	,
		false
	)

static MachineBasicBlock::const_iterator nextIfDebug	(	MachineBasicBlock::const_iterator	I,
		MachineBasicBlock::const_iterator	End
	)

static

If this iterator is a debug value, increment until reaching the End or a non-debug instruction.

Definition at line 191 of file MachineScheduler.cpp.

References I.

Referenced by llvm::ScheduleDAGMI::initQueues(), nextIfDebug(), llvm::ScheduleDAGMI::scheduleMI(), and llvm::ScheduleDAGMI::updatePressureDiffs().

static MachineBasicBlock::iterator nextIfDebug	(	MachineBasicBlock::iterator	I,
		MachineBasicBlock::const_iterator	End
	)

static

Non-const version.

Definition at line 202 of file MachineScheduler.cpp.

References nextIfDebug().

static MachineBasicBlock::const_iterator priorNonDebug	(	MachineBasicBlock::const_iterator	I,
		MachineBasicBlock::const_iterator	Beg
	)

static

Decrement this iterator until reaching the top or a non-debug instr.

Definition at line 170 of file MachineScheduler.cpp.

References I.

Referenced by priorNonDebug(), and llvm::ScheduleDAGMI::scheduleMI().

static MachineBasicBlock::iterator priorNonDebug	(	MachineBasicBlock::iterator	I,
		MachineBasicBlock::const_iterator	Beg
	)

static

Non-const version.

Definition at line 182 of file MachineScheduler.cpp.

References priorNonDebug().

static void tracePick	(	const GenericScheduler::SchedCandidate &	Cand,
		bool	IsTop
	)

static

Definition at line 2678 of file MachineScheduler.cpp.

References llvm::dbgs(), and DEBUG.

static bool tryGreater	(	int	TryVal,
		int	CandVal,
		GenericScheduler::SchedCandidate &	TryCand,
		GenericScheduler::SchedCandidate &	Cand,
		GenericScheduler::CandReason	Reason
	)

static

Definition at line 2337 of file MachineScheduler.cpp.

Referenced by tryLatency(), and tryPressure().

static bool tryLatency	(	GenericScheduler::SchedCandidate &	TryCand,
		GenericScheduler::SchedCandidate &	Cand,
		GenericScheduler::SchedBoundary &	Zone
	)

static

Definition at line 2410 of file MachineScheduler.cpp.

References tryGreater(), and tryLess().

static bool tryLess	(	int	TryVal,
		int	CandVal,
		GenericScheduler::SchedCandidate &	TryCand,
		GenericScheduler::SchedCandidate &	Cand,
		GenericScheduler::CandReason	Reason
	)

static

Return true if this heuristic determines order.

Definition at line 2320 of file MachineScheduler.cpp.

Referenced by tryLatency(), and tryPressure().

static bool tryPressure	(	const PressureChange &	TryP,
		const PressureChange &	CandP,
		GenericScheduler::SchedCandidate &	TryCand,
		GenericScheduler::SchedCandidate &	Cand,
		GenericScheduler::CandReason	Reason
	)

static

Definition at line 2354 of file MachineScheduler.cpp.

References llvm::PressureChange::getPSetOrMax(), llvm::PressureChange::getUnitInc(), std::swap(), tryGreater(), and tryLess().

static ScheduleDAGInstrs* useDefaultMachineSched ( MachineSchedContext * C )

static

A dummy default scheduler factory indicates whether the scheduler is overridden on the command line.

Definition at line 148 of file MachineScheduler.cpp.

Variable Documentation

MachineSchedRegistry DefaultSchedRegistry("default","Use the target's default scheduler choice.", useDefaultMachineSched)

static

cl::opt<bool> EnableCyclicPath("misched-cyclicpath", cl::Hidden, cl::desc("Enable cyclic critical path analysis."), cl::init(true))

static

cl::opt<bool> EnableLoadCluster("misched-cluster", cl::Hidden, cl::desc("Enable load clustering."), cl::init(true))

static

Referenced by createGenericSched().

cl::opt<bool> EnableMacroFusion("misched-fusion", cl::Hidden, cl::desc("Enable scheduling for macro fusion."), cl::init(true))

static

Referenced by createGenericSched().

cl::opt<bool> EnableRegPressure("misched-regpressure", cl::Hidden, cl::desc("Enable register pressure scheduling."), cl::init(true))

static

Machine Instruction false

Definition at line 123 of file MachineScheduler.cpp.

MachineSchedRegistry GenericSchedRegistry("converge","Standard converging scheduler.", createGenericSched)

static

MachineSchedRegistry ILPMaxRegistry("ilpmax","Schedule bottom-up for max ILP", createILPMaxScheduler)

static

MachineSchedRegistry ILPMinRegistry("ilpmin","Schedule bottom-up for min ILP", createILPMinScheduler)

static

cl::opt<MachineSchedRegistry::ScheduleDAGCtor, false, RegisterPassParser<MachineSchedRegistry> > MachineSchedOpt("misched", cl::init(&useDefaultMachineSched), cl::Hidden, cl::desc("Machine instruction scheduler to use"))

static

MachineSchedOpt allows command line selection of the scheduler.

const unsigned MinSubtreeSize = 8

static

Definition at line 73 of file MachineScheduler.cpp.

Referenced by llvm::ScheduleDAGMI::computeDFSResult().

misched

Definition at line 123 of file MachineScheduler.cpp.