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

	~SchedBoundary ()

void	reset ()

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

unsigned	getLatencyStallCycles (SUnit *SU)
	Get the difference between the given SUnit's ready time and the current cycle.

unsigned	getNextResourceCycleByInstance (unsigned InstanceIndex, unsigned Cycles)
	Compute the next cycle at which the given processor resource unit can be scheduled.

std::pair< unsigned, unsigned >	getNextResourceCycle (const MCSchedClassDesc *SC, unsigned PIdx, unsigned Cycles)
	Compute the next cycle at which the given processor resource can be scheduled.

bool	isUnbufferedGroup (unsigned PIdx) const

bool	checkHazard (SUnit *SU)
	Does this SU have a hazard within the current instruction group.

unsigned	findMaxLatency (ArrayRef< SUnit * > ReadySUs)

unsigned	getOtherResourceCount (unsigned &OtherCritIdx)

void	releaseNode (SUnit *SU, unsigned ReadyCycle, bool InPQueue, unsigned Idx=0)
	Release SU to make it ready.

void	bumpCycle (unsigned NextCycle)
	Move the boundary of scheduled code by one cycle.

void	incExecutedResources (unsigned PIdx, unsigned Count)

unsigned	countResource (const MCSchedClassDesc *SC, unsigned PIdx, unsigned Cycles, unsigned ReadyCycle)
	Add the given processor resource to this scheduled zone.

void	bumpNode (SUnit *SU)
	Move the boundary of scheduled code by one SUnit.

void	releasePending ()
	Release pending ready nodes in to the available queue.

void	removeReady (SUnit *SU)
	Remove SU from the ready set for this boundary.

SUnit *	pickOnlyChoice ()
	Call this before applying any other heuristics to the Available queue.

void	dumpReservedCycles () const
	Dump the state of the information that tracks resource usage.

void	dumpScheduledState () const

Public Attributes
ScheduleDAGMI *	DAG = nullptr

const TargetSchedModel *	SchedModel = nullptr

SchedRemainder *	Rem = nullptr

ReadyQueue	Available

ReadyQueue	Pending

ScheduleHazardRecognizer *	HazardRec = nullptr

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 614 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 617 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 721 of file MachineScheduler.h.

References reset().

◆ SchedBoundary() [2/2]

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

delete

◆ ~SchedBoundary()

SchedBoundary::~SchedBoundary ( )

Definition at line 2135 of file MachineScheduler.cpp.

References HazardRec.

Member Function Documentation

◆ bumpCycle()

void SchedBoundary::bumpCycle ( unsigned NextCycle )

Move the boundary of scheduled code by one cycle.

Definition at line 2458 of file MachineScheduler.cpp.

References llvm::ScheduleHazardRecognizer::AdvanceCycle(), assert(), Available, checkResourceLimit(), llvm::dbgs(), getCriticalCount(), llvm::TargetSchedModel::getIssueWidth(), llvm::TargetSchedModel::getLatencyFactor(), llvm::TargetSchedModel::getMicroOpBufferSize(), llvm::ReadyQueue::getName(), getScheduledLatency(), HazardRec, llvm::ScheduleHazardRecognizer::isEnabled(), isTop(), LLVM_DEBUG, llvm::ScheduleHazardRecognizer::RecedeCycle(), and SchedModel.

Referenced by bumpNode(), and pickOnlyChoice().

◆ bumpNode()

void SchedBoundary::bumpNode ( SUnit * SU )

Move the boundary of scheduled code by one SUnit.

Definition at line 2543 of file MachineScheduler.cpp.

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

Referenced by pickOnlyChoice(), and releaseNode().

◆ countResource()

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

Add the given processor resource to this scheduled zone.

Parameters

Cycles indicates the number of consecutive (non-pipelined) cycles during which this resource is consumed.

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

Definition at line 2509 of file MachineScheduler.cpp.

References assert(), llvm::dbgs(), getCriticalCount(), llvm::TargetSchedModel::getLatencyFactor(), getNextResourceCycle(), getResourceCount(), llvm::TargetSchedModel::getResourceFactor(), llvm::TargetSchedModel::getResourceName(), incExecutedResources(), LLVM_DEBUG, Rem, llvm::SchedRemainder::RemainingCounts, 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 2762 of file MachineScheduler.cpp.

References llvm::dbgs(), llvm::TargetSchedModel::getNumProcResourceKinds(), llvm::TargetSchedModel::getProcResource(), llvm::TargetSchedModel::getResourceName(), llvm::TargetSchedModel::hasInstrSchedModel(), llvm::MCProcResourceDesc::NumUnits, and SchedModel.

Referenced by dumpScheduledState().

◆ dumpScheduledState()

LLVM_DUMP_METHOD void SchedBoundary::dumpScheduledState ( ) const

Definition at line 2782 of file MachineScheduler.cpp.

References Available, llvm::dbgs(), dumpReservedCycles(), getExecutedCount(), llvm::TargetSchedModel::getLatencyFactor(), llvm::TargetSchedModel::getMicroOpFactor(), llvm::ReadyQueue::getName(), getResourceCount(), llvm::TargetSchedModel::getResourceFactor(), llvm::TargetSchedModel::getResourceName(), llvm::MISchedDumpReservedCycles, and SchedModel.

Referenced by bumpNode().

◆ findMaxLatency()

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

Definition at line 2376 of file MachineScheduler.cpp.

References Available, llvm::dbgs(), llvm::ReadyQueue::getName(), getUnscheduledLatency(), LLVM_DEBUG, and llvm::SUnit::NodeNum.

Referenced by computeRemLatency().

◆ getCriticalCount()

