CIRCT  19.0.0git
CalyxToFSM.cpp
Go to the documentation of this file.
1 //===- CalyxToFSM.cpp - Calyx to FSM conversion 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 // This is the main Calyx control to FSM Conversion Pass Implementation.
10 //
11 //===----------------------------------------------------------------------===//
12 
14 #include "../PassDetail.h"
21 #include "llvm/ADT/TypeSwitch.h"
22 
23 using namespace mlir;
24 using namespace circt;
25 using namespace calyx;
26 using namespace fsm;
27 using namespace sv;
28 
29 namespace {
30 
31 class CompileFSMVisitor {
32 public:
33  CompileFSMVisitor(SymbolCache &sc, FSMGraph &graph)
34  : graph(graph), sc(sc), ctx(graph.getMachine().getContext()),
35  builder(graph.getMachine().getContext()) {
36  ns.add(sc);
37  }
38 
39  /// Lowers the provided 'op' into a new FSM StateOp.
40  LogicalResult dispatch(StateOp currentState, Operation *op,
41  StateOp nextState) {
42  return TypeSwitch<Operation *, LogicalResult>(op)
43  .template Case<SeqOp, EnableOp, IfOp, WhileOp>(
44  [&](auto opNode) { return visit(currentState, opNode, nextState); })
45  .Default([&](auto) {
46  return op->emitError() << "Operation '" << op->getName()
47  << "' not supported for FSM compilation";
48  });
49  }
50 
51  ArrayRef<Attribute> getCompiledGroups() { return compiledGroups; }
52 
53 private:
54  /// Operation visitors;
55  /// Apart from the visited operation, a visitor is provided with two extra
56  /// arguments:
57  /// currentState:
58  /// This represents a state which the callee has allocated to this visitor;
59  /// the visitor is free to use this state to its liking.
60  /// nextState:
61  /// This represent the next state which this visitor eventually must
62  /// transition to.
63  LogicalResult visit(StateOp currentState, SeqOp, StateOp nextState);
64  LogicalResult visit(StateOp currentState, EnableOp, StateOp nextState);
65  LogicalResult visit(StateOp currentState, IfOp, StateOp nextState);
66  LogicalResult visit(StateOp currentState, WhileOp, StateOp nextState);
67 
68  /// Represents unique state name scopes generated from pushing states onto
69  /// the state stack. The guard carries a unique name as well as managing the
70  /// lifetime of suffixes on the state stack.
71  struct StateScopeGuard {
72  public:
73  StateScopeGuard(CompileFSMVisitor &visitor, StringRef name,
74  StringRef suffix)
75  : visitor(visitor), name(name) {
76  visitor.stateStack.push_back(suffix.str());
77  }
78  ~StateScopeGuard() {
79  assert(!visitor.stateStack.empty());
80  visitor.stateStack.pop_back();
81  }
82 
83  StringRef getName() { return name; }
84 
85  private:
86  CompileFSMVisitor &visitor;
87  std::string name;
88  };
89 
90  /// Generates a new state name based on the current state stack and the
91  /// provided suffix. The new suffix is pushed onto the state stack. Returns a
92  /// guard object which pops the new suffix upon destruction.
93  StateScopeGuard pushStateScope(StringRef suffix) {
94  std::string name;
95  llvm::raw_string_ostream ss(name);
96  llvm::interleave(
97  stateStack, ss, [&](const auto &it) { ss << it; }, "_");
98  ss << "_" << suffix.str();
99  return StateScopeGuard(*this, ns.newName(name), suffix);
100  }
101 
102  FSMGraph &graph;
103  SymbolCache &sc;
104  MLIRContext *ctx;
105  OpBuilder builder;
106  Namespace ns;
107  SmallVector<std::string, 4> stateStack;
108 
109  /// Maintain the set of compiled groups within this FSM, to pass Calyx
110  /// verifiers.
111  SmallVector<Attribute, 8> compiledGroups;
112 };
113 
114 LogicalResult CompileFSMVisitor::visit(StateOp currentState, IfOp ifOp,
115  StateOp nextState) {
116  auto stateGuard = pushStateScope("if");
117  auto loc = ifOp.getLoc();
118 
119  // Rename the current state now that we know it's an if header.
120  graph.renameState(currentState, stateGuard.getName());
121 
122  auto lowerBranch = [&](Value cond, StringRef nextStateSuffix, bool invert,
123  Operation *innerBranchOp) {
124  auto branchStateGuard = pushStateScope(nextStateSuffix);
125  auto branchStateOp =
126  graph.createState(builder, ifOp.getLoc(), branchStateGuard.getName())
127  ->getState();
128 
129  auto transitionOp = graph
130  .createTransition(builder, ifOp.getLoc(),
131  currentState, branchStateOp)
132  ->getTransition();
133  transitionOp.ensureGuard(builder);
134  fsm::ReturnOp returnOp = transitionOp.getGuardReturn();
135  OpBuilder::InsertionGuard g(builder);
136  builder.setInsertionPointToStart(&transitionOp.getGuard().front());
137  Value branchTaken = cond;
138  if (invert) {
139  OpBuilder::InsertionGuard g(builder);
140  branchTaken = comb::createOrFoldNot(loc, branchTaken, builder);
141  }
142 
143  returnOp.setOperand(branchTaken);
144 
145  // Recurse into the body of the branch, with an exit state targeting
146  // 'nextState'.
147  if (failed(dispatch(branchStateOp, innerBranchOp, nextState)))
148  return failure();
149  return success();
150  };
151 
152  // Then branch.
153  if (failed(lowerBranch(ifOp.getCond(), "then", /*invert=*/false,
154  &ifOp.getThenBody()->front())))
155  return failure();
156 
157  // Else branch.
158  if (ifOp.elseBodyExists() &&
159  failed(lowerBranch(ifOp.getCond(), "else", /*invert=*/true,
160  &ifOp.getElseBody()->front())))
161  return failure();
162 
163  return success();
164 }
165 
166 LogicalResult CompileFSMVisitor::visit(StateOp currentState, SeqOp seqOp,
167  StateOp nextState) {
168  Location loc = seqOp.getLoc();
169  auto seqStateGuard = pushStateScope("seq");
170 
171  // Create a new state for each nested operation within this seqOp.
172  auto &seqOps = seqOp.getBodyBlock()->getOperations();
173  llvm::SmallVector<std::pair<Operation *, StateOp>> seqStates;
174 
175  // Iterate over the operations within the sequence. We do this in reverse
176  // order to ensure that we always know the next state.
177  StateOp currentOpNextState = nextState;
178  int n = seqOps.size() - 1;
179  for (auto &op : llvm::reverse(*seqOp.getBodyBlock())) {
180  auto subStateGuard = pushStateScope(std::to_string(n--));
181  auto thisStateOp =
182  graph.createState(builder, op.getLoc(), subStateGuard.getName())
183  ->getState();
184  seqStates.insert(seqStates.begin(), {&op, thisStateOp});
185  sc.addSymbol(thisStateOp);
186 
187  // Recurse into the current operation.
188  if (failed(dispatch(thisStateOp, &op, currentOpNextState)))
189  return failure();
190 
191  // This state is now the next state for the following operation.
192  currentOpNextState = thisStateOp;
193  }
194 
195  // Make 'currentState' transition directly the first state in the sequence.
196  graph.createTransition(builder, loc, currentState, seqStates.front().second);
197 
198  return success();
199 }
200 
201 LogicalResult CompileFSMVisitor::visit(StateOp currentState, WhileOp whileOp,
202  StateOp nextState) {
203  OpBuilder::InsertionGuard g(builder);
204  auto whileStateGuard = pushStateScope("while");
205  auto loc = whileOp.getLoc();
206 
207  // The current state is the while header (branch to whileOp or nextState).
208  // Rename the current state now that we know it's a while header state.
209  StateOp whileHeaderState = currentState;
210  graph.renameState(whileHeaderState,
211  (whileStateGuard.getName() + "_header").str());
212  sc.addSymbol(whileHeaderState);
213 
214  // Dispatch into the while body. The while body will always return to the
215  // header.
216  auto whileBodyEntryState =
217  graph
218  .createState(builder, loc,
219  (whileStateGuard.getName() + "_entry").str())
220  ->getState();
221  sc.addSymbol(whileBodyEntryState);
222  Operation *whileBodyOp = &whileOp.getBodyBlock()->front();
223  if (failed(dispatch(whileBodyEntryState, whileBodyOp, whileHeaderState)))
224  return failure();
225 
226  // Create transitions to either the while body or the next state based on the
227  // while condition.
228  auto bodyTransition =
229  graph
230  .createTransition(builder, loc, whileHeaderState, whileBodyEntryState)
231  ->getTransition();
232  auto nextStateTransition =
233  graph.createTransition(builder, loc, whileHeaderState, nextState)
234  ->getTransition();
235 
236  bodyTransition.ensureGuard(builder);
237  bodyTransition.getGuardReturn().setOperand(whileOp.getCond());
238  nextStateTransition.ensureGuard(builder);
239  builder.setInsertionPoint(nextStateTransition.getGuardReturn());
240  nextStateTransition.getGuardReturn().setOperand(
241  comb::createOrFoldNot(loc, whileOp.getCond(), builder));
242  return success();
243 }
244 
245 LogicalResult CompileFSMVisitor::visit(StateOp currentState, EnableOp enableOp,
246  StateOp nextState) {
247  assert(currentState &&
248  "Expected this enableOp to be nested into some provided state");
249 
250  // Rename the current state now that we know it's an enable state.
251  auto enableStateGuard = pushStateScope(enableOp.getGroupName());
252  graph.renameState(currentState, enableStateGuard.getName());
253 
254  // Create a new calyx.enable in the output state referencing the enabled
255  // group. We create a new op here as opposed to moving the existing, to make
256  // callers iterating over nested ops safer.
257  OpBuilder::InsertionGuard g(builder);
258  builder.setInsertionPointToStart(&currentState.getOutput().front());
259  builder.create<calyx::EnableOp>(enableOp.getLoc(), enableOp.getGroupName());
260 
261  if (nextState)
262  graph.createTransition(builder, enableOp.getLoc(), currentState, nextState);
263 
264  // Append this group to the set of compiled groups.
265  compiledGroups.push_back(
266  SymbolRefAttr::get(builder.getContext(), enableOp.getGroupName()));
267 
268  return success();
269 }
270 
271 // CompileInvoke is used to convert invoke operations to group operations and
272 // enable operations.
273 class CompileInvoke {
274 public:
275  CompileInvoke(ComponentOp component, OpBuilder builder)
276  : component(component), builder(builder) {}
277  void compile();
278 
279 private:
280  void lowerInvokeOp(InvokeOp invokeOp);
281  std::string getTransitionName(InvokeOp invokeOp);
282  ComponentOp component;
283  OpBuilder builder;
284  // Part of the group name. It is used to generate unique group names, the
285  // unique counter is reused across multiple calls to lowerInvokeOp, so the
286  // loop that's checking for name uniqueness usually finds a unique name on the
287  // first try.
288  size_t transitionNameTail = 0;
289 };
290 
291 // Access all invokeOp.
292 void CompileInvoke::compile() {
293  llvm::SmallVector<InvokeOp> invokeOps =
294  component.getControlOp().getInvokeOps();
295  for (InvokeOp op : invokeOps)
296  lowerInvokeOp(op);
297 }
298 
299 // Get the name of the generation group.
300 std::string CompileInvoke::getTransitionName(InvokeOp invokeOp) {
301  llvm::StringRef callee = invokeOp.getCallee();
302  std::string transitionNameHead = "invoke_" + callee.str() + "_";
303  std::string transitionName;
304 
305  // The following loop is used to check if the transitionName already exists.
306  // If it does, the loop regenerates the transitionName.
307  do {
308  transitionName = transitionNameHead + std::to_string(transitionNameTail++);
309  } while (component.getWiresOp().lookupSymbol(transitionName));
310  return transitionName;
311 }
312 
313 // Convert an invoke operation to a group operation and an enable operation.
314 void CompileInvoke::lowerInvokeOp(InvokeOp invokeOp) {
315  // Create a ConstantOp to assign a value to the go port.
316  Operation *prevNode = component.getWiresOp().getOperation()->getPrevNode();
317  builder.setInsertionPointAfter(prevNode);
318  hw::ConstantOp constantOp = builder.create<hw::ConstantOp>(
319  prevNode->getLoc(), builder.getI1Type(), 1);
320  Location loc = component.getWiresOp().getLoc();
321 
322  // Set the insertion point at the end of the wires block.
323  builder.setInsertionPointToEnd(component.getWiresOp().getBodyBlock());
324  std::string transitionName = getTransitionName(invokeOp);
325  GroupOp groupOp = builder.create<GroupOp>(loc, transitionName);
326  builder.setInsertionPointToStart(groupOp.getBodyBlock());
327  Value go = invokeOp.getInstGoValue();
328 
329  // Assign a value to the go port.
330  builder.create<AssignOp>(loc, go, constantOp);
331  auto ports = invokeOp.getPorts();
332  auto inputs = invokeOp.getInputs();
333 
334  // Generate a series of assignment operations from a list of parameters.
335  for (auto [port, input] : llvm::zip(ports, inputs))
336  builder.create<AssignOp>(loc, port, input);
337  Value done = invokeOp.getInstDoneValue();
338 
339  // Generate a group_done operation with the instance's done port.
340  builder.create<calyx::GroupDoneOp>(loc, done);
341  builder.setInsertionPointAfter(invokeOp.getOperation());
342  builder.create<EnableOp>(invokeOp.getLoc(), transitionName);
343  invokeOp.erase();
344 }
345 
346 class CalyxToFSMPass : public CalyxToFSMBase<CalyxToFSMPass> {
347 public:
348  void runOnOperation() override;
349 }; // end anonymous namespace
350 
351 void CalyxToFSMPass::runOnOperation() {
352  ComponentOp component = getOperation();
353  OpBuilder builder(&getContext());
354  auto ctrlOp = component.getControlOp();
355  assert(ctrlOp.getBodyBlock()->getOperations().size() == 1 &&
356  "Expected a single top-level operation in the schedule");
357  CompileInvoke compileInvoke(component, builder);
358  compileInvoke.compile();
359  Operation &topLevelCtrlOp = ctrlOp.getBodyBlock()->front();
360  builder.setInsertionPoint(&topLevelCtrlOp);
361 
362  // Create a side-effect-only FSM (no inputs, no outputs) which will strictly
363  // refer to the symbols and SSA values defined in the regions of the
364  // ComponentOp. This makes for an intermediate step, which allows for
365  // outlining the FSM (materializing FSM I/O) at a later point.
366  auto machineName = ("control_" + component.getName()).str();
367  auto funcType = FunctionType::get(&getContext(), {}, {});
368  auto machine =
369  builder.create<MachineOp>(ctrlOp.getLoc(), machineName,
370  /*initialState=*/"fsm_entry", funcType);
371  auto graph = FSMGraph(machine);
372 
373  SymbolCache sc;
374  sc.addDefinitions(machine);
375 
376  // Create entry and exit states
377  auto entryState =
378  graph.createState(builder, ctrlOp.getLoc(), calyxToFSM::sEntryStateName)
379  ->getState();
380  auto exitState =
381  graph.createState(builder, ctrlOp.getLoc(), calyxToFSM::sExitStateName)
382  ->getState();
383 
384  auto visitor = CompileFSMVisitor(sc, graph);
385  if (failed(visitor.dispatch(entryState, &topLevelCtrlOp, exitState))) {
386  signalPassFailure();
387  return;
388  }
389 
390  // Remove the top-level calyx control operation that we've now converted to an
391  // FSM.
392  topLevelCtrlOp.erase();
393 
394  // Add the set of compiled groups as an attribute to the fsm.
395  machine->setAttr(
396  "compiledGroups",
397  ArrayAttr::get(builder.getContext(), visitor.getCompiledGroups()));
398 }
399 
400 } // namespace
401 
402 std::unique_ptr<mlir::Pass> circt::createCalyxToFSMPass() {
403  return std::make_unique<CalyxToFSMPass>();
404 }
assert(baseType &&"element must be base type")
llvm::SmallVector< StringAttr > inputs
Builder builder
A namespace that is used to store existing names and generate new names in some scope within the IR.
Definition: Namespace.h:29
void addDefinitions(mlir::Operation *top)
Populate the symbol cache with all symbol-defining operations within the 'top' operation.
Definition: SymCache.cpp:23
void addSymbol(mlir::SymbolOpInterface op)
Adds the symbol-defining 'op' to the cache.
Definition: SymCache.h:33
Default symbol cache implementation; stores associations between names (StringAttr's) to mlir::Operat...
Definition: SymCache.h:85
static constexpr std::string_view sExitStateName
Definition: CalyxToFSM.h:31
static constexpr std::string_view sEntryStateName
Definition: CalyxToFSM.h:30
Direction get(bool isOutput)
Returns an output direction if isOutput is true, otherwise returns an input direction.
Definition: CalyxOps.cpp:53
Value createOrFoldNot(Location loc, Value value, OpBuilder &builder, bool twoState=false)
Create a `‘Not’' gate on a value.
Definition: CombOps.cpp:48
StringAttr getName(ArrayAttr names, size_t idx)
Return the name at the specified index of the ArrayAttr or null if it cannot be determined.
This file defines an intermediate representation for circuits acting as an abstraction for constraint...
Definition: DebugAnalysis.h:21
std::unique_ptr< mlir::Pass > createCalyxToFSMPass()
Definition: CalyxToFSM.cpp:402
Definition: fsm.py:1
Definition: sv.py:1