CIRCT  20.0.0git
Problems.cpp
Go to the documentation of this file.
1 //===- Problems.cpp - Modeling of scheduling problems ---------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements base classes for scheduling problems.
10 //
11 //===----------------------------------------------------------------------===//
12 
15 
16 #include "mlir/IR/Operation.h"
17 
18 using namespace circt;
19 using namespace circt::scheduling;
20 using namespace circt::scheduling::detail;
21 
22 //===----------------------------------------------------------------------===//
23 // Problem
24 //===----------------------------------------------------------------------===//
25 
27  Operation *src = dep.getSource();
28  Operation *dst = dep.getDestination();
29 
30  // Fail early on invalid dependences (src == dst == null), and def-use
31  // dependences that cannot be added because the source value is not the result
32  // of an operation (e.g., a BlockArgument).
33  if (!src || !dst)
34  return failure();
35 
36  // record auxiliary dependences explicitly
37  if (dep.isAuxiliary())
38  auxDependences[dst].insert(src);
39 
40  // auto-register the endpoints
41  operations.insert(src);
42  operations.insert(dst);
43 
44  return success();
45 }
46 
48  auto opr = OperatorType::get(containingOp->getContext(), name);
49  operatorTypes.insert(opr);
50  return opr;
51 }
52 
54  return DependenceRange(DependenceIterator(*this, op),
55  DependenceIterator(*this, op, /*end=*/true));
56 }
57 
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));
64  return psv;
65 }
66 
68  return {};
69 }
70 
73  if (auto latency = getLatency(opr))
74  psv.emplace_back("latency", std::to_string(*latency));
75  return psv;
76 }
77 
79 
80 LogicalResult Problem::checkLinkedOperatorType(Operation *op) {
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");
85  return success();
86 }
87 
88 LogicalResult Problem::checkLatency(OperatorType opr) {
89  if (!getLatency(opr))
90  return getContainingOp()->emitError()
91  << "Operator type '" << opr.getValue() << "' has no latency";
92 
93  return success();
94 }
95 
96 LogicalResult Problem::check() {
97  for (auto *op : getOperations())
98  if (failed(checkLinkedOperatorType(op)))
99  return failure();
100 
101  for (auto opr : getOperatorTypes())
102  if (failed(checkLatency(opr)))
103  return failure();
104 
105  return success();
106 }
107 
108 LogicalResult Problem::verifyStartTime(Operation *op) {
109  if (!getStartTime(op))
110  return op->emitError("Operation has no start time");
111  return success();
112 }
113 
115  Operation *i = dep.getSource();
116  Operation *j = dep.getDestination();
117 
118  unsigned stI = *getStartTime(i);
119  unsigned latI = *getLatency(*getLinkedOperatorType(i));
120  unsigned stJ = *getStartTime(j);
121 
122  // check if i's result is available before j starts
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;
128 
129  return success();
130 }
131 
132 LogicalResult Problem::verify() {
133  for (auto *op : getOperations())
134  if (failed(verifyStartTime(op)))
135  return failure();
136 
137  for (auto *op : getOperations())
138  for (auto &dep : getDependences(op))
139  if (failed(verifyPrecedence(dep)))
140  return failure();
141 
142  return success();
143 }
144 
145 std::optional<unsigned> Problem::getEndTime(Operation *op) {
146  if (auto startTime = getStartTime(op))
147  if (auto opType = getLinkedOperatorType(op))
148  if (auto latency = getLatency(*opType))
149  return startTime.value() + latency.value();
150  return std::nullopt;
151 }
152 
153 //===----------------------------------------------------------------------===//
154 // CyclicProblem
155 //===----------------------------------------------------------------------===//
156 
158  auto psv = Problem::getProperties(dep);
159  if (auto distance = getDistance(dep))
160  psv.emplace_back("distance", std::to_string(*distance));
161  return psv;
162 }
163 
165  auto psv = Problem::getProperties();
166  if (auto ii = getInitiationInterval())
167  psv.emplace_back("II", std::to_string(*ii));
168  return psv;
169 }
170 
172  Operation *i = dep.getSource();
173  Operation *j = dep.getDestination();
174 
175  unsigned stI = *getStartTime(i);
176  unsigned latI = *getLatency(*getLinkedOperatorType(i));
177  unsigned stJ = *getStartTime(j);
178  unsigned dist = getDistance(dep).value_or(0); // optional property
179  unsigned ii = *getInitiationInterval();
180 
181  // check if i's result is available before j starts (dist iterations later)
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;
188 
189  return success();
190 }
191 
193  if (!getInitiationInterval() || *getInitiationInterval() == 0)
194  return getContainingOp()->emitError("Invalid initiation interval");
195  return success();
196 }
197 
198 LogicalResult CyclicProblem::verify() {
199  if (failed(verifyInitiationInterval()) || failed(Problem::verify()))
200  return failure();
201  return success();
202 }
203 
204 //===----------------------------------------------------------------------===//
205 // ChainingProblem
206 //===----------------------------------------------------------------------===//
207 
209  auto psv = Problem::getProperties(op);
210  if (auto stic = getStartTimeInCycle(op))
211  psv.emplace_back("start time in cycle", std::to_string(*stic));
212  return psv;
213 }
214 
216  auto psv = Problem::getProperties(opr);
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));
221  return psv;
222 }
223 
225  auto incomingDelay = getIncomingDelay(opr);
226  auto outgoingDelay = getOutgoingDelay(opr);
227 
228  if (!incomingDelay || !outgoingDelay)
229  return getContainingOp()->emitError()
230  << "Missing delays for operator type '" << opr << "'";
231 
232  float iDel = *incomingDelay;
233  float oDel = *outgoingDelay;
234 
235  if (iDel < 0.0f || oDel < 0.0f)
236  return getContainingOp()->emitError()
237  << "Negative delays for operator type '" << opr << "'";
238 
239  if (*getLatency(opr) == 0 && iDel != oDel)
240  return getContainingOp()->emitError()
241  << "Incoming & outgoing delay must be equal for zero-latency "
242  "operator type '"
243  << opr << "'";
244 
245  return success();
246 }
247 
248 LogicalResult ChainingProblem::verifyStartTimeInCycle(Operation *op) {
249  auto startTimeInCycle = getStartTimeInCycle(op);
250  if (!startTimeInCycle || *startTimeInCycle < 0.0f)
251  return op->emitError("Operation has no non-negative start time in cycle");
252  return success();
253 }
254 
256  // Auxiliary edges don't transport values.
257  if (dep.isAuxiliary())
258  return success();
259 
260  Operation *i = dep.getSource();
261  Operation *j = dep.getDestination();
262 
263  unsigned stI = *getStartTime(i);
264  unsigned latI = *getLatency(*getLinkedOperatorType(i));
265  unsigned stJ = *getStartTime(j);
266 
267  // If `i` finishes a full time step earlier than `j`, its value is registered
268  // and thereby available at physical time 0.0 in `j`'s start cycle.
269  if (stI + latI < stJ)
270  return success();
271 
272  // We have stI + latI == stJ, i.e. `i` ends in the same cycle as `j` starts.
273  // If `i` is combinational, both ops also start in the same cycle, and we must
274  // include `i`'s start time in that cycle in the path delay. Otherwise, `i`
275  // started in an earlier cycle and just contributes its outgoing delay to the
276  // path.
277  float sticI = latI == 0 ? *getStartTimeInCycle(i) : 0.0f;
278  float oDelI = *getOutgoingDelay(*getLinkedOperatorType(i));
279  float sticJ = *getStartTimeInCycle(j);
280 
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;
286 
287  return success();
288 }
289 
290 LogicalResult ChainingProblem::check() {
291  if (failed(Problem::check()))
292  return failure();
293 
294  for (auto opr : getOperatorTypes())
295  if (failed(checkDelays(opr)))
296  return failure();
297 
298  return success();
299 }
300 
301 LogicalResult ChainingProblem::verify() {
302  if (failed(Problem::verify()))
303  return failure();
304 
305  for (auto *op : getOperations())
306  if (failed(verifyStartTimeInCycle(op)))
307  return failure();
308 
309  for (auto *op : getOperations())
310  for (auto dep : getDependences(op))
311  if (failed(verifyPrecedenceInCycle(dep)))
312  return failure();
313 
314  return success();
315 }
316 
317 //===----------------------------------------------------------------------===//
318 // SharedOperatorsProblem
319 //===----------------------------------------------------------------------===//
320 
323  auto psv = Problem::getProperties(opr);
324  if (auto limit = getLimit(opr))
325  psv.emplace_back("limit", std::to_string(*limit));
326  return psv;
327 }
328 
330  if (failed(Problem::checkLatency(opr)))
331  return failure();
332 
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.";
338  return success();
339 }
340 
342  auto limit = getLimit(opr);
343  if (!limit)
344  return success();
345 
347  for (auto *op : getOperations())
348  if (opr == *getLinkedOperatorType(op))
349  ++nOpsPerTimeStep[*getStartTime(op)];
350 
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;
357 
358  return success();
359 }
360 
362  if (failed(Problem::verify()))
363  return failure();
364 
365  for (auto opr : getOperatorTypes())
366  if (failed(verifyUtilization(opr)))
367  return failure();
368 
369  return success();
370 }
371 
372 //===----------------------------------------------------------------------===//
373 // ModuloProblem
374 //===----------------------------------------------------------------------===//
375 
377  auto limit = getLimit(opr);
378  if (!limit)
379  return success();
380 
381  unsigned ii = *getInitiationInterval();
382  llvm::SmallDenseMap<unsigned, unsigned> nOpsPerCongruenceClass;
383  for (auto *op : getOperations())
384  if (opr == *getLinkedOperatorType(op))
385  ++nOpsPerCongruenceClass[*getStartTime(op) % ii];
386 
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;
393 
394  return success();
395 }
396 
397 LogicalResult ModuloProblem::verify() {
398  if (failed(CyclicProblem::verify()))
399  return failure();
400 
401  // Don't call SharedOperatorsProblem::verify() here to prevent redundant
402  // verification of the base problem.
403  for (auto opr : getOperatorTypes())
404  if (failed(verifyUtilization(opr)))
405  return failure();
406 
407  return success();
408 }
409 
410 //===----------------------------------------------------------------------===//
411 // ChainingCyclicProblem
412 //===----------------------------------------------------------------------===//
413 
415  if (!dep.isAuxiliary() && (getDistance(dep).value_or(0) != 0))
416  return getContainingOp()->emitError()
417  << "Def-use dependence cannot have non-zero distance.\n"
418  << "On operation: " << *dep.getDestination() << ".\n";
419  return success();
420 }
421 
423  for (auto *op : getOperations())
424  for (auto &dep : getDependences(op))
425  if (failed(checkDefUse(dep)))
426  return failure();
427 
428  if (ChainingProblem::check().succeeded() &&
429  CyclicProblem::check().succeeded())
430  return success();
431  return failure();
432 }
433 
435  if (ChainingProblem::verify().succeeded() &&
436  CyclicProblem::verify().succeeded())
437  return success();
438  return failure();
439 }
440 
441 //===----------------------------------------------------------------------===//
442 // Dependence
443 //===----------------------------------------------------------------------===//
444 
445 Operation *Dependence::getSource() const {
446  return isDefUse() ? defUse->get().getDefiningOp() : auxSrc;
447 }
448 
449 Operation *Dependence::getDestination() const {
450  return isDefUse() ? defUse->getOwner() : auxDst;
451 }
452 
453 std::optional<unsigned> Dependence::getSourceIndex() const {
454  if (!isDefUse())
455  return std::nullopt;
456 
457  assert(isa<OpResult>(defUse->get()) && "source is not an operation");
458  return dyn_cast<OpResult>(defUse->get()).getResultNumber();
459 }
460 
461 std::optional<unsigned> Dependence::getDestinationIndex() const {
462  if (!isDefUse())
463  return std::nullopt;
464  return defUse->getOperandNumber();
465 }
466 
470 }
471 
472 bool Dependence::operator==(const Dependence &other) const {
473  return getAsTuple() == other.getAsTuple();
474 }
475 
476 //===----------------------------------------------------------------------===//
477 // DependenceIterator
478 //===----------------------------------------------------------------------===//
479 
481  bool end)
482  : problem(problem), op(op), operandIdx(0), auxPredIdx(0), auxPreds(nullptr),
483  dep() {
484  if (!end) {
485  if (problem.auxDependences.count(op))
487 
489  }
490 }
491 
493  // Yield dependences corresponding to values used by `op`'s operands...
494  while (operandIdx < op->getNumOperands()) {
495  dep = Dependence(&op->getOpOperand(operandIdx++));
496  Operation *src = dep.getSource();
497 
498  // ... but only if they are outgoing from operations that are registered in
499  // the scheduling problem.
500  if (src && problem.hasOperation(src))
501  return;
502  }
503 
504  // Then, yield auxiliary dependences, if present.
505  if (auxPreds && auxPredIdx < auxPreds->size()) {
506  dep = Dependence((*auxPreds)[auxPredIdx++], op);
507  return;
508  }
509 
510  // An invalid dependence signals the end of iteration.
511  dep = Dependence();
512 }
assert(baseType &&"element must be base type")
Problem::Dependence Dependence
LogicalResult verify() override
Return success if the computed solution is valid.
Definition: Problems.cpp:434
LogicalResult checkDefUse(Dependence dep)
Definition: Problems.cpp:414
LogicalResult check() override
Return success if the constructed scheduling problem is valid.
Definition: Problems.cpp:422
virtual LogicalResult check() override
Return success if the constructed scheduling problem is valid.
Definition: Problems.cpp:290
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...
Definition: Problems.cpp:255
virtual LogicalResult verify() override
Return success if the computed solution is valid.
Definition: Problems.cpp:301
virtual LogicalResult verifyStartTimeInCycle(Operation *op)
op has a non-negative start time in its cycle.
Definition: Problems.cpp:248
virtual LogicalResult checkDelays(OperatorType opr)
Incoming/outgoing delays are set for opr and non-negative.
Definition: Problems.cpp:224
virtual LogicalResult verifyInitiationInterval()
This problem has a non-zero II.
Definition: Problems.cpp:192
virtual PropertyStringVector getProperties() override
Definition: Problems.cpp:164
virtual LogicalResult verifyPrecedence(Dependence dep) override
dep's source operation is available before dep's destination operation starts (dep's distance iterati...
Definition: Problems.cpp:171
virtual LogicalResult verify() override
Return success if the computed solution is valid.
Definition: Problems.cpp:198
virtual LogicalResult verify() override
Return success if the computed solution is valid.
Definition: Problems.cpp:397
virtual LogicalResult verifyUtilization(OperatorType opr) override
opr is not oversubscribed in any congruence class modulo II.
Definition: Problems.cpp:376
This class models the most basic scheduling problem.
Definition: Problems.h:75
virtual LogicalResult checkLatency(OperatorType opr)
opr has a latency.
Definition: Problems.cpp:88
virtual LogicalResult verify()
Return success if the computed solution is valid.
Definition: Problems.cpp:132
virtual LogicalResult check()
Return success if the constructed scheduling problem is valid.
Definition: Problems.cpp:96
virtual PropertyStringVector getProperties()
Definition: Problems.cpp:78
llvm::iterator_range< detail::DependenceIterator > DependenceRange
Definition: Problems.h:105
bool hasOperation(Operation *op)
Return true if op is part of this problem.
Definition: Problems.h:170
LogicalResult insertDependence(Dependence dep)
Include dep in the scheduling problem.
Definition: Problems.cpp:26
std::optional< unsigned > getEndTime(Operation *op)
Returns the end time for op, as computed by the scheduler.
Definition: Problems.cpp:145
OperatorType getOrInsertOperatorType(StringRef name)
Retrieves the operator type identified by the client-specific name.
Definition: Problems.cpp:47
AuxDependenceMap auxDependences
Definition: Problems.h:131
llvm::SmallVector< std::pair< std::string, std::string >, 2 > PropertyStringVector
Definition: Problems.h:252
virtual LogicalResult verifyStartTime(Operation *op)
op has a start time.
Definition: Problems.cpp:108
virtual LogicalResult checkLinkedOperatorType(Operation *op)
op is linked to a registered operator type.
Definition: Problems.cpp:80
DependenceRange getDependences(Operation *op)
Return a range object to transparently iterate over op's incoming 1) implicit def-use dependences (ba...
Definition: Problems.cpp:53
virtual LogicalResult verifyPrecedence(Dependence dep)
dep's source operation is available before dep's destination operation starts.
Definition: Problems.cpp:114
mlir::StringAttr OperatorType
Operator types are distinguished by name (chosen by the client).
Definition: Problems.h:98
virtual LogicalResult verify() override
Return success if the computed solution is valid.
Definition: Problems.cpp:361
virtual LogicalResult checkLatency(OperatorType opr) override
If opr is limited, it has a non-zero latency.
Definition: Problems.cpp:329
virtual LogicalResult verifyUtilization(OperatorType opr)
opr is not oversubscribed in any time step.
Definition: Problems.cpp:341
An iterator to transparently surface an operation's def-use dependences from the SSA subgraph (induce...
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.
Definition: Problems.cpp:480
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
Definition: Problems.cpp:472
std::optional< unsigned > getDestinationIndex() const
Return the destination operation's operand number, if applicable.
Definition: Problems.cpp:461
std::optional< unsigned > getSourceIndex() const
Return the source operation's result number, if applicable.
Definition: Problems.cpp:453
Operation * getDestination() const
Return the destination of the dependence.
Definition: Problems.cpp:449
bool isAuxiliary() const
Return true if this is a valid auxiliary dependence.
TupleRepr getAsTuple() const
Return the tuple representation of this dependence.
Definition: Problems.cpp:467
bool isDefUse() const
Return true if this is a valid def-use dependence.
Operation * getSource() const
Return the source of the dependence.
Definition: Problems.cpp:445
Direction get(bool isOutput)
Returns an output direction if isOutput is true, otherwise returns an input direction.
Definition: CalyxOps.cpp:55
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
Definition: DebugAnalysis.h:21