MachineScheduler.cpp File Reference

#include "llvm/CodeGen/MachineScheduler.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:

Go to the source code of this file.

Classes
struct	llvm::GraphTraits< ScheduleDAGMI * >
struct	llvm::DOTGraphTraits< ScheduleDAGMI * >
Namespaces
namespace	llvm
	List of target independent CodeGen pass IDs.
Defines
#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
	INITIALIZE_PASS (PostMachineScheduler,"postmisched","PostRA Machine Instruction Scheduler", false, false) PostMachineScheduler
static ScheduleDAGInstrs *	useDefaultMachineSched (MachineSchedContext *C)
static ScheduleDAGInstrs *	createGenericSchedLive (MachineSchedContext *C)
static ScheduleDAGInstrs *	createGenericSchedPostRA (MachineSchedContext *C)
	Create a generic scheduler with no vreg liveness or DAG mutation passes.
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.
static MachineBasicBlock::const_iterator	nextIfDebug (MachineBasicBlock::iterator I, MachineBasicBlock::const_iterator End)
	Non-const version.
static bool	isSchedBoundary (MachineBasicBlock::iterator MI, MachineBasicBlock *MBB, MachineFunction *MF, const TargetInstrInfo *TII, bool IsPostRA)
static bool	tryLess (int TryVal, int CandVal, GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, GenericSchedulerBase::CandReason Reason)
	Return true if this heuristic determines order.
static bool	tryGreater (int TryVal, int CandVal, GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, GenericSchedulerBase::CandReason Reason)
static bool	tryLatency (GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, SchedBoundary &Zone)
static void	tracePick (const GenericSchedulerBase::SchedCandidate &Cand, bool IsTop)
static bool	tryPressure (const PressureChange &TryP, const PressureChange &CandP, GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, GenericSchedulerBase::CandReason Reason)
static unsigned	getWeakLeft (const SUnit *SU, bool isTop)
static int	biasPhysRegCopy (const SUnit *SU, bool isTop)
static ScheduleDAGInstrs *	createILPMaxScheduler (MachineSchedContext *C)
static ScheduleDAGInstrs *	createILPMinScheduler (MachineSchedContext *C)
static ScheduleDAGInstrs *	createInstructionShuffler (MachineSchedContext *C)
Variables
cl::opt< bool >	llvm::DumpCriticalPathLength ("misched-dcpl", cl::Hidden, cl::desc("Print critical path length to stdout"))
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< std::string >	SchedOnlyFunc ("misched-only-func", cl::Hidden, cl::desc("Only schedule this function"))
static cl::opt< unsigned >	SchedOnlyBlock ("misched-only-block", cl::Hidden, cl::desc("Only schedule this MBB#"))
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.
static MachineSchedRegistry	DefaultSchedRegistry ("default","Use the target's default scheduler choice.", useDefaultMachineSched)
static const unsigned	InvalidCycle = ~0U
static MachineSchedRegistry	GenericSchedRegistry ("converge","Standard converging scheduler.", createGenericSchedLive)
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)

---

Define Documentation

#define DEBUG_TYPE   "misched"

Definition at line 36 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 2519 of file MachineScheduler.cpp.

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

Referenced by llvm::GenericScheduler::tryCandidate().

static ScheduleDAGInstrs * createGenericSchedLive

