17 #include "llvm/ADT/StringExtras.h"
19 using namespace circt;
20 using namespace scheduling;
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=")) {
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);
46 for (StringRef option : llvm::split(options,
',')) {
47 if (option.consume_front(
"cycle-time="))
48 return std::stof(option.str());
58 auto problemName = instOp.getProblemName();
59 if (!problemName.equals(
"Problem")) {
60 llvm::errs() <<
"ssp-schedule: Unsupported problem '" << problemName
61 <<
"' for ASAP scheduler\n";
65 auto prob = loadProblem<Problem>(instOp);
67 failed(prob.verify()))
76 template <
typename ProblemT>
80 auto prob = loadProblem<ProblemT>(instOp);
81 if (failed(prob.check()) ||
83 failed(prob.verify()))
92 auto prob = loadProblem<scheduling::ChainingProblem>(instOp);
93 if (failed(prob.check()) ||
95 failed(prob.verify()))
104 auto prob = loadProblem<scheduling::ChainingCyclicProblem>(instOp);
105 if (failed(prob.check()) ||
107 failed(prob.verify()))
114 auto lastOp =
getLastOp(instOp, options);
116 auto instName = instOp.getSymName().value_or(
"unnamed");
118 <<
"ssp-schedule: Ambiguous objective for simplex scheduler: Instance '"
119 << instName <<
"' has no designated last operation\n";
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,
131 if (problemName.equals(
"ModuloProblem"))
132 return scheduleProblemTWithSimplex<ModuloProblem>(instOp, lastOp,
builder);
133 if (problemName.equals(
"ChainingProblem")) {
137 llvm::errs() <<
"ssp-schedule: Missing option 'cycle-time' for "
138 "ChainingProblem simplex scheduler\n";
141 if (problemName.equals(
"ChainingCyclicProblem")) {
144 instOp, lastOp, cycleTime.value(),
builder);
145 llvm::errs() <<
"ssp-schedule: Missing option 'cycle-time' for "
146 "ChainingCyclicProblem simplex scheduler\n";
150 llvm::errs() <<
"ssp-schedule: Unsupported problem '" << problemName
151 <<
"' for simplex scheduler\n";
155 #ifdef SCHEDULING_OR_TOOLS
161 template <
typename ProblemT>
162 static InstanceOp scheduleProblemTWithLP(InstanceOp instOp, Operation *lastOp,
164 auto prob = loadProblem<ProblemT>(instOp);
166 failed(prob.verify()))
171 static InstanceOp scheduleWithLP(InstanceOp instOp, StringRef options,
173 auto lastOp =
getLastOp(instOp, options);
175 auto instName = instOp.getSymName().value_or(
"unnamed");
177 <<
"ssp-schedule: Ambiguous objective for LP scheduler: Instance '"
178 << instName <<
"' has no designated last operation\n";
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);
188 llvm::errs() <<
"ssp-schedule: Unsupported problem '" << problemName
189 <<
"' for LP scheduler\n";
197 static InstanceOp scheduleWithCPSAT(InstanceOp instOp, StringRef options,
199 auto lastOp =
getLastOp(instOp, options);
201 auto instName = instOp.getSymName().value_or(
"unnamed");
203 <<
"ssp-schedule: Ambiguous objective for CPSAT scheduler: Instance '"
204 << instName <<
"' has no designated last operation\n";
208 auto problemName = instOp.getProblemName();
209 if (!problemName.equals(
"SharedOperatorsProblem")) {
210 llvm::errs() <<
"ssp-schedule: Unsupported problem '" << problemName
211 <<
"' for CPSAT scheduler\n";
215 auto prob = loadProblem<SharedOperatorsProblem>(instOp);
217 failed(prob.verify()))
229 StringRef options, OpBuilder &
builder) {
230 if (scheduler.empty() || scheduler.equals(
"simplex"))
232 if (scheduler.equals(
"asap"))
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);
241 llvm::errs() <<
"ssp-schedule: Unsupported scheduler '" << scheduler
251 struct SchedulePass :
public ScheduleBase<SchedulePass> {
252 void runOnOperation()
override;
256 void SchedulePass::runOnOperation() {
257 auto moduleOp = getOperation();
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);
266 return signalPassFailure();
267 instanceOps.push_back(instOp);
270 llvm::for_each(instanceOps, [](InstanceOp op) { op.erase(); });
274 return std::make_unique<SchedulePass>();
static InstanceOp scheduleProblemTWithSimplex(InstanceOp instOp, Operation *lastOp, OpBuilder &builder)
static InstanceOp scheduleWithASAP(InstanceOp instOp, OpBuilder &builder)
static OperationOp getLastOp(InstanceOp instOp, StringRef options)
static std::optional< float > getCycleTime(StringRef options)
static InstanceOp scheduleWithSimplex(InstanceOp instOp, StringRef options, OpBuilder &builder)
static InstanceOp scheduleChainingCyclicProblemWithSimplex(InstanceOp instOp, Operation *lastOp, float cycleTime, OpBuilder &builder)
static InstanceOp scheduleChainingProblemWithSimplex(InstanceOp instOp, Operation *lastOp, float cycleTime, OpBuilder &builder)
static InstanceOp scheduleWith(InstanceOp instOp, StringRef scheduler, StringRef options, OpBuilder &builder)
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()
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...
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.