CIRCT  18.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 scheduleWithSimplex(InstanceOp instOp, StringRef options,
101  OpBuilder &builder) {
102  auto lastOp = getLastOp(instOp, options);
103  if (!lastOp) {
104  auto instName = instOp.getSymName().value_or("unnamed");
105  llvm::errs()
106  << "ssp-schedule: Ambiguous objective for simplex scheduler: Instance '"
107  << instName << "' has no designated last operation\n";
108  return {};
109  }
110 
111  auto problemName = instOp.getProblemName();
112  if (problemName.equals("Problem"))
113  return scheduleProblemTWithSimplex<Problem>(instOp, lastOp, builder);
114  if (problemName.equals("CyclicProblem"))
115  return scheduleProblemTWithSimplex<CyclicProblem>(instOp, lastOp, builder);
116  if (problemName.equals("SharedOperatorsProblem"))
117  return scheduleProblemTWithSimplex<SharedOperatorsProblem>(instOp, lastOp,
118  builder);
119  if (problemName.equals("ModuloProblem"))
120  return scheduleProblemTWithSimplex<ModuloProblem>(instOp, lastOp, builder);
121  if (problemName.equals("ChainingProblem")) {
122  if (auto cycleTime = getCycleTime(options))
123  return scheduleChainingProblemWithSimplex(instOp, lastOp,
124  cycleTime.value(), builder);
125  llvm::errs() << "ssp-schedule: Missing option 'cycle-time' for "
126  "ChainingProblem simplex scheduler\n";
127  return {};
128  }
129 
130  llvm::errs() << "ssp-schedule: Unsupported problem '" << problemName
131  << "' for simplex scheduler\n";
132  return {};
133 }
134 
135 #ifdef SCHEDULING_OR_TOOLS
136 
137 //===----------------------------------------------------------------------===//
138 // LP schedulers (require OR-Tools)
139 //===----------------------------------------------------------------------===//
140 
141 template <typename ProblemT>
142 static InstanceOp scheduleProblemTWithLP(InstanceOp instOp, Operation *lastOp,
143  OpBuilder &builder) {
144  auto prob = loadProblem<ProblemT>(instOp);
145  if (failed(prob.check()) || failed(scheduling::scheduleLP(prob, lastOp)) ||
146  failed(prob.verify()))
147  return {};
148  return saveProblem(prob, builder);
149 }
150 
151 static InstanceOp scheduleWithLP(InstanceOp instOp, StringRef options,
152  OpBuilder &builder) {
153  auto lastOp = getLastOp(instOp, options);
154  if (!lastOp) {
155  auto instName = instOp.getSymName().value_or("unnamed");
156  llvm::errs()
157  << "ssp-schedule: Ambiguous objective for LP scheduler: Instance '"
158  << instName << "' has no designated last operation\n";
159  return {};
160  }
161 
162  auto problemName = instOp.getProblemName();
163  if (problemName.equals("Problem"))
164  return scheduleProblemTWithLP<Problem>(instOp, lastOp, builder);
165  if (problemName.equals("CyclicProblem"))
166  return scheduleProblemTWithLP<CyclicProblem>(instOp, lastOp, builder);
167 
168  llvm::errs() << "ssp-schedule: Unsupported problem '" << problemName
169  << "' for LP scheduler\n";
170  return {};
171 }
172 
173 //===----------------------------------------------------------------------===//
174 // CPSAT scheduler (requires OR-Tools)
175 //===----------------------------------------------------------------------===//
176 
177 static InstanceOp scheduleWithCPSAT(InstanceOp instOp, StringRef options,
178  OpBuilder &builder) {
179  auto lastOp = getLastOp(instOp, options);
180  if (!lastOp) {
181  auto instName = instOp.getSymName().value_or("unnamed");
182  llvm::errs()
183  << "ssp-schedule: Ambiguous objective for CPSAT scheduler: Instance '"
184  << instName << "' has no designated last operation\n";
185  return {};
186  }
187 
188  auto problemName = instOp.getProblemName();
189  if (!problemName.equals("SharedOperatorsProblem")) {
190  llvm::errs() << "ssp-schedule: Unsupported problem '" << problemName
191  << "' for CPSAT scheduler\n";
192  return {};
193  }
194 
195  auto prob = loadProblem<SharedOperatorsProblem>(instOp);
196  if (failed(prob.check()) || failed(scheduling::scheduleCPSAT(prob, lastOp)) ||
197  failed(prob.verify()))
198  return {};
199  return saveProblem(prob, builder);
200 }
201 
202 #endif // SCHEDULING_OR_TOOLS
203 
204 //===----------------------------------------------------------------------===//
205 // Algorithm dispatcher
206 //===----------------------------------------------------------------------===//
207 
208 static InstanceOp scheduleWith(InstanceOp instOp, StringRef scheduler,
209  StringRef options, OpBuilder &builder) {
210  if (scheduler.empty() || scheduler.equals("simplex"))
211  return scheduleWithSimplex(instOp, options, builder);
212  if (scheduler.equals("asap"))
213  return scheduleWithASAP(instOp, builder);
214 #ifdef SCHEDULING_OR_TOOLS
215  if (scheduler.equals("lp"))
216  return scheduleWithLP(instOp, options, builder);
217  if (scheduler.equals("cpsat"))
218  return scheduleWithCPSAT(instOp, options, builder);
219 #endif
220 
221  llvm::errs() << "ssp-schedule: Unsupported scheduler '" << scheduler
222  << "' requested\n";
223  return {};
224 }
225 
226 //===----------------------------------------------------------------------===//
227 // Pass implementation
228 //===----------------------------------------------------------------------===//
229 
230 namespace {
231 struct SchedulePass : public ScheduleBase<SchedulePass> {
232  void runOnOperation() override;
233 };
234 } // end anonymous namespace
235 
236 void SchedulePass::runOnOperation() {
237  auto moduleOp = getOperation();
238 
239  SmallVector<InstanceOp> instanceOps;
240  OpBuilder builder(&getContext());
241  for (auto instOp : moduleOp.getOps<InstanceOp>()) {
242  builder.setInsertionPoint(instOp);
243  auto scheduledOp = scheduleWith(instOp, scheduler.getValue(),
244  schedulerOptions.getValue(), builder);
245  if (!scheduledOp)
246  return signalPassFailure();
247  instanceOps.push_back(instOp);
248  }
249 
250  llvm::for_each(instanceOps, [](InstanceOp op) { op.erase(); });
251 }
252 
253 std::unique_ptr<mlir::Pass> circt::ssp::createSchedulePass() {
254  return std::make_unique<SchedulePass>();
255 }
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: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:208
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:253
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...
mlir::raw_indented_ostream & errs()
Definition: Utility.h:33