This class models the most basic scheduling problem. More...

#include <Problems.h>

Inheritance diagram for circt::scheduling::Problem:

[legend]

Collaboration diagram for circt::scheduling::Problem:

[legend]

Public Types
using	Dependence = detail::Dependence
	A thin wrapper to allow a uniform handling of def-use and auxiliary dependences. More...

using	OperatorType = mlir::StringAttr
	Operator types are distinguished by name (chosen by the client). More...

using	OperationSet = llvm::SetVector< Operation * >

using	DependenceRange = llvm::iterator_range< detail::DependenceIterator >

using	OperatorTypeSet = llvm::SetVector< OperatorType >

using	PropertyStringVector = llvm::SmallVector< std::pair< std::string, std::string >, 2 >

Public Member Functions
virtual	~Problem ()=default

void	insertOperation (Operation *op)
	Include `op` in this scheduling problem. More...

LogicalResult	insertDependence (Dependence dep)
	Include `dep` in the scheduling problem. More...

void	insertOperatorType (OperatorType opr)
	Include `opr` in this scheduling problem. More...

OperatorType	getOrInsertOperatorType (StringRef name)
	Retrieves the operator type identified by the client-specific `name`. More...

Operation *	getContainingOp ()
	Return the operation containing this problem, e.g. to emit diagnostics. More...

void	setContainingOp (Operation *op)
	Set the operation containing this problem, e.g. to emit diagnostics. More...

bool	hasOperation (Operation *op)
	Return true if `op` is part of this problem. More...

const OperationSet &	getOperations ()
	Return the set of operations. More...

DependenceRange	getDependences (Operation *op)
	Return a range object to transparently iterate over `op's` incoming 1) implicit def-use dependences (backed by the SSA graph), and then 2) explictly added auxiliary dependences. More...

bool	hasOperatorType (OperatorType opr)
	Return true if `opr` is part of this problem. More...

const OperatorTypeSet &	getOperatorTypes ()
	Return the set of operator types. More...

std::optional< OperatorType >	getLinkedOperatorType (Operation *op)
	The linked operator type provides the runtime characteristics for `op`. More...

void	setLinkedOperatorType (Operation *op, OperatorType opr)

std::optional< unsigned >	getLatency (OperatorType opr)
	The latency is the number of cycles `opr` needs to compute its result. More...

void	setLatency (OperatorType opr, unsigned val)

std::optional< unsigned >	getStartTime (Operation *op)
	Return the start time for `op`, as computed by the scheduler. More...

void	setStartTime (Operation *op, unsigned val)

std::optional< unsigned >	getEndTime (Operation *op)
	Returns the end time for `op`, as computed by the scheduler. More...

StringAttr	getInstanceName ()

void	setInstanceName (StringAttr name)

StringAttr	getLibraryName ()

void	setLibraryName (StringAttr name)

StringAttr	getOperationName (Operation *op)

void	setOperationName (Operation *op, StringAttr name)

virtual PropertyStringVector	getProperties (Operation *op)

virtual PropertyStringVector	getProperties (Dependence dep)

virtual PropertyStringVector	getProperties (OperatorType opr)

virtual PropertyStringVector	getProperties ()

virtual LogicalResult	check ()
	Return success if the constructed scheduling problem is valid. More...

virtual LogicalResult	verify ()
	Return success if the computed solution is valid. More...

Protected Types
using	AuxDependenceMap = llvm::DenseMap< Operation , llvm::SmallSetVector< Operation , 4 > >

template<typename T >
using	OperationProperty = llvm::DenseMap< Operation *, std::optional< T > >

template<typename T >
using	DependenceProperty = llvm::DenseMap< Dependence, std::optional< T > >

template<typename T >
using	OperatorTypeProperty = llvm::DenseMap< OperatorType, std::optional< T > >

template<typename T >
using	InstanceProperty = std::optional< T >

Protected Member Functions
virtual LogicalResult	checkLinkedOperatorType (Operation *op)
	`op` is linked to a registered operator type. More...

virtual LogicalResult	checkLatency (OperatorType opr)
	`opr` has a latency. More...

virtual LogicalResult	verifyStartTime (Operation *op)
	`op` has a start time. More...

virtual LogicalResult	verifyPrecedence (Dependence dep)
	`dep's` source operation is available before `dep's` destination operation starts. More...

Private Attributes
Operation *	containingOp

OperationSet	operations

AuxDependenceMap	auxDependences

OperatorTypeSet	operatorTypes

OperationProperty< OperatorType >	linkedOperatorType

