Each Scheduling boundary is associated with ready queues. More...

#include "llvm/CodeGen/MachineScheduler.h"

Public Types
enum	{ TopQID = 1 , BotQID = 2 , LogMaxQID = 2 }
	SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both) More...

Public Member Functions
	SchedBoundary (unsigned ID, const Twine &Name)
	Pending queues extend the ready queues with the same ID and the PendingFlag set.
SchedBoundary &	operator= (const SchedBoundary &other)=delete
	SchedBoundary (const SchedBoundary &other)=delete
LLVM_ABI	~SchedBoundary ()
LLVM_ABI void	reset ()
LLVM_ABI void	init (ScheduleDAGMI dag, const TargetSchedModel smodel, SchedRemainder *rem)
bool	isTop () const
unsigned	getCurrCycle () const
	Number of cycles to issue the instructions scheduled in this zone.
unsigned	getCurrMOps () const
	Micro-ops issued in the current cycle.
unsigned	getDependentLatency () const
unsigned	getScheduledLatency () const
	Get the number of latency cycles "covered" by the scheduled instructions.
unsigned	getUnscheduledLatency (SUnit *SU) const
unsigned	getResourceCount (unsigned ResIdx) const
unsigned	getCriticalCount () const
	Get the scaled count of scheduled micro-ops and resources, including executed resources.
unsigned	getExecutedCount () const
	Get a scaled count for the minimum execution time of the scheduled micro-ops that are ready to execute by getExecutedCount.
unsigned	getZoneCritResIdx () const
bool	isResourceLimited () const
LLVM_ABI unsigned	getLatencyStallCycles (SUnit *SU)
	Get the difference between the given SUnit's ready time and the current cycle.
LLVM_ABI unsigned	getNextResourceCycleByInstance (unsigned InstanceIndex, unsigned ReleaseAtCycle, unsigned AcquireAtCycle)
	Compute the next cycle at which the given processor resource unit can be scheduled.
LLVM_ABI std::pair< unsigned, unsigned >	getNextResourceCycle (const MCSchedClassDesc *SC, unsigned PIdx, unsigned ReleaseAtCycle, unsigned AcquireAtCycle)
	Compute the next cycle at which the given processor resource can be scheduled.
bool	isReservedGroup (unsigned PIdx) const
LLVM_ABI bool	checkHazard (SUnit *SU)
	Does this SU have a hazard within the current instruction group.
LLVM_ABI unsigned	findMaxLatency (ArrayRef< SUnit * > ReadySUs)
LLVM_ABI unsigned	getOtherResourceCount (unsigned &OtherCritIdx)
LLVM_ABI void	releaseNode (SUnit *SU, unsigned ReadyCycle, bool InPQueue, unsigned Idx=0)
	Release SU to make it ready.
LLVM_ABI void	bumpCycle (unsigned NextCycle)
	Move the boundary of scheduled code by one cycle.
LLVM_ABI void	incExecutedResources (unsigned PIdx, unsigned Count)
LLVM_ABI unsigned	countResource (const MCSchedClassDesc *SC, unsigned PIdx, unsigned Cycles, unsigned ReadyCycle, unsigned StartAtCycle)
	Add the given processor resource to this scheduled zone.
LLVM_ABI void	bumpNode (SUnit *SU)
	Move the boundary of scheduled code by one SUnit.
LLVM_ABI void	releasePending ()
	Release pending ready nodes in to the available queue.
LLVM_ABI void	removeReady (SUnit *SU)
	Remove SU from the ready set for this boundary.
LLVM_ABI SUnit *	pickOnlyChoice ()
	Call this before applying any other heuristics to the Available queue.
LLVM_ABI void	dumpReservedCycles () const
	Dump the state of the information that tracks resource usage.
LLVM_ABI void	dumpScheduledState () const

Public Attributes
ScheduleDAGMI *	DAG = nullptr
const TargetSchedModel *	SchedModel = nullptr
SchedRemainder *	Rem = nullptr
ReadyQueue	Available
ReadyQueue	Pending
std::unique_ptr< ScheduleHazardRecognizer >	HazardRec

