GenericScheduler shrinks the unscheduled zone using heuristics to balance the schedule. More...

#include "llvm/CodeGen/MachineScheduler.h"

Inheritance diagram for llvm::GenericScheduler:

Collaboration diagram for llvm::GenericScheduler:

[legend]

Public Member Functions
	GenericScheduler (const MachineSchedContext *C)

void	initPolicy (MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, unsigned NumRegionInstrs) override
	Initialize the per-region scheduling policy. More...

void	dumpPolicy () const override

bool	shouldTrackPressure () const override
	Check if pressure tracking is needed before building the DAG and initializing this strategy. More...

bool	shouldTrackLaneMasks () const override
	Returns true if lanemasks should be tracked. More...

void	initialize (ScheduleDAGMI *dag) override
	Initialize the strategy after building the DAG for a new region. More...

SUnit *	pickNode (bool &IsTopNode) override
	Pick the best node to balance the schedule. Implements MachineSchedStrategy. More...

void	schedNode (SUnit *SU, bool IsTopNode) override
	Update the scheduler's state after scheduling a node. More...

void	releaseTopNode (SUnit *SU) override
	When all predecessor dependencies have been resolved, free this node for top-down scheduling. More...

void	releaseBottomNode (SUnit *SU) override
	When all successor dependencies have been resolved, free this node for bottom-up scheduling. More...

void	registerRoots () override
	Notify this strategy that all roots have been released (including those that depend on EntrySU or ExitSU). More...

Public Member Functions inherited from llvm::MachineSchedStrategy
virtual	~MachineSchedStrategy ()=default

virtual bool	doMBBSchedRegionsTopDown () const

virtual void	enterMBB (MachineBasicBlock *MBB)
	Tell the strategy that MBB is about to be processed. More...

virtual void	leaveMBB ()
	Tell the strategy that current MBB is done. More...

virtual void	scheduleTree (unsigned SubtreeID)
	Scheduler callback to notify that a new subtree is scheduled. More...

Protected Member Functions
void	checkAcyclicLatency ()
	Set IsAcyclicLatencyLimited if the acyclic path is longer than the cyclic critical path by more cycles than it takes to drain the instruction buffer. More...

void	initCandidate (SchedCandidate &Cand, SUnit *SU, bool AtTop, const RegPressureTracker &RPTracker, RegPressureTracker &TempTracker)

virtual void	tryCandidate (SchedCandidate &Cand, SchedCandidate &TryCand, SchedBoundary *Zone) const
	Apply a set of heuristics to a new candidate. More...

SUnit *	pickNodeBidirectional (bool &IsTopNode)
	Pick the best candidate node from either the top or bottom queue. More...

void	pickNodeFromQueue (SchedBoundary &Zone, const CandPolicy &ZonePolicy, const RegPressureTracker &RPTracker, SchedCandidate &Candidate)
	Pick the best candidate from the queue. More...

void	reschedulePhysReg (SUnit *SU, bool isTop)

Protected Member Functions inherited from llvm::GenericSchedulerBase
	GenericSchedulerBase (const MachineSchedContext *C)

void	setPolicy (CandPolicy &Policy, bool IsPostRA, SchedBoundary &CurrZone, SchedBoundary *OtherZone)
	Set the CandPolicy given a scheduling zone given the current resources and latencies inside and outside the zone. More...

void	traceCandidate (const SchedCandidate &Cand)

Protected Attributes
ScheduleDAGMILive *	DAG = nullptr

MachineSchedPolicy	RegionPolicy

SchedBoundary	Top

SchedBoundary	Bot

SchedCandidate	TopCand
	Candidate last picked from Top boundary. More...

SchedCandidate	BotCand
	Candidate last picked from Bot boundary. More...

Protected Attributes inherited from llvm::GenericSchedulerBase
const MachineSchedContext *	Context

const TargetSchedModel *	SchedModel = nullptr

const TargetRegisterInfo *	TRI = nullptr

SchedRemainder	Rem