OperationProperty< unsigned >	startTime

OperatorTypeProperty< unsigned >	latency

StringAttr	instanceName

StringAttr	libraryName

SmallDenseMap< Operation *, StringAttr >	operationNames

Detailed Description

This class models the most basic scheduling problem.

A problem instance is comprised of:

Operations: The vertices in the data-flow graph to be scheduled.
Dependences: The edges in the data-flow graph to be scheduled, modeling a precedence relation between the involved operations.
Operator types: An abstraction of the characteristics of the target representation, e.g. modules in the HLS component library, available functional units, etc. – operations are executed on instances/units of an operator type.

Operations and operator types are stored explicitly. The registered operations induce a subgraph of the SSA graph. We implicitly include the dependences corresponding to its def-use relationships in the problem, e.g. if operation y's second operand uses the first result produced by x, we'd have a dependence x:0 --> y:1. Clients can additionally register explicit, auxiliary dependence between operations, e.g. to encode memory dependencies or other ordering constraints. Auxiliary dependences do not distinguish specific operands/results. The differences between the flavors are transparent to concrete algorithms.

All components of the problem (operations, dependences, operator types, as well as the instance itself) can be annotated with properties. In this basic problem, we model

linkedOperatorType maps operations to their operator types.
latency, an operator type-property denoting the number of time steps after which the operator's result is available.
startTime, an operation-property for the time step in which an operation is started. Together, the start times for all operations represent the problem's solution, i.e. the schedule.

Subclasses, i.e. corresponding to more complex scheduling problems, can declare additional properties as needed. The check... methods perform validity checks before scheduling, e.g. that all operations have an associated operator type, etc.

The verify... methods check the correctness of the solution determined by a concrete scheduling algorithm, e.g. that there are start times available for each registered operation, and the precedence constraints as modeled by the dependences are satisfied.

Definition at line 87 of file Problems.h.

Member Typedef Documentation

◆ AuxDependenceMap

using circt::scheduling::Problem::AuxDependenceMap = llvm::DenseMap<Operation *, llvm::SmallSetVector<Operation *, 4> >

protected

Definition at line 115 of file Problems.h.

◆ Dependence

using circt::scheduling::Problem::Dependence = detail::Dependence

A thin wrapper to allow a uniform handling of def-use and auxiliary dependences.

Definition at line 101 of file Problems.h.

◆ DependenceProperty

template<typename T >

using circt::scheduling::Problem::DependenceProperty = llvm::DenseMap<Dependence, std::optional<T> >

protected

Definition at line 121 of file Problems.h.

◆ DependenceRange

using circt::scheduling::Problem::DependenceRange = llvm::iterator_range<detail::DependenceIterator>

Definition at line 111 of file Problems.h.

◆ InstanceProperty

template<typename T >

using circt::scheduling::Problem::InstanceProperty = std::optional<T>

protected

Definition at line 125 of file Problems.h.

◆ OperationProperty

template<typename T >

using circt::scheduling::Problem::OperationProperty = llvm::DenseMap<Operation *, std::optional<T> >

protected

Definition at line 119 of file Problems.h.

◆ OperationSet

using circt::scheduling::Problem::OperationSet = llvm::SetVector<Operation *>

Definition at line 110 of file Problems.h.

◆ OperatorType

using circt::scheduling::Problem::OperatorType = mlir::StringAttr

Operator types are distinguished by name (chosen by the client).

Definition at line 104 of file Problems.h.

◆ OperatorTypeProperty

template<typename T >

using circt::scheduling::Problem::OperatorTypeProperty = llvm::DenseMap<OperatorType, std::optional<T> >

protected

Definition at line 123 of file Problems.h.

◆ OperatorTypeSet

using circt::scheduling::Problem::OperatorTypeSet = llvm::SetVector<OperatorType>

Definition at line 112 of file Problems.h.

◆ PropertyStringVector

using circt::scheduling::Problem::PropertyStringVector = llvm::SmallVector<std::pair<std::string, std::string>, 2>

Definition at line 257 of file Problems.h.

Constructor & Destructor Documentation

◆ ~Problem()

virtual circt::scheduling::Problem::~Problem ( )

virtualdefault

Member Function Documentation

◆ check()

LogicalResult Problem::check ( )

virtual

Return success if the constructed scheduling problem is valid.

Reimplemented in circt::scheduling::ChainingProblem.

Definition at line 96 of file Problems.cpp.

Referenced by circt::scheduling::ChainingProblem::check().

◆ checkLatency()

LogicalResult Problem::checkLatency ( OperatorType opr )