Detailed Description

Each Scheduling boundary is associated with ready queues.

It tracks the current cycle in the direction of movement, and maintains the state of "hazards" and other interlocks at the current cycle.

Definition at line 923 of file MachineScheduler.h.

Member Enumeration Documentation

◆ anonymous enum

anonymous enum

SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both)

Enumerator
TopQID
BotQID
LogMaxQID

Definition at line 926 of file MachineScheduler.h.

Constructor & Destructor Documentation

◆ SchedBoundary() [1/2]

llvm::SchedBoundary::SchedBoundary	(	unsigned	ID,
		const Twine &	Name )

inline

Pending queues extend the ready queues with the same ID and the PendingFlag set.

Definition at line 1034 of file MachineScheduler.h.

References Available, LogMaxQID, Pending, and reset().

Referenced by operator=(), and SchedBoundary().

◆ SchedBoundary() [2/2]

llvm::SchedBoundary::SchedBoundary ( const SchedBoundary & other )

delete

References SchedBoundary().

◆ ~SchedBoundary()

SchedBoundary::~SchedBoundary ( )

default

References LLVM_ABI.

Member Function Documentation

◆ bumpCycle()

void SchedBoundary::bumpCycle ( unsigned NextCycle )

Move the boundary of scheduled code by one cycle.

Definition at line 3160 of file MachineScheduler.cpp.

References assert(), Available, checkResourceLimit(), llvm::dbgs(), getCriticalCount(), getScheduledLatency(), HazardRec, isTop(), LLVM_DEBUG, and SchedModel.

Referenced by bumpNode(), llvm::GCNSchedStrategy::pickNode(), and pickOnlyChoice().

◆ bumpNode()

void SchedBoundary::bumpNode ( SUnit * SU )

Move the boundary of scheduled code by one SUnit.

Definition at line 3251 of file MachineScheduler.cpp.

References assert(), Available, llvm::SUnit::BotReadyCycle, bumpCycle(), checkResourceLimit(), countResource(), DAG, llvm::dbgs(), dumpScheduledState(), getCriticalCount(), llvm::SUnit::getDepth(), llvm::SUnit::getHeight(), llvm::SUnit::getInstr(), getNextResourceCycle(), getResourceCount(), llvm::ResourceSegments::getResourceIntervalBottom(), llvm::ResourceSegments::getResourceIntervalTop(), getScheduledLatency(), llvm::SUnit::hasReservedResource, HazardRec, llvm::SUnit::isCall, isTop(), llvm::SUnit::isUnbuffered, LLVM_DEBUG, MIResourceCutOff, Rem, SchedModel, and llvm::SUnit::TopReadyCycle.

◆ checkHazard()

bool SchedBoundary::checkHazard ( SUnit * SU )

Does this SU have a hazard within the current instruction group.

The scheduler supports two modes of hazard recognition. The first is the ScheduleHazardRecognizer API. It is a fully general hazard recognizer that supports highly complicated in-order reservation tables (ScoreboardHazardRecognizer) and arbitrary target-specific logic.

The second is a streamlined mechanism that checks for hazards based on simple counters that the scheduler itself maintains. It explicitly checks for instruction dispatch limitations, including the number of micro-ops that can dispatch per cycle.

TODO: Also check whether the SU must start a new group.

Definition at line 3011 of file MachineScheduler.cpp.

References DAG, llvm::dbgs(), llvm::SUnit::getInstr(), getNextResourceCycle(), llvm::SUnit::hasReservedResource, HazardRec, isTop(), LLVM_DEBUG, llvm::make_range(), llvm::ScheduleHazardRecognizer::NoHazard, and SchedModel.

Referenced by llvm::GCNSchedStrategy::pickNode(), pickOnlyChoice(), and releaseNode().

◆ countResource()

unsigned SchedBoundary::countResource	(	const MCSchedClassDesc *	SC,
		unsigned	PIdx,
		unsigned	ReleaseAtCycle,
		unsigned	NextCycle,
		unsigned	AcquireAtCycle )

Add the given processor resource to this scheduled zone.

Parameters

