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