protectedvirtual

opr has a latency.

Reimplemented in circt::scheduling::SharedOperatorsProblem.

Definition at line 88 of file Problems.cpp.

Referenced by circt::scheduling::SharedOperatorsProblem::checkLatency().

◆ checkLinkedOperatorType()

LogicalResult Problem::checkLinkedOperatorType ( Operation * op )

protectedvirtual

op is linked to a registered operator type.

Definition at line 80 of file Problems.cpp.

◆ getContainingOp()

Operation* circt::scheduling::Problem::getContainingOp ( )

inline

Return the operation containing this problem, e.g. to emit diagnostics.

Definition at line 171 of file Problems.h.

References containingOp.

Referenced by circt::scheduling::handleOperationsInTopologicalOrder(), circt::scheduling::scheduleCPSAT(), and circt::scheduling::scheduleLP().

◆ getDependences()

Problem::DependenceRange Problem::getDependences ( Operation * op )

Return a range object to transparently iterate over op's incoming 1) implicit def-use dependences (backed by the SSA graph), and then 2) explictly added auxiliary dependences.

In other words, this yields dependences whose destination operation is op, and whose source operations are op's predecessors in the problem graph.

To iterate over all of the scheduling problem's dependences, simply process the ranges for all registered operations.

Definition at line 53 of file Problems.cpp.

Referenced by circt::scheduling::computeStartTimesInCycle(), circt::scheduling::dumpAsDOT(), circt::scheduling::scheduleASAP(), circt::scheduling::scheduleCPSAT(), and circt::scheduling::scheduleLP().

◆ getEndTime()

std::optional< unsigned > Problem::getEndTime ( Operation * op )

Returns the end time for op, as computed by the scheduler.

This end time is derived from the start time and the operator type's latency.

Definition at line 145 of file Problems.cpp.

◆ getInstanceName()

StringAttr circt::scheduling::Problem::getInstanceName ( )

inline

Definition at line 240 of file Problems.h.

References instanceName.

◆ getLatency()

std::optional<unsigned> circt::scheduling::Problem::getLatency ( OperatorType opr )

inline

The latency is the number of cycles opr needs to compute its result.

Definition at line 210 of file Problems.h.

References latency.

Referenced by circt::scheduling::scheduleCPSAT(), and circt::scheduling::scheduleLP().

◆ getLibraryName()

StringAttr circt::scheduling::Problem::getLibraryName ( )

inline

Definition at line 243 of file Problems.h.

References libraryName.

◆ getLinkedOperatorType()

std::optional<OperatorType> circt::scheduling::Problem::getLinkedOperatorType ( Operation * op )

inline

The linked operator type provides the runtime characteristics for op.

Definition at line 202 of file Problems.h.

References linkedOperatorType.

Referenced by isLimited(), circt::scheduling::scheduleCPSAT(), and circt::scheduling::scheduleLP().

◆ getOperationName()

StringAttr circt::scheduling::Problem::getOperationName ( Operation * op )

inline

Definition at line 246 of file Problems.h.

References operationNames.

◆ getOperations()

const OperationSet& circt::scheduling::Problem::getOperations ( )

inline

Return the set of operations.

Definition at line 178 of file Problems.h.

References operations.

Referenced by circt::scheduling::dumpAsDOT(), circt::scheduling::handleOperationsInTopologicalOrder(), circt::scheduling::scheduleCPSAT(), and circt::scheduling::scheduleLP().

◆ getOperatorTypes()

const OperatorTypeSet& circt::scheduling::Problem::getOperatorTypes ( )

inline

Return the set of operator types.

Definition at line 195 of file Problems.h.

References operatorTypes.

Referenced by circt::scheduling::dumpAsDOT().

◆ getOrInsertOperatorType()

Problem::OperatorType Problem::getOrInsertOperatorType ( StringRef name )

Retrieves the operator type identified by the client-specific name.

The operator type is automatically registered in the scheduling problem.

Definition at line 47 of file Problems.cpp.

References circt::calyx::direction::get().

◆ getProperties() [1/4]

Problem::PropertyStringVector Problem::getProperties ( )

virtual

Reimplemented in circt::scheduling::CyclicProblem.

Definition at line 78 of file Problems.cpp.

Referenced by circt::scheduling::CyclicProblem::getProperties(), circt::scheduling::ChainingProblem::getProperties(), and circt::scheduling::SharedOperatorsProblem::getProperties().

◆ getProperties() [2/4]

Problem::PropertyStringVector Problem::getProperties ( Dependence dep )

