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()))
102 auto lastOp =
getLastOp(instOp, options);
104 auto instName = instOp.getSymName().value_or(
"unnamed");
106 <<
"ssp-schedule: Ambiguous objective for simplex scheduler: Instance '"
107 << instName <<
"' has no designated last operation\n";
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,
119 if (problemName.equals(
"ModuloProblem"))
120 return scheduleProblemTWithSimplex<ModuloProblem>(instOp, lastOp,
builder);
121 if (problemName.equals(
"ChainingProblem")) {
125 llvm::errs() <<
"ssp-schedule: Missing option 'cycle-time' for "
126 "ChainingProblem simplex scheduler\n";
130 llvm::errs() <<
"ssp-schedule: Unsupported problem '" << problemName
131 <<
"' for simplex scheduler\n";
135 #ifdef SCHEDULING_OR_TOOLS
141 template <
typename ProblemT>
142 static InstanceOp scheduleProblemTWithLP(InstanceOp instOp, Operation *lastOp,
144 auto prob = loadProblem<ProblemT>(instOp);
146 failed(prob.verify()))
151 static InstanceOp scheduleWithLP(InstanceOp instOp, StringRef options,
153 auto lastOp =
getLastOp(instOp, options);
155 auto instName = instOp.getSymName().value_or(
"unnamed");
157 <<
"ssp-schedule: Ambiguous objective for LP scheduler: Instance '"
158 << instName <<
"' has no designated last operation\n";
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);
168 llvm::errs() <<
"ssp-schedule: Unsupported problem '" << problemName
169 <<
"' for LP scheduler\n";
177 static InstanceOp scheduleWithCPSAT(InstanceOp instOp, StringRef options,
179 auto lastOp =
getLastOp(instOp, options);
181 auto instName = instOp.getSymName().value_or(
"unnamed");
183 <<
"ssp-schedule: Ambiguous objective for CPSAT scheduler: Instance '"
184 << instName <<
"' has no designated last operation\n";
188 auto problemName = instOp.getProblemName();
189 if (!problemName.equals(
"SharedOperatorsProblem")) {
190 llvm::errs() <<
"ssp-schedule: Unsupported problem '" << problemName
191 <<
"' for CPSAT scheduler\n";
195 auto prob = loadProblem<SharedOperatorsProblem>(instOp);
197 failed(prob.verify()))
209 StringRef options, OpBuilder &
builder) {
210 if (scheduler.empty() || scheduler.equals(
"simplex"))
212 if (scheduler.equals(
"asap"))
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);
221 llvm::errs() <<
"ssp-schedule: Unsupported scheduler '" << scheduler
231 struct SchedulePass :
public ScheduleBase<SchedulePass> {
232 void runOnOperation()
override;
236 void SchedulePass::runOnOperation() {
237 auto moduleOp = getOperation();
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);
246 return signalPassFailure();
247 instanceOps.push_back(instOp);
250 llvm::for_each(instanceOps, [](InstanceOp op) { op.erase(); });
254 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 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...
This file defines an intermediate representation for circuits acting as an abstraction for constraint...
mlir::raw_indented_ostream & errs()