23 #include "mlir/Pass/Pass.h"
25 #define DEBUG_TYPE "pipeline-schedule-linear"
29 #define GEN_PASS_DEF_SCHEDULELINEARPIPELINE
30 #include "circt/Dialect/Pipeline/PipelinePasses.h.inc"
35 using namespace circt;
37 using namespace pipeline;
41 class ScheduleLinearPipelinePass
42 :
public circt::pipeline::impl::ScheduleLinearPipelineBase<
43 ScheduleLinearPipelinePass> {
45 void runOnOperation()
override;
48 LogicalResult schedulePipeline(UnscheduledPipelineOp pipeline);
55 return op->hasTrait<OpTrait::ConstantLike>();
59 ScheduleLinearPipelinePass::schedulePipeline(UnscheduledPipelineOp pipeline) {
62 auto opLibAttr = pipeline->getAttrOfType<FlatSymbolRefAttr>(
"operator_lib");
64 return pipeline.emitError(
"missing 'operator_lib' attribute");
65 auto parentModule = pipeline->getParentOfType<ModuleOp>();
66 auto opLib = parentModule.lookupSymbol<ssp::OperatorLibraryOp>(opLibAttr);
68 return pipeline.emitError(
"operator library '")
69 << opLibAttr <<
"' not found";
74 DenseMap<SymbolRefAttr, Problem::OperatorType> operatorTypes;
79 cast<pipeline::ReturnOp>(pipeline.getEntryStage()->getTerminator());
80 for (
auto &op : pipeline.getOps()) {
86 bool isReturnOp = &op == returnOp.getOperation();
90 operatorType = problem.getOrInsertOperatorType(
"return");
91 problem.setLatency(operatorType, 0);
94 auto operatorTypeAttr =
95 op.getAttrOfType<SymbolRefAttr>(
"ssp.operator_type");
96 if (!operatorTypeAttr)
98 <<
"Expected 'ssp.operator_type' attribute on operation.";
100 auto operatorTypeIt = operatorTypes.find(operatorTypeAttr);
101 if (operatorTypeIt == operatorTypes.end()) {
104 opLib.lookupSymbol<ssp::OperatorTypeOp>(operatorTypeAttr);
106 return op.emitError() <<
"Operator type '" << operatorTypeAttr
107 <<
"' not found in operator library.";
109 auto insertRes = operatorTypes.try_emplace(
110 operatorTypeAttr, ssp::loadOperatorType<Problem, ssp::LatencyAttr>(
111 problem, opTypeOp, oprIds));
112 operatorTypeIt = insertRes.first;
114 operatorType = operatorTypeIt->second;
117 problem.insertOperation(&op);
118 problem.setLinkedOperatorType(&op, operatorType);
124 if (!isReturnOp && op.use_empty()) {
125 if (failed(problem.insertDependence({&op, returnOp.getOperation()})))
126 return op.emitError()
127 <<
"Failed to insert dependence from operation to return op.";
132 assert(succeeded(problem.check()));
134 return pipeline.emitError(
"Failed to schedule pipeline.");
136 assert(succeeded(problem.verify()));
139 using StageIdx = unsigned;
141 OpBuilder b(pipeline.getContext());
146 std::map<StageIdx, llvm::SmallVector<Operation *>> stageMap;
147 llvm::SmallVector<Operation *, 4> otherOps;
150 b.setInsertionPoint(pipeline);
151 auto schedPipeline = b.template create<pipeline::ScheduledPipelineOp>(
152 pipeline.getLoc(), pipeline.getDataOutputs().getTypes(),
153 pipeline.getInputs(), pipeline.getInputNames(), pipeline.getOutputNames(),
154 pipeline.getClock(), pipeline.getReset(), pipeline.getGo(),
155 pipeline.getStall(), pipeline.getNameAttr());
157 Block *currentStage = schedPipeline.getStage(0);
159 for (
auto [oldBArg, newBArg] :
160 llvm::zip(pipeline.getEntryStage()->getArguments(),
161 currentStage->getArguments()))
162 oldBArg.replaceAllUsesWith(newBArg);
166 unsigned currentEndTime = 0;
167 for (
auto &op : pipeline.getOps()) {
169 otherOps.push_back(&op);
172 unsigned startTime = *problem.getStartTime(&op);
173 stageMap[startTime].push_back(&op);
175 auto oldEndTime = currentEndTime;
176 currentEndTime = std::max(currentEndTime, *problem.getEndTime(&op));
177 for (
unsigned i = oldEndTime; i < currentEndTime; ++i) {
178 Block *newStage = schedPipeline.addStage();
182 b.setInsertionPointToEnd(currentStage);
183 b.create<pipeline::StageOp>(pipeline.getLoc(), newStage, ValueRange{},
185 currentStage = newStage;
190 returnOp->moveBefore(currentStage, currentStage->end());
194 Block *entryStage = schedPipeline.getStage(0);
195 Operation *entryStageTerminator = entryStage->getTerminator();
196 for (
auto *op : otherOps)
197 op->moveBefore(entryStageTerminator);
199 for (
auto [startTime, ops] : stageMap) {
200 Block *stage = schedPipeline.getStage(startTime);
201 assert(stage &&
"Stage not found");
202 Operation *stageTerminator = stage->getTerminator();
204 op->moveBefore(stageTerminator);
208 pipeline.replaceAllUsesWith(schedPipeline);
213 void ScheduleLinearPipelinePass::runOnOperation() {
214 for (
auto ®ion : getOperation()->getRegions()) {
216 llvm::make_early_inc_range(region.getOps<UnscheduledPipelineOp>())) {
217 if (failed(schedulePipeline(pipeline)))
218 return signalPassFailure();
223 std::unique_ptr<mlir::Pass>
225 return std::make_unique<ScheduleLinearPipelinePass>();
assert(baseType &&"element must be base type")
static bool ignoreOp(Operation *op)
This class models the most basic scheduling problem.
mlir::StringAttr OperatorType
Operator types are distinguished by name (chosen by the client).
std::unique_ptr< mlir::Pass > createScheduleLinearPipelinePass()
LogicalResult scheduleSimplex(Problem &prob, Operation *lastOp)
Solve the basic problem using linear programming and a handwritten implementation of the simplex algo...
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.