ReleaseAtCycle	indicates the number of consecutive (non-pipelined) cycles during which this resource is released.
AcquireAtCycle	indicates the number of consecutive (non-pipelined) cycles at which the resource is aquired after issue (assuming no stalls).

Returns: the next cycle at which the instruction may execute without oversubscribing resources.

Definition at line 3214 of file MachineScheduler.cpp.

References assert(), llvm::Count, llvm::dbgs(), getCriticalCount(), getNextResourceCycle(), getResourceCount(), incExecutedResources(), LLVM_DEBUG, Rem, and SchedModel.

Referenced by bumpNode().

◆ dumpReservedCycles()

LLVM_DUMP_METHOD void SchedBoundary::dumpReservedCycles ( ) const

Dump the state of the information that tracks resource usage.

Dump the content of the ReservedCycles vector for the resources that are used in the basic block.

Definition at line 3493 of file MachineScheduler.cpp.

References llvm::dbgs(), LLVM_DUMP_METHOD, and SchedModel.

Referenced by dumpScheduledState(), and getNextResourceCycle().

◆ dumpScheduledState()

LLVM_DUMP_METHOD void SchedBoundary::dumpScheduledState ( ) const

Definition at line 3519 of file MachineScheduler.cpp.

References Available, llvm::dbgs(), dumpReservedCycles(), getExecutedCount(), getResourceCount(), LLVM_DUMP_METHOD, MISchedDumpReservedCycles, and SchedModel.

Referenced by bumpNode().

◆ findMaxLatency()

unsigned SchedBoundary::findMaxLatency ( ArrayRef< SUnit * > ReadySUs )

Definition at line 3065 of file MachineScheduler.cpp.

References Available, llvm::dbgs(), getUnscheduledLatency(), and LLVM_DEBUG.

Referenced by llvm::computeRemLatency().

◆ getCriticalCount()

unsigned llvm::SchedBoundary::getCriticalCount ( ) const

inline

Get the scaled count of scheduled micro-ops and resources, including executed resources.

Definition at line 1077 of file MachineScheduler.h.

References getResourceCount(), and SchedModel.

Referenced by bumpCycle(), bumpNode(), and countResource().

◆ getCurrCycle()

unsigned llvm::SchedBoundary::getCurrCycle ( ) const

inline

Number of cycles to issue the instructions scheduled in this zone.

Definition at line 1052 of file MachineScheduler.h.

Referenced by llvm::CandidateHeuristics::getStallCosts(), llvm::CandidateHeuristics::getStructuralStallCycles(), llvm::GCNSchedStrategy::pickNode(), and llvm::GenericSchedulerBase::setPolicy().

◆ getCurrMOps()

unsigned llvm::SchedBoundary::getCurrMOps ( ) const

inline

Micro-ops issued in the current cycle.

Definition at line 1055 of file MachineScheduler.h.

Referenced by llvm::GCNMaxMemoryClauseSchedStrategy::tryCandidate(), llvm::GenericScheduler::tryCandidate(), llvm::PPCPreRASchedStrategy::tryCandidate(), and llvm::RISCVPreRAMachineSchedStrategy::tryCandidate().

◆ getDependentLatency()

unsigned llvm::SchedBoundary::getDependentLatency ( ) const

inline

Definition at line 1058 of file MachineScheduler.h.

Referenced by llvm::computeRemLatency().

◆ getExecutedCount()

unsigned llvm::SchedBoundary::getExecutedCount ( ) const

inline

Get a scaled count for the minimum execution time of the scheduled micro-ops that are ready to execute by getExecutedCount.

Notice the feedback loop.

Definition at line 1086 of file MachineScheduler.h.

References SchedModel.

Referenced by dumpScheduledState().

◆ getLatencyStallCycles()

unsigned SchedBoundary::getLatencyStallCycles ( SUnit * SU )

Get the difference between the given SUnit's ready time and the current cycle.

Compute the stall cycles based on this SUnit's ready time.

