CIRCT 21.0.0git
Loading...
Searching...
No Matches
Classes | Public Types | Public Member Functions | Static Public Attributes | Protected Types | Protected Member Functions | Private Attributes | List of all members
circt::scheduling::Problem Class Reference

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

#include <Problems.h>

Inheritance diagram for circt::scheduling::Problem:
Inheritance graph
[legend]
Collaboration diagram for circt::scheduling::Problem:
Collaboration graph
[legend]

Classes

struct  OperatorType
 Operator types are distinguished by name (chosen by the client). More...
 
struct  ResourceType
 Resource types are distinguished by name (chosen by the client). More...
 

Public Types

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 >
 

Public Member Functions

 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 OperationSetgetOperations ()
 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 OperatorTypeSetgetOperatorTypes ()
 Return the set of operator types.
 
bool hasResourceType (ResourceType rsrc)
 Return true if rsrc is part of this problem.
 
const ResourceTypeSetgetResourceTypes ()
 Return the set of resource types.
 
std::optional< OperatorTypegetLinkedOperatorType (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 (Dependence dep)
 
virtual PropertyStringVector getProperties (OperatorType opr)
 
virtual PropertyStringVector getProperties ()
 
virtual PropertyStringVector getProperties (ResourceType rsrc)
 
virtual LogicalResult check ()
 Return success if the constructed scheduling problem is valid.
 
virtual LogicalResult verify ()
 Return success if the computed solution is valid.
 

Static Public Attributes

static constexpr auto name = "Problem"
 

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 ResourceTypeProperty = llvm::DenseMap< ResourceType, std::optional< T > >
 
template<typename T >
using InstanceProperty = std::optional< T >
 

Protected Member Functions

 Problem ()=default
 
virtual LogicalResult checkLinkedOperatorType (Operation *op)
 op is linked to a registered operator type.
 
virtual LogicalResult checkLatency (Operation *op)
 op has a latency.
 
virtual LogicalResult verifyStartTime (Operation *op)
 op has a start time.
 
virtual LogicalResult verifyPrecedence (Dependence dep)
 dep's source operation is available before dep's destination operation starts.
 

Private Attributes

Operation * containingOp
 
OperationSet operations
 
AuxDependenceMap auxDependences
 
OperatorTypeSet operatorTypes
 
ResourceTypeSet resourceTypes
 
OperationProperty< OperatorTypelinkedOperatorType
 
OperationProperty< SmallVector< ResourceType > > linkedResourceTypes
 
OperationProperty< unsigned > startTime
 
OperatorTypeProperty< unsigned > latency
 
StringAttr instanceName
 
StringAttr libraryName
 
StringAttr rsrcLibraryName
 
SmallDenseMap< Operation *, StringAttr > operationNames
 

Detailed Description

This class models the most basic scheduling problem.

A problem instance is comprised of:

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

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 75 of file Problems.h.

Member Typedef Documentation

◆ AuxDependenceMap

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

Definition at line 152 of file Problems.h.

◆ Dependence

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

Definition at line 95 of file Problems.h.

◆ DependenceProperty

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

Definition at line 158 of file Problems.h.

◆ DependenceRange

Definition at line 147 of file Problems.h.

◆ InstanceProperty

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

Definition at line 164 of file Problems.h.

◆ OperationProperty

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

Definition at line 156 of file Problems.h.

◆ OperationSet

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

Definition at line 146 of file Problems.h.

◆ OperatorTypeProperty

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

Definition at line 160 of file Problems.h.

◆ OperatorTypeSet

Definition at line 148 of file Problems.h.

◆ PropertyStringVector

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

Definition at line 323 of file Problems.h.

◆ ResourceTypeProperty

template<typename T >
using circt::scheduling::Problem::ResourceTypeProperty = llvm::DenseMap<ResourceType, std::optional<T> >
protected

Definition at line 162 of file Problems.h.

◆ ResourceTypeSet

Definition at line 149 of file Problems.h.

Constructor & Destructor Documentation

◆ Problem() [1/2]

circt::scheduling::Problem::Problem ( Operation *  containingOp)
inlineexplicit

Construct an empty scheduling problem.

containingOp is used for its MLIRContext and to emit diagnostics.

Definition at line 81 of file Problems.h.

◆ ~Problem()

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

◆ Problem() [2/2]

circt::scheduling::Problem::Problem ( )
protecteddefault

Member Function Documentation

◆ check()

LogicalResult Problem::check ( )
virtual

Return success if the constructed scheduling problem is valid.

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

Definition at line 111 of file Problems.cpp.

References checkLatency(), checkLinkedOperatorType(), and getOperations().

Referenced by circt::scheduling::ChainingProblem::check(), and circt::scheduling::ChainingCyclicProblem::check().

◆ checkLatency()

LogicalResult Problem::checkLatency ( Operation *  op)
protectedvirtual

◆ checkLinkedOperatorType()

LogicalResult Problem::checkLinkedOperatorType ( Operation *  op)
protectedvirtual

op is linked to a registered operator type.

Definition at line 90 of file Problems.cpp.

References getLinkedOperatorType(), and hasOperatorType().

Referenced by check().

◆ getContainingOp()

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

◆ 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 59 of file Problems.cpp.

Referenced by circt::scheduling::ChainingCyclicProblem::check(), circt::scheduling::computeStartTimesInCycle(), circt::scheduling::dumpAsDOT(), circt::scheduling::scheduleASAP(), circt::scheduling::scheduleCPSAT(), circt::scheduling::scheduleLP(), circt::scheduling::scheduleLP(), verify(), and circt::scheduling::ChainingProblem::verify().

◆ 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 160 of file Problems.cpp.

References getLatency(), getLinkedOperatorType(), getStartTime(), latency, and startTime.

◆ getInstanceName()

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

Definition at line 303 of file Problems.h.

References instanceName.

◆ getLatency()

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

◆ getLibraryName()

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

Definition at line 306 of file Problems.h.

References libraryName.

◆ getLinkedOperatorType()

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

◆ getLinkedResourceTypes()

std::optional< SmallVector< ResourceType > > circt::scheduling::Problem::getLinkedResourceTypes ( Operation *  op)
inline

◆ getOperationName()

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

Definition at line 312 of file Problems.h.

References operationNames.

◆ getOperations()

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

◆ getOperatorTypes()

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

Return the set of operator types.

Definition at line 243 of file Problems.h.

References operatorTypes.

Referenced by circt::scheduling::ChainingProblem::check(), and 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 containingOp, circt::scheduling::Problem::OperatorType::get(), name, and operatorTypes.

◆ getOrInsertResourceType()

Problem::ResourceType Problem::getOrInsertResourceType ( StringRef  name)

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

The resource type is automatically registered in the scheduling problem.

Definition at line 53 of file Problems.cpp.

References containingOp, circt::scheduling::Problem::ResourceType::get(), name, and resourceTypes.

◆ getProperties() [1/5]

Problem::PropertyStringVector Problem::getProperties ( )
virtual

◆ getProperties() [2/5]

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

Reimplemented in circt::scheduling::CyclicProblem.

Definition at line 73 of file Problems.cpp.

◆ getProperties() [3/5]

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

Reimplemented in circt::scheduling::ChainingProblem.

Definition at line 64 of file Problems.cpp.

References getLinkedOperatorType(), getStartTime(), and startTime.

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

◆ getProperties() [4/5]

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

Reimplemented in circt::scheduling::ChainingProblem.

Definition at line 77 of file Problems.cpp.

References getLatency(), and latency.

◆ getProperties() [5/5]

Problem::PropertyStringVector Problem::getProperties ( ResourceType  rsrc)
virtual

Reimplemented in circt::scheduling::SharedOperatorsProblem.

Definition at line 86 of file Problems.cpp.

◆ getResourceTypes()

const ResourceTypeSet & circt::scheduling::Problem::getResourceTypes ( )
inline

Return the set of resource types.

Definition at line 250 of file Problems.h.

References resourceTypes.

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

◆ getRsrcLibraryName()

StringAttr circt::scheduling::Problem::getRsrcLibraryName ( )
inline

Definition at line 309 of file Problems.h.

References rsrcLibraryName.

◆ getStartTime()

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

◆ hasOperation()

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

◆ hasOperatorType()

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

Return true if opr is part of this problem.

Definition at line 241 of file Problems.h.

References operatorTypes.

Referenced by checkLinkedOperatorType().

◆ hasResourceType()

bool circt::scheduling::Problem::hasResourceType ( ResourceType  rsrc)
inline

Return true if rsrc is part of this problem.

Definition at line 246 of file Problems.h.

References resourceTypes.

◆ 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 auxDependences, circt::scheduling::detail::Dependence::getDestination(), circt::scheduling::detail::Dependence::getSource(), circt::scheduling::detail::Dependence::isAuxiliary(), and operations.

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

◆ insertOperation()

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

Include op in this scheduling problem.

Definition at line 193 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 201 of file Problems.h.

References operatorTypes.

◆ insertResourceType()

void circt::scheduling::Problem::insertResourceType ( ResourceType  rsrc)
inline

Include rsrc in this scheduling problem.

Definition at line 204 of file Problems.h.

References resourceTypes.

◆ setContainingOp()

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

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

Definition at line 221 of file Problems.h.

References containingOp.

◆ setInstanceName()

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

Definition at line 304 of file Problems.h.

References instanceName, and name.

◆ setLatency()

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

Definition at line 276 of file Problems.h.

References latency.

◆ setLibraryName()

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

Definition at line 307 of file Problems.h.

References libraryName, and name.

◆ setLinkedOperatorType()

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

Definition at line 259 of file Problems.h.

References linkedOperatorType.

◆ setLinkedResourceTypes()

void circt::scheduling::Problem::setLinkedResourceTypes ( Operation *  op,
SmallVector< ResourceType rsrc 
)
inline

Definition at line 268 of file Problems.h.

References linkedResourceTypes.

◆ setOperationName()

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

Definition at line 315 of file Problems.h.

References name, and operationNames.

◆ setRsrcLibraryName()

void circt::scheduling::Problem::setRsrcLibraryName ( StringAttr  name)
inline

Definition at line 310 of file Problems.h.

References name, and rsrcLibraryName.

◆ setStartTime()

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

◆ verify()

LogicalResult Problem::verify ( )
virtual

◆ 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 129 of file Problems.cpp.

References getContainingOp(), circt::scheduling::detail::Dependence::getDestination(), getLatency(), getLinkedOperatorType(), circt::scheduling::detail::Dependence::getSource(), and getStartTime().

Referenced by verify().

◆ verifyStartTime()

LogicalResult Problem::verifyStartTime ( Operation *  op)
protectedvirtual

op has a start time.

Definition at line 123 of file Problems.cpp.

References getStartTime().

Referenced by verify().

Member Data Documentation

◆ auxDependences

AuxDependenceMap circt::scheduling::Problem::auxDependences
private

◆ containingOp

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

◆ instanceName

StringAttr circt::scheduling::Problem::instanceName
private

Definition at line 299 of file Problems.h.

Referenced by getInstanceName(), and setInstanceName().

◆ latency

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

Definition at line 186 of file Problems.h.

Referenced by getEndTime(), getLatency(), getProperties(), and setLatency().

◆ libraryName

StringAttr circt::scheduling::Problem::libraryName
private

Definition at line 299 of file Problems.h.

Referenced by getLibraryName(), and setLibraryName().

◆ linkedOperatorType

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

Definition at line 181 of file Problems.h.

Referenced by getLinkedOperatorType(), and setLinkedOperatorType().

◆ linkedResourceTypes

OperationProperty<SmallVector<ResourceType> > circt::scheduling::Problem::linkedResourceTypes
private

Definition at line 182 of file Problems.h.

Referenced by getLinkedResourceTypes(), and setLinkedResourceTypes().

◆ name

constexpr auto circt::scheduling::Problem::name = "Problem"
staticconstexpr

◆ operationNames

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

Definition at line 300 of file Problems.h.

Referenced by getOperationName(), and setOperationName().

◆ operations

OperationSet circt::scheduling::Problem::operations
private

Definition at line 175 of file Problems.h.

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

◆ operatorTypes

OperatorTypeSet circt::scheduling::Problem::operatorTypes
private

◆ resourceTypes

ResourceTypeSet circt::scheduling::Problem::resourceTypes
private

◆ rsrcLibraryName

StringAttr circt::scheduling::Problem::rsrcLibraryName
private

Definition at line 299 of file Problems.h.

Referenced by getRsrcLibraryName(), and setRsrcLibraryName().

◆ startTime

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

Definition at line 183 of file Problems.h.

Referenced by getEndTime(), getProperties(), getStartTime(), and setStartTime().


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