Additional Inherited Members
Public Types inherited from llvm::GenericSchedulerBase
enum	CandReason : uint8_t { NoCand, Only1, PhysReg, RegExcess, RegCritical, Stall, Cluster, Weak, RegMax, ResourceReduce, ResourceDemand, BotHeightReduce, BotPathReduce, TopDepthReduce, TopPathReduce, NextDefUse, NodeOrder }
	Represent the type of SchedCandidate found within a single queue. More...

Static Public Member Functions inherited from llvm::GenericSchedulerBase
static const char *	getReasonStr (GenericSchedulerBase::CandReason Reason)

Detailed Description

GenericScheduler shrinks the unscheduled zone using heuristics to balance the schedule.

Definition at line 935 of file MachineScheduler.h.

Constructor & Destructor Documentation

◆ GenericScheduler()

llvm::GenericScheduler::GenericScheduler ( const MachineSchedContext * C )

inline

Definition at line 937 of file MachineScheduler.h.

Member Function Documentation

◆ checkAcyclicLatency()

void GenericScheduler::checkAcyclicLatency ( )

protected

Set IsAcyclicLatencyLimited if the acyclic path is longer than the cyclic critical path by more cycles than it takes to drain the instruction buffer.

We estimate an upper bounds on in-flight instructions as:

CyclesPerIteration = max( CyclicPath, Loop-Resource-Height ) InFlightIterations = AcyclicPath / CyclesPerIteration InFlightResources = InFlightIterations * LoopResources

TODO: Check execution resources in addition to IssueCount.

Definition at line 2783 of file MachineScheduler.cpp.

References llvm::dbgs(), LLVM_DEBUG, and llvm::max().

◆ dumpPolicy()

void GenericScheduler::dumpPolicy ( ) const

overridevirtual

Reimplemented from llvm::MachineSchedStrategy.

Definition at line 2763 of file MachineScheduler.cpp.

References llvm::dbgs().

◆ initCandidate()

void GenericScheduler::initCandidate	(	SchedCandidate &	Cand,
		SUnit *	SU,
		bool	AtTop,
		const RegPressureTracker &	RPTracker,
		RegPressureTracker &	TempTracker
	)

protected

◆ initialize()

void GenericScheduler::initialize ( ScheduleDAGMI * DAG )

overridevirtual

Initialize the strategy after building the DAG for a new region.

Implements llvm::MachineSchedStrategy.

Reimplemented in llvm::GCNMaxOccupancySchedStrategy.

Definition at line 2686 of file MachineScheduler.cpp.

References assert(), llvm::ScheduleDAGInstrs::getSchedModel(), llvm::ScheduleDAGMI::hasVRegLiveness(), and TRI.

Referenced by llvm::GCNMaxOccupancySchedStrategy::initialize().

◆ initPolicy()

void GenericScheduler::initPolicy	(	MachineBasicBlock::iterator	Begin,
		MachineBasicBlock::iterator	End,
		unsigned	NumRegionInstrs
	)

overridevirtual

Initialize the per-region scheduling policy.

Reimplemented from llvm::MachineSchedStrategy.

Definition at line 2717 of file MachineScheduler.cpp.

◆ pickNode()

SUnit * GenericScheduler::pickNode ( bool & IsTopNode )

overridevirtual

Pick the best node to balance the schedule. Implements MachineSchedStrategy.

Implements llvm::MachineSchedStrategy.

Reimplemented in llvm::GCNMaxOccupancySchedStrategy.

Definition at line 3180 of file MachineScheduler.cpp.

References assert(), llvm::ScheduleDAGMI::bottom(), llvm::dbgs(), llvm::ScheduleDAGMILive::getBotRPTracker(), llvm::SUnit::getInstr(), llvm::ScheduleDAGMILive::getTopRPTracker(), llvm::SUnit::isBottomReady(), llvm::SUnit::isScheduled, llvm::SUnit::isTopReady(), LLVM_DEBUG, llvm::NoCand, llvm::SUnit::NodeNum, llvm::ScheduleDAGMI::top(), and tracePick().

◆ pickNodeBidirectional()

SUnit * GenericScheduler::pickNodeBidirectional ( bool & IsTopNode )

protected

Pick the best candidate node from either the top or bottom queue.

Definition at line 3101 of file MachineScheduler.cpp.