Heuristics treat these "soft stalls" differently than the hard stall cycles based on CPU resources and computed by checkHazard(). A fully in-order model (MicroOpBufferSize==0) will not make use of this since instructions are not available for scheduling until they are ready. However, a weaker in-order model may use this for heuristics. For example, if a processor has in-order behavior when reading certain resources, this may come into play.

Definition at line 2892 of file MachineScheduler.cpp.

References llvm::SUnit::BotReadyCycle, isTop(), llvm::SUnit::isUnbuffered, and llvm::SUnit::TopReadyCycle.

Referenced by llvm::CandidateHeuristics::getStallCosts(), llvm::GCNMaxILPSchedStrategy::tryCandidate(), llvm::GCNMaxMemoryClauseSchedStrategy::tryCandidate(), llvm::GenericScheduler::tryCandidate(), llvm::PPCPreRASchedStrategy::tryCandidate(), and llvm::RISCVPreRAMachineSchedStrategy::tryCandidate().

◆ getNextResourceCycle()

std::pair< unsigned, unsigned > SchedBoundary::getNextResourceCycle	(	const MCSchedClassDesc *	SC,
		unsigned	PIdx,
		unsigned	ReleaseAtCycle,
		unsigned	AcquireAtCycle )

Compute the next cycle at which the given processor resource can be scheduled.

Returns the next cycle and the index of the processor resource instance in the reserved cycles vector.

Definition at line 2930 of file MachineScheduler.cpp.

References assert(), llvm::dbgs(), dumpReservedCycles(), llvm::End, getNextResourceCycle(), getNextResourceCycleByInstance(), I, InvalidCycle, isReservedGroup(), LLVM_DEBUG, llvm::make_range(), MischedDetailResourceBooking, and SchedModel.

Referenced by bumpNode(), checkHazard(), countResource(), getNextResourceCycle(), and llvm::CandidateHeuristics::getStructuralStallCycles().

◆ getNextResourceCycleByInstance()

unsigned SchedBoundary::getNextResourceCycleByInstance	(	unsigned	InstanceIndex,
		unsigned	ReleaseAtCycle,
		unsigned	AcquireAtCycle )

Compute the next cycle at which the given processor resource unit can be scheduled.

Definition at line 2904 of file MachineScheduler.cpp.

References InvalidCycle, isTop(), and SchedModel.

Referenced by getNextResourceCycle().

◆ getOtherResourceCount()

unsigned SchedBoundary::getOtherResourceCount ( unsigned & OtherCritIdx )

Definition at line 3086 of file MachineScheduler.cpp.

References Available, llvm::dbgs(), getResourceCount(), LLVM_DEBUG, Rem, and SchedModel.

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

◆ getResourceCount()

unsigned llvm::SchedBoundary::getResourceCount ( unsigned ResIdx ) const

inline

Definition at line 1071 of file MachineScheduler.h.

Referenced by bumpNode(), countResource(), dumpScheduledState(), getCriticalCount(), and getOtherResourceCount().

◆ getScheduledLatency()

unsigned llvm::SchedBoundary::getScheduledLatency ( ) const

inline

Get the number of latency cycles "covered" by the scheduled instructions.

This is the larger of the critical path within the zone and the number of cycles required to issue the instructions.

Definition at line 1063 of file MachineScheduler.h.

Referenced by bumpCycle(), bumpNode(), llvm::SystemZPreRASchedStrategy::tryCandidate(), and llvm::tryLatency().

◆ getUnscheduledLatency()

unsigned llvm::SchedBoundary::getUnscheduledLatency ( SUnit * SU ) const

inline

Definition at line 1067 of file MachineScheduler.h.

References llvm::SUnit::getDepth(), llvm::SUnit::getHeight(), and isTop().

Referenced by findMaxLatency().

◆ getZoneCritResIdx()

unsigned llvm::SchedBoundary::getZoneCritResIdx ( ) const

inline

Definition at line 1091 of file MachineScheduler.h.

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

◆ incExecutedResources()

void SchedBoundary::incExecutedResources	(	unsigned	PIdx,
		unsigned	Count )

Definition at line 3198 of file MachineScheduler.cpp.

References llvm::Count.

Referenced by countResource().

◆ init()