(

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 2866 of file MachineScheduler.cpp.

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

static ScheduleDAGInstrs * createGenericSchedPostRA

(

MachineSchedContext *

C

)

[static]

Create a generic scheduler with no vreg liveness or DAG mutation passes.

Definition at line 3016 of file MachineScheduler.cpp.

static ScheduleDAGInstrs* createILPMaxScheduler

(

MachineSchedContext *

C

)

[static]

Definition at line 3121 of file MachineScheduler.cpp.

static ScheduleDAGInstrs* createILPMinScheduler

(

MachineSchedContext *

C

)

[static]

Definition at line 3124 of file MachineScheduler.cpp.

static ScheduleDAGInstrs* createInstructionShuffler

(

MachineSchedContext *

C

)

[static]

Definition at line 3209 of file MachineScheduler.cpp.

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

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

Definition at line 2508 of file MachineScheduler.cpp.

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

Referenced by llvm::GenericScheduler::tryCandidate().

INITIALIZE_PASS	(	PostMachineScheduler	,
		"postmisched"	,
		"PostRA Machine Instruction Scheduler"	,
		false	,
		false
	)

Definition at line 177 of file MachineScheduler.cpp.

References llvm::PassRegistry::getPassRegistry(), and llvm::initializePostMachineSchedulerPass().

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

static bool isSchedBoundary	(	MachineBasicBlock::iterator	MI,
		MachineBasicBlock *	MBB,
		MachineFunction *	MF,
		const TargetInstrInfo *	TII,
		bool	IsPostRA
	)		[static]

Return true of the given instruction should not be included in a scheduling region.

MachineScheduler does not currently support scheduling across calls. To handle calls, the DAG builder needs to be modified to create register anti/output dependencies on the registers clobbered by the call's regmask operand. In PreRA scheduling, the stack pointer adjustment already prevents scheduling across calls. In PostRA scheduling, we need the isCall to enforce the boundary, but there would be no benefit to postRA scheduling across calls this late anyway.

Definition at line 374 of file MachineScheduler.cpp.

References llvm::TargetInstrInfo::isSchedulingBoundary().

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

Non-const version.

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

Definition at line 240 of file MachineScheduler.cpp.

References I.

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

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.

Non-const version.

Definition at line 219 of file MachineScheduler.cpp.

References I.

Referenced by llvm::ScheduleDAGMI::schedule(), and llvm::ScheduleDAGMILive::scheduleMI().

static void tracePick	(	const GenericSchedulerBase::SchedCandidate &	Cand,
		bool	IsTop
	)		[static]

Definition at line 2344 of file MachineScheduler.cpp.

References llvm::dbgs(), DEBUG, llvm::GenericSchedulerBase::getReasonStr(), and llvm::GenericSchedulerBase::SchedCandidate::Reason.

Referenced by llvm::GenericScheduler::pickNode(), llvm::PostGenericScheduler::pickNode(), and llvm::GenericScheduler::pickNodeBidirectional().

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

Definition at line 2301 of file MachineScheduler.cpp.

References llvm::GenericSchedulerBase::SchedCandidate::Reason, and llvm::GenericSchedulerBase::SchedCandidate::setRepeat().

Referenced by llvm::GenericScheduler::tryCandidate(), llvm::PostGenericScheduler::tryCandidate(), tryLatency(), and tryPressure().

static bool tryLatency	(	GenericSchedulerBase::SchedCandidate &	TryCand,
		GenericSchedulerBase::SchedCandidate &	Cand,
		SchedBoundary &	Zone
	)		[static]

Definition at line 2318 of file MachineScheduler.cpp.

References llvm::GenericSchedulerBase::BotHeightReduce, llvm::GenericSchedulerBase::BotPathReduce, llvm::SUnit::getDepth(), llvm::SUnit::getHeight(), llvm::SchedBoundary::getScheduledLatency(), llvm::SchedBoundary::isTop(), llvm::GenericSchedulerBase::SchedCandidate::SU, llvm::GenericSchedulerBase::TopDepthReduce, llvm::GenericSchedulerBase::TopPathReduce, tryGreater(), and tryLess().

Referenced by llvm::GenericScheduler::tryCandidate(), and llvm::PostGenericScheduler::tryCandidate().

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

Return true if this heuristic determines order.

Definition at line 2284 of file MachineScheduler.cpp.

References llvm::GenericSchedulerBase::SchedCandidate::Reason, and llvm::GenericSchedulerBase::SchedCandidate::setRepeat().

Referenced by llvm::GenericScheduler::tryCandidate(), llvm::PostGenericScheduler::tryCandidate(), tryLatency(), and tryPressure().

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

Definition at line 2484 of file MachineScheduler.cpp.

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

Referenced by llvm::GenericScheduler::tryCandidate().

static ScheduleDAGInstrs* useDefaultMachineSched

(

MachineSchedContext *

C

)

[static]

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

Definition at line 197 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]

Referenced by llvm::GenericScheduler::registerRoots().

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

Referenced by createGenericSchedLive().

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

Referenced by createGenericSchedLive().

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

Referenced by llvm::GenericScheduler::initPolicy().

Machine Instruction false

Definition at line 152 of file MachineScheduler.cpp.

MachineSchedRegistry GenericSchedRegistry("converge","Standard converging scheduler.", createGenericSchedLive) [static]

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

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

const unsigned InvalidCycle = ~0U [static]

Definition at line 1567 of file MachineScheduler.cpp.

Referenced by llvm::SchedBoundary::getNextResourceCycle(), and llvm::SchedBoundary::init().

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 80 of file MachineScheduler.cpp.

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

misched

Definition at line 152 of file MachineScheduler.cpp.

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

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

cl::opt<unsigned> SchedOnlyBlock("misched-only-block", cl::Hidden, cl::desc("Only schedule this MBB#")) [static]

cl::opt<std::string> SchedOnlyFunc("misched-only-func", cl::Hidden, cl::desc("Only schedule this function")) [static]

Machine Instruction Scheduler

Definition at line 152 of file MachineScheduler.cpp.

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

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

Referenced by llvm::GenericScheduler::tryCandidate().

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

Referenced by llvm::ScheduleDAGMI::schedule(), and llvm::ScheduleDAGMILive::schedule().