virtual

Reimplemented in circt::scheduling::CyclicProblem.

Definition at line 67 of file Problems.cpp.

◆ getProperties() [3/4]

Problem::PropertyStringVector Problem::getProperties ( Operation * op )

virtual

Reimplemented in circt::scheduling::ChainingProblem.

Definition at line 58 of file Problems.cpp.

Referenced by circt::scheduling::dumpAsDOT().

◆ getProperties() [4/4]

Problem::PropertyStringVector Problem::getProperties ( OperatorType opr )

virtual

Reimplemented in circt::scheduling::SharedOperatorsProblem, and circt::scheduling::ChainingProblem.

Definition at line 71 of file Problems.cpp.

◆ getStartTime()

std::optional<unsigned> circt::scheduling::Problem::getStartTime ( Operation * op )

inline

Return the start time for op, as computed by the scheduler.

These start times comprise the basic problem's solution, i.e. the schedule.

Definition at line 218 of file Problems.h.

References startTime.

Referenced by circt::scheduling::computeStartTimesInCycle().

◆ hasOperation()

bool circt::scheduling::Problem::hasOperation ( Operation * op )

inline

Return true if op is part of this problem.

Definition at line 176 of file Problems.h.

References operations.

Referenced by circt::scheduling::detail::DependenceIterator::findNextDependence(), circt::scheduling::scheduleCPSAT(), and circt::scheduling::scheduleLP().

◆ hasOperatorType()

bool circt::scheduling::Problem::hasOperatorType ( OperatorType opr )

inline

Return true if opr is part of this problem.

Definition at line 193 of file Problems.h.

References operatorTypes.

◆ insertDependence()

LogicalResult Problem::insertDependence ( Dependence dep )

Include dep in the scheduling problem.

Return failure if dep does not represent a valid def-use or auxiliary dependence between operations. The endpoints become registered operations w.r.t. the problem.

Definition at line 26 of file Problems.cpp.

References circt::scheduling::detail::Dependence::getDestination(), circt::scheduling::detail::Dependence::getSource(), and circt::scheduling::detail::Dependence::isAuxiliary().

Referenced by circt::analysis::CyclicSchedulingAnalysis::analyzeForOp().

◆ insertOperation()

void circt::scheduling::Problem::insertOperation ( Operation * op )

inline

Include op in this scheduling problem.

Definition at line 152 of file Problems.h.

References operations.

Referenced by circt::analysis::CyclicSchedulingAnalysis::analyzeForOp().

◆ insertOperatorType()

void circt::scheduling::Problem::insertOperatorType ( OperatorType opr )

inline

Include opr in this scheduling problem.

Definition at line 160 of file Problems.h.

References operatorTypes.

◆ setContainingOp()

void circt::scheduling::Problem::setContainingOp ( Operation * op )

inline

Set the operation containing this problem, e.g. to emit diagnostics.

Definition at line 173 of file Problems.h.

References containingOp.

◆ setInstanceName()

void circt::scheduling::Problem::setInstanceName ( StringAttr name )

inline

Definition at line 241 of file Problems.h.

References instanceName.

◆ setLatency()

void circt::scheduling::Problem::setLatency	(	OperatorType	opr,
		unsigned	val
	)

inline

Definition at line 213 of file Problems.h.

References latency.

◆ setLibraryName()

void circt::scheduling::Problem::setLibraryName ( StringAttr name )

inline

Definition at line 244 of file Problems.h.

References libraryName.

◆ setLinkedOperatorType()

void circt::scheduling::Problem::setLinkedOperatorType	(	Operation *	op,
		OperatorType	opr
	)

inline

Definition at line 205 of file Problems.h.

References linkedOperatorType.

◆ setOperationName()

void circt::scheduling::Problem::setOperationName	(	Operation *	op,
		StringAttr	name
	)

inline

Definition at line 249 of file Problems.h.

References operationNames.

◆ setStartTime()

void circt::scheduling::Problem::setStartTime	(	Operation *	op,
		unsigned	val
	)

inline

Definition at line 221 of file Problems.h.

References startTime.

Referenced by circt::scheduling::scheduleASAP(), circt::scheduling::scheduleCPSAT(), and circt::scheduling::scheduleLP().

◆ verify()

LogicalResult Problem::verify ( )

virtual

Return success if the computed solution is valid.

Reimplemented in circt::scheduling::ModuloProblem, circt::scheduling::SharedOperatorsProblem, circt::scheduling::ChainingProblem, and circt::scheduling::CyclicProblem.

