16#include "mlir/IR/Operation.h"
67 psv.emplace_back(
"linkedOpr", (*linkedOpr).str());
69 psv.emplace_back(
"startTime", std::to_string(*
startTime));
80 psv.emplace_back(
"latency", std::to_string(*
latency));
92 return op->emitError(
"Operation is not linked to an operator type");
94 return op->emitError(
"Operation uses an unregistered operator type");
102 <<
"Operation is missing a linked operator type";
106 <<
"Operator type '" << maybeOpr->getValue() <<
"' has no latency";
125 return op->emitError(
"Operation has no start time");
138 if (!(stI + latI <= stJ))
140 <<
"Precedence violated for dependence."
141 <<
"\n from: " << *i <<
", result available in t=" << (stI + latI)
142 <<
"\n to: " << *j <<
", starts in t=" << stJ;
175 psv.emplace_back(
"distance", std::to_string(*
distance));
182 psv.emplace_back(
"II", std::to_string(*ii));
197 if (!(stI + latI <= stJ + dist * ii))
199 <<
"Precedence violated for dependence."
200 <<
"\n from: " << *i <<
", result available in t=" << (stI + latI)
201 <<
"\n to: " << *j <<
", starts in t=" << stJ
202 <<
"\n dist: " << dist <<
", II=" << ii;
226 psv.emplace_back(
"start time in cycle", std::to_string(*stic));
233 psv.emplace_back(
"incoming delay", std::to_string(*incDelay));
235 psv.emplace_back(
"outgoing delay", std::to_string(*outDelay));
245 <<
"Missing delays for operator type '" << opr.
getAttr() <<
"'";
250 if (iDel < 0.0f || oDel < 0.0f)
252 <<
"Negative delays for operator type '" << opr.
getAttr() <<
"'";
256 <<
"Incoming & outgoing delay must be equal for zero-latency "
266 return op->emitError(
"Operation has no non-negative start time in cycle");
284 if (stI + latI < stJ)
296 if (!(sticI + oDelI <= sticJ))
298 <<
"Precedence violated in cycle " << stJ <<
" for dependence:"
299 <<
"\n from: " << *i <<
", result after z=" << (sticI + oDelI)
300 <<
"\n to: " << *j <<
", starts in z=" << sticJ;
340 psv.emplace_back(
"limit", std::to_string(*
limit));
356 for (
auto rsrc : *maybeRsrcs) {
360 <<
"Operator type '" << linkedOprType.
getValue()
361 <<
"' using limited resource '" << rsrc.getValue()
362 <<
"' has zero latency.";
378 if (llvm::none_of(*maybeRsrcs, [&](
ResourceType linkedRsrc) {
379 return linkedRsrc == rsrc;
386 for (
auto &kv : nOpsPerTimeStep)
387 if (kv.second > *
limit)
389 <<
"Resource type '" << rsrc.
getValue() <<
"' is oversubscribed."
390 <<
"\n time step: " << kv.first
391 <<
"\n #operations: " << kv.second <<
"\n limit: " << *
limit;
423 if (llvm::none_of(*maybeRsrcs, [&](
ResourceType linkedRsrc) {
424 return linkedRsrc == rsrc;
431 for (
auto &kv : nOpsPerCongruenceClass)
432 if (kv.second > *
limit)
434 <<
"Resource type '" << rsrc.
getValue() <<
"' is oversubscribed."
435 <<
"\n congruence class: " << kv.first
436 <<
"\n #operations: " << kv.second <<
"\n limit: " << *
limit;
461 <<
"Def-use dependence cannot have non-zero distance.\n"
490 return isDefUse() ? defUse->get().getDefiningOp() : auxSrc;
494 return isDefUse() ? defUse->getOwner() : auxDst;
501 assert(isa<OpResult>(defUse->get()) &&
"source is not an operation");
502 return dyn_cast<OpResult>(defUse->get()).getResultNumber();
508 return defUse->getOperandNumber();
512 return TupleRepr(getSource(), getDestination(), getSourceIndex(),
513 getDestinationIndex());
526 : problem(problem), op(op), operandIdx(0), auxPredIdx(0), auxPreds(nullptr),
538 while (operandIdx < op->getNumOperands()) {
549 if (
auxPreds && auxPredIdx < auxPreds->size()) {
assert(baseType &&"element must be base type")
LogicalResult verify() override
Return success if the computed solution is valid.
LogicalResult checkDefUse(Dependence dep)
LogicalResult check() override
Return success if the constructed scheduling problem is valid.
std::optional< float > getOutgoingDelay(OperatorType opr)
The outgoing delay denotes the propagation time from either the operand inputs (combinational operato...
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 > getIncomingDelay(OperatorType opr)
The incoming delay denotes the propagation time from the operand inputs to either the result outputs ...
OperatorTypeProperty< float > incomingDelay
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.
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...
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...
std::optional< unsigned > getDistance(Dependence dep)
The distance determines whether a dependence has to be satisfied in the same iteration (distance=0 or...
virtual LogicalResult verify() override
Return success if the computed solution is valid.
DependenceProperty< unsigned > distance
std::optional< unsigned > getInitiationInterval()
The initiation interval (II) is the number of time steps between subsequent iterations,...
virtual LogicalResult verify() override
Return success if the computed solution is valid.
virtual LogicalResult verifyUtilization(ResourceType rsrc) override
opr is not oversubscribed in any congruence class modulo II.
This class models the most basic scheduling problem.
virtual LogicalResult verify()
Return success if the computed solution is valid.
virtual LogicalResult check()
Return success if the constructed scheduling problem is valid.
std::optional< unsigned > getLatency(OperatorType opr)
The latency is the number of cycles opr needs to compute its result.
virtual PropertyStringVector getProperties()
llvm::iterator_range< detail::DependenceIterator > DependenceRange
bool hasOperation(Operation *op)
Return true if op is part of this problem.
std::optional< SmallVector< ResourceType > > getLinkedResourceTypes(Operation *op)
The linked resource type provides the available resources for op.
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.
OperationProperty< unsigned > startTime
std::optional< OperatorType > getLinkedOperatorType(Operation *op)
The linked operator type provides the runtime characteristics for op.
ResourceTypeSet resourceTypes
OperatorTypeProperty< unsigned > latency
const ResourceTypeSet & getResourceTypes()
Return the set of resource types.
static constexpr auto name
const OperationSet & getOperations()
Return the set of operations.
OperatorType getOrInsertOperatorType(StringRef name)
Retrieves the operator type identified by the client-specific name.
AuxDependenceMap auxDependences
std::optional< unsigned > getStartTime(Operation *op)
Return the start time for op, as computed by the scheduler.
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.
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.
virtual LogicalResult verifyPrecedence(Dependence dep)
dep's source operation is available before dep's destination operation starts.
Operation * getContainingOp()
Return the operation containing this problem, e.g. to emit diagnostics.
ResourceType getOrInsertResourceType(StringRef name)
Retrieves the resource type identified by the client-specific name.
virtual LogicalResult checkLatency(Operation *op)
op has a latency.
const OperatorTypeSet & getOperatorTypes()
Return the set of operator types.
virtual LogicalResult verifyUtilization(ResourceType rsrc)
rsrc is not oversubscribed in any time step.
virtual LogicalResult verify() override
Return success if the computed solution is valid.
virtual LogicalResult checkLatency(Operation *op) override
If op is limited, it has a non-zero latency.
ResourceTypeProperty< unsigned > limit
std::optional< unsigned > getLimit(ResourceType rsrc)
The limit is the maximum number of operations using rsrc that are available in the target hardware.
An iterator to transparently surface an operation's def-use dependences from the SSA subgraph (induce...
void findNextDependence()
llvm::SmallSetVector< Operation *, 4 > * auxPreds
DependenceIterator(Problem &problem, Operation *op, bool end=false)
Construct an iterator over the op's def-use dependences (i.e.
A wrapper class to uniformly handle def-use and auxiliary dependence edges.
std::tuple< Operation *, Operation *, std::optional< unsigned >, std::optional< unsigned > > TupleRepr
The "expanded" representation of a dependence, intended as the key for comparisons and hashing.
bool operator==(const Dependence &other) const
std::optional< unsigned > getDestinationIndex() const
Return the destination operation's operand number, if applicable.
std::optional< unsigned > getSourceIndex() const
Return the source operation's result number, if applicable.
Operation * getDestination() const
Return the destination of the dependence.
bool isAuxiliary() const
Return true if this is a valid auxiliary dependence.
TupleRepr getAsTuple() const
Return the tuple representation of this dependence.
Operation * getSource() const
Return the source of the dependence.
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
Operator types are distinguished by name (chosen by the client).
mlir::StringAttr getAttr() const
static OperatorType get(mlir::MLIRContext *ctx, llvm::StringRef name)
mlir::StringRef getValue() const
Resource types are distinguished by name (chosen by the client).
mlir::StringRef getValue() const
static ResourceType get(mlir::MLIRContext *ctx, llvm::StringRef name)