CIRCT  19.0.0git
Problems.h
Go to the documentation of this file.
1 //===- Problems.h - Modeling of scheduling problems -------------*- C++ -*-===//
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 // Static scheduling algorithms for use in HLS flows all solve similar problems.
10 // The classes in this file serve as an interface between clients and algorithm
11 // implementations, and model a basic scheduling problem and some commonly used
12 // extensions (e.g. modulo scheduling). This includes problem-specific
13 // verification methods.
14 //
15 //===----------------------------------------------------------------------===//
16 
17 #ifndef CIRCT_SCHEDULING_PROBLEMS_H
18 #define CIRCT_SCHEDULING_PROBLEMS_H
19 
21 #include "circt/Support/LLVM.h"
22 
23 #include "mlir/IR/BuiltinAttributes.h"
24 #include "llvm/ADT/DenseMap.h"
25 #include "llvm/ADT/SetVector.h"
26 
27 #include <optional>
28 
29 #define DEFINE_COMMON_MEMBERS(ProblemClass) \
30 protected: \
31  ProblemClass() {} \
32  \
33 public: \
34  static constexpr auto PROBLEM_NAME = #ProblemClass; \
35  static ProblemClass get(Operation *containingOp) { \
36  ProblemClass prob; \
37  prob.setContainingOp(containingOp); \
38  return prob; \
39  }
40 
41 namespace circt {
42 namespace scheduling {
43 
44 /// This class models the most basic scheduling problem.
45 ///
46 /// A problem instance is comprised of:
47 ///
48 /// - *Operations*: The vertices in the data-flow graph to be scheduled.
49 /// - *Dependences*: The edges in the data-flow graph to be scheduled, modeling
50 /// a precedence relation between the involved operations.
51 /// - *Operator types*: An abstraction of the characteristics of the target
52 /// representation, e.g. modules in the HLS component library, available
53 /// functional units, etc. -- operations are executed on instances/units of
54 /// an operator type.
55 ///
56 /// Operations and operator types are stored explicitly. The registered
57 /// operations induce a subgraph of the SSA graph. We implicitly include the
58 /// dependences corresponding to its *def-use* relationships in the problem,
59 /// e.g. if operation *y*'s second operand uses the first result produced by
60 /// *x*, we'd have a dependence `x:0 --> y:1`. Clients can additionally register
61 /// explicit, *auxiliary* dependence between operations, e.g. to encode memory
62 /// dependencies or other ordering constraints. Auxiliary dependences do not
63 /// distinguish specific operands/results. The differences between the flavors
64 /// are transparent to concrete algorithms.
65 ///
66 /// All components of the problem (operations, dependences, operator types, as
67 /// well as the instance itself) can be annotated with *properties*. In this
68 /// basic problem, we model
69 ///
70 /// - `linkedOperatorType` maps operations to their operator types.
71 /// - `latency`, an operator type-property denoting the number of time steps
72 /// after which the operator's result is available.
73 /// - `startTime`, an operation-property for the time step in which an operation
74 /// is started. Together, the start times for all operations represent the
75 /// problem's solution, i.e. the schedule.
76 ///
77 /// Subclasses, i.e. corresponding to more complex scheduling problems, can
78 /// declare additional properties as needed.
79 //
80 /// The `check...` methods perform validity checks before scheduling, e.g. that
81 /// all operations have an associated operator type, etc.
82 ///
83 /// The `verify...` methods check the correctness of the solution determined by
84 /// a concrete scheduling algorithm, e.g. that there are start times available
85 /// for each registered operation, and the precedence constraints as modeled by
86 /// the dependences are satisfied.
87 class Problem {
89 
90 public:
91  virtual ~Problem() = default;
92 
94 
95  //===--------------------------------------------------------------------===//
96  // Aliases for the problem components
97  //===--------------------------------------------------------------------===//
98 public:
99  /// A thin wrapper to allow a uniform handling of def-use and auxiliary
100  /// dependences.
102 
103  /// Operator types are distinguished by name (chosen by the client).
104  using OperatorType = mlir::StringAttr;
105 
106  //===--------------------------------------------------------------------===//
107  // Aliases for containers storing the problem components and properties
108  //===--------------------------------------------------------------------===//
109 public:
110  using OperationSet = llvm::SetVector<Operation *>;
111  using DependenceRange = llvm::iterator_range<detail::DependenceIterator>;
112  using OperatorTypeSet = llvm::SetVector<OperatorType>;
113 
114 protected:
116  llvm::DenseMap<Operation *, llvm::SmallSetVector<Operation *, 4>>;
117 
118  template <typename T>
119  using OperationProperty = llvm::DenseMap<Operation *, std::optional<T>>;
120  template <typename T>
121  using DependenceProperty = llvm::DenseMap<Dependence, std::optional<T>>;
122  template <typename T>
123  using OperatorTypeProperty = llvm::DenseMap<OperatorType, std::optional<T>>;
124  template <typename T>
125  using InstanceProperty = std::optional<T>;
126 
127  //===--------------------------------------------------------------------===//
128  // Containers for problem components and properties
129  //===--------------------------------------------------------------------===//
130 private:
131  // Operation containing the ops for this scheduling problem. Used for its
132  // MLIRContext and to emit diagnostics.
133  Operation *containingOp;
134 
135  // Problem components
139 
140  // Operation properties
143 
144  // Operator type properties
146 
147  //===--------------------------------------------------------------------===//
148  // Problem construction
149  //===--------------------------------------------------------------------===//
150 public:
151  /// Include \p op in this scheduling problem.
152  void insertOperation(Operation *op) { operations.insert(op); }
153 
154  /// Include \p dep in the scheduling problem. Return failure if \p dep does
155  /// not represent a valid def-use or auxiliary dependence between operations.
156  /// The endpoints become registered operations w.r.t. the problem.
157  LogicalResult insertDependence(Dependence dep);
158 
159  /// Include \p opr in this scheduling problem.
160  void insertOperatorType(OperatorType opr) { operatorTypes.insert(opr); }
161 
162  /// Retrieves the operator type identified by the client-specific \p name. The
163  /// operator type is automatically registered in the scheduling problem.
164  OperatorType getOrInsertOperatorType(StringRef name);
165 
166  //===--------------------------------------------------------------------===//
167  // Access to problem components
168  //===--------------------------------------------------------------------===//
169 public:
170  /// Return the operation containing this problem, e.g. to emit diagnostics.
171  Operation *getContainingOp() { return containingOp; }
172  /// Set the operation containing this problem, e.g. to emit diagnostics.
173  void setContainingOp(Operation *op) { containingOp = op; }
174 
175  /// Return true if \p op is part of this problem.
176  bool hasOperation(Operation *op) { return operations.contains(op); }
177  /// Return the set of operations.
178  const OperationSet &getOperations() { return operations; }
179 
180  /// Return a range object to transparently iterate over \p op's *incoming*
181  /// 1) implicit def-use dependences (backed by the SSA graph), and then
182  /// 2) explictly added auxiliary dependences.
183  ///
184  /// In other words, this yields dependences whose destination operation is
185  /// \p op, and whose source operations are \p op's predecessors in the problem
186  /// graph.
187  ///
188  /// To iterate over all of the scheduling problem's dependences, simply
189  /// process the ranges for all registered operations.
190  DependenceRange getDependences(Operation *op);
191 
192  /// Return true if \p opr is part of this problem.
193  bool hasOperatorType(OperatorType opr) { return operatorTypes.contains(opr); }
194  /// Return the set of operator types.
196 
197  //===--------------------------------------------------------------------===//
198  // Access to properties
199  //===--------------------------------------------------------------------===//
200 public:
201  /// The linked operator type provides the runtime characteristics for \p op.
202  std::optional<OperatorType> getLinkedOperatorType(Operation *op) {
203  return linkedOperatorType.lookup(op);
204  }
205  void setLinkedOperatorType(Operation *op, OperatorType opr) {
206  linkedOperatorType[op] = opr;
207  }
208 
209  /// The latency is the number of cycles \p opr needs to compute its result.
210  std::optional<unsigned> getLatency(OperatorType opr) {
211  return latency.lookup(opr);
212  }
213  void setLatency(OperatorType opr, unsigned val) { latency[opr] = val; }
214 
215  /// Return the start time for \p op, as computed by the scheduler.
216  /// These start times comprise the basic problem's solution, i.e. the
217  /// *schedule*.
218  std::optional<unsigned> getStartTime(Operation *op) {
219  return startTime.lookup(op);
220  }
221  void setStartTime(Operation *op, unsigned val) { startTime[op] = val; }
222 
223  //===--------------------------------------------------------------------===//
224  // Access to derived properties
225  //===--------------------------------------------------------------------===//
226 public:
227  /// Returns the end time for \p op, as computed by the scheduler.
228  /// This end time is derived from the start time and the operator type's
229  /// latency.
230  std::optional<unsigned> getEndTime(Operation *op);
231 
232  //===--------------------------------------------------------------------===//
233  // Optional names (for exporting and debugging instances)
234  //===--------------------------------------------------------------------===//
235 private:
238 
239 public:
240  StringAttr getInstanceName() { return instanceName; }
241  void setInstanceName(StringAttr name) { instanceName = name; }
242 
243  StringAttr getLibraryName() { return libraryName; }
244  void setLibraryName(StringAttr name) { libraryName = name; }
245 
246  StringAttr getOperationName(Operation *op) {
247  return operationNames.lookup(op);
248  }
249  void setOperationName(Operation *op, StringAttr name) {
250  operationNames[op] = name;
251  }
252 
253  //===--------------------------------------------------------------------===//
254  // Properties as string key-value pairs (e.g. for DOT graphs)
255  //===--------------------------------------------------------------------===//
256 public:
258  llvm::SmallVector<std::pair<std::string, std::string>, 2>;
259 
260  virtual PropertyStringVector getProperties(Operation *op);
264 
265  //===--------------------------------------------------------------------===//
266  // Property-specific validators
267  //===--------------------------------------------------------------------===//
268 protected:
269  /// \p op is linked to a registered operator type.
270  virtual LogicalResult checkLinkedOperatorType(Operation *op);
271  /// \p opr has a latency.
272  virtual LogicalResult checkLatency(OperatorType opr);
273  /// \p op has a start time.
274  virtual LogicalResult verifyStartTime(Operation *op);
275  /// \p dep's source operation is available before \p dep's destination
276  /// operation starts.
277  virtual LogicalResult verifyPrecedence(Dependence dep);
278 
279  //===--------------------------------------------------------------------===//
280  // Client API for problem validation
281  //===--------------------------------------------------------------------===//
282 public:
283  /// Return success if the constructed scheduling problem is valid.
284  virtual LogicalResult check();
285  /// Return success if the computed solution is valid.
286  virtual LogicalResult verify();
287 };
288 
289 /// This class models a cyclic scheduling problem. Its solution can be used to
290 /// construct a pipelined datapath with a fixed, integer initiation interval,
291 /// in which the execution of multiple iterations/samples/etc. may overlap.
292 class CyclicProblem : public virtual Problem {
294 
295 private:
298 
299 public:
300  /// The distance determines whether a dependence has to be satisfied in the
301  /// same iteration (distance=0 or not set), or distance-many iterations later.
302  std::optional<unsigned> getDistance(Dependence dep) {
303  return distance.lookup(dep);
304  }
305  void setDistance(Dependence dep, unsigned val) { distance[dep] = val; }
306 
307  /// The initiation interval (II) is the number of time steps between
308  /// subsequent iterations, i.e. a new iteration is started every II time
309  /// steps. The best possible value is 1, meaning that a corresponding pipeline
310  /// accepts new data every cycle. This property is part of the cyclic
311  /// problem's solution.
312  std::optional<unsigned> getInitiationInterval() { return initiationInterval; }
313  void setInitiationInterval(unsigned val) { initiationInterval = val; }
314 
315  virtual PropertyStringVector getProperties(Dependence dep) override;
316  virtual PropertyStringVector getProperties() override;
317 
318 protected:
319  /// \p dep's source operation is available before \p dep's destination
320  /// operation starts (\p dep's distance iterations later).
321  virtual LogicalResult verifyPrecedence(Dependence dep) override;
322  /// This problem has a non-zero II.
323  virtual LogicalResult verifyInitiationInterval();
324 
325 public:
326  virtual LogicalResult verify() override;
327 };
328 
329 /// This class models the accumulation of physical propagation delays on
330 /// combinational paths along SSA dependences.
331 ///
332 /// Each operator type is annotated with estimated values for incoming and
333 /// outgoing delays. Combinational operators (zero-latency, no internal
334 /// registers) have only a single delay; this important special case is modeled
335 /// by setting the incoming and outgoing delays to the same value.
336 ///
337 /// A solution to this problem comprises per-operation start times in a
338 /// continuous unit, e.g. in nanoseconds, inside the discrete time steps/cycles
339 /// determined by the underlying scheduling problem.
340 class ChainingProblem : public virtual Problem {
342 
343 private:
346 
347 public:
348  /// The incoming delay denotes the propagation time from the operand inputs to
349  /// either the result outputs (combinational operators) or the first internal
350  /// register stage.
351  std::optional<float> getIncomingDelay(OperatorType opr) {
352  return incomingDelay.lookup(opr);
353  }
354  void setIncomingDelay(OperatorType opr, float delay) {
355  incomingDelay[opr] = delay;
356  }
357 
358  /// The outgoing delay denotes the propagation time from either the operand
359  /// inputs (combinational operators) or the last internal register stage to
360  /// the result outputs.
361  std::optional<float> getOutgoingDelay(OperatorType opr) {
362  return outgoingDelay.lookup(opr);
363  }
364  void setOutgoingDelay(OperatorType opr, float delay) {
365  outgoingDelay[opr] = delay;
366  }
367 
368  /// Computed by the scheduler, this start time is relative to the beginning of
369  /// the cycle that \p op starts in.
370  std::optional<float> getStartTimeInCycle(Operation *op) {
371  return startTimeInCycle.lookup(op);
372  }
373  void setStartTimeInCycle(Operation *op, float time) {
374  startTimeInCycle[op] = time;
375  }
376 
377  virtual PropertyStringVector getProperties(Operation *op) override;
378  virtual PropertyStringVector getProperties(OperatorType opr) override;
379 
380 protected:
381  /// Incoming/outgoing delays are set for \p opr and non-negative. The delays
382  /// are equal if \p opr is a zero-latency operator type.
383  virtual LogicalResult checkDelays(OperatorType opr);
384 
385  /// \p op has a non-negative start time in its cycle.
386  virtual LogicalResult verifyStartTimeInCycle(Operation *op);
387  /// If \p dep is an SSA edge and its source operation finishes in the same
388  /// time step as the destination operation, the source's result is available
389  /// before the destination starts in that cycle.
390  virtual LogicalResult verifyPrecedenceInCycle(Dependence dep);
391 
392 public:
393  virtual LogicalResult check() override;
394  virtual LogicalResult verify() override;
395 };
396 
397 /// This class models a resource-constrained scheduling problem. An optional,
398 /// non-zero *limit* marks operator types to be *shared* by the operations using
399 /// them. In an HLS setting, this corresponds to multiplexing multiple
400 /// operations onto a pre-allocated number of operator instances. These
401 /// instances are assumed to be *fully pipelined*, meaning each instance can
402 /// accept new operands (coming from a distinct operation) in each time step.
403 ///
404 /// A solution to this problem is feasible iff the number of operations that use
405 /// a certain limited operator type, and start in the same time step, does not
406 /// exceed the operator type's limit. These constraints do not apply to operator
407 /// types without a limit (not set, or 0).
408 class SharedOperatorsProblem : public virtual Problem {
410 
411 private:
413 
414 public:
415  /// The limit is the maximum number of operations using \p opr that are
416  /// allowed to start in the same time step.
417  std::optional<unsigned> getLimit(OperatorType opr) {
418  return limit.lookup(opr);
419  }
420  void setLimit(OperatorType opr, unsigned val) { limit[opr] = val; }
421 
422  virtual PropertyStringVector getProperties(OperatorType opr) override;
423 
424 protected:
425  /// If \p opr is limited, it has a non-zero latency.
426  virtual LogicalResult checkLatency(OperatorType opr) override;
427  /// \p opr is not oversubscribed in any time step.
428  virtual LogicalResult verifyUtilization(OperatorType opr);
429 
430 public:
431  virtual LogicalResult verify() override;
432 };
433 
434 /// This class models the modulo scheduling problem as the composition of the
435 /// cyclic problem and the resource-constrained problem with fully-pipelined
436 /// shared operators.
437 ///
438 /// A solution to this problem comprises an integer II and integer start times
439 /// for all registered operations, and is feasible iff:
440 /// (1) The precedence constraints implied by the `CyclicProblem`'s dependence
441 /// edges are satisfied, and
442 /// (2) The number of operations that use a certain limited operator type,
443 /// and start in the same congruence class (= start time *mod* II), does
444 /// not exceed the operator type's limit.
445 class ModuloProblem : public virtual CyclicProblem,
446  public virtual SharedOperatorsProblem {
448 
449 protected:
450  /// \p opr is not oversubscribed in any congruence class modulo II.
451  virtual LogicalResult verifyUtilization(OperatorType opr) override;
452 
453 public:
454  virtual LogicalResult verify() override;
455 };
456 
457 /// This class models the accumulation of physical propagation delays on
458 /// combinational paths along SSA dependences on a cyclic scheduling problem.
459 ///
460 /// Each operator type is annotated with estimated values for incoming and
461 /// outgoing delays. Combinational operators (zero-latency, no internal
462 /// registers) have only a single delay; this important special case is modeled
463 /// by setting the incoming and outgoing delays to the same values.
464 ///
465 /// A solution to this problem comprises per-operation start times in a
466 /// continuous unit, e.g. in nanoseconds, inside the discrete time steps/cycles
467 /// determined by the underlying scheduling problem. Its solution can be used to
468 /// construct a pipelined datapath with a fixed, integer initiation interval,
469 /// in which the execution of multiple iterations/samples/etc. may overlap.
470 class ChainingCyclicProblem : public virtual ChainingProblem,
471  public virtual CyclicProblem {
473 
474 public:
475  LogicalResult checkDefUse(Dependence dep);
476  LogicalResult check() override;
477  LogicalResult verify() override;
478 };
479 
480 } // namespace scheduling
481 } // namespace circt
482 
483 #undef DEFINE_COMMON_MEMBERS
484 
485 #endif // CIRCT_SCHEDULING_PROBLEMS_H
Problem::Dependence Dependence
#define DEFINE_COMMON_MEMBERS(ProblemClass)
Definition: Problems.h:29
This class models the accumulation of physical propagation delays on combinational paths along SSA de...
Definition: Problems.h:471
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
This class models the accumulation of physical propagation delays on combinational paths along SSA de...
Definition: Problems.h:340
void setStartTimeInCycle(Operation *op, float time)
Definition: Problems.h:373
void setIncomingDelay(OperatorType opr, float delay)
Definition: Problems.h:354
OperationProperty< float > startTimeInCycle
Definition: Problems.h:345
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
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...
Definition: Problems.h:370
std::optional< float > getIncomingDelay(OperatorType opr)
The incoming delay denotes the propagation time from the operand inputs to either the result outputs ...
Definition: Problems.h:351
std::optional< float > getOutgoingDelay(OperatorType opr)
The outgoing delay denotes the propagation time from either the operand inputs (combinational operato...
Definition: Problems.h:361
OperatorTypeProperty< float > incomingDelay
Definition: Problems.h:344
void setOutgoingDelay(OperatorType opr, float delay)
Definition: Problems.h:364
virtual LogicalResult verify() override
Return success if the computed solution is valid.
Definition: Problems.cpp:301
OperatorTypeProperty< float > outgoingDelay
Definition: Problems.h:344
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
This class models a cyclic scheduling problem.
Definition: Problems.h:292
std::optional< unsigned > getInitiationInterval()
The initiation interval (II) is the number of time steps between subsequent iterations,...
Definition: Problems.h:312
void setDistance(Dependence dep, unsigned val)
Definition: Problems.h:305
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
void setInitiationInterval(unsigned val)
Definition: Problems.h:313
InstanceProperty< unsigned > initiationInterval
Definition: Problems.h:297
virtual LogicalResult verify() override
Return success if the computed solution is valid.
Definition: Problems.cpp:198
DependenceProperty< unsigned > distance
Definition: Problems.h:296
std::optional< unsigned > getDistance(Dependence dep)
The distance determines whether a dependence has to be satisfied in the same iteration (distance=0 or...
Definition: Problems.h:302
This class models the modulo scheduling problem as the composition of the cyclic problem and the reso...
Definition: Problems.h:446
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:87
void setLatency(OperatorType opr, unsigned val)
Definition: Problems.h:213
virtual LogicalResult checkLatency(OperatorType opr)
opr has a latency.
Definition: Problems.cpp:88
llvm::DenseMap< Operation *, llvm::SmallSetVector< Operation *, 4 > > AuxDependenceMap
Definition: Problems.h:116
llvm::SetVector< Operation * > OperationSet
Definition: Problems.h:110
llvm::SetVector< OperatorType > OperatorTypeSet
Definition: Problems.h:112
virtual LogicalResult verify()
Return success if the computed solution is valid.
Definition: Problems.cpp:132
StringAttr getInstanceName()
Definition: Problems.h:240
virtual LogicalResult check()
Return success if the constructed scheduling problem is valid.
Definition: Problems.cpp:96
std::optional< OperatorType > getLinkedOperatorType(Operation *op)
The linked operator type provides the runtime characteristics for op.
Definition: Problems.h:202
virtual PropertyStringVector getProperties()
Definition: Problems.cpp:78
void insertOperation(Operation *op)
Include op in this scheduling problem.
Definition: Problems.h:152
llvm::iterator_range< detail::DependenceIterator > DependenceRange
Definition: Problems.h:111
OperationSet operations
Definition: Problems.h:136
bool hasOperation(Operation *op)
Return true if op is part of this problem.
Definition: Problems.h:176
StringAttr getLibraryName()
Definition: Problems.h:243
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
const OperatorTypeSet & getOperatorTypes()
Return the set of operator types.
Definition: Problems.h:195
OperationProperty< OperatorType > linkedOperatorType
Definition: Problems.h:141
OperationProperty< unsigned > startTime
Definition: Problems.h:142
std::optional< T > InstanceProperty
Definition: Problems.h:125
std::optional< unsigned > getStartTime(Operation *op)
Return the start time for op, as computed by the scheduler.
Definition: Problems.h:218
void setStartTime(Operation *op, unsigned val)
Definition: Problems.h:221
OperatorTypeProperty< unsigned > latency
Definition: Problems.h:145
SmallDenseMap< Operation *, StringAttr > operationNames
Definition: Problems.h:237
llvm::DenseMap< Operation *, std::optional< T > > OperationProperty
Definition: Problems.h:119
virtual ~Problem()=default
void setContainingOp(Operation *op)
Set the operation containing this problem, e.g. to emit diagnostics.
Definition: Problems.h:173
OperatorType getOrInsertOperatorType(StringRef name)
Retrieves the operator type identified by the client-specific name.
Definition: Problems.cpp:47
AuxDependenceMap auxDependences
Definition: Problems.h:137
llvm::DenseMap< OperatorType, std::optional< T > > OperatorTypeProperty
Definition: Problems.h:123
void setInstanceName(StringAttr name)
Definition: Problems.h:241
OperatorTypeSet operatorTypes
Definition: Problems.h:138
llvm::SmallVector< std::pair< std::string, std::string >, 2 > PropertyStringVector
Definition: Problems.h:258
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
llvm::DenseMap< Dependence, std::optional< T > > DependenceProperty
Definition: Problems.h:121
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
Operation * containingOp
Definition: Problems.h:133
bool hasOperatorType(OperatorType opr)
Return true if opr is part of this problem.
Definition: Problems.h:193
const OperationSet & getOperations()
Return the set of operations.
Definition: Problems.h:178
virtual LogicalResult verifyPrecedence(Dependence dep)
dep's source operation is available before dep's destination operation starts.
Definition: Problems.cpp:114
void setLibraryName(StringAttr name)
Definition: Problems.h:244
void setLinkedOperatorType(Operation *op, OperatorType opr)
Definition: Problems.h:205
mlir::StringAttr OperatorType
Operator types are distinguished by name (chosen by the client).
Definition: Problems.h:104
void insertOperatorType(OperatorType opr)
Include opr in this scheduling problem.
Definition: Problems.h:160
void setOperationName(Operation *op, StringAttr name)
Definition: Problems.h:249
StringAttr getOperationName(Operation *op)
Definition: Problems.h:246
std::optional< unsigned > getLatency(OperatorType opr)
The latency is the number of cycles opr needs to compute its result.
Definition: Problems.h:210
Operation * getContainingOp()
Return the operation containing this problem, e.g. to emit diagnostics.
Definition: Problems.h:171
This class models a resource-constrained scheduling problem.
Definition: Problems.h:408
OperatorTypeProperty< unsigned > limit
Definition: Problems.h:412
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
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...
Definition: Problems.h:417
virtual LogicalResult verifyUtilization(OperatorType opr)
opr is not oversubscribed in any time step.
Definition: Problems.cpp:341
void setLimit(OperatorType opr, unsigned val)
Definition: Problems.h:420
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...
Definition: DebugAnalysis.h:21