void SchedBoundary::init	(	ScheduleDAGMI *	dag,
		const TargetSchedModel *	smodel,
		SchedRemainder *	rem )

Definition at line 2857 of file MachineScheduler.cpp.

References DAG, InvalidCycle, isReservedGroup(), Rem, reset(), and SchedModel.

◆ isReservedGroup()

bool llvm::SchedBoundary::isReservedGroup ( unsigned PIdx ) const

inline

Definition at line 1108 of file MachineScheduler.h.

References SchedModel.

Referenced by getNextResourceCycle(), and init().

◆ isResourceLimited()

bool llvm::SchedBoundary::isResourceLimited ( ) const

inline

Definition at line 1094 of file MachineScheduler.h.

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

◆ isTop()

bool llvm::SchedBoundary::isTop ( ) const

inline

Definition at line 1047 of file MachineScheduler.h.

References Available, and TopQID.

Referenced by bumpCycle(), bumpNode(), checkHazard(), getLatencyStallCycles(), getNextResourceCycleByInstance(), llvm::CandidateHeuristics::getStallCosts(), llvm::CandidateHeuristics::getStructuralStallCycles(), getUnscheduledLatency(), llvm::AMDGPUCoExecSchedStrategy::pickNodeFromQueue(), llvm::GCNSchedStrategy::pickNodeFromQueue(), llvm::GenericScheduler::pickNodeFromQueue(), llvm::PostGenericScheduler::pickNodeFromQueue(), releasePending(), llvm::tryBiasPhysRegs(), llvm::GCNMaxILPSchedStrategy::tryCandidate(), llvm::GCNMaxMemoryClauseSchedStrategy::tryCandidate(), llvm::GenericScheduler::tryCandidate(), llvm::PPCPreRASchedStrategy::tryCandidate(), llvm::RISCVPreRAMachineSchedStrategy::tryCandidate(), llvm::SystemZPreRASchedStrategy::tryCandidate(), llvm::AMDGPUCoExecSchedStrategy::tryCandidateCoexec(), llvm::CandidateHeuristics::tryEffectiveStall(), and llvm::tryLatency().

◆ operator=()

SchedBoundary & llvm::SchedBoundary::operator= ( const SchedBoundary & other )

delete

References SchedBoundary().

◆ pickOnlyChoice()

SUnit * SchedBoundary::pickOnlyChoice ( )

Call this before applying any other heuristics to the Available queue.

If this queue only has one ready candidate, return it.

Updates the Available/Pending Q's if necessary and returns the single available instruction, or NULL if there are multiple candidates.

As a side effect, defer any nodes that now hit a hazard, and advance the cycle until at least one node is ready. If multiple instructions are ready, return NULL.

Definition at line 3458 of file MachineScheduler.cpp.

References Available, bumpCycle(), checkHazard(), I, LLVM_DEBUG, Pending, and releasePending().

Referenced by pickOnlyChoice(), and pickOnlyChoice().

◆ releaseNode()

void SchedBoundary::releaseNode	(	SUnit *	SU,
		unsigned	ReadyCycle,
		bool	InPQueue,
		unsigned	Idx = 0 )

Release SU to make it ready.

If it's not in hazard, remove it from pending queue (if already in) and push into available queue. Otherwise, push the SU into pending queue.

Parameters

SU	The unit to be released.
ReadyCycle	Until which cycle the unit is ready.
InPQueue	Whether SU is already in pending queue.
Idx	Position offset in pending queue (if in it).

Definition at line 3113 of file MachineScheduler.cpp.

References assert(), Available, checkHazard(), llvm::dbgs(), llvm::SUnit::getInstr(), LLVM_DEBUG, Pending, ReadyListLimit, and SchedModel.

Referenced by releasePending().

◆ releasePending()

void SchedBoundary::releasePending ( )

Release pending ready nodes in to the available queue.

This makes them visible to heuristics.

Definition at line 3417 of file MachineScheduler.cpp.

References Available, llvm::SUnit::BotReadyCycle, llvm::dbgs(), I, isTop(), LLVM_DEBUG, Pending, ReadyListLimit, releaseNode(), and llvm::SUnit::TopReadyCycle.

