#include "llvm/CodeGen/MachineScheduler.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/EquivalenceClasses.h"
#include "llvm/ADT/PriorityQueue.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/CodeGen/LiveInterval.h"
#include "llvm/CodeGen/LiveIntervals.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachinePassRegistry.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/RegisterClassInfo.h"
#include "llvm/CodeGen/RegisterPressure.h"
#include "llvm/CodeGen/ScheduleDAG.h"
#include "llvm/CodeGen/ScheduleDAGInstrs.h"
#include "llvm/CodeGen/ScheduleDAGMutation.h"
#include "llvm/CodeGen/ScheduleDFS.h"
#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
#include "llvm/CodeGen/SlotIndexes.h"
#include "llvm/CodeGen/TargetFrameLowering.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetLowering.h"
#include "llvm/CodeGen/TargetPassConfig.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSchedule.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/CodeGenTypes/MachineValueType.h"
#include "llvm/Config/llvm-config.h"
#include "llvm/InitializePasses.h"
#include "llvm/MC/LaneBitmask.h"
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.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/TargetMachine.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iterator>
#include <limits>
#include <memory>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

Classes
class	llvm::impl_detail::MachineSchedulerBase
	Base class for the machine scheduler classes. More...
class	llvm::impl_detail::MachineSchedulerImpl
	Impl class for MachineScheduler. More...
struct	llvm::impl_detail::MachineSchedulerImpl::RequiredAnalyses
class	llvm::impl_detail::PostMachineSchedulerImpl
	Impl class for PostMachineScheduler. More...
struct	llvm::impl_detail::PostMachineSchedulerImpl::RequiredAnalyses
struct	llvm::GraphTraits< ScheduleDAGMI * >
struct	llvm::DOTGraphTraits< ScheduleDAGMI * >

Namespaces
namespace	llvm
	This is an optimization pass for GlobalISel generic memory operations.
namespace	llvm::impl_detail

Macros
#define	DEBUG_TYPE "machine-scheduler"

Typedefs
using	MBBRegionsVector = SmallVector<SchedRegion, 16>

