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 ReleaseAtCycle, unsigned AcquireAtCycle)
	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 ReleaseAtCycle, unsigned AcquireAtCycle)
	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, unsigned StartAtCycle)
	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 832 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 835 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 943 of file MachineScheduler.h.

References reset().

◆ SchedBoundary() [2/2]

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

delete

◆ ~SchedBoundary()

SchedBoundary::~SchedBoundary ( )

Definition at line 2177 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 2533 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 2624 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 2403 of file MachineScheduler.cpp.

Referenced by 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 2587 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 2863 of file MachineScheduler.cpp.

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

Referenced by dumpScheduledState(), and getNextResourceCycle().

◆ dumpScheduledState()

LLVM_DUMP_METHOD void SchedBoundary::dumpScheduledState ( ) const

Definition at line 2889 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 2451 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 986 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 961 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 964 of file MachineScheduler.h.

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

◆ getDependentLatency()

unsigned llvm::SchedBoundary::getDependentLatency ( ) const

inline

Definition at line 967 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 995 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 2284 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	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 2322 of file MachineScheduler.cpp.

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

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

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

References llvm::TargetSchedModel::enableIntervals(), InvalidCycle, isTop(), and SchedModel.

Referenced by getNextResourceCycle().

◆ getOtherResourceCount()

unsigned SchedBoundary::getOtherResourceCount ( unsigned & OtherCritIdx )

Definition at line 2472 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 980 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 972 of file MachineScheduler.h.

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

◆ getUnscheduledLatency()

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

inline

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

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

◆ incExecutedResources()

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

Definition at line 2571 of file MachineScheduler.cpp.

Referenced by countResource().

◆ init()

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

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

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

◆ isTop()

bool llvm::SchedBoundary::isTop ( ) const

inline

Definition at line 956 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 1018 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 2828 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 2499 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().