Referenced by llvm::GCNSchedStrategy::pickNode(), and pickOnlyChoice().

◆ removeReady()

void SchedBoundary::removeReady ( SUnit * SU )

Remove SU from the ready set for this boundary.

Definition at line 3446 of file MachineScheduler.cpp.

References assert(), Available, and Pending.

◆ reset()

void SchedBoundary::reset ( )

Definition at line 2802 of file MachineScheduler.cpp.

References assert(), Available, HazardRec, and Pending.

Referenced by init(), and SchedBoundary().

Member Data Documentation

◆ Available

ReadyQueue llvm::SchedBoundary::Available

◆ DAG

ScheduleDAGMI* llvm::SchedBoundary::DAG = nullptr

Definition at line 932 of file MachineScheduler.h.

Referenced by bumpNode(), checkHazard(), init(), llvm::AMDGPUCoExecSchedStrategy::pickNodeFromQueue(), and llvm::GCNSchedStrategy::pickNodeFromQueue().

◆ HazardRec

std::unique_ptr<ScheduleHazardRecognizer> llvm::SchedBoundary::HazardRec

Definition at line 939 of file MachineScheduler.h.

Referenced by bumpCycle(), bumpNode(), checkHazard(), llvm::CandidateHeuristics::getStructuralStallCycles(), and reset().

◆ Pending

ReadyQueue llvm::SchedBoundary::Pending

Definition at line 937 of file MachineScheduler.h.

Referenced by llvm::computeRemLatency(), llvm::AMDGPUCoExecSchedStrategy::pickNodeFromQueue(), llvm::GCNSchedStrategy::pickNodeFromQueue(), pickOnlyChoice(), pickOnlyChoice(), pickOnlyChoice(), releaseNode(), releasePending(), removeReady(), reset(), SchedBoundary(), and shouldCheckPending().

◆ Rem

SchedRemainder* llvm::SchedBoundary::Rem = nullptr

Definition at line 934 of file MachineScheduler.h.

Referenced by bumpNode(), countResource(), getOtherResourceCount(), and init().

◆ SchedModel

const TargetSchedModel* llvm::SchedBoundary::SchedModel = nullptr

Definition at line 933 of file MachineScheduler.h.

Referenced by bumpCycle(), bumpNode(), checkHazard(), countResource(), dumpReservedCycles(), dumpScheduledState(), getCriticalCount(), getExecutedCount(), getNextResourceCycle(), getNextResourceCycleByInstance(), getOtherResourceCount(), init(), isReservedGroup(), and releaseNode().

The documentation for this class was generated from the following files:

include/llvm/CodeGen/MachineScheduler.h
lib/CodeGen/MachineScheduler.cpp

Public Types

Public Member Functions

Public Attributes

Detailed Description

Member Enumeration Documentation

◆ anonymous enum

Constructor & Destructor Documentation

◆ SchedBoundary() [1/2]

◆ SchedBoundary() [2/2]

◆ ~SchedBoundary()

Member Function Documentation

◆ bumpCycle()

◆ bumpNode()

◆ checkHazard()

◆ countResource()

◆ dumpReservedCycles()

◆ dumpScheduledState()

◆ findMaxLatency()

◆ getCriticalCount()

◆ getCurrCycle()

◆ getCurrMOps()

◆ getDependentLatency()

◆ getExecutedCount()

◆ getLatencyStallCycles()

◆ getNextResourceCycle()

◆ getNextResourceCycleByInstance()

◆ getOtherResourceCount()

◆ getResourceCount()

◆ getScheduledLatency()

◆ getUnscheduledLatency()

◆ getZoneCritResIdx()

◆ incExecutedResources()

◆ init()

◆ isReservedGroup()

◆ isResourceLimited()

◆ isTop()

◆ operator=()

◆ pickOnlyChoice()

◆ releaseNode()

◆ releasePending()

◆ removeReady()

◆ reset()

Member Data Documentation

◆ Available

◆ DAG

◆ HazardRec

◆ Pending

◆ Rem

◆ SchedModel