References assert(), llvm::dbgs(), llvm::ScheduleDAGMILive::getBotRPTracker(), llvm::ScheduleDAGMILive::getTopRPTracker(), LLVM_DEBUG, llvm::NoCand, llvm::GenericSchedulerBase::SchedCandidate::Reason, llvm::GenericSchedulerBase::SchedCandidate::reset(), llvm::GenericSchedulerBase::SchedCandidate::SU, and tracePick().

◆ pickNodeFromQueue()

void GenericScheduler::pickNodeFromQueue	(	SchedBoundary &	Zone,
		const CandPolicy &	ZonePolicy,
		const RegPressureTracker &	RPTracker,
		SchedCandidate &	Cand
	)

protected

Pick the best candidate from the queue.

TODO: getMaxPressureDelta results can be mostly cached for each SUnit during DAG building. To adjust for the current scheduling location we need to maintain the number of vreg uses remaining to be top-scheduled.

Definition at line 3075 of file MachineScheduler.cpp.

References llvm::GenericSchedulerBase::SchedCandidate::AtTop, llvm::SchedBoundary::Available, llvm::GenericSchedulerBase::SchedCandidate::initResourceDelta(), llvm::SchedBoundary::isTop(), LLVM_DEBUG, llvm::NoCand, llvm::GenericSchedulerBase::SchedCandidate::Reason, llvm::GenericSchedulerBase::SchedCandidate::ResDelta, and llvm::GenericSchedulerBase::SchedCandidate::setBest().

◆ registerRoots()

void GenericScheduler::registerRoots ( )

overridevirtual

Notify this strategy that all roots have been released (including those that depend on EntrySU or ExitSU).

Reimplemented from llvm::MachineSchedStrategy.

Definition at line 2811 of file MachineScheduler.cpp.

References llvm::ScheduleDAGMILive::computeCyclicCriticalPath(), llvm::dbgs(), llvm::DumpCriticalPathLength, llvm::errs(), llvm::ScheduleDAG::ExitSU, llvm::SUnit::getDepth(), and LLVM_DEBUG.

◆ releaseBottomNode()

void llvm::GenericScheduler::releaseBottomNode ( SUnit * SU )

inlineoverridevirtual

When all successor dependencies have been resolved, free this node for bottom-up scheduling.

Implements llvm::MachineSchedStrategy.

Definition at line 969 of file MachineScheduler.h.

References llvm::SUnit::BotReadyCycle, and llvm::SUnit::isScheduled.

◆ releaseTopNode()

void llvm::GenericScheduler::releaseTopNode ( SUnit * SU )

inlineoverridevirtual

When all predecessor dependencies have been resolved, free this node for top-down scheduling.

Implements llvm::MachineSchedStrategy.

Definition at line 961 of file MachineScheduler.h.

References llvm::SUnit::isScheduled, and llvm::SUnit::TopReadyCycle.

◆ reschedulePhysReg()

void GenericScheduler::reschedulePhysReg	(	SUnit *	SU,
		bool	isTop
	)

protected

Definition at line 3225 of file MachineScheduler.cpp.

References llvm::SDep::Data, llvm::dbgs(), llvm::ScheduleDAGInstrs::dumpNode(), llvm::SUnit::getInstr(), llvm::MachineInstr::isCopy(), llvm::MachineInstr::isMoveImmediate(), LLVM_DEBUG, llvm::ScheduleDAGMI::moveInstruction(), llvm::SUnit::Preds, llvm::SUnit::Succs, and TRI.

◆ schedNode()

void GenericScheduler::schedNode	(	SUnit *	SU,
		bool	IsTopNode
	)

overridevirtual

Update the scheduler's state after scheduling a node.

This is the same node that was just returned by pickNode(). However, ScheduleDAGMILive needs to update it's state based on the current cycle before MachineSchedStrategy does.

FIXME: Eventually, we may bundle physreg copies rather than rescheduling them here. See comments in biasPhysReg.

Implements llvm::MachineSchedStrategy.

Definition at line 3255 of file MachineScheduler.cpp.

References llvm::SUnit::BotReadyCycle, llvm::SUnit::hasPhysRegDefs, llvm::SUnit::hasPhysRegUses, llvm::max(), and llvm::SUnit::TopReadyCycle.

