CIRCT  19.0.0git
Schedule.cpp
Go to the documentation of this file.
1 //===- Schedule.cpp - Schedule pass -----------------------------*- 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 // Implements the Schedule pass.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "PassDetails.h"
14 
16 
17 #include "llvm/ADT/StringExtras.h"
18 
19 using namespace circt;
20 using namespace scheduling;
21 using namespace ssp;
22 
23 //===----------------------------------------------------------------------===//
24 // Helpers
25 //===----------------------------------------------------------------------===//
26 
27 // Determine "last" operation, i.e. the one whose start time we are supposed to
28 // minimize.
29 static OperationOp getLastOp(InstanceOp instOp, StringRef options) {
30  StringRef lastOpName = "";
31  for (StringRef option : llvm::split(options, ',')) {
32  if (option.consume_front("last-op-name=")) {
33  lastOpName = option;
34  break;
35  }
36  }
37 
38  auto graphOp = instOp.getDependenceGraph();
39  if (lastOpName.empty() && !graphOp.getBodyBlock()->empty())
40  return cast<OperationOp>(graphOp.getBodyBlock()->back());
41  return graphOp.lookupSymbol<OperationOp>(lastOpName);
42 }
43 
44 // Determine desired cycle time (only relevant for `ChainingProblem` instances).
45 static std::optional<float> getCycleTime(StringRef options) {
46  for (StringRef option : llvm::split(options, ',')) {
47  if (option.consume_front("cycle-time="))
48  return std::stof(option.str());
49  }
50  return std::nullopt;
51 }
52 
53 //===----------------------------------------------------------------------===//
54 // ASAP scheduler
55 //===----------------------------------------------------------------------===//
56 
57 static InstanceOp scheduleWithASAP(InstanceOp instOp, OpBuilder &builder) {
58  auto problemName = instOp.getProblemName();
59  if (!problemName.equals("Problem")) {
60  llvm::errs() << "ssp-schedule: Unsupported problem '" << problemName
61  << "' for ASAP scheduler\n";
62  return {};
63  }
64 
65  auto prob = loadProblem<Problem>(instOp);
66  if (failed(prob.check()) || failed(scheduling::scheduleASAP(prob)) ||
67  failed(prob.verify()))
68  return {};
69  return saveProblem(prob, builder);
70 }
71 
72 //===----------------------------------------------------------------------===//
73 // Simplex schedulers
74 //===----------------------------------------------------------------------===//
75 
76 template <typename ProblemT>
77 static InstanceOp scheduleProblemTWithSimplex(InstanceOp instOp,
78  Operation *lastOp,
79  OpBuilder &builder) {
80  auto prob = loadProblem<ProblemT>(instOp);
81  if (failed(prob.check()) ||
82  failed(scheduling::scheduleSimplex(prob, lastOp)) ||
83  failed(prob.verify()))
84  return {};
85  return saveProblem(prob, builder);
86 }
87 
88 static InstanceOp scheduleChainingProblemWithSimplex(InstanceOp instOp,
89  Operation *lastOp,
90  float cycleTime,
91  OpBuilder &builder) {
92  auto prob = loadProblem<scheduling::ChainingProblem>(instOp);
93  if (failed(prob.check()) ||
94  failed(scheduling::scheduleSimplex(prob, lastOp, cycleTime)) ||
95  failed(prob.verify()))
96  return {};
97  return saveProblem(prob, builder);
98 }
99 
100 static InstanceOp scheduleChainingCyclicProblemWithSimplex(InstanceOp instOp,
101  Operation *lastOp,
102  float cycleTime,
103  OpBuilder &builder) {
104  auto prob = loadProblem<scheduling::ChainingCyclicProblem>(instOp);
105  if (failed(prob.check()) ||
106  failed(scheduling::scheduleSimplex(prob, lastOp, cycleTime)) ||
107  failed(prob.verify()))
108  return {};
109  return saveProblem(prob, builder);
110 }
111 
112 static InstanceOp scheduleWithSimplex(InstanceOp instOp, StringRef options,
113  OpBuilder &builder) {
114  auto lastOp = getLastOp(instOp, options);
115  if (!lastOp) {
116  auto instName = instOp.getSymName().value_or("unnamed");
117  llvm::errs()
118  << "ssp-schedule: Ambiguous objective for simplex scheduler: Instance '"
119  << instName << "' has no designated last operation\n";
120  return {};
121  }
122 
123  auto problemName = instOp.getProblemName();
124  if (problemName.equals("Problem"))
125  return scheduleProblemTWithSimplex<Problem>(instOp, lastOp, builder);
126  if (problemName.equals("CyclicProblem"))
127  return scheduleProblemTWithSimplex<CyclicProblem>(instOp, lastOp, builder);
128  if (problemName.equals("SharedOperatorsProblem"))
129  return scheduleProblemTWithSimplex<SharedOperatorsProblem>(instOp, lastOp,
130  builder);
131  if (problemName.equals("ModuloProblem"))
132  return scheduleProblemTWithSimplex<ModuloProblem>(instOp, lastOp, builder);
133  if (problemName.equals("ChainingProblem")) {
134  if (auto cycleTime = getCycleTime(options))
135  return scheduleChainingProblemWithSimplex(instOp, lastOp,
136  cycleTime.value(), builder);
137  llvm::errs() << "ssp-schedule: Missing option 'cycle-time' for "
138  "ChainingProblem simplex scheduler\n";
139  return {};
140  }
141  if (problemName.equals("ChainingCyclicProblem")) {
142  if (auto cycleTime = getCycleTime(options))
144  instOp, lastOp, cycleTime.value(), builder);
145  llvm::errs() << "ssp-schedule: Missing option 'cycle-time' for "
146  "ChainingCyclicProblem simplex scheduler\n";
147  return {};
148  }
149 
150  llvm::errs() << "ssp-schedule: Unsupported problem '" << problemName
151  << "' for simplex scheduler\n";
152  return {};
153 }
154 
155 #ifdef SCHEDULING_OR_TOOLS
156 
157 //===----------------------------------------------------------------------===//
158 // LP schedulers (require OR-Tools)
159 //===----------------------------------------------------------------------===//
160 
161 template <typename ProblemT>
162 static InstanceOp scheduleProblemTWithLP(InstanceOp instOp, Operation *lastOp,
163  OpBuilder &builder) {
164  auto prob = loadProblem<ProblemT>(instOp);
165  if (failed(prob.check()) || failed(scheduling::scheduleLP(prob, lastOp)) ||
166  failed(prob.verify()))
167  return {};
168  return saveProblem(prob, builder);
169 }
170 
171 static InstanceOp scheduleWithLP(InstanceOp instOp, StringRef options,
172  OpBuilder &builder) {
173  auto lastOp = getLastOp(instOp, options);
174  if (!lastOp) {
175  auto instName = instOp.getSymName().value_or("unnamed");
176  llvm::errs()
177  << "ssp-schedule: Ambiguous objective for LP scheduler: Instance '"
178  << instName << "' has no designated last operation\n";
179  return {};
180  }
181 
182  auto problemName = instOp.getProblemName();
183  if (problemName.equals("Problem"))
184  return scheduleProblemTWithLP<Problem>(instOp, lastOp, builder);
185  if (problemName.equals("CyclicProblem"))
186  return scheduleProblemTWithLP<CyclicProblem>(instOp, lastOp, builder);
187 
188  llvm::errs() << "ssp-schedule: Unsupported problem '" << problemName
189  << "' for LP scheduler\n";
190  return {};
191 }
192 
193 //===----------------------------------------------------------------------===//
194 // CPSAT scheduler (requires OR-Tools)
195 //===----------------------------------------------------------------------===//
196 
197 static InstanceOp scheduleWithCPSAT(InstanceOp instOp, StringRef options,
198  OpBuilder &builder) {
199  auto lastOp = getLastOp(instOp, options);
200  if (!lastOp) {
201  auto instName = instOp.getSymName().value_or("unnamed");
202  llvm::errs()
203  << "ssp-schedule: Ambiguous objective for CPSAT scheduler: Instance '"
204  << instName << "' has no designated last operation\n";
205  return {};
206  }
207 
208  auto problemName = instOp.getProblemName();
209  if (!problemName.equals("SharedOperatorsProblem")) {
210  llvm::errs() << "ssp-schedule: Unsupported problem '" << problemName
211  << "' for CPSAT scheduler\n";
212  return {};
213  }
214 
215  auto prob = loadProblem<SharedOperatorsProblem>(instOp);
216  if (failed(prob.check()) || failed(scheduling::scheduleCPSAT(prob, lastOp)) ||
217  failed(prob.verify()))
218  return {};
219  return saveProblem(prob, builder);
220 }
221 
222 #endif // SCHEDULING_OR_TOOLS
223 
224 //===----------------------------------------------------------------------===//
225 // Algorithm dispatcher
226 //===----------------------------------------------------------------------===//
227 
228 static InstanceOp scheduleWith(InstanceOp instOp, StringRef scheduler,
229  StringRef options, OpBuilder &builder) {
230  if (scheduler.empty() || scheduler.equals("simplex"))
231  return scheduleWithSimplex(instOp, options, builder);
232  if (scheduler.equals("asap"))
233  return scheduleWithASAP(instOp, builder);
234 #ifdef SCHEDULING_OR_TOOLS
235  if (scheduler.equals("lp"))
236  return scheduleWithLP(instOp, options, builder);
237  if (scheduler.equals("cpsat"))
238  return scheduleWithCPSAT(instOp, options, builder);
239 #endif
240 
241  llvm::errs() << "ssp-schedule: Unsupported scheduler '" << scheduler
242  << "' requested\n";
243  return {};
244 }
245 
246 //===----------------------------------------------------------------------===//
247 // Pass implementation
248 //===----------------------------------------------------------------------===//
249 
250 namespace {
251 struct SchedulePass : public ScheduleBase<SchedulePass> {
252  void runOnOperation() override;
253 };
254 } // end anonymous namespace
255 
256 void SchedulePass::runOnOperation() {
257  auto moduleOp = getOperation();
258 
259  SmallVector<InstanceOp> instanceOps;
260  OpBuilder builder(&getContext());
261  for (auto instOp : moduleOp.getOps<InstanceOp>()) {
262  builder.setInsertionPoint(instOp);
263  auto scheduledOp = scheduleWith(instOp, scheduler.getValue(),
264  schedulerOptions.getValue(), builder);
265  if (!scheduledOp)
266  return signalPassFailure();
267  instanceOps.push_back(instOp);
268  }
269 
270  llvm::for_each(instanceOps, [](InstanceOp op) { op.erase(); });
271 }
272 
273 std::unique_ptr<mlir::Pass> circt::ssp::createSchedulePass() {
274  return std::make_unique<SchedulePass>();
275 }
Builder builder
static InstanceOp scheduleProblemTWithSimplex(InstanceOp instOp, Operation *lastOp, OpBuilder &builder)
Definition: Schedule.cpp:77
static InstanceOp scheduleWithASAP(InstanceOp instOp, OpBuilder &builder)
Definition: Schedule.cpp:57
static OperationOp getLastOp(InstanceOp instOp, StringRef options)
Definition: Schedule.cpp:29
static std::optional< float > getCycleTime(StringRef options)
Definition: Schedule.cpp:45
static InstanceOp scheduleWithSimplex(InstanceOp instOp, StringRef options, OpBuilder &builder)
Definition: Schedule.cpp:112
static InstanceOp scheduleChainingCyclicProblemWithSimplex(InstanceOp instOp, Operation *lastOp, float cycleTime, OpBuilder &builder)
Definition: Schedule.cpp:100
static InstanceOp scheduleChainingProblemWithSimplex(InstanceOp instOp, Operation *lastOp, float cycleTime, OpBuilder &builder)
Definition: Schedule.cpp:88
static InstanceOp scheduleWith(InstanceOp instOp, StringRef scheduler, StringRef options, OpBuilder &builder)
Definition: Schedule.cpp:228
LogicalResult scheduleLP(Problem &prob, Operation *lastOp)
Solve the basic problem using linear programming and an external LP solver.
LogicalResult scheduleCPSAT(SharedOperatorsProblem &prob, Operation *lastOp)
Solve the acyclic problem with shared operators using constraint programming and an external SAT solv...
LogicalResult scheduleSimplex(Problem &prob, Operation *lastOp)
Solve the basic problem using linear programming and a handwritten implementation of the simplex algo...
LogicalResult scheduleASAP(Problem &prob)
This is a simple list scheduler for solving the basic scheduling problem.
std::unique_ptr< mlir::Pass > createSchedulePass()
Definition: Schedule.cpp:273
InstanceOp saveProblem(ProblemT &prob, std::tuple< OperationPropertyTs... > opProps, std::tuple< OperatorTypePropertyTs... > oprProps, std::tuple< DependencePropertyTs... > depProps, std::tuple< InstancePropertyTs... > instProps, OpBuilder &builder)
Construct an InstanceOp from a given ProblemT instance, and create/attach attributes of the given cla...
Definition: Utilities.h:320
This file defines an intermediate representation for circuits acting as an abstraction for constraint...
Definition: DebugAnalysis.h:21
mlir::raw_indented_ostream & errs()
Definition: Utility.h:33