CIRCT  19.0.0git
RemoveGroupsFromFSM.cpp
Go to the documentation of this file.
1 //===- RemoveGroupsFromFSM.cpp - Remove Groups 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 Remove Groups pass.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "../PassDetail.h"
20 #include "circt/Support/LLVM.h"
21 #include "mlir/IR/BuiltinTypes.h"
22 #include "mlir/IR/OperationSupport.h"
23 #include "llvm/ADT/STLExtras.h"
24 
25 using namespace circt;
26 using namespace calyx;
27 using namespace mlir;
28 using namespace fsm;
29 
30 namespace {
31 
32 struct CalyxRemoveGroupsFromFSM
33  : public CalyxRemoveGroupsFromFSMBase<CalyxRemoveGroupsFromFSM> {
34  void runOnOperation() override;
35 
36  // Outlines the `fsm.machine` operation from within the `calyx.control`
37  // operation to the module scope, and instantiates the FSM. By doing so, we
38  // record the association between FSM outputs and group go signals as well as
39  // FSM inputs, which are backedges to the group done signals.
40  LogicalResult outlineMachine();
41 
42  /// Makes several modifications to the operations of a GroupOp:
43  /// 1. Assign the 'done' signal of the component with the done_op of the top
44  /// level control group.
45  /// 2. Append the 'go' signal of the component to guard of each assignment.
46  /// 3. Replace all uses of GroupGoOp with the respective guard, and delete the
47  /// GroupGoOp.
48  /// 4. Remove the GroupDoneOp.
49  LogicalResult modifyGroupOperations();
50 
51  /// Inlines each group in the WiresOp.
52  void inlineGroups();
53 
54  /// A handle to the machine under transformation.
55  MachineOp machineOp;
56 
57  // A handle to the component op under transformation.
58  ComponentOp componentOp;
59 
60  OpBuilder *b;
61  BackedgeBuilder *bb;
62 
63  // A mapping between group names and their 'go' inputs generated by the FSM.
64  DenseMap<StringAttr, Value> groupGoSignals;
65 
66  // A mapping between group names and their 'done' output wires sent to
67  // the FSM.
68  DenseMap<StringAttr, calyx::WireLibOp> groupDoneWires;
69 };
70 
71 } // end anonymous namespace
72 
74  auto loc = componentOp.getLoc();
75  for (auto group : componentOp.getWiresOp().getOps<GroupOp>()) {
76  auto groupGo = group.getGoOp();
77  if (groupGo)
78  return emitError(loc)
79  << "This pass does not need `calyx.group_go` operations.";
80 
81  auto groupDone = group.getDoneOp();
82  if (!groupDone)
83  return emitError(loc) << "Group " << group.getSymName()
84  << " does not have a `calyx.group_done` operation";
85 
86  // Update group assignments to guard with the group go signal.
87  auto fsmGroupGo = groupGoSignals.find(group.getSymNameAttr());
88  assert(fsmGroupGo != groupGoSignals.end() &&
89  "Could not find FSM go signal for group");
90 
91  updateGroupAssignmentGuards(*b, group, fsmGroupGo->second);
92 
93  // Create a calyx wire for the group done signal, and assign it to the
94  // expression of the group_done operation.
95  auto doneWireIt = groupDoneWires.find(group.getSymNameAttr());
96  assert(doneWireIt != groupDoneWires.end() &&
97  "Could not find FSM done backedge for group");
98  auto doneWire = doneWireIt->second;
99 
100  b->setInsertionPointToEnd(componentOp.getWiresOp().getBodyBlock());
101  b->create<calyx::AssignOp>(loc, doneWire.getIn(), groupDone.getSrc(),
102  groupDone.getGuard());
103 
104  groupDone.erase();
105  }
106  return success();
107 }
108 
109 /// Inlines each group in the WiresOp.
111  auto &wiresRegion = componentOp.getWiresOp().getRegion();
112  auto &wireBlocks = wiresRegion.getBlocks();
113  auto lastBlock = wiresRegion.end();
114 
115  // Inline the body of each group as a Block into the WiresOp.
116  wiresRegion.walk([&](GroupOp group) {
117  wireBlocks.splice(lastBlock, group.getRegion().getBlocks());
118  group->erase();
119  });
120 
121  // Merge the operations of each Block into the first block of the WiresOp.
122  auto firstBlock = wireBlocks.begin();
123  for (auto it = firstBlock, e = lastBlock; it != e; ++it) {
124  if (it == firstBlock)
125  continue;
126  firstBlock->getOperations().splice(firstBlock->end(), it->getOperations());
127  }
128 
129  // Erase the (now) empty blocks.
130  while (&wiresRegion.front() != &wiresRegion.back())
131  wiresRegion.back().erase();
132 }
133 
134 LogicalResult CalyxRemoveGroupsFromFSM::outlineMachine() {
135  // Walk all operations within the machine and gather the SSA values which are
136  // referenced in case they are not defined within the machine.
137  // MapVector ensures determinism.
138  llvm::MapVector<Value, SmallVector<Operation *>> referencedValues;
139  machineOp.walk([&](Operation *op) {
140  for (auto &operand : op->getOpOperands()) {
141  if (auto barg = operand.get().dyn_cast<BlockArgument>()) {
142  if (barg.getOwner()->getParentOp() == machineOp)
143  continue;
144 
145  // A block argument defined outside of the machineOp.
146  referencedValues[operand.get()].push_back(op);
147  } else {
148  auto *defOp = operand.get().getDefiningOp();
149  auto machineOpParent = defOp->getParentOfType<MachineOp>();
150  if (machineOpParent && machineOpParent == machineOp)
151  continue;
152 
153  referencedValues[operand.get()].push_back(op);
154  }
155  }
156  });
157 
158  // Add a new input to the machine for each referenced SSA value and replace
159  // all uses of the value with the new input.
160  DenseMap<Value, size_t> ssaInputIndices;
161  auto machineOutputTypes = machineOp.getFunctionType().getResults();
162  auto currentInputs = machineOp.getFunctionType().getInputs();
163  llvm::SmallVector<Type> machineInputTypes(currentInputs);
164 
165  for (auto &[value, users] : referencedValues) {
166  ssaInputIndices[value] = machineOp.getBody().getNumArguments();
167  auto t = value.getType();
168  auto arg = machineOp.getBody().addArgument(t, b->getUnknownLoc());
169  machineInputTypes.push_back(t);
170  for (auto *user : users) {
171  for (auto &operand : user->getOpOperands()) {
172  if (operand.get() == value)
173  operand.set(arg);
174  }
175  }
176  }
177  // Update the machineOp type.
178  machineOp.setType(b->getFunctionType(machineInputTypes, machineOutputTypes));
179 
180  // Move the machine to module scope
181  machineOp->moveBefore(componentOp);
182  size_t nMachineInputs = machineOp.getBody().getNumArguments();
183 
184  // Create an fsm.hwinstance in the Calyx component scope with backedges for
185  // the group done inputs.
186  auto groupDoneInputsAttr =
187  machineOp->getAttrOfType<DictionaryAttr>(calyxToFSM::sGroupDoneInputs);
188  auto groupGoOutputsAttr =
189  machineOp->getAttrOfType<DictionaryAttr>(calyxToFSM::sGroupGoOutputs);
190  if (!groupDoneInputsAttr || !groupGoOutputsAttr)
191  return emitError(machineOp.getLoc())
192  << "MachineOp does not have a " << calyxToFSM::sGroupDoneInputs
193  << " or " << calyxToFSM::sGroupGoOutputs
194  << " attribute. Was --materialize-calyx-to-fsm run before "
195  "this pass?";
196 
197  b->setInsertionPointToStart(&componentOp.getBody().front());
198 
199  // Maintain a mapping between the FSM input index and the SSA value.
200  // We do this to sanity check that all inputs occur in the expected order.
201  DenseMap<size_t, Value> fsmInputMap;
202 
203  // First we inspect the groupDoneInputsAttr map and create backedges.
204  for (auto &namedAttr : groupDoneInputsAttr.getValue()) {
205  auto name = namedAttr.getName();
206  auto idx = namedAttr.getValue().cast<IntegerAttr>();
207  auto inputIdx = idx.cast<IntegerAttr>().getInt();
208  if (fsmInputMap.count(inputIdx))
209  return emitError(machineOp.getLoc())
210  << "MachineOp has duplicate input index " << idx;
211 
212  // Create a wire for the group done input.
213  b->setInsertionPointToStart(&componentOp.getBody().front());
214  auto groupDoneWire = b->create<calyx::WireLibOp>(
215  componentOp.getLoc(), name.str() + "_done", b->getI1Type());
216  fsmInputMap[inputIdx] = groupDoneWire.getOut();
217  groupDoneWires[name] = groupDoneWire;
218  }
219 
220  // Then we inspect the top level go/done attributes.
221  auto topLevelGoAttr =
222  machineOp->getAttrOfType<IntegerAttr>(calyxToFSM::sFSMTopLevelGoIndex);
223  if (!topLevelGoAttr)
224  return emitError(machineOp.getLoc())
225  << "MachineOp does not have a " << calyxToFSM::sFSMTopLevelGoIndex
226  << " attribute.";
227  fsmInputMap[topLevelGoAttr.getInt()] = componentOp.getGoPort();
228 
229  auto topLevelDoneAttr =
230  machineOp->getAttrOfType<IntegerAttr>(calyxToFSM::sFSMTopLevelDoneIndex);
231  if (!topLevelDoneAttr)
232  return emitError(machineOp.getLoc())
233  << "MachineOp does not have a " << calyxToFSM::sFSMTopLevelDoneIndex
234  << " attribute.";
235 
236  // Then we inspect the external SSA values.
237  for (auto [value, idx] : ssaInputIndices) {
238  if (fsmInputMap.count(idx))
239  return emitError(machineOp.getLoc())
240  << "MachineOp has duplicate input index " << idx;
241  fsmInputMap[idx] = value;
242  }
243 
244  if (fsmInputMap.size() != nMachineInputs)
245  return emitError(machineOp.getLoc())
246  << "MachineOp has " << nMachineInputs
247  << " inputs, but only recorded " << fsmInputMap.size()
248  << " inputs. This either means that --materialize-calyx-to-fsm "
249  "failed or that there is a mismatch in the MachineOp attributes.";
250 
251  // Convert the fsmInputMap to a list.
252  llvm::SmallVector<Value> fsmInputs;
253  for (size_t idx = 0; idx < nMachineInputs; ++idx) {
254  auto it = fsmInputMap.find(idx);
255  assert(it != fsmInputMap.end() && "Missing FSM input index");
256  fsmInputs.push_back(it->second);
257  }
258 
259  // Instantiate the FSM.
260  auto clkPort = componentOp.getClkPort();
261  auto clk = b->create<seq::ToClockOp>(clkPort.getLoc(), clkPort);
262  auto fsmInstance = b->create<fsm::HWInstanceOp>(
263  machineOp.getLoc(), machineOutputTypes, b->getStringAttr("controller"),
264  machineOp.getSymNameAttr(), fsmInputs, clk, componentOp.getResetPort());
265 
266  // Record the FSM output group go signals.
267  for (auto namedAttr : groupGoOutputsAttr.getValue()) {
268  auto name = namedAttr.getName();
269  auto idx = namedAttr.getValue().cast<IntegerAttr>().getInt();
270  groupGoSignals[name] = fsmInstance.getResult(idx);
271  }
272 
273  // Assign FSM top level done to the component done.
274  b->setInsertionPointToEnd(componentOp.getWiresOp().getBodyBlock());
275  b->create<calyx::AssignOp>(machineOp.getLoc(), componentOp.getDonePort(),
276  fsmInstance.getResult(topLevelDoneAttr.getInt()));
277 
278  return success();
279 }
280 
281 void CalyxRemoveGroupsFromFSM::runOnOperation() {
282  componentOp = getOperation();
283  auto *ctx = componentOp.getContext();
284  auto builder = OpBuilder(ctx);
285  builder.setInsertionPointToStart(&componentOp.getBody().front());
286  auto backedgeBuilder = BackedgeBuilder(builder, componentOp.getLoc());
287  b = &builder;
288  bb = &backedgeBuilder;
289 
290  // Locate the FSM machine in the control op..
291  auto machineOps = componentOp.getControlOp().getOps<fsm::MachineOp>();
292  if (std::distance(machineOps.begin(), machineOps.end()) != 1) {
293  emitError(componentOp.getLoc())
294  << "Expected exactly one fsm.MachineOp in the control op";
295  signalPassFailure();
296  return;
297  }
298  machineOp = *machineOps.begin();
299 
300  if (failed(outlineMachine()) || failed(modifyGroupOperations())) {
301  signalPassFailure();
302  return;
303  }
304 
305  inlineGroups();
306 }
307 
308 std::unique_ptr<mlir::Pass> circt::createRemoveGroupsFromFSMPass() {
309  return std::make_unique<CalyxRemoveGroupsFromFSM>();
310 }
assert(baseType &&"element must be base type")
Builder builder
static std::optional< APInt > getInt(Value value)
Helper to convert a value to a constant integer if it is one.
static void modifyGroupOperations(ComponentOp component)
Makes several modifications to the operations of a GroupOp:
void inlineGroups(ComponentOp component)
Inlines each group in the WiresOp.
Instantiate one of these and use it to build typed backedges.
static constexpr std::string_view sGroupDoneInputs
Definition: CalyxToFSM.h:32
static constexpr std::string_view sFSMTopLevelGoIndex
Definition: CalyxToFSM.h:37
static constexpr std::string_view sFSMTopLevelDoneIndex
Definition: CalyxToFSM.h:39
static constexpr std::string_view sGroupGoOutputs
Definition: CalyxToFSM.h:34
static constexpr std::string_view clkPort
Definition: CalyxOps.h:34
static void updateGroupAssignmentGuards(OpBuilder &builder, GroupOp &group, Op &op)
Updates the guard of each assignment within a group with op.
Definition: CalyxHelpers.h:67
This file defines an intermediate representation for circuits acting as an abstraction for constraint...
Definition: DebugAnalysis.h:21
std::unique_ptr< mlir::Pass > createRemoveGroupsFromFSMPass()
Definition: fsm.py:1