16 #include "mlir/IR/Operation.h"
18 using namespace circt;
38 auxDependences[dst].insert(src);
41 operations.insert(src);
42 operations.insert(dst);
49 operatorTypes.insert(opr);
60 if (
auto linkedOpr = getLinkedOperatorType(op))
61 psv.emplace_back(
"linkedOpr", (*linkedOpr).str());
62 if (
auto startTime = getStartTime(op))
63 psv.emplace_back(
"startTime", std::to_string(*startTime));
73 if (
auto latency = getLatency(opr))
74 psv.emplace_back(
"latency", std::to_string(*latency));
81 if (!getLinkedOperatorType(op))
82 return op->emitError(
"Operation is not linked to an operator type");
83 if (!hasOperatorType(*getLinkedOperatorType(op)))
84 return op->emitError(
"Operation uses an unregistered operator type");
90 return getContainingOp()->emitError()
91 <<
"Operator type '" << opr.getValue() <<
"' has no latency";
97 for (
auto *op : getOperations())
98 if (failed(checkLinkedOperatorType(op)))
101 for (
auto opr : getOperatorTypes())
102 if (failed(checkLatency(opr)))
109 if (!getStartTime(op))
110 return op->emitError(
"Operation has no start time");
118 unsigned stI = *getStartTime(i);
119 unsigned latI = *getLatency(*getLinkedOperatorType(i));
120 unsigned stJ = *getStartTime(j);
123 if (!(stI + latI <= stJ))
124 return getContainingOp()->emitError()
125 <<
"Precedence violated for dependence."
126 <<
"\n from: " << *i <<
", result available in t=" << (stI + latI)
127 <<
"\n to: " << *j <<
", starts in t=" << stJ;
133 for (
auto *op : getOperations())
134 if (failed(verifyStartTime(op)))
137 for (
auto *op : getOperations())
138 for (
auto &dep : getDependences(op))
139 if (failed(verifyPrecedence(dep)))
146 if (
auto startTime = getStartTime(op))
147 if (
auto opType = getLinkedOperatorType(op))
148 if (
auto latency = getLatency(*opType))
149 return startTime.value() + latency.value();
159 if (
auto distance = getDistance(dep))
160 psv.emplace_back(
"distance", std::to_string(*distance));
166 if (
auto ii = getInitiationInterval())
167 psv.emplace_back(
"II", std::to_string(*ii));
175 unsigned stI = *getStartTime(i);
176 unsigned latI = *getLatency(*getLinkedOperatorType(i));
177 unsigned stJ = *getStartTime(j);
178 unsigned dist = getDistance(dep).value_or(0);
179 unsigned ii = *getInitiationInterval();
182 if (!(stI + latI <= stJ + dist * ii))
183 return getContainingOp()->emitError()
184 <<
"Precedence violated for dependence."
185 <<
"\n from: " << *i <<
", result available in t=" << (stI + latI)
186 <<
"\n to: " << *j <<
", starts in t=" << stJ
187 <<
"\n dist: " << dist <<
", II=" << ii;
193 if (!getInitiationInterval() || *getInitiationInterval() == 0)
194 return getContainingOp()->emitError(
"Invalid initiation interval");
210 if (
auto stic = getStartTimeInCycle(op))
211 psv.emplace_back(
"start time in cycle", std::to_string(*stic));
217 if (
auto incDelay = getIncomingDelay(opr))
218 psv.emplace_back(
"incoming delay", std::to_string(*incDelay));
219 if (
auto outDelay = getOutgoingDelay(opr))
220 psv.emplace_back(
"outgoing delay", std::to_string(*outDelay));
225 auto incomingDelay = getIncomingDelay(opr);
226 auto outgoingDelay = getOutgoingDelay(opr);
228 if (!incomingDelay || !outgoingDelay)
229 return getContainingOp()->emitError()
230 <<
"Missing delays for operator type '" << opr <<
"'";
232 float iDel = *incomingDelay;
233 float oDel = *outgoingDelay;
235 if (iDel < 0.0f || oDel < 0.0f)
236 return getContainingOp()->emitError()
237 <<
"Negative delays for operator type '" << opr <<
"'";
239 if (*getLatency(opr) == 0 && iDel != oDel)
240 return getContainingOp()->emitError()
241 <<
"Incoming & outgoing delay must be equal for zero-latency "
249 auto startTimeInCycle = getStartTimeInCycle(op);
250 if (!startTimeInCycle || *startTimeInCycle < 0.0f)
251 return op->emitError(
"Operation has no non-negative start time in cycle");
263 unsigned stI = *getStartTime(i);
264 unsigned latI = *getLatency(*getLinkedOperatorType(i));
265 unsigned stJ = *getStartTime(j);
269 if (stI + latI < stJ)
277 float sticI = latI == 0 ? *getStartTimeInCycle(i) : 0.0f;
278 float oDelI = *getOutgoingDelay(*getLinkedOperatorType(i));
279 float sticJ = *getStartTimeInCycle(j);
281 if (!(sticI + oDelI <= sticJ))
282 return getContainingOp()->emitError()
283 <<
"Precedence violated in cycle " << stJ <<
" for dependence:"
284 <<
"\n from: " << *i <<
", result after z=" << (sticI + oDelI)
285 <<
"\n to: " << *j <<
", starts in z=" << sticJ;
294 for (
auto opr : getOperatorTypes())
295 if (failed(checkDelays(opr)))
305 for (
auto *op : getOperations())
306 if (failed(verifyStartTimeInCycle(op)))
309 for (
auto *op : getOperations())
310 for (
auto dep : getDependences(op))
311 if (failed(verifyPrecedenceInCycle(dep)))
324 if (
auto limit = getLimit(opr))
325 psv.emplace_back(
"limit", std::to_string(*limit));
333 auto limit = getLimit(opr);
334 if (limit && *limit > 0 && *getLatency(opr) == 0)
335 return getContainingOp()->emitError()
336 <<
"Limited operator type '" << opr.getValue()
337 <<
"' has zero latency.";
342 auto limit = getLimit(opr);
347 for (
auto *op : getOperations())
348 if (opr == *getLinkedOperatorType(op))
349 ++nOpsPerTimeStep[*getStartTime(op)];
351 for (
auto &kv : nOpsPerTimeStep)
352 if (kv.second > *limit)
353 return getContainingOp()->emitError()
354 <<
"Operator type '" << opr.getValue() <<
"' is oversubscribed."
355 <<
"\n time step: " << kv.first
356 <<
"\n #operations: " << kv.second <<
"\n limit: " << *limit;
365 for (
auto opr : getOperatorTypes())
366 if (failed(verifyUtilization(opr)))
377 auto limit = getLimit(opr);
381 unsigned ii = *getInitiationInterval();
383 for (
auto *op : getOperations())
384 if (opr == *getLinkedOperatorType(op))
385 ++nOpsPerCongruenceClass[*getStartTime(op) % ii];
387 for (
auto &kv : nOpsPerCongruenceClass)
388 if (kv.second > *limit)
389 return getContainingOp()->emitError()
390 <<
"Operator type '" << opr.getValue() <<
"' is oversubscribed."
391 <<
"\n congruence class: " << kv.first
392 <<
"\n #operations: " << kv.second <<
"\n limit: " << *limit;
403 for (
auto opr : getOperatorTypes())
404 if (failed(verifyUtilization(opr)))
415 if (!dep.
isAuxiliary() && (getDistance(dep).value_or(0) != 0))
416 return getContainingOp()->emitError()
417 <<
"Def-use dependence cannot have non-zero distance.\n"
423 for (
auto *op : getOperations())
424 for (
auto &dep : getDependences(op))
425 if (failed(checkDefUse(dep)))
457 assert(isa<OpResult>(
defUse->get()) &&
"source is not an operation");
458 return dyn_cast<OpResult>(
defUse->get()).getResultNumber();
464 return defUse->getOperandNumber();
482 : problem(problem), op(op), operandIdx(0), auxPredIdx(0), auxPreds(nullptr),
494 while (operandIdx < op->getNumOperands()) {
505 if (
auxPreds && auxPredIdx < auxPreds->size()) {
assert(baseType &&"element must be base type")
Problem::Dependence Dependence
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.
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...
virtual LogicalResult verify() override
Return success if the computed solution is valid.
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.
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...
virtual LogicalResult verify() override
Return success if the computed solution is valid.
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.
virtual LogicalResult checkLatency(OperatorType opr)
opr has a latency.
virtual LogicalResult verify()
Return success if the computed solution is valid.
virtual LogicalResult check()
Return success if the constructed scheduling problem is valid.
virtual PropertyStringVector getProperties()
llvm::iterator_range< detail::DependenceIterator > DependenceRange
bool hasOperation(Operation *op)
Return true if op is part of this problem.
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.
OperatorType getOrInsertOperatorType(StringRef name)
Retrieves the operator type identified by the client-specific name.
AuxDependenceMap auxDependences
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...
virtual LogicalResult verifyPrecedence(Dependence dep)
dep's source operation is available before dep's destination operation starts.
mlir::StringAttr OperatorType
Operator types are distinguished by name (chosen by the client).
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.
virtual LogicalResult verifyUtilization(OperatorType opr)
opr is not oversubscribed in any time step.
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.
bool isDefUse() const
Return true if this is a valid def-use dependence.
Operation * getSource() const
Return the source of the dependence.
Direction get(bool isOutput)
Returns an output direction if isOutput is true, otherwise returns an input direction.
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.