17 #ifndef CIRCT_SCHEDULING_PROBLEMS_H
18 #define CIRCT_SCHEDULING_PROBLEMS_H
23 #include "mlir/IR/BuiltinAttributes.h"
24 #include "llvm/ADT/DenseMap.h"
25 #include "llvm/ADT/SetVector.h"
29 #define DEFINE_COMMON_MEMBERS(ProblemClass) \
34 static constexpr auto PROBLEM_NAME = #ProblemClass; \
35 static ProblemClass get(Operation *containingOp) { \
37 prob.setContainingOp(containingOp); \
42 namespace scheduling {
116 llvm::DenseMap<Operation *, llvm::SmallSetVector<Operation *, 4>>;
118 template <
typename T>
120 template <
typename T>
122 template <
typename T>
124 template <
typename T>
230 std::optional<unsigned>
getEndTime(Operation *op);
258 llvm::SmallVector<std::pair<std::string, std::string>, 2>;
284 virtual LogicalResult
check();
286 virtual LogicalResult
verify();
326 virtual LogicalResult
verify()
override;
393 virtual LogicalResult
check()
override;
394 virtual LogicalResult
verify()
override;
418 return limit.lookup(opr);
431 virtual LogicalResult
verify()
override;
454 virtual LogicalResult
verify()
override;
460 #undef DEFINE_COMMON_MEMBERS
Problem::Dependence Dependence
#define DEFINE_COMMON_MEMBERS(ProblemClass)
This class models the accumulation of physical propagation delays on combinational paths along SSA de...
void setStartTimeInCycle(Operation *op, float time)
void setIncomingDelay(OperatorType opr, float delay)
OperationProperty< float > startTimeInCycle
virtual LogicalResult check() override
Return success if the constructed scheduling problem is valid.
virtual LogicalResult verifyPrecedenceInCycle(Dependence dep)
If dep is an SSA edge and its source operation finishes in the same time step as the destination oper...
std::optional< float > getStartTimeInCycle(Operation *op)
Computed by the scheduler, this start time is relative to the beginning of the cycle that op starts i...
std::optional< float > getIncomingDelay(OperatorType opr)
The incoming delay denotes the propagation time from the operand inputs to either the result outputs ...
std::optional< float > getOutgoingDelay(OperatorType opr)
The outgoing delay denotes the propagation time from either the operand inputs (combinational operato...
OperatorTypeProperty< float > incomingDelay
void setOutgoingDelay(OperatorType opr, float delay)
virtual LogicalResult verify() override
Return success if the computed solution is valid.
OperatorTypeProperty< float > outgoingDelay
virtual LogicalResult verifyStartTimeInCycle(Operation *op)
op has a non-negative start time in its cycle.
virtual LogicalResult checkDelays(OperatorType opr)
Incoming/outgoing delays are set for opr and non-negative.
This class models a cyclic scheduling problem.
std::optional< unsigned > getInitiationInterval()
The initiation interval (II) is the number of time steps between subsequent iterations,...
void setDistance(Dependence dep, unsigned val)
virtual LogicalResult verifyInitiationInterval()
This problem has a non-zero II.
virtual PropertyStringVector getProperties() override
virtual LogicalResult verifyPrecedence(Dependence dep) override
dep's source operation is available before dep's destination operation starts (dep's distance iterati...
void setInitiationInterval(unsigned val)
InstanceProperty< unsigned > initiationInterval
virtual LogicalResult verify() override
Return success if the computed solution is valid.
DependenceProperty< unsigned > distance
std::optional< unsigned > getDistance(Dependence dep)
The distance determines whether a dependence has to be satisfied in the same iteration (distance=0 or...
This class models the modulo scheduling problem as the composition of the cyclic problem and the reso...
virtual LogicalResult verify() override
Return success if the computed solution is valid.
virtual LogicalResult verifyUtilization(OperatorType opr) override
opr is not oversubscribed in any congruence class modulo II.
This class models the most basic scheduling problem.
void setLatency(OperatorType opr, unsigned val)
virtual LogicalResult checkLatency(OperatorType opr)
opr has a latency.
llvm::DenseMap< Operation *, llvm::SmallSetVector< Operation *, 4 > > AuxDependenceMap
llvm::SetVector< Operation * > OperationSet
llvm::SetVector< OperatorType > OperatorTypeSet
virtual LogicalResult verify()
Return success if the computed solution is valid.
StringAttr getInstanceName()
virtual LogicalResult check()
Return success if the constructed scheduling problem is valid.
std::optional< OperatorType > getLinkedOperatorType(Operation *op)
The linked operator type provides the runtime characteristics for op.
virtual PropertyStringVector getProperties()
void insertOperation(Operation *op)
Include op in this scheduling problem.
llvm::iterator_range< detail::DependenceIterator > DependenceRange
bool hasOperation(Operation *op)
Return true if op is part of this problem.
StringAttr getLibraryName()
LogicalResult insertDependence(Dependence dep)
Include dep in the scheduling problem.
std::optional< unsigned > getEndTime(Operation *op)
Returns the end time for op, as computed by the scheduler.
const OperatorTypeSet & getOperatorTypes()
Return the set of operator types.
OperationProperty< OperatorType > linkedOperatorType
OperationProperty< unsigned > startTime
std::optional< T > InstanceProperty
std::optional< unsigned > getStartTime(Operation *op)
Return the start time for op, as computed by the scheduler.
void setStartTime(Operation *op, unsigned val)
OperatorTypeProperty< unsigned > latency
SmallDenseMap< Operation *, StringAttr > operationNames
llvm::DenseMap< Operation *, std::optional< T > > OperationProperty
virtual ~Problem()=default
void setContainingOp(Operation *op)
Set the operation containing this problem, e.g. to emit diagnostics.
OperatorType getOrInsertOperatorType(StringRef name)
Retrieves the operator type identified by the client-specific name.
AuxDependenceMap auxDependences
llvm::DenseMap< OperatorType, std::optional< T > > OperatorTypeProperty
void setInstanceName(StringAttr name)
OperatorTypeSet operatorTypes
llvm::SmallVector< std::pair< std::string, std::string >, 2 > PropertyStringVector
virtual LogicalResult verifyStartTime(Operation *op)
op has a start time.
virtual LogicalResult checkLinkedOperatorType(Operation *op)
op is linked to a registered operator type.
llvm::DenseMap< Dependence, std::optional< T > > DependenceProperty
DependenceRange getDependences(Operation *op)
Return a range object to transparently iterate over op's incoming 1) implicit def-use dependences (ba...
bool hasOperatorType(OperatorType opr)
Return true if opr is part of this problem.
const OperationSet & getOperations()
Return the set of operations.
virtual LogicalResult verifyPrecedence(Dependence dep)
dep's source operation is available before dep's destination operation starts.
void setLibraryName(StringAttr name)
void setLinkedOperatorType(Operation *op, OperatorType opr)
mlir::StringAttr OperatorType
Operator types are distinguished by name (chosen by the client).
void insertOperatorType(OperatorType opr)
Include opr in this scheduling problem.
void setOperationName(Operation *op, StringAttr name)
StringAttr getOperationName(Operation *op)
std::optional< unsigned > getLatency(OperatorType opr)
The latency is the number of cycles opr needs to compute its result.
Operation * getContainingOp()
Return the operation containing this problem, e.g. to emit diagnostics.
This class models a resource-constrained scheduling problem.
OperatorTypeProperty< unsigned > limit
virtual LogicalResult verify() override
Return success if the computed solution is valid.
virtual LogicalResult checkLatency(OperatorType opr) override
If opr is limited, it has a non-zero latency.
std::optional< unsigned > getLimit(OperatorType opr)
The limit is the maximum number of operations using opr that are allowed to start in the same time st...
virtual LogicalResult verifyUtilization(OperatorType opr)
opr is not oversubscribed in any time step.
void setLimit(OperatorType opr, unsigned val)
An iterator to transparently surface an operation's def-use dependences from the SSA subgraph (induce...
A wrapper class to uniformly handle def-use and auxiliary dependence edges.
This file defines an intermediate representation for circuits acting as an abstraction for constraint...