Functions
	STATISTIC (NumInstrsInSourceOrderPreRA, "Number of instructions in source order after pre-RA scheduling")
	STATISTIC (NumInstrsInSourceOrderPostRA, "Number of instructions in source order after post-RA scheduling")
	STATISTIC (NumInstrsScheduledPreRA, "Number of instructions scheduled by pre-RA scheduler")
	STATISTIC (NumInstrsScheduledPostRA, "Number of instructions scheduled by post-RA scheduler")
	STATISTIC (NumClustered, "Number of load/store pairs clustered")
	STATISTIC (NumTopPreRA, "Number of scheduling units chosen from top queue pre-RA")
	STATISTIC (NumBotPreRA, "Number of scheduling units chosen from bottom queue pre-RA")
	STATISTIC (NumNoCandPreRA, "Number of scheduling units chosen for NoCand heuristic pre-RA")
	STATISTIC (NumOnly1PreRA, "Number of scheduling units chosen for Only1 heuristic pre-RA")
	STATISTIC (NumPhysRegPreRA, "Number of scheduling units chosen for PhysReg heuristic pre-RA")
	STATISTIC (NumRegExcessPreRA, "Number of scheduling units chosen for RegExcess heuristic pre-RA")
	STATISTIC (NumRegCriticalPreRA, "Number of scheduling units chosen for RegCritical heuristic pre-RA")
	STATISTIC (NumStallPreRA, "Number of scheduling units chosen for Stall heuristic pre-RA")
	STATISTIC (NumClusterPreRA, "Number of scheduling units chosen for Cluster heuristic pre-RA")
	STATISTIC (NumWeakPreRA, "Number of scheduling units chosen for Weak heuristic pre-RA")
	STATISTIC (NumRegMaxPreRA, "Number of scheduling units chosen for RegMax heuristic pre-RA")
	STATISTIC (NumResourceReducePreRA, "Number of scheduling units chosen for ResourceReduce heuristic pre-RA")
	STATISTIC (NumResourceDemandPreRA, "Number of scheduling units chosen for ResourceDemand heuristic pre-RA")
	STATISTIC (NumTopDepthReducePreRA, "Number of scheduling units chosen for TopDepthReduce heuristic pre-RA")
	STATISTIC (NumTopPathReducePreRA, "Number of scheduling units chosen for TopPathReduce heuristic pre-RA")
	STATISTIC (NumBotHeightReducePreRA, "Number of scheduling units chosen for BotHeightReduce heuristic pre-RA")
	STATISTIC (NumBotPathReducePreRA, "Number of scheduling units chosen for BotPathReduce heuristic pre-RA")
	STATISTIC (NumNodeOrderPreRA, "Number of scheduling units chosen for NodeOrder heuristic pre-RA")
	STATISTIC (NumFirstValidPreRA, "Number of scheduling units chosen for FirstValid heuristic pre-RA")
	STATISTIC (NumTopPostRA, "Number of scheduling units chosen from top queue post-RA")
	STATISTIC (NumBotPostRA, "Number of scheduling units chosen from bottom queue post-RA")
	STATISTIC (NumNoCandPostRA, "Number of scheduling units chosen for NoCand heuristic post-RA")
	STATISTIC (NumOnly1PostRA, "Number of scheduling units chosen for Only1 heuristic post-RA")
	STATISTIC (NumPhysRegPostRA, "Number of scheduling units chosen for PhysReg heuristic post-RA")
	STATISTIC (NumRegExcessPostRA, "Number of scheduling units chosen for RegExcess heuristic post-RA")
	STATISTIC (NumRegCriticalPostRA, "Number of scheduling units chosen for RegCritical heuristic post-RA")
	STATISTIC (NumStallPostRA, "Number of scheduling units chosen for Stall heuristic post-RA")
	STATISTIC (NumClusterPostRA, "Number of scheduling units chosen for Cluster heuristic post-RA")
	STATISTIC (NumWeakPostRA, "Number of scheduling units chosen for Weak heuristic post-RA")
	STATISTIC (NumRegMaxPostRA, "Number of scheduling units chosen for RegMax heuristic post-RA")
	STATISTIC (NumResourceReducePostRA, "Number of scheduling units chosen for ResourceReduce heuristic post-RA")
	STATISTIC (NumResourceDemandPostRA, "Number of scheduling units chosen for ResourceDemand heuristic post-RA")
	STATISTIC (NumTopDepthReducePostRA, "Number of scheduling units chosen for TopDepthReduce heuristic post-RA")
	STATISTIC (NumTopPathReducePostRA, "Number of scheduling units chosen for TopPathReduce heuristic post-RA")
	STATISTIC (NumBotHeightReducePostRA, "Number of scheduling units chosen for BotHeightReduce heuristic post-RA")
	STATISTIC (NumBotPathReducePostRA, "Number of scheduling units chosen for BotPathReduce heuristic post-RA")
	STATISTIC (NumNodeOrderPostRA, "Number of scheduling units chosen for NodeOrder heuristic post-RA")
	STATISTIC (NumFirstValidPostRA, "Number of scheduling units chosen for FirstValid heuristic post-RA")
	INITIALIZE_PASS_BEGIN (MachineSchedulerLegacy, DEBUG_TYPE, "Machine Instruction Scheduler", false, false) INITIALIZE_PASS_END(MachineSchedulerLegacy
	INITIALIZE_PASS_BEGIN (PostMachineSchedulerLegacy, "postmisched", "PostRA Machine Instruction Scheduler", false, false) INITIALIZE_PASS_END(PostMachineSchedulerLegacy
static ScheduleDAGInstrs *	useDefaultMachineSched (MachineSchedContext *C)
	A dummy default scheduler factory indicates whether the scheduler is overridden on the command line.
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::iterator	priorNonDebug (MachineBasicBlock::iterator I, MachineBasicBlock::const_iterator Beg)
	Non-const version.
static MachineBasicBlock::const_iterator	nextIfDebug (MachineBasicBlock::const_iterator I, MachineBasicBlock::const_iterator End)
	If this iterator is a debug value, increment until reaching the End or a non-debug instruction.
static MachineBasicBlock::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)
	Return true of the given instruction should not be included in a scheduling region.
static void	getSchedRegions (MachineBasicBlock *MBB, MBBRegionsVector &Regions, bool RegionsTopDown)
static bool	checkResourceLimit (unsigned LFactor, unsigned Count, unsigned Latency, bool AfterSchedNode)
	Given a Count of resource usage and a Latency value, return true if a SchedBoundary becomes resource limited.
static unsigned	computeRemLatency (SchedBoundary &CurrZone)
	Compute remaining latency.
static void	tracePick (GenericSchedulerBase::CandReason Reason, bool IsTop, bool IsPostRA=false)
static void	tracePick (const GenericSchedulerBase::SchedCandidate &Cand, bool IsPostRA=false)
static ScheduleDAGInstrs *	createConvergingSched (MachineSchedContext *C)
static ScheduleDAGInstrs *	createILPMaxScheduler (MachineSchedContext *C)
static ScheduleDAGInstrs *	createILPMinScheduler (MachineSchedContext *C)
static ScheduleDAGInstrs *	createInstructionShuffler (MachineSchedContext *C)
static bool	sortIntervals (const ResourceSegments::IntervalTy &A, const ResourceSegments::IntervalTy &B)
	Sort predicate for the intervals stored in an instance of ResourceSegments.

Variables
static cl::opt< MISched::Direction >	PostRADirection ("misched-postra-direction", cl::Hidden, cl::desc("Post reg-alloc list scheduling direction"), cl::init(MISched::Unspecified), cl::values(clEnumValN(MISched::TopDown, "topdown", "Force top-down post reg-alloc list scheduling"), clEnumValN(MISched::BottomUp, "bottomup", "Force bottom-up post reg-alloc list scheduling"), clEnumValN(MISched::Bidirectional, "bidirectional", "Force bidirectional post reg-alloc list scheduling")))
static cl::opt< bool >	DumpCriticalPathLength ("misched-dcpl", cl::Hidden, cl::desc("Print critical path length to stdout"))
static cl::opt< bool >	MISchedDumpReservedCycles ("misched-dump-reserved-cycles", cl::Hidden, cl::init(false), cl::desc("Dump resource usage at schedule boundary."))
static cl::opt< bool >	MischedDetailResourceBooking ("misched-detail-resource-booking", cl::Hidden, cl::init(false), cl::desc("Show details of invoking getNextResoufceCycle."))
static cl::opt< unsigned >	ViewMISchedCutoff ("view-misched-cutoff", cl::Hidden, cl::desc("Hide nodes with more predecessor/successor than cutoff"))
	In some situations a few uninteresting nodes depend on nearly all other nodes in the graph, provide a cutoff to hide them.
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< unsigned >	ReadyListLimit ("misched-limit", cl::Hidden, cl::desc("Limit ready list to N instructions"), cl::init(256))
	Avoid quadratic complexity in unusually large basic blocks by limiting the size of the ready lists.
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 >	EnableMemOpCluster ("misched-cluster", cl::Hidden, cl::desc("Enable memop clustering."), cl::init(true))
static cl::opt< bool >	ForceFastCluster ("force-fast-cluster", cl::Hidden, cl::desc("Switch to fast cluster algorithm with the lost " "of some fusion opportunities"), cl::init(false))
static cl::opt< unsigned >	FastClusterThreshold ("fast-cluster-threshold", cl::Hidden, cl::desc("The threshold for fast cluster"), cl::init(1000))
static cl::opt< bool >	MISchedDumpScheduleTrace ("misched-dump-schedule-trace", cl::Hidden, cl::init(false), cl::desc("Dump resource usage at schedule boundary."))
static cl::opt< unsigned >	HeaderColWidth ("misched-dump-schedule-trace-col-header-width", cl::Hidden, cl::desc("Set width of the columns with " "the resources and schedule units"), cl::init(19))
static cl::opt< unsigned >	ColWidth ("misched-dump-schedule-trace-col-width", cl::Hidden, cl::desc("Set width of the columns showing resource booking."), cl::init(5))
static cl::opt< bool >	MISchedSortResourcesInTrace ("misched-sort-resources-in-trace", cl::Hidden, cl::init(true), cl::desc("Sort the resources printed in the dump trace"))
static cl::opt< unsigned >	MIResourceCutOff ("misched-resource-cutoff", cl::Hidden, cl::desc("Number of intervals to track"), cl::init(10))
static const unsigned	MinSubtreeSize = 8
	DEBUG_TYPE
Machine Instruction	Scheduler
Machine Instruction	false
	postmisched
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 cl::opt< bool >	EnableMachineSched ("enable-misched", cl::desc("Enable the machine instruction scheduling pass."), cl::init(true), cl::Hidden)
static cl::opt< bool >	EnablePostRAMachineSched ("enable-post-misched", cl::desc("Enable the post-ra machine instruction scheduling pass."), cl::init(true), cl::Hidden)
static const char *	scheduleTableLegend = " i: issue\n x: resource booked"
static const unsigned	InvalidCycle = ~0U
static MachineSchedRegistry	GenericSchedRegistry ("converge", "Standard converging scheduler.", createConvergingSched)
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

◆ DEBUG_TYPE

#define DEBUG_TYPE "machine-scheduler"

Definition at line 76 of file MachineScheduler.cpp.

Typedef Documentation

◆ MBBRegionsVector

using MBBRegionsVector = SmallVector<SchedRegion, 16>

Definition at line 770 of file MachineScheduler.cpp.

Function Documentation

◆ checkResourceLimit()

bool checkResourceLimit	(	unsigned	LFactor,
		unsigned	Count,
		unsigned	Latency,
		bool	AfterSchedNode )

static

Given a Count of resource usage and a Latency value, return true if a SchedBoundary becomes resource limited.

If we are checking after scheduling a node, we should return true when we just reach the resource limit.

Definition at line 2480 of file MachineScheduler.cpp.

References llvm::Count, and llvm::Latency.

Referenced by llvm::SchedBoundary::bumpCycle(), llvm::SchedBoundary::bumpNode(), and llvm::GenericSchedulerBase::setPolicy().

◆ computeRemLatency()

unsigned computeRemLatency ( SchedBoundary & CurrZone )

static

Compute remaining latency.

We need this both to determine whether the overall schedule has become latency-limited and whether the instructions outside this zone are resource or latency limited.

The "dependent" latency is updated incrementally during scheduling as the max height/depth of scheduled nodes minus the cycles since it was scheduled: DLat = max (N.depth - (CurrCycle - N.ReadyCycle) for N in Zone

The "independent" latency is the max ready queue depth: ILat = max N.depth for N in Available|Pending

RemainingLatency is the greater of independent and dependent latency.

These computations are expensive, especially in DAGs with many edges, so only do them if necessary.

Definition at line 3270 of file MachineScheduler.cpp.

References llvm::SchedBoundary::Available, llvm::ReadyQueue::elements(), llvm::SchedBoundary::findMaxLatency(), llvm::SchedBoundary::getDependentLatency(), and llvm::SchedBoundary::Pending.

Referenced by llvm::GenericSchedulerBase::setPolicy().

◆ createConvergingSched()

ScheduleDAGInstrs * createConvergingSched ( MachineSchedContext * C )

static

Definition at line 4271 of file MachineScheduler.cpp.

References llvm::CallingConv::C, and llvm::createSchedLive().

◆ createILPMaxScheduler()

ScheduleDAGInstrs * createILPMaxScheduler ( MachineSchedContext * C )

static

Definition at line 4688 of file MachineScheduler.cpp.

References llvm::CallingConv::C.

◆ createILPMinScheduler()

ScheduleDAGInstrs * createILPMinScheduler ( MachineSchedContext * C )

static

Definition at line 4691 of file MachineScheduler.cpp.

References llvm::CallingConv::C.

◆ createInstructionShuffler()

ScheduleDAGInstrs * createInstructionShuffler ( MachineSchedContext * C )

static

Definition at line 4780 of file MachineScheduler.cpp.

References llvm::MISched::BottomUp, llvm::CallingConv::C, llvm::PreRADirection, and llvm::MISched::TopDown.

◆ getSchedRegions()

void getSchedRegions	(	MachineBasicBlock *	MBB,
		MBBRegionsVector &	Regions,
		bool	RegionsTopDown )

static

Definition at line 773 of file MachineScheduler.cpp.

References llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::TargetSubtargetInfo::getInstrInfo(), llvm::MachineFunction::getSubtarget(), I, isSchedBoundary(), MBB, MI, llvm::SmallVectorTemplateBase< T, bool >::push_back(), and TII.

Referenced by llvm::impl_detail::MachineSchedulerBase::scheduleRegions().

◆ INITIALIZE_PASS_BEGIN() [1/2]

INITIALIZE_PASS_BEGIN	(	MachineSchedulerLegacy	,
		DEBUG_TYPE	,
		"Machine Instruction Scheduler"	,
		false	,
		false	)

References DEBUG_TYPE, and INITIALIZE_PASS_DEPENDENCY.

◆ INITIALIZE_PASS_BEGIN() [2/2]

INITIALIZE_PASS_BEGIN	(	PostMachineSchedulerLegacy	,
		"postmisched"	,
		"PostRA Machine Instruction Scheduler"	,
		false	,
		false	)

References INITIALIZE_PASS_DEPENDENCY.

◆ isSchedBoundary()

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

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

References MBB, MI, and TII.

Referenced by getSchedRegions().

◆ nextIfDebug() [1/2]

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

References I.

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

◆ nextIfDebug() [2/2]

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

static

Non-const version.

Definition at line 528 of file MachineScheduler.cpp.

References llvm::MachineInstrBundleIterator< Ty, IsReverse >::getNonConstIterator(), I, and nextIfDebug().

◆ priorNonDebug() [1/2]

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

References assert(), and I.

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

◆ priorNonDebug() [2/2]

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

static

Non-const version.

Definition at line 508 of file MachineScheduler.cpp.

References llvm::MachineInstrBundleIterator< Ty, IsReverse >::getNonConstIterator(), I, and priorNonDebug().

◆ sortIntervals()

bool sortIntervals	(	const ResourceSegments::IntervalTy &	A,
		const ResourceSegments::IntervalTy &	B )

static

Sort predicate for the intervals stored in an instance of ResourceSegments.

Intervals are always disjoint (no intersection for any pairs of intervals), therefore we can sort the totality of the intervals by looking only at the left boundary.

Definition at line 4886 of file MachineScheduler.cpp.

References A(), and B().

◆ STATISTIC() [1/43]

STATISTIC	(	NumBotHeightReducePostRA	,
		"Number of scheduling units chosen for BotHeightReduce heuristic post-RA"	)

◆ STATISTIC() [2/43]

STATISTIC	(	NumBotHeightReducePreRA	,
		"Number of scheduling units chosen for BotHeightReduce heuristic pre-RA"	)

◆ STATISTIC() [3/43]

STATISTIC	(	NumBotPathReducePostRA	,
		"Number of scheduling units chosen for BotPathReduce heuristic post-RA"	)

◆ STATISTIC() [4/43]

STATISTIC	(	NumBotPathReducePreRA	,
		"Number of scheduling units chosen for BotPathReduce heuristic pre-RA"	)

◆ STATISTIC() [5/43]

STATISTIC	(	NumBotPostRA	,
		"Number of scheduling units chosen from bottom queue post-RA"	)

◆ STATISTIC() [6/43]

STATISTIC	(	NumBotPreRA	,
		"Number of scheduling units chosen from bottom queue pre-RA"	)

◆ STATISTIC() [7/43]

STATISTIC	(	NumClustered	,
		"Number of load/store pairs clustered"	)

◆ STATISTIC() [8/43]

STATISTIC	(	NumClusterPostRA	,
		"Number of scheduling units chosen for Cluster heuristic post-RA"	)

◆ STATISTIC() [9/43]

STATISTIC	(	NumClusterPreRA	,
		"Number of scheduling units chosen for Cluster heuristic pre-RA"	)

◆ STATISTIC() [10/43]

STATISTIC	(	NumFirstValidPostRA	,
		"Number of scheduling units chosen for FirstValid heuristic post-RA"	)

References llvm::MISched::Bidirectional, llvm::MISched::BottomUp, llvm::cl::Hidden, llvm::cl::init(), llvm::MISched::TopDown, llvm::MISched::Unspecified, and llvm::cl::values().

◆ STATISTIC() [11/43]

STATISTIC	(	NumFirstValidPreRA	,
		"Number of scheduling units chosen for FirstValid heuristic pre-RA"	)

◆ STATISTIC() [12/43]

STATISTIC	(	NumInstrsInSourceOrderPostRA	,
		"Number of instructions in source order after post-RA scheduling"	)

◆ STATISTIC() [13/43]

STATISTIC	(	NumInstrsInSourceOrderPreRA	,
		"Number of instructions in source order after pre-RA scheduling"	)

◆ STATISTIC() [14/43]

STATISTIC	(	NumInstrsScheduledPostRA	,
		"Number of instructions scheduled by post-RA scheduler"	)

◆ STATISTIC() [15/43]

STATISTIC	(	NumInstrsScheduledPreRA	,
		"Number of instructions scheduled by pre-RA scheduler"	)

◆ STATISTIC() [16/43]

STATISTIC	(	NumNoCandPostRA	,
		"Number of scheduling units chosen for NoCand heuristic post-RA"	)

◆ STATISTIC() [17/43]

STATISTIC	(	NumNoCandPreRA	,
		"Number of scheduling units chosen for NoCand heuristic pre-RA"	)

◆ STATISTIC() [18/43]

STATISTIC	(	NumNodeOrderPostRA	,
		"Number of scheduling units chosen for NodeOrder heuristic post-RA"	)

◆ STATISTIC() [19/43]

STATISTIC	(	NumNodeOrderPreRA	,
		"Number of scheduling units chosen for NodeOrder heuristic pre-RA"	)

◆ STATISTIC() [20/43]

STATISTIC	(	NumOnly1PostRA	,
		"Number of scheduling units chosen for Only1 heuristic post-RA"	)

◆ STATISTIC() [21/43]

STATISTIC	(	NumOnly1PreRA	,
		"Number of scheduling units chosen for Only1 heuristic pre-RA"	)

◆ STATISTIC() [22/43]

STATISTIC	(	NumPhysRegPostRA	,
		"Number of scheduling units chosen for PhysReg heuristic post-RA"	)

◆ STATISTIC() [23/43]

STATISTIC	(	NumPhysRegPreRA	,
		"Number of scheduling units chosen for PhysReg heuristic pre-RA"	)

◆ STATISTIC() [24/43]

STATISTIC	(	NumRegCriticalPostRA	,
		"Number of scheduling units chosen for RegCritical heuristic post-RA"	)

◆ STATISTIC() [25/43]

STATISTIC	(	NumRegCriticalPreRA	,
		"Number of scheduling units chosen for RegCritical heuristic pre-RA"	)

◆ STATISTIC() [26/43]

STATISTIC	(	NumRegExcessPostRA	,
		"Number of scheduling units chosen for RegExcess heuristic post-RA"	)

◆ STATISTIC() [27/43]

STATISTIC	(	NumRegExcessPreRA	,
		"Number of scheduling units chosen for RegExcess heuristic pre-RA"	)

◆ STATISTIC() [28/43]

STATISTIC	(	NumRegMaxPostRA	,
		"Number of scheduling units chosen for RegMax heuristic post-RA"	)

◆ STATISTIC() [29/43]

STATISTIC	(	NumRegMaxPreRA	,
		"Number of scheduling units chosen for RegMax heuristic pre-RA"	)

◆ STATISTIC() [30/43]

STATISTIC	(	NumResourceDemandPostRA	,
		"Number of scheduling units chosen for ResourceDemand heuristic post-RA"	)

◆ STATISTIC() [31/43]

STATISTIC	(	NumResourceDemandPreRA	,
		"Number of scheduling units chosen for ResourceDemand heuristic pre-RA"	)

◆ STATISTIC() [32/43]

STATISTIC	(	NumResourceReducePostRA	,
		"Number of scheduling units chosen for ResourceReduce heuristic post-RA"	)

◆ STATISTIC() [33/43]

STATISTIC	(	NumResourceReducePreRA	,
		"Number of scheduling units chosen for ResourceReduce heuristic pre-RA"	)

◆ STATISTIC() [34/43]

STATISTIC	(	NumStallPostRA	,
		"Number of scheduling units chosen for Stall heuristic post-RA"	)

◆ STATISTIC() [35/43]

STATISTIC	(	NumStallPreRA	,
		"Number of scheduling units chosen for Stall heuristic pre-RA"	)

◆ STATISTIC() [36/43]

STATISTIC	(	NumTopDepthReducePostRA	,
		"Number of scheduling units chosen for TopDepthReduce heuristic post-RA"	)

◆ STATISTIC() [37/43]

STATISTIC	(	NumTopDepthReducePreRA	,
		"Number of scheduling units chosen for TopDepthReduce heuristic pre-RA"	)

◆ STATISTIC() [38/43]

STATISTIC	(	NumTopPathReducePostRA	,
		"Number of scheduling units chosen for TopPathReduce heuristic post-RA"	)

◆ STATISTIC() [39/43]

STATISTIC	(	NumTopPathReducePreRA	,
		"Number of scheduling units chosen for TopPathReduce heuristic pre-RA"	)

◆ STATISTIC() [40/43]

STATISTIC	(	NumTopPostRA	,
		"Number of scheduling units chosen from top queue post-RA"	)

◆ STATISTIC() [41/43]

STATISTIC	(	NumTopPreRA	,
		"Number of scheduling units chosen from top queue pre-RA"	)

◆ STATISTIC() [42/43]

STATISTIC	(	NumWeakPostRA	,
		"Number of scheduling units chosen for Weak heuristic post-RA"	)

◆ STATISTIC() [43/43]

STATISTIC	(	NumWeakPreRA	,
		"Number of scheduling units chosen for Weak heuristic pre-RA"	)

◆ tracePick() [1/2]

void tracePick	(	const GenericSchedulerBase::SchedCandidate &	Cand,
		bool	IsPostRA = false )

static

Definition at line 3632 of file MachineScheduler.cpp.

References llvm::GenericSchedulerBase::SchedCandidate::AtTop, llvm::GenericSchedulerBase::SchedCandidate::Reason, and tracePick().

◆ tracePick() [2/2]

void tracePick	(	GenericSchedulerBase::CandReason	Reason,
		bool	IsTop,
		bool	IsPostRA = false )

static

Definition at line 3504 of file MachineScheduler.cpp.

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

◆ useDefaultMachineSched()

ScheduleDAGInstrs * useDefaultMachineSched ( MachineSchedContext * C )

static

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

Definition at line 469 of file MachineScheduler.cpp.

References llvm::CallingConv::C.

Referenced by llvm::impl_detail::MachineSchedulerImpl::createMachineScheduler().

Variable Documentation

◆ ColWidth

cl::opt< unsigned > ColWidth("misched-dump-schedule-trace-col-width", cl::Hidden, cl::desc("Set width of the columns showing resource booking."), cl::init(5))	(	"misched-dump-schedule-trace-col-width"	,
		cl::Hidden	,
		cl::desc("Set width of the columns showing resource booking.")	,
		cl::init(5)	)

static

Referenced by llvm::ScheduleDAGMI::dumpScheduleTraceBottomUp(), and llvm::ScheduleDAGMI::dumpScheduleTraceTopDown().

◆ DEBUG_TYPE

DEBUG_TYPE

Definition at line 418 of file MachineScheduler.cpp.

◆ DefaultSchedRegistry

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

static

◆ DumpCriticalPathLength

cl::opt< bool > DumpCriticalPathLength("misched-dcpl", cl::Hidden, cl::desc("Print critical path length to stdout"))	(	"misched-dcpl"	,
		cl::Hidden	,
		cl::desc("Print critical path length to stdout")	)

static

Referenced by llvm::GenericScheduler::registerRoots(), llvm::PostGenericScheduler::registerRoots(), and llvm::impl_detail::MachineSchedulerBase::scheduleRegions().

◆ EnableCyclicPath

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

static

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

◆ EnableMachineSched

cl::opt< bool > EnableMachineSched("enable-misched", cl::desc("Enable the machine instruction scheduling pass."), cl::init(true), cl::Hidden)	(	"enable-misched"	,
		cl::desc("Enable the machine instruction scheduling pass.")	,
		cl::init(true)	,
		cl::Hidden	)

static

Referenced by llvm::MachineSchedulerPass::run().

◆ EnableMemOpCluster

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

static

Referenced by llvm::createLoadClusterDAGMutation(), and llvm::createStoreClusterDAGMutation().

◆ EnablePostRAMachineSched

cl::opt< bool > EnablePostRAMachineSched("enable-post-misched", cl::desc("Enable the post-ra machine instruction scheduling pass."), cl::init(true), cl::Hidden)	(	"enable-post-misched"	,
		cl::desc("Enable the post-ra machine instruction scheduling pass.")	,
		cl::init(true)	,
		cl::Hidden	)

static

Referenced by llvm::PostMachineSchedulerPass::run().

◆ EnableRegPressure

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

static

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

◆ false

PostRA Machine Instruction false

Definition at line 419 of file MachineScheduler.cpp.

◆ FastClusterThreshold

cl::opt< unsigned > FastClusterThreshold("fast-cluster-threshold", cl::Hidden, cl::desc("The threshold for fast cluster"), cl::init(1000))	(	"fast-cluster-threshold"	,
		cl::Hidden	,
		cl::desc("The threshold for fast cluster")	,
		cl::init(1000)	)

static

◆ ForceFastCluster

cl::opt< bool > ForceFastCluster("force-fast-cluster", cl::Hidden, cl::desc("Switch to fast cluster algorithm with the lost " "of some fusion opportunities"), cl::init(false))	(	"force-fast-cluster"	,
		cl::Hidden	,
		cl::desc("Switch to fast cluster algorithm with the lost " "of some fusion opportunities")	,
		cl::init(false)	)

static

◆ GenericSchedRegistry

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

static

◆ HeaderColWidth

cl::opt< unsigned > HeaderColWidth("misched-dump-schedule-trace-col-header-width", cl::Hidden, cl::desc("Set width of the columns with " "the resources and schedule units"), cl::init(19))	(	"misched-dump-schedule-trace-col-header-width"	,
		cl::Hidden	,
		cl::desc("Set width of the columns with " "the resources and schedule units")	,
		cl::init(19)	)

static

Referenced by llvm::ScheduleDAGMI::dumpScheduleTraceBottomUp(), and llvm::ScheduleDAGMI::dumpScheduleTraceTopDown().

◆ ILPMaxRegistry

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

static

◆ ILPMinRegistry

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

static

◆ InvalidCycle

const unsigned InvalidCycle = ~0U

static

Definition at line 2472 of file MachineScheduler.cpp.

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

◆ MachineSchedOpt

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

static

MachineSchedOpt allows command line selection of the scheduler.

Referenced by llvm::impl_detail::MachineSchedulerImpl::createMachineScheduler().

◆ MinSubtreeSize

const unsigned MinSubtreeSize = 8

static

Definition at line 294 of file MachineScheduler.cpp.

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

◆ MIResourceCutOff

cl::opt< unsigned > MIResourceCutOff("misched-resource-cutoff", cl::Hidden, cl::desc("Number of intervals to track"), cl::init(10))	(	"misched-resource-cutoff"	,
		cl::Hidden	,
		cl::desc("Number of intervals to track")	,
		cl::init(10)	)

static

Referenced by llvm::SchedBoundary::bumpNode().

◆ MISchedCutoff

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

static

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

◆ MischedDetailResourceBooking

cl::opt< bool > MischedDetailResourceBooking("misched-detail-resource-booking", cl::Hidden, cl::init(false), cl::desc("Show details of invoking getNextResoufceCycle."))	(	"misched-detail-resource-booking"	,
		cl::Hidden	,
		cl::init(false)	,
		cl::desc("Show details of invoking getNextResoufceCycle.")	)

static

Referenced by llvm::SchedBoundary::getNextResourceCycle().

◆ MISchedDumpReservedCycles

cl::opt< bool > MISchedDumpReservedCycles("misched-dump-reserved-cycles", cl::Hidden, cl::init(false), cl::desc("Dump resource usage at schedule boundary."))	(	"misched-dump-reserved-cycles"	,
		cl::Hidden	,
		cl::init(false)	,
		cl::desc("Dump resource usage at schedule boundary.")	)

static

Referenced by llvm::SchedBoundary::dumpScheduledState().

◆ MISchedDumpScheduleTrace

cl::opt< bool > MISchedDumpScheduleTrace("misched-dump-schedule-trace", cl::Hidden, cl::init(false), cl::desc("Dump resource usage at schedule boundary."))	(	"misched-dump-schedule-trace"	,
		cl::Hidden	,
		cl::init(false)	,
		cl::desc("Dump resource usage at schedule boundary.")	)

static

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

◆ MISchedSortResourcesInTrace

cl::opt< bool > MISchedSortResourcesInTrace("misched-sort-resources-in-trace", cl::Hidden, cl::init(true), cl::desc("Sort the resources printed in the dump trace"))	(	"misched-sort-resources-in-trace"	,
		cl::Hidden	,
		cl::init(true)	,
		cl::desc("Sort the resources printed in the dump trace")	)

static

Referenced by llvm::ScheduleDAGMI::dumpScheduleTraceBottomUp(), and llvm::ScheduleDAGMI::dumpScheduleTraceTopDown().

◆ postmisched

postmisched

Definition at line 447 of file MachineScheduler.cpp.

◆ PostRADirection

cl::opt< MISched::Direction > PostRADirection("misched-postra-direction", cl::Hidden, cl::desc("Post reg-alloc list scheduling direction"), cl::init(MISched::Unspecified), cl::values( clEnumValN(MISched::TopDown, "topdown", "Force top-down post reg-alloc list scheduling"), clEnumValN(MISched::BottomUp, "bottomup", "Force bottom-up post reg-alloc list scheduling"), clEnumValN(MISched::Bidirectional, "bidirectional", "Force bidirectional post reg-alloc list scheduling")))	(	"misched-postra-direction"	,
		cl::Hidden	,
		cl::desc("Post reg-alloc list scheduling direction")	,
		cl::init(MISched::Unspecified)	,
		cl::values( clEnumValN(MISched::TopDown, "topdown", "Force top-down post reg-alloc list scheduling"), clEnumValN(MISched::BottomUp, "bottomup", "Force bottom-up post reg-alloc list scheduling"), clEnumValN(MISched::Bidirectional, "bidirectional", "Force bidirectional post reg-alloc list scheduling"))	)

static

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

◆ ReadyListLimit

cl::opt< unsigned > ReadyListLimit("misched-limit", cl::Hidden, cl::desc("Limit ready list to N instructions"), cl::init(256))	(	"misched-limit"	,
		cl::Hidden	,
		cl::desc("Limit ready list to N instructions")	,
		cl::init(256)	)

static

Avoid quadratic complexity in unusually large basic blocks by limiting the size of the ready lists.

Referenced by llvm::SchedBoundary::releaseNode(), and llvm::SchedBoundary::releasePending().

◆ SchedOnlyBlock

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

static

Referenced by llvm::impl_detail::MachineSchedulerBase::scheduleRegions().

◆ SchedOnlyFunc

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

static

Referenced by llvm::impl_detail::MachineSchedulerBase::scheduleRegions().

◆ Scheduler

PostRA Machine Instruction Scheduler

Definition at line 419 of file MachineScheduler.cpp.

Referenced by llvm::impl_detail::MachineSchedulerImpl::createMachineScheduler(), llvm::impl_detail::PostMachineSchedulerImpl::createPostMachineScheduler(), llvm::impl_detail::MachineSchedulerImpl::run(), llvm::impl_detail::PostMachineSchedulerImpl::run(), llvm::SIScheduleDAGMI::schedule(), llvm::impl_detail::MachineSchedulerBase::scheduleRegions(), and llvm::SIScheduler::scheduleVariant().

◆ scheduleTableLegend

const char* scheduleTableLegend = " i: issue\n x: resource booked"

static

Definition at line 1214 of file MachineScheduler.cpp.

Referenced by llvm::ScheduleDAGMI::dumpScheduleTraceBottomUp(), and llvm::ScheduleDAGMI::dumpScheduleTraceTopDown().

◆ ShufflerRegistry

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

static

◆ ViewMISchedCutoff

cl::opt< unsigned > ViewMISchedCutoff("view-misched-cutoff", cl::Hidden, cl::desc("Hide nodes with more predecessor/successor than cutoff"))	(	"view-misched-cutoff"	,
		cl::Hidden	,
		cl::desc("Hide nodes with more predecessor/successor than cutoff")	)

static

In some situations a few uninteresting nodes depend on nearly all other nodes in the graph, provide a cutoff to hide them.

Referenced by llvm::DOTGraphTraits< ScheduleDAGMI * >::isNodeHidden().

Classes

Namespaces

Macros

Typedefs

Functions

Variables

Macro Definition Documentation

◆ DEBUG_TYPE

Typedef Documentation

◆ MBBRegionsVector

Function Documentation

◆ checkResourceLimit()

◆ computeRemLatency()

◆ createConvergingSched()

◆ createILPMaxScheduler()

◆ createILPMinScheduler()

◆ createInstructionShuffler()

◆ getSchedRegions()

◆ INITIALIZE_PASS_BEGIN() [1/2]

◆ INITIALIZE_PASS_BEGIN() [2/2]

◆ isSchedBoundary()

◆ nextIfDebug() [1/2]

◆ nextIfDebug() [2/2]

◆ priorNonDebug() [1/2]

◆ priorNonDebug() [2/2]

◆ sortIntervals()

◆ STATISTIC() [1/43]

◆ STATISTIC() [2/43]

◆ STATISTIC() [3/43]

◆ STATISTIC() [4/43]

◆ STATISTIC() [5/43]

◆ STATISTIC() [6/43]

◆ STATISTIC() [7/43]

◆ STATISTIC() [8/43]

◆ STATISTIC() [9/43]

◆ STATISTIC() [10/43]

◆ STATISTIC() [11/43]

◆ STATISTIC() [12/43]

◆ STATISTIC() [13/43]

◆ STATISTIC() [14/43]

◆ STATISTIC() [15/43]

◆ STATISTIC() [16/43]

◆ STATISTIC() [17/43]

◆ STATISTIC() [18/43]

◆ STATISTIC() [19/43]

◆ STATISTIC() [20/43]

◆ STATISTIC() [21/43]

◆ STATISTIC() [22/43]

◆ STATISTIC() [23/43]

◆ STATISTIC() [24/43]

◆ STATISTIC() [25/43]

◆ STATISTIC() [26/43]

◆ STATISTIC() [27/43]

◆ STATISTIC() [28/43]

◆ STATISTIC() [29/43]

◆ STATISTIC() [30/43]

◆ STATISTIC() [31/43]

◆ STATISTIC() [32/43]

◆ STATISTIC() [33/43]

◆ STATISTIC() [34/43]

◆ STATISTIC() [35/43]

◆ STATISTIC() [36/43]

◆ STATISTIC() [37/43]

◆ STATISTIC() [38/43]

◆ STATISTIC() [39/43]

◆ STATISTIC() [40/43]

◆ STATISTIC() [41/43]

◆ STATISTIC() [42/43]

◆ STATISTIC() [43/43]

◆ tracePick() [1/2]

◆ tracePick() [2/2]

◆ useDefaultMachineSched()

Variable Documentation

◆ ColWidth

◆ DEBUG_TYPE

◆ DefaultSchedRegistry

◆ DumpCriticalPathLength

◆ EnableCyclicPath

◆ EnableMachineSched

◆ EnableMemOpCluster