This class models the modulo scheduling problem as the composition of the cyclic problem and the resource-constrained problem with fully-pipelined shared operators. More...

#include <Problems.h>

Inheritance diagram for circt::scheduling::ModuloProblem:

[legend]

Collaboration diagram for circt::scheduling::ModuloProblem:

[legend]

Public Member Functions
virtual LogicalResult	verify () override
	Return success if the computed solution is valid.

	CyclicProblem ()=default

Public Member Functions inherited from circt::scheduling::CyclicProblem
std::optional< unsigned >	getDistance (Dependence dep)
	The distance determines whether a dependence has to be satisfied in the same iteration (distance=0 or not set), or distance-many iterations later.

void	setDistance (Dependence dep, unsigned val)

std::optional< unsigned >	getInitiationInterval ()
	The initiation interval (II) is the number of time steps between subsequent iterations, i.e.

void	setInitiationInterval (unsigned val)

virtual PropertyStringVector	getProperties (Dependence dep) override

virtual PropertyStringVector	getProperties () override

	Problem (Operation *containingOp)
	Construct an empty scheduling problem.

	Problem ()=default

Public Member Functions inherited from circt::scheduling::Problem
	Problem (Operation *containingOp)
	Construct an empty scheduling problem.

virtual	~Problem ()=default

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

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

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

void	insertResourceType (ResourceType rsrc)
	Include `rsrc` in this scheduling problem.

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

ResourceType	getOrInsertResourceType (StringRef name)
	Retrieves the resource type identified by the client-specific `name`.

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

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

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

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

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.

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

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

bool	hasResourceType (ResourceType rsrc)
	Return true if `rsrc` is part of this problem.

const ResourceTypeSet &	getResourceTypes ()
	Return the set of resource types.

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

void	setLinkedOperatorType (Operation *op, OperatorType opr)

std::optional< SmallVector< ResourceType > >	getLinkedResourceTypes (Operation *op)
	The linked resource type provides the available resources for `op`.

void	setLinkedResourceTypes (Operation *op, SmallVector< ResourceType > rsrc)

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

void	setLatency (OperatorType opr, unsigned val)

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

void	setStartTime (Operation *op, unsigned val)

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

StringAttr	getInstanceName ()

void	setInstanceName (StringAttr name)

StringAttr	getLibraryName ()

void	setLibraryName (StringAttr name)

StringAttr	getRsrcLibraryName ()

void	setRsrcLibraryName (StringAttr name)

StringAttr	getOperationName (Operation *op)

void	setOperationName (Operation *op, StringAttr name)

virtual PropertyStringVector	getProperties (Operation *op)

virtual PropertyStringVector	getProperties (OperatorType opr)

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

Public Member Functions inherited from circt::scheduling::SharedOperatorsProblem
std::optional< unsigned >	getLimit (ResourceType rsrc)
	The limit is the maximum number of operations using `rsrc` that are available in the target hardware.

void	setLimit (ResourceType rsrc, unsigned val)

virtual PropertyStringVector	getProperties (ResourceType rsrc) override

	Problem (Operation *containingOp)
	Construct an empty scheduling problem.

	Problem ()=default

Static Public Attributes
static constexpr auto	name = "ModuloProblem"

Static Public Attributes inherited from circt::scheduling::CyclicProblem
static constexpr auto	name = "CyclicProblem"

Static Public Attributes inherited from circt::scheduling::Problem
static constexpr auto	name = "Problem"

Static Public Attributes inherited from circt::scheduling::SharedOperatorsProblem
static constexpr auto	name = "SharedOperatorsProblem"

Protected Member Functions
	ModuloProblem ()=default

virtual LogicalResult	verifyUtilization (ResourceType rsrc) override
	`opr` is not oversubscribed in any congruence class modulo II.

Protected Member Functions inherited from circt::scheduling::CyclicProblem
	CyclicProblem ()=default

virtual LogicalResult	verifyPrecedence (Dependence dep) override
	`dep's` source operation is available before `dep's` destination operation starts (`dep's` distance iterations later).

virtual LogicalResult	verifyInitiationInterval ()
	This problem has a non-zero II.

Protected Member Functions inherited from circt::scheduling::Problem
	Problem ()=default

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

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

Protected Member Functions inherited from circt::scheduling::SharedOperatorsProblem
	SharedOperatorsProblem ()=default

virtual LogicalResult	checkLatency (Operation *op) override
	If `op` is limited, it has a non-zero latency.

Additional Inherited Members
Public Types inherited from circt::scheduling::Problem
using	Dependence = detail::Dependence
	A thin wrapper to allow a uniform handling of def-use and auxiliary dependences.

using	OperationSet = llvm::SetVector< Operation * >

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

using	OperatorTypeSet = llvm::SetVector< OperatorType >

using	ResourceTypeSet = llvm::SetVector< ResourceType >

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

Protected Types inherited from circt::scheduling::Problem
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	ResourceTypeProperty = llvm::DenseMap< ResourceType, std::optional< T > >

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

Detailed Description

This class models the modulo scheduling problem as the composition of the cyclic problem and the resource-constrained problem with fully-pipelined shared operators.

A solution to this problem comprises an integer II and integer start times for all registered operations, and is feasible iff: (1) The precedence constraints implied by the CyclicProblem's dependence edges are satisfied, and (2) The number of operations that use a certain limited operator type, and start in the same congruence class (= start time mod II), does not exceed the operator type's limit.

Definition at line 528 of file Problems.h.

Constructor & Destructor Documentation

◆ ModuloProblem()

circt::scheduling::ModuloProblem::ModuloProblem ( )

protecteddefault

Member Function Documentation

◆ CyclicProblem()

circt::scheduling::CyclicProblem::CyclicProblem ( )

default

◆ verify()

LogicalResult ModuloProblem::verify ( )

overridevirtual

Return success if the computed solution is valid.

Reimplemented from circt::scheduling::CyclicProblem.

Definition at line 441 of file Problems.cpp.

References circt::scheduling::Problem::getResourceTypes(), circt::scheduling::CyclicProblem::verify(), and verifyUtilization().

◆ verifyUtilization()

LogicalResult ModuloProblem::verifyUtilization ( ResourceType rsrc )

overrideprotectedvirtual

opr is not oversubscribed in any congruence class modulo II.

Reimplemented from circt::scheduling::SharedOperatorsProblem.

Definition at line 411 of file Problems.cpp.

References circt::scheduling::Problem::getContainingOp(), circt::scheduling::CyclicProblem::getInitiationInterval(), circt::scheduling::SharedOperatorsProblem::getLimit(), circt::scheduling::Problem::getLinkedResourceTypes(), circt::scheduling::Problem::getOperations(), circt::scheduling::Problem::getStartTime(), circt::scheduling::Problem::ResourceType::getValue(), and circt::scheduling::SharedOperatorsProblem::limit.

Referenced by verify().

Member Data Documentation

◆ name

constexpr auto circt::scheduling::ModuloProblem::name = "ModuloProblem"

staticconstexpr

Definition at line 531 of file Problems.h.

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

/home/runner/work/circt-www/circt-www/circt_src/include/circt/Scheduling/Problems.h
/home/runner/work/circt-www/circt-www/circt_src/lib/Scheduling/Problems.cpp

Public Member Functions

Static Public Attributes

Protected Member Functions

Additional Inherited Members