CIRCT 21.0.0git
|
This class models the most basic scheduling problem. More...
#include <Problems.h>
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 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 (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< OperatorType > | linkedOperatorType |
OperationProperty< SmallVector< ResourceType > > | linkedResourceTypes |
OperationProperty< unsigned > | startTime |
OperatorTypeProperty< unsigned > | latency |
StringAttr | instanceName |
StringAttr | libraryName |
StringAttr | rsrcLibraryName |
SmallDenseMap< Operation *, StringAttr > | operationNames |
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
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 75 of file Problems.h.
|
protected |
Definition at line 152 of file Problems.h.
A thin wrapper to allow a uniform handling of def-use and auxiliary dependences.
Definition at line 95 of file Problems.h.
|
protected |
Definition at line 158 of file Problems.h.
using circt::scheduling::Problem::DependenceRange = llvm::iterator_range<detail::DependenceIterator> |
Definition at line 147 of file Problems.h.
|
protected |
Definition at line 164 of file Problems.h.
|
protected |
Definition at line 156 of file Problems.h.
using circt::scheduling::Problem::OperationSet = llvm::SetVector<Operation *> |
Definition at line 146 of file Problems.h.
|
protected |
Definition at line 160 of file Problems.h.
using circt::scheduling::Problem::OperatorTypeSet = llvm::SetVector<OperatorType> |
Definition at line 148 of file Problems.h.
using circt::scheduling::Problem::PropertyStringVector = llvm::SmallVector<std::pair<std::string, std::string>, 2> |
Definition at line 323 of file Problems.h.
|
protected |
Definition at line 162 of file Problems.h.
using circt::scheduling::Problem::ResourceTypeSet = llvm::SetVector<ResourceType> |
Definition at line 149 of file Problems.h.
|
inlineexplicit |
Construct an empty scheduling problem.
containingOp
is used for its MLIRContext and to emit diagnostics.
Definition at line 81 of file Problems.h.
|
virtualdefault |
|
protecteddefault |
|
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().
|
protectedvirtual |
op
has a latency.
Reimplemented in circt::scheduling::SharedOperatorsProblem.
Definition at line 98 of file Problems.cpp.
References getContainingOp(), getLatency(), and getLinkedOperatorType().
Referenced by check(), and circt::scheduling::SharedOperatorsProblem::checkLatency().
|
protectedvirtual |
op
is linked to a registered operator type.
Definition at line 90 of file Problems.cpp.
References getLinkedOperatorType(), and hasOperatorType().
Referenced by check().
|
inline |
Return the operation containing this problem, e.g. to emit diagnostics.
Definition at line 219 of file Problems.h.
References containingOp.
Referenced by circt::scheduling::ChainingCyclicProblem::checkDefUse(), circt::scheduling::ChainingProblem::checkDelays(), checkLatency(), circt::scheduling::SharedOperatorsProblem::checkLatency(), circt::scheduling::handleOperationsInTopologicalOrder(), circt::scheduling::scheduleCPSAT(), circt::scheduling::scheduleLP(), circt::scheduling::scheduleLP(), circt::scheduling::CyclicProblem::verifyInitiationInterval(), verifyPrecedence(), circt::scheduling::CyclicProblem::verifyPrecedence(), circt::scheduling::ChainingProblem::verifyPrecedenceInCycle(), circt::scheduling::SharedOperatorsProblem::verifyUtilization(), and circt::scheduling::ModuloProblem::verifyUtilization().
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().
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.
|
inline |
Definition at line 303 of file Problems.h.
References instanceName.
|
inline |
The latency is the number of cycles opr
needs to compute its result.
Definition at line 273 of file Problems.h.
References latency.
Referenced by circt::scheduling::ChainingProblem::checkDelays(), checkLatency(), circt::scheduling::SharedOperatorsProblem::checkLatency(), circt::scheduling::computeStartTimesInCycle(), getEndTime(), getProperties(), circt::scheduling::scheduleASAP(), circt::scheduling::scheduleCPSAT(), circt::scheduling::scheduleLP(), circt::scheduling::scheduleLP(), verifyPrecedence(), circt::scheduling::CyclicProblem::verifyPrecedence(), and circt::scheduling::ChainingProblem::verifyPrecedenceInCycle().
|
inline |
Definition at line 306 of file Problems.h.
References libraryName.
|
inline |
The linked operator type provides the runtime characteristics for op
.
Definition at line 256 of file Problems.h.
References linkedOperatorType.
Referenced by checkLatency(), circt::scheduling::SharedOperatorsProblem::checkLatency(), checkLinkedOperatorType(), circt::scheduling::computeStartTimesInCycle(), getEndTime(), getProperties(), circt::scheduling::scheduleASAP(), circt::scheduling::scheduleCPSAT(), circt::scheduling::scheduleLP(), circt::scheduling::scheduleLP(), verifyPrecedence(), circt::scheduling::CyclicProblem::verifyPrecedence(), and circt::scheduling::ChainingProblem::verifyPrecedenceInCycle().
|
inline |
The linked resource type provides the available resources for op
.
Definition at line 265 of file Problems.h.
References linkedResourceTypes.
Referenced by circt::scheduling::SharedOperatorsProblem::checkLatency(), isLimited(), circt::scheduling::scheduleCPSAT(), circt::scheduling::SharedOperatorsProblem::verifyUtilization(), and circt::scheduling::ModuloProblem::verifyUtilization().
|
inline |
Definition at line 312 of file Problems.h.
References operationNames.
|
inline |
Return the set of operations.
Definition at line 226 of file Problems.h.
References operations.
Referenced by check(), circt::scheduling::ChainingCyclicProblem::check(), circt::scheduling::dumpAsDOT(), circt::scheduling::handleOperationsInTopologicalOrder(), circt::scheduling::scheduleCPSAT(), circt::scheduling::scheduleLP(), circt::scheduling::scheduleLP(), verify(), circt::scheduling::ChainingProblem::verify(), circt::scheduling::SharedOperatorsProblem::verifyUtilization(), and circt::scheduling::ModuloProblem::verifyUtilization().
|
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().
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.
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.
|
virtual |
Reimplemented in circt::scheduling::CyclicProblem.
Definition at line 84 of file Problems.cpp.
Referenced by circt::scheduling::CyclicProblem::getProperties(), circt::scheduling::CyclicProblem::getProperties(), circt::scheduling::ChainingProblem::getProperties(), circt::scheduling::ChainingProblem::getProperties(), and circt::scheduling::SharedOperatorsProblem::getProperties().
|
virtual |
Reimplemented in circt::scheduling::CyclicProblem.
Definition at line 73 of file Problems.cpp.
|
virtual |
Reimplemented in circt::scheduling::ChainingProblem.
Definition at line 64 of file Problems.cpp.
References getLinkedOperatorType(), getStartTime(), and startTime.
Referenced by circt::scheduling::dumpAsDOT().
|
virtual |
Reimplemented in circt::scheduling::ChainingProblem.
Definition at line 77 of file Problems.cpp.
References getLatency(), and latency.
|
virtual |
Reimplemented in circt::scheduling::SharedOperatorsProblem.
Definition at line 86 of file Problems.cpp.
|
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().
|
inline |
Definition at line 309 of file Problems.h.
References rsrcLibraryName.
|
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 281 of file Problems.h.
References startTime.
Referenced by circt::scheduling::computeStartTimesInCycle(), getEndTime(), getProperties(), circt::scheduling::scheduleASAP(), verifyPrecedence(), circt::scheduling::CyclicProblem::verifyPrecedence(), circt::scheduling::ChainingProblem::verifyPrecedenceInCycle(), verifyStartTime(), circt::scheduling::SharedOperatorsProblem::verifyUtilization(), and circt::scheduling::ModuloProblem::verifyUtilization().
|
inline |
Return true if op
is part of this problem.
Definition at line 224 of file Problems.h.
References operations.
Referenced by circt::scheduling::detail::DependenceIterator::findNextDependence(), circt::scheduling::scheduleCPSAT(), circt::scheduling::scheduleLP(), and circt::scheduling::scheduleLP().
|
inline |
Return true if opr
is part of this problem.
Definition at line 241 of file Problems.h.
References operatorTypes.
Referenced by checkLinkedOperatorType().
|
inline |
Return true if rsrc
is part of this problem.
Definition at line 246 of file Problems.h.
References resourceTypes.
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().
|
inline |
Include op
in this scheduling problem.
Definition at line 193 of file Problems.h.
References operations.
Referenced by circt::analysis::CyclicSchedulingAnalysis::analyzeForOp().
|
inline |
Include opr
in this scheduling problem.
Definition at line 201 of file Problems.h.
References operatorTypes.
|
inline |
Include rsrc
in this scheduling problem.
Definition at line 204 of file Problems.h.
References resourceTypes.
|
inline |
Set the operation containing this problem, e.g. to emit diagnostics.
Definition at line 221 of file Problems.h.
References containingOp.
|
inline |
Definition at line 304 of file Problems.h.
References instanceName, and name.
|
inline |
Definition at line 276 of file Problems.h.
References latency.
|
inline |
Definition at line 307 of file Problems.h.
References libraryName, and name.
|
inline |
Definition at line 259 of file Problems.h.
References linkedOperatorType.
|
inline |
Definition at line 268 of file Problems.h.
References linkedResourceTypes.
|
inline |
Definition at line 315 of file Problems.h.
References name, and operationNames.
|
inline |
Definition at line 310 of file Problems.h.
References name, and rsrcLibraryName.
|
inline |
Definition at line 284 of file Problems.h.
References startTime.
Referenced by circt::scheduling::scheduleASAP(), circt::scheduling::scheduleCPSAT(), circt::scheduling::scheduleLP(), and circt::scheduling::scheduleLP().
|
virtual |
Return success if the computed solution is valid.
Reimplemented in circt::scheduling::CyclicProblem, circt::scheduling::ChainingProblem, circt::scheduling::SharedOperatorsProblem, circt::scheduling::ModuloProblem, and circt::scheduling::ChainingCyclicProblem.
Definition at line 147 of file Problems.cpp.
References getDependences(), getOperations(), verifyPrecedence(), and verifyStartTime().
Referenced by circt::scheduling::CyclicProblem::verify(), circt::scheduling::ChainingProblem::verify(), and circt::scheduling::SharedOperatorsProblem::verify().
|
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().
|
protectedvirtual |
op
has a start time.
Definition at line 123 of file Problems.cpp.
References getStartTime().
Referenced by verify().
|
private |
Definition at line 176 of file Problems.h.
Referenced by circt::scheduling::detail::DependenceIterator::DependenceIterator(), and insertDependence().
|
private |
Definition at line 172 of file Problems.h.
Referenced by getContainingOp(), getOrInsertOperatorType(), getOrInsertResourceType(), and setContainingOp().
|
private |
Definition at line 299 of file Problems.h.
Referenced by getInstanceName(), and setInstanceName().
|
private |
Definition at line 186 of file Problems.h.
Referenced by getEndTime(), getLatency(), getProperties(), and setLatency().
|
private |
Definition at line 299 of file Problems.h.
Referenced by getLibraryName(), and setLibraryName().
|
private |
Definition at line 181 of file Problems.h.
Referenced by getLinkedOperatorType(), and setLinkedOperatorType().
|
private |
Definition at line 182 of file Problems.h.
Referenced by getLinkedResourceTypes(), and setLinkedResourceTypes().
|
staticconstexpr |
Definition at line 77 of file Problems.h.
Referenced by circt::scheduling::Problem::OperatorType::get(), circt::scheduling::Problem::ResourceType::get(), getOrInsertOperatorType(), getOrInsertResourceType(), setInstanceName(), setLibraryName(), setOperationName(), and setRsrcLibraryName().
|
private |
Definition at line 300 of file Problems.h.
Referenced by getOperationName(), and setOperationName().
|
private |
Definition at line 175 of file Problems.h.
Referenced by getOperations(), hasOperation(), insertDependence(), and insertOperation().
|
private |
Definition at line 177 of file Problems.h.
Referenced by getOperatorTypes(), getOrInsertOperatorType(), hasOperatorType(), and insertOperatorType().
|
private |
Definition at line 178 of file Problems.h.
Referenced by getOrInsertResourceType(), getResourceTypes(), hasResourceType(), and insertResourceType().
|
private |
Definition at line 299 of file Problems.h.
Referenced by getRsrcLibraryName(), and setRsrcLibraryName().
|
private |
Definition at line 183 of file Problems.h.
Referenced by getEndTime(), getProperties(), getStartTime(), and setStartTime().