unsigned llvm::SchedBoundary::getCriticalCount ( ) const

inline

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

Definition at line 764 of file MachineScheduler.h.

References llvm::TargetSchedModel::getMicroOpFactor(), 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 739 of file MachineScheduler.h.

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

◆ getCurrMOps()

unsigned llvm::SchedBoundary::getCurrMOps ( ) const

inline

Micro-ops issued in the current cycle.

Definition at line 742 of file MachineScheduler.h.

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

◆ getDependentLatency()

unsigned llvm::SchedBoundary::getDependentLatency ( ) const

inline

Definition at line 745 of file MachineScheduler.h.

Referenced by 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 773 of file MachineScheduler.h.

References llvm::TargetSchedModel::getLatencyFactor(), and 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 2239 of file MachineScheduler.cpp.

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

Referenced by llvm::PPCPostRASchedStrategy::tryCandidate(), llvm::GenericScheduler::tryCandidate(), llvm::GCNMaxILPSchedStrategy::tryCandidate(), and llvm::PPCPreRASchedStrategy::tryCandidate().

◆ getNextResourceCycle()

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

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

References assert(), End, getNextResourceCycle(), getNextResourceCycleByInstance(), llvm::TargetSchedModel::getProcResource(), llvm::TargetSchedModel::getWriteProcResBegin(), llvm::TargetSchedModel::getWriteProcResEnd(), I, InvalidCycle, isUnbufferedGroup(), llvm::make_range(), llvm::MCProcResourceDesc::NumUnits, SchedModel, and llvm::MCProcResourceDesc::SubUnitsIdxBegin.

Referenced by bumpNode(), checkHazard(), countResource(), and getNextResourceCycle().

◆ getNextResourceCycleByInstance()

unsigned SchedBoundary::getNextResourceCycleByInstance	(	unsigned	InstanceIndex,
		unsigned	Cycles
	)

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

Definition at line 2251 of file MachineScheduler.cpp.

References InvalidCycle, and isTop().

Referenced by getNextResourceCycle().

◆ getOtherResourceCount()

unsigned SchedBoundary::getOtherResourceCount ( unsigned & OtherCritIdx )

Definition at line 2397 of file MachineScheduler.cpp.

References Available, llvm::dbgs(), llvm::TargetSchedModel::getMicroOpFactor(), llvm::ReadyQueue::getName(), llvm::TargetSchedModel::getNumProcResourceKinds(), getResourceCount(), llvm::TargetSchedModel::getResourceFactor(), llvm::TargetSchedModel::getResourceName(), llvm::TargetSchedModel::hasInstrSchedModel(), LLVM_DEBUG, Rem, llvm::SchedRemainder::RemainingCounts, llvm::SchedRemainder::RemIssueCount, and SchedModel.

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

◆ getResourceCount()

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

inline

Definition at line 758 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 750 of file MachineScheduler.h.

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

◆ getUnscheduledLatency()

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

inline

Definition at line 754 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 778 of file MachineScheduler.h.

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

◆ incExecutedResources()

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

Definition at line 2496 of file MachineScheduler.cpp.

Referenced by countResource().

◆ init()

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

Definition at line 2204 of file MachineScheduler.cpp.

References DAG, llvm::TargetSchedModel::getNumProcResourceKinds(), llvm::TargetSchedModel::getProcResource(), llvm::TargetSchedModel::hasInstrSchedModel(), InvalidCycle, isUnbufferedGroup(), llvm::MCProcResourceDesc::NumUnits, Rem, rem, reset(), llvm::SmallVectorImpl< T >::resize(), SchedModel, and llvm::MCProcResourceDesc::SubUnitsIdxBegin.

◆ isResourceLimited()

bool llvm::SchedBoundary::isResourceLimited ( ) const

inline

Definition at line 781 of file MachineScheduler.h.

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

◆ isTop()

bool llvm::SchedBoundary::isTop ( ) const

inline

Definition at line 734 of file MachineScheduler.h.

References Available, llvm::ReadyQueue::getID(), and TopQID.

Referenced by bumpCycle(), bumpNode(), checkHazard(), getLatencyStallCycles(), getNextResourceCycleByInstance(), getUnscheduledLatency(), llvm::GCNSchedStrategy::pickNodeFromQueue(), llvm::GenericScheduler::pickNodeFromQueue(), releasePending(), llvm::GenericScheduler::tryCandidate(), llvm::GCNMaxILPSchedStrategy::tryCandidate(), llvm::PPCPreRASchedStrategy::tryCandidate(), and llvm::tryLatency().

◆ isUnbufferedGroup()

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

inline

Definition at line 794 of file MachineScheduler.h.

References llvm::MCProcResourceDesc::BufferSize, llvm::TargetSchedModel::getProcResource(), SchedModel, and llvm::MCProcResourceDesc::SubUnitsIdxBegin.

Referenced by getNextResourceCycle(), and init().

◆ operator=()

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

delete

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

References Available, llvm::ReadyQueue::begin(), bumpCycle(), checkHazard(), llvm::ReadyQueue::dump(), llvm::ReadyQueue::empty(), llvm::ReadyQueue::end(), I, LLVM_DEBUG, Pending, llvm::ReadyQueue::push(), releasePending(), llvm::ReadyQueue::remove(), and llvm::ReadyQueue::size().

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

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

References assert(), Available, llvm::ReadyQueue::begin(), checkHazard(), llvm::SUnit::getInstr(), llvm::TargetSchedModel::getMicroOpBufferSize(), Idx, Pending, llvm::ReadyQueue::push(), ReadyListLimit, llvm::ReadyQueue::remove(), SchedModel, and llvm::ReadyQueue::size().