CIRCT  17.0.0git
SimplexSchedulers.cpp
Go to the documentation of this file.
1 //===- SimplexSchedulers.cpp - Linear programming-based schedulers --------===//
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 // Implementation of linear programming-based schedulers with a built-in simplex
10 // solver.
11 //
12 //===----------------------------------------------------------------------===//
13 
16 
17 #include "mlir/IR/Operation.h"
18 
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/Support/Debug.h"
21 #include "llvm/Support/Format.h"
22 
23 #include <algorithm>
24 #include <limits>
25 
26 #define DEBUG_TYPE "simplex-schedulers"
27 
28 using namespace circt;
29 using namespace circt::scheduling;
30 
31 using llvm::dbgs;
32 using llvm::format;
33 
34 namespace {
35 
36 /// This class provides a framework to model certain scheduling problems as
37 /// lexico-parametric linear programs (LP), which are then solved with an
38 /// extended version of the dual simplex algorithm.
39 ///
40 /// The approach is described in:
41 /// [1] B. D. de Dinechin, "Simplex Scheduling: More than Lifetime-Sensitive
42 /// Instruction Scheduling", PRISM 1994.22, 1994.
43 /// [2] B. D. de Dinechin, "Fast Modulo Scheduling Under the Simplex Scheduling
44 /// Framework", PRISM 1995.01, 1995.
45 ///
46 /// Resource-free scheduling problems (called "central problems" in the papers)
47 /// have an *integer* linear programming formulation with a totally unimodular
48 /// constraint matrix. Such ILPs can however be solved optimally in polynomial
49 /// time with a (non-integer) LP solver (such as the simplex algorithm), as the
50 /// LP solution is guaranteed to be integer. Note that this is the same idea as
51 /// used by SDC-based schedulers.
52 class SimplexSchedulerBase {
53 protected:
54  /// The objective is to minimize the start time of this operation.
55  Operation *lastOp;
56 
57  /// S is part of a mechanism to assign fixed values to the LP variables.
58  int parameterS;
59 
60  /// T represents the initiation interval (II). Its minimally-feasible value is
61  /// computed by the algorithm.
62  int parameterT;
63 
64  /// The simplex tableau is the algorithm's main data structure.
65  /// The dashed parts always contain the zero respectively the identity matrix,
66  /// and therefore are not stored explicitly.
67  ///
68  /// ◀───nColumns────▶
69  /// nParameters────┐
70  /// ◀─┴─▶
71  /// ┌─────┬───────────┬ ─ ─ ─ ─ ┐
72  /// ▲│. . .│. . ... . .│ 0 ▲
73  /// nObjectives││. . .│. . ... . .│ │ │
74  /// ▼│. . .│. . ... . .│ │
75  /// ├─────┼───────────┼ ─ ─ ─ ─ ┤ │
76  /// firstConstraintRow > │. . .│. . ... . .│1 │nRows
77  /// │. . .│. . ... . .│ 1 │ │
78  /// │. . .│. . ... . .│ 1 │
79  /// │. . .│. . ... . .│ 1 │ │
80  /// │. . .│. . ... . .│ 1 ▼
81  /// └─────┴───────────┴ ─ ─ ─ ─ ┘
82  /// parameter1Column ^
83  /// parameterSColumn ^
84  /// parameterTColumn ^
85  /// firstNonBasicVariableColumn ^
86  /// ─────────── ──────────
87  /// nonBasicVariables basicVariables
88  SmallVector<SmallVector<int>> tableau;
89 
90  /// During the pivot operation, one column in the elided part of the tableau
91  /// is modified; this vector temporarily catches the changes.
92  SmallVector<int> implicitBasicVariableColumnVector;
93 
94  /// The linear program models the operations' start times as variables, which
95  /// we identify here as 0, ..., |ops|-1.
96  /// Additionally, for each dependence (precisely, the inequality modeling the
97  /// precedence constraint), a slack variable is required; these are identified
98  /// as |ops|, ..., |ops|+|deps|-1.
99  ///
100  /// This vector stores the numeric IDs of non-basic variables. A variable's
101  /// index *i* in this vector corresponds to the tableau *column*
102  /// `firstNonBasicVariableColumn`+*i*.
103  SmallVector<unsigned> nonBasicVariables;
104 
105  /// This vector store the numeric IDs of basic variables. A variable's index
106  /// *i* in this vector corresponds to the tableau *row*
107  /// `firstConstraintRow`+*i*.
108  SmallVector<unsigned> basicVariables;
109 
110  /// Used to conveniently retrieve an operation's start time variable. The
111  /// alternative would be to find the op's index in the problem's list of
112  /// operations.
113  DenseMap<Operation *, unsigned> startTimeVariables;
114 
115  /// This vector keeps track of the current locations (i.e. row or column) of
116  /// a start time variable in the tableau. We encode column numbers as positive
117  /// integers, and row numbers as negative integers. We do not track the slack
118  /// variables.
119  SmallVector<int> startTimeLocations;
120 
121  /// Non-basic variables can be "frozen" to a specific value, which prevents
122  /// them from being pivoted into basis again.
123  DenseMap<unsigned, unsigned> frozenVariables;
124 
125  /// Number of rows in the tableau = |obj| + |deps|.
126  unsigned nRows;
127  /// Number of explicitly stored columns in the tableau = |params| + |ops|.
128  unsigned nColumns;
129 
130  // Number of objective rows.
131  unsigned nObjectives;
132  /// All other rows encode linear constraints.
133  unsigned &firstConstraintRow = nObjectives;
134 
135  // Number of parameters (fixed for now).
136  static constexpr unsigned nParameters = 3;
137  /// The first column corresponds to the always-one "parameter" in u = (1,S,T).
138  static constexpr unsigned parameter1Column = 0;
139  /// The second column corresponds to the variable-freezing parameter S.
140  static constexpr unsigned parameterSColumn = 1;
141  /// The third column corresponds to the parameter T, i.e. the current II.
142  static constexpr unsigned parameterTColumn = 2;
143  /// All other (explicitly stored) columns represent non-basic variables.
144  static constexpr unsigned firstNonBasicVariableColumn = nParameters;
145 
146  /// Allow subclasses to collect additional constraints that are not part of
147  /// the input problem, but should be modeled in the linear problem.
148  SmallVector<Problem::Dependence> additionalConstraints;
149 
150  virtual Problem &getProblem() = 0;
151  virtual LogicalResult checkLastOp();
152  virtual bool fillObjectiveRow(SmallVector<int> &row, unsigned obj);
153  virtual void fillConstraintRow(SmallVector<int> &row,
154  Problem::Dependence dep);
155  virtual void fillAdditionalConstraintRow(SmallVector<int> &row,
156  Problem::Dependence dep);
157  void buildTableau();
158 
159  int getParametricConstant(unsigned row);
160  SmallVector<int> getObjectiveVector(unsigned column);
161  std::optional<unsigned> findDualPivotRow();
162  std::optional<unsigned> findDualPivotColumn(unsigned pivotRow,
163  bool allowPositive = false);
164  std::optional<unsigned> findPrimalPivotColumn();
165  std::optional<unsigned> findPrimalPivotRow(unsigned pivotColumn);
166  void multiplyRow(unsigned row, int factor);
167  void addMultipleOfRow(unsigned sourceRow, int factor, unsigned targetRow);
168  void pivot(unsigned pivotRow, unsigned pivotColumn);
169  LogicalResult solveTableau();
170  LogicalResult restoreDualFeasibility();
171  bool isInBasis(unsigned startTimeVariable);
172  unsigned freeze(unsigned startTimeVariable, unsigned timeStep);
173  void translate(unsigned column, int factor1, int factorS, int factorT);
174  LogicalResult scheduleAt(unsigned startTimeVariable, unsigned timeStep);
175  void moveBy(unsigned startTimeVariable, unsigned amount);
176  unsigned getStartTime(unsigned startTimeVariable);
177 
178  void dumpTableau();
179 
180 public:
181  explicit SimplexSchedulerBase(Operation *lastOp) : lastOp(lastOp) {}
182  virtual ~SimplexSchedulerBase() = default;
183  virtual LogicalResult schedule() = 0;
184 };
185 
186 /// This class solves the basic, acyclic `Problem`.
187 class SimplexScheduler : public SimplexSchedulerBase {
188 private:
189  Problem &prob;
190 
191 protected:
192  Problem &getProblem() override { return prob; }
193 
194 public:
195  SimplexScheduler(Problem &prob, Operation *lastOp)
196  : SimplexSchedulerBase(lastOp), prob(prob) {}
197 
198  LogicalResult schedule() override;
199 };
200 
201 /// This class solves the resource-free `CyclicProblem`. The optimal initiation
202 /// interval (II) is determined as a side product of solving the parametric
203 /// problem, and corresponds to the "RecMII" (= recurrence-constrained minimum
204 /// II) usually considered as one component in the lower II bound used by modulo
205 /// schedulers.
206 class CyclicSimplexScheduler : public SimplexSchedulerBase {
207 private:
208  CyclicProblem &prob;
209 
210 protected:
211  Problem &getProblem() override { return prob; }
212  void fillConstraintRow(SmallVector<int> &row,
213  Problem::Dependence dep) override;
214 
215 public:
216  CyclicSimplexScheduler(CyclicProblem &prob, Operation *lastOp)
217  : SimplexSchedulerBase(lastOp), prob(prob) {}
218  LogicalResult schedule() override;
219 };
220 
221 // This class solves acyclic, resource-constrained `SharedOperatorsProblem` with
222 // a simplified version of the iterative heuristic presented in [2].
223 class SharedOperatorsSimplexScheduler : public SimplexSchedulerBase {
224 private:
226 
227 protected:
228  Problem &getProblem() override { return prob; }
229 
230 public:
231  SharedOperatorsSimplexScheduler(SharedOperatorsProblem &prob,
232  Operation *lastOp)
233  : SimplexSchedulerBase(lastOp), prob(prob) {}
234  LogicalResult schedule() override;
235 };
236 
237 // This class solves the `ModuloProblem` using the iterative heuristic presented
238 // in [2].
239 class ModuloSimplexScheduler : public CyclicSimplexScheduler {
240 private:
241  struct MRT {
242  ModuloSimplexScheduler &sched;
243 
245  using ReverseTableType = SmallDenseMap<Operation *, unsigned>;
248 
249  explicit MRT(ModuloSimplexScheduler &sched) : sched(sched) {}
250  LogicalResult enter(Operation *op, unsigned timeStep);
251  void release(Operation *op);
252  };
253 
254  ModuloProblem &prob;
255  SmallVector<unsigned> asapTimes, alapTimes;
256  SmallVector<Operation *> unscheduled, scheduled;
257  MRT mrt;
258 
259 protected:
260  Problem &getProblem() override { return prob; }
261  LogicalResult checkLastOp() override;
262  enum { OBJ_LATENCY = 0, OBJ_AXAP /* i.e. either ASAP or ALAP */ };
263  bool fillObjectiveRow(SmallVector<int> &row, unsigned obj) override;
264  void updateMargins();
265  void scheduleOperation(Operation *n);
266  unsigned computeResMinII();
267 
268 public:
269  ModuloSimplexScheduler(ModuloProblem &prob, Operation *lastOp)
270  : CyclicSimplexScheduler(prob, lastOp), prob(prob), mrt(*this) {}
271  LogicalResult schedule() override;
272 };
273 
274 // This class solves the `ChainingProblem` by relying on pre-computed
275 // chain-breaking constraints.
276 class ChainingSimplexScheduler : public SimplexSchedulerBase {
277 private:
278  ChainingProblem &prob;
279  float cycleTime;
280 
281 protected:
282  Problem &getProblem() override { return prob; }
283  void fillAdditionalConstraintRow(SmallVector<int> &row,
284  Problem::Dependence dep) override;
285 
286 public:
287  ChainingSimplexScheduler(ChainingProblem &prob, Operation *lastOp,
288  float cycleTime)
289  : SimplexSchedulerBase(lastOp), prob(prob), cycleTime(cycleTime) {}
290  LogicalResult schedule() override;
291 };
292 
293 } // anonymous namespace
294 
295 //===----------------------------------------------------------------------===//
296 // SimplexSchedulerBase
297 //===----------------------------------------------------------------------===//
298 
299 LogicalResult SimplexSchedulerBase::checkLastOp() {
300  auto &prob = getProblem();
301  if (!prob.hasOperation(lastOp))
302  return prob.getContainingOp()->emitError(
303  "problem does not include last operation");
304  return success();
305 }
306 
307 bool SimplexSchedulerBase::fillObjectiveRow(SmallVector<int> &row,
308  unsigned obj) {
309  assert(obj == 0);
310  // Minimize start time of user-specified last operation.
311  row[startTimeLocations[startTimeVariables[lastOp]]] = 1;
312  return false;
313 }
314 
315 void SimplexSchedulerBase::fillConstraintRow(SmallVector<int> &row,
316  Problem::Dependence dep) {
317  auto &prob = getProblem();
318  Operation *src = dep.getSource();
319  Operation *dst = dep.getDestination();
320  unsigned latency = *prob.getLatency(*prob.getLinkedOperatorType(src));
321  row[parameter1Column] = -latency; // note the negation
322  if (src != dst) { // note that these coefficients just zero out in self-arcs.
323  row[startTimeLocations[startTimeVariables[src]]] = 1;
324  row[startTimeLocations[startTimeVariables[dst]]] = -1;
325  }
326 }
327 
328 void SimplexSchedulerBase::fillAdditionalConstraintRow(
329  SmallVector<int> &row, Problem::Dependence dep) {
330  // Handling is subclass-specific, so do nothing by default.
331  (void)row;
332  (void)dep;
333 }
334 
335 void SimplexSchedulerBase::buildTableau() {
336  auto &prob = getProblem();
337 
338  // The initial tableau is constructed so that operations' start time variables
339  // are out of basis, whereas all slack variables are in basis. We will number
340  // them accordingly.
341  unsigned var = 0;
342 
343  // Assign column and variable numbers to the operations' start times.
344  for (auto *op : prob.getOperations()) {
345  nonBasicVariables.push_back(var);
346  startTimeVariables[op] = var;
347  startTimeLocations.push_back(firstNonBasicVariableColumn + var);
348  ++var;
349  }
350 
351  // one column for each parameter (1,S,T), and for all operations
352  nColumns = nParameters + nonBasicVariables.size();
353 
354  // Helper to grow both the tableau and the implicit column vector.
355  auto addRow = [&]() -> SmallVector<int> & {
356  implicitBasicVariableColumnVector.push_back(0);
357  return tableau.emplace_back(nColumns, 0);
358  };
359 
360  // Set up the objective rows.
361  nObjectives = 0;
362  bool hasMoreObjectives;
363  do {
364  auto &objRowVec = addRow();
365  hasMoreObjectives = fillObjectiveRow(objRowVec, nObjectives);
366  ++nObjectives;
367  } while (hasMoreObjectives);
368 
369  // Now set up rows/constraints for the dependences.
370  for (auto *op : prob.getOperations()) {
371  for (auto &dep : prob.getDependences(op)) {
372  auto &consRowVec = addRow();
373  fillConstraintRow(consRowVec, dep);
374  basicVariables.push_back(var);
375  ++var;
376  }
377  }
378  for (auto &dep : additionalConstraints) {
379  auto &consRowVec = addRow();
380  fillAdditionalConstraintRow(consRowVec, dep);
381  basicVariables.push_back(var);
382  ++var;
383  }
384 
385  // one row per objective + one row per dependence
386  nRows = tableau.size();
387 }
388 
389 int SimplexSchedulerBase::getParametricConstant(unsigned row) {
390  auto &rowVec = tableau[row];
391  // Compute the dot-product ~B[row] * u between the constant matrix and the
392  // parameter vector.
393  return rowVec[parameter1Column] + rowVec[parameterSColumn] * parameterS +
394  rowVec[parameterTColumn] * parameterT;
395 }
396 
397 SmallVector<int> SimplexSchedulerBase::getObjectiveVector(unsigned column) {
398  SmallVector<int> objVec;
399  // Extract the column vector C^T[column] from the cost matrix.
400  for (unsigned obj = 0; obj < nObjectives; ++obj)
401  objVec.push_back(tableau[obj][column]);
402  return objVec;
403 }
404 
405 std::optional<unsigned> SimplexSchedulerBase::findDualPivotRow() {
406  // Find the first row in which the parametric constant is negative.
407  for (unsigned row = firstConstraintRow; row < nRows; ++row)
408  if (getParametricConstant(row) < 0)
409  return row;
410 
411  return std::nullopt;
412 }
413 
414 std::optional<unsigned>
415 SimplexSchedulerBase::findDualPivotColumn(unsigned pivotRow,
416  bool allowPositive) {
417  SmallVector<int> maxQuot(nObjectives, std::numeric_limits<int>::min());
418  std::optional<unsigned> pivotCol;
419 
420  // Look for non-zero entries in the constraint matrix (~A part of the
421  // tableau). If multiple candidates exist, take the one corresponding to the
422  // lexicographical maximum (over the objective rows) of the quotients:
423  // tableau[<objective row>][col] / pivotCand
424  for (unsigned col = firstNonBasicVariableColumn; col < nColumns; ++col) {
425  if (frozenVariables.count(
426  nonBasicVariables[col - firstNonBasicVariableColumn]))
427  continue;
428 
429  int pivotCand = tableau[pivotRow][col];
430  // Only negative candidates bring us closer to the optimal solution.
431  // However, when freezing variables to a certain value, we accept that the
432  // value of the objective function degrades.
433  if (pivotCand < 0 || (allowPositive && pivotCand > 0)) {
434  // The constraint matrix has only {-1, 0, 1} entries by construction.
435  assert(pivotCand * pivotCand == 1);
436 
437  SmallVector<int> quot;
438  for (unsigned obj = 0; obj < nObjectives; ++obj)
439  quot.push_back(tableau[obj][col] / pivotCand);
440 
441  if (std::lexicographical_compare(maxQuot.begin(), maxQuot.end(),
442  quot.begin(), quot.end())) {
443  maxQuot = quot;
444  pivotCol = col;
445  }
446  }
447  }
448 
449  return pivotCol;
450 }
451 
452 std::optional<unsigned> SimplexSchedulerBase::findPrimalPivotColumn() {
453  // Find the first lexico-negative column in the cost matrix.
454  SmallVector<int> zeroVec(nObjectives, 0);
455  for (unsigned col = firstNonBasicVariableColumn; col < nColumns; ++col) {
456  if (frozenVariables.count(
457  nonBasicVariables[col - firstNonBasicVariableColumn]))
458  continue;
459 
460  SmallVector<int> objVec = getObjectiveVector(col);
461  if (std::lexicographical_compare(objVec.begin(), objVec.end(),
462  zeroVec.begin(), zeroVec.end()))
463  return col;
464  }
465 
466  return std::nullopt;
467 }
468 
469 std::optional<unsigned>
470 SimplexSchedulerBase::findPrimalPivotRow(unsigned pivotColumn) {
471  int minQuot = std::numeric_limits<int>::max();
472  std::optional<unsigned> pivotRow;
473 
474  // Look for positive entries in the constraint matrix (~A part of the
475  // tableau). If multiple candidates exist, take the one corresponding to the
476  // minimum of the quotient:
477  // parametricConstant(row) / pivotCand
478  for (unsigned row = firstConstraintRow; row < nRows; ++row) {
479  int pivotCand = tableau[row][pivotColumn];
480  if (pivotCand > 0) {
481  // The constraint matrix has only {-1, 0, 1} entries by construction.
482  assert(pivotCand == 1);
483  int quot = getParametricConstant(row) / pivotCand;
484  if (quot < minQuot) {
485  minQuot = quot;
486  pivotRow = row;
487  }
488  }
489  }
490 
491  return pivotRow;
492 }
493 
494 void SimplexSchedulerBase::multiplyRow(unsigned row, int factor) {
495  assert(factor != 0);
496  for (unsigned col = 0; col < nColumns; ++col)
497  tableau[row][col] *= factor;
498  // Also multiply the corresponding entry in the temporary column vector.
499  implicitBasicVariableColumnVector[row] *= factor;
500 }
501 
502 void SimplexSchedulerBase::addMultipleOfRow(unsigned sourceRow, int factor,
503  unsigned targetRow) {
504  assert(factor != 0 && sourceRow != targetRow);
505  for (unsigned col = 0; col < nColumns; ++col)
506  tableau[targetRow][col] += tableau[sourceRow][col] * factor;
507  // Again, perform row operation on the temporary column vector as well.
508  implicitBasicVariableColumnVector[targetRow] +=
509  implicitBasicVariableColumnVector[sourceRow] * factor;
510 }
511 
512 /// The pivot operation applies elementary row operations to the tableau in
513 /// order to make the \p pivotColumn (corresponding to a non-basic variable) a
514 /// unit vector (only the \p pivotRow'th entry is 1). Then, a basis exchange is
515 /// performed: the non-basic variable is swapped with the basic variable
516 /// associated with the pivot row.
517 void SimplexSchedulerBase::pivot(unsigned pivotRow, unsigned pivotColumn) {
518  // The implicit columns are part of an identity matrix.
519  implicitBasicVariableColumnVector[pivotRow] = 1;
520 
521  int pivotElem = tableau[pivotRow][pivotColumn];
522  // The constraint matrix has only {-1, 0, 1} entries by construction.
523  assert(pivotElem * pivotElem == 1);
524  // Make `tableau[pivotRow][pivotColumn]` := 1
525  multiplyRow(pivotRow, 1 / pivotElem);
526 
527  for (unsigned row = 0; row < nRows; ++row) {
528  if (row == pivotRow)
529  continue;
530 
531  int elem = tableau[row][pivotColumn];
532  if (elem == 0)
533  continue; // nothing to do
534 
535  // Make `tableau[row][pivotColumn]` := 0.
536  addMultipleOfRow(pivotRow, -elem, row);
537  }
538 
539  // Swap the pivot column with the implicitly constructed column vector.
540  // We really only need to copy in one direction here, as the former pivot
541  // column is a unit vector, which is not stored explicitly.
542  for (unsigned row = 0; row < nRows; ++row) {
543  tableau[row][pivotColumn] = implicitBasicVariableColumnVector[row];
544  implicitBasicVariableColumnVector[row] = 0; // Reset for next pivot step.
545  }
546 
547  // Look up numeric IDs of variables involved in this pivot operation.
548  unsigned &nonBasicVar =
549  nonBasicVariables[pivotColumn - firstNonBasicVariableColumn];
550  unsigned &basicVar = basicVariables[pivotRow - firstConstraintRow];
551 
552  // Keep track of where start time variables are; ignore slack variables.
553  if (nonBasicVar < startTimeLocations.size())
554  startTimeLocations[nonBasicVar] = -pivotRow; // ...going into basis.
555  if (basicVar < startTimeLocations.size())
556  startTimeLocations[basicVar] = pivotColumn; // ...going out of basis.
557 
558  // Record the swap in the variable lists.
559  std::swap(nonBasicVar, basicVar);
560 }
561 
562 LogicalResult SimplexSchedulerBase::solveTableau() {
563  // "Solving" technically means perfoming dual pivot steps until primal
564  // feasibility is reached, i.e. the parametric constants in all constraint
565  // rows are non-negative.
566  while (auto pivotRow = findDualPivotRow()) {
567  // Look for pivot elements.
568  if (auto pivotCol = findDualPivotColumn(*pivotRow)) {
569  pivot(*pivotRow, *pivotCol);
570  continue;
571  }
572 
573  // If we did not find a pivot column, then the entire row contained only
574  // positive entries, and the problem is in principle infeasible. However, if
575  // the entry in the `parameterTColumn` is positive, we can try to make the
576  // LP feasible again by increasing the II.
577  int entry1Col = tableau[*pivotRow][parameter1Column];
578  int entryTCol = tableau[*pivotRow][parameterTColumn];
579  if (entryTCol > 0) {
580  // The negation of `entry1Col` is not in the paper. I think this is an
581  // oversight, because `entry1Col` certainly is negative (otherwise the row
582  // would not have been a valid pivot row), and without the negation, the
583  // new II would be negative.
584  assert(entry1Col < 0);
585  int newParameterT = (-entry1Col - 1) / entryTCol + 1;
586  if (newParameterT > parameterT) {
587  parameterT = newParameterT;
588  LLVM_DEBUG(dbgs() << "Increased II to " << parameterT << '\n');
589  continue;
590  }
591  }
592 
593  // Otherwise, the linear program is infeasible.
594  return failure();
595  }
596 
597  // Optimal solution found!
598  return success();
599 }
600 
601 LogicalResult SimplexSchedulerBase::restoreDualFeasibility() {
602  // Dual feasibility requires that all columns in the cost matrix are
603  // non-lexico-negative. This property may be violated after changing the order
604  // of the objective rows, and can be restored by performing primal pivot
605  // steps.
606  while (auto pivotCol = findPrimalPivotColumn()) {
607  // Look for pivot elements.
608  if (auto pivotRow = findPrimalPivotRow(*pivotCol)) {
609  pivot(*pivotRow, *pivotCol);
610  continue;
611  }
612 
613  // Otherwise, the linear program is unbounded.
614  return failure();
615  }
616 
617  // Optimal solution found!
618  return success();
619 }
620 
621 bool SimplexSchedulerBase::isInBasis(unsigned startTimeVariable) {
622  assert(startTimeVariable < startTimeLocations.size());
623  int loc = startTimeLocations[startTimeVariable];
624  if (-loc >= (int)firstConstraintRow)
625  return true;
626  if (loc >= (int)firstNonBasicVariableColumn)
627  return false;
628  llvm_unreachable("Invalid variable location");
629 }
630 
631 unsigned SimplexSchedulerBase::freeze(unsigned startTimeVariable,
632  unsigned timeStep) {
633  assert(startTimeVariable < startTimeLocations.size());
634  assert(!frozenVariables.count(startTimeVariable));
635 
636  // Mark variable.
637  frozenVariables[startTimeVariable] = timeStep;
638 
639  if (!isInBasis(startTimeVariable))
640  // That's all for non-basic variables.
641  return startTimeLocations[startTimeVariable];
642 
643  // We need to pivot this variable one out of basis.
644  unsigned pivotRow = -startTimeLocations[startTimeVariable];
645 
646  // Here, positive pivot elements can be considered as well, hence finding a
647  // suitable column should not fail.
648  auto pivotCol = findDualPivotColumn(pivotRow, /* allowPositive= */ true);
649  assert(pivotCol);
650 
651  // Perform the exchange.
652  pivot(pivotRow, *pivotCol);
653 
654  // `startTimeVariable` is now represented by `pivotCol`.
655  return *pivotCol;
656 }
657 
658 void SimplexSchedulerBase::translate(unsigned column, int factor1, int factorS,
659  int factorT) {
660  for (unsigned row = 0; row < nRows; ++row) {
661  auto &rowVec = tableau[row];
662  int elem = rowVec[column];
663  if (elem == 0)
664  continue;
665 
666  rowVec[parameter1Column] += -elem * factor1;
667  rowVec[parameterSColumn] += -elem * factorS;
668  rowVec[parameterTColumn] += -elem * factorT;
669  }
670 }
671 
672 LogicalResult SimplexSchedulerBase::scheduleAt(unsigned startTimeVariable,
673  unsigned timeStep) {
674  assert(startTimeVariable < startTimeLocations.size());
675  assert(!frozenVariables.count(startTimeVariable));
676 
677  // Freeze variable and translate its column by parameter S.
678  unsigned frozenCol = freeze(startTimeVariable, timeStep);
679  translate(frozenCol, /* factor1= */ 0, /* factorS= */ 1, /* factorT= */ 0);
680 
681  // Temporarily set S to the desired value, and attempt to solve.
682  parameterS = timeStep;
683  auto solved = solveTableau();
684  parameterS = 0;
685 
686  if (failed(solved)) {
687  // The LP is infeasible with the new constraint. We could try other values
688  // for S, but for now, we just roll back and signal failure to the driver.
689  translate(frozenCol, /* factor1= */ 0, /* factorS= */ -1, /* factorT= */ 0);
690  frozenVariables.erase(startTimeVariable);
691  auto solvedAfterRollback = solveTableau();
692  assert(succeeded(solvedAfterRollback));
693  (void)solvedAfterRollback;
694  return failure();
695  }
696 
697  // Translate S by the other parameter(s). This means setting `factor1` to
698  // `timeStep`.
699  //
700  // This translation does not change the values of the parametric constants,
701  // hence we do not need to solve the tableau again.
702  //
703  // Note: I added a negation of the factors here, which is not mentioned in the
704  // paper's text, but apparently used in the example. Without it, the intended
705  // effect, i.e. making the S-column all-zero again, is not achieved.
706  //
707  // Note 2: For cyclic problems, the paper suggested to perform a modulo
708  // decomposition: S = `factor1` + `factorT` * T, with `factor1` < T.
709  // However, this makes the value baked into the tableau dependent on
710  // `parameterT`, and it is unclear to me how to update it correctly when
711  // changing the II. I found it much more robust to fix the operations to
712  // absolute time steps, and manually shift them by the appropriate amount
713  // whenever the II is incremented (cf. adding `phiJ`, `phiN` in the modulo
714  // scheduler's `scheduleOperation` method).
715  translate(parameterSColumn, /* factor1= */ -timeStep, /* factorS= */ 1,
716  /* factorT= */ 0);
717 
718  return success();
719 }
720 
721 void SimplexSchedulerBase::moveBy(unsigned startTimeVariable, unsigned amount) {
722  assert(startTimeVariable < startTimeLocations.size());
723  assert(frozenVariables.count(startTimeVariable));
724 
725  // Bookkeeping.
726  frozenVariables[startTimeVariable] += amount;
727 
728  // Moving an already frozen variable means translating it by the desired
729  // amount, and solving the tableau to restore primal feasibility...
730  translate(startTimeLocations[startTimeVariable], /* factor1= */ amount,
731  /* factorS= */ 0, /* factorT= */ 0);
732 
733  // ... however, we typically batch-move multiple operations (otherwise, the
734  // tableau may become infeasible on intermediate steps), so actually defer
735  // solving to the caller.
736 }
737 
738 unsigned SimplexSchedulerBase::getStartTime(unsigned startTimeVariable) {
739  assert(startTimeVariable < startTimeLocations.size());
740 
741  if (!isInBasis(startTimeVariable))
742  // Non-basic variables that are not already fixed to a specific time step
743  // are 0 at the end of the simplex algorithm.
744  return frozenVariables.lookup(startTimeVariable);
745 
746  // For the variables currently in basis, we look up the solution in the
747  // tableau.
748  return getParametricConstant(-startTimeLocations[startTimeVariable]);
749 }
750 
751 void SimplexSchedulerBase::dumpTableau() {
752  for (unsigned j = 0; j < nColumns; ++j)
753  dbgs() << "====";
754  dbgs() << "==\n";
755  for (unsigned i = 0; i < nRows; ++i) {
756  if (i == firstConstraintRow) {
757  for (unsigned j = 0; j < nColumns; ++j) {
758  if (j == firstNonBasicVariableColumn)
759  dbgs() << "-+";
760  dbgs() << "----";
761  }
762  dbgs() << '\n';
763  }
764  for (unsigned j = 0; j < nColumns; ++j) {
765  if (j == firstNonBasicVariableColumn)
766  dbgs() << " |";
767  dbgs() << format(" %3d", tableau[i][j]);
768  }
769  if (i >= firstConstraintRow)
770  dbgs() << format(" |< %2d", basicVariables[i - firstConstraintRow]);
771  dbgs() << '\n';
772  }
773  for (unsigned j = 0; j < nColumns; ++j)
774  dbgs() << "====";
775  dbgs() << "==\n";
776  dbgs() << format(" %3d %3d %3d | ", 1, parameterS, parameterT);
777  for (unsigned j = firstNonBasicVariableColumn; j < nColumns; ++j)
778  dbgs() << format(" %2d^",
779  nonBasicVariables[j - firstNonBasicVariableColumn]);
780  dbgs() << '\n';
781 }
782 
783 //===----------------------------------------------------------------------===//
784 // SimplexScheduler
785 //===----------------------------------------------------------------------===//
786 
787 LogicalResult SimplexScheduler::schedule() {
788  if (failed(checkLastOp()))
789  return failure();
790 
791  parameterS = 0;
792  parameterT = 0;
793  buildTableau();
794 
795  LLVM_DEBUG(dbgs() << "Initial tableau:\n"; dumpTableau());
796 
797  if (failed(solveTableau()))
798  return prob.getContainingOp()->emitError() << "problem is infeasible";
799 
800  assert(parameterT == 0);
801  LLVM_DEBUG(
802  dbgs() << "Final tableau:\n"; dumpTableau();
803  dbgs() << "Optimal solution found with start time of last operation = "
804  << -getParametricConstant(0) << '\n');
805 
806  for (auto *op : prob.getOperations())
807  prob.setStartTime(op, getStartTime(startTimeVariables[op]));
808 
809  return success();
810 }
811 
812 //===----------------------------------------------------------------------===//
813 // CyclicSimplexScheduler
814 //===----------------------------------------------------------------------===//
815 
816 void CyclicSimplexScheduler::fillConstraintRow(SmallVector<int> &row,
817  Problem::Dependence dep) {
818  SimplexSchedulerBase::fillConstraintRow(row, dep);
819  if (auto dist = prob.getDistance(dep))
820  row[parameterTColumn] = *dist;
821 }
822 
823 LogicalResult CyclicSimplexScheduler::schedule() {
824  if (failed(checkLastOp()))
825  return failure();
826 
827  parameterS = 0;
828  parameterT = 1;
829  buildTableau();
830 
831  LLVM_DEBUG(dbgs() << "Initial tableau:\n"; dumpTableau());
832 
833  if (failed(solveTableau()))
834  return prob.getContainingOp()->emitError() << "problem is infeasible";
835 
836  LLVM_DEBUG(dbgs() << "Final tableau:\n"; dumpTableau();
837  dbgs() << "Optimal solution found with II = " << parameterT
838  << " and start time of last operation = "
839  << -getParametricConstant(0) << '\n');
840 
841  prob.setInitiationInterval(parameterT);
842  for (auto *op : prob.getOperations())
843  prob.setStartTime(op, getStartTime(startTimeVariables[op]));
844 
845  return success();
846 }
847 
848 //===----------------------------------------------------------------------===//
849 // SharedOperatorsSimplexScheduler
850 //===----------------------------------------------------------------------===//
851 
852 static bool isLimited(Operation *op, SharedOperatorsProblem &prob) {
853  return prob.getLimit(*prob.getLinkedOperatorType(op)).value_or(0) > 0;
854 }
855 
856 LogicalResult SharedOperatorsSimplexScheduler::schedule() {
857  if (failed(checkLastOp()))
858  return failure();
859 
860  parameterS = 0;
861  parameterT = 0;
862  buildTableau();
863 
864  LLVM_DEBUG(dbgs() << "Initial tableau:\n"; dumpTableau());
865 
866  if (failed(solveTableau()))
867  return prob.getContainingOp()->emitError() << "problem is infeasible";
868 
869  LLVM_DEBUG(dbgs() << "After solving resource-free problem:\n"; dumpTableau());
870 
871  // The *heuristic* part of this scheduler starts here:
872  // We will now *choose* start times for operations using a shared operator
873  // type, in a way that respects the allocation limits, and consecutively solve
874  // the LP with these added constraints. The individual LPs are still solved to
875  // optimality (meaning: the start times of the "last" operation is still
876  // optimal w.r.t. the already fixed operations), however the heuristic choice
877  // means we cannot guarantee the optimality for the overall problem.
878 
879  // Determine which operations are subject to resource constraints.
880  auto &ops = prob.getOperations();
881  SmallVector<Operation *> limitedOps;
882  for (auto *op : ops)
883  if (isLimited(op, prob))
884  limitedOps.push_back(op);
885 
886  // Build a priority list of the limited operations.
887  //
888  // We sort by the resource-free start times to produce a topological order of
889  // the operations. Better priority functions are known, but require computing
890  // additional properties, e.g. ASAP and ALAP times for mobility, or graph
891  // analysis for height. Assigning operators (=resources) in this order at
892  // least ensures that the (acyclic!) problem remains feasible throughout the
893  // process.
894  //
895  // TODO: Implement more sophisticated priority function.
896  std::stable_sort(limitedOps.begin(), limitedOps.end(),
897  [&](Operation *a, Operation *b) {
898  return getStartTime(startTimeVariables[a]) <
899  getStartTime(startTimeVariables[b]);
900  });
901 
902  // Store the number of operations using an operator type in a particular time
903  // step.
905  reservationTable;
906 
907  for (auto *op : limitedOps) {
908  auto opr = *prob.getLinkedOperatorType(op);
909  unsigned limit = prob.getLimit(opr).value_or(0);
910  assert(limit > 0);
911 
912  // Find the first time step (beginning at the current start time in the
913  // partial schedule) in which an operator instance is available.
914  unsigned startTimeVar = startTimeVariables[op];
915  unsigned candTime = getStartTime(startTimeVar);
916  while (reservationTable[opr].lookup(candTime) == limit)
917  ++candTime;
918 
919  // Fix the start time. As explained above, this cannot make the problem
920  // infeasible.
921  auto fixed = scheduleAt(startTimeVar, candTime);
922  assert(succeeded(fixed));
923  (void)fixed;
924 
925  // Record the operator use.
926  ++reservationTable[opr][candTime];
927 
928  LLVM_DEBUG(dbgs() << "After scheduling " << startTimeVar
929  << " to t=" << candTime << ":\n";
930  dumpTableau());
931  }
932 
933  assert(parameterT == 0);
934  LLVM_DEBUG(
935  dbgs() << "Final tableau:\n"; dumpTableau();
936  dbgs() << "Feasible solution found with start time of last operation = "
937  << -getParametricConstant(0) << '\n');
938 
939  for (auto *op : ops)
940  prob.setStartTime(op, getStartTime(startTimeVariables[op]));
941 
942  return success();
943 }
944 
945 //===----------------------------------------------------------------------===//
946 // ModuloSimplexScheduler
947 //===----------------------------------------------------------------------===//
948 
949 LogicalResult ModuloSimplexScheduler::checkLastOp() {
950  auto *contOp = prob.getContainingOp();
951  if (!prob.hasOperation(lastOp))
952  return contOp->emitError("problem does not include last operation");
953 
954  // Determine which operations have no outgoing *intra*-iteration dependences.
955  auto &ops = prob.getOperations();
956  DenseSet<Operation *> sinks(ops.begin(), ops.end());
957  for (auto *op : ops)
958  for (auto &dep : prob.getDependences(op))
959  if (prob.getDistance(dep).value_or(0) == 0)
960  sinks.erase(dep.getSource());
961 
962  if (!sinks.contains(lastOp))
963  return contOp->emitError("last operation is not a sink");
964  if (sinks.size() > 1)
965  return contOp->emitError("multiple sinks detected");
966 
967  return success();
968 }
969 
970 LogicalResult ModuloSimplexScheduler::MRT::enter(Operation *op,
971  unsigned timeStep) {
972  auto opr = *sched.prob.getLinkedOperatorType(op);
973  auto lim = *sched.prob.getLimit(opr);
974  assert(lim > 0);
975 
976  auto &revTab = reverseTables[opr];
977  assert(!revTab.count(op));
978 
979  unsigned slot = timeStep % sched.parameterT;
980  auto &cell = tables[opr][slot];
981  if (cell.size() < lim) {
982  cell.insert(op);
983  revTab[op] = slot;
984  return success();
985  }
986  return failure();
987 }
988 
989 void ModuloSimplexScheduler::MRT::release(Operation *op) {
990  auto opr = *sched.prob.getLinkedOperatorType(op);
991  auto &revTab = reverseTables[opr];
992  auto it = revTab.find(op);
993  assert(it != revTab.end());
994  tables[opr][it->second].erase(op);
995  revTab.erase(it);
996 }
997 
998 bool ModuloSimplexScheduler::fillObjectiveRow(SmallVector<int> &row,
999  unsigned obj) {
1000  switch (obj) {
1001  case OBJ_LATENCY:
1002  // Minimize start time of user-specified last operation.
1003  row[startTimeLocations[startTimeVariables[lastOp]]] = 1;
1004  return true;
1005  case OBJ_AXAP:
1006  // Minimize sum of start times of all-but-the-last operation.
1007  for (auto *op : getProblem().getOperations())
1008  if (op != lastOp)
1009  row[startTimeLocations[startTimeVariables[op]]] = 1;
1010  return false;
1011  default:
1012  llvm_unreachable("Unsupported objective requested");
1013  }
1014 }
1015 
1016 void ModuloSimplexScheduler::updateMargins() {
1017  // Assumption: current secondary objective is "ASAP".
1018  // Negate the objective row once to effectively maximize the sum of start
1019  // times, which yields the "ALAP" times after solving the tableau. Then,
1020  // negate it again to restore the "ASAP" objective, and store these times as
1021  // well.
1022  for (auto *axapTimes : {&alapTimes, &asapTimes}) {
1023  multiplyRow(OBJ_AXAP, -1);
1024  // This should not fail for a feasible tableau.
1025  auto dualFeasRestored = restoreDualFeasibility();
1026  auto solved = solveTableau();
1027  assert(succeeded(dualFeasRestored) && succeeded(solved));
1028  (void)dualFeasRestored, (void)solved;
1029 
1030  for (unsigned stv = 0; stv < startTimeLocations.size(); ++stv)
1031  (*axapTimes)[stv] = getStartTime(stv);
1032  }
1033 }
1034 
1035 void ModuloSimplexScheduler::scheduleOperation(Operation *n) {
1036  auto oprN = *prob.getLinkedOperatorType(n);
1037  unsigned stvN = startTimeVariables[n];
1038 
1039  // Get current state of the LP. We'll try to schedule at its current time step
1040  // in the partial solution, and the II-1 following time steps. Scheduling the
1041  // op to a later time step may increase the overall latency, however, as long
1042  // as the solution is still feasible, we prefer that over incrementing the II
1043  // to resolve resource conflicts.
1044  unsigned stN = getStartTime(stvN);
1045  unsigned ubN = stN + parameterT - 1;
1046 
1047  LLVM_DEBUG(dbgs() << "Attempting to schedule in [" << stN << ", " << ubN
1048  << "]: " << *n << '\n');
1049 
1050  for (unsigned ct = stN; ct <= ubN; ++ct)
1051  if (succeeded(mrt.enter(n, ct))) {
1052  auto fixedN = scheduleAt(stvN, ct);
1053  if (succeeded(fixedN)) {
1054  LLVM_DEBUG(dbgs() << "Success at t=" << ct << " " << *n << '\n');
1055  return;
1056  }
1057  // Problem became infeasible with `n` at `ct`, roll back the MRT
1058  // assignment. Also, no later time can be feasible, so stop the search
1059  // here.
1060  mrt.release(n);
1061  break;
1062  }
1063 
1064  // As a last resort, increase II to make room for the op. De Dinechin's
1065  // Theorem 1 lays out conditions/guidelines to transform the current partial
1066  // schedule for II to a valid one for a larger II'.
1067 
1068  LLVM_DEBUG(dbgs() << "Incrementing II to " << (parameterT + 1)
1069  << " to resolve resource conflict for " << *n << '\n');
1070 
1071  // Note that the approach below is much simpler than in the paper
1072  // because of the fully-pipelined operators. In our case, it's always
1073  // sufficient to increment the II by one.
1074 
1075  // Decompose start time.
1076  unsigned phiN = stN / parameterT;
1077  unsigned tauN = stN % parameterT;
1078 
1079  // Keep track whether the following moves free at least one operator
1080  // instance in the slot desired by the current op - then it can stay there.
1081  unsigned deltaN = 1;
1082 
1083  // We're going to revisit the current partial schedule.
1084  SmallVector<Operation *> moved;
1085  for (Operation *j : scheduled) {
1086  auto oprJ = *prob.getLinkedOperatorType(j);
1087  unsigned stvJ = startTimeVariables[j];
1088  unsigned stJ = getStartTime(stvJ);
1089  unsigned phiJ = stJ / parameterT;
1090  unsigned tauJ = stJ % parameterT;
1091  unsigned deltaJ = 0;
1092 
1093  if (oprN == oprJ) {
1094  // To actually resolve the resource conflicts, we will move operations
1095  // that are "preceded" (cf. de Dinechin's ≺ relation) one slot to the
1096  // right.
1097  if (tauN < tauJ || (tauN == tauJ && phiN > phiJ) ||
1098  (tauN == tauJ && phiN == phiJ && stvN < stvJ)) {
1099  // TODO: Replace the last condition with a proper graph analysis.
1100 
1101  deltaJ = 1;
1102  moved.push_back(j);
1103  if (tauN == tauJ)
1104  deltaN = 0;
1105  }
1106  }
1107 
1108  // Move operation.
1109  //
1110  // In order to keep the op in its current MRT slot `tauJ` after incrementing
1111  // the II, we add `phiJ`:
1112  // stJ + phiJ = (phiJ * parameterT + tauJ) + phiJ
1113  // = phiJ * (parameterT + 1) + tauJ
1114  //
1115  // Shifting an additional `deltaJ` time steps then moves the op to a
1116  // different MRT slot, in order to make room for the operation that caused
1117  // the resource conflict.
1118  moveBy(stvJ, phiJ + deltaJ);
1119  }
1120 
1121  // Finally, increment the II and solve to apply the moves.
1122  ++parameterT;
1123  auto solved = solveTableau();
1124  assert(succeeded(solved));
1125  (void)solved;
1126 
1127  // Re-enter moved operations into their new slots.
1128  for (auto *m : moved)
1129  mrt.release(m);
1130  for (auto *m : moved) {
1131  auto enteredM = mrt.enter(m, getStartTime(startTimeVariables[m]));
1132  assert(succeeded(enteredM));
1133  (void)enteredM;
1134  }
1135 
1136  // Finally, schedule the operation. Again, adding `phiN` accounts for the
1137  // implicit shift caused by incrementing the II.
1138  auto fixedN = scheduleAt(stvN, stN + phiN + deltaN);
1139  auto enteredN = mrt.enter(n, tauN + deltaN);
1140  assert(succeeded(fixedN) && succeeded(enteredN));
1141  (void)fixedN, (void)enteredN;
1142 }
1143 
1144 unsigned ModuloSimplexScheduler::computeResMinII() {
1145  unsigned resMinII = 1;
1147  for (auto *op : prob.getOperations())
1148  if (isLimited(op, prob))
1149  ++uses[*prob.getLinkedOperatorType(op)];
1150 
1151  for (auto pair : uses)
1152  resMinII = std::max(
1153  resMinII, (unsigned)ceil(pair.second / *prob.getLimit(pair.first)));
1154 
1155  return resMinII;
1156 }
1157 
1158 LogicalResult ModuloSimplexScheduler::schedule() {
1159  if (failed(checkLastOp()))
1160  return failure();
1161 
1162  parameterS = 0;
1163  parameterT = computeResMinII();
1164  LLVM_DEBUG(dbgs() << "ResMinII = " << parameterT << "\n");
1165  buildTableau();
1166  asapTimes.resize(startTimeLocations.size());
1167  alapTimes.resize(startTimeLocations.size());
1168 
1169  LLVM_DEBUG(dbgs() << "Initial tableau:\n"; dumpTableau());
1170 
1171  if (failed(solveTableau()))
1172  return prob.getContainingOp()->emitError() << "problem is infeasible";
1173 
1174  // Determine which operations are subject to resource constraints.
1175  auto &ops = prob.getOperations();
1176  for (auto *op : ops)
1177  if (isLimited(op, prob))
1178  unscheduled.push_back(op);
1179 
1180  // Main loop: Iteratively fix limited operations to time steps.
1181  while (!unscheduled.empty()) {
1182  // Update ASAP/ALAP times.
1183  updateMargins();
1184 
1185  // Heuristically (here: least amount of slack) pick the next operation to
1186  // schedule.
1187  auto *opIt =
1188  std::min_element(unscheduled.begin(), unscheduled.end(),
1189  [&](Operation *opA, Operation *opB) {
1190  auto stvA = startTimeVariables[opA];
1191  auto stvB = startTimeVariables[opB];
1192  auto slackA = alapTimes[stvA] - asapTimes[stvA];
1193  auto slackB = alapTimes[stvB] - asapTimes[stvB];
1194  return slackA < slackB;
1195  });
1196  Operation *op = *opIt;
1197  unscheduled.erase(opIt);
1198 
1199  scheduleOperation(op);
1200  scheduled.push_back(op);
1201  }
1202 
1203  LLVM_DEBUG(dbgs() << "Final tableau:\n"; dumpTableau();
1204  dbgs() << "Solution found with II = " << parameterT
1205  << " and start time of last operation = "
1206  << -getParametricConstant(0) << '\n');
1207 
1208  prob.setInitiationInterval(parameterT);
1209  for (auto *op : ops)
1210  prob.setStartTime(op, getStartTime(startTimeVariables[op]));
1211 
1212  return success();
1213 }
1214 
1215 //===----------------------------------------------------------------------===//
1216 // ChainingSimplexScheduler
1217 //===----------------------------------------------------------------------===//
1218 
1219 void ChainingSimplexScheduler::fillAdditionalConstraintRow(
1220  SmallVector<int> &row, Problem::Dependence dep) {
1221  fillConstraintRow(row, dep);
1222  // One _extra_ time step breaks the chain (note that the latency is negative
1223  // in the tableau).
1224  row[parameter1Column] -= 1;
1225 }
1226 
1227 LogicalResult ChainingSimplexScheduler::schedule() {
1228  if (failed(checkLastOp()) || failed(computeChainBreakingDependences(
1229  prob, cycleTime, additionalConstraints)))
1230  return failure();
1231 
1232  parameterS = 0;
1233  parameterT = 0;
1234  buildTableau();
1235 
1236  LLVM_DEBUG(dbgs() << "Initial tableau:\n"; dumpTableau());
1237 
1238  if (failed(solveTableau()))
1239  return prob.getContainingOp()->emitError() << "problem is infeasible";
1240 
1241  assert(parameterT == 0);
1242  LLVM_DEBUG(
1243  dbgs() << "Final tableau:\n"; dumpTableau();
1244  dbgs() << "Optimal solution found with start time of last operation = "
1245  << -getParametricConstant(0) << '\n');
1246 
1247  for (auto *op : prob.getOperations())
1248  prob.setStartTime(op, getStartTime(startTimeVariables[op]));
1249 
1250  auto filledIn = computeStartTimesInCycle(prob);
1251  assert(succeeded(filledIn)); // Problem is known to be acyclic at this point.
1252  (void)filledIn;
1253 
1254  return success();
1255 }
1256 
1257 //===----------------------------------------------------------------------===//
1258 // Public API
1259 //===----------------------------------------------------------------------===//
1260 
1261 LogicalResult scheduling::scheduleSimplex(Problem &prob, Operation *lastOp) {
1262  SimplexScheduler simplex(prob, lastOp);
1263  return simplex.schedule();
1264 }
1265 
1267  Operation *lastOp) {
1268  CyclicSimplexScheduler simplex(prob, lastOp);
1269  return simplex.schedule();
1270 }
1271 
1273  Operation *lastOp) {
1274  SharedOperatorsSimplexScheduler simplex(prob, lastOp);
1275  return simplex.schedule();
1276 }
1277 
1279  Operation *lastOp) {
1280  ModuloSimplexScheduler simplex(prob, lastOp);
1281  return simplex.schedule();
1282 }
1283 
1285  Operation *lastOp, float cycleTime) {
1286  ChainingSimplexScheduler simplex(prob, lastOp, cycleTime);
1287  return simplex.schedule();
1288 }
static bool isLimited(Operation *op, SharedOperatorsProblem &prob)
This class models the accumulation of physical propagation delays on combinational paths along SSA de...
Definition: Problems.h:340
This class models a cyclic scheduling problem.
Definition: Problems.h:292
This class models the modulo scheduling problem as the composition of the cyclic problem and the reso...
Definition: Problems.h:446
This class models the most basic scheduling problem.
Definition: Problems.h:87
std::optional< OperatorType > getLinkedOperatorType(Operation *op)
The linked operator type provides the runtime characteristics for op.
Definition: Problems.h:202
This class models a resource-constrained scheduling problem.
Definition: Problems.h:408
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
A wrapper class to uniformly handle def-use and auxiliary dependence edges.
Operation * getDestination() const
Return the destination of the dependence.
Definition: Problems.cpp:418
Operation * getSource() const
Return the source of the dependence.
Definition: Problems.cpp:414
LogicalResult computeChainBreakingDependences(ChainingProblem &prob, float cycleTime, SmallVectorImpl< Problem::Dependence > &result)
Analyse combinational chains in prob's dependence graph and determine pairs of operations that must b...
LogicalResult scheduleSimplex(Problem &prob, Operation *lastOp)
Solve the basic problem using linear programming and a handwritten implementation of the simplex algo...
LogicalResult computeStartTimesInCycle(ChainingProblem &prob)
Assuming prob is scheduled and contains (integer) start times, this method fills in the start times i...
This file defines an intermediate representation for circuits acting as an abstraction for constraint...
mlir::raw_indented_ostream & dbgs()
Definition: Utility.h:28