Definition at line 132 of file Problems.cpp.

Referenced by circt::scheduling::CyclicProblem::verify(), circt::scheduling::ChainingProblem::verify(), and circt::scheduling::SharedOperatorsProblem::verify().

◆ verifyPrecedence()

LogicalResult Problem::verifyPrecedence ( Dependence dep )

protectedvirtual

dep's source operation is available before dep's destination operation starts.

Reimplemented in circt::scheduling::CyclicProblem.

Definition at line 114 of file Problems.cpp.

References circt::scheduling::detail::Dependence::getDestination(), and circt::scheduling::detail::Dependence::getSource().

◆ verifyStartTime()

LogicalResult Problem::verifyStartTime ( Operation * op )

protectedvirtual

op has a start time.

Definition at line 108 of file Problems.cpp.

Member Data Documentation

◆ auxDependences

AuxDependenceMap circt::scheduling::Problem::auxDependences

private

Definition at line 137 of file Problems.h.

Referenced by circt::scheduling::detail::DependenceIterator::DependenceIterator().

◆ containingOp

Operation* circt::scheduling::Problem::containingOp

private

Definition at line 133 of file Problems.h.

Referenced by getContainingOp(), and setContainingOp().

◆ instanceName

StringAttr circt::scheduling::Problem::instanceName

private

Definition at line 236 of file Problems.h.

Referenced by getInstanceName(), and setInstanceName().

◆ latency

OperatorTypeProperty<unsigned> circt::scheduling::Problem::latency

private

Definition at line 145 of file Problems.h.

Referenced by getLatency(), and setLatency().

◆ libraryName

StringAttr circt::scheduling::Problem::libraryName

private

Definition at line 236 of file Problems.h.

Referenced by getLibraryName(), and setLibraryName().

◆ linkedOperatorType

OperationProperty<OperatorType> circt::scheduling::Problem::linkedOperatorType

private

Definition at line 141 of file Problems.h.

Referenced by getLinkedOperatorType(), and setLinkedOperatorType().

◆ operationNames

SmallDenseMap<Operation *, StringAttr> circt::scheduling::Problem::operationNames

private

Definition at line 237 of file Problems.h.

Referenced by getOperationName(), and setOperationName().

◆ operations

OperationSet circt::scheduling::Problem::operations

private

Definition at line 136 of file Problems.h.

Referenced by getOperations(), hasOperation(), and insertOperation().

◆ operatorTypes

OperatorTypeSet circt::scheduling::Problem::operatorTypes

private

Definition at line 138 of file Problems.h.

Referenced by getOperatorTypes(), hasOperatorType(), and insertOperatorType().

◆ startTime

OperationProperty<unsigned> circt::scheduling::Problem::startTime

private

Definition at line 142 of file Problems.h.

Referenced by getStartTime(), and setStartTime().

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

include/circt/Scheduling/Problems.h
lib/Scheduling/Problems.cpp

Public Types

Public Member Functions

Protected Types

Protected Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ AuxDependenceMap

◆ Dependence

◆ DependenceProperty

◆ DependenceRange

◆ InstanceProperty

◆ OperationProperty

◆ OperationSet

◆ OperatorType

◆ OperatorTypeProperty

◆ OperatorTypeSet

◆ PropertyStringVector

Constructor & Destructor Documentation

◆ ~Problem()

Member Function Documentation

◆ check()

◆ checkLatency()

◆ checkLinkedOperatorType()

◆ getContainingOp()

◆ getDependences()

◆ getEndTime()

◆ getInstanceName()

◆ getLatency()

◆ getLibraryName()

◆ getLinkedOperatorType()

◆ getOperationName()

◆ getOperations()

◆ getOperatorTypes()

◆ getOrInsertOperatorType()

◆ getProperties() [1/4]

◆ getProperties() [2/4]

◆ getProperties() [3/4]

◆ getProperties() [4/4]

◆ getStartTime()

◆ hasOperation()

◆ hasOperatorType()

◆ insertDependence()

◆ insertOperation()

◆ insertOperatorType()

◆ setContainingOp()

◆ setInstanceName()

◆ setLatency()

◆ setLibraryName()

◆ setLinkedOperatorType()

◆ setOperationName()

◆ setStartTime()

◆ verify()

◆ verifyPrecedence()

◆ verifyStartTime()

Member Data Documentation

◆ auxDependences

◆ containingOp

◆ instanceName

◆ latency

◆ libraryName

◆ linkedOperatorType

◆ operationNames

◆ operations

◆ operatorTypes

◆ startTime