◆ shouldTrackLaneMasks()

bool llvm::GenericScheduler::shouldTrackLaneMasks ( ) const

inlineoverridevirtual

Returns true if lanemasks should be tracked.

LaneMask tracking is necessary to reorder independent subregister defs for the same vreg. This has to be enabled in combination with shouldTrackPressure().

Reimplemented from llvm::MachineSchedStrategy.

Definition at line 951 of file MachineScheduler.h.

References initialize().

◆ shouldTrackPressure()

bool llvm::GenericScheduler::shouldTrackPressure ( ) const

inlineoverridevirtual

Check if pressure tracking is needed before building the DAG and initializing this strategy.

Called after initPolicy.

Reimplemented from llvm::MachineSchedStrategy.

Definition at line 947 of file MachineScheduler.h.

◆ tryCandidate()

void GenericScheduler::tryCandidate	(	SchedCandidate &	Cand,
		SchedCandidate &	TryCand,
		SchedBoundary *	Zone
	)		const

protectedvirtual

Apply a set of heuristics to a new candidate.

Heuristics are currently hierarchical. This may be more efficient than a graduated cost model because we don't need to evaluate all aspects of the model for each node in the queue. But it's really done to make the heuristics easier to debug and statistically analyze.

Parameters

Cand	provides the policy and current best candidate.
TryCand	refers to the next SUnit candidate, otherwise uninitialized.
Zone	describes the scheduled zone that we are extending, or nullptr

Definition at line 2967 of file MachineScheduler.cpp.

Referenced by llvm::GCNMaxOccupancySchedStrategy::initialize().

Member Data Documentation

◆ Bot

SchedBoundary llvm::GenericScheduler::Bot

protected

Definition at line 986 of file MachineScheduler.h.

Referenced by llvm::GCNMaxOccupancySchedStrategy::initialize(), and llvm::GCNMaxOccupancySchedStrategy::pickNode().

◆ BotCand

SchedCandidate llvm::GenericScheduler::BotCand

protected

Candidate last picked from Bot boundary.

Definition at line 991 of file MachineScheduler.h.

Referenced by llvm::GCNMaxOccupancySchedStrategy::initialize(), and llvm::GCNMaxOccupancySchedStrategy::pickNode().

◆ DAG

ScheduleDAGMILive* llvm::GenericScheduler::DAG = nullptr

protected

Definition at line 980 of file MachineScheduler.h.

Referenced by llvm::GCNMaxOccupancySchedStrategy::initialize(), and llvm::GCNMaxOccupancySchedStrategy::pickNode().

◆ RegionPolicy

MachineSchedPolicy llvm::GenericScheduler::RegionPolicy

protected

Definition at line 982 of file MachineScheduler.h.

Referenced by llvm::GCNMaxOccupancySchedStrategy::pickNode().

◆ Top

SchedBoundary llvm::GenericScheduler::Top

protected

Definition at line 985 of file MachineScheduler.h.

Referenced by llvm::GCNMaxOccupancySchedStrategy::initialize(), and llvm::GCNMaxOccupancySchedStrategy::pickNode().

◆ TopCand

SchedCandidate llvm::GenericScheduler::TopCand

protected

Candidate last picked from Top boundary.

Definition at line 989 of file MachineScheduler.h.

Referenced by llvm::GCNMaxOccupancySchedStrategy::initialize(), and llvm::GCNMaxOccupancySchedStrategy::pickNode().

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

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

Public Member Functions

Protected Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ GenericScheduler()

Member Function Documentation

◆ checkAcyclicLatency()

◆ dumpPolicy()

◆ initCandidate()

◆ initialize()

◆ initPolicy()

◆ pickNode()

◆ pickNodeBidirectional()

◆ pickNodeFromQueue()

◆ registerRoots()

◆ releaseBottomNode()

◆ releaseTopNode()

◆ reschedulePhysReg()

◆ schedNode()

◆ shouldTrackLaneMasks()

◆ shouldTrackPressure()

◆ tryCandidate()

Member Data Documentation

◆ Bot

◆ BotCand

◆ DAG

◆ RegionPolicy

◆ Top

◆ TopCand