CIRCT  20.0.0git
ScheduleLinearPipeline.cpp
Go to the documentation of this file.
1 //===- ScheduleLinearPipeline.cpp - Linear pipeline scheduling pass -----*-===//
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 // Contains the definitions linear pipeline scheduling pass.
10 //
11 //===----------------------------------------------------------------------===//
12 
23 #include "mlir/Pass/Pass.h"
24 
25 #define DEBUG_TYPE "pipeline-schedule-linear"
26 
27 namespace circt {
28 namespace pipeline {
29 #define GEN_PASS_DEF_SCHEDULELINEARPIPELINE
30 #include "circt/Dialect/Pipeline/PipelinePasses.h.inc"
31 } // namespace pipeline
32 } // namespace circt
33 
34 using namespace mlir;
35 using namespace circt;
36 using namespace circt::scheduling;
37 using namespace pipeline;
38 
39 namespace {
40 
41 class ScheduleLinearPipelinePass
42  : public circt::pipeline::impl::ScheduleLinearPipelineBase<
43  ScheduleLinearPipelinePass> {
44 public:
45  void runOnOperation() override;
46 
47 private:
48  LogicalResult schedulePipeline(UnscheduledPipelineOp pipeline);
49 };
50 
51 } // end anonymous namespace
52 
53 // Returns true if 'op' should be ignored in the scheduling problem.
54 static bool ignoreOp(Operation *op) {
55  return op->hasTrait<OpTrait::ConstantLike>();
56 }
57 
58 LogicalResult
59 ScheduleLinearPipelinePass::schedulePipeline(UnscheduledPipelineOp pipeline) {
60  // Get operator library for the pipeline - assume it's placed in the top level
61  // module.
62  auto opLibAttr = pipeline->getAttrOfType<FlatSymbolRefAttr>("operator_lib");
63  if (!opLibAttr)
64  return pipeline.emitError("missing 'operator_lib' attribute");
65  auto parentModule = pipeline->getParentOfType<ModuleOp>();
66  auto opLib = parentModule.lookupSymbol<ssp::OperatorLibraryOp>(opLibAttr);
67  if (!opLib)
68  return pipeline.emitError("operator library '")
69  << opLibAttr << "' not found";
70 
71  // Load operator info from attribute.
72  Problem problem(pipeline);
73 
74  DenseMap<SymbolRefAttr, Problem::OperatorType> operatorTypes;
76 
77  // Set operation operator types.
78  auto returnOp =
79  cast<pipeline::ReturnOp>(pipeline.getEntryStage()->getTerminator());
80  for (auto &op : pipeline.getOps()) {
81  // Skip if is a known non-functional operator
82  if (ignoreOp(&op))
83  continue;
84 
85  Problem::OperatorType operatorType;
86  bool isReturnOp = &op == returnOp.getOperation();
87  if (isReturnOp) {
88  // Construct an operator type for the return op (not an externally defined
89  // operator type since it is intrinsic to this pass).
90  operatorType = problem.getOrInsertOperatorType("return");
91  problem.setLatency(operatorType, 0);
92  } else {
93  // Lookup operator info.
94  auto operatorTypeAttr =
95  op.getAttrOfType<SymbolRefAttr>("ssp.operator_type");
96  if (!operatorTypeAttr)
97  return op.emitError()
98  << "Expected 'ssp.operator_type' attribute on operation.";
99 
100  auto operatorTypeIt = operatorTypes.find(operatorTypeAttr);
101  if (operatorTypeIt == operatorTypes.end()) {
102  // First time seeing operator type - load it into the problem.
103  auto opTypeOp =
104  opLib.lookupSymbol<ssp::OperatorTypeOp>(operatorTypeAttr);
105  if (!opTypeOp)
106  return op.emitError() << "Operator type '" << operatorTypeAttr
107  << "' not found in operator library.";
108 
109  auto insertRes = operatorTypes.try_emplace(
110  operatorTypeAttr, ssp::loadOperatorType<Problem, ssp::LatencyAttr>(
111  problem, opTypeOp, oprIds));
112  operatorTypeIt = insertRes.first;
113  }
114  operatorType = operatorTypeIt->second;
115  }
116 
117  problem.insertOperation(&op);
118  problem.setLinkedOperatorType(&op, operatorType);
119 
120  // We want the return op to be a sink node for the dependence graph, i.e. it
121  // should (transitively) depend on every other op. This is done by inserting
122  // auxiliary dependences from ops without users, complementing the implicit
123  // dependences from the return op's operands.
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.";
128  }
129  }
130 
131  // Solve!
132  assert(succeeded(problem.check()));
133  if (failed(scheduling::scheduleSimplex(problem, returnOp.getOperation())))
134  return pipeline.emitError("Failed to schedule pipeline.");
135 
136  assert(succeeded(problem.verify()));
137 
138  // Gather stage results.
139  using StageIdx = unsigned;
140 
141  OpBuilder b(pipeline.getContext());
142 
143  // Maintain a mapping of {start time : [operations]}, that contains the
144  // operations scheduled to a given start time. This is an ordered map, so that
145  // we can iterate over the stages in order.
146  std::map<StageIdx, llvm::SmallVector<Operation *>> stageMap;
147  llvm::SmallVector<Operation *, 4> otherOps;
148 
149  // Create the scheduled pipeline.
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());
156 
157  Block *currentStage = schedPipeline.getStage(0);
158 
159  for (auto [oldBArg, newBArg] :
160  llvm::zip(pipeline.getEntryStage()->getArguments(),
161  currentStage->getArguments()))
162  oldBArg.replaceAllUsesWith(newBArg);
163 
164  // Iterate over the ops in the pipeline, and add them to the stage map.
165  // While doing so, we also build the pipeline stage operations.
166  unsigned currentEndTime = 0;
167  for (auto &op : pipeline.getOps()) {
168  if (ignoreOp(&op)) {
169  otherOps.push_back(&op);
170  continue;
171  }
172  unsigned startTime = *problem.getStartTime(&op);
173  stageMap[startTime].push_back(&op);
174 
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();
179 
180  // Create a StageOp in the new stage, and branch it to the newly created
181  // stage.
182  b.setInsertionPointToEnd(currentStage);
183  b.create<pipeline::StageOp>(pipeline.getLoc(), newStage, ValueRange{},
184  ValueRange{});
185  currentStage = newStage;
186  }
187  }
188 
189  // Move the return op to the last stage in the scheduled pipeline.
190  returnOp->moveBefore(currentStage, currentStage->end());
191 
192  // Reorder pipeline. Initially place unscheduled ops at the entry stage, and
193  // then all following ops in their assigned stage.
194  Block *entryStage = schedPipeline.getStage(0);
195  Operation *entryStageTerminator = entryStage->getTerminator();
196  for (auto *op : otherOps)
197  op->moveBefore(entryStageTerminator);
198 
199  for (auto [startTime, ops] : stageMap) {
200  Block *stage = schedPipeline.getStage(startTime);
201  assert(stage && "Stage not found");
202  Operation *stageTerminator = stage->getTerminator();
203  for (auto *op : ops)
204  op->moveBefore(stageTerminator);
205  }
206 
207  // Remove the unscheduled pipeline
208  pipeline.replaceAllUsesWith(schedPipeline);
209  pipeline.erase();
210  return success();
211 }
212 
213 void ScheduleLinearPipelinePass::runOnOperation() {
214  for (auto &region : getOperation()->getRegions()) {
215  for (auto pipeline :
216  llvm::make_early_inc_range(region.getOps<UnscheduledPipelineOp>())) {
217  if (failed(schedulePipeline(pipeline)))
218  return signalPassFailure();
219  }
220  }
221 }
222 
223 std::unique_ptr<mlir::Pass>
225  return std::make_unique<ScheduleLinearPipelinePass>();
226 }
assert(baseType &&"element must be base type")
static bool ignoreOp(Operation *op)
This class models the most basic scheduling problem.
Definition: Problems.h:75
mlir::StringAttr OperatorType
Operator types are distinguished by name (chosen by the client).
Definition: Problems.h:98
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.
Definition: DebugAnalysis.h:21