CIRCT  20.0.0git
ExplicitRegs.cpp
Go to the documentation of this file.
1 //===- ExplicitRegs.cpp - Explicit regs pass --------------------*- C++ -*-===//
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 of the explicit regs pass.
10 //
11 //===----------------------------------------------------------------------===//
12 
16 #include "mlir/Pass/Pass.h"
17 #include "llvm/Support/Debug.h"
18 
19 namespace circt {
20 namespace pipeline {
21 #define GEN_PASS_DEF_EXPLICITREGS
22 #include "circt/Dialect/Pipeline/PipelinePasses.h.inc"
23 } // namespace pipeline
24 } // namespace circt
25 
26 using namespace mlir;
27 using namespace circt;
28 using namespace pipeline;
29 
30 namespace {
31 
32 struct NamedValue {
33  Value v;
34  StringAttr name;
35  operator Value() const { return v; }
36  operator Attribute() const { return name; }
37  operator llvm::StringRef() const { return name.getValue(); }
38 };
39 
40 class ExplicitRegsPass
41  : public circt::pipeline::impl::ExplicitRegsBase<ExplicitRegsPass> {
42 public:
43  void runOnOperation() override;
44 
45 private:
46  void runOnPipeline(ScheduledPipelineOp p);
47 
48  // Recursively routes value v backwards through the pipeline, adding new
49  // registers to 'stage' if the value was not already registered in the stage.
50  // Returns the registered version of 'v' through 'stage'.
51  NamedValue routeThroughStage(Value v, Block *stage);
52 
53  // Returns the distance between two stages in the pipeline. The distance is
54  // defined wrt. the ordered stages of the pipeline.
55  int64_t stageDistance(Block *from, Block *to);
56 
57  // Returns a suitable name for a value.
58  StringAttr genValueName(Value v);
59 
60  struct RoutedValue {
61  Backedge v;
62  // If true, this value is routed through a stage as a register, else
63  // it is routed through a stage as a pass-through.e
64  bool isReg;
65  StringAttr name;
66 
67  operator NamedValue() { return NamedValue{v, name}; }
68  };
69  // A mapping storing whether a given stage register constains a registered
70  // version of a given value. The registered version will be a backedge during
71  // pipeline body analysis. Once the entire body has been analyzed, `regs`
72  // operands will be added to the pipeline.stage operation, and the backedge
73  // will be replaced. MapVector ensures deterministic iteration order, which in
74  // turn ensures determinism during stage op IR emission.
75  DenseMap<Block *, llvm::MapVector<Value, RoutedValue>> stageRegOrPassMap;
76 
77  // A mapping between stages and their index in the pipeline.
78  llvm::DenseMap<Block *, unsigned> stageMap;
79 
80  std::shared_ptr<BackedgeBuilder> bb;
81  ScheduledPipelineOp parent;
82 };
83 
84 } // end anonymous namespace
85 
86 int64_t ExplicitRegsPass::stageDistance(Block *from, Block *to) {
87  int64_t fromStage = stageMap[from];
88  int64_t toStage = stageMap[to];
89  return toStage - fromStage;
90 }
91 
92 StringAttr ExplicitRegsPass::genValueName(Value v) {
93  Operation *definingOp = v.getDefiningOp();
94  StringAttr valueName;
95  auto setNameFn = [&](Value other, StringRef name) {
96  if (other == v)
97  valueName = StringAttr::get(other.getContext(), name);
98  };
99  if (definingOp) {
100  if (OpAsmOpInterface asmInterface = dyn_cast<OpAsmOpInterface>(definingOp))
101  asmInterface.getAsmResultNames(setNameFn);
102  // Somewhat comb specific - look for an sv.namehint attribute.
103  else if (auto nameHint =
104  definingOp->getAttrOfType<StringAttr>("sv.namehint"))
105  valueName = nameHint;
106  else
107  valueName = StringAttr::get(v.getContext(), "");
108  } else {
109  // It's a block argument - leverage the OpAsmOpInterface of the pipeline
110  // op.
111  auto asmInterface = cast<OpAsmOpInterface>(parent.getOperation());
112  asmInterface.getAsmBlockArgumentNames(parent.getBody(), setNameFn);
113  }
114 
115  assert(valueName && "Wasn't able to generate a name for a value");
116  return valueName;
117 }
118 
119 // NOLINTNEXTLINE(misc-no-recursion)
120 NamedValue ExplicitRegsPass::routeThroughStage(Value v, Block *stage) {
121  Value retVal = v;
122  Block *definingStage = retVal.getParentBlock();
123 
124  // Is the value defined in the current stage?
125  if (definingStage == stage) {
126  // Value is defined in the current stage - no routing needed, but we need to
127  // define a name.
128  return NamedValue{retVal, genValueName(retVal)};
129  }
130 
131  auto regIt = stageRegOrPassMap[stage].find(retVal);
132  if (regIt != stageRegOrPassMap[stage].end()) {
133  // 'v' is already routed through 'stage' - return the registered/passed
134  // version.
135  return regIt->second;
136  }
137 
138  // Is the value a constant? If so, we allow it; constants are special cases
139  // which are allowed to be used in any stage.
140  auto *definingOp = retVal.getDefiningOp();
141  if (definingOp && definingOp->hasTrait<OpTrait::ConstantLike>())
142  return NamedValue{retVal, StringAttr::get(retVal.getContext(), "")};
143 
144  // Value is defined somewhere before the provided stage - route it through the
145  // stage, and recurse to the predecessor stage.
146  int64_t valueLatency = 0;
147  if (auto latencyOp = dyn_cast_or_null<LatencyOp>(definingOp))
148  valueLatency = latencyOp.getLatency();
149 
150  // A value should be registered in this stage if the latency of the value
151  // is less than the distance between the current stage and the defining stage.
152  bool isReg = valueLatency < stageDistance(definingStage, stage);
153  auto valueBackedge = bb->get(retVal.getType());
154  auto stageRegBE = stageRegOrPassMap[stage].insert(
155  {retVal, RoutedValue{valueBackedge, isReg,
156  StringAttr::get(retVal.getContext(), "")}});
157  retVal = valueBackedge;
158 
159  // Recurse - recursion will only create a new backedge if necessary.
160  Block *stagePred = stage->getSinglePredecessor();
161  assert(stagePred && "Expected stage to have a single predecessor");
162  auto namedV = routeThroughStage(v, stagePred);
163  // And name the backedge using the routed value result name.
164  stageRegBE.first->second.name = namedV.name;
165 
166  return NamedValue{retVal, namedV.name};
167 }
168 
169 void ExplicitRegsPass::runOnPipeline(ScheduledPipelineOp pipeline) {
170  OpBuilder b(pipeline.getContext());
171  parent = pipeline;
172  bb = std::make_shared<BackedgeBuilder>(b, pipeline.getLoc());
173 
174  // Cache external-like inputs in a set for fast lookup. This also includes
175  // clock, reset, and stall.
176  llvm::DenseSet<Value> extLikeInputs;
177  for (auto extInput : pipeline.getExtInputs())
178  extLikeInputs.insert(extInput);
179  extLikeInputs.insert(pipeline.getClock());
180  extLikeInputs.insert(pipeline.getReset());
181  if (pipeline.hasStall())
182  extLikeInputs.insert(pipeline.getStall());
183 
184  // Iterate over the pipeline body in-order (!).
185  stageMap = pipeline.getStageMap();
186  for (Block *stage : pipeline.getOrderedStages()) {
187  // Walk the stage body - we do this since register materialization needs
188  // to consider all levels of nesting within the stage.
189  stage->walk([&](Operation *op) {
190  // Check the operands of this operation to see if any of them cross a
191  // stage boundary.
192  for (OpOperand &operand : op->getOpOperands()) {
193  if (extLikeInputs.contains(operand.get())) {
194  // Never route external inputs through a stage.
195  continue;
196  }
197  if (getParentStageInPipeline(pipeline, operand.get()) == stage) {
198  // The operand is defined by some operation or block which ultimately
199  // resides within the current pipeline stage. No routing needed.
200  continue;
201  }
202  Value reroutedValue = routeThroughStage(operand.get(), stage);
203  if (reroutedValue != operand.get())
204  op->setOperand(operand.getOperandNumber(), reroutedValue);
205  }
206  });
207  }
208 
209  auto *ctx = &getContext();
210 
211  // All values have been recorded through the stages.
212  // Now
213  // 1. Add 'regs' and 'pass' operands to the `pipeline.stage` operations
214  // 2. Add the corresponding block arguments to the stage blocks.
215  for (auto &it : stageRegOrPassMap) {
216  Block *stage = it.first;
217  auto &regOrPassMap = it.second;
218 
219  // Gather register inputs to this stage, either from a predecessor stage
220  // or from the original op.
221  llvm::MapVector<Value, Value> regInsMap, passInsMap;
222  llvm::SmallVector<Attribute> regNames, passNames;
223  Block *predecessorStage = stage->getSinglePredecessor();
224  auto predStageRegOrPassMap = stageRegOrPassMap.find(predecessorStage);
225  assert(predecessorStage && "Stage should always have a single predecessor");
226  for (auto &[value, backedge] : regOrPassMap) {
227  if (backedge.isReg)
228  regNames.push_back(backedge.name);
229  else
230  passNames.push_back(backedge.name);
231 
232  if (predStageRegOrPassMap != stageRegOrPassMap.end()) {
233  // Grab the value if passed through the predecessor stage, else,
234  // use the raw value.
235  auto predRegIt = predStageRegOrPassMap->second.find(value);
236  if (predRegIt != predStageRegOrPassMap->second.end()) {
237  if (backedge.isReg) {
238  regInsMap[value] = predRegIt->second.v;
239  } else {
240  passInsMap[value] = predRegIt->second.v;
241  }
242  continue;
243  }
244  }
245 
246  // Not passed through the stage - must be the original value.
247  if (backedge.isReg)
248  regInsMap[value] = value;
249  else
250  passInsMap[value] = value;
251  }
252 
253  // Replace the predecessor stage terminator, which feeds this stage, with
254  // a new terminator that has materialized arguments.
255  llvm::SmallVector<Value> regIns, passIns;
256  llvm::transform(regInsMap, std::back_inserter(regIns),
257  [](auto &pair) { return pair.second; });
258  llvm::transform(passInsMap, std::back_inserter(passIns),
259  [](auto &pair) { return pair.second; });
260 
261  StageOp terminator = cast<StageOp>(predecessorStage->getTerminator());
262  b.setInsertionPoint(terminator);
263  llvm::SmallVector<llvm::SmallVector<Value>> clockGates;
264  b.create<StageOp>(terminator.getLoc(), terminator.getNextStage(), regIns,
265  passIns, clockGates, b.getArrayAttr(regNames),
266  b.getArrayAttr(passNames));
267  terminator.erase();
268 
269  // ... and add arguments to the next stage. Registers first, then
270  // passthroughs.
271  // While doing so, replace for the next stage arguments with the new
272  // arguments. Doing so wrt. regInsMap ensures that we preserve the
273  // order of operands in the StageOp and the target block.
274  size_t argIdx = 0;
275  auto addArgAndRewriteBE = [&](llvm::MapVector<Value, Value> &map) {
276  for (auto origToActualValue : map) {
277  Value origValue = origToActualValue.first;
278  stage->insertArgument(argIdx, origValue.getType(),
279  UnknownLoc::get(ctx));
280  auto *backedgeIt = regOrPassMap.find(origValue);
281  assert(backedgeIt != regOrPassMap.end() &&
282  "Expected to find backedge for value");
283  backedgeIt->second.v.setValue(stage->getArgument(argIdx));
284  ++argIdx;
285  }
286  };
287  addArgAndRewriteBE(regInsMap);
288  addArgAndRewriteBE(passInsMap);
289  }
290 
291  // Clear internal state. See https://github.com/llvm/circt/issues/3235
292  stageRegOrPassMap.clear();
293 }
294 
295 void ExplicitRegsPass::runOnOperation() {
296  getOperation()->walk(
297  [&](ScheduledPipelineOp pipeline) { runOnPipeline(pipeline); });
298 }
299 
300 std::unique_ptr<mlir::Pass> circt::pipeline::createExplicitRegsPass() {
301  return std::make_unique<ExplicitRegsPass>();
302 }
assert(baseType &&"element must be base type")
static std::string valueName(Operation *scopeOp, Value v)
Convenience function for getting the SSA name of v under the scope of operation scopeOp.
Definition: CalyxOps.cpp:121
static llvm::raw_string_ostream & genValueName(llvm::raw_string_ostream &os, Value value)
Definition: IbisOps.cpp:41
Backedge is a wrapper class around a Value.
Direction get(bool isOutput)
Returns an output direction if isOutput is true, otherwise returns an input direction.
Definition: CalyxOps.cpp:55
std::unique_ptr< mlir::Pass > createExplicitRegsPass()
Block * getParentStageInPipeline(ScheduledPipelineOp pipeline, Operation *op)
Definition: PipelineOps.cpp:66
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
Definition: DebugAnalysis.h:21